aboutsummaryrefslogtreecommitdiff
path: root/backend
diff options
context:
space:
mode:
Diffstat (limited to 'backend')
-rw-r--r--backend/include/rcc/CodeGen/MachineBasicBlock.h151
-rw-r--r--backend/include/rcc/CodeGen/MachineCFGUpdater.h39
-rw-r--r--backend/include/rcc/CodeGen/MachineFunction.h130
-rw-r--r--backend/include/rcc/CodeGen/MachineInstr.h164
-rw-r--r--backend/include/rcc/CodeGen/MachineMemOperand.h6
-rw-r--r--backend/include/rcc/CodeGen/MachineOperand.h344
-rw-r--r--backend/include/rcc/CodeGen/MachineRegisterInfo.h168
-rw-r--r--backend/lib/CodeGen/CMakeLists.txt24
-rw-r--r--backend/lib/CodeGen/MachineBasicBlock.cpp157
-rw-r--r--backend/lib/CodeGen/MachineCFGUpdater.cpp181
-rw-r--r--backend/lib/CodeGen/MachineFunction.cpp205
-rw-r--r--backend/lib/CodeGen/MachineInstr.cpp199
-rw-r--r--backend/lib/CodeGen/MachineOperand.cpp326
-rw-r--r--backend/lib/CodeGen/MachineRegisterInfo.cpp362
-rw-r--r--backend/unittests/CodeGen/CMakeLists.txt12
-rw-r--r--backend/unittests/CodeGen/MachineIRCoreTest.cpp467
16 files changed, 2935 insertions, 0 deletions
diff --git a/backend/include/rcc/CodeGen/MachineBasicBlock.h b/backend/include/rcc/CodeGen/MachineBasicBlock.h
new file mode 100644
index 0000000..ba59160
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MachineBasicBlock.h
@@ -0,0 +1,151 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_MACHINEBASICBLOCK_H
+#define RCC_CODEGEN_MACHINEBASICBLOCK_H
+
+#include "rcc/CodeGen/MachineIRTypes.h"
+#include "rcc/CodeGen/Register.h"
+#include "rcc/CodeGen/StableID.h"
+#include "rcc/Support/Error.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <optional>
+#include <span>
+#include <vector>
+
+namespace rcc {
+
+class MachineBasicBlock;
+class MachineCFGUpdater;
+class MachineFunction;
+class MachineInstr;
+
+struct MachineSuccessor final {
+ MachineBasicBlock *Block = nullptr;
+ BranchProbability Probability;
+
+ friend bool operator==(const MachineSuccessor &Left, const MachineSuccessor &Right) = default;
+};
+
+struct MachineBasicBlockLiveIn final {
+ PhysicalRegister PhysReg;
+ LaneMask Lanes = LaneMask::all();
+
+ friend bool operator==(const MachineBasicBlockLiveIn &Left,
+ const MachineBasicBlockLiveIn &Right) = default;
+};
+
+class MachineBasicBlock final {
+public:
+ MachineBasicBlock(const MachineBasicBlock &) = delete;
+ MachineBasicBlock &operator=(const MachineBasicBlock &) = delete;
+ MachineBasicBlock(MachineBasicBlock &&) = delete;
+ MachineBasicBlock &operator=(MachineBasicBlock &&) = delete;
+ ~MachineBasicBlock() = default;
+
+ [[nodiscard]] MachineBlockStableID stableID() const noexcept {
+ return StableID;
+ }
+
+ [[nodiscard]] MachineFunction &function() noexcept {
+ return *OwnerFunction;
+ }
+
+ [[nodiscard]] const MachineFunction &function() const noexcept {
+ return *OwnerFunction;
+ }
+
+ [[nodiscard]] bool isLinked() const noexcept {
+ return IsLinked;
+ }
+
+ [[nodiscard]] MachineBasicBlock *previous() noexcept {
+ return PreviousBlock;
+ }
+
+ [[nodiscard]] const MachineBasicBlock *previous() const noexcept {
+ return PreviousBlock;
+ }
+
+ [[nodiscard]] MachineBasicBlock *next() noexcept {
+ return NextBlock;
+ }
+
+ [[nodiscard]] const MachineBasicBlock *next() const noexcept {
+ return NextBlock;
+ }
+
+ [[nodiscard]] MachineInstr *firstInstruction() noexcept {
+ return FirstInstruction;
+ }
+
+ [[nodiscard]] const MachineInstr *firstInstruction() const noexcept {
+ return FirstInstruction;
+ }
+
+ [[nodiscard]] MachineInstr *lastInstruction() noexcept {
+ return LastInstruction;
+ }
+
+ [[nodiscard]] const MachineInstr *lastInstruction() const noexcept {
+ return LastInstruction;
+ }
+
+ [[nodiscard]] std::size_t instructionCount() const noexcept;
+ [[nodiscard]] Expected<void> appendInstruction(MachineInstr &Instruction);
+ [[nodiscard]] Expected<void> insertInstructionBefore(MachineInstr &Position,
+ MachineInstr &Instruction);
+ [[nodiscard]] Expected<void> insertInstructionAfter(MachineInstr &Position,
+ MachineInstr &Instruction);
+ [[nodiscard]] Expected<void> removeInstruction(MachineInstr &Instruction);
+ void clearInstructions() noexcept;
+
+ [[nodiscard]] std::span<MachineBasicBlock *const> predecessors() const noexcept {
+ return Predecessors;
+ }
+
+ [[nodiscard]] std::span<const MachineSuccessor> successors() const noexcept {
+ return Successors;
+ }
+
+ [[nodiscard]] Expected<void> addLiveIn(PhysicalRegister PhysReg,
+ LaneMask Lanes = LaneMask::all());
+ [[nodiscard]] Expected<void> removeLiveIn(PhysicalRegister PhysReg);
+ [[nodiscard]] std::span<const MachineBasicBlockLiveIn> liveIns() const noexcept {
+ return LiveIns;
+ }
+
+ [[nodiscard]] std::optional<std::uint32_t> denseNumber() const noexcept {
+ return DenseNumber;
+ }
+
+ [[nodiscard]] std::optional<std::uint32_t> layoutIndex() const noexcept {
+ return LayoutIndex;
+ }
+
+private:
+ MachineBasicBlock(MachineFunction &OwnerFunction, MachineBlockStableID StableID)
+ : OwnerFunction(&OwnerFunction), StableID(StableID) {}
+
+ MachineFunction *OwnerFunction;
+ MachineBlockStableID StableID;
+ bool IsLinked = false;
+ MachineBasicBlock *PreviousBlock = nullptr;
+ MachineBasicBlock *NextBlock = nullptr;
+ MachineInstr *FirstInstruction = nullptr;
+ MachineInstr *LastInstruction = nullptr;
+ std::vector<MachineBasicBlock *> Predecessors;
+ std::vector<MachineSuccessor> Successors;
+ std::vector<MachineBasicBlockLiveIn> LiveIns;
+ std::optional<std::uint32_t> DenseNumber;
+ std::optional<std::uint32_t> LayoutIndex;
+
+ friend class MachineArena;
+ friend class MachineCFGUpdater;
+ friend class MachineFunction;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_MACHINEBASICBLOCK_H
diff --git a/backend/include/rcc/CodeGen/MachineCFGUpdater.h b/backend/include/rcc/CodeGen/MachineCFGUpdater.h
new file mode 100644
index 0000000..4359538
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MachineCFGUpdater.h
@@ -0,0 +1,39 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_MACHINECFGUPDATER_H
+#define RCC_CODEGEN_MACHINECFGUPDATER_H
+
+#include "rcc/CodeGen/MachineIRTypes.h"
+#include "rcc/Support/Error.h"
+
+namespace rcc {
+
+class MachineBasicBlock;
+class MachineFunction;
+
+class MachineCFGUpdater final {
+public:
+ explicit MachineCFGUpdater(MachineFunction &Function) noexcept : Function(&Function) {}
+
+ [[nodiscard]] Expected<void>
+ addSuccessor(MachineBasicBlock &From, MachineBasicBlock &To,
+ BranchProbability Probability = BranchProbability::zero());
+ [[nodiscard]] Expected<void> removeSuccessor(MachineBasicBlock &From, MachineBasicBlock &To);
+ [[nodiscard]] Expected<void> replaceSuccessor(MachineBasicBlock &From,
+ MachineBasicBlock &OldTarget,
+ MachineBasicBlock &NewTarget);
+ [[nodiscard]] Expected<void> updateBranchProbability(MachineBasicBlock &From,
+ MachineBasicBlock &To,
+ BranchProbability Probability);
+ [[nodiscard]] Expected<void> transferSuccessors(MachineBasicBlock &From, MachineBasicBlock &To);
+ [[nodiscard]] Expected<void> disconnectBlock(MachineBasicBlock &Block);
+
+private:
+ [[nodiscard]] Expected<void> verifyOwnership(const MachineBasicBlock &Block) const;
+
+ MachineFunction *Function;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_MACHINECFGUPDATER_H
diff --git a/backend/include/rcc/CodeGen/MachineFunction.h b/backend/include/rcc/CodeGen/MachineFunction.h
new file mode 100644
index 0000000..487fb5b
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MachineFunction.h
@@ -0,0 +1,130 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_MACHINEFUNCTION_H
+#define RCC_CODEGEN_MACHINEFUNCTION_H
+
+#include "rcc/CodeGen/MachineFunctionProperties.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/StableID.h"
+#include "rcc/Support/Error.h"
+
+#include <cstddef>
+#include <memory>
+#include <span>
+#include <string>
+#include <string_view>
+#include <vector>
+
+namespace rcc {
+
+class MachineArena;
+class MachineBasicBlock;
+class MachineCFGUpdater;
+class MachineInstr;
+class MachineMemOperand;
+struct MachineMemOperandDesc;
+class Opcode;
+
+class MachineFunction final {
+public:
+ [[nodiscard]] static Expected<std::unique_ptr<MachineFunction>>
+ create(std::string Name, MachineFunctionStableID StableID);
+
+ MachineFunction(const MachineFunction &) = delete;
+ MachineFunction &operator=(const MachineFunction &) = delete;
+ MachineFunction(MachineFunction &&) = delete;
+ MachineFunction &operator=(MachineFunction &&) = delete;
+ ~MachineFunction();
+
+ [[nodiscard]] std::string_view name() const noexcept {
+ return Name;
+ }
+
+ [[nodiscard]] MachineFunctionStableID stableID() const noexcept {
+ return StableID;
+ }
+
+ [[nodiscard]] MachineRegisterInfo &registerInfo() noexcept {
+ return RegInfo;
+ }
+
+ [[nodiscard]] const MachineRegisterInfo &registerInfo() const noexcept {
+ return RegInfo;
+ }
+
+ [[nodiscard]] MachineFunctionProperties &properties() noexcept {
+ return Properties;
+ }
+
+ [[nodiscard]] const MachineFunctionProperties &properties() const noexcept {
+ return Properties;
+ }
+
+ [[nodiscard]] Expected<MachineBasicBlock *> createBasicBlock();
+ [[nodiscard]] Expected<MachineInstr *> createInstruction(Opcode InstructionOpcode);
+ [[nodiscard]] Expected<const MachineMemOperand *>
+ createMemOperand(MachineMemOperandDesc Description);
+
+ [[nodiscard]] Expected<void> appendBlock(MachineBasicBlock &Block);
+ [[nodiscard]] Expected<void> insertBlockBefore(MachineBasicBlock &Position,
+ MachineBasicBlock &Block);
+ [[nodiscard]] Expected<void> removeBlock(MachineBasicBlock &Block);
+
+ [[nodiscard]] MachineBasicBlock *firstBlock() noexcept {
+ return FirstBlock;
+ }
+
+ [[nodiscard]] const MachineBasicBlock *firstBlock() const noexcept {
+ return FirstBlock;
+ }
+
+ [[nodiscard]] MachineBasicBlock *lastBlock() noexcept {
+ return LastBlock;
+ }
+
+ [[nodiscard]] const MachineBasicBlock *lastBlock() const noexcept {
+ return LastBlock;
+ }
+
+ [[nodiscard]] std::size_t blockCount() const noexcept;
+ [[nodiscard]] std::span<MachineBasicBlock *const> allBlocks() const noexcept {
+ return AllBlocks;
+ }
+
+ [[nodiscard]] std::span<MachineInstr *const> allInstructions() const noexcept {
+ return AllInstructions;
+ }
+
+ [[nodiscard]] std::span<const MachineMemOperand *const> allMemOperands() const noexcept {
+ return AllMemOperands;
+ }
+
+ [[nodiscard]] bool ownsMemOperand(const MachineMemOperand &MemOperand) const noexcept;
+
+ [[nodiscard]] MachineCFGUpdater cfgUpdater() noexcept;
+ void renumberBlocks() noexcept;
+
+private:
+ MachineFunction(std::string Name, MachineFunctionStableID StableID);
+
+ std::string Name;
+ MachineFunctionStableID StableID;
+ MachineRegisterInfo RegInfo;
+ MachineFunctionProperties Properties;
+ MachineBasicBlock *FirstBlock = nullptr;
+ MachineBasicBlock *LastBlock = nullptr;
+ std::vector<MachineBasicBlock *> AllBlocks;
+ std::vector<MachineInstr *> AllInstructions;
+ std::vector<const MachineMemOperand *> AllMemOperands;
+ StableIDGenerator<MachineBlockStableID> BlockIDGenerator;
+ StableIDGenerator<MachineInstrStableID> InstrIDGenerator;
+ std::unique_ptr<MachineArena> Arena;
+
+ friend class MachineBasicBlock;
+ friend class MachineCFGUpdater;
+ friend class MachineInstr;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_MACHINEFUNCTION_H
diff --git a/backend/include/rcc/CodeGen/MachineInstr.h b/backend/include/rcc/CodeGen/MachineInstr.h
new file mode 100644
index 0000000..376273f
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MachineInstr.h
@@ -0,0 +1,164 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_MACHINEINSTR_H
+#define RCC_CODEGEN_MACHINEINSTR_H
+
+#include "rcc/CodeGen/MachineIRTypes.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/StableID.h"
+#include "rcc/Support/Error.h"
+
+#include <cstddef>
+#include <functional>
+#include <optional>
+#include <span>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+
+class MachineBasicBlock;
+class MachineFunction;
+class MachineMemOperand;
+class MachineRegisterInfo;
+
+class MachineInstr final {
+public:
+ MachineInstr(const MachineInstr &) = delete;
+ MachineInstr &operator=(const MachineInstr &) = delete;
+ MachineInstr(MachineInstr &&) = delete;
+ MachineInstr &operator=(MachineInstr &&) = delete;
+ ~MachineInstr();
+
+ [[nodiscard]] Opcode opcode() const noexcept {
+ return InstructionOpcode;
+ }
+
+ [[nodiscard]] Expected<void> setOpcode(Opcode NewOpcode);
+
+ [[nodiscard]] MachineInstrStableID stableID() const noexcept {
+ return StableID;
+ }
+
+ [[nodiscard]] MachineFunction &function() noexcept {
+ return *OwnerFunction;
+ }
+
+ [[nodiscard]] const MachineFunction &function() const noexcept {
+ return *OwnerFunction;
+ }
+
+ [[nodiscard]] MachineBasicBlock *parent() noexcept {
+ return ParentBlock;
+ }
+
+ [[nodiscard]] const MachineBasicBlock *parent() const noexcept {
+ return ParentBlock;
+ }
+
+ [[nodiscard]] MachineInstr *previous() noexcept {
+ return PreviousInstruction;
+ }
+
+ [[nodiscard]] const MachineInstr *previous() const noexcept {
+ return PreviousInstruction;
+ }
+
+ [[nodiscard]] MachineInstr *next() noexcept {
+ return NextInstruction;
+ }
+
+ [[nodiscard]] const MachineInstr *next() const noexcept {
+ return NextInstruction;
+ }
+
+ [[nodiscard]] bool isLinked() const noexcept {
+ return ParentBlock != nullptr;
+ }
+
+ [[nodiscard]] std::size_t operandCount() const noexcept {
+ return Operands.size();
+ }
+
+ [[nodiscard]] MachineOperand *operandAt(std::size_t Index) noexcept;
+ [[nodiscard]] const MachineOperand *operandAt(std::size_t Index) const noexcept;
+ [[nodiscard]] std::span<const MachineOperand> operands() const noexcept {
+ return Operands;
+ }
+
+ void reserveOperands(std::size_t Capacity);
+ [[nodiscard]] Expected<void> addOperand(MachineOperand Operand);
+ [[nodiscard]] Expected<void> insertOperand(std::size_t Index, MachineOperand Operand);
+ [[nodiscard]] Expected<void> eraseOperand(std::size_t Index);
+
+ [[nodiscard]] Expected<void> tieOperands(std::size_t DefIndex, std::size_t UseIndex);
+ [[nodiscard]] Expected<void> untieOperand(std::size_t Index);
+
+ [[nodiscard]] Expected<void> addMemOperand(const MachineMemOperand &MemOperand);
+ [[nodiscard]] Expected<void> eraseMemOperand(std::size_t Index);
+ [[nodiscard]] std::span<const MachineMemOperand *const> memOperands() const noexcept {
+ return MemOperands;
+ }
+
+ [[nodiscard]] MachineInstrFlags flags() const noexcept {
+ return Flags;
+ }
+
+ void setFlags(MachineInstrFlags NewFlags) noexcept {
+ Flags = NewFlags;
+ }
+
+ [[nodiscard]] const std::optional<SourceLocation> &sourceLocation() const noexcept {
+ return Location;
+ }
+
+ void setSourceLocation(SourceLocation NewLocation) {
+ Location = std::move(NewLocation);
+ }
+
+ void clearSourceLocation() noexcept {
+ Location.reset();
+ }
+
+ [[nodiscard]] std::optional<OriginID> origin() const noexcept {
+ return Origin;
+ }
+
+ void setOrigin(OriginID NewOrigin) noexcept {
+ Origin = NewOrigin;
+ }
+
+ void clearOrigin() noexcept {
+ Origin.reset();
+ }
+
+private:
+ MachineInstr(MachineFunction &OwnerFunction, Opcode InstructionOpcode,
+ MachineInstrStableID StableID);
+
+ [[nodiscard]] MachineRegisterInfo *linkedRegisterInfo() noexcept;
+ [[nodiscard]] Expected<void> attachToBlock(MachineBasicBlock &Block);
+ void detachFromBlock() noexcept;
+ void adjustTiesForInsertion(std::size_t Index) noexcept;
+ void adjustTiesForErasure(std::size_t Index) noexcept;
+
+ MachineFunction *OwnerFunction;
+ Opcode InstructionOpcode;
+ MachineInstrStableID StableID;
+ MachineBasicBlock *ParentBlock = nullptr;
+ MachineInstr *PreviousInstruction = nullptr;
+ MachineInstr *NextInstruction = nullptr;
+ std::vector<MachineOperand> Operands;
+ std::vector<const MachineMemOperand *> MemOperands;
+ MachineInstrFlags Flags;
+ std::optional<SourceLocation> Location;
+ std::optional<OriginID> Origin;
+
+ friend class MachineArena;
+ friend class MachineBasicBlock;
+ friend class MachineFunction;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_MACHINEINSTR_H
diff --git a/backend/include/rcc/CodeGen/MachineMemOperand.h b/backend/include/rcc/CodeGen/MachineMemOperand.h
index 52514f9..e513385 100644
--- a/backend/include/rcc/CodeGen/MachineMemOperand.h
+++ b/backend/include/rcc/CodeGen/MachineMemOperand.h
@@ -207,6 +207,12 @@ struct MachineMemOperandDesc final {
class MachineMemOperand final {
public:
+ MachineMemOperand(const MachineMemOperand &) = default;
+ MachineMemOperand &operator=(const MachineMemOperand &) = default;
+ MachineMemOperand(MachineMemOperand &&) noexcept = default;
+ MachineMemOperand &operator=(MachineMemOperand &&) noexcept = default;
+ ~MachineMemOperand() = default;
+
[[nodiscard]] static Expected<MachineMemOperand> create(MachineMemOperandDesc Description);
[[nodiscard]] const MachineMemOperandDesc &description() const noexcept {
diff --git a/backend/include/rcc/CodeGen/MachineOperand.h b/backend/include/rcc/CodeGen/MachineOperand.h
new file mode 100644
index 0000000..0da9f25
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MachineOperand.h
@@ -0,0 +1,344 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_MACHINEOPERAND_H
+#define RCC_CODEGEN_MACHINEOPERAND_H
+
+#include "rcc/CodeGen/LowLevelType.h"
+#include "rcc/CodeGen/MachineIRTypes.h"
+#include "rcc/CodeGen/Register.h"
+#include "rcc/CodeGen/RegisterMask.h"
+#include "rcc/Support/Error.h"
+
+#include <array>
+#include <cstddef>
+#include <cstdint>
+#include <initializer_list>
+#include <memory>
+#include <optional>
+#include <span>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <variant>
+
+namespace rcc {
+
+class MachineBasicBlock;
+class MachineInstr;
+class MachineRegisterInfo;
+class RegOperandIterator;
+
+class FloatingPointBits final {
+public:
+ [[nodiscard]] static Expected<FloatingPointBits> create(FloatSemantics Semantics,
+ std::span<const std::uint64_t> Words);
+
+ [[nodiscard]] FloatSemantics semantics() const noexcept {
+ return Semantics;
+ }
+
+ [[nodiscard]] std::uint32_t bitWidth() const noexcept {
+ return getFloatSemanticsBitWidth(Semantics).value_or(0);
+ }
+
+ [[nodiscard]] std::span<const std::uint64_t> words() const noexcept {
+ return std::span(Words).first(WordCount);
+ }
+
+ friend bool operator==(const FloatingPointBits &Left, const FloatingPointBits &Right) = default;
+
+private:
+ FloatingPointBits(FloatSemantics Semantics, std::array<std::uint64_t, 2> Words,
+ std::uint8_t WordCount) noexcept
+ : Semantics(Semantics), Words(Words), WordCount(WordCount) {}
+
+ FloatSemantics Semantics;
+ std::array<std::uint64_t, 2> Words;
+ std::uint8_t WordCount;
+};
+
+enum class RegisterOperandFlag : std::uint8_t {
+ Define,
+ Use,
+ Implicit,
+ Kill,
+ Dead,
+ Undef,
+ EarlyClobber,
+ InternalRead,
+ Renamable,
+ Debug,
+ Count,
+};
+
+class RegisterOperandFlags final {
+public:
+ constexpr RegisterOperandFlags() noexcept = default;
+
+ RegisterOperandFlags(std::initializer_list<RegisterOperandFlag> Flags) noexcept;
+
+ [[nodiscard]] constexpr bool has(RegisterOperandFlag Flag) const noexcept {
+ const auto Index = static_cast<std::uint16_t>(Flag);
+ if (Index >= static_cast<std::uint16_t>(RegisterOperandFlag::Count))
+ return false;
+ return (Mask & (std::uint16_t{1} << Index)) != 0;
+ }
+
+ constexpr void set(RegisterOperandFlag Flag) noexcept {
+ const auto Index = static_cast<std::uint16_t>(Flag);
+ if (Index < static_cast<std::uint16_t>(RegisterOperandFlag::Count))
+ Mask |= std::uint16_t{1} << Index;
+ }
+
+ constexpr void clear(RegisterOperandFlag Flag) noexcept {
+ const auto Index = static_cast<std::uint16_t>(Flag);
+ if (Index < static_cast<std::uint16_t>(RegisterOperandFlag::Count))
+ Mask &= static_cast<std::uint16_t>(~(std::uint16_t{1} << Index));
+ }
+
+ [[nodiscard]] constexpr std::uint16_t rawValue() const noexcept {
+ return Mask;
+ }
+
+ friend constexpr bool operator==(RegisterOperandFlags Left,
+ RegisterOperandFlags Right) noexcept = default;
+
+private:
+ std::uint16_t Mask = 0;
+};
+
+struct FloatingImmediateOperand final {
+ FloatingPointBits Bits;
+
+ friend bool operator==(const FloatingImmediateOperand &Left,
+ const FloatingImmediateOperand &Right) = default;
+};
+
+struct BasicBlockOperand final {
+ MachineBasicBlock *Block = nullptr;
+
+ friend bool operator==(BasicBlockOperand Left, BasicBlockOperand Right) noexcept = default;
+};
+
+struct FrameIndexOperand final {
+ FrameIndex Index;
+ std::int64_t Offset = 0;
+
+ friend constexpr bool operator==(FrameIndexOperand Left,
+ FrameIndexOperand Right) noexcept = default;
+};
+
+struct ConstantPoolOperand final {
+ ConstantPoolIndex Index;
+ std::int64_t Offset = 0;
+
+ friend constexpr bool operator==(ConstantPoolOperand Left,
+ ConstantPoolOperand Right) noexcept = default;
+};
+
+struct JumpTableOperand final {
+ JumpTableIndex Index;
+
+ friend constexpr bool operator==(JumpTableOperand Left,
+ JumpTableOperand Right) noexcept = default;
+};
+
+struct GlobalSymbolOperand final {
+ std::string Name;
+ std::int64_t Offset = 0;
+
+ friend bool operator==(const GlobalSymbolOperand &Left,
+ const GlobalSymbolOperand &Right) = default;
+};
+
+struct ExternalSymbolOperand final {
+ std::string Name;
+ std::int64_t Offset = 0;
+
+ friend bool operator==(const ExternalSymbolOperand &Left,
+ const ExternalSymbolOperand &Right) = default;
+};
+
+struct BlockAddressOperand final {
+ std::string FunctionName;
+ std::string BlockName;
+ std::int64_t Offset = 0;
+
+ friend bool operator==(const BlockAddressOperand &Left,
+ const BlockAddressOperand &Right) = default;
+};
+
+struct RegisterMaskOperand final {
+ std::shared_ptr<const RegisterMask> Mask;
+
+ friend bool operator==(const RegisterMaskOperand &Left,
+ const RegisterMaskOperand &Right) = default;
+};
+
+struct MetadataOperand final {
+ std::string Marker;
+
+ friend bool operator==(const MetadataOperand &Left, const MetadataOperand &Right) = default;
+};
+
+struct TargetIndexOperand final {
+ TargetIndex Index;
+ std::int64_t Offset = 0;
+
+ friend constexpr bool operator==(TargetIndexOperand Left,
+ TargetIndexOperand Right) noexcept = default;
+};
+
+struct MCSymbolOperand final {
+ std::string Name;
+ std::int64_t Offset = 0;
+
+ friend bool operator==(const MCSymbolOperand &Left, const MCSymbolOperand &Right) = default;
+};
+
+class MachineOperand final {
+public:
+ enum class Kind : std::uint8_t {
+ Register,
+ Immediate,
+ FloatingImmediate,
+ BasicBlock,
+ FrameIndex,
+ ConstantPoolIndex,
+ JumpTableIndex,
+ GlobalSymbol,
+ ExternalSymbol,
+ BlockAddress,
+ RegisterMask,
+ Metadata,
+ TargetIndex,
+ MCSymbol,
+ };
+
+ MachineOperand(const MachineOperand &) = delete;
+ MachineOperand &operator=(const MachineOperand &) = delete;
+ MachineOperand(MachineOperand &&Other) noexcept;
+ MachineOperand &operator=(MachineOperand &&Other) noexcept;
+ ~MachineOperand();
+
+ [[nodiscard]] static Expected<MachineOperand> registerOperand(Register Reg,
+ RegisterOperandFlags Flags,
+ SubRegIndex SubReg = {},
+ std::uint32_t TargetFlags = 0);
+ [[nodiscard]] static MachineOperand immediate(std::int64_t Value, std::uint32_t TargetFlags = 0);
+ [[nodiscard]] static MachineOperand floatingImmediate(FloatingPointBits Bits,
+ std::uint32_t TargetFlags = 0);
+ [[nodiscard]] static MachineOperand basicBlock(MachineBasicBlock &Block,
+ std::uint32_t TargetFlags = 0);
+ [[nodiscard]] static MachineOperand frameIndex(FrameIndex Index, std::int64_t Offset = 0,
+ std::uint32_t TargetFlags = 0);
+ [[nodiscard]] static MachineOperand constantPool(ConstantPoolIndex Index, std::int64_t Offset = 0,
+ std::uint32_t TargetFlags = 0);
+ [[nodiscard]] static MachineOperand jumpTable(JumpTableIndex Index,
+ std::uint32_t TargetFlags = 0);
+ [[nodiscard]] static Expected<MachineOperand>
+ globalSymbol(std::string Name, std::int64_t Offset = 0, std::uint32_t TargetFlags = 0);
+ [[nodiscard]] static Expected<MachineOperand>
+ externalSymbol(std::string Name, std::int64_t Offset = 0, std::uint32_t TargetFlags = 0);
+ [[nodiscard]] static Expected<MachineOperand> blockAddress(std::string FunctionName,
+ std::string BlockName,
+ std::int64_t Offset = 0,
+ std::uint32_t TargetFlags = 0);
+ [[nodiscard]] static Expected<MachineOperand>
+ registerMask(std::shared_ptr<const RegisterMask> Mask, std::uint32_t TargetFlags = 0);
+ [[nodiscard]] static Expected<MachineOperand> metadata(std::string Marker,
+ std::uint32_t TargetFlags = 0);
+ [[nodiscard]] static MachineOperand targetIndex(TargetIndex Index, std::int64_t Offset = 0,
+ std::uint32_t TargetFlags = 0);
+ [[nodiscard]] static Expected<MachineOperand> mcSymbol(std::string Name, std::int64_t Offset = 0,
+ std::uint32_t TargetFlags = 0);
+
+ [[nodiscard]] Kind kind() const noexcept {
+ return OperandKind;
+ }
+
+ [[nodiscard]] bool isRegister() const noexcept {
+ return OperandKind == Kind::Register;
+ }
+
+ [[nodiscard]] std::optional<Register> registerValue() const noexcept;
+ [[nodiscard]] RegisterOperandFlags registerFlags() const noexcept {
+ return RegFlags;
+ }
+ [[nodiscard]] SubRegIndex subReg() const noexcept {
+ return RegSubReg;
+ }
+ [[nodiscard]] bool isDef() const noexcept;
+ [[nodiscard]] bool isUse() const noexcept;
+ [[nodiscard]] bool isDebugUse() const noexcept;
+ [[nodiscard]] bool isImplicit() const noexcept;
+
+ [[nodiscard]] Expected<void> setRegister(Register Reg);
+ [[nodiscard]] Expected<void> setRegisterFlags(RegisterOperandFlags Flags);
+ [[nodiscard]] Expected<void> setSubReg(SubRegIndex SubReg);
+
+ [[nodiscard]] std::optional<std::size_t> tiedOperandIndex() const noexcept {
+ return TiedOperandIndex;
+ }
+
+ [[nodiscard]] std::uint32_t targetFlags() const noexcept {
+ return TargetFlags;
+ }
+
+ void setTargetFlags(std::uint32_t NewTargetFlags) noexcept {
+ TargetFlags = NewTargetFlags;
+ }
+
+ [[nodiscard]] MachineInstr *parent() noexcept {
+ return Parent;
+ }
+
+ [[nodiscard]] const MachineInstr *parent() const noexcept {
+ return Parent;
+ }
+
+ template <typename PayloadT> [[nodiscard]] const PayloadT *getIf() const noexcept {
+ return std::get_if<PayloadT>(&Storage);
+ }
+
+ [[nodiscard]] MachineOperand cloneDetached() const;
+
+private:
+ using OperandStorage =
+ std::variant<Register, std::int64_t, FloatingImmediateOperand, BasicBlockOperand,
+ FrameIndexOperand, ConstantPoolOperand, JumpTableOperand, GlobalSymbolOperand,
+ ExternalSymbolOperand, BlockAddressOperand, RegisterMaskOperand, MetadataOperand,
+ TargetIndexOperand, MCSymbolOperand>;
+
+ MachineOperand(Kind OperandKind, OperandStorage Storage, std::uint32_t TargetFlags = 0)
+ : OperandKind(OperandKind), Storage(std::move(Storage)), TargetFlags(TargetFlags) {}
+
+ [[nodiscard]] static Expected<void> verifyRegisterFlags(RegisterOperandFlags Flags);
+ void attachTo(MachineInstr &Instruction, MachineRegisterInfo *RegInfo);
+ void detachFromInstruction() noexcept;
+ void linkToRegInfo(MachineRegisterInfo &RegInfo);
+ void unlinkFromRegInfo() noexcept;
+ void takeRegLinkFrom(MachineOperand &Other) noexcept;
+ void setTiedOperandIndex(std::optional<std::size_t> Index) noexcept {
+ TiedOperandIndex = Index;
+ }
+
+ Kind OperandKind;
+ OperandStorage Storage;
+ RegisterOperandFlags RegFlags;
+ SubRegIndex RegSubReg;
+ std::optional<std::size_t> TiedOperandIndex;
+ std::uint32_t TargetFlags = 0;
+ MachineInstr *Parent = nullptr;
+ MachineRegisterInfo *LinkedRegInfo = nullptr;
+ MachineOperand **PreviousRegLink = nullptr;
+ MachineOperand *NextRegOperand = nullptr;
+
+ friend class MachineInstr;
+ friend class MachineRegisterInfo;
+ friend class RegOperandIterator;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_MACHINEOPERAND_H
diff --git a/backend/include/rcc/CodeGen/MachineRegisterInfo.h b/backend/include/rcc/CodeGen/MachineRegisterInfo.h
new file mode 100644
index 0000000..495853a
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MachineRegisterInfo.h
@@ -0,0 +1,168 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_MACHINEREGISTERINFO_H
+#define RCC_CODEGEN_MACHINEREGISTERINFO_H
+
+#include "rcc/CodeGen/LowLevelType.h"
+#include "rcc/CodeGen/MachineIRTypes.h"
+#include "rcc/CodeGen/Register.h"
+#include "rcc/Support/Error.h"
+
+#include <cstddef>
+#include <functional>
+#include <iterator>
+#include <memory>
+#include <optional>
+#include <span>
+#include <unordered_map>
+#include <vector>
+
+namespace rcc {
+
+class MachineOperand;
+
+class RegOperandIterator final {
+public:
+ using difference_type = std::ptrdiff_t; // NOLINT(readability-identifier-naming)
+ using value_type = MachineOperand; // NOLINT(readability-identifier-naming)
+ using pointer = MachineOperand *; // NOLINT(readability-identifier-naming)
+ using reference = MachineOperand &; // NOLINT(readability-identifier-naming)
+ using iterator_category = // NOLINT(readability-identifier-naming)
+ std::forward_iterator_tag;
+
+ RegOperandIterator() = default;
+
+ [[nodiscard]] reference operator*() const noexcept;
+ [[nodiscard]] pointer operator->() const noexcept;
+ RegOperandIterator &operator++() noexcept;
+ RegOperandIterator operator++(int) noexcept;
+
+ friend bool operator==(const RegOperandIterator &Left, const RegOperandIterator &Right) noexcept {
+ return Left.Current == Right.Current;
+ }
+
+private:
+ RegOperandIterator(MachineOperand *Current, bool RequireUse, bool RequireDef,
+ bool SkipDebug) noexcept;
+
+ void skipFiltered() noexcept;
+
+ MachineOperand *Current = nullptr;
+ bool RequireUse = false;
+ bool RequireDef = false;
+ bool SkipDebug = false;
+
+ friend class RegOperandRange;
+ friend class MachineRegisterInfo;
+};
+
+class RegOperandRange final {
+public:
+ [[nodiscard]] RegOperandIterator begin() const noexcept {
+ return RegOperandIterator(Head, RequireUse, RequireDef, SkipDebug);
+ }
+
+ [[nodiscard]] RegOperandIterator end() const noexcept {
+ return {};
+ }
+
+private:
+ RegOperandRange(MachineOperand *Head, bool RequireUse, bool RequireDef, bool SkipDebug) noexcept
+ : Head(Head), RequireUse(RequireUse), RequireDef(RequireDef), SkipDebug(SkipDebug) {}
+
+ MachineOperand *Head = nullptr;
+ bool RequireUse = false;
+ bool RequireDef = false;
+ bool SkipDebug = false;
+
+ friend class MachineRegisterInfo;
+};
+
+struct VirtualRegisterInfo final {
+ std::optional<LLT> Type;
+ std::optional<RegisterBankID> Bank;
+ std::optional<RegisterClassID> RegClass;
+ std::vector<PhysicalRegister> AllocationHints;
+ bool IsTombstone = false;
+};
+
+struct PhysicalRegisterLiveIn final {
+ PhysicalRegister PhysReg;
+ std::optional<Register> InitialVirtualRegister;
+
+ friend bool operator==(const PhysicalRegisterLiveIn &Left,
+ const PhysicalRegisterLiveIn &Right) = default;
+};
+
+class MachineRegisterInfo final {
+public:
+ MachineRegisterInfo() = default;
+ MachineRegisterInfo(const MachineRegisterInfo &) = delete;
+ MachineRegisterInfo &operator=(const MachineRegisterInfo &) = delete;
+ MachineRegisterInfo(MachineRegisterInfo &&) = delete;
+ MachineRegisterInfo &operator=(MachineRegisterInfo &&) = delete;
+ ~MachineRegisterInfo();
+
+ [[nodiscard]] Expected<Register> createVirtualRegister();
+ [[nodiscard]] Expected<Register> createVirtualRegister(LLT Type);
+ [[nodiscard]] Expected<void> eraseVirtualRegister(Register Reg);
+
+ [[nodiscard]] bool isKnownVirtualRegister(Register Reg) const noexcept;
+ [[nodiscard]] Expected<std::reference_wrapper<VirtualRegisterInfo>>
+ virtualRegisterInfo(Register Reg);
+ [[nodiscard]] Expected<std::reference_wrapper<const VirtualRegisterInfo>>
+ virtualRegisterInfo(Register Reg) const;
+
+ [[nodiscard]] Expected<void> setType(Register Reg, LLT Type);
+ [[nodiscard]] Expected<void> clearType(Register Reg);
+ [[nodiscard]] Expected<void> setRegisterBank(Register Reg, RegisterBankID Bank);
+ [[nodiscard]] Expected<void> clearRegisterBank(Register Reg);
+ [[nodiscard]] Expected<void> setRegisterClass(Register Reg, RegisterClassID RegClass);
+ [[nodiscard]] Expected<void> clearRegisterClass(Register Reg);
+ [[nodiscard]] Expected<void> addAllocationHint(Register Reg, PhysicalRegister Hint);
+ void clearAllVirtualRegisterTypes() noexcept;
+
+ [[nodiscard]] Expected<void>
+ addLiveIn(PhysicalRegister PhysReg,
+ std::optional<Register> InitialVirtualRegister = std::nullopt);
+ [[nodiscard]] std::span<const PhysicalRegisterLiveIn> liveIns() const noexcept {
+ return LiveIns;
+ }
+
+ [[nodiscard]] Expected<void> reservePhysicalRegister(PhysicalRegister PhysReg);
+ [[nodiscard]] bool isReserved(PhysicalRegister PhysReg) const noexcept;
+ [[nodiscard]] std::span<const PhysicalRegister> reservedRegisters() const noexcept {
+ return ReservedRegisters;
+ }
+
+ [[nodiscard]] RegOperandRange regOperands(Register Reg) noexcept;
+ [[nodiscard]] RegOperandRange regNoDebugOperands(Register Reg) noexcept;
+ [[nodiscard]] RegOperandRange useOperands(Register Reg, bool IncludeDebug = true) noexcept;
+ [[nodiscard]] RegOperandRange defOperands(Register Reg) noexcept;
+
+ [[nodiscard]] bool useEmpty(Register Reg, bool IncludeDebug = true) const noexcept;
+ [[nodiscard]] bool hasOneUse(Register Reg, bool IncludeDebug = true) const noexcept;
+ [[nodiscard]] const MachineOperand *getUniqueVRegDef(Register Reg) const noexcept;
+ [[nodiscard]] Expected<std::size_t> replaceRegWith(Register OldReg, Register NewReg);
+
+ [[nodiscard]] Expected<void> verifyDefUseChains() const;
+
+private:
+ struct RegOperandListHead final {
+ MachineOperand *Head = nullptr;
+ };
+
+ [[nodiscard]] MachineOperand *headFor(Register Reg) const noexcept;
+ void linkOperand(MachineOperand &Operand);
+
+ std::vector<VirtualRegisterInfo> VirtualRegisters;
+ std::vector<PhysicalRegisterLiveIn> LiveIns;
+ std::vector<PhysicalRegister> ReservedRegisters;
+ std::unordered_map<Register, std::unique_ptr<RegOperandListHead>> DefUseHeads;
+
+ friend class MachineOperand;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_MACHINEREGISTERINFO_H
diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt
index 8a45878..ffa5e82 100644
--- a/backend/lib/CodeGen/CMakeLists.txt
+++ b/backend/lib/CodeGen/CMakeLists.txt
@@ -3,8 +3,14 @@
set(
RCCBackendCodeGenSources
LowLevelType.cpp
+ MachineBasicBlock.cpp
+ MachineCFGUpdater.cpp
+ MachineFunction.cpp
MachineIRTypes.cpp
+ MachineInstr.cpp
MachineMemOperand.cpp
+ MachineOperand.cpp
+ MachineRegisterInfo.cpp
MachineFunctionProperties.cpp
Register.cpp
RegisterMask.cpp
@@ -12,8 +18,14 @@ set(
set(
RCCBackendCodeGenHeaders
"${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LowLevelType.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineBasicBlock.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineCFGUpdater.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunction.h"
"${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineIRTypes.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineInstr.h"
"${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineMemOperand.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineOperand.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineRegisterInfo.h"
"${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunctionProperties.h"
"${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/Register.h"
"${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegisterMask.h"
@@ -50,8 +62,14 @@ install(
rcc_backend_register_format_files(
"${CMAKE_CURRENT_SOURCE_DIR}/LowLevelType.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MachineBasicBlock.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MachineCFGUpdater.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunction.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineIRTypes.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MachineInstr.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineMemOperand.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperand.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/Register.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/RegisterMask.cpp"
@@ -59,8 +77,14 @@ rcc_backend_register_format_files(
)
rcc_backend_register_tidy_files(
"${CMAKE_CURRENT_SOURCE_DIR}/LowLevelType.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MachineBasicBlock.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MachineCFGUpdater.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunction.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineIRTypes.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MachineInstr.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineMemOperand.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperand.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/Register.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/RegisterMask.cpp"
diff --git a/backend/lib/CodeGen/MachineBasicBlock.cpp b/backend/lib/CodeGen/MachineBasicBlock.cpp
new file mode 100644
index 0000000..a8d69f6
--- /dev/null
+++ b/backend/lib/CodeGen/MachineBasicBlock.cpp
@@ -0,0 +1,157 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineBasicBlock.h"
+
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+
+#include <algorithm>
+#include <cstddef>
+
+namespace rcc {
+
+std::size_t MachineBasicBlock::instructionCount() const noexcept {
+ std::size_t Count = 0;
+ for (const MachineInstr *Instruction = FirstInstruction; Instruction != nullptr;
+ Instruction = Instruction->next()) {
+ ++Count;
+ }
+ return Count;
+}
+
+Expected<void> MachineBasicBlock::appendInstruction(MachineInstr &Instruction) {
+ if (&Instruction.function() != OwnerFunction) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "instruction belongs to another machine function");
+ }
+ if (Instruction.isLinked()) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "instruction is already linked to a basic block");
+ }
+
+ auto AttachResult = Instruction.attachToBlock(*this);
+ if (!AttachResult)
+ return std::unexpected(AttachResult.error());
+
+ Instruction.PreviousInstruction = LastInstruction;
+ Instruction.NextInstruction = nullptr;
+ if (LastInstruction != nullptr)
+ LastInstruction->NextInstruction = &Instruction;
+ else
+ FirstInstruction = &Instruction;
+ LastInstruction = &Instruction;
+ return {};
+}
+
+Expected<void> MachineBasicBlock::insertInstructionBefore(MachineInstr &Position,
+ MachineInstr &Instruction) {
+ if (Position.parent() != this) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "instruction insertion position is not in this block");
+ }
+ if (&Instruction.function() != OwnerFunction || Instruction.isLinked()) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "inserted instruction is linked or belongs to another function");
+ }
+
+ auto AttachResult = Instruction.attachToBlock(*this);
+ if (!AttachResult)
+ return std::unexpected(AttachResult.error());
+
+ Instruction.PreviousInstruction = Position.PreviousInstruction;
+ Instruction.NextInstruction = &Position;
+ if (Position.PreviousInstruction != nullptr)
+ Position.PreviousInstruction->NextInstruction = &Instruction;
+ else
+ FirstInstruction = &Instruction;
+ Position.PreviousInstruction = &Instruction;
+ return {};
+}
+
+Expected<void> MachineBasicBlock::insertInstructionAfter(MachineInstr &Position,
+ MachineInstr &Instruction) {
+ if (Position.parent() != this) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "instruction insertion position is not in this block");
+ }
+ if (&Instruction.function() != OwnerFunction || Instruction.isLinked()) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "inserted instruction is linked or belongs to another function");
+ }
+
+ auto AttachResult = Instruction.attachToBlock(*this);
+ if (!AttachResult)
+ return std::unexpected(AttachResult.error());
+
+ Instruction.PreviousInstruction = &Position;
+ Instruction.NextInstruction = Position.NextInstruction;
+ if (Position.NextInstruction != nullptr)
+ Position.NextInstruction->PreviousInstruction = &Instruction;
+ else
+ LastInstruction = &Instruction;
+ Position.NextInstruction = &Instruction;
+ return {};
+}
+
+Expected<void> MachineBasicBlock::removeInstruction(MachineInstr &Instruction) {
+ if (Instruction.parent() != this) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "instruction does not belong to this block");
+ }
+
+ if (Instruction.PreviousInstruction != nullptr)
+ Instruction.PreviousInstruction->NextInstruction = Instruction.NextInstruction;
+ else
+ FirstInstruction = Instruction.NextInstruction;
+
+ if (Instruction.NextInstruction != nullptr)
+ Instruction.NextInstruction->PreviousInstruction = Instruction.PreviousInstruction;
+ else
+ LastInstruction = Instruction.PreviousInstruction;
+
+ Instruction.detachFromBlock();
+ return {};
+}
+
+void MachineBasicBlock::clearInstructions() noexcept {
+ MachineInstr *Instruction = FirstInstruction;
+ while (Instruction != nullptr) {
+ MachineInstr *NextInstruction = Instruction->NextInstruction;
+ Instruction->detachFromBlock();
+ Instruction = NextInstruction;
+ }
+ FirstInstruction = nullptr;
+ LastInstruction = nullptr;
+}
+
+Expected<void> MachineBasicBlock::addLiveIn(PhysicalRegister PhysReg, LaneMask Lanes) {
+ if (!PhysReg.isValid() || Lanes.empty()) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "block live-in requires a physical register and nonempty lanes");
+ }
+
+ const auto Position =
+ std::ranges::find_if(LiveIns, [PhysReg](const MachineBasicBlockLiveIn &LiveIn) {
+ return LiveIn.PhysReg == PhysReg;
+ });
+ if (Position != LiveIns.end()) {
+ Position->Lanes = Position->Lanes | Lanes;
+ return {};
+ }
+
+ LiveIns.push_back(MachineBasicBlockLiveIn{PhysReg, Lanes});
+ return {};
+}
+
+Expected<void> MachineBasicBlock::removeLiveIn(PhysicalRegister PhysReg) {
+ const auto Position =
+ std::ranges::find_if(LiveIns, [PhysReg](const MachineBasicBlockLiveIn &LiveIn) {
+ return LiveIn.PhysReg == PhysReg;
+ });
+ if (Position == LiveIns.end()) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "block physical live-in is not present");
+ }
+ LiveIns.erase(Position);
+ return {};
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/MachineCFGUpdater.cpp b/backend/lib/CodeGen/MachineCFGUpdater.cpp
new file mode 100644
index 0000000..c78e318
--- /dev/null
+++ b/backend/lib/CodeGen/MachineCFGUpdater.cpp
@@ -0,0 +1,181 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineCFGUpdater.h"
+
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <optional>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] std::optional<std::size_t> findSuccessorIndex(const MachineBasicBlock &From,
+ const MachineBasicBlock &To) {
+ const auto Successors = From.successors();
+ for (std::size_t Index = 0; Index < Successors.size(); ++Index) {
+ if (Successors[Index].Block == &To)
+ return Index;
+ }
+ return std::nullopt;
+}
+
+} // namespace
+
+Expected<void> MachineCFGUpdater::verifyOwnership(const MachineBasicBlock &Block) const {
+ if (&Block.function() != Function) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "CFG block belongs to another machine function");
+ }
+ return {};
+}
+
+Expected<void> MachineCFGUpdater::addSuccessor(MachineBasicBlock &From, MachineBasicBlock &To,
+ BranchProbability Probability) {
+ auto FromOwnership = verifyOwnership(From);
+ if (!FromOwnership)
+ return std::unexpected(FromOwnership.error());
+ auto ToOwnership = verifyOwnership(To);
+ if (!ToOwnership)
+ return std::unexpected(ToOwnership.error());
+
+ const auto Existing = findSuccessorIndex(From, To);
+ if (Existing) {
+ From.Successors[*Existing].Probability =
+ From.Successors[*Existing].Probability.saturatingAdd(Probability);
+ return {};
+ }
+
+ From.Successors.push_back(MachineSuccessor{&To, Probability});
+ if (std::ranges::find(To.Predecessors, &From) == To.Predecessors.end())
+ To.Predecessors.push_back(&From);
+ return {};
+}
+
+Expected<void> MachineCFGUpdater::removeSuccessor(MachineBasicBlock &From, MachineBasicBlock &To) {
+ auto FromOwnership = verifyOwnership(From);
+ if (!FromOwnership)
+ return std::unexpected(FromOwnership.error());
+ auto ToOwnership = verifyOwnership(To);
+ if (!ToOwnership)
+ return std::unexpected(ToOwnership.error());
+
+ const auto Successor = findSuccessorIndex(From, To);
+ if (!Successor) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "CFG successor edge is not present");
+ }
+ From.Successors.erase(From.Successors.begin() + static_cast<std::ptrdiff_t>(*Successor));
+
+ const auto Predecessor = std::ranges::find(To.Predecessors, &From);
+ if (Predecessor == To.Predecessors.end()) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "CFG successor has no reciprocal predecessor");
+ }
+ To.Predecessors.erase(Predecessor);
+ return {};
+}
+
+Expected<void> MachineCFGUpdater::replaceSuccessor(MachineBasicBlock &From,
+ MachineBasicBlock &OldTarget,
+ MachineBasicBlock &NewTarget) {
+ auto FromOwnership = verifyOwnership(From);
+ if (!FromOwnership)
+ return std::unexpected(FromOwnership.error());
+ auto OldOwnership = verifyOwnership(OldTarget);
+ if (!OldOwnership)
+ return std::unexpected(OldOwnership.error());
+ auto NewOwnership = verifyOwnership(NewTarget);
+ if (!NewOwnership)
+ return std::unexpected(NewOwnership.error());
+
+ if (&OldTarget == &NewTarget)
+ return {};
+
+ const auto Existing = findSuccessorIndex(From, OldTarget);
+ if (!Existing) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "replaced CFG successor edge is not present");
+ }
+ const BranchProbability Probability = From.Successors[*Existing].Probability;
+
+ auto RemoveResult = removeSuccessor(From, OldTarget);
+ if (!RemoveResult)
+ return std::unexpected(RemoveResult.error());
+ auto AddResult = addSuccessor(From, NewTarget, Probability);
+ if (!AddResult) {
+ auto RestoreResult = addSuccessor(From, OldTarget, Probability);
+ if (!RestoreResult) {
+ return makeUnexpected(ErrorCode::InternalError,
+ "failed to restore CFG edge after replacement failure");
+ }
+ return std::unexpected(AddResult.error());
+ }
+ return {};
+}
+
+Expected<void> MachineCFGUpdater::updateBranchProbability(MachineBasicBlock &From,
+ MachineBasicBlock &To,
+ BranchProbability Probability) {
+ auto FromOwnership = verifyOwnership(From);
+ if (!FromOwnership)
+ return std::unexpected(FromOwnership.error());
+ auto ToOwnership = verifyOwnership(To);
+ if (!ToOwnership)
+ return std::unexpected(ToOwnership.error());
+
+ const auto Successor = findSuccessorIndex(From, To);
+ if (!Successor) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "updated CFG successor edge is not present");
+ }
+ From.Successors[*Successor].Probability = Probability;
+ return {};
+}
+
+Expected<void> MachineCFGUpdater::transferSuccessors(MachineBasicBlock &From,
+ MachineBasicBlock &To) {
+ auto FromOwnership = verifyOwnership(From);
+ if (!FromOwnership)
+ return std::unexpected(FromOwnership.error());
+ auto ToOwnership = verifyOwnership(To);
+ if (!ToOwnership)
+ return std::unexpected(ToOwnership.error());
+ if (&From == &To)
+ return {};
+
+ const std::vector<MachineSuccessor> Successors = From.Successors;
+ for (const MachineSuccessor &Successor : Successors) {
+ auto RemoveResult = removeSuccessor(From, *Successor.Block);
+ if (!RemoveResult)
+ return std::unexpected(RemoveResult.error());
+ auto AddResult = addSuccessor(To, *Successor.Block, Successor.Probability);
+ if (!AddResult)
+ return std::unexpected(AddResult.error());
+ }
+ return {};
+}
+
+Expected<void> MachineCFGUpdater::disconnectBlock(MachineBasicBlock &Block) {
+ auto Ownership = verifyOwnership(Block);
+ if (!Ownership)
+ return std::unexpected(Ownership.error());
+
+ const std::vector<MachineSuccessor> Successors = Block.Successors;
+ for (const MachineSuccessor &Successor : Successors) {
+ auto Result = removeSuccessor(Block, *Successor.Block);
+ if (!Result)
+ return std::unexpected(Result.error());
+ }
+
+ const std::vector<MachineBasicBlock *> Predecessors = Block.Predecessors;
+ for (MachineBasicBlock *Predecessor : Predecessors) {
+ auto Result = removeSuccessor(*Predecessor, Block);
+ if (!Result)
+ return std::unexpected(Result.error());
+ }
+ return {};
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/MachineFunction.cpp b/backend/lib/CodeGen/MachineFunction.cpp
new file mode 100644
index 0000000..e19c115
--- /dev/null
+++ b/backend/lib/CodeGen/MachineFunction.cpp
@@ -0,0 +1,205 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineFunction.h"
+
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineCFGUpdater.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineMemOperand.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <memory>
+#include <memory_resource>
+#include <new>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+
+class MachineArena final {
+public:
+ MachineArena() = default;
+ MachineArena(const MachineArena &) = delete;
+ MachineArena &operator=(const MachineArena &) = delete;
+ MachineArena(MachineArena &&) = delete;
+ MachineArena &operator=(MachineArena &&) = delete;
+
+ ~MachineArena() {
+ for (auto Position = Destructors.rbegin(); Position != Destructors.rend(); ++Position)
+ Position->Destroy(Position->Object);
+ }
+
+ template <typename ObjectT, typename... ArgumentTs>
+ [[nodiscard]] ObjectT *create(ArgumentTs &&...Arguments) {
+ void *Storage = Resource.allocate(sizeof(ObjectT), alignof(ObjectT));
+ ObjectT *Object = ::new (Storage) ObjectT(std::forward<ArgumentTs>(Arguments)...);
+ try {
+ Destructors.push_back(DestructorRecord{
+ Object,
+ [](void *RawObject) noexcept { std::destroy_at(static_cast<ObjectT *>(RawObject)); },
+ });
+ } catch (...) {
+ std::destroy_at(Object);
+ throw;
+ }
+ return Object;
+ }
+
+private:
+ struct DestructorRecord final {
+ void *Object;
+ void (*Destroy)(void *) noexcept;
+ };
+
+ std::pmr::monotonic_buffer_resource Resource;
+ std::vector<DestructorRecord> Destructors;
+};
+
+Expected<std::unique_ptr<MachineFunction>>
+MachineFunction::create(std::string Name, MachineFunctionStableID StableID) {
+ if (Name.empty())
+ return makeUnexpected(ErrorCode::InvalidArgument, "machine function name cannot be empty");
+ if (!StableID.isValid())
+ return makeUnexpected(ErrorCode::InvalidArgument, "machine function StableID must be valid");
+ return std::unique_ptr<MachineFunction>(new MachineFunction(std::move(Name), StableID));
+}
+
+MachineFunction::MachineFunction(std::string Name, MachineFunctionStableID StableID)
+ : Name(std::move(Name)), StableID(StableID), Arena(std::make_unique<MachineArena>()) {}
+
+MachineFunction::~MachineFunction() {
+ for (MachineBasicBlock *Block = FirstBlock; Block != nullptr; Block = Block->NextBlock) {
+ Block->clearInstructions();
+ Block->Predecessors.clear();
+ Block->Successors.clear();
+ }
+}
+
+Expected<MachineBasicBlock *> MachineFunction::createBasicBlock() {
+ auto ID = BlockIDGenerator.allocate();
+ if (!ID)
+ return std::unexpected(ID.error());
+ MachineBasicBlock *Block = Arena->create<MachineBasicBlock>(*this, *ID);
+ AllBlocks.push_back(Block);
+ return Block;
+}
+
+Expected<MachineInstr *> MachineFunction::createInstruction(Opcode InstructionOpcode) {
+ if (!InstructionOpcode.isValid())
+ return makeUnexpected(ErrorCode::InvalidArgument, "machine opcode must be nonzero");
+
+ auto ID = InstrIDGenerator.allocate();
+ if (!ID)
+ return std::unexpected(ID.error());
+ MachineInstr *Instruction = Arena->create<MachineInstr>(*this, InstructionOpcode, *ID);
+ AllInstructions.push_back(Instruction);
+ return Instruction;
+}
+
+Expected<const MachineMemOperand *>
+MachineFunction::createMemOperand(MachineMemOperandDesc Description) {
+ auto MemOperand = MachineMemOperand::create(std::move(Description));
+ if (!MemOperand)
+ return std::unexpected(MemOperand.error());
+
+ const MachineMemOperand *Stored = Arena->create<MachineMemOperand>(std::move(*MemOperand));
+ AllMemOperands.push_back(Stored);
+ return Stored;
+}
+
+Expected<void> MachineFunction::appendBlock(MachineBasicBlock &Block) {
+ if (Block.OwnerFunction != this)
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "basic block belongs to another machine function");
+ if (Block.IsLinked)
+ return makeUnexpected(ErrorCode::InvalidArgument, "basic block is already linked");
+
+ Block.PreviousBlock = LastBlock;
+ Block.NextBlock = nullptr;
+ if (LastBlock != nullptr)
+ LastBlock->NextBlock = &Block;
+ else
+ FirstBlock = &Block;
+ LastBlock = &Block;
+ Block.IsLinked = true;
+ renumberBlocks();
+ return {};
+}
+
+Expected<void> MachineFunction::insertBlockBefore(MachineBasicBlock &Position,
+ MachineBasicBlock &Block) {
+ if (Position.OwnerFunction != this || !Position.IsLinked)
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "block insertion position is not linked to this function");
+ if (Block.OwnerFunction != this || Block.IsLinked)
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "inserted block is linked or belongs to another function");
+
+ Block.PreviousBlock = Position.PreviousBlock;
+ Block.NextBlock = &Position;
+ if (Position.PreviousBlock != nullptr)
+ Position.PreviousBlock->NextBlock = &Block;
+ else
+ FirstBlock = &Block;
+ Position.PreviousBlock = &Block;
+ Block.IsLinked = true;
+ renumberBlocks();
+ return {};
+}
+
+Expected<void> MachineFunction::removeBlock(MachineBasicBlock &Block) {
+ if (Block.OwnerFunction != this || !Block.IsLinked)
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "removed block is not linked to this function");
+ if (!Block.Predecessors.empty() || !Block.Successors.empty()) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "disconnect CFG edges before removing a basic block");
+ }
+
+ Block.clearInstructions();
+ if (Block.PreviousBlock != nullptr)
+ Block.PreviousBlock->NextBlock = Block.NextBlock;
+ else
+ FirstBlock = Block.NextBlock;
+ if (Block.NextBlock != nullptr)
+ Block.NextBlock->PreviousBlock = Block.PreviousBlock;
+ else
+ LastBlock = Block.PreviousBlock;
+
+ Block.IsLinked = false;
+ Block.PreviousBlock = nullptr;
+ Block.NextBlock = nullptr;
+ Block.DenseNumber.reset();
+ Block.LayoutIndex.reset();
+ renumberBlocks();
+ return {};
+}
+
+std::size_t MachineFunction::blockCount() const noexcept {
+ std::size_t Count = 0;
+ for (const MachineBasicBlock *Block = FirstBlock; Block != nullptr; Block = Block->next()) {
+ ++Count;
+ }
+ return Count;
+}
+
+bool MachineFunction::ownsMemOperand(const MachineMemOperand &MemOperand) const noexcept {
+ return std::ranges::find(AllMemOperands, &MemOperand) != AllMemOperands.end();
+}
+
+MachineCFGUpdater MachineFunction::cfgUpdater() noexcept {
+ return MachineCFGUpdater(*this);
+}
+
+void MachineFunction::renumberBlocks() noexcept {
+ std::uint32_t Number = 0;
+ for (MachineBasicBlock *Block = FirstBlock; Block != nullptr; Block = Block->NextBlock) {
+ Block->DenseNumber = Number;
+ Block->LayoutIndex = Number;
+ ++Number;
+ }
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/MachineInstr.cpp b/backend/lib/CodeGen/MachineInstr.cpp
new file mode 100644
index 0000000..3692258
--- /dev/null
+++ b/backend/lib/CodeGen/MachineInstr.cpp
@@ -0,0 +1,199 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineInstr.h"
+
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineMemOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+
+#include <cstddef>
+#include <functional>
+#include <optional>
+#include <utility>
+
+namespace rcc {
+
+MachineInstr::MachineInstr(MachineFunction &OwnerFunction, Opcode InstructionOpcode,
+ MachineInstrStableID StableID)
+ : OwnerFunction(&OwnerFunction), InstructionOpcode(InstructionOpcode), StableID(StableID) {}
+
+MachineInstr::~MachineInstr() {
+ for (MachineOperand &Operand : Operands)
+ Operand.detachFromInstruction();
+}
+
+Expected<void> MachineInstr::setOpcode(Opcode NewOpcode) {
+ if (!NewOpcode.isValid())
+ return makeUnexpected(ErrorCode::InvalidArgument, "machine opcode must be nonzero");
+ InstructionOpcode = NewOpcode;
+ return {};
+}
+
+MachineOperand *MachineInstr::operandAt(std::size_t Index) noexcept {
+ if (Index >= Operands.size())
+ return nullptr;
+ return &Operands[Index];
+}
+
+const MachineOperand *MachineInstr::operandAt(std::size_t Index) const noexcept {
+ if (Index >= Operands.size())
+ return nullptr;
+ return &Operands[Index];
+}
+
+void MachineInstr::reserveOperands(std::size_t Capacity) {
+ Operands.reserve(Capacity);
+}
+
+Expected<void> MachineInstr::addOperand(MachineOperand Operand) {
+ return insertOperand(Operands.size(), std::move(Operand));
+}
+
+Expected<void> MachineInstr::insertOperand(std::size_t Index, MachineOperand Operand) {
+ if (Index > Operands.size())
+ return makeUnexpected(ErrorCode::InvalidArgument, "operand insertion index is out of range");
+ if (Operand.Parent != nullptr)
+ return makeUnexpected(ErrorCode::InvalidArgument, "operand already belongs to an instruction");
+ if (Operand.TiedOperandIndex)
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "detached operand cannot carry a tied operand index");
+ if (const auto *BlockOperand = Operand.getIf<BasicBlockOperand>();
+ BlockOperand != nullptr && &BlockOperand->Block->function() != OwnerFunction) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "basic block operand belongs to another machine function");
+ }
+ if (const Register *Reg = Operand.getIf<Register>();
+ Reg != nullptr && Reg->isVirtual() &&
+ !OwnerFunction->registerInfo().isKnownVirtualRegister(*Reg)) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "register operand references an unknown virtual register");
+ }
+
+ Operands.insert(Operands.begin() + static_cast<std::ptrdiff_t>(Index), std::move(Operand));
+ adjustTiesForInsertion(Index);
+ Operands[Index].attachTo(*this, linkedRegisterInfo());
+ return {};
+}
+
+Expected<void> MachineInstr::eraseOperand(std::size_t Index) {
+ if (Index >= Operands.size())
+ return makeUnexpected(ErrorCode::InvalidArgument, "operand erase index is out of range");
+
+ adjustTiesForErasure(Index);
+ Operands.erase(Operands.begin() + static_cast<std::ptrdiff_t>(Index));
+ return {};
+}
+
+Expected<void> MachineInstr::tieOperands(std::size_t DefIndex, std::size_t UseIndex) {
+ if (DefIndex >= Operands.size() || UseIndex >= Operands.size() || DefIndex == UseIndex) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "tied operand indices are invalid");
+ }
+
+ MachineOperand &DefOperand = Operands[DefIndex];
+ MachineOperand &UseOperand = Operands[UseIndex];
+ if (!DefOperand.isRegister() || !UseOperand.isRegister() || !DefOperand.isDef() ||
+ !UseOperand.isUse()) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "tie must connect a register definition and use");
+ }
+ if (DefOperand.TiedOperandIndex || UseOperand.TiedOperandIndex) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "an operand cannot participate in more than one tie");
+ }
+
+ DefOperand.setTiedOperandIndex(UseIndex);
+ UseOperand.setTiedOperandIndex(DefIndex);
+ return {};
+}
+
+Expected<void> MachineInstr::untieOperand(std::size_t Index) {
+ if (Index >= Operands.size())
+ return makeUnexpected(ErrorCode::InvalidArgument, "operand tie index is out of range");
+ const auto OtherIndex = Operands[Index].TiedOperandIndex;
+ if (!OtherIndex)
+ return makeUnexpected(ErrorCode::InvalidArgument, "operand is not tied");
+ if (*OtherIndex >= Operands.size() || Operands[*OtherIndex].TiedOperandIndex != Index) {
+ return makeUnexpected(ErrorCode::VerificationError, "operand tie relation is not reciprocal");
+ }
+
+ Operands[*OtherIndex].setTiedOperandIndex(std::nullopt);
+ Operands[Index].setTiedOperandIndex(std::nullopt);
+ return {};
+}
+
+Expected<void> MachineInstr::addMemOperand(const MachineMemOperand &MemOperand) {
+ if (!OwnerFunction->ownsMemOperand(MemOperand)) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "machine memory operand belongs to another function");
+ }
+ MemOperands.push_back(&MemOperand);
+ return {};
+}
+
+Expected<void> MachineInstr::eraseMemOperand(std::size_t Index) {
+ if (Index >= MemOperands.size()) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "machine memory operand index is out of range");
+ }
+ MemOperands.erase(MemOperands.begin() + static_cast<std::ptrdiff_t>(Index));
+ return {};
+}
+
+MachineRegisterInfo *MachineInstr::linkedRegisterInfo() noexcept {
+ if (!isLinked())
+ return nullptr;
+ return &OwnerFunction->registerInfo();
+}
+
+Expected<void> MachineInstr::attachToBlock(MachineBasicBlock &Block) {
+ if (ParentBlock != nullptr) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "instruction is already linked to a basic block");
+ }
+
+ MachineRegisterInfo &RegInfo = OwnerFunction->registerInfo();
+ for (const MachineOperand &Operand : Operands) {
+ const Register *Reg = Operand.getIf<Register>();
+ if (Reg != nullptr && Reg->isVirtual() && !RegInfo.isKnownVirtualRegister(*Reg)) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "instruction references an unknown virtual register");
+ }
+ }
+
+ ParentBlock = &Block;
+ for (MachineOperand &Operand : Operands) {
+ const Register *Reg = Operand.getIf<Register>();
+ if (Reg != nullptr && !Reg->isNoRegister())
+ Operand.linkToRegInfo(RegInfo);
+ }
+ return {};
+}
+
+void MachineInstr::detachFromBlock() noexcept {
+ for (MachineOperand &Operand : Operands)
+ Operand.unlinkFromRegInfo();
+ ParentBlock = nullptr;
+ PreviousInstruction = nullptr;
+ NextInstruction = nullptr;
+}
+
+void MachineInstr::adjustTiesForInsertion(std::size_t Index) noexcept {
+ for (MachineOperand &Operand : Operands) {
+ if (Operand.TiedOperandIndex && *Operand.TiedOperandIndex >= Index)
+ ++*Operand.TiedOperandIndex;
+ }
+}
+
+void MachineInstr::adjustTiesForErasure(std::size_t Index) noexcept {
+ for (MachineOperand &Operand : Operands) {
+ if (!Operand.TiedOperandIndex)
+ continue;
+ if (*Operand.TiedOperandIndex == Index)
+ Operand.TiedOperandIndex.reset();
+ else if (*Operand.TiedOperandIndex > Index)
+ --*Operand.TiedOperandIndex;
+ }
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/MachineOperand.cpp b/backend/lib/CodeGen/MachineOperand.cpp
new file mode 100644
index 0000000..0e5febd
--- /dev/null
+++ b/backend/lib/CodeGen/MachineOperand.cpp
@@ -0,0 +1,326 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineOperand.h"
+
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+
+#include <algorithm>
+#include <array>
+#include <cstdint>
+#include <memory>
+#include <span>
+#include <utility>
+
+namespace rcc {
+
+Expected<FloatingPointBits> FloatingPointBits::create(FloatSemantics Semantics,
+ std::span<const std::uint64_t> Words) {
+ const auto BitWidth = getFloatSemanticsBitWidth(Semantics);
+ if (!BitWidth) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "floating immediate has unknown semantics");
+ }
+
+ const std::size_t RequiredWords = (*BitWidth + 63U) / 64U;
+ if (RequiredWords > 2 || Words.size() != RequiredWords) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "floating immediate bit pattern has the wrong word count");
+ }
+
+ const std::uint32_t UsedBitsInLastWord = *BitWidth % 64U;
+ if (UsedBitsInLastWord != 0 && (Words.back() >> UsedBitsInLastWord) != 0) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "floating immediate has nonzero bits above its semantics width");
+ }
+
+ std::array<std::uint64_t, 2> StoredWords{};
+ std::ranges::copy(Words, StoredWords.begin());
+ return FloatingPointBits(Semantics, StoredWords, static_cast<std::uint8_t>(RequiredWords));
+}
+
+RegisterOperandFlags::RegisterOperandFlags(
+ std::initializer_list<RegisterOperandFlag> Flags) noexcept {
+ for (const RegisterOperandFlag Flag : Flags)
+ set(Flag);
+}
+
+Expected<void> MachineOperand::verifyRegisterFlags(RegisterOperandFlags Flags) {
+ const bool IsDef = Flags.has(RegisterOperandFlag::Define);
+ const bool IsUse = Flags.has(RegisterOperandFlag::Use);
+ if (!IsDef && !IsUse) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "register operand must be a definition or use");
+ }
+ if (Flags.has(RegisterOperandFlag::Kill) && !IsUse) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "kill flag requires a register use");
+ }
+ if (Flags.has(RegisterOperandFlag::Dead) && !IsDef) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "dead flag requires a register definition");
+ }
+ if (Flags.has(RegisterOperandFlag::Undef) && !IsUse) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "undef flag requires a register use");
+ }
+ if (Flags.has(RegisterOperandFlag::EarlyClobber) && !IsDef) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "early-clobber flag requires a register definition");
+ }
+ if (Flags.has(RegisterOperandFlag::InternalRead) && (!IsDef || !IsUse)) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "internal-read flag requires a register def-use operand");
+ }
+ if (IsDef && IsUse && !Flags.has(RegisterOperandFlag::InternalRead)) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "register def-use operand requires internal-read");
+ }
+ if (Flags.has(RegisterOperandFlag::Debug) && (!IsUse || IsDef)) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "debug register operand must be a use");
+ }
+ return {};
+}
+
+Expected<MachineOperand> MachineOperand::registerOperand(Register Reg, RegisterOperandFlags Flags,
+ SubRegIndex SubReg,
+ std::uint32_t TargetFlags) {
+ const auto Validation = verifyRegisterFlags(Flags);
+ if (!Validation)
+ return std::unexpected(Validation.error());
+
+ MachineOperand Operand(Kind::Register, Reg, TargetFlags);
+ Operand.RegFlags = Flags;
+ Operand.RegSubReg = SubReg;
+ return Operand;
+}
+
+MachineOperand MachineOperand::immediate(std::int64_t Value, std::uint32_t TargetFlags) {
+ return MachineOperand(Kind::Immediate, Value, TargetFlags);
+}
+
+MachineOperand MachineOperand::floatingImmediate(FloatingPointBits Bits,
+ std::uint32_t TargetFlags) {
+ return MachineOperand(Kind::FloatingImmediate, FloatingImmediateOperand{Bits}, TargetFlags);
+}
+
+MachineOperand MachineOperand::basicBlock(MachineBasicBlock &Block, std::uint32_t TargetFlags) {
+ return MachineOperand(Kind::BasicBlock, BasicBlockOperand{&Block}, TargetFlags);
+}
+
+MachineOperand MachineOperand::frameIndex(FrameIndex Index, std::int64_t Offset,
+ std::uint32_t TargetFlags) {
+ return MachineOperand(Kind::FrameIndex, FrameIndexOperand{Index, Offset}, TargetFlags);
+}
+
+MachineOperand MachineOperand::constantPool(ConstantPoolIndex Index, std::int64_t Offset,
+ std::uint32_t TargetFlags) {
+ return MachineOperand(Kind::ConstantPoolIndex, ConstantPoolOperand{Index, Offset}, TargetFlags);
+}
+
+MachineOperand MachineOperand::jumpTable(JumpTableIndex Index, std::uint32_t TargetFlags) {
+ return MachineOperand(Kind::JumpTableIndex, JumpTableOperand{Index}, TargetFlags);
+}
+
+Expected<MachineOperand> MachineOperand::globalSymbol(std::string Name, std::int64_t Offset,
+ std::uint32_t TargetFlags) {
+ if (Name.empty()) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "global symbol operand name cannot be empty");
+ }
+ return MachineOperand(Kind::GlobalSymbol, GlobalSymbolOperand{std::move(Name), Offset},
+ TargetFlags);
+}
+
+Expected<MachineOperand> MachineOperand::externalSymbol(std::string Name, std::int64_t Offset,
+ std::uint32_t TargetFlags) {
+ if (Name.empty()) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "external symbol operand name cannot be empty");
+ }
+ return MachineOperand(Kind::ExternalSymbol, ExternalSymbolOperand{std::move(Name), Offset},
+ TargetFlags);
+}
+
+Expected<MachineOperand> MachineOperand::blockAddress(std::string FunctionName,
+ std::string BlockName, std::int64_t Offset,
+ std::uint32_t TargetFlags) {
+ if (FunctionName.empty() || BlockName.empty()) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "block address operand requires function and block names");
+ }
+ return MachineOperand(Kind::BlockAddress,
+ BlockAddressOperand{std::move(FunctionName), std::move(BlockName), Offset},
+ TargetFlags);
+}
+
+Expected<MachineOperand> MachineOperand::registerMask(std::shared_ptr<const RegisterMask> Mask,
+ std::uint32_t TargetFlags) {
+ if (!Mask) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "register mask operand cannot be null");
+ }
+ return MachineOperand(Kind::RegisterMask, RegisterMaskOperand{std::move(Mask)}, TargetFlags);
+}
+
+Expected<MachineOperand> MachineOperand::metadata(std::string Marker, std::uint32_t TargetFlags) {
+ if (Marker.empty()) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "metadata operand marker cannot be empty");
+ }
+ return MachineOperand(Kind::Metadata, MetadataOperand{std::move(Marker)}, TargetFlags);
+}
+
+MachineOperand MachineOperand::targetIndex(TargetIndex Index, std::int64_t Offset,
+ std::uint32_t TargetFlags) {
+ return MachineOperand(Kind::TargetIndex, TargetIndexOperand{Index, Offset}, TargetFlags);
+}
+
+Expected<MachineOperand> MachineOperand::mcSymbol(std::string Name, std::int64_t Offset,
+ std::uint32_t TargetFlags) {
+ if (Name.empty()) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "MC symbol operand name cannot be empty");
+ }
+ return MachineOperand(Kind::MCSymbol, MCSymbolOperand{std::move(Name), Offset}, TargetFlags);
+}
+
+MachineOperand::MachineOperand(MachineOperand &&Other) noexcept
+ : OperandKind(Other.OperandKind), Storage(std::move(Other.Storage)), RegFlags(Other.RegFlags),
+ RegSubReg(Other.RegSubReg), TiedOperandIndex(Other.TiedOperandIndex),
+ TargetFlags(Other.TargetFlags), Parent(Other.Parent) {
+ takeRegLinkFrom(Other);
+ Other.Parent = nullptr;
+ Other.TiedOperandIndex.reset();
+}
+
+MachineOperand &MachineOperand::operator=(MachineOperand &&Other) noexcept {
+ if (this == &Other)
+ return *this;
+
+ unlinkFromRegInfo();
+ OperandKind = Other.OperandKind;
+ Storage = std::move(Other.Storage);
+ RegFlags = Other.RegFlags;
+ RegSubReg = Other.RegSubReg;
+ TiedOperandIndex = Other.TiedOperandIndex;
+ TargetFlags = Other.TargetFlags;
+ Parent = Other.Parent;
+ takeRegLinkFrom(Other);
+ Other.Parent = nullptr;
+ Other.TiedOperandIndex.reset();
+ return *this;
+}
+
+MachineOperand::~MachineOperand() {
+ unlinkFromRegInfo();
+}
+
+std::optional<Register> MachineOperand::registerValue() const noexcept {
+ if (!isRegister())
+ return std::nullopt;
+ return std::get<Register>(Storage);
+}
+
+bool MachineOperand::isDef() const noexcept {
+ return isRegister() && RegFlags.has(RegisterOperandFlag::Define);
+}
+
+bool MachineOperand::isUse() const noexcept {
+ return isRegister() && RegFlags.has(RegisterOperandFlag::Use);
+}
+
+bool MachineOperand::isDebugUse() const noexcept {
+ return isUse() && RegFlags.has(RegisterOperandFlag::Debug);
+}
+
+bool MachineOperand::isImplicit() const noexcept {
+ return isRegister() && RegFlags.has(RegisterOperandFlag::Implicit);
+}
+
+Expected<void> MachineOperand::setRegister(Register Reg) {
+ if (!isRegister()) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "setRegister requires a register operand");
+ }
+
+ MachineRegisterInfo *RegInfo = LinkedRegInfo;
+ if (RegInfo == nullptr && Parent != nullptr)
+ RegInfo = &Parent->function().registerInfo();
+ if (RegInfo != nullptr && Reg.isVirtual() && !RegInfo->isKnownVirtualRegister(Reg)) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "register operand references an unknown virtual register");
+ }
+
+ const bool WasLinked = LinkedRegInfo != nullptr;
+ unlinkFromRegInfo();
+ Storage = Reg;
+ if (WasLinked && !Reg.isNoRegister())
+ linkToRegInfo(*RegInfo);
+ return {};
+}
+
+Expected<void> MachineOperand::setRegisterFlags(RegisterOperandFlags Flags) {
+ if (!isRegister()) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "register flags require a register operand");
+ }
+ const auto Validation = verifyRegisterFlags(Flags);
+ if (!Validation)
+ return std::unexpected(Validation.error());
+ RegFlags = Flags;
+ return {};
+}
+
+Expected<void> MachineOperand::setSubReg(SubRegIndex SubReg) {
+ if (!isRegister()) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "subregister index requires a register operand");
+ }
+ RegSubReg = SubReg;
+ return {};
+}
+
+MachineOperand MachineOperand::cloneDetached() const {
+ MachineOperand Result(OperandKind, Storage, TargetFlags);
+ Result.RegFlags = RegFlags;
+ Result.RegSubReg = RegSubReg;
+ return Result;
+}
+
+void MachineOperand::attachTo(MachineInstr &Instruction, MachineRegisterInfo *RegInfo) {
+ Parent = &Instruction;
+ if (RegInfo != nullptr && isRegister() && !std::get<Register>(Storage).isNoRegister()) {
+ linkToRegInfo(*RegInfo);
+ }
+}
+
+void MachineOperand::detachFromInstruction() noexcept {
+ unlinkFromRegInfo();
+ Parent = nullptr;
+}
+
+void MachineOperand::linkToRegInfo(MachineRegisterInfo &RegInfo) {
+ RegInfo.linkOperand(*this);
+}
+
+void MachineOperand::unlinkFromRegInfo() noexcept {
+ if (PreviousRegLink == nullptr)
+ return;
+
+ *PreviousRegLink = NextRegOperand;
+ if (NextRegOperand != nullptr)
+ NextRegOperand->PreviousRegLink = PreviousRegLink;
+
+ PreviousRegLink = nullptr;
+ NextRegOperand = nullptr;
+ LinkedRegInfo = nullptr;
+}
+
+void MachineOperand::takeRegLinkFrom(MachineOperand &Other) noexcept {
+ LinkedRegInfo = Other.LinkedRegInfo;
+ PreviousRegLink = Other.PreviousRegLink;
+ NextRegOperand = Other.NextRegOperand;
+
+ if (PreviousRegLink != nullptr)
+ *PreviousRegLink = this;
+ if (NextRegOperand != nullptr)
+ NextRegOperand->PreviousRegLink = &NextRegOperand;
+
+ Other.LinkedRegInfo = nullptr;
+ Other.PreviousRegLink = nullptr;
+ Other.NextRegOperand = nullptr;
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/MachineRegisterInfo.cpp b/backend/lib/CodeGen/MachineRegisterInfo.cpp
new file mode 100644
index 0000000..cc0955e
--- /dev/null
+++ b/backend/lib/CodeGen/MachineRegisterInfo.cpp
@@ -0,0 +1,362 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+
+#include "rcc/CodeGen/MachineOperand.h"
+
+#include <algorithm>
+#include <functional>
+#include <memory>
+#include <optional>
+#include <unordered_set>
+
+namespace rcc {
+
+RegOperandIterator::RegOperandIterator(MachineOperand *Current, bool RequireUse, bool RequireDef,
+ bool SkipDebug) noexcept
+ : Current(Current), RequireUse(RequireUse), RequireDef(RequireDef), SkipDebug(SkipDebug) {
+ skipFiltered();
+}
+
+RegOperandIterator::reference RegOperandIterator::operator*() const noexcept {
+ return *Current;
+}
+
+RegOperandIterator::pointer RegOperandIterator::operator->() const noexcept {
+ return Current;
+}
+
+RegOperandIterator &RegOperandIterator::operator++() noexcept {
+ Current = Current->NextRegOperand;
+ skipFiltered();
+ return *this;
+}
+
+RegOperandIterator RegOperandIterator::operator++(int) noexcept {
+ RegOperandIterator Previous = *this;
+ ++*this;
+ return Previous;
+}
+
+void RegOperandIterator::skipFiltered() noexcept {
+ while (Current != nullptr) {
+ if (RequireUse && !Current->isUse()) {
+ Current = Current->NextRegOperand;
+ continue;
+ }
+ if (RequireDef && !Current->isDef()) {
+ Current = Current->NextRegOperand;
+ continue;
+ }
+ if (SkipDebug && Current->isDebugUse()) {
+ Current = Current->NextRegOperand;
+ continue;
+ }
+ break;
+ }
+}
+
+MachineRegisterInfo::~MachineRegisterInfo() = default;
+
+Expected<Register> MachineRegisterInfo::createVirtualRegister() {
+ auto Reg = Register::makeVirtual(VirtualRegisters.size());
+ if (!Reg)
+ return std::unexpected(Reg.error());
+ VirtualRegisters.emplace_back();
+ return *Reg;
+}
+
+Expected<Register> MachineRegisterInfo::createVirtualRegister(LLT Type) {
+ if (!Type.isValid()) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "virtual register type must be a valid LLT");
+ }
+
+ auto Reg = createVirtualRegister();
+ if (!Reg)
+ return std::unexpected(Reg.error());
+ VirtualRegisters.back().Type = Type;
+ return *Reg;
+}
+
+Expected<void> MachineRegisterInfo::eraseVirtualRegister(Register Reg) {
+ auto Info = virtualRegisterInfo(Reg);
+ if (!Info)
+ return std::unexpected(Info.error());
+ if (headFor(Reg) != nullptr) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "cannot erase a virtual register with operands");
+ }
+
+ Info->get().IsTombstone = true;
+ Info->get().Type.reset();
+ Info->get().Bank.reset();
+ Info->get().RegClass.reset();
+ Info->get().AllocationHints.clear();
+ return {};
+}
+
+bool MachineRegisterInfo::isKnownVirtualRegister(Register Reg) const noexcept {
+ const auto Index = Reg.virtualIndex();
+ if (!Index || *Index >= VirtualRegisters.size())
+ return false;
+ return !VirtualRegisters[*Index].IsTombstone;
+}
+
+Expected<std::reference_wrapper<VirtualRegisterInfo>>
+MachineRegisterInfo::virtualRegisterInfo(Register Reg) {
+ const auto Index = Reg.virtualIndex();
+ if (!Index || *Index >= VirtualRegisters.size() || VirtualRegisters[*Index].IsTombstone) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "register is not a live virtual register");
+ }
+ return std::ref(VirtualRegisters[*Index]);
+}
+
+Expected<std::reference_wrapper<const VirtualRegisterInfo>>
+MachineRegisterInfo::virtualRegisterInfo(Register Reg) const {
+ const auto Index = Reg.virtualIndex();
+ if (!Index || *Index >= VirtualRegisters.size() || VirtualRegisters[*Index].IsTombstone) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "register is not a live virtual register");
+ }
+ return std::cref(VirtualRegisters[*Index]);
+}
+
+Expected<void> MachineRegisterInfo::setType(Register Reg, LLT Type) {
+ if (!Type.isValid()) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "virtual register type must be a valid LLT");
+ }
+ auto Info = virtualRegisterInfo(Reg);
+ if (!Info)
+ return std::unexpected(Info.error());
+ Info->get().Type = Type;
+ return {};
+}
+
+Expected<void> MachineRegisterInfo::clearType(Register Reg) {
+ auto Info = virtualRegisterInfo(Reg);
+ if (!Info)
+ return std::unexpected(Info.error());
+ Info->get().Type.reset();
+ return {};
+}
+
+Expected<void> MachineRegisterInfo::setRegisterBank(Register Reg, RegisterBankID Bank) {
+ auto Info = virtualRegisterInfo(Reg);
+ if (!Info)
+ return std::unexpected(Info.error());
+ Info->get().Bank = Bank;
+ return {};
+}
+
+Expected<void> MachineRegisterInfo::clearRegisterBank(Register Reg) {
+ auto Info = virtualRegisterInfo(Reg);
+ if (!Info)
+ return std::unexpected(Info.error());
+ Info->get().Bank.reset();
+ return {};
+}
+
+Expected<void> MachineRegisterInfo::setRegisterClass(Register Reg, RegisterClassID RegClass) {
+ auto Info = virtualRegisterInfo(Reg);
+ if (!Info)
+ return std::unexpected(Info.error());
+ Info->get().RegClass = RegClass;
+ return {};
+}
+
+Expected<void> MachineRegisterInfo::clearRegisterClass(Register Reg) {
+ auto Info = virtualRegisterInfo(Reg);
+ if (!Info)
+ return std::unexpected(Info.error());
+ Info->get().RegClass.reset();
+ return {};
+}
+
+Expected<void> MachineRegisterInfo::addAllocationHint(Register Reg, PhysicalRegister Hint) {
+ if (!Hint.isValid()) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "allocation hint must name a physical register");
+ }
+ auto Info = virtualRegisterInfo(Reg);
+ if (!Info)
+ return std::unexpected(Info.error());
+
+ auto &Hints = Info->get().AllocationHints;
+ if (std::ranges::find(Hints, Hint) == Hints.end())
+ Hints.push_back(Hint);
+ return {};
+}
+
+void MachineRegisterInfo::clearAllVirtualRegisterTypes() noexcept {
+ for (VirtualRegisterInfo &Info : VirtualRegisters) {
+ if (!Info.IsTombstone)
+ Info.Type.reset();
+ }
+}
+
+Expected<void> MachineRegisterInfo::addLiveIn(PhysicalRegister PhysReg,
+ std::optional<Register> InitialVirtualRegister) {
+ if (!PhysReg.isValid()) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "function live-in must name a physical register");
+ }
+ if (InitialVirtualRegister && !isKnownVirtualRegister(*InitialVirtualRegister)) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "function live-in initial value must be a live virtual register");
+ }
+ if (std::ranges::any_of(LiveIns, [PhysReg](const PhysicalRegisterLiveIn &LiveIn) {
+ return LiveIn.PhysReg == PhysReg;
+ })) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "function physical live-in is already present");
+ }
+
+ LiveIns.push_back(PhysicalRegisterLiveIn{PhysReg, InitialVirtualRegister});
+ return {};
+}
+
+Expected<void> MachineRegisterInfo::reservePhysicalRegister(PhysicalRegister PhysReg) {
+ if (!PhysReg.isValid()) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "reserved register must name a physical register");
+ }
+ if (isReserved(PhysReg)) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "physical register is already reserved");
+ }
+ ReservedRegisters.push_back(PhysReg);
+ return {};
+}
+
+bool MachineRegisterInfo::isReserved(PhysicalRegister PhysReg) const noexcept {
+ return std::ranges::find(ReservedRegisters, PhysReg) != ReservedRegisters.end();
+}
+
+RegOperandRange MachineRegisterInfo::regOperands(Register Reg) noexcept {
+ return RegOperandRange(headFor(Reg), false, false, false);
+}
+
+RegOperandRange MachineRegisterInfo::regNoDebugOperands(Register Reg) noexcept {
+ return RegOperandRange(headFor(Reg), false, false, true);
+}
+
+RegOperandRange MachineRegisterInfo::useOperands(Register Reg, bool IncludeDebug) noexcept {
+ return RegOperandRange(headFor(Reg), true, false, !IncludeDebug);
+}
+
+RegOperandRange MachineRegisterInfo::defOperands(Register Reg) noexcept {
+ return RegOperandRange(headFor(Reg), false, true, false);
+}
+
+bool MachineRegisterInfo::useEmpty(Register Reg, bool IncludeDebug) const noexcept {
+ for (MachineOperand *Operand = headFor(Reg); Operand != nullptr;
+ Operand = Operand->NextRegOperand) {
+ if (Operand->isUse() && (IncludeDebug || !Operand->isDebugUse()))
+ return false;
+ }
+ return true;
+}
+
+bool MachineRegisterInfo::hasOneUse(Register Reg, bool IncludeDebug) const noexcept {
+ bool FoundUse = false;
+ for (MachineOperand *Operand = headFor(Reg); Operand != nullptr;
+ Operand = Operand->NextRegOperand) {
+ if (!Operand->isUse() || (!IncludeDebug && Operand->isDebugUse()))
+ continue;
+ if (FoundUse)
+ return false;
+ FoundUse = true;
+ }
+ return FoundUse;
+}
+
+const MachineOperand *MachineRegisterInfo::getUniqueVRegDef(Register Reg) const noexcept {
+ if (!isKnownVirtualRegister(Reg))
+ return nullptr;
+
+ const MachineOperand *UniqueDef = nullptr;
+ for (MachineOperand *Operand = headFor(Reg); Operand != nullptr;
+ Operand = Operand->NextRegOperand) {
+ if (!Operand->isDef())
+ continue;
+ if (UniqueDef != nullptr)
+ return nullptr;
+ UniqueDef = Operand;
+ }
+ return UniqueDef;
+}
+
+Expected<std::size_t> MachineRegisterInfo::replaceRegWith(Register OldReg, Register NewReg) {
+ if (OldReg.isNoRegister() || NewReg.isNoRegister()) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "register replacement requires two nonzero registers");
+ }
+ if ((OldReg.isVirtual() && !isKnownVirtualRegister(OldReg)) ||
+ (NewReg.isVirtual() && !isKnownVirtualRegister(NewReg))) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "register replacement references an unknown virtual register");
+ }
+
+ std::size_t ReplacementCount = 0;
+ MachineOperand *Operand = headFor(OldReg);
+ while (Operand != nullptr) {
+ MachineOperand *Next = Operand->NextRegOperand;
+ const auto Result = Operand->setRegister(NewReg);
+ if (!Result)
+ return std::unexpected(Result.error());
+ ++ReplacementCount;
+ Operand = Next;
+ }
+ return ReplacementCount;
+}
+
+Expected<void> MachineRegisterInfo::verifyDefUseChains() const {
+ std::unordered_set<const MachineOperand *> SeenOperands;
+
+ for (const auto &[Reg, HeadStorage] : DefUseHeads) {
+ MachineOperand *const *ExpectedPreviousLink = &HeadStorage->Head;
+ for (MachineOperand *Operand = HeadStorage->Head; Operand != nullptr;
+ Operand = Operand->NextRegOperand) {
+ if (!SeenOperands.insert(Operand).second) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "register def-use chains contain a cycle or duplicate operand");
+ }
+ if (!Operand->isRegister() || Operand->registerValue() != Reg) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "register def-use chain contains an operand for another register");
+ }
+ if (Operand->LinkedRegInfo != this || Operand->PreviousRegLink != ExpectedPreviousLink) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "register def-use chain back-link is corrupt");
+ }
+ ExpectedPreviousLink = &Operand->NextRegOperand;
+ }
+ }
+
+ return {};
+}
+
+MachineOperand *MachineRegisterInfo::headFor(Register Reg) const noexcept {
+ const auto Position = DefUseHeads.find(Reg);
+ if (Position == DefUseHeads.end())
+ return nullptr;
+ return Position->second->Head;
+}
+
+void MachineRegisterInfo::linkOperand(MachineOperand &Operand) {
+ const auto Reg = Operand.registerValue();
+ if (!Reg || Reg->isNoRegister())
+ return;
+
+ auto &HeadStorage = DefUseHeads[*Reg];
+ if (!HeadStorage)
+ HeadStorage = std::make_unique<RegOperandListHead>();
+
+ Operand.unlinkFromRegInfo();
+ Operand.LinkedRegInfo = this;
+ Operand.PreviousRegLink = &HeadStorage->Head;
+ Operand.NextRegOperand = HeadStorage->Head;
+ if (HeadStorage->Head != nullptr)
+ HeadStorage->Head->PreviousRegLink = &Operand.NextRegOperand;
+ HeadStorage->Head = &Operand;
+}
+
+} // namespace rcc
diff --git a/backend/unittests/CodeGen/CMakeLists.txt b/backend/unittests/CodeGen/CMakeLists.txt
index 15b0a44..cad2a44 100644
--- a/backend/unittests/CodeGen/CMakeLists.txt
+++ b/backend/unittests/CodeGen/CMakeLists.txt
@@ -3,6 +3,7 @@
set(
RCCBackendCodeGenTestSources
CoreTypesTest.cpp
+ MachineIRCoreTest.cpp
MachineValueTypesTest.cpp
)
@@ -21,11 +22,22 @@ add_test(
COMMAND RCCBackendCodeGenMachineValueTypesTests
)
+add_executable(RCCBackendCodeGenMachineIRCoreTests MachineIRCoreTest.cpp)
+rcc_backend_configure_target(RCCBackendCodeGenMachineIRCoreTests)
+target_link_libraries(RCCBackendCodeGenMachineIRCoreTests PRIVATE RCCBackend::CodeGen)
+
+add_test(
+ NAME RCCBackend.CodeGen.MachineIRCore
+ COMMAND RCCBackendCodeGenMachineIRCoreTests
+)
+
rcc_backend_register_format_files(
"${CMAKE_CURRENT_SOURCE_DIR}/CoreTypesTest.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRCoreTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineValueTypesTest.cpp"
)
rcc_backend_register_tidy_files(
"${CMAKE_CURRENT_SOURCE_DIR}/CoreTypesTest.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRCoreTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineValueTypesTest.cpp"
)
diff --git a/backend/unittests/CodeGen/MachineIRCoreTest.cpp b/backend/unittests/CodeGen/MachineIRCoreTest.cpp
new file mode 100644
index 0000000..1083422
--- /dev/null
+++ b/backend/unittests/CodeGen/MachineIRCoreTest.cpp
@@ -0,0 +1,467 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/LowLevelType.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineCFGUpdater.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineMemOperand.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/RegisterMask.h"
+
+#include <array>
+#include <cstddef>
+#include <cstdint>
+#include <iostream>
+#include <memory>
+#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;
+};
+
+[[nodiscard]] std::unique_ptr<rcc::MachineFunction>
+createFunction(TestContext &Context, std::string Name, std::uint64_t ID) {
+ auto Function =
+ rcc::MachineFunction::create(std::move(Name), rcc::MachineFunctionStableID::fromValue(ID));
+ Context.expect(Function.has_value(), "valid machine function construction must succeed");
+ if (!Function)
+ return nullptr;
+ return std::move(*Function);
+}
+
+[[nodiscard]] rcc::MachineBasicBlock *createLinkedBlock(TestContext &Context,
+ rcc::MachineFunction &Function) {
+ auto Block = Function.createBasicBlock();
+ Context.expect(Block.has_value(), "basic block allocation must succeed");
+ if (!Block)
+ return nullptr;
+ auto LinkResult = Function.appendBlock(**Block);
+ Context.expect(LinkResult.has_value(), "basic block insertion must succeed");
+ if (!LinkResult)
+ return nullptr;
+ return *Block;
+}
+
+[[nodiscard]] bool addRegisterOperand(TestContext &Context, rcc::MachineInstr &Instruction,
+ rcc::Register Reg, rcc::RegisterOperandFlags Flags) {
+ auto Operand = rcc::MachineOperand::registerOperand(Reg, Flags);
+ Context.expect(Operand.has_value(), "valid register operand construction must succeed");
+ if (!Operand)
+ return false;
+ auto AddResult = Instruction.addOperand(std::move(*Operand));
+ Context.expect(AddResult.has_value(), "register operand insertion must succeed");
+ return AddResult.has_value();
+}
+
+[[nodiscard]] std::size_t countOperands(rcc::RegOperandRange Range) {
+ std::size_t Count = 0;
+ for ([[maybe_unused]] const rcc::MachineOperand &Operand : Range)
+ ++Count;
+ return Count;
+}
+
+rcc::MachineMemOperandDesc makeLoadDescription() {
+ rcc::MachineMemOperandDesc Description;
+ Description.Accesses = rcc::MemoryAccessFlags{
+ rcc::MemoryAccessFlag::Load,
+ rcc::MemoryAccessFlag::Dereferenceable,
+ };
+ Description.Size = *rcc::MemorySize::fixed(8);
+ Description.Align = *rcc::Alignment::create(8);
+ Description.Base = rcc::MemoryBase::frameIndex(rcc::FrameIndex::fromValue(0));
+ return Description;
+}
+
+void testOperandKinds(TestContext &Context) {
+ auto Function = createFunction(Context, "operands", 1);
+ if (!Function)
+ return;
+ auto Block = Function->createBasicBlock();
+ Context.expect(Block.has_value(), "operand test block allocation must succeed");
+ if (!Block)
+ return;
+
+ const std::array<std::uint64_t, 1> HalfWords{0x3c00};
+ auto HalfBits = rcc::FloatingPointBits::create(rcc::FloatSemantics::IEEEHalf, HalfWords);
+ Context.expect(HalfBits.has_value(), "well-sized floating immediate must be accepted");
+ if (!HalfBits)
+ return;
+ Context.expect(HalfBits->bitWidth() == 16 && HalfBits->words()[0] == 0x3c00,
+ "floating immediate must preserve semantics and raw bits");
+
+ const std::array<std::uint64_t, 1> OverflowHalfWords{0x10000};
+ Context.expect(!rcc::FloatingPointBits::create(rcc::FloatSemantics::IEEEHalf, OverflowHalfWords),
+ "floating immediate bits above semantics width must be rejected");
+ const std::array<std::uint64_t, 2> TooManyHalfWords{0, 0};
+ Context.expect(!rcc::FloatingPointBits::create(rcc::FloatSemantics::IEEEHalf, TooManyHalfWords),
+ "floating immediate word-count mismatch must be rejected");
+
+ auto Virtual = Function->registerInfo().createVirtualRegister(*rcc::LLT::makeInteger(32));
+ Context.expect(Virtual.has_value(), "operand test virtual register must be created");
+ if (!Virtual)
+ return;
+
+ auto RegOperand = rcc::MachineOperand::registerOperand(
+ *Virtual, rcc::RegisterOperandFlags{rcc::RegisterOperandFlag::Use});
+ Context.expect(RegOperand && RegOperand->kind() == rcc::MachineOperand::Kind::Register,
+ "register operand must preserve its kind");
+ Context.expect(!rcc::MachineOperand::registerOperand(*Virtual, {}),
+ "register operand without def/use role must be rejected");
+ Context.expect(!rcc::MachineOperand::registerOperand(
+ *Virtual, rcc::RegisterOperandFlags{rcc::RegisterOperandFlag::Define,
+ rcc::RegisterOperandFlag::Kill}),
+ "kill flag on register definition must be rejected");
+
+ auto Immediate = rcc::MachineOperand::immediate(-9, 17);
+ Context.expect(Immediate.kind() == rcc::MachineOperand::Kind::Immediate &&
+ *Immediate.getIf<std::int64_t>() == -9 && Immediate.targetFlags() == 17,
+ "immediate operand must preserve value and target flags");
+
+ auto Floating = rcc::MachineOperand::floatingImmediate(*HalfBits);
+ Context.expect(Floating.kind() == rcc::MachineOperand::Kind::FloatingImmediate,
+ "floating operand must preserve its kind");
+ auto BlockRef = rcc::MachineOperand::basicBlock(**Block);
+ Context.expect(BlockRef.getIf<rcc::BasicBlockOperand>()->Block == *Block,
+ "basic block operand must preserve its target");
+ auto Frame = rcc::MachineOperand::frameIndex(rcc::FrameIndex::fromValue(4), -8);
+ Context.expect(Frame.getIf<rcc::FrameIndexOperand>()->Offset == -8,
+ "frame index operand must preserve its offset");
+ auto Constant = rcc::MachineOperand::constantPool(rcc::ConstantPoolIndex::fromValue(2), 3);
+ Context.expect(Constant.kind() == rcc::MachineOperand::Kind::ConstantPoolIndex,
+ "constant pool operand must preserve its kind");
+ auto Jump = rcc::MachineOperand::jumpTable(rcc::JumpTableIndex::fromValue(5));
+ Context.expect(Jump.kind() == rcc::MachineOperand::Kind::JumpTableIndex,
+ "jump table operand must preserve its kind");
+
+ auto Global = rcc::MachineOperand::globalSymbol("global", 12);
+ auto External = rcc::MachineOperand::externalSymbol("external", -4);
+ auto BlockAddress = rcc::MachineOperand::blockAddress("function", "block", 2);
+ Context.expect(Global && External && BlockAddress, "valid symbol operands must be accepted");
+ Context.expect(!rcc::MachineOperand::globalSymbol(""),
+ "empty global symbol operand must be rejected");
+ Context.expect(!rcc::MachineOperand::blockAddress("", "block"),
+ "incomplete block address operand must be rejected");
+
+ auto Mask = std::make_shared<const rcc::RegisterMask>(std::vector<std::uint64_t>{0xffff});
+ auto MaskOperand = rcc::MachineOperand::registerMask(Mask);
+ Context.expect(MaskOperand && MaskOperand->kind() == rcc::MachineOperand::Kind::RegisterMask,
+ "register mask operand must preserve shared immutable mask");
+ Context.expect(!rcc::MachineOperand::registerMask(nullptr),
+ "null register mask operand must be rejected");
+
+ auto Metadata = rcc::MachineOperand::metadata("source-marker");
+ Context.expect(Metadata && Metadata->kind() == rcc::MachineOperand::Kind::Metadata,
+ "metadata operand must preserve its kind");
+ Context.expect(!rcc::MachineOperand::metadata(""), "empty metadata marker must be rejected");
+
+ auto Target = rcc::MachineOperand::targetIndex(rcc::TargetIndex::fromValue(8), 9);
+ Context.expect(Target.getIf<rcc::TargetIndexOperand>()->Offset == 9,
+ "target index operand must preserve its offset");
+ auto MCSymbol = rcc::MachineOperand::mcSymbol(".Ltmp0", 1);
+ Context.expect(MCSymbol && MCSymbol->kind() == rcc::MachineOperand::Kind::MCSymbol,
+ "MC symbol precursor must preserve its kind");
+
+ const auto Clone = Immediate.cloneDetached();
+ Context.expect(Clone.parent() == nullptr &&
+ *Clone.getIf<std::int64_t>() == *Immediate.getIf<std::int64_t>(),
+ "detached operand clone must preserve payload without ownership");
+ Context.expect(!Immediate.setRegister(*Virtual),
+ "register mutation on non-register operand must be rejected");
+}
+
+void testRegisterInfoAndOperandMovement(TestContext &Context) {
+ auto Function = createFunction(Context, "def_use", 2);
+ if (!Function)
+ return;
+ rcc::MachineBasicBlock *Block = createLinkedBlock(Context, *Function);
+ if (Block == nullptr)
+ return;
+
+ auto I32 = rcc::LLT::makeInteger(32);
+ Context.expect(I32.has_value(), "i32 construction for MRI test must succeed");
+ if (!I32)
+ return;
+ auto V0 = Function->registerInfo().createVirtualRegister(*I32);
+ auto V1 = Function->registerInfo().createVirtualRegister(*I32);
+ Context.expect(V0 && V1, "MRI must allocate monotonic virtual registers");
+ if (!V0 || !V1)
+ return;
+ Context.expect(V0->virtualIndex() == 0 && V1->virtualIndex() == 1,
+ "MRI virtual register indices must start at zero and increase");
+
+ auto PhysReg = rcc::PhysicalRegister::create(7);
+ Context.expect(PhysReg.has_value(), "MRI test physical register must be valid");
+ if (!PhysReg)
+ return;
+ const rcc::Register Physical = rcc::Register::fromPhysical(*PhysReg);
+
+ auto Instruction = Function->createInstruction(rcc::Opcode::fromValue(1));
+ Context.expect(Instruction.has_value(), "machine instruction allocation must succeed");
+ if (!Instruction)
+ return;
+ rcc::MachineInstr *Instr = *Instruction;
+
+ if (!addRegisterOperand(Context, *Instr, *V0,
+ rcc::RegisterOperandFlags{rcc::RegisterOperandFlag::Define}) ||
+ !addRegisterOperand(Context, *Instr, *V0,
+ rcc::RegisterOperandFlags{rcc::RegisterOperandFlag::Use}) ||
+ !addRegisterOperand(Context, *Instr, *V0,
+ rcc::RegisterOperandFlags{rcc::RegisterOperandFlag::Use,
+ rcc::RegisterOperandFlag::Debug}) ||
+ !addRegisterOperand(Context, *Instr, Physical,
+ rcc::RegisterOperandFlags{rcc::RegisterOperandFlag::Use})) {
+ return;
+ }
+
+ Context.expect(Function->registerInfo().useEmpty(*V0),
+ "detached instruction operands must not enter def-use chains");
+ auto LinkInstruction = Block->appendInstruction(*Instr);
+ Context.expect(LinkInstruction.has_value(), "instruction insertion must succeed");
+ if (!LinkInstruction)
+ return;
+
+ Context.expect(countOperands(Function->registerInfo().regOperands(*V0)) == 3,
+ "def-use chain must include definition, use, and debug use");
+ Context.expect(countOperands(Function->registerInfo().useOperands(*V0)) == 2,
+ "use iterator must include ordinary and debug uses");
+ Context.expect(countOperands(Function->registerInfo().useOperands(*V0, false)) == 1,
+ "nodbg use iterator must filter debug operands");
+ Context.expect(Function->registerInfo().getUniqueVRegDef(*V0) == Instr->operandAt(0),
+ "unique virtual register definition must be discoverable");
+ Context.expect(countOperands(Function->registerInfo().regOperands(Physical)) == 1,
+ "physical registers must participate in exact def-use chains");
+
+ rcc::MachineOperand *const OldOperandAddress = Instr->operandAt(0);
+ Instr->reserveOperands(128);
+ Context.expect(Instr->operandAt(0) != nullptr && Instr->operandAt(0)->parent() == Instr,
+ "operand relocation must preserve instruction ownership");
+ Context.expect(Function->registerInfo().verifyDefUseChains().has_value(),
+ "operand relocation must repair intrusive def-use links");
+ Context.expect(OldOperandAddress != Instr->operandAt(0) ||
+ Function->registerInfo().getUniqueVRegDef(*V0) == Instr->operandAt(0),
+ "def-use head must follow an operand when its address changes");
+
+ auto TieResult = Instr->tieOperands(0, 1);
+ Context.expect(TieResult.has_value(), "valid def-use operand tie must succeed");
+ const auto DetachedTieClone = Instr->operandAt(0)->cloneDetached();
+ Context.expect(!DetachedTieClone.tiedOperandIndex(),
+ "single detached operand clone must not retain an instruction-local tie");
+ auto InsertResult = Instr->insertOperand(0, rcc::MachineOperand::immediate(5));
+ Context.expect(InsertResult.has_value(), "operand insertion before a tie must succeed");
+ Context.expect(Instr->operandAt(1)->tiedOperandIndex() == 2 &&
+ Instr->operandAt(2)->tiedOperandIndex() == 1,
+ "operand insertion must rewrite both tie indices");
+ auto EraseResult = Instr->eraseOperand(0);
+ Context.expect(EraseResult.has_value(), "temporary operand erasure must succeed");
+ Context.expect(Instr->operandAt(0)->tiedOperandIndex() == 1 &&
+ Instr->operandAt(1)->tiedOperandIndex() == 0,
+ "operand erasure must rewrite both tie indices");
+ Context.expect(Instr->untieOperand(0).has_value(), "reciprocal operand tie must be removable");
+
+ auto SetRegisterResult = Instr->operandAt(1)->setRegister(*V1);
+ Context.expect(SetRegisterResult.has_value(), "register operand rebinding must succeed");
+ Context.expect(Function->registerInfo().useEmpty(*V0, false),
+ "register rebinding must unlink the old ordinary use");
+ Context.expect(Function->registerInfo().hasOneUse(*V1),
+ "register rebinding must link the new use");
+
+ auto ReplaceResult = Function->registerInfo().replaceRegWith(*V1, *V0);
+ Context.expect(ReplaceResult && *ReplaceResult == 1,
+ "replaceRegWith must rewrite every linked operand exactly once");
+ Context.expect(Function->registerInfo().verifyDefUseChains().has_value(),
+ "register replacement must preserve exact def-use chains");
+
+ for (std::int64_t Value = 0; Value < 64; ++Value) {
+ auto Result = Instr->addOperand(rcc::MachineOperand::immediate(Value));
+ Context.expect(Result.has_value(), "variadic immediate operand insertion must succeed");
+ }
+ Context.expect(Function->registerInfo().verifyDefUseChains().has_value(),
+ "repeated operand growth must preserve def-use links");
+
+ auto &MRI = Function->registerInfo();
+ Context.expect(MRI.setRegisterBank(*V0, rcc::RegisterBankID::fromValue(3)).has_value(),
+ "MRI must record a register bank");
+ Context.expect(MRI.setRegisterClass(*V0, rcc::RegisterClassID::fromValue(4)).has_value(),
+ "MRI must record a register class");
+ Context.expect(MRI.addAllocationHint(*V0, *PhysReg).has_value(),
+ "MRI must record a physical allocation hint");
+ auto V0Info = MRI.virtualRegisterInfo(*V0);
+ Context.expect(V0Info && V0Info->get().Type == I32 &&
+ V0Info->get().Bank == rcc::RegisterBankID::fromValue(3) &&
+ V0Info->get().RegClass == rcc::RegisterClassID::fromValue(4),
+ "MRI virtual register properties must evolve without losing LLT");
+
+ Context.expect(MRI.addLiveIn(*PhysReg, *V0).has_value(),
+ "MRI must record function physical live-ins");
+ Context.expect(!MRI.addLiveIn(*PhysReg, *V0),
+ "duplicate function physical live-ins must be rejected");
+ Context.expect(MRI.reservePhysicalRegister(*PhysReg).has_value(),
+ "MRI must record reserved physical registers");
+ Context.expect(MRI.isReserved(*PhysReg),
+ "MRI reserved-register query must find recorded register");
+
+ auto DeadVReg = MRI.createVirtualRegister(*I32);
+ Context.expect(DeadVReg && MRI.eraseVirtualRegister(*DeadVReg).has_value(),
+ "unused virtual register must become a tombstone");
+ auto LaterVReg = MRI.createVirtualRegister(*I32);
+ Context.expect(LaterVReg && LaterVReg->virtualIndex() != DeadVReg->virtualIndex(),
+ "MRI must not reuse tombstoned virtual register indices");
+ Context.expect(!MRI.eraseVirtualRegister(*V0),
+ "virtual register with linked operands must not be erased");
+
+ auto ZombieVReg = MRI.createVirtualRegister(*I32);
+ auto ZombieInstr = Function->createInstruction(rcc::Opcode::fromValue(2));
+ Context.expect(ZombieVReg && ZombieInstr,
+ "detached tombstone validation setup must allocate objects");
+ if (ZombieVReg && ZombieInstr) {
+ Context.expect(addRegisterOperand(Context, **ZombieInstr, *ZombieVReg,
+ rcc::RegisterOperandFlags{rcc::RegisterOperandFlag::Use}),
+ "detached instruction must initially accept its live virtual register");
+ Context.expect(MRI.eraseVirtualRegister(*ZombieVReg).has_value(),
+ "detached operand must not make an unpublished vreg live");
+ const std::size_t OriginalInstructionCount = Block->instructionCount();
+ Context.expect(!Block->appendInstruction(**ZombieInstr),
+ "instruction insertion must reject a tombstoned virtual register");
+ Context.expect((*ZombieInstr)->parent() == nullptr &&
+ Block->instructionCount() == OriginalInstructionCount,
+ "failed instruction insertion must not mutate block layout");
+ Context.expect(!(*ZombieInstr)->operandAt(0)->setRegister(*ZombieVReg),
+ "detached register mutation must reject a tombstoned vreg");
+ }
+
+ auto UnlinkResult = Block->removeInstruction(*Instr);
+ Context.expect(UnlinkResult.has_value(), "instruction removal must succeed");
+ Context.expect(MRI.useEmpty(*V0) && MRI.getUniqueVRegDef(*V0) == nullptr,
+ "instruction removal must unlink every register operand");
+ Context.expect(MRI.verifyDefUseChains().has_value(),
+ "empty def-use lists after removal must remain structurally valid");
+ Context.expect(Block->appendInstruction(*Instr).has_value(),
+ "detached instruction must be reinsertable");
+ Context.expect(MRI.getUniqueVRegDef(*V0) == Instr->operandAt(0),
+ "instruction reinsertion must rebuild register links");
+}
+
+void testOwnershipCFGAndMemory(TestContext &Context) {
+ auto Function = createFunction(Context, "cfg", 3);
+ auto OtherFunction = createFunction(Context, "other", 4);
+ if (!Function || !OtherFunction)
+ return;
+
+ rcc::MachineBasicBlock *Entry = createLinkedBlock(Context, *Function);
+ rcc::MachineBasicBlock *Left = createLinkedBlock(Context, *Function);
+ rcc::MachineBasicBlock *Right = createLinkedBlock(Context, *Function);
+ rcc::MachineBasicBlock *Foreign = createLinkedBlock(Context, *OtherFunction);
+ if (Entry == nullptr || Left == nullptr || Right == nullptr || Foreign == nullptr)
+ return;
+
+ Context.expect(Function->blockCount() == 3,
+ "machine function block list must preserve layout count");
+ Context.expect(Entry->layoutIndex() == 0 && Left->layoutIndex() == 1 && Right->layoutIndex() == 2,
+ "block layout indices must follow intrusive layout order");
+
+ auto Half = rcc::BranchProbability::fromFraction(1, 2);
+ Context.expect(Half.has_value(), "CFG test probability must be valid");
+ if (!Half)
+ return;
+ auto CFG = Function->cfgUpdater();
+ Context.expect(CFG.addSuccessor(*Entry, *Left, *Half).has_value() &&
+ CFG.addSuccessor(*Entry, *Left, *Half).has_value(),
+ "duplicate semantic branches must merge into one CFG successor");
+ Context.expect(Entry->successors().size() == 1 && Left->predecessors().size() == 1,
+ "CFG must not contain duplicate successor or predecessor entries");
+ Context.expect(CFG.addSuccessor(*Entry, *Right, *Half).has_value(),
+ "second CFG successor must be insertable");
+ Context.expect(!CFG.addSuccessor(*Entry, *Foreign, *Half),
+ "cross-function CFG edge must be rejected");
+ Context.expect(!CFG.replaceSuccessor(*Entry, *Left, *Foreign) &&
+ Entry->successors().size() == 2 && Left->predecessors().size() == 1,
+ "cross-function CFG replacement must fail without mutating existing edges");
+
+ Context.expect(CFG.replaceSuccessor(*Entry, *Left, *Right).has_value(),
+ "CFG successor replacement must succeed");
+ Context.expect(Entry->successors().size() == 1 && Left->predecessors().empty() &&
+ Right->predecessors().size() == 1,
+ "CFG replacement must merge duplicate target and repair predecessors");
+ Context.expect(CFG.transferSuccessors(*Entry, *Left).has_value(),
+ "CFG successor transfer must succeed");
+ Context.expect(Entry->successors().empty() && Left->successors().size() == 1 &&
+ Right->predecessors()[0] == Left,
+ "CFG successor transfer must update both directions");
+ Context.expect(CFG.disconnectBlock(*Left).has_value(),
+ "CFG block disconnection must remove incoming and outgoing edges");
+ Context.expect(Left->successors().empty() && Right->predecessors().empty(),
+ "CFG disconnection must leave no stale reciprocal edges");
+
+ auto Instr = Function->createInstruction(rcc::Opcode::fromValue(9));
+ auto NextInstr = Function->createInstruction(rcc::Opcode::fromValue(10));
+ Context.expect(Instr && NextInstr, "instruction arena allocation must succeed");
+ if (!Instr || !NextInstr)
+ return;
+ Context.expect(Entry->appendInstruction(**Instr).has_value(),
+ "first block instruction must be inserted");
+ Context.expect(Entry->insertInstructionBefore(**Instr, **NextInstr).has_value(),
+ "instruction insertion before a stable node must succeed");
+ Context.expect(Entry->firstInstruction() == *NextInstr && Entry->lastInstruction() == *Instr &&
+ Entry->instructionCount() == 2,
+ "intrusive instruction list must preserve order and endpoints");
+
+ auto CrossBlockOperand = rcc::MachineOperand::basicBlock(*Foreign);
+ Context.expect(!(*Instr)->addOperand(std::move(CrossBlockOperand)),
+ "instruction must reject a block operand from another function");
+
+ auto MemOperand = Function->createMemOperand(makeLoadDescription());
+ auto ForeignMemOperand = OtherFunction->createMemOperand(makeLoadDescription());
+ Context.expect(MemOperand && ForeignMemOperand,
+ "function arena must allocate immutable memory operands");
+ if (MemOperand && ForeignMemOperand) {
+ Context.expect((*Instr)->addMemOperand(**MemOperand).has_value(),
+ "instruction must accept a memory operand owned by its function");
+ Context.expect(!(*Instr)->addMemOperand(**ForeignMemOperand),
+ "instruction must reject a memory operand from another function");
+ }
+
+ const rcc::MachineBasicBlock *StableEntryAddress = Entry;
+ const rcc::MachineInstr *StableInstrAddress = *Instr;
+ for (std::uint32_t Index = 0; Index < 128; ++Index) {
+ auto NewBlock = Function->createBasicBlock();
+ auto NewInstr = Function->createInstruction(rcc::Opcode::fromValue(Index + 100));
+ Context.expect(NewBlock && NewInstr, "arena growth must continue to allocate objects");
+ }
+ Context.expect(StableEntryAddress == Entry && StableInstrAddress == *Instr,
+ "arena growth must preserve block and instruction addresses");
+
+ Context.expect(Function->removeBlock(*Right).has_value(),
+ "disconnected empty block must be removable from layout");
+ Context.expect(!Right->isLinked() && Function->blockCount() == 2,
+ "removed block must leave layout while retaining stable storage");
+}
+
+} // namespace
+
+int main() {
+ TestContext Context;
+ testOperandKinds(Context);
+ testRegisterInfoAndOperandMovement(Context);
+ testOwnershipCFGAndMemory(Context);
+ return Context.result();
+}
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-29 03:05:17 +0000