[RISCV][GlobalISel] Match LLVM constant materialization

5 files changed, 246 insertions, 196 deletions

diff --git a/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp b/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp
index a868b0e..0d68cc3 100644
--- a/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp
+++ b/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp
@@ -1,6 +1,7 @@
 // SPDX-License-Identifier: GPL-3.0-or-later
 
 #include "RISCV.h"
+#include "RISCVImmediateMaterialization.h"
 #include "RISCVRegisterBankInfo.h"
 #include "rcc/CodeGen/GenericOpcodes.h"
 #include "rcc/CodeGen/GlobalISel/InstructionSelector.h"
@@ -96,12 +97,6 @@ operandType(const MachineFunction &Function, const MachineInstr &Instruction, st
   return *Info->get().Bank;
 }
 
-[[nodiscard]] bool fitsSigned(std::int64_t Value, std::uint32_t Bits) noexcept {
-  const std::int64_t Minimum = -(std::int64_t{1} << (Bits - 1U));
-  const std::int64_t Maximum = (std::int64_t{1} << (Bits - 1U)) - 1;
-  return Value >= Minimum && Value <= Maximum;
-}
-
 [[nodiscard]] std::optional<std::uint64_t>
 memoryAccessBytes(const MachineInstr &Instruction) noexcept {
   if (Instruction.memOperands().size() != 1)
@@ -645,6 +640,34 @@ private:
   }
 
   [[nodiscard]] Expected<MachineInstr *>
+  buildImmediateOnlyAfter(MachineIRBuilder &Builder, MachineInstr &Anchor, InstructionOpcode Opcode,
+                          Register Def, std::int64_t Value) const {
+    auto Point = Builder.setInsertPointAfter(Anchor);
+    if (!Point)
+      return std::unexpected(Point.error());
+    auto RegisterConstraints =
+        constrainBuilderRegisters(Builder.function(), Builder.target(), {Def});
+    if (!RegisterConstraints)
+      return std::unexpected(RegisterConstraints.error());
+    auto Pending = Builder.buildInstr(instructionOpcode(Opcode));
+    if (!Pending)
+      return std::unexpected(Pending.error());
+    auto DefResult = Pending->addDef(Def);
+    if (!DefResult)
+      return std::unexpected(DefResult.error());
+    auto ImmediateResult = Pending->addImmediate(Value);
+    if (!ImmediateResult)
+      return std::unexpected(ImmediateResult.error());
+    auto Built = Pending->build();
+    if (!Built)
+      return std::unexpected(Built.error());
+    auto Constraint = constrainSelectedInstruction(**Built, Builder.function(), Builder.target());
+    if (!Constraint)
+      return std::unexpected(Constraint.error());
+    return *Built;
+  }
+
+  [[nodiscard]] Expected<MachineInstr *>
   buildImmediateBefore(MachineIRBuilder &Builder, MachineInstr &Anchor, InstructionOpcode Opcode,
                        Register Def, Register Source, std::int64_t Value) const {
     auto Point = Builder.setInsertPointBefore(Anchor);
@@ -2435,137 +2458,75 @@ private:
     if (!DestinationConstraint)
       return std::unexpected(DestinationConstraint.error());
     const std::int64_t Value = *ImmediateValue;
-    const std::uint32_t ImmediateTargetFlags = ImmediateOperand->targetFlags();
-    const bool IsWord = Type->isCategoryNeutralScalar() && Type->scalarBitWidth() <= 32;
-    const InstructionOpcode AddImmediate =
-        IsWord ? InstructionOpcode::ADDIW : InstructionOpcode::ADDI;
-    const InstructionOpcode ShiftLeftImmediate =
-        IsWord ? InstructionOpcode::SLLIW : InstructionOpcode::SLLI;
-    if (fitsSigned(Value, 12)) {
-      auto Zero = physicalRegister(PhysicalRegisterID::X0);
-      if (!Zero)
-        return std::unexpected(Zero.error());
+    auto Zero = physicalRegister(PhysicalRegisterID::X0);
+    if (!Zero)
+      return std::unexpected(Zero.error());
+    if (Value == 0) {
+      auto EraseImmediate = Instruction.eraseOperand(1);
+      if (!EraseImmediate)
+        return std::unexpected(EraseImmediate.error());
       auto Source = insertPhysicalRegister(Instruction, 1, *Zero, RegisterOperandFlag::Use);
       if (!Source)
         return std::unexpected(Source.error());
-      auto EraseImmediate = Instruction.eraseOperand(2);
-      if (!EraseImmediate)
-        return std::unexpected(EraseImmediate.error());
-      auto NormalizeImmediate =
-          Instruction.insertOperand(2, MachineOperand::immediate(Value, ImmediateTargetFlags));
-      if (!NormalizeImmediate)
-        return std::unexpected(NormalizeImmediate.error());
-      return Instruction.setOpcode(instructionOpcode(AddImmediate));
+      return Instruction.setOpcode(opcode(GenericOpcode::COPY));
     }
 
-    // Recursively decompose the value into signed 12-bit chunks.  The
-    // quotient is computed from an unsigned bit pattern with explicit sign
-    // extension so both INT64_MIN and INT64_MAX remain well-defined.
-    std::uint64_t Remaining = static_cast<std::uint64_t>(Value);
-    std::vector<std::int64_t> Digits;
-    while (!fitsSigned(std::bit_cast<std::int64_t>(Remaining), 12)) {
-      const std::uint64_t LowBits = Remaining & 0xFFFU;
-      std::int64_t Digit = static_cast<std::int64_t>(LowBits);
-      if (Digit >= 0x800)
-        Digit -= 0x1000;
-      Digits.push_back(Digit);
-
-      const std::uint64_t Adjusted = Remaining - static_cast<std::uint64_t>(Digit);
-      std::uint64_t Quotient = Adjusted >> 12U;
-      if ((Remaining & (std::uint64_t{1} << 63U)) != 0)
-        Quotient |= ~std::uint64_t{0} << 52U;
-      Remaining = Quotient;
+    ImmediateMaterializationSequence Sequence =
+        generateRV64IntegerMaterialization(Value, Subtarget.features());
+    if (Sequence.empty()) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "RISC-V integer materialization produced an empty sequence");
+    }
+    Register Current = Destination;
+    if (Sequence.size() != 1) {
+      auto Temporary = createTemporary(Function, *Type, Target);
+      if (!Temporary)
+        return std::unexpected(Temporary.error());
+      Current = *Temporary;
     }
-    const std::int64_t Base = std::bit_cast<std::int64_t>(Remaining);
 
-    auto Temporary = createTemporary(Function, *Type, Target);
-    if (!Temporary)
-      return std::unexpected(Temporary.error());
-    auto *Parent = Instruction.parent();
-    if (Parent == nullptr)
-      return makeUnexpected(ErrorCode::VerificationError,
-                            "RISC-V constant selection received a detached instruction");
-    auto SetOpcode = Instruction.setOpcode(instructionOpcode(AddImmediate));
-    if (!SetOpcode)
-      return std::unexpected(SetOpcode.error());
-    auto SetDestination = Instruction.operandAt(0)->setRegister(*Temporary);
-    if (!SetDestination)
-      return std::unexpected(SetDestination.error());
-    auto EraseImmediate = Instruction.eraseOperand(1);
-    if (!EraseImmediate)
-      return std::unexpected(EraseImmediate.error());
-    auto Zero = physicalRegister(PhysicalRegisterID::X0);
-    if (!Zero)
-      return std::unexpected(Zero.error());
-    auto AddSource = insertPhysicalRegister(Instruction, 1, *Zero, RegisterOperandFlag::Use);
-    if (!AddSource)
-      return std::unexpected(AddSource.error());
-    auto AddBase = appendImmediate(Instruction, Base);
-    if (!AddBase)
-      return std::unexpected(AddBase.error());
+    const auto SelectHead = [&](const ImmediateMaterializationInstruction &Step,
+                                Register Definition) -> Expected<void> {
+      auto SetOpcode = Instruction.setOpcode(instructionOpcode(Step.Opcode));
+      if (!SetOpcode)
+        return std::unexpected(SetOpcode.error());
+      auto SetDestination = Instruction.operandAt(0)->setRegister(Definition);
+      if (!SetDestination)
+        return std::unexpected(SetDestination.error());
+      auto EraseImmediate = Instruction.eraseOperand(1);
+      if (!EraseImmediate)
+        return std::unexpected(EraseImmediate.error());
+      if (Step.OperandKind == ImmediateMaterializationOperandKind::Immediate)
+        return Instruction.addOperand(MachineOperand::immediate(Step.Immediate));
+      auto Source = insertPhysicalRegister(Instruction, 1, *Zero, RegisterOperandFlag::Use);
+      if (!Source)
+        return std::unexpected(Source.error());
+      return Instruction.addOperand(MachineOperand::immediate(Step.Immediate));
+    };
+    auto Head = SelectHead(Sequence.front(), Current);
+    if (!Head)
+      return std::unexpected(Head.error());
 
     MachineIRBuilder Builder(Function, Target);
-    auto InsertPoint = Builder.setInsertPointAfter(Instruction);
-    if (!InsertPoint)
-      return std::unexpected(InsertPoint.error());
-
-    Register Current = *Temporary;
-    for (std::size_t Reverse = Digits.size(); Reverse != 0; --Reverse) {
-      const std::size_t Index = Reverse - 1U;
-      auto ShiftResult = createTemporary(Function, *Type, Target);
-      if (!ShiftResult)
-        return std::unexpected(ShiftResult.error());
-      auto Shift = Builder.buildInstr(instructionOpcode(ShiftLeftImmediate));
-      if (!Shift)
-        return std::unexpected(Shift.error());
-      auto ShiftDef = Shift->addDef(*ShiftResult);
-      if (!ShiftDef)
-        return std::unexpected(ShiftDef.error());
-      auto ShiftUse = Shift->addUse(Current);
-      if (!ShiftUse)
-        return std::unexpected(ShiftUse.error());
-      auto ShiftAmount = Shift->addImmediate(12);
-      if (!ShiftAmount)
-        return std::unexpected(ShiftAmount.error());
-      auto BuiltShift = Shift->build();
-      if (!BuiltShift)
-        return std::unexpected(BuiltShift.error());
-      auto ShiftConstraint = constrainSelectedInstruction(**BuiltShift, Function, Target);
-      if (!ShiftConstraint)
-        return std::unexpected(ShiftConstraint.error());
-
-      const bool IsFinal = Index == 0;
-      Register AddDestination;
-      if (IsFinal) {
-        AddDestination = Destination;
-      } else {
-        auto AddTemporary = createTemporary(Function, *Type, Target);
-        if (!AddTemporary)
-          return std::unexpected(AddTemporary.error());
-        AddDestination = *AddTemporary;
+    MachineInstr *Anchor = &Instruction;
+    for (std::size_t Index = 1; Index < Sequence.size(); ++Index) {
+      const bool IsFinal = Index + 1U == Sequence.size();
+      Register Next = Destination;
+      if (!IsFinal) {
+        auto Temporary = createTemporary(Function, *Type, Target);
+        if (!Temporary)
+          return std::unexpected(Temporary.error());
+        Next = *Temporary;
       }
-      auto Add = Builder.setInsertPointAfter(**BuiltShift);
-      if (!Add)
-        return std::unexpected(Add.error());
-      auto AddInstruction = Builder.buildInstr(instructionOpcode(AddImmediate));
-      if (!AddInstruction)
-        return std::unexpected(AddInstruction.error());
-      auto AddDef = AddInstruction->addDef(AddDestination);
-      if (!AddDef)
-        return std::unexpected(AddDef.error());
-      auto AddUse = AddInstruction->addUse(*ShiftResult);
-      if (!AddUse)
-        return std::unexpected(AddUse.error());
-      auto AddImmediateResult = AddInstruction->addImmediate(Digits[Index]);
-      if (!AddImmediateResult)
-        return std::unexpected(AddImmediateResult.error());
-      auto BuiltAdd = AddInstruction->build();
-      if (!BuiltAdd)
-        return std::unexpected(BuiltAdd.error());
-      auto AddConstraint = constrainSelectedInstruction(**BuiltAdd, Function, Target);
-      if (!AddConstraint)
-        return std::unexpected(AddConstraint.error());
-      Current = AddDestination;
+      const ImmediateMaterializationInstruction &Step = Sequence[Index];
+      Expected<MachineInstr *> Built =
+          Step.OperandKind == ImmediateMaterializationOperandKind::Immediate
+              ? buildImmediateOnlyAfter(Builder, *Anchor, Step.Opcode, Next, Step.Immediate)
+              : buildImmediateAfter(Builder, *Anchor, Step.Opcode, Next, Current, Step.Immediate);
+      if (!Built)
+        return std::unexpected(Built.error());
+      Anchor = *Built;
+      Current = Next;
     }
     return {};
   }
diff --git a/backend/lib/Target/RISCV/GISel/RISCVLegalizerInfo.cpp b/backend/lib/Target/RISCV/GISel/RISCVLegalizerInfo.cpp
index 6e4bb76..5d0be47 100644
--- a/backend/lib/Target/RISCV/GISel/RISCVLegalizerInfo.cpp
+++ b/backend/lib/Target/RISCV/GISel/RISCVLegalizerInfo.cpp
@@ -1261,7 +1261,7 @@ Expected<void> RISCVLegalizerInfo::legalizeCustom(LegalizerHelper &Helper,
     if (Immediate != nullptr && Type && Type->isCategoryNeutralScalar() &&
         Type->scalarBitWidth() == 64) {
       auto Value = signedImmediate(*Immediate);
-      if (Value && shouldUseRV64IntegerConstantPool(*Value)) {
+      if (Value && shouldUseRV64IntegerConstantPool(*Value, Subtarget.features())) {
         Helper.Observer.changingInstr(Instruction);
         auto Lowered = lowerConstantToPool(Instruction, Function, Target);
         if (!Lowered)
diff --git a/backend/lib/Target/RISCV/RISCV.rccdesc b/backend/lib/Target/RISCV/RISCV.rccdesc
index 4896229..832e8c1 100644
--- a/backend/lib/Target/RISCV/RISCV.rccdesc
+++ b/backend/lib/Target/RISCV/RISCV.rccdesc
@@ -446,7 +446,7 @@ named_operands:
 
 immediate_predicates:
   - { id: 1, symbol: SIMM12, name: simm12, kind: signed, bits: 12 }
-  - { id: 2, symbol: SIMM20, name: simm20, kind: signed, bits: 20 }
+  - { id: 2, symbol: UIMM20, name: uimm20, kind: unsigned, bits: 20 }
   - { id: 3, symbol: UIMM5, name: uimm5, kind: unsigned, bits: 5 }
   - { id: 4, symbol: UIMM6, name: uimm6, kind: unsigned, bits: 6 }
   - { id: 5, symbol: UIMM12, name: uimm12, kind: unsigned, bits: 12 }
@@ -538,7 +538,7 @@ instructions:
     encoding: 5175
     operands:
       - { kinds: [register], role: def, register_class: GPR, register_bank: GPR, name: RD }
-      - { kinds: [immediate, constant_pool_index, jump_table_index, global_symbol, external_symbol, block_address, mc_symbol], immediate_predicate: SIMM20, allowed_target_flags: 32, name: IMM }
+      - { kinds: [immediate, constant_pool_index, jump_table_index, global_symbol, external_symbol, block_address, mc_symbol], immediate_predicate: UIMM20, allowed_target_flags: 32, name: IMM }
     num_explicit_defs: 1
     flags: [produces_code, rematerializable]
     scheduling_class: ALU
@@ -552,7 +552,7 @@ instructions:
     encoding: 5143
     operands:
       - { kinds: [register], role: def, register_class: GPR, register_bank: GPR, name: RD }
-      - { kinds: [immediate, basic_block, global_symbol, external_symbol, mc_symbol], immediate_predicate: SIMM20, allowed_target_flags: 3, name: IMM }
+      - { kinds: [immediate, basic_block, global_symbol, external_symbol, mc_symbol], immediate_predicate: UIMM20, allowed_target_flags: 3, name: IMM }
     num_explicit_defs: 1
     flags: [produces_code]
     scheduling_class: ALU
diff --git a/backend/lib/Target/RISCV/RISCVImmediateMaterialization.cpp b/backend/lib/Target/RISCV/RISCVImmediateMaterialization.cpp
index d25a609..a3ed5ac 100644
--- a/backend/lib/Target/RISCV/RISCVImmediateMaterialization.cpp
+++ b/backend/lib/Target/RISCV/RISCVImmediateMaterialization.cpp
@@ -2,12 +2,14 @@
 
 #include "RISCVImmediateMaterialization.h"
 
-#include <algorithm>
+#include "rcc/Target/RISCV/RISCVInstructions.h"
+#include "rcc/Target/RISCV/RISCVSubtarget.h"
+
 #include <bit>
 #include <cstddef>
 #include <cstdint>
-#include <limits>
 #include <optional>
+#include <utility>
 
 namespace rcc::riscv {
 namespace {
@@ -19,6 +21,8 @@ namespace {
 }
 
 [[nodiscard]] constexpr std::int64_t signExtend(std::uint64_t Value, std::uint32_t Bits) noexcept {
+  if (Bits == 64)
+    return std::bit_cast<std::int64_t>(Value);
   const std::uint64_t Mask = (std::uint64_t{1} << Bits) - 1U;
   const std::uint64_t Sign = std::uint64_t{1} << (Bits - 1U);
   Value &= Mask;
@@ -27,57 +31,93 @@ namespace {
   return std::bit_cast<std::int64_t>(Value);
 }
 
-[[nodiscard]] std::size_t baseBuildCost(std::int64_t Value) noexcept {
-  const std::uint64_t Bits = static_cast<std::uint64_t>(Value);
+[[nodiscard]] constexpr std::uint64_t trailingBitMask(std::uint32_t Bits) noexcept {
+  return Bits == 64 ? ~std::uint64_t{0} : (std::uint64_t{1} << Bits) - 1U;
+}
+
+[[nodiscard]] constexpr std::int64_t arithmeticShiftRight(std::uint64_t Value,
+                                                          std::uint32_t Amount) noexcept {
+  return signExtend(Value >> Amount, 64U - Amount);
+}
+
+void appendImmediate(ImmediateMaterializationSequence &Sequence, InstructionOpcode Opcode,
+                     std::int64_t Immediate, ImmediateMaterializationOperandKind OperandKind) {
+  Sequence.push_back({.Opcode = Opcode, .Immediate = Immediate, .OperandKind = OperandKind});
+}
+
+void generateBaseSequence(std::int64_t Value, ImmediateMaterializationSequence &Sequence) {
+  const std::uint64_t Bits = std::bit_cast<std::uint64_t>(Value);
   if (fitsSigned(Value, 32)) {
-    const std::uint64_t High20 = ((Bits + 0x800U) >> 12U) & 0xFFFFFU;
+    const std::int64_t High20 = static_cast<std::int64_t>(((Bits + 0x800U) >> 12U) & 0xFFFFFU);
     const std::int64_t Low12 = signExtend(Bits, 12);
-    return static_cast<std::size_t>(High20 != 0) +
-           static_cast<std::size_t>(Low12 != 0 || High20 == 0);
+    if (High20 != 0) {
+      appendImmediate(Sequence, InstructionOpcode::LUI, High20,
+                      ImmediateMaterializationOperandKind::Immediate);
+    }
+    if (Low12 != 0 || High20 == 0) {
+      InstructionOpcode AddOpcode = InstructionOpcode::ADDI;
+      if (High20 != 0) {
+        const std::int64_t LUIResult = signExtend(static_cast<std::uint64_t>(High20) << 12U, 32);
+        if (!fitsSigned(LUIResult + Low12, 32))
+          AddOpcode = InstructionOpcode::ADDIW;
+      }
+      appendImmediate(Sequence, AddOpcode, Low12,
+                      ImmediateMaterializationOperandKind::RegisterImmediate);
+    }
+    return;
   }
 
   const std::int64_t Low12 = signExtend(Bits, 12);
   const std::uint64_t WithoutLow12 = Bits - static_cast<std::uint64_t>(Low12);
   std::int64_t Remaining = std::bit_cast<std::int64_t>(WithoutLow12);
-  std::uint32_t Shift = 0;
+  std::uint32_t ShiftAmount = 0;
   if (!fitsSigned(Remaining, 32)) {
-    Shift = static_cast<std::uint32_t>(std::countr_zero(WithoutLow12));
-    Remaining >>= Shift;
-
-    if (Shift > 12 && !fitsSigned(Remaining, 12)) {
-      const std::int64_t WithLUILowBits =
-          std::bit_cast<std::int64_t>(static_cast<std::uint64_t>(Remaining) << 12U);
-      if (fitsSigned(WithLUILowBits, 32)) {
-        Shift -= 12;
-        Remaining = WithLUILowBits;
+    ShiftAmount = static_cast<std::uint32_t>(std::countr_zero(WithoutLow12));
+    Remaining = arithmeticShiftRight(WithoutLow12, ShiftAmount);
+    if (ShiftAmount > 12 && !fitsSigned(Remaining, 12)) {
+      const std::int64_t ShiftedRemaining =
+          std::bit_cast<std::int64_t>(std::bit_cast<std::uint64_t>(Remaining) << 12U);
+      if (fitsSigned(ShiftedRemaining, 32)) {
+        ShiftAmount -= 12;
+        Remaining = ShiftedRemaining;
       }
     }
   }
 
-  return baseBuildCost(Remaining) + static_cast<std::size_t>(Shift != 0) +
-         static_cast<std::size_t>(Low12 != 0);
+  generateBaseSequence(Remaining, Sequence);
+  if (ShiftAmount != 0) {
+    appendImmediate(Sequence, InstructionOpcode::SLLI, static_cast<std::int64_t>(ShiftAmount),
+                    ImmediateMaterializationOperandKind::RegisterImmediate);
+  }
+  if (Low12 != 0) {
+    appendImmediate(Sequence, InstructionOpcode::ADDI, Low12,
+                    ImmediateMaterializationOperandKind::RegisterImmediate);
+  }
 }
 
-[[nodiscard]] std::optional<std::size_t> leadingZeroBuildCost(std::uint64_t Value) noexcept {
-  if (Value == 0 || (Value & (std::uint64_t{1} << 63U)) != 0)
-    return std::nullopt;
-
-  const std::uint32_t LeadingZeros = static_cast<std::uint32_t>(std::countl_zero(Value));
-  const std::uint64_t Shifted = Value << LeadingZeros;
-  const std::uint64_t LowMask = (std::uint64_t{1} << LeadingZeros) - 1U;
-  std::optional<std::size_t> Best;
-  for (const std::uint64_t Candidate : {Shifted | LowMask, Shifted}) {
-    const std::size_t Cost = baseBuildCost(std::bit_cast<std::int64_t>(Candidate));
-    if (Cost >= 8)
-      continue;
-    const std::size_t WithShift = Cost + 1U;
-    Best = Best ? std::min(*Best, WithShift) : WithShift;
-  }
-  return Best;
+void considerLeadingZeroSequence(std::int64_t Value, ImmediateMaterializationSequence &Sequence) {
+  const std::uint64_t Bits = std::bit_cast<std::uint64_t>(Value);
+  const std::uint32_t LeadingZeros = static_cast<std::uint32_t>(std::countl_zero(Bits));
+  const std::uint64_t Shifted = Bits << LeadingZeros;
+  const auto Consider = [&](std::uint64_t Candidate) {
+    ImmediateMaterializationSequence Temporary;
+    generateBaseSequence(std::bit_cast<std::int64_t>(Candidate), Temporary);
+    const bool Improves = Temporary.size() + 1U < Sequence.size();
+    const bool InitializesSequence = Sequence.empty() && Temporary.size() < 8;
+    if (!Improves && !InitializesSequence)
+      return;
+    appendImmediate(Temporary, InstructionOpcode::SRLI, static_cast<std::int64_t>(LeadingZeros),
+                    ImmediateMaterializationOperandKind::RegisterImmediate);
+    Sequence = std::move(Temporary);
+  };
+
+  Consider(Shifted | trailingBitMask(LeadingZeros));
+  Consider(Shifted & ~trailingBitMask(LeadingZeros));
 }
 
-[[nodiscard]] std::optional<std::size_t> twoRegisterBuildCost(std::int64_t Value) noexcept {
-  const std::uint64_t Bits = static_cast<std::uint64_t>(Value);
+[[nodiscard]] std::optional<std::size_t>
+twoRegisterBuildCost(std::int64_t Value, const RISCVSubtargetFeatures &Features) {
+  const std::uint64_t Bits = std::bit_cast<std::uint64_t>(Value);
   const std::int64_t Low = signExtend(Bits, 32);
   if (Low == 0)
     return std::nullopt;
@@ -90,49 +130,75 @@ namespace {
   const std::uint32_t HighZeros = static_cast<std::uint32_t>(std::countr_zero(HighContribution));
   if (LowZeros >= 32 || HighZeros < 32 || HighZeros < LowZeros)
     return std::nullopt;
-  const std::uint32_t Shift = HighZeros - LowZeros;
-  if (Shift >= 64 || HighContribution != (static_cast<std::uint64_t>(Low) << Shift))
+  const std::uint32_t ShiftAmount = HighZeros - LowZeros;
+  if (ShiftAmount >= 64 || HighContribution != (static_cast<std::uint64_t>(Low) << ShiftAmount)) {
     return std::nullopt;
-  return estimateRV64IntegerBuildCost(Low) + 2U;
+  }
+  return generateRV64IntegerMaterialization(Low, Features).size() + 2U;
 }
 
 } // namespace
 
-std::size_t estimateRV64IntegerBuildCost(std::int64_t Value) noexcept {
-  const std::uint64_t Bits = static_cast<std::uint64_t>(Value);
-  std::size_t Best = baseBuildCost(Value);
+ImmediateMaterializationSequence
+generateRV64IntegerMaterialization(std::int64_t Value, const RISCVSubtargetFeatures &Features) {
+  ImmediateMaterializationSequence Result;
+  generateBaseSequence(Value, Result);
 
-  if ((Bits & 0xFFFU) != 0 && (Bits & 1U) == 0 && Best >= 2) {
+  const std::uint64_t Bits = std::bit_cast<std::uint64_t>(Value);
+  if ((Bits & 0xFFFU) != 0 && (Bits & 1U) == 0 && Result.size() >= 2) {
     const std::uint32_t TrailingZeros = static_cast<std::uint32_t>(std::countr_zero(Bits));
-    const std::int64_t Shifted = Value >> TrailingZeros;
-    const std::size_t Candidate = baseBuildCost(Shifted) + 1U;
-    if (Candidate < Best || fitsSigned(Shifted, 6))
-      Best = Candidate;
+    const std::int64_t ShiftedValue = arithmeticShiftRight(Bits, TrailingZeros);
+    ImmediateMaterializationSequence Temporary;
+    generateBaseSequence(ShiftedValue, Temporary);
+    const bool PreferCompressibleShift =
+        fitsSigned(ShiftedValue, 6) && !Features.has(RISCVSubtargetOption::FusionLUIAddImmediate);
+    if (Temporary.size() + 1U < Result.size() || PreferCompressibleShift) {
+      appendImmediate(Temporary, InstructionOpcode::SLLI, static_cast<std::int64_t>(TrailingZeros),
+                      ImmediateMaterializationOperandKind::RegisterImmediate);
+      Result = std::move(Temporary);
+    }
   }
-  if (Best <= 2)
-    return Best;
+
+  if (Result.size() <= 2)
+    return Result;
 
   if ((Bits & 0xFFFU) != 0 && (Bits & 0x1800U) == 0x1000U) {
     const std::int64_t LastAdd = -static_cast<std::int64_t>(0x800U - (Bits & 0xFFFU));
-    const std::uint64_t AdjustedBits = Bits - static_cast<std::uint64_t>(LastAdd);
-    Best = std::min(Best, baseBuildCost(std::bit_cast<std::int64_t>(AdjustedBits)) + 1U);
+    const std::int64_t AdjustedValue =
+        std::bit_cast<std::int64_t>(Bits - static_cast<std::uint64_t>(LastAdd));
+    ImmediateMaterializationSequence Temporary;
+    generateBaseSequence(AdjustedValue, Temporary);
+    if (Temporary.size() + 1U < Result.size()) {
+      appendImmediate(Temporary, InstructionOpcode::ADDI, LastAdd,
+                      ImmediateMaterializationOperandKind::RegisterImmediate);
+      Result = std::move(Temporary);
+    }
   }
 
-  if (Value > 0 && Best > 2) {
-    if (const auto Candidate = leadingZeroBuildCost(Bits); Candidate && *Candidate < Best)
-      Best = *Candidate;
-  } else if (Value < 0 && Best > 3) {
-    if (const auto Candidate = leadingZeroBuildCost(~Bits); Candidate && *Candidate + 1U < Best) {
-      Best = *Candidate + 1U;
+  if (Value > 0 && Result.size() > 2) {
+    considerLeadingZeroSequence(Value, Result);
+  } else if (Value < 0 && Result.size() > 3) {
+    ImmediateMaterializationSequence Temporary;
+    considerLeadingZeroSequence(std::bit_cast<std::int64_t>(~Bits), Temporary);
+    if (!Temporary.empty() && Temporary.size() + 1U < Result.size()) {
+      appendImmediate(Temporary, InstructionOpcode::XORI, -1,
+                      ImmediateMaterializationOperandKind::RegisterImmediate);
+      Result = std::move(Temporary);
     }
   }
-  return Best;
+  return Result;
+}
+
+std::size_t estimateRV64IntegerBuildCost(std::int64_t Value,
+                                         const RISCVSubtargetFeatures &Features) {
+  return generateRV64IntegerMaterialization(Value, Features).size();
 }
 
-bool shouldUseRV64IntegerConstantPool(std::int64_t Value, std::size_t MaximumBuildCost) noexcept {
-  if (fitsSigned(Value, 32) || estimateRV64IntegerBuildCost(Value) <= MaximumBuildCost)
+bool shouldUseRV64IntegerConstantPool(std::int64_t Value, const RISCVSubtargetFeatures &Features,
+                                      std::size_t MaximumBuildCost) {
+  if (fitsSigned(Value, 32) || estimateRV64IntegerBuildCost(Value, Features) <= MaximumBuildCost)
     return false;
-  const auto TwoRegisterCost = twoRegisterBuildCost(Value);
+  const auto TwoRegisterCost = twoRegisterBuildCost(Value, Features);
   return !TwoRegisterCost || *TwoRegisterCost > MaximumBuildCost;
 }
 
diff --git a/backend/lib/Target/RISCV/RISCVImmediateMaterialization.h b/backend/lib/Target/RISCV/RISCVImmediateMaterialization.h
index e38f752..4d58ec2 100644
--- a/backend/lib/Target/RISCV/RISCVImmediateMaterialization.h
+++ b/backend/lib/Target/RISCV/RISCVImmediateMaterialization.h
@@ -5,15 +5,38 @@
 
 #include <cstddef>
 #include <cstdint>
+#include <vector>
 
 namespace rcc::riscv {
 
+enum class InstructionOpcode : std::uint32_t;
+class RISCVSubtargetFeatures;
+
+enum class ImmediateMaterializationOperandKind : std::uint8_t {
+  Immediate,
+  RegisterImmediate,
+};
+
+struct ImmediateMaterializationInstruction final {
+  InstructionOpcode Opcode;
+  std::int64_t Immediate = 0;
+  ImmediateMaterializationOperandKind OperandKind =
+      ImmediateMaterializationOperandKind::RegisterImmediate;
+};
+
+using ImmediateMaterializationSequence = std::vector<ImmediateMaterializationInstruction>;
+
 inline constexpr std::size_t DefaultRV64IntegerBuildCost = 5;
 
-[[nodiscard]] std::size_t estimateRV64IntegerBuildCost(std::int64_t Value) noexcept;
+[[nodiscard]] ImmediateMaterializationSequence
+generateRV64IntegerMaterialization(std::int64_t Value, const RISCVSubtargetFeatures &Features);
+
+[[nodiscard]] std::size_t estimateRV64IntegerBuildCost(std::int64_t Value,
+                                                       const RISCVSubtargetFeatures &Features);
 
-[[nodiscard]] bool shouldUseRV64IntegerConstantPool(
-    std::int64_t Value, std::size_t MaximumBuildCost = DefaultRV64IntegerBuildCost) noexcept;
+[[nodiscard]] bool
+shouldUseRV64IntegerConstantPool(std::int64_t Value, const RISCVSubtargetFeatures &Features,
+                                 std::size_t MaximumBuildCost = DefaultRV64IntegerBuildCost);
 
 } // namespace rcc::riscv