[LLVMdev] TBAA vs !invariant.load metadata semantics

[Andrew Trick]

> On Dec 2, 2014, at 10:02 AM, Philip Reames <listmail at philipreames.com> wrote:
> 
>> 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.  

Here's a hopefully more intuituve example:

%p = <dereferenceable address>
store <value>, %q
if <type check> { // check whether %p is an invariant field
  m1 = load %p, !invariant
  foo(m1)
} else {
  m2 = load %p
  foo(m2)
}

==> LEGAL

%p = <dereferenceable address>
m1 = load %p, !invariant
store <value>, %q
m2 = load %p
if <type check> { // check whether %p is an invariant field
  foo(m1)
} else {
  foo(m2)
}

==> NOT CURRENTLY DONE (and potentially unsafe)

%p = <dereferenceable address>
m1 = load %p, !invariant
store <value>, %q
if <type check> { // check whether %p is an invariant field
  foo(m1)
} else {
  foo(m1)
}

---

In the above example, if the type check fails, then the store to %q may interfere with the load of m2. The final optimization loses the stored value.

The invariance of data independently applies to
(a) the scope over which other stores are guaranteed not to interfere 
(b) the paths in which the invariance holds

Given control proceeds along some path in (b), the invariant load cannot interfere with any store in (a).

Here is the most useful interpretation I can come up with that is also closest to being sound:

The invariant scope (a) includes all stores that may occur after the address becomes dereferencable and before the end of the object lifetime, subject only to existing constraints on code motion. 

The invariant paths are any that include a use-with-side-effect of the loaded value (similar to our poison values).

I don't particularly like this conservative interpretation either. But even being this conservative, we're left an even more fundamtental question: is it valid to use !invariant metadata for any load from an object that doesn't have process lifetime? What prevents an invariant load from sinking below a "free"? i.e. Is this thing really only valid for global constants?

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