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//
17// This pass also recognizes Xqcibi branch-immediate forms when compared
18// against non-zero immediates.
19//
20// This pass should be run after register allocation and is based on the
21// earliest versions of AArch64RedundantCopyElimination.
22//
23// FIXME: Support compare with non-zero immediates where the immediate is stored
24// in a register.
25//
26//===----------------------------------------------------------------------===//
27
28#include "RISCV.h"
29#include "RISCVInstrInfo.h"
30#include "llvm/ADT/Statistic.h"
31#include "llvm/CodeGen/MachineFunctionPass.h"
32#include "llvm/CodeGen/MachineRegisterInfo.h"
33#include "llvm/CodeGen/RegisterClassInfo.h"
34#include "llvm/Support/Debug.h"
35
36using namespace llvm;
37
38#define DEBUG_TYPE "riscv-copyelim"
39
40STATISTIC(NumCopiesRemoved, "Number of copies removed.");
41
42namespace {
43class RISCVRedundantCopyElimination : public MachineFunctionPass {
44 const MachineRegisterInfo *MRI;
45 const TargetRegisterInfo *TRI;
46 const TargetInstrInfo *TII;
47
48public:
49 static char ID;
50 RISCVRedundantCopyElimination() : MachineFunctionPass(ID) {}
51
52 bool runOnMachineFunction(MachineFunction &MF) override;
53 MachineFunctionProperties getRequiredProperties() const override {
54 return MachineFunctionProperties().setNoVRegs();
55 }
56
57 StringRef getPassName() const override {
58 return "RISC-V Redundant Copy Elimination";
59 }
60
61 void getAnalysisUsage(AnalysisUsage &AU) const override {
62 AU.addPreserved<MachineRegisterClassInfoWrapperPass>();
63 MachineFunctionPass::getAnalysisUsage(AU);
64 }
65
66private:
67 bool optimizeBlock(MachineBasicBlock &MBB);
68};
69
70} // end anonymous namespace
71
72char RISCVRedundantCopyElimination::ID = 0;
73
74INITIALIZE_PASS(RISCVRedundantCopyElimination, "riscv-copyelim",
75 "RISC-V Redundant Copy Elimination", false, false)
76
77static bool
78guaranteesZeroRegInBlock(MachineBasicBlock &MBB,
79 const SmallVectorImpl<MachineOperand> &Cond,
80 MachineBasicBlock *TBB) {
81 assert(Cond.size() == 3 && "Unexpected number of operands");
82 assert(TBB != nullptr && "Expected branch target basic block");
83 auto Opc = Cond[0].getImm();
84 if (Opc == RISCV::BEQ && Cond[2].isReg() && Cond[2].getReg() == RISCV::X0 &&
85 TBB == &MBB)
86 return true;
87 if (Opc == RISCV::BNE && Cond[2].isReg() && Cond[2].getReg() == RISCV::X0 &&
88 TBB != &MBB)
89 return true;
90 return false;
91}
92
93static bool
94guaranteesRegEqualsImmInBlock(MachineBasicBlock &MBB,
95 const SmallVectorImpl<MachineOperand> &Cond,
96 MachineBasicBlock *TBB) {
97 assert(Cond.size() == 3 && "Unexpected number of operands");
98 assert(TBB != nullptr && "Expected branch target basic block");
99 auto Opc = Cond[0].getImm();
100 if ((Opc == RISCV::QC_BEQI || Opc == RISCV::QC_E_BEQI ||
101 Opc == RISCV::NDS_BEQC || Opc == RISCV::BEQI) &&
102 Cond[2].isImm() && Cond[2].getImm() != 0 && TBB == &MBB)
103 return true;
104 if ((Opc == RISCV::QC_BNEI || Opc == RISCV::QC_E_BNEI ||
105 Opc == RISCV::NDS_BNEC || Opc == RISCV::BNEI) &&
106 Cond[2].isImm() && Cond[2].getImm() != 0 && TBB != &MBB)
107 return true;
108 return false;
109}
110
111bool RISCVRedundantCopyElimination::optimizeBlock(MachineBasicBlock &MBB) {
112 // Check if the current basic block has a single predecessor.
113 if (MBB.pred_size() != 1)
114 return false;
115
116 // Check if the predecessor has two successors, implying the block ends in a
117 // conditional branch.
118 MachineBasicBlock *PredMBB = *MBB.pred_begin();
119 if (PredMBB->succ_size() != 2)
120 return false;
121
122 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
123 SmallVector<MachineOperand, 3> Cond;
124 if (TII->analyzeBranch(MBB&: *PredMBB, TBB, FBB, Cond, /*AllowModify*/ false) ||
125 Cond.empty())
126 return false;
127
128 Register TargetReg = Cond[1].getReg();
129
130 if (!TargetReg)
131 return false;
132
133 bool IsZeroCopy = guaranteesZeroRegInBlock(MBB, Cond, TBB);
134
135 if (!IsZeroCopy && !guaranteesRegEqualsImmInBlock(MBB, Cond, TBB))
136 return false;
137
138 bool Changed = false;
139 MachineBasicBlock::iterator LastChange = MBB.begin();
140 // Remove redundant Copy instructions unless TargetReg is modified.
141 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
142 MachineInstr *MI = &*I;
143 ++I;
144 bool RemoveMI = false;
145 if (IsZeroCopy) {
146 if (MI->isCopy() && MI->getOperand(i: 0).isReg() &&
147 MI->getOperand(i: 1).isReg()) {
148 Register DefReg = MI->getOperand(i: 0).getReg();
149 Register SrcReg = MI->getOperand(i: 1).getReg();
150
151 if (SrcReg == RISCV::X0 && !MRI->isReserved(PhysReg: DefReg) &&
152 TargetReg == DefReg)
153 RemoveMI = true;
154 }
155 } else {
156 // Xqcibi, XAndesPref and Zibi compare with non-zero immediate:
157 // remove redundant addi rd,x0,imm or qc.li rd,imm as applicable.
158 if (MI->getOpcode() == RISCV::ADDI && MI->getOperand(i: 0).isReg() &&
159 MI->getOperand(i: 1).isReg() && MI->getOperand(i: 2).isImm()) {
160 Register DefReg = MI->getOperand(i: 0).getReg();
161 Register SrcReg = MI->getOperand(i: 1).getReg();
162 int64_t Imm = MI->getOperand(i: 2).getImm();
163 if (SrcReg == RISCV::X0 && !MRI->isReserved(PhysReg: DefReg) &&
164 TargetReg == DefReg && Imm == Cond[2].getImm())
165 RemoveMI = true;
166 } else if (MI->getOpcode() == RISCV::QC_LI && MI->getOperand(i: 0).isReg() &&
167 MI->getOperand(i: 1).isImm()) {
168 Register DefReg = MI->getOperand(i: 0).getReg();
169 int64_t Imm = MI->getOperand(i: 1).getImm();
170 if (!MRI->isReserved(PhysReg: DefReg) && TargetReg == DefReg &&
171 Imm == Cond[2].getImm())
172 RemoveMI = true;
173 }
174 }
175
176 if (RemoveMI) {
177 LLVM_DEBUG(dbgs() << "Remove redundant Copy: ");
178 LLVM_DEBUG(MI->print(dbgs()));
179
180 MI->eraseFromParent();
181 Changed = true;
182 LastChange = I;
183 ++NumCopiesRemoved;
184 continue;
185 }
186
187 if (MI->modifiesRegister(Reg: TargetReg, TRI))
188 break;
189 }
190
191 if (!Changed)
192 return false;
193
194 MachineBasicBlock::iterator CondBr = PredMBB->getFirstTerminator();
195 assert((CondBr->getOpcode() == RISCV::BEQ ||
196 CondBr->getOpcode() == RISCV::BNE ||
197 CondBr->getOpcode() == RISCV::BEQI ||
198 CondBr->getOpcode() == RISCV::BNEI ||
199 CondBr->getOpcode() == RISCV::QC_BEQI ||
200 CondBr->getOpcode() == RISCV::QC_BNEI ||
201 CondBr->getOpcode() == RISCV::QC_E_BEQI ||
202 CondBr->getOpcode() == RISCV::QC_E_BNEI ||
203 CondBr->getOpcode() == RISCV::NDS_BEQC ||
204 CondBr->getOpcode() == RISCV::NDS_BNEC) &&
205 "Unexpected opcode");
206 assert(CondBr->getOperand(0).getReg() == TargetReg && "Unexpected register");
207
208 // Otherwise, we have to fixup the use-def chain, starting with the
209 // BEQ(I)/BNE(I). Conservatively mark as much as we can live.
210 CondBr->clearRegisterKills(Reg: TargetReg, RegInfo: TRI);
211
212 // Add newly used reg to the block's live-in list if it isn't there already.
213 if (!MBB.isLiveIn(Reg: TargetReg))
214 MBB.addLiveIn(PhysReg: TargetReg);
215
216 // Clear any kills of TargetReg between CondBr and the last removed COPY.
217 for (MachineInstr &MMI : make_range(x: MBB.begin(), y: LastChange))
218 MMI.clearRegisterKills(Reg: TargetReg, RegInfo: TRI);
219
220 return true;
221}
222
223bool RISCVRedundantCopyElimination::runOnMachineFunction(MachineFunction &MF) {
224 if (skipFunction(F: MF.getFunction()))
225 return false;
226
227 TII = MF.getSubtarget().getInstrInfo();
228 TRI = MF.getSubtarget().getRegisterInfo();
229 MRI = &MF.getRegInfo();
230
231 bool Changed = false;
232 for (MachineBasicBlock &MBB : MF)
233 Changed |= optimizeBlock(MBB);
234
235 return Changed;
236}
237
238FunctionPass *llvm::createRISCVRedundantCopyEliminationPass() {
239 return new RISCVRedundantCopyElimination();
240}
241