llvm/lib/Target/BPF/BPFMISimplifyPatchable.cpp

   1 //===----- BPFMISimplifyPatchable.cpp - MI Simplify Patchable Insts -------===//
   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 // This pass targets a subset of instructions like below
  10 //    ld_imm64 r1, @global
  11 //    ldd r2, r1, 0
  12 //    add r3, struct_base_reg, r2
  13 //
  14 // Here @global should represent an AMA (abstruct member access).
  15 // Such an access is subject to bpf load time patching. After this pass, the
  16 // code becomes
  17 //    ld_imm64 r1, @global
  18 //    add r3, struct_base_reg, r1
  19 //
  20 // Eventually, at BTF output stage, a relocation record will be generated
  21 // for ld_imm64 which should be replaced later by bpf loader:
  22 //    r1 = <calculated field_info>
  23 //    add r3, struct_base_reg, r1
  24 //
  25 // This pass also removes the intermediate load generated in IR pass for
  26 // __builtin_btf_type_id() intrinsic.
  27 //
  28 //===----------------------------------------------------------------------===//
  29
  30 #include "BPF.h"
  31 #include "BPFCORE.h"
  32 #include "BPFInstrInfo.h"
  33 #include "BPFTargetMachine.h"
  34 #include "llvm/CodeGen/MachineFunctionPass.h"
  35 #include "llvm/CodeGen/MachineInstrBuilder.h"
  36 #include "llvm/CodeGen/MachineRegisterInfo.h"
  37 #include "llvm/IR/GlobalVariable.h"
  38 #include "llvm/Support/Debug.h"
  39 #include <set>
  40
  41 using namespace llvm;
  42
  43 #define DEBUG_TYPE "bpf-mi-simplify-patchable"
  44
  45 namespace {
  46
  47 struct BPFMISimplifyPatchable : public MachineFunctionPass {
  48
  49   static char ID;
  50   const BPFInstrInfo *TII;
  51   MachineFunction *MF;
  52
  53   BPFMISimplifyPatchable() : MachineFunctionPass(ID) {
  54     initializeBPFMISimplifyPatchablePass(*PassRegistry::getPassRegistry());
  55   }
  56
  57 private:
  58   std::set<MachineInstr *> SkipInsts;
  59
  60   // Initialize class variables.
  61   void initialize(MachineFunction &MFParm);
  62
  63   bool isLoadInst(unsigned Opcode);
  64   bool removeLD();
  65   void processCandidate(MachineRegisterInfo *MRI, MachineBasicBlock &MBB,
  66                         MachineInstr &MI, Register &SrcReg, Register &DstReg,
  67                         const GlobalValue *GVal, bool IsAma);
  68   void processDstReg(MachineRegisterInfo *MRI, Register &DstReg,
  69                      Register &SrcReg, const GlobalValue *GVal,
  70                      bool doSrcRegProp, bool IsAma);
  71   void processInst(MachineRegisterInfo *MRI, MachineInstr *Inst,
  72                    MachineOperand *RelocOp, const GlobalValue *GVal);
  73   void checkADDrr(MachineRegisterInfo *MRI, MachineOperand *RelocOp,
  74                   const GlobalValue *GVal);
  75   void checkShift(MachineRegisterInfo *MRI, MachineBasicBlock &MBB,
  76                   MachineOperand *RelocOp, const GlobalValue *GVal,
  77                   unsigned Opcode);
  78
  79 public:
  80   // Main entry point for this pass.
  81   bool runOnMachineFunction(MachineFunction &MF) override {
  82     if (skipFunction(MF.getFunction()))
  83       return false;
  84
  85     initialize(MF);
  86     return removeLD();
  87   }
  88 };
  89
  90 // Initialize class variables.
  91 void BPFMISimplifyPatchable::initialize(MachineFunction &MFParm) {
  92   MF = &MFParm;
  93   TII = MF->getSubtarget<BPFSubtarget>().getInstrInfo();
  94   LLVM_DEBUG(dbgs() << "*** BPF simplify patchable insts pass ***\n\n");
  95 }
  96
  97 static bool isST(unsigned Opcode) {
  98   return Opcode == BPF::STB_imm || Opcode == BPF::STH_imm ||
  99          Opcode == BPF::STW_imm || Opcode == BPF::STD_imm;
 100 }
 101
 102 static bool isSTX32(unsigned Opcode) {
 103   return Opcode == BPF::STB32 || Opcode == BPF::STH32 || Opcode == BPF::STW32;
 104 }
 105
 106 static bool isSTX64(unsigned Opcode) {
 107   return Opcode == BPF::STB || Opcode == BPF::STH || Opcode == BPF::STW ||
 108          Opcode == BPF::STD;
 109 }
 110
 111 static bool isLDX32(unsigned Opcode) {
 112   return Opcode == BPF::LDB32 || Opcode == BPF::LDH32 || Opcode == BPF::LDW32;
 113 }
 114
 115 static bool isLDX64(unsigned Opcode) {
 116   return Opcode == BPF::LDB || Opcode == BPF::LDH || Opcode == BPF::LDW ||
 117          Opcode == BPF::LDD;
 118 }
 119
 120 static bool isLDSX(unsigned Opcode) {
 121   return Opcode == BPF::LDBSX || Opcode == BPF::LDHSX || Opcode == BPF::LDWSX;
 122 }
 123
 124 bool BPFMISimplifyPatchable::isLoadInst(unsigned Opcode) {
 125   return isLDX32(Opcode) || isLDX64(Opcode) || isLDSX(Opcode);
 126 }
 127
 128 void BPFMISimplifyPatchable::checkADDrr(MachineRegisterInfo *MRI,
 129     MachineOperand *RelocOp, const GlobalValue *GVal) {
 130   const MachineInstr *Inst = RelocOp->getParent();
 131   const MachineOperand *Op1 = &Inst->getOperand(1);
 132   const MachineOperand *Op2 = &Inst->getOperand(2);
 133   const MachineOperand *BaseOp = (RelocOp == Op1) ? Op2 : Op1;
 134
 135   // Go through all uses of %1 as in %1 = ADD_rr %2, %3
 136   const MachineOperand Op0 = Inst->getOperand(0);
 137   for (MachineOperand &MO :
 138        llvm::make_early_inc_range(MRI->use_operands(Op0.getReg()))) {
 139     // The candidate needs to have a unique definition.
 140     if (!MRI->getUniqueVRegDef(MO.getReg()))
 141       continue;
 142
 143     MachineInstr *DefInst = MO.getParent();
 144     unsigned Opcode = DefInst->getOpcode();
 145     unsigned COREOp;
 146     if (isLDX64(Opcode) || isLDSX(Opcode))
 147       COREOp = BPF::CORE_LD64;
 148     else if (isLDX32(Opcode))
 149       COREOp = BPF::CORE_LD32;
 150     else if (isSTX64(Opcode) || isSTX32(Opcode) || isST(Opcode))
 151       COREOp = BPF::CORE_ST;
 152     else
 153       continue;
 154
 155     // It must be a form of %2 = *(type *)(%1 + 0) or *(type *)(%1 + 0) = %2.
 156     const MachineOperand &ImmOp = DefInst->getOperand(2);
 157     if (!ImmOp.isImm() || ImmOp.getImm() != 0)
 158       continue;
 159
 160     // Reject the form:
 161     //   %1 = ADD_rr %2, %3
 162     //   *(type *)(%2 + 0) = %1
 163     if (isSTX64(Opcode) || isSTX32(Opcode)) {
 164       const MachineOperand &Opnd = DefInst->getOperand(0);
 165       if (Opnd.isReg() && Opnd.getReg() == MO.getReg())
 166         continue;
 167     }
 168
 169     BuildMI(*DefInst->getParent(), *DefInst, DefInst->getDebugLoc(), TII->get(COREOp))
 170         .add(DefInst->getOperand(0)).addImm(Opcode).add(*BaseOp)
 171         .addGlobalAddress(GVal);
 172     DefInst->eraseFromParent();
 173   }
 174 }
 175
 176 void BPFMISimplifyPatchable::checkShift(MachineRegisterInfo *MRI,
 177     MachineBasicBlock &MBB, MachineOperand *RelocOp, const GlobalValue *GVal,
 178     unsigned Opcode) {
 179   // Relocation operand should be the operand #2.
 180   MachineInstr *Inst = RelocOp->getParent();
 181   if (RelocOp != &Inst->getOperand(2))
 182     return;
 183
 184   BuildMI(MBB, *Inst, Inst->getDebugLoc(), TII->get(BPF::CORE_SHIFT))
 185       .add(Inst->getOperand(0)).addImm(Opcode)
 186       .add(Inst->getOperand(1)).addGlobalAddress(GVal);
 187   Inst->eraseFromParent();
 188 }
 189
 190 void BPFMISimplifyPatchable::processCandidate(MachineRegisterInfo *MRI,
 191     MachineBasicBlock &MBB, MachineInstr &MI, Register &SrcReg,
 192     Register &DstReg, const GlobalValue *GVal, bool IsAma) {
 193   if (MRI->getRegClass(DstReg) == &BPF::GPR32RegClass) {
 194     if (IsAma) {
 195       // We can optimize such a pattern:
 196       //  %1:gpr = LD_imm64 @"llvm.s:0:4$0:2"
 197       //  %2:gpr32 = LDW32 %1:gpr, 0
 198       //  %3:gpr = SUBREG_TO_REG 0, %2:gpr32, %subreg.sub_32
 199       //  %4:gpr = ADD_rr %0:gpr, %3:gpr
 200       //  or similar patterns below for non-alu32 case.
 201       auto Begin = MRI->use_begin(DstReg), End = MRI->use_end();
 202       decltype(End) NextI;
 203       for (auto I = Begin; I != End; I = NextI) {
 204         NextI = std::next(I);
 205         if (!MRI->getUniqueVRegDef(I->getReg()))
 206           continue;
 207
 208         unsigned Opcode = I->getParent()->getOpcode();
 209         if (Opcode == BPF::SUBREG_TO_REG) {
 210           Register TmpReg = I->getParent()->getOperand(0).getReg();
 211           processDstReg(MRI, TmpReg, DstReg, GVal, false, IsAma);
 212         }
 213       }
 214     }
 215
 216     BuildMI(MBB, MI, MI.getDebugLoc(), TII->get(BPF::COPY), DstReg)
 217         .addReg(SrcReg, 0, BPF::sub_32);
 218     return;
 219   }
 220
 221   // All uses of DstReg replaced by SrcReg
 222   processDstReg(MRI, DstReg, SrcReg, GVal, true, IsAma);
 223 }
 224
 225 void BPFMISimplifyPatchable::processDstReg(MachineRegisterInfo *MRI,
 226     Register &DstReg, Register &SrcReg, const GlobalValue *GVal,
 227     bool doSrcRegProp, bool IsAma) {
 228   auto Begin = MRI->use_begin(DstReg), End = MRI->use_end();
 229   decltype(End) NextI;
 230   for (auto I = Begin; I != End; I = NextI) {
 231     NextI = std::next(I);
 232     if (doSrcRegProp) {
 233       // In situations like below it is not known if usage is a kill
 234       // after setReg():
 235       //
 236       // .-> %2:gpr = LD_imm64 @"llvm.t:0:0$0:0"
 237       // |
 238       // |`----------------.
 239       // |   %3:gpr = LDD %2:gpr, 0
 240       // |   %4:gpr = ADD_rr %0:gpr(tied-def 0), killed %3:gpr <--- (1)
 241       // |   %5:gpr = LDD killed %4:gpr, 0       ^^^^^^^^^^^^^
 242       // |   STD killed %5:gpr, %1:gpr, 0         this is I
 243       //  `----------------.
 244       //     %6:gpr = LDD %2:gpr, 0
 245       //     %7:gpr = ADD_rr %0:gpr(tied-def 0), killed %6:gpr <--- (2)
 246       //     %8:gpr = LDD killed %7:gpr, 0       ^^^^^^^^^^^^^
 247       //     STD killed %8:gpr, %1:gpr, 0         this is I
 248       //
 249       // Instructions (1) and (2) would be updated by setReg() to:
 250       //
 251       //     ADD_rr %0:gpr(tied-def 0), %2:gpr
 252       //
 253       // %2:gpr is not killed at (1), so it is necessary to remove kill flag
 254       // from I.
 255       I->setReg(SrcReg);
 256       I->setIsKill(false);
 257     }
 258
 259     // The candidate needs to have a unique definition.
 260     if (IsAma && MRI->getUniqueVRegDef(I->getReg()))
 261       processInst(MRI, I->getParent(), &*I, GVal);
 262   }
 263 }
 264
 265 // Check to see whether we could do some optimization
 266 // to attach relocation to downstream dependent instructions.
 267 // Two kinds of patterns are recognized below:
 268 // Pattern 1:
 269 //   %1 = LD_imm64 @"llvm.b:0:4$0:1"  <== patch_imm = 4
 270 //   %2 = LDD %1, 0  <== this insn will be removed
 271 //   %3 = ADD_rr %0, %2
 272 //   %4 = LDW[32] %3, 0 OR STW[32] %4, %3, 0
 273 //   The `%4 = ...` will be transformed to
 274 //      CORE_[ALU32_]MEM(%4, mem_opcode, %0, @"llvm.b:0:4$0:1")
 275 //   and later on, BTF emit phase will translate to
 276 //      %4 = LDW[32] %0, 4 STW[32] %4, %0, 4
 277 //   and attach a relocation to it.
 278 // Pattern 2:
 279 //    %15 = LD_imm64 @"llvm.t:5:63$0:2" <== relocation type 5
 280 //    %16 = LDD %15, 0   <== this insn will be removed
 281 //    %17 = SRA_rr %14, %16
 282 //    The `%17 = ...` will be transformed to
 283 //       %17 = CORE_SHIFT(SRA_ri, %14, @"llvm.t:5:63$0:2")
 284 //    and later on, BTF emit phase will translate to
 285 //       %r4 = SRA_ri %r4, 63
 286 void BPFMISimplifyPatchable::processInst(MachineRegisterInfo *MRI,
 287     MachineInstr *Inst, MachineOperand *RelocOp, const GlobalValue *GVal) {
 288   unsigned Opcode = Inst->getOpcode();
 289   if (isLoadInst(Opcode)) {
 290     SkipInsts.insert(Inst);
 291     return;
 292   }
 293
 294   if (Opcode == BPF::ADD_rr)
 295     checkADDrr(MRI, RelocOp, GVal);
 296   else if (Opcode == BPF::SLL_rr)
 297     checkShift(MRI, *Inst->getParent(), RelocOp, GVal, BPF::SLL_ri);
 298   else if (Opcode == BPF::SRA_rr)
 299     checkShift(MRI, *Inst->getParent(), RelocOp, GVal, BPF::SRA_ri);
 300   else if (Opcode == BPF::SRL_rr)
 301     checkShift(MRI, *Inst->getParent(), RelocOp, GVal, BPF::SRL_ri);
 302 }
 303
 304 /// Remove unneeded Load instructions.
 305 bool BPFMISimplifyPatchable::removeLD() {
 306   MachineRegisterInfo *MRI = &MF->getRegInfo();
 307   MachineInstr *ToErase = nullptr;
 308   bool Changed = false;
 309
 310   for (MachineBasicBlock &MBB : *MF) {
 311     for (MachineInstr &MI : MBB) {
 312       if (ToErase) {
 313         ToErase->eraseFromParent();
 314         ToErase = nullptr;
 315       }
 316
 317       // Ensure the register format is LOAD <reg>, <reg>, 0
 318       if (!isLoadInst(MI.getOpcode()))
 319         continue;
 320
 321       if (SkipInsts.find(&MI) != SkipInsts.end())
 322         continue;
 323
 324       if (!MI.getOperand(0).isReg() || !MI.getOperand(1).isReg())
 325         continue;
 326
 327       if (!MI.getOperand(2).isImm() || MI.getOperand(2).getImm())
 328         continue;
 329
 330       Register DstReg = MI.getOperand(0).getReg();
 331       Register SrcReg = MI.getOperand(1).getReg();
 332
 333       MachineInstr *DefInst = MRI->getUniqueVRegDef(SrcReg);
 334       if (!DefInst)
 335         continue;
 336
 337       if (DefInst->getOpcode() != BPF::LD_imm64)
 338         continue;
 339
 340       const MachineOperand &MO = DefInst->getOperand(1);
 341       if (!MO.isGlobal())
 342         continue;
 343
 344       const GlobalValue *GVal = MO.getGlobal();
 345       auto *GVar = dyn_cast<GlobalVariable>(GVal);
 346       if (!GVar)
 347         continue;
 348
 349       // Global variables representing structure offset or type id.
 350       bool IsAma = false;
 351       if (GVar->hasAttribute(BPFCoreSharedInfo::AmaAttr))
 352         IsAma = true;
 353       else if (!GVar->hasAttribute(BPFCoreSharedInfo::TypeIdAttr))
 354         continue;
 355
 356       processCandidate(MRI, MBB, MI, SrcReg, DstReg, GVal, IsAma);
 357
 358       ToErase = &MI;
 359       Changed = true;
 360     }
 361   }
 362
 363   return Changed;
 364 }
 365
 366 } // namespace
 367
 368 INITIALIZE_PASS(BPFMISimplifyPatchable, DEBUG_TYPE,
 369                 "BPF PreEmit SimplifyPatchable", false, false)
 370
 371 char BPFMISimplifyPatchable::ID = 0;
 372 FunctionPass *llvm::createBPFMISimplifyPatchablePass() {
 373   return new BPFMISimplifyPatchable();
 374 }