[LLVMdev] dominance frontiers

[Daniel Berlin]

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.
>>>
>>> Ok, in that case, please check out include/llvm/Transforms/Utils/SSAUpdater.h,
>>> which is the preferred API (that doesn't use dom frontiers) to build SSA.
>>
>> What approach does it use?  I look at the code, but don't really see
>> an explanation.
>
> Sorry, my reading comprehension skills were low, I thought you were asking about MemDep for some reason.  SSAUpdater uses simple local scans across the CFG, excelling at local updates of values.

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).

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.

Both of these things happened around 2005 (local SSA updating in GCC
and replacement of the dominance frontier algorithm), so things may be
different now.