[patch] new dominance calculator

[Michael Matz <matzmich at cs dot tu-berlin dot de>]

Hi,

until the assignment is sorted out, I thought I send the implementation of
a linear algorithm for dominator calculation, for some people to review
and make suggestions. The code itself is ready since some weeks, but it
took so long because writing comments is boring ;)

As I prefer small files which do one thing, I implemented the whole stuff
in a new file (ldc.c as in "linear dominance calculator" ;). The patch
merely includes that new file in the Makefile and changes flow.c to use
the new routines. This implementation is only nearly linear, because I
didn't use microtrees, but the effect of them should be marginal, while
their implementation is overly complex. After all, this routine can
calculate the immediate dominators in a graph of 5151 nodes and 2502003
edges in 12 seconds on a crappy old pentium-166 with an unoptimized cc1 ;)

It bootstraps on Alpha and i386. I also tested and compared that algorithm
and the current implementation in gcc (with some heavy optimizations) on
many random graphs.


Ciao,
Michael.

ldc.c.gz

	* ldc.c: New file.
	* Makefile.in (OBJS): Include it.
	(ldc.o): Dependies.
	* basic-block.h: Prototype for calculate_flow_dominators (from ldc.c).
	* flow.c (compute_flow_dominators_old): renamed from
	compute_flow_dominators.
	(compute_flow_dominators): Use calculate_flow_dominators.


Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/egcs/gcc/Makefile.in,v
retrieving revision 1.470
diff -u -r1.470 Makefile.in
--- Makefile.in	2000/06/22 21:01:04	1.470
+++ Makefile.in	2000/06/24 00:51:16
@@ -686,7 +686,7 @@
  function.o stmt.o except.o expr.o calls.o expmed.o explow.o optabs.o real.o  \
  builtins.o intl.o varasm.o rtl.o print-rtl.o rtlanal.o emit-rtl.o genrtl.o   \
  dbxout.o sdbout.o dwarfout.o dwarf2out.o xcoffout.o bitmap.o alias.o gcse.o  \
- integrate.o jump.o cse.o loop.o unroll.o flow.o combine.o varray.o	      \
+ integrate.o jump.o cse.o loop.o unroll.o flow.o ldc.o combine.o varray.o     \
  regclass.o regmove.o local-alloc.o global.o reload.o reload1.o caller-save.o \
  insn-peep.o reorg.o haifa-sched.o final.o recog.o reg-stack.o regrename.o    \
  insn-opinit.o insn-recog.o insn-extract.o insn-output.o insn-emit.o lcm.o    \
@@ -1334,6 +1334,7 @@
 flow.o : flow.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h insn-config.h \
    $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \
    insn-flags.h function.h except.h $(EXPR_H)
+ldc.o : ldc.c $(CONFIG_H) system.h $(RTL_H) $(BASIC_BLOCK_H) sbitmap.h
 combine.o : combine.c $(CONFIG_H) system.h $(RTL_H) flags.h function.h \
    insn-config.h insn-flags.h insn-codes.h insn-attr.h $(REGS_H) $(EXPR_H) \
    $(BASIC_BLOCK_H) $(RECOG_H) real.h hard-reg-set.h toplev.h
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/basic-block.h,v
retrieving revision 1.71
diff -u -r1.71 basic-block.h
--- basic-block.h	2000/06/14 07:41:57	1.71
+++ basic-block.h	2000/06/24 00:51:16
@@ -517,4 +517,7 @@
 						 void *));
 extern int in_ssa_form;
 
+/* In ldc.c */
+extern void calculate_flow_dominators   PARAMS ((sbitmap *, unsigned int));
+
 #endif /* _BASIC_BLOCK_H */
Index: flow.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/flow.c,v
retrieving revision 1.303
diff -u -r1.303 flow.c
--- flow.c	2000/06/19 22:31:47	1.303
+++ flow.c	2000/06/24 00:51:17
@@ -5957,9 +5957,26 @@
     }
 }
 
-/* Compute dominator relationships using new flow graph structures.  */
+/* Compute dominator relationships using new flow graph structures in
+   nearly linear time.  */
 void
 compute_flow_dominators (dominators, post_dominators)
+     sbitmap *dominators;
+     sbitmap *post_dominators;
+{
+  if (dominators)
+    {
+      calculate_flow_dominators (dominators, 0);
+    }
+  if (post_dominators)
+    {
+      calculate_flow_dominators (post_dominators, 1);
+    }
+}
+
+/* Compute dominator relationships using new flow graph structures.  */
+void
+compute_flow_dominators_old (dominators, post_dominators)
      sbitmap *dominators;
      sbitmap *post_dominators;
 {