MLIR-AIE 1.4.6.dev
AIEPlacer.h
Go to the documentation of this file.
1//===- AIEPlacer.h ----------------------------------------------*- C++ -*-===//
2//
3// Copyright (C) 2026 Advanced Micro Devices, Inc.
4// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
5//
6//===----------------------------------------------------------------------===//
7
8#ifndef AIE_PLACER_H
9#define AIE_PLACER_H
10
18#include "llvm/ADT/BitVector.h"
19#include "llvm/ADT/MapVector.h"
20#include "llvm/ADT/SmallBitVector.h"
21#include "llvm/ADT/SortedVectorMap.h"
22
23#include <array>
24#include <deque>
25#include <map>
26#include <random>
27#include <tuple>
28#include <unordered_map>
29
30namespace xilinx::AIE {
31
32/// Placement algorithm type for pass option
34
35/// Get DMA channel capacity (maxIn, maxOut) for a tile position: its S2MM and
36/// MM2S channel counts.
37inline std::pair<int, int> getDMACapacity(const AIETargetModel &tm,
38 TileID tile) {
39 return {tm.getNumDMAChannels(tile.col, tile.row, DMAChannelDir::S2MM),
40 tm.getNumDMAChannels(tile.col, tile.row, DMAChannelDir::MM2S)};
41}
42
43// Streams through the North and South ports of a tile's stream switch.
45 int northIn = 0, northOut = 0, southIn = 0, southOut = 0;
46
48 northIn += other.northIn;
49 northOut += other.northOut;
50 southIn += other.southIn;
51 southOut += other.southOut;
52 return *this;
53 }
54};
55
56// The streams each boundary between neighbouring rows or columns carries one
57// way, against the channels across it, as Pathfinder::cutOverflow counts
58// them: every circuit tree crossing it takes a channel, and the packet flows
59// crossing it one more. Demand counts only streams sure to be routed and
60// capacity every wire, so a placement over it cannot route.
62public:
63 StreamCuts() = default;
64 explicit StreamCuts(const AIETargetModel &target);
65 // Adds (`sign` 1) or removes (-1) a stream from `src` to `dsts`.
66 void add(TileID src, llvm::ArrayRef<TileID> dsts, bool packet, int sign);
67 // The channels the boundaries are short of.
68 int over() const;
69 // The squared streams past `fraction` of each boundary's channels.
70 int64_t near(double fraction) const;
71
72private:
73 unsigned indexOf(bool rows, int below, bool up) const;
74 int columns = 0;
75 llvm::SmallVector<int, 32> capacity, circuits, packets;
76};
77
78// maps logical tile operations to physical coordinates
79using PlacementResult = llvm::DenseMap<mlir::Operation *, TileID>;
80
81// Track available tiles and resource usage
83 std::vector<TileID> compTiles;
84 std::vector<TileID> nonCompTiles; // Memory and shim tiles
85
86 // O(1) membership shadow of `compTiles` used by SequentialPlacer's
87 // satisfiesComputePeer forward-look, which checks whether each of a
88 // candidate's physical compute neighbors is still free. Without it the
89 // forward-look would do an O(|compTiles|) std::find per direction per
90 // candidate per LTO, which scales as O(N * M^2) on large arrays. Must be
91 // kept in sync with `compTiles` by any code that mutates the vector
92 // (initialize(), limitCoresPerColumn(), removeTile()).
93 llvm::DenseSet<TileID> compTilesSet;
94 // Core positions a physical aie.tile's own aie.core already holds.
95 llvm::DenseSet<TileID> physicalCores;
96 // Compute tiles cores-per-col leaves out. A core pinned by column or row
97 // outranks the budget and may still take one.
98 std::vector<TileID> overBudgetCompTiles;
99
100 llvm::DenseMap<TileID, int> inputChannelsUsed;
101 llvm::DenseMap<TileID, int> outputChannelsUsed;
102 llvm::DenseMap<TileID, StreamDemand> streamsUsed;
103 // The logical tiles placed here whose runtime tasks take BD ids.
104 llvm::DenseMap<TileID, llvm::SmallVector<mlir::Operation *>> runtimeBdTiles;
105
106 void removeTile(TileID tile, AIETileType type);
107};
108
109// Abstract placer interface
110class Placer {
111public:
112 Placer() = default;
113 virtual ~Placer() = default;
114
115 virtual void initialize(DeviceOp device, bool controlOverlay,
117
118 // The program key of each tile op holding a core, and, for each
119 // configuration loaded right before or after this one and already placed,
120 // the key of the core at each of its positions: a core whose program a
121 // neighbour runs at the same position needs no rewrite when they switch.
123 llvm::DenseMap<mlir::Operation *, unsigned> keys,
124 llvm::SmallVector<llvm::DenseMap<TileID, unsigned>> neighbours) {
125 coreKeys = std::move(keys);
126 neighbourCores = std::move(neighbours);
127 }
128
129 virtual mlir::LogicalResult place(DeviceOp device) = 0;
130
131 virtual llvm::StringRef getName() const = 0;
132
133 std::optional<TileID> getPlacement(mlir::Operation *logicalTile) const {
134 auto it = result.find(logicalTile);
135 if (it != result.end())
136 return it->second;
137 return std::nullopt;
138 }
139
140 // Buffer allocation redirects: (ObjectFifoCreateOp, delegate TileID)
141 // Generated when a core tile's buffers exceed local memory and must
142 // spill to a neighbor tile's memory module.
143 using AllocateInfo = std::pair<mlir::Operation *, TileID>;
144 llvm::SmallVector<AllocateInfo> &getAllocates() { return allocates; }
145
146 // Per-LTO peer edges indexed by either endpoint. `tileToEdges` only
147 // indexes `LogicalTileOp` endpoints; `TileOp` peers carry their own
148 // coords.
149 struct Adjacency {
150 llvm::SmallVector<std::pair<TileLike, TileLike>, 4> edges;
151 llvm::DenseMap<mlir::Operation *, llvm::SmallVector<unsigned, 2>>
153
154 void addEdge(TileLike first, TileLike second);
155
156 // Convenience for IR walkers: skip if either Value isn't a TileLike.
157 void addEdgeFromValues(mlir::Value a, mlir::Value b);
158
159 // True if `op` has at least one edge in this adjacency.
160 bool hasEdges(mlir::Operation *op) const {
161 return tileToEdges.count(op) != 0;
162 }
163 };
164
165 // IR operations collected from a DeviceOp for placement.
167 llvm::SmallVector<LogicalTileOp> logicalTiles;
168 llvm::SmallVector<ObjectFifoCreateOp> objectFifos;
169 llvm::SmallVector<ObjectFifoLinkOp> objectFifoLinks;
170 llvm::SmallVector<ObjectFifoAllocateOp> objectFifoAllocates;
171 llvm::SmallVector<CascadeFlowOp> cascadeFlows;
172 llvm::SmallVector<FlowOp> flows;
173 llvm::SmallVector<PacketFlowOp> pktFlows;
174 llvm::SmallVector<RouteOp> routes;
175 // The device's top-level ops by StructuralGraph::rank, for ties.
176 llvm::DenseMap<mlir::Operation *, unsigned> rank;
177 };
178
179 // Collect all placement-relevant operations from the device.
180 static CollectedOps collectOperations(DeviceOp device);
181
182 // The (input, output) DMA channels each tile's flows, packet flows, route
183 // endpoints and channel claims (DMAChannelAnalysis's: program starts,
184 // runtime tasks, shim allocations) take: one per endpoint however many
185 // routes name it, and one per channel named by index. Tiles with both
186 // coordinates are keyed by position. With `named`, the (output, index)
187 // channels named by index, by tile; with `keys`, the tile each tile's
188 // demand is keyed by.
189 static llvm::MapVector<mlir::Operation *, std::pair<int, int>>
191 llvm::ArrayRef<FlowOp> flows, llvm::ArrayRef<PacketFlowOp> pktFlows,
192 llvm::ArrayRef<RouteOp> routes,
193 llvm::ArrayRef<DMAChannelAnalysis::ChannelClaim> claims,
194 llvm::DenseMap<mlir::Operation *, llvm::SmallVector<std::pair<int, int>>>
195 *named = nullptr,
196 llvm::DenseMap<mlir::Operation *, mlir::Operation *> *keys = nullptr);
197
198 // Check if a logical tile's col/row constraints are satisfied at a position.
199 static bool satisfiesConstraints(mlir::Operation *tile, TileID pos);
200
201 // Adjacency builders: pure IR walkers with no placer-specific state.
202
203 // Edge: (cascade source, dest).
204 static Adjacency
205 buildCascadeAdjacency(llvm::ArrayRef<CascadeFlowOp> cascadeFlows);
206
207 // Edge: (producer LTO, consumer LTO) for every ObjectFifo whose producer
208 // AND consumer are CoreTile LTOs.
209 static Adjacency
210 buildComputePeerAdjacency(llvm::ArrayRef<ObjectFifoCreateOp> objectFifos);
211
212 // Edge: (producer, consumer) per forcesSharedMemory() ObjectFifo with one
213 // consumer.
214 static Adjacency
215 buildSharedMemAdjacency(llvm::ArrayRef<ObjectFifoCreateOp> objectFifos);
216
217 // Edge: (producer, consumer_i) per fifo.
218 static Adjacency
219 buildObjectFifoAdjacency(llvm::ArrayRef<ObjectFifoCreateOp> objectFifos);
220
221 // Edge: (src, dst) per `aie.flow`; cross-product per `aie.packet_flow`.
222 static Adjacency buildFlowAdjacency(llvm::ArrayRef<FlowOp> flows,
223 llvm::ArrayRef<PacketFlowOp> pktFlows);
224
225 // A shim tile op's ends on one side, as ShimTransferSpans::plan reads them.
226 struct ShimSide {
227 llvm::SmallVector<mlir::StringAttr> ends;
228 llvm::SmallVector<std::pair<int, llvm::SmallVector<mlir::StringAttr>>>
230 llvm::SmallVector<int> pinned;
231 };
232 // Each shim tile op's sides, [0] receiving and [1] sending, the tile ops
233 // and each side's ends in `rank` order, shared channels by index.
235 llvm::MapVector<mlir::Operation *, std::array<ShimSide, 2>>;
236 // With `routeKeys` (flowChannelDemand's `keys`), a route endpoint's end
237 // goes to the tile its channel demand is keyed by.
239 DeviceOp device, llvm::ArrayRef<ObjectFifoCreateOp> objectFifos,
240 const llvm::DenseMap<mlir::Operation *, unsigned> &rank,
241 const llvm::DenseMap<mlir::Operation *, mlir::Operation *> &routeKeys =
242 {});
243 // The channels `sides` save in one direction below one per end, per
244 // ShimTransferSpans::plan, with `extra` ends joining and objectFIFO ends
245 // pinning `pinnedHere` there.
246 static int shimChannelsSaved(const ShimTransferSpans &spans,
247 llvm::ArrayRef<const ShimSide *> sides,
248 llvm::ArrayRef<mlir::StringAttr> extra,
249 llvm::ArrayRef<int> pinnedHere);
250
251 // The objectFIFO ends that pin one DMA channel of one tile share it, as
252 // objectFIFO allocation lets them: sending ends off a shim or off a core
253 // that pushes its tasks, told apart by packet id, and receiving ends that
254 // take objects out of order.
256 public:
257 // The end of `fifo` (its producer's when `consumer` is empty) on `tile`
258 // pinning `channel`. `movesByDma`: the fifo moves by DMA wherever its
259 // ends are placed (dmaReason(), or an end off a core tile); otherwise
260 // neighbouring cores' shared memory may carry it, and its pin holds only
261 // where it does not.
262 struct End {
263 ObjectFifoCreateOp fifo;
264 std::optional<unsigned> consumer;
265 mlir::Operation *tile;
266 bool sends;
269 };
270 PinnedChannels() = default;
271 // With `packetSwitched`, an end asking for no packet header gets one.
272 PinnedChannels(const AIETargetModel &targetModel, bool packetSwitched)
273 : targetModel(&targetModel), packetSwitched(packetSwitched) {}
274 // The end `fifo` pins a DMA channel by, if it does: the producer when
275 // `consumer` is null, otherwise that consumer.
276 static std::optional<End> endOf(ObjectFifoCreateOp fifo,
277 std::optional<unsigned> consumer);
278 // Why `a` and `b`, pinning one channel of one tile, cannot share it;
279 // nothing when they can.
280 std::optional<std::string> whyApart(End a, End b) const;
281 // The channel `end` shares with the ends of its own tile op that took it
282 // before, numbered by the first. Each pair that cannot share it and, both
283 // moving by DMA wherever placed, would hold it together wherever their
284 // tile goes is diagnosed on the fifo of lower `rank`.
285 unsigned share(End end,
286 const llvm::DenseMap<mlir::Operation *, unsigned> &rank);
287 // Whether share() diagnosed an end, which fails the placement.
288 bool failed() const { return diagnosed; }
289 // Whether `end` may take turns on the channel of `claim`, as allocation
290 // lets a pinned end: a shim allocation whose aie.shareable_with names it,
291 // when it sends packet-switched or receives out of order.
292 bool sharesClaim(End end,
293 const DMAChannelAnalysis::ChannelClaim &claim) const;
294
295 private:
296 const AIETargetModel *targetModel = nullptr;
297 bool packetSwitched = false;
298 bool diagnosed = false;
299 llvm::DenseMap<std::tuple<mlir::Operation *, int, int>,
300 std::pair<llvm::SmallVector<End, 2>, unsigned>>
301 taken;
302 };
303
304 // The pinned ends at each position, where the ends of tiles placed together
305 // meet: one channel serves those that may share it, and two of different
306 // tile ops that may not clash there. Two of one tile op clash wherever it
307 // goes when both move by DMA wherever placed, which PinnedChannels::share
308 // reports; otherwise they clash only where both are placed.
310 public:
311 PinnedChannelUse() = default;
312 explicit PinnedChannelUse(const PinnedChannels &rule) : rule(&rule) {}
313 // Adds (`sign` 1) or removes (-1) `end` at `at`. Returns `sign` when the
314 // end takes or frees its channel there, 0 when other ends hold it too.
315 int place(TileID at, const PinnedChannels::End &end, int sign);
316 // The channels at `at` holding two ends that cannot share them, or
317 // claimed by two tile ops.
318 int clashes(TileID at) const;
319 // The (input, output) channels of one tile op's `ends` that `at` already
320 // holds; nothing when one of them clashes there.
321 std::optional<std::pair<int, int>>
322 heldAt(TileID at, llvm::ArrayRef<PinnedChannels::End> ends) const;
323 // An end at `at` that `end` cannot share its channel with, if any.
324 std::optional<PinnedChannels::End>
325 clashWith(TileID at, const PinnedChannels::End &end) const;
326 // The sending ends at `at`, by the MM2S channel they pin.
327 llvm::DenseMap<int, llvm::SmallVector<PinnedChannels::End, 2>>
328 sendingAt(TileID at) const;
329 // Adds (`sign` 1) or removes (-1) `claim` at `at`. A claimed channel is
330 // held from every pinned end there but those sharesClaim() lets share it.
332 int sign);
333 // The claim at `at` that holds `end`'s channel from it, if any.
334 std::optional<DMAChannelAnalysis::ChannelClaim>
335 claimWith(TileID at, const PinnedChannels::End &end) const;
336 // The channels ends at `at` pin in one direction.
337 llvm::SmallVector<int> channelsAt(TileID at, bool sends) const;
338
339 private:
340 const PinnedChannels *rule = nullptr;
341 std::map<std::tuple<int, int, int, int>,
342 llvm::SmallVector<PinnedChannels::End, 2>>
343 placed;
344 std::map<std::tuple<int, int, int, int>,
345 llvm::SmallVector<DMAChannelAnalysis::ChannelClaim, 1>>
346 claimed;
347 };
348
349 // The gates objectFIFO allocation will share receiving shim ends by: the
350 // #aie.consumed_by proofs aie-objectfifo-verify finds on a copy of the
351 // design with every fifo between two tiles moved by DMA. Placing a fifo on
352 // shared memory instead keeps every proof the DMA-moved copy has, so these
353 // never promise a turn allocation refuses. Empty when the copy does not
354 // verify.
355 static llvm::DenseMap<mlir::StringAttr,
356 llvm::SmallVector<ShimTransferSpans::Gate>>
357 provenShimGates(DeviceOp device);
358
359 // The BD ids a shim tile's DMAs take, as aie-assign-bd-ids and
360 // aie-assign-runtime-sequence-bd-ids hand them out: static BDs around the ids
361 // runtime tasks and copies pin; each sequence's tasks their pinned ids, then
362 // the lowest free (head aligned, descriptors split as
363 // aie-decompose-large-dma-bd splits them), held from configure to the first
364 // await or free; a copy holds its id to the sequence's end. Reclaim,
365 // restarts, already-taken tokens, ids a copy forbids, BD chains and aiex.run
366 // callees are not followed, so the count can err either way and the pass
367 // checks exactly. Placed shims count where they sit.
369 public:
370 // The most ids a shim's DMAs hold at once on a tile of their own, and
371 // whether any pins an id or aligns its head.
372 struct Peak {
373 int live = 0;
374 bool constrained = false;
375 };
376 RuntimeBdIds() = default;
377 RuntimeBdIds(DeviceOp device, const AIETargetModel &targetModel);
378
379 bool uses(mlir::Operation *logicalTile) const {
380 return peaks.contains(logicalTile);
381 }
382 const llvm::DenseMap<mlir::Operation *, Peak> &users() const {
383 return peaks;
384 }
385
386 // The ids the DMAs of `onTile` and of the shim already placed at `tile`
387 // cannot get when they share it.
388 int shortfall(llvm::ArrayRef<mlir::Operation *> onTile, TileID tile) const;
389
390 private:
391 struct Task {
392 mlir::Operation *owner;
393 // One entry per descriptor after the split: its pinned id, if any.
394 llvm::SmallVector<std::optional<uint32_t>> bdIds;
395 uint32_t headAlignment;
396 // An aiex.npu.dma_memcpy_nd: its one id stays held to the end of the
397 // sequence.
398 bool copy = false;
399 };
400 struct StaticBds {
401 llvm::SmallVector<uint32_t> pinned;
402 int unpinned = 0;
403 };
404 llvm::SmallVector<Task> tasks;
405 // Per runtime sequence, (task, configured or released) in program order.
406 llvm::SmallVector<llvm::SmallVector<std::pair<unsigned, bool>>> sequences;
407 llvm::DenseMap<mlir::Operation *, StaticBds> statics;
408 llvm::DenseMap<mlir::Operation *, Peak> peaks;
409 llvm::DenseMap<TileID, mlir::Operation *> placed;
410 const AIETargetModel *targetModel = nullptr;
411 // Each shim in `peaks` by index: its tasks, and per sequence the places
412 // of its events, so a shortfall replays only the shims sharing a tile.
413 struct Shim {
414 mlir::Operation *op;
415 llvm::SmallVector<unsigned> tasks;
416 llvm::SmallVector<llvm::SmallVector<unsigned>> events;
417 };
418 llvm::SmallVector<Shim> shims;
419 llvm::DenseMap<mlir::Operation *, unsigned> indexOf;
420 // Every shim tile lays out its BD ids alike, so the answer depends only on
421 // which shims share one.
422 mutable llvm::DenseMap<llvm::SmallBitVector, int> shortfallOf;
423 };
424
425protected:
426 // DMAChannelAnalysis::getChannelClaims(), grouped by the tile op owning
427 // each: the channels its claims take by index hold them from pinned ends
428 // placed with it.
429 llvm::DenseMap<mlir::Operation *,
430 llvm::SmallVector<DMAChannelAnalysis::ChannelClaim>>
432 // Shim channels count one per end until a shim tile runs out; then ends
433 // never in flight together count once, as allocation will share them.
434 std::optional<ShimTransferSpans> shimSpans;
436 // A shim tile is also charged for the runtime BD ids its tile ops' tasks
437 // lack.
439 // The DDR traffic of shim tile ops' ends, one group per runtime sequence
440 // and direction: each end's tile op, its share of the bytes the group
441 // moves (all alike when any end's are dynamic), and which pairs may be in
442 // flight together (not ShimTransferSpans::apart).
443 struct DdrGroup {
444 llvm::SmallVector<mlir::Operation *> tiles;
445 llvm::SmallVector<int64_t> weights;
446 llvm::SmallVector<llvm::BitVector> together;
447 };
448 llvm::SmallVector<DdrGroup> ddrGroups;
449 // The ddrGroups indices holding each tile op.
450 llvm::DenseMap<mlir::Operation *, llvm::SmallVector<unsigned>> ddrGroupsOf;
452 // How unevenly the groups load the shim columns where `columnOf` puts tile
453 // ops, `weight` per group spread worst: 0 when every group's load is even
454 // across as many columns as it has ends, up to the device's.
455 int64_t
456 ddrSpread(llvm::function_ref<std::optional<int>(mlir::Operation *)> columnOf,
457 int weight) const;
458 // ddrSpread's term for one group.
459 int64_t ddrGroupSpread(
460 const DdrGroup &group,
461 llvm::function_ref<std::optional<int>(mlir::Operation *)> columnOf,
462 int weight) const;
463 // Builds the members above and overlayUses for `device`, whose channel
464 // claims are `claims`; `rank` and `routeKeys` as collectShareableShimEnds
465 // takes them.
466 void buildShimModel(DeviceOp device,
467 llvm::ArrayRef<ObjectFifoCreateOp> objectFifos,
468 llvm::ArrayRef<DMAChannelAnalysis::ChannelClaim> claims,
469 const llvm::DenseMap<mlir::Operation *, unsigned> &rank,
470 const llvm::DenseMap<mlir::Operation *, mlir::Operation *>
471 &routeKeys = {});
472
473 // Whether the control overlay takes an MM2S channel on `tile`.
474 bool overlayChannels(TileID tile) const {
475 return controlOverlay && targetModel->isShimNOCTile(tile.col, tile.row);
476 }
477 // The control overlay's MM2S channel on shim tile `at`, as
478 // aie-generate-column-control-overlay picks it: channel 0, or, with
479 // `adaptiveOverlay`, whichever channel no circuit-switched end pins and
480 // overlayUses finds no circuit on for the tile ops at `at` (`tilesHere`),
481 // preferring the one with fewest packet-switched ends. Pinned ends on that
482 // channel share it with the overlay when ShimTransferSpans proves each is
483 // apart from it; otherwise allocation refuses those pins, and the overlay
484 // does not `fit`. `extra` is a tile op's pinned ends about to join `pins`.
485 struct OverlayFit {
486 bool fits = true;
487 // The MM2S channels it adds: none on a pinned channel it shares.
488 int channels = 0;
489 // Whether it holds a channel of its own, which unpinned ends may share.
490 bool own = false;
491 };
493 llvm::ArrayRef<PinnedChannels::End> extra,
494 llvm::ArrayRef<mlir::Operation *> tilesHere,
495 const ShimTransferSpans *spans) const;
496 // The shim MM2S channels each tile op's ends name, as the overlay's pass
497 // weighs them: `device`'s, and those of the other devices the overlay
498 // serves (its target's), at the tiles they sit on now.
500 void collectOverlayUses(DeviceOp device);
501 llvm::SmallVector<mlir::Operation *> overlayTileOps() const;
502
503 // North/South streams of each tile's ObjectFifos: a memtile has 6
504 // DMA inputs but only 4 streams from the core above, and no East/West.
505 llvm::DenseMap<mlir::Operation *, StreamDemand> streamDemand;
506 // Broadcast consumers in one column share a single incoming stream.
507 llvm::DenseMap<mlir::Operation *, llvm::SmallVector<mlir::Operation *>>
509 // Extra broadcast destinations beyond the first, which uses one DMA channel.
510 llvm::DenseMap<mlir::Operation *, int> broadcastFanout;
511 void buildStreamDemand(llvm::ArrayRef<ObjectFifoCreateOp> objectFifos);
512
513 // A stream routing will need, from one tile op to others. Consumers of an
514 // objectFIFO that share memory with its producer
515 // (ObjectFifoCreateOp::sharedMemoryOf, through its allocate's delegate and
516 // its link's tile) take none of it.
517 struct StreamNet {
518 mlir::Operation *src;
519 llvm::SmallVector<mlir::Operation *, 2> dsts;
520 bool packet;
521 // An objectFIFO dmaReason() leaves to sharedMemoryOf.
522 bool mayShare = false;
523 mlir::Operation *delegate = nullptr;
524 mlir::Operation *link = nullptr;
525 };
526 llvm::SmallVector<StreamNet> streamNets;
527 // The nets each tile op is an end, delegate or link tile of.
528 llvm::DenseMap<mlir::Operation *, llvm::SmallVector<unsigned>> streamNetsOf;
529 void buildStreamNets(DeviceOp device, const CollectedOps &collected);
530 // The stream `net` routes where `at` puts tile ops, into `src` and `dsts`;
531 // false while an end is unplaced, or when no consumer takes a stream.
532 bool streamOf(const StreamNet &net,
533 llvm::function_ref<std::optional<TileID>(mlir::Operation *)> at,
534 TileID &src, llvm::SmallVectorImpl<TileID> &dsts) const;
535
536 // flowChannelDemand's `named`, by tile op.
537 llvm::DenseMap<mlir::Operation *, llvm::SmallVector<std::pair<int, int>>>
539 // A tile op among `others` naming a channel `tile` names too, with that
540 // channel. Two such tile ops cannot share a physical tile: their programs
541 // or flows would drive one channel.
542 std::optional<std::pair<mlir::Operation *, std::pair<int, int>>>
543 namedClash(mlir::Operation *tile,
544 llvm::ArrayRef<mlir::Operation *> others) const;
545 // Reports that `tile` can take no tile of its type, because the one at
546 // `at` with room for it holds `clash`, a tile op naming a channel it names.
547 mlir::LogicalResult
548 emitNamedClash(mlir::Operation *tile, TileID at,
549 std::pair<mlir::Operation *, std::pair<int, int>> clash) const;
550
551 llvm::DenseMap<mlir::Operation *, unsigned> coreKeys;
552 llvm::SmallVector<llvm::DenseMap<TileID, unsigned>> neighbourCores;
553
555 llvm::SmallVector<AllocateInfo> allocates;
556 const AIETargetModel *targetModel = nullptr;
557 bool controlOverlay = false;
558 bool adaptiveOverlay = true;
559 // Routes asking for no packet header carry one (packet-sw-objFifos).
560 bool packetSwitched = false;
562};
563
564// Invoke `fn(peer, thisIsFirst)` for each edge in `adjacency` that
565// mentions `op`. `peer` is the OTHER endpoint of the edge; `thisIsFirst`
566// is true when `op` is `edge.first`.
567template <typename F>
568inline void forEachPeer(mlir::Operation *op, const Placer::Adjacency &adjacency,
569 F &&fn) {
570 auto it = adjacency.tileToEdges.find(op);
571 if (it == adjacency.tileToEdges.end())
572 return;
573 for (unsigned idx : it->second) {
574 auto [first, second] = adjacency.edges[idx];
575 bool thisIsFirst = first.getOperation() == op;
576 TileLike peer = thisIsFirst ? second : first;
577 fn(peer, thisIsFirst);
578 }
579}
580
581// Whether two compute tiles can share one memory module: unlike buffer
582// ownership (where only the consumer must reach the owner's module),
583// sharing has no owner/consumer asymmetry, so either tile reaching the
584// other's module is enough. isLegalMemAffinity itself is directional (see
585// AIETargetModel::getSharedMemory's None/First/Second/Either), so compute-
586// peer neighbor-ness -- what `--aie-objectfifo-split`'s auto transport
587// actually tests -- has to check both.
588inline bool isSharedComputeMemory(const AIETargetModel &targetModel, TileID a,
589 TileID b) {
590 return targetModel.isLegalMemAffinity(a.col, a.row, b.col, b.row) ||
591 targetModel.isLegalMemAffinity(b.col, b.row, a.col, a.row);
592}
593
594// Invoke `fn(TileID)` on every other CoreTile that can share compute-peer
595// memory with `at` per the target model.
596template <typename F>
597inline void forEachMemAffinityNeighbor(const AIETargetModel &targetModel,
598 TileID at, F &&fn) {
599 for (int col = 0; col < targetModel.columns(); ++col)
600 for (int row = 0; row < targetModel.rows(); ++row)
601 if (TileID other{col, row};
602 other != at &&
603 targetModel.getTileType(col, row) == AIETileType::CoreTile &&
604 isSharedComputeMemory(targetModel, at, other))
605 fn(other);
606}
607
608// Sequential placement algorithm
609//
610// Greedy, single-pass placer that maps each `aie.logical_tile` (LTO) to a
611// physical (col, row). Four phases:
612//
613// 1. Collect LogicalTileOp / ObjectFifo* / Cascade* / Flow* / PacketFlow* /
614// Route from the device.
615// 2. Build per-LTO constraints: buffer/cascade/compute-peer adjacencies,
616// channel requirements, and needNeighborIn/Out (the minimum number of
617// compute peers per LTO that MUST land on a shared-L1 neighbor to fit
618// the per-tile DMA budget). Group the compute LTOs by the non-core
619// tile each shares the most flows with (buildCoreGroups).
620// 3. Place compute tiles. Make each core group contiguous, then sort by
621// constraint level (pinned -> partial -> unpinned) and by descending
622// placementPriority. For each LTO: validate buffer/cascade/compute-peer
623// constraints and channel budget, then claim the tile, trying first
624// the columns that keep its group together. Unpinned candidates are
625// tried in two passes: first the slots with column stream capacity and
626// not soft-reserved for another demand-bearing LTO's peers, then a
627// fallback accepting overloaded columns and reserved slots. Placing a
628// demand-bearing LTO soft-reserves its mem-affinity neighbor slots for
629// that LTO's compute peers.
630// 4. Place each remaining non-core (mem/shim) LTO near the column
631// centroid of its placed-core peers. With mergeLogicalTiles == true
632// (default) several non-core LTOs may share one physical tile when
633// DMA capacity allows, preferring tiles whose North/South stream ports
634// and runtime-sequence BDs also fit; with mergeLogicalTiles == false
635// each non-core LTO claims its own physical tile.
636//
637// Greedy: once a tile is chosen the decision is final, with no backtracking.
638// If a later LTO's constraints become unsatisfiable given prior placements,
639// the placer emits an error pointing at the LTOs the user can manually pin
640// to break the deadlock.
641//
642// Compute-to-compute ObjectFifos consume no DMA channel when their endpoints
643// land on shared-L1 neighbor tiles, so they enter the placer as a separate
644// compute-peer adjacency rather than as channel demand.
645class SequentialPlacer : public Placer {
646public:
647 SequentialPlacer(std::optional<int> coresPerCol = std::nullopt,
648 bool mergeLogicalTiles = true,
649 bool spreadUnanchoredTiles = false)
650 : coresPerCol(coresPerCol), mergeLogicalTiles(mergeLogicalTiles),
651 spreadUnanchoredTiles(spreadUnanchoredTiles) {}
652
653 void initialize(DeviceOp device, bool controlOverlay, bool adaptiveOverlay,
654 bool packetSwitched) override;
655
656 mlir::LogicalResult place(DeviceOp device) override;
657
658 llvm::StringRef getName() const override { return "sequential_placer"; }
659
660private:
661 std::optional<int> coresPerCol;
662 bool mergeLogicalTiles;
663 // When a non-core LTO has no CoreTile peers, rank candidates by DMA load
664 // instead of by distance to column 0. See placeNonCoreTileByCentroid.
665 bool spreadUnanchoredTiles;
666 // Physical tiles already assigned to a non-core aie.logical_tile. Used
667 // only when mergeLogicalTiles == false to forbid mapping a second
668 // non-core aie.logical_tile onto a tile that already hosts one.
669 llvm::DenseSet<TileID> assignedNonCoreTiles;
670 int deviceCoresPerCol = 0; // Actual cores per column in device
671 // The compute tiles cores-per-col leaves to unpinned logical cores.
672 int placeableCores = 0;
673
674 llvm::DenseMap<TileID, llvm::SmallVector<mlir::Operation *>> shimTilesAt;
675 // The tile ops placed at each position, whose overlayUses count there.
676 llvm::DenseMap<TileID, llvm::SmallVector<mlir::Operation *>> overlayTilesAt;
677 bool fitsSharingShim(TileID tile, mlir::Operation *logicalTile,
678 std::pair<int, int> required);
679 void recordShimEnds(TileID tile, mlir::Operation *logicalTile);
680
681 // Counts once in `requirements` each group of fifos between a core and one
682 // mem tile that allocation's planTurnSharing will put on one channel.
683 void countTurns(
684 DeviceOp device, llvm::ArrayRef<ObjectFifoCreateOp> objectFifos,
685 llvm::DenseMap<mlir::Operation *, std::pair<int, int>> &requirements);
686
687 // DMA channel direction selector.
688 enum class DmaDir { In, Out };
689
690 // Whether an LTO's placement was pinned by the user (via col/row
691 // attributes) or chosen by the placer.
692 enum class PlacementOrigin { Pinned, Selected };
693
694 /// Keeps at most `maxCoresPerCol` cores in each column, counting the
695 /// `held` positions a physical or pinned core already takes.
696 void limitCoresPerColumn(int maxCoresPerCol, int numColumns,
697 const llvm::DenseSet<TileID> &held);
698
699 // targetCol == nullopt means no routing anchor is known, so candidates are
700 // ranked by DMA load rather than by distance to a column. `withinBudgets`
701 // also requires fitsStreamAndBdBudgets; `apartByName` requires that no
702 // tile op there names a channel `logicalTile` names (namedClash).
703 std::optional<TileID>
704 findTileWithCapacity(std::optional<int> targetCol,
705 llvm::ArrayRef<TileID> tiles, int requiredInputChannels,
706 int requiredOutputChannels, AIETileType requestedType,
707 mlir::Operation *logicalTile, bool withinBudgets,
708 bool apartByName = true);
709
710 // Diagnosis for a failed findTileWithCapacity() call. `findTileWithCapacity`
711 // scans every tile of `requestedType` on the device -- `targetCol` orders
712 // candidates, it does not exclude any -- so a failure is either (a) no
713 // tile of this type has the requested channels free ANYWHERE (device-wide
714 // DMA exhaustion: pinning a column cannot create capacity), or (b) at
715 // least one tile has them free but is already claimed by a different
716 // non-core logical tile (only possible under merge-logical-tiles=false).
717 // `capacityExistsSomewhere` selects between the two; the totals let the
718 // caller report the real budget instead of guessing at it.
719 struct CapacityDiagnosis {
720 bool capacityExistsSomewhere = false;
721 int tilesOfType = 0;
722 int inUsed = 0, inMax = 0, outUsed = 0, outMax = 0;
723 // Both shortfalls belong to one tile, minimizing their sum.
724 int closestShortIn = 0, closestShortOut = 0;
725 // Of outUsed, the control overlay's channels; and the tiles where it has
726 // none it can take.
727 int overlayOut = 0, overlayUnfit = 0;
728 // The tiles where a pinned end of the joining tile clashes with one
729 // already there, and the first such pair.
730 int clashTiles = 0;
731 std::optional<std::tuple<TileID, PinnedChannels::End, PinnedChannels::End>>
732 clash;
733 };
734 // `joining` is the logical tile that found no tile, whose pinned ends move
735 // the control overlay.
736 CapacityDiagnosis diagnoseCapacityExhaustion(AIETileType requestedType,
737 int requiredInputChannels,
738 int requiredOutputChannels,
739 mlir::Operation *joining);
740
741 void updateChannelUsage(TileID tile, DmaDir direction, int numChannels);
742
743 // Aggregate traffic between a column's cores and the tiles below them.
744 llvm::DenseMap<int, StreamDemand> columnStreamsUsed;
745 llvm::DenseMap<int, llvm::DenseSet<mlir::Operation *>> columnIncomingFifos;
746 void recordColumnStreamUsage(mlir::Operation *tile, int col);
747 llvm::DenseMap<TileID, int> broadcastFanoutUsed;
748 // The cuts of the stream nets whose ends are all placed, and which those
749 // are.
750 StreamCuts placedCuts;
751 llvm::BitVector cutNets;
752 // Whether placing `logicalTile` at `tile` leaves the boundaries shorter of
753 // channels than they are.
754 bool raisesStreamCuts(mlir::Operation *logicalTile, TileID tile) const;
755 // Adds the stream nets `logicalTile`, now placed, completes.
756 void addPlacedStreams(mlir::Operation *logicalTile);
757
758 // Pinned objectFIFO ends: the rule, their positions, and each tile op's own.
759 PinnedChannels pinnedRule;
760 PinnedChannelUse pinsAt;
761 llvm::DenseMap<mlir::Operation *, llvm::SmallVector<PinnedChannels::End>>
762 pinnedEnds;
763
764 // True if `tile`'s stream ports and BDs still fit `logicalTile`'s demand on
765 // top of what earlier placements use.
766 bool fitsStreamAndBdBudgets(mlir::Operation *logicalTile, TileID tile) const;
767 // Records the streams, BDs and named DMA channels `logicalTile` takes on
768 // `tile`.
769 void recordStreamAndBdUsage(mlir::Operation *logicalTile, TileID tile);
770
771 // `joining` is the logical tile being placed on `tile`: its pinned ends and
772 // named channels count there, as does its own use of the control overlay.
773 bool hasAvailableChannels(TileID tile, int inputChannels, int outputChannels,
774 mlir::Operation *joining = nullptr);
775 OverlayFit overlayWith(TileID tile, mlir::Operation *joining);
776
777 // Notes on `diag` the first pinned end of `logicalTile` that clashes at
778 // `at` and what it clashes with.
779 void notePinClash(mlir::InFlightDiagnostic &diag, LogicalTileOp logicalTile,
780 TileID at);
781
782 mlir::LogicalResult validateAndUpdateChannelUsage(
783 LogicalTileOp logicalTile, TileID tile,
784 const llvm::DenseMap<mlir::Operation *, std::pair<int, int>>
785 &channelRequirements,
786 PlacementOrigin origin);
787
788 llvm::DenseMap<mlir::Operation *, std::pair<int, int>>
789 buildChannelRequirements(
790 llvm::SmallVector<ObjectFifoCreateOp> &objectFifos,
791 llvm::SmallVector<ObjectFifoLinkOp> &objectFifoLinks,
792 const llvm::DenseMap<mlir::Operation *, unsigned> &rank);
793
794 // Per-place() neighbor-demand maps and soft-reservation table.
795 struct PlacementContext {
796 const AIETargetModel &targetModel;
797 const Adjacency &computePeerAdjacency;
798 const llvm::DenseMap<mlir::Operation *, int> &needNeighborIn;
799 const llvm::DenseMap<mlir::Operation *, int> &needNeighborOut;
800 // Mutable: each placement of an LTO with neighbor demand reserves
801 // its mem-affinity neighbor slots for that LTO's compute peers.
802 llvm::DenseMap<TileID, llvm::SmallVector<mlir::Operation *, 2>>
803 reservedFor{};
804
805 int neighborDemand(mlir::Operation *op) const {
806 return needNeighborIn.lookup(op) + needNeighborOut.lookup(op);
807 }
808 // Priority = max(self demand, highest peer demand). A peer of a
809 // high-fanin Worker rises to the front of the sort so its neighbor
810 // slots aren't consumed by unrelated LTOs.
811 int placementPriority(mlir::Operation *op) const;
812 // Soft-reserve `at`'s mem-affinity compute-tile neighbors for
813 // `placedOp`'s peers, if `placedOp` has non-zero neighbor demand.
814 void reserveNeighborSlots(mlir::Operation *placedOp, TileID at);
815 // True if `candidate` is reserved by any LTO that is NOT a compute
816 // peer of `lto` (i.e. would compete for the slot).
817 bool isReservedForOther(mlir::Operation *lto, TileID candidate) const;
818 };
819
820 // A pairwise-legality adjacency constraint (buffer, cascade, ...)
821 // bundled with everything the placer needs to check it and report a
822 // useful diagnostic when it fails: the edge set, the predicate, the
823 // peer-role label for notes, the short name for the error message,
824 // and the educational hint text appended after the peer notes.
825 struct AdjacencyKind {
826 const Adjacency &adjacency;
827 llvm::function_ref<bool(TileID firstPos, TileID secondPos)> pred;
828 llvm::function_ref<llvm::StringRef(bool thisIsFirst)> peerLabel;
829 llvm::StringRef name; // e.g. "shared-L1 buffer", "cascade"
830 llvm::StringRef constraintHint; // appended as a final attachNote
831 };
832
833 // Check `logicalTile` at `tile` against `kind`'s adjacency. On
834 // failure, emit a fully-formed diagnostic (error + peer notes +
835 // constraint hint) and return failure.
836 mlir::LogicalResult enforceAdjacency(LogicalTileOp logicalTile, TileID tile,
837 const AdjacencyKind &kind);
838
839 // Record that `logicalTile` is placed at `tile`. For CoreTile LTOs
840 // this also removes the tile from availability and asks `ctx` to
841 // soft-reserve the tile's mem-affinity neighbor slots for the LTO's
842 // compute peers. `debugLabel` ("pinned" / "unconstrained") names the
843 // placement path in the LLVM_DEBUG trace.
844 void recordPlacement(LogicalTileOp logicalTile, TileID tile,
845 PlacementContext &ctx, llvm::StringRef debugLabel);
846
847 // Per-call inputs for `findUnconstrainedCoreCandidate`. Bundles the
848 // adjacency + demand state that Phase 3 builds for each candidate
849 // filter.
850 struct UnpinnedPlacementInputs {
851 const Adjacency &bufferAdjacency;
852 llvm::function_ref<bool(TileID, TileID)> bufferPred;
853 const Adjacency &cascadeAdjacency;
854 llvm::function_ref<bool(TileID, TileID)> cascadePred;
855 const Adjacency &sharedMemAdjacency;
856 llvm::function_ref<bool(TileID, TileID)> sharedMemPred;
857 const Adjacency &computePeerAdjacency;
858 const llvm::DenseMap<mlir::Operation *, int> &needNeighborIn;
859 const llvm::DenseMap<mlir::Operation *, int> &needNeighborOut;
860 llvm::function_ref<bool(mlir::Operation *, TileID)> isReservedForOther;
861 // Columns to try first, in order, to keep the LTO with its core group
862 // (see buildCoreGroups). Ignored for LTOs with neighbor demand.
863 llvm::ArrayRef<int> preferredCols;
864 };
865
866 // Outputs of `findUnconstrainedCoreCandidate`. `placement` is set on
867 // success; on failure the three boolean flags describe which filter
868 // rejected the most candidates so place() can construct an actionable
869 // diagnostic.
870 struct UnpinnedSearchResult {
871 std::optional<TileID> placement;
872 bool sawConstraintMatch = false;
873 bool allConstraintMatchesFailedAdjacency = true;
874 bool computePeerWasCause = false;
875 // The first candidate passing every other check where a pin of the LTO
876 // clashes with one placed there.
877 std::optional<TileID> pinClash;
878 };
879
880 // Two-pass candidate search for an unpinned (or partially-pinned)
881 // CoreTile LTO. First pass prefers candidates that aren't
882 // soft-reserved by an unrelated demand-bearing LTO's peers; second
883 // pass falls back to reserved candidates. Each candidate is filtered
884 // by buffer adjacency, cascade adjacency, the compute-peer DMA
885 // budget and the LTO's pinned channels. Does not mutate placer state.
886 UnpinnedSearchResult findUnconstrainedCoreCandidate(
887 LogicalTileOp logicalTile, std::optional<int> col, std::optional<int> row,
888 const UnpinnedPlacementInputs &inputs, llvm::ArrayRef<TileID> candidates,
889 llvm::ArrayRef<TileID> pastBudget);
890
891 // Edge: (consumer LTO, owner tile). Predicate: `isLegalMemAffinity`.
892 // SequentialPlacer-only: walks CoreOps and BufferOps, and takes each end of
893 // an allocated fifo as a consumer of its delegate tile.
895 buildBufferAdjacency(llvm::ArrayRef<LogicalTileOp> logicalTiles,
896 llvm::ArrayRef<ObjectFifoAllocateOp> allocates);
897
898 // Per-LTO peer-Value lists, one list per flow that mentions the LTO.
899 // Built once and shared so each centroid lookup is O(#flows on the LTO).
900 struct FlowMembership {
901 llvm::DenseMap<mlir::Value,
902 llvm::SmallVector<llvm::SmallVector<mlir::Value>>>
903 ltoFlows;
904 };
905
906 // Phase 4 driver: for every still-unplaced non-core LTO, place it near
907 // the centroid column of its core peers, iterating non-core LTOs in
908 // descending channel-demand order so the heaviest consumers get first
909 // pick of physical tiles.
910 mlir::LogicalResult placeNonCoreLogicalTiles(
911 llvm::ArrayRef<LogicalTileOp> logicalTiles,
912 const FlowMembership &flowIndex,
913 const llvm::DenseMap<mlir::Operation *, std::pair<int, int>>
914 &channelRequirements);
915
916 // Core LTOs grouped by the non-core LTO each shares the most flows with
917 // (its hub), members in program order. A core with no non-core peer is a
918 // group of its own. Placing a group in one column lets the hub's
919 // centroid land on that column.
920 struct CoreGroups {
921 llvm::DenseMap<mlir::Operation *, unsigned> groupOf;
922 llvm::SmallVector<llvm::SmallVector<LogicalTileOp>> members;
923 };
924
925 CoreGroups buildCoreGroups(llvm::ArrayRef<LogicalTileOp> logicalTiles,
926 const FlowMembership &flowIndex) const;
927
928 // Columns to try first for `logicalTile`: those already holding members
929 // of its group, most members first; for a group's first member, the
930 // columns with a free core for every member, in column order. Empty
931 // means no preference.
932 llvm::SmallVector<int> preferredGroupColumns(LogicalTileOp logicalTile,
933 const CoreGroups &groups) const;
934
935 FlowMembership
936 buildFlowMembership(llvm::ArrayRef<FlowOp> flows,
937 llvm::ArrayRef<PacketFlowOp> pktFlows,
938 llvm::ArrayRef<RouteOp> routes,
939 llvm::ArrayRef<ObjectFifoCreateOp> objectFifos);
940
941 // Pick the column that minimizes total routing cost across the LTO's
942 // flows. See AIEPlacer.cpp for the per-flow cost formulas and tiebreak.
943 // Returns nullopt when the LTO has no CoreTile peer to measure against.
944 std::optional<int> computeCentroidColumn(LogicalTileOp logicalTile,
945 const FlowMembership &flowIndex);
946
947 mlir::LogicalResult placeNonCoreTileByCentroid(
948 LogicalTileOp logicalTile, const FlowMembership &flowIndex,
949 const llvm::DenseMap<mlir::Operation *, std::pair<int, int>>
950 &channelRequirements);
951
952 // Pairwise legality check. `pred(firstPos, secondPos)` is evaluated for
953 // every edge mentioning `logicalTile`; unplaced peers defer.
954 bool satisfiesAdjacency(
955 LogicalTileOp logicalTile, TileID candidate, const Adjacency &adjacency,
956 llvm::function_ref<bool(TileID firstPos, TileID secondPos)> pred) const;
957
958 // Compute-peer DMA budget check. Returns true if placing `logicalTile` at
959 // `candidate` keeps the compute-peer neighbor demand satisfiable for BOTH
960 // the LTO being placed AND every already-placed compute peer of the LTO.
961 // A compute LTO with peer demand N (N compute-peer fifos must use shared
962 // neighbor memory to fit DMA budget) has slack (totalComputePeers − N): it
963 // can afford at most that many non-neighbor compute peers. The check also
964 // forward-looks: unplaced peers still need a free physical compute-tile
965 // neighbor of `candidate` to land on.
966 bool satisfiesComputePeer(
967 LogicalTileOp logicalTile, TileID candidate,
968 const Adjacency &computePeerAdjacency,
969 const llvm::DenseMap<mlir::Operation *, int> &needNeighborIn,
970 const llvm::DenseMap<mlir::Operation *, int> &needNeighborOut) const;
971
972 // Compute-peer in/out edge counts for `op`, looked up from a prebuilt
973 // `computePeerAdjacency`. Returns {0, 0} if `op` has no entry. Producer
974 // is edges[idx].first, consumer is .second (per buildComputePeerAdjacency).
975 static std::pair<int, int> totalComputePeers(mlir::Operation *op,
976 const Adjacency &adjacency);
977
978 // Diagnostic peer notes. `labelPeer(thisIsFirst)` names the peer endpoint
979 // role; the attached note reads "<label> peer placed at (col, row)".
980 void attachPeerNotes(
981 mlir::InFlightDiagnostic &diag, LogicalTileOp logicalTile,
982 const Adjacency &adjacency,
983 llvm::function_ref<llvm::StringRef(bool thisIsFirst)> labelPeer) const;
984};
985
986// Configuration for the SA placer's cost model and schedule.
987//
988// The SA placer minimizes a total cost with four components:
989//
990// totalCost = HPWL + resourcePenalty + cascadePenalty + memoryPressure
991//
992// 1. HPWL (half-perimeter wire length): sum of bounding-box perimeters
993// across all nets.
994//
995// 2. Resource penalty (hard, blocks legality): penalizes MemTile buffer
996// overflow, core tile overflow, DMA channel overuse, BD count
997// overuse, fifo ends that can't reach their allocate's delegate, and
998// locks LockPlan cannot place at the current positions.
999//
1000// 3. Cascade penalty (hard, blocks legality): penalizes cascade put/get
1001// pairs and shared-memory pairs that aren't adjacent.
1002//
1003// 4. Memory pressure (soft, guides optimization): quadratic penalty when
1004// tile utilization exceeds a threshold.
1005struct SAConfig {
1006 // HPWL (cost 1)
1007 int multicastThreshold = 4; // consumer count above which penalty applies
1008 int multicastMultiplier = 2; // HPWL multiplier for multicast nets
1009
1010 // Resource penalty (cost 2)
1011 int memPenaltyPerKB = 30; // per KB of unresolved memory overflow
1012 int dmaPenaltyPerChannel = 20; // per DMA channel or BD over limit
1013 int delegateWeightPerDist = 30; // per distance from an allocate's delegate
1014
1015 // Cascade penalty (cost 3)
1016 int cascadeWeightPerDist = 30; // per Manhattan distance to valid position
1017 // A shared-memory pair apart, per distance past a neighbour: above a
1018 // fifo's worth of memory overflow, which a neighbour's spare room absorbs.
1020
1021 // Memory pressure (cost 4)
1022 int pressurePerKB = 3; // quadratic pressure above threshold
1023 double pressureThreshold = 0.75; // utilization fraction triggering pressure
1024
1025 // Stream demand: per channel a row or column boundary is short of (hard),
1026 // per squared stream past a fraction of its channels (soft), and per
1027 // North/South port over a tile's or a column's (soft).
1030 double streamNearFraction = 0.75;
1032 // Per runtime sequence and direction, its shim ends' DDR traffic spread
1033 // worst over the shim columns (soft): see Placer::ddrSpread.
1034 int ddrWeight = 8;
1035 // Per core program a switch between neighbouring configurations rewrites
1036 // (soft).
1038
1039 // Adaptive cooling
1040 double coolFast = 0.995; // accept ratio > 96%: cool faster
1041 double coolSteady = 0.998; // accept ratio > 80%: steady progress
1042 double coolBalanced = 0.999; // accept ratio > 15%: balanced exploration
1043 double coolStuck = 0.9998; // accept ratio <= 15%: barely cool
1044 double greedyThreshold = 0.005; // switch to greedy (T=0) below this
1045
1046 // Schedule sizing
1049 int minMaxIters = 10000;
1050 int greedyMultiplier = 50; // greedyIters = multiplier * numMovable
1051 double effort = 1.0; // scales movesPerIter and greedyIters
1052 // assign-buffer-addresses' placement-budget, for core tile layouts.
1054 double tempScaleEstimate = 10.0; // initTemp cap: scale * estimated T
1055 double tempScaleCost = 2.0; // initTemp cap: scale * totalCost
1056
1057 // Temperature estimation
1058 int tempSearchIters = 100; // binary search iterations
1059 double tempSearchCeiling = 5.0; // highT = ceiling * maxDelta
1060 double tempSearchEpsilon = 1e-10; // zero guard in binary search
1061 double tempSearchTolerance = 1e-6; // convergence tolerance
1062
1063 // SA loop intervals
1064 int debugInterval = 5000; // iterations between debug log lines
1065 int fullRecomputeInterval = 10000; // iterations between full cost recompute
1066
1067 // Move generation
1068 int maxMoveAttempts = 20; // retries per move before giving up
1069
1070 // Acceptance tracking
1071 int windowSize = 100; // sliding window for acceptance ratio
1072
1073 // ObjectFIFOs whose mem tile pools allocation walked whole.
1074 llvm::SmallVector<std::string> walkedFifos;
1075 // The data region each core keeps for its own sections, by the device's
1076 // core order, where a build measured it, for a core declaring neither
1077 // data_size nor measured_data_size: its bytes and the alignment its
1078 // sections start at.
1082 int64_t bytes;
1083 int64_t alignBytes;
1084 };
1085 llvm::DenseMap<unsigned, CoreDataCharge> coreDataCharges;
1086};
1087
1088// SA temperature schedule with windowed acceptance tracking.
1090public:
1091 SASchedule() = default;
1092 SASchedule(double startTemp, int movesPerIter, int maxIters, int greedyIters,
1093 const SAConfig &cfg = {});
1094
1095 double getTemperature() const { return temperature; }
1096 int getIteration() const { return currIteration; }
1097 int getMovesPerIter() const { return movesPerIter; }
1098 bool isGreedy() const { return inGreedyStage; }
1099 bool limitReached() const;
1100 double getAcceptanceRatio() const;
1101 void record(bool accepted);
1102 void cool();
1103
1104private:
1105 double temperature = 0.0;
1106 int currIteration = 0;
1107 int currGreedyIteration = 0;
1108 int movesPerIter = 100;
1109 int maxIters = 5000;
1110 int greedyIters = 100;
1111 int windowSize = 100;
1112 SAConfig config;
1113 bool inGreedyStage = false;
1114 std::deque<int> history;
1115 int acceptCount = 0;
1116 int rejectCount = 0;
1117
1118 void trimWindow();
1119};
1120
1121// Per-net bounding box state for incremental HPWL updates.
1122// countAt* tracks how many endpoints sit at each extreme so we can avoid
1123// full rescans when an endpoint moves away from a non-unique extreme.
1125 int minCol = 0, maxCol = 0, minRow = 0, maxRow = 0;
1128};
1129
1130struct NetInfo {
1131 llvm::SmallVector<mlir::Operation *> endpoints; // producer + all consumers
1133 bool isMulticast = false; // >4 consumers triggers 2x HPWL penalty
1134};
1135
1136/// A DenseMap that notes what each write through operator[] overwrote, so
1137/// rollback() can restore it as of the last commit().
1138template <typename Key, typename Value>
1140public:
1141 using Map = llvm::DenseMap<Key, Value>;
1142 Value &operator[](const Key &key) {
1143 auto [it, added] = map.try_emplace(key);
1144 saved.emplace_back(key,
1145 added ? std::nullopt : std::optional<Value>(it->second));
1146 return it->second;
1147 }
1148 Value lookup(const Key &key) const { return map.lookup(key); }
1149 typename Map::const_iterator find(const Key &key) const {
1150 return map.find(key);
1151 }
1152 bool contains(const Key &key) const { return map.contains(key); }
1153 typename Map::const_iterator begin() const { return map.begin(); }
1154 typename Map::const_iterator end() const { return map.end(); }
1155 void clear() {
1156 map.clear();
1157 saved.clear();
1158 }
1159 void commit() { saved.clear(); }
1160 void rollback() {
1161 for (auto &[key, old] : llvm::reverse(saved)) {
1162 if (old)
1163 map[key] = std::move(*old);
1164 else
1165 map.erase(key);
1166 }
1167 saved.clear();
1168 }
1169
1170private:
1171 Map map;
1172 llvm::SmallVector<std::pair<Key, std::optional<Value>>> saved;
1173};
1174
1175// Simulated annealing placement algorithm
1176//
1177// Uses HPWL (half-perimeter wire length) cost with incremental bounding-box
1178// updates. Nets are derived from ObjectFifo producer/consumer connectivity.
1179// All tile types (compute, mem, shim) participate in SA moves, and a move can
1180// put two mem/shim logical tiles on the same physical tile directly: the cost
1181// terms (currentMemUsage, currentDMAUsage, ...) charge the shared position,
1182// not a separate merge step.
1183class SAPlacer : public Placer {
1184public:
1185 explicit SAPlacer(unsigned seed = 0, SAConfig config = {})
1186 : rngSeed(seed), config(config) {}
1187
1188 mlir::LogicalResult place(DeviceOp device) override;
1189 llvm::StringRef getName() const override { return "sa_placer"; }
1190 int getFinalCost() const { return finalCost; }
1191 int getFinalLockGroups() const { return finalLockGroups; }
1192 int getFinalLockPenalty() const { return finalLockPenalty; }
1193 bool getFinalLockStopped() const { return finalLockStopped; }
1194
1195 // Whether a fifo end of `type` sits on either shim tile kind: allocation
1196 // moves such an end's objects by DMA rather than pooling them with a mem
1197 // or core tile's.
1198 static bool isShimEndType(std::optional<AIETileType> type) {
1199 return type == AIETileType::ShimNOCTile || type == AIETileType::ShimPLTile;
1200 }
1201
1202private:
1203 // Configuration
1204 unsigned rngSeed;
1205 SAConfig config;
1206 int finalCost = 0;
1207 int finalLockGroups = 0, finalLockPenalty = 0;
1208 bool finalLockStopped = false;
1209 std::mt19937 rng;
1210 SASchedule schedule;
1211
1212 // Collected IR state
1213 CollectedOps collected;
1214 llvm::DenseMap<mlir::Operation *, AIETileType> tileTypes;
1215 llvm::DenseMap<mlir::Operation *, int64_t> staticBufferSizes;
1216 llvm::DenseMap<mlir::Operation *, int64_t> stackSizes;
1217 // Locks the design already places on each logical tile, in the order
1218 // collectOperations ranks the tiles, and on each placed tile; placed tiles
1219 // take lock groups too.
1220 llvm::MapVector<mlir::Operation *, int> fixedLocks;
1221 llvm::DenseMap<TileID, int> placedLocks;
1222 llvm::SmallVector<TileID> placedTiles;
1223 // Each fifo's place among the ones its core first acquires, in the core's
1224 // program order.
1225 llvm::DenseMap<mlir::Operation *, unsigned> firstAcquire;
1226 // The lock groups of pools already in the input, read as
1227 // aie-objectfifo-allocate reads them: each segment without its locks, used
1228 // by the tiles of the endpoints selecting it (a compute tile's DMA reaching
1229 // only its own locks).
1230 struct InputLockGroup {
1231 mlir::Operation *home;
1232 llvm::SmallVector<std::pair<mlir::Operation *, bool>, 2> users;
1233 int locks;
1234 };
1235 llvm::SmallVector<InputLockGroup> inputLockGroups;
1236
1237 // Net model
1238 struct FifoBufferInfo {
1239 mlir::Operation *fifoOp = nullptr;
1240 // Logical ends, null for a physical one.
1241 mlir::Operation *producer = nullptr;
1242 llvm::SmallVector<mlir::Operation *> consumers;
1243 // Every end's tile, physical ones included.
1244 mlir::Operation *producerTile = nullptr;
1245 llvm::SmallVector<mlir::Operation *> consumerTiles;
1246 mlir::Operation *delegate = nullptr;
1247 int64_t producerSizeBytes = 0;
1248 int64_t consumerSizeBytes = 0;
1249 // Each end's object bytes, unaligned, as addressing lays the buffers out.
1250 int64_t producerRawBytes = 0;
1251 int64_t consumerRawBytes = 0;
1252 // ObjectFifoCreateOp::sharedDepth() and dmaDepth() of each end.
1253 int sharedDepth = 0;
1254 int producerDepth = 0;
1255 llvm::SmallVector<int> consumerDepths;
1256 // ObjectFifoCreateOp::plannedDmaEnd of each end, and the index of its
1257 // entry in memTileEnds on a mem tile.
1258 std::optional<PlannedDmaEnd> producerEnd;
1259 llvm::SmallVector<std::optional<PlannedDmaEnd>> consumerEnds;
1260 std::optional<unsigned> producerMemTileEntry;
1261 llvm::SmallVector<std::optional<unsigned>> consumerMemTileEntries;
1262 // Whether an end on a link's tile holds the link's one pool, which the
1263 // split builds from getPoolOwner and getPoolDepth as the plan says, or
1264 // shares one another end holds.
1265 enum class LinkPool { None, Holds, Shares };
1266 LinkPool producerLinkPool = LinkPool::None;
1267 llvm::SmallVector<LinkPool> consumerLinkPools;
1268 std::optional<PlannedDmaEnd> producerLinkPlan;
1269 llvm::SmallVector<std::optional<PlannedDmaEnd>> consumerLinkPlans;
1270 // The channel each end that draws one pins, if it pins one.
1271 std::optional<PinnedChannels::End> producerPin;
1272 llvm::SmallVector<std::optional<PinnedChannels::End>> consumerPins;
1273 // dmaReason(): it moves by DMA wherever its ends sit.
1274 bool forcesDMA = false;
1275 // The tile of the link naming the fifo, if any.
1276 mlir::Operation *linkTile = nullptr;
1277 // With an aie.objectfifo.allocate, ObjectFifoCreateOp's
1278 // allocateFallsBackToDMA() and whether linkPoolMisfit() is None.
1279 bool allocateFallsBackToDMA = false;
1280 bool fitsLinkPool = true;
1281 bool linkSharedProd = false;
1282 // PoolLocks::needsLocks' facts for the pools the split makes, and which
1283 // ends' cores use the fifo.
1284 bool unsynchronized = false;
1285 int64_t initObjects = 0;
1286 bool rearmed = false;
1287 bool producerCore = false;
1288 llvm::SmallVector<bool> consumerCore;
1289 // The lock groups of the link pool an end holds: the link's segments, or
1290 // none when a participant disables synchronization.
1291 int producerLinkSegments = 0;
1292 llvm::SmallVector<int> consumerLinkSegments;
1293 };
1294 llvm::SmallVector<NetInfo> nets;
1295 llvm::DenseMap<mlir::Operation *, llvm::SmallVector<size_t>> tileToNetIndices;
1296 llvm::SmallVector<FifoBufferInfo, 0> fifoBuffers;
1297 // Each fifo's end tile types, where known, as tileTypes gives them.
1298 struct FifoEndTypes {
1299 std::optional<AIETileType> producer;
1300 llvm::SmallVector<std::optional<AIETileType>, 4> consumers;
1301 };
1302 std::vector<FifoEndTypes> fifoEndTypes;
1303
1304 // A route's DMA end on a logical tile: one channel, in or out, that moves
1305 // with the tile.
1306 struct RouteEndInfo {
1307 mlir::Operation *tile;
1308 bool output;
1309 };
1310 llvm::SmallVector<RouteEndInfo> routeEnds;
1311 llvm::DenseMap<mlir::Operation *, llvm::SmallVector<size_t>> tileToRouteEnds;
1312 // The DMA ends of each mem tile, logical or physical, and the BD ids each
1313 // takes, as the split will make them.
1314 struct MemTileEnd {
1315 DMAChannelDir dir;
1316 PlannedDmaEnd end;
1317 };
1318 llvm::MapVector<mlir::Operation *, llvm::SmallVector<MemTileEnd>> memTileEnds;
1319 // A link whose pool's depth follows where tiles sit: a participant other
1320 // than the owner shares the pool through its allocate only where its ends,
1321 // its delegate and the link's tile let it (ObjectFifoLinkOp::getPoolPlan).
1322 // `tiles` are those tiles; `depth` is the pool's depth the participants'
1323 // plans hold now. `holds` are the participants' ends that hold the pool's
1324 // plan. A participant's ends depend on where tiles sit only through link
1325 // pools' depths, so `replans` keeps them, and the pool's plan, by the
1326 // depths every variable link has.
1327 struct VariableLink {
1328 struct Replan {
1329 llvm::SmallVector<llvm::SmallVector<std::optional<PlannedDmaEnd>>> ends;
1330 std::optional<PlannedDmaEnd> held;
1331 };
1332 ObjectFifoLinkOp link;
1333 LinkPoolPlan plan;
1334 int64_t depth;
1335 llvm::SmallVector<mlir::Operation *> tiles;
1336 llvm::SmallVector<size_t> fifos;
1337 llvm::SmallVector<std::pair<size_t, std::optional<unsigned>>> holds;
1338 std::map<std::vector<int64_t>, Replan> replans;
1339 };
1340 llvm::SmallVector<VariableLink, 0> variableLinks;
1341 // The variable links the move being weighed planned again, with their
1342 // depths before and after it.
1343 struct ReplannedLink {
1344 unsigned index;
1345 int64_t from;
1346 int64_t to;
1347 };
1348 llvm::SmallVector<ReplannedLink> replannedLinks;
1349 // The pools of memTileEnds that config.walkedFifos names.
1350 llvm::DenseSet<mlir::Operation *> chargedPools;
1351
1352 // Placement state
1353 llvm::DenseMap<mlir::Operation *, TileID> currentPlacement;
1354 llvm::DenseMap<TileID, mlir::Operation *> physToLogical;
1355 llvm::SmallVector<mlir::Operation *> movableTiles;
1356 llvm::DenseSet<mlir::Operation *> constrainedTiles;
1357
1358 // Resource tracking
1359 llvm::DenseMap<mlir::Operation *, llvm::SmallVector<size_t>>
1360 tileToFifoIndices;
1361 // Every map a move writes is journaled, and a rejected move rolls them
1362 // back (rejectMove).
1363 JournaledMap<TileID, int64_t> currentMemUsage;
1364 // Lock packings the moves repeat, the costliest to search again.
1365 mutable LockPlan::Memo lockMemo{64};
1366 // Every position whose memory a lock user at a position reaches, by
1367 // LockPlan::reaches, in position order and its own included.
1368 llvm::DenseMap<TileID, llvm::SmallVector<TileID>> lockReach;
1369 // The locks each position's pools, lock ops and input pools take, and how
1370 // many positions take more than they hold.
1371 JournaledMap<TileID, int> currentLockDemand;
1372 int positionsOverLocks = 0;
1373 // The locks a tile op's lock ops and input pools take wherever it sits.
1374 llvm::DenseMap<mlir::Operation *, int> homeLocks;
1375 JournaledMap<TileID, std::pair<int, int>> currentDMAUsage;
1376 // The rule pinned ends share channels by, and the pinned ends at each
1377 // position, whose channels count in currentDMAUsage once each. The move's
1378 // changes to pinUse are logged, each undone by its inverse.
1379 PinnedChannels pinnedRule;
1380 PinnedChannelUse pinUse;
1381 llvm::SmallVector<std::tuple<TileID, PinnedChannels::End, int>> pinLog;
1382 llvm::SmallVector<std::tuple<TileID, DMAChannelAnalysis::ChannelClaim, int>>
1383 claimLog;
1384 JournaledMap<size_t, TileID> sharedMemDestination;
1385 int cachedResourcePenalty = 0;
1386 // The resource terms that read only some tiles' positions, kept so a move
1387 // recomputes one only when it moves a tile the term reads.
1388 int memSpilloverPenalty = 0, bdCountPenalty = 0, delegatePenalty = 0;
1389 // What each core tile op holds besides objectFIFO buffers, as
1390 // assign-buffer-addresses lays it out: its aie.buffers and unsplit pools,
1391 // the buffers its core's section reservations become, and the stack.
1392 struct CoreTileContents {
1393 llvm::SmallVector<TileLayoutBuffer> buffers;
1394 bool hasCore = false;
1395 MemoryRun stackRun;
1396 std::optional<int> stackBank;
1397 int64_t stackAlignBytes = 1;
1398 };
1399 llvm::DenseMap<mlir::Operation *, CoreTileContents> coreContents;
1400 // ObjectFIFO buffers by size, and how many of each.
1401 using BufferCounts = llvm::SortedVectorMap<int64_t, int, 4>;
1402 // The objectFIFO buffers on each core tile.
1403 JournaledMap<TileID, BufferCounts> coreFifoBuffers;
1404 // Charges chargeCoreFifo applied in the current move, which tell the
1405 // tiles it changed.
1406 llvm::SmallVector<std::tuple<TileID, int64_t, int>> coreFifoLog;
1407 // coreUnplaced of each core tile.
1408 JournaledMap<TileID, int64_t> coreUnplacedAt;
1409 // The tiles whose ops the current move changed.
1410 llvm::DenseSet<TileID> coreDirty;
1411 // Cached with the tiles it was computed for; see updateResourcePenalty.
1412 int coreOverflowPenalty = 0;
1413 llvm::SmallVector<TileID> coreOverflowTiles;
1414 // coreUnplaced by layout problem, and by tile ops and objectFIFO buffers;
1415 // a result equals a fresh layoutTile.
1416 struct KeyHash {
1417 size_t operator()(const std::vector<int64_t> &key) const {
1418 return llvm::hash_combine_range(key.begin(), key.end());
1419 }
1420 };
1421 mutable std::unordered_map<std::vector<int64_t>, int64_t, KeyHash>
1422 coreUnplacedOf, coreUnplacedByTile;
1423 // computeLockPenalty's penalty, and whether its packing stopped, by all it
1424 // reads; a result equals a fresh one.
1425 mutable std::unordered_map<std::vector<int64_t>, std::pair<int, bool>,
1426 KeyHash>
1427 lockVerdicts;
1428 static constexpr size_t kLockVerdictBytes = 1 << 20;
1429 static constexpr unsigned kLockVerdictMissRun = 4096;
1430 mutable size_t lockVerdictBytes = 0;
1431 mutable unsigned lockVerdictMissRun = 0;
1432 llvm::DenseSet<mlir::Operation *> spillTiles, delegateTermTiles, pairedTiles;
1433 // The buffers each mem tile, logical or physical, already holds, as the
1434 // allocator lays them out.
1435 llvm::MapVector<mlir::Operation *, llvm::SmallVector<BufferAllocation>>
1436 memTileFixed;
1437 // A variable link's depth changes what ends its participants plan there,
1438 // so every cache below that reads a position's ends or buffers also keys
1439 // on every variable link's depth, not the tiles' positions alone.
1440 // The BD ids the mem tile ends at each position are short of.
1441 JournaledMap<TileID, int64_t> bdShortfallAt;
1442 using WalkSets =
1443 llvm::SmallVector<llvm::SmallVector<std::pair<mlir::Operation *, int>>>;
1444 struct BDShortfall {
1445 int64_t ids;
1446 WalkSets sets;
1447 llvm::SmallVector<int64_t> bytes;
1448 };
1449 // The shortfall of each set of logical tiles sharing a position, by its
1450 // BD layout's position, its tiles in order and every variable link's depth.
1451 BoundedMemo<std::vector<uintptr_t>, BDShortfall> bdShortfallOf{1u << 16};
1452 // The bytes the spill search leaves unplaced in one spill component, by its
1453 // tiles' contents and each mem tile's walk set, keyed as bdShortfallOf is.
1454 BoundedMemo<std::vector<uintptr_t>, int64_t> unplacedOf{1u << 16};
1455 // The spill penalty, by where every mem tile's holders sit, keyed as
1456 // bdShortfallOf is.
1457 BoundedMemo<std::vector<int64_t>, int> spillPenaltyOf{1u << 14};
1458 // The device's mem tiles in column-major order, each one's index there, and
1459 // its memTileSpillNeighbours; built once.
1460 llvm::SmallVector<MemTileSpillSearch::Tile> memTiles;
1461 llvm::DenseMap<TileID, unsigned> memTileIndex;
1462 llvm::DenseMap<TileID, llvm::SmallVector<TileID, 2>> spillNeighbours;
1463 // For each mem tile position, the first position seen whose channels reach
1464 // the same BD ids, which the shortfalls are cached under.
1465 llvm::DenseMap<TileID, TileID> bdLayoutOf;
1466 // What aie-objectfifo-allocate plans a tile's BD ids around: the channels
1467 // and ids its own programs and pinned runtime ids already hold.
1468 std::optional<DMAChannelAnalysis> channelAnalysis;
1469 DMAChannelAnalysis::TakenBDs takenBDs;
1470 llvm::DenseMap<TileID, llvm::SmallVector<mlir::Operation *>> physicalTiles;
1471 // Every logical mem tile, objectFIFO ends or not: its programs hold BD ids
1472 // and channels wherever it is placed.
1473 llvm::SmallVector<mlir::Operation *> logicalMemTiles;
1474 int cachedPressure = 0;
1475 // The DMA-channel term, and its part at each tile.
1476 int dmaPenalty = 0;
1477 JournaledMap<TileID, int> dmaPenaltyAt;
1478 // The tile ops overlayUses names, which the overlay's channel weighs where
1479 // they are.
1480 llvm::SmallVector<mlir::Operation *> overlayTiles;
1481 // The streams each row and column boundary carries, and the penalty for
1482 // the channels they are short of.
1483 StreamCuts cuts;
1484 int streamCutPenalty = 0;
1485 // Each stream net's stream as cuts counts it; no destinations for none.
1486 JournaledMap<unsigned, std::pair<TileID, llvm::SmallVector<TileID, 2>>>
1487 netStreams;
1488 // The North/South streams at each position, how many objectFIFOs enter
1489 // each column's cores and the cores each enters there, and the ports those
1490 // overrun.
1491 JournaledMap<TileID, StreamDemand> streamsAt;
1492 JournaledMap<int, int> incomingAt;
1493 JournaledMap<std::pair<int, mlir::Operation *>, int> incomingCount;
1494 int portsOver = 0;
1495 // Placer::ddrSpread where the shim tile ops sit now.
1496 int ddrPenalty = 0;
1497 // Placer::ddrGroupSpread per group, and their sum.
1498 JournaledMap<unsigned, int64_t> ddrScoreOf;
1499 int64_t ddrTotal = 0;
1500 // The program key of the core at each position, and the program writes
1501 // switching to or from the neighbour configurations take.
1502 JournaledMap<TileID, unsigned> keyAt;
1503 int coresChanged = 0;
1504 // Each position's North/South ports, by column then row, and each
1505 // column's lowest core's South inputs.
1506 llvm::SmallVector<StreamDemand> portsAt;
1507 llvm::SmallVector<int> columnSouthPorts;
1508 // Adds (`sign` 1) or removes (-1) the streams of tile op `op` at `at`.
1509 void chargeStreams(mlir::Operation *op, TileID at, int sign);
1510 int portExcess(TileID at) const;
1511 int columnExcess(int col) const;
1512 // The runtime BD-id charge at each shim position.
1513 JournaledMap<TileID, int> runtimeBdAt;
1514
1515 // Cascade
1516 Adjacency cascadeAdjacency;
1517 // Ends of fifos that ask for shared memory, which must share a module.
1518 Adjacency sharedMemAdjacency;
1519
1520 // SA loop state
1521 int totalCost = 0;
1522 int cascadePen = 0;
1523 int bestCost = INT_MAX; // best legal (resPenalty==0 && cascade==0)
1524 int bestOverallCost = INT_MAX; // best regardless of legality (fallback)
1525 PlacementResult bestPlacement; // corresponds to bestCost
1526 PlacementResult bestOverallPlacement; // corresponds to bestOverallCost
1527 int deviceSlots = 0;
1528 int zeroDeltaMoves = 0, posDeltaMoves = 0, negDeltaMoves = 0;
1529 int acceptedUphill = 0, rejectedMoves = 0;
1530 std::chrono::steady_clock::time_point startTime;
1531
1532 // Phase methods
1533 mlir::LogicalResult collectAndBuildModel(DeviceOp device);
1534 mlir::LogicalResult generateInitialPlacement();
1535 void initializeSAState();
1536 void runSAMainLoop();
1537 mlir::LogicalResult finalizePlacement(DeviceOp device);
1538
1539 // Cost and resource methods
1540 void initResourceTracking();
1541 void addFifoContribution(size_t fifoIdx, int sign);
1542 void addRouteEndContribution(size_t endIdx, int sign);
1543 void addLockDemand(TileID pos, int locks);
1544 void drawChannel(TileID position, bool output,
1545 const std::optional<PinnedChannels::End> &pin, int sign);
1546 int updateResourcePenalty(
1547 const llvm::SmallVector<std::pair<mlir::Operation *, TileID>>
1548 &oldPlacements);
1549 int getResourcePenalty() const { return cachedResourcePenalty; }
1550 /// The BD ids the ends of mem tiles `tiles`, at `position`, are short of
1551 /// once aie-objectfifo-allocate has planned their channels; with
1552 /// `walkSets`, DMAChannelAnalysis::walkSetsThatFit's sets (every walkable
1553 /// pool when none fits) and, with `walkBytes`, each one's bytes.
1554 int64_t bdShortfall(TileID position, llvm::ArrayRef<mlir::Operation *> tiles,
1555 WalkSets *walkSets = nullptr,
1556 llvm::SmallVector<int64_t> *walkBytes = nullptr);
1557 /// The mem tiles at `position`, in memTileEnds order.
1558 llvm::SmallVector<mlir::Operation *> memTilesAt(TileID position) const;
1559 // Each penalty term below with a `charged` argument also appends to it the
1560 // positions of the tiles it charges, for finalizePlacement's notes.
1561 int computeMemSpilloverPenalty(
1562 llvm::SmallVectorImpl<TileID> *charged = nullptr);
1563 int computeCoreOverflowPenalty(
1564 llvm::SmallVectorImpl<TileID> *charged = nullptr) const;
1565 /// No-op off a core tile. Logs the charge in coreFifoLog.
1566 void chargeCoreFifo(TileID pos, int64_t bytes, int count);
1567 /// The bytes assign-buffer-addresses' layout (layoutTile) leaves unplaced
1568 /// on the core tile at `pos`, with `added` objectFIFO buffers more and
1569 /// `removed` fewer.
1570 int64_t coreUnplaced(TileID pos, const BufferCounts &added = {},
1571 const BufferCounts &removed = {}) const;
1572 /// Relocates the intratile fifos of the core tile at `pos` to neighbours
1573 /// whose layout still places everything with them and what `lent` already
1574 /// gave them, as generateAllocates' allocates do; records each in `moves`
1575 /// and returns the bytes the tile's layout still leaves unplaced.
1576 int64_t
1577 planCoreFit(TileID pos, llvm::DenseMap<TileID, BufferCounts> &lent,
1578 llvm::SmallVectorImpl<std::pair<size_t, TileID>> *moves) const;
1579 /// Recomputes coreUnplacedAt for the core tiles whose contents changed, and
1580 /// returns them.
1581 llvm::SmallVector<TileID> refreshCoreUnplaced();
1582 /// The overflowing core tiles and their neighbours.
1583 llvm::DenseSet<TileID> coreOverflowReads() const;
1584 /// Fills `dmaPenaltyAt` and returns its sum.
1585 int computeDMAChannelPenalty();
1586 /// With `bdIds`, sets it to the part a shim tile's runtime BD ids take.
1587 int computeTileDMAPenalty(TileID tilePos, int *bdIds = nullptr) const;
1588 /// Charges `pos` for the runtime BD ids the shims there lack, in
1589 /// runtimeBdAt.
1590 void chargeRuntimeBds(TileID pos);
1591 /// Fills `bdShortfallAt` and returns the penalty it gives.
1592 int computeBDCountPenalty();
1593 int computeDelegatePenalty(
1594 llvm::SmallVectorImpl<TileID> *charged = nullptr) const;
1595 /// Plans the pools of the links `depths` names for the depths it gives
1596 /// them, and their participants' ends; a link already at its given depth
1597 /// keeps its plans. Every other variable link's tiles must not have moved
1598 /// since its last plan.
1599 void replanLinks(llvm::ArrayRef<std::pair<unsigned, int64_t>> depths);
1600 /// Charges each lock LockPlan cannot place at the current positions (see
1601 /// lockGroups). Sets `stopped`, when given, to whether its search stopped.
1602 int computeLockPenalty(
1603 bool *stopped = nullptr,
1604 llvm::SmallVectorImpl<TileID> *charged = nullptr) const;
1605 /// The lock groups aie-objectfifo-allocate gives the pools the split makes
1606 /// where the tiles sit now: how many locks each takes
1607 /// (LockPlan::groupCounts) and the tiles using them, a compute tile's DMA
1608 /// reaching only its own.
1609 llvm::SmallVector<
1610 std::pair<int, llvm::SmallVector<std::pair<TileID, bool>, 2>>>
1611 lockGroups() const;
1612 std::optional<TileID> positionOf(mlir::Operation *tile) const;
1613 int computeMemoryPressure() const;
1614 // Every soft term but memory pressure, summed.
1615 int computeSoftTerms() const;
1616 // The program writes at `pos` when this configuration and a neighbour
1617 // switch, either way, per keyAt.
1618 int coresChangedAt(TileID pos) const;
1619 int computeAdjacencyPenalty(
1620 const Adjacency &adj, llvm::ArrayRef<std::pair<int, int>> validOffsets,
1621 int weight, llvm::SmallVectorImpl<TileID> *charged = nullptr) const;
1622 /// Cascade neighbours placed apart, and shared-memory ends placed on
1623 /// tiles sharing no memory module, by how far.
1624 int computePairingPenalty(
1625 llvm::SmallVectorImpl<TileID> *charged = nullptr) const;
1626 /// Attaches to `diag` one note per nonzero penalty term: its name, its
1627 /// penalty and the positions it charges, anchored on a tile op at the
1628 /// first.
1629 void explainPenalties(mlir::InFlightDiagnostic &diag);
1630 /// Core tiles over local memory, in position order.
1631 llvm::SmallVector<TileID> overflowingCoreTiles() const;
1632 void generateAllocates();
1633
1634 // Move methods
1635 void tryMove(llvm::SmallVector<std::pair<mlir::Operation *, TileID>> &moves);
1636 /// Starts journaling a move's changes afresh.
1637 void commitMove();
1638 /// Undoes every journaled change since commitMove().
1639 void rollbackMove();
1640 bool
1641 generateMove(llvm::SmallVector<std::pair<mlir::Operation *, TileID>> &moves);
1642 int evaluateMove(
1643 mlir::Operation *tile, TileID newPos,
1644 llvm::SmallVector<std::pair<size_t, NetBoundingBox>> &backups);
1645 void
1646 revertMove(llvm::SmallVector<std::pair<size_t, NetBoundingBox>> &backups);
1647
1648 // Utility methods
1649 void buildNetModel(llvm::SmallVector<ObjectFifoCreateOp> &objectFifos,
1650 llvm::SmallVector<ObjectFifoLinkOp> &objectFifoLinks);
1651 void buildFifoBufferInfo(DeviceOp device,
1652 llvm::ArrayRef<ObjectFifoCreateOp> objectFifos,
1653 llvm::ArrayRef<ObjectFifoLinkOp> objectFifoLinks);
1654 void buildRouteModel(DeviceOp device, llvm::ArrayRef<FlowOp> flows,
1655 llvm::ArrayRef<PacketFlowOp> pktFlows,
1656 llvm::ArrayRef<RouteOp> routes,
1657 llvm::ArrayRef<DMAChannelAnalysis::ChannelClaim> claims);
1658 int computeNetHPWL(const NetInfo &net) const;
1659 int computeTotalHPWL() const;
1660 void initBoundingBoxes();
1661 double estimateInitialTemperature(int numSamples);
1662 bool isLegalPosition(mlir::Operation *tile, TileID pos) const;
1663 // The tile ops at `pos`, but `tile` and `leaving`, that name a channel by
1664 // index, for namedClash().
1665 llvm::SmallVector<mlir::Operation *>
1666 namedAt(mlir::Operation *tile, TileID pos,
1667 mlir::Operation *leaving = nullptr) const;
1668 int64_t computeTileMemoryWeight(mlir::Operation *tile) const;
1669 void printPlacementStats(int64_t elapsedMs) const;
1670};
1671
1672} // namespace xilinx::AIE
1673
1674#endif // AIE_PLACER_H
virtual AIETileType getTileType(int col, int row) const =0
Return the tile type for the given tile coordinates.
virtual int rows() const =0
Return the number of rows in the device.
uint32_t getNumDMAChannels(int col, int row, AIE::DMAChannelDir dir) const
Return the number of DMA channels a tile has in one direction.
virtual int columns() const =0
Return the number of columns in the device.
virtual bool isLegalMemAffinity(int coreCol, int coreRow, int memCol, int memRow) const =0
Return true if core can access the memory in mem.
A DenseMap that notes what each write through operator[] overwrote, so rollback() can restore it as o...
Definition AIEPlacer.h:1139
llvm::DenseMap< Key, Value > Map
Definition AIEPlacer.h:1141
Map::const_iterator begin() const
Definition AIEPlacer.h:1153
Value lookup(const Key &key) const
Definition AIEPlacer.h:1148
Map::const_iterator end() const
Definition AIEPlacer.h:1154
Map::const_iterator find(const Key &key) const
Definition AIEPlacer.h:1149
Value & operator[](const Key &key)
Definition AIEPlacer.h:1142
bool contains(const Key &key) const
Definition AIEPlacer.h:1152
BoundedMemo< std::vector< int64_t >, Outcome > Memo
Packings by what pack() reads, the least recently used dropped first beyond its capacity.
Definition AIELockPlan.h:71
std::optional< DMAChannelAnalysis::ChannelClaim > claimWith(TileID at, const PinnedChannels::End &end) const
std::optional< PinnedChannels::End > clashWith(TileID at, const PinnedChannels::End &end) const
PinnedChannelUse(const PinnedChannels &rule)
Definition AIEPlacer.h:312
llvm::SmallVector< int > channelsAt(TileID at, bool sends) const
int place(TileID at, const PinnedChannels::End &end, int sign)
std::optional< std::pair< int, int > > heldAt(TileID at, llvm::ArrayRef< PinnedChannels::End > ends) const
llvm::DenseMap< int, llvm::SmallVector< PinnedChannels::End, 2 > > sendingAt(TileID at) const
void claim(TileID at, const DMAChannelAnalysis::ChannelClaim &claim, int sign)
std::optional< std::string > whyApart(End a, End b) const
bool sharesClaim(End end, const DMAChannelAnalysis::ChannelClaim &claim) const
static std::optional< End > endOf(ObjectFifoCreateOp fifo, std::optional< unsigned > consumer)
unsigned share(End end, const llvm::DenseMap< mlir::Operation *, unsigned > &rank)
PinnedChannels(const AIETargetModel &targetModel, bool packetSwitched)
Definition AIEPlacer.h:272
const llvm::DenseMap< mlir::Operation *, Peak > & users() const
Definition AIEPlacer.h:382
int shortfall(llvm::ArrayRef< mlir::Operation * > onTile, TileID tile) const
bool uses(mlir::Operation *logicalTile) const
Definition AIEPlacer.h:379
ShimMM2SUses overlayUses
Definition AIEPlacer.h:499
virtual mlir::LogicalResult place(DeviceOp device)=0
llvm::DenseMap< mlir::Operation *, llvm::SmallVector< DMAChannelAnalysis::ChannelClaim > > claimsOf
Definition AIEPlacer.h:431
static Adjacency buildCascadeAdjacency(llvm::ArrayRef< CascadeFlowOp > cascadeFlows)
llvm::SmallVector< mlir::Operation * > overlayTileOps() const
static bool satisfiesConstraints(mlir::Operation *tile, TileID pos)
static llvm::MapVector< mlir::Operation *, std::pair< int, int > > flowChannelDemand(llvm::ArrayRef< FlowOp > flows, llvm::ArrayRef< PacketFlowOp > pktFlows, llvm::ArrayRef< RouteOp > routes, llvm::ArrayRef< DMAChannelAnalysis::ChannelClaim > claims, llvm::DenseMap< mlir::Operation *, llvm::SmallVector< std::pair< int, int > > > *named=nullptr, llvm::DenseMap< mlir::Operation *, mlir::Operation * > *keys=nullptr)
static Adjacency buildSharedMemAdjacency(llvm::ArrayRef< ObjectFifoCreateOp > objectFifos)
llvm::DenseMap< mlir::Operation *, llvm::SmallVector< unsigned > > ddrGroupsOf
Definition AIEPlacer.h:450
void buildStreamNets(DeviceOp device, const CollectedOps &collected)
llvm::DenseMap< mlir::Operation *, llvm::SmallVector< unsigned > > streamNetsOf
Definition AIEPlacer.h:528
int64_t ddrGroupSpread(const DdrGroup &group, llvm::function_ref< std::optional< int >(mlir::Operation *)> columnOf, int weight) const
llvm::DenseMap< mlir::Operation *, StreamDemand > streamDemand
Definition AIEPlacer.h:505
llvm::SmallVector< StreamNet > streamNets
Definition AIEPlacer.h:526
llvm::DenseMap< mlir::Operation *, unsigned > coreKeys
Definition AIEPlacer.h:551
RuntimeBdIds runtimeBdIds
Definition AIEPlacer.h:438
static Adjacency buildObjectFifoAdjacency(llvm::ArrayRef< ObjectFifoCreateOp > objectFifos)
static ShareableShimEnds collectShareableShimEnds(DeviceOp device, llvm::ArrayRef< ObjectFifoCreateOp > objectFifos, const llvm::DenseMap< mlir::Operation *, unsigned > &rank, const llvm::DenseMap< mlir::Operation *, mlir::Operation * > &routeKeys={})
static llvm::DenseMap< mlir::StringAttr, llvm::SmallVector< ShimTransferSpans::Gate > > provenShimGates(DeviceOp device)
llvm::DenseMap< mlir::Operation *, int > broadcastFanout
Definition AIEPlacer.h:510
void setNeighbourCores(llvm::DenseMap< mlir::Operation *, unsigned > keys, llvm::SmallVector< llvm::DenseMap< TileID, unsigned > > neighbours)
Definition AIEPlacer.h:122
static Adjacency buildFlowAdjacency(llvm::ArrayRef< FlowOp > flows, llvm::ArrayRef< PacketFlowOp > pktFlows)
const AIETargetModel * targetModel
Definition AIEPlacer.h:556
std::pair< mlir::Operation *, TileID > AllocateInfo
Definition AIEPlacer.h:143
int64_t ddrSpread(llvm::function_ref< std::optional< int >(mlir::Operation *)> columnOf, int weight) const
static Adjacency buildComputePeerAdjacency(llvm::ArrayRef< ObjectFifoCreateOp > objectFifos)
virtual ~Placer()=default
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
virtual llvm::StringRef getName() const =0
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
std::optional< TileID > getPlacement(mlir::Operation *logicalTile) const
Definition AIEPlacer.h:133
void buildShimModel(DeviceOp device, llvm::ArrayRef< ObjectFifoCreateOp > objectFifos, llvm::ArrayRef< DMAChannelAnalysis::ChannelClaim > claims, const llvm::DenseMap< mlir::Operation *, unsigned > &rank, const llvm::DenseMap< mlir::Operation *, mlir::Operation * > &routeKeys={})
void collectOverlayUses(DeviceOp device)
llvm::SmallVector< AllocateInfo > & getAllocates()
Definition AIEPlacer.h:144
TileAvailability availability
Definition AIEPlacer.h:561
llvm::MapVector< mlir::Operation *, std::array< ShimSide, 2 > > ShareableShimEnds
Definition AIEPlacer.h:234
void buildStreamDemand(llvm::ArrayRef< ObjectFifoCreateOp > objectFifos)
static int shimChannelsSaved(const ShimTransferSpans &spans, llvm::ArrayRef< const ShimSide * > sides, llvm::ArrayRef< mlir::StringAttr > extra, llvm::ArrayRef< int > pinnedHere)
OverlayFit overlayAt(TileID at, const PinnedChannelUse &pins, llvm::ArrayRef< PinnedChannels::End > extra, llvm::ArrayRef< mlir::Operation * > tilesHere, const ShimTransferSpans *spans) const
llvm::DenseMap< mlir::Operation *, llvm::SmallVector< mlir::Operation * > > incomingFifos
Definition AIEPlacer.h:508
mlir::LogicalResult emitNamedClash(mlir::Operation *tile, TileID at, std::pair< mlir::Operation *, std::pair< int, int > > clash) const
static CollectedOps collectOperations(DeviceOp device)
Definition AIEPlacer.cpp:95
llvm::SmallVector< DdrGroup > ddrGroups
Definition AIEPlacer.h:448
virtual void initialize(DeviceOp device, bool controlOverlay, bool adaptiveOverlay, bool packetSwitched)
Definition AIEPlacer.cpp:62
int getFinalLockGroups() const
Definition AIEPlacer.h:1191
bool getFinalLockStopped() const
Definition AIEPlacer.h:1193
int getFinalLockPenalty() const
Definition AIEPlacer.h:1192
SAPlacer(unsigned seed=0, SAConfig config={})
Definition AIEPlacer.h:1185
llvm::StringRef getName() const override
Definition AIEPlacer.h:1189
static bool isShimEndType(std::optional< AIETileType > type)
Definition AIEPlacer.h:1198
int getFinalCost() const
Definition AIEPlacer.h:1190
mlir::LogicalResult place(DeviceOp device) override
void record(bool accepted)
double getTemperature() const
Definition AIEPlacer.h:1095
double getAcceptanceRatio() const
int getMovesPerIter() const
Definition AIEPlacer.h:1097
SequentialPlacer(std::optional< int > coresPerCol=std::nullopt, bool mergeLogicalTiles=true, bool spreadUnanchoredTiles=false)
Definition AIEPlacer.h:647
llvm::StringRef getName() const override
Definition AIEPlacer.h:658
void initialize(DeviceOp device, bool controlOverlay, bool adaptiveOverlay, bool packetSwitched) override
mlir::LogicalResult place(DeviceOp device) override
Shim endpoint lifetimes, including calls to self-contained runtime sequences.
int64_t near(double fraction) const
void add(TileID src, llvm::ArrayRef< TileID > dsts, bool packet, int sign)
void forEachPeer(mlir::Operation *op, const Placer::Adjacency &adjacency, F &&fn)
Definition AIEPlacer.h:568
llvm::DenseMap< mlir::Operation *, TileID > PlacementResult
Definition AIEPlacer.h:79
void forEachMemAffinityNeighbor(const AIETargetModel &targetModel, TileID at, F &&fn)
Definition AIEPlacer.h:597
struct TileID { friend std::ostream &operator<<(std::ostream &os, const TileID &s) { os<< "TileID("<< s.col<< ", "<< s.row<< ")"; return os; } friend std::string to_string(const TileID &s) { std::ostringstream ss; ss<< s; return ss.str(); } friend llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const TileID &s) { os<< to_string(s); return os; } inline bool operator<(const TileID &rhs) const { return std::tie(col, row)< std::tie(rhs.col, rhs.row); } bool operator==(const TileID &rhs) const { return std::tie(col, row)==std::tie(rhs.col, rhs.row); } bool operator!=(const TileID &rhs) const { return !(*this==rhs);} int col, row;} TileID
PlacerType
Placement algorithm type for pass option.
Definition AIEPlacer.h:33
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
constexpr int64_t kDefaultPlacementBudget
assign-buffer-addresses' placement-budget unless set.
bool isSharedComputeMemory(const AIETargetModel &targetModel, TileID a, TileID b)
Definition AIEPlacer.h:588
A channel claimed by index: by a DMA program start, a runtime task or a shim allocation (owner),...
llvm::SmallVector< mlir::Operation * > endpoints
Definition AIEPlacer.h:1131
NetBoundingBox bb
Definition AIEPlacer.h:1132
void addEdge(TileLike first, TileLike second)
Definition AIEPlacer.cpp:42
llvm::DenseMap< mlir::Operation *, llvm::SmallVector< unsigned, 2 > > tileToEdges
Definition AIEPlacer.h:152
void addEdgeFromValues(mlir::Value a, mlir::Value b)
Definition AIEPlacer.cpp:53
bool hasEdges(mlir::Operation *op) const
Definition AIEPlacer.h:160
llvm::SmallVector< std::pair< TileLike, TileLike >, 4 > edges
Definition AIEPlacer.h:150
llvm::SmallVector< RouteOp > routes
Definition AIEPlacer.h:174
llvm::SmallVector< ObjectFifoLinkOp > objectFifoLinks
Definition AIEPlacer.h:169
llvm::SmallVector< CascadeFlowOp > cascadeFlows
Definition AIEPlacer.h:171
llvm::DenseMap< mlir::Operation *, unsigned > rank
Definition AIEPlacer.h:176
llvm::SmallVector< PacketFlowOp > pktFlows
Definition AIEPlacer.h:173
llvm::SmallVector< FlowOp > flows
Definition AIEPlacer.h:172
llvm::SmallVector< ObjectFifoCreateOp > objectFifos
Definition AIEPlacer.h:168
llvm::SmallVector< ObjectFifoAllocateOp > objectFifoAllocates
Definition AIEPlacer.h:170
llvm::SmallVector< LogicalTileOp > logicalTiles
Definition AIEPlacer.h:167
llvm::SmallVector< int64_t > weights
Definition AIEPlacer.h:445
llvm::SmallVector< llvm::BitVector > together
Definition AIEPlacer.h:446
llvm::SmallVector< mlir::Operation * > tiles
Definition AIEPlacer.h:444
std::optional< unsigned > consumer
Definition AIEPlacer.h:264
llvm::SmallVector< mlir::StringAttr > ends
Definition AIEPlacer.h:227
llvm::SmallVector< int > pinned
Definition AIEPlacer.h:230
llvm::SmallVector< std::pair< int, llvm::SmallVector< mlir::StringAttr > > > shared
Definition AIEPlacer.h:229
llvm::SmallVector< mlir::Operation *, 2 > dsts
Definition AIEPlacer.h:519
mlir::Operation * delegate
Definition AIEPlacer.h:523
CoreDataCharge(int64_t bytes, int64_t alignBytes)
Definition AIEPlacer.h:1080
llvm::DenseMap< unsigned, CoreDataCharge > coreDataCharges
Definition AIEPlacer.h:1085
llvm::SmallVector< std::string > walkedFifos
Definition AIEPlacer.h:1074
The shim MM2S channels device's overlay weighs, for aie-generate-column-control-overlay.
StreamDemand & operator+=(const StreamDemand &other)
Definition AIEPlacer.h:47
std::vector< TileID > compTiles
Definition AIEPlacer.h:83
llvm::DenseMap< TileID, int > outputChannelsUsed
Definition AIEPlacer.h:101
llvm::DenseSet< TileID > physicalCores
Definition AIEPlacer.h:95
std::vector< TileID > overBudgetCompTiles
Definition AIEPlacer.h:98
void removeTile(TileID tile, AIETileType type)
std::vector< TileID > nonCompTiles
Definition AIEPlacer.h:84
llvm::DenseSet< TileID > compTilesSet
Definition AIEPlacer.h:93
llvm::DenseMap< TileID, int > inputChannelsUsed
Definition AIEPlacer.h:100
llvm::DenseMap< TileID, llvm::SmallVector< mlir::Operation * > > runtimeBdTiles
Definition AIEPlacer.h:104
llvm::DenseMap< TileID, StreamDemand > streamsUsed
Definition AIEPlacer.h:102