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? Ciao! Steven
* cfg-flags.def (BB_NEVER_REACHED): New flag on basic_block. (BB_SUPERBLOCK): Add FIXME, document that this flag should be removed. * tree-cfgcleanup.c (is_only_builtin_unreachable_block): New function. (mark_builtin_unreachable_blocks): New function. (cleanup_tree_cfg_1): Call mark_builtin_unreachable_blocks at the end to set BB_NEVER_REACHED on basic blocks containing only a call to __builtin_unreachable. * cfgexpand.c (expand_gimple_basic_block): Clear BB_NEVER_REACHED. * dominance.c (calc_idoms): Do not mess with edge_iterator internals. If a basic block has BB_NEVER_REACHED set, and post-dominators are being computed, ignore the block for the computation of the immediate post-dominator of its predecessors. * basic-block.h (compute_control_dependences): New prototype. * cfganal.c (compute_dominance_frontiers_1): Implement dominance frontiers of the reverse CFG, aka control dependence. (compute_dominance_frontiers): Update for above change. (compute_control_dependences): New function. 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