[LLVMdev] Re: [open-analysis] Alias Analysis Design & Implementation and LLVM

[Chris Lattner]

On Thu, 6 Nov 2003, Michelle Strout wrote:

> Those of us working on the OpenAnalysis project have been looking at
> LLVM recently (excellent job on the website BTW).

Thanks!  I'm just one of the many people who have worked on it though, the
praise belongs to them as much as it does to me.  :)

> This includes researchers at Rice, Argonne, and LLNL.

Great!

> John Mellor-Crummey has discussed the possibility of us incorporating
> parts of LLVM into OpenAnalysis.  For now, we have some specific
> questions about LLVM.

>>> -  LLVM is in SSA.  It is in SSA before alias analysis has been
>>> performed.  With OA, it has been mentioned that the  SSA generation is
>>> incorrect because it doesn't take alias analysis information into
>>> account.  This seems logical, because the definition of SSA requires
>>> that each variable use only has one definition point.  Is the LLVM in
>>> fact not in legal SSA?

While an SSA form, LLVM does not use SSA for memory locations, only
scalar.  This gives us some very nice properties: for example the C/C++
front-end does not have an "SSA construction pass", instead all automatic
variables live on the stack (in memory) and are accessed via loads &
stores.  As such, no values are live across basic blocks, and there are no
PHI nodes in the C frontend output (making the C frontend easier to
implement).

Later, the LLVM optimizer promotes all of these memory references to SSA
values, using well known optimization techniques.  In particular, the
mem2reg pass implements the well known Cytron et al SSA construction
algorithm.

The advantage of this is that there is only _one_ representation for code
throughout the optimizer, so alias analyses can be run whenever they want
to be (though they are obviously most effective after the gross
inefficiencies have been eliminated from the code).

If you want more details than this, or if my explanation is confusing,
please let me know.

> - Is there a dataflow analysis framework in LLVM?

No there isn't (intentionally).  All of the optimizations in LLVM are
sparse optimizations implemented without traditional dataflow analysis.
The one exception to this is the live variable analysis implemented in the
Sparc backend, which will eventually be unified with the sparse
live-variable analysis in the X86 backend and be eliminated.

Because of this, there was no need to implement a dataflow framework,
though doing so would not be hard.  However, I'm not aware of any analysis
which requires traditional dataflow, or that cannot be implemented more
efficiently in SSA form.  If you are aware of one, please let me know.  :)

> Notice that this email has been CCed to the OpenAnalysis mailing list.

I also CC'd the llvmdev list.  Please let me know if you have any other
questions!

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/