[LLVMdev] dominance frontiers

Cameron Zwarich zwarich at apple.com
Fri Jan 6 21:14:28 PST 2012


On Jan 6, 2012, at 8:27 PM, Daniel Berlin wrote:

> Note: GCC takes exactly the same approach as LLVM here, for exactly
> the reason chris specifies.
> In fact, until we started local SSA updating (which is now many years
> ago, but ...), dominance frontier calculation for ssa updating was in
> the top 10 profile functions for GCC compiles of large source files.
> I had tried a number of the linear time phi placement algorithms
> instead, but sadly, none were fast enough in practice (I believe
> someone later published a paper comparing them all and finding the
> same thing).

I wrote the current implementation of the up-front SSA construction in LLVM, found in Utils/PromoteMemoryToRegister.cpp. It uses a modified version of the Sreedhar-Gao algorithm from "A linear time algorithm for placing phi-nodes". The most interesting modification is that it uses per-variable liveness information to compute pruned SSA by pruning the entire IDF computation, rather than merely pruning the DF -> IDF step like is usually done. I was a bit surprised that it worked so well, given the reputation of the "linear time" algorithms, but it performed the best out of everything I attempted.

> As a completely random aside, the algorithm given in the original
> paper you cited is actually not quite the best way in practice.  It
> performs more comparisons than strictly necessary. When I moved us to
> the algorithm found in http://www.cs.rice.edu/~keith/Embed/dom.pdf,
> Figure 5, it was ~30% faster (AFAIK, Jeanne Ferrante 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 significant performance improvement. I should do a comparison with a careful implementation of the Cooper-Harvey-Kennedy algorithm some day.

Cameron
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120106/de67b49a/attachment.html>


More information about the llvm-dev mailing list