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