[CodeGen] Match LLVM Legalizer ownership

5 files changed, 1387 insertions, 130 deletions

diff --git a/backend/lib/CodeGen/GlobalISel/CMakeLists.txt b/backend/lib/CodeGen/GlobalISel/CMakeLists.txt
index 8a37497..b7064e3 100644
--- a/backend/lib/CodeGen/GlobalISel/CMakeLists.txt
+++ b/backend/lib/CodeGen/GlobalISel/CMakeLists.txt
@@ -2,16 +2,24 @@
 
 set(
   RCCBackendGlobalISelSources
+  GISelChangeObserver.cpp
   InstructionSelect.cpp
   Legalizer.cpp
+  LegalizerHelper.cpp
+  LegalizerInfo.cpp
   RegBankSelect.cpp
 )
 
 set(
   RCCBackendGlobalISelHeaders
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GISelChangeObserver.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GISelWorkList.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GenericMachineInstrs.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/InstructionSelect.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/InstructionSelector.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/Legalizer.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/LegalizerHelper.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/LegalizerInfo.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/RegBankSelect.h"
 )
@@ -19,14 +27,20 @@ set(
 target_sources(RCCBackendCodeGen PRIVATE ${RCCBackendGlobalISelSources})
 
 rcc_backend_register_format_files(
+  "${CMAKE_CURRENT_SOURCE_DIR}/GISelChangeObserver.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/InstructionSelect.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/Legalizer.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/LegalizerHelper.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/LegalizerInfo.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegBankSelect.cpp"
   ${RCCBackendGlobalISelHeaders}
 )
 
 rcc_backend_register_tidy_files(
+  "${CMAKE_CURRENT_SOURCE_DIR}/GISelChangeObserver.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/InstructionSelect.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/Legalizer.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/LegalizerHelper.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/LegalizerInfo.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegBankSelect.cpp"
 )
diff --git a/backend/lib/CodeGen/GlobalISel/GISelChangeObserver.cpp b/backend/lib/CodeGen/GlobalISel/GISelChangeObserver.cpp
new file mode 100644
index 0000000..4ce1473
--- /dev/null
+++ b/backend/lib/CodeGen/GlobalISel/GISelChangeObserver.cpp
@@ -0,0 +1,61 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h"
+
+#include <algorithm>
+
+namespace rcc {
+
+void GISelObserverWrapper::addObserver(GISelChangeObserver &Observer) {
+  Observers.push_back(&Observer);
+}
+
+void GISelObserverWrapper::removeObserver(GISelChangeObserver &Observer) {
+  const auto Position = std::ranges::find(Observers, &Observer);
+  if (Position != Observers.end())
+    Observers.erase(Position);
+}
+
+void GISelObserverWrapper::clearObservers() noexcept {
+  Observers.clear();
+}
+
+void GISelObserverWrapper::erasingInstr(MachineInstr &Instruction) {
+  for (GISelChangeObserver *Observer : Observers)
+    Observer->erasingInstr(Instruction);
+}
+
+void GISelObserverWrapper::createdInstr(MachineInstr &Instruction) {
+  for (GISelChangeObserver *Observer : Observers)
+    Observer->createdInstr(Instruction);
+}
+
+void GISelObserverWrapper::changingInstr(MachineInstr &Instruction) {
+  for (GISelChangeObserver *Observer : Observers)
+    Observer->changingInstr(Instruction);
+}
+
+void GISelObserverWrapper::changedInstr(MachineInstr &Instruction) {
+  for (GISelChangeObserver *Observer : Observers)
+    Observer->changedInstr(Instruction);
+}
+
+void GISelObserverWrapper::handleInsertion(MachineInstr &Instruction) {
+  createdInstr(Instruction);
+}
+
+void GISelObserverWrapper::handleRemoval(MachineInstr &Instruction) {
+  erasingInstr(Instruction);
+}
+
+MachineFunctionDelegateInstaller::MachineFunctionDelegateInstaller(
+    MachineFunction &Function, MachineFunction::Delegate &Delegate)
+    : Function(&Function), Delegate(&Delegate) {
+  Function.setDelegate(Delegate);
+}
+
+MachineFunctionDelegateInstaller::~MachineFunctionDelegateInstaller() {
+  Function->resetDelegate(*Delegate);
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/GlobalISel/Legalizer.cpp b/backend/lib/CodeGen/GlobalISel/Legalizer.cpp
index 83efb6a..d971b42 100644
--- a/backend/lib/CodeGen/GlobalISel/Legalizer.cpp
+++ b/backend/lib/CodeGen/GlobalISel/Legalizer.cpp
@@ -2,6 +2,11 @@
 
 #include "rcc/CodeGen/GlobalISel/Legalizer.h"
 
+#include "rcc/CodeGen/GenericOpcodes.h"
+#include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h"
+#include "rcc/CodeGen/GlobalISel/GISelWorkList.h"
+#include "rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
+#include "rcc/CodeGen/GlobalISel/LegalizerHelper.h"
 #include "rcc/CodeGen/LiveVariables.h"
 #include "rcc/CodeGen/MachineBasicBlock.h"
 #include "rcc/CodeGen/MachineFunction.h"
@@ -10,8 +15,10 @@
 #include "rcc/CodeGen/MachineRegisterInfo.h"
 #include "rcc/CodeGen/TargetDescription.h"
 
-#include <cstdint>
+#include <algorithm>
+#include <cstddef>
 #include <optional>
+#include <ranges>
 #include <string>
 #include <unordered_set>
 #include <utility>
@@ -34,60 +41,122 @@ namespace {
   return Contract;
 }
 
-struct OpcodeState final {
-  MachineInstrStableID Instruction;
-  Opcode OpcodeValue;
-  std::uint64_t OperandFingerprint = 0;
+[[nodiscard]] std::vector<MachineInstr *> layoutInstructions(MachineFunction &Function) {
+  std::vector<MachineInstr *> Result;
+  for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next())
+    for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next())
+      Result.push_back(Instruction);
+  return Result;
+}
 
-  friend bool operator==(const OpcodeState &Left, const OpcodeState &Right) noexcept = default;
-};
+[[nodiscard]] bool isArtifact(const MachineInstr &Instruction) noexcept {
+  switch (static_cast<GenericOpcode>(Instruction.opcode().value())) {
+  default:
+    return false;
+  case GenericOpcode::G_TRUNC:
+  case GenericOpcode::G_ZEXT:
+  case GenericOpcode::G_ANYEXT:
+  case GenericOpcode::G_SEXT:
+  case GenericOpcode::G_MERGE_VALUES:
+  case GenericOpcode::G_UNMERGE_VALUES:
+  case GenericOpcode::G_CONCAT_VECTORS:
+  case GenericOpcode::G_BUILD_VECTOR:
+  case GenericOpcode::G_EXTRACT:
+  case GenericOpcode::G_INSERT:
+    return true;
+  }
+}
+
+using InstList = GISelWorkList<256>;
+using ArtifactList = GISelWorkList<128>;
+
+class LegalizerWorkListManager final : public GISelChangeObserver {
+public:
+  LegalizerWorkListManager(InstList &Instructions, ArtifactList &Artifacts)
+      : Instructions(Instructions), Artifacts(Artifacts) {}
 
-struct OpcodeStateHash final {
-  [[nodiscard]] std::size_t operator()(const OpcodeState &State) const noexcept {
-    return std::hash<std::uint64_t>{}(State.Instruction.value()) ^
-           (std::hash<std::uint32_t>{}(State.OpcodeValue.value()) << 1U) ^
-           (std::hash<std::uint64_t>{}(State.OperandFingerprint) << 2U);
+  void erasingInstr(MachineInstr &Instruction) override {
+    Instructions.remove(&Instruction);
+    Artifacts.remove(&Instruction);
   }
-};
 
-void combineFingerprint(std::uint64_t &State, std::uint64_t Value) noexcept {
-  State ^= Value + 0x9e3779b97f4a7c15ULL + (State << 6U) + (State >> 2U);
-}
+  void createdInstr(MachineInstr &Instruction) override {
+    createdOrChangedInstr(Instruction);
+  }
+
+  void changingInstr(MachineInstr &) override {}
 
-[[nodiscard]] std::uint64_t operandFingerprint(const MachineInstr &Instruction) noexcept {
-  std::uint64_t Result = 0xcbf29ce484222325ULL;
-  combineFingerprint(Result, Instruction.flags().rawValue());
-  combineFingerprint(Result, Instruction.operandCount());
-  for (const MachineOperand &Operand : Instruction.operands()) {
-    combineFingerprint(Result, static_cast<std::uint64_t>(Operand.kind()));
-    combineFingerprint(Result, Operand.targetFlags());
-    combineFingerprint(Result, Operand.registerFlags().rawValue());
-    combineFingerprint(Result, Operand.subReg().value());
-    if (const Register *Reg = Operand.getIf<Register>())
-      combineFingerprint(Result, Reg->opaqueValue());
-    else if (const std::int64_t *Immediate = Operand.getIf<std::int64_t>())
-      combineFingerprint(Result, static_cast<std::uint64_t>(*Immediate));
-    else if (const auto *Integer = Operand.getIf<IntegerImmediateOperand>())
-      combineFingerprint(Result, Integer->Value.bitWidth());
-    else if (const auto *Floating = Operand.getIf<FloatingImmediateOperand>())
-      combineFingerprint(Result, static_cast<std::uint64_t>(Floating->Bits.semantics()));
-    else if (const auto *Block = Operand.getIf<BasicBlockOperand>())
-      combineFingerprint(Result, Block->Block == nullptr ? 0 : Block->Block->stableID().value());
+  void changedInstr(MachineInstr &Instruction) override {
+    createdOrChangedInstr(Instruction);
   }
-  return Result;
-}
 
-[[nodiscard]] OpcodeState stateOf(const MachineInstr &Instruction) noexcept {
-  return {Instruction.stableID(), Instruction.opcode(), operandFingerprint(Instruction)};
-}
+private:
+  void createdOrChangedInstr(MachineInstr &Instruction) {
+    if (!isGenericOpcode(Instruction.opcode()))
+      return;
+    if (isArtifact(Instruction))
+      Artifacts.insert(&Instruction);
+    else
+      Instructions.insert(&Instruction);
+  }
 
-[[nodiscard]] std::vector<MachineInstr *> layoutInstructions(MachineFunction &Function) {
-  std::vector<MachineInstr *> Result;
+  InstList &Instructions;
+  ArtifactList &Artifacts;
+};
+
+[[nodiscard]] std::vector<MachineBasicBlock *> reversePostOrderBlocks(MachineFunction &Function) {
+  struct TraversalFrame final {
+    MachineBasicBlock *Block = nullptr;
+    std::vector<MachineBasicBlock *> Successors;
+    std::size_t NextSuccessor = 0;
+  };
+
+  const auto makeFrame = [](MachineBasicBlock &Block) {
+    TraversalFrame Frame;
+    Frame.Block = &Block;
+    for (const MachineSuccessor &Successor : Block.successors()) {
+      if (Successor.Block != nullptr)
+        Frame.Successors.push_back(Successor.Block);
+    }
+    std::ranges::sort(Frame.Successors, {}, [](const MachineBasicBlock *Successor) {
+      return Successor->stableID().value();
+    });
+    return Frame;
+  };
+
+  std::vector<MachineBasicBlock *> Roots;
   for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next())
-    for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
-         Instruction = Instruction->next())
-      Result.push_back(Instruction);
-  return Result;
+    Roots.push_back(Block);
+  std::ranges::sort(Roots, {},
+                    [](const MachineBasicBlock *Block) { return Block->stableID().value(); });
+  if (MachineBasicBlock *Entry = Function.firstBlock(); Entry != nullptr) {
+    const auto Position = std::ranges::find(Roots, Entry);
+    if (Position != Roots.end())
+      std::rotate(Roots.begin(), Position, std::next(Position));
+  }
+
+  std::vector<MachineBasicBlock *> PostOrder;
+  std::unordered_set<MachineBasicBlock *> Visited;
+  std::vector<TraversalFrame> Stack;
+  for (MachineBasicBlock *Root : Roots) {
+    if (!Visited.insert(Root).second)
+      continue;
+    Stack.push_back(makeFrame(*Root));
+    while (!Stack.empty()) {
+      TraversalFrame &Frame = Stack.back();
+      if (Frame.NextSuccessor < Frame.Successors.size()) {
+        MachineBasicBlock *Successor = Frame.Successors[Frame.NextSuccessor++];
+        if (Visited.insert(Successor).second)
+          Stack.push_back(makeFrame(*Successor));
+        continue;
+      }
+      PostOrder.push_back(Frame.Block);
+      Stack.pop_back();
+    }
+  }
+  std::ranges::reverse(PostOrder);
+  return PostOrder;
 }
 
 [[nodiscard]] Expected<void> requireProperties(const MachineFunction &Function,
@@ -202,91 +271,136 @@ Expected<MachinePassResult> Legalizer::run(MachineFunction &Function,
 Expected<MachinePassResult> Legalizer::runImplementation(MachineFunction &Function,
                                                          const TargetDescription &Target,
                                                          MachineActionReplay &Actions) {
-
   MachinePassResult Result;
-  std::unordered_set<OpcodeState, OpcodeStateHash> SeenStates;
-
-  std::vector<MachineInstr *> Worklist = layoutInstructions(Function);
-  std::unordered_set<MachineInstrStableID> PendingInstructions;
-  for (const MachineInstr *Instruction : Worklist)
-    PendingInstructions.insert(Instruction->stableID());
-  for (std::size_t Index = 0; Index < Worklist.size(); ++Index) {
-    MachineInstr *Instruction = Worklist[Index];
-    if (Instruction != nullptr)
-      PendingInstructions.erase(Instruction->stableID());
-    if (Instruction == nullptr || Instruction->parent() == nullptr)
-      continue;
+  InstList InstructionWorklist;
+  ArtifactList ArtifactWorklist;
+  std::vector<MachineInstr *> RetryList;
 
-    const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
-    if (Descriptor == nullptr)
-      return std::unexpected(
-          passFailure("legalizer encountered an unknown instruction descriptor"));
-    if (!Descriptor->Flags.has(InstructionFlag::Generic))
-      continue;
+  for (MachineBasicBlock *Block : reversePostOrderBlocks(Function)) {
+    for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      if (!isGenericOpcode(Instruction->opcode()))
+        continue;
+      if (isArtifact(*Instruction))
+        ArtifactWorklist.deferredInsert(Instruction);
+      else
+        InstructionWorklist.deferredInsert(Instruction);
+    }
+  }
+  ArtifactWorklist.finalize();
+  InstructionWorklist.finalize();
 
-    auto Validation = Target.validateInstruction(*Instruction, Function.registerInfo());
-    if (!Validation)
-      return std::unexpected(withErrorContext(Validation.error(), "legalizer input is invalid: "));
+  LegalizerWorkListManager WorkListObserver(InstructionWorklist, ArtifactWorklist);
+  GISelObserverWrapper Observer(WorkListObserver);
+  MachineFunctionDelegateInstaller ObserverInstaller(Function, Observer);
+  MachineIRBuilder Builder(Function, Target);
+  LegalizerHelper Helper(Function, *Info, Observer, Builder);
+  LegalizationArtifactCombiner ArtifactCombiner(Builder, Function.registerInfo(), *Info);
 
-    auto Action = Info->classify(*Instruction, Function, Target);
-    if (!Action)
-      return std::unexpected(Action.error());
-    if (*Action == LegalizationAction::Legal)
-      continue;
-    if (*Action == LegalizationAction::Unsupported) {
-      return std::unexpected(
-          passFailure("target legalizer rejected generic instruction '" + Descriptor->Name + "'",
-                      ErrorCode::Unsupported));
-    }
+  do {
+    while (!InstructionWorklist.empty()) {
+      MachineInstr *Instruction = InstructionWorklist.popBack();
+      if (Instruction == nullptr || Instruction->parent() == nullptr)
+        continue;
 
-    const OpcodeState Before = stateOf(*Instruction);
-    if (!SeenStates.insert(Before).second)
-      return std::unexpected(
-          passFailure("target legalizer entered a repeated state for '" + Descriptor->Name + "'",
-                      ErrorCode::InternalError));
+      const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+      if (Descriptor == nullptr)
+        return std::unexpected(
+            passFailure("legalizer encountered an unknown instruction descriptor"));
+      if (!Descriptor->Flags.has(InstructionFlag::Generic))
+        continue;
 
-    auto LoweringValidation = Info->validateLowering(*Instruction, Function, Target, *Action);
-    if (!LoweringValidation)
-      return std::unexpected(
-          withErrorContext(LoweringValidation.error(), "legalizer lowering precondition failed: "));
-    std::string Rule = "legalize.";
-    Rule.append(legalizationActionName(*Action));
-    Rule.push_back('.');
-    Rule.append(Descriptor->Name);
-    auto Accepted = Actions.request(Rule, Function, Instruction->stableID());
-    if (!Accepted)
-      return std::unexpected(Accepted.error());
-    if (!*Accepted) {
-      return std::unexpected(
-          passFailure("required legalizer action was rejected for '" + Descriptor->Name + "'",
-                      ErrorCode::VerificationError));
+      auto Validation = Target.validateInstruction(*Instruction, Function.registerInfo());
+      if (!Validation) {
+        return std::unexpected(
+            withErrorContext(Validation.error(), "legalizer input is invalid: "));
+      }
+
+      auto Decision = Info->getDecision(*Instruction, Function, Target);
+      if (!Decision)
+        return std::unexpected(Decision.error());
+      if (Decision->Action == LegalizationAction::Legal)
+        continue;
+      if (Decision->Action == LegalizationAction::Unsupported) {
+        if (isArtifact(*Instruction)) {
+          RetryList.push_back(Instruction);
+          continue;
+        }
+        return std::unexpected(
+            passFailure("target legalizer rejected generic instruction '" + Descriptor->Name + "'",
+                        ErrorCode::Unsupported));
+      }
+
+      auto LoweringValidation = Info->validateLowering(*Instruction, Function, Target, *Decision);
+      if (!LoweringValidation) {
+        return std::unexpected(withErrorContext(LoweringValidation.error(),
+                                                "legalizer lowering precondition failed: "));
+      }
+      std::string Rule = "legalize.";
+      Rule.append(legalizationActionName(Decision->Action));
+      Rule.push_back('.');
+      Rule.append(Descriptor->Name);
+      auto Accepted = Actions.request(Rule, Function, Instruction->stableID());
+      if (!Accepted)
+        return std::unexpected(Accepted.error());
+      if (!*Accepted) {
+        return std::unexpected(
+            passFailure("required legalizer action was rejected for '" + Descriptor->Name + "'",
+                        ErrorCode::VerificationError));
+      }
+      Expected<void> Lowered = Helper.legalize(*Instruction, *Decision);
+      if (!Lowered) {
+        if (Lowered.error().code() == ErrorCode::Unsupported && Instruction->parent() != nullptr &&
+            isArtifact(*Instruction)) {
+          RetryList.push_back(Instruction);
+          continue;
+        }
+        return std::unexpected(Lowered.error());
+      }
+      Result.Changed = true;
+      Result.Changes.add(MachinePassChange::Instructions);
     }
-    auto Lowered = Info->lower(*Instruction, Function, Target, *Action);
-    if (!Lowered)
-      return std::unexpected(Lowered.error());
-    const bool InstructionWasErased = Instruction->parent() == nullptr;
-    if (!InstructionWasErased) {
-      const OpcodeState After = stateOf(*Instruction);
-      if (After == Before)
-        return std::unexpected(passFailure("target legalizer made no observable progress for '" +
-                                               Descriptor->Name + "'",
-                                           ErrorCode::InternalError));
+
+    if (!RetryList.empty()) {
+      if (!ArtifactWorklist.empty()) {
+        for (MachineInstr *Instruction : RetryList)
+          ArtifactWorklist.insert(Instruction);
+        RetryList.clear();
+      } else {
+        MachineInstr *Instruction = RetryList.front();
+        const InstructionDescriptor *Descriptor =
+            Instruction == nullptr ? nullptr : Target.instructionDescriptor(Instruction->opcode());
+        return std::unexpected(passFailure(
+            "target legalizer rejected generic artifact '" +
+                std::string(Descriptor == nullptr ? "<unknown>" : Descriptor->Name) + "'",
+            ErrorCode::Unsupported));
+      }
     }
-    Result.Changed = true;
-    Result.Changes.add(MachinePassChange::Instructions);
-
-    const std::vector<MachineInstr *> Current = layoutInstructions(Function);
-    for (MachineInstr *Candidate : Current) {
-      const InstructionDescriptor *CandidateDescriptor =
-          Target.instructionDescriptor(Candidate->opcode());
-      if (CandidateDescriptor == nullptr)
-        return std::unexpected(passFailure("legalizer produced an unknown instruction descriptor"));
-      if (CandidateDescriptor->Flags.has(InstructionFlag::Generic) &&
-          PendingInstructions.insert(Candidate->stableID()).second) {
-        Worklist.push_back(Candidate);
+
+    while (!ArtifactWorklist.empty()) {
+      MachineInstr *Instruction = ArtifactWorklist.popBack();
+      if (Instruction == nullptr || Instruction->parent() == nullptr)
+        continue;
+      std::vector<MachineInstr *> DeadInstructions;
+      auto Combined =
+          ArtifactCombiner.tryCombineInstruction(*Instruction, DeadInstructions, Observer);
+      if (!Combined)
+        return std::unexpected(Combined.error());
+      if (*Combined) {
+        for (MachineInstr *Dead : DeadInstructions) {
+          if (Dead == nullptr || Dead->parent() == nullptr)
+            continue;
+          auto Removed = Dead->parent()->removeInstruction(*Dead);
+          if (!Removed)
+            return std::unexpected(Removed.error());
+        }
+        Result.Changed = true;
+        Result.Changes.add(MachinePassChange::Instructions);
+        continue;
       }
+      InstructionWorklist.insert(Instruction);
     }
-  }
+  } while (!InstructionWorklist.empty());
 
   for (MachineInstr *Instruction : layoutInstructions(Function)) {
     const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
@@ -294,15 +408,16 @@ Expected<MachinePassResult> Legalizer::runImplementation(MachineFunction &Functi
       return std::unexpected(passFailure("legalizer produced an unknown instruction descriptor"));
     if (!Descriptor->Flags.has(InstructionFlag::Generic))
       continue;
-    auto Action = Info->classify(*Instruction, Function, Target);
-    if (!Action)
-      return std::unexpected(Action.error());
-    if (*Action != LegalizationAction::Legal)
-      return std::unexpected(
-          passFailure("legalizer reached a fixed point with an illegal generic instruction '" +
-                          Descriptor->Name + "'",
-                      *Action == LegalizationAction::Unsupported ? ErrorCode::Unsupported
-                                                                 : ErrorCode::InternalError));
+    auto Decision = Info->getDecision(*Instruction, Function, Target);
+    if (!Decision)
+      return std::unexpected(Decision.error());
+    if (Decision->Action != LegalizationAction::Legal &&
+        Decision->Action != LegalizationAction::Custom)
+      return std::unexpected(passFailure(
+          "legalizer reached a fixed point with an illegal generic instruction '" +
+              Descriptor->Name + "'",
+          Decision->Action == LegalizationAction::Unsupported ? ErrorCode::Unsupported
+                                                              : ErrorCode::InternalError));
     auto FinalValidation = Target.validateInstruction(*Instruction, Function.registerInfo());
     if (!FinalValidation)
       return std::unexpected(
diff --git a/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp b/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp
new file mode 100644
index 0000000..1e52214
--- /dev/null
+++ b/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp
@@ -0,0 +1,590 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/GlobalISel/LegalizerHelper.h"
+
+#include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineMemOperand.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+
+#include <algorithm>
+#include <bit>
+#include <cstddef>
+#include <cstdint>
+#include <optional>
+#include <utility>
+
+namespace rcc {
+namespace {
+
+struct ScalarLayout final {
+  std::uint64_t StoreSize = 0;
+  std::uint64_t AllocationSize = 0;
+  std::uint64_t ABIAlignment = 0;
+};
+
+[[nodiscard]] Expected<std::int64_t> signedImmediate(const MachineOperand &Operand) {
+  if (const std::int64_t *Value = Operand.getIf<std::int64_t>())
+    return *Value;
+  const auto *Integer = Operand.getIf<IntegerImmediateOperand>();
+  if (Integer == nullptr || Integer->Value.bitWidth() == 0 || Integer->Value.bitWidth() > 64) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "legalizer requires an immediate no wider than 64 bits");
+  }
+  std::uint64_t Raw = Integer->Value.words().empty() ? 0 : Integer->Value.words().front();
+  const std::uint32_t Width = Integer->Value.bitWidth();
+  if (Width < 64 && (Raw & (std::uint64_t{1} << (Width - 1U))) != 0)
+    Raw |= ~std::uint64_t{0} << Width;
+  return std::bit_cast<std::int64_t>(Raw);
+}
+
+[[nodiscard]] std::optional<ScalarLayout> scalarLayout(LowLevelType Type) noexcept {
+  if (!Type.isScalarValue() || Type.scalarBitWidth() == 0)
+    return std::nullopt;
+  const std::uint64_t StoreSize = (Type.scalarBitWidth() + 7U) / 8U;
+  const std::uint64_t AllocationSize = std::bit_ceil(StoreSize);
+  return ScalarLayout{StoreSize, AllocationSize, std::min<std::uint64_t>(AllocationSize, 8)};
+}
+
+[[nodiscard]] Expected<const MachineMemOperand *> createMemoryAccess(MachineFunction &Function,
+                                                                     MemoryAccessFlag Access,
+                                                                     LowLevelType Type,
+                                                                     const ScalarLayout &Layout) {
+  auto Size = MemorySize::fixed(Layout.StoreSize);
+  auto Align = Alignment::create(Layout.ABIAlignment);
+  if (!Size || !Align)
+    return makeUnexpected(ErrorCode::InternalError,
+                          "legalizer cannot represent scalar memory layout");
+  MachineMemOperandDesc Description;
+  Description.Accesses = {Access};
+  Description.Size = *Size;
+  Description.MemoryType = Type;
+  Description.Align = *Align;
+  return Function.createMemOperand(std::move(Description));
+}
+
+[[nodiscard]] Expected<Register> buildConstantBefore(MachineIRBuilder &Builder,
+                                                     MachineInstr &Anchor, LowLevelType Type,
+                                                     std::uint64_t Value) {
+  auto Result = Builder.function().registerInfo().createVirtualRegister(Type);
+  if (!Result)
+    return std::unexpected(Result.error());
+  auto Immediate = APInt::fromUnsigned(Type.scalarBitWidth(), Value);
+  if (!Immediate)
+    return std::unexpected(Immediate.error());
+  if (auto Point = Builder.setInsertPointBefore(Anchor); !Point)
+    return std::unexpected(Point.error());
+  auto Built = Builder.buildConstant(*Result, std::move(*Immediate));
+  if (!Built)
+    return std::unexpected(Built.error());
+  return *Result;
+}
+
+[[nodiscard]] Expected<Register> buildBinaryBefore(MachineIRBuilder &Builder, MachineInstr &Anchor,
+                                                   GenericOpcode Generic, LowLevelType Type,
+                                                   Register Left, Register Right) {
+  auto Result = Builder.function().registerInfo().createVirtualRegister(Type);
+  if (!Result)
+    return std::unexpected(Result.error());
+  if (auto Point = Builder.setInsertPointBefore(Anchor); !Point)
+    return std::unexpected(Point.error());
+  auto Pending = Builder.buildInstr(opcode(Generic));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  if (auto Added = Pending->addDef(*Result); !Added)
+    return std::unexpected(Added.error());
+  if (auto Added = Pending->addUse(Left); !Added)
+    return std::unexpected(Added.error());
+  if (auto Added = Pending->addUse(Right); !Added)
+    return std::unexpected(Added.error());
+  auto Built = Pending->build();
+  if (!Built)
+    return std::unexpected(Built.error());
+  return *Result;
+}
+
+} // namespace
+
+LegalizerHelper::LegalizerHelper(MachineFunction &Function, const LegalizerInfo &Info,
+                                 GISelChangeObserver &Observer, MachineIRBuilder &MIRBuilder)
+    : MIRBuilder(MIRBuilder), Observer(Observer), Function(Function), MRI(Function.registerInfo()),
+      Info(Info) {}
+
+Expected<void> LegalizerHelper::widenScalarSrc(MachineInstr &Instruction, LowLevelType WideType,
+                                               std::size_t OperandIndex,
+                                               GenericOpcode ExtensionOpcode) {
+  MachineOperand *Operand = Instruction.operandAt(OperandIndex);
+  const Register *Source = Operand == nullptr ? nullptr : Operand->getIf<Register>();
+  if (Source == nullptr || !Source->isVirtual() || !Operand->isUse())
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "scalar widening source is not a virtual-register use");
+
+  auto WideSource = MRI.createVirtualRegister(WideType);
+  if (!WideSource)
+    return std::unexpected(WideSource.error());
+  if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
+    return std::unexpected(Point.error());
+  auto Extension = MIRBuilder.buildInstr(opcode(ExtensionOpcode));
+  if (!Extension)
+    return std::unexpected(Extension.error());
+  if (auto Added = Extension->addDef(*WideSource); !Added)
+    return std::unexpected(Added.error());
+  if (auto Added = Extension->addUse(*Source); !Added)
+    return std::unexpected(Added.error());
+  if (auto Built = Extension->build(); !Built)
+    return std::unexpected(Built.error());
+  return Operand->setRegister(*WideSource);
+}
+
+Expected<void> LegalizerHelper::widenScalarDst(MachineInstr &Instruction, LowLevelType WideType,
+                                               std::size_t OperandIndex,
+                                               GenericOpcode TruncOpcode) {
+  MachineOperand *Operand = Instruction.operandAt(OperandIndex);
+  const Register *Destination = Operand == nullptr ? nullptr : Operand->getIf<Register>();
+  if (Destination == nullptr || !Destination->isVirtual() || !Operand->isDef())
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "scalar widening destination is not a virtual-register definition");
+
+  auto WideDestination = MRI.createVirtualRegister(WideType);
+  if (!WideDestination)
+    return std::unexpected(WideDestination.error());
+  if (auto Point = MIRBuilder.setInsertPointAfter(Instruction); !Point)
+    return std::unexpected(Point.error());
+  auto Truncation = MIRBuilder.buildInstr(opcode(TruncOpcode));
+  if (!Truncation)
+    return std::unexpected(Truncation.error());
+  if (auto Added = Truncation->addDef(*Destination); !Added)
+    return std::unexpected(Added.error());
+  if (auto Added = Truncation->addUse(*WideDestination); !Added)
+    return std::unexpected(Added.error());
+  if (auto Built = Truncation->build(); !Built)
+    return std::unexpected(Built.error());
+  return Operand->setRegister(*WideDestination);
+}
+
+Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size_t TypeIndex,
+                                            LowLevelType WideType) {
+  auto Query = LegalizerInfo::buildQuery(Instruction, Function, MIRBuilder.target());
+  if (!Query)
+    return std::unexpected(Query.error());
+  if (!WideType.isCategoryNeutralScalar() || TypeIndex >= Query->Types.size() ||
+      !Query->Types[TypeIndex].isCategoryNeutralScalar() ||
+      WideType.scalarBitWidth() <= Query->Types[TypeIndex].scalarBitWidth()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "scalar widening has an invalid type index or target type");
+  }
+
+  const auto widenSource = [&](std::size_t OperandIndex, GenericOpcode ExtensionOpcode) {
+    return widenScalarSrc(Instruction, WideType, OperandIndex, ExtensionOpcode);
+  };
+  const auto widenDestination = [&](std::size_t OperandIndex = 0,
+                                    GenericOpcode TruncOpcode = GenericOpcode::G_TRUNC) {
+    return widenScalarDst(Instruction, WideType, OperandIndex, TruncOpcode);
+  };
+  const auto apply = [](Expected<void> Result) -> Expected<void> {
+    if (!Result)
+      return std::unexpected(Result.error());
+    return {};
+  };
+
+  Observer.changingInstr(Instruction);
+  switch (static_cast<GenericOpcode>(Instruction.opcode().value())) {
+  case GenericOpcode::G_ATOMICRMW_XCHG:
+  case GenericOpcode::G_ATOMICRMW_ADD:
+  case GenericOpcode::G_ATOMICRMW_SUB:
+  case GenericOpcode::G_ATOMICRMW_AND:
+  case GenericOpcode::G_ATOMICRMW_OR:
+  case GenericOpcode::G_ATOMICRMW_XOR:
+  case GenericOpcode::G_ATOMICRMW_MIN:
+  case GenericOpcode::G_ATOMICRMW_MAX:
+  case GenericOpcode::G_ATOMICRMW_UMIN:
+  case GenericOpcode::G_ATOMICRMW_UMAX:
+    if (TypeIndex != 0)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "atomic RMW value widening has an invalid type index");
+    if (auto Result = apply(widenSource(2, GenericOpcode::G_ANYEXT)); !Result)
+      return Result;
+    if (auto Result = apply(widenDestination()); !Result)
+      return Result;
+    break;
+
+  case GenericOpcode::G_ATOMIC_CMPXCHG:
+    if (TypeIndex != 0)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "compare-exchange widening has an invalid type index");
+    if (auto Result = apply(widenSource(2, GenericOpcode::G_ANYEXT)); !Result)
+      return Result;
+    if (auto Result = apply(widenSource(3, GenericOpcode::G_ANYEXT)); !Result)
+      return Result;
+    if (auto Result = apply(widenDestination()); !Result)
+      return Result;
+    break;
+
+  case GenericOpcode::G_ATOMIC_CMPXCHG_WITH_SUCCESS:
+    if (TypeIndex == 0) {
+      if (auto Result = apply(widenSource(3, GenericOpcode::G_ANYEXT)); !Result)
+        return Result;
+      if (auto Result = apply(widenSource(4, GenericOpcode::G_ANYEXT)); !Result)
+        return Result;
+      if (auto Result = apply(widenDestination()); !Result)
+        return Result;
+      break;
+    }
+    if (TypeIndex != 1)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "compare-exchange success widening has an invalid type index");
+    if (auto Result = apply(widenDestination(1)); !Result)
+      return Result;
+    break;
+
+  case GenericOpcode::G_ADD:
+  case GenericOpcode::G_SUB:
+  case GenericOpcode::G_MUL:
+  case GenericOpcode::G_AND:
+  case GenericOpcode::G_OR:
+  case GenericOpcode::G_XOR:
+    if (TypeIndex != 0)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "binary operation widening has an invalid type index");
+    if (auto Result = apply(widenSource(1, GenericOpcode::G_ANYEXT)); !Result)
+      return Result;
+    if (auto Result = apply(widenSource(2, GenericOpcode::G_ANYEXT)); !Result)
+      return Result;
+    if (auto Result = apply(widenDestination()); !Result)
+      return Result;
+    break;
+
+  case GenericOpcode::G_SDIV:
+  case GenericOpcode::G_SREM:
+  case GenericOpcode::G_SMIN:
+  case GenericOpcode::G_SMAX:
+  case GenericOpcode::G_ABDS:
+    if (TypeIndex != 0)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "signed operation widening has an invalid type index");
+    if (auto Result = apply(widenSource(1, GenericOpcode::G_SEXT)); !Result)
+      return Result;
+    if (auto Result = apply(widenSource(2, GenericOpcode::G_SEXT)); !Result)
+      return Result;
+    if (auto Result = apply(widenDestination()); !Result)
+      return Result;
+    break;
+
+  case GenericOpcode::G_UDIV:
+  case GenericOpcode::G_UREM:
+  case GenericOpcode::G_UMIN:
+  case GenericOpcode::G_UMAX:
+  case GenericOpcode::G_ABDU:
+    if (TypeIndex != 0)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "unsigned operation widening has an invalid type index");
+    if (auto Result = apply(widenSource(1, GenericOpcode::G_ZEXT)); !Result)
+      return Result;
+    if (auto Result = apply(widenSource(2, GenericOpcode::G_ZEXT)); !Result)
+      return Result;
+    if (auto Result = apply(widenDestination()); !Result)
+      return Result;
+    break;
+
+  case GenericOpcode::G_SHL:
+  case GenericOpcode::G_LSHR:
+  case GenericOpcode::G_ASHR:
+    if (TypeIndex == 0) {
+      GenericOpcode ExtensionOpcode = GenericOpcode::G_ANYEXT;
+      if (Instruction.opcode() == opcode(GenericOpcode::G_LSHR))
+        ExtensionOpcode = GenericOpcode::G_ZEXT;
+      else if (Instruction.opcode() == opcode(GenericOpcode::G_ASHR))
+        ExtensionOpcode = GenericOpcode::G_SEXT;
+      if (auto Result = apply(widenSource(1, ExtensionOpcode)); !Result)
+        return Result;
+      if (auto Result = apply(widenDestination()); !Result)
+        return Result;
+      break;
+    }
+    if (TypeIndex != 1)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "shift widening has an invalid type index");
+    if (auto Result = apply(widenSource(2, GenericOpcode::G_ZEXT)); !Result)
+      return Result;
+    break;
+
+  case GenericOpcode::G_ROTL:
+  case GenericOpcode::G_ROTR:
+    if (TypeIndex != 1)
+      return makeUnexpected(ErrorCode::Unsupported, "rotate value widening is not defined");
+    if (auto Result = apply(widenSource(2, GenericOpcode::G_ZEXT)); !Result)
+      return Result;
+    break;
+
+  case GenericOpcode::G_FREEZE:
+  case GenericOpcode::G_CONSTANT_FOLD_BARRIER:
+    if (TypeIndex != 0)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "unary operation widening has an invalid type index");
+    if (auto Result = apply(widenSource(1, GenericOpcode::G_ANYEXT)); !Result)
+      return Result;
+    if (auto Result = apply(widenDestination()); !Result)
+      return Result;
+    break;
+
+  case GenericOpcode::G_ABS:
+    if (TypeIndex != 0)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "absolute-value widening has an invalid type index");
+    if (auto Result = apply(widenSource(1, GenericOpcode::G_SEXT)); !Result)
+      return Result;
+    if (auto Result = apply(widenDestination()); !Result)
+      return Result;
+    break;
+
+  case GenericOpcode::G_SELECT:
+    if (TypeIndex == 0) {
+      if (auto Result = apply(widenSource(2, GenericOpcode::G_ANYEXT)); !Result)
+        return Result;
+      if (auto Result = apply(widenSource(3, GenericOpcode::G_ANYEXT)); !Result)
+        return Result;
+      if (auto Result = apply(widenDestination()); !Result)
+        return Result;
+      break;
+    }
+    if (TypeIndex != 1)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "select widening has an invalid type index");
+    if (auto Result = apply(widenSource(1, GenericOpcode::G_ZEXT)); !Result)
+      return Result;
+    break;
+
+  case GenericOpcode::G_FPEXT:
+    if (TypeIndex != 1)
+      return makeUnexpected(ErrorCode::Unsupported,
+                            "floating-point extension destination widening is not defined");
+    if (auto Result = apply(widenSource(1, GenericOpcode::G_FPEXT)); !Result)
+      return Result;
+    break;
+
+  case GenericOpcode::G_FPTOSI:
+  case GenericOpcode::G_FPTOUI:
+  case GenericOpcode::G_INTRINSIC_LRINT:
+  case GenericOpcode::G_INTRINSIC_LLRINT:
+  case GenericOpcode::G_IS_FPCLASS:
+    if (TypeIndex == 0) {
+      if (auto Result = apply(widenDestination()); !Result)
+        return Result;
+      break;
+    }
+    if (TypeIndex != 1)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "floating-to-integer widening has an invalid type index");
+    if (auto Result = apply(widenSource(1, GenericOpcode::G_FPEXT)); !Result)
+      return Result;
+    break;
+
+  case GenericOpcode::G_SITOFP:
+  case GenericOpcode::G_UITOFP:
+    if (TypeIndex == 0) {
+      if (auto Result = apply(widenDestination(0, GenericOpcode::G_FPTRUNC)); !Result)
+        return Result;
+      break;
+    }
+    if (TypeIndex != 1)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "integer-to-floating widening has an invalid type index");
+    if (auto Result = apply(widenSource(1, Instruction.opcode() == opcode(GenericOpcode::G_SITOFP)
+                                               ? GenericOpcode::G_SEXT
+                                               : GenericOpcode::G_ZEXT));
+        !Result)
+      return Result;
+    break;
+
+  default:
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "scalar widening is not implemented for this opcode");
+  }
+
+  Observer.changedInstr(Instruction);
+  return {};
+}
+
+Expected<void> LegalizerHelper::lowerVAArg(MachineInstr &Instruction) {
+  if (Instruction.opcode() != opcode(GenericOpcode::G_VAARG) || Instruction.operandCount() != 3 ||
+      !Instruction.memOperands().empty()) {
+    return makeUnexpected(ErrorCode::VerificationError, "G_VAARG has invalid operands");
+  }
+
+  MachineOperand *DestinationOperand = Instruction.operandAt(0);
+  MachineOperand *ListOperand = Instruction.operandAt(1);
+  MachineOperand *AlignmentOperand = Instruction.operandAt(2);
+  const Register *Destination =
+      DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>();
+  const Register *ListPointer = ListOperand == nullptr ? nullptr : ListOperand->getIf<Register>();
+  if (Destination == nullptr || ListPointer == nullptr || !Destination->isVirtual() ||
+      !ListPointer->isVirtual() || !DestinationOperand->isDef() || !ListOperand->isUse() ||
+      AlignmentOperand == nullptr) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "G_VAARG requires virtual-register operands");
+  }
+
+  auto DestinationInfo = MRI.virtualRegisterInfo(*Destination);
+  auto PointerInfo = MRI.virtualRegisterInfo(*ListPointer);
+  auto RequestedAlignment = signedImmediate(*AlignmentOperand);
+  if (!DestinationInfo || !PointerInfo || !DestinationInfo->get().Type ||
+      !PointerInfo->get().Type || !RequestedAlignment || *RequestedAlignment <= 0 ||
+      !std::has_single_bit(static_cast<std::uint64_t>(*RequestedAlignment))) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "G_VAARG has invalid type or alignment information");
+  }
+
+  const LowLevelType DestinationType = *DestinationInfo->get().Type;
+  const LowLevelType PointerType = *PointerInfo->get().Type;
+  const auto DestinationLayout = scalarLayout(DestinationType);
+  const auto PointerLayout = scalarLayout(PointerType);
+  if (!DestinationLayout || !PointerLayout || !PointerType.isPointer()) {
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "G_VAARG requires scalar result and pointer list types");
+  }
+
+  auto ListLoadMemory =
+      createMemoryAccess(Function, MemoryAccessFlag::Load, PointerType, *PointerLayout);
+  auto ListStoreMemory =
+      createMemoryAccess(Function, MemoryAccessFlag::Store, PointerType, *PointerLayout);
+  if (!ListLoadMemory)
+    return std::unexpected(ListLoadMemory.error());
+  if (!ListStoreMemory)
+    return std::unexpected(ListStoreMemory.error());
+
+  auto CurrentList = MRI.createVirtualRegister(PointerType);
+  if (!CurrentList)
+    return std::unexpected(CurrentList.error());
+  if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point)
+    return std::unexpected(Point.error());
+  auto ListLoad = MIRBuilder.buildInstr(opcode(GenericOpcode::G_LOAD));
+  if (!ListLoad)
+    return std::unexpected(ListLoad.error());
+  if (auto Added = ListLoad->addDef(*CurrentList); !Added)
+    return std::unexpected(Added.error());
+  if (auto Added = ListLoad->addUse(*ListPointer); !Added)
+    return std::unexpected(Added.error());
+  if (auto Added = ListLoad->addMemOperand(**ListLoadMemory); !Added)
+    return std::unexpected(Added.error());
+  if (auto Built = ListLoad->build(); !Built)
+    return std::unexpected(Built.error());
+
+  Register ValueAddress = *CurrentList;
+  const std::uint64_t AlignmentValue = static_cast<std::uint64_t>(*RequestedAlignment);
+  auto PointerScalarType = LowLevelType::makeCategoryNeutralScalar(PointerType.scalarBitWidth());
+  if (!PointerScalarType)
+    return std::unexpected(PointerScalarType.error());
+  if (AlignmentValue > 1) {
+    auto AlignmentOffset =
+        buildConstantBefore(MIRBuilder, Instruction, *PointerScalarType, AlignmentValue - 1U);
+    if (!AlignmentOffset)
+      return std::unexpected(AlignmentOffset.error());
+    auto BiasedAddress = buildBinaryBefore(MIRBuilder, Instruction, GenericOpcode::G_PTR_ADD,
+                                           PointerType, ValueAddress, *AlignmentOffset);
+    if (!BiasedAddress)
+      return std::unexpected(BiasedAddress.error());
+    auto AlignmentMask =
+        buildConstantBefore(MIRBuilder, Instruction, *PointerScalarType, ~(AlignmentValue - 1U));
+    if (!AlignmentMask)
+      return std::unexpected(AlignmentMask.error());
+    auto AlignedAddress = buildBinaryBefore(MIRBuilder, Instruction, GenericOpcode::G_PTRMASK,
+                                            PointerType, *BiasedAddress, *AlignmentMask);
+    if (!AlignedAddress)
+      return std::unexpected(AlignedAddress.error());
+    ValueAddress = *AlignedAddress;
+  }
+
+  auto Increment = buildConstantBefore(MIRBuilder, Instruction, *PointerScalarType,
+                                       DestinationLayout->AllocationSize);
+  if (!Increment)
+    return std::unexpected(Increment.error());
+  auto NextList = buildBinaryBefore(MIRBuilder, Instruction, GenericOpcode::G_PTR_ADD, PointerType,
+                                    ValueAddress, *Increment);
+  if (!NextList)
+    return std::unexpected(NextList.error());
+
+  auto ListStore = MIRBuilder.buildInstr(opcode(GenericOpcode::G_STORE));
+  if (!ListStore)
+    return std::unexpected(ListStore.error());
+  if (auto Added = ListStore->addUse(*NextList); !Added)
+    return std::unexpected(Added.error());
+  if (auto Added = ListStore->addUse(*ListPointer); !Added)
+    return std::unexpected(Added.error());
+  if (auto Added = ListStore->addMemOperand(**ListStoreMemory); !Added)
+    return std::unexpected(Added.error());
+  if (auto Built = ListStore->build(); !Built)
+    return std::unexpected(Built.error());
+
+  if (!MRI.useEmpty(*Destination)) {
+    auto ValueLoadMemory =
+        createMemoryAccess(Function, MemoryAccessFlag::Load, DestinationType, *DestinationLayout);
+    if (!ValueLoadMemory)
+      return std::unexpected(ValueLoadMemory.error());
+    auto ValueLoad = MIRBuilder.buildInstr(opcode(GenericOpcode::G_LOAD));
+    if (!ValueLoad)
+      return std::unexpected(ValueLoad.error());
+    if (auto Added = ValueLoad->addDef(*Destination); !Added)
+      return std::unexpected(Added.error());
+    if (auto Added = ValueLoad->addUse(ValueAddress); !Added)
+      return std::unexpected(Added.error());
+    if (auto Added = ValueLoad->addMemOperand(**ValueLoadMemory); !Added)
+      return std::unexpected(Added.error());
+    if (auto Built = ValueLoad->build(); !Built)
+      return std::unexpected(Built.error());
+  }
+
+  MachineBasicBlock *Block = Instruction.parent();
+  if (Block == nullptr)
+    return makeUnexpected(ErrorCode::VerificationError, "G_VAARG is detached during legalization");
+  return Block->removeInstruction(Instruction);
+}
+
+Expected<void> LegalizerHelper::lower(MachineInstr &Instruction,
+                                      const LegalizationDecision &Decision) {
+  if (Decision.Action != LegalizationAction::Lower)
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "lower received a non-lower legalization action");
+  switch (static_cast<GenericOpcode>(Instruction.opcode().value())) {
+  case GenericOpcode::G_VAARG:
+    return lowerVAArg(Instruction);
+  default: {
+    const InstructionDescriptor *Descriptor =
+        MIRBuilder.target().instructionDescriptor(Instruction.opcode());
+    const std::string_view Name =
+        Descriptor == nullptr ? std::string_view{"<unknown>"} : Descriptor->Name;
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "generic lowering is not implemented for opcode '" + std::string(Name) +
+                              "'");
+  }
+  }
+}
+
+Expected<void> LegalizerHelper::legalize(MachineInstr &Instruction,
+                                         const LegalizationDecision &Decision) {
+  switch (Decision.Action) {
+  case LegalizationAction::WidenScalar:
+    return widenScalar(Instruction, Decision.TypeIndex, Decision.NewType);
+  case LegalizationAction::Custom:
+    return Info.legalizeCustom(*this, Instruction, Decision);
+  case LegalizationAction::Lower:
+    return lower(Instruction, Decision);
+  case LegalizationAction::Legal:
+    return {};
+  case LegalizationAction::Unsupported:
+  case LegalizationAction::Libcall:
+  case LegalizationAction::NarrowScalar:
+  case LegalizationAction::MoreElements:
+  case LegalizationAction::FewerElements:
+  case LegalizationAction::Bitcast:
+  case LegalizationAction::ChangeElementType:
+  case LegalizationAction::ChangeAddressSpace:
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "legalizer helper does not implement the requested action");
+  }
+  return makeUnexpected(ErrorCode::InternalError, "unknown legalization action");
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp b/backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp
new file mode 100644
index 0000000..7d9e6ff
--- /dev/null
+++ b/backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp
@@ -0,0 +1,477 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/GlobalISel/LegalizerInfo.h"
+
+#include "rcc/CodeGen/GenericOpcodes.h"
+#include "rcc/CodeGen/InstructionDescriptor.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/TargetDescription.h"
+
+#include <algorithm>
+#include <bit>
+#include <cstddef>
+#include <cstdint>
+#include <optional>
+#include <ranges>
+#include <tuple>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] LegalityPredicate typeInSet(std::size_t TypeIndex, std::vector<LowLevelType> Types) {
+  return [TypeIndex, Types = std::move(Types)](const LegalizationQuery &Query) {
+    return TypeIndex < Query.Types.size() &&
+           std::ranges::find(Types, Query.Types[TypeIndex]) != Types.end();
+  };
+}
+
+[[nodiscard]] LegalityPredicate
+typePairInSet(std::vector<std::pair<LowLevelType, LowLevelType>> Types) {
+  return [Types = std::move(Types)](const LegalizationQuery &Query) {
+    return Query.Types.size() >= 2 &&
+           std::ranges::find(Types, std::pair{Query.Types[0], Query.Types[1]}) != Types.end();
+  };
+}
+
+[[nodiscard]] LegalityPredicate
+typeTripleInSet(std::vector<std::tuple<LowLevelType, LowLevelType, LowLevelType>> Types) {
+  return [Types = std::move(Types)](const LegalizationQuery &Query) {
+    return Query.Types.size() >= 3 &&
+           std::ranges::find(Types, std::tuple{Query.Types[0], Query.Types[1], Query.Types[2]}) !=
+               Types.end();
+  };
+}
+
+[[nodiscard]] LowLevelType scalarType(std::uint32_t BitWidth) {
+  auto Type = LowLevelType::makeCategoryNeutralScalar(BitWidth);
+  return Type ? *Type : LowLevelType{};
+}
+
+[[nodiscard]] std::uint32_t nextPowerOfTwo(std::uint32_t Width, std::uint32_t MinimumBitWidth) {
+  return std::max(std::bit_ceil(Width), MinimumBitWidth);
+}
+
+[[nodiscard]] bool memoryRuleMatches(const LegalizationQuery &Query,
+                                     const LegalizeMemoryRule &Rule) {
+  if (Query.Types.size() < 2 || Query.MemoryOperands.size() != 1 ||
+      Query.Types[0] != Rule.ValueType || Query.Types[1] != Rule.AddressType)
+    return false;
+  const LegalizationMemoryDesc &Memory = Query.MemoryOperands.front();
+  if (Memory.AlignmentInBits < Rule.MinimumAlignmentInBits)
+    return false;
+  if (Memory.Type)
+    return Memory.Type->minimumBitWidth() == Rule.MemoryType.minimumBitWidth();
+  return Memory.Size.isKnown() && !Memory.Size.isScalable() &&
+         Memory.Size.minimumBytes() * 8U == Rule.MemoryType.scalarBitWidth();
+}
+
+} // namespace
+
+LegalizeRule::LegalizeRule(LegalityPredicate Predicate, LegalizationAction Action,
+                           LegalizeMutation Mutation)
+    : Predicate(std::move(Predicate)), Action(Action), Mutation(std::move(Mutation)) {}
+
+bool LegalizeRule::matches(const LegalizationQuery &Query) const {
+  return Predicate(Query);
+}
+
+LegalizationDecision LegalizeRule::apply(const LegalizationQuery &Query) const {
+  if (!Mutation)
+    return {.Action = Action, .TypeIndex = 0, .NewType = {}};
+  auto [TypeIndex, NewType] = Mutation(Query);
+  return {.Action = Action, .TypeIndex = TypeIndex, .NewType = NewType};
+}
+
+LegalizeRuleSet &LegalizeRuleSet::actionIf(LegalizationAction Action, LegalityPredicate Predicate,
+                                           LegalizeMutation Mutation) {
+  Rules.emplace_back(std::move(Predicate), Action, std::move(Mutation));
+  return *this;
+}
+
+LegalizeRuleSet &LegalizeRuleSet::actionFor(LegalizationAction Action,
+                                            std::initializer_list<LowLevelType> Types) {
+  return actionIf(Action, typeInSet(0, std::vector<LowLevelType>(Types)));
+}
+
+LegalizeRuleSet &
+LegalizeRuleSet::actionFor(LegalizationAction Action,
+                           std::initializer_list<std::pair<LowLevelType, LowLevelType>> Types) {
+  return actionIf(Action, typePairInSet(std::vector<std::pair<LowLevelType, LowLevelType>>(Types)));
+}
+
+LegalizeRuleSet &LegalizeRuleSet::actionFor(
+    LegalizationAction Action,
+    std::initializer_list<std::tuple<LowLevelType, LowLevelType, LowLevelType>> Types) {
+  return actionIf(
+      Action,
+      typeTripleInSet(std::vector<std::tuple<LowLevelType, LowLevelType, LowLevelType>>(Types)));
+}
+
+LegalizeRuleSet &LegalizeRuleSet::legalIf(LegalityPredicate Predicate) {
+  return actionIf(LegalizationAction::Legal, std::move(Predicate));
+}
+
+LegalizeRuleSet &LegalizeRuleSet::customIf(LegalityPredicate Predicate) {
+  return actionIf(LegalizationAction::Custom, std::move(Predicate));
+}
+
+LegalizeRuleSet &LegalizeRuleSet::lowerIf(LegalityPredicate Predicate) {
+  return actionIf(LegalizationAction::Lower, std::move(Predicate));
+}
+
+LegalizeRuleSet &LegalizeRuleSet::libcallIf(LegalityPredicate Predicate) {
+  return actionIf(LegalizationAction::Libcall, std::move(Predicate));
+}
+
+LegalizeRuleSet &LegalizeRuleSet::unsupportedIf(LegalityPredicate Predicate) {
+  return actionIf(LegalizationAction::Unsupported, std::move(Predicate));
+}
+
+LegalizeRuleSet &LegalizeRuleSet::widenScalarIf(LegalityPredicate Predicate,
+                                                LegalizeMutation Mutation) {
+  return actionIf(LegalizationAction::WidenScalar, std::move(Predicate), std::move(Mutation));
+}
+
+LegalizeRuleSet &LegalizeRuleSet::narrowScalarIf(LegalityPredicate Predicate,
+                                                 LegalizeMutation Mutation) {
+  return actionIf(LegalizationAction::NarrowScalar, std::move(Predicate), std::move(Mutation));
+}
+
+LegalizeRuleSet &LegalizeRuleSet::moreElementsIf(LegalityPredicate Predicate,
+                                                 LegalizeMutation Mutation) {
+  return actionIf(LegalizationAction::MoreElements, std::move(Predicate), std::move(Mutation));
+}
+
+LegalizeRuleSet &LegalizeRuleSet::fewerElementsIf(LegalityPredicate Predicate,
+                                                  LegalizeMutation Mutation) {
+  return actionIf(LegalizationAction::FewerElements, std::move(Predicate), std::move(Mutation));
+}
+
+LegalizeRuleSet &LegalizeRuleSet::bitcastIf(LegalityPredicate Predicate,
+                                            LegalizeMutation Mutation) {
+  return actionIf(LegalizationAction::Bitcast, std::move(Predicate), std::move(Mutation));
+}
+
+LegalizeRuleSet &LegalizeRuleSet::legalFor(std::initializer_list<LowLevelType> Types) {
+  return actionFor(LegalizationAction::Legal, Types);
+}
+
+LegalizeRuleSet &LegalizeRuleSet::legalFor(bool Enabled,
+                                           std::initializer_list<LowLevelType> Types) {
+  return Enabled ? legalFor(Types) : *this;
+}
+
+LegalizeRuleSet &
+LegalizeRuleSet::legalFor(std::initializer_list<std::pair<LowLevelType, LowLevelType>> Types) {
+  return actionFor(LegalizationAction::Legal, Types);
+}
+
+LegalizeRuleSet &
+LegalizeRuleSet::legalFor(bool Enabled,
+                          std::initializer_list<std::pair<LowLevelType, LowLevelType>> Types) {
+  return Enabled ? legalFor(Types) : *this;
+}
+
+LegalizeRuleSet &LegalizeRuleSet::legalFor(
+    std::initializer_list<std::tuple<LowLevelType, LowLevelType, LowLevelType>> Types) {
+  return actionFor(LegalizationAction::Legal, Types);
+}
+
+LegalizeRuleSet &LegalizeRuleSet::customFor(std::initializer_list<LowLevelType> Types) {
+  return actionFor(LegalizationAction::Custom, Types);
+}
+
+LegalizeRuleSet &LegalizeRuleSet::customFor(bool Enabled,
+                                            std::initializer_list<LowLevelType> Types) {
+  return Enabled ? customFor(Types) : *this;
+}
+
+LegalizeRuleSet &
+LegalizeRuleSet::customFor(std::initializer_list<std::pair<LowLevelType, LowLevelType>> Types) {
+  return actionFor(LegalizationAction::Custom, Types);
+}
+
+LegalizeRuleSet &
+LegalizeRuleSet::customFor(bool Enabled,
+                           std::initializer_list<std::pair<LowLevelType, LowLevelType>> Types) {
+  return Enabled ? customFor(Types) : *this;
+}
+
+LegalizeRuleSet &LegalizeRuleSet::lowerFor(std::initializer_list<LowLevelType> Types) {
+  return actionFor(LegalizationAction::Lower, Types);
+}
+
+LegalizeRuleSet &
+LegalizeRuleSet::lowerFor(std::initializer_list<std::pair<LowLevelType, LowLevelType>> Types) {
+  return actionFor(LegalizationAction::Lower, Types);
+}
+
+LegalizeRuleSet &LegalizeRuleSet::libcallFor(std::initializer_list<LowLevelType> Types) {
+  return actionFor(LegalizationAction::Libcall, Types);
+}
+
+LegalizeRuleSet &LegalizeRuleSet::libcallFor(bool Enabled,
+                                             std::initializer_list<LowLevelType> Types) {
+  return Enabled ? libcallFor(Types) : *this;
+}
+
+LegalizeRuleSet &
+LegalizeRuleSet::libcallFor(std::initializer_list<std::pair<LowLevelType, LowLevelType>> Types) {
+  return actionFor(LegalizationAction::Libcall, Types);
+}
+
+LegalizeRuleSet &
+LegalizeRuleSet::libcallFor(bool Enabled,
+                            std::initializer_list<std::pair<LowLevelType, LowLevelType>> Types) {
+  return Enabled ? libcallFor(Types) : *this;
+}
+
+LegalizeRuleSet &
+LegalizeRuleSet::legalForTypesWithMemDesc(std::initializer_list<LegalizeMemoryRule> MemoryRules) {
+  const std::vector<LegalizeMemoryRule> MemoryRuleList(MemoryRules);
+  return legalIf([MemoryRuleList](const LegalizationQuery &Query) {
+    return std::ranges::any_of(MemoryRuleList, [&Query](const LegalizeMemoryRule &Rule) {
+      return memoryRuleMatches(Query, Rule);
+    });
+  });
+}
+
+LegalizeRuleSet &LegalizeRuleSet::widenScalarToNextPow2(std::size_t TypeIndex,
+                                                        std::uint32_t MinimumBitWidth) {
+  return widenScalarIf(
+      [TypeIndex, MinimumBitWidth](const LegalizationQuery &Query) {
+        if (TypeIndex >= Query.Types.size() || !Query.Types[TypeIndex].isCategoryNeutralScalar())
+          return false;
+        const std::uint32_t Width = Query.Types[TypeIndex].scalarBitWidth();
+        return nextPowerOfTwo(Width, MinimumBitWidth) > Width;
+      },
+      [TypeIndex, MinimumBitWidth](const LegalizationQuery &Query) {
+        return std::pair{TypeIndex, scalarType(nextPowerOfTwo(
+                                        Query.Types[TypeIndex].scalarBitWidth(), MinimumBitWidth))};
+      });
+}
+
+LegalizeRuleSet &LegalizeRuleSet::minScalar(std::size_t TypeIndex, LowLevelType MinimumType) {
+  return widenScalarIf(
+      [TypeIndex, MinimumType](const LegalizationQuery &Query) {
+        return TypeIndex < Query.Types.size() && Query.Types[TypeIndex].isCategoryNeutralScalar() &&
+               Query.Types[TypeIndex].scalarBitWidth() < MinimumType.scalarBitWidth();
+      },
+      [TypeIndex, MinimumType](const LegalizationQuery &) {
+        return std::pair{TypeIndex, MinimumType};
+      });
+}
+
+LegalizeRuleSet &LegalizeRuleSet::minScalar(bool Enabled, std::size_t TypeIndex,
+                                            LowLevelType MinimumType) {
+  return Enabled ? minScalar(TypeIndex, MinimumType) : *this;
+}
+
+LegalizeRuleSet &LegalizeRuleSet::maxScalar(std::size_t TypeIndex, LowLevelType MaximumType) {
+  return narrowScalarIf(
+      [TypeIndex, MaximumType](const LegalizationQuery &Query) {
+        return TypeIndex < Query.Types.size() && Query.Types[TypeIndex].isCategoryNeutralScalar() &&
+               Query.Types[TypeIndex].scalarBitWidth() > MaximumType.scalarBitWidth();
+      },
+      [TypeIndex, MaximumType](const LegalizationQuery &) {
+        return std::pair{TypeIndex, MaximumType};
+      });
+}
+
+LegalizeRuleSet &LegalizeRuleSet::maxScalar(bool Enabled, std::size_t TypeIndex,
+                                            LowLevelType MaximumType) {
+  return Enabled ? maxScalar(TypeIndex, MaximumType) : *this;
+}
+
+LegalizeRuleSet &LegalizeRuleSet::clampScalar(std::size_t TypeIndex, LowLevelType MinimumType,
+                                              LowLevelType MaximumType) {
+  return minScalar(TypeIndex, MinimumType).maxScalar(TypeIndex, MaximumType);
+}
+
+LegalizeRuleSet &LegalizeRuleSet::scalarSameSizeAs(std::size_t TypeIndex,
+                                                   std::size_t ReferenceTypeIndex) {
+  const auto changeToReference = [TypeIndex, ReferenceTypeIndex](const LegalizationQuery &Query) {
+    return std::pair{TypeIndex, scalarType(Query.Types[ReferenceTypeIndex].scalarBitWidth())};
+  };
+  widenScalarIf(
+      [TypeIndex, ReferenceTypeIndex](const LegalizationQuery &Query) {
+        return TypeIndex < Query.Types.size() && ReferenceTypeIndex < Query.Types.size() &&
+               Query.Types[TypeIndex].isCategoryNeutralScalar() &&
+               Query.Types[ReferenceTypeIndex].isCategoryNeutralScalar() &&
+               Query.Types[TypeIndex].scalarBitWidth() <
+                   Query.Types[ReferenceTypeIndex].scalarBitWidth();
+      },
+      changeToReference);
+  return narrowScalarIf(
+      [TypeIndex, ReferenceTypeIndex](const LegalizationQuery &Query) {
+        return TypeIndex < Query.Types.size() && ReferenceTypeIndex < Query.Types.size() &&
+               Query.Types[TypeIndex].isCategoryNeutralScalar() &&
+               Query.Types[ReferenceTypeIndex].isCategoryNeutralScalar() &&
+               Query.Types[TypeIndex].scalarBitWidth() >
+                   Query.Types[ReferenceTypeIndex].scalarBitWidth();
+      },
+      changeToReference);
+}
+
+LegalizeRuleSet &LegalizeRuleSet::lowerIfMemSizeNotByteSizePow2(std::size_t MemoryIndex) {
+  return lowerIf([MemoryIndex](const LegalizationQuery &Query) {
+    if (MemoryIndex >= Query.MemoryOperands.size())
+      return false;
+    const MemorySize Size = Query.MemoryOperands[MemoryIndex].Size;
+    return !Size.isKnown() || Size.isScalable() || !std::has_single_bit(Size.minimumBytes());
+  });
+}
+
+LegalizeRuleSet &LegalizeRuleSet::alwaysLegal() {
+  return legalIf([](const LegalizationQuery &) { return true; });
+}
+
+LegalizeRuleSet &LegalizeRuleSet::lower() {
+  return lowerIf([](const LegalizationQuery &) { return true; });
+}
+
+LegalizeRuleSet &LegalizeRuleSet::libcall() {
+  return libcallIf([](const LegalizationQuery &) { return true; });
+}
+
+std::optional<LegalizationDecision> LegalizeRuleSet::apply(const LegalizationQuery &Query) const {
+  for (const LegalizeRule &Rule : Rules) {
+    if (Rule.matches(Query))
+      return Rule.apply(Query);
+  }
+  return std::nullopt;
+}
+
+LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(Opcode InstructionOpcode) {
+  return RuleSets[InstructionOpcode];
+}
+
+LegalizeRuleSet &
+LegalizerInfo::getActionDefinitionsBuilder(std::initializer_list<Opcode> InstructionOpcodes) {
+  const Opcode Representative = *InstructionOpcodes.begin();
+  for (const Opcode InstructionOpcode : InstructionOpcodes) {
+    if (InstructionOpcode != Representative)
+      RuleAliases.emplace(InstructionOpcode, Representative);
+  }
+  return getActionDefinitionsBuilder(Representative);
+}
+
+Expected<LegalizationQuery> LegalizerInfo::buildQuery(const MachineInstr &Instruction,
+                                                      const MachineFunction &Function,
+                                                      const TargetDescription &Target) {
+  const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode());
+  if (Descriptor == nullptr)
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "legalization query requires a registered instruction opcode");
+
+  std::size_t ExplicitCount = 0;
+  while (ExplicitCount < Instruction.operandCount() &&
+         !Instruction.operandAt(ExplicitCount)->isImplicit()) {
+    ++ExplicitCount;
+  }
+  auto OperandDescriptors = resolveExplicitOperandDescriptors(*Descriptor, ExplicitCount);
+  if (!OperandDescriptors)
+    return std::unexpected(OperandDescriptors.error());
+
+  std::size_t TypeCount = 0;
+  for (const OperandDescriptor *Operand : *OperandDescriptors) {
+    if (Operand->TypeConstraint && Operand->TypeConstraint->EqualityGroup) {
+      TypeCount = std::max(TypeCount,
+                           static_cast<std::size_t>(*Operand->TypeConstraint->EqualityGroup) + 1U);
+    }
+  }
+
+  std::vector<std::optional<LowLevelType>> OptionalTypes(TypeCount);
+  std::vector<std::vector<std::size_t>> TypeOperands(TypeCount);
+  for (std::size_t Index = 0; Index < ExplicitCount; ++Index) {
+    const OperandDescriptor &OperandDescriptor = *(*OperandDescriptors)[Index];
+    if (!OperandDescriptor.TypeConstraint || !OperandDescriptor.TypeConstraint->EqualityGroup) {
+      continue;
+    }
+    const std::size_t TypeIndex = *OperandDescriptor.TypeConstraint->EqualityGroup;
+    const Register *Reg = Instruction.operandAt(Index)->getIf<Register>();
+    if (Reg == nullptr || !Reg->isVirtual())
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "legalization type operand must name a virtual register");
+    auto Info = Function.registerInfo().virtualRegisterInfo(*Reg);
+    if (!Info)
+      return std::unexpected(Info.error());
+    if (!Info->get().Type)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "legalization type operand has no LowLevelType");
+    if (OptionalTypes[TypeIndex] && *OptionalTypes[TypeIndex] != *Info->get().Type)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "legalization type operands disagree within one type index");
+    OptionalTypes[TypeIndex] = *Info->get().Type;
+    TypeOperands[TypeIndex].push_back(Index);
+  }
+
+  std::vector<LowLevelType> Types;
+  Types.reserve(TypeCount);
+  for (const std::optional<LowLevelType> &Type : OptionalTypes) {
+    if (!Type)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "legalization query contains a sparse type index");
+    Types.push_back(*Type);
+  }
+
+  std::vector<LegalizationMemoryDesc> MemoryOperands;
+  MemoryOperands.reserve(Instruction.memOperands().size());
+  for (const MachineMemOperand *Memory : Instruction.memOperands()) {
+    const MachineMemOperandDesc &Description = Memory->description();
+    MemoryOperands.push_back({Description.MemoryType, Description.Size,
+                              Description.Align.bytes() * 8U, Description.AddressSpace,
+                              Description.AtomicKind, Description.SuccessOrdering,
+                              Description.FailureOrdering, Description.SyncScope});
+  }
+
+  LegalizationQuery Query(Instruction.opcode(), std::move(Types), std::move(MemoryOperands));
+  Query.TypeOperands = std::move(TypeOperands);
+  return Query;
+}
+
+Expected<LegalizationDecision> LegalizerInfo::getDecision(const MachineInstr &Instruction,
+                                                          const MachineFunction &Function,
+                                                          const TargetDescription &Target) const {
+  auto Query = buildQuery(Instruction, Function, Target);
+  if (!Query)
+    return std::unexpected(Query.error());
+  return getDecision(*Query);
+}
+
+Expected<LegalizationDecision> LegalizerInfo::getDecision(const LegalizationQuery &Query) const {
+  if (!isGenericOpcode(Query.InstructionOpcode))
+    return LegalizationDecision{.Action = LegalizationAction::Legal, .TypeIndex = 0, .NewType = {}};
+
+  Opcode RuleOpcode = Query.InstructionOpcode;
+  if (const auto Alias = RuleAliases.find(RuleOpcode); Alias != RuleAliases.end())
+    RuleOpcode = Alias->second;
+  const auto RuleSet = RuleSets.find(RuleOpcode);
+  if (RuleSet == RuleSets.end())
+    return LegalizationDecision{
+        .Action = LegalizationAction::Unsupported, .TypeIndex = 0, .NewType = {}};
+  const std::optional<LegalizationDecision> Decision = RuleSet->second.apply(Query);
+  return Decision.value_or(LegalizationDecision{
+      .Action = LegalizationAction::Unsupported, .TypeIndex = 0, .NewType = {}});
+}
+
+Expected<bool> LegalizerInfo::isLegal(const LegalizationQuery &Query) const {
+  auto Decision = getDecision(Query);
+  if (!Decision)
+    return std::unexpected(Decision.error());
+  return Decision->Action == LegalizationAction::Legal;
+}
+
+Expected<bool> LegalizerInfo::isUnsupported(const LegalizationQuery &Query) const {
+  auto Decision = getDecision(Query);
+  if (!Decision)
+    return std::unexpected(Decision.error());
+  return Decision->Action == LegalizationAction::Unsupported;
+}
+
+} // namespace rcc