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"
34#define DEBUG_TYPE "aie-objectfifo-allocate"
41#define GEN_PASS_DEF_AIEOBJECTFIFOALLOCATE
42#include "aie/Dialect/AIE/Transforms/AIEPasses.h.inc"
47struct AIEObjectFifoAllocatePass
48 :
public xilinx::AIE::impl::AIEObjectFifoAllocateBase<
49 AIEObjectFifoAllocatePass> {
53 OpBuilder builder{
static_cast<MLIRContext *
>(
nullptr)};
55 DenseMap<Value, Operation *> lastPlaced;
57 std::shared_ptr<PoolLocks> poolLocks;
60 SmallVector<Operation *> loweredFlows;
63 DenseMap<StringAttr, SmallVector<RouteOp>> sourcedFlows;
64 llvm::MapVector<ObjectFifoDmaEndpointOp, llvm::StringMap<PacketInfoAttr>>
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;
79 DenseMap<Operation *, SmallVector<DMAStartOp>> endpointStarts;
80 DenseMap<Operation *, SmallVector<AIEX::DMAConfigureTaskForOp>> endpointTasks;
85 DMAChannelAnalysis::TakenBDs takenBDs;
88 DenseMap<std::tuple<int, int, int>, int64_t> taskBDs;
91 DenseMap<std::tuple<int, int, int>, int64_t> channelDemand;
94 DenseMap<Operation *, unsigned> structuralRank;
95 RouteEndpoint channelFailure;
98 bool bdShortfall =
false;
101 llvm::SetVector<Operation *> bdPlanned;
103 llvm::SetVector<Operation *> turnWalked;
106 DenseMap<StringAttr, bool> hostMovesFirstCache;
109 ObjectFifoPoolOp bufferFailure;
112 SmallVector<TileOp> spillTiles;
114 Operation *lockAccessFailure =
nullptr;
116 ObjectFifoPoolOp lockSearchStoppedOn;
118 bool semaphoreLocks =
false;
119 bool walkSearchStopped =
false;
120 bool lockSearchStopped =
false;
122 bool sameTile(Value a, Value b) {
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;
135 DenseMap<TileID, unsigned> memTilePositions;
136 DenseMap<Operation *, unsigned> unplacedMemTiles;
137 SmallVector<std::optional<TileID>> memTileAt;
139 std::optional<unsigned> memTileIndex(Value tile) {
140 auto like = cast<TileLike>(tile.getDefiningOp());
141 if (!like.isMemTile())
143 auto col = like.tryGetCol(), row = like.tryGetRow();
145 return memTilePositions.lookup({*col, *row});
146 return unplacedMemTiles.lookup(like);
150 MemTileSpillSearch memTileSearch() {
151 const auto &target = device.getTargetModel();
152 memTilePositions.clear();
153 unplacedMemTiles.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);
161 for (
auto tile : device.getOps<TileLike>()) {
162 if (!tile.isMemTile())
164 auto col = tile.tryGetCol(), row = tile.tryGetRow();
166 unplacedMemTiles[tile] = add(std::nullopt);
170 if (!memTilePositions.count(at))
171 memTilePositions[at] = add(at);
172 if (isa<TileOp>(tile.getOperation()))
174 if (!memTilePositions.count(neighbour))
175 memTilePositions[neighbour] = add(neighbour);
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);
186 LogicalResult collectFixedMemory() {
187 MemTileSpillSearch search = memTileSearch();
188 for (
auto tile : device.getOps<TileLike>()) {
189 std::optional<unsigned> index = memTileIndex(tile->getResult(0));
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
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)
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});
220 bool canAccess(Value user, Value memory,
bool localOnly =
false) {
223 auto memoryTile = dyn_cast<TileLike>(memory.getDefiningOp());
225 canAccess(user, compatiblePositions(memoryTile), localOnly);
230 bool canAccess(Value user, ArrayRef<TileID> memoryPositions,
231 bool localOnly =
false) {
232 auto userTile = dyn_cast<TileLike>(user.getDefiningOp());
234 compatiblePositions(userTile),
235 memoryPositions, localOnly);
238 Value lockPlacement(ObjectFifoPoolOp pool, Operation *group) {
239 if (Value placed = lockPlacements.lookup(group))
241 Value local = localPools.lookup(pool);
242 return local ? local : pool.getTile();
246 static int bufferCount(ObjectFifoPoolOp pool) {
247 return pool.getContiguous() ? 1 : pool.getDepth();
249 static int64_t bufferBytes(ObjectFifoPoolOp pool) {
250 return pool.getObjectSizeInBytes() * pool.getObjectsPerBuffer();
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); });
269 for (
auto pool : pools) {
270 if (!localPools.contains(pool))
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;
282 search.
reserve(*index, size, count);
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;
297 bufferPlacements[pool].push_back(tile);
301 if (pool.getTileLike().isShimTile())
303 if (localPools.contains(pool)) {
304 bufferPlacements[pool].append(bufferCount(pool),
305 localPools.lookup(pool));
308 Value home = pool.getTile();
309 bool atHome = reachable(pool, home);
310 std::optional<unsigned> index = memTileIndex(home);
313 bufferFailure = pool;
316 bufferPlacements[pool].append(bufferCount(pool), home);
321 SmallVector<unsigned, 2> neighbours;
322 if (
auto homeOp = dyn_cast<TileOp>(home.getDefiningOp()))
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);
332 bool placed = search.
place(buffers);
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])
339 for (
int col : {homeOp.getCol() - 1, homeOp.getCol() + 1})
340 if (col >= 0 && col < target.columns())
341 spillTile(col, homeOp.getRow(), pool.getLoc());
344 bufferFailure = owners[search.
failed];
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())
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;
361 TileOp tile = TileOp::getOrCreate(builder, device, col, row, loc);
363 spillTiles.push_back(tile);
369 void setInsertionPointOn(Value tile) {
370 Operation *after = lastPlaced.lookup(tile);
372 after = tile.getDefiningOp();
375 builder.setInsertionPointAfter(after);
377 builder.setInsertionPointToStart(device.getBody());
381 void allocateBuffers(ObjectFifoPoolOp pool) {
382 if (pool.getBuffers()) {
385 TileLike home = pool.getTileLike();
386 if (home.isShimTile()) {
390 ArrayRef<Attribute> initValues;
391 if (
auto initAttr = pool.getInitValues()) {
392 initValues = initAttr->getValue();
394 int filled = initValues.size();
395 StringRef base = pool.getBaseName();
397 SmallVector<Attribute> names;
398 MemRefType type = pool.getElemType();
400 if (pool.getContiguous()) {
401 int64_t objectElements = type.getNumElements();
402 type = MemRefType::get({pool.getObjectsPerBuffer() * objectElements},
403 type.getElementType());
405 RankedTensorType::get(type.getShape(), type.getElementType());
406 Attribute zero = builder.getZeroAttr(type.getElementType());
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++) {
417 cast<DenseElementsAttr>(initValues[i]).getValues<Attribute>());
419 values.append(objectElements, zero);
421 values.append((zeroObjects ? (*zeroObjects)[1] : 0) * objectElements,
423 zeros = DenseElementsAttr::get(tensor, values);
424 }
else if (pool.getZeroObjects()) {
425 zeros = DenseElementsAttr::get(tensor, zero);
429 for (
int i = 0; i < bufferCount(pool); i++) {
430 ElementsAttr init = !pool.getContiguous() && i < filled
431 ? cast<ElementsAttr>(initValues[i])
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),
440 names.push_back(FlatSymbolRefAttr::get(builder.getContext(), name));
442 pool.setBuffersAttr(builder.getArrayAttr(names));
445 LockOp createLock(ObjectFifoPoolOp pool, Value tile, StringRef name,
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));
455 LogicalResult planLocks(ArrayRef<ObjectFifoPoolOp> pools) {
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());
466 auto like = cast<TileLike>(tile.getDefiningOp());
467 auto col = like.tryGetCol(), row = like.tryGetRow();
469 {compatiblePositions(like),
470 col && row ? std::optional<TileID>({*col, *row}) : std::nullopt});
471 tileValues.push_back(tile);
475 for (
auto lock : device.getOps<LockOp>())
476 if (!plan.
reserve(indexOf(lock.getTile()), 1)) {
477 lockFailure = lock.getTile();
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;
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);
506 isa<ObjectFifoDmaEndpointOp>(user) &&
508 cast<TileLike>(tile.getDefiningOp()).getTileType())});
512 localPools.contains(pool), buffers, users, ranked));
513 groupOps.push_back(group);
514 groupPools.push_back(pool);
516 for (
auto pool : pools) {
517 if (!poolLocks->needsLocks(pool))
519 SmallVector<Operation *> owners =
521 for (
auto [owner, count] : llvm::zip_equal(
523 pool.getDepth(), owners.size())))
524 add(pool, owner, count);
526 LockPlan::Assignment assignment = plan.
assign(groups);
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();
537 for (
auto [group, tile] : llvm::zip(groupOps, assignment.
tiles))
539 lockPlacements[group] = tileValues[*tile];
540 auto check = [&](
auto endpoint) {
541 for (Value tile : endpointLockTiles(endpoint)) {
542 if (!canAccessLocks(endpoint, tile)) {
543 lockAccessFailure = endpoint;
549 for (
auto endpoint : device.getOps<ObjectFifoCoreEndpointOp>())
550 if (failed(check(endpoint)))
552 for (
auto endpoint : device.getOps<ObjectFifoDmaEndpointOp>())
553 if (failed(check(endpoint)))
558 void allocateLocks(ObjectFifoPoolOp pool) {
559 if (!poolLocks->needsLocks(pool))
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);
567 if (!semaphoreLocks) {
568 if (pool.getLocks()) {
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));
577 pool.setLocksAttr(builder.getArrayAttr(names));
581 for (
auto [index, segment] : llvm::enumerate(pool.getSegmentOps())) {
582 if (segment.getProduceLock() && segment.getConsumeLock()) {
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));
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,
true);
603 return canAccess(user, tile);
606 template <
typename Endpo
intOp>
607 void collectLockUsers(EndpointOp endpoint) {
608 auto pool = endpoint.getPoolOp();
609 if (!semaphoreLocks) {
610 lockUsers[pool].push_back(endpoint);
613 for (
auto segment : endpoint.getSelectedSegments())
614 lockUsers[segment].push_back(endpoint);
619 template <
typename Endpo
intOp>
620 SmallVector<Value> endpointLockTiles(EndpointOp endpoint) {
621 SmallVector<Value> tiles;
622 auto pool = endpoint.getPoolOp();
623 if (pool.getDepth() == 0)
625 if (!semaphoreLocks) {
626 if (poolLocks->needsLocks(pool) && !pool.getLocks())
627 tiles.push_back(lockPlacement(pool, pool));
629 for (
auto lock : pool.getLockOps())
630 tiles.push_back(lock.getTile());
633 for (
auto segment : endpoint.getSelectedSegments()) {
634 if (poolLocks->needsLocks(pool) &&
635 !(segment.getProduceLock() && segment.getConsumeLock())) {
636 tiles.push_back(lockPlacement(pool, segment));
640 {segment.getProduceLockAttr(), segment.getConsumeLockAttr()})
643 tiles.push_back(lock.getTile());
652 bool reachesAdjacentTile(RouteEndpoint endpoint) {
653 if (ownReachesAdjacentTile(endpoint))
655 for (
auto [sharer, owner] : channelSharers)
656 if (owner == endpoint.getOperation() &&
657 ownReachesAdjacentTile(cast<RouteEndpoint>(sharer)))
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()) {
671 ObjectFifoPoolOp pool = dma.getPoolOp();
672 auto remote = [&](Value tile) {
673 return tile && !sameTile(tile, endpoint.getTile());
675 return pool && (llvm::any_of(bufferPlacements[pool], remote) ||
676 llvm::any_of(endpointLockTiles(dma), remote));
679 TileLike tileOf(RouteEndpoint endpoint) {
680 return dyn_cast<TileLike>(endpoint.getTile().getDefiningOp());
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();
691 static int64_t countBDs(Region &taskBody) {
693 taskBody.walk([&](DMABDOp) { bds++; });
698 int64_t endpointBDs(Operation *endpoint) {
700 for (DMAStartOp start : endpointStarts.lookup(endpoint))
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());
716 int64_t endpointTaskBDs(Operation *endpoint) {
718 for (
auto task : endpointTasks.lookup(endpoint))
719 largest = std::max(largest, countBDs(task.getBody()));
725 bool programReachesAdjacentTile(RouteEndpointOp endpoint) {
726 if (!endpoint.getTileLike().isMemTile())
728 auto remote = [&](Operation *op) {
730 if (
auto bd = dyn_cast<DMABDOp>(op)) {
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();
738 return tile && !sameTile(tile, endpoint.getTile());
740 for (DMAStartOp start : endpointStarts.lookup(endpoint))
742 if (llvm::any_of(block->getOperations(),
743 [&](Operation &op) { return remote(&op); }))
745 for (
auto task : endpointTasks.lookup(endpoint)) {
746 bool reaches =
false;
747 task.getBody().walk([&](Operation *op) { reaches |= remote(op); });
756 void collectChannelPrograms() {
757 endpointStarts.clear();
758 endpointTasks.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();
767 return std::make_tuple(*col, *row, channel);
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);
795 void rankStructurally() {
796 StructuralGraph graph;
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();
803 graph.
add(tileNode[tile] = tile);
806 auto [it, first] = placed.try_emplace({*col, *row}, tile);
807 tileNode[tile] = it->second;
809 graph.
nodes.push_back(tile);
810 llvm::raw_string_ostream(graph.
features[tile])
811 <<
"tile " << *col <<
' ' << *row <<
' '
812 << stringifyAIETileType(tile.getTileType());
815 auto link = [&](Operation *from, Operation *to, StringRef label) {
816 if (Operation *tile = tileNode.lookup(to))
818 graph.
link(from, to, label);
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");
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");
835 for (
auto endpoint : device.getOps<RouteEndpoint>()) {
836 llvm::raw_string_ostream os(graph.
add(endpoint));
838 dyn_cast<ObjectFifoDmaEndpointOp>(endpoint.getOperation())) {
839 for (
auto segment : dma.getSelectedSegments())
840 os <<
" @" << segment.getOffset();
841 link(endpoint, dma.getPoolOp(),
"pool");
843 link(endpoint, endpoint.getTile().getDefiningOp(),
"tile");
845 for (
auto route : device.getOps<RouteOp>()) {
847 for (StringRef source : route.getSourceNames())
848 link(route, lookupEndpoint(source),
"source");
849 for (StringRef dest : route.getDestinationNames())
850 link(route, lookupEndpoint(dest),
"dest");
852 DenseMap<Operation *, unsigned> rank = graph.
rank();
856 for (Operation *node : graph.
nodes)
857 graph.
features[node] = llvm::formatv(
"{0,10}", rank[node]).str();
858 for (
auto core : device.getOps<CoreOp>()) {
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());
870 for (
auto [tile, node] : tileNode)
871 rank[tile] = rank[node];
872 structuralRank = std::move(rank);
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 =
886 llvm::find_if(groups, [&](
const DMAChannelAnalysis::BDGroup &g) {
887 return llvm::is_contained(g.
channels, channel);
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())
899 DMAChannelAnalysis::BDPlanEnd planEnd(RouteEndpoint endpoint,
bool adjacent,
901 DMAChannelDir dir = endpoint.getRouteDirection();
903 dir, bdsOf(endpoint),
905 keepPin ? endpoint.getRouteChannel() : std::nullopt};
912 int chooseChannel(DMAChannelAnalysis &channels, RouteEndpoint endpoint,
913 const DenseMap<std::tuple<int, int, int>, int64_t> &demand,
915 TileLike tile = tileOf(endpoint);
916 DMAChannelDir dir = endpoint.getRouteDirection();
917 std::optional<int> col = tile.tryGetCol(), row = tile.tryGetRow();
920 endpoint.getOperation());
922 int64_t bestRoom = 0;
924 for (
int channel = 0; channel < limit; ++channel) {
927 int64_t room = bdRoom(tile, *col, *row, channel, demand);
928 if (best < 0 || room > bestRoom) {
936 endpoint.getOperation());
939 void noteChannelOwner(InFlightDiagnostic &diag, Operation *owner,
940 std::optional<int> channel = std::nullopt) {
941 auto ¬e = 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";
949 note <<
"; occupies channel " << *channel;
950 }
else if (channel) {
951 note <<
"pre-existing " << owner->getName() <<
" reserves DMA channel "
957 DenseSet<Operation *> packetEndpoints() {
958 DenseSet<Operation *> endpoints;
959 for (
auto flow : device.getOps<RouteOp>()) {
960 if (!flow.getPacket())
962 for (StringRef source : flow.getSourceNames())
963 endpoints.insert(lookupEndpoint(source).getOperation());
964 for (StringRef dest : flow.getDestinationNames())
965 endpoints.insert(lookupEndpoint(dest).getOperation());
972 LogicalResult checkStreamPorts() {
973 DMAChannelAnalysis channels(device);
974 DenseSet<Operation *> packetEndpoints = this->packetEndpoints();
976 for (
auto endpoint : device.getOps<RouteEndpoint>()) {
977 if (endpoint.getRouteBundle() != WireBundle::Core)
979 std::optional<int> channel = endpoint.getRouteChannel();
981 return endpoint->emitOpError(
"a stream port names its own channel");
983 tileOf(endpoint), {endpoint.getRouteDirection(), *channel},
984 endpoint.getOperation(),
985 packetEndpoints.contains(endpoint.getOperation())));
987 return failure(clash);
992 bool drawsOwnChannel(RouteEndpoint endpoint) {
993 return endpoint.getRouteBundle() != WireBundle::Core &&
994 !channelSharers.contains(endpoint.getOperation()) &&
995 !allocationSharers.contains(endpoint.getOperation());
1000 bool sharesPinnedChannel(RouteEndpoint endpoint, DMAChannelDir dir) {
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))
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();
1017 if (!flow.getPacket())
1019 hasPacketRoute =
true;
1021 return hasPacketRoute;
1024 LogicalResult assignChannels(DMAChannelAnalysis &channels,
1025 bool diagnose =
true) {
1026 channelAssignments.clear();
1027 channelFailure =
nullptr;
1028 bdShortfall =
false;
1029 SmallVector<RouteEndpoint> pending;
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();
1040 demand[{*col, *row, channel}] += bdsOf(endpoint);
1042 for (
auto endpoint : device.getOps<RouteEndpoint>()) {
1043 DMAChannelDir dir = endpoint.getRouteDirection();
1044 std::optional<int> channel = endpoint.getRouteChannel();
1045 if (!drawsOwnChannel(endpoint))
1049 if (reachesAdjacentTile(endpoint) &&
1052 channelFailure = endpoint;
1055 return endpoint->emitOpError(
"pinned ")
1056 << stringifyDMAChannelDir(dir) <<
" DMA channel " << *channel
1057 <<
" cannot access adjacent MemTile buffers or locks";
1060 tileOf(endpoint), dir, *channel, endpoint.getOperation(),
1061 sharesPinnedChannel(endpoint, dir)) < 0) {
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 =
1069 noteChannelOwner(diag, owner, channel);
1072 noteDemand(endpoint, *channel);
1075 pending.push_back(endpoint);
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);
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,
false,
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); }))
1100 int pinnedCol = col, pinnedRow = row;
1101 auto roomOf = [&](RouteEndpoint endpoint) {
1102 return bdRoom(tileOf(endpoint), pinnedCol, pinnedRow,
1103 *endpoint.getRouteChannel(), demand);
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));
1116 RouteEndpoint deepest = starved.front();
1117 channelFailure = deepest;
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";
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)
1152 bool aProgram = isProgramOwned(a), bProgram = isProgramOwned(b);
1153 if (aProgram != bProgram)
1155 int64_t aBDs = programBDs.lookup(a.getOperation());
1156 int64_t bBDs = programBDs.lookup(b.getOperation());
1159 return structuralRank.lookup(a.getOperation()) <
1160 structuralRank.lookup(b.getOperation());
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();
1171 SmallVector<RouteEndpoint> onTile;
1172 SmallVector<DMAChannelAnalysis::BDPlanEnd> ends, unweighted;
1173 for (RouteEndpoint endpoint : pending) {
1174 if (tileOf(endpoint).getOperation() != tileOp)
1176 onTile.push_back(endpoint);
1177 ends.push_back(planEnd(endpoint, reachesAdjacentTile(endpoint),
1179 DMAChannelAnalysis::BDPlanEnd &zeroed =
1180 unweighted.emplace_back(ends.back());
1183 auto free = [&](DMAChannelDir dir,
int channel) {
1186 const AIETargetModel &target = device.getTargetModel();
1188 target, *col, *row, ends, free,
1189 [&](
int channel) {
return demand.lookup({*col, *row, channel}); });
1191 for (
auto [endpoint, channel] : llvm::zip_equal(onTile, *plan))
1192 planned[endpoint.getOperation()] = channel;
1197 free, [](
int) {
return 0; }))
1199 RouteEndpoint deepest =
1200 *llvm::max_element(onTile, [&](RouteEndpoint a, RouteEndpoint b) {
1201 return bdsOf(a) < bdsOf(b);
1203 channelFailure = deepest;
1208 for (
const DMAChannelAnalysis::BDPlanEnd &end : ends)
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";
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()] =
1224 endpoint.getOperation());
1225 noteDemand(endpoint, it->second);
1231 auto dma = dyn_cast<ObjectFifoDmaEndpointOp>(endpoint.getOperation());
1232 std::optional<int> col = tile.tryGetCol(), row = tile.tryGetRow();
1233 if (dma && col && row) {
1235 for (
int free = 0; free < limit; ++free) {
1238 roomy = bdRoom(tile, *col, *row, free, demand) >= dma.getNumBDs();
1242 int channel = isProgramOwned(endpoint) || !roomy
1243 ? chooseChannel(channels, endpoint, demand, 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;
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";
1259 channelFailure = endpoint;
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 "
1272 diag <<
" for adjacent MemTile access";
1274 for (
int i = 0; i < capacity; ++i)
1276 noteChannelOwner(diag, owner, i);
1277 noteChannelOwner(diag, endpoint.getOperation());
1280 channelAssignments[endpoint.getOperation()] = channel;
1281 noteDemand(endpoint, channel);
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 &&
1289 channel, endpoint,
true) < 0) {
1290 channelFailure = end;
1293 auto diag = endpoint->emitOpError(
"cannot share ");
1294 diag << stringifyDMAChannelDir(alloc.getChannelDir()) <<
" DMA channel "
1295 << channel <<
": already in use or unavailable";
1297 tileOf(end), alloc.getChannelDir(), channel))
1298 noteChannelOwner(diag, owner, channel);
1301 channelAssignments[endpoint] = channel;
1302 noteDemand(end, channel);
1304 for (
auto [sharer, owner] : channelSharers)
1305 channelAssignments[sharer] = channelAssignments.lookup(owner);
1309 for (
auto &[at, bds] : taskBDs)
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());
1322 channelDemand = std::move(demand);
1330 bool planShimSharing(TileLike exhausted, DMAChannelDir dir) {
1333 ShimTransferSpans spans(
1335 [&](StringAttr symbol) {
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)
1347 candidates.push_back(endpoint);
1349 names.push_back(endpoint.getSymNameAttr());
1351 SmallVector<ShimDMAAllocationOp> allocations;
1352 SmallVector<ShimTransferSpans::SharedChannel> shared;
1353 for (
auto alloc : device.getOps<ShimDMAAllocationOp>()) {
1354 auto allowed = AIEDialect::ShareableWithAttrHelper(alloc->getContext())
1356 if (!allowed || alloc.getTile() != exhausted->getResult(0) ||
1357 alloc.getChannelDir() != dir)
1359 SmallVector<StringAttr> listed;
1360 for (Attribute attr : allowed)
1361 if (
auto symbol = dyn_cast<FlatSymbolRefAttr>(attr))
1362 listed.push_back(symbol.getAttr());
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();
1370 allocations.push_back(alloc);
1371 shared.emplace_back(std::move(listed), pinned);
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])
1380 for (
auto &members : plan.
groups)
1381 for (
unsigned sharer : llvm::drop_begin(members))
1383 .insert({candidates[sharer], candidates[members.front()]})
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);
1406 SmallVector<ObjectFifoPoolOp> pools;
1407 SmallVector<DMAChannelAnalysis::BDWalkPool> walkable;
1408 SmallVector<DMAChannelAnalysis::BDPlanEnd> ends;
1409 SmallVector<unsigned> poolOf;
1411 HomeBDPlan homeBDPlan(ArrayRef<ObjectFifoDmaEndpointOp> dmas) {
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);
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))
1426 plan.ends.push_back(planEnd(endpoint,
false,
1428 plan.poolOf.push_back(llvm::find(plan.pools, dma.getPoolOp()) -
1429 plan.pools.begin());
1438 bool walkForBDShortfall(TileLike tile,
1439 MutableArrayRef<ObjectFifoPoolOp> pools) {
1440 if (walkHomeBDPools(pools))
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);
1448 plan.ends, plan.poolOf, plan.walkable,
1449 SmallVector<bool>(plan.pools.size(),
false));
1451 plan.pools[*next].setContiguous(
true);
1452 return next.has_value();
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);
1470 DMAChannelAnalysis::BDWalkSets found;
1471 SmallVector<ObjectFifoDmaEndpointOp> dmas;
1472 unsigned applied = 0;
1474 SmallVector<Tile, 0> tiles;
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);
1490 [&](
int channel) { return taken.lookup(channel); });
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;
1500 if (!found.
sets.empty())
1502 {{at.first, at.second}, std::move(home), std::move(found), dmas});
1504 auto setWalked = [&](Tile &tile,
bool walked) {
1505 for (
unsigned pool : tile.found.sets[tile.applied])
1506 tile.home.pools[pool].setContiguous(walked);
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};
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 =
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;
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)
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);
1555 DMAChannelAnalysis::WalkChoice choice =
1558 [&](ArrayRef<unsigned> choice) {
1560 SmallVector<ObjectFifoPoolOp> trial(componentPools);
1563 return succeeded(planBuffers(trial));
1567 walkSearchStopped |= choice.
stopped;
1568 for (Tile *tile : members) {
1569 if (tile->found.sets[tile->applied].empty())
1572 for (
auto dma : tile->dmas)
1574 tileOf(cast<RouteEndpoint>(dma.getOperation())).getOperation());
1583 bool hostMovesFirst(StringAttr fifo) {
1584 if (
auto it = hostMovesFirstCache.find(fifo);
1585 it != hostMovesFirstCache.end())
1587 bool result = hostMovesFirstUncached(fifo);
1588 hostMovesFirstCache[fifo] = result;
1591 bool hostMovesFirstUncached(StringAttr fifo) {
1592 SymbolTableCollection symbols;
1593 for (
auto seq : device.getOps<RuntimeSequenceOp>()) {
1594 auto names = [&](Operation *op) {
1597 auto waits = [](Operation *op) {
1598 return isa<AIEX::NpuDmaWaitOp, AIEX::DMAAwaitTaskOp, AIEX::NpuSyncOp,
1599 AIEX::NpuMaskPollOp>(op);
1601 bool waited =
false;
1602 WalkResult walk = seq.walk<WalkOrder::PreOrder>([&](Operation *op) {
1605 return WalkResult::advance();
1607 Operation *transfer = op;
1608 if (
auto start = dyn_cast<AIEX::DMAStartTaskOp>(op))
1609 transfer = start.getTask().getDefiningOp();
1611 !isa<AIEX::NpuDmaMemcpyNdOp, AIEX::DMAConfigureTaskForOp,
1612 AIEX::DMAStartBdChainForOp>(transfer) ||
1613 isa<AIEX::DMAConfigureTaskForOp>(op) || !names(transfer))
1614 return WalkResult::advance();
1616 return WalkResult::interrupt();
1617 for (Operation *parent = op->getParentOp(); parent != seq;
1618 parent = parent->getParentOp())
1620 ->walk([&](Operation *inner) {
1621 return waits(inner) ? WalkResult::interrupt()
1622 : WalkResult::advance();
1625 return WalkResult::interrupt();
1626 return WalkResult::advance();
1628 if (walk.wasInterrupted())
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))
1646 if (peer || route.getPacket() || sources.size() != 1 || dests.size() != 1)
1648 RouteEndpoint other = lookupEndpoint(source ? dests[0] : sources[0]);
1649 peer = other ? dyn_cast<ObjectFifoDmaEndpointOp>(other.getOperation())
1650 : ObjectFifoDmaEndpointOp();
1659 ObjectFifoCoreEndpointOp coreEndOf(ObjectFifoDmaEndpointOp endpoint) {
1660 ObjectFifoCoreEndpointOp found;
1661 for (
auto core : device.getOps<ObjectFifoCoreEndpointOp>()) {
1662 if (core.getPool() != endpoint.getPool())
1664 if (found || core.drains() == endpoint.drains())
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()
1681 : end.getNumDescriptors()});
1689 static bool contiguousWalkersFit(ArrayRef<ObjectFifoDmaEndpointOp> ends,
1690 ArrayRef<unsigned> turns) {
1691 SmallVector<std::pair<int64_t, int64_t>> counts = turnCounts(ends, turns);
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)))
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);
1715 channelSharers[end] = owner;
1723 bool planTurnSharing(TileLike exhausted, DMAChannelDir dir) {
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);
1736 auto endsOf = [&](Operation *pool) -> ArrayRef<ObjectFifoDmaEndpointOp> {
1737 auto it = poolEnds.find(pool);
1738 return it == poolEnds.end() ? ArrayRef<ObjectFifoDmaEndpointOp>()
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();
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])
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) {
1762 senderOf[end.getOperation()] = sender;
1763 if (end && onShim(source))
1764 byShim.insert(end.getOperation());
1766 if (llvm::all_of(dests,
1767 [&](RouteEndpoint end) {
return end && onShim(end); }))
1768 byShim.insert(source.getOperation());
1770 auto cachedCoreEnd = [&](ObjectFifoDmaEndpointOp dma) {
1771 return coreEndCache.lookup(dma);
1773 auto cachedCircuitPeer = [&](ObjectFifoDmaEndpointOp dma) {
1774 return circuitPeerCache.lookup(dma);
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);
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())
1800 auto groupOf = [](ObjectFifoDmaEndpointOp end) {
1801 SmallVector<ObjectFifoDmaEndpointOp> group =
turnEndpoints(end);
1802 return group.empty() ? SmallVector<ObjectFifoDmaEndpointOp>{end} : group;
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))
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());
1818 if (llvm::any_of(peers, [&](ObjectFifoDmaEndpointOp peer) {
1819 return !sameTile(peer.getTile(), peers.front().getTile()) ||
1821 return !llvm::is_contained(peers, other);
1824 LLVM_DEBUG(llvm::dbgs()
1825 <<
" " << a.getSymName() <<
" + " << b.getSymName()
1826 <<
": senders on different tiles\n");
1831 if (succeeded(turns.
read(cores, reason)) && !turns.
keepsUp(depths))
1832 reason =
"would stall";
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);
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;
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) {
1875 if (byShim.contains(across.front())) {
1876 hostWaits |= !hostMovesFirst(across.front().getFifoNameAttr());
1879 at = across.front().drains() ? cachedCircuitPeer(across.front())
1880 : senderOf.lookup(across.front());
1885 depth += at.getPoolOp().getDepth();
1886 core = cachedCoreEnd(at);
1890 if (llvm::is_contained(peerCores, core)) {
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);
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";
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)
1914 int64_t part = ++taken[turn];
1915 if (part > asked[fed[turn]]) {
1916 asked[fed[turn]] = part;
1917 peerOrder.push_back(fed[turn]);
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";
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());
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";
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();
1953 device.getTargetModel().getNumBDsForChannel(*col, *row, 0);
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");
1976 pool.setContiguous(
true);
1978 llvm::all_of(others, [&](ObjectFifoDmaEndpointOp end) {
1979 SmallVector<ObjectFifoDmaEndpointOp> ends =
1981 SmallVector<unsigned> order;
1983 end.getTurnsAttr().getAsRange<FlatSymbolRefAttr>())
1986 [&](ObjectFifoDmaEndpointOp e) {
1987 return e.getSymNameAttr() ==
1991 return contiguousWalkersFit(ends, order);
1995 <<
" " << pool.getSymName() <<
" walked whole"
1996 << (linedUp ?
"" :
", but its other turns would not line up")
1999 walked.push_back(pool);
2000 turnWalked.insert(pool);
2002 pool.setContiguous(
false);
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);
2010 if (!reason.empty()) {
2011 LLVM_DEBUG(llvm::dbgs() <<
" " << a.getSymName() <<
" + "
2012 << b.getSymName() <<
": " << reason <<
"\n");
2015 takeTurns(group, turns.
turns());
2016 takeTurns(peers, turns.
turns());
2027 LogicalResult headShimSharingRoutes() {
2028 DenseMap<Operation *, Operation *> channelOf;
2029 for (
auto [sharer, owner] : channelSharers) {
2030 if (!tileOf(cast<RouteEndpoint>(owner)).isShimTile())
2032 channelOf[sharer] = owner;
2033 channelOf[owner] = owner;
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()));
2044 llvm::for_each(route.getSourceNames(), note);
2045 llvm::for_each(route.getDestinationNames(), note);
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())
2060 auto freeOnAll = [&](
int id) {
2061 return llvm::none_of(channels, [&](Operation *channel) {
2062 return idsOn[channel].contains(
id);
2065 std::optional<int> id;
2066 if (
auto *it = llvm::find_if(reused, freeOnAll); it != reused.end())
2069 reused.push_back(*
id);
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)));
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 ||
2093 int channel = it->second;
2094 int64_t room = bdRoom(tile, *col, *row, channel, channelDemand);
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";
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);
2127 if (tried.size() >= 64 || !tried.insert(key).second ||
2128 failed(planBuffers(pools)) || failed(planLocks(pools)))
2130 DMAChannelAnalysis channels(device);
2131 if (succeeded(assignChannels(channels,
false)))
2133 if (!channelFailure || !tileOf(channelFailure).isMemTile() ||
2134 !tileOf(channelFailure).tryGetCol() ||
2135 !tileOf(channelFailure).tryGetRow())
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))
2151 candidates.push_back(pool);
2153 llvm::stable_sort(candidates, [&](ObjectFifoPoolOp a, ObjectFifoPoolOp b) {
2155 a.getBuffers() ? 0 : a.getObjectSizeInBytes() * a.getDepth();
2157 b.getBuffers() ? 0 : b.getObjectSizeInBytes() * b.getDepth();
2158 if (aBytes != bBytes)
2159 return aBytes < bBytes;
2160 return structuralRank.lookup(a) < structuralRank.lookup(b);
2162 for (
auto pool : candidates) {
2163 localPools[pool] = localTile;
2164 if (succeeded(planAllocation(pools, tried)))
2166 localPools.erase(pool);
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;
2182 if (
auto dma = dyn_cast<ObjectFifoDmaEndpointOp>(*source);
2183 dma && dma.getDispatch()) {
2184 dispatchHeaders[dma][*flow.getDestinationNames().begin()] = header;
2187 if (sourcedFlows.at(name.getAttr()).size() == 1)
2188 source.setRoutePacket(header);
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();
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());
2209 builder.setInsertionPointToStart(&ports);
2210 for (RouteEndpoint source : sources) {
2211 PacketSourceOp::create(builder, flow.getLoc(), source.getTile(),
2212 source.getRouteBundle(), channelOf(source));
2214 for (StringRef destName : flow.getDestinationNames()) {
2215 auto dest = lookupEndpoint(destName);
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));
2228 int channelOf(RouteEndpoint endpoint) {
2229 std::optional<int> channel = endpoint.getRouteChannel();
2230 assert(channel &&
"channels are assigned before flows are lowered");
2234 RouteEndpoint lookupEndpoint(StringRef name) {
2235 return dyn_cast_or_null<RouteEndpoint>(SymbolTable::lookupNearestSymbolFrom(
2236 device, StringAttr::get(device.getContext(), name)));
2239 LogicalResult lowerFlows() {
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())
2247 for (StringRef name : flow.getSourceNames()) {
2248 auto source = dyn_cast<ObjectFifoDmaEndpointOp>(
2249 lookupEndpoint(name).getOperation());
2251 source.getReleaseStrategy() != ObjectFifoRelease::PushQueue)
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 "
2261 diag.attachNote(it->second->getLoc()) <<
"other sender is here";
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));
2275 loweredFlows.push_back(flow);
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");
2284 if (failed(lowerPacketFlow(flow, sources, *packet))) {
2291 RouteEndpoint source = sources.front();
2293 int sourceChannel = channelOf(source);
2294 builder.setInsertionPoint(flow);
2295 for (StringRef destName : flow.getDestinationNames()) {
2296 auto dest = lookupEndpoint(destName);
2299 .insert({source.getTile(), sourceChannel, dest.getTile(),
2303 FlowOp::create(builder, flow.getLoc(), source.getTile(),
2304 source.getRouteBundle(), sourceChannel, dest.getTile(),
2305 dest.getRouteBundle(), channelOf(dest));
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));
2321 LogicalResult bindRearmTargets() {
2322 if (poolLocks->rearms().empty()) {
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;
2331 SmallVector<Location> locs;
2333 for (
auto endpoint : device.getOps<RouteEndpoint>()) {
2334 std::optional<int> channel = endpoint.getRouteChannel();
2335 if (endpoint.getFifoName() != fifoName ||
2336 tileOf(endpoint).isShimTile() || !channel) {
2340 dyn_cast<ObjectFifoDmaEndpointOp>(endpoint.getOperation());
2341 dma && dma.getReleaseStrategy() == ObjectFifoRelease::PushQueue) {
2342 for (AIEX::DmaChannelResetForOp user : users)
2344 "does not support core-pushed DMA channels; reset requires "
2345 "coordination with the issuing core and all shared senders");
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());
2354 for (
auto pool : device.getOps<ObjectFifoPoolOp>()) {
2355 if (pool.getFifoName() != fifoName || pool.getTileLike().isShimTile()) {
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));
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 "
2374 std::string name = (fifoName +
"__rearm").str();
2377 name = (fifoName +
"__rearm" + std::to_string(suffix + 1)).str();
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 DenseI32ArrayAttr(),
2388 DenseI32ArrayAttr());
2389 auto target = FlatSymbolRefAttr::get(builder.getContext(), name);
2390 for (AIEX::DmaChannelResetForOp user : users) {
2391 user.setObjfifoAttr(target);
2398 LogicalResult resolveStart(DMAStartOp start, RouteEndpointOp endpoint,
2399 ArrayRef<RouteOp> flows, ArrayRef<int> ids,
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);
2409 bool packet = !flows.empty() && RouteOp(flows.front()).getPacket();
2411 SmallVector<DMABDOp> bds;
2413 llvm::append_range(bds, block->getOps<DMABDOp>());
2414 if (failed(checkHeaders(endpoint, ids, bds)))
2417 start.setChannelAttr(builder.getI32IntegerAttr(channel));
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))
2433 return bd.emitOpError(
"sends on @")
2434 << endpoint.getSymName()
2435 <<
" without the packet header of one of its flows, ids " << ids;
2443 LogicalResult checkSharedSourceUsers(RouteEndpointOp endpoint,
2444 ArrayRef<int> ids) {
2445 auto uses = SymbolTable::getSymbolUses(endpoint, device);
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)))
2457 if (
auto start = dyn_cast<AIEX::DMAStartBdChainForOp>(user)) {
2458 auto chain = device.lookupSymbol<BDChainOp>(start.getSymbol());
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)))
2467 auto memcpy = dyn_cast<AIEX::NpuDmaMemcpyNdOp>(user);
2470 std::optional<PacketInfoAttr> packet = memcpy.getPacket();
2471 if (packet && llvm::is_contained(ids, packet->getPktId()))
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 "
2485 void resolveTask(AIEX::DMAConfigureTaskForOp task, RouteEndpointOp endpoint,
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 UnitAttr(), FlatSymbolRefAttr());
2497 task.getResult().replaceAllUsesWith(configured.getResult());
2498 configured.getBody().takeBody(task.getBody());
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)))
2521 if (starts.empty() && tasks.empty())
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)))
2528 if (endpoint.getTileLike().isShimTile() && endpoint.getFifoName())
2530 for (
auto task : tasks)
2531 resolveTask(task, endpoint, *channel);
2538 void emitShimAllocations() {
2539 builder.setInsertionPoint(device.getBody()->getTerminator());
2544 llvm::StringMap<unsigned> shimEndsSeen;
2545 for (
auto endpoint : device.getOps<RouteEndpoint>()) {
2546 std::optional<StringRef> fifoName = endpoint.getFifoName();
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) {
2554 std::string name = (*fifoName +
"__shim_alloc").str();
2555 unsigned ordinal = shimEndsSeen[*fifoName]++;
2559 create = !SymbolTable::lookupNearestSymbolFrom<ShimDMAAllocationOp>(
2560 device, builder.getStringAttr(name));
2562 for (
unsigned suffix = ordinal - 1; device.lookupSymbol(name);
2565 (*fifoName +
"__shim_alloc" + std::to_string(suffix + 1)).str();
2571 auto routeEndpoint = dyn_cast<RouteEndpointOp>(endpoint.getOperation());
2572 ShimDMAAllocationOp::create(
2573 builder, endpoint.getLoc(), builder.getStringAttr(name),
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());
2583 (void)SymbolTable::replaceAllSymbolUses(
2584 endpoint, builder.getStringAttr(name), device);
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);
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));
2607 return home(a) < home(b);
2610 for (
auto [slot, pool] : llvm::zip(memTileSlots, memTilePools))
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()))
2623 auto &demand = poolChannelDemand[pool];
2624 if (endpoint.getRouteDirection() == DMAChannelDir::S2MM)
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())
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());
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)});
2648 SmallVector<ObjectFifoPoolOp> ordered(pools);
2649 for (
auto [slot, index] :
2651 ordered[slot] = pools[memTileSlots[index]];
2655 void runOnOperation()
override {
2656 device = getOperation();
2657 builder = OpBuilder(device.getContext());
2662 channelSharers.clear();
2663 allocationSharers.clear();
2665 loweredFlows.clear();
2666 sourcedFlows.clear();
2670 lockPlacements.clear();
2672 dispatchHeaders.clear();
2673 channelSharers.clear();
2676 hostMovesFirstCache.clear();
2677 bufferPlacements.clear();
2678 channelAssignments.clear();
2679 endpointStarts.clear();
2680 endpointTasks.clear();
2683 channelDemand.clear();
2684 structuralRank.clear();
2685 channelFailure =
nullptr;
2686 bufferFailure =
nullptr;
2687 lockFailure =
nullptr;
2688 lockAccessFailure =
nullptr;
2689 walkSearchStopped =
false;
2691 if (failed(collectFixedMemory()) || failed(checkStreamPorts()))
2692 return signalPassFailure();
2693 collectChannelPrograms();
2698 SmallVector<ObjectFifoPoolOp> pools(device.getOps<ObjectFifoPoolOp>());
2699 llvm::stable_sort(pools, [&](ObjectFifoPoolOp a, ObjectFifoPoolOp b) {
2700 return structuralRank.lookup(a) < structuralRank.lookup(b);
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);
2709 for (
auto endpoint : device.getOps<ObjectFifoDmaEndpointOp>()) {
2710 poolUsers[endpoint.getPoolOp()].push_back(endpoint.getTile());
2711 collectLockUsers(endpoint);
2713 for (
auto &[group, users] : lockUsers)
2714 llvm::stable_sort(users, [&](Operation *a, Operation *b) {
2715 return structuralRank.lookup(a) < structuralRank.lookup(b);
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)) {
2726 allocated = planAllocation(demandOrdered, tried);
2736 if (channelFailure) {
2737 TileLike tile = tileOf(channelFailure);
2738 DMAChannelDir dir = channelFailure.getRouteDirection();
2740 if (bdPlanned.insert(tile.getOperation()) ||
2741 walkForBDShortfall(tile, pools))
2743 }
else if (tile.isShimTile() ? planShimSharing(tile, dir)
2744 : planTurnSharing(tile, dir)) {
2749 return failed(planBuffers(pools)) && walkHomeBDPools(pools);
2751 while (failed(allocated) && repair()) {
2755 allocated = planAllocation(pools, tried);
2757 if (succeeded(allocated) &&
2758 (!channelSharers.empty() || !allocationSharers.empty()) &&
2759 failed(headShimSharingRoutes()))
2760 return signalPassFailure();
2761 if (failed(allocated)) {
2763 if (failed(planBuffers(pools))) {
2764 InFlightDiagnostic error =
2766 ? bufferFailure.emitOpError(
2767 "could not place buffers: the search for which pools "
2768 "to make contiguous (one buffer, one BD per side) "
2771 <<
" placements tried in one group of neighbouring "
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)}));
2789 if (!walked.empty()) {
2790 Diagnostic ¬e = error.attachNote();
2792 llvm::interleaveComma(walked, note);
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 ")
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");
2809 lockFailure.getDefiningOp()->emitOpError(
2810 "could not place locks within tile lock capacity");
2812 DMAChannelAnalysis channels(device);
2813 (void)assignChannels(channels);
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");
2819 return signalPassFailure();
2821 for (ObjectFifoPoolOp pool : pools) {
2822 allocateBuffers(pool);
2823 allocateLocks(pool);
2825 for (TileOp tile : spillTiles)
2826 if (tile->use_empty())
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();
2837 llvm::EquivalenceClasses<Operation *> matchingPools;
2838 DenseMap<Operation *, int64_t> descriptorCounts;
2839 for (
auto flow : device.getOps<RouteOp>()) {
2840 if (flow.getSources().size() != 1)
2842 ObjectFifoPoolOp first;
2843 for (
auto destName : flow.getDestinationNames()) {
2844 RouteEndpoint receiver = lookupEndpoint(destName);
2847 ? dyn_cast<ObjectFifoDmaEndpointOp>(receiver.getOperation())
2849 if (!dst || !dst.getOutOfOrder())
2851 ObjectFifoPoolOp pool = dst.getPoolOp();
2854 matchingPools.unionSets(first.getOperation(), pool.getOperation());
2855 descriptorCounts[pool] = dst.getNumDescriptors();
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())
2864 Operation *leader = *member;
2865 auto &tags = tagsOfGroup[leader];
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);
2872 pool.setOutOfOrderTagsAttr(tags);
2877 for (
auto flow : device.getOps<RouteOp>()) {
2878 if (flow.getSources().size() != 1)
2880 RouteEndpoint sender = lookupEndpoint(*flow.getSourceNames().begin());
2882 ? dyn_cast<ObjectFifoDmaEndpointOp>(sender.getOperation())
2884 if (!src || !src.getOutOfOrder())
2886 for (
auto destName : flow.getDestinationNames()) {
2887 RouteEndpoint receiver = lookupEndpoint(destName);
2890 ? dyn_cast<ObjectFifoDmaEndpointOp>(receiver.getOperation())
2892 if (dst && dst.getOutOfOrder()) {
2893 src.setOutOfOrderTagsAttr(dst.getPoolOp().getOutOfOrderTagsAttr());
2899 if (failed(bindRearmTargets())) {
2900 return signalPassFailure();
2902 if (failed(lowerFlows()) || failed(resolveEndpointUses())) {
2903 return signalPassFailure();
2905 emitShimAllocations();
2906 for (Operation *flow : loweredFlows) {
2914std::unique_ptr<OperationPass<DeviceOp>>
2916 return std::make_unique<AIEObjectFifoAllocatePass>();
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.
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.
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)
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...
constexpr llvm::StringLiteral kNoBufferRoom
How --aie-objectfifo-allocate says a pool's buffers fit no memory its users reach; the diagnostic's s...
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< int > channels
llvm::SmallVector< int64_t > bytes
The bytes each set walks whole.
llvm::SmallVector< llvm::SmallVector< unsigned > > sets
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.
std::optional< unsigned > full
The last such candidate, when all were full.
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.