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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This family of functions perform movements on basic blocks, and instructions 10 // 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 21 using namespace llvm; 22 23 #define DEBUG_TYPE "codemover-utils" 24 25 STATISTIC(HasDependences, 26 "Cannot move across instructions that has memory dependences"); 27 STATISTIC(MayThrowException, "Cannot move across instructions that may throw"); 28 STATISTIC(NotControlFlowEquivalent, 29 "Instructions are not control flow equivalent"); 30 STATISTIC(NotMovedPHINode, "Movement of PHINodes are not supported"); 31 STATISTIC(NotMovedTerminator, "Movement of Terminator are not supported"); 32 33 bool llvm::isControlFlowEquivalent(const Instruction &I0, const Instruction &I1, 34 const DominatorTree &DT, 35 const PostDominatorTree &PDT) { 36 return isControlFlowEquivalent(*I0.getParent(), *I1.getParent(), DT, PDT); 37 } 38 39 bool llvm::isControlFlowEquivalent(const BasicBlock &BB0, const BasicBlock &BB1, 40 const DominatorTree &DT, 41 const PostDominatorTree &PDT) { 42 if (&BB0 == &BB1) 43 return true; 44 45 return ((DT.dominates(&BB0, &BB1) && PDT.dominates(&BB1, &BB0)) || 46 (PDT.dominates(&BB0, &BB1) && DT.dominates(&BB1, &BB0))); 47 } 48 49 static bool reportInvalidCandidate(const Instruction &I, 50 llvm::Statistic &Stat) { 51 ++Stat; 52 LLVM_DEBUG(dbgs() << "Unable to move instruction: " << I << ". " 53 << Stat.getDesc()); 54 return false; 55 } 56 57 /// Collect all instructions in between \p StartInst and \p EndInst, and store 58 /// them in \p InBetweenInsts. 59 static void 60 collectInstructionsInBetween(Instruction &StartInst, const Instruction &EndInst, 61 SmallPtrSetImpl<Instruction *> &InBetweenInsts) { 62 assert(InBetweenInsts.empty() && "Expecting InBetweenInsts to be empty"); 63 64 /// Get the next instructions of \p I, and push them to \p WorkList. 65 auto getNextInsts = [](Instruction &I, 66 SmallPtrSetImpl<Instruction *> &WorkList) { 67 if (Instruction *NextInst = I.getNextNode()) 68 WorkList.insert(NextInst); 69 else { 70 assert(I.isTerminator() && "Expecting a terminator instruction"); 71 for (BasicBlock *Succ : successors(&I)) 72 WorkList.insert(&Succ->front()); 73 } 74 }; 75 76 SmallPtrSet<Instruction *, 10> WorkList; 77 getNextInsts(StartInst, WorkList); 78 while (!WorkList.empty()) { 79 Instruction *CurInst = *WorkList.begin(); 80 WorkList.erase(CurInst); 81 82 if (CurInst == &EndInst) 83 continue; 84 85 if (!InBetweenInsts.insert(CurInst).second) 86 continue; 87 88 getNextInsts(*CurInst, WorkList); 89 } 90 } 91 92 bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint, 93 const DominatorTree &DT, 94 const PostDominatorTree &PDT, 95 DependenceInfo &DI) { 96 // Cannot move itself before itself. 97 if (&I == &InsertPoint) 98 return false; 99 100 // Not moved. 101 if (I.getNextNode() == &InsertPoint) 102 return true; 103 104 if (isa<PHINode>(I) || isa<PHINode>(InsertPoint)) 105 return reportInvalidCandidate(I, NotMovedPHINode); 106 107 if (I.isTerminator()) 108 return reportInvalidCandidate(I, NotMovedTerminator); 109 110 // TODO remove this limitation. 111 if (!isControlFlowEquivalent(I, InsertPoint, DT, PDT)) 112 return reportInvalidCandidate(I, NotControlFlowEquivalent); 113 114 // As I and InsertPoint are control flow equivalent, if I dominates 115 // InsertPoint, then I comes before InsertPoint. 116 const bool MoveForward = DT.dominates(&I, &InsertPoint); 117 if (MoveForward) { 118 // When I is being moved forward, we need to make sure the InsertPoint 119 // dominates every users. Or else, a user may be using an undefined I. 120 for (const Use &U : I.uses()) 121 if (auto *UserInst = dyn_cast<Instruction>(U.getUser())) 122 if (UserInst != &InsertPoint && !DT.dominates(&InsertPoint, U)) 123 return false; 124 } else { 125 // When I is being moved backward, we need to make sure all its opernads 126 // dominates the InsertPoint. Or else, an operand may be undefined for I. 127 for (const Value *Op : I.operands()) 128 if (auto *OpInst = dyn_cast<Instruction>(Op)) 129 if (&InsertPoint == OpInst || !DT.dominates(OpInst, &InsertPoint)) 130 return false; 131 } 132 133 Instruction &StartInst = (MoveForward ? I : InsertPoint); 134 Instruction &EndInst = (MoveForward ? InsertPoint : I); 135 SmallPtrSet<Instruction *, 10> InstsToCheck; 136 collectInstructionsInBetween(StartInst, EndInst, InstsToCheck); 137 if (!MoveForward) 138 InstsToCheck.insert(&InsertPoint); 139 140 // Check if there exists instructions which may throw, may synchonize, or may 141 // never return, from I to InsertPoint. 142 if (!isSafeToSpeculativelyExecute(&I)) 143 if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(), 144 [](Instruction *I) { 145 if (I->mayThrow()) 146 return true; 147 148 const CallBase *CB = dyn_cast<CallBase>(I); 149 if (!CB) 150 return false; 151 if (!CB->hasFnAttr(Attribute::WillReturn)) 152 return true; 153 if (!CB->hasFnAttr(Attribute::NoSync)) 154 return true; 155 156 return false; 157 })) { 158 return reportInvalidCandidate(I, MayThrowException); 159 } 160 161 // Check if I has any output/flow/anti dependences with instructions from \p 162 // StartInst to \p EndInst. 163 if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(), 164 [&DI, &I](Instruction *CurInst) { 165 auto DepResult = DI.depends(&I, CurInst, true); 166 if (DepResult && 167 (DepResult->isOutput() || DepResult->isFlow() || 168 DepResult->isAnti())) 169 return true; 170 return false; 171 })) 172 return reportInvalidCandidate(I, HasDependences); 173 174 return true; 175 } 176 177 void llvm::moveInstsBottomUp(BasicBlock &FromBB, BasicBlock &ToBB, 178 const DominatorTree &DT, 179 const PostDominatorTree &PDT, DependenceInfo &DI) { 180 for (auto It = ++FromBB.rbegin(); It != FromBB.rend();) { 181 Instruction *MovePos = ToBB.getFirstNonPHIOrDbg(); 182 Instruction &I = *It; 183 // Increment the iterator before modifying FromBB. 184 ++It; 185 186 if (isSafeToMoveBefore(I, *MovePos, DT, PDT, DI)) 187 I.moveBefore(MovePos); 188 } 189 } 190