1 files changed, 163 insertions, 23 deletions

diff --git a/llvm/unittests/Transforms/Utils/MemorySSA.cpp b/llvm/unittests/Transforms/Utils/MemorySSA.cpp
index ceee21a70cf..5a226da476c 100644
--- a/llvm/unittests/Transforms/Utils/MemorySSA.cpp
+++ b/llvm/unittests/Transforms/Utils/MemorySSA.cpp
@@ -19,20 +19,59 @@
 
 using namespace llvm;
 
-TEST(MemorySSA, RemoveMemoryAccess) {
+const static char DLString[] = "e-i64:64-f80:128-n8:16:32:64-S128";
+
+/// There's a lot of common setup between these tests. This fixture helps reduce
+/// that. Tests should mock up a function, store it in F, and then call
+/// setupAnalyses().
+class MemorySSATest : public testing::Test {
+protected:
+  // N.B. Many of these members depend on each other (e.g. the Module depends on
+  // the Context, etc.). So, order matters here (and in TestAnalyses).
   LLVMContext C;
-  std::unique_ptr<Module> M(new Module("Remove memory access", C));
-  IRBuilder<> B(C);
-  DataLayout DL("e-i64:64-f80:128-n8:16:32:64-S128");
+  Module M;
+  IRBuilder<> B;
+  DataLayout DL;
   TargetLibraryInfoImpl TLII;
-  TargetLibraryInfo TLI(TLII);
+  TargetLibraryInfo TLI;
+  Function *F;
+
+  // Things that we need to build after the function is created.
+  struct TestAnalyses {
+    DominatorTree DT;
+    AssumptionCache AC;
+    AAResults AA;
+    BasicAAResult BAA;
+    MemorySSA MSSA;
+    std::unique_ptr<MemorySSAWalker> Walker;
+
+    TestAnalyses(MemorySSATest &Test)
+        : DT(*Test.F), AC(*Test.F), AA(Test.TLI),
+          BAA(Test.DL, Test.TLI, AC, &DT), MSSA(*Test.F) {
+      AA.addAAResult(BAA);
+      Walker.reset(MSSA.buildMemorySSA(&AA, &DT));
+    }
+  };
+
+  std::unique_ptr<TestAnalyses> Analyses;
+
+  void setupAnalyses() {
+    assert(F);
+    Analyses.reset(new TestAnalyses(*this));
+  }
+
+public:
+  MemorySSATest()
+      : M("MemorySSATest", C), B(C), DL(DLString), TLI(TLII), F(nullptr) {}
+};
 
+TEST_F(MemorySSATest, RemoveMemoryAccess) {
   // We create a diamond where there is a store on one side, and then a load
   // after the merge point.  This enables us to test a bunch of different
   // removal cases.
-  Function *F = Function::Create(
+  F = Function::Create(
       FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
-      GlobalValue::ExternalLinkage, "F", M.get());
+      GlobalValue::ExternalLinkage, "F", &M);
   BasicBlock *Entry(BasicBlock::Create(C, "", F));
   BasicBlock *Left(BasicBlock::Create(C, "", F));
   BasicBlock *Right(BasicBlock::Create(C, "", F));
@@ -47,24 +86,21 @@ TEST(MemorySSA, RemoveMemoryAccess) {
   B.SetInsertPoint(Merge);
   LoadInst *LoadInst = B.CreateLoad(PointerArg);
 
-  std::unique_ptr<MemorySSA> MSSA(new MemorySSA(*F));
-  std::unique_ptr<DominatorTree> DT(new DominatorTree(*F));
-  std::unique_ptr<AssumptionCache> AC(new AssumptionCache(*F));
-  AAResults AA(TLI);
-  BasicAAResult BAA(DL, TLI, *AC, &*DT);
-  AA.addAAResult(BAA);
-  std::unique_ptr<MemorySSAWalker> Walker(MSSA->buildMemorySSA(&AA, &*DT));
+  setupAnalyses();
+  MemorySSA &MSSA = Analyses->MSSA;
+  MemorySSAWalker *Walker = &*Analyses->Walker;
+
   // Before, the load will be a use of a phi<store, liveonentry>. It should be
   // the same after.
-  MemoryUse *LoadAccess = cast<MemoryUse>(MSSA->getMemoryAccess(LoadInst));
-  MemoryDef *StoreAccess = cast<MemoryDef>(MSSA->getMemoryAccess(StoreInst));
+  MemoryUse *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(LoadInst));
+  MemoryDef *StoreAccess = cast<MemoryDef>(MSSA.getMemoryAccess(StoreInst));
   MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();
   EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));
   // The load is currently clobbered by one of the phi arguments, so the walker
   // should determine the clobbering access as the phi.
   EXPECT_EQ(DefiningAccess, Walker->getClobberingMemoryAccess(LoadInst));
-  MSSA->removeMemoryAccess(StoreAccess);
-  MSSA->verifyMemorySSA();
+  MSSA.removeMemoryAccess(StoreAccess);
+  MSSA.verifyMemorySSA();
   // After the removeaccess, let's see if we got the right accesses
   // The load should still point to the phi ...
   EXPECT_EQ(DefiningAccess, LoadAccess->getDefiningAccess());
@@ -72,17 +108,121 @@ TEST(MemorySSA, RemoveMemoryAccess) {
   // load, since it will walk past the phi node since every argument is the
   // same.
   EXPECT_TRUE(
-      MSSA->isLiveOnEntryDef(Walker->getClobberingMemoryAccess(LoadInst)));
+      MSSA.isLiveOnEntryDef(Walker->getClobberingMemoryAccess(LoadInst)));
 
   // The phi should now be a two entry phi with two live on entry defs.
   for (const auto &Op : DefiningAccess->operands()) {
     MemoryAccess *Operand = cast<MemoryAccess>(&*Op);
-    EXPECT_TRUE(MSSA->isLiveOnEntryDef(Operand));
+    EXPECT_TRUE(MSSA.isLiveOnEntryDef(Operand));
   }
 
   // Now we try to remove the single valued phi
-  MSSA->removeMemoryAccess(DefiningAccess);
-  MSSA->verifyMemorySSA();
+  MSSA.removeMemoryAccess(DefiningAccess);
+  MSSA.verifyMemorySSA();
   // Now the load should be a load of live on entry.
-  EXPECT_TRUE(MSSA->isLiveOnEntryDef(LoadAccess->getDefiningAccess()));
+  EXPECT_TRUE(MSSA.isLiveOnEntryDef(LoadAccess->getDefiningAccess()));
+}
+
+// We had a bug with caching where the walker would report MemoryDef#3's clobber
+// (below) was MemoryDef#1.
+//
+// define void @F(i8*) {
+//   %A = alloca i8, i8 1
+// ; 1 = MemoryDef(liveOnEntry)
+//   store i8 0, i8* %A
+// ; 2 = MemoryDef(1)
+//   store i8 1, i8* %A
+// ; 3 = MemoryDef(2)
+//   store i8 2, i8* %A
+// }
+TEST_F(MemorySSATest, TestTripleStore) {
+  F = Function::Create(
+      FunctionType::get(B.getVoidTy(), {}, false),
+      GlobalValue::ExternalLinkage, "F", &M);
+  B.SetInsertPoint(BasicBlock::Create(C, "", F));
+  Type *Int8 = Type::getInt8Ty(C);
+  Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
+  StoreInst *S1 = B.CreateStore(ConstantInt::get(Int8, 0), Alloca);
+  StoreInst *S2 = B.CreateStore(ConstantInt::get(Int8, 1), Alloca);
+  StoreInst *S3 = B.CreateStore(ConstantInt::get(Int8, 2), Alloca);
+
+  setupAnalyses();
+  MemorySSA &MSSA = Analyses->MSSA;
+  MemorySSAWalker *Walker = &*Analyses->Walker;
+
+  unsigned I = 0;
+  for (StoreInst *V : {S1, S2, S3}) {
+    // Everything should be clobbered by its defining access
+    MemoryAccess *DefiningAccess =
+        cast<MemoryUseOrDef>(MSSA.getMemoryAccess(V))->getDefiningAccess();
+    MemoryAccess *WalkerClobber = Walker->getClobberingMemoryAccess(V);
+    EXPECT_EQ(DefiningAccess, WalkerClobber)
+        << "Store " << I << " doesn't have the correct clobbering access";
+    // EXPECT_EQ expands such that if we increment I above, it won't get
+    // incremented except when we try to print the error message.
+    ++I;
+  }
+}
+
+// ...And fixing the above bug made it obvious that, when walking, MemorySSA's
+// walker was caching the initial node it walked. This was fine (albeit
+// mostly redundant) unless the initial node being walked is a clobber for the
+// query. In that case, we'd cache that the node clobbered itself.
+TEST_F(MemorySSATest, TestStoreAndLoad) {
+  F = Function::Create(
+      FunctionType::get(B.getVoidTy(), {}, false),
+      GlobalValue::ExternalLinkage, "F", &M);
+  B.SetInsertPoint(BasicBlock::Create(C, "", F));
+  Type *Int8 = Type::getInt8Ty(C);
+  Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
+  Instruction *SI = B.CreateStore(ConstantInt::get(Int8, 0), Alloca);
+  Instruction *LI = B.CreateLoad(Alloca);
+
+  setupAnalyses();
+  MemorySSA &MSSA = Analyses->MSSA;
+  MemorySSAWalker *Walker = &*Analyses->Walker;
+
+  MemoryAccess *LoadClobber = Walker->getClobberingMemoryAccess(LI);
+  EXPECT_EQ(LoadClobber, MSSA.getMemoryAccess(SI));
+  EXPECT_TRUE(MSSA.isLiveOnEntryDef(Walker->getClobberingMemoryAccess(SI)));
+}
+
+// Another bug (related to the above two fixes): It was noted that, given the
+// following code:
+// ; 1 = MemoryDef(liveOnEntry)
+// store i8 0, i8* %1
+//
+// ...A query to getClobberingMemoryAccess(MemoryAccess*, MemoryLocation) would
+// hand back the store (correctly). A later call to
+// getClobberingMemoryAccess(const Instruction*) would also hand back the store
+// (incorrectly; it should return liveOnEntry).
+//
+// This test checks that repeated calls to either function returns what they're
+// meant to.
+TEST_F(MemorySSATest, TestStoreDoubleQuery) {
+  F = Function::Create(
+      FunctionType::get(B.getVoidTy(), {}, false),
+      GlobalValue::ExternalLinkage, "F", &M);
+  B.SetInsertPoint(BasicBlock::Create(C, "", F));
+  Type *Int8 = Type::getInt8Ty(C);
+  Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
+  StoreInst *SI = B.CreateStore(ConstantInt::get(Int8, 0), Alloca);
+
+  setupAnalyses();
+  MemorySSA &MSSA = Analyses->MSSA;
+  MemorySSAWalker *Walker = &*Analyses->Walker;
+
+  MemoryAccess *StoreAccess = MSSA.getMemoryAccess(SI);
+  MemoryLocation StoreLoc = MemoryLocation::get(SI);
+  MemoryAccess *Clobber = Walker->getClobberingMemoryAccess(StoreAccess, StoreLoc);
+  MemoryAccess *LiveOnEntry = Walker->getClobberingMemoryAccess(SI);
+
+  EXPECT_EQ(Clobber, StoreAccess);
+  EXPECT_TRUE(MSSA.isLiveOnEntryDef(LiveOnEntry));
+
+  // Try again (with entries in the cache already) for good measure...
+  Clobber = Walker->getClobberingMemoryAccess(StoreAccess, StoreLoc);
+  LiveOnEntry = Walker->getClobberingMemoryAccess(SI);
+  EXPECT_EQ(Clobber, StoreAccess);
+  EXPECT_TRUE(MSSA.isLiveOnEntryDef(LiveOnEntry));
 }