Module run 

Run extraction + the transient lower_run view + the fewness gate.

Phase A PR-A2 of the “plan IS the graph” rebuild.

A run is the maximal straight-line op-sequence between two decision points — the future dispatch / CUDA-graph-capture unit (see ../docs/architecture/06-runtime.md §“Dispatch: runs, not single ops”). This module derives runs from the graph structure; it does not execute them (Phase C) and does not add an optimizer (Phase A3+). A run is a single-device contiguous chain with one entry and one exit; its members are NodeIds in topological order.

Run boundaries (a new run starts at a node when any hold):

• (a) graph entry — a node with no predecessor inside the reachable set (a source / root input of the walk).
• (b) reconverge — a node named as some Op::Branch’s reconverge_at (the post-merge region is a fresh run).
• (c) arm entry — a node whose sole predecessor is a Branch’s diverge point (the first node of each candidate route).
• (d) residency seam — the node’s Graph::target_backend differs from its sole predecessor’s, or the node is an Op::Copy / Op::Move device-transfer.
• (e) fan-in — a node with more than one predecessor inside the reachable set.

Consequently a run never spans a Branch boundary or a device change. A graph with zero Op::Branch nodes and a single residency extracts to exactly one run covering all reachable nodes — exactly today’s single-route graph.

Structs

Run

A maximal straight-line, single-device op-sequence between two decision points — the dispatch / command-buffer-capture unit.

Constants

FEWNESS_THRESHOLD

The fewness-gate threshold: branch points must be at most ~5% of reachable nodes. Deliberate-fork branching stays this sparse; per-op branching does not.

Functions

branch_density

Branch density: the share of reachable nodes that are decision points (Op::Branch nodes), over root.

branch_density_multi

Multi-root variant of branch_density.

branches_in_topo_order

The reachable Op::Branch decision points over roots, in topological order of their reconverge_at merge points — the order the runtime route picker (Picker 2) resolves them in, so that coupled upstream decisions are committed before a downstream branch is reached (06-runtime §“Resolution order matters when decisions are coupled”).

device_alternating_order

Device-overlap topological reorder of a run list (Step E Phase C, PR C3 — the auto-overlap pass). Returns a permutation of 0..runs.len() (indices into runs) that is a valid topological reordering — every run still appears after all the runs it depends on — chosen so independent cross-device sub-DAGs DISPATCH so they overlap: the longest compute chunk of each device is enqueued/recorded BEFORE the host-blocking cross-device drain that feeds the join.

effective_roots

The effective root set for a run/density walk: the caller’s roots plus every Op::Branch node participating in the reachable computation. A finalized Op::Branch is typically orphaned — nothing downstream reads it (the reconverge_at node reads arm 0 directly, per PR-A1’s runnability invariant), so it would never be found by a plain forward walk. We therefore scan the whole arena and seed any Branch whose reconverge_at (or any arm exit) is already reachable; seeding it pulls its candidate arms into the walk. Run to a fixpoint so a Branch reached only through another Branch’s arm is also covered.

extract_runs

Extract the runs of the graph reachable from root, in topological order of their entries.

extract_runs_multi

Multi-root variant of extract_runs — the reachable set is the union over roots (mirrors topo_order_multi) plus the arms of every reachable Op::Branch. A Branch’s non-arm-0 arms are read only by the Branch node itself (arm 0 is the runnability fallback the reconverge_at node reads directly, per PR-A1), so seeding the walk from the Branch nodes pulls every candidate route into the reachable set.

lower_picked_route

Route-aware lowering (Phase C PR-C1) — the generalization of lower_runs_arm0. The flat executable dispatch order that follows the chosen arm at each Op::Branch (per picked, defaulting to arm 0 for any branch the picker did not resolve) and skips every non-chosen arm’s run.

lower_picked_route_streaming

Streaming route-aware lowering (Step E Phase C, PR C1) — the incremental form of lower_picked_route. Instead of taking a fully-resolved PickedRoute up front, it walks the run partition in topological order and resolves each branch lazily, the first time the walk reaches one of its arm-entry runs, by calling resolve(branch). It emits only the chosen arm’s runs (skipping the non-chosen arms), exactly like lower_picked_route — but the arm decision happens at the frontier, not before the walk.

lower_run

The transient executable view of a single run: its ordered member NodeIds, ready to be recorded into a command buffer (Phase C).

lower_runs_arm0

The arm-0 single-route lowering (Phase A PR-A4, architect- approved temporary fix). The flat executable dispatch order that follows arm 0 through every Op::Branch — the pre-run, arm 0’s run, then the post-run — and skips every non-arm-0 arm’s run.

passes_fewness_gate

Whether the graph passes the fewness gate over root (branch density strictly below FEWNESS_THRESHOLD).

walk_picked_route_streaming

The callback core of the streaming lowering — the form the compiler thread drives so resolution and emission genuinely interleave (the thread compiles + dispatches each chosen run as the walk reaches it, rather than first materializing a flat order). resolve(branch) yields the chosen arm index at the frontier; emit(&[NodeId]) receives each kept run’s members in topological order. lower_picked_route_streaming is the Vec-collecting wrapper over this (used by the byte-identity test); the executor’s compiler thread passes an emit that compile_one’s + sends each node.

Type Aliases

PickedRoute

A resolved route through the multi-path graph: for each Op::Branch decision point (keyed by the Branch node’s NodeId) the arm index the runtime route picker (Picker 2) chose. Arm i is the branch’s inputs[i] (arm-0 = inputs[0] = the cost-vector winner).