Jeffrey A Law
Tue Aug 29 16:44:00 GMT 2000
In message < Pine.GSO.4.21.0008230552470.17066-100000@platon >you write:
> I have no hard data about it. But as it is now, I view it as an
> optimization (and simplification) of the L/T algorithm (mainly the part of
> compressing the I-paths), so I have the impression that it is practically
> faster (although may be not in a better O() class) than L/T esp. for tree
> patterns commonly seen with normal programs.
I'm mostly concerned with implementation complexity right now.
I suspect that anything that gets us to nlogn or better is going to be
sufficiently better than our current simple algorithm -- so much in fact
differences between nlogn or better algorithms will be in the noise as far
as compile-time performance is concerned.
> I don't know of any implementation of L/T in a compiler (but this means
> nothing). I once read about L/T used for comparing dominance algorithms in
> a summer student project (but without any source) ;) The other optimizing
> compilers I have the source (trimaran project and suif) use the naive
> implementation. So, I'm not too sure of real world implementations of
Intel's compilers are known to use L/T. The impression I've gotten from
my readings and talking to people is that most do L/T
A quote from David Chase (who has done real world compiler work):
> Aaron Leon Kaplan wrote:
> > 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 would be very interested in the
> > exchange of ideas.
> To the best of my knowledge, nobody has implemented this algorithm.
> If I recall, some years ago, Michael Wolf(e?) (the older one, who did
> not work with Monica Lam at Stanford) stood up at a PLDI conference
> and asked if anyone in the audience had implemented it, and not one
> person had.
> In practice, I think most people use the O(n log n) Tarjan and Lengauer
> algorithm. I implemented the faster one once O(n inverse-Ackerman(n));
> I recall that the journal article describing it contains a typo. I
> also recall that a friend of mine laughed at me for going to all the
> trouble, since log N grows slowly enough, and the nlogn algorithm is
And Michael Wolfe responding to the same question from Aaron:
> 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,
And someone that tried to implement the Harel algorithm:
> 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.
> 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).
And from one of my texts:
"It is common to use this algorithm [L/T] while mentioning the existence
Harel 1985) of a more complicated linear-time algorithm".
The point being that when folks who write compilers for a living talk
about dominators, they tend to lean towards L/T, even with its limitations.
One of the significant problems with GCC is that it (in many places) does
not use well-understood algorithms, which makes it difficult for people
who do compilers for a living to understand (and ultimately contribute) to
> > generally prefer basing GCC on algorithsm that are widely
> > used/understood than those which are relatively obscure.
> Did you read Lengauer's and Tarjan's original paper? I don't find it very
> clear ;)
No, but I have read its description in a few. It seems to me it's relatively
easy to implement if you don't use re-balancing. That gives you nlogn.
Re-balancing gives you better behavior than nlogn, but not linear.
> > The algorithm you're implementing is, err, highly complex
> ;-) Not as complex as reload I believe. (btw. are there any plans to
> replace it with a colorizing allocator?)
True. There are few things in the compiler as complex as reload, of course
we're in the process of revamping reload to make it simpler.
Moving to a graph coloring allocator is not currently an option due to
> Just ask. After some thinking I was fairly happy about the cleanlyness of
> the algorithm itself. If you take away the microtree stuff, what remains
> is to partition the DFS tree into disjoint structures, then joining them
> all together again, and when doing that to collect knowledge (about
> dominance) wandering from the small parts to the larger ones, until the
> DFS tree is complete again.
I'll try it again ignoring the micro-tree stuff.
More information about the Gcc-patches