# Scheduling

Scheduling turns a high-level `Node` DAG into executable kernel work. The entry point is `schedule(SINK(...))`, and the pass sequence lives in `ren/engine/schedule.py`. Read [Engine overview](<https://ren-docs.pages.dev/engine/overview/index.md>) or [Execution pipeline](<https://ren-docs.pages.dev/engine/execution/index.md>) first if you want the wider realization path before the scheduler details.

## Pass shape

Ren runs these scheduler passes:

| Step | Purpose |
| --- | --- |
| Simplify | Algebra, ring rules, constants, and copies. |
| Lower high-level ops | Lower high-level ring ops such as `ROTATE`. |
| Prepare domains and functions | Insert required `NTT` or `INTT`, remove redundant conversions, and lower `FUNCTION` to `CALL`. |
| Parameterize the root | Replace concrete buffers with positional `PARAM` nodes under one outer `CALL`. |
| Reuse the schedule | Cache lowering by the parameterized `SINK` body and active rules. |
| Plan materialization | Choose nodes that need buffers. |
| Lower storage | Convert `BUFFERIZE(x)` into a storage view or `ALLOC`, `STORE`, and `AFTER`. |
| Lower ring ops | Enforce ring-specific reductions and conversions. |
| Lower constants | Give ring constants explicit coefficient or NTT semantics. |
| Indexify | Convert elementwise work into `GIDX`, `INDEX`, `LOAD`, `STORE`. |
| Kernelize | Parameterize top-level stores and wrap them in `CALL` nodes. |
| Bind scheduled calls | Expand nested schedules and bind current inputs and fresh intermediates. |
| Linearize | Order executable calls under `LINEAR`, then discard ordering edges from buffer bindings. |
| Build `becomes_map` | Map lazy outputs to their concrete output bindings. |

Each pass fixes representation decisions needed by later passes. Preparation resolves argument domains before preparing each function body and lowering it to a `CALL`. The same pass then places the function's resolved outputs in the domains its callers require. Materialization and lowering run only on a schedule-cache miss, then the outer `CALL` binds the current buffers and fresh outputs.

## Trace scheduler rewrites

`schedule(...)` accepts a trace callback. This example records a small summary of pass-level replacements.

Tracing records passes that actually run. A schedule-cache hit returns the cached lowering without replaying the original lowering events.

```python
from ren.engine.schedule import schedule
from ren.ir.node import Node
from ren.poly import Poly
from ren.ring import RingSpec


ring = RingSpec(n=8, moduli=(17, 97))

x = Poly([1, 2, 3, 4, 0, 0, 0, 0], ring)
y = Poly([4, 3, 2, 1, 0, 0, 0, 0], ring)

expr = (x + y) * 2
root = Node.sink(expr.node)

events: list[tuple[str | None, str, str]] = []


def trace(pass_name: str | None, before: Node, after: Node) -> None:
    if before is after:
        return
    events.append((pass_name, before.op.name, after.op.name))


linear, becomes_map = schedule(root, trace=trace)

print("initial root:", root.op.name)
print("scheduled root:", linear.op.name)
print("materialized outputs:", [node.base.op.name for node in becomes_map.values()])
print("rewrite events:", len(events))
for pass_name, before, after in events[:8]:
    print(f"{pass_name}: {before} -> {after}")
```

```
initial root: SINK
scheduled root: LINEAR
materialized outputs: ['BUFFER']
rewrite events: 82
prepare: ADD -> NTT
prepare: AS_RING -> NTT
prepare: NTT -> AS_RING
prepare: MUL -> MUL
prepare: MUL -> MUL
prepare: SINK -> SINK
callify: SINK -> CALL
bufferize: MUL -> BUFFERIZE
```

The example schedules `(x + y) * 2`. The scalar `2` enters as a ring constant. Ren treats this as a normal `MUL`, so domain injection gives both operands NTT-domain semantics before constant lowering turns `2` into its NTT broadcast form. The `bufferize: MUL -> BUFFERIZE` row marks the multiplication's output for storage.

The trace stays compact by design. To debug a scheduling issue, filter by pass name first, then inspect the graph before and after that pass.

## Materialization

Ren materializes values that need buffer identity. Common boundaries are:

- final outputs;
- conversion operations;
- explicit `contiguous()` requests;
- stores and copies;
- views over realized sources that must remain addressable.

The `AFTER` node is a dependency edge. It keeps ordering explicit while letting the value continue to behave like the buffer it wraps.

## Kernelization

Kernelization replaces buffer references in a store body with positional `PARAM` nodes. The `CALL` keeps the lowered body in `src[0]` and its buffer bindings in the remaining sources.

Compute kernels use this shape:

```text
CALL(
  SINK(STORE(INDEX(PARAM(0), GIDX), value)),
  buffers...
)
```

Copies use the same `CALL` shape with lightweight non-compute bodies. Views remain buffer expressions; explicit copies of views still write their destination buffers. All executable calls are collected in execution order under `LINEAR`.

The outer eager graph and each `@ren.function` body use the same parameterized schedule cache. It retains the lowered graph with its output expressions and dependency edges. The scheduler binds inputs and fresh allocations for each invocation, expands nested calls, then builds one `LINEAR` sequence.

## Scheduler terms

| Term | Meaning |
| --- | --- |
| `SINK` | Single root node used to schedule one or more requested outputs together. |
| `BUFFERIZE` | Temporary marker saying a value needs buffer identity. |
| `ALLOC` | Temporary storage request, bound to a fresh buffer for each invocation. |
| `STORE` | Store a computed value into a buffer. |
| `AFTER` | Dependency edge that preserves ordering while returning the wrapped value. |
| `GIDX` | Global element index used after elementwise work is indexified. |
| `INDEX` | Read a logical element from a node at an index. |
| `LOAD` | Load from a buffer slot during indexed lowering. |
| `PARAM` | Positional buffer parameter in a function or lowered call body. |
| `FUNCTION` | Unscheduled invocation of a reusable high-level body. |
| `CALL` | Executable body plus concrete buffers in parameter order. |
| `LINEAR` | Ordered sequence of executable calls. |

## Files to read

- [`ren/engine/schedule.py`](<https://github.com/fieldextension/ren-onboarding/blob/main/ren/engine/schedule.py>): pass order, function expansion, and call extraction.
- [`ren/engine/rules/callify.py`](<https://github.com/fieldextension/ren-onboarding/blob/main/ren/engine/rules/callify.py>): function preparation rules, root parameterization, and call binding.
- [`ren/engine/rules/indexing.py`](<https://github.com/fieldextension/ren-onboarding/blob/main/ren/engine/rules/indexing.py>): materialization planning, view planning, and index lowering.
- [`ren/engine/rules/domain.py`](<https://github.com/fieldextension/ren-onboarding/blob/main/ren/engine/rules/domain.py>): domain requirements and injected conversions.
- [`ren/engine/rules/kernelize.py`](<https://github.com/fieldextension/ren-onboarding/blob/main/ren/engine/rules/kernelize.py>): parameterization and call construction.
- [`ren/kernel.py`](<https://github.com/fieldextension/ren-onboarding/blob/main/ren/kernel.py>): compute-kernel metadata.
- [Runtime](<https://ren-docs.pages.dev/engine/runtime/index.md>) for the next step after scheduling.
