Module dag_schedule 

Bottom-up scheduling of a dependency DAG with explicit value edges and shared materialization tokens.

Hard dependencies constrain order. Value dependencies are a subset of those edges and additionally describe liveness: scheduling a user backward makes the producer value live, while scheduling the producer kills it. A ready node with the smallest live-value delta is selected first. This is the conventional register-pressure list-scheduling model without attaching target-specific widths to source IR values. A materialization token is used by an arbitrary set of nodes rather than being defined by one DAG node. It models cached source expressions whose producer is whichever use gets scheduled first.

For N nodes, E hard edges, V value edges, and I node/token incidences, scheduling costs O((N + E + V + I) log N) time and O(N + E + V + I) space. A value or token changes the contribution to ready-node priorities at most twice, so each incidence is revisited only a constant number of times.

Structs

MappedGraphRows

Borrow adjacency rows from a larger graph and expose only nodes mapped into the current local DAG.

MappedNodeRows

Borrow rows indexed by a larger graph through a local-to-external node map.

Enums

DagScheduleError

Functions

schedule_min_live_values

Return a deterministic forward order for one DAG.

schedule_min_live_values_and_tokens

Return a deterministic forward order while also minimizing shared materialization-token pressure.

schedule_min_live_values_and_tokens_with_mapped_rows

Schedule a local DAG while borrowing dependency, user, and token rows from a larger graph.