search for: gwtta04

...nte is somewhat > responsible for both algorithms :P). It is also a lot simpler to > explain, IMHO. There is a followup paper from other authors (including Tarjan himself) that discusses some implementation tricks for the Lengauer-Tarjan algorithm: http://www.cs.princeton.edu/~rwerneck/docs/GWTTA04.pdf They cite personal communication from Keith Cooper that a later more careful implementation of Lengauer-Tarjan led to different benchmark results than what they published. I added those tricks and some others to LLVM's implementation of Lengauer-Tarjan (the simple O(n log n) version) for a...

On Fri, Jan 6, 2012 at 8:17 PM, Chris Lattner <clattner at apple.com> wrote: > > On Jan 6, 2012, at 5:08 PM, Chris Lattner wrote: > >>>> >>>> It's very like SSA construction, but must make provision >>>> testing anti dependences.  I had planned to use dominance frontiers to >>>> guide placement of phi nodes, as usual. >>>

...each P in Predecessors(B) runner = P while runner != idom[B] DF(runner) += B runner = idom[runner] You can see this does a lot less work by skipping a lot of useless nodes, etc. It's also a lot simpler to explain :) > > http://www.cs.princeton.edu/~rwerneck/docs/GWTTA04.pdf > > They cite personal communication from Keith Cooper that a later more careful > implementation of Lengauer-Tarjan led to different benchmark results than > what they published. I added those tricks and some others to LLVM's > implementation of Lengauer-Tarjan (the simple O...