[PATCH] More DF worklist solver improvements

[PATCH] More DF worklist solver improvements

[Richard Biener]

The following switches the double-queue iteration solver with a
single-queue one that prioritizes backward data flow solving
over forward progress.  That is, it first converges on earlier
cycles before propagating the (possibly again chainging) data
to the following blocks.  This improves data locality and
possibly avoids visiting later blocks multiple times but it
might also cause inner cycles to be iterated multiple times,
so it's possibly not always an improvement.  With the
rev_post_order_and_mark_dfs_back_seme API it would be possible
to iterate only outermost cycles immediately, like we do for
var-tracking.

For the PR26854 all.i testcase it halves DF RD processing time
again (ontop of the previous improvement).

I wanted to show off the potential but will not push this
now but instead will see to find the cycles to do it the
var-tracking style.

	* df-core.cc (df_worklist_propagate_forward): Always
	add to worklist.
	(df_worklist_propagate_backward): Likewise.
	(df_worklist_dataflow_doublequeue): Change to a single
	queue worklist implementation.
---
 gcc/df-core.cc | 49 ++++++++++++++-----------------------------------
 1 file changed, 14 insertions(+), 35 deletions(-)

diff --git a/gcc/df-core.cc b/gcc/df-core.cc
index 38f69ac5743..30c1bfcc314 100644
--- a/gcc/df-core.cc
+++ b/gcc/df-core.cc
@@ -874,8 +874,7 @@ make_pass_df_finish (gcc::context *ctxt)
 /* Helper function for df_worklist_dataflow.
    Propagate the dataflow forward.
    Given a BB_INDEX, do the dataflow propagation
-   and set bits on for successors in PENDING for earlier
-   and WORKLIST for later in bbindex_to_postorder
+   and set bits on WORKLIST for successors
    if the out set of the dataflow has changed.
 
    AGE specify time when BB was visited last time.
@@ -894,7 +893,6 @@ df_worklist_propagate_forward (struct dataflow *dataflow,
 			       unsigned bb_index,
 			       unsigned *bbindex_to_postorder,
 			       bitmap worklist,
-			       bitmap pending,
 			       sbitmap considered,
 			       vec<int> &last_change_age,
 			       int age)
@@ -926,13 +924,7 @@ df_worklist_propagate_forward (struct dataflow *dataflow,
           unsigned ob_index = e->dest->index;
 
           if (bitmap_bit_p (considered, ob_index))
-	    {
-	      if (bbindex_to_postorder[bb_index]
-		  < bbindex_to_postorder[ob_index])
-		bitmap_set_bit (worklist, bbindex_to_postorder[ob_index]);
-	      else
-		bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
-	    }
+	    bitmap_set_bit (worklist, bbindex_to_postorder[ob_index]);
         }
       return true;
     }
@@ -948,7 +940,6 @@ df_worklist_propagate_backward (struct dataflow *dataflow,
 				unsigned bb_index,
 				unsigned *bbindex_to_postorder,
 				bitmap worklist,
-				bitmap pending,
 				sbitmap considered,
 				vec<int> &last_change_age,
 				int age)
@@ -980,13 +971,7 @@ df_worklist_propagate_backward (struct dataflow *dataflow,
           unsigned ob_index = e->src->index;
 
           if (bitmap_bit_p (considered, ob_index))
-	    {
-	      if (bbindex_to_postorder[bb_index]
-		  < bbindex_to_postorder[ob_index])
-		bitmap_set_bit (worklist, bbindex_to_postorder[ob_index]);
-	      else
-		bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
-	    }
+	    bitmap_set_bit (worklist, bbindex_to_postorder[ob_index]);
         }
       return true;
     }
@@ -995,17 +980,17 @@ df_worklist_propagate_backward (struct dataflow *dataflow,
 
 /* Main dataflow solver loop.
 
-   DATAFLOW is problem we are solving, PENDING is worklist of basic blocks we
+   DATAFLOW is problem we are solving, WORKLIST is worklist of basic blocks we
    need to visit.
    BLOCK_IN_POSTORDER is array of size N_BLOCKS specifying postorder in BBs and
    BBINDEX_TO_POSTORDER is array mapping back BB->index to postorder position.
-   PENDING will be freed.
+   WORKLIST will be freed.
 
    The worklists are bitmaps indexed by postorder positions.  
 
-   The function implements standard algorithm for dataflow solving with two
-   worklists (we are processing WORKLIST and storing new BBs to visit in
-   PENDING).
+   The function implements standard algorithm for dataflow solving
+   (we are processing WORKLIST, storing new BBs to the same list
+   to visit dataflow changes across backedges first).
 
    As an optimization we maintain ages when BB was changed (stored in
    last_change_age) and when it was last visited (stored in last_visit_age).
@@ -1014,15 +999,14 @@ df_worklist_propagate_backward (struct dataflow *dataflow,
 
 static void
 df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
-			  	  bitmap pending,
-                                  sbitmap considered,
-                                  int *blocks_in_postorder,
+				  bitmap worklist,
+				  sbitmap considered,
+				  int *blocks_in_postorder,
 				  unsigned *bbindex_to_postorder,
 				  int n_blocks)
 {
   enum df_flow_dir dir = dataflow->problem->dir;
   int dcount = 0;
-  bitmap worklist = BITMAP_ALLOC (&df_bitmap_obstack);
   int age = 0;
   bool changed;
   vec<int> last_visit_age = vNULL;
@@ -1032,12 +1016,8 @@ df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
   last_visit_age.safe_grow_cleared (n_blocks, true);
   last_change_age.safe_grow_cleared (n_blocks, true);
 
-  /* Double-queueing. Worklist is for the current iteration,
-     and pending is for the next. */
-  while (!bitmap_empty_p (pending))
+  if (!bitmap_empty_p (worklist))
     {
-      std::swap (pending, worklist);
-
       do
 	{
 	  unsigned index = bitmap_first_set_bit (worklist);
@@ -1051,14 +1031,14 @@ df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
 	  if (dir == DF_FORWARD)
 	    changed = df_worklist_propagate_forward (dataflow, bb_index,
 						     bbindex_to_postorder,
-						     worklist, pending,
+						     worklist,
 						     considered,
 						     last_change_age,
 						     prev_age);
 	  else
 	    changed = df_worklist_propagate_backward (dataflow, bb_index,
 						      bbindex_to_postorder,
-						      worklist, pending,
+						      worklist,
 						      considered,
 						      last_change_age,
 						      prev_age);
@@ -1070,7 +1050,6 @@ df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
     }
 
   BITMAP_FREE (worklist);
-  BITMAP_FREE (pending);
   last_visit_age.release ();
   last_change_age.release ();
 
-- 
2.35.3