LLVM  14.0.0git
BPFAdjustOpt.cpp
Go to the documentation of this file.
1 //===---------------- BPFAdjustOpt.cpp - Adjust Optimization --------------===//
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 // Adjust optimization to make the code more kernel verifier friendly.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "BPF.h"
14 #include "BPFCORE.h"
15 #include "BPFTargetMachine.h"
16 #include "llvm/IR/Instruction.h"
17 #include "llvm/IR/Instructions.h"
18 #include "llvm/IR/Module.h"
19 #include "llvm/IR/PatternMatch.h"
20 #include "llvm/IR/Type.h"
21 #include "llvm/IR/User.h"
22 #include "llvm/IR/Value.h"
23 #include "llvm/Pass.h"
25 
26 #define DEBUG_TYPE "bpf-adjust-opt"
27 
28 using namespace llvm;
29 using namespace llvm::PatternMatch;
30 
31 static cl::opt<bool>
32  DisableBPFserializeICMP("bpf-disable-serialize-icmp", cl::Hidden,
33  cl::desc("BPF: Disable Serializing ICMP insns."),
34  cl::init(false));
35 
37  "bpf-disable-avoid-speculation", cl::Hidden,
38  cl::desc("BPF: Disable Avoiding Speculative Code Motion."),
39  cl::init(false));
40 
41 namespace {
42 
43 class BPFAdjustOpt final : public ModulePass {
44 public:
45  static char ID;
46 
47  BPFAdjustOpt() : ModulePass(ID) {}
48  bool runOnModule(Module &M) override;
49 };
50 
51 class BPFAdjustOptImpl {
52  struct PassThroughInfo {
53  Instruction *Input;
54  Instruction *UsedInst;
55  uint32_t OpIdx;
56  PassThroughInfo(Instruction *I, Instruction *U, uint32_t Idx)
57  : Input(I), UsedInst(U), OpIdx(Idx) {}
58  };
59 
60 public:
61  BPFAdjustOptImpl(Module *M) : M(M) {}
62 
63  bool run();
64 
65 private:
66  Module *M;
68 
69  void adjustBasicBlock(BasicBlock &BB);
70  bool serializeICMPCrossBB(BasicBlock &BB);
71  void adjustInst(Instruction &I);
72  bool serializeICMPInBB(Instruction &I);
73  bool avoidSpeculation(Instruction &I);
74  bool insertPassThrough();
75 };
76 
77 } // End anonymous namespace
78 
79 char BPFAdjustOpt::ID = 0;
80 INITIALIZE_PASS(BPFAdjustOpt, "bpf-adjust-opt", "BPF Adjust Optimization",
81  false, false)
82 
83 ModulePass *llvm::createBPFAdjustOpt() { return new BPFAdjustOpt(); }
84 
85 bool BPFAdjustOpt::runOnModule(Module &M) { return BPFAdjustOptImpl(&M).run(); }
86 
87 bool BPFAdjustOptImpl::run() {
88  for (Function &F : *M)
89  for (auto &BB : F) {
90  adjustBasicBlock(BB);
91  for (auto &I : BB)
92  adjustInst(I);
93  }
94 
95  return insertPassThrough();
96 }
97 
98 bool BPFAdjustOptImpl::insertPassThrough() {
99  for (auto &Info : PassThroughs) {
101  M, Info.UsedInst->getParent(), Info.Input, Info.UsedInst);
102  Info.UsedInst->setOperand(Info.OpIdx, CI);
103  }
104 
105  return !PassThroughs.empty();
106 }
107 
108 // To avoid combining conditionals in the same basic block by
109 // instrcombine optimization.
110 bool BPFAdjustOptImpl::serializeICMPInBB(Instruction &I) {
111  // For:
112  // comp1 = icmp <opcode> ...;
113  // comp2 = icmp <opcode> ...;
114  // ... or comp1 comp2 ...
115  // changed to:
116  // comp1 = icmp <opcode> ...;
117  // comp2 = icmp <opcode> ...;
118  // new_comp1 = __builtin_bpf_passthrough(seq_num, comp1)
119  // ... or new_comp1 comp2 ...
120  Value *Op0, *Op1;
121  // Use LogicalOr (accept `or i1` as well as `select i1 Op0, true, Op1`)
122  if (!match(&I, m_LogicalOr(m_Value(Op0), m_Value(Op1))))
123  return false;
124  auto *Icmp1 = dyn_cast<ICmpInst>(Op0);
125  if (!Icmp1)
126  return false;
127  auto *Icmp2 = dyn_cast<ICmpInst>(Op1);
128  if (!Icmp2)
129  return false;
130 
131  Value *Icmp1Op0 = Icmp1->getOperand(0);
132  Value *Icmp2Op0 = Icmp2->getOperand(0);
133  if (Icmp1Op0 != Icmp2Op0)
134  return false;
135 
136  // Now we got two icmp instructions which feed into
137  // an "or" instruction.
138  PassThroughInfo Info(Icmp1, &I, 0);
139  PassThroughs.push_back(Info);
140  return true;
141 }
142 
143 // To avoid combining conditionals in the same basic block by
144 // instrcombine optimization.
145 bool BPFAdjustOptImpl::serializeICMPCrossBB(BasicBlock &BB) {
146  // For:
147  // B1:
148  // comp1 = icmp <opcode> ...;
149  // if (comp1) goto B2 else B3;
150  // B2:
151  // comp2 = icmp <opcode> ...;
152  // if (comp2) goto B4 else B5;
153  // B4:
154  // ...
155  // changed to:
156  // B1:
157  // comp1 = icmp <opcode> ...;
158  // comp1 = __builtin_bpf_passthrough(seq_num, comp1);
159  // if (comp1) goto B2 else B3;
160  // B2:
161  // comp2 = icmp <opcode> ...;
162  // if (comp2) goto B4 else B5;
163  // B4:
164  // ...
165 
166  // Check basic predecessors, if two of them (say B1, B2) are using
167  // icmp instructions to generate conditions and one is the predesessor
168  // of another (e.g., B1 is the predecessor of B2). Add a passthrough
169  // barrier after icmp inst of block B1.
170  BasicBlock *B2 = BB.getSinglePredecessor();
171  if (!B2)
172  return false;
173 
175  if (!B1)
176  return false;
177 
178  Instruction *TI = B2->getTerminator();
179  auto *BI = dyn_cast<BranchInst>(TI);
180  if (!BI || !BI->isConditional())
181  return false;
182  auto *Cond = dyn_cast<ICmpInst>(BI->getCondition());
183  if (!Cond || B2->getFirstNonPHI() != Cond)
184  return false;
185  Value *B2Op0 = Cond->getOperand(0);
186  auto Cond2Op = Cond->getPredicate();
187 
188  TI = B1->getTerminator();
189  BI = dyn_cast<BranchInst>(TI);
190  if (!BI || !BI->isConditional())
191  return false;
192  Cond = dyn_cast<ICmpInst>(BI->getCondition());
193  if (!Cond)
194  return false;
195  Value *B1Op0 = Cond->getOperand(0);
196  auto Cond1Op = Cond->getPredicate();
197 
198  if (B1Op0 != B2Op0)
199  return false;
200 
201  if (Cond1Op == ICmpInst::ICMP_SGT || Cond1Op == ICmpInst::ICMP_SGE) {
202  if (Cond2Op != ICmpInst::ICMP_SLT && Cond1Op != ICmpInst::ICMP_SLE)
203  return false;
204  } else if (Cond1Op == ICmpInst::ICMP_SLT || Cond1Op == ICmpInst::ICMP_SLE) {
205  if (Cond2Op != ICmpInst::ICMP_SGT && Cond1Op != ICmpInst::ICMP_SGE)
206  return false;
207  } else {
208  return false;
209  }
210 
211  PassThroughInfo Info(Cond, BI, 0);
212  PassThroughs.push_back(Info);
213 
214  return true;
215 }
216 
217 // To avoid speculative hoisting certain computations out of
218 // a basic block.
219 bool BPFAdjustOptImpl::avoidSpeculation(Instruction &I) {
220  if (auto *LdInst = dyn_cast<LoadInst>(&I)) {
221  if (auto *GV = dyn_cast<GlobalVariable>(LdInst->getOperand(0))) {
222  if (GV->hasAttribute(BPFCoreSharedInfo::AmaAttr) ||
223  GV->hasAttribute(BPFCoreSharedInfo::TypeIdAttr))
224  return false;
225  }
226  }
227 
228  if (!isa<LoadInst>(&I) && !isa<CallInst>(&I))
229  return false;
230 
231  // For:
232  // B1:
233  // var = ...
234  // ...
235  // /* icmp may not be in the same block as var = ... */
236  // comp1 = icmp <opcode> var, <const>;
237  // if (comp1) goto B2 else B3;
238  // B2:
239  // ... var ...
240  // change to:
241  // B1:
242  // var = ...
243  // ...
244  // /* icmp may not be in the same block as var = ... */
245  // comp1 = icmp <opcode> var, <const>;
246  // if (comp1) goto B2 else B3;
247  // B2:
248  // var = __builtin_bpf_passthrough(seq_num, var);
249  // ... var ...
250  bool isCandidate = false;
252  for (User *U : I.users()) {
253  Instruction *Inst = dyn_cast<Instruction>(U);
254  if (!Inst)
255  continue;
256 
257  // May cover a little bit more than the
258  // above pattern.
259  if (auto *Icmp1 = dyn_cast<ICmpInst>(Inst)) {
260  Value *Icmp1Op1 = Icmp1->getOperand(1);
261  if (!isa<Constant>(Icmp1Op1))
262  return false;
263  isCandidate = true;
264  continue;
265  }
266 
267  // Ignore the use in the same basic block as the definition.
268  if (Inst->getParent() == I.getParent())
269  continue;
270 
271  // use in a different basic block, If there is a call or
272  // load/store insn before this instruction in this basic
273  // block. Most likely it cannot be hoisted out. Skip it.
274  for (auto &I2 : *Inst->getParent()) {
275  if (isa<CallInst>(&I2))
276  return false;
277  if (isa<LoadInst>(&I2) || isa<StoreInst>(&I2))
278  return false;
279  if (&I2 == Inst)
280  break;
281  }
282 
283  // It should be used in a GEP or a simple arithmetic like
284  // ZEXT/SEXT which is used for GEP.
285  if (Inst->getOpcode() == Instruction::ZExt ||
286  Inst->getOpcode() == Instruction::SExt) {
287  PassThroughInfo Info(&I, Inst, 0);
288  Candidates.push_back(Info);
289  } else if (auto *GI = dyn_cast<GetElementPtrInst>(Inst)) {
290  // traverse GEP inst to find Use operand index
291  unsigned i, e;
292  for (i = 1, e = GI->getNumOperands(); i != e; ++i) {
293  Value *V = GI->getOperand(i);
294  if (V == &I)
295  break;
296  }
297  if (i == e)
298  continue;
299 
300  PassThroughInfo Info(&I, GI, i);
301  Candidates.push_back(Info);
302  }
303  }
304 
305  if (!isCandidate || Candidates.empty())
306  return false;
307 
308  llvm::append_range(PassThroughs, Candidates);
309  return true;
310 }
311 
312 void BPFAdjustOptImpl::adjustBasicBlock(BasicBlock &BB) {
313  if (!DisableBPFserializeICMP && serializeICMPCrossBB(BB))
314  return;
315 }
316 
317 void BPFAdjustOptImpl::adjustInst(Instruction &I) {
318  if (!DisableBPFserializeICMP && serializeICMPInBB(I))
319  return;
320  if (!DisableBPFavoidSpeculation && avoidSpeculation(I))
321  return;
322 }
323 
325  return BPFAdjustOptImpl(&M).run() ? PreservedAnalyses::none()
327 }
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
B1
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::ModulePass
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:238
llvm::Function
Definition: Function.h:61
Pass.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
INITIALIZE_PASS
INITIALIZE_PASS(BPFAdjustOpt, "bpf-adjust-opt", "BPF Adjust Optimization", false, false) ModulePass *llvm
Definition: BPFAdjustOpt.cpp:80
llvm::PreservedAnalyses::none
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:158
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:747
Module.h
llvm::CmpInst::ICMP_SLE
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:750
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:264
BPF.h
DisableBPFavoidSpeculation
static cl::opt< bool > DisableBPFavoidSpeculation("bpf-disable-avoid-speculation", cl::Hidden, cl::desc("BPF: Disable Avoiding Speculative Code Motion."), cl::init(false))
llvm::createBPFAdjustOpt
ModulePass * createBPFAdjustOpt()
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
Instruction.h
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::User
Definition: User.h:44
llvm::Instruction
Definition: Instruction.h:45
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
PatternMatch.h
llvm::BasicBlock::getFirstNonPHI
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:212
Type.h
llvm::cl::opt< bool >
llvm::PatternMatch::m_LogicalOr
LogicalOp_match< LHS, RHS, Instruction::Or > m_LogicalOr(const LHS &L, const RHS &R)
Matches L || R either in the form of L | R or L ? true : R.
Definition: PatternMatch.h:2510
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::BPFCoreSharedInfo::insertPassThrough
static Instruction * insertPassThrough(Module *M, BasicBlock *BB, Instruction *Input, Instruction *Before)
Insert a bpf passthrough builtin function.
Definition: BPFAbstractMemberAccess.cpp:100
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
llvm::BPFCoreSharedInfo::TypeIdAttr
static constexpr StringRef TypeIdAttr
The attribute attached to globals representing a type id.
Definition: BPFCORE.h:63
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::CmpInst::ICMP_SLT
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:749
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
uint32_t
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1744
llvm::BasicBlock::getTerminator
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.cpp:148
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
BPFCORE.h
llvm::CmpInst::ICMP_SGE
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:748
llvm::BPFCoreSharedInfo::AmaAttr
static constexpr StringRef AmaAttr
The attribute attached to globals representing a field access.
Definition: BPFCORE.h:61
Instructions.h
User.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::BPFAdjustOptPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: BPFAdjustOpt.cpp:324
llvm::PatternMatch
Definition: PatternMatch.h:47
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::cl::desc
Definition: CommandLine.h:414
DisableBPFserializeICMP
static cl::opt< bool > DisableBPFserializeICMP("bpf-disable-serialize-icmp", cl::Hidden, cl::desc("BPF: Disable Serializing ICMP insns."), cl::init(false))
BasicBlockUtils.h
Value.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
BPFTargetMachine.h