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 *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