[LLVMdev] dominance frontiers

[Cameron Zwarich]

On Jan 6, 2012, at 10:40 PM, Daniel Berlin wrote:

> Interesting. Maybe some day i'll give it a try again.
> I swear I had tried this one (I was always a fan of Sreedhar's work),
> however, but it's entirely possible i messed up the implementation :)

One thing I found is that the pruning actually made it faster, even when including the cost of computing per-variable liveness information.

A fun paper with a lot of algorithms (some of them pretty impractical) is "Algorithms for computing the static single assignment form" by Bilardi and Pingali. They have a technique in their paper for caching DFs for an important subset of the nodes in a way that the total DF storage is linear. They claim that this is faster in practice than the fully lazy version of the Sreedhar-Gao algorithm that I modified, but I never implemented this for a comparison.

> Ah, i was referring to the *dominance frontier* computation, not the
> dominator computation.
> If you look, you'll see there is an algorithm in the paper that
> computes dominance frontiers touching only the nodes that are
> *actually in* the dominance frontier :)
> 
> The algorithm in the cytron/et al paper looks like this:
> 
> for each X in a bottom-up traversal of the dominator tree do
>  DF(X) = empty
>  for each Y in Successors(X)
>    if (idom(Y) != X) then DF(X) += Y
>  for each Z in DomChildren(X)
>   for each Y in DF(Z)
>     if (idom(Y) != X then DF(X) += Y
> 
> You can see that this does more comparisons than strictly necessary.
> OTOH, the algorithm by Ferrante that Harvey gives is:
> 
> for each B in all basic blocks
>  if the length of Predecessors(B) >= 2
>    for 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 :)

Ah sorry for the mistake, now your original email makes more sense. This was one of the variants I tested and it was a bit of a speedup over the existing code.

> My only work on LLVM's dominators was when I successfully made a mess
> of the dominator tree implementation in LLVM way back when by using a
> splay-tree structure that stored the sequences, rather than BB's.   It
> is technically faster to update, but in practice wildly complex to
> maintain.
> (See rev 25144)
> :)

How well did your scheme deal with dominator updates after edge deletion? That's the painful part of incremental dominator computation.

Cameron