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