tree-ssa-dce.c (visited_control_parents): New sbitmap to replace BB_VISITED uses.

	* tree-ssa-dce.c (visited_control_parents): New sbitmap to
	replace BB_VISITED uses.
	(find_obviously_necessary_stmts): Don't clear BB_VISITED.
	(propagate_necessity): Check the bitmap instead of BB_VISITED.
	(tree_dce_done): Free visited_control_parents.
	(perform_tree_ssa_dce): Allocate and clear it.
	* tree-ssa-pre.c (compute_antic_aux): Make non-recursive.
	(compute_antic): Iterate from here using a DFS.  Use an sbitmap
	instead of BB_VISITED.

From-SVN: r93654

3 files changed, 101 insertions, 70 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 5a7ade3..08556ae 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,15 @@
+2005-01-14  Steven Bosscher  <stevenb@suse.de>
+
+	* tree-ssa-dce.c (visited_control_parents): New sbitmap to
+	replace BB_VISITED uses.
+	(find_obviously_necessary_stmts): Don't clear BB_VISITED.
+	(propagate_necessity): Check the bitmap instead of BB_VISITED.
+	(tree_dce_done): Free visited_control_parents.
+	(perform_tree_ssa_dce): Allocate and clear it.
+	* tree-ssa-pre.c (compute_antic_aux): Make non-recursive.
+	(compute_antic): Iterate from here using a DFS.  Use an sbitmap
+	instead of BB_VISITED.
+
 2005-01-14  Kazu Hirata  <kazu@cs.umass.edu>
 
 	* c-tree.h, coverage.h, langhooks-def.h, optabs.h, output.h,
diff --git a/gcc/tree-ssa-dce.c b/gcc/tree-ssa-dce.c
index f37430d..4f72d82 100644
--- a/gcc/tree-ssa-dce.c
+++ b/gcc/tree-ssa-dce.c
@@ -93,6 +93,10 @@ static sbitmap last_stmt_necessary;
    on the Ith edge.  */
 bitmap *control_dependence_map;
 
+/* Vector indicating that a basic block has already had all the edges
+   processed that it is control dependent on.  */
+sbitmap visited_control_parents;
+
 /* Execute CODE for each edge (given number EDGE_NUMBER within the CODE)
    for which the block with index N is control dependent.  */
 #define EXECUTE_IF_CONTROL_DEPENDENT(N, EDGE_NUMBER, CODE)		      \
@@ -482,11 +486,6 @@ find_obviously_necessary_stmts (struct edge_list *el)
 	  NECESSARY (stmt) = 0;
 	  mark_stmt_if_obviously_necessary (stmt, el != NULL);
 	}
-
-      /* Mark this basic block as `not visited'.  A block will be marked
-	 visited when the edges that it is control dependent on have been
-	 marked.  */
-      bb->flags &= ~BB_VISITED;
     }
 
   if (el)
@@ -565,9 +564,10 @@ propagate_necessity (struct edge_list *el)
 	     containing `i' is control dependent on, but only if we haven't
 	     already done so.  */
 	  basic_block bb = bb_for_stmt (i);
-	  if (! (bb->flags & BB_VISITED))
+	  if (bb != ENTRY_BLOCK_PTR
+	      && ! TEST_BIT (visited_control_parents, bb->index))
 	    {
-	      bb->flags |= BB_VISITED;
+	      SET_BIT (visited_control_parents, bb->index);
 	      mark_control_dependent_edges_necessary (bb, el);
 	    }
 	}
@@ -593,9 +593,10 @@ propagate_necessity (struct edge_list *el)
 	      for (k = 0; k < PHI_NUM_ARGS (i); k++)
 		{
 		  basic_block arg_bb = PHI_ARG_EDGE (i, k)->src;
-		  if (! (arg_bb->flags & BB_VISITED))
+		  if (arg_bb != ENTRY_BLOCK_PTR
+		      && ! TEST_BIT (visited_control_parents, arg_bb->index))
 		    {
-		      arg_bb->flags |= BB_VISITED;
+		      SET_BIT (visited_control_parents, arg_bb->index);
 		      mark_control_dependent_edges_necessary (arg_bb, el);
 		    }
 		}
@@ -903,6 +904,7 @@ tree_dce_done (bool aggressive)
 	BITMAP_XFREE (control_dependence_map[i]);
       free (control_dependence_map);
 
+      sbitmap_free (visited_control_parents);
       sbitmap_free (last_stmt_necessary);
     }
 
@@ -939,6 +941,9 @@ perform_tree_ssa_dce (bool aggressive)
       find_all_control_dependences (el);
       timevar_pop (TV_CONTROL_DEPENDENCES);
 
+      visited_control_parents = sbitmap_alloc (last_basic_block);
+      sbitmap_zero (visited_control_parents);
+
       mark_dfs_back_edges ();
     }
 
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index 87e5d14..8e22e20 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -1113,52 +1113,32 @@ DEF_VEC_MALLOC_P (basic_block);
 
    ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
 
-   Iterate until fixpointed.
-
    XXX: It would be nice to either write a set_clear, and use it for
    ANTIC_OUT, or to mark the antic_out set as deleted at the end
    of this routine, so that the pool can hand the same memory back out
    again for the next ANTIC_OUT.  */
 
-
 static bool
-compute_antic_aux (basic_block block)
+compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
 {
-  basic_block son;
-  edge e;
   bool changed = false;
   value_set_t S, old, ANTIC_OUT;
   value_set_node_t node;
-  
+
   ANTIC_OUT = S = NULL;
-  /* If any edges from predecessors are abnormal, antic_in is empty, so
-     punt.  Remember that the block has an incoming abnormal edge by
-     setting the BB_VISITED flag.  */
-  if (! (block->flags & BB_VISITED))
-    {
-      edge_iterator ei;
-      FOR_EACH_EDGE (e, ei, block->preds)
-	if (e->flags & EDGE_ABNORMAL)
-	  {
-	    block->flags |= BB_VISITED;
-	    break;
-	  }
-    }
-  if (block->flags & BB_VISITED)
-    {
-      S = NULL;
-      goto visit_sons;
-    }
-  
+
+  /* If any edges from predecessors are abnormal, antic_in is empty,
+     so do nothing.  */
+  if (block_has_abnormal_pred_edge)
+    goto maybe_dump_sets;
 
   old = set_new (false);
   set_copy (old, ANTIC_IN (block));
   ANTIC_OUT = set_new (true);
 
-  /* If the block has no successors, ANTIC_OUT is empty, because it is
-     the exit block.  */
-  if (EDGE_COUNT (block->succs) == 0);
-
+  /* If the block has no successors, ANTIC_OUT is empty.  */
+  if (EDGE_COUNT (block->succs) == 0)
+    ;
   /* If we have one successor, we could have some phi nodes to
      translate through.  */
   else if (EDGE_COUNT (block->succs) == 1)
@@ -1206,21 +1186,16 @@ compute_antic_aux (basic_block block)
 							 TMP_GEN (block),
 							 true);
   
-  /* Then union in the ANTIC_OUT - TMP_GEN values, to get ANTIC_OUT U
-     EXP_GEN - TMP_GEN */
-  for (node = S->head;
-       node;
-       node = node->next)
-    {
-      value_insert_into_set (ANTIC_IN (block), node->expr);
-    }
-  clean (ANTIC_IN (block));
-  
+  /* Then union in the ANTIC_OUT - TMP_GEN values,
+     to get ANTIC_OUT U EXP_GEN - TMP_GEN */
+  for (node = S->head; node; node = node->next)
+    value_insert_into_set (ANTIC_IN (block), node->expr);
 
+  clean (ANTIC_IN (block));
   if (!set_equal (old, ANTIC_IN (block)))
     changed = true;
 
- visit_sons:
+ maybe_dump_sets:
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       if (ANTIC_OUT)
@@ -1228,43 +1203,82 @@ compute_antic_aux (basic_block block)
       print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
       if (S)
 	print_value_set (dump_file, S, "S", block->index);
-
     }
 
-  for (son = first_dom_son (CDI_POST_DOMINATORS, block);
-       son;
-       son = next_dom_son (CDI_POST_DOMINATORS, son))
-    {
-      changed |= compute_antic_aux (son);
-    }
   return changed;
 }
 
-/* Compute ANTIC sets.  */
+/* Compute ANTIC sets.  Iterates until fixpointed.  */
 
 static void
 compute_antic (void)
 {
-  bool changed = true;
-  basic_block bb;
+  bool changed= true;
   int num_iterations = 0;
-  FOR_ALL_BB (bb)
+  basic_block block, *worklist;
+  size_t sp = 0;
+  sbitmap has_abnormal_preds;
+
+  /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
+     We pre-build the map of blocks with incoming abnormal edges here.  */
+  has_abnormal_preds = sbitmap_alloc (last_basic_block);
+  sbitmap_zero (has_abnormal_preds);
+  FOR_EACH_BB (block)
     {
-      ANTIC_IN (bb) = set_new (true);
-      gcc_assert (!(bb->flags & BB_VISITED));
+      edge_iterator ei;
+      edge e;
+
+      FOR_EACH_EDGE (e, ei, block->preds)
+        if (e->flags & EDGE_ABNORMAL)
+          {
+            SET_BIT (has_abnormal_preds, block->index);
+            break;
+          }
+
+      /* While we are here, give empty ANTIC_IN sets to each block.  */
+      ANTIC_IN (block) = set_new (true);
     }
+  /* At the exit block we anticipate nothing.  */
+  ANTIC_IN (EXIT_BLOCK_PTR) = set_new (true);
+
+  /* Allocate the worklist.  */
+  worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
 
+  /* Loop until fixpointed.  */
   while (changed)
     {
-      num_iterations++;
+      basic_block son, bb;
+
       changed = false;
-      changed = compute_antic_aux (EXIT_BLOCK_PTR);
-    }
-  FOR_ALL_BB (bb)
-    {
-      bb->flags &= ~BB_VISITED;
+      num_iterations++;
+
+      /* Seed the algorithm by putting post-dominator children of
+         the exit block in the worklist.  */
+      for (son = first_dom_son (CDI_POST_DOMINATORS, EXIT_BLOCK_PTR);
+	   son;
+	   son = next_dom_son (CDI_POST_DOMINATORS, son))
+	worklist[sp++] = son;
+
+      /* Now visit all blocks in a DFS of the post dominator tree.  */
+      while (sp)
+	{
+	  bool bb_has_abnormal_pred;
+
+	  bb = worklist[--sp];
+	  bb_has_abnormal_pred = TEST_BIT (has_abnormal_preds, bb->index);
+ 	  changed |= compute_antic_aux (bb, bb_has_abnormal_pred);
+
+	  for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
+	       son;
+	       son = next_dom_son (CDI_POST_DOMINATORS, son))
+	    worklist[sp++] = son;
+	}
     }
-  if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
+
+  free (worklist);
+  sbitmap_free (has_abnormal_preds);
+
+  if (dump_file && (dump_flags & TDF_STATS))
     fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
 }