[RISCV] Add pre-emit pass to make more instructions compressible

[lewis-revill]

Summary

When optimizing for size, this pass searches for instructions that are
prevented from being compressed by one of the following:

1. The use of a single uncompressed register.
2. A base register + offset where the offset is too large to be compressed and the base register may or may not already be compressed.

In the first case, if there is a compressed register available, then the
uncompressed register is copied to the compressed register and its uses
replaced. This is only done if there are enough uses that code size
would be improved.

In the second case, if a compressed register is available, then the
original base register is copied and adjusted such that:

new_base_register = base_register + adjustment
base_register + large_offset = new_base_register + small_offset

and the uses of the base register are replaced with the new base
register. Again this is only done if there are enough uses for code size
to be improved.

This pass was authored by Lewis Revill, with large offset optimization
added by Craig Blackmore.

[jrtc27]

llvm/test/CodeGen/RISCV/compress-instrs.ll

1 ↗

(On Diff #307605)

This should be a MIR test running just the new pass so it's less fragile (and can also test more interesting cases where it's hard to coerce CodeGen into creating uncompressible instructions)

[frasercrmck]

llvm/lib/Target/RISCV/RISCVCompressInstrs.cpp

215

Is this a strict enough check for "definition"? What about super- and sub-registers or clobbers? Would MI.modifiesRegister work better (and be simpler)?

263

Same question about defined...ness here.

279

Nit: redundant parens.

[craigblackmore]

Updated to address feedback from @jrtc27 and @frasercrmck and fix lint warnings.

[craigblackmore]

llvm/lib/Target/RISCV/RISCVCompressInstrs.cpp

215

Thanks, MI.modifiesRegister is better and makes this check much simpler.

263

At the moment isDef is sufficient as we are only expecting LW or SW. Given we are post regalloc, that means only physical integer registers (which do not have subregisters). I have added an assert so that it is clear we are only expecting LW or SW and a comment to say that the definedness check may need to be strengthened if the pass is extended to support more instructions.

llvm/test/CodeGen/RISCV/compress-instrs.ll

1 ↗

(On Diff #307605)

Thanks, I have replaced this with a MIR test.

[jrtc27]

llvm/test/CodeGen/RISCV/compress-instrs.mir

3

Please indent continuation lines with an additional 4 spaces.

[jrtc27]

llvm/test/CodeGen/RISCV/compress-instrs.mir

3

Or maybe the style is just 2. For | it seems to be generally 2, but for arguments that wrap it seems to be any of 2, 3 or 4 depending on where you look.

[craigblackmore]

Indented continuation lines in the MIR test. I couldn't see a consistent style, so opted for an indent of 2.

[craigblackmore]

Ping.

[craig.topper]

llvm/lib/Target/RISCV/CMakeLists.txt

25

I think these were in alphabetical order

llvm/lib/Target/RISCV/RISCVCompressInstrs.cpp

201

Use SmallVectorImpl so you don't need to repeat the 8 from the caller.

[craigblackmore]

Addressed comments from @craig.topper.

[jrtc27]

Some comments about current hard-coded assumptions. Whilst only supporting LW/SW at the moment is fine, I don't think it's a good idea to have such assumptions embedded in the design; instead it should be approximately general enough that other widths and types can be added at a later date without overhauling its core (i.e. just adding some more cases). Though at that point you might as well just support LD/SD and FLW/FSW/FLD/FSD given it'd then be trivial...

llvm/lib/Target/RISCV/RISCVCompressInstrs.cpp

100

Compute this based on the size of the register being loaded/stored, as this approach does not generalise.

105

You'll need the type here.

142

Ditto; compute this based on the size of the register.

190

NoRegister

245

You need the type of the register (int or float) in order to support compressing floating-point loads/stores (and so we can support capabilities in our downstream CHERI fork, both for the base and for the source/destination).

[craigblackmore]

Removed hard-coded assumptions noted by @jrtc27 and rebased. Thank you for the review and apologies for the delay in updating the patch.

[asb]

This looks good to me - many thanks for the contribution.

@jrtc27 - are you happy your comments were all addressed?

[jrtc27]

I don't understand why this is still limited to just LW and SW; you have all the bits for dealing with the differing immediate shifts already so it should be ~no effort to add LD and SD on top, and floating-point variants are just supporting additional register classes for the source and destination, some of which you again already have code for.

llvm/lib/Target/RISCV/RISCVCompressInstrs.cpp

109

Comment says bytes, this is bits

125

This is just 31 * width_in_bytes (or 31 << log2(width_in_bytes))

134

If this returned log2(bytes) (or you could compute it, but every user of the function is happy with log2(bytes)) then this is just

return isUIntN(6 + log2(bytes), Offset) && (Offset % (UINT64_C(1) << log2(bytes)) == 0);

(inlining a non-templated version of isShiftedUInt, since we don't seem to have an isShiftedUIntN in MathExtras.h, though perhaps it'd be better to just add it). Ditto for compressibleOffset just with 5 not 6.

164

You don't need the parens

215

There's a lot of duplicated code between loads and stores

[craigblackmore]

Add support for LD/SD/FLW/FLD/FSW/FSD and address other inline comments from @jrtc27.

[jrtc27]

llvm/lib/Target/RISCV/RISCVCompressInstrs.cpp

182

Stray semicolon

190

Can also be scaled by 8 for double-sized quantities (and 16 for us downstream). The scaling isn't really relevant here, just that it has a larger immediate (and no source/destination register restriction, as you already note).

195

Not rs2 in the case of loads, so I guess SrcDest or something?

203

I think this would be more helpful if it then went on to say what it actually did for stores

206

How often is storing an address to itself at offset 0 actually hit?..

207

I can't obviously see tests that exercise this?

llvm/test/CodeGen/RISCV/compress-instrs-i32-f-d.mir

1 ↗

(On Diff #388866)

These will need +f and +d given you use F[LS][WD]

32 ↗

(On Diff #388866)

Why null for all of these? That seems like a bad idea...

80 ↗

(On Diff #388866)

This would be better as an offset to a real pointer, not a horrible inttoptr of a constant

[jrtc27]

llvm/lib/Target/RISCV/RISCVCompressInstrs.cpp

2

File name is also misleading. Makes it sound like where instruction compression happens, but it's not, it's a transformation to make the instructions more amenable to compression, at the expense (in most cases) of instruction count.

220

You can get the MBB from the MI, otherwise you risk passing the wrong MBB

298

What if you hit a def of the new register?

348

What about when Imm is 0 and all uses can be updated?

356

Is it ever possible for this to return false on anything other than the final MI? Shouldn't analyzeCompressibleUses have stopped on such an instruction?

[craig.topper]

llvm/lib/Target/RISCV/RISCVCompressInstrs.cpp

78

This is also misleading like the filename.

101

There's little reason for this to return uint8_t. Just use unsigned.

140

Why do we need to compressibleOffset? Wouldn't the Offset & ~compressedLDSTOffsetMask(Opcode) return 0 for the same cases?

147

Function name should start with a verb action so isCompressedReg

154

isCompressibleLoad

160

isCompressibleStore

247

There should be a comma after instruction.

248

Comma after compressed

[craigblackmore]

Thank you for the reviews. I have updated based on the feedback and rebased.

[jrtc27]

llvm/lib/Target/RISCV/RISCVMakeCompressible.cpp

146 ↗

(On Diff #413085)

You don't want to be transforming FLW on RV64, that's reused for the LD encodings (ditto stores)

164 ↗

(On Diff #413085)

Weird spacing

llvm/test/CodeGen/RISCV/make-compressible-i32-f-d.mir

1 ↗

(On Diff #413085)

The names for these are a bit dodgy IMO in that they encode far too much about the specific instruction sets used, so changing that requires changing the name. Maybe make-compressible.mir and the RV64-only one to be make-compressible-rv64.mir? Or split fp out from i32 into its own file?

42 ↗

(On Diff #413085)

Please don't, ptrtoint is a terrible thing... store %p itself to a bitcasted %p

[craigblackmore]

llvm/lib/Target/RISCV/RISCVCompressInstrs.cpp

207

I have added tests for this now.

298

I have added a comment about this.

// The new register was scavenged for the range of instructions that are
// being updated, therefore it should not be defined within this range
// except possibly in the final instruction.

348

I have added a TODO to possibly update all uses in the future.

356

I have removed the check of the return value and removed the bool from updateOperands since it is no longer used.

[craigblackmore]

Address latest review.

• No longer transforming FLW/FSW on 64-bit.
• Fixed weird spacing.
• Renamed test files.
• Used bitcast instead of ptrtoint.

[asb]

Any thoughts from anyone on whether this should be turned on at Oz only? It can certainly increase the number of instructions executed.

[craigblackmore]

Enable at -Oz instead of -Os.

[luismarques]

Do you have an example of a benchmark or some other codebase where this pass makes a difference? I tested this in 3 different places and there were no changes at all.

[luismarques]

In D92105#3413974, @luismarques wrote:

I tested this in 3 different places and there were no changes at all.

Actually, in OpenTitan I see up to 0.5% code size gains (60 bytes) in the best case.

[craigblackmore]

The pass saves 456 bytes (0.76%) on a proprietary application.

[luismarques]

If no one has additional concerns I think this could be merged.
Thanks for the info regarding the code size gains.

[asb]

@craigblackmore: could you please take a look at compiling complex-2.c from the GCC torture suite with this patch. I'm getting incorrect output for RV32IMAFDC at Oz:

./output_rv32imafdc_ilp32_Oz/complex-2.s:16:7: error: invalid operand for instruction
        addi    fa0, ft0, 0
                ^
./output_rv32imafdc_ilp32_Oz/complex-2.s:18:7: error: invalid operand for instruction
        addi    fa1, ft1, 0
                ^

[lewis-revill]

Rebased including an update from using isShiftedUIntN to the templated replacement isShiftedUInt<N, S>. Addressed the issue of inserting incorrect instructions to copy FP registers to compressible FP registers by using FSGNJ_S and FSGNJ_D instead. We note that we can't have an additional offset to adjust the resulting register by if it is an FP register.

[reames]

Drive by review. I'm mostly using this as an exercise to get familiar with the code and the target, so please don't consider any of my comments blocking.

llvm/lib/Target/RISCV/RISCVMakeCompressible.cpp

100 ↗

(On Diff #424881)

I would expect us to have a means for querying the width of a load/store somewhere, and for this to simply be the log of an existing utility. I haven't dug around, but are you sure that doesn't exist?

126 ↗

(On Diff #424881)

Don't we have a means already for computing max offset representable in the addressing of an instruction? I'd expect us to,

305 ↗

(On Diff #424881)

It's not clear me to me why the last instruction has to be a load as this assert would seem to imply. Could we instead directly assert this is the last instruction somehow?

320 ↗

(On Diff #424881)

While this is a size opt, I'd expect improving code density to outweigh the effect of an extra register move and/or add. We should measure, but this might be useful even for O2.

343 ↗

(On Diff #424881)

The algorithm here appears to be O(N^2). Can we do better here?

[lewis-revill]

In D92105#3474670, @reames wrote:

Drive by review. I'm mostly using this as an exercise to get familiar with the code and the target, so please don't consider any of my comments blocking.

Thanks very much for the review

llvm/lib/Target/RISCV/RISCVMakeCompressible.cpp

100 ↗

(On Diff #424881)

I've had a brief look, and it seems to me the only existing way would be to use MI.memoperands_begin()->getSize(). Doesn't seem to be anything simple in TargetInstrInfo.h that we can use/override either to get this functionality.

126 ↗

(On Diff #424881)

No, every place which would need to check this just repeats the same logic since it's so simple.

305 ↗

(On Diff #424881)

We only look at loads and stores for compressibility, and as such if we see a compressible instruction which also defines the register we know it is a compressible load. We also know that since we stop when we see the next definition of the register we are looking at, but only after we've checked the defining instruction for compressibility. So the only way we are looking at a definition is if it's the final instruction.

320 ↗

(On Diff #424881)

Until recently this was enabled at -Os but changed to -Oz due to the increase in number of instructions executed. I suggest keeping at -Oz and changing this later if there is a motivation for it.

343 ↗

(On Diff #424881)

Hmm, I guess there'd be a way to accumulate the ranges that we're interested in as we go through in one iteration - though I think this would be far more difficult to implement and you might end up with issues to do with looking at instructions which are yet to be updated and making incorrect conclusions (I don't see any cause for that at a first glance but it's always possible).

[JunningWu]

In D92105#3419257, @craigblackmore wrote:

The pass saves 456 bytes (0.76%) on a proprietary application.

The pass saves 160 bytes (0.101%) on a proprietary application, from 157974 bytes-->157814 bytes.

[asb]

At the last sync-up call, @reames I believe said he had no further blocking comments (thanks for the review on this Philip). I think we're good to land this Lewis if you're happy with the current code.

[lewis-revill]

Rebased prior to commit

[iiiyours]

This comment was removed by iiiyours.

llvm/lib/Target/RISCV/CMakeLists.txt

 tablegen(LLVM RISCVGenSystemOperands.inc -gen-searchable-tables)
 
 add_public_tablegen_target(RISCVCommonTableGen)
 
 add_llvm_target(RISCVCodeGen
   RISCVAsmPrinter.cpp
   RISCVCallLowering.cpp
   RISCVExpandAtomicPseudoInsts.cpp
+  RISCVCompressInstrs.cpp
   RISCVExpandPseudoInsts.cpp
   RISCVFrameLowering.cpp
   RISCVInstrInfo.cpp
   RISCVInstructionSelector.cpp
   RISCVISelDAGToDAG.cpp
   RISCVISelLowering.cpp
   RISCVLegalizerInfo.cpp
   RISCVMCInstLower.cpp

llvm/lib/Target/RISCV/RISCV.h

 
 void LowerRISCVMachineInstrToMCInst(const MachineInstr *MI, MCInst &OutMI,
                                     const AsmPrinter &AP);
 bool LowerRISCVMachineOperandToMCOperand(const MachineOperand &MO,
                                          MCOperand &MCOp, const AsmPrinter &AP);
 
 FunctionPass *createRISCVISelDag(RISCVTargetMachine &TM);
 
+FunctionPass *createRISCVCompressInstrsOptPass();
+void initializeRISCVCompressInstrsOptPass(PassRegistry &);
+
 FunctionPass *createRISCVMergeBaseOffsetOptPass();
 void initializeRISCVMergeBaseOffsetOptPass(PassRegistry &);
 
 FunctionPass *createRISCVExpandPseudoPass();
 void initializeRISCVExpandPseudoPass(PassRegistry &);
 
 FunctionPass *createRISCVExpandAtomicPseudoPass();
 void initializeRISCVExpandAtomicPseudoPass(PassRegistry &);
 
 InstructionSelector *createRISCVInstructionSelector(const RISCVTargetMachine &,
                                                     RISCVSubtarget &,
                                                     RISCVRegisterBankInfo &);
 }
 
 #endif

llvm/lib/Target/RISCV/RISCVCompressInstrs.cpp

+//===-- RISCVCompressInstrs.cpp - Make instructions compressible ----------===//
+//
+// 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 pass searches for instructions that are prevented from being compressed
+// by one of the following:
+//
+//   1. The use of a single uncompressed register.
+//   2. A base register + offset where the offset is too large to be compressed
+//   and the base register may or may not be compressed.
+//
+//
+// For case 1, if a compressed register is available, then the uncompressed
+// register is copied to the compressed register and its uses are replaced.
+//
+// For example, storing zero uses the uncompressible zero register:
+//   sw zero, 0(a0)   # if zero
+//   sw zero, 8(a0)   # if zero
+//   sw zero, 4(a0)   # if zero
+//   sw zero, 24(a0)   # if zero
+//
+// If a compressed register (e.g. a1) is available, the above can be transformed
+// to the following to improve code size:
+//   li a1, 0
+//   c.sw a1, 0(a0)
+//   c.sw a1, 8(a0)
+//   c.sw a1, 4(a0)
+//   c.sw a1, 24(a0)
+//
+//
+// For case 2, if a compressed register is available, then the original base
+// is copied and adjusted such that:
+//
+//   new_base_register = base_register + adjustment
+//   base_register + large_offset = new_base_register + small_offset
+//
+// For example, the following offsets are too large for c.sw:
+//   lui a2, 983065
+//   sw  a1, -236(a2)
+//   sw  a1, -240(a2)
+//   sw  a1, -244(a2)
+//   sw  a1, -248(a2)
+//   sw  a1, -252(a2)
+//   sw  a0, -256(a2)
+//
+// If a compressed register is available (e.g. a3), a new base could be created
+// such that the addresses can accessed with a compressible offset, thus
+// improving code size:
+//   lui a2, 983065
+//   addi  a3, a2, -256
+//   c.sw  a1, 20(a3)
+//   c.sw  a1, 16(a3)
+//   c.sw  a1, 12(a3)
+//   c.sw  a1, 8(a3)
+//   c.sw  a1, 4(a3)
+//   c.sw  a0, 0(a3)
+//
+//
+// This optimization is only applied if there are enough uses of the copied
+// register for code size to be reduced.
+//
+//===----------------------------------------------------------------------===//
+
+#include "RISCV.h"
+#include "RISCVSubtarget.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/RegisterScavenging.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/TargetRegistry.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "riscv-compress-instrs"
+#define RISCV_COMPRESS_INSTRS_NAME "RISCV Compress Instructions"
+
+namespace {
+
+struct RISCVCompressInstrsOpt : public MachineFunctionPass {
+  static char ID;
+
+  bool runOnMachineFunction(MachineFunction &Fn) override;
+
+  RISCVCompressInstrsOpt() : MachineFunctionPass(ID) {
+    initializeRISCVCompressInstrsOptPass(*PassRegistry::getPassRegistry());
+  }
+
+  StringRef getPassName() const override { return RISCV_COMPRESS_INSTRS_NAME; }
+};
+} // namespace
+
+char RISCVCompressInstrsOpt::ID = 0;
+INITIALIZE_PASS(RISCVCompressInstrsOpt, "riscv-compress-instrs",
+                RISCV_COMPRESS_INSTRS_NAME, false, false)
+
+static const uint8_t CSWOffsetMask = 0b1111100;
+
+// Given an offset for a load/store, return the adjustment required to the base
+// register such that the address can be accessed with a compressible offset.
+// Return 0 if the offset is already compressible.
+static int64_t getBaseAdjustForCompression(int64_t Offset) {
+  if (isShiftedUInt<5, 2>(Offset))
+    return 0;
+  // Return the excess bits that do not fit in a compressible offset.
+  return Offset & ~(CSWOffsetMask);
+}
+
+// Find a single register and/or large offset which, if compressible, would
+// allow the given instruction to be compressed.
+//
+// Possible return values:
+//   {Reg, 0}          - Uncompressed Reg needs replacing with a compressed
+//                       register.
+//   {Reg, N}          - Reg needs replacing with a compressed register and
+//                       N needs adding to the new register. (Reg may be
+//                       compressed or uncompressed).
+//   {Register(0), 0}  - No suitable optimization found for this instruction.
+static RegImmPair getRegImmPairPreventingCompression(const MachineInstr &MI) {
+  int64_t NewBaseAdjust = 0;
+
+  switch (MI.getOpcode()) {
+  default:
+    break;
+  case RISCV::LW: {
+    const MachineOperand &MOImm = MI.getOperand(2);
+    if (!MOImm.isImm())
+      break;
+
+    int64_t Offset = MOImm.getImm();
+
+    NewBaseAdjust = getBaseAdjustForCompression(Offset);
+
+    Register Base = MI.getOperand(1).getReg();
+    // Load from stack pointer does not have a requirement for either of the
+    // registers to be compressible and the offset can be a 6 bit immediate
+    // scaled by 4.
+    if (RISCV::SPRegClass.contains(Base)) {
+      if (!isShiftedUInt<6, 2>(Offset) && NewBaseAdjust)
+        return RegImmPair(Base, NewBaseAdjust);
+      break;
+    }
+
+    Register Dest = MI.getOperand(0).getReg();
+    bool DestCompressed = RISCV::GPRCRegClass.contains(Dest);
+    bool BaseCompressed = RISCV::GPRCRegClass.contains(Base);
+
+    // For loads we can only change the base register since dest is defined
+    // rather than used.
+    if ((!BaseCompressed || NewBaseAdjust) && DestCompressed)
+      return RegImmPair(Base, NewBaseAdjust);
+
+    break;
+  }
+  case RISCV::SW: {
+    const MachineOperand &MOImm = MI.getOperand(2);
+    if (!MOImm.isImm())
+      break;
+
+    int64_t Offset = MOImm.getImm();
+
+    NewBaseAdjust = getBaseAdjustForCompression(Offset);
+
+    Register Base = MI.getOperand(1).getReg();
+    // Store to stack pointer does not have a requirement for either of the
+    // registers to be compressible and the offset can be a 6 bit immediate
+    // scaled by 4.
+    if (RISCV::SPRegClass.contains(Base)) {
+      if (!isShiftedUInt<6, 2>(Offset) && NewBaseAdjust)
+        return RegImmPair(Base, NewBaseAdjust);
+      break;
+    }
+
+    Register Src = MI.getOperand(0).getReg();
+    bool SrcCompressed = RISCV::GPRCRegClass.contains(Src);
+    bool BaseCompressed = RISCV::GPRCRegClass.contains(Base);
+
+    // Cannot resolve uncompressible offset if we are resolving src reg
+    if (!SrcCompressed && (BaseCompressed || Src == Base) && !NewBaseAdjust)
+      return RegImmPair(Src, NewBaseAdjust);
+    if ((!BaseCompressed || NewBaseAdjust) && SrcCompressed)
+      return RegImmPair(Base, NewBaseAdjust);
+
+    break;
+  }
+  }
+  return RegImmPair(Register(0), 0);
+}
+
+// Check all uses after FirstMI of the given register, keeping a vector of
+// instructions that would be compressible if the given register (and offset if
+// applicable) were compressible.
+//
+// If there are enough uses for this optimization to improve code size and a
+// compressed register is available, return that compressed register.
+static Register analyzeCompressibleUses(MachineBasicBlock &MBB,
+                                        MachineInstr &FirstMI,
+                                        RegImmPair RegImm,
+                                        SmallVector<MachineInstr *, 8> &MIs) {
+  const TargetRegisterInfo *TRI =
+      MBB.getParent()->getSubtarget().getRegisterInfo();
+
+  RegScavenger RS;
+  RS.enterBasicBlock(MBB);
+
+  for (MachineBasicBlock::instr_iterator I = FirstMI.getIterator(),
+                                         E = MBB.instr_end();
+       I != E; ++I) {
+    MachineInstr &MI = *I;
+
+    // Determine if this is an instruction which would benefit from using the
+    // new register.
+    RegImmPair CandidateRegImm = getRegImmPairPreventingCompression(MI);
+    if (CandidateRegImm.Reg == RegImm.Reg &&
+        CandidateRegImm.Imm == RegImm.Imm) {
+      // Advance tracking since the value in the new register must be live for
+      // this instruction too.
+      RS.forward(I);
+
+      MIs.push_back(&MI);
+    }
+
+    // If RegImm.Reg is modified by this instruction then we cannot optimize
+    // past this instruction. If the register is already compressed then it may
+    // possible to optimize a large offset in the current instruction - this
+    // will have been detected by the preceeding call to
+    // getRegImmPairPreventingCompression.
+    if (MI.modifiesRegister(RegImm.Reg, TRI))
+      break;
+  }
+
+  // Adjusting the base costs one new uncompressed addi and therefore three uses
+  // are required for a code size reduction. If no base adjustment is required,
+  // then copying the register costs one new c.mv (or c.li Rd, 0 for "copying"
+  // the zero register) and therefore two uses are required for a code size
+  // reduction.
+  if (MIs.size() < 2 || (RegImm.Imm != 0 && MIs.size() < 3))
+    return Register(0);
+
+  // Find a compressible register which will be available from the first
+  // instruction we care about to the last.
+  return RS.scavengeRegisterBackwards(RISCV::GPRCRegClass,
+                                      FirstMI.getIterator(),
+                                      /*RestoreAfter=*/false, /*SPAdj=*/0,
+                                      /*AllowSpill=*/false);
+}
+
+// Update uses of the old register in the given instruction to the new register.
+// Return false if no further instructions should be updated.
+static bool updateOperands(MachineInstr &MI, RegImmPair OldRegImm,
+                           Register NewReg) {
+  bool UpdatesAllowed = true;
+
+  // If this pass is extended to support more instructions, the check for
+  // definedness may need to be strengthened.
+  assert((MI.getOpcode() == RISCV::LW || MI.getOpcode() == RISCV::SW) &&
+         "Unsupported instruction for this optimization.");
+
+  // Update registers
+  for (MachineOperand &MO : MI.operands())
+    if (MO.isReg() && MO.getReg() == OldRegImm.Reg) {
+      // Do not update operands that define the old register.
+      if (MO.isDef()) {
+        assert(MI.getOpcode() == RISCV::LW);
+        // Don't allow any more updates after optimizing LW where OldRegImm.Reg
+        // is defined and don't update this register.
+        UpdatesAllowed = false;
+        continue;
+      }
+      // Update reg
+      MO.setReg(NewReg);
+    }
+
+  // Update offset
+  if (MI.getOpcode() == RISCV::LW || MI.getOpcode() == RISCV::SW) {
+    MachineOperand &MOImm = MI.getOperand(2);
+    int64_t NewOffset = MOImm.getImm() & CSWOffsetMask;
+    MOImm.setImm(NewOffset);
+  }
+
+  return UpdatesAllowed;
+}
+
+bool RISCVCompressInstrsOpt::runOnMachineFunction(MachineFunction &Fn) {
+  // This is a size optimization.
+  if (skipFunction(Fn.getFunction()) || !Fn.getFunction().hasOptSize())
+    return false;
+
+  const RISCVSubtarget &STI = Fn.getSubtarget<RISCVSubtarget>();
+  const RISCVInstrInfo &TII = *STI.getInstrInfo();
+
+  // This optimization only makes sense if compressed instructions are emitted.
+  if (!STI.hasStdExtC())
+    return false;
+
+  for (MachineBasicBlock &MBB : Fn) {
+    LLVM_DEBUG(dbgs() << "MBB: " << MBB.getName() << "\n");
+    for (MachineInstr &MI : MBB) {
+      // Determine if this instruction would otherwise be compressed if not for
+      // an uncompressible register or offset.
+      RegImmPair RegImm = getRegImmPairPreventingCompression(MI);
+      if (!RegImm.Reg && RegImm.Imm == 0)
+        continue;
+
+      // Determine if there is a set of instructions for which replacing this
+      // register with a compressed register (and compressible offset if
+      // applicable) is possible and will allow compression.
+      SmallVector<MachineInstr *, 8> MIs;
+      Register NewReg = analyzeCompressibleUses(MBB, MI, RegImm, MIs);
+      if (!NewReg)
+        continue;
+
+      assert(isInt<12>(RegImm.Imm));
+      BuildMI(MBB, MI, MI.getDebugLoc(), TII.get(RISCV::ADDI), NewReg)
+          .addReg(RegImm.Reg)
+          .addImm(RegImm.Imm);
+
+      // Update the set of instructions to use the compressed register and
+      // compressible offset instead. These instructions should now be
+      // compressible.
+      for (MachineInstr *UpdateMI : MIs)
+        if (!updateOperands(*UpdateMI, RegImm, NewReg))
+          break;
+    }
+  }
+  return true;
+}
+
+/// Returns an instance of the Compress Instructions Optimization pass.
+FunctionPass *llvm::createRISCVCompressInstrsOptPass() {
+  return new RISCVCompressInstrsOpt();
+}

llvm/lib/Target/RISCV/RISCVTargetMachine.cpp

 #include "llvm/Target/TargetOptions.h"
 using namespace llvm;
 
 extern "C" LLVM_EXTERNAL_VISIBILITY void LLVMInitializeRISCVTarget() {
   RegisterTargetMachine<RISCVTargetMachine> X(getTheRISCV32Target());
   RegisterTargetMachine<RISCVTargetMachine> Y(getTheRISCV64Target());
   auto PR = PassRegistry::getPassRegistry();
   initializeGlobalISel(*PR);
+  initializeRISCVCompressInstrsOptPass(*PR);
   initializeRISCVExpandPseudoPass(*PR);
 }
 
 static StringRef computeDataLayout(const Triple &TT) {
   if (TT.isArch64Bit()) {
     return "e-m:e-p:64:64-i64:64-i128:128-n64-S128";
   } else {
     assert(TT.isArch32Bit() && "only RV32 and RV64 are currently supported");

 
 bool RISCVPassConfig::addGlobalInstructionSelect() {
   addPass(new InstructionSelect());
   return false;
 }
 
 void RISCVPassConfig::addPreSched2() {}
 
-void RISCVPassConfig::addPreEmitPass() { addPass(&BranchRelaxationPassID); }
+void RISCVPassConfig::addPreEmitPass() {
+  addPass(&BranchRelaxationPassID);
+  addPass(createRISCVCompressInstrsOptPass());
+}
 
 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());
 }
 
 void RISCVPassConfig::addPreRegAlloc() {
   addPass(createRISCVMergeBaseOffsetOptPass());
 }

llvm/test/CodeGen/RISCV/compress-instrs.mir

+# RUN: llc -o - %s -mtriple=riscv32 -mattr=+c -simplify-mir \
+# RUN:   -run-pass=riscv-compress-instrs | FileCheck %s
+# RUN: llc -o - %s -mtriple=riscv64 -mattr=+c -simplify-mir \
+# RUN:   -run-pass=riscv-compress-instrs | FileCheck %s
+--- |
+  define void @store_common_value(i32* %a, i32* %b, i32* %c) #0 {
+  entry:
+    store i32 0, i32* %a, align 4
+    store i32 0, i32* %b, align 4
+    store i32 0, i32* %c, align 4
+    ret void
+  }
+
+  define void @store_common_ptr() #0 {
+  entry:
+    store volatile i32 1, i32* null, align 4
+    store volatile i32 3, i32* null, align 4
+    store volatile i32 5, i32* null, align 4
+    ret void
+  }
+
+  define void @load_common_ptr() #0 {
+  entry:
+    %a = load volatile i32, i32* null, align 4
+    %b = load volatile i32, i32* null, align 4
+    %c = load volatile i32, i32* null, align 4
+    ret void
+  }
+
+  define void @store_large_offset() #0 {
+  entry:
+    store volatile i32 1, i32* inttoptr (i32 305421696 to i32*), align 4
+    store volatile i32 3, i32* inttoptr (i32 305421700 to i32*), align 4
+    store volatile i32 5, i32* inttoptr (i32 305421704 to i32*), align 4
+    store volatile i32 7, i32* inttoptr (i32 305421708 to i32*), align 4
+    ret void
+  }
+
+  define void @load_large_offset() #0 {
+  entry:
+    %a = load volatile i32, i32* inttoptr (i32 305421696 to i32*), align 4
+    %b = load volatile i32, i32* inttoptr (i32 305421700 to i32*), align 4
+    %c = load volatile i32, i32* inttoptr (i32 305421704 to i32*), align 4
+    %d = load volatile i32, i32* inttoptr (i32 305421708 to i32*), align 4
+    ret void
+  }
+
+  define void @store_common_value_no_opt(i32* %a, i32* %b, i32* %c) #0 {
+  entry:
+    store i32 0, i32* %a, align 4
+    ret void
+  }
+
+  define void @store_common_ptr_no_opt() #0 {
+  entry:
+    store volatile i32 1, i32* null, align 4
+    ret void
+  }
+
+  define void @load_common_ptr_no_opt() #0 {
+  entry:
+    %a = load volatile i32, i32* null, align 4
+    ret void
+  }
+
+  define void @store_large_offset_no_opt() #0 {
+  entry:
+    store volatile i32 1, i32* inttoptr (i32 305421696 to i32*), align 4
+    store volatile i32 3, i32* inttoptr (i32 305421700 to i32*), align 4
+    ret void
+  }
+
+  define void @load_large_offset_no_opt() #0 {
+  entry:
+    %a = load volatile i32, i32* inttoptr (i32 305421696 to i32*), align 4
+    %b = load volatile i32, i32* inttoptr (i32 305421700 to i32*), align 4
+    ret void
+  }
+
+  attributes #0 = { optsize "target-features"="+c" }
+
+...
+---
+name:            store_common_value
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+    liveins: $x10, $x11, $x12
+    ; CHECK-LABEL: name: store_common_value
+    ; CHECK: $x13 = ADDI $x0, 0
+    ; CHECK-NEXT: SW $x13, killed renamable $x10, 0 :: (store 4 into %ir.a)
+    ; CHECK-NEXT: SW $x13, killed renamable $x11, 0 :: (store 4 into %ir.b)
+    ; CHECK-NEXT: SW $x13, killed renamable $x12, 0 :: (store 4 into %ir.c)
+    SW $x0, killed renamable $x10, 0 :: (store 4 into %ir.a)
+    SW $x0, killed renamable $x11, 0 :: (store 4 into %ir.b)
+    SW $x0, killed renamable $x12, 0 :: (store 4 into %ir.c)
+    PseudoRET
+
+...
+---
+name:            store_common_ptr
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+    ; CHECK-LABEL: name: store_common_ptr
+    ; CHECK: renamable $x10 = ADDI $x0, 1
+    ; CHECK-NEXT: $x11 = ADDI $x0, 0
+    ; CHECK-NEXT: SW killed renamable $x10, $x11, 0 :: (volatile store 4 into `i32* null`)
+    ; CHECK-NEXT: renamable $x10 = ADDI $x0, 3
+    ; CHECK-NEXT: SW killed renamable $x10, $x11, 0 :: (volatile store 4 into `i32* null`)
+    ; CHECK-NEXT: renamable $x10 = ADDI $x0, 5
+    ; CHECK-NEXT: SW killed renamable $x10, $x11, 0 :: (volatile store 4 into `i32* null`)
+    renamable $x10 = ADDI $x0, 1
+    SW killed renamable $x10, $x0, 0 :: (volatile store 4 into `i32* null`)
+    renamable $x10 = ADDI $x0, 3
+    SW killed renamable $x10, $x0, 0 :: (volatile store 4 into `i32* null`)
+    renamable $x10 = ADDI $x0, 5
+    SW killed renamable $x10, $x0, 0 :: (volatile store 4 into `i32* null`)
+    PseudoRET
+
+...
+---
+name:            load_common_ptr
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+    ; CHECK-LABEL: name: load_common_ptr
+    ; CHECK: $x11 = ADDI $x0, 0
+    ; CHECK-NEXT: dead renamable $x10 = LW $x11, 0 :: (volatile load 4 from `i32* null`)
+    ; CHECK-NEXT: dead renamable $x10 = LW $x11, 0 :: (volatile load 4 from `i32* null`)
+    ; CHECK-NEXT: dead renamable $x10 = LW $x11, 0 :: (volatile load 4 from `i32* null`)
+    dead renamable $x10 = LW $x0, 0 :: (volatile load 4 from `i32* null`)
+    dead renamable $x10 = LW $x0, 0 :: (volatile load 4 from `i32* null`)
+    dead renamable $x10 = LW $x0, 0 :: (volatile load 4 from `i32* null`)
+    PseudoRET
+
+...
+---
+name:            store_large_offset
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+    ; CHECK-LABEL: name: store_large_offset
+    ; CHECK: renamable $x10 = LUI 74566
+    ; CHECK-NEXT: renamable $x11 = ADDI $x0, 1
+    ; CHECK-NEXT: $x12 = ADDI $x10, -640
+    ; CHECK-NEXT: SW killed renamable $x11, $x12, 0 :: (volatile store 4 into `i32* inttoptr (i32 305421696 to i32*)`)
+    ; CHECK-NEXT: renamable $x11 = ADDI $x0, 3
+    ; CHECK-NEXT: SW killed renamable $x11, $x12, 4 :: (volatile store 4 into `i32* inttoptr (i32 305421700 to i32*)`)
+    ; CHECK-NEXT: renamable $x11 = ADDI $x0, 5
+    ; CHECK-NEXT: SW killed renamable $x11, $x12, 8 :: (volatile store 4 into `i32* inttoptr (i32 305421704 to i32*)`)
+    ; CHECK-NEXT: renamable $x11 = ADDI $x0, 7
+    ; CHECK-NEXT: SW killed renamable $x11, killed $x12, 12 :: (volatile store 4 into `i32* inttoptr (i32 305421708 to i32*)`)
+    renamable $x10 = LUI 74566
+    renamable $x11 = ADDI $x0, 1
+    SW killed renamable $x11, renamable $x10, -640 :: (volatile store 4 into `i32* inttoptr (i32 305421696 to i32*)`)
+    renamable $x11 = ADDI $x0, 3
+    SW killed renamable $x11, renamable $x10, -636 :: (volatile store 4 into `i32* inttoptr (i32 305421700 to i32*)`)
+    renamable $x11 = ADDI $x0, 5
+    SW killed renamable $x11, renamable $x10, -632 :: (volatile store 4 into `i32* inttoptr (i32 305421704 to i32*)`)
+    renamable $x11 = ADDI $x0, 7
+    SW killed renamable $x11, killed renamable $x10, -628 :: (volatile store 4 into `i32* inttoptr (i32 305421708 to i32*)`)
+    PseudoRET
+
+...
+---
+name:            load_large_offset
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+    ; CHECK-LABEL: name: load_large_offset
+    ; CHECK: renamable $x10 = LUI 74566
+    ; CHECK-NEXT: $x12 = ADDI $x10, -640
+    ; CHECK-NEXT: dead renamable $x11 = LW $x12, 0 :: (volatile load 4 from `i32* inttoptr (i32 305421696 to i32*)`)
+    ; CHECK-NEXT: dead renamable $x11 = LW $x12, 4 :: (volatile load 4 from `i32* inttoptr (i32 305421700 to i32*)`)
+    ; CHECK-NEXT: dead renamable $x11 = LW $x12, 8 :: (volatile load 4 from `i32* inttoptr (i32 305421704 to i32*)`)
+    ; CHECK-NEXT: dead renamable $x10 = LW killed $x12, 12 :: (volatile load 4 from `i32* inttoptr (i32 305421708 to i32*)`)
+    renamable $x10 = LUI 74566
+    dead renamable $x11 = LW renamable $x10, -640 :: (volatile load 4 from `i32* inttoptr (i32 305421696 to i32*)`)
+    dead renamable $x11 = LW renamable $x10, -636 :: (volatile load 4 from `i32* inttoptr (i32 305421700 to i32*)`)
+    dead renamable $x11 = LW renamable $x10, -632 :: (volatile load 4 from `i32* inttoptr (i32 305421704 to i32*)`)
+    dead renamable $x10 = LW killed renamable $x10, -628 :: (volatile load 4 from `i32* inttoptr (i32 305421708 to i32*)`)
+    PseudoRET
+
+...
+---
+name:            store_common_value_no_opt
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+    liveins: $x10
+    ; CHECK-LABEL: name: store_common_value_no_opt
+    ; CHECK: SW $x0, killed renamable $x10, 0 :: (store 4 into %ir.a)
+    SW $x0, killed renamable $x10, 0 :: (store 4 into %ir.a)
+    PseudoRET
+
+...
+---
+name:            store_common_ptr_no_opt
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+    ; CHECK-LABEL: name: store_common_ptr_no_opt
+    ; CHECK: renamable $x10 = ADDI $x0, 1
+    ; CHECK-NEXT: SW killed renamable $x10, $x0, 0 :: (volatile store 4 into `i32* null`)
+    renamable $x10 = ADDI $x0, 1
+    SW killed renamable $x10, $x0, 0 :: (volatile store 4 into `i32* null`)
+    PseudoRET
+
+...
+---
+name:            load_common_ptr_no_opt
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+    ; CHECK-LABEL: name: load_common_ptr_no_opt
+    ; CHECK: dead renamable $x10 = LW $x0, 0 :: (volatile load 4 from `i32* null`)
+    dead renamable $x10 = LW $x0, 0 :: (volatile load 4 from `i32* null`)
+    PseudoRET
+
+...
+---
+name:            store_large_offset_no_opt
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+    ; CHECK-LABEL: name: store_large_offset_no_opt
+    ; CHECK: renamable $x10 = LUI 74566
+    ; CHECK-NEXT: renamable $x11 = ADDI $x0, 1
+    ; CHECK-NEXT: SW killed renamable $x11, renamable $x10, -640 :: (volatile store 4 into `i32* inttoptr (i32 305421696 to i32*)`)
+    ; CHECK-NEXT: renamable $x11 = ADDI $x0, 3
+    ; CHECK-NEXT: SW killed renamable $x11, killed renamable $x10, -636 :: (volatile store 4 into `i32* inttoptr (i32 305421700 to i32*)`)
+    renamable $x10 = LUI 74566
+    renamable $x11 = ADDI $x0, 1
+    SW killed renamable $x11, renamable $x10, -640 :: (volatile store 4 into `i32* inttoptr (i32 305421696 to i32*)`)
+    renamable $x11 = ADDI $x0, 3
+    SW killed renamable $x11, killed renamable $x10, -636 :: (volatile store 4 into `i32* inttoptr (i32 305421700 to i32*)`)
+    PseudoRET
+
+...
+---
+name:            load_large_offset_no_opt
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+    ; CHECK-LABEL: name: load_large_offset_no_opt
+    ; CHECK: renamable $x10 = LUI 74566
+    ; CHECK-NEXT: dead renamable $x11 = LW renamable $x10, -640 :: (volatile load 4 from `i32* inttoptr (i32 305421696 to i32*)`)
+    ; CHECK-NEXT: dead renamable $x10 = LW killed renamable $x10, -636 :: (volatile load 4 from `i32* inttoptr (i32 305421700 to i32*)`)
+    renamable $x10 = LUI 74566
+    dead renamable $x11 = LW renamable $x10, -640 :: (volatile load 4 from `i32* inttoptr (i32 305421696 to i32*)`)
+    dead renamable $x10 = LW killed renamable $x10, -636 :: (volatile load 4 from `i32* inttoptr (i32 305421700 to i32*)`)
+    PseudoRET
+
+...