Function sequant::eval::detail::ordered_schedule_topo_sort_steps¶

Defined in File ordered_schedule.hpp

Function Documentation¶

inline container::vector<Step> sequant::eval::detail::ordered_schedule_topo_sort_steps(container::vector<Step> items, container::vector<OrderedScheduleStepMeta> const &meta)¶

Topologically sort items (one already-built Step per entry, paired index-for-index with meta) by the local dependency edges among this block’s own steps: step A must precede step B whenever B’s requires_ names a value_id that’s in A’s produced. Kahn’s algorithm; among simultaneously-ready steps, always picks the smallest tie_key first, for a deterministic result when the true dependency order leaves steps genuinely unordered relative to each other.

A single scalar per step can be made to sort a child block before every value that reads its output (see build_ordered_schedule's own doc comment, part 3), but it cannot also guarantee a step sorts after every value its own content reads as an input — those are two independent constraints a single total order satisfies only when they happen to agree. A topological sort over the actual per-step dependency edges satisfies both directions by construction, and tie_key serves only to break ties among steps with no dependency relation to each other at all.

SEQUANT_ASSERT's that every item is placed exactly once (a cycle in this local edge set would be a bug — these edges are a sub-relation of the whole-forest DAG’s edges, restricted to one block’s own siblings, so they inherit its acyclicity), then re-derives the local edges a second time against the final order and SEQUANT_ASSERT's every one is actually satisfied (a loud tripwire against any violation of this invariant rather than a silent mis-order).