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/Type.h"
20 #include "llvm/IR/User.h"
21 #include "llvm/IR/Value.h"
22 #include "llvm/Pass.h"
23 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
24 
25 #define DEBUG_TYPE "bpf-adjust-opt"
26 
27 using namespace llvm;
28 
29 static cl::opt<bool>
30     DisableBPFserializeICMP("bpf-disable-serialize-icmp", cl::Hidden,
31                             cl::desc("BPF: Disable Serializing ICMP insns."),
32                             cl::init(false));
33 
34 static cl::opt<bool> DisableBPFavoidSpeculation(
35     "bpf-disable-avoid-speculation", cl::Hidden,
36     cl::desc("BPF: Disable Avoiding Speculative Code Motion."),
37     cl::init(false));
38 
39 namespace {
40 
41 class BPFAdjustOpt final : public ModulePass {
42 public:
43   static char ID;
44 
45   BPFAdjustOpt() : ModulePass(ID) {}
46   bool runOnModule(Module &M) override;
47 };
48 
49 class BPFAdjustOptImpl {
50   struct PassThroughInfo {
51     Instruction *Input;
52     Instruction *UsedInst;
53     uint32_t OpIdx;
54     PassThroughInfo(Instruction *I, Instruction *U, uint32_t Idx)
55         : Input(I), UsedInst(U), OpIdx(Idx) {}
56   };
57 
58 public:
59   BPFAdjustOptImpl(Module *M) : M(M) {}
60 
61   bool run();
62 
63 private:
64   Module *M;
65   SmallVector<PassThroughInfo, 16> PassThroughs;
66 
67   void adjustBasicBlock(BasicBlock &BB);
68   bool serializeICMPCrossBB(BasicBlock &BB);
69   void adjustInst(Instruction &I);
70   bool serializeICMPInBB(Instruction &I);
71   bool avoidSpeculation(Instruction &I);
72   bool insertPassThrough();
73 };
74 
75 } // End anonymous namespace
76 
77 char BPFAdjustOpt::ID = 0;
78 INITIALIZE_PASS(BPFAdjustOpt, "bpf-adjust-opt", "BPF Adjust Optimization",
79                 false, false)
80 
81 ModulePass *llvm::createBPFAdjustOpt() { return new BPFAdjustOpt(); }
82 
83 bool BPFAdjustOpt::runOnModule(Module &M) { return BPFAdjustOptImpl(&M).run(); }
84 
85 bool BPFAdjustOptImpl::run() {
86   for (Function &F : *M)
87     for (auto &BB : F) {
88       adjustBasicBlock(BB);
89       for (auto &I : BB)
90         adjustInst(I);
91     }
92 
93   return insertPassThrough();
94 }
95 
96 bool BPFAdjustOptImpl::insertPassThrough() {
97   for (auto &Info : PassThroughs) {
98     auto *CI = BPFCoreSharedInfo::insertPassThrough(
99         M, Info.UsedInst->getParent(), Info.Input, Info.UsedInst);
100     Info.UsedInst->setOperand(Info.OpIdx, CI);
101   }
102 
103   return !PassThroughs.empty();
104 }
105 
106 // To avoid combining conditionals in the same basic block by
107 // instrcombine optimization.
108 bool BPFAdjustOptImpl::serializeICMPInBB(Instruction &I) {
109   // For:
110   //   comp1 = icmp <opcode> ...;
111   //   comp2 = icmp <opcode> ...;
112   //   ... or comp1 comp2 ...
113   // changed to:
114   //   comp1 = icmp <opcode> ...;
115   //   comp2 = icmp <opcode> ...;
116   //   new_comp1 = __builtin_bpf_passthrough(seq_num, comp1)
117   //   ... or new_comp1 comp2 ...
118   if (I.getOpcode() != Instruction::Or)
119     return false;
120   auto *Icmp1 = dyn_cast<ICmpInst>(I.getOperand(0));
121   if (!Icmp1)
122     return false;
123   auto *Icmp2 = dyn_cast<ICmpInst>(I.getOperand(1));
124   if (!Icmp2)
125     return false;
126 
127   Value *Icmp1Op0 = Icmp1->getOperand(0);
128   Value *Icmp2Op0 = Icmp2->getOperand(0);
129   if (Icmp1Op0 != Icmp2Op0)
130     return false;
131 
132   // Now we got two icmp instructions which feed into
133   // an "or" instruction.
134   PassThroughInfo Info(Icmp1, &I, 0);
135   PassThroughs.push_back(Info);
136   return true;
137 }
138 
139 // To avoid combining conditionals in the same basic block by
140 // instrcombine optimization.
141 bool BPFAdjustOptImpl::serializeICMPCrossBB(BasicBlock &BB) {
142   // For:
143   //   B1:
144   //     comp1 = icmp <opcode> ...;
145   //     if (comp1) goto B2 else B3;
146   //   B2:
147   //     comp2 = icmp <opcode> ...;
148   //     if (comp2) goto B4 else B5;
149   //   B4:
150   //     ...
151   // changed to:
152   //   B1:
153   //     comp1 = icmp <opcode> ...;
154   //     comp1 = __builtin_bpf_passthrough(seq_num, comp1);
155   //     if (comp1) goto B2 else B3;
156   //   B2:
157   //     comp2 = icmp <opcode> ...;
158   //     if (comp2) goto B4 else B5;
159   //   B4:
160   //     ...
161 
162   // Check basic predecessors, if two of them (say B1, B2) are using
163   // icmp instructions to generate conditions and one is the predesessor
164   // of another (e.g., B1 is the predecessor of B2). Add a passthrough
165   // barrier after icmp inst of block B1.
166   BasicBlock *B2 = BB.getSinglePredecessor();
167   if (!B2)
168     return false;
169 
170   BasicBlock *B1 = B2->getSinglePredecessor();
171   if (!B1)
172     return false;
173 
174   Instruction *TI = B2->getTerminator();
175   auto *BI = dyn_cast<BranchInst>(TI);
176   if (!BI || !BI->isConditional())
177     return false;
178   auto *Cond = dyn_cast<ICmpInst>(BI->getCondition());
179   if (!Cond || B2->getFirstNonPHI() != Cond)
180     return false;
181   Value *B2Op0 = Cond->getOperand(0);
182   auto Cond2Op = Cond->getPredicate();
183 
184   TI = B1->getTerminator();
185   BI = dyn_cast<BranchInst>(TI);
186   if (!BI || !BI->isConditional())
187     return false;
188   Cond = dyn_cast<ICmpInst>(BI->getCondition());
189   if (!Cond)
190     return false;
191   Value *B1Op0 = Cond->getOperand(0);
192   auto Cond1Op = Cond->getPredicate();
193 
194   if (B1Op0 != B2Op0)
195     return false;
196 
197   if (Cond1Op == ICmpInst::ICMP_SGT || Cond1Op == ICmpInst::ICMP_SGE) {
198     if (Cond2Op != ICmpInst::ICMP_SLT && Cond1Op != ICmpInst::ICMP_SLE)
199       return false;
200   } else if (Cond1Op == ICmpInst::ICMP_SLT || Cond1Op == ICmpInst::ICMP_SLE) {
201     if (Cond2Op != ICmpInst::ICMP_SGT && Cond1Op != ICmpInst::ICMP_SGE)
202       return false;
203   } else {
204     return false;
205   }
206 
207   PassThroughInfo Info(Cond, BI, 0);
208   PassThroughs.push_back(Info);
209 
210   return true;
211 }
212 
213 // To avoid speculative hoisting certain computations out of
214 // a basic block.
215 bool BPFAdjustOptImpl::avoidSpeculation(Instruction &I) {
216   if (auto *LdInst = dyn_cast<LoadInst>(&I)) {
217     if (auto *GV = dyn_cast<GlobalVariable>(LdInst->getOperand(0))) {
218       if (GV->hasAttribute(BPFCoreSharedInfo::AmaAttr) ||
219           GV->hasAttribute(BPFCoreSharedInfo::TypeIdAttr))
220         return false;
221     }
222   }
223 
224   if (!isa<LoadInst>(&I) && !isa<CallInst>(&I))
225     return false;
226 
227   // For:
228   //   B1:
229   //     var = ...
230   //     ...
231   //     /* icmp may not be in the same block as var = ... */
232   //     comp1 = icmp <opcode> var, <const>;
233   //     if (comp1) goto B2 else B3;
234   //   B2:
235   //     ... var ...
236   // change to:
237   //   B1:
238   //     var = ...
239   //     ...
240   //     /* icmp may not be in the same block as var = ... */
241   //     comp1 = icmp <opcode> var, <const>;
242   //     if (comp1) goto B2 else B3;
243   //   B2:
244   //     var = __builtin_bpf_passthrough(seq_num, var);
245   //     ... var ...
246   bool isCandidate = false;
247   SmallVector<PassThroughInfo, 4> Candidates;
248   for (User *U : I.users()) {
249     Instruction *Inst = dyn_cast<Instruction>(U);
250     if (!Inst)
251       continue;
252 
253     // May cover a little bit more than the
254     // above pattern.
255     if (auto *Icmp1 = dyn_cast<ICmpInst>(Inst)) {
256       Value *Icmp1Op1 = Icmp1->getOperand(1);
257       if (!isa<Constant>(Icmp1Op1))
258         return false;
259       isCandidate = true;
260       continue;
261     }
262 
263     // Ignore the use in the same basic block as the definition.
264     if (Inst->getParent() == I.getParent())
265       continue;
266 
267     // use in a different basic block, If there is a call or
268     // load/store insn before this instruction in this basic
269     // block. Most likely it cannot be hoisted out. Skip it.
270     for (auto &I2 : *Inst->getParent()) {
271       if (dyn_cast<CallInst>(&I2))
272         return false;
273       if (dyn_cast<LoadInst>(&I2) || dyn_cast<StoreInst>(&I2))
274         return false;
275       if (&I2 == Inst)
276         break;
277     }
278 
279     // It should be used in a GEP or a simple arithmetic like
280     // ZEXT/SEXT which is used for GEP.
281     if (Inst->getOpcode() == Instruction::ZExt ||
282         Inst->getOpcode() == Instruction::SExt) {
283       PassThroughInfo Info(&I, Inst, 0);
284       Candidates.push_back(Info);
285     } else if (auto *GI = dyn_cast<GetElementPtrInst>(Inst)) {
286       // traverse GEP inst to find Use operand index
287       unsigned i, e;
288       for (i = 1, e = GI->getNumOperands(); i != e; ++i) {
289         Value *V = GI->getOperand(i);
290         if (V == &I)
291           break;
292       }
293       if (i == e)
294         continue;
295 
296       PassThroughInfo Info(&I, GI, i);
297       Candidates.push_back(Info);
298     }
299   }
300 
301   if (!isCandidate || Candidates.empty())
302     return false;
303 
304   llvm::append_range(PassThroughs, Candidates);
305   return true;
306 }
307 
308 void BPFAdjustOptImpl::adjustBasicBlock(BasicBlock &BB) {
309   if (!DisableBPFserializeICMP && serializeICMPCrossBB(BB))
310     return;
311 }
312 
313 void BPFAdjustOptImpl::adjustInst(Instruction &I) {
314   if (!DisableBPFserializeICMP && serializeICMPInBB(I))
315     return;
316   if (!DisableBPFavoidSpeculation && avoidSpeculation(I))
317     return;
318 }
319 
320 PreservedAnalyses BPFAdjustOptPass::run(Module &M, ModuleAnalysisManager &AM) {
321   return BPFAdjustOptImpl(&M).run() ? PreservedAnalyses::none()
322                                     : PreservedAnalyses::all();
323 }
324