MemorySSA Optimizations: Patch 1 of N

[george.burgess.iv]

Summary

This patch re-adds two of the optimizations that were taken out of MemorySSA due to sketchiness.

Specifically:

• We now try to take advantage of memory ordering rules on loads before querying AA
• We recognize and appropriately react to invariant loads, and loads that AA can prove point constant memory.

Note that the memory ordering check was strengthened to Monotonic, because that's the equivalent of std::memory_order_relaxed, which guarantees no ordering whatsoever, AFAIK.

Also note that I'm not an expert in memory models. So if anything seems fishy, let me know. :)

[majnemer]

lib/Transforms/Utils/MemorySSA.cpp

980

TODO(username) is more of a Google-ism, I don't think LLVM does this very often.

982–983

Is this clang-format'd?

[george.burgess.iv]

Addressed all feedback + made a comment more concise.

lib/Transforms/Utils/MemorySSA.cpp

980

Works for me! Thanks for the heads up

982–983

It is now :)

[george.burgess.iv]

Ping :)

[george.burgess.iv]

Ping :)

[• dberlin]

I'll look when i'm back from getting married :)

[davidxl]

lib/Transforms/Utils/MemorySSA.cpp

756

Unfinished sentence here.

758

nit: MaybeDef -> MayDef

759

This needs some explanation --> can the alias query be moved here to make this function more general?

769

Move this comment up and combine with the other volatile related comment.

788–789

This does not look correct:

When canUseBeReorderedAboveDef returns false, it is not ok to unconditionally feed it into the AA query -- unless AA query also honors the ordering constraint (I have not checked).

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

17

what is this change about?

42

Is this correct? The atomic load can not be reordered before the previous load with acquire.

45

Is this too conservative?

[george.burgess.iv]

Addressed feedback

lib/Transforms/Utils/MemorySSA.cpp

759

Do you still think this should happen (given my response to your comment below)?

769

I'm assuming you meant just the first sentence -- done. :)

788–789

Looking at the things we query, it seems that AAResults (lib/Analysis/AliasAnalysis.cpp) *always* hands back MRI_ModRef if there's any kind of ordering (including volatile) involved for loads/stores, and will return MRI_ModRef if we hand it an AtomicCmpXchgInst or AtomicRMWInst, with ordering greater than Monotonic. This seems inconsistent, so I've sent out http://reviews.llvm.org/D17631 to see if that's intentional or not.

If said patch goes in, AAResults should always be conservative in the cases that canUseBeReorderedAboveDef says are no bueno.

If you think it would be better, I can try adding a canUseNeverBeReorderedAboveDef function, or I can have canUseBeReorderedAboveDef return an enum of {Never, IfNoAlias, Always}. Entirely up to you. :)

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

17

Random noise. Reverted.

42

I believe it is. Even if the load for %2 was non-atomic, it can't be hoisted above an acquire, because that would break cases like

struct Foo {
  std::atomic<int> a;
  int b;
  Foo(): a(0), b(0) {}
};

Foo f;

void thread1() {
  f.b = 1;
  f.a.store(1, std::memory_order_release);
}

void thread2() {
  if (f.a.load(std::memory_order_acquire)) {
    assert(f.b == 1);
  }
}

Wouldn't it? (specifically, if we allowed this, thread2 would be able to load f.b before f.a)

45

For the same reason as above, I think this is all we can do here.

[davidxl]

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

42

yes -- load acquire prevents all following load/store from being moved above it. The problem is that the memory SSA dump confused me a little:

I thought ID:1 MemoryDef is for the LiveOnEntry -- but actually it is the MemoryDef associated the acquire load.

So indeed this is correct.

45

you are right -- I missread the dump.

[davidxl]

lib/Transforms/Utils/MemorySSA.cpp

752

MaybeDef --> MayDef

759

The problem with the current interface design is that 'false' does not really mean 'false' -- it means either 'don't know yet' or 'no it can not be reordered'. This either leads to redundant check later (if it means 'no') or skipped mistakenly later (if it means 'don't know yet) when the client code does know the difference. Possible solution is to move the check that both accesses are loads outside this function and change the function name to : canLoadsBeSafelyReordered( ...)

if (isLoad(Def) && isLoad(Use))

return canLoadsBeSafetlyReordered();

// Using AA interface to do the check here

...

773

This is too strict.

if (LoadDef->getOrdering() <= Monotonic &&

 LoadUse->getOrdering() <= Monotonic)
return true;

// Check other cases. For instance, non acquire loads before an acquire load can be moved after it.

788–789

yes -- there should be an 'hand shaking' with AA interfaces otherwise you will need to special treatment here for synchronization related accesses before AA query. Add test cases to cover those should be good.

[george.burgess.iv]

Addressed all feedback

lib/Transforms/Utils/MemorySSA.cpp

752

Oops. :)

759

Yeah, I like canLoadsBeReordered better.

773

Nice catch.

788–789

Added check_aa_is_sane (which is really tiny) in atomic-clobber.ll. I think it largely covers the behavior that we need, though.

[george.burgess.iv]

Fix a typo in the tests.

[davidxl]

lib/Transforms/Utils/MemorySSA.cpp

757

The overall structure of the patch looks good -- however this function still needs more scrutiny -- please ping Phillip or Hal for more comments.

[george.burgess.iv]

Ping :)

[george.burgess.iv]

ping :)

[george.burgess.iv]

Ping :)

[george.burgess.iv]

Ping :)

[george.burgess.iv]

So, I bugged Philip at the social, and he said the patch (as it stood) looks good, with a few comments:

1. The LLVM spec is ambiguous about whether we can hoist a non-volatile load above a volatile load when the loads alias. It's probably best not to exploit this ambiguity at the moment by unconditionally allowing the motion of nonvolatile loads above volatile loads (and vice versa).

2. It may be good to make pointsToConstantMemory bit check not succeed if the operation is a volatile access

3. A few style things

Items #3 and #1 have been addressed. #1 required a bit of refactoring of the newly-named getLoadReorderability function, because we now have to care about aliasing in some cases.

Item #2 I've thought about, and I'm no longer sure that I agree. Specifically, I believe that MemorySSA's job is to reason about whether one memory operation can cause another memory operation to produce a different result. If MemorySSA determines that memop A doesn't interfere with memop B, it's the *user's* job to determine where it's actually safe to put memop B. For example, consider:

define void @foo(i8* %a) {
	; 1 = MemoryDef(liveOnEntry)
	store volatile i8 0, i8* %a
	br i1 undef, label %if.then, label %if.end

if.then:
	; 2 = MemoryDef(1)
	load volatile i8, i8* %a
	br i1 label %if.end

if.end:
	ret void
}

...MemorySSA will happily (and correctly) say that the volatile load is clobbered by the volatile store. However, it's clearly incorrect to hoist the volatile load into the entry block here, so passes that use MemorySSA will need to exercise some amount of caution in cases involving volatile ops anyway. For this reason, I think it's fine if we say that loads of constant memory are always live on entry, regardless of whether the load is volatile or not.

[george.burgess.iv]

It may be good to make pointsToConstantMemory bit check not succeed if the operation is a volatile access

Wow, that was phrased poorly.

It may be good to make the pointsToConstantMemory check (line 1122) not succeed if the operation is a volatile access. That's what I meant. :)

lib/Transforms/Utils/MemorySSA.cpp

MemoryAccess *CachingMemorySSAWalker::doCacheLookup(const MemoryAccess *M,
   else
     Result = CachedUpwardsClobberingAccess.lookup({M, Loc});
 
   if (Result)
     ++NumClobberCacheHits;
   return Result;
 }
 
+/// This does one-way checks to see if Use could theoretically be hoisted above
+/// MaybeDef. This will not check the other way around.
+///
+/// This assumes that, for the purposes of MemorySSA, Use comes directly after
+/// MayDef, with no potentially clobbering operations in between them.
+/// (Where potentially clobbering ops are memory barriers, aliased stores, etc.)
+static bool canUseAlwaysBeReorderedAboveDef(const Instruction *Use,
+                                            const Instruction *MayDef) {
+  // We only check for load-load clobbers; everything else is AA's problem. :)
+  if (!isa<LoadInst>(MayDef) || !isa<LoadInst>(Use))
+    return false;
+
+  auto *LoadDef = cast<LoadInst>(MayDef);
+  auto *LoadUse = cast<LoadInst>(Use);
+  // Volatile operations can never be reordered with other volatile operations,
+  // but volatile operations *can* be reordered with non-volatile operations.
+  if (LoadDef->isVolatile() && LoadUse->isVolatile())
+    return false;
+
+  // Volatile ordering and atomic ordering are unrelated, so whether a load is
+  // volatile or not is now entirely irrelevant. Also, it's fine to reorder two
+  // monotonic (read: std::memory_order_relaxed) loads, even if they alias.
+  return LoadDef->getOrdering() <= Monotonic &&
+         LoadUse->getOrdering() <= Monotonic;
+}
+
 bool CachingMemorySSAWalker::instructionClobbersQuery(
     const MemoryDef *MD, UpwardsMemoryQuery &Q,
     const MemoryLocation &Loc) const {
   Instruction *DefMemoryInst = MD->getMemoryInst();
   assert(DefMemoryInst && "Defining instruction not actually an instruction");
 
-  if (!Q.IsCall)
+  if (!Q.IsCall) {
+    // If two memory operations can be reordered, then they can't clobber each
+    // other.
+    if (canUseAlwaysBeReorderedAboveDef(Q.Inst, DefMemoryInst))
+      return false;
     return AA->getModRefInfo(DefMemoryInst, Loc) & MRI_Mod;
+  }
 
   // If this is a call, mark it for caching
   if (ImmutableCallSite(DefMemoryInst))
     Q.VisitedCalls.insert(MD);
   ModRefInfo I = AA->getModRefInfo(DefMemoryInst, ImmutableCallSite(Q.Inst));
   return I != MRI_NoModRef;
 }
 
CachingMemorySSAWalker::getClobberingMemoryAccess(const Instruction *I) {
   Q.IsCall = bool(ImmutableCallSite(I));
   if (!Q.IsCall)
     Q.StartingLoc = MemoryLocation::get(I);
   Q.Inst = I;
   Q.DL = &Q.Inst->getModule()->getDataLayout();
   if (auto CacheResult = doCacheLookup(StartingAccess, Q, Q.StartingLoc))
     return CacheResult;
 
+  // If the memory can't be changed, then loads of the memory can't be
+  // clobbered.
+  //
+  // FIXME: We should handle invariant groups, as well. It's a bit harder,
+  // because we need to pay close attention to invariant group barriers.
+  if (isa<LoadInst>(I) && (I->getMetadata(LLVMContext::MD_invariant_load) ||
+                           AA->pointsToConstantMemory(I))) {
+    doCacheInsert(StartingAccess, MSSA->getLiveOnEntryDef(), Q, Q.StartingLoc);
+    return MSSA->getLiveOnEntryDef();
+  }
+
   // Start with the thing we already think clobbers this location
   MemoryAccess *DefiningAccess = StartingAccess->getDefiningAccess();
 
   // At this point, DefiningAccess may be the live on entry def.
   // If it is, we will not get a better result.
   if (MSSA->isLiveOnEntryDef(DefiningAccess))
     return DefiningAccess;
 

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

 ; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
 ;
 ; Ensures that atomic loads count as MemoryDefs
 
+; CHECK-LABEL: define i32 @foo
 define i32 @foo(i32* %a, i32* %b) {
 ; CHECK: 1 = MemoryDef(liveOnEntry)
 ; CHECK-NEXT: store i32 4
   store i32 4, i32* %a, align 4
 ; CHECK: 2 = MemoryDef(1)
 ; CHECK-NEXT: %1 = load atomic i32
   %1 = load atomic i32, i32* %b acquire, align 4
 ; CHECK: MemoryUse(2)
 ; CHECK-NEXT: %2 = load i32
   %2 = load i32, i32* %a, align 4
   %3 = add i32 %1, %2
   ret i32 %3
 }
+
+; CHECK-LABEL: define void @bar
+define void @bar(i32* %a) {
+; CHECK: MemoryUse(liveOnEntry)
+; CHECK-NEXT: %1 = load atomic i32
+  %1 = load atomic i32, i32* %a unordered, align 4
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: %2 = load atomic i32
+  %2 = load atomic i32, i32* %a monotonic, align 4
+; CHECK: 2 = MemoryDef(1)
+; CHECK-NEXT: %3 = load atomic i32
+  %3 = load atomic i32, i32* %a acquire, align 4
+; CHECK: 3 = MemoryDef(2)
+; CHECK-NEXT: %4 = load atomic i32
+  %4 = load atomic i32, i32* %a seq_cst, align 4
+  ret void
+}
+
+; CHECK-LABEL: define void @baz
+define void @baz(i32* %a) {
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: %1 = load atomic i32
+  %1 = load atomic i32, i32* %a acquire, align 4
+; CHECK: MemoryUse(1)
+; CHECK-NEXT: %2 = load atomic i32
+  %2 = load atomic i32, i32* %a unordered, align 4
+; CHECK: 2 = MemoryDef(1)
+; CHECK-NEXT: %3 = load atomic i32
+  %3 = load atomic i32, i32* %a monotonic, align 4
+  ret void
+}
+
+; CHECK-LABEL: define void @fences
+define void @fences(i32* %a) {
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: fence acquire
+  fence acquire
+; CHECK: MemoryUse(1)
+; CHECK-NEXT: %1 = load i32
+  %1 = load i32, i32* %a
+
+; CHECK: 2 = MemoryDef(1)
+; CHECK-NEXT: fence release
+  fence release
+; CHECK: MemoryUse(2)
+; CHECK-NEXT: %2 = load i32
+  %2 = load i32, i32* %a
+
+; CHECK: 3 = MemoryDef(2)
+; CHECK-NEXT: fence acq_rel
+  fence acq_rel
+; CHECK: MemoryUse(3)
+; CHECK-NEXT: %3 = load i32
+  %3 = load i32, i32* %a
+
+; CHECK: 4 = MemoryDef(3)
+; CHECK-NEXT: fence seq_cst
+  fence seq_cst
+; CHECK: MemoryUse(4)
+; CHECK-NEXT: %4 = load i32
+  %4 = load i32, i32* %a
+  ret void
+}

test/Transforms/Util/MemorySSA/constant-memory.ll

+; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
+;
+; Things that BasicAA can prove points to constant memory should be
+; liveOnEntry, as well.
+
+declare void @clobberAllTheThings()
+
+@str = private unnamed_addr constant [2 x i8] c"hi"
+
+define i8 @foo() {
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: call void @clobberAllTheThings()
+  call void @clobberAllTheThings()
+  %1 = getelementptr [2 x i8], [2 x i8]* @str, i64 0, i64 0
+; CHECK: MemoryUse(liveOnEntry)
+; CHECK-NEXT: %2 = load i8
+  %2 = load i8, i8* %1, align 1
+  %3 = getelementptr [2 x i8], [2 x i8]* @str, i64 0, i64 1
+; CHECK: MemoryUse(liveOnEntry)
+; CHECK-NEXT: %4 = load i8
+  %4 = load i8, i8* %3, align 1
+  %5 = add i8 %2, %4
+  ret i8 %5
+}
+
+define i8 @select(i1 %b) {
+  %1 = alloca i8, align 1
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: store i8 0
+  store i8 0, i8* %1, align 1
+
+; CHECK: 2 = MemoryDef(1)
+; CHECK-NEXT: call void @clobberAllTheThings()
+  call void @clobberAllTheThings()
+  %2 = getelementptr [2 x i8], [2 x i8]* @str, i64 0, i64 0
+  %3 = select i1 %b, i8* %2, i8* %1
+; CHECK: MemoryUse(2)
+; CHECK-NEXT: %4 = load i8
+  %4 = load i8, i8* %3, align 1
+  ret i8 %4
+}

test/Transforms/Util/MemorySSA/invariant-groups.ll

+; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
+;
+; Currently, MemorySSA doesn't support invariant groups. So, we should ignore
+; invariant.group.barrier intrinsics entirely. We'll need to pay attention to
+; them when/if we decide to support invariant groups.
+
+@g = external global i32
+
+define i32 @foo(i32* %a) {
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: store i32 0
+  store i32 0, i32* %a, align 4, !llvm.invariant.group !0
+
+; CHECK: 2 = MemoryDef(1)
+; CHECK-NEXT: store i32 1
+  store i32 1, i32* @g, align 4
+
+  %1 = bitcast i32* %a to i8*
+  %a8 = call i8* @llvm.invariant.group.barrier(i8* %1)
+  %a32 = bitcast i8* %a8 to i32*
+
+; CHECK: MemoryUse(2)
+; CHECK-NEXT: %2 = load i32
+  %2 = load i32, i32* %a32, align 4, !llvm.invariant.group !0
+  ret i32 %2
+}
+
+declare i8* @llvm.invariant.group.barrier(i8*)
+
+!0 = !{!"group1"}

test/Transforms/Util/MemorySSA/load-invariant.ll

-; XFAIL: *
 ; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
 ;
 ; Invariant loads should be considered live on entry, because, once the
 ; location is known to be dereferenceable, the value can never change.
-;
-; Currently XFAILed because this optimization was held back from the initial
-; commit.
 
 @g = external global i32
 
 declare void @clobberAllTheThings()
 
 define i32 @foo() {
 ; CHECK: 1 = MemoryDef(liveOnEntry)
 ; CHECK-NEXT: call void @clobberAllTheThings()
   call void @clobberAllTheThings()
 ; CHECK: MemoryUse(liveOnEntry)
 ; CHECK-NEXT: %1 = load i32
   %1 = load i32, i32* @g, align 4, !invariant.load !0
   ret i32 %1
 }
 
+define i32 @bar(i32* %a) {
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: call void @clobberAllTheThings()
+  call void @clobberAllTheThings()
+
+; CHECK: 2 = MemoryDef(1)
+; CHECK-NEXT: %1 = load atomic i32
+  %1 = load atomic i32, i32* %a acquire, align 4, !invariant.load !0
+
+; CHECK: MemoryUse(2)
+; CHECK-NEXT: %2 = load i32
+  %2 = load i32, i32* %a, align 4
+  ret i32 %2
+}
+
 !0 = !{}

test/Transforms/Util/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
 }
+
+define i32 @noclobber(i32* %vol, i32* %nonvol) {
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: %1 = load volatile i32
+  %1 = load volatile i32, i32* %vol, align 4
+; CHECK: MemoryUse(liveOnEntry)
+; CHECK-NEXT: %2 = load i32
+  %2 = load i32, i32* %nonvol, align 4
+  %3 = add i32 %1, %2
+  ret i32 %3
+}
+
+define i32 @ordered_clobber(i32* %vol, i32* %nonvol) {
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: %1 = load atomic volatile i32
+  %1 = load atomic volatile i32, i32* %vol acquire, align 4
+; CHECK: MemoryUse(1)
+; CHECK-NEXT: %2 = load i32
+  %2 = load i32, i32* %nonvol, align 4
+  %3 = add i32 %1, %2
+  ret i32 %3
+}