diff options
Diffstat (limited to 'backend/include/rcc/CodeGen')
| -rw-r--r-- | backend/include/rcc/CodeGen/GenericConstant.h | 7 | ||||
| -rw-r--r-- | backend/include/rcc/CodeGen/LiveRangeEdit.h | 32 | ||||
| -rw-r--r-- | backend/include/rcc/CodeGen/LiveRegMatrix.h | 73 | ||||
| -rw-r--r-- | backend/include/rcc/CodeGen/MachineFrameInfo.h | 3 | ||||
| -rw-r--r-- | backend/include/rcc/CodeGen/MachineRegisterInfo.h | 1 | ||||
| -rw-r--r-- | backend/include/rcc/CodeGen/PBQP/Graph.h | 194 | ||||
| -rw-r--r-- | backend/include/rcc/CodeGen/PBQP/Math.h | 114 | ||||
| -rw-r--r-- | backend/include/rcc/CodeGen/PBQP/ReductionRules.h | 32 | ||||
| -rw-r--r-- | backend/include/rcc/CodeGen/PBQP/Solution.h | 85 | ||||
| -rw-r--r-- | backend/include/rcc/CodeGen/PBQP/Solver.h | 342 | ||||
| -rw-r--r-- | backend/include/rcc/CodeGen/RegAllocCommon.h | 25 | ||||
| -rw-r--r-- | backend/include/rcc/CodeGen/RegAllocFast.h | 26 | ||||
| -rw-r--r-- | backend/include/rcc/CodeGen/RegAllocPBQP.h | 29 | ||||
| -rw-r--r-- | backend/include/rcc/CodeGen/Spiller.h | 41 | ||||
| -rw-r--r-- | backend/include/rcc/CodeGen/TargetMIRTextInfo.h | 15 | ||||
| -rw-r--r-- | backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h | 58 | ||||
| -rw-r--r-- | backend/include/rcc/CodeGen/VirtRegMap.h | 93 |
17 files changed, 1154 insertions, 16 deletions
diff --git a/backend/include/rcc/CodeGen/GenericConstant.h b/backend/include/rcc/CodeGen/GenericConstant.h index 11c5068..92a8f13 100644 --- a/backend/include/rcc/CodeGen/GenericConstant.h +++ b/backend/include/rcc/CodeGen/GenericConstant.h @@ -50,8 +50,8 @@ struct GenericConstantType final { [[nodiscard]] static GenericConstantType byte() noexcept; [[nodiscard]] static Expected<GenericConstantType> floating(FloatSemantics Semantics); [[nodiscard]] static GenericConstantType pointer(std::uint32_t AddressSpace = 0) noexcept; - [[nodiscard]] static Expected<GenericConstantType> - array(std::uint64_t ElementCount, GenericConstantType Element); + [[nodiscard]] static Expected<GenericConstantType> array(std::uint64_t ElementCount, + GenericConstantType Element); [[nodiscard]] static Expected<GenericConstantType> vector(std::uint64_t ElementCount, GenericConstantType Element, bool Scalable = false); [[nodiscard]] static Expected<GenericConstantType> @@ -152,8 +152,7 @@ struct GenericConstantData final { std::string Block; bool NumericSymbol = false; bool NumericBlock = false; - GenericConstantExpressionOpcode ExpressionOpcode = - GenericConstantExpressionOpcode::Invalid; + GenericConstantExpressionOpcode ExpressionOpcode = GenericConstantExpressionOpcode::Invalid; GenericConstantExpressionFlags ExpressionFlags; std::optional<GenericConstantType> SourceElementType; std::optional<IntegerImmediate> InRangeStart; diff --git a/backend/include/rcc/CodeGen/LiveRangeEdit.h b/backend/include/rcc/CodeGen/LiveRangeEdit.h new file mode 100644 index 0000000..66696df --- /dev/null +++ b/backend/include/rcc/CodeGen/LiveRangeEdit.h @@ -0,0 +1,32 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_LIVERANGEEDIT_H +#define RCC_CODEGEN_LIVERANGEEDIT_H + +#include "rcc/CodeGen/VirtRegMap.h" + +#include <optional> + +namespace rcc { + +class TargetDescription; + +class LiveRangeEdit final { +public: + LiveRangeEdit(MachineFunction &Function, const TargetDescription &Target, VirtRegMap &Mapping) + : Function(&Function), Target(&Target), Mapping(&Mapping) {} + + [[nodiscard]] Expected<Register> createFrom(Register Parent, bool Spillable, + std::optional<Register> Origin = std::nullopt); + [[nodiscard]] Expected<FrameIndex> getOrCreateSpillSlot(Register VirtualReg); + [[nodiscard]] Expected<void> eraseVirtualRegister(Register VirtualReg); + +private: + MachineFunction *Function; + const TargetDescription *Target; + VirtRegMap *Mapping; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_LIVERANGEEDIT_H diff --git a/backend/include/rcc/CodeGen/LiveRegMatrix.h b/backend/include/rcc/CodeGen/LiveRegMatrix.h new file mode 100644 index 0000000..953828c --- /dev/null +++ b/backend/include/rcc/CodeGen/LiveRegMatrix.h @@ -0,0 +1,73 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_LIVEREGMATRIX_H +#define RCC_CODEGEN_LIVEREGMATRIX_H + +#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/CodeGen/TargetRegisterInfo.h" + +#include <cstdint> +#include <optional> +#include <span> +#include <unordered_map> +#include <utility> +#include <vector> + +namespace rcc { + +class MachineFunction; +class TargetDescription; + +enum class RegisterInterferenceKind : std::uint8_t { + Free, + VirtualRegister, + FixedRegister, + RegisterMask, + RegisterUnit, +}; + +struct RegisterInterference final { + RegisterInterferenceKind Kind = RegisterInterferenceKind::Free; + std::optional<Register> VirtualReg; + std::optional<PhysicalRegister> FixedReg; + std::optional<RegisterUnitID> Unit; + std::optional<MachineInstrStableID> Instruction; +}; + +class LiveRegMatrix final { +public: + LiveRegMatrix(const MachineFunction &Function, const TargetDescription &Target, + const LiveIntervalsAnalysis::Result &Intervals) noexcept + : Function(&Function), Target(&Target), Intervals(&Intervals) {} + + [[nodiscard]] Expected<void> assign(Register VirtualReg, PhysicalRegister PhysicalReg); + [[nodiscard]] Expected<void> unassign(Register VirtualReg); + [[nodiscard]] std::optional<PhysicalRegister> assignment(Register VirtualReg) const noexcept; + [[nodiscard]] RegisterInterference checkInterference(Register VirtualReg, + PhysicalRegister PhysicalReg) const noexcept; + [[nodiscard]] std::vector<RegisterInterference> + collectInterferences(Register VirtualReg, PhysicalRegister PhysicalReg) const; + + [[nodiscard]] std::span<const std::pair<Register, PhysicalRegister>> + assignments() const noexcept { + return OrderedAssignments; + } + +private: + [[nodiscard]] bool intervalsOverlapOnCandidates(const LiveInterval &Left, + PhysicalRegister LeftReg, + const LiveInterval &Right, + PhysicalRegister RightReg) const noexcept; + [[nodiscard]] bool intervalOverlapsUnit(const LiveInterval &Interval, RegisterUnitLane Unit, + const LiveRange &UnitRange) const noexcept; + + const MachineFunction *Function; + const TargetDescription *Target; + const LiveIntervalsAnalysis::Result *Intervals; + std::unordered_map<Register, PhysicalRegister> Assignments; + std::vector<std::pair<Register, PhysicalRegister>> OrderedAssignments; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_LIVEREGMATRIX_H diff --git a/backend/include/rcc/CodeGen/MachineFrameInfo.h b/backend/include/rcc/CodeGen/MachineFrameInfo.h index 48e3d7a..c884afb 100644 --- a/backend/include/rcc/CodeGen/MachineFrameInfo.h +++ b/backend/include/rcc/CodeGen/MachineFrameInfo.h @@ -197,8 +197,7 @@ struct MachineFrameState final { std::vector<MachineFrameSaveRestorePoint> SavePoints; std::vector<MachineFrameSaveRestorePoint> RestorePoints; - friend bool operator==(const MachineFrameState &Left, - const MachineFrameState &Right) = default; + friend bool operator==(const MachineFrameState &Left, const MachineFrameState &Right) = default; }; class MachineFrameInfo final { diff --git a/backend/include/rcc/CodeGen/MachineRegisterInfo.h b/backend/include/rcc/CodeGen/MachineRegisterInfo.h index b6485e3..14e50a3 100644 --- a/backend/include/rcc/CodeGen/MachineRegisterInfo.h +++ b/backend/include/rcc/CodeGen/MachineRegisterInfo.h @@ -134,6 +134,7 @@ public: [[nodiscard]] std::span<const PhysicalRegisterLiveIn> liveIns() const noexcept { return LiveIns; } + void clearLiveInVirtualRegisters() noexcept; [[nodiscard]] Expected<void> reservePhysicalRegister(PhysicalRegister PhysReg); [[nodiscard]] bool isReserved(PhysicalRegister PhysReg) const noexcept; diff --git a/backend/include/rcc/CodeGen/PBQP/Graph.h b/backend/include/rcc/CodeGen/PBQP/Graph.h new file mode 100644 index 0000000..9173bfd --- /dev/null +++ b/backend/include/rcc/CodeGen/PBQP/Graph.h @@ -0,0 +1,194 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_PBQP_GRAPH_H +#define RCC_CODEGEN_PBQP_GRAPH_H + +#include "rcc/CodeGen/PBQP/Math.h" +#include "rcc/Support/Error.h" + +#include <compare> +#include <cstddef> +#include <cstdint> +#include <functional> +#include <limits> +#include <optional> +#include <span> +#include <utility> +#include <vector> + +namespace rcc::pbqp { + +class NodeID final { +public: + constexpr NodeID() noexcept = default; + [[nodiscard]] static constexpr NodeID fromValue(std::uint32_t Value) noexcept { + return NodeID(Value); + } + [[nodiscard]] constexpr bool isValid() const noexcept { + return Value != InvalidValue; + } + [[nodiscard]] constexpr std::uint32_t value() const noexcept { + return Value; + } + friend constexpr bool operator==(NodeID, NodeID) noexcept = default; + friend constexpr auto operator<=>(NodeID, NodeID) noexcept = default; + +private: + static constexpr std::uint32_t InvalidValue = std::numeric_limits<std::uint32_t>::max(); + explicit constexpr NodeID(std::uint32_t Value) noexcept : Value(Value) {} + std::uint32_t Value = InvalidValue; +}; + +class EdgeID final { +public: + constexpr EdgeID() noexcept = default; + [[nodiscard]] static constexpr EdgeID fromValue(std::uint32_t Value) noexcept { + return EdgeID(Value); + } + [[nodiscard]] constexpr bool isValid() const noexcept { + return Value != InvalidValue; + } + [[nodiscard]] constexpr std::uint32_t value() const noexcept { + return Value; + } + friend constexpr bool operator==(EdgeID, EdgeID) noexcept = default; + friend constexpr auto operator<=>(EdgeID, EdgeID) noexcept = default; + +private: + static constexpr std::uint32_t InvalidValue = std::numeric_limits<std::uint32_t>::max(); + explicit constexpr EdgeID(std::uint32_t Value) noexcept : Value(Value) {} + std::uint32_t Value = InvalidValue; +}; + +struct Node final { + NodeID ID; + std::uint64_t StableKey = 0; + CostVector Costs; + std::vector<EdgeID> AdjacentEdges; +}; + +struct Edge final { + EdgeID ID; + NodeID First; + NodeID Second; + std::uint64_t StableKey = 0; + CostMatrix Costs; +}; + +class Graph final { +public: + [[nodiscard]] Expected<NodeID> addNode(CostVector Costs, std::uint64_t StableKey = 0) { + if (Costs.empty()) + return makeUnexpected(ErrorCode::InvalidArgument, "PBQP node requires at least one option"); + if (Nodes.size() >= std::numeric_limits<std::uint32_t>::max()) + return makeUnexpected(ErrorCode::Unsupported, "PBQP node ID space is exhausted"); + const NodeID ID = NodeID::fromValue(static_cast<std::uint32_t>(Nodes.size())); + Nodes.push_back(Node{ID, StableKey, std::move(Costs), {}}); + return ID; + } + + [[nodiscard]] Expected<EdgeID> addEdge(NodeID First, NodeID Second, CostMatrix Costs, + std::uint64_t StableKey = 0) { + const Node *FirstNode = node(First); + const Node *SecondNode = node(Second); + if (FirstNode == nullptr || SecondNode == nullptr || First == Second) { + return makeUnexpected(ErrorCode::InvalidArgument, + "PBQP edge requires two distinct known nodes"); + } + if (edgeBetween(First, Second)) + return makeUnexpected(ErrorCode::InvalidArgument, "PBQP graph already contains this edge"); + + if (Second < First) { + std::swap(First, Second); + Costs = Costs.transpose(); + std::swap(FirstNode, SecondNode); + } + if (Costs.rows() != FirstNode->Costs.size() || Costs.columns() != SecondNode->Costs.size()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "PBQP edge matrix dimensions do not match its nodes"); + } + if (Edges.size() >= std::numeric_limits<std::uint32_t>::max()) + return makeUnexpected(ErrorCode::Unsupported, "PBQP edge ID space is exhausted"); + const EdgeID ID = EdgeID::fromValue(static_cast<std::uint32_t>(Edges.size())); + Edges.push_back(Edge{ID, First, Second, StableKey, std::move(Costs)}); + Nodes[First.value()].AdjacentEdges.push_back(ID); + Nodes[Second.value()].AdjacentEdges.push_back(ID); + return ID; + } + + [[nodiscard]] const Node *node(NodeID ID) const noexcept { + return ID.isValid() && ID.value() < Nodes.size() ? &Nodes[ID.value()] : nullptr; + } + [[nodiscard]] const Edge *edge(EdgeID ID) const noexcept { + return ID.isValid() && ID.value() < Edges.size() ? &Edges[ID.value()] : nullptr; + } + + [[nodiscard]] const Edge *edgeBetween(NodeID Left, NodeID Right) const noexcept { + const Node *LeftNode = node(Left); + if (LeftNode == nullptr || node(Right) == nullptr) + return nullptr; + for (const EdgeID ID : LeftNode->AdjacentEdges) { + const Edge &Candidate = Edges[ID.value()]; + if ((Candidate.First == Left && Candidate.Second == Right) || + (Candidate.First == Right && Candidate.Second == Left)) + return &Candidate; + } + return nullptr; + } + + [[nodiscard]] std::span<const Node> nodes() const noexcept { + return Nodes; + } + [[nodiscard]] std::span<const Edge> edges() const noexcept { + return Edges; + } + [[nodiscard]] std::size_t nodeCount() const noexcept { + return Nodes.size(); + } + + [[nodiscard]] Expected<void> verify() const { + for (std::size_t Index = 0; Index < Nodes.size(); ++Index) { + const Node &Value = Nodes[Index]; + if (Value.ID.value() != Index || Value.Costs.empty()) + return makeUnexpected(ErrorCode::VerificationError, "PBQP graph contains an invalid node"); + for (const EdgeID ID : Value.AdjacentEdges) { + const Edge *Adjacent = edge(ID); + if (Adjacent == nullptr || (Adjacent->First != Value.ID && Adjacent->Second != Value.ID)) { + return makeUnexpected(ErrorCode::VerificationError, + "PBQP node has an invalid adjacency entry"); + } + } + } + for (std::size_t Index = 0; Index < Edges.size(); ++Index) { + const Edge &Value = Edges[Index]; + const Node *First = node(Value.First); + const Node *Second = node(Value.Second); + if (Value.ID.value() != Index || First == nullptr || Second == nullptr || + !(Value.First < Value.Second) || Value.Costs.rows() != First->Costs.size() || + Value.Costs.columns() != Second->Costs.size()) { + return makeUnexpected(ErrorCode::VerificationError, "PBQP graph contains an invalid edge"); + } + } + return {}; + } + +private: + std::vector<Node> Nodes; + std::vector<Edge> Edges; +}; + +} // namespace rcc::pbqp + +template <> struct std::hash<rcc::pbqp::NodeID> { + [[nodiscard]] std::size_t operator()(rcc::pbqp::NodeID ID) const noexcept { + return std::hash<std::uint32_t>{}(ID.value()); + } +}; + +template <> struct std::hash<rcc::pbqp::EdgeID> { + [[nodiscard]] std::size_t operator()(rcc::pbqp::EdgeID ID) const noexcept { + return std::hash<std::uint32_t>{}(ID.value()); + } +}; + +#endif // RCC_CODEGEN_PBQP_GRAPH_H diff --git a/backend/include/rcc/CodeGen/PBQP/Math.h b/backend/include/rcc/CodeGen/PBQP/Math.h new file mode 100644 index 0000000..90fc751 --- /dev/null +++ b/backend/include/rcc/CodeGen/PBQP/Math.h @@ -0,0 +1,114 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_PBQP_MATH_H +#define RCC_CODEGEN_PBQP_MATH_H + +#include <algorithm> +#include <cstddef> +#include <cstdint> +#include <limits> +#include <span> +#include <utility> +#include <vector> + +namespace rcc::pbqp { + +using Cost = std::int64_t; + +inline constexpr Cost InfiniteCost = std::numeric_limits<Cost>::max() / 4; +inline constexpr Cost NegativeInfiniteCost = -InfiniteCost; + +[[nodiscard]] constexpr bool isInfinite(Cost Value) noexcept { + return Value >= InfiniteCost; +} + +[[nodiscard]] constexpr Cost addCosts(Cost Left, Cost Right) noexcept { + if (isInfinite(Left) || isInfinite(Right)) + return InfiniteCost; + if (Left <= NegativeInfiniteCost || Right <= NegativeInfiniteCost) + return NegativeInfiniteCost; + if (Right > 0 && Left > InfiniteCost - Right) + return InfiniteCost; + if (Right < 0 && Left < NegativeInfiniteCost - Right) + return NegativeInfiniteCost; + return Left + Right; +} + +class CostVector final { +public: + explicit CostVector(std::size_t Size, Cost Initial = 0) : Values(Size, Initial) {} + explicit CostVector(std::vector<Cost> Values) : Values(std::move(Values)) {} + + [[nodiscard]] std::size_t size() const noexcept { + return Values.size(); + } + [[nodiscard]] bool empty() const noexcept { + return Values.empty(); + } + [[nodiscard]] Cost &operator[](std::size_t Index) noexcept { + return Values[Index]; + } + [[nodiscard]] Cost operator[](std::size_t Index) const noexcept { + return Values[Index]; + } + [[nodiscard]] std::span<const Cost> values() const noexcept { + return Values; + } + + [[nodiscard]] std::size_t minimumIndex() const noexcept { + return static_cast<std::size_t>(std::ranges::min_element(Values) - Values.begin()); + } + + void add(const CostVector &Other) noexcept { + for (std::size_t Index = 0; Index < Values.size(); ++Index) + Values[Index] = addCosts(Values[Index], Other.Values[Index]); + } + +private: + std::vector<Cost> Values; +}; + +class CostMatrix final { +public: + CostMatrix(std::size_t Rows, std::size_t Columns, Cost Initial = 0) + : RowCount(Rows), ColumnCount(Columns), Values(Rows * Columns, Initial) {} + + [[nodiscard]] std::size_t rows() const noexcept { + return RowCount; + } + [[nodiscard]] std::size_t columns() const noexcept { + return ColumnCount; + } + [[nodiscard]] bool empty() const noexcept { + return RowCount == 0 || ColumnCount == 0; + } + + [[nodiscard]] Cost &at(std::size_t Row, std::size_t Column) noexcept { + return Values[Row * ColumnCount + Column]; + } + [[nodiscard]] Cost at(std::size_t Row, std::size_t Column) const noexcept { + return Values[Row * ColumnCount + Column]; + } + + [[nodiscard]] CostMatrix transpose() const { + CostMatrix Result(ColumnCount, RowCount); + for (std::size_t Row = 0; Row < RowCount; ++Row) + for (std::size_t Column = 0; Column < ColumnCount; ++Column) + Result.at(Column, Row) = at(Row, Column); + return Result; + } + + void add(const CostMatrix &Other) noexcept { + for (std::size_t Index = 0; Index < Values.size(); ++Index) + Values[Index] = addCosts(Values[Index], Other.Values[Index]); + } + +private: + std::size_t RowCount; + std::size_t ColumnCount; + std::vector<Cost> Values; +}; + +} // namespace rcc::pbqp + +#endif // RCC_CODEGEN_PBQP_MATH_H diff --git a/backend/include/rcc/CodeGen/PBQP/ReductionRules.h b/backend/include/rcc/CodeGen/PBQP/ReductionRules.h new file mode 100644 index 0000000..1b28e33 --- /dev/null +++ b/backend/include/rcc/CodeGen/PBQP/ReductionRules.h @@ -0,0 +1,32 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_PBQP_REDUCTIONRULES_H +#define RCC_CODEGEN_PBQP_REDUCTIONRULES_H + +#include "rcc/CodeGen/PBQP/Graph.h" + +#include <cstdint> + +namespace rcc::pbqp { + +enum class ReductionKind : std::uint8_t { + DegreeZero, + DegreeOne, + DegreeTwo, + Heuristic, +}; + +struct ReductionRecord final { + ReductionKind Kind = ReductionKind::DegreeZero; + NodeID Node; + NodeID FirstNeighbor; + NodeID SecondNeighbor; + std::size_t FixedSelection = 0; + CostVector NodeCosts{1}; + CostMatrix FirstCosts{1, 1}; + CostMatrix SecondCosts{1, 1}; +}; + +} // namespace rcc::pbqp + +#endif // RCC_CODEGEN_PBQP_REDUCTIONRULES_H diff --git a/backend/include/rcc/CodeGen/PBQP/Solution.h b/backend/include/rcc/CodeGen/PBQP/Solution.h new file mode 100644 index 0000000..512eb57 --- /dev/null +++ b/backend/include/rcc/CodeGen/PBQP/Solution.h @@ -0,0 +1,85 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_PBQP_SOLUTION_H +#define RCC_CODEGEN_PBQP_SOLUTION_H + +#include "rcc/CodeGen/PBQP/Graph.h" +#include "rcc/Support/Error.h" + +#include <cstddef> +#include <limits> +#include <optional> +#include <span> +#include <vector> + +namespace rcc::pbqp { + +class Solution final { +public: + explicit Solution(std::size_t NodeCount) + : Selections(NodeCount, std::numeric_limits<std::size_t>::max()) {} + + [[nodiscard]] Expected<void> setSelection(NodeID ID, std::size_t Selection) { + if (!ID.isValid() || ID.value() >= Selections.size()) + return makeUnexpected(ErrorCode::InvalidArgument, "PBQP solution received an unknown node"); + Selections[ID.value()] = Selection; + return {}; + } + + [[nodiscard]] std::optional<std::size_t> selection(NodeID ID) const noexcept { + if (!ID.isValid() || ID.value() >= Selections.size() || + Selections[ID.value()] == std::numeric_limits<std::size_t>::max()) + return std::nullopt; + return Selections[ID.value()]; + } + + [[nodiscard]] std::span<const std::size_t> selections() const noexcept { + return Selections; + } + [[nodiscard]] Cost totalCost() const noexcept { + return TotalCost; + } + void setTotalCost(Cost Value) noexcept { + TotalCost = Value; + } + + [[nodiscard]] Expected<void> verify(const Graph &Problem) const { + if (Selections.size() != Problem.nodeCount()) + return makeUnexpected(ErrorCode::VerificationError, "PBQP solution has the wrong node count"); + Cost Total = 0; + for (const Node &NodeValue : Problem.nodes()) { + const auto Selection = selection(NodeValue.ID); + if (!Selection) + return makeUnexpected(ErrorCode::VerificationError, + "PBQP solution omits a valid node selection"); + const std::size_t SelectedOption = Selection.value(); + if (SelectedOption >= NodeValue.Costs.size()) + return makeUnexpected(ErrorCode::VerificationError, + "PBQP solution selects an invalid node option"); + Total = addCosts(Total, NodeValue.Costs[SelectedOption]); + } + for (const Edge &EdgeValue : Problem.edges()) { + const auto FirstSelection = selection(EdgeValue.First); + const auto SecondSelection = selection(EdgeValue.Second); + if (!FirstSelection || !SecondSelection) { + return makeUnexpected(ErrorCode::VerificationError, + "PBQP solution omits an edge endpoint selection"); + } + Total = addCosts(Total, EdgeValue.Costs.at(FirstSelection.value(), SecondSelection.value())); + } + if (isInfinite(Total)) + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "PBQP problem has no finite solution"); + if (Total != TotalCost) + return makeUnexpected(ErrorCode::VerificationError, "PBQP solution cost is inconsistent"); + return {}; + } + +private: + std::vector<std::size_t> Selections; + Cost TotalCost = 0; +}; + +} // namespace rcc::pbqp + +#endif // RCC_CODEGEN_PBQP_SOLUTION_H diff --git a/backend/include/rcc/CodeGen/PBQP/Solver.h b/backend/include/rcc/CodeGen/PBQP/Solver.h new file mode 100644 index 0000000..ff14857 --- /dev/null +++ b/backend/include/rcc/CodeGen/PBQP/Solver.h @@ -0,0 +1,342 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_PBQP_SOLVER_H +#define RCC_CODEGEN_PBQP_SOLVER_H + +#include "rcc/CodeGen/PBQP/ReductionRules.h" +#include "rcc/CodeGen/PBQP/Solution.h" + +#include <algorithm> +#include <cstddef> +#include <cstdint> +#include <map> +#include <optional> +#include <set> +#include <tuple> +#include <utility> +#include <vector> + +namespace rcc::pbqp { + +class DeterministicSolver final { +public: + [[nodiscard]] Expected<Solution> solve(const Graph &Problem) const { + auto Verified = Problem.verify(); + if (!Verified) + return std::unexpected(Verified.error()); + + WorkingProblem Work(Problem); + std::vector<ReductionRecord> Reductions; + Reductions.reserve(Problem.nodeCount()); + while (Work.activeNodeCount() != 0) { + const NodeID Selected = Work.selectReductionNode(); + const std::size_t Degree = Work.degree(Selected); + Expected<ReductionRecord> Reduced = Degree == 0 ? Work.reduceDegreeZero(Selected) + : Degree == 1 ? Work.reduceDegreeOne(Selected) + : Degree == 2 ? Work.reduceDegreeTwo(Selected) + : Work.reduceHeuristically(Selected); + if (!Reduced) + return std::unexpected(Reduced.error()); + Reductions.push_back(std::move(*Reduced)); + } + + Solution Result(Problem.nodeCount()); + for (auto Position = Reductions.rbegin(); Position != Reductions.rend(); ++Position) { + const ReductionRecord &Record = *Position; + std::size_t Choice = Record.FixedSelection; + if (Record.Kind != ReductionKind::Heuristic) { + Cost Best = InfiniteCost; + for (std::size_t Option = 0; Option < Record.NodeCosts.size(); ++Option) { + Cost Candidate = Record.NodeCosts[Option]; + if (Record.Kind == ReductionKind::DegreeOne || Record.Kind == ReductionKind::DegreeTwo) { + const auto Neighbor = Result.selection(Record.FirstNeighbor); + if (!Neighbor) + return makeUnexpected(ErrorCode::InternalError, + "PBQP back-propagation encountered an unsolved neighbor"); + Candidate = addCosts(Candidate, Record.FirstCosts.at(Option, *Neighbor)); + } + if (Record.Kind == ReductionKind::DegreeTwo) { + const auto Neighbor = Result.selection(Record.SecondNeighbor); + if (!Neighbor) + return makeUnexpected(ErrorCode::InternalError, + "PBQP back-propagation encountered an unsolved neighbor"); + Candidate = addCosts(Candidate, Record.SecondCosts.at(Option, *Neighbor)); + } + if (Candidate < Best) { + Best = Candidate; + Choice = Option; + } + } + if (isInfinite(Best)) + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "PBQP reductions produced no finite option"); + } + auto Set = Result.setSelection(Record.Node, Choice); + if (!Set) + return std::unexpected(Set.error()); + } + + Cost Total = 0; + for (const Node &NodeValue : Problem.nodes()) { + const auto Selection = Result.selection(NodeValue.ID); + if (!Selection) { + return makeUnexpected(ErrorCode::InternalError, + "PBQP solver did not select a reduced node option"); + } + Total = addCosts(Total, NodeValue.Costs[Selection.value()]); + } + for (const Edge &EdgeValue : Problem.edges()) { + const auto FirstSelection = Result.selection(EdgeValue.First); + const auto SecondSelection = Result.selection(EdgeValue.Second); + if (!FirstSelection || !SecondSelection) { + return makeUnexpected(ErrorCode::InternalError, + "PBQP solver did not select an edge endpoint option"); + } + Total = addCosts(Total, EdgeValue.Costs.at(FirstSelection.value(), SecondSelection.value())); + } + if (isInfinite(Total)) + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "PBQP problem has no finite solution"); + Result.setTotalCost(Total); + auto ResultVerification = Result.verify(Problem); + if (!ResultVerification) + return std::unexpected(ResultVerification.error()); + return Result; + } + +private: + struct WorkingEdge final { + NodeID First; + NodeID Second; + CostMatrix Costs; + }; + + class WorkingProblem final { + public: + explicit WorkingProblem(const Graph &Problem) { + Costs.reserve(Problem.nodeCount()); + StableKeys.reserve(Problem.nodeCount()); + Active.assign(Problem.nodeCount(), true); + for (const Node &NodeValue : Problem.nodes()) { + Costs.push_back(NodeValue.Costs); + StableKeys.push_back(NodeValue.StableKey); + } + for (const Edge &EdgeValue : Problem.edges()) + Edges.emplace(key(EdgeValue.First, EdgeValue.Second), + WorkingEdge{EdgeValue.First, EdgeValue.Second, EdgeValue.Costs}); + ActiveCount = Problem.nodeCount(); + } + + [[nodiscard]] std::size_t activeNodeCount() const noexcept { + return ActiveCount; + } + + [[nodiscard]] std::size_t degree(NodeID ID) const noexcept { + std::size_t Result = 0; + for (const auto &[EdgeKey, EdgeValue] : Edges) { + (void)EdgeKey; + if (Active[EdgeValue.First.value()] && Active[EdgeValue.Second.value()] && + (EdgeValue.First == ID || EdgeValue.Second == ID)) + ++Result; + } + return Result; + } + + [[nodiscard]] NodeID selectReductionNode() const noexcept { + std::optional<std::tuple<bool, std::size_t, std::uint64_t, std::uint32_t>> Best; + NodeID Result; + for (std::size_t Index = 0; Index < Active.size(); ++Index) { + if (!Active[Index]) + continue; + const NodeID ID = NodeID::fromValue(static_cast<std::uint32_t>(Index)); + const std::size_t Degree = degree(ID); + const auto Rank = std::tuple{Degree > 2, Degree, StableKeys[Index], ID.value()}; + if (!Best || Rank < *Best) { + Best = Rank; + Result = ID; + } + } + return Result; + } + + [[nodiscard]] Expected<ReductionRecord> reduceDegreeZero(NodeID ID) { + ReductionRecord Record; + Record.Kind = ReductionKind::DegreeZero; + Record.Node = ID; + Record.NodeCosts = Costs[ID.value()]; + deactivate(ID); + return Record; + } + + [[nodiscard]] Expected<ReductionRecord> reduceDegreeOne(NodeID ID) { + const std::vector<WorkingEdge> Incident = incidentEdges(ID); + if (Incident.size() != 1) + return makeUnexpected(ErrorCode::InternalError, + "PBQP degree-one reduction is inconsistent"); + const WorkingEdge &EdgeValue = Incident.front(); + const NodeID Neighbor = other(EdgeValue, ID); + const CostMatrix Oriented = orientFrom(EdgeValue, ID); + + ReductionRecord Record; + Record.Kind = ReductionKind::DegreeOne; + Record.Node = ID; + Record.FirstNeighbor = Neighbor; + Record.NodeCosts = Costs[ID.value()]; + Record.FirstCosts = Oriented; + + for (std::size_t NeighborOption = 0; NeighborOption < Costs[Neighbor.value()].size(); + ++NeighborOption) { + Cost Minimum = InfiniteCost; + for (std::size_t Option = 0; Option < Costs[ID.value()].size(); ++Option) { + Minimum = std::min( + Minimum, addCosts(Costs[ID.value()][Option], Oriented.at(Option, NeighborOption))); + } + Costs[Neighbor.value()][NeighborOption] = + addCosts(Costs[Neighbor.value()][NeighborOption], Minimum); + } + removeIncidentEdges(ID); + deactivate(ID); + return Record; + } + + [[nodiscard]] Expected<ReductionRecord> reduceDegreeTwo(NodeID ID) { + const std::vector<WorkingEdge> Incident = incidentEdges(ID); + if (Incident.size() != 2) + return makeUnexpected(ErrorCode::InternalError, + "PBQP degree-two reduction is inconsistent"); + NodeID First = other(Incident[0], ID); + NodeID Second = other(Incident[1], ID); + CostMatrix FirstCosts = orientFrom(Incident[0], ID); + CostMatrix SecondCosts = orientFrom(Incident[1], ID); + if (Second < First) { + std::swap(First, Second); + std::swap(FirstCosts, SecondCosts); + } + + ReductionRecord Record; + Record.Kind = ReductionKind::DegreeTwo; + Record.Node = ID; + Record.FirstNeighbor = First; + Record.SecondNeighbor = Second; + Record.NodeCosts = Costs[ID.value()]; + Record.FirstCosts = FirstCosts; + Record.SecondCosts = SecondCosts; + + CostMatrix Delta(Costs[First.value()].size(), Costs[Second.value()].size(), InfiniteCost); + for (std::size_t FirstOption = 0; FirstOption < Delta.rows(); ++FirstOption) { + for (std::size_t SecondOption = 0; SecondOption < Delta.columns(); ++SecondOption) { + for (std::size_t Option = 0; Option < Costs[ID.value()].size(); ++Option) { + const Cost Candidate = + addCosts(Costs[ID.value()][Option], addCosts(FirstCosts.at(Option, FirstOption), + SecondCosts.at(Option, SecondOption))); + Delta.at(FirstOption, SecondOption) = + std::min(Delta.at(FirstOption, SecondOption), Candidate); + } + } + } + removeIncidentEdges(ID); + const auto Position = Edges.find(key(First, Second)); + if (Position == Edges.end()) + Edges.emplace(key(First, Second), WorkingEdge{First, Second, std::move(Delta)}); + else + Position->second.Costs.add(Delta); + deactivate(ID); + return Record; + } + + [[nodiscard]] Expected<ReductionRecord> reduceHeuristically(NodeID ID) { + const std::vector<WorkingEdge> Incident = incidentEdges(ID); + Cost Best = InfiniteCost; + std::size_t Choice = 0; + for (std::size_t Option = 0; Option < Costs[ID.value()].size(); ++Option) { + Cost Candidate = Costs[ID.value()][Option]; + for (const WorkingEdge &EdgeValue : Incident) { + const NodeID Neighbor = other(EdgeValue, ID); + const CostMatrix Oriented = orientFrom(EdgeValue, ID); + Cost NeighborMinimum = InfiniteCost; + for (std::size_t NeighborOption = 0; NeighborOption < Costs[Neighbor.value()].size(); + ++NeighborOption) { + NeighborMinimum = std::min(NeighborMinimum, Oriented.at(Option, NeighborOption)); + } + Candidate = addCosts(Candidate, NeighborMinimum); + } + if (Candidate < Best) { + Best = Candidate; + Choice = Option; + } + } + if (isInfinite(Best)) + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "PBQP heuristic reduction has no finite option"); + + ReductionRecord Record; + Record.Kind = ReductionKind::Heuristic; + Record.Node = ID; + Record.FixedSelection = Choice; + Record.NodeCosts = Costs[ID.value()]; + for (const WorkingEdge &EdgeValue : Incident) { + const NodeID Neighbor = other(EdgeValue, ID); + const CostMatrix Oriented = orientFrom(EdgeValue, ID); + for (std::size_t Option = 0; Option < Costs[Neighbor.value()].size(); ++Option) { + Costs[Neighbor.value()][Option] = + addCosts(Costs[Neighbor.value()][Option], Oriented.at(Choice, Option)); + } + } + removeIncidentEdges(ID); + deactivate(ID); + return Record; + } + + private: + using EdgeKey = std::pair<std::uint32_t, std::uint32_t>; + + [[nodiscard]] static EdgeKey key(NodeID First, NodeID Second) noexcept { + if (Second < First) + std::swap(First, Second); + return {First.value(), Second.value()}; + } + + [[nodiscard]] static NodeID other(const WorkingEdge &EdgeValue, NodeID ID) noexcept { + return EdgeValue.First == ID ? EdgeValue.Second : EdgeValue.First; + } + + [[nodiscard]] static CostMatrix orientFrom(const WorkingEdge &EdgeValue, NodeID ID) { + return EdgeValue.First == ID ? EdgeValue.Costs : EdgeValue.Costs.transpose(); + } + + [[nodiscard]] std::vector<WorkingEdge> incidentEdges(NodeID ID) const { + std::vector<WorkingEdge> Result; + for (const auto &[EdgeKeyValue, EdgeValue] : Edges) { + (void)EdgeKeyValue; + if (Active[EdgeValue.First.value()] && Active[EdgeValue.Second.value()] && + (EdgeValue.First == ID || EdgeValue.Second == ID)) + Result.push_back(EdgeValue); + } + return Result; + } + + void removeIncidentEdges(NodeID ID) { + for (auto Position = Edges.begin(); Position != Edges.end();) { + if (Position->second.First == ID || Position->second.Second == ID) + Position = Edges.erase(Position); + else + ++Position; + } + } + + void deactivate(NodeID ID) noexcept { + Active[ID.value()] = false; + --ActiveCount; + } + + std::vector<CostVector> Costs; + std::vector<std::uint64_t> StableKeys; + std::vector<bool> Active; + std::size_t ActiveCount = 0; + std::map<EdgeKey, WorkingEdge> Edges; + }; +}; + +} // namespace rcc::pbqp + +#endif // RCC_CODEGEN_PBQP_SOLVER_H diff --git a/backend/include/rcc/CodeGen/RegAllocCommon.h b/backend/include/rcc/CodeGen/RegAllocCommon.h new file mode 100644 index 0000000..0df9799 --- /dev/null +++ b/backend/include/rcc/CodeGen/RegAllocCommon.h @@ -0,0 +1,25 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_REGALLOCCOMMON_H +#define RCC_CODEGEN_REGALLOCCOMMON_H + +#include "rcc/CodeGen/MachinePass.h" + +#include <memory> + +namespace rcc { + +class TargetRegisterAllocationInfo; + +struct RegisterAllocationOptions final { + bool EnableRematerialization = true; + bool EnableCopyCoalescing = true; +}; + +[[nodiscard]] std::unique_ptr<MachineFunctionPass> +createBasicAllocatorPass(const TargetRegisterAllocationInfo &Info, + RegisterAllocationOptions Options = {}); + +} // namespace rcc + +#endif // RCC_CODEGEN_REGALLOCCOMMON_H diff --git a/backend/include/rcc/CodeGen/RegAllocFast.h b/backend/include/rcc/CodeGen/RegAllocFast.h new file mode 100644 index 0000000..84cf30c --- /dev/null +++ b/backend/include/rcc/CodeGen/RegAllocFast.h @@ -0,0 +1,26 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_REGALLOCFAST_H +#define RCC_CODEGEN_REGALLOCFAST_H + +#include "rcc/CodeGen/MachinePass.h" +#include "rcc/CodeGen/TargetRegisterAllocationInfo.h" + +namespace rcc { + +class FastAllocatorPass final : public MachineFunctionPass { +public: + explicit FastAllocatorPass(const TargetRegisterAllocationInfo &Info) noexcept : Info(&Info) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + const TargetRegisterAllocationInfo *Info; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_REGALLOCFAST_H diff --git a/backend/include/rcc/CodeGen/RegAllocPBQP.h b/backend/include/rcc/CodeGen/RegAllocPBQP.h new file mode 100644 index 0000000..368cbee --- /dev/null +++ b/backend/include/rcc/CodeGen/RegAllocPBQP.h @@ -0,0 +1,29 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_REGALLOCPBQP_H +#define RCC_CODEGEN_REGALLOCPBQP_H + +#include "rcc/CodeGen/RegAllocCommon.h" +#include "rcc/CodeGen/TargetRegisterAllocationInfo.h" + +namespace rcc { + +class PBQPAllocatorPass final : public MachineFunctionPass { +public: + explicit PBQPAllocatorPass(const TargetRegisterAllocationInfo &Info, + RegisterAllocationOptions Options = {}) noexcept + : Info(&Info), Options(Options) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + const TargetRegisterAllocationInfo *Info; + RegisterAllocationOptions Options; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_REGALLOCPBQP_H diff --git a/backend/include/rcc/CodeGen/Spiller.h b/backend/include/rcc/CodeGen/Spiller.h new file mode 100644 index 0000000..3d1fc66 --- /dev/null +++ b/backend/include/rcc/CodeGen/Spiller.h @@ -0,0 +1,41 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_SPILLER_H +#define RCC_CODEGEN_SPILLER_H + +#include "rcc/CodeGen/LiveRangeEdit.h" +#include "rcc/CodeGen/TargetRegisterAllocationInfo.h" + +#include <optional> +#include <vector> + +namespace rcc { + +class Spiller final { +public: + Spiller(MachineFunction &Function, const TargetDescription &Target, + const TargetRegisterAllocationInfo &TargetInfo, VirtRegMap &Mapping, + bool EnableRematerialization = true) + : Function(&Function), Target(&Target), TargetInfo(&TargetInfo), Mapping(&Mapping), + Edit(Function, Target, Mapping), EnableRematerialization(EnableRematerialization) {} + + [[nodiscard]] Expected<std::vector<Register>> spill(Register VirtualReg); + +private: + [[nodiscard]] Expected<std::vector<Register>> spillAtInstructions(Register VirtualReg); + [[nodiscard]] Expected<void> spillLiveIn(Register VirtualReg, RegisterClassID Class, + FrameIndex StackSlot); + [[nodiscard]] Expected<std::optional<std::vector<Register>>> + tryRematerialize(Register VirtualReg); + + MachineFunction *Function; + const TargetDescription *Target; + const TargetRegisterAllocationInfo *TargetInfo; + VirtRegMap *Mapping; + LiveRangeEdit Edit; + bool EnableRematerialization; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_SPILLER_H diff --git a/backend/include/rcc/CodeGen/TargetMIRTextInfo.h b/backend/include/rcc/CodeGen/TargetMIRTextInfo.h index b8eb4ee..3ed6022 100644 --- a/backend/include/rcc/CodeGen/TargetMIRTextInfo.h +++ b/backend/include/rcc/CodeGen/TargetMIRTextInfo.h @@ -68,10 +68,8 @@ struct MIRTargetMappingEntry final { const MIRTargetMappingEntry &Right) = default; }; -using MIRTargetFunctionStateParser = - Expected<TargetFunctionState> (*)(const MIRTargetNode &Node); -using MIRTargetFunctionStatePrinter = - Expected<MIRTargetNode> (*)(const TargetFunctionState &State); +using MIRTargetFunctionStateParser = Expected<TargetFunctionState> (*)(const MIRTargetNode &Node); +using MIRTargetFunctionStatePrinter = Expected<MIRTargetNode> (*)(const TargetFunctionState &State); using MIRTargetConstantParser = Expected<TargetConstant> (*)(std::string_view Text); using MIRTargetConstantPrinter = Expected<std::string> (*)(const TargetConstant &Constant); @@ -235,13 +233,10 @@ public: return Description.FunctionStateType; } - [[nodiscard]] Expected<TargetFunctionState> - parseFunctionState(const MIRTargetNode &Node) const; - [[nodiscard]] Expected<MIRTargetNode> - printFunctionState(const TargetFunctionState &State) const; + [[nodiscard]] Expected<TargetFunctionState> parseFunctionState(const MIRTargetNode &Node) const; + [[nodiscard]] Expected<MIRTargetNode> printFunctionState(const TargetFunctionState &State) const; [[nodiscard]] Expected<TargetConstant> parseTargetConstant(std::string_view Text) const; - [[nodiscard]] Expected<std::string> - printTargetConstant(const TargetConstant &Constant) const; + [[nodiscard]] Expected<std::string> printTargetConstant(const TargetConstant &Constant) const; private: explicit TargetMIRTextInfo(TargetMIRTextInfoDesc Description) diff --git a/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h b/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h new file mode 100644 index 0000000..6e25465 --- /dev/null +++ b/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h @@ -0,0 +1,58 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_TARGETREGISTERALLOCATIONINFO_H +#define RCC_CODEGEN_TARGETREGISTERALLOCATIONINFO_H + +#include "rcc/CodeGen/MachineFrameInfo.h" +#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/CodeGen/TargetRegisterInfo.h" + +#include <cstdint> + +namespace rcc { + +class MachineIRBuilder; +class MachineInstr; +class TargetDescription; + +class TargetRegisterAllocationInfo { +public: + virtual ~TargetRegisterAllocationInfo() = default; + + [[nodiscard]] virtual Expected<void> + validateSpillReload(RegisterClassID Class, const TargetDescription &Target) const = 0; + [[nodiscard]] virtual Expected<MachineInstr *> + emitReload(MachineIRBuilder &Builder, Register Destination, RegisterClassID Class, + FrameIndex StackSlot, LaneMask Lanes) const = 0; + [[nodiscard]] virtual Expected<MachineInstr *> emitSpill(MachineIRBuilder &Builder, + Register Source, RegisterClassID Class, + FrameIndex StackSlot, + LaneMask Lanes) const = 0; + + [[nodiscard]] virtual Expected<bool> isRematerializable(const MachineInstr &, Register, + const MachineFunction &, + const TargetDescription &) const { + return false; + } + [[nodiscard]] virtual Expected<MachineInstr *> rematerialize(MachineIRBuilder &, + const MachineInstr &, Register, + Register, + const TargetDescription &) const { + return makeUnexpected(ErrorCode::InternalError, + "target accepted rematerialization without implementing it"); + } + + [[nodiscard]] virtual std::uint64_t physicalRegisterCost(const MachineFunction &, Register, + PhysicalRegister, RegisterClassID, + bool) const noexcept { + return 0; + } + [[nodiscard]] virtual std::uint64_t spillCost(const MachineFunction &, const LiveInterval &, + RegisterClassID) const noexcept { + return 1; + } +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_TARGETREGISTERALLOCATIONINFO_H diff --git a/backend/include/rcc/CodeGen/VirtRegMap.h b/backend/include/rcc/CodeGen/VirtRegMap.h new file mode 100644 index 0000000..f37af84 --- /dev/null +++ b/backend/include/rcc/CodeGen/VirtRegMap.h @@ -0,0 +1,93 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_VIRTREGMAP_H +#define RCC_CODEGEN_VIRTREGMAP_H + +#include "rcc/CodeGen/MachineFrameInfo.h" +#include "rcc/CodeGen/MachinePass.h" +#include "rcc/CodeGen/TargetRegisterInfo.h" + +#include <cstdint> +#include <optional> +#include <unordered_map> +#include <vector> + +namespace rcc { + +class MachineFunction; +class TargetDescription; + +enum class VirtRegAllocationState : std::uint8_t { + Unassigned, + Assigned, + Spilled, + Split, +}; + +struct VirtRegSpillMetadata final { + std::optional<FrameIndex> StackSlot; + LaneMask Lanes = LaneMask::all(); + std::uint64_t SpillCount = 0; + std::uint64_t ReloadCount = 0; + std::uint64_t RematerializationCount = 0; +}; + +struct VirtRegMapEntry final { + Register VirtualReg; + VirtRegAllocationState State = VirtRegAllocationState::Unassigned; + std::optional<PhysicalRegister> PhysicalReg; + std::optional<Register> SplitParent; + std::optional<Register> Origin; + bool Spillable = true; + VirtRegSpillMetadata Spill; +}; + +class VirtRegMap final { +public: + explicit VirtRegMap(MachineFunction &Function) noexcept : Function(&Function) {} + + [[nodiscard]] MachineFunction &function() const noexcept { + return *Function; + } + [[nodiscard]] Expected<void> add(Register VirtualReg, bool Spillable = true, + std::optional<Register> SplitParent = std::nullopt, + std::optional<Register> Origin = std::nullopt); + [[nodiscard]] Expected<void> assign(Register VirtualReg, PhysicalRegister PhysicalReg); + [[nodiscard]] Expected<void> assignStackSlot(Register VirtualReg, FrameIndex StackSlot, + LaneMask Lanes = LaneMask::all()); + [[nodiscard]] Expected<void> markSplit(Register VirtualReg, Register Parent, Register Origin); + [[nodiscard]] Expected<void> setSpillable(Register VirtualReg, bool Spillable); + [[nodiscard]] VirtRegMapEntry *entry(Register VirtualReg) noexcept; + [[nodiscard]] const VirtRegMapEntry *entry(Register VirtualReg) const noexcept; + [[nodiscard]] std::optional<PhysicalRegister> + physicalRegister(Register VirtualReg) const noexcept; + [[nodiscard]] std::optional<FrameIndex> stackSlot(Register VirtualReg) const noexcept; + [[nodiscard]] bool isSpillable(Register VirtualReg) const noexcept; + [[nodiscard]] std::vector<const VirtRegMapEntry *> orderedEntries() const; + [[nodiscard]] Expected<void> verify() const; + +private: + MachineFunction *Function; + std::unordered_map<Register, VirtRegMapEntry> Entries; +}; + +[[nodiscard]] Expected<bool> rewriteVirtualRegisters(MachineFunction &Function, + const TargetDescription &Target, + const VirtRegMap &Mapping); + +class VirtualRegisterRewritePass final : public MachineFunctionPass { +public: + explicit VirtualRegisterRewritePass(const VirtRegMap &Mapping) noexcept : Mapping(&Mapping) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + const VirtRegMap *Mapping; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_VIRTREGMAP_H |