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
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/IntrinsicInst.h"
70#include "llvm/IR/Operator.h"
71#include "llvm/InitializePasses.h"
72#include "llvm/Support/CommandLine.h"
73#include "llvm/Support/Debug.h"
74#include "llvm/Transforms/Scalar.h"
75
76using namespace llvm;
77
78#define DEBUG_TYPE "speculative-execution"
79
80// The risk that speculation will not pay off increases with the
81// number of instructions speculated, so we put a limit on that.
82static cl::opt<unsigned> SpecExecMaxSpeculationCost(
83 "spec-exec-max-speculation-cost", cl::init(Val: 7), cl::Hidden,
84 cl::desc("Speculative execution is not applied to basic blocks where "
85 "the cost of the instructions to speculatively execute "
86 "exceeds this limit."));
87
88// Speculating just a few instructions from a larger block tends not
89// to be profitable and this limit prevents that. A reason for that is
90// that small basic blocks are more likely to be candidates for
91// further optimization.
92static cl::opt<unsigned> SpecExecMaxNotHoisted(
93 "spec-exec-max-not-hoisted", cl::init(Val: 5), cl::Hidden,
94 cl::desc("Speculative execution is not applied to basic blocks where the "
95 "number of instructions that would not be speculatively executed "
96 "exceeds this limit."));
97
98static cl::opt<bool> SpecExecOnlyIfDivergentTarget(
99 "spec-exec-only-if-divergent-target", cl::init(Val: false), cl::Hidden,
100 cl::desc("Speculative execution is applied only to targets with divergent "
101 "branches, even if the pass was configured to apply only to all "
102 "targets."));
103
104namespace {
105
106class SpeculativeExecutionLegacyPass : public FunctionPass {
107public:
108 static char ID;
109 explicit SpeculativeExecutionLegacyPass(bool OnlyIfDivergentTarget = false)
110 : FunctionPass(ID), OnlyIfDivergentTarget(OnlyIfDivergentTarget ||
111 SpecExecOnlyIfDivergentTarget),
112 Impl(OnlyIfDivergentTarget) {}
113
114 void getAnalysisUsage(AnalysisUsage &AU) const override;
115 bool runOnFunction(Function &F) override;
116
117 StringRef getPassName() const override {
118 if (OnlyIfDivergentTarget)
119 return "Speculatively execute instructions if target has divergent "
120 "branches";
121 return "Speculatively execute instructions";
122 }
123
124private:
125 // Variable preserved purely for correct name printing.
126 const bool OnlyIfDivergentTarget;
127
128 SpeculativeExecutionPass Impl;
129};
130} // namespace
131
132char SpeculativeExecutionLegacyPass::ID = 0;
133INITIALIZE_PASS_BEGIN(SpeculativeExecutionLegacyPass, "speculative-execution",
134 "Speculatively execute instructions", false, false)
135INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
136INITIALIZE_PASS_END(SpeculativeExecutionLegacyPass, "speculative-execution",
137 "Speculatively execute instructions", false, false)
138
139void SpeculativeExecutionLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const {
140 AU.addRequired<TargetTransformInfoWrapperPass>();
141 AU.addPreserved<GlobalsAAWrapperPass>();
142 AU.setPreservesCFG();
143}
144
145bool SpeculativeExecutionLegacyPass::runOnFunction(Function &F) {
146 if (skipFunction(F))
147 return false;
148
149 auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
150 return Impl.runImpl(F, TTI);
151}
152
153namespace llvm {
154
155bool SpeculativeExecutionPass::runImpl(Function &F, TargetTransformInfo *TTI) {
156 if (OnlyIfDivergentTarget && !TTI->hasBranchDivergence(F: &F)) {
157 LLVM_DEBUG(dbgs() << "Not running SpeculativeExecution because "
158 "TTI->hasBranchDivergence() is false.\n");
159 return false;
160 }
161
162 this->TTI = TTI;
163 bool Changed = false;
164 for (auto& B : F) {
165 Changed |= runOnBasicBlock(B);
166 }
167 return Changed;
168}
169
170bool SpeculativeExecutionPass::runOnBasicBlock(BasicBlock &B) {
171 BranchInst *BI = dyn_cast<BranchInst>(Val: B.getTerminator());
172 if (BI == nullptr)
173 return false;
174
175 if (BI->getNumSuccessors() != 2)
176 return false;
177 BasicBlock &Succ0 = *BI->getSuccessor(i: 0);
178 BasicBlock &Succ1 = *BI->getSuccessor(i: 1);
179
180 if (&B == &Succ0 || &B == &Succ1 || &Succ0 == &Succ1) {
181 return false;
182 }
183
184 // Hoist from if-then (triangle).
185 if (Succ0.getSinglePredecessor() != nullptr &&
186 Succ0.getSingleSuccessor() == &Succ1) {
187 return considerHoistingFromTo(FromBlock&: Succ0, ToBlock&: B);
188 }
189
190 // Hoist from if-else (triangle).
191 if (Succ1.getSinglePredecessor() != nullptr &&
192 Succ1.getSingleSuccessor() == &Succ0) {
193 return considerHoistingFromTo(FromBlock&: Succ1, ToBlock&: B);
194 }
195
196 // Hoist from if-then-else (diamond), but only if it is equivalent to
197 // an if-else or if-then due to one of the branches doing nothing.
198 if (Succ0.getSinglePredecessor() != nullptr &&
199 Succ1.getSinglePredecessor() != nullptr &&
200 Succ1.getSingleSuccessor() != nullptr &&
201 Succ1.getSingleSuccessor() != &B &&
202 Succ1.getSingleSuccessor() == Succ0.getSingleSuccessor()) {
203 // If a block has only one instruction, then that is a terminator
204 // instruction so that the block does nothing. This does happen.
205 if (Succ1.size() == 1) // equivalent to if-then
206 return considerHoistingFromTo(FromBlock&: Succ0, ToBlock&: B);
207 if (Succ0.size() == 1) // equivalent to if-else
208 return considerHoistingFromTo(FromBlock&: Succ1, ToBlock&: B);
209 }
210
211 return false;
212}
213
214static InstructionCost ComputeSpeculationCost(const Instruction *I,
215 const TargetTransformInfo &TTI) {
216 switch (Operator::getOpcode(V: I)) {
217 case Instruction::GetElementPtr:
218 case Instruction::Add:
219 case Instruction::Mul:
220 case Instruction::And:
221 case Instruction::Or:
222 case Instruction::Select:
223 case Instruction::Shl:
224 case Instruction::Sub:
225 case Instruction::LShr:
226 case Instruction::AShr:
227 case Instruction::Xor:
228 case Instruction::ZExt:
229 case Instruction::SExt:
230 case Instruction::Call:
231 case Instruction::BitCast:
232 case Instruction::PtrToInt:
233 case Instruction::IntToPtr:
234 case Instruction::AddrSpaceCast:
235 case Instruction::FPToUI:
236 case Instruction::FPToSI:
237 case Instruction::UIToFP:
238 case Instruction::SIToFP:
239 case Instruction::FPExt:
240 case Instruction::FPTrunc:
241 case Instruction::FAdd:
242 case Instruction::FSub:
243 case Instruction::FMul:
244 case Instruction::FDiv:
245 case Instruction::FRem:
246 case Instruction::FNeg:
247 case Instruction::ICmp:
248 case Instruction::FCmp:
249 case Instruction::Trunc:
250 case Instruction::Freeze:
251 case Instruction::ExtractElement:
252 case Instruction::InsertElement:
253 case Instruction::ShuffleVector:
254 case Instruction::ExtractValue:
255 case Instruction::InsertValue:
256 return TTI.getInstructionCost(U: I, CostKind: TargetTransformInfo::TCK_SizeAndLatency);
257
258 default:
259 return InstructionCost::getInvalid(); // Disallow anything not explicitly
260 // listed.
261 }
262}
263
264// Do not hoist any debug info intrinsics.
265// ...
266// if (cond) {
267// x = y * z;
268// foo();
269// }
270// ...
271// -------- Which then becomes:
272// ...
273// if.then:
274// %x = mul i32 %y, %z
275// call void @llvm.dbg.value(%x, !"x", !DIExpression())
276// call void foo()
277//
278// SpeculativeExecution might decide to hoist the 'y * z' calculation
279// out of the 'if' block, because it is more efficient that way, so the
280// '%x = mul i32 %y, %z' moves to the block above. But it might also
281// decide to hoist the 'llvm.dbg.value' call.
282// This is incorrect, because even if we've moved the calculation of
283// 'y * z', we should not see the value of 'x' change unless we
284// actually go inside the 'if' block.
285
286bool SpeculativeExecutionPass::considerHoistingFromTo(
287 BasicBlock &FromBlock, BasicBlock &ToBlock) {
288 SmallPtrSet<const Instruction *, 8> NotHoisted;
289 auto HasNoUnhoistedInstr = [&NotHoisted](auto Values) {
290 for (const Value *V : Values) {
291 if (const auto *I = dyn_cast_or_null<Instruction>(Val: V))
292 if (NotHoisted.contains(Ptr: I))
293 return false;
294 }
295 return true;
296 };
297 auto AllPrecedingUsesFromBlockHoisted =
298 [&HasNoUnhoistedInstr](const User *U) {
299 return HasNoUnhoistedInstr(U->operand_values());
300 };
301
302 InstructionCost TotalSpeculationCost = 0;
303 unsigned NotHoistedInstCount = 0;
304 for (const auto &I : FromBlock) {
305 const InstructionCost Cost = ComputeSpeculationCost(I: &I, TTI: *TTI);
306 if (Cost.isValid() && isSafeToSpeculativelyExecute(I: &I) &&
307 AllPrecedingUsesFromBlockHoisted(&I)) {
308 TotalSpeculationCost += Cost;
309 if (TotalSpeculationCost > SpecExecMaxSpeculationCost)
310 return false; // too much to hoist
311 } else {
312 NotHoistedInstCount++;
313 if (NotHoistedInstCount > SpecExecMaxNotHoisted)
314 return false; // too much left behind
315 NotHoisted.insert(Ptr: &I);
316 }
317 }
318
319 for (auto I = FromBlock.begin(); I != FromBlock.end();) {
320 // We have to increment I before moving Current as moving Current
321 // changes the list that I is iterating through.
322 auto Current = I;
323 ++I;
324 if (!NotHoisted.count(Ptr: &*Current)) {
325 Current->moveBefore(InsertPos: ToBlock.getTerminator()->getIterator());
326 Current->dropLocation();
327 }
328 }
329 return true;
330}
331
332FunctionPass *createSpeculativeExecutionPass() {
333 return new SpeculativeExecutionLegacyPass();
334}
335
336FunctionPass *createSpeculativeExecutionIfHasBranchDivergencePass() {
337 return new SpeculativeExecutionLegacyPass(/* OnlyIfDivergentTarget = */ true);
338}
339
340SpeculativeExecutionPass::SpeculativeExecutionPass(bool OnlyIfDivergentTarget)
341 : OnlyIfDivergentTarget(OnlyIfDivergentTarget ||
342 SpecExecOnlyIfDivergentTarget) {}
343
344PreservedAnalyses SpeculativeExecutionPass::run(Function &F,
345 FunctionAnalysisManager &AM) {
346 auto *TTI = &AM.getResult<TargetIRAnalysis>(IR&: F);
347
348 bool Changed = runImpl(F, TTI);
349
350 if (!Changed)
351 return PreservedAnalyses::all();
352 PreservedAnalyses PA;
353 PA.preserveSet<CFGAnalyses>();
354 return PA;
355}
356
357void SpeculativeExecutionPass::printPipeline(
358 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
359 static_cast<PassInfoMixin<SpeculativeExecutionPass> *>(this)->printPipeline(
360 OS, MapClassName2PassName);
361 OS << '<';
362 if (OnlyIfDivergentTarget)
363 OS << "only-if-divergent-target";
364 OS << '>';
365}
366} // namespace llvm
367