2008-01-17 Seongbae Park <seongbae.park@gmail.com>

	PR rtl-optimization/34400
	* df-core.c (df_worklist_dataflow_overeager,
	df_worklist_dataflow_doublequeue): New functions.
	(df_worklist_dataflow): Two different worklist solvers.
	* params.def (PARAM_DF_DOUBLE_QUEUE_THRESHOLD_FACTOR):
	New param.



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@131608 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 127 insertions, 18 deletions

diff --git a/gcc/df-core.c b/gcc/df-core.c
index 9692dbbb7dc..5404000ef39 100644
--- a/gcc/df-core.c
+++ b/gcc/df-core.c
@@ -399,6 +399,7 @@ are write-only operations.
 #include "timevar.h"
 #include "df.h"
 #include "tree-pass.h"
+#include "params.h"
 
 static void *df_get_bb_info (struct dataflow *, unsigned int);
 static void df_set_bb_info (struct dataflow *, unsigned int, void *);
@@ -931,6 +932,105 @@ df_worklist_propagate_backward (struct dataflow *dataflow,
 }
 
 
+
+/* This will free "pending". */
+static void 
+df_worklist_dataflow_overeager (struct dataflow *dataflow,
+				bitmap pending,
+                                sbitmap considered,
+                                int *blocks_in_postorder,
+				unsigned *bbindex_to_postorder)
+{
+  enum df_flow_dir dir = dataflow->problem->dir;
+  int count = 0;
+
+  while (!bitmap_empty_p (pending))
+    {
+      unsigned bb_index;
+      int index;
+      count++;
+
+      index = bitmap_first_set_bit (pending);
+      bitmap_clear_bit (pending, index);
+
+      bb_index = blocks_in_postorder[index];
+
+      if (dir == DF_FORWARD)
+	df_worklist_propagate_forward (dataflow, bb_index,
+				       bbindex_to_postorder,
+				       pending, considered);
+      else 
+	df_worklist_propagate_backward (dataflow, bb_index,
+					bbindex_to_postorder,
+					pending, considered);
+    }
+
+  BITMAP_FREE (pending);
+
+  /* Dump statistics. */
+  if (dump_file)
+    fprintf (dump_file, "df_worklist_dataflow_overeager:"
+	     "n_basic_blocks %d n_edges %d"
+	     " count %d (%5.2g)\n",
+	     n_basic_blocks, n_edges,
+	     count, count / (float)n_basic_blocks);
+}
+
+static void 
+df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
+			  	  bitmap pending,
+                                  sbitmap considered,
+                                  int *blocks_in_postorder,
+				  unsigned *bbindex_to_postorder)
+{
+  enum df_flow_dir dir = dataflow->problem->dir;
+  int dcount = 0;
+  bitmap worklist = BITMAP_ALLOC (&df_bitmap_obstack);
+
+  /* Double-queueing. Worklist is for the current iteration,
+     and pending is for the next. */
+  while (!bitmap_empty_p (pending))
+    {
+      /* Swap pending and worklist. */
+      bitmap temp = worklist;
+      worklist = pending;
+      pending = temp;
+
+      do
+	{
+	  int index;
+	  unsigned bb_index;
+	  dcount++;
+
+	  index = bitmap_first_set_bit (worklist);
+	  bitmap_clear_bit (worklist, index);
+
+	  bb_index = blocks_in_postorder[index];
+
+	  if (dir == DF_FORWARD)
+	    df_worklist_propagate_forward (dataflow, bb_index,
+					   bbindex_to_postorder,
+					   pending, considered);
+	  else 
+	    df_worklist_propagate_backward (dataflow, bb_index,
+					    bbindex_to_postorder,
+					    pending, considered);
+	}
+      while (!bitmap_empty_p (worklist));
+    }
+
+  BITMAP_FREE (worklist);
+  BITMAP_FREE (pending);
+
+  /* Dump statistics. */
+  if (dump_file)
+    fprintf (dump_file, "df_worklist_dataflow_doublequeue:"
+	     "n_basic_blocks %d n_edges %d"
+	     " count %d (%5.2g)\n",
+	     n_basic_blocks, n_edges,
+	     dcount, dcount / (float)n_basic_blocks);
+}
+
 /* Worklist-based dataflow solver. It uses sbitmap as a worklist,
    with "n"-th bit representing the n-th block in the reverse-postorder order. 
    This is so-called over-eager algorithm where it propagates
@@ -942,7 +1042,14 @@ df_worklist_propagate_backward (struct dataflow *dataflow,
    iterative algorithm by some margin overall.  
    Note that this is slightly different from the traditional textbook worklist solver,
    in that the worklist is effectively sorted by the reverse postorder.
-   For CFGs with no nested loops, this is optimal.  */
+   For CFGs with no nested loops, this is optimal. 
+   
+   The overeager algorithm while works well for typical inputs,
+   it could degenerate into excessive iterations given CFGs with high loop nests
+   and unstructured loops. To cap the excessive iteration on such case,
+   we switch to double-queueing when the original algorithm seems to 
+   get into such.
+   */
 
 void 
 df_worklist_dataflow (struct dataflow *dataflow,
@@ -983,29 +1090,31 @@ df_worklist_dataflow (struct dataflow *dataflow,
       bitmap_set_bit (pending, i);
     }
 
+  /* Initialize the problem. */
   if (dataflow->problem->init_fun)
     dataflow->problem->init_fun (blocks_to_consider);
 
-  while (!bitmap_empty_p (pending))
+  /* Solve it. Determine the solving algorithm
+     based on a simple heuristic. */
+  if (n_edges > PARAM_VALUE (PARAM_DF_DOUBLE_QUEUE_THRESHOLD_FACTOR)
+      * n_basic_blocks)
     {
-      unsigned bb_index;
-
-      index = bitmap_first_set_bit (pending);
-      bitmap_clear_bit (pending, index);
-
-      bb_index = blocks_in_postorder[index];
-
-      if (dir == DF_FORWARD)
-        df_worklist_propagate_forward (dataflow, bb_index,
-                                       bbindex_to_postorder,
-                                       pending, considered);
-      else 
-        df_worklist_propagate_backward (dataflow, bb_index,
-                                        bbindex_to_postorder,
-                                        pending, considered);
+      /* High average connectivity, meaning dense graph
+         with more likely deep nested loops
+	 or unstructured loops. */
+      df_worklist_dataflow_doublequeue (dataflow, pending, considered,
+					blocks_in_postorder,
+					bbindex_to_postorder);
+    }
+  else 
+    {
+      /* Most inputs fall into this case
+        with relatively flat or structured CFG. */
+      df_worklist_dataflow_overeager (dataflow, pending, considered,
+				      blocks_in_postorder,
+				      bbindex_to_postorder);
     }
 
-  BITMAP_FREE (pending);
   sbitmap_free (considered);
   free (bbindex_to_postorder);
 }