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