Fast dominators code

[Brad Lucier <lucier at math dot purdue dot edu>]

Michael Matz submitted the following patch:

http://gcc.gnu.org/ml/gcc-patches/2000-06/msg00794.html

part of which includes ldc.c, a (near) linear time dominators computation,
which is *much* faster than the current dominators calculation.  At the
time, this patch applied cleanly, and passed make bootstrap and make
check with no regressions.  Matz's copyright assignment has since been
registered by the FSF. I would very much like this patch to be in GCC 3.0.

Richard Henderson in

http://gcc.gnu.org/ml/gcc-patches/2000-08/msg00161.html

remarks:

> I'd prefer that we not create such trivial wrapper functions.  Instead,
> just modify all current users of compute_flow_dominators to use your
> new function.
> 
> Additionally, since the algorithm has the entire dominator tree, then
> immediate dominators are available directly.  You should export an
> interface to get at them, and then replace the existing
> compute_immediate_dominators function.

Jeff Law in

http://gcc.gnu.org/ml/gcc-patches/2000-08/msg00033.html

remarks:

> Never include assert.h.
...
> The formatting for init_ar, stack_top,stack_pop has a number of problems. 
> 
> Comments should be complete sentences with proper capitalization and
> punctuation.  You have several that start with lower case.
> 
> Most of your code could stand for some whitespace at boundaries where you
> transition from one logical task to another.
...

In later e-mails, Jeff makes more general remarks about the choice of
algorithm, etc.

I am willing (and I believe able) to make the low-level changes requested
by Jeff, and to implement the changes implied by Richard's first comment.
(I'm not so sure about my implementing Richard's second suggestion.)
I'm in no position to implement a different algorithm.

With these considerations, I don't want to put the effort into cleaning up
this submission if the real problem is the choice of algorithm, etc.  So,
what do people think?  (I'm not asking for pre-approval of a cleaned-up
patch, I'm asking for people's ideas about how I should proceed.)

Brad Lucier