1 files changed, 64 insertions, 59 deletions

diff --git a/llvm/lib/Analysis/DomTreeUpdater.cpp b/llvm/lib/Analysis/DomTreeUpdater.cpp
index e4d505b8f1a..49215889cfd 100644
--- a/llvm/lib/Analysis/DomTreeUpdater.cpp
+++ b/llvm/lib/Analysis/DomTreeUpdater.cpp
@@ -12,11 +12,13 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/DomTreeUpdater.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/Support/GenericDomTree.h"
 #include <algorithm>
 #include <functional>
+#include <utility>
 
 namespace llvm {
 
@@ -53,41 +55,6 @@ bool DomTreeUpdater::isSelfDominance(
   return Update.getFrom() == Update.getTo();
 }
 
-bool DomTreeUpdater::applyLazyUpdate(DominatorTree::UpdateKind Kind,
-                                     BasicBlock *From, BasicBlock *To) {
-  assert((DT || PDT) &&
-         "Call applyLazyUpdate() when both DT and PDT are nullptrs.");
-  assert(Strategy == DomTreeUpdater::UpdateStrategy::Lazy &&
-         "Call applyLazyUpdate() with Eager strategy error");
-  // Analyze pending updates to determine if the update is unnecessary.
-  const DominatorTree::UpdateType Update = {Kind, From, To};
-  const DominatorTree::UpdateType Invert = {Kind != DominatorTree::Insert
-                                                ? DominatorTree::Insert
-                                                : DominatorTree::Delete,
-                                            From, To};
-  // Only check duplicates in updates that are not applied by both trees.
-  auto I =
-      PendUpdates.begin() + std::max(PendDTUpdateIndex, PendPDTUpdateIndex);
-  const auto E = PendUpdates.end();
-
-  assert(I <= E && "Iterator out of range.");
-
-  for (; I != E; ++I) {
-    if (Update == *I)
-      return false; // Discard duplicate updates.
-
-    if (Invert == *I) {
-      // Update and Invert are both valid (equivalent to a no-op). Remove
-      // Invert from PendUpdates and discard the Update.
-      PendUpdates.erase(I);
-      return false;
-    }
-  }
-
-  PendUpdates.push_back(Update); // Save the valid update.
-  return true;
-}
-
 void DomTreeUpdater::applyDomTreeUpdates() {
   // No pending DomTreeUpdates.
   if (Strategy != UpdateStrategy::Lazy || !DT)
@@ -261,31 +228,15 @@ void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) {
   new UnreachableInst(DelBB->getContext(), DelBB);
 }
 
-void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
-                                  bool ForceRemoveDuplicates) {
+void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates) {
   if (!DT && !PDT)
     return;
 
-  if (Strategy == UpdateStrategy::Lazy || ForceRemoveDuplicates) {
-    SmallVector<DominatorTree::UpdateType, 8> Seen;
+  if (Strategy == UpdateStrategy::Lazy) {
     for (const auto U : Updates)
-      // For Lazy UpdateStrategy, avoid duplicates to applyLazyUpdate() to save
-      // on analysis.
-      if (llvm::none_of(
-              Seen,
-              [U](const DominatorTree::UpdateType S) { return S == U; }) &&
-          isUpdateValid(U) && !isSelfDominance(U)) {
-        Seen.push_back(U);
-        if (Strategy == UpdateStrategy::Lazy)
-          applyLazyUpdate(U.getKind(), U.getFrom(), U.getTo());
-      }
-    if (Strategy == UpdateStrategy::Lazy)
-      return;
+      if (!isSelfDominance(U))
+        PendUpdates.push_back(U);
 
-    if (DT)
-      DT->applyUpdates(Seen);
-    if (PDT)
-      PDT->applyUpdates(Seen);
     return;
   }
 
@@ -295,6 +246,60 @@ void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
     PDT->applyUpdates(Updates);
 }
 
+void DomTreeUpdater::applyUpdatesPermissive(
+    ArrayRef<DominatorTree::UpdateType> Updates) {
+  if (!DT && !PDT)
+    return;
+
+  SmallSet<std::pair<BasicBlock *, BasicBlock *>, 8> Seen;
+  SmallVector<DominatorTree::UpdateType, 8> DeduplicatedUpdates;
+  for (const auto U : Updates) {
+    auto Edge = std::make_pair(U.getFrom(), U.getTo());
+    // Because it is illegal to submit updates that have already been applied
+    // and updates to an edge need to be strictly ordered,
+    // it is safe to infer the existence of an edge from the first update
+    // to this edge.
+    // If the first update to an edge is "Delete", it means that the edge
+    // existed before. If the first update to an edge is "Insert", it means
+    // that the edge didn't exist before.
+    //
+    // For example, if the user submits {{Delete, A, B}, {Insert, A, B}},
+    // because
+    // 1. it is illegal to submit updates that have already been applied,
+    // i.e., user cannot delete an nonexistent edge,
+    // 2. updates to an edge need to be strictly ordered,
+    // So, initially edge A -> B existed.
+    // We can then safely ignore future updates to this edge and directly
+    // inspect the current CFG:
+    // a. If the edge still exists, because the user cannot insert an existent
+    // edge, so both {Delete, A, B}, {Insert, A, B} actually happened and
+    // resulted in a no-op. DTU won't submit any update in this case.
+    // b. If the edge doesn't exist, we can then infer that {Delete, A, B}
+    // actually happened but {Insert, A, B} was an invalid update which never
+    // happened. DTU will submit {Delete, A, B} in this case.
+    if (!isSelfDominance(U) && Seen.count(Edge) == 0) {
+      Seen.insert(Edge);
+      // If the update doesn't appear in the CFG, it means that
+      // either the change isn't made or relevant operations
+      // result in a no-op.
+      if (isUpdateValid(U)) {
+        if (isLazy())
+          PendUpdates.push_back(U);
+        else
+          DeduplicatedUpdates.push_back(U);
+      }
+    }
+  }
+
+  if (Strategy == UpdateStrategy::Lazy)
+    return;
+
+  if (DT)
+    DT->applyUpdates(DeduplicatedUpdates);
+  if (PDT)
+    PDT->applyUpdates(DeduplicatedUpdates);
+}
+
 DominatorTree &DomTreeUpdater::getDomTree() {
   assert(DT && "Invalid acquisition of a null DomTree");
   applyDomTreeUpdates();
@@ -331,7 +336,7 @@ void DomTreeUpdater::insertEdge(BasicBlock *From, BasicBlock *To) {
     return;
   }
 
-  applyLazyUpdate(DominatorTree::Insert, From, To);
+  PendUpdates.push_back({DominatorTree::Insert, From, To});
 }
 
 void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
@@ -352,7 +357,7 @@ void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
     return;
   }
 
-  applyLazyUpdate(DominatorTree::Insert, From, To);
+  PendUpdates.push_back({DominatorTree::Insert, From, To});
 }
 
 void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) {
@@ -377,7 +382,7 @@ void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) {
     return;
   }
 
-  applyLazyUpdate(DominatorTree::Delete, From, To);
+  PendUpdates.push_back({DominatorTree::Delete, From, To});
 }
 
 void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
@@ -398,7 +403,7 @@ void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
     return;
   }
 
-  applyLazyUpdate(DominatorTree::Delete, From, To);
+  PendUpdates.push_back({DominatorTree::Delete, From, To});
 }
 
 void DomTreeUpdater::dropOutOfDateUpdates() {