Re: dominator tree

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'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. While it is mostly of theoretical interest,
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.


Note to flamers: we all know about Lengauer&Tarjan's algorithm, which
is the algorithm of choice, even if Harel's algorithm truly is linear,
but the true academic in me gags when I see linear time complexity
claims based on an unproven algorithm.


Michael Wolfe, closet academic
--

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