| Message ID | CABu31nNHjWr92Pm8HrX_fO7_VFj2W=8XkrLiWgWbuN5aoUZZVg@mail.gmail.com |
|---|---|
| State | New |
| Headers | show |
On 01/05/2013 01:10 PM, Steven Bosscher wrote: >> >> Presumably BB7 was created in response to the builtin_unreachable? > > Yes. The block only contains the BB_UNREACHABLE call. It is cleaned up > at the end of the GIMPLE passes pipeline, in the fold-all-builtins > pass (most __builtin_unreachable calls are, but not all). I think if you eliminate the block and the cleanup the CFG appropriately, the right thing will just happen. > The problem with this, is that __builtin_unreachable actually exposes > optimization opportunities: more const/copy props of "implicit sets" > in the predicate guarding the __builtin_unreachable call, more > optimistic value numbering, etc. It also helps improve maybe-unused > warnings accuracy. So simply removing these "dead ends" in the CFG is > probably not a good idea. ?!? By removing the empty unreachable block that's precisely what you enable. The block itself goes away and the branch leading to the block is simplified appropriately. That in turn will create larger basic blocks, enabling the const/copy propagations and similar optimizations. Finally removing unreachable paths was insired by the desire to eliminate false positives from maybe-{unused,uninitialized} and similar warnings. I'd be very curious to see the conditions under which removing the empty unreachable and appropriate cleanup of the CFG (including the underlying control statement) results in less optimizations and less precision in our may-warnings. > > I think there is one important difference: In the thread you referred > to, you're removing paths in the CFG that are implicitly not > executable (for some languages anyway), whereas a > __builtin_unreachable call is an explicit marker for "this can never > happen". I think this difference is important: I don't see this as an important distinction. The difference is in the implicit "can't happen" case, eliminating the "can't happen" path may eliminate a user visible side effect (for example a segfault). > > * The explicit marker may have been put there on purpose (e.g. to get > rid of a false-positive warning). The compiler should respect that. An > implicit unreachable path can be optimized away without regard for the > user's intent. Right, but if done right, eliminating the unreachable path correctly should eliminate false positive warnings. > > * The explicit marker should not inhibit optimizations. For an > implicit unreachable path the compiler should be conservative. But for > a __builtin_unreachable call that is the only statement in a basic > block, the compiler should be allowed to work as if the block really > is never reached. Right. > > The attached patch implements these ideas. During a tree-CFG cleanup, > basic blocks containing only a __builtin_unreachable call are marked > with a new flag BB_NEVER_REACHED. The flag is used in post-dominance: > A marked block is not considered in the computations of the immediate > post-dominator of the predecessor blocks. The result is a more > optimistic post-dominance tree: Without the patch all predecessors of > these BB_NEVER_REACHED blocks have the EXIT block as their > post-dominator, but with the patch this non-executable path in the CFG > is ignored and the post-dominators are those that would result if the > BB_NEVER_REACHED blocks are not there at all (the BB_NEVER_REACHED > blocks themselves are only post-dominated by the EXIT block). > > I've also added a control dependence calculation function. It's not > currently used, but it shows how the BB_NEVER_REACHED flag is used in > this case to avoid the "false" control dependences that I showed in > the graphs in http://gcc.gnu.org/ml/gcc/2013-01/msg00021.html. > > Bootstrapped&tested on powerpc64-unknown-linux-gnu. > What do you think of this approach? Before diving into the patch I think we should figure out why we see such different effects of eliminating these paths from the CFG. Your assertion is eliminating them will result in more false positives and less optimization while my assertion is the opposite. Jeff
On Mon, Jan 7, 2013 at 8:45 PM, Jeff Law <law@redhat.com> wrote: > Before diving into the patch I think we should figure out why we see such > different effects of eliminating these paths from the CFG. Your assertion > is eliminating them will result in more false positives and less > optimization while my assertion is the opposite. Warnings: $ cat q.c #if 0 #define UNREACHABLE() __builtin_unreachable() #else #define UNREACHABLE() break #endif typedef enum fruits { banana = 0, apple = 1, pear = 2, orange = 3 } fruit; extern void price_fruit_of_the_day (int); void discount_of_the_day (fruit f) { int p, c = (int) f; switch (f) { case banana: UNREACHABLE (); case apple: p = 3 * c + 4; break; case pear: case orange: p = 7; break; } price_fruit_of_the_day (p); } $ # Compiled with UNREACHABLE defined as break: $ ./cc1 -quiet -W -Wall -Wextra q.c -fdump-tree-all -O1 q.c: In function 'discount_of_the_day': q.c:28:26: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized] price_fruit_of_the_day (p); ^ $ # Compiled with UNREACHABLE defined as builtin_unreachable: $ ./cc1 -quiet -W -Wall -Wextra q.c -fdump-tree-all -O1 $ For optimizations it's a bit more difficult. The situations I'm looking at, are all sinking related, and I suspect that most missed optimizations will be of this form: int foo (int b, int c, int d) { int res, r = 0; res = 5 * d + b; if (d) __builtin_unreachable (); if (c) r = res; return r; } The "res =" statement can be sunk into the conditional arm of "if(c)" and tree-ssa-sink.c is able to do so. But secondary effects are missed (and test cases for this are hard to reduce to mailing list acceptable size ;-) because tree-ssa-sink walks the post-dominator tree and, with the right amount of bad luck, it visits the "res=" statement _before_ the part of the (forward-)dominator tree below "if(d)" because the basic block containing "res=" has EXIT as its immediate post-dominator, because that's where __builtin_unreachable() leads to. The "optimistic" post-dominator of "res=" is the "if(c)" block, of course, because the builtin_unreachable is a kind-of assert, not something that can really ever happen. I already showed how the control dependence graph looks Wrong with __builtin_unreachable calls in place. Any transformation using the CDG will also be less effective because of this. Ciao! Steven
On Mon, Jan 7, 2013 at 8:45 PM, Jeff Law <law@redhat.com> wrote: > On 01/05/2013 01:10 PM, Steven Bosscher wrote: >>> >>> >>> Presumably BB7 was created in response to the builtin_unreachable? >> >> >> Yes. The block only contains the BB_UNREACHABLE call. It is cleaned up >> at the end of the GIMPLE passes pipeline, in the fold-all-builtins >> pass (most __builtin_unreachable calls are, but not all). > > I think if you eliminate the block and the cleanup the CFG appropriately, > the right thing will just happen. > > >> The problem with this, is that __builtin_unreachable actually exposes >> optimization opportunities: more const/copy props of "implicit sets" >> in the predicate guarding the __builtin_unreachable call, more >> optimistic value numbering, etc. It also helps improve maybe-unused >> warnings accuracy. So simply removing these "dead ends" in the CFG is >> probably not a good idea. > > ?!? By removing the empty unreachable block that's precisely what you > enable. The block itself goes away and the branch leading to the block is > simplified appropriately. That in turn will create larger basic blocks, > enabling the const/copy propagations and similar optimizations. > > Finally removing unreachable paths was insired by the desire to eliminate > false positives from maybe-{unused,uninitialized} and similar warnings. > > I'd be very curious to see the conditions under which removing the empty > unreachable and appropriate cleanup of the CFG (including the underlying > control statement) results in less optimizations and less precision in our > may-warnings. The issue is VRP - when you remove unreachable blocks you lose the conditional statement as it is no longer necessary and thus the predicate you can derive value-ranges from. Maybe there are more examples. I can imagine false positive may-be warnings then become must-be false positives. There are clearly (as seen here) missed optimizations because we do keep the unreachable blocks around. Note that the whole point of the unreachable () excercise was to be able to implement an assert () that even with -DNDEBUG leaves the compiler with the same optimization opportunities (as of value-range analysis) as with -UNDEBUG. Richard.
On Sat, Jan 5, 2013 at 9:10 PM, Steven Bosscher <stevenb.gcc@gmail.com> wrote: > On Thu, Jan 3, 2013 at 9:51 PM, Jeff Law wrote: >> On 01/03/2013 12:01 PM, Steven Bosscher wrote: >>> >>> Hello, >>> >>> Consider the following test case: >>> >>> void bar (void); >>> int foo (int b, int c, int d) >>> { >>> int r = 0; >>> if (b) >>> res = b * 2 + 4; >>> if (c) >>> { >>> if (d) >>> r = res; >>> else >>> __builtin_unreachable (); >>> } >>> return r; >>> } >>> >>> This is typical for code in GCC itself in places where >>> gcc_unreachable() is used. >> >> >>> >>> The corresponding CFG looks like this: >>> >>> +-----+ >>> | bb0 | >>> +-----+ >>> | >>> | >>> v >>> +-----+ >>> | bb2 | -+ >>> +-----+ | >>> | | >>> | | >>> v | >>> +-----+ | >>> | bb3 | | >>> +-----+ | >>> | | >>> | | >>> v | >>> +-----+ +-----+ | >>> | bb8 | <-- | bb4 | <+ >>> +-----+ +-----+ >>> | | >>> | | >>> | v >>> | +-----+ +-----+ >>> | | bb5 | --> | bb7 | >>> | +-----+ +-----+ >>> | | >>> | | >>> | v >>> | +-----+ >>> | | bb6 | >>> | +-----+ >>> | | >>> | | >>> | v >>> | +-----+ >>> +-------> | bb9 | >>> +-----+ >>> | >>> | >>> v >>> +-----+ >>> | bb1 | >>> +-----+ >> >> Presumably BB7 was created in response to the builtin_unreachable? > > Yes. The block only contains the BB_UNREACHABLE call. It is cleaned up > at the end of the GIMPLE passes pipeline, in the fold-all-builtins > pass (most __builtin_unreachable calls are, but not all). > > >> One >> could argue that an empty dead-end basic block should just be removed and >> the CFG appropriately simplified. > > The problem with this, is that __builtin_unreachable actually exposes > optimization opportunities: more const/copy props of "implicit sets" > in the predicate guarding the __builtin_unreachable call, more > optimistic value numbering, etc. It also helps improve maybe-unused > warnings accuracy. So simply removing these "dead ends" in the CFG is > probably not a good idea. > > >> You might want to look at a discussion from Oct/Nov 2011 "New pass to >> delete unexecutable paths in the CFG" which touches on some of this stuff. > > That's a really interesting discussion! I must have missed it at the time :-) > > >> It's not 100% the same, but the concept of eliminating edges from the CFG >> which we can never traverse in a conforming program applies to both your >> example and the stuff I was playing with. > > I think there is one important difference: In the thread you referred > to, you're removing paths in the CFG that are implicitly not > executable (for some languages anyway), whereas a > __builtin_unreachable call is an explicit marker for "this can never > happen". I think this difference is important: > > * The explicit marker may have been put there on purpose (e.g. to get > rid of a false-positive warning). The compiler should respect that. An > implicit unreachable path can be optimized away without regard for the > user's intent. > > * The explicit marker should not inhibit optimizations. For an > implicit unreachable path the compiler should be conservative. But for > a __builtin_unreachable call that is the only statement in a basic > block, the compiler should be allowed to work as if the block really > is never reached. > > The attached patch implements these ideas. During a tree-CFG cleanup, > basic blocks containing only a __builtin_unreachable call are marked > with a new flag BB_NEVER_REACHED. The flag is used in post-dominance: > A marked block is not considered in the computations of the immediate > post-dominator of the predecessor blocks. The result is a more > optimistic post-dominance tree: Without the patch all predecessors of > these BB_NEVER_REACHED blocks have the EXIT block as their > post-dominator, but with the patch this non-executable path in the CFG > is ignored and the post-dominators are those that would result if the > BB_NEVER_REACHED blocks are not there at all (the BB_NEVER_REACHED > blocks themselves are only post-dominated by the EXIT block). > > I've also added a control dependence calculation function. It's not > currently used, but it shows how the BB_NEVER_REACHED flag is used in > this case to avoid the "false" control dependences that I showed in > the graphs in http://gcc.gnu.org/ml/gcc/2013-01/msg00021.html. > > Bootstrapped&tested on powerpc64-unknown-linux-gnu. > What do you think of this approach? Does it handle side-effects on the builtin-unreachable path correctly? int b; int a; extern void foo (); int main() { if (!a) { if (!b) foo (); __builtin_unreachable (); } } --- void foo () { puts("Hello"); exit(0); } ? Users are not _required_ to annotate noreturn functions. The BB with __builtin_unreachable () is still empty otherwise. Thanks, Richard. > Ciao! > Steven
On 01/08/2013 04:26 AM, Richard Biener wrote: > > The issue is VRP - when you remove unreachable blocks you lose the > conditional statement as it is no longer necessary and thus the predicate > you can derive value-ranges from. Understood. Perhaps we could eliminate them after the first VRP pass, but before the second. That ought to give us the majority of the benefit of seeing the conditional and propagating based on the conditional, but also give us the benefit of eliminating the branch generating straight-line code. Clearly it needs more investigation, but I think it's worth exploring. Jeff
On Tue, Jan 8, 2013 at 12:32 PM, Richard Biener wrote: > Does it handle side-effects on the builtin-unreachable path correctly? > > int b; > int a; > extern void foo (); > int main() > { > if (!a) > { > if (!b) > foo (); > __builtin_unreachable (); > } > } > > --- > > void foo () { puts("Hello"); exit(0); } > > ? Users are not _required_ to annotate noreturn functions. The BB with > __builtin_unreachable () is still empty otherwise. Not sure what you're expecting in this case, so guessing... There is a warning for "reaching end of non-void" blah, but that's correct on the a!=0 path. With that if(!a) commented out, I don't have that warning of course. The code is identical with and without patch. It's another example of how __builtin_unreachable() helps hide unnecessary warnings. Ciao! Steven
On Tue, Jan 8, 2013 at 5:16 PM, Jeff Law <law@redhat.com> wrote: > On 01/08/2013 04:26 AM, Richard Biener wrote: > >> >> The issue is VRP - when you remove unreachable blocks you lose the >> conditional statement as it is no longer necessary and thus the predicate >> you can derive value-ranges from. > > Understood. Perhaps we could eliminate them after the first VRP pass, but > before the second. That ought to give us the majority of the benefit of > seeing the conditional and propagating based on the conditional, but also > give us the benefit of eliminating the branch generating straight-line code. > > Clearly it needs more investigation, but I think it's worth exploring. Sure - especially if we eventually move to preserve value-range information across passes. __builtin_constant_p is a similar thing - it guards one reachable and one unreachable path but we forcefully remove it only during the late fold-all-builtins pass. Richard. > Jeff
On 01/07/2013 01:42 PM, Steven Bosscher wrote: > typedef enum fruits { banana = 0, apple = 1, pear = 2, orange = 3 } fruit; > > extern void price_fruit_of_the_day (int); > > void > discount_of_the_day (fruit f) > { > int p, c = (int) f; > switch (f) > { > case banana: > UNREACHABLE (); > case apple: > p = 3 * c + 4; > break; > case pear: > case orange: > p = 7; > break; > } > price_fruit_of_the_day (p); > } So if we look at this (I'll analyze the other cases separately). In reassoc2 we have: # BLOCK 2 freq:10000 # PRED: ENTRY [100.0%] (fallthru,exec) c_3 = (int) f_2(D); switch (f_2(D)) <default: <L4>, case 0: <L0>, case 1: <L1>, case 2 ... 3: <L2>> # SUCC: 6 [25.0%] (exec) 3 [25.0%] (exec) 4 [25.0%] (exec) 5 [25.0%] (exec) # BLOCK 3 freq:2500 # PRED: 2 [25.0%] (exec) <L0>: # VUSE <.MEM_8(D)> __builtin_unreachable (); # SUCC: # BLOCK 4 freq:2500 # PRED: 2 [25.0%] (exec) <L1>: D.1724_5 = c_3 * 3; p_6 = D.1724_5 + 4; goto <bb 6> (<L4>); # SUCC: 6 [100.0%] (fallthru,exec) # BLOCK 5 freq:2500 # PRED: 2 [25.0%] (exec) <L2>: # SUCC: 6 [100.0%] (fallthru,exec) # BLOCK 6 freq:7500 # PRED: 2 [25.0%] (exec) 4 [100.0%] (fallthru,exec) 5 [100.0%] (fallthru,exec) # p_1 = PHI <p_4(D)(2), p_6(4), 7(5)> <L4>: # .MEM_9 = VDEF <.MEM_8(D)> price_fruit_of_the_day (p_1); # VUSE <.MEM_9> return; # SUCC: EXIT [100.0%] } What I'm suggesting is not simply removing the directive at the source level, but at the appropriate time using the knowledge that the block is unreachable to simplify the CFG. In this specific case we would eliminate block #3 and the edge from 2->3. If we do that VRP will come along and do its thing. With the block/edge removals, it will discover that p_6 has the value 7, p_4 is undefined and ultimately it'll collapse the PHI into p_1 = 7. The net result (in this case) will be the same as using builtin_unreachable. Contrast that to simply defining away the directive per your test. In that case we'd still have an edge from 2->3. And when that's the case, VRP won't find a constant for p_6, which ultimately makes p_1 varying and triggers the warning because of the use of p_4 to compute p_1. Jeff
On 01/07/2013 01:42 PM, Steven Bosscher wrote: > For optimizations it's a bit more difficult. Somewhat. For what I'm suggesting, the way we'd miss an optimization would be if by removing the unreachable block and simplifying the CFG we ultimately remove a conditional which produced a result which we could use later. Something like this (tweaking your 2nd test): int foo (int b, int c, int d) { int res, r = 0; res = 5 * d + b; if (d) __builtin_unreachable (); if (c) r = res; return r + d; } What I'm suggesting would effectively remove the conditional and __builtin_unreacahble, so at the source level it'd look like: int foo (int b, int c, int d) { int res, r = 0; res = 5 * d + b; if (c) r = res; return r + d; } By removing the conditional, we've lost the fact that to reach the return statement, "d" must be zero, which is useful in optimizing the return statement. The situations I'm > looking at, are all sinking related, and I suspect that most missed > optimizations will be of this form: > > int foo (int b, int c, int d) > { > int res, r = 0; > res = 5 * d + b; > if (d) > __builtin_unreachable (); > if (c) > r = res; > return r; > } I don't see how my proposal would inhibit sinking in this kind of code. In fact, it'd made it easier. > > I already showed how the control dependence graph looks Wrong with > __builtin_unreachable calls in place. Any transformation using the CDG > will also be less effective because of this. And what I'm suggesting would actually fix the post dominator tree, among other things. Where we potentially lose is the tweaked case above. However, if we do the optimization at the right time, we can get the benefits we're both looking for, I believe. jeff
Index: cfg-flags.def =================================================================== --- cfg-flags.def (revision 194924) +++ cfg-flags.def (working copy) @@ -51,9 +51,26 @@ DEF_BASIC_BLOCK_FLAG(REACHABLE, 1) /* Set for blocks in an irreducible loop by loop analysis. */ DEF_BASIC_BLOCK_FLAG(IRREDUCIBLE_LOOP, 2) -/* Set on blocks that may actually not be single-entry single-exit block. */ +/* Set on blocks that may actually not be single-entry single-exit block. + Only valid in RTL. The value of this flag is overloaded by the + BB_NEVER_REACHED flag. + FIXME: This is only used by the SLJL exception mechanism. Should clean + this up for GCC 4.9. */ DEF_BASIC_BLOCK_FLAG(SUPERBLOCK, 3) +/* Set on blocks that contain only a __builtin_unreachable call. Such blocks + are not really reachable, their only purpose is to inform the compiler that + some path through the control flow graph can never be taken. This flag is + used, for instance, to ignore marked basic blocks in the computation of + post-dominance. This flag is only used in GIMPLE, __builtin_unreachable + calls are either removed during builtin-folding or expanded as BARRIERs. + Note that the meaning of this flag is *not* the complement of BB_REACHABLE. + The latter is set on blocks that are reachable from the CFG entry block. + The BB_NEVER_REACHED flag is only set on basic blocks that have been + marked expelicitly as unreachable using __builtin_unreachable, but such + blocks are usually reachable from ENTRY. */ +DEF_BASIC_BLOCK_FLAG(NEVER_REACHED, 3) + /* Set on basic blocks that the scheduler should not touch. This is used by SMS to prevent other schedulers from messing with the loop schedule. */ DEF_BASIC_BLOCK_FLAG(DISABLE_SCHEDULE, 4) Index: tree-cfgcleanup.c =================================================================== --- tree-cfgcleanup.c (revision 194924) +++ tree-cfgcleanup.c (working copy) @@ -577,6 +577,55 @@ split_bbs_on_noreturn_calls (void) return changed; } +/* Return true if B is empty except for a __builtin_unreachable call and + maybe debug statements and/or removable labels. */ + +static bool +is_only_builtin_unreachable_block (basic_block bb) +{ + gimple_stmt_iterator gsi; + + if (EDGE_COUNT (bb->succs) > 1 + || (EDGE_COUNT (bb->succs) == 1 + && !(single_succ_edge (bb)->flags & EDGE_FAKE))) + return false; + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple stmt = gsi_stmt (gsi); + if (is_gimple_debug (stmt)) + continue; + if (gimple_code (stmt) == GIMPLE_LABEL) + { + if (FORCED_LABEL (gimple_label_label (stmt))) + return false; + continue; + } + if (! is_gimple_builtin_call (stmt) + || DECL_FUNCTION_CODE (gimple_call_fndecl (stmt)) + != BUILT_IN_UNREACHABLE) + return false; + } + return true; +} + +/* Mark basic blocks that only contain a __builtin_unreachabel call as + BB_NEVER_REACHED. Such blocks may appear reachable but, by definition, + really are not reachable. Not marking these blocks is conservative but + may inhibit optimizations (e.g. post-dominance and control dependences + are pessimized if unmarked blocks persist). */ + +static void +mark_builtin_unreachable_blocks (void) +{ + basic_block bb; + FOR_EACH_BB (bb) + { + bb->flags &= ~BB_NEVER_REACHED; + if (is_only_builtin_unreachable_block (bb)) + bb->flags |= BB_NEVER_REACHED; + } +} + /* Tries to cleanup cfg in basic block BB. Returns true if anything changes. */ @@ -652,6 +701,7 @@ cleanup_tree_cfg_1 (void) end_recording_case_labels (); BITMAP_FREE (cfgcleanup_altered_bbs); + mark_builtin_unreachable_blocks (); return retval; } Index: cfgexpand.c =================================================================== --- cfgexpand.c (revision 194924) +++ cfgexpand.c (working copy) @@ -3776,6 +3776,9 @@ expand_gimple_basic_block (basic_block bb, bool di fprintf (dump_file, "\n;; Generating RTL for gimple basic block %d\n", bb->index); + /* This flag has no purpose in RTL land (and clashes with BB_SUPERBLOCK). */ + bb->flags &= ~BB_NEVER_REACHED; + /* Note that since we are now transitioning from GIMPLE to RTL, we cannot use the gsi_*_bb() routines because they expect the basic block to be in GIMPLE, instead of RTL. Therefore, we need to Index: dominance.c =================================================================== --- dominance.c (revision 194924) +++ dominance.c (working copy) @@ -524,7 +524,6 @@ calc_idoms (struct dom_info *di, bool reverse) if (bitmap_bit_p (di->fake_exit_edge, bb->index)) { einext = ei; - einext.index = 0; goto do_fake_exit_edge; } } @@ -543,6 +542,17 @@ calc_idoms (struct dom_info *di, bool reverse) einext = ei; ei_next (&einext); + if (reverse) + { + /* If this is a __builtin_unreachable block, skip it so that + predecessors don't get the EXIT block as post-dominator. */ + if (b->flags & BB_NEVER_REACHED) + { + ei = einext; + continue; + } + } + if (b == en_block) { do_fake_exit_edge: Index: basic-block.h =================================================================== --- basic-block.h (revision 194924) +++ basic-block.h (working copy) @@ -790,6 +790,7 @@ extern int dfs_enumerate_from (basic_block, int, basic_block *, int, const void *); extern void compute_dominance_frontiers (struct bitmap_head_def *); extern bitmap compute_idf (bitmap, struct bitmap_head_def *); +extern void compute_control_dependences (struct bitmap_head_def *); /* In cfgrtl.c */ extern rtx block_label (basic_block); Index: cfganal.c =================================================================== --- cfganal.c (revision 194924) +++ cfganal.c (working copy) @@ -1079,34 +1079,46 @@ dfs_enumerate_from (basic_block bb, int reverse, The number of nodes touched by this algorithm is equal to the size of the dominance frontiers, no more, no less. + + If FORWARD is false, run on the reverse CFG so that control dependences + are computed instead. */ static void -compute_dominance_frontiers_1 (bitmap_head *frontiers) +compute_dominance_frontiers_1 (bitmap_head *frontiers, bool forward) { edge p; edge_iterator ei; basic_block b; + enum cdi_direction dir = forward ? CDI_DOMINATORS : CDI_POST_DOMINATORS; + basic_block entrybb = forward ? ENTRY_BLOCK_PTR : EXIT_BLOCK_PTR; + FOR_EACH_BB (b) { - if (EDGE_COUNT (b->preds) >= 2) + vec<edge, va_gc> *preds = forward ? b->preds : b->succs; + if (EDGE_COUNT (preds) >= 2) { - FOR_EACH_EDGE (p, ei, b->preds) + FOR_EACH_EDGE (p, ei, preds) { - basic_block runner = p->src; + basic_block runner = forward ? p->src : p->dest; basic_block domsb; - if (runner == ENTRY_BLOCK_PTR) + + if (runner == entrybb) continue; + if (!forward && (runner->flags & BB_NEVER_REACHED)) + { + bitmap_set_bit (&frontiers[runner->index], b->index); + continue; + } - domsb = get_immediate_dominator (CDI_DOMINATORS, b); + domsb = get_immediate_dominator (dir, b); while (runner != domsb) { if (!bitmap_set_bit (&frontiers[runner->index], b->index)) break; - runner = get_immediate_dominator (CDI_DOMINATORS, - runner); + runner = get_immediate_dominator (dir, runner); } } } @@ -1119,11 +1131,21 @@ compute_dominance_frontiers (bitmap_head *frontier { timevar_push (TV_DOM_FRONTIERS); - compute_dominance_frontiers_1 (frontiers); + compute_dominance_frontiers_1 (frontiers, /*forward=*/true); timevar_pop (TV_DOM_FRONTIERS); } +void +compute_control_dependences (bitmap_head *control_deps) +{ + timevar_push (TV_CONTROL_DEPENDENCES); + + compute_dominance_frontiers_1 (control_deps, /*forward=*/false); + + timevar_pop (TV_CONTROL_DEPENDENCES); +} + /* Given a set of blocks with variable definitions (DEF_BLOCKS), return a bitmap with all the blocks in the iterated dominance frontier of the blocks in DEF_BLOCKS. DFS contains dominance