[LLVMdev] dominance frontiers
preston.briggs at gmail.com
Fri Dec 23 17:48:48 PST 2011
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?
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?
More information about the llvm-dev