BPFMISimplifyPatchable.cpp revision 363496 
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//===----------------------------------------------------------------------===//
26
27#include "BPF.h"
28#include "BPFCORE.h"
29#include "BPFInstrInfo.h"
30#include "BPFTargetMachine.h"
31#include "llvm/CodeGen/MachineInstrBuilder.h"
32#include "llvm/CodeGen/MachineRegisterInfo.h"
33#include "llvm/Support/Debug.h"
34
35using namespace llvm;
36
37#define DEBUG_TYPE "bpf-mi-simplify-patchable"
38
39namespace {
40
41struct BPFMISimplifyPatchable : public MachineFunctionPass {
42
43  static char ID;
44  const BPFInstrInfo *TII;
45  MachineFunction *MF;
46
47  BPFMISimplifyPatchable() : MachineFunctionPass(ID) {
48    initializeBPFMISimplifyPatchablePass(*PassRegistry::getPassRegistry());
49  }
50
51private:
52  // Initialize class variables.
53  void initialize(MachineFunction &MFParm);
54
55  bool removeLD(void);
56  void processCandidate(MachineRegisterInfo *MRI, MachineBasicBlock &MBB,
57                        MachineInstr &MI, Register &SrcReg, Register &DstReg,
58                        const GlobalValue *GVal);
59  void processDstReg(MachineRegisterInfo *MRI, Register &DstReg,
60                     Register &SrcReg, const GlobalValue *GVal,
61                     bool doSrcRegProp);
62  void processInst(MachineRegisterInfo *MRI, MachineInstr *Inst,
63                   MachineOperand *RelocOp, const GlobalValue *GVal);
64  void checkADDrr(MachineRegisterInfo *MRI, MachineOperand *RelocOp,
65                  const GlobalValue *GVal);
66  void checkShift(MachineRegisterInfo *MRI, MachineBasicBlock &MBB,
67                  MachineOperand *RelocOp, const GlobalValue *GVal,
68                  unsigned Opcode);
69
70public:
71  // Main entry point for this pass.
72  bool runOnMachineFunction(MachineFunction &MF) override {
73    if (skipFunction(MF.getFunction()))
74      return false;
75
76    initialize(MF);
77    return removeLD();
78  }
79};
80
81// Initialize class variables.
82void BPFMISimplifyPatchable::initialize(MachineFunction &MFParm) {
83  MF = &MFParm;
84  TII = MF->getSubtarget<BPFSubtarget>().getInstrInfo();
85  LLVM_DEBUG(dbgs() << "*** BPF simplify patchable insts pass ***\n\n");
86}
87
88void BPFMISimplifyPatchable::checkADDrr(MachineRegisterInfo *MRI,
89    MachineOperand *RelocOp, const GlobalValue *GVal) {
90  const MachineInstr *Inst = RelocOp->getParent();
91  const MachineOperand *Op1 = &Inst->getOperand(1);
92  const MachineOperand *Op2 = &Inst->getOperand(2);
93  const MachineOperand *BaseOp = (RelocOp == Op1) ? Op2 : Op1;
94
95  // Go through all uses of %1 as in %1 = ADD_rr %2, %3
96  const MachineOperand Op0 = Inst->getOperand(0);
97  auto Begin = MRI->use_begin(Op0.getReg()), End = MRI->use_end();
98  decltype(End) NextI;
99  for (auto I = Begin; I != End; I = NextI) {
100    NextI = std::next(I);
101    // The candidate needs to have a unique definition.
102    if (!MRI->getUniqueVRegDef(I->getReg()))
103      continue;
104
105    MachineInstr *DefInst = I->getParent();
106    unsigned Opcode = DefInst->getOpcode();
107    unsigned COREOp;
108    if (Opcode == BPF::LDB || Opcode == BPF::LDH || Opcode == BPF::LDW ||
109        Opcode == BPF::LDD || Opcode == BPF::STB || Opcode == BPF::STH ||
110        Opcode == BPF::STW || Opcode == BPF::STD)
111      COREOp = BPF::CORE_MEM;
112    else if (Opcode == BPF::LDB32 || Opcode == BPF::LDH32 ||
113             Opcode == BPF::LDW32 || Opcode == BPF::STB32 ||
114             Opcode == BPF::STH32 || Opcode == BPF::STW32)
115      COREOp = BPF::CORE_ALU32_MEM;
116    else
117      continue;
118
119    // It must be a form of %2 = *(type *)(%1 + 0) or *(type *)(%1 + 0) = %2.
120    const MachineOperand &ImmOp = DefInst->getOperand(2);
121    if (!ImmOp.isImm() || ImmOp.getImm() != 0)
122      continue;
123
124    // Reject the form:
125    //   %1 = ADD_rr %2, %3
126    //   *(type *)(%2 + 0) = %1
127    if (Opcode == BPF::STB || Opcode == BPF::STH || Opcode == BPF::STW ||
128        Opcode == BPF::STD || Opcode == BPF::STB32 || Opcode == BPF::STH32 ||
129        Opcode == BPF::STW32) {
130      const MachineOperand &Opnd = DefInst->getOperand(0);
131      if (Opnd.isReg() && Opnd.getReg() == I->getReg())
132        continue;
133    }
134
135    BuildMI(*DefInst->getParent(), *DefInst, DefInst->getDebugLoc(), TII->get(COREOp))
136        .add(DefInst->getOperand(0)).addImm(Opcode).add(*BaseOp)
137        .addGlobalAddress(GVal);
138    DefInst->eraseFromParent();
139  }
140}
141
142void BPFMISimplifyPatchable::checkShift(MachineRegisterInfo *MRI,
143    MachineBasicBlock &MBB, MachineOperand *RelocOp, const GlobalValue *GVal,
144    unsigned Opcode) {
145  // Relocation operand should be the operand #2.
146  MachineInstr *Inst = RelocOp->getParent();
147  if (RelocOp != &Inst->getOperand(2))
148    return;
149
150  BuildMI(MBB, *Inst, Inst->getDebugLoc(), TII->get(BPF::CORE_SHIFT))
151      .add(Inst->getOperand(0)).addImm(Opcode)
152      .add(Inst->getOperand(1)).addGlobalAddress(GVal);
153  Inst->eraseFromParent();
154}
155
156void BPFMISimplifyPatchable::processCandidate(MachineRegisterInfo *MRI,
157    MachineBasicBlock &MBB, MachineInstr &MI, Register &SrcReg,
158    Register &DstReg, const GlobalValue *GVal) {
159  if (MRI->getRegClass(DstReg) == &BPF::GPR32RegClass) {
160    // We can optimize such a pattern:
161    //  %1:gpr = LD_imm64 @"llvm.s:0:4$0:2"
162    //  %2:gpr32 = LDW32 %1:gpr, 0
163    //  %3:gpr = SUBREG_TO_REG 0, %2:gpr32, %subreg.sub_32
164    //  %4:gpr = ADD_rr %0:gpr, %3:gpr
165    //  or similar patterns below for non-alu32 case.
166    auto Begin = MRI->use_begin(DstReg), End = MRI->use_end();
167    decltype(End) NextI;
168    for (auto I = Begin; I != End; I = NextI) {
169      NextI = std::next(I);
170      if (!MRI->getUniqueVRegDef(I->getReg()))
171        continue;
172
173      unsigned Opcode = I->getParent()->getOpcode();
174      if (Opcode == BPF::SUBREG_TO_REG) {
175        Register TmpReg = I->getParent()->getOperand(0).getReg();
176        processDstReg(MRI, TmpReg, DstReg, GVal, false);
177      }
178    }
179
180    BuildMI(MBB, MI, MI.getDebugLoc(), TII->get(BPF::COPY), DstReg)
181        .addReg(SrcReg, 0, BPF::sub_32);
182    return;
183  }
184
185  // All uses of DstReg replaced by SrcReg
186  processDstReg(MRI, DstReg, SrcReg, GVal, true);
187}
188
189void BPFMISimplifyPatchable::processDstReg(MachineRegisterInfo *MRI,
190    Register &DstReg, Register &SrcReg, const GlobalValue *GVal,
191    bool doSrcRegProp) {
192  auto Begin = MRI->use_begin(DstReg), End = MRI->use_end();
193  decltype(End) NextI;
194  for (auto I = Begin; I != End; I = NextI) {
195    NextI = std::next(I);
196    if (doSrcRegProp)
197      I->setReg(SrcReg);
198
199    // The candidate needs to have a unique definition.
200    if (MRI->getUniqueVRegDef(I->getReg()))
201      processInst(MRI, I->getParent(), &*I, GVal);
202  }
203}
204
205// Check to see whether we could do some optimization
206// to attach relocation to downstream dependent instructions.
207// Two kinds of patterns are recognized below:
208// Pattern 1:
209//   %1 = LD_imm64 @"llvm.b:0:4$0:1"  <== patch_imm = 4
210//   %2 = LDD %1, 0  <== this insn will be removed
211//   %3 = ADD_rr %0, %2
212//   %4 = LDW[32] %3, 0 OR STW[32] %4, %3, 0
213//   The `%4 = ...` will be transformed to
214//      CORE_[ALU32_]MEM(%4, mem_opcode, %0, @"llvm.b:0:4$0:1")
215//   and later on, BTF emit phase will translate to
216//      %4 = LDW[32] %0, 4 STW[32] %4, %0, 4
217//   and attach a relocation to it.
218// Pattern 2:
219//    %15 = LD_imm64 @"llvm.t:5:63$0:2" <== relocation type 5
220//    %16 = LDD %15, 0   <== this insn will be removed
221//    %17 = SRA_rr %14, %16
222//    The `%17 = ...` will be transformed to
223//       %17 = CORE_SHIFT(SRA_ri, %14, @"llvm.t:5:63$0:2")
224//    and later on, BTF emit phase will translate to
225//       %r4 = SRA_ri %r4, 63
226void BPFMISimplifyPatchable::processInst(MachineRegisterInfo *MRI,
227    MachineInstr *Inst, MachineOperand *RelocOp, const GlobalValue *GVal) {
228  unsigned Opcode = Inst->getOpcode();
229  if (Opcode == BPF::ADD_rr)
230    checkADDrr(MRI, RelocOp, GVal);
231  else if (Opcode == BPF::SLL_rr)
232    checkShift(MRI, *Inst->getParent(), RelocOp, GVal, BPF::SLL_ri);
233  else if (Opcode == BPF::SRA_rr)
234    checkShift(MRI, *Inst->getParent(), RelocOp, GVal, BPF::SRA_ri);
235  else if (Opcode == BPF::SRL_rr)
236    checkShift(MRI, *Inst->getParent(), RelocOp, GVal, BPF::SRL_ri);
237}
238
239/// Remove unneeded Load instructions.
240bool BPFMISimplifyPatchable::removeLD() {
241  MachineRegisterInfo *MRI = &MF->getRegInfo();
242  MachineInstr *ToErase = nullptr;
243  bool Changed = false;
244
245  for (MachineBasicBlock &MBB : *MF) {
246    for (MachineInstr &MI : MBB) {
247      if (ToErase) {
248        ToErase->eraseFromParent();
249        ToErase = nullptr;
250      }
251
252      // Ensure the register format is LOAD <reg>, <reg>, 0
253      if (MI.getOpcode() != BPF::LDD && MI.getOpcode() != BPF::LDW &&
254          MI.getOpcode() != BPF::LDH && MI.getOpcode() != BPF::LDB &&
255          MI.getOpcode() != BPF::LDW32 && MI.getOpcode() != BPF::LDH32 &&
256          MI.getOpcode() != BPF::LDB32)
257        continue;
258
259      if (!MI.getOperand(0).isReg() || !MI.getOperand(1).isReg())
260        continue;
261
262      if (!MI.getOperand(2).isImm() || MI.getOperand(2).getImm())
263        continue;
264
265      Register DstReg = MI.getOperand(0).getReg();
266      Register SrcReg = MI.getOperand(1).getReg();
267
268      MachineInstr *DefInst = MRI->getUniqueVRegDef(SrcReg);
269      if (!DefInst)
270        continue;
271
272      bool IsCandidate = false;
273      const GlobalValue *GVal = nullptr;
274      if (DefInst->getOpcode() == BPF::LD_imm64) {
275        const MachineOperand &MO = DefInst->getOperand(1);
276        if (MO.isGlobal()) {
277          GVal = MO.getGlobal();
278          auto *GVar = dyn_cast<GlobalVariable>(GVal);
279          if (GVar) {
280            // Global variables representing structure offset or
281            // patchable extern globals.
282            if (GVar->hasAttribute(BPFCoreSharedInfo::AmaAttr)) {
283              assert(MI.getOperand(2).getImm() == 0);
284              IsCandidate = true;
285            }
286          }
287        }
288      }
289
290      if (!IsCandidate)
291        continue;
292
293      processCandidate(MRI, MBB, MI, SrcReg, DstReg, GVal);
294
295      ToErase = &MI;
296      Changed = true;
297    }
298  }
299
300  return Changed;
301}
302
303} // namespace
304
305INITIALIZE_PASS(BPFMISimplifyPatchable, DEBUG_TYPE,
306                "BPF PreEmit SimplifyPatchable", false, false)
307
308char BPFMISimplifyPatchable::ID = 0;
309FunctionPass *llvm::createBPFMISimplifyPatchablePass() {
310  return new BPFMISimplifyPatchable();
311}
312