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;
RISCVRedundantCopyElimination()45 RISCVRedundantCopyElimination() : MachineFunctionPass(ID) {
46 initializeRISCVRedundantCopyEliminationPass(
47 *PassRegistry::getPassRegistry());
48 }
49
50 bool runOnMachineFunction(MachineFunction &MF) override;
getRequiredProperties() const51 MachineFunctionProperties getRequiredProperties() const override {
52 return MachineFunctionProperties().set(
53 MachineFunctionProperties::Property::NoVRegs);
54 }
55
getPassName() const56 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
guaranteesZeroRegInBlock(const MachineInstr & MI,const MachineBasicBlock & MBB)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
optimizeBlock(MachineBasicBlock & MBB)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
runOnMachineFunction(MachineFunction & MF)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
createRISCVRedundantCopyEliminationPass()177 FunctionPass *llvm::createRISCVRedundantCopyEliminationPass() {
178 return new RISCVRedundantCopyElimination();
179 }
180