[RISCV] Combine and remove redundant ADD/SUB instructions

[eklepilkina]

Summary

Tail duplication pass can cause appearing of redundant intructions (see attached .ll test). Support the simpliest cases in separate MachineIR pass.

The number of removed instruction from statistics output on LLVM test-suite

Tests: 2025
Metric: riscv-addsub-comb.NumRemovedInstructions

Program                                       riscv-addsub-comb.NumRemovedInstructions
                                              results                                 
ultiSource...nchmarks/tramp3d-v4/tramp3d-v4    16.00                                  
ultiSource/Applications/sqlite3/sqlite3        15.00                                  
ultiSource/Applications/lemon/lemon             7.00                                  
ultiSource...ch/office-ispell/office-ispell     7.00                                  
ultiSource.../DOE-ProxyApps-C++/CLAMR/CLAMR     6.00                                  
ultiSource...chmarks/Prolangs-C/agrep/agrep     6.00                                  
ultiSource/Applications/ClamAV/clamscan         5.00                                  
ultiSource...gs-C/TimberWolfMC/timberwolfmc     2.00                                  
ultiSource...Prolangs-C/assembler/assembler     2.00                                  
ultiSource/Applications/lua/lua                 1.00                                  
ultiSource...Benchmarks/7zip/7zip-benchmark     1.00                                  
ultiSource...omotive-susan/automotive-susan     1.00

[craig.topper]

llvm/test/CodeGen/RISCV/jumptable.ll

237

This doesn’t look correct. (sext(x) -1) is not the same as sext(x-1).

Consider x==0x000000008000000. Sext(x)-1 is 0xffffffff7fffffff. Sext(x-1) is 0x000000007fffffff.

[craig.topper]

llvm/lib/Target/RISCV/CMakeLists.txt

26

This list is supposed to be alphabetical. Looks like MakeCompressible broke that, but we shouldn't make it worse.

llvm/lib/Target/RISCV/RISCVAddSubCombiner.cpp

115

Move this above the earlier if and use BaseRegister in the if

171

Cann't -> Can't

176

Reuse the iterator returned from find above

192

Register is wrapper around unsigned. Pass it by value not reference

195

llvm::find_if

236

It doesn't look like Modified is assigned anywhere else in this function

256

This should be a reference.

263

Drop curly braces

270

Do we have to assume there is only 1 def? Can we check isDef on the operand instead of checking 0?

293

Can this be llvm::is_contained?

305

You don't need to manually construct an empty vector here. Calling operator[] on line 310 will default construct the vector if it doesn't already exist. Then the push_back will be called.

323

RISCVSubtarget::getInstrINfo returns a RISCVInstrInfo *. No need for static_cast

llvm/lib/Target/RISCV/RISCVTargetMachine.cpp

242

Use != like the other places in this file

[eklepilkina]

• Upstream review fixes

[eklepilkina]

Gently ping

[craig.topper]

llvm/lib/Target/RISCV/RISCVAddSubCombiner.cpp

43

"divided by" -> "keyed by"?

148

Why is the cast to MachineInstr* needed? Isn't there an operator-> on MIB?

169

Remove extra space before RegisterUsageIter

188

Can this use llvm::erase_if?

197

llvm::erase_value?

260

llvm::is_contained?

262

Why do you need to check Operand.isDef() and modifiedRegister? Isn't isDef enough?

llvm/lib/Target/RISCV/RISCVTargetMachine.cpp

243

Should this be done before branch folding since it removes instructions which could reduce jump distance?

[eklepilkina]

llvm/lib/Target/RISCV/RISCVTargetMachine.cpp

243

This impossible, because BranchFolder is set in pipeline before TailDuplicationPass that combines these redundant instructions in one BB.

[eklepilkina]

• Upstream review fixes(2)

[craig.topper]

llvm/lib/Target/RISCV/RISCVTargetMachine.cpp

243

Sorry. I meant to write BranchRelaxation.

[eklepilkina]

• Replace pass before BranchRelaxation

[eklepilkina]

Oh, yep, I got it.

[eklepilkina]

• Fix test

[eklepilkina]

Need to mention that the number of optimized cases became much less after of rebasing on the new main and escaping combining ADDI and ADDIW on 64-bit platform

Tests: 2025
Metric: riscv-addsub-comb.NumRemovedInstructions

Program                                       riscv-addsub-comb.NumRemovedInstructions
                                              results                                 
ultiSource...nchmarks/tramp3d-v4/tramp3d-v4    16.00                                  
ultiSource/Applications/sqlite3/sqlite3        15.00                                  
ultiSource/Applications/lemon/lemon             7.00                                  
ultiSource...ch/office-ispell/office-ispell     7.00                                  
ultiSource.../DOE-ProxyApps-C++/CLAMR/CLAMR     6.00                                  
ultiSource...chmarks/Prolangs-C/agrep/agrep     6.00                                  
ultiSource/Applications/ClamAV/clamscan         5.00                                  
ultiSource...gs-C/TimberWolfMC/timberwolfmc     2.00                                  
ultiSource...Prolangs-C/assembler/assembler     2.00                                  
ultiSource/Applications/lua/lua                 1.00                                  
ultiSource...Benchmarks/7zip/7zip-benchmark     1.00                                  
ultiSource...omotive-susan/automotive-susan     1.00

[craig.topper]

llvm/lib/Target/RISCV/RISCVAddSubCombiner.cpp

189

Something looks weird here. [&Reg](std::pair<Register, bool> Element) { is repeated

[eklepilkina]

• Cherry-pick fix

[eklepilkina]

llvm/lib/Target/RISCV/RISCVAddSubCombiner.cpp

189

Sorry, cherry-picked and merged badly.

[craig.topper]

llvm/lib/Target/RISCV/RISCVAddSubCombiner.cpp

119

Drop curly braces

130

Can we update the immediate for MBBI instead of creating a new instruction?

169

Extra space here

[liaolucy]

Can add/sub combine use instcombine? Adding a new pass seems to be expensive

[eklepilkina]

Can add/sub combine use instcombine? Adding a new pass seems to be expensive

I'm afraid that this is impossible because we can't cover all cases on LLVM IR. If you look at llvm/test/CodeGen/RISCV/adds-combinations.ll added in this review, you'll see that these add instructions appear on the late passes. On LLVM IR we can have different cases that can cause generation of such combination. And it seems to me it's hard to predict this on the step of InstCombine. If you have an idea what patterns should be matched in InstCombine, please, share .

[eklepilkina]

• Upstream review fixes
• Upstream review fixes(2)
• Replace pass before BranchRelaxation
• Some more review feedback

[eklepilkina]

Fix

[reames]

I'm not convinced as to the motivation of this patch. Running the provided IR file through instcombine greatly simplifies it, and seems to remove the motivating pattern. As such, either this is an overly reduced test (which is fine, but more motivation is needed in review description), or this is fixing a pass ordering problem in the middle end in the wrong place.

Can you explain why this is the right way to fix this problem? At the moment, I'm unconvinced.

[craig.topper]

In D130769#3728922, @reames wrote:

I'm not convinced as to the motivation of this patch. Running the provided IR file through instcombine greatly simplifies it, and seems to remove the motivating pattern. As such, either this is an overly reduced test (which is fine, but more motivation is needed in review description), or this is fixing a pass ordering problem in the middle end in the wrong place.

Can you explain why this is the right way to fix this problem? At the moment, I'm unconvinced.

I agree the tests are overly reduced. Based on the description, I think this patch is trying to fix cases where tail duplication duplicates a block that originally contained a phi. This allows duplicated code to end up in the basic block that produced the original incoming value. I've seen this happen where the incoming values are constants. After duplication we end up still putting the constant in a register instead of folding it. I don't think this patch addresses that case though.

[reames]

In D130769#3730408, @craig.topper wrote:

I agree the tests are overly reduced. Based on the description, I think this patch is trying to fix cases where tail duplication duplicates a block that originally contained a phi. This allows duplicated code to end up in the basic block that produced the original incoming value. I've seen this happen where the incoming values are constants. After duplication we end up still putting the constant in a register instead of folding it. I don't think this patch addresses that case though.

That sounds plausible, but the patch itself needs to include this justification (including in reasonable tests).

If this is the use case, it really feels like something tail folding itself should be doing. Having tail folding run a forward simplify pass over the duplicated tail would seem reasonable. Not sure we have the right API for that today, but if not, maybe we should.

[eklepilkina]

• Upstream review fixes
• Upstream review fixes(2)
• Replace pass before BranchRelaxation
• Fix test
• Cherry-pick fix
• Some more review feedback

[eklepilkina]

Sorry for delay. I checked using InstCombine, but unfortuantely it doesn't help in all cases. I updated adds-combinations.ll test (please, have a look), even if I call opt with instcombine pass, it doesn't change IR in this case. Moreover, I made experiment where I added InstCombinePass after LoopStrengthReduce and measure performance, I got several regressions on benchmarks.

[eklepilkina]

Gently ping

[eklepilkina]

Gently ping

[eklepilkina]

Gently ping

llvm/lib/Target/RISCV/CMakeLists.txt

 
 add_public_tablegen_target(RISCVCommonTableGen)
 
 add_llvm_target(RISCVCodeGen
   RISCVAsmPrinter.cpp
   RISCVCallLowering.cpp
   RISCVCodeGenPrepare.cpp
   RISCVMakeCompressible.cpp
+  RISCVAddSubCombiner.cpp
   RISCVExpandAtomicPseudoInsts.cpp
   RISCVExpandPseudoInsts.cpp
   RISCVFrameLowering.cpp
   RISCVGatherScatterLowering.cpp
   RISCVInsertVSETVLI.cpp
   RISCVInstrInfo.cpp
   RISCVInstructionSelector.cpp
   RISCVISelDAGToDAG.cpp

llvm/lib/Target/RISCV/RISCV.h

 void initializeRISCVExpandAtomicPseudoPass(PassRegistry &);
 
 FunctionPass *createRISCVInsertVSETVLIPass();
 void initializeRISCVInsertVSETVLIPass(PassRegistry &);
 
 FunctionPass *createRISCVRedundantCopyEliminationPass();
 void initializeRISCVRedundantCopyEliminationPass(PassRegistry &);
 
+FunctionPass *createRISCVAddSubCombinerPass();
+void initializeRISCVAddSubCombinerPass(PassRegistry &);
+
 InstructionSelector *createRISCVInstructionSelector(const RISCVTargetMachine &,
                                                     RISCVSubtarget &,
                                                     RISCVRegisterBankInfo &);
 }
 
 #endif

llvm/lib/Target/RISCV/RISCVAddSubCombiner.cpp

+//===- 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 divided 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) {
+  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<Register, bool> 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<std::pair<Register, bool>, 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<RISCVSubtarget>();
+  TII = static_cast<const RISCVInstrInfo *>(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();
+}

llvm/lib/Target/RISCV/RISCVTargetMachine.cpp

extern "C" LLVM_EXTERNAL_VISIBILITY void LLVMInitializeRISCVTarget() {
   initializeGlobalISel(*PR);
   initializeRISCVMakeCompressibleOptPass(*PR);
   initializeRISCVGatherScatterLoweringPass(*PR);
   initializeRISCVCodeGenPreparePass(*PR);
   initializeRISCVMergeBaseOffsetOptPass(*PR);
   initializeRISCVSExtWRemovalPass(*PR);
   initializeRISCVExpandPseudoPass(*PR);
   initializeRISCVInsertVSETVLIPass(*PR);
+  initializeRISCVAddSubCombinerPass(*PR);
 }
 
 static StringRef computeDataLayout(const Triple &TT) {
   if (TT.isArch64Bit())
     return "e-m:e-p:64:64-i64:64-i128:128-n64-S128";
   assert(TT.isArch32Bit() && "only RV32 and RV64 are currently supported");
   return "e-m:e-p:32:32-i64:64-n32-S128";
 }
bool RISCVPassConfig::addGlobalInstructionSelect() {
   return false;
 }
 
 void RISCVPassConfig::addPreSched2() {}
 
 void RISCVPassConfig::addPreEmitPass() {
   addPass(&BranchRelaxationPassID);
   addPass(createRISCVMakeCompressibleOptPass());
+  if (TM->getOptLevel() > CodeGenOpt::None)
+    addPass(createRISCVAddSubCombinerPass());
 }
 
 void RISCVPassConfig::addPreEmitPass2() {
   addPass(createRISCVExpandPseudoPass());
   // Schedule the expansion of AMOs at the last possible moment, avoiding the
   // possibility for other passes to break the requirements for forward
   // progress in the LR/SC block.
   addPass(createRISCVExpandAtomicPseudoPass());

llvm/test/CodeGen/RISCV/O3-pipeline.ll

 ; CHECK-NEXT:       Machine Block Frequency Analysis
 ; CHECK-NEXT:       MachinePostDominator Tree Construction
 ; CHECK-NEXT:       Branch Probability Basic Block Placement
 ; CHECK-NEXT:       Insert fentry calls
 ; CHECK-NEXT:       Insert XRay ops
 ; 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
 ; CHECK-NEXT:     Machine Outliner
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       RISCV pseudo instruction expansion pass
 ; CHECK-NEXT:       RISCV atomic pseudo instruction expansion pass
 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:       Machine Optimization Remark Emitter
 ; CHECK-NEXT:       RISCV Assembly Printer
 ; CHECK-NEXT:       Free MachineFunction

llvm/test/CodeGen/RISCV/add-sub-combiner.mir

 # 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
 tracksRegLiveness: true
 body:             |
   bb.0:
     liveins: $x6, $x13
     ; 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
 ...
 ---
 name: redundant-adds
 tracksRegLiveness: true
 body:             |
   bb.0:
     liveins: $x6, $x13
     ; 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
     renamable $x13 = nuw ADDI killed renamable $x13, 1
     PseudoRET implicit killed $x10
 ...
 ---
 name: adds-combination-chain
 tracksRegLiveness: true
 body:             |
   bb.0:
     liveins: $x6, $x13
     ; 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
     renamable $x13 = nuw ADDIW killed renamable $x13, 7
 ...
 ---
 name: add-sub-combination
 tracksRegLiveness: true
 body:             |
   bb.0:
     liveins: $x6, $x13
     ; 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
 ...
 ---
 name: rewrite-register
 tracksRegLiveness: true
 body:             |
   bb.0:
     liveins: $x6, $x13
     ; 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
     renamable $x13 = ADDI $x0, 7
     renamable $x13 = nuw ADDI killed renamable $x13, 1
 ...
 ---
 name: different-registers-chain
 tracksRegLiveness: true
 body:             |
   bb.0:
     liveins: $x6, $x13
+    ; Negative test
     ; CHECK-LABEL: name: different-registers-chain
     ; CHECK: liveins: $x6, $x13
     ; CHECK-NEXT: {{  $}}
     ; CHECK-NEXT: renamable $x10 = ADDI $x0, 7
     ; CHECK-NEXT: renamable $x13 = ADDI killed renamable $x10, 6
     ; CHECK-NEXT: renamable $x13 = nuw ADDI killed renamable $x13, 1
     renamable $x10 = ADDI $x0, 7
     renamable $x13 = ADDI killed renamable $x10, 6
     renamable $x13 = nuw ADDI killed renamable $x13, 1
 ...
 ---
 name: add-sub-different-registers
 tracksRegLiveness: true
 body:             |
   bb.0:
     liveins: $x6, $x13
+    ; Negative test
     ; CHECK-LABEL: name: add-sub-different-registers
     ; 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, $x10
     renamable $x13 = ADD killed renamable $x13, $x0
     renamable $x10 = ADDIW $x0, 7
     renamable $x13 = SUB killed renamable $x13, $x10
 ...
 ---
 name: not-redundant-adds
 tracksRegLiveness: true
 body:             |
   bb.0:
     liveins: $x6, $x13
+    ; Negative test
     ; CHECK-LABEL: name: not-redundant-adds
     ; CHECK: liveins: $x6, $x13
     ; CHECK-NEXT: {{  $}}
     ; CHECK-NEXT: renamable $x13 = ADDI killed renamable $x13, -1
     ; CHECK-NEXT: renamable $x10 = ADDI $x13, 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 $x13, 7
     renamable $x13 = nuw ADDI killed renamable $x13, 1
     PseudoRET implicit killed $x10

llvm/test/CodeGen/RISCV/adds-combinations.ll

 ; CHECK-NEXT:    j .LBB0_6
 ; CHECK-NEXT:  .LBB0_3:
 ; CHECK-NEXT:    li a1, 0
 ; CHECK-NEXT:    j .LBB0_7
 ; CHECK-NEXT:  .LBB0_4: # %sw.bb
 ; 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
 ; CHECK-NEXT:  .LBB0_6: # %if.then
 ; CHECK-NEXT:    addi a2, a2, 1
 ; CHECK-NEXT:  .LBB0_7: # %for.end
 ; CHECK-NEXT:    sd a2, 0(a0)
 ; CHECK-NEXT:    mv a0, a1

llvm/test/CodeGen/RISCV/jumptable.ll

 ; RV32I-MEDIUM-NEXT:    li a0, 200
 ; RV32I-MEDIUM-NEXT:  .LBB1_8: # %exit
 ; RV32I-MEDIUM-NEXT:    sw a0, 0(a1)
 ; RV32I-MEDIUM-NEXT:  .LBB1_9: # %exit
 ; RV32I-MEDIUM-NEXT:    ret
 ;
 ; 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
 ; RV64I-SMALL-NEXT:    slli a0, a0, 2
 ; RV64I-SMALL-NEXT:    lui a2, %hi(.LJTI1_0)
 ; RV64I-SMALL-NEXT:    addi a2, a2, %lo(.LJTI1_0)
 ; RV64I-SMALL-NEXT:    add a0, a0, a2
 ; RV64I-SMALL-NEXT:    lw a0, 0(a0)

 ; RV64I-SMALL-NEXT:    li a0, 200
 ; RV64I-SMALL-NEXT:  .LBB1_8: # %exit
 ; RV64I-SMALL-NEXT:    sw a0, 0(a1)
 ; RV64I-SMALL-NEXT:  .LBB1_9: # %exit
 ; RV64I-SMALL-NEXT:    ret
 ;
 ; 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
 ; RV64I-MEDIUM-NEXT:    slli a0, a0, 3
 ; RV64I-MEDIUM-NEXT:  .LBB1_10: # %entry
 ; RV64I-MEDIUM-NEXT:    # Label of block must be emitted
 ; RV64I-MEDIUM-NEXT:    auipc a2, %pcrel_hi(.LJTI1_0)
 ; RV64I-MEDIUM-NEXT:    addi a2, a2, %pcrel_lo(.LBB1_10)

llvm/test/CodeGen/RISCV/sext-zext-trunc.ll

 ; RV32I:       # %bb.0:
 ; RV32I-NEXT:    addi a0, a0, -7
 ; RV32I-NEXT:    snez a0, a0
 ; RV32I-NEXT:    neg a0, a0
 ; RV32I-NEXT:    ret
 ;
 ; 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
   %cmp = icmp eq i32 %x, 7
   %xor = xor i1 %cmp, 1
   %sext = sext i1 %xor to i32
   ret i32 %sext
 }

 ; RV32I:       # %bb.0:
 ; RV32I-NEXT:    addi a0, a0, -7
 ; RV32I-NEXT:    seqz a0, a0
 ; RV32I-NEXT:    addi a0, a0, -1
 ; RV32I-NEXT:    ret
 ;
 ; 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
   %cmp = icmp eq i32 %x, 7
   %zext = zext i1 %cmp to i32
   %dec = sub i32 %zext, 1
   ret i32 %dec
 }