OSDN Git Service

PR rtl-optimization/36365
authorsteven <steven@138bc75d-0d04-0410-961f-82ee72b054a4>
Sat, 6 Dec 2008 22:52:43 +0000 (22:52 +0000)
committersteven <steven@138bc75d-0d04-0410-961f-82ee72b054a4>
Sat, 6 Dec 2008 22:52:43 +0000 (22:52 +0000)
* df-core.c (df_worklist_dataflow_overeager): Remove.
(df_worklist_dataflow): Don't call it, use double-queue only.
* params.def (PARAM_DF_DOUBLE_QUQUQ_THRESHOLD_FACTOR): Remove.

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

gcc/ChangeLog
gcc/df-core.c
gcc/params.def

index 2f6ea17..0c889a1 100644 (file)
@@ -1,3 +1,10 @@
+2008-12-06  Steven Bosscher  <steven@gcc.gnu.org>
+
+       PR rtl-optimization/36365
+       * df-core.c (df_worklist_dataflow_overeager): Remove.
+       (df_worklist_dataflow): Don't call it, use double-queue only.
+       * params.def (PARAM_DF_DOUBLE_QUQUQ_THRESHOLD_FACTOR): Remove.
+
 2008-12-06  Jakub Jelinek  <jakub@redhat.com>
 
        PR middle-end/38428
index 1ad7ab1..7b83dce 100644 (file)
@@ -943,47 +943,6 @@ 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,
@@ -1042,23 +1001,10 @@ df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
 
 /* 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
-   changes on demand. This algorithm may visit blocks more than
-   iterative method if there are deeply nested loops. 
-   Worklist algorithm works better than iterative algorithm
-   for CFGs with no nested loops.
-   In practice, the measurement shows worklist algorithm beats 
-   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. 
-   
-   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.
-   */
+   The solver is a double-queue algorithm similar to the "double stack" solver
+   from Cooper, Harvey and Kennedy, "Iterative data-flow analysis, Revisited".
+   The only significant difference is that the worklist in this implementation
+   is always sorted in RPO of the CFG visiting direction.  */
 
 void 
 df_worklist_dataflow (struct dataflow *dataflow,
@@ -1103,26 +1049,10 @@ df_worklist_dataflow (struct dataflow *dataflow,
   if (dataflow->problem->init_fun)
     dataflow->problem->init_fun (blocks_to_consider);
 
-  /* 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)
-    {
-      /* 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);
-    }
+  /* Solve it.  */
+  df_worklist_dataflow_doublequeue (dataflow, pending, considered,
+                                   blocks_in_postorder,
+                                   bbindex_to_postorder);
 
   sbitmap_free (considered);
   free (bbindex_to_postorder);
index 50a7133..ea3015b 100644 (file)
@@ -745,12 +745,6 @@ DEFPARAM (PARAM_SCCVN_MAX_SCC_SIZE,
          "Maximum size of a SCC before SCCVN stops processing a function",
          10000, 10, 0)
 
-
-DEFPARAM (PARAM_DF_DOUBLE_QUEUE_THRESHOLD_FACTOR,
-         "df-double-queue-threshold-factor",
-         "Multiplier used for determining the double-queueing threshold",
-         2, 0, 0)
-
 DEFPARAM (PARAM_IRA_MAX_LOOPS_NUM,
          "ira-max-loops-num",
          "max loops number for regional RA",