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

[Michelle Strout]

Chris,

I think some clarifications and examples would be helpful.

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

Scalar variables still have a stack location associated with them, 
don't they?

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

I think an example would help here.  I am going to start one to expose 
my confusion and then you can fix it and enlighten all of us. =)

source code:
a  = b + c
if (z) then
     a = 10
else
     *p = 20
endif
print a

LLVM created by frontend (keep in mind I am unfamiliar with LLVM 
syntax, just doing something like 3-address code):
ld b, r1
ld c, r2
add r1,r2,r3
st r3,a
ld z
bne z,else
st 10,a
ba endif
else:
ld p, r1
st 20, (r1)  // store 20 to storage location referenced by address in r1
endif:
ld a,r1
print r1

LLVM after the LLVM optimizer turns things into SSA:
- Do you get rid of the loads and stores?
- In SSA there should be a phi node for a after the if statement.  From 
looking at the original code, it seems that the phi statement should 
look like this:
     a_3 = phi(a_1,a_2,(*p_1))
Seems like you need to include something involving *p because it might 
alias the location for a.  How do you handle this?


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

Backward dataflow analyses, like live variable analysis, cannot be 
performed with SSA [Choi91, JohnsonPingali93].  Attached to this email 
is an example (color pdf) that illustrates why.

Do you convert from SSA back to a non-SSA LLVM to do the live-variable 
analysis that you have implemented in the backends?

At Argonne one of the application specific analyses we need to perform, 
activity analysis, has a forward and backward dataflow analysis 
component.

Thanks,
Michelle


@inproceedings{Choi91,
	Author = {Jong-Deok Choi and Ron Cytron and Jeanne Ferrante},
	Booktitle = {Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on 
Principles of programming languages},
	Location = {Orlando, Florida, United States},
	Pages = {55--66},
	Publisher = {ACM Press},
	Title = {Automatic construction of sparse data flow evaluation graphs},
	Year = {1991}}

@inproceedings{JohnsonPingali93,
	Author = {Richard Johnson and Keshav Pingali},
	Booktitle = {Proceedings of the ACM SIGPLAN 1993 conference on 
Programming language design and implementation},
	Location = {Albuquerque, New Mexico, United States},
	Pages = {78--89},
	Publisher = {ACM Press},
	Title = {Dependence-based program analysis},
	Year = {1993}}

-------------- next part --------------
A non-text attachment was scrubbed...
Name: SSA-backward-dataflow.pdf
Type: application/pdf
Size: 22111 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20031106/0f594314/attachment.pdf>
-------------- next part --------------

=======================================
  Michelle Mills Strout, Ph.D.
  Argonne National Laboratory, MCS Division
  9700 S. Cass Avenue, Bldg 221, Rm D243
  Argonne, IL  60439-4844

  http://www.mcs.anl.gov/~mstrout
  mstrout at mcs.anl.gov
=======================================