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