[LLVMdev] dominance frontiers

[Chris Lattner]

On Dec 23, 2011, at 5:48 PM, Preston Briggs wrote:
> 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.

Ok.  Having worked in similar spaces (and caring about compile time :), I've quickly given up on approaches like that.  Instead, I've found that lazy approaches (e.g. what is done in the "memory dependence analysis" pass) work better, because you burn compile time only when a client is making queries (instead of eagerly analyzing every possible alias relation).  YMMV of course.

>  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.

Ok, in that case, please check out include/llvm/Transforms/Utils/SSAUpdater.h, which is the preferred API (that doesn't use dom frontiers) to build SSA.

> 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?

Admittedly, our implementation is brutally inefficient :).  That said, dom frontiers are another great example of a non-lazy data  structure that you have to fully compute even if you end up not using it - and I'd much rather rip it out of LLVM than fix it.

In my experience, there are better ways to solve problems that are traditionally formulated in terms of it.  That said, my experience is limited to the domains that are already implemented in LLVM, so if you're trying to do something new... then that experience may not be very useful :)

-Chris