[MC] Implement RV64GC object emission

8 files changed, 2363 insertions, 0 deletions

diff --git a/backend/lib/MC/CMakeLists.txt b/backend/lib/MC/CMakeLists.txt
index a55b468..330ede3 100644
--- a/backend/lib/MC/CMakeLists.txt
+++ b/backend/lib/MC/CMakeLists.txt
@@ -2,20 +2,34 @@
 
 set(
   RCCBackendMCSources
+  ELFObjectWriter.cpp
   MCCFI.cpp
+  MCDwarfFrameEmitter.cpp
+  MCAsmBackend.cpp
+  MCAssembler.cpp
   MCContext.cpp
   MCExpr.cpp
+  MCFixup.cpp
   MCInstPrinter.cpp
+  MCObjectStreamer.cpp
   MCSection.cpp
   MCStreamer.cpp
 )
 set(
   RCCBackendMCHeaders
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MC/ELFObjectWriter.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MC/MCCFI.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MC/MCDwarfFrameEmitter.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MC/MCAsmBackend.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MC/MCAssembler.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MC/MCCodeEmitter.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MC/MCContext.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MC/MCExpr.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MC/MCFixup.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MC/MCInst.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MC/MCInstPrinter.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MC/MCObjectStreamer.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MC/MCObjectWriter.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MC/MCSection.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MC/MCStreamer.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MC/MCSymbol.h"
diff --git a/backend/lib/MC/ELFObjectWriter.cpp b/backend/lib/MC/ELFObjectWriter.cpp
new file mode 100644
index 0000000..730ef72
--- /dev/null
+++ b/backend/lib/MC/ELFObjectWriter.cpp
@@ -0,0 +1,707 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/MC/ELFObjectWriter.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <limits>
+#include <optional>
+#include <span>
+#include <string>
+#include <string_view>
+#include <unordered_map>
+#include <utility>
+#include <vector>
+
+namespace rcc::mc {
+namespace {
+
+constexpr std::uint32_t SHTNull = 0;
+constexpr std::uint32_t SHTProgBits = 1;
+constexpr std::uint32_t SHTSymTab = 2;
+constexpr std::uint32_t SHTStrTab = 3;
+constexpr std::uint32_t SHTRela = 4;
+constexpr std::uint32_t SHTNoBits = 8;
+constexpr std::uint32_t SHTRel = 9;
+constexpr std::uint32_t SHTGroup = 17;
+constexpr std::uint32_t SHTSymTabShndx = 18;
+constexpr std::uint16_t SHNUndefined = 0;
+constexpr std::uint32_t SHNLoReserve = 0xff00U;
+constexpr std::uint16_t SHNCommon = 0xfff2U;
+constexpr std::uint32_t GRPComdat = 1;
+
+constexpr std::uint64_t SHFWrite = 0x1;
+constexpr std::uint64_t SHFAlloc = 0x2;
+constexpr std::uint64_t SHFExecInstr = 0x4;
+constexpr std::uint64_t SHFMerge = 0x10;
+constexpr std::uint64_t SHFStrings = 0x20;
+constexpr std::uint64_t SHFInfoLink = 0x40;
+constexpr std::uint64_t SHFGroup = 0x200;
+constexpr std::uint64_t SHFTLS = 0x400;
+constexpr std::uint64_t SHFGNURetain = 0x200000;
+
+class StringTable final {
+public:
+  StringTable() {
+    Bytes.push_back(0);
+  }
+
+  [[nodiscard]] Expected<std::uint32_t> add(std::string_view Value) {
+    const auto Existing = Offsets.find(std::string(Value));
+    if (Existing != Offsets.end())
+      return Existing->second;
+    constexpr std::size_t Maximum = std::numeric_limits<std::uint32_t>::max();
+    if (Value.size() > Maximum - 1U || Bytes.size() > Maximum - Value.size() - 1U) {
+      return makeUnexpected(ErrorCode::ObjectWritingFailed, "ELF string table exceeds 4 GiB");
+    }
+    const auto Offset = static_cast<std::uint32_t>(Bytes.size());
+    Bytes.insert(Bytes.end(), Value.begin(), Value.end());
+    Bytes.push_back(0);
+    Offsets.emplace(std::string(Value), Offset);
+    return Offset;
+  }
+
+  [[nodiscard]] const std::vector<std::uint8_t> &bytes() const noexcept {
+    return Bytes;
+  }
+
+private:
+  std::vector<std::uint8_t> Bytes;
+  std::unordered_map<std::string, std::uint32_t> Offsets;
+};
+
+struct OutputSymbol final {
+  std::uint32_t Name = 0;
+  std::uint8_t Info = 0;
+  std::uint8_t Other = 0;
+  std::uint16_t Section = SHNUndefined;
+  std::uint64_t Value = 0;
+  std::uint64_t Size = 0;
+  const MCSymbol *Identity = nullptr;
+};
+
+struct OutputSection final {
+  std::string Name;
+  std::uint32_t NameOffset = 0;
+  std::uint32_t Type = SHTProgBits;
+  std::uint64_t Flags = 0;
+  std::uint64_t Alignment = 1;
+  std::uint64_t EntrySize = 0;
+  std::uint32_t Link = 0;
+  std::uint32_t Info = 0;
+  std::vector<std::uint8_t> Contents;
+  std::uint64_t AddressSize = 0;
+  std::uint64_t FileOffset = 0;
+  const MCSection *Input = nullptr;
+  std::optional<std::size_t> RelocationTarget;
+  MCSymbolRef GroupSignature;
+};
+
+[[nodiscard]] bool isPowerOfTwo(std::uint64_t Value) noexcept {
+  return Value != 0 && (Value & (Value - 1U)) == 0;
+}
+
+[[nodiscard]] bool isWriterManagedSectionType(std::uint32_t Type) noexcept {
+  switch (Type) {
+  case SHTNull:
+  case SHTSymTab:
+  case SHTStrTab:
+  case SHTRela:
+  case SHTNoBits:
+  case SHTRel:
+  case SHTGroup:
+  case SHTSymTabShndx:
+    return true;
+  default:
+    return false;
+  }
+}
+
+[[nodiscard]] Expected<std::uint64_t> checkedAdd(std::uint64_t Left, std::uint64_t Right,
+                                                 std::string_view Message) {
+  std::uint64_t Result = 0;
+  if (__builtin_add_overflow(Left, Right, &Result))
+    return makeUnexpected(ErrorCode::ObjectWritingFailed, std::string(Message));
+  return Result;
+}
+
+[[nodiscard]] Expected<std::uint64_t> alignTo(std::uint64_t Value, std::uint64_t Alignment) {
+  if (!isPowerOfTwo(Alignment))
+    return makeUnexpected(ErrorCode::ObjectWritingFailed, "ELF alignment is not a power of two");
+  auto Adjusted = checkedAdd(Value, Alignment - 1U, "ELF file offset overflows");
+  if (!Adjusted)
+    return std::unexpected(Adjusted.error());
+  return *Adjusted & ~(Alignment - 1U);
+}
+
+void appendU16(std::vector<std::uint8_t> &Output, std::uint16_t Value) {
+  Output.push_back(static_cast<std::uint8_t>(Value));
+  Output.push_back(static_cast<std::uint8_t>(Value >> 8U));
+}
+
+void appendU32(std::vector<std::uint8_t> &Output, std::uint32_t Value) {
+  for (std::uint32_t Shift = 0; Shift < 32; Shift += 8)
+    Output.push_back(static_cast<std::uint8_t>(Value >> Shift));
+}
+
+void appendU64(std::vector<std::uint8_t> &Output, std::uint64_t Value) {
+  for (std::uint32_t Shift = 0; Shift < 64; Shift += 8)
+    Output.push_back(static_cast<std::uint8_t>(Value >> Shift));
+}
+
+void writeU64(std::vector<std::uint8_t> &Output, std::size_t Offset, std::uint64_t Value) {
+  for (std::uint32_t Shift = 0; Shift < 64; Shift += 8)
+    Output[Offset + Shift / 8U] = static_cast<std::uint8_t>(Value >> Shift);
+}
+
+[[nodiscard]] std::uint64_t sectionFlags(MCSectionFlags Flags) noexcept {
+  std::uint64_t Result = 0;
+  if (Flags.has(MCSectionFlag::Writable))
+    Result |= SHFWrite;
+  if (Flags.has(MCSectionFlag::Alloc))
+    Result |= SHFAlloc;
+  if (Flags.has(MCSectionFlag::Executable))
+    Result |= SHFExecInstr;
+  if (Flags.has(MCSectionFlag::Merge))
+    Result |= SHFMerge;
+  if (Flags.has(MCSectionFlag::Strings))
+    Result |= SHFStrings;
+  if (Flags.has(MCSectionFlag::Group))
+    Result |= SHFGroup;
+  if (Flags.has(MCSectionFlag::TLS))
+    Result |= SHFTLS;
+  if (Flags.has(MCSectionFlag::Retain))
+    Result |= SHFGNURetain;
+  return Result;
+}
+
+[[nodiscard]] std::uint8_t symbolBinding(MCObjectSymbolBinding Binding) noexcept {
+  switch (Binding) {
+  case MCObjectSymbolBinding::Local:
+    return 0;
+  case MCObjectSymbolBinding::Global:
+    return 1;
+  case MCObjectSymbolBinding::Weak:
+    return 2;
+  }
+  return 0;
+}
+
+[[nodiscard]] std::uint8_t symbolType(MCObjectSymbolType Type) noexcept {
+  switch (Type) {
+  case MCObjectSymbolType::None:
+    return 0;
+  case MCObjectSymbolType::Object:
+    return 1;
+  case MCObjectSymbolType::Function:
+    return 2;
+  case MCObjectSymbolType::Section:
+    return 3;
+  case MCObjectSymbolType::TLSObject:
+    return 6;
+  }
+  return 0;
+}
+
+[[nodiscard]] std::uint8_t symbolVisibility(MCObjectSymbolVisibility Visibility) noexcept {
+  switch (Visibility) {
+  case MCObjectSymbolVisibility::Default:
+    return 0;
+  case MCObjectSymbolVisibility::Hidden:
+    return 2;
+  case MCObjectSymbolVisibility::Protected:
+    return 3;
+  }
+  return 0;
+}
+
+[[nodiscard]] Expected<void> appendAtOffset(std::vector<std::uint8_t> &Output, std::uint64_t Offset,
+                                            std::span<const std::uint8_t> Contents) {
+  if (Offset > std::numeric_limits<std::size_t>::max() ||
+      Contents.size() >
+          std::numeric_limits<std::size_t>::max() - static_cast<std::size_t>(Offset)) {
+    return makeUnexpected(ErrorCode::ObjectWritingFailed, "ELF output exceeds the host limit");
+  }
+  const std::size_t Position = static_cast<std::size_t>(Offset);
+  if (Output.size() > Position) {
+    return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                          "ELF output sections overlap in file layout");
+  }
+  if (Output.size() < Position)
+    Output.resize(Position);
+  Output.insert(Output.end(), Contents.begin(), Contents.end());
+  return {};
+}
+
+} // namespace
+
+Expected<std::vector<std::uint8_t>>
+ELF64LEObjectWriter::writeObject(const MCAssembledObject &Object) const {
+  if (Target.Machine == 0)
+    return makeUnexpected(ErrorCode::ObjectWritingFailed, "ELF target machine is not configured");
+
+  constexpr std::size_t ReservedOutputSections = 4;
+  constexpr std::size_t MaximumInputAndExtraSections = SHNLoReserve - ReservedOutputSections - 1U;
+  if (Object.Sections.size() > MaximumInputAndExtraSections ||
+      Target.ExtraSections.size() > MaximumInputAndExtraSections - Object.Sections.size()) {
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "ELF extended section numbering is not implemented");
+  }
+
+  std::vector<OutputSection> Sections;
+  Sections.push_back(OutputSection{.Name = {},
+                                   .NameOffset = 0,
+                                   .Type = SHTNull,
+                                   .Flags = 0,
+                                   .Alignment = 0,
+                                   .EntrySize = 0,
+                                   .Link = 0,
+                                   .Info = 0,
+                                   .Contents = {},
+                                   .AddressSize = 0,
+                                   .FileOffset = 0,
+                                   .Input = nullptr,
+                                   .RelocationTarget = std::nullopt,
+                                   .GroupSignature = {}});
+  const auto RequireSectionCapacity = [&Sections](std::size_t Additional) -> Expected<void> {
+    if (Sections.size() >= SHNLoReserve || Additional >= SHNLoReserve - Sections.size()) {
+      return makeUnexpected(ErrorCode::Unsupported,
+                            "ELF extended section numbering is not implemented");
+    }
+    return {};
+  };
+  auto InputCapacity = RequireSectionCapacity(Object.Sections.size());
+  if (!InputCapacity)
+    return std::unexpected(InputCapacity.error());
+  std::vector<std::uint32_t> InputSectionIndices(Object.Sections.size());
+  std::unordered_map<const MCSection *, bool> ExistingSections;
+  for (std::size_t Index = 0; Index < Object.Sections.size(); ++Index) {
+    const MCObjectSection &Input = Object.Sections[Index];
+    if (!Input.Section)
+      return makeUnexpected(ErrorCode::ObjectWritingFailed, "ELF input section is null");
+    if (!ExistingSections.emplace(Input.Section.get(), true).second) {
+      return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                            "ELF input contains a duplicate section identity");
+    }
+    const MCSectionDesc &Description = Input.Section->description();
+    auto DescriptionVerification = Description.verify();
+    if (!DescriptionVerification)
+      return std::unexpected(DescriptionVerification.error());
+    const bool NoBits =
+        Description.Kind == MCSectionKind::BSS || Description.Kind == MCSectionKind::TLSBSS;
+    if (!isPowerOfTwo(Input.Alignment) || Input.Alignment < Description.Alignment) {
+      return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                            "ELF input section has an invalid effective alignment");
+    }
+    if ((!NoBits && Input.AddressSize != Input.Contents.size()) ||
+        (NoBits && !Input.Contents.empty())) {
+      return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                            "ELF input section contents disagree with its address size");
+    }
+    if (NoBits && !Input.Relocations.empty()) {
+      return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                            "ELF NOBITS section cannot contain relocations");
+    }
+    const auto OutputIndex = static_cast<std::uint32_t>(Sections.size());
+    InputSectionIndices[Index] = OutputIndex;
+    Sections.push_back(
+        OutputSection{.Name = Description.Name,
+                      .NameOffset = 0,
+                      .Type = NoBits ? SHTNoBits : SHTProgBits,
+                      .Flags = sectionFlags(Description.Flags),
+                      .Alignment = Input.Alignment,
+                      .EntrySize = Description.EntrySize,
+                      .Link = 0,
+                      .Info = 0,
+                      .Contents = NoBits ? std::vector<std::uint8_t>{} : Input.Contents,
+                      .AddressSize = Input.AddressSize,
+                      .FileOffset = 0,
+                      .Input = Input.Section.get(),
+                      .RelocationTarget = std::nullopt,
+                      .GroupSignature = Description.Group});
+  }
+
+  for (const ELFExtraSection &Extra : Target.ExtraSections) {
+    if (Extra.Name.empty() || isWriterManagedSectionType(Extra.Type) ||
+        !isPowerOfTwo(Extra.Alignment) || (Extra.Flags & (SHFInfoLink | SHFGroup)) != 0 ||
+        (Extra.EntrySize != 0 && Extra.Contents.size() % Extra.EntrySize != 0)) {
+      return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                            "ELF extra section has an invalid description");
+    }
+    auto ExtraCapacity = RequireSectionCapacity(1);
+    if (!ExtraCapacity)
+      return std::unexpected(ExtraCapacity.error());
+    Sections.push_back(OutputSection{.Name = Extra.Name,
+                                     .NameOffset = 0,
+                                     .Type = Extra.Type,
+                                     .Flags = Extra.Flags,
+                                     .Alignment = Extra.Alignment,
+                                     .EntrySize = Extra.EntrySize,
+                                     .Link = 0,
+                                     .Info = 0,
+                                     .Contents = Extra.Contents,
+                                     .AddressSize = Extra.Contents.size(),
+                                     .FileOffset = 0,
+                                     .Input = nullptr,
+                                     .RelocationTarget = std::nullopt,
+                                     .GroupSignature = {}});
+  }
+
+  StringTable SymbolNames;
+  std::vector<OutputSymbol> LocalSymbols;
+  std::vector<OutputSymbol> GlobalSymbols;
+  std::unordered_map<const MCSymbol *, bool> ExistingSymbols;
+  for (const MCObjectSymbol &Input : Object.Symbols) {
+    if (!Input.Symbol)
+      return makeUnexpected(ErrorCode::ObjectWritingFailed, "ELF input symbol is null");
+    if (!ExistingSymbols.emplace(Input.Symbol.get(), true).second) {
+      return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                            "ELF input contains a duplicate symbol identity");
+    }
+    auto Name = SymbolNames.add(Input.Symbol->name());
+    if (!Name)
+      return std::unexpected(Name.error());
+    std::uint16_t Section = SHNUndefined;
+    std::uint64_t Value = Input.Value;
+    if (Input.CommonAlignment != 0) {
+      if (!isPowerOfTwo(Input.CommonAlignment) || Input.Size == 0 || Input.SectionIndex ||
+          Input.Binding == MCObjectSymbolBinding::Local || Input.Value != Input.CommonAlignment) {
+        return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                              "ELF common symbol has an invalid definition");
+      }
+      Section = SHNCommon;
+      Value = Input.CommonAlignment;
+    } else if (Input.SectionIndex) {
+      if (*Input.SectionIndex >= InputSectionIndices.size()) {
+        return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                              "ELF symbol references an invalid section");
+      }
+      const std::uint32_t Mapped = InputSectionIndices[*Input.SectionIndex];
+      if (Mapped >= SHNLoReserve) {
+        return makeUnexpected(ErrorCode::Unsupported,
+                              "ELF extended section indices are not implemented");
+      }
+      Section = static_cast<std::uint16_t>(Mapped);
+      const std::uint64_t SectionSize = Object.Sections[*Input.SectionIndex].AddressSize;
+      if (Input.Value > SectionSize || Input.Size > SectionSize - Input.Value) {
+        return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                              "ELF symbol range exceeds its section");
+      }
+    } else if (Input.Value != 0) {
+      return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                            "ELF undefined symbol has a nonzero value");
+    }
+    OutputSymbol Symbol{.Name = *Name,
+                        .Info = static_cast<std::uint8_t>((symbolBinding(Input.Binding) << 4U) |
+                                                          symbolType(Input.Type)),
+                        .Other = symbolVisibility(Input.Visibility),
+                        .Section = Section,
+                        .Value = Value,
+                        .Size = Input.Size,
+                        .Identity = Input.Symbol.get()};
+    if (Input.Binding == MCObjectSymbolBinding::Local)
+      LocalSymbols.push_back(Symbol);
+    else
+      GlobalSymbols.push_back(Symbol);
+  }
+
+  for (const OutputSection &Section : Sections) {
+    if (!Section.GroupSignature || ExistingSymbols.contains(Section.GroupSignature.get()))
+      continue;
+    auto Name = SymbolNames.add(Section.GroupSignature->name());
+    if (!Name)
+      return std::unexpected(Name.error());
+    GlobalSymbols.push_back(OutputSymbol{.Name = *Name,
+                                         .Info = static_cast<std::uint8_t>(1U << 4U),
+                                         .Other = 0,
+                                         .Section = SHNUndefined,
+                                         .Value = 0,
+                                         .Size = 0,
+                                         .Identity = Section.GroupSignature.get()});
+    ExistingSymbols.emplace(Section.GroupSignature.get(), true);
+  }
+
+  std::vector<OutputSymbol> Symbols;
+  Symbols.push_back(OutputSymbol{});
+  for (std::size_t Index = 1; Index < Sections.size(); ++Index) {
+    Symbols.push_back(OutputSymbol{.Name = 0,
+                                   .Info = static_cast<std::uint8_t>(3),
+                                   .Other = 0,
+                                   .Section = static_cast<std::uint16_t>(Index),
+                                   .Value = 0,
+                                   .Size = 0,
+                                   .Identity = nullptr});
+  }
+  constexpr std::size_t MaximumSymbolCount = std::numeric_limits<std::uint32_t>::max();
+  if (LocalSymbols.size() > MaximumSymbolCount - Symbols.size()) {
+    return makeUnexpected(ErrorCode::Unsupported, "ELF symbol index exceeds 32 bits");
+  }
+  Symbols.insert(Symbols.end(), LocalSymbols.begin(), LocalSymbols.end());
+  const std::uint32_t FirstGlobal = static_cast<std::uint32_t>(Symbols.size());
+  if (GlobalSymbols.size() > MaximumSymbolCount - Symbols.size()) {
+    return makeUnexpected(ErrorCode::Unsupported, "ELF symbol index exceeds 32 bits");
+  }
+  Symbols.insert(Symbols.end(), GlobalSymbols.begin(), GlobalSymbols.end());
+  std::unordered_map<const MCSymbol *, std::uint32_t> SymbolIndices;
+  for (std::size_t Index = 0; Index < Symbols.size(); ++Index) {
+    if (Symbols[Index].Identity)
+      SymbolIndices.emplace(Symbols[Index].Identity, static_cast<std::uint32_t>(Index));
+  }
+
+  for (std::size_t InputIndex = 0; InputIndex < Object.Sections.size(); ++InputIndex) {
+    const MCObjectSection &Input = Object.Sections[InputIndex];
+    if (Input.Relocations.empty())
+      continue;
+    if (Input.Relocations.size() > std::numeric_limits<std::size_t>::max() / 24U) {
+      return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                            "ELF relocation section exceeds the host limit");
+    }
+    std::vector<std::uint8_t> Contents;
+    Contents.reserve(Input.Relocations.size() * 24U);
+    for (const MCObjectRelocation &Relocation : Input.Relocations) {
+      const auto Symbol = SymbolIndices.find(Relocation.Symbol.get());
+      if (!Relocation.Symbol || Symbol == SymbolIndices.end()) {
+        return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                              "ELF relocation references an unknown symbol");
+      }
+      if (Relocation.Type == 0 || Relocation.Offset >= Input.AddressSize) {
+        return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                              "ELF relocation has an invalid type or section offset");
+      }
+      appendU64(Contents, Relocation.Offset);
+      appendU64(Contents, (static_cast<std::uint64_t>(Symbol->second) << 32U) | Relocation.Type);
+      appendU64(Contents, static_cast<std::uint64_t>(Relocation.Addend));
+    }
+    const std::uint32_t TargetSection = InputSectionIndices[InputIndex];
+    const MCSymbolRef GroupSignature = Sections[TargetSection].GroupSignature;
+    auto RelocationCapacity = RequireSectionCapacity(1);
+    if (!RelocationCapacity)
+      return std::unexpected(RelocationCapacity.error());
+    Sections.push_back(OutputSection{.Name = ".rela" + std::string(Input.Section->name()),
+                                     .NameOffset = 0,
+                                     .Type = SHTRela,
+                                     .Flags = SHFInfoLink | (GroupSignature ? SHFGroup : 0),
+                                     .Alignment = 8,
+                                     .EntrySize = 24,
+                                     .Link = 0,
+                                     .Info = TargetSection,
+                                     .Contents = std::move(Contents),
+                                     .AddressSize = 0,
+                                     .FileOffset = 0,
+                                     .Input = nullptr,
+                                     .RelocationTarget = InputIndex,
+                                     .GroupSignature = GroupSignature});
+  }
+
+  struct PendingGroup final {
+    MCSymbolRef Signature;
+    std::vector<std::uint32_t> Members;
+  };
+  std::vector<PendingGroup> Groups;
+  for (std::size_t SectionIndex = 1; SectionIndex < Sections.size(); ++SectionIndex) {
+    if (!Sections[SectionIndex].GroupSignature)
+      continue;
+    const auto Existing = std::ranges::find_if(Groups, [&](const PendingGroup &Group) {
+      return Group.Signature == Sections[SectionIndex].GroupSignature;
+    });
+    if (Existing == Groups.end()) {
+      Groups.push_back(PendingGroup{
+          .Signature = Sections[SectionIndex].GroupSignature,
+          .Members = {static_cast<std::uint32_t>(SectionIndex)},
+      });
+    } else {
+      Existing->Members.push_back(static_cast<std::uint32_t>(SectionIndex));
+    }
+  }
+  for (const PendingGroup &Group : Groups) {
+    const auto Signature = SymbolIndices.find(Group.Signature.get());
+    if (Signature == SymbolIndices.end() || (Symbols[Signature->second].Info >> 4U) == 0) {
+      return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                            "ELF COMDAT group requires a nonlocal signature symbol");
+    }
+    std::vector<std::uint8_t> Contents;
+    appendU32(Contents, GRPComdat);
+    for (const std::uint32_t Member : Group.Members)
+      appendU32(Contents, Member);
+    auto GroupCapacity = RequireSectionCapacity(1);
+    if (!GroupCapacity)
+      return std::unexpected(GroupCapacity.error());
+    Sections.push_back(OutputSection{.Name = ".group",
+                                     .NameOffset = 0,
+                                     .Type = SHTGroup,
+                                     .Flags = 0,
+                                     .Alignment = 4,
+                                     .EntrySize = 4,
+                                     .Link = 0,
+                                     .Info = Signature->second,
+                                     .Contents = std::move(Contents),
+                                     .AddressSize = 0,
+                                     .FileOffset = 0,
+                                     .Input = nullptr,
+                                     .RelocationTarget = std::nullopt,
+                                     .GroupSignature = {}});
+  }
+
+  auto MetadataCapacity = RequireSectionCapacity(3);
+  if (!MetadataCapacity)
+    return std::unexpected(MetadataCapacity.error());
+  const std::uint32_t SymTabIndex = static_cast<std::uint32_t>(Sections.size());
+  const std::uint32_t StrTabIndex = SymTabIndex + 1U;
+  for (OutputSection &Section : Sections) {
+    if (Section.Type == SHTGroup || Section.Type == SHTRela)
+      Section.Link = SymTabIndex;
+  }
+
+  std::vector<std::uint8_t> SymbolContents;
+  if (Symbols.size() > std::numeric_limits<std::size_t>::max() / 24U) {
+    return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                          "ELF symbol table exceeds the host limit");
+  }
+  SymbolContents.reserve(Symbols.size() * 24U);
+  for (const OutputSymbol &Symbol : Symbols) {
+    appendU32(SymbolContents, Symbol.Name);
+    SymbolContents.push_back(Symbol.Info);
+    SymbolContents.push_back(Symbol.Other);
+    appendU16(SymbolContents, Symbol.Section);
+    appendU64(SymbolContents, Symbol.Value);
+    appendU64(SymbolContents, Symbol.Size);
+  }
+  Sections.push_back(OutputSection{.Name = ".symtab",
+                                   .NameOffset = 0,
+                                   .Type = SHTSymTab,
+                                   .Flags = 0,
+                                   .Alignment = 8,
+                                   .EntrySize = 24,
+                                   .Link = StrTabIndex,
+                                   .Info = FirstGlobal,
+                                   .Contents = std::move(SymbolContents),
+                                   .AddressSize = 0,
+                                   .FileOffset = 0,
+                                   .Input = nullptr,
+                                   .RelocationTarget = std::nullopt,
+                                   .GroupSignature = {}});
+  Sections.push_back(OutputSection{.Name = ".strtab",
+                                   .NameOffset = 0,
+                                   .Type = SHTStrTab,
+                                   .Flags = 0,
+                                   .Alignment = 1,
+                                   .EntrySize = 0,
+                                   .Link = 0,
+                                   .Info = 0,
+                                   .Contents = SymbolNames.bytes(),
+                                   .AddressSize = 0,
+                                   .FileOffset = 0,
+                                   .Input = nullptr,
+                                   .RelocationTarget = std::nullopt,
+                                   .GroupSignature = {}});
+
+  StringTable SectionNames;
+  for (OutputSection &Section : Sections) {
+    auto Name = SectionNames.add(Section.Name);
+    if (!Name)
+      return std::unexpected(Name.error());
+    Section.NameOffset = *Name;
+  }
+  const std::uint32_t ShStrTabIndex = static_cast<std::uint32_t>(Sections.size());
+  auto ShStrName = SectionNames.add(".shstrtab");
+  if (!ShStrName)
+    return std::unexpected(ShStrName.error());
+  Sections.push_back(OutputSection{.Name = ".shstrtab",
+                                   .NameOffset = *ShStrName,
+                                   .Type = SHTStrTab,
+                                   .Flags = 0,
+                                   .Alignment = 1,
+                                   .EntrySize = 0,
+                                   .Link = 0,
+                                   .Info = 0,
+                                   .Contents = SectionNames.bytes(),
+                                   .AddressSize = 0,
+                                   .FileOffset = 0,
+                                   .Input = nullptr,
+                                   .RelocationTarget = std::nullopt,
+                                   .GroupSignature = {}});
+
+  if (Sections.size() >= SHNLoReserve) {
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "ELF extended section numbering is not implemented");
+  }
+
+  std::uint64_t FileOffset = 64;
+  for (std::size_t Index = 1; Index < Sections.size(); ++Index) {
+    OutputSection &Section = Sections[Index];
+    auto Aligned = alignTo(FileOffset, Section.Alignment);
+    if (!Aligned)
+      return std::unexpected(Aligned.error());
+    Section.FileOffset = *Aligned;
+    if (Section.Type == SHTNoBits)
+      continue;
+    auto End = checkedAdd(*Aligned, Section.Contents.size(), "ELF section file range overflows");
+    if (!End)
+      return std::unexpected(End.error());
+    FileOffset = *End;
+  }
+  auto SectionHeaderOffset = alignTo(FileOffset, 8);
+  if (!SectionHeaderOffset)
+    return std::unexpected(SectionHeaderOffset.error());
+  if (Sections.size() > std::numeric_limits<std::uint64_t>::max() / 64U) {
+    return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                          "ELF section header table exceeds the host limit");
+  }
+  auto End = checkedAdd(*SectionHeaderOffset, static_cast<std::uint64_t>(Sections.size()) * 64U,
+                        "ELF section header table overflows");
+  if (!End || *End > std::numeric_limits<std::size_t>::max()) {
+    return makeUnexpected(ErrorCode::ObjectWritingFailed, "ELF output exceeds the host limit");
+  }
+
+  std::vector<std::uint8_t> Output(64, 0);
+  Output[0] = 0x7f;
+  Output[1] = 'E';
+  Output[2] = 'L';
+  Output[3] = 'F';
+  Output[4] = 2;
+  Output[5] = 1;
+  Output[6] = 1;
+  Output[7] = Target.OSABI;
+  Output[8] = Target.ABIVersion;
+  Output[16] = 1;
+  Output[18] = static_cast<std::uint8_t>(Target.Machine);
+  Output[19] = static_cast<std::uint8_t>(Target.Machine >> 8U);
+  Output[20] = 1;
+  writeU64(Output, 40, *SectionHeaderOffset);
+  Output[48] = static_cast<std::uint8_t>(Target.Flags | Object.Flags);
+  Output[49] = static_cast<std::uint8_t>((Target.Flags | Object.Flags) >> 8U);
+  Output[50] = static_cast<std::uint8_t>((Target.Flags | Object.Flags) >> 16U);
+  Output[51] = static_cast<std::uint8_t>((Target.Flags | Object.Flags) >> 24U);
+  Output[52] = 64;
+  Output[58] = 64;
+  Output[60] = static_cast<std::uint8_t>(Sections.size());
+  Output[61] = static_cast<std::uint8_t>(Sections.size() >> 8U);
+  Output[62] = static_cast<std::uint8_t>(ShStrTabIndex);
+  Output[63] = static_cast<std::uint8_t>(ShStrTabIndex >> 8U);
+
+  for (std::size_t Index = 1; Index < Sections.size(); ++Index) {
+    if (Sections[Index].Type == SHTNoBits)
+      continue;
+    auto Appended = appendAtOffset(Output, Sections[Index].FileOffset, Sections[Index].Contents);
+    if (!Appended)
+      return std::unexpected(Appended.error());
+  }
+  if (Output.size() < *SectionHeaderOffset)
+    Output.resize(static_cast<std::size_t>(*SectionHeaderOffset));
+  for (const OutputSection &Section : Sections) {
+    appendU32(Output, Section.NameOffset);
+    appendU32(Output, Section.Type);
+    appendU64(Output, Section.Flags);
+    appendU64(Output, 0);
+    appendU64(Output, Section.FileOffset);
+    appendU64(Output, Section.Type == SHTNoBits ? Section.AddressSize : Section.Contents.size());
+    appendU32(Output, Section.Link);
+    appendU32(Output, Section.Info);
+    appendU64(Output, Section.Alignment);
+    appendU64(Output, Section.EntrySize);
+  }
+  return Output;
+}
+
+} // namespace rcc::mc
diff --git a/backend/lib/MC/MCAsmBackend.cpp b/backend/lib/MC/MCAsmBackend.cpp
new file mode 100644
index 0000000..bc350b7
--- /dev/null
+++ b/backend/lib/MC/MCAsmBackend.cpp
@@ -0,0 +1,25 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/MC/MCAsmBackend.h"
+
+namespace rcc::mc {
+
+Expected<std::vector<MCFixupRelocation>>
+MCAsmBackend::relocationsForFixup(const MCFixup &Fixup, const MCValue &Value) const {
+  if (!Value.AddSymbol || Value.SubtractSymbol) {
+    return makeUnexpected(ErrorCode::RelocationFailed,
+                          "MC backend cannot represent this expression as one relocation");
+  }
+  auto Type = relocationType(Fixup, Value);
+  if (!Type)
+    return std::unexpected(Type.error());
+  return std::vector<MCFixupRelocation>{
+      {.Type = *Type, .Symbol = Value.AddSymbol, .Addend = Value.Addend}};
+}
+
+Expected<MCInst> MCAsmBackend::relaxInstruction(const MCInst &) const {
+  return makeUnexpected(ErrorCode::InstructionEncodingFailed,
+                        "target does not support MC instruction relaxation");
+}
+
+} // namespace rcc::mc
diff --git a/backend/lib/MC/MCAssembler.cpp b/backend/lib/MC/MCAssembler.cpp
new file mode 100644
index 0000000..0f92edb
--- /dev/null
+++ b/backend/lib/MC/MCAssembler.cpp
@@ -0,0 +1,849 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/MC/MCAssembler.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <limits>
+#include <optional>
+#include <utility>
+
+namespace rcc::mc {
+namespace {
+
+[[nodiscard]] bool isPowerOfTwo(std::uint64_t Value) noexcept {
+  return Value != 0 && (Value & (Value - 1U)) == 0;
+}
+
+[[nodiscard]] Expected<std::uint64_t> checkedAdd(std::uint64_t Left, std::uint64_t Right,
+                                                 std::string_view Message) {
+  std::uint64_t Result = 0;
+  if (__builtin_add_overflow(Left, Right, &Result))
+    return makeUnexpected(ErrorCode::ObjectWritingFailed, std::string(Message));
+  return Result;
+}
+
+[[nodiscard]] Expected<std::int64_t> checkedAdd(std::int64_t Left, std::int64_t Right,
+                                                std::string_view Message) {
+  std::int64_t Result = 0;
+  if (__builtin_add_overflow(Left, Right, &Result))
+    return makeUnexpected(ErrorCode::RelocationFailed, std::string(Message));
+  return Result;
+}
+
+[[nodiscard]] Expected<std::int64_t> checkedSubtract(std::int64_t Left, std::int64_t Right,
+                                                     std::string_view Message) {
+  std::int64_t Result = 0;
+  if (__builtin_sub_overflow(Left, Right, &Result))
+    return makeUnexpected(ErrorCode::RelocationFailed, std::string(Message));
+  return Result;
+}
+
+[[nodiscard]] Expected<std::int64_t> signedOffset(std::uint64_t Value, std::string_view Message) {
+  if (Value > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max()))
+    return makeUnexpected(ErrorCode::RelocationFailed, std::string(Message));
+  return static_cast<std::int64_t>(Value);
+}
+
+[[nodiscard]] Expected<std::uint64_t> alignmentPadding(std::uint64_t Offset,
+                                                       std::uint64_t Alignment) {
+  if (!isPowerOfTwo(Alignment))
+    return makeUnexpected(ErrorCode::InvalidArgument, "MC alignment is not a power of two");
+  const std::uint64_t Mask = Alignment - 1U;
+  auto Adjusted = checkedAdd(Offset, Mask, "MC section alignment overflows");
+  if (!Adjusted)
+    return std::unexpected(Adjusted.error());
+  return (*Adjusted & ~Mask) - Offset;
+}
+
+[[nodiscard]] MCFixupKind dataFixupKind(std::uint8_t Size) noexcept {
+  switch (Size) {
+  case 1:
+    return fixup_kind::Data1;
+  case 2:
+    return fixup_kind::Data2;
+  case 4:
+    return fixup_kind::Data4;
+  case 8:
+    return fixup_kind::Data8;
+  default:
+    return fixup_kind::None;
+  }
+}
+
+void appendLittleEndian(std::vector<std::uint8_t> &Bytes, std::uint64_t Value, std::uint8_t Size) {
+  for (std::uint8_t Index = 0; Index < Size; ++Index)
+    Bytes.push_back(static_cast<std::uint8_t>(Value >> (Index * 8U)));
+}
+
+[[nodiscard]] bool isNoBits(const MCSection &Section) noexcept {
+  return Section.description().Kind == MCSectionKind::BSS ||
+         Section.description().Kind == MCSectionKind::TLSBSS;
+}
+
+} // namespace
+
+Expected<std::size_t> MCAssembler::currentSectionIndex() const {
+  if (WasAssembled)
+    return makeUnexpected(ErrorCode::ObjectWritingFailed, "MC assembler is already finalized");
+  if (!CurrentSection)
+    return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                          "object emission requires an active MC section");
+  return *CurrentSection;
+}
+
+MCAssembler::SymbolData &MCAssembler::getOrCreateSymbol(MCSymbolRef Symbol) {
+  const auto Position = SymbolIndices.find(Symbol.get());
+  if (Position != SymbolIndices.end())
+    return Symbols[Position->second];
+  const std::size_t Index = Symbols.size();
+  Symbols.push_back(SymbolData{.Symbol = std::move(Symbol),
+                               .Binding = MCObjectSymbolBinding::Local,
+                               .BindingWasSet = false,
+                               .Type = MCObjectSymbolType::None,
+                               .Visibility = MCObjectSymbolVisibility::Default,
+                               .SectionIndex = std::nullopt,
+                               .FragmentIndex = 0,
+                               .Size = {},
+                               .CommonSize = 0,
+                               .CommonAlignment = 0});
+  SymbolIndices.emplace(Symbols.back().Symbol.get(), Index);
+  return Symbols.back();
+}
+
+std::optional<std::uint64_t> MCAssembler::symbolOffset(const SymbolData &Symbol) const {
+  if (!Symbol.SectionIndex || *Symbol.SectionIndex >= Sections.size())
+    return std::nullopt;
+  const SectionData &Section = Sections[*Symbol.SectionIndex];
+  if (Symbol.FragmentIndex > Section.Fragments.size())
+    return std::nullopt;
+  if (Symbol.FragmentIndex == Section.Fragments.size())
+    return Section.AddressSize;
+  return Section.Fragments[Symbol.FragmentIndex].Offset;
+}
+
+Expected<void> MCAssembler::switchSection(MCSectionRef Section) {
+  if (WasAssembled)
+    return makeUnexpected(ErrorCode::ObjectWritingFailed, "MC assembler is already finalized");
+  if (!Section)
+    return makeUnexpected(ErrorCode::InvalidArgument, "cannot switch to a null MC section");
+  auto Verification = Section->description().verify();
+  if (!Verification)
+    return std::unexpected(Verification.error());
+  const auto Existing = SectionIndices.find(Section.get());
+  if (Existing != SectionIndices.end()) {
+    CurrentSection = Existing->second;
+    return {};
+  }
+  const std::size_t Index = Sections.size();
+  const std::uint64_t Alignment = Section->description().Alignment;
+  Sections.push_back(SectionData{
+      .Section = std::move(Section), .Fragments = {}, .AddressSize = 0, .Alignment = Alignment});
+  SectionIndices.emplace(Sections.back().Section.get(), Index);
+  CurrentSection = Index;
+  return {};
+}
+
+Expected<void> MCAssembler::emitLabel(MCSymbolRef Symbol) {
+  auto SectionIndex = currentSectionIndex();
+  if (!SectionIndex)
+    return std::unexpected(SectionIndex.error());
+  if (!Symbol)
+    return makeUnexpected(ErrorCode::InvalidArgument, "cannot emit a null MC symbol label");
+  SymbolData &Data = getOrCreateSymbol(std::move(Symbol));
+  if (Data.SectionIndex || Data.CommonSize != 0) {
+    return makeUnexpected(ErrorCode::ObjectWritingFailed, "MC symbol is defined more than once");
+  }
+  Data.SectionIndex = *SectionIndex;
+  Data.FragmentIndex = Sections[*SectionIndex].Fragments.size();
+  return {};
+}
+
+Expected<void> MCAssembler::emitInstruction(const MCInst &Instruction) {
+  auto SectionIndex = currentSectionIndex();
+  if (!SectionIndex)
+    return std::unexpected(SectionIndex.error());
+  if (!Instruction.opcode().isValid())
+    return makeUnexpected(ErrorCode::InvalidArgument, "cannot encode an invalid MC opcode");
+  Sections[*SectionIndex].Fragments.push_back(
+      Fragment{.Payload = InstructionFragment{.Instruction = Instruction},
+               .Offset = 0,
+               .Size = 0,
+               .EncodedBytes = {},
+               .Fixups = {}});
+  return {};
+}
+
+Expected<void> MCAssembler::emitValue(MCExprRef Value, std::uint8_t Size) {
+  auto SectionIndex = currentSectionIndex();
+  if (!SectionIndex)
+    return std::unexpected(SectionIndex.error());
+  const MCFixupKind Kind = dataFixupKind(Size);
+  if (!Value || Kind == fixup_kind::None) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "MC value requires an expression and a supported size");
+  }
+  DataFragment Data;
+  if (const auto Absolute = Value->evaluateAbsolute()) {
+    appendLittleEndian(Data.Bytes, static_cast<std::uint64_t>(*Absolute), Size);
+  } else {
+    Data.Bytes.resize(Size);
+    Data.Fixups.push_back(MCFixup{.Offset = 0, .Value = std::move(Value), .Kind = Kind});
+  }
+  Sections[*SectionIndex].Fragments.push_back(Fragment{
+      .Payload = std::move(Data), .Offset = 0, .Size = 0, .EncodedBytes = {}, .Fixups = {}});
+  return {};
+}
+
+Expected<void> MCAssembler::emitBytes(std::span<const std::uint8_t> Bytes) {
+  auto SectionIndex = currentSectionIndex();
+  if (!SectionIndex)
+    return std::unexpected(SectionIndex.error());
+  if (Bytes.empty())
+    return {};
+  Sections[*SectionIndex].Fragments.push_back(
+      Fragment{.Payload = DataFragment{.Bytes = {Bytes.begin(), Bytes.end()}, .Fixups = {}},
+               .Offset = 0,
+               .Size = 0,
+               .EncodedBytes = {},
+               .Fixups = {}});
+  return {};
+}
+
+Expected<void> MCAssembler::emitZeroFill(std::uint64_t Size) {
+  auto SectionIndex = currentSectionIndex();
+  if (!SectionIndex)
+    return std::unexpected(SectionIndex.error());
+  if (Size == 0)
+    return {};
+  Sections[*SectionIndex].Fragments.push_back(Fragment{.Payload = ZeroFillFragment{.Size = Size},
+                                                       .Offset = 0,
+                                                       .Size = 0,
+                                                       .EncodedBytes = {},
+                                                       .Fixups = {}});
+  return {};
+}
+
+Expected<void> MCAssembler::emitAlignment(std::uint64_t Alignment, std::uint8_t Fill,
+                                          std::uint64_t MaximumBytes) {
+  auto SectionIndex = currentSectionIndex();
+  if (!SectionIndex)
+    return std::unexpected(SectionIndex.error());
+  if (!isPowerOfTwo(Alignment))
+    return makeUnexpected(ErrorCode::InvalidArgument, "MC alignment is not a power of two");
+  Sections[*SectionIndex].Fragments.push_back(Fragment{
+      .Payload =
+          AlignmentFragment{.Alignment = Alignment, .Fill = Fill, .MaximumBytes = MaximumBytes},
+      .Offset = 0,
+      .Size = 0,
+      .EncodedBytes = {},
+      .Fixups = {}});
+  return {};
+}
+
+Expected<void> MCAssembler::emitSymbolAttribute(MCSymbolRef Symbol, MCSymbolAttribute Attribute) {
+  if (WasAssembled)
+    return makeUnexpected(ErrorCode::ObjectWritingFailed, "MC assembler is already finalized");
+  if (!Symbol)
+    return makeUnexpected(ErrorCode::InvalidArgument, "MC symbol attribute has no symbol");
+  SymbolData &Data = getOrCreateSymbol(std::move(Symbol));
+  switch (Attribute) {
+  case MCSymbolAttribute::Global:
+    Data.Binding = MCObjectSymbolBinding::Global;
+    Data.BindingWasSet = true;
+    break;
+  case MCSymbolAttribute::Weak:
+    Data.Binding = MCObjectSymbolBinding::Weak;
+    Data.BindingWasSet = true;
+    break;
+  case MCSymbolAttribute::Local:
+    Data.Binding = MCObjectSymbolBinding::Local;
+    Data.BindingWasSet = true;
+    break;
+  case MCSymbolAttribute::Hidden:
+    Data.Visibility = MCObjectSymbolVisibility::Hidden;
+    break;
+  case MCSymbolAttribute::Protected:
+    Data.Visibility = MCObjectSymbolVisibility::Protected;
+    break;
+  case MCSymbolAttribute::Function:
+    Data.Type = MCObjectSymbolType::Function;
+    break;
+  case MCSymbolAttribute::Object:
+    Data.Type = MCObjectSymbolType::Object;
+    break;
+  case MCSymbolAttribute::TLSObject:
+    Data.Type = MCObjectSymbolType::TLSObject;
+    break;
+  }
+  return {};
+}
+
+Expected<void> MCAssembler::emitSymbolSize(MCSymbolRef Symbol, MCExprRef Size) {
+  if (WasAssembled)
+    return makeUnexpected(ErrorCode::ObjectWritingFailed, "MC assembler is already finalized");
+  if (!Symbol || !Size)
+    return makeUnexpected(ErrorCode::InvalidArgument, "MC symbol size is incomplete");
+  SymbolData &Data = getOrCreateSymbol(std::move(Symbol));
+  if (Data.Size)
+    return makeUnexpected(ErrorCode::ObjectWritingFailed, "MC symbol size is defined twice");
+  Data.Size = std::move(Size);
+  return {};
+}
+
+Expected<void> MCAssembler::emitCommonSymbol(MCSymbolRef Symbol, std::uint64_t Size,
+                                             std::uint64_t Alignment) {
+  if (WasAssembled)
+    return makeUnexpected(ErrorCode::ObjectWritingFailed, "MC assembler is already finalized");
+  if (!Symbol || Size == 0 || !isPowerOfTwo(Alignment)) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "common symbol requires a size and power-of-two alignment");
+  }
+  SymbolData &Data = getOrCreateSymbol(std::move(Symbol));
+  if (Data.SectionIndex || Data.CommonSize != 0)
+    return makeUnexpected(ErrorCode::ObjectWritingFailed, "common symbol is defined twice");
+  Data.CommonSize = Size;
+  Data.CommonAlignment = Alignment;
+  if (Data.Binding == MCObjectSymbolBinding::Local)
+    Data.Binding = MCObjectSymbolBinding::Global;
+  if (Data.Type == MCObjectSymbolType::None)
+    Data.Type = MCObjectSymbolType::Object;
+  return {};
+}
+
+Expected<void> MCAssembler::configureDwarfFrame(MCSectionRef Section, MCDwarfFrameInfo Info) {
+  if (WasAssembled || !CFIProcedures.empty() || DwarfFrameInfo) {
+    return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                          "DWARF frame emission is already configured or active");
+  }
+  if (!Section || Section->description().Kind != MCSectionKind::EHFrame) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "DWARF frame emission requires an EHFrame section");
+  }
+  auto SectionVerification = Section->description().verify();
+  if (!SectionVerification)
+    return std::unexpected(SectionVerification.error());
+  auto InfoVerification = Info.verify();
+  if (!InfoVerification)
+    return std::unexpected(InfoVerification.error());
+  EHFrameSection = std::move(Section);
+  DwarfFrameInfo = Info;
+  return {};
+}
+
+Expected<void> MCAssembler::emitCFI(const MCCFIInstruction &Instruction) {
+  if (WasAssembled)
+    return makeUnexpected(ErrorCode::ObjectWritingFailed, "MC assembler is already finalized");
+  auto Verification = Instruction.verify();
+  if (!Verification)
+    return std::unexpected(Verification.error());
+  auto SectionIndex = currentSectionIndex();
+  if (!SectionIndex)
+    return std::unexpected(SectionIndex.error());
+  const std::size_t FragmentIndex = Sections[*SectionIndex].Fragments.size();
+
+  if (Instruction.Operation == MCCFIOperation::StartProc) {
+    if (ActiveCFIProcedure) {
+      return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                            "nested CFI procedures are not permitted");
+    }
+    MCSymbolRef Function;
+    for (auto Position = Symbols.rbegin(); Position != Symbols.rend(); ++Position) {
+      if (Position->SectionIndex == SectionIndex && Position->FragmentIndex == FragmentIndex &&
+          Position->Symbol && Position->Symbol->kind() == MCSymbolKind::Function) {
+        Function = Position->Symbol;
+        break;
+      }
+    }
+    if (!Function) {
+      return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                            "CFI procedure does not begin at a function symbol");
+    }
+    CFIProcedures.push_back(CFIProcedure{.Function = std::move(Function),
+                                         .SectionIndex = *SectionIndex,
+                                         .BeginFragmentIndex = FragmentIndex,
+                                         .EndFragmentIndex = 0,
+                                         .Events = {},
+                                         .IsClosed = false});
+    ActiveCFIProcedure = CFIProcedures.size() - 1U;
+    return {};
+  }
+
+  if (!ActiveCFIProcedure) {
+    return makeUnexpected(ErrorCode::ObjectWritingFailed, "CFI event appears outside a procedure");
+  }
+  CFIProcedure &Procedure = CFIProcedures[*ActiveCFIProcedure];
+  if (Procedure.SectionIndex != *SectionIndex) {
+    return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                          "CFI procedure changes sections before it ends");
+  }
+  if (Instruction.Operation == MCCFIOperation::EndProc) {
+    Procedure.EndFragmentIndex = FragmentIndex;
+    Procedure.IsClosed = true;
+    ActiveCFIProcedure.reset();
+    return {};
+  }
+  if (Instruction.Operation == MCCFIOperation::Label) {
+    return emitLabel(Instruction.Symbol);
+  }
+  Procedure.Events.push_back(CFIEvent{.Instruction = Instruction, .FragmentIndex = FragmentIndex});
+  return {};
+}
+
+Expected<void> MCAssembler::encodeFragments() {
+  for (SectionData &Section : Sections) {
+    for (Fragment &Fragment : Section.Fragments) {
+      Fragment.EncodedBytes.clear();
+      Fragment.Fixups.clear();
+      Fragment.Size = 0;
+      if (auto *Instruction = std::get_if<InstructionFragment>(&Fragment.Payload)) {
+        auto Encoded = Emitter->encodeInstruction(Instruction->Instruction);
+        if (!Encoded)
+          return std::unexpected(Encoded.error());
+        Fragment.EncodedBytes = std::move(Encoded->Bytes);
+        Fragment.Fixups = std::move(Encoded->Fixups);
+      } else if (auto *Data = std::get_if<DataFragment>(&Fragment.Payload)) {
+        Fragment.EncodedBytes = Data->Bytes;
+        Fragment.Fixups = Data->Fixups;
+      }
+      Fragment.Size = Fragment.EncodedBytes.size();
+      for (const MCFixup &Fixup : Fragment.Fixups) {
+        auto Verification = Fixup.verify();
+        if (!Verification)
+          return std::unexpected(Verification.error());
+        auto KindInfo = Backend->fixupKindInfo(Fixup.Kind);
+        if (!KindInfo)
+          return std::unexpected(KindInfo.error());
+        if (Fixup.PCRelative != KindInfo->PCRelative) {
+          return makeUnexpected(ErrorCode::InstructionEncodingFailed,
+                                "MC fixup PC-relative state disagrees with its kind");
+        }
+        if (Fixup.Offset > Fragment.EncodedBytes.size() ||
+            KindInfo->StorageSize >
+                Fragment.EncodedBytes.size() - static_cast<std::size_t>(Fixup.Offset)) {
+          return makeUnexpected(ErrorCode::InstructionEncodingFailed,
+                                "MC fixup exceeds its encoded fragment");
+        }
+      }
+    }
+  }
+  return {};
+}
+
+Expected<bool> MCAssembler::layoutAndRelax() {
+  std::size_t RelaxableInstructionCount = 0;
+  for (const SectionData &Section : Sections) {
+    for (const Fragment &Fragment : Section.Fragments) {
+      const auto *Instruction = std::get_if<InstructionFragment>(&Fragment.Payload);
+      if (Instruction != nullptr && Backend->mayNeedRelaxation(Instruction->Instruction)) {
+        if (RelaxableInstructionCount == std::numeric_limits<std::size_t>::max()) {
+          return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                                "MC relaxation budget exceeds the host limit");
+        }
+        ++RelaxableInstructionCount;
+      }
+    }
+  }
+  const std::size_t MaximumIterations = RelaxableInstructionCount + 1U;
+  for (std::size_t Iteration = 0; Iteration < MaximumIterations; ++Iteration) {
+    auto Encoded = encodeFragments();
+    if (!Encoded)
+      return std::unexpected(Encoded.error());
+
+    for (SectionData &Section : Sections) {
+      std::uint64_t Offset = 0;
+      Section.Alignment = Section.Section->description().Alignment;
+      const bool NoBits = isNoBits(*Section.Section);
+      for (Fragment &Fragment : Section.Fragments) {
+        Fragment.Offset = Offset;
+        std::uint64_t Size = Fragment.Size;
+        if (const auto *Alignment = std::get_if<AlignmentFragment>(&Fragment.Payload)) {
+          auto Padding = alignmentPadding(Offset, Alignment->Alignment);
+          if (!Padding)
+            return std::unexpected(Padding.error());
+          Size = Alignment->MaximumBytes != 0 && *Padding > Alignment->MaximumBytes ? 0 : *Padding;
+          Section.Alignment = std::max(Section.Alignment, Alignment->Alignment);
+          if (NoBits)
+            Fragment.EncodedBytes.clear();
+          else
+            Fragment.EncodedBytes.assign(static_cast<std::size_t>(Size), Alignment->Fill);
+        } else if (const auto *Zero = std::get_if<ZeroFillFragment>(&Fragment.Payload)) {
+          Size = Zero->Size;
+          if (!NoBits && Size > std::numeric_limits<std::size_t>::max()) {
+            return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                                  "zero-fill fragment exceeds the host size limit");
+          }
+          if (NoBits)
+            Fragment.EncodedBytes.clear();
+          else
+            Fragment.EncodedBytes.assign(static_cast<std::size_t>(Size), 0);
+        } else if (NoBits) {
+          if (std::holds_alternative<InstructionFragment>(Fragment.Payload) ||
+              !Fragment.Fixups.empty() ||
+              std::ranges::any_of(Fragment.EncodedBytes,
+                                  [](std::uint8_t Byte) { return Byte != 0; })) {
+            return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                                  "MC NOBITS section contains initialized data");
+          }
+          Fragment.EncodedBytes.clear();
+        }
+        Fragment.Size = Size;
+        auto End = checkedAdd(Offset, Size, "MC section size overflows");
+        if (!End)
+          return std::unexpected(End.error());
+        Offset = *End;
+      }
+      Section.AddressSize = Offset;
+    }
+
+    bool Changed = false;
+    for (SectionData &Section : Sections) {
+      for (Fragment &Fragment : Section.Fragments) {
+        auto *Instruction = std::get_if<InstructionFragment>(&Fragment.Payload);
+        if (Instruction == nullptr || !Backend->mayNeedRelaxation(Instruction->Instruction))
+          continue;
+        for (const MCFixup &Fixup : Fragment.Fixups) {
+          auto Value = evaluateAsRelocatable(*Fixup.Value);
+          if (!Value)
+            return std::unexpected(Value.error());
+          if (!Value->AddSymbol || Value->SubtractSymbol || Value->TargetKind != 0)
+            continue;
+          const auto SymbolPosition = SymbolIndices.find(Value->AddSymbol.get());
+          if (SymbolPosition == SymbolIndices.end())
+            continue;
+          const SymbolData &Target = Symbols[SymbolPosition->second];
+          if (!Target.SectionIndex || *Target.SectionIndex != SectionIndices[Section.Section.get()])
+            continue;
+          const auto TargetOffset = symbolOffset(Target);
+          if (!TargetOffset)
+            continue;
+          auto PlaceOffset = checkedAdd(Fragment.Offset, Fixup.Offset, "MC fixup place overflows");
+          if (!PlaceOffset)
+            return std::unexpected(PlaceOffset.error());
+          auto Place = signedOffset(*PlaceOffset, "MC fixup place exceeds the signed range");
+          auto TargetPosition =
+              signedOffset(*TargetOffset, "MC relaxation target exceeds the signed range");
+          if (!Place)
+            return std::unexpected(Place.error());
+          if (!TargetPosition)
+            return std::unexpected(TargetPosition.error());
+          auto WithAddend =
+              checkedAdd(*TargetPosition, Value->Addend, "MC relaxation target addend overflows");
+          if (!WithAddend)
+            return std::unexpected(WithAddend.error());
+          auto Displacement =
+              checkedSubtract(*WithAddend, *Place, "MC relaxation displacement overflows");
+          if (!Displacement)
+            return std::unexpected(Displacement.error());
+          auto NeedsRelaxation = Backend->fixupNeedsRelaxation(Fixup, *Displacement);
+          if (!NeedsRelaxation)
+            return std::unexpected(NeedsRelaxation.error());
+          if (!*NeedsRelaxation)
+            continue;
+          auto Relaxed = Backend->relaxInstruction(Instruction->Instruction);
+          if (!Relaxed)
+            return std::unexpected(Relaxed.error());
+          Instruction->Instruction = std::move(*Relaxed);
+          Changed = true;
+          break;
+        }
+      }
+    }
+    if (!Changed)
+      return false;
+  }
+  return makeUnexpected(ErrorCode::InternalError, "MC relaxation did not reach a fixed point");
+}
+
+Expected<MCAssembledObject> MCAssembler::finalizeObject() {
+  for (SectionData &Section : Sections) {
+    for (Fragment &Fragment : Section.Fragments) {
+      for (const MCFixup &Fixup : Fragment.Fixups) {
+        auto Value = evaluateAsRelocatable(*Fixup.Value);
+        if (!Value)
+          return std::unexpected(Value.error());
+        if (Value->AddSymbol)
+          static_cast<void>(getOrCreateSymbol(Value->AddSymbol));
+        if (Value->SubtractSymbol)
+          static_cast<void>(getOrCreateSymbol(Value->SubtractSymbol));
+      }
+    }
+  }
+
+  MCAssembledObject Result;
+  Result.Flags = Backend->objectFlags();
+  Result.Sections.reserve(Sections.size());
+  for (const SectionData &Section : Sections) {
+    MCObjectSection Output{.Section = Section.Section,
+                           .Contents = {},
+                           .AddressSize = Section.AddressSize,
+                           .Alignment = Section.Alignment,
+                           .Relocations = {}};
+    if (!isNoBits(*Section.Section) &&
+        Section.AddressSize > std::numeric_limits<std::size_t>::max()) {
+      return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                            "MC section exceeds the host size limit");
+    }
+    if (!isNoBits(*Section.Section)) {
+      Output.Contents.reserve(static_cast<std::size_t>(Section.AddressSize));
+      for (const Fragment &Fragment : Section.Fragments)
+        Output.Contents.insert(Output.Contents.end(), Fragment.EncodedBytes.begin(),
+                               Fragment.EncodedBytes.end());
+    }
+    Result.Sections.push_back(std::move(Output));
+  }
+
+  Result.Symbols.reserve(Symbols.size());
+  for (const SymbolData &Data : Symbols) {
+    if (!Data.SectionIndex && Data.CommonSize == 0 && Data.Symbol->isTemporary()) {
+      return makeUnexpected(ErrorCode::RelocationFailed,
+                            "temporary MC symbol is referenced but not defined");
+    }
+    const MCObjectSymbolBinding Binding =
+        !Data.BindingWasSet && !Data.SectionIndex && Data.CommonSize == 0
+            ? MCObjectSymbolBinding::Global
+            : Data.Binding;
+    MCObjectSymbol Output{.Symbol = Data.Symbol,
+                          .Binding = Binding,
+                          .Type = Data.Type,
+                          .Visibility = Data.Visibility,
+                          .SectionIndex = Data.SectionIndex,
+                          .CommonAlignment = Data.CommonAlignment};
+    if (Data.CommonSize != 0) {
+      Output.Size = Data.CommonSize;
+      Output.Value = Data.CommonAlignment;
+    } else if (const auto Offset = symbolOffset(Data)) {
+      Output.Value = *Offset;
+    }
+    if (Data.Size) {
+      auto SizeValue = evaluateAsRelocatable(*Data.Size);
+      if (!SizeValue)
+        return std::unexpected(SizeValue.error());
+      if (SizeValue->TargetKind != 0) {
+        return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                              "symbol size cannot use a target expression");
+      }
+      if (SizeValue->AddSymbol && SizeValue->SubtractSymbol) {
+        const auto AddPosition = SymbolIndices.find(SizeValue->AddSymbol.get());
+        const auto SubtractPosition = SymbolIndices.find(SizeValue->SubtractSymbol.get());
+        if (AddPosition == SymbolIndices.end() || SubtractPosition == SymbolIndices.end()) {
+          return makeUnexpected(ErrorCode::ObjectWritingFailed, "symbol size is unresolved");
+        }
+        const SymbolData &Add = Symbols[AddPosition->second];
+        const SymbolData &Subtract = Symbols[SubtractPosition->second];
+        if (!Add.SectionIndex || !Subtract.SectionIndex ||
+            Add.SectionIndex != Subtract.SectionIndex) {
+          return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                                "symbol size difference crosses sections");
+        }
+      }
+      std::int64_t Resolved = SizeValue->Addend;
+      const auto Resolve = [&](const MCSymbolRef &Symbol) -> Expected<std::int64_t> {
+        const auto Position = SymbolIndices.find(Symbol.get());
+        if (Position == SymbolIndices.end())
+          return makeUnexpected(ErrorCode::ObjectWritingFailed, "symbol size is unresolved");
+        const auto Offset = symbolOffset(Symbols[Position->second]);
+        if (!Offset)
+          return makeUnexpected(ErrorCode::ObjectWritingFailed, "symbol size is unresolved");
+        return signedOffset(*Offset, "symbol size offset exceeds the signed range");
+      };
+      if (SizeValue->AddSymbol) {
+        auto Offset = Resolve(SizeValue->AddSymbol);
+        if (!Offset)
+          return std::unexpected(Offset.error());
+        auto Updated = checkedAdd(Resolved, *Offset, "symbol size addition overflows");
+        if (!Updated)
+          return std::unexpected(Updated.error());
+        Resolved = *Updated;
+      }
+      if (SizeValue->SubtractSymbol) {
+        auto Offset = Resolve(SizeValue->SubtractSymbol);
+        if (!Offset)
+          return std::unexpected(Offset.error());
+        auto Updated = checkedSubtract(Resolved, *Offset, "symbol size subtraction overflows");
+        if (!Updated)
+          return std::unexpected(Updated.error());
+        Resolved = *Updated;
+      }
+      if (Resolved < 0)
+        return makeUnexpected(ErrorCode::ObjectWritingFailed, "symbol size is negative");
+      Output.Size = static_cast<std::uint64_t>(Resolved);
+    }
+    if (Output.SectionIndex) {
+      const std::uint64_t SectionSize = Sections[*Output.SectionIndex].AddressSize;
+      if (Output.Value > SectionSize || Output.Size > SectionSize - Output.Value) {
+        return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                              "symbol range exceeds its defining section");
+      }
+    }
+    Result.Symbols.push_back(std::move(Output));
+  }
+
+  for (std::size_t SectionIndex = 0; SectionIndex < Sections.size(); ++SectionIndex) {
+    const SectionData &Section = Sections[SectionIndex];
+    MCObjectSection &Output = Result.Sections[SectionIndex];
+    for (const Fragment &Fragment : Section.Fragments) {
+      for (const MCFixup &Fixup : Fragment.Fixups) {
+        auto Value = evaluateAsRelocatable(*Fixup.Value);
+        if (!Value)
+          return std::unexpected(Value.error());
+        auto PlaceValue =
+            checkedAdd(Fragment.Offset, Fixup.Offset, "MC relocation offset overflows");
+        if (!PlaceValue)
+          return std::unexpected(PlaceValue.error());
+        const std::uint64_t Place = *PlaceValue;
+        bool Resolved = Value->isAbsolute();
+        std::int64_t FixedValue = Value->Addend;
+        const auto FindSymbol = [&](const MCSymbolRef &Symbol) -> const SymbolData * {
+          const auto Position = SymbolIndices.find(Symbol.get());
+          return Position == SymbolIndices.end() ? nullptr : &Symbols[Position->second];
+        };
+        const SymbolData *Add = Value->AddSymbol ? FindSymbol(Value->AddSymbol) : nullptr;
+        const SymbolData *Subtract =
+            Value->SubtractSymbol ? FindSymbol(Value->SubtractSymbol) : nullptr;
+        if (Value->TargetKind == 0 && Add != nullptr && Subtract != nullptr && Add->SectionIndex &&
+            Subtract->SectionIndex && Add->SectionIndex == Subtract->SectionIndex) {
+          const auto AddOffset = symbolOffset(*Add);
+          const auto SubtractOffset = symbolOffset(*Subtract);
+          if (AddOffset && SubtractOffset) {
+            auto SignedAdd = signedOffset(*AddOffset, "MC symbol offset exceeds the signed range");
+            auto SignedSubtract =
+                signedOffset(*SubtractOffset, "MC symbol offset exceeds the signed range");
+            if (!SignedAdd)
+              return std::unexpected(SignedAdd.error());
+            if (!SignedSubtract)
+              return std::unexpected(SignedSubtract.error());
+            auto Difference =
+                checkedSubtract(*SignedAdd, *SignedSubtract, "MC symbol difference overflows");
+            if (!Difference)
+              return std::unexpected(Difference.error());
+            auto Updated = checkedAdd(FixedValue, *Difference, "MC resolved fixup value overflows");
+            if (!Updated)
+              return std::unexpected(Updated.error());
+            FixedValue = *Updated;
+            Resolved = true;
+          }
+        } else if (Value->TargetKind == 0 && Fixup.PCRelative && Add != nullptr &&
+                   !Value->SubtractSymbol && Add->SectionIndex &&
+                   *Add->SectionIndex == SectionIndex) {
+          const auto AddOffset = symbolOffset(*Add);
+          if (AddOffset) {
+            auto SignedAdd = signedOffset(*AddOffset, "MC symbol offset exceeds the signed range");
+            auto SignedPlace = signedOffset(Place, "MC fixup place exceeds the signed range");
+            if (!SignedAdd)
+              return std::unexpected(SignedAdd.error());
+            if (!SignedPlace)
+              return std::unexpected(SignedPlace.error());
+            auto Difference =
+                checkedSubtract(*SignedAdd, *SignedPlace, "MC PC-relative displacement overflows");
+            if (!Difference)
+              return std::unexpected(Difference.error());
+            auto Updated = checkedAdd(FixedValue, *Difference, "MC resolved fixup value overflows");
+            if (!Updated)
+              return std::unexpected(Updated.error());
+            FixedValue = *Updated;
+            Resolved = true;
+          }
+        }
+
+        if (Resolved) {
+          auto Applied = Backend->applyFixup(Fixup.Kind, Output.Contents, Place, FixedValue);
+          if (!Applied)
+            return std::unexpected(Applied.error());
+          continue;
+        }
+        auto Relocations = Backend->relocationsForFixup(Fixup, *Value);
+        if (!Relocations)
+          return std::unexpected(Relocations.error());
+        for (const MCFixupRelocation &Relocation : *Relocations) {
+          if (Relocation.Type == 0 || !Relocation.Symbol) {
+            return makeUnexpected(ErrorCode::RelocationFailed,
+                                  "MC backend produced an invalid relocation");
+          }
+          Output.Relocations.push_back(MCObjectRelocation{.Offset = Place,
+                                                          .Type = Relocation.Type,
+                                                          .Symbol = Relocation.Symbol,
+                                                          .Addend = Relocation.Addend});
+        }
+      }
+    }
+  }
+  auto DwarfFrame = appendDwarfFrame(Result);
+  if (!DwarfFrame)
+    return std::unexpected(DwarfFrame.error());
+  return Result;
+}
+
+Expected<void> MCAssembler::appendDwarfFrame(MCAssembledObject &Object) const {
+  if (CFIProcedures.empty())
+    return {};
+  if (!DwarfFrameInfo || !EHFrameSection) {
+    return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                          "CFI was emitted without DWARF frame configuration");
+  }
+  if (ActiveCFIProcedure) {
+    return makeUnexpected(ErrorCode::ObjectWritingFailed, "CFI procedure was not terminated");
+  }
+
+  std::vector<MCDwarfFrameProcedure> Procedures;
+  Procedures.reserve(CFIProcedures.size());
+  for (const CFIProcedure &Procedure : CFIProcedures) {
+    if (!Procedure.IsClosed || Procedure.SectionIndex >= Sections.size()) {
+      return makeUnexpected(ErrorCode::ObjectWritingFailed, "CFI procedure is incomplete");
+    }
+    const SectionData &Section = Sections[Procedure.SectionIndex];
+    const auto FragmentOffset = [&Section](std::size_t Index) -> std::optional<std::uint64_t> {
+      if (Index > Section.Fragments.size())
+        return std::nullopt;
+      if (Index == Section.Fragments.size())
+        return Section.AddressSize;
+      return Section.Fragments[Index].Offset;
+    };
+    const auto Begin = FragmentOffset(Procedure.BeginFragmentIndex);
+    const auto End = FragmentOffset(Procedure.EndFragmentIndex);
+    if (!Begin || !End || *End < *Begin) {
+      return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                            "CFI procedure has an invalid address range");
+    }
+    MCDwarfFrameProcedure Output{
+        .Function = Procedure.Function, .AddressRange = *End - *Begin, .Instructions = {}};
+    Output.Instructions.reserve(Procedure.Events.size());
+    for (const CFIEvent &Event : Procedure.Events) {
+      const auto Offset = FragmentOffset(Event.FragmentIndex);
+      if (!Offset || *Offset < *Begin || *Offset > *End) {
+        return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                              "CFI event lies outside its procedure");
+      }
+      Output.Instructions.push_back(MCDwarfFrameInstruction{
+          .Instruction = Event.Instruction,
+          .Offset = *Offset - *Begin,
+      });
+    }
+    Procedures.push_back(std::move(Output));
+  }
+  auto Frame = emitDwarfEHFrame(EHFrameSection, Procedures, *DwarfFrameInfo, *Backend);
+  if (!Frame)
+    return std::unexpected(Frame.error());
+  Object.Sections.push_back(std::move(*Frame));
+  return {};
+}
+
+Expected<MCAssembledObject> MCAssembler::assemble() {
+  if (WasAssembled)
+    return makeUnexpected(ErrorCode::ObjectWritingFailed, "MC assembler was already finalized");
+  if (ActiveCFIProcedure) {
+    return makeUnexpected(ErrorCode::ObjectWritingFailed, "CFI procedure was not terminated");
+  }
+  MCAssembler Working = *this;
+  auto Relaxed = Working.layoutAndRelax();
+  if (!Relaxed)
+    return std::unexpected(Relaxed.error());
+  auto Result = Working.finalizeObject();
+  if (!Result)
+    return std::unexpected(Result.error());
+  WasAssembled = true;
+  return Result;
+}
+
+} // namespace rcc::mc
diff --git a/backend/lib/MC/MCDwarfFrameEmitter.cpp b/backend/lib/MC/MCDwarfFrameEmitter.cpp
new file mode 100644
index 0000000..581c8cb
--- /dev/null
+++ b/backend/lib/MC/MCDwarfFrameEmitter.cpp
@@ -0,0 +1,443 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/MC/MCDwarfFrameEmitter.h"
+
+#include "rcc/MC/MCExpr.h"
+#include "rcc/MC/MCFixup.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <limits>
+#include <string>
+#include <utility>
+#include <vector>
+
+namespace rcc::mc {
+namespace {
+
+constexpr std::uint8_t DWCFAAdvanceLoc = 0x40;
+constexpr std::uint8_t DWCFAOffset = 0x80;
+constexpr std::uint8_t DWCFARestore = 0xc0;
+constexpr std::uint8_t DWCFANop = 0x00;
+constexpr std::uint8_t DWCFAAdvanceLoc1 = 0x02;
+constexpr std::uint8_t DWCFAAdvanceLoc2 = 0x03;
+constexpr std::uint8_t DWCFAAdvanceLoc4 = 0x04;
+constexpr std::uint8_t DWCFAOffsetExtended = 0x05;
+constexpr std::uint8_t DWCFARestoreExtended = 0x06;
+constexpr std::uint8_t DWCFAUndefined = 0x07;
+constexpr std::uint8_t DWCFASameValue = 0x08;
+constexpr std::uint8_t DWCFARegister = 0x09;
+constexpr std::uint8_t DWCFARememberState = 0x0a;
+constexpr std::uint8_t DWCFARestoreState = 0x0b;
+constexpr std::uint8_t DWCFADefCFA = 0x0c;
+constexpr std::uint8_t DWCFADefCFARegister = 0x0d;
+constexpr std::uint8_t DWCFADefCFAOffset = 0x0e;
+constexpr std::uint8_t DWCFAValOffset = 0x14;
+constexpr std::uint8_t DWCFAGNUWindowSave = 0x2d;
+constexpr std::uint8_t DWCFAGNUArgsSize = 0x2e;
+constexpr std::uint8_t DWEHPEPCRelativeSData4 = 0x1b;
+
+void appendU16(std::vector<std::uint8_t> &Bytes, std::uint16_t Value) {
+  Bytes.push_back(static_cast<std::uint8_t>(Value));
+  Bytes.push_back(static_cast<std::uint8_t>(Value >> 8U));
+}
+
+void appendU32(std::vector<std::uint8_t> &Bytes, std::uint32_t Value) {
+  for (std::uint8_t Shift = 0; Shift < 32; Shift += 8)
+    Bytes.push_back(static_cast<std::uint8_t>(Value >> Shift));
+}
+
+void writeU32(std::vector<std::uint8_t> &Bytes, std::size_t Offset, std::uint32_t Value) {
+  for (std::uint8_t Shift = 0; Shift < 32; Shift += 8)
+    Bytes[Offset + Shift / 8U] = static_cast<std::uint8_t>(Value >> Shift);
+}
+
+void appendULEB128(std::vector<std::uint8_t> &Bytes, std::uint64_t Value) {
+  do {
+    std::uint8_t Byte = static_cast<std::uint8_t>(Value & 0x7fU);
+    Value >>= 7U;
+    if (Value != 0)
+      Byte |= 0x80U;
+    Bytes.push_back(Byte);
+  } while (Value != 0);
+}
+
+void appendSLEB128(std::vector<std::uint8_t> &Bytes, std::int64_t Value) {
+  bool More = true;
+  while (More) {
+    std::uint8_t Byte = static_cast<std::uint8_t>(Value & 0x7f);
+    const bool HasSign = (Byte & 0x40U) != 0;
+    Value >>= 7;
+    More = (Value != 0 || HasSign) && (Value != -1 || !HasSign);
+    if (More)
+      Byte |= 0x80U;
+    Bytes.push_back(Byte);
+  }
+}
+
+[[nodiscard]] Expected<void> appendAdvance(std::vector<std::uint8_t> &Bytes, std::uint64_t Delta,
+                                           const MCDwarfFrameInfo &Info) {
+  if (Delta == 0)
+    return {};
+  if (Delta % Info.CodeAlignment != 0) {
+    return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                          "CFI location is not aligned to the DWARF code factor");
+  }
+  const std::uint64_t Factored = Delta / Info.CodeAlignment;
+  if (Factored <= 0x3fU) {
+    Bytes.push_back(static_cast<std::uint8_t>(DWCFAAdvanceLoc | Factored));
+  } else if (Factored <= std::numeric_limits<std::uint8_t>::max()) {
+    Bytes.push_back(DWCFAAdvanceLoc1);
+    Bytes.push_back(static_cast<std::uint8_t>(Factored));
+  } else if (Factored <= std::numeric_limits<std::uint16_t>::max()) {
+    Bytes.push_back(DWCFAAdvanceLoc2);
+    appendU16(Bytes, static_cast<std::uint16_t>(Factored));
+  } else if (Factored <= std::numeric_limits<std::uint32_t>::max()) {
+    Bytes.push_back(DWCFAAdvanceLoc4);
+    appendU32(Bytes, static_cast<std::uint32_t>(Factored));
+  } else {
+    return makeUnexpected(ErrorCode::Unsupported, "DWARF CFI location delta exceeds 32 bits");
+  }
+  return {};
+}
+
+[[nodiscard]] Expected<std::uint64_t> registerNumber(std::int64_t Value) {
+  if (Value < 0 || static_cast<std::uint64_t>(Value) > std::numeric_limits<std::uint32_t>::max()) {
+    return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                          "DWARF CFI register number is out of range");
+  }
+  return static_cast<std::uint64_t>(Value);
+}
+
+[[nodiscard]] Expected<std::uint64_t> factoredOffset(std::int64_t Offset,
+                                                     std::int64_t DataAlignment) {
+  if (Offset == std::numeric_limits<std::int64_t>::min() && DataAlignment == -1) {
+    return makeUnexpected(ErrorCode::ObjectWritingFailed, "DWARF CFI offset factor overflows");
+  }
+  if (Offset % DataAlignment != 0) {
+    return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                          "DWARF CFI offset is not divisible by its data factor");
+  }
+  const std::int64_t Factored = Offset / DataAlignment;
+  if (Factored < 0) {
+    return makeUnexpected(ErrorCode::Unsupported, "DWARF CFI rule requires a signed offset opcode");
+  }
+  return static_cast<std::uint64_t>(Factored);
+}
+
+void appendOffsetRule(std::vector<std::uint8_t> &Bytes, std::uint64_t Register,
+                      std::uint64_t Offset) {
+  if (Register <= 0x3fU) {
+    Bytes.push_back(static_cast<std::uint8_t>(DWCFAOffset | Register));
+  } else {
+    Bytes.push_back(DWCFAOffsetExtended);
+    appendULEB128(Bytes, Register);
+  }
+  appendULEB128(Bytes, Offset);
+}
+
+void appendRestoreRule(std::vector<std::uint8_t> &Bytes, std::uint64_t Register) {
+  if (Register <= 0x3fU) {
+    Bytes.push_back(static_cast<std::uint8_t>(DWCFARestore | Register));
+  } else {
+    Bytes.push_back(DWCFARestoreExtended);
+    appendULEB128(Bytes, Register);
+  }
+}
+
+struct CFAState final {
+  std::uint64_t Register = 0;
+  std::int64_t Offset = 0;
+};
+
+[[nodiscard]] Expected<void>
+appendFrameInstructions(std::vector<std::uint8_t> &Bytes,
+                        std::span<const MCDwarfFrameInstruction> Instructions,
+                        const MCDwarfFrameInfo &Info) {
+  CFAState State{.Register = Info.InitialCFARegister,
+                 .Offset = static_cast<std::int64_t>(Info.InitialCFAOffset)};
+  std::vector<CFAState> StateStack;
+  std::uint64_t PreviousOffset = 0;
+  for (const MCDwarfFrameInstruction &Entry : Instructions) {
+    auto Verification = Entry.Instruction.verify();
+    if (!Verification)
+      return std::unexpected(Verification.error());
+    if (Entry.Offset < PreviousOffset) {
+      return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                            "DWARF CFI locations are not monotonic");
+    }
+    if (Entry.Instruction.Operation == MCCFIOperation::Label)
+      continue;
+    auto Advance = appendAdvance(Bytes, Entry.Offset - PreviousOffset, Info);
+    if (!Advance)
+      return std::unexpected(Advance.error());
+    PreviousOffset = Entry.Offset;
+
+    const auto &Operands = Entry.Instruction.Operands;
+    switch (Entry.Instruction.Operation) {
+    case MCCFIOperation::SameValue: {
+      auto Register = registerNumber(Operands[0]);
+      if (!Register)
+        return std::unexpected(Register.error());
+      Bytes.push_back(DWCFASameValue);
+      appendULEB128(Bytes, *Register);
+      break;
+    }
+    case MCCFIOperation::RememberState:
+      Bytes.push_back(DWCFARememberState);
+      StateStack.push_back(State);
+      break;
+    case MCCFIOperation::RestoreState:
+      if (StateStack.empty()) {
+        return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                              "DWARF CFI restore_state has no saved state");
+      }
+      Bytes.push_back(DWCFARestoreState);
+      State = StateStack.back();
+      StateStack.pop_back();
+      break;
+    case MCCFIOperation::Offset:
+    case MCCFIOperation::RelativeOffset: {
+      auto Register = registerNumber(Operands[0]);
+      if (!Register)
+        return std::unexpected(Register.error());
+      std::int64_t Offset = Operands[1];
+      if (Entry.Instruction.Operation == MCCFIOperation::RelativeOffset &&
+          __builtin_sub_overflow(Offset, State.Offset, &Offset)) {
+        return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                              "relative DWARF CFI offset overflows");
+      }
+      auto Factored = factoredOffset(Offset, Info.DataAlignment);
+      if (!Factored)
+        return std::unexpected(Factored.error());
+      appendOffsetRule(Bytes, *Register, *Factored);
+      break;
+    }
+    case MCCFIOperation::DefCFARegister: {
+      auto Register = registerNumber(Operands[0]);
+      if (!Register)
+        return std::unexpected(Register.error());
+      Bytes.push_back(DWCFADefCFARegister);
+      appendULEB128(Bytes, *Register);
+      State.Register = *Register;
+      break;
+    }
+    case MCCFIOperation::DefCFAOffset:
+      if (Operands[0] < 0) {
+        return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                              "DWARF CFA offset cannot be negative");
+      }
+      Bytes.push_back(DWCFADefCFAOffset);
+      appendULEB128(Bytes, static_cast<std::uint64_t>(Operands[0]));
+      State.Offset = Operands[0];
+      break;
+    case MCCFIOperation::DefCFA: {
+      auto Register = registerNumber(Operands[0]);
+      if (!Register)
+        return std::unexpected(Register.error());
+      if (Operands[1] < 0) {
+        return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                              "DWARF CFA offset cannot be negative");
+      }
+      Bytes.push_back(DWCFADefCFA);
+      appendULEB128(Bytes, *Register);
+      appendULEB128(Bytes, static_cast<std::uint64_t>(Operands[1]));
+      State = CFAState{.Register = *Register, .Offset = Operands[1]};
+      break;
+    }
+    case MCCFIOperation::AdjustCFAOffset: {
+      std::int64_t Adjusted = 0;
+      if (__builtin_add_overflow(State.Offset, Operands[0], &Adjusted) || Adjusted < 0) {
+        return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                              "adjusted DWARF CFA offset is invalid");
+      }
+      Bytes.push_back(DWCFADefCFAOffset);
+      appendULEB128(Bytes, static_cast<std::uint64_t>(Adjusted));
+      State.Offset = Adjusted;
+      break;
+    }
+    case MCCFIOperation::Escape:
+      Bytes.insert(Bytes.end(), Entry.Instruction.Bytes.begin(), Entry.Instruction.Bytes.end());
+      break;
+    case MCCFIOperation::Restore: {
+      auto Register = registerNumber(Operands[0]);
+      if (!Register)
+        return std::unexpected(Register.error());
+      appendRestoreRule(Bytes, *Register);
+      break;
+    }
+    case MCCFIOperation::Undefined: {
+      auto Register = registerNumber(Operands[0]);
+      if (!Register)
+        return std::unexpected(Register.error());
+      Bytes.push_back(DWCFAUndefined);
+      appendULEB128(Bytes, *Register);
+      break;
+    }
+    case MCCFIOperation::Register: {
+      auto Register = registerNumber(Operands[0]);
+      auto Source = registerNumber(Operands[1]);
+      if (!Register)
+        return std::unexpected(Register.error());
+      if (!Source)
+        return std::unexpected(Source.error());
+      Bytes.push_back(DWCFARegister);
+      appendULEB128(Bytes, *Register);
+      appendULEB128(Bytes, *Source);
+      break;
+    }
+    case MCCFIOperation::WindowSave:
+      Bytes.push_back(DWCFAGNUWindowSave);
+      break;
+    case MCCFIOperation::GNUArgsSize:
+      if (Operands[0] < 0) {
+        return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                              "DWARF GNU argument size cannot be negative");
+      }
+      Bytes.push_back(DWCFAGNUArgsSize);
+      appendULEB128(Bytes, static_cast<std::uint64_t>(Operands[0]));
+      break;
+    case MCCFIOperation::ValueOffset: {
+      auto Register = registerNumber(Operands[0]);
+      if (!Register)
+        return std::unexpected(Register.error());
+      auto Factored = factoredOffset(Operands[1], Info.DataAlignment);
+      if (!Factored)
+        return std::unexpected(Factored.error());
+      Bytes.push_back(DWCFAValOffset);
+      appendULEB128(Bytes, *Register);
+      appendULEB128(Bytes, *Factored);
+      break;
+    }
+    case MCCFIOperation::StartProc:
+    case MCCFIOperation::EndProc:
+    case MCCFIOperation::Sections:
+    case MCCFIOperation::Personality:
+    case MCCFIOperation::LSDA:
+    case MCCFIOperation::SignalFrame:
+    case MCCFIOperation::ReturnColumn:
+    case MCCFIOperation::NegateReturnAddressState:
+    case MCCFIOperation::NegateReturnAddressStateWithPC:
+    case MCCFIOperation::Label:
+      return makeUnexpected(ErrorCode::Unsupported,
+                            "this CFI operation cannot be encoded in an RV64GC FDE");
+    }
+  }
+  if (!StateStack.empty()) {
+    return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                          "DWARF CFI procedure has unbalanced remember_state operations");
+  }
+  return {};
+}
+
+[[nodiscard]] Expected<void> finishEntry(std::vector<std::uint8_t> &Bytes, std::size_t EntryStart) {
+  while (Bytes.size() % 4U != 0)
+    Bytes.push_back(DWCFANop);
+  const std::size_t Length = Bytes.size() - EntryStart - 4U;
+  if (Length > std::numeric_limits<std::uint32_t>::max()) {
+    return makeUnexpected(ErrorCode::Unsupported, "DWARF frame entry exceeds 32 bits");
+  }
+  writeU32(Bytes, EntryStart, static_cast<std::uint32_t>(Length));
+  return {};
+}
+
+} // namespace
+
+Expected<void> MCDwarfFrameInfo::verify() const {
+  if (CodeAlignment == 0 || DataAlignment == 0) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "DWARF frame alignment factors must be nonzero");
+  }
+  if (InitialCFAOffset > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max())) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "initial DWARF CFA offset is too large");
+  }
+  return {};
+}
+
+Expected<MCObjectSection> emitDwarfEHFrame(MCSectionRef Section,
+                                           std::span<const MCDwarfFrameProcedure> Procedures,
+                                           const MCDwarfFrameInfo &Info,
+                                           const MCAsmBackend &Backend) {
+  if (!Section || Section->description().Kind != MCSectionKind::EHFrame) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "DWARF EH frame emission requires an EHFrame section");
+  }
+  auto Verification = Info.verify();
+  if (!Verification)
+    return std::unexpected(Verification.error());
+
+  MCObjectSection Result{.Section = std::move(Section),
+                         .Contents = {},
+                         .AddressSize = 0,
+                         .Alignment = 1,
+                         .Relocations = {}};
+  Result.Alignment = Result.Section->description().Alignment;
+  const std::size_t CIEStart = Result.Contents.size();
+  appendU32(Result.Contents, 0);
+  appendU32(Result.Contents, 0);
+  Result.Contents.push_back(1);
+  Result.Contents.insert(Result.Contents.end(), {'z', 'R', 0});
+  appendULEB128(Result.Contents, Info.CodeAlignment);
+  appendSLEB128(Result.Contents, Info.DataAlignment);
+  appendULEB128(Result.Contents, Info.ReturnAddressRegister);
+  appendULEB128(Result.Contents, 1);
+  Result.Contents.push_back(DWEHPEPCRelativeSData4);
+  Result.Contents.push_back(DWCFADefCFA);
+  appendULEB128(Result.Contents, Info.InitialCFARegister);
+  appendULEB128(Result.Contents, Info.InitialCFAOffset);
+  auto FinishedCIE = finishEntry(Result.Contents, CIEStart);
+  if (!FinishedCIE)
+    return std::unexpected(FinishedCIE.error());
+
+  for (const MCDwarfFrameProcedure &Procedure : Procedures) {
+    if (!Procedure.Function) {
+      return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                            "DWARF frame procedure has no function symbol");
+    }
+    if (Procedure.AddressRange > std::numeric_limits<std::uint32_t>::max()) {
+      return makeUnexpected(ErrorCode::Unsupported, "DWARF FDE address range exceeds 32 bits");
+    }
+    const std::size_t FDEStart = Result.Contents.size();
+    appendU32(Result.Contents, 0);
+    const std::size_t CIEPointerOffset = Result.Contents.size();
+    const std::size_t CIEDistance = CIEPointerOffset - CIEStart;
+    if (CIEDistance > std::numeric_limits<std::uint32_t>::max()) {
+      return makeUnexpected(ErrorCode::Unsupported, "DWARF FDE CIE distance exceeds 32 bits");
+    }
+    appendU32(Result.Contents, static_cast<std::uint32_t>(CIEDistance));
+    const std::size_t InitialLocationOffset = Result.Contents.size();
+    appendU32(Result.Contents, 0);
+    appendU32(Result.Contents, static_cast<std::uint32_t>(Procedure.AddressRange));
+    appendULEB128(Result.Contents, 0);
+    auto Instructions = appendFrameInstructions(Result.Contents, Procedure.Instructions, Info);
+    if (!Instructions)
+      return std::unexpected(Instructions.error());
+    auto FinishedFDE = finishEntry(Result.Contents, FDEStart);
+    if (!FinishedFDE)
+      return std::unexpected(FinishedFDE.error());
+
+    auto Expression = MCExpr::symbol(Procedure.Function);
+    if (!Expression)
+      return std::unexpected(Expression.error());
+    MCFixup Fixup{.Offset = InitialLocationOffset,
+                  .Value = *Expression,
+                  .Kind = fixup_kind::PCRelative4,
+                  .PCRelative = true,
+                  .LinkerRelaxable = false};
+    MCValue Value{
+        .AddSymbol = Procedure.Function, .SubtractSymbol = {}, .Addend = 0, .TargetKind = 0};
+    auto Relocation = Backend.relocationType(Fixup, Value);
+    if (!Relocation)
+      return std::unexpected(Relocation.error());
+    Result.Relocations.push_back(MCObjectRelocation{
+        .Offset = InitialLocationOffset,
+        .Type = *Relocation,
+        .Symbol = Procedure.Function,
+        .Addend = 0,
+    });
+  }
+  Result.AddressSize = Result.Contents.size();
+  return Result;
+}
+
+} // namespace rcc::mc
diff --git a/backend/lib/MC/MCFixup.cpp b/backend/lib/MC/MCFixup.cpp
new file mode 100644
index 0000000..8819cd4
--- /dev/null
+++ b/backend/lib/MC/MCFixup.cpp
@@ -0,0 +1,177 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/MC/MCFixup.h"
+
+#include <algorithm>
+#include <array>
+#include <cstdint>
+#include <limits>
+#include <utility>
+#include <vector>
+
+namespace rcc::mc {
+namespace {
+
+[[nodiscard]] Expected<std::int64_t> checkedAdd(std::int64_t Left, std::int64_t Right) {
+  std::int64_t Result = 0;
+  if (__builtin_add_overflow(Left, Right, &Result))
+    return makeUnexpected(ErrorCode::RelocationFailed, "MC expression addition overflows");
+  return Result;
+}
+
+[[nodiscard]] Expected<std::int64_t> checkedSubtract(std::int64_t Left, std::int64_t Right) {
+  std::int64_t Result = 0;
+  if (__builtin_sub_overflow(Left, Right, &Result))
+    return makeUnexpected(ErrorCode::RelocationFailed, "MC expression subtraction overflows");
+  return Result;
+}
+
+[[nodiscard]] Expected<MCValue> combineLinearValues(const MCValue &Left, const MCValue &Right,
+                                                    bool SubtractRight) {
+  struct SymbolTerm final {
+    MCSymbolRef Symbol;
+    int Coefficient = 0;
+  };
+  std::vector<SymbolTerm> Terms;
+  const auto AddTerm = [&Terms](const MCSymbolRef &Symbol, int Coefficient) -> Expected<void> {
+    if (!Symbol)
+      return {};
+    const auto Position = std::ranges::find(Terms, Symbol, &SymbolTerm::Symbol);
+    if (Position == Terms.end()) {
+      Terms.push_back(SymbolTerm{.Symbol = Symbol, .Coefficient = Coefficient});
+      return {};
+    }
+    Position->Coefficient += Coefficient;
+    if (Position->Coefficient < -1 || Position->Coefficient > 1) {
+      return makeUnexpected(ErrorCode::RelocationFailed,
+                            "MC expression has a symbol coefficient outside -1 to 1");
+    }
+    if (Position->Coefficient == 0)
+      Terms.erase(Position);
+    return {};
+  };
+
+  for (const auto &[Symbol, Coefficient] : std::array<std::pair<MCSymbolRef, int>, 4>{
+           std::pair{Left.AddSymbol, 1},
+           std::pair{Left.SubtractSymbol, -1},
+           std::pair{Right.AddSymbol, SubtractRight ? -1 : 1},
+           std::pair{Right.SubtractSymbol, SubtractRight ? 1 : -1},
+       }) {
+    auto Added = AddTerm(Symbol, Coefficient);
+    if (!Added)
+      return std::unexpected(Added.error());
+  }
+
+  MCValue Result;
+  for (const SymbolTerm &Term : Terms) {
+    MCSymbolRef &Destination = Term.Coefficient > 0 ? Result.AddSymbol : Result.SubtractSymbol;
+    if (Destination) {
+      return makeUnexpected(ErrorCode::RelocationFailed,
+                            "MC expression contains more than one symbol with the same sign");
+    }
+    Destination = Term.Symbol;
+  }
+  auto Addend = SubtractRight ? checkedSubtract(Left.Addend, Right.Addend)
+                              : checkedAdd(Left.Addend, Right.Addend);
+  if (!Addend)
+    return std::unexpected(Addend.error());
+  Result.Addend = *Addend;
+  return Result;
+}
+
+[[nodiscard]] Expected<MCValue> evaluate(const MCExpr &Expression, std::size_t Depth) {
+  if (Depth > 256)
+    return makeUnexpected(ErrorCode::RelocationFailed, "MC expression exceeds its depth limit");
+
+  switch (Expression.kind()) {
+  case MCExpr::Kind::Constant:
+    return MCValue{.AddSymbol = {},
+                   .SubtractSymbol = {},
+                   .Addend = *Expression.getIf<std::int64_t>(),
+                   .TargetKind = 0};
+  case MCExpr::Kind::SymbolRef:
+    return MCValue{.AddSymbol = Expression.getIf<MCSymbolRefExpr>()->Symbol,
+                   .SubtractSymbol = {},
+                   .Addend = 0,
+                   .TargetKind = 0};
+  case MCExpr::Kind::Target: {
+    const auto &Target = *Expression.getIf<MCTargetExpr>();
+    auto Result = evaluate(*Target.Operand, Depth + 1);
+    if (!Result)
+      return std::unexpected(Result.error());
+    if (Result->TargetKind != 0) {
+      return makeUnexpected(ErrorCode::RelocationFailed,
+                            "nested target MC expressions are not relocatable");
+    }
+    Result->TargetKind = Target.Kind;
+    return Result;
+  }
+  case MCExpr::Kind::Unary: {
+    const auto &Unary = *Expression.getIf<MCUnaryExpr>();
+    auto Operand = evaluate(*Unary.Operand, Depth + 1);
+    if (!Operand)
+      return std::unexpected(Operand.error());
+    if (Unary.Operator == MCUnaryOperator::Plus)
+      return Operand;
+    if (Unary.Operator == MCUnaryOperator::Minus && Operand->isAbsolute()) {
+      if (Operand->Addend == std::numeric_limits<std::int64_t>::min()) {
+        return makeUnexpected(ErrorCode::RelocationFailed, "MC expression negation overflows");
+      }
+      Operand->Addend = -Operand->Addend;
+      return Operand;
+    }
+    const auto Absolute = Expression.evaluateAbsolute();
+    if (!Absolute) {
+      return makeUnexpected(ErrorCode::RelocationFailed,
+                            "symbolic unary MC expression is not relocatable");
+    }
+    return MCValue{.AddSymbol = {}, .SubtractSymbol = {}, .Addend = *Absolute, .TargetKind = 0};
+  }
+  case MCExpr::Kind::Binary: {
+    const auto &Binary = *Expression.getIf<MCBinaryExpr>();
+    if (Binary.Operator != MCBinaryOperator::Add && Binary.Operator != MCBinaryOperator::Subtract) {
+      const auto Absolute = Expression.evaluateAbsolute();
+      if (!Absolute) {
+        return makeUnexpected(ErrorCode::RelocationFailed,
+                              "symbolic binary MC expression is not relocatable");
+      }
+      return MCValue{.AddSymbol = {}, .SubtractSymbol = {}, .Addend = *Absolute, .TargetKind = 0};
+    }
+    auto Left = evaluate(*Binary.Left, Depth + 1);
+    auto Right = evaluate(*Binary.Right, Depth + 1);
+    if (!Left)
+      return std::unexpected(Left.error());
+    if (!Right)
+      return std::unexpected(Right.error());
+    if (Left->TargetKind != 0 || Right->TargetKind != 0) {
+      return makeUnexpected(ErrorCode::RelocationFailed,
+                            "target MC expression cannot participate in outer arithmetic");
+    }
+
+    return combineLinearValues(*Left, *Right, Binary.Operator == MCBinaryOperator::Subtract);
+  }
+  }
+  return makeUnexpected(ErrorCode::InternalError, "MC expression has an invalid kind");
+}
+
+} // namespace
+
+Expected<void> MCFixup::verify() const {
+  if (Kind == fixup_kind::None)
+    return makeUnexpected(ErrorCode::InvalidArgument, "MC fixup has no kind");
+  if (!Value)
+    return makeUnexpected(ErrorCode::InvalidArgument, "MC fixup has no value expression");
+  auto Verification = Value->verify();
+  if (!Verification)
+    return std::unexpected(Verification.error());
+  return {};
+}
+
+Expected<MCValue> evaluateAsRelocatable(const MCExpr &Expression) {
+  auto Verification = Expression.verify();
+  if (!Verification)
+    return std::unexpected(Verification.error());
+  return evaluate(Expression, 0);
+}
+
+} // namespace rcc::mc
diff --git a/backend/lib/MC/MCObjectStreamer.cpp b/backend/lib/MC/MCObjectStreamer.cpp
new file mode 100644
index 0000000..634b713
--- /dev/null
+++ b/backend/lib/MC/MCObjectStreamer.cpp
@@ -0,0 +1,132 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/MC/MCObjectStreamer.h"
+
+#include <utility>
+
+namespace rcc::mc {
+
+Expected<void> ELFObjectStreamer::ensureOpen() const {
+  if (IsFinished)
+    return makeUnexpected(ErrorCode::ObjectWritingFailed, "object stream is already finalized");
+  return {};
+}
+
+Expected<void> ELFObjectStreamer::switchSection(MCSectionRef Section) {
+  auto Open = ensureOpen();
+  return Open ? Assembler.switchSection(std::move(Section)) : Open;
+}
+
+Expected<void> ELFObjectStreamer::emitLabel(MCSymbolRef Symbol) {
+  auto Open = ensureOpen();
+  return Open ? Assembler.emitLabel(std::move(Symbol)) : Open;
+}
+
+Expected<void> ELFObjectStreamer::emitInstruction(const MCInst &Instruction) {
+  auto Open = ensureOpen();
+  return Open ? Assembler.emitInstruction(Instruction) : Open;
+}
+
+Expected<void> ELFObjectStreamer::emitValue(MCExprRef Value, std::uint8_t Size) {
+  auto Open = ensureOpen();
+  return Open ? Assembler.emitValue(std::move(Value), Size) : Open;
+}
+
+Expected<void> ELFObjectStreamer::emitBytes(std::span<const std::uint8_t> Bytes) {
+  auto Open = ensureOpen();
+  return Open ? Assembler.emitBytes(Bytes) : Open;
+}
+
+Expected<void> ELFObjectStreamer::emitZeroFill(std::uint64_t Size) {
+  auto Open = ensureOpen();
+  return Open ? Assembler.emitZeroFill(Size) : Open;
+}
+
+Expected<void> ELFObjectStreamer::emitAlignment(std::uint64_t Alignment, std::uint8_t Fill,
+                                                std::uint64_t MaximumBytes) {
+  auto Open = ensureOpen();
+  return Open ? Assembler.emitAlignment(Alignment, Fill, MaximumBytes) : Open;
+}
+
+Expected<void> ELFObjectStreamer::emitSymbolAttribute(MCSymbolRef Symbol,
+                                                      MCSymbolAttribute Attribute) {
+  auto Open = ensureOpen();
+  return Open ? Assembler.emitSymbolAttribute(std::move(Symbol), Attribute) : Open;
+}
+
+Expected<void> ELFObjectStreamer::emitSymbolSize(MCSymbolRef Symbol, MCExprRef Size) {
+  auto Open = ensureOpen();
+  return Open ? Assembler.emitSymbolSize(std::move(Symbol), std::move(Size)) : Open;
+}
+
+Expected<void> ELFObjectStreamer::emitCommonSymbol(MCSymbolRef Symbol, std::uint64_t Size,
+                                                   std::uint64_t Alignment) {
+  auto Open = ensureOpen();
+  return Open ? Assembler.emitCommonSymbol(std::move(Symbol), Size, Alignment) : Open;
+}
+
+Expected<void> ELFObjectStreamer::emitDirective(std::string_view Name, std::string_view) {
+  auto Open = ensureOpen();
+  if (!Open)
+    return Open;
+  if (Name == "attribute")
+    return {};
+  return makeUnexpected(ErrorCode::Unsupported,
+                        "native object emission does not support the MC directive '" +
+                            std::string(Name) + "'");
+}
+
+Expected<void> ELFObjectStreamer::emitCFI(const MCCFIInstruction &Instruction) {
+  auto Open = ensureOpen();
+  if (!Open)
+    return Open;
+  return Assembler.emitCFI(Instruction);
+}
+
+Expected<void> ELFObjectStreamer::emitInlineAssembly(std::string_view Text) {
+  auto Open = ensureOpen();
+  if (!Open)
+    return Open;
+  if (Text.empty())
+    return {};
+  return makeUnexpected(ErrorCode::Unsupported,
+                        "native object emission requires parsed inline assembly");
+}
+
+Expected<void> ELFObjectStreamer::emitComment(std::string_view) {
+  return ensureOpen();
+}
+
+Expected<void> ELFObjectStreamer::configureDwarfFrame(MCSectionRef Section, MCDwarfFrameInfo Info) {
+  auto Open = ensureOpen();
+  if (!Open)
+    return Open;
+  return Assembler.configureDwarfFrame(std::move(Section), Info);
+}
+
+Expected<void> ELFObjectStreamer::finish() {
+  auto Open = ensureOpen();
+  if (!Open)
+    return Open;
+  auto Object = Assembler.assemble();
+  if (!Object)
+    return std::unexpected(Object.error());
+  auto Written = Writer->writeObject(*Object);
+  if (!Written)
+    return std::unexpected(Written.error());
+  Output = std::move(*Written);
+  IsFinished = true;
+  return {};
+}
+
+Expected<std::vector<std::uint8_t>> ELFObjectStreamer::takeOutput() {
+  if (!IsFinished)
+    return makeUnexpected(ErrorCode::ObjectWritingFailed,
+                          "object output cannot be taken before finalization");
+  if (OutputWasTaken)
+    return makeUnexpected(ErrorCode::ObjectWritingFailed, "object output was already taken");
+  OutputWasTaken = true;
+  return std::move(Output);
+}
+
+} // namespace rcc::mc
diff --git a/backend/lib/MC/MCStreamer.cpp b/backend/lib/MC/MCStreamer.cpp
index 001fa28..56c3f96 100644
--- a/backend/lib/MC/MCStreamer.cpp
+++ b/backend/lib/MC/MCStreamer.cpp
@@ -342,6 +342,22 @@ Expected<void> AsmTextStreamer::emitSymbolSize(MCSymbolRef Symbol, MCExprRef Siz
   return appendLine({}, ".size " + *Name + ", " + *PrintedSize);
 }
 
+Expected<void> AsmTextStreamer::emitCommonSymbol(MCSymbolRef Symbol, std::uint64_t Size,
+                                                 std::uint64_t Alignment) {
+  if (IsFinished)
+    return makeUnexpected(ErrorCode::AssemblyLoweringFailed,
+                          "cannot emit a common symbol after assembly finalization");
+  if (!Symbol || Size == 0 || Alignment == 0 || (Alignment & (Alignment - 1U)) != 0) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "common symbol requires a symbol, size, and power-of-two alignment");
+  }
+  auto Name = printMCSymbolName(Symbol->name());
+  if (!Name)
+    return std::unexpected(Name.error());
+  return appendLine({}, ".comm " + *Name + "," + std::to_string(Size) + "," +
+                            std::to_string(Alignment));
+}
+
 Expected<void> AsmTextStreamer::emitDirective(std::string_view Name, std::string_view Arguments) {
   if (!isDirectiveName(Name) || containsInvalidLineCharacter(Arguments)) {
     return makeUnexpected(ErrorCode::InvalidArgument,