aboutsummaryrefslogtreecommitdiff
path: root/backend/include/rcc/CodeGen
diff options
context:
space:
mode:
Diffstat (limited to 'backend/include/rcc/CodeGen')
-rw-r--r--backend/include/rcc/CodeGen/MachineBlockPlacement.h7
-rw-r--r--backend/include/rcc/CodeGen/MachineBranchRelaxation.h5
-rw-r--r--backend/include/rcc/CodeGen/MachineCombiner.h5
-rw-r--r--backend/include/rcc/CodeGen/MachineCopyPropagation.h5
-rw-r--r--backend/include/rcc/CodeGen/MachinePass.h72
-rw-r--r--backend/include/rcc/CodeGen/MachinePipelinePasses.h4
-rw-r--r--backend/include/rcc/CodeGen/MachineSSAExit.h4
-rw-r--r--backend/include/rcc/CodeGen/PBQP/Solver.h49
-rw-r--r--backend/include/rcc/CodeGen/RegisterPressure.h2
-rw-r--r--backend/include/rcc/CodeGen/Spiller.h8
10 files changed, 136 insertions, 25 deletions
diff --git a/backend/include/rcc/CodeGen/MachineBlockPlacement.h b/backend/include/rcc/CodeGen/MachineBlockPlacement.h
index 27a06f4..52ddafd 100644
--- a/backend/include/rcc/CodeGen/MachineBlockPlacement.h
+++ b/backend/include/rcc/CodeGen/MachineBlockPlacement.h
@@ -15,9 +15,10 @@ public:
MachineAnalysisManager &Analyses) override;
private:
- [[nodiscard]] Expected<MachinePassResult>
- runImplementation(MachineFunction &Function, const TargetDescription &Target,
- MachineAnalysisManager &Analyses) const;
+ [[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function,
+ const TargetDescription &Target,
+ MachineAnalysisManager &Analyses,
+ MachineActionReplay &Actions) const;
};
} // namespace rcc
diff --git a/backend/include/rcc/CodeGen/MachineBranchRelaxation.h b/backend/include/rcc/CodeGen/MachineBranchRelaxation.h
index 1793a54..c88c1d5 100644
--- a/backend/include/rcc/CodeGen/MachineBranchRelaxation.h
+++ b/backend/include/rcc/CodeGen/MachineBranchRelaxation.h
@@ -27,8 +27,9 @@ public:
MachineAnalysisManager &Analyses) override;
private:
- [[nodiscard]] Expected<MachinePassResult>
- runImplementation(MachineFunction &Function, const TargetDescription &Target) const;
+ [[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function,
+ const TargetDescription &Target,
+ MachineActionReplay &Actions) const;
const TargetBranchInfo *Info;
MachineBranchRelaxationOptions Options;
diff --git a/backend/include/rcc/CodeGen/MachineCombiner.h b/backend/include/rcc/CodeGen/MachineCombiner.h
index 943d6ad..ef7f432 100644
--- a/backend/include/rcc/CodeGen/MachineCombiner.h
+++ b/backend/include/rcc/CodeGen/MachineCombiner.h
@@ -27,8 +27,9 @@ public:
MachineAnalysisManager &Analyses) override;
private:
- [[nodiscard]] Expected<MachinePassResult>
- runImplementation(MachineFunction &Function, const TargetDescription &Target) const;
+ [[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function,
+ const TargetDescription &Target,
+ MachineActionReplay &Actions) const;
const TargetMachineCombinerInfo *Info;
MachineCombinerStage Stage;
diff --git a/backend/include/rcc/CodeGen/MachineCopyPropagation.h b/backend/include/rcc/CodeGen/MachineCopyPropagation.h
index 5f84ac6..e8ee788 100644
--- a/backend/include/rcc/CodeGen/MachineCopyPropagation.h
+++ b/backend/include/rcc/CodeGen/MachineCopyPropagation.h
@@ -33,8 +33,9 @@ public:
MachineAnalysisManager &Analyses) override;
private:
- [[nodiscard]] Expected<MachinePassResult>
- runImplementation(MachineFunction &Function, const TargetDescription &Target) const;
+ [[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function,
+ const TargetDescription &Target,
+ MachineActionReplay &Actions) const;
const TargetSSAInfo *Info;
MachineCopyPropagationStage Stage;
diff --git a/backend/include/rcc/CodeGen/MachinePass.h b/backend/include/rcc/CodeGen/MachinePass.h
index 1637954..ee67924 100644
--- a/backend/include/rcc/CodeGen/MachinePass.h
+++ b/backend/include/rcc/CodeGen/MachinePass.h
@@ -5,6 +5,7 @@
#include "rcc/CodeGen/InstructionDescriptor.h"
#include "rcc/CodeGen/MachineFunctionProperties.h"
+#include "rcc/CodeGen/StableID.h"
#include "rcc/Support/Error.h"
#include <concepts>
@@ -279,6 +280,9 @@ public:
[[nodiscard]] Expected<std::unique_ptr<MachineAnalysisManager>> forkEmpty() const;
[[nodiscard]] Expected<bool>
requestAction(std::string_view Action, const MachineFunction &Function, std::uint64_t Cost = 1);
+ [[nodiscard]] Expected<bool> requestAction(std::string_view Rule, const MachineFunction &Function,
+ MachineInstrStableID Instruction,
+ std::uint64_t Cost = 1);
private:
using ErasedRunner = std::function<Expected<std::shared_ptr<void>>(
@@ -315,6 +319,7 @@ private:
std::unordered_map<MachineFunction *, std::unordered_map<AnalysisID, CacheEntry>> Cache;
std::unordered_map<MachineFunction *, std::vector<AnalysisID>> ActiveComputations;
MachinePassInstrumentation *Instrumentation = nullptr;
+ std::string ActivePass;
friend class MachinePassManager;
friend class CompilationUnitPassManager;
@@ -473,6 +478,58 @@ struct InstrumentationStatistic final {
std::uint64_t TotalNanoseconds = 0;
};
+struct MachineActionID final {
+ std::string Pass;
+ std::string Rule;
+ MachineFunctionStableID Function;
+ MachineInstrStableID Instruction;
+
+ [[nodiscard]] std::string toString() const;
+
+ friend bool operator==(const MachineActionID &, const MachineActionID &) = default;
+};
+
+struct MachineActionEvent final {
+ MachineActionID ID;
+ std::uint64_t Cost = 0;
+ bool Accepted = false;
+
+ friend bool operator==(const MachineActionEvent &, const MachineActionEvent &) = default;
+};
+
+class MachineActionReplay final {
+public:
+ explicit MachineActionReplay(MachineAnalysisManager &Analyses) noexcept : Analyses(&Analyses) {}
+ MachineActionReplay(
+ MachineAnalysisManager &Analyses,
+ const std::unordered_map<MachineInstrStableID, MachineInstrStableID> &SourceToClone)
+ : Analyses(&Analyses) {
+ for (const auto &[Source, Clone] : SourceToClone)
+ RecordingInstructionIDs.try_emplace(Clone, Source);
+ }
+
+ [[nodiscard]] Expected<bool> request(std::string_view Rule, const MachineFunction &Function,
+ MachineInstrStableID Instruction = {},
+ std::uint64_t Cost = 1);
+ void beginReplay() noexcept;
+ [[nodiscard]] Expected<void> finishReplay() const;
+
+private:
+ struct Decision final {
+ std::string Rule;
+ MachineFunctionStableID Function;
+ MachineInstrStableID Instruction;
+ std::uint64_t Cost = 0;
+ bool Accepted = false;
+ };
+
+ MachineAnalysisManager *Analyses = nullptr;
+ std::unordered_map<MachineInstrStableID, MachineInstrStableID> RecordingInstructionIDs;
+ std::vector<Decision> Decisions;
+ std::size_t NextDecision = 0;
+ bool IsReplaying = false;
+};
+
class MachinePassInstrumentation final {
public:
using BeforeCallback = std::function<void(std::string_view, const MachineFunction &)>;
@@ -489,8 +546,7 @@ public:
std::function<void(InstrumentationPhase, std::string_view, const MachineFunction &)>;
using ChangeCallback =
std::function<void(std::string_view, const MachineFunction &, MachinePassChanges, bool)>;
- using ActionFilter =
- std::function<bool(std::string_view, const MachineFunction &, std::uint64_t)>;
+ using ActionFilter = std::function<bool(const MachineActionID &, std::uint64_t)>;
using BeforeUnitCallback = std::function<void(std::string_view, const CompilationUnit &)>;
using AfterUnitCallback = std::function<void(std::string_view, const CompilationUnit &,
@@ -522,6 +578,7 @@ public:
void addUnitAnalysisFailureCallback(UnitAnalysisFailureCallback Callback);
[[nodiscard]] std::vector<InstrumentationStatistic> statistics() const;
+ [[nodiscard]] std::vector<MachineActionEvent> actionEvents() const;
void clearStatistics();
private:
@@ -548,7 +605,7 @@ private:
const Error &ErrorValue, std::uint64_t Nanoseconds) const;
void change(std::string_view Name, const MachineFunction &Function, MachinePassChanges Changes,
bool FingerprintChanged) const;
- [[nodiscard]] Expected<bool> requestAction(std::string_view Action,
+ [[nodiscard]] Expected<bool> requestAction(const MachineActionID &Action,
const MachineFunction &Function, std::uint64_t Cost);
void beforeUnit(std::string_view Name, const CompilationUnit &Unit) const;
@@ -577,6 +634,7 @@ private:
ActionFilter Filter;
std::optional<std::uint64_t> PerFunctionFuel;
std::unordered_map<std::uint64_t, std::uint64_t> ConsumedFuel;
+ std::vector<MachineActionEvent> ActionEvents;
std::vector<BeforeUnitCallback> BeforeUnit;
std::vector<AfterUnitCallback> AfterUnit;
@@ -602,6 +660,8 @@ struct MachinePassManagerOptions final {
class MachinePassManager final {
public:
+ using PassList = std::vector<std::unique_ptr<MachineFunctionPass>>;
+
explicit MachinePassManager(MachinePassManagerOptions Options = {}) : Options(Options) {}
MachinePassManager(const MachinePassManager &) = delete;
@@ -620,11 +680,15 @@ public:
return Passes.size();
}
+ [[nodiscard]] PassList takePasses() && noexcept {
+ return std::move(Passes);
+ }
+
private:
[[nodiscard]] Expected<void> validateContract(const MachinePassContract &Contract) const;
MachinePassManagerOptions Options;
- std::vector<std::unique_ptr<MachineFunctionPass>> Passes;
+ PassList Passes;
};
struct CompilationUnitPassManagerOptions final {
diff --git a/backend/include/rcc/CodeGen/MachinePipelinePasses.h b/backend/include/rcc/CodeGen/MachinePipelinePasses.h
index c5bdac0..08f0dac 100644
--- a/backend/include/rcc/CodeGen/MachinePipelinePasses.h
+++ b/backend/include/rcc/CodeGen/MachinePipelinePasses.h
@@ -21,7 +21,7 @@ public:
private:
[[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function,
const TargetDescription &Target,
- MachineAnalysisManager &Analyses);
+ MachineActionReplay &Actions);
const TargetLegalizerInfo *Info;
};
@@ -53,7 +53,7 @@ public:
private:
[[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function,
const TargetDescription &Target,
- MachineAnalysisManager &Analyses);
+ MachineActionReplay &Actions);
const TargetInstructionSelector *Info;
};
diff --git a/backend/include/rcc/CodeGen/MachineSSAExit.h b/backend/include/rcc/CodeGen/MachineSSAExit.h
index d98c0b9..fdf74f0 100644
--- a/backend/include/rcc/CodeGen/MachineSSAExit.h
+++ b/backend/include/rcc/CodeGen/MachineSSAExit.h
@@ -21,7 +21,7 @@ public:
private:
[[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function,
const TargetDescription &Target,
- MachineAnalysisManager &Analyses);
+ MachineActionReplay &Actions);
const TargetSSAInfo *Info = nullptr;
};
@@ -39,7 +39,7 @@ public:
private:
[[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function,
const TargetDescription &Target,
- MachineAnalysisManager &Analyses);
+ MachineActionReplay &Actions);
const TargetSSAInfo *Info = nullptr;
};
diff --git a/backend/include/rcc/CodeGen/PBQP/Solver.h b/backend/include/rcc/CodeGen/PBQP/Solver.h
index ff14857..f010fd1 100644
--- a/backend/include/rcc/CodeGen/PBQP/Solver.h
+++ b/backend/include/rcc/CodeGen/PBQP/Solver.h
@@ -9,6 +9,7 @@
#include <algorithm>
#include <cstddef>
#include <cstdint>
+#include <functional>
#include <map>
#include <optional>
#include <set>
@@ -18,9 +19,24 @@
namespace rcc::pbqp {
+enum class SolverActionKind : std::uint8_t {
+ Reduction,
+ Choice,
+};
+
+struct SolverAction final {
+ SolverActionKind Kind = SolverActionKind::Reduction;
+ ReductionKind Reduction = ReductionKind::DegreeZero;
+ NodeID Node;
+ std::size_t Value = 0;
+};
+
class DeterministicSolver final {
public:
- [[nodiscard]] Expected<Solution> solve(const Graph &Problem) const {
+ using ActionCallback = std::function<Expected<bool>(const SolverAction &)>;
+
+ [[nodiscard]] Expected<Solution> solve(const Graph &Problem,
+ const ActionCallback &Action = {}) const {
auto Verified = Problem.verify();
if (!Verified)
return std::unexpected(Verified.error());
@@ -31,10 +47,24 @@ public:
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);
+ const ReductionKind Kind = Degree == 0 ? ReductionKind::DegreeZero
+ : Degree == 1 ? ReductionKind::DegreeOne
+ : Degree == 2 ? ReductionKind::DegreeTwo
+ : ReductionKind::Heuristic;
+ if (Action) {
+ auto Accepted = Action({SolverActionKind::Reduction, Kind, Selected, Degree});
+ if (!Accepted)
+ return std::unexpected(Accepted.error());
+ if (!*Accepted) {
+ return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+ "PBQP reduction action was rejected");
+ }
+ }
+ Expected<ReductionRecord> Reduced =
+ Kind == ReductionKind::DegreeZero ? Work.reduceDegreeZero(Selected)
+ : Kind == ReductionKind::DegreeOne ? Work.reduceDegreeOne(Selected)
+ : Kind == ReductionKind::DegreeTwo ? Work.reduceDegreeTwo(Selected)
+ : Work.reduceHeuristically(Selected);
if (!Reduced)
return std::unexpected(Reduced.error());
Reductions.push_back(std::move(*Reduced));
@@ -71,6 +101,15 @@ public:
return makeUnexpected(ErrorCode::RegisterAllocationFailed,
"PBQP reductions produced no finite option");
}
+ if (Action) {
+ auto Accepted = Action({SolverActionKind::Choice, Record.Kind, Record.Node, Choice});
+ if (!Accepted)
+ return std::unexpected(Accepted.error());
+ if (!*Accepted) {
+ return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+ "PBQP choice action was rejected");
+ }
+ }
auto Set = Result.setSelection(Record.Node, Choice);
if (!Set)
return std::unexpected(Set.error());
diff --git a/backend/include/rcc/CodeGen/RegisterPressure.h b/backend/include/rcc/CodeGen/RegisterPressure.h
index fa1209a..107bc29 100644
--- a/backend/include/rcc/CodeGen/RegisterPressure.h
+++ b/backend/include/rcc/CodeGen/RegisterPressure.h
@@ -22,7 +22,7 @@ struct MachineBlockLiveness;
namespace detail {
struct RegisterPressureBuilder;
-}
+} // namespace detail
struct RegisterPressureValue final {
RegisterPressureSetID Set;
diff --git a/backend/include/rcc/CodeGen/Spiller.h b/backend/include/rcc/CodeGen/Spiller.h
index 3d1fc66..f63158d 100644
--- a/backend/include/rcc/CodeGen/Spiller.h
+++ b/backend/include/rcc/CodeGen/Spiller.h
@@ -11,13 +11,16 @@
namespace rcc {
+class MachineActionReplay;
+
class Spiller final {
public:
Spiller(MachineFunction &Function, const TargetDescription &Target,
const TargetRegisterAllocationInfo &TargetInfo, VirtRegMap &Mapping,
- bool EnableRematerialization = true)
+ bool EnableRematerialization = true, MachineActionReplay *Actions = nullptr)
: Function(&Function), Target(&Target), TargetInfo(&TargetInfo), Mapping(&Mapping),
- Edit(Function, Target, Mapping), EnableRematerialization(EnableRematerialization) {}
+ Edit(Function, Target, Mapping), EnableRematerialization(EnableRematerialization),
+ Actions(Actions) {}
[[nodiscard]] Expected<std::vector<Register>> spill(Register VirtualReg);
@@ -34,6 +37,7 @@ private:
VirtRegMap *Mapping;
LiveRangeEdit Edit;
bool EnableRematerialization;
+ MachineActionReplay *Actions;
};
} // namespace rcc
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-29 08:41:21 +0000