[RISCV][GlobalISel] Generate shift selections

12 files changed, 1048 insertions, 185 deletions

diff --git a/backend/include/rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h b/backend/include/rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h
index afd0d70..fbbf68f 100644
--- a/backend/include/rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h
+++ b/backend/include/rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h
@@ -4,11 +4,14 @@
 #define RCC_CODEGEN_GLOBALISEL_GIMATCHTABLEEXECUTOR_H
 
 #include "rcc/CodeGen/MachineIRTypes.h"
+#include "rcc/CodeGen/MachineOperand.h"
 #include "rcc/Support/Error.h"
 
 #include <cstdint>
+#include <optional>
 #include <span>
 #include <string_view>
+#include <vector>
 
 namespace rcc {
 
@@ -35,10 +38,15 @@ enum class GIMatchTableOpcode : std::uint8_t {
   CheckOperandClass,
   CheckIntegerPredicate,
   CheckOperandDefConstantRanges,
+  CheckOperandDefOpcode,
+  CheckOperandDefOperandConstantRanges,
+  CaptureDefOperand,
   CreateTemporary,
   MutateOpcode,
   BuildInstruction,
   RenderOperand,
+  RenderComplexOperand,
+  RenderCapturedOperand,
   RenderPhysicalRegister,
   RenderTemporary,
   RenderCapturedImmediate,
@@ -53,6 +61,18 @@ struct GIMatchTableInstruction final {
   std::uint32_t Value = 0;
   std::uint32_t Auxiliary = 0;
   std::int64_t Immediate = 0;
+  std::string_view Symbol;
+};
+
+struct GIMatchComplexInstruction final {
+  Opcode ResultOpcode;
+  LowLevelType ResultType;
+  std::vector<MachineOperand> Operands;
+};
+
+struct GIMatchComplexOperand final {
+  std::optional<MachineOperand> Operand;
+  std::optional<GIMatchComplexInstruction> Instruction;
 };
 
 struct GIMatchTableConstantRange final {
@@ -88,6 +108,11 @@ public:
                                       const TargetDescription &Target) const;
 
 protected:
+  [[nodiscard]] virtual Expected<std::optional<GIMatchComplexOperand>>
+  renderComplexOperand(std::string_view Name, const MachineInstr &Instruction,
+                       const MachineFunction &Function, const TargetDescription &Target,
+                       std::uint32_t OperandIndex) const;
+
   [[nodiscard]] virtual Expected<void>
   finalizeGeneratedInstruction(MachineInstr &Output, MachineFunction &Function,
                                const TargetDescription &Target, MachineInstrFlags InputFlags,
diff --git a/backend/include/rcc/CodeGen/GlobalISel/GISelValueTracking.h b/backend/include/rcc/CodeGen/GlobalISel/GISelValueTracking.h
index aa02fe3..e51f8c1 100644
--- a/backend/include/rcc/CodeGen/GlobalISel/GISelValueTracking.h
+++ b/backend/include/rcc/CodeGen/GlobalISel/GISelValueTracking.h
@@ -18,7 +18,7 @@ class TargetDescription;
 
 class GISelValueTracking final : public GISelChangeObserver {
 public:
-  GISelValueTracking(MachineFunction &Function, const TargetDescription &Target,
+  GISelValueTracking(const MachineFunction &Function, const TargetDescription &Target,
                      unsigned MaxDepth = 6) noexcept;
 
   [[nodiscard]] const MachineFunction &getMachineFunction() const noexcept {
@@ -42,8 +42,8 @@ private:
   [[nodiscard]] Expected<KnownBits> makeUnknown(std::uint32_t BitWidth) const;
   [[nodiscard]] Expected<KnownBits> getKnownBits(Register Reg, unsigned Depth = 0) const;
 
-  MachineFunction &Function;
-  MachineRegisterInfo &MRI;
+  const MachineFunction &Function;
+  const MachineRegisterInfo &MRI;
   const TargetDescription &Target;
   unsigned MaxDepth;
 };
diff --git a/backend/include/rcc/TableGen/Record.h b/backend/include/rcc/TableGen/Record.h
index 57e5832..6575b82 100644
--- a/backend/include/rcc/TableGen/Record.h
+++ b/backend/include/rcc/TableGen/Record.h
@@ -247,6 +247,20 @@ struct SourceSelectionOperandDefConstantPredicate final {
   TextRange Range;
 };
 
+struct SourceSelectionDefUseCapture final {
+  std::string Symbol;
+  std::uint32_t OperandIndex = 0;
+  TextRange Range;
+};
+
+struct SourceSelectionDefUsePredicate final {
+  std::uint32_t RootOperandIndex = 0;
+  std::string OpcodeSymbol;
+  std::vector<SourceSelectionDefUseCapture> Captures;
+  std::vector<SourceSelectionOperandDefConstantPredicate> OperandDefConstants;
+  TextRange Range;
+};
+
 struct SourceSelectionTemporary final {
   std::string Symbol;
   std::uint32_t TypeFromOperand = 0;
@@ -255,8 +269,11 @@ struct SourceSelectionTemporary final {
 
 struct SourceSelectionOperandRenderer final {
   std::optional<std::uint32_t> OperandIndex;
+  std::optional<std::uint32_t> ComplexOperandIndex;
   std::string PhysicalRegisterSymbol;
+  std::string ComplexRendererSymbol;
   std::string TemporarySymbol;
+  std::string CapturedOperandSymbol;
   std::optional<std::uint32_t> CapturedImmediateOperand;
   std::optional<std::int64_t> Immediate;
   std::string ImmediateTransform;
@@ -281,6 +298,7 @@ struct SourceSelectionRule final {
   std::vector<SourceSelectionOperandBankPredicate> OperandBanks;
   std::vector<SourceSelectionOperandClassPredicate> OperandClasses;
   std::vector<SourceSelectionOperandDefConstantPredicate> OperandDefConstants;
+  std::vector<SourceSelectionDefUsePredicate> DefUsePredicates;
   std::vector<SourceSelectionTemporary> Temporaries;
   std::vector<SourceSelectionAction> Actions;
   std::vector<std::uint32_t> EraseOperandDefinitions;
diff --git a/backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp b/backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp
index 7f7cb63..97b6cfe 100644
--- a/backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp
+++ b/backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp
@@ -105,6 +105,20 @@ namespace {
   return Integer != nullptr && static_cast<std::uint32_t>(*Integer) == Step.Value;
 }
 
+[[nodiscard]] std::optional<std::int64_t> immediateValue(const MachineOperand &Operand) {
+  if (const std::int64_t *Immediate = Operand.getIf<std::int64_t>())
+    return *Immediate;
+  const auto *Integer = Operand.getIf<IntegerImmediateOperand>();
+  if (Integer == nullptr)
+    return std::optional<std::int64_t>{};
+  const std::string Text = Integer->Value.toSignedDecimal();
+  std::int64_t Parsed = 0;
+  const auto [End, Error] = std::from_chars(Text.data(), Text.data() + Text.size(), Parsed);
+  if (Error != std::errc{} || End != Text.data() + Text.size())
+    return std::optional<std::int64_t>{};
+  return Parsed;
+}
+
 [[nodiscard]] Expected<std::optional<std::int64_t>>
 operandDefConstantValue(const MachineInstr &Instruction, const MachineFunction &Function,
                         std::size_t OperandIndex) {
@@ -118,23 +132,24 @@ operandDefConstantValue(const MachineInstr &Instruction, const MachineFunction &
   const MachineOperand *Value = Definition->operandAt(1);
   if (Value == nullptr)
     return std::optional<std::int64_t>{};
-  if (const std::int64_t *Immediate = Value->getIf<std::int64_t>())
-    return *Immediate;
-  const auto *Integer = Value->getIf<IntegerImmediateOperand>();
-  if (Integer == nullptr)
-    return std::optional<std::int64_t>{};
-  const std::string Text = Integer->Value.toSignedDecimal();
-  std::int64_t Parsed = 0;
-  const auto [End, Error] = std::from_chars(Text.data(), Text.data() + Text.size(), Parsed);
-  if (Error != std::errc{} || End != Text.data() + Text.size())
+  return immediateValue(*Value);
+}
+
+[[nodiscard]] Expected<std::optional<std::int64_t>>
+operandOrDefConstantValue(const MachineInstr &Instruction, const MachineFunction &Function,
+                          std::size_t OperandIndex) {
+  const MachineOperand *Operand = Instruction.operandAt(OperandIndex);
+  if (Operand == nullptr)
     return std::optional<std::int64_t>{};
-  return Parsed;
+  if (const auto Value = immediateValue(*Operand))
+    return Value;
+  return operandDefConstantValue(Instruction, Function, OperandIndex);
 }
 
-[[nodiscard]] Expected<bool>
-matchesOperandDefConstantRanges(const GIMatchTable &Table, const MachineInstr &Instruction,
-                                const MachineFunction &Function,
-                                const GIMatchTableInstruction &Step) {
+[[nodiscard]] Expected<bool> matchesOperandDefConstantRanges(const GIMatchTable &Table,
+                                                             const MachineInstr &Instruction,
+                                                             const MachineFunction &Function,
+                                                             const GIMatchTableInstruction &Step) {
   const std::size_t First = Step.Value;
   const std::size_t Count = Step.Auxiliary;
   if (Count == 0 || First > Table.ConstantRanges.size() ||
@@ -159,6 +174,59 @@ matchesOperandDefConstantRanges(const GIMatchTable &Table, const MachineInstr &I
   return false;
 }
 
+[[nodiscard]] const MachineInstr *operandDefinition(const MachineInstr &Instruction,
+                                                    const MachineFunction &Function,
+                                                    std::size_t OperandIndex) {
+  const MachineOperand *Operand = Instruction.operandAt(OperandIndex);
+  const Register *Reg = Operand == nullptr ? nullptr : Operand->getIf<Register>();
+  return Reg != nullptr && Reg->isVirtual() ? Function.registerInfo().getVRegDef(*Reg) : nullptr;
+}
+
+[[nodiscard]] Expected<bool> matchesOperandDefOpcode(const MachineInstr &Instruction,
+                                                     const MachineFunction &Function,
+                                                     const GIMatchTableInstruction &Step) {
+  if (Step.Value == 0)
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "generated match table has an invalid def-use opcode");
+  const MachineInstr *Definition = operandDefinition(Instruction, Function, Step.OperandIndex);
+  return Definition != nullptr && Definition->opcode().value() == Step.Value;
+}
+
+[[nodiscard]] Expected<bool>
+matchesOperandDefOperandConstantRanges(const GIMatchTable &Table, const MachineInstr &Instruction,
+                                       const MachineFunction &Function,
+                                       const GIMatchTableInstruction &Step) {
+  if (Step.Immediate <= 0 ||
+      static_cast<std::uint64_t>(Step.Immediate) > std::numeric_limits<std::uint32_t>::max()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "generated match table has an invalid def-use constant range count");
+  }
+  const std::size_t First = Step.Value;
+  const std::size_t Count = static_cast<std::size_t>(Step.Immediate);
+  if (First > Table.ConstantRanges.size() || Count > Table.ConstantRanges.size() - First) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "generated match table has an invalid def-use constant range");
+  }
+  const MachineInstr *Definition = operandDefinition(Instruction, Function, Step.OperandIndex);
+  if (Definition == nullptr)
+    return false;
+  auto Value = operandOrDefConstantValue(*Definition, Function, Step.Auxiliary);
+  if (!Value)
+    return std::unexpected(Value.error());
+  if (!*Value)
+    return false;
+  for (std::size_t Index = First; Index < First + Count; ++Index) {
+    const GIMatchTableConstantRange &Range = Table.ConstantRanges[Index];
+    if (Range.Minimum > Range.Maximum) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "generated match table has an inverted def-use constant range");
+    }
+    if (**Value >= Range.Minimum && **Value <= Range.Maximum)
+      return true;
+  }
+  return false;
+}
+
 [[nodiscard]] Expected<RegisterOperandFlags> registerFlagsFromRaw(std::uint32_t Raw) {
   constexpr std::uint32_t ValidBits =
       (std::uint32_t{1} << static_cast<std::uint16_t>(RegisterOperandFlag::Count)) - 1U;
@@ -176,6 +244,11 @@ matchesOperandDefConstantRanges(const GIMatchTable &Table, const MachineInstr &I
 }
 
 struct MatchedRule final {
+  struct CapturedOperand final {
+    std::uint32_t ID = 0;
+    MachineOperand Operand;
+  };
+
   struct Temporary final {
     std::uint32_t ID = 0;
     std::uint32_t TypeFromOperand = 0;
@@ -184,6 +257,8 @@ struct MatchedRule final {
   struct RenderedOperand final {
     enum class Kind : std::uint8_t {
       RootOperand,
+      ComplexOperand,
+      CapturedOperand,
       PhysicalRegister,
       Temporary,
       CapturedImmediate,
@@ -193,6 +268,7 @@ struct MatchedRule final {
     Kind SourceKind = Kind::RootOperand;
     std::uint32_t Value = 0;
     std::uint32_t Flags = 0;
+    std::string_view ComplexRenderer;
     GIMatchImmediateTransform Transform = GIMatchImmediateTransform::Identity;
     std::int64_t Immediate = 0;
   };
@@ -204,15 +280,27 @@ struct MatchedRule final {
   };
 
   std::vector<Temporary> Temporaries;
+  std::vector<CapturedOperand> CapturedOperands;
   std::vector<Instruction> Instructions;
   std::vector<Register> EraseOperandDefinitions;
 };
 
 [[nodiscard]] bool hasTemporary(const MatchedRule &Rule, std::uint32_t ID) {
-  return std::ranges::any_of(Rule.Temporaries,
-                             [ID](const MatchedRule::Temporary &Temporary) {
-                               return Temporary.ID == ID;
-                             });
+  return std::ranges::any_of(Rule.Temporaries, [ID](const MatchedRule::Temporary &Temporary) {
+    return Temporary.ID == ID;
+  });
+}
+
+[[nodiscard]] bool hasCapturedOperand(const MatchedRule &Rule, std::uint32_t ID) {
+  return std::ranges::any_of(
+      Rule.CapturedOperands,
+      [ID](const MatchedRule::CapturedOperand &Capture) { return Capture.ID == ID; });
+}
+
+[[nodiscard]] const MatchedRule::CapturedOperand *
+findCapturedOperand(const std::vector<MatchedRule::CapturedOperand> &Captures, std::uint32_t ID) {
+  const auto Position = std::ranges::find(Captures, ID, &MatchedRule::CapturedOperand::ID);
+  return Position == Captures.end() ? nullptr : &*Position;
 }
 
 [[nodiscard]] Expected<std::optional<MatchedRule>> matchRule(const GIMatchTable &Table,
@@ -300,6 +388,46 @@ struct MatchedRule final {
         return std::optional<MatchedRule>{};
       break;
     }
+    case GIMatchTableOpcode::CheckOperandDefOpcode: {
+      if (Applying) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "generated match table performs a predicate after an action");
+      }
+      auto Matched = matchesOperandDefOpcode(Instruction, Function, Step);
+      if (!Matched)
+        return std::unexpected(Matched.error());
+      if (!*Matched)
+        return std::optional<MatchedRule>{};
+      break;
+    }
+    case GIMatchTableOpcode::CheckOperandDefOperandConstantRanges: {
+      if (Applying) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "generated match table performs a predicate after an action");
+      }
+      auto Matched = matchesOperandDefOperandConstantRanges(Table, Instruction, Function, Step);
+      if (!Matched)
+        return std::unexpected(Matched.error());
+      if (!*Matched)
+        return std::optional<MatchedRule>{};
+      break;
+    }
+    case GIMatchTableOpcode::CaptureDefOperand: {
+      if (Applying || Complete || Step.Value == 0 || hasCapturedOperand(Result, Step.Value)) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "generated match table has an invalid def-use capture");
+      }
+      const MachineInstr *Definition = operandDefinition(Instruction, Function, Step.OperandIndex);
+      const MachineOperand *Operand =
+          Definition == nullptr ? nullptr : Definition->operandAt(Step.Auxiliary);
+      if (Operand == nullptr || Operand->isImplicit())
+        return std::optional<MatchedRule>{};
+      Result.CapturedOperands.push_back({
+          .ID = Step.Value,
+          .Operand = Operand->cloneDetached(),
+      });
+      break;
+    }
     case GIMatchTableOpcode::CreateTemporary: {
       if (Complete || Step.Value == 0 || hasTemporary(Result, Step.Value)) {
         return makeUnexpected(ErrorCode::VerificationError,
@@ -353,6 +481,32 @@ struct MatchedRule final {
       Result.Instructions.back().Operands.push_back({
           .SourceKind = MatchedRule::RenderedOperand::Kind::RootOperand,
           .Value = Step.OperandIndex,
+          .ComplexRenderer = {},
+      });
+      break;
+    case GIMatchTableOpcode::RenderComplexOperand:
+      if (Complete || Result.Instructions.empty() || Step.Symbol.empty() ||
+          Instruction.operandAt(Step.OperandIndex) == nullptr ||
+          Instruction.operandAt(Step.OperandIndex)->isImplicit()) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "generated match table has an invalid complex operand renderer");
+      }
+      Result.Instructions.back().Operands.push_back({
+          .SourceKind = MatchedRule::RenderedOperand::Kind::ComplexOperand,
+          .Value = Step.OperandIndex,
+          .ComplexRenderer = Step.Symbol,
+      });
+      break;
+    case GIMatchTableOpcode::RenderCapturedOperand:
+      if (Complete || Result.Instructions.empty() || Step.Value == 0 ||
+          !hasCapturedOperand(Result, Step.Value)) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "generated match table has an invalid captured operand renderer");
+      }
+      Result.Instructions.back().Operands.push_back({
+          .SourceKind = MatchedRule::RenderedOperand::Kind::CapturedOperand,
+          .Value = Step.Value,
+          .ComplexRenderer = {},
       });
       break;
     case GIMatchTableOpcode::RenderPhysicalRegister:
@@ -364,6 +518,7 @@ struct MatchedRule final {
           .SourceKind = MatchedRule::RenderedOperand::Kind::PhysicalRegister,
           .Value = Step.Value,
           .Flags = Step.Auxiliary,
+          .ComplexRenderer = {},
       });
       break;
     case GIMatchTableOpcode::RenderTemporary:
@@ -375,6 +530,7 @@ struct MatchedRule final {
           .SourceKind = MatchedRule::RenderedOperand::Kind::Temporary,
           .Value = Step.Value,
           .Flags = Step.Auxiliary,
+          .ComplexRenderer = {},
       });
       break;
     case GIMatchTableOpcode::RenderCapturedImmediate: {
@@ -393,6 +549,7 @@ struct MatchedRule final {
       Result.Instructions.back().Operands.push_back({
           .SourceKind = MatchedRule::RenderedOperand::Kind::CapturedImmediate,
           .Value = Step.OperandIndex,
+          .ComplexRenderer = {},
           .Transform = static_cast<GIMatchImmediateTransform>(Step.Value),
       });
       break;
@@ -404,6 +561,7 @@ struct MatchedRule final {
       }
       Result.Instructions.back().Operands.push_back({
           .SourceKind = MatchedRule::RenderedOperand::Kind::Immediate,
+          .ComplexRenderer = {},
           .Immediate = Step.Immediate,
       });
       break;
@@ -438,6 +596,26 @@ struct MatchedRule final {
   return std::optional<MatchedRule>(std::move(Result));
 }
 
+template <typename ComplexRenderer>
+[[nodiscard]] Expected<bool>
+complexRenderersMatch(const MatchedRule &Rule, const MachineInstr &Instruction,
+                      const MachineFunction &Function, const TargetDescription &Target,
+                      ComplexRenderer &&RenderComplex) {
+  for (const MatchedRule::Instruction &Action : Rule.Instructions) {
+    for (const MatchedRule::RenderedOperand &Rendered : Action.Operands) {
+      if (Rendered.SourceKind != MatchedRule::RenderedOperand::Kind::ComplexOperand)
+        continue;
+      auto Complex =
+          RenderComplex(Rendered.ComplexRenderer, Instruction, Function, Target, Rendered.Value);
+      if (!Complex)
+        return std::unexpected(Complex.error());
+      if (!*Complex)
+        return false;
+    }
+  }
+  return true;
+}
+
 [[nodiscard]] std::size_t explicitOperandCount(const MachineInstr &Instruction) noexcept {
   std::size_t Count = 0;
   while (Count < Instruction.operandCount() && !Instruction.operandAt(Count)->isImplicit())
@@ -483,8 +661,7 @@ struct RegisterConstraintSnapshot final {
 
 [[nodiscard]] const MaterializedTemporary *
 findTemporary(const std::vector<MaterializedTemporary> &Temporaries, std::uint32_t ID) {
-  const auto Position =
-      std::ranges::find(Temporaries, ID, &MaterializedTemporary::ID);
+  const auto Position = std::ranges::find(Temporaries, ID, &MaterializedTemporary::ID);
   return Position == Temporaries.end() ? nullptr : &*Position;
 }
 
@@ -501,6 +678,18 @@ eraseTemporaries(MachineRegisterInfo &Registers,
   return {};
 }
 
+[[nodiscard]] Expected<void> eraseRegisters(MachineRegisterInfo &Registers,
+                                            const std::vector<Register> &RegistersToErase) {
+  for (auto Iterator = RegistersToErase.rbegin(); Iterator != RegistersToErase.rend(); ++Iterator) {
+    if (!Registers.isKnownVirtualRegister(*Iterator))
+      continue;
+    auto Erased = Registers.eraseVirtualRegister(*Iterator);
+    if (!Erased)
+      return std::unexpected(Erased.error());
+  }
+  return {};
+}
+
 [[nodiscard]] Expected<void>
 restoreRegisterConstraints(MachineRegisterInfo &Registers,
                            const std::vector<RegisterConstraintSnapshot> &Snapshots) {
@@ -531,8 +720,8 @@ restoreRegisterConstraints(MachineRegisterInfo &Registers,
 
 [[nodiscard]] Expected<void>
 constrainRenderedInstruction(const InstructionDescriptor &Descriptor,
-                             std::span<const MachineOperand> Operands,
-                             MachineFunction &Function, const TargetDescription &Target,
+                             std::span<const MachineOperand> Operands, MachineFunction &Function,
+                             const TargetDescription &Target,
                              std::vector<RegisterConstraintSnapshot> &Snapshots) {
   if (Descriptor.Operands.empty() && !Operands.empty()) {
     return makeUnexpected(ErrorCode::VerificationError,
@@ -550,8 +739,9 @@ constrainRenderedInstruction(const InstructionDescriptor &Descriptor,
     if (Reg == nullptr || !Reg->isVirtual())
       continue;
 
-    const OperandDescriptor &OperandDescriptor =
-        Index < Descriptor.Operands.size() ? Descriptor.Operands[Index] : Descriptor.Operands.back();
+    const OperandDescriptor &OperandDescriptor = Index < Descriptor.Operands.size()
+                                                     ? Descriptor.Operands[Index]
+                                                     : Descriptor.Operands.back();
     if (!OperandDescriptor.RegBank && !OperandDescriptor.RegClass)
       continue;
 
@@ -591,6 +781,7 @@ constrainRenderedInstruction(const InstructionDescriptor &Descriptor,
 renderOperand(const MatchedRule::RenderedOperand &Rendered, const MachineInstr &Instruction,
               const MachineFunction &Function, const TargetDescription &Target,
               const std::vector<MaterializedTemporary> &Temporaries,
+              const std::vector<MatchedRule::CapturedOperand> &CapturedOperands,
               std::size_t OriginalExplicitCount) {
   switch (Rendered.SourceKind) {
   case MatchedRule::RenderedOperand::Kind::RootOperand:
@@ -599,6 +790,18 @@ renderOperand(const MatchedRule::RenderedOperand &Rendered, const MachineInstr &
                             "generated match table renders an implicit or missing operand");
     }
     return Instruction.operandAt(Rendered.Value)->cloneDetached();
+  case MatchedRule::RenderedOperand::Kind::ComplexOperand:
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "generated match table did not resolve a complex operand renderer");
+  case MatchedRule::RenderedOperand::Kind::CapturedOperand: {
+    const MatchedRule::CapturedOperand *Captured =
+        findCapturedOperand(CapturedOperands, Rendered.Value);
+    if (Captured == nullptr) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "generated match table renders an unknown captured operand");
+    }
+    return Captured->Operand.cloneDetached();
+  }
   case MatchedRule::RenderedOperand::Kind::PhysicalRegister: {
     auto Physical = PhysicalRegister::create(Rendered.Value);
     if (!Physical || Target.registers().physicalRegister(*Physical) == nullptr) {
@@ -657,12 +860,11 @@ renderOperand(const MatchedRule::RenderedOperand &Rendered, const MachineInstr &
                         "generated match table has an invalid operand renderer");
 }
 
-template <typename Finalizer>
-[[nodiscard]] Expected<void>
-applyRule(const MatchedRule &Rule, MachineInstr &Instruction, MachineFunction &Function,
-          const TargetDescription &Target, Finalizer &&Finalize) {
-  const InstructionDescriptor *InputDescriptor =
-      Target.instructionDescriptor(Instruction.opcode());
+template <typename Finalizer, typename ComplexRenderer>
+[[nodiscard]] Expected<void> applyRule(const MatchedRule &Rule, MachineInstr &Instruction,
+                                       MachineFunction &Function, const TargetDescription &Target,
+                                       Finalizer &&Finalize, ComplexRenderer &&RenderComplex) {
+  const InstructionDescriptor *InputDescriptor = Target.instructionDescriptor(Instruction.opcode());
   if (InputDescriptor == nullptr) {
     return makeUnexpected(ErrorCode::VerificationError,
                           "generated match table input has no instruction descriptor");
@@ -723,17 +925,31 @@ applyRule(const MatchedRule &Rule, MachineInstr &Instruction, MachineFunction &F
     Temporaries.push_back({.ID = Temporary.ID, .Reg = *Reg});
   }
 
+  struct PendingComplexInstruction final {
+    Opcode ResultOpcode;
+    std::vector<MachineOperand> Operands;
+  };
+
+  std::vector<Register> ComplexRegisters;
+  std::vector<PendingComplexInstruction> PendingComplexInstructions;
+  std::vector<MachineInstr *> AddedInstructions;
+  const auto CleanupGeneratedRegisters = [&]() -> Expected<void> {
+    auto ErasedTemporaries = eraseTemporaries(Function.registerInfo(), Temporaries);
+    if (!ErasedTemporaries)
+      return std::unexpected(ErasedTemporaries.error());
+    return eraseRegisters(Function.registerInfo(), ComplexRegisters);
+  };
+
   std::vector<std::vector<MachineOperand>> RenderedInstructions;
   RenderedInstructions.reserve(Rule.Instructions.size());
   std::vector<std::optional<std::size_t>> SourceToOutput(OriginalOperandCount);
   for (std::size_t InstructionIndex = 0; InstructionIndex < Rule.Instructions.size();
        ++InstructionIndex) {
     const MatchedRule::Instruction &Planned = Rule.Instructions[InstructionIndex];
-    const InstructionDescriptor *Descriptor =
-        Target.instructionDescriptor(Planned.ResultOpcode);
+    const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Planned.ResultOpcode);
     if (Descriptor == nullptr ||
         (!Descriptor->Variadic && Descriptor->Operands.size() != Planned.Operands.size())) {
-      auto Cleanup = eraseTemporaries(Function.registerInfo(), Temporaries);
+      auto Cleanup = CleanupGeneratedRegisters();
       if (!Cleanup)
         return std::unexpected(Cleanup.error());
       return makeUnexpected(ErrorCode::VerificationError,
@@ -742,10 +958,51 @@ applyRule(const MatchedRule &Rule, MachineInstr &Instruction, MachineFunction &F
     std::vector<MachineOperand> Operands;
     Operands.reserve(Planned.Operands.size());
     for (const MatchedRule::RenderedOperand &Rendered : Planned.Operands) {
-      auto Operand = renderOperand(Rendered, Instruction, Function, Target, Temporaries,
-                                   OriginalExplicitCount);
+      Expected<MachineOperand> Operand = [&]() -> Expected<MachineOperand> {
+        if (Rendered.SourceKind != MatchedRule::RenderedOperand::Kind::ComplexOperand)
+          return renderOperand(Rendered, Instruction, Function, Target, Temporaries,
+                               Rule.CapturedOperands, OriginalExplicitCount);
+
+        auto Complex =
+            RenderComplex(Rendered.ComplexRenderer, Instruction, Function, Target, Rendered.Value);
+        if (!Complex)
+          return std::unexpected(Complex.error());
+        if (!*Complex)
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "generated match table complex operand unexpectedly did not match");
+        if ((*Complex)->Operand && (*Complex)->Instruction)
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "generated match table complex operand has two renderings");
+        if ((*Complex)->Operand)
+          return std::move(*(*Complex)->Operand);
+        if (!(*Complex)->Instruction)
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "generated match table complex operand has no rendering");
+
+        GIMatchComplexInstruction &Plan = *(*Complex)->Instruction;
+        if (!Plan.ResultType.isValid())
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "generated match table complex instruction has no result type");
+        auto Result = Function.registerInfo().createVirtualRegister(Plan.ResultType);
+        if (!Result)
+          return std::unexpected(Result.error());
+        ComplexRegisters.push_back(*Result);
+        auto Definition = MachineOperand::registerOperand(*Result, {RegisterOperandFlag::Define});
+        if (!Definition)
+          return std::unexpected(Definition.error());
+        std::vector<MachineOperand> PlannedOperands;
+        PlannedOperands.reserve(Plan.Operands.size() + 1U);
+        PlannedOperands.push_back(std::move(*Definition));
+        for (MachineOperand &PlanOperand : Plan.Operands)
+          PlannedOperands.push_back(std::move(PlanOperand));
+        PendingComplexInstructions.push_back({
+            .ResultOpcode = Plan.ResultOpcode,
+            .Operands = std::move(PlannedOperands),
+        });
+        return MachineOperand::registerOperand(*Result, {RegisterOperandFlag::Use});
+      }();
       if (!Operand) {
-        auto Cleanup = eraseTemporaries(Function.registerInfo(), Temporaries);
+        auto Cleanup = CleanupGeneratedRegisters();
         if (!Cleanup)
           return std::unexpected(Cleanup.error());
         return std::unexpected(Operand.error());
@@ -754,7 +1011,7 @@ applyRule(const MatchedRule &Rule, MachineInstr &Instruction, MachineFunction &F
           Rendered.SourceKind == MatchedRule::RenderedOperand::Kind::RootOperand) {
         if (SourceToOutput[Rendered.Value] &&
             Instruction.operandAt(Rendered.Value)->tiedOperandIndex()) {
-          auto Cleanup = eraseTemporaries(Function.registerInfo(), Temporaries);
+          auto Cleanup = CleanupGeneratedRegisters();
           if (!Cleanup)
             return std::unexpected(Cleanup.error());
           return makeUnexpected(ErrorCode::VerificationError,
@@ -767,7 +1024,6 @@ applyRule(const MatchedRule &Rule, MachineInstr &Instruction, MachineFunction &F
     RenderedInstructions.push_back(std::move(Operands));
   }
 
-  std::vector<MachineInstr *> AddedInstructions;
   std::vector<RegisterConstraintSnapshot> ConstraintSnapshots;
   bool RootModified = false;
   const auto Rollback = [&](Error Failure) -> Expected<void> {
@@ -788,12 +1044,25 @@ applyRule(const MatchedRule &Rule, MachineInstr &Instruction, MachineFunction &F
         restoreRegisterConstraints(Function.registerInfo(), ConstraintSnapshots);
     if (!RestoredConstraints)
       return std::unexpected(RestoredConstraints.error());
-    auto ErasedTemporaries = eraseTemporaries(Function.registerInfo(), Temporaries);
-    if (!ErasedTemporaries)
-      return std::unexpected(ErasedTemporaries.error());
+    auto ErasedGenerated = CleanupGeneratedRegisters();
+    if (!ErasedGenerated)
+      return std::unexpected(ErasedGenerated.error());
     return std::unexpected(std::move(Failure));
   };
 
+  for (const PendingComplexInstruction &Pending : PendingComplexInstructions) {
+    const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Pending.ResultOpcode);
+    if (Descriptor == nullptr ||
+        (!Descriptor->Variadic && Descriptor->Operands.size() != Pending.Operands.size())) {
+      return Rollback(Error(ErrorCode::VerificationError,
+                            "generated match table complex renderer has an incompatible result"));
+    }
+    auto Constraint = constrainRenderedInstruction(*Descriptor, Pending.Operands, Function, Target,
+                                                   ConstraintSnapshots);
+    if (!Constraint)
+      return Rollback(Constraint.error());
+  }
+
   for (std::size_t Index = 0; Index < Rule.Instructions.size(); ++Index) {
     const InstructionDescriptor *Descriptor =
         Target.instructionDescriptor(Rule.Instructions[Index].ResultOpcode);
@@ -807,6 +1076,30 @@ applyRule(const MatchedRule &Rule, MachineInstr &Instruction, MachineFunction &F
   }
 
   MachineIRBuilder Builder(Function, Target);
+  MachineInstr *ComplexAnchor = nullptr;
+  for (PendingComplexInstruction &Pending : PendingComplexInstructions) {
+    auto Point = ComplexAnchor == nullptr ? Builder.setInsertPointBefore(Instruction)
+                                          : Builder.setInsertPointAfter(*ComplexAnchor);
+    if (!Point)
+      return Rollback(Point.error());
+    auto Built = Builder.buildInstr(Pending.ResultOpcode);
+    if (!Built)
+      return Rollback(Built.error());
+    for (MachineOperand &Operand : Pending.Operands) {
+      auto Added = Built->addOperand(std::move(Operand));
+      if (!Added)
+        return Rollback(Added.error());
+    }
+    auto Complete = Built->build();
+    if (!Complete)
+      return Rollback(Complete.error());
+    AddedInstructions.push_back(*Complete);
+    auto Finalized = Finalize(**Complete, InputFlags, InputMayRaiseFPException);
+    if (!Finalized)
+      return Rollback(Finalized.error());
+    ComplexAnchor = *Complete;
+  }
+
   MachineInstr *Anchor = &Instruction;
   for (std::size_t Index = 1; Index < Rule.Instructions.size(); ++Index) {
     auto Point = Builder.setInsertPointAfter(*Anchor);
@@ -876,11 +1169,19 @@ applyRule(const MatchedRule &Rule, MachineInstr &Instruction, MachineFunction &F
 
 } // namespace
 
-Expected<void> GIMatchTableExecutor::finalizeGeneratedInstruction(
-    MachineInstr &, MachineFunction &, const TargetDescription &, MachineInstrFlags, bool) const {
+Expected<void> GIMatchTableExecutor::finalizeGeneratedInstruction(MachineInstr &, MachineFunction &,
+                                                                  const TargetDescription &,
+                                                                  MachineInstrFlags, bool) const {
   return {};
 }
 
+Expected<std::optional<GIMatchComplexOperand>>
+GIMatchTableExecutor::renderComplexOperand(std::string_view, const MachineInstr &,
+                                           const MachineFunction &, const TargetDescription &,
+                                           std::uint32_t) const {
+  return std::optional<GIMatchComplexOperand>{};
+}
+
 Expected<bool> GIMatchTableExecutor::match(const GIMatchTable &Table,
                                            const MachineInstr &Instruction,
                                            const MachineFunction &Function,
@@ -891,6 +1192,17 @@ Expected<bool> GIMatchTableExecutor::match(const GIMatchTable &Table,
       return std::unexpected(Match.error());
     if (!*Match)
       continue;
+    auto Complex = complexRenderersMatch(
+        **Match, Instruction, Function, Target,
+        [this](std::string_view Name, const MachineInstr &Input,
+               const MachineFunction &InputFunction, const TargetDescription &InputTarget,
+               std::uint32_t OperandIndex) {
+          return renderComplexOperand(Name, Input, InputFunction, InputTarget, OperandIndex);
+        });
+    if (!Complex)
+      return std::unexpected(Complex.error());
+    if (!*Complex)
+      continue;
     for (const MatchedRule::Instruction &Action : (*Match)->Instructions) {
       if (Target.instructionDescriptor(Action.ResultOpcode) == nullptr) {
         return makeUnexpected(ErrorCode::VerificationError,
@@ -911,12 +1223,28 @@ Expected<bool> GIMatchTableExecutor::select(const GIMatchTable &Table, MachineIn
       return std::unexpected(Match.error());
     if (!*Match)
       continue;
+    auto Complex = complexRenderersMatch(
+        **Match, Instruction, Function, Target,
+        [this](std::string_view Name, const MachineInstr &Input,
+               const MachineFunction &InputFunction, const TargetDescription &InputTarget,
+               std::uint32_t OperandIndex) {
+          return renderComplexOperand(Name, Input, InputFunction, InputTarget, OperandIndex);
+        });
+    if (!Complex)
+      return std::unexpected(Complex.error());
+    if (!*Complex)
+      continue;
     auto Applied = applyRule(
         **Match, Instruction, Function, Target,
         [this, &Function, &Target](MachineInstr &Output, MachineInstrFlags InputFlags,
-                                  bool InputMayRaiseFPException) {
+                                   bool InputMayRaiseFPException) {
           return finalizeGeneratedInstruction(Output, Function, Target, InputFlags,
                                               InputMayRaiseFPException);
+        },
+        [this](std::string_view Name, const MachineInstr &Input,
+               const MachineFunction &InputFunction, const TargetDescription &InputTarget,
+               std::uint32_t OperandIndex) {
+          return renderComplexOperand(Name, Input, InputFunction, InputTarget, OperandIndex);
         });
     if (!Applied)
       return std::unexpected(Applied.error());
diff --git a/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp b/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp
index 6e045b0..85e552c 100644
--- a/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp
+++ b/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp
@@ -170,8 +170,8 @@ constantShiftAmount(Register Reg, const MachineRegisterInfo &MRI, std::uint32_t
 
 } // namespace
 
-GISelValueTracking::GISelValueTracking(MachineFunction &Function, const TargetDescription &Target,
-                                       unsigned MaxDepth) noexcept
+GISelValueTracking::GISelValueTracking(const MachineFunction &Function,
+                                       const TargetDescription &Target, unsigned MaxDepth) noexcept
     : Function(Function), MRI(Function.registerInfo()), Target(Target), MaxDepth(MaxDepth) {}
 
 Expected<GISelValueTracking::KnownBits>
diff --git a/backend/lib/TableGen/Parser.cpp b/backend/lib/TableGen/Parser.cpp
index c194448..b4ff73c 100644
--- a/backend/lib/TableGen/Parser.cpp
+++ b/backend/lib/TableGen/Parser.cpp
@@ -1232,6 +1232,73 @@ private:
   }
 
   [[nodiscard]] bool
+  parseSelectionDefUsePredicates(const yaml::Node &Node,
+                                 std::vector<SourceSelectionDefUsePredicate> &Result) {
+    if (!requireSequence(&Node, "selection def-use predicates"))
+      return false;
+    for (const yaml::NodeID ElementID : Node.sequence()) {
+      const yaml::Node *Element = Input.node(ElementID);
+      if (!requireMapping(Element, "selection def-use predicate") ||
+          !checkKeys(*Element, {"operand", "opcode", "captures", "operand_def_constants"},
+                     "selection def-use predicate")) {
+        return false;
+      }
+      const yaml::Node *OperandNode =
+          requiredNode(*Element, "operand", "selection def-use predicate");
+      const auto Opcode = requiredScalar(*Element, "opcode", "selection def-use predicate");
+      if (OperandNode == nullptr || !Opcode)
+        return false;
+      const auto Operand = unsignedInteger32(*OperandNode, "selection def-use operand");
+      if (!Operand)
+        return false;
+
+      SourceSelectionDefUsePredicate Predicate{
+          .RootOperandIndex = *Operand,
+          .OpcodeSymbol = *Opcode,
+          .Captures = {},
+          .OperandDefConstants = {},
+          .Range = Element->range(),
+      };
+      if (const yaml::Node *Captures = optionalNode(*Element, "captures")) {
+        if (!requireSequence(Captures, "selection def-use captures"))
+          return false;
+        for (const yaml::NodeID CaptureID : Captures->sequence()) {
+          const yaml::Node *Capture = Input.node(CaptureID);
+          if (!requireMapping(Capture, "selection def-use capture") ||
+              !checkKeys(*Capture, {"id", "operand"}, "selection def-use capture")) {
+            return false;
+          }
+          const auto Symbol = requiredScalar(*Capture, "id", "selection def-use capture");
+          const yaml::Node *CaptureOperand =
+              requiredNode(*Capture, "operand", "selection def-use capture");
+          if (!Symbol || CaptureOperand == nullptr)
+            return false;
+          const auto Index =
+              unsignedInteger32(*CaptureOperand, "selection def-use capture operand");
+          if (!Index)
+            return false;
+          Predicate.Captures.push_back({
+              .Symbol = *Symbol,
+              .OperandIndex = *Index,
+              .Range = Capture->range(),
+          });
+        }
+      }
+      if (const yaml::Node *Constants = optionalNode(*Element, "operand_def_constants")) {
+        if (!parseSelectionOperandDefConstants(*Constants, Predicate.OperandDefConstants))
+          return false;
+      }
+      if (Predicate.Captures.empty() && Predicate.OperandDefConstants.empty()) {
+        fail(Element->range(),
+             "selection def-use predicate requires a capture or constant predicate");
+        return false;
+      }
+      Result.push_back(std::move(Predicate));
+    }
+    return true;
+  }
+
+  [[nodiscard]] bool
   parseSelectionOperandRenderers(const yaml::Node &Node,
                                  std::vector<SourceSelectionOperandRenderer> &Result) {
     if (!requireSequence(&Node, "selection operand renderers"))
@@ -1240,36 +1307,55 @@ private:
       const yaml::Node *Element = Input.node(ElementID);
       if (!requireMapping(Element, "selection operand renderer") ||
           !checkKeys(*Element,
-                     {"operand", "physical_register", "temporary", "captured_immediate",
-                      "immediate", "transform", "flags"},
+                     {"operand", "complex", "physical_register", "temporary", "captured_operand",
+                      "captured_immediate", "immediate", "transform", "flags"},
                      "selection operand renderer")) {
         return false;
       }
       const yaml::Node *OperandNode = optionalNode(*Element, "operand");
+      const yaml::Node *ComplexNode = optionalNode(*Element, "complex");
       const yaml::Node *PhysicalRegisterNode = optionalNode(*Element, "physical_register");
       const yaml::Node *TemporaryNode = optionalNode(*Element, "temporary");
+      const yaml::Node *CapturedOperandNode = optionalNode(*Element, "captured_operand");
       const yaml::Node *CapturedImmediateNode = optionalNode(*Element, "captured_immediate");
       const yaml::Node *ImmediateNode = optionalNode(*Element, "immediate");
-      const std::uint32_t SourceCount = static_cast<std::uint32_t>(OperandNode != nullptr) +
-                                        static_cast<std::uint32_t>(PhysicalRegisterNode != nullptr) +
-                                        static_cast<std::uint32_t>(TemporaryNode != nullptr) +
-                                        static_cast<std::uint32_t>(CapturedImmediateNode != nullptr) +
-                                        static_cast<std::uint32_t>(ImmediateNode != nullptr);
+      const std::uint32_t SourceCount =
+          static_cast<std::uint32_t>(ComplexNode != nullptr) +
+          static_cast<std::uint32_t>(ComplexNode == nullptr && OperandNode != nullptr) +
+          static_cast<std::uint32_t>(PhysicalRegisterNode != nullptr) +
+          static_cast<std::uint32_t>(TemporaryNode != nullptr) +
+          static_cast<std::uint32_t>(CapturedOperandNode != nullptr) +
+          static_cast<std::uint32_t>(CapturedImmediateNode != nullptr) +
+          static_cast<std::uint32_t>(ImmediateNode != nullptr);
       if (SourceCount != 1) {
         fail(Element->range(), "selection operand renderer requires exactly one source");
         return false;
       }
       SourceSelectionOperandRenderer Renderer{
           .OperandIndex = std::nullopt,
+          .ComplexOperandIndex = std::nullopt,
           .PhysicalRegisterSymbol = {},
+          .ComplexRendererSymbol = {},
           .TemporarySymbol = {},
+          .CapturedOperandSymbol = {},
           .CapturedImmediateOperand = std::nullopt,
           .Immediate = std::nullopt,
           .ImmediateTransform = "identity",
           .Flags = {},
           .Range = Element->range(),
       };
-      if (OperandNode != nullptr) {
+      if (ComplexNode != nullptr) {
+        if (OperandNode == nullptr) {
+          fail(Element->range(), "complex selection operand renderer requires an operand index");
+          return false;
+        }
+        const auto Name = scalar(*ComplexNode, "selection operand renderer complex matcher");
+        const auto Index = unsignedInteger32(*OperandNode, "selection operand renderer operand");
+        if (!Name || !Index)
+          return false;
+        Renderer.ComplexRendererSymbol = *Name;
+        Renderer.ComplexOperandIndex = Index;
+      } else if (OperandNode != nullptr) {
         const auto Index = unsignedInteger32(*OperandNode, "selection operand renderer operand");
         if (!Index)
           return false;
@@ -1285,9 +1371,15 @@ private:
         if (!Symbol)
           return false;
         Renderer.TemporarySymbol = *Symbol;
+      } else if (CapturedOperandNode != nullptr) {
+        const auto Symbol =
+            scalar(*CapturedOperandNode, "selection operand renderer captured operand");
+        if (!Symbol)
+          return false;
+        Renderer.CapturedOperandSymbol = *Symbol;
       } else if (CapturedImmediateNode != nullptr) {
-        const auto Index =
-            unsignedInteger32(*CapturedImmediateNode, "selection operand renderer captured immediate");
+        const auto Index = unsignedInteger32(*CapturedImmediateNode,
+                                             "selection operand renderer captured immediate");
         if (!Index)
           return false;
         Renderer.CapturedImmediateOperand = *Index;
@@ -1304,7 +1396,8 @@ private:
         Renderer.ImmediateTransform = *Transform;
       }
       if (!Renderer.CapturedImmediateOperand && Renderer.ImmediateTransform != "identity") {
-        fail(Element->range(), "selection operand renderer transform requires a captured immediate");
+        fail(Element->range(),
+             "selection operand renderer transform requires a captured immediate");
         return false;
       }
       if (const yaml::Node *FlagsNode = optionalNode(*Element, "flags")) {
@@ -1319,7 +1412,7 @@ private:
   }
 
   [[nodiscard]] bool parseSelectionTemporaries(const yaml::Node &Node,
-                                                std::vector<SourceSelectionTemporary> &Result) {
+                                               std::vector<SourceSelectionTemporary> &Result) {
     if (!requireSequence(&Node, "selection temporaries"))
       return false;
     for (const yaml::NodeID ElementID : Node.sequence()) {
@@ -1329,7 +1422,8 @@ private:
         return false;
       }
       const auto Symbol = requiredScalar(*Element, "id", "selection temporary");
-      const yaml::Node *TypeNode = requiredNode(*Element, "type_from_operand", "selection temporary");
+      const yaml::Node *TypeNode =
+          requiredNode(*Element, "type_from_operand", "selection temporary");
       if (!Symbol || TypeNode == nullptr)
         return false;
       const auto TypeFromOperand = unsignedInteger32(*TypeNode, "selection temporary type operand");
@@ -1345,7 +1439,7 @@ private:
   }
 
   [[nodiscard]] bool parseSelectionActions(const yaml::Node &Node,
-                                            std::vector<SourceSelectionAction> &Result) {
+                                           std::vector<SourceSelectionAction> &Result) {
     if (!requireSequence(&Node, "selection instructions"))
       return false;
     for (const yaml::NodeID ElementID : Node.sequence()) {
@@ -1379,7 +1473,7 @@ private:
     if (!requireMapping(&Node, "selection rule match") ||
         !checkKeys(Node,
                    {"opcode", "result_type", "integer_predicate", "operand_types", "operand_banks",
-                    "operand_classes", "operand_def_constants"},
+                    "operand_classes", "operand_def_constants", "def_use"},
                    "selection rule match")) {
       return false;
     }
@@ -1413,6 +1507,10 @@ private:
       if (!parseSelectionOperandDefConstants(*OperandDefConstants, Result.OperandDefConstants))
         return false;
     }
+    if (const yaml::Node *DefUse = optionalNode(Node, "def_use")) {
+      if (!parseSelectionDefUsePredicates(*DefUse, Result.DefUsePredicates))
+        return false;
+    }
     return true;
   }
 
diff --git a/backend/lib/Target/RISCV/CMakeLists.txt b/backend/lib/Target/RISCV/CMakeLists.txt
index 8c84398..f9eb79f 100644
--- a/backend/lib/Target/RISCV/CMakeLists.txt
+++ b/backend/lib/Target/RISCV/CMakeLists.txt
@@ -15,6 +15,7 @@ set(
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVInstrInfoZb.rccdesc"
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVInstrInfoPseudo.rccdesc"
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVGISelInteger.rccdesc"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RISCVGISelShift.rccdesc"
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVGISelFloating.rccdesc"
 )
 set(RCCBackendRISCVTableGenArguments)
diff --git a/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp b/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp
index c3f2a17..e258fa4 100644
--- a/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp
+++ b/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp
@@ -4,6 +4,7 @@
 #include "RISCVImmediateMaterialization.h"
 #include "RISCVRegisterBankInfo.h"
 #include "rcc/CodeGen/GenericOpcodes.h"
+#include "rcc/CodeGen/GlobalISel/GISelValueTracking.h"
 #include "rcc/CodeGen/GlobalISel/InstructionSelector.h"
 #include "rcc/CodeGen/LowLevelType.h"
 #include "rcc/CodeGen/MachineBasicBlock.h"
@@ -169,6 +170,140 @@ public:
     return RegisterBanks.constrainSelectedInstruction(Instruction, Function, Target);
   }
 
+  [[nodiscard]] Expected<std::optional<GIMatchComplexOperand>>
+  renderComplexOperand(std::string_view Name, const MachineInstr &Instruction,
+                       const MachineFunction &Function, const TargetDescription &Target,
+                       std::uint32_t OperandIndex) const override {
+    const std::uint64_t ShiftWidth = Name == "shift_mask_xlen" ? 64U
+                                     : Name == "shift_mask_32" ? 32U
+                                                               : 0U;
+    if (ShiftWidth == 0)
+      return std::optional<GIMatchComplexOperand>{};
+    const MachineOperand *Root = Instruction.operandAt(OperandIndex);
+    const Register *RootRegister = Root == nullptr ? nullptr : Root->getIf<Register>();
+    if (RootRegister == nullptr || !RootRegister->isVirtual())
+      return std::optional<GIMatchComplexOperand>{};
+
+    Register ShiftRegister = *RootRegister;
+    const auto Definition = [&Function](Register Reg) -> const MachineInstr * {
+      return Reg.isVirtual() ? Function.registerInfo().getVRegDef(Reg) : nullptr;
+    };
+    const auto UseOperand = [](Register Reg) -> Expected<MachineOperand> {
+      return MachineOperand::registerOperand(Reg, {RegisterOperandFlag::Use});
+    };
+    const auto DirectResult = [&UseOperand](Register Reg) -> Expected<GIMatchComplexOperand> {
+      auto Operand = UseOperand(Reg);
+      if (!Operand)
+        return std::unexpected(Operand.error());
+      return GIMatchComplexOperand{
+          .Operand = std::move(*Operand),
+          .Instruction = std::nullopt,
+      };
+    };
+
+    if (const MachineInstr *Extension = Definition(ShiftRegister);
+        Extension != nullptr && Extension->opcode() == opcode(GenericOpcode::G_ZEXT)) {
+      const MachineOperand *SourceOperand = Extension->operandAt(1);
+      const Register *Source =
+          SourceOperand == nullptr ? nullptr : SourceOperand->getIf<Register>();
+      if (Source != nullptr)
+        ShiftRegister = *Source;
+    }
+
+    const std::uint64_t ShiftMask = ShiftWidth - 1U;
+    if (const MachineInstr *And = Definition(ShiftRegister);
+        And != nullptr && And->opcode() == opcode(GenericOpcode::G_AND)) {
+      const MachineOperand *SourceOperand = And->operandAt(1);
+      const MachineOperand *MaskOperand = And->operandAt(2);
+      const Register *Source =
+          SourceOperand == nullptr ? nullptr : SourceOperand->getIf<Register>();
+      const Register *Mask = MaskOperand == nullptr ? nullptr : MaskOperand->getIf<Register>();
+      const auto MaskValue =
+          Mask == nullptr ? std::nullopt : directIntegerConstant(Function.registerInfo(), *Mask);
+      if (Source != nullptr && MaskValue) {
+        const std::uint64_t RawMask = std::bit_cast<std::uint64_t>(*MaskValue);
+        bool ElideMask = (RawMask & ShiftMask) == ShiftMask;
+        if (!ElideMask) {
+          GISelValueTracking ValueTracking(Function, Target);
+          auto KnownZeroes = ValueTracking.getKnownZeroes(*Source);
+          if (!KnownZeroes)
+            return std::unexpected(KnownZeroes.error());
+          ElideMask = ((RawMask | KnownZeroes->word(0)) & ShiftMask) == ShiftMask;
+        }
+        if (ElideMask)
+          ShiftRegister = *Source;
+      }
+    }
+
+    const MachineInstr *ShiftDefinition = Definition(ShiftRegister);
+    if (ShiftDefinition == nullptr)
+      return DirectResult(ShiftRegister);
+    const MachineOperand *LeftOperand = ShiftDefinition->operandAt(1);
+    const MachineOperand *RightOperand = ShiftDefinition->operandAt(2);
+    const Register *Left = LeftOperand == nullptr ? nullptr : LeftOperand->getIf<Register>();
+    const Register *Right = RightOperand == nullptr ? nullptr : RightOperand->getIf<Register>();
+
+    if (ShiftDefinition->opcode() == opcode(GenericOpcode::G_ADD) && Left != nullptr &&
+        Right != nullptr) {
+      const auto Immediate = directIntegerConstant(Function.registerInfo(), *Right);
+      if (Immediate != std::nullopt && *Immediate != 0 &&
+          std::bit_cast<std::uint64_t>(*Immediate) % ShiftWidth == 0)
+        return DirectResult(*Left);
+    }
+
+    if (ShiftDefinition->opcode() != opcode(GenericOpcode::G_SUB) || Left == nullptr ||
+        Right == nullptr)
+      return DirectResult(ShiftRegister);
+    const auto Immediate = directIntegerConstant(Function.registerInfo(), *Left);
+    if (!Immediate || *Immediate == 0)
+      return DirectResult(ShiftRegister);
+
+    const std::uint64_t Remainder = std::bit_cast<std::uint64_t>(*Immediate) % ShiftWidth;
+    if (Remainder != 0 && Remainder != ShiftMask)
+      return DirectResult(ShiftRegister);
+    auto Type = Function.registerInfo().getType(*Right);
+    if (!Type)
+      return std::unexpected(Type.error());
+    std::vector<MachineOperand> Operands;
+    if (Remainder == 0) {
+      auto Zero = physicalRegister(PhysicalRegisterID::X0);
+      if (!Zero)
+        return std::unexpected(Zero.error());
+      auto ZeroOperand = UseOperand(Register::fromPhysical(*Zero));
+      auto SourceOperand = UseOperand(*Right);
+      if (!ZeroOperand)
+        return std::unexpected(ZeroOperand.error());
+      if (!SourceOperand)
+        return std::unexpected(SourceOperand.error());
+      Operands.push_back(std::move(*ZeroOperand));
+      Operands.push_back(std::move(*SourceOperand));
+      return GIMatchComplexOperand{
+          .Operand = std::nullopt,
+          .Instruction =
+              GIMatchComplexInstruction{
+                  .ResultOpcode = instructionOpcode(InstructionOpcode::SUBW),
+                  .ResultType = *Type,
+                  .Operands = std::move(Operands),
+              },
+      };
+    }
+
+    auto SourceOperand = UseOperand(*Right);
+    if (!SourceOperand)
+      return std::unexpected(SourceOperand.error());
+    Operands.push_back(std::move(*SourceOperand));
+    Operands.push_back(MachineOperand::immediate(-1));
+    return GIMatchComplexOperand{
+        .Operand = std::nullopt,
+        .Instruction =
+            GIMatchComplexInstruction{
+                .ResultOpcode = instructionOpcode(InstructionOpcode::XORI),
+                .ResultType = *Type,
+                .Operands = std::move(Operands),
+            },
+    };
+  }
+
   [[nodiscard]] Expected<void> canSelect(const MachineInstr &Instruction,
                                          const MachineFunction &Function,
                                          const TargetDescription &Target) const override {
@@ -190,13 +325,6 @@ public:
     const auto Integer = [Type] { return Type && isSupportedIntegerType(*Type); };
     const auto Float = [Type] { return Type && isSupportedFloatingScalar(*Type); };
     switch (Generic) {
-    case GenericOpcode::G_SHL:
-    case GenericOpcode::G_LSHR:
-    case GenericOpcode::G_ASHR:
-      if (!Integer())
-        return makeUnexpected(ErrorCode::Unsupported,
-                              "RISC-V selector requires an i1-i64 integer or 64-bit pointer value");
-      return {};
     case GenericOpcode::G_CONSTANT:
       if (!Integer())
         return makeUnexpected(ErrorCode::Unsupported,
@@ -302,28 +430,6 @@ public:
     const std::optional<LowLevelType> Type = resultType(Function, Instruction);
 
     switch (Generic) {
-    case GenericOpcode::G_SHL:
-      return selectIntegerBinary(Instruction, Function, Type, InstructionOpcode::SLL,
-                                 InstructionOpcode::SLLW, InstructionOpcode::SLLI,
-                                 InstructionOpcode::SLLIW, false, 6, 5);
-    case GenericOpcode::G_LSHR:
-      if (auto Selected = selectRV64WordShift(Instruction, Function, Type, Generic); !Selected) {
-        return std::unexpected(Selected.error());
-      } else if (*Selected) {
-        return {};
-      }
-      return selectNormalizedIntegerBinary(
-          Instruction, Function, Target, Type, InstructionOpcode::SRL, InstructionOpcode::SRLW,
-          false, false, InstructionOpcode::SRLI, InstructionOpcode::SRLIW, false, 6, 5);
-    case GenericOpcode::G_ASHR:
-      if (auto Selected = selectRV64WordShift(Instruction, Function, Type, Generic); !Selected) {
-        return std::unexpected(Selected.error());
-      } else if (*Selected) {
-        return {};
-      }
-      return selectNormalizedIntegerBinary(
-          Instruction, Function, Target, Type, InstructionOpcode::SRA, InstructionOpcode::SRAW,
-          true, false, InstructionOpcode::SRAI, InstructionOpcode::SRAIW, false, 6, 5);
     case GenericOpcode::G_LOAD:
       return selectLoad(Instruction, Function, Type);
     case GenericOpcode::G_SEXTLOAD:
@@ -1866,84 +1972,6 @@ private:
     return true;
   }
 
-  [[nodiscard]] Expected<bool> selectRV64WordShift(MachineInstr &Instruction,
-                                                   MachineFunction &Function,
-                                                   std::optional<LowLevelType> Type,
-                                                   GenericOpcode Generic) const {
-    if (!Type || !Type->isCategoryNeutralScalar() || Type->scalarBitWidth() != 64)
-      return false;
-    const MachineOperand *LeftOperand = Instruction.operandAt(1);
-    const MachineOperand *RightOperand = Instruction.operandAt(2);
-    const Register *Left = LeftOperand == nullptr ? nullptr : LeftOperand->getIf<Register>();
-    const Register *Right = RightOperand == nullptr ? nullptr : RightOperand->getIf<Register>();
-    if (Left == nullptr || Right == nullptr || !Right->isVirtual())
-      return false;
-    const std::optional<std::int64_t> ShiftAmount =
-        directIntegerConstant(Function.registerInfo(), *Right);
-    if (!ShiftAmount || !fitsIntegerImmediate(*ShiftAmount, false, 5))
-      return false;
-
-    const MachineInstr *LeftDefinition = Function.registerInfo().getVRegDef(*Left);
-    if (LeftDefinition == nullptr)
-      return false;
-    const MachineOperand *SourceOperand = LeftDefinition->operandAt(1);
-    const Register *Source = SourceOperand == nullptr ? nullptr : SourceOperand->getIf<Register>();
-    if (Source == nullptr)
-      return false;
-
-    InstructionOpcode Selected = InstructionOpcode::Invalid;
-    if (Generic == GenericOpcode::G_LSHR &&
-        LeftDefinition->opcode() == opcode(GenericOpcode::G_AND)) {
-      const MachineOperand *MaskOperand = LeftDefinition->operandAt(2);
-      const Register *Mask = MaskOperand == nullptr ? nullptr : MaskOperand->getIf<Register>();
-      const std::optional<std::int64_t> MaskValue =
-          Mask == nullptr ? std::nullopt : directIntegerConstant(Function.registerInfo(), *Mask);
-      if (MaskValue && *MaskValue == std::int64_t{0xffffffff})
-        Selected = InstructionOpcode::SRLIW;
-    } else if (Generic == GenericOpcode::G_ASHR &&
-               LeftDefinition->opcode() == opcode(GenericOpcode::G_SEXT_INREG)) {
-      const MachineOperand *WidthOperand = LeftDefinition->operandAt(2);
-      const auto *Width = WidthOperand == nullptr ? nullptr : WidthOperand->getIf<std::int64_t>();
-      if (Width != nullptr && *Width == 32)
-        Selected = InstructionOpcode::SRAIW;
-    }
-    if (Selected == InstructionOpcode::Invalid)
-      return false;
-
-    auto SetLeft = Instruction.operandAt(1)->setRegister(*Source);
-    if (!SetLeft)
-      return std::unexpected(SetLeft.error());
-    auto EraseRight = Instruction.eraseOperand(2);
-    if (!EraseRight)
-      return std::unexpected(EraseRight.error());
-    auto AddImmediate = Instruction.addOperand(MachineOperand::immediate(*ShiftAmount));
-    if (!AddImmediate)
-      return std::unexpected(AddImmediate.error());
-    auto SetOpcode = Instruction.setOpcode(instructionOpcode(Selected));
-    if (!SetOpcode)
-      return std::unexpected(SetOpcode.error());
-    return true;
-  }
-
-  [[nodiscard]] Expected<void>
-  selectIntegerBinary(MachineInstr &Instruction, MachineFunction &Function,
-                      std::optional<LowLevelType> Type, InstructionOpcode DoubleWord,
-                      InstructionOpcode Word, InstructionOpcode DoubleWordImmediate,
-                      InstructionOpcode WordImmediate, bool SignedImmediate,
-                      std::uint32_t DoubleWordBits, std::uint32_t WordBits) const {
-    if (!Type || !isSupportedIntegerType(*Type))
-      return makeUnexpected(ErrorCode::Unsupported,
-                            "RISC-V integer instruction requires a supported scalar integer");
-    const bool IsWord = Type->isCategoryNeutralScalar() && Type->scalarBitWidth() <= 32;
-    const auto Folded = foldRightConstantToImmediate(Instruction, Function, SignedImmediate,
-                                                     IsWord ? WordBits : DoubleWordBits);
-    if (!Folded)
-      return std::unexpected(Folded.error());
-    if (*Folded)
-      return Instruction.setOpcode(instructionOpcode(IsWord ? WordImmediate : DoubleWordImmediate));
-    return Instruction.setOpcode(instructionOpcode(IsWord ? Word : DoubleWord));
-  }
-
   [[nodiscard]] Expected<void> selectNormalizedIntegerBinary(
       MachineInstr &Instruction, MachineFunction &Function, const TargetDescription &Target,
       std::optional<LowLevelType> Type, InstructionOpcode DoubleWord, InstructionOpcode Word,
diff --git a/backend/lib/Target/RISCV/RISCVGISelShift.rccdesc b/backend/lib/Target/RISCV/RISCVGISelShift.rccdesc
new file mode 100644
index 0000000..bf9bf71
--- /dev/null
+++ b/backend/lib/Target/RISCV/RISCVGISelShift.rccdesc
@@ -0,0 +1,198 @@
+# SPDX-License-Identifier: GPL-3.0-or-later
+
+selection_rules:
+  -
+    id: select_g_lshr_s64_word_immediate
+    priority: 500
+    match:
+      opcode: G_LSHR
+      result_type: { kind: scalar, bits: 64 }
+      operand_types:
+        - { index: 1, kind: scalar, bits: 64 }
+        - { index: 2, kind: scalar, bits: 64 }
+      operand_banks:
+        - { index: 0, bank: GPR }
+        - { index: 1, bank: GPR }
+        - { index: 2, bank: GPR }
+      operand_def_constants:
+        - index: 2
+          ranges: [{ min: 0, max: 31 }]
+      def_use:
+        - operand: 1
+          opcode: G_AND
+          captures:
+            - { id: source, operand: 1 }
+          operand_def_constants:
+            - index: 2
+              ranges: [{ min: 4294967295, max: 4294967295 }]
+    apply:
+      instructions:
+        - opcode: SRLIW
+          root: true
+          operands:
+            - { operand: 0 }
+            - { captured_operand: source }
+            - { captured_immediate: 2 }
+      erase_operand_definitions: [1, 2]
+  -
+    id: select_g_ashr_s64_word_immediate
+    priority: 500
+    match:
+      opcode: G_ASHR
+      result_type: { kind: scalar, bits: 64 }
+      operand_types:
+        - { index: 1, kind: scalar, bits: 64 }
+        - { index: 2, kind: scalar, bits: 64 }
+      operand_banks:
+        - { index: 0, bank: GPR }
+        - { index: 1, bank: GPR }
+        - { index: 2, bank: GPR }
+      operand_def_constants:
+        - index: 2
+          ranges: [{ min: 0, max: 31 }]
+      def_use:
+        - operand: 1
+          opcode: G_SEXT_INREG
+          captures:
+            - { id: source, operand: 1 }
+          operand_def_constants:
+            - index: 2
+              ranges: [{ min: 32, max: 32 }]
+    apply:
+      instructions:
+        - opcode: SRAIW
+          root: true
+          operands:
+            - { operand: 0 }
+            - { captured_operand: source }
+            - { captured_immediate: 2 }
+      erase_operand_definitions: [1, 2]
+  -
+    id: select_g_shl_s64_immediate
+    priority: 400
+    match:
+      opcode: G_SHL
+      result_type: { kind: scalar, bits: 64 }
+      operand_types:
+        - { index: 1, kind: scalar, bits: 64 }
+        - { index: 2, kind: scalar, bits: 64 }
+      operand_banks:
+        - { index: 0, bank: GPR }
+        - { index: 1, bank: GPR }
+        - { index: 2, bank: GPR }
+      operand_def_constants:
+        - index: 2
+          ranges: [{ min: 0, max: 63 }]
+    apply:
+      instructions:
+        - opcode: SLLI
+          root: true
+          operands: [{ operand: 0 }, { operand: 1 }, { captured_immediate: 2 }]
+      erase_operand_definitions: [2]
+  -
+    id: select_g_lshr_s64_immediate
+    priority: 400
+    match:
+      opcode: G_LSHR
+      result_type: { kind: scalar, bits: 64 }
+      operand_types:
+        - { index: 1, kind: scalar, bits: 64 }
+        - { index: 2, kind: scalar, bits: 64 }
+      operand_banks:
+        - { index: 0, bank: GPR }
+        - { index: 1, bank: GPR }
+        - { index: 2, bank: GPR }
+      operand_def_constants:
+        - index: 2
+          ranges: [{ min: 0, max: 63 }]
+    apply:
+      instructions:
+        - opcode: SRLI
+          root: true
+          operands: [{ operand: 0 }, { operand: 1 }, { captured_immediate: 2 }]
+      erase_operand_definitions: [2]
+  -
+    id: select_g_ashr_s64_immediate
+    priority: 400
+    match:
+      opcode: G_ASHR
+      result_type: { kind: scalar, bits: 64 }
+      operand_types:
+        - { index: 1, kind: scalar, bits: 64 }
+        - { index: 2, kind: scalar, bits: 64 }
+      operand_banks:
+        - { index: 0, bank: GPR }
+        - { index: 1, bank: GPR }
+        - { index: 2, bank: GPR }
+      operand_def_constants:
+        - index: 2
+          ranges: [{ min: 0, max: 63 }]
+    apply:
+      instructions:
+        - opcode: SRAI
+          root: true
+          operands: [{ operand: 0 }, { operand: 1 }, { captured_immediate: 2 }]
+      erase_operand_definitions: [2]
+  -
+    id: select_g_shl_s64_register
+    priority: 100
+    match:
+      opcode: G_SHL
+      result_type: { kind: scalar, bits: 64 }
+      operand_types:
+        - { index: 1, kind: scalar, bits: 64 }
+        - { index: 2, kind: scalar, bits: 64 }
+      operand_banks:
+        - { index: 0, bank: GPR }
+        - { index: 1, bank: GPR }
+        - { index: 2, bank: GPR }
+    apply:
+      instructions:
+        - opcode: SLL
+          root: true
+          operands:
+            - { operand: 0 }
+            - { operand: 1 }
+            - { complex: shift_mask_xlen, operand: 2 }
+  -
+    id: select_g_lshr_s64_register
+    priority: 100
+    match:
+      opcode: G_LSHR
+      result_type: { kind: scalar, bits: 64 }
+      operand_types:
+        - { index: 1, kind: scalar, bits: 64 }
+        - { index: 2, kind: scalar, bits: 64 }
+      operand_banks:
+        - { index: 0, bank: GPR }
+        - { index: 1, bank: GPR }
+        - { index: 2, bank: GPR }
+    apply:
+      instructions:
+        - opcode: SRL
+          root: true
+          operands:
+            - { operand: 0 }
+            - { operand: 1 }
+            - { complex: shift_mask_xlen, operand: 2 }
+  -
+    id: select_g_ashr_s64_register
+    priority: 100
+    match:
+      opcode: G_ASHR
+      result_type: { kind: scalar, bits: 64 }
+      operand_types:
+        - { index: 1, kind: scalar, bits: 64 }
+        - { index: 2, kind: scalar, bits: 64 }
+      operand_banks:
+        - { index: 0, bank: GPR }
+        - { index: 1, bank: GPR }
+        - { index: 2, bank: GPR }
+    apply:
+      instructions:
+        - opcode: SRA
+          root: true
+          operands:
+            - { operand: 0 }
+            - { operand: 1 }
+            - { complex: shift_mask_xlen, operand: 2 }
diff --git a/backend/utils/TableGen/Common/CodeGenSelection.cpp b/backend/utils/TableGen/Common/CodeGenSelection.cpp
index 1e65e04..88f85f7 100644
--- a/backend/utils/TableGen/Common/CodeGenSelection.cpp
+++ b/backend/utils/TableGen/Common/CodeGenSelection.cpp
@@ -265,7 +265,8 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) {
     for (const SourceSelectionOperandDefConstantPredicate &Predicate : Rule.OperandDefConstants) {
       if (!ConstantOperands.insert(Predicate.OperandIndex).second ||
           (MatchInstruction != nullptr &&
-           !isRegisterOperand(*MatchInstruction, Predicate.OperandIndex)) || Predicate.Ranges.empty()) {
+           !isRegisterOperand(*MatchInstruction, Predicate.OperandIndex)) ||
+          Predicate.Ranges.empty()) {
         fail(Predicate.Range,
              "selection operand definition constant predicates require distinct register "
              "operands and at least one range");
@@ -300,6 +301,81 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) {
       ++Normalized.Specificity;
     }
 
+    std::unordered_map<std::string, std::uint32_t> CaptureIDs;
+    std::unordered_set<std::uint32_t> DefUseRootOperands;
+    for (const SourceSelectionDefUsePredicate &Predicate : Rule.DefUsePredicates) {
+      const auto DefOpcode = resolveOpcode(Result, Predicate.OpcodeSymbol);
+      if (!DefOpcode || !isGenericOpcode(Opcode::fromValue(*DefOpcode)) ||
+          !DefUseRootOperands.insert(Predicate.RootOperandIndex).second ||
+          (MatchInstruction != nullptr &&
+           !isRegisterOperand(*MatchInstruction, Predicate.RootOperandIndex))) {
+        fail(Predicate.Range,
+             "selection def-use predicates require distinct register operands and generic opcodes");
+        return false;
+      }
+
+      NormalizedSelectionDefUsePredicate NormalizedPredicate{
+          .RootOperandIndex = Predicate.RootOperandIndex,
+          .Opcode = *DefOpcode,
+          .Captures = {},
+          .OperandDefConstants = {},
+      };
+      std::unordered_set<std::uint32_t> CapturedOperands;
+      for (const SourceSelectionDefUseCapture &Capture : Predicate.Captures) {
+        if (!isIdentifier(Capture.Symbol) ||
+            !CapturedOperands.insert(Capture.OperandIndex).second ||
+            !CaptureIDs.emplace(Capture.Symbol, CaptureIDs.size() + 1U).second) {
+          fail(Capture.Range,
+               "selection def-use captures require unique identifiers and distinct operands");
+          return false;
+        }
+        NormalizedPredicate.Captures.push_back({
+            .ID = CaptureIDs.at(Capture.Symbol),
+            .OperandIndex = Capture.OperandIndex,
+        });
+      }
+
+      std::unordered_set<std::uint32_t> ConstantOperandsInDef;
+      for (const SourceSelectionOperandDefConstantPredicate &Constant :
+           Predicate.OperandDefConstants) {
+        if (!ConstantOperandsInDef.insert(Constant.OperandIndex).second ||
+            Constant.Ranges.empty()) {
+          fail(Constant.Range, "selection def-use constant predicates require distinct operands "
+                               "and at least one range");
+          return false;
+        }
+        NormalizedSelectionOperandDefConstantPredicate NormalizedConstant{
+            .OperandIndex = Constant.OperandIndex,
+            .Ranges = {},
+        };
+        for (const SourceSelectionOperandDefConstantPredicate::ConstantRange &Range :
+             Constant.Ranges) {
+          if (Range.Minimum > Range.Maximum) {
+            fail(Range.SourceRange, "selection def-use constant range is invalid");
+            return false;
+          }
+          NormalizedConstant.Ranges.push_back({
+              .Minimum = Range.Minimum,
+              .Maximum = Range.Maximum,
+          });
+        }
+        std::ranges::sort(NormalizedConstant.Ranges, {},
+                          &NormalizedSelectionOperandDefConstantPredicate::Range::Minimum);
+        for (std::size_t Index = 1; Index < NormalizedConstant.Ranges.size(); ++Index) {
+          const auto &Previous = NormalizedConstant.Ranges[Index - 1];
+          const auto &Current = NormalizedConstant.Ranges[Index];
+          if (Current.Minimum <= Previous.Maximum) {
+            fail(Constant.Range, "selection def-use constant ranges overlap");
+            return false;
+          }
+        }
+        NormalizedPredicate.OperandDefConstants.push_back(std::move(NormalizedConstant));
+      }
+      Normalized.DefUsePredicates.push_back(std::move(NormalizedPredicate));
+      Normalized.Specificity += 1U + static_cast<std::uint32_t>(Predicate.Captures.size()) +
+                                static_cast<std::uint32_t>(Predicate.OperandDefConstants.size());
+    }
+
     std::unordered_map<std::string, std::uint32_t> TemporaryIDs;
     for (const SourceSelectionTemporary &Temporary : Rule.Temporaries) {
       if (!isIdentifier(Temporary.Symbol) ||
@@ -346,6 +422,22 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) {
       };
       NormalizedAction.OperandRenderers.reserve(Action.OperandRenderers.size());
       for (const SourceSelectionOperandRenderer &Renderer : Action.OperandRenderers) {
+        if (Renderer.ComplexOperandIndex) {
+          if (Renderer.ComplexRendererSymbol.empty() || !Renderer.Flags.empty() ||
+              Renderer.ImmediateTransform != "identity") {
+            fail(Renderer.Range,
+                 "selection complex operand renderer requires a matcher and no flags or transform");
+            return false;
+          }
+          NormalizedAction.OperandRenderers.push_back({
+              .SourceKind = NormalizedSelectionOperandRenderer::Kind::ComplexOperand,
+              .Value = *Renderer.ComplexOperandIndex,
+              .ComplexRenderer = Renderer.ComplexRendererSymbol,
+              .Flags = 0,
+          });
+          continue;
+        }
+
         if (Renderer.OperandIndex) {
           if (MatchInstruction != nullptr &&
               *Renderer.OperandIndex >= MatchInstruction->Operands.size()) {
@@ -359,6 +451,7 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) {
           NormalizedAction.OperandRenderers.push_back({
               .SourceKind = NormalizedSelectionOperandRenderer::Kind::Operand,
               .Value = *Renderer.OperandIndex,
+              .ComplexRenderer = {},
               .Flags = 0,
           });
           continue;
@@ -378,6 +471,7 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) {
           NormalizedAction.OperandRenderers.push_back({
               .SourceKind = NormalizedSelectionOperandRenderer::Kind::PhysicalRegister,
               .Value = Physical->ID,
+              .ComplexRenderer = {},
               .Flags = Flags->rawValue(),
           });
           continue;
@@ -395,14 +489,32 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) {
           NormalizedAction.OperandRenderers.push_back({
               .SourceKind = NormalizedSelectionOperandRenderer::Kind::Temporary,
               .Value = Temporary->second,
+              .ComplexRenderer = {},
               .Flags = Flags->rawValue(),
           });
           continue;
         }
 
+        if (!Renderer.CapturedOperandSymbol.empty()) {
+          const auto Capture = CaptureIDs.find(Renderer.CapturedOperandSymbol);
+          if (Capture == CaptureIDs.end() || !Renderer.Flags.empty() ||
+              Renderer.ImmediateTransform != "identity") {
+            fail(Renderer.Range,
+                 "selection captured operand renderer requires a matched capture and no flags");
+            return false;
+          }
+          NormalizedAction.OperandRenderers.push_back({
+              .SourceKind = NormalizedSelectionOperandRenderer::Kind::CapturedOperand,
+              .Value = Capture->second,
+              .ComplexRenderer = {},
+              .Flags = 0,
+          });
+          continue;
+        }
+
         if (Renderer.CapturedImmediateOperand) {
-          const auto Transform = [&Renderer]()
-              -> std::optional<NormalizedSelectionImmediateTransform> {
+          const auto Transform =
+              [&Renderer]() -> std::optional<NormalizedSelectionImmediateTransform> {
             if (Renderer.ImmediateTransform == "identity")
               return NormalizedSelectionImmediateTransform::Identity;
             if (Renderer.ImmediateTransform == "negate")
@@ -421,6 +533,7 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) {
           NormalizedAction.OperandRenderers.push_back({
               .SourceKind = NormalizedSelectionOperandRenderer::Kind::CapturedImmediate,
               .Value = *Renderer.CapturedImmediateOperand,
+              .ComplexRenderer = {},
               .Flags = 0,
               .Transform = *Transform,
           });
@@ -435,6 +548,7 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) {
           NormalizedAction.OperandRenderers.push_back({
               .SourceKind = NormalizedSelectionOperandRenderer::Kind::Immediate,
               .Value = 0,
+              .ComplexRenderer = {},
               .Flags = 0,
               .Immediate = *Renderer.Immediate,
           });
@@ -458,8 +572,9 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) {
         fail(Rule.Range, "selection erased definitions require distinct register operands");
         return false;
       }
-      if (!ConstantOperands.contains(OperandIndex)) {
-        fail(Rule.Range, "selection erased definition requires a matched constant operand");
+      if (!ConstantOperands.contains(OperandIndex) && !DefUseRootOperands.contains(OperandIndex)) {
+        fail(Rule.Range,
+             "selection erased definition requires a matched constant or def-use operand");
         return false;
       }
     }
diff --git a/backend/utils/TableGen/Common/CodeGenTarget.h b/backend/utils/TableGen/Common/CodeGenTarget.h
index 42a28c1..47dd598 100644
--- a/backend/utils/TableGen/Common/CodeGenTarget.h
+++ b/backend/utils/TableGen/Common/CodeGenTarget.h
@@ -204,6 +204,18 @@ struct NormalizedSelectionOperandDefConstantPredicate final {
   std::vector<Range> Ranges;
 };
 
+struct NormalizedSelectionDefUseCapture final {
+  std::uint32_t ID = 0;
+  std::uint32_t OperandIndex = 0;
+};
+
+struct NormalizedSelectionDefUsePredicate final {
+  std::uint32_t RootOperandIndex = 0;
+  std::uint32_t Opcode = 0;
+  std::vector<NormalizedSelectionDefUseCapture> Captures;
+  std::vector<NormalizedSelectionOperandDefConstantPredicate> OperandDefConstants;
+};
+
 struct NormalizedSelectionTemporary final {
   std::uint32_t ID = 0;
   std::uint32_t TypeFromOperand = 0;
@@ -218,17 +230,19 @@ enum class NormalizedSelectionImmediateTransform : std::uint8_t {
 struct NormalizedSelectionOperandRenderer final {
   enum class Kind : std::uint8_t {
     Operand,
+    ComplexOperand,
     PhysicalRegister,
     Temporary,
+    CapturedOperand,
     CapturedImmediate,
     Immediate,
   };
 
   Kind SourceKind = Kind::Operand;
   std::uint32_t Value = 0;
+  std::string ComplexRenderer;
   std::uint16_t Flags = 0;
-  NormalizedSelectionImmediateTransform Transform =
-      NormalizedSelectionImmediateTransform::Identity;
+  NormalizedSelectionImmediateTransform Transform = NormalizedSelectionImmediateTransform::Identity;
   std::int64_t Immediate = 0;
 };
 
@@ -249,6 +263,7 @@ struct NormalizedSelectionRule final {
   std::vector<NormalizedSelectionOperandBankPredicate> OperandBanks;
   std::vector<NormalizedSelectionOperandClassPredicate> OperandClasses;
   std::vector<NormalizedSelectionOperandDefConstantPredicate> OperandDefConstants;
+  std::vector<NormalizedSelectionDefUsePredicate> DefUsePredicates;
   std::vector<NormalizedSelectionTemporary> Temporaries;
   std::vector<NormalizedSelectionAction> Actions;
   std::vector<std::uint32_t> EraseOperandDefinitions;
diff --git a/backend/utils/TableGen/GlobalISelEmitter.cpp b/backend/utils/TableGen/GlobalISelEmitter.cpp
index 784d418..562ff7c 100644
--- a/backend/utils/TableGen/GlobalISelEmitter.cpp
+++ b/backend/utils/TableGen/GlobalISelEmitter.cpp
@@ -26,9 +26,11 @@ namespace {
 
 void emitInstruction(std::ostream &Output, std::string_view Opcode, std::uint32_t OperandIndex,
                      std::uint32_t Value = 0, std::string_view Auxiliary = "0",
-                     std::int64_t Immediate = 0) {
+                     std::int64_t Immediate = 0, std::string_view Symbol = {}) {
   Output << "    {GIMatchTableOpcode::" << Opcode << ", " << OperandIndex << ", " << Value << ", "
-         << Auxiliary << ", " << Immediate << "},\n";
+         << Auxiliary << ", " << Immediate << ", ";
+  appendQuoted(Output, Symbol);
+  Output << "},\n";
 }
 
 void emitTypePredicate(std::ostream &Output, std::uint32_t OperandIndex,
@@ -39,11 +41,12 @@ void emitTypePredicate(std::ostream &Output, std::uint32_t OperandIndex,
 }
 
 [[nodiscard]] std::size_t instructionCount(const NormalizedSelectionRule &Rule) noexcept {
-  std::size_t Count = 2U + (Rule.ResultType ? 1U : 0U) +
-                      (Rule.IntegerPredicate ? 1U : 0U) +
-         Rule.OperandTypes.size() + Rule.OperandBanks.size() + Rule.OperandClasses.size() +
-                      Rule.OperandDefConstants.size() + Rule.Temporaries.size() +
-                      Rule.EraseOperandDefinitions.size();
+  std::size_t Count = 2U + (Rule.ResultType ? 1U : 0U) + (Rule.IntegerPredicate ? 1U : 0U) +
+                      Rule.OperandTypes.size() + Rule.OperandBanks.size() +
+                      Rule.OperandClasses.size() + Rule.OperandDefConstants.size() +
+                      Rule.Temporaries.size() + Rule.EraseOperandDefinitions.size();
+  for (const NormalizedSelectionDefUsePredicate &Predicate : Rule.DefUsePredicates)
+    Count += 1U + Predicate.Captures.size() + Predicate.OperandDefConstants.size();
   for (const NormalizedSelectionAction &Action : Rule.Actions)
     Count += 1U + Action.OperandRenderers.size();
   return Count;
@@ -61,6 +64,12 @@ std::string emitGlobalISel(const NormalizedTargetModel &Model, std::string_view
          Rule.OperandDefConstants) {
       ConstantRangeCount += Predicate.Ranges.size();
     }
+    for (const NormalizedSelectionDefUsePredicate &DefUse : Rule.DefUsePredicates) {
+      for (const NormalizedSelectionOperandDefConstantPredicate &Predicate :
+           DefUse.OperandDefConstants) {
+        ConstantRangeCount += Predicate.Ranges.size();
+      }
+    }
   }
 
   std::ostringstream Output;
@@ -77,6 +86,13 @@ std::string emitGlobalISel(const NormalizedTargetModel &Model, std::string_view
       for (const NormalizedSelectionOperandDefConstantPredicate::Range &Range : Predicate.Ranges)
         Output << "    {" << Range.Minimum << ", " << Range.Maximum << "},\n";
     }
+    for (const NormalizedSelectionDefUsePredicate &DefUse : Rule.DefUsePredicates) {
+      for (const NormalizedSelectionOperandDefConstantPredicate &Predicate :
+           DefUse.OperandDefConstants) {
+        for (const NormalizedSelectionOperandDefConstantPredicate::Range &Range : Predicate.Ranges)
+          Output << "    {" << Range.Minimum << ", " << Range.Maximum << "},\n";
+      }
+    }
   }
   Output << "}};\n\n";
 
@@ -103,6 +119,20 @@ std::string emitGlobalISel(const NormalizedTargetModel &Model, std::string_view
                       std::to_string(Predicate.Ranges.size()));
       FirstConstantRange += Predicate.Ranges.size();
     }
+    for (const NormalizedSelectionDefUsePredicate &DefUse : Rule.DefUsePredicates) {
+      emitInstruction(Output, "CheckOperandDefOpcode", DefUse.RootOperandIndex, DefUse.Opcode);
+      for (const NormalizedSelectionOperandDefConstantPredicate &Predicate :
+           DefUse.OperandDefConstants) {
+        emitInstruction(Output, "CheckOperandDefOperandConstantRanges", DefUse.RootOperandIndex,
+                        static_cast<std::uint32_t>(FirstConstantRange),
+                        std::to_string(Predicate.OperandIndex),
+                        static_cast<std::int64_t>(Predicate.Ranges.size()));
+        FirstConstantRange += Predicate.Ranges.size();
+      }
+      for (const NormalizedSelectionDefUseCapture &Capture : DefUse.Captures)
+        emitInstruction(Output, "CaptureDefOperand", DefUse.RootOperandIndex, Capture.ID,
+                        std::to_string(Capture.OperandIndex));
+    }
     for (const NormalizedSelectionTemporary &Temporary : Rule.Temporaries)
       emitInstruction(Output, "CreateTemporary", Temporary.TypeFromOperand, Temporary.ID);
     for (const NormalizedSelectionAction &Action : Rule.Actions) {
@@ -113,6 +143,10 @@ std::string emitGlobalISel(const NormalizedTargetModel &Model, std::string_view
         case NormalizedSelectionOperandRenderer::Kind::Operand:
           emitInstruction(Output, "RenderOperand", Renderer.Value);
           break;
+        case NormalizedSelectionOperandRenderer::Kind::ComplexOperand:
+          emitInstruction(Output, "RenderComplexOperand", Renderer.Value, 0, "0", 0,
+                          Renderer.ComplexRenderer);
+          break;
         case NormalizedSelectionOperandRenderer::Kind::PhysicalRegister:
           emitInstruction(Output, "RenderPhysicalRegister", 0, Renderer.Value,
                           std::to_string(Renderer.Flags));
@@ -121,6 +155,9 @@ std::string emitGlobalISel(const NormalizedTargetModel &Model, std::string_view
           emitInstruction(Output, "RenderTemporary", 0, Renderer.Value,
                           std::to_string(Renderer.Flags));
           break;
+        case NormalizedSelectionOperandRenderer::Kind::CapturedOperand:
+          emitInstruction(Output, "RenderCapturedOperand", 0, Renderer.Value);
+          break;
         case NormalizedSelectionOperandRenderer::Kind::CapturedImmediate:
           emitInstruction(Output, "RenderCapturedImmediate", Renderer.Value,
                           static_cast<std::uint32_t>(Renderer.Transform));