491 lines · cpp
1//===- CodeMoverUtils.cpp - CodeMover Utilities ----------------------------==//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This family of functions perform movements on basic blocks, and instructions10// contained within a function.11//12//===----------------------------------------------------------------------===//13 14#include "llvm/Transforms/Utils/CodeMoverUtils.h"15#include "llvm/ADT/Statistic.h"16#include "llvm/Analysis/DependenceAnalysis.h"17#include "llvm/Analysis/PostDominators.h"18#include "llvm/Analysis/ValueTracking.h"19#include "llvm/IR/Dominators.h"20 21using namespace llvm;22 23#define DEBUG_TYPE "codemover-utils"24 25STATISTIC(HasDependences,26 "Cannot move across instructions that has memory dependences");27STATISTIC(MayThrowException, "Cannot move across instructions that may throw");28STATISTIC(NotControlFlowEquivalent,29 "Instructions are not control flow equivalent");30STATISTIC(NotMovedPHINode, "Movement of PHINodes are not supported");31STATISTIC(NotMovedTerminator, "Movement of Terminator are not supported");32 33namespace {34/// Represent a control condition. A control condition is a condition of a35/// terminator to decide which successors to execute. The pointer field36/// represents the address of the condition of the terminator. The integer field37/// is a bool, it is true when the basic block is executed when V is true. For38/// example, `br %cond, bb0, bb1` %cond is a control condition of bb0 with the39/// integer field equals to true, while %cond is a control condition of bb1 with40/// the integer field equals to false.41using ControlCondition = PointerIntPair<Value *, 1, bool>;42#ifndef NDEBUG43raw_ostream &operator<<(raw_ostream &OS, const ControlCondition &C) {44 OS << "[" << *C.getPointer() << ", " << (C.getInt() ? "true" : "false")45 << "]";46 return OS;47}48#endif49 50/// Represent a set of control conditions required to execute ToBB from FromBB.51class ControlConditions {52 using ConditionVectorTy = SmallVector<ControlCondition, 6>;53 54 /// A SmallVector of control conditions.55 ConditionVectorTy Conditions;56 57public:58 /// Return a ControlConditions which stores all conditions required to execute59 /// \p BB from \p Dominator. If \p MaxLookup is non-zero, it limits the60 /// number of conditions to collect. Return std::nullopt if not all conditions61 /// are collected successfully, or we hit the limit.62 static const std::optional<ControlConditions>63 collectControlConditions(const BasicBlock &BB, const BasicBlock &Dominator,64 const DominatorTree &DT,65 const PostDominatorTree &PDT,66 unsigned MaxLookup = 6);67 68 /// Return true if there exists no control conditions required to execute ToBB69 /// from FromBB.70 bool isUnconditional() const { return Conditions.empty(); }71 72 /// Return a constant reference of Conditions.73 const ConditionVectorTy &getControlConditions() const { return Conditions; }74 75 /// Add \p V as one of the ControlCondition in Condition with IsTrueCondition76 /// equals to \p True. Return true if inserted successfully.77 bool addControlCondition(ControlCondition C);78 79 /// Return true if for all control conditions in Conditions, there exists an80 /// equivalent control condition in \p Other.Conditions.81 bool isEquivalent(const ControlConditions &Other) const;82 83 /// Return true if \p C1 and \p C2 are equivalent.84 static bool isEquivalent(const ControlCondition &C1,85 const ControlCondition &C2);86 87private:88 ControlConditions() = default;89 90 static bool isEquivalent(const Value &V1, const Value &V2);91 static bool isInverse(const Value &V1, const Value &V2);92};93} // namespace94 95static bool domTreeLevelBefore(DominatorTree *DT, const Instruction *InstA,96 const Instruction *InstB) {97 // Use ordered basic block in case the 2 instructions are in the same98 // block.99 if (InstA->getParent() == InstB->getParent())100 return InstA->comesBefore(InstB);101 102 DomTreeNode *DA = DT->getNode(InstA->getParent());103 DomTreeNode *DB = DT->getNode(InstB->getParent());104 return DA->getLevel() < DB->getLevel();105}106 107const std::optional<ControlConditions>108ControlConditions::collectControlConditions(const BasicBlock &BB,109 const BasicBlock &Dominator,110 const DominatorTree &DT,111 const PostDominatorTree &PDT,112 unsigned MaxLookup) {113 assert(DT.dominates(&Dominator, &BB) && "Expecting Dominator to dominate BB");114 115 ControlConditions Conditions;116 unsigned NumConditions = 0;117 118 // BB is executed unconditional from itself.119 if (&Dominator == &BB)120 return Conditions;121 122 const BasicBlock *CurBlock = &BB;123 // Walk up the dominator tree from the associated DT node for BB to the124 // associated DT node for Dominator.125 do {126 assert(DT.getNode(CurBlock) && "Expecting a valid DT node for CurBlock");127 BasicBlock *IDom = DT.getNode(CurBlock)->getIDom()->getBlock();128 assert(DT.dominates(&Dominator, IDom) &&129 "Expecting Dominator to dominate IDom");130 131 // Limitation: can only handle branch instruction currently.132 const BranchInst *BI = dyn_cast<BranchInst>(IDom->getTerminator());133 if (!BI)134 return std::nullopt;135 136 bool Inserted = false;137 if (PDT.dominates(CurBlock, IDom)) {138 LLVM_DEBUG(dbgs() << CurBlock->getName()139 << " is executed unconditionally from "140 << IDom->getName() << "\n");141 } else if (PDT.dominates(CurBlock, BI->getSuccessor(0))) {142 LLVM_DEBUG(dbgs() << CurBlock->getName() << " is executed when \""143 << *BI->getCondition() << "\" is true from "144 << IDom->getName() << "\n");145 Inserted = Conditions.addControlCondition(146 ControlCondition(BI->getCondition(), true));147 } else if (PDT.dominates(CurBlock, BI->getSuccessor(1))) {148 LLVM_DEBUG(dbgs() << CurBlock->getName() << " is executed when \""149 << *BI->getCondition() << "\" is false from "150 << IDom->getName() << "\n");151 Inserted = Conditions.addControlCondition(152 ControlCondition(BI->getCondition(), false));153 } else154 return std::nullopt;155 156 if (Inserted)157 ++NumConditions;158 159 if (MaxLookup != 0 && NumConditions > MaxLookup)160 return std::nullopt;161 162 CurBlock = IDom;163 } while (CurBlock != &Dominator);164 165 return Conditions;166}167 168bool ControlConditions::addControlCondition(ControlCondition C) {169 bool Inserted = false;170 if (none_of(Conditions, [&](ControlCondition &Exists) {171 return ControlConditions::isEquivalent(C, Exists);172 })) {173 Conditions.push_back(C);174 Inserted = true;175 }176 177 LLVM_DEBUG(dbgs() << (Inserted ? "Inserted " : "Not inserted ") << C << "\n");178 return Inserted;179}180 181bool ControlConditions::isEquivalent(const ControlConditions &Other) const {182 if (Conditions.empty() && Other.Conditions.empty())183 return true;184 185 if (Conditions.size() != Other.Conditions.size())186 return false;187 188 return all_of(Conditions, [&](const ControlCondition &C) {189 return any_of(Other.Conditions, [&](const ControlCondition &OtherC) {190 return ControlConditions::isEquivalent(C, OtherC);191 });192 });193}194 195bool ControlConditions::isEquivalent(const ControlCondition &C1,196 const ControlCondition &C2) {197 if (C1.getInt() == C2.getInt()) {198 if (isEquivalent(*C1.getPointer(), *C2.getPointer()))199 return true;200 } else if (isInverse(*C1.getPointer(), *C2.getPointer()))201 return true;202 203 return false;204}205 206// FIXME: Use SCEV and reuse GVN/CSE logic to check for equivalence between207// Values.208// Currently, isEquivalent rely on other passes to ensure equivalent conditions209// have the same value, e.g. GVN.210bool ControlConditions::isEquivalent(const Value &V1, const Value &V2) {211 return &V1 == &V2;212}213 214bool ControlConditions::isInverse(const Value &V1, const Value &V2) {215 if (const CmpInst *Cmp1 = dyn_cast<CmpInst>(&V1))216 if (const CmpInst *Cmp2 = dyn_cast<CmpInst>(&V2)) {217 if (Cmp1->getPredicate() == Cmp2->getInversePredicate() &&218 Cmp1->getOperand(0) == Cmp2->getOperand(0) &&219 Cmp1->getOperand(1) == Cmp2->getOperand(1))220 return true;221 222 if (Cmp1->getPredicate() ==223 CmpInst::getSwappedPredicate(Cmp2->getInversePredicate()) &&224 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&225 Cmp1->getOperand(1) == Cmp2->getOperand(0))226 return true;227 }228 return false;229}230 231bool llvm::isControlFlowEquivalent(const Instruction &I0, const Instruction &I1,232 const DominatorTree &DT,233 const PostDominatorTree &PDT) {234 return isControlFlowEquivalent(*I0.getParent(), *I1.getParent(), DT, PDT);235}236 237bool llvm::isControlFlowEquivalent(const BasicBlock &BB0, const BasicBlock &BB1,238 const DominatorTree &DT,239 const PostDominatorTree &PDT) {240 if (&BB0 == &BB1)241 return true;242 243 if ((DT.dominates(&BB0, &BB1) && PDT.dominates(&BB1, &BB0)) ||244 (PDT.dominates(&BB0, &BB1) && DT.dominates(&BB1, &BB0)))245 return true;246 247 // If the set of conditions required to execute BB0 and BB1 from their common248 // dominator are the same, then BB0 and BB1 are control flow equivalent.249 const BasicBlock *CommonDominator = DT.findNearestCommonDominator(&BB0, &BB1);250 LLVM_DEBUG(dbgs() << "The nearest common dominator of " << BB0.getName()251 << " and " << BB1.getName() << " is "252 << CommonDominator->getName() << "\n");253 254 const std::optional<ControlConditions> BB0Conditions =255 ControlConditions::collectControlConditions(BB0, *CommonDominator, DT,256 PDT);257 if (BB0Conditions == std::nullopt)258 return false;259 260 const std::optional<ControlConditions> BB1Conditions =261 ControlConditions::collectControlConditions(BB1, *CommonDominator, DT,262 PDT);263 if (BB1Conditions == std::nullopt)264 return false;265 266 return BB0Conditions->isEquivalent(*BB1Conditions);267}268 269static bool reportInvalidCandidate(const Instruction &I,270 llvm::Statistic &Stat) {271 ++Stat;272 LLVM_DEBUG(dbgs() << "Unable to move instruction: " << I << ". "273 << Stat.getDesc());274 return false;275}276 277/// Collect all instructions in between \p StartInst and \p EndInst, and store278/// them in \p InBetweenInsts.279static void280collectInstructionsInBetween(Instruction &StartInst, const Instruction &EndInst,281 SmallPtrSetImpl<Instruction *> &InBetweenInsts) {282 assert(InBetweenInsts.empty() && "Expecting InBetweenInsts to be empty");283 284 /// Get the next instructions of \p I, and push them to \p WorkList.285 auto getNextInsts = [](Instruction &I,286 SmallPtrSetImpl<Instruction *> &WorkList) {287 if (Instruction *NextInst = I.getNextNode())288 WorkList.insert(NextInst);289 else {290 assert(I.isTerminator() && "Expecting a terminator instruction");291 for (BasicBlock *Succ : successors(&I))292 WorkList.insert(&Succ->front());293 }294 };295 296 SmallPtrSet<Instruction *, 10> WorkList;297 getNextInsts(StartInst, WorkList);298 while (!WorkList.empty()) {299 Instruction *CurInst = *WorkList.begin();300 WorkList.erase(CurInst);301 302 if (CurInst == &EndInst)303 continue;304 305 if (!InBetweenInsts.insert(CurInst).second)306 continue;307 308 getNextInsts(*CurInst, WorkList);309 }310}311 312bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,313 DominatorTree &DT, const PostDominatorTree *PDT,314 DependenceInfo *DI, bool CheckForEntireBlock) {315 // Skip tests when we don't have PDT or DI316 if (!PDT || !DI)317 return false;318 319 // Cannot move itself before itself.320 if (&I == &InsertPoint)321 return false;322 323 // Not moved.324 if (I.getNextNode() == &InsertPoint)325 return true;326 327 if (isa<PHINode>(I) || isa<PHINode>(InsertPoint))328 return reportInvalidCandidate(I, NotMovedPHINode);329 330 if (I.isTerminator())331 return reportInvalidCandidate(I, NotMovedTerminator);332 333 // TODO remove this limitation.334 if (!isControlFlowEquivalent(I, InsertPoint, DT, *PDT))335 return reportInvalidCandidate(I, NotControlFlowEquivalent);336 337 if (isReachedBefore(&I, &InsertPoint, &DT, PDT))338 for (const Use &U : I.uses())339 if (auto *UserInst = dyn_cast<Instruction>(U.getUser())) {340 // If InsertPoint is in a BB that comes after I, then we cannot move if341 // I is used in the terminator of the current BB.342 if (I.getParent() == InsertPoint.getParent() &&343 UserInst == I.getParent()->getTerminator())344 return false;345 if (UserInst != &InsertPoint && !DT.dominates(&InsertPoint, U)) {346 // If UserInst is an instruction that appears later in the same BB as347 // I, then it is okay to move since I will still be available when348 // UserInst is executed.349 if (CheckForEntireBlock && I.getParent() == UserInst->getParent() &&350 DT.dominates(&I, UserInst))351 continue;352 return false;353 }354 }355 if (isReachedBefore(&InsertPoint, &I, &DT, PDT))356 for (const Value *Op : I.operands())357 if (auto *OpInst = dyn_cast<Instruction>(Op)) {358 if (&InsertPoint == OpInst)359 return false;360 // If OpInst is an instruction that appears earlier in the same BB as361 // I, then it is okay to move since OpInst will still be available.362 if (CheckForEntireBlock && I.getParent() == OpInst->getParent() &&363 DT.dominates(OpInst, &I))364 continue;365 if (!DT.dominates(OpInst, &InsertPoint))366 return false;367 }368 369 DT.updateDFSNumbers();370 const bool MoveForward = domTreeLevelBefore(&DT, &I, &InsertPoint);371 Instruction &StartInst = (MoveForward ? I : InsertPoint);372 Instruction &EndInst = (MoveForward ? InsertPoint : I);373 SmallPtrSet<Instruction *, 10> InstsToCheck;374 collectInstructionsInBetween(StartInst, EndInst, InstsToCheck);375 if (!MoveForward)376 InstsToCheck.insert(&InsertPoint);377 378 // Check if there exists instructions which may throw, may synchonize, or may379 // never return, from I to InsertPoint.380 if (!isSafeToSpeculativelyExecute(&I))381 if (llvm::any_of(InstsToCheck, [](Instruction *I) {382 if (I->mayThrow())383 return true;384 385 const CallBase *CB = dyn_cast<CallBase>(I);386 if (!CB)387 return false;388 if (!CB->hasFnAttr(Attribute::WillReturn))389 return true;390 if (!CB->hasFnAttr(Attribute::NoSync))391 return true;392 393 return false;394 })) {395 return reportInvalidCandidate(I, MayThrowException);396 }397 398 // Check if I has any output/flow/anti dependences with instructions from \p399 // StartInst to \p EndInst.400 if (llvm::any_of(InstsToCheck, [&DI, &I](Instruction *CurInst) {401 auto DepResult = DI->depends(&I, CurInst);402 if (DepResult && (DepResult->isOutput() || DepResult->isFlow() ||403 DepResult->isAnti()))404 return true;405 return false;406 }))407 return reportInvalidCandidate(I, HasDependences);408 409 return true;410}411 412bool llvm::isSafeToMoveBefore(BasicBlock &BB, Instruction &InsertPoint,413 DominatorTree &DT, const PostDominatorTree *PDT,414 DependenceInfo *DI) {415 return llvm::all_of(BB, [&](Instruction &I) {416 if (BB.getTerminator() == &I)417 return true;418 419 return isSafeToMoveBefore(I, InsertPoint, DT, PDT, DI,420 /*CheckForEntireBlock=*/true);421 });422}423 424void llvm::moveInstructionsToTheBeginning(BasicBlock &FromBB, BasicBlock &ToBB,425 DominatorTree &DT,426 const PostDominatorTree &PDT,427 DependenceInfo &DI) {428 for (Instruction &I :429 llvm::make_early_inc_range(llvm::drop_begin(llvm::reverse(FromBB)))) {430 BasicBlock::iterator MovePos = ToBB.getFirstNonPHIOrDbg();431 432 if (isSafeToMoveBefore(I, *MovePos, DT, &PDT, &DI))433 I.moveBeforePreserving(MovePos);434 }435}436 437void llvm::moveInstructionsToTheEnd(BasicBlock &FromBB, BasicBlock &ToBB,438 DominatorTree &DT,439 const PostDominatorTree &PDT,440 DependenceInfo &DI) {441 Instruction *MovePos = ToBB.getTerminator();442 while (FromBB.size() > 1) {443 Instruction &I = FromBB.front();444 if (isSafeToMoveBefore(I, *MovePos, DT, &PDT, &DI))445 I.moveBeforePreserving(MovePos->getIterator());446 }447}448 449bool llvm::nonStrictlyPostDominate(const BasicBlock *ThisBlock,450 const BasicBlock *OtherBlock,451 const DominatorTree *DT,452 const PostDominatorTree *PDT) {453 assert(isControlFlowEquivalent(*ThisBlock, *OtherBlock, *DT, *PDT) &&454 "ThisBlock and OtherBlock must be CFG equivalent!");455 const BasicBlock *CommonDominator =456 DT->findNearestCommonDominator(ThisBlock, OtherBlock);457 if (CommonDominator == nullptr)458 return false;459 460 /// Recursively check the predecessors of \p ThisBlock up to461 /// their common dominator, and see if any of them post-dominates462 /// \p OtherBlock.463 SmallVector<const BasicBlock *, 8> WorkList;464 SmallPtrSet<const BasicBlock *, 8> Visited;465 WorkList.push_back(ThisBlock);466 while (!WorkList.empty()) {467 const BasicBlock *CurBlock = WorkList.pop_back_val();468 Visited.insert(CurBlock);469 if (PDT->dominates(CurBlock, OtherBlock))470 return true;471 472 for (const auto *Pred : predecessors(CurBlock)) {473 if (Pred == CommonDominator || Visited.count(Pred))474 continue;475 WorkList.push_back(Pred);476 }477 }478 return false;479}480 481bool llvm::isReachedBefore(const Instruction *I0, const Instruction *I1,482 const DominatorTree *DT,483 const PostDominatorTree *PDT) {484 const BasicBlock *BB0 = I0->getParent();485 const BasicBlock *BB1 = I1->getParent();486 if (BB0 == BB1)487 return DT->dominates(I0, I1);488 489 return nonStrictlyPostDominate(BB1, BB0, DT, PDT);490}491