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