[RISCV] Introduce the RISCVMatInt::generateInstSeq helper

[asb]

Summary

Logic to load 32-bit and 64-bit immediates is currently present in
RISCVAsmParser::emitLoadImm in order to support the li pseudoinstruction. With
the introduction of RV64 codegen, there is a greater benefit of sharing
immediate materialisation logic between the MC layer and codegen. The
generateInstSeq helper allows this by producing a vector of simple structs
representing the chosen instructions. This can then be consumed in the MC
layer to produce MCInsts or at instruction selection time to produce
appropriate SelectionDAG node. Sharing this logic means that both the li
pseudoinstruction and codegen can benefit from future optimisations, and
that this logic can be used for materialising constants during RV64 codegen.

This patch does contain a behaviour change: addi will now be produced on RV64
when no lui is necessary to materialise the constant. In that case addiw takes
x0 as the source register, so is semantically identical to addi.

[sabuasal]

The helper makes it clear to follow. Thanks!

I am just not sure why you did the change to prefer add to addiw when for 64bit? is addi faster than addiw?

[asb]

In D52961#1258446, @sabuasal wrote:

The helper makes it clear to follow. Thanks!

I am just not sure why you did the change to prefer add to addiw when for 64bit? is addi faster than addiw?

No real reason to prefer one or the other when they're semantically identical. It's mostly to be closer to gas/gcc which uses addi at least for the isInt<12> case.

[lewis-revill]

It is a bit off topic for this patch but considering the range between best & worst case materialization is it worth adding an implementation of TargetTransformInfo::getIntImmCost for RISC-V? Or maybe adding a TargetTransformInfo implementation would be better as one larger patch, once codegen behaviour is relatively stable.

[asb]

I'm trying to keep things separate where possible, but yes we will want getIntImmCost and as you point out it's likely to be more useful for RV64. Ideally it would recognise that compressible code sequences are cheaper than non-compressible sequences.

[sabuasal]

In D52961#1258464, @asb wrote:

In D52961#1258446, @sabuasal wrote:

The helper makes it clear to follow. Thanks!

I am just not sure why you did the change to prefer add to addiw when for 64bit? is addi faster than addiw?

No real reason to prefer one or the other when they're semantically identical. It's mostly to be closer to gas/gcc which uses addi at least for the isInt<12> case.

I see. makes sense. I just checked gcc and it seems to be favoring addi for that case.

[asb]

The other motivation is that many of our codegen tests are going to include both RV32 and RV64 check lines. It's distracting to see addiw for materialising constants when it's not necessary, and it represents an unnecessary diff vs the equivalent RV32 code.

This patch still applies cleanly against HEAD.

@niosHD, did you have any thoughts about this approach?

[niosHD]

For me the patch looks good, thank you for working on it Alex!

I like using ADDI instead of ADDIW when possible to get more consistent codegen output. However, the comment should be updated to reflect this change.

lib/Target/RISCV/Utils/RISCVMatInt.cpp

26

The comment should be updated to reflect that we now always emit ADDI in the first two cases.

[asb]

Fixed out of date comment (thanks @niosHD).

[asb]

In D52961#1261196, @sabuasal wrote:

In D52961#1258464, @asb wrote:

No real reason to prefer one or the other when they're semantically identical. It's mostly to be closer to gas/gcc which uses addi at least for the isInt<12> case.

I see. makes sense. I just checked gcc and it seems to be favoring addi for that case.

Does this look good to you then?

[sabuasal]

In D52961#1265204, @asb wrote:

In D52961#1261196, @sabuasal wrote:

In D52961#1258464, @asb wrote:

No real reason to prefer one or the other when they're semantically identical. It's mostly to be closer to gas/gcc which uses addi at least for the isInt<12> case.

I see. makes sense. I just checked gcc and it seems to be favoring addi for that case.

Does this look good to you then?

Yes, no more comments on my side.

[lewis-revill]

lib/Target/RISCV/Utils/RISCVMatInt.cpp

67

I noticed MathExtras.h has a function isMask_64, which essentially tells you whether a value is a non-zero set of 1s from the least significant bit up to a high bit. From this it's quite simple to implement the ADDI -1 + SRLI as described in D52962. Inserting the following code at this point would mean that the sequence it replaces will be at least 3 instructions as Val > 32 bits and Lo12 would be full of 1s:

// Find the special case of the value being a mask containing all ones from
// bit position 0 up to bit position N. In other words, a right shift of the
// constant -1. Uses only two instructions, ADDI+SRLI.
if (isMask_64((uint64_t)Val)) {
  Res.push_back(Inst(RISCV::ADDI, -1));

  int ShiftAmount = findLastSet((uint64_t)Val);
  Res.push_back(Inst(RISCV::SRLI, ShiftAmount));

  return;
}

[asb]

lib/Target/RISCV/Utils/RISCVMatInt.cpp

67

I agree it's easy to add, but I wanted to perform this refactoring as a no-op with improvements going in further patches.

Plus handling this case is one of the tasks I walk people through in my RISC-V LLVM Coding Lab this afternoon :)

lib/Target/RISCV/AsmParser/RISCVAsmParser.cpp

 //===-- RISCVAsmParser.cpp - Parse RISCV assembly to MCInst instructions --===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "MCTargetDesc/RISCVMCExpr.h"
 #include "MCTargetDesc/RISCVMCTargetDesc.h"
 #include "MCTargetDesc/RISCVTargetStreamer.h"
 #include "Utils/RISCVBaseInfo.h"
+#include "Utils/RISCVMatInt.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/MC/MCContext.h"
 #include "llvm/MC/MCExpr.h"
 #include "llvm/MC/MCInst.h"
 #include "llvm/MC/MCInstBuilder.h"
 #include "llvm/MC/MCParser/MCAsmLexer.h"
 #include "llvm/MC/MCParser/MCParsedAsmOperand.h"
void RISCVAsmParser::emitToStreamer(MCStreamer &S, const MCInst &Inst) {
   MCInst CInst;
   bool Res = compressInst(CInst, Inst, getSTI(), S.getContext());
   CInst.setLoc(Inst.getLoc());
   S.EmitInstruction((Res ? CInst : Inst), getSTI());
 }
 
 void RISCVAsmParser::emitLoadImm(unsigned DestReg, int64_t Value,
                                  MCStreamer &Out) {
-  if (isInt<32>(Value)) {
-    // Emits the MC instructions for loading a 32-bit constant into a register.
-    //
-    // Depending on the active bits in the immediate Value v, the following
-    // instruction sequences are emitted:
-    //
-    // v == 0                        : ADDI(W)
-    // v[0,12) != 0 && v[12,32) == 0 : ADDI(W)
-    // v[0,12) == 0 && v[12,32) != 0 : LUI
-    // v[0,32) != 0                  : LUI+ADDI(W)
-    //
-    int64_t Hi20 = ((Value + 0x800) >> 12) & 0xFFFFF;
-    int64_t Lo12 = SignExtend64<12>(Value);
-    unsigned SrcReg = RISCV::X0;
+  RISCVMatInt::InstSeq Seq;
+  RISCVMatInt::generateInstSeq(Value, isRV64(), Seq);
+
+  for (RISCVMatInt::Inst &Inst : Seq) {
+    if (Inst.Opc == RISCV::LUI) {
+      emitToStreamer(
+          Out, MCInstBuilder(RISCV::LUI).addReg(DestReg).addImm(Inst.Imm));
+    } else {
+      emitToStreamer(
+          Out, MCInstBuilder(Inst.Opc).addReg(DestReg).addReg(SrcReg).addImm(
+                   Inst.Imm));
+    }
 
-    if (Hi20) {
-      emitToStreamer(Out,
-                     MCInstBuilder(RISCV::LUI).addReg(DestReg).addImm(Hi20));
-      SrcReg = DestReg;
-    }
-
-    if (Lo12 || Hi20 == 0) {
-      unsigned AddiOpcode =
-          STI->hasFeature(RISCV::Feature64Bit) ? RISCV::ADDIW : RISCV::ADDI;
-      emitToStreamer(Out, MCInstBuilder(AddiOpcode)
-                              .addReg(DestReg)
-                              .addReg(SrcReg)
-                              .addImm(Lo12));
-    }
-    return;
-  }
-  assert(STI->hasFeature(RISCV::Feature64Bit) &&
-         "Target must be 64-bit to support a >32-bit constant");
-
-  // In the worst case, for a full 64-bit constant, a sequence of 8 instructions
-  // (i.e., LUI+ADDIW+SLLI+ADDI+SLLI+ADDI+SLLI+ADDI) has to be emmitted. Note
-  // that the first two instructions (LUI+ADDIW) can contribute up to 32 bits
-  // while the following ADDI instructions contribute up to 12 bits each.
-  //
-  // On the first glance, implementing this seems to be possible by simply
-  // emitting the most significant 32 bits (LUI+ADDIW) followed by as many left
-  // shift (SLLI) and immediate additions (ADDI) as needed. However, due to the
-  // fact that ADDI performs a sign extended addition, doing it like that would
-  // only be possible when at most 11 bits of the ADDI instructions are used.
-  // Using all 12 bits of the ADDI instructions, like done by GAS, actually
-  // requires that the constant is processed starting with the least significant
-  // bit.
-  //
-  // In the following, constants are processed from LSB to MSB but instruction
-  // emission is performed from MSB to LSB by recursively calling
-  // emitLoadImm. In each recursion, first the lowest 12 bits are removed
-  // from the constant and the optimal shift amount, which can be greater than
-  // 12 bits if the constant is sparse, is determined. Then, the shifted
-  // remaining constant is processed recursively and gets emitted as soon as it
-  // fits into 32 bits. The emission of the shifts and additions is subsequently
-  // performed when the recursion returns.
-  //
-  int64_t Lo12 = SignExtend64<12>(Value);
-  int64_t Hi52 = (Value + 0x800) >> 12;
-  int ShiftAmount = 12 + findFirstSet((uint64_t)Hi52);
-  Hi52 = SignExtend64(Hi52 >> (ShiftAmount - 12), 64 - ShiftAmount);
-
-  emitLoadImm(DestReg, Hi52, Out);
-
-  emitToStreamer(Out, MCInstBuilder(RISCV::SLLI)
-                          .addReg(DestReg)
-                          .addReg(DestReg)
-                          .addImm(ShiftAmount));
-
-  if (Lo12)
-    emitToStreamer(Out, MCInstBuilder(RISCV::ADDI)
-                            .addReg(DestReg)
-                            .addReg(DestReg)
-                            .addImm(Lo12));
+    // Only the first instruction has X0 as its source.
 }
 
 void RISCVAsmParser::emitLoadLocalAddress(MCInst &Inst, SMLoc IDLoc,
                                           MCStreamer &Out) {
   // The local load address pseudo-instruction "lla" is used in PC-relative
   // addressing of symbols:
   //   lla rdest, symbol
   // expands to

lib/Target/RISCV/Utils/CMakeLists.txt

 add_llvm_library(LLVMRISCVUtils
   RISCVBaseInfo.cpp
+  RISCVMatInt.cpp
   )

lib/Target/RISCV/Utils/RISCVMatInt.h

+//===- RISCVMatInt.h - Immediate materialisation ---------------*- C++ -*--===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIB_TARGET_RISCV_MATINT_H
+#define LLVM_LIB_TARGET_RISCV_MATINT_H
+
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/MachineValueType.h"
+#include <cstdint>
+
+namespace llvm {
+
+namespace RISCVMatInt {
+struct Inst {
+  unsigned Opc;
+  int64_t Imm;
+
+  Inst(unsigned Opc, int64_t Imm) : Opc(Opc), Imm(Imm) {}
+};
+using InstSeq = SmallVector<Inst, 8>;
+
+// Helper to generate an instruction sequence that will materialise the given
+// immediate value into a register. A sequence of instructions represented by
+// a simple struct produced rather than directly emitting the instructions in
+// order to allow this helper to be used from both the MC layer and during
+// instruction selection.
+void generateInstSeq(int64_t Val, bool IsRV64, InstSeq &Res);
+} // namespace RISCVMatInt
+} // namespace llvm
+#endif

lib/Target/RISCV/Utils/RISCVMatInt.cpp

+//===- RISCVMatInt.cpp - Immediate materialisation -------------*- C++ -*--===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "RISCVMatInt.h"
+#include "MCTargetDesc/RISCVMCTargetDesc.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/MachineValueType.h"
+#include "llvm/Support/MathExtras.h"
+#include <cstdint>
+
+namespace llvm {
+
+namespace RISCVMatInt {
+void generateInstSeq(int64_t Val, bool Is64Bit, InstSeq &Res) {
+  if (isInt<32>(Val)) {
+    // Depending on the active bits in the immediate Value v, the following
+    // instruction sequences are emitted:
+    //
+    // v == 0                        : ADDI(W)
+    // v[0,12) != 0 && v[12,32) == 0 : ADDI(W)
+    // v[0,12) == 0 && v[12,32) != 0 : LUI
+    // v[0,32) != 0                  : LUI+ADDI(W)
+    int64_t Hi20 = ((Val + 0x800) >> 12) & 0xFFFFF;
+    int64_t Lo12 = SignExtend64<12>(Val);
+
+    if (Hi20)
+      Res.push_back(Inst(RISCV::LUI, Hi20));
+
+    if (Lo12 || Hi20 == 0) {
+      unsigned AddiOpc = (Is64Bit && Hi20) ? RISCV::ADDIW : RISCV::ADDI;
+      Res.push_back(Inst(AddiOpc, Lo12));
+    }
+    return;
+  }
+
+  assert(Is64Bit && "Can't emit >32-bit imm for non-RV64 target");
+
+  // In the worst case, for a full 64-bit constant, a sequence of 8 instructions
+  // (i.e., LUI+ADDIW+SLLI+ADDI+SLLI+ADDI+SLLI+ADDI) has to be emmitted. Note
+  // that the first two instructions (LUI+ADDIW) can contribute up to 32 bits
+  // while the following ADDI instructions contribute up to 12 bits each.
+  //
+  // On the first glance, implementing this seems to be possible by simply
+  // emitting the most significant 32 bits (LUI+ADDIW) followed by as many left
+  // shift (SLLI) and immediate additions (ADDI) as needed. However, due to the
+  // fact that ADDI performs a sign extended addition, doing it like that would
+  // only be possible when at most 11 bits of the ADDI instructions are used.
+  // Using all 12 bits of the ADDI instructions, like done by GAS, actually
+  // requires that the constant is processed starting with the least significant
+  // bit.
+  //
+  // In the following, constants are processed from LSB to MSB but instruction
+  // emission is performed from MSB to LSB by recursively calling
+  // generateInstSeq. In each recursion, first the lowest 12 bits are removed
+  // from the constant and the optimal shift amount, which can be greater than
+  // 12 bits if the constant is sparse, is determined. Then, the shifted
+  // remaining constant is processed recursively and gets emitted as soon as it
+  // fits into 32 bits. The emission of the shifts and additions is subsequently
+  // performed when the recursion returns.
+
+  int64_t Lo12 = SignExtend64<12>(Val);
+  int64_t Hi52 = (Val + 0x800) >> 12;
+  int ShiftAmount = 12 + findFirstSet((uint64_t)Hi52);
+  Hi52 = SignExtend64(Hi52 >> (ShiftAmount - 12), 64 - ShiftAmount);
+
+  generateInstSeq(Hi52, Is64Bit, Res);
+
+  Res.push_back(Inst(RISCV::SLLI, ShiftAmount));
+  if (Lo12)
+    Res.push_back(Inst(RISCV::ADDI, Lo12));
+}
+} // namespace RISCVMatInt
+} // namespace llvm

test/MC/RISCV/rv64c-aliases-valid.s

 # RUN: llvm-mc -triple=riscv64 -mattr=+c -riscv-no-aliases < %s \
 # RUN:     | FileCheck -check-prefixes=CHECK-EXPAND,CHECK-INST %s
 # RUN: llvm-mc -filetype=obj -triple riscv64 -mattr=+c < %s \
 # RUN:     | llvm-objdump -d -riscv-no-aliases - \
 # RUN:     | FileCheck -check-prefixes=CHECK-EXPAND,CHECK-INST %s
 
 # The following check prefixes are used in this test:
 # CHECK-INST.....Match the canonical instr (tests alias to instr. mapping)
 # CHECK-EXPAND...Match canonical instr. unconditionally (tests alias expansion)
 
 # CHECK-EXPAND: c.li a0, 0
 li x10, 0
 # CHECK-EXPAND: c.li a0, 1
 li x10, 1
 # CHECK-EXPAND: c.li a0, -1
 li x10, -1
-# CHECK-EXPAND: addiw a0, zero, 2047
+# CHECK-EXPAND: addi a0, zero, 2047
 li x10, 2047
-# CHECK-EXPAND: addiw a0, zero, -2047
+# CHECK-EXPAND: addi a0, zero, -2047
 li x10, -2047
 # CHECK-EXPAND: c.lui a1, 1
 # CHECK-EXPAND: addiw a1, a1, -2048
 li x11, 2048
-# CHECK-EXPAND: addiw a1, zero, -2048
+# CHECK-EXPAND: addi a1, zero, -2048
 li x11, -2048
 # CHECK-EXPAND: c.lui a1, 1
 # CHECK-EXPAND: addiw a1, a1, -2047
 li x11, 2049
 # CHECK-EXPAND: c.lui a1, 1048575
 # CHECK-EXPAND: addiw a1, a1, 2047
 li x11, -2049
 # CHECK-EXPAND: c.lui a1, 1

test/MC/RISCV/rv64i-aliases-valid.s

 # The following check prefixes are used in this test:
 # CHECK-INST.....Match the canonical instr (tests alias to instr. mapping)
 # CHECK-ALIAS....Match the alias (tests instr. to alias mapping)
 # CHECK-EXPAND...Match canonical instr. unconditionally (tests alias expansion)
 
 # TODO ld
 # TODO sd
 
-# CHECK-INST: addiw a0, zero, 0
-# CHECK-ALIAS: sext.w a0, zero
+# CHECK-INST: addi a0, zero, 0
+# CHECK-ALIAS: mv a0, zero
 li x10, 0
-# CHECK-EXPAND: addiw a0, zero, 1
+# CHECK-EXPAND: addi a0, zero, 1
 li x10, 1
-# CHECK-EXPAND: addiw a0, zero, -1
+# CHECK-EXPAND: addi a0, zero, -1
 li x10, -1
-# CHECK-EXPAND: addiw a0, zero, 2047
+# CHECK-EXPAND: addi a0, zero, 2047
 li x10, 2047
-# CHECK-EXPAND: addiw a0, zero, -2047
+# CHECK-EXPAND: addi a0, zero, -2047
 li x10, -2047
 # CHECK-EXPAND: lui a1, 1
 # CHECK-EXPAND: addiw a1, a1, -2048
 li x11, 2048
-# CHECK-EXPAND: addiw a1, zero, -2048
+# CHECK-EXPAND: addi a1, zero, -2048
 li x11, -2048
 # CHECK-EXPAND: lui a1, 1
 # CHECK-EXPAND: addiw a1, a1, -2047
 li x11, 2049
 # CHECK-EXPAND: lui a1, 1048575
 # CHECK-EXPAND: addiw a1, a1, 2047
 li x11, -2049
 # CHECK-EXPAND: lui a1, 1

 # CHECK-EXPAND: lui a2, 524288
 # CHECK-EXPAND: addiw a2, a2, 1
 li x12, -2147483647
 # CHECK-EXPAND: lui a2, 524288
 li x12, -2147483648
 # CHECK-EXPAND: lui a2, 524288
 li x12, -0x80000000
 
-# CHECK-EXPAND: addiw a2, zero, 1
+# CHECK-EXPAND: addi a2, zero, 1
 # CHECK-EXPAND: slli a2, a2, 31
 li x12, 0x80000000
-# CHECK-EXPAND: addiw a2, zero, 1
+# CHECK-EXPAND: addi a2, zero, 1
 # CHECK-EXPAND: slli a2, a2, 32
 # CHECK-EXPAND: addi a2, a2, -1
 li x12, 0xFFFFFFFF
 
-# CHECK-EXPAND: addiw t0, zero, 1
+# CHECK-EXPAND: addi t0, zero, 1
 # CHECK-EXPAND: slli t0, t0, 32
 li t0, 0x100000000
-# CHECK-EXPAND: addiw t1, zero, -1
+# CHECK-EXPAND: addi t1, zero, -1
 # CHECK-EXPAND: slli t1, t1, 63
 li t1, 0x8000000000000000
-# CHECK-EXPAND: addiw t1, zero, -1
+# CHECK-EXPAND: addi t1, zero, -1
 # CHECK-EXPAND: slli t1, t1, 63
 li t1, -0x8000000000000000
 # CHECK-EXPAND: lui t2, 9321
 # CHECK-EXPAND: addiw t2, t2, -1329
 # CHECK-EXPAND: slli t2, t2, 35
 li t2, 0x1234567800000000
-# CHECK-EXPAND: addiw t3, zero, 7
+# CHECK-EXPAND: addi t3, zero, 7
 # CHECK-EXPAND: slli t3, t3, 36
 # CHECK-EXPAND: addi t3, t3, 11
 # CHECK-EXPAND: slli t3, t3, 24
 # CHECK-EXPAND: addi t3, t3, 15
 li t3, 0x700000000B00000F
 # CHECK-EXPAND: lui t4, 583
 # CHECK-EXPAND: addiw t4, t4, -1875
 # CHECK-EXPAND: slli t4, t4, 14
 # CHECK-EXPAND: addi t4, t4, -947
 # CHECK-EXPAND: slli t4, t4, 12
 # CHECK-EXPAND: addi t4, t4, 1511
 # CHECK-EXPAND: slli t4, t4, 13
 # CHECK-EXPAND: addi t4, t4, -272
 li t4, 0x123456789abcdef0
-# CHECK-EXPAND: addiw t5, zero, -1
+# CHECK-EXPAND: addi t5, zero, -1
 li t5, 0xFFFFFFFFFFFFFFFF
 
 # CHECK-INST: subw t6, zero, ra
 # CHECK-ALIAS: negw t6, ra
 negw x31, x1
 # CHECK-INST: addiw t6, ra, 0
 # CHECK-ALIAS: sext.w t6, ra
 sext.w x31, x1