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 "llvm/ADT/Statistic.h"
28 #include "llvm/CodeGen/MachineFunctionPass.h"
29 #include "llvm/CodeGen/MachineRegisterInfo.h"
30 #include "llvm/Support/Debug.h"
31 
32 using namespace llvm;
33 
34 #define DEBUG_TYPE "riscv-copyelim"
35 
36 STATISTIC(NumCopiesRemoved, "Number of copies removed.");
37 
38 namespace {
39 class RISCVRedundantCopyElimination : public MachineFunctionPass {
40   const MachineRegisterInfo *MRI;
41   const TargetRegisterInfo *TRI;
42 
43 public:
44   static char ID;
45   RISCVRedundantCopyElimination() : MachineFunctionPass(ID) {
46     initializeRISCVRedundantCopyEliminationPass(
47         *PassRegistry::getPassRegistry());
48   }
49 
50   bool runOnMachineFunction(MachineFunction &MF) override;
51   MachineFunctionProperties getRequiredProperties() const override {
52     return MachineFunctionProperties().set(
53         MachineFunctionProperties::Property::NoVRegs);
54   }
55 
56   StringRef getPassName() const override {
57     return "RISCV Redundant Copy Elimination";
58   }
59 
60 private:
61   bool optimizeBlock(MachineBasicBlock &MBB);
62 };
63 
64 } // end anonymous namespace
65 
66 char RISCVRedundantCopyElimination::ID = 0;
67 
68 INITIALIZE_PASS(RISCVRedundantCopyElimination, "riscv-copyelim",
69                 "RISCV redundant copy elimination pass", false, false)
70 
71 static bool guaranteesZeroRegInBlock(const MachineInstr &MI,
72                                      const MachineBasicBlock &MBB) {
73   unsigned Opc = MI.getOpcode();
74   if (Opc == RISCV::BEQ && MI.getOperand(1).getReg() == RISCV::X0 &&
75       &MBB == MI.getOperand(2).getMBB())
76     return true;
77   if (Opc == RISCV::BNE && MI.getOperand(1).getReg() == RISCV::X0 &&
78       &MBB != MI.getOperand(2).getMBB())
79     return true;
80 
81   return false;
82 }
83 
84 bool RISCVRedundantCopyElimination::optimizeBlock(MachineBasicBlock &MBB) {
85   // Check if the current basic block has a single predecessor.
86   if (MBB.pred_size() != 1)
87     return false;
88 
89   // Check if the predecessor has two successors, implying the block ends in a
90   // conditional branch.
91   MachineBasicBlock *PredMBB = *MBB.pred_begin();
92   if (PredMBB->succ_size() != 2)
93     return false;
94 
95   MachineBasicBlock::iterator CondBr = PredMBB->getLastNonDebugInstr();
96   if (CondBr == PredMBB->end())
97     return false;
98 
99   while (true) {
100     // If we run out of terminators, give up.
101     if (!CondBr->isTerminator())
102       return false;
103     // If we found a branch with X0, stop searching and try to remove copies.
104     // TODO: Handle multiple branches with different registers.
105     if (guaranteesZeroRegInBlock(*CondBr, MBB))
106       break;
107     // If we reached the beginning of the basic block, give up.
108     if (CondBr == PredMBB->begin())
109       return false;
110     --CondBr;
111   }
112 
113   Register TargetReg = CondBr->getOperand(0).getReg();
114   if (!TargetReg)
115     return false;
116 
117   bool Changed = false;
118   MachineBasicBlock::iterator LastChange = MBB.begin();
119   // Remove redundant Copy instructions unless TargetReg is modified.
120   for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
121     MachineInstr *MI = &*I;
122     ++I;
123     if (MI->isCopy() && MI->getOperand(0).isReg() &&
124         MI->getOperand(1).isReg()) {
125       Register DefReg = MI->getOperand(0).getReg();
126       Register SrcReg = MI->getOperand(1).getReg();
127 
128       if (SrcReg == RISCV::X0 && !MRI->isReserved(DefReg) &&
129           TargetReg == DefReg) {
130         LLVM_DEBUG(dbgs() << "Remove redundant Copy : ");
131         LLVM_DEBUG(MI->print(dbgs()));
132 
133         MI->eraseFromParent();
134         Changed = true;
135         LastChange = I;
136         ++NumCopiesRemoved;
137         continue;
138       }
139     }
140 
141     if (MI->modifiesRegister(TargetReg, TRI))
142       break;
143   }
144 
145   if (!Changed)
146     return false;
147 
148   // Otherwise, we have to fixup the use-def chain, starting with the
149   // BEQ/BNE. Conservatively mark as much as we can live.
150   CondBr->clearRegisterKills(TargetReg, TRI);
151 
152   // Add newly used reg to the block's live-in list if it isn't there already.
153   if (!MBB.isLiveIn(TargetReg))
154     MBB.addLiveIn(TargetReg);
155 
156   // Clear any kills of TargetReg between CondBr and the last removed COPY.
157   for (MachineInstr &MMI : make_range(MBB.begin(), LastChange))
158     MMI.clearRegisterKills(TargetReg, TRI);
159 
160   return true;
161 }
162 
163 bool RISCVRedundantCopyElimination::runOnMachineFunction(MachineFunction &MF) {
164   if (skipFunction(MF.getFunction()))
165     return false;
166 
167   TRI = MF.getSubtarget().getRegisterInfo();
168   MRI = &MF.getRegInfo();
169 
170   bool Changed = false;
171   for (MachineBasicBlock &MBB : MF)
172     Changed |= optimizeBlock(MBB);
173 
174   return Changed;
175 }
176 
177 FunctionPass *llvm::createRISCVRedundantCopyEliminationPass() {
178   return new RISCVRedundantCopyElimination();
179 }
180