A minimal compiler for a Futhark-like programming language that generates SPIR-V and WGSL code for GPU shaders.

• Functional syntax for shader programming
• Hindley-Milner type inference with polymorphic types
• Higher-order functions (map, reduce, zip, etc.)
• Pattern matching
• SPIR-V and WGSL code generation for Vulkan/WebGPU shaders
• Vertex, fragment, and compute shader support
• Vector and matrix types optimized for GPU operations
• Array operations with size tracking
• Loop constructs

The project is organized as a Rust workspace:

• wyn-core/ - Compiler library (lexer, parser, type checker, TLC, EGIR mid-end, SSA, SPIR-V/WGSL backends). Includes an in-crate generic SSA framework at ssa::framework (blocks, values, instructions, terminators) used only for codegen.
• wyn/ - Command-line executable
• wyn-analyzer/ - Language server (in development)
• viz/ - Visualization tool for rendering SPIR-V shaders
• prelude/ - Standard library functions written in Wyn

The compiler uses a multi-stage pipeline with typestate-driven phases. Each stage consumes self and returns the next stage, enforcing valid ordering at compile time.

The mid-end is an acyclic e-graph: a sea of hash-consed pure nodes plus a skeleton CFG of effectful instructions. Purity is blacklisted, not whitelisted — only Alloca / Load / Store stay in the skeleton; everything else (calls, intrinsics, storage views, projections, indexing) is hash-consed in the pure sea. Named user calls are classified from the complete TLC call graph and enter EGIR in the pure sea only when their definitions are proven effect-free.

Most optimizations fall out of the data structure without dedicated passes:

• GVN — pure-node interning deduplicates by structural equality.
• Constant folding — the interner consults a folder before inserting, so folds compose.
• DCE — elaboration is demand-driven from skeleton roots; unreached pure nodes are never emitted.
• CSE along the domtree — emitted pure nodes are scoped to dominator regions; siblings never share.
• LICM — pure nodes float to the outermost loop where all their operands are available.
• Partial inlining — a bounded policy fixpoint uses the generic EGIR inliner for profitable explicit-loop calls with both invariant and varying arguments, after which ordinary LICM hoists invariant-only subgraphs.
• Branch folding + redundant-phi elimination — the skeleton CFG is rewritten before elaboration.

The table above is one valid topological sort of the constraints below (optimize_tlc_for_test in wyn-core/src/lib.rs and the CLI pipeline in wyn/src/main.rs must stay in sync with it). A ≺ B means A runs before B. Each notes how it's enforced; when you move a pass, check it here.

• validate_ownership ≺ partial_eval — source-level consumption must be checked while the call boundary carrying the *T contract still exists. Enforced by: partial_eval is defined only on TlcOwnershipValidated.
• monomorphize ≺ defunctionalize — monomorphization specializes the still-higher-order program; defunctionalization then removes function-typed parameters and gives EGIR concrete callable references and captures. Enforced by: the TLC typestate chain.
• defunctionalize ≺ fold_generated_lambdas — fold inlines the _w_lambda_* defs that defunc generates. Enforced by: the TLC typestate chain.
• monomorphize ≺ force_inline_soac_helpers — force-inline's free-type-var guard skips any helper still carrying an unresolved element-type Variable, so helpers must be concrete first. Enforced by: the TLC typestate chain.
• rep_specialize ≺ force_inline_soac_helpers — makes filter-result helpers representation-concrete (Abstract → Bounded/View) so the guard admits them. Enforced by: the TLC typestate chain.
• force_inline_soac_helpers ≺ soac_anf — every SOAC helper is inlined so EGIR receives explicit intra-def producer/consumer edges rather than needing cross-call summaries. Enforced by: the TLC typestate chain.
• soac_anf ≺ float_runtime_index_nested_producers ≺ defunctionalize ≺ to_egraph — nested producers become explicit let-bound demand edges before callables are lowered to the reference/capture ABI consumed by EGIR. Enforced by: the TLC typestate chain.
• apply_ownership ≺ to_egraph — TLC records source-level uniqueness but does not decide physical reuse. EGIR resolves UniqueInput only after output realization and semantic optimization. Enforced by: the TLC/EGIR typestate chain and a physical-expansion assertion rejecting unresolved candidates.

The EGIR order is also load-bearing:

• realize_outputs ≺ segment — output routes must become authoritative writes before raw SOACs are wrapped as segmented operations.
• segment ≺ optimize — fusion legality depends on explicit domains, semantic operation IDs, effects, and dependency edges.
• optimize ≺ allocate — residency and uniqueness resolution use the final fused graph's liveness and demands.
• allocate ≺ plan — target scheduling consumes the final semantic residency manifest, then transactionally adds recipe-owned work buffers before choosing bindings, dispatches, and physical entries.
• plan ≺ lower_to_ssa — SOAC expansion accepts only the validated physical program built from the kernel plan.

Every dependency above is enforced by the top-level typestate chain; each typestate exposes only its single next pass.

SSA is intentionally minimal: all mid-end machinery (effect tokens, canonicalization, verification, generic transform passes) lives in EGIR. A generic CFG-with-block-params representation is provided in ssa::framework; the concrete instantiation lives in ssa::types.

Key properties:

• CFG with basic blocks and block parameters (not phi nodes).
• No effect tokens at the SSA layer — instruction order is fixed by elaboration.
• Function parameters and block parameters are distinct kinds of values.

Parallel semantics live in EGIR. TLC performs source-level normalization and uniqueness reasoning but emits no per-entry strategy record. EGIR reifies every reachable SOAC, retains it through semantic optimization and logical allocation, and destroys it only at the target-aware lower-to-SSA boundary. That terminal operation produces SSA kernels, the dependency/resource schedule, and the descriptor as one result. Its initial portable scheduler implements:

• Map — lane-indexed scalar kernel: one thread per element, guarded by a bounds check. The serial-loop builder is still used for non-entry maps (intermediate map inside a function body) which legitimately want sequential execution per thread.
• Reduce — two-phase: phase 1 chunks the input per thread and writes a partial; phase 2 is a synthesized combine entry over the partials.
• Redomap — same two-phase shape as Reduce, with the redomap's combiner in phase 2.
• Scan — three-phase Blelloch-style: phase 1 chunks the scan per-thread + writes per-block sums; phase 2 sequentially scans the per-block sums into per-block offsets; phase 3 applies the per-element fold. When the input is marked consumable (*[]T), phases 1 and 3 write back in place and the pipeline descriptor skips the auto-output slot.

TLC has six SoacOp variants; the table also lists Redomap, which is a fused semantic EGIR form rather than a TLC constructor. "Serial" = correct sequential lowering through soac_expand. "Consuming-input DPS" = TLC records a uniqueness candidate and EGIR residency verifies post-fusion death before choosing in-place reuse instead of a fresh output buffer. "Parallel" = EGIR-side parallelization fires on a compute-entry SOAC matching the strategy's shape.

Notes:

• TLC ownership emits only UniqueInput. After fusion, egir::residency::select_in_place_destinations promotes it to InputBuffer only when the final semantic graph proves the compatible input dead; otherwise it becomes Fresh (or output routing has already selected an OutputView). soac_expand turns an accepted in-place destination into array_with_inplace operations.
• Phase 3 of parallel scan applies op(off, elem), not op(elem, off): egir::parallelize synthesizes a swap-args wrapper EgirFunc \(a, b) -> op(b, a) alongside the phase entries, and phase 3's Map routes through the wrapper. Correct for non-commutative associative combiners (string concat, matmul).

filter is shape-changing: it returns the existential ?k. [k]T, opened to a runtime length k ≤ n at the consumer. Two lowerings, by input size:

• Static input ([N]T, capacity known): a function-local Bounded {buffer:[N]T, len:i32} struct — soac_expand::build_filter_loop.
• Runtime input (a storage view / entry param, length only known at dispatch): the serial loop compacts kept elements into a reserved scratch storage buffer (capacity n, host-sized LikeInput of the input) and yields a runtime-length view over it (StorageView(scratch)[0, count]). The surviving count is the view's len operand — a value, not a type-level size — so length and reduce consume it like any view. The scratch binding is represented in EGIR's logical resource manifest and published by terminal scheduling alongside gather/shared-array resources. A runtime filter reached in a standalone function (one inlining didn't fold into a compute entry) errors — only an entry owns a descriptor set to host the scratch buffer; from_tlc::convert_function guards this.
• filter as a compute output: realize_outputs::retarget_filter_output makes the filter compact directly into the entry's output buffer and writes the surviving count to a paired u32 length cell (Fixed{4}, repurposed from the scratch binding) the host reads back alongside the data.

Parallelization status. Semantic EGIR folds non-escaping filters into masked reduction steps; length becomes one shared count reduction, so no compacted intermediate is required. SOAC helpers are force-inlined before EGIR conversion, making the same rewrite available when source code factors the filter and consumer into different functions.

An escaping SegFilter uses the parallel map → flag scan → scatter algorithm (if flags[i] { out[offsets[i]-1] = xs[i] }) and publishes the final count through the paired length cell. Ordered general-purpose SegHist/scatter lowering remains serial; the filter scheduler owns its guarded compaction scatter as part of the specialized filter phase model.

The unimplemented cells above have a few hard dependencies between them, plus some softer reuse opportunities. Anything not on this list is independent.

• Scatter serial is in place ((xs..) -> (index, value) envelope with map-producer fusion, lowered to a sequential indexed-store loop against the bound storage view). The OOB-guarded indexed-store builder it produces is the natural starting point for ReduceByIndex serial, which adds a read-combine-write step on top.
• Surface parsing. reduce_by_index already has a producer at tlc::mod::transform_soac_reduce_by_index; scatter is parsed as an ordinary function call (no dedicated SoacOp surface form — the envelope lambda is what marks it as a SOAC).
• Parallel ReduceByIndex → atomic intrinsics. The catalog has no atomicAdd/atomicMin/etc. today; adding them is a prerequisite for parallel histograms. Serial ReduceByIndex doesn't need them.
• Parallel Scatter → no hard prerequisite, but the duplicate- index semantics ("last write wins" sequentially) become racy in parallel. Either accept the race (matches Futhark's documented behavior) or gate on atomic-store availability.

A view array ([]T) is a window into a storage buffer: a runtime {offset, len} pair plus a static descriptor (set, binding) — Vulkan can't pick a descriptor by a runtime value, so the binding must be a compile-time constant at every consumer. Wyn makes the binding a property of the type: the Array type's trailing buffer/region slot (always the last type argument) holds Buffer(set, binding). Thus a rank-one view has four type arguments, [elem, ArrayVariantView, dim_0, buffer]; the runtime {offset, len} value is separate from this static type-level buffer slot.

• Born at entry params. pin_entry_buffers (the first TLC pass) computes each storage entry-param's binding (auto-allocated set 0, 0..N, or an explicit #[storage(set, binding)]) and substitutes the param's buffer variable → Buffer(set, binding) throughout the entry.
• Flows by unification. A view is buffer-polymorphic everywhere else (∀b. View[…, b]), so a slice, a let, a function argument, or a SOAC capture inherits its buffer the same way it inherits its element type — no side-channel, no manual threading. if c then xs else ys over two different buffers fails to unify, which is the correct "can't pick a descriptor at runtime" error.
• Specialized by monomorphize. Because the buffer is an ordinary type parameter, monomorphize specializes a view function per buffer exactly as it does per element type — f(xs) and f(ys) over two buffers become two monomorphs. (This is what let the dedicated buffer_specialize pass be deleted.)
• Read by the backends from the type. A view is a runtime value (SPIR-V: a {offset,len} struct; WGSL: a vec2<u32>). ViewIndex recovers the backing buffer via array_view_buffer(value_type) → get_or_assign_buffer_id (SPIR-V) / storage_name (WGSL). No ValueId → binding side-map. The lone exception is workgroup-shared views, whose _wg_<id> isn't a descriptor and rides a small side map.

The defunctionalize() typestate transition composes three sequential passes that share a closure-info side table. Every callable position in the IR resolves through a single lookup that says either "direct call" or "closure (code address + captures)".

1. closure_convert — lifts every standalone lambda to a top-level def. Free variables become trailing parameters on the lifted def. Let-bound lambdas are substituted away so no callable aliases survive. Transitive captures are pulled in.

2. hof_specialize — clones each user-defined higher-order function for every concrete callable that flows in, eliminating function-typed parameters. After this pass, every reachable top-level def has zero function-typed parameters.

3. closure_calls_lower — final global tree walk that threads captures into call sites. Idempotent with the pre-threading hof_specialize already did inside cloned bodies.

Lambdas embedded in SOAC operators are lifted the same way, but the SOAC keeps a (lambda, captures) payload so the loop body and its closed-over values stay together for later expansion.

Three verifier-checked invariants guard the phase boundaries: no standalone lambdas survive outside SOAC envelopes, no reachable def has a function-typed parameter, and every call is fully arity-matched to a non-callable target.

Throughout TLC and EGIR, types are polytype::Type<TypeName>. The underlying carrier is Type::Constructed(TypeName, Vec<Type>) — the Vec<Type> (the "args") means different things per variant. This schema is the canonical mapping. Helpers in wyn-core/src/types/mod.rs (array_elem, array_size, array_variant, strip_unique, extract_function_signature) centralize the position queries so passes don't pattern-match on args indices directly.

-- Render a full-screen triangle.

#[vertex]
entry vertex_main(#[builtin(vertex_index)] vid: i32) #[builtin(position)] vec4f32 =
  let verts = [@[-1.0, -1.0, 0.0, 1.0],
               @[ 3.0, -1.0, 0.0, 1.0],
               @[-1.0,  3.0, 0.0, 1.0]] in
  verts[vid]

#[fragment]
entry fragment_main(#[builtin(position)] pos: vec4f32) #[target(screen)] vec4f32 =
  @[0.529, 0.808, 0.922, 1.0]  -- Sky blue

# Compile to SPIR-V
cargo run --bin wyn -- compile input.wyn -o output.spv

# Compile to WGSL
cargo run --bin wyn -- compile input.wyn -o output.wgsl -t wgsl

# Type check without generating code
cargo run --bin wyn -- check input.wyn

# Output intermediate representations
cargo run --bin wyn -- compile input.wyn --output-init-ssa out.ssa   # Initial SSA
cargo run --bin wyn -- compile input.wyn --output-annotated out.ann  # Annotated source

# Visualize a SPIR-V shader
cd viz && cargo run vf ../shader.spv --vertex vertex_main --fragment fragment_main

cargo build --release
cargo test

Use cargo test --workspace for the full Rust suite. All SPIR-V testfiles in testfiles/ compile and validate (bash scripts/validate_testfiles.sh); the WGSL subset also validates (bash scripts/validate_testfiles.sh --wgsl — a handful skip because they depend on linked SPIR-V helpers).

• Primitives: i32, u32, f32, bool
• Arrays: [N]T for fixed size, []T for inferred size
• Vectors: vec2f32, vec3f32, vec4f32 (SPIR-V types)
• Matrices: mat2f32, mat3f32, mat4f32
• Tuples: (T1, T2, ...)
• Functions: T1 -> T2

-- Top-level definitions
def add(x: i32, y: i32) i32 = x + y
def first(xs: []i32) i32 = xs[0]

-- Shader entry points (one entry-point keyword per stage)
#[vertex]
entry vs_main(#[builtin(vertex_index)] id: i32) #[builtin(position)] vec4f32 = ...

#[fragment]
entry fs_main(#[varying(0)] color: vec3f32) #[target(screen)] vec4f32 = ...

#[compute]
entry sum_array(#[size_hint(1024)] data: []f32) f32 =
  reduce(|a: f32, b: f32| a + b, 0.0, data)

-- Lambdas
|x: i32| x + 1
|x: i32, y: i32| x + y

-- Loops (the supported looping primitive)
loop (acc, i) = (0, 0) while i < n do (acc + arr[i], i + 1)

-- Higher-order functions
map(|x: i32| x * 2, arr)
reduce(|a: i32, b: i32| a + b, 0, arr)

def identity(x) = x
-- Inferred: ∀a. a -> a

def zip_arrays(xs, ys) = zip(xs, ys)
-- Inferred: ∀n t1 t2. [n]t1 -> [n]t2 -> [n](t1, t2)

• Module system covers the common path (open, qualified access, multi-file imports — see testfiles/open_module_demo.wyn); some advanced features remain unimplemented.
• match expressions work for literals, wildcards, and sum-type constructors (testfiles/match_*.wyn, testfiles/sum_demo.wyn); guards and nested patterns are pending.

These are deliberate and not on a fix-it list:

• No recursion. Use loop or higher-order functions. Aligns with Futhark and GPU-targeted execution.

• nom — Parser combinators
• polytype — Hindley-Milner type system
• rspirv — SPIR-V builder

For complete language details, see SPECIFICATION.md.