AliasAnalysis: Be less conservative about volatile than atomic.

[• dberlin]

Summary

getModRefInfo is meant to answer the question "what impact does this
instruction have on a given memory location" (not even another
instruction).

Long debate on this on IRC comes to the conclusion the answer should be "nothing special".

That is, a noalias volatile store does not affect a memory location
just by being volatile. Note: DSE and GVN and memdep currently
believe this, because memdep just goes behind AA's back after it says
"modref" right now.

see line 635 of memdep. Prior to this patch we would get modref there, then check aliasing,
and if it said noalias, we would continue.

getModRefInfo *already* has this same AA check, it just wasn't being used because volatile was
lumped in with ordering.

(I am separately testing whether this code in memdep is now dead except for the invariant load case)

[• dberlin]

• Update patch for now-passing newgvn test

[• dberlin]

• Fix spurious whitespace change

[sanjoy]

lib/Analysis/AliasAnalysis.cpp

336 ↗

(On Diff #94285)

Why not isStrongerThan(L->getOrdering(), AtomicOrdering::Unordered)? (same below)

OTOH I'm surprised that this did not break any tests.

[• dberlin]

lib/Analysis/AliasAnalysis.cpp

336 ↗

(On Diff #94285)

Honestly:
Because i don't know enough to know if that's okay ;)
If it is, happy to do it.

It breaks 1 optimizations test that i'm looking at:

memcpy/atomic.ll optimizes *less* now.
Which makes no sense at all. I suspect it was relying on weird aliasing before. I'm debugging.

Otherwise, it does break some memoryssa tests, which i'm updating for the correct answers.
(i'm also still awaiting 3 stage results on linux)

[• dberlin]

lib/Analysis/AliasAnalysis.cpp

336 ↗

(On Diff #94285)

Actually the memcpyopt is exactly the issue you point out, so fixing as part of test updates.

[sanjoy]

lib/Analysis/AliasAnalysis.cpp

336 ↗

(On Diff #94285)

I think it is, but (more importantly) wasn't that the behavior before?

Previously if L was non-volatile AND (NotAtomic or Unordered) then we'd go through the normal alias analysis codepath.

Now you want to remove the "non-volatile AND" bit. This would mean we'd want to go through the normal path if the load was NotAtomic or Unordered.

[• dberlin]

lib/Analysis/AliasAnalysis.cpp

336 ↗

(On Diff #94285)

Yes, you are correct., fixed.

[• dberlin]

• Update to be stronger than Unordered, update all tests for fact that volatile loads are no longer modref.

[• dberlin]

test/Transforms/Util/MemorySSA/volatile-clobber.ll

27 ↗

(On Diff #94296)

Note: we could leave them (volatile loads) as defs if we wanted by overriding getModRefInfo, but this is also consistent with what we do for other cases.

(if we left them as defs, they would link together all volatile loads and stores, everything else would bypass them.

[chandlerc]

test/Transforms/Util/MemorySSA/volatile-clobber.ll

27 ↗

(On Diff #94296)

I think volatile loads should be defs for other volatile loads, even if the two pointers are known to not alias. I'm not sure how to express this though.

[• dberlin]

test/Transforms/Util/MemorySSA/volatile-clobber.ll

27 ↗

(On Diff #94296)

Note:

MemorySSA does not pretend in any way to represent ordering constraints (it can't sanely do so as part of the default chain without losing optimization).
That said what you want is certainly possible, it just adds extra phis, extra defs, extra things that every other load must bypass or prove equal.

What you'd actually get would be stores + volatile loads as defs.

IE a volatile load would be a def for a regular store as well.

Calling getclobberingaccess on the store would give a correct answer, but costs something.

So we could do it as part of the default chain of course. Like i said, it just blocks optimization. It also tends to confuse things, as there is a real difference between "does this write or read the same memory as that" and "can i reorder these two memory operations".

Memdep tries to return clobbers to let things handle the second case, but it misses cases.

So if your goal is to be able to find the next volatile load, from a volatile load, for reordering, we should just add that, but my inclination (without data) would *not* try to make them defs. Because they aren't defs. They are uses. Just ordered ones :)

(Note, of course, atomics that same visible effect as writing memory are already defs and stay defs no matter what we do)

There are a couple ways to go about representing the ordering constraint:

Add an orderedmemoryuse/def, use it for them, it has an extra operand representing the ordering chain (IE the next thing that it can't be move above)

This would require orderedmemoryphis for that chain, but honestly, 99% of the cost of memoryssa is the use optimization and aliasing, not the initial chain building. Since the the ordering rules themselves are not anywhere as expensive as aliasing, ....

So i'd expect this to cost nearly nothing, but be completely precise for loads (We already know what the next thing that *reads or writes that memory* is, and can combine with that to give precise answers).

The downside is you have two chains. But that basically amounts to: If you use the default chain, you don't touch ordered operations (IE try to replace them).
If you use both chains at once, you get precise answers about both properties.

Of course, just a thought.
I haven't tried it in practice yet :)

(any happy to make volatiles defs against other volatiles in the meanwhile if we like)

[• dberlin]

• Make volatiles defs again

[• dberlin]

I"ve now three staged this on darwin and linux with no regressions.

[hfinkel]

lib/Analysis/AliasAnalysis.cpp

336 ↗

(On Diff #94312)

Can you please make sure this part of the AA interface contract is now documented in the header file.

lib/Transforms/Utils/MemorySSA.cpp

1468 ↗

(On Diff #94312)

Can you add a comment somewhere that we don't need to check atomicrmw or cmpxchg because they're not allowed to have an ordering less than relaxed. The LangRef says so, but I think it is worth noting why these are the only two things you need to check here because the others should always get a ModRef return from AA.

[• dberlin]

lib/Analysis/AliasAnalysis.cpp

336 ↗

(On Diff #94312)

Gave it a shot.

lib/Transforms/Utils/MemorySSA.cpp

1468 ↗

(On Diff #94312)

Did this an then tried to explain why we do it for the moment.

[• dberlin]

• Update for comments

[• dberlin]

• This time check it into the right tree

[• dberlin]

include/llvm/Analysis/AliasAnalysis.h

534 ↗

(On Diff #94414)

I already fixed the double->triple slash :)

[hfinkel]

LGTM

include/llvm/Analysis/AliasAnalysis.h

530 ↗

(On Diff #94414)

reordere -> reordered

The volatile load also can't be removed.

llvm/trunk/include/llvm/Analysis/AliasAnalysis.h

ModRefInfo getModRefInfo(const Instruction *I) {
     }
 
     return getModRefInfo(I, MemoryLocation());
   }
 
   /// Check whether or not an instruction may read or write the specified
   /// memory location.
   ///
+  /// Note explicitly that getModRefInfo considers the effects of reading and
+  /// writing the memory location, and not the effect of ordering relative to
+  /// other instructions.  Thus, a volatile load is considered to be Ref,
+  /// because it does not actually write memory, it just can't be reordered
+  /// relative to other volatiles (or removed).  Atomic ordered loads/stores are
+  /// considered ModRef ATM because conservatively, the visible effect appears
+  /// as if memory was written, not just an ordering constraint.
+  ///
   /// An instruction that doesn't read or write memory may be trivially LICM'd
   /// for example.
   ///
   /// This primarily delegates to specific helpers above.
   ModRefInfo getModRefInfo(const Instruction *I, const MemoryLocation &Loc) {
     switch (I->getOpcode()) {
     case Instruction::VAArg:  return getModRefInfo((const VAArgInst*)I, Loc);
     case Instruction::Load:   return getModRefInfo((const LoadInst*)I,  Loc);

llvm/trunk/lib/Analysis/AliasAnalysis.cpp

 }
 
 //===----------------------------------------------------------------------===//
 // Helper method implementation
 //===----------------------------------------------------------------------===//
 
 ModRefInfo AAResults::getModRefInfo(const LoadInst *L,
                                     const MemoryLocation &Loc) {
-  // Be conservative in the face of volatile/atomic.
-  if (!L->isUnordered())
+  // Be conservative in the face of atomic.
+  if (isStrongerThan(L->getOrdering(), AtomicOrdering::Unordered))
     return MRI_ModRef;
 
   // If the load address doesn't alias the given address, it doesn't read
   // or write the specified memory.
   if (Loc.Ptr && !alias(MemoryLocation::get(L), Loc))
     return MRI_NoModRef;
 
   // Otherwise, a load just reads.
   return MRI_Ref;
 }
 
 ModRefInfo AAResults::getModRefInfo(const StoreInst *S,
                                     const MemoryLocation &Loc) {
-  // Be conservative in the face of volatile/atomic.
-  if (!S->isUnordered())
+  // Be conservative in the face of atomic.
+  if (isStrongerThan(S->getOrdering(), AtomicOrdering::Unordered))
     return MRI_ModRef;
 
   if (Loc.Ptr) {
     // If the store address cannot alias the pointer in question, then the
     // specified memory cannot be modified by the store.
     if (!alias(MemoryLocation::get(S), Loc))
       return MRI_NoModRef;
 

llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp

void swap(RenamePassData &RHS) {
     std::swap(DTN, RHS.DTN);
     std::swap(ChildIt, RHS.ChildIt);
     std::swap(IncomingVal, RHS.IncomingVal);
   }
 };
 } // anonymous namespace
 
 namespace llvm {
-/// \brief A MemorySSAWalker that does AA walks to disambiguate accesses. It no longer does caching on its own,
+/// \brief A MemorySSAWalker that does AA walks to disambiguate accesses. It no
+/// longer does caching on its own,
 /// but the name has been retained for the moment.
 class MemorySSA::CachingWalker final : public MemorySSAWalker {
   ClobberWalker Walker;
   bool AutoResetWalker;
 
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, UpwardsMemoryQuery &);
   void verifyRemoved(MemoryAccess *);
 
MemoryUseOrDef *MemorySSA::createDefinedAccess(Instruction *I,
   MemoryUseOrDef *NewAccess = createNewAccess(I);
   assert(
       NewAccess != nullptr &&
       "Tried to create a memory access for a non-memory touching instruction");
   NewAccess->setDefiningAccess(Definition);
   return NewAccess;
 }
 
+// Return true if the instruction has ordering constraints.
+// Note specifically that this only considers stores and loads
+// because others are still considered ModRef by getModRefInfo.
+static inline bool isOrdered(const Instruction *I) {
+  if (auto *SI = dyn_cast<StoreInst>(I)) {
+    if (!SI->isUnordered())
+      return true;
+  } else if (auto *LI = dyn_cast<LoadInst>(I)) {
+    if (!LI->isUnordered())
+      return true;
+  }
+  return false;
+}
 /// \brief Helper function to create new memory accesses
 MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I) {
   // The assume intrinsic has a control dependency which we model by claiming
   // that it writes arbitrarily. Ignore that fake memory dependency here.
   // FIXME: Replace this special casing with a more accurate modelling of
   // assume's control dependency.
   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
     if (II->getIntrinsicID() == Intrinsic::assume)
       return nullptr;
 
   // Find out what affect this instruction has on memory.
   ModRefInfo ModRef = AA->getModRefInfo(I);
-  bool Def = bool(ModRef & MRI_Mod);
+  // The isOrdered check is used to ensure that volatiles end up as defs
+  // (atomics end up as ModRef right now anyway).  Until we separate the
+  // ordering chain from the memory chain, this enables people to see at least
+  // some relative ordering to volatiles.  Note that getClobberingMemoryAccess
+  // will still give an answer that bypasses other volatile loads.  TODO:
+  // Separate memory aliasing and ordering into two different chains so that we
+  // can precisely represent both "what memory will this read/write/is clobbered
+  // by" and "what instructions can I move this past".
+  bool Def = bool(ModRef & MRI_Mod) || isOrdered(I);
   bool Use = bool(ModRef & MRI_Ref);
 
   // It's possible for an instruction to not modify memory at all. During
   // construction, we ignore them.
   if (!Def && !Use)
     return nullptr;
 
   assert((Def || Use) &&

llvm/trunk/test/Transforms/NewGVN/volatile-nonvolatile.ll

-; XFAIL: *
 ; RUN: opt -tbaa -newgvn -S < %s | FileCheck %s
 
 %struct.t = type { i32* }
 
 ; The loaded address and the location of the address itself are not aliased,
 ; so the second reload is not necessary. Check that it can be eliminated.
 ; CHECK-LABEL: test1
 ; CHECK: load