• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
BPFMIPeephole__anon5e540ed00111::BPFMIPeephole46   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.
runOnMachineFunction__anon5e540ed00111::BPFMIPeephole60   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.
initialize(MachineFunction & MFParm)71 void BPFMIPeephole::initialize(MachineFunction &MFParm) {
72   MF = &MFParm;
73   MRI = &MF->getRegInfo();
74   TII = MF->getSubtarget<BPFSubtarget>().getInstrInfo();
75   LLVM_DEBUG(dbgs() << "*** BPF MachineSSA peephole pass ***\n\n");
76 }
77 
isMovFrom32Def(MachineInstr * MovMI)78 bool BPFMIPeephole::isMovFrom32Def(MachineInstr *MovMI)
79 {
80   MachineInstr *DefInsn = MRI->getVRegDef(MovMI->getOperand(1).getReg());
81 
82   LLVM_DEBUG(dbgs() << "  Def of Mov Src:");
83   LLVM_DEBUG(DefInsn->dump());
84 
85   if (!DefInsn)
86     return false;
87 
88   if (DefInsn->isPHI()) {
89     for (unsigned i = 1, e = DefInsn->getNumOperands(); i < e; i += 2) {
90       MachineOperand &opnd = DefInsn->getOperand(i);
91 
92       if (!opnd.isReg())
93         return false;
94 
95       MachineInstr *PhiDef = MRI->getVRegDef(opnd.getReg());
96       // quick check on PHI incoming definitions.
97       if (!PhiDef || PhiDef->isPHI() || PhiDef->getOpcode() == BPF::COPY)
98         return false;
99     }
100   }
101 
102   if (DefInsn->getOpcode() == BPF::COPY) {
103     MachineOperand &opnd = DefInsn->getOperand(1);
104 
105     if (!opnd.isReg())
106       return false;
107 
108     unsigned Reg = opnd.getReg();
109     if ((TargetRegisterInfo::isVirtualRegister(Reg) &&
110          MRI->getRegClass(Reg) == &BPF::GPRRegClass))
111        return false;
112   }
113 
114   LLVM_DEBUG(dbgs() << "  One ZExt elim sequence identified.\n");
115 
116   return true;
117 }
118 
eliminateZExtSeq(void)119 bool BPFMIPeephole::eliminateZExtSeq(void) {
120   MachineInstr* ToErase = nullptr;
121   bool Eliminated = false;
122 
123   for (MachineBasicBlock &MBB : *MF) {
124     for (MachineInstr &MI : MBB) {
125       // If the previous instruction was marked for elimination, remove it now.
126       if (ToErase) {
127         ToErase->eraseFromParent();
128         ToErase = nullptr;
129       }
130 
131       // Eliminate the 32-bit to 64-bit zero extension sequence when possible.
132       //
133       //   MOV_32_64 rB, wA
134       //   SLL_ri    rB, rB, 32
135       //   SRL_ri    rB, rB, 32
136       if (MI.getOpcode() == BPF::SRL_ri &&
137           MI.getOperand(2).getImm() == 32) {
138         unsigned DstReg = MI.getOperand(0).getReg();
139         unsigned ShfReg = MI.getOperand(1).getReg();
140         MachineInstr *SllMI = MRI->getVRegDef(ShfReg);
141 
142         LLVM_DEBUG(dbgs() << "Starting SRL found:");
143         LLVM_DEBUG(MI.dump());
144 
145         if (!SllMI ||
146             SllMI->isPHI() ||
147             SllMI->getOpcode() != BPF::SLL_ri ||
148             SllMI->getOperand(2).getImm() != 32)
149           continue;
150 
151         LLVM_DEBUG(dbgs() << "  SLL found:");
152         LLVM_DEBUG(SllMI->dump());
153 
154         MachineInstr *MovMI = MRI->getVRegDef(SllMI->getOperand(1).getReg());
155         if (!MovMI ||
156             MovMI->isPHI() ||
157             MovMI->getOpcode() != BPF::MOV_32_64)
158           continue;
159 
160         LLVM_DEBUG(dbgs() << "  Type cast Mov found:");
161         LLVM_DEBUG(MovMI->dump());
162 
163         unsigned SubReg = MovMI->getOperand(1).getReg();
164         if (!isMovFrom32Def(MovMI)) {
165           LLVM_DEBUG(dbgs()
166                      << "  One ZExt elim sequence failed qualifying elim.\n");
167           continue;
168         }
169 
170         BuildMI(MBB, MI, MI.getDebugLoc(), TII->get(BPF::SUBREG_TO_REG), DstReg)
171           .addImm(0).addReg(SubReg).addImm(BPF::sub_32);
172 
173         SllMI->eraseFromParent();
174         MovMI->eraseFromParent();
175         // MI is the right shift, we can't erase it in it's own iteration.
176         // Mark it to ToErase, and erase in the next iteration.
177         ToErase = &MI;
178         ZExtElemNum++;
179         Eliminated = true;
180       }
181     }
182   }
183 
184   return Eliminated;
185 }
186 
187 } // end default namespace
188 
189 INITIALIZE_PASS(BPFMIPeephole, DEBUG_TYPE,
190                 "BPF MachineSSA Peephole Optimization", false, false)
191 
192 char BPFMIPeephole::ID = 0;
createBPFMIPeepholePass()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 
BPFMIPreEmitPeephole__anon5e540ed00211::BPFMIPreEmitPeephole205   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.
runOnMachineFunction__anon5e540ed00211::BPFMIPreEmitPeephole218   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.
initialize(MachineFunction & MFParm)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 
eliminateRedundantMov(void)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       if (MI.getOpcode() == BPF::MOV_32_64) {
258         unsigned dst = MI.getOperand(0).getReg();
259         unsigned dst_sub = TRI->getSubReg(dst, BPF::sub_32);
260         unsigned src = MI.getOperand(1).getReg();
261 
262         if (dst_sub != src)
263           continue;
264 
265         ToErase = &MI;
266         RedundantMovElemNum++;
267         Eliminated = true;
268       }
269     }
270   }
271 
272   return Eliminated;
273 }
274 
275 } // end default namespace
276 
277 INITIALIZE_PASS(BPFMIPreEmitPeephole, "bpf-mi-pemit-peephole",
278                 "BPF PreEmit Peephole Optimization", false, false)
279 
280 char BPFMIPreEmitPeephole::ID = 0;
createBPFMIPreEmitPeepholePass()281 FunctionPass* llvm::createBPFMIPreEmitPeepholePass()
282 {
283   return new BPFMIPreEmitPeephole();
284 }
285