[CodeGen] Build the core MachineIR object model

Add arena-owned, address-stable MachineFunction, MachineBasicBlock, and MachineInstr nodes with intrusive layout and instruction lists. Model every required MachineOperand category, reciprocal ties, source state, and immutable per-instruction memory references.

Implement physical and virtual register def-use chains whose back-links survive operand vector moves, plus vreg properties, tombstones, live-ins, reserved registers, and atomic CFG updates. Exercise ownership, reallocation, unlink/relink, cross-function rejection, and sanitizer paths.

16 files changed, 2935 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
diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt
index 8a45878..ffa5e82 100644
--- a/backend/lib/CodeGen/CMakeLists.txt
+++ b/backend/lib/CodeGen/CMakeLists.txt
@@ -3,8 +3,14 @@
 set(
   RCCBackendCodeGenSources
   LowLevelType.cpp
+  MachineBasicBlock.cpp
+  MachineCFGUpdater.cpp
+  MachineFunction.cpp
   MachineIRTypes.cpp
+  MachineInstr.cpp
   MachineMemOperand.cpp
+  MachineOperand.cpp
+  MachineRegisterInfo.cpp
   MachineFunctionProperties.cpp
   Register.cpp
   RegisterMask.cpp
@@ -12,8 +18,14 @@ set(
 set(
   RCCBackendCodeGenHeaders
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LowLevelType.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineBasicBlock.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineCFGUpdater.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunction.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineIRTypes.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineInstr.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineMemOperand.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineOperand.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineRegisterInfo.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunctionProperties.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/Register.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegisterMask.h"
@@ -50,8 +62,14 @@ install(
 
 rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/LowLevelType.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineBasicBlock.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineCFGUpdater.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunction.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRTypes.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineInstr.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineMemOperand.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperand.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/Register.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegisterMask.cpp"
@@ -59,8 +77,14 @@ rcc_backend_register_format_files(
 )
 rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/LowLevelType.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineBasicBlock.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineCFGUpdater.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunction.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRTypes.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineInstr.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineMemOperand.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperand.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/Register.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegisterMask.cpp"
diff --git a/backend/lib/CodeGen/MachineBasicBlock.cpp b/backend/lib/CodeGen/MachineBasicBlock.cpp
new file mode 100644
index 0000000..a8d69f6
--- /dev/null
+++ b/backend/lib/CodeGen/MachineBasicBlock.cpp
@@ -0,0 +1,157 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineBasicBlock.h"
+
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+
+#include <algorithm>
+#include <cstddef>
+
+namespace rcc {
+
+std::size_t MachineBasicBlock::instructionCount() const noexcept {
+  std::size_t Count = 0;
+  for (const MachineInstr *Instruction = FirstInstruction; Instruction != nullptr;
+       Instruction = Instruction->next()) {
+    ++Count;
+  }
+  return Count;
+}
+
+Expected<void> MachineBasicBlock::appendInstruction(MachineInstr &Instruction) {
+  if (&Instruction.function() != OwnerFunction) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "instruction belongs to another machine function");
+  }
+  if (Instruction.isLinked()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "instruction is already linked to a basic block");
+  }
+
+  auto AttachResult = Instruction.attachToBlock(*this);
+  if (!AttachResult)
+    return std::unexpected(AttachResult.error());
+
+  Instruction.PreviousInstruction = LastInstruction;
+  Instruction.NextInstruction = nullptr;
+  if (LastInstruction != nullptr)
+    LastInstruction->NextInstruction = &Instruction;
+  else
+    FirstInstruction = &Instruction;
+  LastInstruction = &Instruction;
+  return {};
+}
+
+Expected<void> MachineBasicBlock::insertInstructionBefore(MachineInstr &Position,
+                                                          MachineInstr &Instruction) {
+  if (Position.parent() != this) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "instruction insertion position is not in this block");
+  }
+  if (&Instruction.function() != OwnerFunction || Instruction.isLinked()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "inserted instruction is linked or belongs to another function");
+  }
+
+  auto AttachResult = Instruction.attachToBlock(*this);
+  if (!AttachResult)
+    return std::unexpected(AttachResult.error());
+
+  Instruction.PreviousInstruction = Position.PreviousInstruction;
+  Instruction.NextInstruction = &Position;
+  if (Position.PreviousInstruction != nullptr)
+    Position.PreviousInstruction->NextInstruction = &Instruction;
+  else
+    FirstInstruction = &Instruction;
+  Position.PreviousInstruction = &Instruction;
+  return {};
+}
+
+Expected<void> MachineBasicBlock::insertInstructionAfter(MachineInstr &Position,
+                                                         MachineInstr &Instruction) {
+  if (Position.parent() != this) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "instruction insertion position is not in this block");
+  }
+  if (&Instruction.function() != OwnerFunction || Instruction.isLinked()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "inserted instruction is linked or belongs to another function");
+  }
+
+  auto AttachResult = Instruction.attachToBlock(*this);
+  if (!AttachResult)
+    return std::unexpected(AttachResult.error());
+
+  Instruction.PreviousInstruction = &Position;
+  Instruction.NextInstruction = Position.NextInstruction;
+  if (Position.NextInstruction != nullptr)
+    Position.NextInstruction->PreviousInstruction = &Instruction;
+  else
+    LastInstruction = &Instruction;
+  Position.NextInstruction = &Instruction;
+  return {};
+}
+
+Expected<void> MachineBasicBlock::removeInstruction(MachineInstr &Instruction) {
+  if (Instruction.parent() != this) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "instruction does not belong to this block");
+  }
+
+  if (Instruction.PreviousInstruction != nullptr)
+    Instruction.PreviousInstruction->NextInstruction = Instruction.NextInstruction;
+  else
+    FirstInstruction = Instruction.NextInstruction;
+
+  if (Instruction.NextInstruction != nullptr)
+    Instruction.NextInstruction->PreviousInstruction = Instruction.PreviousInstruction;
+  else
+    LastInstruction = Instruction.PreviousInstruction;
+
+  Instruction.detachFromBlock();
+  return {};
+}
+
+void MachineBasicBlock::clearInstructions() noexcept {
+  MachineInstr *Instruction = FirstInstruction;
+  while (Instruction != nullptr) {
+    MachineInstr *NextInstruction = Instruction->NextInstruction;
+    Instruction->detachFromBlock();
+    Instruction = NextInstruction;
+  }
+  FirstInstruction = nullptr;
+  LastInstruction = nullptr;
+}
+
+Expected<void> MachineBasicBlock::addLiveIn(PhysicalRegister PhysReg, LaneMask Lanes) {
+  if (!PhysReg.isValid() || Lanes.empty()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "block live-in requires a physical register and nonempty lanes");
+  }
+
+  const auto Position =
+      std::ranges::find_if(LiveIns, [PhysReg](const MachineBasicBlockLiveIn &LiveIn) {
+        return LiveIn.PhysReg == PhysReg;
+      });
+  if (Position != LiveIns.end()) {
+    Position->Lanes = Position->Lanes | Lanes;
+    return {};
+  }
+
+  LiveIns.push_back(MachineBasicBlockLiveIn{PhysReg, Lanes});
+  return {};
+}
+
+Expected<void> MachineBasicBlock::removeLiveIn(PhysicalRegister PhysReg) {
+  const auto Position =
+      std::ranges::find_if(LiveIns, [PhysReg](const MachineBasicBlockLiveIn &LiveIn) {
+        return LiveIn.PhysReg == PhysReg;
+      });
+  if (Position == LiveIns.end()) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "block physical live-in is not present");
+  }
+  LiveIns.erase(Position);
+  return {};
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/MachineCFGUpdater.cpp b/backend/lib/CodeGen/MachineCFGUpdater.cpp
new file mode 100644
index 0000000..c78e318
--- /dev/null
+++ b/backend/lib/CodeGen/MachineCFGUpdater.cpp
@@ -0,0 +1,181 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineCFGUpdater.h"
+
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <optional>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] std::optional<std::size_t> findSuccessorIndex(const MachineBasicBlock &From,
+                                                            const MachineBasicBlock &To) {
+  const auto Successors = From.successors();
+  for (std::size_t Index = 0; Index < Successors.size(); ++Index) {
+    if (Successors[Index].Block == &To)
+      return Index;
+  }
+  return std::nullopt;
+}
+
+} // namespace
+
+Expected<void> MachineCFGUpdater::verifyOwnership(const MachineBasicBlock &Block) const {
+  if (&Block.function() != Function) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "CFG block belongs to another machine function");
+  }
+  return {};
+}
+
+Expected<void> MachineCFGUpdater::addSuccessor(MachineBasicBlock &From, MachineBasicBlock &To,
+                                               BranchProbability Probability) {
+  auto FromOwnership = verifyOwnership(From);
+  if (!FromOwnership)
+    return std::unexpected(FromOwnership.error());
+  auto ToOwnership = verifyOwnership(To);
+  if (!ToOwnership)
+    return std::unexpected(ToOwnership.error());
+
+  const auto Existing = findSuccessorIndex(From, To);
+  if (Existing) {
+    From.Successors[*Existing].Probability =
+        From.Successors[*Existing].Probability.saturatingAdd(Probability);
+    return {};
+  }
+
+  From.Successors.push_back(MachineSuccessor{&To, Probability});
+  if (std::ranges::find(To.Predecessors, &From) == To.Predecessors.end())
+    To.Predecessors.push_back(&From);
+  return {};
+}
+
+Expected<void> MachineCFGUpdater::removeSuccessor(MachineBasicBlock &From, MachineBasicBlock &To) {
+  auto FromOwnership = verifyOwnership(From);
+  if (!FromOwnership)
+    return std::unexpected(FromOwnership.error());
+  auto ToOwnership = verifyOwnership(To);
+  if (!ToOwnership)
+    return std::unexpected(ToOwnership.error());
+
+  const auto Successor = findSuccessorIndex(From, To);
+  if (!Successor) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "CFG successor edge is not present");
+  }
+  From.Successors.erase(From.Successors.begin() + static_cast<std::ptrdiff_t>(*Successor));
+
+  const auto Predecessor = std::ranges::find(To.Predecessors, &From);
+  if (Predecessor == To.Predecessors.end()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "CFG successor has no reciprocal predecessor");
+  }
+  To.Predecessors.erase(Predecessor);
+  return {};
+}
+
+Expected<void> MachineCFGUpdater::replaceSuccessor(MachineBasicBlock &From,
+                                                   MachineBasicBlock &OldTarget,
+                                                   MachineBasicBlock &NewTarget) {
+  auto FromOwnership = verifyOwnership(From);
+  if (!FromOwnership)
+    return std::unexpected(FromOwnership.error());
+  auto OldOwnership = verifyOwnership(OldTarget);
+  if (!OldOwnership)
+    return std::unexpected(OldOwnership.error());
+  auto NewOwnership = verifyOwnership(NewTarget);
+  if (!NewOwnership)
+    return std::unexpected(NewOwnership.error());
+
+  if (&OldTarget == &NewTarget)
+    return {};
+
+  const auto Existing = findSuccessorIndex(From, OldTarget);
+  if (!Existing) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "replaced CFG successor edge is not present");
+  }
+  const BranchProbability Probability = From.Successors[*Existing].Probability;
+
+  auto RemoveResult = removeSuccessor(From, OldTarget);
+  if (!RemoveResult)
+    return std::unexpected(RemoveResult.error());
+  auto AddResult = addSuccessor(From, NewTarget, Probability);
+  if (!AddResult) {
+    auto RestoreResult = addSuccessor(From, OldTarget, Probability);
+    if (!RestoreResult) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "failed to restore CFG edge after replacement failure");
+    }
+    return std::unexpected(AddResult.error());
+  }
+  return {};
+}
+
+Expected<void> MachineCFGUpdater::updateBranchProbability(MachineBasicBlock &From,
+                                                          MachineBasicBlock &To,
+                                                          BranchProbability Probability) {
+  auto FromOwnership = verifyOwnership(From);
+  if (!FromOwnership)
+    return std::unexpected(FromOwnership.error());
+  auto ToOwnership = verifyOwnership(To);
+  if (!ToOwnership)
+    return std::unexpected(ToOwnership.error());
+
+  const auto Successor = findSuccessorIndex(From, To);
+  if (!Successor) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "updated CFG successor edge is not present");
+  }
+  From.Successors[*Successor].Probability = Probability;
+  return {};
+}
+
+Expected<void> MachineCFGUpdater::transferSuccessors(MachineBasicBlock &From,
+                                                     MachineBasicBlock &To) {
+  auto FromOwnership = verifyOwnership(From);
+  if (!FromOwnership)
+    return std::unexpected(FromOwnership.error());
+  auto ToOwnership = verifyOwnership(To);
+  if (!ToOwnership)
+    return std::unexpected(ToOwnership.error());
+  if (&From == &To)
+    return {};
+
+  const std::vector<MachineSuccessor> Successors = From.Successors;
+  for (const MachineSuccessor &Successor : Successors) {
+    auto RemoveResult = removeSuccessor(From, *Successor.Block);
+    if (!RemoveResult)
+      return std::unexpected(RemoveResult.error());
+    auto AddResult = addSuccessor(To, *Successor.Block, Successor.Probability);
+    if (!AddResult)
+      return std::unexpected(AddResult.error());
+  }
+  return {};
+}
+
+Expected<void> MachineCFGUpdater::disconnectBlock(MachineBasicBlock &Block) {
+  auto Ownership = verifyOwnership(Block);
+  if (!Ownership)
+    return std::unexpected(Ownership.error());
+
+  const std::vector<MachineSuccessor> Successors = Block.Successors;
+  for (const MachineSuccessor &Successor : Successors) {
+    auto Result = removeSuccessor(Block, *Successor.Block);
+    if (!Result)
+      return std::unexpected(Result.error());
+  }
+
+  const std::vector<MachineBasicBlock *> Predecessors = Block.Predecessors;
+  for (MachineBasicBlock *Predecessor : Predecessors) {
+    auto Result = removeSuccessor(*Predecessor, Block);
+    if (!Result)
+      return std::unexpected(Result.error());
+  }
+  return {};
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/MachineFunction.cpp b/backend/lib/CodeGen/MachineFunction.cpp
new file mode 100644
index 0000000..e19c115
--- /dev/null
+++ b/backend/lib/CodeGen/MachineFunction.cpp
@@ -0,0 +1,205 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineFunction.h"
+
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineCFGUpdater.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineMemOperand.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <memory>
+#include <memory_resource>
+#include <new>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+
+class MachineArena final {
+public:
+  MachineArena() = default;
+  MachineArena(const MachineArena &) = delete;
+  MachineArena &operator=(const MachineArena &) = delete;
+  MachineArena(MachineArena &&) = delete;
+  MachineArena &operator=(MachineArena &&) = delete;
+
+  ~MachineArena() {
+    for (auto Position = Destructors.rbegin(); Position != Destructors.rend(); ++Position)
+      Position->Destroy(Position->Object);
+  }
+
+  template <typename ObjectT, typename... ArgumentTs>
+  [[nodiscard]] ObjectT *create(ArgumentTs &&...Arguments) {
+    void *Storage = Resource.allocate(sizeof(ObjectT), alignof(ObjectT));
+    ObjectT *Object = ::new (Storage) ObjectT(std::forward<ArgumentTs>(Arguments)...);
+    try {
+      Destructors.push_back(DestructorRecord{
+          Object,
+          [](void *RawObject) noexcept { std::destroy_at(static_cast<ObjectT *>(RawObject)); },
+      });
+    } catch (...) {
+      std::destroy_at(Object);
+      throw;
+    }
+    return Object;
+  }
+
+private:
+  struct DestructorRecord final {
+    void *Object;
+    void (*Destroy)(void *) noexcept;
+  };
+
+  std::pmr::monotonic_buffer_resource Resource;
+  std::vector<DestructorRecord> Destructors;
+};
+
+Expected<std::unique_ptr<MachineFunction>>
+MachineFunction::create(std::string Name, MachineFunctionStableID StableID) {
+  if (Name.empty())
+    return makeUnexpected(ErrorCode::InvalidArgument, "machine function name cannot be empty");
+  if (!StableID.isValid())
+    return makeUnexpected(ErrorCode::InvalidArgument, "machine function StableID must be valid");
+  return std::unique_ptr<MachineFunction>(new MachineFunction(std::move(Name), StableID));
+}
+
+MachineFunction::MachineFunction(std::string Name, MachineFunctionStableID StableID)
+    : Name(std::move(Name)), StableID(StableID), Arena(std::make_unique<MachineArena>()) {}
+
+MachineFunction::~MachineFunction() {
+  for (MachineBasicBlock *Block = FirstBlock; Block != nullptr; Block = Block->NextBlock) {
+    Block->clearInstructions();
+    Block->Predecessors.clear();
+    Block->Successors.clear();
+  }
+}
+
+Expected<MachineBasicBlock *> MachineFunction::createBasicBlock() {
+  auto ID = BlockIDGenerator.allocate();
+  if (!ID)
+    return std::unexpected(ID.error());
+  MachineBasicBlock *Block = Arena->create<MachineBasicBlock>(*this, *ID);
+  AllBlocks.push_back(Block);
+  return Block;
+}
+
+Expected<MachineInstr *> MachineFunction::createInstruction(Opcode InstructionOpcode) {
+  if (!InstructionOpcode.isValid())
+    return makeUnexpected(ErrorCode::InvalidArgument, "machine opcode must be nonzero");
+
+  auto ID = InstrIDGenerator.allocate();
+  if (!ID)
+    return std::unexpected(ID.error());
+  MachineInstr *Instruction = Arena->create<MachineInstr>(*this, InstructionOpcode, *ID);
+  AllInstructions.push_back(Instruction);
+  return Instruction;
+}
+
+Expected<const MachineMemOperand *>
+MachineFunction::createMemOperand(MachineMemOperandDesc Description) {
+  auto MemOperand = MachineMemOperand::create(std::move(Description));
+  if (!MemOperand)
+    return std::unexpected(MemOperand.error());
+
+  const MachineMemOperand *Stored = Arena->create<MachineMemOperand>(std::move(*MemOperand));
+  AllMemOperands.push_back(Stored);
+  return Stored;
+}
+
+Expected<void> MachineFunction::appendBlock(MachineBasicBlock &Block) {
+  if (Block.OwnerFunction != this)
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "basic block belongs to another machine function");
+  if (Block.IsLinked)
+    return makeUnexpected(ErrorCode::InvalidArgument, "basic block is already linked");
+
+  Block.PreviousBlock = LastBlock;
+  Block.NextBlock = nullptr;
+  if (LastBlock != nullptr)
+    LastBlock->NextBlock = &Block;
+  else
+    FirstBlock = &Block;
+  LastBlock = &Block;
+  Block.IsLinked = true;
+  renumberBlocks();
+  return {};
+}
+
+Expected<void> MachineFunction::insertBlockBefore(MachineBasicBlock &Position,
+                                                  MachineBasicBlock &Block) {
+  if (Position.OwnerFunction != this || !Position.IsLinked)
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "block insertion position is not linked to this function");
+  if (Block.OwnerFunction != this || Block.IsLinked)
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "inserted block is linked or belongs to another function");
+
+  Block.PreviousBlock = Position.PreviousBlock;
+  Block.NextBlock = &Position;
+  if (Position.PreviousBlock != nullptr)
+    Position.PreviousBlock->NextBlock = &Block;
+  else
+    FirstBlock = &Block;
+  Position.PreviousBlock = &Block;
+  Block.IsLinked = true;
+  renumberBlocks();
+  return {};
+}
+
+Expected<void> MachineFunction::removeBlock(MachineBasicBlock &Block) {
+  if (Block.OwnerFunction != this || !Block.IsLinked)
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "removed block is not linked to this function");
+  if (!Block.Predecessors.empty() || !Block.Successors.empty()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "disconnect CFG edges before removing a basic block");
+  }
+
+  Block.clearInstructions();
+  if (Block.PreviousBlock != nullptr)
+    Block.PreviousBlock->NextBlock = Block.NextBlock;
+  else
+    FirstBlock = Block.NextBlock;
+  if (Block.NextBlock != nullptr)
+    Block.NextBlock->PreviousBlock = Block.PreviousBlock;
+  else
+    LastBlock = Block.PreviousBlock;
+
+  Block.IsLinked = false;
+  Block.PreviousBlock = nullptr;
+  Block.NextBlock = nullptr;
+  Block.DenseNumber.reset();
+  Block.LayoutIndex.reset();
+  renumberBlocks();
+  return {};
+}
+
+std::size_t MachineFunction::blockCount() const noexcept {
+  std::size_t Count = 0;
+  for (const MachineBasicBlock *Block = FirstBlock; Block != nullptr; Block = Block->next()) {
+    ++Count;
+  }
+  return Count;
+}
+
+bool MachineFunction::ownsMemOperand(const MachineMemOperand &MemOperand) const noexcept {
+  return std::ranges::find(AllMemOperands, &MemOperand) != AllMemOperands.end();
+}
+
+MachineCFGUpdater MachineFunction::cfgUpdater() noexcept {
+  return MachineCFGUpdater(*this);
+}
+
+void MachineFunction::renumberBlocks() noexcept {
+  std::uint32_t Number = 0;
+  for (MachineBasicBlock *Block = FirstBlock; Block != nullptr; Block = Block->NextBlock) {
+    Block->DenseNumber = Number;
+    Block->LayoutIndex = Number;
+    ++Number;
+  }
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/MachineInstr.cpp b/backend/lib/CodeGen/MachineInstr.cpp
new file mode 100644
index 0000000..3692258
--- /dev/null
+++ b/backend/lib/CodeGen/MachineInstr.cpp
@@ -0,0 +1,199 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineInstr.h"
+
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineMemOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+
+#include <cstddef>
+#include <functional>
+#include <optional>
+#include <utility>
+
+namespace rcc {
+
+MachineInstr::MachineInstr(MachineFunction &OwnerFunction, Opcode InstructionOpcode,
+                           MachineInstrStableID StableID)
+    : OwnerFunction(&OwnerFunction), InstructionOpcode(InstructionOpcode), StableID(StableID) {}
+
+MachineInstr::~MachineInstr() {
+  for (MachineOperand &Operand : Operands)
+    Operand.detachFromInstruction();
+}
+
+Expected<void> MachineInstr::setOpcode(Opcode NewOpcode) {
+  if (!NewOpcode.isValid())
+    return makeUnexpected(ErrorCode::InvalidArgument, "machine opcode must be nonzero");
+  InstructionOpcode = NewOpcode;
+  return {};
+}
+
+MachineOperand *MachineInstr::operandAt(std::size_t Index) noexcept {
+  if (Index >= Operands.size())
+    return nullptr;
+  return &Operands[Index];
+}
+
+const MachineOperand *MachineInstr::operandAt(std::size_t Index) const noexcept {
+  if (Index >= Operands.size())
+    return nullptr;
+  return &Operands[Index];
+}
+
+void MachineInstr::reserveOperands(std::size_t Capacity) {
+  Operands.reserve(Capacity);
+}
+
+Expected<void> MachineInstr::addOperand(MachineOperand Operand) {
+  return insertOperand(Operands.size(), std::move(Operand));
+}
+
+Expected<void> MachineInstr::insertOperand(std::size_t Index, MachineOperand Operand) {
+  if (Index > Operands.size())
+    return makeUnexpected(ErrorCode::InvalidArgument, "operand insertion index is out of range");
+  if (Operand.Parent != nullptr)
+    return makeUnexpected(ErrorCode::InvalidArgument, "operand already belongs to an instruction");
+  if (Operand.TiedOperandIndex)
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "detached operand cannot carry a tied operand index");
+  if (const auto *BlockOperand = Operand.getIf<BasicBlockOperand>();
+      BlockOperand != nullptr && &BlockOperand->Block->function() != OwnerFunction) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "basic block operand belongs to another machine function");
+  }
+  if (const Register *Reg = Operand.getIf<Register>();
+      Reg != nullptr && Reg->isVirtual() &&
+      !OwnerFunction->registerInfo().isKnownVirtualRegister(*Reg)) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "register operand references an unknown virtual register");
+  }
+
+  Operands.insert(Operands.begin() + static_cast<std::ptrdiff_t>(Index), std::move(Operand));
+  adjustTiesForInsertion(Index);
+  Operands[Index].attachTo(*this, linkedRegisterInfo());
+  return {};
+}
+
+Expected<void> MachineInstr::eraseOperand(std::size_t Index) {
+  if (Index >= Operands.size())
+    return makeUnexpected(ErrorCode::InvalidArgument, "operand erase index is out of range");
+
+  adjustTiesForErasure(Index);
+  Operands.erase(Operands.begin() + static_cast<std::ptrdiff_t>(Index));
+  return {};
+}
+
+Expected<void> MachineInstr::tieOperands(std::size_t DefIndex, std::size_t UseIndex) {
+  if (DefIndex >= Operands.size() || UseIndex >= Operands.size() || DefIndex == UseIndex) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "tied operand indices are invalid");
+  }
+
+  MachineOperand &DefOperand = Operands[DefIndex];
+  MachineOperand &UseOperand = Operands[UseIndex];
+  if (!DefOperand.isRegister() || !UseOperand.isRegister() || !DefOperand.isDef() ||
+      !UseOperand.isUse()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "tie must connect a register definition and use");
+  }
+  if (DefOperand.TiedOperandIndex || UseOperand.TiedOperandIndex) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "an operand cannot participate in more than one tie");
+  }
+
+  DefOperand.setTiedOperandIndex(UseIndex);
+  UseOperand.setTiedOperandIndex(DefIndex);
+  return {};
+}
+
+Expected<void> MachineInstr::untieOperand(std::size_t Index) {
+  if (Index >= Operands.size())
+    return makeUnexpected(ErrorCode::InvalidArgument, "operand tie index is out of range");
+  const auto OtherIndex = Operands[Index].TiedOperandIndex;
+  if (!OtherIndex)
+    return makeUnexpected(ErrorCode::InvalidArgument, "operand is not tied");
+  if (*OtherIndex >= Operands.size() || Operands[*OtherIndex].TiedOperandIndex != Index) {
+    return makeUnexpected(ErrorCode::VerificationError, "operand tie relation is not reciprocal");
+  }
+
+  Operands[*OtherIndex].setTiedOperandIndex(std::nullopt);
+  Operands[Index].setTiedOperandIndex(std::nullopt);
+  return {};
+}
+
+Expected<void> MachineInstr::addMemOperand(const MachineMemOperand &MemOperand) {
+  if (!OwnerFunction->ownsMemOperand(MemOperand)) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "machine memory operand belongs to another function");
+  }
+  MemOperands.push_back(&MemOperand);
+  return {};
+}
+
+Expected<void> MachineInstr::eraseMemOperand(std::size_t Index) {
+  if (Index >= MemOperands.size()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "machine memory operand index is out of range");
+  }
+  MemOperands.erase(MemOperands.begin() + static_cast<std::ptrdiff_t>(Index));
+  return {};
+}
+
+MachineRegisterInfo *MachineInstr::linkedRegisterInfo() noexcept {
+  if (!isLinked())
+    return nullptr;
+  return &OwnerFunction->registerInfo();
+}
+
+Expected<void> MachineInstr::attachToBlock(MachineBasicBlock &Block) {
+  if (ParentBlock != nullptr) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "instruction is already linked to a basic block");
+  }
+
+  MachineRegisterInfo &RegInfo = OwnerFunction->registerInfo();
+  for (const MachineOperand &Operand : Operands) {
+    const Register *Reg = Operand.getIf<Register>();
+    if (Reg != nullptr && Reg->isVirtual() && !RegInfo.isKnownVirtualRegister(*Reg)) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "instruction references an unknown virtual register");
+    }
+  }
+
+  ParentBlock = &Block;
+  for (MachineOperand &Operand : Operands) {
+    const Register *Reg = Operand.getIf<Register>();
+    if (Reg != nullptr && !Reg->isNoRegister())
+      Operand.linkToRegInfo(RegInfo);
+  }
+  return {};
+}
+
+void MachineInstr::detachFromBlock() noexcept {
+  for (MachineOperand &Operand : Operands)
+    Operand.unlinkFromRegInfo();
+  ParentBlock = nullptr;
+  PreviousInstruction = nullptr;
+  NextInstruction = nullptr;
+}
+
+void MachineInstr::adjustTiesForInsertion(std::size_t Index) noexcept {
+  for (MachineOperand &Operand : Operands) {
+    if (Operand.TiedOperandIndex && *Operand.TiedOperandIndex >= Index)
+      ++*Operand.TiedOperandIndex;
+  }
+}
+
+void MachineInstr::adjustTiesForErasure(std::size_t Index) noexcept {
+  for (MachineOperand &Operand : Operands) {
+    if (!Operand.TiedOperandIndex)
+      continue;
+    if (*Operand.TiedOperandIndex == Index)
+      Operand.TiedOperandIndex.reset();
+    else if (*Operand.TiedOperandIndex > Index)
+      --*Operand.TiedOperandIndex;
+  }
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/MachineOperand.cpp b/backend/lib/CodeGen/MachineOperand.cpp
new file mode 100644
index 0000000..0e5febd
--- /dev/null
+++ b/backend/lib/CodeGen/MachineOperand.cpp
@@ -0,0 +1,326 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineOperand.h"
+
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+
+#include <algorithm>
+#include <array>
+#include <cstdint>
+#include <memory>
+#include <span>
+#include <utility>
+
+namespace rcc {
+
+Expected<FloatingPointBits> FloatingPointBits::create(FloatSemantics Semantics,
+                                                      std::span<const std::uint64_t> Words) {
+  const auto BitWidth = getFloatSemanticsBitWidth(Semantics);
+  if (!BitWidth) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "floating immediate has unknown semantics");
+  }
+
+  const std::size_t RequiredWords = (*BitWidth + 63U) / 64U;
+  if (RequiredWords > 2 || Words.size() != RequiredWords) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "floating immediate bit pattern has the wrong word count");
+  }
+
+  const std::uint32_t UsedBitsInLastWord = *BitWidth % 64U;
+  if (UsedBitsInLastWord != 0 && (Words.back() >> UsedBitsInLastWord) != 0) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "floating immediate has nonzero bits above its semantics width");
+  }
+
+  std::array<std::uint64_t, 2> StoredWords{};
+  std::ranges::copy(Words, StoredWords.begin());
+  return FloatingPointBits(Semantics, StoredWords, static_cast<std::uint8_t>(RequiredWords));
+}
+
+RegisterOperandFlags::RegisterOperandFlags(
+    std::initializer_list<RegisterOperandFlag> Flags) noexcept {
+  for (const RegisterOperandFlag Flag : Flags)
+    set(Flag);
+}
+
+Expected<void> MachineOperand::verifyRegisterFlags(RegisterOperandFlags Flags) {
+  const bool IsDef = Flags.has(RegisterOperandFlag::Define);
+  const bool IsUse = Flags.has(RegisterOperandFlag::Use);
+  if (!IsDef && !IsUse) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "register operand must be a definition or use");
+  }
+  if (Flags.has(RegisterOperandFlag::Kill) && !IsUse) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "kill flag requires a register use");
+  }
+  if (Flags.has(RegisterOperandFlag::Dead) && !IsDef) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "dead flag requires a register definition");
+  }
+  if (Flags.has(RegisterOperandFlag::Undef) && !IsUse) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "undef flag requires a register use");
+  }
+  if (Flags.has(RegisterOperandFlag::EarlyClobber) && !IsDef) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "early-clobber flag requires a register definition");
+  }
+  if (Flags.has(RegisterOperandFlag::InternalRead) && (!IsDef || !IsUse)) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "internal-read flag requires a register def-use operand");
+  }
+  if (IsDef && IsUse && !Flags.has(RegisterOperandFlag::InternalRead)) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "register def-use operand requires internal-read");
+  }
+  if (Flags.has(RegisterOperandFlag::Debug) && (!IsUse || IsDef)) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "debug register operand must be a use");
+  }
+  return {};
+}
+
+Expected<MachineOperand> MachineOperand::registerOperand(Register Reg, RegisterOperandFlags Flags,
+                                                         SubRegIndex SubReg,
+                                                         std::uint32_t TargetFlags) {
+  const auto Validation = verifyRegisterFlags(Flags);
+  if (!Validation)
+    return std::unexpected(Validation.error());
+
+  MachineOperand Operand(Kind::Register, Reg, TargetFlags);
+  Operand.RegFlags = Flags;
+  Operand.RegSubReg = SubReg;
+  return Operand;
+}
+
+MachineOperand MachineOperand::immediate(std::int64_t Value, std::uint32_t TargetFlags) {
+  return MachineOperand(Kind::Immediate, Value, TargetFlags);
+}
+
+MachineOperand MachineOperand::floatingImmediate(FloatingPointBits Bits,
+                                                 std::uint32_t TargetFlags) {
+  return MachineOperand(Kind::FloatingImmediate, FloatingImmediateOperand{Bits}, TargetFlags);
+}
+
+MachineOperand MachineOperand::basicBlock(MachineBasicBlock &Block, std::uint32_t TargetFlags) {
+  return MachineOperand(Kind::BasicBlock, BasicBlockOperand{&Block}, TargetFlags);
+}
+
+MachineOperand MachineOperand::frameIndex(FrameIndex Index, std::int64_t Offset,
+                                          std::uint32_t TargetFlags) {
+  return MachineOperand(Kind::FrameIndex, FrameIndexOperand{Index, Offset}, TargetFlags);
+}
+
+MachineOperand MachineOperand::constantPool(ConstantPoolIndex Index, std::int64_t Offset,
+                                            std::uint32_t TargetFlags) {
+  return MachineOperand(Kind::ConstantPoolIndex, ConstantPoolOperand{Index, Offset}, TargetFlags);
+}
+
+MachineOperand MachineOperand::jumpTable(JumpTableIndex Index, std::uint32_t TargetFlags) {
+  return MachineOperand(Kind::JumpTableIndex, JumpTableOperand{Index}, TargetFlags);
+}
+
+Expected<MachineOperand> MachineOperand::globalSymbol(std::string Name, std::int64_t Offset,
+                                                      std::uint32_t TargetFlags) {
+  if (Name.empty()) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "global symbol operand name cannot be empty");
+  }
+  return MachineOperand(Kind::GlobalSymbol, GlobalSymbolOperand{std::move(Name), Offset},
+                        TargetFlags);
+}
+
+Expected<MachineOperand> MachineOperand::externalSymbol(std::string Name, std::int64_t Offset,
+                                                        std::uint32_t TargetFlags) {
+  if (Name.empty()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "external symbol operand name cannot be empty");
+  }
+  return MachineOperand(Kind::ExternalSymbol, ExternalSymbolOperand{std::move(Name), Offset},
+                        TargetFlags);
+}
+
+Expected<MachineOperand> MachineOperand::blockAddress(std::string FunctionName,
+                                                      std::string BlockName, std::int64_t Offset,
+                                                      std::uint32_t TargetFlags) {
+  if (FunctionName.empty() || BlockName.empty()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "block address operand requires function and block names");
+  }
+  return MachineOperand(Kind::BlockAddress,
+                        BlockAddressOperand{std::move(FunctionName), std::move(BlockName), Offset},
+                        TargetFlags);
+}
+
+Expected<MachineOperand> MachineOperand::registerMask(std::shared_ptr<const RegisterMask> Mask,
+                                                      std::uint32_t TargetFlags) {
+  if (!Mask) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "register mask operand cannot be null");
+  }
+  return MachineOperand(Kind::RegisterMask, RegisterMaskOperand{std::move(Mask)}, TargetFlags);
+}
+
+Expected<MachineOperand> MachineOperand::metadata(std::string Marker, std::uint32_t TargetFlags) {
+  if (Marker.empty()) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "metadata operand marker cannot be empty");
+  }
+  return MachineOperand(Kind::Metadata, MetadataOperand{std::move(Marker)}, TargetFlags);
+}
+
+MachineOperand MachineOperand::targetIndex(TargetIndex Index, std::int64_t Offset,
+                                           std::uint32_t TargetFlags) {
+  return MachineOperand(Kind::TargetIndex, TargetIndexOperand{Index, Offset}, TargetFlags);
+}
+
+Expected<MachineOperand> MachineOperand::mcSymbol(std::string Name, std::int64_t Offset,
+                                                  std::uint32_t TargetFlags) {
+  if (Name.empty()) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "MC symbol operand name cannot be empty");
+  }
+  return MachineOperand(Kind::MCSymbol, MCSymbolOperand{std::move(Name), Offset}, TargetFlags);
+}
+
+MachineOperand::MachineOperand(MachineOperand &&Other) noexcept
+    : OperandKind(Other.OperandKind), Storage(std::move(Other.Storage)), RegFlags(Other.RegFlags),
+      RegSubReg(Other.RegSubReg), TiedOperandIndex(Other.TiedOperandIndex),
+      TargetFlags(Other.TargetFlags), Parent(Other.Parent) {
+  takeRegLinkFrom(Other);
+  Other.Parent = nullptr;
+  Other.TiedOperandIndex.reset();
+}
+
+MachineOperand &MachineOperand::operator=(MachineOperand &&Other) noexcept {
+  if (this == &Other)
+    return *this;
+
+  unlinkFromRegInfo();
+  OperandKind = Other.OperandKind;
+  Storage = std::move(Other.Storage);
+  RegFlags = Other.RegFlags;
+  RegSubReg = Other.RegSubReg;
+  TiedOperandIndex = Other.TiedOperandIndex;
+  TargetFlags = Other.TargetFlags;
+  Parent = Other.Parent;
+  takeRegLinkFrom(Other);
+  Other.Parent = nullptr;
+  Other.TiedOperandIndex.reset();
+  return *this;
+}
+
+MachineOperand::~MachineOperand() {
+  unlinkFromRegInfo();
+}
+
+std::optional<Register> MachineOperand::registerValue() const noexcept {
+  if (!isRegister())
+    return std::nullopt;
+  return std::get<Register>(Storage);
+}
+
+bool MachineOperand::isDef() const noexcept {
+  return isRegister() && RegFlags.has(RegisterOperandFlag::Define);
+}
+
+bool MachineOperand::isUse() const noexcept {
+  return isRegister() && RegFlags.has(RegisterOperandFlag::Use);
+}
+
+bool MachineOperand::isDebugUse() const noexcept {
+  return isUse() && RegFlags.has(RegisterOperandFlag::Debug);
+}
+
+bool MachineOperand::isImplicit() const noexcept {
+  return isRegister() && RegFlags.has(RegisterOperandFlag::Implicit);
+}
+
+Expected<void> MachineOperand::setRegister(Register Reg) {
+  if (!isRegister()) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "setRegister requires a register operand");
+  }
+
+  MachineRegisterInfo *RegInfo = LinkedRegInfo;
+  if (RegInfo == nullptr && Parent != nullptr)
+    RegInfo = &Parent->function().registerInfo();
+  if (RegInfo != nullptr && Reg.isVirtual() && !RegInfo->isKnownVirtualRegister(Reg)) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "register operand references an unknown virtual register");
+  }
+
+  const bool WasLinked = LinkedRegInfo != nullptr;
+  unlinkFromRegInfo();
+  Storage = Reg;
+  if (WasLinked && !Reg.isNoRegister())
+    linkToRegInfo(*RegInfo);
+  return {};
+}
+
+Expected<void> MachineOperand::setRegisterFlags(RegisterOperandFlags Flags) {
+  if (!isRegister()) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "register flags require a register operand");
+  }
+  const auto Validation = verifyRegisterFlags(Flags);
+  if (!Validation)
+    return std::unexpected(Validation.error());
+  RegFlags = Flags;
+  return {};
+}
+
+Expected<void> MachineOperand::setSubReg(SubRegIndex SubReg) {
+  if (!isRegister()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "subregister index requires a register operand");
+  }
+  RegSubReg = SubReg;
+  return {};
+}
+
+MachineOperand MachineOperand::cloneDetached() const {
+  MachineOperand Result(OperandKind, Storage, TargetFlags);
+  Result.RegFlags = RegFlags;
+  Result.RegSubReg = RegSubReg;
+  return Result;
+}
+
+void MachineOperand::attachTo(MachineInstr &Instruction, MachineRegisterInfo *RegInfo) {
+  Parent = &Instruction;
+  if (RegInfo != nullptr && isRegister() && !std::get<Register>(Storage).isNoRegister()) {
+    linkToRegInfo(*RegInfo);
+  }
+}
+
+void MachineOperand::detachFromInstruction() noexcept {
+  unlinkFromRegInfo();
+  Parent = nullptr;
+}
+
+void MachineOperand::linkToRegInfo(MachineRegisterInfo &RegInfo) {
+  RegInfo.linkOperand(*this);
+}
+
+void MachineOperand::unlinkFromRegInfo() noexcept {
+  if (PreviousRegLink == nullptr)
+    return;
+
+  *PreviousRegLink = NextRegOperand;
+  if (NextRegOperand != nullptr)
+    NextRegOperand->PreviousRegLink = PreviousRegLink;
+
+  PreviousRegLink = nullptr;
+  NextRegOperand = nullptr;
+  LinkedRegInfo = nullptr;
+}
+
+void MachineOperand::takeRegLinkFrom(MachineOperand &Other) noexcept {
+  LinkedRegInfo = Other.LinkedRegInfo;
+  PreviousRegLink = Other.PreviousRegLink;
+  NextRegOperand = Other.NextRegOperand;
+
+  if (PreviousRegLink != nullptr)
+    *PreviousRegLink = this;
+  if (NextRegOperand != nullptr)
+    NextRegOperand->PreviousRegLink = &NextRegOperand;
+
+  Other.LinkedRegInfo = nullptr;
+  Other.PreviousRegLink = nullptr;
+  Other.NextRegOperand = nullptr;
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/MachineRegisterInfo.cpp b/backend/lib/CodeGen/MachineRegisterInfo.cpp
new file mode 100644
index 0000000..cc0955e
--- /dev/null
+++ b/backend/lib/CodeGen/MachineRegisterInfo.cpp
@@ -0,0 +1,362 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+
+#include "rcc/CodeGen/MachineOperand.h"
+
+#include <algorithm>
+#include <functional>
+#include <memory>
+#include <optional>
+#include <unordered_set>
+
+namespace rcc {
+
+RegOperandIterator::RegOperandIterator(MachineOperand *Current, bool RequireUse, bool RequireDef,
+                                       bool SkipDebug) noexcept
+    : Current(Current), RequireUse(RequireUse), RequireDef(RequireDef), SkipDebug(SkipDebug) {
+  skipFiltered();
+}
+
+RegOperandIterator::reference RegOperandIterator::operator*() const noexcept {
+  return *Current;
+}
+
+RegOperandIterator::pointer RegOperandIterator::operator->() const noexcept {
+  return Current;
+}
+
+RegOperandIterator &RegOperandIterator::operator++() noexcept {
+  Current = Current->NextRegOperand;
+  skipFiltered();
+  return *this;
+}
+
+RegOperandIterator RegOperandIterator::operator++(int) noexcept {
+  RegOperandIterator Previous = *this;
+  ++*this;
+  return Previous;
+}
+
+void RegOperandIterator::skipFiltered() noexcept {
+  while (Current != nullptr) {
+    if (RequireUse && !Current->isUse()) {
+      Current = Current->NextRegOperand;
+      continue;
+    }
+    if (RequireDef && !Current->isDef()) {
+      Current = Current->NextRegOperand;
+      continue;
+    }
+    if (SkipDebug && Current->isDebugUse()) {
+      Current = Current->NextRegOperand;
+      continue;
+    }
+    break;
+  }
+}
+
+MachineRegisterInfo::~MachineRegisterInfo() = default;
+
+Expected<Register> MachineRegisterInfo::createVirtualRegister() {
+  auto Reg = Register::makeVirtual(VirtualRegisters.size());
+  if (!Reg)
+    return std::unexpected(Reg.error());
+  VirtualRegisters.emplace_back();
+  return *Reg;
+}
+
+Expected<Register> MachineRegisterInfo::createVirtualRegister(LLT Type) {
+  if (!Type.isValid()) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "virtual register type must be a valid LLT");
+  }
+
+  auto Reg = createVirtualRegister();
+  if (!Reg)
+    return std::unexpected(Reg.error());
+  VirtualRegisters.back().Type = Type;
+  return *Reg;
+}
+
+Expected<void> MachineRegisterInfo::eraseVirtualRegister(Register Reg) {
+  auto Info = virtualRegisterInfo(Reg);
+  if (!Info)
+    return std::unexpected(Info.error());
+  if (headFor(Reg) != nullptr) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "cannot erase a virtual register with operands");
+  }
+
+  Info->get().IsTombstone = true;
+  Info->get().Type.reset();
+  Info->get().Bank.reset();
+  Info->get().RegClass.reset();
+  Info->get().AllocationHints.clear();
+  return {};
+}
+
+bool MachineRegisterInfo::isKnownVirtualRegister(Register Reg) const noexcept {
+  const auto Index = Reg.virtualIndex();
+  if (!Index || *Index >= VirtualRegisters.size())
+    return false;
+  return !VirtualRegisters[*Index].IsTombstone;
+}
+
+Expected<std::reference_wrapper<VirtualRegisterInfo>>
+MachineRegisterInfo::virtualRegisterInfo(Register Reg) {
+  const auto Index = Reg.virtualIndex();
+  if (!Index || *Index >= VirtualRegisters.size() || VirtualRegisters[*Index].IsTombstone) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "register is not a live virtual register");
+  }
+  return std::ref(VirtualRegisters[*Index]);
+}
+
+Expected<std::reference_wrapper<const VirtualRegisterInfo>>
+MachineRegisterInfo::virtualRegisterInfo(Register Reg) const {
+  const auto Index = Reg.virtualIndex();
+  if (!Index || *Index >= VirtualRegisters.size() || VirtualRegisters[*Index].IsTombstone) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "register is not a live virtual register");
+  }
+  return std::cref(VirtualRegisters[*Index]);
+}
+
+Expected<void> MachineRegisterInfo::setType(Register Reg, LLT Type) {
+  if (!Type.isValid()) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "virtual register type must be a valid LLT");
+  }
+  auto Info = virtualRegisterInfo(Reg);
+  if (!Info)
+    return std::unexpected(Info.error());
+  Info->get().Type = Type;
+  return {};
+}
+
+Expected<void> MachineRegisterInfo::clearType(Register Reg) {
+  auto Info = virtualRegisterInfo(Reg);
+  if (!Info)
+    return std::unexpected(Info.error());
+  Info->get().Type.reset();
+  return {};
+}
+
+Expected<void> MachineRegisterInfo::setRegisterBank(Register Reg, RegisterBankID Bank) {
+  auto Info = virtualRegisterInfo(Reg);
+  if (!Info)
+    return std::unexpected(Info.error());
+  Info->get().Bank = Bank;
+  return {};
+}
+
+Expected<void> MachineRegisterInfo::clearRegisterBank(Register Reg) {
+  auto Info = virtualRegisterInfo(Reg);
+  if (!Info)
+    return std::unexpected(Info.error());
+  Info->get().Bank.reset();
+  return {};
+}
+
+Expected<void> MachineRegisterInfo::setRegisterClass(Register Reg, RegisterClassID RegClass) {
+  auto Info = virtualRegisterInfo(Reg);
+  if (!Info)
+    return std::unexpected(Info.error());
+  Info->get().RegClass = RegClass;
+  return {};
+}
+
+Expected<void> MachineRegisterInfo::clearRegisterClass(Register Reg) {
+  auto Info = virtualRegisterInfo(Reg);
+  if (!Info)
+    return std::unexpected(Info.error());
+  Info->get().RegClass.reset();
+  return {};
+}
+
+Expected<void> MachineRegisterInfo::addAllocationHint(Register Reg, PhysicalRegister Hint) {
+  if (!Hint.isValid()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "allocation hint must name a physical register");
+  }
+  auto Info = virtualRegisterInfo(Reg);
+  if (!Info)
+    return std::unexpected(Info.error());
+
+  auto &Hints = Info->get().AllocationHints;
+  if (std::ranges::find(Hints, Hint) == Hints.end())
+    Hints.push_back(Hint);
+  return {};
+}
+
+void MachineRegisterInfo::clearAllVirtualRegisterTypes() noexcept {
+  for (VirtualRegisterInfo &Info : VirtualRegisters) {
+    if (!Info.IsTombstone)
+      Info.Type.reset();
+  }
+}
+
+Expected<void> MachineRegisterInfo::addLiveIn(PhysicalRegister PhysReg,
+                                              std::optional<Register> InitialVirtualRegister) {
+  if (!PhysReg.isValid()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "function live-in must name a physical register");
+  }
+  if (InitialVirtualRegister && !isKnownVirtualRegister(*InitialVirtualRegister)) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "function live-in initial value must be a live virtual register");
+  }
+  if (std::ranges::any_of(LiveIns, [PhysReg](const PhysicalRegisterLiveIn &LiveIn) {
+        return LiveIn.PhysReg == PhysReg;
+      })) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "function physical live-in is already present");
+  }
+
+  LiveIns.push_back(PhysicalRegisterLiveIn{PhysReg, InitialVirtualRegister});
+  return {};
+}
+
+Expected<void> MachineRegisterInfo::reservePhysicalRegister(PhysicalRegister PhysReg) {
+  if (!PhysReg.isValid()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "reserved register must name a physical register");
+  }
+  if (isReserved(PhysReg)) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "physical register is already reserved");
+  }
+  ReservedRegisters.push_back(PhysReg);
+  return {};
+}
+
+bool MachineRegisterInfo::isReserved(PhysicalRegister PhysReg) const noexcept {
+  return std::ranges::find(ReservedRegisters, PhysReg) != ReservedRegisters.end();
+}
+
+RegOperandRange MachineRegisterInfo::regOperands(Register Reg) noexcept {
+  return RegOperandRange(headFor(Reg), false, false, false);
+}
+
+RegOperandRange MachineRegisterInfo::regNoDebugOperands(Register Reg) noexcept {
+  return RegOperandRange(headFor(Reg), false, false, true);
+}
+
+RegOperandRange MachineRegisterInfo::useOperands(Register Reg, bool IncludeDebug) noexcept {
+  return RegOperandRange(headFor(Reg), true, false, !IncludeDebug);
+}
+
+RegOperandRange MachineRegisterInfo::defOperands(Register Reg) noexcept {
+  return RegOperandRange(headFor(Reg), false, true, false);
+}
+
+bool MachineRegisterInfo::useEmpty(Register Reg, bool IncludeDebug) const noexcept {
+  for (MachineOperand *Operand = headFor(Reg); Operand != nullptr;
+       Operand = Operand->NextRegOperand) {
+    if (Operand->isUse() && (IncludeDebug || !Operand->isDebugUse()))
+      return false;
+  }
+  return true;
+}
+
+bool MachineRegisterInfo::hasOneUse(Register Reg, bool IncludeDebug) const noexcept {
+  bool FoundUse = false;
+  for (MachineOperand *Operand = headFor(Reg); Operand != nullptr;
+       Operand = Operand->NextRegOperand) {
+    if (!Operand->isUse() || (!IncludeDebug && Operand->isDebugUse()))
+      continue;
+    if (FoundUse)
+      return false;
+    FoundUse = true;
+  }
+  return FoundUse;
+}
+
+const MachineOperand *MachineRegisterInfo::getUniqueVRegDef(Register Reg) const noexcept {
+  if (!isKnownVirtualRegister(Reg))
+    return nullptr;
+
+  const MachineOperand *UniqueDef = nullptr;
+  for (MachineOperand *Operand = headFor(Reg); Operand != nullptr;
+       Operand = Operand->NextRegOperand) {
+    if (!Operand->isDef())
+      continue;
+    if (UniqueDef != nullptr)
+      return nullptr;
+    UniqueDef = Operand;
+  }
+  return UniqueDef;
+}
+
+Expected<std::size_t> MachineRegisterInfo::replaceRegWith(Register OldReg, Register NewReg) {
+  if (OldReg.isNoRegister() || NewReg.isNoRegister()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "register replacement requires two nonzero registers");
+  }
+  if ((OldReg.isVirtual() && !isKnownVirtualRegister(OldReg)) ||
+      (NewReg.isVirtual() && !isKnownVirtualRegister(NewReg))) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "register replacement references an unknown virtual register");
+  }
+
+  std::size_t ReplacementCount = 0;
+  MachineOperand *Operand = headFor(OldReg);
+  while (Operand != nullptr) {
+    MachineOperand *Next = Operand->NextRegOperand;
+    const auto Result = Operand->setRegister(NewReg);
+    if (!Result)
+      return std::unexpected(Result.error());
+    ++ReplacementCount;
+    Operand = Next;
+  }
+  return ReplacementCount;
+}
+
+Expected<void> MachineRegisterInfo::verifyDefUseChains() const {
+  std::unordered_set<const MachineOperand *> SeenOperands;
+
+  for (const auto &[Reg, HeadStorage] : DefUseHeads) {
+    MachineOperand *const *ExpectedPreviousLink = &HeadStorage->Head;
+    for (MachineOperand *Operand = HeadStorage->Head; Operand != nullptr;
+         Operand = Operand->NextRegOperand) {
+      if (!SeenOperands.insert(Operand).second) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "register def-use chains contain a cycle or duplicate operand");
+      }
+      if (!Operand->isRegister() || Operand->registerValue() != Reg) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "register def-use chain contains an operand for another register");
+      }
+      if (Operand->LinkedRegInfo != this || Operand->PreviousRegLink != ExpectedPreviousLink) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "register def-use chain back-link is corrupt");
+      }
+      ExpectedPreviousLink = &Operand->NextRegOperand;
+    }
+  }
+
+  return {};
+}
+
+MachineOperand *MachineRegisterInfo::headFor(Register Reg) const noexcept {
+  const auto Position = DefUseHeads.find(Reg);
+  if (Position == DefUseHeads.end())
+    return nullptr;
+  return Position->second->Head;
+}
+
+void MachineRegisterInfo::linkOperand(MachineOperand &Operand) {
+  const auto Reg = Operand.registerValue();
+  if (!Reg || Reg->isNoRegister())
+    return;
+
+  auto &HeadStorage = DefUseHeads[*Reg];
+  if (!HeadStorage)
+    HeadStorage = std::make_unique<RegOperandListHead>();
+
+  Operand.unlinkFromRegInfo();
+  Operand.LinkedRegInfo = this;
+  Operand.PreviousRegLink = &HeadStorage->Head;
+  Operand.NextRegOperand = HeadStorage->Head;
+  if (HeadStorage->Head != nullptr)
+    HeadStorage->Head->PreviousRegLink = &Operand.NextRegOperand;
+  HeadStorage->Head = &Operand;
+}
+
+} // namespace rcc
diff --git a/backend/unittests/CodeGen/CMakeLists.txt b/backend/unittests/CodeGen/CMakeLists.txt
index 15b0a44..cad2a44 100644
--- a/backend/unittests/CodeGen/CMakeLists.txt
+++ b/backend/unittests/CodeGen/CMakeLists.txt
@@ -3,6 +3,7 @@
 set(
   RCCBackendCodeGenTestSources
   CoreTypesTest.cpp
+  MachineIRCoreTest.cpp
   MachineValueTypesTest.cpp
 )
 
@@ -21,11 +22,22 @@ add_test(
   COMMAND RCCBackendCodeGenMachineValueTypesTests
 )
 
+add_executable(RCCBackendCodeGenMachineIRCoreTests MachineIRCoreTest.cpp)
+rcc_backend_configure_target(RCCBackendCodeGenMachineIRCoreTests)
+target_link_libraries(RCCBackendCodeGenMachineIRCoreTests PRIVATE RCCBackend::CodeGen)
+
+add_test(
+  NAME RCCBackend.CodeGen.MachineIRCore
+  COMMAND RCCBackendCodeGenMachineIRCoreTests
+)
+
 rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/CoreTypesTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRCoreTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineValueTypesTest.cpp"
 )
 rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/CoreTypesTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRCoreTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineValueTypesTest.cpp"
 )
diff --git a/backend/unittests/CodeGen/MachineIRCoreTest.cpp b/backend/unittests/CodeGen/MachineIRCoreTest.cpp
new file mode 100644
index 0000000..1083422
--- /dev/null
+++ b/backend/unittests/CodeGen/MachineIRCoreTest.cpp
@@ -0,0 +1,467 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/LowLevelType.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineCFGUpdater.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineMemOperand.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/RegisterMask.h"
+
+#include <array>
+#include <cstddef>
+#include <cstdint>
+#include <iostream>
+#include <memory>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <vector>
+
+namespace {
+
+class TestContext final {
+public:
+  void expect(bool Condition, std::string_view Message) {
+    if (Condition)
+      return;
+    std::cerr << Message << '\n';
+    ++FailureCount;
+  }
+
+  [[nodiscard]] int result() const noexcept {
+    return FailureCount == 0 ? 0 : 1;
+  }
+
+private:
+  int FailureCount = 0;
+};
+
+[[nodiscard]] std::unique_ptr<rcc::MachineFunction>
+createFunction(TestContext &Context, std::string Name, std::uint64_t ID) {
+  auto Function =
+      rcc::MachineFunction::create(std::move(Name), rcc::MachineFunctionStableID::fromValue(ID));
+  Context.expect(Function.has_value(), "valid machine function construction must succeed");
+  if (!Function)
+    return nullptr;
+  return std::move(*Function);
+}
+
+[[nodiscard]] rcc::MachineBasicBlock *createLinkedBlock(TestContext &Context,
+                                                        rcc::MachineFunction &Function) {
+  auto Block = Function.createBasicBlock();
+  Context.expect(Block.has_value(), "basic block allocation must succeed");
+  if (!Block)
+    return nullptr;
+  auto LinkResult = Function.appendBlock(**Block);
+  Context.expect(LinkResult.has_value(), "basic block insertion must succeed");
+  if (!LinkResult)
+    return nullptr;
+  return *Block;
+}
+
+[[nodiscard]] bool addRegisterOperand(TestContext &Context, rcc::MachineInstr &Instruction,
+                                      rcc::Register Reg, rcc::RegisterOperandFlags Flags) {
+  auto Operand = rcc::MachineOperand::registerOperand(Reg, Flags);
+  Context.expect(Operand.has_value(), "valid register operand construction must succeed");
+  if (!Operand)
+    return false;
+  auto AddResult = Instruction.addOperand(std::move(*Operand));
+  Context.expect(AddResult.has_value(), "register operand insertion must succeed");
+  return AddResult.has_value();
+}
+
+[[nodiscard]] std::size_t countOperands(rcc::RegOperandRange Range) {
+  std::size_t Count = 0;
+  for ([[maybe_unused]] const rcc::MachineOperand &Operand : Range)
+    ++Count;
+  return Count;
+}
+
+rcc::MachineMemOperandDesc makeLoadDescription() {
+  rcc::MachineMemOperandDesc Description;
+  Description.Accesses = rcc::MemoryAccessFlags{
+      rcc::MemoryAccessFlag::Load,
+      rcc::MemoryAccessFlag::Dereferenceable,
+  };
+  Description.Size = *rcc::MemorySize::fixed(8);
+  Description.Align = *rcc::Alignment::create(8);
+  Description.Base = rcc::MemoryBase::frameIndex(rcc::FrameIndex::fromValue(0));
+  return Description;
+}
+
+void testOperandKinds(TestContext &Context) {
+  auto Function = createFunction(Context, "operands", 1);
+  if (!Function)
+    return;
+  auto Block = Function->createBasicBlock();
+  Context.expect(Block.has_value(), "operand test block allocation must succeed");
+  if (!Block)
+    return;
+
+  const std::array<std::uint64_t, 1> HalfWords{0x3c00};
+  auto HalfBits = rcc::FloatingPointBits::create(rcc::FloatSemantics::IEEEHalf, HalfWords);
+  Context.expect(HalfBits.has_value(), "well-sized floating immediate must be accepted");
+  if (!HalfBits)
+    return;
+  Context.expect(HalfBits->bitWidth() == 16 && HalfBits->words()[0] == 0x3c00,
+                 "floating immediate must preserve semantics and raw bits");
+
+  const std::array<std::uint64_t, 1> OverflowHalfWords{0x10000};
+  Context.expect(!rcc::FloatingPointBits::create(rcc::FloatSemantics::IEEEHalf, OverflowHalfWords),
+                 "floating immediate bits above semantics width must be rejected");
+  const std::array<std::uint64_t, 2> TooManyHalfWords{0, 0};
+  Context.expect(!rcc::FloatingPointBits::create(rcc::FloatSemantics::IEEEHalf, TooManyHalfWords),
+                 "floating immediate word-count mismatch must be rejected");
+
+  auto Virtual = Function->registerInfo().createVirtualRegister(*rcc::LLT::makeInteger(32));
+  Context.expect(Virtual.has_value(), "operand test virtual register must be created");
+  if (!Virtual)
+    return;
+
+  auto RegOperand = rcc::MachineOperand::registerOperand(
+      *Virtual, rcc::RegisterOperandFlags{rcc::RegisterOperandFlag::Use});
+  Context.expect(RegOperand && RegOperand->kind() == rcc::MachineOperand::Kind::Register,
+                 "register operand must preserve its kind");
+  Context.expect(!rcc::MachineOperand::registerOperand(*Virtual, {}),
+                 "register operand without def/use role must be rejected");
+  Context.expect(!rcc::MachineOperand::registerOperand(
+                     *Virtual, rcc::RegisterOperandFlags{rcc::RegisterOperandFlag::Define,
+                                                         rcc::RegisterOperandFlag::Kill}),
+                 "kill flag on register definition must be rejected");
+
+  auto Immediate = rcc::MachineOperand::immediate(-9, 17);
+  Context.expect(Immediate.kind() == rcc::MachineOperand::Kind::Immediate &&
+                     *Immediate.getIf<std::int64_t>() == -9 && Immediate.targetFlags() == 17,
+                 "immediate operand must preserve value and target flags");
+
+  auto Floating = rcc::MachineOperand::floatingImmediate(*HalfBits);
+  Context.expect(Floating.kind() == rcc::MachineOperand::Kind::FloatingImmediate,
+                 "floating operand must preserve its kind");
+  auto BlockRef = rcc::MachineOperand::basicBlock(**Block);
+  Context.expect(BlockRef.getIf<rcc::BasicBlockOperand>()->Block == *Block,
+                 "basic block operand must preserve its target");
+  auto Frame = rcc::MachineOperand::frameIndex(rcc::FrameIndex::fromValue(4), -8);
+  Context.expect(Frame.getIf<rcc::FrameIndexOperand>()->Offset == -8,
+                 "frame index operand must preserve its offset");
+  auto Constant = rcc::MachineOperand::constantPool(rcc::ConstantPoolIndex::fromValue(2), 3);
+  Context.expect(Constant.kind() == rcc::MachineOperand::Kind::ConstantPoolIndex,
+                 "constant pool operand must preserve its kind");
+  auto Jump = rcc::MachineOperand::jumpTable(rcc::JumpTableIndex::fromValue(5));
+  Context.expect(Jump.kind() == rcc::MachineOperand::Kind::JumpTableIndex,
+                 "jump table operand must preserve its kind");
+
+  auto Global = rcc::MachineOperand::globalSymbol("global", 12);
+  auto External = rcc::MachineOperand::externalSymbol("external", -4);
+  auto BlockAddress = rcc::MachineOperand::blockAddress("function", "block", 2);
+  Context.expect(Global && External && BlockAddress, "valid symbol operands must be accepted");
+  Context.expect(!rcc::MachineOperand::globalSymbol(""),
+                 "empty global symbol operand must be rejected");
+  Context.expect(!rcc::MachineOperand::blockAddress("", "block"),
+                 "incomplete block address operand must be rejected");
+
+  auto Mask = std::make_shared<const rcc::RegisterMask>(std::vector<std::uint64_t>{0xffff});
+  auto MaskOperand = rcc::MachineOperand::registerMask(Mask);
+  Context.expect(MaskOperand && MaskOperand->kind() == rcc::MachineOperand::Kind::RegisterMask,
+                 "register mask operand must preserve shared immutable mask");
+  Context.expect(!rcc::MachineOperand::registerMask(nullptr),
+                 "null register mask operand must be rejected");
+
+  auto Metadata = rcc::MachineOperand::metadata("source-marker");
+  Context.expect(Metadata && Metadata->kind() == rcc::MachineOperand::Kind::Metadata,
+                 "metadata operand must preserve its kind");
+  Context.expect(!rcc::MachineOperand::metadata(""), "empty metadata marker must be rejected");
+
+  auto Target = rcc::MachineOperand::targetIndex(rcc::TargetIndex::fromValue(8), 9);
+  Context.expect(Target.getIf<rcc::TargetIndexOperand>()->Offset == 9,
+                 "target index operand must preserve its offset");
+  auto MCSymbol = rcc::MachineOperand::mcSymbol(".Ltmp0", 1);
+  Context.expect(MCSymbol && MCSymbol->kind() == rcc::MachineOperand::Kind::MCSymbol,
+                 "MC symbol precursor must preserve its kind");
+
+  const auto Clone = Immediate.cloneDetached();
+  Context.expect(Clone.parent() == nullptr &&
+                     *Clone.getIf<std::int64_t>() == *Immediate.getIf<std::int64_t>(),
+                 "detached operand clone must preserve payload without ownership");
+  Context.expect(!Immediate.setRegister(*Virtual),
+                 "register mutation on non-register operand must be rejected");
+}
+
+void testRegisterInfoAndOperandMovement(TestContext &Context) {
+  auto Function = createFunction(Context, "def_use", 2);
+  if (!Function)
+    return;
+  rcc::MachineBasicBlock *Block = createLinkedBlock(Context, *Function);
+  if (Block == nullptr)
+    return;
+
+  auto I32 = rcc::LLT::makeInteger(32);
+  Context.expect(I32.has_value(), "i32 construction for MRI test must succeed");
+  if (!I32)
+    return;
+  auto V0 = Function->registerInfo().createVirtualRegister(*I32);
+  auto V1 = Function->registerInfo().createVirtualRegister(*I32);
+  Context.expect(V0 && V1, "MRI must allocate monotonic virtual registers");
+  if (!V0 || !V1)
+    return;
+  Context.expect(V0->virtualIndex() == 0 && V1->virtualIndex() == 1,
+                 "MRI virtual register indices must start at zero and increase");
+
+  auto PhysReg = rcc::PhysicalRegister::create(7);
+  Context.expect(PhysReg.has_value(), "MRI test physical register must be valid");
+  if (!PhysReg)
+    return;
+  const rcc::Register Physical = rcc::Register::fromPhysical(*PhysReg);
+
+  auto Instruction = Function->createInstruction(rcc::Opcode::fromValue(1));
+  Context.expect(Instruction.has_value(), "machine instruction allocation must succeed");
+  if (!Instruction)
+    return;
+  rcc::MachineInstr *Instr = *Instruction;
+
+  if (!addRegisterOperand(Context, *Instr, *V0,
+                          rcc::RegisterOperandFlags{rcc::RegisterOperandFlag::Define}) ||
+      !addRegisterOperand(Context, *Instr, *V0,
+                          rcc::RegisterOperandFlags{rcc::RegisterOperandFlag::Use}) ||
+      !addRegisterOperand(Context, *Instr, *V0,
+                          rcc::RegisterOperandFlags{rcc::RegisterOperandFlag::Use,
+                                                    rcc::RegisterOperandFlag::Debug}) ||
+      !addRegisterOperand(Context, *Instr, Physical,
+                          rcc::RegisterOperandFlags{rcc::RegisterOperandFlag::Use})) {
+    return;
+  }
+
+  Context.expect(Function->registerInfo().useEmpty(*V0),
+                 "detached instruction operands must not enter def-use chains");
+  auto LinkInstruction = Block->appendInstruction(*Instr);
+  Context.expect(LinkInstruction.has_value(), "instruction insertion must succeed");
+  if (!LinkInstruction)
+    return;
+
+  Context.expect(countOperands(Function->registerInfo().regOperands(*V0)) == 3,
+                 "def-use chain must include definition, use, and debug use");
+  Context.expect(countOperands(Function->registerInfo().useOperands(*V0)) == 2,
+                 "use iterator must include ordinary and debug uses");
+  Context.expect(countOperands(Function->registerInfo().useOperands(*V0, false)) == 1,
+                 "nodbg use iterator must filter debug operands");
+  Context.expect(Function->registerInfo().getUniqueVRegDef(*V0) == Instr->operandAt(0),
+                 "unique virtual register definition must be discoverable");
+  Context.expect(countOperands(Function->registerInfo().regOperands(Physical)) == 1,
+                 "physical registers must participate in exact def-use chains");
+
+  rcc::MachineOperand *const OldOperandAddress = Instr->operandAt(0);
+  Instr->reserveOperands(128);
+  Context.expect(Instr->operandAt(0) != nullptr && Instr->operandAt(0)->parent() == Instr,
+                 "operand relocation must preserve instruction ownership");
+  Context.expect(Function->registerInfo().verifyDefUseChains().has_value(),
+                 "operand relocation must repair intrusive def-use links");
+  Context.expect(OldOperandAddress != Instr->operandAt(0) ||
+                     Function->registerInfo().getUniqueVRegDef(*V0) == Instr->operandAt(0),
+                 "def-use head must follow an operand when its address changes");
+
+  auto TieResult = Instr->tieOperands(0, 1);
+  Context.expect(TieResult.has_value(), "valid def-use operand tie must succeed");
+  const auto DetachedTieClone = Instr->operandAt(0)->cloneDetached();
+  Context.expect(!DetachedTieClone.tiedOperandIndex(),
+                 "single detached operand clone must not retain an instruction-local tie");
+  auto InsertResult = Instr->insertOperand(0, rcc::MachineOperand::immediate(5));
+  Context.expect(InsertResult.has_value(), "operand insertion before a tie must succeed");
+  Context.expect(Instr->operandAt(1)->tiedOperandIndex() == 2 &&
+                     Instr->operandAt(2)->tiedOperandIndex() == 1,
+                 "operand insertion must rewrite both tie indices");
+  auto EraseResult = Instr->eraseOperand(0);
+  Context.expect(EraseResult.has_value(), "temporary operand erasure must succeed");
+  Context.expect(Instr->operandAt(0)->tiedOperandIndex() == 1 &&
+                     Instr->operandAt(1)->tiedOperandIndex() == 0,
+                 "operand erasure must rewrite both tie indices");
+  Context.expect(Instr->untieOperand(0).has_value(), "reciprocal operand tie must be removable");
+
+  auto SetRegisterResult = Instr->operandAt(1)->setRegister(*V1);
+  Context.expect(SetRegisterResult.has_value(), "register operand rebinding must succeed");
+  Context.expect(Function->registerInfo().useEmpty(*V0, false),
+                 "register rebinding must unlink the old ordinary use");
+  Context.expect(Function->registerInfo().hasOneUse(*V1),
+                 "register rebinding must link the new use");
+
+  auto ReplaceResult = Function->registerInfo().replaceRegWith(*V1, *V0);
+  Context.expect(ReplaceResult && *ReplaceResult == 1,
+                 "replaceRegWith must rewrite every linked operand exactly once");
+  Context.expect(Function->registerInfo().verifyDefUseChains().has_value(),
+                 "register replacement must preserve exact def-use chains");
+
+  for (std::int64_t Value = 0; Value < 64; ++Value) {
+    auto Result = Instr->addOperand(rcc::MachineOperand::immediate(Value));
+    Context.expect(Result.has_value(), "variadic immediate operand insertion must succeed");
+  }
+  Context.expect(Function->registerInfo().verifyDefUseChains().has_value(),
+                 "repeated operand growth must preserve def-use links");
+
+  auto &MRI = Function->registerInfo();
+  Context.expect(MRI.setRegisterBank(*V0, rcc::RegisterBankID::fromValue(3)).has_value(),
+                 "MRI must record a register bank");
+  Context.expect(MRI.setRegisterClass(*V0, rcc::RegisterClassID::fromValue(4)).has_value(),
+                 "MRI must record a register class");
+  Context.expect(MRI.addAllocationHint(*V0, *PhysReg).has_value(),
+                 "MRI must record a physical allocation hint");
+  auto V0Info = MRI.virtualRegisterInfo(*V0);
+  Context.expect(V0Info && V0Info->get().Type == I32 &&
+                     V0Info->get().Bank == rcc::RegisterBankID::fromValue(3) &&
+                     V0Info->get().RegClass == rcc::RegisterClassID::fromValue(4),
+                 "MRI virtual register properties must evolve without losing LLT");
+
+  Context.expect(MRI.addLiveIn(*PhysReg, *V0).has_value(),
+                 "MRI must record function physical live-ins");
+  Context.expect(!MRI.addLiveIn(*PhysReg, *V0),
+                 "duplicate function physical live-ins must be rejected");
+  Context.expect(MRI.reservePhysicalRegister(*PhysReg).has_value(),
+                 "MRI must record reserved physical registers");
+  Context.expect(MRI.isReserved(*PhysReg),
+                 "MRI reserved-register query must find recorded register");
+
+  auto DeadVReg = MRI.createVirtualRegister(*I32);
+  Context.expect(DeadVReg && MRI.eraseVirtualRegister(*DeadVReg).has_value(),
+                 "unused virtual register must become a tombstone");
+  auto LaterVReg = MRI.createVirtualRegister(*I32);
+  Context.expect(LaterVReg && LaterVReg->virtualIndex() != DeadVReg->virtualIndex(),
+                 "MRI must not reuse tombstoned virtual register indices");
+  Context.expect(!MRI.eraseVirtualRegister(*V0),
+                 "virtual register with linked operands must not be erased");
+
+  auto ZombieVReg = MRI.createVirtualRegister(*I32);
+  auto ZombieInstr = Function->createInstruction(rcc::Opcode::fromValue(2));
+  Context.expect(ZombieVReg && ZombieInstr,
+                 "detached tombstone validation setup must allocate objects");
+  if (ZombieVReg && ZombieInstr) {
+    Context.expect(addRegisterOperand(Context, **ZombieInstr, *ZombieVReg,
+                                      rcc::RegisterOperandFlags{rcc::RegisterOperandFlag::Use}),
+                   "detached instruction must initially accept its live virtual register");
+    Context.expect(MRI.eraseVirtualRegister(*ZombieVReg).has_value(),
+                   "detached operand must not make an unpublished vreg live");
+    const std::size_t OriginalInstructionCount = Block->instructionCount();
+    Context.expect(!Block->appendInstruction(**ZombieInstr),
+                   "instruction insertion must reject a tombstoned virtual register");
+    Context.expect((*ZombieInstr)->parent() == nullptr &&
+                       Block->instructionCount() == OriginalInstructionCount,
+                   "failed instruction insertion must not mutate block layout");
+    Context.expect(!(*ZombieInstr)->operandAt(0)->setRegister(*ZombieVReg),
+                   "detached register mutation must reject a tombstoned vreg");
+  }
+
+  auto UnlinkResult = Block->removeInstruction(*Instr);
+  Context.expect(UnlinkResult.has_value(), "instruction removal must succeed");
+  Context.expect(MRI.useEmpty(*V0) && MRI.getUniqueVRegDef(*V0) == nullptr,
+                 "instruction removal must unlink every register operand");
+  Context.expect(MRI.verifyDefUseChains().has_value(),
+                 "empty def-use lists after removal must remain structurally valid");
+  Context.expect(Block->appendInstruction(*Instr).has_value(),
+                 "detached instruction must be reinsertable");
+  Context.expect(MRI.getUniqueVRegDef(*V0) == Instr->operandAt(0),
+                 "instruction reinsertion must rebuild register links");
+}
+
+void testOwnershipCFGAndMemory(TestContext &Context) {
+  auto Function = createFunction(Context, "cfg", 3);
+  auto OtherFunction = createFunction(Context, "other", 4);
+  if (!Function || !OtherFunction)
+    return;
+
+  rcc::MachineBasicBlock *Entry = createLinkedBlock(Context, *Function);
+  rcc::MachineBasicBlock *Left = createLinkedBlock(Context, *Function);
+  rcc::MachineBasicBlock *Right = createLinkedBlock(Context, *Function);
+  rcc::MachineBasicBlock *Foreign = createLinkedBlock(Context, *OtherFunction);
+  if (Entry == nullptr || Left == nullptr || Right == nullptr || Foreign == nullptr)
+    return;
+
+  Context.expect(Function->blockCount() == 3,
+                 "machine function block list must preserve layout count");
+  Context.expect(Entry->layoutIndex() == 0 && Left->layoutIndex() == 1 && Right->layoutIndex() == 2,
+                 "block layout indices must follow intrusive layout order");
+
+  auto Half = rcc::BranchProbability::fromFraction(1, 2);
+  Context.expect(Half.has_value(), "CFG test probability must be valid");
+  if (!Half)
+    return;
+  auto CFG = Function->cfgUpdater();
+  Context.expect(CFG.addSuccessor(*Entry, *Left, *Half).has_value() &&
+                     CFG.addSuccessor(*Entry, *Left, *Half).has_value(),
+                 "duplicate semantic branches must merge into one CFG successor");
+  Context.expect(Entry->successors().size() == 1 && Left->predecessors().size() == 1,
+                 "CFG must not contain duplicate successor or predecessor entries");
+  Context.expect(CFG.addSuccessor(*Entry, *Right, *Half).has_value(),
+                 "second CFG successor must be insertable");
+  Context.expect(!CFG.addSuccessor(*Entry, *Foreign, *Half),
+                 "cross-function CFG edge must be rejected");
+  Context.expect(!CFG.replaceSuccessor(*Entry, *Left, *Foreign) &&
+                     Entry->successors().size() == 2 && Left->predecessors().size() == 1,
+                 "cross-function CFG replacement must fail without mutating existing edges");
+
+  Context.expect(CFG.replaceSuccessor(*Entry, *Left, *Right).has_value(),
+                 "CFG successor replacement must succeed");
+  Context.expect(Entry->successors().size() == 1 && Left->predecessors().empty() &&
+                     Right->predecessors().size() == 1,
+                 "CFG replacement must merge duplicate target and repair predecessors");
+  Context.expect(CFG.transferSuccessors(*Entry, *Left).has_value(),
+                 "CFG successor transfer must succeed");
+  Context.expect(Entry->successors().empty() && Left->successors().size() == 1 &&
+                     Right->predecessors()[0] == Left,
+                 "CFG successor transfer must update both directions");
+  Context.expect(CFG.disconnectBlock(*Left).has_value(),
+                 "CFG block disconnection must remove incoming and outgoing edges");
+  Context.expect(Left->successors().empty() && Right->predecessors().empty(),
+                 "CFG disconnection must leave no stale reciprocal edges");
+
+  auto Instr = Function->createInstruction(rcc::Opcode::fromValue(9));
+  auto NextInstr = Function->createInstruction(rcc::Opcode::fromValue(10));
+  Context.expect(Instr && NextInstr, "instruction arena allocation must succeed");
+  if (!Instr || !NextInstr)
+    return;
+  Context.expect(Entry->appendInstruction(**Instr).has_value(),
+                 "first block instruction must be inserted");
+  Context.expect(Entry->insertInstructionBefore(**Instr, **NextInstr).has_value(),
+                 "instruction insertion before a stable node must succeed");
+  Context.expect(Entry->firstInstruction() == *NextInstr && Entry->lastInstruction() == *Instr &&
+                     Entry->instructionCount() == 2,
+                 "intrusive instruction list must preserve order and endpoints");
+
+  auto CrossBlockOperand = rcc::MachineOperand::basicBlock(*Foreign);
+  Context.expect(!(*Instr)->addOperand(std::move(CrossBlockOperand)),
+                 "instruction must reject a block operand from another function");
+
+  auto MemOperand = Function->createMemOperand(makeLoadDescription());
+  auto ForeignMemOperand = OtherFunction->createMemOperand(makeLoadDescription());
+  Context.expect(MemOperand && ForeignMemOperand,
+                 "function arena must allocate immutable memory operands");
+  if (MemOperand && ForeignMemOperand) {
+    Context.expect((*Instr)->addMemOperand(**MemOperand).has_value(),
+                   "instruction must accept a memory operand owned by its function");
+    Context.expect(!(*Instr)->addMemOperand(**ForeignMemOperand),
+                   "instruction must reject a memory operand from another function");
+  }
+
+  const rcc::MachineBasicBlock *StableEntryAddress = Entry;
+  const rcc::MachineInstr *StableInstrAddress = *Instr;
+  for (std::uint32_t Index = 0; Index < 128; ++Index) {
+    auto NewBlock = Function->createBasicBlock();
+    auto NewInstr = Function->createInstruction(rcc::Opcode::fromValue(Index + 100));
+    Context.expect(NewBlock && NewInstr, "arena growth must continue to allocate objects");
+  }
+  Context.expect(StableEntryAddress == Entry && StableInstrAddress == *Instr,
+                 "arena growth must preserve block and instruction addresses");
+
+  Context.expect(Function->removeBlock(*Right).has_value(),
+                 "disconnected empty block must be removable from layout");
+  Context.expect(!Right->isLinked() && Function->blockCount() == 2,
+                 "removed block must leave layout while retaining stable storage");
+}
+
+} // namespace
+
+int main() {
+  TestContext Context;
+  testOperandKinds(Context);
+  testRegisterInfoAndOperandMovement(Context);
+  testOwnershipCFGAndMemory(Context);
+  return Context.result();
+}