1351278Sdim//===----- BPFMISimplifyPatchable.cpp - MI Simplify Patchable Insts -------===// 2351278Sdim// 3351278Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4351278Sdim// See https://llvm.org/LICENSE.txt for license information. 5351278Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6351278Sdim// 7351278Sdim//===----------------------------------------------------------------------===// 8351278Sdim// 9351278Sdim// This pass targets a subset of instructions like below 10351278Sdim// ld_imm64 r1, @global 11351278Sdim// ldd r2, r1, 0 12351278Sdim// add r3, struct_base_reg, r2 13351278Sdim// 14360784Sdim// Here @global should represent an AMA (abstruct member access). 15360784Sdim// Such an access is subject to bpf load time patching. After this pass, the 16351278Sdim// code becomes 17351278Sdim// ld_imm64 r1, @global 18351278Sdim// add r3, struct_base_reg, r1 19351278Sdim// 20351278Sdim// Eventually, at BTF output stage, a relocation record will be generated 21351278Sdim// for ld_imm64 which should be replaced later by bpf loader: 22360784Sdim// r1 = <calculated field_info> 23351278Sdim// add r3, struct_base_reg, r1 24351278Sdim// 25351278Sdim//===----------------------------------------------------------------------===// 26351278Sdim 27351278Sdim#include "BPF.h" 28351278Sdim#include "BPFCORE.h" 29351278Sdim#include "BPFInstrInfo.h" 30351278Sdim#include "BPFTargetMachine.h" 31351278Sdim#include "llvm/CodeGen/MachineInstrBuilder.h" 32351278Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 33360784Sdim#include "llvm/Support/Debug.h" 34351278Sdim 35351278Sdimusing namespace llvm; 36351278Sdim 37351278Sdim#define DEBUG_TYPE "bpf-mi-simplify-patchable" 38351278Sdim 39351278Sdimnamespace { 40351278Sdim 41351278Sdimstruct BPFMISimplifyPatchable : public MachineFunctionPass { 42351278Sdim 43351278Sdim static char ID; 44351278Sdim const BPFInstrInfo *TII; 45351278Sdim MachineFunction *MF; 46351278Sdim 47351278Sdim BPFMISimplifyPatchable() : MachineFunctionPass(ID) { 48351278Sdim initializeBPFMISimplifyPatchablePass(*PassRegistry::getPassRegistry()); 49351278Sdim } 50351278Sdim 51351278Sdimprivate: 52351278Sdim // Initialize class variables. 53351278Sdim void initialize(MachineFunction &MFParm); 54351278Sdim 55351278Sdim bool removeLD(void); 56360784Sdim void processCandidate(MachineRegisterInfo *MRI, MachineBasicBlock &MBB, 57360784Sdim MachineInstr &MI, Register &SrcReg, Register &DstReg, 58360784Sdim const GlobalValue *GVal); 59360784Sdim void processDstReg(MachineRegisterInfo *MRI, Register &DstReg, 60360784Sdim Register &SrcReg, const GlobalValue *GVal, 61360784Sdim bool doSrcRegProp); 62360784Sdim void processInst(MachineRegisterInfo *MRI, MachineInstr *Inst, 63360784Sdim MachineOperand *RelocOp, const GlobalValue *GVal); 64360784Sdim void checkADDrr(MachineRegisterInfo *MRI, MachineOperand *RelocOp, 65360784Sdim const GlobalValue *GVal); 66360784Sdim void checkShift(MachineRegisterInfo *MRI, MachineBasicBlock &MBB, 67360784Sdim MachineOperand *RelocOp, const GlobalValue *GVal, 68360784Sdim unsigned Opcode); 69351278Sdim 70351278Sdimpublic: 71351278Sdim // Main entry point for this pass. 72351278Sdim bool runOnMachineFunction(MachineFunction &MF) override { 73360784Sdim if (skipFunction(MF.getFunction())) 74360784Sdim return false; 75360784Sdim 76360784Sdim initialize(MF); 77351278Sdim return removeLD(); 78351278Sdim } 79351278Sdim}; 80351278Sdim 81351278Sdim// Initialize class variables. 82351278Sdimvoid BPFMISimplifyPatchable::initialize(MachineFunction &MFParm) { 83351278Sdim MF = &MFParm; 84351278Sdim TII = MF->getSubtarget<BPFSubtarget>().getInstrInfo(); 85351278Sdim LLVM_DEBUG(dbgs() << "*** BPF simplify patchable insts pass ***\n\n"); 86351278Sdim} 87351278Sdim 88360784Sdimvoid BPFMISimplifyPatchable::checkADDrr(MachineRegisterInfo *MRI, 89360784Sdim MachineOperand *RelocOp, const GlobalValue *GVal) { 90360784Sdim const MachineInstr *Inst = RelocOp->getParent(); 91360784Sdim const MachineOperand *Op1 = &Inst->getOperand(1); 92360784Sdim const MachineOperand *Op2 = &Inst->getOperand(2); 93360784Sdim const MachineOperand *BaseOp = (RelocOp == Op1) ? Op2 : Op1; 94360784Sdim 95360784Sdim // Go through all uses of %1 as in %1 = ADD_rr %2, %3 96360784Sdim const MachineOperand Op0 = Inst->getOperand(0); 97360784Sdim auto Begin = MRI->use_begin(Op0.getReg()), End = MRI->use_end(); 98360784Sdim decltype(End) NextI; 99360784Sdim for (auto I = Begin; I != End; I = NextI) { 100360784Sdim NextI = std::next(I); 101360784Sdim // The candidate needs to have a unique definition. 102360784Sdim if (!MRI->getUniqueVRegDef(I->getReg())) 103360784Sdim continue; 104360784Sdim 105360784Sdim MachineInstr *DefInst = I->getParent(); 106360784Sdim unsigned Opcode = DefInst->getOpcode(); 107360784Sdim unsigned COREOp; 108360784Sdim if (Opcode == BPF::LDB || Opcode == BPF::LDH || Opcode == BPF::LDW || 109360784Sdim Opcode == BPF::LDD || Opcode == BPF::STB || Opcode == BPF::STH || 110360784Sdim Opcode == BPF::STW || Opcode == BPF::STD) 111360784Sdim COREOp = BPF::CORE_MEM; 112360784Sdim else if (Opcode == BPF::LDB32 || Opcode == BPF::LDH32 || 113360784Sdim Opcode == BPF::LDW32 || Opcode == BPF::STB32 || 114360784Sdim Opcode == BPF::STH32 || Opcode == BPF::STW32) 115360784Sdim COREOp = BPF::CORE_ALU32_MEM; 116360784Sdim else 117360784Sdim continue; 118360784Sdim 119363496Sdim // It must be a form of %2 = *(type *)(%1 + 0) or *(type *)(%1 + 0) = %2. 120360784Sdim const MachineOperand &ImmOp = DefInst->getOperand(2); 121360784Sdim if (!ImmOp.isImm() || ImmOp.getImm() != 0) 122360784Sdim continue; 123360784Sdim 124363496Sdim // Reject the form: 125363496Sdim // %1 = ADD_rr %2, %3 126363496Sdim // *(type *)(%2 + 0) = %1 127363496Sdim if (Opcode == BPF::STB || Opcode == BPF::STH || Opcode == BPF::STW || 128363496Sdim Opcode == BPF::STD || Opcode == BPF::STB32 || Opcode == BPF::STH32 || 129363496Sdim Opcode == BPF::STW32) { 130363496Sdim const MachineOperand &Opnd = DefInst->getOperand(0); 131363496Sdim if (Opnd.isReg() && Opnd.getReg() == I->getReg()) 132363496Sdim continue; 133363496Sdim } 134363496Sdim 135360784Sdim BuildMI(*DefInst->getParent(), *DefInst, DefInst->getDebugLoc(), TII->get(COREOp)) 136360784Sdim .add(DefInst->getOperand(0)).addImm(Opcode).add(*BaseOp) 137360784Sdim .addGlobalAddress(GVal); 138360784Sdim DefInst->eraseFromParent(); 139360784Sdim } 140360784Sdim} 141360784Sdim 142360784Sdimvoid BPFMISimplifyPatchable::checkShift(MachineRegisterInfo *MRI, 143360784Sdim MachineBasicBlock &MBB, MachineOperand *RelocOp, const GlobalValue *GVal, 144360784Sdim unsigned Opcode) { 145360784Sdim // Relocation operand should be the operand #2. 146360784Sdim MachineInstr *Inst = RelocOp->getParent(); 147360784Sdim if (RelocOp != &Inst->getOperand(2)) 148360784Sdim return; 149360784Sdim 150360784Sdim BuildMI(MBB, *Inst, Inst->getDebugLoc(), TII->get(BPF::CORE_SHIFT)) 151360784Sdim .add(Inst->getOperand(0)).addImm(Opcode) 152360784Sdim .add(Inst->getOperand(1)).addGlobalAddress(GVal); 153360784Sdim Inst->eraseFromParent(); 154360784Sdim} 155360784Sdim 156360784Sdimvoid BPFMISimplifyPatchable::processCandidate(MachineRegisterInfo *MRI, 157360784Sdim MachineBasicBlock &MBB, MachineInstr &MI, Register &SrcReg, 158360784Sdim Register &DstReg, const GlobalValue *GVal) { 159360784Sdim if (MRI->getRegClass(DstReg) == &BPF::GPR32RegClass) { 160360784Sdim // We can optimize such a pattern: 161360784Sdim // %1:gpr = LD_imm64 @"llvm.s:0:4$0:2" 162360784Sdim // %2:gpr32 = LDW32 %1:gpr, 0 163360784Sdim // %3:gpr = SUBREG_TO_REG 0, %2:gpr32, %subreg.sub_32 164360784Sdim // %4:gpr = ADD_rr %0:gpr, %3:gpr 165360784Sdim // or similar patterns below for non-alu32 case. 166360784Sdim auto Begin = MRI->use_begin(DstReg), End = MRI->use_end(); 167360784Sdim decltype(End) NextI; 168360784Sdim for (auto I = Begin; I != End; I = NextI) { 169360784Sdim NextI = std::next(I); 170360784Sdim if (!MRI->getUniqueVRegDef(I->getReg())) 171360784Sdim continue; 172360784Sdim 173360784Sdim unsigned Opcode = I->getParent()->getOpcode(); 174360784Sdim if (Opcode == BPF::SUBREG_TO_REG) { 175360784Sdim Register TmpReg = I->getParent()->getOperand(0).getReg(); 176360784Sdim processDstReg(MRI, TmpReg, DstReg, GVal, false); 177360784Sdim } 178360784Sdim } 179360784Sdim 180360784Sdim BuildMI(MBB, MI, MI.getDebugLoc(), TII->get(BPF::COPY), DstReg) 181360784Sdim .addReg(SrcReg, 0, BPF::sub_32); 182360784Sdim return; 183360784Sdim } 184360784Sdim 185360784Sdim // All uses of DstReg replaced by SrcReg 186360784Sdim processDstReg(MRI, DstReg, SrcReg, GVal, true); 187360784Sdim} 188360784Sdim 189360784Sdimvoid BPFMISimplifyPatchable::processDstReg(MachineRegisterInfo *MRI, 190360784Sdim Register &DstReg, Register &SrcReg, const GlobalValue *GVal, 191360784Sdim bool doSrcRegProp) { 192360784Sdim auto Begin = MRI->use_begin(DstReg), End = MRI->use_end(); 193360784Sdim decltype(End) NextI; 194360784Sdim for (auto I = Begin; I != End; I = NextI) { 195360784Sdim NextI = std::next(I); 196360784Sdim if (doSrcRegProp) 197360784Sdim I->setReg(SrcReg); 198360784Sdim 199360784Sdim // The candidate needs to have a unique definition. 200360784Sdim if (MRI->getUniqueVRegDef(I->getReg())) 201360784Sdim processInst(MRI, I->getParent(), &*I, GVal); 202360784Sdim } 203360784Sdim} 204360784Sdim 205360784Sdim// Check to see whether we could do some optimization 206360784Sdim// to attach relocation to downstream dependent instructions. 207360784Sdim// Two kinds of patterns are recognized below: 208360784Sdim// Pattern 1: 209360784Sdim// %1 = LD_imm64 @"llvm.b:0:4$0:1" <== patch_imm = 4 210360784Sdim// %2 = LDD %1, 0 <== this insn will be removed 211360784Sdim// %3 = ADD_rr %0, %2 212360784Sdim// %4 = LDW[32] %3, 0 OR STW[32] %4, %3, 0 213360784Sdim// The `%4 = ...` will be transformed to 214360784Sdim// CORE_[ALU32_]MEM(%4, mem_opcode, %0, @"llvm.b:0:4$0:1") 215360784Sdim// and later on, BTF emit phase will translate to 216360784Sdim// %4 = LDW[32] %0, 4 STW[32] %4, %0, 4 217360784Sdim// and attach a relocation to it. 218360784Sdim// Pattern 2: 219360784Sdim// %15 = LD_imm64 @"llvm.t:5:63$0:2" <== relocation type 5 220360784Sdim// %16 = LDD %15, 0 <== this insn will be removed 221360784Sdim// %17 = SRA_rr %14, %16 222360784Sdim// The `%17 = ...` will be transformed to 223360784Sdim// %17 = CORE_SHIFT(SRA_ri, %14, @"llvm.t:5:63$0:2") 224360784Sdim// and later on, BTF emit phase will translate to 225360784Sdim// %r4 = SRA_ri %r4, 63 226360784Sdimvoid BPFMISimplifyPatchable::processInst(MachineRegisterInfo *MRI, 227360784Sdim MachineInstr *Inst, MachineOperand *RelocOp, const GlobalValue *GVal) { 228360784Sdim unsigned Opcode = Inst->getOpcode(); 229360784Sdim if (Opcode == BPF::ADD_rr) 230360784Sdim checkADDrr(MRI, RelocOp, GVal); 231360784Sdim else if (Opcode == BPF::SLL_rr) 232360784Sdim checkShift(MRI, *Inst->getParent(), RelocOp, GVal, BPF::SLL_ri); 233360784Sdim else if (Opcode == BPF::SRA_rr) 234360784Sdim checkShift(MRI, *Inst->getParent(), RelocOp, GVal, BPF::SRA_ri); 235360784Sdim else if (Opcode == BPF::SRL_rr) 236360784Sdim checkShift(MRI, *Inst->getParent(), RelocOp, GVal, BPF::SRL_ri); 237360784Sdim} 238360784Sdim 239351278Sdim/// Remove unneeded Load instructions. 240351278Sdimbool BPFMISimplifyPatchable::removeLD() { 241351278Sdim MachineRegisterInfo *MRI = &MF->getRegInfo(); 242351278Sdim MachineInstr *ToErase = nullptr; 243351278Sdim bool Changed = false; 244351278Sdim 245351278Sdim for (MachineBasicBlock &MBB : *MF) { 246351278Sdim for (MachineInstr &MI : MBB) { 247351278Sdim if (ToErase) { 248351278Sdim ToErase->eraseFromParent(); 249351278Sdim ToErase = nullptr; 250351278Sdim } 251351278Sdim 252351278Sdim // Ensure the register format is LOAD <reg>, <reg>, 0 253351278Sdim if (MI.getOpcode() != BPF::LDD && MI.getOpcode() != BPF::LDW && 254351278Sdim MI.getOpcode() != BPF::LDH && MI.getOpcode() != BPF::LDB && 255351278Sdim MI.getOpcode() != BPF::LDW32 && MI.getOpcode() != BPF::LDH32 && 256351278Sdim MI.getOpcode() != BPF::LDB32) 257351278Sdim continue; 258351278Sdim 259351278Sdim if (!MI.getOperand(0).isReg() || !MI.getOperand(1).isReg()) 260351278Sdim continue; 261351278Sdim 262351278Sdim if (!MI.getOperand(2).isImm() || MI.getOperand(2).getImm()) 263351278Sdim continue; 264351278Sdim 265360784Sdim Register DstReg = MI.getOperand(0).getReg(); 266360784Sdim Register SrcReg = MI.getOperand(1).getReg(); 267351278Sdim 268351278Sdim MachineInstr *DefInst = MRI->getUniqueVRegDef(SrcReg); 269351278Sdim if (!DefInst) 270351278Sdim continue; 271351278Sdim 272351278Sdim bool IsCandidate = false; 273360784Sdim const GlobalValue *GVal = nullptr; 274351278Sdim if (DefInst->getOpcode() == BPF::LD_imm64) { 275351278Sdim const MachineOperand &MO = DefInst->getOperand(1); 276351278Sdim if (MO.isGlobal()) { 277360784Sdim GVal = MO.getGlobal(); 278351278Sdim auto *GVar = dyn_cast<GlobalVariable>(GVal); 279351278Sdim if (GVar) { 280351278Sdim // Global variables representing structure offset or 281351278Sdim // patchable extern globals. 282351278Sdim if (GVar->hasAttribute(BPFCoreSharedInfo::AmaAttr)) { 283360784Sdim assert(MI.getOperand(2).getImm() == 0); 284351278Sdim IsCandidate = true; 285351278Sdim } 286351278Sdim } 287351278Sdim } 288351278Sdim } 289351278Sdim 290351278Sdim if (!IsCandidate) 291351278Sdim continue; 292351278Sdim 293360784Sdim processCandidate(MRI, MBB, MI, SrcReg, DstReg, GVal); 294351278Sdim 295351278Sdim ToErase = &MI; 296351278Sdim Changed = true; 297351278Sdim } 298351278Sdim } 299351278Sdim 300351278Sdim return Changed; 301351278Sdim} 302351278Sdim 303351278Sdim} // namespace 304351278Sdim 305351278SdimINITIALIZE_PASS(BPFMISimplifyPatchable, DEBUG_TYPE, 306351278Sdim "BPF PreEmit SimplifyPatchable", false, false) 307351278Sdim 308351278Sdimchar BPFMISimplifyPatchable::ID = 0; 309351278SdimFunctionPass *llvm::createBPFMISimplifyPatchablePass() { 310351278Sdim return new BPFMISimplifyPatchable(); 311351278Sdim} 312