| 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 | |
| 41 | using namespace llvm; |
| 42 | |
| 43 | #define DEBUG_TYPE "riscv-redundant-copy-elimination" |
| 44 | |
| 45 | STATISTIC(NumCopiesRemoved, "Number of copies removed." ); |
| 46 | |
| 47 | namespace { |
| 48 | class RISCVRedundantCopyEliminationLegacy : public MachineFunctionPass { |
| 49 | public: |
| 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 | |
| 71 | char RISCVRedundantCopyEliminationLegacy::ID = 0; |
| 72 | |
| 73 | INITIALIZE_PASS(RISCVRedundantCopyEliminationLegacy, "riscv-copyelim" , |
| 74 | "RISC-V Redundant Copy Elimination" , false, false) |
| 75 | |
| 76 | static bool |
| 77 | guaranteesZeroRegInBlock(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 | |
| 92 | static bool |
| 93 | guaranteesRegEqualsImmInBlock(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. |
| 112 | static 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 | |
| 126 | static std::optional<int64_t> |
| 127 | getRegImmediateBeforeTerminator(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 | |
| 146 | static 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 | |
| 261 | static 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 | |
| 273 | FunctionPass *llvm::createRISCVRedundantCopyEliminationLegacyPass() { |
| 274 | return new RISCVRedundantCopyEliminationLegacy(); |
| 275 | } |
| 276 | |
| 277 | bool RISCVRedundantCopyEliminationLegacy::runOnMachineFunction( |
| 278 | MachineFunction &MF) { |
| 279 | if (skipFunction(F: MF.getFunction())) |
| 280 | return false; |
| 281 | return runRedundantCopyElimination(MF); |
| 282 | } |
| 283 | |
| 284 | PreservedAnalyses |
| 285 | RISCVRedundantCopyEliminationPass::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 | |