7 files changed, 1002 insertions, 0 deletions
diff --git a/backend/include/rcc/CodeGen/MachineBasicBlock.h b/backend/include/rcc/CodeGen/MachineBasicBlock.h
new file mode 100644
index 0000000..ba59160
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MachineBasicBlock.h
@@ -0,0 +1,151 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_MACHINEBASICBLOCK_H
+#define RCC_CODEGEN_MACHINEBASICBLOCK_H
+
+#include "rcc/CodeGen/MachineIRTypes.h"
+#include "rcc/CodeGen/Register.h"
+#include "rcc/CodeGen/StableID.h"
+#include "rcc/Support/Error.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <optional>
+#include <span>
+#include <vector>
+
+namespace rcc {
+
+class MachineBasicBlock;
+class MachineCFGUpdater;
+class MachineFunction;
+class MachineInstr;
+
+struct MachineSuccessor final {
+  MachineBasicBlock *Block = nullptr;
+  BranchProbability Probability;
+
+  friend bool operator==(const MachineSuccessor &Left, const MachineSuccessor &Right) = default;
+};
+
+struct MachineBasicBlockLiveIn final {
+  PhysicalRegister PhysReg;
+  LaneMask Lanes = LaneMask::all();
+
+  friend bool operator==(const MachineBasicBlockLiveIn &Left,
+                         const MachineBasicBlockLiveIn &Right) = default;
+};
+
+class MachineBasicBlock final {
+public:
+  MachineBasicBlock(const MachineBasicBlock &) = delete;
+  MachineBasicBlock &operator=(const MachineBasicBlock &) = delete;
+  MachineBasicBlock(MachineBasicBlock &&) = delete;
+  MachineBasicBlock &operator=(MachineBasicBlock &&) = delete;
+  ~MachineBasicBlock() = default;
+
+  [[nodiscard]] MachineBlockStableID stableID() const noexcept {
+    return StableID;
+  }
+
+  [[nodiscard]] MachineFunction &function() noexcept {
+    return *OwnerFunction;
+  }
+
+  [[nodiscard]] const MachineFunction &function() const noexcept {
+    return *OwnerFunction;
+  }
+
+  [[nodiscard]] bool isLinked() const noexcept {
+    return IsLinked;
+  }
+
+  [[nodiscard]] MachineBasicBlock *previous() noexcept {
+    return PreviousBlock;
+  }
+
+  [[nodiscard]] const MachineBasicBlock *previous() const noexcept {
+    return PreviousBlock;
+  }
+
+  [[nodiscard]] MachineBasicBlock *next() noexcept {
+    return NextBlock;
+  }
+
+  [[nodiscard]] const MachineBasicBlock *next() const noexcept {
+    return NextBlock;
+  }
+
+  [[nodiscard]] MachineInstr *firstInstruction() noexcept {
+    return FirstInstruction;
+  }
+
+  [[nodiscard]] const MachineInstr *firstInstruction() const noexcept {
+    return FirstInstruction;
+  }
+
+  [[nodiscard]] MachineInstr *lastInstruction() noexcept {
+    return LastInstruction;
+  }
+
+  [[nodiscard]] const MachineInstr *lastInstruction() const noexcept {
+    return LastInstruction;
+  }
+
+  [[nodiscard]] std::size_t instructionCount() const noexcept;
+  [[nodiscard]] Expected<void> appendInstruction(MachineInstr &Instruction);
+  [[nodiscard]] Expected<void> insertInstructionBefore(MachineInstr &Position,
+                                                       MachineInstr &Instruction);
+  [[nodiscard]] Expected<void> insertInstructionAfter(MachineInstr &Position,
+                                                      MachineInstr &Instruction);
+  [[nodiscard]] Expected<void> removeInstruction(MachineInstr &Instruction);
+  void clearInstructions() noexcept;
+
+  [[nodiscard]] std::span<MachineBasicBlock *const> predecessors() const noexcept {
+    return Predecessors;
+  }
+
+  [[nodiscard]] std::span<const MachineSuccessor> successors() const noexcept {
+    return Successors;
+  }
+
+  [[nodiscard]] Expected<void> addLiveIn(PhysicalRegister PhysReg,
+                                         LaneMask Lanes = LaneMask::all());
+  [[nodiscard]] Expected<void> removeLiveIn(PhysicalRegister PhysReg);
+  [[nodiscard]] std::span<const MachineBasicBlockLiveIn> liveIns() const noexcept {
+    return LiveIns;
+  }
+
+  [[nodiscard]] std::optional<std::uint32_t> denseNumber() const noexcept {
+    return DenseNumber;
+  }
+
+  [[nodiscard]] std::optional<std::uint32_t> layoutIndex() const noexcept {
+    return LayoutIndex;
+  }
+
+private:
+  MachineBasicBlock(MachineFunction &OwnerFunction, MachineBlockStableID StableID)
+      : OwnerFunction(&OwnerFunction), StableID(StableID) {}
+
+  MachineFunction *OwnerFunction;
+  MachineBlockStableID StableID;
+  bool IsLinked = false;
+  MachineBasicBlock *PreviousBlock = nullptr;
+  MachineBasicBlock *NextBlock = nullptr;
+  MachineInstr *FirstInstruction = nullptr;
+  MachineInstr *LastInstruction = nullptr;
+  std::vector<MachineBasicBlock *> Predecessors;
+  std::vector<MachineSuccessor> Successors;
+  std::vector<MachineBasicBlockLiveIn> LiveIns;
+  std::optional<std::uint32_t> DenseNumber;
+  std::optional<std::uint32_t> LayoutIndex;
+
+  friend class MachineArena;
+  friend class MachineCFGUpdater;
+  friend class MachineFunction;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_MACHINEBASICBLOCK_H
diff --git a/backend/include/rcc/CodeGen/MachineCFGUpdater.h b/backend/include/rcc/CodeGen/MachineCFGUpdater.h
new file mode 100644
index 0000000..4359538
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MachineCFGUpdater.h
@@ -0,0 +1,39 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_MACHINECFGUPDATER_H
+#define RCC_CODEGEN_MACHINECFGUPDATER_H
+
+#include "rcc/CodeGen/MachineIRTypes.h"
+#include "rcc/Support/Error.h"
+
+namespace rcc {
+
+class MachineBasicBlock;
+class MachineFunction;
+
+class MachineCFGUpdater final {
+public:
+  explicit MachineCFGUpdater(MachineFunction &Function) noexcept : Function(&Function) {}
+
+  [[nodiscard]] Expected<void>
+  addSuccessor(MachineBasicBlock &From, MachineBasicBlock &To,
+               BranchProbability Probability = BranchProbability::zero());
+  [[nodiscard]] Expected<void> removeSuccessor(MachineBasicBlock &From, MachineBasicBlock &To);
+  [[nodiscard]] Expected<void> replaceSuccessor(MachineBasicBlock &From,
+                                                MachineBasicBlock &OldTarget,
+                                                MachineBasicBlock &NewTarget);
+  [[nodiscard]] Expected<void> updateBranchProbability(MachineBasicBlock &From,
+                                                       MachineBasicBlock &To,
+                                                       BranchProbability Probability);
+  [[nodiscard]] Expected<void> transferSuccessors(MachineBasicBlock &From, MachineBasicBlock &To);
+  [[nodiscard]] Expected<void> disconnectBlock(MachineBasicBlock &Block);
+
+private:
+  [[nodiscard]] Expected<void> verifyOwnership(const MachineBasicBlock &Block) const;
+
+  MachineFunction *Function;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_MACHINECFGUPDATER_H
diff --git a/backend/include/rcc/CodeGen/MachineFunction.h b/backend/include/rcc/CodeGen/MachineFunction.h
new file mode 100644
index 0000000..487fb5b
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MachineFunction.h
@@ -0,0 +1,130 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_MACHINEFUNCTION_H
+#define RCC_CODEGEN_MACHINEFUNCTION_H
+
+#include "rcc/CodeGen/MachineFunctionProperties.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/StableID.h"
+#include "rcc/Support/Error.h"
+
+#include <cstddef>
+#include <memory>
+#include <span>
+#include <string>
+#include <string_view>
+#include <vector>
+
+namespace rcc {
+
+class MachineArena;
+class MachineBasicBlock;
+class MachineCFGUpdater;
+class MachineInstr;
+class MachineMemOperand;
+struct MachineMemOperandDesc;
+class Opcode;
+
+class MachineFunction final {
+public:
+  [[nodiscard]] static Expected<std::unique_ptr<MachineFunction>>
+  create(std::string Name, MachineFunctionStableID StableID);
+
+  MachineFunction(const MachineFunction &) = delete;
+  MachineFunction &operator=(const MachineFunction &) = delete;
+  MachineFunction(MachineFunction &&) = delete;
+  MachineFunction &operator=(MachineFunction &&) = delete;
+  ~MachineFunction();
+
+  [[nodiscard]] std::string_view name() const noexcept {
+    return Name;
+  }
+
+  [[nodiscard]] MachineFunctionStableID stableID() const noexcept {
+    return StableID;
+  }
+
+  [[nodiscard]] MachineRegisterInfo &registerInfo() noexcept {
+    return RegInfo;
+  }
+
+  [[nodiscard]] const MachineRegisterInfo &registerInfo() const noexcept {
+    return RegInfo;
+  }
+
+  [[nodiscard]] MachineFunctionProperties &properties() noexcept {
+    return Properties;
+  }
+
+  [[nodiscard]] const MachineFunctionProperties &properties() const noexcept {
+    return Properties;
+  }
+
+  [[nodiscard]] Expected<MachineBasicBlock *> createBasicBlock();
+  [[nodiscard]] Expected<MachineInstr *> createInstruction(Opcode InstructionOpcode);
+  [[nodiscard]] Expected<const MachineMemOperand *>
+  createMemOperand(MachineMemOperandDesc Description);
+
+  [[nodiscard]] Expected<void> appendBlock(MachineBasicBlock &Block);
+  [[nodiscard]] Expected<void> insertBlockBefore(MachineBasicBlock &Position,
+                                                 MachineBasicBlock &Block);
+  [[nodiscard]] Expected<void> removeBlock(MachineBasicBlock &Block);
+
+  [[nodiscard]] MachineBasicBlock *firstBlock() noexcept {
+    return FirstBlock;
+  }
+
+  [[nodiscard]] const MachineBasicBlock *firstBlock() const noexcept {
+    return FirstBlock;
+  }
+
+  [[nodiscard]] MachineBasicBlock *lastBlock() noexcept {
+    return LastBlock;
+  }
+
+  [[nodiscard]] const MachineBasicBlock *lastBlock() const noexcept {
+    return LastBlock;
+  }
+
+  [[nodiscard]] std::size_t blockCount() const noexcept;
+  [[nodiscard]] std::span<MachineBasicBlock *const> allBlocks() const noexcept {
+    return AllBlocks;
+  }
+
+  [[nodiscard]] std::span<MachineInstr *const> allInstructions() const noexcept {
+    return AllInstructions;
+  }
+
+  [[nodiscard]] std::span<const MachineMemOperand *const> allMemOperands() const noexcept {
+    return AllMemOperands;
+  }
+
+  [[nodiscard]] bool ownsMemOperand(const MachineMemOperand &MemOperand) const noexcept;
+
+  [[nodiscard]] MachineCFGUpdater cfgUpdater() noexcept;
+  void renumberBlocks() noexcept;
+
+private:
+  MachineFunction(std::string Name, MachineFunctionStableID StableID);
+
+  std::string Name;
+  MachineFunctionStableID StableID;
+  MachineRegisterInfo RegInfo;
+  MachineFunctionProperties Properties;
+  MachineBasicBlock *FirstBlock = nullptr;
+  MachineBasicBlock *LastBlock = nullptr;
+  std::vector<MachineBasicBlock *> AllBlocks;
+  std::vector<MachineInstr *> AllInstructions;
+  std::vector<const MachineMemOperand *> AllMemOperands;
+  StableIDGenerator<MachineBlockStableID> BlockIDGenerator;
+  StableIDGenerator<MachineInstrStableID> InstrIDGenerator;
+  std::unique_ptr<MachineArena> Arena;
+
+  friend class MachineBasicBlock;
+  friend class MachineCFGUpdater;
+  friend class MachineInstr;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_MACHINEFUNCTION_H
diff --git a/backend/include/rcc/CodeGen/MachineInstr.h b/backend/include/rcc/CodeGen/MachineInstr.h
new file mode 100644
index 0000000..376273f
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MachineInstr.h
@@ -0,0 +1,164 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_MACHINEINSTR_H
+#define RCC_CODEGEN_MACHINEINSTR_H
+
+#include "rcc/CodeGen/MachineIRTypes.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/StableID.h"
+#include "rcc/Support/Error.h"
+
+#include <cstddef>
+#include <functional>
+#include <optional>
+#include <span>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+
+class MachineBasicBlock;
+class MachineFunction;
+class MachineMemOperand;
+class MachineRegisterInfo;
+
+class MachineInstr final {
+public:
+  MachineInstr(const MachineInstr &) = delete;
+  MachineInstr &operator=(const MachineInstr &) = delete;
+  MachineInstr(MachineInstr &&) = delete;
+  MachineInstr &operator=(MachineInstr &&) = delete;
+  ~MachineInstr();
+
+  [[nodiscard]] Opcode opcode() const noexcept {
+    return InstructionOpcode;
+  }
+
+  [[nodiscard]] Expected<void> setOpcode(Opcode NewOpcode);
+
+  [[nodiscard]] MachineInstrStableID stableID() const noexcept {
+    return StableID;
+  }
+
+  [[nodiscard]] MachineFunction &function() noexcept {
+    return *OwnerFunction;
+  }
+
+  [[nodiscard]] const MachineFunction &function() const noexcept {
+    return *OwnerFunction;
+  }
+
+  [[nodiscard]] MachineBasicBlock *parent() noexcept {
+    return ParentBlock;
+  }
+
+  [[nodiscard]] const MachineBasicBlock *parent() const noexcept {
+    return ParentBlock;
+  }
+
+  [[nodiscard]] MachineInstr *previous() noexcept {
+    return PreviousInstruction;
+  }
+
+  [[nodiscard]] const MachineInstr *previous() const noexcept {
+    return PreviousInstruction;
+  }
+
+  [[nodiscard]] MachineInstr *next() noexcept {
+    return NextInstruction;
+  }
+
+  [[nodiscard]] const MachineInstr *next() const noexcept {
+    return NextInstruction;
+  }
+
+  [[nodiscard]] bool isLinked() const noexcept {
+    return ParentBlock != nullptr;
+  }
+
+  [[nodiscard]] std::size_t operandCount() const noexcept {
+    return Operands.size();
+  }
+
+  [[nodiscard]] MachineOperand *operandAt(std::size_t Index) noexcept;
+  [[nodiscard]] const MachineOperand *operandAt(std::size_t Index) const noexcept;
+  [[nodiscard]] std::span<const MachineOperand> operands() const noexcept {
+    return Operands;
+  }
+
+  void reserveOperands(std::size_t Capacity);
+  [[nodiscard]] Expected<void> addOperand(MachineOperand Operand);
+  [[nodiscard]] Expected<void> insertOperand(std::size_t Index, MachineOperand Operand);
+  [[nodiscard]] Expected<void> eraseOperand(std::size_t Index);
+
+  [[nodiscard]] Expected<void> tieOperands(std::size_t DefIndex, std::size_t UseIndex);
+  [[nodiscard]] Expected<void> untieOperand(std::size_t Index);
+
+  [[nodiscard]] Expected<void> addMemOperand(const MachineMemOperand &MemOperand);
+  [[nodiscard]] Expected<void> eraseMemOperand(std::size_t Index);
+  [[nodiscard]] std::span<const MachineMemOperand *const> memOperands() const noexcept {
+    return MemOperands;
+  }
+
+  [[nodiscard]] MachineInstrFlags flags() const noexcept {
+    return Flags;
+  }
+
+  void setFlags(MachineInstrFlags NewFlags) noexcept {
+    Flags = NewFlags;
+  }
+
+  [[nodiscard]] const std::optional<SourceLocation> &sourceLocation() const noexcept {
+    return Location;
+  }
+
+  void setSourceLocation(SourceLocation NewLocation) {
+    Location = std::move(NewLocation);
+  }
+
+  void clearSourceLocation() noexcept {
+    Location.reset();
+  }
+
+  [[nodiscard]] std::optional<OriginID> origin() const noexcept {
+    return Origin;
+  }
+
+  void setOrigin(OriginID NewOrigin) noexcept {
+    Origin = NewOrigin;
+  }
+
+  void clearOrigin() noexcept {
+    Origin.reset();
+  }
+
+private:
+  MachineInstr(MachineFunction &OwnerFunction, Opcode InstructionOpcode,
+               MachineInstrStableID StableID);
+
+  [[nodiscard]] MachineRegisterInfo *linkedRegisterInfo() noexcept;
+  [[nodiscard]] Expected<void> attachToBlock(MachineBasicBlock &Block);
+  void detachFromBlock() noexcept;
+  void adjustTiesForInsertion(std::size_t Index) noexcept;
+  void adjustTiesForErasure(std::size_t Index) noexcept;
+
+  MachineFunction *OwnerFunction;
+  Opcode InstructionOpcode;
+  MachineInstrStableID StableID;
+  MachineBasicBlock *ParentBlock = nullptr;
+  MachineInstr *PreviousInstruction = nullptr;
+  MachineInstr *NextInstruction = nullptr;
+  std::vector<MachineOperand> Operands;
+  std::vector<const MachineMemOperand *> MemOperands;
+  MachineInstrFlags Flags;
+  std::optional<SourceLocation> Location;
+  std::optional<OriginID> Origin;
+
+  friend class MachineArena;
+  friend class MachineBasicBlock;
+  friend class MachineFunction;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_MACHINEINSTR_H
diff --git a/backend/include/rcc/CodeGen/MachineMemOperand.h b/backend/include/rcc/CodeGen/MachineMemOperand.h
index 52514f9..e513385 100644
--- a/backend/include/rcc/CodeGen/MachineMemOperand.h
+++ b/backend/include/rcc/CodeGen/MachineMemOperand.h
@@ -207,6 +207,12 @@ struct MachineMemOperandDesc final {
 
 class MachineMemOperand final {
 public:
+  MachineMemOperand(const MachineMemOperand &) = default;
+  MachineMemOperand &operator=(const MachineMemOperand &) = default;
+  MachineMemOperand(MachineMemOperand &&) noexcept = default;
+  MachineMemOperand &operator=(MachineMemOperand &&) noexcept = default;
+  ~MachineMemOperand() = default;
+
   [[nodiscard]] static Expected<MachineMemOperand> create(MachineMemOperandDesc Description);
 
   [[nodiscard]] const MachineMemOperandDesc &description() const noexcept {
diff --git a/backend/include/rcc/CodeGen/MachineOperand.h b/backend/include/rcc/CodeGen/MachineOperand.h
new file mode 100644
index 0000000..0da9f25
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MachineOperand.h
@@ -0,0 +1,344 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_MACHINEOPERAND_H
+#define RCC_CODEGEN_MACHINEOPERAND_H
+
+#include "rcc/CodeGen/LowLevelType.h"
+#include "rcc/CodeGen/MachineIRTypes.h"
+#include "rcc/CodeGen/Register.h"
+#include "rcc/CodeGen/RegisterMask.h"
+#include "rcc/Support/Error.h"
+
+#include <array>
+#include <cstddef>
+#include <cstdint>
+#include <initializer_list>
+#include <memory>
+#include <optional>
+#include <span>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <variant>
+
+namespace rcc {
+
+class MachineBasicBlock;
+class MachineInstr;
+class MachineRegisterInfo;
+class RegOperandIterator;
+
+class FloatingPointBits final {
+public:
+  [[nodiscard]] static Expected<FloatingPointBits> create(FloatSemantics Semantics,
+                                                          std::span<const std::uint64_t> Words);
+
+  [[nodiscard]] FloatSemantics semantics() const noexcept {
+    return Semantics;
+  }
+
+  [[nodiscard]] std::uint32_t bitWidth() const noexcept {
+    return getFloatSemanticsBitWidth(Semantics).value_or(0);
+  }
+
+  [[nodiscard]] std::span<const std::uint64_t> words() const noexcept {
+    return std::span(Words).first(WordCount);
+  }
+
+  friend bool operator==(const FloatingPointBits &Left, const FloatingPointBits &Right) = default;
+
+private:
+  FloatingPointBits(FloatSemantics Semantics, std::array<std::uint64_t, 2> Words,
+                    std::uint8_t WordCount) noexcept
+      : Semantics(Semantics), Words(Words), WordCount(WordCount) {}
+
+  FloatSemantics Semantics;
+  std::array<std::uint64_t, 2> Words;
+  std::uint8_t WordCount;
+};
+
+enum class RegisterOperandFlag : std::uint8_t {
+  Define,
+  Use,
+  Implicit,
+  Kill,
+  Dead,
+  Undef,
+  EarlyClobber,
+  InternalRead,
+  Renamable,
+  Debug,
+  Count,
+};
+
+class RegisterOperandFlags final {
+public:
+  constexpr RegisterOperandFlags() noexcept = default;
+
+  RegisterOperandFlags(std::initializer_list<RegisterOperandFlag> Flags) noexcept;
+
+  [[nodiscard]] constexpr bool has(RegisterOperandFlag Flag) const noexcept {
+    const auto Index = static_cast<std::uint16_t>(Flag);
+    if (Index >= static_cast<std::uint16_t>(RegisterOperandFlag::Count))
+      return false;
+    return (Mask & (std::uint16_t{1} << Index)) != 0;
+  }
+
+  constexpr void set(RegisterOperandFlag Flag) noexcept {
+    const auto Index = static_cast<std::uint16_t>(Flag);
+    if (Index < static_cast<std::uint16_t>(RegisterOperandFlag::Count))
+      Mask |= std::uint16_t{1} << Index;
+  }
+
+  constexpr void clear(RegisterOperandFlag Flag) noexcept {
+    const auto Index = static_cast<std::uint16_t>(Flag);
+    if (Index < static_cast<std::uint16_t>(RegisterOperandFlag::Count))
+      Mask &= static_cast<std::uint16_t>(~(std::uint16_t{1} << Index));
+  }
+
+  [[nodiscard]] constexpr std::uint16_t rawValue() const noexcept {
+    return Mask;
+  }
+
+  friend constexpr bool operator==(RegisterOperandFlags Left,
+                                   RegisterOperandFlags Right) noexcept = default;
+
+private:
+  std::uint16_t Mask = 0;
+};
+
+struct FloatingImmediateOperand final {
+  FloatingPointBits Bits;
+
+  friend bool operator==(const FloatingImmediateOperand &Left,
+                         const FloatingImmediateOperand &Right) = default;
+};
+
+struct BasicBlockOperand final {
+  MachineBasicBlock *Block = nullptr;
+
+  friend bool operator==(BasicBlockOperand Left, BasicBlockOperand Right) noexcept = default;
+};
+
+struct FrameIndexOperand final {
+  FrameIndex Index;
+  std::int64_t Offset = 0;
+
+  friend constexpr bool operator==(FrameIndexOperand Left,
+                                   FrameIndexOperand Right) noexcept = default;
+};
+
+struct ConstantPoolOperand final {
+  ConstantPoolIndex Index;
+  std::int64_t Offset = 0;
+
+  friend constexpr bool operator==(ConstantPoolOperand Left,
+                                   ConstantPoolOperand Right) noexcept = default;
+};
+
+struct JumpTableOperand final {
+  JumpTableIndex Index;
+
+  friend constexpr bool operator==(JumpTableOperand Left,
+                                   JumpTableOperand Right) noexcept = default;
+};
+
+struct GlobalSymbolOperand final {
+  std::string Name;
+  std::int64_t Offset = 0;
+
+  friend bool operator==(const GlobalSymbolOperand &Left,
+                         const GlobalSymbolOperand &Right) = default;
+};
+
+struct ExternalSymbolOperand final {
+  std::string Name;
+  std::int64_t Offset = 0;
+
+  friend bool operator==(const ExternalSymbolOperand &Left,
+                         const ExternalSymbolOperand &Right) = default;
+};
+
+struct BlockAddressOperand final {
+  std::string FunctionName;
+  std::string BlockName;
+  std::int64_t Offset = 0;
+
+  friend bool operator==(const BlockAddressOperand &Left,
+                         const BlockAddressOperand &Right) = default;
+};
+
+struct RegisterMaskOperand final {
+  std::shared_ptr<const RegisterMask> Mask;
+
+  friend bool operator==(const RegisterMaskOperand &Left,
+                         const RegisterMaskOperand &Right) = default;
+};
+
+struct MetadataOperand final {
+  std::string Marker;
+
+  friend bool operator==(const MetadataOperand &Left, const MetadataOperand &Right) = default;
+};
+
+struct TargetIndexOperand final {
+  TargetIndex Index;
+  std::int64_t Offset = 0;
+
+  friend constexpr bool operator==(TargetIndexOperand Left,
+                                   TargetIndexOperand Right) noexcept = default;
+};
+
+struct MCSymbolOperand final {
+  std::string Name;
+  std::int64_t Offset = 0;
+
+  friend bool operator==(const MCSymbolOperand &Left, const MCSymbolOperand &Right) = default;
+};
+
+class MachineOperand final {
+public:
+  enum class Kind : std::uint8_t {
+    Register,
+    Immediate,
+    FloatingImmediate,
+    BasicBlock,
+    FrameIndex,
+    ConstantPoolIndex,
+    JumpTableIndex,
+    GlobalSymbol,
+    ExternalSymbol,
+    BlockAddress,
+    RegisterMask,
+    Metadata,
+    TargetIndex,
+    MCSymbol,
+  };
+
+  MachineOperand(const MachineOperand &) = delete;
+  MachineOperand &operator=(const MachineOperand &) = delete;
+  MachineOperand(MachineOperand &&Other) noexcept;
+  MachineOperand &operator=(MachineOperand &&Other) noexcept;
+  ~MachineOperand();
+
+  [[nodiscard]] static Expected<MachineOperand> registerOperand(Register Reg,
+                                                                RegisterOperandFlags Flags,
+                                                                SubRegIndex SubReg = {},
+                                                                std::uint32_t TargetFlags = 0);
+  [[nodiscard]] static MachineOperand immediate(std::int64_t Value, std::uint32_t TargetFlags = 0);
+  [[nodiscard]] static MachineOperand floatingImmediate(FloatingPointBits Bits,
+                                                        std::uint32_t TargetFlags = 0);
+  [[nodiscard]] static MachineOperand basicBlock(MachineBasicBlock &Block,
+                                                 std::uint32_t TargetFlags = 0);
+  [[nodiscard]] static MachineOperand frameIndex(FrameIndex Index, std::int64_t Offset = 0,
+                                                 std::uint32_t TargetFlags = 0);
+  [[nodiscard]] static MachineOperand constantPool(ConstantPoolIndex Index, std::int64_t Offset = 0,
+                                                   std::uint32_t TargetFlags = 0);
+  [[nodiscard]] static MachineOperand jumpTable(JumpTableIndex Index,
+                                                std::uint32_t TargetFlags = 0);
+  [[nodiscard]] static Expected<MachineOperand>
+  globalSymbol(std::string Name, std::int64_t Offset = 0, std::uint32_t TargetFlags = 0);
+  [[nodiscard]] static Expected<MachineOperand>
+  externalSymbol(std::string Name, std::int64_t Offset = 0, std::uint32_t TargetFlags = 0);
+  [[nodiscard]] static Expected<MachineOperand> blockAddress(std::string FunctionName,
+                                                             std::string BlockName,
+                                                             std::int64_t Offset = 0,
+                                                             std::uint32_t TargetFlags = 0);
+  [[nodiscard]] static Expected<MachineOperand>
+  registerMask(std::shared_ptr<const RegisterMask> Mask, std::uint32_t TargetFlags = 0);
+  [[nodiscard]] static Expected<MachineOperand> metadata(std::string Marker,
+                                                         std::uint32_t TargetFlags = 0);
+  [[nodiscard]] static MachineOperand targetIndex(TargetIndex Index, std::int64_t Offset = 0,
+                                                  std::uint32_t TargetFlags = 0);
+  [[nodiscard]] static Expected<MachineOperand> mcSymbol(std::string Name, std::int64_t Offset = 0,
+                                                         std::uint32_t TargetFlags = 0);
+
+  [[nodiscard]] Kind kind() const noexcept {
+    return OperandKind;
+  }
+
+  [[nodiscard]] bool isRegister() const noexcept {
+    return OperandKind == Kind::Register;
+  }
+
+  [[nodiscard]] std::optional<Register> registerValue() const noexcept;
+  [[nodiscard]] RegisterOperandFlags registerFlags() const noexcept {
+    return RegFlags;
+  }
+  [[nodiscard]] SubRegIndex subReg() const noexcept {
+    return RegSubReg;
+  }
+  [[nodiscard]] bool isDef() const noexcept;
+  [[nodiscard]] bool isUse() const noexcept;
+  [[nodiscard]] bool isDebugUse() const noexcept;
+  [[nodiscard]] bool isImplicit() const noexcept;
+
+  [[nodiscard]] Expected<void> setRegister(Register Reg);
+  [[nodiscard]] Expected<void> setRegisterFlags(RegisterOperandFlags Flags);
+  [[nodiscard]] Expected<void> setSubReg(SubRegIndex SubReg);
+
+  [[nodiscard]] std::optional<std::size_t> tiedOperandIndex() const noexcept {
+    return TiedOperandIndex;
+  }
+
+  [[nodiscard]] std::uint32_t targetFlags() const noexcept {
+    return TargetFlags;
+  }
+
+  void setTargetFlags(std::uint32_t NewTargetFlags) noexcept {
+    TargetFlags = NewTargetFlags;
+  }
+
+  [[nodiscard]] MachineInstr *parent() noexcept {
+    return Parent;
+  }
+
+  [[nodiscard]] const MachineInstr *parent() const noexcept {
+    return Parent;
+  }
+
+  template <typename PayloadT> [[nodiscard]] const PayloadT *getIf() const noexcept {
+    return std::get_if<PayloadT>(&Storage);
+  }
+
+  [[nodiscard]] MachineOperand cloneDetached() const;
+
+private:
+  using OperandStorage =
+      std::variant<Register, std::int64_t, FloatingImmediateOperand, BasicBlockOperand,
+                   FrameIndexOperand, ConstantPoolOperand, JumpTableOperand, GlobalSymbolOperand,
+                   ExternalSymbolOperand, BlockAddressOperand, RegisterMaskOperand, MetadataOperand,
+                   TargetIndexOperand, MCSymbolOperand>;
+
+  MachineOperand(Kind OperandKind, OperandStorage Storage, std::uint32_t TargetFlags = 0)
+      : OperandKind(OperandKind), Storage(std::move(Storage)), TargetFlags(TargetFlags) {}
+
+  [[nodiscard]] static Expected<void> verifyRegisterFlags(RegisterOperandFlags Flags);
+  void attachTo(MachineInstr &Instruction, MachineRegisterInfo *RegInfo);
+  void detachFromInstruction() noexcept;
+  void linkToRegInfo(MachineRegisterInfo &RegInfo);
+  void unlinkFromRegInfo() noexcept;
+  void takeRegLinkFrom(MachineOperand &Other) noexcept;
+  void setTiedOperandIndex(std::optional<std::size_t> Index) noexcept {
+    TiedOperandIndex = Index;
+  }
+
+  Kind OperandKind;
+  OperandStorage Storage;
+  RegisterOperandFlags RegFlags;
+  SubRegIndex RegSubReg;
+  std::optional<std::size_t> TiedOperandIndex;
+  std::uint32_t TargetFlags = 0;
+  MachineInstr *Parent = nullptr;
+  MachineRegisterInfo *LinkedRegInfo = nullptr;
+  MachineOperand **PreviousRegLink = nullptr;
+  MachineOperand *NextRegOperand = nullptr;
+
+  friend class MachineInstr;
+  friend class MachineRegisterInfo;
+  friend class RegOperandIterator;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_MACHINEOPERAND_H
diff --git a/backend/include/rcc/CodeGen/MachineRegisterInfo.h b/backend/include/rcc/CodeGen/MachineRegisterInfo.h
new file mode 100644
index 0000000..495853a
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MachineRegisterInfo.h
@@ -0,0 +1,168 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_MACHINEREGISTERINFO_H
+#define RCC_CODEGEN_MACHINEREGISTERINFO_H
+
+#include "rcc/CodeGen/LowLevelType.h"
+#include "rcc/CodeGen/MachineIRTypes.h"
+#include "rcc/CodeGen/Register.h"
+#include "rcc/Support/Error.h"
+
+#include <cstddef>
+#include <functional>
+#include <iterator>
+#include <memory>
+#include <optional>
+#include <span>
+#include <unordered_map>
+#include <vector>
+
+namespace rcc {
+
+class MachineOperand;
+
+class RegOperandIterator final {
+public:
+  using difference_type = std::ptrdiff_t; // NOLINT(readability-identifier-naming)
+  using value_type = MachineOperand;      // NOLINT(readability-identifier-naming)
+  using pointer = MachineOperand *;       // NOLINT(readability-identifier-naming)
+  using reference = MachineOperand &;     // NOLINT(readability-identifier-naming)
+  using iterator_category =               // NOLINT(readability-identifier-naming)
+      std::forward_iterator_tag;
+
+  RegOperandIterator() = default;
+
+  [[nodiscard]] reference operator*() const noexcept;
+  [[nodiscard]] pointer operator->() const noexcept;
+  RegOperandIterator &operator++() noexcept;
+  RegOperandIterator operator++(int) noexcept;
+
+  friend bool operator==(const RegOperandIterator &Left, const RegOperandIterator &Right) noexcept {
+    return Left.Current == Right.Current;
+  }
+
+private:
+  RegOperandIterator(MachineOperand *Current, bool RequireUse, bool RequireDef,
+                     bool SkipDebug) noexcept;
+
+  void skipFiltered() noexcept;
+
+  MachineOperand *Current = nullptr;
+  bool RequireUse = false;
+  bool RequireDef = false;
+  bool SkipDebug = false;
+
+  friend class RegOperandRange;
+  friend class MachineRegisterInfo;
+};
+
+class RegOperandRange final {
+public:
+  [[nodiscard]] RegOperandIterator begin() const noexcept {
+    return RegOperandIterator(Head, RequireUse, RequireDef, SkipDebug);
+  }
+
+  [[nodiscard]] RegOperandIterator end() const noexcept {
+    return {};
+  }
+
+private:
+  RegOperandRange(MachineOperand *Head, bool RequireUse, bool RequireDef, bool SkipDebug) noexcept
+      : Head(Head), RequireUse(RequireUse), RequireDef(RequireDef), SkipDebug(SkipDebug) {}
+
+  MachineOperand *Head = nullptr;
+  bool RequireUse = false;
+  bool RequireDef = false;
+  bool SkipDebug = false;
+
+  friend class MachineRegisterInfo;
+};
+
+struct VirtualRegisterInfo final {
+  std::optional<LLT> Type;
+  std::optional<RegisterBankID> Bank;
+  std::optional<RegisterClassID> RegClass;
+  std::vector<PhysicalRegister> AllocationHints;
+  bool IsTombstone = false;
+};
+
+struct PhysicalRegisterLiveIn final {
+  PhysicalRegister PhysReg;
+  std::optional<Register> InitialVirtualRegister;
+
+  friend bool operator==(const PhysicalRegisterLiveIn &Left,
+                         const PhysicalRegisterLiveIn &Right) = default;
+};
+
+class MachineRegisterInfo final {
+public:
+  MachineRegisterInfo() = default;
+  MachineRegisterInfo(const MachineRegisterInfo &) = delete;
+  MachineRegisterInfo &operator=(const MachineRegisterInfo &) = delete;
+  MachineRegisterInfo(MachineRegisterInfo &&) = delete;
+  MachineRegisterInfo &operator=(MachineRegisterInfo &&) = delete;
+  ~MachineRegisterInfo();
+
+  [[nodiscard]] Expected<Register> createVirtualRegister();
+  [[nodiscard]] Expected<Register> createVirtualRegister(LLT Type);
+  [[nodiscard]] Expected<void> eraseVirtualRegister(Register Reg);
+
+  [[nodiscard]] bool isKnownVirtualRegister(Register Reg) const noexcept;
+  [[nodiscard]] Expected<std::reference_wrapper<VirtualRegisterInfo>>
+  virtualRegisterInfo(Register Reg);
+  [[nodiscard]] Expected<std::reference_wrapper<const VirtualRegisterInfo>>
+  virtualRegisterInfo(Register Reg) const;
+
+  [[nodiscard]] Expected<void> setType(Register Reg, LLT Type);
+  [[nodiscard]] Expected<void> clearType(Register Reg);
+  [[nodiscard]] Expected<void> setRegisterBank(Register Reg, RegisterBankID Bank);
+  [[nodiscard]] Expected<void> clearRegisterBank(Register Reg);
+  [[nodiscard]] Expected<void> setRegisterClass(Register Reg, RegisterClassID RegClass);
+  [[nodiscard]] Expected<void> clearRegisterClass(Register Reg);
+  [[nodiscard]] Expected<void> addAllocationHint(Register Reg, PhysicalRegister Hint);
+  void clearAllVirtualRegisterTypes() noexcept;
+
+  [[nodiscard]] Expected<void>
+  addLiveIn(PhysicalRegister PhysReg,
+            std::optional<Register> InitialVirtualRegister = std::nullopt);
+  [[nodiscard]] std::span<const PhysicalRegisterLiveIn> liveIns() const noexcept {
+    return LiveIns;
+  }
+
+  [[nodiscard]] Expected<void> reservePhysicalRegister(PhysicalRegister PhysReg);
+  [[nodiscard]] bool isReserved(PhysicalRegister PhysReg) const noexcept;
+  [[nodiscard]] std::span<const PhysicalRegister> reservedRegisters() const noexcept {
+    return ReservedRegisters;
+  }
+
+  [[nodiscard]] RegOperandRange regOperands(Register Reg) noexcept;
+  [[nodiscard]] RegOperandRange regNoDebugOperands(Register Reg) noexcept;
+  [[nodiscard]] RegOperandRange useOperands(Register Reg, bool IncludeDebug = true) noexcept;
+  [[nodiscard]] RegOperandRange defOperands(Register Reg) noexcept;
+
+  [[nodiscard]] bool useEmpty(Register Reg, bool IncludeDebug = true) const noexcept;
+  [[nodiscard]] bool hasOneUse(Register Reg, bool IncludeDebug = true) const noexcept;
+  [[nodiscard]] const MachineOperand *getUniqueVRegDef(Register Reg) const noexcept;
+  [[nodiscard]] Expected<std::size_t> replaceRegWith(Register OldReg, Register NewReg);
+
+  [[nodiscard]] Expected<void> verifyDefUseChains() const;
+
+private:
+  struct RegOperandListHead final {
+    MachineOperand *Head = nullptr;
+  };
+
+  [[nodiscard]] MachineOperand *headFor(Register Reg) const noexcept;
+  void linkOperand(MachineOperand &Operand);
+
+  std::vector<VirtualRegisterInfo> VirtualRegisters;
+  std::vector<PhysicalRegisterLiveIn> LiveIns;
+  std::vector<PhysicalRegister> ReservedRegisters;
+  std::unordered_map<Register, std::unique_ptr<RegOperandListHead>> DefUseHeads;
+
+  friend class MachineOperand;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_MACHINEREGISTERINFO_H