[PATCH] proper dataflow block visitation order

["Seongbae Park (박성배, 朴成培)" <seongbae dot park at gmail dot com>]

This is an embarrassing mistake on my part that I only noticed this week,
where we were using wrong block visit orders for dataflow analysis
i.e. for forward problem, reverse postorder is the best known
but we have been using postorder of inverted graph,
and for backward problem, we should have used reverse postorder of
inverted graph
but we've been using postorder (of non-inverted).

Two mistakes (of not reversing the postorder, and using wrong graph direction)
canceled each other somewhat which made this mistake not noticeable
for this long.
The following patch reduces the total number of block visits during
dataflow by about 4%
building cc1 on i686, and it also reduces the block visits for the
testcases in PR34400.

While this is an overall win, there are cases where this patch increases
the number of visits - I'll have to look at them further later,
but clearly this is the right thing to do for now.

Bootstrapped on i686 with c/c++ and no regression.
While this is not exactly a regression,
I'd like to commit this to 4.3 -
as it's a fairly safe change (famous last word :).
On the other hand, this is only a compile time fix
and not a high-impact one at that,
so I don't have very strong opinion on this.

Seongbae


2008-02-08  Seongbae Park <seongbae.park@gmail.com>

        * df-core.c (reverse_array, df_compute_postoder): New functions.
        (rest_of_handle_df_initialize): Refactored
        to call df_compute_postorder.
        (df_analyze): Refactored to call df_compute_postorder.
        Pass proper ordering for forward and backward problems.
        (df_get_postorder): Return the correct block ordering.
        (df_compact_blocks): Call df_compute_postorder.

Index: gcc/df-core.c
===================================================================
--- gcc/df-core.c	(revision 132188)
+++ gcc/df-core.c	(working copy)
@@ -703,6 +703,46 @@ df_finish_pass (bool verify ATTRIBUTE_UN
 }
 
 
+/* Put all elements in the reverse order.  */
+
+static void
+reverse_array (int n, int *array)
+{
+  int i;
+  for (i = 0; i < n / 2; i++)
+    {
+      int temp = array[i];
+      array[i] = array[n - i - 1];
+      array[n - i - 1] = temp;
+    }
+}
+
+
+/* Compute the block visit orders 
+   for forward and backward dataflow problems.  */
+
+static void
+df_compute_postorder (struct df *this_df)
+{
+  if (this_df->postorder)
+    free (this_df->postorder);
+  if (this_df->postorder_inverted)
+    free (this_df->postorder_inverted);
+  this_df->postorder = XNEWVEC (int, last_basic_block);
+  this_df->postorder_inverted = XNEWVEC (int, last_basic_block);
+  this_df->n_blocks 
+    = post_order_compute (this_df->postorder, true, true);
+  this_df->n_blocks_inverted 
+    = inverted_post_order_compute (this_df->postorder_inverted);
+
+  /* These should be the same.  */
+  gcc_assert (this_df->n_blocks == this_df->n_blocks_inverted);
+
+  /* Make them reverse postorder.  */
+  reverse_array (this_df->n_blocks, this_df->postorder);
+  reverse_array (this_df->n_blocks, this_df->postorder_inverted);
+}
+
 /* Set up the dataflow instance for the entire back end.  */
 
 static unsigned int
@@ -726,11 +766,7 @@ rest_of_handle_df_initialize (void)
   if (optimize > 1)
     df_live_add_problem ();
 
-  df->postorder = XNEWVEC (int, last_basic_block);
-  df->postorder_inverted = XNEWVEC (int, last_basic_block);
-  df->n_blocks = post_order_compute (df->postorder, true, true);
-  df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
-  gcc_assert (df->n_blocks == df->n_blocks_inverted);
+  df_compute_postorder (df);
 
   df->hard_regs_live_count = XNEWVEC (unsigned int, FIRST_PSEUDO_REGISTER);
   memset (df->hard_regs_live_count, 0, 
@@ -1184,6 +1220,8 @@ df_analyze_problem (struct dataflow *dfl
 }
 
 
+
+
 /* Analyze dataflow info for the basic blocks specified by the bitmap
    BLOCKS, or for the whole CFG if BLOCKS is zero.  */
 
@@ -1194,17 +1232,7 @@ df_analyze (void)
   bool everything;
   int i;
   
-  if (df->postorder)
-    free (df->postorder);
-  if (df->postorder_inverted)
-    free (df->postorder_inverted);
-  df->postorder = XNEWVEC (int, last_basic_block);
-  df->postorder_inverted = XNEWVEC (int, last_basic_block);
-  df->n_blocks = post_order_compute (df->postorder, true, true);
-  df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
-
-  /* These should be the same.  */
-  gcc_assert (df->n_blocks == df->n_blocks_inverted);
+  df_compute_postorder (df);
 
   /* We need to do this before the df_verify_all because this is
      not kept incrementally up to date.  */
@@ -1258,12 +1286,12 @@ df_analyze (void)
           if (dflow->problem->dir == DF_FORWARD)
             df_analyze_problem (dflow,
                                 df->blocks_to_analyze,
-                                df->postorder_inverted,
+                                df->postorder,
                                 df->n_blocks_inverted);
           else
             df_analyze_problem (dflow,
                                 df->blocks_to_analyze,
-                                df->postorder,
+                                df->postorder_inverted,
                                 df->n_blocks);
         }
     }
@@ -1305,15 +1333,13 @@ df_get_n_blocks (enum df_flow_dir dir)
 int *
 df_get_postorder (enum df_flow_dir dir)
 {
-  gcc_assert (dir != DF_NONE);
-
   if (dir == DF_FORWARD)
     {
-      gcc_assert (df->postorder_inverted);
-      return df->postorder_inverted;
+      gcc_assert (df->postorder);
+      return df->postorder;
     }
-  gcc_assert (df->postorder);
-  return df->postorder;
+  gcc_assert (df->postorder_inverted);
+  return df->postorder_inverted;
 }
 
 static struct df_problem user_problem; 
@@ -1539,6 +1565,9 @@ df_compact_blocks (void)
   for (; i < last_basic_block; i++)
     SET_BASIC_BLOCK (i, NULL);
 
+  /* Recompute the block visit order. */
+  df_compute_postorder (df);
+
 #ifdef DF_DEBUG_CFG
   if (!df_lr->solutions_dirty)
     df_set_clean_cfg ();