[MemorySSA] Allow reordering of loads that alias in the presence of volatile loads.

[asbirlea]

Summary

Make MemorySSA allow reordering of two loads that may alias, when one is volatile.
This makes MemorySSA less conservative and behaving the same as the AliasSetTracker.
For more context, see D16875.

LLVM language reference: "The optimizers must not change the number of volatile operations or change their order of execution relative to other volatile operations. The optimizers may change the order of volatile operations relative to non-volatile operations. This is not Java’s “volatile” and has no cross-thread synchronization behavior."

[george.burgess.iv]

Thanks for this! Just a few nitpicks.

I think this is the right way forward, though please wait until tomorrow to land this change, so people have the chance to chime in if they'd like to.

lib/Analysis/MemorySSA.cpp

213

Since this code is pretty subtle, can we keep a comment here saying something like "Otherwise, volatile doesn't matter here. From the langref: 'optimizers may change the order of volatile operations relative to non-volatile operations.'"?

225

Can we simplify this to return !(SeqCstUse || MayClobberIsAcquire) (or the !A && !B equivalent; whatever you feel is cleaner)?

257–258

Remove these braces, too, please.

[asbirlea]

Address comments.

Thank you for the review!

lib/Analysis/MemorySSA.cpp

return hash_combine(
         MLOC.IsCall, DenseMapInfo<MemoryLocation>::getHashValue(MLOC.getLoc()));
   }
 
   static bool isEqual(const MemoryLocOrCall &LHS, const MemoryLocOrCall &RHS) {
     return LHS == RHS;
   }
 };
 
-enum class Reorderability { Always, IfNoAlias, Never };
-
 } // end namespace llvm
 
 /// This does one-way checks to see if Use could theoretically be hoisted above
 /// MayClobber. This will not check the other way around.
 ///
 /// This assumes that, for the purposes of MemorySSA, Use comes directly after
 /// MayClobber, with no potentially clobbering operations in between them.
 /// (Where potentially clobbering ops are memory barriers, aliased stores, etc.)
-static Reorderability getLoadReorderability(const LoadInst *Use,
-                                            const LoadInst *MayClobber) {
+static bool areLoadsReorderable(const LoadInst *Use,
   bool VolatileUse = Use->isVolatile();
   bool VolatileClobber = MayClobber->isVolatile();
   // Volatile operations may never be reordered with other volatile operations.
   if (VolatileUse && VolatileClobber)
-    return Reorderability::Never;
-
-  // The lang ref allows reordering of volatile and non-volatile operations.
-  // Whether an aliasing nonvolatile load and volatile load can be reordered,
-  // though, is ambiguous. Because it may not be best to exploit this ambiguity,
-  // we only allow volatile/non-volatile reordering if the volatile and
-  // non-volatile operations don't alias.
-  Reorderability Result = VolatileUse || VolatileClobber
-                              ? Reorderability::IfNoAlias
-                              : Reorderability::Always;
+    return false;
+  // Otherwise, volatile doesn't matter here. From the language reference:
+  // 'optimizers may change the order of volatile operations relative to
+  // non-volatile operations.'"
 
   // If a load is seq_cst, it cannot be moved above other loads. If its ordering
   // is weaker, it can be moved above other loads. We just need to be sure that
   // MayClobber isn't an acquire load, because loads can't be moved above
   // acquire loads.
   //
   // Note that this explicitly *does* allow the free reordering of monotonic (or
   // weaker) loads of the same address.
   bool SeqCstUse = Use->getOrdering() == AtomicOrdering::SequentiallyConsistent;
   bool MayClobberIsAcquire = isAtLeastOrStrongerThan(MayClobber->getOrdering(),
                                                      AtomicOrdering::Acquire);
-  if (SeqCstUse || MayClobberIsAcquire)
-    return Reorderability::Never;
-  return Result;
+  return !(SeqCstUse || MayClobberIsAcquire);
 }
 
 static bool instructionClobbersQuery(MemoryDef *MD,
                                      const MemoryLocation &UseLoc,
                                      const Instruction *UseInst,
                                      AliasAnalysis &AA) {
   Instruction *DefInst = MD->getMemoryInst();
   assert(DefInst && "Defining instruction not actually an instruction");
   ImmutableCallSite UseCS(UseInst);
default:
       break;
     }
   }
 
   if (UseCS) {
     ModRefInfo I = AA.getModRefInfo(DefInst, UseCS);
     return isModOrRefSet(I);
   }
 
-  if (auto *DefLoad = dyn_cast<LoadInst>(DefInst)) {
-    if (auto *UseLoad = dyn_cast<LoadInst>(UseInst)) {
-      switch (getLoadReorderability(UseLoad, DefLoad)) {
-      case Reorderability::Always:
-        return false;
-      case Reorderability::Never:
-        return true;
-      case Reorderability::IfNoAlias:
-        return !AA.isNoAlias(UseLoc, MemoryLocation::get(DefLoad));
-      }
-    }
-  }
+  if (auto *DefLoad = dyn_cast<LoadInst>(DefInst))
+    if (auto *UseLoad = dyn_cast<LoadInst>(UseInst))
+      return !areLoadsReorderable(UseLoad, DefLoad);
 
   return isModSet(AA.getModRefInfo(DefInst, UseLoc));
 }
 
 static bool instructionClobbersQuery(MemoryDef *MD, const MemoryUseOrDef *MU,
                                      const MemoryLocOrCall &UseMLOC,
                                      AliasAnalysis &AA) {
   // FIXME: This is a temporary hack to allow a single instructionClobbersQuery

test/Analysis/MemorySSA/volatile-clobber.ll

; CHECK-NEXT: %2 = load volatile i32
   %2 = load volatile i32, i32* %1, align 4
 ; CHECK: 4 = MemoryDef(3)
 ; CHECK-NEXT: %3 = load volatile i32
   %3 = load volatile i32, i32* %1, align 4
   %4 = add i32 %3, %2
   ret i32 %4
 }
 
-; Ensuring that we don't automatically hoist nonvolatile loads around volatile
-; loads
+; Ensuring we allow hoisting nonvolatile loads around volatile loads.
 ; CHECK-LABEL define void @volatile_only
 define void @volatile_only(i32* %arg1, i32* %arg2) {
   ; Trivially NoAlias/MustAlias
   %a = alloca i32
   %b = alloca i32
 
 ; CHECK: 1 = MemoryDef(liveOnEntry)
 ; CHECK-NEXT: load volatile i32, i32* %a
   load volatile i32, i32* %a
 ; CHECK: MemoryUse(liveOnEntry)
 ; CHECK-NEXT: load i32, i32* %b
   load i32, i32* %b
-; CHECK: MemoryUse(1)
+; CHECK: MemoryUse(liveOnEntry)
 ; CHECK-NEXT: load i32, i32* %a
   load i32, i32* %a
 
   ; MayAlias
 ; CHECK: 2 = MemoryDef(1)
 ; CHECK-NEXT: load volatile i32, i32* %arg1
   load volatile i32, i32* %arg1
-; CHECK: MemoryUse(2)
+; CHECK: MemoryUse(liveOnEntry)
 ; CHECK-NEXT: load i32, i32* %arg2
   load i32, i32* %arg2
 
   ret void
 }
 
 ; Ensuring that volatile atomic operations work properly.
 ; CHECK-LABEL define void @volatile_atomics

 ; CHECK-NEXT: load atomic volatile i32, i32* %a monotonic, align 4
   load atomic volatile i32, i32* %a monotonic, align 4
 ; CHECK: MemoryUse(1)
 ; CHECK-NEXT: load i32, i32* %b
   load i32, i32* %b
 ; CHECK: MemoryUse(1)
 ; CHECK-NEXT: load atomic i32, i32* %b unordered, align 4
   load atomic i32, i32* %b unordered, align 4
-; CHECK: MemoryUse(2)
+; CHECK: MemoryUse(1)
 ; CHECK-NEXT: load atomic i32, i32* %a unordered, align 4
   load atomic i32, i32* %a unordered, align 4
-; CHECK: MemoryUse(2)
+; CHECK: MemoryUse(1)
 ; CHECK-NEXT: load i32, i32* %a
   load i32, i32* %a
 
   ; MayAlias
 ; CHECK: 3 = MemoryDef(2)
 ; CHECK-NEXT: load atomic volatile i32, i32* %arg1 monotonic, align 4
   load atomic volatile i32, i32* %arg1 monotonic, align 4
-; CHECK: MemoryUse(3)
+; CHECK: MemoryUse(1)
 ; CHECK-NEXT: load i32, i32* %arg2
   load i32, i32* %arg2
 
   ret void
 }