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 const BasicBlock *BB0 = I0.getParent(); 37 const BasicBlock *BB1 = I1.getParent(); 38 return ((DT.dominates(BB0, BB1) && PDT.dominates(BB1, BB0)) || 39 (PDT.dominates(BB0, BB1) && DT.dominates(BB1, BB0))); 40 } 41 42 static bool reportInvalidCandidate(const Instruction &I, 43 llvm::Statistic &Stat) { 44 ++Stat; 45 LLVM_DEBUG(dbgs() << "Unable to move instruction: " << I << ". " 46 << Stat.getDesc()); 47 return false; 48 } 49 50 /// Collect all instructions in between \p StartInst and \p EndInst, and store 51 /// them in \p InBetweenInsts. 52 static void 53 collectInstructionsInBetween(Instruction &StartInst, const Instruction &EndInst, 54 SmallPtrSetImpl<Instruction *> &InBetweenInsts) { 55 assert(InBetweenInsts.empty() && "Expecting InBetweenInsts to be empty"); 56 57 /// Get the next instructions of \p I, and push them to \p WorkList. 58 auto getNextInsts = [](Instruction &I, 59 SmallPtrSetImpl<Instruction *> &WorkList) { 60 if (Instruction *NextInst = I.getNextNode()) 61 WorkList.insert(NextInst); 62 else { 63 assert(I.isTerminator() && "Expecting a terminator instruction"); 64 for (BasicBlock *Succ : successors(&I)) 65 WorkList.insert(&Succ->front()); 66 } 67 }; 68 69 SmallPtrSet<Instruction *, 10> WorkList; 70 getNextInsts(StartInst, WorkList); 71 while (!WorkList.empty()) { 72 Instruction *CurInst = *WorkList.begin(); 73 WorkList.erase(CurInst); 74 75 if (CurInst == &EndInst) 76 continue; 77 78 if (!InBetweenInsts.insert(CurInst).second) 79 continue; 80 81 getNextInsts(*CurInst, WorkList); 82 } 83 } 84 85 bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint, 86 const DominatorTree &DT, 87 const PostDominatorTree &PDT, 88 DependenceInfo &DI) { 89 // Cannot move itself before itself. 90 if (&I == &InsertPoint) 91 return false; 92 93 // Not moved. 94 if (I.getNextNode() == &InsertPoint) 95 return true; 96 97 if (isa<PHINode>(I) || isa<PHINode>(InsertPoint)) 98 return reportInvalidCandidate(I, NotMovedPHINode); 99 100 if (I.isTerminator()) 101 return reportInvalidCandidate(I, NotMovedTerminator); 102 103 // TODO remove this limitation. 104 if (!isControlFlowEquivalent(I, InsertPoint, DT, PDT)) 105 return reportInvalidCandidate(I, NotControlFlowEquivalent); 106 107 // As I and InsertPoint are control flow equivalent, if I dominates 108 // InsertPoint, then I comes before InsertPoint. 109 const bool MoveForward = DT.dominates(&I, &InsertPoint); 110 if (MoveForward) { 111 // When I is being moved forward, we need to make sure the InsertPoint 112 // dominates every users. Or else, a user may be using an undefined I. 113 for (const Value *User : I.users()) 114 if (auto *UserInst = dyn_cast<Instruction>(User)) 115 if (!DT.dominates(&InsertPoint, UserInst)) 116 return false; 117 } else { 118 // When I is being moved backward, we need to make sure all its opernads 119 // dominates the InsertPoint. Or else, an operand may be undefined for I. 120 for (const Value *Op : I.operands()) 121 if (auto *OpInst = dyn_cast<Instruction>(Op)) 122 if (&InsertPoint == OpInst || !DT.dominates(OpInst, &InsertPoint)) 123 return false; 124 } 125 126 Instruction &StartInst = (MoveForward ? I : InsertPoint); 127 Instruction &EndInst = (MoveForward ? InsertPoint : I); 128 SmallPtrSet<Instruction *, 10> InstsToCheck; 129 collectInstructionsInBetween(StartInst, EndInst, InstsToCheck); 130 if (!MoveForward) 131 InstsToCheck.insert(&InsertPoint); 132 133 // Check if there exists instructions which may throw, may synchonize, or may 134 // never return, from I to InsertPoint. 135 if (!isSafeToSpeculativelyExecute(&I)) 136 if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(), 137 [](Instruction *I) { 138 if (I->mayThrow()) 139 return true; 140 141 const CallBase *CB = dyn_cast<CallBase>(I); 142 if (!CB) 143 return false; 144 if (!CB->hasFnAttr(Attribute::WillReturn)) 145 return true; 146 if (!CB->hasFnAttr(Attribute::NoSync)) 147 return true; 148 149 return false; 150 })) { 151 return reportInvalidCandidate(I, MayThrowException); 152 } 153 154 // Check if I has any output/flow/anti dependences with instructions from \p 155 // StartInst to \p EndInst. 156 if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(), 157 [&DI, &I](Instruction *CurInst) { 158 auto DepResult = DI.depends(&I, CurInst, true); 159 if (DepResult && 160 (DepResult->isOutput() || DepResult->isFlow() || 161 DepResult->isAnti())) 162 return true; 163 return false; 164 })) 165 return reportInvalidCandidate(I, HasDependences); 166 167 return true; 168 } 169