diff --git a/llvm/lib/Target/RISCV/CMakeLists.txt b/llvm/lib/Target/RISCV/CMakeLists.txt --- a/llvm/lib/Target/RISCV/CMakeLists.txt +++ b/llvm/lib/Target/RISCV/CMakeLists.txt @@ -23,6 +23,7 @@ RISCVCallLowering.cpp RISCVCodeGenPrepare.cpp RISCVMakeCompressible.cpp + RISCVAddSubCombiner.cpp RISCVExpandAtomicPseudoInsts.cpp RISCVExpandPseudoInsts.cpp RISCVFrameLowering.cpp diff --git a/llvm/lib/Target/RISCV/RISCV.h b/llvm/lib/Target/RISCV/RISCV.h --- a/llvm/lib/Target/RISCV/RISCV.h +++ b/llvm/lib/Target/RISCV/RISCV.h @@ -65,6 +65,9 @@ FunctionPass *createRISCVRedundantCopyEliminationPass(); void initializeRISCVRedundantCopyEliminationPass(PassRegistry &); +FunctionPass *createRISCVAddSubCombinerPass(); +void initializeRISCVAddSubCombinerPass(PassRegistry &); + InstructionSelector *createRISCVInstructionSelector(const RISCVTargetMachine &, RISCVSubtarget &, RISCVRegisterBankInfo &); diff --git a/llvm/lib/Target/RISCV/RISCVAddSubCombiner.cpp b/llvm/lib/Target/RISCV/RISCVAddSubCombiner.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Target/RISCV/RISCVAddSubCombiner.cpp @@ -0,0 +1,337 @@ +//===- RISCVAddSubCombiner.cpp - RISCV add/sub combiner pass -------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file contains a pass that performs add/sub operations combining and +// removing redundant ones. +// +//===----------------------------------------------------------------------===// + +#include "RISCV.h" +#include "RISCVInstrInfo.h" +#include "RISCVMachineFunctionInfo.h" +#include "RISCVSubtarget.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/CodeGen/MachineOperand.h" +#include "llvm/CodeGen/TargetRegisterInfo.h" +#include "llvm/IR/DebugLoc.h" +#include "llvm/Pass.h" +#include "llvm/Support/Debug.h" +#include + +using namespace llvm; + +#define DEBUG_TYPE "riscv-addsub-comb" + +STATISTIC(NumRemovedInstructions, "Number of removed add/sub instructions"); + +#define RISCV_ADD_SUB_COMB_NAME "RISCV add/sub combiner pass" +namespace { + +class RISCVAddSubCombiner : public MachineFunctionPass { + // Instructions that are possible candidates to be combined divided by + // destination registers. + DenseMap CandidatesToBeCombined; + + // Destination registers of add/sub instructions that can potentially + // be optimized. + SmallVector DestinationRegistersToCheck; + // List of ignored registers as far as they are used to work with frames. + SmallVector IgnoredFrameRegisters; + // Registers that are used as operands and are monitored not to be modified. + DenseMap, 4>> + ModificationRegisterMonitor; + + const RISCVInstrInfo *TII; + const RISCVSubtarget *Subtarget; + + bool optimizeBlock(MachineBasicBlock &MBB); + bool tryToCombineInstructions(MachineBasicBlock::iterator &MBBI, + unsigned Opcode); + void excludeFromCandidatesByRegister(const Register &Reg); + unsigned getInverseInstructionOpcode(const MachineInstr &MI); + bool isAddOrSubInstr(const MachineInstr &MI); + void eraseInstructions(MachineBasicBlock::iterator &MBBI, + MachineInstr *CheckedInstr, + MachineInstr *CurrentInstr); + +public: + static char ID; + + RISCVAddSubCombiner() : MachineFunctionPass(ID) { + initializeRISCVAddSubCombinerPass(*PassRegistry::getPassRegistry()); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + MachineFunctionPass::getAnalysisUsage(AU); + } + + bool runOnMachineFunction(MachineFunction &MF) override; + + MachineFunctionProperties getRequiredProperties() const override { + return MachineFunctionProperties().set( + MachineFunctionProperties::Property::NoVRegs); + } + + StringRef getPassName() const override { return RISCV_ADD_SUB_COMB_NAME; } +}; + +char RISCVAddSubCombiner::ID = 0; + +} // end anonymous namespace + +INITIALIZE_PASS(RISCVAddSubCombiner, "riscv-addsub-comb", + RISCV_ADD_SUB_COMB_NAME, false, false) + +void RISCVAddSubCombiner::eraseInstructions(MachineBasicBlock::iterator &MBBI, + MachineInstr *CheckedInstr, + MachineInstr *CurrentInstr) { + MBBI--; + if (&*MBBI == CheckedInstr) { + MBBI--; + } + // Remove both instructions. + LLVM_DEBUG(dbgs() << "Erase instruction " << *CheckedInstr << "\n"); + LLVM_DEBUG(dbgs() << "Erase instruction " << *CurrentInstr << "\n"); + CheckedInstr->eraseFromParent(); + CurrentInstr->eraseFromParent(); +} + +bool RISCVAddSubCombiner::tryToCombineInstructions( + MachineBasicBlock::iterator &MBBI, unsigned Opcode) { + // Now supports only case when destination and source registers are the same. + if (MBBI->getOperand(0).getReg() != MBBI->getOperand(1).getReg()) + return false; + Register BaseRegister = MBBI->getOperand(0).getReg(); + if (MachineInstr *CheckedInstr = CandidatesToBeCombined[BaseRegister]) { + MachineInstr *CurrentInstr = &*MBBI; + if (Subtarget->is64Bit() && + ((CheckedInstr->getOpcode() == RISCV::ADDI && Opcode == RISCV::ADDIW) || + (CheckedInstr->getOpcode() == RISCV::ADDIW && + Opcode == RISCV::ADDI))) { + // On 64-bit platform also can be used 32-bit commands. + Opcode = RISCV::ADDIW; + } else if (Opcode != CheckedInstr->getOpcode()) { + return false; + } + // If the last operands are immediates combine instructions. + if (CheckedInstr->getOperand(2).isImm() && MBBI->getOperand(2).isImm()) { + int64_t ResultImm = + CheckedInstr->getOperand(2).getImm() + MBBI->getOperand(2).getImm(); + // Validate result immediate. + if (!isInt<12>(ResultImm)) + return false; + if (ResultImm != 0) { + // Combine instructions to one. + DebugLoc DL = CheckedInstr->getDebugLoc(); + MachineBasicBlock *MBB = CheckedInstr->getParent(); + MachineInstrBuilder MIB; + MIB = BuildMI(*MBB, MBBI, DL, TII->get(Opcode)) + .add(MBBI->getOperand(0)) + .add(MBBI->getOperand(1)) + .addImm(ResultImm) + .cloneMergedMemRefs({&*CheckedInstr, &*MBBI}) + .setMIFlags(CheckedInstr->mergeFlagsWith(*MBBI)); + + LLVM_DEBUG( + dbgs() + << "Creating new instruction. Replacing instructions:\n "); + LLVM_DEBUG(CheckedInstr->print(dbgs())); + LLVM_DEBUG(dbgs() << " "); + LLVM_DEBUG(MBBI->print(dbgs())); + LLVM_DEBUG(dbgs() << " with instruction:\n "); + LLVM_DEBUG(((MachineInstr *)MIB)->print(dbgs())); + LLVM_DEBUG(dbgs() << "\n"); + + CandidatesToBeCombined[BaseRegister] = MIB; + NumRemovedInstructions++; + } else { + excludeFromCandidatesByRegister(BaseRegister); + NumRemovedInstructions += 2; + } + + eraseInstructions(MBBI, CheckedInstr, CurrentInstr); + + return true; + } + // If the second operand is register, check that it isn't written. + if (CheckedInstr->getOperand(2).isReg() && MBBI->getOperand(2).isReg() && + CheckedInstr->getOperand(2).getReg() == MBBI->getOperand(2).getReg()) { + assert(CheckedInstr->getOpcode() != MBBI->getOpcode()); + // Cann't combine if the last operand was modified between current + // instructions. + if (ModificationRegisterMonitor.find(MBBI->getOperand(2).getReg()) != + ModificationRegisterMonitor.end()) { + for (const auto &Users : + ModificationRegisterMonitor[MBBI->getOperand(2).getReg()]) { + if (Users.first == BaseRegister && Users.second) { + excludeFromCandidatesByRegister(BaseRegister); + return false; + } + } + } + eraseInstructions(MBBI, CheckedInstr, CurrentInstr); + excludeFromCandidatesByRegister(BaseRegister); + NumRemovedInstructions += 2; + return true; + } + } + return false; +} + +void RISCVAddSubCombiner::excludeFromCandidatesByRegister(const Register &Reg) { + for (auto &RegistersInfo : ModificationRegisterMonitor) { + auto ElementToErase = + std::find_if(RegistersInfo.second.begin(), RegistersInfo.second.end(), + [&Reg](std::pair Element) { + return Element.first == Reg; + }); + if (ElementToErase != RegistersInfo.second.end()) { + RegistersInfo.second.erase(ElementToErase); + } + } + DestinationRegistersToCheck.erase(find(DestinationRegistersToCheck, Reg)); + CandidatesToBeCombined.erase(Reg); +} + +bool RISCVAddSubCombiner::isAddOrSubInstr(const MachineInstr &MI) { + switch (MI.getOpcode()) { + default: + return false; + case RISCV::ADD: + case RISCV::ADDI: + case RISCV::ADDIW: + case RISCV::SUB: + return true; + } +} + +// TODO: Rewrite with TableGen InstrMapping? +unsigned +RISCVAddSubCombiner::getInverseInstructionOpcode(const MachineInstr &MI) { + switch (MI.getOpcode()) { + default: + llvm_unreachable("Opcode has no inverse instruction!"); + case RISCV::ADD: + return RISCV::SUB; + case RISCV::SUB: + return RISCV::ADD; + } +} + +bool RISCVAddSubCombiner::optimizeBlock(MachineBasicBlock &MBB) { + CandidatesToBeCombined.clear(); + DestinationRegistersToCheck.clear(); + ModificationRegisterMonitor.clear(); + bool Modified = false; + + for (MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end(); MBBI != E; + MBBI++) { + if (isAddOrSubInstr(*MBBI) && + (MBBI->getOperand(2).isImm() || MBBI->getOperand(2).isReg())) { + // Check if the instruction can be combined with existing candidates. + unsigned CheckedInstrOpcode = MBBI->getOperand(2).isImm() + ? MBBI->getOpcode() + : getInverseInstructionOpcode(*MBBI); + bool Combined = tryToCombineInstructions(MBBI, CheckedInstrOpcode); + if (Combined) { + LLVM_DEBUG(dbgs() << "Successfully combined\n"); + continue; + } + } + + // Check operands of instruction. + for (int OperandIndex = MBBI->getNumOperands() - 1; OperandIndex >= 0; + OperandIndex--) { + auto Operand = MBBI->getOperand(OperandIndex); + + if (Operand.isReg()) { + Register OperandRegister = Operand.getReg(); + if (ModificationRegisterMonitor.find(OperandRegister) != + ModificationRegisterMonitor.end() && + MBBI->modifiesRegister(OperandRegister)) { + for (auto &Users : ModificationRegisterMonitor[OperandRegister]) { + Users.second = true; + } + } + + if (find(DestinationRegistersToCheck, OperandRegister) != + DestinationRegistersToCheck.end()) { + if (OperandIndex == 0 && MBBI->modifiesRegister(OperandRegister)) { + // Result of instruction is forbidden, can erase it. + LLVM_DEBUG(dbgs() << "Erase instruction " + << *CandidatesToBeCombined[Operand.getReg()] + << " as redundant\n"); + CandidatesToBeCombined[Operand.getReg()]->eraseFromParent(); + NumRemovedInstructions++; + } + // Value of add/sub expressions is used. + excludeFromCandidatesByRegister(Operand.getReg()); + } + } + } + + if (isAddOrSubInstr(*MBBI) && + (MBBI->getOperand(2).isImm() || MBBI->getOperand(2).isReg()) && + MBBI->getOperand(0).getReg() == MBBI->getOperand(1).getReg()) { + // Ignore registers used for work with frames. + if (MBBI->getFlag(MachineInstr::FrameDestroy) || + MBBI->getFlag(MachineInstr::FrameSetup)) { + IgnoredFrameRegisters.push_back(MBBI->getOperand(0).getReg()); + continue; + } + if (find(IgnoredFrameRegisters, MBBI->getOperand(0).getReg()) != + IgnoredFrameRegisters.end()) { + continue; + } + // Found an instruction that is possible to combine later. Add it as + // possible candidates. + Register DestRegister = MBBI->getOperand(0).getReg(); + CandidatesToBeCombined[DestRegister] = &*MBBI; + DestinationRegistersToCheck.push_back(DestRegister); + + // Save operand register to check it isn't modified. + if (MBBI->getOperand(2).isReg()) { + if (ModificationRegisterMonitor.find(MBBI->getOperand(2).getReg()) == + ModificationRegisterMonitor.end()) { + ModificationRegisterMonitor[MBBI->getOperand(2).getReg()] = + SmallVector, 4>(); + } + ModificationRegisterMonitor[MBBI->getOperand(2).getReg()].push_back( + std::make_pair(DestRegister, false)); + } + } + } + return Modified; +} + +bool RISCVAddSubCombiner::runOnMachineFunction(MachineFunction &MF) { + if (skipFunction(MF.getFunction())) + return false; + + Subtarget = &MF.getSubtarget(); + TII = static_cast(Subtarget->getInstrInfo()); + + bool Modified = false; + for (auto &MBB : MF) { + Modified |= optimizeBlock(MBB); + } + + return Modified; +} + +/// createRISCVAddSubCombinerPass - returns an instance of the +/// add/sub combine pass. +FunctionPass *llvm::createRISCVAddSubCombinerPass() { + return new RISCVAddSubCombiner(); +} diff --git a/llvm/lib/Target/RISCV/RISCVTargetMachine.cpp b/llvm/lib/Target/RISCV/RISCVTargetMachine.cpp --- a/llvm/lib/Target/RISCV/RISCVTargetMachine.cpp +++ b/llvm/lib/Target/RISCV/RISCVTargetMachine.cpp @@ -54,6 +54,7 @@ initializeRISCVSExtWRemovalPass(*PR); initializeRISCVExpandPseudoPass(*PR); initializeRISCVInsertVSETVLIPass(*PR); + initializeRISCVAddSubCombinerPass(*PR); } static StringRef computeDataLayout(const Triple &TT) { @@ -238,6 +239,8 @@ void RISCVPassConfig::addPreEmitPass() { addPass(&BranchRelaxationPassID); addPass(createRISCVMakeCompressibleOptPass()); + if (TM->getOptLevel() > CodeGenOpt::None) + addPass(createRISCVAddSubCombinerPass()); } void RISCVPassConfig::addPreEmitPass2() { diff --git a/llvm/test/CodeGen/RISCV/O3-pipeline.ll b/llvm/test/CodeGen/RISCV/O3-pipeline.ll --- a/llvm/test/CodeGen/RISCV/O3-pipeline.ll +++ b/llvm/test/CodeGen/RISCV/O3-pipeline.ll @@ -154,6 +154,7 @@ ; CHECK-NEXT: Implement the 'patchable-function' attribute ; CHECK-NEXT: Branch relaxation pass ; CHECK-NEXT: RISCV Make Compressible +; CHECK-NEXT: RISCV add/sub combiner pass ; CHECK-NEXT: Contiguously Lay Out Funclets ; CHECK-NEXT: StackMap Liveness Analysis ; CHECK-NEXT: Live DEBUG_VALUE analysis diff --git a/llvm/test/CodeGen/RISCV/add-sub-combiner.mir b/llvm/test/CodeGen/RISCV/add-sub-combiner.mir --- a/llvm/test/CodeGen/RISCV/add-sub-combiner.mir +++ b/llvm/test/CodeGen/RISCV/add-sub-combiner.mir @@ -1,5 +1,5 @@ # NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py -# RUN: llc -march=riscv64 -run-pass riscv-make-compressible %s -o - 2>&1 | FileCheck %s +# RUN: llc -march=riscv64 -run-pass riscv-addsub-comb %s -o - 2>&1 | FileCheck %s --- name: adds-combination @@ -10,9 +10,8 @@ ; CHECK-LABEL: name: adds-combination ; CHECK: liveins: $x6, $x13 ; CHECK-NEXT: {{ $}} - ; CHECK-NEXT: renamable $x13 = ADDI killed renamable $x13, 6 ; CHECK-NEXT: renamable $x10 = ADDI $x0, 7 - ; CHECK-NEXT: renamable $x13 = nuw ADDI killed renamable $x13, 1 + ; CHECK-NEXT: renamable $x13 = nuw ADDI killed renamable $x13, 7 renamable $x13 = ADDI killed renamable $x13, 6 renamable $x10 = ADDI $x0, 7 renamable $x13 = nuw ADDI killed renamable $x13, 1 @@ -26,9 +25,7 @@ ; CHECK-LABEL: name: redundant-adds ; CHECK: liveins: $x6, $x13 ; CHECK-NEXT: {{ $}} - ; CHECK-NEXT: renamable $x13 = ADDI killed renamable $x13, -1 ; CHECK-NEXT: renamable $x10 = ADDI $x0, 7 - ; CHECK-NEXT: renamable $x13 = nuw ADDI killed renamable $x13, 1 ; CHECK-NEXT: PseudoRET implicit killed $x10 renamable $x13 = ADDI killed renamable $x13, -1 renamable $x10 = ADDI $x0, 7 @@ -44,10 +41,8 @@ ; CHECK-LABEL: name: adds-combination-chain ; CHECK: liveins: $x6, $x13 ; CHECK-NEXT: {{ $}} - ; CHECK-NEXT: renamable $x13 = ADDIW killed renamable $x13, 6 ; CHECK-NEXT: renamable $x10 = ADDIW $x0, 7 - ; CHECK-NEXT: renamable $x13 = nuw ADDIW killed renamable $x13, 1 - ; CHECK-NEXT: renamable $x13 = nuw ADDIW killed renamable $x13, 7 + ; CHECK-NEXT: renamable $x13 = nuw ADDIW killed renamable $x13, 14 renamable $x13 = ADDIW killed renamable $x13, 6 renamable $x10 = ADDIW $x0, 7 renamable $x13 = nuw ADDIW killed renamable $x13, 1 @@ -62,9 +57,7 @@ ; CHECK-LABEL: name: add-sub-combination ; CHECK: liveins: $x6, $x13 ; CHECK-NEXT: {{ $}} - ; CHECK-NEXT: renamable $x13 = ADD killed renamable $x13, $x0 ; CHECK-NEXT: renamable $x10 = ADDIW $x0, 7 - ; CHECK-NEXT: renamable $x13 = SUB killed renamable $x13, $x0 renamable $x13 = ADD killed renamable $x13, $x0 renamable $x10 = ADDIW $x0, 7 renamable $x13 = SUB killed renamable $x13, $x0 @@ -78,7 +71,6 @@ ; CHECK-LABEL: name: rewrite-register ; CHECK: liveins: $x6, $x13 ; CHECK-NEXT: {{ $}} - ; CHECK-NEXT: renamable $x13 = ADDI killed renamable $x13, 6 ; CHECK-NEXT: renamable $x13 = ADDI $x0, 7 ; CHECK-NEXT: renamable $x13 = nuw ADDI killed renamable $x13, 1 renamable $x13 = ADDI killed renamable $x13, 6 @@ -91,6 +83,7 @@ body: | bb.0: liveins: $x6, $x13 + ; Negative test ; CHECK-LABEL: name: different-registers-chain ; CHECK: liveins: $x6, $x13 ; CHECK-NEXT: {{ $}} @@ -107,6 +100,7 @@ body: | bb.0: liveins: $x6, $x13 + ; Negative test ; CHECK-LABEL: name: add-sub-different-registers ; CHECK: liveins: $x6, $x13 ; CHECK-NEXT: {{ $}} @@ -123,6 +117,7 @@ body: | bb.0: liveins: $x6, $x13 + ; Negative test ; CHECK-LABEL: name: not-redundant-adds ; CHECK: liveins: $x6, $x13 ; CHECK-NEXT: {{ $}} diff --git a/llvm/test/CodeGen/RISCV/adds-combinations.ll b/llvm/test/CodeGen/RISCV/adds-combinations.ll --- a/llvm/test/CodeGen/RISCV/adds-combinations.ll +++ b/llvm/test/CodeGen/RISCV/adds-combinations.ll @@ -21,8 +21,6 @@ ; CHECK-NEXT: addiw a3, a3, -58 ; CHECK-NEXT: andi a3, a3, 255 ; CHECK-NEXT: li a4, 245 -; CHECK-NEXT: addi a2, a2, 1 -; CHECK-NEXT: addi a2, a2, -1 ; CHECK-NEXT: bltu a4, a3, .LBB0_7 ; CHECK-NEXT: # %bb.5: # %if.then.loopexit ; CHECK-NEXT: li a1, 5 diff --git a/llvm/test/CodeGen/RISCV/jumptable.ll b/llvm/test/CodeGen/RISCV/jumptable.ll --- a/llvm/test/CodeGen/RISCV/jumptable.ll +++ b/llvm/test/CodeGen/RISCV/jumptable.ll @@ -234,8 +234,7 @@ ; ; RV64I-SMALL-LABEL: above_threshold: ; RV64I-SMALL: # %bb.0: # %entry -; RV64I-SMALL-NEXT: sext.w a0, a0 -; RV64I-SMALL-NEXT: addi a0, a0, -1 +; RV64I-SMALL-NEXT: addiw a0, a0, -1 ; RV64I-SMALL-NEXT: li a2, 5 ; RV64I-SMALL-NEXT: bltu a2, a0, .LBB1_9 ; RV64I-SMALL-NEXT: # %bb.1: # %entry @@ -269,8 +268,7 @@ ; ; RV64I-MEDIUM-LABEL: above_threshold: ; RV64I-MEDIUM: # %bb.0: # %entry -; RV64I-MEDIUM-NEXT: sext.w a0, a0 -; RV64I-MEDIUM-NEXT: addi a0, a0, -1 +; RV64I-MEDIUM-NEXT: addiw a0, a0, -1 ; RV64I-MEDIUM-NEXT: li a2, 5 ; RV64I-MEDIUM-NEXT: bltu a2, a0, .LBB1_9 ; RV64I-MEDIUM-NEXT: # %bb.1: # %entry diff --git a/llvm/test/CodeGen/RISCV/sext-zext-trunc.ll b/llvm/test/CodeGen/RISCV/sext-zext-trunc.ll --- a/llvm/test/CodeGen/RISCV/sext-zext-trunc.ll +++ b/llvm/test/CodeGen/RISCV/sext-zext-trunc.ll @@ -481,8 +481,7 @@ ; ; RV64I-LABEL: sext_of_not_cmp_i32: ; RV64I: # %bb.0: -; RV64I-NEXT: sext.w a0, a0 -; RV64I-NEXT: addi a0, a0, -7 +; RV64I-NEXT: addiw a0, a0, -7 ; RV64I-NEXT: snez a0, a0 ; RV64I-NEXT: neg a0, a0 ; RV64I-NEXT: ret @@ -525,8 +524,7 @@ ; ; RV64I-LABEL: dec_of_zexted_cmp_i32: ; RV64I: # %bb.0: -; RV64I-NEXT: sext.w a0, a0 -; RV64I-NEXT: addi a0, a0, -7 +; RV64I-NEXT: addiw a0, a0, -7 ; RV64I-NEXT: seqz a0, a0 ; RV64I-NEXT: addi a0, a0, -1 ; RV64I-NEXT: ret