[MC] Implement RV64GC object emission

9 files changed, 499 insertions, 0 deletions

diff --git a/backend/include/rcc/MC/ELFObjectWriter.h b/backend/include/rcc/MC/ELFObjectWriter.h
new file mode 100644
index 0000000..2cd8879
--- /dev/null
+++ b/backend/include/rcc/MC/ELFObjectWriter.h
@@ -0,0 +1,45 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_MC_ELFOBJECTWRITER_H
+#define RCC_MC_ELFOBJECTWRITER_H
+
+#include "rcc/MC/MCObjectWriter.h"
+
+#include <cstdint>
+#include <string>
+#include <utility>
+#include <vector>
+
+namespace rcc::mc {
+
+struct ELFExtraSection final {
+  std::string Name;
+  std::uint32_t Type = 1;
+  std::uint64_t Flags = 0;
+  std::uint64_t Alignment = 1;
+  std::uint64_t EntrySize = 0;
+  std::vector<std::uint8_t> Contents;
+};
+
+struct ELFObjectTargetInfo final {
+  std::uint16_t Machine = 0;
+  std::uint8_t OSABI = 0;
+  std::uint8_t ABIVersion = 0;
+  std::uint32_t Flags = 0;
+  std::vector<ELFExtraSection> ExtraSections;
+};
+
+class ELF64LEObjectWriter final : public MCObjectWriter {
+public:
+  explicit ELF64LEObjectWriter(ELFObjectTargetInfo Target) : Target(std::move(Target)) {}
+
+  [[nodiscard]] Expected<std::vector<std::uint8_t>>
+  writeObject(const MCAssembledObject &Object) const override;
+
+private:
+  ELFObjectTargetInfo Target;
+};
+
+} // namespace rcc::mc
+
+#endif // RCC_MC_ELFOBJECTWRITER_H
diff --git a/backend/include/rcc/MC/MCAsmBackend.h b/backend/include/rcc/MC/MCAsmBackend.h
new file mode 100644
index 0000000..76e6214
--- /dev/null
+++ b/backend/include/rcc/MC/MCAsmBackend.h
@@ -0,0 +1,55 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_MC_MCASMBACKEND_H
+#define RCC_MC_MCASMBACKEND_H
+
+#include "rcc/MC/MCFixup.h"
+#include "rcc/MC/MCInst.h"
+#include "rcc/Support/Error.h"
+
+#include <cstdint>
+#include <span>
+#include <vector>
+
+namespace rcc::mc {
+
+struct MCFixupKindInfo final {
+  std::uint8_t StorageSize = 0;
+  bool PCRelative = false;
+};
+
+struct MCFixupRelocation final {
+  std::uint32_t Type = 0;
+  MCSymbolRef Symbol;
+  std::int64_t Addend = 0;
+};
+
+class MCAsmBackend {
+public:
+  virtual ~MCAsmBackend() = default;
+
+  [[nodiscard]] virtual Expected<MCFixupKindInfo> fixupKindInfo(MCFixupKind Kind) const = 0;
+  [[nodiscard]] virtual Expected<void> applyFixup(MCFixupKind Kind, std::span<std::uint8_t> Data,
+                                                  std::uint64_t Offset,
+                                                  std::int64_t Value) const = 0;
+  [[nodiscard]] virtual Expected<std::uint32_t> relocationType(const MCFixup &Fixup,
+                                                               const MCValue &Value) const = 0;
+  [[nodiscard]] virtual Expected<std::vector<MCFixupRelocation>>
+  relocationsForFixup(const MCFixup &Fixup, const MCValue &Value) const;
+
+  [[nodiscard]] virtual bool mayNeedRelaxation(const MCInst &) const noexcept {
+    return false;
+  }
+  [[nodiscard]] virtual Expected<bool> fixupNeedsRelaxation(const MCFixup &, std::int64_t) const {
+    return false;
+  }
+  [[nodiscard]] virtual Expected<MCInst> relaxInstruction(const MCInst &) const;
+
+  [[nodiscard]] virtual std::uint32_t objectFlags() const noexcept {
+    return 0;
+  }
+};
+
+} // namespace rcc::mc
+
+#endif // RCC_MC_MCASMBACKEND_H
diff --git a/backend/include/rcc/MC/MCAssembler.h b/backend/include/rcc/MC/MCAssembler.h
new file mode 100644
index 0000000..7a75498
--- /dev/null
+++ b/backend/include/rcc/MC/MCAssembler.h
@@ -0,0 +1,131 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_MC_MCASSEMBLER_H
+#define RCC_MC_MCASSEMBLER_H
+
+#include "rcc/MC/MCAsmBackend.h"
+#include "rcc/MC/MCCodeEmitter.h"
+#include "rcc/MC/MCDwarfFrameEmitter.h"
+#include "rcc/MC/MCObjectWriter.h"
+#include "rcc/MC/MCStreamer.h"
+#include "rcc/Support/Error.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <memory>
+#include <optional>
+#include <span>
+#include <unordered_map>
+#include <variant>
+#include <vector>
+
+namespace rcc::mc {
+
+class MCAssembler final {
+public:
+  MCAssembler(const MCCodeEmitter &Emitter, const MCAsmBackend &Backend) noexcept
+      : Emitter(&Emitter), Backend(&Backend) {}
+
+  [[nodiscard]] Expected<void> switchSection(MCSectionRef Section);
+  [[nodiscard]] Expected<void> emitLabel(MCSymbolRef Symbol);
+  [[nodiscard]] Expected<void> emitInstruction(const MCInst &Instruction);
+  [[nodiscard]] Expected<void> emitValue(MCExprRef Value, std::uint8_t Size);
+  [[nodiscard]] Expected<void> emitBytes(std::span<const std::uint8_t> Bytes);
+  [[nodiscard]] Expected<void> emitZeroFill(std::uint64_t Size);
+  [[nodiscard]] Expected<void> emitAlignment(std::uint64_t Alignment, std::uint8_t Fill,
+                                             std::uint64_t MaximumBytes);
+  [[nodiscard]] Expected<void> emitSymbolAttribute(MCSymbolRef Symbol, MCSymbolAttribute Attribute);
+  [[nodiscard]] Expected<void> emitSymbolSize(MCSymbolRef Symbol, MCExprRef Size);
+  [[nodiscard]] Expected<void> emitCommonSymbol(MCSymbolRef Symbol, std::uint64_t Size,
+                                                std::uint64_t Alignment);
+  [[nodiscard]] Expected<void> emitCFI(const MCCFIInstruction &Instruction);
+  [[nodiscard]] Expected<void> configureDwarfFrame(MCSectionRef Section, MCDwarfFrameInfo Info);
+
+  [[nodiscard]] Expected<MCAssembledObject> assemble();
+
+private:
+  struct InstructionFragment final {
+    MCInst Instruction;
+  };
+  struct DataFragment final {
+    std::vector<std::uint8_t> Bytes;
+    std::vector<MCFixup> Fixups;
+  };
+  struct AlignmentFragment final {
+    std::uint64_t Alignment = 1;
+    std::uint8_t Fill = 0;
+    std::uint64_t MaximumBytes = 0;
+  };
+  struct ZeroFillFragment final {
+    std::uint64_t Size = 0;
+  };
+  using FragmentPayload =
+      std::variant<InstructionFragment, DataFragment, AlignmentFragment, ZeroFillFragment>;
+
+  struct Fragment final {
+    FragmentPayload Payload;
+    std::uint64_t Offset = 0;
+    std::uint64_t Size = 0;
+    std::vector<std::uint8_t> EncodedBytes;
+    std::vector<MCFixup> Fixups;
+  };
+
+  struct SectionData final {
+    MCSectionRef Section;
+    std::vector<Fragment> Fragments;
+    std::uint64_t AddressSize = 0;
+    std::uint64_t Alignment = 1;
+  };
+
+  struct SymbolData final {
+    MCSymbolRef Symbol;
+    MCObjectSymbolBinding Binding = MCObjectSymbolBinding::Local;
+    bool BindingWasSet = false;
+    MCObjectSymbolType Type = MCObjectSymbolType::None;
+    MCObjectSymbolVisibility Visibility = MCObjectSymbolVisibility::Default;
+    std::optional<std::size_t> SectionIndex;
+    std::size_t FragmentIndex = 0;
+    MCExprRef Size;
+    std::uint64_t CommonSize = 0;
+    std::uint64_t CommonAlignment = 0;
+  };
+
+  struct CFIEvent final {
+    MCCFIInstruction Instruction;
+    std::size_t FragmentIndex = 0;
+  };
+
+  struct CFIProcedure final {
+    MCSymbolRef Function;
+    std::size_t SectionIndex = 0;
+    std::size_t BeginFragmentIndex = 0;
+    std::size_t EndFragmentIndex = 0;
+    std::vector<CFIEvent> Events;
+    bool IsClosed = false;
+  };
+
+  [[nodiscard]] Expected<std::size_t> currentSectionIndex() const;
+  [[nodiscard]] SymbolData &getOrCreateSymbol(MCSymbolRef Symbol);
+  [[nodiscard]] Expected<void> encodeFragments();
+  [[nodiscard]] Expected<bool> layoutAndRelax();
+  [[nodiscard]] Expected<MCAssembledObject> finalizeObject();
+  [[nodiscard]] Expected<void> appendDwarfFrame(MCAssembledObject &Object) const;
+  [[nodiscard]] std::optional<std::uint64_t> symbolOffset(const SymbolData &Symbol) const;
+
+  const MCCodeEmitter *Emitter;
+  const MCAsmBackend *Backend;
+  std::vector<SectionData> Sections;
+  std::unordered_map<const MCSection *, std::size_t> SectionIndices;
+  std::vector<SymbolData> Symbols;
+  std::unordered_map<const MCSymbol *, std::size_t> SymbolIndices;
+  std::optional<std::size_t> CurrentSection;
+  std::vector<CFIProcedure> CFIProcedures;
+  std::optional<std::size_t> ActiveCFIProcedure;
+  MCSectionRef EHFrameSection;
+  std::optional<MCDwarfFrameInfo> DwarfFrameInfo;
+  bool WasAssembled = false;
+};
+
+} // namespace rcc::mc
+
+#endif // RCC_MC_MCASSEMBLER_H
diff --git a/backend/include/rcc/MC/MCCodeEmitter.h b/backend/include/rcc/MC/MCCodeEmitter.h
new file mode 100644
index 0000000..7307a83
--- /dev/null
+++ b/backend/include/rcc/MC/MCCodeEmitter.h
@@ -0,0 +1,30 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_MC_MCCODEEMITTER_H
+#define RCC_MC_MCCODEEMITTER_H
+
+#include "rcc/MC/MCFixup.h"
+#include "rcc/MC/MCInst.h"
+#include "rcc/Support/Error.h"
+
+#include <cstdint>
+#include <vector>
+
+namespace rcc::mc {
+
+struct MCEncodedInstruction final {
+  std::vector<std::uint8_t> Bytes;
+  std::vector<MCFixup> Fixups;
+};
+
+class MCCodeEmitter {
+public:
+  virtual ~MCCodeEmitter() = default;
+
+  [[nodiscard]] virtual Expected<MCEncodedInstruction>
+  encodeInstruction(const MCInst &Instruction) const = 0;
+};
+
+} // namespace rcc::mc
+
+#endif // RCC_MC_MCCODEEMITTER_H
diff --git a/backend/include/rcc/MC/MCDwarfFrameEmitter.h b/backend/include/rcc/MC/MCDwarfFrameEmitter.h
new file mode 100644
index 0000000..f338f36
--- /dev/null
+++ b/backend/include/rcc/MC/MCDwarfFrameEmitter.h
@@ -0,0 +1,44 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_MC_MCDWARFFRAMEEMITTER_H
+#define RCC_MC_MCDWARFFRAMEEMITTER_H
+
+#include "rcc/MC/MCAsmBackend.h"
+#include "rcc/MC/MCCFI.h"
+#include "rcc/MC/MCObjectWriter.h"
+#include "rcc/Support/Error.h"
+
+#include <cstdint>
+#include <span>
+#include <vector>
+
+namespace rcc::mc {
+
+struct MCDwarfFrameInfo final {
+  std::uint64_t CodeAlignment = 1;
+  std::int64_t DataAlignment = -8;
+  std::uint32_t ReturnAddressRegister = 0;
+  std::uint32_t InitialCFARegister = 0;
+  std::uint64_t InitialCFAOffset = 0;
+
+  [[nodiscard]] Expected<void> verify() const;
+};
+
+struct MCDwarfFrameInstruction final {
+  MCCFIInstruction Instruction;
+  std::uint64_t Offset = 0;
+};
+
+struct MCDwarfFrameProcedure final {
+  MCSymbolRef Function;
+  std::uint64_t AddressRange = 0;
+  std::vector<MCDwarfFrameInstruction> Instructions;
+};
+
+[[nodiscard]] Expected<MCObjectSection>
+emitDwarfEHFrame(MCSectionRef Section, std::span<const MCDwarfFrameProcedure> Procedures,
+                 const MCDwarfFrameInfo &Info, const MCAsmBackend &Backend);
+
+} // namespace rcc::mc
+
+#endif // RCC_MC_MCDWARFFRAMEEMITTER_H
diff --git a/backend/include/rcc/MC/MCFixup.h b/backend/include/rcc/MC/MCFixup.h
new file mode 100644
index 0000000..3329fab
--- /dev/null
+++ b/backend/include/rcc/MC/MCFixup.h
@@ -0,0 +1,52 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_MC_MCFIXUP_H
+#define RCC_MC_MCFIXUP_H
+
+#include "rcc/MC/MCExpr.h"
+#include "rcc/Support/Error.h"
+
+#include <cstdint>
+
+namespace rcc::mc {
+
+using MCFixupKind = std::uint16_t;
+
+namespace fixup_kind {
+
+inline constexpr MCFixupKind None = 0;
+inline constexpr MCFixupKind Data1 = 1;
+inline constexpr MCFixupKind Data2 = 2;
+inline constexpr MCFixupKind Data4 = 3;
+inline constexpr MCFixupKind Data8 = 4;
+inline constexpr MCFixupKind PCRelative4 = 5;
+inline constexpr MCFixupKind FirstTarget = 256;
+
+} // namespace fixup_kind
+
+struct MCFixup final {
+  std::uint64_t Offset = 0;
+  MCExprRef Value;
+  MCFixupKind Kind = fixup_kind::None;
+  bool PCRelative = false;
+  bool LinkerRelaxable = false;
+
+  [[nodiscard]] Expected<void> verify() const;
+};
+
+struct MCValue final {
+  MCSymbolRef AddSymbol;
+  MCSymbolRef SubtractSymbol;
+  std::int64_t Addend = 0;
+  std::uint32_t TargetKind = 0;
+
+  [[nodiscard]] bool isAbsolute() const noexcept {
+    return !AddSymbol && !SubtractSymbol;
+  }
+};
+
+[[nodiscard]] Expected<MCValue> evaluateAsRelocatable(const MCExpr &Expression);
+
+} // namespace rcc::mc
+
+#endif // RCC_MC_MCFIXUP_H
diff --git a/backend/include/rcc/MC/MCObjectStreamer.h b/backend/include/rcc/MC/MCObjectStreamer.h
new file mode 100644
index 0000000..4a6b56c
--- /dev/null
+++ b/backend/include/rcc/MC/MCObjectStreamer.h
@@ -0,0 +1,59 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_MC_MCOBJECTSTREAMER_H
+#define RCC_MC_MCOBJECTSTREAMER_H
+
+#include "rcc/MC/MCAssembler.h"
+#include "rcc/MC/MCObjectWriter.h"
+#include "rcc/MC/MCStreamer.h"
+
+#include <cstdint>
+#include <span>
+#include <string_view>
+#include <vector>
+
+namespace rcc::mc {
+
+class ELFObjectStreamer final : public MCStreamer {
+public:
+  ELFObjectStreamer(const MCCodeEmitter &Emitter, const MCAsmBackend &Backend,
+                    const MCObjectWriter &Writer) noexcept
+      : Assembler(Emitter, Backend), Writer(&Writer) {}
+
+  [[nodiscard]] Expected<void> switchSection(MCSectionRef Section) override;
+  [[nodiscard]] Expected<void> emitLabel(MCSymbolRef Symbol) override;
+  [[nodiscard]] Expected<void> emitInstruction(const MCInst &Instruction) override;
+  [[nodiscard]] Expected<void> emitValue(MCExprRef Value, std::uint8_t Size) override;
+  [[nodiscard]] Expected<void> emitBytes(std::span<const std::uint8_t> Bytes) override;
+  [[nodiscard]] Expected<void> emitZeroFill(std::uint64_t Size) override;
+  [[nodiscard]] Expected<void> emitAlignment(std::uint64_t Alignment, std::uint8_t Fill = 0,
+                                             std::uint64_t MaximumBytes = 0) override;
+  [[nodiscard]] Expected<void> emitSymbolAttribute(MCSymbolRef Symbol,
+                                                   MCSymbolAttribute Attribute) override;
+  [[nodiscard]] Expected<void> emitSymbolSize(MCSymbolRef Symbol, MCExprRef Size) override;
+  [[nodiscard]] Expected<void> emitCommonSymbol(MCSymbolRef Symbol, std::uint64_t Size,
+                                                std::uint64_t Alignment) override;
+  [[nodiscard]] Expected<void> emitDirective(std::string_view Name,
+                                             std::string_view Arguments = {}) override;
+  [[nodiscard]] Expected<void> emitCFI(const MCCFIInstruction &Instruction) override;
+  [[nodiscard]] Expected<void> emitInlineAssembly(std::string_view Text) override;
+  [[nodiscard]] Expected<void> emitComment(std::string_view Text) override;
+  [[nodiscard]] Expected<void> finish() override;
+
+  [[nodiscard]] Expected<void> configureDwarfFrame(MCSectionRef Section, MCDwarfFrameInfo Info);
+
+  [[nodiscard]] Expected<std::vector<std::uint8_t>> takeOutput();
+
+private:
+  [[nodiscard]] Expected<void> ensureOpen() const;
+
+  MCAssembler Assembler;
+  const MCObjectWriter *Writer;
+  std::vector<std::uint8_t> Output;
+  bool IsFinished = false;
+  bool OutputWasTaken = false;
+};
+
+} // namespace rcc::mc
+
+#endif // RCC_MC_MCOBJECTSTREAMER_H
diff --git a/backend/include/rcc/MC/MCObjectWriter.h b/backend/include/rcc/MC/MCObjectWriter.h
new file mode 100644
index 0000000..16c6a50
--- /dev/null
+++ b/backend/include/rcc/MC/MCObjectWriter.h
@@ -0,0 +1,79 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_MC_MCOBJECTWRITER_H
+#define RCC_MC_MCOBJECTWRITER_H
+
+#include "rcc/MC/MCSection.h"
+#include "rcc/MC/MCSymbol.h"
+#include "rcc/Support/Error.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <optional>
+#include <vector>
+
+namespace rcc::mc {
+
+enum class MCObjectSymbolBinding : std::uint8_t {
+  Local,
+  Global,
+  Weak,
+};
+
+enum class MCObjectSymbolType : std::uint8_t {
+  None,
+  Function,
+  Object,
+  TLSObject,
+  Section,
+};
+
+enum class MCObjectSymbolVisibility : std::uint8_t {
+  Default,
+  Hidden,
+  Protected,
+};
+
+struct MCObjectRelocation final {
+  std::uint64_t Offset = 0;
+  std::uint32_t Type = 0;
+  MCSymbolRef Symbol;
+  std::int64_t Addend = 0;
+};
+
+struct MCObjectSection final {
+  MCSectionRef Section;
+  std::vector<std::uint8_t> Contents;
+  std::uint64_t AddressSize = 0;
+  std::uint64_t Alignment = 1;
+  std::vector<MCObjectRelocation> Relocations;
+};
+
+struct MCObjectSymbol final {
+  MCSymbolRef Symbol;
+  MCObjectSymbolBinding Binding = MCObjectSymbolBinding::Local;
+  MCObjectSymbolType Type = MCObjectSymbolType::None;
+  MCObjectSymbolVisibility Visibility = MCObjectSymbolVisibility::Default;
+  std::optional<std::size_t> SectionIndex;
+  std::uint64_t Value = 0;
+  std::uint64_t Size = 0;
+  std::uint64_t CommonAlignment = 0;
+};
+
+struct MCAssembledObject final {
+  std::vector<MCObjectSection> Sections;
+  std::vector<MCObjectSymbol> Symbols;
+  std::uint32_t Flags = 0;
+};
+
+class MCObjectWriter {
+public:
+  virtual ~MCObjectWriter() = default;
+
+  [[nodiscard]] virtual Expected<std::vector<std::uint8_t>>
+  writeObject(const MCAssembledObject &Object) const = 0;
+};
+
+} // namespace rcc::mc
+
+#endif // RCC_MC_MCOBJECTWRITER_H
diff --git a/backend/include/rcc/MC/MCStreamer.h b/backend/include/rcc/MC/MCStreamer.h
index 3add976..ea37178 100644
--- a/backend/include/rcc/MC/MCStreamer.h
+++ b/backend/include/rcc/MC/MCStreamer.h
@@ -44,6 +44,8 @@ public:
   [[nodiscard]] virtual Expected<void> emitSymbolAttribute(MCSymbolRef Symbol,
                                                            MCSymbolAttribute Attribute) = 0;
   [[nodiscard]] virtual Expected<void> emitSymbolSize(MCSymbolRef Symbol, MCExprRef Size) = 0;
+  [[nodiscard]] virtual Expected<void> emitCommonSymbol(MCSymbolRef Symbol, std::uint64_t Size,
+                                                        std::uint64_t Alignment) = 0;
   [[nodiscard]] virtual Expected<void> emitDirective(std::string_view Name,
                                                      std::string_view Arguments = {}) = 0;
   [[nodiscard]] virtual Expected<void> emitCFI(const MCCFIInstruction &Instruction) = 0;
@@ -67,6 +69,8 @@ public:
   [[nodiscard]] Expected<void> emitSymbolAttribute(MCSymbolRef Symbol,
                                                    MCSymbolAttribute Attribute) override;
   [[nodiscard]] Expected<void> emitSymbolSize(MCSymbolRef Symbol, MCExprRef Size) override;
+  [[nodiscard]] Expected<void> emitCommonSymbol(MCSymbolRef Symbol, std::uint64_t Size,
+                                                std::uint64_t Alignment) override;
   [[nodiscard]] Expected<void> emitDirective(std::string_view Name,
                                              std::string_view Arguments = {}) override;
   [[nodiscard]] Expected<void> emitCFI(const MCCFIInstruction &Instruction) override;