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