Introduce a basic MemorySSA updater, that supports insertDef,

insertUse, moveBefore and moveAfter operations.

Summary:
This creates a basic MemorySSA updater that handles arbitrary
insertion of uses and defs into MemorySSA, as well as arbitrary
movement around the CFG. It replaces the current splice API.

It can be made to handle arbitrary control flow changes.
Currently, it uses the same updater algorithm from D28934.

The main difference is because MemorySSA is single variable, we have
the complete def and use list, and don't need anyone to give it to us
as part of the API.  We also have to rename stores below us in some
cases.

If we go that direction in that patch, i will merge all the updater
implementations (using an updater_traits or something to provide the
get* functions we use, called read*/write* in that patch).

Sadly, the current SSAUpdater algorithm is way too slow to use for
what we are doing here.

I have updated the tests we have to basically build memoryssa
incrementally using the updater api, and make sure it still comes out
the same.

Reviewers: george.burgess.iv

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D29047

llvm-svn: 293356

1 files changed, 270 insertions, 8 deletions

diff --git a/llvm/unittests/Transforms/Utils/MemorySSA.cpp b/llvm/unittests/Transforms/Utils/MemorySSA.cpp
index 7d9cefa9dc3..74f8d247f83 100644
--- a/llvm/unittests/Transforms/Utils/MemorySSA.cpp
+++ b/llvm/unittests/Transforms/Utils/MemorySSA.cpp
@@ -104,11 +104,145 @@ TEST_F(MemorySSATest, CreateALoad) {
   EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));
   MSSA.verifyMemorySSA();
 }
+TEST_F(MemorySSATest, CreateLoadsAndStoreUpdater) {
+  // We create a diamond, then build memoryssa with no memory accesses, and
+  // incrementally update it by inserting a store in the, entry, a load in the
+  // merge point, then a store in the branch, another load in the merge point,
+  // and then a store in the entry.
+  F = Function::Create(
+      FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
+      GlobalValue::ExternalLinkage, "F", &M);
+  BasicBlock *Entry(BasicBlock::Create(C, "", F));
+  BasicBlock *Left(BasicBlock::Create(C, "", F));
+  BasicBlock *Right(BasicBlock::Create(C, "", F));
+  BasicBlock *Merge(BasicBlock::Create(C, "", F));
+  B.SetInsertPoint(Entry);
+  B.CreateCondBr(B.getTrue(), Left, Right);
+  B.SetInsertPoint(Left, Left->begin());
+  Argument *PointerArg = &*F->arg_begin();
+  B.SetInsertPoint(Left);
+  B.CreateBr(Merge);
+  B.SetInsertPoint(Right);
+  B.CreateBr(Merge);
+
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+  MemorySSAUpdater Updater(&MSSA);
+  // Add the store
+  B.SetInsertPoint(Entry, Entry->begin());
+  StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);
+  MemoryAccess *EntryStoreAccess = MSSA.createMemoryAccessInBB(
+      EntryStore, nullptr, Entry, MemorySSA::Beginning);
+  Updater.insertDef(cast<MemoryDef>(EntryStoreAccess));
+
+  // Add the load
+  B.SetInsertPoint(Merge, Merge->begin());
+  LoadInst *FirstLoad = B.CreateLoad(PointerArg);
+
+  // MemoryPHI should not already exist.
+  MemoryPhi *MP = MSSA.getMemoryAccess(Merge);
+  EXPECT_EQ(MP, nullptr);
+
+  // Create the load memory access
+  MemoryUse *FirstLoadAccess = cast<MemoryUse>(MSSA.createMemoryAccessInBB(
+      FirstLoad, nullptr, Merge, MemorySSA::Beginning));
+  Updater.insertUse(FirstLoadAccess);
+  // Should just have a load using the entry access, because it should discover
+  // the phi is trivial
+  EXPECT_EQ(FirstLoadAccess->getDefiningAccess(), EntryStoreAccess);
+
+  // Create a store on the left
+  // Add the store
+  B.SetInsertPoint(Left, Left->begin());
+  StoreInst *LeftStore = B.CreateStore(B.getInt8(16), PointerArg);
+  MemoryAccess *LeftStoreAccess = MSSA.createMemoryAccessInBB(
+      LeftStore, nullptr, Left, MemorySSA::Beginning);
+  Updater.insertDef(cast<MemoryDef>(LeftStoreAccess));
+  // We don't touch existing loads, so we need to create a new one to get a phi
+  // Add the second load
+  B.SetInsertPoint(Merge, Merge->begin());
+  LoadInst *SecondLoad = B.CreateLoad(PointerArg);
+
+  // MemoryPHI should not already exist.
+  MP = MSSA.getMemoryAccess(Merge);
+  EXPECT_EQ(MP, nullptr);
+
+  // Create the load memory access
+  MemoryUse *SecondLoadAccess = cast<MemoryUse>(MSSA.createMemoryAccessInBB(
+      SecondLoad, nullptr, Merge, MemorySSA::Beginning));
+  Updater.insertUse(SecondLoadAccess);
+  // Now the load should be a phi of the entry store and the left store
+  MemoryPhi *MergePhi =
+      dyn_cast<MemoryPhi>(SecondLoadAccess->getDefiningAccess());
+  EXPECT_NE(MergePhi, nullptr);
+  EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess);
+  EXPECT_EQ(MergePhi->getIncomingValue(1), LeftStoreAccess);
+  // Now create a store below the existing one in the entry
+  B.SetInsertPoint(Entry, --Entry->end());
+  StoreInst *SecondEntryStore = B.CreateStore(B.getInt8(16), PointerArg);
+  MemoryAccess *SecondEntryStoreAccess = MSSA.createMemoryAccessInBB(
+      SecondEntryStore, nullptr, Entry, MemorySSA::End);
+  Updater.insertDef(cast<MemoryDef>(SecondEntryStoreAccess));
+  // and make sure the phi below it got updated, despite being blocks away
+  MergePhi = dyn_cast<MemoryPhi>(SecondLoadAccess->getDefiningAccess());
+  EXPECT_NE(MergePhi, nullptr);
+  EXPECT_EQ(MergePhi->getIncomingValue(0), SecondEntryStoreAccess);
+  EXPECT_EQ(MergePhi->getIncomingValue(1), LeftStoreAccess);
+  MSSA.verifyMemorySSA();
+}
+
+TEST_F(MemorySSATest, CreateALoadUpdater) {
+  // We create a diamond, then build memoryssa with no memory accesses, and
+  // incrementally update it by inserting a store in one of the branches, and a
+  // load in the merge point
+  F = Function::Create(
+      FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
+      GlobalValue::ExternalLinkage, "F", &M);
+  BasicBlock *Entry(BasicBlock::Create(C, "", F));
+  BasicBlock *Left(BasicBlock::Create(C, "", F));
+  BasicBlock *Right(BasicBlock::Create(C, "", F));
+  BasicBlock *Merge(BasicBlock::Create(C, "", F));
+  B.SetInsertPoint(Entry);
+  B.CreateCondBr(B.getTrue(), Left, Right);
+  B.SetInsertPoint(Left, Left->begin());
+  Argument *PointerArg = &*F->arg_begin();
+  B.SetInsertPoint(Left);
+  B.CreateBr(Merge);
+  B.SetInsertPoint(Right);
+  B.CreateBr(Merge);
+
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+  MemorySSAUpdater Updater(&MSSA);
+  B.SetInsertPoint(Left, Left->begin());
+  // Add the store
+  StoreInst *SI = B.CreateStore(B.getInt8(16), PointerArg);
+  MemoryAccess *StoreAccess =
+      MSSA.createMemoryAccessInBB(SI, nullptr, Left, MemorySSA::Beginning);
+  Updater.insertDef(cast<MemoryDef>(StoreAccess));
+
+  // Add the load
+  B.SetInsertPoint(Merge, Merge->begin());
+  LoadInst *LoadInst = B.CreateLoad(PointerArg);
+
+  // MemoryPHI should not already exist.
+  MemoryPhi *MP = MSSA.getMemoryAccess(Merge);
+  EXPECT_EQ(MP, nullptr);
+
+  // Create the load memory acccess
+  MemoryUse *LoadAccess = cast<MemoryUse>(MSSA.createMemoryAccessInBB(
+      LoadInst, nullptr, Merge, MemorySSA::Beginning));
+  Updater.insertUse(LoadAccess);
+  MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();
+  EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));
+  MSSA.verifyMemorySSA();
+}
 
 TEST_F(MemorySSATest, MoveAStore) {
   // We create a diamond where there is a in the entry, a store on one side, and
   // a load at the end.  After building MemorySSA, we test updating by moving
-  // the store from the side block to the entry block.
+  // the store from the side block to the entry block. This destroys the old
+  // access.
   F = Function::Create(
       FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
       GlobalValue::ExternalLinkage, "F", &M);
@@ -140,6 +274,96 @@ TEST_F(MemorySSATest, MoveAStore) {
   MSSA.verifyMemorySSA();
 }
 
+TEST_F(MemorySSATest, MoveAStoreUpdater) {
+  // We create a diamond where there is a in the entry, a store on one side, and
+  // a load at the end.  After building MemorySSA, we test updating by moving
+  // the store from the side block to the entry block.  This destroys the old
+  // access.
+  F = Function::Create(
+      FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
+      GlobalValue::ExternalLinkage, "F", &M);
+  BasicBlock *Entry(BasicBlock::Create(C, "", F));
+  BasicBlock *Left(BasicBlock::Create(C, "", F));
+  BasicBlock *Right(BasicBlock::Create(C, "", F));
+  BasicBlock *Merge(BasicBlock::Create(C, "", F));
+  B.SetInsertPoint(Entry);
+  Argument *PointerArg = &*F->arg_begin();
+  StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);
+  B.CreateCondBr(B.getTrue(), Left, Right);
+  B.SetInsertPoint(Left);
+  auto *SideStore = B.CreateStore(B.getInt8(16), PointerArg);
+  BranchInst::Create(Merge, Left);
+  BranchInst::Create(Merge, Right);
+  B.SetInsertPoint(Merge);
+  auto *MergeLoad = B.CreateLoad(PointerArg);
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+  MemorySSAUpdater Updater(&MSSA);
+
+  // Move the store
+  SideStore->moveBefore(Entry->getTerminator());
+  auto *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore);
+  auto *SideStoreAccess = MSSA.getMemoryAccess(SideStore);
+  auto *NewStoreAccess = MSSA.createMemoryAccessAfter(
+      SideStore, EntryStoreAccess, EntryStoreAccess);
+  // Before, the load will point to a phi of the EntryStore and SideStore.
+  auto *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(MergeLoad));
+  EXPECT_TRUE(isa<MemoryPhi>(LoadAccess->getDefiningAccess()));
+  MemoryPhi *MergePhi = cast<MemoryPhi>(LoadAccess->getDefiningAccess());
+  EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess);
+  EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess);
+  MSSA.removeMemoryAccess(SideStoreAccess);
+  Updater.insertDef(cast<MemoryDef>(NewStoreAccess));
+  // After it's a phi of the new side store access.
+  EXPECT_EQ(MergePhi->getIncomingValue(0), NewStoreAccess);
+  EXPECT_EQ(MergePhi->getIncomingValue(1), NewStoreAccess);
+  MSSA.verifyMemorySSA();
+}
+
+TEST_F(MemorySSATest, MoveAStoreUpdaterMove) {
+  // We create a diamond where there is a in the entry, a store on one side, and
+  // a load at the end.  After building MemorySSA, we test updating by moving
+  // the store from the side block to the entry block.  This does not destroy
+  // the old access.
+  F = Function::Create(
+      FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
+      GlobalValue::ExternalLinkage, "F", &M);
+  BasicBlock *Entry(BasicBlock::Create(C, "", F));
+  BasicBlock *Left(BasicBlock::Create(C, "", F));
+  BasicBlock *Right(BasicBlock::Create(C, "", F));
+  BasicBlock *Merge(BasicBlock::Create(C, "", F));
+  B.SetInsertPoint(Entry);
+  Argument *PointerArg = &*F->arg_begin();
+  StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);
+  B.CreateCondBr(B.getTrue(), Left, Right);
+  B.SetInsertPoint(Left);
+  auto *SideStore = B.CreateStore(B.getInt8(16), PointerArg);
+  BranchInst::Create(Merge, Left);
+  BranchInst::Create(Merge, Right);
+  B.SetInsertPoint(Merge);
+  auto *MergeLoad = B.CreateLoad(PointerArg);
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+  MemorySSAUpdater Updater(&MSSA);
+
+  // Move the store
+  auto *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore);
+  auto *SideStoreAccess = MSSA.getMemoryAccess(SideStore);
+  // Before, the load will point to a phi of the EntryStore and SideStore.
+  auto *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(MergeLoad));
+  EXPECT_TRUE(isa<MemoryPhi>(LoadAccess->getDefiningAccess()));
+  MemoryPhi *MergePhi = cast<MemoryPhi>(LoadAccess->getDefiningAccess());
+  EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess);
+  EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess);
+  SideStore->moveBefore(*EntryStore->getParent(), ++EntryStore->getIterator());
+  Updater.moveAfter(SideStoreAccess, EntryStoreAccess);
+  // After, it's a phi of the side store.
+  EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess);
+  EXPECT_EQ(MergePhi->getIncomingValue(1), SideStoreAccess);
+
+  MSSA.verifyMemorySSA();
+}
+
 TEST_F(MemorySSATest, RemoveAPhi) {
   // 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
@@ -485,9 +709,8 @@ TEST_F(MemorySSATest, WalkerReopt) {
   EXPECT_EQ(NewLoadAccess->getDefiningAccess(), LoadClobber);
 }
 
-#if 0
-// Test out MemorySSA::spliceMemoryAccessAbove.
-TEST_F(MemorySSATest, SpliceAboveMemoryDef) {
+// Test out MemorySSAUpdater::moveBefore
+TEST_F(MemorySSATest, MoveAboveMemoryDef) {
   F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
                        GlobalValue::ExternalLinkage, "F", &M);
   B.SetInsertPoint(BasicBlock::Create(C, "", F));
@@ -501,7 +724,6 @@ TEST_F(MemorySSATest, SpliceAboveMemoryDef) {
   StoreInst *StoreB = B.CreateStore(ConstantInt::get(Int8, 0), B_);
   LoadInst *LoadB = B.CreateLoad(B_);
   StoreInst *StoreA1 = B.CreateStore(ConstantInt::get(Int8, 4), A);
-  // splice this above StoreB
   StoreInst *StoreC = B.CreateStore(ConstantInt::get(Int8, 4), C);
   StoreInst *StoreA2 = B.CreateStore(ConstantInt::get(Int8, 4), A);
   LoadInst *LoadC = B.CreateLoad(C);
@@ -510,9 +732,10 @@ TEST_F(MemorySSATest, SpliceAboveMemoryDef) {
   MemorySSA &MSSA = *Analyses->MSSA;
   MemorySSAWalker &Walker = *Analyses->Walker;
 
+  MemorySSAUpdater Updater(&MSSA);
   StoreC->moveBefore(StoreB);
-  MSSA.spliceMemoryAccessAbove(cast<MemoryDef>(MSSA.getMemoryAccess(StoreB)),
-                               MSSA.getMemoryAccess(StoreC));
+  Updater.moveBefore(cast<MemoryDef>(MSSA.getMemoryAccess(StoreC)),
+                     cast<MemoryDef>(MSSA.getMemoryAccess(StoreB)));
 
   MSSA.verifyMemorySSA();
 
@@ -533,4 +756,43 @@ TEST_F(MemorySSATest, SpliceAboveMemoryDef) {
   EXPECT_TRUE(MSSA.locallyDominates(MSSA.getMemoryAccess(StoreA1),
                                     MSSA.getMemoryAccess(StoreA2)));
 }
-#endif
+
+TEST_F(MemorySSATest, Irreducible) {
+  // Create the equivalent of
+  // x = something
+  // if (...)
+  //    goto second_loop_entry
+  // while (...) {
+  // second_loop_entry:
+  // }
+  // use(x)
+
+  SmallVector<PHINode *, 8> Inserted;
+  IRBuilder<> B(C);
+  F = Function::Create(
+      FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
+      GlobalValue::ExternalLinkage, "F", &M);
+
+  // Make blocks
+  BasicBlock *IfBB = BasicBlock::Create(C, "if", F);
+  BasicBlock *LoopStartBB = BasicBlock::Create(C, "loopstart", F);
+  BasicBlock *LoopMainBB = BasicBlock::Create(C, "loopmain", F);
+  BasicBlock *AfterLoopBB = BasicBlock::Create(C, "afterloop", F);
+  B.SetInsertPoint(IfBB);
+  B.CreateCondBr(B.getTrue(), LoopMainBB, LoopStartBB);
+  B.SetInsertPoint(LoopStartBB);
+  B.CreateBr(LoopMainBB);
+  B.SetInsertPoint(LoopMainBB);
+  B.CreateCondBr(B.getTrue(), LoopStartBB, AfterLoopBB);
+  B.SetInsertPoint(AfterLoopBB);
+  Argument *FirstArg = &*F->arg_begin();
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+  MemorySSAUpdater Updater(&MSSA);
+  // Create the load memory acccess
+  LoadInst *LoadInst = B.CreateLoad(FirstArg);
+  MemoryUse *LoadAccess = cast<MemoryUse>(MSSA.createMemoryAccessInBB(
+      LoadInst, nullptr, AfterLoopBB, MemorySSA::Beginning));
+  Updater.insertUse(LoadAccess);
+  MSSA.verifyMemorySSA();
+}