[LLVMdev] TBAA vs !invariant.load metadata semantics

[Philip Reames]

On 12/01/2014 06:05 PM, Andrew Trick wrote:
>
>> On Dec 1, 2014, at 3:44 PM, Philip Reames <listmail at philipreames.com 
>> <mailto:listmail at philipreames.com>> wrote:
>>
>> (Spawning a separate subthread off the 'Optimization hints for 
>> "constant" loads' discussion for a related question. )
>>
>> Looking at TBAA again, I was reminded that TBAA also contains a third 
>> field which indicates that "meaning pointsToConstantMemory should 
>> return true; see other useful AliasAnalysis methods 
>> <http://llvm.org/docs/AliasAnalysis.html#OtherItfs>".  Looking at 
>> this a bit, it really seems like this flag has the exact same meaning 
>> as !invariant.load.
>>
>> pointsToConstantMemory returns a value for a Location. Since it is 
>> entirely legal to have two Locations which describe the same physical 
>> memory, it seems like you'd be back to the same semantics as 
>> !invariant.load.
>>
>> The only uncertainty here is that a Location is clearly (??) 
>> position/Instruction specific.  Does that also imply that the 
>> Location is control dependent?  What is the semantics of the 
>> following code?
>> if (is_known_invariant) {
>>   load %p, !tbaa is_constant=true
>> }
>>
>> Is the optimizer allowed to lift the load above the conditional?  
>> (Assuming it can prove the location is known dereferenceable.)  The 
>> semantics for !invariant.load clearly allow this, but do the 
>> semantics for TBAA's constant flag?
>>
>> I think the answer to these questions is that the load is *not* 
>> control dependent on the conditional (assuming it's otherwise known 
>> dereferenceable).  Given this, why do we have both?  Should we 
>> canonicalize one into the other?
>
> It would be very confusing if the two had different semantics.
>
> In either case, hoisting the load (without dropping metadata) is 
> definitely legit.
Agreed up to here.
> But conservatively, the invariance is still a path sensitive property. 
> The load is invariant w.r.t. any store as long as control reaches a 
> use-with-side-effects of the loaded value.
I disagree with this.  The !invariant.load metadata is not a path 
sensitive property.  It is a property of the pointer value which happens 
to be described on the load.  Consider how we use the !invariant.load 
metadata in LICM.  We look at the load (*not* it's uses) and decide to 
skip all remaining alias checks.

To be clear, the preceding statement is not true of llvm.invariant.start 
and llvm.invariant.end.
>
> Given:
>
> store %q
> m1 = load %p
> if <something> {
>  m2 = load %p, !invariant.load
> }
> m = phi(m1, m2)
>
> We can safely convert to:
>
> m2 = load %p, !invariant.load
> store %q
> m1 = load %p
> if <something> {}
> m = phi(m1, m2)
>
> But cannot safely convert to:
>
> m = load %p, !invariant.load
> store %q
>
> I would *really* like to specify more aggressive semantics so that we 
> can do that, but haven’t adequately proved we can do that safely. I’m 
> don’t think the optimizer will do the unsafe thing today, unless 
> there’s an oversight somewhere.
We perform nearly exactly this transformation today.  Consider LICM:
load %p
for(int i = 0; i < 1; i++) {
   store %p
   load %p !invariant.load
}

LICM - in isolation - will transform this to:
load %p
load %p, !invariant.load
for(int i = 0; i < 1; i++) { }
store %p

Can you be more explicit about what you mean by "safely"?  Given the 
semantics I understand for !invariant.load, the transformation you've 
described is entirely legal.  We might not implement it today - I don't 
believe we'd forward the non-invariant load to the invariant load in 
your original example - but that's a limitation of the implementation.


>
>> Looking at the current implementations, it appears that TBAA's 
>> constant flag is more broadly implemented.  On first glance, I'm 
>> really tempted to just deprecate !invariant.load in place of TBAA's 
>> constant flag. Thoughts?
>
> I don’t have a strong opinion here. I’m fine relying on TBAA being 
> enabled to active these sort of optimizations.
I'll throw together a patch in a few days.
>
> -Andy
>
>> Philip
>>
>>
>>
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141202/58ad44c4/attachment.html>