# Execution pipeline

Connect lazy `Poly` graphs to the scheduler, memory planner, backend, and JIT capture/replay paths. Read [Engine overview](<https://ren-docs.pages.dev/engine/overview/index.md>) first if you need the shorter map.

flowchart LR A\["Lazy Poly graph"\] B\["Realization boundary"\] C\["Schedule, plan memory, lower"\] D\["Run ExecUnits"\] E\["Realized buffers"\] A --\> B --\> C --\> D --\> E

JIT wraps the same realization machinery with a capture path on cache miss and a replay path on cache hit:

flowchart LR A\["Call jitted function"\] B\["Realize input Polys"\] C{"Plan cached?"} D\["Capture:\<br/\>run function, record scheduled CALLs,\<br/\>build and store replay plan"\] E\["Replay:\<br/\>bind input buffers,\<br/\>run captured plan"\] F\["Return output structure"\] A --\> B --\> C C -- "miss" --\> D --\> F C -- "hit" --\> E --\> F

Eager realization schedules, plans, lowers, and runs the lazy graph each time a concrete value is needed. JIT capture uses that same realization machinery on a cache miss while recording scheduled `CALL`s; replay skips scheduling and lowering for the captured computation when the input specs match a captured plan.

## Lazy graph

`Poly` wraps a `Node`. `Poly` operations add nodes without launching backend kernels.

- `a + b`, `a - b`, and `a * b` create arithmetic nodes.
- `a.ntt()` and `a.intt()` create domain conversion nodes.
- `a.to_quotient_ring(ring)` and `a.lift_to_ring(ring)` create a `TO_RING` node, which may become either a real conversion or a buffer view.
- `a.rescale(moduli)` creates a `RESCALE` node.
- `a.rotate(k)` creates a high-level `ROTATE` node that is lowered later.
- `a.to(device)` creates a `COPY` node.

A `Node` has an `Op`, a `dtype`, zero or more sources in `src`, and optional operation metadata in `arg`. Nodes form a DAG, not a tree. If the same polynomial expression is reused, downstream nodes can point at the same producer node.

Ring semantics live on metadata nodes. `AS_RING` attaches a `RingSpec` and a domain to storage or computation: `Domain.COEFF` means coefficient representation, and `Domain.NTT` means NTT representation.

## Creation

Creating a public polynomial from coefficients stores the input coefficient limbs in a Python buffer, then converts them into the ring's Montgomery RNS basis with `TO_RNS`:

```text
coefficients
  -> packed u32 limb array
  -> BUFFER(device="python")
  -> TO_RNS(ring, limb_count)
  -> Poly
```

Random constructors such as `uniform()`, `uniform_on_interval()`, `ternary()`, and `sparse_ternary()` create lazy `RANDOM` nodes with ring metadata. Realization materializes the random polynomial. Constant constructors are different: `Poly.const()` creates a symbolic `CONST` node and attaches ring metadata. Constants stay allocation-free until a later pass needs to lower them into coefficient or NTT form.

## Realization

Realization turns lazy polynomial IR into concrete buffers. `realize()`, `tolist()`, `tobytes()`, serialization, decryption, and JIT capture all force realization.

During `ren.realize(*values)`, Ren collects Polys from the supplied values and gathers their requested output nodes into a single `SINK`:

```text
SINK(out0, out1, ...)
```

The single sink gives the scheduler one root that covers every output requested together. If two output polynomials use the same intermediate, scheduling can see that shared dependency in one graph.

The normal realization path is:

```text
ren.realize(*values)
  -> tree.collect(..., leaf=Poly)
  -> _schedule_and_lower(...)
       -> schedule(SINK(...))
       -> plan_memory(...)
       -> make_exec_units(...)
  -> run_exec_units(...)
```

After scheduling, Ren records a `becomes_map` from old lazy outputs to their new buffer-backed outputs. Ren updates existing `Poly` objects whose graphs overlap the realized computation so they point at realized `BUFFER` or `CONST` nodes.

## Scheduling

Scheduling turns a high-level polynomial DAG into a `LINEAR` sequence of executable `CALL` nodes. Ren applies this pass sequence:

```text
1. Simplify algebra, ring rules, constants, and copies
2. Lower high-level ring ops such as ROTATE
3. Inject NTT or INTT nodes for domain requirements
4. Simplify domain conversions
5. Parameterize the outer SINK as a CALL with explicit buffer bindings
6. Reuse or create its cached lowered graph, including output expressions
7. Decide materialization boundaries on a cache miss
8. Lower BUFFERIZE markers to storage views or ALLOC + STORE + AFTER
9. Lower automorphisms, ring rules, and constants
10. Indexify elementwise computation with GIDX, INDEX, LOAD, and STORE
11. Kernelize top-level stores into parameterized CALLs
12. Resolve the outer CALL with the current buffers and fresh writable storage
13. Order executable calls under LINEAR and resolve output bindings
```

The scheduler inserts representation changes based on operation requirements. `MUL` and `ROTATE` require NTT inputs, `RESCALE` requires coefficient-domain input, and some `TO_RING` conversions require coefficient-domain input. After insertion, domain simplification removes round trips such as `NTT(INTT(x))`.

Some expressions need materialized buffers. Ren marks materialization boundaries for outputs, conversion operations, copies, contiguous requests, and stores. The scheduler first represents a boundary as `BUFFERIZE(x)`. A storage view already satisfies that request; other values need `ALLOC`, `STORE`, and `AFTER`. `AFTER` keeps dependency ordering explicit without changing the value that flows through the graph.

Ren lowers eligible `TO_RING` operations to views. If the destination moduli are a contiguous subset of the source basis and the layout/domain constraints allow it, the scheduler creates a `BUFFER_VIEW` with an element offset. If a view feeds an elementwise compute chain, the scheduler can also fuse the view into indexed loads.

After indexing, each top-level `STORE` becomes a `CALL`. Its body uses positional `PARAM` nodes instead of concrete buffers and lives in `CALL.src[0]`; the remaining sources hold the buffers in parameter order. Copies use lightweight `COPY` bodies. Views remain buffer expressions in arguments and outputs throughout scheduling. They never become calls.

The scheduler uses the same parameterized cache for eager roots and `@ren.function` bodies. Each cached graph retains its output expressions and dependency edges. Ren binds inputs and fresh allocations together, expands nested calls, then orders the executable calls into the final `LINEAR` sequence.

## Memory planning

Before calls become executable units, Ren plans intermediate memory. The memory planner computes first and last use from the `LINEAR` call sequence. For optimizable intermediate buffers, it simulates a TLSF-style allocator and packs them into one arena per device.

The goal is to reuse storage for temporaries whose live ranges do not overlap. Ren preserves final outputs, already allocated buffers, explicit no-opt buffers, and the bases of preserved output views. Copy buffers also stay out of the arena to preserve transfer parallelism. Other intermediate views can share arena storage with their bases. The memory planner makes allocation decisions once from the schedule. Runtime execution reuses arena offsets instead of allocating and freeing each temporary.

## Backend lowering and execution

`make_exec_units()` lowers each `CALL` to an `ExecUnit`. Compute calls go through the selected backend: the Python backend interprets the lowered body with NumPy and Montgomery helpers, while the CUDA backend renders kernel code, compiles it, builds launch specs, and runs it on CUDA queues.

Copies lower to either device transfer or host-mediated copy depending on allocator support. Buffer views lower to validation-only exec units that bind a view to its base.

Execution follows a short loop:

```text
for each exec unit:
  allocate required buffers
  run the unit
  let Python refcounts release intermediates after their final use
```

## JIT capture and replay

`ren.jit` wraps a Python function whose arguments and outputs contain `Poly` objects. Inputs can be direct arguments or nested inside supported Python containers and records, including CKKS `Plaintext` and `Ciphertext` objects. See [nested values](<https://ren-docs.pages.dev/engine/jit/#nested-values>) for the traversal contract. Top-level scalar arguments are frozen into the captured plan; if they change on replay, Ren raises instead of running a stale branch.

On a cache miss, JIT realizes inputs, runs the user function under capture, and records scheduled `CALL`s as outputs are realized. It normalizes bindings, optionally prunes input-independent work, and replans captured intermediate memory. One rewrite binds inputs, outputs, and planned storage before lowering the replay calls into executable units and creating a backend graph runner if possible. Explicit `realize()` calls inside the body also record and execute their scheduled work. Polynomial host reads and random polynomial generation inside the body are rejected. On a cache hit, JIT passes current input and output bindings to the replay plan.

Eager lazy execution builds and schedules the graph on each realization. JIT pays that cost once per argument shape/spec and reuses the captured execution plan. See [`ren.jit` replay](<https://ren-docs.pages.dev/engine/jit/index.md>) for examples and failure modes.

## Source map

- [`ren/poly.py`](<https://github.com/fieldextension/ren-onboarding/blob/main/ren/poly.py>) for the user-facing polynomial API and realization entry point
- [`ren/ir/op.py`](<https://github.com/fieldextension/ren-onboarding/blob/main/ren/ir/op.py>) for the operation set
- [`ren/ir/node.py`](<https://github.com/fieldextension/ren-onboarding/blob/main/ren/ir/node.py>) for graph structure, metadata, constants, and formatting
- [`ren/engine/schedule.py`](<https://github.com/fieldextension/ren-onboarding/blob/main/ren/engine/schedule.py>) for the scheduling pass order
- [`ren/engine/rules/`](<https://github.com/fieldextension/ren-onboarding/tree/main/ren/engine/rules>) for the individual rewrite passes
- [`ren/engine/memory.py`](<https://github.com/fieldextension/ren-onboarding/blob/main/ren/engine/memory.py>) for arena planning
- [`ren/engine/realize.py`](<https://github.com/fieldextension/ren-onboarding/blob/main/ren/engine/realize.py>) for lowering scheduled items into executable units
- [`ren/engine/jit.py`](<https://github.com/fieldextension/ren-onboarding/blob/main/ren/engine/jit.py>) for capture and replay
- [`ren/backends/python/`](<https://github.com/fieldextension/ren-onboarding/tree/main/ren/backends/python>) and [`ren/backends/cuda/`](<https://github.com/fieldextension/ren-onboarding/tree/main/ren/backends/cuda>) for backend execution
