blob: 022267fbe3c2156a2cbf40816b4f873a4b62974d [file] [log] [blame]
//===-------------- 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"
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);
std::set<MachineInstr *> PhiInsns;
public:
// Main entry point for this pass.
bool runOnMachineFunction(MachineFunction &MF) override {
if (skipFunction(MF.getFunction()))
return false;
initialize(MF);
return eliminateZExtSeq();
}
};
// 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;
}
} // 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
//
// This is particularly possible to happen when sub-register support
// enabled. The special type cast insn MOV_32_64 involves different
// register class on src (i32) and dst (i64), RA could generate useless
// instruction due to this.
unsigned Opcode = MI.getOpcode();
if (Opcode == BPF::MOV_32_64 ||
Opcode == BPF::MOV_rr || Opcode == BPF::MOV_rr_32) {
Register dst = MI.getOperand(0).getReg();
Register src = MI.getOperand(1).getReg();
if (Opcode == BPF::MOV_32_64)
dst = TRI->getSubReg(dst, BPF::sub_32);
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();
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();
}