[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

514

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

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

102

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.

319

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

102

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?

319

Acknowledged and updated

[Whitney]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

102

in that case change the parameters back to references for ControlConditions

[RithikSharma]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

102

Thanks, updated.

[Whitney]

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

29

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

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

225

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

230

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

319

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.

365

return false

373

return false

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp

33

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

319

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

319

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

319

Yes it does, Updated.

[asbirlea]

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

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

319

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

365

Only check PDT. DT has been checked above.

[Whitney]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

318

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.

319

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;
   ScalarEvolution &SE;
   PostDominatorTree &PDT;
   OptimizationRemarkEmitter &ORE;
 
 public:
   LoopFuser(LoopInfo &LI, DominatorTree &DT, DependenceInfo &DI,
             ScalarEvolution &SE, PostDominatorTree &PDT,
             OptimizationRemarkEmitter &ORE, const DataLayout &DL)
private:
   /// the other is guaranteed to execute. This is determined using dominators
   /// and post-dominators: if A dominates B and B post-dominates A then A and B
   /// are control-flow equivalent.
   bool isControlFlowEquivalent(const FusionCandidate &FC0,
                                const FusionCandidate &FC1) const {
     assert(FC0.Preheader && FC1.Preheader && "Expecting valid preheaders");
 
     return ::isControlFlowEquivalent(*FC0.getEntryBlock(), *FC1.getEntryBlock(),
-                                     DT, PDT);
+                                     &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);
for (auto &CandidateSet : FusionCandidates) {
             LLVM_DEBUG(dbgs() << "Fusion candidates do not have identical "
                                  "guards. Not Fusing.\n");
             reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
                                                        NonIdenticalGuards);
             continue;
           }
 
           if (!isSafeToMoveBefore(*FC1->Preheader,
-                                  *FC0->Preheader->getTerminator(), DT, PDT,
-                                  DI)) {
+                                  *FC0->Preheader->getTerminator(), &DT, &PDT,
+                                  &DI)) {
             LLVM_DEBUG(dbgs() << "Fusion candidate contains unsafe "
                                  "instructions in preheader. Not fusing.\n");
             reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
                                                        NonEmptyPreheader);
             continue;
           }
 
           if (FC0->GuardBranch) {
             assert(FC1->GuardBranch && "Expecting valid FC1 guard branch");
 
             if (!isSafeToMoveBefore(*FC0->ExitBlock,
-                                    *FC1->ExitBlock->getFirstNonPHIOrDbg(), DT,
-                                    PDT, DI)) {
+                                    *FC1->ExitBlock->getFirstNonPHIOrDbg(), &DT,
+                                    &PDT, &DI)) {
               LLVM_DEBUG(dbgs() << "Fusion candidate contains unsafe "
                                    "instructions in exit block. Not fusing.\n");
               reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
                                                          NonEmptyExitBlock);
               continue;
             }
 
             if (!isSafeToMoveBefore(
                     *FC1->GuardBranch->getParent(),
-                    *FC0->GuardBranch->getParent()->getTerminator(), DT, PDT,
-                    DI)) {
+                    *FC0->GuardBranch->getParent()->getTerminator(), &DT, &PDT,
+                    &DI)) {
               LLVM_DEBUG(dbgs()
                          << "Fusion candidate contains unsafe "
                             "instructions in guard block. Not fusing.\n");
               reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
                                                          NonEmptyGuardBlock);
               continue;
             }
           }
if (FCLatchBranch) {
       FCLatchBranch->setCondition(
           llvm::ConstantInt::getTrue(FCLatchBranch->getCondition()->getType()));
     }
   }
 
   /// Move instructions from FC0.Latch to FC1.Latch. If FC0.Latch has an unique
   /// successor, then merge FC0.Latch with its unique successor.
   void mergeLatch(const FusionCandidate &FC0, const FusionCandidate &FC1) {
-    moveInstructionsToTheBeginning(*FC0.Latch, *FC1.Latch, DT, PDT, DI);
+    moveInstructionsToTheBeginning(*FC0.Latch, *FC1.Latch, &DT, &PDT, &DI);
     if (BasicBlock *Succ = FC0.Latch->getUniqueSuccessor()) {
       MergeBlockIntoPredecessor(Succ, &DTU, &LI);
       DTU.flush();
     }
   }
 
   /// Fuse two fusion candidates, creating a new fused loop.
   ///
Loop *performFusion(const FusionCandidate &FC0, const FusionCandidate &FC1) {
     assert(FC0.isValid() && FC1.isValid() &&
            "Expecting valid fusion candidates");
 
     LLVM_DEBUG(dbgs() << "Fusion Candidate 0: \n"; FC0.dump();
                dbgs() << "Fusion Candidate 1: \n"; FC1.dump(););
 
     // Move instructions from the preheader of FC1 to the end of the preheader
     // of FC0.
-    moveInstructionsToTheEnd(*FC1.Preheader, *FC0.Preheader, DT, PDT, DI);
+    moveInstructionsToTheEnd(*FC1.Preheader, *FC0.Preheader, &DT, &PDT, &DI);
 
     // Fusing guarded loops is handled slightly differently than non-guarded
     // loops and has been broken out into a separate method instead of trying to
     // intersperse the logic within a single method.
     if (FC0.GuardBranch)
       return fuseGuardedLoops(FC0, FC1);
 
     assert(FC1.Preheader == FC0.ExitBlock);
Loop *fuseGuardedLoops(const FusionCandidate &FC0,
 
     BasicBlock *FC0GuardBlock = FC0.GuardBranch->getParent();
     BasicBlock *FC1GuardBlock = FC1.GuardBranch->getParent();
     BasicBlock *FC0NonLoopBlock = FC0.getNonLoopBlock();
     BasicBlock *FC1NonLoopBlock = FC1.getNonLoopBlock();
 
     // Move instructions from the exit block of FC0 to the beginning of the exit
     // block of FC1.
-    moveInstructionsToTheBeginning(*FC0.ExitBlock, *FC1.ExitBlock, DT, PDT, DI);
+    moveInstructionsToTheBeginning(*FC0.ExitBlock, *FC1.ExitBlock, &DT, &PDT,
+                                   &DI);
 
     // Move instructions from the guard block of FC1 to the end of the guard
     // block of FC0.
-    moveInstructionsToTheEnd(*FC1GuardBlock, *FC0GuardBlock, DT, PDT, DI);
+    moveInstructionsToTheEnd(*FC1GuardBlock, *FC0GuardBlock, &DT, &PDT, &DI);
 
     assert(FC0NonLoopBlock == FC1GuardBlock && "Loops are not adjacent");
 
     SmallVector<DominatorTree::UpdateType, 8> TreeUpdates;
 
     ////////////////////////////////////////////////////////////////////////////
     // Update the Loop Guard
     ////////////////////////////////////////////////////////////////////////////

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

 };
 } // 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");
 
   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
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);
+      ControlConditions::collectControlConditions(BB0, *CommonDominator, *DT,
+                                                  *PDT);
   if (BB0Conditions == None)
     return false;
 
   const Optional<ControlConditions> BB1Conditions =
-      ControlConditions::collectControlConditions(BB1, *CommonDominator, DT,
-                                                  PDT);
+      ControlConditions::collectControlConditions(BB1, *CommonDominator, *DT,
+                                                  *PDT);
   if (BB1Conditions == None)
     return false;
 
   return BB0Conditions->isEquivalent(*BB1Conditions);
 }
 
 static bool reportInvalidCandidate(const Instruction &I,
                                    llvm::Statistic &Stat) {
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 false;
 
-  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));
       });
 }