sbitmap.h (sbitmap_intersection_of_succs): Add prototype.

Wed Aug 25 13:55:47 EDT 1999  Andrew MacLeod  <amacleod@cygnus.com>

	* sbitmap.h (sbitmap_intersection_of_succs): Add prototype.
	(sbitmap_intersection_of_preds, sbitmap_union_of_succs,
	sbitmap_union_of_preds): Add prototypes.
	* sbitmap.c (sbitmap_intersection_of_succs): New function to compute
	the intersection of successors with the new flow graph structures.
	(sbitmap_intersection_of_preds): New function to compute the
	intersection of predecessors with the new flow graph structures.
	(sbitmap_union_of_succs): New function to compute the union of
	successors with the new flow graph structures.
	(sbitmap_union_of_preds): New function to compute the union of
	predecessors with the new flow graph structures.
	* gcse.c (compute_rdm, compute_available): Use new sbitmap routines.
	(expr_reaches_here_p): Use edge and basic_block structures instead
	of s_preds and s_succs.
	(compute_cprop_avinout): Use new sbitmap routines.
	(pre_expr_reaches_here_p): Use edge and basic_block structures instead
	of s_preds and s_succs.
	* flow.c (compute_flow_dominators): Compute dominators using
	edges and basic blocks instead of s_preds and s_succs.

From-SVN: r28866

5 files changed, 245 insertions, 12 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 3e39ae7c08c..7267f064574 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,25 @@
+Wed Aug 25 13:55:47 EDT 1999  Andrew MacLeod  <amacleod@cygnus.com>
+
+	* sbitmap.h (sbitmap_intersection_of_succs): Add prototype.
+	(sbitmap_intersection_of_preds, sbitmap_union_of_succs, 
+	sbitmap_union_of_preds): Add prototypes.
+	* sbitmap.c (sbitmap_intersection_of_succs): New function to compute
+	the intersection of successors with the new flow graph structures.
+	(sbitmap_intersection_of_preds): New function to compute the 
+	intersection of predecessors with the new flow graph structures.
+	(sbitmap_union_of_succs): New function to compute the union of 
+	successors with the new flow graph structures.
+	(sbitmap_union_of_preds): New function to compute the union of 
+	predecessors with the new flow graph structures.
+	* gcse.c (compute_rdm, compute_available): Use new sbitmap routines.
+	(expr_reaches_here_p): Use edge and basic_block structures instead 
+	of s_preds and s_succs.
+	(compute_cprop_avinout): Use new sbitmap routines.
+	(pre_expr_reaches_here_p): Use edge and basic_block structures instead 
+	of s_preds and s_succs.
+	* flow.c (compute_flow_dominators): Compute dominators using
+	edges and basic blocks instead of s_preds and s_succs.
+
 Wed Aug 25 13:41:47 EDT 1999  Andrew MacLeod  <amacleod@cygnus.com>
 
 	* lists.c (unused_insn_list, unused_expr_list): New file for
diff --git a/gcc/flow.c b/gcc/flow.c
index d1b493bbe5a..a6420a74507 100644
--- a/gcc/flow.c
+++ b/gcc/flow.c
@@ -4678,6 +4678,50 @@ compute_dominators (dominators, post_dominators, s_preds, s_succs)
   free (temp_bitmap);
 }
 
+/* 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;
+
+  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)
+    {
+      changed = 0;
+      for (bb = 1; bb < n_basic_blocks; bb++)
+	{
+	  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]);
+	  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]);
+	}
+      passes++;
+    }
+
+  free (temp_bitmap);
+}
+
 /* Given DOMINATORS, compute the immediate dominators into IDOM.  */
 
 void
diff --git a/gcc/gcse.c b/gcc/gcse.c
index f5fe9b9cd6f..7a484ab2be7 100644
--- a/gcc/gcse.c
+++ b/gcc/gcse.c
@@ -2632,8 +2632,7 @@ compute_rd ()
       changed = 0;
       for (bb = 0; bb < n_basic_blocks; bb++)
 	{
-	  sbitmap_union_of_predecessors (reaching_defs[bb], rd_out,
-					 bb, s_preds);
+	  sbitmap_union_of_preds (reaching_defs[bb], rd_out, bb);
 	  changed |= sbitmap_union_of_diff (rd_out[bb], rd_gen[bb],
 					    reaching_defs[bb], rd_kill[bb]);
 	}
@@ -2833,7 +2832,7 @@ compute_available ()
       changed = 0;
       for (bb = 1; bb < n_basic_blocks; bb++)
 	{
-	  sbitmap_intersect_of_predecessors (ae_in[bb], ae_out, bb, s_preds);
+	  sbitmap_intersection_of_preds (ae_in[bb], ae_out, bb);
 	  changed |= sbitmap_union_of_diff (ae_out[bb], ae_gen[bb],
 					    ae_in[bb], ae_kill[bb]);
 	}
@@ -2870,7 +2869,7 @@ expr_reaches_here_p (occr, expr, bb, check_self_loop, visited)
      int check_self_loop;
      char *visited;
 {
-  int_list_ptr pred;
+  edge pred;
 
   if (visited == NULL)
     {
@@ -2878,9 +2877,9 @@ expr_reaches_here_p (occr, expr, bb, check_self_loop, visited)
       bzero (visited, n_basic_blocks);
     }
 
-  for (pred = s_preds[bb]; pred != NULL; pred = pred->next)
+  for (pred = BASIC_BLOCK(bb)->pred; pred != NULL; pred = pred->pred_next)
     {
-      int pred_bb = INT_LIST_VAL (pred);
+      int pred_bb = pred->src->index;
 
       if (visited[pred_bb])
 	{
@@ -3512,8 +3511,7 @@ compute_cprop_avinout ()
       for (bb = 0; bb < n_basic_blocks; bb++)
 	{
 	  if (bb != 0)
-	    sbitmap_intersect_of_predecessors (cprop_avin[bb],
-					       cprop_avout, bb, s_preds);
+	    sbitmap_intersection_of_preds (cprop_avin[bb], cprop_avout, bb);
 	  changed |= sbitmap_union_of_diff (cprop_avout[bb],
 					    cprop_pavloc[bb],
 					    cprop_avin[bb],
@@ -4125,7 +4123,7 @@ pre_expr_reaches_here_p (occr_bb, expr, bb, check_pre_comp, visited)
      int check_pre_comp;
      char *visited;
 {
-  int_list_ptr pred;
+  edge pred;
 
   if (visited == NULL)
     {
@@ -4133,11 +4131,11 @@ pre_expr_reaches_here_p (occr_bb, expr, bb, check_pre_comp, visited)
       bzero (visited, n_basic_blocks);
     }
 
-  for (pred = s_preds[bb]; pred != NULL; pred = pred->next)
+  for (pred = BASIC_BLOCK (bb)->pred; pred != NULL; pred = pred->pred_next)
     {
-      int pred_bb = INT_LIST_VAL (pred);
+      int pred_bb = pred->src->index;
 
-      if (pred_bb == ENTRY_BLOCK
+      if (pred->src == ENTRY_BLOCK_PTR
 	  /* Has predecessor has already been visited?  */
 	  || visited[pred_bb])
 	{
diff --git a/gcc/sbitmap.c b/gcc/sbitmap.c
index 2a417922300..89d6600927d 100644
--- a/gcc/sbitmap.c
+++ b/gcc/sbitmap.c
@@ -429,6 +429,166 @@ sbitmap_union_of_predsucc (dst, src, bb, pred_succ)
     }
 }
 
+/* Set the bitmap DST to the intersection of SRC of successors of
+   block number BB, using the new flow graph structures.  */
+
+void
+sbitmap_intersection_of_succs (dst, src, bb)
+     sbitmap dst;
+     sbitmap *src;
+     int bb;
+{
+  basic_block b = BASIC_BLOCK (bb);
+  edge e = b->succ;
+  int set_size = dst->size;
+
+  for ( ; e != NULL; e = e->succ_next)
+    {
+      if (e->dest == EXIT_BLOCK_PTR)
+        continue;
+      sbitmap_copy (dst, src[e->dest->index]);
+      break;
+    }
+  if (e == NULL)
+    sbitmap_ones (dst);
+  else
+    {
+      for ( e = e->succ_next; e != NULL; e = e->succ_next)
+        {
+	  int i;
+	  sbitmap_ptr p,r;
+
+	  if (e->dest == EXIT_BLOCK_PTR)
+	    continue;
+
+	  p = src[e->dest->index]->elms;
+	  r = dst->elms;
+	  for (i = 0; i < set_size; i++)
+	    *r++ &= *p++;
+	}
+    }
+}
+
+/* Set the bitmap DST to the intersection of SRC of predecessors of
+   block number BB, using the new flow graph structures.  */
+
+void
+sbitmap_intersection_of_preds (dst, src, bb)
+     sbitmap dst;
+     sbitmap *src;
+     int bb;
+{
+  basic_block b = BASIC_BLOCK (bb);
+  edge e = b->pred;
+  int set_size = dst->size;
+
+  for ( ; e != NULL; e = e->pred_next)
+    {
+      if (e->src== ENTRY_BLOCK_PTR)
+        continue;
+      sbitmap_copy (dst, src[e->src->index]);
+      break;
+    }
+  if (e == NULL)
+    sbitmap_ones (dst);
+  else
+    {
+      for ( e = e->pred_next; e != NULL; e = e->pred_next)
+        {
+	  int i;
+	  sbitmap_ptr p,r;
+
+	  if (e->src == ENTRY_BLOCK_PTR)
+	    continue;
+
+	  p = src[e->src->index]->elms;
+	  r = dst->elms;
+	  for (i = 0; i < set_size; i++)
+	    *r++ &= *p++;
+	}
+    }
+}
+
+/* Set the bitmap DST to the union of SRC of successors of
+   block number BB, using the new flow graph structures.  */
+
+void
+sbitmap_union_of_succs (dst, src, bb)
+     sbitmap dst;
+     sbitmap *src;
+     int bb;
+{
+  basic_block b = BASIC_BLOCK (bb);
+  edge e = b->succ;
+  int set_size = dst->size;
+
+  for ( ; e != NULL; e = e->succ_next)
+    {
+      if (e->dest == EXIT_BLOCK_PTR)
+        continue;
+      sbitmap_copy (dst, src[e->dest->index]);
+      break;
+    }
+  if (e == NULL)
+    sbitmap_zero (dst);
+  else
+    {
+      for ( e = e->succ_next; e != NULL; e = e->succ_next)
+        {
+	  int i;
+	  sbitmap_ptr p,r;
+
+	  if (e->dest == EXIT_BLOCK_PTR)
+	    continue;
+
+	  p = src[e->dest->index]->elms;
+	  r = dst->elms;
+	  for (i = 0; i < set_size; i++)
+	    *r++ |= *p++;
+	}
+    }
+}
+
+/* Set the bitmap DST to the union of SRC of predecessors of
+   block number BB, using the new flow graph structures.  */
+
+void
+sbitmap_union_of_preds (dst, src, bb)
+     sbitmap dst;
+     sbitmap *src;
+     int bb;
+{
+  basic_block b = BASIC_BLOCK (bb);
+  edge e = b->pred;
+  int set_size = dst->size;
+
+  for ( ; e != NULL; e = e->pred_next)
+    {
+      if (e->src== ENTRY_BLOCK_PTR)
+        continue;
+      sbitmap_copy (dst, src[e->src->index]);
+      break;
+    }
+  if (e == NULL)
+    sbitmap_zero (dst);
+  else
+    {
+      for ( e = e->pred_next; e != NULL; e = e->pred_next)
+        {
+	  int i;
+	  sbitmap_ptr p,r;
+
+	  if (e->src == ENTRY_BLOCK_PTR)
+	    continue;
+
+	  p = src[e->src->index]->elms;
+	  r = dst->elms;
+	  for (i = 0; i < set_size; i++)
+	    *r++ |= *p++;
+	}
+    }
+}
+
 void
 dump_sbitmap (file, bmap)
      FILE *file;
diff --git a/gcc/sbitmap.h b/gcc/sbitmap.h
index ca475fa756c..ca2f99730a5 100644
--- a/gcc/sbitmap.h
+++ b/gcc/sbitmap.h
@@ -120,3 +120,12 @@ extern void sbitmap_union_of_predsucc PROTO ((sbitmap, sbitmap *, int,
 					      struct int_list **));
 #define sbitmap_union_of_predecessors  sbitmap_union_of_predsucc
 #define sbitmap_union_of_successors    sbitmap_union_of_predsucc
+
+/* Intersection and Union of preds/succs using the new flow graph 
+   structure instead of the pred/succ arrays.  */
+
+extern void sbitmap_intersection_of_succs    PROTO ((sbitmap, sbitmap *, int));
+extern void sbitmap_intersection_of_preds    PROTO ((sbitmap, sbitmap *, int));
+extern void sbitmap_union_of_succs	     PROTO ((sbitmap, sbitmap *, int));
+extern void sbitmap_union_of_preds	     PROTO ((sbitmap, sbitmap *, int));
+