1 //===- SpeculativeExecution.cpp ---------------------------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This pass hoists instructions to enable speculative execution on 11 // targets where branches are expensive. This is aimed at GPUs. It 12 // currently works on simple if-then and if-then-else 13 // patterns. 14 // 15 // Removing branches is not the only motivation for this 16 // pass. E.g. consider this code and assume that there is no 17 // addressing mode for multiplying by sizeof(*a): 18 // 19 // if (b > 0) 20 // c = a[i + 1] 21 // if (d > 0) 22 // e = a[i + 2] 23 // 24 // turns into 25 // 26 // p = &a[i + 1]; 27 // if (b > 0) 28 // c = *p; 29 // q = &a[i + 2]; 30 // if (d > 0) 31 // e = *q; 32 // 33 // which could later be optimized to 34 // 35 // r = &a[i]; 36 // if (b > 0) 37 // c = r[1]; 38 // if (d > 0) 39 // e = r[2]; 40 // 41 // Later passes sink back much of the speculated code that did not enable 42 // further optimization. 43 // 44 // This pass is more aggressive than the function SpeculativeyExecuteBB in 45 // SimplifyCFG. SimplifyCFG will not speculate if no selects are introduced and 46 // it will speculate at most one instruction. It also will not speculate if 47 // there is a value defined in the if-block that is only used in the then-block. 48 // These restrictions make sense since the speculation in SimplifyCFG seems 49 // aimed at introducing cheap selects, while this pass is intended to do more 50 // aggressive speculation while counting on later passes to either capitalize on 51 // that or clean it up. 52 // 53 //===----------------------------------------------------------------------===// 54 55 #include "llvm/ADT/SmallSet.h" 56 #include "llvm/Analysis/TargetTransformInfo.h" 57 #include "llvm/Analysis/ValueTracking.h" 58 #include "llvm/IR/Instructions.h" 59 #include "llvm/IR/Module.h" 60 #include "llvm/IR/Operator.h" 61 #include "llvm/Support/CommandLine.h" 62 #include "llvm/Support/Debug.h" 63 64 using namespace llvm; 65 66 #define DEBUG_TYPE "speculative-execution" 67 68 // The risk that speculation will not pay off increases with the 69 // number of instructions speculated, so we put a limit on that. 70 static cl::opt<unsigned> SpecExecMaxSpeculationCost( 71 "spec-exec-max-speculation-cost", cl::init(7), cl::Hidden, 72 cl::desc("Speculative execution is not applied to basic blocks where " 73 "the cost of the instructions to speculatively execute " 74 "exceeds this limit.")); 75 76 // Speculating just a few instructions from a larger block tends not 77 // to be profitable and this limit prevents that. A reason for that is 78 // that small basic blocks are more likely to be candidates for 79 // further optimization. 80 static cl::opt<unsigned> SpecExecMaxNotHoisted( 81 "spec-exec-max-not-hoisted", cl::init(5), cl::Hidden, 82 cl::desc("Speculative execution is not applied to basic blocks where the " 83 "number of instructions that would not be speculatively executed " 84 "exceeds this limit.")); 85 86 namespace { 87 class SpeculativeExecution : public FunctionPass { 88 public: 89 static char ID; 90 SpeculativeExecution(): FunctionPass(ID) {} 91 92 void getAnalysisUsage(AnalysisUsage &AU) const override; 93 bool runOnFunction(Function &F) override; 94 95 private: 96 bool runOnBasicBlock(BasicBlock &B); 97 bool considerHoistingFromTo(BasicBlock &FromBlock, BasicBlock &ToBlock); 98 99 const TargetTransformInfo *TTI = nullptr; 100 }; 101 } // namespace 102 103 char SpeculativeExecution::ID = 0; 104 INITIALIZE_PASS_BEGIN(SpeculativeExecution, "speculative-execution", 105 "Speculatively execute instructions", false, false) 106 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 107 INITIALIZE_PASS_END(SpeculativeExecution, "speculative-execution", 108 "Speculatively execute instructions", false, false) 109 110 void SpeculativeExecution::getAnalysisUsage(AnalysisUsage &AU) const { 111 AU.addRequired<TargetTransformInfoWrapperPass>(); 112 } 113 114 bool SpeculativeExecution::runOnFunction(Function &F) { 115 if (skipOptnoneFunction(F)) 116 return false; 117 118 TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 119 120 bool Changed = false; 121 for (auto& B : F) { 122 Changed |= runOnBasicBlock(B); 123 } 124 return Changed; 125 } 126 127 bool SpeculativeExecution::runOnBasicBlock(BasicBlock &B) { 128 BranchInst *BI = dyn_cast<BranchInst>(B.getTerminator()); 129 if (BI == nullptr) 130 return false; 131 132 if (BI->getNumSuccessors() != 2) 133 return false; 134 BasicBlock &Succ0 = *BI->getSuccessor(0); 135 BasicBlock &Succ1 = *BI->getSuccessor(1); 136 137 if (&B == &Succ0 || &B == &Succ1 || &Succ0 == &Succ1) { 138 return false; 139 } 140 141 // Hoist from if-then (triangle). 142 if (Succ0.getSinglePredecessor() != nullptr && 143 Succ0.getSingleSuccessor() == &Succ1) { 144 return considerHoistingFromTo(Succ0, B); 145 } 146 147 // Hoist from if-else (triangle). 148 if (Succ1.getSinglePredecessor() != nullptr && 149 Succ1.getSingleSuccessor() == &Succ0) { 150 return considerHoistingFromTo(Succ1, B); 151 } 152 153 // Hoist from if-then-else (diamond), but only if it is equivalent to 154 // an if-else or if-then due to one of the branches doing nothing. 155 if (Succ0.getSinglePredecessor() != nullptr && 156 Succ1.getSinglePredecessor() != nullptr && 157 Succ1.getSingleSuccessor() != nullptr && 158 Succ1.getSingleSuccessor() != &B && 159 Succ1.getSingleSuccessor() == Succ0.getSingleSuccessor()) { 160 // If a block has only one instruction, then that is a terminator 161 // instruction so that the block does nothing. This does happen. 162 if (Succ1.size() == 1) // equivalent to if-then 163 return considerHoistingFromTo(Succ0, B); 164 if (Succ0.size() == 1) // equivalent to if-else 165 return considerHoistingFromTo(Succ1, B); 166 } 167 168 return false; 169 } 170 171 static unsigned ComputeSpeculationCost(const Instruction *I, 172 const TargetTransformInfo &TTI) { 173 switch (Operator::getOpcode(I)) { 174 case Instruction::GetElementPtr: 175 case Instruction::Add: 176 case Instruction::Mul: 177 case Instruction::And: 178 case Instruction::Or: 179 case Instruction::Select: 180 case Instruction::Shl: 181 case Instruction::Sub: 182 case Instruction::LShr: 183 case Instruction::AShr: 184 case Instruction::Xor: 185 case Instruction::ZExt: 186 case Instruction::SExt: 187 return TTI.getUserCost(I); 188 189 default: 190 return UINT_MAX; // Disallow anything not whitelisted. 191 } 192 } 193 194 bool SpeculativeExecution::considerHoistingFromTo(BasicBlock &FromBlock, 195 BasicBlock &ToBlock) { 196 SmallSet<const Instruction *, 8> NotHoisted; 197 const auto AllPrecedingUsesFromBlockHoisted = [&NotHoisted](User *U) { 198 for (Value* V : U->operand_values()) { 199 if (Instruction *I = dyn_cast<Instruction>(V)) { 200 if (NotHoisted.count(I) > 0) 201 return false; 202 } 203 } 204 return true; 205 }; 206 207 unsigned TotalSpeculationCost = 0; 208 for (auto& I : FromBlock) { 209 const unsigned Cost = ComputeSpeculationCost(&I, *TTI); 210 if (Cost != UINT_MAX && isSafeToSpeculativelyExecute(&I) && 211 AllPrecedingUsesFromBlockHoisted(&I)) { 212 TotalSpeculationCost += Cost; 213 if (TotalSpeculationCost > SpecExecMaxSpeculationCost) 214 return false; // too much to hoist 215 } else { 216 NotHoisted.insert(&I); 217 if (NotHoisted.size() > SpecExecMaxNotHoisted) 218 return false; // too much left behind 219 } 220 } 221 222 if (TotalSpeculationCost == 0) 223 return false; // nothing to hoist 224 225 for (auto I = FromBlock.begin(); I != FromBlock.end();) { 226 // We have to increment I before moving Current as moving Current 227 // changes the list that I is iterating through. 228 auto Current = I; 229 ++I; 230 if (!NotHoisted.count(&*Current)) { 231 Current->moveBefore(ToBlock.getTerminator()); 232 } 233 } 234 return true; 235 } 236 237 namespace llvm { 238 239 FunctionPass *createSpeculativeExecutionPass() { 240 return new SpeculativeExecution(); 241 } 242 243 } // namespace llvm 244
