[CodeGen] Complete register allocation infrastructure

7 files changed, 67 insertions, 52 deletions

diff --git a/backend/lib/MIR/EmbeddedIR.cpp b/backend/lib/MIR/EmbeddedIR.cpp
index b19748e..662faac 100644
--- a/backend/lib/MIR/EmbeddedIR.cpp
+++ b/backend/lib/MIR/EmbeddedIR.cpp
@@ -322,8 +322,8 @@ private:
       parseMetadataDefinition(Line, LineOffset, Position, End);
   }
 
-  void parseTypeDefinition(std::string_view Line, std::size_t LineOffset,
-                           std::size_t Position, std::size_t End) {
+  void parseTypeDefinition(std::string_view Line, std::size_t LineOffset, std::size_t Position,
+                           std::size_t End) {
     auto Name = parseIdentifier(Line, LineOffset, Position, End, '%');
     if (!Name || Failed)
       return;
@@ -350,15 +350,14 @@ private:
       return;
     }
     const std::size_t TypeIndex = Index.TypeDefinitions.size();
-    const bool NumericName = !Name->Name.empty() && Name->Name.front() >= '0' &&
-                             Name->Name.front() <= '9';
+    const bool NumericName =
+        !Name->Name.empty() && Name->Name.front() >= '0' && Name->Name.front() <= '9';
     Index.TypeNameToIndex.emplace(Name->Name, TypeIndex);
     Index.TypeDefinitions.push_back(EmbeddedIRTypeDefinition{
         .Name = std::move(Name->Name),
         .Range = Name->Range,
         .Definition = std::string(Line.substr(Position, DefinitionEnd - Position)),
-        .DefinitionRange =
-            Index.Source.range(LineOffset + Position, LineOffset + DefinitionEnd),
+        .DefinitionRange = Index.Source.range(LineOffset + Position, LineOffset + DefinitionEnd),
         .NumericName = NumericName,
     });
   }
@@ -495,10 +494,10 @@ private:
         std::size_t Previous = IdentifierBegin;
         while (Previous > 0 && isHorizontalSpace(Line[Previous - 1]))
           --Previous;
-        const bool HasTypeBefore = Previous != 0 && Line[Previous - 1] != '(' &&
-                                   Line[Previous - 1] != ',';
-        const bool EndsParameter = Following == End || Line[Following] == ',' ||
-                                   Line[Following] == ')';
+        const bool HasTypeBefore =
+            Previous != 0 && Line[Previous - 1] != '(' && Line[Previous - 1] != ',';
+        const bool EndsParameter =
+            Following == End || Line[Following] == ',' || Line[Following] == ')';
         if (HasTypeBefore && EndsParameter)
           addLocalValue(*Name, Index.Functions[ActiveFunction.value()]);
         Position = Name->End - 1;
@@ -630,9 +629,8 @@ private:
     });
   }
 
-  void parseLocalValueDefinition(std::string_view Line, std::size_t LineOffset,
-                                 std::size_t Begin, std::size_t End,
-                                 EmbeddedIRFunction &Function) {
+  void parseLocalValueDefinition(std::string_view Line, std::size_t LineOffset, std::size_t Begin,
+                                 std::size_t End, EmbeddedIRFunction &Function) {
     std::size_t Position = skipHorizontalSpace(Line, Begin, End);
     if (Position >= End || Line[Position] != '%')
       return;
diff --git a/backend/lib/MIR/LLVMConstantSyntax.cpp b/backend/lib/MIR/LLVMConstantSyntax.cpp
index 543cc1a..8bc2c18 100644
--- a/backend/lib/MIR/LLVMConstantSyntax.cpp
+++ b/backend/lib/MIR/LLVMConstantSyntax.cpp
@@ -248,9 +248,7 @@ private:
     Words[Nibble / 16U] |= static_cast<std::uint64_t>(hexDigitValue(*Iterator))
                            << ((Nibble % 16U) * 4U);
   }
-  if ((BitWidth % 64U) != 0 && (Words.back() >> (BitWidth % 64U)) != 0)
-    return false;
-  return true;
+  return (BitWidth % 64U) == 0 || (Words.back() >> (BitWidth % 64U)) == 0;
 }
 
 [[nodiscard]] bool parseLegacyWideFloatHexWords(std::string_view Digits,
@@ -1172,7 +1170,7 @@ convertRawDoubleNaN(FloatSemantics Semantics, bool Negative, std::uint64_t Fract
                           "integer hexadecimal spelling contains a non-hexadecimal digit");
   }
 
-  const auto FirstNonZero =
+  const auto *const FirstNonZero =
       std::ranges::find_if(Digits, [](char Character) { return hexDigitValue(Character) != 0; });
   std::size_t ActiveBits = 0;
   if (FirstNonZero != Digits.end()) {
@@ -1998,9 +1996,8 @@ Expected<GenericConstantData> ConstantParser::parseExpression(GenericConstantTyp
     case GenericConstantExpressionOpcode::Xor:
     case GenericConstantExpressionOpcode::ExtractElement:
       return 2;
-    case GenericConstantExpressionOpcode::InsertElement:
-      return 3;
     case GenericConstantExpressionOpcode::ShuffleVector:
+    case GenericConstantExpressionOpcode::InsertElement:
       return 3;
     case GenericConstantExpressionOpcode::GetElementPtr:
       return 1;
@@ -2454,15 +2451,22 @@ Expected<std::string> printValue(const GenericConstantData &Value, bool IncludeT
   case GenericConstantKind::Invalid:
     break;
   case GenericConstantKind::Integer:
+    if (!Value.IntegerValue)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "integer constant is missing its integer payload");
     if (resolvedType(Value.Type).Kind == GenericConstantTypeKind::Integer &&
         resolvedType(Value.Type).BitWidth == 1)
-      Result.append(Value.IntegerValue->isZero() ? "false" : "true");
+      Result.append(Value.IntegerValue.value().isZero() ? "false" : "true");
     else
-      Result.append(Value.IntegerValue->toUnsignedDecimal());
+      Result.append(Value.IntegerValue.value().toUnsignedDecimal());
     return Result;
   case GenericConstantKind::Floating:
+    if (!Value.FloatingValue)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "floating constant is missing its floating payload");
     Result.append("f0x");
-    Result.append(hexadecimalWords(Value.FloatingValue->words(), Value.FloatingValue->bitWidth()));
+    Result.append(hexadecimalWords(Value.FloatingValue.value().words(),
+                                   Value.FloatingValue.value().bitWidth()));
     return Result;
   case GenericConstantKind::NullPointer:
     Result.append("null");
@@ -2549,15 +2553,25 @@ Expected<std::string> printValue(const GenericConstantData &Value, bool IncludeT
     if (Value.ExpressionFlags.has(GenericConstantExpressionFlag::NoSignedWrap))
       Result.append(" nsw");
     if (Value.InRangeStart) {
+      if (!Value.InRangeEnd) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "constant expression is missing its inrange end");
+      }
+      const auto &InRangeStart = Value.InRangeStart.value();
+      const auto &InRangeEnd = Value.InRangeEnd.value();
       Result.append(" inrange(");
-      Result.append(std::to_string(std::bit_cast<std::int64_t>(Value.InRangeStart->words()[0])));
+      Result.append(std::to_string(std::bit_cast<std::int64_t>(InRangeStart.words()[0])));
       Result.append(", ");
-      Result.append(std::to_string(std::bit_cast<std::int64_t>(Value.InRangeEnd->words()[0])));
+      Result.append(std::to_string(std::bit_cast<std::int64_t>(InRangeEnd.words()[0])));
       Result.push_back(')');
     }
     Result.append(" (");
     if (Value.ExpressionOpcode == GenericConstantExpressionOpcode::GetElementPtr) {
-      auto SourceType = printType(*Value.SourceElementType);
+      if (!Value.SourceElementType) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "getelementptr constant is missing its source element type");
+      }
+      auto SourceType = printType(Value.SourceElementType.value());
       if (!SourceType)
         return std::unexpected(SourceType.error());
       Result.append(*SourceType);
@@ -3004,14 +3018,12 @@ LayoutAlignment DataLayoutInfo::scalarAlignment(char Kind, std::uint32_t BitWidt
     if (Entry.Kind != Kind)
       continue;
     if (Kind == 'i') {
-      if (Entry.BitWidth >= BitWidth &&
-          (Selected == nullptr || Entry.BitWidth < Selected->BitWidth)) {
+      const bool BetterMatch =
+          Selected == nullptr ||
+          (Entry.BitWidth >= BitWidth && Entry.BitWidth < Selected->BitWidth) ||
+          (Selected->BitWidth < BitWidth && Entry.BitWidth > Selected->BitWidth);
+      if (BetterMatch)
         Selected = &Entry;
-      } else if (Selected == nullptr) {
-        Selected = &Entry;
-      } else if (Selected->BitWidth < BitWidth && Entry.BitWidth > Selected->BitWidth) {
-        Selected = &Entry;
-      }
     } else if (Entry.BitWidth == BitWidth) {
       Selected = &Entry;
       break;
diff --git a/backend/lib/MIR/MIDebugSyntax.cpp b/backend/lib/MIR/MIDebugSyntax.cpp
index bee82c4..fc08df6 100644
--- a/backend/lib/MIR/MIDebugSyntax.cpp
+++ b/backend/lib/MIR/MIDebugSyntax.cpp
@@ -16,15 +16,13 @@ namespace {
 [[nodiscard]] bool parseIndex(std::string_view Text, std::uint64_t &Value) noexcept {
   if (Text.empty())
     return false;
-  const auto [End, Error] =
-      std::from_chars(Text.data(), Text.data() + Text.size(), Value, 10);
+  const auto [End, Error] = std::from_chars(Text.data(), Text.data() + Text.size(), Value, 10);
   return Error == std::errc{} && End == Text.data() + Text.size();
 }
 
 } // namespace
 
-std::optional<std::uint64_t>
-parseDIExpressionOpcodeName(std::string_view Name) noexcept {
+std::optional<std::uint64_t> parseDIExpressionOpcodeName(std::string_view Name) noexcept {
   const auto NumberedOpcode = [Name](std::string_view Prefix,
                                      std::uint64_t Base) -> std::optional<std::uint64_t> {
     if (!Name.starts_with(Prefix))
@@ -117,7 +115,7 @@ parseDIExpressionOpcodeName(std::string_view Name) noexcept {
       {"DW_OP_LLVM_implicit_pointer", 0x1004},
       {"DW_OP_LLVM_arg", 0x1005},
   });
-  const auto Found =
+  const auto *const Found =
       std::ranges::find_if(NamedOpcodes, [Name](const auto &Entry) { return Entry.first == Name; });
   if (Found == NamedOpcodes.end())
     return std::nullopt;
diff --git a/backend/lib/MIR/MIPrinter.cpp b/backend/lib/MIR/MIPrinter.cpp
index 83fce40..8ad6d6c 100644
--- a/backend/lib/MIR/MIPrinter.cpp
+++ b/backend/lib/MIR/MIPrinter.cpp
@@ -1285,20 +1285,24 @@ Expected<void> BodyPrinter::printInstruction(const MachineInstr &Instruction) {
     return makeUnexpected(ErrorCode::VerificationError,
                           "machine instruction has no target descriptor");
   }
-  if (Descriptor->NumExplicitDefs > Instruction.operandCount()) {
-    return makeUnexpected(ErrorCode::VerificationError,
-                          "machine instruction has fewer operands than explicit definitions");
+  std::size_t ExplicitDefs = 0;
+  while (ExplicitDefs < Instruction.operandCount()) {
+    const MachineOperand *Operand = Instruction.operandAt(ExplicitDefs);
+    if (Operand == nullptr || !Operand->isRegister() || Operand->isImplicit() ||
+        !Operand->isDef() || Operand->isUse())
+      break;
+    ++ExplicitDefs;
   }
 
   Output.append("  ");
-  for (std::size_t Index = 0; Index < Descriptor->NumExplicitDefs; ++Index) {
+  for (std::size_t Index = 0; Index < ExplicitDefs; ++Index) {
     if (Index != 0)
       Output.append(", ");
     if (auto Printed = printOperand(*Instruction.operandAt(Index), true); !Printed) {
       return Printed;
     }
   }
-  if (Descriptor->NumExplicitDefs != 0)
+  if (ExplicitDefs != 0)
     Output.append(" = ");
 
   const MachineInstrFlags Flags = Instruction.flags();
@@ -1333,8 +1337,7 @@ Expected<void> BodyPrinter::printInstruction(const MachineInstr &Instruction) {
   Output.append(Descriptor->Name);
 
   bool HasPrintedTail = false;
-  for (std::size_t Index = Descriptor->NumExplicitDefs; Index < Instruction.operandCount();
-       ++Index) {
+  for (std::size_t Index = ExplicitDefs; Index < Instruction.operandCount(); ++Index) {
     Output.append(HasPrintedTail ? ", " : " ");
     HasPrintedTail = true;
     if (auto Printed = printOperand(*Instruction.operandAt(Index), false); !Printed) {
diff --git a/backend/lib/MIR/MIRDocument.cpp b/backend/lib/MIR/MIRDocument.cpp
index 4808df7..67e6ffb 100644
--- a/backend/lib/MIR/MIRDocument.cpp
+++ b/backend/lib/MIR/MIRDocument.cpp
@@ -406,7 +406,8 @@ class MIRDocumentParser final {
 public:
   MIRDocumentParser(const TargetDescription &Target, std::string SourceName, std::string SourceText,
                     MIRDocumentParserOptions Options)
-      : Target(Target), Options(Options), Result(std::move(SourceName), std::move(SourceText)) {}
+      : Target(Target), Options(std::move(Options)),
+        Result(std::move(SourceName), std::move(SourceText)) {}
 
   [[nodiscard]] MIRDocumentParseResult run();
 
@@ -2144,8 +2145,7 @@ bool MIRDocumentParser::parseFunctionRecords(const yaml::Node &Root, MachineFunc
           WideFlags > std::numeric_limits<std::uint32_t>::max()) {
         return true;
       }
-      if (ActiveDocument->EmbeddedIR &&
-          ActiveDocument->EmbeddedIR->hasGlobalValue(Callee) == false) {
+      if (ActiveDocument->EmbeddedIR && !ActiveDocument->EmbeddedIR->hasGlobalValue(Callee)) {
         return fail(CalleeNode->range(), "called global references an undefined embedded global");
       }
       auto AddResult =
@@ -2765,7 +2765,8 @@ MIRDocumentParseResult::~MIRDocumentParseResult() = default;
 
 MIRDocumentParseResult parseMIRDocument(const TargetDescription &Target, std::string SourceName,
                                         std::string SourceText, MIRDocumentParserOptions Options) {
-  return MIRDocumentParser(Target, std::move(SourceName), std::move(SourceText), Options).run();
+  return MIRDocumentParser(Target, std::move(SourceName), std::move(SourceText), std::move(Options))
+      .run();
 }
 
 } // namespace rcc::mir
diff --git a/backend/lib/MIR/MIRDocumentPrinter.cpp b/backend/lib/MIR/MIRDocumentPrinter.cpp
index e9f9e1c..dba1ec7 100644
--- a/backend/lib/MIR/MIRDocumentPrinter.cpp
+++ b/backend/lib/MIR/MIRDocumentPrinter.cpp
@@ -85,7 +85,7 @@ class MIRDocumentPrinter final {
 public:
   MIRDocumentPrinter(const MIRDocument &Document, const TargetDescription &Target,
                      MIRDocumentPrinterOptions Options)
-      : Document(Document), Target(Target), Options(Options) {}
+      : Document(Document), Target(Target), Options(std::move(Options)) {}
 
   [[nodiscard]] Expected<std::string> run();
 
@@ -1187,9 +1187,10 @@ Expected<void> MIRDocumentPrinter::printFunction(const MachineFunction &Function
   Output.append("---\nname: ");
   Output.append(yamlScalar(Function.name()));
   Output.push_back('\n');
-  if (Function.attributes().alignment()) {
+  const auto Alignment = Function.attributes().alignment();
+  if (Alignment) {
     Output.append("alignment: ");
-    Output.append(std::to_string(Function.attributes().alignment()->bytes()));
+    Output.append(std::to_string(Alignment->bytes()));
     Output.push_back('\n');
   }
 
@@ -1296,7 +1297,7 @@ Expected<std::string> MIRDocumentPrinter::run() {
 
 Expected<std::string> printMIRDocument(const MIRDocument &Document, const TargetDescription &Target,
                                        MIRDocumentPrinterOptions Options) {
-  return MIRDocumentPrinter(Document, Target, Options).run();
+  return MIRDocumentPrinter(Document, Target, std::move(Options)).run();
 }
 
 } // namespace rcc::mir
diff --git a/backend/lib/MIR/MIRDocumentReferenceValidation.h b/backend/lib/MIR/MIRDocumentReferenceValidation.h
index 0992d84..2ab6291 100644
--- a/backend/lib/MIR/MIRDocumentReferenceValidation.h
+++ b/backend/lib/MIR/MIRDocumentReferenceValidation.h
@@ -1,5 +1,7 @@
 // SPDX-License-Identifier: GPL-3.0-or-later
 
+// The private header has no stable include-root-relative guard name.
+// NOLINTNEXTLINE(llvm-header-guard)
 #ifndef RCC_LIB_MIR_MIRDOCUMENTREFERENCEVALIDATION_H
 #define RCC_LIB_MIR_MIRDOCUMENTREFERENCEVALIDATION_H