[LLVMdev] "Best" alias analysis algorithm

[Chris Lattner]

On Tue, 26 Apr 2005, Vladimir Prus wrote:
>> to be a very simple mod/ref analysis that does no "pointer analysis" at
>> all.  In particular, it only tracks globals that it knows "never have
>> their address taken".  If a global has non-internal linkage, the compiler
>> can't know that something outside of the program doesn't take its address
>> and pass around its address.
>
> Even if something outside of the current module has the address of the global,
> it cannot modify that global, because the control never leaves the current
> module, no?

In this case, yes, obviously.  ;)  The problem is that the pass does not 
track this possibility.  It is meant to be a very simple and quick pass 
that handles one thing well (non-address taken globals).  For example, in 
this function:


extern int P;
int test(int *Q) { *Q = 1; return P; }

It can't decide whether 'test' could modify P.  In practice, MANY 
trivial cases like this exist where globals mod/ref can't answer, so it 
does not even attempt to track external globals.

If you're interested in this, a more powerful algorithm like DSA should be 
used, or you could build a context-sensitive mod/ref follow-on pass that 
uses a non-context-sensitive alias analysis algorithm (like andersens or 
steensgaards) as its base.

-Chris

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