1 //===-------------- BPFMIPeephole.cpp - MI Peephole Cleanups -------------===//
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
7 //===----------------------------------------------------------------------===//
9 // This pass performs peephole optimizations to cleanup ugly code sequences at
10 // MachineInstruction layer.
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
19 // - One post-RA PreEmit pass to do final cleanup on some redundant
20 // instructions generated due to bad RA on subregister.
21 //===----------------------------------------------------------------------===//
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"
33 #define DEBUG_TYPE "bpf-mi-zext-elim"
35 STATISTIC(ZExtElemNum, "Number of zero extension shifts eliminated");
39 struct BPFMIPeephole : public MachineFunctionPass {
42 const BPFInstrInfo *TII;
44 MachineRegisterInfo *MRI;
46 BPFMIPeephole() : MachineFunctionPass(ID) {
47 initializeBPFMIPeepholePass(*PassRegistry::getPassRegistry());
51 // Initialize class variables.
52 void initialize(MachineFunction &MFParm);
54 bool isCopyFrom32Def(MachineInstr *CopyMI);
55 bool isInsnFrom32Def(MachineInstr *DefInsn);
56 bool isPhiFrom32Def(MachineInstr *MovMI);
57 bool isMovFrom32Def(MachineInstr *MovMI);
58 bool eliminateZExtSeq(void);
60 std::set<MachineInstr *> PhiInsns;
64 // Main entry point for this pass.
65 bool runOnMachineFunction(MachineFunction &MF) override {
66 if (skipFunction(MF.getFunction()))
71 return eliminateZExtSeq();
75 // Initialize class variables.
76 void BPFMIPeephole::initialize(MachineFunction &MFParm) {
78 MRI = &MF->getRegInfo();
79 TII = MF->getSubtarget<BPFSubtarget>().getInstrInfo();
80 LLVM_DEBUG(dbgs() << "*** BPF MachineSSA ZEXT Elim peephole pass ***\n\n");
83 bool BPFMIPeephole::isCopyFrom32Def(MachineInstr *CopyMI)
85 MachineOperand &opnd = CopyMI->getOperand(1);
90 // Return false if getting value from a 32bit physical register.
91 // Most likely, this physical register is aliased to
92 // function call return value or current function parameters.
93 Register Reg = opnd.getReg();
94 if (!Register::isVirtualRegister(Reg))
97 if (MRI->getRegClass(Reg) == &BPF::GPRRegClass)
100 MachineInstr *DefInsn = MRI->getVRegDef(Reg);
101 if (!isInsnFrom32Def(DefInsn))
107 bool BPFMIPeephole::isPhiFrom32Def(MachineInstr *PhiMI)
109 for (unsigned i = 1, e = PhiMI->getNumOperands(); i < e; i += 2) {
110 MachineOperand &opnd = PhiMI->getOperand(i);
115 MachineInstr *PhiDef = MRI->getVRegDef(opnd.getReg());
118 if (PhiDef->isPHI()) {
119 if (PhiInsns.find(PhiDef) != PhiInsns.end())
121 PhiInsns.insert(PhiDef);
122 if (!isPhiFrom32Def(PhiDef))
125 if (PhiDef->getOpcode() == BPF::COPY && !isCopyFrom32Def(PhiDef))
132 // The \p DefInsn instruction defines a virtual register.
133 bool BPFMIPeephole::isInsnFrom32Def(MachineInstr *DefInsn)
138 if (DefInsn->isPHI()) {
139 if (PhiInsns.find(DefInsn) != PhiInsns.end())
141 PhiInsns.insert(DefInsn);
142 if (!isPhiFrom32Def(DefInsn))
144 } else if (DefInsn->getOpcode() == BPF::COPY) {
145 if (!isCopyFrom32Def(DefInsn))
152 bool BPFMIPeephole::isMovFrom32Def(MachineInstr *MovMI)
154 MachineInstr *DefInsn = MRI->getVRegDef(MovMI->getOperand(1).getReg());
156 LLVM_DEBUG(dbgs() << " Def of Mov Src:");
157 LLVM_DEBUG(DefInsn->dump());
160 if (!isInsnFrom32Def(DefInsn))
163 LLVM_DEBUG(dbgs() << " One ZExt elim sequence identified.\n");
168 bool BPFMIPeephole::eliminateZExtSeq(void) {
169 MachineInstr* ToErase = nullptr;
170 bool Eliminated = false;
172 for (MachineBasicBlock &MBB : *MF) {
173 for (MachineInstr &MI : MBB) {
174 // If the previous instruction was marked for elimination, remove it now.
176 ToErase->eraseFromParent();
180 // Eliminate the 32-bit to 64-bit zero extension sequence when possible.
185 if (MI.getOpcode() == BPF::SRL_ri &&
186 MI.getOperand(2).getImm() == 32) {
187 Register DstReg = MI.getOperand(0).getReg();
188 Register ShfReg = MI.getOperand(1).getReg();
189 MachineInstr *SllMI = MRI->getVRegDef(ShfReg);
191 LLVM_DEBUG(dbgs() << "Starting SRL found:");
192 LLVM_DEBUG(MI.dump());
196 SllMI->getOpcode() != BPF::SLL_ri ||
197 SllMI->getOperand(2).getImm() != 32)
200 LLVM_DEBUG(dbgs() << " SLL found:");
201 LLVM_DEBUG(SllMI->dump());
203 MachineInstr *MovMI = MRI->getVRegDef(SllMI->getOperand(1).getReg());
206 MovMI->getOpcode() != BPF::MOV_32_64)
209 LLVM_DEBUG(dbgs() << " Type cast Mov found:");
210 LLVM_DEBUG(MovMI->dump());
212 Register SubReg = MovMI->getOperand(1).getReg();
213 if (!isMovFrom32Def(MovMI)) {
215 << " One ZExt elim sequence failed qualifying elim.\n");
219 BuildMI(MBB, MI, MI.getDebugLoc(), TII->get(BPF::SUBREG_TO_REG), DstReg)
220 .addImm(0).addReg(SubReg).addImm(BPF::sub_32);
222 SllMI->eraseFromParent();
223 MovMI->eraseFromParent();
224 // MI is the right shift, we can't erase it in it's own iteration.
225 // Mark it to ToErase, and erase in the next iteration.
236 } // end default namespace
238 INITIALIZE_PASS(BPFMIPeephole, DEBUG_TYPE,
239 "BPF MachineSSA Peephole Optimization For ZEXT Eliminate",
242 char BPFMIPeephole::ID = 0;
243 FunctionPass* llvm::createBPFMIPeepholePass() { return new BPFMIPeephole(); }
245 STATISTIC(RedundantMovElemNum, "Number of redundant moves eliminated");
249 struct BPFMIPreEmitPeephole : public MachineFunctionPass {
253 const TargetRegisterInfo *TRI;
255 BPFMIPreEmitPeephole() : MachineFunctionPass(ID) {
256 initializeBPFMIPreEmitPeepholePass(*PassRegistry::getPassRegistry());
260 // Initialize class variables.
261 void initialize(MachineFunction &MFParm);
263 bool eliminateRedundantMov(void);
267 // Main entry point for this pass.
268 bool runOnMachineFunction(MachineFunction &MF) override {
269 if (skipFunction(MF.getFunction()))
274 return eliminateRedundantMov();
278 // Initialize class variables.
279 void BPFMIPreEmitPeephole::initialize(MachineFunction &MFParm) {
281 TRI = MF->getSubtarget<BPFSubtarget>().getRegisterInfo();
282 LLVM_DEBUG(dbgs() << "*** BPF PreEmit peephole pass ***\n\n");
285 bool BPFMIPreEmitPeephole::eliminateRedundantMov(void) {
286 MachineInstr* ToErase = nullptr;
287 bool Eliminated = false;
289 for (MachineBasicBlock &MBB : *MF) {
290 for (MachineInstr &MI : MBB) {
291 // If the previous instruction was marked for elimination, remove it now.
293 LLVM_DEBUG(dbgs() << " Redundant Mov Eliminated:");
294 LLVM_DEBUG(ToErase->dump());
295 ToErase->eraseFromParent();
299 // Eliminate identical move:
303 // This is particularly possible to happen when sub-register support
304 // enabled. The special type cast insn MOV_32_64 involves different
305 // register class on src (i32) and dst (i64), RA could generate useless
306 // instruction due to this.
307 unsigned Opcode = MI.getOpcode();
308 if (Opcode == BPF::MOV_32_64 ||
309 Opcode == BPF::MOV_rr || Opcode == BPF::MOV_rr_32) {
310 Register dst = MI.getOperand(0).getReg();
311 Register src = MI.getOperand(1).getReg();
313 if (Opcode == BPF::MOV_32_64)
314 dst = TRI->getSubReg(dst, BPF::sub_32);
320 RedundantMovElemNum++;
329 } // end default namespace
331 INITIALIZE_PASS(BPFMIPreEmitPeephole, "bpf-mi-pemit-peephole",
332 "BPF PreEmit Peephole Optimization", false, false)
334 char BPFMIPreEmitPeephole::ID = 0;
335 FunctionPass* llvm::createBPFMIPreEmitPeepholePass()
337 return new BPFMIPreEmitPeephole();
340 STATISTIC(TruncElemNum, "Number of truncation eliminated");
344 struct BPFMIPeepholeTruncElim : public MachineFunctionPass {
347 const BPFInstrInfo *TII;
349 MachineRegisterInfo *MRI;
351 BPFMIPeepholeTruncElim() : MachineFunctionPass(ID) {
352 initializeBPFMIPeepholeTruncElimPass(*PassRegistry::getPassRegistry());
356 // Initialize class variables.
357 void initialize(MachineFunction &MFParm);
359 bool eliminateTruncSeq(void);
363 // Main entry point for this pass.
364 bool runOnMachineFunction(MachineFunction &MF) override {
365 if (skipFunction(MF.getFunction()))
370 return eliminateTruncSeq();
374 static bool TruncSizeCompatible(int TruncSize, unsigned opcode)
377 return opcode == BPF::LDB || opcode == BPF::LDB32;
380 return opcode == BPF::LDH || opcode == BPF::LDH32;
383 return opcode == BPF::LDW || opcode == BPF::LDW32;
388 // Initialize class variables.
389 void BPFMIPeepholeTruncElim::initialize(MachineFunction &MFParm) {
391 MRI = &MF->getRegInfo();
392 TII = MF->getSubtarget<BPFSubtarget>().getInstrInfo();
393 LLVM_DEBUG(dbgs() << "*** BPF MachineSSA TRUNC Elim peephole pass ***\n\n");
396 // Reg truncating is often the result of 8/16/32bit->64bit or
397 // 8/16bit->32bit conversion. If the reg value is loaded with
398 // masked byte width, the AND operation can be removed since
399 // BPF LOAD already has zero extension.
401 // This also solved a correctness issue.
402 // In BPF socket-related program, e.g., __sk_buff->{data, data_end}
403 // are 32-bit registers, but later on, kernel verifier will rewrite
404 // it with 64-bit value. Therefore, truncating the value after the
405 // load will result in incorrect code.
406 bool BPFMIPeepholeTruncElim::eliminateTruncSeq(void) {
407 MachineInstr* ToErase = nullptr;
408 bool Eliminated = false;
410 for (MachineBasicBlock &MBB : *MF) {
411 for (MachineInstr &MI : MBB) {
412 // The second insn to remove if the eliminate candidate is a pair.
413 MachineInstr *MI2 = nullptr;
414 Register DstReg, SrcReg;
418 // If the previous instruction was marked for elimination, remove it now.
420 ToErase->eraseFromParent();
424 // AND A, 0xFFFFFFFF will be turned into SLL/SRL pair due to immediate
425 // for BPF ANDI is i32, and this case only happens on ALU64.
426 if (MI.getOpcode() == BPF::SRL_ri &&
427 MI.getOperand(2).getImm() == 32) {
428 SrcReg = MI.getOperand(1).getReg();
429 MI2 = MRI->getVRegDef(SrcReg);
430 DstReg = MI.getOperand(0).getReg();
433 MI2->getOpcode() != BPF::SLL_ri ||
434 MI2->getOperand(2).getImm() != 32)
438 SrcReg = MI2->getOperand(1).getReg();
439 DefMI = MRI->getVRegDef(SrcReg);
442 } else if (MI.getOpcode() == BPF::AND_ri ||
443 MI.getOpcode() == BPF::AND_ri_32) {
444 SrcReg = MI.getOperand(1).getReg();
445 DstReg = MI.getOperand(0).getReg();
446 DefMI = MRI->getVRegDef(SrcReg);
451 int64_t imm = MI.getOperand(2).getImm();
454 else if (imm == 0xffff)
461 // The definition is PHI node, check all inputs.
462 if (DefMI->isPHI()) {
463 bool CheckFail = false;
465 for (unsigned i = 1, e = DefMI->getNumOperands(); i < e; i += 2) {
466 MachineOperand &opnd = DefMI->getOperand(i);
472 MachineInstr *PhiDef = MRI->getVRegDef(opnd.getReg());
473 if (!PhiDef || PhiDef->isPHI() ||
474 !TruncSizeCompatible(TruncSize, PhiDef->getOpcode())) {
482 } else if (!TruncSizeCompatible(TruncSize, DefMI->getOpcode())) {
486 BuildMI(MBB, MI, MI.getDebugLoc(), TII->get(BPF::MOV_rr), DstReg)
490 MI2->eraseFromParent();
492 // Mark it to ToErase, and erase in the next iteration.
502 } // end default namespace
504 INITIALIZE_PASS(BPFMIPeepholeTruncElim, "bpf-mi-trunc-elim",
505 "BPF MachineSSA Peephole Optimization For TRUNC Eliminate",
508 char BPFMIPeepholeTruncElim::ID = 0;
509 FunctionPass* llvm::createBPFMIPeepholeTruncElimPass()
511 return new BPFMIPeepholeTruncElim();