[CodeGen] Generate RISC-V macro fusion rules

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 {};
 }