1 files changed, 128 insertions, 62 deletions

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;
 }