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