2001-11-25 Daniel Berlin <dan@cgsoftware.com>

	* df.c: Add prototypes for hybrid_search_bitmap and
	hybrid_search_sbitmap.
	(hybrid_search_bitmap): New function.
	(hybrid_search_sbitmap): New function.
	(iterative_dataflow_sbitmap): Change to use hybrid_search_sbitmap.
	(iterative_dataflow_bitmap): Ditto.


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

1 files changed, 254 insertions, 160 deletions

diff --git a/gcc/df.c b/gcc/df.c
index 9bd0ad2dc1e..9cb0230b27c 100644
--- a/gcc/df.c
+++ b/gcc/df.c
@@ -301,6 +301,16 @@ static void df_ru_transfer_function PARAMS ((int, int *, bitmap, bitmap,
 					     bitmap, bitmap, void *));
 static void df_lr_transfer_function PARAMS ((int, int *, bitmap, bitmap, 
 					     bitmap, bitmap, void *));
+static void hybrid_search_bitmap PARAMS ((basic_block, bitmap *, bitmap *, 
+					  bitmap *, bitmap *, enum df_flow_dir, 
+					  enum df_confluence_op, 
+					  transfer_function_bitmap, 
+					  sbitmap, sbitmap, void *));
+static void hybrid_search_sbitmap PARAMS ((basic_block, sbitmap *, sbitmap *,
+					   sbitmap *, sbitmap *, enum df_flow_dir,
+					   enum df_confluence_op,
+					   transfer_function_sbitmap,
+					   sbitmap, sbitmap, void *));
 static inline bool read_modify_subreg_p PARAMS ((rtx));
 
 
@@ -1014,7 +1024,6 @@ df_uses_record (df, loc, ref_type, bb, insn, flags)
 {
   RTX_CODE code;
   rtx x;
-
  retry:
   x = *loc;
   if (!x)
@@ -1928,7 +1937,6 @@ df_luids_set (df, blocks)
   return total;
 }
 
-
 /* Perform dataflow analysis using existing DF structure for blocks
    within BLOCKS.  If BLOCKS is zero, use all basic blocks in the CFG.  */
 static void
@@ -3588,82 +3596,32 @@ debug_df_chain (link)
   fputc ('\n', stderr);
 }
 
-/* gen = GEN set.
-   kill = KILL set.
-   in, out = Filled in by function.
-   blocks = Blocks to analyze.
-   dir = Dataflow direction.
-   conf_op = Confluence operation.
-   transfun = Transfer function.
-   order = Order to iterate in. (Should map block numbers -> order)
-   data = Whatever you want.  It's passed to the transfer function.
-   
-   This function will perform iterative bitvector dataflow, producing
-   the in and out sets.  Even if you only want to perform it for a
-   small number of blocks, the vectors for in and out must be large
-   enough for *all* blocks, because changing one block might affect
-   others.  However, it'll only put what you say to analyze on the
-   initial worklist.
-   
-   For forward problems, you probably want to pass in a mapping of
-   block number to rc_order (like df->inverse_rc_map).
-*/
-
-void
-iterative_dataflow_sbitmap (in, out, gen, kill, blocks, 
-			    dir, conf_op, transfun, order, data)
-     sbitmap *in, *out, *gen, *kill;
-     bitmap blocks;
+/* Hybrid search algorithm from "Implementation Techniques for
+   Efficient Data-Flow Analysis of Large Programs".  */
+static void 
+hybrid_search_bitmap (block, in, out, gen, kill, dir, 
+		      conf_op, transfun, visited, pending, 
+		      data)
+     basic_block block;
+     bitmap *in, *out, *gen, *kill;
      enum df_flow_dir dir;
      enum df_confluence_op conf_op;
-     transfer_function_sbitmap transfun;
-     int *order;
+     transfer_function_bitmap transfun;
+     sbitmap visited;
+     sbitmap pending;
      void *data;
 {
   int changed;
-  int i;
-  fibheap_t worklist;
-  sbitmap onqueue;
-  basic_block bb;
-  onqueue = sbitmap_alloc (n_basic_blocks);
-  sbitmap_zero (onqueue);
-  worklist = fibheap_new ();
-  EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
-  {
-    fibheap_insert (worklist, order[i], (void *) i); 
-    SET_BIT (onqueue, i);
-    if (dir == FORWARD)
-      {
-	sbitmap_copy (out[i], gen[i]);
-      }
-    else
-      {
-	sbitmap_copy (in[i], gen[i]);
-      }
-    
-  });
-  while (!fibheap_empty (worklist))
+  int i = block->index;
+  edge e;
+  basic_block bb= block;
+  SET_BIT (visited, block->index);
+  if (TEST_BIT (pending, block->index))
     {
-      edge e;
-      i = (int) fibheap_extract_min  (worklist);
-      changed = 0;
-      bb = BASIC_BLOCK (i);
-      RESET_BIT (onqueue, i);
       if (dir == FORWARD)
 	{
 	  /*  Calculate <conf_op> of predecessor_outs */
-	  for (e = bb->pred; e != 0; e = e->pred_next)
-	    {
-	      if (e->src == ENTRY_BLOCK_PTR)
-		{
-		  sbitmap_zero (in[i]);
-		  continue;
-		}
-	      sbitmap_copy (in[i], out[e->src->index]);
-	      break;
-	    }
-	  if (e == 0)
-	    sbitmap_zero (in[i]);
+	  bitmap_zero (in[i]);
 	  for (e = bb->pred; e != 0; e = e->pred_next)
 	    {
 	      if (e->src == ENTRY_BLOCK_PTR)
@@ -3671,10 +3629,10 @@ iterative_dataflow_sbitmap (in, out, gen, kill, blocks,
 	      switch (conf_op)
 		{
 		case UNION:
-		  sbitmap_a_or_b (in[i], in[i], out[e->src->index]);
+		  bitmap_a_or_b (in[i], in[i], out[e->src->index]);
 		  break;
 		case INTERSECTION:
-		  sbitmap_a_and_b (in[i], in[i], out[e->src->index]);
+		  bitmap_a_and_b (in[i], in[i], out[e->src->index]);
 		  break;
 		}
 	    }
@@ -3682,7 +3640,7 @@ iterative_dataflow_sbitmap (in, out, gen, kill, blocks,
       else 
 	{
 	  /* Calculate <conf_op> of successor ins */
-	  sbitmap_zero (out[i]);
+	  bitmap_zero(out[i]);
 	  for (e = bb->succ; e != 0; e = e->succ_next)
 	    {
 	      if (e->dest == EXIT_BLOCK_PTR)
@@ -3690,104 +3648,91 @@ iterative_dataflow_sbitmap (in, out, gen, kill, blocks,
 	      switch (conf_op)
 		{	
 		case UNION:
-		  sbitmap_a_or_b (out[i], out[i], in[e->dest->index]);
+		  bitmap_a_or_b (out[i], out[i], in[e->dest->index]);
 		  break;
 		case INTERSECTION:
-		  sbitmap_a_and_b (out[i], out[i], in[e->dest->index]);
+		  bitmap_a_and_b (out[i], out[i], in[e->dest->index]);
 		  break;
 		}
 	    }
 	}      
       /* Common part */
       (*transfun)(i, &changed, in[i], out[i], gen[i], kill[i], data);
-
+      RESET_BIT (pending, i);
       if (changed)
 	{
 	  if (dir == FORWARD)
 	    {
 	      for (e = bb->succ; e != 0; e = e->succ_next)
 		{
-		  if (e->dest == EXIT_BLOCK_PTR)
+		  if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i)
 		    continue;
-		  if (!TEST_BIT (onqueue, e->dest->index))
-		    { 
-		      SET_BIT (onqueue, e->dest->index);
-		      fibheap_insert (worklist, 
-				      order[e->dest->index], 
-				      (void *)e->dest->index);
-		    }
+		  SET_BIT (pending, e->dest->index);
 		}
 	    }
 	  else
 	    {
 	      for (e = bb->pred; e != 0; e = e->pred_next)
 		{
-		  if (e->src == ENTRY_BLOCK_PTR)
+		  if (e->src == ENTRY_BLOCK_PTR || e->dest->index == i)
 		    continue;
-		  if (!TEST_BIT (onqueue, e->src->index))
-		    {
-		      SET_BIT (onqueue, e->src->index);
-		      fibheap_insert (worklist, 
-				      order[e->src->index], 
-				      (void *)e->src->index);
-		    }
-
+		  SET_BIT (pending, e->src->index);
 		}
 	    }
 	}
     }
-  sbitmap_free (onqueue);
-  fibheap_delete (worklist);
-  
+  if (dir == FORWARD)
+    {
+      for (e = bb->succ; e != 0; e = e->succ_next)
+	{
+	  if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i)
+	    continue;
+	  if (!TEST_BIT (visited, e->dest->index))
+	    hybrid_search_bitmap (e->dest, in, out, gen, kill, dir, 
+				  conf_op, transfun, visited, pending, 
+				  data);
+	}
+    }
+  else
+    {
+      for (e = bb->pred; e != 0; e = e->pred_next)
+	{
+	  if (e->src == ENTRY_BLOCK_PTR || e->src->index == i)
+	    continue;
+	  if (!TEST_BIT (visited, e->src->index))
+	    hybrid_search_bitmap (e->src, in, out, gen, kill, dir, 
+				  conf_op, transfun, visited, pending, 
+				  data);
+	}
+    }
 }
-/* Exactly the same as iterative_dataflow_sbitmap, except it works on
-   bitmaps instead */
-void
-iterative_dataflow_bitmap (in, out, gen, kill, blocks, 
-			   dir, conf_op, transfun, order, data)     
-     bitmap *in, *out, *gen, *kill;
-     bitmap blocks;
+
+
+/* Hybrid search for sbitmaps, rather than bitmaps.  */
+static void 
+hybrid_search_sbitmap (block, in, out, gen, kill, dir, 
+		       conf_op, transfun, visited, pending,
+		       data)
+     basic_block block;
+     sbitmap *in, *out, *gen, *kill;
      enum df_flow_dir dir;
      enum df_confluence_op conf_op;
-     transfer_function_bitmap transfun;
-     int *order;
+     transfer_function_sbitmap transfun;
+     sbitmap visited;
+     sbitmap pending;
      void *data;
 {
   int changed;
-  int i;
-  fibheap_t worklist;
-  sbitmap onqueue;
-  basic_block bb;
-
-  onqueue = sbitmap_alloc (n_basic_blocks);
-  sbitmap_zero (onqueue);
-  worklist = fibheap_new ();
-  EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
-  {
-    fibheap_insert (worklist, order[i], (void *) i); 
-    SET_BIT (onqueue, i);
-    if (dir == FORWARD)
-      {
-	bitmap_copy (out[i], gen[i]);
-      }
-    else
-      {
-	bitmap_copy (in[i], gen[i]);
-      }
-    
-  });
-  while (!fibheap_empty (worklist))
-    {
-      edge e;
-      i = (int) fibheap_extract_min  (worklist);
-      changed = 0;
-      bb = BASIC_BLOCK (i);
-      RESET_BIT (onqueue, i);
-      
+  int i = block->index;
+  edge e;
+  basic_block bb= block;
+  SET_BIT (visited, block->index);
+  if (TEST_BIT (pending, block->index))
+    {
       if (dir == FORWARD)
 	{
 	  /*  Calculate <conf_op> of predecessor_outs */
-	  bitmap_zero (in[i]);
+	  sbitmap_zero (in[i]);
 	  for (e = bb->pred; e != 0; e = e->pred_next)
 	    {
 	      if (e->src == ENTRY_BLOCK_PTR)
@@ -3795,10 +3740,10 @@ iterative_dataflow_bitmap (in, out, gen, kill, blocks,
 	      switch (conf_op)
 		{
 		case UNION:
-		  bitmap_a_or_b (in[i], in[i], out[e->src->index]);
+		  sbitmap_a_or_b (in[i], in[i], out[e->src->index]);
 		  break;
 		case INTERSECTION:
-		  bitmap_a_and_b (in[i], in[i], out[e->src->index]);
+		  sbitmap_a_and_b (in[i], in[i], out[e->src->index]);
 		  break;
 		}
 	    }
@@ -3806,7 +3751,7 @@ iterative_dataflow_bitmap (in, out, gen, kill, blocks,
       else 
 	{
 	  /* Calculate <conf_op> of successor ins */
-	  bitmap_zero(out[i]);
+	  sbitmap_zero(out[i]);
 	  for (e = bb->succ; e != 0; e = e->succ_next)
 	    {
 	      if (e->dest == EXIT_BLOCK_PTR)
@@ -3814,53 +3759,202 @@ iterative_dataflow_bitmap (in, out, gen, kill, blocks,
 	      switch (conf_op)
 		{	
 		case UNION:
-		  bitmap_a_or_b (out[i], out[i], in[e->dest->index]);
+		  sbitmap_a_or_b (out[i], out[i], in[e->dest->index]);
 		  break;
 		case INTERSECTION:
-		  bitmap_a_and_b (out[i], out[i], in[e->dest->index]);
+		  sbitmap_a_and_b (out[i], out[i], in[e->dest->index]);
 		  break;
 		}
 	    }
 	}      
       /* Common part */
       (*transfun)(i, &changed, in[i], out[i], gen[i], kill[i], data);
-
+      RESET_BIT (pending, i);
       if (changed)
 	{
 	  if (dir == FORWARD)
 	    {
 	      for (e = bb->succ; e != 0; e = e->succ_next)
 		{
-		  if (e->dest == EXIT_BLOCK_PTR)
+		  if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i)
 		    continue;
-		  if (!TEST_BIT (onqueue, e->dest->index))
-		    { 
-		      SET_BIT (onqueue, e->dest->index);
-		      fibheap_insert (worklist, 
-				      order[e->dest->index], 
-				      (void *)e->dest->index);
-		    }
+		  SET_BIT (pending, e->dest->index);
 		}
 	    }
 	  else
 	    {
 	      for (e = bb->pred; e != 0; e = e->pred_next)
 		{
-		  if (e->src == ENTRY_BLOCK_PTR)
+		  if (e->src == ENTRY_BLOCK_PTR || e->dest->index == i)
 		    continue;
-		  if (!TEST_BIT (onqueue, e->src->index))
-		    {
-		      SET_BIT (onqueue, e->src->index);
-		      fibheap_insert (worklist, 
-				      order[e->src->index], 
-				      (void *)e->src->index);
-		    }
-
+		  SET_BIT (pending, e->src->index);
 		}
 	    }
 	}
     }
-  sbitmap_free (onqueue);
+  if (dir == FORWARD)
+    {
+      for (e = bb->succ; e != 0; e = e->succ_next)
+	{
+	  if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i)
+	    continue;
+	  if (!TEST_BIT (visited, e->dest->index))
+	    hybrid_search_sbitmap (e->dest, in, out, gen, kill, dir, 
+				   conf_op, transfun, visited, pending, 
+				   data);
+	}
+    }
+  else
+    {
+      for (e = bb->pred; e != 0; e = e->pred_next)
+	{
+	  if (e->src == ENTRY_BLOCK_PTR || e->src->index == i)
+	    continue;
+	  if (!TEST_BIT (visited, e->src->index))
+	    hybrid_search_sbitmap (e->src, in, out, gen, kill, dir, 
+				   conf_op, transfun, visited, pending, 
+				   data);
+	}
+    }
+}
+
+
+
+
+/* gen = GEN set.
+   kill = KILL set.
+   in, out = Filled in by function.
+   blocks = Blocks to analyze.
+   dir = Dataflow direction.
+   conf_op = Confluence operation.
+   transfun = Transfer function.
+   order = Order to iterate in. (Should map block numbers -> order)
+   data = Whatever you want.  It's passed to the transfer function.
+   
+   This function will perform iterative bitvector dataflow, producing
+   the in and out sets.  Even if you only want to perform it for a
+   small number of blocks, the vectors for in and out must be large
+   enough for *all* blocks, because changing one block might affect
+   others.  However, it'll only put what you say to analyze on the
+   initial worklist.
+   
+   For forward problems, you probably want to pass in a mapping of
+   block number to rc_order (like df->inverse_rc_map).
+*/
+void
+iterative_dataflow_sbitmap (in, out, gen, kill, blocks, 
+			    dir, conf_op, transfun, order, data)     
+     sbitmap *in, *out, *gen, *kill;
+     bitmap blocks;
+     enum df_flow_dir dir;
+     enum df_confluence_op conf_op;
+     transfer_function_sbitmap transfun;
+     int *order;
+     void *data;
+{
+  int i;
+  fibheap_t worklist;
+  basic_block bb;
+  sbitmap visited, pending;
+  pending = sbitmap_alloc (n_basic_blocks);
+  visited = sbitmap_alloc (n_basic_blocks);
+  sbitmap_zero (pending);
+  sbitmap_zero (visited);
+  worklist = fibheap_new ();
+  EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
+  {
+    fibheap_insert (worklist, order[i], (void *) i); 
+    SET_BIT (pending, i);
+    if (dir == FORWARD)
+      sbitmap_copy (out[i], gen[i]);
+    else
+      sbitmap_copy (in[i], gen[i]);
+  });
+  while (sbitmap_first_set_bit (pending) != -1)
+    {
+      while (!fibheap_empty (worklist))
+	{
+	  i = (int) fibheap_extract_min  (worklist);
+	  bb = BASIC_BLOCK (i);
+	  if (!TEST_BIT (visited, bb->index))
+	    hybrid_search_sbitmap (bb, in, out, gen, kill, dir, 
+				   conf_op, transfun, visited, pending, 
+				   data);
+	}
+      if (sbitmap_first_set_bit (pending) != -1)
+	{
+	  EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
+	  {
+	    fibheap_insert (worklist, order[i], (void *) i);
+	  });
+	  sbitmap_zero (visited);
+	}
+      else
+	{
+	  break;
+	}      
+    }
+  sbitmap_free (pending);
+  sbitmap_free (visited);
   fibheap_delete (worklist);
-  
+}
+
+/* Exactly the same as iterative_dataflow_sbitmap, except it works on
+   bitmaps instead */
+void
+iterative_dataflow_bitmap (in, out, gen, kill, blocks, 
+			   dir, conf_op, transfun, order, data)     
+     bitmap *in, *out, *gen, *kill;
+     bitmap blocks;
+     enum df_flow_dir dir;
+     enum df_confluence_op conf_op;
+     transfer_function_bitmap transfun;
+     int *order;
+     void *data;
+{
+  int i;
+  fibheap_t worklist;
+  basic_block bb;
+  sbitmap visited, pending;
+  pending = sbitmap_alloc (n_basic_blocks);
+  visited = sbitmap_alloc (n_basic_blocks);
+  sbitmap_zero (pending);
+  sbitmap_zero (visited);
+  worklist = fibheap_new ();
+  EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
+  {
+    fibheap_insert (worklist, order[i], (void *) i); 
+    SET_BIT (pending, i);
+    if (dir == FORWARD)
+      bitmap_copy (out[i], gen[i]);
+    else
+      bitmap_copy (in[i], gen[i]);
+  });
+  while (sbitmap_first_set_bit (pending) != -1)
+    {
+      while (!fibheap_empty (worklist))
+	{
+	  i = (int) fibheap_extract_min  (worklist);
+	  bb = BASIC_BLOCK (i);
+	  if (!TEST_BIT (visited, bb->index))
+	    hybrid_search_bitmap (bb, in, out, gen, kill, dir, 
+				  conf_op, transfun, visited, pending, 
+				  data);
+	}
+      if (sbitmap_first_set_bit (pending) != -1)
+	{
+	  EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
+	  {
+	    fibheap_insert (worklist, order[i], (void *) i);
+	  });
+	  sbitmap_zero (visited);
+	}
+      else
+	{
+	  break;
+	}     
+    }
+  sbitmap_free (pending);
+  sbitmap_free (visited);
+  fibheap_delete (worklist);  
 }