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