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"
54#define GEN_PASS_DEF_AIEASSIGNRUNTIMESEQUENCEBDIDS
55#include "aie/Dialect/AIEX/Transforms/AIEXPasses.h.inc"
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)
74 llvm::DenseMap<AIE::TileID, BdIdGenerator> gens;
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.";
86 static bool writesQueue(Operation *op,
87 ArrayRef<DmaQueueModel::ChannelKey> keys) {
88 std::optional<uint32_t> first;
90 if (
auto write = dyn_cast<NpuWrite32Op>(op)) {
91 if (write.getBuffer())
93 first = write.getAbsoluteAddress();
94 }
else if (
auto write = dyn_cast<NpuMaskWrite32Op>(op)) {
95 if (write.getBuffer())
97 first = write.getAbsoluteAddress();
98 }
else if (
auto write = dyn_cast<NpuBlockWriteOp>(op)) {
99 if (write.getBuffer())
101 first = write.getAbsoluteAddress();
102 auto data = dyn_cast<MemRefType>(write.getData().getType());
103 if (!data || !data.hasStaticShape())
105 bytes = data.getNumElements() * data.getElementTypeBitWidth() / 8;
111 const AIETargetModel &tm =
115 key[0], key[1], key[3],
static_cast<AIE::DMAChannelDir
>(key[2]));
116 return queue >= *first && queue < *first + bytes;
130 llvm::DenseMap<Operation *,
131 llvm::DenseMap<AIE::TileID, SmallVector<uint32_t>>>
136 void seedFromStaticBds(AIE::DeviceOp device, AIE::TileOp tile,
137 BdIdGenerator &gen) {
138 auto [it, inserted] = staticBdIds.try_emplace(device);
140 for (AIE::DmaBody program : device.getOps<AIE::DmaBody>())
141 llvm::append_range(it->second[program.getTileID()],
143 for (uint32_t
id : it->second.lookup(tile.getTileID()))
151 BdIdGenerator &getGeneratorForTile(AIE::TileOp tile) {
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())})
159 seedFromStaticBds(device, tile, it->second);
160 if (loadedDevice && loadedDevice != device)
161 seedFromStaticBds(loadedDevice, tile, it->second);
167 llvm::DenseMap<Operation *,
168 std::map<DmaQueueModel::ChannelKey, AIE::DMAStartOp>>
171 std::set<DmaQueueModel::ChannelKey> resetChannels;
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;
179 for (AIE::DmaBody program : device.getOps<AIE::DmaBody>()) {
181 program->walk([&](AIE::DMAStartOp start) {
182 if (start.getEndpoint())
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;
189 starts.try_emplace({tile.col, tile.row,
190 static_cast<int>(start.getChannelDir()),
191 start.getChannelIndex()},
201 LogicalResult checkNotBehindLoop(DMAStartTaskOp start,
202 DMAConfigureTaskOp cfg) {
206 if (resetChannels.count(key))
209 loopingStartsOf(loadedDevice ? loadedDevice : getOperation());
210 auto it = starts.find(key);
211 if (it == starts.end())
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";
225 AIE::DeviceOp loadedDevice;
227 NpuLoadPdiOp opaqueLoad;
229 llvm::SmallPtrSet<Operation *, 16> unloaded;
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);
242 pendingAwaitReleases.clear();
243 freedInFlight.clear();
250 LogicalResult rejectRuntimeControlFlow(AIE::RuntimeSequenceOp seq) {
251 WalkResult wr = seq.walk([&](Operation *op) -> WalkResult {
252 if (isa<scf::ForOp, scf::IfOp, scf::WhileOp>(op)) {
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();
261 return WalkResult::advance();
263 return failure(wr.wasInterrupted());
277 LogicalResult verifyChannelUsage(AIE::RuntimeSequenceOp seq) {
280 const AIETargetModel &tm =
283 std::map<ChannelKey, int> avail;
286 WalkResult wr = seq.walk([&](Operation *op) -> WalkResult {
287 if (
auto start = dyn_cast<DMAStartTaskOp>(op)) {
288 DMAConfigureTaskOp cfg = start.getTaskOp();
290 return WalkResult::advance();
292 AIE::TileOp tile = cfg.getTileOp();
294 tile.getCol(), tile.getRow(), cfg.getChannel(), cfg.getDirection());
297 bool issuesToken = start.getPushIssueToken(cfg);
298 queue.
push(key, issuesToken);
301 }
else if (
auto await = dyn_cast<DMAAwaitTaskOp>(op)) {
302 DMAConfigureTaskOp cfg = await.getTaskOp();
305 if (!cfg || !cfg.getIssueToken())
306 return WalkResult::advance();
308 int &tokens = avail[key];
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();
320 }
else if (QueueEffect raw =
rawQueueEffect(op, *deviceState.symbols);
321 raw.
kind == QueueEffect::Kind::Await) {
325 avail[raw.key] = std::max(0, avail[raw.key] - 1);
327 }
else if (raw.kind == QueueEffect::Kind::Push) {
328 avail[raw.key] += raw.issuesToken;
329 queue.
push(raw.key, raw.issuesToken);
331 return WalkResult::advance();
333 return failure(wr.wasInterrupted());
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();
344 if (unplaced.wasInterrupted())
348 if (failed(rejectRuntimeControlFlow(seq)))
350 if (failed(verifyChannelUsage(seq)))
355 LogicalResult allocateConfigure(DMAConfigureTaskOp op) {
356 AIE::TileOp tile = op.getTileOp();
357 BdIdGenerator &gen = getGeneratorForTile(tile);
359 const AIETargetModel &targetModel =
363 WalkResult result = op.walk<WalkOrder::PreOrder>([&](AIE::DMABDOp bd_op) {
364 if (bd_op.getBdId().has_value()) {
366 bd_op.getBdId().value(),
368 bd_op.emitOpError(
"Buffer descriptor ID ")
369 << bd_op.getBdId().value() <<
" cannot be submitted on channel "
370 << op.getChannel() <<
" of tile (" << tile.getCol() <<
","
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();
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();
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();
400 checkReallocation(tile, bd_op.getBdId().value(), bd_op.getLoc());
403 return WalkResult::advance();
405 if (result.wasInterrupted())
408 AIE::DMABDOp head = op.getFirstBd();
409 uint32_t headAlignment = DMAStartTaskOp::headBdIdAlignment(op.getResult());
413 SmallVector<int32_t> blocked;
415 auto it = forbidden.find(op);
416 if (it == forbidden.end())
418 for (
auto [
id, copy] : it->second)
421 blocked.push_back(
id);
425 unsigned tookBack = 0;
428 result = op.walk<WalkOrder::PreOrder>([&](AIE::DMABDOp bd_op) {
429 if (bd_op.getBdId().has_value())
430 return WalkResult::advance();
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 "
439 .attachNote(opaqueLoad.getLoc())
440 <<
"the PDI is loaded here";
441 return WalkResult::interrupt();
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))) {
451 next_id = gen.
nextBdId(op.getChannel(), alignment);
456 <<
"Too many simultaneously active buffer descriptors on tile ("
457 << tile.getCol() <<
"," << tile.getRow()
458 <<
"), which supports up to "
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() &&
470 id, op.getChannel()))
472 {id, copyHolding(tile.getTileID(),
id)->copy,
false});
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).";
484 bool otherLiveTask = llvm::any_of(
485 liveByTile[tile.getTileID()],
486 [&](DMAConfigureTaskOp t) { return !releasedTasks.contains(t); });
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.";
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.";
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 "
516 for (
auto [
id, copyOp, isForbidden] : copied) {
517 auto copy = cast<NpuDmaMemcpyNdOp>(copyOp);
518 Diagnostic ¬e = 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: ");
527 return WalkResult::interrupt();
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();
534 for (int32_t
id : blocked)
536 if (result.wasInterrupted())
539 liveByTile[tile.getTileID()].push_back(op);
547 DMAConfigureTaskOp task;
557 struct ChannelPushes {
558 SmallVector<StartedTask, 8> tasks;
561 std::map<DmaQueueModel::ChannelKey, ChannelPushes> startedOnChannel;
562 uint64_t pushCount = 0;
567 unsigned started = 0;
568 unsigned running = 0;
569 uint64_t lastPushOrder = 0;
571 llvm::DenseMap<Operation *, PushCounts> pushCounts;
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});
580 PushCounts &counts = pushCounts[task];
583 counts.lastPushOrder = order;
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;
594 through = std::nullopt;
595 pushes.push_back({order, through});
598 llvm::SmallPtrSet<Operation *, 16> knownComplete;
602 llvm::SmallPtrSet<Operation *, 16> provenFinished;
604 llvm::SmallPtrSet<Operation *, 16> reclaimed;
606 llvm::SmallPtrSet<Operation *, 16> releasedTasks;
613 llvm::DenseMap<Operation *, unsigned> positionOf;
614 llvm::DenseMap<Value, unsigned> lastReleaseOf;
615 bool reallocate =
false;
617 SmallVector<AIE::DMABDOp> assignedHere;
618 SmallVector<Operation *> insertedHere;
620 RoundState roundState;
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();
631 cfg.walk([&](AIE::UseLockOp lock) {
633 roundState.lastReleaseOf[lock.getLock()] = roundState.positionOf[&op];
639 llvm::DenseMap<AIE::TileID, SmallVector<DMAConfigureTaskOp, 16>> liveByTile;
650 using TileBdId = std::pair<AIE::TileID, int32_t>;
652 NpuDmaMemcpyNdOp copy;
657 llvm::DenseMap<Operation *, SmallVector<std::pair<int32_t, Operation *>>>
661 const HeldBy *copyHolding(
AIE::TileID tile, int32_t
id)
const {
662 if (!loadState.copyOwned.contains({tile, id}))
664 return &loadState.holdsOn.find({tile,
id})->second.begin()->second;
668 void releaseTaskBdId(
AIE::TileID tile, BdIdGenerator &gen, int32_t
id) {
670 if (!loadState.holdsOn.contains({tile, id}))
673 loadState.copyOwned.insert({tile,
id});
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)))
689 LogicalResult holdCopy(NpuDmaMemcpyNdOp copy,
692 AIE::TileOp tile = allocationOf(copy).getTileOp();
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(
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++;
705 BdIdGenerator &gen = getGeneratorForTile(tile);
706 loadState.holdsByChannel[key].push_back({order, tileId,
id});
707 loadState.holdsOn[{tileId,
id}][order] = {copy, issuesToken};
709 checkReallocation(tile,
id, copy.getLoc());
711 loadState.copyOwned.insert({tileId,
id});
714 if (loadState.copyOwned.contains({tileId, id}))
716 for (DMAConfigureTaskOp task : liveByTile[tileId]) {
717 if (releasedTasks.contains(task) || unloaded.contains(task))
720 task.walk([&](AIE::DMABDOp bd) {
721 if (bd.getBdId() ==
id)
726 bool running = pushCounts.lookup(task).running;
729 bool everStarted = pushCounts.contains(task);
730 DMAStartTaskOp restart = startAfter(task, copy);
731 if (!running && !restart)
733 if (!llvm::is_contained(roundState.assignedHere, held)) {
734 InFlightDiagnostic diag =
735 task.emitOpError(
"Specified buffer descriptor ID ") << id;
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.";
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 "
751 diag.attachNote(copy.getLoc()) <<
"the copy is here";
753 diag.attachNote(restart.getLoc())
754 << (everStarted ?
"the task is started again here"
755 :
"the task starts here, after the copy");
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;
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})
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";
786 auto holds = loadState.holdsByChannel.find(key);
787 if (holds == loadState.holdsByChannel.end())
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())
801 loadState.holdsOn.erase(on);
802 if (loadState.copyOwned.erase({hold.tile, hold.id}))
803 gens.find(hold.tile)->second.freeBdId(hold.id);
809 struct ReleasedTask {
810 DMAConfigureTaskOp configure;
813 std::map<std::pair<int, int>, std::map<uint32_t, ReleasedTask>> freedInFlight;
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())
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;
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);
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);
858 ChannelPushes &channel = startedOnChannel[key];
859 if (channel.tasks.size() <= unfinished)
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);
872 AIE::ConsumedByAttr proof) {
873 int64_t granule = proof.getGranuleBytes();
874 Volume counted = received;
876 counted[-1] -= granule - 1;
884 bool nonNegative(AIE::RuntimeSequenceOp seq, int64_t index) {
885 auto [it, inserted] = deviceState.nonNegativeByIndex.try_emplace(
886 {seq.getOperation(), index},
false);
889 auto module = getOperation()->getParentOfType<ModuleOp>();
892 ArrayAttr reads = seq.getScratchpadParametersAttr();
893 bool found =
false, held =
true;
894 for (
auto parameter : module.getOps<ScratchpadParameterOp>()) {
895 if (parameter.getStateTableIdx() != index ||
897 !llvm::is_contained(reads.getAsValueRange<FlatSymbolRefAttr>(),
898 parameter.getSymName())))
900 std::optional<int32_t> min = parameter.getMinValue();
902 held &= min && *min >= 0;
904 it->second = found && held;
911 std::optional<Volume> pushVolume(DMAStartTaskOp start,
912 DMAConfigureTaskOp cfg) {
913 std::optional<int64_t> repeat =
914 start.hasRepeatParameter()
916 : getConstantIntValue(start.getPushRepeatCount(cfg));
917 Region &body = cfg.getBody();
918 if (!repeat || *repeat < 0 || body.empty())
921 llvm::SmallPtrSet<Block *, 8> seen;
922 for (Block *block = &body.front(); block;) {
923 if (!seen.insert(block).second)
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())
930 int64_t width = bd.getBufferElementTypeWidthInBytes();
932 if (std::optional<uint8_t> index = bd.getLengthStateTableIdx()) {
933 std::optional<int32_t> unit = bd.getLengthUnit();
935 !nonNegative(start->getParentOfType<AIE::RuntimeSequenceOp>(),
938 bytes[*index] +=
static_cast<int64_t
>(*unit) * width;
941 auto next = dyn_cast<AIE::NextBDOp>(block->getTerminator());
942 block = next ? next.getDest() :
nullptr;
944 for (
auto &[key, coefficient] : bytes)
945 if (llvm::MulOverflow(coefficient, *repeat + 1, coefficient))
952 static std::optional<Volume> copyVolume(NpuDmaMemcpyNdOp copy) {
953 std::optional<int64_t> bytes = copy.getStaticBytesStreamed();
967 std::optional<SymbolTable> symbols;
971 SmallVector<std::pair<AIE::ShimDMAAllocationOp, AIE::ConsumedByAttr>>>
976 llvm::DenseMap<std::pair<Operation *, Operation *>,
bool> balancedPairs;
978 llvm::DenseMap<std::pair<Operation *, int64_t>,
bool> nonNegativeByIndex;
980 DeviceState deviceState;
983 AIE::ShimDMAAllocationOp allocationOf(DMAConfigureTaskOp cfg) {
984 FlatSymbolRefAttr alloc = cfg.getAllocAttr();
986 return alloc ? deviceState.symbols->lookup<AIE::ShimDMAAllocationOp>(
992 AIE::ShimDMAAllocationOp allocationOf(NpuDmaMemcpyNdOp copy) {
996 return deviceState.symbols->lookup<AIE::ShimDMAAllocationOp>(
997 copy.getMetadata().getRootReference());
1003 struct AllocationPush {
1005 std::optional<Volume> through;
1011 std::optional<Volume> through;
1012 uint64_t pushesBefore;
1017 llvm::DenseMap<Operation *, SmallVector<AllocationPush>> pushesByAllocation;
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;
1026 LoadState loadState;
1036 bool leavesNothing(AIE::ShimDMAAllocationOp input,
1037 AIE::ShimDMAAllocationOp output,
1038 AIE::ConsumedByAttr proof) {
1039 auto entry = deviceState.balancedPairs.try_emplace({input, output},
true);
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;
1048 return entry.first->second;
1053 AIE::DeviceOp proofDevice(AIE::ConsumedByAttr proof) {
1054 FlatSymbolRefAttr device = proof.getDevice();
1055 Operation *module = getOperation()->getParentOp();
1057 return getOperation();
1058 return module ? SymbolTable::lookupNearestSymbolFrom<AIE::DeviceOp>(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>(
1082 Operation *where =
nullptr;
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;
1098 seq.walk([&](Operation *op) {
1101 return WalkResult::advance();
1104 return WalkResult::advance();
1105 if (
auto load = dyn_cast<NpuLoadPdiOp>(op)) {
1106 if (target && loaded == target)
1108 if (why != Unbalanced::No) {
1110 *at = {op, in, out};
1111 return WalkResult::interrupt();
1115 loaded = loadedBy(load);
1116 return WalkResult::advance();
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;
1128 else if (QueueEffect raw =
rawQueueEffect(op, *deviceState.symbols);
1129 raw.
kind == QueueEffect::Kind::Push)
1131 bool circuit = byChannel && allocation && !allocation.getPacket();
1133 llvm::is_contained(inputs, allocation) ||
1134 (circuit && channel && *channel == inKey && !input.getPacket());
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;
1143 *at = {op, in, out};
1144 return WalkResult::interrupt();
1146 if (!allocation || (!isInput && !isOutput))
1147 return WalkResult::advance();
1150 std::optional<Volume> moved = op->getParentOp() != seq ? std::nullopt
1151 : cfg ? pushVolume(start, cfg)
1154 why = Unbalanced::Unsized;
1156 *at = {op, in, out};
1157 return WalkResult::interrupt();
1159 for (
auto [key, bytes] : *moved)
1160 (isInput ? in : out)[key] += bytes;
1161 return WalkResult::advance();
1163 if (why == Unbalanced::No && target && loaded == target)
1165 if (at && why != Unbalanced::No && !at->where)
1166 *at = {
nullptr, in, out};
1175 LogicalResult checkForeignTail(AIE::RuntimeSequenceOp seq) {
1177 for (
auto load : seq.getOps<NpuLoadPdiOp>())
1179 AIE::DeviceOp loaded = last ? loadedBy(last) : AIE::DeviceOp();
1180 if (!loaded || loaded == getOperation())
1182 SmallVector<std::tuple<AIE::ShimDMAAllocationOp, AIE::ShimDMAAllocationOp,
1185 for (
auto input : loaded.getOps<AIE::ShimDMAAllocationOp>()) {
1186 ArrayAttr proofs = input.getConsumedByAttr();
1189 for (
auto proof : proofs.getAsRange<AIE::ConsumedByAttr>()) {
1190 auto output = AIE::ShimDMAAllocationOp::getForSymbol(
1191 loaded, proof.getOutput().getValue());
1192 if (!output || proof.getDevice())
1194 SmallVector<AIE::ShimDMAAllocationOp> inputs, outputs;
1195 for (
auto copy : getOperation().getOps<AIE::ShimDMAAllocationOp>()) {
1196 ArrayAttr copied = copy.getConsumedByAttr();
1200 for (
auto cp : copied.getAsRange<AIE::ConsumedByAttr>()) {
1201 if (proofDevice(cp) != loaded)
1204 auto out = deviceState.symbols->lookup<AIE::ShimDMAAllocationOp>(
1205 cp.getOutput().getAttr());
1208 inputs.push_back(copy);
1209 outputs.push_back(out);
1213 Unbalanced why = stretchesUnbalanced(seq, last, loaded, input, output,
1214 inputs, outputs, proof,
1216 if (why != Unbalanced::No)
1217 unbalanced.push_back({input, output, why});
1221 llvm::stable_sort(unbalanced, [&](
const auto &a,
const auto &b) {
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 "
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";
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.";
1249 return failure(!unbalanced.empty());
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())
1260 auto byOrder = [](
const auto &push, uint64_t bound) {
1261 return push.order < bound;
1263 const AllocationPush *done =
1264 llvm::lower_bound(outPushes->second, order, byOrder);
1265 if (done == outPushes->second.end() || done->order != order)
1267 loadState.awaitedThrough[output] = {done->through, pushCount};
1270 AIE::DeviceOp configured = opaqueLoad ? AIE::DeviceOp()
1271 : loadedDevice ? loadedDevice
1273 for (
auto [input, proof] : proofs->second) {
1274 if (!configured || proofDevice(proof) != configured)
1276 auto inPushes = loadState.pushesByAllocation.find(input);
1278 if (inPushes == loadState.pushesByAllocation.end() ||
1279 !leavesNothing(input, output, proof))
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()))
1291 if (covered == credited)
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);
1306 void notePoll(NpuMaskPollOp poll) {
1307 std::optional<uint32_t> address = poll.getAbsoluteAddress();
1310 const AIETargetModel &tm =
1314 if (!address || !mask || !value || !field)
1316 for (
const auto &[key, channel] : startedOnChannel) {
1318 static_cast<AIE::DMAChannelDir
>(key[2])) !=
1321 if (idle && (*mask & idle) == idle && (*value & idle) == 0)
1322 return noteDrained(key, 0);
1323 unsigned shift = llvm::countr_zero(field);
1325 for (uint32_t size = 0; size <= field >> shift; ++size)
1326 if (((size << shift) & *mask & field) == (*value & *mask & field))
1328 return noteDrained(key, bound + 1);
1335 void noteFreedInFlight(DMAConfigureTaskOp cfg, Operation *freeOp) {
1336 if (!pushCounts.lookup(cfg).started)
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};
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;
1360 for (
const auto &term : bytes) {
1361 if (term.first < 0 || !term.second)
1365 int64_t coefficient = term.second * scale;
1366 if (coefficient != 1)
1367 os << coefficient <<
"*";
1368 printParameter(os, term.first, seq);
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();
1378 for (
auto parameter : module.getOps<ScratchpadParameterOp>())
1379 if (parameter.getStateTableIdx() == index &&
1381 llvm::is_contained(reads.getAsValueRange<FlatSymbolRefAttr>(),
1382 parameter.getSymName()))) {
1383 os <<
"@" << parameter.getSymName();
1386 os <<
"parameter " << index;
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();
1398 why.push_back(
"it names no shim allocation, so no output's progress "
1399 "can prove it consumed");
1402 if (!proofs || proofs.empty()) {
1405 llvm::raw_string_ostream os(clause);
1406 os <<
"aie-objectfifo-verify found no output whose progress proves @"
1407 << input.getSymName() <<
" consumed";
1409 why.push_back(std::move(clause));
1412 auto seq = task->getParentOfType<AIE::RuntimeSequenceOp>();
1413 AIE::DeviceOp configured = opaqueLoad ? AIE::DeviceOp()
1414 : loadedDevice ? loadedDevice
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() <<
", ";
1423 os <<
"that output is not in this device";
1426 if (!configured || proofDevice(proof) != configured) {
1427 os <<
"the proof describes the array of "
1428 << (proof.getDevice()
1430 : FlatSymbolRefAttr::get(getOperation().getSymNameAttr()))
1431 <<
", which is not the one loaded";
1434 if (!leavesNothing(input, output, proof)) {
1435 for (
auto other : getOperation().getOps<AIE::RuntimeSequenceOp>()) {
1438 other,
nullptr, proofDevice(proof), input, output, {input},
1439 {output}, proof,
false, &verdict);
1440 Operation *where = verdict.where;
1441 if (why == Unbalanced::No)
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 "
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";
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";
1468 os <<
" times " << proof.getOutputBytes();
1470 printVolume(os, verdict.in, proof.getOutputBytes(), other);
1471 os <<
", against output bytes";
1473 os <<
" times " << proof.getInputBytes();
1475 printVolume(os, verdict.out, proof.getInputBytes(), other);
1478 for (
const auto &term : verdict.in) {
1479 int64_t index = term.first;
1480 auto taken = verdict.out.find(index);
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;
1488 exceeding.push_back({index, other});
1490 note =
"the stretch ends here";
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);
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()
1505 : llvm::find_if(pushes->second, [&](
const AllocationPush &p) {
1506 return p.order == order->second.lastPushOrder;
1508 if (!push || push == pushes->second.end() || !push->through) {
1509 os <<
"the bytes the input has moved up to this transfer are not "
1513 auto awaited = loadState.awaitedThrough.find(output);
1514 if (awaited == loadState.awaitedThrough.end()) {
1515 os <<
"no await on it has retired a transfer yet";
1518 if (awaited->second.pushesBefore <= push->order) {
1519 os <<
"no await on it has retired a transfer since this one was "
1523 const std::optional<Volume> &taken = awaited->second.through;
1525 os <<
"the bytes its awaited transfers moved are not known";
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";
1535 bool scaled = proof.getInputBytes() != proof.getOutputBytes();
1536 os <<
"the bytes its awaited transfers moved";
1538 os <<
", less the part of an object of the join the proof passes ("
1539 << proof.getGranuleBytes() <<
" bytes) they may end in,";
1541 os <<
" times " << proof.getInputBytes();
1543 printVolume(os, counted, proof.getInputBytes(), seq);
1544 os <<
", fall short of the bytes the input moved up to this "
1547 os <<
" times " << proof.getOutputBytes();
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";
1555 for (AIE::ConsumedByAttr proof : proofs.getAsRange<AIE::ConsumedByAttr>()) {
1558 llvm::raw_string_ostream os(clause);
1559 explainProof(proof, os);
1561 why.push_back(std::move(clause));
1563 if (proofs.size() > 1 && excess == proofs.size()) {
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)
1574 llvm::interleaveComma(exceeding, os, [&](
const auto ¶meter) {
1575 printParameter(os, parameter.first, parameter.second);
1579 why.push_back(std::move(clause));
1584 void checkReallocation(AIE::TileOp tile, uint32_t
id, Location at) {
1585 if (!warnUnsafeBdReuse)
1587 auto tileIt = freedInFlight.find({tile.getCol(), tile.getRow()});
1588 if (tileIt == freedInFlight.end())
1590 auto idIt = tileIt->second.find(
id);
1591 if (idIt == tileIt->second.end())
1593 ReleasedTask released = idIt->second;
1594 tileIt->second.erase(idIt);
1595 if (knownComplete.contains(released.configure) ||
1596 provenFinished.contains(released.configure))
1598 auto [entry, inserted] = unsafeReuses.try_emplace(
1599 at, UnsafeReuse{id, tile.getCol(), tile.getRow(), {}});
1600 UnsafeReuse &reuse = entry->second;
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()});
1614 struct UnsafeReuse {
1617 SmallVector<Location> freeLocs;
1618 std::set<std::pair<int, int>> tiles = {};
1620 SmallVector<std::string> why = {};
1621 SmallVector<std::pair<Location, std::string>> notes = {};
1623 llvm::MapVector<Location, UnsafeReuse> unsafeReuses;
1626 struct CopyOverCopy {
1630 bool earlierIssuesToken;
1631 std::set<std::pair<int, int>> tiles = {};
1634 llvm::MapVector<Location, CopyOverCopy> copiesOverCopies;
1636 void emitUnsafeReuses() {
1637 for (
auto &[loc, reuse] : unsafeReuses) {
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 ¬e = 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 <<
")";
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 "
1675 diag << (reuse.earlierIssuesToken ? kWaitForToken : kNoTokenAdvice);
1676 diag.attachNote(reuse.earlier) <<
"the earlier copy is here";
1677 if (reuse.count > 1) {
1678 Diagnostic ¬e = 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 <<
")";
1687 copiesOverCopies.clear();
1695 llvm::SmallPtrSet<Operation *, 8> awaitedConfigures;
1697 llvm::SmallPtrSet<Operation *, 8> pendingAwaitReleases;
1703 LogicalResult recycle(DMAConfigureTaskOp task_op, Operation *freeOp,
1705 pendingAwaitReleases.erase(task_op);
1708 if (awaitedConfigures.contains(task_op) || reclaimed.contains(task_op) ||
1709 unloaded.contains(task_op))
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();
1718 !loadState.copyOwned.contains(
1719 {task_op.getTileOp().getTileID(), bd.getBdId().value()})) {
1720 releaseTaskBdId(task_op.getTileOp().getTileID(), gen,
1721 bd.getBdId().value());
1723 freeOp->emitOpError(
"frees buffer descriptor ID ")
1724 << bd.getBdId().value()
1725 <<
", which is not currently in use; it was already completed by "
1727 "earlier aiex.dma_free_task or aiex.dma_await_task";
1728 return WalkResult::interrupt();
1730 return WalkResult::advance();
1732 if (result.wasInterrupted())
1734 releasedTasks.insert(task_op);
1736 awaitedConfigures.insert(task_op);
1738 noteFreedInFlight(task_op, freeOp);
1745 LogicalResult recycleTask(Value task, Operation *op,
bool isAwait) {
1746 auto cfg = dyn_cast_or_null<DMAConfigureTaskOp>(task.getDefiningOp());
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.";
1763 return recycle(cfg, op,
false);
1764 pendingAwaitReleases.insert(cfg);
1765 return recycleCompletedTasks(op);
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);
1775 if (!knownComplete.contains(pendingCfg))
1778 if (llvm::any_of(pendingCfg.getResult().getUsers(), [&](Operation *user) {
1779 return isa<DMAStartTaskOp>(user) &&
1780 user->getBlock() == op->getBlock() &&
1781 op->isBeforeInBlock(user);
1784 if (failed(recycle(pendingCfg, op,
true)))
1801 LogicalResult reclaimFor(DMAConfigureTaskOp op) {
1802 AIE::TileOp tile = op.getTileOp();
1803 const AIETargetModel &tm =
1805 auto isCandidate = [&](DMAConfigureTaskOp task) {
1806 if (releasedTasks.contains(task) || startAfter(task, op))
1808 bool usable =
false;
1809 task.walk([&](AIE::DMABDOp bd) {
1810 usable |= bd.getBdId() &&
1812 *bd.getBdId(), op.getChannel());
1816 auto take = [&](DMAConfigureTaskOp task) {
1817 BdIdGenerator &gen = getGeneratorForTile(tile);
1818 task.walk([&](AIE::DMABDOp bd) {
1819 releaseTaskBdId(tile.getTileID(), gen, *bd.getBdId());
1821 reclaimed.insert(task);
1822 releasedTasks.insert(task);
1823 pendingAwaitReleases.erase(task);
1826 ArrayRef<DMAConfigureTaskOp> live = liveByTile[tile.getTileID()];
1827 for (DMAConfigureTaskOp task : live)
1828 if ((knownComplete.contains(task) || provenFinished.contains(task)) &&
1829 isCandidate(task)) {
1834 unsigned at = roundState.positionOf.lookup(op);
1835 auto waitsOnLater = [&](DMAConfigureTaskOp task) {
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;
1847 DMAConfigureTaskOp victim;
1848 size_t victimQueuedBehind = 0;
1849 uint64_t victimOrder = 0;
1850 for (DMAConfigureTaskOp task : live) {
1851 if (!isCandidate(task) || waitsOnLater(task))
1855 static_cast<AIE::DMAChannelDir
>(key[2])))
1857 const ChannelPushes &channel = startedOnChannel[key];
1858 ArrayRef<StartedTask> started = channel.tasks;
1860 llvm::find_if(llvm::reverse(started),
1861 [&](
const StartedTask &s) {
return s.task == task; });
1862 size_t queuedBehind = std::distance(started.rbegin(), last);
1864 if (last == started.rend() ||
1865 started.size() - 1 - queuedBehind < channel.finished)
1867 if (queuedBehind == 0 ? !idle : !field)
1870 if (victim && std::make_pair(queuedBehind == 0, last->order) >=
1871 std::make_pair(victimQueuedBehind == 0, victimOrder))
1874 victimQueuedBehind = queuedBehind;
1875 victimOrder = last->order;
1882 key[0], key[1], key[3],
static_cast<AIE::DMAChannelDir
>(key[2]));
1885 uint32_t mask = idle;
1886 size_t unfinished = 0;
1887 if (victimQueuedBehind > 0) {
1888 unsigned shift = llvm::countr_zero(field);
1890 std::min<uint32_t>(llvm::bit_floor(victimQueuedBehind),
1891 llvm::bit_floor((field >> shift) + 1) / 2) -
1893 mask = field & ~(bound << shift);
1894 unfinished = bound + 1;
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();
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,
1910 roundState.insertedHere.push_back(poll);
1911 SmallVector<int32_t> ids;
1912 victim.walk([&](AIE::DMABDOp bd) { ids.push_back(*bd.getBdId()); });
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);
1936 void resetPerSequenceState() {
1938 awaitedConfigures.clear();
1939 pendingAwaitReleases.clear();
1940 startedOnChannel.clear();
1943 knownComplete.clear();
1944 provenFinished.clear();
1946 releasedTasks.clear();
1948 freedInFlight.clear();
1952 resetChannels.clear();
1957 void warnLeaks(AIE::RuntimeSequenceOp sequence) {
1958 if (!warnUnreleasedTransfers)
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())
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";
1984 void runOnOperation()
override {
1985 AIE::DeviceOp device = getOperation();
1986 staticBdIds.clear();
1987 loopingStarts.clear();
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>())
1994 deviceState.symbols->lookup<AIE::ShimDMAAllocationOp>(
1995 proof.getOutput().getAttr()))
1996 deviceState.proofsByOutput[output].push_back({input, proof});
1998 WalkResult wr = device.walk([&](AIE::RuntimeSequenceOp seq) -> WalkResult {
1999 if (failed(checkForeignTail(seq)))
2000 return WalkResult::interrupt();
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);
2012 isa<DMAConfigureTaskOp, DMAConfigureTaskForOp, DMAStartBdChainOp,
2013 DMAStartTaskOp, DMAAwaitTaskOp, DMAFreeTaskOp>(op);
2015 if (dynamicPool || (!hasTasks && hasControlFlow))
2016 return WalkResult::advance();
2018 if (hasTasks && failed(validate(seq)))
2019 return WalkResult::interrupt();
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)) {
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();
2045 if (releasedTasks.contains(cfg)) {
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();
2053 if (failed(checkNotBehindLoop(start, cfg)))
2054 return WalkResult::interrupt();
2055 knownComplete.erase(cfg);
2056 provenFinished.erase(cfg);
2058 start.getPushIssueToken(cfg), start, allocationOf(cfg),
2059 pushVolume(start, cfg));
2061 }
else if (
auto load = dyn_cast<NpuLoadPdiOp>(op)) {
2063 }
else if (
auto reset = dyn_cast<DmaChannelResetOp>(op)) {
2065 reset.getTileOp(), reset.getDirection(), reset.getChannel()));
2066 }
else if (
auto poll = dyn_cast<NpuMaskPollOp>(op)) {
2068 }
else if (
auto await = dyn_cast<DMAAwaitTaskOp>(op)) {
2069 if (DMAConfigureTaskOp cfg = await.getTaskOp())
2070 if (cfg.getIssueToken())
2072 if (failed(recycleTask(await.getTask(), await,
true)))
2073 return WalkResult::interrupt();
2074 }
else if (
auto freeOp = dyn_cast<DMAFreeTaskOp>(op)) {
2075 if (failed(recycleTask(freeOp.getTask(), freeOp,
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);
2089 if (failed(holdCopy(copy, raw.key, pushCount - 1, raw.issuesToken)))
2090 return WalkResult::interrupt();
2091 if (roundState.reallocate)
2092 return WalkResult::interrupt();
2095 return WalkResult::advance();
2102 auto reusesBefore = unsafeReuses;
2103 auto copiesBefore = copiesOverCopies;
2104 WalkResult r = WalkResult::advance();
2105 std::vector<Diagnostic> held;
2107 resetPerSequenceState();
2111 indexLockReleases(seq);
2115 uint64_t thread = llvm::get_threadid();
2116 ScopedDiagnosticHandler hold(&getContext(), [&](Diagnostic &diag) {
2117 if (llvm::get_threadid() != thread)
2119 held.push_back(std::move(diag));
2122 r = seq.walk(visit);
2124 if (!roundState.reallocate)
2126 for (AIE::DMABDOp bd : roundState.assignedHere)
2127 bd.removeBdIdAttr();
2128 for (Operation *inserted : llvm::reverse(roundState.insertedHere))
2130 unsafeReuses = reusesBefore;
2131 copiesOverCopies = copiesBefore;
2133 for (Diagnostic &diag : held)
2134 getContext().getDiagEngine().emit(std::move(diag));
2135 if (r.wasInterrupted())
2136 return WalkResult::interrupt();
2138 for (DMAFreeTaskOp freeOp : frees)
2140 return WalkResult::advance();
2143 if (wr.wasInterrupted())
2144 return signalPassFailure();
2150std::unique_ptr<OperationPass<AIE::DeviceOp>>
2152 return std::make_unique<AIEAssignRuntimeSequenceBDIDsPass>();
2155std::unique_ptr<OperationPass<AIE::DeviceOp>>
2157 const AIEAssignRuntimeSequenceBDIDsOptions &options) {
2158 return std::make_unique<AIEAssignRuntimeSequenceBDIDsPass>(options);
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)
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)
std::optional< uint32_t > getConstantIntOperand(mlir::Value v)
std::map< int64_t, int64_t > Volume
std::unique_ptr< mlir::OperationPass< AIE::DeviceOp > > createAIEAssignRuntimeSequenceBDIDsPass()
Unbalanced balanceUnder(AIE::ConsumedByAttr proof, const Volume &in, const Volume &out)
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)