gcse.c (post_dominators): Kill.

        * gcse.c (post_dominators): Kill.
        (alloc_code_hoist_mem, free_code_hoist_mem); Kill post_dominators.
        (compute_code_hoist_data): Use compute_flow_dominators.  Do not
        pass in a pdom array since we do not need pdoms.
        * haifa-sched.c (schedule_insns): Similarly.
        * flow.c (compute_dominators): Remove dead function.
        (compute_flow_dominators): Do not compute doms or pdoms if the
        caller does not request them.  Split up loop to build doms and
        pdoms.  Use a worklist to compute doms and pdoms.
        * basic-block.h (compute_dominators): Remove prototype.

From-SVN: r30437

1 files changed, 80 insertions, 66 deletions

diff --git a/gcc/flow.c b/gcc/flow.c
index 43688ae..bf48263 100644
--- a/gcc/flow.c
+++ b/gcc/flow.c
@@ -5317,95 +5317,109 @@ free_bb_mem ()
   free_int_list (&pred_int_list_blocks);
 }
 
-/* Compute dominator relationships.  */
+/* Compute dominator relationships using new flow graph structures.  */
 void
-compute_dominators (dominators, post_dominators, s_preds, s_succs)
+compute_flow_dominators (dominators, post_dominators)
      sbitmap *dominators;
      sbitmap *post_dominators;
-     int_list_ptr *s_preds;
-     int_list_ptr *s_succs;
 {
-  int bb, changed, passes;
+  int bb;
   sbitmap *temp_bitmap;
+  edge e;
+  basic_block *worklist, *tos;
+
+  /* Allocate a worklist array/queue.  Entries are only added to the
+     list if they were not already on the list.  So the size is
+     bounded by the number of basic blocks.  */
+  tos = worklist = (basic_block *) xmalloc (sizeof (basic_block)
+		    * n_basic_blocks);
 
   temp_bitmap = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
-  sbitmap_vector_ones (dominators, n_basic_blocks);
-  sbitmap_vector_ones (post_dominators, n_basic_blocks);
   sbitmap_vector_zero (temp_bitmap, n_basic_blocks);
 
-  sbitmap_zero (dominators[0]);
-  SET_BIT (dominators[0], 0);
-
-  sbitmap_zero (post_dominators[n_basic_blocks - 1]);
-  SET_BIT (post_dominators[n_basic_blocks - 1], 0);
-
-  passes = 0;
-  changed = 1;
-  while (changed)
+  if (dominators)
     {
-      changed = 0;
-      for (bb = 1; bb < n_basic_blocks; bb++)
+      sbitmap_vector_ones (dominators, n_basic_blocks);
+      sbitmap_zero (dominators[0]);
+      SET_BIT (dominators[0], 0);
+
+      /* Put the successors of the entry block on the worklist.  */
+      for (e = BASIC_BLOCK (0)->succ; e; e = e->succ_next)
 	{
-	  sbitmap_intersect_of_predecessors (temp_bitmap[bb], dominators,
-					     bb, s_preds);
-	  SET_BIT (temp_bitmap[bb], bb);
-	  changed |= sbitmap_a_and_b (dominators[bb],
-				      dominators[bb],
-				      temp_bitmap[bb]);
-	  sbitmap_intersect_of_successors (temp_bitmap[bb], post_dominators,
-					   bb, s_succs);
-	  SET_BIT (temp_bitmap[bb], bb);
-	  changed |= sbitmap_a_and_b (post_dominators[bb],
-				      post_dominators[bb],
-				      temp_bitmap[bb]);
+	  *tos++ = e->dest;
+	  e->dest->aux = e;
 	}
-      passes++;
-    }
 
-  free (temp_bitmap);
-}
+      /* Iterate until the worklist is empty.  */
+      while (tos != worklist)
+	{
+	  /* Take the first entry off the worklist.  */
+	  basic_block b = *--tos;
+	  b->aux = NULL;
+	  bb = b->index;
 
-/* Compute dominator relationships using new flow graph structures.  */
-void
-compute_flow_dominators (dominators, post_dominators)
-     sbitmap *dominators;
-     sbitmap *post_dominators;
-{
-  int bb, changed, passes;
-  sbitmap *temp_bitmap;
+	  sbitmap_intersection_of_preds (temp_bitmap[bb], dominators, bb);
+	  SET_BIT (temp_bitmap[bb], bb);
 
-  temp_bitmap = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
-  sbitmap_vector_ones (dominators, n_basic_blocks);
-  sbitmap_vector_ones (post_dominators, n_basic_blocks);
-  sbitmap_vector_zero (temp_bitmap, n_basic_blocks);
+	  /* If the out state of this block changed, then we need to
+	     add the successors of this block to the worklist if they
+	     are not already on the worklist.  */
+	  if (sbitmap_a_and_b (dominators[bb], dominators[bb], temp_bitmap[bb]))
+	    {
+	      for (e = b->succ; e; e = e->succ_next)
+		{
+		  if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
+		    {
+		      *tos++ = e->dest;
+		      e->dest->aux = e;
+		    }
+		}
+	    }
+	}
+    }
 
-  sbitmap_zero (dominators[0]);
-  SET_BIT (dominators[0], 0);
+  if (post_dominators)
+    {
+      sbitmap_vector_ones (post_dominators, n_basic_blocks);
+      sbitmap_zero (post_dominators[n_basic_blocks - 1]);
+      SET_BIT (post_dominators[n_basic_blocks - 1], 0);
 
-  sbitmap_zero (post_dominators[n_basic_blocks - 1]);
-  SET_BIT (post_dominators[n_basic_blocks - 1], 0);
+      /* Put the predecessors of the exit block on the worklist.  */
+      for (e = BASIC_BLOCK (n_basic_blocks - 1)->pred; e; e = e->pred_next)
+	{
+	  *tos++ = e->src;
+	  e->src->aux = e;
+	}
 
-  passes = 0;
-  changed = 1;
-  while (changed)
-    {
-      changed = 0;
-      for (bb = 1; bb < n_basic_blocks; bb++)
+      /* Iterate until the worklist is empty.  */
+      while (tos != worklist)
 	{
-	  sbitmap_intersection_of_preds (temp_bitmap[bb], dominators, bb);
-	  SET_BIT (temp_bitmap[bb], bb);
-	  changed |= sbitmap_a_and_b (dominators[bb],
-				      dominators[bb],
-				      temp_bitmap[bb]);
+	  /* Take the first entry off the worklist.  */
+	  basic_block b = *--tos;
+	  b->aux = NULL;
+	  bb = b->index;
+
 	  sbitmap_intersection_of_succs (temp_bitmap[bb], post_dominators, bb);
 	  SET_BIT (temp_bitmap[bb], bb);
-	  changed |= sbitmap_a_and_b (post_dominators[bb],
-				      post_dominators[bb],
-				      temp_bitmap[bb]);
+
+	  /* If the out state of this block changed, then we need to
+	     add the successors of this block to the worklist if they
+	     are not already on the worklist.  */
+	  if (sbitmap_a_and_b (post_dominators[bb],
+			       post_dominators[bb],
+			       temp_bitmap[bb]))
+	    {
+	      for (e = b->pred; e; e = e->pred_next)
+		{
+		  if (!e->src->aux && e->src != ENTRY_BLOCK_PTR)
+		    {
+		      *tos++ = e->src;
+		      e->src->aux = e;
+		    }
+		}
+	    }
 	}
-      passes++;
     }
-
   free (temp_bitmap);
 }