llvm/lib/Target/BPF/BPFAdjustOpt.cpp

   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"
  24 #include "llvm/Transforms/Utils/BasicBlockUtils.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
  36 static cl::opt<bool> DisableBPFavoidSpeculation(
  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;
  67   SmallVector<PassThroughInfo, 16> PassThroughs;
  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) {
 100     auto *CI = BPFCoreSharedInfo::insertPassThrough(
 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
 174   BasicBlock *B1 = B2->getSinglePredecessor();
 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;
 251   SmallVector<PassThroughInfo, 4> Candidates;
 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
 324 PreservedAnalyses BPFAdjustOptPass::run(Module &M, ModuleAnalysisManager &AM) {
 325   return BPFAdjustOptImpl(&M).run() ? PreservedAnalyses::none()
 326                                     : PreservedAnalyses::all();
 327 }