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