From a69d14b8ebc028dddc689658b08d42d3e83f5e38 Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Sat, 1 Aug 2026 14:19:20 +0800 Subject: [CodeGen] Add constant and jump table state Add stable, tombstone-preserving MachineConstantPool and MachineJumpTableInfo ownership. Define the versioned TargetConstant contract and integrate all table references with builders, verification, and deterministic deep cloning. --- backend/include/rcc/CodeGen/MachineConstantPool.h | 183 +++++++++++++++ backend/include/rcc/CodeGen/MachineFunction.h | 20 ++ backend/include/rcc/CodeGen/MachineIRBuilder.h | 2 + backend/include/rcc/CodeGen/MachineIRTypes.h | 6 + backend/include/rcc/CodeGen/MachineJumpTableInfo.h | 116 +++++++++ backend/include/rcc/CodeGen/TargetConstant.h | 259 +++++++++++++++++++++ 6 files changed, 586 insertions(+) create mode 100644 backend/include/rcc/CodeGen/MachineConstantPool.h create mode 100644 backend/include/rcc/CodeGen/MachineJumpTableInfo.h create mode 100644 backend/include/rcc/CodeGen/TargetConstant.h (limited to 'backend/include/rcc') diff --git a/backend/include/rcc/CodeGen/MachineConstantPool.h b/backend/include/rcc/CodeGen/MachineConstantPool.h new file mode 100644 index 0000000..cc9ae04 --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineConstantPool.h @@ -0,0 +1,183 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINECONSTANTPOOL_H +#define RCC_CODEGEN_MACHINECONSTANTPOOL_H + +#include "rcc/CodeGen/MachineIRTypes.h" +#include "rcc/CodeGen/MachineMemOperand.h" +#include "rcc/CodeGen/TargetConstant.h" +#include "rcc/Support/Error.h" + +#include +#include +#include +#include +#include +#include +#include +#include + +namespace rcc { + +enum class ConstantPoolEntryKind : std::uint8_t { + Generic, + Target, + SymbolDifference, + BlockAddress, + TargetExpression, +}; + +enum class ConstantPoolMergeKind : std::uint8_t { + Never, + Exact, +}; + +enum class ConstantPoolRelocationMode : std::uint8_t { + None, + Static, + PositionIndependent, + Target, +}; + +enum class ConstantPoolSectionKind : std::uint8_t { + TargetDefault, + ReadOnly, + MergeableReadOnly, + Data, + TextAdjacent, + Target, + Count, +}; + +struct ConstantPoolPlacement final { + ConstantPoolSectionKind Section = ConstantPoolSectionKind::TargetDefault; + bool UniqueSection = false; + std::optional MaximumDistance; + std::uint64_t TargetFlags = 0; + + friend bool operator==(const ConstantPoolPlacement &Left, + const ConstantPoolPlacement &Right) = default; +}; + +struct GenericConstantData final { + std::string TypeIdentity; + std::vector Bytes; + + friend bool operator==(const GenericConstantData &Left, + const GenericConstantData &Right) = default; +}; + +struct SymbolDifferenceConstant final { + std::string Minuend; + std::string Subtrahend; + std::int64_t Addend = 0; + + friend bool operator==(const SymbolDifferenceConstant &Left, + const SymbolDifferenceConstant &Right) = default; +}; + +struct BlockAddressConstant final { + std::string FunctionName; + std::string BlockName; + std::int64_t Addend = 0; + + friend bool operator==(const BlockAddressConstant &Left, + const BlockAddressConstant &Right) = default; +}; + +struct TargetExpressionConstant final { + TargetConstant Expression; +}; + +using MachineConstantPoolValue = + std::variant; + +struct MachineConstantPoolEntryDesc final { + MachineConstantPoolEntryDesc() = default; + MachineConstantPoolEntryDesc(const MachineConstantPoolEntryDesc &) = delete; + MachineConstantPoolEntryDesc &operator=(const MachineConstantPoolEntryDesc &) = delete; + MachineConstantPoolEntryDesc(MachineConstantPoolEntryDesc &&) noexcept = default; + MachineConstantPoolEntryDesc &operator=(MachineConstantPoolEntryDesc &&) noexcept = default; + ~MachineConstantPoolEntryDesc() = default; + + MachineConstantPoolValue Value; + std::uint64_t Size = 0; + Alignment Align; + ConstantPoolMergeKind Merge = ConstantPoolMergeKind::Never; + ConstantPoolRelocationMode Relocation = ConstantPoolRelocationMode::None; + ConstantPoolPlacement Placement; + + [[nodiscard]] ConstantPoolEntryKind kind() const noexcept; + [[nodiscard]] Expected verify() const; + [[nodiscard]] Expected clone() const; + [[nodiscard]] bool semanticallyEquals(const MachineConstantPoolEntryDesc &Other) const noexcept; +}; + +class MachineConstantPoolEntry final { +public: + [[nodiscard]] ConstantPoolIndex index() const noexcept { + return Index; + } + + [[nodiscard]] bool isTombstone() const noexcept { + return std::holds_alternative(Description); + } + + [[nodiscard]] const MachineConstantPoolEntryDesc *description() const noexcept { + return std::get_if(&Description); + } + + [[nodiscard]] Expected cloneDescription() const; + +private: + MachineConstantPoolEntry(ConstantPoolIndex Index, MachineConstantPoolEntryDesc Description) + : Index(Index), Description(std::move(Description)) {} + + ConstantPoolIndex Index; + std::variant Description; + + friend class MachineConstantPool; +}; + +class MachineConstantPool final { +public: + MachineConstantPool() = default; + MachineConstantPool(const MachineConstantPool &) = delete; + MachineConstantPool &operator=(const MachineConstantPool &) = delete; + MachineConstantPool(MachineConstantPool &&) noexcept = default; + MachineConstantPool &operator=(MachineConstantPool &&) noexcept = default; + ~MachineConstantPool() = default; + + [[nodiscard]] Expected addEntry(MachineConstantPoolEntryDesc Description); + [[nodiscard]] Expected updateEntry(ConstantPoolIndex Index, + MachineConstantPoolEntryDesc Description); + [[nodiscard]] Expected eraseEntry(ConstantPoolIndex Index); + + [[nodiscard]] const MachineConstantPoolEntry *entry(ConstantPoolIndex Index) const noexcept; + [[nodiscard]] std::span entries() const noexcept { + return Entries; + } + + [[nodiscard]] std::size_t liveEntryCount() const noexcept; + + [[nodiscard]] bool isFrozen() const noexcept { + return Frozen; + } + + [[nodiscard]] Expected freeze(); + [[nodiscard]] Expected verify() const; + +private: + [[nodiscard]] Expected mutableEntry(ConstantPoolIndex Index); + [[nodiscard]] const MachineConstantPoolEntry * + findEquivalent(const MachineConstantPoolEntryDesc &Description, + std::optional Excluded = std::nullopt) const noexcept; + + std::vector Entries; + bool Frozen = false; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINECONSTANTPOOL_H diff --git a/backend/include/rcc/CodeGen/MachineFunction.h b/backend/include/rcc/CodeGen/MachineFunction.h index 3e3fecb..38d88f9 100644 --- a/backend/include/rcc/CodeGen/MachineFunction.h +++ b/backend/include/rcc/CodeGen/MachineFunction.h @@ -3,8 +3,10 @@ #ifndef RCC_CODEGEN_MACHINEFUNCTION_H #define RCC_CODEGEN_MACHINEFUNCTION_H +#include "rcc/CodeGen/MachineConstantPool.h" #include "rcc/CodeGen/MachineFrameInfo.h" #include "rcc/CodeGen/MachineFunctionProperties.h" +#include "rcc/CodeGen/MachineJumpTableInfo.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/StableID.h" #include "rcc/Support/Error.h" @@ -61,6 +63,22 @@ public: return FrameInfo; } + [[nodiscard]] MachineConstantPool &constantPool() noexcept { + return ConstantPool; + } + + [[nodiscard]] const MachineConstantPool &constantPool() const noexcept { + return ConstantPool; + } + + [[nodiscard]] MachineJumpTableInfo &jumpTableInfo() noexcept { + return JumpTables; + } + + [[nodiscard]] const MachineJumpTableInfo &jumpTableInfo() const noexcept { + return JumpTables; + } + [[nodiscard]] MachineFunctionProperties &properties() noexcept { return Properties; } @@ -120,6 +138,8 @@ private: MachineFunctionStableID StableID; MachineRegisterInfo RegInfo; MachineFrameInfo FrameInfo; + MachineConstantPool ConstantPool; + MachineJumpTableInfo JumpTables; MachineFunctionProperties Properties; MachineBasicBlock *FirstBlock = nullptr; MachineBasicBlock *LastBlock = nullptr; diff --git a/backend/include/rcc/CodeGen/MachineIRBuilder.h b/backend/include/rcc/CodeGen/MachineIRBuilder.h index 3bd8d67..47fd63c 100644 --- a/backend/include/rcc/CodeGen/MachineIRBuilder.h +++ b/backend/include/rcc/CodeGen/MachineIRBuilder.h @@ -97,6 +97,8 @@ private: [[nodiscard]] Expected ensurePending() const; [[nodiscard]] Expected validateInsertionPoint() const; [[nodiscard]] Expected validateFrameReference(FrameIndex Index) const; + [[nodiscard]] Expected validateConstantPoolReference(ConstantPoolIndex Index) const; + [[nodiscard]] Expected validateJumpTableReference(JumpTableIndex Index) const; [[nodiscard]] Expected validateOperandOwnership(const MachineOperand &Operand) const; [[nodiscard]] std::vector collectOperandTies() const; [[nodiscard]] Expected appendRegister(Register Reg, RegisterOperandFlags Flags, diff --git a/backend/include/rcc/CodeGen/MachineIRTypes.h b/backend/include/rcc/CodeGen/MachineIRTypes.h index de6be5a..058cacb 100644 --- a/backend/include/rcc/CodeGen/MachineIRTypes.h +++ b/backend/include/rcc/CodeGen/MachineIRTypes.h @@ -55,6 +55,9 @@ struct AssemblyFormatIDTag; struct SyncScopeIDTag; struct MemoryAliasSourceIDTag; struct OriginIDTag; +struct TargetConstantTypeIDTag; +struct TargetFunctionStateTypeIDTag; +struct TargetRelocationKindIDTag; } // namespace detail @@ -74,6 +77,9 @@ using AssemblyFormatID = MachineIndex; using SyncScopeID = MachineIndex; using MemoryAliasSourceID = MachineIndex; using OriginID = MachineIndex; +using TargetConstantTypeID = MachineIndex; +using TargetFunctionStateTypeID = MachineIndex; +using TargetRelocationKindID = MachineIndex; class Opcode final { public: diff --git a/backend/include/rcc/CodeGen/MachineJumpTableInfo.h b/backend/include/rcc/CodeGen/MachineJumpTableInfo.h new file mode 100644 index 0000000..6342281 --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineJumpTableInfo.h @@ -0,0 +1,116 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINEJUMPTABLEINFO_H +#define RCC_CODEGEN_MACHINEJUMPTABLEINFO_H + +#include "rcc/CodeGen/MachineIRTypes.h" +#include "rcc/CodeGen/MachineMemOperand.h" +#include "rcc/Support/Error.h" + +#include +#include +#include +#include +#include +#include +#include + +namespace rcc { + +class MachineBasicBlock; +class MachineFunction; + +enum class JumpTableEntryEncoding : std::uint8_t { + AbsoluteAddress, + RelativeToTableBase, + RelativeToEntry, + CompressedOffset, + Target, + Count, +}; + +struct JumpTablePlacement final { + bool InTextSection = true; + bool UniqueSection = false; + std::optional MaximumDistance; + std::uint64_t TargetFlags = 0; + + friend bool operator==(const JumpTablePlacement &Left, const JumpTablePlacement &Right) = default; +}; + +struct MachineJumpTableDesc final { + JumpTableEntryEncoding Encoding = JumpTableEntryEncoding::AbsoluteAddress; + std::uint8_t EntrySize = 8; + Alignment Align; + std::vector Targets; + JumpTablePlacement Placement; + std::uint32_t TargetEncoding = 0; + + friend bool operator==(const MachineJumpTableDesc &Left, + const MachineJumpTableDesc &Right) = default; +}; + +class MachineJumpTableEntry final { +public: + [[nodiscard]] JumpTableIndex index() const noexcept { + return Index; + } + + [[nodiscard]] bool isTombstone() const noexcept { + return std::holds_alternative(Description); + } + + [[nodiscard]] const MachineJumpTableDesc *description() const noexcept { + return std::get_if(&Description); + } + +private: + MachineJumpTableEntry(JumpTableIndex Index, MachineJumpTableDesc Description) + : Index(Index), Description(std::move(Description)) {} + + JumpTableIndex Index; + std::variant Description; + + friend class MachineJumpTableInfo; +}; + +class MachineJumpTableInfo final { +public: + explicit MachineJumpTableInfo(MachineFunction &Owner) noexcept : Owner(&Owner) {} + + MachineJumpTableInfo(const MachineJumpTableInfo &) = delete; + MachineJumpTableInfo &operator=(const MachineJumpTableInfo &) = delete; + MachineJumpTableInfo(MachineJumpTableInfo &&) = delete; + MachineJumpTableInfo &operator=(MachineJumpTableInfo &&) = delete; + ~MachineJumpTableInfo() = default; + + [[nodiscard]] Expected createTable(MachineJumpTableDesc Description); + [[nodiscard]] Expected updateTable(JumpTableIndex Index, MachineJumpTableDesc Description); + [[nodiscard]] Expected eraseTable(JumpTableIndex Index); + + [[nodiscard]] const MachineJumpTableEntry *table(JumpTableIndex Index) const noexcept; + [[nodiscard]] std::span tables() const noexcept { + return Tables; + } + + [[nodiscard]] std::size_t liveTableCount() const noexcept; + + [[nodiscard]] bool isFrozen() const noexcept { + return Frozen; + } + + [[nodiscard]] Expected freeze(); + [[nodiscard]] Expected verify() const; + +private: + [[nodiscard]] Expected verifyDescription(const MachineJumpTableDesc &Description) const; + [[nodiscard]] Expected mutableTable(JumpTableIndex Index); + + MachineFunction *Owner; + std::vector Tables; + bool Frozen = false; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINEJUMPTABLEINFO_H diff --git a/backend/include/rcc/CodeGen/TargetConstant.h b/backend/include/rcc/CodeGen/TargetConstant.h new file mode 100644 index 0000000..37f352e --- /dev/null +++ b/backend/include/rcc/CodeGen/TargetConstant.h @@ -0,0 +1,259 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_TARGETCONSTANT_H +#define RCC_CODEGEN_TARGETCONSTANT_H + +#include "rcc/CodeGen/MachineIRTypes.h" +#include "rcc/CodeGen/MachineMemOperand.h" +#include "rcc/Support/Error.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +namespace rcc { + +struct TargetConstantFixup final { + std::uint64_t Offset = 0; + TargetRelocationKindID Kind; + std::string Symbol; + std::int64_t Addend = 0; + + friend bool operator==(const TargetConstantFixup &Left, + const TargetConstantFixup &Right) = default; +}; + +struct TargetConstantEmission final { + std::vector Bytes; + std::vector Fixups; + + [[nodiscard]] Expected verify() const; + + friend bool operator==(const TargetConstantEmission &Left, + const TargetConstantEmission &Right) = default; +}; + +struct EncodedTargetConstant final { + TargetConstantTypeID TypeID; + std::uint32_t Version = 0; + std::vector Payload; + + friend bool operator==(const EncodedTargetConstant &Left, + const EncodedTargetConstant &Right) = default; +}; + +template +concept TargetConstantValue = + std::move_constructible && + requires(const ValueT &Value, const ValueT &Other, std::uint32_t Version, + std::span Payload, std::string_view Text) { + { ValueT::stableTypeID() } -> std::same_as; + { ValueT::schemaVersion() } -> std::same_as; + { Value.verify() } -> std::same_as>; + { Value.clone() } -> std::same_as>; + { Value.stableHash() } -> std::same_as; + { Value.print() } -> std::same_as; + { Value.encode() } -> std::same_as>>; + { Value.emit() } -> std::same_as>; + { Value.requiredAlignment() } -> std::same_as; + { Value.relocationKind() } -> std::same_as>; + { Value == Other } -> std::convertible_to; + { ValueT::parse(Text) } -> std::same_as>; + { ValueT::decode(Version, Payload) } -> std::same_as>; + }; + +class TargetConstant final { +public: + TargetConstant() = default; + TargetConstant(const TargetConstant &) = delete; + TargetConstant &operator=(const TargetConstant &) = delete; + TargetConstant(TargetConstant &&) noexcept; + TargetConstant &operator=(TargetConstant &&) noexcept; + ~TargetConstant(); + + template + [[nodiscard]] static Expected create(ValueT Value) { + if (ValueT::stableTypeID().value() == 0) + return makeUnexpected(ErrorCode::InvalidArgument, "target constant TypeID must be nonzero"); + if (ValueT::schemaVersion() == 0) { + return makeUnexpected(ErrorCode::InvalidArgument, + "target constant schema version must be nonzero"); + } + auto Verification = Value.verify(); + if (!Verification) + return std::unexpected(Verification.error()); + + std::unique_ptr NewStorage = std::make_unique>(std::move(Value)); + return TargetConstant(std::move(NewStorage)); + } + + template + [[nodiscard]] static Expected parse(std::string_view Text) { + auto Value = ValueT::parse(Text); + if (!Value) + return std::unexpected(Value.error()); + return create(std::move(*Value)); + } + + template + [[nodiscard]] static Expected decode(const EncodedTargetConstant &Encoded) { + if (Encoded.TypeID != ValueT::stableTypeID()) { + return makeUnexpected(ErrorCode::ParseError, + "encoded target constant TypeID does not match its target schema"); + } + if (Encoded.Version == 0) + return makeUnexpected(ErrorCode::ParseError, "target constant version must be nonzero"); + auto Value = ValueT::decode(Encoded.Version, Encoded.Payload); + if (!Value) + return std::unexpected(Value.error()); + return create(std::move(*Value)); + } + + [[nodiscard]] bool hasValue() const noexcept { + return Storage != nullptr; + } + + [[nodiscard]] std::optional typeID() const noexcept; + [[nodiscard]] std::optional schemaVersion() const noexcept; + [[nodiscard]] Expected verify() const; + [[nodiscard]] Expected clone() const; + [[nodiscard]] Expected stableHash() const; + [[nodiscard]] Expected print() const; + [[nodiscard]] Expected encode() const; + [[nodiscard]] Expected emit() const; + [[nodiscard]] Expected requiredAlignment() const; + [[nodiscard]] Expected> relocationKind() const; + + [[nodiscard]] bool equals(const TargetConstant &Other) const noexcept; + + template [[nodiscard]] ValueT *getIf() noexcept { + if (!hasType()) + return nullptr; + return &static_cast *>(Storage.get())->value(); + } + + template [[nodiscard]] const ValueT *getIf() const noexcept { + if (!hasType()) + return nullptr; + return &static_cast *>(Storage.get())->value(); + } + +private: + class Concept { + public: + Concept() = default; + Concept(const Concept &) = delete; + Concept &operator=(const Concept &) = delete; + Concept(Concept &&) = delete; + Concept &operator=(Concept &&) = delete; + virtual ~Concept() = default; + + [[nodiscard]] virtual TargetConstantTypeID typeID() const noexcept = 0; + [[nodiscard]] virtual std::uint32_t schemaVersion() const noexcept = 0; + [[nodiscard]] virtual const void *localTypeToken() const noexcept = 0; + [[nodiscard]] virtual Expected verify() const = 0; + [[nodiscard]] virtual Expected> cloneStorage() const = 0; + [[nodiscard]] virtual std::uint64_t stableHash() const noexcept = 0; + [[nodiscard]] virtual std::string print() const = 0; + [[nodiscard]] virtual Expected> encodePayload() const = 0; + [[nodiscard]] virtual Expected emit() const = 0; + [[nodiscard]] virtual Alignment requiredAlignment() const noexcept = 0; + [[nodiscard]] virtual std::optional relocationKind() const noexcept = 0; + [[nodiscard]] virtual bool equals(const Concept &Other) const noexcept = 0; + }; + + template [[nodiscard]] static const void *typeToken() noexcept { + static const std::byte Token{}; + return &Token; + } + + template class Model final : public Concept { + public: + explicit Model(ValueT Value) : Value(std::move(Value)) {} + + [[nodiscard]] TargetConstantTypeID typeID() const noexcept override { + return ValueT::stableTypeID(); + } + + [[nodiscard]] std::uint32_t schemaVersion() const noexcept override { + return ValueT::schemaVersion(); + } + + [[nodiscard]] const void *localTypeToken() const noexcept override { + return TargetConstant::typeToken(); + } + + [[nodiscard]] Expected verify() const override { + return Value.verify(); + } + + [[nodiscard]] Expected> cloneStorage() const override { + auto Cloned = Value.clone(); + if (!Cloned) + return std::unexpected(Cloned.error()); + std::unique_ptr Result = std::make_unique>(std::move(*Cloned)); + return Result; + } + + [[nodiscard]] std::uint64_t stableHash() const noexcept override { + return Value.stableHash(); + } + + [[nodiscard]] std::string print() const override { + return Value.print(); + } + + [[nodiscard]] Expected> encodePayload() const override { + return Value.encode(); + } + + [[nodiscard]] Expected emit() const override { + return Value.emit(); + } + + [[nodiscard]] Alignment requiredAlignment() const noexcept override { + return Value.requiredAlignment(); + } + + [[nodiscard]] std::optional relocationKind() const noexcept override { + return Value.relocationKind(); + } + + [[nodiscard]] bool equals(const Concept &Other) const noexcept override { + if (Other.localTypeToken() != TargetConstant::typeToken()) + return false; + return Value == static_cast &>(Other).Value; + } + + [[nodiscard]] ValueT &value() noexcept { + return Value; + } + + [[nodiscard]] const ValueT &value() const noexcept { + return Value; + } + + private: + ValueT Value; + }; + + explicit TargetConstant(std::unique_ptr Storage) : Storage(std::move(Storage)) {} + + template [[nodiscard]] bool hasType() const noexcept { + return Storage != nullptr && Storage->typeID() == ValueT::stableTypeID() && + Storage->localTypeToken() == typeToken(); + } + + std::unique_ptr Storage; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_TARGETCONSTANT_H -- cgit v1.2.3