MLIR-AIE 1.4.6.dev
AIESAPlacer.cpp
Go to the documentation of this file.
1//===- AIESAPlacer.cpp ------------------------------------------*- C++ -*-===//
2//
3// Copyright (C) 2026 Advanced Micro Devices, Inc.
4// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
5//
6//===----------------------------------------------------------------------===//
7
12#include "llvm/ADT/BitVector.h"
13#include "llvm/ADT/MapVector.h"
14#include "llvm/Support/Debug.h"
15
16#include <algorithm>
17#include <chrono>
18#include <cmath>
19#include <limits>
20#include <numeric>
21
22using namespace mlir;
23using namespace xilinx::AIE;
24
25#define DEBUG_TYPE "aie-sa-placer"
26
27// The std:: distributions and std::shuffle are implementation-defined, so the
28// same seed yields different placements under libstdc++ and MSVC. These
29// helpers consume raw std::mt19937 output, which the standard fixes.
30
31/// Draw an index in [0, upperExclusive).
32static size_t drawBoundedIndex(std::mt19937 &rng, size_t upperExclusive) {
33 return static_cast<size_t>(rng()) % upperExclusive;
34}
35
36/// Draw a double in [0, 1).
37static double drawUnitReal(std::mt19937 &rng) {
38 constexpr double denominator = static_cast<double>(std::mt19937::max()) + 1.0;
39 return static_cast<double>(rng()) / denominator;
40}
41
42/// Fisher-Yates shuffle.
43static void deterministicShuffle(MutableArrayRef<TileID> values,
44 std::mt19937 &rng) {
45 for (size_t i = values.size(); i > 1; --i)
46 std::swap(values[i - 1], values[drawBoundedIndex(rng, i)]);
47}
48
49/// Return the neighbouring tiles an aie.objectfifo.allocate can move a fifo
50/// with both ends on `tilePos` to, by the rule split checks it with.
51static SmallVector<TileID>
52getMemAffinityNeighbors(const AIETargetModel &targetModel, TileID tilePos) {
53 SmallVector<TileID> neighbors;
54 for (std::optional<TileID> candidate :
55 {targetModel.getMemWest(tilePos), targetModel.getMemEast(tilePos),
56 targetModel.getMemNorth(tilePos), targetModel.getMemSouth(tilePos)})
57 if (candidate && *candidate != tilePos &&
58 ObjectFifoCreateOp::delegateReaches(targetModel, *candidate, tilePos,
59 tilePos))
60 neighbors.push_back(*candidate);
61 return neighbors;
62}
63
64/// Bytes a buffer takes on a tile once assign-buffer-addresses aligns it.
65static int64_t alignedBufferBytes(const AIETargetModel &targetModel,
66 AIETileType tileType, int64_t bytes) {
67 TileMemoryLimits limits = tileMemoryLimits(targetModel, tileType);
68 return llvm::alignTo(bytes,
70 limits.maxVecAlignBits, bytes) /
71 8);
72}
73
74//===----------------------------------------------------------------------===//
75// SASchedule
76//===----------------------------------------------------------------------===//
77
78SASchedule::SASchedule(double startTemp, int movesPerIter, int maxIters,
79 int greedyIters, const SAConfig &cfg)
80 : temperature(startTemp), movesPerIter(movesPerIter), maxIters(maxIters),
81 greedyIters(greedyIters),
82 windowSize(std::max(movesPerIter, cfg.windowSize)), config(cfg) {}
83
85 return currIteration >= maxIters ||
86 (inGreedyStage && currGreedyIteration >= greedyIters);
87}
88
90 int total = acceptCount + rejectCount;
91 return (total == 0) ? 1.0 : static_cast<double>(acceptCount) / total;
92}
93
94void SASchedule::record(bool accepted) {
95 history.push_back(accepted ? 1 : 0);
96 ++(accepted ? acceptCount : rejectCount);
97 trimWindow();
98}
99
101 if (!inGreedyStage) {
102 double ratio = getAcceptanceRatio();
103 double adaptiveFactor;
104 if (ratio > 0.96)
105 adaptiveFactor = config.coolFast;
106 else if (ratio > 0.8)
107 adaptiveFactor = config.coolSteady;
108 else if (ratio > 0.15)
109 adaptiveFactor = config.coolBalanced;
110 else
111 adaptiveFactor = config.coolStuck;
112
113 temperature *= adaptiveFactor;
114
115 if (ratio < config.greedyThreshold || temperature < 1e-8) {
116 inGreedyStage = true;
117 temperature = 0.0;
118 }
119 } else {
120 currGreedyIteration++;
121 }
122 currIteration++;
123}
124
125void SASchedule::trimWindow() {
126 while (static_cast<int>(history.size()) > windowSize) {
127 if (history.front() == 1)
128 acceptCount--;
129 else
130 rejectCount--;
131 history.pop_front();
132 }
133}
134
135//===----------------------------------------------------------------------===//
136// Net model
137//===----------------------------------------------------------------------===//
138
139void SAPlacer::buildNetModel(SmallVector<ObjectFifoCreateOp> &objectFifos,
140 SmallVector<ObjectFifoLinkOp> &objectFifoLinks) {
141 nets.clear();
142 tileToNetIndices.clear();
143
144 for (auto ofOp : objectFifos) {
145 NetInfo net;
146 Value producerTile = ofOp.getProducerTile();
147 if (auto *prodOp = producerTile.getDefiningOp())
148 if (isa<LogicalTileOp>(prodOp))
149 net.endpoints.push_back(prodOp);
150
151 for (Value consumerTile : ofOp.getConsumerTiles()) {
152 if (auto *consOp = consumerTile.getDefiningOp())
153 if (isa<LogicalTileOp>(consOp))
154 net.endpoints.push_back(consOp);
155 }
156
157 // Skip degenerate nets (0-1 endpoints)
158 if (net.endpoints.size() < 2)
159 continue;
160
161 // Cost increase for large multicast
162 net.isMulticast = (ofOp.getConsumerTiles().size() >
163 static_cast<unsigned>(config.multicastThreshold));
164
165 size_t idx = nets.size();
166 nets.push_back(net);
167
168 // Build reverse index
169 for (auto *ep : net.endpoints)
170 tileToNetIndices[ep].push_back(idx);
171 }
172}
173
174// A route is a net over the tiles of its ends, and each DMA end is one channel
175// on its tile; a pool is bytes on its tile, and descriptors when the tile is a
176// mem tile. None of it needs the DMA-or-shared-memory guess a fifo needs: a
177// route already moves data by DMA.
178void SAPlacer::buildRouteModel(
179 DeviceOp device, ArrayRef<FlowOp> flows, ArrayRef<PacketFlowOp> pktFlows,
180 ArrayRef<RouteOp> routes,
181 ArrayRef<DMAChannelAnalysis::ChannelClaim> claims) {
182 routeEnds.clear();
183 namedChannels.clear();
184 for (auto &[tile, inOut] :
185 flowChannelDemand(flows, pktFlows, routes, claims, &namedChannels)) {
186 for (int i = 0; i < inOut.first; ++i)
187 routeEnds.push_back({tile, /*output=*/false});
188 for (int i = 0; i < inOut.second; ++i)
189 routeEnds.push_back({tile, /*output=*/true});
190 }
191 for (RouteOp route : routes) {
192 NetInfo net;
193 auto addEnd = [&](StringRef name, bool output) {
194 auto endpoint = SymbolTable::lookupNearestSymbolFrom<RouteEndpoint>(
195 route, StringAttr::get(route.getContext(), name));
196 if (!endpoint)
197 return;
198 Operation *tileOp = endpoint.getTile().getDefiningOp();
199 if (!isa_and_nonnull<LogicalTileOp>(tileOp))
200 return;
201 net.endpoints.push_back(tileOp);
202 };
203 for (StringRef source : route.getSourceNames())
204 addEnd(source, /*output=*/true);
205 for (StringRef dest : route.getDestinationNames())
206 addEnd(dest, /*output=*/false);
207 if (net.endpoints.size() < 2)
208 continue;
209 unsigned threshold = static_cast<unsigned>(config.multicastThreshold);
210 net.isMulticast = route.getDestinations().size() > threshold ||
211 route.getSources().size() > threshold;
212 size_t idx = nets.size();
213 nets.push_back(net);
214 for (auto *ep : net.endpoints)
215 tileToNetIndices[ep].push_back(idx);
216 }
217
218 for (auto pool : device.getOps<ObjectFifoPoolOp>()) {
219 Operation *tileOp = pool.getTile().getDefiningOp();
220 if (!isa_and_nonnull<TileLike>(tileOp))
221 continue;
222 staticBufferSizes[tileOp] += pool.getObjectSizeInBytes() * pool.getDepth();
223 }
224 // Ends already split count the BD ids they take; other DMA ends only hold
225 // a channel.
226 for (auto endpoint : device.getOps<RouteEndpoint>()) {
227 auto tile = dyn_cast_or_null<TileLike>(endpoint.getTile().getDefiningOp());
228 if (endpoint.getRouteBundle() != WireBundle::DMA || !tile ||
229 tile.getTileType() != AIETileType::MemTile)
230 continue;
231 std::optional<int> channel = endpoint.getRouteChannel();
232 PlannedDmaEnd end{0, nullptr, -1, 0, false, 0, 0, channel};
233 if (auto dma = dyn_cast<ObjectFifoDmaEndpointOp>(endpoint.getOperation())) {
234 ObjectFifoPoolOp pool = dma.getPoolOp();
235 end = {dma.getNumBDs(),
236 pool,
237 -1,
238 pool.getDepth(),
239 pool.canWalkWhole(),
240 pool.getObjectSizeInBytes(),
241 pool.getContiguous() ? pool.getObjectsPerBuffer() : 0,
242 channel};
243 }
244 memTileEnds[tile].push_back({endpoint.getRouteDirection(), end});
245 }
246}
247
248int SAPlacer::computeNetHPWL(const NetInfo &net) const {
249 int spanCol = net.bb.maxCol - net.bb.minCol;
250 int spanRow = net.bb.maxRow - net.bb.minRow;
251 int hpwl = spanCol + spanRow;
252 if (net.isMulticast)
253 hpwl *= config.multicastMultiplier;
254 // Area penalty: penalizes spread-out nets that consume more routing tracks.
255 // A row-aligned broadcast (area=0) is much cheaper to route than a
256 // scattered one (area=cols*rows).
257 int area = spanCol * spanRow;
258 return hpwl + area;
259}
260
261int SAPlacer::computeTotalHPWL() const {
262 int total = 0;
263 for (const auto &net : nets)
264 total += computeNetHPWL(net);
265 return total;
266}
267
268void SAPlacer::initBoundingBoxes() {
269 for (auto &net : nets) {
270 if (net.endpoints.empty())
271 continue;
272
273 TileID first = currentPlacement[net.endpoints[0]];
274 net.bb = {first.col, first.col, first.row, first.row, 1, 1, 1, 1};
275
276 for (size_t i = 1; i < net.endpoints.size(); i++) {
277 TileID pos = currentPlacement[net.endpoints[i]];
278
279 if (pos.col < net.bb.minCol) {
280 net.bb.minCol = pos.col;
281 net.bb.countAtMinCol = 1;
282 } else if (pos.col == net.bb.minCol) {
283 net.bb.countAtMinCol++;
284 }
285
286 if (pos.col > net.bb.maxCol) {
287 net.bb.maxCol = pos.col;
288 net.bb.countAtMaxCol = 1;
289 } else if (pos.col == net.bb.maxCol) {
290 net.bb.countAtMaxCol++;
291 }
292
293 if (pos.row < net.bb.minRow) {
294 net.bb.minRow = pos.row;
295 net.bb.countAtMinRow = 1;
296 } else if (pos.row == net.bb.minRow) {
297 net.bb.countAtMinRow++;
298 }
299
300 if (pos.row > net.bb.maxRow) {
301 net.bb.maxRow = pos.row;
302 net.bb.countAtMaxRow = 1;
303 } else if (pos.row == net.bb.maxRow) {
304 net.bb.countAtMaxRow++;
305 }
306 }
307 }
308}
309
310//===----------------------------------------------------------------------===//
311// Incremental move evaluation
312//===----------------------------------------------------------------------===//
313
314int SAPlacer::evaluateMove(
315 Operation *tile, TileID newPos,
316 SmallVector<std::pair<size_t, NetBoundingBox>> &backups) {
317 backups.clear();
318 int deltaCost = 0;
319
320 auto it = tileToNetIndices.find(tile);
321 if (it == tileToNetIndices.end())
322 return 0;
323
324 for (size_t netIdx : it->second) {
325 NetInfo &net = nets[netIdx];
326 backups.push_back({netIdx, net.bb});
327 int oldCost = computeNetHPWL(net);
328
329 // Recompute BB from scratch for this net
330 int newMinCol = INT_MAX, newMaxCol = INT_MIN;
331 int newMinRow = INT_MAX, newMaxRow = INT_MIN;
332 int cMinCol = 0, cMaxCol = 0, cMinRow = 0, cMaxRow = 0;
333
334 for (auto *ep : net.endpoints) {
335 TileID pos = (ep == tile) ? newPos : currentPlacement[ep];
336
337 if (pos.col < newMinCol) {
338 newMinCol = pos.col;
339 cMinCol = 1;
340 } else if (pos.col == newMinCol) {
341 cMinCol++;
342 }
343 if (pos.col > newMaxCol) {
344 newMaxCol = pos.col;
345 cMaxCol = 1;
346 } else if (pos.col == newMaxCol) {
347 cMaxCol++;
348 }
349 if (pos.row < newMinRow) {
350 newMinRow = pos.row;
351 cMinRow = 1;
352 } else if (pos.row == newMinRow) {
353 cMinRow++;
354 }
355 if (pos.row > newMaxRow) {
356 newMaxRow = pos.row;
357 cMaxRow = 1;
358 } else if (pos.row == newMaxRow) {
359 cMaxRow++;
360 }
361 }
362
363 net.bb = {newMinCol, newMaxCol, newMinRow, newMaxRow,
364 cMinCol, cMaxCol, cMinRow, cMaxRow};
365
366 deltaCost += computeNetHPWL(net) - oldCost;
367 }
368
369 return deltaCost;
370}
371
372void SAPlacer::revertMove(
373 SmallVector<std::pair<size_t, NetBoundingBox>> &backups) {
374 for (auto &[netIdx, savedBB] : backups)
375 nets[netIdx].bb = savedBB;
376}
377
378//===----------------------------------------------------------------------===//
379// Move generation
380//===----------------------------------------------------------------------===//
381
382bool SAPlacer::isLegalPosition(Operation *tile, TileID pos) const {
383 auto it = tileTypes.find(tile);
384 if (it == tileTypes.end())
385 return false;
386
387 AIETileType needed = it->second;
388 AIETileType actual = targetModel->getTileType(pos.col, pos.row);
389 if (needed != actual)
390 return false;
391
392 // Compute tiles: must be unoccupied
393 if (needed == AIETileType::CoreTile) {
394 auto occIt = physToLogical.find(pos);
395 if (occIt != physToLogical.end() && occIt->second != tile)
396 return false;
397 }
398
399 return satisfiesConstraints(tile, pos) &&
400 !namedClash(tile, namedAt(tile, pos));
401}
402
403SmallVector<Operation *> SAPlacer::namedAt(Operation *tile, TileID pos,
404 Operation *leaving) const {
405 SmallVector<Operation *> here;
406 if (!namedChannels.contains(tile))
407 return here;
408 for (auto &[other, named] : namedChannels)
409 if (other != tile && other != leaving && positionOf(other) == pos)
410 here.push_back(other);
411 return here;
412}
413
414//===----------------------------------------------------------------------===//
415// Memory capacity tracking
416//===----------------------------------------------------------------------===//
417
418std::optional<TileID> SAPlacer::positionOf(Operation *tile) const {
419 if (auto it = currentPlacement.find(tile);
420 tile && it != currentPlacement.end())
421 return it->second;
422 if (auto tileOp = dyn_cast_or_null<TileOp>(tile))
423 return tileOp.getTileID();
424 return std::nullopt;
425}
426
427// Add a single fifo's contributions to memory and DMA usage maps.
428void SAPlacer::addRouteEndContribution(size_t endIdx, int sign) {
429 const RouteEndInfo &end = routeEnds[endIdx];
430 std::optional<TileID> pos = positionOf(end.tile);
431 if (!pos)
432 return;
433 if (end.output)
434 currentDMAUsage[*pos].second += sign;
435 else
436 currentDMAUsage[*pos].first += sign;
437}
438
439void SAPlacer::addFifoContribution(size_t fifoIdx, int sign) {
440 const auto &fb = fifoBuffers[fifoIdx];
441 std::optional<TileID> prodAt = positionOf(fb.producerTile);
442 if (!prodAt)
443 return;
444 TileID prodPos = *prodAt;
445 const FifoEndTypes &types = fifoEndTypes[fifoIdx];
446 bool prodIsShim = isShimEndType(types.producer);
447
448 // A fifo that already has an aie.objectfifo.allocate keeps its shared-memory
449 // objects on that delegate tile.
450 std::optional<TileID> delegatePos = positionOf(fb.delegate);
451
452 // A fifo shared memory carries keeps one pool of sharedDepth() objects;
453 // otherwise each end off a shim keeps its own, except a link output's
454 // producer, whose objects are the link input's consumer pool.
455 bool prodCharged = false;
456 bool prodNeedsDMA = false;
457 // The producer's pool, or a shared one, holds the initial objects; a
458 // consumer's starts empty.
459 auto heldLocks = [&](int64_t depth) {
460 return PoolLocks::needsLocks(fb.unsynchronized, fb.initObjects, depth,
461 fb.producerCore, fb.rearmed);
462 };
463 auto addLocks = [&](TileID pos, int segments, int64_t depth, bool needed) {
464 if (!needed || !segments)
465 return;
466 SmallVector<int> counts =
467 LockPlan::groupCounts(*targetModel, depth, segments);
468 addLockDemand(pos, sign * std::accumulate(counts.begin(), counts.end(), 0));
469 };
470 using LinkPool = FifoBufferInfo::LinkPool;
471 auto chargeLinkPool = [&](TileID pos, const PlannedDmaEnd &end) {
472 int count = end.contiguousObjects ? 1 : end.depth;
473 int64_t bytes =
474 end.objectBytes * std::max<int64_t>(end.contiguousObjects, 1);
475 currentMemUsage[pos] +=
476 sign * count *
477 alignedBufferBytes(*targetModel,
478 targetModel->getTileType(pos.col, pos.row), bytes);
479 chargeCoreFifo(pos, bytes, sign * count);
480 };
481 // A link's ends keep no objects of their own, shared memory or not: the
482 // split builds the link's one pool on its tile.
483 bool prodLinked = fb.producerLinkPool != LinkPool::None;
484 if (const std::optional<PlannedDmaEnd> &plan = fb.producerLinkPlan) {
485 chargeLinkPool(prodPos, *plan);
486 addLocks(prodPos, fb.producerLinkSegments, plan->depth, true);
487 }
488
489 for (size_t ci = 0; ci < fb.consumerTiles.size(); ci++) {
490 std::optional<TileID> consAt = positionOf(fb.consumerTiles[ci]);
491 if (!consAt)
492 continue;
493 TileID consPos = *consAt;
494 bool consIsShim = isShimEndType(types.consumers[ci]);
495
496 using SharedMemory = AIETargetModel::SharedMemory;
497 SharedMemory shared = fb.forcesDMA
498 ? SharedMemory::None
499 : ObjectFifoCreateOp::sharedMemoryOf(
500 *targetModel, prodPos, consPos, delegatePos,
501 positionOf(fb.linkTile));
502 bool isSharedMem = shared != SharedMemory::None;
503 int64_t sharedBytes =
504 std::max(fb.producerSizeBytes, fb.consumerSizeBytes) * fb.sharedDepth;
505
506 int64_t sharedRaw = std::max(fb.producerRawBytes, fb.consumerRawBytes);
507 bool consLinked = fb.consumerLinkPools[ci] != LinkPool::None;
508 if (const std::optional<PlannedDmaEnd> &plan = fb.consumerLinkPlans[ci]) {
509 chargeLinkPool(consPos, *plan);
510 addLocks(consPos, fb.consumerLinkSegments[ci], plan->depth, true);
511 }
512 bool sharedPool = isSharedMem && !prodLinked && !consLinked;
513 if (prodPos == consPos && sharedPool) {
514 currentMemUsage[delegatePos.value_or(prodPos)] += sign * sharedBytes;
515 chargeCoreFifo(delegatePos.value_or(prodPos), sharedRaw,
516 sign * fb.sharedDepth);
517 if (ci == 0)
518 addLocks(delegatePos.value_or(prodPos), 1, fb.sharedDepth,
519 heldLocks(fb.sharedDepth));
520 } else if (sharedPool) {
521 TileID bufTile;
522 if (delegatePos) {
523 bufTile = *delegatePos;
524 } else if (shared == SharedMemory::Either) {
525 if (sign > 0) {
526 int64_t prodUsed = currentMemUsage.lookup(prodPos);
527 int64_t consUsed = currentMemUsage.lookup(consPos);
528 bufTile = (prodUsed <= consUsed) ? prodPos : consPos;
529 // Only track shared-mem destination for single-consumer fifos.
530 // allocate ops require all endpoints share access to the delegate
531 // tile, which is only guaranteed for single-consumer fifos.
532 if (fb.consumers.size() == 1)
533 sharedMemDestination[fifoIdx] = bufTile;
534 } else {
535 auto it = sharedMemDestination.find(fifoIdx);
536 bufTile = (it != sharedMemDestination.end()) ? it->second : prodPos;
537 }
538 } else if (shared == SharedMemory::Second) {
539 bufTile = consPos;
540 } else {
541 bufTile = prodPos;
542 }
543 currentMemUsage[bufTile] += sign * sharedBytes;
544 chargeCoreFifo(bufTile, sharedRaw, sign * fb.sharedDepth);
545 if (ci == 0)
546 addLocks(bufTile, 1, fb.sharedDepth, heldLocks(fb.sharedDepth));
547 } else if (!isSharedMem) {
548 if (!prodCharged && !prodLinked && !prodIsShim && !fb.linkSharedProd) {
549 currentMemUsage[prodPos] +=
550 sign * fb.producerSizeBytes * fb.producerDepth;
551 chargeCoreFifo(prodPos, fb.producerRawBytes, sign * fb.producerDepth);
552 if (fb.producerEnd)
553 addLocks(prodPos, 1, fb.producerDepth, heldLocks(fb.producerDepth));
554 prodCharged = true;
555 }
556 if (!consLinked && !consIsShim) {
557 currentMemUsage[consPos] +=
558 sign * fb.consumerSizeBytes * fb.consumerDepths[ci];
559 chargeCoreFifo(consPos, fb.consumerRawBytes,
560 sign * fb.consumerDepths[ci]);
561 if (fb.consumerEnds[ci])
562 addLocks(consPos, 1, fb.consumerDepths[ci], !fb.unsynchronized);
563 }
564 }
565
566 // DMA contribution: a fifo that shared memory carries does not run
567 // through the DMAs, back to its own tile as well. An end takes a channel
568 // of its own unless it is a stream port, a PLIO, or a merge's or
569 // dispatch's participant whose shared end another took.
570 if (!isSharedMem) {
571 bool plio = cast<ObjectFifoCreateOp>(fb.fifoOp).getPlio();
572 if (consIsShim ? !plio : fb.consumerEnds[ci].has_value())
573 drawChannel(consPos, false, fb.consumerPins[ci], sign);
574 prodNeedsDMA = prodIsShim ? !plio : fb.producerEnd.has_value();
575 }
576 }
577
578 if (prodNeedsDMA)
579 drawChannel(prodPos, true, fb.producerPin, sign);
580}
581
582void SAPlacer::drawChannel(TileID position, bool output,
583 const std::optional<PinnedChannels::End> &pin,
584 int sign) {
585 int taken = sign;
586 if (pin) {
587 taken = pinUse.place(position, *pin, sign);
588 pinLog.push_back({position, *pin, sign});
589 }
590 auto &[in, out] = currentDMAUsage[position];
591 (output ? out : in) += taken;
592}
593
594void SAPlacer::addLockDemand(TileID pos, int locks) {
595 int &demand = currentLockDemand[pos];
596 int held = targetModel->getNumLocks(pos.col, pos.row);
597 positionsOverLocks += (demand + locks > held) - (demand > held);
598 demand += locks;
599}
600
601void SAPlacer::initResourceTracking() {
602 currentMemUsage.clear();
603 currentLockDemand.clear();
604 positionsOverLocks = 0;
605 SmallVector<std::pair<unsigned, int64_t>> depths;
606 auto at = [this](Value tile) { return positionOf(tile.getDefiningOp()); };
607 for (auto [index, variable] : llvm::enumerate(variableLinks))
608 depths.push_back({index, variable.plan.depthAt(*targetModel, at)});
609 replanLinks(depths);
610 currentDMAUsage.clear();
611 pinUse = PinnedChannelUse(pinnedRule);
612 sharedMemDestination.clear();
613 coreFifoBuffers.clear();
614 coreFifoLog.clear();
615
616 auto typeOf = [&](Operation *tile) -> std::optional<AIETileType> {
617 if (auto it = tileTypes.find(tile); it != tileTypes.end())
618 return it->second;
619 if (auto placed = dyn_cast_or_null<TileOp>(tile))
620 return placed.getTileType();
621 return std::nullopt;
622 };
623 fifoEndTypes.clear();
624 for (const auto &fb : fifoBuffers) {
625 FifoEndTypes &types = fifoEndTypes.emplace_back();
626 types.producer = typeOf(fb.producerTile);
627 for (Operation *cons : fb.consumerTiles)
628 types.consumers.push_back(typeOf(cons));
629 }
630
631 // Build reverse index: tile → fifo indices
632 tileToFifoIndices.clear();
633 for (size_t i = 0; i < fifoBuffers.size(); i++) {
634 const auto &fb = fifoBuffers[i];
635 if (fb.producer)
636 tileToFifoIndices[fb.producer].push_back(i);
637 for (auto *cons : fb.consumers)
638 if (cons)
639 tileToFifoIndices[cons].push_back(i);
640 if (fb.delegate)
641 tileToFifoIndices[fb.delegate].push_back(i);
642 }
643
644 // Static buffers and stacks go first: a shared-memory fifo picks the emptier
645 // of its two tiles as it is added, and must see what they already hold.
646 for (auto &[op, bufSize] : staticBufferSizes)
647 if (std::optional<TileID> pos = positionOf(op))
648 currentMemUsage[*pos] += bufSize;
649 // Add core stack overhead (reserved by assign-buffer-addresses pass)
650 for (auto &[op, bytes] : stackSizes)
651 if (std::optional<TileID> pos = positionOf(op))
652 currentMemUsage[*pos] += bytes;
653
654 for (size_t i = 0; i < fifoBuffers.size(); i++)
655 addFifoContribution(i, +1);
656 coreUnplacedAt.clear();
657 for (auto &[op, _] : coreContents)
658 if (std::optional<TileID> pos = positionOf(op))
659 coreDirty.insert(*pos);
660 refreshCoreUnplaced();
661
662 tileToRouteEnds.clear();
663 for (size_t i = 0; i < routeEnds.size(); i++) {
664 tileToRouteEnds[routeEnds[i].tile].push_back(i);
665 addRouteEndContribution(i, +1);
666 }
667 for (auto &[tile, claims] : claimsOf)
668 if (std::optional<TileID> pos = positionOf(tile))
669 for (const DMAChannelAnalysis::ChannelClaim &claim : claims)
670 pinUse.claim(*pos, claim, 1);
671 homeLocks.clear();
672 for (auto &[tile, locks] : fixedLocks)
673 homeLocks[tile] += locks;
674 for (const InputLockGroup &group : inputLockGroups)
675 homeLocks[group.home] += group.locks;
676 for (auto &[tile, locks] : homeLocks)
677 if (std::optional<TileID> pos = positionOf(tile))
678 addLockDemand(*pos, locks);
679 for (auto &[at, locks] : placedLocks)
680 addLockDemand(at, locks);
681 runtimeBdAt.clear();
682 for (auto &[shim, peak] : runtimeBdIds.users())
683 if (std::optional<TileID> pos = positionOf(shim);
684 pos && !runtimeBdAt.contains(*pos))
685 chargeRuntimeBds(*pos);
686
687 spillTiles.clear();
688 for (auto &[op, _] : memTileEnds)
689 spillTiles.insert(op);
690 for (auto &[op, _] : memTileFixed)
691 spillTiles.insert(op);
692 spillTiles.insert(logicalMemTiles.begin(), logicalMemTiles.end());
693 delegateTermTiles.clear();
694 for (const auto &fb : fifoBuffers) {
695 if (!fb.delegate)
696 continue;
697 delegateTermTiles.insert(fb.delegate);
698 delegateTermTiles.insert(fb.producer);
699 delegateTermTiles.insert(fb.consumers.begin(), fb.consumers.end());
700 }
701 pairedTiles.clear();
702 for (const Adjacency *adj : {&cascadeAdjacency, &sharedMemAdjacency})
703 for (auto [first, second] : adj->edges) {
704 pairedTiles.insert(first.getOperation());
705 pairedTiles.insert(second.getOperation());
706 }
707
708 memSpilloverPenalty = computeMemSpilloverPenalty();
709 bdCountPenalty = computeBDCountPenalty();
710 delegatePenalty = computeDelegatePenalty();
711 dmaPenalty = computeDMAChannelPenalty();
712 coreOverflowTiles = overflowingCoreTiles();
713 coreOverflowPenalty = computeCoreOverflowPenalty();
714 cuts = StreamCuts(*targetModel);
715 portsAt.clear();
716 columnSouthPorts.clear();
717 for (int col = 0; col < targetModel->columns(); ++col) {
718 for (int row = 0; row < targetModel->rows(); ++row)
719 portsAt.push_back(
720 {static_cast<int>(targetModel->getNumSourceSwitchboxConnections(
721 col, row, WireBundle::North)),
722 static_cast<int>(targetModel->getNumDestSwitchboxConnections(
723 col, row, WireBundle::North)),
724 static_cast<int>(targetModel->getNumSourceSwitchboxConnections(
725 col, row, WireBundle::South)),
726 static_cast<int>(targetModel->getNumDestSwitchboxConnections(
727 col, row, WireBundle::South))});
728 // A column's cores take their objectFIFOs through its lowest core's
729 // South ports.
730 int bottom = 0;
731 while (bottom < targetModel->rows() &&
732 !targetModel->isCoreTile(col, bottom))
733 ++bottom;
734 columnSouthPorts.push_back(
735 bottom < targetModel->rows()
736 ? static_cast<int>(targetModel->getNumSourceSwitchboxConnections(
737 col, bottom, WireBundle::South))
738 : 0);
739 }
740 streamsAt.clear();
741 incomingAt.clear();
742 incomingCount.clear();
743 portsOver = 0;
744 for (auto &[op, _] : streamDemand)
745 if (std::optional<TileID> at = positionOf(op))
746 chargeStreams(op, *at, 1);
747 auto columnOf = [this](Operation *op) -> std::optional<int> {
748 std::optional<TileID> at = positionOf(op);
749 return at ? std::optional(at->col) : std::nullopt;
750 };
751 ddrScoreOf.clear();
752 ddrTotal = 0;
753 for (auto [index, group] : llvm::enumerate(ddrGroups)) {
754 int64_t score = ddrGroupSpread(group, columnOf, config.ddrWeight);
755 ddrScoreOf[index] = score;
756 ddrTotal += score;
757 }
758 ddrPenalty = static_cast<int>(ddrTotal);
759 keyAt.clear();
760 coresChanged = 0;
761 if (!neighbourCores.empty()) {
762 for (auto &[op, key] : coreKeys)
763 if (std::optional<TileID> at = positionOf(op))
764 keyAt[*at] = key;
765 llvm::SmallVector<TileID> positions;
766 for (auto &[at, key] : keyAt)
767 positions.push_back(at);
768 for (const DenseMap<TileID, unsigned> &neighbour : neighbourCores)
769 for (auto &[at, key] : neighbour)
770 positions.push_back(at);
771 llvm::sort(positions);
772 positions.erase(llvm::unique(positions), positions.end());
773 for (TileID at : positions)
774 coresChanged += coresChangedAt(at);
775 }
776 netStreams.clear();
777 auto placed = [this](Operation *op) { return positionOf(op); };
778 for (auto [index, net] : llvm::enumerate(streamNets)) {
779 auto &[src, dsts] = netStreams[index];
780 if (streamOf(net, placed, src, dsts))
781 cuts.add(src, dsts, net.packet, 1);
782 }
783 streamCutPenalty = config.streamCutPenaltyPerChannel * cuts.over();
784 cachedResourcePenalty = memSpilloverPenalty + coreOverflowPenalty +
785 computeLockPenalty() + dmaPenalty + bdCountPenalty +
786 delegatePenalty + streamCutPenalty;
787 cachedPressure = computeMemoryPressure() + computeSoftTerms();
788}
789
790int SAPlacer::portExcess(TileID at) const {
791 StreamDemand streams = streamsAt.lookup(at);
792 const StreamDemand &ports = portsAt[at.col * targetModel->rows() + at.row];
793 return std::max(0, streams.northIn - ports.northIn) +
794 std::max(0, streams.southIn - ports.southIn) +
795 std::max(0, streams.northOut - ports.northOut) +
796 std::max(0, streams.southOut - ports.southOut);
797}
798
799int SAPlacer::columnExcess(int col) const {
800 return std::max(0, incomingAt.lookup(col) - columnSouthPorts[col]);
801}
802
803void SAPlacer::chargeStreams(Operation *op, TileID at, int sign) {
804 auto demand = streamDemand.find(op);
805 if (demand == streamDemand.end())
806 return;
807 portsOver -= portExcess(at);
808 StreamDemand &streams = streamsAt[at];
809 streams.northIn += sign * demand->second.northIn;
810 streams.northOut += sign * demand->second.northOut;
811 streams.southIn += sign * demand->second.southIn;
812 streams.southOut += sign * demand->second.southOut;
813 portsOver += portExcess(at);
814 auto incoming = incomingFifos.find(op);
815 if (incoming == incomingFifos.end())
816 return;
817 portsOver -= columnExcess(at.col);
818 for (Operation *fifo : incoming->second) {
819 int &count = incomingCount[{at.col, fifo}];
820 if (!count || count + sign == 0)
821 incomingAt[at.col] += sign;
822 count += sign;
823 }
824 portsOver += columnExcess(at.col);
825}
826
827int SAPlacer::computeSoftTerms() const {
828 return static_cast<int>(config.streamNearWeight *
829 cuts.near(config.streamNearFraction) +
830 config.portOverWeight * portsOver + ddrPenalty +
831 config.coresChangedWeight * coresChanged);
832}
833
834int SAPlacer::coresChangedAt(TileID pos) const {
835 unsigned mine = keyAt.lookup(pos);
836 int writes = 0;
837 for (const DenseMap<TileID, unsigned> &neighbour : neighbourCores) {
838 unsigned theirs = neighbour.lookup(pos);
839 if (mine != theirs)
840 writes += (mine != 0) + (theirs != 0);
841 }
842 return writes;
843}
844
845int SAPlacer::computeMemoryPressure() const {
846 int64_t coreCapacity = targetModel->getLocalMemorySize();
847 int64_t memTileCapacity = targetModel->getMemTileSize();
848 int pressure = 0;
849
850 for (auto &[tilePos, used] : currentMemUsage) {
851 auto tileType = targetModel->getTileType(tilePos.col, tilePos.row);
852 if (targetModel->isShimNOCorPLTile(tilePos.col, tilePos.row))
853 continue;
854 int64_t capacity =
855 (tileType == AIETileType::MemTile) ? memTileCapacity : coreCapacity;
856 double utilization = static_cast<double>(used) / capacity;
857 if (utilization > config.pressureThreshold) {
858 double excess = (utilization - config.pressureThreshold) /
859 (1.0 - config.pressureThreshold);
860 pressure += static_cast<int>(config.pressurePerKB * excess * excess);
861 }
862 }
863 return pressure;
864}
865
866// The objectfifo split keeps an allocated fifo's objects where
867// ObjectFifoCreateOp::allocatedHome says, which both ends must reach.
868// Otherwise it moves a link's participant that does not own the link's pool by
869// DMA, and rejects any other allocate. A fifo that shares a link's pool must
870// fit it, or ObjectFifoAllocateOp's verifier rejects the placement.
871int SAPlacer::computeDelegatePenalty(SmallVectorImpl<TileID> *charged) const {
872 int penalty = 0;
873 for (const auto &fb : fifoBuffers) {
874 std::optional<TileID> delegatePos = positionOf(fb.delegate);
875 if (!delegatePos)
876 continue;
877 std::optional<TileID> prodPos = positionOf(fb.producerTile);
878 std::optional<TileID> consPos = positionOf(fb.consumerTiles.front());
879 if (!prodPos || !consPos)
880 continue;
881 std::optional<TileID> linkPos = positionOf(fb.linkTile);
882 bool home = ObjectFifoCreateOp::allocatedHome(
883 *targetModel, *prodPos, *consPos, *delegatePos, linkPos);
884 if (home ? fb.fitsLinkPool : fb.allocateFallsBackToDMA)
885 continue;
886 if (home) {
887 penalty += config.delegateWeightPerDist;
888 if (charged)
889 charged->append({*delegatePos, *prodPos, *consPos});
890 continue;
891 }
892 for (std::optional<TileID> held : {delegatePos, linkPos}) {
893 if (!held)
894 continue;
895 for (TileID end : {*prodPos, *consPos}) {
896 if (ObjectFifoCreateOp::delegateReaches(*targetModel, *held, end, end))
897 continue;
898 int dist =
899 std::abs(held->col - end.col) + std::abs(held->row - end.row);
900 penalty += config.delegateWeightPerDist * std::max(dist - 1, 1);
901 if (charged)
902 charged->append({*held, end});
903 }
904 }
905 }
906 return penalty;
907}
908
909// Charges by the KB what MemTileSpillSearch, in the allocator's attempt order,
910// cannot place.
911int SAPlacer::computeMemSpilloverPenalty(SmallVectorImpl<TileID> *charged) {
912 std::vector<int64_t> key;
913 auto keyPosition = [&](Operation *op) {
914 std::optional<TileID> at = positionOf(op);
915 key.push_back(at ? at->col : -1);
916 key.push_back(at ? at->row : -1);
917 };
918 for (auto &[op, _] : memTileEnds)
919 keyPosition(op);
920 for (auto &[op, _] : memTileFixed)
921 keyPosition(op);
922 for (Operation *tile : logicalMemTiles)
923 keyPosition(tile);
924 for (const VariableLink &variable : variableLinks)
925 key.push_back(variable.depth);
926 if (const int *known = charged ? nullptr : spillPenaltyOf.find(key))
927 return *known;
928
929 if (memTileIndex.empty())
930 for (int col = 0; col < targetModel->columns(); ++col)
931 for (int row = 0; row < targetModel->rows(); ++row)
932 if (targetModel->getTileType(col, row) == AIETileType::MemTile) {
933 memTileIndex[{col, row}] = memTiles.size();
934 memTiles.push_back({targetModel->getMemTileSize(), {}});
935 spillNeighbours[{col, row}] =
937 }
938 SmallVector<MemTileSpillSearch::Tile> tiles = memTiles;
939 const DenseMap<TileID, unsigned> &index = memTileIndex;
940 auto neighboursOf = [&](TileID at) {
941 auto it = spillNeighbours.find(at);
942 return it != spillNeighbours.end()
943 ? it->second
945 };
946 for (auto &[op, fixed] : memTileFixed)
947 if (std::optional<TileID> at = positionOf(op))
948 llvm::append_range(tiles[index.lookup(*at)].fixed, fixed);
949
950 // Each placed position's pools, with the sets of them it may walk whole.
951 struct Position {
952 TileID at;
953 llvm::MapVector<std::pair<Operation *, int>,
954 std::pair<const PlannedDmaEnd *, std::pair<int, int>>>
955 pools;
956 WalkSets sets;
957 SmallVector<int64_t> bytes;
958 };
959 // memTilesAt for every position, in one pass.
960 llvm::MapVector<TileID, SmallVector<Operation *>> tilesAt;
961 for (auto &[tile, _] : memTileEnds)
962 if (std::optional<TileID> at = positionOf(tile))
963 tilesAt[*at].push_back(tile);
964 SmallVector<Position> positions;
965 for (auto &[at, here] : tilesAt) {
966 Position &position = positions.emplace_back();
967 position.at = at;
968 (void)bdShortfall(at, here, &position.sets, &position.bytes);
969 for (Operation *op : here)
970 for (const MemTileEnd &end : memTileEnds.find(op)->second) {
971 const PlannedDmaEnd &plan = end.end;
972 auto split = dyn_cast_or_null<ObjectFifoPoolOp>(plan.pool);
973 if (!plan.pool || (split && split.getBuffers()))
974 continue;
975 auto &[first, demand] = position.pools[{plan.pool, plan.id}];
976 first = first ? first : &plan;
977 ++(end.dir == DMAChannelDir::S2MM ? demand.first : demand.second);
978 }
979 }
980 llvm::sort(positions, [](const Position &a, const Position &b) {
981 return std::make_pair(a.at.col, a.at.row) <
982 std::make_pair(b.at.col, b.at.row);
983 });
984 bool anyWalked =
985 !chargedPools.empty() || llvm::any_of(positions, [](const Position &p) {
986 return !p.sets.empty();
987 });
988
989 // Per pool of the positions `members`, in the allocator's size-first order,
990 // with each position walking the set `walk` gives it (none when null).
991 using Walk = const SmallVector<std::pair<Operation *, int>> *;
992 auto unsortedShapes = [&](ArrayRef<unsigned> members, ArrayRef<Walk> walk) {
993 SmallVector<std::pair<SpillPool, TileID>> shaped;
994 for (unsigned member : members) {
995 const Position &position = positions[member];
996 unsigned home = index.lookup(position.at);
997 for (auto &[key, entry] : position.pools) {
998 auto [plan, demand] = entry;
999 int busier = std::max(demand.first, demand.second);
1000 int64_t whole = plan->contiguousObjects;
1001 if (!whole &&
1002 (chargedPools.contains(plan->pool) ||
1003 (walk[member] && llvm::is_contained(*walk[member], key))))
1004 whole = plan->depth;
1005 shaped.push_back({{plan->objectBytes * std::max<int64_t>(whole, 1),
1006 whole ? 1 : plan->depth, home, busier},
1007 position.at});
1008 }
1009 }
1010 return shaped;
1011 };
1012 auto shapes = [&](ArrayRef<unsigned> members, ArrayRef<Walk> walk) {
1013 SmallVector<std::pair<SpillPool, TileID>> shaped =
1014 unsortedShapes(members, walk);
1015 llvm::stable_sort(shaped, [](const auto &a, const auto &b) {
1016 return std::make_pair(a.second.col, a.second.row) <
1017 std::make_pair(b.second.col, b.second.row);
1018 });
1020 [](const auto &pool) { return pool.first.bytes; });
1021 return shaped;
1022 };
1023
1024 auto attempt = [&](ArrayRef<std::pair<SpillPool, TileID>> pools,
1025 ArrayRef<unsigned> order) {
1026 SmallVector<MemTileSpillSearch::Buffer> buffers;
1027 for (unsigned i : order) {
1028 auto [pool, at] = pools[i];
1029 SmallVector<unsigned, 2> neighbours;
1030 for (TileID neighbour : neighboursOf(at))
1031 if (auto it = index.find(neighbour); it != index.end())
1032 neighbours.push_back(it->second);
1033 buffers.append(pool.count, {pool.bytes, pool.home, true, neighbours});
1034 }
1035 MemTileSpillSearch search(tiles,
1036 targetModel->getMemTileLoadStoreBusWidth() / 8);
1037 return search.place(buffers) ? int64_t{0}
1038 : std::max<int64_t>(search.unplacedBytes, 1);
1039 };
1040 auto inOrder = [](size_t size) {
1041 return llvm::to_vector(llvm::seq<unsigned>(0, size));
1042 };
1043 // A component's outcome depends only on its tiles' contents and its walk
1044 // sets, so it is cached. bdShortfall's sets also depend on every tile at a
1045 // position whose programs hold channels or BD ids there.
1046 DenseMap<TileID, std::vector<Operation *>> opsAt;
1047 for (auto &[op, _] : memTileEnds)
1048 if (std::optional<TileID> at = positionOf(op))
1049 opsAt[*at].push_back(op);
1050 for (auto &[op, _] : memTileFixed)
1051 if (std::optional<TileID> at = positionOf(op))
1052 opsAt[*at].push_back(op);
1053 for (Operation *tile : logicalMemTiles)
1054 if (std::optional<TileID> at = positionOf(tile))
1055 opsAt[*at].push_back(tile);
1056 for (auto &[at, tiles] : physicalTiles)
1057 llvm::append_range(opsAt[at], tiles);
1058 for (auto &[_, ops] : opsAt) {
1059 llvm::sort(ops);
1060 ops.erase(llvm::unique(ops), ops.end());
1061 }
1062 SmallVector<TileID> homes =
1063 llvm::map_to_vector(positions, [](const Position &p) { return p.at; });
1064 SmallVector<unsigned> componentOf =
1065 memTileSpillComponents(homes, neighboursOf);
1066 unsigned components =
1067 componentOf.empty() ? 0 : *llvm::max_element(componentOf) + 1;
1068 SmallVector<Walk> walk(positions.size(), nullptr);
1069 int64_t unplaced = 0;
1070 bool anyOverfull = false;
1071 for (unsigned component = 0; component < components; ++component) {
1072 SmallVector<unsigned> members;
1073 for (auto [i, c] : llvm::enumerate(componentOf))
1074 if (c == component)
1075 members.push_back(i);
1076 std::vector<uintptr_t> tilesKey;
1077 SmallVector<std::pair<int, int>> reach;
1078 for (unsigned member : members) {
1079 reach.push_back({positions[member].at.col, positions[member].at.row});
1080 for (TileID n : neighboursOf(positions[member].at))
1081 reach.push_back({n.col, n.row});
1082 }
1083 llvm::sort(reach);
1084 reach.erase(llvm::unique(reach), reach.end());
1085 for (auto [col, row] : reach) {
1086 tilesKey.push_back(col);
1087 tilesKey.push_back(row);
1088 std::vector<Operation *> ops = opsAt.lookup({col, row});
1089 tilesKey.push_back(ops.size());
1090 for (Operation *op : ops)
1091 tilesKey.push_back(reinterpret_cast<uintptr_t>(op));
1092 }
1093 for (const VariableLink &variable : variableLinks)
1094 tilesKey.push_back(static_cast<uintptr_t>(variable.depth));
1095 SmallVector<SmallVector<int64_t>> bytes;
1096 for (unsigned member : members)
1097 bytes.push_back(positions[member].sets.empty() ? SmallVector<int64_t>{0}
1098 : positions[member].bytes);
1099 int64_t last = 0;
1100 auto places = [&](ArrayRef<unsigned> choice) {
1101 std::vector<uintptr_t> key = tilesKey;
1102 for (auto [member, set] : llvm::zip_equal(members, choice)) {
1103 key.push_back(set);
1104 walk[member] = positions[member].sets.empty()
1105 ? nullptr
1106 : &positions[member].sets[set];
1107 }
1108 if (const int64_t *known = unplacedOf.find(key))
1109 return (last = *known) == 0;
1110 auto shaped = shapes(members, walk);
1111 last = attempt(shaped, inOrder(shaped.size()));
1112 unplacedOf.record(key, last);
1113 return last == 0;
1114 };
1115 // Walking changes no buffer's bytes in total, so when the component's
1116 // buffers outweigh its tiles' room, no choice of walk sets places them.
1117 int64_t needed = 0, room = 0;
1118 for (auto &[pool, _] :
1119 unsortedShapes(members, SmallVector<Walk>(walk.size())))
1120 needed += pool.bytes * pool.count;
1121 for (auto [col, row] : reach) {
1122 room += targetModel->getMemTileSize();
1123 for (const BufferAllocation &buffer :
1124 tiles[index.lookup({col, row})].fixed)
1125 room -= buffer.size;
1126 }
1127 DMAChannelAnalysis::WalkChoice choice;
1128 choice.sets.assign(members.size(), 0);
1129 anyOverfull |= needed > room;
1130 if (needed <= room)
1131 choice = DMAChannelAnalysis::searchWalkProduct(bytes, places, 1);
1132 if (!choice.placed)
1133 (void)places(choice.sets);
1134 for (auto [member, set] : llvm::zip_equal(members, choice.sets))
1135 walk[member] = positions[member].sets.empty()
1136 ? nullptr
1137 : &positions[member].sets[set];
1138 unplaced += last;
1139 if (charged && last)
1140 for (unsigned member : members)
1141 charged->push_back(positions[member].at);
1142 }
1143 // An overfull component fails the whole-device attempt too.
1144 if (unplaced && !anyWalked && !anyOverfull) {
1145 SmallVector<unsigned> all =
1146 llvm::to_vector(llvm::seq<unsigned>(0, positions.size()));
1147 auto split = shapes(all, SmallVector<Walk>(positions.size(), nullptr));
1148 SmallVector<SpillPool> records;
1149 for (auto &[pool, _] : split)
1150 records.push_back(pool);
1151 if (!attempt(split, demandFirstOrder(records)))
1152 unplaced = 0;
1153 }
1154 int penalty = ((unplaced + 1023) / 1024) * config.memPenaltyPerKB;
1155 if (!charged)
1156 spillPenaltyOf.record(key, penalty);
1157 return penalty;
1158}
1159
1160// In position order: room that one tile is lent is gone for the next, so the
1161// order decides the outcome and must not follow the map's hashing.
1162SmallVector<TileID> SAPlacer::overflowingCoreTiles() const {
1163 SmallVector<TileID> tiles;
1164 for (auto &[tilePos, unplaced] : coreUnplacedAt)
1165 if (unplaced > 0)
1166 tiles.push_back(tilePos);
1167 llvm::sort(tiles);
1168 return tiles;
1169}
1170
1171void SAPlacer::chargeCoreFifo(TileID pos, int64_t bytes, int count) {
1172 if (count == 0 ||
1173 targetModel->getTileType(pos.col, pos.row) != AIETileType::CoreTile)
1174 return;
1175 BufferCounts &held = coreFifoBuffers[pos];
1176 if ((held[bytes] += count) == 0)
1177 held.erase(held.find(bytes));
1178 coreFifoLog.push_back({pos, bytes, count});
1179}
1180
1181int64_t SAPlacer::coreUnplaced(TileID pos, const BufferCounts &added,
1182 const BufferCounts &removed) const {
1183 SmallVector<const CoreTileContents *, 2> here;
1184 int numBanks = targetModel->getNumBanks(pos.col, pos.row);
1185 // The tile ops and objectFIFO buffers decide the layout, so they key it.
1186 std::vector<int64_t> tileKey = {numBanks};
1187 auto addOp = [&](Operation *op) {
1188 if (auto it = coreContents.find(op); it != coreContents.end()) {
1189 here.push_back(&it->second);
1190 tileKey.push_back(reinterpret_cast<intptr_t>(op));
1191 }
1192 };
1193 if (auto physical = physicalTiles.find(pos); physical != physicalTiles.end())
1194 for (Operation *op : physical->second)
1195 addOp(op);
1196 if (Operation *op = physToLogical.lookup(pos))
1197 if (auto at = currentPlacement.find(op);
1198 at != currentPlacement.end() && at->second == pos)
1199 addOp(op);
1200 tileKey.push_back(-1);
1201 static const BufferCounts none;
1202 auto held = coreFifoBuffers.find(pos);
1203 const BufferCounts &base =
1204 held == coreFifoBuffers.end() ? none : held->second;
1205 BufferCounts adjusted;
1206 if (!added.empty() || !removed.empty()) {
1207 adjusted = base;
1208 for (auto [bytes, count] : added)
1209 adjusted[bytes] += count;
1210 for (auto [bytes, count] : removed)
1211 adjusted[bytes] -= count;
1212 }
1213 const BufferCounts &fifo = added.empty() && removed.empty() ? base : adjusted;
1214 for (auto [bytes, count] : fifo)
1215 if (count > 0)
1216 tileKey.insert(tileKey.end(), {bytes, count});
1217 if (auto cached = coreUnplacedByTile.find(tileKey);
1218 cached != coreUnplacedByTile.end())
1219 return cached->second;
1220
1221 TileMemoryLimits limits =
1222 tileMemoryLimits(*targetModel, AIETileType::CoreTile);
1223 TileLayoutProblem problem;
1224 problem.numBanks = numBanks;
1225 problem.tileAlignBitWidth = limits.tileAlignBitWidth;
1226 problem.maxVecAlignBits = limits.maxVecAlignBits;
1227 problem.maxDataMemorySize = limits.maxDataMemorySize;
1228 problem.budget = config.placementBudget;
1229 for (auto [bytes, count] : fifo) {
1230 TileLayoutBuffer buffer;
1231 buffer.size = bytes;
1233 limits.maxVecAlignBits, bytes) /
1234 8;
1235 for (int i = 0; i < count; ++i)
1236 problem.buffers.push_back(buffer);
1237 }
1238 for (const CoreTileContents *contents : here) {
1239 llvm::append_range(problem.buffers, contents->buffers);
1240 if (contents->hasCore) {
1241 problem.hasCore = true;
1242 problem.stackRun = contents->stackRun;
1243 problem.stackBank = contents->stackBank;
1244 problem.stackAlignBytes = contents->stackAlignBytes;
1245 }
1246 }
1247
1248 // Different tiles holding the same buffers share a layout.
1249 std::vector<int64_t> key = {problem.numBanks,
1250 problem.hasCore,
1251 problem.stackRun.start,
1252 problem.stackRun.size,
1253 problem.stackBank.value_or(-1),
1254 problem.stackAlignBytes};
1255 for (const TileLayoutBuffer &buffer : problem.buffers) {
1256 key.insert(key.end(),
1257 {buffer.size, buffer.alignBytes, buffer.sectionAlignBytes,
1258 buffer.aligned, buffer.address.value_or(-1),
1259 buffer.memBank.value_or(-1), buffer.initialized,
1260 static_cast<int64_t>(buffer.spaceBanks.size())});
1261 llvm::append_range(key, buffer.spaceBanks);
1262 }
1263 // Both bounded, since a run meets more layouts than a design has tiles.
1264 if (coreUnplacedByTile.size() > (1u << 18))
1265 coreUnplacedByTile.clear();
1266 if (auto cached = coreUnplacedOf.find(key); cached != coreUnplacedOf.end()) {
1267 coreUnplacedByTile[std::move(tileKey)] = cached->second;
1268 return cached->second;
1269 }
1270 if (coreUnplacedOf.size() > (1u << 16))
1271 coreUnplacedOf.clear();
1272 // More bytes than the tile holds fail any layout, so the excess is
1273 // charged without searching for the bytes the search would leave.
1274 int64_t bytes = problem.stackRun.size;
1275 for (const TileLayoutBuffer &buffer : problem.buffers)
1276 bytes += buffer.size;
1277 if (bytes > problem.maxDataMemorySize) {
1278 int64_t excess = bytes - problem.maxDataMemorySize;
1279 coreUnplacedOf[std::move(key)] = excess;
1280 coreUnplacedByTile[std::move(tileKey)] = excess;
1281 return excess;
1282 }
1283 TileLayoutStats stats;
1284 TileLayout layout = layoutTile(problem, stats);
1285 int64_t unplaced = 0;
1286 if (layout.status == TileLayout::Status::NoRoom) {
1287 unplaced = layout.unplacedBytes;
1288 } else if (layout.status != TileLayout::Status::Placed) {
1289 // A pin or stack the tile cannot honour fails addressing whatever is
1290 // placed with it.
1291 for (const TileLayoutBuffer &buffer : problem.buffers)
1292 unplaced += buffer.size;
1293 unplaced = std::max<int64_t>(unplaced, 1);
1294 }
1295 coreUnplacedOf[std::move(key)] = unplaced;
1296 coreUnplacedByTile[std::move(tileKey)] = unplaced;
1297 return unplaced;
1298}
1299
1300SmallVector<TileID> SAPlacer::refreshCoreUnplaced() {
1301 // A fifo a move takes off a tile and puts back leaves it as it was.
1302 llvm::SmallDenseMap<std::pair<TileID, int64_t>, int, 8> net;
1303 for (auto &[pos, bytes, count] : coreFifoLog)
1304 net[{pos, bytes}] += count;
1305 for (auto &[charge, count] : net)
1306 if (count)
1307 coreDirty.insert(charge.first);
1308 SmallVector<TileID> changed;
1309 for (TileID pos : coreDirty) {
1310 if (targetModel->getTileType(pos.col, pos.row) != AIETileType::CoreTile)
1311 continue;
1312 coreUnplacedAt[pos] = coreUnplaced(pos);
1313 changed.push_back(pos);
1314 }
1315 coreDirty.clear();
1316 return changed;
1317}
1318
1319DenseSet<TileID> SAPlacer::coreOverflowReads() const {
1320 DenseSet<TileID> reads;
1321 for (TileID pos : coreOverflowTiles) {
1322 reads.insert(pos);
1323 for (TileID nbr : getMemAffinityNeighbors(*targetModel, pos))
1324 reads.insert(nbr);
1325 }
1326 return reads;
1327}
1328
1329int64_t
1330SAPlacer::planCoreFit(TileID pos, DenseMap<TileID, BufferCounts> &lent,
1331 SmallVectorImpl<std::pair<size_t, TileID>> *moves) const {
1332 // The intratile fifos an allocate can move to a neighbour, largest first,
1333 // then with the larger objects, then the one the core acquires first.
1334 SmallVector<std::pair<size_t, int64_t>, 8> relocatable;
1335 if (Operation *op = physToLogical.lookup(pos))
1336 if (auto fifoIt = tileToFifoIndices.find(op);
1337 fifoIt != tileToFifoIndices.end()) {
1338 DenseSet<size_t> seen;
1339 for (size_t fi : fifoIt->second) {
1340 if (!seen.insert(fi).second)
1341 continue;
1342 const auto &fb = fifoBuffers[fi];
1343 if (fb.consumers.size() != 1 || !fb.producer || !fb.consumers[0] ||
1344 fb.delegate || fb.forcesDMA)
1345 continue;
1346 auto prodIt = currentPlacement.find(fb.producer);
1347 auto consIt = currentPlacement.find(fb.consumers[0]);
1348 if (prodIt == currentPlacement.end() ||
1349 consIt == currentPlacement.end() || prodIt->second != pos ||
1350 consIt->second != pos)
1351 continue;
1352 relocatable.push_back(
1353 {fi, std::max(fb.producerSizeBytes, fb.consumerSizeBytes) *
1354 fb.sharedDepth});
1355 }
1356 }
1357 llvm::stable_sort(relocatable, [&](const auto &a, const auto &b) {
1358 const FifoBufferInfo &x = fifoBuffers[a.first];
1359 const FifoBufferInfo &y = fifoBuffers[b.first];
1360 return std::make_tuple(b.second,
1361 std::max(y.producerRawBytes, y.consumerRawBytes),
1362 firstAcquire.lookup_or(x.fifoOp, UINT_MAX),
1363 collected.rank.lookup(x.fifoOp)) <
1364 std::make_tuple(a.second,
1365 std::max(x.producerRawBytes, x.consumerRawBytes),
1366 firstAcquire.lookup_or(y.fifoOp, UINT_MAX),
1367 collected.rank.lookup(y.fifoOp));
1368 });
1369
1370 // Neighbours in position order, so the plan reads only the tiles' contents.
1371 SmallVector<TileID, 4> neighbours(getMemAffinityNeighbors(*targetModel, pos));
1372 llvm::sort(neighbours);
1373
1374 BufferCounts removed;
1375 for (auto [fi, size] : relocatable) {
1376 const auto &fb = fifoBuffers[fi];
1377 int64_t bytes = std::max(fb.producerRawBytes, fb.consumerRawBytes);
1378 for (TileID nbr : neighbours) {
1379 BufferCounts added = lent.lookup(nbr);
1380 added[bytes] += fb.sharedDepth;
1381 if (coreUnplaced(nbr, added) != 0)
1382 continue;
1383 lent[nbr] = std::move(added);
1384 removed[bytes] += fb.sharedDepth;
1385 if (moves)
1386 moves->push_back({fi, nbr});
1387 break;
1388 }
1389 }
1390 return coreUnplaced(pos, lent.lookup(pos), removed);
1391}
1392
1393int SAPlacer::computeCoreOverflowPenalty(
1394 SmallVectorImpl<TileID> *charged) const {
1395 int penalty = 0;
1396 // Room a neighbour gives one overflowing tile is gone for the next, as
1397 // generateAllocates hands it out.
1398 DenseMap<TileID, BufferCounts> lent;
1399 for (TileID tilePos : overflowingCoreTiles()) {
1400 int64_t unresolved = planCoreFit(tilePos, lent, nullptr);
1401 if (unresolved <= 0)
1402 continue;
1403 penalty += ((unresolved + 1023) / 1024) * config.memPenaltyPerKB;
1404 if (charged)
1405 charged->push_back(tilePos);
1406 }
1407 return penalty;
1408}
1409
1410SmallVector<std::pair<int, SmallVector<std::pair<TileID, bool>, 2>>>
1411SAPlacer::lockGroups() const {
1412 SmallVector<std::pair<int, SmallVector<std::pair<TileID, bool>, 2>>> groups;
1413 auto add = [&](const SmallVector<std::pair<TileID, bool>, 2> &users,
1414 int segments, int64_t depth) {
1415 for (int count : LockPlan::groupCounts(*targetModel, depth, segments))
1416 groups.push_back({count, users});
1417 };
1418 auto isCore = [](std::optional<AIETileType> type) {
1419 return type == AIETileType::CoreTile;
1420 };
1421 // A pool on an end's tile serves that end's core, if it uses the fifo, and
1422 // the tile's DMA.
1423 auto endUsers = [&](TileID at, bool core, std::optional<AIETileType> type) {
1424 SmallVector<std::pair<TileID, bool>, 2> users;
1425 if (core)
1426 users.push_back({at, false});
1427 users.push_back({at, isCore(type)});
1428 return users;
1429 };
1430 using LinkPool = FifoBufferInfo::LinkPool;
1431 for (size_t index = 0; index < fifoBuffers.size(); ++index) {
1432 const FifoBufferInfo &fb = fifoBuffers[index];
1433 std::optional<TileID> prodPos = positionOf(fb.producerTile);
1434 if (!prodPos)
1435 continue;
1436 auto heldLocks = [&](int64_t depth) {
1437 return PoolLocks::needsLocks(fb.unsynchronized, fb.initObjects, depth,
1438 fb.producerCore, fb.rearmed);
1439 };
1440 const FifoEndTypes &types = fifoEndTypes[index];
1441 std::optional<TileID> delegatePos = positionOf(fb.delegate);
1442 bool prodLinked = fb.producerLinkPool != LinkPool::None;
1443 if (const std::optional<PlannedDmaEnd> &plan = fb.producerLinkPlan)
1444 add(endUsers(*prodPos, fb.producerCore, types.producer),
1445 fb.producerLinkSegments, plan->depth);
1446 bool prodPool = false;
1447 for (size_t ci = 0; ci < fb.consumerTiles.size(); ++ci) {
1448 std::optional<TileID> consPos = positionOf(fb.consumerTiles[ci]);
1449 if (!consPos)
1450 continue;
1451 bool consLinked = fb.consumerLinkPools[ci] != LinkPool::None;
1452 if (const std::optional<PlannedDmaEnd> &plan = fb.consumerLinkPlans[ci])
1453 add(endUsers(*consPos, fb.consumerCore[ci], types.consumers[ci]),
1454 fb.consumerLinkSegments[ci], plan->depth);
1455 using SharedMemory = AIETargetModel::SharedMemory;
1456 if (!fb.forcesDMA && ObjectFifoCreateOp::sharedMemoryOf(
1457 *targetModel, *prodPos, *consPos, delegatePos,
1458 positionOf(fb.linkTile)) != SharedMemory::None) {
1459 if (prodLinked || consLinked || ci != 0 || !heldLocks(fb.sharedDepth))
1460 continue;
1461 SmallVector<std::pair<TileID, bool>, 2> users;
1462 if (fb.producerCore)
1463 users.push_back({*prodPos, false});
1464 if (fb.consumerCore[ci])
1465 users.push_back({*consPos, false});
1466 add(users, 1, fb.sharedDepth);
1467 continue;
1468 }
1469 if (!prodPool && !prodLinked && !isShimEndType(types.producer) &&
1470 !fb.linkSharedProd && fb.producerEnd) {
1471 prodPool = true;
1472 if (heldLocks(fb.producerDepth))
1473 add(endUsers(*prodPos, fb.producerCore, types.producer), 1,
1474 fb.producerDepth);
1475 }
1476 if (!consLinked && !isShimEndType(types.consumers[ci]) &&
1477 fb.consumerEnds[ci] && !fb.unsynchronized)
1478 add(endUsers(*consPos, fb.consumerCore[ci], types.consumers[ci]), 1,
1479 fb.consumerDepths[ci]);
1480 }
1481 }
1482 for (const InputLockGroup &group : inputLockGroups) {
1483 SmallVector<std::pair<TileID, bool>, 2> users;
1484 bool placed = true;
1485 for (auto [tile, localOnly] : group.users) {
1486 std::optional<TileID> at = positionOf(tile);
1487 placed &= at.has_value();
1488 if (at)
1489 users.push_back({*at, localOnly});
1490 }
1491 if (placed)
1492 groups.push_back({group.locks, users});
1493 }
1494 return groups;
1495}
1496
1497int SAPlacer::computeLockPenalty(bool *stopped,
1498 SmallVectorImpl<TileID> *charged) const {
1499 if (stopped)
1500 *stopped = false;
1501 // Each group taking its locks at home always fits there.
1502 if (!positionsOverLocks)
1503 return 0;
1504
1505 auto groups = lockGroups();
1506 SmallVector<TileID> positions;
1507 for (auto &[op, at] : currentPlacement)
1508 positions.push_back(at);
1509 llvm::append_range(positions, placedTiles);
1510 llvm::sort(positions, [](TileID a, TileID b) {
1511 return std::make_pair(a.col, a.row) < std::make_pair(b.col, b.row);
1512 });
1513 positions.erase(llvm::unique(positions), positions.end());
1514
1515 // The verdict reads the groups, the locks logical tiles hold and the
1516 // occupied positions a group may take: those its first user reaches, or
1517 // every one for a group without users. Placed tiles' locks never move.
1518 // Recording stops after a long run of misses, where moves seldom revisit.
1519 bool recording = !charged && lockVerdictMissRun < kLockVerdictMissRun;
1520 std::vector<int64_t> key;
1521 auto known = lockVerdicts.end();
1522 if (recording) {
1523 bool unanchored = false;
1524 int rows = targetModel->rows();
1525 BitVector reached(targetModel->columns() * rows);
1526 BitVector anchored(reached.size());
1527 SmallVector<TileID> anchors;
1528 for (auto &[locks, users] : groups) {
1529 llvm::append_values(key, locks, static_cast<int64_t>(users.size()));
1530 for (auto [at, localOnly] : users)
1531 llvm::append_values(key, at.col, at.row,
1532 static_cast<int64_t>(localOnly));
1533 if (users.empty())
1534 unanchored = true;
1535 else if (auto [first, localOnly] = users.front(); localOnly)
1536 reached.set(first.col * rows + first.row);
1537 else if (!anchored.test(first.col * rows + first.row)) {
1538 anchored.set(first.col * rows + first.row);
1539 anchors.push_back(first);
1540 }
1541 }
1542 for (TileID anchor : anchors)
1543 for (TileID at : lockReach.find(anchor)->second)
1544 reached.set(at.col * rows + at.row);
1545 key.push_back(-1);
1546 for (auto &[tile, locks] : fixedLocks) {
1547 std::optional<TileID> at = positionOf(tile);
1548 llvm::append_values(key, at ? at->col : -1, at ? at->row : -1, locks);
1549 }
1550 llvm::append_values(key, -1, static_cast<int64_t>(positions.empty()));
1551 for (TileID at : positions)
1552 if (unanchored || reached.test(at.col * rows + at.row))
1553 llvm::append_values(key, at.col, at.row);
1554 known = lockVerdicts.find(key);
1555 if (known != lockVerdicts.end()) {
1556 lockVerdictMissRun = 0;
1557#ifndef EXPENSIVE_CHECKS
1558 if (stopped)
1559 *stopped = known->second.second;
1560 return known->second.first;
1561#endif
1562 }
1563 }
1564
1565 LockPlan plan(*targetModel);
1566 DenseMap<TileID, unsigned> index;
1567 auto tileAt = [&](TileID at) {
1568 auto [entry, fresh] = index.try_emplace(at, 0);
1569 if (fresh)
1570 entry->second = plan.addTile({{at}, at});
1571 return entry->second;
1572 };
1573 int penalty = 0;
1574 for (auto &[tile, locks] : fixedLocks)
1575 if (std::optional<TileID> at = positionOf(tile))
1576 if (!plan.reserve(tileAt(*at), locks)) {
1577 penalty += locks * config.dmaPenaltyPerChannel;
1578 if (charged)
1579 charged->push_back(*at);
1580 }
1581 for (auto &[at, locks] : placedLocks)
1582 if (!plan.reserve(tileAt(at), locks)) {
1583 penalty += locks * config.dmaPenaltyPerChannel;
1584 if (charged)
1585 charged->push_back(at);
1586 }
1587 SmallVector<unsigned> ranked;
1588 for (TileID at : positions)
1589 ranked.push_back(tileAt(at));
1590 if (ranked.empty())
1591 return penalty;
1592 // A group may take the occupied positions all its users reach, so those
1593 // come from the first user's reach, not from every position.
1594 SmallVector<LockPlan::Group> planned;
1595 for (auto &[locks, users] : groups) {
1596 SmallVector<LockPlan::User> records;
1597 for (auto [at, localOnly] : users)
1598 records.push_back({tileAt(at), localOnly});
1599 auto reachesAt = [&](std::pair<TileID, bool> user, TileID at) {
1600 return user.first == at ||
1601 (!user.second &&
1602 llvm::is_contained(lockReach.find(user.first)->second, at));
1603 };
1604 SmallVector<unsigned> eligible;
1605 if (users.empty()) {
1606 eligible = ranked;
1607 } else {
1608 auto [first, localOnly] = users.front();
1609 for (TileID at : localOnly ? ArrayRef<TileID>(first)
1610 : ArrayRef(lockReach.find(first)->second))
1611 if (index.contains(at) &&
1612 llvm::all_of(users, [&](auto user) { return reachesAt(user, at); }))
1613 eligible.push_back(index.lookup(at));
1614 }
1615#ifdef EXPENSIVE_CHECKS
1616 for (unsigned tile : ranked)
1617 assert(llvm::is_contained(eligible, tile) ==
1618 llvm::all_of(records,
1619 [&](const LockPlan::User &user) {
1620 return plan.reaches(user, tile);
1621 }) &&
1622 "a lock group's tiles differ from those every user reaches");
1623#endif
1624 planned.push_back({locks, std::move(eligible), std::move(records)});
1625 }
1626 // Allocation places in its own order first, which the SA cannot know; the
1627 // canonical order alone fits only where allocation fits too.
1628 LockPlan::Assignment assignment =
1629 plan.assign(planned, &lockMemo, /*callerOrder=*/false);
1630 if (stopped)
1631 *stopped = assignment.stopped;
1632 for (auto [group, tile, grouped] :
1633 llvm::zip(planned, assignment.tiles, groups)) {
1634 if (tile)
1635 continue;
1636 penalty += group.count * config.dmaPenaltyPerChannel;
1637 if (charged)
1638 for (auto [at, localOnly] : grouped.second)
1639 charged->push_back(at);
1640 }
1641#ifdef EXPENSIVE_CHECKS
1642 assert((known == lockVerdicts.end() ||
1643 known->second == std::pair(penalty, assignment.stopped)) &&
1644 "a recorded lock verdict differs from a fresh one");
1645#endif
1646 if (recording && known == lockVerdicts.end()) {
1647 if (++lockVerdictMissRun == kLockVerdictMissRun) {
1648 decltype(lockVerdicts)().swap(lockVerdicts);
1649 lockVerdictBytes = 0;
1650 return penalty;
1651 }
1652 // Bounded by bytes, since moves reach more lock states than they revisit.
1653 key.shrink_to_fit();
1654 size_t bytes = key.capacity() * sizeof(int64_t);
1655 if (lockVerdictBytes + bytes > kLockVerdictBytes) {
1656 lockVerdicts.clear();
1657 lockVerdictBytes = 0;
1658 }
1659 lockVerdictBytes += bytes;
1660 lockVerdicts.emplace(std::move(key),
1661 std::pair(penalty, assignment.stopped));
1662 }
1663 return penalty;
1664}
1665
1666void SAPlacer::replanLinks(ArrayRef<std::pair<unsigned, int64_t>> depths) {
1667 auto at = [this](Value tile) { return positionOf(tile.getDefiningOp()); };
1668 SmallVector<unsigned> changed;
1669 for (auto [index, depth] : depths) {
1670 VariableLink &variable = variableLinks[index];
1671 if (depth == variable.depth)
1672 continue;
1673 variable.depth = depth;
1674 changed.push_back(index);
1675 }
1676 if (changed.empty())
1677 return;
1678 // A link whose tiles stayed keeps its depth, so these are every link's.
1679 std::vector<int64_t> all;
1680 for (const VariableLink &variable : variableLinks)
1681 all.push_back(variable.depth);
1682 for (unsigned index : changed) {
1683 VariableLink &variable = variableLinks[index];
1684 auto [replan, added] = variable.replans.try_emplace(all);
1685 if (added) {
1686 // The pool's plan is the first end's that names it, in fifo order, as
1687 // buildFifoBufferInfo took it.
1688 for (size_t fifoIndex : variable.fifos) {
1689 FifoBufferInfo &fb = fifoBuffers[fifoIndex];
1690 auto fifo = cast<ObjectFifoCreateOp>(fb.fifoOp);
1691 auto &ends = replan->second.ends.emplace_back();
1692 for (unsigned ci = 0, e = fb.consumerEnds.size(); ci < e; ++ci)
1693 ends.push_back(fifo.plannedDmaEnd(ci, at));
1694 ends.push_back(fifo.plannedDmaEnd(std::nullopt, at));
1695 for (const std::optional<PlannedDmaEnd> &end : ends)
1696 if (!replan->second.held && end &&
1697 end->pool == variable.link.getOperation())
1698 replan->second.held = end;
1699 }
1700 }
1701 for (auto [fifoIndex, ends] :
1702 llvm::zip_equal(variable.fifos, replan->second.ends)) {
1703 FifoBufferInfo &fb = fifoBuffers[fifoIndex];
1704 auto install = [&](std::optional<PlannedDmaEnd> &end,
1705 const std::optional<PlannedDmaEnd> &plan,
1706 std::optional<unsigned> entry, Operation *tile) {
1707 end = plan;
1708 if (entry)
1709 memTileEnds.find(tile)->second[*entry].end = *end;
1710 };
1711 for (unsigned ci = 0, e = fb.consumerEnds.size(); ci < e; ++ci)
1712 install(fb.consumerEnds[ci], ends[ci], fb.consumerMemTileEntries[ci],
1713 fb.consumerTiles[ci]);
1714 install(fb.producerEnd, ends.back(), fb.producerMemTileEntry,
1715 fb.producerTile);
1716 }
1717 for (auto [fifoIndex, consumer] : variable.holds) {
1718 FifoBufferInfo &fb = fifoBuffers[fifoIndex];
1719 (consumer ? fb.consumerLinkPlans[*consumer] : fb.producerLinkPlan) =
1720 replan->second.held;
1721 }
1722 }
1723}
1724
1725int SAPlacer::computeTileDMAPenalty(TileID tilePos, int *bdIds) const {
1726 auto usage = currentDMAUsage.lookup(tilePos);
1727 auto [maxIn, maxOut] = getDMACapacity(*targetModel, tilePos);
1728 SmallVector<Operation *> tilesHere;
1729 if (overlayChannels(tilePos))
1730 for (Operation *tile : overlayTiles)
1731 if (positionOf(tile) == tilePos)
1732 tilesHere.push_back(tile);
1733 OverlayFit overlay = overlayAt(tilePos, pinUse, {}, tilesHere,
1734 shimSpans ? &*shimSpans : nullptr);
1735 int used[2] = {usage.first, usage.second + overlay.channels};
1736 int max[2] = {maxIn, maxOut};
1737 // Two ends that cannot share a channel they both pin clash here wherever
1738 // the rest goes, and so does an overlay with nowhere to sit.
1739 int penalty =
1740 (pinUse.clashes(tilePos) + !overlay.fits) * config.dmaPenaltyPerChannel;
1741 for (int dir : {0, 1}) {
1742 if (used[dir] <= max[dir])
1743 continue;
1744 if (shimSpans && targetModel->getTileType(tilePos.col, tilePos.row) ==
1745 AIETileType::ShimNOCTile) {
1746 SmallVector<const ShimSide *> sides;
1747 for (auto &[lt, own] : shareableShimEnds) {
1748 if (positionOf(lt) == tilePos)
1749 sides.push_back(&own[dir]);
1750 }
1751 SmallVector<StringAttr> extra;
1752 if (dir == 1 && overlay.own)
1753 extra.push_back(shimSpans->overlayEnd(tilePos.col));
1754 used[dir] -= shimChannelsSaved(*shimSpans, sides, extra,
1755 pinUse.channelsAt(tilePos, dir == 1));
1756 }
1757 penalty += std::max(0, used[dir] - max[dir]) * config.dmaPenaltyPerChannel;
1758 }
1759 int ids = runtimeBdAt.lookup(tilePos);
1760 penalty += ids;
1761 if (bdIds)
1762 *bdIds = ids;
1763 return penalty;
1764}
1765
1766void SAPlacer::chargeRuntimeBds(TileID pos) {
1767 if (targetModel->getTileType(pos.col, pos.row) != AIETileType::ShimNOCTile)
1768 return;
1769 SmallVector<Operation *> onTile;
1770 for (auto &[lt, peak] : runtimeBdIds.users())
1771 if (auto at = currentPlacement.find(lt);
1772 at != currentPlacement.end() && at->second == pos)
1773 onTile.push_back(lt);
1774 runtimeBdAt[pos] =
1775 runtimeBdIds.shortfall(onTile, pos) * config.dmaPenaltyPerChannel;
1776}
1777
1778int SAPlacer::computeDMAChannelPenalty() {
1779 dmaPenaltyAt.clear();
1780 int penalty = 0;
1781 for (auto &[tilePos, _] : currentDMAUsage) {
1782 int at = computeTileDMAPenalty(tilePos);
1783 dmaPenaltyAt[tilePos] = at;
1784 penalty += at;
1785 }
1786 return penalty;
1787}
1788
1789SmallVector<Operation *> SAPlacer::memTilesAt(TileID position) const {
1790 SmallVector<Operation *> tiles;
1791 for (auto &[tile, ends] : memTileEnds)
1792 if (positionOf(tile) == position)
1793 tiles.push_back(tile);
1794 return tiles;
1795}
1796
1797int64_t SAPlacer::bdShortfall(TileID position, ArrayRef<Operation *> tiles,
1798 WalkSets *walkSets,
1799 SmallVector<int64_t> *walkBytes) {
1800 auto [layout, added] = bdLayoutOf.try_emplace(position, position);
1801 if (added) {
1802 auto access = [&](TileID at) {
1803 std::vector<bool> bits;
1804 int channels = targetModel->getNumSourceSwitchboxConnections(
1805 at.col, at.row, WireBundle::DMA);
1806 for (int channel = 0; channel < channels; ++channel)
1807 for (uint32_t bd = 0, e = targetModel->getNumBDs(at.col, at.row);
1808 bd < e; ++bd)
1809 bits.push_back(
1810 targetModel->isBdChannelAccessible(at.col, at.row, bd, channel));
1811 return bits;
1812 };
1813 for (auto &[other, rep] : bdLayoutOf)
1814 if (other == rep && !(other == position) &&
1815 access(other) == access(position)) {
1816 layout->second = other;
1817 break;
1818 }
1819 }
1820 // Bounded, since tiles meet at positions in more ways than a design has
1821 // positions. Every tile at the position holds what its programs take; a tile
1822 // with fixed coordinates is only ever here, so the list keys the position
1823 // too.
1824 SmallVector<Operation *> holders(tiles);
1825 for (Operation *tile : logicalMemTiles)
1826 if (auto at = currentPlacement.find(tile);
1827 at != currentPlacement.end() && at->second == position &&
1828 !llvm::is_contained(holders, tile))
1829 holders.push_back(tile);
1830 for (Operation *tile : physicalTiles.lookup(position))
1831 if (!llvm::is_contained(holders, tile))
1832 holders.push_back(tile);
1833 std::vector<uintptr_t> key = {static_cast<uintptr_t>(layout->second.col),
1834 static_cast<uintptr_t>(layout->second.row),
1835 holders.size()};
1836 for (Operation *tile : holders)
1837 key.push_back(reinterpret_cast<uintptr_t>(tile));
1838 for (const VariableLink &variable : variableLinks)
1839 key.push_back(static_cast<uintptr_t>(variable.depth));
1840 if (const BDShortfall *cached = bdShortfallOf.find(key)) {
1841 if (walkSets)
1842 *walkSets = cached->sets;
1843 if (walkBytes)
1844 *walkBytes = cached->bytes;
1845 return cached->ids;
1846 }
1847 SmallVector<const MemTileEnd *> ends;
1848 for (Operation *tile : tiles)
1849 if (auto *it = memTileEnds.find(tile); it != memTileEnds.end())
1850 for (const MemTileEnd &end : it->second)
1851 ends.push_back(&end);
1852 auto [col, row] = position;
1853 int channels[2] = {
1854 static_cast<int>(targetModel->getNumDestSwitchboxConnections(
1855 col, row, WireBundle::DMA)),
1856 static_cast<int>(targetModel->getNumSourceSwitchboxConnections(
1857 col, row, WireBundle::DMA))};
1858 // The plan asks about each channel many times, so each answer is kept.
1859 SmallVector<std::optional<bool>> freeChannels[2];
1860 for (SmallVector<std::optional<bool>> &known : freeChannels)
1861 known.resize(std::max(channels[0], channels[1]));
1862 auto free = [&](DMAChannelDir dir, int channel) {
1863 std::optional<bool> &known =
1864 freeChannels[dir == DMAChannelDir::MM2S][channel];
1865 if (!known)
1866 known = llvm::all_of(holders, [&](Operation *tile) {
1867 return channelAnalysis->isChannelFree(cast<TileLike>(tile), dir,
1868 channel);
1869 });
1870 return *known;
1871 };
1872 DenseMap<int, int64_t> taken = takenBDs.at(*targetModel, col, row, holders);
1873 auto spent = [&](int channel) { return taken.lookup(channel); };
1874 SmallVector<DMAChannelAnalysis::BDPlanEnd> planned;
1875 SmallVector<unsigned> poolOf;
1876 SmallVector<DMAChannelAnalysis::BDWalkPool> pools;
1877 SmallVector<std::pair<Operation *, int>> poolKeys;
1878 for (const MemTileEnd *end : ends) {
1879 std::pair<Operation *, int> poolKey{end->end.pool, end->end.id};
1880 auto *at = llvm::find(poolKeys, poolKey);
1881 if (at == poolKeys.end()) {
1882 poolKeys.push_back(poolKey);
1883 pools.push_back({end->end.depth, end->end.objectBytes, false});
1884 at = std::prev(poolKeys.end());
1885 }
1886 unsigned pool = at - poolKeys.begin();
1887 pools[pool].walkable |= end->end.walkable;
1888 poolOf.push_back(pool);
1889 planned.push_back({end->dir, end->end.bds,
1890 channels[end->dir == DMAChannelDir::MM2S],
1891 end->end.channel});
1892 }
1893 // The spill search tries only each position's cheapest set.
1894 DMAChannelAnalysis::BDWalkSets found = DMAChannelAnalysis::walkSetsThatFit(
1895 *targetModel, col, row, planned, poolOf, pools, free, spent,
1896 /*maxSets=*/1);
1897 WalkSets sets;
1898 for (ArrayRef<unsigned> set : found.sets)
1899 sets.push_back(llvm::map_to_vector(
1900 set, [&](unsigned pool) { return poolKeys[pool]; }));
1901 SmallVector<int64_t> bytes = found.bytes;
1902 int64_t shortfall = 0;
1903 if (found.channelShort || !found.fits) {
1904 // No set fits: every walkable pool is walked, and the ids still short
1905 // are charged; too few channels is the DMA term's to charge.
1906 if (!found.channelShort) {
1907 sets.emplace_back();
1908 bytes.push_back(0);
1909 for (auto [pool, walkable] : llvm::enumerate(pools))
1910 if (walkable.walkable) {
1911 sets.back().push_back(poolKeys[pool]);
1912 bytes.back() += walkable.depth * walkable.objectBytes;
1913 }
1914 }
1915 DenseSet<std::pair<Operation *, int>> whole;
1916 if (!sets.empty())
1917 whole.insert(sets.front().begin(), sets.front().end());
1918 int64_t total = 0;
1919 for (auto [end, pool] : llvm::zip_equal(planned, poolOf))
1920 total += whole.contains(poolKeys[pool]) ? 1 : end.bds;
1921 for (auto [channel, held] : taken)
1922 total += held;
1923 int64_t ids = targetModel->getNumBDs(col, row);
1924 shortfall = found.channelShort ? std::max<int64_t>(0, total - ids)
1925 : std::max<int64_t>(1, total - ids);
1926 }
1927 bdShortfallOf.record(std::move(key), {shortfall, sets, bytes});
1928 if (walkSets)
1929 *walkSets = std::move(sets);
1930 if (walkBytes)
1931 *walkBytes = std::move(bytes);
1932 return shortfall;
1933}
1934
1935// Penalizes mem tile positions whose ends' BD ids no channel plan fits.
1936int SAPlacer::computeBDCountPenalty() {
1937 bdShortfallAt.clear();
1938 int64_t penalty = 0;
1939 for (auto &[tile, ends] : memTileEnds) {
1940 std::optional<TileID> at = positionOf(tile);
1941 if (!at || bdShortfallAt.contains(*at))
1942 continue;
1943 int64_t shortfall = bdShortfall(*at, memTilesAt(*at));
1944 bdShortfallAt[*at] = shortfall;
1945 penalty += shortfall * config.dmaPenaltyPerChannel;
1946 }
1947 return static_cast<int>(penalty);
1948}
1949
1950int SAPlacer::computeAdjacencyPenalty(
1951 const Adjacency &adj, ArrayRef<std::pair<int, int>> validOffsets,
1952 int weight, SmallVectorImpl<TileID> *charged) const {
1953 int penalty = 0;
1954 for (auto [first, second] : adj.edges) {
1955 auto firstIt = currentPlacement.find(first.getOperation());
1956 auto secondIt = currentPlacement.find(second.getOperation());
1957 if (firstIt == currentPlacement.end() || secondIt == currentPlacement.end())
1958 continue;
1959
1960 TileID firstPos = firstIt->second;
1961 TileID secondPos = secondIt->second;
1962
1963 // Find minimum Manhattan distance to any valid offset.
1964 int minDist = INT_MAX;
1965 for (auto [dc, dr] : validOffsets) {
1966 int dist = std::abs(secondPos.col - (firstPos.col + dc)) +
1967 std::abs(secondPos.row - (firstPos.row + dr));
1968 minDist = std::min(minDist, dist);
1969 }
1970 if (minDist == 0)
1971 continue;
1972 penalty += weight * minDist;
1973 if (charged)
1974 charged->append({firstPos, secondPos});
1975 }
1976 return penalty;
1977}
1978
1979int SAPlacer::computePairingPenalty(SmallVectorImpl<TileID> *charged) const {
1980 int penalty =
1981 computeAdjacencyPenalty(cascadeAdjacency, targetModel->getCascadeSteps(),
1982 config.cascadeWeightPerDist, charged);
1983 for (auto [first, second] : sharedMemAdjacency.edges) {
1984 auto firstIt = currentPlacement.find(first.getOperation());
1985 auto secondIt = currentPlacement.find(second.getOperation());
1986 if (firstIt == currentPlacement.end() || secondIt == currentPlacement.end())
1987 continue;
1988 TileID a = firstIt->second, b = secondIt->second;
1989 if (a == b || targetModel->isLegalMemAffinity(a.col, a.row, b.col, b.row) ||
1990 targetModel->isLegalMemAffinity(b.col, b.row, a.col, a.row))
1991 continue;
1992 int distance = std::abs(a.col - b.col) + std::abs(a.row - b.row);
1993 penalty += config.sharedMemWeightPerDist * std::max(1, distance - 1);
1994 if (charged)
1995 charged->append({a, b});
1996 }
1997 return penalty;
1998}
1999
2000void SAPlacer::generateAllocates() {
2001 DenseSet<size_t> emittedFifoIndices;
2002
2003 // Case A: the moves that planCoreFit plans.
2004 DenseMap<TileID, BufferCounts> lent;
2005 for (TileID tilePos : overflowingCoreTiles()) {
2006 SmallVector<std::pair<size_t, TileID>> moves;
2007 (void)planCoreFit(tilePos, lent, &moves);
2008 for (auto [fifoIdx, nbrPos] : moves) {
2009 if (!emittedFifoIndices.insert(fifoIdx).second)
2010 continue;
2011 const auto &fb = fifoBuffers[fifoIdx];
2012 currentMemUsage[nbrPos] +=
2013 std::max(fb.producerSizeBytes, fb.consumerSizeBytes) * fb.sharedDepth;
2014 allocates.push_back({fb.fifoOp, nbrPos});
2015 }
2016 }
2017
2018 // Case B: Shared-mem destination communication.
2019 // sharedMemDestination is populated by addFifoContribution during
2020 // initResourceTracking, which runs on the final placement before this.
2021 for (auto &[fifoIdx, destTile] : sharedMemDestination) {
2022 if (emittedFifoIndices.contains(fifoIdx))
2023 continue;
2024 const auto &fb = fifoBuffers[fifoIdx];
2025 std::optional<TileID> prodPos = positionOf(fb.producerTile);
2026 std::optional<TileID> consPos = positionOf(fb.consumerTiles[0]);
2027 if (!prodPos || !consPos || *prodPos == *consPos)
2028 continue;
2029 if (destTile != *prodPos)
2030 allocates.push_back({fb.fifoOp, destTile});
2031 }
2032}
2033
2034int SAPlacer::updateResourcePenalty(
2035 const SmallVector<std::pair<Operation *, TileID>> &oldPlacements) {
2036 // Collect all fifo indices affected by the moved tiles
2037 DenseSet<size_t> affectedFifos;
2038 for (auto &[op, _] : oldPlacements) {
2039 auto it = tileToFifoIndices.find(op);
2040 if (it != tileToFifoIndices.end())
2041 for (size_t idx : it->second)
2042 affectedFifos.insert(idx);
2043 }
2044 // A move that changes where a variable link's pool is shared changes its
2045 // depth: its participants come off with the old plans, on with the new.
2046 replannedLinks.clear();
2047 auto at = [this](Value tile) { return positionOf(tile.getDefiningOp()); };
2048 for (unsigned index = 0, e = variableLinks.size(); index < e; ++index) {
2049 const VariableLink &variable = variableLinks[index];
2050 if (llvm::none_of(oldPlacements, [&](const auto &moved) {
2051 return llvm::is_contained(variable.tiles, moved.first);
2052 }))
2053 continue;
2054 int64_t depth = variable.plan.depthAt(*targetModel, at);
2055 if (depth == variable.depth)
2056 continue;
2057 replannedLinks.push_back({index, variable.depth, depth});
2058 affectedFifos.insert(variable.fifos.begin(), variable.fifos.end());
2059 }
2060
2061 // Update static buffer and stack contributions for moved tiles
2062 for (auto &[op, oldPos] : oldPlacements) {
2063 auto bufIt = staticBufferSizes.find(op);
2064 if (bufIt != staticBufferSizes.end())
2065 currentMemUsage[oldPos] -= bufIt->second;
2066 auto stackIt = stackSizes.find(op);
2067 if (stackIt != stackSizes.end())
2068 currentMemUsage[oldPos] -= stackIt->second;
2069 }
2070
2071 // Subtract old fifo contributions (positions already updated in
2072 // currentPlacement, but we need old positions for subtraction).
2073 // Temporarily swap back old positions for affected fifos.
2074 SmallVector<std::pair<Operation *, TileID>, 3> savedPositions;
2075 for (auto &[op, oldPos] : oldPlacements) {
2076 TileID &pos = currentPlacement[op];
2077 savedPositions.push_back({op, pos});
2078 pos = oldPos;
2079 }
2080 for (size_t fi : affectedFifos)
2081 addFifoContribution(fi, -1);
2082 SetVector<unsigned> movedNets;
2083 for (auto &[op, _] : oldPlacements)
2084 if (auto nets = streamNetsOf.find(op); nets != streamNetsOf.end())
2085 movedNets.insert_range(nets->second);
2086 for (unsigned net : movedNets) {
2087 auto stream = netStreams.find(net);
2088 cuts.add(stream->second.first, stream->second.second,
2089 streamNets[net].packet, -1);
2090 }
2091 for (auto &[op, _] : oldPlacements) {
2092 for (size_t ei : tileToRouteEnds.lookup(op))
2093 addRouteEndContribution(ei, -1);
2094 for (const DMAChannelAnalysis::ChannelClaim &claim : claimsOf.lookup(op)) {
2095 pinUse.claim(currentPlacement[op], claim, -1);
2096 claimLog.push_back({currentPlacement[op], claim, -1});
2097 }
2098 }
2099
2100 // Restore new positions and add new contributions
2101 for (auto &[op, newPos] : savedPositions)
2102 currentPlacement[op] = newPos;
2103 replanLinks(llvm::map_to_vector(replannedLinks, [](ReplannedLink replanned) {
2104 return std::make_pair(replanned.index, replanned.to);
2105 }));
2106 for (size_t fi : affectedFifos)
2107 addFifoContribution(fi, +1);
2108 auto placed = [this](Operation *op) { return positionOf(op); };
2109 for (unsigned net : movedNets) {
2110 auto &[src, dsts] = netStreams[net];
2111 if (streamOf(streamNets[net], placed, src, dsts))
2112 cuts.add(src, dsts, streamNets[net].packet, 1);
2113 }
2114 streamCutPenalty = config.streamCutPenaltyPerChannel * cuts.over();
2115 for (auto &[op, oldPos] : oldPlacements) {
2116 chargeStreams(op, oldPos, -1);
2117 chargeStreams(op, currentPlacement[op], 1);
2118 }
2119 if (!neighbourCores.empty()) {
2120 SmallVector<TileID, 4> changed;
2121 for (auto &[op, oldPos] : oldPlacements)
2122 if (coreKeys.contains(op))
2123 changed.append({oldPos, currentPlacement[op]});
2124 llvm::sort(changed);
2125 changed.erase(llvm::unique(changed), changed.end());
2126 for (TileID at : changed)
2127 coresChanged -= coresChangedAt(at);
2128 for (auto &[op, oldPos] : oldPlacements)
2129 if (coreKeys.contains(op))
2130 keyAt[oldPos] = 0;
2131 for (auto &[op, oldPos] : oldPlacements)
2132 if (unsigned key = coreKeys.lookup(op))
2133 keyAt[currentPlacement[op]] = key;
2134 for (TileID at : changed)
2135 coresChanged += coresChangedAt(at);
2136 }
2137 SmallVector<unsigned> ddrMoved;
2138 for (auto &[op, _] : oldPlacements)
2139 if (auto it = ddrGroupsOf.find(op); it != ddrGroupsOf.end())
2140 llvm::append_range(ddrMoved, it->second);
2141 if (!ddrMoved.empty()) {
2142 llvm::sort(ddrMoved);
2143 ddrMoved.erase(llvm::unique(ddrMoved), ddrMoved.end());
2144 auto columnOf = [this](Operation *op) -> std::optional<int> {
2145 std::optional<TileID> at = positionOf(op);
2146 return at ? std::optional(at->col) : std::nullopt;
2147 };
2148 for (unsigned index : ddrMoved) {
2149 int64_t score =
2150 ddrGroupSpread(ddrGroups[index], columnOf, config.ddrWeight);
2151 int64_t &at = ddrScoreOf[index];
2152 ddrTotal += score - at;
2153 at = score;
2154 }
2155 ddrPenalty = static_cast<int>(ddrTotal);
2156 }
2157 for (auto &[op, _] : oldPlacements) {
2158 for (size_t ei : tileToRouteEnds.lookup(op))
2159 addRouteEndContribution(ei, +1);
2160 for (const DMAChannelAnalysis::ChannelClaim &claim : claimsOf.lookup(op)) {
2161 pinUse.claim(currentPlacement[op], claim, 1);
2162 claimLog.push_back({currentPlacement[op], claim, 1});
2163 }
2164 }
2165
2166 for (auto &[op, oldPos] : oldPlacements)
2167 if (int locks = homeLocks.lookup(op)) {
2168 addLockDemand(oldPos, -locks);
2169 addLockDemand(currentPlacement[op], locks);
2170 }
2171
2172 // Add new static buffer and stack contributions
2173 for (auto &[op, _] : oldPlacements) {
2174 TileID newPos = currentPlacement[op];
2175 auto bufIt = staticBufferSizes.find(op);
2176 if (bufIt != staticBufferSizes.end())
2177 currentMemUsage[newPos] += bufIt->second;
2178 auto stackIt = stackSizes.find(op);
2179 if (stackIt != stackSizes.end())
2180 currentMemUsage[newPos] += stackIt->second;
2181 }
2182 for (auto &[op, oldPos] : oldPlacements)
2183 if (coreContents.count(op)) {
2184 coreDirty.insert(oldPos);
2185 coreDirty.insert(currentPlacement[op]);
2186 }
2187 // The overflow set and the tiles its penalty reads change only through
2188 // a core tile whose layout changed.
2189 if (SmallVector<TileID> coreChanged = refreshCoreUnplaced();
2190 !coreChanged.empty()) {
2191 SmallVector<TileID> overflowing = overflowingCoreTiles();
2192 DenseSet<TileID> overflowReads = coreOverflowReads();
2193 if (overflowing != coreOverflowTiles ||
2194 llvm::any_of(coreChanged,
2195 [&](TileID pos) { return overflowReads.contains(pos); })) {
2196 coreOverflowTiles = std::move(overflowing);
2197 coreOverflowPenalty = computeCoreOverflowPenalty();
2198 }
2199 }
2200
2201 auto reads = [&](const DenseSet<Operation *> &tiles) {
2202 return llvm::any_of(oldPlacements, [&](const auto &moved) {
2203 return tiles.contains(moved.first);
2204 });
2205 };
2206 if (reads(spillTiles) || !replannedLinks.empty())
2207 memSpilloverPenalty = computeMemSpilloverPenalty();
2208 SmallVector<TileID> bdTouched;
2209 for (ReplannedLink replanned : replannedLinks)
2210 if (std::optional<TileID> pos =
2211 positionOf(variableLinks[replanned.index].tiles.front());
2212 pos &&
2213 targetModel->getTileType(pos->col, pos->row) == AIETileType::MemTile)
2214 bdTouched.push_back(*pos);
2215 for (auto &[op, oldPos] : oldPlacements)
2216 if (memTileEnds.count(op) || llvm::is_contained(logicalMemTiles, op))
2217 for (TileID pos : {oldPos, currentPlacement[op]})
2218 if (!llvm::is_contained(bdTouched, pos))
2219 bdTouched.push_back(pos);
2220 for (TileID pos : bdTouched) {
2221 int64_t &at = bdShortfallAt[pos];
2222 bdCountPenalty -= static_cast<int>(at * config.dmaPenaltyPerChannel);
2223 at = bdShortfall(pos, memTilesAt(pos));
2224 bdCountPenalty += static_cast<int>(at * config.dmaPenaltyPerChannel);
2225 }
2226 if (reads(delegateTermTiles))
2227 delegatePenalty = computeDelegatePenalty();
2228
2229 // DMA usage changed only where the affected fifos' ends and the moved
2230 // tiles sit, before or after the move, and so did which shim ends share.
2231 llvm::SmallDenseSet<TileID, 16> dmaTouched;
2232 for (auto &[op, oldPos] : oldPlacements) {
2233 dmaTouched.insert(oldPos);
2234 dmaTouched.insert(currentPlacement[op]);
2235 }
2236 for (size_t fi : affectedFifos) {
2237 const auto &fb = fifoBuffers[fi];
2238 SmallVector<Operation *, 4> ends = {fb.producer};
2239 llvm::append_range(ends, fb.consumers);
2240 for (Operation *end : ends)
2241 if (auto it = currentPlacement.find(end); it != currentPlacement.end())
2242 dmaTouched.insert(it->second);
2243 }
2244 for (auto &[op, oldPos] : oldPlacements)
2245 if (runtimeBdIds.uses(op))
2246 for (TileID pos : {oldPos, currentPlacement[op]})
2247 chargeRuntimeBds(pos);
2248 for (TileID tile : dmaTouched) {
2249 int &at = dmaPenaltyAt[tile];
2250 int now = computeTileDMAPenalty(tile);
2251 dmaPenalty += now - at;
2252 at = now;
2253 }
2254
2255 cachedResourcePenalty = memSpilloverPenalty + coreOverflowPenalty +
2256 computeLockPenalty() + dmaPenalty + bdCountPenalty +
2257 delegatePenalty + streamCutPenalty;
2258 return cachedResourcePenalty;
2259}
2260
2261//===----------------------------------------------------------------------===//
2262// Move generation
2263//===----------------------------------------------------------------------===//
2264
2265bool SAPlacer::generateMove(
2266 SmallVector<std::pair<Operation *, TileID>> &moves) {
2267 if (movableTiles.empty())
2268 return false;
2269
2270 for (int attempt = 0; attempt < config.maxMoveAttempts; attempt++) {
2271 // Pick a random movable tile.
2272 Operation *tile = movableTiles[drawBoundedIndex(rng, movableTiles.size())];
2273
2274 auto typeIt = tileTypes.find(tile);
2275 if (typeIt == tileTypes.end())
2276 continue;
2277 AIETileType type = typeIt->second;
2278
2279 // Pick a random target position of matching type.
2280 const auto &candidates = (type == AIETileType::CoreTile)
2281 ? availability.compTiles
2282 : availability.nonCompTiles;
2283 if (candidates.empty())
2284 continue;
2285
2286 TileID targetPos = candidates[drawBoundedIndex(rng, candidates.size())];
2287
2288 // Filter by tile type for non-compute (nonCompTiles has mixed types).
2289 if (type != AIETileType::CoreTile &&
2290 targetModel->getTileType(targetPos.col, targetPos.row) != type)
2291 continue;
2292
2293 TileID currentPos = currentPlacement[tile];
2294 if (targetPos == currentPos)
2295 continue;
2296
2297 if (!satisfiesConstraints(tile, targetPos))
2298 continue;
2299
2300 // Check if target is occupied by another movable tile.
2301 Operation *occupant = nullptr;
2302 for (auto *t : movableTiles) {
2303 if (t != tile && currentPlacement[t] == targetPos) {
2304 occupant = t;
2305 break;
2306 }
2307 }
2308
2309 // Shift onto an empty target, or onto an occupied one whose type several
2310 // tiles may share (a coin flip keeps swaps available too, since how many
2311 // sit on each could never change if sharing always won).
2312 if (!occupant ||
2313 (type != AIETileType::CoreTile && drawBoundedIndex(rng, 2) == 0)) {
2314 if (!isLegalPosition(tile, targetPos))
2315 continue;
2316 moves.clear();
2317 moves.push_back({tile, targetPos});
2318 } else {
2319 // Swap: both tiles must accept each other's position.
2320 if (tileTypes[occupant] != type)
2321 continue;
2322 if (!satisfiesConstraints(occupant, currentPos) ||
2323 namedClash(tile, namedAt(tile, targetPos, occupant)) ||
2324 namedClash(occupant, namedAt(occupant, currentPos, tile)))
2325 continue;
2326 moves.clear();
2327 moves.push_back({tile, targetPos});
2328 moves.push_back({occupant, currentPos});
2329 }
2330 return true;
2331 }
2332 return false;
2333}
2334
2335//===----------------------------------------------------------------------===//
2336// Initial temperature estimation
2337//===----------------------------------------------------------------------===//
2338
2339double SAPlacer::estimateInitialTemperature(int numSamples) {
2340 // Collect delta costs from random moves
2341 std::vector<double> deltaCosts;
2342 deltaCosts.reserve(numSamples);
2343
2344 SmallVector<std::pair<size_t, NetBoundingBox>> backups;
2345
2346 for (int i = 0; i < numSamples; i++) {
2347 SmallVector<std::pair<Operation *, TileID>> moves;
2348 if (!generateMove(moves))
2349 continue;
2350
2351 // Use the first tile's HPWL delta as cost sample.
2352 int delta = evaluateMove(moves[0].first, moves[0].second, backups);
2353 deltaCosts.push_back(delta);
2354 revertMove(backups);
2355 }
2356
2357 if (deltaCosts.empty())
2358 return 1.0;
2359
2360 // Equilibrium binary search: find T where E[delta_cost] ≈ 0,
2361 // improving and worsening moves roughly cancel out and
2362 // SA accepts most moves freely - good starting point
2363 double maxDelta = 0.0;
2364 for (double d : deltaCosts)
2365 maxDelta = std::max(maxDelta, std::abs(d));
2366
2367 if (maxDelta == 0.0)
2368 return 1.0;
2369
2370 auto getExpectedValue = [&](double T) -> double {
2371 double ev = 0.0;
2372 for (double d : deltaCosts) {
2373 if (d <= 0)
2374 ev += d;
2375 else
2376 ev += d * std::exp(-d / T);
2377 }
2378 return ev;
2379 };
2380
2381 double lowT = 0.0;
2382 double highT = config.tempSearchCeiling * maxDelta;
2383 double T = 1.0;
2384
2385 for (int iter = 0; iter < config.tempSearchIters; iter++) {
2386 double ev = getExpectedValue(T);
2387 if (std::abs(highT - lowT) / std::max(T, config.tempSearchEpsilon) <
2388 config.tempSearchTolerance)
2389 break;
2390 if (ev > 0) {
2391 // Expected value positive → worsening moves dominate → T too high
2392 // (accepting too many bad moves). Lower the ceiling.
2393 highT = T;
2394 } else {
2395 // Expected value negative → improving moves dominate → T too low.
2396 // Raise the floor.
2397 lowT = T;
2398 }
2399 T = (lowT + highT) / 2.0;
2400 }
2401
2402 return T;
2403}
2404
2405//===----------------------------------------------------------------------===//
2406// Memory weight estimation (for initial placement sorting)
2407//===----------------------------------------------------------------------===//
2408
2409int64_t SAPlacer::computeTileMemoryWeight(Operation *tile) const {
2410 int64_t weight = 0;
2411
2412 // Static buffers (aie.buffer ops)
2413 auto bufIt = staticBufferSizes.find(tile);
2414 if (bufIt != staticBufferSizes.end())
2415 weight += bufIt->second;
2416
2417 // Core stack overhead
2418 auto stackIt = stackSizes.find(tile);
2419 if (stackIt != stackSizes.end())
2420 weight += stackIt->second;
2421
2422 // Fifo endpoint contributions
2423 for (const auto &fb : fifoBuffers) {
2424 bool isProd = (fb.producer == tile);
2425 int consIdx = -1;
2426 for (size_t ci = 0; ci < fb.consumers.size(); ci++) {
2427 if (fb.consumers[ci] == tile) {
2428 consIdx = static_cast<int>(ci);
2429 break;
2430 }
2431 }
2432 if (!isProd && consIdx < 0)
2433 continue;
2434
2435 if (isProd && consIdx >= 0) {
2436 weight +=
2437 std::max(fb.producerSizeBytes, fb.consumerSizeBytes) * fb.sharedDepth;
2438 } else if (isProd) {
2439 weight += fb.producerSizeBytes * fb.producerDepth;
2440 } else {
2441 weight += fb.consumerSizeBytes * fb.consumerDepths[consIdx];
2442 }
2443 }
2444 return weight;
2445}
2446
2447//===----------------------------------------------------------------------===//
2448// SA placement
2449//===----------------------------------------------------------------------===//
2450
2451LogicalResult SAPlacer::place(DeviceOp device) {
2452 startTime = std::chrono::steady_clock::now();
2453
2454 // Seed RNG
2455 if (rngSeed == 0) {
2456 rng.seed(std::random_device{}());
2457 } else {
2458 rng.seed(rngSeed);
2459 }
2460
2461 // Phase 1-2: Collect IR ops, build net model, fifo info, cascade groups.
2462 if (failed(collectAndBuildModel(device)))
2463 return failure();
2464 // Phase 3: Classify tiles by type, generate initial placement.
2465 if (failed(generateInitialPlacement()))
2466 return failure();
2467 // Phase 4: Initialize bounding boxes, resource tracking, initial cost.
2468 initializeSAState();
2469 // Phase 5: SA main loop (skip if nothing to optimize).
2470 runSAMainLoop();
2471 // Phase 6: Restore best, generate allocates, stats.
2472 return finalizePlacement(device);
2473}
2474
2475LogicalResult SAPlacer::collectAndBuildModel(DeviceOp device) {
2476 collected = collectOperations(device);
2477 auto &logicalTiles = collected.logicalTiles;
2478 auto &objectFifos = collected.objectFifos;
2479 auto &objectFifoLinks = collected.objectFifoLinks;
2480 pinnedRule = PinnedChannels(*targetModel, packetSwitched);
2481
2482 if (logicalTiles.empty())
2483 return success();
2484
2485 // Cache tile types
2486 for (auto lt : logicalTiles)
2487 tileTypes[lt.getOperation()] = lt.getTileType();
2488
2489 // Collect static buffer sizes per tile
2490 device.walk([&](BufferOp bufOp) {
2491 auto tile = dyn_cast_or_null<TileLike>(bufOp.getTile().getDefiningOp());
2492 if (!tile)
2493 return;
2494 int64_t bytes = bufOp.getAllocationSize();
2495 if (tile.getTileType() == AIETileType::MemTile)
2496 memTileFixed[tile].push_back(
2497 {bytes,
2498 bufOp.getAligned() ? targetModel->getMemTileLoadStoreBusWidth() / 8
2499 : 1,
2500 bufOp.getAddress()});
2501 TileMemoryLimits limits =
2503 staticBufferSizes[tile] +=
2504 llvm::alignTo(bytes, bufferAlignBytes(bufOp, limits.tileAlignBitWidth,
2505 limits.maxVecAlignBits));
2506 if (tile.getTileType() == AIETileType::CoreTile)
2507 coreContents[tile].buffers.push_back(tileLayoutBuffer(bufOp, limits));
2508 });
2509 TileMemoryLimits coreLimits =
2510 tileMemoryLimits(*targetModel, AIETileType::CoreTile);
2511 // An unsplit pool becomes the buffers aie-objectfifo-allocate gives it.
2512 for (auto pool : device.getOps<ObjectFifoPoolOp>()) {
2513 auto tile = dyn_cast_or_null<TileLike>(pool.getTile().getDefiningOp());
2514 if (!tile || tile.getTileType() != AIETileType::CoreTile ||
2515 pool.getBuffers())
2516 continue;
2517 TileLayoutBuffer buffer;
2518 buffer.size = pool.getObjectSizeInBytes() * pool.getObjectsPerBuffer();
2519 buffer.alignBytes =
2521 coreLimits.maxVecAlignBits, buffer.size) /
2522 8;
2523 for (int i = 0, e = pool.getContiguous() ? 1 : pool.getDepth(); i < e; ++i)
2524 coreContents[tile].buffers.push_back(buffer);
2525 }
2526
2527 for (LogicalTileOp tile : logicalTiles)
2528 for (Operation *user : tile->getUsers())
2529 if (isa<LockOp>(user))
2530 ++fixedLocks[tile];
2531 device.walk([&](LockOp lock) {
2532 if (auto placed = dyn_cast_or_null<TileOp>(lock.getTile().getDefiningOp()))
2533 ++placedLocks[placed.getTileID()];
2534 });
2535 for (auto tile : device.getOps<TileOp>())
2536 placedTiles.push_back(tile.getTileID());
2537 llvm::StringMap<Operation *> fifoNamed;
2538 for (ObjectFifoCreateOp fifo : collected.objectFifos)
2539 fifoNamed[fifo.getSymName()] = fifo;
2540 firstAcquire.clear();
2541 device.walk([&](ObjectFifoAcquireOp acquire) {
2542 if (Operation *fifo = fifoNamed.lookup(acquire.getObjFifoName()))
2543 firstAcquire.try_emplace(fifo, firstAcquire.size());
2544 });
2545 lockReach.clear();
2546 for (int col = 0; col < targetModel->columns(); ++col)
2547 for (int row = 0; row < targetModel->rows(); ++row) {
2548 TileID user{col, row};
2549 SmallVector<TileID> &reach = lockReach[user];
2550 for (int c = 0; c < targetModel->columns(); ++c)
2551 for (int r = 0; r < targetModel->rows(); ++r)
2552 if (TileID at{c, r};
2553 at == user ||
2554 LockPlan::reaches(*targetModel, user, at, /*localOnly=*/false))
2555 reach.push_back(at);
2556 }
2557 {
2558 PoolLocks poolLocks(device);
2559 for (auto pool : device.getOps<ObjectFifoPoolOp>()) {
2560 if (!poolLocks.needsLocks(pool))
2561 continue;
2562 SmallVector<Operation *> owners =
2564 SmallVector<int> counts =
2565 LockPlan::groupCounts(*targetModel, pool.getDepth(), owners.size());
2566 for (auto [index, entry] : llvm::enumerate(owners)) {
2567 Operation *owner = entry;
2568 InputLockGroup &group = inputLockGroups.emplace_back();
2569 group.home = pool.getTile().getDefiningOp();
2570 group.locks = counts[index];
2571 // A segment's locks serve the endpoints selecting it; a pool's, all.
2572 auto addUser = [&](Operation *endpoint, auto selected, bool dma) {
2573 if (owner != pool && !llvm::is_contained(selected, owner))
2574 return;
2575 auto *tile = endpoint->getOperand(0).getDefiningOp();
2576 group.users.push_back(
2577 {tile, dma && LockPlan::dmaLocalOnly(
2578 cast<TileLike>(tile).getTileType())});
2579 };
2580 for (auto endpoint : device.getOps<ObjectFifoCoreEndpointOp>())
2581 if (endpoint.getPoolOp() == pool)
2582 addUser(endpoint, endpoint.getSelectedSegments(), false);
2583 for (auto endpoint : device.getOps<ObjectFifoDmaEndpointOp>())
2584 if (endpoint.getPoolOp() == pool)
2585 addUser(endpoint, endpoint.getSelectedSegments(), true);
2586 }
2587 }
2588 }
2589
2590 // Collect core stack and data regions (reserved by assign-buffer-addresses)
2591 for (auto [ordinal, coreOp] : llvm::enumerate(device.getOps<CoreOp>())) {
2592 auto *tileOp = coreOp.getTile().getDefiningOp();
2593 if (!isa_and_nonnull<TileLike>(tileOp))
2594 continue;
2595 // What addressing reserves for the core's own sections is as much its
2596 // memory as the stack.
2597 int64_t bytes = alignedBufferBytes(*targetModel, AIETileType::CoreTile,
2598 coreOp.getEffectiveStackSize());
2599 CoreTileContents &contents = coreContents[tileOp];
2600 contents.hasCore = true;
2601 contents.stackRun = coreOp.getStackRun();
2602 std::optional<uint32_t> stackBank = coreOp.getStackBank();
2603 if (!coreOp.getStackAddress() && stackBank) {
2604 contents.stackBank = static_cast<int>(*stackBank);
2605 contents.stackAlignBytes = targetModel->getCoreStackAlignment();
2606 }
2607 SmallVector<CoreSectionReservation> reservations =
2608 coreOp.getSectionReservations();
2609 if (!coreOp.getDataSize() && !coreOp.getMeasuredDataSize())
2610 if (auto charge = config.coreDataCharges.find(ordinal);
2611 charge != config.coreDataCharges.end() && charge->second.bytes)
2612 reservations.push_back({CoreSectionReservation::Kind::DataRegion,
2613 charge->second.bytes, 0,
2614 charge->second.alignBytes});
2615 for (auto [held, holder] : llvm::zip_equal(
2616 reservations, coreOp.getSectionReservationBuffers(reservations)))
2617 if (!holder) {
2618 TileLayoutBuffer buffer = tileLayoutBuffer(held, coreLimits);
2619 bytes += llvm::alignTo(buffer.size, buffer.alignBytes);
2620 contents.buffers.push_back(buffer);
2621 }
2622 stackSizes[tileOp] = bytes;
2623 }
2624
2625 // Build net model, fifo buffer info, and cascade groups
2626 buildNetModel(objectFifos, objectFifoLinks);
2627 buildFifoBufferInfo(device, objectFifos, objectFifoLinks);
2628 buildStreamNets(device, collected);
2629 buildStreamDemand(objectFifos);
2630 if (pinnedRule.failed())
2631 return failure();
2632 llvm::ArrayRef<DMAChannelAnalysis::ChannelClaim> claims =
2633 channelAnalysis.emplace(device).getChannelClaims();
2634 buildRouteModel(device, collected.flows, collected.pktFlows, collected.routes,
2635 claims);
2636 buildShimModel(device, objectFifos, claims, collected.rank);
2637 overlayTiles = overlayTileOps();
2638 takenBDs = DMAChannelAnalysis::TakenBDs(device);
2639 logicalMemTiles.clear();
2640 for (auto tile : device.getOps<LogicalTileOp>())
2641 if (tile.getTileType() == AIETileType::MemTile)
2642 logicalMemTiles.push_back(tile);
2643 physicalTiles.clear();
2644 for (TileOp tile : device.getOps<TileOp>())
2645 physicalTiles[{tile.getCol(), tile.getRow()}].push_back(tile);
2646 cascadeAdjacency = buildCascadeAdjacency(collected.cascadeFlows);
2647 LLVM_DEBUG(llvm::dbgs() << "[SA] Cascade adjacency: "
2648 << cascadeAdjacency.edges.size() << " edges\n");
2649 for (ObjectFifoCreateOp fifo : objectFifos)
2650 if (fifo.forcesSharedMemory() && fifo.getConsumerTiles().size() == 1)
2651 sharedMemAdjacency.addEdgeFromValues(fifo.getProducerTile(),
2652 fifo.getConsumerTiles()[0]);
2653
2654 // A pool is known by its objectFIFO as the split names it: a link's by the
2655 // fifo that owns its pool.
2656 chargedPools.clear();
2657 for (auto &[tile, ends] : memTileEnds)
2658 for (const MemTileEnd &end : ends) {
2659 std::optional<StringRef> fifo;
2660 if (auto create = dyn_cast_or_null<ObjectFifoCreateOp>(end.end.pool))
2661 fifo = create.name().getValue();
2662 else if (auto link = dyn_cast_or_null<ObjectFifoLinkOp>(end.end.pool))
2663 fifo = link.getPoolOwner().name().getValue();
2664 else if (auto pool = dyn_cast_or_null<ObjectFifoPoolOp>(end.end.pool))
2665 fifo = pool.getFifoName();
2666 if (fifo && llvm::is_contained(config.walkedFifos, *fifo))
2667 chargedPools.insert(end.end.pool);
2668 }
2669
2670 return success();
2671}
2672
2673void SAPlacer::buildFifoBufferInfo(DeviceOp device,
2674 ArrayRef<ObjectFifoCreateOp> objectFifos,
2675 ArrayRef<ObjectFifoLinkOp> objectFifoLinks) {
2676 mlir::DataLayout dataLayout(device->getParentOfType<ModuleOp>());
2677
2678 memTileEnds.clear();
2679 PoolLocks poolLocks(device);
2680 llvm::StringMap<Operation *> delegates;
2681 for (auto alloc : device.getOps<ObjectFifoAllocateOp>())
2682 delegates[alloc.getObjFifoName()] = alloc.getDelegateTile().getDefiningOp();
2683
2684 for (auto ofOp : objectFifos) {
2685 FifoBufferInfo fb;
2686 fb.fifoOp = ofOp.getOperation();
2687 fb.delegate = delegates.lookup(ofOp.getSymName());
2688
2689 // Get producer
2690 auto *prodOp = ofOp.getProducerTile().getDefiningOp();
2691 fb.producer = (isa_and_nonnull<LogicalTileOp>(prodOp)) ? prodOp : nullptr;
2692 fb.producerTile = prodOp;
2693
2694 // Null for a placed consumer, so indices stay the fifo's own.
2695 for (Value ct : ofOp.getConsumerTiles()) {
2696 auto *consOp = ct.getDefiningOp();
2697 fb.consumers.push_back(isa_and_nonnull<LogicalTileOp>(consOp) ? consOp
2698 : nullptr);
2699 fb.consumerTiles.push_back(consOp);
2700 }
2701
2702 // Compute buffer element size (producer side)
2703 auto fifoType = llvm::cast<AIEObjectFifoType>(ofOp.getElemType());
2704 auto elemType = llvm::cast<MemRefType>(fifoType.getElementType());
2705 int64_t producerBytes = getMemRefSizeInBytes(elemType, dataLayout);
2706 auto prodLike = dyn_cast_or_null<TileLike>(prodOp);
2707 AIETileType prodType =
2708 prodLike ? prodLike.getTileType() : AIETileType::CoreTile;
2709 fb.producerSizeBytes =
2710 alignedBufferBytes(*targetModel, prodType, producerBytes);
2711 fb.producerRawBytes = producerBytes;
2712
2713 // Consumer element size (may differ with consumerElemType)
2714 int64_t consumerBytes = producerBytes;
2715 if (auto consType = ofOp.getConsumerElemType()) {
2716 auto consOFType = llvm::cast<AIEObjectFifoType>(consType.value());
2717 auto consMemref = llvm::cast<MemRefType>(consOFType.getElementType());
2718 consumerBytes = getMemRefSizeInBytes(consMemref, dataLayout);
2719 }
2720 // One size serves every consumer, so align it for a core tile if any
2721 // consumer is one.
2722 bool coreConsumer = llvm::any_of(fb.consumerTiles, [&](Operation *cons) {
2723 auto tile = dyn_cast_or_null<TileLike>(cons);
2724 return tile && tile.getTileType() == AIETileType::CoreTile;
2725 });
2726 fb.consumerSizeBytes = alignedBufferBytes(
2727 *targetModel,
2728 coreConsumer ? AIETileType::CoreTile : AIETileType::MemTile,
2729 consumerBytes);
2730 fb.consumerRawBytes = consumerBytes;
2731
2732 fb.sharedDepth = ofOp.sharedDepth();
2733 fb.producerDepth = ofOp.dmaDepth(std::nullopt);
2734 for (unsigned ci = 0, e = fb.consumers.size(); ci < e; ++ci)
2735 fb.consumerDepths.push_back(ofOp.dmaDepth(ci));
2736
2737 auto at = [this](Value tile) { return positionOf(tile.getDefiningOp()); };
2738 fb.producerEnd = ofOp.plannedDmaEnd(std::nullopt, at);
2739 for (unsigned ci = 0, e = fb.consumers.size(); ci < e; ++ci)
2740 fb.consumerEnds.push_back(ofOp.plannedDmaEnd(ci, at));
2741 auto onMemTile = [&](Operation *tile) {
2742 auto like = dyn_cast_or_null<TileLike>(tile);
2743 return like && like.getTileType() == AIETileType::MemTile;
2744 };
2745 auto drawsChannel = [&](Operation *tile, bool planned) {
2746 auto like = dyn_cast_or_null<TileLike>(tile);
2747 if (!like)
2748 return false;
2749 return isShimEndType(like.getTileType()) ? !ofOp.getPlio() : planned;
2750 };
2751 if (drawsChannel(fb.producerTile, fb.producerEnd.has_value()))
2752 fb.producerPin = PinnedChannels::endOf(ofOp, std::nullopt);
2753 if (fb.producerPin)
2754 pinnedRule.share(*fb.producerPin, collected.rank);
2755 for (unsigned ci = 0, e = fb.consumers.size(); ci < e; ++ci) {
2756 std::optional<PinnedChannels::End> pin;
2757 if (drawsChannel(fb.consumerTiles[ci], fb.consumerEnds[ci].has_value()))
2758 pin = PinnedChannels::endOf(ofOp, ci);
2759 if (pin)
2760 pinnedRule.share(*pin, collected.rank);
2761 fb.consumerPins.push_back(pin);
2762 }
2763 if (fb.producerEnd && onMemTile(fb.producerTile)) {
2764 SmallVector<MemTileEnd> &ends = memTileEnds[fb.producerTile];
2765 fb.producerMemTileEntry = ends.size();
2766 ends.push_back({DMAChannelDir::MM2S, *fb.producerEnd});
2767 }
2768 for (unsigned ci = 0, e = fb.consumers.size(); ci < e; ++ci) {
2769 std::optional<unsigned> &entry = fb.consumerMemTileEntries.emplace_back();
2770 if (const std::optional<PlannedDmaEnd> &end = fb.consumerEnds[ci];
2771 end && onMemTile(fb.consumerTiles[ci])) {
2772 SmallVector<MemTileEnd> &ends = memTileEnds[fb.consumerTiles[ci]];
2773 entry = ends.size();
2774 ends.push_back({DMAChannelDir::S2MM, *end});
2775 }
2776 }
2777
2778 std::optional<ObjectFifoLinkOp> link = ofOp.getLink();
2779 fb.forcesDMA = ofOp.dmaReason().has_value();
2780 if (link)
2781 fb.linkTile = link->getOptionalSharedTile()->getDefiningOp();
2782 if (fb.delegate) {
2783 fb.allocateFallsBackToDMA = ofOp.allocateFallsBackToDMA();
2784 fb.fitsLinkPool = ofOp.linkPoolMisfit() == LinkPoolMisfit::None;
2785 }
2786 // A link output's producer objects are the link input's consumer pool.
2787 fb.linkSharedProd =
2788 link && llvm::is_contained(link->getOutputObjectFifos(), ofOp);
2789 fb.unsynchronized = ofOp.getDisableSynchronization();
2790 if (auto init = ofOp.getInitValues())
2791 fb.initObjects = init->size();
2792 fb.rearmed = poolLocks.rearms().contains(ofOp.getSymName());
2793 fb.producerCore = hasCoreAccess(device, ofOp.getProducerTile(), ofOp,
2794 ObjectFifoPort::Produce);
2795 for (Value tile : ofOp.getConsumerTiles())
2796 fb.consumerCore.push_back(
2797 hasCoreAccess(device, tile, ofOp, ObjectFifoPort::Consume));
2798 fifoBuffers.push_back(fb);
2799 }
2800
2801 // Every end of a link on its tile shares the link's one pool, as the split
2802 // builds it once; the first end holds it. A merge's or dispatch's later
2803 // participants plan no DMA end of their own, so the pool's plan is the
2804 // first end's that names it.
2805 DenseMap<Operation *, PlannedDmaEnd> linkPlans;
2806 for (FifoBufferInfo &fb : fifoBuffers)
2807 for (const std::optional<PlannedDmaEnd> &end :
2808 llvm::concat<const std::optional<PlannedDmaEnd>>(
2809 fb.consumerEnds, ArrayRef(fb.producerEnd)))
2810 if (end && isa_and_nonnull<ObjectFifoLinkOp>(end->pool))
2811 linkPlans.try_emplace(end->pool, *end);
2812 DenseSet<Operation *> heldLinkPools;
2813 for (FifoBufferInfo &fb : fifoBuffers) {
2814 auto fifo = cast<ObjectFifoCreateOp>(fb.fifoOp);
2815 auto linkPoolOf = [&](std::optional<unsigned> consumer)
2816 -> std::pair<FifoBufferInfo::LinkPool, std::optional<PlannedDmaEnd>> {
2817 using LinkPool = FifoBufferInfo::LinkPool;
2818 ObjectFifoLinkOp link =
2819 consumer ? fifo.getConsumerLink(*consumer) : fifo.getProducerLink();
2820 auto plan = link ? linkPlans.find(link) : linkPlans.end();
2821 if (plan == linkPlans.end())
2822 return {LinkPool::None, std::nullopt};
2823 if (!heldLinkPools.insert(link).second)
2824 return {LinkPool::Shares, std::nullopt};
2825 return {LinkPool::Holds, plan->second};
2826 };
2827 for (unsigned ci = 0, e = fb.consumerEnds.size(); ci < e; ++ci) {
2828 auto [pool, plan] = linkPoolOf(ci);
2829 fb.consumerLinkPools.push_back(pool);
2830 fb.consumerLinkPlans.push_back(plan);
2831 }
2832 std::tie(fb.producerLinkPool, fb.producerLinkPlan) =
2833 linkPoolOf(std::nullopt);
2834 // A link's pool takes locks unless a participant disables
2835 // synchronization.
2836 auto linkSegments = [](const std::optional<PlannedDmaEnd> &plan) {
2837 if (!plan)
2838 return 0;
2839 auto link = cast<ObjectFifoLinkOp>(plan->pool);
2840 auto unsynchronized = [](ObjectFifoCreateOp participant) {
2841 return participant.getDisableSynchronization();
2842 };
2843 if (llvm::any_of(link.getInputObjectFifos(), unsynchronized) ||
2844 llvm::any_of(link.getOutputObjectFifos(), unsynchronized))
2845 return 0;
2846 return static_cast<int>(link.getPoolSegments().size());
2847 };
2848 for (const std::optional<PlannedDmaEnd> &plan : fb.consumerLinkPlans)
2849 fb.consumerLinkSegments.push_back(linkSegments(plan));
2850 fb.producerLinkSegments = linkSegments(fb.producerLinkPlan);
2851 }
2852
2853 variableLinks.clear();
2854 DenseMap<Operation *, size_t> fifoIndex;
2855 for (auto [index, fb] : llvm::enumerate(fifoBuffers))
2856 fifoIndex[fb.fifoOp] = index;
2857 auto at = [this](Value tile) { return positionOf(tile.getDefiningOp()); };
2858 for (ObjectFifoLinkOp link : objectFifoLinks) {
2859 LinkPoolPlan plan = link.getPoolPlan();
2860 if (plan.sharers.empty())
2861 continue;
2862 Operation *point = plan.linkTile.getDefiningOp();
2863 VariableLink variable{link, std::move(plan), 0, {point}, {}, {}, {}};
2864 for (const LinkPoolSharer &sharer : variable.plan.sharers)
2865 variable.tiles.append({sharer.producer.getDefiningOp(),
2866 sharer.consumer.getDefiningOp(),
2867 sharer.delegate.getDefiningOp()});
2868 std::vector<ObjectFifoCreateOp> ins = link.getInputObjectFifos();
2869 std::vector<ObjectFifoCreateOp> outs = link.getOutputObjectFifos();
2870 for (ObjectFifoCreateOp fifo : llvm::concat<ObjectFifoCreateOp>(ins, outs))
2871 if (auto index = fifoIndex.find(fifo.getOperation());
2872 index != fifoIndex.end())
2873 variable.fifos.push_back(index->second);
2874 llvm::sort(variable.fifos);
2875 variable.fifos.erase(llvm::unique(variable.fifos), variable.fifos.end());
2876 using LinkPool = FifoBufferInfo::LinkPool;
2877 for (size_t index : variable.fifos) {
2878 FifoBufferInfo &fb = fifoBuffers[index];
2879 auto fifo = cast<ObjectFifoCreateOp>(fb.fifoOp);
2880 for (unsigned ci = 0, e = fb.consumerLinkPools.size(); ci < e; ++ci)
2881 if (fb.consumerLinkPools[ci] == LinkPool::Holds &&
2882 fifo.getConsumerLink(ci) == link)
2883 variable.holds.push_back({index, ci});
2884 if (fb.producerLinkPool == LinkPool::Holds &&
2885 fifo.getProducerLink() == link)
2886 variable.holds.push_back({index, std::nullopt});
2887 }
2888 variable.depth = variable.plan.depthAt(*targetModel, at);
2889 variableLinks.push_back(std::move(variable));
2890 }
2891
2892 LLVM_DEBUG(llvm::dbgs() << "[SA] seed=" << rngSeed << "\n");
2893 LLVM_DEBUG(llvm::dbgs() << "[SA] Collected " << fifoBuffers.size()
2894 << " ObjectFifo buffer requirements\n");
2895}
2896
2897LogicalResult SAPlacer::generateInitialPlacement() {
2898 auto &logicalTiles = collected.logicalTiles;
2899
2900 // Classify available tiles by type
2901 std::vector<TileID> availComp = availability.compTiles;
2902 std::vector<TileID> availMem, availShim;
2903 for (auto &t : availability.nonCompTiles) {
2904 AIETileType type = targetModel->getTileType(t.col, t.row);
2905 if (type == AIETileType::MemTile)
2906 availMem.push_back(t);
2907 else if (type == AIETileType::ShimNOCTile)
2908 availShim.push_back(t);
2909 }
2910
2911 // Order compute positions in checkerboard pattern: phase-0 positions
2912 // ((col+row) even) first, then phase-1. No two phase-0 positions are
2913 // 4-connected neighbors, so the heaviest tiles placed first are guaranteed
2914 // non-adjacent. Within each phase, row-major order.
2915 llvm::sort(availComp, [](TileID a, TileID b) {
2916 int phaseA = (a.col + a.row) % 2;
2917 int phaseB = (b.col + b.row) % 2;
2918 if (phaseA != phaseB)
2919 return phaseA < phaseB;
2920 if (a.row != b.row)
2921 return a.row < b.row;
2922 return a.col < b.col;
2923 });
2924 // Order MemTile positions: even columns first (0,2,4,6,1,3,5,7).
2925 // Heavy MemTile tiles placed first get non-adjacent columns, avoiding
2926 // per-buffer spill collisions.
2927 llvm::sort(availMem, [](TileID a, TileID b) {
2928 int phaseA = a.col % 2;
2929 int phaseB = b.col % 2;
2930 if (phaseA != phaseB)
2931 return phaseA < phaseB;
2932 return a.col < b.col;
2933 });
2934 deterministicShuffle(availShim, rng);
2935
2936 size_t compIdx = 0, memIdx = 0, shimIdx = 0;
2937
2938 // A core position holds one tile. Mem and shim positions hold several, as
2939 // moves and allocation allow, so a pinned one only sends its position to
2940 // the back of the pool, after the free ones.
2941 SmallVector<TileID> pinnedMem, pinnedShim;
2942 for (auto lt : logicalTiles) {
2943 Operation *op = lt.getOperation();
2944 auto col = lt.tryGetCol();
2945 auto row = lt.tryGetRow();
2946 AIETileType type = lt.getTileType();
2947
2948 if (col && row) {
2949 // Fully constrained
2950 TileID pos{*col, *row};
2951 currentPlacement[op] = pos;
2952 physToLogical[pos] = op;
2953 constrainedTiles.insert(op);
2954
2955 if (type == AIETileType::CoreTile) {
2956 llvm::erase(availComp, pos);
2957 } else if (llvm::is_contained(availMem, pos)) {
2958 llvm::erase(availMem, pos);
2959 pinnedMem.push_back(pos);
2960 } else if (llvm::is_contained(availShim, pos)) {
2961 llvm::erase(availShim, pos);
2962 pinnedShim.push_back(pos);
2963 }
2964 }
2965 }
2966 llvm::append_range(availMem, pinnedMem);
2967 llvm::append_range(availShim, pinnedShim);
2968
2969 // Place unconstrained core tiles sorted by memory weight (heaviest first)
2970 // into checkerboard-spread positions. Cascade tiles are placed independently;
2971 // the cascade penalty guides them to adjacent positions during SA.
2972 auto byMemWeightDesc = [this](Operation *a, Operation *b) {
2973 int64_t wa = computeTileMemoryWeight(a);
2974 int64_t wb = computeTileMemoryWeight(b);
2975 if (wa != wb)
2976 return wa > wb;
2977 return collected.rank.lookup(a) < collected.rank.lookup(b);
2978 };
2979 {
2980 SmallVector<Operation *> sortedCoreTiles;
2981 for (auto lt : logicalTiles) {
2982 Operation *op = lt.getOperation();
2983 if (constrainedTiles.contains(op))
2984 continue;
2985 if (lt.getTileType() == AIETileType::CoreTile)
2986 sortedCoreTiles.push_back(op);
2987 }
2988 llvm::stable_sort(sortedCoreTiles, byMemWeightDesc);
2989
2990 for (auto *op : sortedCoreTiles) {
2991 TileID pos;
2992 bool found = false;
2993 for (size_t i = compIdx; i < availComp.size(); i++) {
2994 if (isLegalPosition(op, availComp[i])) {
2995 pos = availComp[i];
2996 std::swap(availComp[i], availComp[compIdx]);
2997 compIdx++;
2998 found = true;
2999 break;
3000 }
3001 }
3002 if (!found)
3003 return cast<LogicalTileOp>(op).emitError(
3004 "no available physical tile for placement");
3005 currentPlacement[op] = pos;
3006 physToLogical[pos] = op;
3007 movableTiles.push_back(op);
3008 }
3009 }
3010
3011 // Place unconstrained MemTile tiles sorted by memory weight (heaviest
3012 // first into spread positions), then shim tiles.
3013 {
3014 SmallVector<Operation *> sortedMemTiles, shimTiles;
3015 for (auto lt : logicalTiles) {
3016 Operation *op = lt.getOperation();
3017 if (constrainedTiles.contains(op))
3018 continue;
3019 AIETileType type = lt.getTileType();
3020 if (type == AIETileType::MemTile)
3021 sortedMemTiles.push_back(op);
3022 else if (type == AIETileType::ShimNOCTile)
3023 shimTiles.push_back(op);
3024 }
3025 llvm::stable_sort(sortedMemTiles, byMemWeightDesc);
3026
3027 // Each takes the next legal position of its pool, round robin.
3028 auto placeIn = [&](ArrayRef<Operation *> ops, ArrayRef<TileID> pool,
3029 size_t &next) -> LogicalResult {
3030 for (Operation *op : ops) {
3031 std::optional<TileID> pos, named;
3032 for (size_t i = 0; i < pool.size() && !pos; ++i) {
3033 TileID at = pool[(next + i) % pool.size()];
3034 if (isLegalPosition(op, at))
3035 pos = at;
3036 else if (!named && satisfiesConstraints(op, at) &&
3037 namedClash(op, namedAt(op, at)))
3038 named = at;
3039 }
3040 if (!pos && named)
3041 if (auto clash = namedClash(op, namedAt(op, *named)))
3042 return emitNamedClash(op, *named, *clash);
3043 if (!pos)
3044 return cast<LogicalTileOp>(op).emitError(
3045 "no available physical tile for placement");
3046 next++;
3047 currentPlacement[op] = *pos;
3048 movableTiles.push_back(op);
3049 }
3050 return success();
3051 };
3052 if (failed(placeIn(sortedMemTiles, availMem, memIdx)) ||
3053 failed(placeIn(shimTiles, availShim, shimIdx)))
3054 return failure();
3055 }
3056
3057 return success();
3058}
3059
3060void SAPlacer::initializeSAState() {
3061 initBoundingBoxes();
3062 initResourceTracking();
3063
3064 cascadePen = computePairingPenalty();
3065 int memPressure = computeMemoryPressure() + computeSoftTerms();
3066 totalCost =
3067 computeTotalHPWL() + getResourcePenalty() + cascadePen + memPressure;
3068
3069 deviceSlots = availability.compTiles.size() + movableTiles.size();
3070
3071 LLVM_DEBUG(llvm::dbgs() << "[SA] Initial cost: " << totalCost
3072 << " (HPWL=" << computeTotalHPWL()
3073 << ", resPenalty=" << getResourcePenalty()
3074 << "), movable tiles: " << movableTiles.size()
3075 << ", nets: " << nets.size()
3076 << ", fifos: " << fifoBuffers.size() << "\n");
3077}
3078
3079void SAPlacer::runSAMainLoop() {
3080 // Skip SA when there is nothing to optimize.
3081 bool hasCostTerms = !nets.empty() || !fifoBuffers.empty() ||
3082 !cascadeAdjacency.edges.empty() ||
3083 !neighbourCores.empty();
3084 if (movableTiles.empty() || !hasCostTerms)
3085 return;
3086
3087 // SA schedule parameters scaled by design and device.
3088 int numMovable = movableTiles.size();
3089 int numNets = nets.size();
3090
3091 int movesPerIter =
3092 std::clamp(static_cast<int>(numMovable * std::sqrt(std::max(numNets, 1))),
3093 config.minMovesPerIter, config.maxMovesPerIter);
3094
3095 int maxIters = std::max(
3096 config.minMaxIters,
3097 static_cast<int>(1000 * std::sqrt(static_cast<double>(numMovable) *
3098 std::max(numNets, 1))));
3099
3100 int greedyIters = config.greedyMultiplier * numMovable;
3101
3102 // A large effort saturates rather than overflowing the int conversion.
3103 auto scaled = [&](int budget) {
3104 double v = std::min(budget * config.effort,
3105 static_cast<double>(std::numeric_limits<int>::max()));
3106 return std::max(1, static_cast<int>(v));
3107 };
3108 movesPerIter = scaled(movesPerIter);
3109 // Same floor as movesPerIter above: a small positive effort must still
3110 // scale the greedy stage down, but never to zero -- skipping it entirely
3111 // is what leaves violations unresolved (see finalizePlacement's legality
3112 // check).
3113 greedyIters = scaled(greedyIters);
3114
3115 int numSamples = std::max(10 * numMovable, 50);
3116 double estimatedT = estimateInitialTemperature(numSamples);
3117 double initTemp =
3118 std::min(config.tempScaleEstimate * estimatedT,
3119 static_cast<double>(totalCost) * config.tempScaleCost);
3120 initTemp = std::max(initTemp, 1.0);
3121
3122 LLVM_DEBUG(llvm::dbgs() << "[SA] Schedule: movesPerIter=" << movesPerIter
3123 << " maxIters=" << maxIters
3124 << " initTemp=" << initTemp << "\n");
3125
3126 schedule = SASchedule(initTemp, movesPerIter, maxIters, greedyIters, config);
3127
3128 bestPlacement = currentPlacement;
3129 bestCost =
3130 (getResourcePenalty() == 0 && cascadePen == 0) ? totalCost : INT_MAX;
3131 bestOverallPlacement = currentPlacement;
3132 bestOverallCost = totalCost;
3133 zeroDeltaMoves = posDeltaMoves = negDeltaMoves = 0;
3134 acceptedUphill = rejectedMoves = 0;
3135
3136 while (!schedule.limitReached()) {
3137 for (int m = 0; m < schedule.getMovesPerIter(); m++) {
3138
3139 SmallVector<std::pair<Operation *, TileID>> moves;
3140 if (!generateMove(moves))
3141 continue;
3142 tryMove(moves);
3143 }
3144
3145 if (schedule.getIteration() % config.debugInterval == 0)
3146 LLVM_DEBUG(llvm::dbgs()
3147 << "[SA] Iter " << schedule.getIteration()
3148 << " T=" << llvm::format("%.3e", schedule.getTemperature())
3149 << " cost=" << totalCost << " best=" << bestCost << " accept="
3150 << llvm::format("%.3f", schedule.getAcceptanceRatio())
3151 << " d0=" << zeroDeltaMoves << " d+=" << posDeltaMoves
3152 << " d-=" << negDeltaMoves << " uphill=" << acceptedUphill
3153 << " rej=" << rejectedMoves
3154 << (schedule.isGreedy() ? " (greedy)" : "") << "\n");
3155
3156 // Periodic full recompute to reset incremental cost drift.
3157 if (schedule.getIteration() % config.fullRecomputeInterval == 0 &&
3158 schedule.getIteration() > 0) {
3159 initResourceTracking();
3160 cascadePen = computePairingPenalty();
3161 totalCost = computeTotalHPWL() + getResourcePenalty() + cascadePen +
3162 computeMemoryPressure() + computeSoftTerms();
3163 }
3164
3165 schedule.cool();
3166 }
3167}
3168
3169//===----------------------------------------------------------------------===//
3170// Move acceptance
3171//===----------------------------------------------------------------------===//
3172
3173void SAPlacer::tryMove(SmallVector<std::pair<Operation *, TileID>> &moves) {
3174 // What the move changes is journaled from here, and the terms it may
3175 // recompute are kept, for a rejection to restore.
3176 commitMove();
3177 SmallVector<std::pair<Operation *, TileID>> oldPlacements;
3178 for (auto &[t, _] : moves)
3179 oldPlacements.push_back({t, currentPlacement[t]});
3180 int oldResPenalty = cachedResourcePenalty;
3181 int oldMemSpillover = memSpilloverPenalty, oldBDCount = bdCountPenalty,
3182 oldDelegate = delegatePenalty, oldDMA = dmaPenalty;
3183 int oldCoreOverflow = coreOverflowPenalty;
3184 SmallVector<TileID> oldCoreOverflowTiles = coreOverflowTiles;
3185 int oldPositionsOverLocks = positionsOverLocks;
3186 StreamCuts oldCuts = cuts;
3187 int oldStreamCut = streamCutPenalty;
3188 int oldPortsOver = portsOver;
3189 int oldDdr = ddrPenalty;
3190 int64_t oldDdrTotal = ddrTotal;
3191 int oldCoresChanged = coresChanged;
3192
3193 // Apply moves: update placement maps and compute HPWL delta.
3194 for (auto &[t, _] : moves)
3195 physToLogical.erase(currentPlacement[t]);
3196 SmallVector<SmallVector<std::pair<size_t, NetBoundingBox>>> allBackups(
3197 moves.size());
3198 int hpwlDelta = 0;
3199 for (size_t i = 0; i < moves.size(); i++) {
3200 hpwlDelta += evaluateMove(moves[i].first, moves[i].second, allBackups[i]);
3201 currentPlacement[moves[i].first] = moves[i].second;
3202 }
3203 for (auto &[t, pos] : moves)
3204 physToLogical[pos] = t;
3205
3206 // Compute total cost delta across all cost terms.
3207 int oldCascade = cascadePen;
3208 int oldPressure = cachedPressure;
3209 int newResPenalty = updateResourcePenalty(oldPlacements);
3210 int newCascade = llvm::any_of(moves,
3211 [&](const auto &move) {
3212 return pairedTiles.contains(move.first);
3213 })
3214 ? computePairingPenalty()
3215 : cascadePen;
3216 int newPressure = computeMemoryPressure() + computeSoftTerms();
3217 int delta = hpwlDelta + (newResPenalty - oldResPenalty) +
3218 (newCascade - oldCascade) + (newPressure - oldPressure);
3219
3220 if (delta == 0)
3221 zeroDeltaMoves++;
3222 else if (delta > 0)
3223 posDeltaMoves++;
3224 else
3225 negDeltaMoves++;
3226
3227 // Accept improving moves unconditionally; accept worsening moves
3228 // with probability exp(-delta/T).
3229 bool accept =
3230 delta <= 0 ||
3231 (schedule.getTemperature() > 0 &&
3232 drawUnitReal(rng) < std::exp(-delta / schedule.getTemperature()));
3233
3234 if (accept) {
3235 if (delta > 0)
3236 acceptedUphill++;
3237 totalCost += delta;
3238 cascadePen = newCascade;
3239 cachedPressure = newPressure;
3240 schedule.record(true);
3241 if (totalCost < bestOverallCost) {
3242 bestOverallCost = totalCost;
3243 bestOverallPlacement = currentPlacement;
3244 }
3245 // Only update bestPlacement when fully legal (no resource or cascade
3246 // violations).
3247 if (totalCost < bestCost && newResPenalty == 0 && newCascade == 0) {
3248 bestCost = totalCost;
3249 bestPlacement = currentPlacement;
3250 }
3251 } else {
3252 // Revert: undo moves in reverse order and restore saved state.
3253 for (auto &[t, pos] : moves)
3254 physToLogical.erase(pos);
3255 for (int i = moves.size() - 1; i >= 0; i--) {
3256 revertMove(allBackups[i]);
3257 currentPlacement[moves[i].first] = oldPlacements[i].second;
3258 }
3259 for (auto &[op, oldPos] : oldPlacements)
3260 physToLogical[oldPos] = op;
3261 replanLinks(
3262 llvm::map_to_vector(replannedLinks, [](ReplannedLink replanned) {
3263 return std::make_pair(replanned.index, replanned.from);
3264 }));
3265 rollbackMove();
3266 positionsOverLocks = oldPositionsOverLocks;
3267 cuts = std::move(oldCuts);
3268 streamCutPenalty = oldStreamCut;
3269 portsOver = oldPortsOver;
3270 ddrPenalty = oldDdr;
3271 ddrTotal = oldDdrTotal;
3272 coresChanged = oldCoresChanged;
3273 cachedResourcePenalty = oldResPenalty;
3274 memSpilloverPenalty = oldMemSpillover;
3275 bdCountPenalty = oldBDCount;
3276 delegatePenalty = oldDelegate;
3277 dmaPenalty = oldDMA;
3278 coreOverflowPenalty = oldCoreOverflow;
3279 coreOverflowTiles = std::move(oldCoreOverflowTiles);
3280 rejectedMoves++;
3281 schedule.record(false);
3282 }
3283}
3284
3285void SAPlacer::commitMove() {
3286 currentMemUsage.commit();
3287 currentLockDemand.commit();
3288 currentDMAUsage.commit();
3289 sharedMemDestination.commit();
3290 coreFifoBuffers.commit();
3291 coreUnplacedAt.commit();
3292 bdShortfallAt.commit();
3293 dmaPenaltyAt.commit();
3294 ddrScoreOf.commit();
3295 runtimeBdAt.commit();
3296 netStreams.commit();
3297 keyAt.commit();
3298 streamsAt.commit();
3299 incomingAt.commit();
3300 incomingCount.commit();
3301 pinLog.clear();
3302 claimLog.clear();
3303 coreFifoLog.clear();
3304}
3305
3306void SAPlacer::rollbackMove() {
3307 currentMemUsage.rollback();
3308 currentLockDemand.rollback();
3309 currentDMAUsage.rollback();
3310 sharedMemDestination.rollback();
3311 coreFifoBuffers.rollback();
3312 coreUnplacedAt.rollback();
3313 bdShortfallAt.rollback();
3314 dmaPenaltyAt.rollback();
3315 ddrScoreOf.rollback();
3316 runtimeBdAt.rollback();
3317 netStreams.rollback();
3318 keyAt.rollback();
3319 streamsAt.rollback();
3320 incomingAt.rollback();
3321 incomingCount.rollback();
3322 for (auto &[at, end, sign] : llvm::reverse(pinLog))
3323 pinUse.place(at, end, -sign);
3324 for (auto &[at, claim, sign] : llvm::reverse(claimLog))
3325 pinUse.claim(at, claim, -sign);
3326 pinLog.clear();
3327 claimLog.clear();
3328 coreFifoLog.clear();
3329}
3330
3331//===----------------------------------------------------------------------===//
3332// Debug output
3333//===----------------------------------------------------------------------===//
3334
3335void SAPlacer::printPlacementStats(int64_t elapsedMs) const {
3336 int finalHPWL = computeTotalHPWL();
3337 int finalHardPenalty = getResourcePenalty();
3338 int finalPressure = computeMemoryPressure() + computeSoftTerms();
3339 int finalCascade = computePairingPenalty();
3340 bool isLegal = (finalHardPenalty == 0 && finalCascade == 0);
3341
3342 llvm::dbgs() << "[SA] seed=" << rngSeed << " Final HPWL=" << finalHPWL
3343 << ", resPenalty=" << finalHardPenalty
3344 << ", pressure=" << finalPressure << ", cascade=" << finalCascade
3345 << ", cut=" << cuts.over() << ", ddr=" << ddrPenalty
3346 << ", cores-changed=" << coresChanged
3347 << ", legal=" << (isLegal ? "yes" : "NO") << "\n";
3348 llvm::dbgs() << "[SA] " << schedule.getIteration() << " iters, "
3349 << movableTiles.size() << " tiles, " << nets.size() << " nets, "
3350 << allocates.size() << " allocates, " << elapsedMs << " ms\n";
3351 llvm::dbgs() << "[SA] Moves: d-=" << negDeltaMoves << " d0=" << zeroDeltaMoves
3352 << " d+=" << posDeltaMoves << " uphill=" << acceptedUphill
3353 << " rej=" << rejectedMoves << "\n";
3354
3355 // Per-tile resource utilization (tiles above 75% capacity).
3356 int64_t coreCap = targetModel->getLocalMemorySize();
3357 int64_t memCap = targetModel->getMemTileSize();
3358 for (auto &[pos, used] : currentMemUsage) {
3359 auto type = targetModel->getTileType(pos.col, pos.row);
3360 int64_t cap = (type == AIETileType::MemTile) ? memCap : coreCap;
3361 if (used > cap * 3 / 4)
3362 llvm::dbgs() << "[SA-RES] mem(" << pos.col << "," << pos.row
3363 << "): " << used << "/" << cap
3364 << (used > cap ? " OVERFLOW" : "") << "\n";
3365 }
3366 for (auto &[pos, usage] : currentDMAUsage) {
3367 auto [maxIn, maxOut] = getDMACapacity(*targetModel, pos);
3368 if (usage.first >= maxIn || usage.second >= maxOut)
3369 llvm::dbgs() << "[SA-RES] dma(" << pos.col << "," << pos.row
3370 << "): in=" << usage.first << "/" << maxIn
3371 << " out=" << usage.second << "/" << maxOut
3372 << (usage.first > maxIn || usage.second > maxOut
3373 ? " OVERFLOW"
3374 : " AT-LIMIT")
3375 << "\n";
3376 }
3377
3378 // Detailed breakdown for overflowing core tiles: neighbor spare capacity.
3379 for (auto &[pos, used] : currentMemUsage) {
3380 auto type = targetModel->getTileType(pos.col, pos.row);
3381 if (type != AIETileType::CoreTile || used <= coreCap)
3382 continue;
3383 int64_t overflow = used - coreCap;
3384 for (TileID n : getMemAffinityNeighbors(*targetModel, pos)) {
3385 auto it = currentMemUsage.find(n);
3386 int64_t nbrUsed = it != currentMemUsage.end() ? it->second : 0;
3387 llvm::dbgs() << " nbr(" << n.col << "," << n.row << "): used=" << nbrUsed
3388 << " spare=" << std::max(coreCap - nbrUsed, int64_t{0})
3389 << "\n";
3390 }
3391 llvm::dbgs() << "[SA-PENALTY] tile(" << pos.col << "," << pos.row
3392 << "): used=" << used << " cap=" << coreCap
3393 << " overflow=" << overflow << "\n";
3394 }
3395}
3396
3397//===----------------------------------------------------------------------===//
3398// Post-SA finalization
3399//===----------------------------------------------------------------------===//
3400
3401LogicalResult SAPlacer::finalizePlacement(DeviceOp device) {
3402 // Restore best placement found during SA. Skip if SA loop didn't run
3403 // (bestOverallCost stays at INT_MAX when runSAMainLoop returns early).
3404 finalCost = totalCost;
3405 if (bestOverallCost < INT_MAX) {
3406 if (bestCost < INT_MAX) {
3407 currentPlacement = bestPlacement;
3408 finalCost = bestCost;
3409 } else {
3410 currentPlacement = bestOverallPlacement;
3411 finalCost = bestOverallCost;
3412 }
3413 physToLogical.clear();
3414 for (auto &[op, pos] : currentPlacement)
3415 physToLogical[pos] = op;
3416 initResourceTracking();
3417 }
3418
3419 // Generate allocates (state is fresh from initResourceTracking)
3420 generateAllocates();
3421 finalLockGroups = lockGroups().size();
3422 finalLockPenalty = computeLockPenalty(&finalLockStopped);
3423
3424 auto endTime = std::chrono::steady_clock::now();
3425 auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(
3426 endTime - startTime);
3427
3428 LLVM_DEBUG(printPlacementStats(elapsed.count()));
3429
3430 // SA optimizes for legality but is not guaranteed to reach it (e.g. a very
3431 // low --sa-effort can starve the greedy stage that normally drives hard
3432 // violations to zero). Cascade and shared memory pairs and delegate reach
3433 // are exact, and a placement breaking them would only fail later and less
3434 // clearly, so they fail here. Memory, DMA channel and BD use are this pass's
3435 // estimates of what later passes allocate, and those passes check them
3436 // exactly, so an overrun here is a warning.
3437 int finalPairing = computePairingPenalty();
3438 int finalDelegate = computeDelegatePenalty();
3439 if (finalPairing != 0 || finalDelegate != 0) {
3440 InFlightDiagnostic diag =
3441 device.emitError("SA placer failed to find a legal placement (cascade "
3442 "and shared memory penalty=")
3443 << finalPairing << ", delegate penalty=" << finalDelegate
3444 << "); try increasing --sa-effort";
3445 explainPenalties(diag);
3446 return failure();
3447 }
3448 if (int estimated = getResourcePenalty() - finalDelegate; estimated != 0) {
3449 InFlightDiagnostic diag =
3450 device.emitWarning("SA placer's resource estimate is over capacity "
3451 "(penalty=")
3452 << estimated
3453 << "); later passes check exactly, and increasing --sa-effort may help";
3454 explainPenalties(diag);
3455 }
3456
3457 result = currentPlacement;
3458 return success();
3459}
3460
3461void SAPlacer::explainPenalties(InFlightDiagnostic &diag) {
3462 SmallVector<TileID> spill, core, locks, channels, bds, delegates, pairing,
3463 none;
3464 int spillPenalty = computeMemSpilloverPenalty(&spill);
3465 int corePenalty = computeCoreOverflowPenalty(&core);
3466 int lockPenalty = computeLockPenalty(nullptr, &locks);
3467 int channelPenalty = 0;
3468 int bdPenalty = computeBDCountPenalty();
3469 for (auto &[at, ids] : bdShortfallAt)
3470 if (ids)
3471 bds.push_back(at);
3472 for (auto &[at, _] : currentDMAUsage) {
3473 int ids = 0;
3474 int penalty = computeTileDMAPenalty(at, &ids);
3475 if (penalty != ids) {
3476 channelPenalty += penalty - ids;
3477 channels.push_back(at);
3478 }
3479 if (ids) {
3480 bdPenalty += ids;
3481 bds.push_back(at);
3482 }
3483 }
3484 int delegatePenalty = computeDelegatePenalty(&delegates);
3485 int cutPenalty = config.streamCutPenaltyPerChannel * cuts.over();
3486 int pairingPenalty = computePairingPenalty(&pairing);
3487
3488 // The tuner reads these names.
3489 std::tuple<StringRef, int, SmallVector<TileID> &> terms[] = {
3490 {"memory spillover", spillPenalty, spill},
3491 {"core overflow", corePenalty, core},
3492 {"locks", lockPenalty, locks},
3493 {"DMA channels", channelPenalty, channels},
3494 {"BD ids", bdPenalty, bds},
3495 {"delegates", delegatePenalty, delegates},
3496 {"cascade and shared memory pairing", pairingPenalty, pairing},
3497 {"stream cuts", cutPenalty, none}};
3498 for (auto &[term, penalty, tiles] : terms) {
3499 if (!penalty)
3500 continue;
3501 llvm::sort(tiles);
3502 tiles.erase(llvm::unique(tiles), tiles.end());
3503 Operation *anchor = nullptr;
3504 // Structurally alike tile ops share a rank; the first written anchors.
3505 auto consider = [&](Operation *op) {
3506 unsigned rank = collected.rank.lookup(op);
3507 if (!anchor || rank < collected.rank.lookup(anchor) ||
3508 (rank == collected.rank.lookup(anchor) &&
3509 op->isBeforeInBlock(anchor)))
3510 anchor = op;
3511 };
3512 if (!tiles.empty()) {
3513 for (auto &[op, at] : currentPlacement)
3514 if (at == tiles.front())
3515 consider(op);
3516 for (Operation *op : physicalTiles.lookup(tiles.front()))
3517 consider(op);
3518 }
3519 Diagnostic &note =
3520 anchor ? diag.attachNote(anchor->getLoc()) : diag.attachNote();
3521 note << term << " penalty=" << penalty;
3522 for (auto [i, at] : llvm::enumerate(tiles))
3523 note << (i ? ", " : " on ") << "(" << at.col << ", " << at.row << ")";
3524 }
3525}
virtual std::optional< TileID > getMemNorth(TileID src) const =0
Return the tile ID of the memory to the north of the given tile, if it exists.
virtual AIETileType getTileType(int col, int row) const =0
Return the tile type for the given tile coordinates.
virtual std::optional< TileID > getMemSouth(TileID src) const =0
Return the tile ID of the memory to the south of the given tile, if it exists.
virtual std::optional< TileID > getMemEast(TileID src) const =0
Return the tile ID of the memory to the east of the given tile, if it exists.
virtual std::optional< TileID > getMemWest(TileID src) const =0
Return the tile ID of the memory to the west of the given tile, if it exists.
virtual uint32_t getMemTileLoadStoreBusWidth() const
Return the data bus width (in bits) for load/store operations of a memory tile.
SharedMemory
Which of two tiles' memory modules both of them can address.
static WalkChoice searchWalkProduct(llvm::ArrayRef< llvm::SmallVector< int64_t > > bytes, llvm::function_ref< bool(llvm::ArrayRef< unsigned >)> places, unsigned maxTries)
Tries the choices of one set per tile, bytes[tile] giving each of its sets' bytes walked whole,...
static BDWalkSets walkSetsThatFit(const AIETargetModel &target, int col, int row, llvm::ArrayRef< BDPlanEnd > ends, llvm::ArrayRef< unsigned > poolOf, llvm::ArrayRef< BDWalkPool > pools, llvm::function_ref< bool(DMAChannelDir, int)> free, llvm::function_ref< int64_t(int)> spent, unsigned maxSets=std::numeric_limits< unsigned >::max())
Every set of walkable pools whose walk lets planBDChannels fit ends (poolOf gives each end's pool),...
static llvm::SmallVector< mlir::Operation * > lockOwners(const AIETargetModel &target, ObjectFifoPoolOp pool)
The ops whose locks allocation and the SA each make for pool: with semaphore locks,...
static llvm::SmallVector< int > groupCounts(const AIETargetModel &target, int64_t depth, int owners)
The lock groups owners lock owners of a pool of depth objects take, by count.
Definition AIELockPlan.h:79
static bool dmaLocalOnly(AIETileType type)
Whether a DMA on a tile of type uses only its own tile's locks: every DMA does but a mem tile's.
Definition AIELockPlan.h:90
static bool reaches(const AIETargetModel &target, llvm::ArrayRef< TileID > user, llvm::ArrayRef< TileID > memory, bool localOnly)
Whether a tile at one of user reaches memory at one of memory; with localOnly, only at its own positi...
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)
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
const AIETargetModel * targetModel
Definition AIEPlacer.h:556
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
llvm::SmallVector< llvm::DenseMap< TileID, unsigned > > neighbourCores
Definition AIEPlacer.h:552
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
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={})
TileAvailability availability
Definition AIEPlacer.h:561
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
bool needsLocks(ObjectFifoPoolOp pool) const
Whether pool gets locks.
static bool isShimEndType(std::optional< AIETileType > type)
Definition AIEPlacer.h:1198
mlir::LogicalResult place(DeviceOp device) override
void record(bool accepted)
double getAcceptanceRatio() const
void sortLargestBufferFirst(Range &&buffers, BytesFn bytes)
Buffers are laid out, and given a tile, largest buffer first: by the address layout below,...
TileLayout layoutTile(const TileLayoutProblem &problem, TileLayoutStats &stats)
Lays out problem as assign-buffer-addresses does, without touching IR.
TileLayoutBuffer tileLayoutBuffer(BufferOp buffer, const TileMemoryLimits &limits)
What assign-buffer-addresses lays buffer out as, on a tile with limits.
llvm::SmallVector< unsigned > demandFirstOrder(llvm::ArrayRef< SpillPool > pools)
aie-objectfifo-allocate's demand-first packing order of pools, given in its size-first order,...
bool hasCoreAccess(DeviceOp device, mlir::Value tile, ObjectFifoCreateOp fifo, ObjectFifoPort port)
int64_t getMemRefSizeInBytes(mlir::MemRefType type, const mlir::DataLayout &layout)
llvm::SmallVector< TileID, 2 > memTileSpillNeighbours(const AIETargetModel &target, TileID home)
The tiles a mem tile buffer homed at home may spill to: those in its row home shares memory with,...
struct TileID { friend std::ostream &operator<<(std::ostream &os, const TileID &s) { os<< "TileID("<< s.col<< ", "<< s.row<< ")"; return os; } friend std::string to_string(const TileID &s) { std::ostringstream ss; ss<< s; return ss.str(); } friend llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const TileID &s) { os<< to_string(s); return os; } inline bool operator<(const TileID &rhs) const { return std::tie(col, row)< std::tie(rhs.col, rhs.row); } bool operator==(const TileID &rhs) const { return std::tie(col, row)==std::tie(rhs.col, rhs.row); } bool operator!=(const TileID &rhs) const { return !(*this==rhs);} int col, row;} TileID
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
uint32_t requiredBufferAlignBits(uint32_t busAlignBits, uint32_t maxVecAlignBits, int64_t sizeBytes)
Return the alignment (in bits) a buffer of sizeBytes must satisfy.
int64_t bufferAlignBytes(BufferOp buffer, uint32_t tileAlignBitWidth, uint32_t maxVecAlignBits)
The alignment assign-buffer-addresses places buffer at, in bytes: the vector rule when aligned,...
TileMemoryLimits tileMemoryLimits(const AIETargetModel &targetModel, AIETileType tileType)
llvm::SmallVector< unsigned > memTileSpillComponents(llvm::ArrayRef< TileID > homes, llvm::function_ref< llvm::SmallVector< TileID, 2 >(TileID)> neighboursOf)
For each of homes, the index of its component: homes whose buffers may spill to a tile in common,...
llvm::SmallVector< int64_t > bytes
The bytes each set walks whole.
llvm::SmallVector< llvm::SmallVector< unsigned > > sets
llvm::SmallVector< LinkPoolSharer > sharers
Definition AIEDialect.h:439
llvm::SmallVector< std::optional< unsigned > > tiles
bool stopped
The exact packing ran out of kPackBudget steps before it decided.
llvm::SmallVector< mlir::Operation * > endpoints
Definition AIEPlacer.h:1131
NetBoundingBox bb
Definition AIEPlacer.h:1132
llvm::SmallVector< ObjectFifoLinkOp > objectFifoLinks
Definition AIEPlacer.h:169
llvm::SmallVector< ObjectFifoCreateOp > objectFifos
Definition AIEPlacer.h:168
llvm::SmallVector< LogicalTileOp > logicalTiles
Definition AIEPlacer.h:167
mlir::Operation * pool
Definition AIEDialect.h:451
One buffer of a tile, as assign-buffer-addresses lays it out.
int64_t alignBytes
bufferAlignBytes.
llvm::SmallVector< int, 2 > spaceBanks
The banks the buffer's memory space allows, when it names some.
llvm::SmallVector< TileLayoutBuffer > buffers
In the order the device holds them.
bool hasCore
Whether the tile runs a core, whose sections need a contiguous region.
MemoryRun stackRun
The core's stack; empty without one.
std::optional< int > stackBank
For a stack pinned to a bank but not an address: the bank, and the alignment of the address chosen in...
int64_t budget
Placements each search may try before it gives up.
@ NoRoom
Buffer failed fits nowhere once the others are placed.
int64_t unplacedBytes
Bytes of the buffers left without an address on NoRoom.
A memtile is reached by DMA rather than by core vector load and store, so its bus width also covers t...