1 //=- RISCVRedundantCopyElimination.cpp - Remove useless copy for RISCV ------=//
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 "RISCV 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                 "RISCV redundant copy elimination pass", 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 }
182