LLVM  15.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"
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) {
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.
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 :
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,
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  I->setReg(SrcReg);
212 
213  // The candidate needs to have a unique definition.
214  if (IsAma && MRI->getUniqueVRegDef(I->getReg()))
215  processInst(MRI, I->getParent(), &*I, GVal);
216  }
217 }
218 
219 // Check to see whether we could do some optimization
220 // to attach relocation to downstream dependent instructions.
221 // Two kinds of patterns are recognized below:
222 // Pattern 1:
223 // %1 = LD_imm64 @"llvm.b:0:4$0:1" <== patch_imm = 4
224 // %2 = LDD %1, 0 <== this insn will be removed
225 // %3 = ADD_rr %0, %2
226 // %4 = LDW[32] %3, 0 OR STW[32] %4, %3, 0
227 // The `%4 = ...` will be transformed to
228 // CORE_[ALU32_]MEM(%4, mem_opcode, %0, @"llvm.b:0:4$0:1")
229 // and later on, BTF emit phase will translate to
230 // %4 = LDW[32] %0, 4 STW[32] %4, %0, 4
231 // and attach a relocation to it.
232 // Pattern 2:
233 // %15 = LD_imm64 @"llvm.t:5:63$0:2" <== relocation type 5
234 // %16 = LDD %15, 0 <== this insn will be removed
235 // %17 = SRA_rr %14, %16
236 // The `%17 = ...` will be transformed to
237 // %17 = CORE_SHIFT(SRA_ri, %14, @"llvm.t:5:63$0:2")
238 // and later on, BTF emit phase will translate to
239 // %r4 = SRA_ri %r4, 63
240 void BPFMISimplifyPatchable::processInst(MachineRegisterInfo *MRI,
241  MachineInstr *Inst, MachineOperand *RelocOp, const GlobalValue *GVal) {
242  unsigned Opcode = Inst->getOpcode();
243  if (isLoadInst(Opcode)) {
244  SkipInsts.insert(Inst);
245  return;
246  }
247 
248  if (Opcode == BPF::ADD_rr)
249  checkADDrr(MRI, RelocOp, GVal);
250  else if (Opcode == BPF::SLL_rr)
251  checkShift(MRI, *Inst->getParent(), RelocOp, GVal, BPF::SLL_ri);
252  else if (Opcode == BPF::SRA_rr)
253  checkShift(MRI, *Inst->getParent(), RelocOp, GVal, BPF::SRA_ri);
254  else if (Opcode == BPF::SRL_rr)
255  checkShift(MRI, *Inst->getParent(), RelocOp, GVal, BPF::SRL_ri);
256 }
257 
258 /// Remove unneeded Load instructions.
259 bool BPFMISimplifyPatchable::removeLD() {
260  MachineRegisterInfo *MRI = &MF->getRegInfo();
261  MachineInstr *ToErase = nullptr;
262  bool Changed = false;
263 
264  for (MachineBasicBlock &MBB : *MF) {
265  for (MachineInstr &MI : MBB) {
266  if (ToErase) {
267  ToErase->eraseFromParent();
268  ToErase = nullptr;
269  }
270 
271  // Ensure the register format is LOAD <reg>, <reg>, 0
272  if (!isLoadInst(MI.getOpcode()))
273  continue;
274 
275  if (SkipInsts.find(&MI) != SkipInsts.end())
276  continue;
277 
278  if (!MI.getOperand(0).isReg() || !MI.getOperand(1).isReg())
279  continue;
280 
281  if (!MI.getOperand(2).isImm() || MI.getOperand(2).getImm())
282  continue;
283 
284  Register DstReg = MI.getOperand(0).getReg();
285  Register SrcReg = MI.getOperand(1).getReg();
286 
287  MachineInstr *DefInst = MRI->getUniqueVRegDef(SrcReg);
288  if (!DefInst)
289  continue;
290 
291  if (DefInst->getOpcode() != BPF::LD_imm64)
292  continue;
293 
294  const MachineOperand &MO = DefInst->getOperand(1);
295  if (!MO.isGlobal())
296  continue;
297 
298  const GlobalValue *GVal = MO.getGlobal();
299  auto *GVar = dyn_cast<GlobalVariable>(GVal);
300  if (!GVar)
301  continue;
302 
303  // Global variables representing structure offset or type id.
304  bool IsAma = false;
305  if (GVar->hasAttribute(BPFCoreSharedInfo::AmaAttr))
306  IsAma = true;
307  else if (!GVar->hasAttribute(BPFCoreSharedInfo::TypeIdAttr))
308  continue;
309 
310  processCandidate(MRI, MBB, MI, SrcReg, DstReg, GVal, IsAma);
311 
312  ToErase = &MI;
313  Changed = true;
314  }
315  }
316 
317  return Changed;
318 }
319 
320 } // namespace
321 
322 INITIALIZE_PASS(BPFMISimplifyPatchable, DEBUG_TYPE,
323  "BPF PreEmit SimplifyPatchable", false, false)
324 
325 char BPFMISimplifyPatchable::ID = 0;
327  return new BPFMISimplifyPatchable();
328 }
llvm::BPFInstrInfo
Definition: BPFInstrInfo.h:24
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
llvm::MachineInstrBuilder::addImm
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
Definition: MachineInstrBuilder.h:131
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::MachineOperand::getGlobal
const GlobalValue * getGlobal() const
Definition: MachineOperand.h:572
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
llvm::MachineInstrBuilder::add
const MachineInstrBuilder & add(const MachineOperand &MO) const
Definition: MachineInstrBuilder.h:224
llvm::MachineRegisterInfo::getUniqueVRegDef
MachineInstr * getUniqueVRegDef(Register Reg) const
getUniqueVRegDef - Return the unique machine instr that defines the specified virtual register or nul...
Definition: MachineRegisterInfo.cpp:407
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::MachineRegisterInfo::use_operands
iterator_range< use_iterator > use_operands(Register Reg) const
Definition: MachineRegisterInfo.h:477
initialize
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringLiteral > StandardNames)
Initialize the set of available library functions based on the specified target triple.
Definition: TargetLibraryInfo.cpp:116
BPF.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
MachineRegisterInfo.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::MachineOperand::getImm
int64_t getImm() const
Definition: MachineOperand.h:546
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:501
INITIALIZE_PASS
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:37
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::MachineOperand::getParent
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
Definition: MachineOperand.h:237
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:642
llvm::initializeBPFMISimplifyPatchablePass
void initializeBPFMISimplifyPatchablePass(PassRegistry &)
llvm::MachineInstr::getDebugLoc
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:420
llvm::GlobalValue
Definition: GlobalValue.h:44
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:320
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::make_early_inc_range
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:618
MachineFunctionPass.h
llvm::BPFCoreSharedInfo::TypeIdAttr
static constexpr StringRef TypeIdAttr
The attribute attached to globals representing a type id.
Definition: BPFCORE.h:65
llvm::MachineInstrBuilder::addReg
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Definition: MachineInstrBuilder.h:97
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:359
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::createBPFMISimplifyPatchablePass
FunctionPass * createBPFMISimplifyPatchablePass()
llvm::MachineInstr::getOpcode
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:491
llvm::MachineRegisterInfo::use_begin
use_iterator use_begin(Register RegNo) const
Definition: MachineRegisterInfo.h:472
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:288
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:622
BPFCORE.h
llvm::MachineOperand::isImm
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
Definition: MachineOperand.h:322
llvm::BPFCoreSharedInfo::AmaAttr
static constexpr StringRef AmaAttr
The attribute attached to globals representing a field access.
Definition: BPFCORE.h:63
llvm::MachineInstrBuilder::addGlobalAddress
const MachineInstrBuilder & addGlobalAddress(const GlobalValue *GV, int64_t Offset=0, unsigned TargetFlags=0) const
Definition: MachineInstrBuilder.h:177
llvm::MachineRegisterInfo::use_end
static use_iterator use_end()
Definition: MachineRegisterInfo.h:475
MachineInstrBuilder.h
llvm::BuildMI
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
Definition: MachineInstrBuilder.h:328
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::MachineInstr::eraseFromParent
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
Definition: MachineInstr.cpp:650
Debug.h
DEBUG_TYPE
#define DEBUG_TYPE
Definition: BPFMISimplifyPatchable.cpp:42
BPFInstrInfo.h
llvm::BPFSubtarget
Definition: BPFSubtarget.h:31
llvm::MachineOperand::isGlobal
bool isGlobal() const
isGlobal - Tests if this is a MO_GlobalAddress operand.
Definition: MachineOperand.h:338
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
BPFTargetMachine.h