diff --git a/llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h b/llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h --- a/llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h +++ b/llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h @@ -26,39 +26,41 @@ /// 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 diff --git a/llvm/lib/Transforms/Scalar/LoopFuse.cpp b/llvm/lib/Transforms/Scalar/LoopFuse.cpp --- a/llvm/lib/Transforms/Scalar/LoopFuse.cpp +++ b/llvm/lib/Transforms/Scalar/LoopFuse.cpp @@ -598,7 +598,7 @@ 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 @@ -743,8 +743,8 @@ } 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(*FC0, *FC1, @@ -756,8 +756,8 @@ 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(*FC0, *FC1, @@ -767,8 +767,8 @@ 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"); @@ -1102,7 +1102,7 @@ /// 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(); @@ -1147,7 +1147,7 @@ // 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 @@ -1367,11 +1367,12 @@ // 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"); diff --git a/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp b/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp --- a/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp +++ b/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp @@ -63,8 +63,8 @@ /// collected successfully, or we hit the limit. static const Optional 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 @@ -95,9 +95,10 @@ } // namespace const Optional 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; @@ -110,9 +111,9 @@ // 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. @@ -121,17 +122,17 @@ 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"); @@ -216,24 +217,25 @@ } 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"); @@ -297,8 +299,8 @@ } 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; @@ -313,23 +315,23 @@ 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(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(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); @@ -359,11 +361,23 @@ 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())) @@ -376,8 +390,8 @@ } 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; @@ -387,9 +401,9 @@ } 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; @@ -402,9 +416,9 @@ } 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(); diff --git a/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp b/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp --- a/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp +++ b/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp @@ -30,8 +30,8 @@ } static void run(Module &M, StringRef FuncName, - function_ref + function_ref Test) { auto *F = M.getFunction(FuncName); DominatorTree DT(*F); @@ -43,7 +43,7 @@ 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) { @@ -93,8 +93,8 @@ 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)); @@ -184,8 +184,8 @@ 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"); @@ -244,8 +244,8 @@ 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 = @@ -314,8 +314,8 @@ 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( @@ -368,8 +368,8 @@ 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 @@ -418,8 +418,8 @@ 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(); @@ -482,8 +482,8 @@ 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(CI_safecall) && @@ -572,8 +572,8 @@ })"); 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"); @@ -604,8 +604,8 @@ })"); 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"); @@ -637,8 +637,8 @@ })"); 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");