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 @@ -19,6 +19,7 @@ add_public_tablegen_target(RISCVCommonTableGen) add_llvm_target(RISCVCodeGen + RISCVAddSubCombiner.cpp RISCVAsmPrinter.cpp RISCVCallLowering.cpp RISCVCodeGenPrepare.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,315 @@ +//===- 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 keyed 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) { + if (CurrentInstr) + MBBI--; + if (&*MBBI == CheckedInstr) + MBBI--; + // Remove both instructions. + LLVM_DEBUG(dbgs() << "Erase instruction " << *CheckedInstr << "\n"); + CheckedInstr->eraseFromParent(); + if (CurrentInstr) { + LLVM_DEBUG(dbgs() << "Erase instruction " << *CurrentInstr << "\n"); + CurrentInstr->eraseFromParent(); + } +} + +bool RISCVAddSubCombiner::tryToCombineInstructions( + MachineBasicBlock::iterator &MBBI, unsigned Opcode) { + Register BaseRegister = MBBI->getOperand(0).getReg(); + // Now supports only case when destination and source registers are the same. + if (BaseRegister != MBBI->getOperand(1).getReg()) + return false; + if (MachineInstr *CheckedInstr = CandidatesToBeCombined[BaseRegister]) { + MachineInstr *CurrentInstr = &*MBBI; + 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) { + MachineFunction *MF = MBBI->getParent()->getParent(); + + LLVM_DEBUG(dbgs() << "Replacing instructions:\n "); + LLVM_DEBUG(CheckedInstr->print(dbgs())); + LLVM_DEBUG(dbgs() << " "); + LLVM_DEBUG(MBBI->print(dbgs())); + LLVM_DEBUG(dbgs() << " with instruction:\n "); + + // Combine instructions to one. + MBBI->getOperand(2).setImm(ResultImm); + MBBI->setFlags(CheckedInstr->mergeFlagsWith(*MBBI)); + MBBI->cloneMergedMemRefs(*MF, {&*CheckedInstr, &*MBBI}); + + LLVM_DEBUG(MBBI->print(dbgs())); + LLVM_DEBUG(dbgs() << "\n"); + + CandidatesToBeCombined[BaseRegister] = &*MBBI; + NumRemovedInstructions++; + CurrentInstr = nullptr; + } 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()); + // Can't combine if the last operand was modified between current + // instructions. + auto RegisterUsageIter = ModificationRegisterMonitor.find(MBBI->getOperand(2).getReg()); + if (RegisterUsageIter != ModificationRegisterMonitor.end()) { + for (const auto &Users : RegisterUsageIter->second) { + 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) { + erase_if(RegistersInfo.second, [&Reg](std::pair Element) { + return Element.first == Reg; + }); + } + erase_value(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; + + LLVM_DEBUG(dbgs() << MBB); + 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) { + Modified = true; + LLVM_DEBUG(dbgs() << "Successfully combined\n"); + continue; + } + } + + // Check operands of instruction. + for (const auto &Operand : reverse(MBBI->operands())) { + 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 (is_contained(DestinationRegistersToCheck, OperandRegister)) { + if (Operand.isDef() && !Operand.isImplicit()) { + // Result of instruction is forbidden, can erase it. + LLVM_DEBUG(dbgs() << "Erase instruction " + << *CandidatesToBeCombined[Operand.getReg()] + << " as redundant\n"); + CandidatesToBeCombined[Operand.getReg()]->eraseFromParent(); + Modified = true; + 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 (is_contained(IgnoredFrameRegisters, MBBI->getOperand(0).getReg())) { + 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()) { + 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 = 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) { @@ -236,6 +237,8 @@ void RISCVPassConfig::addPreSched2() {} void RISCVPassConfig::addPreEmitPass() { + if (TM->getOptLevel() != CodeGenOpt::None) + addPass(createRISCVAddSubCombinerPass()); addPass(&BranchRelaxationPassID); addPass(createRISCVMakeCompressibleOptPass()); } 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 @@ -152,6 +152,7 @@ ; CHECK-NEXT: Insert fentry calls ; CHECK-NEXT: Insert XRay ops ; CHECK-NEXT: Implement the 'patchable-function' attribute +; CHECK-NEXT: RISCV add/sub combiner pass ; CHECK-NEXT: Branch relaxation pass ; CHECK-NEXT: RISCV Make Compressible ; CHECK-NEXT: Contiguously Lay Out Funclets 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