[PATCH] Fix lto bootstrap verification failure with -freorder-blocks-and-partition

[Teresa Johnson]

When testing with -freorder-blocks-and-partition enabled, I hit a
verification failure in an LTO profiledbootstrap. Edge forwarding
performed when we went into cfg layout mode after bb reordering
(during compgotos) created a situation where a hot block was then
dominated by a cold block and was therefore remarked as cold. Because
bb reorder was complete at that point, it was not moved in the
physical layout, and we incorrectly went in and out of the cold
section multiple times.

The following patch addresses that by fixing the layout when we move
blocks to the cold section after bb reordering is complete.

Tested with an LTO profiledbootstrap with
-freorder-blocks-and-partition enabled. Ok for trunk?

Thanks,
Teresa

2013-11-15  Teresa Johnson  <tejohnson@google.com>

        * cfgrtl.c (fixup_partitions): Reorder blocks if necessary.

Index: cfgrtl.c
===================================================================
--- cfgrtl.c    (revision 204792)
+++ cfgrtl.c    (working copy)
@@ -61,6 +61,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "ggc.h"
 #include "tree-pass.h"
 #include "df.h"
+#include "pointer-set.h"

 /* Holds the interesting leading and trailing notes for the function.
    Only applicable if the CFG is in cfglayout mode.  */
@@ -2332,14 +2333,69 @@ fixup_partitions (void)
      forwarding and unreachable block deletion.  */
   vec<basic_block> bbs_to_fix = find_partition_fixes (false);

+  unsigned new_cold_count = bbs_to_fix.length();
+  if (! new_cold_count)
+    return;
+
   /* 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.  */
+  struct pointer_set_t *bbs_moved_to_cold = pointer_set_create ();
   while (! bbs_to_fix.is_empty ())
     {
       bb = bbs_to_fix.pop ();
       fixup_new_cold_bb (bb);
+      pointer_set_insert (bbs_moved_to_cold, bb);
     }
+
+  /* If this happens after bb reordering is done we need to adjust the layout
+     via the next_bb pointers. Otherwise we will incorrectly have multiple
+     switches in and out of the cold section, which is illegal and will be
+     flagged by verify_flow_info. Currently, the compgotos pass goes back into
+     and out of cfglayout mode after bb reordering is complete. When
+     going into cfglayout mode, cfg optimizations may detect opportunities
+     for edge forwarding, which could leave a block in the hot section
+     dominated by a cold block, which will cause the above code to move
+     into to the cold section. By adjusting the next_bb/prev_bb pointers we
+     ensure that fixup_reorder_chain correctly relinks the blocks on exit
+     from cfglayout mode.  */
+  if (crtl->bb_reorder_complete)
+    {
+      /* We should only be doing optimizations that require moving
+         blocks between sections after reordering when we are in cfglayout
+         mode.  */
+      gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
+
+      /* Walk through in layout order, rip out each bb that was moved to
+         the cold section and physically move it to the end of the cold
+         section in layout order. Doing it in this order will guarantee
+         that any fallthrough blocks that were both reassigned to cold stay
+         in the right order.  */
+      unsigned moved_bbs = 0;
+      FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR, next_bb)
+        {
+          if (BB_PARTITION (bb) != BB_COLD_PARTITION)
+            continue;
+
+          /* If this was already a cold bb (it is not in the set
+             bbs_moved_to_cold), then we have hit the original cold
+             section blocks and we are done.  */
+          if (!pointer_set_contains (bbs_moved_to_cold, bb))
+            {
+              /* Make sure we processed all the newly cold bbs.  */
+              gcc_assert (moved_bbs == new_cold_count);
+              break;
+            }
+
+          /* Remove bb from current layout position.  */
+          unlink_block (bb);
+          /* Move bb to the end of the cold section.  */
+          link_block (bb, EXIT_BLOCK_PTR->prev_bb);
+
+          moved_bbs++;
+        }
+    }
+    pointer_set_destroy (bbs_moved_to_cold);
 }

 /* Verify, in the basic block chain, that there is at most one switch

-- 
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413