Module Ir.Low_level

How a loop's iterations map to hardware; see docs/proposals/axis-types-for-loops.md. Serial is an ordinary for-loop. Grid / Workgroup bind the loop index to a GPU grid / workgroup (block, threadgroup) hardware index instead of looping; Workgroup_reduce is a Workgroup axis participating in a workgroup-cooperative reduction (see the contract below). Unrolled is emitted as the repeated body with substituted constants. Vectorized renders eligible bodies as explicit SIMD code — elementwise statements via vector extensions / packed loads (gh-ocannl-164 / gh-ocannl-463), a single recognized accumulation as independent accumulator chains with a horizontal reduce at exit on CPU backends (gh-ocannl-468) — and everything else as a serial loop annotated with the backend's vectorization pragmas when it provides them (a plain, un-annotated serial loop for accumulating bodies, whose loop-carried dependency the pragmas would deny) — like the hardware kinds, the annotating pass asserts iteration independence or, for a recognized accumulation, licenses reassociating it. Hardware slots are positional: among a kernel's loops of one kind, the innermost binds .x, then .y, .z. Annotated loops must have from_ = 0 and iterations with no cross-iteration dependencies (Vectorized accumulations again excepted). Workgroup_reduce is the labelled exception; its body must either stage its communication explicitly through workgroup-shared nodes and barriers (rendered by binding the index like Workgroup), or be a single accumulation statement acc = op(acc, contrib) over an associative-commutative op with the accumulator's indices free of the loop index — the renderer then owns the communication: warp/simdgroup shuffles on GPU backends (gh-ocannl-462), the plain serial loop on CPU backends. Like Vectorized, the annotation licenses reassociating the (floating-point) reduction.

Loop keyword used by the human-readable printers: plain "for" for Serial, "for@<axis>" otherwise.

Which pass minted a Local_scope (gh-ocannl-687). The construct has two producers, and a consumer that walks the IR looking for schedulable structure means only one of them:

• Inlined_computation -- virtualization's inline of a virtual node's computation at a read site, and the rewrites that carry those scopes along. The loops inside such a body are the inlined node's own iteration space, re-instantiated per use site; no Schedule op has ever targeted them.
• Schedule_minted -- the accumulator localization built by Schedule's materializing Unroll and by Partition (gh-ocannl-639), and by C_syntax.try_localize_serial_reduce: a running value for a MATERIALIZED cell, whose body holds the very per-step / per-segment loops Schedule.rewrite_loop retargets.

This is the fact Autotune.collect_loops needs: it enumerates loops inside Schedule_minted scopes only, so the action menu does not spend its per-unit budget proposing splits, swaps, unrolls and vectorize retypes for inlined interpolation and reduction loops that no schedule op has ever been able to reach.

Deliberately NOT the mechanism behind the scope-target contract input_scope_ids serves: that one asks whether a scope was in the program a given optimize call was HANDED, which is a per-call fact -- a virtualizer-minted scope handed back into a second optimize still carries Inlined_computation and still is not that call's to retract -- and hand-built IR has no honest way to spell "not mine".

Cases: t -- code, scalar_t -- single number at some precision.

The argument precision is preserved in heterogeneous precision operation arguments, and is ignored (overridden) in homogeneous precision operations.

gh-563: the one canonical rendering of lowered code, shared by both digest consumers — analysis_cache_stats' cache (keyed inside optimize) and Schedule_cache.canonicalize (schedule replay across sessions).

Generate loops that iterate only over the padding margins of a tensor. For dimensions with padding, generates separate loops for left margin, middle (recursing), and right margin. The middle region continues recursing to find padding in other dimensions.

Whether the tree carries a read-modify-write accumulation: some Set (resp. Set_local) reads its own target — a loop-carried dependency through memory when the written cell does not vary with an enclosing loop. Conservative: Local_scope contents count as reading anything, and Tile_mma and (gh-466) Set_dynamic accumulate by construction. Used by the autotune menu and by codegen fallbacks that must not assert iteration independence (e.g. vectorization pragmas) over an accumulating body (gh-ocannl-468).

Whether the scalar reads the node anywhere (gh-ocannl-639) — certifies that an accumulation's contribution is free of the accumulator's node, which licenses holding the accumulator out of memory across the reduction.

The statement-body counterpart of scalar_touches_tn: any read or write of the node.

The accumulation-update statement shape tn[idcs] = op(tn[idcs], contrib) (or its FMA form) over an associative-commutative op, with contrib free of tn; returns (op, contrib). The single source of truth shared by C_syntax's widened renderings and Schedule.Unroll ~materialize:true's scope-form unrolling (gh-ocannl-639), so "what counts as an accumulation" cannot drift between the schedule transform and the emission.

Retarget an accum_update_parts-shaped update's read of tn[idcs] to the scope local id. Raises on any other shape.

Whether the scalar reads the scope local id, descending into nested scope bodies — the scope-local counterpart of scalar_touches_tn. Distinguishes a scope-opening init (a Set_local whose value is free of the local) from a self-referential update.

The reduction operator of a scope-local update in either spelling: the plain accum_local_update_parts form, or virtualization's guarded-read form Where (index-only cond, update, Get_local id) (possibly nested per guard condition). The residency classifier's recognizer (gh-ocannl-663): the guarded form is a reduction for accumulator-width purposes but does NOT decompose into an unguarded (op, contrib), so it is deliberately not part of accum_local_update_parts or of scope_updates_reduce_op's hoist license.

The reduce-shaped update of a scope LOCAL, local = op(local, contrib) (or its FMA form) with contrib free of the local — subst_accum_read's output shape; returns (op, contrib). The SIMD reduction rendering uses it to fold vector chains into a widened accumulator's scope local (gh-ocannl-639), and peel_accum_nest's scope-form validation is built on it.

Whether the tree holds a SELF-RECURRENCE: some Set whose value reads the very cell it writes (gh-ocannl-733). This is what makes the localizing peel a live question at a level, and it is the predicate the peel census gates on. Narrower than has_accumulation in two ways, both deliberate: the recurrence is on the CELL rather than on the node, and a Local_scope counts only when its body actually reads that cell — has_accumulation must count every scope conservatively, being the predicate that decides whether iteration independence may be asserted, and censusing on it recorded every non-reduction virtualized scope as a declined reduction site.

What peel_accum_nest decided about one If it peeled through (gh-ocannl-733). Two shapes that render identically can earn different verdicts here, which is the whole point of reporting them: a test pinning the rendered FORM cannot tell "the guard was confined to the peeled levels" from "the guard mentioned an enclosing lane and the cell separated it".

Why peel_accum_nest stopped, when it did (gh-ocannl-733).

What one peel_accum_nest call decided, beyond whether it succeeded (gh-ocannl-733). Reported to the optional ~report callback on every call, success or refusal; C_syntax turns it into the per-routine peel census, so that a test can pin which DECISION produced a kernel and not only which form was rendered.

Peel a single-statement reduction nest down to its accumulation base (gh-ocannl-639). Levels are Serial/Unrolled/Vectorized loops, loops extra_level vouches for (codegen passes a predicate accepting hardware-annotated reduction loops its backend serializes — the schedule mints pass nothing, since wrapping a hardware-annotated loop in a scope at transform time would break the schedule on backends that do bind the hardware dimension), and pure-index-guarded Ifs (the gh-490 If (i < s) shape and its constant-bound sibling — data-dependent guards stay opaque), each containing nothing else; the base is a raw accum_update_parts-shaped update (`Update) or the scope form a previous rewrite minted (`Scope: the scope id and the update statements after the opening init, validated to carry ONE reduction operator — mixed-operator sequences are not reductions and keep their per-iteration narrowing), with the accumulated cell invariant across the peeled levels (free_of seeds the invariance check with the caller's own loop). rebuild re-wraps a replacement base statement in the peeled levels. The ONE definition shared by C_syntax's localizing serial fallback and the schedule mints, so transform and emission cannot drift.

A DEAD level (to_ < from_) is never peeled, and that refusal is load-bearing rather than tidiness: the body of a dead loop performs no accesses at all — the routine-interface walk propagates liveness as live && to_ >= from_, so a node reached only under one is absent from the parameters and need not be allocated — while every form this peel licenses reads and writes the accumulated cell OUTSIDE the levels, unconditionally. Peeling a dead level would invent accesses the program does not make, possibly on an identifier the interface never declared.

Whether a GUARD may join the peeled levels is Affine.peel_guard's and Affine.separates's answer, not this function's (gh-ocannl-722) — rebuild keeps the guard around the accumulating update only, so the localized form loads and stores outside it, and the engine is where the two hazards that creates are stated: a guard mentioning no peeled symbol is fixed for the whole nest, so the hoist invents both accesses, and one mentioning an enclosing loop symbol selects among that level's iterations, so lanes the guard excludes would write their unchanged local back over the accumulating lane's result. The second is admitted when the accumulated cell SEPARATES those enclosing symbols — each instance then owning a distinct cell makes the invented load/store pair private and idempotent (gh-ocannl-721) — which is why the cell reaches the decision and the peel defers it to the base.

loop_bounds is loop_bounds of the enclosing program, and supplies both the classification and the ranges: a guard symbol in it that is not peeled is an enclosing level's index, while one outside it is a static index parameter or a runtime extent and is harmless — which is what keeps gh-490's runtime-extent guard (Assignments.extent_guard's i < s, whose bound is a static symbol rather than a constant) peelable. Required rather than defaulted, and derived from the program rather than certified by the caller, so that no call site can forget it: the mints of Schedule need it as much as codegen does, since a refused mint there turns segment seams into narrowing points instead of merely declining an optimization.

report, when given, is called EXACTLY ONCE per call with the peel_report of what was decided — how many levels were peeled, which verdict each peeled guard earned, and the refusal where there was one (gh-ocannl-733). The result alone cannot answer that: two nests differing only in whether the accumulated cell mentions the enclosing index peel a different number of levels under a different guard verdict and render the same localized kernel. Codegen passes a reporter that accumulates the per-routine peel census; the schedule mints pass none.

Arrays of length 3 (.x, .y, .z); all-1s for all-Serial code.

All hardware-annotated loops in pre-order, with their positional slots.

Per-slot maximum extents over the kernel's annotated loops; grid.(2) is the product of the per-slot maxima of grid slots >= 2 (the .z fold, see the section comment).

The binding arithmetic of a Grid loop at slot >= 2 under the .z fold: (stride, cap) such that the loop binds (z / stride) % cap — stride the product of the per-slot maxima of grid slots in [2, slot), cap = None (no modulo) when no higher grid slot exists in the kernel. (1, None) — the bare .z register — for the common single-slot-2 case.

gh-ocannl-584: the predicate form of validate_scope_bodies — None when every Local_scope body in llc is pure, else a description of the first violation. hoist_cross_statement_cse uses it to guard its own precondition (it is the one pass that can move an effect out of a scope, so an impure body reaching it would be laundered past the codegen gate); tests use it to assert that a body was left where it was.

gh-ocannl-584: enforces the scope-purity contract stated at scalar_t.Local_scope — a scope body's only effect is on the locals it owns (its own scope id, plus ids Declare_locald lexically within it). Raises Invalid_argument on anything else inside a Local_scope body at any nesting depth: a tensor-node write (Set, Set_from_vec, Set_dynamic, Zero_out, Tile_mma), a Set_local of a sibling or enclosing scope's local, a Workgroup_barrier, or a Staged_compilation. Applied at both ends of the pipeline — optimize on the way in (before a pass can launder a violation out of any body) and C_syntax.compile_proc on the way out. The raw analysis entry points analyze_proc / specialize_proc deliberately do not validate, being the probes that must stay conservative on IR they may not trust. The optimization pipeline satisfies the contract by construction.

Backend-independent well-formedness of hardware annotations (axis-types proposal §2); a no-op for all-Serial code. Raises Invalid_argument on structural violations: nonzero from_, more than 3 slots per kind, annotated loops inside Local_scope bodies, barriers under divergent extents or If guards, writes to materialized nodes not nested under annotated loops covering every active (non-unit) hardware dimension — launch dimensions are global to the kernel, so an uncovered dimension executes the write once per hardware index — and whole-node Zero_out of materialized nodes in multi-threaded kernels (nesting never distributes it). Cannot prove iteration independence — that is the annotating pass's obligation.

Internal backend-facing variant of validate_parallel; transports a validation Invalid_argument as a typed Schedule_outcome.cause.Illegal_schedule.

Wraps bodies of annotated loops whose extent is below their slot's launch dimension in If (index < extent) guards, for the kinds the backend binds in hardware.

A shallow-copy fork of the lineage state (computations and placements tables): the copy sees everything decided so far; its later mutations are invisible to the original and to sibling copies. Backend compile forks the incoming context's optimize_ctx through this, so sibling candidate compiles from one frontier are hermetic.

Records an On_device decision for each node this lineage has not already resolved otherwise — the "materialize this node" move of the placement lattice. Nodes already resolved to Virtual / Local / Effectively_constant keep their resolution: decisions are final within a lineage.

Context.decide_materialized is the context-level form (it forks the lineage first) and is what ordinary Assignments callers want. This raw form serves the paths holding an optimize_ctx directly: the analyze-only entry points, and hand-built optimize calls in tests — for which no context-level form can work, since the ?prelowered seam replaces the context's lineage state with the optimized record's own optimize_ctx.

Granularity of the XOR remap applied to a swizzled node's minor axis (gh-ocannl-481 item 3, D1). Both flavors are per-row bijections of the minor axis, so the IR-level semantics are identical; they differ in the unit the XOR permutes and therefore in which access pattern they de-conflict.

gh-555: one searchable inlining decision dimension of a compile — a node whose placement the default policy decided, together with the flip a search can try and the recompute-cost bound of the virtual placement (reduction extent × per-cell read multiplicity × transitive inline fan-in). `Materialize flips a node the policy left virtual (via Context.decide_materialized); `Inline flips a node materialized by the heuristic caps (never by legality or observability), via Context.decide_inline. An `Inline flip's legality is settled only when the virtualizer replays: a rejected flip reproduces the materialized placement.

gh-487: a software-pipelined (double-buffered) staged tile — codegen allocates pt_depth rotating copies of the tile and renders every access with a buffer-selection term rotated by the pt_rotor loop counter: reads select copy rotor mod depth, writes copy (rotor + 1) mod depth (the schedule emits the loads one iteration ahead), and writes outside the rotor loop (the prologue load) select copy 0. The IR keeps the tile's single-copy dims and indices — the rotation is a physical-layout choice like swizzle_kind, invisible to IR-level semantics — so the pipelined rendering is bitwise identical to the unpipelined one.

gh-ocannl-498: the backend-agnostic byte footprint implied by an optimized routine's placement vector. The allocator-side scorer lives in Backends.score_footprint.

Decision-independent analysis of a lowered routine (gh-555 step 1): the structural per-node facts and the lazily-materialized affine access metrics — everything the optimization pipeline consumes that does not depend on the lineage's placement decisions.

Compute the analysis once for a routine. optimize is analyze_proc followed by specialize_proc (plus the pretty-printing callbacks).

The decision-dependent tail of the pipeline: placement decisions (decide_placements under the given lineage's placements and inline preferences), virtualization, cleanup, simplification and CSE. Cheap to replay per candidate over one shared analysis (gh-555): sibling calls with hermetic optimize_ctx forks (see copy_optimize_ctx) produce hermetic optimized results — the traced store is record-copied per call.

The gh-ocannl-805 seam assertion run after virtualization and before cleanup: every tensor-buffer read (Get / Get_dynamic) in a statement cleanup will keep, including reads inside a kept inlined Local_scope body, must name a node with a placement decision. Reads in a virtual candidate's setter are excluded because cleanup drops the whole setter without visiting its right-hand side. Exposed so hand-built-IR tests can inject the otherwise-unreachable negative control directly at this boundary.

gh-560: (hits, misses) of the process-global analysis cache consulted by optimize: sibling candidate compiles of one routine share one analyze_proc result — keyed by a canonical digest of the raw lowered code and the static indices (tensor nodes and static symbols by identity, loop binders and local-scope ids alpha-renamed) — and replay only specialize_proc. Cumulative counters, for tests and diagnostics.

Drops the analysis cache's entries (the stats persist). Entries retain their routines' lowered code, hence their tensor nodes; the cache clears itself before accessibility snapshots (Tnode.print_accessible_headers) and callers that tear down a session (Tensor.unsafe_reinitialize) clear it to release the nodes promptly. Never needed for correctness: entries keyed by stale nodes cannot alias fresh ones (Tnode.uid is never reused).

reads_scope_before_set id body returns true if id is read (via Get_local) before the first definitely-executed Set_local id in body. Use this at code-generation time to decide whether a Local_scope or Declare_local declaration needs a zero initializer.

Top-down algebraic simplification with interval-driven comparison folding (in particular, it erases If guards whose conditions the loop extents prove). The interval environment is narrowed by every enclosing If condition that is a conjunction of integer-affine index comparisons (gh-ocannl-566), so a guard the statement guard proves folds too — what is simplified under a condition is valid only where that condition holds. Called internally by optimize; exposed for Schedule.apply, whose transforms construct guards after the pipeline's simplify already ran (docs/proposals/schedule-ir-optops.md §2), and for testing. Pure and idempotent.

gh-343: rewrites the narrow one-hot embedding pattern -- an Add reduction over a loop variable k whose body selects an embedding-table row via k == index_expr (a logical one-hot) -- into a guarded dynamic gather (Get_dynamic) that reads the table row at index_expr directly, with an in-range guard returning 0 out of [0, vocab_size) to preserve the one-hot semantics. The guard is constructed generically and interval analysis (docs/proposals/interval-analysis-scalar-t.md) erases the conjuncts it can prove -- from the index precision's machine range, loop extents seeded from static_indices, and settled per-tensor bounds (Tnode.bounds_state).

gh-466: also rewrites the transposed one-hot pattern -- the embedding-table gradient for k in [0, V): tn[.., k, ..] += (k == index_expr) * g where the loop variable indexes the written tensor itself -- into a guarded dynamic scatter-accumulate (Set_dynamic): if in_range(index_expr): tn[.., index_expr, ..] += g, dropping the O(V) per-position work (llm.c's deterministic encoder backward, docs/research/llmc-lessons.md B5). The enclosing position loops keep their original serial order and the schedule analyses never parallelize over a dynamically-written node, preserving determinism without atomics.

Unmatched or unsupported reductions are left unchanged. Called internally by optimize between simplify_llc and eliminate_common_subexpressions; exposed for testing.

Eliminates common subexpressions within each statement's scalar expression tree. Replaces duplicate Local_scope nodes (structurally identical modulo scope_id) with Get_local references to the first occurrence. Called internally by optimize; exposed for testing.

Hoists shared Local_scope computations from sibling statements to the enclosing scope. When two or more sibling statements share an alpha-equivalent Local_scope node, the computation is extracted as a Declare_local + body preceding the first user, and all occurrences are replaced with Get_local.

Inputs are the materialized read-only and read-before-write (within the code) non-constant non-merge nodes. They are inputs in a broad sense, as they could be recurrent nodes or parameters. Outputs are all the materialized nodes written-to by the code. The last returned component is the input merge node, if used in the code. Reads entering the code only through a cross-routine inlined computation count: the traced store is completed from the final optimized code (gh-610).

All For_loop bindings within the code (loop symbols are unique within a routine), with inclusive iteration bounds — the box environment for Affine queries, and what peel_accum_nest classifies its guard symbols against: one absent from this list is bound outside every loop (a static index parameter, a runtime extent) and cannot select among any level's iterations.

The value-dependence symbols of statement-level scalar scope-locals, whole-code: per scope id, the union of the symbols its statement-level assignments depend on, transitively through Get_local references (such a local may be assigned in one statement and read in another). Assignments inside Local_scope bodies are not recorded — a scope id is re-instantiated at every use site with per-site loop symbols, and scope-internal flow is covered lexically by the value scans. Consumed by the setter value scans so a value routed through a scope-local is not laundered of its symbols (gh-494 per-thread value-variance).

Loop symbols a scalar expression's value depends on syntactically — index symbols of reads, embedded indices, dynamic-index sub-expressions — resolving scope-locals through locals (from scope_value_syms).

gh-494 waypoint 1: the routine's tensor-node accesses as explicit affine relations (Affine.access), extracted from (typically optimized) code, in program order (a statement's right-hand-side reads precede its write; Local_scope bodies are descended into at their use site; Tile_mma is traversed through its scalar fallback). Not represented: scope-locals, merge-buffer reads, and opaque Staged_compilation — callers needing exhaustiveness must check for the latter separately.

gh-ocannl-489 liveness-based buffer aliasing: per-tnode access span over the final (post-schedule, post-fission) code of a routine, as a closed interval of positions; the input is the routine's kernels in execution order (a singleton when not fissioned). With stmt_serial:true every top-level statement gets its own position — sound only for backends where consecutive top-level statements of one compiled procedure are fully synchronized (the C backends); with stmt_serial:false all statements of a segment share one position, since GPU kernels have no grid-wide synchronization between top-level statements. Returns None when the code contains Staged_compilation (opaque accesses: no aliasing plan can be trusted).

gh-ocannl-489 follow-up: sinks each top-level Zero_out to just before the first later top-level statement accessing the zeroed node (Train.grad_update's up-front zero_grads block otherwise starts every gradient's live span at that block, nesting the backprop chain's intervals and defeating the arena planner). Sound: a Zero_out commutes with statements not accessing the node; it never crosses such an access, a Staged_compilation, or a Workgroup_barrier. Apply to whole-routine code BEFORE scheduling/fission.

Adheres more to the C syntax, outputs implicit type casts.

Adheres to the %cd syntax.