Namespace sequant::eval::detail

The deterministic sequencer lowers the LegalitySchedule (per-value home_floor / per_axis roles) plus the RichSchedule (per-value first_use / last_use over the forest’s single post-order static-point timeline) into an OrderedSchedule.

Detailed Description

Static peak-profile analysis over an eval forest (see doc/dev/specs/2026-09-12-batched-array-dag-eval-as-built.md, section 5).

The realized chain is per loop instance, not per axis type: one block per distinct fusion loop_slot appearing on a space across all cells, so a value carrying two same-space modes on different slots gets two nested loops, not one. A nest holding members of more than one pass additionally emits one sibling block per pass (latitude = pass), run in schedule order (see step 2b and forced_split_levels). See the as-built design section 6.1, doc/dev/specs/2026-09-12-batched-array-dag-eval-as-built.md.

Four-part algorithm, pure scheduling (no cost choice):

1. The canonical chain For each batch axis space (IndexSpace::base_key()) appearing in any cell’s CellLegality::per_axis (not just home_floor a None must still get a block to host its escape output, even though no cell is homed inside it in that role), one realized depth per distinct fusion loop_slot on it (slots_of_space / type_slot, resolved through fusion_slot). Spaces are ordered by mode_order (most-significant/outermost first), ties/ unlisted spaces alphabetical, slot-ascending within a space but that is only a stable tie-break: the nesting actually satisfies every RichSchedule::loop_order pair, and a cycle among those is a builder error. Loop members that never co-occur (no value is home-sliced on both) are then cut into disjoint nests by a union-find (type_cluster / cluster_min) and concatenated at root, rather than realized as one over-deep chain.

2. Per-value placement: home BuildStep vs. escape output A value’s CellLegality::per_axis has, by construction (see None own doc comment), only LoopLocal, Reduction, or LoopCarried entries (never the implicit LoopInvariant). Two cases:

  • every per_axis entry is LoopLocal (this includes the empty case: no batch-axis dependence at all, e.g. water-20’s I``(i,i;a,a))  the value is a plain ``BuildStep. Its home block is the depth whose accumulated (root-to-depth) type set equals home_floor's type set (root if home_floor is empty), by set equality (an unmatched/non-prefix home_floor falls back to root). This value gets no outputs entry anywhere (see well_formed's single- producer invariant): “Transient” (design point 4) is realized as “produced by a c BuildStep and nothing else”, not as an explicit OutputKind::Transient outputs record, since well_formed::detail::collect_production_ids counts every outputs entry (regardless of OutputKind) as an independent production site a Transient outputs entry alongside the BuildStep would be flagged as double-production.

  • at least one per_axis entry is Reduction or LoopCarried (“escapes” that axis, per design point 4: Reduction -> accumulate-summed out, LoopCarried -> accumulate-scattered out) the value has no BuildStep anywhere; instead it is recorded as an outputs entry (kind AccumulateSum / AccumulateScatter) of each escaped instance’s block. With more than one escape this is a multi-level escape chain: raw production at the deepest escape site, pure forwarding at every shallower one. The innermost escaped loop is where the accumulation the value’s own node performs actually happens, so that block is its true production site; an outer escape on a shallower axis needs this value already complete before the outer loop can close exactly consistent with an outer accumulator reading an inner one. A chain may legitimately skip a level the value is invariant on; that crossing is carried by residency plus produce_if_absent, not by an escape (as-built section 6.2).

3. Topological order within a block a real topological sort Each block’s own steps interleave its None (one per value homed there) with, if the chain continues, one nested child ScopeBlock Step for the next-deeper axis. These are ordered by detail::ordered_schedule_topo_sort_steps against a per-step dependency graph, not a scalar key alone (see below for why a scalar key cannot suffice), reconstructed from rich alone no forest access needed:

  • global direct-dependency edges: for every OccurrenceRec of every value, its consumer_point names the static point of its structural parent node; resolving that point back to the value_id whose own occurrence starts there (point_owner, built once up front) recovers “this parent value directly reads that child value” the exact same edges the forest itself encodes, without needing the forest.

  • Per level (one None own steps list, including root), each candidate step gets a None

    • a None produced = {v}; its requires_ = every value_id v directly reads (raw, unfiltered irrelevant/ external entries are dropped by the topo-sort itself, since they simply never match a local produced set).

    • a nested child block’s produced = that block’s own top-level outputs value_id’s (what it makes visible to its own parent’s siblings its internal None and any further-nested child’s content are never directly readable from outside it: by construction, a value crossing a block boundary as an operand must first have been resolved out of that axis, which is exactly the escape/outputs case). Its requires_ is the full, recursively bubbled external need of its whole subtree (built bottom-up alongside the block itself: requires_all(level) = (this level’s own direct needs union its child’s already-bubbled requires_all) minus produced_all(level), where produced_all is everything ever produced anywhere in the subtree, recursively) so a need that is only satisfiable several levels further out (e.g. a root-homed common factor consumed by a value nested two axes deep) still surfaces at whichever level can actually satisfy it.

  • Ties (two ready steps with no dependency relation to each other) are broken by tie_key ascending: a None is its value’s own ValueCell::first_use; a child block’s is the min first_use over its own produced_all (deterministic, and though correctness rests on the real edges, which enforce both directions it places a block as early as its own true dependency slack allows).

A single scalar key alone cannot express both directions of this at once. Taking the min first_use as the sort key itself is sound for “the block sorts before every true consumer”, but carries no corresponding guarantee for “the block sorts after every true input it reads”: a value produced by a same-level sibling BuildStep (e.g. a root-homed operand consumed by content nested inside a child block) can land, by raw point value, after the block’s min-derived key, mis-ordering the schedule with no structural check to catch it. The topological sort above satisfies both directions by construction and is checked twice (no-cycle placement count, then a second pass confirming every edge survived the final order) see ordered_schedule_topo_sort_steps's own doc comment.

policy is accepted for interface symmetry with the rest of the pipeline (every stage from analyze_legality onward threads it) and as a hook for a split threshold; the logic here only consults rich and legality; the batchable-axis filtering policy would otherwise provide is already baked into CellLegality::per_axis by analyze_legality.

Two sizing primitives (detail::home_depth_of, detail::cell_footprint), the forest linearization plus loop-identity pass (compute_dag_boulevard) and the interval-event sweep (peak_profile_sweep) that turns an eval forest into a PeakProfile. compute_dag_boulevard is on the ordered runtime path: it produces the RichSchedule the schedule builder, the cell table and the executor all consume; peak_profile_sweep is the analysis-only half.

Classes

Functions

Typedefs