aboutsummaryrefslogtreecommitdiff
path: root/backend/lib/CodeGen
diff options
context:
space:
mode:
Diffstat (limited to 'backend/lib/CodeGen')
-rw-r--r--backend/lib/CodeGen/CMakeLists.txt2
-rw-r--r--backend/lib/CodeGen/MachineOptimizationPipeline.cpp6
-rw-r--r--backend/lib/CodeGen/MachineScheduler.cpp26
-rw-r--r--backend/lib/CodeGen/MacroFusion.cpp168
-rw-r--r--backend/lib/CodeGen/PostRAScheduler.cpp4
-rw-r--r--backend/lib/CodeGen/ScheduleDAG.cpp161
-rw-r--r--backend/lib/CodeGen/TargetDescription.cpp14
-rw-r--r--backend/lib/CodeGen/TargetSchedulingModel.cpp4
8 files changed, 347 insertions, 38 deletions
diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt
index 6a7f38d..2fc7254 100644
--- a/backend/lib/CodeGen/CMakeLists.txt
+++ b/backend/lib/CodeGen/CMakeLists.txt
@@ -58,6 +58,7 @@ set(
PostRAScheduler.cpp
RegisterPressure.cpp
RegisterScavenger.cpp
+ MacroFusion.cpp
ScheduleDAG.cpp
ScheduleHazardRecognizer.cpp
InlineSpiller.cpp
@@ -95,6 +96,7 @@ set(
"${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/InstructionDescriptor.h"
"${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/InlineAsm.h"
"${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LowLevelType.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MacroFusion.h"
"${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineBasicBlockAttributes.h"
"${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineCFIInfo.h"
"${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineCompilationStatus.h"
diff --git a/backend/lib/CodeGen/MachineOptimizationPipeline.cpp b/backend/lib/CodeGen/MachineOptimizationPipeline.cpp
index f96d544..adec384 100644
--- a/backend/lib/CodeGen/MachineOptimizationPipeline.cpp
+++ b/backend/lib/CodeGen/MachineOptimizationPipeline.cpp
@@ -71,7 +71,8 @@ Expected<void> addPreRegisterAllocationOptimizationPipeline(
MachineCombinerStage::PreRegisterAllocation);
if (!Added)
return std::unexpected(Added.error());
- return addPass<MachineSchedulerPass>(Pipeline, TargetInfo.SchedulingModel);
+ return addPass<MachineSchedulerPass>(Pipeline, TargetInfo.SchedulingModel,
+ TargetInfo.SchedulerOptions);
}
Expected<void>
@@ -112,7 +113,8 @@ addPostRegisterAllocationPipeline(MachineFunctionPassManager &Pipeline,
Added = addPass<ExpandPostRAPseudosPass>(Pipeline, TargetInfo.PseudoExpansion);
if (!Added)
return std::unexpected(Added.error());
- Added = addPass<PostRASchedulerPass>(Pipeline, TargetInfo.SchedulingModel);
+ Added = addPass<PostRASchedulerPass>(Pipeline, TargetInfo.SchedulingModel,
+ TargetInfo.SchedulerOptions);
if (!Added)
return std::unexpected(Added.error());
Added = addPass<MachineBlockPlacementPass>(Pipeline);
diff --git a/backend/lib/CodeGen/MachineScheduler.cpp b/backend/lib/CodeGen/MachineScheduler.cpp
index 9fffa65..302173f 100644
--- a/backend/lib/CodeGen/MachineScheduler.cpp
+++ b/backend/lib/CodeGen/MachineScheduler.cpp
@@ -18,6 +18,7 @@
#include <algorithm>
#include <cstddef>
#include <cstdint>
+#include <iostream>
#include <limits>
#include <optional>
#include <ranges>
@@ -89,14 +90,17 @@ struct ScheduleCandidate final {
std::uint64_t CriticalPath = 0;
std::uint32_t Latency = 0;
std::int64_t TargetPreference = 0;
+ bool ContinuesCluster = false;
bool OptimizeLatency = false;
- std::uint64_t StableID = 0;
+ std::size_t StableOrder = 0;
};
[[nodiscard]] bool isBetterCandidate(const ScheduleCandidate &Left,
const ScheduleCandidate &Right) noexcept {
if (Left.Cycle != Right.Cycle)
return Left.Cycle < Right.Cycle;
+ if (Left.ContinuesCluster != Right.ContinuesCluster)
+ return Left.ContinuesCluster;
if (Left.TargetPreference != Right.TargetPreference)
return Left.TargetPreference > Right.TargetPreference;
if (Left.OptimizeLatency && Right.OptimizeLatency) {
@@ -115,8 +119,8 @@ struct ScheduleCandidate final {
return Left.CriticalPath > Right.CriticalPath;
if (Left.Latency != Right.Latency)
return Left.Latency > Right.Latency;
- if (Left.StableID != Right.StableID)
- return Left.StableID < Right.StableID;
+ if (Left.StableOrder != Right.StableOrder)
+ return Left.StableOrder < Right.StableOrder;
return !Left.Bottom && Right.Bottom;
}
@@ -177,8 +181,9 @@ scheduleDAG(const ScheduleDAG &DAG, const MachineFunction &Function,
Unit.Latency,
Model.hooks().candidatePreference(Unit, ScheduleDirection::TopDown, DAG.block(),
BlockFrequency),
+ Unit.ClusterPredecessor && Scheduled[*Unit.ClusterPredecessor],
BlockFrequency >= MachineBlockFrequencyAnalysis::EntryFrequency,
- Unit.StableID.value()};
+ Unit.ID};
if (!Best || isBetterCandidate(Candidate, *Best))
Best = Candidate;
}
@@ -198,8 +203,9 @@ scheduleDAG(const ScheduleDAG &DAG, const MachineFunction &Function,
Unit.Latency,
Model.hooks().candidatePreference(Unit, ScheduleDirection::BottomUp, DAG.block(),
BlockFrequency),
+ Unit.ClusterSuccessor && Scheduled[*Unit.ClusterSuccessor],
BlockFrequency >= MachineBlockFrequencyAnalysis::EntryFrequency,
- Unit.StableID.value()};
+ Unit.ID};
if (!Best || isBetterCandidate(Candidate, *Best))
Best = Candidate;
}
@@ -270,7 +276,11 @@ scheduleRegion(MachineBasicBlock &Block, std::span<MachineInstr *const> Instruct
MachineSchedulerOptions Options, MachineActionReplay *Actions) {
if (Instructions.size() < 2 || Instructions.size() > Options.MaximumRegionSize)
return false;
- auto DAG = ScheduleDAG::build(Block, Instructions, Function, Target, Model, Mode);
+ if (Options.EmitDebugOutput) {
+ std::cerr << Function.name() << ":%bb." << Block.denseNumber().value_or(0) << '\n';
+ }
+ auto DAG = ScheduleDAG::build(Block, Instructions, Function, Target, Model, Mode,
+ Options.EmitDebugOutput);
if (!DAG)
return std::unexpected(DAG.error());
if (DAG->units().size() < 2)
@@ -408,9 +418,11 @@ Expected<MachinePassResult> MachineSchedulerPass::run(MachineFunction &Function,
if (!TrialFrequencies)
return std::unexpected(TrialFrequencies.error());
MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
+ MachineSchedulerOptions TrialOptions = Options;
+ TrialOptions.EmitDebugOutput = false;
auto TrialResult = runMachineScheduler(*Trial->ClonedFunction, Target, *Model,
ScheduleDAGMode::PreRegisterAllocation, **TrialLiveness,
- **TrialFrequencies, Options, &Actions);
+ **TrialFrequencies, TrialOptions, &Actions);
if (!TrialResult)
return std::unexpected(TrialResult.error());
diff --git a/backend/lib/CodeGen/MacroFusion.cpp b/backend/lib/CodeGen/MacroFusion.cpp
new file mode 100644
index 0000000..726ca59
--- /dev/null
+++ b/backend/lib/CodeGen/MacroFusion.cpp
@@ -0,0 +1,168 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MacroFusion.h"
+
+#include "rcc/CodeGen/InstructionDescriptor.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/ScheduleDAG.h"
+#include "rcc/CodeGen/TargetDescription.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <iostream>
+#include <optional>
+#include <ranges>
+#include <span>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] const MachineInstr *instructionFor(MacroFusionInstruction Side,
+ const MachineInstr *First,
+ const MachineInstr &Second) noexcept {
+ return Side == MacroFusionInstruction::First ? First : &Second;
+}
+
+[[nodiscard]] std::optional<Register> registerAt(const MachineInstr &Instruction,
+ std::uint32_t OperandIndex) noexcept {
+ const MachineOperand *Operand = Instruction.operandAt(OperandIndex);
+ return Operand == nullptr ? std::nullopt : Operand->registerValue();
+}
+
+[[nodiscard]] const std::int64_t *immediateAt(const MachineInstr &Instruction,
+ std::uint32_t OperandIndex) noexcept {
+ const MachineOperand *Operand = Instruction.operandAt(OperandIndex);
+ return Operand == nullptr ? nullptr : Operand->getIf<std::int64_t>();
+}
+
+[[nodiscard]] bool containsOpcode(std::span<const Opcode> Opcodes, Opcode Value) noexcept {
+ return std::ranges::contains(Opcodes, Value);
+}
+
+[[nodiscard]] bool matchesLink(const MacroFusionRule &Rule, const MachineInstr &First,
+ const MachineInstr &Second) noexcept {
+ const std::optional<Register> FirstDefinition = registerAt(First, Rule.FirstDefinitionOperand);
+ const std::optional<Register> SecondUse = registerAt(Second, Rule.SecondUseOperand);
+ const std::optional<Register> AlternateSecondUse =
+ Rule.CommutableSecondUseOperand == MacroFusionRule::NoOperand
+ ? std::nullopt
+ : registerAt(Second, Rule.CommutableSecondUseOperand);
+ if (!FirstDefinition ||
+ (*FirstDefinition != SecondUse && *FirstDefinition != AlternateSecondUse)) {
+ return false;
+ }
+
+ if (Rule.RequireSingleNonDebugUse && FirstDefinition->isVirtual() &&
+ !Second.function().registerInfo().hasOneUse(*FirstDefinition, false)) {
+ return false;
+ }
+
+ if (!Rule.RequireSecondDestinationTie)
+ return true;
+ const std::optional<Register> SecondDefinition = registerAt(Second, Rule.SecondDefinitionOperand);
+ if (!SecondDefinition || SecondDefinition->isVirtual())
+ return SecondDefinition.has_value();
+ return *SecondDefinition == SecondUse || *SecondDefinition == AlternateSecondUse;
+}
+
+[[nodiscard]] bool isFusionCandidateDependency(ScheduleDependencyKind Kind) noexcept {
+ return Kind != ScheduleDependencyKind::Anti && Kind != ScheduleDependencyKind::Output &&
+ Kind != ScheduleDependencyKind::Cluster;
+}
+
+[[nodiscard]] std::string_view opcodeName(const TargetDescription &Target, Opcode Value) noexcept {
+ const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Value);
+ return Descriptor == nullptr ? std::string_view{"<unknown>"} : Descriptor->Name;
+}
+
+} // namespace
+
+bool matchesMacroFusion(const MacroFusionRule &Rule, const MachineInstr *First,
+ const MachineInstr &Second) noexcept {
+ if (!containsOpcode(Rule.SecondOpcodes, Second.opcode()))
+ return false;
+ if (First == nullptr)
+ return true;
+ if (!containsOpcode(Rule.FirstOpcodes, First->opcode()))
+ return false;
+ if (!Rule.OpcodePairs.empty() &&
+ std::ranges::none_of(Rule.OpcodePairs, [First, &Second](MacroFusionOpcodePair Pair) {
+ return Pair.First == First->opcode() && Pair.Second == Second.opcode();
+ })) {
+ return false;
+ }
+
+ for (const MacroFusionImmediatePredicate &Predicate : Rule.ImmediatePredicates) {
+ const MachineInstr *Instruction = instructionFor(Predicate.Instruction, First, Second);
+ const std::int64_t *Value =
+ Instruction == nullptr ? nullptr : immediateAt(*Instruction, Predicate.OperandIndex);
+ if (Value == nullptr || *Value < Predicate.Minimum || *Value > Predicate.Maximum)
+ return false;
+ }
+ for (const MacroFusionRegisterInequality &Predicate : Rule.RegisterInequalities) {
+ const MachineInstr *Instruction = instructionFor(Predicate.Instruction, First, Second);
+ if (Instruction == nullptr)
+ return false;
+ const std::optional<Register> Left = registerAt(*Instruction, Predicate.LeftOperand);
+ const std::optional<Register> Right = registerAt(*Instruction, Predicate.RightOperand);
+ if (!Left || !Right || *Left == *Right)
+ return false;
+ }
+ for (const MacroFusionImmediateRelation &Predicate : Rule.ImmediateRelations) {
+ const std::int64_t *FirstValue = immediateAt(*First, Predicate.FirstOperand);
+ const std::int64_t *SecondValue = immediateAt(Second, Predicate.SecondOperand);
+ if (FirstValue == nullptr || SecondValue == nullptr || *FirstValue > *SecondValue)
+ return false;
+ }
+ return matchesLink(Rule, *First, Second);
+}
+
+Expected<void> applyMacroFusion(ScheduleDAG &DAG, std::span<const MacroFusionRule> Rules,
+ const TargetDescription &Target, bool EmitDebugOutput) {
+ if (Rules.empty())
+ return {};
+ for (ScheduleUnit &Anchor : DAG.units()) {
+ if (Anchor.Instructions.size() != 1 || Anchor.ClusterPredecessor || Anchor.ClusterSuccessor)
+ continue;
+ const MachineInstr &Second = *Anchor.Instructions.front();
+ if (std::ranges::none_of(Rules, [&Second](const MacroFusionRule &Rule) {
+ return matchesMacroFusion(Rule, nullptr, Second);
+ })) {
+ continue;
+ }
+ const std::vector<ScheduleDependency> Predecessors = Anchor.Predecessors;
+ for (const ScheduleDependency &Dependency : Predecessors) {
+ if (!isFusionCandidateDependency(Dependency.Kind))
+ continue;
+ const ScheduleUnit *FirstUnit = DAG.unit(Dependency.Source);
+ if (FirstUnit == nullptr || FirstUnit->Instructions.size() != 1 ||
+ FirstUnit->ClusterPredecessor || FirstUnit->ClusterSuccessor) {
+ continue;
+ }
+ const MachineInstr &First = *FirstUnit->Instructions.front();
+ if (std::ranges::none_of(Rules, [&First, &Second](const MacroFusionRule &Rule) {
+ return matchesMacroFusion(Rule, &First, Second);
+ })) {
+ continue;
+ }
+ auto Fused = DAG.fuseInstructionPair(FirstUnit->ID, Anchor.ID);
+ if (!Fused)
+ return std::unexpected(Fused.error());
+ if (!*Fused)
+ continue;
+ if (EmitDebugOutput) {
+ std::cerr << "Macro fuse: SU(" << FirstUnit->ID << ") - SU(" << Anchor.ID << ") / "
+ << opcodeName(Target, First.opcode()) << " - "
+ << opcodeName(Target, Second.opcode()) << '\n';
+ }
+ break;
+ }
+ }
+ return {};
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/PostRAScheduler.cpp b/backend/lib/CodeGen/PostRAScheduler.cpp
index d2feb92..7f5c697 100644
--- a/backend/lib/CodeGen/PostRAScheduler.cpp
+++ b/backend/lib/CodeGen/PostRAScheduler.cpp
@@ -73,9 +73,11 @@ Expected<MachinePassResult> PostRASchedulerPass::run(MachineFunction &Function,
if (!TrialFrequencies)
return std::unexpected(TrialFrequencies.error());
MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
+ MachineSchedulerOptions TrialOptions = Options;
+ TrialOptions.EmitDebugOutput = false;
auto TrialRun = runMachineScheduler(*Trial->ClonedFunction, Target, *Model,
ScheduleDAGMode::PostRegisterAllocation, **TrialLiveness,
- **TrialFrequencies, Options, &Actions);
+ **TrialFrequencies, TrialOptions, &Actions);
if (!TrialRun)
return std::unexpected(TrialRun.error());
auto TrialRepair =
diff --git a/backend/lib/CodeGen/ScheduleDAG.cpp b/backend/lib/CodeGen/ScheduleDAG.cpp
index 8696f2e..9fba862 100644
--- a/backend/lib/CodeGen/ScheduleDAG.cpp
+++ b/backend/lib/CodeGen/ScheduleDAG.cpp
@@ -168,13 +168,16 @@ maskKeys(const RegisterMask &Mask, const TargetDescription &Target) {
});
}
+[[nodiscard]] bool isHazardDependency(ScheduleDependencyKind Kind) noexcept {
+ return Kind == ScheduleDependencyKind::Anti || Kind == ScheduleDependencyKind::Output;
+}
+
} // namespace
-Expected<ScheduleDAG> ScheduleDAG::build(MachineBasicBlock &Block,
- std::span<MachineInstr *const> Instructions,
- const MachineFunction &Function,
- const TargetDescription &Target,
- const TargetSchedulingModel &Model, ScheduleDAGMode Mode) {
+Expected<ScheduleDAG>
+ScheduleDAG::build(MachineBasicBlock &Block, std::span<MachineInstr *const> Instructions,
+ const MachineFunction &Function, const TargetDescription &Target,
+ const TargetSchedulingModel &Model, ScheduleDAGMode Mode, bool EmitDebugOutput) {
if (&Block.function() != &Function)
return makeUnexpected(ErrorCode::InvalidArgument,
"schedule DAG block belongs to another function");
@@ -191,10 +194,12 @@ Expected<ScheduleDAG> ScheduleDAG::build(MachineBasicBlock &Block,
auto Order = Result.buildOrderDependencies(Target);
if (!Order)
return std::unexpected(Order.error());
- auto Mutated = Model.hooks().mutateScheduleDAG(Result, Function, Target, Mode);
+ auto Mutated = Model.hooks().mutateScheduleDAG(Result, Function, Target, Mode, EmitDebugOutput);
if (!Mutated)
return std::unexpected(Mutated.error());
- Result.computeCriticalPaths();
+ auto CriticalPaths = Result.computeCriticalPaths();
+ if (!CriticalPaths)
+ return std::unexpected(CriticalPaths.error());
return Result;
}
@@ -382,15 +387,101 @@ Expected<void> ScheduleDAG::buildRegisterDependencies(const MachineFunction &Fun
Expected<void> ScheduleDAG::addArtificialDependency(std::size_t Source, std::size_t Destination,
std::uint32_t Latency) {
- if (Source >= Units.size() || Destination >= Units.size() || Source >= Destination) {
- return makeUnexpected(
- ErrorCode::InvalidArgument,
- "target schedule mutation requires a forward dependency between known units");
+ if (Source >= Units.size() || Destination >= Units.size() || Source == Destination) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "target schedule mutation requires distinct known schedule units");
}
+ if (hasPath(Destination, Source))
+ return makeUnexpected(ErrorCode::SchedulingFailed,
+ "target schedule mutation would introduce a dependency cycle");
addDependency(Source, Destination, ScheduleDependencyKind::Artificial, Latency);
return {};
}
+bool ScheduleDAG::hasPath(std::size_t Source, std::size_t Destination) const {
+ if (Source >= Units.size() || Destination >= Units.size())
+ return false;
+ std::vector<bool> Visited(Units.size());
+ std::vector<std::size_t> Pending = {Source};
+ Visited[Source] = true;
+ while (!Pending.empty()) {
+ const std::size_t Current = Pending.back();
+ Pending.pop_back();
+ for (const ScheduleDependency &Dependency : Units[Current].Successors) {
+ if (Dependency.Destination == Destination)
+ return true;
+ if (!Visited[Dependency.Destination]) {
+ Visited[Dependency.Destination] = true;
+ Pending.push_back(Dependency.Destination);
+ }
+ }
+ }
+ return false;
+}
+
+bool ScheduleDAG::hasDirectDependency(std::size_t Source, std::size_t Destination) const {
+ if (Source >= Units.size() || Destination >= Units.size())
+ return false;
+ return std::ranges::any_of(Units[Source].Successors,
+ [Destination](const ScheduleDependency &Dependency) {
+ return Dependency.Destination == Destination;
+ });
+}
+
+Expected<bool> ScheduleDAG::fuseInstructionPair(std::size_t First, std::size_t Second) {
+ if (First >= Units.size() || Second >= Units.size() || First == Second) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "macro fusion requires two distinct known schedule units");
+ }
+ ScheduleUnit &FirstUnit = Units[First];
+ ScheduleUnit &SecondUnit = Units[Second];
+ if (FirstUnit.ClusterPredecessor || FirstUnit.ClusterSuccessor || SecondUnit.ClusterPredecessor ||
+ SecondUnit.ClusterSuccessor || hasPath(Second, First)) {
+ return false;
+ }
+
+ struct Binding final {
+ std::size_t Source = 0;
+ std::size_t Destination = 0;
+ };
+ std::vector<Binding> Bindings;
+ const std::vector<ScheduleDependency> FirstSuccessors = FirstUnit.Successors;
+ const std::vector<ScheduleDependency> SecondPredecessors = SecondUnit.Predecessors;
+ for (const ScheduleDependency &Dependency : FirstSuccessors) {
+ if (Dependency.Kind == ScheduleDependencyKind::Cluster || isHazardDependency(Dependency.Kind) ||
+ Dependency.Destination == Second || hasDirectDependency(Dependency.Destination, Second)) {
+ continue;
+ }
+ if (hasPath(Dependency.Destination, Second))
+ return false;
+ Bindings.push_back({Second, Dependency.Destination});
+ }
+ for (const ScheduleDependency &Dependency : SecondPredecessors) {
+ if (Dependency.Kind == ScheduleDependencyKind::Cluster || isHazardDependency(Dependency.Kind) ||
+ Dependency.Source == First || hasDirectDependency(First, Dependency.Source)) {
+ continue;
+ }
+ if (hasPath(First, Dependency.Source))
+ return false;
+ Bindings.push_back({Dependency.Source, First});
+ }
+
+ addDependency(First, Second, ScheduleDependencyKind::Cluster, 0);
+ FirstUnit.ClusterSuccessor = Second;
+ SecondUnit.ClusterPredecessor = First;
+ for (ScheduleDependency &Dependency : FirstUnit.Successors) {
+ if (Dependency.Destination == Second)
+ Dependency.Latency = 0;
+ }
+ for (ScheduleDependency &Dependency : SecondUnit.Predecessors) {
+ if (Dependency.Source == First)
+ Dependency.Latency = 0;
+ }
+ for (const Binding &Binding : Bindings)
+ addDependency(Binding.Source, Binding.Destination, ScheduleDependencyKind::Artificial, 0);
+ return true;
+}
+
Expected<void> ScheduleDAG::buildMemoryDependencies(const TargetDescription &Target) {
MachineAliasAnalysis::Result Aliases;
for (std::size_t LaterIndex = 0; LaterIndex < Units.size(); ++LaterIndex) {
@@ -488,8 +579,38 @@ void ScheduleDAG::addDependency(std::size_t Source, std::size_t Destination,
Units[Destination].Predecessors.push_back(Dependency);
}
-void ScheduleDAG::computeCriticalPaths() {
- for (ScheduleUnit &Unit : Units) {
+Expected<void> ScheduleDAG::computeCriticalPaths() {
+ std::vector<std::size_t> RemainingPredecessors;
+ RemainingPredecessors.reserve(Units.size());
+ for (const ScheduleUnit &Unit : Units)
+ RemainingPredecessors.push_back(Unit.Predecessors.size());
+ std::vector<std::size_t> TopologicalOrder;
+ TopologicalOrder.reserve(Units.size());
+ std::vector<bool> Emitted(Units.size());
+ for (std::size_t Count = 0; Count < Units.size(); ++Count) {
+ std::optional<std::size_t> Next;
+ for (const ScheduleUnit &Unit : Units) {
+ if (!Emitted[Unit.ID] && RemainingPredecessors[Unit.ID] == 0) {
+ Next = Unit.ID;
+ break;
+ }
+ }
+ if (!Next) {
+ return makeUnexpected(ErrorCode::SchedulingFailed,
+ "schedule DAG contains a cyclic target mutation");
+ }
+ Emitted[*Next] = true;
+ TopologicalOrder.push_back(*Next);
+ for (const ScheduleDependency &Dependency : Units[*Next].Successors) {
+ if (RemainingPredecessors[Dependency.Destination] == 0) {
+ return makeUnexpected(ErrorCode::InternalError,
+ "schedule DAG predecessor count underflowed");
+ }
+ --RemainingPredecessors[Dependency.Destination];
+ }
+ }
+ for (const std::size_t ID : TopologicalOrder) {
+ ScheduleUnit &Unit = Units[ID];
Unit.Depth = 0;
for (const ScheduleDependency &Dependency : Unit.Predecessors) {
Unit.Depth =
@@ -497,18 +618,20 @@ void ScheduleDAG::computeCriticalPaths() {
static_cast<std::uint64_t>(Dependency.Latency)));
}
}
- for (auto Position = Units.rbegin(); Position != Units.rend(); ++Position) {
- Position->Height = Position->Latency;
- for (const ScheduleDependency &Dependency : Position->Successors) {
- Position->Height =
- std::max(Position->Height, saturatingAdd(Units[Dependency.Destination].Height,
- static_cast<std::uint64_t>(Dependency.Latency)));
+ for (auto Position = TopologicalOrder.rbegin(); Position != TopologicalOrder.rend(); ++Position) {
+ ScheduleUnit &Unit = Units[*Position];
+ Unit.Height = Unit.Latency;
+ for (const ScheduleDependency &Dependency : Unit.Successors) {
+ Unit.Height =
+ std::max(Unit.Height, saturatingAdd(Units[Dependency.Destination].Height,
+ static_cast<std::uint64_t>(Dependency.Latency)));
}
}
for (ScheduleUnit &Unit : Units) {
std::ranges::sort(Unit.Predecessors, {}, &ScheduleDependency::Source);
std::ranges::sort(Unit.Successors, {}, &ScheduleDependency::Destination);
}
+ return {};
}
} // namespace rcc
diff --git a/backend/lib/CodeGen/TargetDescription.cpp b/backend/lib/CodeGen/TargetDescription.cpp
index ab77965..3701add 100644
--- a/backend/lib/CodeGen/TargetDescription.cpp
+++ b/backend/lib/CodeGen/TargetDescription.cpp
@@ -345,10 +345,10 @@ Expected<void> TargetDescription::validateTargetOperand(const OperandDescriptor
if (!EffectiveClass || !Registers.isSubclass(*EffectiveClass, *Descriptor->RegClass)) {
const std::string ActualClass =
EffectiveClass ? std::to_string(EffectiveClass->value()) : "<none>";
- return makeUnexpected(
- ErrorCode::VerificationError,
- "virtual register class " + ActualClass + " does not satisfy required class " +
- std::to_string(Descriptor->RegClass->value()));
+ return makeUnexpected(ErrorCode::VerificationError,
+ "virtual register class " + ActualClass +
+ " does not satisfy required class " +
+ std::to_string(Descriptor->RegClass->value()));
}
}
return {};
@@ -469,9 +469,9 @@ TargetDescription::validateExplicitOperands(Opcode InstructionOpcode,
auto TargetValidation =
validateTargetOperand(&descriptorForOperand(*Descriptor, Index), Operands[Index], RegInfo);
if (!TargetValidation)
- return std::unexpected(withErrorContext(
- TargetValidation.error(), "operand " + std::to_string(Index) + " of '" +
- Descriptor->Name + "': "));
+ return std::unexpected(
+ withErrorContext(TargetValidation.error(), "operand " + std::to_string(Index) + " of '" +
+ Descriptor->Name + "': "));
}
return {};
}
diff --git a/backend/lib/CodeGen/TargetSchedulingModel.cpp b/backend/lib/CodeGen/TargetSchedulingModel.cpp
index 97abecd..f462c21 100644
--- a/backend/lib/CodeGen/TargetSchedulingModel.cpp
+++ b/backend/lib/CodeGen/TargetSchedulingModel.cpp
@@ -49,8 +49,8 @@ bool TargetSchedulingHooks::isSchedulingBoundary(const MachineInstr &,
}
Expected<void> TargetSchedulingHooks::mutateScheduleDAG(ScheduleDAG &, const MachineFunction &,
- const TargetDescription &,
- ScheduleDAGMode) const {
+ const TargetDescription &, ScheduleDAGMode,
+ bool) const {
return {};
}
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-29 16:09:27 +0000