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
BPFMISimplifyPatchable__anon217b3e8c0111::BPFMISimplifyPatchable53 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.
runOnMachineFunction__anon217b3e8c0111::BPFMISimplifyPatchable81 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.
initialize(MachineFunction & MFParm)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
isST(unsigned Opcode)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
isSTX32(unsigned Opcode)102 static bool isSTX32(unsigned Opcode) {
103 return Opcode == BPF::STB32 || Opcode == BPF::STH32 || Opcode == BPF::STW32;
104 }
105
isSTX64(unsigned Opcode)106 static bool isSTX64(unsigned Opcode) {
107 return Opcode == BPF::STB || Opcode == BPF::STH || Opcode == BPF::STW ||
108 Opcode == BPF::STD;
109 }
110
isLDX32(unsigned Opcode)111 static bool isLDX32(unsigned Opcode) {
112 return Opcode == BPF::LDB32 || Opcode == BPF::LDH32 || Opcode == BPF::LDW32;
113 }
114
isLDX64(unsigned Opcode)115 static bool isLDX64(unsigned Opcode) {
116 return Opcode == BPF::LDB || Opcode == BPF::LDH || Opcode == BPF::LDW ||
117 Opcode == BPF::LDD;
118 }
119
isLDSX(unsigned Opcode)120 static bool isLDSX(unsigned Opcode) {
121 return Opcode == BPF::LDBSX || Opcode == BPF::LDHSX || Opcode == BPF::LDWSX;
122 }
123
isLoadInst(unsigned Opcode)124 bool BPFMISimplifyPatchable::isLoadInst(unsigned Opcode) {
125 return isLDX32(Opcode) || isLDX64(Opcode) || isLDSX(Opcode);
126 }
127
checkADDrr(MachineRegisterInfo * MRI,MachineOperand * RelocOp,const GlobalValue * GVal)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
checkShift(MachineRegisterInfo * MRI,MachineBasicBlock & MBB,MachineOperand * RelocOp,const GlobalValue * GVal,unsigned Opcode)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
processCandidate(MachineRegisterInfo * MRI,MachineBasicBlock & MBB,MachineInstr & MI,Register & SrcReg,Register & DstReg,const GlobalValue * GVal,bool IsAma)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
processDstReg(MachineRegisterInfo * MRI,Register & DstReg,Register & SrcReg,const GlobalValue * GVal,bool doSrcRegProp,bool IsAma)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
processInst(MachineRegisterInfo * MRI,MachineInstr * Inst,MachineOperand * RelocOp,const GlobalValue * GVal)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.
removeLD()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;
createBPFMISimplifyPatchablePass()372 FunctionPass *llvm::createBPFMISimplifyPatchablePass() {
373 return new BPFMISimplifyPatchable();
374 }
375