MLIR-AIE 1.4.6.dev
AIEAssignRuntimeSequenceBDIDs.cpp
Go to the documentation of this file.
1//===- AIEAssignRuntimeSequenceBDIDs.cpp ------------------------*- C++ -*-===//
2//
3// Copyright (C) 2024 Advanced Micro Devices, Inc.
4// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
5//
6//===----------------------------------------------------------------------===//
7//
8// Assigns buffer-descriptor (BD) IDs to the DMA tasks configured in a runtime
9// sequence.
10//
11// This pass runs on straight-line IR: --aie-unroll-runtime-sequence-loops has
12// unrolled every constant-trip scf.for, and canonicalization has folded every
13// constant-predicate scf.if, before this pass runs. So in the static path no
14// scf op survives to reach the allocator -- a rolled ping-pong over a constant
15// loop is just N straight-line configures whose ids ordinary liveness reuse
16// recycles. Any scf.for/scf.if still present is therefore runtime-valued, which
17// the static path cannot lower (the runtime sequence becomes a flat, branchless
18// NPU instruction stream); such forms are rejected here for the dynamic EmitC
19// path (Phase 2).
20//
21// aie-split-long-repeats has already made every start exactly one queue push.
22//
23// The per-channel resource checks before allocation (see the pass
24// description) are verifyChannelUsage, a single-pass per-channel count on the
25// straight-line IR; what an await there proves relies on checkTokensConsumed
26// (DmaQueueModel.h). reclaim-bds's "status poll already proves finished, or
27// one inserted to" is reclaimFor.
28//
29//===----------------------------------------------------------------------===//
30
37
38#include "mlir/Dialect/Arith/IR/Arith.h"
39#include "mlir/Dialect/SCF/IR/SCF.h"
40#include "mlir/Dialect/Utils/StaticValueUtils.h"
41#include "mlir/Pass/Pass.h"
42#include "llvm/ADT/DenseMap.h"
43#include "llvm/ADT/DenseSet.h"
44#include "llvm/ADT/SmallPtrSet.h"
45#include "llvm/Support/MathExtras.h"
46#include "llvm/Support/Threading.h"
47
48#include <array>
49#include <deque>
50#include <map>
51#include <set>
52
53namespace xilinx::AIEX {
54#define GEN_PASS_DEF_AIEASSIGNRUNTIMESEQUENCEBDIDS
55#include "aie/Dialect/AIEX/Transforms/AIEXPasses.h.inc"
56} // namespace xilinx::AIEX
57
58using namespace mlir;
59using namespace xilinx;
60using namespace xilinx::AIEX;
61
62namespace {
63
64struct AIEAssignRuntimeSequenceBDIDsPass
65 : xilinx::AIEX::impl::AIEAssignRuntimeSequenceBDIDsBase<
66 AIEAssignRuntimeSequenceBDIDsPass> {
67 using Base = xilinx::AIEX::impl::AIEAssignRuntimeSequenceBDIDsBase<
68 AIEAssignRuntimeSequenceBDIDsPass>;
69 AIEAssignRuntimeSequenceBDIDsPass() = default;
70 AIEAssignRuntimeSequenceBDIDsPass(
71 const AIEAssignRuntimeSequenceBDIDsOptions &options)
72 : Base(options) {}
73
74 llvm::DenseMap<AIE::TileID, BdIdGenerator> gens;
75
76 // How to retire a copy still holding an id, by whether it issues a token.
77 static constexpr llvm::StringLiteral kWaitForToken =
78 "wait for it (aiex.npu.sync or aiex.npu.dma_wait on its channel, "
79 "consuming its token).";
80 static constexpr llvm::StringLiteral kNoTokenAdvice =
81 "it issues no token: set issue_token = true and wait for it, or await "
82 "a later token-issuing transfer on its channel.";
83
84 // Whether `op` writes array registers raw, at an address it does not fix or
85 // over one of `keys`' task queues, so pushing a task no count sees.
86 static bool writesQueue(Operation *op,
87 ArrayRef<DmaQueueModel::ChannelKey> keys) {
88 std::optional<uint32_t> first;
89 uint64_t bytes = 4;
90 if (auto write = dyn_cast<NpuWrite32Op>(op)) {
91 if (write.getBuffer())
92 return false;
93 first = write.getAbsoluteAddress();
94 } else if (auto write = dyn_cast<NpuMaskWrite32Op>(op)) {
95 if (write.getBuffer())
96 return false;
97 first = write.getAbsoluteAddress();
98 } else if (auto write = dyn_cast<NpuBlockWriteOp>(op)) {
99 if (write.getBuffer())
100 return false;
101 first = write.getAbsoluteAddress();
102 auto data = dyn_cast<MemRefType>(write.getData().getType());
103 if (!data || !data.hasStaticShape())
104 return true;
105 bytes = data.getNumElements() * data.getElementTypeBitWidth() / 8;
106 } else {
107 return false;
108 }
109 if (!first)
110 return true;
111 const AIETargetModel &tm =
112 op->getParentOfType<AIE::DeviceOp>().getTargetModel();
113 return llvm::any_of(keys, [&](const DmaQueueModel::ChannelKey &key) {
114 uint64_t queue = tm.getDmaQueueAddress(
115 key[0], key[1], key[3], static_cast<AIE::DMAChannelDir>(key[2]));
116 return queue >= *first && queue < *first + bytes;
117 });
118 }
119
120 // The BD ids each device's static DMAs take, by tile. Generators restart
121 // at every PDI load, so this is read once per tile per load.
122 //
123 // Known limitation: after a load_pdi of another device, this and
124 // loopingStartsOf read that sibling device's DMA programs, which races with
125 // the sibling's own nested pipeline (aie-dma-to-npu adds globals to its
126 // block) once devices run in parallel. The MLIR aiecc builds against runs
127 // them one at a time today. Splitting the nest does not help, since the pass
128 // manager merges adjacent device nests; a parallel build needs these
129 // summaries computed at module scope before the nest.
130 llvm::DenseMap<Operation *,
131 llvm::DenseMap<AIE::TileID, SmallVector<uint32_t>>>
132 staticBdIds;
133
134 // Mark every BD id a static DMA already took on `tile`, so this allocator
135 // doesn't hand the same id to a runtime-sequence task.
136 void seedFromStaticBds(AIE::DeviceOp device, AIE::TileOp tile,
137 BdIdGenerator &gen) {
138 auto [it, inserted] = staticBdIds.try_emplace(device);
139 if (inserted)
140 for (AIE::DmaBody program : device.getOps<AIE::DmaBody>())
141 llvm::append_range(it->second[program.getTileID()],
142 AIE::getAssignedBdIds(program));
143 for (uint32_t id : it->second.lookup(tile.getTileID()))
144 if (!gen.bdIdAlreadyAssigned(id))
145 gen.assignBdId(id);
146 }
147
148 // Keyed by (col, row), not the aie.tile op's own identity: two tile ops
149 // for one coordinate (accepted elsewhere, see runtime_vs_static_multi_
150 // tile.mlir) must share one generator, not bypass each other's claims.
151 BdIdGenerator &getGeneratorForTile(AIE::TileOp tile) {
152 AIE::TileID id = tile.getTileID();
153 auto it = gens.find(id);
154 if (it == gens.end()) {
155 AIE::DeviceOp device = tile->getParentOfType<AIE::DeviceOp>();
156 it = gens.insert({id, BdIdGenerator(tile.getCol(), tile.getRow(),
157 device.getTargetModel())})
158 .first;
159 seedFromStaticBds(device, tile, it->second);
160 if (loadedDevice && loadedDevice != device)
161 seedFromStaticBds(loadedDevice, tile, it->second);
162 }
163 return it->second;
164 }
165
166 // Each device's static aie.dma_starts whose BD chain never ends, by channel.
167 llvm::DenseMap<Operation *,
168 std::map<DmaQueueModel::ChannelKey, AIE::DMAStartOp>>
169 loopingStarts;
170 // Channels an aiex.dma_channel_reset drained since the latest load.
171 std::set<DmaQueueModel::ChannelKey> resetChannels;
172
173 std::map<DmaQueueModel::ChannelKey, AIE::DMAStartOp> &
174 loopingStartsOf(AIE::DeviceOp device) {
175 auto [it, inserted] = loopingStarts.try_emplace(device);
176 auto &starts = it->second;
177 if (!inserted)
178 return starts;
179 for (AIE::DmaBody program : device.getOps<AIE::DmaBody>()) {
180 AIE::TileID tile = program.getTileID();
181 program->walk([&](AIE::DMAStartOp start) {
182 if (start.getEndpoint())
183 return;
184 llvm::SmallPtrSet<Block *, 8> visited;
185 Block *bd = start.getDest();
186 while (bd && visited.insert(bd).second)
187 bd = bd->getNumSuccessors() == 1 ? bd->getSuccessor(0) : nullptr;
188 if (bd)
189 starts.try_emplace({tile.col, tile.row,
190 static_cast<int>(start.getChannelDir()),
191 start.getChannelIndex()},
192 start);
193 });
194 }
195 return starts;
196 }
197
198 // A task pushed behind a static program that never ends never runs. Only
199 // a named load tells which programs run; the sequence's own device does
200 // until the first load.
201 LogicalResult checkNotBehindLoop(DMAStartTaskOp start,
202 DMAConfigureTaskOp cfg) {
203 if (opaqueLoad)
204 return success();
206 if (resetChannels.count(key))
207 return success();
208 auto &starts =
209 loopingStartsOf(loadedDevice ? loadedDevice : getOperation());
210 auto it = starts.find(key);
211 if (it == starts.end())
212 return success();
213 InFlightDiagnostic diag =
214 start.emitOpError("starts a task on a channel whose static DMA "
215 "program loops forever, so the task never runs; "
216 "end that program's BD chain, or reset the channel "
217 "with aiex.dma_channel_reset first");
218 diag.attachNote(it->second.getLoc()) << "the program starts here";
219 return diag;
220 }
221
222 // The device the latest aiex.npu.load_pdi configured. A sequence that
223 // aie-materialize-runtime-sequences inlined runs on that device's static
224 // DMAs, which stay in it rather than in the device that holds the sequence.
225 AIE::DeviceOp loadedDevice;
226 // The latest aiex.npu.load_pdi, when it names no device in this module.
227 NpuLoadPdiOp opaqueLoad;
228 // Configures from before the latest aiex.npu.load_pdi.
229 llvm::SmallPtrSet<Operation *, 16> unloaded;
230
231 // A PDI load reconfigures the array, so the tasks configured so far no
232 // longer hold ids and allocation restarts around the new static BDs.
233 void noteLoadPdi(NpuLoadPdiOp load) {
234 loadedDevice = loadedBy(load);
235 opaqueLoad = loadedDevice ? NpuLoadPdiOp() : load;
236 resetChannels.clear();
237 for (auto &[tile, tasks] : liveByTile)
238 for (DMAConfigureTaskOp task : tasks)
239 unloaded.insert(task);
240 gens.clear();
241 liveByTile.clear();
242 pendingAwaitReleases.clear();
243 freedInFlight.clear();
244 loadState = {};
245 }
246
247 // Reject control flow the static path cannot lower. Constant-trip scf.for is
248 // unrolled and constant-predicate scf.if is folded before this pass, so any
249 // scf op here is runtime-valued and belongs to the dynamic EmitC path.
250 LogicalResult rejectRuntimeControlFlow(AIE::RuntimeSequenceOp seq) {
251 WalkResult wr = seq.walk([&](Operation *op) -> WalkResult {
252 if (isa<scf::ForOp, scf::IfOp, scf::WhileOp>(op)) {
253 op->emitOpError(
254 "Runtime-valued control flow in a runtime sequence is not "
255 "supported by this static BD-ID allocation pass. Either pass "
256 "only constant-valued predicates to scf.for and scf.if so "
257 "`aie-unroll-runtime-sequence-loops` can unroll/fold them, or "
258 "use the dynamic EmitC path instead.");
259 return WalkResult::interrupt();
260 }
261 return WalkResult::advance();
262 });
263 return failure(wr.wasInterrupted());
264 }
265
266 // Track the two per-channel resources a sequence can exhaust. Their failure
267 // modes differ: over-production costs the TCT FIFO no capacity (see
268 // checkTokensConsumed for what it costs later), but a push onto a full queue
269 // is dropped and its transfer never runs.
270 //
271 // Queue counting differs from token counting in three ways: every push takes
272 // a slot, not just issue_token ones; a non-token push is still retired
273 // implicitly, since in-order execution means awaiting a token drains
274 // everything queued ahead of it too; and a repeat_count does not multiply
275 // slots. rejectRuntimeControlFlow has already run, so one program-order pass
276 // over straight-line IR is exact.
277 LogicalResult verifyChannelUsage(AIE::RuntimeSequenceOp seq) {
278 using ChannelKey = DmaQueueModel::ChannelKey;
279
280 const AIETargetModel &tm =
281 seq->getParentOfType<AIE::DeviceOp>().getTargetModel();
282
283 std::map<ChannelKey, int> avail;
284 DmaQueueModel queue;
285
286 WalkResult wr = seq.walk([&](Operation *op) -> WalkResult {
287 if (auto start = dyn_cast<DMAStartTaskOp>(op)) {
288 DMAConfigureTaskOp cfg = start.getTaskOp();
289 if (!cfg)
290 return WalkResult::advance();
291 ChannelKey key = DmaQueueModel::keyOf(cfg);
292 AIE::TileOp tile = cfg.getTileOp();
293 uint32_t depth = tm.getDmaTaskQueueDepth(
294 tile.getCol(), tile.getRow(), cfg.getChannel(), cfg.getDirection());
295 if (queue.wouldOverflow(key, depth))
296 guardQueueOverflow(queue, start, tm, key, depth, enforceQueueDepth);
297 bool issuesToken = start.getPushIssueToken(cfg);
298 queue.push(key, issuesToken);
299 if (issuesToken)
300 avail[key]++;
301 } else if (auto await = dyn_cast<DMAAwaitTaskOp>(op)) {
302 DMAConfigureTaskOp cfg = await.getTaskOp();
303 // A non-issue_token await is diagnosed later by aie-dma-tasks-to-npu;
304 // an unresolved task is diagnosed by the recycle path. Skip both here.
305 if (!cfg || !cfg.getIssueToken())
306 return WalkResult::advance();
307 ChannelKey key = DmaQueueModel::keyOf(cfg);
308 int &tokens = avail[key];
309 if (tokens < 1) {
310 await.emitOpError(
311 "awaits a task-completion token on a channel where no "
312 "outstanding token is guaranteed to have been produced; the "
313 "runtime sequence would block here forever. Ensure a prior "
314 "issue_token dma_start_task on the same tile, direction and "
315 "channel reaches this await");
316 return WalkResult::interrupt();
317 }
318 tokens--;
319 queue.awaitToken(key);
320 } else if (QueueEffect raw = rawQueueEffect(op, *deviceState.symbols);
321 raw.kind == QueueEffect::Kind::Await) {
322 // A raw wait may consume a token from a push this count cannot see,
323 // such as a raw register write. Do not diagnose those here, but never
324 // reuse a token already consumed by one.
325 avail[raw.key] = std::max(0, avail[raw.key] - 1);
326 queue.awaitToken(raw.key);
327 } else if (raw.kind == QueueEffect::Kind::Push) {
328 avail[raw.key] += raw.issuesToken;
329 queue.push(raw.key, raw.issuesToken);
330 }
331 return WalkResult::advance();
332 });
333 return failure(wr.wasInterrupted());
334 }
335
336 LogicalResult validate(AIE::RuntimeSequenceOp seq) {
337 WalkResult unplaced = seq.walk([](DMAConfigureTaskOp cfg) {
338 if (cfg.getTile().getDefiningOp<AIE::TileOp>())
339 return WalkResult::advance();
340 cfg.emitOpError("Cannot assign buffer descriptor ids to a DMA task "
341 "whose tile is not placed; run placement first.");
342 return WalkResult::interrupt();
343 });
344 if (unplaced.wasInterrupted())
345 return failure();
346 // Reject runtime control flow first, so the token-balance pass below runs
347 // on straight-line IR and needs no control-flow reasoning.
348 if (failed(rejectRuntimeControlFlow(seq)))
349 return failure();
350 if (failed(verifyChannelUsage(seq)))
351 return failure();
352 return success();
353 }
354
355 LogicalResult allocateConfigure(DMAConfigureTaskOp op) {
356 AIE::TileOp tile = op.getTileOp();
357 BdIdGenerator &gen = getGeneratorForTile(tile);
358
359 const AIETargetModel &targetModel =
360 tile->getParentOfType<AIE::DeviceOp>().getTargetModel();
361
362 // First, honor all the user-specified BD IDs.
363 WalkResult result = op.walk<WalkOrder::PreOrder>([&](AIE::DMABDOp bd_op) {
364 if (bd_op.getBdId().has_value()) {
365 if (!targetModel.isBdChannelAccessible(tile.getCol(), tile.getRow(),
366 bd_op.getBdId().value(),
367 op.getChannel())) {
368 bd_op.emitOpError("Buffer descriptor ID ")
369 << bd_op.getBdId().value() << " cannot be submitted on channel "
370 << op.getChannel() << " of tile (" << tile.getCol() << ","
371 << tile.getRow()
372 << "), which partitions its buffer descriptors by channel "
373 "parity: an even channel reaches only the low half of the "
374 "ids and an odd channel only the high half.";
375 return WalkResult::interrupt();
376 }
377 if (const HeldBy *held =
378 copyHolding(tile.getTileID(), bd_op.getBdId().value())) {
379 InFlightDiagnostic diag =
380 op.emitOpError("Specified buffer descriptor ID ")
381 << bd_op.getBdId().value()
382 << " is the one an aiex.npu.dma_memcpy_nd on this tile "
383 "programs, and that copy may still be in flight here. Give "
384 "the task another ID, or retire the copy first: ";
385 diag << (held->issuesToken ? kWaitForToken : kNoTokenAdvice);
386 diag.attachNote(held->copy->getLoc()) << "the copy is here";
387 return WalkResult::interrupt();
388 }
389 if (gen.bdIdAlreadyAssigned(bd_op.getBdId().value())) {
390 op.emitOpError("Specified buffer descriptor ID ")
391 << bd_op.getBdId().value()
392 << " is already in use. Release the earlier task first: "
393 "aiex.dma_await_task waits for hardware completion before its "
394 "BDs are reusable. aiex.dma_free_task also releases them but "
395 "does NOT wait, so it is only safe when some other "
396 "synchronization already guarantees that task has finished "
397 "(see programming_guide/section-2/section-2d/DMATasks.md).";
398 return WalkResult::interrupt();
399 }
400 checkReallocation(tile, bd_op.getBdId().value(), bd_op.getLoc());
401 gen.assignBdId(bd_op.getBdId().value());
402 }
403 return WalkResult::advance();
404 });
405 if (result.wasInterrupted())
406 return failure();
407
408 AIE::DMABDOp head = op.getFirstBd();
409 uint32_t headAlignment = DMAStartTaskOp::headBdIdAlignment(op.getResult());
410
411 // The ids a copy reprograms while this task may run are not its to take,
412 // including any a reclaim frees on the way.
413 SmallVector<int32_t> blocked;
414 auto block = [&] {
415 auto it = forbidden.find(op);
416 if (it == forbidden.end())
417 return;
418 for (auto [id, copy] : it->second)
419 if (!gen.bdIdAlreadyAssigned(id)) {
420 gen.assignBdId(id);
421 blocked.push_back(id);
422 }
423 };
424 block();
425 unsigned tookBack = 0;
426
427 // Now allocate BD IDs for all unspecified BDs.
428 result = op.walk<WalkOrder::PreOrder>([&](AIE::DMABDOp bd_op) {
429 if (bd_op.getBdId().has_value())
430 return WalkResult::advance();
431 if (opaqueLoad) {
432 bd_op.emitOpError(
433 "needs a buffer descriptor ID, but the aiex.npu.load_pdi "
434 "before it does not name a device in this module, so the "
435 "compiler cannot tell which ids the loaded PDI's static "
436 "DMAs use. Name the loaded device with device_ref = "
437 "@<device>, or give this aie.dma_bd a bd_id that the PDI "
438 "leaves free.")
439 .attachNote(opaqueLoad.getLoc())
440 << "the PDI is loaded here";
441 return WalkResult::interrupt();
442 }
443 // channelIndex matters on a MemTile, where the AIE2 model partitions
444 // BDs by channel parity (isBdChannelAccessible: an even channel can
445 // only submit ids below 24, an odd channel only 24 and above).
446 uint32_t alignment = bd_op == head ? headAlignment : 1;
447 std::optional<int32_t> next_id = gen.nextBdId(op.getChannel(), alignment);
448 while (!next_id && reclaimBds && succeeded(reclaimFor(op))) {
449 ++tookBack;
450 block();
451 next_id = gen.nextBdId(op.getChannel(), alignment);
452 }
453 if (!next_id) {
454 auto diag =
455 op.emitOpError()
456 << "Too many simultaneously active buffer descriptors on tile ("
457 << tile.getCol() << "," << tile.getRow()
458 << "), which supports up to "
459 << targetModel.getNumBDsForChannel(tile.getCol(), tile.getRow(),
460 op.getChannel())
461 << ".";
462 SmallVector<std::tuple<int32_t, Operation *, bool>> copied;
463 if (auto it = forbidden.find(op); it != forbidden.end())
464 for (auto [id, copy] : it->second)
465 if (llvm::is_contained(blocked, id))
466 copied.push_back({id, copy, true});
467 for (auto [owner, id] : loadState.copyOwned)
468 if (owner == tile.getTileID() &&
469 targetModel.isBdChannelAccessible(tile.getCol(), tile.getRow(),
470 id, op.getChannel()))
471 copied.push_back(
472 {id, copyHolding(tile.getTileID(), id)->copy, false});
473 llvm::sort(copied);
474 if (!copied.empty()) {
475 diag << " Of those, aiex.npu.dma_memcpy_nd ops program "
476 << (copied.size() > 1 ? "ids " : "id ");
477 llvm::interleaveComma(
478 copied, diag, [&](auto &entry) { diag << std::get<0>(entry); });
479 diag << " while this task may run (see the notes).";
480 }
481 // reclaimFor only ever considers a liveByTile task, never a copy, so
482 // its advice -- and the task-shaped reasons it failed -- apply only
483 // where some other task actually lives on this tile to reclaim from.
484 bool otherLiveTask = llvm::any_of(
485 liveByTile[tile.getTileID()],
486 [&](DMAConfigureTaskOp t) { return !releasedTasks.contains(t); });
487 if (otherLiveTask) {
488 diag << " Emit an aiex.dma_await_task to free BDs for reuse; it "
489 "waits for hardware completion, so the recycled ids are no "
490 "longer in flight. aiex.dma_free_task also recycles ids but "
491 "does NOT wait for completion -- using it before the task "
492 "has finished is a race -- so reach for it only when some "
493 "other synchronization already guarantees completion (see "
494 "programming_guide/section-2/section-2d/DMATasks.md).";
495 if (reclaimBds && tookBack)
496 diag << " The ids the compiler took back did not cover it, and "
497 "it could not take more: every other task holding one is "
498 "not started yet, is started again later, waits on a "
499 "lock this or a later task releases, or runs on a "
500 "channel whose status it cannot poll.";
501 else if (reclaimBds)
502 diag << " The compiler could not take any back either: every "
503 "task holding one is not started yet, is started again "
504 "later, waits on a lock this or a later task releases, "
505 "or runs on a channel whose status it cannot poll.";
506 else
507 diag << " Or let the compiler poll for finished tasks and take "
508 "their ids (reclaim-bds, aiecc --reclaim-runtime-bds), "
509 "provided no task depends on a push issued after it.";
510 } else if (!copied.empty()) {
511 diag << " Every id in use here is an aiex.npu.dma_memcpy_nd copy "
512 "(reclaim-bds does not consider those); retire the ones "
513 "the notes name, or give this task's buffer descriptors "
514 "other ids.";
515 }
516 for (auto [id, copyOp, isForbidden] : copied) {
517 auto copy = cast<NpuDmaMemcpyNdOp>(copyOp);
518 Diagnostic &note = diag.attachNote(copy.getLoc());
519 note << "this copy " << (isForbidden ? "reprograms" : "holds")
520 << " buffer descriptor ID " << id
521 << (isForbidden ? " while the task may run; "
522 : " until it is retired: ");
523 note << (rawQueueEffect(copy, *deviceState.symbols).issuesToken
524 ? kWaitForToken
525 : kNoTokenAdvice);
526 }
527 return WalkResult::interrupt();
528 }
529 checkReallocation(tile, *next_id, bd_op.getLoc());
530 bd_op.setBdId(next_id);
531 roundState.assignedHere.push_back(bd_op);
532 return WalkResult::advance();
533 });
534 for (int32_t id : blocked)
535 gen.freeBdId(id);
536 if (result.wasInterrupted())
537 return failure();
538
539 liveByTile[tile.getTileID()].push_back(op);
540 return success();
541 }
542
543 // One push onto a channel: the task it started (null for a raw push or
544 // memcpy transfer) and whether that push issues a token. A task started more
545 // than once may issue a token on only some of its pushes.
546 struct StartedTask {
547 DMAConfigureTaskOp task;
548 Operation *origin;
549 bool issuesToken;
550 // Program order of the push, for picking the oldest task to reclaim.
551 uint64_t order;
552 };
553 // Pushes on a channel, in program order, whose tokens no await has consumed
554 // yet. A status poll proves a prefix of them finished, the first `finished`;
555 // their tokens, if any, still wait for an await, so they stay here until one
556 // consumes them.
557 struct ChannelPushes {
558 SmallVector<StartedTask, 8> tasks;
559 size_t finished = 0;
560 };
561 std::map<DmaQueueModel::ChannelKey, ChannelPushes> startedOnChannel;
562 uint64_t pushCount = 0;
563 // Per configure, its pushes in startedOnChannel, how many of them are not
564 // yet finished, and the order of its latest one. A configure pushes onto
565 // its own channel alone.
566 struct PushCounts {
567 unsigned started = 0;
568 unsigned running = 0;
569 uint64_t lastPushOrder = 0;
570 };
571 llvm::DenseMap<Operation *, PushCounts> pushCounts;
572
573 void notePush(const DmaQueueModel::ChannelKey &key, DMAConfigureTaskOp task,
574 bool issuesToken, Operation *origin,
575 AIE::ShimDMAAllocationOp allocation,
576 std::optional<Volume> moved) {
577 uint64_t order = pushCount++;
578 startedOnChannel[key].tasks.push_back({task, origin, issuesToken, order});
579 if (task) {
580 PushCounts &counts = pushCounts[task];
581 ++counts.started;
582 ++counts.running;
583 counts.lastPushOrder = order;
584 }
585 if (!allocation)
586 return;
587 auto &pushes = loadState.pushesByAllocation[allocation];
588 std::optional<Volume> through =
589 pushes.empty() ? Volume() : pushes.back().through;
590 if (through && moved)
591 for (auto [term, bytes] : *moved)
592 (*through)[term] += bytes;
593 else
594 through = std::nullopt;
595 pushes.push_back({order, through});
596 }
597 // Configures whose completion an await has established.
598 llvm::SmallPtrSet<Operation *, 16> knownComplete;
599 // Configures a status poll, or the consumption an output's await proves
600 // (#aie.consumed_by), shows finished. Kept apart from knownComplete so that
601 // the ids an await releases do not move.
602 llvm::SmallPtrSet<Operation *, 16> provenFinished;
603 // Configures whose ids reclaimFor took back.
604 llvm::SmallPtrSet<Operation *, 16> reclaimed;
605 // Configures whose ids went back to the pool by any route.
606 llvm::SmallPtrSet<Operation *, 16> releasedTasks;
607 // State scoped to one allocation attempt of one sequence: reset by
608 // assignment in resetPerSequenceState, which runs again for each
609 // reallocation round within a sequence.
610 struct RoundState {
611 // Each top-level op's place in the sequence, and per lock the last place
612 // a task releasing it is configured or started (see reclaimFor).
613 llvm::DenseMap<Operation *, unsigned> positionOf;
614 llvm::DenseMap<Value, unsigned> lastReleaseOf;
615 bool reallocate = false;
616 // What one allocation of the sequence did that the next undoes.
617 SmallVector<AIE::DMABDOp> assignedHere;
618 SmallVector<Operation *> insertedHere;
619 };
620 RoundState roundState;
621
622 void indexLockReleases(AIE::RuntimeSequenceOp seq) {
623 unsigned position = 0;
624 for (Operation &op : seq.getBody().getOps()) {
625 roundState.positionOf[&op] = position++;
626 DMAConfigureTaskOp cfg = dyn_cast<DMAConfigureTaskOp>(op);
627 if (auto start = dyn_cast<DMAStartTaskOp>(op))
628 cfg = start.getTaskOp();
629 if (!cfg)
630 continue;
631 cfg.walk([&](AIE::UseLockOp lock) {
632 if (lock.release())
633 roundState.lastReleaseOf[lock.getLock()] = roundState.positionOf[&op];
634 });
635 }
636 }
637
638 // Configures allocated on each tile, in program order.
639 llvm::DenseMap<AIE::TileID, SmallVector<DMAConfigureTaskOp, 16>> liveByTile;
640
641 // An aiex.npu.dma_memcpy_nd's BD id is held on its tile from its push until
642 // the queue model counts that push finished. Holds are kept per channel in
643 // push order, so they retire as a prefix; per tile and id, the copies
644 // holding it by push order, and whether they took it in the generator.
645 struct CopyHold {
646 uint64_t order;
647 AIE::TileID tile;
648 int32_t id;
649 };
650 using TileBdId = std::pair<AIE::TileID, int32_t>;
651 struct HeldBy {
652 NpuDmaMemcpyNdOp copy;
653 bool issuesToken;
654 };
655 // Per configure, the ids it may not take and the copy that reprograms each
656 // while it may run.
657 llvm::DenseMap<Operation *, SmallVector<std::pair<int32_t, Operation *>>>
658 forbidden;
659
660 // The oldest copy still holding `id` on `tile`, if copies hold it.
661 const HeldBy *copyHolding(AIE::TileID tile, int32_t id) const {
662 if (!loadState.copyOwned.contains({tile, id}))
663 return nullptr;
664 return &loadState.holdsOn.find({tile, id})->second.begin()->second;
665 }
666
667 // Return a task's id to the pool; a copy waiting for it takes it at once.
668 void releaseTaskBdId(AIE::TileID tile, BdIdGenerator &gen, int32_t id) {
669 gen.freeBdId(id);
670 if (!loadState.holdsOn.contains({tile, id}))
671 return;
672 gen.assignBdId(id);
673 loadState.copyOwned.insert({tile, id});
674 }
675
676 static DMAStartTaskOp startAfter(DMAConfigureTaskOp task, Operation *op) {
677 DMAStartTaskOp first;
678 for (Operation *user : task.getResult().getUsers())
679 if (auto start = dyn_cast<DMAStartTaskOp>(user);
680 start && start->getBlock() == op->getBlock() &&
681 op->isBeforeInBlock(start) &&
682 (!first || start->isBeforeInBlock(first)))
683 first = start;
684 return first;
685 }
686
687 // The copy reprograms its BD at once, so a task on that id must neither be
688 // in flight nor be started again after it.
689 LogicalResult holdCopy(NpuDmaMemcpyNdOp copy,
690 const DmaQueueModel::ChannelKey &key, uint64_t order,
691 bool issuesToken) {
692 AIE::TileOp tile = allocationOf(copy).getTileOp();
693 AIE::TileID tileId = tile.getTileID();
694 auto id = static_cast<int32_t>(copy.getId());
695 if (auto held = loadState.holdsOn.find({tileId, id});
696 held != loadState.holdsOn.end() && warnUnsafeBdReuse) {
697 const HeldBy &earlier = held->second.begin()->second;
698 auto [entry, inserted] = copiesOverCopies.try_emplace(
699 copy.getLoc(),
700 CopyOverCopy{id, tile.getCol(), tile.getRow(), earlier.copy->getLoc(),
701 earlier.issuesToken});
702 entry->second.tiles.insert({tile.getCol(), tile.getRow()});
703 entry->second.count++;
704 }
705 BdIdGenerator &gen = getGeneratorForTile(tile);
706 loadState.holdsByChannel[key].push_back({order, tileId, id});
707 loadState.holdsOn[{tileId, id}][order] = {copy, issuesToken};
708 if (!gen.bdIdAlreadyAssigned(id)) {
709 checkReallocation(tile, id, copy.getLoc());
710 gen.assignBdId(id);
711 loadState.copyOwned.insert({tileId, id});
712 return success();
713 }
714 if (loadState.copyOwned.contains({tileId, id}))
715 return success();
716 for (DMAConfigureTaskOp task : liveByTile[tileId]) {
717 if (releasedTasks.contains(task) || unloaded.contains(task))
718 continue;
719 AIE::DMABDOp held;
720 task.walk([&](AIE::DMABDOp bd) {
721 if (bd.getBdId() == id)
722 held = bd;
723 });
724 if (!held)
725 continue;
726 bool running = pushCounts.lookup(task).running;
727 // A task not yet started even once has no prior push to its name: its
728 // only start landing after the copy is its first, not a restart.
729 bool everStarted = pushCounts.contains(task);
730 DMAStartTaskOp restart = startAfter(task, copy);
731 if (!running && !restart)
732 return success();
733 if (!llvm::is_contained(roundState.assignedHere, held)) {
734 InFlightDiagnostic diag =
735 task.emitOpError("Specified buffer descriptor ID ") << id;
736 if (running)
737 diag << " is the one an aiex.npu.dma_memcpy_nd on this tile "
738 "programs while this task may be in flight. Give the task "
739 "another ID, or await it before the copy.";
740 else if (everStarted)
741 diag << " is the one an aiex.npu.dma_memcpy_nd on this tile "
742 "programs before this task is started again, so the "
743 "restart would run the copy's descriptor. Give the task "
744 "another ID, or configure a new task after the copy.";
745 else
746 diag << " is the one an aiex.npu.dma_memcpy_nd on this tile "
747 "programs after this task's own configure wrote it, so "
748 "starting the task would launch the copy's descriptor "
749 "instead of its own. Give the task another ID, or start it "
750 "before the copy.";
751 diag.attachNote(copy.getLoc()) << "the copy is here";
752 if (!running)
753 diag.attachNote(restart.getLoc())
754 << (everStarted ? "the task is started again here"
755 : "the task starts here, after the copy");
756 return failure();
757 }
758 assert(llvm::none_of(forbidden[task],
759 [&](auto &entry) { return entry.first == id; }) &&
760 "a forbidden id was handed out again");
761 forbidden[task].push_back({id, copy});
762 roundState.reallocate = true;
763 return success();
764 }
765 // The id was already taken in the generator, owned by neither a copy
766 // nor a live task: only a static DMA program claims an id that way.
767 InFlightDiagnostic diag = copy.emitOpError("programs buffer descriptor ID ")
768 << id << ", which a static DMA program on tile ("
769 << tile.getCol() << "," << tile.getRow()
770 << ") already uses; give the copy another ID";
771 AIE::DeviceOp other =
772 loadedDevice && loadedDevice != getOperation() ? loadedDevice : nullptr;
773 for (AIE::DeviceOp candidate : {getOperation(), other})
774 if (candidate)
775 for (AIE::DmaBody program : candidate.getOps<AIE::DmaBody>())
776 if (program.getTileID() == tileId)
777 program.getDmaBody().walk([&](AIE::DMABDOp bd) {
778 if (bd.getBdId() == id)
779 diag.attachNote(bd.getLoc())
780 << "the static program's buffer descriptor is here";
781 });
782 return diag;
783 }
784
785 void releaseRetiredCopies(const DmaQueueModel::ChannelKey &key) {
786 auto holds = loadState.holdsByChannel.find(key);
787 if (holds == loadState.holdsByChannel.end())
788 return;
789 const ChannelPushes &channel = startedOnChannel[key];
790 std::optional<uint64_t> oldest;
791 if (channel.finished < channel.tasks.size())
792 oldest = channel.tasks[channel.finished].order;
793 while (!holds->second.empty() &&
794 (!oldest || holds->second.front().order < *oldest)) {
795 CopyHold hold = holds->second.front();
796 holds->second.pop_front();
797 auto on = loadState.holdsOn.find({hold.tile, hold.id});
798 on->second.erase(hold.order);
799 if (!on->second.empty())
800 continue;
801 loadState.holdsOn.erase(on);
802 if (loadState.copyOwned.erase({hold.tile, hold.id}))
803 gens.find(hold.tile)->second.freeBdId(hold.id);
804 }
805 }
806
807 // BD ids released by aiex.dma_free_task while the task could still have been
808 // in flight, keyed by tile, with the task and the free that released them.
809 struct ReleasedTask {
810 DMAConfigureTaskOp configure;
811 Operation *freeOp;
812 };
813 std::map<std::pair<int, int>, std::map<uint32_t, ReleasedTask>> freedInFlight;
814
815 // An await consumes the oldest outstanding token on the channel, regardless
816 // of the configure named by its SSA operand. Only that token-issuing task and
817 // the tasks queued ahead of it are known to have finished.
818 void noteAwaited(const DmaQueueModel::ChannelKey &key) {
819 ChannelPushes &channel = startedOnChannel[key];
820 auto &started = channel.tasks;
821 auto *it = llvm::find_if(
822 started, [](const StartedTask &s) { return s.issuesToken; });
823 if (it == started.end())
824 return;
825 size_t retired = std::distance(started.begin(), it) + 1;
826 for (size_t i = 0; i < retired; ++i)
827 if (DMAConfigureTaskOp task = started[i].task) {
828 --pushCounts[task].started;
829 if (i >= channel.finished)
830 --pushCounts[task].running;
831 }
832 for (size_t i = 0; i < retired; ++i)
833 if (DMAConfigureTaskOp task = started[i].task)
834 if (pushCounts.lookup(task).started == 0)
835 knownComplete.insert(task);
836 // Counts are cumulative, so the newest push an allocation retired here
837 // credits all that its older ones would.
838 SmallVector<std::pair<AIE::ShimDMAAllocationOp, uint64_t>> newest;
839 for (const StartedTask &push :
840 llvm::reverse(llvm::make_range(started.begin(), std::next(it))))
841 if (AIE::ShimDMAAllocationOp output =
842 push.task ? allocationOf(push.task)
843 : allocationOf(dyn_cast<NpuDmaMemcpyNdOp>(push.origin)))
844 if (llvm::none_of(newest,
845 [&](auto &seen) { return seen.first == output; }))
846 newest.push_back({output, push.order});
847 started.erase(started.begin(), std::next(it));
848 channel.finished -= std::min(channel.finished, retired);
849 for (auto [output, order] : newest)
850 creditInputs(output, order);
851 releaseRetiredCopies(key);
852 }
853
854 // A status poll, or consumption an output proves, shows at most
855 // `unfinished` pushes on `key` still queued or running. The channel runs its
856 // queue in order, so those are the newest.
857 void noteDrained(const DmaQueueModel::ChannelKey &key, size_t unfinished) {
858 ChannelPushes &channel = startedOnChannel[key];
859 if (channel.tasks.size() <= unfinished)
860 return;
861 for (size_t done = channel.tasks.size() - unfinished;
862 channel.finished < done; ++channel.finished)
863 if (DMAConfigureTaskOp task = channel.tasks[channel.finished].task)
864 if (--pushCounts[task].running == 0)
865 provenFinished.insert(task);
866 releaseRetiredCopies(key);
867 }
868
869 // The output bytes `proof` lets count: `received` rounded down to a
870 // multiple of its granule, at least `received` - (granule - 1).
871 static Volume countedOutput(const Volume &received,
872 AIE::ConsumedByAttr proof) {
873 int64_t granule = proof.getGranuleBytes();
874 Volume counted = received;
875 if (!wholeGranules(received, granule))
876 counted[-1] -= granule - 1;
877 return counted;
878 }
879
880 // Whether the host library holds the scratchpad parameter `seq` reads at
881 // state-table index `index` at 0 or above. Commands that never run together
882 // share slots, so where `seq` does not list what it reads, every parameter
883 // on the slot must be.
884 bool nonNegative(AIE::RuntimeSequenceOp seq, int64_t index) {
885 auto [it, inserted] = deviceState.nonNegativeByIndex.try_emplace(
886 {seq.getOperation(), index}, false);
887 if (!inserted)
888 return it->second;
889 auto module = getOperation()->getParentOfType<ModuleOp>();
890 if (!module)
891 return false;
892 ArrayAttr reads = seq.getScratchpadParametersAttr();
893 bool found = false, held = true;
894 for (auto parameter : module.getOps<ScratchpadParameterOp>()) {
895 if (parameter.getStateTableIdx() != index ||
896 (reads &&
897 !llvm::is_contained(reads.getAsValueRange<FlatSymbolRefAttr>(),
898 parameter.getSymName())))
899 continue;
900 std::optional<int32_t> min = parameter.getMinValue();
901 found = true;
902 held &= min && *min >= 0;
903 }
904 it->second = found && held;
905 return it->second;
906 }
907
908 // The bytes one push of `cfg` by `start` moves, or nullopt where its chain
909 // loops, iterates, continues outside its body, or takes its length from a
910 // parameter not held non-negative.
911 std::optional<Volume> pushVolume(DMAStartTaskOp start,
912 DMAConfigureTaskOp cfg) {
913 std::optional<int64_t> repeat =
914 start.hasRepeatParameter()
915 ? std::nullopt
916 : getConstantIntValue(start.getPushRepeatCount(cfg));
917 Region &body = cfg.getBody();
918 if (!repeat || *repeat < 0 || body.empty())
919 return std::nullopt;
920 Volume bytes;
921 llvm::SmallPtrSet<Block *, 8> seen;
922 for (Block *block = &body.front(); block;) {
923 if (!seen.insert(block).second)
924 return std::nullopt;
925 for (AIE::DMABDOp bd : block->getOps<AIE::DMABDOp>()) {
926 std::optional<int64_t> len = bd.getStaticLenInBytes();
927 if (!len || bd.getIteration() || bd.getNextBdId() ||
928 bd.getLengthParameterAttr())
929 return std::nullopt;
930 int64_t width = bd.getBufferElementTypeWidthInBytes();
931 bytes[-1] += *len;
932 if (std::optional<uint8_t> index = bd.getLengthStateTableIdx()) {
933 std::optional<int32_t> unit = bd.getLengthUnit();
934 if (!unit ||
935 !nonNegative(start->getParentOfType<AIE::RuntimeSequenceOp>(),
936 *index))
937 return std::nullopt;
938 bytes[*index] += static_cast<int64_t>(*unit) * width;
939 }
940 }
941 auto next = dyn_cast<AIE::NextBDOp>(block->getTerminator());
942 block = next ? next.getDest() : nullptr;
943 }
944 for (auto &[key, coefficient] : bytes)
945 if (llvm::MulOverflow(coefficient, *repeat + 1, coefficient))
946 return std::nullopt;
947 return bytes;
948 }
949
950 // The bytes one push of `copy` moves, or nullopt unless all its sizes are
951 // constants.
952 static std::optional<Volume> copyVolume(NpuDmaMemcpyNdOp copy) {
953 std::optional<int64_t> bytes = copy.getStaticBytesStreamed();
954 if (!bytes)
955 return std::nullopt;
956 Volume volume;
957 volume[-1] = *bytes;
958 return volume;
959 }
960
961 // State whose lifetime is this device's whole processing in runOnOperation,
962 // independent of which sequence or load is being walked: reset by
963 // assignment there, so a new field is reset without a hand-kept list.
964 struct DeviceState {
965 // The device's symbols; a task names one of its own device's
966 // allocations. runOnOperation sets this before visiting any op.
967 std::optional<SymbolTable> symbols;
968 // Each output's proofs, with the input that holds each.
969 llvm::DenseMap<
970 Operation *,
971 SmallVector<std::pair<AIE::ShimDMAAllocationOp, AIE::ConsumedByAttr>>>
972 proofsByOutput;
973 // Whether leavesNothing already proved (input, output) balanced, valid
974 // for the device's lifetime since nothing it depends on changes per
975 // sequence.
976 llvm::DenseMap<std::pair<Operation *, Operation *>, bool> balancedPairs;
977 // nonNegative's memo.
978 llvm::DenseMap<std::pair<Operation *, int64_t>, bool> nonNegativeByIndex;
979 };
980 DeviceState deviceState;
981
982 // The shim allocation `cfg` was configured for, when substitution kept it.
983 AIE::ShimDMAAllocationOp allocationOf(DMAConfigureTaskOp cfg) {
984 FlatSymbolRefAttr alloc = cfg.getAllocAttr();
985 // NOLINTNEXTLINE(bugprone-unchecked-optional-access)
986 return alloc ? deviceState.symbols->lookup<AIE::ShimDMAAllocationOp>(
987 alloc.getAttr())
988 : nullptr;
989 }
990
991 // The shim allocation `copy` moves through.
992 AIE::ShimDMAAllocationOp allocationOf(NpuDmaMemcpyNdOp copy) {
993 if (!copy)
994 return nullptr;
995 // NOLINTNEXTLINE(bugprone-unchecked-optional-access)
996 return deviceState.symbols->lookup<AIE::ShimDMAAllocationOp>(
997 copy.getMetadata().getRootReference());
998 }
999
1000 // A shim allocation's pushes since the latest load, in program order, with
1001 // the bytes it has moved through each: nullopt from the first whose bytes
1002 // are unknown.
1003 struct AllocationPush {
1004 uint64_t order;
1005 std::optional<Volume> through;
1006 };
1007 // Per output, the bytes moved through its newest push an await retired since
1008 // the latest load (nullopt where unknown), and how many pushes the sequence
1009 // had issued by that await.
1010 struct Awaited {
1011 std::optional<Volume> through;
1012 uint64_t pushesBefore;
1013 };
1014 // State valid for one "loaded device" span: wiped at the per-sequence
1015 // reset and again whenever a new aiex.npu.load_pdi reconfigures the array.
1016 struct LoadState {
1017 llvm::DenseMap<Operation *, SmallVector<AllocationPush>> pushesByAllocation;
1018 // Per (input, output), how many of the input's pushes that output has
1019 // already proven taken: both counts only grow, so a credit resumes there.
1020 llvm::DenseMap<std::pair<Operation *, Operation *>, size_t> creditedPushes;
1021 llvm::DenseMap<Operation *, Awaited> awaitedThrough;
1022 std::map<DmaQueueModel::ChannelKey, std::deque<CopyHold>> holdsByChannel;
1023 llvm::DenseMap<TileBdId, std::map<uint64_t, HeldBy>> holdsOn;
1024 llvm::DenseSet<TileBdId> copyOwned;
1025 };
1026 LoadState loadState;
1027
1028 // Whether every stretch of every runtime sequence of this device, from its
1029 // start or a load to the next load or its end, ends with all of `input`'s
1030 // bytes covered by `output`'s under `proof`. The counts restart at each
1031 // stretch, but a load of the PDI already loaded leaves the array as it was,
1032 // so a stretch starts where the previous one, perhaps another dispatch's,
1033 // left it, and its counts hold only when none leaves input bytes behind.
1034 // They count only the two allocations' own tasks, so any other push on
1035 // either channel, in any sequence, voids the pair.
1036 bool leavesNothing(AIE::ShimDMAAllocationOp input,
1037 AIE::ShimDMAAllocationOp output,
1038 AIE::ConsumedByAttr proof) {
1039 auto entry = deviceState.balancedPairs.try_emplace({input, output}, true);
1040 if (entry.second)
1041 entry.first->second = llvm::all_of(
1042 getOperation().getOps<AIE::RuntimeSequenceOp>(),
1043 [&](AIE::RuntimeSequenceOp seq) {
1044 return stretchesUnbalanced(seq, nullptr, proofDevice(proof), input,
1045 output, {input}, {output},
1046 proof) == Unbalanced::No;
1047 });
1048 return entry.first->second;
1049 }
1050
1051 // The device whose array `proof` describes: the one materialization copied
1052 // it from, else this one; none where that device is not in the module.
1053 AIE::DeviceOp proofDevice(AIE::ConsumedByAttr proof) {
1054 FlatSymbolRefAttr device = proof.getDevice();
1055 Operation *module = getOperation()->getParentOp();
1056 if (!device)
1057 return getOperation();
1058 return module ? SymbolTable::lookupNearestSymbolFrom<AIE::DeviceOp>(module,
1059 device)
1060 : AIE::DeviceOp();
1061 }
1062
1063 // The device `load` configures; none where it names none in the module.
1064 AIE::DeviceOp loadedBy(NpuLoadPdiOp load) {
1065 FlatSymbolRefAttr ref = load.getDeviceRefAttr();
1066 Operation *module = getOperation()->getParentOp();
1067 return ref && module ? SymbolTable::lookupNearestSymbolFrom<AIE::DeviceOp>(
1068 module, ref)
1069 : AIE::DeviceOp();
1070 }
1071
1072 // Whether each stretch of `seq` after `from` (all of them when null) with
1073 // `target` loaded ends with the bytes `proof`'s input channel moved covered
1074 // by those its output channel moved. Pushes through `inputs` and `outputs`
1075 // count as the proof's, and with `byChannel` any push on a circuit channel
1076 // (no packet header on it or on `input`/`output`), which carries only that
1077 // route's words; any other on those channels is traffic the proof does not
1078 // describe. Stretches under another PDI end at a real load of `target`.
1079 // `at` receives where the verdict stops, null for the sequence end, and the
1080 // stretch's counts there.
1081 struct Verdict {
1082 Operation *where = nullptr;
1083 Volume in, out;
1084 };
1085 Unbalanced stretchesUnbalanced(
1086 AIE::RuntimeSequenceOp seq, Operation *from, AIE::DeviceOp target,
1087 AIE::ShimDMAAllocationOp input, AIE::ShimDMAAllocationOp output,
1088 ArrayRef<AIE::ShimDMAAllocationOp> inputs,
1089 ArrayRef<AIE::ShimDMAAllocationOp> outputs, AIE::ConsumedByAttr proof,
1090 bool byChannel = false, Verdict *at = nullptr) {
1093 auto fromLoad = dyn_cast_or_null<NpuLoadPdiOp>(from);
1094 AIE::DeviceOp loaded = fromLoad ? loadedBy(fromLoad) : getOperation();
1095 bool counting = !from;
1096 Volume in, out;
1097 Unbalanced why = Unbalanced::No;
1098 seq.walk([&](Operation *op) {
1099 if (op == from) {
1100 counting = true;
1101 return WalkResult::advance();
1102 }
1103 if (!counting)
1104 return WalkResult::advance();
1105 if (auto load = dyn_cast<NpuLoadPdiOp>(op)) {
1106 if (target && loaded == target)
1107 why = balanceUnder(proof, in, out);
1108 if (why != Unbalanced::No) {
1109 if (at)
1110 *at = {op, in, out};
1111 return WalkResult::interrupt();
1112 }
1113 in.clear();
1114 out.clear();
1115 loaded = loadedBy(load);
1116 return WalkResult::advance();
1117 }
1118 if (!target || loaded != target)
1119 return WalkResult::advance();
1120 auto start = dyn_cast<DMAStartTaskOp>(op);
1121 DMAConfigureTaskOp cfg = start ? start.getTaskOp() : nullptr;
1122 auto copy = dyn_cast<NpuDmaMemcpyNdOp>(op);
1123 AIE::ShimDMAAllocationOp allocation =
1124 cfg ? allocationOf(cfg) : allocationOf(copy);
1125 std::optional<DmaQueueModel::ChannelKey> channel;
1126 if (cfg)
1127 channel = DmaQueueModel::keyOf(cfg);
1128 else if (QueueEffect raw = rawQueueEffect(op, *deviceState.symbols);
1129 raw.kind == QueueEffect::Kind::Push)
1130 channel = raw.key;
1131 bool circuit = byChannel && allocation && !allocation.getPacket();
1132 bool isInput =
1133 llvm::is_contained(inputs, allocation) ||
1134 (circuit && channel && *channel == inKey && !input.getPacket());
1135 bool isOutput =
1136 llvm::is_contained(outputs, allocation) ||
1137 (circuit && channel && *channel == outKey && !output.getPacket());
1138 if ((channel && ((*channel == inKey && !isInput) ||
1139 (*channel == outKey && !isOutput))) ||
1140 writesQueue(op, {inKey, outKey})) {
1141 why = Unbalanced::Traffic;
1142 if (at)
1143 *at = {op, in, out};
1144 return WalkResult::interrupt();
1145 }
1146 if (!allocation || (!isInput && !isOutput))
1147 return WalkResult::advance();
1148 // A dynamic-pool sequence keeps its loops, whose trip counts these
1149 // counts cannot follow.
1150 std::optional<Volume> moved = op->getParentOp() != seq ? std::nullopt
1151 : cfg ? pushVolume(start, cfg)
1152 : copyVolume(copy);
1153 if (!moved) {
1154 why = Unbalanced::Unsized;
1155 if (at)
1156 *at = {op, in, out};
1157 return WalkResult::interrupt();
1158 }
1159 for (auto [key, bytes] : *moved)
1160 (isInput ? in : out)[key] += bytes;
1161 return WalkResult::advance();
1162 });
1163 if (why == Unbalanced::No && target && loaded == target)
1164 why = balanceUnder(proof, in, out);
1165 if (at && why != Unbalanced::No && !at->where)
1166 *at = {nullptr, in, out};
1167 return why;
1168 }
1169
1170 // Ending on another device's PDI hands that array on as leavesNothing
1171 // describes, so the last stretch is held to the loaded device's own proofs,
1172 // read off it as seedFromStaticBds reads its BDs: pushes on a proof's
1173 // channels count through the copies materialization stamped with it, and
1174 // any other there is traffic the proof does not describe.
1175 LogicalResult checkForeignTail(AIE::RuntimeSequenceOp seq) {
1176 NpuLoadPdiOp last;
1177 for (auto load : seq.getOps<NpuLoadPdiOp>())
1178 last = load;
1179 AIE::DeviceOp loaded = last ? loadedBy(last) : AIE::DeviceOp();
1180 if (!loaded || loaded == getOperation())
1181 return success();
1182 SmallVector<std::tuple<AIE::ShimDMAAllocationOp, AIE::ShimDMAAllocationOp,
1183 Unbalanced>>
1184 unbalanced;
1185 for (auto input : loaded.getOps<AIE::ShimDMAAllocationOp>()) {
1186 ArrayAttr proofs = input.getConsumedByAttr();
1187 if (!proofs)
1188 continue;
1189 for (auto proof : proofs.getAsRange<AIE::ConsumedByAttr>()) {
1190 auto output = AIE::ShimDMAAllocationOp::getForSymbol(
1191 loaded, proof.getOutput().getValue());
1192 if (!output || proof.getDevice())
1193 continue;
1194 SmallVector<AIE::ShimDMAAllocationOp> inputs, outputs;
1195 for (auto copy : getOperation().getOps<AIE::ShimDMAAllocationOp>()) {
1196 ArrayAttr copied = copy.getConsumedByAttr();
1197 if (!copied ||
1199 continue;
1200 for (auto cp : copied.getAsRange<AIE::ConsumedByAttr>()) {
1201 if (proofDevice(cp) != loaded)
1202 continue;
1203 // NOLINTNEXTLINE(bugprone-unchecked-optional-access)
1204 auto out = deviceState.symbols->lookup<AIE::ShimDMAAllocationOp>(
1205 cp.getOutput().getAttr());
1206 if (out &&
1208 inputs.push_back(copy);
1209 outputs.push_back(out);
1210 }
1211 }
1212 }
1213 Unbalanced why = stretchesUnbalanced(seq, last, loaded, input, output,
1214 inputs, outputs, proof,
1215 /*byChannel=*/true);
1216 if (why != Unbalanced::No)
1217 unbalanced.push_back({input, output, why});
1218 }
1219 }
1220 // Every unbalanced pair, by its channels rather than declaration order.
1221 llvm::stable_sort(unbalanced, [&](const auto &a, const auto &b) {
1222 return std::pair(DmaQueueModel::keyOf(std::get<0>(a)),
1223 DmaQueueModel::keyOf(std::get<1>(a))) <
1224 std::pair(DmaQueueModel::keyOf(std::get<0>(b)),
1225 DmaQueueModel::keyOf(std::get<1>(b)));
1226 });
1227 for (auto [input, output, why] : unbalanced) {
1228 auto diag = last.emitOpError()
1229 << "leaves " << last.getDeviceRefAttr()
1230 << " loaded, and its next dispatch, whose proof that @"
1231 << input.getSymName() << " is consumed by @"
1232 << output.getSymName()
1233 << " counts on a clean start, finds what this "
1234 "sequence's last stretch left: it ";
1235 if (why == Unbalanced::Excess)
1236 diag << "moves more through that input than the output proves "
1237 "taken";
1238 else if (why == Unbalanced::PartGranule)
1239 diag << "may end with the output partway through an object of the "
1240 "join the proof passes";
1241 else if (why == Unbalanced::Traffic)
1242 diag << "has other traffic on their channels";
1243 else
1244 diag << "moves bytes on their channels whose count is not known, "
1245 "so cannot be proven balanced";
1246 diag << ". Balance them before the sequence ends, or load this "
1247 "device's PDI again.";
1248 }
1249 return failure(!unbalanced.empty());
1250 }
1251
1252 // `output`'s pushes up to `order` have finished; see recordConsumption in
1253 // aie-objectfifo-verify for why that finishes its inputs' pushes too.
1254 void creditInputs(AIE::ShimDMAAllocationOp output, uint64_t order) {
1255 auto outPushes = loadState.pushesByAllocation.find(output);
1256 auto proofs = deviceState.proofsByOutput.find(output);
1257 if (outPushes == loadState.pushesByAllocation.end() ||
1258 proofs == deviceState.proofsByOutput.end())
1259 return;
1260 auto byOrder = [](const auto &push, uint64_t bound) {
1261 return push.order < bound;
1262 };
1263 const AllocationPush *done =
1264 llvm::lower_bound(outPushes->second, order, byOrder);
1265 if (done == outPushes->second.end() || done->order != order)
1266 return;
1267 loadState.awaitedThrough[output] = {done->through, pushCount};
1268 if (!done->through)
1269 return;
1270 AIE::DeviceOp configured = opaqueLoad ? AIE::DeviceOp()
1271 : loadedDevice ? loadedDevice
1272 : getOperation();
1273 for (auto [input, proof] : proofs->second) {
1274 if (!configured || proofDevice(proof) != configured)
1275 continue;
1276 auto inPushes = loadState.pushesByAllocation.find(input);
1278 if (inPushes == loadState.pushesByAllocation.end() ||
1279 !leavesNothing(input, output, proof))
1280 continue;
1281 ArrayRef<AllocationPush> pushes = inPushes->second;
1282 size_t &credited = loadState.creditedPushes[{input, output}];
1283 size_t covered = credited;
1284 Volume counted = countedOutput(*done->through, proof);
1285 for (; covered < pushes.size(); ++covered) {
1286 const std::optional<Volume> &through = pushes[covered].through;
1287 if (!through || !atMost(*through, proof.getOutputBytes(), counted,
1288 proof.getInputBytes()))
1289 break;
1290 }
1291 if (covered == credited)
1292 continue;
1293 credited = covered;
1294 auto &tasks = startedOnChannel[key].tasks;
1295 const StartedTask *at =
1296 llvm::lower_bound(tasks, pushes[covered - 1].order, byOrder);
1297 if (at != tasks.end() && at->order == pushes[covered - 1].order)
1298 noteDrained(key, tasks.end() - at - 1);
1299 }
1300 }
1301
1302 // Credit a maskpoll on a channel's status register, whether the queue-depth
1303 // guard, reclaimFor or the design emitted it. A poll bounding the queue size
1304 // by b leaves at most b + 1 unfinished (see getDmaTaskQueueSizeMask); one
1305 // that also clears the running and stall bits leaves none.
1306 void notePoll(NpuMaskPollOp poll) {
1307 std::optional<uint32_t> address = poll.getAbsoluteAddress();
1308 std::optional<uint32_t> mask = getConstantIntOperand(poll.getMask());
1309 std::optional<uint32_t> value = getConstantIntOperand(poll.getValue());
1310 const AIETargetModel &tm =
1311 poll->getParentOfType<AIE::DeviceOp>().getTargetModel();
1312 uint32_t field = tm.getDmaTaskQueueSizeMask();
1313 uint32_t idle = tm.getDmaChannelIdleMask();
1314 if (!address || !mask || !value || !field)
1315 return;
1316 for (const auto &[key, channel] : startedOnChannel) {
1317 if (tm.getDmaStatusAddress(key[0], key[1], key[3],
1318 static_cast<AIE::DMAChannelDir>(key[2])) !=
1319 address)
1320 continue;
1321 if (idle && (*mask & idle) == idle && (*value & idle) == 0)
1322 return noteDrained(key, 0);
1323 unsigned shift = llvm::countr_zero(field);
1324 uint32_t bound = 0;
1325 for (uint32_t size = 0; size <= field >> shift; ++size)
1326 if (((size << shift) & *mask & field) == (*value & *mask & field))
1327 bound = size;
1328 return noteDrained(key, bound + 1);
1329 }
1330 }
1331
1332 // Record ids released without any completion guarantee. nextBdId scans upward
1333 // from 0, so a just-freed low id is the first one handed out again -- the
1334 // worst case for aliasing a BD that is still running.
1335 void noteFreedInFlight(DMAConfigureTaskOp cfg, Operation *freeOp) {
1336 if (!pushCounts.lookup(cfg).started)
1337 return;
1338 AIE::TileOp tile = cfg.getTileOp();
1339 auto &ids = freedInFlight[{tile.getCol(), tile.getRow()}];
1340 cfg.walk([&](AIE::DMABDOp bd) {
1341 if (bd.getBdId().has_value())
1342 ids[bd.getBdId().value()] = {cfg, freeOp};
1343 });
1344 }
1345
1346 // Prints `bytes` scaled by `scale` as "c + k*@param + ...", dropping a zero
1347 // constant unless nothing else would print, and a coefficient of 1.
1348 void printVolume(llvm::raw_ostream &os, const Volume &bytes, int64_t scale,
1349 AIE::RuntimeSequenceOp seq) {
1350 auto constant = bytes.find(-1);
1351 int64_t constantValue =
1352 constant == bytes.end() ? 0 : constant->second * scale;
1353 bool hasTerm = llvm::any_of(
1354 bytes, [](const auto &term) { return term.first >= 0 && term.second; });
1355 bool printed = false;
1356 if (constantValue || !hasTerm) {
1357 os << constantValue;
1358 printed = true;
1359 }
1360 for (const auto &term : bytes) {
1361 if (term.first < 0 || !term.second)
1362 continue;
1363 if (printed)
1364 os << " + ";
1365 int64_t coefficient = term.second * scale;
1366 if (coefficient != 1)
1367 os << coefficient << "*";
1368 printParameter(os, term.first, seq);
1369 printed = true;
1370 }
1371 }
1372
1373 void printParameter(llvm::raw_ostream &os, int64_t index,
1374 AIE::RuntimeSequenceOp seq) {
1375 auto module = getOperation()->getParentOfType<ModuleOp>();
1376 ArrayAttr reads = seq.getScratchpadParametersAttr();
1377 if (module)
1378 for (auto parameter : module.getOps<ScratchpadParameterOp>())
1379 if (parameter.getStateTableIdx() == index &&
1380 (!reads ||
1381 llvm::is_contained(reads.getAsValueRange<FlatSymbolRefAttr>(),
1382 parameter.getSymName()))) {
1383 os << "@" << parameter.getSymName();
1384 return;
1385 }
1386 os << "parameter " << index;
1387 }
1388
1389 // Why no proof shows `task`'s transfer finished, for the unsafe-reuse
1390 // warning: one clause per proof its allocation holds, and the ops they
1391 // point at as notes.
1392 void explainUnproven(DMAConfigureTaskOp task,
1393 SmallVectorImpl<std::string> &why,
1394 SmallVectorImpl<std::pair<Location, std::string>> &at) {
1395 AIE::ShimDMAAllocationOp input = allocationOf(task);
1396 ArrayAttr proofs = input ? input.getConsumedByAttr() : ArrayAttr();
1397 if (!input) {
1398 why.push_back("it names no shim allocation, so no output's progress "
1399 "can prove it consumed");
1400 return;
1401 }
1402 if (!proofs || proofs.empty()) {
1403 std::string clause;
1404 {
1405 llvm::raw_string_ostream os(clause);
1406 os << "aie-objectfifo-verify found no output whose progress proves @"
1407 << input.getSymName() << " consumed";
1408 }
1409 why.push_back(std::move(clause));
1410 return;
1411 }
1412 auto seq = task->getParentOfType<AIE::RuntimeSequenceOp>();
1413 AIE::DeviceOp configured = opaqueLoad ? AIE::DeviceOp()
1414 : loadedDevice ? loadedDevice
1415 : getOperation();
1416 size_t excess = 0;
1417 SmallVector<std::pair<int64_t, AIE::RuntimeSequenceOp>> exceeding;
1418 auto explainProof = [&](AIE::ConsumedByAttr proof, llvm::raw_ostream &os) {
1419 auto output = deviceState.symbols->lookup<AIE::ShimDMAAllocationOp>(
1420 proof.getOutput().getAttr());
1421 os << "through " << proof.getOutput() << ", ";
1422 if (!output) {
1423 os << "that output is not in this device";
1424 return;
1425 }
1426 if (!configured || proofDevice(proof) != configured) {
1427 os << "the proof describes the array of "
1428 << (proof.getDevice()
1429 ? proof.getDevice()
1430 : FlatSymbolRefAttr::get(getOperation().getSymNameAttr()))
1431 << ", which is not the one loaded";
1432 return;
1433 }
1434 if (!leavesNothing(input, output, proof)) {
1435 for (auto other : getOperation().getOps<AIE::RuntimeSequenceOp>()) {
1436 Verdict verdict;
1437 Unbalanced why = stretchesUnbalanced(
1438 other, nullptr, proofDevice(proof), input, output, {input},
1439 {output}, proof, /*byChannel=*/false, &verdict);
1440 Operation *where = verdict.where;
1441 if (why == Unbalanced::No)
1442 continue;
1443 std::string note;
1444 if (why == Unbalanced::Traffic) {
1445 os << "another transfer shares their channels, which the "
1446 "counts do not describe";
1447 note = "the other transfer";
1448 } else if (why == Unbalanced::PartGranule) {
1449 os << "a stretch of @" << other.getSymName()
1450 << " may end with the output partway through an object of "
1451 "the join the proof passes ("
1452 << proof.getGranuleBytes()
1453 << " output bytes), whose later segments it has then taken "
1454 "less of";
1455 note = "the stretch ends here";
1456 } else if (why == Unbalanced::Unsized) {
1457 os << "a transfer on them moves a byte count the compiler "
1458 "cannot follow (a BD chain, a loop, or a length "
1459 "parameter without min_value >= 0)";
1460 note = "the transfer";
1461 } else {
1462 bool scaled = proof.getInputBytes() != proof.getOutputBytes();
1463 os << "a stretch of @" << other.getSymName()
1464 << " can end having moved more through the input than the "
1465 "output proves taken, so the next dispatch's counts do "
1466 "not start clean (input bytes";
1467 if (scaled)
1468 os << " times " << proof.getOutputBytes();
1469 os << ", ";
1470 printVolume(os, verdict.in, proof.getOutputBytes(), other);
1471 os << ", against output bytes";
1472 if (scaled)
1473 os << " times " << proof.getInputBytes();
1474 os << ", ";
1475 printVolume(os, verdict.out, proof.getInputBytes(), other);
1476 os << ")";
1477 ++excess;
1478 for (const auto &term : verdict.in) {
1479 int64_t index = term.first;
1480 auto taken = verdict.out.find(index);
1481 if (index >= 0 &&
1482 term.second * proof.getOutputBytes() >
1483 (taken == verdict.out.end() ? 0 : taken->second) *
1484 proof.getInputBytes() &&
1485 llvm::none_of(exceeding, [&](const auto &seen) {
1486 return seen.first == index;
1487 }))
1488 exceeding.push_back({index, other});
1489 }
1490 note = "the stretch ends here";
1491 }
1492 std::pair<Location, std::string> pointer = {
1493 where ? where->getLoc() : other.getLoc(), note};
1494 if (!llvm::is_contained(at, pointer))
1495 at.push_back(pointer);
1496 return;
1497 }
1498 }
1499 auto pushes = loadState.pushesByAllocation.find(input);
1500 auto order = pushCounts.find(task);
1501 const AllocationPush *push =
1502 pushes == loadState.pushesByAllocation.end() ||
1503 order == pushCounts.end()
1504 ? nullptr
1505 : llvm::find_if(pushes->second, [&](const AllocationPush &p) {
1506 return p.order == order->second.lastPushOrder;
1507 });
1508 if (!push || push == pushes->second.end() || !push->through) {
1509 os << "the bytes the input has moved up to this transfer are not "
1510 "known";
1511 return;
1512 }
1513 auto awaited = loadState.awaitedThrough.find(output);
1514 if (awaited == loadState.awaitedThrough.end()) {
1515 os << "no await on it has retired a transfer yet";
1516 return;
1517 }
1518 if (awaited->second.pushesBefore <= push->order) {
1519 os << "no await on it has retired a transfer since this one was "
1520 "pushed";
1521 return;
1522 }
1523 const std::optional<Volume> &taken = awaited->second.through;
1524 if (!taken) {
1525 os << "the bytes its awaited transfers moved are not known";
1526 return;
1527 }
1528 Volume counted = countedOutput(*taken, proof);
1529 if (atMost(*push->through, proof.getOutputBytes(), counted,
1530 proof.getInputBytes())) {
1531 os << "its awaited transfers cover this transfer's bytes, but "
1532 "not those of every push of this task";
1533 return;
1534 }
1535 bool scaled = proof.getInputBytes() != proof.getOutputBytes();
1536 os << "the bytes its awaited transfers moved";
1537 if (!wholeGranules(*taken, proof.getGranuleBytes()))
1538 os << ", less the part of an object of the join the proof passes ("
1539 << proof.getGranuleBytes() << " bytes) they may end in,";
1540 if (scaled)
1541 os << " times " << proof.getInputBytes();
1542 os << ", ";
1543 printVolume(os, counted, proof.getInputBytes(), seq);
1544 os << ", fall short of the bytes the input moved up to this "
1545 "transfer";
1546 if (scaled)
1547 os << " times " << proof.getOutputBytes();
1548 os << ", ";
1549 printVolume(os, *push->through, proof.getOutputBytes(), seq);
1550 auto isParameter = [](auto term) { return term.first >= 0; };
1551 if (llvm::any_of(counted, isParameter) ||
1552 llvm::any_of(*push->through, isParameter))
1553 os << ", for some parameter values";
1554 };
1555 for (AIE::ConsumedByAttr proof : proofs.getAsRange<AIE::ConsumedByAttr>()) {
1556 std::string clause;
1557 {
1558 llvm::raw_string_ostream os(clause);
1559 explainProof(proof, os);
1560 }
1561 why.push_back(std::move(clause));
1562 }
1563 if (proofs.size() > 1 && excess == proofs.size()) {
1564 std::string clause;
1565 {
1566 llvm::raw_string_ostream os(clause);
1567 os << "no one output's proof covers the input: it moves more than "
1568 "each proves alone";
1569 if (!exceeding.empty()) {
1570 os << ", by how much depending on the runtime parameter";
1571 if (exceeding.size() > 1)
1572 os << "s";
1573 os << " ";
1574 llvm::interleaveComma(exceeding, os, [&](const auto &parameter) {
1575 printParameter(os, parameter.first, parameter.second);
1576 });
1577 }
1578 }
1579 why.push_back(std::move(clause));
1580 }
1581 }
1582
1583 // Warn where the hazard actually bites: reusing the id, not releasing it.
1584 void checkReallocation(AIE::TileOp tile, uint32_t id, Location at) {
1585 if (!warnUnsafeBdReuse)
1586 return;
1587 auto tileIt = freedInFlight.find({tile.getCol(), tile.getRow()});
1588 if (tileIt == freedInFlight.end())
1589 return;
1590 auto idIt = tileIt->second.find(id);
1591 if (idIt == tileIt->second.end())
1592 return;
1593 ReleasedTask released = idIt->second;
1594 tileIt->second.erase(idIt);
1595 if (knownComplete.contains(released.configure) ||
1596 provenFinished.contains(released.configure))
1597 return;
1598 auto [entry, inserted] = unsafeReuses.try_emplace(
1599 at, UnsafeReuse{id, tile.getCol(), tile.getRow(), {}});
1600 UnsafeReuse &reuse = entry->second;
1601 if (inserted)
1602 explainUnproven(released.configure, reuse.why, reuse.notes);
1603 if (!llvm::is_contained(reuse.freeLocs, released.freeOp->getLoc()))
1604 reuse.freeLocs.push_back(released.freeOp->getLoc());
1605 reuse.tiles.insert({tile.getCol(), tile.getRow()});
1606 reuse.count++;
1607 }
1608
1609 // A full ELF inlines a sequence at every call, so one source transfer can
1610 // reuse an id once per call; it is reported once, with how often. Several
1611 // distinct frees can still merge here -- a generated control-packet copy
1612 // and a user task both reusing the id this allocation pass's own location
1613 // names -- so every free actually seen is kept, not just the first.
1614 struct UnsafeReuse {
1615 uint32_t id;
1616 int col, row;
1617 SmallVector<Location> freeLocs;
1618 std::set<std::pair<int, int>> tiles = {};
1619 int64_t count = 0;
1620 SmallVector<std::string> why = {};
1621 SmallVector<std::pair<Location, std::string>> notes = {};
1622 };
1623 llvm::MapVector<Location, UnsafeReuse> unsafeReuses;
1624 // Copies that reprogram a BD id an earlier copy on the tile may still have
1625 // in flight, reported once per copy like unsafeReuses.
1626 struct CopyOverCopy {
1627 int32_t id;
1628 int col, row;
1629 Location earlier;
1630 bool earlierIssuesToken;
1631 std::set<std::pair<int, int>> tiles = {};
1632 int64_t count = 0;
1633 };
1634 llvm::MapVector<Location, CopyOverCopy> copiesOverCopies;
1635
1636 void emitUnsafeReuses() {
1637 for (auto &[loc, reuse] : unsafeReuses) {
1638 // Not bd->emitWarning(): its "see current operation" note verifies and
1639 // numbers the whole device for each warning, quadratic in the sequence.
1640 auto diag =
1641 mlir::emitWarning(loc)
1642 << "reuses buffer descriptor ID " << reuse.id << " on tile ("
1643 << reuse.col << "," << reuse.row
1644 << ") after it was released by an aiex.dma_free_task that had no "
1645 "completion guarantee, so the DMA it belonged to may still be "
1646 "running and this reprograms it underneath. Consume the "
1647 "outstanding tokens on the same tile, direction and channel "
1648 "through a task queued at or after this transfer -- each await "
1649 "consumes the oldest token, regardless of the task it names.";
1650 for (const std::string &why : reuse.why)
1651 diag.attachNote() << "not proven finished: " << why;
1652 for (Location freeLoc : reuse.freeLocs)
1653 diag.attachNote(freeLoc) << "released here";
1654 for (auto &[noteLoc, text] : reuse.notes)
1655 diag.attachNote(noteLoc) << text;
1656 if (reuse.count > 1) {
1657 Diagnostic &note = diag.attachNote();
1658 note << "and " << reuse.count - 1
1659 << " more times from this transfer, on tile"
1660 << (reuse.tiles.size() > 1 ? "s " : " ");
1661 llvm::interleaveComma(reuse.tiles, note, [&](auto tile) {
1662 note << "(" << tile.first << "," << tile.second << ")";
1663 });
1664 }
1665 }
1666 unsafeReuses.clear();
1667 for (auto &[loc, reuse] : copiesOverCopies) {
1668 auto diag = mlir::emitWarning(loc)
1669 << "reuses buffer descriptor ID " << reuse.id << " on tile ("
1670 << reuse.col << "," << reuse.row
1671 << ") while an earlier aiex.npu.dma_memcpy_nd of that ID may "
1672 "still be in flight, so this reprograms it underneath. "
1673 "Give this copy another ID, or retire the earlier copy "
1674 "first: ";
1675 diag << (reuse.earlierIssuesToken ? kWaitForToken : kNoTokenAdvice);
1676 diag.attachNote(reuse.earlier) << "the earlier copy is here";
1677 if (reuse.count > 1) {
1678 Diagnostic &note = diag.attachNote();
1679 note << "and " << reuse.count - 1
1680 << " more times from this copy, on tile"
1681 << (reuse.tiles.size() > 1 ? "s " : " ");
1682 llvm::interleaveComma(reuse.tiles, note, [&](auto tile) {
1683 note << "(" << tile.first << "," << tile.second << ")";
1684 });
1685 }
1686 }
1687 copiesOverCopies.clear();
1688 }
1689
1690 // Configures already completed by an aiex.dma_await_task. Awaiting a task
1691 // returns its BD ids to the pool (like a free), but a subsequent
1692 // aiex.dma_free_task of the same task is the common "wait, then release"
1693 // idiom, not a double free -- so freeing an awaited task's already-returned
1694 // ids is tolerated.
1695 llvm::SmallPtrSet<Operation *, 8> awaitedConfigures;
1696 // Awaited configures whose IDs remain live until their FIFO completion.
1697 llvm::SmallPtrSet<Operation *, 8> pendingAwaitReleases;
1698
1699 // Return the ids of the configure's chain to the pool. `isAwait` records the
1700 // configure so a later free of it is treated as a redundant release rather
1701 // than a double free. Otherwise an already-freed id is a real double free (or
1702 // a free of a task that was never started) and is an error.
1703 LogicalResult recycle(DMAConfigureTaskOp task_op, Operation *freeOp,
1704 bool isAwait) {
1705 pendingAwaitReleases.erase(task_op);
1706 // Those IDs may now belong to another configure. A redundant release must
1707 // not inspect or change the generator's current ownership.
1708 if (awaitedConfigures.contains(task_op) || reclaimed.contains(task_op) ||
1709 unloaded.contains(task_op))
1710 return success();
1711 BdIdGenerator &gen = getGeneratorForTile(task_op.getTileOp());
1712 WalkResult result = task_op.walk<WalkOrder::PreOrder>([&](AIE::DMABDOp bd) {
1713 if (!bd.getBdId().has_value()) {
1714 bd.emitOpError("Free called on BD chain with unassigned IDs.");
1715 return WalkResult::interrupt();
1716 }
1717 if (gen.bdIdAlreadyAssigned(bd.getBdId().value()) &&
1718 !loadState.copyOwned.contains(
1719 {task_op.getTileOp().getTileID(), bd.getBdId().value()})) {
1720 releaseTaskBdId(task_op.getTileOp().getTileID(), gen,
1721 bd.getBdId().value());
1722 } else {
1723 freeOp->emitOpError("frees buffer descriptor ID ")
1724 << bd.getBdId().value()
1725 << ", which is not currently in use; it was already completed by "
1726 "an "
1727 "earlier aiex.dma_free_task or aiex.dma_await_task";
1728 return WalkResult::interrupt();
1729 }
1730 return WalkResult::advance();
1731 });
1732 if (result.wasInterrupted())
1733 return failure();
1734 releasedTasks.insert(task_op);
1735 if (isAwait)
1736 awaitedConfigures.insert(task_op);
1737 else
1738 noteFreedInFlight(task_op, freeOp);
1739 return success();
1740 }
1741
1742 // Resolve a free/await to its configure. In straight-line IR the task value
1743 // is defined directly by the configure op; anything else is an unlowered task
1744 // op.
1745 LogicalResult recycleTask(Value task, Operation *op, bool isAwait) {
1746 auto cfg = dyn_cast_or_null<DMAConfigureTaskOp>(task.getDefiningOp());
1747 if (!cfg) {
1748 auto err = op->emitOpError(
1749 "does not reference a valid configure_task operation.");
1750 if (Operation *def = task.getDefiningOp()) {
1751 if (isa<DMAStartBdChainOp>(def))
1752 err.attachNote(def->getLoc())
1753 << "Lower this operation first using the "
1754 "--aie-materialize-bd-chains pass.";
1755 if (isa<DMAConfigureTaskForOp>(def))
1756 err.attachNote(def->getLoc())
1757 << "Lower this operation first using the "
1758 "--aie-substitute-shim-dma-allocations pass.";
1759 }
1760 return err;
1761 }
1762 if (!isAwait)
1763 return recycle(cfg, op, /*isAwait=*/false);
1764 pendingAwaitReleases.insert(cfg);
1765 return recycleCompletedTasks(op);
1766 }
1767
1768 LogicalResult recycleCompletedTasks(Operation *op) {
1769 SmallVector<Operation *, 8> pending(pendingAwaitReleases.begin(),
1770 pendingAwaitReleases.end());
1771 for (Operation *pendingOp : pending) {
1772 auto pendingCfg = cast<DMAConfigureTaskOp>(pendingOp);
1773 // An earlier await may have named this task while consuming an older
1774 // token. Revisit its release when a later await proves it complete.
1775 if (!knownComplete.contains(pendingCfg))
1776 continue;
1777 // Retain ownership across any remaining starts of the same configure.
1778 if (llvm::any_of(pendingCfg.getResult().getUsers(), [&](Operation *user) {
1779 return isa<DMAStartTaskOp>(user) &&
1780 user->getBlock() == op->getBlock() &&
1781 op->isBeforeInBlock(user);
1782 }))
1783 continue;
1784 if (failed(recycle(pendingCfg, op, /*isAwait=*/true)))
1785 return failure();
1786 }
1787 return success();
1788 }
1789
1790 // Take back the ids of a started task that is not started again after `op`
1791 // and holds an id `op`'s channel can use (on a mem tile, its parity's half).
1792 // One a poll already proved finished is taken as is. Otherwise a poll before
1793 // `op` proves one finished: the oldest with j >= 1 pushes queued behind it,
1794 // for which Task_Queue_Size <= j - 1 is proof (as a masked equality, the
1795 // largest 2^k - 1 <= j - 1), so it waits on no push not yet issued; failing
1796 // that, the oldest, until its channel is idle. A task that acquires a lock
1797 // `op` or a later push releases is never polled for: it cannot finish
1798 // before that push, so the poll would never return. The same dependence
1799 // through a core the compiler cannot see; a design with one releases its own
1800 // BDs.
1801 LogicalResult reclaimFor(DMAConfigureTaskOp op) {
1802 AIE::TileOp tile = op.getTileOp();
1803 const AIETargetModel &tm =
1804 tile->getParentOfType<AIE::DeviceOp>().getTargetModel();
1805 auto isCandidate = [&](DMAConfigureTaskOp task) {
1806 if (releasedTasks.contains(task) || startAfter(task, op))
1807 return false;
1808 bool usable = false;
1809 task.walk([&](AIE::DMABDOp bd) {
1810 usable |= bd.getBdId() &&
1811 tm.isBdChannelAccessible(tile.getCol(), tile.getRow(),
1812 *bd.getBdId(), op.getChannel());
1813 });
1814 return usable;
1815 };
1816 auto take = [&](DMAConfigureTaskOp task) {
1817 BdIdGenerator &gen = getGeneratorForTile(tile);
1818 task.walk([&](AIE::DMABDOp bd) {
1819 releaseTaskBdId(tile.getTileID(), gen, *bd.getBdId());
1820 });
1821 reclaimed.insert(task);
1822 releasedTasks.insert(task);
1823 pendingAwaitReleases.erase(task);
1824 };
1825
1826 ArrayRef<DMAConfigureTaskOp> live = liveByTile[tile.getTileID()];
1827 for (DMAConfigureTaskOp task : live)
1828 if ((knownComplete.contains(task) || provenFinished.contains(task)) &&
1829 isCandidate(task)) {
1830 take(task);
1831 return success();
1832 }
1833
1834 unsigned at = roundState.positionOf.lookup(op);
1835 auto waitsOnLater = [&](DMAConfigureTaskOp task) {
1836 bool waits = false;
1837 task.walk([&](AIE::UseLockOp lock) {
1838 auto last = roundState.lastReleaseOf.find(lock.getLock());
1839 waits |= (lock.acquire() || lock.acquireGE()) &&
1840 last != roundState.lastReleaseOf.end() && last->second >= at;
1841 });
1842 return waits;
1843 };
1844
1845 uint32_t field = tm.getDmaTaskQueueSizeMask();
1846 uint32_t idle = tm.getDmaChannelIdleMask();
1847 DMAConfigureTaskOp victim;
1848 size_t victimQueuedBehind = 0;
1849 uint64_t victimOrder = 0;
1850 for (DMAConfigureTaskOp task : live) {
1851 if (!isCandidate(task) || waitsOnLater(task))
1852 continue;
1854 if (!tm.getDmaStatusAddress(key[0], key[1], key[3],
1855 static_cast<AIE::DMAChannelDir>(key[2])))
1856 continue;
1857 const ChannelPushes &channel = startedOnChannel[key];
1858 ArrayRef<StartedTask> started = channel.tasks;
1859 auto last =
1860 llvm::find_if(llvm::reverse(started),
1861 [&](const StartedTask &s) { return s.task == task; });
1862 size_t queuedBehind = std::distance(started.rbegin(), last);
1863 // Never started, or retired by an await and caught above.
1864 if (last == started.rend() ||
1865 started.size() - 1 - queuedBehind < channel.finished)
1866 continue;
1867 if (queuedBehind == 0 ? !idle : !field)
1868 continue;
1869 // Rule 1 before rule 2, then oldest.
1870 if (victim && std::make_pair(queuedBehind == 0, last->order) >=
1871 std::make_pair(victimQueuedBehind == 0, victimOrder))
1872 continue;
1873 victim = task;
1874 victimQueuedBehind = queuedBehind;
1875 victimOrder = last->order;
1876 }
1877 if (!victim)
1878 return failure();
1879
1881 std::optional<uint32_t> status = tm.getDmaStatusAddress(
1882 key[0], key[1], key[3], static_cast<AIE::DMAChannelDir>(key[2]));
1883 if (!status)
1884 return failure();
1885 uint32_t mask = idle;
1886 size_t unfinished = 0;
1887 if (victimQueuedBehind > 0) {
1888 unsigned shift = llvm::countr_zero(field);
1889 uint32_t bound =
1890 std::min<uint32_t>(llvm::bit_floor(victimQueuedBehind),
1891 llvm::bit_floor((field >> shift) + 1) / 2) -
1892 1;
1893 mask = field & ~(bound << shift);
1894 unfinished = bound + 1;
1895 }
1896 OpBuilder b(op);
1897 auto cst = [&](uint32_t v) {
1898 auto constant = arith::ConstantOp::create(b, op.getLoc(), b.getI32Type(),
1899 b.getI32IntegerAttr(v));
1900 roundState.insertedHere.push_back(constant);
1901 return constant.getResult();
1902 };
1903 Value maskValue = cst(mask);
1904 Value compareValue = cst(0);
1905 Value statusValue = cst(*status);
1906 auto poll = NpuMaskPollOp::create(b, op.getLoc(), statusValue, compareValue,
1907 maskValue,
1908 /*buffer=*/nullptr, /*column=*/nullptr,
1909 /*row=*/nullptr);
1910 roundState.insertedHere.push_back(poll);
1911 SmallVector<int32_t> ids;
1912 victim.walk([&](AIE::DMABDOp bd) { ids.push_back(*bd.getBdId()); });
1913 // Not poll.emitRemark(): its "see current operation" note verifies and
1914 // numbers the whole device for each poll, quadratic in the sequence.
1915 auto remark = mlir::emitRemark(poll.getLoc())
1916 << "tile (" << tile.getCol() << "," << tile.getRow()
1917 << ") has no free buffer descriptor id, so this poll waits "
1918 << (victimQueuedBehind > 0
1919 ? "until the queue behind an earlier task is short "
1920 "enough to prove it finished"
1921 : "until the channel of an earlier task is idle")
1922 << " and takes back its ids ";
1923 llvm::interleaveComma(ids, remark);
1924 remark.attachNote(victim.getLoc()) << "the task it waits for";
1925 noteDrained(key, unfinished);
1926 take(victim);
1927 return success();
1928 }
1929
1930 // All of this is scoped to one runtime sequence. `gens` restarts BD id
1931 // allocation per sequence, so hazard state left over from an earlier one
1932 // describes ids that no longer name the same tasks. freedInFlight is the
1933 // one that bites rather than merely misleads: it holds aiex.dma_free_task
1934 // pointers, and those ops are erased once the sequence that owns them is
1935 // done, so carrying an entry forward leaves a dangling note location.
1936 void resetPerSequenceState() {
1937 gens.clear();
1938 awaitedConfigures.clear();
1939 pendingAwaitReleases.clear();
1940 startedOnChannel.clear();
1941 pushCount = 0;
1942 pushCounts.clear();
1943 knownComplete.clear();
1944 provenFinished.clear();
1945 reclaimed.clear();
1946 releasedTasks.clear();
1947 liveByTile.clear();
1948 freedInFlight.clear();
1949 loadedDevice = {};
1950 opaqueLoad = {};
1951 unloaded.clear();
1952 resetChannels.clear();
1953 loadState = {};
1954 roundState = {};
1955 }
1956
1957 void warnLeaks(AIE::RuntimeSequenceOp sequence) {
1958 if (!warnUnreleasedTransfers)
1959 return;
1960 for (const auto &[key, channel] : startedOnChannel) {
1961 SmallVector<Operation *> outstanding;
1962 for (const StartedTask &push :
1963 llvm::drop_begin(channel.tasks, channel.finished))
1964 if (!push.task || (!releasedTasks.contains(push.task) &&
1965 !unloaded.contains(push.task)))
1966 outstanding.push_back(push.origin);
1967 if (outstanding.empty())
1968 continue;
1969 auto diag = mlir::emitWarning(sequence.getLoc())
1970 << "may exit with " << outstanding.size()
1971 << " DMA transfer(s) neither awaited nor freed on tile ("
1972 << key[0] << "," << key[1] << ") "
1973 << AIE::stringifyDMAChannelDir(
1974 static_cast<AIE::DMAChannelDir>(key[2]))
1975 << " channel " << key[3]
1976 << "; runtime sequences called by aiex.run must finish using "
1977 "their channels before returning. Await completion, or "
1978 "free tasks whose completion is guaranteed indirectly";
1979 diag.attachNote(outstanding.front()->getLoc())
1980 << "first outstanding transfer starts here";
1981 }
1982 }
1983
1984 void runOnOperation() override {
1985 AIE::DeviceOp device = getOperation();
1986 staticBdIds.clear();
1987 loopingStarts.clear();
1988 deviceState = {};
1989 deviceState.symbols.emplace(device);
1990 for (auto input : device.getOps<AIE::ShimDMAAllocationOp>())
1991 if (ArrayAttr proofs = input.getConsumedByAttr())
1992 for (auto proof : proofs.getAsRange<AIE::ConsumedByAttr>())
1993 if (auto output =
1994 deviceState.symbols->lookup<AIE::ShimDMAAllocationOp>(
1995 proof.getOutput().getAttr()))
1996 deviceState.proofsByOutput[output].push_back({input, proof});
1997
1998 WalkResult wr = device.walk([&](AIE::RuntimeSequenceOp seq) -> WalkResult {
1999 if (failed(checkForeignTail(seq)))
2000 return WalkResult::interrupt();
2001 // Skip sequences already handled by the dynamic free-list pool path
2002 // (aie-lower-dynamic-bd-pool): they draw BD ids at runtime via
2003 // dma_bd_pool_pop and keep their scf.for rolled, which the static
2004 // straight-line allocator neither needs to touch nor can validate.
2005 bool dynamicPool = false;
2006 bool hasTasks = false;
2007 bool hasControlFlow = false;
2008 seq.walk([&](Operation *op) {
2009 dynamicPool |= isa<DMABdPoolPopOp>(op);
2010 hasControlFlow |= isa<scf::ForOp, scf::IfOp, scf::WhileOp>(op);
2011 hasTasks |=
2012 isa<DMAConfigureTaskOp, DMAConfigureTaskForOp, DMAStartBdChainOp,
2013 DMAStartTaskOp, DMAAwaitTaskOp, DMAFreeTaskOp>(op);
2014 });
2015 if (dynamicPool || (!hasTasks && hasControlFlow))
2016 return WalkResult::advance();
2017
2018 if (hasTasks && failed(validate(seq)))
2019 return WalkResult::interrupt();
2020
2021 // Straight-line walk. Collect frees to erase after (recycling reads the
2022 // configure the free points at, so erase only once the walk is done).
2023 // This allocation strategy works only for straight-line IR without
2024 // branching or conditionals; the verifier of this pass ensures this is
2025 // the case on the input IR.
2026 SmallVector<DMAFreeTaskOp> frees;
2027 auto visit = [&](Operation *op) -> WalkResult {
2028 if (auto cfg = dyn_cast<DMAConfigureTaskOp>(op)) {
2029 if (failed(allocateConfigure(cfg)))
2030 return WalkResult::interrupt();
2031 } else if (auto start = dyn_cast<DMAStartTaskOp>(op)) {
2032 if (DMAConfigureTaskOp cfg = start.getTaskOp()) {
2033 if (unloaded.contains(cfg)) {
2034 start.emitOpError(
2035 "starts a task configured before an aiex.npu.load_pdi, "
2036 "which reconfigured the array; its buffer descriptor ids "
2037 "may now belong to the loaded device's static DMAs. "
2038 "Configure the task after the load_pdi instead.");
2039 return WalkResult::interrupt();
2040 }
2041 // Only an explicit aiex.dma_free_task releases a task that is
2042 // started again (an await or a reclaim keeps the ids of one that
2043 // is), so this start would push ids that may already describe
2044 // another task's transfer.
2045 if (releasedTasks.contains(cfg)) {
2046 start.emitOpError(
2047 "starts a task whose buffer descriptors an earlier "
2048 "aiex.dma_free_task released; their ids may already be "
2049 "reprogrammed for another task. Free the task after its "
2050 "last start instead.");
2051 return WalkResult::interrupt();
2052 }
2053 if (failed(checkNotBehindLoop(start, cfg)))
2054 return WalkResult::interrupt();
2055 knownComplete.erase(cfg);
2056 provenFinished.erase(cfg);
2057 notePush(DmaQueueModel::keyOf(cfg), cfg,
2058 start.getPushIssueToken(cfg), start, allocationOf(cfg),
2059 pushVolume(start, cfg));
2060 }
2061 } else if (auto load = dyn_cast<NpuLoadPdiOp>(op)) {
2062 noteLoadPdi(load);
2063 } else if (auto reset = dyn_cast<DmaChannelResetOp>(op)) {
2064 resetChannels.insert(DmaQueueModel::keyOf(
2065 reset.getTileOp(), reset.getDirection(), reset.getChannel()));
2066 } else if (auto poll = dyn_cast<NpuMaskPollOp>(op)) {
2067 notePoll(poll);
2068 } else if (auto await = dyn_cast<DMAAwaitTaskOp>(op)) {
2069 if (DMAConfigureTaskOp cfg = await.getTaskOp())
2070 if (cfg.getIssueToken())
2071 noteAwaited(DmaQueueModel::keyOf(cfg));
2072 if (failed(recycleTask(await.getTask(), await, /*isAwait=*/true)))
2073 return WalkResult::interrupt();
2074 } else if (auto freeOp = dyn_cast<DMAFreeTaskOp>(op)) {
2075 if (failed(recycleTask(freeOp.getTask(), freeOp, /*isAwait=*/false)))
2076 return WalkResult::interrupt();
2077 frees.push_back(freeOp);
2078 } else if (QueueEffect raw = rawQueueEffect(op, *deviceState.symbols);
2079 raw.kind == QueueEffect::Kind::Await) {
2080 noteAwaited(raw.key);
2081 if (failed(recycleCompletedTasks(op)))
2082 return WalkResult::interrupt();
2083 } else if (raw.kind == QueueEffect::Kind::Push) {
2084 auto copy = dyn_cast<NpuDmaMemcpyNdOp>(op);
2085 AIE::ShimDMAAllocationOp allocation = allocationOf(copy);
2086 notePush(raw.key, DMAConfigureTaskOp{}, raw.issuesToken, op,
2087 allocation, copy ? copyVolume(copy) : std::nullopt);
2088 if (copy) {
2089 if (failed(holdCopy(copy, raw.key, pushCount - 1, raw.issuesToken)))
2090 return WalkResult::interrupt();
2091 if (roundState.reallocate)
2092 return WalkResult::interrupt();
2093 }
2094 }
2095 return WalkResult::advance();
2096 };
2097 // A copy that meets a task in flight on its id forbids the task that id
2098 // and the sequence is allocated again; each round adds one such pair.
2099 // A round's diagnostics are held until it stands. Other threads' pass
2100 // instances share the context, so only this thread's are held.
2101 forbidden.clear();
2102 auto reusesBefore = unsafeReuses;
2103 auto copiesBefore = copiesOverCopies;
2104 WalkResult r = WalkResult::advance();
2105 std::vector<Diagnostic> held;
2106 for (;;) {
2107 resetPerSequenceState();
2108 // roundState.positionOf/roundState.lastReleaseOf only ever feed
2109 // reclaimFor.
2110 if (reclaimBds)
2111 indexLockReleases(seq);
2112 frees.clear();
2113 held.clear();
2114 {
2115 uint64_t thread = llvm::get_threadid();
2116 ScopedDiagnosticHandler hold(&getContext(), [&](Diagnostic &diag) {
2117 if (llvm::get_threadid() != thread)
2118 return failure();
2119 held.push_back(std::move(diag));
2120 return success();
2121 });
2122 r = seq.walk(visit);
2123 }
2124 if (!roundState.reallocate)
2125 break;
2126 for (AIE::DMABDOp bd : roundState.assignedHere)
2127 bd.removeBdIdAttr();
2128 for (Operation *inserted : llvm::reverse(roundState.insertedHere))
2129 inserted->erase();
2130 unsafeReuses = reusesBefore;
2131 copiesOverCopies = copiesBefore;
2132 }
2133 for (Diagnostic &diag : held)
2134 getContext().getDiagEngine().emit(std::move(diag));
2135 if (r.wasInterrupted())
2136 return WalkResult::interrupt();
2137 warnLeaks(seq);
2138 for (DMAFreeTaskOp freeOp : frees)
2139 freeOp.erase();
2140 return WalkResult::advance();
2141 });
2142 emitUnsafeReuses();
2143 if (wr.wasInterrupted())
2144 return signalPassFailure();
2145 }
2146};
2147
2148} // namespace
2149
2150std::unique_ptr<OperationPass<AIE::DeviceOp>>
2152 return std::make_unique<AIEAssignRuntimeSequenceBDIDsPass>();
2153}
2154
2155std::unique_ptr<OperationPass<AIE::DeviceOp>>
2157 const AIEAssignRuntimeSequenceBDIDsOptions &options) {
2158 return std::make_unique<AIEAssignRuntimeSequenceBDIDsPass>(options);
2159}
static void push(ChannelState &q, bool issuesToken)
Record a push.
static void awaitToken(ChannelState &q)
Retire what a task-completion-token await proves has drained.
std::array< int, 4 > ChannelKey
{col, row, direction, channel}.
static bool wouldOverflow(const ChannelState &q, uint32_t depth)
True when a push would land on a full queue.
static ChannelKey keyOf(AIE::TileOp tile, AIE::DMAChannelDir direction, int64_t channel)
virtual uint32_t getDmaChannelIdleMask() const
Return the bits of the getDmaStatusAddress() register that are all clear exactly when the channel has...
virtual uint32_t getDmaTaskQueueDepth() const =0
Return how many DMA tasks a single channel's task queue holds (unsupported = 0).
virtual bool isBdChannelAccessible(int col, int row, uint32_t bd_id, int channel) const =0
Return true iff buffer descriptor bd_id on tile (col, row) can be submitted on channel channel.
virtual uint32_t getDmaTaskQueueSizeMask() const
Return the mask selecting the live task-queue occupancy field within the getDmaStatusAddress() regist...
uint32_t getDmaQueueAddress(int col, int row, int channel, AIE::DMAChannelDir direction) const
Return the array address of the task queue register a push writes, the word after the channel's contr...
uint32_t getNumBDsForChannel(int col, int row, int channel) const
Return the number of buffer descriptors accessible on channel channel for the tile at (col,...
virtual std::optional< uint32_t > getDmaStatusAddress(int, int, int, AIE::DMAChannelDir) const
Return the address of the DMA status register for a channel, or nullopt when this target's layout has...
QueueEffect rawQueueEffect(mlir::Operation *op, mlir::SymbolTable &symbols)
What a push or an await that names no task does to its channel: an aiex.npu.push_queue; an aiex....
bool atMost(const Volume &a, int64_t scaleA, const Volume &b, int64_t scaleB)
Definition AIEUtils.cpp:354
void guardQueueOverflow(DmaQueueModel &queue, mlir::Operation *push, const AIE::AIETargetModel &tm, const DmaQueueModel::ChannelKey &key, uint32_t depth, bool enforce)
Handle a push on key that would land on a full queue: poll where one can be emitted,...
bool wholeGranules(const Volume &bytes, int64_t granule)
Definition AIEUtils.cpp:371
std::optional< uint32_t > getConstantIntOperand(mlir::Value v)
std::map< int64_t, int64_t > Volume
Definition AIEUtils.h:146
std::unique_ptr< mlir::OperationPass< AIE::DeviceOp > > createAIEAssignRuntimeSequenceBDIDsPass()
Unbalanced balanceUnder(AIE::ConsumedByAttr proof, const Volume &in, const Volume &out)
Definition AIEUtils.cpp:377
struct TileID { friend std::ostream &operator<<(std::ostream &os, const TileID &s) { os<< "TileID("<< s.col<< ", "<< s.row<< ")"; return os; } friend std::string to_string(const TileID &s) { std::ostringstream ss; ss<< s; return ss.str(); } friend llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const TileID &s) { os<< to_string(s); return os; } inline bool operator<(const TileID &rhs) const { return std::tie(col, row)< std::tie(rhs.col, rhs.row); } bool operator==(const TileID &rhs) const { return std::tie(col, row)==std::tie(rhs.col, rhs.row); } bool operator!=(const TileID &rhs) const { return !(*this==rhs);} int col, row;} TileID
llvm::SmallVector< uint32_t > getAssignedBdIds(DmaBody program)
const AIETargetModel & getTargetModel(mlir::Operation *op)
bool bdIdAlreadyAssigned(uint32_t bdId)
void assignBdId(uint32_t bdId)
void freeBdId(uint32_t bdId)
std::optional< uint32_t > nextBdId(int channelIndex, uint32_t alignment=1)