diff options
Diffstat (limited to 'contrib/llvm-project/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp')
| -rw-r--r-- | contrib/llvm-project/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp | 425 |
1 files changed, 425 insertions, 0 deletions
diff --git a/contrib/llvm-project/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp b/contrib/llvm-project/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp new file mode 100644 index 000000000000..ce982c7403aa --- /dev/null +++ b/contrib/llvm-project/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp @@ -0,0 +1,425 @@ +//===- 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); + } +} |