4 files changed, 371 insertions, 0 deletions

diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt
index 341452a..15f1772 100644
--- a/backend/lib/CodeGen/CMakeLists.txt
+++ b/backend/lib/CodeGen/CMakeLists.txt
@@ -3,6 +3,7 @@
 set(
   RCCBackendCodeGenSources
   CompilationUnit.cpp
+  GlobalObject.cpp
   GenericOpcodes.cpp
   GenericConstant.cpp
   FrameIndexElimination.cpp
@@ -82,6 +83,7 @@ set(
 set(
   RCCBackendCodeGenHeaders
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/CompilationUnit.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalObject.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GenericOpcodes.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GenericConstant.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/FrameIndexElimination.h"
@@ -201,6 +203,7 @@ install(
 
 rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/CompilationUnit.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/GlobalObject.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/GenericOpcodes.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/GenericConstant.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/InstructionDescriptor.cpp"
@@ -281,6 +284,7 @@ rcc_backend_register_format_files(
 )
 rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/CompilationUnit.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/GlobalObject.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/GenericOpcodes.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/GenericConstant.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/InstructionDescriptor.cpp"
diff --git a/backend/lib/CodeGen/CompilationUnit.cpp b/backend/lib/CodeGen/CompilationUnit.cpp
index 1de6487..5ec54bc 100644
--- a/backend/lib/CodeGen/CompilationUnit.cpp
+++ b/backend/lib/CodeGen/CompilationUnit.cpp
@@ -28,6 +28,10 @@ Expected<MachineFunction *> CompilationUnit::createMachineFunction(std::string N
     return makeUnexpected(ErrorCode::InvalidArgument,
                           "machine function name is already present in the compilation unit");
   }
+  if (GlobalNameToIndex.contains(Name)) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "machine function name conflicts with a global object");
+  }
 
   auto StableID = FunctionIDGenerator.allocate();
   if (!StableID)
@@ -43,6 +47,27 @@ Expected<MachineFunction *> CompilationUnit::createMachineFunction(std::string N
   return Result;
 }
 
+Expected<GlobalObjectDesc *> CompilationUnit::addGlobalObject(GlobalObjectDesc Object) {
+  auto Verification = Object.verify();
+  if (!Verification)
+    return std::unexpected(Verification.error());
+  if (FunctionNameToIndex.contains(Object.Symbol)) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "global object symbol conflicts with a machine function");
+  }
+  if (GlobalNameToIndex.contains(Object.Symbol)) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "global object symbol is already present in the compilation unit");
+  }
+
+  const std::size_t Index = GlobalObjects.size();
+  auto Storage = std::make_unique<GlobalObjectDesc>(std::move(Object));
+  GlobalObjectDesc *Result = Storage.get();
+  GlobalNameToIndex.emplace(Result->Symbol, Index);
+  GlobalObjects.push_back(std::move(Storage));
+  return Result;
+}
+
 MachineFunction *CompilationUnit::functionAt(std::size_t Index) noexcept {
   if (Index >= Functions.size())
     return nullptr;
@@ -85,11 +110,33 @@ const MachineFunction *CompilationUnit::function(MachineFunctionStableID ID) con
   return nullptr;
 }
 
+GlobalObjectDesc *CompilationUnit::globalObjectAt(std::size_t Index) noexcept {
+  return Index < GlobalObjects.size() ? GlobalObjects[Index].get() : nullptr;
+}
+
+const GlobalObjectDesc *CompilationUnit::globalObjectAt(std::size_t Index) const noexcept {
+  return Index < GlobalObjects.size() ? GlobalObjects[Index].get() : nullptr;
+}
+
+GlobalObjectDesc *CompilationUnit::globalObject(std::string_view Name) noexcept {
+  const auto Position = GlobalNameToIndex.find(Name);
+  return Position == GlobalNameToIndex.end() ? nullptr : GlobalObjects[Position->second].get();
+}
+
+const GlobalObjectDesc *CompilationUnit::globalObject(std::string_view Name) const noexcept {
+  const auto Position = GlobalNameToIndex.find(Name);
+  return Position == GlobalNameToIndex.end() ? nullptr : GlobalObjects[Position->second].get();
+}
+
 Expected<void> CompilationUnit::verify() const {
   if (FunctionNameToIndex.size() != Functions.size()) {
     return makeUnexpected(ErrorCode::VerificationError,
                           "compilation unit function name index has an inconsistent size");
   }
+  if (GlobalNameToIndex.size() != GlobalObjects.size()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "compilation unit global object name index has an inconsistent size");
+  }
 
   std::unordered_set<MachineFunctionStableID> StableIDs;
   for (std::size_t Index = 0; Index < Functions.size(); ++Index) {
@@ -112,6 +159,30 @@ Expected<void> CompilationUnit::verify() const {
       return makeUnexpected(ErrorCode::VerificationError,
                             "compilation unit function name index is inconsistent");
     }
+    if (GlobalNameToIndex.contains(Function->name())) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "function name conflicts with a global object symbol");
+    }
+  }
+
+  for (std::size_t Index = 0; Index < GlobalObjects.size(); ++Index) {
+    const std::unique_ptr<GlobalObjectDesc> &Object = GlobalObjects[Index];
+    if (Object == nullptr) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "compilation unit contains a null global object");
+    }
+    auto ObjectVerification = Object->verify();
+    if (!ObjectVerification)
+      return std::unexpected(ObjectVerification.error());
+    const auto Position = GlobalNameToIndex.find(Object->Symbol);
+    if (Position == GlobalNameToIndex.end() || Position->second != Index) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "compilation unit global object name index is inconsistent");
+    }
+    if (FunctionNameToIndex.contains(Object->Symbol)) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "global object symbol conflicts with a function name");
+    }
   }
   return {};
 }
diff --git a/backend/lib/CodeGen/GlobalObject.cpp b/backend/lib/CodeGen/GlobalObject.cpp
new file mode 100644
index 0000000..cda28bd
--- /dev/null
+++ b/backend/lib/CodeGen/GlobalObject.cpp
@@ -0,0 +1,295 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/GlobalObject.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <limits>
+#include <memory>
+#include <string>
+#include <unordered_set>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] bool validText(const std::string &Text) noexcept {
+  return !Text.empty() && Text.find('\0') == std::string::npos &&
+         Text.find('\n') == std::string::npos && Text.find('\r') == std::string::npos;
+}
+
+[[nodiscard]] bool validValueSize(std::uint8_t Size) noexcept {
+  return Size == 1 || Size == 2 || Size == 4 || Size == 8;
+}
+
+[[nodiscard]] Expected<std::uint64_t> addSize(std::uint64_t Left, std::uint64_t Right) {
+  std::uint64_t Result = 0;
+  if (__builtin_add_overflow(Left, Right, &Result))
+    return makeUnexpected(ErrorCode::VerificationError, "global initializer size overflows");
+  return Result;
+}
+
+[[nodiscard]] Expected<std::uint64_t> multiplySize(std::uint64_t Left, std::uint64_t Right) {
+  std::uint64_t Result = 0;
+  if (__builtin_mul_overflow(Left, Right, &Result))
+    return makeUnexpected(ErrorCode::VerificationError, "global initializer size overflows");
+  return Result;
+}
+
+[[nodiscard]] Expected<std::uint64_t> initializerSize(const GlobalInitializer &Initializer,
+                                                      std::size_t Depth, std::size_t MaximumDepth) {
+  if (Depth > MaximumDepth)
+    return makeUnexpected(ErrorCode::VerificationError, "global initializer is too deeply nested");
+  switch (Initializer.kind()) {
+  case GlobalInitializer::Kind::Invalid:
+    return makeUnexpected(ErrorCode::VerificationError, "global initializer is invalid");
+  case GlobalInitializer::Kind::Integer: {
+    const auto *Value = Initializer.getIf<IntegerImmediate>();
+    if (Value == nullptr)
+      return makeUnexpected(ErrorCode::InternalError, "integer initializer storage is invalid");
+    auto Verified = Value->verify();
+    if (!Verified)
+      return std::unexpected(Verified.error());
+    return (static_cast<std::uint64_t>(Value->bitWidth()) + 7U) / 8U;
+  }
+  case GlobalInitializer::Kind::Floating: {
+    const auto *Value = Initializer.getIf<FloatingPointBits>();
+    if (Value == nullptr)
+      return makeUnexpected(ErrorCode::InternalError, "floating initializer storage is invalid");
+    return (static_cast<std::uint64_t>(Value->bitWidth()) + 7U) / 8U;
+  }
+  case GlobalInitializer::Kind::Bytes: {
+    const auto *Value = Initializer.getIf<std::vector<std::byte>>();
+    if (Value == nullptr || Value->empty())
+      return makeUnexpected(ErrorCode::VerificationError, "byte initializer cannot be empty");
+    return static_cast<std::uint64_t>(Value->size());
+  }
+  case GlobalInitializer::Kind::ZeroFill: {
+    const auto *Value = Initializer.getIf<GlobalZeroFill>();
+    if (Value == nullptr || Value->Size == 0)
+      return makeUnexpected(ErrorCode::VerificationError, "zero-fill initializer has zero size");
+    return Value->Size;
+  }
+  case GlobalInitializer::Kind::Repeated: {
+    const auto *Value = Initializer.getIf<GlobalRepeatedInitializer>();
+    if (Value == nullptr || Value->Count == 0 || !Value->Value)
+      return makeUnexpected(ErrorCode::VerificationError, "repeated initializer is invalid");
+    auto ElementSize = initializerSize(*Value->Value, Depth + 1, MaximumDepth);
+    if (!ElementSize)
+      return std::unexpected(ElementSize.error());
+    return multiplySize(*ElementSize, Value->Count);
+  }
+  case GlobalInitializer::Kind::Aggregate: {
+    const auto *Value = Initializer.getIf<GlobalAggregateInitializer>();
+    if (Value == nullptr || Value->Elements.empty())
+      return makeUnexpected(ErrorCode::VerificationError, "aggregate initializer cannot be empty");
+    std::uint64_t Size = 0;
+    for (const GlobalInitializerRef &Element : Value->Elements) {
+      if (!Element)
+        return makeUnexpected(ErrorCode::VerificationError, "aggregate initializer is null");
+      auto ElementSize = initializerSize(*Element, Depth + 1, MaximumDepth);
+      if (!ElementSize)
+        return std::unexpected(ElementSize.error());
+      auto Updated = addSize(Size, *ElementSize);
+      if (!Updated)
+        return std::unexpected(Updated.error());
+      Size = *Updated;
+    }
+    return Size;
+  }
+  case GlobalInitializer::Kind::SymbolAddress: {
+    const auto *Value = Initializer.getIf<GlobalSymbolAddress>();
+    if (Value == nullptr || !validText(Value->Symbol) || !validValueSize(Value->Size)) {
+      return makeUnexpected(ErrorCode::VerificationError, "symbol-address initializer is invalid");
+    }
+    return Value->Size;
+  }
+  case GlobalInitializer::Kind::SymbolDifference: {
+    const auto *Value = Initializer.getIf<GlobalSymbolDifference>();
+    if (Value == nullptr || !validText(Value->Minuend) || !validText(Value->Subtrahend) ||
+        !validValueSize(Value->Size)) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "symbol-difference initializer is invalid");
+    }
+    return Value->Size;
+  }
+  case GlobalInitializer::Kind::Target: {
+    const auto *Value = Initializer.getIf<TargetConstant>();
+    if (Value == nullptr)
+      return makeUnexpected(ErrorCode::InternalError, "target initializer storage is invalid");
+    auto Emission = Value->emit();
+    if (!Emission)
+      return std::unexpected(Emission.error());
+    return static_cast<std::uint64_t>(Emission->Bytes.size());
+  }
+  case GlobalInitializer::Kind::AlignmentPadding: {
+    const auto *Value = Initializer.getIf<GlobalAlignmentPadding>();
+    if (Value == nullptr || Value->Size == 0)
+      return makeUnexpected(ErrorCode::VerificationError, "alignment padding has zero size");
+    return Value->Size;
+  }
+  case GlobalInitializer::Kind::UndefinedStorage: {
+    const auto *Value = Initializer.getIf<GlobalUndefinedStorage>();
+    if (Value == nullptr || Value->Size == 0)
+      return makeUnexpected(ErrorCode::VerificationError, "undefined storage has zero size");
+    return Value->Size;
+  }
+  }
+  return makeUnexpected(ErrorCode::InternalError, "global initializer kind is invalid");
+}
+
+} // namespace
+
+GlobalInitializer GlobalInitializer::integer(IntegerImmediate Value) {
+  return GlobalInitializer(std::move(Value));
+}
+
+GlobalInitializer GlobalInitializer::floating(FloatingPointBits Value) {
+  return GlobalInitializer(Value);
+}
+
+Expected<GlobalInitializer> GlobalInitializer::bytes(std::vector<std::byte> Value) {
+  if (Value.empty())
+    return makeUnexpected(ErrorCode::InvalidArgument, "byte initializer cannot be empty");
+  return GlobalInitializer(std::move(Value));
+}
+
+Expected<GlobalInitializer> GlobalInitializer::zeroFill(std::uint64_t Size) {
+  if (Size == 0)
+    return makeUnexpected(ErrorCode::InvalidArgument, "zero-fill initializer size must be nonzero");
+  return GlobalInitializer(GlobalZeroFill{.Size = Size});
+}
+
+Expected<GlobalInitializer> GlobalInitializer::repeated(std::uint64_t Count,
+                                                        GlobalInitializer Value) {
+  if (Count == 0)
+    return makeUnexpected(ErrorCode::InvalidArgument, "initializer repeat count must be nonzero");
+  auto Reference = std::make_shared<GlobalInitializer>(std::move(Value));
+  auto Verification = Reference->verify();
+  if (!Verification)
+    return std::unexpected(Verification.error());
+  return GlobalInitializer(
+      GlobalRepeatedInitializer{.Count = Count, .Value = std::move(Reference)});
+}
+
+Expected<GlobalInitializer> GlobalInitializer::aggregate(std::vector<GlobalInitializer> Elements) {
+  if (Elements.empty())
+    return makeUnexpected(ErrorCode::InvalidArgument, "aggregate initializer cannot be empty");
+  GlobalAggregateInitializer Result;
+  Result.Elements.reserve(Elements.size());
+  for (GlobalInitializer &Element : Elements) {
+    auto Reference = std::make_shared<GlobalInitializer>(std::move(Element));
+    auto Verification = Reference->verify();
+    if (!Verification)
+      return std::unexpected(Verification.error());
+    Result.Elements.push_back(std::move(Reference));
+  }
+  return GlobalInitializer(std::move(Result));
+}
+
+Expected<GlobalInitializer> GlobalInitializer::symbolAddress(GlobalSymbolAddress Value) {
+  GlobalInitializer Result(std::move(Value));
+  auto Verification = Result.verify();
+  if (!Verification)
+    return std::unexpected(Verification.error());
+  return Result;
+}
+
+Expected<GlobalInitializer> GlobalInitializer::symbolDifference(GlobalSymbolDifference Value) {
+  GlobalInitializer Result(std::move(Value));
+  auto Verification = Result.verify();
+  if (!Verification)
+    return std::unexpected(Verification.error());
+  return Result;
+}
+
+Expected<GlobalInitializer> GlobalInitializer::target(TargetConstant Value) {
+  GlobalInitializer Result(std::move(Value));
+  auto Verification = Result.verify();
+  if (!Verification)
+    return std::unexpected(Verification.error());
+  return Result;
+}
+
+Expected<GlobalInitializer> GlobalInitializer::alignmentPadding(std::uint64_t Size,
+                                                                std::uint8_t Fill) {
+  if (Size == 0)
+    return makeUnexpected(ErrorCode::InvalidArgument, "alignment padding size must be nonzero");
+  return GlobalInitializer(GlobalAlignmentPadding{.Size = Size, .Fill = Fill});
+}
+
+Expected<GlobalInitializer> GlobalInitializer::undefinedStorage(std::uint64_t Size) {
+  if (Size == 0)
+    return makeUnexpected(ErrorCode::InvalidArgument, "undefined storage size must be nonzero");
+  return GlobalInitializer(GlobalUndefinedStorage{.Size = Size});
+}
+
+GlobalInitializer::Kind GlobalInitializer::kind() const noexcept {
+  return static_cast<Kind>(Storage.index());
+}
+
+Expected<void> GlobalInitializer::verify(std::size_t MaximumDepth) const {
+  if (MaximumDepth == 0)
+    return makeUnexpected(ErrorCode::InvalidArgument, "initializer depth limit cannot be zero");
+  auto Size = initializerSize(*this, 1, MaximumDepth);
+  if (!Size)
+    return std::unexpected(Size.error());
+  return {};
+}
+
+Expected<std::uint64_t> GlobalInitializer::storageSize(std::size_t MaximumDepth) const {
+  if (MaximumDepth == 0)
+    return makeUnexpected(ErrorCode::InvalidArgument, "initializer depth limit cannot be zero");
+  return initializerSize(*this, 1, MaximumDepth);
+}
+
+Expected<void> GlobalObjectDesc::verify() const {
+  if (!validText(Symbol))
+    return makeUnexpected(ErrorCode::VerificationError, "global object symbol is invalid");
+  auto TypeVerification = ObjectType.verify();
+  if (!TypeVerification)
+    return std::unexpected(TypeVerification.error());
+  if (Linkage >= GlobalLinkage::Count || Visibility >= GlobalVisibility::Count ||
+      TLSModel >= GlobalTLSModel::Count || UnnamedAddress >= GlobalUnnamedAddress::Count) {
+    return makeUnexpected(ErrorCode::VerificationError, "global object enum field is invalid");
+  }
+  if (Section && !validText(*Section))
+    return makeUnexpected(ErrorCode::VerificationError, "global object section is invalid");
+  if (COMDAT && !validText(*COMDAT))
+    return makeUnexpected(ErrorCode::VerificationError, "global object COMDAT is invalid");
+  if (Size == 0 && !isDeclaration())
+    return makeUnexpected(ErrorCode::VerificationError, "defined global object has zero size");
+  if (!isDeclaration() &&
+      Size > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max())) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "global object size exceeds the supported assembly range");
+  }
+  if (Linkage == GlobalLinkage::Common && Initializer)
+    return makeUnexpected(ErrorCode::VerificationError, "common global cannot have an initializer");
+  if (Initializer) {
+    auto InitializerSize = Initializer->storageSize();
+    if (!InitializerSize)
+      return std::unexpected(InitializerSize.error());
+    if (*InitializerSize != Size) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "global initializer size does not match its object size");
+    }
+  }
+  std::unordered_set<std::string> AttributeNames;
+  for (const auto &[Name, Value] : TargetAttributes) {
+    if (!validText(Name) || Value.find('\0') != std::string::npos ||
+        Value.find('\n') != std::string::npos || Value.find('\r') != std::string::npos ||
+        !AttributeNames.insert(Name).second) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "global target attribute is invalid or duplicated");
+    }
+  }
+  for (const std::string &Expression : DebugExpressions) {
+    if (!validText(Expression))
+      return makeUnexpected(ErrorCode::VerificationError, "global debug expression is invalid");
+  }
+  return {};
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/MachineCompilationStatus.cpp b/backend/lib/CodeGen/MachineCompilationStatus.cpp
index e541d39..93acf3a 100644
--- a/backend/lib/CodeGen/MachineCompilationStatus.cpp
+++ b/backend/lib/CodeGen/MachineCompilationStatus.cpp
@@ -50,6 +50,7 @@ isKnownDiagnosticSeverity(MachineCompilationDiagnosticSeverity Severity) noexcep
   case ErrorCode::PseudoExpansionFailed:
   case ErrorCode::FinalEncodabilityFailed:
   case ErrorCode::CFGOptimizationFailed:
+  case ErrorCode::AssemblyLoweringFailed:
   case ErrorCode::IoError:
   case ErrorCode::InternalError:
     return true;