[LLVMdev] dominance frontiers

[Chris Lattner]

On Dec 24, 2011, at 7:48 AM, Preston Briggs wrote:

> Here's how I did things, back when I got to write my own infrastructure.  It's still O(n^2) in the worst case, but much quicker in the expected case.
> 
> Number all the basic blocks, 0 to n-1 and build a vector mapping from integer to block.  Requires O(n) time and space.
> 
> For each block, compute the set containing it's dominance frontier, based on Figure 10 of
> 
> Efficiently Computing Static Single Assignment Form and ...
> Cytron, Ferrante, Rosen, Wegman
> 
> During the calculation, represent the current frontier, DF(X), as suggested in
> 
> An Efficient Representation for Sparse Sets
> Briggs, Torczon
> 
> This lets us add members and clear the set in constant time and allows us to enumerate the members in time proportional to the number of members.  O(n) space.
> 
> Then, having computed the DF for a single block, allocate a vector of the appropriate length and copy the members of the set into the vector.  This requires time and space proportional to the actual size of the DF, typically much smaller than O(n) per block.
> 
> When you're done computing DFs, throw away the big sparse set (you only need one as a workspace) and retain the dense vectors.
> 
> When placing phi nodes, Figure 11 of Cytron, et al., the only use of the DF is to walk over the members in a for loop, and the dense vector is perfect for the occasion.  More general representations waste space.
> 
> So, the only real trick is to change the set representation between the time the DFs are computed and the time they are used.  Some people object to numbering the basic blocks, but I've never understood this objection. I did it often, whenever I needed it; it's not some expensive property that you need to maintain across many phases.

The other major problem that I forgot to mention is the "updating" problem.  If you have many clients that are using DF, then you want anything that changes the CFG to update DF.  This can be non-trivial, and (again) is a waste of time in most cases IMO.

-Chris


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