[LLVMdev] dominance frontiers

[Preston Briggs]

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.

Preston




On Fri, Dec 23, 2011 at 3:53 PM, Chris Lattner <clattner at apple.com> wrote:

>
> On Dec 23, 2011, at 1:35 PM, Preston Briggs wrote:
>
> > Reading the comments in Analysis/DominanceFrontier.h, I see a note that
> the structure is deprecated and we're not to use it for anything new.
> >
> > Has it been replaced with something equally useful, or shall I redo the
> calculation for myself, or ...?
>
> We're hoping to remove them, because they're inherently an N^2 data
> structure and there are usually better ways to do things.  What are you
> trying to do?  SSA construction?
>
> -Chris
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20111224/28f6464d/attachment.html>