LLVM 22.0.0git
BPFMISimplifyPatchable.cpp
Go to the documentation of this file.
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"
38#include "llvm/Support/Debug.h"
39#include <set>
40
41using namespace llvm;
42
43#define DEBUG_TYPE "bpf-mi-simplify-patchable"
44
45namespace {
46
47struct BPFMISimplifyPatchable : public MachineFunctionPass {
48
49 static char ID;
50 const BPFInstrInfo *TII;
52
53 BPFMISimplifyPatchable() : MachineFunctionPass(ID) {}
54
55private:
56 std::set<MachineInstr *> SkipInsts;
57
58 // Initialize class variables.
59 void initialize(MachineFunction &MFParm);
60
61 bool isLoadInst(unsigned Opcode);
62 bool removeLD();
63 void processCandidate(MachineRegisterInfo *MRI, MachineBasicBlock &MBB,
64 MachineInstr &MI, Register &SrcReg, Register &DstReg,
65 const GlobalValue *GVal, bool IsAma);
66 void processDstReg(MachineRegisterInfo *MRI, Register &DstReg,
67 Register &SrcReg, const GlobalValue *GVal,
68 bool doSrcRegProp, bool IsAma);
69 void processInst(MachineRegisterInfo *MRI, MachineInstr *Inst,
70 MachineOperand *RelocOp, const GlobalValue *GVal);
71 void checkADDrr(MachineRegisterInfo *MRI, MachineOperand *RelocOp,
72 const GlobalValue *GVal);
74 MachineOperand *RelocOp, const GlobalValue *GVal,
75 unsigned Opcode);
76
77public:
78 // Main entry point for this pass.
79 bool runOnMachineFunction(MachineFunction &MF) override {
80 if (skipFunction(MF.getFunction()))
81 return false;
82
83 initialize(MF);
84 return removeLD();
85 }
86};
87
88// Initialize class variables.
89void BPFMISimplifyPatchable::initialize(MachineFunction &MFParm) {
90 MF = &MFParm;
91 TII = MF->getSubtarget<BPFSubtarget>().getInstrInfo();
92 LLVM_DEBUG(dbgs() << "*** BPF simplify patchable insts pass ***\n\n");
93}
94
95static bool isStoreImm(unsigned Opcode) {
96 return Opcode == BPF::STB_imm || Opcode == BPF::STH_imm ||
97 Opcode == BPF::STW_imm || Opcode == BPF::STD_imm;
98}
99
100static bool isStore32(unsigned Opcode) {
101 return Opcode == BPF::STB32 || Opcode == BPF::STH32 || Opcode == BPF::STW32 ||
102 Opcode == BPF::STBREL32 || Opcode == BPF::STHREL32 ||
103 Opcode == BPF::STWREL32;
104}
105
106static bool isStore64(unsigned Opcode) {
107 return Opcode == BPF::STB || Opcode == BPF::STH || Opcode == BPF::STW ||
108 Opcode == BPF::STD || Opcode == BPF::STDREL;
109}
110
111static bool isLoad32(unsigned Opcode) {
112 return Opcode == BPF::LDB32 || Opcode == BPF::LDH32 || Opcode == BPF::LDW32 ||
113 Opcode == BPF::LDBACQ32 || Opcode == BPF::LDHACQ32 ||
114 Opcode == BPF::LDWACQ32;
115}
116
117static bool isLoad64(unsigned Opcode) {
118 return Opcode == BPF::LDB || Opcode == BPF::LDH || Opcode == BPF::LDW ||
119 Opcode == BPF::LDD || Opcode == BPF::LDDACQ;
120}
121
122static bool isLoadSext(unsigned Opcode) {
123 return Opcode == BPF::LDBSX || Opcode == BPF::LDHSX || Opcode == BPF::LDWSX;
124}
125
126bool BPFMISimplifyPatchable::isLoadInst(unsigned Opcode) {
127 return isLoad32(Opcode) || isLoad64(Opcode) || isLoadSext(Opcode);
128}
129
130void BPFMISimplifyPatchable::checkADDrr(MachineRegisterInfo *MRI,
131 MachineOperand *RelocOp, const GlobalValue *GVal) {
132 const MachineInstr *Inst = RelocOp->getParent();
133 const MachineOperand *Op1 = &Inst->getOperand(1);
134 const MachineOperand *Op2 = &Inst->getOperand(2);
135 const MachineOperand *BaseOp = (RelocOp == Op1) ? Op2 : Op1;
136
137 // Go through all uses of %1 as in %1 = ADD_rr %2, %3
138 const MachineOperand Op0 = Inst->getOperand(0);
139 for (MachineOperand &MO :
140 llvm::make_early_inc_range(MRI->use_operands(Op0.getReg()))) {
141 // The candidate needs to have a unique definition.
142 if (!MRI->getUniqueVRegDef(MO.getReg()))
143 continue;
144
145 MachineInstr *DefInst = MO.getParent();
146 unsigned Opcode = DefInst->getOpcode();
147 unsigned COREOp;
148 if (isLoad64(Opcode) || isLoadSext(Opcode))
149 COREOp = BPF::CORE_LD64;
150 else if (isLoad32(Opcode))
151 COREOp = BPF::CORE_LD32;
152 else if (isStore64(Opcode) || isStore32(Opcode) || isStoreImm(Opcode))
153 COREOp = BPF::CORE_ST;
154 else
155 continue;
156
157 // It must be a form of %2 = *(type *)(%1 + 0) or *(type *)(%1 + 0) = %2.
158 const MachineOperand &ImmOp = DefInst->getOperand(2);
159 if (!ImmOp.isImm() || ImmOp.getImm() != 0)
160 continue;
161
162 // Reject the form:
163 // %1 = ADD_rr %2, %3
164 // *(type *)(%2 + 0) = %1
165 if (isStore64(Opcode) || isStore32(Opcode)) {
166 const MachineOperand &Opnd = DefInst->getOperand(0);
167 if (Opnd.isReg() && Opnd.getReg() == MO.getReg())
168 continue;
169 }
170
171 BuildMI(*DefInst->getParent(), *DefInst, DefInst->getDebugLoc(), TII->get(COREOp))
172 .add(DefInst->getOperand(0)).addImm(Opcode).add(*BaseOp)
173 .addGlobalAddress(GVal);
174 DefInst->eraseFromParent();
175 }
176}
177
178void BPFMISimplifyPatchable::checkShift(MachineRegisterInfo *MRI,
179 MachineBasicBlock &MBB, MachineOperand *RelocOp, const GlobalValue *GVal,
180 unsigned Opcode) {
181 // Relocation operand should be the operand #2.
182 MachineInstr *Inst = RelocOp->getParent();
183 if (RelocOp != &Inst->getOperand(2))
184 return;
185
186 BuildMI(MBB, *Inst, Inst->getDebugLoc(), TII->get(BPF::CORE_SHIFT))
187 .add(Inst->getOperand(0)).addImm(Opcode)
188 .add(Inst->getOperand(1)).addGlobalAddress(GVal);
189 Inst->eraseFromParent();
190}
191
192void BPFMISimplifyPatchable::processCandidate(MachineRegisterInfo *MRI,
194 Register &DstReg, const GlobalValue *GVal, bool IsAma) {
195 if (MRI->getRegClass(DstReg) == &BPF::GPR32RegClass) {
196 if (IsAma) {
197 // We can optimize such a pattern:
198 // %1:gpr = LD_imm64 @"llvm.s:0:4$0:2"
199 // %2:gpr32 = LDW32 %1:gpr, 0
200 // %3:gpr = SUBREG_TO_REG 0, %2:gpr32, %subreg.sub_32
201 // %4:gpr = ADD_rr %0:gpr, %3:gpr
202 // or similar patterns below for non-alu32 case.
203 auto Begin = MRI->use_begin(DstReg), End = MRI->use_end();
204 decltype(End) NextI;
205 for (auto I = Begin; I != End; I = NextI) {
206 NextI = std::next(I);
207 if (!MRI->getUniqueVRegDef(I->getReg()))
208 continue;
209
210 unsigned Opcode = I->getParent()->getOpcode();
211 if (Opcode == BPF::SUBREG_TO_REG) {
212 Register TmpReg = I->getParent()->getOperand(0).getReg();
213 processDstReg(MRI, TmpReg, DstReg, GVal, false, IsAma);
214 }
215 }
216 }
217
218 BuildMI(MBB, MI, MI.getDebugLoc(), TII->get(BPF::COPY), DstReg)
219 .addReg(SrcReg, 0, BPF::sub_32);
220 return;
221 }
222
223 // All uses of DstReg replaced by SrcReg
224 processDstReg(MRI, DstReg, SrcReg, GVal, true, IsAma);
225}
226
227void BPFMISimplifyPatchable::processDstReg(MachineRegisterInfo *MRI,
228 Register &DstReg, Register &SrcReg, const GlobalValue *GVal,
229 bool doSrcRegProp, bool IsAma) {
230 auto Begin = MRI->use_begin(DstReg), End = MRI->use_end();
231 decltype(End) NextI;
232 for (auto I = Begin; I != End; I = NextI) {
233 NextI = std::next(I);
234 if (doSrcRegProp) {
235 // In situations like below it is not known if usage is a kill
236 // after setReg():
237 //
238 // .-> %2:gpr = LD_imm64 @"llvm.t:0:0$0:0"
239 // |
240 // |`----------------.
241 // | %3:gpr = LDD %2:gpr, 0
242 // | %4:gpr = ADD_rr %0:gpr(tied-def 0), killed %3:gpr <--- (1)
243 // | %5:gpr = LDD killed %4:gpr, 0 ^^^^^^^^^^^^^
244 // | STD killed %5:gpr, %1:gpr, 0 this is I
245 // `----------------.
246 // %6:gpr = LDD %2:gpr, 0
247 // %7:gpr = ADD_rr %0:gpr(tied-def 0), killed %6:gpr <--- (2)
248 // %8:gpr = LDD killed %7:gpr, 0 ^^^^^^^^^^^^^
249 // STD killed %8:gpr, %1:gpr, 0 this is I
250 //
251 // Instructions (1) and (2) would be updated by setReg() to:
252 //
253 // ADD_rr %0:gpr(tied-def 0), %2:gpr
254 //
255 // %2:gpr is not killed at (1), so it is necessary to remove kill flag
256 // from I.
257 I->setReg(SrcReg);
258 I->setIsKill(false);
259 }
260
261 // The candidate needs to have a unique definition.
262 if (IsAma && MRI->getUniqueVRegDef(I->getReg()))
263 processInst(MRI, I->getParent(), &*I, GVal);
264 }
265}
266
267// Check to see whether we could do some optimization
268// to attach relocation to downstream dependent instructions.
269// Two kinds of patterns are recognized below:
270// Pattern 1:
271// %1 = LD_imm64 @"llvm.b:0:4$0:1" <== patch_imm = 4
272// %2 = LDD %1, 0 <== this insn will be removed
273// %3 = ADD_rr %0, %2
274// %4 = LDW[32] %3, 0 OR STW[32] %4, %3, 0
275// The `%4 = ...` will be transformed to
276// CORE_[ALU32_]MEM(%4, mem_opcode, %0, @"llvm.b:0:4$0:1")
277// and later on, BTF emit phase will translate to
278// %4 = LDW[32] %0, 4 STW[32] %4, %0, 4
279// and attach a relocation to it.
280// Pattern 2:
281// %15 = LD_imm64 @"llvm.t:5:63$0:2" <== relocation type 5
282// %16 = LDD %15, 0 <== this insn will be removed
283// %17 = SRA_rr %14, %16
284// The `%17 = ...` will be transformed to
285// %17 = CORE_SHIFT(SRA_ri, %14, @"llvm.t:5:63$0:2")
286// and later on, BTF emit phase will translate to
287// %r4 = SRA_ri %r4, 63
288void BPFMISimplifyPatchable::processInst(MachineRegisterInfo *MRI,
289 MachineInstr *Inst, MachineOperand *RelocOp, const GlobalValue *GVal) {
290 unsigned Opcode = Inst->getOpcode();
291 if (isLoadInst(Opcode)) {
292 SkipInsts.insert(Inst);
293 return;
294 }
295
296 if (Opcode == BPF::ADD_rr)
297 checkADDrr(MRI, RelocOp, GVal);
298 else if (Opcode == BPF::SLL_rr)
299 checkShift(MRI, *Inst->getParent(), RelocOp, GVal, BPF::SLL_ri);
300 else if (Opcode == BPF::SRA_rr)
301 checkShift(MRI, *Inst->getParent(), RelocOp, GVal, BPF::SRA_ri);
302 else if (Opcode == BPF::SRL_rr)
303 checkShift(MRI, *Inst->getParent(), RelocOp, GVal, BPF::SRL_ri);
304}
305
306/// Remove unneeded Load instructions.
307bool BPFMISimplifyPatchable::removeLD() {
309 MachineInstr *ToErase = nullptr;
310 bool Changed = false;
311
312 for (MachineBasicBlock &MBB : *MF) {
313 for (MachineInstr &MI : MBB) {
314 if (ToErase) {
315 ToErase->eraseFromParent();
316 ToErase = nullptr;
317 }
318
319 // Ensure the register format is LOAD <reg>, <reg>, 0
320 if (!isLoadInst(MI.getOpcode()))
321 continue;
322
323 if (SkipInsts.find(&MI) != SkipInsts.end())
324 continue;
325
326 if (!MI.getOperand(0).isReg() || !MI.getOperand(1).isReg())
327 continue;
328
329 if (!MI.getOperand(2).isImm() || MI.getOperand(2).getImm())
330 continue;
331
332 Register DstReg = MI.getOperand(0).getReg();
333 Register SrcReg = MI.getOperand(1).getReg();
334
335 MachineInstr *DefInst = MRI->getUniqueVRegDef(SrcReg);
336 if (!DefInst)
337 continue;
338
339 if (DefInst->getOpcode() != BPF::LD_imm64)
340 continue;
341
342 const MachineOperand &MO = DefInst->getOperand(1);
343 if (!MO.isGlobal())
344 continue;
345
346 const GlobalValue *GVal = MO.getGlobal();
347 auto *GVar = dyn_cast<GlobalVariable>(GVal);
348 if (!GVar)
349 continue;
350
351 // Global variables representing structure offset or type id.
352 bool IsAma = false;
353 if (GVar->hasAttribute(BPFCoreSharedInfo::AmaAttr))
354 IsAma = true;
355 else if (!GVar->hasAttribute(BPFCoreSharedInfo::TypeIdAttr))
356 continue;
357
358 processCandidate(MRI, MBB, MI, SrcReg, DstReg, GVal, IsAma);
359
360 ToErase = &MI;
361 Changed = true;
362 }
363 }
364
365 return Changed;
366}
367
368} // namespace
369
370INITIALIZE_PASS(BPFMISimplifyPatchable, DEBUG_TYPE,
371 "BPF PreEmit SimplifyPatchable", false, false)
372
373char BPFMISimplifyPatchable::ID = 0;
374FunctionPass *llvm::createBPFMISimplifyPatchablePass() {
375 return new BPFMISimplifyPatchable();
376}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
#define DEBUG_TYPE
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition MD5.cpp:58
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition PassSupport.h:56
#define LLVM_DEBUG(...)
Definition Debug.h:114
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringLiteral > StandardNames)
Initialize the set of available library functions based on the specified target triple.
static constexpr StringRef TypeIdAttr
The attribute attached to globals representing a type id.
Definition BPFCORE.h:48
static constexpr StringRef AmaAttr
The attribute attached to globals representing a field access.
Definition BPFCORE.h:46
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
const MachineInstrBuilder & add(const MachineOperand &MO) const
const MachineInstrBuilder & addGlobalAddress(const GlobalValue *GV, int64_t Offset=0, unsigned TargetFlags=0) const
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Representation of each machine instruction.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
const MachineBasicBlock * getParent() const
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
LLVM_ABI void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
const MachineOperand & getOperand(unsigned i) const
MachineOperand class - Representation of each machine instruction operand.
const GlobalValue * getGlobal() const
int64_t getImm() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
bool isGlobal() const
isGlobal - Tests if this is a MO_GlobalAddress operand.
Register getReg() const
getReg - Returns the register number.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Wrapper class representing virtual and physical registers.
Definition Register.h:19
Changed
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
FunctionPass * createBPFMISimplifyPatchablePass()
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:649
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition STLExtras.h:634
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:207