MLIR-AIE 1.4.6.dev
AIEPlacer.cpp
Go to the documentation of this file.
1//===- AIEPlacer.cpp --------------------------------------------*- C++ -*-===//
2//
3// Copyright (C) 2026 Advanced Micro Devices, Inc.
4// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
5//
6//===----------------------------------------------------------------------===//
7
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"
27
28#include <algorithm>
29#include <cmath>
30#include <iterator>
31#include <limits>
32#include <numeric>
33
34using namespace mlir;
35using namespace xilinx::AIE;
36
37#define DEBUG_TYPE "aie-placer"
38
39static std::optional<TileID> resolvePeerPosition(TileLike peer,
40 const PlacementResult &placed);
41
42void Placer::Adjacency::addEdge(TileLike first, TileLike second) {
43 if (!first || !second)
44 return;
45 unsigned idx = edges.size();
46 edges.push_back({first, second});
47 if (mlir::isa<LogicalTileOp>(first.getOperation()))
48 tileToEdges[first.getOperation()].push_back(idx);
49 if (mlir::isa<LogicalTileOp>(second.getOperation()))
50 tileToEdges[second.getOperation()].push_back(idx);
51}
52
54 if (!a || !b)
55 return;
56 auto aT = dyn_cast_or_null<TileLike>(a.getDefiningOp());
57 auto bT = dyn_cast_or_null<TileLike>(b.getDefiningOp());
58 if (aT && bT)
59 addEdge(aT, bT);
60}
61
62void Placer::initialize(DeviceOp device, bool controlOverlay,
64 const AIETargetModel &tm = device.getTargetModel();
65 targetModel = &tm;
66 this->controlOverlay = controlOverlay;
67 this->adaptiveOverlay = adaptiveOverlay;
68 this->packetSwitched = packetSwitched;
69 availability.physicalCores.clear();
70 for (CoreOp core : device.getOps<CoreOp>())
71 if (auto tile = dyn_cast_or_null<TileOp>(core.getTile().getDefiningOp()))
72 availability.physicalCores.insert(tile.getTileID());
73 availability.compTiles.clear();
74 availability.overBudgetCompTiles.clear();
75 availability.nonCompTiles.clear();
76 for (int col = 0; col < tm.columns(); col++) {
77 for (int row = 0; row < tm.rows(); row++) {
78 TileID id = {col, row};
79 switch (tm.getTileType(col, row)) {
80 case AIETileType::CoreTile:
81 if (!availability.physicalCores.contains(id))
82 availability.compTiles.push_back(id);
83 break;
84 case AIETileType::MemTile:
85 case AIETileType::ShimNOCTile:
86 availability.nonCompTiles.push_back(id);
87 break;
88 default:
89 break;
90 }
91 }
92 }
93}
94
96 CollectedOps ops;
97 device.walk([&](Operation *op) {
98 llvm::TypeSwitch<Operation *>(op)
99 .Case<LogicalTileOp>([&](auto lt) { ops.logicalTiles.push_back(lt); })
100 .Case<ObjectFifoCreateOp>(
101 [&](auto of) { ops.objectFifos.push_back(of); })
102 .Case<ObjectFifoLinkOp>(
103 [&](auto link) { ops.objectFifoLinks.push_back(link); })
104 .Case<ObjectFifoAllocateOp>(
105 [&](auto alloc) { ops.objectFifoAllocates.push_back(alloc); })
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); });
110 });
111 // Every later tie between logical tiles falls back on this order, so it is
112 // the design's structure rather than the order the tiles were written in:
113 // shim tiles, which have the fewest places to go, then MemTiles, then cores.
114 ops.rank = StructuralGraph::of(device).rank();
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);
119 });
120 return ops;
121}
122
123bool Placer::satisfiesConstraints(Operation *tile, TileID pos) {
124 if (auto lt = dyn_cast<LogicalTileOp>(tile)) {
125 if (auto c = lt.tryGetCol(); c && *c != pos.col)
126 return false;
127 if (auto r = lt.tryGetRow(); r && *r != pos.row)
128 return false;
129 }
130 return true;
131}
132
134 bool adaptiveOverlay, bool packetSwitched) {
136
137 // Compute tiles iterate column-major (fill a column top-to-bottom before
138 // moving right); non-compute tiles iterate row-major.
139 auto compTileCmp = [](TileID a, TileID b) {
140 if (a.col != b.col)
141 return a.col < b.col;
142 return a.row < b.row;
143 };
144 auto rowMajorCmp = [](TileID a, TileID b) {
145 if (a.row != b.row)
146 return a.row < b.row;
147 return a.col < b.col;
148 };
149 std::sort(availability.compTiles.begin(), availability.compTiles.end(),
150 compTileCmp);
151 std::sort(availability.nonCompTiles.begin(), availability.nonCompTiles.end(),
152 rowMajorCmp);
153 availability.compTilesSet.clear();
154 availability.compTilesSet.insert(availability.compTiles.begin(),
155 availability.compTiles.end());
156
157 if (coresPerCol.has_value()) {
158 deviceCoresPerCol = 0;
159 for (int col = 0; col < targetModel->columns(); col++) {
160 int cores = 0;
161 for (int row = 0; row < targetModel->rows(); row++)
162 cores += targetModel->getTileType(col, row) == AIETileType::CoreTile;
163 deviceCoresPerCol = std::max(deviceCoresPerCol, cores);
164 }
165 DenseSet<TileID> held(availability.physicalCores.begin(),
166 availability.physicalCores.end());
167 for (CoreOp core : device.getOps<CoreOp>())
168 if (auto tile =
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);
173 }
174}
175
176void SequentialPlacer::limitCoresPerColumn(int maxCoresPerCol, int numColumns,
177 const DenseSet<TileID> &held) {
178 llvm::DenseMap<int, std::vector<TileID>> tilesByColumn;
179 for (const auto &tile : availability.compTiles)
180 if (!held.contains(tile))
181 tilesByColumn[tile.col].push_back(tile);
182
183 // Keep the first maxCoresPerCol tiles from each column, less the column's
184 // held cores. The per-column vectors are already row-sorted because
185 // compTiles is column-major.
186 DenseMap<int, int> heldInColumn;
187 for (TileID tile : held)
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())
193 continue;
194 const auto &tilesInCol = it->second;
195 size_t numToTake = std::min<size_t>(
196 tilesInCol.size(),
197 std::max(0, maxCoresPerCol - heldInColumn.lookup(col)));
198 limitedTiles.insert(limitedTiles.end(), tilesInCol.begin(),
199 tilesInCol.begin() + numToTake);
201 availability.overBudgetCompTiles.end(), tilesInCol.begin() + numToTake,
202 tilesInCol.end());
203 }
204
205 placeableCores = limitedTiles.size();
206 availability.compTiles = limitedTiles;
209 availability.compTiles.end());
210}
211
212LogicalResult SequentialPlacer::place(DeviceOp device) {
213 // Phase 0: Validate options
214 if (!targetModel)
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)";
221 }
222
223 // Phase 1: Collect operations needed for placement
224 auto collected = collectOperations(device);
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;
232
233 // Phase 2a: Build placement constraints
234 auto bufferAdjacency =
235 buildBufferAdjacency(logicalTiles, collected.objectFifoAllocates);
236 auto computePeerAdjacency = buildComputePeerAdjacency(objectFifos);
237 auto sharedMemAdjacency = buildSharedMemAdjacency(objectFifos);
238
239 // Phase 2b: Build channel requirements from ObjectFifo and Flow connectivity,
240 // and cascade adjacency constraints from CascadeFlow connectivity.
241 auto channelRequirements =
242 buildChannelRequirements(objectFifos, objectFifoLinks, collected.rank);
243 if (pinnedRule.failed())
244 return failure();
245 namedChannels.clear();
246 llvm::DenseMap<Operation *, Operation *> demandKeys;
247 DMAChannelAnalysis channelAnalysis(device);
248 for (auto &[tile, inOut] : flowChannelDemand(
249 flows, pktFlows, routes, channelAnalysis.getChannelClaims(),
250 &namedChannels, &demandKeys)) {
251 channelRequirements[tile].first += inOut.first;
252 channelRequirements[tile].second += inOut.second;
253 }
254 countTurns(device, objectFifos, channelRequirements);
255 buildStreamDemand(objectFifos);
256 columnStreamsUsed.clear();
257 columnIncomingFifos.clear();
258 broadcastFanoutUsed.clear();
259 for (auto &[op, demand] : streamDemand)
260 if (auto tile = dyn_cast<TileOp>(op))
261 if (tile.isCoreTile())
262 recordColumnStreamUsage(op, tile.getCol());
263 for (auto &[op, fanout] : broadcastFanout)
264 if (auto tile = dyn_cast<TileOp>(op))
265 broadcastFanoutUsed[{tile.getCol(), tile.getRow()}] += fanout;
266 buildStreamNets(device, collected);
267 placedCuts = StreamCuts(*targetModel);
268 cutNets.clear();
269 cutNets.resize(streamNets.size());
270 for (TileOp tile : device.getOps<TileOp>())
271 addPlacedStreams(tile);
272 buildShimModel(device, objectFifos, channelAnalysis.getChannelClaims(),
273 collected.rank, demandKeys);
274 shimTilesAt.clear();
275 overlayTilesAt.clear();
276 // Seed each physical tile op's position with the ends, flows and claims it
277 // already holds.
278 for (TileOp placed : device.getOps<TileOp>()) {
279 TileID at = placed.getTileID();
280 auto [in, out] = channelRequirements.lookup(placed);
281 if (in)
282 updateChannelUsage(at, DmaDir::In, in);
283 if (out)
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);
288 for (const DMAChannelAnalysis::ChannelClaim &claim :
289 claimsOf.lookup(placed))
290 pinsAt.claim(at, claim, 1);
291 recordShimEnds(at, placed);
292 }
293 // Other devices of the overlay's target count where they sit.
294 for (Operation *tile : overlayTileOps())
295 if (auto placed = dyn_cast<TileOp>(tile);
296 placed && placed->getParentOfType<DeviceOp>() != device)
297 overlayTilesAt[placed.getTileID()].push_back(placed);
298
299 auto cascadeAdjacency = buildCascadeAdjacency(cascadeFlows);
300
301 // A forced-shared-mem peer is already in `computePeerAdjacency`; this
302 // tallies which of a tile's peers are forced, to floor its neighbor
303 // demand below regardless of DMA channel headroom.
304 llvm::DenseMap<Operation *, int> forcedSharedMemIn, forcedSharedMemOut;
305 for (auto ofOp : objectFifos) {
306 if (!ofOp.forcesSharedMemory() || ofOp.getConsumerTiles().size() != 1)
307 continue;
308 auto producer =
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)
313 continue;
314 if (!consumer || consumer.getTileType() != AIETileType::CoreTile)
315 continue;
316 if (producer.getOperation() == consumer.getOperation())
317 continue;
318 ++forcedSharedMemOut[producer.getOperation()];
319 ++forcedSharedMemIn[consumer.getOperation()];
320 }
321
322 // Phase 2c: For every compute LTO, compute the minimum number of its
323 // compute-peer producers/consumers that must land on physical neighbors so
324 // the LTO fits its DMA channel budget. A compute→compute ObjectFifo can use
325 // shared neighbor memory (no DMA) when the two endpoints sit on physical-
326 // neighbor compute tiles; otherwise it consumes one DMA channel on each
327 // side. Non-compute-peer fifos (from/to memtile or shim) always need a DMA
328 // channel and already appear in `channelRequirements`, so the headroom left
329 // for compute-peer fifos is (DMA-budget − channelRequirements). If a
330 // Worker has more compute-peer fifos than that headroom, the surplus MUST
331 // come from neighbors -- and a peer forcing shared memory always must,
332 // budget or not.
333 llvm::DenseMap<Operation *, int> needNeighborIn, needNeighborOut;
334 for (auto lt : logicalTiles) {
335 if (lt.getTileType() != AIETileType::CoreTile)
336 continue;
337 auto [peerIn, peerOut] =
338 totalComputePeers(lt.getOperation(), computePeerAdjacency);
339 auto [inBudget, outBudget] =
340 getDMACapacity(*targetModel, lt.getCanonicalTileID());
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()]
355 << "\n");
356 }
357 PlacementContext ctx{*targetModel, computePeerAdjacency, needNeighborIn,
358 needNeighborOut};
359
360 // Phase 2d: group cores by the non-core tile they share the most flows
361 // with, so each group can be placed in one column and its hub's centroid
362 // lands there too.
363 FlowMembership flowIndex =
364 buildFlowMembership(flows, pktFlows, routes, objectFifos);
365 CoreGroups coreGroups = buildCoreGroups(logicalTiles, flowIndex);
366
367 // Per-kind predicates / labelers shared by all phase-3 call sites below.
368 // Buffer: consumer LTO (edge.first) must satisfy isLegalMemAffinity to the
369 // owner tile (edge.second).
370 auto bufferPred = [this](TileID consumerPos, TileID ownerPos) {
371 return targetModel->isLegalMemAffinity(consumerPos.col, consumerPos.row,
372 ownerPos.col, ownerPos.row);
373 };
374 auto bufferLabel = [](bool thisIsConsumer) -> StringRef {
375 return thisIsConsumer ? "shared-L1 buffer owner"
376 : "shared-L1 buffer consumer";
377 };
378 // Cascade: same predicate as AIELowerCascadeFlowsPass -- src (edge.first)
379 // must be one row North or one column West of dst (edge.second); rows
380 // increase upward, so isSouth(src,dst) means dst is south of src.
381 auto cascadePred = [this](TileID srcPos, TileID dstPos) {
382 return targetModel->isLegalCascade(srcPos.col, srcPos.row, dstPos.col,
383 dstPos.row);
384 };
385 auto cascadeLabel = [](bool thisIsSrc) -> StringRef {
386 return thisIsSrc ? "cascade destination" : "cascade source";
387 };
388 // Shared memory: unlike buffer ownership, either end satisfying
389 // isLegalMemAffinity to the other is enough -- a shared_mem objectFifo
390 // has no owner/consumer asymmetry, it just needs both ends on tiles that
391 // share a memory module. Same bidirectional check as SAPlacer's own
392 // shared-memory penalty.
393 auto sharedMemPred = [this](TileID aPos, TileID bPos) {
394 return targetModel->isLegalMemAffinity(aPos.col, aPos.row, bPos.col,
395 bPos.row) ||
396 targetModel->isLegalMemAffinity(bPos.col, bPos.row, aPos.col,
397 aPos.row);
398 };
399 auto sharedMemLabel = [](bool thisIsProducer) -> StringRef {
400 return thisIsProducer ? "shared-memory consumer" : "shared-memory producer";
401 };
402
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)"};
418
419 // Phase 3: Place constrained tiles then compute tiles.
420 //
421 // Process LogicalTileOps in order of how constrained they are: fully pinned
422 // (both col and row) first, partially constrained (col xor row) next, fully
423 // unpinned last. This guarantees every pinned coordinate is recorded — and
424 // for CoreTiles, removed from availability — before any unpinned tile gets
425 // to pick from `availability.compTiles`, so unpinned tiles cannot land on a
426 // coordinate that a later-iterated pinned tile claims.
427 //
428 // Within the unpinned bucket, place compute LTOs with the highest
429 // neighbor-demand first so a high-fanin Worker grabs an interior tile (with
430 // two compute neighbors) before its producers consume the surrounding
431 // slots. Producers and consumers that the heavy Worker needs as physical
432 // neighbors are then steered to those slots by `computePeerAdjacency`.
433 //
434 // Before sorting, each core group is made contiguous at its first member,
435 // so the order in which the program creates cores does not decide which
436 // of them share a column.
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]);
445 }
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)
451 return 0; // fully pinned
452 if (hasCol || hasRow)
453 return 1; // partially constrained
454 return 2; // fully unpinned
455 };
456 int ra = rank(a), rb = rank(b);
457 if (ra != rb)
458 return ra < rb;
459 // Same constraint level: high priority first. Priority
460 // = max(self demand, highest peer demand) so a Worker's
461 // compute-peer producers/consumers also rise to the
462 // front and claim the Worker's neighbor tiles before
463 // unrelated LTOs consume them.
464 int pa = ctx.placementPriority(a.getOperation());
465 int pb = ctx.placementPriority(b.getOperation());
466 if (pa != pb)
467 return pa > pb;
468 // Among equal priority, place the high-demand LTO
469 // itself first so its peers can be steered to its
470 // neighbors immediately afterward.
471 return ctx.neighborDemand(a.getOperation()) >
472 ctx.neighborDemand(b.getOperation());
473 });
474
475 // An unpinned tile sharing L1 with another unpinned tile is placed right
476 // after it, while that tile's neighbors are still free.
477 auto unpinned = [](LogicalTileOp lt) {
478 return !lt.tryGetCol() && !lt.tryGetRow();
479 };
480 SmallVector<LogicalTileOp> sequenced;
481 llvm::DenseSet<Operation *> queued;
482 for (auto start : orderedTiles) {
483 if (!queued.insert(start.getOperation()).second)
484 continue;
485 size_t next = sequenced.size();
486 sequenced.push_back(start);
487 for (; next < sequenced.size(); ++next) {
488 LogicalTileOp lt = sequenced[next];
489 if (!unpinned(lt))
490 continue;
491 forEachPeer(lt.getOperation(), bufferAdjacency,
492 [&](TileLike peer, bool /*thisIsFirst*/) {
493 auto peerLt = dyn_cast<LogicalTileOp>(peer.getOperation());
494 if (peerLt && unpinned(peerLt) &&
495 queued.insert(peerLt.getOperation()).second)
496 sequenced.push_back(peerLt);
497 });
498 }
499 }
500 orderedTiles = std::move(sequenced);
501
502 for (auto logicalTile : orderedTiles) {
503 // Place fully constrained tiles at their specified coordinates
504 auto col = logicalTile.tryGetCol();
505 auto row = logicalTile.tryGetRow();
506 if (col && row) {
507 TileID tile{*col, *row};
508 if (failed(enforceAdjacency(logicalTile, tile, bufferKind)))
509 return failure();
510 if (failed(enforceAdjacency(logicalTile, tile, cascadeKind)))
511 return failure();
512 if (failed(enforceAdjacency(logicalTile, tile, sharedMemKind)))
513 return failure();
514 if (failed(validateAndUpdateChannelUsage(
515 logicalTile, tile, channelRequirements, PlacementOrigin::Pinned)))
516 return failure();
517
518 recordPlacement(logicalTile, tile, ctx, "pinned");
519 continue;
520 }
521
522 // Place compute tiles with partial constraint support
523 if (logicalTile.getTileType() == AIETileType::CoreTile) {
524 auto isReservedForOtherBound = [&](Operation *lto, TileID candidate) {
525 return ctx.isReservedForOther(lto, candidate);
526 };
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,
535 preferredCols};
536 // A pin outranks the budget, so a pinned core searches the tiles it
537 // left out as well.
538 bool searchedPastBudget = col || row;
539 auto search = findUnconstrainedCoreCandidate(
540 logicalTile, col, row, inputs, availability.compTiles,
541 searchedPastBudget
542 ? ArrayRef<TileID>(availability.overBudgetCompTiles)
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;
549
550 if (!placement) {
551 bool adjacencyWasCause =
552 sawConstraintMatch && allConstraintMatchesFailedAdjacency &&
553 bufferAdjacency.hasEdges(logicalTile.getOperation());
554 bool hasCascade = cascadeAdjacency.hasEdges(logicalTile.getOperation());
555 bool hasSharedMem =
556 sharedMemAdjacency.hasEdges(logicalTile.getOperation());
557 InFlightDiagnostic diag = logicalTile.emitError();
558 if (col || row) {
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" : "");
566 } else {
567 diag << "no available compute tiles for placement"
568 << (adjacencyWasCause
569 ? " (shared-L1 buffer adjacency unsatisfiable)"
570 : "")
571 << (hasCascade ? " (cascade adjacency unsatisfiable)" : "")
572 << (hasSharedMem ? " (shared-memory transport unsatisfiable)"
573 : "")
574 << (computePeerWasCause
575 ? " (compute-peer DMA budget unsatisfiable)"
576 : "");
577 }
578 // A cores-per-col budget leaves no trace in the message above: the
579 // tiles it removed are simply absent from `availability.compTiles`.
580 if (coresPerCol.has_value() && deviceCoresPerCol > 0 &&
581 !searchedPastBudget) {
582 int columns = targetModel->columns();
583 diag.attachNote()
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";
589 }
590 if (search.pinClash)
591 notePinClash(diag, logicalTile, *search.pinClash);
592 if (adjacencyWasCause)
593 attachPeerNotes(diag, logicalTile, bufferAdjacency, bufferLabel);
594 if (hasCascade)
595 attachPeerNotes(diag, logicalTile, cascadeAdjacency, cascadeLabel);
596 if (hasSharedMem)
597 attachPeerNotes(diag, logicalTile, sharedMemAdjacency,
598 sharedMemLabel);
599 if (computePeerWasCause) {
600 attachPeerNotes(diag, logicalTile, computePeerAdjacency,
601 [](bool thisIsProducer) -> StringRef {
602 return thisIsProducer ? "compute-peer consumer"
603 : "compute-peer producer";
604 });
605 diag.attachNote()
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 "
609 "satisfiable";
610 }
611 if (adjacencyWasCause || hasCascade || hasSharedMem ||
612 computePeerWasCause)
613 diag.attachNote()
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";
618 return failure();
619 }
620
621 if (failed(validateAndUpdateChannelUsage(logicalTile, *placement,
622 channelRequirements,
623 PlacementOrigin::Selected)))
624 return failure();
625
626 recordPlacement(logicalTile, *placement, ctx, "unconstrained");
627 }
628
629 if (logicalTile.getTileType() == AIETileType::ShimPLTile) {
630 return logicalTile.emitError(
631 "DMA channel-based SequentialPlacer does not support unplaced "
632 "ShimPLTiles (no DMAs).");
633 }
634 }
635
636 // Phase 4: place every still-unplaced non-core (mem/shim) LTO at the
637 // centroid column of its placed core peers.
638 return placeNonCoreLogicalTiles(logicalTiles, flowIndex, channelRequirements);
639}
640
641SequentialPlacer::CoreGroups
642SequentialPlacer::buildCoreGroups(ArrayRef<LogicalTileOp> logicalTiles,
643 const FlowMembership &flowIndex) const {
644 // Flows from each core to each non-core tile, in first-seen order.
645 SmallVector<std::pair<LogicalTileOp, llvm::MapVector<Operation *, int>>>
646 coreFlows;
647 llvm::DenseMap<Operation *, int> coresOnHub;
648 for (auto lt : logicalTiles) {
649 if (lt.getTileType() != AIETileType::CoreTile)
650 continue;
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()];
659 }
660 for (auto &entry : counts)
661 ++coresOnHub[entry.first];
662 coreFlows.emplace_back(lt, std::move(counts));
663 }
664
665 // A core's hub is the tile it has the most flows with; on a tie, the one
666 // fewer cores touch (the more specific one), then the first seen.
667 CoreGroups groups;
668 llvm::DenseMap<Operation *, unsigned> groupOfHub;
669 for (auto &[lt, counts] : coreFlows) {
670 Operation *hub = nullptr;
671 int best = 0;
672 for (auto &[peer, n] : counts)
673 if (!hub || n > best ||
674 (n == best && coresOnHub[peer] < coresOnHub[hub])) {
675 hub = peer;
676 best = n;
677 }
678 unsigned idx = groups.members.size();
679 if (hub) {
680 auto [it, inserted] = groupOfHub.try_emplace(hub, idx);
681 idx = it->second;
682 if (!inserted) {
683 groups.members[idx].push_back(lt);
684 groups.groupOf[lt.getOperation()] = idx;
685 continue;
686 }
687 }
688 groups.members.push_back({lt});
689 groups.groupOf[lt.getOperation()] = idx;
690 }
691 return groups;
692}
693
694SmallVector<int>
695SequentialPlacer::preferredGroupColumns(LogicalTileOp logicalTile,
696 const CoreGroups &groups) const {
697 auto group = groups.groupOf.find(logicalTile.getOperation());
698 if (group == groups.groupOf.end())
699 return {};
700 SmallVector<std::pair<int, int>> placedCols; // (column, members there)
701 int unplaced = 0;
702 for (auto member : groups.members[group->second]) {
703 auto placed = result.find(member.getOperation());
704 if (placed == result.end()) {
705 ++unplaced;
706 continue;
707 }
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});
712 else
713 ++entry->second;
714 }
715 llvm::stable_sort(placedCols, [](auto &a, auto &b) {
716 return a.second != b.second ? a.second > b.second : a.first < b.first;
717 });
718
719 SmallVector<int> cols;
720 for (auto &[col, n] : placedCols)
721 cols.push_back(col);
722 // compTiles is column-major, so this visits columns in order.
723 llvm::MapVector<int, int> freeCores;
724 for (TileID t : availability.compTiles)
725 ++freeCores[t.col];
726 for (auto &[col, n] : freeCores)
727 if (n >= unplaced && !llvm::is_contained(cols, col))
728 cols.push_back(col);
729 return cols;
730}
731
732LogicalResult SequentialPlacer::placeNonCoreLogicalTiles(
733 ArrayRef<LogicalTileOp> logicalTiles, const FlowMembership &flowIndex,
734 const llvm::DenseMap<Operation *, std::pair<int, int>>
735 &channelRequirements) {
736 // Sort the unplaced non-core LTOs by descending channel demand so the
737 // heaviest consumers (e.g. memtile joins that need many input channels)
738 // get first pick of physical tiles before lighter pass-through fifos
739 // crowd into the same column and leave no room.
740 SmallVector<LogicalTileOp> nonCoreOrdered;
741 for (auto logicalTile : logicalTiles) {
742 if (result.count(logicalTile.getOperation()))
743 continue;
744 AIETileType tileType = logicalTile.getTileType();
745 if (tileType == AIETileType::CoreTile ||
746 tileType == AIETileType::ShimPLTile)
747 continue;
748 nonCoreOrdered.push_back(logicalTile);
749 }
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;
754 };
755 return demand(a) > demand(b);
756 });
757
758 for (auto logicalTile : nonCoreOrdered) {
759 if (failed(placeNonCoreTileByCentroid(logicalTile, flowIndex,
760 channelRequirements)))
761 return failure();
762 }
763 return success();
764}
765
766int SequentialPlacer::PlacementContext::placementPriority(Operation *op) const {
767 int self = neighborDemand(op);
768 int best = 0;
769 forEachPeer(op, computePeerAdjacency,
770 [&](TileLike peer, bool /*thisIsFirst*/) {
771 best = std::max(best, neighborDemand(peer.getOperation()));
772 });
773 return std::max(self, best);
774}
775
776void SequentialPlacer::PlacementContext::reserveNeighborSlots(
777 Operation *placedOp, TileID at) {
778 if (neighborDemand(placedOp) <= 0)
779 return;
781 targetModel, at, [&](TileID nb) { reservedFor[nb].push_back(placedOp); });
782}
783
784bool SequentialPlacer::PlacementContext::isReservedForOther(
785 Operation *lto, TileID candidate) const {
786 auto it = reservedFor.find(candidate);
787 if (it == reservedFor.end())
788 return false;
789 for (Operation *owner : it->second) {
790 if (owner == lto)
791 continue; // The LTO's own slot reservation never counts as "other".
792 bool isPeer = false;
793 forEachPeer(lto, computePeerAdjacency,
794 [&](TileLike peer, bool /*thisIsFirst*/) {
795 if (peer.getOperation() == owner)
796 isPeer = true;
797 });
798 if (!isPeer)
799 return true;
800 }
801 return false;
802}
803
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);
812 };
813
814 // compTiles is sorted column-major top-to-bottom. For high-fanin LTOs
815 // (neighborDemand > 0) the placer needs an INTERIOR tile (with the most
816 // compute neighbors sharing its memory) so its compute-peer
817 // producers/consumers can sit around it. Reorder the candidate iteration
818 // for THIS LTO only to prefer high-neighbor-count rows first; LTOs with
819 // no neighbor demand fall through to the default column-major order so
820 // existing single-worker tests keep landing on (col, 2).
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) {
828 if (a.col != b.col)
829 return a.col < b.col;
830 int na = neighbors.lookup(a);
831 int nb = neighbors.lookup(b);
832 if (na != nb)
833 return na > nb;
834 return a.row < b.row;
835 });
836 } else if (!inputs.preferredCols.empty()) {
837 // Keep the LTO with its core group: preferred columns first, in
838 // preference order; the rest keep the column-major order after them.
839 auto rankOf = [&](TileID t) {
840 return std::distance(inputs.preferredCols.begin(),
841 llvm::find(inputs.preferredCols, t.col));
842 };
843 llvm::stable_sort(orderedCandidates, [&](TileID a, TileID b) {
844 return rankOf(a) < rankOf(b);
845 });
846 }
847
848 // Tiles past the budget come after it, so a pinned core exceeds the budget
849 // only when no tile within it passes a pass's checks; the strict passes see
850 // them before the last pass takes a tile a floating peer needs.
851 llvm::append_range(orderedCandidates, pastBudget);
852
853 // A candidate that leaves no free core tile for one of this LTO's
854 // unplaced shared-L1 peers is tried only in the final pass. Each peer
855 // claims its own tile; claiming greedily is exact when the peers share one
856 // candidate set, as one owner's consumers do.
857 auto leavesPeerRoom = [&](TileID candidate) {
858 llvm::DenseSet<TileID> claimed;
859 bool room = true;
860 forEachPeer(logicalTile.getOperation(), inputs.bufferAdjacency,
861 [&](TileLike peer, bool thisIsFirst) {
862 if (!room || resolvePeerPosition(peer, this->result))
863 return;
864 // thisIsFirst: this tile is the consumer, peer the owner.
865 auto free =
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));
870 });
871 room = free != availability.compTiles.end();
872 if (room)
873 claimed.insert(*free);
874 });
875 return room;
876 };
877
878 auto fitsColumnStreams = [&](TileID candidate) {
879 StreamDemand demand = streamDemand.lookup(logicalTile);
880 StreamDemand used = columnStreamsUsed.lookup(candidate.col);
881 auto incoming = columnIncomingFifos.find(candidate.col);
882 if (incoming != columnIncomingFifos.end())
883 for (Operation *fifo : incomingFifos.lookup(logicalTile))
884 demand.southIn -= incoming->second.contains(fifo);
885 // Measure the bottleneck at the bottom compute row, not at a candidate
886 // in the middle of the column. Overflow can still route via other columns.
887 int bottomRow = candidate.row;
888 while (bottomRow > 0 &&
889 targetModel->isCoreTile(candidate.col, bottomRow - 1))
890 --bottomRow;
891 return (!demand.southIn ||
892 used.southIn + demand.southIn <=
893 static_cast<int>(targetModel->getNumSourceSwitchboxConnections(
894 candidate.col, bottomRow, WireBundle::South))) &&
895 (!demand.southOut ||
896 used.southOut + demand.southOut <=
897 static_cast<int>(targetModel->getNumDestSwitchboxConnections(
898 candidate.col, bottomRow, WireBundle::South)));
899 };
900
901 // First prefer columns with stream capacity, then allow overloaded columns
902 // while preserving peer room and reservations. Relax those only as a last
903 // resort.
904 // Pass 0 tries first the tiles where a neighbouring configuration runs
905 // this core's program.
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;
912 });
913 });
914 for (int pass = 0; pass < 3; ++pass) {
915 for (const TileID &candidate :
916 pass == 0 ? sameProgramFirst : orderedCandidates) {
917 if (col && candidate.col != *col)
918 continue;
919 if (row && candidate.row != *row)
920 continue;
921 if (pass < 2 &&
922 (inputs.isReservedForOther(logicalTile.getOperation(), candidate) ||
923 !leavesPeerRoom(candidate)))
924 continue;
925 if (pass == 0 && (!fitsColumnStreams(candidate) ||
926 raisesStreamCuts(logicalTile, candidate)))
927 continue;
928 result.sawConstraintMatch = true;
929 if (!satisfiesAdjacency(logicalTile, candidate, inputs.bufferAdjacency,
930 inputs.bufferPred))
931 continue;
932 result.allConstraintMatchesFailedAdjacency = false;
933 if (!satisfiesAdjacency(logicalTile, candidate, inputs.cascadeAdjacency,
934 inputs.cascadePred))
935 continue;
936 if (!satisfiesAdjacency(logicalTile, candidate, inputs.sharedMemAdjacency,
937 inputs.sharedMemPred))
938 continue;
939 if (!satisfiesComputePeer(
940 logicalTile, candidate, inputs.computePeerAdjacency,
941 inputs.needNeighborIn, inputs.needNeighborOut)) {
942 result.computePeerWasCause = true;
943 continue;
944 }
945 if (!pinsAt.heldAt(candidate,
946 pinnedEnds.lookup(logicalTile.getOperation()))) {
947 if (!result.pinClash)
948 result.pinClash = candidate;
949 continue;
950 }
951 result.placement = candidate;
952 return result;
953 }
954 }
955 return result;
956}
957
958void SequentialPlacer::notePinClash(InFlightDiagnostic &diag,
959 LogicalTileOp logicalTile, TileID at) {
960 for (PinnedChannels::End end :
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)
966 continue;
967 auto &note = 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;
972 if (other) {
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");
976 } else if (claim) {
977 note << ", which another op holds";
978 diag.attachNote(claim->owner->getLoc()) << "held here";
979 }
980 return;
981 }
982}
983
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);
993 if (!held) {
994 llvm::stable_sort(
995 pins, [](const PinnedChannels::End &a, const PinnedChannels::End &b) {
996 return std::make_pair(a.sends, a.channel) <
997 std::make_pair(b.sends, b.channel);
998 });
999 [[maybe_unused]] bool reported = false;
1000 for (PinnedChannels::End end : pins) {
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");
1009 reported = true;
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";
1017 reported = true;
1018 }
1019 }
1020 assert(reported &&
1021 "heldAt reports only a clash clashWith or claimWith finds");
1022 return failure();
1023 }
1024 inChannels -= held->first;
1025 outChannels -= held->second;
1026
1027 if (!hasAvailableChannels(tile, inChannels, outChannels, logicalTile) &&
1028 !fitsSharingShim(tile, logicalTile, {inChannels, outChannels})) {
1029 // The same capacity as hasAvailableChannels, so the message matches it.
1030 auto [maxIn, maxOut] = getDMACapacity(*targetModel, tile);
1031 int availIn = maxIn - availability.inputChannelsUsed[tile];
1032 int availOut = maxOut - availability.outputChannelsUsed[tile] -
1033 overlayWith(tile, logicalTile).channels;
1034
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);
1041 overlay.channels || !overlay.fits)
1042 diag.attachNote()
1043 << "the control overlay "
1044 << (overlay.fits ? "takes one of its output channels"
1045 : "has no output channel here it may take or "
1046 "share")
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)";
1053 return failure();
1054 }
1055
1056 // Its pins and named channels first: they decide where the overlay sits.
1057 recordStreamAndBdUsage(logicalTile, tile);
1058 if (inChannels > 0)
1059 updateChannelUsage(tile, DmaDir::In, inChannels);
1060 if (outChannels > 0)
1061 updateChannelUsage(tile, DmaDir::Out, outChannels);
1062 recordShimEnds(tile, logicalTile);
1063
1064 return success();
1065}
1066
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;
1073
1074 // Build map of ObjectFifo name -> CreateOp for link processing
1075 llvm::StringMap<ObjectFifoCreateOp> fifoNameToOp;
1076 for (auto ofOp : objectFifos) {
1077 fifoNameToOp[ofOp.getSymName()] = ofOp;
1078 }
1079
1080 // A link's tile is the one producing its dest fifos (each fifo has one
1081 // producer). The link loop below credits it with (#sources input + #dests
1082 // output), so the per-fifo loop skips the side of each linked fifo on a tile
1083 // of a link reading it, and only those: a linked source fifo can have other
1084 // consumers, such as a shim that also drains it, and those still need their
1085 // own channels.
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();
1097 }
1098 linkTileOf[linkOp.getOperation()] = linkTileOp;
1099 if (!linkTileOp)
1100 continue;
1101 for (auto srcFifoAttr : linkOp.getFifoIns())
1102 if (auto sym = dyn_cast<FlatSymbolRefAttr>(srcFifoAttr))
1103 linkTilesOfSource[sym.getValue()].push_back(linkTileOp);
1104 }
1105
1106 // A tile op's ends that pin one channel pay for it once; those of tile ops
1107 // placed together meet in pinsAt.
1109 pinsAt = PinnedChannelUse(pinnedRule);
1110 pinnedEnds.clear();
1111 llvm::DenseSet<unsigned> counted;
1112 auto drawsChannel = [&](ObjectFifoCreateOp fifo,
1113 std::optional<unsigned> consumer, Operation *tile) {
1114 std::optional<PinnedChannels::End> end =
1115 PinnedChannels::endOf(fifo, consumer);
1116 if (!end)
1117 return true;
1118 pinnedEnds[tile].push_back(*end);
1119 return counted.insert(pinnedRule.share(*end, rank)).second;
1120 };
1121 // An end takes a channel of its own when the fifo moves by DMA: a shim's
1122 // unless it is a PLIO, any other one the split gives a DMA end.
1123 auto dmaEnd = [](ObjectFifoCreateOp fifo, std::optional<unsigned> consumer,
1124 Operation *tile) {
1125 auto like = dyn_cast_or_null<TileLike>(tile);
1126 return like && like.isShimTile() ? !fifo.getPlio()
1127 : fifo.plannedDmaEnd(consumer).has_value();
1128 };
1129
1130 // Count channels for every ObjectFifo, omitting only the link-tile side of
1131 // linked fifos. The off-link-tile endpoint still needs DMA: a shim that
1132 // produces a linked source fifo consumes an MM2S channel; a core that
1133 // consumes a linked dest fifo consumes an S2MM channel.
1134 for (auto ofOp : objectFifos) {
1135 SmallVector<Operation *> linkConsumers =
1136 linkTilesOfSource.lookup(ofOp.getSymName());
1137 bool skipProducerSide = linkedAsDest.count(ofOp.getSymName());
1138
1139 Value producerTile = ofOp.getProducerTile();
1140 auto *producerOp = producerTile.getDefiningOp();
1141 auto producerLogicalTile = dyn_cast_or_null<LogicalTileOp>(producerOp);
1142
1143 // Check if ANY consumer is a different tile type (needs DMA channel)
1144 bool producerNeedsDMA = false;
1145
1146 for (auto [consumerIndex, consumerTile] :
1147 llvm::enumerate(ofOp.getConsumerTiles())) {
1148 auto *consumerOp = consumerTile.getDefiningOp();
1149 auto consumerLogicalTile = dyn_cast_or_null<LogicalTileOp>(consumerOp);
1150
1151 // Skip a core-to-core fifo neighbor memory may carry instead of DMA: a
1152 // compute peer (buildComputePeerAdjacency), one end placed or both
1153 // not. One that moves by DMA wherever it sits (dmaReason) is counted
1154 // here.
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 &&
1161 !ofOp.dmaReason())
1162 continue;
1163
1164 // Linked consumers and shared channels are counted separately.
1165 if (consumerOp && !llvm::is_contained(linkConsumers, consumerOp) &&
1166 dmaEnd(ofOp, consumerIndex, consumerOp) &&
1167 drawsChannel(ofOp, consumerIndex, consumerOp))
1168 channelRequirements[consumerOp].first++; // input++
1169
1170 producerNeedsDMA = true;
1171 }
1172
1173 // Producer needs ONE output channel if any consumer needs DMA (unless the
1174 // producer IS the link tile of an outgoing linked dest fifo, or it shares
1175 // an already-counted shared channel).
1176 if (producerNeedsDMA && producerOp && !skipProducerSide &&
1177 dmaEnd(ofOp, std::nullopt, producerOp) &&
1178 drawsChannel(ofOp, std::nullopt, producerOp))
1179 channelRequirements[producerOp].second++; // output++
1180 }
1181
1182 // For linked ObjectFifos, count channels based on the link structure
1183 // Link tiles need channels for all sources and destinations
1184 for (auto linkOp : objectFifoLinks) {
1185
1186 Operation *linkTileOp = linkTileOf.lookup(linkOp.getOperation());
1187 if (!linkTileOp)
1188 continue;
1189
1190 // Link tile needs one input channel per source ObjectFifo and one output
1191 // channel per dest ObjectFifo, except that a time link's turns share one,
1192 // and so do ends pinning one channel; their pins hold it there.
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();
1200 if (!fifo) {
1201 ++(input ? numInputChannels : numOutputChannels);
1202 continue;
1203 }
1204 if (!input) {
1205 numOutputChannels += drawsChannel(fifo, std::nullopt, linkTileOp);
1206 continue;
1207 }
1208 for (unsigned index = 0, e = fifo.getConsumerTiles().size(); index < e;
1209 ++index)
1210 if (fifo.getConsumerLink(index) == linkOp)
1211 numInputChannels += drawsChannel(fifo, index, linkTileOp);
1212 }
1213 if (linkOp.isMerge())
1214 numInputChannels = 1;
1215 if (linkOp.isDispatch())
1216 numOutputChannels = 1;
1217
1218 channelRequirements[linkTileOp].first += numInputChannels;
1219 channelRequirements[linkTileOp].second += numOutputChannels;
1220 }
1221
1222 return channelRequirements;
1223}
1224
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))
1231 continue;
1232 auto &[in, out] = requirements[tile];
1233 for (bool coreDrains : {true, false}) {
1234 int &need = coreDrains ? in : out;
1235 auto [inBudget, outBudget] =
1236 getDMACapacity(*targetModel, tile.getCanonicalTileID());
1237 int budget = coreDrains ? inBudget : outBudget;
1238 if (need <= budget)
1239 continue;
1240 // Peers with coordinates are one mem tile however many ops name it.
1241 llvm::MapVector<std::pair<Operation *, std::optional<TileID>>,
1242 SmallVector<ObjectFifoCreateOp>>
1243 byTile;
1244 for (ObjectFifoCreateOp fifo : objectFifos) {
1245 if (!fifo.canTakeTurns())
1246 continue;
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())
1252 continue;
1253 std::optional<int> col = peer.tryGetCol(), row = peer.tryGetRow();
1254 if (col && row)
1255 byTile[{nullptr, TileID{*col, *row}}].push_back(fifo);
1256 else
1257 byTile[{peer, std::nullopt}].push_back(fifo);
1258 }
1259 for (auto &[peer, fifos] : byTile) {
1260 if (fifos.size() < 2 || need <= budget)
1261 continue;
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)
1267 : std::nullopt));
1268 }
1269 CoreTurns turns;
1270 std::string reason;
1271 if (succeeded(turns.read(core, names, coreDrains, reason)) &&
1272 turns.keepsUp(depths))
1273 need -= static_cast<int>(fifos.size()) - 1;
1274 }
1275 }
1276 }
1277}
1278
1279// Walk view-like aliasing memref ops back to the underlying BufferOp.
1280static BufferOp traceToBuffer(Value val) {
1281 for (Operation *op = val.getDefiningOp(); op;) {
1282 if (auto buf = dyn_cast<BufferOp>(op))
1283 return buf;
1284 if (auto view = dyn_cast<ViewLikeOpInterface>(op)) {
1285 val = view.getViewSource();
1286 op = val.getDefiningOp();
1287 continue;
1288 }
1289 return nullptr;
1290 }
1291 return nullptr;
1292}
1293
1294static std::optional<TileID>
1295resolvePeerPosition(TileLike peer, const PlacementResult &placed) {
1296 if (!peer)
1297 return std::nullopt;
1298 auto it = placed.find(peer.getOperation());
1299 if (it != placed.end())
1300 return it->second;
1301 auto col = peer.tryGetCol();
1302 auto row = peer.tryGetRow();
1303 if (col && row)
1304 return TileID{*col, *row};
1305 return std::nullopt;
1306}
1307
1308Placer::Adjacency SequentialPlacer::buildBufferAdjacency(
1309 ArrayRef<LogicalTileOp> logicalTiles,
1310 ArrayRef<ObjectFifoAllocateOp> allocates) {
1311 Adjacency adjacency;
1312 // One edge per (user, owner) pair: a duplicate would book a second free
1313 // tile for the same peer in leavesPeerRoom.
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);
1318 };
1319 // An allocated fifo's objects live in the delegate's memory, which each of
1320 // its ends then reaches as it would a buffer the delegate owns.
1321 for (auto alloc : allocates) {
1322 auto delegate =
1323 dyn_cast_or_null<TileLike>(alloc.getDelegateTile().getDefiningOp());
1324 ObjectFifoCreateOp fifo = alloc.getObjectFifo();
1325 if (!delegate || !fifo || delegate.getTileType() != AIETileType::CoreTile)
1326 continue;
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);
1334 }
1335 }
1336 for (auto consumer : logicalTiles) {
1337 if (consumer.getTileType() != AIETileType::CoreTile)
1338 continue;
1339 CoreOp core = nullptr;
1340 for (Operation *user : consumer.getResult().getUsers())
1341 if (auto c = dyn_cast<CoreOp>(user)) {
1342 core = c;
1343 break;
1344 }
1345 if (!core)
1346 continue;
1347
1348 core.getBody().walk([&](Operation *op) {
1349 for (Value operand : op->getOperands()) {
1350 BufferOp buf = traceToBuffer(operand);
1351 if (!buf)
1352 continue;
1353 auto owner = dyn_cast_or_null<TileLike>(buf.getTile().getDefiningOp());
1354 if (owner && owner.getOperation() != consumer.getOperation())
1355 addOnce(TileLike(consumer), owner);
1356 }
1357 });
1358 }
1359 return adjacency;
1360}
1361
1362Placer::Adjacency
1363Placer::buildCascadeAdjacency(ArrayRef<CascadeFlowOp> cascadeFlows) {
1364 Adjacency adjacency;
1365 for (auto cf : cascadeFlows) {
1366 TileLike src = cf.getSourceTileLike();
1367 TileLike dst = cf.getDestTileLike();
1368 if (!src || !dst)
1369 continue;
1370 adjacency.addEdge(src, dst);
1371 }
1372 return adjacency;
1373}
1374
1376Placer::buildComputePeerAdjacency(ArrayRef<ObjectFifoCreateOp> objectFifos) {
1377 Adjacency adjacency;
1378 for (auto ofOp : objectFifos) {
1379 auto producer =
1380 dyn_cast_or_null<TileLike>(ofOp.getProducerTile().getDefiningOp());
1381 if (!producer || producer.getTileType() != AIETileType::CoreTile)
1382 continue;
1383 // Only a fifo neighbor memory may carry is a compute peer.
1384 if (ofOp.dmaReason())
1385 continue;
1386 for (Value consumerVal : ofOp.getConsumerTiles()) {
1387 auto consumer = dyn_cast_or_null<TileLike>(consumerVal.getDefiningOp());
1388 if (!consumer || consumer.getTileType() != AIETileType::CoreTile)
1389 continue;
1390 // Self-loops live entirely in the tile's own L1 and consume no DMA
1391 // channel, so they should not push the LTO toward a neighbor-heavy
1392 // placement. Two physical cores leave nothing to place.
1393 if (producer.getOperation() == consumer.getOperation() ||
1394 (!isa<LogicalTileOp>(producer.getOperation()) &&
1395 !isa<LogicalTileOp>(consumer.getOperation())))
1396 continue;
1397 adjacency.addEdge(producer, consumer);
1398 }
1399 }
1400 return adjacency;
1401}
1402
1404Placer::buildSharedMemAdjacency(ArrayRef<ObjectFifoCreateOp> objectFifos) {
1405 Adjacency adjacency;
1406 for (auto ofOp : objectFifos)
1407 if (ofOp.forcesSharedMemory() && ofOp.getConsumerTiles().size() == 1)
1408 adjacency.addEdgeFromValues(ofOp.getProducerTile(),
1409 ofOp.getConsumerTiles()[0]);
1410 return adjacency;
1411}
1412
1413bool SequentialPlacer::satisfiesAdjacency(
1414 LogicalTileOp logicalTile, TileID candidate, const Adjacency &adjacency,
1415 llvm::function_ref<bool(TileID firstPos, TileID secondPos)> pred) const {
1416 bool ok = true;
1417 forEachPeer(logicalTile.getOperation(), adjacency,
1418 [&](TileLike peer, bool thisIsFirst) {
1419 if (!ok)
1420 return;
1421 auto peerPos = resolvePeerPosition(peer, result);
1422 if (!peerPos)
1423 return;
1424 TileID firstPos = thisIsFirst ? candidate : *peerPos;
1425 TileID secondPos = thisIsFirst ? *peerPos : candidate;
1426 if (!pred(firstPos, secondPos))
1427 ok = false;
1428 });
1429 return ok;
1430}
1431
1432LogicalResult SequentialPlacer::enforceAdjacency(LogicalTileOp logicalTile,
1433 TileID tile,
1434 const AdjacencyKind &kind) {
1435 if (satisfiesAdjacency(logicalTile, tile, kind.adjacency, kind.pred))
1436 return success();
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;
1442 return failure();
1443}
1444
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);
1455 availability.removeTile(tile, AIETileType::CoreTile);
1456 ctx.reserveNeighborSlots(logicalTile.getOperation(), tile);
1457 // A placed compute peer this core is not beside moves the fifo by DMA,
1458 // on a channel of its own tile.
1460 logicalTile.getOperation(), ctx.computePeerAdjacency,
1461 [&](TileLike peer, bool thisIsFirst) {
1462 auto placed = dyn_cast<TileOp>(peer.getOperation());
1463 if (placed &&
1464 !isSharedComputeMemory(*targetModel, placed.getTileID(), tile))
1465 updateChannelUsage(placed.getTileID(),
1466 thisIsFirst ? DmaDir::In : DmaDir::Out, 1);
1467 });
1468 }
1469}
1470
1471std::pair<int, int>
1472SequentialPlacer::totalComputePeers(Operation *op, const Adjacency &adjacency) {
1473 int in = 0, out = 0;
1474 // Compute-peer convention: edge.first is the producer (OUT for `op`),
1475 // edge.second is the consumer (IN for `op`).
1476 forEachPeer(op, adjacency, [&](TileLike /*peer*/, bool thisIsFirst) {
1477 if (thisIsFirst)
1478 ++out;
1479 else
1480 ++in;
1481 });
1482 return {in, out};
1483}
1484
1485bool SequentialPlacer::satisfiesComputePeer(
1486 LogicalTileOp logicalTile, TileID candidate,
1487 const Adjacency &computePeerAdjacency,
1488 const llvm::DenseMap<Operation *, int> &needNeighborIn,
1489 const llvm::DenseMap<Operation *, int> &needNeighborOut) const {
1490 // No compute-peer edges => the compute-peer DMA budget constraint is
1491 // vacuous for this LTO. (Phase 2c can still populate a non-zero
1492 // needNeighborIn/Out for a tile whose non-peer channel count exceeds
1493 // its DMA budget, but no neighbor placement can fix that and the
1494 // channel validator emits the right error later.)
1495 if (!computePeerAdjacency.hasEdges(logicalTile.getOperation()))
1496 return true;
1497
1498 // Self side: count placed peers that would land non-neighbor of
1499 // candidate, and reject if the count exceeds the slack budget.
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);
1505 if (!peerPos)
1506 return;
1507 bool isNeighbor =
1508 isSharedComputeMemory(*targetModel, candidate, *peerPos);
1509 bool thisIsConsumer = !thisIsFirst;
1510 if (isNeighbor) {
1511 if (thisIsConsumer)
1512 ++selfNeighborIn;
1513 else
1514 ++selfNeighborOut;
1515 } else {
1516 if (thisIsConsumer)
1517 ++selfNonNeighborIn;
1518 else
1519 ++selfNonNeighborOut;
1520 }
1521 });
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)
1529 return false;
1530 if (selfNonNeighborOut > selfSlackOut)
1531 return false;
1532
1533 // Forward-look: even if no placed peer violates slack at this
1534 // candidate, future peers still to be placed must land on a physical
1535 // compute neighbor of candidate. Count candidate's free shared-L1
1536 // compute neighbors (N, S, and the checkerboard W neighbor on AIE2)
1537 // and reject if the remaining demand exceeds that count. A free slot
1538 // can host an IN-peer OR an OUT-peer (not both); the sum-check is a
1539 // conservative approximation.
1540 if (selfNeedIn > 0 || selfNeedOut > 0) {
1541 int freeNeighborSlots = 0;
1542 forEachMemAffinityNeighbor(*targetModel, candidate, [&](TileID nb) {
1543 if (availability.compTilesSet.contains(nb))
1544 ++freeNeighborSlots;
1545 });
1546 int remainingInNeed = std::max(0, selfNeedIn - selfNeighborIn);
1547 int remainingOutNeed = std::max(0, selfNeedOut - selfNeighborOut);
1548 if (remainingInNeed + remainingOutNeed > freeNeighborSlots)
1549 return false;
1550 }
1551
1552 // Symmetric side: for each already-placed compute peer p, placing
1553 // logicalTile at candidate adds one non-neighbor entry to p's count if
1554 // candidate isn't a neighbor of p. Re-derive p's count using the current
1555 // `result` plus this candidate, then check p's slack.
1556 bool symmetricOk = true;
1558 logicalTile.getOperation(), computePeerAdjacency,
1559 [&](TileLike peer, bool thisIsFirst) {
1560 if (!symmetricOk)
1561 return;
1562 auto peerLTO = dyn_cast_or_null<LogicalTileOp>(peer.getOperation());
1563 auto peerPos = resolvePeerPosition(peer, result);
1564 if (!peerPos)
1565 return;
1566 // A placed core keeps no neighbor budget: apart from it, the fifo
1567 // takes one more DMA channel of its tile, which must be free.
1568 if (!peerLTO) {
1569 auto [maxIn, maxOut] = getDMACapacity(*targetModel, *peerPos);
1570 if (!isSharedComputeMemory(*targetModel, *peerPos, candidate) &&
1571 (thisIsFirst
1572 ? availability.inputChannelsUsed.lookup(*peerPos) >= maxIn
1573 : availability.outputChannelsUsed.lookup(*peerPos) >=
1574 maxOut))
1575 symmetricOk = false;
1576 return;
1577 }
1578 // From peer's POV, logicalTile is one of peer's compute peers.
1579 // If logicalTile is the consumer here (thisIsFirst == false),
1580 // peer is the producer and logicalTile sits on peer's OUT side.
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;
1589
1590 // Count peer's currently placed non-neighbor peers in this direction.
1591 int peerNonNeighborDir = 0;
1593 peerLTO.getOperation(), computePeerAdjacency,
1594 [&](TileLike peerPeer, bool peerLTOIsFirst) {
1595 // peerLTO is the consumer of this edge when it sits on
1596 // edge.second (compute-peer convention is producer=first,
1597 // consumer=second). logicalIsPeerOut selects peer's OUT
1598 // edges (peer = producer), which is the opposite role.
1599 bool peerIsConsumerHere = !peerLTOIsFirst;
1600 if (logicalIsPeerOut == peerIsConsumerHere)
1601 return;
1602 if (peerPeer.getOperation() == logicalTile.getOperation()) {
1603 // For the edge currently being decided, score candidate
1604 // against peerPos.
1605 if (!isSharedComputeMemory(*targetModel, *peerPos, candidate))
1606 ++peerNonNeighborDir;
1607 return;
1608 }
1609 auto pp = resolvePeerPosition(peerPeer, result);
1610 if (!pp)
1611 return;
1612 if (!isSharedComputeMemory(*targetModel, *peerPos, *pp))
1613 ++peerNonNeighborDir;
1614 });
1615 if (peerNonNeighborDir > peerSlackDir)
1616 symmetricOk = false;
1617 });
1618 return symmetricOk;
1619}
1620
1621void SequentialPlacer::attachPeerNotes(
1622 InFlightDiagnostic &diag, LogicalTileOp logicalTile,
1623 const Adjacency &adjacency,
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);
1629 if (!peerPos) {
1630 ++unplacedCount;
1631 return;
1632 }
1633 diag.attachNote(peer.getLoc())
1634 << labelPeer(thisIsFirst) << " peer placed at ("
1635 << peerPos->col << ", " << peerPos->row << ")";
1636 });
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)";
1642}
1643
1644Placer::Adjacency
1645Placer::buildObjectFifoAdjacency(ArrayRef<ObjectFifoCreateOp> objectFifos) {
1646 Adjacency adjacency;
1647 for (auto ofOp : objectFifos)
1648 for (Value consumer : ofOp.getConsumerTiles())
1649 adjacency.addEdgeFromValues(ofOp.getProducerTile(), consumer);
1650 return adjacency;
1651}
1652
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()});
1660 ShareableShimEnds ends;
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}))
1667 return nullptr;
1668 return lt.getOperation();
1669 };
1670 for (auto fifo : objectFifos) {
1671 endRank[fifo.getSymNameAttr()] = rank.lookup(fifo);
1672 if (Operation *lt =
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());
1678 }
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)
1682 continue;
1683 ShimSide &side =
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);
1691 }
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))
1698 continue;
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));
1706 }
1707 // ShimTransferSpans::plan first-fits in the order it is given ends and
1708 // shared channels, so give them in structural and channel order.
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);
1712 });
1713 for (auto &[tile, sides] : entries) {
1714 for (ShimSide &side : sides) {
1715 llvm::stable_sort(side.ends, [&](StringAttr a, StringAttr b) {
1716 return endRank.lookup(a) < endRank.lookup(b);
1717 });
1718 llvm::stable_sort(side.shared, [](const auto &a, const auto &b) {
1719 return a.first < b.first;
1720 });
1721 }
1722 ends.insert({tile, std::move(sides)});
1723 }
1724 return ends;
1725}
1726
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);
1736 }
1737 llvm::append_range(ends, extra);
1738 SmallVector<ShimTransferSpans::SharedChannel> shared;
1739 for (const ShimSide *side : sides)
1740 for (auto &[channel, listed] : side->shared)
1741 shared.emplace_back(listed, llvm::is_contained(pinned, channel));
1742 ShimTransferSpans::Plan plan = spans.plan(ends, ends, shared);
1743 return static_cast<int>(ends.size() - plan.groups.size());
1744}
1745
1747 DeviceOp device, ArrayRef<ObjectFifoCreateOp> objectFifos,
1748 ArrayRef<DMAChannelAnalysis::ChannelClaim> claims,
1749 const DenseMap<Operation *, unsigned> &rank,
1750 const DenseMap<Operation *, Operation *> &routeKeys) {
1751 claimsOf.clear();
1752 for (const DMAChannelAnalysis::ChannelClaim &claim : claims)
1753 claimsOf[claim.tile.getDefiningOp()].push_back(claim);
1756 collectShareableShimEnds(device, objectFifos, rank, routeKeys);
1757 collectOverlayUses(device);
1758 // Gates only let receiving ends share, so without any to share the proofs
1759 // are never read.
1760 bool receiving = llvm::any_of(shareableShimEnds, [](const auto &entry) {
1761 const ShimSide &side = entry.second[0];
1762 return !side.ends.empty() || !side.shared.empty();
1763 });
1764 // Without gates the spans keep no per-sequence bytes, which ddrGroups
1765 // reads; empty ones let no receiving end share either.
1766 shimSpans.emplace(
1767 device,
1768 [&](StringAttr symbol) {
1769 return ShimTransferSpans::endOf(device, symbol);
1770 },
1771 receiving ? provenShimGates(device) : ShimTransferSpans::Gates(),
1773
1774 ddrGroups.clear();
1775 ddrGroupsOf.clear();
1776 ddrShimColumns = 0;
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);
1781 });
1782 for (unsigned seq = 0, e = shimSpans->sequences(); seq < e; ++seq)
1783 for (int dir : {0, 1}) {
1784 DdrGroup group;
1785 SmallVector<StringAttr> ends;
1786 SmallVector<std::optional<int64_t>> bytes;
1787 for (auto &[tile, sides] : shareableShimEnds)
1788 for (StringAttr end : sides[dir].ends)
1789 if (shimSpans->names(seq, end)) {
1790 group.tiles.push_back(tile);
1791 ends.push_back(end);
1792 bytes.push_back(shimSpans->bytes(seq, end));
1793 }
1794 if (group.tiles.size() < 2)
1795 continue;
1796 bool dynamic = llvm::is_contained(bytes, std::nullopt);
1797 int64_t total = 0;
1798 for (std::optional<int64_t> b : bytes)
1799 total += b.value_or(0);
1800 for (std::optional<int64_t> b : bytes)
1801 group.weights.push_back(
1802 dynamic || total <= 0
1803 ? 1
1804 : std::max<int64_t>(1, (b.value_or(0) * 65536 + total / 2) /
1805 total));
1806 for (StringAttr a : ends) {
1807 llvm::BitVector &together = group.together.emplace_back(ends.size());
1808 for (auto [j, b] : llvm::enumerate(ends))
1809 if (a != b && !shimSpans->apart(a, b))
1810 together.set(j);
1811 }
1812 for (Operation *tile : group.tiles) {
1813 SmallVector<unsigned> &groups = ddrGroupsOf[tile];
1814 if (groups.empty() || groups.back() != ddrGroups.size())
1815 groups.push_back(ddrGroups.size());
1816 }
1817 ddrGroups.push_back(std::move(group));
1818 }
1819}
1820
1821int64_t
1822Placer::ddrSpread(function_ref<std::optional<int>(Operation *)> columnOf,
1823 int weight) const {
1824 int64_t spread = 0;
1825 for (const DdrGroup &group : ddrGroups)
1826 spread += ddrGroupSpread(group, columnOf, weight);
1827 return spread;
1828}
1829
1830int64_t
1832 function_ref<std::optional<int>(Operation *)> columnOf,
1833 int weight) const {
1834 SmallVector<std::optional<int>> cols =
1835 llvm::map_to_vector(group.tiles, columnOf);
1836 int64_t load = 0, sameColumn = 0;
1837 int placed = 0;
1838 for (auto [i, col] : llvm::enumerate(cols)) {
1839 if (!col)
1840 continue;
1841 ++placed;
1842 load += group.weights[i];
1843 sameColumn += group.weights[i] * group.weights[i];
1844 for (size_t j = i + 1; j < cols.size(); ++j)
1845 if (cols[j] == col && group.together[i].test(j))
1846 sameColumn += 2 * group.weights[i] * group.weights[j];
1847 }
1848 if (placed < 2)
1849 return 0;
1850 int64_t spreadOver = std::min(ddrShimColumns, placed);
1851 return weight * (spreadOver * sameColumn - load * load) / (load * load);
1852}
1853
1854std::optional<Placer::PinnedChannels::End>
1855Placer::PinnedChannels::endOf(ObjectFifoCreateOp fifo,
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;
1862 Value tile =
1863 consumer ? fifo.getConsumerTiles()[*consumer] : fifo.getProducerTile();
1864 auto offCore = [](Value end) {
1865 return cast<TileLike>(end.getDefiningOp()).getTileType() !=
1866 AIETileType::CoreTile;
1867 };
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};
1871}
1872
1873std::optional<std::string> Placer::PinnedChannels::whyApart(End a,
1874 End b) const {
1875 if (a.sends) {
1876 for (ObjectFifoCreateOp fifo : {a.fifo, b.fifo}) {
1877 auto tile = cast<TileLike>(fifo.getProducerTile().getDefiningOp());
1878 if (tile.isShimTile())
1879 continue;
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");
1883 }
1884 if (!isPacketSwitched(a.fifo.packetHeader(), packetSwitched) ||
1885 !isPacketSwitched(b.fifo.packetHeader(), packetSwitched))
1886 return std::string("a shared channel carries both at once, which only "
1887 "packet-switched routes tell apart");
1888 // A core's sharers each get push_queue (sharesSendChannel).
1889 for (ObjectFifoCreateOp fifo : {a.fifo, b.fifo})
1890 if (std::optional<StringRef> why =
1891 cast<TileLike>(fifo.getProducerTile().getDefiningOp())
1892 .isShimTile()
1893 ? std::nullopt
1894 : fifo.pushQueueRefusal())
1895 return "@" + fifo.getSymName().str() + "'s " + why->str();
1896 } else {
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()))
1902 return why->str();
1903 }
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;
1911}
1912
1913unsigned
1915 const DenseMap<Operation *, unsigned> &rank) {
1916 auto key =
1917 std::make_tuple(end.tile, end.channel, static_cast<int>(end.sends));
1918 auto &[before, number] = taken
1919 .try_emplace(key, SmallVector<End, 2>{},
1920 static_cast<unsigned>(taken.size()))
1921 .first->second;
1922 for (End other : before) {
1923 if (!end.movesByDma || !other.movesByDma)
1924 continue;
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;
1932 diagnosed = true;
1933 }
1934 }
1935 before.push_back(end);
1936 return number;
1937}
1938
1940 End end, const DMAChannelAnalysis::ChannelClaim &claim) const {
1941 auto alloc = dyn_cast_or_null<ShimDMAAllocationOp>(claim.owner);
1942 if (!alloc)
1943 return false;
1944 auto allowed =
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();
1949 }))
1950 return false;
1951 return end.sends ? isPacketSwitched(end.fifo.packetHeader(), packetSwitched)
1952 : end.fifo.getOutOfOrder();
1953}
1954
1956 TileID at, const DMAChannelAnalysis::ChannelClaim &claim, int sign) {
1957 auto key =
1958 std::make_tuple(at.col, at.row, claim.channel,
1959 static_cast<int>(claim.dir == DMAChannelDir::MM2S));
1960 auto &claims = claimed[key];
1961 if (sign > 0) {
1962 claims.push_back(claim);
1963 return;
1964 }
1965 auto *found =
1966 llvm::find_if(claims, [&](const DMAChannelAnalysis::ChannelClaim &c) {
1967 return c.owner == claim.owner;
1968 });
1969 assert(found != claims.end() && "removing a claim never placed");
1970 claims.erase(found);
1971 if (claims.empty())
1972 claimed.erase(key);
1973}
1974
1975std::optional<DMAChannelAnalysis::ChannelClaim>
1977 const PinnedChannels::End &end) const {
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;
1982 for (const DMAChannelAnalysis::ChannelClaim &claim : it->second)
1983 if (!rule->sharesClaim(end, claim))
1984 return claim;
1985 return std::nullopt;
1986}
1987
1989 int sign) {
1990 auto key =
1991 std::make_tuple(at.col, at.row, end.channel, static_cast<int>(end.sends));
1992 if (sign > 0) {
1993 auto &ends = placed[key];
1994 ends.push_back(end);
1995 return ends.size() == 1 ? 1 : 0;
1996 }
1997 auto it = placed.find(key);
1998 assert(it != placed.end() && "removing an end never placed");
1999 auto *found = llvm::find_if(it->second, [&](const PinnedChannels::End &e) {
2000 return e.fifo == end.fifo && e.consumer == end.consumer;
2001 });
2002 assert(found != it->second.end() && "removing an end never placed");
2003 it->second.erase(found);
2004 if (!it->second.empty())
2005 return 0;
2006 placed.erase(it);
2007 return -1;
2008}
2009
2011 auto claimsClash = [](ArrayRef<DMAChannelAnalysis::ChannelClaim> claims) {
2012 return llvm::any_of(claims,
2014 return claim.tile != claims.front().tile;
2015 });
2016 };
2017 int count = 0;
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;
2022 ++it) {
2023 const auto &ends = it->second;
2024 bool clash = false;
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) ||
2032 llvm::any_of(ends, [&](const PinnedChannels::End &end) {
2033 return llvm::any_of(
2034 held->second,
2036 return !rule->sharesClaim(end, claim);
2037 });
2038 });
2039 count += clash;
2040 }
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;
2045 ++it)
2046 count += !placed.count(it->first) && claimsClash(it->second);
2047 return count;
2048}
2049
2050std::optional<Placer::PinnedChannels::End>
2052 const PinnedChannels::End &end) const {
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;
2057 for (const PinnedChannels::End &other : it->second)
2058 if (other.tile != end.tile && rule->whyApart(end, other))
2059 return other;
2060 return std::nullopt;
2061}
2062
2064 bool sends) const {
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;
2070 ++it)
2071 if (std::get<3>(it->first) == static_cast<int>(sends))
2072 channels.push_back(std::get<2>(it->first));
2073 return channels;
2074}
2075
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;
2083 ++it)
2084 if (std::get<3>(it->first))
2085 llvm::append_range(sending[std::get<2>(it->first)], it->second);
2086 return sending;
2087}
2088
2089std::optional<std::pair<Operation *, std::pair<int, int>>>
2090Placer::namedClash(Operation *tile, ArrayRef<Operation *> others) const {
2091 auto mine = namedChannels.find(tile);
2092 if (mine == namedChannels.end())
2093 return std::nullopt;
2094 for (Operation *other : others) {
2095 auto theirs = namedChannels.find(other);
2096 if (other == tile || theirs == namedChannels.end())
2097 continue;
2098 for (std::pair<int, int> named : mine->second)
2099 if (llvm::is_contained(theirs->second, named))
2100 return std::make_pair(other, named);
2101 }
2102 return std::nullopt;
2103}
2104
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 =
2112 tile->emitError()
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;
2121 return diag;
2122}
2123
2124void Placer::collectOverlayUses(DeviceOp device) {
2126 auto module = device->getParentOfType<ModuleOp>();
2127 if (!controlOverlay || !module)
2128 return;
2129 for (DeviceOp other : module.getOps<DeviceOp>()) {
2130 if (other == device || other.getDevice() != device.getDevice() ||
2131 !getsColumnControlOverlay(other, true))
2132 continue;
2134 for (auto fifo : other.getOps<ObjectFifoCreateOp>()) {
2135 std::optional<PinnedChannels::End> end =
2136 PinnedChannels::endOf(fifo, std::nullopt);
2137 if (!end)
2138 continue;
2139 auto tile = dyn_cast_or_null<TileOp>(end->tile);
2140 if (!tile || !tile.isShimNOCorPLTile())
2141 continue;
2142 if (isPacketSwitched(fifo.packetHeader(), packetSwitched))
2143 uses.packetEnds[{tile, end->channel}].push_back(fifo.getSymNameAttr());
2144 else
2145 uses.circuits[tile].insert(end->channel);
2146 }
2147 for (auto &[tile, channels] : uses.circuits)
2148 if (isa<TileOp>(tile))
2149 overlayUses.circuits[tile].insert(channels.begin(), channels.end());
2150 for (auto &[key, ends] : uses.packetEnds)
2151 if (isa<TileOp>(key.first))
2152 llvm::append_range(overlayUses.packetEnds[key], ends);
2153 for (auto &[key, flows] : uses.packetFlows)
2154 if (isa<TileOp>(key.first))
2155 overlayUses.packetFlows[key] += flows;
2156 }
2157}
2158
2159SmallVector<Operation *> Placer::overlayTileOps() const {
2160 llvm::SetVector<Operation *> tiles;
2161 for (auto &[tile, channels] : overlayUses.circuits)
2162 tiles.insert(tile);
2163 for (auto &[key, ends] : overlayUses.packetEnds)
2164 tiles.insert(key.first);
2165 for (auto &[key, flows] : overlayUses.packetFlows)
2166 tiles.insert(key.first);
2167 return tiles.takeVector();
2168}
2169
2171 ArrayRef<PinnedChannels::End> extra,
2172 ArrayRef<Operation *> tilesHere,
2173 const ShimTransferSpans *spans) const {
2174 if (!overlayChannels(at))
2175 return {};
2176 llvm::DenseSet<int> circuits;
2177 llvm::DenseMap<int, SmallVector<StringAttr>> packetEnds;
2178 llvm::DenseMap<int, unsigned> packetFlows;
2179 for (Operation *tile : tilesHere)
2180 if (auto it = overlayUses.circuits.find(tile);
2181 it != overlayUses.circuits.end())
2182 circuits.insert(it->second.begin(), it->second.end());
2183 for (auto &[key, ends] : overlayUses.packetEnds)
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;
2189 auto onChannel = pins.sendingAt(at);
2190 for (const PinnedChannels::End &end : extra)
2191 if (end.sends)
2192 onChannel[end.channel].push_back(end);
2193 int count = adaptiveOverlay ? targetModel->getNumSourceShimMuxConnections(
2194 at.col, at.row, WireBundle::DMA)
2195 : 1;
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) ||
2201 llvm::any_of(ends, [&](PinnedChannels::End end) {
2202 return !isPacketSwitched(end.fifo.packetHeader(), packetSwitched);
2203 }))
2204 continue;
2205 size_t demand = ends.size() + packetEnds.lookup(channel).size() +
2206 packetFlows.lookup(channel);
2207 if (demand < fewest) {
2208 fewest = demand;
2209 chosen = channel;
2210 }
2211 }
2212 if (!chosen)
2213 return {/*fits=*/false, /*channels=*/1, /*own=*/false};
2214 SmallVector<StringAttr> sharers = packetEnds.lookup(*chosen);
2215 for (PinnedChannels::End end : onChannel.lookup(*chosen))
2216 sharers.push_back(end.fifo.getSymNameAttr());
2217 if (sharers.empty() && !packetFlows.lookup(*chosen))
2218 return {/*fits=*/true, /*channels=*/1, /*own=*/true};
2219 bool apart = llvm::all_of(sharers, [&](StringAttr end) {
2220 return spans && spans->apart(spans->overlayEnd(at.col), end);
2221 });
2222 return {apart, /*channels=*/0, /*own=*/false};
2223}
2224
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;
2230 for (const PinnedChannels::End &end : ends) {
2231 if (clashWith(at, end) || claimWith(at, end))
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);
2238 }
2239 return held;
2240}
2241
2242DenseMap<StringAttr, SmallVector<ShimTransferSpans::Gate>>
2243Placer::provenShimGates(DeviceOp device) {
2244 // A context of its own: the passes below cannot run nested in this one's.
2245 // Printing just this device, not its whole module, keeps the roundtrip's
2246 // cost to this device's size on a module with several; the parse skips
2247 // reverifying IR this context already verified once.
2248 std::string text;
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, /*verifyAfterParse=*/false));
2257 if (!copy)
2258 return {};
2259 auto devices = llvm::to_vector(copy->getOps<DeviceOp>());
2260 if (devices.empty())
2261 return {};
2262 DeviceOp clone = devices.front();
2263
2264 // Split needs placed tiles. With every fifo between two tiles on DMA,
2265 // which tiles they are does not change what verify proves.
2266 const AIETargetModel &target = clone.getTargetModel();
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());
2273 // Pinned tiles first, so a tile free to go anywhere never takes the one a
2274 // pin needs; then in collectOperations' structural order.
2275 SmallVector<LogicalTileOp> logicalTiles =
2277 llvm::stable_sort(logicalTiles, [](LogicalTileOp a, LogicalTileOp b) {
2278 return !a.tryGetCol() + !a.tryGetRow() < !b.tryGetCol() + !b.tryGetRow();
2279 });
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() &&
2285 satisfiesConstraints(lt, {col, row}) &&
2286 (lt.getTileType() != AIETileType::CoreTile ||
2287 !usedCores.contains({col, row})))
2288 fits.push_back({col, row});
2289 if (fits.empty())
2290 return {};
2291 TileID at = lt.getTileType() == AIETileType::CoreTile
2292 ? fits.front()
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());
2298 lt.erase();
2299 }
2300 for (auto fifo : clone.getOps<ObjectFifoCreateOp>()) {
2301 if (fifo.forcesDMA() ||
2302 llvm::all_of(fifo.getConsumerTiles(), [&](Value consumer) {
2303 return consumer == fifo.getProducerTile();
2304 }))
2305 continue;
2306 ObjectFifoTransportAttr transport = fifo.getTransportAttr();
2307 fifo.setTransportAttr(ObjectFifoTransportAttr::get(
2308 &context, ObjectFifoTransportMode::DMA,
2309 transport ? transport.getPacket() : PacketInfoAttr(),
2310 transport && transport.getOutOfOrder()));
2311 }
2312 for (auto allocate : llvm::to_vector(clone.getOps<ObjectFifoAllocateOp>()))
2313 allocate.erase();
2314
2315 PassManager pm(&context, DeviceOp::getOperationName());
2316 pm.addPass(createAIEObjectFifoSplitPass());
2317 pm.addPass(createAIEObjectFifoVerifyPass());
2318 if (failed(pm.run(clone)))
2319 return {};
2320 DenseMap<StringAttr, SmallVector<ShimTransferSpans::Gate>> gates;
2321 MLIRContext *ctx = device.getContext();
2322 for (auto &[fifo, proven] :
2324 for (const ShimTransferSpans::Gate &gate : 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())});
2335 }
2336 return gates;
2337}
2338
2340 ArrayRef<PacketFlowOp> pktFlows) {
2341 Adjacency adjacency;
2342 for (auto flow : flows)
2343 adjacency.addEdgeFromValues(flow.getSource(), flow.getDest());
2344
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());
2352 });
2353 for (auto s : srcs)
2354 for (auto d : dsts)
2355 adjacency.addEdgeFromValues(s, d);
2356 }
2357 return adjacency;
2358}
2359
2360// Tiles with both coordinates are one tile however many ops name them, as in
2361// DMAChannelAnalysis::getTileKey: their demand is keyed by the first op seen
2362// there, placed or not, so a physical tile's channels count at its position.
2363// A DMA channel is a hardware resource: a broadcast (one source channel feeding
2364// multiple destinations) consumes one MM2S channel on the producer regardless
2365// of the number of `aie.flow` ops it lowers to, and a merge (multiple sources
2366// landing on one destination channel) consumes one S2MM channel on the
2367// consumer. Dedup by (tile, channel) so the producer-of-broadcast and
2368// consumer-of-merge sides are each counted once. An `aie.route` end whose
2369// channel allocation has yet to pick holds a channel of its own.
2370llvm::MapVector<Operation *, std::pair<int, int>> Placer::flowChannelDemand(
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;
2378
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)
2383 return;
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;
2387 if (keys)
2388 (*keys)[tileOp] = key;
2389 tileOp = key;
2390 auto &seen = isOutput ? seenSrc : seenDst;
2391 if (channel && !seen.insert({tileOp, *channel}).second)
2392 return;
2393 if (channel && named)
2394 (*named)[tileOp].push_back({isOutput, *channel});
2395 if (isOutput)
2396 demand[tileOp].second++;
2397 else
2398 demand[tileOp].first++;
2399 };
2400
2401 for (auto flow : flows) {
2402 incIfDMA(flow.getSource().getDefiningOp(), flow.getSourceBundle(),
2403 flow.getSourceChannel(), /*isOutput=*/true);
2404 incIfDMA(flow.getDest().getDefiningOp(), flow.getDestBundle(),
2405 flow.getDestChannel(), /*isOutput=*/false);
2406 }
2407
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(), /*isOutput=*/true);
2413 } else if (auto dst = dyn_cast<PacketDestOp>(op)) {
2414 incIfDMA(dst.getTile().getDefiningOp(), dst.getBundle(),
2415 dst.getChannel(), /*isOutput=*/false);
2416 }
2417 });
2418 }
2419
2420 for (const DMAChannelAnalysis::ChannelClaim &claim : claims)
2421 incIfDMA(claim.tile.getDefiningOp(), WireBundle::DMA, claim.channel,
2422 claim.dir == DMAChannelDir::MM2S);
2423
2424 // Packet routes may share an endpoint, which holds one channel however many
2425 // routes name it, and a fan-in's sources share one destination channel.
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);
2434 };
2435 for (StringRef source : route.getSourceNames())
2436 count(source, /*isOutput=*/true);
2437 for (StringRef dest : route.getDestinationNames())
2438 count(dest, /*isOutput=*/false);
2439 }
2440 return demand;
2441}
2442
2443SequentialPlacer::FlowMembership SequentialPlacer::buildFlowMembership(
2444 ArrayRef<FlowOp> flows, ArrayRef<PacketFlowOp> pktFlows,
2445 ArrayRef<RouteOp> routes, ArrayRef<ObjectFifoCreateOp> objectFifos) {
2446 // packet_flow connectivity is sources x destinations -- destinations
2447 // are never each other's peers. Same asymmetry for route and objectfifo
2448 // producer/consumers.
2449 FlowMembership idx;
2450 auto isLto = [](Value v) {
2451 return v && mlir::isa_and_nonnull<LogicalTileOp>(v.getDefiningOp());
2452 };
2453 auto addEntry = [&](Value lto, ArrayRef<Value> peers) {
2454 if (!isLto(lto) || peers.empty())
2455 return;
2456 idx.ltoFlows[lto].push_back(SmallVector<Value>(peers.begin(), peers.end()));
2457 };
2458
2459 for (auto flow : flows) {
2460 Value s = flow.getSource(), d = flow.getDest();
2461 addEntry(s, {d});
2462 addEntry(d, {s});
2463 }
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());
2471 });
2472 for (Value s : srcs)
2473 addEntry(s, dsts);
2474 for (Value d : dsts)
2475 addEntry(d, srcs);
2476 }
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();
2482 };
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)
2491 addEntry(s, dsts);
2492 for (Value d : dsts)
2493 addEntry(d, srcs);
2494 }
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});
2502 }
2503 return idx;
2504}
2505
2506std::optional<int>
2507SequentialPlacer::computeCentroidColumn(LogicalTileOp logicalTile,
2508 const FlowMembership &flowIndex) {
2509 // Per-flow routing cost as a function of the LTO's column S:
2510 // single-dest flow to col D : cost(S) = |S - D|
2511 // N-dest flow spanning [lo, hi]:
2512 // cost(S) = 0 if lo <= S <= hi
2513 // = lo - S if S < lo
2514 // = S - hi if S > hi
2515 // Inside a broadcast's span the cost is flat -- broadcasts constrain
2516 // the LTO to stay within their reach but don't pull it to any column.
2517 // Tiebreak by closest-to-mean-of-dests so a pure broadcast lands mid
2518 // and two single-dest flows average to their midpoint.
2519 Value ltoVal = logicalTile.getResult();
2520 auto ltoIt = flowIndex.ltoFlows.find(ltoVal);
2521 if (ltoIt == flowIndex.ltoFlows.end())
2522 return std::nullopt;
2523
2524 // Column of a flow endpoint, or nullopt if not yet fixed. A memtile that
2525 // already knows its column answers here; looking past it to its cores
2526 // would pick up the other flows it carries.
2527 auto resolvePeerCol = [&](Value v) -> std::optional<int> {
2528 Operation *defOp = v.getDefiningOp();
2529 if (!defOp)
2530 return std::nullopt;
2531 // A physical tile's column is fixed by construction, whatever its type.
2532 if (auto tileOp = dyn_cast<TileOp>(defOp))
2533 return tileOp.getCol();
2534 auto lto = dyn_cast<LogicalTileOp>(defOp);
2535 if (!lto)
2536 return std::nullopt;
2537 if (auto c = lto.tryGetCol())
2538 return c;
2539 auto it = result.find(defOp);
2540 if (it != result.end())
2541 return it->second.col;
2542 return std::nullopt;
2543 };
2544
2545 // One level of indirection for shim->memtile->core, used only when the
2546 // memtile's own column is still unknown. Multi-level memtile chains aren't
2547 // currently produced by mlir-aie.
2548 auto resolveLtoCoreCols = [&](Value v) {
2549 SmallVector<int> out;
2550 auto it = flowIndex.ltoFlows.find(v);
2551 if (it == flowIndex.ltoFlows.end())
2552 return out;
2553 for (auto &peerList : it->second)
2554 for (Value p : peerList)
2555 if (auto col = resolvePeerCol(p))
2556 out.push_back(*col);
2557 return out;
2558 };
2559
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);
2566 continue;
2567 }
2568 if (p == ltoVal)
2569 continue;
2570 for (int c : resolveLtoCoreCols(p))
2571 dests.push_back(c);
2572 }
2573 if (!dests.empty())
2574 perFlowDests.push_back(std::move(dests));
2575 }
2576
2577 if (perFlowDests.empty())
2578 return std::nullopt;
2579
2580 double meanDestCol = 0.0;
2581 int destCount = 0;
2582 for (auto &dests : perFlowDests)
2583 for (int d : dests) {
2584 meanDestCol += d;
2585 ++destCount;
2586 }
2587 meanDestCol /= destCount;
2588
2589 int numCols = targetModel->columns();
2590 int bestCol = 0;
2591 int bestCost = std::numeric_limits<int>::max();
2592 double bestTiebreak = std::numeric_limits<double>::infinity();
2593 for (int S = 0; S < numCols; ++S) {
2594 int cost = 0;
2595 for (auto &dests : perFlowDests) {
2596 if (dests.size() == 1) {
2597 cost += std::abs(S - dests[0]);
2598 } else {
2599 int lo = *llvm::min_element(dests);
2600 int hi = *llvm::max_element(dests);
2601 if (S < lo)
2602 cost += lo - S;
2603 else if (S > hi)
2604 cost += S - hi;
2605 }
2606 }
2607 double tiebreak = std::abs(S - meanDestCol);
2608 if (cost < bestCost || (cost == bestCost && tiebreak < bestTiebreak)) {
2609 bestCost = cost;
2610 bestTiebreak = tiebreak;
2611 bestCol = S;
2612 }
2613 }
2614 return bestCol;
2615}
2616
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();
2624
2625 // With spread-unanchored-tiles off, an LTO with no CoreTile peer targets
2626 // column 0, which ranks every candidate at the same distance and so pins the
2627 // whole design to one column until it fills up.
2628 std::optional<int> targetCol = colConstraint ? colConstraint : centroidCol;
2629 if (!targetCol && !spreadUnanchoredTiles)
2630 targetCol = 0;
2631
2632 auto [numInputChannels, numOutputChannels] =
2633 channelRequirements.lookup(logicalTile.getOperation());
2634
2635 auto maybeTile = findTileWithCapacity(targetCol, availability.nonCompTiles,
2636 numInputChannels, numOutputChannels,
2637 logicalTile.getTileType(), logicalTile,
2638 /*withinBudgets=*/true);
2639 if (!maybeTile)
2640 maybeTile = findTileWithCapacity(targetCol, availability.nonCompTiles,
2641 numInputChannels, numOutputChannels,
2642 logicalTile.getTileType(), logicalTile,
2643 /*withinBudgets=*/false);
2644 // Exhausted shim tiles are no longer in availability, so look at them all.
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) {
2649 TileID tile{col, 0};
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}))
2657 continue;
2658 std::pair<int, int> key{targetCol ? std::abs(col - *targetCol) : 0, col};
2659 if (!bestKey || key < *bestKey) {
2660 bestKey = key;
2661 maybeTile = tile;
2662 }
2663 }
2664 }
2665 if (!maybeTile) {
2666 if (std::optional<TileID> named = findTileWithCapacity(
2667 targetCol, availability.nonCompTiles, numInputChannels,
2668 numOutputChannels, logicalTile.getTileType(), logicalTile,
2669 /*withinBudgets=*/false, /*apartByName=*/false))
2670 if (auto clash = namedClash(logicalTile, overlayTilesAt.lookup(*named)))
2671 return emitNamedClash(logicalTile, *named, *clash);
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)
2679 return;
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";
2688 };
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";
2693 noteClash();
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)
2705 diag.attachNote()
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 << " "
2712 << tileTypeName
2713 << "(s), with this tile's pinned ends, the control "
2714 "overlay has no output channel it may take or "
2715 "share";
2716 int shortIn = diagnosis.closestShortIn;
2717 int shortOut = diagnosis.closestShortOut;
2718 if (shortIn == 0 && shortOut == 0)
2719 return failure();
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 "
2731 "tile";
2732 } else {
2733 diag << "no " << tileTypeName << " has sufficient DMA capacity for "
2734 << numInputChannels << " input/" << numOutputChannels
2735 << " output channels ";
2736 if (colConstraint)
2737 diag << "at column " << *colConstraint;
2738 else if (centroidCol)
2739 diag << "near centroid column " << *centroidCol;
2740 else
2741 diag << "on any column";
2742 noteClash();
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";
2750 }
2751 return failure();
2752 }
2753
2754 result[logicalTile] = *maybeTile;
2755 addPlacedStreams(logicalTile);
2756 LLVM_DEBUG({
2757 auto showCol = [](std::optional<int> c) {
2758 return c ? std::to_string(*c) : std::string("none");
2759 };
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";
2764 });
2765 if (!mergeLogicalTiles)
2766 assignedNonCoreTiles.insert(*maybeTile);
2767 std::optional<std::pair<int, int>> held =
2768 pinsAt.heldAt(*maybeTile, pinnedEnds.lookup(logicalTile));
2769 if (!held)
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);
2780 return success();
2781}
2782
2783bool SequentialPlacer::fitsSharingShim(TileID tile, Operation *logicalTile,
2784 std::pair<int, int> required) {
2785 if (targetModel->getTileType(tile.col, tile.row) !=
2786 AIETileType::ShimNOCTile ||
2787 !shimSpans)
2788 return false;
2789 const ShimTransferSpans &spans = *shimSpans;
2790 auto [maxIn, maxOut] = getDMACapacity(*targetModel, tile);
2791 OverlayFit overlay = overlayWith(tile, logicalTile);
2792 if (!overlay.fits)
2793 return false;
2794 int used[2] = {availability.inputChannelsUsed[tile],
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));
2799 if (shareableShimEnds.contains(logicalTile))
2800 tilesHere.push_back(logicalTile);
2801 for (int dir : {0, 1}) {
2802 if (used[dir] + need[dir] <= max[dir])
2803 continue;
2804 SmallVector<const ShimSide *> sides;
2805 for (Operation *op : tilesHere)
2806 sides.push_back(&shareableShimEnds.find(op)->second[dir]);
2807 SmallVector<StringAttr> extra;
2808 if (dir == 1 && overlay.own)
2809 extra.push_back(spans.overlayEnd(tile.col));
2810 SmallVector<int> pinnedHere = pinsAt.channelsAt(tile, dir == 1);
2811 for (const PinnedChannels::End &end : pinnedEnds.lookup(logicalTile))
2812 if (end.sends == (dir == 1))
2813 pinnedHere.push_back(end.channel);
2814 if (used[dir] + need[dir] -
2815 shimChannelsSaved(spans, sides, extra, pinnedHere) >
2816 max[dir])
2817 return false;
2818 }
2819 return true;
2820}
2821
2822void SequentialPlacer::recordShimEnds(TileID tile, Operation *logicalTile) {
2823 if (shareableShimEnds.contains(logicalTile))
2824 shimTilesAt[tile].push_back(logicalTile);
2825}
2826
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,
2831 bool apartByName) {
2832 // Choose a physical tile by lexicographic minimum of
2833 // (|col - targetCol| + broadcast pressure, current load, col, row).
2834 // A memtile's extra broadcast destinations penalize sharing its bandwidth,
2835 // even when an idle tile is slightly farther from the centroid. Without
2836 // broadcasts, and for shims or explicit column hints, distance still leads.
2837 // (col, row) is the final tiebreaker for determinism.
2838 //
2839 // Without a targetCol there is no routing anchor to measure against, so the
2840 // distance term is dropped and load leads. Load is then counted only in the
2841 // directions this LTO actually needs, matching hasAvailableChannels, which
2842 // already filters per direction: summing both would push a chain's read and
2843 // write shims onto different columns and need 2N columns for N chains.
2844 std::optional<TileID> best;
2845 std::tuple<int, int64_t, int, int, int> bestKey;
2846 SmallVector<PinnedChannels::End> pins = pinnedEnds.lookup(logicalTile);
2847
2848 for (auto &tile : tiles) {
2849 if (targetModel->getTileType(tile.col, tile.row) != requestedType)
2850 continue;
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))
2855 continue;
2856 // When merge-logical-tiles is disabled, a tile that already hosts a
2857 // non-core aie.logical_tile is off-limits even if it has spare DMA
2858 // capacity.
2859 if (!mergeLogicalTiles && assignedNonCoreTiles.contains(tile))
2860 continue;
2861 if (withinBudgets && (!fitsStreamAndBdBudgets(logicalTile, tile) ||
2862 raisesStreamCuts(logicalTile, tile)))
2863 continue;
2864 if (apartByName &&
2865 namedClash(logicalTile, overlayTilesAt.lookup(tile)).has_value())
2866 continue;
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);
2871 int load;
2872 if (targetCol ||
2873 (requiredInputChannels == 0 && requiredOutputChannels == 0)) {
2874 load = availability.inputChannelsUsed[tile] +
2875 availability.outputChannelsUsed[tile];
2876 } else {
2877 load = 0;
2878 if (requiredInputChannels > 0)
2879 load += availability.inputChannelsUsed[tile];
2880 if (requiredOutputChannels > 0)
2881 load += availability.outputChannelsUsed[tile];
2882 }
2883 // Among equally near shim tiles, the one spreading DDR traffic most.
2884 int64_t ddr = 0;
2885 if (ddrGroupsOf.contains(logicalTile))
2886 ddr = ddrSpread(
2887 [&](Operation *op) -> std::optional<int> {
2888 if (op == logicalTile)
2889 return tile.col;
2890 if (auto placed = dyn_cast<TileOp>(op))
2891 return placed.getCol();
2892 std::optional<TileID> at = getPlacement(op);
2893 return at ? std::optional(at->col) : std::nullopt;
2894 },
2895 /*weight=*/1 << 16);
2896 std::tuple<int, int64_t, int, int, int> key{dist, ddr, load, tile.col,
2897 tile.row};
2898 if (!best || key < bestKey) {
2899 best = tile;
2900 bestKey = key;
2901 }
2902 }
2903
2904 return best;
2905}
2906
2907SequentialPlacer::CapacityDiagnosis
2908SequentialPlacer::diagnoseCapacityExhaustion(AIETileType requestedType,
2909 int requiredInputChannels,
2910 int requiredOutputChannels,
2911 Operation *joining) {
2912 // Walk the device directly rather than `availability.nonCompTiles`: a
2913 // fully-exhausted tile is meant to stay enumerable here even if a future
2914 // fix makes `updateChannelUsage`'s prune (see its `removeTile` call)
2915 // actually fire, which today it structurally cannot.
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)
2920 continue;
2921 TileID tile{col, row};
2922 ++diagnosis.tilesOfType;
2923 auto [maxIn, maxOut] = getDMACapacity(*targetModel, tile);
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;
2930 int usedOut =
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;
2941 }
2942 SmallVector<PinnedChannels::End> pins = pinnedEnds.lookup(joining);
2943 std::optional<std::pair<int, int>> held = pinsAt.heldAt(tile, pins);
2944 if (!held) {
2945 ++diagnosis.clashTiles;
2946 for (const PinnedChannels::End &end : pins)
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);
2951 continue;
2952 }
2953 if (hasAvailableChannels(tile, requiredInputChannels - held->first,
2954 requiredOutputChannels - held->second, joining))
2955 diagnosis.capacityExistsSomewhere = true;
2956 }
2957 }
2958 return diagnosis;
2959}
2960
2961void SequentialPlacer::updateChannelUsage(TileID tile, DmaDir direction,
2962 int numChannels) {
2963 if (direction == DmaDir::Out)
2964 availability.outputChannelsUsed[tile] += numChannels;
2965 else
2966 availability.inputChannelsUsed[tile] += numChannels;
2967
2968 if (!hasAvailableChannels(tile, 0, 0)) {
2969 AIETileType type = targetModel->getTileType(tile.col, tile.row);
2970 availability.removeTile(tile, type);
2971 }
2972}
2973
2974bool SequentialPlacer::hasAvailableChannels(TileID tile, int inputChannels,
2975 int outputChannels,
2976 Operation *joining) {
2977 auto [maxIn, maxOut] = getDMACapacity(*targetModel, tile);
2978 OverlayFit overlay = overlayWith(tile, joining);
2979
2980 int currentIn = availability.inputChannelsUsed[tile];
2981 int currentOut = availability.outputChannelsUsed[tile] + overlay.channels;
2982
2983 return overlay.fits && (currentIn + inputChannels <= maxIn) &&
2984 (currentOut + outputChannels <= maxOut);
2985}
2986
2987Placer::OverlayFit SequentialPlacer::overlayWith(TileID tile,
2988 Operation *joining) {
2989 if (!overlayChannels(tile))
2990 return {};
2991 SmallVector<Operation *> tilesHere(overlayTilesAt.lookup(tile));
2992 SmallVector<PinnedChannels::End> pins;
2993 if (joining) {
2994 tilesHere.push_back(joining);
2995 pins = pinnedEnds.lookup(joining);
2996 }
2997 return overlayAt(tile, pinsAt, pins, tilesHere,
2998 shimSpans ? &*shimSpans : nullptr);
2999}
3000
3001void SequentialPlacer::recordColumnStreamUsage(Operation *tile, int col) {
3002 auto &incoming = columnIncomingFifos[col];
3003 for (Operation *fifo : incomingFifos.lookup(tile))
3004 incoming.insert(fifo);
3005 auto &used = columnStreamsUsed[col];
3006 used += streamDemand.lookup(tile);
3007 used.southIn = incoming.size();
3008}
3009
3010void Placer::buildStreamDemand(ArrayRef<ObjectFifoCreateOp> objectFifos) {
3011 streamDemand.clear();
3012 incomingFifos.clear();
3013 broadcastFanout.clear();
3014 // Rows rise from shims through memtiles to cores, so a stream to a higher
3015 // rank leaves through the North port and arrives through the South port.
3016 auto rank = [](Operation *op) -> std::optional<int> {
3017 auto tile = dyn_cast_or_null<TileLike>(op);
3018 if (!tile)
3019 return std::nullopt;
3020 if (tile.isShimTile())
3021 return 0;
3022 return tile.isMemTile() ? 1 : 2;
3023 };
3024 for (auto of : objectFifos) {
3025 Operation *producer = of.getProducerTile().getDefiningOp();
3026 std::optional<int> producerRank = rank(producer);
3027 if (!producerRank)
3028 continue;
3029 if (*producerRank == 1)
3030 broadcastFanout[producer] +=
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)
3037 continue;
3038 if (*consumerRank > *producerRank) {
3039 north = true;
3040 streamDemand[consumer].southIn++;
3041 if (*consumerRank == 2)
3042 incomingFifos[consumer].push_back(of.getOperation());
3043 } else {
3044 south = true;
3045 streamDemand[consumer].northIn++;
3046 }
3047 }
3048 if (north)
3049 streamDemand[producer].northOut++;
3050 if (south)
3051 streamDemand[producer].southOut++;
3052 }
3053}
3054
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);
3062 // Each wire from a switchbox to its neighbour's, through a port both have.
3063 auto wires = [&](TileID a, TileID b, WireBundle out, WireBundle in) {
3064 auto [rowCut, below, up] = boundaryOf(a, b);
3065 capacity[indexOf(rowCut, below, up)] +=
3066 std::min(target.getNumDestSwitchboxConnections(a.col, a.row, out),
3067 target.getNumSourceSwitchboxConnections(b.col, b.row, in));
3068 };
3069 for (int col = 0; col < columns; ++col)
3070 for (int row = 0; row < rows; ++row) {
3071 TileID at{col, 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);
3076 }
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);
3081 }
3082 }
3083}
3084
3085unsigned StreamCuts::indexOf(bool rows, int below, bool up) const {
3086 return (rows ? 2 * (columns - 1) : 0) + 2 * below + up;
3087}
3088
3089void StreamCuts::add(TileID src, ArrayRef<TileID> dsts, bool packet, int sign) {
3090 if (dsts.empty())
3091 return;
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;
3096 };
3097 auto [minCol, maxCol] =
3098 std::minmax_element(dsts.begin(), dsts.end(),
3099 [](TileID a, TileID b) { return a.col < b.col; });
3100 auto [minRow, maxRow] =
3101 std::minmax_element(dsts.begin(), dsts.end(),
3102 [](TileID a, TileID b) { return a.row < b.row; });
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);
3107}
3108
3109int StreamCuts::over() const {
3110 int missing = 0;
3111 for (auto [cap, circuit, packet] : llvm::zip(capacity, circuits, packets))
3112 missing += std::max(0, circuit + (packet > 0) - cap);
3113 return missing;
3114}
3115
3116int64_t StreamCuts::near(double fraction) const {
3117 int64_t total = 0;
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));
3121 if (past > 0)
3122 total += past * past;
3123 }
3124 return total;
3125}
3126
3127void Placer::buildStreamNets(DeviceOp device, const CollectedOps &collected) {
3128 streamNets.clear();
3129 streamNetsOf.clear();
3130 llvm::StringMap<Operation *> delegates;
3131 for (ObjectFifoAllocateOp alloc : collected.objectFifoAllocates)
3132 delegates[alloc.getObjFifoName()] = alloc.getDelegateTile().getDefiningOp();
3133 for (ObjectFifoCreateOp fifo : collected.objectFifos) {
3134 StreamNet &net = streamNets.emplace_back();
3135 net.src = fifo.getProducerTile().getDefiningOp();
3136 for (Value consumer : fifo.getConsumerTiles())
3137 net.dsts.push_back(consumer.getDefiningOp());
3138 net.packet = isPacketSwitched(fifo.packetHeader(), packetSwitched);
3139 net.mayShare = !fifo.dmaReason();
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();
3144 }
3145 for (FlowOp flow : collected.flows)
3146 streamNets.push_back({flow.getSource().getDefiningOp(),
3147 {flow.getDest().getDefiningOp()},
3148 /*packet=*/false});
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)
3156 streamNets.push_back({source, dests, /*packet=*/true});
3157 }
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;
3163 };
3164 SmallVector<Operation *, 2> dests;
3165 for (StringRef dest : route.getDestinationNames())
3166 dests.push_back(tileOf(dest));
3167 bool packet = isPacketSwitched(route.getPacketAttr(), packetSwitched);
3168 for (StringRef source : route.getSourceNames())
3169 streamNets.push_back({tileOf(source), dests, packet});
3170 }
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)
3178 if (tile)
3179 streamNetsOf[tile].push_back(index);
3180 }
3181}
3182
3184 function_ref<std::optional<TileID>(Operation *)> at,
3185 TileID &src, SmallVectorImpl<TileID> &dsts) const {
3186 dsts.clear();
3187 std::optional<TileID> from = net.src ? at(net.src) : std::nullopt;
3188 if (!from)
3189 return false;
3190 src = *from;
3191 std::optional<TileID> delegate, link;
3192 if (net.mayShare) {
3193 if (net.delegate && !(delegate = at(net.delegate)))
3194 return false;
3195 if (net.link && !(link = at(net.link)))
3196 return false;
3197 }
3198 for (Operation *dst : net.dsts) {
3199 std::optional<TileID> to = dst ? at(dst) : std::nullopt;
3200 if (!to)
3201 return false;
3202 if (!net.mayShare || ObjectFifoCreateOp::sharedMemoryOf(
3203 *targetModel, src, *to, delegate, link) ==
3205 dsts.push_back(*to);
3206 }
3207 return !dsts.empty();
3208}
3209
3211 const AIETargetModel &targetModel)
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;
3216 };
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);
3223 else
3224 ++bds.unpinned;
3225 });
3226 }
3227 // How a descriptor splits depends on the tile type, not on its column.
3228 std::optional<int> shimCol;
3229 for (int col = 0; col < targetModel.columns() && !shimCol; ++col)
3230 if (targetModel.getTileType(col, 0) == AIETileType::ShimNOCTile)
3231 shimCol = col;
3232
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);
3243 auto plan = AIEX::decomposeTaskBdPattern(bd, targetModel, *shimCol, 0);
3244 size_t pieces =
3245 succeeded(plan) && !plan->pieces.empty() ? plan->pieces.size() : 1;
3246 // A pinned id stays with the first piece.
3247 task.bdIds.push_back(pinned);
3248 task.bdIds.append(pieces - 1, std::nullopt);
3249 });
3250 taskOf[result] = tasks.size();
3251 events.push_back({tasks.size(), true});
3252 tasks.push_back(std::move(task));
3253 };
3254 seq.walk([&](Operation *op) {
3255 if (!shimCol)
3256 return;
3257 if (auto cfg = dyn_cast<AIEX::DMAConfigureTaskLike>(op)) {
3258 if (Operation *shim = shimOf(AIEX::getRuntimeDmaTile(op, symbols)))
3259 configure(shim, op->getResult(0), cfg.getBody());
3260 return;
3261 }
3262 if (auto copy = dyn_cast<AIEX::NpuDmaMemcpyNdOp>(op)) {
3263 if (Operation *shim = shimOf(AIEX::getRuntimeDmaTile(op, symbols))) {
3264 events.push_back({tasks.size(), true});
3265 tasks.push_back(
3266 {shim, {static_cast<uint32_t>(copy.getId())}, 1, true});
3267 }
3268 return;
3269 }
3270 Value released;
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});
3277 taskOf.erase(it);
3278 }
3279 });
3280 });
3281
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();
3286 }
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);
3297 }
3298 }
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;
3308
3309 auto shimAt = [&](Operation *shim) -> Shim & {
3310 auto [entry, fresh] = indexOf.try_emplace(shim, shims.size());
3311 if (fresh)
3312 shims.push_back(
3313 {shim, {}, SmallVector<SmallVector<unsigned>>(sequences.size())});
3314 return shims[entry->second];
3315 };
3316 for (auto program : device.getOps<ShimDMAOp>())
3317 if (Operation *shim = shimOf(program.getTile().getDefiningOp()))
3318 shimAt(shim);
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);
3324}
3325
3326int Placer::RuntimeBdIds::shortfall(ArrayRef<Operation *> onTile,
3327 TileID tile) const {
3328 llvm::SmallBitVector key(shims.size());
3329 int live = 0;
3330 bool constrained = false;
3331 auto add = [&](Operation *shim) {
3332 auto peak = peaks.find(shim);
3333 if (peak == peaks.end())
3334 return;
3335 unsigned index = indexOf.lookup(shim);
3336 if (key.test(index))
3337 return;
3338 key.set(index);
3339 live += peak->second.live;
3340 constrained |= peak->second.constrained;
3341 };
3342 for (Operation *shim : onTile)
3343 add(shim);
3344 if (Operation *shim = placed.lookup(tile))
3345 add(shim);
3346 // Lowest-free ids never fragment, so peaks that fit together always do.
3347 if (!constrained &&
3348 live <= static_cast<int>(targetModel->getNumBDs(tile.col, tile.row)))
3349 return 0;
3350 auto [cached, added] = shortfallOf.try_emplace(key, 0);
3351 if (!added)
3352 return cached->second;
3353 int &missing = cached->second;
3354
3355 // aie-assign-bd-ids: runtime-pinned ids are reserved, then static BDs take
3356 // theirs.
3357 BdIdGenerator assigned(tile.col, tile.row, *targetModel);
3358 for (unsigned shim : key.set_bits())
3359 for (unsigned task : shims[shim].tasks)
3360 for (std::optional<uint32_t> pinned : tasks[task].bdIds)
3361 if (pinned && !assigned.bdIdAlreadyAssigned(*pinned))
3362 assigned.assignBdId(*pinned);
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) {
3367 if (assigned.bdIdAlreadyAssigned(id)) {
3368 ++missing;
3369 continue;
3370 }
3371 assigned.assignBdId(id);
3372 staticIds.push_back(id);
3373 }
3374 }
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);
3379 else
3380 ++missing;
3381 }
3382
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)) {
3387 BdIdGenerator ids(tile.col, tile.row, *targetModel);
3388 for (uint32_t id : staticIds)
3389 ids.assignBdId(id);
3390 // Each shim's events are in sequence order already.
3391 mine.clear();
3392 for (unsigned shim : key.set_bits()) {
3393 ArrayRef<unsigned> theirs = shims[shim].events[sequence];
3394 merged.clear();
3395 std::merge(mine.begin(), mine.end(), theirs.begin(), theirs.end(),
3396 std::back_inserter(merged));
3397 std::swap(mine, merged);
3398 }
3399 held.clear();
3400 copied.clear();
3401 for (unsigned at : mine) {
3402 auto [index, configured] = events[at];
3403 const Task &task = tasks[index];
3404 if (task.copy) {
3405 // Copies reprogram their id at once, so they share it.
3406 uint32_t id = *task.bdIds.front();
3407 if (!copied.insert(id).second)
3408 continue;
3409 if (ids.bdIdAlreadyAssigned(id))
3410 ++missing;
3411 else
3412 ids.assignBdId(id);
3413 continue;
3414 }
3415 if (!configured) {
3416 for (uint32_t id : held.lookup(index))
3417 ids.freeBdId(id);
3418 held.erase(index);
3419 continue;
3420 }
3421 SmallVector<uint32_t> &taken = held[index];
3422 for (std::optional<uint32_t> pinned : task.bdIds) {
3423 if (!pinned)
3424 continue;
3425 if (ids.bdIdAlreadyAssigned(*pinned)) {
3426 ++missing;
3427 continue;
3428 }
3429 ids.assignBdId(*pinned);
3430 taken.push_back(*pinned);
3431 }
3432 for (auto [i, pinned] : llvm::enumerate(task.bdIds)) {
3433 if (pinned)
3434 continue;
3435 if (std::optional<uint32_t> id =
3436 ids.nextBdId(0, i == 0 ? task.headAlignment : 1))
3437 taken.push_back(*id);
3438 else
3439 ++missing;
3440 }
3441 }
3442 }
3443 return missing;
3444}
3445
3446bool SequentialPlacer::fitsStreamAndBdBudgets(Operation *logicalTile,
3447 TileID tile) const {
3448 // Only the ports this LTO adds to: a tile a fallback already overfilled
3449 // stays open to LTOs that use none of its streams.
3450 StreamDemand demand = streamDemand.lookup(logicalTile);
3451 StreamDemand streams = availability.streamsUsed.lookup(tile);
3452 streams += demand;
3453 const AIETargetModel &tm = *targetModel;
3454 if ((demand.northIn &&
3455 streams.northIn > static_cast<int>(tm.getNumSourceSwitchboxConnections(
3456 tile.col, tile.row, WireBundle::North))) ||
3457 (demand.southIn &&
3458 streams.southIn > static_cast<int>(tm.getNumSourceSwitchboxConnections(
3459 tile.col, tile.row, WireBundle::South))) ||
3460 (demand.northOut &&
3461 streams.northOut > static_cast<int>(tm.getNumDestSwitchboxConnections(
3462 tile.col, tile.row, WireBundle::North))) ||
3463 (demand.southOut &&
3464 streams.southOut > static_cast<int>(tm.getNumDestSwitchboxConnections(
3465 tile.col, tile.row, WireBundle::South))))
3466 return false;
3467
3468 if (!runtimeBdIds.uses(logicalTile))
3469 return true;
3470 // Only the ids this LTO adds to: a tile a fallback already overfilled stays
3471 // open to LTOs whose tasks take none.
3472 SmallVector<Operation *> onTile = availability.runtimeBdTiles.lookup(tile);
3473 int before = runtimeBdIds.shortfall(onTile, tile);
3474 onTile.push_back(logicalTile);
3475 return runtimeBdIds.shortfall(onTile, tile) == before;
3476}
3477
3478bool SequentialPlacer::raisesStreamCuts(Operation *logicalTile,
3479 TileID tile) const {
3480 auto at = [&](Operation *op) -> std::optional<TileID> {
3481 if (op == logicalTile)
3482 return tile;
3483 if (auto placed = dyn_cast<TileOp>(op))
3484 return placed.getTileID();
3485 return getPlacement(op);
3486 };
3487 StreamCuts cuts = placedCuts;
3488 int before = cuts.over();
3489 TileID src;
3490 SmallVector<TileID> dsts;
3491 for (unsigned net : streamNetsOf.lookup(logicalTile))
3492 if (!cutNets.test(net) && streamOf(streamNets[net], at, src, dsts))
3493 cuts.add(src, dsts, streamNets[net].packet, 1);
3494 return cuts.over() > before;
3495}
3496
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();
3501 return getPlacement(op);
3502 };
3503 TileID src;
3504 SmallVector<TileID> dsts;
3505 for (unsigned net : streamNetsOf.lookup(logicalTile))
3506 if (!cutNets.test(net) && streamOf(streamNets[net], at, src, dsts)) {
3507 placedCuts.add(src, dsts, streamNets[net].packet, 1);
3508 cutNets.set(net);
3509 }
3510}
3511
3512void SequentialPlacer::recordStreamAndBdUsage(Operation *logicalTile,
3513 TileID tile) {
3514 broadcastFanoutUsed[tile] += broadcastFanout.lookup(logicalTile);
3515 overlayTilesAt[tile].push_back(logicalTile);
3516 for (const PinnedChannels::End &end : pinnedEnds.lookup(logicalTile))
3517 pinsAt.place(tile, end, 1);
3518 for (const DMAChannelAnalysis::ChannelClaim &claim :
3519 claimsOf.lookup(logicalTile))
3520 pinsAt.claim(tile, claim, 1);
3521 if (auto it = streamDemand.find(logicalTile); it != streamDemand.end())
3522 availability.streamsUsed[tile] += it->second;
3523 if (runtimeBdIds.uses(logicalTile))
3524 availability.runtimeBdTiles[tile].push_back(logicalTile);
3525}
3526
3527void TileAvailability::removeTile(TileID tile, AIETileType type) {
3528 auto removeFromVector = [&](std::vector<TileID> &vec) {
3529 vec.erase(std::remove(vec.begin(), vec.end(), tile), vec.end());
3530 };
3531
3532 switch (type) {
3533 case AIETileType::CoreTile:
3534 removeFromVector(compTiles);
3535 removeFromVector(overBudgetCompTiles);
3536 compTilesSet.erase(tile);
3537 break;
3538 case AIETileType::MemTile:
3539 case AIETileType::ShimNOCTile:
3540 case AIETileType::ShimPLTile:
3541 removeFromVector(nonCompTiles);
3542 break;
3543 }
3544}
#define DEBUG_TYPE
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)
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
ShimMM2SUses overlayUses
Definition AIEPlacer.h:499
llvm::DenseMap< mlir::Operation *, llvm::SmallVector< DMAChannelAnalysis::ChannelClaim > > claimsOf
Definition AIEPlacer.h:431
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
Definition AIEPlacer.h:450
void buildStreamNets(DeviceOp device, const CollectedOps &collected)
llvm::DenseMap< mlir::Operation *, llvm::SmallVector< unsigned > > streamNetsOf
Definition AIEPlacer.h:528
int64_t ddrGroupSpread(const DdrGroup &group, llvm::function_ref< std::optional< int >(mlir::Operation *)> columnOf, int weight) const
llvm::DenseMap< mlir::Operation *, StreamDemand > streamDemand
Definition AIEPlacer.h:505
llvm::SmallVector< StreamNet > streamNets
Definition AIEPlacer.h:526
llvm::DenseMap< mlir::Operation *, unsigned > coreKeys
Definition AIEPlacer.h:551
RuntimeBdIds runtimeBdIds
Definition AIEPlacer.h:438
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
Definition AIEPlacer.h:510
static Adjacency buildFlowAdjacency(llvm::ArrayRef< FlowOp > flows, llvm::ArrayRef< PacketFlowOp > pktFlows)
const AIETargetModel * targetModel
Definition AIEPlacer.h:556
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
Definition AIEPlacer.h:474
llvm::DenseMap< mlir::Operation *, llvm::SmallVector< std::pair< int, int > > > namedChannels
Definition AIEPlacer.h:538
llvm::SmallVector< AllocateInfo > allocates
Definition AIEPlacer.h:555
std::optional< std::pair< mlir::Operation *, std::pair< int, int > > > namedClash(mlir::Operation *tile, llvm::ArrayRef< mlir::Operation * > others) const
PlacementResult result
Definition AIEPlacer.h:554
bool streamOf(const StreamNet &net, llvm::function_ref< std::optional< TileID >(mlir::Operation *)> at, TileID &src, llvm::SmallVectorImpl< TileID > &dsts) const
ShareableShimEnds shareableShimEnds
Definition AIEPlacer.h:435
std::optional< ShimTransferSpans > shimSpans
Definition AIEPlacer.h:434
std::optional< TileID > getPlacement(mlir::Operation *logicalTile) const
Definition AIEPlacer.h:133
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
Definition AIEPlacer.h:561
llvm::MapVector< mlir::Operation *, std::array< ShimSide, 2 > > ShareableShimEnds
Definition AIEPlacer.h:234
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
Definition AIEPlacer.h:508
mlir::LogicalResult emitNamedClash(mlir::Operation *tile, TileID at, std::pair< mlir::Operation *, std::pair< int, int > > clash) const
static CollectedOps collectOperations(DeviceOp device)
Definition AIEPlacer.cpp:95
llvm::SmallVector< DdrGroup > ddrGroups
Definition AIEPlacer.h:448
virtual void initialize(DeviceOp device, bool controlOverlay, bool adaptiveOverlay, bool packetSwitched)
Definition AIEPlacer.cpp:62
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)
Definition AIEUtils.cpp:578
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)
Definition AIEPlacer.h:568
bool isPacketSwitched(PacketInfoAttr header, bool packetSwDefault)
Definition AIEDialect.h:520
llvm::DenseMap< mlir::Operation *, TileID > PlacementResult
Definition AIEPlacer.h:79
bool getsColumnControlOverlay(DeviceOp device, bool configuration)
void forEachMemAffinityNeighbor(const AIETargetModel &targetModel, TileID at, F &&fn)
Definition AIEPlacer.h:597
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.
Definition AIEPlacer.h:37
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)
Definition AIEPlacer.h:588
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)
Definition AIEPlacer.cpp:42
llvm::DenseMap< mlir::Operation *, llvm::SmallVector< unsigned, 2 > > tileToEdges
Definition AIEPlacer.h:152
void addEdgeFromValues(mlir::Value a, mlir::Value b)
Definition AIEPlacer.cpp:53
llvm::SmallVector< std::pair< TileLike, TileLike >, 4 > edges
Definition AIEPlacer.h:150
llvm::SmallVector< RouteOp > routes
Definition AIEPlacer.h:174
llvm::SmallVector< ObjectFifoLinkOp > objectFifoLinks
Definition AIEPlacer.h:169
llvm::SmallVector< CascadeFlowOp > cascadeFlows
Definition AIEPlacer.h:171
llvm::DenseMap< mlir::Operation *, unsigned > rank
Definition AIEPlacer.h:176
llvm::SmallVector< PacketFlowOp > pktFlows
Definition AIEPlacer.h:173
llvm::SmallVector< FlowOp > flows
Definition AIEPlacer.h:172
llvm::SmallVector< ObjectFifoCreateOp > objectFifos
Definition AIEPlacer.h:168
llvm::SmallVector< ObjectFifoAllocateOp > objectFifoAllocates
Definition AIEPlacer.h:170
llvm::SmallVector< LogicalTileOp > logicalTiles
Definition AIEPlacer.h:167
llvm::SmallVector< int64_t > weights
Definition AIEPlacer.h:445
llvm::SmallVector< llvm::BitVector > together
Definition AIEPlacer.h:446
llvm::SmallVector< mlir::Operation * > tiles
Definition AIEPlacer.h:444
llvm::SmallVector< mlir::StringAttr > ends
Definition AIEPlacer.h:227
llvm::SmallVector< int > pinned
Definition AIEPlacer.h:230
llvm::SmallVector< std::pair< int, llvm::SmallVector< mlir::StringAttr > > > shared
Definition AIEPlacer.h:229
llvm::SmallVector< mlir::Operation *, 2 > dsts
Definition AIEPlacer.h:519
mlir::Operation * delegate
Definition AIEPlacer.h:523
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
Definition AIEPlacer.h:83
std::vector< TileID > overBudgetCompTiles
Definition AIEPlacer.h:98
void removeTile(TileID tile, AIETileType type)
std::vector< TileID > nonCompTiles
Definition AIEPlacer.h:84
llvm::DenseSet< TileID > compTilesSet
Definition AIEPlacer.h:93