Exo 2: Growing a Scheduling Language

Programmers speed up code by writing a schedule — a recipe of transformations that rewrites a program into a faster but equivalent one — and scheduling languages like Halide make this safe, but they ship a fixed menu of transformations, so the moment you need one they lack, you fall off a cliff into hand-written assembly or hacking the compiler; this work from MIT builds Exo 2, a scheduling language designed to grow, where users compose a small set of trusted, correctness-preserving primitives into their own scheduling libraries in ordinary user code, held together by a new referencing mechanism called Cursors that keeps a stable handle on the code even as it is transformed, cutting scheduling code tenfold while matching hand-tuned libraries like MKL and OpenBLAS.

Why this problem is worth solving

To see why the fixed menu is the crux, it helps to understand what a scheduling language actually is.

The reason a fixed set of operations is a fundamental limit, not a temporary gap, is that the right line keeps moving.

What people did before, and where it broke

• Halide-style fixed operations with nominal references. A well-chosen menu of built-in scheduling operations, each loop named uniquely by the buffer it writes. Where it broke. The menu cannot grow without changing the compiler, and global names cannot express relative references like “the second-outermost loop” or “three stages back.”
• Method-chaining scheduling (Halide, TVM, original Exo). Scheduling operators as methods on a program object, chained together. Where it broke. User-written helpers do not have the same shape as built-in operators, so they are second-class and cannot be composed as freely as the primitives themselves.
• Rewrite-strategy languages (ELEVATE). Let users define traversal strategies and rewrite rules, with relative references. Where it broke. It allows only a single reference at a time, and those references are one-time — invalidated after each action — so they are inflexible and break as the code changes.
• Pattern matching to point at code. Identify the loop or statement to transform by matching a structural pattern. Where it broke. A pattern that matched before a transformation may match nothing, or something different, afterward (a loop ceases to exist once tiled), making patterns brittle and hard to encapsulate in reusable operations.
• Drop to C, assembly, or hack the compiler. When the language falls short, leave it. Where it broke. This forfeits every safety guarantee the language provided and does not scale across the configuration cross-product of a real library.
• The gap. Every approach fixed the set of transformations, the referencing scheme, and the automation boundary at design time, leaving no safe way to extend the language for an unforeseen optimization or accelerator. What was missing was a scheduling language built to grow — where users add new operations, and even new referencing schemes, from within user code — which is exactly what real performance engineering needs.

How Exo 2 works

The idea

Grow the language from trusted primitives, instead of shipping a fixed menu. The move that unlocks everything is to stop trying to guess the perfect set of scheduling operations and instead provide a small set of fine-grained, composable primitives — each verified to preserve the program’s meaning — from which users assemble their own operations and whole libraries, in ordinary user code, without touching the compiler. Because composition can build any abstraction on top of the primitives (though never finer control than the primitives themselves), when the built-ins fall short the engineer extends the language rather than abandoning it, and a uniform procedure-to-procedure type makes a user-written tiler a first-class operation indistinguishable from a built-in. Handing users a small set of safe, composable building blocks and letting them build the automation they need on top, so the system extends to cases its designers never anticipated without changes to its core, is the same philosophy the compute-in-memory compiler work covered elsewhere on this site follows, exposing a lean set of primitives that new targets and optimizations are built upon rather than baked in.

Point at code by relative context, and keep the handle stable as the code changes. The subtle hard problem in any scheduling language is reference: how does a schedule say which loop to transform, and what happens to that reference after the transformation? Global names cannot express “the second-outermost loop,” and a structural pattern breaks the instant the code it matched is reshaped. Exo 2’s Cursors are relative references — context-dependent, like a noun phrase rather than a proper name — and each one carries two coordinates: which version of the program it points into, and where in that program’s syntax tree it sits. When a transformation produces a new version, Exo 2 forwards the cursor to the corresponding place, so a reference stays meaningful across an entire multi-step schedule and inside reusable library functions. Separating the two coordinates that a naive reference conflates — the temporal question of which version and the spatial question of where — so each can be tracked on its own terms is the same discipline the memory-resizing work covered elsewhere on this site follows, prising apart two concerns that had been tangled together so neither contaminates the other.

Make safety compositional, so any user library is correct by construction. Letting users write their own transformations sounds dangerous — a wrong rewrite silently corrupts the program. Exo 2 defuses this by verifying each primitive to preserve functional equivalence, so that any composition of primitives is equivalence-preserving too, and a user can build a sprawling scheduling library and trust that it never changes what the program computes, only how fast. A transformation that would break equivalence simply raises an error, which the schedule can catch and route around. Building a large guarantee out of small, individually-verified, composable steps, so that correctness holds by construction no matter how the pieces are assembled, is the same foundation the quantum-program verification work covered elsewhere on this site rests on, deriving the soundness of the whole from the soundness of each elementary reasoning step.

Following a reusable vectorizer through Exo 2

A user-defined operation and a built-in are interchangeable because they share one procedure-to-procedure type.

Why it works

• Composing fine-grained primitives lets users build any transformation they need. A fixed menu of coarse operations cannot anticipate every optimization an engineer wants → but a small set of low-level primitives composes into arbitrarily rich scheduling operations in user code → so when the built-ins fall short, the user extends the language instead of dropping to assembly.
• A uniform functional type makes user operations indistinguishable from built-ins. If user code had a different shape than the compiler’s operations, the two could not interoperate → but giving every primitive and every user function the same procedure-to-procedure type lets them compose freely → so a user-written tiler is a first-class scheduling operation, reusable and combinable like any built-in.
• Relative, stable references survive the transformations they guide. Global names cannot express “the second-outermost loop” and pattern matches break the moment the code changes → but a Cursor points relatively and is forwarded to the new program after each edit → so a reference stays meaningful across a whole multi-step schedule and inside reusable library functions.
• Inspection lets automation adapt to the actual code. Without seeing the object program, a schedule cannot make a decision like unrolling only the small loops or using a fused instruction if present → but exposing the syntax tree through cursors lets library code query bounds, precisions, and structure → so users build analyses the compiler never provided and specialize their schedules accordingly.
• Verified primitives make user libraries safe by construction. Letting users write transformations risks producing wrong code → but because each primitive is checked to preserve the program’s meaning, any composition of them is equivalence-preserving too → so a user can build a complex scheduling library and trust it never changes what the program computes.

What it costs (trade-offs and scope)

• It automates less than it looks; you still write the schedules. Exo 2 gives the building blocks to write reusable scheduling libraries, not an autotuner — performance still depends entirely on the optimization strategy the engineer encodes, and the tenfold code reduction is about amortizing across a configuration cross-product, not eliminating effort.
• Ambiguous cursor forwarding is heuristic and can surprise. When a cursor points into the very part of the code an action rewrites, forwarding falls back to per-primitive heuristics that the authors admit may behave unintuitively, especially deep inside composed library calls; the practical remedy is to print the cursor and see where it landed.
• It inherits the limits of the underlying object language. Exo’s core language lacks some features — value-dependent control, for instance — so certain kernels (two BLAS level-1 operations, some matrix formats) simply cannot be expressed.
• The order-of-magnitude claim is an estimate. The comparison counts the primitive rewrites a user would have written in the previous system, which the authors note may slightly overstate the gap versus a best-effort hand schedule.
• Building a good library is still expert work. The trusted primitives are the safe base, but choosing which optimizations to apply and in what order — the phase-ordering problem is explicit — remains deep performance-engineering knowledge.
• Safety is per-transform equivalence, not a performance guarantee. The compiler guarantees each primitive preserves the result, so a schedule always computes the right answer, but a poor strategy compiles to correct-but-slow code.
• Evaluated on CPUs and one accelerator, mostly on linear algebra. The results cover x86 vector kernels (BLAS, GEMM), a couple of image filters, and the Gemmini accelerator; broader domains and GPUs are not shown.

The evaluation

Check yourself

Sources

The paper is “Exo 2: Growing a Scheduling Language” by Yuka Ikarashi, Kevin Qian, Samir Droubi, Alex Reinking, Gilbert Louis Bernstein, and Jonathan Ragan-Kelley, published at ASPLOS 2025, DOI 10.1145/3669940.3707218. The authors are at MIT CSAIL, Adobe, and the University of Washington; Exo 2 is open-source under the MIT license.

This explainer is written from the full text. Everything above comes from the paper’s own sections: the introduction arguing that user-schedulable languages should be designed to grow, and the failures of fixed automation-control boundaries (Halide’s prefetching, vector instruction selection, and lack of tensor-accelerator support); the framing of scheduling languages through action, inspection, and reference; the action section on the 46 composable, equivalence-preserving primitives, their uniform procedure-to-procedure type versus method chaining, reusable schedule functions, control flow with try/except fallback, and higher-order combinators; the inspection section on type reflection through cursors and building bounds inference externally; the reference section’s taxonomy of nominal-versus-relative, single-versus-multiple, and stable-versus-one-time references and the fixed, linear, and branching scheduling-time models, and the Cursors mechanism (multiple, stable, relative references) with its version-plus-path implementation and forwarding by decomposition into atomic AST edits (insert, delete, replace, move, wrap); the library-building sections (a parameterized vectorize with FMA-aware staging, Gemmini configuration hoisting, the BLAS level-1 and level-2 and GEMM libraries covering 24, 50, and micro-kernel variants, and reproducing ELEVATE and Halide referencing within user code); and the evaluation showing an order-of-magnitude reduction in scheduling code across more than 80 kernels with performance matching MKL, OpenBLAS, BLIS, and Halide on AVX2, AVX512, and Gemmini.