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].getReg() == RISCV::X0 && TBB == &MBB)
  81     return true;
  82   if (CC == RISCVCC::COND_NE && Cond[2].getReg() == RISCV::X0 && TBB != &MBB)
  83     return true;
  84   return false;
  85 }
  86
  87 bool RISCVRedundantCopyElimination::optimizeBlock(MachineBasicBlock &MBB) {
  88   // Check if the current basic block has a single predecessor.
  89   if (MBB.pred_size() != 1)
  90     return false;
  91
  92   // Check if the predecessor has two successors, implying the block ends in a
  93   // conditional branch.
  94   MachineBasicBlock *PredMBB = *MBB.pred_begin();
  95   if (PredMBB->succ_size() != 2)
  96     return false;
  97
  98   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
  99   SmallVector<MachineOperand, 3> Cond;
 100   if (TII->analyzeBranch(*PredMBB, TBB, FBB, Cond, /*AllowModify*/ false) ||
 101       Cond.empty())
 102     return false;
 103
 104   // Is this a branch with X0?
 105   if (!guaranteesZeroRegInBlock(MBB, Cond, TBB))
 106     return false;
 107
 108   Register TargetReg = Cond[1].getReg();
 109   if (!TargetReg)
 110     return false;
 111
 112   bool Changed = false;
 113   MachineBasicBlock::iterator LastChange = MBB.begin();
 114   // Remove redundant Copy instructions unless TargetReg is modified.
 115   for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
 116     MachineInstr *MI = &*I;
 117     ++I;
 118     if (MI->isCopy() && MI->getOperand(0).isReg() &&
 119         MI->getOperand(1).isReg()) {
 120       Register DefReg = MI->getOperand(0).getReg();
 121       Register SrcReg = MI->getOperand(1).getReg();
 122
 123       if (SrcReg == RISCV::X0 && !MRI->isReserved(DefReg) &&
 124           TargetReg == DefReg) {
 125         LLVM_DEBUG(dbgs() << "Remove redundant Copy : ");
 126         LLVM_DEBUG(MI->print(dbgs()));
 127
 128         MI->eraseFromParent();
 129         Changed = true;
 130         LastChange = I;
 131         ++NumCopiesRemoved;
 132         continue;
 133       }
 134     }
 135
 136     if (MI->modifiesRegister(TargetReg, TRI))
 137       break;
 138   }
 139
 140   if (!Changed)
 141     return false;
 142
 143   MachineBasicBlock::iterator CondBr = PredMBB->getFirstTerminator();
 144   assert((CondBr->getOpcode() == RISCV::BEQ ||
 145           CondBr->getOpcode() == RISCV::BNE) &&
 146          "Unexpected opcode");
 147   assert(CondBr->getOperand(0).getReg() == TargetReg && "Unexpected register");
 148
 149   // Otherwise, we have to fixup the use-def chain, starting with the
 150   // BEQ/BNE. Conservatively mark as much as we can live.
 151   CondBr->clearRegisterKills(TargetReg, TRI);
 152
 153   // Add newly used reg to the block's live-in list if it isn't there already.
 154   if (!MBB.isLiveIn(TargetReg))
 155     MBB.addLiveIn(TargetReg);
 156
 157   // Clear any kills of TargetReg between CondBr and the last removed COPY.
 158   for (MachineInstr &MMI : make_range(MBB.begin(), LastChange))
 159     MMI.clearRegisterKills(TargetReg, TRI);
 160
 161   return true;
 162 }
 163
 164 bool RISCVRedundantCopyElimination::runOnMachineFunction(MachineFunction &MF) {
 165   if (skipFunction(MF.getFunction()))
 166     return false;
 167
 168   TII = MF.getSubtarget().getInstrInfo();
 169   TRI = MF.getSubtarget().getRegisterInfo();
 170   MRI = &MF.getRegInfo();
 171
 172   bool Changed = false;
 173   for (MachineBasicBlock &MBB : MF)
 174     Changed |= optimizeBlock(MBB);
 175
 176   return Changed;
 177 }
 178
 179 FunctionPass *llvm::createRISCVRedundantCopyEliminationPass() {
 180   return new RISCVRedundantCopyElimination();
 181 }