MLIR-AIE 1.4.6.dev
AIEShimSharing.cpp
Go to the documentation of this file.
1//===- AIEShimSharing.cpp ---------------------------------------*- C++ -*-===//
2//
3// Copyright (C) 2026 Advanced Micro Devices, Inc.
4// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
5//
6//===----------------------------------------------------------------------===//
7
12
13#include "mlir/IR/Matchers.h"
14#include "mlir/Interfaces/LoopLikeInterface.h"
15#include "llvm/ADT/STLExtras.h"
16#include "llvm/Support/CheckedArithmetic.h"
17
18#include <tuple>
19
20using namespace mlir;
21using namespace xilinx;
22using namespace xilinx::AIE;
23
24namespace xilinx::AIE {
25#define GEN_PASS_DEF_AIEANNOTATESHIMSHARING
26#include "aie/Dialect/AIE/Transforms/AIEPasses.h.inc"
27} // namespace xilinx::AIE
28
30 DeviceOp device, function_ref<std::optional<End>(StringAttr)> endOf,
31 std::optional<Gates> gates, bool plannedOverlay)
32 : gates(std::move(gates)), context(device.getContext()),
33 overlayColumns(plannedOverlay ? device.getTargetModel().columns() : 0) {
34 auto inDevice = [&](DeviceOp owner, StringAttr symbol) {
35 return owner == device ? endOf(symbol) : std::nullopt;
36 };
37 for (int column = 0; column < overlayColumns; ++column)
38 used.insert(overlayEnd(column));
39 analyze(device, inDevice);
40 if (this->gates)
41 analyzeGates(device, inDevice);
42}
43
45 ModuleOp module,
46 function_ref<std::optional<End>(DeviceOp, StringAttr)> endOf,
47 std::optional<Gates> gates)
48 : gates(std::move(gates)), context(module.getContext()) {
49 analyze(module, endOf);
50 if (this->gates)
51 analyzeGates(module, endOf);
52}
53
54void ShimTransferSpans::analyze(
55 Operation *root,
56 function_ref<std::optional<End>(DeviceOp, StringAttr)> endOf) {
57 struct Span {
58 StringAttr endpoint;
59 int64_t first, last;
60 };
61 struct Summary {
62 SmallVector<Span> spans;
63 int64_t duration = 0;
64 };
65 DenseMap<Operation *, Summary> summaries;
66 DenseSet<Operation *> active;
67 NamedOpTableCollection names;
68 std::function<Summary(RuntimeSequenceOp)> summarize =
69 [&](RuntimeSequenceOp sequence) -> Summary {
70 if (active.contains(sequence)) {
71 unknown = true;
72 return {};
73 }
74 if (auto found = summaries.find(sequence); found != summaries.end())
75 return found->second;
76 active.insert(sequence);
77 DeviceOp device = sequence->getParentOfType<DeviceOp>();
78 Summary result;
79 DenseMap<Operation *, int64_t> position, end;
80 std::function<void(Operation *)> number = [&](Operation *op) {
81 position[op] = result.duration++;
82 if (auto run = dyn_cast<AIEX::RunOp>(op)) {
83 if (auto callee = run.getCalleeRuntimeSequenceOp(&names))
84 result.duration += summarize(callee).duration;
85 else
86 unknown = true;
87 }
88 for (Region &region : op->getRegions())
89 for (Block &block : region)
90 for (Operation &nested : block)
91 number(&nested);
92 end[op] = result.duration++;
93 };
94 number(sequence);
95 auto interval = [&](Operation *op, int64_t from, int64_t to) {
96 for (Operation *parent = op->getParentOp(); parent != sequence;
97 parent = parent->getParentOp())
98 if (isa<LoopLikeOpInterface>(parent)) {
99 from = position[parent];
100 to = end[parent];
101 }
102 return std::make_pair(from, to);
103 };
104 // Completion names a specific start, so a callee cannot retire caller work.
105 auto note = [&](StringAttr endpoint, int64_t at,
106 std::optional<size_t> completion = std::nullopt) {
107 if (completion) {
108 result.spans[*completion].last = at;
109 return *completion;
110 }
111 used.insert(endpoint);
112 result.spans.push_back({endpoint, at, end[sequence]});
113 return result.spans.size() - 1;
114 };
115 DenseMap<StringAttr, SmallVector<size_t>> pending;
116 DenseMap<Value, StringAttr> tasks;
117 DenseMap<size_t, Value> owners;
118 auto transfer = [&](Operation *op, StringAttr symbol, bool starts,
119 bool all = false, Value owner = {}) {
120 auto endpoint = endOf(device, symbol);
121 if (!endpoint)
122 return;
123 auto [from, to] = interval(op, position[op], position[op]);
124 auto &queue = pending[symbol];
125 if (starts) {
126 size_t start = note(endpoint->fifo, from);
127 owners[start] = owner;
128 queue.push_back(start);
129 } else if (!endpoint->sends) {
130 for (auto it = queue.begin(); it != queue.end();) {
131 if (owner && owners.lookup(*it) != owner) {
132 ++it;
133 continue;
134 }
135 note(endpoint->fifo, to, *it);
136 it = queue.erase(it);
137 if (!all)
138 break;
139 }
140 }
141 };
142 auto synchronous = [&](Operation *op, StringAttr endpoint, int64_t from,
143 int64_t to) {
144 std::tie(from, to) = interval(op, from, to);
145 auto start = note(endpoint, from);
146 note(endpoint, to, start);
147 };
148 auto configuration = [&](Operation *op, DeviceOp configured,
149 std::optional<int> column = {}) {
150 if (!configured)
151 return;
152 for (int planned = 0; planned < overlayColumns; ++planned)
153 if (!column || planned == *column)
154 synchronous(op, overlayEnd(planned), position[op], position[op]);
155 for (auto alloc : configured.getOps<ShimDMAAllocationOp>()) {
156 if (!AIEDialect::IsCtrlPktOverlayAttrHelper(root->getContext())
157 .isAttrPresent(alloc) ||
158 (column && alloc.getTileOp().colIndex() != *column))
159 continue;
160 if (auto endpoint = endOf(configured, alloc.getSymNameAttr()))
161 synchronous(op, endpoint->fifo, position[op], position[op]);
162 }
163 };
164 sequence.walk<WalkOrder::PreOrder>([&](Operation *op) {
165 if (auto run = dyn_cast<AIEX::RunOp>(op)) {
166 if (auto callee = run.getCalleeRuntimeSequenceOp(&names))
167 for (const Span &span : summarize(callee).spans)
168 synchronous(op, span.endpoint, position[op] + 1 + span.first,
169 position[op] + 1 + span.last);
170 } else if (auto configure = dyn_cast<AIEX::ConfigureOp>(op)) {
171 configuration(op, configure.getReferencedDeviceOp());
172 } else if (isa<AIEX::NpuLoadPdiOp, AIEX::NpuWriteConfigOp,
173 AIEX::NpuWriteTeardownOp>(op)) {
174 if (isa<AIEX::NpuLoadPdiOp>(op) && op->getParentOp() == sequence) {
175 for (auto &[symbol, queue] : pending) {
176 for (size_t start : queue)
177 note(result.spans[start].endpoint, position[op] - 1, start);
178 queue.clear();
179 }
180 }
181 auto ref = op->getAttrOfType<FlatSymbolRefAttr>("device_ref");
182 configuration(
183 op, ref ? SymbolTable::lookupNearestSymbolFrom<DeviceOp>(op, ref)
184 : device);
185 } else if (auto packet = dyn_cast<AIEX::NpuControlPacketOp>(op)) {
186 configuration(op, device, packet.getColumnFromAddr());
187 } else if (auto sync = dyn_cast<AIEX::NpuSyncOp>(op)) {
188 SmallVector<int> values;
189 for (Value operand : sync->getOperands()) {
190 APInt value;
191 if (!matchPattern(operand, m_ConstantInt(&value)))
192 return;
193 values.push_back(value.getSExtValue());
194 }
195 if (values[4] != 1 || values[5] != 1)
196 return;
197 StringAttr symbol;
198 size_t first = std::numeric_limits<size_t>::max();
199 for (const auto &[name, queue] : pending) {
200 if (queue.empty() || queue.front() >= first)
201 continue;
202 Operation *owner = device.lookupSymbol(name);
203 TileOp tile;
204 std::optional<int> channel;
205 DMAChannelDir direction;
206 if (auto alloc = dyn_cast_or_null<ShimDMAAllocationOp>(owner)) {
207 tile = alloc.getTileOp();
208 channel = alloc.getChannelIndex();
209 direction = alloc.getChannelDir();
210 } else if (auto endpoint = dyn_cast_or_null<RouteEndpointOp>(owner)) {
211 tile = endpoint.getTile().getDefiningOp<TileOp>();
212 channel = endpoint.getChannelIndex();
213 direction = endpoint.getRouteDirection();
214 }
215 if (tile && channel && tile.colIndex() == values[0] &&
216 tile.rowIndex() == values[1] &&
217 static_cast<int>(direction) == values[2] &&
218 *channel == values[3]) {
219 first = queue.front();
220 symbol = name;
221 }
222 }
223 if (symbol)
224 transfer(op, symbol, false);
225 } else if (auto memcpy = dyn_cast<AIEX::NpuDmaMemcpyNdOp>(op)) {
226 transfer(op, memcpy.getMetadata().getRootReference(), true);
227 } else if (auto wait = dyn_cast<AIEX::NpuDmaWaitOp>(op)) {
228 transfer(op, wait.getSymbolAttr().getAttr(), false, true);
229 } else if (auto configure = dyn_cast<AIEX::DMAConfigureTaskForOp>(op)) {
230 tasks[configure.getResult()] = configure.getAlloc().getRootReference();
231 } else if (auto chain = dyn_cast<AIEX::DMAStartBdChainForOp>(op)) {
232 StringAttr symbol = chain.getAllocAttr().getAttr();
233 tasks[chain.getResult()] = symbol;
234 transfer(op, symbol, true, false, chain.getResult());
235 } else if (isa<AIEX::DMAStartTaskOp, AIEX::DMAAwaitTaskOp,
236 AIEX::DMAFreeTaskOp>(op)) {
237 if (auto symbol = tasks.lookup(op->getOperand(0)))
238 transfer(op, symbol, isa<AIEX::DMAStartTaskOp>(op),
239 isa<AIEX::DMAFreeTaskOp>(op),
240 isa<AIEX::DMAAwaitTaskOp>(op) ? Value{} : op->getOperand(0));
241 }
242 });
243 llvm::stable_sort(result.spans, [](const Span &a, const Span &b) {
244 return a.first < b.first;
245 });
246 DenseMap<StringAttr, int64_t> live;
247 for (const Span &span : result.spans) {
248 lifetimes[span.endpoint].emplace_back(summaries.size(), span.first,
249 span.last);
250 for (const auto &[other, last] : live) {
251 if (last < span.first)
252 continue;
253 overlaps.insert({span.endpoint, other});
254 overlaps.insert({other, span.endpoint});
255 }
256 live[span.endpoint] = std::max(live.lookup(span.endpoint), span.last);
257 }
258 active.erase(sequence);
259 summaries[sequence] = result;
260 return result;
261 };
262 root->walk([&](Operation *op) {
263 if (!isa<ObjectFifoCreateOp, RouteEndpointOp, ShimDMAAllocationOp>(op))
264 return;
265 DeviceOp device = op->getParentOfType<DeviceOp>();
266 auto endpoint = endOf(device, SymbolTable::getSymbolName(op));
267 if (!endpoint)
268 return;
269 bool sends = endpoint->sends;
270 if (auto alloc = dyn_cast<ShimDMAAllocationOp>(op)) {
271 sends = alloc.getChannelDir() == DMAChannelDir::MM2S;
272 used.insert(endpoint->fifo);
273 } else if (auto allowed =
274 AIEDialect::ShareableWithAttrHelper(op->getContext())
275 .getAttr(op)) {
276 auto &peers = permissions[endpoint->fifo];
277 for (Attribute attr : allowed)
278 if (auto ref = dyn_cast<FlatSymbolRefAttr>(attr))
279 if (auto other = endOf(device, ref.getAttr()))
280 peers.push_back(other->fifo);
281 }
282 if (auto fifo = dyn_cast<ObjectFifoCreateOp>(op))
283 if (llvm::any_of(fifo.getConsumerTiles(), [](Value tile) {
284 return cast<TileLike>(tile.getDefiningOp()).isShimTile();
285 }))
286 sends = false;
287 // Receive ordering does not constrain when independent producers send.
288 if (!sends)
289 receivers.insert(endpoint->fifo);
290 });
291 root->walk([&](RuntimeSequenceOp sequence) { summarize(sequence); });
292}
293
294void ShimTransferSpans::analyzeGates(
295 Operation *root,
296 function_ref<std::optional<End>(DeviceOp, StringAttr)> endOf) {
297 root->walk([&](RuntimeSequenceOp sequence) {
298 DeviceOp device = sequence->getParentOfType<DeviceOp>();
299 DenseMap<Operation *, int64_t> position, end;
300 int64_t next = 0;
301 std::function<void(Operation *)> number = [&](Operation *op) {
302 position[op] = next++;
303 for (Region &region : op->getRegions())
304 for (Block &block : region)
305 for (Operation &nested : block)
306 number(&nested);
307 end[op] = next - 1;
308 };
309 number(sequence);
310
311 auto &byFifo = spans.emplace_back();
312 DenseMap<Value, StringAttr> tasks;
313 DenseMap<Value, bool> tokens;
314 DenseMap<StringAttr, std::optional<int64_t>> moved;
315 // An end's transfers not yet awaited, over the loops around them: nullopt
316 // once one is issued that no await can take (no completion token, under a
317 // branch, or in a loop of unknown trips). An await under a branch, or in a
318 // loop that may not run, takes nothing; an issue there still spans the
319 // whole branch or loop.
320 DenseMap<StringAttr, std::optional<int64_t>> pending;
321 auto note = [&](Operation *op, StringAttr symbol, bool issues, bool awaits,
322 bool tokened = false) {
323 std::optional<End> shimEnd = endOf(device, symbol);
324 if (!shimEnd)
325 return;
326 int64_t from = position[op], to = position[op];
327 for (Operation *parent = op->getParentOp(); parent != sequence;
328 parent = parent->getParentOp()) {
329 from = position[parent];
330 to = end[parent];
331 }
332 // A loop that may not run leaves an issue or await unconfirmed, the
333 // same as an unknown trip count.
334 std::optional<int64_t> runs = AIEX::staticExecutions(op);
335 if (runs == 0)
336 runs = std::nullopt;
337 Span &span = byFifo[shimEnd->fifo];
338 span.sends |= shimEnd->sends;
339 span.first = std::min(span.first, from);
340 span.last = std::max(span.last, to);
341 std::optional<int64_t> &waiting =
342 pending.try_emplace(shimEnd->fifo, 0).first->second;
343 if (issues) {
344 span.lastIssue = std::max(span.lastIssue, to);
345 waiting = waiting && runs && tokened ? llvm::checkedAdd(*waiting, *runs)
346 : std::nullopt;
347 } else if (runs) {
348 span.lastDone = std::max(span.lastDone, to);
349 if (awaits && waiting) {
350 waiting = std::max<int64_t>(*waiting - *runs, 0);
351 if (*waiting == 0)
352 span.lastAwaited = std::max(span.lastAwaited, to);
353 }
354 }
355 };
356 auto noteTask = [&](Operation *op, Value task, bool issues, bool awaits) {
357 if (StringAttr symbol = tasks.lookup(task))
358 note(op, symbol, issues, awaits, tokens.lookup(task));
359 };
360 // Adds the bytes `op` moves each time it runs, times the trip counts of
361 // the loops around it, to its end's total; nullopt where any is unknown.
362 auto count = [&](Operation *op, StringAttr symbol,
363 std::optional<int64_t> bytes) {
364 std::optional<End> shimEnd = endOf(device, symbol);
365 if (!shimEnd)
366 return;
367 std::optional<int64_t> runs = AIEX::staticExecutions(op);
368 bytes = bytes && runs ? llvm::checkedMul(*bytes, *runs) : std::nullopt;
369 std::optional<int64_t> &total =
370 moved.try_emplace(shimEnd->fifo, 0).first->second;
371 total = total && bytes ? llvm::checkedAdd(*total, *bytes) : std::nullopt;
372 };
373 sequence.walk([&](Operation *op) {
374 if (auto memcpy = dyn_cast<AIEX::NpuDmaMemcpyNdOp>(op)) {
375 StringAttr symbol = memcpy.getMetadata().getRootReference();
376 note(op, symbol, true, false, memcpy.getIssueToken());
377 count(op, symbol, memcpy.getStaticBytesStreamed());
378 } else if (auto wait = dyn_cast<AIEX::NpuDmaWaitOp>(op))
379 note(op, wait.getSymbolAttr().getAttr(), false, true);
380 else if (auto configure = dyn_cast<AIEX::DMAConfigureTaskForOp>(op)) {
381 StringAttr symbol = configure.getAlloc().getRootReference();
382 tasks[configure.getResult()] = symbol;
383 tokens[configure.getResult()] = configure.getIssueToken();
384 count(op, symbol, configure.getStaticBytesStreamed());
385 } else if (auto chain = dyn_cast<AIEX::DMAStartBdChainForOp>(op)) {
386 tasks[chain.getResult()] = chain.getAllocAttr().getAttr();
387 tokens[chain.getResult()] = chain.getIssueToken();
388 note(op, chain.getAllocAttr().getAttr(), true, false,
389 chain.getIssueToken());
390 count(op, chain.getAllocAttr().getAttr(), std::nullopt);
391 } else if (auto start = dyn_cast<AIEX::DMAStartTaskOp>(op))
392 noteTask(op, start.getTask(), true, false);
393 else if (auto await = dyn_cast<AIEX::DMAAwaitTaskOp>(op))
394 noteTask(op, await.getTask(), false, true);
395 // Freeing a task lets its BD ids be reused, which is only safe once its
396 // transfers are done.
397 else if (auto free = dyn_cast<AIEX::DMAFreeTaskOp>(op))
398 noteTask(op, free.getTask(), false, false);
399 });
400 for (auto &[fifo, bytes] : moved)
401 if (auto it = byFifo.find(fifo); it != byFifo.end())
402 it->second.bytes = bytes;
403 });
404}
405
406SmallVector<const ShimTransferSpans::Gate *>
407ShimTransferSpans::usableGates(StringAttr end) const {
408 if (auto it = usableGatesCache.find(end); it != usableGatesCache.end())
409 return it->second;
410 bool receives = llvm::any_of(spans, [&](const auto &byFifo) {
411 auto it = byFifo.find(end);
412 return it != byFifo.end() && !it->second.sends;
413 });
414 SmallVector<const Gate *> usable;
415 if (!gates || !receives) {
416 usable.push_back(nullptr);
417 } else if (auto it = gates->find(end); it != gates->end()) {
418 for (const Gate &gate : it->second)
419 if (contained(end, gate))
420 usable.push_back(&gate);
421 }
422 return usableGatesCache[end] = usable;
423}
424
425bool ShimTransferSpans::before(const DenseMap<StringAttr, Span> &byFifo,
426 const Span &x, const Span &y,
427 const Gate *gate) const {
428 if (x.sends || x.last >= y.first || x.lastDone <= x.lastIssue)
429 return false;
430 if (!gate)
431 return true;
432 auto input = byFifo.find(gate->input);
433 return x.lastAwaited > x.lastIssue && input != byFifo.end() &&
434 input->second.first > x.lastAwaited;
435}
436
437bool ShimTransferSpans::contained(StringAttr end, const Gate &gate) const {
438 return llvm::all_of(spans, [&](const DenseMap<StringAttr, Span> &byFifo) {
439 auto in = byFifo.find(gate.input), out = byFifo.find(end);
440 if (out == byFifo.end())
441 return in == byFifo.end();
442 const Span &drain = out->second;
443 std::optional<int64_t> filled = in == byFifo.end() ? 0 : in->second.bytes;
444 if (!filled || !drain.bytes || drain.lastAwaited <= drain.lastIssue)
445 return false;
446 return AIEX::balanceUnder(gate.proof, {{-1, *filled}},
447 {{-1, *drain.bytes}}) == AIEX::Unbalanced::No;
448 });
449}
450
451bool ShimTransferSpans::gated(StringAttr a, StringAttr b) const {
452 if (!gates || unknown || overlaps.contains({a, b}))
453 return false;
454 // An end no sequence names is driven some other way, so nothing is known
455 // about when it is in flight.
456 auto named = [&](StringAttr end) {
457 if (auto it = namedCache.find(end); it != namedCache.end())
458 return it->second;
459 bool result = llvm::any_of(
460 spans, [&](const auto &byFifo) { return byFifo.contains(end); });
461 return namedCache[end] = result;
462 };
463 for (StringAttr end : {a, b})
464 if (!named(end))
465 return false;
466 // One gate per end serves every sequence, for its fill bound and its turn.
467 for (const Gate *ga : usableGates(a))
468 for (const Gate *gb : usableGates(b))
469 if (llvm::all_of(spans, [&](const DenseMap<StringAttr, Span> &byFifo) {
470 auto sa = byFifo.find(a), sb = byFifo.find(b);
471 return sa == byFifo.end() || sb == byFifo.end() ||
472 before(byFifo, sa->second, sb->second, gb) ||
473 before(byFifo, sb->second, sa->second, ga);
474 }))
475 return true;
476 return false;
477}
478
479StringAttr ShimTransferSpans::keyOf(RouteEndpointOp endpoint) {
480 return endpoint.getFifoNameAttr() ? endpoint.getFifoNameAttr()
481 : endpoint.getSymNameAttr();
482}
483
484std::optional<ShimTransferSpans::End>
485ShimTransferSpans::endOf(DeviceOp device, StringAttr symbol) {
486 Operation *op = SymbolTable::lookupNearestSymbolFrom(device, symbol);
487 if (auto endpoint = dyn_cast_or_null<RouteEndpointOp>(op)) {
488 if (endpoint.getBundle() != WireBundle::DMA ||
489 !endpoint.getTileLike().isShimTile())
490 return std::nullopt;
491 return End{keyOf(endpoint),
492 endpoint.getRouteDirection() == DMAChannelDir::MM2S};
493 }
494 auto fifo = dyn_cast_or_null<ObjectFifoCreateOp>(op);
495 if (!fifo)
496 return std::nullopt;
497 auto producer =
498 dyn_cast_or_null<TileLike>(fifo.getProducerTile().getDefiningOp());
499 return End{symbol, producer && producer.isShimTile()};
500}
501
503 DeviceOp device, function_ref<StringAttr(RouteEndpointOp)> keyOf) {
504 Gates gates;
505 for (auto input : device.getOps<RouteEndpointOp>()) {
506 StringAttr inputKey = input.getConsumedBy() ? keyOf(input) : StringAttr();
507 if (!inputKey)
508 continue;
509 for (auto proof : input.getConsumedByAttr().getAsRange<ConsumedByAttr>()) {
510 auto output = SymbolTable::lookupNearestSymbolFrom<RouteEndpointOp>(
511 device, proof.getOutput());
512 if (StringAttr outputKey = output ? keyOf(output) : StringAttr())
513 gates[outputKey].push_back({inputKey, proof});
514 }
515 }
516 return gates;
517}
518
519bool ShimTransferSpans::isUsed(StringAttr endpoint) const {
520 return used.contains(endpoint);
521}
522
523StringAttr ShimTransferSpans::overlayEnd(int column) const {
524 // Typed, so no symbol name (an untyped StringAttr) is ever this end.
525 return StringAttr::get("ctrlpkt_col" + Twine(column),
526 IndexType::get(context));
527}
528
529bool ShimTransferSpans::apart(StringAttr a, StringAttr b) const {
530 // gated is symmetric, so one call answers for both directions whenever
531 // both ends reach it.
532 std::optional<bool> symmetric;
533 auto permits = [&](StringAttr from, StringAttr to) {
534 if (auto it = permissions.find(from); it != permissions.end())
535 return llvm::is_contained(it->second, to);
536 if (receivers.contains(from)) {
537 if (!symmetric)
538 symmetric = gated(from, to);
539 return *symmetric;
540 }
541 return !unknown && isUsed(from) && isUsed(to) &&
542 !overlaps.contains({from, to});
543 };
544 return a != b && permits(a, b) && permits(b, a);
545}
546
547SmallVector<SmallVector<unsigned>>
548ShimTransferSpans::groups(ArrayRef<StringAttr> ends) const {
549 static const SmallVector<std::tuple<unsigned, int64_t, int64_t>> kNoLifetime;
550 auto when = llvm::map_to_vector(ends, [&](StringAttr end) {
551 auto it = lifetimes.find(end);
552 return it == lifetimes.end() ? &kNoLifetime : &it->second;
553 });
554 auto order = llvm::to_vector(llvm::seq<unsigned>(0, ends.size()));
555 llvm::stable_sort(
556 order, [&](unsigned x, unsigned y) { return *when[x] < *when[y]; });
557 SmallVector<SmallVector<unsigned>> result;
558 for (unsigned end : order) {
559 auto *group = llvm::find_if(result, [&](ArrayRef<unsigned> members) {
560 return llvm::all_of(
561 members, [&](unsigned m) { return apart(ends[m], ends[end]); });
562 });
563 if (group == result.end())
564 result.push_back({end});
565 else
566 group->push_back(end);
567 }
568 return result;
569}
570
572ShimTransferSpans::plan(ArrayRef<StringAttr> ends, ArrayRef<StringAttr> names,
573 ArrayRef<SharedChannel> shared) const {
574 Plan result;
575 result.sharedChannel.assign(ends.size(), std::nullopt);
576 for (auto [index, channel] : llvm::enumerate(shared)) {
577 if (channel.pinned)
578 continue;
579 SmallVector<unsigned> taken;
580 for (unsigned end : llvm::seq<unsigned>(0, ends.size()))
581 if (!result.sharedChannel[end] &&
582 llvm::is_contained(channel.listed, names[end]) &&
583 llvm::all_of(taken, [&](unsigned other) {
584 return apart(ends[end], ends[other]);
585 })) {
586 result.sharedChannel[end] = index;
587 taken.push_back(end);
588 }
589 }
590 SmallVector<unsigned> rest;
591 SmallVector<StringAttr> restEnds;
592 for (unsigned end : llvm::seq<unsigned>(0, ends.size()))
593 if (!result.sharedChannel[end]) {
594 rest.push_back(end);
595 restEnds.push_back(ends[end]);
596 }
597 for (auto &group : groups(restEnds)) {
598 auto &members = result.groups.emplace_back();
599 for (unsigned member : group)
600 members.push_back(rest[member]);
601 }
602 return result;
603}
604
605namespace {
606struct AIEAnnotateShimSharingPass
607 : xilinx::AIE::impl::AIEAnnotateShimSharingBase<
608 AIEAnnotateShimSharingPass> {
609 void runOnOperation() override {
610 ModuleOp module = getOperation();
611 AIEDialect::IsCtrlPktOverlayAttrHelper overlay(&getContext());
612 AIEDialect::ShareableWithAttrHelper sharing(&getContext());
613 DenseMap<Operation *, StringAttr> keys;
614 auto key = [&](Operation *op) {
615 auto [it, inserted] = keys.try_emplace(op);
616 if (inserted)
617 it->second =
618 StringAttr::get(&getContext(), std::to_string(keys.size()));
619 return it->second;
620 };
622 for (DeviceOp device : module.getOps<DeviceOp>())
623 for (auto &[output, proven] : ShimTransferSpans::provenGates(
624 device, [&](RouteEndpointOp endpoint) {
625 return endpoint.getBundle() == WireBundle::DMA &&
626 endpoint.getTileLike().isShimTile()
627 ? key(endpoint)
628 : StringAttr();
629 }))
630 llvm::append_range(gates[output], proven);
631 ShimTransferSpans spans(
632 module,
633 [&](DeviceOp device,
634 StringAttr symbol) -> std::optional<ShimTransferSpans::End> {
635 Operation *op = device.lookupSymbol(symbol);
636 if (auto endpoint = dyn_cast_or_null<RouteEndpointOp>(op)) {
637 if (endpoint.getBundle() != WireBundle::DMA ||
638 !endpoint.getTileLike().isShimTile())
639 return std::nullopt;
640 return ShimTransferSpans::End{key(endpoint),
641 endpoint.getRouteDirection() ==
642 DMAChannelDir::MM2S};
643 }
644 auto alloc = dyn_cast_or_null<ShimDMAAllocationOp>(op);
645 if (!alloc)
646 return std::nullopt;
647 if (overlay.isAttrPresent(alloc)) {
648 if (auto ref = device.getOverlayAttr())
649 if (auto definition =
650 module.lookupSymbol<DeviceOp>(ref.getValue()))
651 if (Operation *original = definition.lookupSymbol(symbol))
652 op = original;
653 return ShimTransferSpans::End{key(op), false};
654 }
655 return ShimTransferSpans::End{key(op), alloc.getChannelDir() ==
656 DMAChannelDir::MM2S};
657 },
658 std::move(gates));
659 for (DeviceOp device : module.getOps<DeviceOp>()) {
660 auto annotate = [&](Operation *op, Value tile, DMAChannelDir direction,
661 StringAttr identity) {
662 if (sharing.isAttrPresent(op))
663 return;
664 SmallVector<Attribute> allowed;
665 for (auto other : device.getOps<RouteEndpointOp>())
666 if (other != op && other.getBundle() == WireBundle::DMA &&
667 other.getTile() == tile &&
668 other.getRouteDirection() == direction &&
669 spans.apart(identity, keys.lookup(other)))
670 allowed.push_back(FlatSymbolRefAttr::get(other.getSymNameAttr()));
671 sharing.setAttr(op, ArrayAttr::get(&getContext(), allowed));
672 };
673 for (auto endpoint : device.getOps<RouteEndpointOp>())
674 if (endpoint.getBundle() == WireBundle::DMA &&
675 endpoint.getTileLike().isShimTile())
676 annotate(endpoint, endpoint.getTile(), endpoint.getRouteDirection(),
677 keys.lookup(endpoint));
678 for (auto alloc : device.getOps<ShimDMAAllocationOp>())
679 if (overlay.isAttrPresent(alloc)) {
680 Operation *original = alloc;
681 if (auto ref = device.getOverlayAttr())
682 if (auto definition = module.lookupSymbol<DeviceOp>(ref.getValue()))
683 if (Operation *source =
684 definition.lookupSymbol(alloc.getSymName()))
685 original = source;
686 annotate(alloc, alloc.getTile(), alloc.getChannelDir(),
687 keys.lookup(original));
688 }
689 }
690 }
691};
692} // namespace
693
694std::unique_ptr<OperationPass<ModuleOp>>
696 return std::make_unique<AIEAnnotateShimSharingPass>();
697}
Shim endpoint lifetimes, including calls to self-contained runtime sequences.
std::optional< int64_t > bytes(unsigned seq, mlir::StringAttr end) const
The bytes runtime sequence seq moves through end, nullopt when not static or when end is not one of i...
llvm::DenseMap< mlir::StringAttr, llvm::SmallVector< Gate > > Gates
Plan plan(llvm::ArrayRef< mlir::StringAttr > ends, llvm::ArrayRef< mlir::StringAttr > names, llvm::ArrayRef< SharedChannel > shared) const
Plans ends (keyed as apart() takes keys); names[i] is how shared's lists name ends[i].
bool isUsed(mlir::StringAttr end) const
bool names(unsigned seq, mlir::StringAttr end) const
Whether runtime sequence seq transfers through end at all, static or not; bytes alone cannot tell a d...
bool apart(mlir::StringAttr a, mlir::StringAttr b) const
Whether both ends permit sharing: explicitly, by MM2S lifetime analysis, or, for a receiving end,...
static std::optional< End > endOf(DeviceOp device, mlir::StringAttr symbol)
The end a runtime sequence of device transfers through when it names symbol: a shim DMA route end,...
static mlir::StringAttr keyOf(RouteEndpointOp endpoint)
How ends and gates name a shim route end: by its objectFIFO, else by its own symbol.
mlir::StringAttr overlayEnd(int column) const
The planned control overlay channel's end on column column's shim tile.
llvm::SmallVector< llvm::SmallVector< unsigned > > groups(llvm::ArrayRef< mlir::StringAttr > ends) const
Splits ends into groups whose members are pairwise apart, each group taking one channel: first fit,...
ShimTransferSpans(DeviceOp device, llvm::function_ref< std::optional< End >(mlir::StringAttr)> endOf, std::optional< Gates > gates=std::nullopt, bool plannedOverlay=false)
endOf maps a symbol a runtime sequence transfers through to the objectFIFO end it belongs to,...
static Gates provenGates(DeviceOp device, llvm::function_ref< mlir::StringAttr(RouteEndpointOp)> keyOf)
Each receiving end's gates, keyed by keyOf: the shim inputs whose consumption its progress proves,...
std::optional< int64_t > staticExecutions(Operation *op)
Definition AIEUtils.cpp:329
Unbalanced balanceUnder(AIE::ConsumedByAttr proof, const Volume &in, const Volume &out)
Definition AIEUtils.cpp:377
const AIETargetModel & getTargetModel(mlir::Operation *op)
std::unique_ptr< mlir::OperationPass< mlir::ModuleOp > > createAIEAnnotateShimSharingPass()
A shim end a runtime sequence transfers through.
A shim input gating a receiving end's senders, per its #aie.consumed_by.
How one shim tile's unpinned ends in one direction share channels, as objectFIFO allocation shares th...
llvm::SmallVector< llvm::SmallVector< unsigned > > groups
The other ends, in groups taking one channel each.
llvm::SmallVector< std::optional< unsigned > > sharedChannel
Per end, the index of the shared channel it takes, if any.