[MIR] Add machine instruction lexer

5 files changed, 1569 insertions, 4 deletions

diff --git a/backend/include/rcc/MIR/MILexer.h b/backend/include/rcc/MIR/MILexer.h
new file mode 100644
index 0000000..f54f255
--- /dev/null
+++ b/backend/include/rcc/MIR/MILexer.h
@@ -0,0 +1,181 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_MIR_MILEXER_H
+#define RCC_MIR_MILEXER_H
+
+#include "rcc/Support/TextDiagnostic.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <memory>
+#include <span>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <variant>
+
+namespace rcc::mir {
+
+enum class MITokenKind : std::uint8_t {
+  EndOfFile,
+  Error,
+  Newline,
+
+  Comma,
+  Equal,
+  Underscore,
+  Colon,
+  DoubleColon,
+  Dot,
+  Exclaim,
+  LeftParen,
+  RightParen,
+  LeftBrace,
+  RightBrace,
+  Plus,
+  Minus,
+  Less,
+  Greater,
+
+  Keyword,
+  MetadataKeyword,
+  Identifier,
+  NamedRegister,
+  NamedVirtualRegister,
+  MachineBasicBlockLabel,
+  MachineBasicBlock,
+  StackObject,
+  FixedStackObject,
+  NamedGlobalValue,
+  GlobalValue,
+  ExternalSymbol,
+  MCSymbol,
+  IntegerLiteral,
+  FloatingPointLiteral,
+  HexLiteral,
+  VirtualRegister,
+  ConstantPoolItem,
+  JumpTableIndex,
+  NamedIRBlock,
+  IRBlock,
+  NamedIRValue,
+  IRValue,
+  QuotedIRValue,
+  SubRegisterIndex,
+  StringConstant,
+};
+
+[[nodiscard]] std::string_view getMITokenKindName(MITokenKind Kind) noexcept;
+[[nodiscard]] bool isMIKeyword(std::string_view Spelling) noexcept;
+[[nodiscard]] bool isMIMetadataKeyword(std::string_view Spelling) noexcept;
+
+class MIToken final {
+public:
+  [[nodiscard]] MITokenKind kind() const noexcept {
+    return Kind;
+  }
+
+  [[nodiscard]] const TextRange &range() const noexcept {
+    return Range;
+  }
+
+  [[nodiscard]] std::string_view spelling() const noexcept {
+    return Spelling;
+  }
+
+  [[nodiscard]] bool hasStringValue() const noexcept {
+    return !std::holds_alternative<std::monostate>(StringValue);
+  }
+
+  [[nodiscard]] std::string_view stringValue() const noexcept;
+
+  [[nodiscard]] bool hasIntegerValue() const noexcept {
+    return !IntegerValue.empty();
+  }
+
+  [[nodiscard]] std::string_view integerValue() const noexcept {
+    return IntegerValue;
+  }
+
+  [[nodiscard]] bool is(MITokenKind Expected) const noexcept {
+    return Kind == Expected;
+  }
+
+  [[nodiscard]] bool isKeyword(std::string_view Expected) const noexcept {
+    return Kind == MITokenKind::Keyword && stringValue() == Expected;
+  }
+
+  [[nodiscard]] bool isMetadataKeyword(std::string_view Expected) const noexcept {
+    return Kind == MITokenKind::MetadataKeyword && stringValue() == Expected;
+  }
+
+  [[nodiscard]] bool isNewlineOrEnd() const noexcept {
+    return Kind == MITokenKind::Newline || Kind == MITokenKind::EndOfFile;
+  }
+
+  [[nodiscard]] bool isErrorOrEnd() const noexcept {
+    return Kind == MITokenKind::Error || Kind == MITokenKind::EndOfFile;
+  }
+
+  [[nodiscard]] bool isRegister() const noexcept;
+  [[nodiscard]] bool isRegisterFlag() const noexcept;
+  [[nodiscard]] bool isMemoryOperandFlag() const noexcept;
+
+private:
+  using StringValueStorage = std::variant<std::monostate, std::string_view, std::string>;
+
+  MIToken(MITokenKind Kind, TextRange Range, std::string_view Spelling,
+          StringValueStorage StringValue = {}, std::string_view IntegerValue = {})
+      : Kind(Kind), Range(Range), Spelling(Spelling), StringValue(std::move(StringValue)),
+        IntegerValue(IntegerValue) {}
+
+  MITokenKind Kind = MITokenKind::Error;
+  TextRange Range;
+  std::string_view Spelling;
+  StringValueStorage StringValue;
+  std::string_view IntegerValue;
+
+  friend class MILexer;
+};
+
+struct MILexerOptions final {
+  std::size_t MaximumTokenLength = std::size_t{1} << 24U;
+  std::size_t MaximumTokens = std::size_t{1} << 24U;
+};
+
+class MILexer final {
+public:
+  MILexer(std::string SourceName, std::string SourceText, MILexerOptions Options = {});
+  MILexer(const MILexer &) = delete;
+  MILexer &operator=(const MILexer &) = delete;
+  MILexer(MILexer &&) noexcept;
+  MILexer &operator=(MILexer &&) noexcept;
+  ~MILexer();
+
+  [[nodiscard]] MIToken next();
+
+  [[nodiscard]] const TextSource &source() const noexcept;
+  [[nodiscard]] std::span<const TextDiagnostic> diagnostics() const noexcept;
+  [[nodiscard]] bool failed() const noexcept;
+  [[nodiscard]] std::size_t tokenCount() const noexcept;
+
+private:
+  [[nodiscard]] static MIToken makeToken(MITokenKind Kind, TextRange Range,
+                                         std::string_view Spelling,
+                                         std::string_view IntegerValue = {});
+  [[nodiscard]] static MIToken makeStringToken(MITokenKind Kind, TextRange Range,
+                                               std::string_view Spelling,
+                                               std::string_view StringValue,
+                                               std::string_view IntegerValue = {});
+  [[nodiscard]] static MIToken makeOwnedStringToken(MITokenKind Kind, TextRange Range,
+                                                    std::string_view Spelling,
+                                                    std::string StringValue,
+                                                    std::string_view IntegerValue = {});
+
+  class Impl;
+  std::unique_ptr<Impl> Implementation;
+};
+
+} // namespace rcc::mir
+
+#endif // RCC_MIR_MILEXER_H
diff --git a/backend/lib/MIR/CMakeLists.txt b/backend/lib/MIR/CMakeLists.txt
index 882e488..ca213aa 100644
--- a/backend/lib/MIR/CMakeLists.txt
+++ b/backend/lib/MIR/CMakeLists.txt
@@ -1,9 +1,14 @@
 # SPDX-License-Identifier: GPL-3.0-or-later
 
-set(RCCBackendMIRSources EmbeddedIR.cpp)
+set(
+  RCCBackendMIRSources
+  EmbeddedIR.cpp
+  MILexer.cpp
+)
 set(
   RCCBackendMIRHeaders
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MIR/EmbeddedIR.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MIR/MILexer.h"
 )
 
 add_library(RCCBackendMIR ${RCCBackendMIRSources})
@@ -36,6 +41,10 @@ install(
 
 rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/EmbeddedIR.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MILexer.cpp"
   ${RCCBackendMIRHeaders}
 )
-rcc_backend_register_tidy_files("${CMAKE_CURRENT_SOURCE_DIR}/EmbeddedIR.cpp")
+rcc_backend_register_tidy_files(
+  "${CMAKE_CURRENT_SOURCE_DIR}/EmbeddedIR.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MILexer.cpp"
+)
diff --git a/backend/lib/MIR/MILexer.cpp b/backend/lib/MIR/MILexer.cpp
new file mode 100644
index 0000000..816264e
--- /dev/null
+++ b/backend/lib/MIR/MILexer.cpp
@@ -0,0 +1,946 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/MIR/MILexer.h"
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <cstddef>
+#include <cstdint>
+#include <iomanip>
+#include <optional>
+#include <ranges>
+#include <sstream>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <vector>
+
+namespace rcc::mir {
+namespace {
+
+template <std::size_t Size>
+[[nodiscard]] consteval std::array<std::string_view, Size>
+sortSpellings(std::array<std::string_view, Size> Spellings) {
+  for (std::size_t Left = 0; Left < Spellings.size(); ++Left) {
+    for (std::size_t Right = Left + 1; Right < Spellings.size(); ++Right) {
+      if (Spellings[Right] < Spellings[Left])
+        std::swap(Spellings[Left], Spellings[Right]);
+    }
+  }
+  return Spellings;
+}
+
+template <std::size_t Size>
+[[nodiscard]] consteval bool
+hasUniqueSpellings(const std::array<std::string_view, Size> &Spellings) {
+  for (std::size_t Index = 1; Index < Spellings.size(); ++Index) {
+    if (Spellings[Index - 1] == Spellings[Index])
+      return false;
+  }
+  return true;
+}
+
+constexpr auto Keywords = sortSpellings(std::array{
+    std::string_view{"addrspace"},
+    std::string_view{"adjust_cfa_offset"},
+    std::string_view{"afn"},
+    std::string_view{"align"},
+    std::string_view{"arcp"},
+    std::string_view{"basealign"},
+    std::string_view{"bb_id"},
+    std::string_view{"bbsections"},
+    std::string_view{"bfloat"},
+    std::string_view{"blockaddress"},
+    std::string_view{"call-entry"},
+    std::string_view{"call-frame-size"},
+    std::string_view{"cfi-type"},
+    std::string_view{"constant-pool"},
+    std::string_view{"contract"},
+    std::string_view{"custom"},
+    std::string_view{"dead"},
+    std::string_view{"deactivation-symbol"},
+    std::string_view{"debug-instr-number"},
+    std::string_view{"debug-location"},
+    std::string_view{"debug-use"},
+    std::string_view{"dbg-instr-ref"},
+    std::string_view{"def"},
+    std::string_view{"def_cfa"},
+    std::string_view{"def_cfa_offset"},
+    std::string_view{"def_cfa_register"},
+    std::string_view{"dereferenceable"},
+    std::string_view{"disjoint"},
+    std::string_view{"distinct"},
+    std::string_view{"double"},
+    std::string_view{"early-clobber"},
+    std::string_view{"ehfunclet-entry"},
+    std::string_view{"ehscope-entry"},
+    std::string_view{"escape"},
+    std::string_view{"exact"},
+    std::string_view{"float"},
+    std::string_view{"floatpred"},
+    std::string_view{"fp128"},
+    std::string_view{"frame-destroy"},
+    std::string_view{"frame-setup"},
+    std::string_view{"got"},
+    std::string_view{"half"},
+    std::string_view{"heap-alloc-marker"},
+    std::string_view{"implicit"},
+    std::string_view{"implicit-def"},
+    std::string_view{"inbounds"},
+    std::string_view{"inlineasm-br-indirect-target"},
+    std::string_view{"internal"},
+    std::string_view{"intpred"},
+    std::string_view{"intrinsic"},
+    std::string_view{"invariant"},
+    std::string_view{"ir-block-address-taken"},
+    std::string_view{"jump-table"},
+    std::string_view{"killed"},
+    std::string_view{"landing-pad"},
+    std::string_view{"lanemask"},
+    std::string_view{"liveins"},
+    std::string_view{"liveout"},
+    std::string_view{"llvm_def_aspace_cfa"},
+    std::string_view{"llvm_register_pair"},
+    std::string_view{"llvm_vector_offset"},
+    std::string_view{"llvm_vector_register_mask"},
+    std::string_view{"llvm_vector_registers"},
+    std::string_view{"machine-block-address-taken"},
+    std::string_view{"mmra"},
+    std::string_view{"negate_ra_sign_state"},
+    std::string_view{"negate_ra_sign_state_with_pc"},
+    std::string_view{"ninf"},
+    std::string_view{"nnan"},
+    std::string_view{"noconvergent"},
+    std::string_view{"nofpexcept"},
+    std::string_view{"non-temporal"},
+    std::string_view{"nneg"},
+    std::string_view{"nsw"},
+    std::string_view{"nsz"},
+    std::string_view{"nusw"},
+    std::string_view{"nuw"},
+    std::string_view{"offset"},
+    std::string_view{"pcsections"},
+    std::string_view{"post-instr-symbol"},
+    std::string_view{"ppc_fp128"},
+    std::string_view{"pre-instr-symbol"},
+    std::string_view{"reassoc"},
+    std::string_view{"rel_offset"},
+    std::string_view{"remember_state"},
+    std::string_view{"renamable"},
+    std::string_view{"register"},
+    std::string_view{"restore"},
+    std::string_view{"restore_state"},
+    std::string_view{"same_value"},
+    std::string_view{"samesign"},
+    std::string_view{"shufflemask"},
+    std::string_view{"stack"},
+    std::string_view{"successors"},
+    std::string_view{"target-flags"},
+    std::string_view{"target-index"},
+    std::string_view{"tied-def"},
+    std::string_view{"undef"},
+    std::string_view{"undefined"},
+    std::string_view{"unknown-address"},
+    std::string_view{"unknown-size"},
+    std::string_view{"unpredictable"},
+    std::string_view{"volatile"},
+    std::string_view{"window_save"},
+    std::string_view{"x86_fp80"},
+});
+
+constexpr auto MetadataKeywords = sortSpellings(std::array{
+    std::string_view{"!DIExpression"},
+    std::string_view{"!DILocation"},
+    std::string_view{"!alias.scope"},
+    std::string_view{"!noalias"},
+    std::string_view{"!noalias.addrspace"},
+    std::string_view{"!range"},
+    std::string_view{"!tbaa"},
+});
+
+static_assert(hasUniqueSpellings(Keywords));
+static_assert(hasUniqueSpellings(MetadataKeywords));
+
+[[nodiscard]] constexpr bool isASCIIAlpha(char Character) noexcept {
+  return (Character >= 'a' && Character <= 'z') || (Character >= 'A' && Character <= 'Z');
+}
+
+[[nodiscard]] constexpr bool isASCIIDigit(char Character) noexcept {
+  return Character >= '0' && Character <= '9';
+}
+
+[[nodiscard]] constexpr bool isASCIIHexDigit(char Character) noexcept {
+  return isASCIIDigit(Character) || (Character >= 'a' && Character <= 'f') ||
+         (Character >= 'A' && Character <= 'F');
+}
+
+[[nodiscard]] constexpr unsigned hexDigitValue(char Character) noexcept {
+  if (isASCIIDigit(Character))
+    return static_cast<unsigned>(Character - '0');
+  if (Character >= 'a' && Character <= 'f')
+    return static_cast<unsigned>(Character - 'a' + 10);
+  return static_cast<unsigned>(Character - 'A' + 10);
+}
+
+[[nodiscard]] constexpr bool isIdentifierCharacter(char Character) noexcept {
+  return isASCIIAlpha(Character) || isASCIIDigit(Character) || Character == '_' ||
+         Character == '-' || Character == '.' || Character == '$';
+}
+
+[[nodiscard]] constexpr bool isRegisterCharacter(char Character) noexcept {
+  return isIdentifierCharacter(Character) && Character != '.';
+}
+
+[[nodiscard]] constexpr bool isHorizontalWhitespace(char Character) noexcept {
+  return Character == ' ' || Character == '\t';
+}
+
+[[nodiscard]] constexpr bool isNewlineCharacter(char Character) noexcept {
+  return Character == '\n' || Character == '\r';
+}
+
+[[nodiscard]] constexpr bool isHexFloatingPointPrefix(char Character) noexcept {
+  return Character == 'H' || Character == 'K' || Character == 'L' || Character == 'M' ||
+         Character == 'R';
+}
+
+[[nodiscard]] std::string unexpectedCharacterMessage(unsigned char Character) {
+  if (Character >= 0x20U && Character <= 0x7EU) {
+    return "unexpected character '" + std::string(1, static_cast<char>(Character)) + "'";
+  }
+  std::ostringstream Message;
+  Message << "unexpected byte 0x" << std::uppercase << std::hex << std::setw(2) << std::setfill('0')
+          << static_cast<unsigned>(Character);
+  return Message.str();
+}
+
+} // namespace
+
+std::string_view getMITokenKindName(MITokenKind Kind) noexcept {
+  switch (Kind) {
+  case MITokenKind::EndOfFile:
+    return "end-of-file";
+  case MITokenKind::Error:
+    return "error";
+  case MITokenKind::Newline:
+    return "newline";
+  case MITokenKind::Comma:
+    return "comma";
+  case MITokenKind::Equal:
+    return "equal";
+  case MITokenKind::Underscore:
+    return "underscore";
+  case MITokenKind::Colon:
+    return "colon";
+  case MITokenKind::DoubleColon:
+    return "double-colon";
+  case MITokenKind::Dot:
+    return "dot";
+  case MITokenKind::Exclaim:
+    return "exclaim";
+  case MITokenKind::LeftParen:
+    return "left-paren";
+  case MITokenKind::RightParen:
+    return "right-paren";
+  case MITokenKind::LeftBrace:
+    return "left-brace";
+  case MITokenKind::RightBrace:
+    return "right-brace";
+  case MITokenKind::Plus:
+    return "plus";
+  case MITokenKind::Minus:
+    return "minus";
+  case MITokenKind::Less:
+    return "less";
+  case MITokenKind::Greater:
+    return "greater";
+  case MITokenKind::Keyword:
+    return "keyword";
+  case MITokenKind::MetadataKeyword:
+    return "metadata-keyword";
+  case MITokenKind::Identifier:
+    return "identifier";
+  case MITokenKind::NamedRegister:
+    return "named-register";
+  case MITokenKind::NamedVirtualRegister:
+    return "named-virtual-register";
+  case MITokenKind::MachineBasicBlockLabel:
+    return "machine-basic-block-label";
+  case MITokenKind::MachineBasicBlock:
+    return "machine-basic-block";
+  case MITokenKind::StackObject:
+    return "stack-object";
+  case MITokenKind::FixedStackObject:
+    return "fixed-stack-object";
+  case MITokenKind::NamedGlobalValue:
+    return "named-global-value";
+  case MITokenKind::GlobalValue:
+    return "global-value";
+  case MITokenKind::ExternalSymbol:
+    return "external-symbol";
+  case MITokenKind::MCSymbol:
+    return "mc-symbol";
+  case MITokenKind::IntegerLiteral:
+    return "integer-literal";
+  case MITokenKind::FloatingPointLiteral:
+    return "floating-point-literal";
+  case MITokenKind::HexLiteral:
+    return "hex-literal";
+  case MITokenKind::VirtualRegister:
+    return "virtual-register";
+  case MITokenKind::ConstantPoolItem:
+    return "constant-pool-item";
+  case MITokenKind::JumpTableIndex:
+    return "jump-table-index";
+  case MITokenKind::NamedIRBlock:
+    return "named-ir-block";
+  case MITokenKind::IRBlock:
+    return "ir-block";
+  case MITokenKind::NamedIRValue:
+    return "named-ir-value";
+  case MITokenKind::IRValue:
+    return "ir-value";
+  case MITokenKind::QuotedIRValue:
+    return "quoted-ir-value";
+  case MITokenKind::SubRegisterIndex:
+    return "subregister-index";
+  case MITokenKind::StringConstant:
+    return "string-constant";
+  }
+  return "unknown";
+}
+
+bool isMIKeyword(std::string_view Spelling) noexcept {
+  return std::ranges::binary_search(Keywords, Spelling);
+}
+
+bool isMIMetadataKeyword(std::string_view Spelling) noexcept {
+  return std::ranges::binary_search(MetadataKeywords, Spelling);
+}
+
+std::string_view MIToken::stringValue() const noexcept {
+  if (const auto *View = std::get_if<std::string_view>(&StringValue))
+    return *View;
+  if (const auto *Owned = std::get_if<std::string>(&StringValue))
+    return *Owned;
+  return {};
+}
+
+bool MIToken::isRegister() const noexcept {
+  return Kind == MITokenKind::NamedRegister || Kind == MITokenKind::NamedVirtualRegister ||
+         Kind == MITokenKind::VirtualRegister || Kind == MITokenKind::Underscore;
+}
+
+bool MIToken::isRegisterFlag() const noexcept {
+  return isKeyword("implicit") || isKeyword("implicit-def") || isKeyword("def") ||
+         isKeyword("dead") || isKeyword("killed") || isKeyword("undef") || isKeyword("internal") ||
+         isKeyword("early-clobber") || isKeyword("debug-use") || isKeyword("renamable");
+}
+
+bool MIToken::isMemoryOperandFlag() const noexcept {
+  return isKeyword("volatile") || isKeyword("non-temporal") || isKeyword("dereferenceable") ||
+         isKeyword("invariant") || Kind == MITokenKind::StringConstant;
+}
+
+MIToken MILexer::makeToken(MITokenKind Kind, TextRange Range, std::string_view Spelling,
+                           std::string_view IntegerValue) {
+  return MIToken(Kind, Range, Spelling, {}, IntegerValue);
+}
+
+MIToken MILexer::makeStringToken(MITokenKind Kind, TextRange Range, std::string_view Spelling,
+                                 std::string_view StringValue, std::string_view IntegerValue) {
+  return MIToken(Kind, Range, Spelling, StringValue, IntegerValue);
+}
+
+MIToken MILexer::makeOwnedStringToken(MITokenKind Kind, TextRange Range, std::string_view Spelling,
+                                      std::string StringValue, std::string_view IntegerValue) {
+  return MIToken(Kind, Range, Spelling, std::move(StringValue), IntegerValue);
+}
+
+class MILexer::Impl final {
+public:
+  Impl(std::string SourceName, std::string SourceText, MILexerOptions Options)
+      : Source(std::move(SourceName), std::move(SourceText)), Options(Options) {}
+
+  [[nodiscard]] MIToken next() {
+    if (Failed)
+      return token(MITokenKind::EndOfFile, Offset, Offset);
+
+    if (auto TriviaError = skipTrivia())
+      return std::move(*TriviaError);
+
+    if (atEnd())
+      return token(MITokenKind::EndOfFile, Offset, Offset);
+
+    const std::size_t Begin = Offset;
+    MIToken Result = lexToken();
+    if (Result.kind() == MITokenKind::Error)
+      return Result;
+
+    if (Options.MaximumTokenLength != 0 &&
+        Result.range().End.Offset - Result.range().Begin.Offset > Options.MaximumTokenLength) {
+      return fail(Begin, Offset, "machine instruction token exceeds the configured length limit");
+    }
+    if (Options.MaximumTokens != 0 && TokenCount >= Options.MaximumTokens) {
+      return fail(Begin, Offset, "machine instruction token count exceeds the configured limit");
+    }
+    ++TokenCount;
+    return Result;
+  }
+
+  [[nodiscard]] const TextSource &source() const noexcept {
+    return Source;
+  }
+
+  [[nodiscard]] std::span<const TextDiagnostic> diagnostics() const noexcept {
+    return Diagnostics;
+  }
+
+  [[nodiscard]] bool failed() const noexcept {
+    return Failed;
+  }
+
+  [[nodiscard]] std::size_t tokenCount() const noexcept {
+    return TokenCount;
+  }
+
+private:
+  struct QuotedValue final {
+    std::size_t End = 0;
+    std::string Value;
+  };
+
+  [[nodiscard]] std::string_view text() const noexcept {
+    return Source.text();
+  }
+
+  [[nodiscard]] bool atEnd(std::size_t Lookahead = 0) const noexcept {
+    return Offset >= text().size() || Lookahead >= text().size() - Offset;
+  }
+
+  [[nodiscard]] char peek(std::size_t Lookahead = 0) const noexcept {
+    if (Offset >= text().size() || Lookahead >= text().size() - Offset)
+      return '\0';
+    return text()[Offset + Lookahead];
+  }
+
+  [[nodiscard]] bool startsWith(std::string_view Prefix) const noexcept {
+    return text().substr(Offset).starts_with(Prefix);
+  }
+
+  [[nodiscard]] std::string_view slice(std::size_t Begin, std::size_t End) const noexcept {
+    assert(Begin <= End && End <= text().size());
+    return text().substr(Begin, End - Begin);
+  }
+
+  [[nodiscard]] MIToken token(MITokenKind Kind, std::size_t Begin, std::size_t End,
+                              std::string_view IntegerValue = {}) const {
+    return MILexer::makeToken(Kind, Source.range(Begin, End), slice(Begin, End), IntegerValue);
+  }
+
+  [[nodiscard]] MIToken stringToken(MITokenKind Kind, std::size_t Begin, std::size_t End,
+                                    std::string_view Value,
+                                    std::string_view IntegerValue = {}) const {
+    return MILexer::makeStringToken(Kind, Source.range(Begin, End), slice(Begin, End), Value,
+                                    IntegerValue);
+  }
+
+  [[nodiscard]] MIToken ownedStringToken(MITokenKind Kind, std::size_t Begin, std::size_t End,
+                                         std::string Value,
+                                         std::string_view IntegerValue = {}) const {
+    return MILexer::makeOwnedStringToken(Kind, Source.range(Begin, End), slice(Begin, End),
+                                         std::move(Value), IntegerValue);
+  }
+
+  [[nodiscard]] MIToken fail(std::size_t Begin, std::size_t End, std::string Message) {
+    End = std::clamp(End, Begin, text().size());
+    Diagnostics.push_back(TextDiagnostic{
+        .Severity = DiagnosticSeverity::Error,
+        .Category = "mir-lexer",
+        .Message = std::move(Message),
+        .SourceName = std::string(Source.name()),
+        .Range = Source.range(Begin, End),
+    });
+    Failed = true;
+    return token(MITokenKind::Error, Begin, End);
+  }
+
+  [[nodiscard]] std::optional<MIToken> skipTrivia() {
+    while (true) {
+      while (!atEnd() && isHorizontalWhitespace(peek()))
+        ++Offset;
+
+      if (peek() == ';') {
+        while (!atEnd() && !isNewlineCharacter(peek()))
+          ++Offset;
+        continue;
+      }
+
+      if (!startsWith("/*"))
+        return std::nullopt;
+
+      const std::size_t Begin = Offset;
+      Offset += 2;
+      while (!atEnd() && !startsWith("*/"))
+        ++Offset;
+      if (atEnd()) {
+        return fail(Begin, Offset,
+                    "end of machine instruction input reached before the closing '*/'");
+      }
+      Offset += 2;
+    }
+  }
+
+  [[nodiscard]] std::optional<QuotedValue> scanQuotedString(std::size_t QuoteOffset) {
+    assert(QuoteOffset < text().size() && text()[QuoteOffset] == '"');
+    std::size_t Cursor = QuoteOffset + 1;
+    while (Cursor < text().size() && text()[Cursor] != '"') {
+      if (isNewlineCharacter(text()[Cursor])) {
+        Offset = Cursor;
+        static_cast<void>(fail(QuoteOffset, Cursor,
+                               "end of machine instruction reached before the closing '\"'"));
+        return std::nullopt;
+      }
+      ++Cursor;
+    }
+    if (Cursor == text().size()) {
+      Offset = Cursor;
+      static_cast<void>(
+          fail(QuoteOffset, Cursor, "end of machine instruction reached before the closing '\"'"));
+      return std::nullopt;
+    }
+
+    std::string Value;
+    Value.reserve(Cursor - QuoteOffset - 1);
+    for (std::size_t Index = QuoteOffset + 1; Index < Cursor; ++Index) {
+      const char Character = text()[Index];
+      if (Character == '\\' && Index + 1 < Cursor && text()[Index + 1] == '\\') {
+        Value.push_back('\\');
+        ++Index;
+        continue;
+      }
+      if (Character == '\\' && Index + 2 < Cursor && isASCIIHexDigit(text()[Index + 1]) &&
+          isASCIIHexDigit(text()[Index + 2])) {
+        const unsigned Decoded =
+            hexDigitValue(text()[Index + 1]) * 16U + hexDigitValue(text()[Index + 2]);
+        Value.push_back(static_cast<char>(Decoded));
+        Index += 2;
+        continue;
+      }
+      Value.push_back(Character);
+    }
+    return QuotedValue{.End = Cursor + 1, .Value = std::move(Value)};
+  }
+
+  [[nodiscard]] MIToken lexName(MITokenKind Kind, std::size_t PrefixLength) {
+    const std::size_t Begin = Offset;
+    Offset += PrefixLength;
+    if (peek() == '"') {
+      auto Quoted = scanQuotedString(Offset);
+      if (!Quoted)
+        return token(MITokenKind::Error, Begin, Offset);
+      Offset = Quoted->End;
+      return ownedStringToken(Kind, Begin, Offset, std::move(Quoted->Value));
+    }
+
+    const std::size_t ValueBegin = Offset;
+    while (!atEnd() && isIdentifierCharacter(peek()))
+      ++Offset;
+    return stringToken(Kind, Begin, Offset, slice(ValueBegin, Offset));
+  }
+
+  [[nodiscard]] std::optional<MIToken> lexMachineBasicBlock() {
+    const bool IsReference = startsWith("%bb.");
+    if (!IsReference && !startsWith("bb."))
+      return std::nullopt;
+
+    const std::size_t Begin = Offset;
+    const std::size_t PrefixLength = IsReference ? 4 : 3;
+    Offset += PrefixLength;
+    if (!isASCIIDigit(peek())) {
+      return fail(Offset, std::min(Offset + 1, text().size()),
+                  "expected a decimal block number after '" +
+                      std::string(IsReference ? "%bb.'" : "bb.'"));
+    }
+
+    const std::size_t NumberBegin = Offset;
+    while (!atEnd() && isASCIIDigit(peek()))
+      ++Offset;
+    const std::string_view Number = slice(NumberBegin, Offset);
+
+    std::size_t NameBegin = Offset;
+    if (peek() == '.') {
+      ++Offset;
+      NameBegin = Offset;
+      while (!atEnd() && isIdentifierCharacter(peek()))
+        ++Offset;
+    }
+
+    return stringToken(IsReference ? MITokenKind::MachineBasicBlock
+                                   : MITokenKind::MachineBasicBlockLabel,
+                       Begin, Offset, slice(NameBegin, Offset), Number);
+  }
+
+  [[nodiscard]] std::optional<MIToken> lexIndex(std::string_view Prefix, MITokenKind Kind,
+                                                bool HasOptionalName) {
+    if (!startsWith(Prefix) || !isASCIIDigit(peek(Prefix.size())))
+      return std::nullopt;
+
+    const std::size_t Begin = Offset;
+    Offset += Prefix.size();
+    const std::size_t NumberBegin = Offset;
+    while (!atEnd() && isASCIIDigit(peek()))
+      ++Offset;
+    const std::string_view Number = slice(NumberBegin, Offset);
+
+    if (!HasOptionalName)
+      return token(Kind, Begin, Offset, Number);
+
+    std::size_t NameBegin = Offset;
+    if (peek() == '.') {
+      ++Offset;
+      NameBegin = Offset;
+      while (!atEnd() && isIdentifierCharacter(peek()))
+        ++Offset;
+    }
+    return stringToken(Kind, Begin, Offset, slice(NameBegin, Offset), Number);
+  }
+
+  [[nodiscard]] std::optional<MIToken>
+  lexIRReference(std::string_view Prefix, MITokenKind NumericKind, MITokenKind NamedKind) {
+    if (!startsWith(Prefix))
+      return std::nullopt;
+    if (isASCIIDigit(peek(Prefix.size())))
+      return lexIndex(Prefix, NumericKind, false);
+    return lexName(NamedKind, Prefix.size());
+  }
+
+  [[nodiscard]] std::optional<MIToken> lexRegister() {
+    if (peek() != '%' && peek() != '$')
+      return std::nullopt;
+
+    const std::size_t Begin = Offset;
+    const char Prefix = peek();
+    ++Offset;
+    if (Prefix == '%' && isASCIIDigit(peek())) {
+      const std::size_t NumberBegin = Offset;
+      while (!atEnd() && isASCIIDigit(peek()))
+        ++Offset;
+      return token(MITokenKind::VirtualRegister, Begin, Offset, slice(NumberBegin, Offset));
+    }
+
+    if (Prefix == '%' && !isRegisterCharacter(peek())) {
+      Offset = Begin;
+      return std::nullopt;
+    }
+
+    const std::size_t NameBegin = Offset;
+    while (!atEnd() && isRegisterCharacter(peek()))
+      ++Offset;
+    return stringToken(Prefix == '%' ? MITokenKind::NamedVirtualRegister
+                                     : MITokenKind::NamedRegister,
+                       Begin, Offset, slice(NameBegin, Offset));
+  }
+
+  [[nodiscard]] std::optional<MIToken> lexGlobalValue() {
+    if (peek() != '@')
+      return std::nullopt;
+    if (!isASCIIDigit(peek(1)))
+      return lexName(MITokenKind::NamedGlobalValue, 1);
+
+    const std::size_t Begin = Offset++;
+    const std::size_t NumberBegin = Offset;
+    while (!atEnd() && isASCIIDigit(peek()))
+      ++Offset;
+    return token(MITokenKind::GlobalValue, Begin, Offset, slice(NumberBegin, Offset));
+  }
+
+  [[nodiscard]] std::optional<MIToken> lexMCSymbol() {
+    constexpr std::string_view Prefix = "<mcsymbol ";
+    if (!startsWith(Prefix))
+      return std::nullopt;
+
+    const std::size_t Begin = Offset;
+    Offset += Prefix.size();
+    if (peek() != '"') {
+      const std::size_t NameBegin = Offset;
+      while (!atEnd() && isIdentifierCharacter(peek()))
+        ++Offset;
+      const std::string_view Name = slice(NameBegin, Offset);
+      if (peek() != '>') {
+        return fail(Begin, Offset, "expected the '<mcsymbol ...' operand to be closed by '>'");
+      }
+      ++Offset;
+      return stringToken(MITokenKind::MCSymbol, Begin, Offset, Name);
+    }
+
+    auto Quoted = scanQuotedString(Offset);
+    if (!Quoted)
+      return token(MITokenKind::Error, Begin, Offset);
+    Offset = Quoted->End;
+    if (peek() != '>') {
+      return fail(Begin, Offset, "expected the '<mcsymbol ...' operand to be closed by '>'");
+    }
+    ++Offset;
+    return ownedStringToken(MITokenKind::MCSymbol, Begin, Offset, std::move(Quoted->Value));
+  }
+
+  [[nodiscard]] std::optional<MIToken> lexFloatHexBits() {
+    if (!startsWith("f0x") && !startsWith("f0X"))
+      return std::nullopt;
+    std::size_t End = Offset + 3;
+    while (End < text().size() && isASCIIHexDigit(text()[End]))
+      ++End;
+    if (End == Offset + 3)
+      return std::nullopt;
+    const std::size_t Begin = Offset;
+    Offset = End;
+    return token(MITokenKind::FloatingPointLiteral, Begin, Offset);
+  }
+
+  [[nodiscard]] std::optional<MIToken> lexHexadecimalLiteral() {
+    if (peek() != '0' || (peek(1) != 'x' && peek(1) != 'X'))
+      return std::nullopt;
+
+    std::size_t End = Offset + 2;
+    bool IsFloatingPoint = false;
+    if (End < text().size() && isHexFloatingPointPrefix(text()[End])) {
+      IsFloatingPoint = true;
+      ++End;
+    }
+    const std::size_t DigitsBegin = End;
+    while (End < text().size() && isASCIIHexDigit(text()[End]))
+      ++End;
+    if (End == DigitsBegin)
+      return std::nullopt;
+
+    const std::size_t Begin = Offset;
+    Offset = End;
+    return token(IsFloatingPoint ? MITokenKind::FloatingPointLiteral : MITokenKind::HexLiteral,
+                 Begin, Offset);
+  }
+
+  [[nodiscard]] std::optional<MIToken> lexNumericalLiteral() {
+    if (!isASCIIDigit(peek()) && (peek() != '-' || !isASCIIDigit(peek(1)))) {
+      return std::nullopt;
+    }
+
+    const std::size_t Begin = Offset;
+    if (peek() == '-')
+      ++Offset;
+    while (!atEnd() && isASCIIDigit(peek()))
+      ++Offset;
+
+    if (peek() != '.') {
+      return token(MITokenKind::IntegerLiteral, Begin, Offset, slice(Begin, Offset));
+    }
+
+    ++Offset;
+    while (!atEnd() && isASCIIDigit(peek()))
+      ++Offset;
+    if ((peek() == 'e' || peek() == 'E') &&
+        (isASCIIDigit(peek(1)) || ((peek(1) == '-' || peek(1) == '+') && isASCIIDigit(peek(2))))) {
+      ++Offset;
+      if (peek() == '-' || peek() == '+')
+        ++Offset;
+      while (!atEnd() && isASCIIDigit(peek()))
+        ++Offset;
+    }
+    return token(MITokenKind::FloatingPointLiteral, Begin, Offset);
+  }
+
+  [[nodiscard]] std::optional<MIToken> lexExclaim() {
+    if (peek() != '!')
+      return std::nullopt;
+
+    const std::size_t Begin = Offset++;
+    if (isASCIIDigit(peek()) || !isIdentifierCharacter(peek()))
+      return token(MITokenKind::Exclaim, Begin, Offset);
+
+    while (!atEnd() && isIdentifierCharacter(peek()))
+      ++Offset;
+    const std::string_view Spelling = slice(Begin, Offset);
+    if (!isMIMetadataKeyword(Spelling)) {
+      return fail(Begin, Offset, "use of unknown metadata keyword '" + std::string(Spelling) + "'");
+    }
+    return stringToken(MITokenKind::MetadataKeyword, Begin, Offset, Spelling);
+  }
+
+  [[nodiscard]] std::optional<MIToken> lexSymbol() {
+    const std::size_t Begin = Offset;
+    if (startsWith("::")) {
+      Offset += 2;
+      return token(MITokenKind::DoubleColon, Begin, Offset);
+    }
+
+    MITokenKind Kind = MITokenKind::Error;
+    switch (peek()) {
+    case ',':
+      Kind = MITokenKind::Comma;
+      break;
+    case '=':
+      Kind = MITokenKind::Equal;
+      break;
+    case ':':
+      Kind = MITokenKind::Colon;
+      break;
+    case '.':
+      Kind = MITokenKind::Dot;
+      break;
+    case '(':
+      Kind = MITokenKind::LeftParen;
+      break;
+    case ')':
+      Kind = MITokenKind::RightParen;
+      break;
+    case '{':
+      Kind = MITokenKind::LeftBrace;
+      break;
+    case '}':
+      Kind = MITokenKind::RightBrace;
+      break;
+    case '+':
+      Kind = MITokenKind::Plus;
+      break;
+    case '-':
+      Kind = MITokenKind::Minus;
+      break;
+    case '<':
+      Kind = MITokenKind::Less;
+      break;
+    case '>':
+      Kind = MITokenKind::Greater;
+      break;
+    default:
+      return std::nullopt;
+    }
+    ++Offset;
+    return token(Kind, Begin, Offset);
+  }
+
+  [[nodiscard]] std::optional<MIToken> lexNewline() {
+    if (!isNewlineCharacter(peek()))
+      return std::nullopt;
+    const std::size_t Begin = Offset++;
+    if (text()[Begin] == '\r' && peek() == '\n')
+      ++Offset;
+    return token(MITokenKind::Newline, Begin, Offset);
+  }
+
+  [[nodiscard]] std::optional<MIToken> lexQuotedIRValue() {
+    if (peek() != '`')
+      return std::nullopt;
+
+    const std::size_t Begin = Offset++;
+    const std::size_t ValueBegin = Offset;
+    while (!atEnd() && peek() != '`' && !isNewlineCharacter(peek()))
+      ++Offset;
+    if (atEnd() || isNewlineCharacter(peek())) {
+      return fail(Begin, Offset, "end of machine instruction reached before the closing '`'");
+    }
+    const std::size_t ValueEnd = Offset++;
+    return stringToken(MITokenKind::QuotedIRValue, Begin, Offset, slice(ValueBegin, ValueEnd));
+  }
+
+  [[nodiscard]] MIToken lexToken() {
+    if (auto Result = lexMachineBasicBlock())
+      return std::move(*Result);
+    if (auto Result = lexFloatHexBits())
+      return std::move(*Result);
+
+    if (isASCIIAlpha(peek()) || peek() == '_') {
+      const std::size_t Begin = Offset;
+      while (!atEnd() && isIdentifierCharacter(peek()))
+        ++Offset;
+      const std::string_view Value = slice(Begin, Offset);
+      if (Value == "_")
+        return token(MITokenKind::Underscore, Begin, Offset);
+      return stringToken(isMIKeyword(Value) ? MITokenKind::Keyword : MITokenKind::Identifier, Begin,
+                         Offset, Value);
+    }
+
+    if (auto Result = lexIndex("%jump-table.", MITokenKind::JumpTableIndex, false))
+      return std::move(*Result);
+    if (auto Result = lexIndex("%stack.", MITokenKind::StackObject, true))
+      return std::move(*Result);
+    if (auto Result = lexIndex("%fixed-stack.", MITokenKind::FixedStackObject, false))
+      return std::move(*Result);
+    if (auto Result = lexIndex("%const.", MITokenKind::ConstantPoolItem, false))
+      return std::move(*Result);
+    if (startsWith("%subreg."))
+      return lexName(MITokenKind::SubRegisterIndex, 8);
+    if (auto Result = lexIRReference("%ir-block.", MITokenKind::IRBlock, MITokenKind::NamedIRBlock))
+      return std::move(*Result);
+    if (auto Result = lexIRReference("%ir.", MITokenKind::IRValue, MITokenKind::NamedIRValue))
+      return std::move(*Result);
+    if (auto Result = lexRegister())
+      return std::move(*Result);
+    if (auto Result = lexGlobalValue())
+      return std::move(*Result);
+    if (peek() == '&')
+      return lexName(MITokenKind::ExternalSymbol, 1);
+    if (auto Result = lexMCSymbol())
+      return std::move(*Result);
+    if (auto Result = lexHexadecimalLiteral())
+      return std::move(*Result);
+    if (auto Result = lexNumericalLiteral())
+      return std::move(*Result);
+    if (auto Result = lexExclaim())
+      return std::move(*Result);
+    if (auto Result = lexSymbol())
+      return std::move(*Result);
+    if (auto Result = lexNewline())
+      return std::move(*Result);
+    if (auto Result = lexQuotedIRValue())
+      return std::move(*Result);
+    if (peek() == '"')
+      return lexName(MITokenKind::StringConstant, 0);
+
+    const std::size_t Begin = Offset++;
+    return fail(Begin, Offset,
+                unexpectedCharacterMessage(static_cast<unsigned char>(text()[Begin])));
+  }
+
+  TextSource Source;
+  MILexerOptions Options;
+  std::size_t Offset = 0;
+  std::size_t TokenCount = 0;
+  bool Failed = false;
+  std::vector<TextDiagnostic> Diagnostics;
+};
+
+MILexer::MILexer(std::string SourceName, std::string SourceText, MILexerOptions Options)
+    : Implementation(
+          std::make_unique<Impl>(std::move(SourceName), std::move(SourceText), Options)) {}
+
+MILexer::MILexer(MILexer &&) noexcept = default;
+MILexer &MILexer::operator=(MILexer &&) noexcept = default;
+MILexer::~MILexer() = default;
+
+MIToken MILexer::next() {
+  assert(Implementation != nullptr);
+  return Implementation->next();
+}
+
+const TextSource &MILexer::source() const noexcept {
+  assert(Implementation != nullptr);
+  return Implementation->source();
+}
+
+std::span<const TextDiagnostic> MILexer::diagnostics() const noexcept {
+  assert(Implementation != nullptr);
+  return Implementation->diagnostics();
+}
+
+bool MILexer::failed() const noexcept {
+  assert(Implementation != nullptr);
+  return Implementation->failed();
+}
+
+std::size_t MILexer::tokenCount() const noexcept {
+  assert(Implementation != nullptr);
+  return Implementation->tokenCount();
+}
+
+} // namespace rcc::mir
diff --git a/backend/unittests/MIR/CMakeLists.txt b/backend/unittests/MIR/CMakeLists.txt
index 7a60ba2..bff2c99 100644
--- a/backend/unittests/MIR/CMakeLists.txt
+++ b/backend/unittests/MIR/CMakeLists.txt
@@ -6,5 +6,17 @@ target_link_libraries(RCCBackendEmbeddedIRTests PRIVATE RCCBackend::MIR)
 
 add_test(NAME RCCBackend.MIR.EmbeddedIR COMMAND RCCBackendEmbeddedIRTests)
 
-rcc_backend_register_format_files("${CMAKE_CURRENT_SOURCE_DIR}/EmbeddedIRTest.cpp")
-rcc_backend_register_tidy_files("${CMAKE_CURRENT_SOURCE_DIR}/EmbeddedIRTest.cpp")
+add_executable(RCCBackendMILexerTests MILexerTest.cpp)
+rcc_backend_configure_target(RCCBackendMILexerTests)
+target_link_libraries(RCCBackendMILexerTests PRIVATE RCCBackend::MIR)
+
+add_test(NAME RCCBackend.MIR.MILexer COMMAND RCCBackendMILexerTests)
+
+rcc_backend_register_format_files(
+  "${CMAKE_CURRENT_SOURCE_DIR}/EmbeddedIRTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MILexerTest.cpp"
+)
+rcc_backend_register_tidy_files(
+  "${CMAKE_CURRENT_SOURCE_DIR}/EmbeddedIRTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MILexerTest.cpp"
+)
diff --git a/backend/unittests/MIR/MILexerTest.cpp b/backend/unittests/MIR/MILexerTest.cpp
new file mode 100644
index 0000000..a130eb0
--- /dev/null
+++ b/backend/unittests/MIR/MILexerTest.cpp
@@ -0,0 +1,417 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/MIR/MILexer.h"
+
+#include "rcc/Support/TextDiagnostic.h"
+
+#include <array>
+#include <cstddef>
+#include <iostream>
+#include <optional>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <vector>
+
+namespace {
+
+class TestContext final {
+public:
+  void expect(bool Condition, std::string_view Message) {
+    if (Condition)
+      return;
+    std::cerr << Message << '\n';
+    ++FailureCount;
+  }
+
+  [[nodiscard]] int result() const noexcept {
+    return FailureCount == 0 ? 0 : 1;
+  }
+
+private:
+  int FailureCount = 0;
+};
+
+using rcc::mir::MITokenKind;
+
+struct ExpectedToken final {
+  MITokenKind Kind;
+  std::string_view Spelling;
+  std::optional<std::string_view> StringValue;
+  std::optional<std::string_view> IntegerValue;
+};
+
+void expectToken(TestContext &Context, rcc::mir::MILexer &Lexer, const ExpectedToken &Expected) {
+  const rcc::mir::MIToken Token = Lexer.next();
+  Context.expect(Token.kind() == Expected.Kind && Token.spelling() == Expected.Spelling,
+                 "MI token kind and spelling must match the fixed grammar");
+  Context.expect(Token.hasStringValue() == Expected.StringValue.has_value() &&
+                     (!Expected.StringValue || Token.stringValue() == *Expected.StringValue),
+                 "MI token string payload must be exact");
+  Context.expect(Token.hasIntegerValue() == Expected.IntegerValue.has_value() &&
+                     (!Expected.IntegerValue || Token.integerValue() == *Expected.IntegerValue),
+                 "MI token integer spelling must remain exact");
+}
+
+void expectEnd(TestContext &Context, rcc::mir::MILexer &Lexer) {
+  const rcc::mir::MIToken Token = Lexer.next();
+  Context.expect(Token.kind() == MITokenKind::EndOfFile && Token.spelling().empty(),
+                 "MI lexer must terminate with an empty end-of-file token");
+}
+
+void testPunctuationAndTrivia(TestContext &Context) {
+  rcc::mir::MILexer Lexer("punctuation.mir",
+                          " \t; line comment\r\n/* first */ /* second\ncomment */ , = _ : :: . ! "
+                          "( ) { } + - < >");
+
+  const std::array Expected{
+      ExpectedToken{MITokenKind::Newline, "\r\n", std::nullopt, std::nullopt},
+      ExpectedToken{MITokenKind::Comma, ",", std::nullopt, std::nullopt},
+      ExpectedToken{MITokenKind::Equal, "=", std::nullopt, std::nullopt},
+      ExpectedToken{MITokenKind::Underscore, "_", std::nullopt, std::nullopt},
+      ExpectedToken{MITokenKind::Colon, ":", std::nullopt, std::nullopt},
+      ExpectedToken{MITokenKind::DoubleColon, "::", std::nullopt, std::nullopt},
+      ExpectedToken{MITokenKind::Dot, ".", std::nullopt, std::nullopt},
+      ExpectedToken{MITokenKind::Exclaim, "!", std::nullopt, std::nullopt},
+      ExpectedToken{MITokenKind::LeftParen, "(", std::nullopt, std::nullopt},
+      ExpectedToken{MITokenKind::RightParen, ")", std::nullopt, std::nullopt},
+      ExpectedToken{MITokenKind::LeftBrace, "{", std::nullopt, std::nullopt},
+      ExpectedToken{MITokenKind::RightBrace, "}", std::nullopt, std::nullopt},
+      ExpectedToken{MITokenKind::Plus, "+", std::nullopt, std::nullopt},
+      ExpectedToken{MITokenKind::Minus, "-", std::nullopt, std::nullopt},
+      ExpectedToken{MITokenKind::Less, "<", std::nullopt, std::nullopt},
+      ExpectedToken{MITokenKind::Greater, ">", std::nullopt, std::nullopt},
+  };
+  for (const ExpectedToken &Token : Expected)
+    expectToken(Context, Lexer, Token);
+  expectEnd(Context, Lexer);
+
+  Context.expect(!Lexer.failed() && Lexer.diagnostics().empty() &&
+                     Lexer.tokenCount() == Expected.size(),
+                 "whitespace and both MIR comment forms must not create tokens");
+}
+
+void testKeywordCorpus(TestContext &Context) {
+  // Compatibility corpus from llvm/lib/CodeGen/MIRParser/MILexer.cpp at
+  // 2b40c303e79f64c5c7642032554eda026594d604.
+  constexpr std::array Keywords{
+      std::string_view{"implicit"},
+      std::string_view{"implicit-def"},
+      std::string_view{"def"},
+      std::string_view{"dead"},
+      std::string_view{"killed"},
+      std::string_view{"undef"},
+      std::string_view{"internal"},
+      std::string_view{"early-clobber"},
+      std::string_view{"debug-use"},
+      std::string_view{"renamable"},
+      std::string_view{"tied-def"},
+      std::string_view{"frame-setup"},
+      std::string_view{"frame-destroy"},
+      std::string_view{"nnan"},
+      std::string_view{"ninf"},
+      std::string_view{"nsz"},
+      std::string_view{"arcp"},
+      std::string_view{"contract"},
+      std::string_view{"afn"},
+      std::string_view{"reassoc"},
+      std::string_view{"nuw"},
+      std::string_view{"nsw"},
+      std::string_view{"nusw"},
+      std::string_view{"exact"},
+      std::string_view{"nneg"},
+      std::string_view{"disjoint"},
+      std::string_view{"samesign"},
+      std::string_view{"inbounds"},
+      std::string_view{"nofpexcept"},
+      std::string_view{"unpredictable"},
+      std::string_view{"debug-location"},
+      std::string_view{"debug-instr-number"},
+      std::string_view{"dbg-instr-ref"},
+      std::string_view{"same_value"},
+      std::string_view{"offset"},
+      std::string_view{"rel_offset"},
+      std::string_view{"def_cfa_register"},
+      std::string_view{"def_cfa_offset"},
+      std::string_view{"adjust_cfa_offset"},
+      std::string_view{"escape"},
+      std::string_view{"def_cfa"},
+      std::string_view{"llvm_def_aspace_cfa"},
+      std::string_view{"remember_state"},
+      std::string_view{"restore"},
+      std::string_view{"restore_state"},
+      std::string_view{"undefined"},
+      std::string_view{"register"},
+      std::string_view{"window_save"},
+      std::string_view{"negate_ra_sign_state"},
+      std::string_view{"negate_ra_sign_state_with_pc"},
+      std::string_view{"llvm_register_pair"},
+      std::string_view{"llvm_vector_registers"},
+      std::string_view{"llvm_vector_offset"},
+      std::string_view{"llvm_vector_register_mask"},
+      std::string_view{"blockaddress"},
+      std::string_view{"intrinsic"},
+      std::string_view{"target-index"},
+      std::string_view{"half"},
+      std::string_view{"bfloat"},
+      std::string_view{"float"},
+      std::string_view{"double"},
+      std::string_view{"x86_fp80"},
+      std::string_view{"fp128"},
+      std::string_view{"ppc_fp128"},
+      std::string_view{"target-flags"},
+      std::string_view{"volatile"},
+      std::string_view{"non-temporal"},
+      std::string_view{"dereferenceable"},
+      std::string_view{"invariant"},
+      std::string_view{"align"},
+      std::string_view{"basealign"},
+      std::string_view{"addrspace"},
+      std::string_view{"stack"},
+      std::string_view{"got"},
+      std::string_view{"jump-table"},
+      std::string_view{"constant-pool"},
+      std::string_view{"call-entry"},
+      std::string_view{"custom"},
+      std::string_view{"lanemask"},
+      std::string_view{"liveout"},
+      std::string_view{"landing-pad"},
+      std::string_view{"inlineasm-br-indirect-target"},
+      std::string_view{"ehscope-entry"},
+      std::string_view{"ehfunclet-entry"},
+      std::string_view{"liveins"},
+      std::string_view{"successors"},
+      std::string_view{"floatpred"},
+      std::string_view{"intpred"},
+      std::string_view{"shufflemask"},
+      std::string_view{"pre-instr-symbol"},
+      std::string_view{"post-instr-symbol"},
+      std::string_view{"heap-alloc-marker"},
+      std::string_view{"pcsections"},
+      std::string_view{"cfi-type"},
+      std::string_view{"deactivation-symbol"},
+      std::string_view{"bbsections"},
+      std::string_view{"bb_id"},
+      std::string_view{"unknown-size"},
+      std::string_view{"unknown-address"},
+      std::string_view{"distinct"},
+      std::string_view{"ir-block-address-taken"},
+      std::string_view{"machine-block-address-taken"},
+      std::string_view{"call-frame-size"},
+      std::string_view{"noconvergent"},
+      std::string_view{"mmra"},
+  };
+
+  std::string Source;
+  for (const std::string_view Keyword : Keywords) {
+    Source += Keyword;
+    Source.push_back(' ');
+  }
+  Source += "TEST_OPCODE keyword-like";
+
+  rcc::mir::MILexer Lexer("keywords.mir", std::move(Source));
+  for (const std::string_view Keyword : Keywords) {
+    const rcc::mir::MIToken Token = Lexer.next();
+    Context.expect(Token.kind() == MITokenKind::Keyword && Token.stringValue() == Keyword &&
+                       rcc::mir::isMIKeyword(Keyword),
+                   "every fixed LLVM MIR keyword must be reserved");
+  }
+  expectToken(Context, Lexer,
+              {MITokenKind::Identifier, "TEST_OPCODE", "TEST_OPCODE", std::nullopt});
+  expectToken(Context, Lexer,
+              {MITokenKind::Identifier, "keyword-like", "keyword-like", std::nullopt});
+  expectEnd(Context, Lexer);
+  Context.expect(!rcc::mir::isMIKeyword("Implicit") && !rcc::mir::isMIKeyword("unknown-keyword"),
+                 "MIR keyword classification must remain case-sensitive");
+}
+
+void testMetadataKeywords(TestContext &Context) {
+  constexpr std::array Keywords{
+      std::string_view{"!tbaa"},       std::string_view{"!alias.scope"},
+      std::string_view{"!noalias"},    std::string_view{"!noalias.addrspace"},
+      std::string_view{"!range"},      std::string_view{"!DIExpression"},
+      std::string_view{"!DILocation"},
+  };
+  std::string Source;
+  for (const std::string_view Keyword : Keywords) {
+    Source += Keyword;
+    Source.push_back(' ');
+  }
+  Source += "! !12";
+
+  rcc::mir::MILexer Lexer("metadata.mir", std::move(Source));
+  for (const std::string_view Keyword : Keywords) {
+    const rcc::mir::MIToken Token = Lexer.next();
+    Context.expect(Token.kind() == MITokenKind::MetadataKeyword && Token.stringValue() == Keyword &&
+                       rcc::mir::isMIMetadataKeyword(Keyword),
+                   "every fixed named metadata token must be recognized");
+  }
+  expectToken(Context, Lexer, {MITokenKind::Exclaim, "!", std::nullopt, std::nullopt});
+  expectToken(Context, Lexer, {MITokenKind::Exclaim, "!", std::nullopt, std::nullopt});
+  expectToken(Context, Lexer, {MITokenKind::IntegerLiteral, "12", std::nullopt, "12"});
+  expectEnd(Context, Lexer);
+}
+
+void testNamedEntities(TestContext &Context) {
+  rcc::mir::MILexer Lexer("entities.mir",
+                          R"(bb.12.entry %bb.13.exit %jump-table.2 %stack.3.slot )"
+                          R"(%fixed-stack.4 %const.5 %subreg.low32 %ir-block.7 )"
+                          R"(%ir-block."quoted\20block" %ir.8 %ir.named %12 %named-vreg $x0 )"
+                          R"(@9 @global @"quoted\20global" &external &"quoted\20external" )"
+                          R"(<mcsymbol local.label> <mcsymbol "quoted\20symbol"> `i32 7` )"
+                          R"("plain\20string\\tail")");
+
+  const std::array Expected{
+      ExpectedToken{MITokenKind::MachineBasicBlockLabel, "bb.12.entry", "entry", "12"},
+      ExpectedToken{MITokenKind::MachineBasicBlock, "%bb.13.exit", "exit", "13"},
+      ExpectedToken{MITokenKind::JumpTableIndex, "%jump-table.2", std::nullopt, "2"},
+      ExpectedToken{MITokenKind::StackObject, "%stack.3.slot", "slot", "3"},
+      ExpectedToken{MITokenKind::FixedStackObject, "%fixed-stack.4", std::nullopt, "4"},
+      ExpectedToken{MITokenKind::ConstantPoolItem, "%const.5", std::nullopt, "5"},
+      ExpectedToken{MITokenKind::SubRegisterIndex, "%subreg.low32", "low32", std::nullopt},
+      ExpectedToken{MITokenKind::IRBlock, "%ir-block.7", std::nullopt, "7"},
+      ExpectedToken{MITokenKind::NamedIRBlock, R"(%ir-block."quoted\20block")", "quoted block",
+                    std::nullopt},
+      ExpectedToken{MITokenKind::IRValue, "%ir.8", std::nullopt, "8"},
+      ExpectedToken{MITokenKind::NamedIRValue, "%ir.named", "named", std::nullopt},
+      ExpectedToken{MITokenKind::VirtualRegister, "%12", std::nullopt, "12"},
+      ExpectedToken{MITokenKind::NamedVirtualRegister, "%named-vreg", "named-vreg", std::nullopt},
+      ExpectedToken{MITokenKind::NamedRegister, "$x0", "x0", std::nullopt},
+      ExpectedToken{MITokenKind::GlobalValue, "@9", std::nullopt, "9"},
+      ExpectedToken{MITokenKind::NamedGlobalValue, "@global", "global", std::nullopt},
+      ExpectedToken{MITokenKind::NamedGlobalValue, R"(@"quoted\20global")", "quoted global",
+                    std::nullopt},
+      ExpectedToken{MITokenKind::ExternalSymbol, "&external", "external", std::nullopt},
+      ExpectedToken{MITokenKind::ExternalSymbol, R"(&"quoted\20external")", "quoted external",
+                    std::nullopt},
+      ExpectedToken{MITokenKind::MCSymbol, "<mcsymbol local.label>", "local.label", std::nullopt},
+      ExpectedToken{MITokenKind::MCSymbol, R"(<mcsymbol "quoted\20symbol">)", "quoted symbol",
+                    std::nullopt},
+      ExpectedToken{MITokenKind::QuotedIRValue, "`i32 7`", "i32 7", std::nullopt},
+      ExpectedToken{MITokenKind::StringConstant, R"("plain\20string\\tail")",
+                    R"(plain string\tail)", std::nullopt},
+  };
+  for (const ExpectedToken &Token : Expected)
+    expectToken(Context, Lexer, Token);
+  expectEnd(Context, Lexer);
+  Context.expect(!Lexer.failed() && Lexer.diagnostics().empty(),
+                 "all fixed named MIR entity forms must lex without diagnostics");
+}
+
+void testNumericalLiterals(TestContext &Context) {
+  rcc::mir::MILexer Lexer("numbers.mir", "-42 17 1. 1.25 -2.5e-3 6.02E23 0xFF 0XK3FFF000000000000 "
+                                         "f0x3F800000 1e3 0x f0x");
+
+  const std::array Expected{
+      ExpectedToken{MITokenKind::IntegerLiteral, "-42", std::nullopt, "-42"},
+      ExpectedToken{MITokenKind::IntegerLiteral, "17", std::nullopt, "17"},
+      ExpectedToken{MITokenKind::FloatingPointLiteral, "1.", std::nullopt, std::nullopt},
+      ExpectedToken{MITokenKind::FloatingPointLiteral, "1.25", std::nullopt, std::nullopt},
+      ExpectedToken{MITokenKind::FloatingPointLiteral, "-2.5e-3", std::nullopt, std::nullopt},
+      ExpectedToken{MITokenKind::FloatingPointLiteral, "6.02E23", std::nullopt, std::nullopt},
+      ExpectedToken{MITokenKind::HexLiteral, "0xFF", std::nullopt, std::nullopt},
+      ExpectedToken{MITokenKind::FloatingPointLiteral, "0XK3FFF000000000000", std::nullopt,
+                    std::nullopt},
+      ExpectedToken{MITokenKind::FloatingPointLiteral, "f0x3F800000", std::nullopt, std::nullopt},
+      ExpectedToken{MITokenKind::IntegerLiteral, "1", std::nullopt, "1"},
+      ExpectedToken{MITokenKind::Identifier, "e3", "e3", std::nullopt},
+      ExpectedToken{MITokenKind::IntegerLiteral, "0", std::nullopt, "0"},
+      ExpectedToken{MITokenKind::Identifier, "x", "x", std::nullopt},
+      ExpectedToken{MITokenKind::Identifier, "f0x", "f0x", std::nullopt},
+  };
+  for (const ExpectedToken &Token : Expected)
+    expectToken(Context, Lexer, Token);
+  expectEnd(Context, Lexer);
+
+  std::string LargeNumber(10000, '9');
+  rcc::mir::MILexer LargeLexer("large-number.mir", LargeNumber);
+  const rcc::mir::MIToken LargeToken = LargeLexer.next();
+  Context.expect(LargeToken.kind() == MITokenKind::IntegerLiteral &&
+                     LargeToken.integerValue() == LargeNumber,
+                 "integer tokenization must preserve arbitrary-width decimal spelling");
+}
+
+void expectSingleError(TestContext &Context, std::string Source, std::string_view MessageFragment,
+                       rcc::mir::MILexerOptions Options = {}) {
+  rcc::mir::MILexer Lexer("invalid.mir", std::move(Source), Options);
+  const rcc::mir::MIToken Token = Lexer.next();
+  Context.expect(Token.kind() == MITokenKind::Error && Lexer.failed() &&
+                     Lexer.diagnostics().size() == 1 &&
+                     Lexer.diagnostics().front().Category == "mir-lexer" &&
+                     Lexer.diagnostics().front().Message.find(MessageFragment) != std::string::npos,
+                 "invalid MI input must produce one structured lexer diagnostic");
+  expectEnd(Context, Lexer);
+  Context.expect(Lexer.diagnostics().size() == 1,
+                 "reading after an MI lexer failure must not duplicate diagnostics");
+}
+
+void testDiagnosticsAndLimits(TestContext &Context) {
+  expectSingleError(Context, "/* never closed", "closing '*/'");
+  expectSingleError(Context, R"("never closed)", "closing '\"'");
+  expectSingleError(Context, "`never closed", "closing '`'");
+  expectSingleError(Context, "<mcsymbol local", "closed by '>'");
+  expectSingleError(Context, "!unknown", "unknown metadata keyword");
+  expectSingleError(Context, "bb.name", "decimal block number");
+  expectSingleError(Context, "#", "unexpected character '#'");
+  expectSingleError(Context, std::string(1, '\0'), "unexpected byte 0x00");
+  expectSingleError(Context, "four", "length limit",
+                    rcc::mir::MILexerOptions{.MaximumTokenLength = 3});
+
+  rcc::mir::MILexer Limited("limited.mir", "one two",
+                            rcc::mir::MILexerOptions{.MaximumTokenLength = 0, .MaximumTokens = 1});
+  expectToken(Context, Limited, {MITokenKind::Identifier, "one", "one", std::nullopt});
+  const rcc::mir::MIToken LimitError = Limited.next();
+  Context.expect(LimitError.kind() == MITokenKind::Error && Limited.diagnostics().size() == 1 &&
+                     Limited.diagnostics().front().Message.find("token count") !=
+                         std::string::npos &&
+                     Limited.tokenCount() == 1,
+                 "MI lexer token count limits must fail before publishing excess tokens");
+}
+
+void testRangesAndClassifiers(TestContext &Context) {
+  rcc::mir::MILexer Lexer("ranges.mir", "implicit\n  $x0 \"flag\"");
+  const rcc::mir::MIToken Flag = Lexer.next();
+  const rcc::mir::MIToken Newline = Lexer.next();
+  const rcc::mir::MIToken Register = Lexer.next();
+  const rcc::mir::MIToken StringFlag = Lexer.next();
+
+  Context.expect(Flag.isRegisterFlag() && !Flag.isRegister() && Flag.range().Begin.Line == 1 &&
+                     Flag.range().Begin.Column == 1 && Flag.range().End.Column == 9,
+                 "register flags must retain exact source ranges");
+  Context.expect(Newline.kind() == MITokenKind::Newline && Register.isRegister() &&
+                     Register.stringValue() == "x0" && Register.range().Begin.Line == 2 &&
+                     Register.range().Begin.Column == 3,
+                 "line and column tracking must account for skipped indentation");
+  Context.expect(StringFlag.isMemoryOperandFlag() &&
+                     rcc::mir::getMITokenKindName(StringFlag.kind()) == "string-constant",
+                 "memory operand and token-kind classifiers must cover string flags");
+
+  rcc::mir::MILexer Invalid("body.mir", "ok\n  #");
+  static_cast<void>(Invalid.next());
+  static_cast<void>(Invalid.next());
+  static_cast<void>(Invalid.next());
+  const std::string Formatted =
+      rcc::formatTextDiagnostic(Invalid.diagnostics().front(), Invalid.source());
+  Context.expect(Formatted.starts_with("body.mir:2:3: error[mir-lexer]: unexpected character '#'"),
+                 "formatted MI diagnostics must report stable input line and column");
+
+  rcc::mir::MILexer Original("move.mir", R"("owned\20value")");
+  rcc::mir::MILexer Moved(std::move(Original));
+  const rcc::mir::MIToken Owned = Moved.next();
+  Context.expect(Owned.stringValue() == "owned value",
+                 "moving an MI lexer must preserve owned decoded token values");
+}
+
+} // namespace
+
+int main() {
+  TestContext Context;
+  testPunctuationAndTrivia(Context);
+  testKeywordCorpus(Context);
+  testMetadataKeywords(Context);
+  testNamedEntities(Context);
+  testNumericalLiterals(Context);
+  testDiagnosticsAndLimits(Context);
+  testRangesAndClassifiers(Context);
+  return Context.result();
+}