immediate dominators

[Jeffrey A Law]

Something that Mark Mitchell needs for future work:


        * flow.c (compute_immediate_dominators): New function.
        * basic-block.h (compute_immediate_dominators): Declare it.

Index: basic-block.h
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/basic-block.h,v
retrieving revision 1.21
diff -c -3 -p -r1.21 basic-block.h
*** basic-block.h	1999/02/25 23:45:08	1.21
--- basic-block.h	1999/03/18 05:56:45
*************** extern void compute_preds_succs		PROTO (
*** 249,251 ****
--- 249,252 ----
  extern void compute_dominators		PROTO ((sbitmap *, sbitmap *,
  						int_list_ptr *,
  						int_list_ptr *));
+ extern void compute_immediate_dominators	PROTO ((int *, sbitmap *));
Index: flow.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/flow.c,v
retrieving revision 1.105
diff -c -3 -p -r1.105 flow.c
*** flow.c	1999/03/09 15:49:53	1.105
--- flow.c	1999/03/18 05:56:51
*************** compute_dominators (dominators, post_dom
*** 4560,4565 ****
--- 4560,4605 ----
    free (temp_bitmap);
  }
  
+ /* Given DOMINATORS, compute the immediate dominators into IDOM.  */
+ 
+ void
+ compute_immediate_dominators (idom, dominators)
+      int *idom;
+      sbitmap *dominators;
+ {
+   sbitmap *tmp;
+   int b;
+ 
+   tmp = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
+ 
+   /* Begin with tmp(n) = dom(n) - { n }.  */
+   for (b = n_basic_blocks; --b >= 0; )
+     {
+       sbitmap_copy (tmp[b], dominators[b]);
+       RESET_BIT (tmp[b], b);
+     }
+ 
+   /* Subtract out all of our dominator's dominators.  */
+   for (b = n_basic_blocks; --b >= 0; )
+     {
+       sbitmap tmp_b = tmp[b];
+       int s;
+ 
+       for (s = n_basic_blocks; --s >= 0; )
+ 	if (TEST_BIT (tmp_b, s))
+ 	  sbitmap_difference (tmp_b, tmp_b, tmp[s]);
+     }
+ 
+   /* Find the one bit set in the bitmap and put it in the output array.  */
+   for (b = n_basic_blocks; --b >= 0; )
+     {
+       int t;
+       EXECUTE_IF_SET_IN_SBITMAP (tmp[b], 0, t, { idom[b] = t; });
+     }
+ 
+   sbitmap_vector_free (tmp);
+ }
+ 
  /* Count for a single SET rtx, X.  */
  
  static void