On Fri, Aug 2, 2013 at 9:48 PM, Teresa Johnson <tejohn...@google.com> wrote: > On Fri, Aug 2, 2013 at 8:05 AM, Jan Hubicka <hubi...@ucw.cz> wrote: >>> >>> 2013-08-01 Teresa Johnson <tejohn...@google.com> >>> Steven Bosscher <ste...@gcc.gnu.org> >>> >>> * cfgrtl.c (fixup_bb_partition): New routine. >>> (commit_edge_insertions): Invoke fixup_partitions. >>> (find_partition_fixes): New routine. >>> (fixup_partitions): Ditto. >>> (verify_hot_cold_block_grouping): Update comments. >>> (rtl_verify_edges): Invoke find_partition_fixes. >>> (rtl_verify_bb_pointers): Update comments. >>> (rtl_verify_bb_layout): Ditto. >>> * basic-block.h (fixup_partitions): Declare. >>> * cfgcleanup.c (try_optimize_cfg): Invoke fixup_partitions. >>> * bb-reorder.c (sanitize_dominator_hotness): New function. >>> (find_rarely_executed_basic_blocks_and_crossing_edges): Invoke >>> sanitize_dominator_hotness. >>> >>> Index: cfgrtl.c >>> =================================================================== >>> --- cfgrtl.c (revision 201281) >>> +++ cfgrtl.c (working copy) >>> @@ -1341,6 +1341,34 @@ fixup_partition_crossing (edge e) >>> } >>> } >>> >>> +/* Called when block BB has been reassigned to a different partition, >>> + to ensure that the region crossing attributes are updated. */ >>> + >>> +static void >>> +fixup_bb_partition (basic_block bb) >>> +{ >>> + edge e; >>> + edge_iterator ei; >>> + >>> + /* Now need to make bb's pred edges non-region crossing. */ >>> + FOR_EACH_EDGE (e, ei, bb->preds) >>> + { >>> + fixup_partition_crossing (e); >>> + } >>> + >>> + /* Possibly need to make bb's successor edges region crossing, >>> + or remove stale region crossing. */ >>> + FOR_EACH_EDGE (e, ei, bb->succs) >>> + { >>> + if ((e->flags & EDGE_FALLTHRU) >>> + && BB_PARTITION (bb) != BB_PARTITION (e->dest) >>> + && e->dest != EXIT_BLOCK_PTR) >>> + force_nonfallthru (e); >>> + else >>> + fixup_partition_crossing (e); >>> + } >>> +} >> >> Is there particular reason why preds can not be fallhtrus and why >> force_nonfallthru edge does not need partition crossing fixup? >> (if so, perhpas it could be mentioned in the description, if not, >> I think force_nonfallthru path has to check if new BB was introduced >> and do the right thing on the edge. > > I need to clarify the comments in this routine, because without the > context of how this is called it isn't clear. This routine is only > called when we detect a hot bb that is now dominated by a cold bb and > needs to become cold. Therefore, its preds will no longer be region > crossing (any non-dominating blocks that were previously hot would > have been marked cold in the caller for the same reason, so we will > not end up adjusting the region crossing-ness or fallthrough-ness of > those pred edges). Any that were region crossing before but aren't any > longer could not have been fall through (as Steven noted, you can't > have a fall through across a partition boundary). I will add some > better comments here. > > Regarding the call to force_nonfallthru, that routine calls > fixup_partition_crossing as needed, and I will update the comment to > reflect that too.
Patch with updated comments below. Ok for trunk? Thanks, Teresa 2013-08-05 Teresa Johnson <tejohn...@google.com> Steven Bosscher <ste...@gcc.gnu.org> * cfgrtl.c (fixup_bb_partition): New routine. (commit_edge_insertions): Invoke fixup_partitions. (find_partition_fixes): New routine. (fixup_partitions): Ditto. (verify_hot_cold_block_grouping): Update comments. (rtl_verify_edges): Invoke find_partition_fixes. (rtl_verify_bb_pointers): Update comments. (rtl_verify_bb_layout): Ditto. * basic-block.h (fixup_partitions): Declare. * cfgcleanup.c (try_optimize_cfg): Invoke fixup_partitions. * bb-reorder.c (sanitize_dominator_hotness): New function. (find_rarely_executed_basic_blocks_and_crossing_edges): Invoke sanitize_dominator_hotness. Index: cfgrtl.c =================================================================== --- cfgrtl.c (revision 201461) +++ cfgrtl.c (working copy) @@ -1341,6 +1341,43 @@ fixup_partition_crossing (edge e) } } +/* Called when block BB has been reassigned to the cold partition, + because it is now dominated by another cold block, + to ensure that the region crossing attributes are updated. */ + +static void +fixup_new_cold_bb (basic_block bb) +{ + edge e; + edge_iterator ei; + + /* This is called when a hot bb is found to now be dominated + by a cold bb and therefore needs to become cold. Therefore, + its preds will no longer be region crossing. Any non-dominating + preds that were previously hot would also have become cold + in the caller for the same region. Any preds that were previously + region-crossing will be adjusted in fixup_partition_crossing. */ + FOR_EACH_EDGE (e, ei, bb->preds) + { + fixup_partition_crossing (e); + } + + /* Possibly need to make bb's successor edges region crossing, + or remove stale region crossing. */ + FOR_EACH_EDGE (e, ei, bb->succs) + { + /* We can't have fall-through edges across partition boundaries. + Note that force_nonfallthru will do any necessary partition + boundary fixup by calling fixup_partition_crossing itself. */ + if ((e->flags & EDGE_FALLTHRU) + && BB_PARTITION (bb) != BB_PARTITION (e->dest) + && e->dest != EXIT_BLOCK_PTR) + force_nonfallthru (e); + else + fixup_partition_crossing (e); + } +} + /* Attempt to change code to redirect edge E to TARGET. Don't do that on expense of adding new instructions or reordering basic blocks. @@ -1979,6 +2016,14 @@ commit_edge_insertions (void) { basic_block bb; + /* Optimization passes that invoke this routine can cause hot blocks + previously reached by both hot and cold blocks to become dominated only + by cold blocks. This will cause the verification below to fail, + and lead to now cold code in the hot section. In some cases this + may only be visible after newly unreachable blocks are deleted, + which will be done by fixup_partitions. */ + fixup_partitions (); + #ifdef ENABLE_CHECKING verify_flow_info (); #endif @@ -2173,6 +2218,101 @@ get_last_bb_insn (basic_block bb) return end; } +/* Sanity check partition hotness to ensure that basic blocks in + the cold partition don't dominate basic blocks in the hot partition. + If FLAG_ONLY is true, report violations as errors. Otherwise + re-mark the dominated blocks as cold, since this is run after + cfg optimizations that may make hot blocks previously reached + by both hot and cold blocks now only reachable along cold paths. */ + +static vec<basic_block> +find_partition_fixes (bool flag_only) +{ + basic_block bb; + vec<basic_block> bbs_in_cold_partition = vNULL; + vec<basic_block> bbs_to_fix = vNULL; + + /* Callers check this. */ + gcc_checking_assert (crtl->has_bb_partition); + + FOR_EACH_BB (bb) + if ((BB_PARTITION (bb) == BB_COLD_PARTITION)) + bbs_in_cold_partition.safe_push (bb); + + if (bbs_in_cold_partition.is_empty ()) + return vNULL; + + bool dom_calculated_here = !dom_info_available_p (CDI_DOMINATORS); + + if (dom_calculated_here) + calculate_dominance_info (CDI_DOMINATORS); + + while (! bbs_in_cold_partition.is_empty ()) + { + bb = bbs_in_cold_partition.pop (); + /* Any blocks dominated by a block in the cold section + must also be cold. */ + basic_block son; + for (son = first_dom_son (CDI_DOMINATORS, bb); + son; + son = next_dom_son (CDI_DOMINATORS, son)) + { + /* If son is not yet cold, then mark it cold here and + enqueue it for further processing. */ + if ((BB_PARTITION (son) != BB_COLD_PARTITION)) + { + if (flag_only) + error ("non-cold basic block %d dominated " + "by a block in the cold partition", son->index); + else + BB_SET_PARTITION (son, BB_COLD_PARTITION); + bbs_to_fix.safe_push (son); + bbs_in_cold_partition.safe_push (son); + } + } + } + + if (dom_calculated_here) + free_dominance_info (CDI_DOMINATORS); + + return bbs_to_fix; +} + +/* Perform cleanup on the hot/cold bb partitioning after optimization + passes that modify the cfg. */ + +void +fixup_partitions (void) +{ + basic_block bb; + + if (!crtl->has_bb_partition) + return; + + /* Delete any blocks that became unreachable and weren't + already cleaned up, for example during edge forwarding + and convert_jumps_to_returns. This will expose more + opportunities for fixing the partition boundaries here. + Also, the calculation of the dominance graph during verification + will assert if there are unreachable nodes. */ + delete_unreachable_blocks (); + + /* If there are partitions, do a sanity check on them: A basic block in + a cold partition cannot dominate a basic block in a hot partition. + Fixup any that now violate this requirement, as a result of edge + forwarding and unreachable block deletion. */ + vec<basic_block> bbs_to_fix = find_partition_fixes (false); + + /* Do the partition fixup after all necessary blocks have been converted to + cold, so that we only update the region crossings the minimum number of + places, which can require forcing edges to be non fallthru. */ + while (! bbs_to_fix.is_empty ()) + { + bb = bbs_to_fix.pop (); + fixup_new_cold_bb (bb); + } +} + /* Verify, in the basic block chain, that there is at most one switch between hot/cold partitions. This condition will not be true until after reorder_basic_blocks is called. */ @@ -2219,7 +2359,8 @@ verify_hot_cold_block_grouping (void) /* Perform several checks on the edges out of each block, such as the consistency of the branch probabilities, the correctness of hot/cold partition crossing edges, and the number of expected - successor edges. */ + successor edges. Also verify that the dominance relationship + between hot/cold blocks is sane. */ static int rtl_verify_edges (void) @@ -2382,6 +2523,14 @@ rtl_verify_edges (void) } } + /* If there are partitions, do a sanity check on them: A basic block in + a cold partition cannot dominate a basic block in a hot partition. */ + if (crtl->has_bb_partition && !err) + { + vec<basic_block> bbs_to_fix = find_partition_fixes (true); + err = !bbs_to_fix.is_empty (); + } + /* Clean up. */ return err; } @@ -2515,7 +2664,7 @@ rtl_verify_bb_pointers (void) and NOTE_INSN_BASIC_BLOCK - verify that no fall_thru edge crosses hot/cold partition boundaries - verify that there are no pending RTL branch predictions - - verify that there is a single hot/cold partition boundary after bbro + - verify that hot blocks are not dominated by cold blocks In future it can be extended check a lot of other stuff as well (reachability of basic blocks, life information, etc. etc.). */ @@ -2761,7 +2910,8 @@ rtl_verify_bb_layout (void) - check that all insns are in the basic blocks (except the switch handling code, barriers and notes) - check that all returns are followed by barriers - - check that all fallthru edge points to the adjacent blocks. */ + - check that all fallthru edge points to the adjacent blocks + - verify that there is a single hot/cold partition boundary after bbro */ static int rtl_verify_flow_info (void) Index: basic-block.h =================================================================== --- basic-block.h (revision 201461) +++ basic-block.h (working copy) @@ -797,6 +797,7 @@ extern bool contains_no_active_insn_p (const_basic extern bool forwarder_block_p (const_basic_block); extern bool can_fallthru (basic_block, basic_block); extern void emit_barrier_after_bb (basic_block bb); +extern void fixup_partitions (void); /* In cfgbuild.c. */ extern void find_many_sub_basic_blocks (sbitmap); Index: cfgcleanup.c =================================================================== --- cfgcleanup.c (revision 201461) +++ cfgcleanup.c (working copy) @@ -2807,10 +2807,21 @@ try_optimize_cfg (int mode) df_analyze (); } + if (changed) + { + /* Edge forwarding in particular can cause hot blocks previously + reached by both hot and cold blocks to become dominated only + by cold blocks. This will cause the verification below to fail, + and lead to now cold code in the hot section. This is not easy + to detect and fix during edge forwarding, and in some cases + is only visible after newly unreachable blocks are deleted, + which will be done in fixup_partitions. */ + fixup_partitions (); + #ifdef ENABLE_CHECKING - if (changed) - verify_flow_info (); + verify_flow_info (); #endif + } changed_overall |= changed; first_pass = false; Index: bb-reorder.c =================================================================== --- bb-reorder.c (revision 201461) +++ bb-reorder.c (working copy) @@ -1444,6 +1444,57 @@ fix_up_crossing_landing_pad (eh_landing_pad old_lp ei_next (&ei); } + +/* Ensure that no cold bbs dominate hot bbs along the dominance or + post-dominance DIR, for example as a result of edge weight insanities. + Returns the updated value of COLD_BB_COUNT and adds newly-hot bbs + to BBS_IN_HOT_PARTITION. */ + +static unsigned int +sanitize_dominator_hotness (enum cdi_direction dir, unsigned int cold_bb_count, + vec<basic_block> *bbs_in_hot_partition) +{ + /* Callers check this. */ + gcc_checking_assert (cold_bb_count); + + bool dom_calculated_here = !dom_info_available_p (dir); + + if (dom_calculated_here) + calculate_dominance_info (dir); + + /* Keep examining hot bbs while we still have some left to check + and there are remaining cold bbs. */ + vec<basic_block> hot_bbs_to_check = bbs_in_hot_partition->copy (); + while (! hot_bbs_to_check.is_empty () + && cold_bb_count) + { + basic_block bb = hot_bbs_to_check.pop (); + basic_block dom_bb = get_immediate_dominator (dir, bb); + + /* If bb's immediate dominator is also hot (or unpartitioned, + e.g. the entry block) then it is ok. If it is cold, it + needs to be adjusted. */ + if (BB_PARTITION (dom_bb) != BB_COLD_PARTITION) + continue; + + /* We have a hot bb with an immediate dominator that is cold. + The dominator needs to be re-marked hot. */ + BB_SET_PARTITION (dom_bb, BB_HOT_PARTITION); + cold_bb_count--; + + /* Now we need to examine newly-hot dom_bb to see if it is also + dominated by a cold bb. */ + bbs_in_hot_partition->safe_push (dom_bb); + hot_bbs_to_check.safe_push (dom_bb); + } + + if (dom_calculated_here) + free_dominance_info (dir); + + return cold_bb_count; +} + + /* Find the basic blocks that are rarely executed and need to be moved to a separate section of the .o file (to cut down on paging and improve cache locality). Return a vector of all edges that cross. */ @@ -1455,16 +1506,42 @@ find_rarely_executed_basic_blocks_and_crossing_edg basic_block bb; edge e; edge_iterator ei; + unsigned int cold_bb_count = 0; + vec<basic_block> bbs_in_hot_partition = vNULL; /* Mark which partition (hot/cold) each basic block belongs in. */ FOR_EACH_BB (bb) { if (probably_never_executed_bb_p (cfun, bb)) - BB_SET_PARTITION (bb, BB_COLD_PARTITION); + { + BB_SET_PARTITION (bb, BB_COLD_PARTITION); + cold_bb_count++; + } else - BB_SET_PARTITION (bb, BB_HOT_PARTITION); + { + BB_SET_PARTITION (bb, BB_HOT_PARTITION); + bbs_in_hot_partition.safe_push (bb); + } } + /* Ensure that no cold bbs dominate hot bbs. This could happen as a result of + several different possibilities. One is that there are edge weight insanities + due to optimization phases that do not properly update basic block profile + counts. The second is that the entry of the function may not be hot, because + it is entered fewer times than the number of profile training runs, but there + is a loop inside the function that causes blocks within the function to be + above the threshold for hotness. Then do the same along the post-dominator + tree (which could have additional changes required after fixing up + dominators). */ + if (cold_bb_count) + cold_bb_count = sanitize_dominator_hotness (CDI_DOMINATORS, + cold_bb_count, + &bbs_in_hot_partition); + if (cold_bb_count) + sanitize_dominator_hotness (CDI_POST_DOMINATORS, + cold_bb_count, + &bbs_in_hot_partition); + /* The format of .gcc_except_table does not allow landing pads to be in a different partition as the throw. Fix this by either moving or duplicating the landing pads. */ > >> >>> +/* Sanity check partition hotness to ensure that basic blocks in >>> + the cold partition don't dominate basic blocks in the hot partition. >>> + If FLAG_ONLY is true, report violations as errors. Otherwise >>> + re-mark the dominated blocks as cold, since this is run after >>> + cfg optimizations that may make hot blocks previously reached >>> + by both hot and cold blocks now only reachable along cold paths. */ >> >> With profile, I suppose we can have cold blocks dominating hot blocks when >> the >> hot blocks is in loop whose trip count is high enough. Indeed for >> partitioning >> reasons it does not make sense to push those into different section. >> >> I also wonder, if we finally get the pass stable, can we enable it by default >> and offline probably cold blocks w/o profile? Primarily blocks reachable only >> by EH + blocks leading to a crash or throw(). For C++ those should be common >> enough to make a difference... > > Yep, as soon as PR57451 is fixed, which I hope to get to next week, > then I am going to send a patch to turn this on by default, at least > with profile feedback, which is where I've been doing performance > tuning. But you are right that there are some cases where it should be > beneficial without profile data as well. > > Thanks, > Teresa > >> >> Honza > > > > -- > Teresa Johnson | Software Engineer | tejohn...@google.com | 408-460-2413 -- Teresa Johnson | Software Engineer | tejohn...@google.com | 408-460-2413