From e156d99231a7735d06a97b5b83de70bf4ce4f034 Mon Sep 17 00:00:00 2001
From: Alina Sbirlea <asbirlea@google.com>
Date: Wed, 7 Jun 2017 16:46:53 +0000
Subject: [PATCH] [mssa] Fix case when there is no definition in a block prior
 to an inserted use.

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.

Reviewers: dberlin, gbiv

Subscribers: sanjoy, Prazek, llvm-commits

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@304926 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Analysis/MemorySSAUpdater.cpp | 17 ++++--------
 unittests/Analysis/MemorySSA.cpp  | 46 +++++++++++++++++++++++++++++++
 2 files changed, 52 insertions(+), 11 deletions(-)

diff --git a/lib/Analysis/MemorySSAUpdater.cpp b/lib/Analysis/MemorySSAUpdater.cpp
index 86a4eb66fc9..1ff84471c09 100644
--- a/lib/Analysis/MemorySSAUpdater.cpp
+++ b/lib/Analysis/MemorySSAUpdater.cpp
@@ -124,17 +124,12 @@ MemoryAccess *MemorySSAUpdater::getPreviousDefInBlock(MemoryAccess *MA) {
         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;
diff --git a/unittests/Analysis/MemorySSA.cpp b/unittests/Analysis/MemorySSA.cpp
index 7295591f7b6..affa0e71820 100644
--- a/unittests/Analysis/MemorySSA.cpp
+++ b/unittests/Analysis/MemorySSA.cpp
@@ -244,6 +244,52 @@ TEST_F(MemorySSATest, CreateALoadUpdater) {
   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
-- 
2.50.1