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 // 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 "RISCVInstrInfo.h"
28 #include "llvm/ADT/Statistic.h"
29 #include "llvm/CodeGen/MachineFunctionPass.h"
30 #include "llvm/CodeGen/MachineRegisterInfo.h"
31 #include "llvm/Support/Debug.h"
32
33 using namespace llvm;
34
35 #define DEBUG_TYPE "riscv-copyelim"
36
37 STATISTIC(NumCopiesRemoved, "Number of copies removed.");
38
39 namespace {
40 class RISCVRedundantCopyElimination : public MachineFunctionPass {
41 const MachineRegisterInfo *MRI;
42 const TargetRegisterInfo *TRI;
43 const TargetInstrInfo *TII;
44
45 public:
46 static char ID;
RISCVRedundantCopyElimination()47 RISCVRedundantCopyElimination() : MachineFunctionPass(ID) {
48 initializeRISCVRedundantCopyEliminationPass(
49 *PassRegistry::getPassRegistry());
50 }
51
52 bool runOnMachineFunction(MachineFunction &MF) override;
getRequiredProperties() const53 MachineFunctionProperties getRequiredProperties() const override {
54 return MachineFunctionProperties().set(
55 MachineFunctionProperties::Property::NoVRegs);
56 }
57
getPassName() const58 StringRef getPassName() const override {
59 return "RISC-V Redundant Copy Elimination";
60 }
61
62 private:
63 bool optimizeBlock(MachineBasicBlock &MBB);
64 };
65
66 } // end anonymous namespace
67
68 char RISCVRedundantCopyElimination::ID = 0;
69
70 INITIALIZE_PASS(RISCVRedundantCopyElimination, "riscv-copyelim",
71 "RISC-V Redundant Copy Elimination", false, false)
72
73 static bool
guaranteesZeroRegInBlock(MachineBasicBlock & MBB,const SmallVectorImpl<MachineOperand> & Cond,MachineBasicBlock * TBB)74 guaranteesZeroRegInBlock(MachineBasicBlock &MBB,
75 const SmallVectorImpl<MachineOperand> &Cond,
76 MachineBasicBlock *TBB) {
77 assert(Cond.size() == 3 && "Unexpected number of operands");
78 assert(TBB != nullptr && "Expected branch target basic block");
79 auto CC = static_cast<RISCVCC::CondCode>(Cond[0].getImm());
80 if (CC == RISCVCC::COND_EQ && Cond[2].isReg() &&
81 Cond[2].getReg() == RISCV::X0 && TBB == &MBB)
82 return true;
83 if (CC == RISCVCC::COND_NE && Cond[2].isReg() &&
84 Cond[2].getReg() == RISCV::X0 && TBB != &MBB)
85 return true;
86 return false;
87 }
88
optimizeBlock(MachineBasicBlock & MBB)89 bool RISCVRedundantCopyElimination::optimizeBlock(MachineBasicBlock &MBB) {
90 // Check if the current basic block has a single predecessor.
91 if (MBB.pred_size() != 1)
92 return false;
93
94 // Check if the predecessor has two successors, implying the block ends in a
95 // conditional branch.
96 MachineBasicBlock *PredMBB = *MBB.pred_begin();
97 if (PredMBB->succ_size() != 2)
98 return false;
99
100 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
101 SmallVector<MachineOperand, 3> Cond;
102 if (TII->analyzeBranch(*PredMBB, TBB, FBB, Cond, /*AllowModify*/ false) ||
103 Cond.empty())
104 return false;
105
106 // Is this a branch with X0?
107 if (!guaranteesZeroRegInBlock(MBB, Cond, TBB))
108 return false;
109
110 Register TargetReg = Cond[1].getReg();
111 if (!TargetReg)
112 return false;
113
114 bool Changed = false;
115 MachineBasicBlock::iterator LastChange = MBB.begin();
116 // Remove redundant Copy instructions unless TargetReg is modified.
117 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
118 MachineInstr *MI = &*I;
119 ++I;
120 if (MI->isCopy() && MI->getOperand(0).isReg() &&
121 MI->getOperand(1).isReg()) {
122 Register DefReg = MI->getOperand(0).getReg();
123 Register SrcReg = MI->getOperand(1).getReg();
124
125 if (SrcReg == RISCV::X0 && !MRI->isReserved(DefReg) &&
126 TargetReg == DefReg) {
127 LLVM_DEBUG(dbgs() << "Remove redundant Copy : ");
128 LLVM_DEBUG(MI->print(dbgs()));
129
130 MI->eraseFromParent();
131 Changed = true;
132 LastChange = I;
133 ++NumCopiesRemoved;
134 continue;
135 }
136 }
137
138 if (MI->modifiesRegister(TargetReg, TRI))
139 break;
140 }
141
142 if (!Changed)
143 return false;
144
145 MachineBasicBlock::iterator CondBr = PredMBB->getFirstTerminator();
146 assert((CondBr->getOpcode() == RISCV::BEQ ||
147 CondBr->getOpcode() == RISCV::BNE) &&
148 "Unexpected opcode");
149 assert(CondBr->getOperand(0).getReg() == TargetReg && "Unexpected register");
150
151 // Otherwise, we have to fixup the use-def chain, starting with the
152 // BEQ/BNE. Conservatively mark as much as we can live.
153 CondBr->clearRegisterKills(TargetReg, TRI);
154
155 // Add newly used reg to the block's live-in list if it isn't there already.
156 if (!MBB.isLiveIn(TargetReg))
157 MBB.addLiveIn(TargetReg);
158
159 // Clear any kills of TargetReg between CondBr and the last removed COPY.
160 for (MachineInstr &MMI : make_range(MBB.begin(), LastChange))
161 MMI.clearRegisterKills(TargetReg, TRI);
162
163 return true;
164 }
165
runOnMachineFunction(MachineFunction & MF)166 bool RISCVRedundantCopyElimination::runOnMachineFunction(MachineFunction &MF) {
167 if (skipFunction(MF.getFunction()))
168 return false;
169
170 TII = MF.getSubtarget().getInstrInfo();
171 TRI = MF.getSubtarget().getRegisterInfo();
172 MRI = &MF.getRegInfo();
173
174 bool Changed = false;
175 for (MachineBasicBlock &MBB : MF)
176 Changed |= optimizeBlock(MBB);
177
178 return Changed;
179 }
180
createRISCVRedundantCopyEliminationPass()181 FunctionPass *llvm::createRISCVRedundantCopyEliminationPass() {
182 return new RISCVRedundantCopyElimination();
183 }
184