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