llvm/lib/Target/BPF/BPFMIPeephole.cpp - llvm-project - Git at Google

 //===-------------- BPFMIPeephole.cpp - MI Peephole Cleanups  -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass performs peephole optimizations to cleanup ugly code sequences at
 // MachineInstruction layer.
 //
 // Currently, there are two optimizations implemented:
 //  - One pre-RA MachineSSA pass to eliminate type promotion sequences, those
 //    zero extend 32-bit subregisters to 64-bit registers, if the compiler
 //    could prove the subregisters is defined by 32-bit operations in which
 //    case the upper half of the underlying 64-bit registers were zeroed
 //    implicitly.
 //
 //  - One post-RA PreEmit pass to do final cleanup on some redundant
 //    instructions generated due to bad RA on subregister.
 //===----------------------------------------------------------------------===//

 #include "BPF.h"
 #include "BPFInstrInfo.h"
 #include "BPFTargetMachine.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Support/Debug.h"
 #include <set>

 using namespace llvm;

 #define DEBUG_TYPE "bpf-mi-zext-elim"

 STATISTIC(ZExtElemNum, "Number of zero extension shifts eliminated");

 namespace {

 struct BPFMIPeephole : public MachineFunctionPass {

   static char ID;
   const BPFInstrInfo *TII;
   MachineFunction *MF;
   MachineRegisterInfo *MRI;

   BPFMIPeephole() : MachineFunctionPass(ID) {
     initializeBPFMIPeepholePass(*PassRegistry::getPassRegistry());
   }

 private:
   // Initialize class variables.
   void initialize(MachineFunction &MFParm);

   bool isCopyFrom32Def(MachineInstr *CopyMI);
   bool isInsnFrom32Def(MachineInstr *DefInsn);
   bool isPhiFrom32Def(MachineInstr *MovMI);
   bool isMovFrom32Def(MachineInstr *MovMI);
   bool eliminateZExtSeq(void);
   bool eliminateZExt(void);

   std::set<MachineInstr *> PhiInsns;

 public:

   // Main entry point for this pass.
   bool runOnMachineFunction(MachineFunction &MF) override {
     if (skipFunction(MF.getFunction()))
       return false;

     initialize(MF);

     // First try to eliminate (zext, lshift, rshift) and then
     // try to eliminate zext.
     bool ZExtSeqExist, ZExtExist;
     ZExtSeqExist = eliminateZExtSeq();
     ZExtExist = eliminateZExt();
     return ZExtSeqExist || ZExtExist;
   }
 };

 // Initialize class variables.
 void BPFMIPeephole::initialize(MachineFunction &MFParm) {
   MF = &MFParm;
   MRI = &MF->getRegInfo();
   TII = MF->getSubtarget<BPFSubtarget>().getInstrInfo();
   LLVM_DEBUG(dbgs() << "*** BPF MachineSSA ZEXT Elim peephole pass ***\n\n");
 }

 bool BPFMIPeephole::isCopyFrom32Def(MachineInstr *CopyMI)
 {
   MachineOperand &opnd = CopyMI->getOperand(1);

   if (!opnd.isReg())
     return false;

   // Return false if getting value from a 32bit physical register.
   // Most likely, this physical register is aliased to
   // function call return value or current function parameters.
   Register Reg = opnd.getReg();
   if (!Register::isVirtualRegister(Reg))
     return false;

   if (MRI->getRegClass(Reg) == &BPF::GPRRegClass)
     return false;

   MachineInstr *DefInsn = MRI->getVRegDef(Reg);
   if (!isInsnFrom32Def(DefInsn))
     return false;

   return true;
 }

 bool BPFMIPeephole::isPhiFrom32Def(MachineInstr *PhiMI)
 {
   for (unsigned i = 1, e = PhiMI->getNumOperands(); i < e; i += 2) {
     MachineOperand &opnd = PhiMI->getOperand(i);

     if (!opnd.isReg())
       return false;

     MachineInstr *PhiDef = MRI->getVRegDef(opnd.getReg());
     if (!PhiDef)
       return false;
     if (PhiDef->isPHI()) {
       if (PhiInsns.find(PhiDef) != PhiInsns.end())
         return false;
       PhiInsns.insert(PhiDef);
       if (!isPhiFrom32Def(PhiDef))
         return false;
     }
     if (PhiDef->getOpcode() == BPF::COPY && !isCopyFrom32Def(PhiDef))
       return false;
   }

   return true;
 }

 // The \p DefInsn instruction defines a virtual register.
 bool BPFMIPeephole::isInsnFrom32Def(MachineInstr *DefInsn)
 {
   if (!DefInsn)
     return false;

   if (DefInsn->isPHI()) {
     if (PhiInsns.find(DefInsn) != PhiInsns.end())
       return false;
     PhiInsns.insert(DefInsn);
     if (!isPhiFrom32Def(DefInsn))
       return false;
   } else if (DefInsn->getOpcode() == BPF::COPY) {
     if (!isCopyFrom32Def(DefInsn))
       return false;
   }

   return true;
 }

 bool BPFMIPeephole::isMovFrom32Def(MachineInstr *MovMI)
 {
   MachineInstr *DefInsn = MRI->getVRegDef(MovMI->getOperand(1).getReg());

   LLVM_DEBUG(dbgs() << "  Def of Mov Src:");
   LLVM_DEBUG(DefInsn->dump());

   PhiInsns.clear();
   if (!isInsnFrom32Def(DefInsn))
     return false;

   LLVM_DEBUG(dbgs() << "  One ZExt elim sequence identified.\n");

   return true;
 }

 bool BPFMIPeephole::eliminateZExtSeq(void) {
   MachineInstr* ToErase = nullptr;
   bool Eliminated = false;

   for (MachineBasicBlock &MBB : *MF) {
     for (MachineInstr &MI : MBB) {
       // If the previous instruction was marked for elimination, remove it now.
       if (ToErase) {
         ToErase->eraseFromParent();
         ToErase = nullptr;
       }

       // Eliminate the 32-bit to 64-bit zero extension sequence when possible.
       //
       //   MOV_32_64 rB, wA
       //   SLL_ri    rB, rB, 32
       //   SRL_ri    rB, rB, 32
       if (MI.getOpcode() == BPF::SRL_ri &&
           MI.getOperand(2).getImm() == 32) {
         Register DstReg = MI.getOperand(0).getReg();
         Register ShfReg = MI.getOperand(1).getReg();
         MachineInstr *SllMI = MRI->getVRegDef(ShfReg);

         LLVM_DEBUG(dbgs() << "Starting SRL found:");
         LLVM_DEBUG(MI.dump());

         if (!SllMI ||
             SllMI->isPHI() ||
             SllMI->getOpcode() != BPF::SLL_ri ||
             SllMI->getOperand(2).getImm() != 32)
           continue;

         LLVM_DEBUG(dbgs() << "  SLL found:");
         LLVM_DEBUG(SllMI->dump());

         MachineInstr *MovMI = MRI->getVRegDef(SllMI->getOperand(1).getReg());
         if (!MovMI ||
             MovMI->isPHI() ||
             MovMI->getOpcode() != BPF::MOV_32_64)
           continue;

         LLVM_DEBUG(dbgs() << "  Type cast Mov found:");
         LLVM_DEBUG(MovMI->dump());

         Register SubReg = MovMI->getOperand(1).getReg();
         if (!isMovFrom32Def(MovMI)) {
           LLVM_DEBUG(dbgs()
                      << "  One ZExt elim sequence failed qualifying elim.\n");
           continue;
         }

         BuildMI(MBB, MI, MI.getDebugLoc(), TII->get(BPF::SUBREG_TO_REG), DstReg)
           .addImm(0).addReg(SubReg).addImm(BPF::sub_32);

         SllMI->eraseFromParent();
         MovMI->eraseFromParent();
         // MI is the right shift, we can't erase it in it's own iteration.
         // Mark it to ToErase, and erase in the next iteration.
         ToErase = &MI;
         ZExtElemNum++;
         Eliminated = true;
       }
     }
   }

   return Eliminated;
 }

 bool BPFMIPeephole::eliminateZExt(void) {
   MachineInstr* ToErase = nullptr;
   bool Eliminated = false;

   for (MachineBasicBlock &MBB : *MF) {
     for (MachineInstr &MI : MBB) {
       // If the previous instruction was marked for elimination, remove it now.
       if (ToErase) {
         ToErase->eraseFromParent();
         ToErase = nullptr;
       }

       if (MI.getOpcode() != BPF::MOV_32_64)
         continue;

       // Eliminate MOV_32_64 if possible.
       //   MOV_32_64 rA, wB
       //
       // If wB has been zero extended, replace it with a SUBREG_TO_REG.
       // This is to workaround BPF programs where pkt->{data, data_end}
       // is encoded as u32, but actually the verifier populates them
       // as 64bit pointer. The MOV_32_64 will zero out the top 32 bits.
       LLVM_DEBUG(dbgs() << "Candidate MOV_32_64 instruction:");
       LLVM_DEBUG(MI.dump());

       if (!isMovFrom32Def(&MI))
         continue;

       LLVM_DEBUG(dbgs() << "Removing the MOV_32_64 instruction\n");

       Register dst = MI.getOperand(0).getReg();
       Register src = MI.getOperand(1).getReg();

       // Build a SUBREG_TO_REG instruction.
       BuildMI(MBB, MI, MI.getDebugLoc(), TII->get(BPF::SUBREG_TO_REG), dst)
         .addImm(0).addReg(src).addImm(BPF::sub_32);

       ToErase = &MI;
       Eliminated = true;
     }
   }

   return Eliminated;
 }

 } // end default namespace

 INITIALIZE_PASS(BPFMIPeephole, DEBUG_TYPE,
                 "BPF MachineSSA Peephole Optimization For ZEXT Eliminate",
                 false, false)

 char BPFMIPeephole::ID = 0;
 FunctionPass* llvm::createBPFMIPeepholePass() { return new BPFMIPeephole(); }

 STATISTIC(RedundantMovElemNum, "Number of redundant moves eliminated");

 namespace {

 struct BPFMIPreEmitPeephole : public MachineFunctionPass {

   static char ID;
   MachineFunction *MF;
   const TargetRegisterInfo *TRI;

   BPFMIPreEmitPeephole() : MachineFunctionPass(ID) {
     initializeBPFMIPreEmitPeepholePass(*PassRegistry::getPassRegistry());
   }

 private:
   // Initialize class variables.
   void initialize(MachineFunction &MFParm);

   bool eliminateRedundantMov(void);

 public:

   // Main entry point for this pass.
   bool runOnMachineFunction(MachineFunction &MF) override {
     if (skipFunction(MF.getFunction()))
       return false;

     initialize(MF);

     return eliminateRedundantMov();
   }
 };

 // Initialize class variables.
 void BPFMIPreEmitPeephole::initialize(MachineFunction &MFParm) {
   MF = &MFParm;
   TRI = MF->getSubtarget<BPFSubtarget>().getRegisterInfo();
   LLVM_DEBUG(dbgs() << "*** BPF PreEmit peephole pass ***\n\n");
 }

 bool BPFMIPreEmitPeephole::eliminateRedundantMov(void) {
   MachineInstr* ToErase = nullptr;
   bool Eliminated = false;

   for (MachineBasicBlock &MBB : *MF) {
     for (MachineInstr &MI : MBB) {
       // If the previous instruction was marked for elimination, remove it now.
       if (ToErase) {
         LLVM_DEBUG(dbgs() << "  Redundant Mov Eliminated:");
         LLVM_DEBUG(ToErase->dump());
         ToErase->eraseFromParent();
         ToErase = nullptr;
       }

       // Eliminate identical move:
       //
       //   MOV rA, rA
       //
       // Note that we cannot remove
       //   MOV_32_64  rA, wA
       //   MOV_rr_32  wA, wA
       // as these two instructions having side effects, zeroing out
       // top 32 bits of rA.
       unsigned Opcode = MI.getOpcode();
       if (Opcode == BPF::MOV_rr) {
         Register dst = MI.getOperand(0).getReg();
         Register src = MI.getOperand(1).getReg();

         if (dst != src)
           continue;

         ToErase = &MI;
         RedundantMovElemNum++;
         Eliminated = true;
       }
     }
   }

   return Eliminated;
 }

 } // end default namespace

 INITIALIZE_PASS(BPFMIPreEmitPeephole, "bpf-mi-pemit-peephole",
                 "BPF PreEmit Peephole Optimization", false, false)

 char BPFMIPreEmitPeephole::ID = 0;
 FunctionPass* llvm::createBPFMIPreEmitPeepholePass()
 {
   return new BPFMIPreEmitPeephole();
 }

 STATISTIC(TruncElemNum, "Number of truncation eliminated");

 namespace {

 struct BPFMIPeepholeTruncElim : public MachineFunctionPass {

   static char ID;
   const BPFInstrInfo *TII;
   MachineFunction *MF;
   MachineRegisterInfo *MRI;

   BPFMIPeepholeTruncElim() : MachineFunctionPass(ID) {
     initializeBPFMIPeepholeTruncElimPass(*PassRegistry::getPassRegistry());
   }

 private:
   // Initialize class variables.
   void initialize(MachineFunction &MFParm);

   bool eliminateTruncSeq(void);

 public:

   // Main entry point for this pass.
   bool runOnMachineFunction(MachineFunction &MF) override {
     if (skipFunction(MF.getFunction()))
       return false;

     initialize(MF);

     return eliminateTruncSeq();
   }
 };

 static bool TruncSizeCompatible(int TruncSize, unsigned opcode)
 {
   if (TruncSize == 1)
     return opcode == BPF::LDB || opcode == BPF::LDB32;

   if (TruncSize == 2)
     return opcode == BPF::LDH || opcode == BPF::LDH32;

   if (TruncSize == 4)
     return opcode == BPF::LDW || opcode == BPF::LDW32;

   return false;
 }

 // Initialize class variables.
 void BPFMIPeepholeTruncElim::initialize(MachineFunction &MFParm) {
   MF = &MFParm;
   MRI = &MF->getRegInfo();
   TII = MF->getSubtarget<BPFSubtarget>().getInstrInfo();
   LLVM_DEBUG(dbgs() << "*** BPF MachineSSA TRUNC Elim peephole pass ***\n\n");
 }

 // Reg truncating is often the result of 8/16/32bit->64bit or
 // 8/16bit->32bit conversion. If the reg value is loaded with
 // masked byte width, the AND operation can be removed since
 // BPF LOAD already has zero extension.
 //
 // This also solved a correctness issue.
 // In BPF socket-related program, e.g., __sk_buff->{data, data_end}
 // are 32-bit registers, but later on, kernel verifier will rewrite
 // it with 64-bit value. Therefore, truncating the value after the
 // load will result in incorrect code.
 bool BPFMIPeepholeTruncElim::eliminateTruncSeq(void) {
   MachineInstr* ToErase = nullptr;
   bool Eliminated = false;

   for (MachineBasicBlock &MBB : *MF) {
     for (MachineInstr &MI : MBB) {
       // The second insn to remove if the eliminate candidate is a pair.
       MachineInstr *MI2 = nullptr;
       Register DstReg, SrcReg;
       MachineInstr *DefMI;
       int TruncSize = -1;

       // If the previous instruction was marked for elimination, remove it now.
       if (ToErase) {
         ToErase->eraseFromParent();
         ToErase = nullptr;
       }

       // AND A, 0xFFFFFFFF will be turned into SLL/SRL pair due to immediate
       // for BPF ANDI is i32, and this case only happens on ALU64.
       if (MI.getOpcode() == BPF::SRL_ri &&
           MI.getOperand(2).getImm() == 32) {
         SrcReg = MI.getOperand(1).getReg();
         if (!MRI->hasOneNonDBGUse(SrcReg))
           continue;

         MI2 = MRI->getVRegDef(SrcReg);
         DstReg = MI.getOperand(0).getReg();

         if (!MI2 ||
             MI2->getOpcode() != BPF::SLL_ri ||
             MI2->getOperand(2).getImm() != 32)
           continue;

         // Update SrcReg.
         SrcReg = MI2->getOperand(1).getReg();
         DefMI = MRI->getVRegDef(SrcReg);
         if (DefMI)
           TruncSize = 4;
       } else if (MI.getOpcode() == BPF::AND_ri ||
                  MI.getOpcode() == BPF::AND_ri_32) {
         SrcReg = MI.getOperand(1).getReg();
         DstReg = MI.getOperand(0).getReg();
         DefMI = MRI->getVRegDef(SrcReg);

         if (!DefMI)
           continue;

         int64_t imm = MI.getOperand(2).getImm();
         if (imm == 0xff)
           TruncSize = 1;
         else if (imm == 0xffff)
           TruncSize = 2;
       }

       if (TruncSize == -1)
         continue;

       // The definition is PHI node, check all inputs.
       if (DefMI->isPHI()) {
         bool CheckFail = false;

         for (unsigned i = 1, e = DefMI->getNumOperands(); i < e; i += 2) {
           MachineOperand &opnd = DefMI->getOperand(i);
           if (!opnd.isReg()) {
             CheckFail = true;
             break;
           }

           MachineInstr *PhiDef = MRI->getVRegDef(opnd.getReg());
           if (!PhiDef || PhiDef->isPHI() ||
               !TruncSizeCompatible(TruncSize, PhiDef->getOpcode())) {
             CheckFail = true;
             break;
           }
         }

         if (CheckFail)
           continue;
       } else if (!TruncSizeCompatible(TruncSize, DefMI->getOpcode())) {
         continue;
       }

       BuildMI(MBB, MI, MI.getDebugLoc(), TII->get(BPF::MOV_rr), DstReg)
               .addReg(SrcReg);

       if (MI2)
         MI2->eraseFromParent();

       // Mark it to ToErase, and erase in the next iteration.
       ToErase = &MI;
       TruncElemNum++;
       Eliminated = true;
     }
   }

   return Eliminated;
 }

 } // end default namespace

 INITIALIZE_PASS(BPFMIPeepholeTruncElim, "bpf-mi-trunc-elim",
                 "BPF MachineSSA Peephole Optimization For TRUNC Eliminate",
                 false, false)

 char BPFMIPeepholeTruncElim::ID = 0;
 FunctionPass* llvm::createBPFMIPeepholeTruncElimPass()
 {
   return new BPFMIPeepholeTruncElim();
 }
	//===-------------- BPFMIPeephole.cpp - MI Peephole Cleanups -------------===//
	//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//
	//===----------------------------------------------------------------------===//
	//
	// This pass performs peephole optimizations to cleanup ugly code sequences at
	// MachineInstruction layer.
	//
	// Currently, there are two optimizations implemented:
	// - One pre-RA MachineSSA pass to eliminate type promotion sequences, those
	// zero extend 32-bit subregisters to 64-bit registers, if the compiler
	// could prove the subregisters is defined by 32-bit operations in which
	// case the upper half of the underlying 64-bit registers were zeroed
	// implicitly.
	//
	// - One post-RA PreEmit pass to do final cleanup on some redundant
	// instructions generated due to bad RA on subregister.
	//===----------------------------------------------------------------------===//

	#include "BPF.h"
	#include "BPFInstrInfo.h"
	#include "BPFTargetMachine.h"
	#include "llvm/ADT/Statistic.h"
	#include "llvm/CodeGen/MachineInstrBuilder.h"
	#include "llvm/CodeGen/MachineRegisterInfo.h"
	#include "llvm/Support/Debug.h"
	#include <set>

	using namespace llvm;

	#define DEBUG_TYPE "bpf-mi-zext-elim"

	STATISTIC(ZExtElemNum, "Number of zero extension shifts eliminated");

	namespace {

	struct BPFMIPeephole : public MachineFunctionPass {

	static char ID;
	const BPFInstrInfo *TII;
	MachineFunction *MF;
	MachineRegisterInfo *MRI;

	BPFMIPeephole() : MachineFunctionPass(ID) {
	initializeBPFMIPeepholePass(*PassRegistry::getPassRegistry());
	}

	private:
	// Initialize class variables.
	void initialize(MachineFunction &MFParm);

	bool isCopyFrom32Def(MachineInstr *CopyMI);
	bool isInsnFrom32Def(MachineInstr *DefInsn);
	bool isPhiFrom32Def(MachineInstr *MovMI);
	bool isMovFrom32Def(MachineInstr *MovMI);
	bool eliminateZExtSeq(void);
	bool eliminateZExt(void);

	std::set<MachineInstr *> PhiInsns;

	public:

	// Main entry point for this pass.
	bool runOnMachineFunction(MachineFunction &MF) override {
	if (skipFunction(MF.getFunction()))
	return false;

	initialize(MF);

	// First try to eliminate (zext, lshift, rshift) and then
	// try to eliminate zext.
	bool ZExtSeqExist, ZExtExist;
	ZExtSeqExist = eliminateZExtSeq();
	ZExtExist = eliminateZExt();
	return ZExtSeqExist \|\| ZExtExist;
	}
	};

	// Initialize class variables.
	void BPFMIPeephole::initialize(MachineFunction &MFParm) {
	MF = &MFParm;
	MRI = &MF->getRegInfo();
	TII = MF->getSubtarget<BPFSubtarget>().getInstrInfo();
	LLVM_DEBUG(dbgs() << "* BPF MachineSSA ZEXT Elim peephole pass *\n\n");
	}

	bool BPFMIPeephole::isCopyFrom32Def(MachineInstr *CopyMI)
	{
	MachineOperand &opnd = CopyMI->getOperand(1);

	if (!opnd.isReg())
	return false;

	// Return false if getting value from a 32bit physical register.
	// Most likely, this physical register is aliased to
	// function call return value or current function parameters.
	Register Reg = opnd.getReg();
	if (!Register::isVirtualRegister(Reg))
	return false;

	if (MRI->getRegClass(Reg) == &BPF::GPRRegClass)
	return false;

	MachineInstr *DefInsn = MRI->getVRegDef(Reg);
	if (!isInsnFrom32Def(DefInsn))
	return false;

	return true;
	}

	bool BPFMIPeephole::isPhiFrom32Def(MachineInstr *PhiMI)
	{
	for (unsigned i = 1, e = PhiMI->getNumOperands(); i < e; i += 2) {
	MachineOperand &opnd = PhiMI->getOperand(i);

	if (!opnd.isReg())
	return false;

	MachineInstr *PhiDef = MRI->getVRegDef(opnd.getReg());
	if (!PhiDef)
	return false;
	if (PhiDef->isPHI()) {
	if (PhiInsns.find(PhiDef) != PhiInsns.end())
	return false;
	PhiInsns.insert(PhiDef);
	if (!isPhiFrom32Def(PhiDef))
	return false;
	}
	if (PhiDef->getOpcode() == BPF::COPY && !isCopyFrom32Def(PhiDef))
	return false;
	}

	return true;
	}

	// The \p DefInsn instruction defines a virtual register.
	bool BPFMIPeephole::isInsnFrom32Def(MachineInstr *DefInsn)
	{
	if (!DefInsn)
	return false;

	if (DefInsn->isPHI()) {
	if (PhiInsns.find(DefInsn) != PhiInsns.end())
	return false;
	PhiInsns.insert(DefInsn);
	if (!isPhiFrom32Def(DefInsn))
	return false;
	} else if (DefInsn->getOpcode() == BPF::COPY) {
	if (!isCopyFrom32Def(DefInsn))
	return false;
	}

	return true;
	}

	bool BPFMIPeephole::isMovFrom32Def(MachineInstr *MovMI)
	{
	MachineInstr *DefInsn = MRI->getVRegDef(MovMI->getOperand(1).getReg());

	LLVM_DEBUG(dbgs() << " Def of Mov Src:");
	LLVM_DEBUG(DefInsn->dump());

	PhiInsns.clear();
	if (!isInsnFrom32Def(DefInsn))
	return false;

	LLVM_DEBUG(dbgs() << " One ZExt elim sequence identified.\n");

	return true;
	}

	bool BPFMIPeephole::eliminateZExtSeq(void) {
	MachineInstr* ToErase = nullptr;
	bool Eliminated = false;

	for (MachineBasicBlock &MBB : *MF) {
	for (MachineInstr &MI : MBB) {
	// If the previous instruction was marked for elimination, remove it now.
	if (ToErase) {
	ToErase->eraseFromParent();
	ToErase = nullptr;
	}

	// Eliminate the 32-bit to 64-bit zero extension sequence when possible.
	//
	// MOV_32_64 rB, wA
	// SLL_ri rB, rB, 32
	// SRL_ri rB, rB, 32
	if (MI.getOpcode() == BPF::SRL_ri &&
	MI.getOperand(2).getImm() == 32) {
	Register DstReg = MI.getOperand(0).getReg();
	Register ShfReg = MI.getOperand(1).getReg();
	MachineInstr *SllMI = MRI->getVRegDef(ShfReg);

	LLVM_DEBUG(dbgs() << "Starting SRL found:");
	LLVM_DEBUG(MI.dump());

	if (!SllMI \|\|
	SllMI->isPHI() \|\|
	SllMI->getOpcode() != BPF::SLL_ri \|\|
	SllMI->getOperand(2).getImm() != 32)
	continue;

	LLVM_DEBUG(dbgs() << " SLL found:");
	LLVM_DEBUG(SllMI->dump());

	MachineInstr *MovMI = MRI->getVRegDef(SllMI->getOperand(1).getReg());
	if (!MovMI \|\|
	MovMI->isPHI() \|\|
	MovMI->getOpcode() != BPF::MOV_32_64)
	continue;

	LLVM_DEBUG(dbgs() << " Type cast Mov found:");
	LLVM_DEBUG(MovMI->dump());

	Register SubReg = MovMI->getOperand(1).getReg();
	if (!isMovFrom32Def(MovMI)) {
	LLVM_DEBUG(dbgs()
	<< " One ZExt elim sequence failed qualifying elim.\n");
	continue;
	}

	BuildMI(MBB, MI, MI.getDebugLoc(), TII->get(BPF::SUBREG_TO_REG), DstReg)
	.addImm(0).addReg(SubReg).addImm(BPF::sub_32);

	SllMI->eraseFromParent();
	MovMI->eraseFromParent();
	// MI is the right shift, we can't erase it in it's own iteration.
	// Mark it to ToErase, and erase in the next iteration.
	ToErase = &MI;
	ZExtElemNum++;
	Eliminated = true;
	}
	}
	}

	return Eliminated;
	}

	bool BPFMIPeephole::eliminateZExt(void) {
	MachineInstr* ToErase = nullptr;
	bool Eliminated = false;

	for (MachineBasicBlock &MBB : *MF) {
	for (MachineInstr &MI : MBB) {
	// If the previous instruction was marked for elimination, remove it now.
	if (ToErase) {
	ToErase->eraseFromParent();
	ToErase = nullptr;
	}

	if (MI.getOpcode() != BPF::MOV_32_64)
	continue;

	// Eliminate MOV_32_64 if possible.
	// MOV_32_64 rA, wB
	//
	// If wB has been zero extended, replace it with a SUBREG_TO_REG.
	// This is to workaround BPF programs where pkt->{data, data_end}
	// is encoded as u32, but actually the verifier populates them
	// as 64bit pointer. The MOV_32_64 will zero out the top 32 bits.
	LLVM_DEBUG(dbgs() << "Candidate MOV_32_64 instruction:");
	LLVM_DEBUG(MI.dump());

	if (!isMovFrom32Def(&MI))
	continue;

	LLVM_DEBUG(dbgs() << "Removing the MOV_32_64 instruction\n");

	Register dst = MI.getOperand(0).getReg();
	Register src = MI.getOperand(1).getReg();

	// Build a SUBREG_TO_REG instruction.
	BuildMI(MBB, MI, MI.getDebugLoc(), TII->get(BPF::SUBREG_TO_REG), dst)
	.addImm(0).addReg(src).addImm(BPF::sub_32);

	ToErase = &MI;
	Eliminated = true;
	}
	}

	return Eliminated;
	}

	} // end default namespace

	INITIALIZE_PASS(BPFMIPeephole, DEBUG_TYPE,
	"BPF MachineSSA Peephole Optimization For ZEXT Eliminate",
	false, false)

	char BPFMIPeephole::ID = 0;
	FunctionPass* llvm::createBPFMIPeepholePass() { return new BPFMIPeephole(); }

	STATISTIC(RedundantMovElemNum, "Number of redundant moves eliminated");

	namespace {

	struct BPFMIPreEmitPeephole : public MachineFunctionPass {

	static char ID;
	MachineFunction *MF;
	const TargetRegisterInfo *TRI;

	BPFMIPreEmitPeephole() : MachineFunctionPass(ID) {
	initializeBPFMIPreEmitPeepholePass(*PassRegistry::getPassRegistry());
	}

	private:
	// Initialize class variables.
	void initialize(MachineFunction &MFParm);

	bool eliminateRedundantMov(void);

	public:

	// Main entry point for this pass.
	bool runOnMachineFunction(MachineFunction &MF) override {
	if (skipFunction(MF.getFunction()))
	return false;

	initialize(MF);

	return eliminateRedundantMov();
	}
	};

	// Initialize class variables.
	void BPFMIPreEmitPeephole::initialize(MachineFunction &MFParm) {
	MF = &MFParm;
	TRI = MF->getSubtarget<BPFSubtarget>().getRegisterInfo();
	LLVM_DEBUG(dbgs() << "* BPF PreEmit peephole pass *\n\n");
	}

	bool BPFMIPreEmitPeephole::eliminateRedundantMov(void) {
	MachineInstr* ToErase = nullptr;
	bool Eliminated = false;

	for (MachineBasicBlock &MBB : *MF) {
	for (MachineInstr &MI : MBB) {
	// If the previous instruction was marked for elimination, remove it now.
	if (ToErase) {
	LLVM_DEBUG(dbgs() << " Redundant Mov Eliminated:");
	LLVM_DEBUG(ToErase->dump());
	ToErase->eraseFromParent();
	ToErase = nullptr;
	}

	// Eliminate identical move:
	//
	// MOV rA, rA
	//
	// Note that we cannot remove
	// MOV_32_64 rA, wA
	// MOV_rr_32 wA, wA
	// as these two instructions having side effects, zeroing out
	// top 32 bits of rA.
	unsigned Opcode = MI.getOpcode();
	if (Opcode == BPF::MOV_rr) {
	Register dst = MI.getOperand(0).getReg();
	Register src = MI.getOperand(1).getReg();

	if (dst != src)
	continue;

	ToErase = &MI;
	RedundantMovElemNum++;
	Eliminated = true;
	}
	}
	}

	return Eliminated;
	}

	} // end default namespace

	INITIALIZE_PASS(BPFMIPreEmitPeephole, "bpf-mi-pemit-peephole",
	"BPF PreEmit Peephole Optimization", false, false)

	char BPFMIPreEmitPeephole::ID = 0;
	FunctionPass* llvm::createBPFMIPreEmitPeepholePass()
	{
	return new BPFMIPreEmitPeephole();
	}

	STATISTIC(TruncElemNum, "Number of truncation eliminated");

	namespace {

	struct BPFMIPeepholeTruncElim : public MachineFunctionPass {

	static char ID;
	const BPFInstrInfo *TII;
	MachineFunction *MF;
	MachineRegisterInfo *MRI;

	BPFMIPeepholeTruncElim() : MachineFunctionPass(ID) {
	initializeBPFMIPeepholeTruncElimPass(*PassRegistry::getPassRegistry());
	}

	private:
	// Initialize class variables.
	void initialize(MachineFunction &MFParm);

	bool eliminateTruncSeq(void);

	public:

	// Main entry point for this pass.
	bool runOnMachineFunction(MachineFunction &MF) override {
	if (skipFunction(MF.getFunction()))
	return false;

	initialize(MF);

	return eliminateTruncSeq();
	}
	};

	static bool TruncSizeCompatible(int TruncSize, unsigned opcode)
	{
	if (TruncSize == 1)
	return opcode == BPF::LDB \|\| opcode == BPF::LDB32;

	if (TruncSize == 2)
	return opcode == BPF::LDH \|\| opcode == BPF::LDH32;

	if (TruncSize == 4)
	return opcode == BPF::LDW \|\| opcode == BPF::LDW32;

	return false;
	}

	// Initialize class variables.
	void BPFMIPeepholeTruncElim::initialize(MachineFunction &MFParm) {
	MF = &MFParm;
	MRI = &MF->getRegInfo();
	TII = MF->getSubtarget<BPFSubtarget>().getInstrInfo();
	LLVM_DEBUG(dbgs() << "* BPF MachineSSA TRUNC Elim peephole pass *\n\n");
	}

	// Reg truncating is often the result of 8/16/32bit->64bit or
	// 8/16bit->32bit conversion. If the reg value is loaded with
	// masked byte width, the AND operation can be removed since
	// BPF LOAD already has zero extension.
	//
	// This also solved a correctness issue.
	// In BPF socket-related program, e.g., __sk_buff->{data, data_end}
	// are 32-bit registers, but later on, kernel verifier will rewrite
	// it with 64-bit value. Therefore, truncating the value after the
	// load will result in incorrect code.
	bool BPFMIPeepholeTruncElim::eliminateTruncSeq(void) {
	MachineInstr* ToErase = nullptr;
	bool Eliminated = false;

	for (MachineBasicBlock &MBB : *MF) {
	for (MachineInstr &MI : MBB) {
	// The second insn to remove if the eliminate candidate is a pair.
	MachineInstr *MI2 = nullptr;
	Register DstReg, SrcReg;
	MachineInstr *DefMI;
	int TruncSize = -1;

	// If the previous instruction was marked for elimination, remove it now.
	if (ToErase) {
	ToErase->eraseFromParent();
	ToErase = nullptr;
	}

	// AND A, 0xFFFFFFFF will be turned into SLL/SRL pair due to immediate
	// for BPF ANDI is i32, and this case only happens on ALU64.
	if (MI.getOpcode() == BPF::SRL_ri &&
	MI.getOperand(2).getImm() == 32) {
	SrcReg = MI.getOperand(1).getReg();
	if (!MRI->hasOneNonDBGUse(SrcReg))
	continue;

	MI2 = MRI->getVRegDef(SrcReg);
	DstReg = MI.getOperand(0).getReg();

	if (!MI2 \|\|
	MI2->getOpcode() != BPF::SLL_ri \|\|
	MI2->getOperand(2).getImm() != 32)
	continue;

	// Update SrcReg.
	SrcReg = MI2->getOperand(1).getReg();
	DefMI = MRI->getVRegDef(SrcReg);
	if (DefMI)
	TruncSize = 4;
	} else if (MI.getOpcode() == BPF::AND_ri \|\|
	MI.getOpcode() == BPF::AND_ri_32) {
	SrcReg = MI.getOperand(1).getReg();
	DstReg = MI.getOperand(0).getReg();
	DefMI = MRI->getVRegDef(SrcReg);

	if (!DefMI)
	continue;

	int64_t imm = MI.getOperand(2).getImm();
	if (imm == 0xff)
	TruncSize = 1;
	else if (imm == 0xffff)
	TruncSize = 2;
	}

	if (TruncSize == -1)
	continue;

	// The definition is PHI node, check all inputs.
	if (DefMI->isPHI()) {
	bool CheckFail = false;

	for (unsigned i = 1, e = DefMI->getNumOperands(); i < e; i += 2) {
	MachineOperand &opnd = DefMI->getOperand(i);
	if (!opnd.isReg()) {
	CheckFail = true;
	break;
	}

	MachineInstr *PhiDef = MRI->getVRegDef(opnd.getReg());
	if (!PhiDef \|\| PhiDef->isPHI() \|\|
	!TruncSizeCompatible(TruncSize, PhiDef->getOpcode())) {
	CheckFail = true;
	break;
	}
	}

	if (CheckFail)
	continue;
	} else if (!TruncSizeCompatible(TruncSize, DefMI->getOpcode())) {
	continue;
	}

	BuildMI(MBB, MI, MI.getDebugLoc(), TII->get(BPF::MOV_rr), DstReg)
	.addReg(SrcReg);

	if (MI2)
	MI2->eraseFromParent();

	// Mark it to ToErase, and erase in the next iteration.
	ToErase = &MI;
	TruncElemNum++;
	Eliminated = true;
	}
	}

	return Eliminated;
	}

	} // end default namespace

	INITIALIZE_PASS(BPFMIPeepholeTruncElim, "bpf-mi-trunc-elim",
	"BPF MachineSSA Peephole Optimization For TRUNC Eliminate",
	false, false)

	char BPFMIPeepholeTruncElim::ID = 0;
	FunctionPass* llvm::createBPFMIPeepholeTruncElimPass()
	{
	return new BPFMIPeepholeTruncElim();
	}