SpeculativeExecution.cpp revision 296417
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 64using 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. 70static 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. 80static 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 86namespace { 87class 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 103char SpeculativeExecution::ID = 0; 104INITIALIZE_PASS_BEGIN(SpeculativeExecution, "speculative-execution", 105 "Speculatively execute instructions", false, false) 106INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 107INITIALIZE_PASS_END(SpeculativeExecution, "speculative-execution", 108 "Speculatively execute instructions", false, false) 109 110void SpeculativeExecution::getAnalysisUsage(AnalysisUsage &AU) const { 111 AU.addRequired<TargetTransformInfoWrapperPass>(); 112} 113 114bool 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 127bool 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 171static 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 194bool 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 237namespace llvm { 238 239FunctionPass *createSpeculativeExecutionPass() { 240 return new SpeculativeExecution(); 241} 242 243} // namespace llvm 244