[CodeMoverUtils] Make specific analysis dependent checks optional

[RithikSharma]

Summary

This patch makes code motion checks optional which are dependent on specific analysis example, dominator tree, post dominator tree and dependence info. The aim is to make the adoption of CodeMoverUtils easier for clients that don't use analysis which were strictly required by CodeMoverUtils. This will also help in diversifying code motion checks using other analysis example MSSA.

[Whitney]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

513

where is no need to change LoopFuse, just pass the address when calling the APIs.

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

100

you can a segfault here when DT is nullptr, making analyses optional means you have to add handle when they are nullptr, and add alternative ways to do what the function is intended to do.

320

so as long as DT is nullptr, instruction is safe to move before InsertPoint? can return false here instead of true.

[RithikSharma]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

100

Acknowledged but right now ControlConditions or its member functions are not called when we don't have DT or PDT. ControlConditions don't know that DT and PDT are optional, isn't it be handled by ControlCondition's clients?

320

Acknowledged and updated

[Whitney]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

100

in that case change the parameters back to references for ControlConditions

[RithikSharma]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

100

Thanks, updated.

[Whitney]

llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h

29–30

what's the reason why some arguments have nullptr as default value, and some doesn't?

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

226–227

Is there an alternative way to check control flow equivalent without DT and PDT? If not, change it back to references.

231–232

here you are dereferencing a pointer that can be a nullptr.

320

Actually if DI or PDT or DI, either one is nullptr, than this function never return true, so why not just check that in the beginning.

366

return false

374

return false

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp

33–34

I prefer not to change any of the parameters from references to pointers, just change the call site.

[RithikSharma]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

320

I understood your point. Say we don't have DT, PDT or DI then instead of returning false should we return true/false based on our best knowledge? If a client don't have DT, PDT and DI then it may be expecting at least some checks (which may or may not be of any real use)? Also, when we will add more analysis (example MSSA) then would it make more sense to return true/false based on whatever checks/analysis we have with us and not conservatively returning false?

[Whitney]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

320

If DT, PDT, or DI is nullptr, we have to conservatively return false, we can only say is safe to move before if we are sure it is safe. If we have more analysis, for example MSSA, and it can tell if the instruction is for sure safe to move, then we can return true in that case. Does it make sense?

[RithikSharma]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

320

Yes it does, Updated.

[asbirlea]

Seems like this needs to be rebased on top of D82290?

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

320

MSSA will always have DT available.
I'm not clear why this is not keeping DT a reference.

366

Only check PDT. DT has been checked above.

[Whitney]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

319

if we check here

if (!DT || !PDT || !DI)
  return false;

then we can save some compile time. As currently, there are no way that can return true, if any of them is nullptr.

320

Good point, we can keep DT as reference, all loop passes have access to DT.

[RithikSharma]

Many thanks, I have updated the diff.

llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h

 class DominatorTree;
 class Instruction;
 class PostDominatorTree;
 
 /// Return true if \p I0 and \p I1 are control flow equivalent.
 /// Two instructions are control flow equivalent if their basic blocks are
 /// control flow equivalent.
 bool isControlFlowEquivalent(const Instruction &I0, const Instruction &I1,
-                             const DominatorTree &DT,
-                             const PostDominatorTree &PDT);
+                             const DominatorTree *DT,
+                             const PostDominatorTree *PDT);
 
 /// Return true if \p BB0 and \p BB1 are control flow equivalent.
 /// Two basic blocks are control flow equivalent if when one executes, the other
 /// is guaranteed to execute.
 bool isControlFlowEquivalent(const BasicBlock &BB0, const BasicBlock &BB1,
-                             const DominatorTree &DT,
-                             const PostDominatorTree &PDT);
+                             const DominatorTree *DT,
+                             const PostDominatorTree *PDT);
 
 /// Return true if \p I can be safely moved before \p InsertPoint.
 bool isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
-                        DominatorTree &DT, const PostDominatorTree &PDT,
-                        DependenceInfo &DI);
+                        DominatorTree *DT = nullptr,
+                        const PostDominatorTree *PDT = nullptr,
+                        DependenceInfo *DI = nullptr);
 
 /// Return true if all instructions (except the terminator) in \p BB can be
 /// safely moved before \p InsertPoint.
 bool isSafeToMoveBefore(BasicBlock &BB, Instruction &InsertPoint,
-                        DominatorTree &DT, const PostDominatorTree &PDT,
-                        DependenceInfo &DI);
+                        DominatorTree *DT = nullptr,
+                        const PostDominatorTree *PDT = nullptr,
+                        DependenceInfo *DI = nullptr);
 
 /// Move instructions, in an order-preserving manner, from \p FromBB to the
 /// beginning of \p ToBB when proven safe.
 void moveInstructionsToTheBeginning(BasicBlock &FromBB, BasicBlock &ToBB,
-                                    DominatorTree &DT,
-                                    const PostDominatorTree &PDT,
-                                    DependenceInfo &DI);
+                                    DominatorTree *DT,
+                                    const PostDominatorTree *PDT,
+                                    DependenceInfo *DI);
 
 /// Move instructions, in an order-preserving manner, from \p FromBB to the end
 /// of \p ToBB when proven safe.
 void moveInstructionsToTheEnd(BasicBlock &FromBB, BasicBlock &ToBB,
-                              DominatorTree &DT, const PostDominatorTree &PDT,
-                              DependenceInfo &DI);
+                              DominatorTree *DT, const PostDominatorTree *PDT,
+                              DependenceInfo *DI);
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_CODEMOVERUTILS_H

llvm/lib/Transforms/Scalar/LoopFuse.cpp

 private:
   // Sets of control flow equivalent fusion candidates for a given nest level.
   FusionCandidateCollection FusionCandidates;
 
   LoopDepthTree LDT;
   DomTreeUpdater DTU;
 
   LoopInfo &LI;
-  DominatorTree &DT;
-  DependenceInfo &DI;
+  DominatorTree *DT;
+  DependenceInfo *DI;
   ScalarEvolution &SE;
-  PostDominatorTree &PDT;
+  PostDominatorTree *PDT;
   OptimizationRemarkEmitter &ORE;
 
 public:
-  LoopFuser(LoopInfo &LI, DominatorTree &DT, DependenceInfo &DI,
-            ScalarEvolution &SE, PostDominatorTree &PDT,
+  LoopFuser(LoopInfo &LI, DominatorTree *DT, DependenceInfo *DI,
+            ScalarEvolution &SE, PostDominatorTree *PDT,
             OptimizationRemarkEmitter &ORE, const DataLayout &DL)
       : LDT(LI), DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy), LI(LI),
         DT(DT), DI(DI), SE(SE), PDT(PDT), ORE(ORE) {}
 
   /// This is the main entry point for loop fusion. It will traverse the
   /// specified function and collect candidate loops to fuse, starting at the
   /// outermost nesting level and working inwards.
   bool fuseLoops(Function &F) {
#endif
       LDT.descend();
       FusionCandidates.clear();
     }
 
     if (Changed)
       LLVM_DEBUG(dbgs() << "Function after Loop Fusion: \n"; F.dump(););
 
 #ifndef NDEBUG
-    assert(DT.verify());
-    assert(PDT.verify());
-    LI.verify(DT);
+    assert(DT->verify());
+    assert(PDT->verify());
+    LI.verify(*DT);
     SE.verify();
 #endif
 
     LLVM_DEBUG(dbgs() << "Loop Fusion complete\n");
     return Changed;
   }
 
 private:
return ::isControlFlowEquivalent(*FC0.getEntryBlock(), *FC1.getEntryBlock(),
                                      DT, PDT);
   }
 
   /// Iterate over all loops in the given loop set and identify the loops that
   /// are eligible for fusion. Place all eligible fusion candidates into Control
   /// Flow Equivalent sets, sorted by dominance.
   void collectFusionCandidates(const LoopVector &LV) {
     for (Loop *L : LV) {
-      FusionCandidate CurrCand(L, &DT, &PDT, ORE);
+      FusionCandidate CurrCand(L, DT, PDT, ORE);
       if (!CurrCand.isEligibleForFusion(SE))
         continue;
 
       // Go through each list in FusionCandidates and determine if L is control
       // flow equivalent with the first loop in that list. If it is, append LV.
       // If not, go to the next list.
       // If no suitable list is found, start another list and add it to
       // FusionCandidates.
for (auto &CandidateSet : FusionCandidates) {
                             << *FC1 << "\n");
 
           // Report fusion to the Optimization Remarks.
           // Note this needs to be done *before* performFusion because
           // performFusion will change the original loops, making it not
           // possible to identify them after fusion is complete.
           reportLoopFusion<OptimizationRemark>(*FC0, *FC1, FuseCounter);
 
-          FusionCandidate FusedCand(performFusion(*FC0, *FC1), &DT, &PDT, ORE);
+          FusionCandidate FusedCand(performFusion(*FC0, *FC1), DT, PDT, ORE);
           FusedCand.verify();
           assert(FusedCand.isEligibleForFusion(SE) &&
                  "Fused candidate should be eligible for fusion!");
 
           // Notify the loop-depth-tree that these loops are not valid objects
           LDT.removeLoop(FC1->L);
 
           CandidateSet.erase(FC0);
#endif
     //       L0) and the other is not. We could check if it is monotone and test
     //       the beginning and end value instead.
 
     BasicBlock *L0Header = L0.getHeader();
     auto HasNonLinearDominanceRelation = [&](const SCEV *S) {
       const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S);
       if (!AddRec)
         return false;
-      return !DT.dominates(L0Header, AddRec->getLoop()->getHeader()) &&
-             !DT.dominates(AddRec->getLoop()->getHeader(), L0Header);
+      return !DT->dominates(L0Header, AddRec->getLoop()->getHeader()) &&
+             !DT->dominates(AddRec->getLoop()->getHeader(), L0Header);
     };
     if (SCEVExprContains(SCEVPtr1, HasNonLinearDominanceRelation))
       return false;
 
     ICmpInst::Predicate Pred =
         EqualIsInvalid ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_SGE;
     bool IsAlwaysGE = SE.isKnownPredicate(Pred, SCEVPtr0, SCEVPtr1);
 #ifndef NDEBUG
if (VerboseFusionDebugging) {
       LLVM_DEBUG(dbgs() << "Check dep: " << I0 << " vs " << I1 << " : "
                         << DepChoice << "\n");
     }
 #endif
     switch (DepChoice) {
     case FUSION_DEPENDENCE_ANALYSIS_SCEV:
       return accessDiffIsPositive(*FC0.L, *FC1.L, I0, I1, AnyDep);
     case FUSION_DEPENDENCE_ANALYSIS_DA: {
-      auto DepResult = DI.depends(&I0, &I1, true);
+      auto DepResult = DI->depends(&I0, &I1, true);
       if (!DepResult)
         return true;
 #ifndef NDEBUG
       if (VerboseFusionDebugging) {
         LLVM_DEBUG(dbgs() << "DA res: "; DepResult->dump(dbgs());
                    dbgs() << " [#l: " << DepResult->getLevels() << "][Ordered: "
                           << (DepResult->isOrdered() ? "true" : "false")
                           << "]\n");
#endif
   }
 
   /// Perform a dependence check and return if @p FC0 and @p FC1 can be fused.
   bool dependencesAllowFusion(const FusionCandidate &FC0,
                               const FusionCandidate &FC1) {
     LLVM_DEBUG(dbgs() << "Check if " << FC0 << " can be fused with " << FC1
                       << "\n");
     assert(FC0.L->getLoopDepth() == FC1.L->getLoopDepth());
-    assert(DT.dominates(FC0.getEntryBlock(), FC1.getEntryBlock()));
+    assert(DT->dominates(FC0.getEntryBlock(), FC1.getEntryBlock()));
 
     for (Instruction *WriteL0 : FC0.MemWrites) {
       for (Instruction *WriteL1 : FC1.MemWrites)
         if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *WriteL1,
                                     /* AnyDep */ false,
                                     FusionDependenceAnalysis)) {
           InvalidDependencies++;
           return false;
while (!FC1.L->empty()) {
       FC0.L->addChildLoop(ChildLoop);
     }
 
     // Delete the now empty loop L1.
     LI.erase(FC1.L);
 
 #ifndef NDEBUG
     assert(!verifyFunction(*FC0.Header->getParent(), &errs()));
-    assert(DT.verify(DominatorTree::VerificationLevel::Fast));
-    assert(PDT.verify());
-    LI.verify(DT);
+    assert(DT->verify(DominatorTree::VerificationLevel::Fast));
+    assert(PDT->verify());
+    LI.verify(*DT);
     SE.verify();
 #endif
 
     LLVM_DEBUG(dbgs() << "Fusion done:\n");
 
     return FC0.L;
   }
 
while (!FC1.L->empty()) {
       FC0.L->addChildLoop(ChildLoop);
     }
 
     // Delete the now empty loop L1.
     LI.erase(FC1.L);
 
 #ifndef NDEBUG
     assert(!verifyFunction(*FC0.Header->getParent(), &errs()));
-    assert(DT.verify(DominatorTree::VerificationLevel::Fast));
-    assert(PDT.verify());
-    LI.verify(DT);
+    assert(DT->verify(DominatorTree::VerificationLevel::Fast));
+    assert(PDT->verify());
+    LI.verify(*DT);
     SE.verify();
 #endif
 
     LLVM_DEBUG(dbgs() << "Fusion done:\n");
 
     return FC0.L;
   }
 };
void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addPreserved<PostDominatorTreeWrapperPass>();
   }
 
   bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;
     auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
-    auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-    auto &DI = getAnalysis<DependenceAnalysisWrapperPass>().getDI();
+    auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+    auto *DI = &getAnalysis<DependenceAnalysisWrapperPass>().getDI();
     auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
-    auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
+    auto *PDT = &getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
     auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
 
     const DataLayout &DL = F.getParent()->getDataLayout();
     LoopFuser LF(LI, DT, DI, SE, PDT, ORE, DL);
     return LF.fuseLoops(F);
   }
 };
 } // namespace
 
 PreservedAnalyses LoopFusePass::run(Function &F, FunctionAnalysisManager &AM) {
   auto &LI = AM.getResult<LoopAnalysis>(F);
-  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
-  auto &DI = AM.getResult<DependenceAnalysis>(F);
+  auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
+  auto *DI = &AM.getResult<DependenceAnalysis>(F);
   auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
-  auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
+  auto *PDT = &AM.getResult<PostDominatorTreeAnalysis>(F);
   auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
 
   const DataLayout &DL = F.getParent()->getDataLayout();
   LoopFuser LF(LI, DT, DI, SE, PDT, ORE, DL);
   bool Changed = LF.fuseLoops(F);
   if (!Changed)
     return PreservedAnalyses::all();
 

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

 
 public:
   /// Return a ControlConditions which stores all conditions required to execute
   /// \p BB from \p Dominator. If \p MaxLookup is non-zero, it limits the
   /// number of conditions to collect. Return None if not all conditions are
   /// collected successfully, or we hit the limit.
   static const Optional<ControlConditions>
   collectControlConditions(const BasicBlock &BB, const BasicBlock &Dominator,
-                           const DominatorTree &DT,
-                           const PostDominatorTree &PDT,
+                           const DominatorTree *DT,
+                           const PostDominatorTree *PDT,
                            unsigned MaxLookup = 6);
 
   /// Return true if there exists no control conditions required to execute ToBB
   /// from FromBB.
   bool isUnconditional() const { return Conditions.empty(); }
 
   /// Return a constant reference of Conditions.
   const ConditionVectorTy &getControlConditions() const { return Conditions; }
private:
   ControlConditions() = default;
 
   static bool isEquivalent(const Value &V1, const Value &V2);
   static bool isInverse(const Value &V1, const Value &V2);
 };
 } // namespace
 
 const Optional<ControlConditions> ControlConditions::collectControlConditions(
-    const BasicBlock &BB, const BasicBlock &Dominator, const DominatorTree &DT,
-    const PostDominatorTree &PDT, unsigned MaxLookup) {
-  assert(DT.dominates(&Dominator, &BB) && "Expecting Dominator to dominate BB");
+    const BasicBlock &BB, const BasicBlock &Dominator, const DominatorTree *DT,
+    const PostDominatorTree *PDT, unsigned MaxLookup) {
+  assert(DT->dominates(&Dominator, &BB) &&
+         "Expecting Dominator to dominate BB");
 
   ControlConditions Conditions;
   unsigned NumConditions = 0;
 
   // BB is executed unconditional from itself.
   if (&Dominator == &BB)
     return Conditions;
 
   const BasicBlock *CurBlock = &BB;
   // Walk up the dominator tree from the associated DT node for BB to the
   // associated DT node for Dominator.
   do {
-    assert(DT.getNode(CurBlock) && "Expecting a valid DT node for CurBlock");
-    BasicBlock *IDom = DT.getNode(CurBlock)->getIDom()->getBlock();
-    assert(DT.dominates(&Dominator, IDom) &&
+    assert(DT->getNode(CurBlock) && "Expecting a valid DT node for CurBlock");
+    BasicBlock *IDom = DT->getNode(CurBlock)->getIDom()->getBlock();
+    assert(DT->dominates(&Dominator, IDom) &&
            "Expecting Dominator to dominate IDom");
 
     // Limitation: can only handle branch instruction currently.
     const BranchInst *BI = dyn_cast<BranchInst>(IDom->getTerminator());
     if (!BI)
       return None;
 
     bool Inserted = false;
-    if (PDT.dominates(CurBlock, IDom)) {
+    if (PDT->dominates(CurBlock, IDom)) {
       LLVM_DEBUG(dbgs() << CurBlock->getName()
                         << " is executed unconditionally from "
                         << IDom->getName() << "\n");
-    } else if (PDT.dominates(CurBlock, BI->getSuccessor(0))) {
+    } else if (PDT->dominates(CurBlock, BI->getSuccessor(0))) {
       LLVM_DEBUG(dbgs() << CurBlock->getName() << " is executed when \""
                         << *BI->getCondition() << "\" is true from "
                         << IDom->getName() << "\n");
       Inserted = Conditions.addControlCondition(
           ControlCondition(BI->getCondition(), true));
-    } else if (PDT.dominates(CurBlock, BI->getSuccessor(1))) {
+    } else if (PDT->dominates(CurBlock, BI->getSuccessor(1))) {
       LLVM_DEBUG(dbgs() << CurBlock->getName() << " is executed when \""
                         << *BI->getCondition() << "\" is false from "
                         << IDom->getName() << "\n");
       Inserted = Conditions.addControlCondition(
           ControlCondition(BI->getCondition(), false));
     } else
       return None;
 
if (const CmpInst *Cmp2 = dyn_cast<CmpInst>(&V2)) {
           Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
           Cmp1->getOperand(1) == Cmp2->getOperand(0))
         return true;
     }
   return false;
 }
 
 bool llvm::isControlFlowEquivalent(const Instruction &I0, const Instruction &I1,
-                                   const DominatorTree &DT,
-                                   const PostDominatorTree &PDT) {
+                                   const DominatorTree *DT,
+                                   const PostDominatorTree *PDT) {
   return isControlFlowEquivalent(*I0.getParent(), *I1.getParent(), DT, PDT);
 }
 
 bool llvm::isControlFlowEquivalent(const BasicBlock &BB0, const BasicBlock &BB1,
-                                   const DominatorTree &DT,
-                                   const PostDominatorTree &PDT) {
+                                   const DominatorTree *DT,
+                                   const PostDominatorTree *PDT) {
   if (&BB0 == &BB1)
     return true;
 
-  if ((DT.dominates(&BB0, &BB1) && PDT.dominates(&BB1, &BB0)) ||
-      (PDT.dominates(&BB0, &BB1) && DT.dominates(&BB1, &BB0)))
+  if ((DT->dominates(&BB0, &BB1) && PDT->dominates(&BB1, &BB0)) ||
+      (PDT->dominates(&BB0, &BB1) && DT->dominates(&BB1, &BB0)))
     return true;
 
   // If the set of conditions required to execute BB0 and BB1 from their common
   // dominator are the same, then BB0 and BB1 are control flow equivalent.
-  const BasicBlock *CommonDominator = DT.findNearestCommonDominator(&BB0, &BB1);
+  const BasicBlock *CommonDominator =
+      DT->findNearestCommonDominator(&BB0, &BB1);
   LLVM_DEBUG(dbgs() << "The nearest common dominator of " << BB0.getName()
                     << " and " << BB1.getName() << " is "
                     << CommonDominator->getName() << "\n");
 
   const Optional<ControlConditions> BB0Conditions =
       ControlConditions::collectControlConditions(BB0, *CommonDominator, DT,
                                                   PDT);
   if (BB0Conditions == None)
while (!WorkList.empty()) {
     if (!InBetweenInsts.insert(CurInst).second)
       continue;
 
     getNextInsts(*CurInst, WorkList);
   }
 }
 
 bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
-                              DominatorTree &DT, const PostDominatorTree &PDT,
-                              DependenceInfo &DI) {
+                              DominatorTree *DT, const PostDominatorTree *PDT,
+                              DependenceInfo *DI) {
   // Cannot move itself before itself.
   if (&I == &InsertPoint)
     return false;
 
   // Not moved.
   if (I.getNextNode() == &InsertPoint)
     return true;
 
   if (isa<PHINode>(I) || isa<PHINode>(InsertPoint))
     return reportInvalidCandidate(I, NotMovedPHINode);
 
   if (I.isTerminator())
     return reportInvalidCandidate(I, NotMovedTerminator);
 
-  // TODO remove this limitation.
-  if (!isControlFlowEquivalent(I, InsertPoint, DT, PDT))
-    return reportInvalidCandidate(I, NotControlFlowEquivalent);
+  // Skip tests that need DT
+  if (!DT)
+    return true;
 
-  if (!DT.dominates(&InsertPoint, &I))
+  if (!DT->dominates(&InsertPoint, &I))
     for (const Use &U : I.uses())
       if (auto *UserInst = dyn_cast<Instruction>(U.getUser()))
-        if (UserInst != &InsertPoint && !DT.dominates(&InsertPoint, U))
+        if (UserInst != &InsertPoint && !DT->dominates(&InsertPoint, U))
           return false;
-  if (!DT.dominates(&I, &InsertPoint))
+  if (!DT->dominates(&I, &InsertPoint))
     for (const Value *Op : I.operands())
       if (auto *OpInst = dyn_cast<Instruction>(Op))
-        if (&InsertPoint == OpInst || !DT.dominates(OpInst, &InsertPoint))
+        if (&InsertPoint == OpInst || !DT->dominates(OpInst, &InsertPoint))
           return false;
 
-  OrderedInstructions OI(&DT);
-  DT.updateDFSNumbers();
+  OrderedInstructions OI(DT);
+  DT->updateDFSNumbers();
   const bool MoveForward = OI.domTreeLevelBefore(&I, &InsertPoint);
   Instruction &StartInst = (MoveForward ? I : InsertPoint);
   Instruction &EndInst = (MoveForward ? InsertPoint : I);
   SmallPtrSet<Instruction *, 10> InstsToCheck;
   collectInstructionsInBetween(StartInst, EndInst, InstsToCheck);
   if (!MoveForward)
     InstsToCheck.insert(&InsertPoint);
 
if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(),
                       if (!CB->hasFnAttr(Attribute::NoSync))
                         return true;
 
                       return false;
                     })) {
       return reportInvalidCandidate(I, MayThrowException);
     }
 
+  // Skip checks that require DT and PDT
+  if (!(DT && PDT))
+    return true;
+
+  // TODO remove this limitation.
+  if (!isControlFlowEquivalent(I, InsertPoint, DT, PDT))
+    return reportInvalidCandidate(I, NotControlFlowEquivalent);
+
+  // Skip DependenceInfo checks as we don't have DI
+  if (!DI)
+    return true;
+
   // Check if I has any output/flow/anti dependences with instructions from \p
   // StartInst to \p EndInst.
   if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(),
                   [&DI, &I](Instruction *CurInst) {
-                    auto DepResult = DI.depends(&I, CurInst, true);
+                    auto DepResult = DI->depends(&I, CurInst, true);
                     if (DepResult &&
                         (DepResult->isOutput() || DepResult->isFlow() ||
                          DepResult->isAnti()))
                       return true;
                     return false;
                   }))
     return reportInvalidCandidate(I, HasDependences);
 
   return true;
 }
 
 bool llvm::isSafeToMoveBefore(BasicBlock &BB, Instruction &InsertPoint,
-                              DominatorTree &DT, const PostDominatorTree &PDT,
-                              DependenceInfo &DI) {
+                              DominatorTree *DT, const PostDominatorTree *PDT,
+                              DependenceInfo *DI) {
   return llvm::all_of(BB, [&](Instruction &I) {
     if (BB.getTerminator() == &I)
       return true;
 
     return isSafeToMoveBefore(I, InsertPoint, DT, PDT, DI);
   });
 }
 
 void llvm::moveInstructionsToTheBeginning(BasicBlock &FromBB, BasicBlock &ToBB,
-                                          DominatorTree &DT,
-                                          const PostDominatorTree &PDT,
-                                          DependenceInfo &DI) {
+                                          DominatorTree *DT,
+                                          const PostDominatorTree *PDT,
+                                          DependenceInfo *DI) {
   for (auto It = ++FromBB.rbegin(); It != FromBB.rend();) {
     Instruction *MovePos = ToBB.getFirstNonPHIOrDbg();
     Instruction &I = *It;
     // Increment the iterator before modifying FromBB.
     ++It;
 
     if (isSafeToMoveBefore(I, *MovePos, DT, PDT, DI))
       I.moveBefore(MovePos);
   }
 }
 
 void llvm::moveInstructionsToTheEnd(BasicBlock &FromBB, BasicBlock &ToBB,
-                                    DominatorTree &DT,
-                                    const PostDominatorTree &PDT,
-                                    DependenceInfo &DI) {
+                                    DominatorTree *DT,
+                                    const PostDominatorTree *PDT,
+                                    DependenceInfo *DI) {
   Instruction *MovePos = ToBB.getTerminator();
   while (FromBB.size() > 1) {
     Instruction &I = FromBB.front();
     if (isSafeToMoveBefore(I, *MovePos, DT, PDT, DI))
       I.moveBefore(MovePos);
   }
 }

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp

static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
   SMDiagnostic Err;
   std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
   if (!Mod)
     Err.print("CodeMoverUtilsTests", errs());
   return Mod;
 }
 
 static void run(Module &M, StringRef FuncName,
-                function_ref<void(Function &F, DominatorTree &DT,
-                                  PostDominatorTree &PDT, DependenceInfo &DI)>
+                function_ref<void(Function &F, DominatorTree *DT,
+                                  PostDominatorTree *PDT, DependenceInfo *DI)>
                     Test) {
   auto *F = M.getFunction(FuncName);
   DominatorTree DT(*F);
   PostDominatorTree PDT(*F);
   TargetLibraryInfoImpl TLII;
   TargetLibraryInfo TLI(TLII);
   AssumptionCache AC(*F);
   AliasAnalysis AA(TLI);
   LoopInfo LI(DT);
   ScalarEvolution SE(*F, TLI, AC, DT, LI);
   DependenceInfo DI(F, &AA, &SE, &LI);
-  Test(*F, DT, PDT, DI);
+  Test(*F, &DT, &PDT, &DI);
 }
 
 static BasicBlock *getBasicBlockByName(Function &F, StringRef Name) {
   for (BasicBlock &BB : F)
     if (BB.getName() == Name)
       return &BB;
   llvm_unreachable("Expected to find basic block!");
 }
std::unique_ptr<Module> M =
                    br i1 %cond2, label %if.third, label %if.third.end
                  if.third:
                    store i32 3, i32* %i, align 4
                    br label %if.third.end
                  if.third.end:
                    ret void
                  })");
   run(*M, "foo",
-      [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
-          DependenceInfo &DI) {
+      [&](Function &F, DominatorTree* DT, PostDominatorTree* PDT,
+          DependenceInfo* DI) {
         BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first");
         EXPECT_TRUE(
             isControlFlowEquivalent(*FirstIfBody, *FirstIfBody, DT, PDT));
         BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second");
         EXPECT_TRUE(
             isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT));
 
         BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.third");
std::unique_ptr<Module> M =
                    br label %if.sixth.end
                  if.sixth.else:
                    store i32 9, i32* %i, align 4
                    br label %if.sixth.end
                  if.sixth.end:
                    ret void
                  })");
   run(*M, "foo",
-      [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
-          DependenceInfo &DI) {
+      [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT,
+          DependenceInfo *DI) {
         BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first");
         BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second");
         BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.third");
         BasicBlock *ThirdElseBody = getBasicBlockByName(F, "if.third.else");
         EXPECT_TRUE(
             isControlFlowEquivalent(*FirstIfBody, *ThirdElseBody, DT, PDT));
         EXPECT_TRUE(
             isControlFlowEquivalent(*SecondIfBody, *ThirdElseBody, DT, PDT));
std::unique_ptr<Module> M =
            br i1 %cond1, label %if.inner.second, label %if.second.end
          if.inner.second:
            store i32 2, i32* %i, align 4
            br label %if.second.end
          if.second.end:
            ret void
          })");
   run(*M, "foo",
-      [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
-          DependenceInfo &DI) {
+      [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT,
+          DependenceInfo *DI) {
         BasicBlock *FirstOuterIfBody = getBasicBlockByName(F, "if.outer.first");
         BasicBlock *FirstInnerIfBody = getBasicBlockByName(F, "if.inner.first");
         BasicBlock *SecondOuterIfBody =
             getBasicBlockByName(F, "if.outer.second");
         BasicBlock *SecondInnerIfBody =
             getBasicBlockByName(F, "if.inner.second");
         EXPECT_TRUE(isControlFlowEquivalent(*FirstInnerIfBody,
                                             *SecondInnerIfBody, DT, PDT));
std::unique_ptr<Module> M = parseIR(
            br i1 %cond1, label %if.fourth, label %if.fourth.end
          if.fourth:
            store i32 4, i32* %i, align 4
            br label %if.fourth.end
          if.fourth.end:
            ret void
          })");
   run(*M, "foo",
-      [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
-          DependenceInfo &DI) {
+      [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT,
+          DependenceInfo *DI) {
         BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.inner.first");
         BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.inner.second");
         EXPECT_FALSE(
             isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT));
 
         BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.inner.third");
         BasicBlock *FourthIfBody = getBasicBlockByName(F, "if.fourth");
         EXPECT_TRUE(
std::unique_ptr<Module> M =
                    br i1 %tobool3, label %if.third, label %if.third.end
                  if.third:
                    store i32 3, i32* %i, align 4
                    br label %if.third.end
                  if.third.end:
                    ret void
                  })");
   run(*M, "foo",
-      [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
-          DependenceInfo &DI) {
+      [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT,
+          DependenceInfo *DI) {
         BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first");
         BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second");
         // Limitation: if we can prove cond haven't been modify between %0 and
         // %1, then we can prove FirstIfBody and SecondIfBody are control flow
         // equivalent.
         EXPECT_FALSE(
             isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT));
 
std::unique_ptr<Module> M =
                  succ1ret:
                    ret void
                  succ1succ1:
                    br label %bb
                  bb:
                    ret void
                  })");
   run(*M, "foo",
-      [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
-          DependenceInfo &DI) {
+      [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT,
+          DependenceInfo *DI) {
         BasicBlock &Idom = F.front();
         assert(Idom.getName() == "idom" && "Expecting BasicBlock idom");
         BasicBlock &BB = F.back();
         assert(BB.getName() == "bb" && "Expecting BasicBlock bb");
         EXPECT_FALSE(isControlFlowEquivalent(Idom, BB, DT, PDT));
       });
 }
 
std::unique_ptr<Module> M = parseIR(
          for.end:
            ret void
          }
          declare void @safecall() nounwind nosync willreturn
          declare void @unsafecall1()
          declare void @unsafecall2())");
 
   run(*M, "foo",
-      [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
-          DependenceInfo &DI) {
+      [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT,
+          DependenceInfo *DI) {
         BasicBlock *Entry = getBasicBlockByName(F, "entry");
         Instruction *CI_safecall = Entry->front().getNextNode();
         assert(isa<CallInst>(CI_safecall) &&
                "Expecting CI_safecall to be a CallInst");
         Instruction *CI_unsafecall = CI_safecall->getNextNode()->getNextNode();
         assert(isa<CallInst>(CI_unsafecall) &&
                "Expecting CI_unsafecall to be a CallInst");
         BasicBlock *ForBody = getBasicBlockByName(F, "for.body");
std::unique_ptr<Module> M =
                    %sub_op0 = add i32 %op0, 1
                    %sub = sub i32 %sub_op0, %op1
                    br label %if.end.second
                  if.end.second:
                    ret void
                  })");
 
   run(*M, "foo",
-      [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
-          DependenceInfo &DI) {
+      [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT,
+          DependenceInfo *DI) {
         Instruction *AddInst = getInstructionByName(F, "add");
         Instruction *SubInst = getInstructionByName(F, "sub");
 
         // Cannot move as %user uses %add and %sub doesn't dominates %user.
         EXPECT_FALSE(isSafeToMoveBefore(*AddInst, *SubInst, DT, PDT, DI));
 
         // Cannot move as %sub_op0 is an operand of %sub and %add doesn't
         // dominates %sub_op0.
std::unique_ptr<Module> M = parseIR(C, R"(define void @foo(i64 %N) {
                  for.latch:
                    %cmp = icmp slt i64 %inc, %N
                    br i1 %cmp, label %for.body, label %for.end
                  for.end:
                    ret void
                  })");
 
   run(*M, "foo",
-      [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
-          DependenceInfo &DI) {
+      [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT,
+          DependenceInfo *DI) {
         Instruction *IncInst = getInstructionByName(F, "inc");
         Instruction *CmpInst = getInstructionByName(F, "cmp");
 
         // Can move as the incoming block of %inc for %i (%for.latch) dominated
         // by %cmp.
         EXPECT_TRUE(isSafeToMoveBefore(*IncInst, *CmpInst, DT, PDT, DI));
       });
 }
std::unique_ptr<Module> M =
                    %sub_op0 = add i32 %op0, 1
                    %sub = sub i32 %sub_op0, %op1
                    br label %if.end.second
                  if.end.second:
                    ret void
                  })");
 
   run(*M, "foo",
-      [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
-          DependenceInfo &DI) {
+      [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT,
+          DependenceInfo *DI) {
         Instruction *AddInst = getInstructionByName(F, "add");
         Instruction *SubInst = getInstructionByName(F, "sub");
 
         // Cannot move as %user uses %add and %sub doesn't dominates %user.
         EXPECT_FALSE(isSafeToMoveBefore(*AddInst, *SubInst, DT, PDT, DI));
 
         // Cannot move as %sub_op0 is an operand of %sub and %add doesn't
         // dominates %sub_op0.
         EXPECT_FALSE(isSafeToMoveBefore(*SubInst, *AddInst, DT, PDT, DI));
       });
 }