Sanitize block partitioning under -freorder-blocks-and-partition

Patch 3 of 3 split out from the patch I sent in May that fixes problems with
-freorder-blocks-and-partition, with changes/fixes discussed in that thread.

See http://gcc.gnu.org/ml/gcc-patches/2013-05/threads.html#00388 for context.

This patch sanitizes the partitioning to address issues such as edge
weight insanities that sometimes occur due to upstream optimizations,
and ensures that hot blocks are not dominated by cold blocks. This
needs to be resanitized after certain cfg optimizations that may
cause hot blocks previously reached via both hot and cold paths to
only be reached by cold paths.

The verification code in sanitize_dominator_hotness was contributed by
Steven Bosscher.

Bootstrapped and tested on x86-64-unknown-linux-gnu. Also ensured that
a profiledbootstrap passed with -freorder-blocks-and-partition enabled
(and with the dwarf version changed to 2 to work around PR57451).

Ok for trunk?

(I also included the patch as an attachment since my mailer invariably
messes up the formatting in the pasted version.)

Thanks,
Teresa

2013-08-01  Teresa Johnson  <tejohnson@google.com>
            Steven Bosscher  <steven@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.

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

On 1 August 2013 18:32, Teresa Johnson <tejohnson@google.com> wrote:
> Patch 3 of 3 split out from the patch I sent in May that fixes problems with
> -freorder-blocks-and-partition, with changes/fixes discussed in that thread.
>
> See http://gcc.gnu.org/ml/gcc-patches/2013-05/threads.html#00388 for context.
>
> This patch sanitizes the partitioning to address issues such as edge
> weight insanities that sometimes occur due to upstream optimizations,
> and ensures that hot blocks are not dominated by cold blocks. This
> needs to be resanitized after certain cfg optimizations that may
> cause hot blocks previously reached via both hot and cold paths to
> only be reached by cold paths.
>
> The verification code in sanitize_dominator_hotness was contributed by
> Steven Bosscher.
>
> Bootstrapped and tested on x86-64-unknown-linux-gnu. Also ensured that
> a profiledbootstrap passed with -freorder-blocks-and-partition enabled
> (and with the dwarf version changed to 2 to work around PR57451).
>
> Ok for trunk?
>
> (I also included the patch as an attachment since my mailer invariably
> messes up the formatting in the pasted version.)
>
> Thanks,
> Teresa
>
> 2013-08-01  Teresa Johnson  <tejohnson@google.com>
>             Steven Bosscher  <steven@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);
> +    }
> +}
> +
>  /* 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 +2007,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 +2209,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.  */
> +
> +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;
> +
> +  if (!crtl->has_bb_partition)
> +    return vNULL;

I'd push this early return into the callers instead, at most turn it into a
gcc_checking_assert to be safe.

Both callers, fixup_partitions and rtl_verify_edges, look at
ctrl->has_bb_partition already before calling this, so the above should
be dead already.

Did my mailer somehow swallow the static from find_partition_fixes?

> +
> +  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_bb_partition (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 +2350,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 +2514,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 +2655,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 +2901,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 201281)
> +++ 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 201281)
> +++ 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 201281)
> +++ bb-reorder.c (working copy)
> @@ -1444,6 +1444,55 @@ 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)
> +{
> +  if (!cold_bb_count)
> +    return 0;

Same pattern as above. Callers do not invoke us if !cold_bb_count so the above
check is dead code. Again, remove or checking assert?
> +
> +  bool dom_calculated_here = !dom_info_available_p (dir);
> +
> +  if (dom_calculated_here)
> +    calculate_dominance_info (dir);
> +
> +  /* Keep examining hot bbs until we have either checked them all, or
> +     re-marked all cold bbs as hot.  */
> +  vec<basic_block> hot_bbs_to_check = bbs_in_hot_partition->copy ();
> +  while (! hot_bbs_to_check.is_empty ()
> +         && cold_bb_count)

The comment says "or", which sounds plausible, but the code says "and"?
> +    {
> +      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 then it is ok.  */
> +      if (BB_PARTITION (dom_bb) != BB_COLD_PARTITION)

Why not follow the comment here and == BB_HOT_PARTITION instead, for clarity?

> +        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 +1504,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)
> +    cold_bb_count = sanitize_dominator_hotness (CDI_POST_DOMINATORS,
> +                                                cold_bb_count,
> +                                                &bbs_in_hot_partition);

I take it this last store to cold_bb_count is eliminated anyway.

Thanks,
> +
>    /* 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.  */
>
>
> --
> Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413