[LLVMdev] alias information in codegen

[Dan Gohman]

On Thu, April 3, 2008 7:33 pm, Chris Lattner wrote:
> 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.

I just tried it, and it did work. Perhaps this means that the
current -anders-aa pass is doing more work than it should.

>> 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 was thinking of starting with something very simple here: an
AliasAnalysis implementation where alias queries are implemented by
computing a SCEV for each pointer and doing a getMinusSCEV with them.
If the result is a constant, it can be handled. If the result is a
subtraction of two simpler values, they can be handed off to the
next analysis in the chain.

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

I agree this would be useful.

Dan