MLIR-AIE 1.4.6.dev
AIEObjectFifoAllocate.cpp
Go to the documentation of this file.
1//===- AIEObjectFifoAllocate.cpp --------------------------------*- C++ -*-===//
2//
3// Copyright (C) 2026 Advanced Micro Devices, Inc.
4// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
5//
6//===----------------------------------------------------------------------===//
7
20
21#include "mlir/IR/Attributes.h"
22#include "mlir/Interfaces/DataLayoutInterfaces.h"
23#include "mlir/Pass/Pass.h"
24#include "llvm/ADT/EquivalenceClasses.h"
25#include "llvm/ADT/MapVector.h"
26#include "llvm/ADT/StringMap.h"
27#include "llvm/Support/Debug.h"
28#include "llvm/Support/FormatVariadic.h"
29
30#include <map>
31#include <memory>
32#include <set>
33
34#define DEBUG_TYPE "aie-objectfifo-allocate"
35
36using namespace mlir;
37using namespace xilinx;
38using namespace xilinx::AIE;
39
40namespace xilinx::AIE {
41#define GEN_PASS_DEF_AIEOBJECTFIFOALLOCATE
42#include "aie/Dialect/AIE/Transforms/AIEPasses.h.inc"
43} // namespace xilinx::AIE
44
45namespace {
46
47struct AIEObjectFifoAllocatePass
48 : public xilinx::AIE::impl::AIEObjectFifoAllocateBase<
49 AIEObjectFifoAllocatePass> {
50 using Base::Base;
51
52 DeviceOp device;
53 OpBuilder builder{static_cast<MLIRContext *>(nullptr)};
54 /// The last buffer or lock this pass placed on each tile.
55 DenseMap<Value, Operation *> lastPlaced;
56 /// Which pools get locks, and the resets re-arming each fifo.
57 std::shared_ptr<PoolLocks> poolLocks;
58 /// Flows already lowered. A route endpoint reads its direction off the
59 /// flow naming it, so these outlive the walk that replaces them.
60 SmallVector<Operation *> loweredFlows;
61 /// The flows each route endpoint is the source of, by its symbol name,
62 /// gathered before any flow is lowered.
63 DenseMap<StringAttr, SmallVector<RouteOp>> sourcedFlows;
64 llvm::MapVector<ObjectFifoDmaEndpointOp, llvm::StringMap<PacketInfoAttr>>
65 dispatchHeaders;
66 /// Ends that take another end's channel, by the end they take it from:
67 /// shim ends never in flight together, and ends taking turns.
68 llvm::MapVector<Operation *, Operation *> channelSharers;
69 llvm::MapVector<Operation *, ShimDMAAllocationOp> allocationSharers;
70 DenseMap<Operation *, SmallVector<Value>> bufferPlacements;
71 DenseMap<Operation *, int> channelAssignments;
72 DenseMap<Operation *, Value> localPools;
73 DenseMap<Operation *, SmallVector<Value>> poolUsers;
74 DenseMap<Operation *, SmallVector<Operation *>> lockUsers;
75 DenseMap<Operation *, Value> lockPlacements;
76 /// What runs on each channel the design programs itself, by the
77 /// `aie.route_endpoint` naming it: dma_starts in its tile's DMA program and
78 /// tasks the runtime sequence configures for it.
79 DenseMap<Operation *, SmallVector<DMAStartOp>> endpointStarts;
80 DenseMap<Operation *, SmallVector<AIEX::DMAConfigureTaskForOp>> endpointTasks;
81 /// BD ids DMA programs and pinned runtime ids hold before objectFIFOs take
82 /// theirs. Channels are chosen from these and the endpoints' own chains
83 /// alone, so an image built for one runtime sequence serves another's
84 /// instruction stream.
85 DMAChannelAnalysis::TakenBDs takenBDs;
86 /// The most unpinned BDs one task the runtime sequence configures on each
87 /// channel by index holds, by (col, row, channel).
88 DenseMap<std::tuple<int, int, int>, int64_t> taskBDs;
89 /// The BDs every channel the last assignment handed out needs at once,
90 /// runtime tasks included.
91 DenseMap<std::tuple<int, int, int>, int64_t> channelDemand;
92 /// Where each tile, pool, endpoint and route falls in an order taken from
93 /// the design's structure alone, which settles the choices op order would.
94 DenseMap<Operation *, unsigned> structuralRank;
95 RouteEndpoint channelFailure;
96 /// Whether channelFailure's channel has too few BD ids left, rather than no
97 /// channel being free.
98 bool bdShortfall = false;
99 /// Mem tiles once short of BD ids, whose ends since take their channels
100 /// from planBDChannels.
101 llvm::SetVector<Operation *> bdPlanned;
102 /// Pools planTurnSharing walked whole (some walks are undone later).
103 llvm::SetVector<Operation *> turnWalked;
104 /// hostMovesFirst's answer, by fifo: the runtime sequences it walks never
105 /// change once this pass starts.
106 DenseMap<StringAttr, bool> hostMovesFirstCache;
107 /// The pool the buffer search could not place with the fewest left
108 /// unplaced, i.e. where it got furthest.
109 ObjectFifoPoolOp bufferFailure;
110 /// Neighbours made for a spill planBuffers weighed. The ones no buffer ends
111 /// up on are erased once allocation is done.
112 SmallVector<TileOp> spillTiles;
113 Value lockFailure;
114 Operation *lockAccessFailure = nullptr;
115 /// The pool whose lock group the packing search was stopped on.
116 ObjectFifoPoolOp lockSearchStoppedOn;
117 /// See LockPlan::groupCounts for what this changes.
118 bool semaphoreLocks = false;
119 bool walkSearchStopped = false;
120 bool lockSearchStopped = false;
121
122 bool sameTile(Value a, Value b) {
123 if (a == b)
124 return true;
125 auto first = cast<TileLike>(a.getDefiningOp());
126 auto second = cast<TileLike>(b.getDefiningOp());
127 auto ac = first.tryGetCol(), ar = first.tryGetRow();
128 auto bc = second.tryGetCol(), br = second.tryGetRow();
129 return ac && ar && bc && br && ac == bc && ar == br;
130 }
131
132 /// The mem tiles a buffer search weighs, as MemTileSpillSearch indices: one
133 /// per placed position, however many ops name it, with the positions a
134 /// placed TileOp may spill to, and one per unplaced tile.
135 DenseMap<TileID, unsigned> memTilePositions;
136 DenseMap<Operation *, unsigned> unplacedMemTiles;
137 SmallVector<std::optional<TileID>> memTileAt;
138
139 std::optional<unsigned> memTileIndex(Value tile) {
140 auto like = cast<TileLike>(tile.getDefiningOp());
141 if (!like.isMemTile())
142 return std::nullopt;
143 auto col = like.tryGetCol(), row = like.tryGetRow();
144 if (col && row)
145 return memTilePositions.lookup({*col, *row});
146 return unplacedMemTiles.lookup(like);
147 }
148
149 /// The search over the device's mem tiles, holding their existing buffers.
150 MemTileSpillSearch memTileSearch() {
151 const auto &target = device.getTargetModel();
152 memTilePositions.clear();
153 unplacedMemTiles.clear();
154 memTileAt.clear();
155 SmallVector<MemTileSpillSearch::Tile> tiles;
156 auto add = [&](std::optional<TileID> at) {
157 memTileAt.push_back(at);
158 tiles.push_back({target.getMemTileSize(), {}});
159 return static_cast<unsigned>(tiles.size() - 1);
160 };
161 for (auto tile : device.getOps<TileLike>()) {
162 if (!tile.isMemTile())
163 continue;
164 auto col = tile.tryGetCol(), row = tile.tryGetRow();
165 if (!col || !row) {
166 unplacedMemTiles[tile] = add(std::nullopt);
167 continue;
168 }
169 TileID at{*col, *row};
170 if (!memTilePositions.count(at))
171 memTilePositions[at] = add(at);
172 if (isa<TileOp>(tile.getOperation()))
173 for (TileID neighbour : memTileSpillNeighbours(target, at))
174 if (!memTilePositions.count(neighbour))
175 memTilePositions[neighbour] = add(neighbour);
176 }
177 int64_t alignment = target.getMemTileLoadStoreBusWidth() / 8;
178 for (auto buffer : device.getOps<BufferOp>())
179 if (std::optional<unsigned> index = memTileIndex(buffer.getTile()))
180 tiles[*index].fixed.push_back({buffer.getAllocationSize(),
181 buffer.getAligned() ? alignment : 1,
182 buffer.getAddress()});
183 return MemTileSpillSearch(std::move(tiles), alignment);
184 }
185
186 LogicalResult collectFixedMemory() {
187 MemTileSpillSearch search = memTileSearch();
188 for (auto tile : device.getOps<TileLike>()) {
189 std::optional<unsigned> index = memTileIndex(tile->getResult(0));
190 if (!index)
191 continue;
192 int64_t bytes = search.used(*index);
193 int64_t capacity = device.getTargetModel().getMemTileSize();
194 if (bytes > capacity)
195 return tile->emitOpError("existing buffers require ")
196 << bytes << " bytes, exceeding MemTile capacity of " << capacity
197 << " bytes";
198 }
199 return success();
200 }
201
202 /// Coordinates `tile` may take: its own once placed, else every position
203 /// of its type in the rows and columns it is pinned to.
204 SmallVector<TileID> compatiblePositions(TileLike tile) {
205 const auto &target = device.getTargetModel();
206 SmallVector<TileID> compatible;
207 auto col = tile.tryGetCol(), row = tile.tryGetRow();
208 for (int c = 0; c < target.columns(); ++c) {
209 if (col && c != *col)
210 continue;
211 for (int r = 0; r < target.rows(); ++r) {
212 if ((!row || r == *row) &&
213 target.getTileType(c, r) == tile.getTileType())
214 compatible.push_back({c, r});
215 }
216 }
217 return compatible;
218 }
219
220 bool canAccess(Value user, Value memory, bool localOnly = false) {
221 if (user == memory)
222 return true;
223 auto memoryTile = dyn_cast<TileLike>(memory.getDefiningOp());
224 return memoryTile &&
225 canAccess(user, compatiblePositions(memoryTile), localOnly);
226 }
227
228 /// Before placement, defer only accesses that some compatible physical
229 /// positions could satisfy. Known coordinates can already disprove affinity.
230 bool canAccess(Value user, ArrayRef<TileID> memoryPositions,
231 bool localOnly = false) {
232 auto userTile = dyn_cast<TileLike>(user.getDefiningOp());
233 return userTile && LockPlan::reaches(device.getTargetModel(),
234 compatiblePositions(userTile),
235 memoryPositions, localOnly);
236 }
237
238 Value lockPlacement(ObjectFifoPoolOp pool, Operation *group) {
239 if (Value placed = lockPlacements.lookup(group))
240 return placed;
241 Value local = localPools.lookup(pool);
242 return local ? local : pool.getTile();
243 }
244
245 /// A contiguous pool's objects are one buffer; others have one per object.
246 static int bufferCount(ObjectFifoPoolOp pool) {
247 return pool.getContiguous() ? 1 : pool.getDepth();
248 }
249 static int64_t bufferBytes(ObjectFifoPoolOp pool) {
250 return pool.getObjectSizeInBytes() * pool.getObjectsPerBuffer();
251 }
252
253 /// FIXME: choosing which tile a buffer lives on is the buffer allocator's
254 /// job, not this pass's; --aie-assign-buffer-addresses should instead be
255 /// free to move buffers between tiles that share a memory module.
256 ///
257 /// Reserve mandatory-local objects before any other pool can spill into
258 /// their memory. Existing buffers are fixed and counted by identity, not by
259 /// how many pools or endpoints reference them. The others' mem tile buffers
260 /// go where MemTileSpillSearch puts them, in pool order.
261 LogicalResult planBuffers(ArrayRef<ObjectFifoPoolOp> pools) {
262 bufferPlacements.clear();
263 bufferFailure = nullptr;
264 MemTileSpillSearch search = memTileSearch();
265 auto reachable = [&](ObjectFifoPoolOp pool, auto memory) {
266 return llvm::all_of(poolUsers[pool],
267 [&](Value user) { return canAccess(user, memory); });
268 };
269 for (auto pool : pools) {
270 if (!localPools.contains(pool))
271 continue;
272 Value tile = localPools.lookup(pool);
273 int count = pool.getBuffers() ? 0 : bufferCount(pool);
274 int64_t size = bufferBytes(pool);
275 std::optional<unsigned> index = memTileIndex(tile);
276 if (!canAccess(pool.getTile(), tile) || !reachable(pool, tile) ||
277 (index && !search.fits(*index, size, count))) {
278 bufferFailure = pool;
279 return failure();
280 }
281 if (index)
282 search.reserve(*index, size, count);
283 }
284 const auto &target = device.getTargetModel();
285 SmallVector<MemTileSpillSearch::Buffer> buffers;
286 SmallVector<ObjectFifoPoolOp> owners;
287 for (auto pool : pools) {
288 if (pool.getBuffers()) {
289 for (auto buffer : pool.getBufferOps()) {
290 Value tile = buffer.getBufferTile();
291 if (tile && ((localPools.contains(pool) &&
292 !sameTile(tile, localPools.lookup(pool))) ||
293 !reachable(pool, tile))) {
294 bufferFailure = pool;
295 return failure();
296 }
297 bufferPlacements[pool].push_back(tile);
298 }
299 continue;
300 }
301 if (pool.getTileLike().isShimTile())
302 continue;
303 if (localPools.contains(pool)) {
304 bufferPlacements[pool].append(bufferCount(pool),
305 localPools.lookup(pool));
306 continue;
307 }
308 Value home = pool.getTile();
309 bool atHome = reachable(pool, home);
310 std::optional<unsigned> index = memTileIndex(home);
311 if (!index) {
312 if (!atHome) {
313 bufferFailure = pool;
314 return failure();
315 }
316 bufferPlacements[pool].append(bufferCount(pool), home);
317 continue;
318 }
319 // Which tiles neighbor an unplaced one is not yet known, so its buffers
320 // stay at home.
321 SmallVector<unsigned, 2> neighbours;
322 if (auto homeOp = dyn_cast<TileOp>(home.getDefiningOp()))
323 for (TileID at :
324 memTileSpillNeighbours(target, {homeOp.getCol(), homeOp.getRow()}))
325 if (reachable(pool, ArrayRef<TileID>{at}))
326 neighbours.push_back(memTilePositions.lookup(at));
327 for (int i = 0, e = bufferCount(pool); i < e; ++i) {
328 buffers.push_back({bufferBytes(pool), *index, atHome, neighbours});
329 owners.push_back(pool);
330 }
331 }
332 bool placed = search.place(buffers);
333 // A spill weighed from a placed home makes its neighbors' tile ops; the
334 // ones no buffer ends up on are erased once allocation is done.
335 for (auto [buffer, pool] : llvm::zip(buffers, owners)) {
336 auto homeOp = dyn_cast<TileOp>(pool.getTile().getDefiningOp());
337 if (!homeOp || !search.weighed[buffer.home])
338 continue;
339 for (int col : {homeOp.getCol() - 1, homeOp.getCol() + 1})
340 if (col >= 0 && col < target.columns())
341 spillTile(col, homeOp.getRow(), pool.getLoc());
342 }
343 if (!placed) {
344 bufferFailure = owners[search.failed];
345 return failure();
346 }
347 for (auto [buffer, tile, pool] : llvm::zip(buffers, search.chosen, owners))
348 bufferPlacements[pool].push_back(
349 tile == buffer.home ? pool.getTile()
350 : spillTile(memTileAt[tile]->col,
351 memTileAt[tile]->row, pool.getLoc())
352 .getResult());
353 return success();
354 }
355
356 /// The tile op at (`col`, `row`), made if the device has none.
357 TileOp spillTile(int col, int row, Location loc) {
358 bool declared = llvm::any_of(device.getOps<TileOp>(), [&](TileOp t) {
359 return t.getCol() == col && t.getRow() == row;
360 });
361 TileOp tile = TileOp::getOrCreate(builder, device, col, row, loc);
362 if (!declared)
363 spillTiles.push_back(tile);
364 return tile;
365 }
366
367 /// Buffers and locks sit directly below the tile whose memory holds them,
368 /// after whatever this pass has already put there.
369 void setInsertionPointOn(Value tile) {
370 Operation *after = lastPlaced.lookup(tile);
371 if (!after) {
372 after = tile.getDefiningOp();
373 }
374 if (after) {
375 builder.setInsertionPointAfter(after);
376 } else {
377 builder.setInsertionPointToStart(device.getBody());
378 }
379 }
380
381 void allocateBuffers(ObjectFifoPoolOp pool) {
382 if (pool.getBuffers()) {
383 return;
384 }
385 TileLike home = pool.getTileLike();
386 if (home.isShimTile()) {
387 return;
388 }
389
390 ArrayRef<Attribute> initValues;
391 if (auto initAttr = pool.getInitValues()) {
392 initValues = initAttr->getValue();
393 }
394 int filled = initValues.size();
395 StringRef base = pool.getBaseName();
396
397 SmallVector<Attribute> names;
398 MemRefType type = pool.getElemType();
399 ElementsAttr zeros;
400 if (pool.getContiguous()) {
401 int64_t objectElements = type.getNumElements();
402 type = MemRefType::get({pool.getObjectsPerBuffer() * objectElements},
403 type.getElementType());
404 auto tensor =
405 RankedTensorType::get(type.getShape(), type.getElementType());
406 Attribute zero = builder.getZeroAttr(type.getElementType());
407 if (filled) {
408 // The one buffer starts as its objects do, in order, between its zero
409 // objects; objects with no initial contents start zero.
410 auto zeroObjects = pool.getZeroObjects();
411 SmallVector<Attribute> values(
412 (zeroObjects ? (*zeroObjects)[0] : 0) * objectElements, zero);
413 for (int i = 0; i < pool.getDepth(); i++) {
414 if (i < filled)
415 llvm::append_range(
416 values,
417 cast<DenseElementsAttr>(initValues[i]).getValues<Attribute>());
418 else
419 values.append(objectElements, zero);
420 }
421 values.append((zeroObjects ? (*zeroObjects)[1] : 0) * objectElements,
422 zero);
423 zeros = DenseElementsAttr::get(tensor, values);
424 } else if (pool.getZeroObjects()) {
425 zeros = DenseElementsAttr::get(tensor, zero);
426 }
427 }
428 // Initial contents may fill only the first objects of a deeper pool.
429 for (int i = 0; i < bufferCount(pool); i++) {
430 ElementsAttr init = !pool.getContiguous() && i < filled
431 ? cast<ElementsAttr>(initValues[i])
432 : zeros;
433 std::string name = (base + "__buf" + std::to_string(i)).str();
434 Value placement = bufferPlacements[pool][i];
435 setInsertionPointOn(placement);
436 lastPlaced[placement] = BufferOp::create(
437 builder, pool.getLoc(), type, placement, builder.getStringAttr(name),
438 /*address=*/nullptr, init,
439 /*mem_bank=*/nullptr, /*core_data=*/false);
440 names.push_back(FlatSymbolRefAttr::get(builder.getContext(), name));
441 }
442 pool.setBuffersAttr(builder.getArrayAttr(names));
443 }
444
445 LockOp createLock(ObjectFifoPoolOp pool, Value tile, StringRef name,
446 int value) {
447 setInsertionPointOn(tile);
448 auto lock = LockOp::create(builder, pool.getLoc(), tile, value);
449 lastPlaced[tile] = lock;
450 lock->setAttr(SymbolTable::getSymbolAttrName(),
451 builder.getStringAttr(name));
452 return lock;
453 }
454
455 LogicalResult planLocks(ArrayRef<ObjectFifoPoolOp> pools) {
456 lockFailure = {};
457 lockAccessFailure = nullptr;
458 lockSearchStopped = false;
459 lockPlacements.clear();
460 LockPlan plan(device.getTargetModel());
461 SmallVector<Value> tileValues;
462 DenseMap<Value, unsigned> tileIndex;
463 auto indexOf = [&](Value tile) {
464 auto [at, fresh] = tileIndex.try_emplace(tile, tileValues.size());
465 if (fresh) {
466 auto like = cast<TileLike>(tile.getDefiningOp());
467 auto col = like.tryGetCol(), row = like.tryGetRow();
468 plan.addTile(
469 {compatiblePositions(like),
470 col && row ? std::optional<TileID>({*col, *row}) : std::nullopt});
471 tileValues.push_back(tile);
472 }
473 return at->second;
474 };
475 for (auto lock : device.getOps<LockOp>())
476 if (!plan.reserve(indexOf(lock.getTile()), 1)) {
477 lockFailure = lock.getTile();
478 return failure();
479 }
480 // Neighbours created to weigh a spill take no locks: the placers count
481 // locks only on the tiles that exist before allocation.
482 SmallVector<TileLike> tiles(device.getOps<TileLike>());
483 llvm::stable_sort(tiles, [&](TileLike a, TileLike b) {
484 auto aRank = structuralRank.find(a), bRank = structuralRank.find(b);
485 if ((aRank == structuralRank.end()) != (bRank == structuralRank.end()))
486 return bRank == structuralRank.end();
487 return aRank != structuralRank.end() && aRank->second < bRank->second;
488 });
489 SmallVector<unsigned> ranked;
490 for (auto tile : tiles)
491 if (!llvm::is_contained(spillTiles, tile.getOperation()))
492 ranked.push_back(indexOf(tile->getResult(0)));
493 SmallVector<LockPlan::Group> groups;
494 SmallVector<Operation *> groupOps;
495 SmallVector<ObjectFifoPoolOp> groupPools;
496 auto add = [&](ObjectFifoPoolOp pool, Operation *group, int count) {
497 SmallVector<unsigned> buffers;
498 for (Value tile : bufferPlacements[pool])
499 if (tile && !llvm::is_contained(spillTiles, tile.getDefiningOp()))
500 buffers.push_back(indexOf(tile));
501 SmallVector<LockPlan::User> users;
502 for (Operation *user : lockUsers[group]) {
503 Value tile = user->getOperand(0);
504 users.push_back(
505 {indexOf(tile),
506 isa<ObjectFifoDmaEndpointOp>(user) &&
508 cast<TileLike>(tile.getDefiningOp()).getTileType())});
509 }
510 groups.push_back(
511 LockPlan::group(count, indexOf(lockPlacement(pool, group)),
512 localPools.contains(pool), buffers, users, ranked));
513 groupOps.push_back(group);
514 groupPools.push_back(pool);
515 };
516 for (auto pool : pools) {
517 if (!poolLocks->needsLocks(pool))
518 continue;
519 SmallVector<Operation *> owners =
520 LockPlan::lockOwners(device.getTargetModel(), pool);
521 for (auto [owner, count] : llvm::zip_equal(
522 owners, LockPlan::groupCounts(device.getTargetModel(),
523 pool.getDepth(), owners.size())))
524 add(pool, owner, count);
525 }
526 LockPlan::Assignment assignment = plan.assign(groups);
527 if (assignment.failed) {
528 Operation *group = groupOps[*assignment.failed];
529 const LockPlan::Placed &missed = assignment.failure;
530 lockSearchStopped = assignment.stopped;
531 lockSearchStoppedOn = groupPools[*assignment.failed];
532 lockFailure = missed.full ? tileValues[*missed.full] : Value();
533 if (!missed.reachable && !lockUsers[group].empty())
534 lockAccessFailure = lockUsers[group].front();
535 return failure();
536 }
537 for (auto [group, tile] : llvm::zip(groupOps, assignment.tiles))
538 if (tile)
539 lockPlacements[group] = tileValues[*tile];
540 auto check = [&](auto endpoint) {
541 for (Value tile : endpointLockTiles(endpoint)) {
542 if (!canAccessLocks(endpoint, tile)) {
543 lockAccessFailure = endpoint;
544 return failure();
545 }
546 }
547 return success();
548 };
549 for (auto endpoint : device.getOps<ObjectFifoCoreEndpointOp>())
550 if (failed(check(endpoint)))
551 return failure();
552 for (auto endpoint : device.getOps<ObjectFifoDmaEndpointOp>())
553 if (failed(check(endpoint)))
554 return failure();
555 return success();
556 }
557
558 void allocateLocks(ObjectFifoPoolOp pool) {
559 if (!poolLocks->needsLocks(pool))
560 return;
561 StringRef base = pool.getBaseName();
562 int depth = pool.getDepth();
563 auto initValues = pool.getInitValues();
564 int filled = initValues ? initValues->size() : 0;
565 int repeat = pool.getRepeatCount().value_or(1);
566
567 if (!semaphoreLocks) {
568 if (pool.getLocks()) {
569 return;
570 }
571 SmallVector<Attribute> names;
572 for (int i = 0; i < depth; i++) {
573 std::string name = (base + "__lock" + std::to_string(i)).str();
574 createLock(pool, lockPlacement(pool, pool), name, i < filled ? 1 : 0);
575 names.push_back(FlatSymbolRefAttr::get(builder.getContext(), name));
576 }
577 pool.setLocksAttr(builder.getArrayAttr(names));
578 return;
579 }
580
581 for (auto [index, segment] : llvm::enumerate(pool.getSegmentOps())) {
582 if (segment.getProduceLock() && segment.getConsumeLock()) {
583 continue;
584 }
585 std::string produce = (base + "__prodlock" + std::to_string(index)).str();
586 std::string consume = (base + "__conslock" + std::to_string(index)).str();
587 Value tile = lockPlacement(pool, segment);
588 createLock(pool, tile, produce, (depth - filled) * repeat);
589 createLock(pool, tile, consume, filled * repeat);
590 segment.setProduceLockAttr(
591 FlatSymbolRefAttr::get(builder.getContext(), produce));
592 segment.setConsumeLockAttr(
593 FlatSymbolRefAttr::get(builder.getContext(), consume));
594 }
595 }
596
597 bool canAccessLocks(Operation *endpoint, Value tile) {
598 Value user = endpoint->getOperand(0);
599 if (isa<ObjectFifoDmaEndpointOp>(endpoint) &&
601 cast<TileLike>(user.getDefiningOp()).getTileType()))
602 return canAccess(user, tile, /*localOnly=*/true);
603 return canAccess(user, tile);
604 }
605
606 template <typename EndpointOp>
607 void collectLockUsers(EndpointOp endpoint) {
608 auto pool = endpoint.getPoolOp();
609 if (!semaphoreLocks) {
610 lockUsers[pool].push_back(endpoint);
611 return;
612 }
613 for (auto segment : endpoint.getSelectedSegments())
614 lockUsers[segment].push_back(endpoint);
615 }
616
617 /// Predict the locks core and DMA lowering will use, including hand-written
618 /// locks and those allocation will create. Only selected segments matter.
619 template <typename EndpointOp>
620 SmallVector<Value> endpointLockTiles(EndpointOp endpoint) {
621 SmallVector<Value> tiles;
622 auto pool = endpoint.getPoolOp();
623 if (pool.getDepth() == 0)
624 return tiles;
625 if (!semaphoreLocks) {
626 if (poolLocks->needsLocks(pool) && !pool.getLocks())
627 tiles.push_back(lockPlacement(pool, pool));
628 else
629 for (auto lock : pool.getLockOps())
630 tiles.push_back(lock.getTile());
631 return tiles;
632 }
633 for (auto segment : endpoint.getSelectedSegments()) {
634 if (poolLocks->needsLocks(pool) &&
635 !(segment.getProduceLock() && segment.getConsumeLock())) {
636 tiles.push_back(lockPlacement(pool, segment));
637 continue;
638 }
639 for (auto name :
640 {segment.getProduceLockAttr(), segment.getConsumeLockAttr()})
641 if (name)
642 if (auto lock = lookupNamedOp<LockOp>(device, name.getAttr()))
643 tiles.push_back(lock.getTile());
644 }
645 return tiles;
646 }
647
648 /// Both buffers and locks must be local to use the local-only channels.
649 /// Distinct unresolved tiles may be neighbors after placement, so they
650 /// cannot be assumed local when assigning a placed endpoint's channels.
651 /// An end whose channel others take turns on reaches what they reach too.
652 bool reachesAdjacentTile(RouteEndpoint endpoint) {
653 if (ownReachesAdjacentTile(endpoint))
654 return true;
655 for (auto [sharer, owner] : channelSharers)
656 if (owner == endpoint.getOperation() &&
657 ownReachesAdjacentTile(cast<RouteEndpoint>(sharer)))
658 return true;
659 return false;
660 }
661
662 /// Whether `endpoint`'s own pool, locks or DMA program reach another tile,
663 /// whatever ends take turns on its channel.
664 bool ownReachesAdjacentTile(RouteEndpoint endpoint) {
665 if (auto route = dyn_cast<RouteEndpointOp>(endpoint.getOperation()))
666 return programReachesAdjacentTile(route);
667 auto dma = dyn_cast<ObjectFifoDmaEndpointOp>(endpoint.getOperation());
668 if (!dma || !dma.getTileLike().isMemTile()) {
669 return false;
670 }
671 ObjectFifoPoolOp pool = dma.getPoolOp();
672 auto remote = [&](Value tile) {
673 return tile && !sameTile(tile, endpoint.getTile());
674 };
675 return pool && (llvm::any_of(bufferPlacements[pool], remote) ||
676 llvm::any_of(endpointLockTiles(dma), remote));
677 }
678
679 TileLike tileOf(RouteEndpoint endpoint) {
680 return dyn_cast<TileLike>(endpoint.getTile().getDefiningOp());
681 }
682
683 /// A DMA channel the design programs itself, by naming this endpoint from a
684 /// dma_start or a runtime task, rather than one an objectFIFO lowers to.
685 static bool isProgramOwned(RouteEndpoint endpoint) {
686 auto route = dyn_cast<RouteEndpointOp>(endpoint.getOperation());
687 return route && route.getBundle() == WireBundle::DMA &&
688 !route.getTileLike().isShimTile();
689 }
690
691 static int64_t countBDs(Region &taskBody) {
692 int64_t bds = 0;
693 taskBody.walk([&](DMABDOp) { bds++; });
694 return bds;
695 }
696
697 /// BDs a program-owned endpoint's static chains hold; they stay configured.
698 int64_t endpointBDs(Operation *endpoint) {
699 int64_t bds = 0;
700 for (DMAStartOp start : endpointStarts.lookup(endpoint))
701 bds += DMAChannelAnalysis::countBDs(start);
702 return bds;
703 }
704
705 /// BDs `endpoint` needs: an objectFIFO's DMA count, a program-owned
706 /// endpoint's static chains, or none.
707 int64_t bdsOf(RouteEndpoint endpoint) {
708 if (auto dma = dyn_cast<ObjectFifoDmaEndpointOp>(endpoint.getOperation()))
709 return dma.getNumBDs();
710 if (isProgramOwned(endpoint))
711 return endpointBDs(endpoint.getOperation());
712 return 0;
713 }
714
715 /// BDs the largest runtime task on a program-owned endpoint needs.
716 int64_t endpointTaskBDs(Operation *endpoint) {
717 int64_t largest = 0;
718 for (auto task : endpointTasks.lookup(endpoint))
719 largest = std::max(largest, countBDs(task.getBody()));
720 return largest;
721 }
722
723 /// Whether a program-owned MemTile channel's BDs touch a neighbor's buffers
724 /// or locks, which only the lower channels can.
725 bool programReachesAdjacentTile(RouteEndpointOp endpoint) {
726 if (!endpoint.getTileLike().isMemTile())
727 return false;
728 auto remote = [&](Operation *op) {
729 Value tile;
730 if (auto bd = dyn_cast<DMABDOp>(op)) {
731 if (auto buffer =
732 dyn_cast_or_null<BufferOp>(bd.getBuffer().getDefiningOp()))
733 tile = buffer.getTile();
734 } else if (auto use = dyn_cast<UseLockOp>(op)) {
735 if (auto lock = dyn_cast_or_null<LockOp>(use.getLock().getDefiningOp()))
736 tile = lock.getTile();
737 }
738 return tile && !sameTile(tile, endpoint.getTile());
739 };
740 for (DMAStartOp start : endpointStarts.lookup(endpoint))
741 for (Block *block : DMAChannelAnalysis::chainOf(start))
742 if (llvm::any_of(block->getOperations(),
743 [&](Operation &op) { return remote(&op); }))
744 return true;
745 for (auto task : endpointTasks.lookup(endpoint)) {
746 bool reaches = false;
747 task.getBody().walk([&](Operation *op) { reaches |= remote(op); });
748 if (reaches)
749 return true;
750 }
751 return false;
752 }
753
754 /// Find what programs each endpoint-named channel, and the BDs already spoken
755 /// for on channels named by index.
756 void collectChannelPrograms() {
757 endpointStarts.clear();
758 endpointTasks.clear();
759 taskBDs.clear();
760 takenBDs = DMAChannelAnalysis::TakenBDs(device);
761 auto key = [](Value tile,
762 int channel) -> std::optional<std::tuple<int, int, int>> {
763 auto placed = cast<TileLike>(tile.getDefiningOp());
764 auto col = placed.tryGetCol(), row = placed.tryGetRow();
765 if (!col || !row)
766 return std::nullopt;
767 return std::make_tuple(*col, *row, channel);
768 };
769 for (auto program : device.getOps<DmaBody>())
770 for (Block &block : program.getDmaBody())
771 for (auto start : block.getOps<DMAStartOp>())
772 if (auto endpoint = start.getEndpointOp())
773 endpointStarts[endpoint].push_back(start);
774 device.walk([&](Operation *op) {
775 if (auto task = dyn_cast<AIEX::DMAConfigureTaskForOp>(op)) {
776 if (auto endpoint = dyn_cast_or_null<RouteEndpointOp>(
777 SymbolTable::lookupNearestSymbolFrom(
778 device, task.getAlloc().getRootReference())))
779 endpointTasks[endpoint].push_back(task);
780 } else if (auto task = dyn_cast<AIEX::DMAConfigureTaskOp>(op)) {
781 if (auto at = key(task.getTile(), task.getChannel())) {
782 int64_t unpinned = 0;
783 task.getBody().walk([&](DMABDOp bd) { unpinned += !bd.getBdId(); });
784 int64_t &largest = taskBDs[*at];
785 largest = std::max(largest, unpinned);
786 }
787 }
788 });
789 }
790
791 /// Rank tiles, pools, endpoints and routes by their attributes and then, a
792 /// round at a time until no class splits, by the ranks of what they connect
793 /// to. Symbol names and op order play no part, so a permuted or renamed
794 /// design ranks alike, and ops still tied cannot be told apart.
795 void rankStructurally() {
796 StructuralGraph graph;
797 // A placed tile is one node however many ops name it.
798 DenseMap<std::pair<int, int>, Operation *> placed;
799 DenseMap<Operation *, Operation *> tileNode;
800 for (auto tile : device.getOps<TileLike>()) {
801 auto col = tile.tryGetCol(), row = tile.tryGetRow();
802 if (!col || !row) {
803 graph.add(tileNode[tile] = tile);
804 continue;
805 }
806 auto [it, first] = placed.try_emplace({*col, *row}, tile);
807 tileNode[tile] = it->second;
808 if (first) {
809 graph.nodes.push_back(tile);
810 llvm::raw_string_ostream(graph.features[tile])
811 << "tile " << *col << ' ' << *row << ' '
812 << stringifyAIETileType(tile.getTileType());
813 }
814 }
815 auto link = [&](Operation *from, Operation *to, StringRef label) {
816 if (Operation *tile = tileNode.lookup(to))
817 to = tile;
818 graph.link(from, to, label);
819 };
820 for (auto pool : device.getOps<ObjectFifoPoolOp>()) {
821 llvm::raw_string_ostream os(graph.add(pool));
822 for (auto segment : pool.getSegmentOps())
823 os << " [" << segment.getOffset() << ", " << segment.getSize() << "]";
824 link(pool, pool.getTile().getDefiningOp(), "tile");
825 }
826 DenseMap<StringAttr, Operation *> coreEndpoints;
827 for (auto endpoint : device.getOps<ObjectFifoCoreEndpointOp>()) {
828 coreEndpoints[endpoint.getSymNameAttr()] = endpoint;
829 llvm::raw_string_ostream os(graph.add(endpoint));
830 for (auto segment : endpoint.getSelectedSegments())
831 os << " @" << segment.getOffset();
832 link(endpoint, endpoint.getTile().getDefiningOp(), "tile");
833 link(endpoint, endpoint.getPoolOp(), "pool");
834 }
835 for (auto endpoint : device.getOps<RouteEndpoint>()) {
836 llvm::raw_string_ostream os(graph.add(endpoint));
837 if (auto dma =
838 dyn_cast<ObjectFifoDmaEndpointOp>(endpoint.getOperation())) {
839 for (auto segment : dma.getSelectedSegments())
840 os << " @" << segment.getOffset();
841 link(endpoint, dma.getPoolOp(), "pool");
842 }
843 link(endpoint, endpoint.getTile().getDefiningOp(), "tile");
844 }
845 for (auto route : device.getOps<RouteOp>()) {
846 graph.add(route);
847 for (StringRef source : route.getSourceNames())
848 link(route, lookupEndpoint(source), "source");
849 for (StringRef dest : route.getDestinationNames())
850 link(route, lookupEndpoint(dest), "dest");
851 }
852 DenseMap<Operation *, unsigned> rank = graph.rank();
853 // Ops still tied fall to the order each core first acquires its ends in,
854 // the core's program order: ranking again from the ranks found, with the
855 // cores linked in, splits only ties.
856 for (Operation *node : graph.nodes)
857 graph.features[node] = llvm::formatv("{0,10}", rank[node]).str();
858 for (auto core : device.getOps<CoreOp>()) {
859 graph.add(core);
860 llvm::SmallPtrSet<Operation *, 8> acquired;
861 core.walk([&](ObjectFifoAcquireOp acquire) {
862 Operation *endpoint =
863 coreEndpoints.lookup(acquire.getObjFifoNameAttr().getAttr());
864 if (endpoint && acquired.insert(endpoint).second)
865 graph.link(core, endpoint,
866 llvm::formatv("acquire {0,10}", acquired.size()).str());
867 });
868 }
869 rank = graph.rank();
870 for (auto [tile, node] : tileNode)
871 rank[tile] = rank[node];
872 structuralRank = std::move(rank);
873 }
874
875 /// BDs `channel` of the tile at (`col`, `row`) can use that `demand` leaves
876 /// over, counting every channel whose BD ids overlap its own. Negative when
877 /// overcommitted.
878 int64_t bdRoom(TileLike tile, int col, int row, int channel,
879 const DenseMap<std::tuple<int, int, int>, int64_t> &demand) {
880 const AIETargetModel &target = device.getTargetModel();
881 int numChannels = std::max(tile.getNumSourceConnections(WireBundle::DMA),
882 tile.getNumDestConnections(WireBundle::DMA));
883 SmallVector<DMAChannelAnalysis::BDGroup> groups =
884 DMAChannelAnalysis::bdGroups(target, col, row, numChannels);
885 auto *group =
886 llvm::find_if(groups, [&](const DMAChannelAnalysis::BDGroup &g) {
887 return llvm::is_contained(g.channels, channel);
888 });
889 int64_t room = group->ids.count();
890 for (int other : group->channels)
891 if (auto it = demand.find({col, row, other}); it != demand.end())
892 room -= it->second;
893 return room;
894 }
895
896 /// `endpoint`'s BD plan: its direction, BD count, channel limit (with
897 /// `adjacent` access, where its tile allows it), and its pinned channel,
898 /// kept only when `keepPin`.
899 DMAChannelAnalysis::BDPlanEnd planEnd(RouteEndpoint endpoint, bool adjacent,
900 bool keepPin) {
901 DMAChannelDir dir = endpoint.getRouteDirection();
902 return {
903 dir, bdsOf(endpoint),
904 DMAChannelAnalysis::getDMAChannelLimit(tileOf(endpoint), dir, adjacent),
905 keepPin ? endpoint.getRouteChannel() : std::nullopt};
906 }
907
908 /// On a tile whose BD ids are split between channels, the free channel whose
909 /// BDs have the most room left once every channel sharing them has its
910 /// demand; ties, and tiles without such a split, go to the lowest index.
911 /// Falls back to first-free where coordinates are unknown.
912 int chooseChannel(DMAChannelAnalysis &channels, RouteEndpoint endpoint,
913 const DenseMap<std::tuple<int, int, int>, int64_t> &demand,
914 bool adjacent) {
915 TileLike tile = tileOf(endpoint);
916 DMAChannelDir dir = endpoint.getRouteDirection();
917 std::optional<int> col = tile.tryGetCol(), row = tile.tryGetRow();
918 if (!col || !row)
919 return channels.getDMAChannelIndex(tile, dir, adjacent,
920 endpoint.getOperation());
921 int best = -1;
922 int64_t bestRoom = 0;
923 int limit = DMAChannelAnalysis::getDMAChannelLimit(tile, dir, adjacent);
924 for (int channel = 0; channel < limit; ++channel) {
925 if (!channels.isChannelFree(tile, dir, channel))
926 continue;
927 int64_t room = bdRoom(tile, *col, *row, channel, demand);
928 if (best < 0 || room > bestRoom) {
929 best = channel;
930 bestRoom = room;
931 }
932 }
933 if (best < 0)
934 return -1;
935 return channels.reservePinnedChannel(tile, dir, best,
936 endpoint.getOperation());
937 }
938
939 void noteChannelOwner(InFlightDiagnostic &diag, Operation *owner,
940 std::optional<int> channel = std::nullopt) {
941 auto &note = diag.attachNote(owner->getLoc());
942 if (auto endpoint = dyn_cast<RouteEndpoint>(owner)) {
943 note << "DMA endpoint @" << cast<SymbolOpInterface>(owner).getName();
944 if (auto fifo = owner->getAttrOfType<StringAttr>("fifoName"))
945 note << " for ObjectFifo @" << fifo.getValue();
946 if (reachesAdjacentTile(endpoint))
947 note << " requires adjacent MemTile access";
948 if (channel)
949 note << "; occupies channel " << *channel;
950 } else if (channel) {
951 note << "pre-existing " << owner->getName() << " reserves DMA channel "
952 << *channel;
953 }
954 }
955
956 // The endpoints of the routes that switch packets.
957 DenseSet<Operation *> packetEndpoints() {
958 DenseSet<Operation *> endpoints;
959 for (auto flow : device.getOps<RouteOp>()) {
960 if (!flow.getPacket())
961 continue;
962 for (StringRef source : flow.getSourceNames())
963 endpoints.insert(lookupEndpoint(source).getOperation());
964 for (StringRef dest : flow.getDestinationNames())
965 endpoints.insert(lookupEndpoint(dest).getOperation());
966 }
967 return endpoints;
968 }
969
970 // No allocation can move a stream port the design names, so a clash fails
971 // the pass before the search rather than surfacing inside it.
972 LogicalResult checkStreamPorts() {
973 DMAChannelAnalysis channels(device);
974 DenseSet<Operation *> packetEndpoints = this->packetEndpoints();
975 bool clash = false;
976 for (auto endpoint : device.getOps<RouteEndpoint>()) {
977 if (endpoint.getRouteBundle() != WireBundle::Core)
978 continue;
979 std::optional<int> channel = endpoint.getRouteChannel();
980 if (!channel)
981 return endpoint->emitOpError("a stream port names its own channel");
982 clash |= failed(channels.checkAIEStreamIndex(
983 tileOf(endpoint), {endpoint.getRouteDirection(), *channel},
984 endpoint.getOperation(),
985 packetEndpoints.contains(endpoint.getOperation())));
986 }
987 return failure(clash);
988 }
989
990 /// Whether `endpoint` draws a DMA channel of its own, rather than being a
991 /// core's stream port or sharing another end's channel.
992 bool drawsOwnChannel(RouteEndpoint endpoint) {
993 return endpoint.getRouteBundle() != WireBundle::Core &&
994 !channelSharers.contains(endpoint.getOperation()) &&
995 !allocationSharers.contains(endpoint.getOperation());
996 }
997
998 /// Whether this endpoint can share its pinned channel without a cyclic
999 /// DMA program monopolizing it.
1000 bool sharesPinnedChannel(RouteEndpoint endpoint, DMAChannelDir dir) {
1001 // An out-of-order receiver takes each object into the buffer its header
1002 // names, so its channel keeps no order its fifos would have to agree on.
1003 auto dma = dyn_cast<ObjectFifoDmaEndpointOp>(endpoint.getOperation());
1004 if (dir == DMAChannelDir::S2MM)
1005 return !ObjectFifoCreateOp::sharedReceiveRefusal(
1006 tileOf(endpoint).isShimTile(), dma && dma.getOutOfOrder());
1007 if (!tileOf(endpoint).isShimTile() &&
1008 !(dma && dma.getReleaseStrategy() == ObjectFifoRelease::PushQueue))
1009 return false;
1010 bool hasPacketRoute = false;
1011 for (auto flow : device.getOps<RouteOp>()) {
1012 if (llvm::none_of(flow.getSourceNames(), [&](StringRef name) {
1013 return lookupEndpoint(name).getOperation() ==
1014 endpoint.getOperation();
1015 }))
1016 continue;
1017 if (!flow.getPacket())
1018 return false;
1019 hasPacketRoute = true;
1020 }
1021 return hasPacketRoute;
1022 }
1023
1024 LogicalResult assignChannels(DMAChannelAnalysis &channels,
1025 bool diagnose = true) {
1026 channelAssignments.clear();
1027 channelFailure = nullptr;
1028 bdShortfall = false;
1029 SmallVector<RouteEndpoint> pending;
1030 // BDs per placed (col, row, channel) as channels are handed out, for
1031 // choosing among a tile's channels by the BD ids they can use.
1032 DenseMap<std::tuple<int, int, int>, int64_t> demand;
1033 for (auto [col, row] : takenBDs.positions())
1034 for (auto [channel, bds] : takenBDs.at(device.getTargetModel(), col, row))
1035 demand[{col, row, channel}] += bds;
1036 auto noteDemand = [&](RouteEndpoint endpoint, int channel) {
1037 TileLike tile = tileOf(endpoint);
1038 auto col = tile.tryGetCol(), row = tile.tryGetRow();
1039 if (col && row)
1040 demand[{*col, *row, channel}] += bdsOf(endpoint);
1041 };
1042 for (auto endpoint : device.getOps<RouteEndpoint>()) {
1043 DMAChannelDir dir = endpoint.getRouteDirection();
1044 std::optional<int> channel = endpoint.getRouteChannel();
1045 if (!drawsOwnChannel(endpoint))
1046 continue;
1047
1048 if (channel) {
1049 if (reachesAdjacentTile(endpoint) &&
1050 *channel >= DMAChannelAnalysis::getDMAChannelLimit(tileOf(endpoint),
1051 dir, true)) {
1052 channelFailure = endpoint;
1053 if (!diagnose)
1054 return failure();
1055 return endpoint->emitOpError("pinned ")
1056 << stringifyDMAChannelDir(dir) << " DMA channel " << *channel
1057 << " cannot access adjacent MemTile buffers or locks";
1058 }
1059 if (channels.reservePinnedChannel(
1060 tileOf(endpoint), dir, *channel, endpoint.getOperation(),
1061 sharesPinnedChannel(endpoint, dir)) < 0) {
1062 if (!diagnose)
1063 return failure();
1064 auto diag = endpoint->emitOpError("pinned ");
1065 diag << stringifyDMAChannelDir(dir) << " DMA channel " << *channel
1066 << " is out of range or already in use on this tile";
1067 if (Operation *owner =
1068 channels.getDMAChannelOwner(tileOf(endpoint), dir, *channel))
1069 noteChannelOwner(diag, owner, channel);
1070 return failure();
1071 }
1072 noteDemand(endpoint, *channel);
1073 continue;
1074 }
1075 pending.push_back(endpoint);
1076 }
1077
1078 // A mem tile's pinned ends must fit the BD ids of the channels they pin,
1079 // as a plan of the tile's BD ids weighs every end.
1080 std::map<std::pair<int, int>, SmallVector<RouteEndpoint>> pinnedEnds;
1081 for (auto endpoint : device.getOps<RouteEndpoint>()) {
1082 TileLike tile = tileOf(endpoint);
1083 std::optional<int> col = tile.tryGetCol(), row = tile.tryGetRow();
1084 if (tile.isMemTile() && col && row && endpoint.getRouteChannel() &&
1085 drawsOwnChannel(endpoint))
1086 pinnedEnds[{*col, *row}].push_back(endpoint);
1087 }
1088 for (auto &[at, onTile] : pinnedEnds) {
1089 auto [col, row] = at;
1090 SmallVector<DMAChannelAnalysis::BDPlanEnd> ends;
1091 for (RouteEndpoint endpoint : onTile)
1092 ends.push_back(planEnd(endpoint, /*adjacent=*/false, /*keepPin=*/true));
1093 DenseMap<int, int64_t> taken =
1094 takenBDs.at(device.getTargetModel(), col, row);
1096 device.getTargetModel(), col, row, ends,
1097 [](DMAChannelDir, int) { return true; },
1098 [&](int channel) { return taken.lookup(channel); }))
1099 continue;
1100 int pinnedCol = col, pinnedRow = row;
1101 auto roomOf = [&](RouteEndpoint endpoint) {
1102 return bdRoom(tileOf(endpoint), pinnedCol, pinnedRow,
1103 *endpoint.getRouteChannel(), demand);
1104 };
1105 // The ends short of BD ids, the most demanding first.
1106 SmallVector<RouteEndpoint> starved;
1107 for (RouteEndpoint endpoint : onTile)
1108 if (roomOf(endpoint) < 0)
1109 starved.push_back(endpoint);
1110 assert(!starved.empty() &&
1111 "bdRoom and planBDChannels weigh the same BD ids");
1112 llvm::stable_sort(starved, [&](RouteEndpoint a, RouteEndpoint b) {
1113 return std::make_tuple(bdsOf(b), structuralRank.lookup(a)) <
1114 std::make_tuple(bdsOf(a), structuralRank.lookup(b));
1115 });
1116 RouteEndpoint deepest = starved.front();
1117 channelFailure = deepest;
1118 bdShortfall = true;
1119 if (!diagnose)
1120 return failure();
1121 InFlightDiagnostic diag =
1122 deepest->emitOpError("needs ")
1123 << bdsOf(deepest) << " buffer descriptors, but pinned "
1124 << stringifyDMAChannelDir(deepest.getRouteDirection())
1125 << " DMA channel " << *deepest.getRouteChannel()
1126 << " of its tile has " << roomOf(deepest) + bdsOf(deepest)
1127 << " left beside the ends on the channels sharing its BD ids";
1128 for (RouteEndpoint other : llvm::drop_begin(starved))
1129 diag.attachNote(other->getLoc())
1130 << "this end, on pinned "
1131 << stringifyDMAChannelDir(other.getRouteDirection())
1132 << " DMA channel " << *other.getRouteChannel() << ", needs "
1133 << bdsOf(other) << " of them too";
1134 return diag;
1135 }
1136
1137 // Endpoints reaching a spilled buffer draw from a restricted channel
1138 // range, so they are served before the unrestricted ones. Channels the
1139 // design programs itself come after the objectFIFOs', whose BDs they are
1140 // then chosen around, the most demanding first. The structural rank
1141 // settles the rest, so the order ops were written in never does.
1142 DenseMap<Operation *, int64_t> programBDs;
1143 for (auto endpoint : pending)
1144 if (isProgramOwned(endpoint))
1145 programBDs[endpoint.getOperation()] =
1146 endpointBDs(endpoint.getOperation());
1147 llvm::stable_sort(pending, [&](RouteEndpoint a, RouteEndpoint b) {
1148 bool aAdjacent = reachesAdjacentTile(a);
1149 bool bAdjacent = reachesAdjacentTile(b);
1150 if (aAdjacent != bAdjacent)
1151 return aAdjacent;
1152 bool aProgram = isProgramOwned(a), bProgram = isProgramOwned(b);
1153 if (aProgram != bProgram)
1154 return bProgram;
1155 int64_t aBDs = programBDs.lookup(a.getOperation());
1156 int64_t bBDs = programBDs.lookup(b.getOperation());
1157 if (aBDs != bBDs)
1158 return aBDs > bBDs;
1159 return structuralRank.lookup(a.getOperation()) <
1160 structuralRank.lookup(b.getOperation());
1161 });
1162
1163 // On a mem tile once short of BD ids, every end gets the channel a plan of
1164 // the tile's BD ids gives it, before any pool there is walked whole.
1165 DenseMap<Operation *, int> planned;
1166 for (Operation *tileOp : bdPlanned) {
1167 TileLike tile = cast<TileLike>(tileOp);
1168 std::optional<int> col = tile.tryGetCol(), row = tile.tryGetRow();
1169 if (!col || !row)
1170 continue;
1171 SmallVector<RouteEndpoint> onTile;
1172 SmallVector<DMAChannelAnalysis::BDPlanEnd> ends, unweighted;
1173 for (RouteEndpoint endpoint : pending) {
1174 if (tileOf(endpoint).getOperation() != tileOp)
1175 continue;
1176 onTile.push_back(endpoint);
1177 ends.push_back(planEnd(endpoint, reachesAdjacentTile(endpoint),
1178 /*keepPin=*/false));
1179 DMAChannelAnalysis::BDPlanEnd &zeroed =
1180 unweighted.emplace_back(ends.back());
1181 zeroed.bds = 0;
1182 }
1183 auto free = [&](DMAChannelDir dir, int channel) {
1184 return channels.isChannelFree(tile, dir, channel);
1185 };
1186 const AIETargetModel &target = device.getTargetModel();
1187 std::optional<SmallVector<int>> plan = DMAChannelAnalysis::planBDChannels(
1188 target, *col, *row, ends, free,
1189 [&](int channel) { return demand.lookup({*col, *row, channel}); });
1190 if (plan) {
1191 for (auto [endpoint, channel] : llvm::zip_equal(onTile, *plan))
1192 planned[endpoint.getOperation()] = channel;
1193 continue;
1194 }
1195 // Fails even with zero BDs: a channel shortage, handled below.
1196 if (!DMAChannelAnalysis::planBDChannels(target, *col, *row, unweighted,
1197 free, [](int) { return 0; }))
1198 continue;
1199 RouteEndpoint deepest =
1200 *llvm::max_element(onTile, [&](RouteEndpoint a, RouteEndpoint b) {
1201 return bdsOf(a) < bdsOf(b);
1202 });
1203 channelFailure = deepest;
1204 bdShortfall = true;
1205 if (!diagnose)
1206 return failure();
1207 int64_t total = 0;
1208 for (const DMAChannelAnalysis::BDPlanEnd &end : ends)
1209 total += end.bds;
1210 return deepest->emitOpError("needs ")
1211 << bdsOf(deepest) << " buffer descriptors, but the tile's "
1212 << ends.size() << " unpinned DMA ends need " << total
1213 << " in all, more than their channels' BD ids hold";
1214 }
1215
1216 for (auto endpoint : pending) {
1217 DMAChannelDir dir = endpoint.getRouteDirection();
1218 TileLike tile = tileOf(endpoint);
1219 bool adjacent = reachesAdjacentTile(endpoint);
1220 if (auto it = planned.find(endpoint.getOperation());
1221 it != planned.end()) {
1222 channelAssignments[endpoint.getOperation()] =
1223 channels.reservePinnedChannel(tile, dir, it->second,
1224 endpoint.getOperation());
1225 noteDemand(endpoint, it->second);
1226 continue;
1227 }
1228 // An objectFIFO end takes the first free channel, unless that channel's
1229 // BD ids have too few left for it: then the one with the most left.
1230 bool roomy = true;
1231 auto dma = dyn_cast<ObjectFifoDmaEndpointOp>(endpoint.getOperation());
1232 std::optional<int> col = tile.tryGetCol(), row = tile.tryGetRow();
1233 if (dma && col && row) {
1234 int limit = DMAChannelAnalysis::getDMAChannelLimit(tile, dir, adjacent);
1235 for (int free = 0; free < limit; ++free) {
1236 if (!channels.isChannelFree(tile, dir, free))
1237 continue;
1238 roomy = bdRoom(tile, *col, *row, free, demand) >= dma.getNumBDs();
1239 break;
1240 }
1241 }
1242 int channel = isProgramOwned(endpoint) || !roomy
1243 ? chooseChannel(channels, endpoint, demand, adjacent)
1244 : channels.getDMAChannelIndex(tile, dir, adjacent,
1245 endpoint.getOperation());
1246 if (channel >= 0 && dma && col && row && tile.isMemTile() &&
1247 bdRoom(tile, *col, *row, channel, demand) < dma.getNumBDs()) {
1248 channelFailure = endpoint;
1249 bdShortfall = true;
1250 if (!diagnose)
1251 return failure();
1252 return endpoint->emitOpError("needs ")
1253 << dma.getNumBDs() << " buffer descriptors, but channel "
1254 << channel << " of its tile has "
1255 << bdRoom(tile, *col, *row, channel, demand)
1256 << " left beside the channels sharing its BD ids";
1257 }
1258 if (channel < 0) {
1259 channelFailure = endpoint;
1260 if (!diagnose)
1261 return failure();
1262 int capacity =
1263 DMAChannelAnalysis::getDMAChannelLimit(tile, dir, adjacent);
1264 auto diag =
1265 tile.emitOpError(dir == DMAChannelDir::MM2S
1266 ? "number of output DMA channel exceeded!"
1267 : "number of input DMA channel exceeded!");
1268 diag << " requires at least " << capacity + 1 << " "
1269 << stringifyDMAChannelDir(dir) << " channels, but capacity is "
1270 << capacity;
1271 if (adjacent) {
1272 diag << " for adjacent MemTile access";
1273 }
1274 for (int i = 0; i < capacity; ++i)
1275 if (Operation *owner = channels.getDMAChannelOwner(tile, dir, i))
1276 noteChannelOwner(diag, owner, i);
1277 noteChannelOwner(diag, endpoint.getOperation());
1278 return failure();
1279 }
1280 channelAssignments[endpoint.getOperation()] = channel;
1281 noteDemand(endpoint, channel);
1282 }
1283 DenseSet<Operation *> claimedAllocations;
1284 for (auto [endpoint, alloc] : allocationSharers) {
1285 auto end = cast<RouteEndpoint>(endpoint);
1286 int channel = alloc.getChannelIndex();
1287 if (claimedAllocations.insert(alloc).second &&
1288 channels.reservePinnedChannel(tileOf(end), alloc.getChannelDir(),
1289 channel, endpoint, true) < 0) {
1290 channelFailure = end;
1291 if (!diagnose)
1292 return failure();
1293 auto diag = endpoint->emitOpError("cannot share ");
1294 diag << stringifyDMAChannelDir(alloc.getChannelDir()) << " DMA channel "
1295 << channel << ": already in use or unavailable";
1296 if (Operation *owner = channels.getDMAChannelOwner(
1297 tileOf(end), alloc.getChannelDir(), channel))
1298 noteChannelOwner(diag, owner, channel);
1299 return failure();
1300 }
1301 channelAssignments[endpoint] = channel;
1302 noteDemand(end, channel);
1303 }
1304 for (auto [sharer, owner] : channelSharers)
1305 channelAssignments[sharer] = channelAssignments.lookup(owner);
1306 // Unpinned runtime BDs did not steer the choice, so the image serves any
1307 // runtime sequence pinning the same ids, but they hold BDs while they
1308 // run, which the overcommit warning counts.
1309 for (auto &[at, bds] : taskBDs)
1310 demand[at] += bds;
1311 for (auto endpoint : device.getOps<RouteEndpoint>()) {
1312 TileLike tile = tileOf(endpoint);
1313 std::optional<int> col = tile.tryGetCol(), row = tile.tryGetRow();
1314 std::optional<int> channel = endpoint.getRouteChannel();
1315 if (auto it = channelAssignments.find(endpoint.getOperation());
1316 it != channelAssignments.end())
1317 channel = it->second;
1318 if (isProgramOwned(endpoint) && channel && col && row)
1319 demand[{*col, *row, *channel}] +=
1320 endpointTaskBDs(endpoint.getOperation());
1321 }
1322 channelDemand = std::move(demand);
1323 return success();
1324 }
1325
1326 /// Gives one more shim end of `exhausted` the channel of ends it is never in
1327 /// flight with, in the order ShimTransferSpans groups them, so only as many
1328 /// ends share as the tile needs. Packet headers tell a shared channel's ends
1329 /// apart.
1330 bool planShimSharing(TileLike exhausted, DMAChannelDir dir) {
1331 // Receiving ends share by the #aie.consumed_by proofs
1332 // aie-objectfifo-verify leaves; without them, by explicit permission only.
1333 ShimTransferSpans spans(
1334 device,
1335 [&](StringAttr symbol) {
1336 return ShimTransferSpans::endOf(device, symbol);
1337 },
1339 SmallVector<Operation *> candidates;
1340 SmallVector<StringAttr> fifos, names;
1341 for (auto endpoint : device.getOps<RouteEndpointOp>()) {
1342 if (endpoint.getBundle() != WireBundle::DMA ||
1343 endpoint.getChannelIndex() ||
1344 endpoint.getTile() != exhausted->getResult(0) ||
1345 endpoint.getRouteDirection() != dir)
1346 continue;
1347 candidates.push_back(endpoint);
1348 fifos.push_back(ShimTransferSpans::keyOf(endpoint));
1349 names.push_back(endpoint.getSymNameAttr());
1350 }
1351 SmallVector<ShimDMAAllocationOp> allocations;
1352 SmallVector<ShimTransferSpans::SharedChannel> shared;
1353 for (auto alloc : device.getOps<ShimDMAAllocationOp>()) {
1354 auto allowed = AIEDialect::ShareableWithAttrHelper(alloc->getContext())
1355 .getAttr(alloc);
1356 if (!allowed || alloc.getTile() != exhausted->getResult(0) ||
1357 alloc.getChannelDir() != dir)
1358 continue;
1359 SmallVector<StringAttr> listed;
1360 for (Attribute attr : allowed)
1361 if (auto symbol = dyn_cast<FlatSymbolRefAttr>(attr))
1362 listed.push_back(symbol.getAttr());
1363 bool pinned =
1364 llvm::any_of(device.getOps<RouteEndpoint>(), [&](RouteEndpoint end) {
1365 return end.getRouteBundle() == WireBundle::DMA &&
1366 sameTile(end.getTile(), alloc.getTile()) &&
1367 end.getRouteDirection() == dir &&
1368 end.getRouteChannel() == alloc.getChannelIndex();
1369 });
1370 allocations.push_back(alloc);
1371 shared.emplace_back(std::move(listed), pinned);
1372 }
1373 ShimTransferSpans::Plan plan = spans.plan(fifos, names, shared);
1374 for (unsigned channel : llvm::seq<unsigned>(0, shared.size()))
1375 for (auto [candidate, taken] : llvm::zip(candidates, plan.sharedChannel))
1376 if (taken == channel &&
1377 allocationSharers.try_emplace(candidate, allocations[channel])
1378 .second)
1379 return true;
1380 for (auto &members : plan.groups)
1381 for (unsigned sharer : llvm::drop_begin(members))
1382 if (channelSharers
1383 .insert({candidates[sharer], candidates[members.front()]})
1384 .second)
1385 return true;
1386 return false;
1387 }
1388
1389 /// Whether `pool` can be walked whole (ObjectFifoPoolOp::canWalkWhole),
1390 /// its ends taking no turns but those in `regrouped`, whose turns are being
1391 /// chosen again.
1392 bool canWalkWhole(ObjectFifoPoolOp pool,
1393 ArrayRef<ObjectFifoDmaEndpointOp> regrouped = {}) {
1394 return pool && pool.canWalkWhole() &&
1395 llvm::all_of(device.getOps<ObjectFifoDmaEndpointOp>(),
1396 [&](ObjectFifoDmaEndpointOp end) {
1397 return end.getPoolOp() != pool || !end.getTurns() ||
1398 llvm::is_contained(regrouped, end);
1399 });
1400 }
1401
1402 /// The DMA ends `dmas` of one mem tile that draw a channel of their own,
1403 /// and their pools in structural order, as a plan of the tile's BD ids
1404 /// weighs them with every buffer at home.
1405 struct HomeBDPlan {
1406 SmallVector<ObjectFifoPoolOp> pools;
1407 SmallVector<DMAChannelAnalysis::BDWalkPool> walkable;
1408 SmallVector<DMAChannelAnalysis::BDPlanEnd> ends;
1409 SmallVector<unsigned> poolOf;
1410 };
1411 HomeBDPlan homeBDPlan(ArrayRef<ObjectFifoDmaEndpointOp> dmas) {
1412 HomeBDPlan plan;
1413 for (auto dma : dmas)
1414 if (!llvm::is_contained(plan.pools, dma.getPoolOp()))
1415 plan.pools.push_back(dma.getPoolOp());
1416 llvm::stable_sort(plan.pools, [&](ObjectFifoPoolOp a, ObjectFifoPoolOp b) {
1417 return structuralRank.lookup(a) < structuralRank.lookup(b);
1418 });
1419 for (ObjectFifoPoolOp pool : plan.pools)
1420 plan.walkable.push_back(
1421 {pool.getDepth(), pool.getObjectSizeInBytes(), canWalkWhole(pool)});
1422 for (auto dma : dmas) {
1423 auto endpoint = cast<RouteEndpoint>(dma.getOperation());
1424 if (!drawsOwnChannel(endpoint))
1425 continue;
1426 plan.ends.push_back(planEnd(endpoint, /*adjacent=*/false,
1427 /*keepPin=*/true));
1428 plan.poolOf.push_back(llvm::find(plan.pools, dma.getPoolOp()) -
1429 plan.pools.begin());
1430 }
1431 return plan;
1432 }
1433
1434 /// Walks whichever pools need it: first walkHomeBDPools' plan for `tile`'s
1435 /// BD ids at home; once that needs none, the one pool
1436 /// DMAChannelAnalysis::nextPoolToWalk picks for what only the tile's real
1437 /// channels are short of. False once none is left to walk.
1438 bool walkForBDShortfall(TileLike tile,
1439 MutableArrayRef<ObjectFifoPoolOp> pools) {
1440 if (walkHomeBDPools(pools))
1441 return true;
1442 SmallVector<ObjectFifoDmaEndpointOp> dmas;
1443 for (auto dma : device.getOps<ObjectFifoDmaEndpointOp>())
1444 if (sameTile(dma.getTile(), tile->getResult(0)) && dma.getPoolOp())
1445 dmas.push_back(dma);
1446 HomeBDPlan plan = homeBDPlan(dmas);
1447 std::optional<unsigned> next = DMAChannelAnalysis::nextPoolToWalk(
1448 plan.ends, plan.poolOf, plan.walkable,
1449 SmallVector<bool>(plan.pools.size(), false));
1450 if (next)
1451 plan.pools[*next].setContiguous(true);
1452 return next.has_value();
1453 }
1454
1455 /// Walks whole, on each placed mem tile, a set of
1456 /// DMAChannelAnalysis::walkSetsThatFit's, chosen by placing `pools` as the
1457 /// SA placer does; every walkable pool when none fits. Those tiles then take
1458 /// their channels from that plan. False when nothing is left to walk.
1459 bool walkHomeBDPools(MutableArrayRef<ObjectFifoPoolOp> pools) {
1460 std::map<std::pair<int, int>, SmallVector<ObjectFifoDmaEndpointOp>> ends;
1461 for (auto dma : device.getOps<ObjectFifoDmaEndpointOp>()) {
1462 TileLike tile = tileOf(cast<RouteEndpoint>(dma.getOperation()));
1463 auto col = tile.tryGetCol(), row = tile.tryGetRow();
1464 if (tile.isMemTile() && col && row && dma.getPoolOp())
1465 ends[{*col, *row}].push_back(dma);
1466 }
1467 struct Tile {
1468 TileID at;
1469 HomeBDPlan home;
1470 DMAChannelAnalysis::BDWalkSets found;
1471 SmallVector<ObjectFifoDmaEndpointOp> dmas;
1472 unsigned applied = 0;
1473 };
1474 SmallVector<Tile, 0> tiles;
1475 // The tile's own programs and runtime tasks keep their channels and BD
1476 // ids, as the SA placer's plan of the tile does.
1477 DMAChannelAnalysis channels(device);
1478 for (auto &[at, dmas] : ends) {
1479 HomeBDPlan home = homeBDPlan(dmas);
1480 TileLike tile = tileOf(cast<RouteEndpoint>(dmas.front().getOperation()));
1481 DenseMap<int, int64_t> taken =
1482 takenBDs.at(device.getTargetModel(), at.first, at.second);
1483 DMAChannelAnalysis::BDWalkSets found =
1485 device.getTargetModel(), at.first, at.second, home.ends,
1486 home.poolOf, home.walkable,
1487 [&](DMAChannelDir dir, int channel) {
1488 return channels.isChannelFree(tile, dir, channel);
1489 },
1490 [&](int channel) { return taken.lookup(channel); });
1491 if (found.sets.empty() && !found.fits && !found.channelShort) {
1492 found.sets.emplace_back();
1493 found.bytes.push_back(0);
1494 for (auto [pool, walkable] : llvm::enumerate(home.walkable))
1495 if (walkable.walkable) {
1496 found.sets.back().push_back(pool);
1497 found.bytes.back() += walkable.depth * walkable.objectBytes;
1498 }
1499 }
1500 if (!found.sets.empty())
1501 tiles.push_back(
1502 {{at.first, at.second}, std::move(home), std::move(found), dmas});
1503 }
1504 auto setWalked = [&](Tile &tile, bool walked) {
1505 for (unsigned pool : tile.found.sets[tile.applied])
1506 tile.home.pools[pool].setContiguous(walked);
1507 };
1508 auto homeOf = [](ObjectFifoPoolOp pool) -> std::optional<TileID> {
1509 TileLike tile = pool.getTileLike();
1510 auto col = tile.tryGetCol(), row = tile.tryGetRow();
1511 if (!tile.isMemTile() || !col || !row)
1512 return std::nullopt;
1513 return TileID{*col, *row};
1514 };
1515 std::set<std::pair<int, int>> homeSet;
1516 for (ObjectFifoPoolOp pool : pools)
1517 if (std::optional<TileID> at = homeOf(pool))
1518 homeSet.insert({at->col, at->row});
1519 for (Tile &tile : tiles)
1520 homeSet.insert({tile.at.col, tile.at.row});
1521 SmallVector<TileID> homes;
1522 for (auto [col, row] : homeSet)
1523 homes.push_back({col, row});
1524 SmallVector<unsigned> componentIds =
1525 memTileSpillComponents(device.getTargetModel(), homes);
1526 std::map<std::pair<int, int>, unsigned> componentAt;
1527 for (auto [home, id] : llvm::zip_equal(homes, componentIds))
1528 componentAt[{home.col, home.row}] = id;
1529
1530 bool walkedAny = false;
1531 std::set<unsigned> searched;
1532 for (Tile &first : tiles) {
1533 unsigned component = componentAt[{first.at.col, first.at.row}];
1534 if (!searched.insert(component).second)
1535 continue;
1536 SmallVector<Tile *> members;
1537 for (Tile &tile : tiles)
1538 if (componentAt[{tile.at.col, tile.at.row}] == component)
1539 members.push_back(&tile);
1540 SmallVector<ObjectFifoPoolOp> componentPools;
1541 for (ObjectFifoPoolOp pool : pools)
1542 if (std::optional<TileID> at = homeOf(pool);
1543 at && componentAt[{at->col, at->row}] == component)
1544 componentPools.push_back(pool);
1545 SmallVector<SmallVector<int64_t>> bytes;
1546 for (Tile *tile : members)
1547 bytes.push_back(tile->found.bytes);
1548 auto apply = [&](ArrayRef<unsigned> choice) {
1549 for (auto [tile, set] : llvm::zip_equal(members, choice)) {
1550 setWalked(*tile, false);
1551 tile->applied = set;
1552 setWalked(*tile, true);
1553 }
1554 };
1555 DMAChannelAnalysis::WalkChoice choice =
1557 bytes,
1558 [&](ArrayRef<unsigned> choice) {
1559 apply(choice);
1560 SmallVector<ObjectFifoPoolOp> trial(componentPools);
1561 sizeOrder(trial);
1562 localPools.clear();
1563 return succeeded(planBuffers(trial));
1564 },
1566 apply(choice.sets);
1567 walkSearchStopped |= choice.stopped;
1568 for (Tile *tile : members) {
1569 if (tile->found.sets[tile->applied].empty())
1570 continue;
1571 walkedAny = true;
1572 for (auto dma : tile->dmas)
1573 bdPlanned.insert(
1574 tileOf(cast<RouteEndpoint>(dma.getOperation())).getOperation());
1575 }
1576 }
1577 return walkedAny;
1578 }
1579
1580 /// Whether, in every runtime sequence, the host issues each transfer
1581 /// through `fifo` before any wait: a turn chain waiting on that fifo's
1582 /// objects then waits on nothing the host does after the array has moved.
1583 bool hostMovesFirst(StringAttr fifo) {
1584 if (auto it = hostMovesFirstCache.find(fifo);
1585 it != hostMovesFirstCache.end())
1586 return it->second;
1587 bool result = hostMovesFirstUncached(fifo);
1588 hostMovesFirstCache[fifo] = result;
1589 return result;
1590 }
1591 bool hostMovesFirstUncached(StringAttr fifo) {
1592 SymbolTableCollection symbols;
1593 for (auto seq : device.getOps<RuntimeSequenceOp>()) {
1594 auto names = [&](Operation *op) {
1595 return fifo && AIEX::namesFifo(op, fifo.getValue(), symbols);
1596 };
1597 auto waits = [](Operation *op) {
1598 return isa<AIEX::NpuDmaWaitOp, AIEX::DMAAwaitTaskOp, AIEX::NpuSyncOp,
1599 AIEX::NpuMaskPollOp>(op);
1600 };
1601 bool waited = false;
1602 WalkResult walk = seq.walk<WalkOrder::PreOrder>([&](Operation *op) {
1603 if (waits(op)) {
1604 waited = true;
1605 return WalkResult::advance();
1606 }
1607 Operation *transfer = op;
1608 if (auto start = dyn_cast<AIEX::DMAStartTaskOp>(op))
1609 transfer = start.getTask().getDefiningOp();
1610 if (!transfer ||
1611 !isa<AIEX::NpuDmaMemcpyNdOp, AIEX::DMAConfigureTaskForOp,
1612 AIEX::DMAStartBdChainForOp>(transfer) ||
1613 isa<AIEX::DMAConfigureTaskForOp>(op) || !names(transfer))
1614 return WalkResult::advance();
1615 if (waited)
1616 return WalkResult::interrupt();
1617 for (Operation *parent = op->getParentOp(); parent != seq;
1618 parent = parent->getParentOp())
1619 if (parent
1620 ->walk([&](Operation *inner) {
1621 return waits(inner) ? WalkResult::interrupt()
1622 : WalkResult::advance();
1623 })
1624 .wasInterrupted())
1625 return WalkResult::interrupt();
1626 return WalkResult::advance();
1627 });
1628 if (walk.wasInterrupted())
1629 return false;
1630 }
1631 return true;
1632 }
1633
1634 /// The other end of the one route naming `endpoint`, when that route is a
1635 /// circuit between two objectFIFO DMA endpoints.
1636 ObjectFifoDmaEndpointOp circuitPeer(ObjectFifoDmaEndpointOp endpoint) {
1637 ObjectFifoDmaEndpointOp peer;
1638 StringRef name = endpoint.getSymName();
1639 for (RouteOp route : device.getOps<RouteOp>()) {
1640 SmallVector<StringRef> sources = llvm::to_vector(route.getSourceNames());
1641 SmallVector<StringRef> dests =
1642 llvm::to_vector(route.getDestinationNames());
1643 bool source = llvm::is_contained(sources, name);
1644 if (!source && !llvm::is_contained(dests, name))
1645 continue;
1646 if (peer || route.getPacket() || sources.size() != 1 || dests.size() != 1)
1647 return {};
1648 RouteEndpoint other = lookupEndpoint(source ? dests[0] : sources[0]);
1649 peer = other ? dyn_cast<ObjectFifoDmaEndpointOp>(other.getOperation())
1650 : ObjectFifoDmaEndpointOp();
1651 if (!peer)
1652 return {};
1653 }
1654 return peer;
1655 }
1656
1657 /// The one core endpoint working through `endpoint`'s pool from the other
1658 /// side.
1659 ObjectFifoCoreEndpointOp coreEndOf(ObjectFifoDmaEndpointOp endpoint) {
1660 ObjectFifoCoreEndpointOp found;
1661 for (auto core : device.getOps<ObjectFifoCoreEndpointOp>()) {
1662 if (core.getPool() != endpoint.getPool())
1663 continue;
1664 if (found || core.drains() == endpoint.drains())
1665 return {};
1666 found = core;
1667 }
1668 return found;
1669 }
1670
1671 /// How many turns in `turns` land on each of `ends`, and the descriptors
1672 /// each unrolled pass over it takes (0 for a pool already walked whole):
1673 /// the pairs turnPasses takes.
1674 static SmallVector<std::pair<int64_t, int64_t>>
1675 turnCounts(ArrayRef<ObjectFifoDmaEndpointOp> ends, ArrayRef<unsigned> turns) {
1676 SmallVector<std::pair<int64_t, int64_t>> counts;
1677 for (auto [i, constEnd] : llvm::enumerate(ends)) {
1678 ObjectFifoDmaEndpointOp end = constEnd;
1679 counts.push_back({llvm::count(turns, i), end.getPoolOp().getContiguous()
1680 ? 0
1681 : end.getNumDescriptors()});
1682 }
1683 return counts;
1684 }
1685
1686 /// Whether a chain moving `turns` over `ends` can walk each contiguous pool
1687 /// with one descriptor per turn of its unrolled passes, each stepping over
1688 /// the others' objects: they must divide the pool's objects.
1689 static bool contiguousWalkersFit(ArrayRef<ObjectFifoDmaEndpointOp> ends,
1690 ArrayRef<unsigned> turns) {
1691 SmallVector<std::pair<int64_t, int64_t>> counts = turnCounts(ends, turns);
1692 int64_t passes = turnPasses(counts);
1693 for (auto [i, constEnd] : llvm::enumerate(ends)) {
1694 ObjectFifoDmaEndpointOp end = constEnd;
1695 if (end.getPoolOp().getContiguous() &&
1696 (end.walksStream() ||
1697 end.getPoolOp().getDepth() % (counts[i].first * passes)))
1698 return false;
1699 }
1700 return true;
1701 }
1702
1703 /// Gives `ends` one channel, the k-th object belonging to `ends[order[k]]`.
1704 void takeTurns(MutableArrayRef<ObjectFifoDmaEndpointOp> ends,
1705 ArrayRef<unsigned> order) {
1706 SmallVector<Attribute> names;
1707 for (unsigned i : order)
1708 names.push_back(FlatSymbolRefAttr::get(ends[i].getSymNameAttr()));
1709 ArrayAttr turns = builder.getArrayAttr(names);
1710 Operation *owner = ends[order.front()];
1711 channelSharers.erase(owner);
1712 for (ObjectFifoDmaEndpointOp end : ends) {
1713 end.setTurnsAttr(turns);
1714 if (end != owner)
1715 channelSharers[end] = owner;
1716 }
1717 }
1718
1719 /// Gives one more end of `exhausted` the channel of others whose objects
1720 /// the same core needs in a fixed order, read off its program, so only as
1721 /// many ends share as the tile needs. A circuit carries one stream, so the
1722 /// ends at the routes' other ends take the same turns.
1723 bool planTurnSharing(TileLike exhausted, DMAChannelDir dir) {
1724 // `coreEndOf`/`circuitPeer` each rescan the whole device; neither's
1725 // domain (core endpoints, routes) changes within this function (only
1726 // pool `contiguous` flags and endpoints' `turns` attrs do), so caching
1727 // them once here turns every lookup below from O(device size) into O(1).
1728 DenseMap<Operation *, ObjectFifoCoreEndpointOp> coreEndCache;
1729 DenseMap<Operation *, ObjectFifoDmaEndpointOp> circuitPeerCache;
1730 DenseMap<Operation *, SmallVector<ObjectFifoDmaEndpointOp>> poolEnds;
1731 for (auto dma : device.getOps<ObjectFifoDmaEndpointOp>()) {
1732 coreEndCache[dma] = coreEndOf(dma);
1733 circuitPeerCache[dma] = circuitPeer(dma);
1734 poolEnds[dma.getPoolOp()].push_back(dma);
1735 }
1736 auto endsOf = [&](Operation *pool) -> ArrayRef<ObjectFifoDmaEndpointOp> {
1737 auto it = poolEnds.find(pool);
1738 return it == poolEnds.end() ? ArrayRef<ObjectFifoDmaEndpointOp>()
1739 : it->second;
1740 };
1741 // Each circuit destination's one sender, a broadcast's included, and the
1742 // ends a circuit joins to the shim alone, which wait on the host only.
1743 DenseMap<Operation *, ObjectFifoDmaEndpointOp> senderOf;
1744 DenseSet<Operation *> byShim;
1745 auto onShim = [](RouteEndpoint end) {
1746 auto tile = end.getTile().getDefiningOp<TileLike>();
1747 return tile && tile.isShimTile();
1748 };
1749 for (RouteOp route : device.getOps<RouteOp>()) {
1750 SmallVector<StringRef> sources = llvm::to_vector(route.getSourceNames());
1751 RouteEndpoint source = sources.size() == 1 && !route.getPacket()
1752 ? lookupEndpoint(sources[0])
1753 : RouteEndpoint();
1754 if (!source)
1755 continue;
1756 auto sender = dyn_cast<ObjectFifoDmaEndpointOp>(source.getOperation());
1757 SmallVector<RouteEndpoint> dests;
1758 for (StringRef dest : route.getDestinationNames())
1759 dests.push_back(lookupEndpoint(dest));
1760 for (RouteEndpoint end : dests) {
1761 if (end && sender)
1762 senderOf[end.getOperation()] = sender;
1763 if (end && onShim(source))
1764 byShim.insert(end.getOperation());
1765 }
1766 if (llvm::all_of(dests,
1767 [&](RouteEndpoint end) { return end && onShim(end); }))
1768 byShim.insert(source.getOperation());
1769 }
1770 auto cachedCoreEnd = [&](ObjectFifoDmaEndpointOp dma) {
1771 return coreEndCache.lookup(dma);
1772 };
1773 auto cachedCircuitPeer = [&](ObjectFifoDmaEndpointOp dma) {
1774 return circuitPeerCache.lookup(dma);
1775 };
1776 SmallVector<ObjectFifoDmaEndpointOp> candidates;
1777 for (auto dma : device.getOps<ObjectFifoDmaEndpointOp>())
1778 if (sameTile(dma.getTile(), exhausted->getResult(0)) &&
1779 dma.getRouteDirection() == dir && cachedCoreEnd(dma) &&
1780 (dma.getTurns() ? turnEndpoints(dma).front() : dma).canTakeTurns())
1781 if (ObjectFifoDmaEndpointOp peer = cachedCircuitPeer(dma);
1782 peer && peer.canTakeTurns())
1783 candidates.push_back(dma);
1784 llvm::stable_sort(candidates, [&](Operation *a, Operation *b) {
1785 return structuralRank.lookup(a) < structuralRank.lookup(b);
1786 });
1787 LLVM_DEBUG({
1788 llvm::dbgs() << "turns on " << exhausted->getLoc() << ": "
1789 << candidates.size() << " candidate ends\n";
1790 for (auto dma : device.getOps<ObjectFifoDmaEndpointOp>())
1791 if (sameTile(dma.getTile(), exhausted->getResult(0)) &&
1792 dma.getRouteDirection() == dir)
1793 llvm::dbgs() << " " << dma.getSymName() << ": core end "
1794 << bool(cachedCoreEnd(dma)) << ", takes turns "
1795 << dma.canTakeTurns() << ", peer takes turns "
1796 << (cachedCircuitPeer(dma) &&
1797 cachedCircuitPeer(dma).canTakeTurns())
1798 << "\n";
1799 });
1800 auto groupOf = [](ObjectFifoDmaEndpointOp end) {
1801 SmallVector<ObjectFifoDmaEndpointOp> group = turnEndpoints(end);
1802 return group.empty() ? SmallVector<ObjectFifoDmaEndpointOp>{end} : group;
1803 };
1804 for (auto [i, a] : llvm::enumerate(candidates)) {
1805 for (ObjectFifoDmaEndpointOp b : llvm::drop_begin(candidates, i + 1)) {
1806 SmallVector<ObjectFifoDmaEndpointOp> group = groupOf(a);
1807 if (llvm::is_contained(group, b))
1808 continue;
1809 llvm::append_range(group, groupOf(b));
1810 SmallVector<ObjectFifoCoreEndpointOp> cores;
1811 SmallVector<ObjectFifoDmaEndpointOp> peers;
1812 SmallVector<int64_t> depths;
1813 for (ObjectFifoDmaEndpointOp end : group) {
1814 cores.push_back(cachedCoreEnd(end));
1815 peers.push_back(cachedCircuitPeer(end));
1816 depths.push_back(end.getPoolOp().getDepth());
1817 }
1818 if (llvm::any_of(peers, [&](ObjectFifoDmaEndpointOp peer) {
1819 return !sameTile(peer.getTile(), peers.front().getTile()) ||
1820 llvm::any_of(turnEndpoints(peer), [&](auto other) {
1821 return !llvm::is_contained(peers, other);
1822 });
1823 })) {
1824 LLVM_DEBUG(llvm::dbgs()
1825 << " " << a.getSymName() << " + " << b.getSymName()
1826 << ": senders on different tiles\n");
1827 continue;
1828 }
1829 CoreTurns turns;
1830 std::string reason;
1831 if (succeeded(turns.read(cores, reason)) && !turns.keepsUp(depths))
1832 reason = "would stall";
1833 // The peers' chain moves the same turns, so a core working through
1834 // their pools, or through the pools that feed them circuit by circuit,
1835 // must keep up with that order too, through all those pools' depths.
1836 // A peer reached from the shim waits on the host, so the host must
1837 // move it before it waits on anything; one whose feeding core the walk
1838 // cannot find refuses the turns. Peers that split one pool between
1839 // them, draining it or filling it, each carry a part of what the core
1840 // at the pool's other end moves in one piece, so they count as one peer
1841 // of that core's when every segment on their side takes these turns.
1842 SmallVector<ObjectFifoCoreEndpointOp> peerCores;
1843 SmallVector<int64_t> peerDepths;
1844 SmallVector<unsigned> fed(peers.size(), ~0u);
1845 DenseMap<Operation *, unsigned> fedByPool;
1846 bool lost = false, hostWaits = false;
1847 auto wholePool = [&](ObjectFifoDmaEndpointOp peer) {
1848 bool drains = peer.drains();
1849 return peer.getSegments() &&
1850 llvm::all_of(endsOf(peer.getPoolOp()), [&](auto end) {
1851 return end.drains() != drains ||
1852 llvm::is_contained(peers, end);
1853 });
1854 };
1855 for (auto [i, peer] : llvm::enumerate(peers)) {
1856 if (wholePool(peer)) {
1857 auto segment = fedByPool.find(peer.getPoolOp());
1858 if (segment != fedByPool.end()) {
1859 fed[i] = segment->second;
1860 continue;
1861 }
1862 }
1863 int64_t depth = peer.getPoolOp().getDepth();
1864 ObjectFifoCoreEndpointOp core = cachedCoreEnd(peer);
1865 SmallPtrSet<Operation *, 8> seen;
1866 for (ObjectFifoDmaEndpointOp at = peer; !core;) {
1867 SmallVector<ObjectFifoDmaEndpointOp> across;
1868 for (ObjectFifoDmaEndpointOp end : endsOf(at.getPoolOp()))
1869 if (end.drains() != at.drains())
1870 across.push_back(end);
1871 if (!seen.insert(at).second || across.size() != 1) {
1872 lost = true;
1873 break;
1874 }
1875 if (byShim.contains(across.front())) {
1876 hostWaits |= !hostMovesFirst(across.front().getFifoNameAttr());
1877 break;
1878 }
1879 at = across.front().drains() ? cachedCircuitPeer(across.front())
1880 : senderOf.lookup(across.front());
1881 if (!at) {
1882 lost = true;
1883 break;
1884 }
1885 depth += at.getPoolOp().getDepth();
1886 core = cachedCoreEnd(at);
1887 }
1888 if (!core)
1889 continue;
1890 if (llvm::is_contained(peerCores, core)) {
1891 lost = true;
1892 continue;
1893 }
1894 fed[i] = peerCores.size();
1895 if (wholePool(peer))
1896 fedByPool[peer.getPoolOp()] = fed[i];
1897 peerCores.push_back(core);
1898 peerDepths.push_back(depth);
1899 }
1900 if (reason.empty() && lost)
1901 reason = "a peer's feeding core is not known, or feeds two peers";
1902 if (reason.empty() && hostWaits)
1903 reason = "the host waits before it moves a peer fed by the shim";
1904 // A turn on a segment past every object its pool's segments have
1905 // reached asks the core for the next one; the objects the segments
1906 // hold open at once must fit the pool, and every segment takes one
1907 // part of each object.
1908 SmallVector<unsigned> peerOrder;
1909 DenseMap<unsigned, int64_t> asked;
1910 SmallVector<int64_t> taken(peers.size(), 0);
1911 for (unsigned turn : turns.turns()) {
1912 if (fed[turn] == ~0u)
1913 continue;
1914 int64_t part = ++taken[turn];
1915 if (part > asked[fed[turn]]) {
1916 asked[fed[turn]] = part;
1917 peerOrder.push_back(fed[turn]);
1918 }
1919 ObjectFifoPoolOp pool = peers[turn].getPoolOp();
1920 int64_t fewest = part;
1921 for (auto [j, other] : llvm::enumerate(peers))
1922 if (other.getPoolOp() == pool)
1923 fewest = std::min(fewest, taken[j]);
1924 if (reason.empty() && asked[fed[turn]] - fewest > pool.getDepth())
1925 reason = "a pool's segments hold more objects open than it has";
1926 }
1927 for (auto [i, peer] : llvm::enumerate(peers))
1928 for (auto [j, other] : llvm::enumerate(peers))
1929 if (reason.empty() && other.getPoolOp() == peer.getPoolOp() &&
1930 taken[i] != taken[j])
1931 reason = "a pool's segments take different counts of turns";
1932 if (reason.empty() && !peerCores.empty()) {
1933 CoreTurns peerTurns;
1934 if (llvm::any_of(peerCores, [&](ObjectFifoCoreEndpointOp c) {
1935 return !sameTile(c.getTile(), peerCores.front().getTile());
1936 }))
1937 reason = "several cores feed the peers";
1938 else if (succeeded(peerTurns.read(peerCores, reason)) &&
1939 !peerTurns.keepsUp(peerOrder, peerDepths))
1940 reason = "the core at the peers' far end would stall";
1941 }
1942 // Over plain pools the chain unrolls to whole passes over each; past
1943 // the peers' channel BDs, walking them whole takes one a turn.
1944 bool overflows = false;
1945 if (reason.empty()) {
1946 SmallVector<std::pair<int64_t, int64_t>> counts =
1947 turnCounts(peers, turns.turns());
1948 TileLike tile = peers.front().getTileLike();
1949 std::optional<int> col = tile.tryGetCol(), row = tile.tryGetRow();
1950 overflows =
1951 col && row &&
1952 turnPasses(counts) * static_cast<int64_t>(turns.turns().size()) >
1953 device.getTargetModel().getNumBDsForChannel(*col, *row, 0);
1954 }
1955 // Beside a pool walked whole, the others' descriptors must come round
1956 // each pass, which walking them whole as well lines up.
1957 // A pool whose other end already takes turns may be walked whole too,
1958 // where those turns still line up.
1959 SmallVector<ObjectFifoPoolOp> walked;
1960 if (reason.empty() &&
1961 (overflows || !contiguousWalkersFit(peers, turns.turns())))
1962 for (ObjectFifoDmaEndpointOp peer : peers) {
1963 ObjectFifoPoolOp pool = peer.getPoolOp();
1964 SmallVector<ObjectFifoDmaEndpointOp> others;
1965 for (auto end : device.getOps<ObjectFifoDmaEndpointOp>())
1966 if (end.getPoolOp() == pool && end.getTurns() &&
1967 !llvm::is_contained(peers, end))
1968 others.push_back(end);
1969 SmallVector<ObjectFifoDmaEndpointOp> ignored(peers);
1970 llvm::append_range(ignored, others);
1971 if (!canWalkWhole(pool, ignored)) {
1972 LLVM_DEBUG(llvm::dbgs() << " " << pool.getSymName()
1973 << " cannot be walked whole\n");
1974 continue;
1975 }
1976 pool.setContiguous(true);
1977 bool linedUp =
1978 llvm::all_of(others, [&](ObjectFifoDmaEndpointOp end) {
1979 SmallVector<ObjectFifoDmaEndpointOp> ends =
1980 turnEndpoints(end);
1981 SmallVector<unsigned> order;
1982 for (auto name :
1983 end.getTurnsAttr().getAsRange<FlatSymbolRefAttr>())
1984 order.push_back(
1985 llvm::find_if(ends,
1986 [&](ObjectFifoDmaEndpointOp e) {
1987 return e.getSymNameAttr() ==
1988 name.getAttr();
1989 }) -
1990 ends.begin());
1991 return contiguousWalkersFit(ends, order);
1992 });
1993 LLVM_DEBUG(
1994 llvm::dbgs()
1995 << " " << pool.getSymName() << " walked whole"
1996 << (linedUp ? "" : ", but its other turns would not line up")
1997 << "\n");
1998 if (linedUp) {
1999 walked.push_back(pool);
2000 turnWalked.insert(pool);
2001 } else
2002 pool.setContiguous(false);
2003 }
2004 if (reason.empty() && (!contiguousWalkersFit(group, turns.turns()) ||
2005 !contiguousWalkersFit(peers, turns.turns()))) {
2006 reason = "a contiguous pool's objects do not divide among its turns";
2007 for (ObjectFifoPoolOp pool : walked)
2008 pool.setContiguous(false);
2009 }
2010 if (!reason.empty()) {
2011 LLVM_DEBUG(llvm::dbgs() << " " << a.getSymName() << " + "
2012 << b.getSymName() << ": " << reason << "\n");
2013 continue;
2014 }
2015 takeTurns(group, turns.turns());
2016 takeTurns(peers, turns.turns());
2017 return true;
2018 }
2019 }
2020 return false;
2021 }
2022
2023 /// A route reaching or leaving a shared shim channel carries a packet
2024 /// header, its id distinct from those of the routes it shares the channel
2025 /// with. Other shared channels reuse the same ids: the router keeps flows
2026 /// with one id apart wherever their destinations differ.
2027 LogicalResult headShimSharingRoutes() {
2028 DenseMap<Operation *, Operation *> channelOf;
2029 for (auto [sharer, owner] : channelSharers) {
2030 if (!tileOf(cast<RouteEndpoint>(owner)).isShimTile())
2031 continue;
2032 channelOf[sharer] = owner;
2033 channelOf[owner] = owner;
2034 }
2035 for (auto [endpoint, alloc] : allocationSharers)
2036 channelOf[endpoint] = alloc.getOperation();
2037 auto channelsOf = [&](RouteOp route) {
2038 SmallVector<Operation *> channels;
2039 auto note = [&](StringRef name) {
2040 if (auto endpoint = lookupEndpoint(name);
2041 endpoint && channelOf.count(endpoint.getOperation()))
2042 channels.push_back(channelOf.lookup(endpoint.getOperation()));
2043 };
2044 llvm::for_each(route.getSourceNames(), note);
2045 llvm::for_each(route.getDestinationNames(), note);
2046 return channels;
2047 };
2048 DenseMap<Operation *, DenseSet<int>> idsOn;
2049 for (auto route : device.getOps<RouteOp>())
2050 if (PacketInfoAttr packet = route.getPacketAttr();
2051 packet && packet.isAssigned())
2052 for (Operation *channel : channelsOf(route))
2053 idsOn[channel].insert(packet.assignedId());
2054 PacketIdSpace ids(device);
2055 SmallVector<int> reused;
2056 for (auto route : device.getOps<RouteOp>()) {
2057 SmallVector<Operation *> channels = channelsOf(route);
2058 if (route.getPacket() || channels.empty())
2059 continue;
2060 auto freeOnAll = [&](int id) {
2061 return llvm::none_of(channels, [&](Operation *channel) {
2062 return idsOn[channel].contains(id);
2063 });
2064 };
2065 std::optional<int> id;
2066 if (auto *it = llvm::find_if(reused, freeOnAll); it != reused.end())
2067 id = *it;
2068 else if ((id = ids.takeLowestFrom()))
2069 reused.push_back(*id);
2070 else
2071 return route.emitOpError("shares a shim channel, but no packet id is "
2072 "left to tell its transfers apart");
2073 for (Operation *channel : channels)
2074 idsOn[channel].insert(*id);
2075 route.setPacketAttr(PacketInfoAttr::get(builder.getContext(), 0,
2076 static_cast<uint16_t>(*id)));
2077 }
2078 return success();
2079 }
2080
2081 /// Channels are chosen by BD room but never refused for lack of it: a task
2082 /// that frees its BDs before the next starts lets demand exceed the BDs.
2083 /// Otherwise BD id assignment fails, so say where.
2084 void warnOvercommittedBDs() {
2085 const AIETargetModel &target = device.getTargetModel();
2086 for (auto endpoint : device.getOps<RouteEndpoint>()) {
2087 auto it = channelAssignments.find(endpoint.getOperation());
2088 TileLike tile = tileOf(endpoint);
2089 std::optional<int> col = tile.tryGetCol(), row = tile.tryGetRow();
2090 if (it == channelAssignments.end() || !isProgramOwned(endpoint) || !col ||
2091 !row)
2092 continue;
2093 int channel = it->second;
2094 int64_t room = bdRoom(tile, *col, *row, channel, channelDemand);
2095 if (room >= 0)
2096 continue;
2097 int64_t numBDs = target.getNumBDsForChannel(*col, *row, channel);
2098 endpoint->emitWarning("")
2099 << stringifyDMAChannelDir(endpoint.getRouteDirection())
2100 << " DMA channel " << channel << " can use " << numBDs
2101 << " BDs, but it and the channels sharing them need " << numBDs - room
2102 << " at once; BD id assignment fails unless tasks free their BDs "
2103 "before others start";
2104 }
2105 }
2106
2107 /// Keep a successful largest-first allocation unchanged. On channel
2108 /// exhaustion, try keeping an affected pool's resources local, cheapest
2109 /// first. Existing buffers and locks never move. Each DMA accesses every
2110 /// object in its pool, even when it selects only one segment. Reserving that
2111 /// pool once can therefore free several restricted channels. This is a
2112 /// bounded repair of the greedy buffer placement, not an exhaustive solver
2113 /// for tile placement or memory packing.
2114 LogicalResult planAllocation(ArrayRef<ObjectFifoPoolOp> pools,
2115 std::set<std::vector<unsigned>> &tried) {
2116 std::vector<unsigned> key;
2117 for (auto [index, pool] : llvm::enumerate(pools)) {
2118 if (auto tile = localPools.lookup(pool)) {
2119 auto placed = cast<TileLike>(tile.getDefiningOp());
2120 auto col = placed.tryGetCol(), row = placed.tryGetRow();
2121 assert(col && row && "locality repair requires resolved coordinates");
2122 key.push_back(index);
2123 key.push_back(*col);
2124 key.push_back(*row);
2125 }
2126 }
2127 if (tried.size() >= 64 || !tried.insert(key).second ||
2128 failed(planBuffers(pools)) || failed(planLocks(pools)))
2129 return failure();
2130 DMAChannelAnalysis channels(device);
2131 if (succeeded(assignChannels(channels, /*diagnose=*/false)))
2132 return success();
2133 if (!channelFailure || !tileOf(channelFailure).isMemTile() ||
2134 !tileOf(channelFailure).tryGetCol() ||
2135 !tileOf(channelFailure).tryGetRow())
2136 return failure();
2137
2138 Value localTile = channelFailure.getTile();
2139 SmallVector<ObjectFifoPoolOp> candidates;
2140 for (auto dma : device.getOps<ObjectFifoDmaEndpointOp>()) {
2141 auto endpoint = cast<RouteEndpoint>(dma.getOperation());
2142 auto pool = dma.getPoolOp();
2143 if (!pool || localPools.contains(pool) ||
2144 !sameTile(endpoint.getTile(), channelFailure.getTile()) ||
2145 endpoint.getRouteDirection() != channelFailure.getRouteDirection() ||
2146 (channelFailure.getRouteChannel() && endpoint != channelFailure) ||
2147 (endpoint.getRouteChannel() && endpoint != channelFailure) ||
2148 !ownReachesAdjacentTile(endpoint) ||
2149 llvm::is_contained(candidates, pool))
2150 continue;
2151 candidates.push_back(pool);
2152 }
2153 llvm::stable_sort(candidates, [&](ObjectFifoPoolOp a, ObjectFifoPoolOp b) {
2154 int64_t aBytes =
2155 a.getBuffers() ? 0 : a.getObjectSizeInBytes() * a.getDepth();
2156 int64_t bBytes =
2157 b.getBuffers() ? 0 : b.getObjectSizeInBytes() * b.getDepth();
2158 if (aBytes != bBytes)
2159 return aBytes < bBytes;
2160 return structuralRank.lookup(a) < structuralRank.lookup(b);
2161 });
2162 for (auto pool : candidates) {
2163 localPools[pool] = localTile;
2164 if (succeeded(planAllocation(pools, tried)))
2165 return success();
2166 localPools.erase(pool);
2167 }
2168 return failure();
2169 }
2170
2171 /// A packet-switched flow shares the stream with others, so every buffer
2172 /// descriptor the source emits has to carry the packet header.
2173 /// One packet flow carries every source of the route: each stamps the same
2174 /// header, and their packets share the destination channels.
2175 LogicalResult lowerPacketFlow(RouteOp flow, ArrayRef<RouteEndpoint> sources,
2176 PacketInfoAttr header) {
2177 int packetID = header.assignedId();
2178 for (auto [name, endpoint] : llvm::zip_equal(
2179 flow.getSources().getAsRange<FlatSymbolRefAttr>(), sources)) {
2180 RouteEndpoint source = endpoint;
2181 // Written out in turn order after the last route.
2182 if (auto dma = dyn_cast<ObjectFifoDmaEndpointOp>(*source);
2183 dma && dma.getDispatch()) {
2184 dispatchHeaders[dma][*flow.getDestinationNames().begin()] = header;
2185 continue;
2186 }
2187 if (sourcedFlows.at(name.getAttr()).size() == 1)
2188 source.setRoutePacket(header);
2189 }
2190
2191 // An out-of-order receiver reads the buffer it should fill out of the
2192 // header, so the header has to reach its DMA.
2193 bool keepHeader = flow.getKeepPktHeader();
2194 for (StringRef destName : flow.getDestinationNames())
2195 if (auto dma = dyn_cast<ObjectFifoDmaEndpointOp>(
2196 lookupEndpoint(destName).getOperation()))
2197 keepHeader |= dma.getOutOfOrder();
2198
2199 builder.setInsertionPoint(flow);
2200 auto packetFlow = PacketFlowOp::create(
2201 builder, flow.getLoc(),
2202 builder.getIntegerAttr(builder.getI8Type(), packetID),
2203 keepHeader ? builder.getBoolAttr(true) : nullptr, nullptr);
2204 OpBuilder::InsertionGuard g(builder);
2205 Block &ports = packetFlow.getRegion().emplaceBlock();
2206 builder.setInsertionPointToStart(&ports);
2207 EndOp::create(builder, flow.getLoc());
2208
2209 builder.setInsertionPointToStart(&ports);
2210 for (RouteEndpoint source : sources) {
2211 PacketSourceOp::create(builder, flow.getLoc(), source.getTile(),
2212 source.getRouteBundle(), channelOf(source));
2213 }
2214 for (StringRef destName : flow.getDestinationNames()) {
2215 auto dest = lookupEndpoint(destName);
2216 // An out-of-order receiver matches on the header rather than walking a
2217 // chain, so its descriptors carry the id too.
2218 if (auto dma = dyn_cast<ObjectFifoDmaEndpointOp>(dest.getOperation()))
2219 if (dma.getOutOfOrder())
2220 dest.setRoutePacket(header);
2221 PacketDestOp::create(builder, flow.getLoc(), dest.getTile(),
2222 dest.getRouteBundle(), channelOf(dest));
2223 }
2224 return success();
2225 }
2226
2227 /// Assigned before flows are lowered, so every endpoint has one by now.
2228 int channelOf(RouteEndpoint endpoint) {
2229 std::optional<int> channel = endpoint.getRouteChannel();
2230 assert(channel && "channels are assigned before flows are lowered");
2231 return *channel;
2232 }
2233
2234 RouteEndpoint lookupEndpoint(StringRef name) {
2235 return dyn_cast_or_null<RouteEndpoint>(SymbolTable::lookupNearestSymbolFrom(
2236 device, StringAttr::get(device.getContext(), name)));
2237 }
2238
2239 LogicalResult lowerFlows() {
2240 // Independent core-pushed senders need different routing IDs even when
2241 // their descriptors are submitted at different times.
2242 DenseMap<std::tuple<Value, int, int>, Operation *> pushedPacketSources;
2243 for (RouteOp flow : device.getOps<RouteOp>()) {
2244 auto packet = flow.getPacket();
2245 if (!packet || !packet->isAssigned())
2246 continue;
2247 for (StringRef name : flow.getSourceNames()) {
2248 auto source = dyn_cast<ObjectFifoDmaEndpointOp>(
2249 lookupEndpoint(name).getOperation());
2250 if (!source ||
2251 source.getReleaseStrategy() != ObjectFifoRelease::PushQueue)
2252 continue;
2253 auto [it, inserted] = pushedPacketSources.try_emplace(
2254 std::make_tuple(source.getTile(), channelOf(source),
2255 packet->assignedId()),
2256 source.getOperation());
2257 if (!inserted && it->second != source.getOperation()) {
2258 auto diag = source.emitOpError(
2259 "core-pushed senders sharing an MM2S channel require distinct "
2260 "packet IDs");
2261 diag.attachNote(it->second->getLoc()) << "other sender is here";
2262 return failure();
2263 }
2264 }
2265 }
2266 DenseSet<std::tuple<Value, int, Value, int>> circuits;
2267 for (RouteOp flow : device.getOps<RouteOp>())
2268 for (auto name : flow.getSources().getAsRange<FlatSymbolRefAttr>())
2269 sourcedFlows[name.getAttr()].push_back(flow);
2270 for (auto flow : device.getOps<RouteOp>()) {
2271 SmallVector<RouteEndpoint> sources;
2272 for (StringRef name : flow.getSourceNames()) {
2273 sources.push_back(lookupEndpoint(name));
2274 }
2275 loweredFlows.push_back(flow);
2276
2277 // Which switching a route gets was settled upstream of this pass: the
2278 // header is on the route, and --aie-assign-packet-ids gave it its id.
2279 if (std::optional<PacketInfoAttr> packet = flow.getPacket()) {
2280 if (!packet->isAssigned()) {
2281 return flow.emitOpError("has a packet header with no pkt_id; run "
2282 "--aie-assign-packet-ids before this pass");
2283 }
2284 if (failed(lowerPacketFlow(flow, sources, *packet))) {
2285 return failure();
2286 }
2287 continue;
2288 }
2289
2290 // The verifier keeps a circuit route to one source.
2291 RouteEndpoint source = sources.front();
2292
2293 int sourceChannel = channelOf(source);
2294 builder.setInsertionPoint(flow);
2295 for (StringRef destName : flow.getDestinationNames()) {
2296 auto dest = lookupEndpoint(destName);
2297 // Ends taking turns share one circuit for all their routes.
2298 if (!circuits
2299 .insert({source.getTile(), sourceChannel, dest.getTile(),
2300 channelOf(dest)})
2301 .second)
2302 continue;
2303 FlowOp::create(builder, flow.getLoc(), source.getTile(),
2304 source.getRouteBundle(), sourceChannel, dest.getTile(),
2305 dest.getRouteBundle(), channelOf(dest));
2306 }
2307 }
2308 for (auto &[endpoint, byDest] : dispatchHeaders) {
2309 SmallVector<Attribute> headers;
2310 for (StringRef dest :
2311 endpoint.getDispatchAttr().getAsValueRange<FlatSymbolRefAttr>())
2312 headers.push_back(byDest.lookup(dest));
2313 endpoint.setDispatchPacketsAttr(builder.getArrayAttr(headers));
2314 }
2315 return success();
2316 }
2317
2318 /// An `aiex.dma_channel_reset_for` outlives the fifo it names, so record the
2319 /// channels and locks it has to re-arm and point it at that record. Shim
2320 /// endpoints are left out: the host re-pushes those itself.
2321 LogicalResult bindRearmTargets() {
2322 if (poolLocks->rearms().empty()) {
2323 return success();
2324 }
2325
2326 builder.setInsertionPoint(device.getBody()->getTerminator());
2327 for (auto &[fifoName, users] : poolLocks->rearms()) {
2328 SmallVector<Value> channelTiles, lockValues;
2329 SmallVector<int32_t> channelDirs, channelIndices, lockInits;
2330 // The record stands for these endpoints and pools: located at each.
2331 SmallVector<Location> locs;
2332
2333 for (auto endpoint : device.getOps<RouteEndpoint>()) {
2334 std::optional<int> channel = endpoint.getRouteChannel();
2335 if (endpoint.getFifoName() != fifoName ||
2336 tileOf(endpoint).isShimTile() || !channel) {
2337 continue;
2338 }
2339 if (auto dma =
2340 dyn_cast<ObjectFifoDmaEndpointOp>(endpoint.getOperation());
2341 dma && dma.getReleaseStrategy() == ObjectFifoRelease::PushQueue) {
2342 for (AIEX::DmaChannelResetForOp user : users)
2343 user.emitOpError(
2344 "does not support core-pushed DMA channels; reset requires "
2345 "coordination with the issuing core and all shared senders");
2346 return failure();
2347 }
2348 channelTiles.push_back(endpoint.getTile());
2349 channelDirs.push_back(
2350 static_cast<int32_t>(endpoint.getRouteDirection()));
2351 channelIndices.push_back(*channel);
2352 locs.push_back(endpoint->getLoc());
2353 }
2354 for (auto pool : device.getOps<ObjectFifoPoolOp>()) {
2355 if (pool.getFifoName() != fifoName || pool.getTileLike().isShimTile()) {
2356 continue;
2357 }
2358 locs.push_back(pool.getLoc());
2359 for (LockOp lock : pool.getLockOps()) {
2360 lockValues.push_back(lock.getResult());
2361 lockInits.push_back(lock.getInit().value_or(0));
2362 }
2363 }
2364
2365 if (channelTiles.empty() && lockValues.empty()) {
2366 for (AIEX::DmaChannelResetForOp user : users) {
2367 user.emitOpError() << "objectFIFO '" << fifoName
2368 << "' has no resident core/mem DMA channels or "
2369 "locks to re-arm";
2370 }
2371 return failure();
2372 }
2373
2374 std::string name = (fifoName + "__rearm").str();
2375 for (unsigned suffix = 0; lookupNamedOpIn(device, StringRef(name));
2376 suffix++) {
2377 name = (fifoName + "__rearm" + std::to_string(suffix + 1)).str();
2378 }
2379
2380 // head_bd_ids and repeat_counts are filled in by --aie-assign-bd-ids.
2381 ObjectFifoRearmBindingOp::create(
2382 builder, FusedLoc::get(builder.getContext(), locs),
2383 builder.getStringAttr(name), ValueRange(channelTiles),
2384 ValueRange(lockValues), builder.getDenseI32ArrayAttr(channelDirs),
2385 builder.getDenseI32ArrayAttr(channelIndices),
2386 builder.getDenseI32ArrayAttr(lockInits),
2387 /*head_bd_ids=*/DenseI32ArrayAttr(),
2388 /*repeat_counts=*/DenseI32ArrayAttr());
2389 auto target = FlatSymbolRefAttr::get(builder.getContext(), name);
2390 for (AIEX::DmaChannelResetForOp user : users) {
2391 user.setObjfifoAttr(target);
2392 }
2393 }
2394 return success();
2395 }
2396
2397 /// Give each dma_start naming an endpoint the channel it was assigned.
2398 LogicalResult resolveStart(DMAStartOp start, RouteEndpointOp endpoint,
2399 ArrayRef<RouteOp> flows, ArrayRef<int> ids,
2400 int channel) {
2401 DMAChannelDir dir = endpoint.getRouteDirection();
2402 if (start.getChannelDir() != dir)
2403 return start.emitOpError("starts ")
2404 << stringifyDMAChannelDir(start.getChannelDir()) << " on "
2405 << start.getEndpoint() << ", but its route makes it "
2406 << stringifyDMAChannelDir(dir);
2407 // Only a runtime task's BDs are given the packet header, so a DMA
2408 // program states it in each BD; --aie-assign-packet-ids made it pin one.
2409 bool packet = !flows.empty() && RouteOp(flows.front()).getPacket();
2410 if (packet) {
2411 SmallVector<DMABDOp> bds;
2412 for (Block *block : DMAChannelAnalysis::chainOf(start))
2413 llvm::append_range(bds, block->getOps<DMABDOp>());
2414 if (failed(checkHeaders(endpoint, ids, bds)))
2415 return failure();
2416 }
2417 start.setChannelAttr(builder.getI32IntegerAttr(channel));
2418 return success();
2419 }
2420
2421 /// A packet source that no one header is stamped on needs each of `bds` to
2422 /// state the header of one of its flows, whose pinned ids are `ids`.
2423 LogicalResult checkHeaders(RouteEndpointOp endpoint, ArrayRef<int> ids,
2424 ArrayRef<DMABDOp> bds) {
2425 for (DMABDOp bd : bds) {
2426 std::optional<int> id;
2427 if (auto packet = bd.getPacket())
2428 id = packet->getPktId();
2429 else if (auto ops = bd->getBlock()->getOps<DMABDPACKETOp>(); !ops.empty())
2430 id = (*ops.begin()).getPacketId();
2431 if (id && llvm::is_contained(ids, *id))
2432 continue;
2433 return bd.emitOpError("sends on @")
2434 << endpoint.getSymName()
2435 << " without the packet header of one of its flows, ids " << ids;
2436 }
2437 return success();
2438 }
2439
2440 /// Each runtime task or transfer that sends on a shared source must state
2441 /// one of its flows' headers; a DMA program's start is resolveStart's, and
2442 /// other users send nothing.
2443 LogicalResult checkSharedSourceUsers(RouteEndpointOp endpoint,
2444 ArrayRef<int> ids) {
2445 auto uses = SymbolTable::getSymbolUses(endpoint, device);
2446 if (!uses)
2447 return success();
2448 for (const SymbolTable::SymbolUse &use : *uses) {
2449 Operation *user = use.getUser();
2450 if (auto task = dyn_cast<AIEX::DMAConfigureTaskForOp>(user)) {
2451 SmallVector<DMABDOp> bds;
2452 task.getBody().walk([&](DMABDOp bd) { bds.push_back(bd); });
2453 if (failed(checkHeaders(endpoint, ids, bds)))
2454 return failure();
2455 continue;
2456 }
2457 if (auto start = dyn_cast<AIEX::DMAStartBdChainForOp>(user)) {
2458 auto chain = device.lookupSymbol<BDChainOp>(start.getSymbol());
2459 if (!chain)
2460 return start.emitOpError("symbol does not reference valid BD chain");
2461 SmallVector<DMABDOp> bds;
2462 chain.getBody().walk([&](DMABDOp bd) { bds.push_back(bd); });
2463 if (failed(checkHeaders(endpoint, ids, bds)))
2464 return failure();
2465 continue;
2466 }
2467 auto memcpy = dyn_cast<AIEX::NpuDmaMemcpyNdOp>(user);
2468 if (!memcpy)
2469 continue;
2470 std::optional<PacketInfoAttr> packet = memcpy.getPacket();
2471 if (packet && llvm::is_contained(ids, packet->getPktId()))
2472 continue;
2473 return memcpy.emitOpError("sends on @")
2474 << endpoint.getSymName()
2475 << ", a source several packet routes share, which has no one "
2476 "header to stamp; it needs a packet header of its own, one of "
2477 "ids "
2478 << ids;
2479 }
2480 return success();
2481 }
2482
2483 /// A runtime task naming an endpoint is configured on the endpoint's tile
2484 /// and channel directly.
2485 void resolveTask(AIEX::DMAConfigureTaskForOp task, RouteEndpointOp endpoint,
2486 int channel) {
2487 builder.setInsertionPoint(task);
2488 auto configured = AIEX::DMAConfigureTaskOp::create(
2489 builder, task.getLoc(), builder.getIndexType(), endpoint.getTile(),
2490 DMAChannelDirAttr::get(builder.getContext(),
2491 endpoint.getRouteDirection()),
2492 builder.getI32IntegerAttr(channel),
2493 builder.getBoolAttr(task.getIssueToken()),
2494 builder.getI32IntegerAttr(task.getRepeatCount()),
2495 task.getRepeatCountVal(), endpoint.getPacketAttr(),
2496 /*out_of_order=*/UnitAttr(), /*alloc=*/FlatSymbolRefAttr());
2497 task.getResult().replaceAllUsesWith(configured.getResult());
2498 configured.getBody().takeBody(task.getBody());
2499 task.erase();
2500 }
2501
2502 /// Rewrite the programs and tasks naming an endpoint to its channel while
2503 /// the route giving its direction is still there. A shim end with a fifo
2504 /// name keeps its tasks, which emitShimAllocations points at the allocation.
2505 LogicalResult resolveEndpointUses() {
2506 for (auto endpoint : device.getOps<RouteEndpointOp>()) {
2507 auto starts = endpointStarts.lookup(endpoint);
2508 auto tasks = endpointTasks.lookup(endpoint);
2509 auto sourced = sourcedFlows.find(endpoint.getSymNameAttr());
2510 ArrayRef<RouteOp> flows;
2511 if (sourced != sourcedFlows.end())
2512 flows = sourced->second;
2513 SmallVector<int> ids;
2514 for (RouteOp flow : flows)
2515 if (std::optional<PacketInfoAttr> packet = flow.getPacket();
2516 packet && packet->isAssigned())
2517 ids.push_back(packet->assignedId());
2518 bool shared = flows.size() > 1;
2519 if (shared && failed(checkSharedSourceUsers(endpoint, ids)))
2520 return failure();
2521 if (starts.empty() && tasks.empty())
2522 continue;
2523 std::optional<int> channel = endpoint.getRouteChannel();
2524 assert(channel && "assignChannels gives every routed endpoint one");
2525 for (DMAStartOp start : starts)
2526 if (failed(resolveStart(start, endpoint, flows, ids, *channel)))
2527 return failure();
2528 if (endpoint.getTileLike().isShimTile() && endpoint.getFifoName())
2529 continue;
2530 for (auto task : tasks)
2531 resolveTask(task, endpoint, *channel);
2532 }
2533 return success();
2534 }
2535
2536 /// A shim endpoint has no memory of its own, so the runtime needs its channel
2537 /// spelled out under the name the sequence refers to.
2538 void emitShimAllocations() {
2539 builder.setInsertionPoint(device.getBody()->getTerminator());
2540 // A fifo's first shim end takes the name the runtime sequence was pointed
2541 // at. Any further shim end of the same fifo, as when a core broadcasts to
2542 // two shim tiles, is a different tile and channel and needs a record of
2543 // its own; sharing the first would send the runtime to the wrong tile.
2544 llvm::StringMap<unsigned> shimEndsSeen;
2545 for (auto endpoint : device.getOps<RouteEndpoint>()) {
2546 std::optional<StringRef> fifoName = endpoint.getFifoName();
2547 if (!fifoName)
2548 if (auto named = dyn_cast<RouteEndpointOp>(endpoint.getOperation()))
2549 fifoName = named.getSymName();
2550 std::optional<int> channel = endpoint.getRouteChannel();
2551 if (!tileOf(endpoint).isShimTile() || !fifoName || !channel) {
2552 continue;
2553 }
2554 std::string name = (*fifoName + "__shim_alloc").str();
2555 unsigned ordinal = shimEndsSeen[*fifoName]++;
2556 bool create = true;
2557 if (ordinal == 0) {
2558 // A record under this name may already be there, declared by hand.
2559 create = !SymbolTable::lookupNearestSymbolFrom<ShimDMAAllocationOp>(
2560 device, builder.getStringAttr(name));
2561 } else {
2562 for (unsigned suffix = ordinal - 1; device.lookupSymbol(name);
2563 suffix++) {
2564 name =
2565 (*fifoName + "__shim_alloc" + std::to_string(suffix + 1)).str();
2566 }
2567 }
2568 if (create) {
2569 // The proof names other shim endpoints, which replaceAllSymbolUses
2570 // renames to their allocations as each is reached.
2571 auto routeEndpoint = dyn_cast<RouteEndpointOp>(endpoint.getOperation());
2572 ShimDMAAllocationOp::create(
2573 builder, endpoint.getLoc(), builder.getStringAttr(name),
2574 endpoint.getTile(),
2575 DMAChannelDirAttr::get(builder.getContext(),
2576 endpoint.getRouteDirection()),
2577 builder.getI64IntegerAttr(*channel),
2578 builder.getBoolAttr(endpoint.getRouteBundle() == WireBundle::PLIO),
2579 endpoint->getAttrOfType<PacketInfoAttr>("packet"),
2580 routeEndpoint ? routeEndpoint.getConsumedByAttr() : ArrayAttr());
2581 }
2582 // The runtime sequence reaches the fifo through this record.
2583 (void)SymbolTable::replaceAllSymbolUses(
2584 endpoint, builder.getStringAttr(name), device);
2585 }
2586 }
2587
2588 /// Size-first packing order: mem tile pools largest buffer first, equal
2589 /// ones by home coordinates, unplaced last, as the SA placer orders them, in
2590 /// the slots mem tile pools hold, the others left in place. A pool walked
2591 /// whole becomes one large buffer, so this is chosen again after every walk.
2592 void sizeOrder(MutableArrayRef<ObjectFifoPoolOp> pools) {
2593 SmallVector<size_t> memTileSlots;
2594 SmallVector<ObjectFifoPoolOp> memTilePools;
2595 for (auto [index, pool] : llvm::enumerate(pools)) {
2596 if (pool.getTileLike().isMemTile()) {
2597 memTileSlots.push_back(index);
2598 memTilePools.push_back(pool);
2599 }
2600 }
2601 llvm::stable_sort(memTilePools, [](ObjectFifoPoolOp a, ObjectFifoPoolOp b) {
2602 auto home = [](ObjectFifoPoolOp pool) {
2603 TileLike tile = pool.getTileLike();
2604 auto col = tile.tryGetCol(), row = tile.tryGetRow();
2605 return std::make_tuple(!col || !row, col.value_or(0), row.value_or(0));
2606 };
2607 return home(a) < home(b);
2608 });
2609 sortLargestBufferFirst(memTilePools, bufferBytes);
2610 for (auto [slot, pool] : llvm::zip(memTileSlots, memTilePools))
2611 pools[slot] = pool;
2612 }
2613
2614 /// Alternative packing order (demandFirstOrder). The same buffer, lock and
2615 /// channel planner validates both orders.
2616 SmallVector<ObjectFifoPoolOp>
2617 demandOrderedPools(ArrayRef<ObjectFifoPoolOp> pools) {
2618 DenseMap<Operation *, std::pair<int, int>> poolChannelDemand;
2619 for (auto endpoint : device.getOps<ObjectFifoDmaEndpointOp>()) {
2620 ObjectFifoPoolOp pool = endpoint.getPoolOp();
2621 if (!sameTile(endpoint.getTile(), pool.getTile()))
2622 continue;
2623 auto &demand = poolChannelDemand[pool];
2624 if (endpoint.getRouteDirection() == DMAChannelDir::S2MM)
2625 ++demand.first;
2626 else
2627 ++demand.second;
2628 }
2629 SmallVector<size_t> memTileSlots;
2630 SmallVector<Value> homes;
2631 SmallVector<SpillPool> records;
2632 for (size_t index = 0, e = pools.size(); index < e; ++index) {
2633 ObjectFifoPoolOp pool = pools[index];
2634 if (!pool.getTileLike().isMemTile())
2635 continue;
2636 memTileSlots.push_back(index);
2637 auto *home = llvm::find_if(
2638 homes, [&](Value known) { return sameTile(pool.getTile(), known); });
2639 if (home == homes.end()) {
2640 homes.push_back(pool.getTile());
2641 home = std::prev(homes.end());
2642 }
2643 auto [input, output] = poolChannelDemand.lookup(pool.getOperation());
2644 records.push_back({bufferBytes(pool), bufferCount(pool),
2645 static_cast<unsigned>(home - homes.begin()),
2646 std::max(input, output)});
2647 }
2648 SmallVector<ObjectFifoPoolOp> ordered(pools);
2649 for (auto [slot, index] :
2650 llvm::zip(memTileSlots, demandFirstOrder(records)))
2651 ordered[slot] = pools[memTileSlots[index]];
2652 return ordered;
2653 }
2654
2655 void runOnOperation() override {
2656 device = getOperation();
2657 builder = OpBuilder(device.getContext());
2658 semaphoreLocks =
2659 device.getTargetModel().hasProperty(AIETargetModel::UsesSemaphoreLocks);
2660 // One pass instance serves every device in the module, and none of this
2661 // state means anything outside the device it was gathered from.
2662 channelSharers.clear();
2663 allocationSharers.clear();
2664 lastPlaced.clear();
2665 loweredFlows.clear();
2666 sourcedFlows.clear();
2667 localPools.clear();
2668 poolUsers.clear();
2669 lockUsers.clear();
2670 lockPlacements.clear();
2671 spillTiles.clear();
2672 dispatchHeaders.clear();
2673 channelSharers.clear();
2674 bdPlanned.clear();
2675 turnWalked.clear();
2676 hostMovesFirstCache.clear();
2677 bufferPlacements.clear();
2678 channelAssignments.clear();
2679 endpointStarts.clear();
2680 endpointTasks.clear();
2681 takenBDs = {};
2682 taskBDs.clear();
2683 channelDemand.clear();
2684 structuralRank.clear();
2685 channelFailure = nullptr;
2686 bufferFailure = nullptr;
2687 lockFailure = nullptr;
2688 lockAccessFailure = nullptr;
2689 walkSearchStopped = false;
2690
2691 if (failed(collectFixedMemory()) || failed(checkStreamPorts()))
2692 return signalPassFailure();
2693 collectChannelPrograms();
2694 rankStructurally();
2695
2696 // Preserve successful largest-first allocations, including their locality
2697 // repairs. Only try demand ordering when that search fails.
2698 SmallVector<ObjectFifoPoolOp> pools(device.getOps<ObjectFifoPoolOp>());
2699 llvm::stable_sort(pools, [&](ObjectFifoPoolOp a, ObjectFifoPoolOp b) {
2700 return structuralRank.lookup(a) < structuralRank.lookup(b);
2701 });
2702 sizeOrder(pools);
2703
2704 poolLocks = std::make_shared<PoolLocks>(device);
2705 for (auto endpoint : device.getOps<ObjectFifoCoreEndpointOp>()) {
2706 poolUsers[endpoint.getPoolOp()].push_back(endpoint.getTile());
2707 collectLockUsers(endpoint);
2708 }
2709 for (auto endpoint : device.getOps<ObjectFifoDmaEndpointOp>()) {
2710 poolUsers[endpoint.getPoolOp()].push_back(endpoint.getTile());
2711 collectLockUsers(endpoint);
2712 }
2713 for (auto &[group, users] : lockUsers)
2714 llvm::stable_sort(users, [&](Operation *a, Operation *b) {
2715 return structuralRank.lookup(a) < structuralRank.lookup(b);
2716 });
2717
2718 std::set<std::vector<unsigned>> tried;
2719 LogicalResult allocated = planAllocation(pools, tried);
2720 if (failed(allocated)) {
2721 auto demandOrdered = demandOrderedPools(pools);
2722 if (!llvm::equal(pools, demandOrdered)) {
2723 // Memoized locality sets are specific to a packing order.
2724 localPools.clear();
2725 tried.clear();
2726 allocated = planAllocation(demandOrdered, tried);
2727 }
2728 }
2729 // Out of channels, ends that never need theirs at once take turns on one,
2730 // a tile and direction at a time: on a shim tile, ends never in flight
2731 // together; elsewhere, ends whose objects one core needs in a fixed order.
2732 // Short of BD ids on a mem tile channel, its deepest pool walked whole
2733 // takes one a side. Buffers that fit nowhere as split are placed again
2734 // with the pools walked whole that the tiles' BD ids need anyway.
2735 auto repair = [&] {
2736 if (channelFailure) {
2737 TileLike tile = tileOf(channelFailure);
2738 DMAChannelDir dir = channelFailure.getRouteDirection();
2739 if (bdShortfall) {
2740 if (bdPlanned.insert(tile.getOperation()) ||
2741 walkForBDShortfall(tile, pools))
2742 return true;
2743 } else if (tile.isShimTile() ? planShimSharing(tile, dir)
2744 : planTurnSharing(tile, dir)) {
2745 return true;
2746 }
2747 }
2748 localPools.clear();
2749 return failed(planBuffers(pools)) && walkHomeBDPools(pools);
2750 };
2751 while (failed(allocated) && repair()) {
2752 localPools.clear();
2753 tried.clear();
2754 sizeOrder(pools);
2755 allocated = planAllocation(pools, tried);
2756 }
2757 if (succeeded(allocated) &&
2758 (!channelSharers.empty() || !allocationSharers.empty()) &&
2759 failed(headShimSharingRoutes()))
2760 return signalPassFailure();
2761 if (failed(allocated)) {
2762 localPools.clear();
2763 if (failed(planBuffers(pools))) {
2764 InFlightDiagnostic error =
2765 walkSearchStopped
2766 ? bufferFailure.emitOpError(
2767 "could not place buffers: the search for which pools "
2768 "to make contiguous (one buffer, one BD per side) "
2769 "stopped after ")
2771 << " placements tried in one group of neighbouring "
2772 "mem tiles"
2773 : bufferFailure.emitOpError(kNoBufferRoom);
2774 if (std::optional<StringRef> fifo = bufferFailure.getFifoName())
2775 error << " for objectFIFO "
2776 << SymbolRefAttr::get(
2777 device.getSymNameAttr(),
2778 {FlatSymbolRefAttr::get(device.getContext(), *fifo)});
2779 SmallVector<Attribute> walked;
2780 for (Operation *op : turnWalked) {
2781 auto pool = cast<ObjectFifoPoolOp>(op);
2782 std::optional<StringRef> name = pool.getFifoName();
2783 if (pool.getContiguous() && name &&
2784 cast<TileLike>(pool.getTile().getDefiningOp()).isMemTile())
2785 walked.push_back(SymbolRefAttr::get(
2786 device.getSymNameAttr(),
2787 {FlatSymbolRefAttr::get(device.getContext(), *name)}));
2788 }
2789 if (!walked.empty()) {
2790 Diagnostic &note = error.attachNote();
2791 note << kTurnWalkedNote;
2792 llvm::interleaveComma(walked, note);
2793 }
2794 } else if (failed(planLocks(pools))) {
2795 if (lockSearchStopped) {
2796 InFlightDiagnostic error =
2797 lockSearchStoppedOn.emitOpError(
2798 "could not decide whether the locks fit: the lock packing "
2799 "search stopped after ")
2800 << LockPlan::kPackBudget << " steps";
2801 if (std::optional<StringRef> fifo = lockSearchStoppedOn.getFifoName())
2802 error << " for objectFIFO "
2803 << SymbolRefAttr::get(
2804 device.getSymNameAttr(),
2805 {FlatSymbolRefAttr::get(device.getContext(), *fifo)});
2806 } else if (lockAccessFailure)
2807 lockAccessFailure->emitOpError("cannot access pool locks");
2808 else
2809 lockFailure.getDefiningOp()->emitOpError(
2810 "could not place locks within tile lock capacity");
2811 } else {
2812 DMAChannelAnalysis channels(device);
2813 (void)assignChannels(channels);
2814 device.emitRemark(
2815 "could not find a spill-aware allocation with size-first and "
2816 "demand-first packing and bounded local-pool retries; tile "
2817 "placement and buffer packing remain greedy");
2818 }
2819 return signalPassFailure();
2820 }
2821 for (ObjectFifoPoolOp pool : pools) {
2822 allocateBuffers(pool);
2823 allocateLocks(pool);
2824 }
2825 for (TileOp tile : spillTiles)
2826 if (tile->use_empty())
2827 tile->erase();
2828 for (auto endpoint : device.getOps<RouteEndpoint>())
2829 if (auto it = channelAssignments.find(endpoint.getOperation());
2830 it != channelAssignments.end())
2831 endpoint.setRouteChannel(it->second);
2832 warnOvercommittedBDs();
2833
2834 // Routes still identify each sender's receiving buffers here, but hardware
2835 // BD IDs are assigned later. Preserve that pairing with temporary tags
2836 // before lowering erases the routes.
2837 llvm::EquivalenceClasses<Operation *> matchingPools;
2838 DenseMap<Operation *, int64_t> descriptorCounts;
2839 for (auto flow : device.getOps<RouteOp>()) {
2840 if (flow.getSources().size() != 1)
2841 continue;
2842 ObjectFifoPoolOp first;
2843 for (auto destName : flow.getDestinationNames()) {
2844 RouteEndpoint receiver = lookupEndpoint(destName);
2845 auto dst =
2846 receiver
2847 ? dyn_cast<ObjectFifoDmaEndpointOp>(receiver.getOperation())
2848 : nullptr;
2849 if (!dst || !dst.getOutOfOrder())
2850 continue;
2851 ObjectFifoPoolOp pool = dst.getPoolOp();
2852 if (!first)
2853 first = pool;
2854 matchingPools.unionSets(first.getOperation(), pool.getOperation());
2855 descriptorCounts[pool] = dst.getNumDescriptors();
2856 }
2857 }
2858 int32_t nextTag = 0;
2859 DenseMap<Operation *, DenseI32ArrayAttr> tagsOfGroup;
2860 for (ObjectFifoPoolOp pool : pools) {
2861 auto member = matchingPools.findLeader(pool.getOperation());
2862 if (member == matchingPools.member_end())
2863 continue;
2864 Operation *leader = *member;
2865 auto &tags = tagsOfGroup[leader];
2866 if (!tags) {
2867 SmallVector<int32_t> values;
2868 for (int64_t slot = 0; slot < descriptorCounts.lookup(pool); ++slot)
2869 values.push_back(nextTag++);
2870 tags = builder.getDenseI32ArrayAttr(values);
2871 }
2872 pool.setOutOfOrderTagsAttr(tags);
2873 }
2874
2875 // A sender references the next hop's receiving slots, independently of
2876 // any receiving descriptors that fill its own pool.
2877 for (auto flow : device.getOps<RouteOp>()) {
2878 if (flow.getSources().size() != 1)
2879 continue;
2880 RouteEndpoint sender = lookupEndpoint(*flow.getSourceNames().begin());
2881 auto src = sender
2882 ? dyn_cast<ObjectFifoDmaEndpointOp>(sender.getOperation())
2883 : nullptr;
2884 if (!src || !src.getOutOfOrder())
2885 continue;
2886 for (auto destName : flow.getDestinationNames()) {
2887 RouteEndpoint receiver = lookupEndpoint(destName);
2888 auto dst =
2889 receiver
2890 ? dyn_cast<ObjectFifoDmaEndpointOp>(receiver.getOperation())
2891 : nullptr;
2892 if (dst && dst.getOutOfOrder()) {
2893 src.setOutOfOrderTagsAttr(dst.getPoolOp().getOutOfOrderTagsAttr());
2894 break;
2895 }
2896 }
2897 }
2898
2899 if (failed(bindRearmTargets())) {
2900 return signalPassFailure();
2901 }
2902 if (failed(lowerFlows()) || failed(resolveEndpointUses())) {
2903 return signalPassFailure();
2904 }
2905 emitShimAllocations();
2906 for (Operation *flow : loweredFlows) {
2907 flow->erase();
2908 }
2909 }
2910};
2911
2912} // namespace
2913
2914std::unique_ptr<OperationPass<DeviceOp>>
2916 return std::make_unique<AIEObjectFifoAllocatePass>();
2917}
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,...
mlir::LogicalResult read(llvm::ArrayRef< ObjectFifoCoreEndpointOp > ends, std::string &reason)
Reads the order off the program of the core working through ends, all draining (the channel fills the...
bool keepsUp(llvm::ArrayRef< int64_t > depths)
Whether a channel moving objects in turns() order forever, through pools of depths,...
llvm::ArrayRef< unsigned > turns() const
Indices into ends, one per object the channel moves in a period of the core's steady state.
int getDMAChannelIndex(TileLike tile, DMAChannelDir dir, bool requiresAdjacentTileAccessChannels, mlir::Operation *owner=nullptr)
Next free channel of tile in dir, or -1 when the tile has none left.
static std::optional< unsigned > nextPoolToWalk(llvm::ArrayRef< BDPlanEnd > ends, llvm::ArrayRef< unsigned > poolOf, llvm::ArrayRef< BDWalkPool > pools, llvm::ArrayRef< bool > whole)
The walkable pool not yet whole to walk next: the deepest, then the one with the smallest objects,...
mlir::Operation * getDMAChannelOwner(TileLike tile, DMAChannelDir dir, int channel)
Operation reserving or routing this channel; null if none.
bool isChannelFree(TileLike tile, DMAChannelDir dir, int channel)
Whether first-free assignment could hand out channel: nothing reserves it and no explicit flow routes...
static std::optional< llvm::SmallVector< int > > planBDChannels(const AIETargetModel &target, int col, int row, llvm::ArrayRef< BDPlanEnd > ends, llvm::function_ref< bool(DMAChannelDir, int)> free, llvm::function_ref< int64_t(int)> spent)
A channel of the tile at (col, row) for each of ends: its pinned one, else one free leaves that no ot...
static constexpr unsigned kMaxWalkPlacements
static int64_t countBDs(DMAStartOp start)
static llvm::SmallVector< BDGroup > bdGroups(const AIETargetModel &target, int col, int row, int numChannels)
static WalkChoice searchWalkProduct(llvm::ArrayRef< llvm::SmallVector< int64_t > > bytes, llvm::function_ref< bool(llvm::ArrayRef< unsigned >)> places, unsigned maxTries)
Tries the choices of one set per tile, bytes[tile] giving each of its sets' bytes walked whole,...
static llvm::SmallVector< mlir::Block * > chainOf(DMAStartOp start)
Blocks of the BD chain start begins, following next_bd.
static BDWalkSets walkSetsThatFit(const AIETargetModel &target, int col, int row, llvm::ArrayRef< BDPlanEnd > ends, llvm::ArrayRef< unsigned > poolOf, llvm::ArrayRef< BDWalkPool > pools, llvm::function_ref< bool(DMAChannelDir, int)> free, llvm::function_ref< int64_t(int)> spent, unsigned maxSets=std::numeric_limits< unsigned >::max())
Every set of walkable pools whose walk lets planBDChannels fit ends (poolOf gives each end's pool),...
static int getDMAChannelLimit(TileLike tile, DMAChannelDir dir, bool requiresAdjacentTileAccessChannels)
Exclusive upper bound on channel indices eligible for this transfer.
mlir::LogicalResult checkAIEStreamIndex(TileLike tile, DMAChannel chan, mlir::Operation *user, bool packet=false)
Claim a raw stream port for user, reporting on it when the port is taken; packet users may share it w...
int reservePinnedChannel(TileLike tile, DMAChannelDir dir, int channel, mlir::Operation *owner=nullptr, bool shareable=false)
Claim channel for (tile, dir) so first-free assignment cannot take it.
static llvm::SmallVector< mlir::Operation * > lockOwners(const AIETargetModel &target, ObjectFifoPoolOp pool)
The ops whose locks allocation and the SA each make for pool: with semaphore locks,...
static llvm::SmallVector< int > groupCounts(const AIETargetModel &target, int64_t depth, int owners)
The lock groups owners lock owners of a pool of depth objects take, by count.
Definition AIELockPlan.h:79
static constexpr int64_t kPackBudget
Steps the exact packing of groups of different counts may take on each connected component.
unsigned addTile(Tile tile)
Assignment assign(llvm::ArrayRef< Group > groups, Memo *memo=nullptr, bool callerOrder=true)
Places groups first fit: with callerOrder, in order on each one's candidates, then in canonical order...
static bool dmaLocalOnly(AIETileType type)
Whether a DMA on a tile of type uses only its own tile's locks: every DMA does but a mem tile's.
Definition AIELockPlan.h:90
bool reserve(unsigned tile, int count)
Takes count locks on tile, or returns false when it has too few left.
static bool reaches(const AIETargetModel &target, llvm::ArrayRef< TileID > user, llvm::ArrayRef< TileID > memory, bool localOnly)
Whether a tile at one of user reaches memory at one of memory; with localOnly, only at its own positi...
static Group group(int count, unsigned home, bool local, llvm::ArrayRef< unsigned > buffers, llvm::ArrayRef< User > users, llvm::ArrayRef< unsigned > ranked)
A group of count locks a pool's objects are counted by: on home, else, unless the pool must stay loca...
void reserve(unsigned tile, int64_t bytes, int count=1)
bool place(llvm::ArrayRef< Buffer > buffers)
Places buffers in order on top of what the tiles hold.
llvm::SmallVector< bool > weighed
Homes a spill from was weighed: aie-objectfifo-allocate gives their neighbours tile ops,...
bool fits(unsigned tile, int64_t bytes, int count=1) const
llvm::SmallVector< unsigned > chosen
int64_t used(unsigned tile, int64_t bytes=0, int count=0) const
The bytes tile spans with what it holds and count more of bytes.
std::optional< int > takeLowestFrom(int from=0)
Takes and returns the lowest free id at or above from, or nothing when the field is exhausted.
static std::optional< End > endOf(DeviceOp device, mlir::StringAttr symbol)
The end a runtime sequence of device transfers through when it names symbol: a shim DMA route end,...
static mlir::StringAttr keyOf(RouteEndpointOp endpoint)
How ends and gates name a shim route end: by its objectFIFO, else by its own symbol.
static Gates provenGates(DeviceOp device, llvm::function_ref< mlir::StringAttr(RouteEndpointOp)> keyOf)
Each receiving end's gates, keyed by keyOf: the shim inputs whose consumption its progress proves,...
bool namesFifo(Operation *op, StringRef fifo, SymbolTableCollection &symbols)
Definition AIEUtils.cpp:386
void sortLargestBufferFirst(Range &&buffers, BytesFn bytes)
Buffers are laid out, and given a tile, largest buffer first: by the address layout below,...
llvm::SmallVector< ObjectFifoDmaEndpointOp > turnEndpoints(ObjectFifoDmaEndpointOp end)
llvm::SmallVector< unsigned > demandFirstOrder(llvm::ArrayRef< SpillPool > pools)
aie-objectfifo-allocate's demand-first packing order of pools, given in its size-first order,...
std::unique_ptr< mlir::OperationPass< DeviceOp > > createAIEObjectFifoAllocatePass()
mlir::Operation * lookupNamedOpIn(mlir::Operation *symbolTableOp, mlir::StringAttr name)
llvm::SmallVector< TileID, 2 > memTileSpillNeighbours(const AIETargetModel &target, TileID home)
The tiles a mem tile buffer homed at home may spill to: those in its row home shares memory with,...
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
int64_t turnPasses(llvm::ArrayRef< std::pair< int64_t, int64_t > > ends)
mlir::Operation * lookupNamedOp(mlir::Operation *from, mlir::StringAttr name)
constexpr llvm::StringLiteral kTurnWalkedNote
The note on it naming, as its symbol arguments, the mem tile pools channel turns walked whole: one bu...
Definition AIEPasses.h:46
constexpr llvm::StringLiteral kNoBufferRoom
How --aie-objectfifo-allocate says a pool's buffers fit no memory its users reach; the diagnostic's s...
Definition AIEPasses.h:42
llvm::SmallVector< unsigned > memTileSpillComponents(llvm::ArrayRef< TileID > homes, llvm::function_ref< llvm::SmallVector< TileID, 2 >(TileID)> neighboursOf)
For each of homes, the index of its component: homes whose buffers may spill to a tile in common,...
llvm::SmallVector< int64_t > bytes
The bytes each set walks whole.
llvm::SmallVector< llvm::SmallVector< unsigned > > sets
std::optional< size_t > failed
The first group no assignment finds room for: first fit's miss, or, after packing or matching run,...
llvm::SmallVector< std::optional< unsigned > > tiles
bool stopped
The exact packing ran out of kPackBudget steps before it decided.
bool reachable
Some candidate every user reaches.
Definition AIELockPlan.h:52
std::optional< unsigned > full
The last such candidate, when all were full.
Definition AIELockPlan.h:54
llvm::SmallVector< llvm::SmallVector< unsigned > > groups
The other ends, in groups taking one channel each.
llvm::SmallVector< std::optional< unsigned > > sharedChannel
Per end, the index of the shared channel it takes, if any.
void link(mlir::Operation *from, mlir::Operation *to, llvm::StringRef label)
Link from to to under label, and to back to from.
llvm::SmallVector< mlir::Operation * > nodes
std::string & add(mlir::Operation *op)
Add op as a node whose features are its name and attributes, symbol names and references left out.
llvm::DenseMap< mlir::Operation *, unsigned > rank() const
Rank the nodes by their features and then, a round at a time until no class splits,...
llvm::DenseMap< mlir::Operation *, std::string > features
What each node is, before anything it links to is considered.