[LLVMdev] dominance frontiers

[Preston Briggs]

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

To do dependence analysis efficiently, we want to avoid testing all
memory references against each other (another O(N^2) proposition). So
we build FUD chains for memory references, guided by the Alias Sets
analysis.  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.

I'm surprised they cause you a space problem. In my experience
(admittedly, long ago), we never noticed a problem.  We certainly had
much less memory available at the time.  Perhaps we could profitably
re-visit how they are represented?

Preston