[MemorySSA] Clear VisitedBlocks per query

[Whitney]

Summary

I am not sure my fix is the best approach, but it fixes the assertion of "Incomplete phi during partial rename". Could it be an issue with how I use the MemorySSAUpdater in the test case?

The problem can be shown from the newly added test case.
There are two invocations to MemorySSAUpdater::moveToPlace, and the internal data structure VisitedBlocks is changed in the first invocation, and reused in the second invocation. In between the two invocations, there is a change to the CFG, and MemorySSAUpdater is notified about the change.

[asbirlea]

I think the clearing should be added at the beginning of insertDef and insertUse. A similar clearing is done on visited phis at the same two places. I didn't get a chance to test it yet though.

[Whitney]

Verified that clearing at the beginning of insertDef and insertUse can resolve the problem shown in the test case.

[asbirlea]

lgtm

llvm/lib/Analysis/MemorySSAUpdater.cpp

MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi,
   }
 
   // We should only end up recursing in case we replaced something, in which
   // case, we may have made other Phis trivial.
   return recursePhi(Same);
 }
 
 void MemorySSAUpdater::insertUse(MemoryUse *MU, bool RenameUses) {
+  VisitedBlocks.clear();
   InsertedPHIs.clear();
   MU->setDefiningAccess(getPreviousDef(MU));
 
   // In cases without unreachable blocks, because uses do not create new
   // may-defs, there are only two cases:
   // 1. There was a def already below us, and therefore, we should not have
   // created a phi node because it was already needed for the def.
   //

 
 // A brief description of the algorithm:
 // First, we compute what should define the new def, using the SSA
 // construction algorithm.
 // Then, we update the defs below us (and any new phi nodes) in the graph to
 // point to the correct new defs, to ensure we only have one variable, and no
 // disconnected stores.
 void MemorySSAUpdater::insertDef(MemoryDef *MD, bool RenameUses) {
+  VisitedBlocks.clear();
   InsertedPHIs.clear();
 
   // See if we had a local def, and if not, go hunting.
   MemoryAccess *DefBefore = getPreviousDef(MD);
   bool DefBeforeSameBlock = false;
   if (DefBefore->getBlock() == MD->getBlock() &&
       !(isa<MemoryPhi>(DefBefore) &&
         llvm::is_contained(InsertedPHIs, DefBefore)))

llvm/unittests/Analysis/MemorySSATest.cpp

TEST_F(MemorySSATest, TestInvariantGroup) {
 
   {
     MemoryAccess *CallAccess = MSSA.getMemoryAccess(&Call);
     MemoryAccess *LAccess = MSSA.getMemoryAccess(&LI);
     MemoryAccess *LClobber = Walker->getClobberingMemoryAccess(LAccess);
     EXPECT_EQ(CallAccess, LClobber);
   }
 }
+
+static BasicBlock *getBasicBlockByName(Function &F, StringRef Name) {
+  for (BasicBlock &BB : F)
+    if (BB.getName() == Name)
+      return &BB;
+  llvm_unreachable("Expected to find basic block!");
+}
+
+static Instruction *getInstructionByName(Function &F, StringRef Name) {
+  for (BasicBlock &BB : F)
+    for (Instruction &I : BB)
+      if (I.getName() == Name)
+        return &I;
+  llvm_unreachable("Expected to find instruction!");
+}
+
+TEST_F(MemorySSATest, TestVisitedBlocks) {
+  SMDiagnostic E;
+  auto M = parseAssemblyString(
+      "define void @test(i64* noalias %P, i64 %N) {\n"
+      "preheader.n:\n"
+      "  br label %header.n\n"
+      "header.n:\n"
+      "  %n = phi i64 [ 0, %preheader.n ], [ %inc.n, %latch.n ]\n"
+      "  %guard.cond.i = icmp slt i64 0, %N\n"
+      "  br i1 %guard.cond.i, label %header.i.check, label %other.i\n"
+      "header.i.check:\n"
+      "  br label %preheader.i\n"
+      "preheader.i:\n"
+      "  br label %header.i\n"
+      "header.i:\n"
+      "  %i = phi i64 [ 0, %preheader.i ], [ %inc.i, %header.i ]\n"
+      "  %v1 = load i64, i64* %P, align 8\n"
+      "  %v2 = load i64, i64* %P, align 8\n"
+      "  %inc.i = add nsw i64 %i, 1\n"
+      "  %cmp.i = icmp slt i64 %inc.i, %N\n"
+      "  br i1 %cmp.i, label %header.i, label %exit.i\n"
+      "exit.i:\n"
+      "  br label %commonexit\n"
+      "other.i:\n"
+      "  br label %commonexit\n"
+      "commonexit:\n"
+      "  br label %latch.n\n"
+      "latch.n:\n"
+      "  %inc.n = add nsw i64 %n, 1\n"
+      "  %cmp.n = icmp slt i64 %inc.n, %N\n"
+      "  br i1 %cmp.n, label %header.n, label %exit.n\n"
+      "exit.n:\n"
+      "  ret void\n"
+      "}\n",
+      E, C);
+  ASSERT_TRUE(M);
+  F = M->getFunction("test");
+  ASSERT_TRUE(F);
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+  MemorySSAUpdater Updater(&MSSA);
+
+  {
+    // Move %v1 before the terminator of %header.i.check
+    BasicBlock *BB = getBasicBlockByName(*F, "header.i.check");
+    Instruction *LI = getInstructionByName(*F, "v1");
+    LI->moveBefore(BB->getTerminator());
+    if (MemoryUseOrDef *MUD = MSSA.getMemoryAccess(LI))
+      Updater.moveToPlace(MUD, BB, MemorySSA::BeforeTerminator);
+
+    // Change the termiantor of %header.i.check to `br label true, label
+    // %preheader.i, label %other.i`
+    BB->getTerminator()->eraseFromParent();
+    ConstantInt *BoolTrue = ConstantInt::getTrue(F->getContext());
+    BranchInst::Create(getBasicBlockByName(*F, "preheader.i"),
+                       getBasicBlockByName(*F, "other.i"), BoolTrue, BB);
+    SmallVector<DominatorTree::UpdateType, 4> DTUpdates;
+    DTUpdates.push_back(DominatorTree::UpdateType(
+        DominatorTree::Insert, BB, getBasicBlockByName(*F, "other.i")));
+    Updater.applyUpdates(DTUpdates, Analyses->DT, true);
+  }
+
+  // After the first moveToPlace(), %other.i is in VisitedBlocks, even after
+  // there is a new edge to %other.i, which makes the second moveToPlace()
+  // traverse incorrectly.
+  {
+    // Move %v2 before the terminator of %preheader.i
+    BasicBlock *BB = getBasicBlockByName(*F, "preheader.i");
+    Instruction *LI = getInstructionByName(*F, "v2");
+    LI->moveBefore(BB->getTerminator());
+    // Check that there is no assertion of "Incomplete phi during partial
+    // rename"
+    if (MemoryUseOrDef *MUD = MSSA.getMemoryAccess(LI))
+      Updater.moveToPlace(MUD, BB, MemorySSA::BeforeTerminator);
+  }
+}