1 //===-------------- BPFMIPeephole.cpp - MI Peephole Cleanups  -------------===//
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 performs peephole optimizations to cleanup ugly code sequences at
10 // MachineInstruction layer.
11 //
12 // Currently, there are two optimizations implemented:
13 //  - One pre-RA MachineSSA pass to eliminate type promotion sequences, those
14 //    zero extend 32-bit subregisters to 64-bit registers, if the compiler
15 //    could prove the subregisters is defined by 32-bit operations in which
16 //    case the upper half of the underlying 64-bit registers were zeroed
17 //    implicitly.
18 //
19 //  - One post-RA PreEmit pass to do final cleanup on some redundant
20 //    instructions generated due to bad RA on subregister.
21 //===----------------------------------------------------------------------===//
22 
23 #include "BPF.h"
24 #include "BPFInstrInfo.h"
25 #include "BPFTargetMachine.h"
26 #include "llvm/ADT/Statistic.h"
27 #include "llvm/CodeGen/MachineInstrBuilder.h"
28 #include "llvm/CodeGen/MachineRegisterInfo.h"
29 
30 using namespace llvm;
31 
32 #define DEBUG_TYPE "bpf-mi-zext-elim"
33 
34 STATISTIC(ZExtElemNum, "Number of zero extension shifts eliminated");
35 
36 namespace {
37 
38 struct BPFMIPeephole : public MachineFunctionPass {
39 
40   static char ID;
41   const BPFInstrInfo *TII;
42   MachineFunction *MF;
43   MachineRegisterInfo *MRI;
44 
45   BPFMIPeephole() : MachineFunctionPass(ID) {
46     initializeBPFMIPeepholePass(*PassRegistry::getPassRegistry());
47   }
48 
49 private:
50   // Initialize class variables.
51   void initialize(MachineFunction &MFParm);
52 
53   bool isMovFrom32Def(MachineInstr *MovMI);
54   bool eliminateZExtSeq(void);
55 
56 public:
57 
58   // Main entry point for this pass.
59   bool runOnMachineFunction(MachineFunction &MF) override {
60     if (skipFunction(MF.getFunction()))
61       return false;
62 
63     initialize(MF);
64 
65     return eliminateZExtSeq();
66   }
67 };
68 
69 // Initialize class variables.
70 void BPFMIPeephole::initialize(MachineFunction &MFParm) {
71   MF = &MFParm;
72   MRI = &MF->getRegInfo();
73   TII = MF->getSubtarget<BPFSubtarget>().getInstrInfo();
74   LLVM_DEBUG(dbgs() << "*** BPF MachineSSA ZEXT Elim peephole pass ***\n\n");
75 }
76 
77 bool BPFMIPeephole::isMovFrom32Def(MachineInstr *MovMI)
78 {
79   MachineInstr *DefInsn = MRI->getVRegDef(MovMI->getOperand(1).getReg());
80 
81   LLVM_DEBUG(dbgs() << "  Def of Mov Src:");
82   LLVM_DEBUG(DefInsn->dump());
83 
84   if (!DefInsn)
85     return false;
86 
87   if (DefInsn->isPHI()) {
88     for (unsigned i = 1, e = DefInsn->getNumOperands(); i < e; i += 2) {
89       MachineOperand &opnd = DefInsn->getOperand(i);
90 
91       if (!opnd.isReg())
92         return false;
93 
94       MachineInstr *PhiDef = MRI->getVRegDef(opnd.getReg());
95       // quick check on PHI incoming definitions.
96       if (!PhiDef || PhiDef->isPHI() || PhiDef->getOpcode() == BPF::COPY)
97         return false;
98     }
99   }
100 
101   if (DefInsn->getOpcode() == BPF::COPY) {
102     MachineOperand &opnd = DefInsn->getOperand(1);
103 
104     if (!opnd.isReg())
105       return false;
106 
107     Register Reg = opnd.getReg();
108     if ((Register::isVirtualRegister(Reg) &&
109          MRI->getRegClass(Reg) == &BPF::GPRRegClass))
110       return false;
111   }
112 
113   LLVM_DEBUG(dbgs() << "  One ZExt elim sequence identified.\n");
114 
115   return true;
116 }
117 
118 bool BPFMIPeephole::eliminateZExtSeq(void) {
119   MachineInstr* ToErase = nullptr;
120   bool Eliminated = false;
121 
122   for (MachineBasicBlock &MBB : *MF) {
123     for (MachineInstr &MI : MBB) {
124       // If the previous instruction was marked for elimination, remove it now.
125       if (ToErase) {
126         ToErase->eraseFromParent();
127         ToErase = nullptr;
128       }
129 
130       // Eliminate the 32-bit to 64-bit zero extension sequence when possible.
131       //
132       //   MOV_32_64 rB, wA
133       //   SLL_ri    rB, rB, 32
134       //   SRL_ri    rB, rB, 32
135       if (MI.getOpcode() == BPF::SRL_ri &&
136           MI.getOperand(2).getImm() == 32) {
137         Register DstReg = MI.getOperand(0).getReg();
138         Register ShfReg = MI.getOperand(1).getReg();
139         MachineInstr *SllMI = MRI->getVRegDef(ShfReg);
140 
141         LLVM_DEBUG(dbgs() << "Starting SRL found:");
142         LLVM_DEBUG(MI.dump());
143 
144         if (!SllMI ||
145             SllMI->isPHI() ||
146             SllMI->getOpcode() != BPF::SLL_ri ||
147             SllMI->getOperand(2).getImm() != 32)
148           continue;
149 
150         LLVM_DEBUG(dbgs() << "  SLL found:");
151         LLVM_DEBUG(SllMI->dump());
152 
153         MachineInstr *MovMI = MRI->getVRegDef(SllMI->getOperand(1).getReg());
154         if (!MovMI ||
155             MovMI->isPHI() ||
156             MovMI->getOpcode() != BPF::MOV_32_64)
157           continue;
158 
159         LLVM_DEBUG(dbgs() << "  Type cast Mov found:");
160         LLVM_DEBUG(MovMI->dump());
161 
162         Register SubReg = MovMI->getOperand(1).getReg();
163         if (!isMovFrom32Def(MovMI)) {
164           LLVM_DEBUG(dbgs()
165                      << "  One ZExt elim sequence failed qualifying elim.\n");
166           continue;
167         }
168 
169         BuildMI(MBB, MI, MI.getDebugLoc(), TII->get(BPF::SUBREG_TO_REG), DstReg)
170           .addImm(0).addReg(SubReg).addImm(BPF::sub_32);
171 
172         SllMI->eraseFromParent();
173         MovMI->eraseFromParent();
174         // MI is the right shift, we can't erase it in it's own iteration.
175         // Mark it to ToErase, and erase in the next iteration.
176         ToErase = &MI;
177         ZExtElemNum++;
178         Eliminated = true;
179       }
180     }
181   }
182 
183   return Eliminated;
184 }
185 
186 } // end default namespace
187 
188 INITIALIZE_PASS(BPFMIPeephole, DEBUG_TYPE,
189                 "BPF MachineSSA Peephole Optimization For ZEXT Eliminate",
190                 false, false)
191 
192 char BPFMIPeephole::ID = 0;
193 FunctionPass* llvm::createBPFMIPeepholePass() { return new BPFMIPeephole(); }
194 
195 STATISTIC(RedundantMovElemNum, "Number of redundant moves eliminated");
196 
197 namespace {
198 
199 struct BPFMIPreEmitPeephole : public MachineFunctionPass {
200 
201   static char ID;
202   MachineFunction *MF;
203   const TargetRegisterInfo *TRI;
204 
205   BPFMIPreEmitPeephole() : MachineFunctionPass(ID) {
206     initializeBPFMIPreEmitPeepholePass(*PassRegistry::getPassRegistry());
207   }
208 
209 private:
210   // Initialize class variables.
211   void initialize(MachineFunction &MFParm);
212 
213   bool eliminateRedundantMov(void);
214 
215 public:
216 
217   // Main entry point for this pass.
218   bool runOnMachineFunction(MachineFunction &MF) override {
219     if (skipFunction(MF.getFunction()))
220       return false;
221 
222     initialize(MF);
223 
224     return eliminateRedundantMov();
225   }
226 };
227 
228 // Initialize class variables.
229 void BPFMIPreEmitPeephole::initialize(MachineFunction &MFParm) {
230   MF = &MFParm;
231   TRI = MF->getSubtarget<BPFSubtarget>().getRegisterInfo();
232   LLVM_DEBUG(dbgs() << "*** BPF PreEmit peephole pass ***\n\n");
233 }
234 
235 bool BPFMIPreEmitPeephole::eliminateRedundantMov(void) {
236   MachineInstr* ToErase = nullptr;
237   bool Eliminated = false;
238 
239   for (MachineBasicBlock &MBB : *MF) {
240     for (MachineInstr &MI : MBB) {
241       // If the previous instruction was marked for elimination, remove it now.
242       if (ToErase) {
243         LLVM_DEBUG(dbgs() << "  Redundant Mov Eliminated:");
244         LLVM_DEBUG(ToErase->dump());
245         ToErase->eraseFromParent();
246         ToErase = nullptr;
247       }
248 
249       // Eliminate identical move:
250       //
251       //   MOV rA, rA
252       //
253       // This is particularly possible to happen when sub-register support
254       // enabled. The special type cast insn MOV_32_64 involves different
255       // register class on src (i32) and dst (i64), RA could generate useless
256       // instruction due to this.
257       unsigned Opcode = MI.getOpcode();
258       if (Opcode == BPF::MOV_32_64 ||
259           Opcode == BPF::MOV_rr || Opcode == BPF::MOV_rr_32) {
260         Register dst = MI.getOperand(0).getReg();
261         Register src = MI.getOperand(1).getReg();
262 
263         if (Opcode == BPF::MOV_32_64)
264           dst = TRI->getSubReg(dst, BPF::sub_32);
265 
266         if (dst != src)
267           continue;
268 
269         ToErase = &MI;
270         RedundantMovElemNum++;
271         Eliminated = true;
272       }
273     }
274   }
275 
276   return Eliminated;
277 }
278 
279 } // end default namespace
280 
281 INITIALIZE_PASS(BPFMIPreEmitPeephole, "bpf-mi-pemit-peephole",
282                 "BPF PreEmit Peephole Optimization", false, false)
283 
284 char BPFMIPreEmitPeephole::ID = 0;
285 FunctionPass* llvm::createBPFMIPreEmitPeepholePass()
286 {
287   return new BPFMIPreEmitPeephole();
288 }
289 
290 STATISTIC(TruncElemNum, "Number of truncation eliminated");
291 
292 namespace {
293 
294 struct BPFMIPeepholeTruncElim : public MachineFunctionPass {
295 
296   static char ID;
297   const BPFInstrInfo *TII;
298   MachineFunction *MF;
299   MachineRegisterInfo *MRI;
300 
301   BPFMIPeepholeTruncElim() : MachineFunctionPass(ID) {
302     initializeBPFMIPeepholeTruncElimPass(*PassRegistry::getPassRegistry());
303   }
304 
305 private:
306   // Initialize class variables.
307   void initialize(MachineFunction &MFParm);
308 
309   bool eliminateTruncSeq(void);
310 
311 public:
312 
313   // Main entry point for this pass.
314   bool runOnMachineFunction(MachineFunction &MF) override {
315     if (skipFunction(MF.getFunction()))
316       return false;
317 
318     initialize(MF);
319 
320     return eliminateTruncSeq();
321   }
322 };
323 
324 static bool TruncSizeCompatible(int TruncSize, unsigned opcode)
325 {
326   if (TruncSize == 1)
327     return opcode == BPF::LDB || opcode == BPF::LDB32;
328 
329   if (TruncSize == 2)
330     return opcode == BPF::LDH || opcode == BPF::LDH32;
331 
332   if (TruncSize == 4)
333     return opcode == BPF::LDW || opcode == BPF::LDW32;
334 
335   return false;
336 }
337 
338 // Initialize class variables.
339 void BPFMIPeepholeTruncElim::initialize(MachineFunction &MFParm) {
340   MF = &MFParm;
341   MRI = &MF->getRegInfo();
342   TII = MF->getSubtarget<BPFSubtarget>().getInstrInfo();
343   LLVM_DEBUG(dbgs() << "*** BPF MachineSSA TRUNC Elim peephole pass ***\n\n");
344 }
345 
346 // Reg truncating is often the result of 8/16/32bit->64bit or
347 // 8/16bit->32bit conversion. If the reg value is loaded with
348 // masked byte width, the AND operation can be removed since
349 // BPF LOAD already has zero extension.
350 //
351 // This also solved a correctness issue.
352 // In BPF socket-related program, e.g., __sk_buff->{data, data_end}
353 // are 32-bit registers, but later on, kernel verifier will rewrite
354 // it with 64-bit value. Therefore, truncating the value after the
355 // load will result in incorrect code.
356 bool BPFMIPeepholeTruncElim::eliminateTruncSeq(void) {
357   MachineInstr* ToErase = nullptr;
358   bool Eliminated = false;
359 
360   for (MachineBasicBlock &MBB : *MF) {
361     for (MachineInstr &MI : MBB) {
362       // The second insn to remove if the eliminate candidate is a pair.
363       MachineInstr *MI2 = nullptr;
364       Register DstReg, SrcReg;
365       MachineInstr *DefMI;
366       int TruncSize = -1;
367 
368       // If the previous instruction was marked for elimination, remove it now.
369       if (ToErase) {
370         ToErase->eraseFromParent();
371         ToErase = nullptr;
372       }
373 
374       // AND A, 0xFFFFFFFF will be turned into SLL/SRL pair due to immediate
375       // for BPF ANDI is i32, and this case only happens on ALU64.
376       if (MI.getOpcode() == BPF::SRL_ri &&
377           MI.getOperand(2).getImm() == 32) {
378         SrcReg = MI.getOperand(1).getReg();
379         MI2 = MRI->getVRegDef(SrcReg);
380         DstReg = MI.getOperand(0).getReg();
381 
382         if (!MI2 ||
383             MI2->getOpcode() != BPF::SLL_ri ||
384             MI2->getOperand(2).getImm() != 32)
385           continue;
386 
387         // Update SrcReg.
388         SrcReg = MI2->getOperand(1).getReg();
389         DefMI = MRI->getVRegDef(SrcReg);
390         if (DefMI)
391           TruncSize = 4;
392       } else if (MI.getOpcode() == BPF::AND_ri ||
393                  MI.getOpcode() == BPF::AND_ri_32) {
394         SrcReg = MI.getOperand(1).getReg();
395         DstReg = MI.getOperand(0).getReg();
396         DefMI = MRI->getVRegDef(SrcReg);
397 
398         if (!DefMI)
399           continue;
400 
401         int64_t imm = MI.getOperand(2).getImm();
402         if (imm == 0xff)
403           TruncSize = 1;
404         else if (imm == 0xffff)
405           TruncSize = 2;
406       }
407 
408       if (TruncSize == -1)
409         continue;
410 
411       // The definition is PHI node, check all inputs.
412       if (DefMI->isPHI()) {
413         bool CheckFail = false;
414 
415         for (unsigned i = 1, e = DefMI->getNumOperands(); i < e; i += 2) {
416           MachineOperand &opnd = DefMI->getOperand(i);
417           if (!opnd.isReg()) {
418             CheckFail = true;
419             break;
420           }
421 
422           MachineInstr *PhiDef = MRI->getVRegDef(opnd.getReg());
423           if (!PhiDef || PhiDef->isPHI() ||
424               !TruncSizeCompatible(TruncSize, PhiDef->getOpcode())) {
425             CheckFail = true;
426             break;
427           }
428         }
429 
430         if (CheckFail)
431           continue;
432       } else if (!TruncSizeCompatible(TruncSize, DefMI->getOpcode())) {
433         continue;
434       }
435 
436       BuildMI(MBB, MI, MI.getDebugLoc(), TII->get(BPF::MOV_rr), DstReg)
437               .addReg(SrcReg);
438 
439       if (MI2)
440         MI2->eraseFromParent();
441 
442       // Mark it to ToErase, and erase in the next iteration.
443       ToErase = &MI;
444       TruncElemNum++;
445       Eliminated = true;
446     }
447   }
448 
449   return Eliminated;
450 }
451 
452 } // end default namespace
453 
454 INITIALIZE_PASS(BPFMIPeepholeTruncElim, "bpf-mi-trunc-elim",
455                 "BPF MachineSSA Peephole Optimization For TRUNC Eliminate",
456                 false, false)
457 
458 char BPFMIPeepholeTruncElim::ID = 0;
459 FunctionPass* llvm::createBPFMIPeepholeTruncElimPass()
460 {
461   return new BPFMIPeepholeTruncElim();
462 }
463