several messages

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
  > L/T.
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
  > simpler.

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
patent issues.

  > 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 mailing list