[MemorySSA] Define a restricted upward AccessList splice.

[bryant]

Summary

This defines an API endpoint that allows clients to move upwards a MemoryUse/Def
*M to just before a MemoryDef *Dest, where Dest and M may reside in separate
BasicBlocks. The following conditions must hold:

• Dest must dominate M,
• All MemoryAccesses between the Dest and M, as well as Dest itself, must be no-alias with M,
• Dest is MemoryDef (this restriction could probably be lifted).

These conditions allow the splice to be carried out with simple
replaceAllUsesWith and setDefiningAccess operations. In particular, the first
and second conditions are sufficient conditions for preservation of semantics.

[bryant]

• Mark affected basic blocks for re-numbering.
• Add test.

llvm/trunk/include/llvm/Transforms/Utils/MemorySSA.h

public:
   /// inaccessible and it *must* have removeMemoryAccess called on it.
   MemoryUseOrDef *createMemoryAccessBefore(Instruction *I,
                                            MemoryAccess *Definition,
                                            MemoryUseOrDef *InsertPt);
   MemoryUseOrDef *createMemoryAccessAfter(Instruction *I,
                                           MemoryAccess *Definition,
                                           MemoryAccess *InsertPt);
 
+  // \brief Splice \p What to just before \p Where.
+  //
+  // In order to be efficient, the following conditions must be met:
+  //   - \p Where  dominates \p What,
+  //   - All memory accesses in [\p Where, \p What) are no-alias with \p What.
+  //
+  // TODO: relax the MemoryDef requirement on Where.
+  void spliceMemoryAccessAbove(MemoryDef *Where, MemoryUseOrDef *What);
+
   /// \brief Remove a MemoryAccess from MemorySSA, including updating all
   /// definitions and uses.
   /// This should be called when a memory instruction that has a MemoryAccess
   /// associated with it is erased from the program.  For example, if a store or
   /// load is simply erased (not replaced), removeMemoryAccess should be called
   /// on the MemoryAccess for that store/load.
   void removeMemoryAccess(MemoryAccess *);
 

llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp

assert(I->getParent() == InsertPt->getBlock() &&
          "New and old access must be in the same block");
   MemoryUseOrDef *NewAccess = createDefinedAccess(I, Definition);
   auto *Accesses = getOrCreateAccessList(InsertPt->getBlock());
   Accesses->insertAfter(AccessList::iterator(InsertPt), NewAccess);
   BlockNumberingValid.erase(InsertPt->getBlock());
   return NewAccess;
 }
 
+void MemorySSA::spliceMemoryAccessAbove(MemoryDef *Where,
+                                        MemoryUseOrDef *What) {
+  assert(What != getLiveOnEntryDef() &&
+         Where != getLiveOnEntryDef() && "Can't splice (above) LOE.");
+  assert(dominates(Where, What) && "Only upwards splices are permitted.");
+
+  if (Where == What)
+    return;
+  if (isa<MemoryDef>(What)) {
+    // TODO: possibly use removeMemoryAccess' more efficient RAUW
+    What->replaceAllUsesWith(What->getDefiningAccess());
+    What->setDefiningAccess(Where->getDefiningAccess());
+    Where->setDefiningAccess(What);
+  }
+  AccessList *Src = getWritableBlockAccesses(What->getBlock());
+  AccessList *Dest = getWritableBlockAccesses(Where->getBlock());
+  Dest->splice(AccessList::iterator(Where), *Src, What);
+
+  BlockNumberingValid.erase(What->getBlock());
+  if (What->getBlock() != Where->getBlock())
+    BlockNumberingValid.erase(Where->getBlock());
+}
+
 /// \brief Helper function to create new memory accesses
 MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I) {
   // The assume intrinsic has a control dependency which we model by claiming
   // that it writes arbitrarily. Ignore that fake memory dependency here.
   // FIXME: Replace this special casing with a more accurate modelling of
   // assume's control dependency.
   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
     if (II->getIntrinsicID() == Intrinsic::assume)

llvm/trunk/unittests/Transforms/Utils/MemorySSA.cpp

TEST_F(MemorySSATest, WalkerReopt) {
 
   // Create the load memory access pointing to an unoptimized place.
   MemoryUse *NewLoadAccess = cast<MemoryUse>(MSSA.createMemoryAccessInBB(
       LIA, MSSA.getMemoryAccess(SIB), LIA->getParent(), MemorySSA::End));
   // This should it cause it to be optimized
   EXPECT_EQ(Walker->getClobberingMemoryAccess(NewLoadAccess), LoadClobber);
   EXPECT_EQ(NewLoadAccess->getDefiningAccess(), LoadClobber);
 }
+
+// Test out MemorySSA::spliceMemoryAccessAbove.
+TEST_F(MemorySSATest, SpliceAboveMemoryDef) {
+  F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
+                       GlobalValue::ExternalLinkage, "F", &M);
+  B.SetInsertPoint(BasicBlock::Create(C, "", F));
+
+  Type *Int8 = Type::getInt8Ty(C);
+  Value *A = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
+  Value *B_ = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B");
+  Value *C = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "C");
+
+  StoreInst *StoreA0 = B.CreateStore(ConstantInt::get(Int8, 0), A);
+  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);
+
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+  MemorySSAWalker &Walker = *Analyses->Walker;
+
+  StoreC->moveBefore(StoreB);
+  MSSA.spliceMemoryAccessAbove(cast<MemoryDef>(MSSA.getMemoryAccess(StoreB)),
+                               MSSA.getMemoryAccess(StoreC));
+
+  MSSA.verifyMemorySSA();
+
+  EXPECT_EQ(MSSA.getMemoryAccess(StoreB)->getDefiningAccess(),
+            MSSA.getMemoryAccess(StoreC));
+  EXPECT_EQ(MSSA.getMemoryAccess(StoreC)->getDefiningAccess(),
+            MSSA.getMemoryAccess(StoreA0));
+  EXPECT_EQ(MSSA.getMemoryAccess(StoreA2)->getDefiningAccess(),
+            MSSA.getMemoryAccess(StoreA1));
+  EXPECT_EQ(Walker.getClobberingMemoryAccess(LoadB),
+            MSSA.getMemoryAccess(StoreB));
+  EXPECT_EQ(Walker.getClobberingMemoryAccess(LoadC),
+            MSSA.getMemoryAccess(StoreC));
+
+  // exercise block numbering
+  EXPECT_TRUE(MSSA.locallyDominates(MSSA.getMemoryAccess(StoreC),
+                                    MSSA.getMemoryAccess(StoreB)));
+  EXPECT_TRUE(MSSA.locallyDominates(MSSA.getMemoryAccess(StoreA1),
+                                    MSSA.getMemoryAccess(StoreA2)));
+}