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 <cassert>
+
+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<Register, MachineInstr *> CandidatesToBeCombined;
+
+ // Destination registers of add/sub instructions that can potentially
+ // be optimized.
+ SmallVector<Register, 8> DestinationRegistersToCheck;
+ // List of ignored registers as far as they are used to work with frames.
+ SmallVector<Register, 8> IgnoredFrameRegisters;
+ // Registers that are used as operands and are monitored not to be modified.
+ DenseMap<Register, SmallVector<std::pair<Register, bool>, 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<Register, bool> 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<RISCVSubtarget>();
+ 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
@@ -32,9 +32,7 @@
; CHECK-NEXT: lbu a4, -1(a2)
; CHECK-NEXT: bne a4, a1, .LBB0_5
; CHECK-NEXT: .LBB0_8: # %if.then.loopexit1
-; CHECK-NEXT: addi a2, a2, -1
; CHECK-NEXT: li a1, 5
-; CHECK-NEXT: addi a2, a2, 1
; CHECK-NEXT: j .LBB0_12
; CHECK-NEXT: .LBB0_9: # %for.inc.jt.preheader
; CHECK-NEXT: li a1, 4