[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.

318

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?

318

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

30

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

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

226

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

231

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

318

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.

364

return false

372

return false

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp

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

318

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

318

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

318

Yes it does, Updated.

[asbirlea]

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

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

318

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

364

Only check PDT. DT has been checked above.

[Whitney]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

317

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.

318

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 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);
 
 /// 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);
 
 /// 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);
 

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)
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;
             }
           }

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

 bool llvm::isControlFlowEquivalent(const Instruction &I0, const Instruction &I1,
                                    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) {
   if (&BB0 == &BB1)
     return true;
 
   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);
   LLVM_DEBUG(dbgs() << "The nearest common dominator of " << BB0.getName()
                     << " and " << BB1.getName() << " is "
                     << CommonDominator->getName() << "\n");
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 false;
+
+  // 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 false;
+
   // 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) {
   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))
+    if (isSafeToMoveBefore(I, *MovePos, &DT, &PDT, &DI))
       I.moveBefore(MovePos);
   }
 }
 
 void llvm::moveInstructionsToTheEnd(BasicBlock &FromBB, BasicBlock &ToBB,
                                     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))
+    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) {
   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)>
                     Test) {
   auto *F = M.getFunction(FuncName);
   DominatorTree DT(*F);
   PostDominatorTree PDT(*F);
   TargetLibraryInfoImpl TLII;
   TargetLibraryInfo TLI(TLII);
   AssumptionCache AC(*F);
   AliasAnalysis AA(TLI);
run(*M, "foo",
         Instruction *LI1 = getInstructionByName(F, "load1");
         Instruction *LI2 = getInstructionByName(F, "load2");
         Instruction *SI_A6 =
             getInstructionByName(F, "arrayidx_A6")->getNextNode();
 
         // Can move after CI_safecall, as it does not throw, not synchronize, or
         // must return.
         EXPECT_TRUE(isSafeToMoveBefore(*CI_safecall->getPrevNode(),
-                                       *CI_safecall->getNextNode(), DT, PDT,
-                                       DI));
+                                       *CI_safecall->getNextNode(), &DT, &PDT,
+                                       &DI));
 
         // Cannot move CI_unsafecall, as it may throw.
         EXPECT_FALSE(isSafeToMoveBefore(*CI_unsafecall->getNextNode(),
-                                        *CI_unsafecall, DT, PDT, DI));
+                                        *CI_unsafecall, &DT, &PDT, &DI));
 
         // Moving instruction to non control flow equivalent places are not
         // supported.
-        EXPECT_FALSE(
-            isSafeToMoveBefore(*SI_A5, *Entry->getTerminator(), DT, PDT, DI));
+        EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *Entry->getTerminator(), &DT,
+                                        &PDT, &DI));
 
         // Moving PHINode is not supported.
         EXPECT_FALSE(isSafeToMoveBefore(PN, *PN.getNextNode()->getNextNode(),
-                                        DT, PDT, DI));
+                                        &DT, &PDT, &DI));
 
         // Cannot move non-PHINode before PHINode.
-        EXPECT_FALSE(isSafeToMoveBefore(*PN.getNextNode(), PN, DT, PDT, DI));
+        EXPECT_FALSE(isSafeToMoveBefore(*PN.getNextNode(), PN, &DT, &PDT, &DI));
 
         // Moving Terminator is not supported.
         EXPECT_FALSE(isSafeToMoveBefore(*Entry->getTerminator(),
-                                        *PN.getNextNode(), DT, PDT, DI));
+                                        *PN.getNextNode(), &DT, &PDT, &DI));
 
         // Cannot move %arrayidx_A after SI, as SI is its user.
         EXPECT_FALSE(isSafeToMoveBefore(*SI->getPrevNode(), *SI->getNextNode(),
-                                        DT, PDT, DI));
+                                        &DT, &PDT, &DI));
 
         // Cannot move SI before %arrayidx_A, as %arrayidx_A is its operand.
-        EXPECT_FALSE(isSafeToMoveBefore(*SI, *SI->getPrevNode(), DT, PDT, DI));
+        EXPECT_FALSE(
+            isSafeToMoveBefore(*SI, *SI->getPrevNode(), &DT, &PDT, &DI));
 
         // Cannot move LI2 after SI_A6, as there is a flow dependence.
         EXPECT_FALSE(
-            isSafeToMoveBefore(*LI2, *SI_A6->getNextNode(), DT, PDT, DI));
+            isSafeToMoveBefore(*LI2, *SI_A6->getNextNode(), &DT, &PDT, &DI));
 
         // Cannot move SI after LI1, as there is a anti dependence.
-        EXPECT_FALSE(isSafeToMoveBefore(*SI, *LI1->getNextNode(), DT, PDT, DI));
+        EXPECT_FALSE(
+            isSafeToMoveBefore(*SI, *LI1->getNextNode(), &DT, &PDT, &DI));
 
         // Cannot move SI_A5 after SI, as there is a output dependence.
-        EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *LI1, DT, PDT, DI));
+        EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *LI1, &DT, &PDT, &DI));
 
         // Can move LI2 before LI1, as there is only an input dependence.
-        EXPECT_TRUE(isSafeToMoveBefore(*LI2, *LI1, DT, PDT, DI));
+        EXPECT_TRUE(isSafeToMoveBefore(*LI2, *LI1, &DT, &PDT, &DI));
       });
 }
 
 TEST(CodeMoverUtils, IsSafeToMoveTest2) {
   LLVMContext C;
 
   std::unique_ptr<Module> M =
       parseIR(C, R"(define void @foo(i1 %cond, i32 %op0, i32 %op1) {
TEST(CodeMoverUtils, IsSafeToMoveTest2) {
 
   run(*M, "foo",
       [&](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));
+        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));
+        EXPECT_FALSE(isSafeToMoveBefore(*SubInst, *AddInst, &DT, &PDT, &DI));
       });
 }
 
 TEST(CodeMoverUtils, IsSafeToMoveTest3) {
   LLVMContext C;
 
   std::unique_ptr<Module> M = parseIR(C, R"(define void @foo(i64 %N) {
                  entry:
TEST(CodeMoverUtils, IsSafeToMoveTest3) {
   run(*M, "foo",
       [&](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));
+        EXPECT_TRUE(isSafeToMoveBefore(*IncInst, *CmpInst, &DT, &PDT, &DI));
       });
 }
 
 TEST(CodeMoverUtils, IsSafeToMoveTest4) {
   LLVMContext C;
 
   std::unique_ptr<Module> M =
       parseIR(C, R"(define void @foo(i1 %cond, i32 %op0, i32 %op1) {
TEST(CodeMoverUtils, IsSafeToMoveTest4) {
 
   run(*M, "foo",
       [&](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));
+        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));
+        EXPECT_FALSE(isSafeToMoveBefore(*SubInst, *AddInst, &DT, &PDT, &DI));
       });
 }