MLIR-AIE 1.4.6.dev
AIEDMAChannelAnalysis.cpp
Go to the documentation of this file.
1//===- AIEDMAChannelAnalysis.cpp --------------------------------*- C++ -*-===//
2//
3// Copyright (C) 2021-2022 Xilinx, Inc.
4// Copyright (C) 2022-2026 Advanced Micro Devices, Inc.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
12
13#include "llvm/ADT/BitVector.h"
14#include "llvm/ADT/DenseSet.h"
15
16#include <functional>
17#include <map>
18#include <numeric>
19#include <set>
20#include <vector>
21
22using namespace mlir;
23using namespace xilinx;
24using namespace xilinx::AIE;
25
26Value DMAChannelAnalysis::getTileKey(Value tile) {
27 auto tileOp = cast<TileLike>(tile.getDefiningOp());
28 auto col = tileOp.tryGetCol();
29 auto row = tileOp.tryGetRow();
30 if (!col || !row)
31 return tile;
32 return tilesByCoordinate.try_emplace({*col, *row}, tile).first->second;
33}
34
35void DMAChannelAnalysis::claim(Value tile, DMAChannelDir dir, int channel,
36 Operation *owner) {
37 if (usedChannels.try_emplace({getTileKey(tile), dir, channel}, owner).second)
38 claims.emplace_back(tile, dir, channel, owner);
39}
40
42 for (auto program : device.getOps<DmaBody>()) {
43 for (Block &block : program.getDmaBody()) {
44 for (auto start : block.getOps<DMAStartOp>()) {
45 // The route endpoint it names claims the channel; see assignChannels.
46 if (start.getEndpoint())
47 continue;
48 claim(program.getTile(), start.getChannelDir(), start.getChannelIndex(),
49 start);
50 }
51 }
52 }
53
54 // A flow ending at a tile's DMA claims that channel's stream even when no
55 // DMA body here starts it: its BDs may come from the runtime sequence alone.
56 // First-free assignment must skip it, but a pinned request may name it --
57 // that is the DMA feeding or draining the flow, as when allocation reruns
58 // over flows it lowered itself.
59 auto streamDMA = [&](Value tile, DMAChannelDir dir, int channel,
60 Operation *owner) {
61 streamedChannels.try_emplace(
62 std::make_tuple(getTileKey(tile), dir, channel), owner);
63 };
64 for (auto flowOp : device.getOps<FlowOp>()) {
65 if (flowOp.getSourceBundle() == WireBundle::Core) {
66 usedStreams.try_emplace({getTileKey(flowOp.getSource()),
67 DMAChannelDir::MM2S, flowOp.getSourceChannel()},
68 StreamClaim{flowOp, false});
69 }
70 if (flowOp.getDestBundle() == WireBundle::Core) {
71 usedStreams.try_emplace({getTileKey(flowOp.getDest()),
72 DMAChannelDir::S2MM, flowOp.getDestChannel()},
73 StreamClaim{flowOp, false});
74 }
75 if (flowOp.getSourceBundle() == WireBundle::DMA)
76 streamDMA(flowOp.getSource(), DMAChannelDir::MM2S,
77 flowOp.getSourceChannel(), flowOp);
78 if (flowOp.getDestBundle() == WireBundle::DMA)
79 streamDMA(flowOp.getDest(), DMAChannelDir::S2MM, flowOp.getDestChannel(),
80 flowOp);
81 }
82 for (auto packetFlow : device.getOps<PacketFlowOp>()) {
83 for (auto source : packetFlow.getOps<PacketSourceOp>())
84 if (source.getBundle() == WireBundle::DMA)
85 streamDMA(source.getTile(), DMAChannelDir::MM2S, source.getChannel(),
86 packetFlow);
87 for (auto dest : packetFlow.getOps<PacketDestOp>())
88 if (dest.getBundle() == WireBundle::DMA)
89 streamDMA(dest.getTile(), DMAChannelDir::S2MM, dest.getChannel(),
90 packetFlow);
91 }
92
93 // A task the runtime sequence configures on a channel by index programs that
94 // channel, as a DMA body would.
95 device.walk([&](AIEX::DMAConfigureTaskOp task) {
96 claim(task.getTile(), task.getDirection(), (int)task.getChannel(), task);
97 });
98
99 for (auto flow : device.getOps<PacketFlowOp>()) {
100 Block &ports = flow.getPorts().front();
101 for (auto source : ports.getOps<PacketSourceOp>())
102 if (source.getBundle() == WireBundle::Core)
103 usedStreams.try_emplace({getTileKey(source.getTile()),
104 DMAChannelDir::MM2S, source.channelIndex()},
105 StreamClaim{source, true});
106 for (auto dest : ports.getOps<PacketDestOp>())
107 if (dest.getBundle() == WireBundle::Core)
108 usedStreams.try_emplace({getTileKey(dest.getTile()),
109 DMAChannelDir::S2MM, dest.channelIndex()},
110 StreamClaim{dest, true});
111 }
112
113 // Shim allocations reserve channels outside the DMA bodies above. A
114 // shareable allocation still holds its channel against unlisted ends, so
115 // it is a claim too; skip the control overlay's, which the placers count
116 // as the planned overlay channel.
117 for (auto allocOp : device.getOps<ShimDMAAllocationOp>()) {
118 MLIRContext *context = allocOp->getContext();
119 if (!AIEDialect::ShareableWithAttrHelper(context).isAttrPresent(allocOp)) {
120 claim(allocOp.getTile(), allocOp.getChannelDir(),
121 (int)allocOp.getChannelIndex(), allocOp);
122 continue;
123 }
124 shareableChannels.try_emplace(
125 std::make_tuple(getTileKey(allocOp.getTile()), allocOp.getChannelDir(),
126 (int)allocOp.getChannelIndex()),
127 allocOp.getOperation());
128 if (!AIEDialect::IsCtrlPktOverlayAttrHelper(context).isAttrPresent(allocOp))
129 claims.emplace_back(allocOp.getTile(), allocOp.getChannelDir(),
130 (int)allocOp.getChannelIndex(), allocOp);
131 }
132}
133
135 TileLike tile, DMAChannelDir dir, bool requiresAdjacentTileAccessChannels) {
136 std::optional<int> col = tile.tryGetCol();
137 std::optional<int> row = tile.tryGetRow();
138 const auto &targetModel = getTargetModel(tile);
139 // A tile that is not fully placed stands for any tile of its type.
140 TileID id =
141 col && row
142 ? TileID{*col, *row}
143 : cast<LogicalTileOp>(tile.getOperation()).getCanonicalTileID();
144 int maxChannelNum = targetModel.getNumDMAChannels(id.col, id.row, dir);
145
146 if (!requiresAdjacentTileAccessChannels)
147 return maxChannelNum;
148
149 if (col && row)
150 return std::min<int>(
151 maxChannelNum,
152 targetModel.getMaxChannelNumForAdjacentMemTile(*col, *row));
153
154 // Assignment before placement must be safe at every compatible position,
155 // not assume that unresolved coordinates remove neighbor restrictions.
156 bool foundPosition = false;
157 for (int c = 0; c < targetModel.columns(); ++c) {
158 if (col && c != *col)
159 continue;
160 for (int r = 0; r < targetModel.rows(); ++r) {
161 if ((row && r != *row) ||
162 targetModel.getTileType(c, r) != tile.getTileType())
163 continue;
164 foundPosition = true;
165 maxChannelNum = std::min<int>(
166 maxChannelNum, targetModel.getMaxChannelNumForAdjacentMemTile(c, r));
167 }
168 }
169
170 return foundPosition ? maxChannelNum : 0;
171}
172
174 TileLike tile, DMAChannelDir dir, bool requiresAdjacentTileAccessChannels,
175 Operation *owner) {
176 int limit = getDMAChannelLimit(tile, dir, requiresAdjacentTileAccessChannels);
177 for (int i = 0; i < limit; i++) {
178 if (isChannelFree(tile, dir, i) &&
179 reservePinnedChannel(tile, dir, i, owner) >= 0) {
180 return i;
181 }
182 }
183 return -1;
184}
185
186bool DMAChannelAnalysis::isChannelFree(TileLike tile, DMAChannelDir dir,
187 int channel) {
188 auto key = std::make_tuple(getTileKey(tile->getResult(0)), dir, channel);
189 return !usedChannels.contains(key) && !streamedChannels.contains(key) &&
190 !shareableChannels.contains(key);
191}
192
193int DMAChannelAnalysis::reservePinnedChannel(TileLike tile, DMAChannelDir dir,
194 int channel, Operation *owner,
195 bool shareable) {
196 int maxChannelNum = getDMAChannelLimit(tile, dir, false);
197 if (channel < 0 || channel >= maxChannelNum) {
198 return -1;
199 }
200 auto key = std::make_tuple(getTileKey(tile->getResult(0)), dir, channel);
201 if (auto *reservation = shareableChannels.lookup(key)) {
202 if (!shareable)
203 return -1;
204 auto allowed =
205 AIEDialect::ShareableWithAttrHelper(reservation->getContext())
206 .getAttr(reservation);
207 auto name =
208 owner ? owner->getAttrOfType<StringAttr>("sym_name") : StringAttr();
209 if (!allowed || !name || llvm::none_of(allowed, [&](Attribute attr) {
210 auto symbol = dyn_cast<FlatSymbolRefAttr>(attr);
211 return symbol && symbol.getAttr() == name;
212 }))
213 return -1;
214 }
215 if (usedChannels.try_emplace(key, owner).second) {
216 if (shareable)
217 sharedChannels.insert(key);
218 return channel;
219 }
220 // Packet-switched sources share a channel: the runtime writes its
221 // descriptors one transfer at a time, each under its own header.
222 if (shareable && sharedChannels.contains(key))
223 return channel;
224 return -1;
225}
226
228 DMAChannelDir dir,
229 int channel) {
230 auto key = std::make_tuple(getTileKey(tile->getResult(0)), dir, channel);
231 if (Operation *owner = usedChannels.lookup(key))
232 return owner;
233 if (Operation *owner = streamedChannels.lookup(key))
234 return owner;
235 return shareableChannels.lookup(key);
236}
237
238LogicalResult DMAChannelAnalysis::checkAIEStreamIndex(TileLike tile,
239 DMAChannel chan,
240 Operation *user,
241 bool packet) {
242 auto [it, inserted] = usedStreams.try_emplace(
243 {getTileKey(tile->getResult(0)), chan.direction, chan.channel},
244 StreamClaim{user, packet});
245 if (inserted || (packet && it->second.packet)) {
246 return success();
247 }
248 auto diag = user->emitOpError("Core ")
249 << (chan.direction == DMAChannelDir::MM2S ? "output " : "input ")
250 << chan.channel
251 << " is already in use on this tile; a core stream port carries "
252 "one circuit or only packet flows";
253 diag.attachNote(it->second.owner->getLoc()) << "the other stream is here";
254 return diag;
255}
256
257SmallVector<Block *> DMAChannelAnalysis::chainOf(DMAStartOp start) {
258 SmallVector<Block *> chain;
259 SmallPtrSet<Block *, 8> seen;
260 SmallVector<Block *> work{start.getDest()};
261 while (!work.empty()) {
262 Block *block = work.pop_back_val();
263 if (!seen.insert(block).second || block->getOps<DMABDOp>().empty())
264 continue;
265 chain.push_back(block);
266 if (auto next = dyn_cast<NextBDOp>(block->getTerminator()))
267 work.push_back(next.getDest());
268 }
269 return chain;
270}
271
272int64_t DMAChannelAnalysis::countBDs(DMAStartOp start) {
273 int64_t bds = 0;
274 for (Block *block : chainOf(start))
275 bds += llvm::range_size(block->getOps<DMABDOp>());
276 return bds;
277}
278
280 for (auto program : device.getOps<DmaBody>())
281 for (Block &block : program.getDmaBody())
282 for (auto start : block.getOps<DMAStartOp>())
283 if (!start.getEndpointOp())
284 if (Operation *tile = program.getTile().getDefiningOp())
285 fixed[tile][start.getChannelIndex()] += countBDs(start);
286 unsigned order = 0;
288 device,
289 [&](Operation *, Operation *tile, std::optional<int> channel,
290 int32_t id) { pinned[tile].try_emplace(id, Pin{order++, channel}); });
291}
292
293DenseMap<int, int64_t>
294DMAChannelAnalysis::TakenBDs::at(const AIETargetModel &target, int col, int row,
295 ArrayRef<Operation *> tiles) const {
296 auto here = [&](Operation *tile) {
297 auto like = dyn_cast<TileLike>(tile);
298 return llvm::is_contained(tiles, tile) ||
299 (like && like.tryGetCol() == col && like.tryGetRow() == row);
300 };
301 DenseMap<int, int64_t> taken;
302 for (auto &[tile, channels] : fixed)
303 if (here(tile))
304 for (auto [channel, bds] : channels)
305 taken[channel] += bds;
306 std::map<int32_t, Pin> ids;
307 for (auto &[tile, pins] : pinned)
308 if (here(tile))
309 for (auto [id, pin] : pins)
310 if (auto [it, added] = ids.try_emplace(id, pin);
311 !added && pin.order < it->second.order)
312 it->second = pin;
313 int numChannels = std::max(
314 target.getNumSourceSwitchboxConnections(col, row, WireBundle::DMA),
315 target.getNumDestSwitchboxConnections(col, row, WireBundle::DMA));
316 for (auto [id, pin] : ids)
317 for (int channel = 0, last = pin.channel.value_or(numChannels - 1);
318 channel <= last; ++channel)
319 if (target.isBdChannelAccessible(col, row, id, channel)) {
320 ++taken[channel];
321 break;
322 }
323 return taken;
324}
325
326SmallVector<std::pair<int, int>>
328 std::set<std::pair<int, int>> at;
329 auto add = [&](Operation *tile) {
330 auto like = dyn_cast<TileLike>(tile);
331 if (!like)
332 return;
333 if (auto col = like.tryGetCol(), row = like.tryGetRow(); col && row)
334 at.insert({*col, *row});
335 };
336 for (auto &entry : fixed)
337 add(entry.first);
338 for (auto &entry : pinned)
339 add(entry.first);
340 return {at.begin(), at.end()};
341}
342
343llvm::SmallVector<DMAChannelAnalysis::BDGroup>
344DMAChannelAnalysis::bdGroups(const AIETargetModel &target, int col, int row,
345 int numChannels) {
346 uint32_t numBDs = target.getNumBDs(col, row);
347 SmallVector<BDGroup> groups;
348 for (int channel = 0; channel < numChannels; ++channel) {
349 llvm::BitVector ids(numBDs);
350 for (uint32_t bd = 0; bd < numBDs; ++bd)
351 if (target.isBdChannelAccessible(col, row, bd, channel))
352 ids.set(bd);
353 BDGroup merged{ids, {channel}};
354 for (auto *it = groups.begin(); it != groups.end();) {
355 if (!it->ids.anyCommon(merged.ids)) {
356 ++it;
357 continue;
358 }
359 merged.ids |= it->ids;
360 llvm::append_range(merged.channels, it->channels);
361 it = groups.erase(it);
362 }
363 groups.push_back(std::move(merged));
364 }
365 for (BDGroup &group : groups)
366 llvm::sort(group.channels);
367 return groups;
368}
369
370static SmallVector<DMAChannelAnalysis::BDGroup>
371tileBDGroups(const AIETargetModel &target, int col, int row) {
372 int numChannels = std::max(
373 target.getNumSourceSwitchboxConnections(col, row, WireBundle::DMA),
374 target.getNumDestSwitchboxConnections(col, row, WireBundle::DMA));
375 return DMAChannelAnalysis::bdGroups(target, col, row, numChannels);
376}
377
378std::optional<SmallVector<int>>
380 int row, ArrayRef<BDPlanEnd> allEnds,
381 function_ref<bool(DMAChannelDir, int)> free,
382 function_ref<int64_t(int)> spent) {
383 return planBDChannels(tileBDGroups(target, col, row), allEnds, free, spent);
384}
385
386std::optional<SmallVector<int>>
387DMAChannelAnalysis::planBDChannels(ArrayRef<BDGroup> tileGroups,
388 ArrayRef<BDPlanEnd> allEnds,
389 function_ref<bool(DMAChannelDir, int)> free,
390 function_ref<int64_t(int)> spent) {
391 // Channels whose BD ids overlap at all share one pool of ids, as bdRoom in
392 // aie-objectfifo-allocate counts them.
393 struct Group {
394 llvm::BitVector ids;
395 SmallVector<int> channels;
396 int64_t room = 0;
397 };
398 SmallVector<Group> groups;
399 for (const BDGroup &group : tileGroups)
400 groups.push_back({group.ids, group.channels, 0});
401 for (Group &group : groups) {
402 group.room = group.ids.count();
403 for (int channel : group.channels)
404 group.room -= spent(channel);
405 }
406
407 // An end pinning a channel takes it, whatever `free` says, and shares it
408 // with every end pinning it too; the rest are planned around them.
409 SmallVector<BDPlanEnd> ends;
410 SmallVector<unsigned> looseOf;
411 llvm::DenseSet<std::pair<int, int>> pinned;
412 for (auto [index, end] : llvm::enumerate(allEnds)) {
413 if (!end.pinned) {
414 ends.push_back(end);
415 looseOf.push_back(index);
416 continue;
417 }
418 int channel = *end.pinned;
419 auto *group = llvm::find_if(groups, [&](const Group &group) {
420 return llvm::is_contained(group.channels, channel);
421 });
422 if (group == groups.end())
423 return std::nullopt;
424 group->room -= end.bds;
425 pinned.insert({static_cast<int>(end.dir), *end.pinned});
426 }
427 if (llvm::any_of(groups, [](const Group &group) { return group.room < 0; }))
428 return std::nullopt;
429 auto open = [&](DMAChannelDir dir, int channel) {
430 return free(dir, channel) &&
431 !pinned.contains({static_cast<int>(dir), channel});
432 };
433
434 // Each end goes to a group, the most demanding first; a choice stands when
435 // every group's ends fit its ids and, within a direction, take distinct free
436 // channels below their bounds: the tightest bound first, each the lowest
437 // channel left, which finds a matching whenever one exists since the
438 // allowed channels of any two ends nest.
439 SmallVector<unsigned> order(ends.size());
440 std::iota(order.begin(), order.end(), 0);
441 auto shape = [&](unsigned end) {
442 return std::make_tuple(-ends[end].bds, static_cast<int>(ends[end].dir),
443 ends[end].limit);
444 };
445 llvm::stable_sort(
446 order, [&](unsigned a, unsigned b) { return shape(a) < shape(b); });
447 SmallVector<unsigned> groupOf(ends.size());
448 SmallVector<int> channelOf(ends.size(), -1);
449 auto match = [&]() {
450 SmallVector<unsigned> byBound(ends.size());
451 std::iota(byBound.begin(), byBound.end(), 0);
452 llvm::stable_sort(byBound, [&](unsigned a, unsigned b) {
453 return ends[a].limit < ends[b].limit;
454 });
455 llvm::DenseSet<std::pair<int, int>> taken;
456 for (unsigned end : byBound) {
457 channelOf[end] = -1;
458 for (int channel : groups[groupOf[end]].channels) {
459 int dir = static_cast<int>(ends[end].dir);
460 if (channel < ends[end].limit && open(ends[end].dir, channel) &&
461 taken.insert({dir, channel}).second) {
462 channelOf[end] = channel;
463 break;
464 }
465 }
466 if (channelOf[end] < 0)
467 return false;
468 }
469 return true;
470 };
471 // The same nesting (bounds above) means a group's ends fit a direction
472 // exactly when, for every bound, no more of them have that bound or a
473 // tighter one than free channels lie below it. Checked as ends are placed:
474 // every completed choice matches, since no group ever holds more ends than
475 // it has channels.
476 SmallVector<int> bounds;
477 for (const BDPlanEnd &end : ends)
478 bounds.push_back(end.limit);
479 llvm::sort(bounds);
480 bounds.erase(llvm::unique(bounds), bounds.end());
481 size_t slots = 2 * bounds.size();
482 SmallVector<int64_t> below(groups.size() * slots, 0);
483 for (auto [g, group] : llvm::enumerate(groups))
484 for (DMAChannelDir dir : {DMAChannelDir::S2MM, DMAChannelDir::MM2S})
485 for (auto [i, bound] : llvm::enumerate(bounds))
486 for (int channel : group.channels)
487 below[g * slots + static_cast<int>(dir) * bounds.size() + i] +=
488 channel < bound && open(dir, channel);
489 SmallVector<int64_t> held(groups.size() * slots, 0);
490 auto fits = [&](unsigned g, DMAChannelDir dir) {
491 size_t base = g * slots + static_cast<int>(dir) * bounds.size();
492 int64_t tighter = 0;
493 for (size_t i = 0; i < bounds.size(); ++i) {
494 tighter += held[base + i];
495 if (tighter > below[base + i])
496 return false;
497 }
498 return true;
499 };
500 // Over every group at once, too many ends of a direction and bound fail
501 // before any is placed.
502 for (DMAChannelDir dir : {DMAChannelDir::S2MM, DMAChannelDir::MM2S}) {
503 int64_t tighter = 0;
504 for (size_t i = 0; i < bounds.size(); ++i) {
505 int64_t room = 0;
506 for (size_t g = 0; g < groups.size(); ++g)
507 room += below[g * slots + static_cast<int>(dir) * bounds.size() + i];
508 tighter += llvm::count_if(ends, [&](const BDPlanEnd &end) {
509 return end.dir == dir && end.limit == bounds[i];
510 });
511 if (tighter > room)
512 return std::nullopt;
513 }
514 }
515 // Ends of one shape are interchangeable, so each takes a group no lower
516 // than the one before it of its shape.
517 std::function<bool(size_t)> place = [&](size_t next) {
518 if (next == order.size())
519 return match();
520 unsigned end = order[next];
521 size_t slot = static_cast<int>(ends[end].dir) * bounds.size() +
522 (llvm::lower_bound(bounds, ends[end].limit) - bounds.begin());
523 unsigned first = next > 0 && shape(order[next - 1]) == shape(end)
524 ? groupOf[order[next - 1]]
525 : 0;
526 for (unsigned g = first; g < groups.size(); ++g) {
527 if (groups[g].room < ends[end].bds)
528 continue;
529 ++held[g * slots + slot];
530 if (fits(g, ends[end].dir)) {
531 groupOf[end] = g;
532 groups[g].room -= ends[end].bds;
533 bool placed = place(next + 1);
534 groups[g].room += ends[end].bds;
535 if (placed) {
536 --held[g * slots + slot];
537 return true;
538 }
539 }
540 --held[g * slots + slot];
541 }
542 return false;
543 };
544 if (!place(0))
545 return std::nullopt;
546 SmallVector<int> result;
547 for (const BDPlanEnd &end : allEnds)
548 result.push_back(end.pinned ? *end.pinned : -1);
549 for (auto [loose, index] : llvm::enumerate(looseOf))
550 result[index] = channelOf[loose];
551 return result;
552}
553
555 ArrayRef<BDPlanEnd> ends, ArrayRef<unsigned> poolOf,
556 ArrayRef<BDWalkPool> pools, ArrayRef<bool> whole) {
557 SmallVector<int64_t> bds(pools.size(), 0);
558 for (auto [end, pool] : llvm::zip_equal(ends, poolOf))
559 bds[pool] += end.bds;
560 auto key = [&](unsigned pool) {
561 return std::make_tuple(pools[pool].depth, -pools[pool].objectBytes,
562 bds[pool]);
563 };
564 std::optional<unsigned> next;
565 for (unsigned pool = 0, e = pools.size(); pool < e; ++pool)
566 if (pools[pool].walkable && !whole[pool] &&
567 (!next || key(pool) > key(*next)))
568 next = pool;
569 return next;
570}
571
573 const AIETargetModel &target, int col, int row, ArrayRef<BDPlanEnd> ends,
574 ArrayRef<unsigned> poolOf, ArrayRef<BDWalkPool> pools,
575 function_ref<bool(DMAChannelDir, int)> free,
576 function_ref<int64_t(int)> spent, unsigned maxSets) {
577 BDWalkSets result;
578 SmallVector<BDGroup> tileGroups = tileBDGroups(target, col, row);
579 auto none = [](int) -> int64_t { return 0; };
580 auto fitsWalking = [&](ArrayRef<bool> whole, bool weighted) {
581 SmallVector<BDPlanEnd> planned;
582 for (auto [end, pool] : llvm::zip_equal(ends, poolOf))
583 planned.push_back({end.dir,
584 !weighted ? 0
585 : whole[pool] ? 1
586 : end.bds,
587 end.limit, end.pinned});
588 return planBDChannels(tileGroups, planned, free,
589 weighted ? spent : function_ref<int64_t(int)>(none))
590 .has_value();
591 };
592 SmallVector<bool> whole(pools.size(), false);
593 if (!fitsWalking(whole, /*weighted=*/false)) {
594 result.channelShort = true;
595 return result;
596 }
597 if (fitsWalking(whole, /*weighted=*/true))
598 return result;
599
600 SmallVector<unsigned> ranked;
601 while (std::optional<unsigned> next =
602 nextPoolToWalk(ends, poolOf, pools, whole)) {
603 ranked.push_back(*next);
604 whole[*next] = true;
605 }
606 if (!fitsWalking(whole, /*weighted=*/true)) {
607 result.fits = false;
608 return result;
609 }
610 // Walking a pool only lowers its ends' BD ids, so a set holding one that
611 // fits fits too, without asking planBDChannels.
612 unsigned n = ranked.size();
613 assert(n < 32 && "each walkable pool draws a channel the plan above fit");
614 SmallVector<int64_t> maskBytes(uint32_t(1) << n, 0);
615 for (uint32_t mask = 1; mask < (uint32_t(1) << n); ++mask) {
616 const BDWalkPool &pool = pools[ranked[llvm::countr_zero(mask)]];
617 maskBytes[mask] =
618 maskBytes[mask & (mask - 1)] + pool.depth * pool.objectBytes;
619 }
620 auto bytes = [&](uint32_t mask) { return maskBytes[mask]; };
621 // The final order needs no plan, so masks are sorted into it before any
622 // are tested: a subset always has fewer or equal bytes and a lower
623 // popcount than its supersets, so it still sorts before them, and the
624 // fitsMask shortcut below still only ever looks back at masks already
625 // tested.
626 SmallVector<uint32_t> order;
627 for (uint32_t mask = 1; mask < (uint32_t(1) << n); ++mask)
628 order.push_back(mask);
629 llvm::stable_sort(order, [&](uint32_t a, uint32_t b) {
630 int64_t aBytes = bytes(a), bBytes = bytes(b);
631 if (aBytes != bBytes)
632 return aBytes < bBytes;
633 if (llvm::popcount(a) != llvm::popcount(b))
634 return llvm::popcount(a) < llvm::popcount(b);
635 // Of two sets alike in size, the one holding the first-ranked pool that
636 // only one holds.
637 uint32_t differ = a ^ b;
638 return differ && (a & differ & -differ);
639 });
640 llvm::BitVector fitsMask(uint32_t(1) << n);
641 for (uint32_t mask : order) {
642 if (result.sets.size() >= maxSets)
643 break;
644 bool fits = llvm::any_of(llvm::seq<unsigned>(0, n), [&](unsigned bit) {
645 return (mask >> bit & 1) && fitsMask.test(mask & ~(uint32_t(1) << bit));
646 });
647 if (!fits) {
648 llvm::fill(whole, false);
649 for (unsigned bit = 0; bit < n; ++bit)
650 if (mask >> bit & 1)
651 whole[ranked[bit]] = true;
652 fits = fitsWalking(whole, /*weighted=*/true);
653 }
654 if (fits) {
655 fitsMask.set(mask);
656 SmallVector<unsigned> set;
657 for (unsigned bit = 0; bit < n; ++bit)
658 if (mask >> bit & 1)
659 set.push_back(ranked[bit]);
660 result.sets.push_back(std::move(set));
661 result.bytes.push_back(bytes(mask));
662 }
663 }
664 return result;
665}
666
668 ArrayRef<SmallVector<int64_t>> bytes,
669 function_ref<bool(ArrayRef<unsigned>)> places, unsigned maxTries) {
670 using Choice = std::vector<unsigned>;
671 auto total = [&](const Choice &choice) {
672 int64_t sum = 0;
673 for (auto [tile, set] : llvm::enumerate(choice))
674 sum += bytes[tile][set];
675 return sum;
676 };
677 // Each tile's sets come cheapest first, so a choice's successors (one tile
678 // a set further) never cost less: popped in order, the first that places
679 // is the cheapest that does.
680 std::set<std::pair<int64_t, Choice>> frontier;
681 std::set<Choice> seen;
682 Choice first(bytes.size(), 0);
683 frontier.insert({total(first), first});
684 seen.insert(first);
685 WalkChoice result;
686 result.sets.assign(first.begin(), first.end());
687 for (unsigned tries = 0; !frontier.empty(); ++tries) {
688 if (tries == maxTries) {
689 result.stopped = true;
690 return result;
691 }
692 Choice choice = frontier.begin()->second;
693 frontier.erase(frontier.begin());
694 if (places(choice)) {
695 result.sets.assign(choice.begin(), choice.end());
696 result.placed = true;
697 return result;
698 }
699 for (unsigned tile = 0; tile < choice.size(); ++tile) {
700 if (choice[tile] + 1 >= bytes[tile].size())
701 continue;
702 Choice next = choice;
703 ++next[tile];
704 if (seen.insert(next).second)
705 frontier.insert({total(next), next});
706 }
707 }
708 return result;
709}
virtual bool isBdChannelAccessible(int col, int row, uint32_t bd_id, int channel) const =0
Return true iff buffer descriptor bd_id on tile (col, row) can be submitted on channel channel.
virtual uint32_t getNumBDs(AIETileType tileType) const =0
Return the number of buffer descriptors for a given tile type.
virtual uint32_t getNumDestSwitchboxConnections(int col, int row, WireBundle bundle) const =0
Return the number of destinations of connections inside a switchbox.
virtual uint32_t getNumSourceSwitchboxConnections(int col, int row, WireBundle bundle) const =0
Return the number of sources of connections inside a switchbox.
llvm::DenseMap< int, int64_t > at(const AIETargetModel &target, int col, int row, llvm::ArrayRef< mlir::Operation * > tiles={}) const
By channel, the ids held at (col, row) by tiles and by every tile with those coordinates.
llvm::SmallVector< std::pair< int, int > > positions() const
Coordinates of the placed tiles that hold BD ids.
int getDMAChannelIndex(TileLike tile, DMAChannelDir dir, bool requiresAdjacentTileAccessChannels, mlir::Operation *owner=nullptr)
Next free channel of tile in dir, or -1 when the tile has none left.
static std::optional< unsigned > nextPoolToWalk(llvm::ArrayRef< BDPlanEnd > ends, llvm::ArrayRef< unsigned > poolOf, llvm::ArrayRef< BDWalkPool > pools, llvm::ArrayRef< bool > whole)
The walkable pool not yet whole to walk next: the deepest, then the one with the smallest objects,...
mlir::Operation * getDMAChannelOwner(TileLike tile, DMAChannelDir dir, int channel)
Operation reserving or routing this channel; null if none.
bool isChannelFree(TileLike tile, DMAChannelDir dir, int channel)
Whether first-free assignment could hand out channel: nothing reserves it and no explicit flow routes...
static std::optional< llvm::SmallVector< int > > planBDChannels(const AIETargetModel &target, int col, int row, llvm::ArrayRef< BDPlanEnd > ends, llvm::function_ref< bool(DMAChannelDir, int)> free, llvm::function_ref< int64_t(int)> spent)
A channel of the tile at (col, row) for each of ends: its pinned one, else one free leaves that no ot...
static int64_t countBDs(DMAStartOp start)
static llvm::SmallVector< BDGroup > bdGroups(const AIETargetModel &target, int col, int row, int numChannels)
static WalkChoice searchWalkProduct(llvm::ArrayRef< llvm::SmallVector< int64_t > > bytes, llvm::function_ref< bool(llvm::ArrayRef< unsigned >)> places, unsigned maxTries)
Tries the choices of one set per tile, bytes[tile] giving each of its sets' bytes walked whole,...
static llvm::SmallVector< mlir::Block * > chainOf(DMAStartOp start)
Blocks of the BD chain start begins, following next_bd.
static BDWalkSets walkSetsThatFit(const AIETargetModel &target, int col, int row, llvm::ArrayRef< BDPlanEnd > ends, llvm::ArrayRef< unsigned > poolOf, llvm::ArrayRef< BDWalkPool > pools, llvm::function_ref< bool(DMAChannelDir, int)> free, llvm::function_ref< int64_t(int)> spent, unsigned maxSets=std::numeric_limits< unsigned >::max())
Every set of walkable pools whose walk lets planBDChannels fit ends (poolOf gives each end's pool),...
static int getDMAChannelLimit(TileLike tile, DMAChannelDir dir, bool requiresAdjacentTileAccessChannels)
Exclusive upper bound on channel indices eligible for this transfer.
mlir::LogicalResult checkAIEStreamIndex(TileLike tile, DMAChannel chan, mlir::Operation *user, bool packet=false)
Claim a raw stream port for user, reporting on it when the port is taken; packet users may share it w...
int reservePinnedChannel(TileLike tile, DMAChannelDir dir, int channel, mlir::Operation *owner=nullptr, bool shareable=false)
Claim channel for (tile, dir) so first-free assignment cannot take it.
void forEachRuntimePinnedBdId(AIE::DeviceOp device, llvm::function_ref< void(Operation *op, Operation *tile, std::optional< int > channel, int32_t id)> pinned)
Definition AIEUtils.cpp:599
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
const AIETargetModel & getTargetModel(mlir::Operation *op)
struct DMAChannel { DMAChannelDir direction; int channel; bool operator==(const DMAChannel &rhs) const { return std::tie(direction, channel)==std::tie(rhs.direction, rhs.channel); } } DMAChannel
Definition AIEDialect.h:314
Channels among 0..numChannels-1 at (col, row), grouped by whichever BD ids any two in a group share,...
A DMA end of one tile: its direction, the BD ids it takes, the exclusive upper bound on the channels ...
A pool whose ends a BD plan weighs: how many objects it holds, the bytes of one, and whether it can b...
walkSetsThatFit's result; channelShort when the ends do not fit the tile's channels even taking no BD...
llvm::SmallVector< int64_t > bytes
The bytes each set walks whole.
llvm::SmallVector< llvm::SmallVector< unsigned > > sets
One walkSetsThatFit set per mem tile of a spill component (memTileSpillComponents),...