> On Dec 1, 2014, at 3:44 PM, Philip Reames <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. 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. 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.> 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. -Andy> Philip > > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141201/eacd0122/attachment.html>
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>
> 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>