Skip to main content

schedule_instructions

Function schedule_instructions 

Source
pub fn schedule_instructions(stmts: &mut Vec<(String, Expr)>)
Expand description

Schedule assignment statements to maximise instruction-level parallelism (ILP).

Algorithm (Sethi-Ullman critical-path heuristic):

  1. Build a def-use dependency graph: for each statement (name, expr), record all prior statements whose results expr references (via Expr::Temp).
  2. Compute critical-path depth per statement via longest-path from leaves:
    • Statements with no temp-ref dependencies → depth 0.
    • Each dependent statement → 1 + max(deps' depths).
  3. Topological re-ordering: maintain a ready-queue of statements whose all dependencies have already been emitted. Among ready candidates, prefer those with the largest critical-path depth (i.e., the ones that unblock the longest remaining work) — this is the “greedy critical-path first” rule.
  4. Guaranteed correctness: no statement is emitted before all its deps are done.

The pass operates in-place on the assignment vector. It will not reorder statements that were placed in a topologically invalid order beforehand — call topological_sort_assignments first if needed. In practice, emit_body_from_symbolic calls both in sequence.