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