1 //===-------------- BPFMIPeephole.cpp - MI Peephole Cleanups  -------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass performs peephole optimizations to cleanup ugly code sequences at
11 // MachineInstruction layer.
12 //
13 // Currently, there are two optimizations implemented:
14 //  - One pre-RA MachineSSA pass to eliminate type promotion sequences, those
15 //    zero extend 32-bit subregisters to 64-bit registers, if the compiler
16 //    could prove the subregisters is defined by 32-bit operations in which
17 //    case the upper half of the underlying 64-bit registers were zeroed
18 //    implicitly.
19 //
20 //  - One post-RA PreEmit pass to do final cleanup on some redundant
21 //    instructions generated due to bad RA on subregister.
22 //===----------------------------------------------------------------------===//
23 
24 #include "BPF.h"
25 #include "BPFInstrInfo.h"
26 #include "BPFTargetMachine.h"
27 #include "llvm/ADT/Statistic.h"
28 #include "llvm/CodeGen/MachineInstrBuilder.h"
29 #include "llvm/CodeGen/MachineRegisterInfo.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 isMovFrom32Def(MachineInstr *MovMI);
55   bool eliminateZExtSeq(void);
56 
57 public:
58 
59   // Main entry point for this pass.
60   bool runOnMachineFunction(MachineFunction &MF) override {
61     if (skipFunction(MF.getFunction()))
62       return false;
63 
64     initialize(MF);
65 
66     return eliminateZExtSeq();
67   }
68 };
69 
70 // Initialize class variables.
71 void BPFMIPeephole::initialize(MachineFunction &MFParm) {
72   MF = &MFParm;
73   MRI = &MF->getRegInfo();
74   TII = MF->getSubtarget<BPFSubtarget>().getInstrInfo();
75   DEBUG(dbgs() << "*** BPF MachineSSA peephole pass ***\n\n");
76 }
77 
78 bool BPFMIPeephole::isMovFrom32Def(MachineInstr *MovMI)
79 {
80   MachineInstr *DefInsn = MRI->getVRegDef(MovMI->getOperand(1).getReg());
81 
82   if (!DefInsn)
83     return false;
84 
85   if (DefInsn->isPHI()) {
86     for (unsigned i = 1, e = DefInsn->getNumOperands(); i < e; i += 2) {
87       MachineOperand &opnd = DefInsn->getOperand(i);
88 
89       if (!opnd.isReg())
90         return false;
91 
92       MachineInstr *PhiDef = MRI->getVRegDef(opnd.getReg());
93       // quick check on PHI incoming definitions.
94       if (!PhiDef || PhiDef->isPHI() || PhiDef->getOpcode() == BPF::COPY)
95         return false;
96     }
97   }
98 
99   if (DefInsn->getOpcode() == BPF::COPY) {
100     MachineOperand &opnd = DefInsn->getOperand(1);
101 
102     if (!opnd.isReg())
103       return false;
104 
105     unsigned Reg = opnd.getReg();
106     if ((TargetRegisterInfo::isVirtualRegister(Reg) &&
107          MRI->getRegClass(Reg) == &BPF::GPRRegClass))
108        return false;
109   }
110 
111   return true;
112 }
113 
114 bool BPFMIPeephole::eliminateZExtSeq(void) {
115   MachineInstr* ToErase = nullptr;
116   bool Eliminated = false;
117 
118   for (MachineBasicBlock &MBB : *MF) {
119     for (MachineInstr &MI : MBB) {
120       // If the previous instruction was marked for elimination, remove it now.
121       if (ToErase) {
122         ToErase->eraseFromParent();
123         ToErase = nullptr;
124       }
125 
126       // Eliminate the 32-bit to 64-bit zero extension sequence when possible.
127       //
128       //   MOV_32_64 rB, wA
129       //   SLL_ri    rB, rB, 32
130       //   SRL_ri    rB, rB, 32
131       if (MI.getOpcode() == BPF::SRL_ri &&
132           MI.getOperand(2).getImm() == 32) {
133         unsigned DstReg = MI.getOperand(0).getReg();
134         unsigned ShfReg = MI.getOperand(1).getReg();
135         MachineInstr *SllMI = MRI->getVRegDef(ShfReg);
136 
137         if (!SllMI ||
138             SllMI->isPHI() ||
139             SllMI->getOpcode() != BPF::SLL_ri ||
140             SllMI->getOperand(2).getImm() != 32)
141           continue;
142 
143         MachineInstr *MovMI = MRI->getVRegDef(SllMI->getOperand(1).getReg());
144         if (!MovMI ||
145             MovMI->isPHI() ||
146             MovMI->getOpcode() != BPF::MOV_32_64)
147           continue;
148 
149         unsigned SubReg = MovMI->getOperand(1).getReg();
150         if (!isMovFrom32Def(MovMI))
151           continue;
152 
153         BuildMI(MBB, MI, MI.getDebugLoc(), TII->get(BPF::SUBREG_TO_REG), DstReg)
154           .addImm(0).addReg(SubReg).addImm(BPF::sub_32);
155 
156         SllMI->eraseFromParent();
157         MovMI->eraseFromParent();
158         // MI is the right shift, we can't erase it in it's own iteration.
159         // Mark it to ToErase, and erase in the next iteration.
160         ToErase = &MI;
161         ZExtElemNum++;
162         Eliminated = true;
163       }
164     }
165   }
166 
167   return Eliminated;
168 }
169 
170 } // end default namespace
171 
172 INITIALIZE_PASS(BPFMIPeephole, DEBUG_TYPE,
173                 "BPF MachineSSA Peephole Optimization", false, false)
174 
175 char BPFMIPeephole::ID = 0;
176 FunctionPass* llvm::createBPFMIPeepholePass() { return new BPFMIPeephole(); }
177 
178 STATISTIC(RedundantMovElemNum, "Number of redundant moves eliminated");
179 
180 namespace {
181 
182 struct BPFMIPreEmitPeephole : public MachineFunctionPass {
183 
184   static char ID;
185   MachineFunction *MF;
186   const TargetRegisterInfo *TRI;
187 
188   BPFMIPreEmitPeephole() : MachineFunctionPass(ID) {
189     initializeBPFMIPreEmitPeepholePass(*PassRegistry::getPassRegistry());
190   }
191 
192 private:
193   // Initialize class variables.
194   void initialize(MachineFunction &MFParm);
195 
196   bool eliminateRedundantMov(void);
197 
198 public:
199 
200   // Main entry point for this pass.
201   bool runOnMachineFunction(MachineFunction &MF) override {
202     if (skipFunction(MF.getFunction()))
203       return false;
204 
205     initialize(MF);
206 
207     return eliminateRedundantMov();
208   }
209 };
210 
211 // Initialize class variables.
212 void BPFMIPreEmitPeephole::initialize(MachineFunction &MFParm) {
213   MF = &MFParm;
214   TRI = MF->getSubtarget<BPFSubtarget>().getRegisterInfo();
215   DEBUG(dbgs() << "*** BPF PreEmit peephole pass ***\n\n");
216 }
217 
218 bool BPFMIPreEmitPeephole::eliminateRedundantMov(void) {
219   MachineInstr* ToErase = nullptr;
220   bool Eliminated = false;
221 
222   for (MachineBasicBlock &MBB : *MF) {
223     for (MachineInstr &MI : MBB) {
224       // If the previous instruction was marked for elimination, remove it now.
225       if (ToErase) {
226         ToErase->eraseFromParent();
227         ToErase = nullptr;
228       }
229 
230       // Eliminate identical move:
231       //
232       //   MOV rA, rA
233       //
234       // This is particularly possible to happen when sub-register support
235       // enabled. The special type cast insn MOV_32_64 involves different
236       // register class on src (i32) and dst (i64), RA could generate useless
237       // instruction due to this.
238       if (MI.getOpcode() == BPF::MOV_32_64) {
239         unsigned dst = MI.getOperand(0).getReg();
240         unsigned dst_sub = TRI->getSubReg(dst, BPF::sub_32);
241         unsigned src = MI.getOperand(1).getReg();
242 
243         if (dst_sub != src)
244           continue;
245 
246         ToErase = &MI;
247         RedundantMovElemNum++;
248         Eliminated = true;
249       }
250     }
251   }
252 
253   return Eliminated;
254 }
255 
256 } // end default namespace
257 
258 INITIALIZE_PASS(BPFMIPreEmitPeephole, "bpf-mi-pemit-peephole",
259                 "BPF PreEmit Peephole Optimization", false, false)
260 
261 char BPFMIPreEmitPeephole::ID = 0;
262 FunctionPass* llvm::createBPFMIPreEmitPeepholePass()
263 {
264   return new BPFMIPreEmitPeephole();
265 }
266