17#include "mlir/IR/Diagnostics.h"
18#include "mlir/Interfaces/ViewLikeInterface.h"
19#include "mlir/Parser/Parser.h"
20#include "mlir/Pass/PassManager.h"
21#include "llvm/ADT/DenseSet.h"
22#include "llvm/ADT/MapVector.h"
23#include "llvm/ADT/STLExtras.h"
24#include "llvm/ADT/SetVector.h"
25#include "llvm/ADT/TypeSwitch.h"
26#include "llvm/Support/Debug.h"
37#define DEBUG_TYPE "aie-placer"
39static std::optional<TileID> resolvePeerPosition(TileLike peer,
43 if (!first || !second)
45 unsigned idx =
edges.size();
46 edges.push_back({first, second});
47 if (mlir::isa<LogicalTileOp>(first.getOperation()))
49 if (mlir::isa<LogicalTileOp>(second.getOperation()))
56 auto aT = dyn_cast_or_null<TileLike>(a.getDefiningOp());
57 auto bT = dyn_cast_or_null<TileLike>(b.getDefiningOp());
70 for (CoreOp core : device.getOps<CoreOp>())
71 if (
auto tile = dyn_cast_or_null<TileOp>(core.getTile().getDefiningOp()))
76 for (
int col = 0; col < tm.
columns(); col++) {
77 for (
int row = 0; row < tm.
rows(); row++) {
80 case AIETileType::CoreTile:
84 case AIETileType::MemTile:
85 case AIETileType::ShimNOCTile:
97 device.walk([&](Operation *op) {
98 llvm::TypeSwitch<Operation *>(op)
99 .Case<LogicalTileOp>([&](
auto lt) { ops.
logicalTiles.push_back(lt); })
100 .Case<ObjectFifoCreateOp>(
102 .Case<ObjectFifoLinkOp>(
104 .Case<ObjectFifoAllocateOp>(
106 .Case<CascadeFlowOp>([&](
auto cf) { ops.
cascadeFlows.push_back(cf); })
107 .Case<FlowOp>([&](
auto f) { ops.
flows.push_back(f); })
108 .Case<PacketFlowOp>([&](
auto pf) { ops.
pktFlows.push_back(pf); })
109 .Case<RouteOp>([&](
auto route) { ops.
routes.push_back(route); });
115 llvm::stable_sort(ops.
logicalTiles, [&](LogicalTileOp a, LogicalTileOp b) {
116 if (a.getTileType() != b.getTileType())
117 return a.getTileType() > b.getTileType();
118 return ops.rank.lookup(a) < ops.rank.lookup(b);
124 if (
auto lt = dyn_cast<LogicalTileOp>(tile)) {
125 if (
auto c = lt.tryGetCol(); c && *c != pos.col)
127 if (
auto r = lt.tryGetRow(); r && *r != pos.row)
141 return a.col < b.col;
142 return a.row < b.row;
146 return a.row < b.row;
147 return a.col < b.col;
157 if (coresPerCol.has_value()) {
158 deviceCoresPerCol = 0;
159 for (
int col = 0; col <
targetModel->columns(); col++) {
161 for (
int row = 0; row <
targetModel->rows(); row++)
162 cores +=
targetModel->getTileType(col, row) == AIETileType::CoreTile;
163 deviceCoresPerCol = std::max(deviceCoresPerCol, cores);
165 DenseSet<TileID> held(
availability.physicalCores.begin(),
167 for (CoreOp core : device.getOps<CoreOp>())
169 dyn_cast_or_null<LogicalTileOp>(core.getTile().getDefiningOp()))
170 if (
auto col = tile.tryGetCol(), row = tile.tryGetRow(); col && row)
171 held.insert({*col, *row});
172 limitCoresPerColumn(*coresPerCol,
targetModel->columns(), held);
176void SequentialPlacer::limitCoresPerColumn(
int maxCoresPerCol,
int numColumns,
177 const DenseSet<TileID> &held) {
178 llvm::DenseMap<int, std::vector<TileID>> tilesByColumn;
180 if (!held.contains(tile))
181 tilesByColumn[tile.col].push_back(tile);
186 DenseMap<int, int> heldInColumn;
188 ++heldInColumn[tile.col];
189 std::vector<TileID> limitedTiles;
190 for (
int col = 0; col < numColumns; col++) {
191 auto it = tilesByColumn.find(col);
192 if (it == tilesByColumn.end())
194 const auto &tilesInCol = it->second;
195 size_t numToTake = std::min<size_t>(
197 std::max(0, maxCoresPerCol - heldInColumn.lookup(col)));
198 limitedTiles.insert(limitedTiles.end(), tilesInCol.begin(),
199 tilesInCol.begin() + numToTake);
205 placeableCores = limitedTiles.size();
215 return device.emitError() <<
"SequentialPlacer::place called before "
216 "initialize(); targetModel is null";
217 if (coresPerCol.has_value() && *coresPerCol > deviceCoresPerCol) {
218 return device.emitError() <<
"requested cores-per-col (" << *coresPerCol
219 <<
") exceeds device capacity ("
220 << deviceCoresPerCol <<
" cores per column)";
225 auto &logicalTiles = collected.logicalTiles;
226 auto &objectFifos = collected.objectFifos;
227 auto &objectFifoLinks = collected.objectFifoLinks;
228 auto &cascadeFlows = collected.cascadeFlows;
229 auto &flows = collected.flows;
230 auto &pktFlows = collected.pktFlows;
231 auto &routes = collected.routes;
234 auto bufferAdjacency =
235 buildBufferAdjacency(logicalTiles, collected.objectFifoAllocates);
241 auto channelRequirements =
242 buildChannelRequirements(objectFifos, objectFifoLinks, collected.rank);
243 if (pinnedRule.failed())
246 llvm::DenseMap<Operation *, Operation *> demandKeys;
251 channelRequirements[tile].first += inOut.first;
252 channelRequirements[tile].second += inOut.second;
254 countTurns(device, objectFifos, channelRequirements);
256 columnStreamsUsed.clear();
257 columnIncomingFifos.clear();
258 broadcastFanoutUsed.clear();
260 if (
auto tile = dyn_cast<TileOp>(op))
261 if (tile.isCoreTile())
262 recordColumnStreamUsage(op, tile.getCol());
264 if (
auto tile = dyn_cast<TileOp>(op))
265 broadcastFanoutUsed[{tile.getCol(), tile.getRow()}] += fanout;
270 for (TileOp tile : device.getOps<TileOp>())
271 addPlacedStreams(tile);
273 collected.rank, demandKeys);
275 overlayTilesAt.clear();
278 for (TileOp placed : device.getOps<TileOp>()) {
279 TileID at = placed.getTileID();
280 auto [in, out] = channelRequirements.lookup(placed);
282 updateChannelUsage(at, DmaDir::In, in);
284 updateChannelUsage(at, DmaDir::Out, out);
285 overlayTilesAt[at].push_back(placed);
286 for (
const PinnedChannels::End &end : pinnedEnds.lookup(placed))
287 pinsAt.place(at, end, 1);
290 pinsAt.claim(at, claim, 1);
291 recordShimEnds(at, placed);
295 if (
auto placed = dyn_cast<TileOp>(tile);
296 placed && placed->getParentOfType<DeviceOp>() != device)
297 overlayTilesAt[placed.getTileID()].push_back(placed);
304 llvm::DenseMap<Operation *, int> forcedSharedMemIn, forcedSharedMemOut;
305 for (
auto ofOp : objectFifos) {
306 if (!ofOp.forcesSharedMemory() || ofOp.getConsumerTiles().size() != 1)
309 dyn_cast_or_null<LogicalTileOp>(ofOp.getProducerTile().getDefiningOp());
310 auto consumer = dyn_cast_or_null<LogicalTileOp>(
311 ofOp.getConsumerTiles()[0].getDefiningOp());
312 if (!producer || producer.getTileType() != AIETileType::CoreTile)
314 if (!consumer || consumer.getTileType() != AIETileType::CoreTile)
316 if (producer.getOperation() == consumer.getOperation())
318 ++forcedSharedMemOut[producer.getOperation()];
319 ++forcedSharedMemIn[consumer.getOperation()];
333 llvm::DenseMap<Operation *, int> needNeighborIn, needNeighborOut;
334 for (
auto lt : logicalTiles) {
335 if (lt.getTileType() != AIETileType::CoreTile)
337 auto [peerIn, peerOut] =
338 totalComputePeers(lt.getOperation(), computePeerAdjacency);
339 auto [inBudget, outBudget] =
341 auto [nonPeerIn, nonPeerOut] =
342 channelRequirements.lookup(lt.getOperation());
343 needNeighborIn[lt.getOperation()] =
344 std::max({0, peerIn - (inBudget - nonPeerIn),
345 forcedSharedMemIn.lookup(lt.getOperation())});
346 needNeighborOut[lt.getOperation()] =
347 std::max({0, peerOut - (outBudget - nonPeerOut),
348 forcedSharedMemOut.lookup(lt.getOperation())});
349 LLVM_DEBUG(llvm::dbgs()
350 <<
DEBUG_TYPE <<
": LTO " << lt.getLoc() <<
" peerIn=" << peerIn
351 <<
" peerOut=" << peerOut <<
" nonPeerIn=" << nonPeerIn
352 <<
" nonPeerOut=" << nonPeerOut
353 <<
" => needNeighborIn=" << needNeighborIn[lt.getOperation()]
354 <<
" needNeighborOut=" << needNeighborOut[lt.getOperation()]
357 PlacementContext ctx{*
targetModel, computePeerAdjacency, needNeighborIn,
363 FlowMembership flowIndex =
364 buildFlowMembership(flows, pktFlows, routes, objectFifos);
365 CoreGroups coreGroups = buildCoreGroups(logicalTiles, flowIndex);
370 auto bufferPred = [
this](
TileID consumerPos,
TileID ownerPos) {
371 return targetModel->isLegalMemAffinity(consumerPos.col, consumerPos.row,
372 ownerPos.col, ownerPos.row);
374 auto bufferLabel = [](
bool thisIsConsumer) -> StringRef {
375 return thisIsConsumer ?
"shared-L1 buffer owner"
376 :
"shared-L1 buffer consumer";
381 auto cascadePred = [
this](
TileID srcPos,
TileID dstPos) {
382 return targetModel->isLegalCascade(srcPos.col, srcPos.row, dstPos.col,
385 auto cascadeLabel = [](
bool thisIsSrc) -> StringRef {
386 return thisIsSrc ?
"cascade destination" :
"cascade source";
394 return targetModel->isLegalMemAffinity(aPos.col, aPos.row, bPos.col,
396 targetModel->isLegalMemAffinity(bPos.col, bPos.row, aPos.col,
399 auto sharedMemLabel = [](
bool thisIsProducer) -> StringRef {
400 return thisIsProducer ?
"shared-memory consumer" :
"shared-memory producer";
403 AdjacencyKind bufferKind{
404 bufferAdjacency, bufferPred, bufferLabel,
"shared-L1 buffer",
405 "shared-L1 buffer adjacency requires this LTO to be on a tile "
406 "whose L1 is shared with the buffer owner's tile (N/S neighbor, "
407 "or W neighbor per the device's checkerboard rule)"};
408 AdjacencyKind cascadeKind{
409 cascadeAdjacency, cascadePred, cascadeLabel,
"cascade",
410 "cascade adjacency requires the destination tile to be one row "
411 "South or one column East of the source tile"};
412 AdjacencyKind sharedMemKind{
413 sharedMemAdjacency, sharedMemPred, sharedMemLabel,
414 "shared-memory transport",
415 "a `shared_mem` objectFifo requires its producer and consumer to "
416 "land on tiles that share a memory module (N/S neighbor, or W "
417 "neighbor per the device's checkerboard rule)"};
437 SmallVector<LogicalTileOp> orderedTiles;
438 llvm::DenseSet<unsigned> emittedGroups;
439 for (
auto lt : logicalTiles) {
440 auto group = coreGroups.groupOf.find(lt.getOperation());
441 if (group == coreGroups.groupOf.end())
442 orderedTiles.push_back(lt);
443 else if (emittedGroups.insert(group->second).second)
444 llvm::append_range(orderedTiles, coreGroups.members[group->second]);
446 llvm::stable_sort(orderedTiles, [&](LogicalTileOp a, LogicalTileOp b) {
447 auto rank = [](LogicalTileOp lt) {
448 bool hasCol = lt.tryGetCol().has_value();
449 bool hasRow = lt.tryGetRow().has_value();
450 if (hasCol && hasRow)
452 if (hasCol || hasRow)
456 int ra = rank(a), rb = rank(b);
464 int pa = ctx.placementPriority(a.getOperation());
465 int pb = ctx.placementPriority(b.getOperation());
471 return ctx.neighborDemand(a.getOperation()) >
472 ctx.neighborDemand(b.getOperation());
477 auto unpinned = [](LogicalTileOp lt) {
478 return !lt.tryGetCol() && !lt.tryGetRow();
480 SmallVector<LogicalTileOp> sequenced;
481 llvm::DenseSet<Operation *> queued;
482 for (
auto start : orderedTiles) {
483 if (!queued.insert(start.getOperation()).second)
485 size_t next = sequenced.size();
486 sequenced.push_back(start);
487 for (; next < sequenced.size(); ++next) {
488 LogicalTileOp lt = sequenced[next];
492 [&](TileLike peer,
bool ) {
493 auto peerLt = dyn_cast<LogicalTileOp>(peer.getOperation());
494 if (peerLt && unpinned(peerLt) &&
495 queued.insert(peerLt.getOperation()).second)
496 sequenced.push_back(peerLt);
500 orderedTiles = std::move(sequenced);
502 for (
auto logicalTile : orderedTiles) {
504 auto col = logicalTile.tryGetCol();
505 auto row = logicalTile.tryGetRow();
508 if (failed(enforceAdjacency(logicalTile, tile, bufferKind)))
510 if (failed(enforceAdjacency(logicalTile, tile, cascadeKind)))
512 if (failed(enforceAdjacency(logicalTile, tile, sharedMemKind)))
514 if (failed(validateAndUpdateChannelUsage(
515 logicalTile, tile, channelRequirements, PlacementOrigin::Pinned)))
518 recordPlacement(logicalTile, tile, ctx,
"pinned");
523 if (logicalTile.getTileType() == AIETileType::CoreTile) {
524 auto isReservedForOtherBound = [&](Operation *lto,
TileID candidate) {
525 return ctx.isReservedForOther(lto, candidate);
527 SmallVector<int> preferredCols =
528 preferredGroupColumns(logicalTile, coreGroups);
529 UnpinnedPlacementInputs inputs{
530 bufferAdjacency, bufferPred,
531 cascadeAdjacency, cascadePred,
532 sharedMemAdjacency, sharedMemPred,
533 computePeerAdjacency, needNeighborIn,
534 needNeighborOut, isReservedForOtherBound,
538 bool searchedPastBudget = col || row;
539 auto search = findUnconstrainedCoreCandidate(
543 : ArrayRef<TileID>());
544 std::optional<TileID> placement = search.placement;
545 bool sawConstraintMatch = search.sawConstraintMatch;
546 bool allConstraintMatchesFailedAdjacency =
547 search.allConstraintMatchesFailedAdjacency;
548 bool computePeerWasCause = search.computePeerWasCause;
551 bool adjacencyWasCause =
552 sawConstraintMatch && allConstraintMatchesFailedAdjacency &&
553 bufferAdjacency.hasEdges(logicalTile.getOperation());
554 bool hasCascade = cascadeAdjacency.hasEdges(logicalTile.getOperation());
556 sharedMemAdjacency.hasEdges(logicalTile.getOperation());
557 InFlightDiagnostic diag = logicalTile.emitError();
559 diag <<
"no compute tile available matching constraint ("
560 << (col ? std::to_string(*col) :
"?") <<
", "
561 << (row ? std::to_string(*row) :
"?") <<
")"
562 << (adjacencyWasCause ?
" and shared-L1 buffer adjacency" :
"")
563 << (hasCascade ?
" and cascade adjacency" :
"")
564 << (hasSharedMem ?
" and shared-memory transport" :
"")
565 << (computePeerWasCause ?
" and compute-peer DMA budget" :
"");
567 diag <<
"no available compute tiles for placement"
568 << (adjacencyWasCause
569 ?
" (shared-L1 buffer adjacency unsatisfiable)"
571 << (hasCascade ?
" (cascade adjacency unsatisfiable)" :
"")
572 << (hasSharedMem ?
" (shared-memory transport unsatisfiable)"
574 << (computePeerWasCause
575 ?
" (compute-peer DMA budget unsatisfiable)"
580 if (coresPerCol.has_value() && deviceCoresPerCol > 0 &&
581 !searchedPastBudget) {
584 <<
"cores-per-col=" << *coresPerCol <<
" leaves "
585 << placeableCores <<
" of this device's "
586 << columns * deviceCoresPerCol
587 <<
" compute tiles placeable and may be limiting placement; "
588 "consider raising it or reducing the design's core count";
591 notePinClash(diag, logicalTile, *search.pinClash);
592 if (adjacencyWasCause)
593 attachPeerNotes(diag, logicalTile, bufferAdjacency, bufferLabel);
595 attachPeerNotes(diag, logicalTile, cascadeAdjacency, cascadeLabel);
597 attachPeerNotes(diag, logicalTile, sharedMemAdjacency,
599 if (computePeerWasCause) {
600 attachPeerNotes(diag, logicalTile, computePeerAdjacency,
601 [](
bool thisIsProducer) -> StringRef {
602 return thisIsProducer ?
"compute-peer consumer"
603 :
"compute-peer producer";
606 <<
"to fix, pin this LTO to a position that is shared-L1 with "
607 "the placed compute-peers above, or pin one of those peers "
608 "to a different coordinate so this LTO's constraints become "
611 if (adjacencyWasCause || hasCascade || hasSharedMem ||
614 <<
"the sequential placer places tiles one at a time and never "
615 "moves a placed peer; if these constraints can be met "
616 "together, --placer=sa_placer, which searches placements "
617 "jointly, may place them";
621 if (failed(validateAndUpdateChannelUsage(logicalTile, *placement,
623 PlacementOrigin::Selected)))
626 recordPlacement(logicalTile, *placement, ctx,
"unconstrained");
629 if (logicalTile.getTileType() == AIETileType::ShimPLTile) {
630 return logicalTile.emitError(
631 "DMA channel-based SequentialPlacer does not support unplaced "
632 "ShimPLTiles (no DMAs).");
638 return placeNonCoreLogicalTiles(logicalTiles, flowIndex, channelRequirements);
641SequentialPlacer::CoreGroups
642SequentialPlacer::buildCoreGroups(ArrayRef<LogicalTileOp> logicalTiles,
643 const FlowMembership &flowIndex)
const {
645 SmallVector<std::pair<LogicalTileOp, llvm::MapVector<Operation *, int>>>
647 llvm::DenseMap<Operation *, int> coresOnHub;
648 for (
auto lt : logicalTiles) {
649 if (lt.getTileType() != AIETileType::CoreTile)
651 llvm::MapVector<Operation *, int> counts;
652 auto it = flowIndex.ltoFlows.find(lt.getResult());
653 if (it != flowIndex.ltoFlows.end())
654 for (
auto &peers : it->second)
655 for (Value p : peers) {
656 auto tile = dyn_cast_or_null<TileLike>(p.getDefiningOp());
657 if (tile && !tile.isCoreTile())
658 ++counts[p.getDefiningOp()];
660 for (
auto &entry : counts)
661 ++coresOnHub[entry.first];
662 coreFlows.emplace_back(lt, std::move(counts));
668 llvm::DenseMap<Operation *, unsigned> groupOfHub;
669 for (
auto &[lt, counts] : coreFlows) {
670 Operation *hub =
nullptr;
672 for (
auto &[peer, n] : counts)
673 if (!hub || n > best ||
674 (n == best && coresOnHub[peer] < coresOnHub[hub])) {
678 unsigned idx = groups.members.size();
680 auto [it, inserted] = groupOfHub.try_emplace(hub, idx);
683 groups.members[idx].push_back(lt);
684 groups.groupOf[lt.getOperation()] = idx;
688 groups.members.push_back({lt});
689 groups.groupOf[lt.getOperation()] = idx;
695SequentialPlacer::preferredGroupColumns(LogicalTileOp logicalTile,
696 const CoreGroups &groups)
const {
697 auto group = groups.groupOf.find(logicalTile.getOperation());
698 if (group == groups.groupOf.end())
700 SmallVector<std::pair<int, int>> placedCols;
702 for (
auto member : groups.members[group->second]) {
703 auto placed =
result.find(member.getOperation());
704 if (placed ==
result.end()) {
708 auto *entry = llvm::find_if(
709 placedCols, [&](
auto &e) {
return e.first == placed->second.col; });
710 if (entry == placedCols.end())
711 placedCols.push_back({placed->second.col, 1});
715 llvm::stable_sort(placedCols, [](
auto &a,
auto &b) {
716 return a.second != b.second ? a.second > b.second : a.first < b.first;
719 SmallVector<int> cols;
720 for (
auto &[col, n] : placedCols)
723 llvm::MapVector<int, int> freeCores;
726 for (
auto &[col, n] : freeCores)
727 if (n >= unplaced && !llvm::is_contained(cols, col))
732LogicalResult SequentialPlacer::placeNonCoreLogicalTiles(
733 ArrayRef<LogicalTileOp> logicalTiles,
const FlowMembership &flowIndex,
734 const llvm::DenseMap<Operation *, std::pair<int, int>>
735 &channelRequirements) {
740 SmallVector<LogicalTileOp> nonCoreOrdered;
741 for (
auto logicalTile : logicalTiles) {
742 if (
result.count(logicalTile.getOperation()))
744 AIETileType tileType = logicalTile.getTileType();
745 if (tileType == AIETileType::CoreTile ||
746 tileType == AIETileType::ShimPLTile)
748 nonCoreOrdered.push_back(logicalTile);
750 llvm::stable_sort(nonCoreOrdered, [&](LogicalTileOp a, LogicalTileOp b) {
751 auto demand = [&](LogicalTileOp lt) {
752 auto chans = channelRequirements.lookup(lt.getOperation());
753 return chans.first + chans.second;
755 return demand(a) > demand(b);
758 for (
auto logicalTile : nonCoreOrdered) {
759 if (failed(placeNonCoreTileByCentroid(logicalTile, flowIndex,
760 channelRequirements)))
766int SequentialPlacer::PlacementContext::placementPriority(Operation *op)
const {
767 int self = neighborDemand(op);
770 [&](TileLike peer,
bool ) {
771 best = std::max(best, neighborDemand(peer.getOperation()));
773 return std::max(self, best);
776void SequentialPlacer::PlacementContext::reserveNeighborSlots(
777 Operation *placedOp,
TileID at) {
778 if (neighborDemand(placedOp) <= 0)
784bool SequentialPlacer::PlacementContext::isReservedForOther(
785 Operation *lto,
TileID candidate)
const {
786 auto it = reservedFor.find(candidate);
787 if (it == reservedFor.end())
789 for (Operation *owner : it->second) {
794 [&](TileLike peer,
bool ) {
795 if (peer.getOperation() == owner)
804SequentialPlacer::UnpinnedSearchResult
805SequentialPlacer::findUnconstrainedCoreCandidate(
806 LogicalTileOp logicalTile, std::optional<int> col, std::optional<int> row,
807 const UnpinnedPlacementInputs &inputs, ArrayRef<TileID> candidates,
808 ArrayRef<TileID> pastBudget) {
809 UnpinnedSearchResult
result;
810 auto neighborDemand = [&](Operation *op) {
811 return inputs.needNeighborIn.lookup(op) + inputs.needNeighborOut.lookup(op);
821 SmallVector<TileID> orderedCandidates(candidates);
822 if (neighborDemand(logicalTile.getOperation()) > 0) {
823 DenseMap<TileID, int> neighbors;
824 for (
TileID candidate : orderedCandidates)
826 [&](
TileID) { ++neighbors[candidate]; });
827 llvm::stable_sort(orderedCandidates, [&](
TileID a,
TileID b) {
829 return a.col < b.col;
830 int na = neighbors.lookup(a);
831 int nb = neighbors.lookup(b);
834 return a.row < b.row;
836 }
else if (!inputs.preferredCols.empty()) {
839 auto rankOf = [&](
TileID t) {
840 return std::distance(inputs.preferredCols.begin(),
841 llvm::find(inputs.preferredCols, t.col));
843 llvm::stable_sort(orderedCandidates, [&](
TileID a,
TileID b) {
844 return rankOf(a) < rankOf(b);
851 llvm::append_range(orderedCandidates, pastBudget);
857 auto leavesPeerRoom = [&](
TileID candidate) {
858 llvm::DenseSet<TileID> claimed;
860 forEachPeer(logicalTile.getOperation(), inputs.bufferAdjacency,
861 [&](TileLike peer,
bool thisIsFirst) {
862 if (!room || resolvePeerPosition(peer, this->result))
866 llvm::find_if(availability.compTiles, [&](TileID t) {
867 return t != candidate && !claimed.contains(t) &&
868 (thisIsFirst ? inputs.bufferPred(candidate, t)
869 : inputs.bufferPred(t, candidate));
873 claimed.insert(*free);
878 auto fitsColumnStreams = [&](
TileID candidate) {
880 StreamDemand used = columnStreamsUsed.lookup(candidate.col);
881 auto incoming = columnIncomingFifos.find(candidate.col);
882 if (incoming != columnIncomingFifos.end())
884 demand.
southIn -= incoming->second.contains(fifo);
887 int bottomRow = candidate.row;
888 while (bottomRow > 0 &&
889 targetModel->isCoreTile(candidate.col, bottomRow - 1))
893 static_cast<int>(
targetModel->getNumSourceSwitchboxConnections(
894 candidate.col, bottomRow, WireBundle::South))) &&
897 static_cast<int>(
targetModel->getNumDestSwitchboxConnections(
898 candidate.col, bottomRow, WireBundle::South)));
906 SmallVector<TileID> sameProgramFirst(orderedCandidates);
907 if (
unsigned key =
coreKeys.lookup(logicalTile))
908 std::stable_partition(
909 sameProgramFirst.begin(), sameProgramFirst.end(), [&](
TileID at) {
910 return llvm::any_of(neighbourCores, [&](const auto &neighbour) {
911 return neighbour.lookup(at) == key;
914 for (
int pass = 0; pass < 3; ++pass) {
915 for (
const TileID &candidate :
916 pass == 0 ? sameProgramFirst : orderedCandidates) {
917 if (col && candidate.col != *col)
919 if (row && candidate.row != *row)
922 (inputs.isReservedForOther(logicalTile.getOperation(), candidate) ||
923 !leavesPeerRoom(candidate)))
925 if (pass == 0 && (!fitsColumnStreams(candidate) ||
926 raisesStreamCuts(logicalTile, candidate)))
928 result.sawConstraintMatch =
true;
929 if (!satisfiesAdjacency(logicalTile, candidate, inputs.bufferAdjacency,
932 result.allConstraintMatchesFailedAdjacency =
false;
933 if (!satisfiesAdjacency(logicalTile, candidate, inputs.cascadeAdjacency,
936 if (!satisfiesAdjacency(logicalTile, candidate, inputs.sharedMemAdjacency,
937 inputs.sharedMemPred))
939 if (!satisfiesComputePeer(
940 logicalTile, candidate, inputs.computePeerAdjacency,
941 inputs.needNeighborIn, inputs.needNeighborOut)) {
942 result.computePeerWasCause =
true;
945 if (!pinsAt.heldAt(candidate,
946 pinnedEnds.lookup(logicalTile.getOperation()))) {
948 result.pinClash = candidate;
951 result.placement = candidate;
958void SequentialPlacer::notePinClash(InFlightDiagnostic &diag,
959 LogicalTileOp logicalTile,
TileID at) {
961 pinnedEnds.lookup(logicalTile.getOperation())) {
962 std::optional<PinnedChannels::End> other = pinsAt.clashWith(at, end);
963 std::optional<DMAChannelAnalysis::ChannelClaim> claim =
964 other ? std::nullopt : pinsAt.claimWith(at, end);
965 if (!other && !claim)
967 auto ¬e = diag.attachNote();
968 note <<
"on (" << at.col <<
", " << at.row
969 <<
"), the first compute tile it fits otherwise, @"
970 << end.fifo.getSymName() <<
" pins " << (end.sends ?
"MM2S" :
"S2MM")
971 <<
" channel " << end.channel;
973 std::optional<std::string> why = pinnedRule.whyApart(end, *other);
974 note <<
", which @" << other->fifo.getSymName() <<
" pins there too, but "
975 << (why ? *why :
"they clash");
977 note <<
", which another op holds";
978 diag.attachNote(claim->owner->getLoc()) <<
"held here";
984LogicalResult SequentialPlacer::validateAndUpdateChannelUsage(
985 LogicalTileOp logicalTile,
TileID tile,
986 const llvm::DenseMap<Operation *, std::pair<int, int>> &channelRequirements,
987 PlacementOrigin origin) {
988 auto [inChannels, outChannels] =
989 channelRequirements.lookup(logicalTile.getOperation());
990 SmallVector<PinnedChannels::End> pins =
991 pinnedEnds.lookup(logicalTile.getOperation());
992 std::optional<std::pair<int, int>> held = pinsAt.heldAt(tile, pins);
996 return std::make_pair(a.sends, a.channel) <
997 std::make_pair(b.sends, b.channel);
999 [[maybe_unused]]
bool reported =
false;
1001 if (std::optional<PinnedChannels::End> other =
1002 pinsAt.clashWith(tile, end)) {
1003 std::optional<std::string> why = pinnedRule.whyApart(end, *other);
1004 end.fifo.emitError()
1005 <<
"pins " << (end.sends ?
"MM2S" :
"S2MM") <<
" channel "
1006 << end.channel <<
" of tile (" << tile.col <<
", " << tile.row
1007 <<
"), which @" << other->fifo.getSymName()
1008 <<
" pins there too, but " << (why ? *why :
"they clash");
1010 }
else if (std::optional<DMAChannelAnalysis::ChannelClaim> claim =
1011 pinsAt.claimWith(tile, end)) {
1012 auto diag = end.fifo.emitError()
1013 <<
"pins " << (end.sends ?
"MM2S" :
"S2MM") <<
" channel "
1014 << end.channel <<
" of tile (" << tile.col <<
", "
1015 << tile.row <<
"), which another op holds";
1016 diag.attachNote(claim->owner->getLoc()) <<
"held here";
1021 "heldAt reports only a clash clashWith or claimWith finds");
1024 inChannels -= held->first;
1025 outChannels -= held->second;
1027 if (!hasAvailableChannels(tile, inChannels, outChannels, logicalTile) &&
1028 !fitsSharingShim(tile, logicalTile, {inChannels, outChannels})) {
1031 int availIn = maxIn -
availability.inputChannelsUsed[tile];
1032 int availOut = maxOut -
availability.outputChannelsUsed[tile] -
1033 overlayWith(tile, logicalTile).channels;
1035 auto diag = logicalTile.emitError();
1036 diag <<
"tile (" << tile.col <<
", " << tile.row <<
") requires "
1037 << inChannels <<
" input/" << outChannels
1038 <<
" output DMA channels, but only " << availIn <<
" input/"
1039 << availOut <<
" output available";
1040 if (
OverlayFit overlay = overlayWith(tile, logicalTile);
1043 <<
"the control overlay "
1044 << (overlay.fits ?
"takes one of its output channels"
1045 :
"has no output channel here it may take or "
1047 <<
"; aie-generate-column-control-overlay shares one only with "
1048 "ends never in flight with its control packets";
1049 if (origin == PlacementOrigin::Selected)
1050 diag.attachNote() <<
"placer selected this tile; to fix, pin this LTO "
1051 "to a tile with more spare DMA capacity, or reduce "
1052 "the LTO's DMA fanin (e.g. via memtile staging)";
1057 recordStreamAndBdUsage(logicalTile, tile);
1059 updateChannelUsage(tile, DmaDir::In, inChannels);
1060 if (outChannels > 0)
1061 updateChannelUsage(tile, DmaDir::Out, outChannels);
1062 recordShimEnds(tile, logicalTile);
1067llvm::DenseMap<Operation *, std::pair<int, int>>
1068SequentialPlacer::buildChannelRequirements(
1069 SmallVector<ObjectFifoCreateOp> &objectFifos,
1070 SmallVector<ObjectFifoLinkOp> &objectFifoLinks,
1071 const DenseMap<Operation *, unsigned> &rank) {
1072 llvm::DenseMap<Operation *, std::pair<int, int>> channelRequirements;
1075 llvm::StringMap<ObjectFifoCreateOp> fifoNameToOp;
1076 for (
auto ofOp : objectFifos) {
1077 fifoNameToOp[ofOp.getSymName()] = ofOp;
1086 llvm::DenseMap<Operation *, Operation *> linkTileOf;
1087 llvm::StringMap<SmallVector<Operation *>> linkTilesOfSource;
1088 llvm::DenseSet<llvm::StringRef> linkedAsDest;
1089 for (
auto linkOp : objectFifoLinks) {
1090 Operation *linkTileOp =
nullptr;
1091 for (
auto dstFifoAttr : linkOp.getFifoOuts())
1092 if (
auto sym = dyn_cast<FlatSymbolRefAttr>(dstFifoAttr)) {
1093 linkedAsDest.insert(sym.getValue());
1094 auto it = fifoNameToOp.find(sym.getValue());
1095 if (!linkTileOp && it != fifoNameToOp.end())
1096 linkTileOp = it->second.getProducerTile().getDefiningOp();
1098 linkTileOf[linkOp.getOperation()] = linkTileOp;
1101 for (
auto srcFifoAttr : linkOp.getFifoIns())
1102 if (
auto sym = dyn_cast<FlatSymbolRefAttr>(srcFifoAttr))
1103 linkTilesOfSource[sym.getValue()].push_back(linkTileOp);
1111 llvm::DenseSet<unsigned> counted;
1112 auto drawsChannel = [&](ObjectFifoCreateOp fifo,
1113 std::optional<unsigned> consumer, Operation *tile) {
1114 std::optional<PinnedChannels::End> end =
1118 pinnedEnds[tile].push_back(*end);
1119 return counted.insert(pinnedRule.share(*end, rank)).second;
1123 auto dmaEnd = [](ObjectFifoCreateOp fifo, std::optional<unsigned> consumer,
1125 auto like = dyn_cast_or_null<TileLike>(tile);
1126 return like && like.isShimTile() ? !fifo.getPlio()
1127 : fifo.plannedDmaEnd(consumer).has_value();
1134 for (
auto ofOp : objectFifos) {
1135 SmallVector<Operation *> linkConsumers =
1136 linkTilesOfSource.lookup(ofOp.getSymName());
1137 bool skipProducerSide = linkedAsDest.count(ofOp.getSymName());
1139 Value producerTile = ofOp.getProducerTile();
1140 auto *producerOp = producerTile.getDefiningOp();
1141 auto producerLogicalTile = dyn_cast_or_null<LogicalTileOp>(producerOp);
1144 bool producerNeedsDMA =
false;
1146 for (
auto [consumerIndex, consumerTile] :
1147 llvm::enumerate(ofOp.getConsumerTiles())) {
1148 auto *consumerOp = consumerTile.getDefiningOp();
1149 auto consumerLogicalTile = dyn_cast_or_null<LogicalTileOp>(consumerOp);
1155 auto producerLike = dyn_cast_or_null<TileLike>(producerOp);
1156 auto consumerLike = dyn_cast_or_null<TileLike>(consumerOp);
1157 if (producerLike && consumerLike &&
1158 (producerLogicalTile || consumerLogicalTile) &&
1159 producerLike.getTileType() == AIETileType::CoreTile &&
1160 consumerLike.getTileType() == AIETileType::CoreTile &&
1165 if (consumerOp && !llvm::is_contained(linkConsumers, consumerOp) &&
1166 dmaEnd(ofOp, consumerIndex, consumerOp) &&
1167 drawsChannel(ofOp, consumerIndex, consumerOp))
1168 channelRequirements[consumerOp].first++;
1170 producerNeedsDMA =
true;
1176 if (producerNeedsDMA && producerOp && !skipProducerSide &&
1177 dmaEnd(ofOp, std::nullopt, producerOp) &&
1178 drawsChannel(ofOp, std::nullopt, producerOp))
1179 channelRequirements[producerOp].second++;
1184 for (
auto linkOp : objectFifoLinks) {
1186 Operation *linkTileOp = linkTileOf.lookup(linkOp.getOperation());
1193 int numInputChannels = 0, numOutputChannels = 0;
1194 for (
auto [sources, input] : {std::make_pair(linkOp.getFifoIns(),
true),
1195 std::make_pair(linkOp.getFifoOuts(),
false)})
1196 for (Attribute attr : sources) {
1197 auto sym = dyn_cast<FlatSymbolRefAttr>(attr);
1198 ObjectFifoCreateOp fifo =
1199 sym ? fifoNameToOp.lookup(sym.getValue()) : ObjectFifoCreateOp();
1201 ++(input ? numInputChannels : numOutputChannels);
1205 numOutputChannels += drawsChannel(fifo, std::nullopt, linkTileOp);
1208 for (
unsigned index = 0, e = fifo.getConsumerTiles().size(); index < e;
1210 if (fifo.getConsumerLink(index) == linkOp)
1211 numInputChannels += drawsChannel(fifo, index, linkTileOp);
1213 if (linkOp.isMerge())
1214 numInputChannels = 1;
1215 if (linkOp.isDispatch())
1216 numOutputChannels = 1;
1218 channelRequirements[linkTileOp].first += numInputChannels;
1219 channelRequirements[linkTileOp].second += numOutputChannels;
1222 return channelRequirements;
1225void SequentialPlacer::countTurns(
1226 DeviceOp device, ArrayRef<ObjectFifoCreateOp> objectFifos,
1227 llvm::DenseMap<Operation *, std::pair<int, int>> &requirements) {
1228 for (CoreOp core : device.getOps<CoreOp>()) {
1229 auto tile = dyn_cast_or_null<LogicalTileOp>(core.getTile().getDefiningOp());
1230 if (!tile || !requirements.count(tile))
1232 auto &[in, out] = requirements[tile];
1233 for (
bool coreDrains : {
true,
false}) {
1234 int &need = coreDrains ? in : out;
1235 auto [inBudget, outBudget] =
1237 int budget = coreDrains ? inBudget : outBudget;
1241 llvm::MapVector<std::pair<Operation *, std::optional<TileID>>,
1242 SmallVector<ObjectFifoCreateOp>>
1244 for (ObjectFifoCreateOp fifo : objectFifos) {
1245 if (!fifo.canTakeTurns())
1247 auto consumers = fifo.getConsumerTiles();
1248 Value mine = coreDrains ? consumers[0] : fifo.getProducerTile();
1249 Value other = coreDrains ? fifo.getProducerTile() : consumers[0];
1250 auto peer = dyn_cast_or_null<TileLike>(other.getDefiningOp());
1251 if (mine != tile.getResult() || !peer || !peer.isMemTile())
1253 std::optional<int> col = peer.tryGetCol(), row = peer.tryGetRow();
1255 byTile[{
nullptr,
TileID{*col, *row}}].push_back(fifo);
1257 byTile[{peer, std::nullopt}].push_back(fifo);
1259 for (
auto &[peer, fifos] : byTile) {
1260 if (fifos.size() < 2 || need <= budget)
1262 SmallVector<StringAttr> names;
1263 SmallVector<int64_t> depths;
1264 for (ObjectFifoCreateOp fifo : fifos) {
1265 names.push_back(fifo.getSymNameAttr());
1266 depths.push_back(fifo.dmaDepth(coreDrains ? std::optional<unsigned>(0)
1271 if (succeeded(turns.
read(core, names, coreDrains, reason)) &&
1273 need -=
static_cast<int>(fifos.size()) - 1;
1280static BufferOp traceToBuffer(Value val) {
1281 for (Operation *op = val.getDefiningOp(); op;) {
1282 if (
auto buf = dyn_cast<BufferOp>(op))
1284 if (
auto view = dyn_cast<ViewLikeOpInterface>(op)) {
1285 val = view.getViewSource();
1286 op = val.getDefiningOp();
1294static std::optional<TileID>
1297 return std::nullopt;
1298 auto it = placed.find(peer.getOperation());
1299 if (it != placed.end())
1301 auto col = peer.tryGetCol();
1302 auto row = peer.tryGetRow();
1304 return TileID{*col, *row};
1305 return std::nullopt;
1308Placer::Adjacency SequentialPlacer::buildBufferAdjacency(
1309 ArrayRef<LogicalTileOp> logicalTiles,
1310 ArrayRef<ObjectFifoAllocateOp>
allocates) {
1314 llvm::DenseSet<std::pair<Operation *, Operation *>> seen;
1315 auto addOnce = [&](TileLike user, TileLike owner) {
1316 if (seen.insert({user.getOperation(), owner.getOperation()}).second)
1317 adjacency.addEdge(user, owner);
1323 dyn_cast_or_null<TileLike>(alloc.getDelegateTile().getDefiningOp());
1324 ObjectFifoCreateOp fifo = alloc.getObjectFifo();
1325 if (!delegate || !fifo || delegate.getTileType() != AIETileType::CoreTile)
1327 SmallVector<Value> ends{fifo.getProducerTile()};
1328 llvm::append_range(ends, fifo.getConsumerTiles());
1329 for (Value end : ends) {
1330 auto tile = dyn_cast_or_null<TileLike>(end.getDefiningOp());
1331 if (tile && tile.getTileType() == AIETileType::CoreTile &&
1332 tile.getOperation() != delegate.getOperation())
1333 addOnce(tile, delegate);
1336 for (
auto consumer : logicalTiles) {
1337 if (consumer.getTileType() != AIETileType::CoreTile)
1339 CoreOp core =
nullptr;
1340 for (Operation *user : consumer.getResult().getUsers())
1341 if (
auto c = dyn_cast<CoreOp>(user)) {
1348 core.getBody().walk([&](Operation *op) {
1349 for (Value operand : op->getOperands()) {
1350 BufferOp buf = traceToBuffer(operand);
1353 auto owner = dyn_cast_or_null<TileLike>(buf.getTile().getDefiningOp());
1354 if (owner && owner.getOperation() != consumer.getOperation())
1355 addOnce(TileLike(consumer), owner);
1365 for (
auto cf : cascadeFlows) {
1366 TileLike src = cf.getSourceTileLike();
1367 TileLike dst = cf.getDestTileLike();
1378 for (
auto ofOp : objectFifos) {
1380 dyn_cast_or_null<TileLike>(ofOp.getProducerTile().getDefiningOp());
1381 if (!producer || producer.getTileType() != AIETileType::CoreTile)
1384 if (ofOp.dmaReason())
1386 for (Value consumerVal : ofOp.getConsumerTiles()) {
1387 auto consumer = dyn_cast_or_null<TileLike>(consumerVal.getDefiningOp());
1388 if (!consumer || consumer.getTileType() != AIETileType::CoreTile)
1393 if (producer.getOperation() == consumer.getOperation() ||
1394 (!isa<LogicalTileOp>(producer.getOperation()) &&
1395 !isa<LogicalTileOp>(consumer.getOperation())))
1397 adjacency.
addEdge(producer, consumer);
1406 for (
auto ofOp : objectFifos)
1407 if (ofOp.forcesSharedMemory() && ofOp.getConsumerTiles().size() == 1)
1409 ofOp.getConsumerTiles()[0]);
1413bool SequentialPlacer::satisfiesAdjacency(
1414 LogicalTileOp logicalTile,
TileID candidate,
const Adjacency &adjacency,
1415 llvm::function_ref<
bool(
TileID firstPos,
TileID secondPos)> pred)
const {
1417 forEachPeer(logicalTile.getOperation(), adjacency,
1418 [&](TileLike peer,
bool thisIsFirst) {
1421 auto peerPos = resolvePeerPosition(peer, result);
1424 TileID firstPos = thisIsFirst ? candidate : *peerPos;
1425 TileID secondPos = thisIsFirst ? *peerPos : candidate;
1426 if (!pred(firstPos, secondPos))
1432LogicalResult SequentialPlacer::enforceAdjacency(LogicalTileOp logicalTile,
1434 const AdjacencyKind &kind) {
1435 if (satisfiesAdjacency(logicalTile, tile, kind.adjacency, kind.pred))
1437 auto diag = logicalTile.emitError()
1438 <<
"tile (" << tile.col <<
", " << tile.row <<
") violates "
1439 << kind.name <<
" adjacency";
1440 attachPeerNotes(diag, logicalTile, kind.adjacency, kind.peerLabel);
1441 diag.attachNote() << kind.constraintHint;
1445void SequentialPlacer::recordPlacement(LogicalTileOp logicalTile,
TileID tile,
1446 PlacementContext &ctx,
1447 StringRef debugLabel) {
1448 result[logicalTile] = tile;
1449 addPlacedStreams(logicalTile);
1450 LLVM_DEBUG(llvm::dbgs() <<
DEBUG_TYPE <<
": placed " << debugLabel <<
" LTO "
1451 << logicalTile.getLoc() <<
" at (" << tile.col <<
", "
1452 << tile.row <<
")\n");
1453 if (logicalTile.getTileType() == AIETileType::CoreTile) {
1454 recordColumnStreamUsage(logicalTile, tile.col);
1456 ctx.reserveNeighborSlots(logicalTile.getOperation(), tile);
1460 logicalTile.getOperation(), ctx.computePeerAdjacency,
1461 [&](TileLike peer,
bool thisIsFirst) {
1462 auto placed = dyn_cast<TileOp>(peer.getOperation());
1464 !isSharedComputeMemory(*targetModel, placed.getTileID(), tile))
1465 updateChannelUsage(placed.getTileID(),
1466 thisIsFirst ? DmaDir::In : DmaDir::Out, 1);
1472SequentialPlacer::totalComputePeers(Operation *op,
const Adjacency &adjacency) {
1473 int in = 0, out = 0;
1476 forEachPeer(op, adjacency, [&](TileLike ,
bool thisIsFirst) {
1485bool SequentialPlacer::satisfiesComputePeer(
1486 LogicalTileOp logicalTile,
TileID candidate,
1488 const llvm::DenseMap<Operation *, int> &needNeighborIn,
1489 const llvm::DenseMap<Operation *, int> &needNeighborOut)
const {
1495 if (!computePeerAdjacency.hasEdges(logicalTile.getOperation()))
1500 int selfNonNeighborIn = 0, selfNonNeighborOut = 0;
1501 int selfNeighborIn = 0, selfNeighborOut = 0;
1502 forEachPeer(logicalTile.getOperation(), computePeerAdjacency,
1503 [&](TileLike peer,
bool thisIsFirst) {
1504 auto peerPos = resolvePeerPosition(peer, result);
1508 isSharedComputeMemory(*targetModel, candidate, *peerPos);
1509 bool thisIsConsumer = !thisIsFirst;
1517 ++selfNonNeighborIn;
1519 ++selfNonNeighborOut;
1522 auto [selfTotalIn, selfTotalOut] =
1523 totalComputePeers(logicalTile.getOperation(), computePeerAdjacency);
1524 int selfNeedIn = needNeighborIn.lookup(logicalTile.getOperation());
1525 int selfNeedOut = needNeighborOut.lookup(logicalTile.getOperation());
1526 int selfSlackIn = selfTotalIn - selfNeedIn;
1527 int selfSlackOut = selfTotalOut - selfNeedOut;
1528 if (selfNonNeighborIn > selfSlackIn)
1530 if (selfNonNeighborOut > selfSlackOut)
1540 if (selfNeedIn > 0 || selfNeedOut > 0) {
1541 int freeNeighborSlots = 0;
1544 ++freeNeighborSlots;
1546 int remainingInNeed = std::max(0, selfNeedIn - selfNeighborIn);
1547 int remainingOutNeed = std::max(0, selfNeedOut - selfNeighborOut);
1548 if (remainingInNeed + remainingOutNeed > freeNeighborSlots)
1556 bool symmetricOk =
true;
1558 logicalTile.getOperation(), computePeerAdjacency,
1559 [&](TileLike peer,
bool thisIsFirst) {
1562 auto peerLTO = dyn_cast_or_null<LogicalTileOp>(peer.getOperation());
1563 auto peerPos = resolvePeerPosition(peer, result);
1569 auto [maxIn, maxOut] = getDMACapacity(*targetModel, *peerPos);
1570 if (!isSharedComputeMemory(*targetModel, *peerPos, candidate) &&
1572 ? availability.inputChannelsUsed.lookup(*peerPos) >= maxIn
1573 : availability.outputChannelsUsed.lookup(*peerPos) >=
1575 symmetricOk = false;
1581 bool logicalIsPeerOut = !thisIsFirst;
1582 int peerNeedDir = logicalIsPeerOut
1583 ? needNeighborOut.lookup(peerLTO.getOperation())
1584 : needNeighborIn.lookup(peerLTO.getOperation());
1585 auto [peerTotalIn, peerTotalOut] =
1586 totalComputePeers(peerLTO.getOperation(), computePeerAdjacency);
1587 int peerTotalDir = logicalIsPeerOut ? peerTotalOut : peerTotalIn;
1588 int peerSlackDir = peerTotalDir - peerNeedDir;
1591 int peerNonNeighborDir = 0;
1593 peerLTO.getOperation(), computePeerAdjacency,
1594 [&](TileLike peerPeer,
bool peerLTOIsFirst) {
1599 bool peerIsConsumerHere = !peerLTOIsFirst;
1600 if (logicalIsPeerOut == peerIsConsumerHere)
1602 if (peerPeer.getOperation() == logicalTile.getOperation()) {
1605 if (!isSharedComputeMemory(*targetModel, *peerPos, candidate))
1606 ++peerNonNeighborDir;
1609 auto pp = resolvePeerPosition(peerPeer,
result);
1613 ++peerNonNeighborDir;
1615 if (peerNonNeighborDir > peerSlackDir)
1616 symmetricOk =
false;
1621void SequentialPlacer::attachPeerNotes(
1622 InFlightDiagnostic &diag, LogicalTileOp logicalTile,
1624 llvm::function_ref<StringRef(
bool thisIsFirst)> labelPeer)
const {
1625 int unplacedCount = 0;
1626 forEachPeer(logicalTile.getOperation(), adjacency,
1627 [&](TileLike peer,
bool thisIsFirst) {
1628 auto peerPos = resolvePeerPosition(peer, result);
1633 diag.attachNote(peer.getLoc())
1634 << labelPeer(thisIsFirst) <<
" peer placed at ("
1635 << peerPos->col <<
", " << peerPos->row <<
")";
1637 if (unplacedCount > 0)
1638 diag.attachNote() << unplacedCount
1639 <<
" additional peer(s) on this LTO are not yet placed "
1640 "(placed after this LTO; their positions may "
1641 "subsequently constrain or unblock this placement)";
1647 for (
auto ofOp : objectFifos)
1648 for (Value consumer : ofOp.getConsumerTiles())
1654 DeviceOp device, ArrayRef<ObjectFifoCreateOp> objectFifos,
1655 const llvm::DenseMap<Operation *, unsigned> &rank,
1656 const llvm::DenseMap<Operation *, Operation *> &routeKeys) {
1657 llvm::DenseSet<std::pair<Operation *, Value>> registered;
1658 for (
auto reg : device.getOps<ObjectFifoRegisterExternalBuffersOp>())
1659 registered.insert({reg.getObjectFifo(), reg.getTile()});
1661 DenseMap<StringAttr, unsigned> endRank;
1662 auto shareable = [&](ObjectFifoCreateOp fifo, Value tile,
1663 ObjectFifoEndPortAttr port) -> Operation * {
1664 auto lt = dyn_cast_or_null<TileLike>(tile.getDefiningOp());
1665 if (!lt || lt.getTileType() != AIETileType::ShimNOCTile || fifo.getPlio() ||
1666 (port && port.channelIndex()) || registered.contains({fifo, tile}))
1668 return lt.getOperation();
1670 for (
auto fifo : objectFifos) {
1671 endRank[fifo.getSymNameAttr()] = rank.lookup(fifo);
1673 shareable(fifo, fifo.getProducerTile(), fifo.getProdPortAttr()))
1674 ends[lt][1].ends.push_back(fifo.getSymNameAttr());
1675 for (
auto [i, consumer] : llvm::enumerate(fifo.getConsumerTiles()))
1676 if (Operation *lt = shareable(fifo, consumer, fifo.getConsumerPort(i)))
1677 ends[lt][0].ends.push_back(fifo.getSymNameAttr());
1679 for (
auto endpoint : device.getOps<RouteEndpointOp>()) {
1680 auto tile = dyn_cast<TileLike>(endpoint.getTile().getDefiningOp());
1681 if (!tile || !tile.isShimTile() || endpoint.getBundle() != WireBundle::DMA)
1684 ends[routeKeys.lookup_or(tile.getOperation(), tile.getOperation())]
1685 [endpoint.getRouteDirection() == DMAChannelDir::MM2S ? 1 : 0];
1686 if (std::optional<int> channel = endpoint.getChannelIndex())
1687 side.
pinned.push_back(*channel);
1688 else if (isa<LogicalTileOp>(tile.getOperation()))
1689 side.
ends.push_back(endpoint.getSymNameAttr());
1690 endRank[endpoint.getSymNameAttr()] = rank.lookup(endpoint);
1692 for (
auto alloc : device.getOps<ShimDMAAllocationOp>()) {
1693 MLIRContext *context = alloc->getContext();
1694 auto tile = dyn_cast_or_null<TileLike>(alloc.getTile().getDefiningOp());
1695 auto allowed = AIEDialect::ShareableWithAttrHelper(context).getAttr(alloc);
1696 if (!tile || !tile.isShimTile() || !allowed ||
1697 AIEDialect::IsCtrlPktOverlayAttrHelper(context).isAttrPresent(alloc))
1699 SmallVector<StringAttr> listed;
1700 for (Attribute attr : allowed)
1701 if (
auto symbol = dyn_cast<FlatSymbolRefAttr>(attr))
1702 listed.push_back(symbol.getAttr());
1703 ends[routeKeys.lookup_or(tile.getOperation(), tile.getOperation())]
1704 [alloc.getChannelDir() == DMAChannelDir::MM2S ? 1 : 0]
1705 .shared.emplace_back(alloc.getChannelIndex(), std::move(listed));
1709 auto entries = ends.takeVector();
1710 llvm::stable_sort(entries, [&](
const auto &a,
const auto &b) {
1711 return rank.lookup(a.first) < rank.lookup(b.first);
1713 for (
auto &[tile, sides] : entries) {
1715 llvm::stable_sort(side.ends, [&](StringAttr a, StringAttr b) {
1716 return endRank.lookup(a) < endRank.lookup(b);
1718 llvm::stable_sort(side.shared, [](
const auto &a,
const auto &b) {
1719 return a.first < b.first;
1722 ends.insert({tile, std::move(sides)});
1728 ArrayRef<const ShimSide *> sides,
1729 ArrayRef<StringAttr> extra,
1730 ArrayRef<int> pinnedHere) {
1731 SmallVector<StringAttr> ends;
1732 SmallVector<int> pinned(pinnedHere);
1733 for (
const ShimSide *side : sides) {
1734 llvm::append_range(ends, side->ends);
1735 llvm::append_range(pinned, side->pinned);
1737 llvm::append_range(ends, extra);
1738 SmallVector<ShimTransferSpans::SharedChannel> shared;
1740 for (
auto &[channel, listed] : side->shared)
1741 shared.emplace_back(listed, llvm::is_contained(pinned, channel));
1743 return static_cast<int>(ends.size() - plan.
groups.size());
1747 DeviceOp device, ArrayRef<ObjectFifoCreateOp> objectFifos,
1748 ArrayRef<DMAChannelAnalysis::ChannelClaim> claims,
1749 const DenseMap<Operation *, unsigned> &rank,
1750 const DenseMap<Operation *, Operation *> &routeKeys) {
1753 claimsOf[claim.tile.getDefiningOp()].push_back(claim);
1761 const ShimSide &side = entry.second[0];
1762 return !side.
ends.empty() || !side.
shared.empty();
1768 [&](StringAttr symbol) {
1777 for (
int col = 0; col <
targetModel->columns(); ++col)
1779 llvm::any_of(llvm::seq(0,
targetModel->rows()), [&](
int row) {
1780 return targetModel->isShimNOCTile(col, row);
1782 for (
unsigned seq = 0, e =
shimSpans->sequences(); seq < e; ++seq)
1783 for (
int dir : {0, 1}) {
1785 SmallVector<StringAttr> ends;
1786 SmallVector<std::optional<int64_t>> bytes;
1788 for (StringAttr end : sides[dir].ends)
1790 group.
tiles.push_back(tile);
1791 ends.push_back(end);
1792 bytes.push_back(
shimSpans->bytes(seq, end));
1794 if (group.
tiles.size() < 2)
1796 bool dynamic = llvm::is_contained(bytes, std::nullopt);
1798 for (std::optional<int64_t> b : bytes)
1799 total += b.value_or(0);
1800 for (std::optional<int64_t> b : bytes)
1802 dynamic || total <= 0
1804 : std::max<int64_t>(1, (b.value_or(0) * 65536 + total / 2) /
1806 for (StringAttr a : ends) {
1807 llvm::BitVector &together = group.
together.emplace_back(ends.size());
1808 for (
auto [j, b] : llvm::enumerate(ends))
1812 for (Operation *tile : group.
tiles) {
1813 SmallVector<unsigned> &groups =
ddrGroupsOf[tile];
1814 if (groups.empty() || groups.back() !=
ddrGroups.size())
1832 function_ref<std::optional<int>(Operation *)> columnOf,
1834 SmallVector<std::optional<int>> cols =
1835 llvm::map_to_vector(group.
tiles, columnOf);
1836 int64_t load = 0, sameColumn = 0;
1838 for (
auto [i, col] : llvm::enumerate(cols)) {
1844 for (
size_t j = i + 1; j < cols.size(); ++j)
1845 if (cols[j] == col && group.
together[i].test(j))
1851 return weight * (spreadOver * sameColumn - load * load) / (load * load);
1854std::optional<Placer::PinnedChannels::End>
1856 std::optional<unsigned> consumer) {
1857 ObjectFifoEndPortAttr port =
1858 consumer ? fifo.getConsumerPort(*consumer) : fifo.getProdPortAttr();
1859 std::optional<int> pin = port ? port.channelIndex() : std::nullopt;
1860 if (!pin || port.isCore() || *pin < 0)
1861 return std::nullopt;
1863 consumer ? fifo.getConsumerTiles()[*consumer] : fifo.getProducerTile();
1864 auto offCore = [](Value end) {
1865 return cast<TileLike>(end.getDefiningOp()).getTileType() !=
1866 AIETileType::CoreTile;
1868 bool movesByDma = fifo.dmaReason() || offCore(fifo.getProducerTile()) ||
1869 llvm::any_of(fifo.getConsumerTiles(), offCore);
1870 return End{fifo, consumer, tile.getDefiningOp(), !consumer, *pin, movesByDma};
1876 for (ObjectFifoCreateOp fifo : {a.
fifo, b.
fifo}) {
1877 auto tile = cast<TileLike>(fifo.getProducerTile().getDefiningOp());
1878 if (tile.isShimTile())
1880 if (!tile.isCoreTile() || targetModel->getDmaTaskQueueDepth() == 0)
1881 return std::string(
"only a shim, or a core that pushes its tasks, "
1882 "sends two fifos on one channel");
1886 return std::string(
"a shared channel carries both at once, which only "
1887 "packet-switched routes tell apart");
1889 for (ObjectFifoCreateOp fifo : {a.
fifo, b.
fifo})
1890 if (std::optional<StringRef> why =
1891 cast<TileLike>(fifo.getProducerTile().getDefiningOp())
1894 : fifo.pushQueueRefusal())
1895 return "@" + fifo.getSymName().str() +
"'s " + why->str();
1897 for (
End end : {a, b})
1898 if (std::optional<StringRef> why =
1899 ObjectFifoCreateOp::sharedReceiveRefusal(
1900 cast<TileLike>(end.tile).isShimTile(),
1901 end.fifo.getOutOfOrder()))
1904 std::optional<uint16_t>
id =
1905 a.
fifo.packetHeader() ? a.
fifo.packetHeader().getPktId() : std::nullopt;
1906 std::optional<uint16_t> otherId =
1907 b.
fifo.packetHeader() ? b.
fifo.packetHeader().getPktId() : std::nullopt;
1908 if (
id && otherId && *
id == *otherId)
1909 return "both pin packet id " + std::to_string(*
id);
1910 return std::nullopt;
1915 const DenseMap<Operation *, unsigned> &rank) {
1918 auto &[before, number] = taken
1919 .try_emplace(key, SmallVector<End, 2>{},
1920 static_cast<unsigned>(taken.size()))
1922 for (
End other : before) {
1925 auto [first, second] = rank.lookup(other.fifo) < rank.lookup(end.
fifo)
1926 ? std::pair(other, end)
1927 : std::pair(end, other);
1928 if (std::optional<std::string> why =
whyApart(first, second)) {
1929 first.fifo.emitError() <<
"shares " << (first.sends ?
"MM2S" :
"S2MM")
1930 <<
" channel " << first.channel <<
" with @"
1931 << second.fifo.getSymName() <<
", but " << *why;
1935 before.push_back(end);
1941 auto alloc = dyn_cast_or_null<ShimDMAAllocationOp>(claim.
owner);
1945 AIEDialect::ShareableWithAttrHelper(alloc->getContext()).getAttr(alloc);
1946 if (!allowed || llvm::none_of(allowed, [&](Attribute attr) {
1947 auto symbol = dyn_cast<FlatSymbolRefAttr>(attr);
1948 return symbol && symbol.getAttr() == end.
fifo.getSymNameAttr();
1952 : end.
fifo.getOutOfOrder();
1958 std::make_tuple(at.col, at.row,
claim.channel,
1959 static_cast<int>(
claim.dir == DMAChannelDir::MM2S));
1960 auto &claims = claimed[key];
1962 claims.push_back(
claim);
1969 assert(found != claims.end() &&
"removing a claim never placed");
1970 claims.erase(found);
1975std::optional<DMAChannelAnalysis::ChannelClaim>
1978 auto it = claimed.find(std::make_tuple(at.col, at.row, end.
channel,
1979 static_cast<int>(end.
sends)));
1980 if (it == claimed.end())
1981 return std::nullopt;
1983 if (!rule->sharesClaim(end,
claim))
1985 return std::nullopt;
1991 std::make_tuple(at.col, at.row, end.
channel,
static_cast<int>(end.
sends));
1993 auto &ends = placed[key];
1994 ends.push_back(end);
1995 return ends.size() == 1 ? 1 : 0;
1997 auto it = placed.find(key);
1998 assert(it != placed.end() &&
"removing an end never placed");
2000 return e.fifo == end.fifo && e.consumer == end.consumer;
2002 assert(found != it->second.end() &&
"removing an end never placed");
2003 it->second.erase(found);
2004 if (!it->second.empty())
2011 auto claimsClash = [](ArrayRef<DMAChannelAnalysis::ChannelClaim> claims) {
2012 return llvm::any_of(claims,
2014 return claim.tile != claims.front().tile;
2018 for (
auto it = placed.lower_bound(
2019 std::make_tuple(at.col, at.row, std::numeric_limits<int>::min(), 0));
2020 it != placed.end() && std::get<0>(it->first) == at.col &&
2021 std::get<1>(it->first) == at.row;
2023 const auto &ends = it->second;
2025 for (
size_t i = 0; i < ends.size() && !clash; ++i)
2026 for (
size_t j = i + 1; j < ends.size() && !clash; ++j)
2027 clash = (ends[i].tile != ends[j].tile || !ends[i].movesByDma ||
2028 !ends[j].movesByDma) &&
2029 rule->whyApart(ends[i], ends[j]).has_value();
2030 if (
auto held = claimed.find(it->first); held != claimed.end())
2031 clash = clash || claimsClash(held->second) ||
2033 return llvm::any_of(
2036 return !rule->sharesClaim(end, claim);
2041 for (
auto it = claimed.lower_bound(
2042 std::make_tuple(at.col, at.row, std::numeric_limits<int>::min(), 0));
2043 it != claimed.end() && std::get<0>(it->first) == at.col &&
2044 std::get<1>(it->first) == at.row;
2046 count += !placed.count(it->first) && claimsClash(it->second);
2050std::optional<Placer::PinnedChannels::End>
2053 auto it = placed.find(std::make_tuple(at.col, at.row, end.
channel,
2054 static_cast<int>(end.
sends)));
2055 if (it == placed.end())
2056 return std::nullopt;
2058 if (other.
tile != end.
tile && rule->whyApart(end, other))
2060 return std::nullopt;
2065 llvm::SmallVector<int> channels;
2066 for (
auto it = placed.lower_bound(
2067 std::make_tuple(at.col, at.row, std::numeric_limits<int>::min(), 0));
2068 it != placed.end() && std::get<0>(it->first) == at.col &&
2069 std::get<1>(it->first) == at.row;
2071 if (std::get<3>(it->first) ==
static_cast<int>(sends))
2072 channels.push_back(std::get<2>(it->first));
2076llvm::DenseMap<int, llvm::SmallVector<Placer::PinnedChannels::End, 2>>
2078 llvm::DenseMap<int, llvm::SmallVector<PinnedChannels::End, 2>> sending;
2079 for (
auto it = placed.lower_bound(
2080 std::make_tuple(at.col, at.row, std::numeric_limits<int>::min(), 0));
2081 it != placed.end() && std::get<0>(it->first) == at.col &&
2082 std::get<1>(it->first) == at.row;
2084 if (std::get<3>(it->first))
2085 llvm::append_range(sending[std::get<2>(it->first)], it->second);
2089std::optional<std::pair<Operation *, std::pair<int, int>>>
2093 return std::nullopt;
2094 for (Operation *other : others) {
2098 for (std::pair<int, int> named : mine->second)
2099 if (llvm::is_contained(theirs->second, named))
2100 return std::make_pair(other, named);
2102 return std::nullopt;
2106 Operation *tile,
TileID at,
2107 std::pair<Operation *, std::pair<int, int>> clash)
const {
2108 auto [other, named] = clash;
2109 auto [output, channel] = named;
2110 StringRef dir = output ?
"MM2S" :
"S2MM";
2111 InFlightDiagnostic diag =
2113 <<
"names " << dir <<
" channel " << channel <<
", as a tile op on ("
2114 << at.col <<
", " << at.row <<
") does, and each "
2115 << stringifyAIETileType(
targetModel->getTileType(at.col, at.row))
2116 <<
" with room for it holds a tile op naming one of its channels; tile "
2117 "ops whose DMA programs or flows name one channel cannot share a "
2118 "physical tile, so give one of them another channel";
2119 diag.attachNote(other->getLoc())
2120 <<
"the tile op naming " << dir <<
" channel " << channel;
2126 auto module = device->getParentOfType<ModuleOp>();
2129 for (DeviceOp other : module.getOps<DeviceOp>()) {
2130 if (other == device || other.getDevice() != device.getDevice() ||
2134 for (
auto fifo : other.getOps<ObjectFifoCreateOp>()) {
2135 std::optional<PinnedChannels::End> end =
2139 auto tile = dyn_cast_or_null<TileOp>(end->tile);
2140 if (!tile || !tile.isShimNOCorPLTile())
2143 uses.
packetEnds[{tile, end->channel}].push_back(fifo.getSymNameAttr());
2145 uses.
circuits[tile].insert(end->channel);
2147 for (
auto &[tile, channels] : uses.
circuits)
2148 if (isa<TileOp>(tile))
2149 overlayUses.circuits[tile].insert(channels.begin(), channels.end());
2151 if (isa<TileOp>(key.first))
2152 llvm::append_range(
overlayUses.packetEnds[key], ends);
2154 if (isa<TileOp>(key.first))
2160 llvm::SetVector<Operation *> tiles;
2161 for (
auto &[tile, channels] :
overlayUses.circuits)
2164 tiles.insert(key.first);
2165 for (
auto &[key, flows] :
overlayUses.packetFlows)
2166 tiles.insert(key.first);
2167 return tiles.takeVector();
2171 ArrayRef<PinnedChannels::End> extra,
2172 ArrayRef<Operation *> tilesHere,
2176 llvm::DenseSet<int> circuits;
2177 llvm::DenseMap<int, SmallVector<StringAttr>> packetEnds;
2178 llvm::DenseMap<int, unsigned> packetFlows;
2179 for (Operation *tile : tilesHere)
2182 circuits.insert(it->second.begin(), it->second.end());
2184 if (llvm::is_contained(tilesHere, key.first))
2185 llvm::append_range(packetEnds[key.second], ends);
2186 for (
auto &[key, flows] :
overlayUses.packetFlows)
2187 if (llvm::is_contained(tilesHere, key.first))
2188 packetFlows[key.second] += flows;
2192 onChannel[end.channel].push_back(end);
2194 at.col, at.row, WireBundle::DMA)
2196 std::optional<int> chosen;
2197 size_t fewest = std::numeric_limits<size_t>::max();
2198 for (
int channel = 0; channel < count; ++channel) {
2199 auto ends = onChannel.lookup(channel);
2200 if (circuits.contains(channel) ||
2202 return !isPacketSwitched(end.fifo.packetHeader(), packetSwitched);
2205 size_t demand = ends.size() + packetEnds.lookup(channel).size() +
2206 packetFlows.lookup(channel);
2207 if (demand < fewest) {
2213 return {
false, 1,
false};
2214 SmallVector<StringAttr> sharers = packetEnds.lookup(*chosen);
2216 sharers.push_back(end.fifo.getSymNameAttr());
2217 if (sharers.empty() && !packetFlows.lookup(*chosen))
2218 return {
true, 1,
true};
2219 bool apart = llvm::all_of(sharers, [&](StringAttr end) {
2222 return {apart, 0,
false};
2225std::optional<std::pair<int, int>>
2227 ArrayRef<PinnedChannels::End> ends)
const {
2228 std::pair<int, int> held{0, 0};
2229 llvm::SmallDenseSet<std::pair<int, int>, 4> counted;
2232 return std::nullopt;
2233 auto key = std::make_tuple(at.col, at.row, end.channel,
2234 static_cast<int>(end.sends));
2235 if ((placed.count(key) || claimed.count(key)) &&
2236 counted.insert({end.channel, end.sends}).second)
2237 ++(end.sends ? held.second : held.first);
2242DenseMap<StringAttr, SmallVector<ShimTransferSpans::Gate>>
2249 llvm::raw_string_ostream os(text);
2250 device->print(os, OpPrintingFlags().printGenericOpForm());
2251 MLIRContext context(device.getContext()->getDialectRegistry(),
2252 MLIRContext::Threading::DISABLED);
2253 ScopedDiagnosticHandler quiet(&context,
2254 [](Diagnostic &) {
return success(); });
2255 OwningOpRef<ModuleOp> copy = parseSourceString<ModuleOp>(
2256 text, ParserConfig(&context,
false));
2259 auto devices = llvm::to_vector(copy->getOps<DeviceOp>());
2260 if (devices.empty())
2262 DeviceOp clone = devices.front();
2267 DenseSet<TileID> usedCores;
2268 for (
auto tile : clone.getOps<TileOp>())
2269 if (tile.isCoreTile())
2270 usedCores.insert({tile.getCol(), tile.getRow()});
2271 DenseMap<AIETileType, unsigned> turn;
2272 OpBuilder builder(clone.getBody(), clone.getBody()->begin());
2275 SmallVector<LogicalTileOp> logicalTiles =
2277 llvm::stable_sort(logicalTiles, [](LogicalTileOp a, LogicalTileOp b) {
2278 return !a.tryGetCol() + !a.tryGetRow() < !b.tryGetCol() + !b.tryGetRow();
2280 for (LogicalTileOp lt : logicalTiles) {
2281 SmallVector<TileID> fits;
2282 for (
int col = 0; col < target.
columns(); ++col)
2283 for (
int row = 0; row < target.
rows(); ++row)
2284 if (target.
getTileType(col, row) == lt.getTileType() &&
2286 (lt.getTileType() != AIETileType::CoreTile ||
2287 !usedCores.contains({col, row})))
2288 fits.push_back({col, row});
2291 TileID at = lt.getTileType() == AIETileType::CoreTile
2293 : fits[turn[lt.getTileType()]++ % fits.size()];
2294 if (lt.getTileType() == AIETileType::CoreTile)
2295 usedCores.insert(at);
2296 TileOp tile = TileOp::getOrCreate(builder, clone, at.col, at.row);
2297 lt.getResult().replaceAllUsesWith(tile.getResult());
2300 for (
auto fifo : clone.getOps<ObjectFifoCreateOp>()) {
2301 if (fifo.forcesDMA() ||
2302 llvm::all_of(fifo.getConsumerTiles(), [&](Value consumer) {
2303 return consumer == fifo.getProducerTile();
2306 ObjectFifoTransportAttr transport = fifo.getTransportAttr();
2307 fifo.setTransportAttr(ObjectFifoTransportAttr::get(
2308 &context, ObjectFifoTransportMode::DMA,
2309 transport ? transport.getPacket() : PacketInfoAttr(),
2310 transport && transport.getOutOfOrder()));
2312 for (
auto allocate : llvm::to_vector(clone.getOps<ObjectFifoAllocateOp>()))
2315 PassManager pm(&context, DeviceOp::getOperationName());
2318 if (failed(pm.run(clone)))
2320 DenseMap<StringAttr, SmallVector<ShimTransferSpans::Gate>> gates;
2321 MLIRContext *ctx = device.getContext();
2322 for (
auto &[fifo, proven] :
2325 ConsumedByAttr proof = gate.proof;
2326 FlatSymbolRefAttr device = proof.getDevice();
2327 gates[StringAttr::get(ctx, fifo.getValue())].push_back(
2328 {StringAttr::get(ctx, gate.input.getValue()),
2329 ConsumedByAttr::get(
2330 ctx, FlatSymbolRefAttr::get(ctx, proof.getOutput().getValue()),
2331 proof.getInputBytes(), proof.getOutputBytes(),
2332 proof.getGranuleBytes(),
2333 device ? FlatSymbolRefAttr::get(ctx, device.getValue())
2334 : FlatSymbolRefAttr())});
2340 ArrayRef<PacketFlowOp> pktFlows) {
2342 for (
auto flow : flows)
2345 for (
auto pktFlow : pktFlows) {
2346 SmallVector<Value> srcs, dsts;
2347 pktFlow.walk([&](Operation *op) {
2348 if (
auto src = dyn_cast<PacketSourceOp>(op))
2349 srcs.push_back(src.getTile());
2350 else if (
auto dst = dyn_cast<PacketDestOp>(op))
2351 dsts.push_back(dst.getTile());
2371 ArrayRef<FlowOp> flows, ArrayRef<PacketFlowOp> pktFlows,
2372 ArrayRef<RouteOp> routes, ArrayRef<DMAChannelAnalysis::ChannelClaim> claims,
2373 llvm::DenseMap<Operation *, SmallVector<std::pair<int, int>>> *named,
2374 llvm::DenseMap<Operation *, Operation *> *keys) {
2375 llvm::MapVector<Operation *, std::pair<int, int>> demand;
2376 llvm::DenseSet<std::tuple<Operation *, int>> seenSrc, seenDst;
2377 llvm::DenseMap<std::pair<int, int>, Operation *> byCoordinate;
2379 auto incIfDMA = [&](Operation *tileOp, WireBundle bundle,
2380 std::optional<int> channel,
bool isOutput) {
2381 auto tile = dyn_cast_or_null<TileLike>(tileOp);
2382 if (!tile || bundle != WireBundle::DMA)
2384 Operation *key = tileOp;
2385 if (
auto col = tile.tryGetCol(), row = tile.tryGetRow(); col && row)
2386 key = byCoordinate.try_emplace({*col, *row}, tileOp).first->second;
2388 (*keys)[tileOp] = key;
2390 auto &seen = isOutput ? seenSrc : seenDst;
2391 if (channel && !seen.insert({tileOp, *channel}).second)
2393 if (channel && named)
2394 (*named)[tileOp].push_back({isOutput, *channel});
2396 demand[tileOp].second++;
2398 demand[tileOp].first++;
2401 for (
auto flow : flows) {
2402 incIfDMA(flow.getSource().getDefiningOp(), flow.getSourceBundle(),
2403 flow.getSourceChannel(),
true);
2404 incIfDMA(flow.getDest().getDefiningOp(), flow.getDestBundle(),
2405 flow.getDestChannel(),
false);
2408 for (
auto pktFlow : pktFlows) {
2409 pktFlow.walk([&](Operation *op) {
2410 if (
auto src = dyn_cast<PacketSourceOp>(op)) {
2411 incIfDMA(src.getTile().getDefiningOp(), src.getBundle(),
2412 src.getChannel(),
true);
2413 }
else if (
auto dst = dyn_cast<PacketDestOp>(op)) {
2414 incIfDMA(dst.getTile().getDefiningOp(), dst.getBundle(),
2415 dst.getChannel(),
false);
2421 incIfDMA(claim.tile.getDefiningOp(), WireBundle::DMA, claim.channel,
2422 claim.dir == DMAChannelDir::MM2S);
2426 llvm::DenseSet<Operation *> countedEndpoints;
2427 for (
auto route : routes) {
2428 auto count = [&](StringRef name,
bool isOutput) {
2429 auto endpoint = SymbolTable::lookupNearestSymbolFrom<RouteEndpoint>(
2430 route, StringAttr::get(route.getContext(), name));
2431 if (endpoint && countedEndpoints.insert(endpoint).second)
2432 incIfDMA(endpoint.getTile().getDefiningOp(), endpoint.getRouteBundle(),
2433 endpoint.getRouteChannel(), isOutput);
2435 for (StringRef source : route.getSourceNames())
2436 count(source,
true);
2437 for (StringRef dest : route.getDestinationNames())
2443SequentialPlacer::FlowMembership SequentialPlacer::buildFlowMembership(
2444 ArrayRef<FlowOp> flows, ArrayRef<PacketFlowOp> pktFlows,
2445 ArrayRef<RouteOp> routes, ArrayRef<ObjectFifoCreateOp> objectFifos) {
2450 auto isLto = [](Value v) {
2451 return v && mlir::isa_and_nonnull<LogicalTileOp>(v.getDefiningOp());
2453 auto addEntry = [&](Value lto, ArrayRef<Value> peers) {
2454 if (!isLto(lto) || peers.empty())
2456 idx.ltoFlows[lto].push_back(SmallVector<Value>(peers.begin(), peers.end()));
2459 for (
auto flow : flows) {
2460 Value s = flow.getSource(), d = flow.getDest();
2464 for (
auto pf : pktFlows) {
2465 SmallVector<Value> srcs, dsts;
2466 pf.walk([&](Operation *op) {
2467 if (
auto src = dyn_cast<PacketSourceOp>(op))
2468 srcs.push_back(src.getTile());
2469 else if (
auto dst = dyn_cast<PacketDestOp>(op))
2470 dsts.push_back(dst.getTile());
2472 for (Value s : srcs)
2474 for (Value d : dsts)
2477 for (
auto route : routes) {
2478 auto tileOf = [&](StringRef name) -> Value {
2479 auto endpoint = SymbolTable::lookupNearestSymbolFrom<RouteEndpoint>(
2480 route, StringAttr::get(route.getContext(), name));
2481 return endpoint ? endpoint.getTile() : Value();
2483 SmallVector<Value> srcs, dsts;
2484 for (StringRef source : route.getSourceNames())
2485 if (Value tile = tileOf(source))
2486 srcs.push_back(tile);
2487 for (StringRef dest : route.getDestinationNames())
2488 if (Value tile = tileOf(dest))
2489 dsts.push_back(tile);
2490 for (Value s : srcs)
2492 for (Value d : dsts)
2495 for (
auto of : objectFifos) {
2496 Value prod = of.getProducerTile();
2497 auto cons = of.getConsumerTiles();
2498 SmallVector<Value> consVec(cons.begin(), cons.end());
2499 addEntry(prod, consVec);
2500 for (Value c : consVec)
2501 addEntry(c, {prod});
2507SequentialPlacer::computeCentroidColumn(LogicalTileOp logicalTile,
2508 const FlowMembership &flowIndex) {
2519 Value ltoVal = logicalTile.getResult();
2520 auto ltoIt = flowIndex.ltoFlows.find(ltoVal);
2521 if (ltoIt == flowIndex.ltoFlows.end())
2522 return std::nullopt;
2527 auto resolvePeerCol = [&](Value v) -> std::optional<int> {
2528 Operation *defOp = v.getDefiningOp();
2530 return std::nullopt;
2532 if (
auto tileOp = dyn_cast<TileOp>(defOp))
2533 return tileOp.getCol();
2534 auto lto = dyn_cast<LogicalTileOp>(defOp);
2536 return std::nullopt;
2537 if (
auto c = lto.tryGetCol())
2539 auto it =
result.find(defOp);
2541 return it->second.col;
2542 return std::nullopt;
2548 auto resolveLtoCoreCols = [&](Value v) {
2549 SmallVector<int> out;
2550 auto it = flowIndex.ltoFlows.find(v);
2551 if (it == flowIndex.ltoFlows.end())
2553 for (
auto &peerList : it->second)
2554 for (Value p : peerList)
2555 if (
auto col = resolvePeerCol(p))
2556 out.push_back(*col);
2560 SmallVector<SmallVector<int>> perFlowDests;
2561 for (
auto &peers : ltoIt->second) {
2562 SmallVector<int> dests;
2563 for (Value p : peers) {
2564 if (
auto col = resolvePeerCol(p)) {
2565 dests.push_back(*col);
2570 for (
int c : resolveLtoCoreCols(p))
2574 perFlowDests.push_back(std::move(dests));
2577 if (perFlowDests.empty())
2578 return std::nullopt;
2580 double meanDestCol = 0.0;
2582 for (
auto &dests : perFlowDests)
2583 for (
int d : dests) {
2587 meanDestCol /= destCount;
2591 int bestCost = std::numeric_limits<int>::max();
2592 double bestTiebreak = std::numeric_limits<double>::infinity();
2593 for (
int S = 0; S < numCols; ++S) {
2595 for (
auto &dests : perFlowDests) {
2596 if (dests.size() == 1) {
2597 cost += std::abs(S - dests[0]);
2599 int lo = *llvm::min_element(dests);
2600 int hi = *llvm::max_element(dests);
2607 double tiebreak = std::abs(S - meanDestCol);
2608 if (cost < bestCost || (cost == bestCost && tiebreak < bestTiebreak)) {
2610 bestTiebreak = tiebreak;
2617LogicalResult SequentialPlacer::placeNonCoreTileByCentroid(
2618 LogicalTileOp logicalTile,
const FlowMembership &flowIndex,
2619 const llvm::DenseMap<Operation *, std::pair<int, int>>
2620 &channelRequirements) {
2621 std::optional<int> centroidCol =
2622 computeCentroidColumn(logicalTile, flowIndex);
2623 auto colConstraint = logicalTile.tryGetCol();
2628 std::optional<int> targetCol = colConstraint ? colConstraint : centroidCol;
2629 if (!targetCol && !spreadUnanchoredTiles)
2632 auto [numInputChannels, numOutputChannels] =
2633 channelRequirements.lookup(logicalTile.getOperation());
2635 auto maybeTile = findTileWithCapacity(targetCol,
availability.nonCompTiles,
2636 numInputChannels, numOutputChannels,
2637 logicalTile.getTileType(), logicalTile,
2640 maybeTile = findTileWithCapacity(targetCol,
availability.nonCompTiles,
2641 numInputChannels, numOutputChannels,
2642 logicalTile.getTileType(), logicalTile,
2645 if (!maybeTile && mergeLogicalTiles &&
2646 logicalTile.getTileType() == AIETileType::ShimNOCTile) {
2647 std::optional<std::pair<int, int>> bestKey;
2648 for (
int col = 0, numCols =
targetModel->columns(); col < numCols; ++col) {
2650 std::optional<std::pair<int, int>> held =
2651 pinsAt.heldAt(tile, pinnedEnds.lookup(logicalTile));
2652 if ((colConstraint && col != *colConstraint) || !held ||
2653 namedClash(logicalTile, overlayTilesAt.lookup(tile)) ||
2654 !fitsSharingShim(tile, logicalTile,
2655 {numInputChannels - held->first,
2656 numOutputChannels - held->second}))
2658 std::pair<int, int> key{targetCol ? std::abs(col - *targetCol) : 0, col};
2659 if (!bestKey || key < *bestKey) {
2666 if (std::optional<TileID> named = findTileWithCapacity(
2667 targetCol,
availability.nonCompTiles, numInputChannels,
2668 numOutputChannels, logicalTile.getTileType(), logicalTile,
2670 if (
auto clash =
namedClash(logicalTile, overlayTilesAt.lookup(*named)))
2672 AIETileType requestedType = logicalTile.getTileType();
2673 StringRef tileTypeName = stringifyAIETileType(requestedType);
2674 auto diag = logicalTile.emitError();
2675 CapacityDiagnosis diagnosis = diagnoseCapacityExhaustion(
2676 requestedType, numInputChannels, numOutputChannels, logicalTile);
2677 auto noteClash = [&]() {
2678 if (!diagnosis.clash)
2680 auto &[at, end, other] = *diagnosis.clash;
2681 std::string why = pinnedRule.whyApart(end, other).value_or(
"they clash");
2682 diag.attachNote() <<
"@" << end.fifo.getSymName() <<
" pins "
2683 << (end.sends ?
"MM2S" :
"S2MM") <<
" channel "
2684 << end.channel <<
", which @" << other.fifo.getSymName()
2685 <<
" pins on (" << at.col <<
", " << at.row
2686 <<
") too, but " << why <<
"; " << diagnosis.clashTiles
2687 <<
" " << tileTypeName <<
"(s) hold such a pin";
2689 if (!diagnosis.capacityExistsSomewhere && diagnosis.clash) {
2690 diag <<
"no " << tileTypeName
2691 <<
" with DMA channels to spare can hold this tile's pinned ends "
2692 "beside the ends pinned there";
2694 }
else if (!diagnosis.capacityExistsSomewhere) {
2695 diag <<
"no " << tileTypeName <<
" on the device has " << numInputChannels
2696 <<
" input/" << numOutputChannels
2697 <<
" output DMA channel(s) free: all " << diagnosis.tilesOfType
2698 <<
" " << tileTypeName <<
"(s) are at " << diagnosis.inUsed <<
"/"
2699 << diagnosis.inMax <<
" input, " << diagnosis.outUsed <<
"/"
2700 << diagnosis.outMax <<
" output channels used";
2701 diag.attachNote() <<
"this is the device's total " << tileTypeName
2702 <<
" DMA budget, not a placement choice -- no column "
2703 "has spare capacity to pin to";
2704 if (diagnosis.overlayOut)
2706 << diagnosis.overlayOut
2707 <<
" of the output channels used are the control overlay's, "
2708 "which aie-generate-column-control-overlay shares only with "
2709 "ends never in flight with its control packets";
2710 if (diagnosis.overlayUnfit)
2711 diag.attachNote() <<
"on " << diagnosis.overlayUnfit <<
" "
2713 <<
"(s), with this tile's pinned ends, the control "
2714 "overlay has no output channel it may take or "
2716 int shortIn = diagnosis.closestShortIn;
2717 int shortOut = diagnosis.closestShortOut;
2718 if (shortIn == 0 && shortOut == 0)
2720 auto &remedy = diag.attachNote();
2721 remedy <<
"the closest " << tileTypeName <<
" is ";
2722 if (shortIn > 0 && shortOut > 0)
2723 remedy <<
"short " << shortIn <<
" input/" << shortOut
2724 <<
" output channel(s); ";
2725 else if (shortIn > 0)
2726 remedy <<
"short " << shortIn <<
" input channel(s); ";
2727 else if (shortOut > 0)
2728 remedy <<
"short " << shortOut <<
" output channel(s); ";
2729 remedy <<
"fan traffic through a MemTile via aie.objectfifo.link, or "
2730 "reduce the number of DMA-attached ObjectFIFOs feeding this "
2733 diag <<
"no " << tileTypeName <<
" has sufficient DMA capacity for "
2734 << numInputChannels <<
" input/" << numOutputChannels
2735 <<
" output channels ";
2737 diag <<
"at column " << *colConstraint;
2738 else if (centroidCol)
2739 diag <<
"near centroid column " << *centroidCol;
2741 diag <<
"on any column";
2743 if (!mergeLogicalTiles)
2744 diag.attachNote() <<
"every " << tileTypeName
2745 <<
" with spare DMA capacity already hosts a "
2746 "different logical tile (merge-logical-tiles is "
2747 "off); enable merging, or pin logical tiles "
2748 "one-per-column if fewer of them than physical "
2749 << tileTypeName <<
"s remain unclaimed";
2754 result[logicalTile] = *maybeTile;
2755 addPlacedStreams(logicalTile);
2757 auto showCol = [](std::optional<int> c) {
2758 return c ? std::to_string(*c) : std::string(
"none");
2760 llvm::dbgs() <<
DEBUG_TYPE <<
": placed non-core LTO "
2761 << logicalTile.getLoc() <<
" at (" << maybeTile->col <<
", "
2762 << maybeTile->row <<
") (centroid col=" << showCol(centroidCol)
2763 <<
", target col=" << showCol(targetCol) <<
")\n";
2765 if (!mergeLogicalTiles)
2766 assignedNonCoreTiles.insert(*maybeTile);
2767 std::optional<std::pair<int, int>> held =
2768 pinsAt.heldAt(*maybeTile, pinnedEnds.lookup(logicalTile));
2770 return logicalTile.emitError()
2771 <<
"pins a channel that (" << maybeTile->col <<
", "
2772 << maybeTile->row <<
") cannot hold beside its other pinned ends";
2773 auto [heldIn, heldOut] = *held;
2774 recordStreamAndBdUsage(logicalTile, *maybeTile);
2775 if (numInputChannels > heldIn)
2776 updateChannelUsage(*maybeTile, DmaDir::In, numInputChannels - heldIn);
2777 if (numOutputChannels > heldOut)
2778 updateChannelUsage(*maybeTile, DmaDir::Out, numOutputChannels - heldOut);
2779 recordShimEnds(*maybeTile, logicalTile);
2783bool SequentialPlacer::fitsSharingShim(
TileID tile, Operation *logicalTile,
2784 std::pair<int, int> required) {
2785 if (
targetModel->getTileType(tile.col, tile.row) !=
2786 AIETileType::ShimNOCTile ||
2789 const ShimTransferSpans &spans = *
shimSpans;
2791 OverlayFit overlay = overlayWith(tile, logicalTile);
2795 availability.outputChannelsUsed[tile] + overlay.channels};
2796 int need[2] = {required.first, required.second};
2797 int max[2] = {maxIn, maxOut};
2798 SmallVector<Operation *> tilesHere(shimTilesAt.lookup(tile));
2800 tilesHere.push_back(logicalTile);
2801 for (
int dir : {0, 1}) {
2802 if (used[dir] + need[dir] <= max[dir])
2804 SmallVector<const ShimSide *> sides;
2805 for (Operation *op : tilesHere)
2807 SmallVector<StringAttr> extra;
2808 if (dir == 1 && overlay.own)
2810 SmallVector<int> pinnedHere = pinsAt.channelsAt(tile, dir == 1);
2812 if (end.sends == (dir == 1))
2813 pinnedHere.push_back(end.channel);
2814 if (used[dir] + need[dir] -
2822void SequentialPlacer::recordShimEnds(
TileID tile, Operation *logicalTile) {
2824 shimTilesAt[tile].push_back(logicalTile);
2827std::optional<TileID> SequentialPlacer::findTileWithCapacity(
2828 std::optional<int> targetCol, llvm::ArrayRef<TileID> tiles,
2829 int requiredInputChannels,
int requiredOutputChannels,
2830 AIETileType requestedType, Operation *logicalTile,
bool withinBudgets,
2844 std::optional<TileID> best;
2845 std::tuple<int, int64_t, int, int, int> bestKey;
2846 SmallVector<PinnedChannels::End> pins = pinnedEnds.lookup(logicalTile);
2848 for (
auto &tile : tiles) {
2849 if (
targetModel->getTileType(tile.col, tile.row) != requestedType)
2851 std::optional<std::pair<int, int>> held = pinsAt.heldAt(tile, pins);
2852 if (!held || !hasAvailableChannels(
2853 tile, requiredInputChannels - held->first,
2854 requiredOutputChannels - held->second, logicalTile))
2859 if (!mergeLogicalTiles && assignedNonCoreTiles.contains(tile))
2861 if (withinBudgets && (!fitsStreamAndBdBudgets(logicalTile, tile) ||
2862 raisesStreamCuts(logicalTile, tile)))
2865 namedClash(logicalTile, overlayTilesAt.lookup(tile)).has_value())
2867 int dist = targetCol ? std::abs(tile.col - *targetCol) : 0;
2868 if (requestedType == AIETileType::MemTile &&
2869 !cast<LogicalTileOp>(logicalTile).tryGetCol())
2870 dist += broadcastFanoutUsed.lookup(tile);
2873 (requiredInputChannels == 0 && requiredOutputChannels == 0)) {
2878 if (requiredInputChannels > 0)
2880 if (requiredOutputChannels > 0)
2887 [&](Operation *op) -> std::optional<int> {
2888 if (op == logicalTile)
2890 if (
auto placed = dyn_cast<TileOp>(op))
2891 return placed.getCol();
2893 return at ? std::optional(at->col) : std::nullopt;
2896 std::tuple<int, int64_t, int, int, int> key{dist, ddr, load, tile.col,
2898 if (!best || key < bestKey) {
2907SequentialPlacer::CapacityDiagnosis
2908SequentialPlacer::diagnoseCapacityExhaustion(AIETileType requestedType,
2909 int requiredInputChannels,
2910 int requiredOutputChannels,
2911 Operation *joining) {
2916 CapacityDiagnosis diagnosis;
2917 for (
int col = 0, numCols =
targetModel->columns(); col < numCols; ++col) {
2918 for (
int row = 0, numRows =
targetModel->rows(); row < numRows; ++row) {
2919 if (
targetModel->getTileType(col, row) != requestedType)
2922 ++diagnosis.tilesOfType;
2924 diagnosis.inMax += maxIn;
2925 diagnosis.outMax += maxOut;
2926 int usedIn =
availability.inputChannelsUsed.lookup(tile);
2927 OverlayFit overlay = overlayWith(tile, joining);
2928 diagnosis.overlayOut += overlay.channels;
2929 diagnosis.overlayUnfit += !overlay.fits;
2931 availability.outputChannelsUsed.lookup(tile) + overlay.channels;
2932 diagnosis.inUsed += usedIn;
2933 diagnosis.outUsed += usedOut;
2934 int shortIn = std::max(0, requiredInputChannels - (maxIn - usedIn));
2935 int shortOut = std::max(0, requiredOutputChannels - (maxOut - usedOut));
2936 if (diagnosis.tilesOfType == 1 ||
2937 shortIn + shortOut <
2938 diagnosis.closestShortIn + diagnosis.closestShortOut) {
2939 diagnosis.closestShortIn = shortIn;
2940 diagnosis.closestShortOut = shortOut;
2942 SmallVector<PinnedChannels::End> pins = pinnedEnds.lookup(joining);
2943 std::optional<std::pair<int, int>> held = pinsAt.heldAt(tile, pins);
2945 ++diagnosis.clashTiles;
2947 if (std::optional<PinnedChannels::End> other =
2948 pinsAt.clashWith(tile, end);
2949 other && !diagnosis.clash)
2950 diagnosis.clash = std::make_tuple(tile, end, *other);
2953 if (hasAvailableChannels(tile, requiredInputChannels - held->first,
2954 requiredOutputChannels - held->second, joining))
2955 diagnosis.capacityExistsSomewhere =
true;
2961void SequentialPlacer::updateChannelUsage(
TileID tile, DmaDir direction,
2963 if (direction == DmaDir::Out)
2968 if (!hasAvailableChannels(tile, 0, 0)) {
2969 AIETileType type =
targetModel->getTileType(tile.col, tile.row);
2974bool SequentialPlacer::hasAvailableChannels(
TileID tile,
int inputChannels,
2976 Operation *joining) {
2978 OverlayFit overlay = overlayWith(tile, joining);
2981 int currentOut =
availability.outputChannelsUsed[tile] + overlay.channels;
2983 return overlay.fits && (currentIn + inputChannels <= maxIn) &&
2984 (currentOut + outputChannels <= maxOut);
2987Placer::OverlayFit SequentialPlacer::overlayWith(
TileID tile,
2988 Operation *joining) {
2991 SmallVector<Operation *> tilesHere(overlayTilesAt.lookup(tile));
2992 SmallVector<PinnedChannels::End> pins;
2994 tilesHere.push_back(joining);
2995 pins = pinnedEnds.lookup(joining);
2997 return overlayAt(tile, pinsAt, pins, tilesHere,
3001void SequentialPlacer::recordColumnStreamUsage(Operation *tile,
int col) {
3002 auto &incoming = columnIncomingFifos[col];
3004 incoming.insert(fifo);
3005 auto &used = columnStreamsUsed[col];
3007 used.southIn = incoming.size();
3016 auto rank = [](Operation *op) -> std::optional<int> {
3017 auto tile = dyn_cast_or_null<TileLike>(op);
3019 return std::nullopt;
3020 if (tile.isShimTile())
3022 return tile.isMemTile() ? 1 : 2;
3024 for (
auto of : objectFifos) {
3025 Operation *producer = of.getProducerTile().getDefiningOp();
3026 std::optional<int> producerRank = rank(producer);
3029 if (*producerRank == 1)
3031 std::max(0,
static_cast<int>(of.getConsumerTiles().size()) - 1);
3032 bool north =
false, south =
false;
3033 for (Value consumerTile : of.getConsumerTiles()) {
3034 Operation *consumer = consumerTile.getDefiningOp();
3035 std::optional<int> consumerRank = rank(consumer);
3036 if (!consumerRank || *consumerRank == *producerRank)
3038 if (*consumerRank > *producerRank) {
3041 if (*consumerRank == 2)
3056 : columns(target.columns()) {
3057 int rows = target.
rows();
3058 size_t cuts = 2 * std::max(columns - 1, 0) + 2 * std::max(rows - 1, 0);
3059 capacity.assign(cuts, 0);
3060 circuits.assign(cuts, 0);
3061 packets.assign(cuts, 0);
3063 auto wires = [&](
TileID a,
TileID b, WireBundle out, WireBundle in) {
3065 capacity[indexOf(rowCut, below, up)] +=
3069 for (
int col = 0; col < columns; ++col)
3070 for (
int row = 0; row < rows; ++row) {
3072 if (col + 1 < columns) {
3073 TileID east{col + 1, row};
3074 wires(at, east, WireBundle::East, WireBundle::West);
3075 wires(east, at, WireBundle::West, WireBundle::East);
3077 if (row + 1 < rows) {
3078 TileID north{col, row + 1};
3079 wires(at, north, WireBundle::North, WireBundle::South);
3080 wires(north, at, WireBundle::South, WireBundle::North);
3085unsigned StreamCuts::indexOf(
bool rows,
int below,
bool up)
const {
3086 return (rows ? 2 * (columns - 1) : 0) + 2 * below + up;
3092 SmallVectorImpl<int> &streams = packet ? packets : circuits;
3093 auto cross = [&](
bool rows,
int from,
int to,
bool up) {
3094 for (
int below = from; below < to; ++below)
3095 streams[indexOf(rows, below, up)] += sign;
3097 auto [minCol, maxCol] =
3098 std::minmax_element(dsts.begin(), dsts.end(),
3100 auto [minRow, maxRow] =
3101 std::minmax_element(dsts.begin(), dsts.end(),
3103 cross(
false, src.col, maxCol->col,
true);
3104 cross(
false, minCol->col, src.col,
false);
3105 cross(
true, src.row, maxRow->row,
true);
3106 cross(
true, minRow->row, src.row,
false);
3111 for (
auto [cap, circuit, packet] : llvm::zip(capacity, circuits, packets))
3112 missing += std::max(0, circuit + (packet > 0) - cap);
3118 for (
auto [cap, circuit, packet] : llvm::zip(capacity, circuits, packets)) {
3119 int64_t past = circuit + (packet > 0) -
3120 static_cast<int64_t
>(std::floor(fraction * cap));
3122 total += past * past;
3130 llvm::StringMap<Operation *> delegates;
3132 delegates[alloc.getObjFifoName()] = alloc.getDelegateTile().getDefiningOp();
3133 for (ObjectFifoCreateOp fifo : collected.
objectFifos) {
3135 net.
src = fifo.getProducerTile().getDefiningOp();
3136 for (Value consumer : fifo.getConsumerTiles())
3137 net.
dsts.push_back(consumer.getDefiningOp());
3140 net.
delegate = delegates.lookup(fifo.getSymName());
3141 if (std::optional<ObjectFifoLinkOp> link = fifo.getLink())
3142 if (std::optional<Value> tile = link->getOptionalSharedTile())
3143 net.
link = tile->getDefiningOp();
3145 for (FlowOp flow : collected.
flows)
3146 streamNets.push_back({flow.getSource().getDefiningOp(),
3147 {flow.getDest().getDefiningOp()},
3149 for (PacketFlowOp flow : collected.
pktFlows) {
3150 SmallVector<Operation *, 2> sources, dests;
3151 for (
auto source : flow.getOps<PacketSourceOp>())
3152 sources.push_back(source.getTile().getDefiningOp());
3153 for (
auto dest : flow.getOps<PacketDestOp>())
3154 dests.push_back(dest.getTile().getDefiningOp());
3155 for (Operation *source : sources)
3158 for (RouteOp route : collected.
routes) {
3159 auto tileOf = [&](StringRef name) -> Operation * {
3160 auto endpoint = SymbolTable::lookupNearestSymbolFrom<RouteEndpoint>(
3161 device, StringAttr::get(device.getContext(), name));
3162 return endpoint ? endpoint.getTile().getDefiningOp() :
nullptr;
3164 SmallVector<Operation *, 2> dests;
3165 for (StringRef dest : route.getDestinationNames())
3166 dests.push_back(tileOf(dest));
3168 for (StringRef source : route.getSourceNames())
3169 streamNets.push_back({tileOf(source), dests, packet});
3171 for (
auto [index, net] : llvm::enumerate(
streamNets)) {
3172 SetVector<Operation *> tiles;
3173 tiles.insert(net.src);
3174 tiles.insert(net.dsts.begin(), net.dsts.end());
3175 tiles.insert(net.delegate);
3176 tiles.insert(net.link);
3177 for (Operation *tile : tiles)
3184 function_ref<std::optional<TileID>(Operation *)> at,
3185 TileID &src, SmallVectorImpl<TileID> &dsts)
const {
3187 std::optional<TileID> from = net.
src ? at(net.
src) : std::nullopt;
3191 std::optional<TileID> delegate, link;
3195 if (net.
link && !(link = at(net.
link)))
3198 for (Operation *dst : net.
dsts) {
3199 std::optional<TileID> to = dst ? at(dst) : std::nullopt;
3202 if (!net.
mayShare || ObjectFifoCreateOp::sharedMemoryOf(
3205 dsts.push_back(*to);
3207 return !dsts.empty();
3212 : targetModel(&targetModel) {
3213 auto shimOf = [](Operation *tile) -> Operation * {
3214 auto like = dyn_cast_or_null<TileLike>(tile);
3215 return like && like.isShimNOCTile() ? tile :
nullptr;
3217 for (
auto program : device.getOps<ShimDMAOp>())
3218 if (Operation *shim = shimOf(program.getTile().getDefiningOp())) {
3219 StaticBds &bds = statics[shim];
3220 program.walk([&](DMABDOp bd) {
3221 if (std::optional<int32_t> id = bd.getBdId())
3222 bds.pinned.push_back(*id);
3228 std::optional<int> shimCol;
3229 for (
int col = 0; col <
targetModel.columns() && !shimCol; ++col)
3230 if (
targetModel.getTileType(col, 0) == AIETileType::ShimNOCTile)
3233 SymbolTable symbols(device);
3234 device.walk([&](RuntimeSequenceOp seq) {
3235 auto &events = sequences.emplace_back();
3236 DenseMap<Value, unsigned> taskOf;
3237 auto configure = [&](Operation *shim, Value
result, Region &body) {
3238 Task task{shim, {}, AIEX::DMAStartTaskOp::headBdIdAlignment(
result)};
3239 body.walk([&](DMABDOp bd) {
3240 std::optional<uint32_t> pinned;
3241 if (std::optional<int32_t>
id = bd.getBdId())
3242 pinned =
static_cast<uint32_t
>(*id);
3245 succeeded(plan) && !plan->pieces.empty() ? plan->pieces.size() : 1;
3247 task.bdIds.push_back(pinned);
3248 task.bdIds.append(pieces - 1, std::nullopt);
3250 taskOf[
result] = tasks.size();
3251 events.push_back({tasks.size(),
true});
3252 tasks.push_back(std::move(task));
3254 seq.walk([&](Operation *op) {
3257 if (
auto cfg = dyn_cast<AIEX::DMAConfigureTaskLike>(op)) {
3259 configure(shim, op->getResult(0), cfg.getBody());
3262 if (
auto copy = dyn_cast<AIEX::NpuDmaMemcpyNdOp>(op)) {
3264 events.push_back({tasks.size(),
true});
3266 {shim, {
static_cast<uint32_t
>(copy.getId())}, 1,
true});
3271 if (
auto await = dyn_cast<AIEX::DMAAwaitTaskOp>(op))
3272 released = await.getTask();
3273 else if (
auto free = dyn_cast<AIEX::DMAFreeTaskOp>(op))
3274 released = free.getTask();
3275 if (
auto it = taskOf.find(released); it != taskOf.end()) {
3276 events.push_back({it->second,
false});
3282 for (
auto &[shim, bds] : statics) {
3283 Peak &peak = peaks[shim];
3284 peak.live = bds.pinned.size() + bds.unpinned;
3285 peak.constrained |= !bds.pinned.empty();
3287 DenseMap<Operation *, int> mostHeld;
3288 for (
const auto &events : sequences) {
3289 DenseMap<Operation *, int> held;
3290 for (
auto [index, configured] : events) {
3291 const Task &task = tasks[index];
3292 int bds =
static_cast<int>(task.bdIds.size());
3293 int &now = held[task.owner];
3294 now += configured ? bds : -bds;
3295 int &most = mostHeld[task.owner];
3296 most = std::max(most, now);
3299 for (
const Task &task : tasks)
3300 peaks[task.owner].constrained |=
3301 task.headAlignment > 1 ||
3302 llvm::any_of(task.bdIds, [](
auto id) { return id.has_value(); });
3303 for (
auto &[shim, most] : mostHeld)
3304 peaks[shim].live += most;
3305 for (
auto &[shim, peak] : peaks)
3306 if (
auto tile = dyn_cast<TileOp>(shim))
3307 placed[{tile.getCol(), tile.getRow()}] = shim;
3309 auto shimAt = [&](Operation *shim) -> Shim & {
3310 auto [entry, fresh] = indexOf.try_emplace(shim, shims.size());
3313 {shim, {}, SmallVector<SmallVector<unsigned>>(sequences.size())});
3314 return shims[entry->second];
3316 for (
auto program : device.getOps<ShimDMAOp>())
3317 if (Operation *shim = shimOf(program.getTile().getDefiningOp()))
3319 for (
auto [index, task] : llvm::enumerate(tasks))
3320 shimAt(task.owner).tasks.push_back(index);
3321 for (
auto [sequence, events] : llvm::enumerate(sequences))
3322 for (
auto [at, event] : llvm::enumerate(events))
3323 shimAt(tasks[event.first].owner).events[sequence].push_back(at);
3328 llvm::SmallBitVector key(shims.size());
3330 bool constrained =
false;
3331 auto add = [&](Operation *shim) {
3332 auto peak = peaks.find(shim);
3333 if (peak == peaks.end())
3335 unsigned index = indexOf.lookup(shim);
3336 if (key.test(index))
3339 live += peak->second.live;
3340 constrained |= peak->second.constrained;
3342 for (Operation *shim : onTile)
3344 if (Operation *shim = placed.lookup(tile))
3348 live <=
static_cast<int>(targetModel->getNumBDs(tile.col, tile.row)))
3350 auto [cached, added] = shortfallOf.try_emplace(key, 0);
3352 return cached->second;
3353 int &missing = cached->second;
3358 for (
unsigned shim : key.set_bits())
3359 for (
unsigned task : shims[shim].tasks)
3360 for (std::optional<uint32_t> pinned : tasks[task].bdIds)
3363 SmallVector<uint32_t> staticIds;
3364 for (
unsigned shim : key.set_bits()) {
3365 StaticBds bds = statics.lookup(shims[shim].op);
3366 for (uint32_t
id : bds.pinned) {
3372 staticIds.push_back(
id);
3375 for (
unsigned shim : key.set_bits())
3376 for (
int i = 0, e = statics.lookup(shims[shim].op).unpinned; i < e; ++i) {
3377 if (std::optional<uint32_t>
id = assigned.
nextBdId(0))
3378 staticIds.push_back(*
id);
3383 SmallVector<unsigned> mine, merged;
3384 DenseMap<unsigned, SmallVector<uint32_t>> held;
3385 DenseSet<uint32_t> copied;
3386 for (
auto [sequence, events] : llvm::enumerate(sequences)) {
3388 for (uint32_t
id : staticIds)
3392 for (
unsigned shim : key.set_bits()) {
3393 ArrayRef<unsigned> theirs = shims[shim].events[sequence];
3395 std::merge(mine.begin(), mine.end(), theirs.begin(), theirs.end(),
3396 std::back_inserter(merged));
3397 std::swap(mine, merged);
3401 for (
unsigned at : mine) {
3402 auto [index, configured] = events[at];
3403 const Task &task = tasks[index];
3406 uint32_t
id = *task.bdIds.front();
3407 if (!copied.insert(
id).second)
3416 for (uint32_t
id : held.lookup(index))
3421 SmallVector<uint32_t> &taken = held[index];
3422 for (std::optional<uint32_t> pinned : task.bdIds) {
3430 taken.push_back(*pinned);
3432 for (
auto [i, pinned] : llvm::enumerate(task.bdIds)) {
3435 if (std::optional<uint32_t>
id =
3436 ids.
nextBdId(0, i == 0 ? task.headAlignment : 1))
3437 taken.push_back(*
id);
3446bool SequentialPlacer::fitsStreamAndBdBudgets(Operation *logicalTile,
3456 tile.col, tile.row, WireBundle::North))) ||
3459 tile.col, tile.row, WireBundle::South))) ||
3462 tile.col, tile.row, WireBundle::North))) ||
3465 tile.col, tile.row, WireBundle::South))))
3472 SmallVector<Operation *> onTile =
availability.runtimeBdTiles.lookup(tile);
3474 onTile.push_back(logicalTile);
3478bool SequentialPlacer::raisesStreamCuts(Operation *logicalTile,
3480 auto at = [&](Operation *op) -> std::optional<TileID> {
3481 if (op == logicalTile)
3483 if (
auto placed = dyn_cast<TileOp>(op))
3484 return placed.getTileID();
3488 int before = cuts.
over();
3490 SmallVector<TileID> dsts;
3494 return cuts.
over() > before;
3497void SequentialPlacer::addPlacedStreams(Operation *logicalTile) {
3498 auto at = [&](Operation *op) -> std::optional<TileID> {
3499 if (
auto placed = dyn_cast<TileOp>(op))
3500 return placed.getTileID();
3504 SmallVector<TileID> dsts;
3507 placedCuts.add(src, dsts,
streamNets[net].packet, 1);
3512void SequentialPlacer::recordStreamAndBdUsage(Operation *logicalTile,
3515 overlayTilesAt[tile].push_back(logicalTile);
3517 pinsAt.place(tile, end, 1);
3518 for (
const DMAChannelAnalysis::ChannelClaim &claim :
3520 pinsAt.claim(tile, claim, 1);
3524 availability.runtimeBdTiles[tile].push_back(logicalTile);
3528 auto removeFromVector = [&](std::vector<TileID> &vec) {
3529 vec.erase(std::remove(vec.begin(), vec.end(), tile), vec.end());
3533 case AIETileType::CoreTile:
3538 case AIETileType::MemTile:
3539 case AIETileType::ShimNOCTile:
3540 case AIETileType::ShimPLTile:
virtual AIETileType getTileType(int col, int row) const =0
Return the tile type for the given tile coordinates.
virtual int rows() const =0
Return the number of rows in the device.
virtual int columns() const =0
Return the number of columns in the device.
virtual uint32_t getNumDestSwitchboxConnections(int col, int row, WireBundle bundle) const =0
Return the number of destinations of connections inside a switchbox.
@ None
Neither tile can address the other's memory module.
virtual uint32_t getNumSourceSwitchboxConnections(int col, int row, WireBundle bundle) const =0
Return the number of sources of connections inside a switchbox.
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,...
Which DMA channels of each tile are already spoken for, so that a channel is handed out at most once ...
llvm::ArrayRef< ChannelClaim > getChannelClaims() const
The channels taken by index rather than through a route endpoint, in the order the claims were made.
std::optional< DMAChannelAnalysis::ChannelClaim > claimWith(TileID at, const PinnedChannels::End &end) const
std::optional< PinnedChannels::End > clashWith(TileID at, const PinnedChannels::End &end) const
llvm::SmallVector< int > channelsAt(TileID at, bool sends) const
int place(TileID at, const PinnedChannels::End &end, int sign)
std::optional< std::pair< int, int > > heldAt(TileID at, llvm::ArrayRef< PinnedChannels::End > ends) const
llvm::DenseMap< int, llvm::SmallVector< PinnedChannels::End, 2 > > sendingAt(TileID at) const
void claim(TileID at, const DMAChannelAnalysis::ChannelClaim &claim, int sign)
int clashes(TileID at) const
std::optional< std::string > whyApart(End a, End b) const
bool sharesClaim(End end, const DMAChannelAnalysis::ChannelClaim &claim) const
static std::optional< End > endOf(ObjectFifoCreateOp fifo, std::optional< unsigned > consumer)
unsigned share(End end, const llvm::DenseMap< mlir::Operation *, unsigned > &rank)
int shortfall(llvm::ArrayRef< mlir::Operation * > onTile, TileID tile) const
llvm::DenseMap< mlir::Operation *, llvm::SmallVector< DMAChannelAnalysis::ChannelClaim > > claimsOf
static Adjacency buildCascadeAdjacency(llvm::ArrayRef< CascadeFlowOp > cascadeFlows)
llvm::SmallVector< mlir::Operation * > overlayTileOps() const
static bool satisfiesConstraints(mlir::Operation *tile, TileID pos)
static llvm::MapVector< mlir::Operation *, std::pair< int, int > > flowChannelDemand(llvm::ArrayRef< FlowOp > flows, llvm::ArrayRef< PacketFlowOp > pktFlows, llvm::ArrayRef< RouteOp > routes, llvm::ArrayRef< DMAChannelAnalysis::ChannelClaim > claims, llvm::DenseMap< mlir::Operation *, llvm::SmallVector< std::pair< int, int > > > *named=nullptr, llvm::DenseMap< mlir::Operation *, mlir::Operation * > *keys=nullptr)
static Adjacency buildSharedMemAdjacency(llvm::ArrayRef< ObjectFifoCreateOp > objectFifos)
llvm::DenseMap< mlir::Operation *, llvm::SmallVector< unsigned > > ddrGroupsOf
void buildStreamNets(DeviceOp device, const CollectedOps &collected)
llvm::DenseMap< mlir::Operation *, llvm::SmallVector< unsigned > > streamNetsOf
int64_t ddrGroupSpread(const DdrGroup &group, llvm::function_ref< std::optional< int >(mlir::Operation *)> columnOf, int weight) const
llvm::DenseMap< mlir::Operation *, StreamDemand > streamDemand
llvm::SmallVector< StreamNet > streamNets
llvm::DenseMap< mlir::Operation *, unsigned > coreKeys
RuntimeBdIds runtimeBdIds
static Adjacency buildObjectFifoAdjacency(llvm::ArrayRef< ObjectFifoCreateOp > objectFifos)
static ShareableShimEnds collectShareableShimEnds(DeviceOp device, llvm::ArrayRef< ObjectFifoCreateOp > objectFifos, const llvm::DenseMap< mlir::Operation *, unsigned > &rank, const llvm::DenseMap< mlir::Operation *, mlir::Operation * > &routeKeys={})
static llvm::DenseMap< mlir::StringAttr, llvm::SmallVector< ShimTransferSpans::Gate > > provenShimGates(DeviceOp device)
llvm::DenseMap< mlir::Operation *, int > broadcastFanout
static Adjacency buildFlowAdjacency(llvm::ArrayRef< FlowOp > flows, llvm::ArrayRef< PacketFlowOp > pktFlows)
const AIETargetModel * targetModel
int64_t ddrSpread(llvm::function_ref< std::optional< int >(mlir::Operation *)> columnOf, int weight) const
static Adjacency buildComputePeerAdjacency(llvm::ArrayRef< ObjectFifoCreateOp > objectFifos)
bool overlayChannels(TileID tile) const
llvm::DenseMap< mlir::Operation *, llvm::SmallVector< std::pair< int, int > > > namedChannels
llvm::SmallVector< AllocateInfo > allocates
std::optional< std::pair< mlir::Operation *, std::pair< int, int > > > namedClash(mlir::Operation *tile, llvm::ArrayRef< mlir::Operation * > others) const
bool streamOf(const StreamNet &net, llvm::function_ref< std::optional< TileID >(mlir::Operation *)> at, TileID &src, llvm::SmallVectorImpl< TileID > &dsts) const
ShareableShimEnds shareableShimEnds
std::optional< ShimTransferSpans > shimSpans
std::optional< TileID > getPlacement(mlir::Operation *logicalTile) const
void buildShimModel(DeviceOp device, llvm::ArrayRef< ObjectFifoCreateOp > objectFifos, llvm::ArrayRef< DMAChannelAnalysis::ChannelClaim > claims, const llvm::DenseMap< mlir::Operation *, unsigned > &rank, const llvm::DenseMap< mlir::Operation *, mlir::Operation * > &routeKeys={})
void collectOverlayUses(DeviceOp device)
TileAvailability availability
llvm::MapVector< mlir::Operation *, std::array< ShimSide, 2 > > ShareableShimEnds
void buildStreamDemand(llvm::ArrayRef< ObjectFifoCreateOp > objectFifos)
static int shimChannelsSaved(const ShimTransferSpans &spans, llvm::ArrayRef< const ShimSide * > sides, llvm::ArrayRef< mlir::StringAttr > extra, llvm::ArrayRef< int > pinnedHere)
OverlayFit overlayAt(TileID at, const PinnedChannelUse &pins, llvm::ArrayRef< PinnedChannels::End > extra, llvm::ArrayRef< mlir::Operation * > tilesHere, const ShimTransferSpans *spans) const
llvm::DenseMap< mlir::Operation *, llvm::SmallVector< mlir::Operation * > > incomingFifos
mlir::LogicalResult emitNamedClash(mlir::Operation *tile, TileID at, std::pair< mlir::Operation *, std::pair< int, int > > clash) const
static CollectedOps collectOperations(DeviceOp device)
llvm::SmallVector< DdrGroup > ddrGroups
virtual void initialize(DeviceOp device, bool controlOverlay, bool adaptiveOverlay, bool packetSwitched)
void initialize(DeviceOp device, bool controlOverlay, bool adaptiveOverlay, bool packetSwitched) override
mlir::LogicalResult place(DeviceOp device) override
Shim endpoint lifetimes, including calls to self-contained runtime sequences.
llvm::DenseMap< mlir::StringAttr, llvm::SmallVector< Gate > > Gates
Plan plan(llvm::ArrayRef< mlir::StringAttr > ends, llvm::ArrayRef< mlir::StringAttr > names, llvm::ArrayRef< SharedChannel > shared) const
Plans ends (keyed as apart() takes keys); names[i] is how shared's lists name ends[i].
bool apart(mlir::StringAttr a, mlir::StringAttr b) const
Whether both ends permit sharing: explicitly, by MM2S lifetime analysis, or, for a receiving end,...
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.
mlir::StringAttr overlayEnd(int column) const
The planned control overlay channel's end on column column's shim tile.
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,...
int64_t near(double fraction) const
void add(TileID src, llvm::ArrayRef< TileID > dsts, bool packet, int sign)
Operation * getRuntimeDmaTile(Operation *op, SymbolTable &symbols)
mlir::FailureOr< TaskBdDecomposition > decomposeTaskBdPattern(xilinx::AIE::DMABDOp bd, const xilinx::AIE::AIETargetModel &targetModel, int tileCol, int tileRow)
Plan the split of bd, a runtime task's descriptor, on tile (tileCol, tileRow).
void forEachPeer(mlir::Operation *op, const Placer::Adjacency &adjacency, F &&fn)
bool isPacketSwitched(PacketInfoAttr header, bool packetSwDefault)
llvm::DenseMap< mlir::Operation *, TileID > PlacementResult
bool getsColumnControlOverlay(DeviceOp device, bool configuration)
void forEachMemAffinityNeighbor(const AIETargetModel &targetModel, TileID at, F &&fn)
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
std::pair< int, int > getDMACapacity(const AIETargetModel &tm, TileID tile)
Get DMA channel capacity (maxIn, maxOut) for a tile position: its S2MM and MM2S channel counts.
std::tuple< bool, int, bool > boundaryOf(TileID a, TileID b)
std::unique_ptr< mlir::OperationPass< DeviceOp > > createAIEObjectFifoVerifyPass()
bool isSharedComputeMemory(const AIETargetModel &targetModel, TileID a, TileID b)
std::unique_ptr< mlir::OperationPass< DeviceOp > > createAIEObjectFifoSplitPass()
ShimMM2SUses shimMM2SUses(DeviceOp device, bool packetSwitched)
bool bdIdAlreadyAssigned(uint32_t bdId)
void assignBdId(uint32_t bdId)
void freeBdId(uint32_t bdId)
std::optional< uint32_t > nextBdId(int channelIndex, uint32_t alignment=1)
A channel claimed by index: by a DMA program start, a runtime task or a shim allocation (owner),...
void addEdge(TileLike first, TileLike second)
llvm::DenseMap< mlir::Operation *, llvm::SmallVector< unsigned, 2 > > tileToEdges
void addEdgeFromValues(mlir::Value a, mlir::Value b)
llvm::SmallVector< std::pair< TileLike, TileLike >, 4 > edges
llvm::SmallVector< RouteOp > routes
llvm::SmallVector< ObjectFifoLinkOp > objectFifoLinks
llvm::SmallVector< CascadeFlowOp > cascadeFlows
llvm::DenseMap< mlir::Operation *, unsigned > rank
llvm::SmallVector< PacketFlowOp > pktFlows
llvm::SmallVector< FlowOp > flows
llvm::SmallVector< ObjectFifoCreateOp > objectFifos
llvm::SmallVector< ObjectFifoAllocateOp > objectFifoAllocates
llvm::SmallVector< LogicalTileOp > logicalTiles
llvm::SmallVector< int64_t > weights
llvm::SmallVector< llvm::BitVector > together
llvm::SmallVector< mlir::Operation * > tiles
llvm::SmallVector< mlir::StringAttr > ends
llvm::SmallVector< int > pinned
llvm::SmallVector< std::pair< int, llvm::SmallVector< mlir::StringAttr > > > shared
llvm::SmallVector< mlir::Operation *, 2 > dsts
mlir::Operation * delegate
The shim MM2S channels device's overlay weighs, for aie-generate-column-control-overlay.
llvm::DenseMap< std::pair< mlir::Operation *, int >, unsigned > packetFlows
Packet flows per (tile, channel).
llvm::DenseMap< mlir::Operation *, llvm::SmallSet< int, 2 > > circuits
Channels a circuit-switched route end, flow, allocation or shim mux holds, per shim tile op.
llvm::DenseMap< std::pair< mlir::Operation *, int >, llvm::SmallVector< mlir::StringAttr > > packetEnds
Packet-switched route ends, by name, per (tile, channel).
A shim input gating a receiving end's senders, per its #aie.consumed_by.
How one shim tile's unpinned ends in one direction share channels, as objectFIFO allocation shares th...
llvm::SmallVector< llvm::SmallVector< unsigned > > groups
The other ends, in groups taking one channel each.
llvm::DenseMap< mlir::Operation *, unsigned > rank() const
Rank the nodes by their features and then, a round at a time until no class splits,...
static StructuralGraph of(DeviceOp device)
The ops directly in device but its runtime sequences, each with the ops nested in it,...
std::vector< TileID > compTiles
std::vector< TileID > overBudgetCompTiles
void removeTile(TileID tile, AIETileType type)
std::vector< TileID > nonCompTiles
llvm::DenseSet< TileID > compTilesSet