[LLVMdev] alias information in codegen

[Chris Lattner]

On Apr 3, 2008, at 1:00 PM, Dan Gohman wrote:
> * BasicAliasAnalysis, the default AliasAnalysis implementation,  
> doesn't
>   understand lowered GEPs, integer arithmetic, or PHIs, and the
>   regular codegen process involves passes that lower GEPs.

Sure.

> One way to solve this is to use a different AliasAnalysis
> implementation.
> I haven't looked at it in detail, but I'd guess that the Andersen's
> pass handles all of these constructs reasonably well. And it has the
> advantage of being much more capable than the BasicAliasAnalysis.

I haven't tried, but I seriously doubt it.  Most AA's specifically  
just look at pointers and interprocedural ones are much more  
interested in this than local ones: this reduces the number of values  
to track, speeding up analysis and reducing memory use.

>
> Another alternative is to develop a SCEV-based alias analysis. The  
> SCEV
> framework currently has the opposite problem; it understands integer
> arithmetic and PHIs quite well, but doesn't currently understand GEPs.
> I know it can be made to understand GEPs though, and it's on my TODO
> list to implement this.

This could be interesting, but you're basically attacking the  
dependence analysis problem here.  Dependence analysis can be used to  
disambiguate pointers (and basicaa does a simple form of this) but  
that is orthogonal to the rest of the problem.

I think it would be better by starting to make LSR just not throw away  
pointer information when it is trivial to preserve it.  This is  
obviously not always the case, but it is VERY VERY VERY often the  
case, so we should see how far that gets us.  If nothing else, it  
makes the IR sent into the codegen simpler and smaller.

> * There are still a variety of places in SelectionDAG creation that
>   don't preserve SVOperand/SVOffset (as well as alignment and
> volatile).
>
> These places need to be found and fixed. This is pretty straight-
> forward,
> and the places that need changing can be found by inserting some
> strategic assert(SVOperand)'s.

This is also a serious issue that can manifest as bugs already, so it  
is a correctness issue, not a performance issue.

>  * The DAGCombiner's alias-analysis handling isn't ideal.
>
> This is the -combiner-alias-analysis and -combiner-global-alias- 
> analysis
> options. They basically work, though they aren't turned on by default
> currently. The algorithm used wants some scrutiny as well.

Yep, it would be very interesting to rewrite the combiner aa stuff to  
be more scalable.  We've seen significant improvements with it, and it  
currently just does trivial base+offset disambiguation.  It would be  
much more interesting to throw full AliasAnalysis info into it. :)

-Chris