[MemorySSA] Use provided memory location even if instruction is call

[nikic]

Summary

If getClobberingMemoryAccess() is called with an explicit MemoryLocation, but the starting access happens to be a call, the provided location is currently ignored, and alias analysis queries will be performed against the call instruction instead. Something similar happens if the starting access is a load with a MemoryDef.

Change the implementation to not set Q.Inst in the first place if we want to perform a MemoryLocation-based query, to make sure it can't be turned into an Instruction-based query along the way...

Additionally, remove the special handling that lifetime.start intrinsics currently get. They simply report NoAlias for clobbers between lifetime.start and other calls, but that's obviously not correct if the other call is something like a memset or memcpy. The default behavior we get from getModRefInfo() will already do the right thing here.

[nikic]

Okay, I'm pretty sure this is not fixing the right issue. If I'm understanding correctly, the real problem is that the provided memory location just gets ignored entirely if the UseInst happens to be a call. I think whether AA is queried with the location or with the call should be determined by Query.IsCall, not whether UseInst is a call.

[nikic]

Fix the underlying problem. Ran into this with lifetime intrinsics, but it's really something that affects all calls.

[asbirlea]

llvm/lib/Analysis/MemorySSA.cpp

2354

Is it possible this is the place where the inconsistency comes from, or did I misunderstand?

[nikic]

llvm/lib/Analysis/MemorySSA.cpp

2354

Depends on what you mean by "comes from" :) This is indeed the place where we create a Query with IsCall=false and Inst being (potentially) a CallBase. However, I believe this is correct, as this query should only care about the provided Loc, not the Inst it happens to start at. Maybe it would be possible to set Inst to nullptr altogether...

[nikic]

Add a dedicated test with queries starting from a memset.

[nikic]

llvm/lib/Analysis/MemorySSA.cpp

301

Even after this fix, there will still be an issue with the handling of loads, due to this code. Say we start from a store and perform a clobber query on getDefiningAccess(), which happens to return a volatile load. Then we will end up trying to find clobbers for the volatile load, once again ignoring the provided location completely.

[nikic]

Set Inst to nullptr to prevent any abuse, thus handling both the call and the load case. Also drop the special lifetime.start handling so that clobbers between calls and lifetime.start are correctly handled.

[asbirlea]

Thank you for detailed tests, this looks good!

llvm/lib/Analysis/MemorySSA.cpp

 // Return a pair of {IsClobber (bool), AR (AliasResult)}. It relies on AR being
 // ignored if IsClobber = false.
 template <typename AliasAnalysisType>
 static ClobberAlias
 instructionClobbersQuery(const MemoryDef *MD, const MemoryLocation &UseLoc,
                          const Instruction *UseInst, AliasAnalysisType &AA) {
   Instruction *DefInst = MD->getMemoryInst();
   assert(DefInst && "Defining instruction not actually an instruction");
-  const auto *UseCall = dyn_cast<CallBase>(UseInst);
   Optional<AliasResult> AR;
 
   if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(DefInst)) {
     // These intrinsics will show up as affecting memory, but they are just
     // markers, mostly.
     //
     // FIXME: We probably don't actually want MemorySSA to model these at all
     // (including creating MemoryAccesses for them): we just end up inventing
     // clobbers where they don't really exist at all. Please see D43269 for
     // context.
     switch (II->getIntrinsicID()) {
-    case Intrinsic::lifetime_start:
-      if (UseCall)
-        return {false, NoAlias};
-      AR = AA.alias(MemoryLocation(II->getArgOperand(1)), UseLoc);
-      return {AR != NoAlias, AR};
     case Intrinsic::lifetime_end:
     case Intrinsic::invariant_start:
     case Intrinsic::invariant_end:
     case Intrinsic::assume:
       return {false, NoAlias};
     case Intrinsic::dbg_addr:
     case Intrinsic::dbg_declare:
     case Intrinsic::dbg_label:
     case Intrinsic::dbg_value:
       llvm_unreachable("debuginfo shouldn't have associated defs!");
     default:
       break;
     }
   }
 
-  if (UseCall) {
-    ModRefInfo I = AA.getModRefInfo(DefInst, UseCall);
+  if (auto *CB = dyn_cast_or_null<CallBase>(UseInst)) {
+    ModRefInfo I = AA.getModRefInfo(DefInst, CB);
     AR = isMustSet(I) ? MustAlias : MayAlias;
     return {isModOrRefSet(I), AR};
   }
 
   if (auto *DefLoad = dyn_cast<LoadInst>(DefInst))
-    if (auto *UseLoad = dyn_cast<LoadInst>(UseInst))
+    if (auto *UseLoad = dyn_cast_or_null<LoadInst>(UseInst))
       return {!areLoadsReorderable(UseLoad, DefLoad), MayAlias};
 
   ModRefInfo I = AA.getModRefInfo(DefInst, UseLoc);
   AR = isMustSet(I) ? MustAlias : MayAlias;
   return {isModSet(I), AR};
 }
 
 template <typename AliasAnalysisType>
 static ClobberAlias instructionClobbersQuery(MemoryDef *MD,
MemorySSA::ClobberWalkerBase<AliasAnalysisType>::getClobberingMemoryAccessBase(
   // Conservatively, fences are always clobbers, so don't perform the walk if we
   // hit a fence.
   if (!isa<CallBase>(I) && I->isFenceLike())
     return StartingUseOrDef;
 
   UpwardsMemoryQuery Q;
   Q.OriginalAccess = StartingUseOrDef;
   Q.StartingLoc = Loc;
-  Q.Inst = I;
+  Q.Inst = nullptr;
   Q.IsCall = false;
 
   // Unlike the other function, do not walk to the def of a def, because we are
   // handed something we already believe is the clobbering access.
   // We never set SkipSelf to true in Q in this method.
   MemoryAccess *DefiningAccess = isa<MemoryUse>(StartingUseOrDef)
                                      ? StartingUseOrDef->getDefiningAccess()
                                      : StartingUseOrDef;
 

llvm/unittests/Analysis/MemorySSATest.cpp

for (StoreInst *V : Sts) {
     ++I;
   }
 }
 
 TEST_F(MemorySSATest, LifetimeMarkersAreClobbers) {
   // Example code:
   // define void @a(i8* %foo) {
   //   %bar = getelementptr i8, i8* %foo, i64 1
+  //   %baz = getelementptr i8, i8* %foo, i64 2
   //   store i8 0, i8* %foo
   //   store i8 0, i8* %bar
-  //   call void @llvm.lifetime.end.p0i8(i64 8, i32* %p)
-  //   call void @llvm.lifetime.start.p0i8(i64 8, i32* %p)
+  //   call void @llvm.lifetime.end.p0i8(i64 3, i8* %foo)
+  //   call void @llvm.lifetime.start.p0i8(i64 3, i8* %foo)
   //   store i8 0, i8* %foo
   //   store i8 0, i8* %bar
+  //   call void @llvm.memset.p0i8(i8* %baz, i8 0, i64 1)
   //   ret void
   // }
   //
   // Patterns like this are possible after inlining; the stores to %foo and %bar
   // should both be clobbered by the lifetime.start call if they're dominated by
   // it.
 
   IRBuilder<> B(C);
   F = Function::Create(
       FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
       GlobalValue::ExternalLinkage, "F", &M);
 
   // Make blocks
   BasicBlock *Entry = BasicBlock::Create(C, "entry", F);
 
   B.SetInsertPoint(Entry);
   Value *Foo = &*F->arg_begin();
 
   Value *Bar = B.CreateGEP(B.getInt8Ty(), Foo, B.getInt64(1), "bar");
+  Value *Baz = B.CreateGEP(B.getInt8Ty(), Foo, B.getInt64(2), "baz");
 
   B.CreateStore(B.getInt8(0), Foo);
   B.CreateStore(B.getInt8(0), Bar);
 
   auto GetLifetimeIntrinsic = [&](Intrinsic::ID ID) {
     return Intrinsic::getDeclaration(&M, ID, {Foo->getType()});
   };
 
   B.CreateCall(GetLifetimeIntrinsic(Intrinsic::lifetime_end),
-               {B.getInt64(2), Foo});
+               {B.getInt64(3), Foo});
   Instruction *LifetimeStart = B.CreateCall(
-      GetLifetimeIntrinsic(Intrinsic::lifetime_start), {B.getInt64(2), Foo});
+      GetLifetimeIntrinsic(Intrinsic::lifetime_start), {B.getInt64(3), Foo});
 
   Instruction *FooStore = B.CreateStore(B.getInt8(0), Foo);
   Instruction *BarStore = B.CreateStore(B.getInt8(0), Bar);
+  Instruction *BazMemSet = B.CreateMemSet(Baz, B.getInt8(0), 1, Align(1));
 
   setupAnalyses();
   MemorySSA &MSSA = *Analyses->MSSA;
 
   MemoryAccess *LifetimeStartAccess = MSSA.getMemoryAccess(LifetimeStart);
   ASSERT_NE(LifetimeStartAccess, nullptr);
 
   MemoryAccess *FooAccess = MSSA.getMemoryAccess(FooStore);
   ASSERT_NE(FooAccess, nullptr);
 
   MemoryAccess *BarAccess = MSSA.getMemoryAccess(BarStore);
   ASSERT_NE(BarAccess, nullptr);
 
+  MemoryAccess *BazAccess = MSSA.getMemoryAccess(BazMemSet);
+  ASSERT_NE(BazAccess, nullptr);
+
   MemoryAccess *FooClobber =
       MSSA.getWalker()->getClobberingMemoryAccess(FooAccess);
   EXPECT_EQ(FooClobber, LifetimeStartAccess);
 
   MemoryAccess *BarClobber =
       MSSA.getWalker()->getClobberingMemoryAccess(BarAccess);
   EXPECT_EQ(BarClobber, LifetimeStartAccess);
+
+  MemoryAccess *BazClobber =
+      MSSA.getWalker()->getClobberingMemoryAccess(BazAccess);
+  EXPECT_EQ(BazClobber, LifetimeStartAccess);
+
+  MemoryAccess *LifetimeStartClobber =
+      MSSA.getWalker()->getClobberingMemoryAccess(
+          LifetimeStartAccess, MemoryLocation(Foo));
+  EXPECT_EQ(LifetimeStartClobber, LifetimeStartAccess);
 }
 
 TEST_F(MemorySSATest, DefOptimizationsAreInvalidatedOnMoving) {
   IRBuilder<> B(C);
   F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getInt1Ty()}, false),
                        GlobalValue::ExternalLinkage, "F", &M);
 
   // Make a CFG like
TEST_F(MemorySSATest, TestAddedEdgeToBlockWithNoPhiAddNewPhis) {
 
   MemoryPhi *MPC = MSSA.getMemoryAccess(CBlock);
   EXPECT_NE(MPC, nullptr);
   MemoryPhi *MPD = MSSA.getMemoryAccess(DBlock);
   EXPECT_NE(MPD, nullptr);
   MemoryPhi *MPE = MSSA.getMemoryAccess(EBlock);
   EXPECT_EQ(MPD, MPE->getIncomingValueForBlock(DBlock));
 }
+
+TEST_F(MemorySSATest, TestCallClobber) {
+  F = Function::Create(
+      FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
+      GlobalValue::ExternalLinkage, "F", &M);
+
+  Value *Pointer1 = &*F->arg_begin();
+  BasicBlock *Entry(BasicBlock::Create(C, "", F));
+  B.SetInsertPoint(Entry);
+  Value *Pointer2 = B.CreateGEP(B.getInt8Ty(), Pointer1, B.getInt64(1));
+  Instruction *StorePointer1 = B.CreateStore(B.getInt8(0), Pointer1);
+  Instruction *StorePointer2 = B.CreateStore(B.getInt8(0), Pointer2);
+  Instruction *MemSet = B.CreateMemSet(Pointer2, B.getInt8(0), 1, Align(1));
+
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+  MemorySSAWalker *Walker = Analyses->Walker;
+
+  MemoryUseOrDef *Store1Access = MSSA.getMemoryAccess(StorePointer1);
+  MemoryUseOrDef *Store2Access = MSSA.getMemoryAccess(StorePointer2);
+  MemoryUseOrDef *MemSetAccess = MSSA.getMemoryAccess(MemSet);
+
+  MemoryAccess *Pointer1Clobber = Walker->getClobberingMemoryAccess(
+      MemSetAccess, MemoryLocation(Pointer1, LocationSize::precise(1)));
+  EXPECT_EQ(Pointer1Clobber, Store1Access);
+
+  MemoryAccess *Pointer2Clobber = Walker->getClobberingMemoryAccess(
+      MemSetAccess, MemoryLocation(Pointer2, LocationSize::precise(1)));
+  EXPECT_EQ(Pointer2Clobber, MemSetAccess);
+
+  MemoryAccess *MemSetClobber = Walker->getClobberingMemoryAccess(MemSetAccess);
+  EXPECT_EQ(MemSetClobber, Store2Access);
+}
+
+TEST_F(MemorySSATest, TestLoadClobber) {
+  F = Function::Create(
+      FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
+      GlobalValue::ExternalLinkage, "F", &M);
+
+  Value *Pointer1 = &*F->arg_begin();
+  BasicBlock *Entry(BasicBlock::Create(C, "", F));
+  B.SetInsertPoint(Entry);
+  Value *Pointer2 = B.CreateGEP(B.getInt8Ty(), Pointer1, B.getInt64(1));
+  Instruction *LoadPointer1 =
+      B.CreateLoad(B.getInt8Ty(), Pointer1, /* Volatile */ true);
+  Instruction *LoadPointer2 =
+      B.CreateLoad(B.getInt8Ty(), Pointer2, /* Volatile */ true);
+
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+  MemorySSAWalker *Walker = Analyses->Walker;
+
+  MemoryUseOrDef *Load1Access = MSSA.getMemoryAccess(LoadPointer1);
+  MemoryUseOrDef *Load2Access = MSSA.getMemoryAccess(LoadPointer2);
+
+  // When providing a memory location, we should never return a load as the
+  // clobber.
+  MemoryAccess *Pointer1Clobber = Walker->getClobberingMemoryAccess(
+      Load2Access, MemoryLocation(Pointer1, LocationSize::precise(1)));
+  EXPECT_TRUE(MSSA.isLiveOnEntryDef(Pointer1Clobber));
+
+  MemoryAccess *Pointer2Clobber = Walker->getClobberingMemoryAccess(
+      Load2Access, MemoryLocation(Pointer2, LocationSize::precise(1)));
+  EXPECT_TRUE(MSSA.isLiveOnEntryDef(Pointer2Clobber));
+
+  MemoryAccess *Load2Clobber = Walker->getClobberingMemoryAccess(Load2Access);
+  EXPECT_EQ(Load2Clobber, Load1Access);
+}