llvm/lib/Target/RISCV/RISCVRedundantCopyElimination.cpp

   1 //=- RISCVRedundantCopyElimination.cpp - Remove useless copy for RISC-V -----=//
   2 //
   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
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This pass removes unnecessary zero copies in BBs that are targets of
  10 // beqz/bnez instructions. For instance, the copy instruction in the code below
  11 // can be removed because the beqz jumps to BB#2 when a0 is zero.
  12 //  BB#1:
  13 //    beqz %a0, <BB#2>
  14 //  BB#2:
  15 //    %a0 = COPY %x0
  16 // This pass should be run after register allocation.
  17 //
  18 // This pass is based on the earliest versions of
  19 // AArch64RedundantCopyElimination.
  20 //
  21 // FIXME: Support compares with constants other than zero? This is harder to
  22 // do on RISC-V since branches can't have immediates.
  23 //
  24 //===----------------------------------------------------------------------===//
  25
  26 #include "RISCV.h"
  27 #include "RISCVInstrInfo.h"
  28 #include "llvm/ADT/Statistic.h"
  29 #include "llvm/CodeGen/MachineFunctionPass.h"
  30 #include "llvm/CodeGen/MachineRegisterInfo.h"
  31 #include "llvm/Support/Debug.h"
  32
  33 using namespace llvm;
  34
  35 #define DEBUG_TYPE "riscv-copyelim"
  36
  37 STATISTIC(NumCopiesRemoved, "Number of copies removed.");
  38
  39 namespace {
  40 class RISCVRedundantCopyElimination : public MachineFunctionPass {
  41   const MachineRegisterInfo *MRI;
  42   const TargetRegisterInfo *TRI;
  43   const TargetInstrInfo *TII;
  44
  45 public:
  46   static char ID;
  47   RISCVRedundantCopyElimination() : MachineFunctionPass(ID) {
  48     initializeRISCVRedundantCopyEliminationPass(
  49         *PassRegistry::getPassRegistry());
  50   }
  51
  52   bool runOnMachineFunction(MachineFunction &MF) override;
  53   MachineFunctionProperties getRequiredProperties() const override {
  54     return MachineFunctionProperties().set(
  55         MachineFunctionProperties::Property::NoVRegs);
  56   }
  57
  58   StringRef getPassName() const override {
  59     return "RISC-V Redundant Copy Elimination";
  60   }
  61
  62 private:
  63   bool optimizeBlock(MachineBasicBlock &MBB);
  64 };
  65
  66 } // end anonymous namespace
  67
  68 char RISCVRedundantCopyElimination::ID = 0;
  69
  70 INITIALIZE_PASS(RISCVRedundantCopyElimination, "riscv-copyelim",
  71                 "RISC-V Redundant Copy Elimination", false, false)
  72
  73 static bool
  74 guaranteesZeroRegInBlock(MachineBasicBlock &MBB,
  75                          const SmallVectorImpl<MachineOperand> &Cond,
  76                          MachineBasicBlock *TBB) {
  77   assert(Cond.size() == 3 && "Unexpected number of operands");
  78   assert(TBB != nullptr && "Expected branch target basic block");
  79   auto CC = static_cast<RISCVCC::CondCode>(Cond[0].getImm());
  80   if (CC == RISCVCC::COND_EQ && Cond[2].isReg() &&
  81       Cond[2].getReg() == RISCV::X0 && TBB == &MBB)
  82     return true;
  83   if (CC == RISCVCC::COND_NE && Cond[2].isReg() &&
  84       Cond[2].getReg() == RISCV::X0 && TBB != &MBB)
  85     return true;
  86   return false;
  87 }
  88
  89 bool RISCVRedundantCopyElimination::optimizeBlock(MachineBasicBlock &MBB) {
  90   // Check if the current basic block has a single predecessor.
  91   if (MBB.pred_size() != 1)
  92     return false;
  93
  94   // Check if the predecessor has two successors, implying the block ends in a
  95   // conditional branch.
  96   MachineBasicBlock *PredMBB = *MBB.pred_begin();
  97   if (PredMBB->succ_size() != 2)
  98     return false;
  99
 100   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
 101   SmallVector<MachineOperand, 3> Cond;
 102   if (TII->analyzeBranch(*PredMBB, TBB, FBB, Cond, /*AllowModify*/ false) ||
 103       Cond.empty())
 104     return false;
 105
 106   // Is this a branch with X0?
 107   if (!guaranteesZeroRegInBlock(MBB, Cond, TBB))
 108     return false;
 109
 110   Register TargetReg = Cond[1].getReg();
 111   if (!TargetReg)
 112     return false;
 113
 114   bool Changed = false;
 115   MachineBasicBlock::iterator LastChange = MBB.begin();
 116   // Remove redundant Copy instructions unless TargetReg is modified.
 117   for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
 118     MachineInstr *MI = &*I;
 119     ++I;
 120     if (MI->isCopy() && MI->getOperand(0).isReg() &&
 121         MI->getOperand(1).isReg()) {
 122       Register DefReg = MI->getOperand(0).getReg();
 123       Register SrcReg = MI->getOperand(1).getReg();
 124
 125       if (SrcReg == RISCV::X0 && !MRI->isReserved(DefReg) &&
 126           TargetReg == DefReg) {
 127         LLVM_DEBUG(dbgs() << "Remove redundant Copy : ");
 128         LLVM_DEBUG(MI->print(dbgs()));
 129
 130         MI->eraseFromParent();
 131         Changed = true;
 132         LastChange = I;
 133         ++NumCopiesRemoved;
 134         continue;
 135       }
 136     }
 137
 138     if (MI->modifiesRegister(TargetReg, TRI))
 139       break;
 140   }
 141
 142   if (!Changed)
 143     return false;
 144
 145   MachineBasicBlock::iterator CondBr = PredMBB->getFirstTerminator();
 146   assert((CondBr->getOpcode() == RISCV::BEQ ||
 147           CondBr->getOpcode() == RISCV::BNE) &&
 148          "Unexpected opcode");
 149   assert(CondBr->getOperand(0).getReg() == TargetReg && "Unexpected register");
 150
 151   // Otherwise, we have to fixup the use-def chain, starting with the
 152   // BEQ/BNE. Conservatively mark as much as we can live.
 153   CondBr->clearRegisterKills(TargetReg, TRI);
 154
 155   // Add newly used reg to the block's live-in list if it isn't there already.
 156   if (!MBB.isLiveIn(TargetReg))
 157     MBB.addLiveIn(TargetReg);
 158
 159   // Clear any kills of TargetReg between CondBr and the last removed COPY.
 160   for (MachineInstr &MMI : make_range(MBB.begin(), LastChange))
 161     MMI.clearRegisterKills(TargetReg, TRI);
 162
 163   return true;
 164 }
 165
 166 bool RISCVRedundantCopyElimination::runOnMachineFunction(MachineFunction &MF) {
 167   if (skipFunction(MF.getFunction()))
 168     return false;
 169
 170   TII = MF.getSubtarget().getInstrInfo();
 171   TRI = MF.getSubtarget().getRegisterInfo();
 172   MRI = &MF.getRegInfo();
 173
 174   bool Changed = false;
 175   for (MachineBasicBlock &MBB : MF)
 176     Changed |= optimizeBlock(MBB);
 177
 178   return Changed;
 179 }
 180
 181 FunctionPass *llvm::createRISCVRedundantCopyEliminationPass() {
 182   return new RISCVRedundantCopyElimination();
 183 }