[Dominators] Convert existing passes to use DomTreeUpdater - 1

[NutshellySima]

Summary

This patch is the second in a series of patches related to the RFC - A new dominator tree updater for LLVM.

It aims to convert some existing passes without dependencies to "local.h" and "BasicBlockUtils.h" to use the DomTreeUpdater.

[kuhar]

One thing that is not clear to me is whether it's work to replace plain updates (DT->insert/deleteEdge, DT->applyUpdates) with DTU when it's clear that both are going to be functionally the same. The overhead of constructing DTU is probably negligible, but it's more verbose and I'm not sure what benefit it brings.

It definitely makes sense to use DTU when you are updating both DT and PDT, and when you can use the lazy strategy, or use some other functions that take DTU. Do you think it's worth to replace it everywhere for some other reason?

lib/Transforms/Scalar/ADCE.cpp

618

Maybe use it directly from the constructor without creating a local variable -- like below?

I think either is fine - this should be easier to debug, the latter is more concise, but I think it's better to be somewhat consistent. What do you think?

[brzycki]

In D48919#1152530, @kuhar wrote:

One thing that is not clear to me is whether it's work to replace plain updates (DT->insert/deleteEdge, DT->applyUpdates) with DTU when it's clear that both are going to be functionally the same. The overhead of constructing DTU is probably negligible, but it's more verbose and I'm not sure what benefit it brings.

It definitely makes sense to use DTU when you are updating both DT and PDT, and when you can use the lazy strategy, or use some other functions that take DTU. Do you think it's worth to replace it everywhere for some other reason?

Hi @kuhar, I was hoping all instances of DT were replaced with DTU for the following reasons:

• call consistency. IT reduces problems when users do a git grep to see how others call DT and being unsure which interface to use, and why.
• every call site of DTU gets DT and PDT for free simply by adding the tree to the object. It makes both types of analysis easier to add in and potentially more used.
• an abstraction layer to the DT and PDT trees giving more flexibility to change the mechanics of both should new algorithms be developed or performance enhancements discovered.
• potential performance improvements. We can test eager vs lazy in different subsystems to tune the creation and use of DT/PDT.
• easier to add DT/PDT preservation to other passes. One of the most difficult parts of preserving DT in JumpThreading was all the external calls to Local, BasicBlock, or BasicBlockUtils. Had those routunes passed in a DTU instead of a DT the changes would be smaller and simpler. There are one or two calls in JumpThreading where I manually fixed things up before and after the external call simply because it was less-invasive and required far less testing than changing the external call. I also ran into problem with header inclusion problems when working with such core parts of the middle-end.

It's my hope, unless I'm missing something here, to eventually see very few parameterized method/function calls containing a DT/PDT pointer in llvm.

[NutshellySima]

In D48919#1153192, @brzycki wrote:

In D48919#1152530, @kuhar wrote:

One thing that is not clear to me is whether it's work to replace plain updates (DT->insert/deleteEdge, DT->applyUpdates) with DTU when it's clear that both are going to be functionally the same. The overhead of constructing DTU is probably negligible, but it's more verbose and I'm not sure what benefit it brings.

It definitely makes sense to use DTU when you are updating both DT and PDT, and when you can use the lazy strategy, or use some other functions that take DTU. Do you think it's worth to replace it everywhere for some other reason?

Hi @kuhar, I was hoping all instances of DT were replaced with DTU for the following reasons:

• call consistency. IT reduces problems when users do a git grep to see how others call DT and being unsure which interface to use, and why.
• every call site of DTU gets DT and PDT for free simply by adding the tree to the object. It makes both types of analysis easier to add in and potentially more used.
• an abstraction layer to the DT and PDT trees giving more flexibility to change the mechanics of both should new algorithms be developed or performance enhancements discovered.
• potential performance improvements. We can test eager vs lazy in different subsystems to tune the creation and use of DT/PDT.
• easier to add DT/PDT preservation to other passes. One of the most difficult parts of preserving DT in JumpThreading was all the external calls to Local, BasicBlock, or BasicBlockUtils. Had those routunes passed in a DTU instead of a DT the changes would be smaller and simpler. There are one or two calls in JumpThreading where I manually fixed things up before and after the external call simply because it was less-invasive and required far less testing than changing the external call. I also ran into problem with header inclusion problems when working with such core parts of the middle-end.

It's my hope, unless I'm missing something here, to eventually see very few parameterized method/function calls containing a DT/PDT pointer in llvm.

Hi @brzycki, thanks for pointing them out. It is good to see passes getting easier DT/PDT preservation by replacing (DT->insert/deleteEdge, DT->applyUpdates) to corresponding ones in DTU and adding PDT to the object. I'll add them back in https://reviews.llvm.org/D48967.

lib/Transforms/Scalar/ADCE.cpp

 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/IteratedDominanceFrontier.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/DebugLoc.h"
+#include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/Dominators.h"
-#include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Function.h"
+#include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/Use.h"
 #include "llvm/IR/Value.h"
for (auto *Succ : RemovedSuccessors) {
       if (Succ != PreferredSucc->BB) {
         LLVM_DEBUG(dbgs() << "ADCE: (Post)DomTree edge enqueued for deletion"
                           << BB->getName() << " -> " << Succ->getName()
                           << "\n");
         DeletedEdges.push_back({DominatorTree::Delete, BB, Succ});
       }
     }
 
-    DT.applyUpdates(DeletedEdges);
-    PDT.applyUpdates(DeletedEdges);
+    DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
+    DTU.applyUpdates(DeletedEdges);
 
     NumBranchesRemoved += 1;
   }
 }
 
 // reverse top-sort order
 void AggressiveDeadCodeElimination::computeReversePostOrder() {
   // This provides a post-order numbering of the reverse control flow graph

lib/Transforms/Scalar/LoopInterchange.cpp

 #include "llvm/Analysis/DependenceAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DiagnosticInfo.h"
+#include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
bool LoopInterchangeTransform::adjustLoopBranches() {
 
   updateSuccessor(InnerLoopLatchBI, InnerLoopLatchSuccessor,
                   OuterLoopLatchSuccessor, DTUpdates);
   updateSuccessor(OuterLoopLatchBI, OuterLoopLatchSuccessor, InnerLoopLatch,
                   DTUpdates);
 
   updateIncomingBlock(OuterLoopLatchSuccessor, OuterLoopLatch, InnerLoopLatch);
 
-  DT->applyUpdates(DTUpdates);
+  DomTreeUpdater(*DT, DomTreeUpdater::UpdateStrategy::Eager)
+      .applyUpdates(DTUpdates);
   restructureLoops(OuterLoop, InnerLoop, InnerLoopPreHeader,
                    OuterLoopPreHeader);
 
   // Now update the reduction PHIs in the inner and outer loop headers.
   SmallVector<PHINode *, 4> InnerLoopPHIs, OuterLoopPHIs;
   for (PHINode &PHI : drop_begin(InnerLoopHeader->phis(), 1))
     InnerLoopPHIs.push_back(cast<PHINode>(&PHI));
   for (PHINode &PHI : drop_begin(OuterLoopHeader->phis(), 1))

lib/Transforms/Scalar/LoopUnswitch.cpp

 //
 // This pass expects LICM to be run before it to hoist invariant conditions out
 // of the loop, to make the unswitching opportunity obvious.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/DivergenceAnalysis.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
-#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
 #include <algorithm>
 #include <cassert>
 #include <map>
 #include <set>
 #include <tuple>
 #include <utility>
if (DT) {
     if (FalseDest != OldBranchSucc)
       Updates.push_back({DominatorTree::Insert, OldBranchParent, FalseDest});
     // If both of the new successors are different from the old one, inform the
     // DT that the edge was deleted.
     if (OldBranchSucc != TrueDest && OldBranchSucc != FalseDest) {
       Updates.push_back({DominatorTree::Delete, OldBranchParent, OldBranchSucc});
     }
 
-    DT->applyUpdates(Updates);
+    DomTreeUpdater(*DT, DomTreeUpdater::UpdateStrategy::Eager)
+        .applyUpdates(Updates);
   }
 
   // If either edge is critical, split it. This helps preserve LoopSimplify
   // form for enclosing loops.
   auto Options = CriticalEdgeSplittingOptions(DT, LI).setPreserveLCSSA();
   SplitCriticalEdge(BI, 0, Options);
   SplitCriticalEdge(BI, 1, Options);
 }

lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/Utils/Local.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
+#include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Use.h"
 #include "llvm/IR/Value.h"
static bool unswitchTrivialBranch(Loop &L, BranchInst &BI, DominatorTree &DT,
 
   // Rewrite the relevant PHI nodes.
   if (UnswitchedBB == LoopExitBB)
     rewritePHINodesForUnswitchedExitBlock(*UnswitchedBB, *ParentBB, *OldPH);
   else
     rewritePHINodesForExitAndUnswitchedBlocks(*LoopExitBB, *UnswitchedBB,
                                               *ParentBB, *OldPH, FullUnswitch);
 
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
   // Now we need to update the dominator tree.
-  DT.insertEdge(OldPH, UnswitchedBB);
+  DTU.insertEdge(OldPH, UnswitchedBB);
   if (FullUnswitch)
-    DT.deleteEdge(ParentBB, UnswitchedBB);
+    DTU.deleteEdge(ParentBB, UnswitchedBB);
 
   // The constant we can replace all of our invariants with inside the loop
   // body. If any of the invariants have a value other than this the loop won't
   // be entered.
   ConstantInt *Replacement = ExitDirection
                                  ? ConstantInt::getFalse(BI.getContext())
                                  : ConstantInt::getTrue(BI.getContext());
 
for (auto *UnswitchedExitBB : UnswitchedExitBBs) {
     DTUpdates.push_back({DT.Delete, ParentBB, UnswitchedExitBB});
     DTUpdates.push_back({DT.Insert, OldPH, UnswitchedExitBB});
   }
   for (auto SplitUnswitchedPair : SplitExitBBMap) {
     auto *UnswitchedBB = SplitUnswitchedPair.second;
     DTUpdates.push_back({DT.Delete, ParentBB, UnswitchedBB});
     DTUpdates.push_back({DT.Insert, OldPH, UnswitchedBB});
   }
-  DT.applyUpdates(DTUpdates);
+  DomTreeUpdater(DT, DomTreeUpdater::UpdateStrategy::Eager)
+      .applyUpdates(DTUpdates);
 
   assert(DT.verify(DominatorTree::VerificationLevel::Fast));
   ++NumTrivial;
   ++NumSwitches;
   return true;
 }
 
 /// This routine scans the loop to find a branch or switch which occurs before
if (FullUnswitch) {
     // When doing a partial unswitch, we have to do a bit more work to build up
     // the branch in the split block.
     buildPartialUnswitchConditionalBranch(*SplitBB, Invariants, Direction,
                                           *ClonedPH, *LoopPH);
     DTUpdates.push_back({DominatorTree::Insert, SplitBB, ClonedPH});
   }
 
   // Apply the updates accumulated above to get an up-to-date dominator tree.
-  DT.applyUpdates(DTUpdates);
+  DomTreeUpdater(DT, DomTreeUpdater::UpdateStrategy::Eager)
+      .applyUpdates(DTUpdates);
 
   // Now that we have an accurate dominator tree, first delete the dead cloned
   // blocks so that we can accurately build any cloned loops. It is important to
   // not delete the blocks from the original loop yet because we still want to
   // reference the original loop to understand the cloned loop's structure.
   deleteDeadClonedBlocks(L, ExitBlocks, VMaps, DT);
 
   // Build the cloned loop structure itself. This may be substantially

lib/Transforms/Utils/BreakCriticalEdges.cpp

 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/CFG.h"
+#include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Type.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Transforms/Utils.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
if (DT) {
     // DestBB stays reachable in the DT the whole time and its subtree doesn't
     // get disconnected.
     SmallVector<DominatorTree::UpdateType, 3> Updates;
     Updates.push_back({DominatorTree::Insert, TIBB, NewBB});
     Updates.push_back({DominatorTree::Insert, NewBB, DestBB});
     if (llvm::find(successors(TIBB), DestBB) == succ_end(TIBB))
       Updates.push_back({DominatorTree::Delete, TIBB, DestBB});
 
-    DT->applyUpdates(Updates);
+    DomTreeUpdater(*DT, DomTreeUpdater::UpdateStrategy::Eager)
+        .applyUpdates(Updates);
   }
 
   // Update LoopInfo if it is around.
   if (LI) {
     if (Loop *TIL = LI->getLoopFor(TIBB)) {
       // If one or the other blocks were not in a loop, the new block is not
       // either, and thus LI doesn't need to be updated.
       if (Loop *DestLoop = LI->getLoopFor(DestBB)) {

lib/Transforms/Utils/LoopRotationUtils.cpp

 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
-#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/DebugInfoMetadata.h"
+#include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-rotate"
 
 STATISTIC(NumRotated, "Number of loops rotated");
bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) {
   // Inform DT about changes to the CFG.
   if (DT) {
     // The OrigPreheader branches to the NewHeader and Exit now. Then, inform
     // the DT about the removed edge to the OrigHeader (that got removed).
     SmallVector<DominatorTree::UpdateType, 3> Updates;
     Updates.push_back({DominatorTree::Insert, OrigPreheader, Exit});
     Updates.push_back({DominatorTree::Insert, OrigPreheader, NewHeader});
     Updates.push_back({DominatorTree::Delete, OrigPreheader, OrigHeader});
-    DT->applyUpdates(Updates);
+    DomTreeUpdater(*DT, DomTreeUpdater::UpdateStrategy::Eager)
+        .applyUpdates(Updates);
   }
 
   // At this point, we've finished our major CFG changes.  As part of cloning
   // the loop into the preheader we've simplified instructions and the
   // duplicated conditional branch may now be branching on a constant.  If it is
   // branching on a constant and if that constant means that we enter the loop,
   // then we fold away the cond branch to an uncond branch.  This simplifies the
   // loop in cases important for nested loops, and it also means we don't have
if (!isa<ConstantInt>(PHBI->getCondition()) ||
     // We can fold the conditional branch in the preheader, this makes things
     // simpler. The first step is to remove the extra edge to the Exit block.
     Exit->removePredecessor(OrigPreheader, true /*preserve LCSSA*/);
     BranchInst *NewBI = BranchInst::Create(NewHeader, PHBI);
     NewBI->setDebugLoc(PHBI->getDebugLoc());
     PHBI->eraseFromParent();
 
     // With our CFG finalized, update DomTree if it is available.
-    if (DT) DT->deleteEdge(OrigPreheader, Exit);
+    if (DT)
+      DomTreeUpdater(*DT, DomTreeUpdater::UpdateStrategy::Eager)
+          .deleteEdge(OrigPreheader, Exit);
   }
 
   assert(L->getLoopPreheader() && "Invalid loop preheader after loop rotation");
   assert(L->getLoopLatch() && "Invalid loop latch after loop rotation");
 
   // Now that the CFG and DomTree are in a consistent state again, try to merge
   // the OrigHeader block into OrigLatch.  This will succeed if they are
   // connected by an unconditional branch.  This is just a cleanup so the

lib/Transforms/Utils/LoopUtils.cpp

 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/MustExecute.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/KnownBits.h"
void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT = nullptr,
 
   // Disconnect the loop body by branching directly to its exit.
   Builder.SetInsertPoint(Preheader->getTerminator());
   Builder.CreateBr(ExitBlock);
   // Remove the old branch.
   Preheader->getTerminator()->eraseFromParent();
 
   if (DT) {
+    DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Eager);
     // Update the dominator tree by informing it about the new edge from the
     // preheader to the exit.
-    DT->insertEdge(Preheader, ExitBlock);
+    DTU.insertEdge(Preheader, ExitBlock);
     // Inform the dominator tree about the removed edge.
-    DT->deleteEdge(Preheader, L->getHeader());
+    DTU.deleteEdge(Preheader, L->getHeader());
   }
 
   // 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
   // unreachable uses into account. We handle them here.
   // We could do it after drop all references (in this case all users in the
   // loop will be already eliminated and we have less work to do but according
   // to API doc of User::dropAllReferences only valid operation after dropping