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,39 @@ /// 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, const PostDominatorTree *PDT, + DependenceInfo *DI); /// 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, const PostDominatorTree *PDT, + DependenceInfo *DI); /// 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 @@ -510,15 +510,15 @@ 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) {} @@ -576,9 +576,9 @@ 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 @@ -606,7 +606,7 @@ /// 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; @@ -809,7 +809,7 @@ // possible to identify them after fusion is complete. reportLoopFusion(*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!"); @@ -912,8 +912,8 @@ const SCEVAddRecExpr *AddRec = dyn_cast(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; @@ -947,7 +947,7 @@ 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 @@ -985,7 +985,7 @@ 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) @@ -1303,9 +1303,9 @@ #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 @@ -1578,9 +1578,9 @@ #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 @@ -1617,10 +1617,10 @@ if (skipFunction(F)) return false; auto &LI = getAnalysis().getLoopInfo(); - auto &DT = getAnalysis().getDomTree(); - auto &DI = getAnalysis().getDI(); + auto *DT = &getAnalysis().getDomTree(); + auto *DI = &getAnalysis().getDI(); auto &SE = getAnalysis().getSE(); - auto &PDT = getAnalysis().getPostDomTree(); + auto *PDT = &getAnalysis().getPostDomTree(); auto &ORE = getAnalysis().getORE(); const DataLayout &DL = F.getParent()->getDataLayout(); @@ -1632,10 +1632,10 @@ PreservedAnalyses LoopFusePass::run(Function &F, FunctionAnalysisManager &AM) { auto &LI = AM.getResult(F); - auto &DT = AM.getResult(F); - auto &DI = AM.getResult(F); + auto *DT = &AM.getResult(F); + auto *DI = &AM.getResult(F); auto &SE = AM.getResult(F); - auto &PDT = AM.getResult(F); + auto *PDT = &AM.getResult(F); auto &ORE = AM.getResult(F); const DataLayout &DL = F.getParent()->getDataLayout(); 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,9 @@ } bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint, - DominatorTree &DT, const PostDominatorTree &PDT, - DependenceInfo &DI) { + DominatorTree *DT = nullptr, + const PostDominatorTree *PDT = nullptr, + DependenceInfo *DI = nullptr) { // Cannot move itself before itself. if (&I == &InsertPoint) return false; @@ -313,23 +316,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 true; - 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 +362,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 +391,9 @@ } bool llvm::isSafeToMoveBefore(BasicBlock &BB, Instruction &InsertPoint, - DominatorTree &DT, const PostDominatorTree &PDT, - DependenceInfo &DI) { + DominatorTree *DT = nullptr, + const PostDominatorTree *PDT = nullptr, + DependenceInfo *DI = nullptr) { return llvm::all_of(BB, [&](Instruction &I) { if (BB.getTerminator() == &I) return true; @@ -387,9 +403,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 +418,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");