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