Dynamic runtime sequences via standalone TXN encoding + EmitC C++ generation

[hunhoffe]

Let an aie.runtime_sequence be compiled once and run at many problem sizes. Instead of baking fixed sizes into a static TXN binary, emit the control program as dependency-free C++ that assembles the TXN binary at run time from scalar arguments. One xclbin serves many shapes (e.g. a GEMM with runtime M/K/N, or a passthrough with runtime length).

This is a fresh, incrementally-landable rebuild superseding branch dynamic-runtime-sequences-ssa (PR #3168), salvaging its good parts (TXN encoder, BD-word encoder, AIEX→EmitC conversion) as clean, individually reviewable PRs.

Goals

• Standalone, dependency-free TXN encoding library that owns the word format and is static_assert-pinned to the existing binary emitter so the two can't drift.
• AIEX→EmitC conversion + C++ TXN target emitting a generate_txn_sequence(...) function taking runtime scalars as arguments.
• npu control ops carry operands as SSA values (not attributes) so runtime scalars flow end to end.
• DMA BD lowering accepting runtime-valued sizes/strides/offsets, byte-identical to the static path for constant inputs.
• Correctness regime proving dynamic ≡ static, plus hardware-verified passthrough and GEMM on NPU1/NPU2.

Non-goals

• Runtime legalization/tiling of illegal access patterns (illegal-wrap splitting, >4-D unrolling, runtime alignment). The dynamic path assumes runtime values are already hardware-legal; it warns and guards rather than miscompiling. See "Legalization strategy".
• Porting airrt's static legalization into mlir-aie — orthogonal, broadly useful, tracked separately (see "Related effort"). This milestone depends only on the hardware bounds (known constants).
• Python frontend ergonomics beyond what's needed to drive/test the compiler path.
• Non-shim engines in the first increment — shim NOC is the MVP, core tiles are out of scope.

Legalization strategy: constrain the dynamic domain

airrt's mature legalization is constant-dependent (it inspects concrete sizes to pick tiling factors and unroll loops) so it can't run on runtime values. Analysis shows this isn't a blocker: the dims that are genuinely runtime-valued already stay within hardware limits, while patterns that need legalization come from static structure and can be legalized at compile time as today.

So: static structure is legalized at compile time (existing lowering; airrt port tracked separately); runtime values are allowed only on dims within hardware bounds (per-dim wrap ≤ {64,1024,1024,1024} after scaling, stride ≤ 2²⁰, ≤ 4 dims, inner alignment to address-gen granularity); and the path emits a compile-time warning when a bound can't be statically verified, plus a runtime guard where cheap.

Correctness criteria ("done")

• Static ≡ dynamic: the dynamic C++ builder invoked with constant args produces a byte-identical TXN stream to the static emitter. (Must be checked in compiled C++ — aie-translate can't substitute SSA i32 args at translate time.)
• All shared opcodes static_assert-pinned between header and binary emitter.
• FileCheck coverage per supported op (and static-vs-dynamic BD lowering for DMA).
• Dynamic passthrough + GEMM run correctly on NPU1 and NPU2.
• No supported op silently miscompiles an out-of-range runtime value — guarded or rejected.

---

PR sequence

Each PR is independently reviewable and landable, ordered to keep the tree green. Grouped into three phases: Phase 0 makes the existing static infrastructure correct under control flow (prerequisites that the prior branch skipped — its allocators silently mis-handle scf); Phase 1 builds the TXN/EmitC foundation; Phase 2 adds the dynamic capability and control flow on top.

Phase 0 — Correctness prerequisites (control-flow-safe static infrastructure)

0a. Control-flow-aware BD-ID / lock allocation via SSA liveness. Today three allocators(AIEAssignRuntimeSequenceBDIDs, AIEAssignLockIDs, AIEAssignBufferDescriptorIDs) walk the sequence in program order and assume straight-line code. AIEAssignRuntimeSequenceBDIDs.cpp:140 says so outright: "if in the future we support branching/jumping… a proper liveness analysis will become necessary." Under scf.for/scf.if a BD or lock whose live-range crosses a loop back-edge or differs between if arms can be assigned an overlapping ID with no diagnostic → silent data corruption. (The existing dynamic GEMM only works because its ping-pong keeps every live-range inside one iteration — unverified luck, not correctness.)

• Key enabler: a DMA task is already an SSA value — dma_configure_task defines an Index result; dma_start_task/dma_await_task/dma_free_task consume it. So BD-ID liveness is SSA value liveness, directly computable by upstream mlir/Analysis/Liveness.h (region/CFG-aware, so scf works for free). The current allocators are an ad-hoc program-order approximation of what mlir::Liveness already computes correctly.
• Refactor, don't rewrite ×3: BdIdGenerator (the pool/free-list) is already shared between the core and runtime-sequence BD allocators; only the traversal differs. Factor a single CF-aware liveness/traversal layer over the existing generator and use it from all three sites. (Note: mlir-air has no reusable liveness to borrow — it unrolls everything to constants — so the reuse target is upstream MLIR, not air.)
• Task-completion-token (TCT) balance is the same class of problem and is in scope here. A queue push issues exactly one TCT regardless of repeat_count (the token bit is on the push command, AIEDMATasksToNPU.cpp:107); a dma_await_task lowers to one npu.sync that waits on a channel region, with no token-count field. So a loop that pushes N times but awaits once outside the loop silently under-waits and reads incomplete data — a control-flow-dependent imbalance that program-order reasoning cannot catch. The liveness layer must therefore verify push/await (token produce/consume) balance across the CFG, not only BD-ID/lock live-ranges.
• Acceptance: BD/lock IDs correct for straight-line, scf.for, scf.if, and nested cases; a live-range that genuinely exceeds the hardware pool is rejected with a clear diagnostic (never a silent overlap); a push/await token imbalance across control flow is rejected with a clear diagnostic (never a silent under-wait); existing static tests unchanged.
• [aiecc] Make scf->cf lowering runtime-sequence-aware #3243
• [dyn-seq P0a] Unroll-first BD-ID allocation for runtime sequences #3226
• [aiex] Reject deadlocking task-completion-token imbalances in runtime sequences #3254

Phase 1 — TXN / EmitC foundation

1. Standalone TXN encoding library + opcode pinning. Dependency-free header with txn_init, txn_prepend_header, txn_append_* (write32, maskwrite32, sync, blockwrite, address_patch, loadpdi, preempt). Refactor AIETargetNPU.cpp onto it; static_assert all shared opcodes. Existing TXN tests unchanged (proves byte-neutral). [dyn-seq P1.1] Extract TXN instruction encoding into a standalone header #3224
2. SSA-operand npu scalar ops + migration. write32/maskwrite32/sync/address_patch/rtp_writetake SSA operands; attribute forms removed; constant operands fold identically; all users migrated; breaking-change note. [dyn-seq P1.2] Carry npu scalar op fields as SSA operands #3225 [dyn-seq] Convert aie.dma_bd sizes/strides/offset/len to SSA operands (DynamicIndexList) #3306
3. AIEX→EmitC conversion + C++ TXN target (scalar + blockwrite ops). Handles write32, maskwrite32, blockwrite, sync, address_patch, end, and the get_global feeding blockwrite. Generated C++ includes the PR 1 header. New aie-translate target. Unsupported ops emitOpError (never silent). FileCheck per op. [dyn-seq P1.3] AIEX→EmitC conversion + C++ TXN target  #3256
4. Static-vs-dynamic equivalence harness. Compiles static + runtime versions into two TUs, asserts byte-identical TXN for matching values; ≥2 distinct 4-D DMA patterns + direct/derived rtp_write; documented recipe to add a size. [dyn-seq P1.4] Static-vs-dynamic TXN equivalence harness #3289

Phase 2 — Dynamic capability + control flow

5. Dynamic BD-word encoder (shim NOC), shared with static path. Computes d0/d1/d2/iter size+stride, repeat_count, buffer_length with correct masks/shifts, size-gated strides, element-width/addr-gen rescaling. Shared word layout → byte-identical for constants; only runtime fields become write32 overrides. Compile-time warning + runtime guard on bounds. Restrictions enforced with diagnostics (shim NOC only, innermost stride == 1, all-or-nothing dynamic sizes/strides, pad_dimensions incompatible). A runtime-valued memref.subview (the memref must currently trace to a block arg through static subview offsets/sizes/strides, AIEDmaToNpu.cpp:621-626) is rejected with a clean diagnostic, not a crash. FileCheck for valid + invalid cases. [dyn-seq P5] Dynamic BD-word encoder for dma_memcpy_nd #3293
6. Dynamic repeat_count + blockwrite-fold interaction. Runtime outer-dim repeat_count; defined, tested behavior when dynamic sizes prevent blockwrite folding (larger per-register write32 stream). (Open: may fold into PR 5.)
7. Static control flow via unroll (binary path) + the CF correctness oracle. scf.for/scf.if with constant bounds in a runtime sequence are fully unrolled to a flat op list and lowered down the existing binary TXN path. The binary path rejects non-constant-bound control flow with a clean diagnostic (never crashes, never silently drops a loop). Establishes the oracle the next PR relies on: a constant-bound sequence lowered two ways (unroll→binary vs. scf→EmitC fed the same constants) must produce byte-identical TXN, checked via the PR 4 harness. FileCheck for the unrolled lowering and for the reject diagnostic. Prior art (mlir-air, copy the recipe down): unrollSCFFors / unrollAffineFors (AIRRtToNpuPass.cpp:2147 / :2106) — constant-bound loopUnrollFull + post-unroll walk that renumbers per-op metadata (the BD-ID/symbol analogue), and scf.forall→scf.for normalization via forallToForLoop (:1434) which must precede unrolling. Required acceptance criterion (known silent-failure trap): after unrolling, fold affine.apply/arith ops whose operands became constants — induction vars unroll to constants but affine.apply(constant) does not auto-fold, and downstream constant reads then silently fall back to 0 (see AIRRtToNpuPass.cpp:1456-1465). Test that an unrolled loop carrying an induction-derived offset lowers to the correct (non-zero) value.
8. Dynamic control flow in runtime sequences — integration + robustness. No prior art — this is novel. mlir-air only ever emits a flat static binary; it has no runtime control program, so nothing here can be borrowed (its loop handling is constant-bound loopUnrollFull only). scf.for (runtime bounds), scf.if (runtime condition), and arbitrary nesting (loop-in-loop, if-in-loop) survive through AIEX→EmitC into real C++ for/if via upstream convert-scf-to-emitc. This is the integration point of SSA-operand ops + EmitC + the dynamic BD encoder, so it is where all three are proven together. Acceptance criteria, each tested:
   • SSA remapping across the body clone: iter-args, scf.yield values, externally-defined values used inside, in-loop values used after. Non-arith.constant external operands are rejected with a diagnostic (today's cloneExternalConstants limitation) — test both accepted and rejected.
   • Device-relative resolution of AIEX ops nested in scf at depth ≥ 2 (lockstep clone/resolve walk).
   • blockwrite fusion behaves correctly inside loop bodies (fuses when valid, does not fuse across iteration boundaries).
   • Dynamic BD inside a runtime-bounded loop (a dma_memcpy_nd with runtime sizes inside an scf.for with runtime trip count) — the stacked target case (tiled dynamic GEMM).
   • Equivalence oracle from PR 7 extended to cover loops/conditionals with constant bounds.
9. End-to-end on hardware (shim NOC). Dynamic passthrough (runtime length) and dynamic GEMM (runtime M/K/N, including a runtime-loop-tiled variant) compile once, run at multiple shapes on NPU1+NPU2, results verified; driven through the high-level flow (xclbin + generated C++ TXN, no static insts); lit gated on hardware.
   • Multi-column in tested scope. The await/sync lowering currently hardcodes columnNum = rowNum = 1 (AIEDMATasksToNPU.cpp:177-178), so a multi-column design emits N separate (correct) 1×1 syncs rather than one wide sync — functionally correct, not collapsed. Add a dynamic design spanning >1 column to the hardware matrix to confirm correctness (the dynamic path has no multi-column coverage today); collapsing into wide syncs is an optional later optimization, not required here.
10. Trace under dynamic sizes — constraint + clean rejection. Trace with arg_idx = -1 ("append the trace buffer after the last tensor") computes its DDR offset from the static memref shape (memrefType.getNumElements() * elemBytes, AIEInsertTraceFlows.cpp:165-166) and a compile-time bufferSize (:150). With a runtime-sized output buffer (e.g. C[M×N]) that offset is wrong and the trace silently lands at the wrong DDR location, corrupting trace or output. (The branch's on-hardware trace verification only ever exercised static-size passthrough.) Fix: support trace via an explicit, separate trace argument (its own buffer, not appended) whose offset does not depend on a runtime-sized tensor; and reject arg_idx = -1 + runtime-sized buffers with a clear diagnostic rather than miscompiling. FileCheck for the rejection; hardware check of an explicit trace buffer on a dynamic design.

Coverage-gap PRs (parallelizable after PR 3, one scoped PR each, FileCheck + equivalence): extend EmitC to push_queue, preempt, load_pdi, create_scratchpad/update_from_scratchpad, control_packet, dma_wait, writebd. (Open: confirm which are needed vs. deferrable for target workloads.)

---

Related effort (separate milestone)

Port airrt's static BD legalization into mlir-aie — tileIllegalWrapDim, canonicalizeWrapAndStrideList, and alignment helpers (getDmaInnerElementAlignment, findLargestAlignedFactor, isContiguousRowMajorOrRepeated). Mature, broadly useful for lowering static patterns to legal BDs; benefits the whole compiler independent of this work. Because mlir-aie is strictly below mlir-air, it's a one-way port down (mlir-air must never become a dependency). This milestone depends only on the hardware bounds those helpers encode, not the helpers themselves.

[jgmelber]

@hunhoffe this looks like a great plan. It has evolved much since my initial naive stab...

[erwei-xilinx]

The analysis on AIRRt makes sense today. The goal of the airrt-to-npu pass in mlir-air is essentially to satisfy today's mlir-aie runtime sequence being fully static. The pass attempts to digest every SSA value into constants via (tiling, for NPU BD optimization) unrolling and canonicalization.

[hunhoffe]

@jgmelber I forgot some things so now it's even more involved, but hopefully I've articulated the pitfalls well

[thomthehound]

I'm just checking that I'm understanding this correctly, but the idea is to turn aie.runtime_sequence from a statically flattened configuration blob into a compiled, host-side control program that can construct TXNs on the fly from invocation-time scalars?

If that is so... I like this idea, and I like it a whole lot. I've been wanting something like this for a while. The ambition is a bit staggering, though. It sounds like this may eventually become one unified, parametric, scheduling model, where the existing static lowering is mostly just a specialization.

That actually brings me to my first comment/concern: overhead. The current static method doesn't have to think; it just has to do. But if it is built on top of more general machinery, cycles can get burned needlessly. As long as "byte-identical" means "literally output the same thing as today without a control program/middleman recreating it", then you have that covered. But for the dynamic side, I'm not sure it is going to end up being as simple as SSA use-liveness. I think Phase 0 is already showing that there is a bit more to it than that.

Single-digit microseconds and nobody will know the difference, but if reconfiguration starts taking dozens, or hundreds, then it becomes a "robbing Peter to pay Paul" problem (at least for one of the workloads I have in mind). On GPU, a UAV barrier for memory access reconfigure is almost always sub 10 microseconds as far as I've measured on Strix (usually more like 2-6). That would be nice to see with this in terms of switch-over times. But, given the CPU overhead, I think anything under ~75 us for a full invocation would be fine-ish (but more akin to a small GPU dispatch boundary, during which work is getting done).

Also, from a user-program perspective, I think actually making use of this in most cases is probably going to require XRT fences, because polling will just tank performance. We have those on Windows, but we'll have to bug Soren for a fresher SDK build to pick up the usability fixes he made in that area a few months ago. I think there is probably a ton of latency-hiding potential to be had with that as well, depending how clever the control layer gets, because you can async NPU work from CPU setup.

Second, I think it is probably going to have to be documented from the start exactly what this can and cannot do. Obviously workers, tile placements, the lock/ObjectFIFO topology, and core kernels are not going to be realistically touchable by something like this. But that still leaves offsets, strides, transfer extents, repeat/loop behavior, and conditional behavior as much more flexible targets than they were before. I think you were implicitly saying all that, but I had to really think through the implications before it became truly clear. I mean, now it is clear from the start. I just didn't quite grasp the shape of it at first.

Third, after thinking this over, I'm wondering whether now would be a good time to implement a canonical form of finish-on-TLAST? I don't mean that it needs to become another prerequisite for this project, but the dynamic specialization could probably make a very real early use of it: fixed hardware topology, but runtime-controlled transfer/termination behavior. Maybe that could extend IO flexibility enough to solve some problems?

Sorry, I spent so much time restating things you've already said. I'm just reasoning through this. I haven't spent very much time thinking about this layer or the project yet.

[hunhoffe]

Small correction to the Phase 0a TCT criterion

The TCT balance check is implemented (#3254, split out of #3226 and verified on Strix). While building it I found the direction of the failure mode in 0a needs a flip. The plan says:

a loop that pushes N times but awaits once outside the loop silently under-waits and reads incomplete data

... but that's actually legal. Checking against the lowering: a sync pops one fungible token from a FIFO keyed (col, row, direction, channel) — txn_append_sync carries no bd_id, so it waits for "a token on this channel," not a specific task. So push-N / await-once is the documented fire-and-forget / FIFO idiom (AIEX.td, "if you can reason one BD will always complete after all others, it is not strictly necessary to issue and wait on the TC token for every BD") — and it's exactly what the rolled ping-pong in #3226 relies on. Leftover tokens at sequence end are harmless.

The real bug is the dual — over-consumption: an await on a path where the matching token may not have been produced (the sync drains an empty FIFO and blocks forever). E.g. a token produced in only one scf.if arm but awaited after the join, or an await inside an scf.for whose producing start is outside the loop (fine on iteration 0, deadlocks after).

So the corrected criterion:

Along every control-flow path, token consumes (awaits) on a channel must never exceed token produces reaching that point.

Over-production is legal; only paths that can drain an empty FIFO are rejected, with a clear diagnostic.

The rest of 0a stands.

[hunhoffe]

@thomthehound Thanks for taking a look! Yes: aie.runtime_sequence becomes a compiled host-side control program that assembles the TXN from invocation-time scalars, with today's static lowering as a specialization.

Initial Goal: the first real goal is "compile a GEMM once, run it at many matrix sizes" — runtime M/K/N into one xclbin, no recompile per shape. That keeps the dynamic path honest: it has to handle real runtime-valued offsets/strides/extents, not toy cases. Where we bound complexity beyond that, I'm genuinely not sure yet — runtime trip counts and conditionals are in, full runtime legalization of illegal access patterns is out, but the line in between (how far control flow can go before it's not worth it vs. just recompiling) I expect we'll find empirically. Open to thoughts on where you think that boundary should be.

On overhead — The static/constant-bound case stays on the existing flat-binary path (constant-bound scf is unrolled straight to the binary TXN). So if nothing is actually runtime-valued, there shouldn't be overhead. The general machinery only kicks in for a genuinely dynamic scalar — two paths sharing representation upstream, diverging at lowering, static one untouched. For the dynamic path there is real host-side cost (a C++ function building the TXN per invocation). I haven't measured overhead yet.... I'm going to rely on the maxim: "premature optimization is the root of all evil" and worry more about this once I have something functional.

On "more than SSA liveness" — agreed. BD-ID allocation needed region-aware liveness (plain mlir::Liveness falsely makes scf.if arms interfere), and TCT balance (#3254) turned out to be a separate counted invariant — fungible per-channel token FIFOs, not value liveness.

On XRT fences — agreed, great point. Might be follow on work to think more deeply about this, I haven't worked through the full implications of this yet.

On finish-on-TLAST — I want to understand your use case before I answer well. I haven't worked through the implications yet either, so rather than hand-wave: can you sketch the workload shape you have in mind?

Thanks for participating in this discussion!

[thomthehound]

@hunhoffe Thank you for your clarification, Erika!

I'm glad to hear all of that. It's what I gathered from what you were saying, but I just wanted to be sure, especially about what the costs are going to be. This is all great news, and I am super-excited about this work!

Because I'm a little bit less "in the weeds" on this than you, I'm looking at it from a pretty high level, at which point it becomes, in my mind, essentially: on the fly memory access pattern changes. Love it. GPU can do this with its shaders, but NPU couldn't without loading another xclbin. That's a huge feature gap closed when this lands.

I agree that you shouldn't over-optimize now, but I'm almost certain there is going to be a temptation to introduce polling the further into this that you get. Preventing that isn't really an optimization; it's just the way it needs to be in order for dynamic mode to not become a perpetual tax. Aside from that, everything else is just gravy. Obviously I wouldn't want to hold up your work by pressing the matter, but I would plan around this problem early, even if you use polling to get it off the ground. From previous experience I can say that fences often turn out to be the difference between "Welp, this turned out to be a disappointment" and "Wow! That's even faster than I thought it would be!"

As for the FoT idea I mentioned... honestly, it's something that's just been in the back of my mind for a while without any clear use-case. But it seems like there could be a simplification here if we don't need the control program to always know the exact output length for every given shape. Perhaps it could just size an output BO at a sensible, compile-time-determined, maximum from the start? Up front: the idea is half-baked (not even a quarter, really). Nothing to get distracted by. (Edit: although I do feel like there is a way to remove at least some of the output descriptor issues this way. If we can stop needing to care about reprogramming the output stream, then the input stream can be treated as just some sort of variably-strided pointer through a compile-time schedule. It seems like that could resolve a whole layer of the problem if we reduce it down to "just steer the memory pointer"). This couldn't really be that helpful unless output data layout never changed. So, sorry about the lark.

Anyway, I'll try to keep following this as it develops, but I can't promise I'm going to have a huge amount of helpful feedback. Terrific idea, and great work, though!