[DTU] Refine the interface and logic of applyUpdates

Summary:
This patch separates two semantics of `applyUpdates`:
1. User provides an accurate CFG diff and the dominator tree is updated according to the difference of `the number of edge insertions` and `the number of edge deletions` to infer the status of an edge before and after the update.
2. User provides a sequence of hints. Updates mentioned in this sequence might never happened and even duplicated.

Logic changes:

Previously, removing invalid updates is considered a side-effect of deduplication and is not guaranteed to be reliable. To handle the second semantic, `applyUpdates` does validity checking before deduplication, which can cause updates that have already been applied to be submitted again. Then, different calls to `applyUpdates` might cause unintended consequences, for example,
```
DTU(Lazy) and Edge A->B exists.
1. DTU.applyUpdates({{Delete, A, B}, {Insert, A, B}}) // User expects these 2 updates result in a no-op, but {Insert, A, B} is queued
2. Remove A->B
3. DTU.applyUpdates({{Delete, A, B}}) // DTU cancels this update with {Insert, A, B} mentioned above together (Unintended)
```
But by restricting the precondition that updates of an edge need to be strictly ordered as how CFG changes were made, we can infer the initial status of this edge to resolve this issue.

Interface changes:
The second semantic of `applyUpdates`  is separated to `applyUpdatesPermissive`.
These changes enable DTU(Lazy) to use the first semantic if needed, which is quite useful in `transforms/utils`.

Reviewers: kuhar, brzycki, dmgreen, grosser

Reviewed By: brzycki

Subscribers: hiraditya, llvm-commits

Tags: #llvm

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

llvm-svn: 354669

1 files changed, 88 insertions, 25 deletions

diff --git a/llvm/unittests/Analysis/DomTreeUpdaterTest.cpp b/llvm/unittests/Analysis/DomTreeUpdaterTest.cpp
index a1154a3bfbb..4a5e2d73f96 100644
--- a/llvm/unittests/Analysis/DomTreeUpdaterTest.cpp
+++ b/llvm/unittests/Analysis/DomTreeUpdaterTest.cpp
@@ -71,9 +71,9 @@ TEST(DomTreeUpdater, EagerUpdateBasicOperations) {
   SwitchInst *SI = dyn_cast<SwitchInst>(BB0->getTerminator());
   ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst.";
 
-  DTU.applyUpdates(
-      {{DominatorTree::Insert, BB0, BB0}, {DominatorTree::Delete, BB0, BB0}},
-      /*ForceRemoveDuplicates*/ true);
+  DTU.applyUpdatesPermissive(
+      {{DominatorTree::Insert, BB0, BB0}, {DominatorTree::Delete, BB0, BB0}});
+  ASSERT_FALSE(DTU.hasPendingUpdates());
 
   // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
   // entries are discarded.
@@ -102,14 +102,13 @@ TEST(DomTreeUpdater, EagerUpdateBasicOperations) {
   // queued for deletion.
   ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
   EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
-  DTU.applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+  DTU.applyUpdatesPermissive(Updates);
   ASSERT_FALSE(DTU.hasPendingUpdates());
 
   // Invalid Insert: no edge bb1 -> bb2 after change to bb0.
   // Invalid Delete: edge exists bb0 -> bb1 after change to bb0.
-  DTU.applyUpdates(
-      {{DominatorTree::Insert, BB1, BB2}, {DominatorTree::Delete, BB0, BB1}},
-      /*ForceRemoveDuplicates*/ true);
+  DTU.applyUpdatesPermissive(
+      {{DominatorTree::Insert, BB1, BB2}, {DominatorTree::Delete, BB0, BB1}});
 
   // DTU working with Eager UpdateStrategy does not need to flush.
   ASSERT_TRUE(DT.verify());
@@ -184,8 +183,7 @@ TEST(DomTreeUpdater, EagerUpdateReplaceEntryBB) {
   EXPECT_EQ(F->begin()->getName(), NewEntry->getName());
   EXPECT_TRUE(&F->getEntryBlock() == NewEntry);
 
-  DTU.applyUpdates({{DominatorTree::Insert, NewEntry, BB0}},
-                   /*ForceRemoveDuplicates*/ true);
+  DTU.applyUpdates({{DominatorTree::Insert, NewEntry, BB0}});
 
   // Changing the Entry BB requires a full recalculation of DomTree.
   DTU.recalculate(*F);
@@ -254,7 +252,7 @@ TEST(DomTreeUpdater, LazyUpdateDTBasicOperations) {
   BasicBlock *BB3 = &*FI++;
 
   // Test discards of self-domination update.
-  DTU.applyUpdates({{DominatorTree::Delete, BB0, BB0}});
+  DTU.applyUpdatesPermissive({{DominatorTree::Insert, BB0, BB0}});
   ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
 
   // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
@@ -277,7 +275,7 @@ TEST(DomTreeUpdater, LazyUpdateDTBasicOperations) {
 
   // Verify. Updates to DTU must be applied *after* all changes to the CFG
   // (including block deletion).
-  DTU.applyUpdates(Updates);
+  DTU.applyUpdatesPermissive(Updates);
   ASSERT_TRUE(DTU.getDomTree().verify());
 
   // Deletion of a BasicBlock is an immediate event. We remove all uses to the
@@ -362,9 +360,9 @@ TEST(DomTreeUpdater, LazyUpdateDTInheritedPreds) {
   //
   // While the final CFG form is functionally identical the updates to
   // DTU are not. In the first case we must have
-  // DTU.applyUpdates({{DominatorTree::Insert, Pred1, Succ}}) while in the
-  // latter case we must *NOT* have DTU.applyUpdates({{DominatorTree::Insert,
-  // Pred1, Succ}}).
+  // DTU.applyUpdates({{DominatorTree::Insert, Pred1, Succ}}) while in
+  // the latter case we must *NOT* have
+  // DTU.applyUpdates({{DominatorTree::Insert, Pred1, Succ}}).
 
   // CFG Change: bb0 now only has bb0 -> bb1 and bb0 -> bb3. We are preparing to
   // remove bb2.
@@ -384,9 +382,9 @@ TEST(DomTreeUpdater, LazyUpdateDTInheritedPreds) {
         BasicBlocks.end());
   };
   ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(2));
-  // Remove bb2 from F. This has to happen before the call to applyUpdates() for
-  // DTU to detect there is no longer an edge between bb2 -> bb3. The deleteBB()
-  // method converts bb2's TI into "unreachable".
+  // Remove bb2 from F. This has to happen before the call to
+  // applyUpdates() for DTU to detect there is no longer an edge between
+  // bb2 -> bb3. The deleteBB() method converts bb2's TI into "unreachable".
   ASSERT_FALSE(isa<UnreachableInst>(BB2->getTerminator()));
   EXPECT_FALSE(DTU.isBBPendingDeletion(BB2));
   DTU.callbackDeleteBB(BB2, Eraser);
@@ -407,9 +405,9 @@ TEST(DomTreeUpdater, LazyUpdateDTInheritedPreds) {
   BranchInst::Create(BB3, BB0);
   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
 
-  // Remove bb1 from F. This has to happen before the call to applyUpdates() for
-  // DTU to detect there is no longer an edge between bb1 -> bb3. The deleteBB()
-  // method converts bb1's TI into "unreachable".
+  // Remove bb1 from F. This has to happen before the call to
+  // applyUpdates() for DTU to detect there is no longer an edge between
+  // bb1 -> bb3. The deleteBB() method converts bb1's TI into "unreachable".
   ASSERT_FALSE(isa<UnreachableInst>(BB1->getTerminator()));
   EXPECT_FALSE(DTU.isBBPendingDeletion(BB1));
   DTU.callbackDeleteBB(BB1, Eraser);
@@ -424,7 +422,7 @@ TEST(DomTreeUpdater, LazyUpdateDTInheritedPreds) {
   Updates.push_back({DominatorTree::Delete, BB1, BB3});
 
   // Verify everything.
-  DTU.applyUpdates(Updates);
+  DTU.applyUpdatesPermissive(Updates);
   ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(2));
   DTU.flush();
   ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(0));
@@ -509,7 +507,7 @@ TEST(DomTreeUpdater, LazyUpdateBasicOperations) {
 
   // Verify. Updates to DTU must be applied *after* all changes to the CFG
   // (including block deletion).
-  DTU.applyUpdates(Updates);
+  DTU.applyUpdatesPermissive(Updates);
   ASSERT_TRUE(DTU.getDomTree().verify());
   ASSERT_TRUE(DTU.hasPendingUpdates());
   ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates());
@@ -648,8 +646,7 @@ TEST(DomTreeUpdater, LazyUpdateStepTest) {
   SwitchInst *SI = dyn_cast<SwitchInst>(BB0->getTerminator());
   ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst.";
 
-  // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
-  // entries are discarded.
+  // Delete edge bb0 -> bb3.
   std::vector<DominatorTree::UpdateType> Updates;
   Updates.reserve(1);
   Updates.push_back({DominatorTree::Delete, BB0, BB3});
@@ -694,7 +691,7 @@ TEST(DomTreeUpdater, LazyUpdateStepTest) {
       ++i;
   }
 
-  DTU.applyUpdates(Updates);
+  DTU.applyUpdatesPermissive(Updates);
   // flush PostDomTree
   ASSERT_TRUE(DTU.getPostDomTree().verify());
   ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates());
@@ -729,3 +726,69 @@ TEST(DomTreeUpdater, NoTreeTest) {
   DTU.recalculate(*F);
   ASSERT_FALSE(DTU.hasPendingDeletedBB());
 }
+
+TEST(DomTreeUpdater, LazyUpdateDeduplicationTest) {
+  StringRef FuncName = "f";
+  StringRef ModuleString = R"(
+                           define i32 @f() {
+                           bb0:
+                              br label %bb1
+                           bb1:
+                              ret i32 1
+                           bb2:
+                              ret i32 1
+                           }
+                           )";
+  // Make the module.
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+  Function *F = M->getFunction(FuncName);
+
+  // Make the DTU.
+  DominatorTree DT(*F);
+  DomTreeUpdater DTU(&DT, nullptr, DomTreeUpdater::UpdateStrategy::Lazy);
+  ASSERT_TRUE(DTU.getDomTree().verify());
+
+  Function::iterator FI = F->begin();
+  BasicBlock *BB0 = &*FI++;
+  BasicBlock *BB1 = &*FI++;
+  BasicBlock *BB2 = &*FI++;
+
+  // CFG Change: remove bb0 -> bb1 and add back bb0 -> bb1.
+  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
+  BB0->getTerminator()->eraseFromParent();
+  BranchInst::Create(BB1, BB0);
+  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
+
+  // Update the DTU and simulate duplicates.
+  DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB0, BB1},
+                              {DominatorTree::Delete, BB0, BB1},
+                              {DominatorTree::Insert, BB0, BB1},
+                              {DominatorTree::Insert, BB0, BB1},
+                              {DominatorTree::Insert, BB0, BB1}});
+
+  // The above operations result in a no-op.
+  ASSERT_FALSE(DTU.hasPendingUpdates());
+
+  // Update the DTU. Simulate an invalid update.
+  DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB0, BB1}});
+  ASSERT_FALSE(DTU.hasPendingUpdates());
+
+  // CFG Change: remove bb0 -> bb1.
+  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
+  BB0->getTerminator()->eraseFromParent();
+
+  // Update the DTU and simulate invalid updates.
+  DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB0, BB1},
+                              {DominatorTree::Insert, BB0, BB1},
+                              {DominatorTree::Delete, BB0, BB1},
+                              {DominatorTree::Insert, BB0, BB1},
+                              {DominatorTree::Insert, BB0, BB1}});
+  ASSERT_TRUE(DTU.hasPendingUpdates());
+
+  // CFG Change: add bb0 -> bb2.
+  BranchInst::Create(BB2, BB0);
+  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
+  DTU.applyUpdates({{DominatorTree::Insert, BB0, BB2}});
+  ASSERT_TRUE(DTU.getDomTree().verify());
+}