bpf: New optimization pass for eliminating unnecessary i32 promotions

This pass performs peephole optimizations to cleanup ugly code sequences at
MachineInstruction layer.

Currently, the only optimization in this pass is to eliminate type
promotion
sequences for zero extending 32-bit subregisters to 64-bit registers.

If the compiler could prove the zero extended source come from 32-bit
subregistere then it is safe to erase those promotion sequece, because the
upper half of the underlying 64-bit registers were zeroed implicitly
already.

Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
Reviewed-by: Yonghong Song <yhs@fb.com>
llvm-svn: 325991

4 files changed, 197 insertions, 0 deletions

diff --git a/llvm/lib/Target/BPF/BPF.h b/llvm/lib/Target/BPF/BPF.h
index 4a0cb20357c..8b94ba1f4fd 100644
--- a/llvm/lib/Target/BPF/BPF.h
+++ b/llvm/lib/Target/BPF/BPF.h
@@ -17,6 +17,9 @@ namespace llvm {
 class BPFTargetMachine;
 
 FunctionPass *createBPFISelDag(BPFTargetMachine &TM);
+FunctionPass *createBPFMIPeepholePass();
+
+void initializeBPFMIPeepholePass(PassRegistry&);
 }
 
 #endif
diff --git a/llvm/lib/Target/BPF/BPFMIPeephole.cpp b/llvm/lib/Target/BPF/BPFMIPeephole.cpp
new file mode 100644
index 00000000000..80f4437a31c
--- /dev/null
+++ b/llvm/lib/Target/BPF/BPFMIPeephole.cpp
@@ -0,0 +1,175 @@
+//===-------------- BPFMIPeephole.cpp - MI Peephole Cleanups  -------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass performs peephole optimizations to cleanup ugly code sequences at
+// MachineInstruction layer.
+//
+// Currently, the only optimization in this pass is 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.
+//
+//===----------------------------------------------------------------------===//
+
+#include "BPF.h"
+#include "BPFInstrInfo.h"
+#include "BPFTargetMachine.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "bpf-mi-promotion-elim"
+
+STATISTIC(CmpPromotionElemNum, "Number of shifts for CMP promotion 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 eliminateCmpPromotionSeq(void);
+  MachineInstr *getInsnDefZExtSubReg(unsigned Reg) const;
+  void updateInsnSeq(MachineBasicBlock &MBB, MachineInstr &MI,
+                     unsigned Reg) const;
+
+public:
+
+  // Main entry point for this pass.
+  bool runOnMachineFunction(MachineFunction &MF) override {
+    if (skipFunction(MF.getFunction()))
+      return false;
+
+    initialize(MF);
+
+    return eliminateCmpPromotionSeq();
+  }
+};
+
+// Initialize class variables.
+void BPFMIPeephole::initialize(MachineFunction &MFParm) {
+  MF = &MFParm;
+  MRI = &MF->getRegInfo();
+  TII = MF->getSubtarget<BPFSubtarget>().getInstrInfo();
+  DEBUG(dbgs() << "*** BPF MI peephole pass ***\n\n");
+}
+
+MachineInstr *BPFMIPeephole::getInsnDefZExtSubReg(unsigned Reg) const {
+  MachineInstr *Insn = MRI->getVRegDef(Reg);
+
+  if (!Insn ||
+      Insn->isPHI() ||
+      Insn->getOpcode() != BPF::SRL_ri ||
+      Insn->getOperand(2).getImm() != 32)
+    return nullptr;
+
+  Insn = MRI->getVRegDef(Insn->getOperand(1).getReg());
+  if (!Insn ||
+      Insn->isPHI() ||
+      Insn->getOpcode() != BPF::SLL_ri ||
+      Insn->getOperand(2).getImm() != 32)
+    return nullptr;
+
+  Insn = MRI->getVRegDef(Insn->getOperand(1).getReg());
+  if (!Insn ||
+      Insn->isPHI() ||
+      Insn->getOpcode() != BPF::MOV_32_64)
+    return nullptr;
+
+  return Insn;
+}
+
+void
+BPFMIPeephole::updateInsnSeq(MachineBasicBlock &MBB, MachineInstr &MI,
+                             unsigned Reg) const {
+  MachineInstr *Mov, *Lshift, *Rshift;
+  unsigned SubReg;
+  DebugLoc DL;
+
+  Rshift = MRI->getVRegDef(Reg);
+  Lshift = MRI->getVRegDef(Rshift->getOperand(1).getReg());
+  Mov = MRI->getVRegDef(Lshift->getOperand(1).getReg());
+  SubReg = Mov->getOperand(1).getReg();
+  DL = MI.getDebugLoc();
+  BuildMI(MBB, Rshift, DL, TII->get(BPF::SUBREG_TO_REG), Reg)
+    .addImm(0).addReg(SubReg).addImm(BPF::sub_32);
+  Rshift->eraseFromParent();
+  Lshift->eraseFromParent();
+  Mov->eraseFromParent();
+
+  CmpPromotionElemNum++;
+}
+
+bool BPFMIPeephole::eliminateCmpPromotionSeq(void) {
+  bool Eliminated = false;
+  MachineInstr *Mov;
+  unsigned Reg;
+
+  for (MachineBasicBlock &MBB : *MF) {
+    for (MachineInstr &MI : MBB) {
+      switch (MI.getOpcode()) {
+      default:
+        break;
+      case BPF::JUGT_rr:
+      case BPF::JUGE_rr:
+      case BPF::JULT_rr:
+      case BPF::JULE_rr:
+      case BPF::JEQ_rr:
+      case BPF::JNE_rr:
+        Reg = MI.getOperand(1).getReg();
+        Mov = getInsnDefZExtSubReg(Reg);
+        if (!Mov)
+          break;
+
+	updateInsnSeq(MBB, MI, Reg);
+	Eliminated = true;
+
+        // Fallthrough
+      case BPF::JUGT_ri:
+      case BPF::JUGE_ri:
+      case BPF::JULT_ri:
+      case BPF::JULE_ri:
+      case BPF::JEQ_ri:
+      case BPF::JNE_ri:
+        Reg = MI.getOperand(0).getReg();
+        Mov = getInsnDefZExtSubReg(Reg);
+        if (!Mov)
+          break;
+
+	updateInsnSeq(MBB, MI, Reg);
+	Eliminated = true;
+        break;
+      }
+    }
+  }
+
+  return Eliminated;
+}
+
+} // end default namespace
+
+INITIALIZE_PASS(BPFMIPeephole, DEBUG_TYPE, "BPF MI Peephole Optimization",
+                false, false)
+
+char BPFMIPeephole::ID = 0;
+FunctionPass* llvm::createBPFMIPeepholePass() { return new BPFMIPeephole(); }
diff --git a/llvm/lib/Target/BPF/BPFTargetMachine.cpp b/llvm/lib/Target/BPF/BPFTargetMachine.cpp
index 60672fa2684..0114d18599a 100644
--- a/llvm/lib/Target/BPF/BPFTargetMachine.cpp
+++ b/llvm/lib/Target/BPF/BPFTargetMachine.cpp
@@ -22,11 +22,18 @@
 #include "llvm/Target/TargetOptions.h"
 using namespace llvm;
 
+static cl::
+opt<bool> DisableMIPeephole("disable-bpf-peephole", cl::Hidden,
+                            cl::desc("Disable machine peepholes for BPF"));
+
 extern "C" void LLVMInitializeBPFTarget() {
   // Register the target.
   RegisterTargetMachine<BPFTargetMachine> X(getTheBPFleTarget());
   RegisterTargetMachine<BPFTargetMachine> Y(getTheBPFbeTarget());
   RegisterTargetMachine<BPFTargetMachine> Z(getTheBPFTarget());
+
+  PassRegistry &PR = *PassRegistry::getPassRegistry();
+  initializeBPFMIPeepholePass(PR);
 }
 
 // DataLayout: little or big endian
@@ -74,6 +81,7 @@ public:
   }
 
   bool addInstSelector() override;
+  void addMachineSSAOptimization() override;
 };
 }
 
@@ -88,3 +96,13 @@ bool BPFPassConfig::addInstSelector() {
 
   return false;
 }
+
+void BPFPassConfig::addMachineSSAOptimization() {
+  // The default implementation must be called first as we want eBPF
+  // Peephole ran at last.
+  TargetPassConfig::addMachineSSAOptimization();
+
+  const BPFSubtarget *Subtarget = getBPFTargetMachine().getSubtargetImpl();
+  if (Subtarget->getHasAlu32() && !DisableMIPeephole)
+    addPass(createBPFMIPeepholePass());
+}
diff --git a/llvm/lib/Target/BPF/CMakeLists.txt b/llvm/lib/Target/BPF/CMakeLists.txt
index 1e4b685a609..c3d2e48de51 100644
--- a/llvm/lib/Target/BPF/CMakeLists.txt
+++ b/llvm/lib/Target/BPF/CMakeLists.txt
@@ -21,6 +21,7 @@ add_llvm_target(BPFCodeGen
   BPFRegisterInfo.cpp
   BPFSubtarget.cpp
   BPFTargetMachine.cpp
+  BPFMIPeephole.cpp
   )
 
 add_subdirectory(AsmParser)