[mssa] If there is no definition in a block prior to an inserted use, return nullptr.

[asbirlea]

Summary

Check that the first access before one being tested is valid.
Before this patch, if there was no definition prior to the Use being tested,
the first time Iter was deferenced, it hit the sentinel.
Patch updates the check and return nullptr.

[davide]

Can you write an updater unittest for this case?

[asbirlea]

Yes, working in it.

[george.burgess.iv]

Thanks for the patch!

lib/Analysis/MemorySSAUpdater.cpp

126

If we instead refactor this else block to look something like:

auto End = getWritableBlockAccesses()->rend();
for (auto &U : make_range(++MA->getReverseIterator(), End))
  if (!isa<MemoryUse>(U))
    return cast<MemoryAccess>(&U);
// Note that if MA comes before Defs->begin(), we won't hit a def.
return nullptr;

does that still fix the problem?

Personally, I feel like that's clearer about the intent, and is probably less prone to edge-cases.

126

Oops; I meant:

auto End = getWritableBlockAccesses(MA->getBlock())->rend();

[• dberlin]

lib/Analysis/MemorySSAUpdater.cpp

126

I was going to suggest the same thing george did :)

[asbirlea]

Updated per George's suggestion.
Added unit test.

[george.burgess.iv]

Thanks again!

lib/Analysis/MemorySSAUpdater.cpp

MemoryAccess *MemorySSAUpdater::getPreviousDefInBlock(MemoryAccess *MA) {
   if (Defs) {
     // If this is a def, we can just use the def iterators.
     if (!isa<MemoryUse>(MA)) {
       auto Iter = MA->getReverseDefsIterator();
       ++Iter;
       if (Iter != Defs->rend())
         return &*Iter;
     } else {
       // Otherwise, have to walk the all access iterator.
-      auto Iter = MA->getReverseIterator();
-      ++Iter;
-      while (&*Iter != &*Defs->begin()) {
-        if (!isa<MemoryUse>(*Iter))
-          return &*Iter;
-        --Iter;
-      }
-      // At this point it must be pointing at firstdef
-      assert(&*Iter == &*Defs->begin() &&
-             "Should have hit first def walking backwards");
-      return &*Iter;
+      auto End = MSSA->getWritableBlockAccesses(MA->getBlock())->rend();
+      for (auto &U : make_range(++MA->getReverseIterator(), End))
+        if (!isa<MemoryUse>(U))
+          return cast<MemoryAccess>(&U);
+      // Note that if MA comes before Defs->begin(), we won't hit a def.
+      return nullptr;
     }
   }
   return nullptr;
 }
 
 // This starts at the end of block
 MemoryAccess *MemorySSAUpdater::getPreviousDefFromEnd(BasicBlock *BB) {
   auto *Defs = MSSA->getWritableBlockDefs(BB);

unittests/Analysis/MemorySSA.cpp

TEST_F(MemorySSATest, CreateALoadUpdater) {
   MemoryUse *LoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
       LoadInst, nullptr, Merge, MemorySSA::Beginning));
   Updater.insertUse(LoadAccess);
   MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();
   EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));
   MSSA.verifyMemorySSA();
 }
 
+TEST_F(MemorySSATest, SinkLoad) {
+  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);
+
+  // Load in left block
+  B.SetInsertPoint(Left, Left->begin());
+  LoadInst *LoadInst1 = B.CreateLoad(PointerArg);
+  // Store in merge block
+  B.SetInsertPoint(Merge, Merge->begin());
+  B.CreateStore(B.getInt8(16), PointerArg);
+
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+  MemorySSAUpdater Updater(&MSSA);
+
+  // Mimic sinking of a load:
+  // - clone load
+  // - insert in "exit" block
+  // - insert in mssa
+  // - remove from original block
+
+  LoadInst *LoadInstClone = cast<LoadInst>(LoadInst1->clone());
+  Merge->getInstList().insert(Merge->begin(), LoadInstClone);
+  MemoryAccess * NewLoadAccess =
+      Updater.createMemoryAccessInBB(LoadInstClone, nullptr,
+                                     LoadInstClone->getParent(),
+                                     MemorySSA::Beginning);
+  Updater.insertUse(cast<MemoryUse>(NewLoadAccess));
+  MSSA.verifyMemorySSA();
+  Updater.removeMemoryAccess(MSSA.getMemoryAccess(LoadInst1));
+  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. This destroys the old
   // access.
   F = Function::Create(
       FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
       GlobalValue::ExternalLinkage, "F", &M);