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

source code of llvm/lib/Target/BPF/BPFMISimplifyPatchable.cpp