Re: dominator tree

Michael Wolfe wrote:
>
> Aaron Leon Kaplan writes:
> > Has anyone implemented the dominator tree algorithm by Dov Harel
> > (idescribed in the paper "A linear time algorithm for finding
> > dominators in a flow graph and related problems")?
>
> I'd like to see this myself; I've never found anyone who claims to
> have even really understood the whole algorithm. At one PLDI meeting,
> there was one fellow from Australia who claimed he had the algorithm
> 'almost' implemented, but after the meeting I didn't get the promised
> copy of the program.


I am the above mentioned person, and indeed I did have a mostly working
implementation, but I quickly found that the amount of time required to check
my understanding of Harel's algorithm, then check that my code agrees with my
understanding, was far more than the amount of time required to write the
standard Tarjan method. In the last 2.5 years I have scarcely had enough time
to squeeze in any compiler work at all, so the Harel stuff was one of the
first things to get dropped, sorry.


In addition, my use is for a real-world optimizer, and I currently don't have
the confidence in either the Harel algorithm's correctness nor my
understanding and implementation of it to guarantee it for real-world use
where other people (end users) might suffer if I were wrong.


This is a case where going against the flow is just not worth it, because the
effort and especially the risks are not worth the infinitesimally small gain.
Perhaps you might say that I gave up, but I look at it more like cutting my
losses.


The bottom line is that Tarjan's algorithm is well understood, well tested in
practice, and not a performance problem at all in the context of a real-world
optimizer. My very limited testing showed that Tarjan is certainly no slower
in practice (perhaps even faster, given the nature of implementing such
algorithms and tuning them etc).




> I've exchanged email with Dov Harel, but it's been so long that he's
> not up to speed on all the details and not all that interested either.


This is the problem with pursuing it at all. Given the all-too-short lifetimes
of human beings, there are some problems that are just not worth wasting six
months on.




> there are lots of papers claiming 'linear time complexity' based on
> the linear time DOM algorithm, I think as a community we should make
> the effort to verify the algorithm. Interestingly, none of the
> authors making these claims shows any interest in doing such an
> implementation.


And I can certainly understand why :-)




JASON PATTERSON
  jason@reflections.com.au http://www.reflections.com.au/~jason


      A UNIX Christmas Carol: ls; ncheck; ncheck
                                                        who | grep naughty; who | grep nice
                                                        santa_claus <northpole >town




--

Return to the comp.compilers page.
Search the comp.compilers archives again.