364 lines · cpp
1//===- SpeculativeExecution.cpp ---------------------------------*- C++ -*-===//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 pass hoists instructions to enable speculative execution on10// targets where branches are expensive. This is aimed at GPUs. It11// currently works on simple if-then and if-then-else12// patterns.13//14// Removing branches is not the only motivation for this15// pass. E.g. consider this code and assume that there is no16// addressing mode for multiplying by sizeof(*a):17//18// if (b > 0)19// c = a[i + 1]20// if (d > 0)21// e = a[i + 2]22//23// turns into24//25// p = &a[i + 1];26// if (b > 0)27// c = *p;28// q = &a[i + 2];29// if (d > 0)30// e = *q;31//32// which could later be optimized to33//34// r = &a[i];35// if (b > 0)36// c = r[1];37// if (d > 0)38// e = r[2];39//40// Later passes sink back much of the speculated code that did not enable41// further optimization.42//43// This pass is more aggressive than the function SpeculativeyExecuteBB in44// SimplifyCFG. SimplifyCFG will not speculate if no selects are introduced and45// it will speculate at most one instruction. It also will not speculate if46// there is a value defined in the if-block that is only used in the then-block.47// These restrictions make sense since the speculation in SimplifyCFG seems48// aimed at introducing cheap selects, while this pass is intended to do more49// aggressive speculation while counting on later passes to either capitalize on50// that or clean it up.51//52// If the pass was created by calling53// createSpeculativeExecutionIfHasBranchDivergencePass or the54// -spec-exec-only-if-divergent-target option is present, this pass only has an55// effect on targets where TargetTransformInfo::hasBranchDivergence() is true;56// on other targets, it is a nop.57//58// This lets you include this pass unconditionally in the IR pass pipeline, but59// only enable it for relevant targets.60//61//===----------------------------------------------------------------------===//62 63#include "llvm/Transforms/Scalar/SpeculativeExecution.h"64#include "llvm/ADT/SmallPtrSet.h"65#include "llvm/Analysis/GlobalsModRef.h"66#include "llvm/Analysis/TargetTransformInfo.h"67#include "llvm/Analysis/ValueTracking.h"68#include "llvm/IR/Instructions.h"69#include "llvm/IR/Operator.h"70#include "llvm/InitializePasses.h"71#include "llvm/Support/CommandLine.h"72#include "llvm/Support/Debug.h"73#include "llvm/Transforms/Scalar.h"74 75using namespace llvm;76 77#define DEBUG_TYPE "speculative-execution"78 79// The risk that speculation will not pay off increases with the80// number of instructions speculated, so we put a limit on that.81static cl::opt<unsigned> SpecExecMaxSpeculationCost(82 "spec-exec-max-speculation-cost", cl::init(7), cl::Hidden,83 cl::desc("Speculative execution is not applied to basic blocks where "84 "the cost of the instructions to speculatively execute "85 "exceeds this limit."));86 87// Speculating just a few instructions from a larger block tends not88// to be profitable and this limit prevents that. A reason for that is89// that small basic blocks are more likely to be candidates for90// further optimization.91static cl::opt<unsigned> SpecExecMaxNotHoisted(92 "spec-exec-max-not-hoisted", cl::init(5), cl::Hidden,93 cl::desc("Speculative execution is not applied to basic blocks where the "94 "number of instructions that would not be speculatively executed "95 "exceeds this limit."));96 97static cl::opt<bool> SpecExecOnlyIfDivergentTarget(98 "spec-exec-only-if-divergent-target", cl::init(false), cl::Hidden,99 cl::desc("Speculative execution is applied only to targets with divergent "100 "branches, even if the pass was configured to apply only to all "101 "targets."));102 103namespace {104 105class SpeculativeExecutionLegacyPass : public FunctionPass {106public:107 static char ID;108 explicit SpeculativeExecutionLegacyPass(bool OnlyIfDivergentTarget = false)109 : FunctionPass(ID), OnlyIfDivergentTarget(OnlyIfDivergentTarget ||110 SpecExecOnlyIfDivergentTarget),111 Impl(OnlyIfDivergentTarget) {}112 113 void getAnalysisUsage(AnalysisUsage &AU) const override;114 bool runOnFunction(Function &F) override;115 116 StringRef getPassName() const override {117 if (OnlyIfDivergentTarget)118 return "Speculatively execute instructions if target has divergent "119 "branches";120 return "Speculatively execute instructions";121 }122 123private:124 // Variable preserved purely for correct name printing.125 const bool OnlyIfDivergentTarget;126 127 SpeculativeExecutionPass Impl;128};129} // namespace130 131char SpeculativeExecutionLegacyPass::ID = 0;132INITIALIZE_PASS_BEGIN(SpeculativeExecutionLegacyPass, "speculative-execution",133 "Speculatively execute instructions", false, false)134INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)135INITIALIZE_PASS_END(SpeculativeExecutionLegacyPass, "speculative-execution",136 "Speculatively execute instructions", false, false)137 138void SpeculativeExecutionLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const {139 AU.addRequired<TargetTransformInfoWrapperPass>();140 AU.addPreserved<GlobalsAAWrapperPass>();141 AU.setPreservesCFG();142}143 144bool SpeculativeExecutionLegacyPass::runOnFunction(Function &F) {145 if (skipFunction(F))146 return false;147 148 auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);149 return Impl.runImpl(F, TTI);150}151 152bool SpeculativeExecutionPass::runImpl(Function &F, TargetTransformInfo *TTI) {153 if (OnlyIfDivergentTarget && !TTI->hasBranchDivergence(&F)) {154 LLVM_DEBUG(dbgs() << "Not running SpeculativeExecution because "155 "TTI->hasBranchDivergence() is false.\n");156 return false;157 }158 159 this->TTI = TTI;160 bool Changed = false;161 for (auto& B : F) {162 Changed |= runOnBasicBlock(B);163 }164 return Changed;165}166 167bool SpeculativeExecutionPass::runOnBasicBlock(BasicBlock &B) {168 BranchInst *BI = dyn_cast<BranchInst>(B.getTerminator());169 if (BI == nullptr)170 return false;171 172 if (BI->getNumSuccessors() != 2)173 return false;174 BasicBlock &Succ0 = *BI->getSuccessor(0);175 BasicBlock &Succ1 = *BI->getSuccessor(1);176 177 if (&B == &Succ0 || &B == &Succ1 || &Succ0 == &Succ1) {178 return false;179 }180 181 // Hoist from if-then (triangle).182 if (Succ0.getSinglePredecessor() != nullptr &&183 Succ0.getSingleSuccessor() == &Succ1) {184 return considerHoistingFromTo(Succ0, B);185 }186 187 // Hoist from if-else (triangle).188 if (Succ1.getSinglePredecessor() != nullptr &&189 Succ1.getSingleSuccessor() == &Succ0) {190 return considerHoistingFromTo(Succ1, B);191 }192 193 // Hoist from if-then-else (diamond), but only if it is equivalent to194 // an if-else or if-then due to one of the branches doing nothing.195 if (Succ0.getSinglePredecessor() != nullptr &&196 Succ1.getSinglePredecessor() != nullptr &&197 Succ1.getSingleSuccessor() != nullptr &&198 Succ1.getSingleSuccessor() != &B &&199 Succ1.getSingleSuccessor() == Succ0.getSingleSuccessor()) {200 // If a block has only one instruction, then that is a terminator201 // instruction so that the block does nothing. This does happen.202 if (Succ1.size() == 1) // equivalent to if-then203 return considerHoistingFromTo(Succ0, B);204 if (Succ0.size() == 1) // equivalent to if-else205 return considerHoistingFromTo(Succ1, B);206 }207 208 return false;209}210 211static InstructionCost ComputeSpeculationCost(const Instruction *I,212 const TargetTransformInfo &TTI) {213 switch (Operator::getOpcode(I)) {214 case Instruction::GetElementPtr:215 case Instruction::Add:216 case Instruction::Mul:217 case Instruction::And:218 case Instruction::Or:219 case Instruction::Select:220 case Instruction::Shl:221 case Instruction::Sub:222 case Instruction::LShr:223 case Instruction::AShr:224 case Instruction::Xor:225 case Instruction::ZExt:226 case Instruction::SExt:227 case Instruction::Call:228 case Instruction::BitCast:229 case Instruction::PtrToInt:230 case Instruction::PtrToAddr:231 case Instruction::IntToPtr:232 case Instruction::AddrSpaceCast:233 case Instruction::FPToUI:234 case Instruction::FPToSI:235 case Instruction::UIToFP:236 case Instruction::SIToFP:237 case Instruction::FPExt:238 case Instruction::FPTrunc:239 case Instruction::FAdd:240 case Instruction::FSub:241 case Instruction::FMul:242 case Instruction::FDiv:243 case Instruction::FRem:244 case Instruction::FNeg:245 case Instruction::ICmp:246 case Instruction::FCmp:247 case Instruction::Trunc:248 case Instruction::Freeze:249 case Instruction::ExtractElement:250 case Instruction::InsertElement:251 case Instruction::ShuffleVector:252 case Instruction::ExtractValue:253 case Instruction::InsertValue:254 return TTI.getInstructionCost(I, TargetTransformInfo::TCK_SizeAndLatency);255 256 default:257 return InstructionCost::getInvalid(); // Disallow anything not explicitly258 // listed.259 }260}261 262// Do not hoist any debug info intrinsics.263// ...264// if (cond) {265// x = y * z;266// foo();267// }268// ...269// -------- Which then becomes:270// ...271// if.then:272// %x = mul i32 %y, %z273// call void @llvm.dbg.value(%x, !"x", !DIExpression())274// call void foo()275//276// SpeculativeExecution might decide to hoist the 'y * z' calculation277// out of the 'if' block, because it is more efficient that way, so the278// '%x = mul i32 %y, %z' moves to the block above. But it might also279// decide to hoist the 'llvm.dbg.value' call.280// This is incorrect, because even if we've moved the calculation of281// 'y * z', we should not see the value of 'x' change unless we282// actually go inside the 'if' block.283 284bool SpeculativeExecutionPass::considerHoistingFromTo(285 BasicBlock &FromBlock, BasicBlock &ToBlock) {286 SmallPtrSet<const Instruction *, 8> NotHoisted;287 auto HasNoUnhoistedInstr = [&NotHoisted](auto Values) {288 for (const Value *V : Values) {289 if (const auto *I = dyn_cast_or_null<Instruction>(V))290 if (NotHoisted.contains(I))291 return false;292 }293 return true;294 };295 auto AllPrecedingUsesFromBlockHoisted =296 [&HasNoUnhoistedInstr](const User *U) {297 return HasNoUnhoistedInstr(U->operand_values());298 };299 300 InstructionCost TotalSpeculationCost = 0;301 unsigned NotHoistedInstCount = 0;302 for (const auto &I : FromBlock) {303 const InstructionCost Cost = ComputeSpeculationCost(&I, *TTI);304 if (Cost.isValid() && isSafeToSpeculativelyExecute(&I) &&305 AllPrecedingUsesFromBlockHoisted(&I)) {306 TotalSpeculationCost += Cost;307 if (TotalSpeculationCost > SpecExecMaxSpeculationCost)308 return false; // too much to hoist309 } else {310 NotHoistedInstCount++;311 if (NotHoistedInstCount > SpecExecMaxNotHoisted)312 return false; // too much left behind313 NotHoisted.insert(&I);314 }315 }316 317 for (auto I = FromBlock.begin(); I != FromBlock.end();) {318 // We have to increment I before moving Current as moving Current319 // changes the list that I is iterating through.320 auto Current = I;321 ++I;322 if (!NotHoisted.count(&*Current)) {323 Current->moveBefore(ToBlock.getTerminator()->getIterator());324 Current->dropLocation();325 }326 }327 return true;328}329 330FunctionPass *llvm::createSpeculativeExecutionPass() {331 return new SpeculativeExecutionLegacyPass();332}333 334FunctionPass *llvm::createSpeculativeExecutionIfHasBranchDivergencePass() {335 return new SpeculativeExecutionLegacyPass(/* OnlyIfDivergentTarget = */ true);336}337 338SpeculativeExecutionPass::SpeculativeExecutionPass(bool OnlyIfDivergentTarget)339 : OnlyIfDivergentTarget(OnlyIfDivergentTarget ||340 SpecExecOnlyIfDivergentTarget) {}341 342PreservedAnalyses SpeculativeExecutionPass::run(Function &F,343 FunctionAnalysisManager &AM) {344 auto *TTI = &AM.getResult<TargetIRAnalysis>(F);345 346 bool Changed = runImpl(F, TTI);347 348 if (!Changed)349 return PreservedAnalyses::all();350 PreservedAnalyses PA;351 PA.preserveSet<CFGAnalyses>();352 return PA;353}354 355void SpeculativeExecutionPass::printPipeline(356 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {357 static_cast<PassInfoMixin<SpeculativeExecutionPass> *>(this)->printPipeline(358 OS, MapClassName2PassName);359 OS << '<';360 if (OnlyIfDivergentTarget)361 OS << "only-if-divergent-target";362 OS << '>';363}364