LLVM 19.0.0git
SpeculativeExecution.cpp
Go to the documentation of this file.
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-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass hoists instructions to enable speculative execution on
10// targets where branches are expensive. This is aimed at GPUs. It
11// currently works on simple if-then and if-then-else
12// patterns.
13//
14// Removing branches is not the only motivation for this
15// pass. E.g. consider this code and assume that there is no
16// 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 into
24//
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 to
33//
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 enable
41// further optimization.
42//
43// This pass is more aggressive than the function SpeculativeyExecuteBB in
44// SimplifyCFG. SimplifyCFG will not speculate if no selects are introduced and
45// it will speculate at most one instruction. It also will not speculate if
46// 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 seems
48// aimed at introducing cheap selects, while this pass is intended to do more
49// aggressive speculation while counting on later passes to either capitalize on
50// that or clean it up.
51//
52// If the pass was created by calling
53// createSpeculativeExecutionIfHasBranchDivergencePass or the
54// -spec-exec-only-if-divergent-target option is present, this pass only has an
55// 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, but
59// only enable it for relevant targets.
60//
61//===----------------------------------------------------------------------===//
62
70#include "llvm/IR/Operator.h"
73#include "llvm/Support/Debug.h"
74
75using namespace llvm;
76
77#define DEBUG_TYPE "speculative-execution"
78
79// The risk that speculation will not pay off increases with the
80// number of instructions speculated, so we put a limit on that.
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 not
88// to be profitable and this limit prevents that. A reason for that is
89// that small basic blocks are more likely to be candidates for
90// further optimization.
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
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 ||
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
128};
129} // namespace
130
131char SpeculativeExecutionLegacyPass::ID = 0;
132INITIALIZE_PASS_BEGIN(SpeculativeExecutionLegacyPass, "speculative-execution",
133 "Speculatively execute instructions", false, false)
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
152namespace llvm {
153
155 if (OnlyIfDivergentTarget && !TTI->hasBranchDivergence(&F)) {
156 LLVM_DEBUG(dbgs() << "Not running SpeculativeExecution because "
157 "TTI->hasBranchDivergence() is false.\n");
158 return false;
159 }
160
161 this->TTI = TTI;
162 bool Changed = false;
163 for (auto& B : F) {
164 Changed |= runOnBasicBlock(B);
165 }
166 return Changed;
167}
168
169bool SpeculativeExecutionPass::runOnBasicBlock(BasicBlock &B) {
170 BranchInst *BI = dyn_cast<BranchInst>(B.getTerminator());
171 if (BI == nullptr)
172 return false;
173
174 if (BI->getNumSuccessors() != 2)
175 return false;
176 BasicBlock &Succ0 = *BI->getSuccessor(0);
177 BasicBlock &Succ1 = *BI->getSuccessor(1);
178
179 if (&B == &Succ0 || &B == &Succ1 || &Succ0 == &Succ1) {
180 return false;
181 }
182
183 // Hoist from if-then (triangle).
184 if (Succ0.getSinglePredecessor() != nullptr &&
185 Succ0.getSingleSuccessor() == &Succ1) {
186 return considerHoistingFromTo(Succ0, B);
187 }
188
189 // Hoist from if-else (triangle).
190 if (Succ1.getSinglePredecessor() != nullptr &&
191 Succ1.getSingleSuccessor() == &Succ0) {
192 return considerHoistingFromTo(Succ1, B);
193 }
194
195 // Hoist from if-then-else (diamond), but only if it is equivalent to
196 // an if-else or if-then due to one of the branches doing nothing.
197 if (Succ0.getSinglePredecessor() != nullptr &&
198 Succ1.getSinglePredecessor() != nullptr &&
199 Succ1.getSingleSuccessor() != nullptr &&
200 Succ1.getSingleSuccessor() != &B &&
201 Succ1.getSingleSuccessor() == Succ0.getSingleSuccessor()) {
202 // If a block has only one instruction, then that is a terminator
203 // instruction so that the block does nothing. This does happen.
204 if (Succ1.size() == 1) // equivalent to if-then
205 return considerHoistingFromTo(Succ0, B);
206 if (Succ0.size() == 1) // equivalent to if-else
207 return considerHoistingFromTo(Succ1, B);
208 }
209
210 return false;
211}
212
214 const TargetTransformInfo &TTI) {
215 switch (Operator::getOpcode(I)) {
216 case Instruction::GetElementPtr:
217 case Instruction::Add:
218 case Instruction::Mul:
219 case Instruction::And:
220 case Instruction::Or:
221 case Instruction::Select:
222 case Instruction::Shl:
223 case Instruction::Sub:
224 case Instruction::LShr:
225 case Instruction::AShr:
226 case Instruction::Xor:
227 case Instruction::ZExt:
228 case Instruction::SExt:
229 case Instruction::Call:
230 case Instruction::BitCast:
231 case Instruction::PtrToInt:
232 case Instruction::IntToPtr:
233 case Instruction::AddrSpaceCast:
234 case Instruction::FPToUI:
235 case Instruction::FPToSI:
236 case Instruction::UIToFP:
237 case Instruction::SIToFP:
238 case Instruction::FPExt:
239 case Instruction::FPTrunc:
240 case Instruction::FAdd:
241 case Instruction::FSub:
242 case Instruction::FMul:
243 case Instruction::FDiv:
244 case Instruction::FRem:
245 case Instruction::FNeg:
246 case Instruction::ICmp:
247 case Instruction::FCmp:
248 case Instruction::Trunc:
249 case Instruction::Freeze:
250 case Instruction::ExtractElement:
251 case Instruction::InsertElement:
252 case Instruction::ShuffleVector:
253 case Instruction::ExtractValue:
254 case Instruction::InsertValue:
256
257 default:
258 return InstructionCost::getInvalid(); // Disallow anything not explicitly
259 // listed.
260 }
261}
262
263bool SpeculativeExecutionPass::considerHoistingFromTo(
264 BasicBlock &FromBlock, BasicBlock &ToBlock) {
267 auto HasNoUnhoistedInstr = [&NotHoisted](auto Values) {
268 for (const Value *V : Values) {
269 if (const auto *I = dyn_cast_or_null<Instruction>(V))
270 if (NotHoisted.contains(I))
271 return false;
272 }
273 return true;
274 };
275 auto AllPrecedingUsesFromBlockHoisted =
276 [&HasNoUnhoistedInstr](const User *U) {
277 // Debug variable has special operand to check it's not hoisted.
278 if (const auto *DVI = dyn_cast<DbgVariableIntrinsic>(U))
279 return HasNoUnhoistedInstr(DVI->location_ops());
280
281 // Usially debug label intrinsic corresponds to label in LLVM IR. In
282 // these cases we should not move it here.
283 // TODO: Possible special processing needed to detect it is related to a
284 // hoisted instruction.
285 if (isa<DbgLabelInst>(U))
286 return false;
287
288 return HasNoUnhoistedInstr(U->operand_values());
289 };
290
291 InstructionCost TotalSpeculationCost = 0;
292 unsigned NotHoistedInstCount = 0;
293 for (const auto &I : FromBlock) {
294 // Make note of any DPValues that need hoisting. DPLabels
295 // get left behind just like llvm.dbg.labels.
296 for (DPValue &DPV : filterDbgVars(I.getDbgRecordRange())) {
297 if (HasNoUnhoistedInstr(DPV.location_ops()))
298 DPValuesToHoist[DPV.getInstruction()].push_back(&DPV);
299 }
302 AllPrecedingUsesFromBlockHoisted(&I)) {
303 TotalSpeculationCost += Cost;
304 if (TotalSpeculationCost > SpecExecMaxSpeculationCost)
305 return false; // too much to hoist
306 } else {
307 // Debug info intrinsics should not be counted for threshold.
308 if (!isa<DbgInfoIntrinsic>(I))
309 NotHoistedInstCount++;
310 if (NotHoistedInstCount > SpecExecMaxNotHoisted)
311 return false; // too much left behind
312 NotHoisted.insert(&I);
313 }
314 }
315
316 for (auto I = FromBlock.begin(); I != FromBlock.end();) {
317 // If any DPValues attached to this instruction should be hoisted, hoist
318 // them now - they will end up attached to either the next hoisted
319 // instruction or the ToBlock terminator.
320 if (DPValuesToHoist.contains(&*I)) {
321 for (auto *DPV : DPValuesToHoist[&*I]) {
322 DPV->removeFromParent();
323 ToBlock.insertDbgRecordBefore(DPV,
324 ToBlock.getTerminator()->getIterator());
325 }
326 }
327 // We have to increment I before moving Current as moving Current
328 // changes the list that I is iterating through.
329 auto Current = I;
330 ++I;
331 if (!NotHoisted.count(&*Current)) {
332 Current->moveBefore(ToBlock.getTerminator());
333 }
334 }
335 return true;
336}
337
339 return new SpeculativeExecutionLegacyPass();
340}
341
343 return new SpeculativeExecutionLegacyPass(/* OnlyIfDivergentTarget = */ true);
344}
345
347 : OnlyIfDivergentTarget(OnlyIfDivergentTarget ||
349
352 auto *TTI = &AM.getResult<TargetIRAnalysis>(F);
353
354 bool Changed = runImpl(F, TTI);
355
356 if (!Changed)
357 return PreservedAnalyses::all();
360 return PA;
361}
362
364 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
366 OS, MapClassName2PassName);
367 OS << '<';
368 if (OnlyIfDivergentTarget)
369 OS << "only-if-divergent-target";
370 OS << '>';
371}
372} // namespace llvm
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This is the interface for a simple mod/ref and alias analysis over globals.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
raw_pwrite_stream & OS
This file defines the SmallPtrSet class.
static cl::opt< unsigned > SpecExecMaxNotHoisted("spec-exec-max-not-hoisted", cl::init(5), cl::Hidden, cl::desc("Speculative execution is not applied to basic blocks where the " "number of instructions that would not be speculatively executed " "exceeds this limit."))
speculative Speculatively execute instructions
static cl::opt< unsigned > SpecExecMaxSpeculationCost("spec-exec-max-speculation-cost", cl::init(7), cl::Hidden, cl::desc("Speculative execution is not applied to basic blocks where " "the cost of the instructions to speculatively execute " "exceeds this limit."))
static cl::opt< bool > SpecExecOnlyIfDivergentTarget("spec-exec-only-if-divergent-target", cl::init(false), cl::Hidden, cl::desc("Speculative execution is applied only to targets with divergent " "branches, even if the pass was configured to apply only to all " "targets."))
speculative execution
This pass exposes codegen information to IR-level passes.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
Represent the analysis usage information of a pass.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:439
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:469
void insertDbgRecordBefore(DbgRecord *DPV, InstListType::iterator Here)
Insert a DbgRecord into a block at the position given by Here.
size_t size() const
Definition: BasicBlock.h:450
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:220
Conditional or Unconditional Branch instruction.
unsigned getNumSuccessors() const
BasicBlock * getSuccessor(unsigned i) const
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:70
Record of a variable value-assignment, aka a non instruction representation of the dbg....
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
Definition: DenseMap.h:145
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Legacy wrapper pass to provide the GlobalsAAResult object.
static InstructionCost getInvalid(CostType Val=0)
unsigned getOpcode() const
Return the opcode for this Instruction or ConstantExpr.
Definition: Operator.h:41
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:98
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
void preserveSet()
Mark an analysis set as preserved.
Definition: Analysis.h:144
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:360
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:342
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
SpeculativeExecutionPass(bool OnlyIfDivergentTarget=false)
bool runImpl(Function &F, TargetTransformInfo *TTI)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
Analysis pass providing the TargetTransformInfo.
Wrapper pass for TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
bool hasBranchDivergence(const Function *F=nullptr) const
Return true if branch divergence exists.
@ TCK_SizeAndLatency
The weighted sum of size and latency.
InstructionCost getInstructionCost(const User *U, ArrayRef< const Value * > Operands, TargetCostKind CostKind) const
Estimate the cost of a given IR user when lowered.
LLVM Value Representation.
Definition: Value.h:74
An efficient, type-erasing, non-owning reference to a callable.
self_iterator getIterator()
Definition: ilist_node.h:109
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
FunctionPass * createSpeculativeExecutionIfHasBranchDivergencePass()
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
FunctionPass * createSpeculativeExecutionPass()
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
InstructionCost Cost
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DPValue types only and downcast.
static InstructionCost ComputeSpeculationCost(const Instruction *I, const TargetTransformInfo &TTI)
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:91