[RISCV][GlobalISel] Generate indirect branch selection

13 files changed, 143 insertions, 22 deletions

diff --git a/backend/include/rcc/TableGen/Record.h b/backend/include/rcc/TableGen/Record.h
index 17b0e46..449cb92 100644
--- a/backend/include/rcc/TableGen/Record.h
+++ b/backend/include/rcc/TableGen/Record.h
@@ -71,6 +71,7 @@ struct SourceRegisterClass final {
   std::uint64_t Lanes = 0;
   std::vector<std::string> RegisterSymbols;
   std::vector<std::string> AllocationOrderSymbols;
+  std::vector<std::string> SuperClassSymbols;
   bool Allocatable = true;
   std::uint32_t CopyCost = 1;
   TextRange Range;
diff --git a/backend/lib/TableGen/Parser.cpp b/backend/lib/TableGen/Parser.cpp
index 1a2af30..248e831 100644
--- a/backend/lib/TableGen/Parser.cpp
+++ b/backend/lib/TableGen/Parser.cpp
@@ -477,7 +477,7 @@ private:
       if (!checkKeys(*Element,
                      {"id", "symbol", "name", "bank", "size_bits", "spill_size_bits",
                       "spill_alignment_bits", "lanes", "registers", "allocation_order",
-                      "allocatable", "copy_cost"},
+                      "superclasses", "allocatable", "copy_cost"},
                      "register class")) {
         return false;
       }
@@ -522,8 +522,15 @@ private:
           .Lanes = *Lanes,
           .RegisterSymbols = *Registers,
           .AllocationOrderSymbols = *AllocationOrder,
+          .SuperClassSymbols = {},
           .Range = Element->range(),
       };
+      if (const yaml::Node *SuperClasses = optionalNode(*Element, "superclasses")) {
+        const auto Values = scalarSequence(*SuperClasses, "register class superclasses");
+        if (!Values)
+          return false;
+        RegisterClass.SuperClassSymbols = *Values;
+      }
       if (const yaml::Node *Allocatable = optionalNode(*Element, "allocatable")) {
         const auto Value = boolean(*Allocatable, "register class allocatable");
         if (!Value)
diff --git a/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp b/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp
index 1e2eb92..ce6400e 100644
--- a/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp
+++ b/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp
@@ -478,8 +478,6 @@ public:
       return selectAtomicRMW(Instruction, Function, Target, Type, Generic);
     case GenericOpcode::G_FENCE:
       return selectFence(Instruction);
-    case GenericOpcode::G_BRINDIRECT:
-      return selectIndirectBranch(Instruction);
     case GenericOpcode::G_TRAP:
     case GenericOpcode::G_DEBUGTRAP:
     case GenericOpcode::G_UBSANTRAP:
@@ -1198,19 +1196,6 @@ private:
     return Instruction.setOpcode(instructionOpcode(InstructionOpcode::FENCE));
   }
 
-  [[nodiscard]] Expected<void> selectIndirectBranch(MachineInstr &Instruction) const {
-    auto Zero = physicalRegister(PhysicalRegisterID::X0);
-    if (!Zero)
-      return std::unexpected(Zero.error());
-    auto Inserted = insertPhysicalRegister(Instruction, 0, *Zero, RegisterOperandFlag::Define);
-    if (!Inserted)
-      return std::unexpected(Inserted.error());
-    auto Immediate = appendImmediate(Instruction, 0);
-    if (!Immediate)
-      return std::unexpected(Immediate.error());
-    return Instruction.setOpcode(instructionOpcode(InstructionOpcode::JALR));
-  }
-
   [[nodiscard]] Expected<void> selectTrap(MachineInstr &Instruction) const {
     while (Instruction.operandCount() != 0) {
       auto Erased = Instruction.eraseOperand(Instruction.operandCount() - 1U);
diff --git a/backend/lib/Target/RISCV/RISCVGISelControlFlow.rccdesc b/backend/lib/Target/RISCV/RISCVGISelControlFlow.rccdesc
index c58135f..21fd338 100644
--- a/backend/lib/Target/RISCV/RISCVGISelControlFlow.rccdesc
+++ b/backend/lib/Target/RISCV/RISCVGISelControlFlow.rccdesc
@@ -2,6 +2,18 @@
 
 selection_rules:
   -
+    id: select_g_brindirect
+    priority: 100
+    match:
+      opcode: G_BRINDIRECT
+    apply:
+      instructions:
+        - opcode: PseudoBRIND
+          root: true
+          operands:
+            - { operand: 0 }
+            - { immediate: 0 }
+  -
     id: select_g_br
     priority: 100
     match:
diff --git a/backend/lib/Target/RISCV/RISCVInstrInfoPseudo.rccdesc b/backend/lib/Target/RISCV/RISCVInstrInfoPseudo.rccdesc
index 4f16ec6..be57f89 100644
--- a/backend/lib/Target/RISCV/RISCVInstrInfoPseudo.rccdesc
+++ b/backend/lib/Target/RISCV/RISCVInstrInfoPseudo.rccdesc
@@ -378,3 +378,15 @@ instructions:
     size: 4
     owner: post_ra_expansion
     deadline: post_ra_finalized
+  -
+    id: 1263
+    symbol: PseudoBRIND
+    name: PseudoBRIND
+    operands:
+      - { kinds: [register], role: use, register_class: GPRJALRNonX7, register_bank: GPR, name: RS1 }
+      - { kinds: [immediate], immediate_predicate: SIMM12, name: IMM }
+    num_explicit_defs: 0
+    flags: [pseudo, produces_code, allowed_pre_legalizer, terminator, branch, indirect_branch, barrier]
+    size: 4
+    owner: post_ra_expansion
+    deadline: post_ra_finalized
diff --git a/backend/lib/Target/RISCV/RISCVPseudoExpansion.cpp b/backend/lib/Target/RISCV/RISCVPseudoExpansion.cpp
index b9cdb48..df3e5ad 100644
--- a/backend/lib/Target/RISCV/RISCVPseudoExpansion.cpp
+++ b/backend/lib/Target/RISCV/RISCVPseudoExpansion.cpp
@@ -544,6 +544,51 @@ copyRegisters(const MachineInstr &Instruction) {
   return true;
 }
 
+[[nodiscard]] Expected<bool> expandIndirectBranch(MachineInstr &Instruction,
+                                                  MachineFunction &Function,
+                                                  const TargetDescription &Target) {
+  const MachineOperand *Address = Instruction.operandAt(0);
+  const MachineOperand *Offset = Instruction.operandAt(1);
+  if (Address == nullptr || Address->getIf<Register>() == nullptr || Offset == nullptr ||
+      Offset->getIf<std::int64_t>() == nullptr) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "RISC-V PseudoBRIND has malformed operands");
+  }
+
+  auto Zero = physicalRegister(PhysicalRegisterID::X0);
+  if (!Zero)
+    return std::unexpected(Zero.error());
+  MachineIRBuilder Builder(Function, Target);
+  auto Point = Builder.setInsertPointBefore(Instruction);
+  if (!Point)
+    return std::unexpected(Point.error());
+  auto Pending = Builder.buildInstr(instructionOpcode(InstructionOpcode::JALR));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  auto Added = Pending->addDef(Register::fromPhysical(*Zero));
+  if (!Added)
+    return std::unexpected(Added.error());
+  Added = Pending->addOperand(Address->cloneDetached());
+  if (!Added)
+    return std::unexpected(Added.error());
+  Added = Pending->addOperand(Offset->cloneDetached());
+  if (!Added)
+    return std::unexpected(Added.error());
+  auto Implicit = copyExtraImplicitOperands(Instruction, 2, *Pending, std::nullopt, std::nullopt);
+  if (!Implicit)
+    return std::unexpected(Implicit.error());
+  auto Replacement = Pending->build();
+  if (!Replacement)
+    return std::unexpected(Replacement.error());
+  auto Decoration = copyCommonDecoration(Instruction, **Replacement, true, true, true);
+  if (!Decoration)
+    return std::unexpected(Decoration.error());
+  auto Removed = removeOldInstruction(Instruction);
+  if (!Removed)
+    return std::unexpected(Removed.error());
+  return true;
+}
+
 class RISCVPseudoExpansionInfo final : public TargetPseudoExpansionInfo {
 public:
   [[nodiscard]] Expected<bool> preparePostRAPseudo(MachineInstr &Instruction,
@@ -571,6 +616,8 @@ public:
       return expandReturn(Instruction, Function, Target);
     if (Instruction.opcode() == instructionOpcode(InstructionOpcode::PseudoBR))
       return expandBranch(Instruction, Function, Target);
+    if (Instruction.opcode() == instructionOpcode(InstructionOpcode::PseudoBRIND))
+      return expandIndirectBranch(Instruction, Function, Target);
     if (Instruction.opcode() == instructionOpcode(InstructionOpcode::ReadFFLAGS))
       return expandFFLAGSAccess(Instruction, Function, Target, true);
     if (Instruction.opcode() == instructionOpcode(InstructionOpcode::WriteFFLAGS))
diff --git a/backend/lib/Target/RISCV/RISCVRegisterAllocation.cpp b/backend/lib/Target/RISCV/RISCVRegisterAllocation.cpp
index e24c199..99c261c 100644
--- a/backend/lib/Target/RISCV/RISCVRegisterAllocation.cpp
+++ b/backend/lib/Target/RISCV/RISCVRegisterAllocation.cpp
@@ -36,7 +36,8 @@ struct SpillForm final {
   if (Class == registerClassID(RegisterClass::GPR) ||
       Class == registerClassID(RegisterClass::GPRC) ||
       Class == registerClassID(RegisterClass::GPR_NX0) ||
-      Class == registerClassID(RegisterClass::GPR_NX0_NX2)) {
+      Class == registerClassID(RegisterClass::GPR_NX0_NX2) ||
+      Class == registerClassID(RegisterClass::GPRJALRNonX7)) {
     return SpillForm{InstructionOpcode::LD, InstructionOpcode::SD, 8};
   }
   if (Class == registerClassID(RegisterClass::FPR64) ||
diff --git a/backend/lib/Target/RISCV/RISCVRegisterInfo.rccdesc b/backend/lib/Target/RISCV/RISCVRegisterInfo.rccdesc
index 7a63dc0..0a95adb 100644
--- a/backend/lib/Target/RISCV/RISCVRegisterInfo.rccdesc
+++ b/backend/lib/Target/RISCV/RISCVRegisterInfo.rccdesc
@@ -253,6 +253,7 @@ register_classes:
     symbol: GPRC
     name: GPRC
     bank: GPR
+    superclasses: [GPR]
     size_bits: 64
     spill_size_bits: 64
     spill_alignment_bits: 64
@@ -275,6 +276,7 @@ register_classes:
     symbol: FPR64C
     name: FPR64C
     bank: FPR
+    superclasses: [FPR64]
     size_bits: 64
     spill_size_bits: 64
     spill_alignment_bits: 64
@@ -297,6 +299,7 @@ register_classes:
     symbol: FPR32C
     name: FPR32C
     bank: FPR
+    superclasses: [FPR32]
     size_bits: 32
     spill_size_bits: 32
     spill_alignment_bits: 32
@@ -308,6 +311,7 @@ register_classes:
     symbol: GPR_NX0
     name: GPR_NX0
     bank: GPR
+    superclasses: [GPR]
     size_bits: 64
     spill_size_bits: 64
     spill_alignment_bits: 64
@@ -319,6 +323,7 @@ register_classes:
     symbol: GPR_NX0_NX2
     name: GPR_NX0_NX2
     bank: GPR
+    superclasses: [GPR_NX0]
     size_bits: 64
     spill_size_bits: 64
     spill_alignment_bits: 64
@@ -361,6 +366,18 @@ register_classes:
     registers: [V0, V1, V2, V3, V4, V5, V6, V7, V8, V9, V10, V11, V12, V13, V14, V15, V16, V17, V18, V19, V20, V21, V22, V23, V24, V25, V26, V27, V28, V29, V30, V31]
     allocation_order: []
     allocatable: false
+  -
+    id: 12
+    symbol: GPRJALRNonX7
+    name: GPRJALRNonX7
+    bank: GPR
+    superclasses: [GPR]
+    size_bits: 64
+    spill_size_bits: 64
+    spill_alignment_bits: 64
+    lanes: 1
+    registers: [X6, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, X23, X24, X25, X26, X27, X28, X29, X30, X31]
+    allocation_order: [X6, X28, X29, X30, X31, X10, X11, X12, X13, X14, X15, X16, X17, X8, X9, X18, X19, X20, X21, X22, X23, X24, X25, X26, X27]
 
 register_masks:
   -
diff --git a/backend/lib/Target/RISCV/RISCVScheduling.cpp b/backend/lib/Target/RISCV/RISCVScheduling.cpp
index 90b6620..a58b913 100644
--- a/backend/lib/Target/RISCV/RISCVScheduling.cpp
+++ b/backend/lib/Target/RISCV/RISCVScheduling.cpp
@@ -112,7 +112,8 @@ enum class PressureSet : std::uint32_t {
       {pressureSet(PressureSet::GPR),
        "gpr",
        {registerClass(RegisterClass::GPR), registerClass(RegisterClass::GPRC),
-        registerClass(RegisterClass::GPR_NX0), registerClass(RegisterClass::GPR_NX0_NX2)},
+        registerClass(RegisterClass::GPR_NX0), registerClass(RegisterClass::GPR_NX0_NX2),
+        registerClass(RegisterClass::GPRJALRNonX7)},
        27},
       {pressureSet(PressureSet::FPR),
        "fpr",
diff --git a/backend/lib/Target/RISCV/RISCVTarget.cpp b/backend/lib/Target/RISCV/RISCVTarget.cpp
index 0c202a2..4f33ce3 100644
--- a/backend/lib/Target/RISCV/RISCVTarget.cpp
+++ b/backend/lib/Target/RISCV/RISCVTarget.cpp
@@ -43,11 +43,21 @@ physicalRegisters(std::initializer_list<PhysicalRegisterID> IDs) {
   return Result;
 }
 
+[[nodiscard]] std::vector<RegisterClassID>
+registerClasses(std::initializer_list<RegisterClass> IDs) {
+  std::vector<RegisterClassID> Result;
+  Result.reserve(IDs.size());
+  for (const RegisterClass ID : IDs)
+    Result.push_back(RegisterClassID::fromValue(static_cast<std::uint32_t>(ID)));
+  return Result;
+}
+
 [[nodiscard]] RegisterClassDesc registerClass(
     RegisterClass ID, const char *Name, std::initializer_list<PhysicalRegisterID> Registers,
-    std::initializer_list<PhysicalRegisterID> AllocationOrder, RegisterBank Bank,
-    std::uint32_t SizeInBits, std::uint32_t SpillSizeInBits, std::uint32_t SpillAlignmentInBits,
-    std::uint64_t Lanes, bool Allocatable, std::uint32_t CopyCost) {
+    std::initializer_list<PhysicalRegisterID> AllocationOrder,
+    std::initializer_list<RegisterClass> SuperClasses, RegisterBank Bank, std::uint32_t SizeInBits,
+    std::uint32_t SpillSizeInBits, std::uint32_t SpillAlignmentInBits, std::uint64_t Lanes,
+    bool Allocatable, std::uint32_t CopyCost) {
   return {
       .ID = RegisterClassID::fromValue(static_cast<std::uint32_t>(ID)),
       .Name = Name,
@@ -58,7 +68,7 @@ physicalRegisters(std::initializer_list<PhysicalRegisterID> IDs) {
       .SpillAlignmentInBits = SpillAlignmentInBits,
       .Lanes = LaneMask::fromRaw(Lanes),
       .SupportedSubRegs = {},
-      .SuperClasses = {},
+      .SuperClasses = registerClasses(SuperClasses),
       .DefaultBank = RegisterBankID::fromValue(static_cast<std::uint32_t>(Bank)),
       .Allocatable = Allocatable,
       .CopyCost = CopyCost,
diff --git a/backend/utils/TableGen/Common/CodeGenRegisters.cpp b/backend/utils/TableGen/Common/CodeGenRegisters.cpp
index 839196e..9fa8d7c 100644
--- a/backend/utils/TableGen/Common/CodeGenRegisters.cpp
+++ b/backend/utils/TableGen/Common/CodeGenRegisters.cpp
@@ -132,6 +132,9 @@ namespace rcc::targetgen {
       return false;
     }
     ClassBySymbol.emplace(Class.Symbol, Class.ID);
+  }
+  for (const SourceRegisterClass &Class : Input.RegisterClasses) {
+    const auto Bank = BankBySymbol.find(Class.BankSymbol);
     NormalizedRegisterClass Normalized{
         .ID = Class.ID,
         .Symbol = Class.Symbol,
@@ -143,6 +146,7 @@ namespace rcc::targetgen {
         .Lanes = Class.Lanes,
         .Registers = {},
         .AllocationOrder = {},
+        .SuperClasses = {},
         .Allocatable = Class.Allocatable,
         .CopyCost = Class.CopyCost,
     };
@@ -166,6 +170,18 @@ namespace rcc::targetgen {
       }
       Normalized.AllocationOrder.push_back(Register->second);
     }
+    std::unordered_set<std::uint32_t> SuperClasses;
+    for (const std::string &Symbol : Class.SuperClassSymbols) {
+      const auto SuperClass = ClassBySymbol.find(Symbol);
+      if (SuperClass == ClassBySymbol.end() || SuperClass->second == Class.ID ||
+          !SuperClasses.insert(SuperClass->second).second) {
+        fail(Class.Range,
+             "register class superclasses must reference distinct declared classes other than "
+             "the class itself");
+        return false;
+      }
+      Normalized.SuperClasses.push_back(SuperClass->second);
+    }
     if ((Normalized.Allocatable && Normalized.AllocationOrder.empty()) ||
         (!Normalized.Allocatable && !Normalized.AllocationOrder.empty())) {
       fail(Class.Range, "allocatable register classes require an allocation order and "
diff --git a/backend/utils/TableGen/Common/CodeGenTarget.h b/backend/utils/TableGen/Common/CodeGenTarget.h
index 97e1447..9a7c0a2 100644
--- a/backend/utils/TableGen/Common/CodeGenTarget.h
+++ b/backend/utils/TableGen/Common/CodeGenTarget.h
@@ -53,6 +53,7 @@ struct NormalizedRegisterClass final {
   std::uint64_t Lanes = 0;
   std::vector<std::uint32_t> Registers;
   std::vector<std::uint32_t> AllocationOrder;
+  std::vector<std::uint32_t> SuperClasses;
   bool Allocatable = true;
   std::uint32_t CopyCost = 1;
 };
diff --git a/backend/utils/TableGen/RegisterInfoEmitter.cpp b/backend/utils/TableGen/RegisterInfoEmitter.cpp
index a4caa69..0eee15c 100644
--- a/backend/utils/TableGen/RegisterInfoEmitter.cpp
+++ b/backend/utils/TableGen/RegisterInfoEmitter.cpp
@@ -20,6 +20,15 @@ void emitRegisterIDList(std::ostream &Output, const NormalizedTargetModel &Model
     Output << "PhysicalRegisterID::" << findRegister(Model, ID).Symbol << ", ";
 }
 
+void emitRegisterClassIDList(std::ostream &Output, const NormalizedTargetModel &Model,
+                             std::span<const std::uint32_t> IDs) {
+  for (const std::uint32_t ID : IDs) {
+    const auto Position =
+        std::ranges::find(Model.RegisterClasses, ID, &NormalizedRegisterClass::ID);
+    Output << "RegisterClass::" << Position->Symbol << ", ";
+  }
+}
+
 } // namespace
 
 [[nodiscard]] std::string emitRegisterHeader(const NormalizedTargetModel &Model,
@@ -114,6 +123,8 @@ std::string emitRegisterInfo(const NormalizedTargetModel &Model, std::string_vie
     emitRegisterIDList(Output, Model, Class.Registers);
     Output << "}, {";
     emitRegisterIDList(Output, Model, Class.AllocationOrder);
+    Output << "}, {";
+    emitRegisterClassIDList(Output, Model, Class.SuperClasses);
     Output << "}, RegisterBank::" << findRegisterBank(Model, Class.BankID).Symbol << ", "
            << Class.SizeInBits << ", " << Class.SpillSizeInBits << ", "
            << Class.SpillAlignmentInBits << ", " << Class.Lanes << ", "