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// The pass also handles register-register branches when one operand is
24// materialized as a non-zero immediate in the predecessor block.
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#include <optional>
36
37using namespace llvm;
38
39#define DEBUG_TYPE "riscv-copyelim"
40
41STATISTIC(NumCopiesRemoved, "Number of copies removed.");
42
43namespace {
44class RISCVRedundantCopyElimination : public MachineFunctionPass {
45 const MachineRegisterInfo *MRI;
46 const TargetRegisterInfo *TRI;
47 const TargetInstrInfo *TII;
48
49public:
50 static char ID;
51 RISCVRedundantCopyElimination() : MachineFunctionPass(ID) {}
52
53 bool runOnMachineFunction(MachineFunction &MF) override;
54 MachineFunctionProperties getRequiredProperties() const override {
55 return MachineFunctionProperties().setNoVRegs();
56 }
57
58 StringRef getPassName() const override {
59 return "RISC-V Redundant Copy Elimination";
60 }
61
62 void getAnalysisUsage(AnalysisUsage &AU) const override {
63 AU.addPreserved<MachineRegisterClassInfoWrapperPass>();
64 MachineFunctionPass::getAnalysisUsage(AU);
65 }
66
67private:
68 bool optimizeBlock(MachineBasicBlock &MBB);
69};
70
71} // end anonymous namespace
72
73char RISCVRedundantCopyElimination::ID = 0;
74
75INITIALIZE_PASS(RISCVRedundantCopyElimination, "riscv-copyelim",
76 "RISC-V Redundant Copy Elimination", false, false)
77
78static bool
79guaranteesZeroRegInBlock(MachineBasicBlock &MBB,
80 const SmallVectorImpl<MachineOperand> &Cond,
81 MachineBasicBlock *TBB) {
82 assert(Cond.size() == 3 && "Unexpected number of operands");
83 assert(TBB != nullptr && "Expected branch target basic block");
84 auto Opc = Cond[0].getImm();
85 if (Opc == RISCV::BEQ && Cond[2].isReg() && Cond[2].getReg() == RISCV::X0 &&
86 TBB == &MBB)
87 return true;
88 if (Opc == RISCV::BNE && Cond[2].isReg() && Cond[2].getReg() == RISCV::X0 &&
89 TBB != &MBB)
90 return true;
91 return false;
92}
93
94static bool
95guaranteesRegEqualsImmInBlock(MachineBasicBlock &MBB,
96 const SmallVectorImpl<MachineOperand> &Cond,
97 MachineBasicBlock *TBB) {
98 assert(Cond.size() == 3 && "Unexpected number of operands");
99 assert(TBB != nullptr && "Expected branch target basic block");
100 auto Opc = Cond[0].getImm();
101 if ((Opc == RISCV::QC_BEQI || Opc == RISCV::QC_E_BEQI ||
102 Opc == RISCV::NDS_BEQC || Opc == RISCV::BEQI) &&
103 Cond[2].isImm() && Cond[2].getImm() != 0 && TBB == &MBB)
104 return true;
105 if ((Opc == RISCV::QC_BNEI || Opc == RISCV::QC_E_BNEI ||
106 Opc == RISCV::NDS_BNEC || Opc == RISCV::BNEI) &&
107 Cond[2].isImm() && Cond[2].getImm() != 0 && TBB != &MBB)
108 return true;
109 return false;
110}
111
112// Match copy from x0, "addi rd, x0, imm", or "qc.li rd, imm", returning the
113// defined register and the known value. Reg is invalid if MI isn't a match.
114static RegImmPair matchRegKnownVal(const MachineInstr &MI) {
115 if (MI.isCopy() && MI.getOperand(i: 0).isReg() && MI.getOperand(i: 1).isReg() &&
116 MI.getOperand(i: 1).getReg() == RISCV::X0)
117 return RegImmPair(MI.getOperand(i: 0).getReg(), 0);
118 if (MI.getOpcode() == RISCV::ADDI && MI.getOperand(i: 0).isReg() &&
119 MI.getOperand(i: 1).isReg() && MI.getOperand(i: 1).getReg() == RISCV::X0 &&
120 MI.getOperand(i: 2).isImm())
121 return RegImmPair(MI.getOperand(i: 0).getReg(), MI.getOperand(i: 2).getImm());
122 if (MI.getOpcode() == RISCV::QC_LI && MI.getOperand(i: 0).isReg() &&
123 MI.getOperand(i: 1).isImm())
124 return RegImmPair(MI.getOperand(i: 0).getReg(), MI.getOperand(i: 1).getImm());
125 return RegImmPair(Register(), 0);
126}
127
128static std::optional<int64_t>
129getRegImmediateBeforeTerminator(MachineBasicBlock &MBB, Register Reg,
130 const TargetRegisterInfo *TRI) {
131 // A write to X0 is discarded, so it cannot establish a nonzero value.
132 if (Reg == RISCV::X0)
133 return std::nullopt;
134
135 for (auto I = MBB.getFirstTerminator(); I != MBB.begin();) {
136 MachineInstr &MI = *--I;
137 if (!MI.modifiesRegister(Reg, TRI))
138 continue;
139 // The last modification must define Reg itself to a known value.
140 RegImmPair Match = matchRegKnownVal(MI);
141 if (Match.Reg == Reg)
142 return Match.Imm;
143 return std::nullopt;
144 }
145 return std::nullopt;
146}
147
148bool RISCVRedundantCopyElimination::optimizeBlock(MachineBasicBlock &MBB) {
149 // Check if the current basic block has a single predecessor.
150 if (MBB.pred_size() != 1)
151 return false;
152
153 // Check if the predecessor has two successors, implying the block ends in a
154 // conditional branch.
155 MachineBasicBlock *PredMBB = *MBB.pred_begin();
156 if (PredMBB->succ_size() != 2)
157 return false;
158
159 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
160 SmallVector<MachineOperand, 3> Cond;
161 if (TII->analyzeBranch(MBB&: *PredMBB, TBB, FBB, Cond, /*AllowModify*/ false) ||
162 Cond.empty())
163 return false;
164
165 Register TargetReg = Cond[1].getReg();
166
167 if (!TargetReg)
168 return false;
169
170 bool IsZeroCopy = guaranteesZeroRegInBlock(MBB, Cond, TBB);
171 bool IsImmCopy = !IsZeroCopy && guaranteesRegEqualsImmInBlock(MBB, Cond, TBB);
172 int64_t CompareImm = IsImmCopy ? Cond[2].getImm() : 0;
173 if (!IsZeroCopy && !IsImmCopy && Cond.size() == 3 &&
174 (Cond[0].getImm() == RISCV::BEQ || Cond[0].getImm() == RISCV::BNE) &&
175 Cond[2].isReg()) {
176 // One branch operand may have been materialized with ADDI or QC_LI.
177 // The other operand is known to have the same value on the equality edge,
178 // irrespective of the operand order.
179 std::optional<int64_t> Imm =
180 getRegImmediateBeforeTerminator(MBB&: *PredMBB, Reg: Cond[2].getReg(), TRI);
181 if (Imm && *Imm != 0) {
182 TargetReg = Cond[1].getReg();
183 CompareImm = *Imm;
184 IsImmCopy = true;
185 } else {
186 Imm = getRegImmediateBeforeTerminator(MBB&: *PredMBB, Reg: Cond[1].getReg(), TRI);
187 if (Imm && *Imm != 0) {
188 TargetReg = Cond[2].getReg();
189 CompareImm = *Imm;
190 IsImmCopy = true;
191 }
192 }
193 // For BEQ, equality is guaranteed on the taken edge. For BNE, it is
194 // guaranteed on the fallthrough edge.
195 IsImmCopy &= (Cond[0].getImm() == RISCV::BEQ) == (TBB == &MBB);
196 }
197
198 if (!IsZeroCopy && !IsImmCopy)
199 return false;
200
201 bool Changed = false;
202 MachineBasicBlock::iterator LastChange = MBB.begin();
203 // Remove redundant Copy instructions unless TargetReg is modified.
204 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
205 MachineInstr *MI = &*I;
206 ++I;
207 // Compare with non-zero immediate or a known register value:
208 // remove redundant copy, addi rd,x0,imm, or qc.li rd,imm as applicable.
209 RegImmPair Match = matchRegKnownVal(MI: *MI);
210 if (Match.Reg && TargetReg == Match.Reg && Match.Imm == CompareImm &&
211 !MRI->isReserved(PhysReg: Match.Reg)) {
212 LLVM_DEBUG(dbgs() << "Remove redundant Copy: ");
213 LLVM_DEBUG(MI->print(dbgs()));
214
215 MI->eraseFromParent();
216 Changed = true;
217 LastChange = I;
218 ++NumCopiesRemoved;
219 continue;
220 }
221
222 if (MI->modifiesRegister(Reg: TargetReg, TRI))
223 break;
224 }
225
226 if (!Changed)
227 return false;
228
229 MachineBasicBlock::iterator CondBr = PredMBB->getFirstTerminator();
230 assert((CondBr->getOpcode() == RISCV::BEQ ||
231 CondBr->getOpcode() == RISCV::BNE ||
232 CondBr->getOpcode() == RISCV::BEQI ||
233 CondBr->getOpcode() == RISCV::BNEI ||
234 CondBr->getOpcode() == RISCV::QC_BEQI ||
235 CondBr->getOpcode() == RISCV::QC_BNEI ||
236 CondBr->getOpcode() == RISCV::QC_E_BEQI ||
237 CondBr->getOpcode() == RISCV::QC_E_BNEI ||
238 CondBr->getOpcode() == RISCV::NDS_BEQC ||
239 CondBr->getOpcode() == RISCV::NDS_BNEC) &&
240 "Unexpected opcode");
241 assert((CondBr->getOperand(0).getReg() == TargetReg ||
242 CondBr->getOperand(1).getReg() == TargetReg) &&
243 "Unexpected register");
244
245 // Otherwise, we have to fixup the use-def chain, starting with the
246 // BEQ(I)/BNE(I). Conservatively mark as much as we can live.
247 CondBr->clearRegisterKills(Reg: TargetReg, RegInfo: TRI);
248
249 // Add newly used reg to the block's live-in list if it isn't there already.
250 if (!MBB.isLiveIn(Reg: TargetReg))
251 MBB.addLiveIn(PhysReg: TargetReg);
252
253 // Clear any kills of TargetReg between CondBr and the last removed COPY.
254 for (MachineInstr &MMI : make_range(x: MBB.begin(), y: LastChange))
255 MMI.clearRegisterKills(Reg: TargetReg, RegInfo: TRI);
256
257 return true;
258}
259
260bool RISCVRedundantCopyElimination::runOnMachineFunction(MachineFunction &MF) {
261 if (skipFunction(F: MF.getFunction()))
262 return false;
263
264 TII = MF.getSubtarget().getInstrInfo();
265 TRI = MF.getSubtarget().getRegisterInfo();
266 MRI = &MF.getRegInfo();
267
268 bool Changed = false;
269 for (MachineBasicBlock &MBB : MF)
270 Changed |= optimizeBlock(MBB);
271
272 return Changed;
273}
274
275FunctionPass *llvm::createRISCVRedundantCopyEliminationPass() {
276 return new RISCVRedundantCopyElimination();
277}
278