| //===- CodeMoverUtils.cpp - CodeMover Utilities ----------------------------==// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This family of functions perform movements on basic blocks, and instructions |
| // contained within a function. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "llvm/Transforms/Utils/CodeMoverUtils.h" |
| #include "llvm/ADT/Optional.h" |
| #include "llvm/ADT/Statistic.h" |
| #include "llvm/Analysis/DependenceAnalysis.h" |
| #include "llvm/Analysis/PostDominators.h" |
| #include "llvm/Analysis/ValueTracking.h" |
| #include "llvm/IR/Dominators.h" |
| |
| using namespace llvm; |
| |
| #define DEBUG_TYPE "codemover-utils" |
| |
| STATISTIC(HasDependences, |
| "Cannot move across instructions that has memory dependences"); |
| STATISTIC(MayThrowException, "Cannot move across instructions that may throw"); |
| STATISTIC(NotControlFlowEquivalent, |
| "Instructions are not control flow equivalent"); |
| STATISTIC(NotMovedPHINode, "Movement of PHINodes are not supported"); |
| STATISTIC(NotMovedTerminator, "Movement of Terminator are not supported"); |
| |
| namespace { |
| /// Represent a control condition. A control condition is a condition of a |
| /// terminator to decide which successors to execute. The pointer field |
| /// represents the address of the condition of the terminator. The integer field |
| /// is a bool, it is true when the basic block is executed when V is true. For |
| /// example, `br %cond, bb0, bb1` %cond is a control condition of bb0 with the |
| /// integer field equals to true, while %cond is a control condition of bb1 with |
| /// the integer field equals to false. |
| using ControlCondition = PointerIntPair<Value *, 1, bool>; |
| #ifndef NDEBUG |
| raw_ostream &operator<<(raw_ostream &OS, const ControlCondition &C) { |
| OS << "[" << *C.getPointer() << ", " << (C.getInt() ? "true" : "false") |
| << "]"; |
| return OS; |
| } |
| #endif |
| |
| /// Represent a set of control conditions required to execute ToBB from FromBB. |
| class ControlConditions { |
| using ConditionVectorTy = SmallVector<ControlCondition, 6>; |
| |
| /// A SmallVector of control conditions. |
| ConditionVectorTy Conditions; |
| |
| 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, |
| 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; } |
| |
| /// Add \p V as one of the ControlCondition in Condition with IsTrueCondition |
| /// equals to \p True. Return true if inserted successfully. |
| bool addControlCondition(ControlCondition C); |
| |
| /// Return true if for all control conditions in Conditions, there exists an |
| /// equivalent control condition in \p Other.Conditions. |
| bool isEquivalent(const ControlConditions &Other) const; |
| |
| /// Return true if \p C1 and \p C2 are equivalent. |
| static bool isEquivalent(const ControlCondition &C1, |
| const ControlCondition &C2); |
| |
| private: |
| ControlConditions() = default; |
| |
| static bool isEquivalent(const Value &V1, const Value &V2); |
| static bool isInverse(const Value &V1, const Value &V2); |
| }; |
| } // namespace |
| |
| static bool domTreeLevelBefore(DominatorTree *DT, const Instruction *InstA, |
| const Instruction *InstB) { |
| // Use ordered basic block in case the 2 instructions are in the same |
| // block. |
| if (InstA->getParent() == InstB->getParent()) |
| return InstA->comesBefore(InstB); |
| |
| DomTreeNode *DA = DT->getNode(InstA->getParent()); |
| DomTreeNode *DB = DT->getNode(InstB->getParent()); |
| return DA->getLevel() < DB->getLevel(); |
| } |
| |
| 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 |
| // 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) && |
| "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)) { |
| LLVM_DEBUG(dbgs() << CurBlock->getName() |
| << " is executed unconditionally from " |
| << IDom->getName() << "\n"); |
| } 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))) { |
| 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 (Inserted) |
| ++NumConditions; |
| |
| if (MaxLookup != 0 && NumConditions > MaxLookup) |
| return None; |
| |
| CurBlock = IDom; |
| } while (CurBlock != &Dominator); |
| |
| return Conditions; |
| } |
| |
| bool ControlConditions::addControlCondition(ControlCondition C) { |
| bool Inserted = false; |
| if (none_of(Conditions, [&](ControlCondition &Exists) { |
| return ControlConditions::isEquivalent(C, Exists); |
| })) { |
| Conditions.push_back(C); |
| Inserted = true; |
| } |
| |
| LLVM_DEBUG(dbgs() << (Inserted ? "Inserted " : "Not inserted ") << C << "\n"); |
| return Inserted; |
| } |
| |
| bool ControlConditions::isEquivalent(const ControlConditions &Other) const { |
| if (Conditions.empty() && Other.Conditions.empty()) |
| return true; |
| |
| if (Conditions.size() != Other.Conditions.size()) |
| return false; |
| |
| return all_of(Conditions, [&](const ControlCondition &C) { |
| return any_of(Other.Conditions, [&](const ControlCondition &OtherC) { |
| return ControlConditions::isEquivalent(C, OtherC); |
| }); |
| }); |
| } |
| |
| bool ControlConditions::isEquivalent(const ControlCondition &C1, |
| const ControlCondition &C2) { |
| if (C1.getInt() == C2.getInt()) { |
| if (isEquivalent(*C1.getPointer(), *C2.getPointer())) |
| return true; |
| } else if (isInverse(*C1.getPointer(), *C2.getPointer())) |
| return true; |
| |
| return false; |
| } |
| |
| // FIXME: Use SCEV and reuse GVN/CSE logic to check for equivalence between |
| // Values. |
| // Currently, isEquivalent rely on other passes to ensure equivalent conditions |
| // have the same value, e.g. GVN. |
| bool ControlConditions::isEquivalent(const Value &V1, const Value &V2) { |
| return &V1 == &V2; |
| } |
| |
| bool ControlConditions::isInverse(const Value &V1, const Value &V2) { |
| if (const CmpInst *Cmp1 = dyn_cast<CmpInst>(&V1)) |
| if (const CmpInst *Cmp2 = dyn_cast<CmpInst>(&V2)) { |
| if (Cmp1->getPredicate() == Cmp2->getInversePredicate() && |
| Cmp1->getOperand(0) == Cmp2->getOperand(0) && |
| Cmp1->getOperand(1) == Cmp2->getOperand(1)) |
| return true; |
| |
| if (Cmp1->getPredicate() == |
| CmpInst::getSwappedPredicate(Cmp2->getInversePredicate()) && |
| 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) { |
| 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"); |
| |
| const Optional<ControlConditions> BB0Conditions = |
| ControlConditions::collectControlConditions(BB0, *CommonDominator, DT, |
| PDT); |
| if (BB0Conditions == None) |
| return false; |
| |
| const Optional<ControlConditions> BB1Conditions = |
| ControlConditions::collectControlConditions(BB1, *CommonDominator, DT, |
| PDT); |
| if (BB1Conditions == None) |
| return false; |
| |
| return BB0Conditions->isEquivalent(*BB1Conditions); |
| } |
| |
| static bool reportInvalidCandidate(const Instruction &I, |
| llvm::Statistic &Stat) { |
| ++Stat; |
| LLVM_DEBUG(dbgs() << "Unable to move instruction: " << I << ". " |
| << Stat.getDesc()); |
| return false; |
| } |
| |
| /// Collect all instructions in between \p StartInst and \p EndInst, and store |
| /// them in \p InBetweenInsts. |
| static void |
| collectInstructionsInBetween(Instruction &StartInst, const Instruction &EndInst, |
| SmallPtrSetImpl<Instruction *> &InBetweenInsts) { |
| assert(InBetweenInsts.empty() && "Expecting InBetweenInsts to be empty"); |
| |
| /// Get the next instructions of \p I, and push them to \p WorkList. |
| auto getNextInsts = [](Instruction &I, |
| SmallPtrSetImpl<Instruction *> &WorkList) { |
| if (Instruction *NextInst = I.getNextNode()) |
| WorkList.insert(NextInst); |
| else { |
| assert(I.isTerminator() && "Expecting a terminator instruction"); |
| for (BasicBlock *Succ : successors(&I)) |
| WorkList.insert(&Succ->front()); |
| } |
| }; |
| |
| SmallPtrSet<Instruction *, 10> WorkList; |
| getNextInsts(StartInst, WorkList); |
| while (!WorkList.empty()) { |
| Instruction *CurInst = *WorkList.begin(); |
| WorkList.erase(CurInst); |
| |
| if (CurInst == &EndInst) |
| continue; |
| |
| if (!InBetweenInsts.insert(CurInst).second) |
| continue; |
| |
| getNextInsts(*CurInst, WorkList); |
| } |
| } |
| |
| bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint, |
| DominatorTree &DT, const PostDominatorTree *PDT, |
| DependenceInfo *DI) { |
| // Skip tests when we don't have PDT or DI |
| if (!PDT || !DI) |
| return false; |
| |
| // 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); |
| |
| 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)) |
| return false; |
| 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)) |
| return false; |
| |
| DT.updateDFSNumbers(); |
| const bool MoveForward = domTreeLevelBefore(&DT, &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); |
| |
| // Check if there exists instructions which may throw, may synchonize, or may |
| // never return, from I to InsertPoint. |
| if (!isSafeToSpeculativelyExecute(&I)) |
| if (llvm::any_of(InstsToCheck, [](Instruction *I) { |
| if (I->mayThrow()) |
| return true; |
| |
| const CallBase *CB = dyn_cast<CallBase>(I); |
| if (!CB) |
| return false; |
| if (!CB->hasFnAttr(Attribute::WillReturn)) |
| return true; |
| if (!CB->hasFnAttr(Attribute::NoSync)) |
| return true; |
| |
| return false; |
| })) { |
| return reportInvalidCandidate(I, MayThrowException); |
| } |
| |
| // Check if I has any output/flow/anti dependences with instructions from \p |
| // StartInst to \p EndInst. |
| if (llvm::any_of(InstsToCheck, [&DI, &I](Instruction *CurInst) { |
| 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) { |
| 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)) |
| 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)) |
| I.moveBefore(MovePos); |
| } |
| } |
