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 
35 using namespace llvm;
36 
37 #define DEBUG_TYPE "bpf-mi-simplify-patchable"
38 
39 namespace {
40 
41 struct 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 
51 private:
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 
70 public:
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.
82 void 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 
88 void 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 
142 void 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 
156 void 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 
189 void 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
226 void 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.
240 bool 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 
305 INITIALIZE_PASS(BPFMISimplifyPatchable, DEBUG_TYPE,
306                 "BPF PreEmit SimplifyPatchable", false, false)
307 
308 char BPFMISimplifyPatchable::ID = 0;
309 FunctionPass *llvm::createBPFMISimplifyPatchablePass() {
310   return new BPFMISimplifyPatchable();
311 }
312