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

[Chris Lattner]

On Mon, 10 Nov 2003, Michelle Strout wrote:
> In a sense llvm is doing a simple type of alias analysis when they do
> a mem2reg pass using no other analyses.  It appears that the
> following memory references are assumed to possibly be aliased and
> therefore are not treated as scalar variables (ie. they are always
> loaded
> and stored to memory) in the resulting SSA:
> - global variables
> - fields in a struct allocated with malloc and fields in local structs
> - a dereference of any parameter pointer, *p
> - an array reference whether the array is malloced or local
> - if a local variable has its address taken as parameter to a function,
> it could be aliased and therefore is not treated as a scalar
>      NOTE: p = &A;
>            d = *p + 10;
>      is treated with some implicit copy propagation.

Note that copy propagation in general cannot be disabled in LLVM, this is
not specific to pointers.

> Anyone from the LLVM group should correct me if any of the above
> observations are incorrect or incomplete.

I believe that is a correct assessment of the LLVM mem2reg pass.  Note
that there are several other passes (like -scalarrepl, -licm, "-load-vn
-gcse"), that do more advanced analyses as well, and can more aggressively
transform the program based on alias analysis.

LICM, for example, turns this loop:

  for ( ... )
    *P = *P + ...

into

  tmp = *P;
  for ( ... )
    tmp += ...
  *P = tmp;

when it is safe (a common example of this is when *P is actually a global
variable).

> Upon further consideration, I realized that all of the papers that said
> backward dataflow analysis can not be done with SSA meant "with only
> SSA".  In other words, an algorithm that uses both the CFG and SSA (like
> the live var analysis in LLVM) can do backward dataflow problems.
> Attached to this email is another example of the backward flow problem
> live variable analysis.  This time the SSA graph is shown as well as the
> CFG.  The example shows that constant propagation (a forward analysis)
> can be performed by only traversing the SSA edges, but that live var
> analysis requires the CFG as well.

Ah, that makes perfect sense.  Ok, I see what you mean.  I forgot that
some compilers do not always have a CFG implicitly available.

Just to be perfectly clear with my previous response, there are cases when
solving problems with dense bit-vector dataflow can be faster than using
'sparse' SSA solutions: bit-vectors have a tremendous amount of
parallelism. That said, we do just about everything without dataflow in
LLVM, and it seems to work pretty well so far. *shrug*

-Chris

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