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/IntrinsicsBPF.h"
19 #include "llvm/IR/Module.h"
20 #include "llvm/IR/PatternMatch.h"
21 #include "llvm/IR/Type.h"
22 #include "llvm/IR/User.h"
23 #include "llvm/IR/Value.h"
24 #include "llvm/Pass.h"
25 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
26
27 #define DEBUG_TYPE "bpf-adjust-opt"
28
29 using namespace llvm;
30 using namespace llvm::PatternMatch;
31
32 static cl::opt<bool>
33 DisableBPFserializeICMP("bpf-disable-serialize-icmp", cl::Hidden,
34 cl::desc("BPF: Disable Serializing ICMP insns."),
35 cl::init(false));
36
37 static cl::opt<bool> DisableBPFavoidSpeculation(
38 "bpf-disable-avoid-speculation", cl::Hidden,
39 cl::desc("BPF: Disable Avoiding Speculative Code Motion."),
40 cl::init(false));
41
42 namespace {
43 class BPFAdjustOptImpl {
44 struct PassThroughInfo {
45 Instruction *Input;
46 Instruction *UsedInst;
47 uint32_t OpIdx;
PassThroughInfo__anonb65f9f030111::BPFAdjustOptImpl::PassThroughInfo48 PassThroughInfo(Instruction *I, Instruction *U, uint32_t Idx)
49 : Input(I), UsedInst(U), OpIdx(Idx) {}
50 };
51
52 public:
BPFAdjustOptImpl(Module * M)53 BPFAdjustOptImpl(Module *M) : M(M) {}
54
55 bool run();
56
57 private:
58 Module *M;
59 SmallVector<PassThroughInfo, 16> PassThroughs;
60
61 bool adjustICmpToBuiltin();
62 void adjustBasicBlock(BasicBlock &BB);
63 bool serializeICMPCrossBB(BasicBlock &BB);
64 void adjustInst(Instruction &I);
65 bool serializeICMPInBB(Instruction &I);
66 bool avoidSpeculation(Instruction &I);
67 bool insertPassThrough();
68 };
69
70 } // End anonymous namespace
71
run()72 bool BPFAdjustOptImpl::run() {
73 bool Changed = adjustICmpToBuiltin();
74
75 for (Function &F : *M)
76 for (auto &BB : F) {
77 adjustBasicBlock(BB);
78 for (auto &I : BB)
79 adjustInst(I);
80 }
81 return insertPassThrough() || Changed;
82 }
83
84 // Commit acabad9ff6bf ("[InstCombine] try to canonicalize icmp with
85 // trunc op into mask and cmp") added a transformation to
86 // convert "(conv)a < power_2_const" to "a & <const>" in certain
87 // cases and bpf kernel verifier has to handle the resulted code
88 // conservatively and this may reject otherwise legitimate program.
89 // Here, we change related icmp code to a builtin which will
90 // be restored to original icmp code later to prevent that
91 // InstCombine transformatin.
adjustICmpToBuiltin()92 bool BPFAdjustOptImpl::adjustICmpToBuiltin() {
93 bool Changed = false;
94 ICmpInst *ToBeDeleted = nullptr;
95 for (Function &F : *M)
96 for (auto &BB : F)
97 for (auto &I : BB) {
98 if (ToBeDeleted) {
99 ToBeDeleted->eraseFromParent();
100 ToBeDeleted = nullptr;
101 }
102
103 auto *Icmp = dyn_cast<ICmpInst>(&I);
104 if (!Icmp)
105 continue;
106
107 Value *Op0 = Icmp->getOperand(0);
108 if (!isa<TruncInst>(Op0))
109 continue;
110
111 auto ConstOp1 = dyn_cast<ConstantInt>(Icmp->getOperand(1));
112 if (!ConstOp1)
113 continue;
114
115 auto ConstOp1Val = ConstOp1->getValue().getZExtValue();
116 auto Op = Icmp->getPredicate();
117 if (Op == ICmpInst::ICMP_ULT || Op == ICmpInst::ICMP_UGE) {
118 if ((ConstOp1Val - 1) & ConstOp1Val)
119 continue;
120 } else if (Op == ICmpInst::ICMP_ULE || Op == ICmpInst::ICMP_UGT) {
121 if (ConstOp1Val & (ConstOp1Val + 1))
122 continue;
123 } else {
124 continue;
125 }
126
127 Constant *Opcode =
128 ConstantInt::get(Type::getInt32Ty(BB.getContext()), Op);
129 Function *Fn = Intrinsic::getDeclaration(
130 M, Intrinsic::bpf_compare, {Op0->getType(), ConstOp1->getType()});
131 auto *NewInst = CallInst::Create(Fn, {Opcode, Op0, ConstOp1});
132 NewInst->insertBefore(&I);
133 Icmp->replaceAllUsesWith(NewInst);
134 Changed = true;
135 ToBeDeleted = Icmp;
136 }
137
138 return Changed;
139 }
140
insertPassThrough()141 bool BPFAdjustOptImpl::insertPassThrough() {
142 for (auto &Info : PassThroughs) {
143 auto *CI = BPFCoreSharedInfo::insertPassThrough(
144 M, Info.UsedInst->getParent(), Info.Input, Info.UsedInst);
145 Info.UsedInst->setOperand(Info.OpIdx, CI);
146 }
147
148 return !PassThroughs.empty();
149 }
150
151 // To avoid combining conditionals in the same basic block by
152 // instrcombine optimization.
serializeICMPInBB(Instruction & I)153 bool BPFAdjustOptImpl::serializeICMPInBB(Instruction &I) {
154 // For:
155 // comp1 = icmp <opcode> ...;
156 // comp2 = icmp <opcode> ...;
157 // ... or comp1 comp2 ...
158 // changed to:
159 // comp1 = icmp <opcode> ...;
160 // comp2 = icmp <opcode> ...;
161 // new_comp1 = __builtin_bpf_passthrough(seq_num, comp1)
162 // ... or new_comp1 comp2 ...
163 Value *Op0, *Op1;
164 // Use LogicalOr (accept `or i1` as well as `select i1 Op0, true, Op1`)
165 if (!match(&I, m_LogicalOr(m_Value(Op0), m_Value(Op1))))
166 return false;
167 auto *Icmp1 = dyn_cast<ICmpInst>(Op0);
168 if (!Icmp1)
169 return false;
170 auto *Icmp2 = dyn_cast<ICmpInst>(Op1);
171 if (!Icmp2)
172 return false;
173
174 Value *Icmp1Op0 = Icmp1->getOperand(0);
175 Value *Icmp2Op0 = Icmp2->getOperand(0);
176 if (Icmp1Op0 != Icmp2Op0)
177 return false;
178
179 // Now we got two icmp instructions which feed into
180 // an "or" instruction.
181 PassThroughInfo Info(Icmp1, &I, 0);
182 PassThroughs.push_back(Info);
183 return true;
184 }
185
186 // To avoid combining conditionals in the same basic block by
187 // instrcombine optimization.
serializeICMPCrossBB(BasicBlock & BB)188 bool BPFAdjustOptImpl::serializeICMPCrossBB(BasicBlock &BB) {
189 // For:
190 // B1:
191 // comp1 = icmp <opcode> ...;
192 // if (comp1) goto B2 else B3;
193 // B2:
194 // comp2 = icmp <opcode> ...;
195 // if (comp2) goto B4 else B5;
196 // B4:
197 // ...
198 // changed to:
199 // B1:
200 // comp1 = icmp <opcode> ...;
201 // comp1 = __builtin_bpf_passthrough(seq_num, comp1);
202 // if (comp1) goto B2 else B3;
203 // B2:
204 // comp2 = icmp <opcode> ...;
205 // if (comp2) goto B4 else B5;
206 // B4:
207 // ...
208
209 // Check basic predecessors, if two of them (say B1, B2) are using
210 // icmp instructions to generate conditions and one is the predesessor
211 // of another (e.g., B1 is the predecessor of B2). Add a passthrough
212 // barrier after icmp inst of block B1.
213 BasicBlock *B2 = BB.getSinglePredecessor();
214 if (!B2)
215 return false;
216
217 BasicBlock *B1 = B2->getSinglePredecessor();
218 if (!B1)
219 return false;
220
221 Instruction *TI = B2->getTerminator();
222 auto *BI = dyn_cast<BranchInst>(TI);
223 if (!BI || !BI->isConditional())
224 return false;
225 auto *Cond = dyn_cast<ICmpInst>(BI->getCondition());
226 if (!Cond || B2->getFirstNonPHI() != Cond)
227 return false;
228 Value *B2Op0 = Cond->getOperand(0);
229 auto Cond2Op = Cond->getPredicate();
230
231 TI = B1->getTerminator();
232 BI = dyn_cast<BranchInst>(TI);
233 if (!BI || !BI->isConditional())
234 return false;
235 Cond = dyn_cast<ICmpInst>(BI->getCondition());
236 if (!Cond)
237 return false;
238 Value *B1Op0 = Cond->getOperand(0);
239 auto Cond1Op = Cond->getPredicate();
240
241 if (B1Op0 != B2Op0)
242 return false;
243
244 if (Cond1Op == ICmpInst::ICMP_SGT || Cond1Op == ICmpInst::ICMP_SGE) {
245 if (Cond2Op != ICmpInst::ICMP_SLT && Cond2Op != ICmpInst::ICMP_SLE)
246 return false;
247 } else if (Cond1Op == ICmpInst::ICMP_SLT || Cond1Op == ICmpInst::ICMP_SLE) {
248 if (Cond2Op != ICmpInst::ICMP_SGT && Cond2Op != ICmpInst::ICMP_SGE)
249 return false;
250 } else if (Cond1Op == ICmpInst::ICMP_ULT || Cond1Op == ICmpInst::ICMP_ULE) {
251 if (Cond2Op != ICmpInst::ICMP_UGT && Cond2Op != ICmpInst::ICMP_UGE)
252 return false;
253 } else if (Cond1Op == ICmpInst::ICMP_UGT || Cond1Op == ICmpInst::ICMP_UGE) {
254 if (Cond2Op != ICmpInst::ICMP_ULT && Cond2Op != ICmpInst::ICMP_ULE)
255 return false;
256 } else {
257 return false;
258 }
259
260 PassThroughInfo Info(Cond, BI, 0);
261 PassThroughs.push_back(Info);
262
263 return true;
264 }
265
266 // To avoid speculative hoisting certain computations out of
267 // a basic block.
avoidSpeculation(Instruction & I)268 bool BPFAdjustOptImpl::avoidSpeculation(Instruction &I) {
269 if (auto *LdInst = dyn_cast<LoadInst>(&I)) {
270 if (auto *GV = dyn_cast<GlobalVariable>(LdInst->getOperand(0))) {
271 if (GV->hasAttribute(BPFCoreSharedInfo::AmaAttr) ||
272 GV->hasAttribute(BPFCoreSharedInfo::TypeIdAttr))
273 return false;
274 }
275 }
276
277 if (!isa<LoadInst>(&I) && !isa<CallInst>(&I))
278 return false;
279
280 // For:
281 // B1:
282 // var = ...
283 // ...
284 // /* icmp may not be in the same block as var = ... */
285 // comp1 = icmp <opcode> var, <const>;
286 // if (comp1) goto B2 else B3;
287 // B2:
288 // ... var ...
289 // change to:
290 // B1:
291 // var = ...
292 // ...
293 // /* icmp may not be in the same block as var = ... */
294 // comp1 = icmp <opcode> var, <const>;
295 // if (comp1) goto B2 else B3;
296 // B2:
297 // var = __builtin_bpf_passthrough(seq_num, var);
298 // ... var ...
299 bool isCandidate = false;
300 SmallVector<PassThroughInfo, 4> Candidates;
301 for (User *U : I.users()) {
302 Instruction *Inst = dyn_cast<Instruction>(U);
303 if (!Inst)
304 continue;
305
306 // May cover a little bit more than the
307 // above pattern.
308 if (auto *Icmp1 = dyn_cast<ICmpInst>(Inst)) {
309 Value *Icmp1Op1 = Icmp1->getOperand(1);
310 if (!isa<Constant>(Icmp1Op1))
311 return false;
312 isCandidate = true;
313 continue;
314 }
315
316 // Ignore the use in the same basic block as the definition.
317 if (Inst->getParent() == I.getParent())
318 continue;
319
320 // use in a different basic block, If there is a call or
321 // load/store insn before this instruction in this basic
322 // block. Most likely it cannot be hoisted out. Skip it.
323 for (auto &I2 : *Inst->getParent()) {
324 if (isa<CallInst>(&I2))
325 return false;
326 if (isa<LoadInst>(&I2) || isa<StoreInst>(&I2))
327 return false;
328 if (&I2 == Inst)
329 break;
330 }
331
332 // It should be used in a GEP or a simple arithmetic like
333 // ZEXT/SEXT which is used for GEP.
334 if (Inst->getOpcode() == Instruction::ZExt ||
335 Inst->getOpcode() == Instruction::SExt) {
336 PassThroughInfo Info(&I, Inst, 0);
337 Candidates.push_back(Info);
338 } else if (auto *GI = dyn_cast<GetElementPtrInst>(Inst)) {
339 // traverse GEP inst to find Use operand index
340 unsigned i, e;
341 for (i = 1, e = GI->getNumOperands(); i != e; ++i) {
342 Value *V = GI->getOperand(i);
343 if (V == &I)
344 break;
345 }
346 if (i == e)
347 continue;
348
349 PassThroughInfo Info(&I, GI, i);
350 Candidates.push_back(Info);
351 }
352 }
353
354 if (!isCandidate || Candidates.empty())
355 return false;
356
357 llvm::append_range(PassThroughs, Candidates);
358 return true;
359 }
360
adjustBasicBlock(BasicBlock & BB)361 void BPFAdjustOptImpl::adjustBasicBlock(BasicBlock &BB) {
362 if (!DisableBPFserializeICMP && serializeICMPCrossBB(BB))
363 return;
364 }
365
adjustInst(Instruction & I)366 void BPFAdjustOptImpl::adjustInst(Instruction &I) {
367 if (!DisableBPFserializeICMP && serializeICMPInBB(I))
368 return;
369 if (!DisableBPFavoidSpeculation && avoidSpeculation(I))
370 return;
371 }
372
run(Module & M,ModuleAnalysisManager & AM)373 PreservedAnalyses BPFAdjustOptPass::run(Module &M, ModuleAnalysisManager &AM) {
374 return BPFAdjustOptImpl(&M).run() ? PreservedAnalyses::none()
375 : PreservedAnalyses::all();
376 }
377