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