From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 23721 invoked by alias); 8 Dec 2015 14:27:09 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 23692 invoked by uid 89); 8 Dec 2015 14:27:08 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.1 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-qg0-f48.google.com Received: from mail-qg0-f48.google.com (HELO mail-qg0-f48.google.com) (209.85.192.48) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Tue, 08 Dec 2015 14:27:06 +0000 Received: by qgea14 with SMTP id a14so17824973qge.0 for ; Tue, 08 Dec 2015 06:27:04 -0800 (PST) MIME-Version: 1.0 X-Received: by 10.13.242.133 with SMTP id b127mr2129032ywf.280.1449584823681; Tue, 08 Dec 2015 06:27:03 -0800 (PST) Received: by 10.37.93.11 with HTTP; Tue, 8 Dec 2015 06:27:03 -0800 (PST) In-Reply-To: References: <56667585.5040307@redhat.com> Date: Tue, 08 Dec 2015 14:27:00 -0000 Message-ID: Subject: Re: [RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [1/3] From: Richard Biener To: Jeff Law Cc: gcc-patches Content-Type: text/plain; charset=UTF-8 X-IsSubscribed: yes X-SW-Source: 2015-12/txt/msg00873.txt.bz2 On Tue, Dec 8, 2015 at 3:23 PM, Richard Biener wrote: > On Tue, Dec 8, 2015 at 7:15 AM, Jeff Law wrote: >> >> First in the series. This merely refactors code from tree-ssa-sccvn.c into >> domwalk.c so that other walkers can use it as they see fit. >> >> >> There's an initialization function which sets all edges to executable. >> >> There's a test function to see if a block is reachable. >> >> There's a propagation function to propagate the unreachable property to >> edges. >> >> Finally a function to clear m_unreachable_dom. I consider this a wart. >> Essentially that data member contains the highest unreachable block in the >> dominator tree. Once we've finished processing that block's children, we >> need to clear the member. Ideally clients wouldn't need to call this member >> function. >> >> Bikeshedding on the members names is encouraged. And if someone has a >> clean, simple way to ensure that the m_unreachable_dom member gets cleared >> regardless of whether or not a client has its own after_dom_children >> callback, I'd love to hear it. > > I wonder if it makes more sense to integrate this with the domwalker > itself. Add > a constructor flag to it and do everything in itself. By letting the > before_dom_children > return a taken edge (or NULL if unknown) it can drive the outgoing edge marking. > And the domwalk worker would simply not recurse to dom children for unreachable > blocks. So interface-wise do Index: gcc/domwalk.h =================================================================== --- gcc/domwalk.h (revision 231396) +++ gcc/domwalk.h (working copy) @@ -30,13 +30,16 @@ along with GCC; see the file COPYING3. class dom_walker { public: - dom_walker (cdi_direction direction) : m_dom_direction (direction) {} + dom_walker (cdi_direction direction, + bool skip_unreachable_blocks = false) + : m_dom_direction (direction), + m_skip_unreachable_blocks (skip_unreachable_blocks) {} /* Walk the dominator tree. */ void walk (basic_block); /* Function to call before the recursive walk of the dominator children. */ - virtual void before_dom_children (basic_block) {} + virtual edge before_dom_children (basic_block) {} /* Function to call after the recursive walk of the dominator children. */ virtual void after_dom_children (basic_block) {} @@ -47,6 +50,7 @@ private: if it is set to CDI_POST_DOMINATORS, then we walk the post dominator tree. */ const ENUM_BITFIELD (cdi_direction) m_dom_direction : 2; + const bool m_skip_unreachable_blocks; }; #endif and simply inline all the code into dom_walker::walk. Richard. > Richard. > >> OK for trunk? >> >> >> Jeff >> >> commit 5e53fefae0373768b98d51d5746d43f36cecbe2a >> Author: Jeff Law >> Date: Mon Dec 7 11:32:58 2015 -0700 >> >> * domwalk.h (dom_walker::init_edge_executable): New method. >> (dom_walker::maybe_clear_unreachable_dom): Likewise. >> (dom_walker::bb_reachable): Likewise. >> (dom_walker::propagate_unreachable_to_edges): Likewise. >> (dom_walker::m_unreachable_dom): New private data member. >> * domwalk.c: Include dumpfile.h. >> (dom_walker::init_edge_executable): New method. >> (dom_walker::maybe_clear_unreachable_dom): Likewise. >> (dom_walker::bb_reachable): Likewise. Factored out of >> tree-ssa-sccvn.c >> (dom_walker::propagate_unreachable_to_edges): Likewise. >> * tree-ssa-sccvn.c (sccvn_dom_walker::unreachable_dom): Remove >> private data member. >> (sccvn_dom_walker::after_dom_children): Use methods from dom_walker >> class. >> (sccvn_dom_walker::before_dom_children): Similarly. >> (run_scc_vn): Likewise. >> >> diff --git a/gcc/domwalk.c b/gcc/domwalk.c >> index 167fc38..feb6478 100644 >> --- a/gcc/domwalk.c >> +++ b/gcc/domwalk.c >> @@ -24,6 +24,7 @@ along with GCC; see the file COPYING3. If not see >> #include "backend.h" >> #include "cfganal.h" >> #include "domwalk.h" >> +#include "dumpfile.h" >> >> /* This file implements a generic walker for dominator trees. >> >> @@ -142,6 +143,93 @@ cmp_bb_postorder (const void *a, const void *b) >> return 1; >> } >> >> +/* Mark all edges in the CFG as possibly being executable. */ >> + >> +void >> +dom_walker::init_edge_executable (struct function *fun) >> +{ >> + basic_block bb; >> + FOR_ALL_BB_FN (bb, fun) >> + { >> + edge_iterator ei; >> + edge e; >> + FOR_EACH_EDGE (e, ei, bb->succs) >> + e->flags |= EDGE_EXECUTABLE; >> + } >> +} >> + >> +/* Return TRUE if BB is reachable, false otherwise. */ >> + >> +bool >> +dom_walker::bb_reachable (struct function *fun, basic_block bb) >> +{ >> + /* If any of the predecessor edges that do not come from blocks dominated >> + by us are still marked as possibly executable consider this block >> + reachable. */ >> + bool reachable = false; >> + if (!m_unreachable_dom) >> + { >> + reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (fun); >> + edge_iterator ei; >> + edge e; >> + FOR_EACH_EDGE (e, ei, bb->preds) >> + if (!dominated_by_p (CDI_DOMINATORS, e->src, bb)) >> + reachable |= (e->flags & EDGE_EXECUTABLE); >> + } >> + >> + return reachable; >> +} >> + >> +/* BB has been determined to be unreachable. Propagate that property >> + to incoming and outgoing edges of BB as appropriate. */ >> + >> +void >> +dom_walker::propagate_unreachable_to_edges (basic_block bb, >> + FILE *dump_file, >> + int dump_flags) >> +{ >> + if (dump_file && (dump_flags & TDF_DETAILS)) >> + fprintf (dump_file, "Marking all outgoing edges of unreachable " >> + "BB %d as not executable\n", bb->index); >> + >> + edge_iterator ei; >> + edge e; >> + FOR_EACH_EDGE (e, ei, bb->succs) >> + e->flags &= ~EDGE_EXECUTABLE; >> + >> + FOR_EACH_EDGE (e, ei, bb->preds) >> + { >> + if (dominated_by_p (CDI_DOMINATORS, e->src, bb)) >> + { >> + if (dump_file && (dump_flags & TDF_DETAILS)) >> + fprintf (dump_file, "Marking backedge from BB %d into " >> + "unreachable BB %d as not executable\n", >> + e->src->index, bb->index); >> + e->flags &= ~EDGE_EXECUTABLE; >> + } >> + } >> + >> + if (!m_unreachable_dom) >> + m_unreachable_dom = bb; >> +} >> + >> +/* When we propagate the unreachable property to edges, we >> + also arrange to track the highest block in the dominator >> + walk which was unreachable. We can use that to identify >> + more unreachable blocks. >> + >> + When we finish processing the dominator children for that >> + highest unreachable block, we need to make sure to clear >> + that recorded highest block unreachable block in the >> + dominator tree. */ >> + >> +void >> +dom_walker::maybe_clear_unreachable_dom (basic_block bb) >> +{ >> + if (m_unreachable_dom == bb) >> + m_unreachable_dom = NULL; >> +} >> + >> /* Recursively walk the dominator tree. >> BB is the basic block we are currently visiting. */ >> >> diff --git a/gcc/domwalk.h b/gcc/domwalk.h >> index 71a7c47..d6b37a2 100644 >> --- a/gcc/domwalk.h >> +++ b/gcc/domwalk.h >> @@ -30,7 +30,8 @@ along with GCC; see the file COPYING3. If not see >> class dom_walker >> { >> public: >> - dom_walker (cdi_direction direction) : m_dom_direction (direction) {} >> + dom_walker (cdi_direction direction) : m_dom_direction (direction), >> + m_unreachable_dom (NULL) {} >> >> /* Walk the dominator tree. */ >> void walk (basic_block); >> @@ -41,12 +42,41 @@ public: >> /* Function to call after the recursive walk of the dominator children. >> */ >> virtual void after_dom_children (basic_block) {} >> >> + /* The next several methods support discovering unreachable blocks >> + and edges in the CFG during the dominator walk. Using these routines >> + is totally optional and only makes sense if your walker can change >> + the state of a block/edge to unreachable/unexecutable and your walker >> + can exploit that information to optimize better. */ >> + >> + /* Set EDGE_EXECUTABLE for every edge in the CFG. This must be done >> + before walking begins. */ >> + void init_edge_executable (struct function *); >> + >> + /* Query whether or not the given block is reachable or not. >> + >> + Typically used in the before_dom_children callback. */ >> + bool bb_reachable (struct function *, basic_block); >> + >> + /* Given an unreachable block, propagate that property to outgoing >> + and possibly incoming edges for the block. Typically called after >> + determining a block is unreachable in the before_dom_children >> + callback. */ >> + void propagate_unreachable_to_edges (basic_block, FILE *, int); >> + >> + /* This is a bit of a wart. We need to conditionally clear a bit of >> + state after we have process the dominator children. >> + >> + I'd prefer to hide this detail within domwalk, but right now it >> + bleeds out into the clients. */ >> + void maybe_clear_unreachable_dom (basic_block); >> + >> private: >> /* This is the direction of the dominator tree we want to walk. i.e., >> if it is set to CDI_DOMINATORS, then we walk the dominator tree, >> if it is set to CDI_POST_DOMINATORS, then we walk the post >> dominator tree. */ >> const ENUM_BITFIELD (cdi_direction) m_dom_direction : 2; >> + basic_block m_unreachable_dom; >> }; >> >> #endif >> diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c >> index 2014ee7..dbd61c9 100644 >> --- a/gcc/tree-ssa-sccvn.c >> +++ b/gcc/tree-ssa-sccvn.c >> @@ -4207,8 +4207,7 @@ class sccvn_dom_walker : public dom_walker >> { >> public: >> sccvn_dom_walker () >> - : dom_walker (CDI_DOMINATORS), fail (false), unreachable_dom (NULL), >> - cond_stack (vNULL) {} >> + : dom_walker (CDI_DOMINATORS), fail (false), cond_stack (vNULL) {} >> ~sccvn_dom_walker (); >> >> virtual void before_dom_children (basic_block); >> @@ -4220,7 +4219,6 @@ public: >> enum tree_code code, tree lhs, tree rhs, bool value); >> >> bool fail; >> - basic_block unreachable_dom; >> vec > > >> cond_stack; >> }; >> @@ -4301,8 +4299,7 @@ sccvn_dom_walker::record_conds (basic_block bb, >> void >> sccvn_dom_walker::after_dom_children (basic_block bb) >> { >> - if (unreachable_dom == bb) >> - unreachable_dom = NULL; >> + this->maybe_clear_unreachable_dom (bb); >> >> while (!cond_stack.is_empty () >> && cond_stack.last ().first == bb) >> @@ -4327,45 +4324,11 @@ sccvn_dom_walker::before_dom_children (basic_block >> bb) >> if (fail) >> return; >> >> - /* If any of the predecessor edges that do not come from blocks dominated >> - by us are still marked as possibly executable consider this block >> - reachable. */ >> - bool reachable = false; >> - if (!unreachable_dom) >> + /* If BB is not reachable, then propagate that property to edges, but >> + do not process this block any further. */ >> + if (!this->bb_reachable (cfun, bb)) >> { >> - reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (cfun); >> - FOR_EACH_EDGE (e, ei, bb->preds) >> - if (!dominated_by_p (CDI_DOMINATORS, e->src, bb)) >> - reachable |= (e->flags & EDGE_EXECUTABLE); >> - } >> - >> - /* If the block is not reachable all outgoing edges are not >> - executable. Neither are incoming edges with src dominated by us. */ >> - if (!reachable) >> - { >> - if (dump_file && (dump_flags & TDF_DETAILS)) >> - fprintf (dump_file, "Marking all outgoing edges of unreachable " >> - "BB %d as not executable\n", bb->index); >> - >> - FOR_EACH_EDGE (e, ei, bb->succs) >> - e->flags &= ~EDGE_EXECUTABLE; >> - >> - FOR_EACH_EDGE (e, ei, bb->preds) >> - { >> - if (dominated_by_p (CDI_DOMINATORS, e->src, bb)) >> - { >> - if (dump_file && (dump_flags & TDF_DETAILS)) >> - fprintf (dump_file, "Marking backedge from BB %d into " >> - "unreachable BB %d as not executable\n", >> - e->src->index, bb->index); >> - e->flags &= ~EDGE_EXECUTABLE; >> - } >> - } >> - >> - /* Record the most dominating unreachable block. */ >> - if (!unreachable_dom) >> - unreachable_dom = bb; >> - >> + this->propagate_unreachable_to_edges (bb, dump_file, dump_flags); >> return; >> } >> >> @@ -4519,7 +4482,6 @@ sccvn_dom_walker::before_dom_children (basic_block bb) >> bool >> run_scc_vn (vn_lookup_kind default_vn_walk_kind_) >> { >> - basic_block bb; >> size_t i; >> >> default_vn_walk_kind = default_vn_walk_kind_; >> @@ -4549,18 +4511,10 @@ run_scc_vn (vn_lookup_kind default_vn_walk_kind_) >> } >> } >> >> - /* Mark all edges as possibly executable. */ >> - FOR_ALL_BB_FN (bb, cfun) >> - { >> - edge_iterator ei; >> - edge e; >> - FOR_EACH_EDGE (e, ei, bb->succs) >> - e->flags |= EDGE_EXECUTABLE; >> - } >> - >> /* Walk all blocks in dominator order, value-numbering stmts >> SSA defs and decide whether outgoing edges are not executable. */ >> sccvn_dom_walker walker; >> + walker.init_edge_executable (cfun); >> walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun)); >> if (walker.fail) >> { >>