[DTU] Deprecate insertEdge*/deleteEdge*

[NutshellySima]

Summary

This patch converts all existing insertEdge*/deleteEdge* to applyUpdates and marks insertEdge*/deleteEdge* as deprecated.

[kuhar]

Great, thanks for putting effort into this and the related patches

[brzycki]

+1 Thank you. LGTM.

llvm/include/llvm/Analysis/DomTreeUpdater.h

public:
   void recalculate(Function &F);
 
   /// \deprecated { Submit an edge insertion to all available trees. The Eager
   /// Strategy flushes this update immediately while the Lazy Strategy queues
   /// the update. An internal function checks if the edge exists in the CFG in
   /// DEBUG mode. CAUTION! This function has to be called *after* making the
   /// update on the actual CFG. It is illegal to submit any update that has
   /// already been applied. }
-  void insertEdge(BasicBlock *From, BasicBlock *To);
+  LLVM_ATTRIBUTE_DEPRECATED(void insertEdge(BasicBlock *From, BasicBlock *To),
+                            "Use applyUpdates() instead.");
 
   /// \deprecated {Submit an edge insertion to all available trees.
   /// Under either Strategy, an invalid update will be discard silently.
   /// Invalid update means inserting an edge that does not exist in the CFG.
   /// The Eager Strategy flushes this update immediately while the Lazy Strategy
   /// queues the update. It is only recommended to use this method when you
   /// want to discard an invalid update.
   /// CAUTION! It is illegal to submit any update that has already been
   /// submitted. }
-  void insertEdgeRelaxed(BasicBlock *From, BasicBlock *To);
+  LLVM_ATTRIBUTE_DEPRECATED(void insertEdgeRelaxed(BasicBlock *From,
+                                                   BasicBlock *To),
+                            "Use applyUpdates() instead.");
 
   /// \deprecated { Submit an edge deletion to all available trees. The Eager
   /// Strategy flushes this update immediately while the Lazy Strategy queues
   /// the update. An internal function checks if the edge doesn't exist in the
   /// CFG in DEBUG mode.
   /// CAUTION! This function has to be called *after* making the update on the
   /// actual CFG. It is illegal to submit any update that has already been
   /// submitted. }
-  void deleteEdge(BasicBlock *From, BasicBlock *To);
+  LLVM_ATTRIBUTE_DEPRECATED(void deleteEdge(BasicBlock *From, BasicBlock *To),
+                            "Use applyUpdates() instead.");
 
   /// \deprecated { Submit an edge deletion to all available trees.
   /// Under either Strategy, an invalid update will be discard silently.
   /// Invalid update means deleting an edge that exists in the CFG.
   /// The Eager Strategy flushes this update immediately while the Lazy Strategy
   /// queues the update. It is only recommended to use this method when you
   /// want to discard an invalid update.
   /// CAUTION! It is illegal to submit any update that has already been
   /// submitted. }
-  void deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To);
+  LLVM_ATTRIBUTE_DEPRECATED(void deleteEdgeRelaxed(BasicBlock *From,
+                                                   BasicBlock *To),
+                            "Use applyUpdates() instead.");
 
   /// Delete DelBB. DelBB will be removed from its Parent and
   /// erased from available trees if it exists and finally get deleted.
   /// Under Eager UpdateStrategy, DelBB will be processed immediately.
   /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
   /// all available trees are up-to-date. Assert if any instruction of DelBB is
   /// modified while awaiting deletion. When both DT and PDT are nullptrs, DelBB
   /// will be queued until flush() is called.

llvm/lib/Transforms/Scalar/CallSiteSplitting.cpp

if (IsMustTailCall) {
     // Remove superfluous `br` terminators from the end of the Split blocks
     // NOTE: Removing terminator removes the SplitBlock from the TailBB's
     // predecessors. Therefore we must get complete list of Splits before
     // attempting removal.
     SmallVector<BasicBlock *, 2> Splits(predecessors((TailBB)));
     assert(Splits.size() == 2 && "Expected exactly 2 splits!");
     for (unsigned i = 0; i < Splits.size(); i++) {
       Splits[i]->getTerminator()->eraseFromParent();
-      DTU.deleteEdge(Splits[i], TailBB);
+      DTU.applyUpdates({{DominatorTree::Delete, Splits[i], TailBB}});
     }
 
     // Erase the tail block once done with musttail patching
     DTU.deleteBB(TailBB);
     return;
   }
 
   auto *OriginalBegin = &*TailBB->begin();

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

if (State == LazyValueInfo::False) {
 
       // The condition can be modified by removePredecessor's PHI simplification
       // logic.
       Cond = SI->getCondition();
 
       ++NumDeadCases;
       Changed = true;
       if (--SuccessorsCount[Succ] == 0)
-        DTU.deleteEdge(BB, Succ);
+        DTU.applyUpdates({{DominatorTree::Delete, BB, Succ}});
       continue;
     }
     if (State == LazyValueInfo::True) {
       // This case always fires.  Arrange for the switch to be turned into an
       // unconditional branch by replacing the switch condition with the case
       // value.
       SI->setCondition(Case);
       NumDeadCases += SI->getNumCases();

llvm/lib/Transforms/Scalar/JumpThreading.cpp

if (CondBr && CondConst) {
         // including the guards/assumes themselves and the uses before the
         // guard/assume.
         else if (CondCmp->getParent() == BB) {
           auto *CI = Ret == LazyValueInfo::True ?
             ConstantInt::getTrue(CondCmp->getType()) :
             ConstantInt::getFalse(CondCmp->getType());
           ReplaceFoldableUses(CondCmp, CI);
         }
-        DTU->deleteEdgeRelaxed(BB, ToRemoveSucc);
+        DTU->applyUpdates({{DominatorTree::Delete, BB, ToRemoveSucc}});
         return true;
       }
 
       // We did not manage to simplify this branch, try to see whether
       // CondCmp depends on a known phi-select pattern.
       if (TryToUnfoldSelect(CondCmp, BB))
         return true;
     }
while (CurrentPred && Iter++ < ImplicationSearchThreshold) {
     Optional<bool> Implication =
         isImpliedCondition(PBI->getCondition(), Cond, DL, CondIsTrue);
     if (Implication) {
       BasicBlock *KeepSucc = BI->getSuccessor(*Implication ? 0 : 1);
       BasicBlock *RemoveSucc = BI->getSuccessor(*Implication ? 1 : 0);
       RemoveSucc->removePredecessor(BB);
       BranchInst::Create(KeepSucc, BI);
       BI->eraseFromParent();
-      DTU->deleteEdgeRelaxed(BB, RemoveSucc);
+      DTU->applyUpdates({{DominatorTree::Delete, BB, RemoveSucc}});
       return true;
     }
     CurrentBB = CurrentPred;
     CurrentPred = CurrentBB->getSinglePredecessor();
   }
 
   return false;
 }

llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp

static bool eliminateRecursiveTailCall(
 
   // Now that all of the PHI nodes are in place, remove the call and
   // ret instructions, replacing them with an unconditional branch.
   BranchInst *NewBI = BranchInst::Create(OldEntry, Ret);
   NewBI->setDebugLoc(CI->getDebugLoc());
 
   BB->getInstList().erase(Ret);  // Remove return.
   BB->getInstList().erase(CI);   // Remove call.
-  DTU.insertEdge(BB, OldEntry);
+  DTU.applyUpdates({{DominatorTree::Insert, BB, OldEntry}});
   ++NumEliminated;
   return true;
 }
 
 static bool foldReturnAndProcessPred(
     BasicBlock *BB, ReturnInst *Ret, BasicBlock *&OldEntry,
     bool &TailCallsAreMarkedTail, SmallVectorImpl<PHINode *> &ArgumentPHIs,
     bool CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *TTI,

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

ReturnInst *llvm::FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB,
   }
 
   // Update any PHI nodes in the returning block to realize that we no
   // longer branch to them.
   BB->removePredecessor(Pred);
   UncondBranch->eraseFromParent();
 
   if (DTU)
-    DTU->deleteEdge(Pred, BB);
+    DTU->applyUpdates({{DominatorTree::Delete, Pred, BB}});
 
   return cast<ReturnInst>(NewRet);
 }
 
 Instruction *llvm::SplitBlockAndInsertIfThen(Value *Cond,
                                              Instruction *SplitBefore,
                                              bool Unreachable,
                                              MDNode *BranchWeights,

llvm/lib/Transforms/Utils/Local.cpp

if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
       // Let the basic block know that we are letting go of it.  Based on this,
       // it will adjust it's PHI nodes.
       OldDest->removePredecessor(BB);
 
       // Replace the conditional branch with an unconditional one.
       Builder.CreateBr(Destination);
       BI->eraseFromParent();
       if (DTU)
-        DTU->deleteEdgeRelaxed(BB, OldDest);
+        DTU->applyUpdates({{DominatorTree::Delete, BB, OldDest}},
+                          /*ForceRemoveDuplicates*/ true);
       return true;
     }
 
     if (Dest2 == Dest1) {       // Conditional branch to same location?
       // This branch matches something like this:
       //     br bool %cond, label %Dest, label %Dest
       // and changes it into:  br label %Dest
 
for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
                           createBranchWeights(Weights));
         }
         // Remove this entry.
         BasicBlock *ParentBB = SI->getParent();
         DefaultDest->removePredecessor(ParentBB);
         i = SI->removeCase(i);
         e = SI->case_end();
         if (DTU)
-          DTU->deleteEdgeRelaxed(ParentBB, DefaultDest);
+          DTU->applyUpdates({{DominatorTree::Delete, ParentBB, DefaultDest}},
+                            /*ForceRemoveDuplicates*/ true);
         continue;
       }
 
       // Otherwise, check to see if the switch only branches to one destination.
       // We do this by reseting "TheOnlyDest" to null when we find two non-equal
       // destinations.
       if (i->getCaseSuccessor() != TheOnlyDest)
         TheOnlyDest = nullptr;
if (!recursivelySimplifyInstruction(PN))
       continue;
 
     // If recursive simplification ended up deleting the next PHI node we would
     // iterate to, then our iterator is invalid, restart scanning from the top
     // of the block.
     if (PhiIt != OldPhiIt) PhiIt = &BB->front();
   }
   if (DTU)
-    DTU->deleteEdgeRelaxed(Pred, BB);
+    DTU->applyUpdates({{DominatorTree::Delete, Pred, BB}},
+                      /*ForceRemoveDuplicates*/ true);
 }
 
 /// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its
 /// predecessor is known to have one successor (DestBB!). Eliminate the edge
 /// between them, moving the instructions in the predecessor into DestBB and
 /// deleting the predecessor block.
 void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB,
                                        DomTreeUpdater *DTU) {
static void changeToCall(InvokeInst *II, DomTreeUpdater *DTU = nullptr) {
   BranchInst::Create(NormalDestBB, II);
 
   // Update PHI nodes in the unwind destination
   BasicBlock *BB = II->getParent();
   BasicBlock *UnwindDestBB = II->getUnwindDest();
   UnwindDestBB->removePredecessor(BB);
   II->eraseFromParent();
   if (DTU)
-    DTU->deleteEdgeRelaxed(BB, UnwindDestBB);
+    DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}},
+                      /*ForceRemoveDuplicates*/ true);
 }
 
 BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI,
                                                    BasicBlock *UnwindEdge) {
   BasicBlock *BB = CI->getParent();
 
   // Convert this function call into an invoke instruction.  First, split the
   // basic block.
if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
         if (II->use_empty() && II->onlyReadsMemory()) {
           // jump to the normal destination branch.
           BasicBlock *NormalDestBB = II->getNormalDest();
           BasicBlock *UnwindDestBB = II->getUnwindDest();
           BranchInst::Create(NormalDestBB, II);
           UnwindDestBB->removePredecessor(II->getParent());
           II->eraseFromParent();
           if (DTU)
-            DTU->deleteEdgeRelaxed(BB, UnwindDestBB);
+            DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}},
+                              /*ForceRemoveDuplicates*/ true);
         } else
           changeToCall(II, DTU);
         Changed = true;
       }
     } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
       // Remove catchpads which cannot be reached.
       struct CatchPadDenseMapInfo {
         static CatchPadInst *getEmptyKey() {
void llvm::removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU) {
   }
 
   NewTI->takeName(TI);
   NewTI->setDebugLoc(TI->getDebugLoc());
   UnwindDest->removePredecessor(BB);
   TI->replaceAllUsesWith(NewTI);
   TI->eraseFromParent();
   if (DTU)
-    DTU->deleteEdgeRelaxed(BB, UnwindDest);
+    DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDest}},
+                      /*ForceRemoveDuplicates*/ true);
 }
 
 /// removeUnreachableBlocks - Remove blocks that are not reachable, even
 /// if they are in a dead cycle.  Return true if a change was made, false
 /// otherwise. If `LVI` is passed, this function preserves LazyValueInfo
 /// after modifying the CFG.
 bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI,
                                    DomTreeUpdater *DTU,

llvm/lib/Transforms/Utils/LoopUtils.cpp

void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT = nullptr,
   Builder.SetInsertPoint(Preheader->getTerminator());
   Builder.CreateBr(ExitBlock);
   // Remove the old branch.
   Preheader->getTerminator()->eraseFromParent();
 
   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
   if (DT) {
     // Update the dominator tree by informing it about the new edge from the
-    // preheader to the exit.
-    DTU.insertEdge(Preheader, ExitBlock);
-    // Inform the dominator tree about the removed edge.
-    DTU.deleteEdge(Preheader, L->getHeader());
+    // preheader to the exit and the removed edge.
+    DTU.applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock},
+                      {DominatorTree::Delete, Preheader, L->getHeader()}});
   }
 
   // Use a map to unique and a vector to guarantee deterministic ordering.
   llvm::SmallDenseSet<std::pair<DIVariable *, DIExpression *>, 4> DeadDebugSet;
   llvm::SmallVector<DbgVariableIntrinsic *, 4> DeadDebugInst;
 
   // Given LCSSA form is satisfied, we should not have users of instructions
   // within the dead loop outside of the loop. However, LCSSA doesn't take

llvm/unittests/Analysis/DomTreeUpdaterTest.cpp

TEST(DomTreeUpdater, EagerUpdateBasicOperations) {
   Function::iterator FI = F->begin();
   BasicBlock *BB0 = &*FI++;
   BasicBlock *BB1 = &*FI++;
   BasicBlock *BB2 = &*FI++;
   BasicBlock *BB3 = &*FI++;
   SwitchInst *SI = dyn_cast<SwitchInst>(BB0->getTerminator());
   ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst.";
 
-  DTU.insertEdgeRelaxed(BB0, BB0);
-  DTU.deleteEdgeRelaxed(BB0, BB0);
+  DTU.applyUpdates(
+      {{DominatorTree::Insert, BB0, BB0}, {DominatorTree::Delete, BB0, BB0}},
+      /*ForceRemoveDuplicates*/ true);
 
   // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
   // entries are discarded.
   std::vector<DominatorTree::UpdateType> Updates;
   Updates.reserve(4);
   Updates.push_back({DominatorTree::Delete, BB0, BB3});
   Updates.push_back({DominatorTree::Delete, BB0, BB3});
 
TEST(DomTreeUpdater, EagerUpdateBasicOperations) {
   // contained Instructions and change the Terminator to "unreachable" when
   // queued for deletion.
   ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
   EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
   DTU.applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
   ASSERT_FALSE(DTU.hasPendingUpdates());
 
   // Invalid Insert: no edge bb1 -> bb2 after change to bb0.
-  DTU.insertEdgeRelaxed(BB1, BB2);
   // Invalid Delete: edge exists bb0 -> bb1 after change to bb0.
-  DTU.deleteEdgeRelaxed(BB0, BB1);
+  DTU.applyUpdates(
+      {{DominatorTree::Insert, BB1, BB2}, {DominatorTree::Delete, BB0, BB1}},
+      /*ForceRemoveDuplicates*/ true);
 
   // DTU working with Eager UpdateStrategy does not need to flush.
   ASSERT_TRUE(DT.verify());
   ASSERT_TRUE(PDT.verify());
 
   // Test callback utils.
   ASSERT_EQ(BB3->getParent(), F);
   DTU.callbackDeleteBB(BB3,
TEST(DomTreeUpdater, EagerUpdateReplaceEntryBB) {
 
   // Add a block as the new function entry BB. We also link it to BB0.
   BasicBlock *NewEntry =
       BasicBlock::Create(F->getContext(), "new_entry", F, BB0);
   BranchInst::Create(BB0, NewEntry);
   EXPECT_EQ(F->begin()->getName(), NewEntry->getName());
   EXPECT_TRUE(&F->getEntryBlock() == NewEntry);
 
-  DTU.insertEdgeRelaxed(NewEntry, BB0);
+  DTU.applyUpdates({{DominatorTree::Insert, NewEntry, BB0}},
+                   /*ForceRemoveDuplicates*/ true);
 
   // Changing the Entry BB requires a full recalculation of DomTree.
   DTU.recalculate(*F);
   ASSERT_TRUE(DT.verify());
   ASSERT_TRUE(PDT.verify());
 
   // CFG Change: remove new_edge -> bb0 and redirect to new_edge -> bb1.
   EXPECT_EQ(NewEntry->getTerminator()->getNumSuccessors(), 1u);
TEST(DomTreeUpdater, LazyUpdateDTBasicOperations) {
 
   Function::iterator FI = F->begin();
   BasicBlock *BB0 = &*FI++;
   BasicBlock *BB1 = &*FI++;
   BasicBlock *BB2 = &*FI++;
   BasicBlock *BB3 = &*FI++;
 
   // Test discards of self-domination update.
-  DTU.deleteEdge(BB0, BB0);
+  DTU.applyUpdates({{DominatorTree::Delete, BB0, BB0}});
   ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
 
   // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
   // entries are discarded.
   std::vector<DominatorTree::UpdateType> Updates;
   Updates.reserve(4);
   Updates.push_back({DominatorTree::Delete, BB0, BB3});
   Updates.push_back({DominatorTree::Delete, BB0, BB3});
TEST(DomTreeUpdater, LazyUpdateDTInheritedPreds) {
   //   pred1..predN
   //   ||        |
   //   |+> curr <+    converted into:   pred1..predN curr
   //   |    |                            |        |
   //   |    v                            +> succ <+
   //   +-> succ
   //
   // While the final CFG form is functionally identical the updates to
-  // DTU are not. In the first case we must have DTU.insertEdge(Pred1, Succ)
-  // while in the latter case we must *NOT* have DTU.insertEdge(Pred1, Succ).
+  // 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}}).
 
   // CFG Change: bb0 now only has bb0 -> bb1 and bb0 -> bb3. We are preparing to
   // remove bb2.
   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 3u);
   BB0->getTerminator()->eraseFromParent();
   BranchInst::Create(BB1, BB3, ConstantInt::getTrue(F->getContext()), BB0);
   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
 
TEST(DomTreeUpdater, LazyUpdateDTInheritedPreds) {
   // method converts bb1's TI into "unreachable".
   ASSERT_FALSE(isa<UnreachableInst>(BB1->getTerminator()));
   EXPECT_FALSE(DTU.isBBPendingDeletion(BB1));
   DTU.callbackDeleteBB(BB1, Eraser);
   EXPECT_TRUE(DTU.isBBPendingDeletion(BB1));
   ASSERT_TRUE(isa<UnreachableInst>(BB1->getTerminator()));
   EXPECT_EQ(BB1->getParent(), F);
 
-  // Update the DTU. In this case we don't call DTU.insertEdge(BB0, BB3) because
-  // the edge previously existed at the start of this test when DT was first
-  // created.
+  // Update the DTU. In this case we don't submit {DominatorTree::Insert, BB0,
+  // BB3} because the edge previously existed at the start of this test when DT
+  // was first created.
   Updates.push_back({DominatorTree::Delete, BB0, BB1});
   Updates.push_back({DominatorTree::Delete, BB1, BB3});
 
   // Verify everything.
   DTU.applyUpdates(Updates);
   ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(2));
   DTU.flush();
   ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(0));
TEST(DomTreeUpdater, LazyUpdateBasicOperations) {
   ASSERT_TRUE(DTU.getPostDomTree().verify());
 
   Function::iterator FI = F->begin();
   BasicBlock *BB0 = &*FI++;
   BasicBlock *BB1 = &*FI++;
   BasicBlock *BB2 = &*FI++;
   BasicBlock *BB3 = &*FI++;
   // Test discards of self-domination update.
-  DTU.deleteEdge(BB0, BB0);
+  DTU.applyUpdates({{DominatorTree::Delete, BB0, BB0}});
 
   // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
   // entries are discarded.
   std::vector<DominatorTree::UpdateType> Updates;
   Updates.reserve(4);
   Updates.push_back({DominatorTree::Delete, BB0, BB3});
   Updates.push_back({DominatorTree::Delete, BB0, BB3});
 
BasicBlock *NewEntry =
       BasicBlock::Create(F->getContext(), "new_entry", F, BB0);
   BranchInst::Create(BB0, NewEntry);
   EXPECT_EQ(F->begin()->getName(), NewEntry->getName());
   EXPECT_TRUE(&F->getEntryBlock() == NewEntry);
 
   // Insert the new edge between new_entry -> bb0. Without this the
   // recalculate() call below will not actually recalculate the DT as there
   // are no changes pending and no blocks deleted.
-  DTU.insertEdge(NewEntry, BB0);
+  DTU.applyUpdates({{DominatorTree::Insert, NewEntry, BB0}});
 
   // Changing the Entry BB requires a full recalculation.
   DTU.recalculate(*F);
   ASSERT_TRUE(DTU.getDomTree().verify());
   ASSERT_TRUE(DTU.getPostDomTree().verify());
 
   // CFG Change: remove new_edge -> bb0 and redirect to new_edge -> bb1.
   EXPECT_EQ(NewEntry->getTerminator()->getNumSuccessors(), 1u);