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/MachineFunctionAnalysisManager.h"
35#include "llvm/CodeGen/MachineFunctionPass.h"
36#include "llvm/CodeGen/MachineInstrBuilder.h"
37#include "llvm/CodeGen/MachinePassManager.h"
38#include "llvm/CodeGen/MachineRegisterInfo.h"
39#include "llvm/IR/Analysis.h"
40#include "llvm/IR/GlobalVariable.h"
41#include "llvm/Support/Debug.h"
42#include <set>
43
44using namespace llvm;
45
46#define DEBUG_TYPE "bpf-mi-simplify-patchable"
47
48static cl::opt<bool>
49 DisableCOREOptimization("disable-bpf-core-optimization", cl::Hidden,
50 cl::desc("Disable CORE relocation optimization"));
51
52namespace {
53
54struct BPFMISimplifyPatchableImpl {
55 const BPFInstrInfo *TII;
56 MachineFunction *MF;
57
58private:
59 std::set<MachineInstr *> SkipInsts;
60
61 // Initialize class variables.
62 void initialize(MachineFunction &MFParm);
63
64 bool isLoadInst(unsigned Opcode);
65 bool removeLD();
66 void processCandidate(MachineRegisterInfo *MRI, MachineBasicBlock &MBB,
67 MachineInstr &MI, Register &SrcReg, Register &DstReg,
68 const GlobalValue *GVal, bool IsAma);
69 void processDstReg(MachineRegisterInfo *MRI, Register &DstReg,
70 Register &SrcReg, const GlobalValue *GVal,
71 bool doSrcRegProp, bool IsAma);
72 void processInst(MachineRegisterInfo *MRI, MachineInstr *Inst,
73 unsigned RelocOpNo, const GlobalValue *GVal);
74 void checkADDrr(MachineRegisterInfo *MRI, MachineInstr *Inst,
75 unsigned RelocOpNo, const GlobalValue *GVal);
76 void checkShift(MachineRegisterInfo *MRI, MachineInstr *Inst,
77 unsigned RelocOpNo, const GlobalValue *GVal, unsigned Opcode);
78
79public:
80 // Main entry point for this pass.
81 bool runOnMachineFunction(MachineFunction &MF) {
82 initialize(MFParm&: MF);
83 return removeLD();
84 }
85};
86
87class BPFMISimplifyPatchableLegacy : public MachineFunctionPass {
88public:
89 static char ID;
90
91 BPFMISimplifyPatchableLegacy() : MachineFunctionPass(ID) {}
92
93 // Main entry point for this pass.
94 bool runOnMachineFunction(MachineFunction &MF) override;
95};
96
97// Initialize class variables.
98void BPFMISimplifyPatchableImpl::initialize(MachineFunction &MFParm) {
99 MF = &MFParm;
100 TII = MF->getSubtarget<BPFSubtarget>().getInstrInfo();
101 LLVM_DEBUG(dbgs() << "*** BPF simplify patchable insts pass ***\n\n");
102}
103
104static bool isStoreImm(unsigned Opcode) {
105 return Opcode == BPF::STB_imm || Opcode == BPF::STH_imm ||
106 Opcode == BPF::STW_imm || Opcode == BPF::STD_imm;
107}
108
109static bool isStore32(unsigned Opcode) {
110 return Opcode == BPF::STB32 || Opcode == BPF::STH32 || Opcode == BPF::STW32 ||
111 Opcode == BPF::STBREL32 || Opcode == BPF::STHREL32 ||
112 Opcode == BPF::STWREL32;
113}
114
115static bool isStore64(unsigned Opcode) {
116 return Opcode == BPF::STB || Opcode == BPF::STH || Opcode == BPF::STW ||
117 Opcode == BPF::STD || Opcode == BPF::STDREL;
118}
119
120static bool isLoad32(unsigned Opcode) {
121 return Opcode == BPF::LDB32 || Opcode == BPF::LDH32 || Opcode == BPF::LDW32 ||
122 Opcode == BPF::LDBACQ32 || Opcode == BPF::LDHACQ32 ||
123 Opcode == BPF::LDWACQ32;
124}
125
126static bool isLoad64(unsigned Opcode) {
127 return Opcode == BPF::LDB || Opcode == BPF::LDH || Opcode == BPF::LDW ||
128 Opcode == BPF::LDD || Opcode == BPF::LDDACQ;
129}
130
131static bool isLoadSext(unsigned Opcode) {
132 return Opcode == BPF::LDBSX || Opcode == BPF::LDHSX || Opcode == BPF::LDWSX;
133}
134
135bool BPFMISimplifyPatchableImpl::isLoadInst(unsigned Opcode) {
136 return isLoad32(Opcode) || isLoad64(Opcode) || isLoadSext(Opcode);
137}
138
139void BPFMISimplifyPatchableImpl::checkADDrr(MachineRegisterInfo *MRI,
140 MachineInstr *Inst,
141 unsigned RelocOpNo,
142 const GlobalValue *GVal) {
143 const MachineOperand *BaseOp = &Inst->getOperand(i: RelocOpNo == 1 ? 2 : 1);
144
145 // Go through all uses of %1 as in %1 = ADD_rr %2, %3
146 const MachineOperand Op0 = Inst->getOperand(i: 0);
147 for (MachineOperand &MO :
148 llvm::make_early_inc_range(Range: MRI->use_operands(Reg: Op0.getReg()))) {
149 // The candidate needs to have a unique definition.
150 if (!MRI->getUniqueVRegDef(Reg: MO.getReg()))
151 continue;
152
153 MachineInstr *DefInst = MO.getParent();
154 unsigned Opcode = DefInst->getOpcode();
155 unsigned COREOp;
156 if (isLoad64(Opcode) || isLoadSext(Opcode))
157 COREOp = BPF::CORE_LD64;
158 else if (isLoad32(Opcode))
159 COREOp = BPF::CORE_LD32;
160 else if (isStore64(Opcode) || isStore32(Opcode) || isStoreImm(Opcode))
161 COREOp = BPF::CORE_ST;
162 else
163 continue;
164
165 // It must be a form of %2 = *(type *)(%1 + 0) or *(type *)(%1 + 0) = %2.
166 const MachineOperand &ImmOp = DefInst->getOperand(i: 2);
167 if (!ImmOp.isImm() || ImmOp.getImm() != 0)
168 continue;
169
170 // Reject the form:
171 // %1 = ADD_rr %2, %3
172 // *(type *)(%2 + 0) = %1
173 if (isStore64(Opcode) || isStore32(Opcode)) {
174 const MachineOperand &Opnd = DefInst->getOperand(i: 0);
175 if (Opnd.isReg() && Opnd.getReg() == MO.getReg())
176 continue;
177 }
178
179 BuildMI(BB&: *DefInst->getParent(), I&: *DefInst, MIMD: DefInst->getDebugLoc(), MCID: TII->get(Opcode: COREOp))
180 .add(MO: DefInst->getOperand(i: 0)).addImm(Val: Opcode).add(MO: *BaseOp)
181 .addGlobalAddress(GV: GVal);
182 DefInst->eraseFromParent();
183 }
184}
185
186void BPFMISimplifyPatchableImpl::checkShift(MachineRegisterInfo *MRI,
187 MachineInstr *Inst,
188 unsigned RelocOpNo,
189 const GlobalValue *GVal,
190 unsigned Opcode) {
191 // Relocation operand should be the operand #2.
192 if (RelocOpNo != 2)
193 return;
194
195 BuildMI(BB&: *Inst->getParent(), I&: *Inst, MIMD: Inst->getDebugLoc(),
196 MCID: TII->get(Opcode: BPF::CORE_SHIFT))
197 .add(MO: Inst->getOperand(i: 0))
198 .addImm(Val: Opcode)
199 .add(MO: Inst->getOperand(i: 1))
200 .addGlobalAddress(GV: GVal);
201 Inst->eraseFromParent();
202}
203
204void BPFMISimplifyPatchableImpl::processCandidate(
205 MachineRegisterInfo *MRI, MachineBasicBlock &MBB, MachineInstr &MI,
206 Register &SrcReg, Register &DstReg, const GlobalValue *GVal, bool IsAma) {
207 if (MRI->getRegClass(Reg: DstReg) == &BPF::GPR32RegClass) {
208 if (IsAma) {
209 // We can optimize such a pattern:
210 // %1:gpr = LD_imm64 @"llvm.s:0:4$0:2"
211 // %2:gpr32 = LDW32 %1:gpr, 0
212 // %3:gpr = SUBREG_TO_REG %2:gpr32, %subreg.sub_32
213 // %4:gpr = ADD_rr %0:gpr, %3:gpr
214 // or similar patterns below for non-alu32 case.
215 auto Begin = MRI->use_begin(RegNo: DstReg), End = MRI->use_end();
216 decltype(End) NextI;
217 for (auto I = Begin; I != End; I = NextI) {
218 NextI = std::next(x: I);
219 if (!MRI->getUniqueVRegDef(Reg: I->getReg()))
220 continue;
221
222 unsigned Opcode = I->getParent()->getOpcode();
223 if (Opcode == BPF::SUBREG_TO_REG) {
224 Register TmpReg = I->getParent()->getOperand(i: 0).getReg();
225 processDstReg(MRI, DstReg&: TmpReg, SrcReg&: DstReg, GVal, doSrcRegProp: false, IsAma);
226 }
227 }
228 }
229
230 BuildMI(BB&: MBB, I&: MI, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: BPF::COPY), DestReg: DstReg)
231 .addReg(RegNo: SrcReg, Flags: {}, SubReg: BPF::sub_32);
232 return;
233 }
234
235 // All uses of DstReg replaced by SrcReg
236 processDstReg(MRI, DstReg, SrcReg, GVal, doSrcRegProp: true, IsAma);
237}
238
239void BPFMISimplifyPatchableImpl::processDstReg(MachineRegisterInfo *MRI,
240 Register &DstReg,
241 Register &SrcReg,
242 const GlobalValue *GVal,
243 bool doSrcRegProp, bool IsAma) {
244 auto Begin = MRI->use_begin(RegNo: DstReg), End = MRI->use_end();
245 decltype(End) NextI;
246 for (auto I = Begin; I != End; I = NextI) {
247 NextI = std::next(x: I);
248 if (doSrcRegProp) {
249 // In situations like below it is not known if usage is a kill
250 // after setReg():
251 //
252 // .-> %2:gpr = LD_imm64 @"llvm.t:0:0$0:0"
253 // |
254 // |`----------------.
255 // | %3:gpr = LDD %2:gpr, 0
256 // | %4:gpr = ADD_rr %0:gpr(tied-def 0), killed %3:gpr <--- (1)
257 // | %5:gpr = LDD killed %4:gpr, 0 ^^^^^^^^^^^^^
258 // | STD killed %5:gpr, %1:gpr, 0 this is I
259 // `----------------.
260 // %6:gpr = LDD %2:gpr, 0
261 // %7:gpr = ADD_rr %0:gpr(tied-def 0), killed %6:gpr <--- (2)
262 // %8:gpr = LDD killed %7:gpr, 0 ^^^^^^^^^^^^^
263 // STD killed %8:gpr, %1:gpr, 0 this is I
264 //
265 // Instructions (1) and (2) would be updated by setReg() to:
266 //
267 // ADD_rr %0:gpr(tied-def 0), %2:gpr
268 //
269 // %2:gpr is not killed at (1), so it is necessary to remove kill flag
270 // from I.
271 I->setReg(SrcReg);
272 I->setIsKill(false);
273 }
274
275 // The candidate needs to have a unique definition.
276 if (IsAma && MRI->getUniqueVRegDef(Reg: I->getReg()))
277 processInst(MRI, Inst: I->getParent(), RelocOpNo: I.getOperandNo(), GVal);
278 }
279}
280
281// Check to see whether we could do some optimization
282// to attach relocation to downstream dependent instructions.
283// Two kinds of patterns are recognized below:
284// Pattern 1:
285// %1 = LD_imm64 @"llvm.b:0:4$0:1" <== patch_imm = 4
286// %2 = LDD %1, 0 <== this insn will be removed
287// %3 = ADD_rr %0, %2
288// %4 = LDW[32] %3, 0 OR STW[32] %4, %3, 0
289// The `%4 = ...` will be transformed to
290// CORE_[ALU32_]MEM(%4, mem_opcode, %0, @"llvm.b:0:4$0:1")
291// and later on, BTF emit phase will translate to
292// %4 = LDW[32] %0, 4 STW[32] %4, %0, 4
293// and attach a relocation to it.
294// Pattern 2:
295// %15 = LD_imm64 @"llvm.t:5:63$0:2" <== relocation type 5
296// %16 = LDD %15, 0 <== this insn will be removed
297// %17 = SRA_rr %14, %16
298// The `%17 = ...` will be transformed to
299// %17 = CORE_SHIFT(SRA_ri, %14, @"llvm.t:5:63$0:2")
300// and later on, BTF emit phase will translate to
301// %r4 = SRA_ri %r4, 63
302void BPFMISimplifyPatchableImpl::processInst(MachineRegisterInfo *MRI,
303 MachineInstr *Inst,
304 unsigned RelocOpNo,
305 const GlobalValue *GVal) {
306 unsigned Opcode = Inst->getOpcode();
307 if (isLoadInst(Opcode)) {
308 SkipInsts.insert(x: Inst);
309 return;
310 }
311
312 if (DisableCOREOptimization)
313 return;
314
315 if (Opcode == BPF::ADD_rr) {
316 // If the struct offset is greater than INT16_MAX, skip optimization.
317 StringRef AccessPattern = GVal->getName();
318 size_t FirstDollar = AccessPattern.find_first_of(C: '$');
319 size_t FirstColon = AccessPattern.find_first_of(C: ':');
320 size_t SecondColon = AccessPattern.find_first_of(C: ':', From: FirstColon + 1);
321 StringRef PatchImmStr =
322 AccessPattern.substr(Start: SecondColon + 1, N: FirstDollar - SecondColon);
323 int PatchImm = std::stoll(str: std::string(PatchImmStr));
324 if (PatchImm <= INT16_MAX)
325 checkADDrr(MRI, Inst, RelocOpNo, GVal);
326 return;
327 }
328
329 if (Opcode == BPF::SLL_rr)
330 checkShift(MRI, Inst, RelocOpNo, GVal, Opcode: BPF::SLL_ri);
331 else if (Opcode == BPF::SRA_rr)
332 checkShift(MRI, Inst, RelocOpNo, GVal, Opcode: BPF::SRA_ri);
333 else if (Opcode == BPF::SRL_rr)
334 checkShift(MRI, Inst, RelocOpNo, GVal, Opcode: BPF::SRL_ri);
335}
336
337/// Remove unneeded Load instructions.
338bool BPFMISimplifyPatchableImpl::removeLD() {
339 MachineRegisterInfo *MRI = &MF->getRegInfo();
340 MachineInstr *ToErase = nullptr;
341 bool Changed = false;
342
343 for (MachineBasicBlock &MBB : *MF) {
344 for (MachineInstr &MI : MBB) {
345 if (ToErase) {
346 ToErase->eraseFromParent();
347 ToErase = nullptr;
348 }
349
350 // Ensure the register format is LOAD <reg>, <reg>, 0
351 if (!isLoadInst(Opcode: MI.getOpcode()))
352 continue;
353
354 if (SkipInsts.find(x: &MI) != SkipInsts.end())
355 continue;
356
357 if (!MI.getOperand(i: 0).isReg() || !MI.getOperand(i: 1).isReg())
358 continue;
359
360 if (!MI.getOperand(i: 2).isImm() || MI.getOperand(i: 2).getImm())
361 continue;
362
363 Register DstReg = MI.getOperand(i: 0).getReg();
364 Register SrcReg = MI.getOperand(i: 1).getReg();
365
366 MachineInstr *DefInst = MRI->getUniqueVRegDef(Reg: SrcReg);
367 if (!DefInst)
368 continue;
369
370 if (DefInst->getOpcode() != BPF::LD_imm64)
371 continue;
372
373 const MachineOperand &MO = DefInst->getOperand(i: 1);
374 if (!MO.isGlobal())
375 continue;
376
377 const GlobalValue *GVal = MO.getGlobal();
378 auto *GVar = dyn_cast<GlobalVariable>(Val: GVal);
379 if (!GVar)
380 continue;
381
382 // Global variables representing structure offset or type id.
383 bool IsAma = false;
384 if (GVar->hasAttribute(Kind: BPFCoreSharedInfo::AmaAttr))
385 IsAma = true;
386 else if (!GVar->hasAttribute(Kind: BPFCoreSharedInfo::TypeIdAttr))
387 continue;
388
389 processCandidate(MRI, MBB, MI, SrcReg, DstReg, GVal, IsAma);
390
391 ToErase = &MI;
392 Changed = true;
393 }
394 }
395
396 return Changed;
397}
398
399} // namespace
400
401INITIALIZE_PASS(BPFMISimplifyPatchableLegacy, DEBUG_TYPE,
402 "BPF PreEmit SimplifyPatchable", false, false)
403
404char BPFMISimplifyPatchableLegacy::ID = 0;
405FunctionPass *llvm::createBPFMISimplifyPatchableLegacyPass() {
406 return new BPFMISimplifyPatchableLegacy();
407}
408
409bool BPFMISimplifyPatchableLegacy::runOnMachineFunction(MachineFunction &MF) {
410 if (skipFunction(F: MF.getFunction()))
411 return false;
412
413 BPFMISimplifyPatchableImpl Impl;
414 return Impl.runOnMachineFunction(MF);
415}
416
417PreservedAnalyses
418BPFMISimplifyPatchablePass::run(MachineFunction &MF,
419 MachineFunctionAnalysisManager &MFAM) {
420 BPFMISimplifyPatchableImpl Impl;
421 return Impl.runOnMachineFunction(MF)
422 ? getMachineFunctionPassPreservedAnalyses()
423 .preserveSet<CFGAnalyses>()
424 : PreservedAnalyses::all();
425}
426