MLIR-AIE 1.4.6.dev
AIEStreamDependencyAnalysis.cpp
Go to the documentation of this file.
1//===- AIEStreamDependencyAnalysis.cpp --------------------------*- C++ -*-===//
2//
3// Copyright (C) 2026 Advanced Micro Devices, Inc.
4// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
5//
6//===----------------------------------------------------------------------===//
7
11
12#include "mlir/Dialect/Utils/StaticValueUtils.h"
13#include "mlir/IR/Matchers.h"
14#include "mlir/Interfaces/ControlFlowInterfaces.h"
15#include "mlir/Interfaces/LoopLikeInterface.h"
16
17#include "llvm/ADT/DenseSet.h"
18#include "llvm/ADT/GraphTraits.h"
19#include "llvm/ADT/SCCIterator.h"
20#include "llvm/ADT/STLExtras.h"
21#include "llvm/ADT/ScopeExit.h"
22#include "llvm/ADT/SetVector.h"
23#include "llvm/ADT/SparseBitVector.h"
24#include "llvm/Support/Debug.h"
25#include "llvm/Support/FormatVariadic.h"
26
27#include <algorithm>
28#include <deque>
29#include <set>
30#include <variant>
31
32#define DEBUG_TYPE "aie-stream-dependency"
33
34using namespace mlir;
35using namespace xilinx;
36using namespace xilinx::AIE;
37
38namespace {
39
40std::optional<TileID> tileOf(Value tile) {
41 if (auto tileOp = dyn_cast_or_null<TileOp>(tile.getDefiningOp()))
42 return tileOp.getTileID();
43 return std::nullopt;
44}
45
46std::optional<DmaChannelProgram> makeProgram(Operation *op, DeviceOp device) {
47 auto parentTile = [](Operation *op) -> std::optional<TileID> {
48 if (auto element = op->getParentOfType<TileElement>())
49 return tileOf(element.getTile());
50 return std::nullopt;
51 };
52 if (auto start = dyn_cast<DMAStartOp>(op)) {
53 std::optional<TileID> tile = parentTile(op);
54 if (!tile)
55 return std::nullopt;
57 op, {*tile, start.getChannelDir(), start.getChannelIndex()}};
58 p.passes += start.getRepeatCount();
59 llvm::SmallPtrSet<Block *, 8> seen;
60 for (Block *b = start.getDest(); b;) {
61 if (!seen.insert(b).second) {
62 p.loops = true;
63 p.loopStart = llvm::find(p.bds, b) - p.bds.begin();
64 break;
65 }
66 p.bds.push_back(b);
67 auto next = dyn_cast<NextBDOp>(b->getTerminator());
68 b = next ? next.getDest() : nullptr;
69 }
70 return p;
71 }
72 if (auto dma = dyn_cast<DMAOp>(op)) {
73 std::optional<TileID> tile = parentTile(op);
74 if (!tile)
75 return std::nullopt;
77 {*tile, dma.getChannelDir(), dma.getChannelIndex()}};
78 p.passes += dma.getRepeatCount();
79 for (Region &r : dma.getBds())
80 p.regions.push_back(&r);
81 p.loops = dma.getLoop();
82 return p;
83 }
84 if (auto task = dyn_cast<AIEX::DMAConfigureTaskOp>(op)) {
85 std::optional<TileID> tile = tileOf(task.getTile());
86 if (!tile)
87 return std::nullopt;
89 op, {*tile, task.getDirection(), static_cast<int>(task.getChannel())}};
90 p.regions.push_back(&task.getBody());
91 p.passes += task.getRepeatCount();
92 return p;
93 }
94 if (auto task = dyn_cast<AIEX::DMAConfigureTaskForOp>(op)) {
95 auto alloc = ShimDMAAllocationOp::getForSymbol(
96 device, task.getAlloc().getRootReference());
97 if (!alloc)
98 return std::nullopt;
99 std::optional<TileID> tile = tileOf(alloc.getTile());
100 if (!tile)
101 return std::nullopt;
103 {*tile, alloc.getChannelDir(),
104 static_cast<int>(alloc.getChannelIndex())}};
105 p.regions.push_back(&task.getBody());
106 p.passes += task.getRepeatCount();
107 return p;
108 }
109 return std::nullopt;
110}
111
112// Every DMA channel program: aie.dma_start and aie.dma inside the tile DMA
113// ops, and runtime-configured tasks.
114SmallVector<DmaChannelProgram> collectDmaPrograms(DeviceOp device) {
115 SmallVector<DmaChannelProgram> programs;
116 device.walk([&](Operation *op) {
117 if (isa<DMAStartOp, DMAOp, AIEX::DMAConfigureTaskOp,
118 AIEX::DMAConfigureTaskForOp>(op))
119 if (std::optional<DmaChannelProgram> p = makeProgram(op, device))
120 programs.push_back(std::move(*p));
121 });
122 return programs;
123}
124
125template <typename OpT>
126void forEachInProgram(const DmaChannelProgram &p,
127 llvm::function_ref<void(OpT)> fn) {
128 for (Block *b : p.bds)
129 for (auto op : b->getOps<OpT>())
130 fn(op);
131 for (Region *r : p.regions)
132 r->walk([&](OpT op) { fn(op); });
133}
134
135std::optional<TileDMAChannel> channelOfSymbol(DeviceOp device,
136 StringRef symbol) {
137 auto alloc = ShimDMAAllocationOp::getForSymbol(device, symbol);
138 if (!alloc)
139 return std::nullopt;
140 std::optional<TileID> tile = tileOf(alloc.getTile());
141 if (!tile)
142 return std::nullopt;
143 return TileDMAChannel{*tile, alloc.getChannelDir(),
144 static_cast<int>(alloc.getChannelIndex())};
145}
146
147// The ops that can create `task`, following it back through the results and
148// block arguments of runtime control flow (scf.for iter_args, scf.if results).
149// Empty when some value it can come from has no creator here.
150SmallVector<Operation *> taskCreators(Value task) {
151 SmallVector<Operation *> creators;
152 llvm::SmallPtrSet<Value, 8> seen;
153 SmallVector<Value> worklist{task};
154 while (!worklist.empty()) {
155 Value v = worklist.pop_back_val();
156 if (!seen.insert(v).second)
157 continue;
158 Operation *op = v.getDefiningOp();
159 if (isa_and_nonnull<AIEX::DMAConfigureTaskOp, AIEX::DMAConfigureTaskForOp,
160 AIEX::DMAStartBdChainOp, AIEX::DMAStartBdChainForOp>(
161 op)) {
162 creators.push_back(op);
163 continue;
164 }
165 Operation *owner =
166 op ? op : cast<BlockArgument>(v).getOwner()->getParentOp();
167 auto branch = dyn_cast_or_null<RegionBranchOpInterface>(owner);
168 if (!branch)
169 return {};
170 RegionBranchInverseSuccessorMapping mapping;
171 branch.getSuccessorInputOperandMapping(mapping);
172 auto it = mapping.find(v);
173 if (it == mapping.end())
174 return {};
175 for (OpOperand *operand : it->second)
176 worklist.push_back(operand->get());
177 }
178 return creators;
179}
180
181// The channels `task` can run on; empty when that is not known here.
182SmallVector<TileDMAChannel> channelsOfTask(DeviceOp device, Value task) {
183 SmallVector<TileDMAChannel> keys;
184 for (Operation *op : taskCreators(task)) {
185 std::optional<TileDMAChannel> key;
186 auto onTile = [&](Value tileValue, DMAChannelDir dir, int channel) {
187 if (std::optional<TileID> tile = tileOf(tileValue))
188 key = TileDMAChannel{*tile, dir, channel};
189 };
190 if (auto configure = dyn_cast<AIEX::DMAConfigureTaskOp>(op))
191 onTile(configure.getTile(), configure.getDirection(),
192 configure.getChannel());
193 else if (auto chain = dyn_cast<AIEX::DMAStartBdChainOp>(op))
194 onTile(chain.getTile(), chain.getDirection(), chain.getChannel());
195 else if (auto configure = dyn_cast<AIEX::DMAConfigureTaskForOp>(op))
196 key = channelOfSymbol(device, configure.getAlloc().getRootReference());
197 else if (auto chain = dyn_cast<AIEX::DMAStartBdChainForOp>(op))
198 key = channelOfSymbol(device, chain.getAlloc());
199 if (!key)
200 return {};
201 if (!llvm::is_contained(keys, *key))
202 keys.push_back(*key);
203 }
204 return keys;
205}
206
207// Visits the ops in `region` in program order, going through the body of
208// each loop twice, so that what one iteration does follows all the previous
209// iteration did.
210void walkLoopsTwice(Region &region, function_ref<void(Operation *)> fn) {
211 for (Operation &op : region.getOps()) {
212 fn(&op);
213 auto branch = dyn_cast<RegionBranchOpInterface>(op);
214 int passes = branch && branch.hasLoop() ? 2 : 1;
215 for (int pass = 0; pass < passes; pass++)
216 for (Region &r : op.getRegions())
217 walkLoopsTwice(r, fn);
218 }
219}
220
221// Packet ids each sending channel is programmed with.
222std::map<TileDMAChannel, std::set<int>> collectSentPacketIDs(DeviceOp device) {
223 std::map<TileDMAChannel, std::set<int>> ids;
224 for (const DmaChannelProgram &p : collectDmaPrograms(device)) {
225 if (p.dma.dir != DMAChannelDir::MM2S)
226 continue;
227 forEachInProgram<DMABDOp>(p, [&](DMABDOp bd) {
228 if (std::optional<PacketInfoAttr> packet = bd.getPacket())
229 ids[p.dma].insert(packet->assignedId());
230 });
231 }
232 for (auto alloc : device.getOps<ShimDMAAllocationOp>()) {
233 std::optional<PacketInfoAttr> packet = alloc.getPacket();
234 std::optional<TileID> tile = tileOf(alloc.getTile());
235 if (packet && tile)
236 ids[{*tile, alloc.getChannelDir(),
237 static_cast<int>(alloc.getChannelIndex())}]
238 .insert(packet->assignedId());
239 }
240 device.walk([&](AIEX::NpuDmaMemcpyNdOp memcpy) {
241 std::optional<PacketInfoAttr> packet = memcpy.getPacket();
242 if (!packet)
243 return;
244 if (std::optional<TileDMAChannel> key =
245 channelOfSymbol(device, memcpy.getMetadata().getRootReference()))
246 ids[*key].insert(packet->assignedId());
247 });
248 return ids;
249}
250
251class StreamTracer {
252public:
253 explicit StreamTracer(DeviceOp device)
254 : maxPacketID(getTargetModel(device).getMaxPacketId()) {
255 for (auto sb : device.getOps<SwitchboxOp>())
256 switchboxes[sb.getTileOp().getTileID()] = sb;
257 for (auto mux : device.getOps<ShimMuxOp>())
258 shimMuxes[mux.getTileOp().getTileID()] = mux;
259 sentIDs = collectSentPacketIDs(device);
260 }
261
262 std::vector<RoutedStream> trace() {
263 for (auto &[tile, mux] : shimMuxes)
264 for (Port p : inputPorts(mux.getConnections()))
265 if (p.bundle != WireBundle::North)
266 traceFrom({tile, p}, mux, p);
267 for (auto &[tile, sb] : switchboxes)
268 for (Port p : inputPorts(sb.getConnections()))
269 if (!isDirectional(p.bundle))
270 traceFrom({tile, p}, sb, p);
271 return std::move(streams);
272 }
273
274private:
275 struct Hop {
276 Interconnect interconnect;
277 Port input;
278 };
279
280 static SmallVector<Port> inputPorts(Region &connections) {
281 SmallVector<Port> ports;
282 for (Operation &op : connections.front()) {
283 std::optional<Port> p;
284 if (auto connect = dyn_cast<ConnectOp>(op))
285 p = connect.sourcePort();
286 else if (auto rules = dyn_cast<PacketRulesOp>(op))
287 p = rules.sourcePort();
288 if (p && !llvm::is_contained(ports, *p))
289 ports.push_back(*p);
290 }
291 return ports;
292 }
293
294 void traceFrom(StreamEndpoint src, Interconnect interconnect, Port input) {
295 std::optional<std::set<int>> ids;
296 // A tile sends from its MM2S channel on the port of the same number.
297 if (src.port.bundle == WireBundle::DMA) {
298 auto it = sentIDs.find({src.tile, DMAChannelDir::MM2S, src.port.channel});
299 if (it != sentIDs.end())
300 ids = it->second;
301 }
302 if (!ids) {
303 step(src, {interconnect, input}, std::nullopt);
304 return;
305 }
306 for (int id : *ids)
307 step(src, {interconnect, input}, id);
308 }
309
310 // The switchbox input a master port of `from` drives, or the tile port it
311 // leaves the fabric at.
312 std::variant<Hop, StreamEndpoint> follow(Interconnect from, Port out) {
313 TileID here{from.colIndex(), from.rowIndex()};
314 if (isa<ShimMuxOp>(from)) {
315 if (out.bundle == WireBundle::North)
316 if (auto sb = switchboxes.find(here); sb != switchboxes.end())
317 return Hop{sb->second, {WireBundle::South, out.channel}};
318 return StreamEndpoint{here, out};
319 }
320 if (!isDirectional(out.bundle))
321 return StreamEndpoint{here, out};
322 if (out.bundle == WireBundle::South)
323 if (auto mux = shimMuxes.find(here); mux != shimMuxes.end())
324 return Hop{mux->second, {WireBundle::North, out.channel}};
325 TileID next = here;
326 WireBundle in = WireBundle::South;
327 switch (out.bundle) {
328 case WireBundle::North:
329 next.row++;
330 in = WireBundle::South;
331 break;
332 case WireBundle::South:
333 next.row--;
334 in = WireBundle::North;
335 break;
336 case WireBundle::East:
337 next.col++;
338 in = WireBundle::West;
339 break;
340 default:
341 next.col--;
342 in = WireBundle::East;
343 break;
344 }
345 if (auto sb = switchboxes.find(next); sb != switchboxes.end())
346 return Hop{sb->second, {in, out.channel}};
347 return StreamEndpoint{here, out};
348 }
349
350 // Follows the stream `src` sends with `id` on from `hop`, along every
351 // branch that does not come back to an input it already took.
352 void step(StreamEndpoint src, Hop hop, std::optional<int> id) {
353 std::pair<Operation *, Port> input{hop.interconnect, hop.input};
354 if (!onPath.insert(input).second)
355 return;
356 llvm::scope_exit leave([&] { onPath.erase(input); });
357 auto sb = dyn_cast<SwitchboxOp>(hop.interconnect.getOperation());
358 Block &b = hop.interconnect.getConnections().front();
359
360 auto next = [&](Port out, std::optional<int> nextID,
361 std::optional<int> arbiter, bool keepsPktHeader = false) {
362 if (sb)
363 path.push_back({sb.getTileOp().getTileID(), hop.input, arbiter});
364 llvm::scope_exit backtrack([&] {
365 if (sb)
366 path.pop_back();
367 });
368 std::variant<Hop, StreamEndpoint> to = follow(hop.interconnect, out);
369 if (auto *endpoint = std::get_if<StreamEndpoint>(&to))
370 streams.push_back({src, *endpoint, nextID, keepsPktHeader, path});
371 else
372 step(src, std::get<Hop>(to), nextID);
373 };
374
375 for (auto connect : b.getOps<ConnectOp>())
376 if (connect.sourcePort() == hop.input)
377 next(connect.destPort(), id, std::nullopt);
378
379 for (auto rules : b.getOps<PacketRulesOp>()) {
380 if (rules.sourcePort() != hop.input)
381 continue;
382 auto route = [&](PacketRuleOp rule, int ruleID) {
383 std::optional<int> arbiter;
384 if (auto amsel = rule.getAmsel().getDefiningOp<AMSelOp>())
385 arbiter = amsel.arbiterIndex();
386 for (auto masterSet : b.getOps<MasterSetOp>())
387 if (llvm::is_contained(masterSet.getAmsels(), rule.getAmsel()))
388 next(masterSet.destPort(), ruleID, arbiter,
389 masterSet.keepsPktHeader());
390 };
391 for (int packetID = id.value_or(0); packetID <= id.value_or(maxPacketID);
392 ++packetID)
393 for (auto rule : rules.getRules().front().getOps<PacketRuleOp>())
394 if ((packetID & rule.maskInt()) ==
395 (rule.valueInt() & rule.maskInt())) {
396 route(rule, packetID);
397 break;
398 }
399 }
400 }
401
402 std::map<TileID, SwitchboxOp> switchboxes;
403 std::map<TileID, ShimMuxOp> shimMuxes;
404 std::map<TileDMAChannel, std::set<int>> sentIDs;
405 std::vector<RoutedStream> streams;
406 // The interconnect inputs the stream `step` follows has taken, and the
407 // switchboxes it has passed.
408 llvm::DenseSet<std::pair<Operation *, Port>> onPath;
409 SmallVector<StreamHop, 8> path;
410 int maxPacketID;
411};
412
413} // namespace
414
415std::vector<RoutedStream> AIE::traceRoutedStreams(DeviceOp device) {
416 return StreamTracer(device).trace();
417}
418
419std::vector<RoutedStream> AIE::requestedStreams(DeviceOp device) {
420 std::vector<RoutedStream> streams;
421 for (auto flow : device.getOps<FlowOp>()) {
422 std::optional<TileID> srcTile = tileOf(flow.getSource());
423 std::optional<TileID> dstTile = tileOf(flow.getDest());
424 if (srcTile && dstTile)
425 streams.push_back(
426 {{*srcTile, {flow.getSourceBundle(), flow.sourceIndex()}},
427 {*dstTile, {flow.getDestBundle(), flow.destIndex()}},
428 std::nullopt});
429 }
430 // The router writes one keep_pkt_header per destination port, the last
431 // packet flow's into it.
432 DenseMap<std::pair<TileID, Port>, std::optional<bool>> keepAt;
433 for (auto flow : device.getOps<PacketFlowOp>())
434 for (auto dst : flow.getPorts().front().getOps<PacketDestOp>())
435 if (std::optional<TileID> dstTile = tileOf(dst.getTile()))
436 keepAt[{*dstTile, dst.port()}] = flow.getKeepPktHeader();
437 for (auto flow : device.getOps<PacketFlowOp>()) {
438 Block &b = flow.getPorts().front();
439 for (auto src : b.getOps<PacketSourceOp>()) {
440 std::optional<TileID> srcTile = tileOf(src.getTile());
441 if (!srcTile)
442 continue;
443 for (auto dst : b.getOps<PacketDestOp>())
444 if (std::optional<TileID> dstTile = tileOf(dst.getTile()))
445 streams.push_back(
446 {{*srcTile, src.port()},
447 {*dstTile, dst.port()},
448 flow.IDInt(),
449 keepsPktHeader(*dstTile, dst.port(),
450 keepAt.lookup({*dstTile, dst.port()})),
451 {},
452 static_cast<int>(flow.getMask().value_or(~0))});
453 }
454 }
455 return streams;
456}
457
459 ArrayRef<RoutedStream> streams)
460 : device(device), streams(streams) {
461 for (DmaChannelProgram &p : collectDmaPrograms(device))
462 programs[p.dma].push_back(std::move(p));
463 for (const auto &[dma, channelPrograms] : programs)
464 for (const DmaChannelProgram &p : channelPrograms)
465 forEachInProgram<UseLockOp>(
466 p, [&](UseLockOp use) { lockUseProgram[use] = &p; });
467 device.walk([&](AIEX::NpuDmaMemcpyNdOp memcpy) {
468 if (std::optional<TileDMAChannel> dma =
469 channelOfSymbol(device, memcpy.getMetadata().getRootReference()))
470 memcpys[*dma].push_back(memcpy);
471 });
472}
473
474// The BD blocks of a program in the order its channel runs them.
475static SmallVector<Block *> chainBlocks(const DmaChannelProgram &p) {
476 SmallVector<Block *> sequence(p.bds);
477 for (Region *r : p.regions)
478 sequence.push_back(&r->front());
479 return sequence;
480}
481
482// Index into `sequence` of the block a program runs at `step`: the blocks
483// before the cycle once, then the cycle over and over. A looping chain cycles
484// from where it returns to, a repeated one over the whole chain.
485static size_t blockAt(const DmaChannelProgram &p, size_t size, uint64_t step) {
486 size_t start = p.loops ? p.loopStart : 0;
487 if (step < start)
488 return step;
489 return start + (step - start) % (size - start);
490}
491
492// The value `use` acquires or releases, if it is a constant.
493static std::optional<int64_t> lockAmount(UseLockOp use) {
494 APInt amount;
495 if (!use.getLock().getDefiningOp<LockOp>() ||
496 !matchPattern(use.getValue(), m_ConstantInt(&amount)))
497 return std::nullopt;
498 return amount.getSExtValue();
499}
500
501// The tokens `use` takes or gives, if that is a known count.
502static std::optional<uint64_t> lockTokens(UseLockOp use) {
503 std::optional<int64_t> n = lockAmount(use);
504 if (!n || *n < 0)
505 return std::nullopt;
506 return *n;
507}
508
509constexpr int maxBDSteps = 1024;
510
511std::optional<uint64_t>
513 if (stream.src.port.bundle != WireBundle::DMA)
514 return std::nullopt;
515 TileDMAChannel dma{stream.src.tile, DMAChannelDir::MM2S,
516 stream.src.port.channel};
517 constexpr uint64_t pktHeaderBytes = 4;
518 auto headerBytes = [&](std::optional<PacketInfoAttr> packet) -> uint64_t {
519 return packet && stream.keepsPktHeader ? pktHeaderBytes : 0;
520 };
521 auto bytesOf = [&](DMABDOp bd) -> uint64_t {
522 if (!stream.carries(bd.getPacket()))
523 return 0;
524 return bd.getLenInBytes() + headerBytes(bd.getPacket());
525 };
526 bool known = false;
527 uint64_t total = 0;
528 if (auto it = programs.find(dma); it != programs.end()) {
529 for (const DmaChannelProgram &p : it->second) {
530 bool carried = false;
531 uint64_t bytes = 0;
532 forEachInProgram<DMABDOp>(p, [&](DMABDOp bd) {
533 if (!stream.carries(bd.getPacket()))
534 return;
535 carried = true;
536 bytes += bytesOf(bd);
537 });
538 known = true;
539 if (!carried)
540 continue;
541 if (p.loops) {
542 std::optional<uint64_t> looped = loopedVolume(p, bytesOf);
543 if (!looped)
544 return std::nullopt;
545 total += *looped;
546 continue;
547 }
548 uint64_t runs = p.passes;
549 if (isa<AIEX::DMAConfigureTaskOp, AIEX::DMAConfigureTaskForOp>(p.op)) {
550 auto task = dyn_cast<AIEX::DMAConfigureTaskOp>(p.op);
551 auto taskFor = dyn_cast<AIEX::DMAConfigureTaskForOp>(p.op);
552 if ((task && task.getRepeatCountVal()) ||
553 (taskFor && taskFor.getRepeatCountVal()))
554 return std::nullopt;
555 runs = 0;
556 for (Operation *user : p.op->getUsers()) {
557 if (isa<AIEX::DMAAwaitTaskOp, AIEX::DMAFreeTaskOp>(user))
558 continue;
559 // Any other user, such as an scf.yield or an scf.for init, can
560 // forward the task to starts this does not count.
561 auto start = dyn_cast<AIEX::DMAStartTaskOp>(user);
562 if (!start || start.hasRepeatParameter())
563 return std::nullopt;
564 if (user->getParentOfType<LoopLikeOpInterface>())
565 return std::nullopt;
566 runs += p.passes;
567 }
568 }
569 total += bytes * runs;
570 }
571 }
572 if (auto it = memcpys.find(dma); it != memcpys.end()) {
573 for (Operation *op : it->second) {
574 auto memcpy = cast<AIEX::NpuDmaMemcpyNdOp>(op);
575 std::optional<PacketInfoAttr> packet = memcpy.getPacket();
576 if (!packet)
577 packet = ShimDMAAllocationOp::getForSymbol(
578 device, memcpy.getMetadata().getRootReference())
579 .getPacket();
580 if (!stream.carries(packet))
581 continue;
582 auto type = dyn_cast<BaseMemRefType>(memcpy.getMemref().getType());
583 if (memcpy->getParentOfType<LoopLikeOpInterface>() || !type ||
584 !type.getElementType().isIntOrFloat())
585 return std::nullopt;
586 std::optional<SmallVector<int64_t>> sizes =
587 getConstantIntValues(memcpy.getMixedSizes());
588 if (!sizes)
589 return std::nullopt;
590 uint64_t elements = 1;
591 for (int64_t n : *sizes)
592 elements *= n;
593 // The outermost dimension re-runs the BD (as iterations, or as repeats
594 // when its stride is 0), and each run sends its own header.
595 uint64_t runs = sizes->front();
596 known = true;
597 total += elements * type.getElementTypeBitWidth() / 8 +
598 runs * headerBytes(packet);
599 }
600 }
601 if (!known)
602 return std::nullopt;
603 return total;
604}
605
606std::optional<uint64_t> StreamVolumeAnalysis::loopedVolume(
607 const DmaChannelProgram &program,
608 function_ref<uint64_t(DMABDOp)> bytesOf) const {
609 uint64_t bytes = 0;
610 if (!walkLoop(program, [&](DMABDOp bd) { bytes += bytesOf(bd); }))
611 return std::nullopt;
612 return bytes;
613}
614
615bool StreamVolumeAnalysis::walkLoop(const DmaChannelProgram &p,
616 function_ref<void(DMABDOp)> visit) const {
617 // Binary locks hold a state rather than count tokens.
618 if (!getTargetModel(device).hasProperty(AIETargetModel::UsesSemaphoreLocks) ||
619 !visiting.insert(&p).second)
620 return false;
621 llvm::scope_exit done([&] { visiting.erase(&p); });
622 SmallVector<Block *> sequence = chainBlocks(p);
623 if (sequence.empty())
624 return false;
625 DenseMap<Operation *, uint64_t> tokens;
626 for (int step = 0; step < maxBDSteps; step++) {
627 for (Operation &bdOp : *sequence[blockAt(p, sequence.size(), step)]) {
628 if (auto use = dyn_cast<UseLockOp>(bdOp)) {
629 auto lock = use.getLock().getDefiningOp<LockOp>();
630 std::optional<uint64_t> n = lockTokens(use);
631 if (!n || (!use.release() && !use.acquireGE()))
632 return false;
633 auto it = tokens.find(lock);
634 if (it == tokens.end()) {
635 std::optional<uint64_t> others = tokensFromOthers(lock, &p);
636 if (!others)
637 return false;
638 it = tokens.try_emplace(lock, lock.getInit().value_or(0) + *others)
639 .first;
640 }
641 if (use.release())
642 it->second += *n;
643 else if (it->second < *n)
644 return true;
645 else
646 it->second -= *n;
647 } else if (auto bd = dyn_cast<DMABDOp>(bdOp)) {
648 visit(bd);
649 }
650 }
651 }
652 return false;
653}
654
655// Whether `op` runs at most once each time its core runs its body.
656static bool onceInCore(Operation *op) {
657 for (Operation *parent = op->getParentOp(); parent;
658 op = parent, parent = parent->getParentOp()) {
659 if (!op->getParentRegion()->hasOneBlock() ||
660 isa<LoopLikeOpInterface>(parent))
661 return false;
662 if (isa<CoreOp>(parent))
663 return true;
664 }
665 return false;
666}
667
668std::optional<uint64_t>
669StreamVolumeAnalysis::tokensFromOthers(LockOp lock,
670 const DmaChannelProgram *self) const {
671 llvm::SetVector<const DmaChannelProgram *> releasers;
672 uint64_t tokens = 0;
673 for (Operation *user : lock->getUsers()) {
674 auto use = dyn_cast<UseLockOp>(user);
675 if (!use)
676 return std::nullopt;
677 if (!use.release())
678 continue;
679 auto owner = lockUseProgram.find(use);
680 if (owner == lockUseProgram.end()) {
681 std::optional<uint64_t> n = lockTokens(use);
682 if (!onceInCore(use) || !n)
683 return std::nullopt;
684 tokens += *n;
685 continue;
686 }
687 if (owner->second != self)
688 releasers.insert(owner->second);
689 }
690 for (const DmaChannelProgram *program : releasers) {
691 std::optional<uint64_t> n = releasesOver(*program, lock);
692 if (!n)
693 return std::nullopt;
694 tokens += *n;
695 }
696 return tokens;
697}
698
699std::optional<bool>
701 const RoutedStream &then) const {
702 if (first.src != then.src)
703 return std::nullopt;
704 if (!first.packetID || !then.packetID ||
705 ((*first.packetID ^ *then.packetID) & first.packetMask &
706 then.packetMask) == 0)
707 return true;
708 if (first.src.port.bundle != WireBundle::DMA)
709 return std::nullopt;
710 TileDMAChannel dma{first.src.tile, DMAChannelDir::MM2S,
711 first.src.port.channel};
712 auto it = programs.find(dma);
713 if (it == programs.end() || it->second.size() != 1 ||
714 !isa<DMAStartOp, DMAOp>(it->second.front().op) || memcpys.count(dma))
715 return std::nullopt;
716 const DmaChannelProgram &p = it->second.front();
717 bool sent = false, after = false;
718 auto visit = [&](DMABDOp bd) {
719 after |= sent && then.carries(bd.getPacket());
720 sent |= first.carries(bd.getPacket());
721 };
722 if (p.loops) {
723 if (!walkLoop(p, visit))
724 return std::nullopt;
725 return after;
726 }
727 SmallVector<Block *> sequence = chainBlocks(p);
728 for (uint64_t pass = 0; pass < p.passes && !after; pass++)
729 for (Block *b : sequence)
730 for (DMABDOp bd : b->getOps<DMABDOp>())
731 visit(bd);
732 return after;
733}
734
735std::optional<uint64_t>
736StreamVolumeAnalysis::releasesOver(const DmaChannelProgram &p,
737 LockOp lock) const {
738 if (!isa<DMAStartOp, DMAOp>(p.op))
739 return std::nullopt;
740 SmallVector<Block *> sequence = chainBlocks(p);
741 if (!p.loops) {
742 uint64_t perPass = 0;
743 for (Block *b : sequence)
744 for (auto use : b->getOps<UseLockOp>())
745 if (use.release() && use.getLock().getDefiningOp() == lock) {
746 std::optional<uint64_t> n = lockTokens(use);
747 if (!n)
748 return std::nullopt;
749 perPass += *n;
750 }
751 return perPass * p.passes;
752 }
753 // A looping receiver finishes only the BDs what it is sent fills.
754 if (p.dma.dir != DMAChannelDir::S2MM || sequence.empty())
755 return std::nullopt;
756 StreamEndpoint endpoint{p.dma.tile, {WireBundle::DMA, p.dma.channel}};
757 uint64_t received = 0;
758 for (const RoutedStream &s : streams) {
759 if (s.dst != endpoint)
760 continue;
761 std::optional<uint64_t> bytes = sendVolume(s);
762 if (!bytes)
763 return std::nullopt;
764 received += *bytes;
765 }
766 uint64_t filled = 0, tokens = 0;
767 for (int step = 0; step < maxBDSteps; step++) {
768 for (Operation &bdOp : *sequence[blockAt(p, sequence.size(), step)]) {
769 if (auto bd = dyn_cast<DMABDOp>(bdOp)) {
770 if (filled + bd.getLenInBytes() > received)
771 return tokens;
772 filled += bd.getLenInBytes();
773 } else if (auto use = dyn_cast<UseLockOp>(bdOp)) {
774 if (!use.release() || use.getLock().getDefiningOp() != lock)
775 continue;
776 std::optional<uint64_t> n = lockTokens(use);
777 if (!n)
778 return std::nullopt;
779 tokens += *n;
780 }
781 }
782 }
783 return std::nullopt;
784}
785
786static std::optional<uint64_t> programCapacity(const DmaChannelProgram &p,
787 DeviceOp device) {
788 if (!isa<DMAStartOp, DMAOp>(p.op))
789 return 0;
790
791 // Run the BD chain from its initial lock values until an acquire blocks.
792 SmallVector<Block *> sequence = chainBlocks(p);
793 if (sequence.empty())
794 return 0;
795 // Binary locks hold a state an acquire waits to equal and a release sets;
796 // semaphore locks count, and an acquire waiting for an exact count is taken
797 // to block.
798 bool stateLocks =
800 DenseMap<Operation *, int64_t> lockValues;
801 uint64_t bytes = 0;
802 // Lock values and bytes when the cycle last began. A cycle that leaves every
803 // lock where it found it, or with more tokens, runs again the same way.
804 std::optional<DenseMap<Operation *, int64_t>> cycleLocks;
805 uint64_t cycleBytes = 0;
806 size_t start = p.loops ? p.loopStart : 0;
807 for (uint64_t step = 0;; step++) {
808 if (!p.loops && step >= p.passes * sequence.size())
809 return bytes;
810 size_t i = blockAt(p, sequence.size(), step);
811 if (i == start) {
812 if (cycleLocks && cycleLocks->size() == lockValues.size() &&
813 llvm::all_of(lockValues, [&](const auto &lv) {
814 int64_t before = cycleLocks->at(lv.first);
815 return stateLocks ? lv.second == before : lv.second >= before;
816 })) {
817 if (p.loops)
818 return std::nullopt;
819 return bytes +
820 (p.passes - step / sequence.size()) * (bytes - cycleBytes);
821 }
822 cycleLocks = lockValues;
823 cycleBytes = bytes;
824 }
825 // Past the analysis limit, what it took in so far is a safe capacity.
826 if (step >= static_cast<uint64_t>(maxBDSteps))
827 return bytes;
828 for (Operation &bdOp : *sequence[i]) {
829 if (auto use = dyn_cast<UseLockOp>(bdOp)) {
830 std::optional<int64_t> n = lockAmount(use);
831 if (!n)
832 return 0;
833 auto lock = use.getLock().getDefiningOp<LockOp>();
834 int64_t &value =
835 lockValues.try_emplace(lock, lock.getInit().value_or(0))
836 .first->second;
837 if (stateLocks) {
838 if (use.release())
839 value = *n;
840 else if (value != *n)
841 return bytes;
842 } else if (use.release()) {
843 value += *n;
844 } else if (!use.acquireGE() || value < *n) {
845 return bytes;
846 } else {
847 value -= *n;
848 }
849 } else if (auto bd = dyn_cast<DMABDOp>(bdOp)) {
850 bytes += bd.getLenInBytes();
851 }
852 }
853 }
854}
855
856std::optional<uint64_t>
858 if (endpoint.port.bundle != WireBundle::DMA)
859 return 0;
860 auto it = programs.find(
861 {endpoint.tile, DMAChannelDir::S2MM, endpoint.port.channel});
862 if (it == programs.end())
863 return 0;
864 std::optional<uint64_t> capacity;
865 for (const DmaChannelProgram &p : it->second)
866 if (std::optional<uint64_t> c = programCapacity(p, device))
867 capacity = std::min(*c, capacity.value_or(*c));
868 return capacity;
869}
870
872 ArrayRef<RoutedStream> streams) const {
873 std::optional<uint64_t> capacity = receiveCapacity(endpoint);
874 if (!capacity)
875 return false;
876 uint64_t sent = 0;
877 for (const RoutedStream &s : streams) {
878 if (s.dst != endpoint)
879 continue;
880 std::optional<uint64_t> bytes = sendVolume(s);
881 if (!bytes)
882 return true;
883 sent += *bytes;
884 }
885 return sent > *capacity;
886}
887
889 ArrayRef<RoutedStream> streams,
890 const StreamVolumeAnalysis &volumes) {
891 std::set<TileDMAChannel> neverFull;
892 for (const RoutedStream &s : streams)
893 if (s.dst.port.bundle == WireBundle::DMA &&
894 !volumes.canFill(s.dst, streams))
895 neverFull.insert({s.dst.tile, DMAChannelDir::S2MM, s.dst.port.channel});
896 auto waitsOnLocks = [&](unsigned agent) {
897 const Agent &a = agents[agent];
898 return a.kind == Agent::Kind::Core || !neverFull.count(a.dma);
899 };
900
901 // Who acquires and who releases each lock.
902 DenseMap<Operation *, llvm::SetVector<unsigned>> acquirers, releasers;
903 auto noteLock = [&](UseLockOp use, unsigned agent) {
904 Operation *lock = use.getLock().getDefiningOp();
905 if (!lock)
906 return;
907 if (use.getAction() == LockAction::Release)
908 releasers[lock].insert(agent);
909 else
910 acquirers[lock].insert(agent);
911 };
912
913 // Agents whose waits the design spells out; see the end of this constructor
914 // for the rest.
915 for (auto core : device.getOps<CoreOp>()) {
916 unsigned agent = getOrCreate(Agent::core(core.getTileOp().getTileID()));
917 modeled.insert(agent);
918 core.walk([&](UseLockOp use) { noteLock(use, agent); });
919 }
920 for (const DmaChannelProgram &p : collectDmaPrograms(device)) {
921 unsigned agent = getOrCreate(Agent::channel(p.dma));
922 modeled.insert(agent);
923 forEachInProgram<UseLockOp>(p,
924 [&](UseLockOp use) { noteLock(use, agent); });
925 }
926 // Document order, not pointer order: edge order picks the chain a
927 // diagnostic reports.
928 for (auto lock : device.getOps<LockOp>()) {
929 auto waiting = acquirers.find(lock), it = releasers.find(lock);
930 if (waiting == acquirers.end() || it == releasers.end())
931 continue;
932 for (unsigned p : waiting->second)
933 for (unsigned q : it->second)
934 if (p != q && waitsOnLocks(p))
935 addEdge(p, q, EdgeKind::Lock);
936 }
937
938 for (const RoutedStream &s : streams) {
939 std::optional<unsigned> from, to;
940 if (std::optional<Agent> agent = Agent::at(s.src, true))
941 from = getOrCreate(*agent);
942 if (std::optional<Agent> agent = Agent::at(s.dst, false))
943 to = getOrCreate(*agent);
944 if (!from || !to || *from == *to)
945 continue;
946 addEdge(*from, *to, EdgeKind::Stream, /*sends=*/true);
947 addEdge(*to, *from, EdgeKind::Stream, /*sends=*/false, /*receives=*/true);
948 }
949
950 // The host issues a channel's transfer only after every wait before it in
951 // the runtime sequence completes. Each issue is modeled: a later one can
952 // follow waits the first did not. A wait on a channel not known here may be
953 // on any the sequence issues, and an issue on one, or a raw register write,
954 // may start any channel.
955 unsigned numStreamAgents = agents.size();
956 for (auto sequence : device.getOps<RuntimeSequenceOp>()) {
957 auto bySymbol = [&](SymbolRefAttr symbol) -> SmallVector<TileDMAChannel> {
958 if (std::optional<TileDMAChannel> key =
959 channelOfSymbol(device, symbol.getRootReference()))
960 return {*key};
961 return {};
962 };
963 auto issued =
964 [&](Operation *op) -> std::optional<SmallVector<TileDMAChannel>> {
965 if (auto memcpy = dyn_cast<AIEX::NpuDmaMemcpyNdOp>(op))
966 return bySymbol(memcpy.getMetadata());
967 if (auto start = dyn_cast<AIEX::DMAStartTaskOp>(op))
968 return channelsOfTask(device, start.getTask());
969 if (isa<AIEX::DMAStartBdChainOp, AIEX::DMAStartBdChainForOp>(op))
970 return channelsOfTask(device, op->getResult(0));
971 if (auto push = dyn_cast<AIEX::NpuPushQueueOp>(op))
972 return SmallVector<TileDMAChannel>{
973 {{static_cast<int>(push.getColumn()),
974 static_cast<int>(push.getRow())},
975 push.getDirection(),
976 static_cast<int>(push.getChannel())}};
977 if (isa<AIEX::NpuWrite32Op, AIEX::NpuMaskWrite32Op, AIEX::NpuBlockWriteOp,
978 AIEX::NpuWriteConfigOp, AIEX::NpuWriteTeardownOp>(op))
979 return SmallVector<TileDMAChannel>{};
980 return std::nullopt;
981 };
982 auto awaited =
983 [&](Operation *op) -> std::optional<SmallVector<TileDMAChannel>> {
984 if (auto dmaWait = dyn_cast<AIEX::NpuDmaWaitOp>(op))
985 return bySymbol(dmaWait.getSymbolAttr());
986 if (auto await = dyn_cast<AIEX::DMAAwaitTaskOp>(op))
987 return channelsOfTask(device, await.getTask());
988 if (auto sync = dyn_cast<AIEX::NpuSyncOp>(op)) {
989 std::optional<int64_t> col = getConstantIntValue(sync.getColumn()),
990 row = getConstantIntValue(sync.getRow()),
991 dir = getConstantIntValue(sync.getDirection()),
992 channel = getConstantIntValue(sync.getChannel()),
993 cols = getConstantIntValue(sync.getColumnNum()),
994 rows = getConstantIntValue(sync.getRowNum());
995 if (!col || !row || !dir || !channel || !cols || !rows)
996 return SmallVector<TileDMAChannel>{};
997 SmallVector<TileDMAChannel> keys;
998 for (int64_t c = *col; c < *col + *cols; c++)
999 for (int64_t r = *row; r < *row + *rows; r++)
1000 keys.push_back({{static_cast<int>(c), static_cast<int>(r)},
1001 *dir ? DMAChannelDir::MM2S : DMAChannelDir::S2MM,
1002 static_cast<int>(*channel)});
1003 return keys;
1004 }
1005 if (isa<AIEX::NpuMaskPollOp>(op))
1006 return SmallVector<TileDMAChannel>{};
1007 return std::nullopt;
1008 };
1009 llvm::SetVector<TileDMAChannel, SmallVector<TileDMAChannel>,
1010 std::set<TileDMAChannel>>
1011 issuedKeys;
1012 sequence.walk([&](Operation *op) {
1013 if (std::optional<SmallVector<TileDMAChannel>> keys = issued(op))
1014 issuedKeys.insert(keys->begin(), keys->end());
1015 });
1016
1017 llvm::SetVector<unsigned> waited;
1018 walkLoopsTwice(sequence.getBody(), [&](Operation *op) {
1019 if (std::optional<SmallVector<TileDMAChannel>> keys = issued(op)) {
1020 for (const TileDMAChannel &key : *keys) {
1021 unsigned agent = getOrCreate(Agent::channel(key));
1022 modeled.insert(agent);
1023 for (unsigned w : waited)
1024 if (w != agent)
1025 addEdge(agent, w, EdgeKind::Host);
1026 }
1027 if (keys->empty())
1028 for (unsigned a = 0; a < numStreamAgents; a++)
1029 if (agents[a].kind == Agent::Kind::Channel)
1030 for (unsigned w : waited)
1031 if (w != a)
1032 addEdge(a, w, EdgeKind::Host);
1033 } else if (std::optional<SmallVector<TileDMAChannel>> keys =
1034 awaited(op)) {
1035 for (const TileDMAChannel &key :
1036 keys->empty() ? issuedKeys.getArrayRef() : ArrayRef(*keys)) {
1037 waited.insert(getOrCreate(Agent::channel(key)));
1038 for (unsigned a = 0; a < numStreamAgents; a++)
1039 if (agents[a].kind == Agent::Kind::Controller &&
1040 agents[a].dma.tile.col == key.tile.col)
1041 waited.insert(a);
1042 }
1043 }
1044 });
1045 }
1046
1047 // A channel nothing programs here is programmed elsewhere, in ways this
1048 // cannot see, so it may wait on anything else on its tile. One on a shim
1049 // tile is driven by the host, which may wait on any other shim tile first.
1050 const AIETargetModel &targetModel = getTargetModel(device);
1051 for (Agent &a : agents)
1052 a.onShim = a.kind == Agent::Kind::Channel &&
1053 targetModel.isShimNOCorPLTile(a.dma.tile.col, a.dma.tile.row);
1054 for (unsigned a = 0; a < agents.size(); a++) {
1055 if (modeled.contains(a) || agents[a].kind == Agent::Kind::Controller ||
1056 !waitsOnLocks(a))
1057 continue;
1058 for (unsigned b = 0; b < agents.size(); b++)
1059 if (b != a && agents[b].kind != Agent::Kind::Controller &&
1060 (agents[b].dma.tile == agents[a].dma.tile ||
1061 (agents[a].onShim && agents[b].onShim)))
1062 addEdge(a, b, EdgeKind::Lock);
1063 }
1064
1065 LLVM_DEBUG({
1066 for (unsigned a = 0; a < agents.size(); a++)
1067 for (const Edge &e : edges[a])
1068 llvm::dbgs() << "Wait: " << describe(a) << " on " << describe(e.to)
1069 << (e.kind == EdgeKind::Lock ? " (lock)"
1070 : e.kind == EdgeKind::Stream ? " (stream)"
1071 : " (host)")
1072 << (e.kind == EdgeKind::Lock && !modeled.contains(a)
1073 ? ", assumed"
1074 : "")
1075 << "\n";
1076 });
1077}
1078
1079std::optional<StreamWaitGraph::Agent>
1080StreamWaitGraph::Agent::at(const StreamEndpoint &endpoint, bool sending) {
1081 if (endpoint.port.bundle == WireBundle::Core)
1082 return core(endpoint.tile);
1083 if (endpoint.port.bundle == WireBundle::TileControl && sending)
1084 return controller(endpoint.tile);
1085 if (endpoint.port.bundle == WireBundle::DMA)
1086 return channel({endpoint.tile,
1087 sending ? DMAChannelDir::MM2S : DMAChannelDir::S2MM,
1088 endpoint.port.channel});
1089 // Other ports (PLIO, NOC, a receiving TileControl) are taken to always
1090 // drain, so the streams into them never block.
1091 return std::nullopt;
1092}
1093
1094unsigned StreamWaitGraph::getOrCreate(const Agent &agent) {
1095 auto [it, inserted] =
1096 agentIDs.try_emplace({agent.kind, agent.dma}, agents.size());
1097 if (inserted) {
1098 agents.push_back(agent);
1099 edges.emplace_back();
1100 }
1101 return it->second;
1102}
1103
1104std::optional<unsigned> StreamWaitGraph::lookup(const Agent &agent) const {
1105 auto it = agentIDs.find({agent.kind, agent.dma});
1106 if (it == agentIDs.end())
1107 return std::nullopt;
1108 return it->second;
1109}
1110
1111void StreamWaitGraph::addEdge(unsigned from, unsigned to, EdgeKind kind,
1112 bool sends, bool receives) {
1113 for (Edge &e : edges[from]) {
1114 if (e.to == to && e.kind == kind) {
1115 e.sends |= sends;
1116 e.receives |= receives;
1117 return;
1118 }
1119 }
1120 edges[from].push_back({to, kind, sends, receives});
1121}
1122
1123std::optional<unsigned> StreamWaitGraph::agentAt(const StreamEndpoint &endpoint,
1124 bool sending) const {
1125 if (std::optional<Agent> agent = Agent::at(endpoint, sending))
1126 return lookup(*agent);
1127 return std::nullopt;
1128}
1129
1130SmallVector<unsigned> StreamWaitGraph::drainersOf(unsigned agent) const {
1131 if (agents[agent].kind == Agent::Kind::Core)
1132 return {agent};
1133 SmallVector<unsigned> drainers;
1134 for (const Edge &e : edges[agent])
1135 if (e.kind != EdgeKind::Stream)
1136 drainers.push_back(e.to);
1137 return drainers;
1138}
1139
1140SmallVector<unsigned>
1141StreamWaitGraph::waitChain(ArrayRef<unsigned> from, ArrayRef<unsigned> targets,
1142 ArrayRef<unsigned> avoid) const {
1143 // A state is an agent plus `took`, the subset of channel agents already
1144 // waited on to reach it, and `taking`, whether it was reached as a DMA
1145 // receiver still taking data. A state is dropped once a prior state at the
1146 // same agent is at least as free and took a subset of the same agents: it
1147 // leads nowhere new. Live states per agent therefore form an antichain in
1148 // that subset lattice, so by Sperner's theorem their count can be
1149 // exponential in the worst case -- a known, understood limitation, not an
1150 // oversight. No smaller *exact* representation preserves this dominance
1151 // search's soundness.
1152 struct State {
1153 unsigned agent;
1154 bool taking;
1155 llvm::SparseBitVector<> took;
1156 std::optional<size_t> parent;
1157 };
1158 std::vector<State> states;
1159 DenseMap<unsigned, SmallVector<size_t>> seen;
1160 std::deque<size_t> worklist;
1161 auto visit = [&](State next) {
1162 for (size_t i : seen.lookup(next.agent)) {
1163 const State &s = states[i];
1164 if ((next.taking || !s.taking) && next.took.contains(s.took))
1165 return;
1166 }
1167 seen[next.agent].push_back(states.size());
1168 worklist.push_back(states.size());
1169 states.push_back(std::move(next));
1170 };
1171 for (unsigned a : from)
1172 if (!llvm::is_contained(avoid, a))
1173 visit({a, false, {}, std::nullopt});
1174 while (!worklist.empty()) {
1175 size_t index = worklist.front();
1176 worklist.pop_front();
1177 unsigned a = states[index].agent;
1178 if (llvm::is_contained(targets, a)) {
1179 SmallVector<unsigned> chain;
1180 for (std::optional<size_t> at = index; at; at = states[*at].parent)
1181 chain.push_back(states[*at].agent);
1182 std::reverse(chain.begin(), chain.end());
1183 return chain;
1184 }
1185 for (const Edge &e : edges[a]) {
1186 const State &state = states[index];
1187 if (state.taking && e.receives && !e.sends &&
1188 agents[e.to].kind == Agent::Kind::Channel)
1189 continue;
1190 if (llvm::is_contained(avoid, e.to) || state.took.test(e.to))
1191 continue;
1192 bool takes = e.kind == EdgeKind::Stream && e.sends &&
1193 agents[e.to].kind == Agent::Kind::Channel;
1194 llvm::SparseBitVector<> took = state.took;
1195 if (takes)
1196 took.set(e.to);
1197 visit({e.to, takes, std::move(took), index});
1198 }
1199 }
1200 return {};
1201}
1202
1203std::string StreamWaitGraph::describe(unsigned id) const {
1204 const Agent &a = agents[id];
1205 std::string s;
1206 llvm::raw_string_ostream os(s);
1207 os << "(" << a.dma.tile.col << ", " << a.dma.tile.row << ") ";
1208 if (a.kind == Agent::Kind::Core)
1209 os << "core";
1210 else if (a.kind == Agent::Kind::Controller)
1211 os << "TileControl";
1212 else
1213 os << stringifyDMAChannelDir(a.dma.dir) << " " << a.dma.channel;
1214 return s;
1215}
1216
1218 ArrayRef<RoutedStream> streams)
1219 : streams(streams), volumes(device, streams),
1220 graph(device, streams, volumes), stalls(streams.size()),
1221 silence(streams.size()) {}
1222
1223bool StreamDeadlockAnalysis::canStall(size_t f) const {
1224 std::optional<bool> &stall = stalls[f];
1225 if (!stall)
1226 stall = volumes.canFill(streams[f].dst, streams);
1227 return *stall;
1228}
1229
1230SmallVector<unsigned> StreamDeadlockAnalysis::blockingChain(size_t f,
1231 size_t g) const {
1232 const RoutedStream &fs = streams[f], &gs = streams[g];
1233 std::optional<unsigned> fDst = graph.agentAt(fs.dst, false);
1234 if (!fDst)
1235 return {};
1236 SmallVector<unsigned> own;
1237 if (std::optional<unsigned> fSrc = graph.agentAt(fs.src, true))
1238 own.push_back(*fSrc);
1239 own.push_back(*fDst);
1240 SmallVector<unsigned> drainers = graph.drainersOf(*fDst);
1241 SmallVector<unsigned> avoid, targets;
1242 for (unsigned a : own)
1243 if (!llvm::is_contained(drainers, a))
1244 avoid.push_back(a);
1245 for (std::optional<unsigned> a :
1246 {graph.agentAt(gs.src, true), graph.agentAt(gs.dst, false)})
1247 if (a && !llvm::is_contained(own, *a))
1248 targets.push_back(*a);
1249 if (targets.empty())
1250 return {};
1251 return graph.waitChain(drainers, targets, avoid);
1252}
1253
1254bool StreamDeadlockAnalysis::canBlock(size_t f, size_t g) const {
1255 if (auto it = blocks.find({f, g}); it != blocks.end())
1256 return it->second;
1257 return blocks[{f, g}] = canStall(f) && !silent(f) && !silent(g) &&
1258 volumes.maySendAfter(streams[f], streams[g]) !=
1259 std::optional(false) &&
1260 !blockingChain(f, g).empty();
1261}
1262
1264 std::optional<bool> &quiet = silence[f];
1265 if (!quiet)
1266 quiet = volumes.sendVolume(streams[f]) == std::optional<uint64_t>(0);
1267 return *quiet;
1268}
1269
1270std::string StreamDeadlockAnalysis::explainBlock(size_t f, size_t g) const {
1271 const RoutedStream &fs = streams[f], &gs = streams[g];
1272 SmallVector<unsigned> chain = blockingChain(f, g);
1273 std::string s;
1274 llvm::raw_string_ostream os(s);
1275 os << describeStream(fs) << " can fill its receiver, and draining that "
1276 << "waits on ";
1277 for (auto [i, a] : llvm::enumerate(chain))
1278 os << (i ? ", then " : "") << graph.describe(a);
1279 os << (graph.agentAt(gs.dst, false) == chain.back() ? ", which receives "
1280 : ", which sends ")
1281 << describeStream(gs) << '.';
1282 for (const std::string &a : assumptions(f, g))
1283 os << ' ' << a;
1284 return s;
1285}
1286
1287SmallVector<std::string> StreamDeadlockAnalysis::assumptions(size_t f,
1288 size_t g) const {
1289 const RoutedStream &fs = streams[f], &gs = streams[g];
1290 SmallVector<std::string> assumed;
1291 for (const RoutedStream &other : streams)
1292 if (other.dst == fs.dst && !volumes.sendVolume(other)) {
1293 assumed.push_back("The volume " + describeStream(other) +
1294 " carries is unknown, so it is assumed to overrun its "
1295 "receiver.");
1296 break;
1297 }
1298 if (fs.src == gs.src && !volumes.maySendAfter(fs, gs))
1299 assumed.push_back("Both come from " +
1300 describeTilePort(fs.src.tile, fs.src.port) +
1301 ", and the order it sends in is not modeled.");
1302 SmallVector<unsigned> chain = blockingChain(f, g);
1303 std::optional<unsigned> receiver = graph.agentAt(fs.dst, false);
1304 assert(receiver && "a stream that can block has a receiver");
1305 SmallVector<unsigned> waiters{*receiver};
1306 waiters.append(chain.begin(), std::prev(chain.end()));
1307 for (auto [i, a] : llvm::enumerate(waiters))
1308 if (!graph.isModeled(a) &&
1309 !llvm::is_contained(ArrayRef(waiters).take_front(i), a))
1310 assumed.push_back(
1311 "Nothing in the design programs " + graph.describe(a) +
1312 ", so it is assumed to wait on anything on its tile" +
1313 (graph.getAgent(a).onShim ? " or on another shim tile." : "."));
1314 return assumed;
1315}
1316
1317std::string AIE::describeStream(const RoutedStream &stream) {
1318 std::string s;
1319 llvm::raw_string_ostream os(s);
1320 os << (stream.packetID ? "packet flow " : "flow ")
1321 << describeTilePort(stream.src.tile, stream.src.port) << " -> "
1322 << describeTilePort(stream.dst.tile, stream.dst.port);
1323 if (stream.packetID)
1324 os << " (id " << *stream.packetID << ")";
1325 return s;
1326}
1327
1329 : device(device), streams(requestedStreams(device)),
1330 numRequested(streams.size()) {
1331 for (RoutedStream &s : traceRoutedStreams(device))
1332 streams.push_back(std::move(s));
1333 std::map<TreeKey, size_t> treeIDs;
1334 for (size_t i = 0; i < streams.size(); i++) {
1335 size_t tree = treeMembers.size();
1336 if (std::optional<TreeKey> key = treeKey(i))
1337 tree = treeIDs.try_emplace(*key, tree).first->second;
1338 if (tree == treeMembers.size())
1339 treeMembers.emplace_back();
1340 treeMembers[tree].push_back(i);
1341 treeOf.push_back(tree);
1342 }
1343 waits.resize(treeMembers.size());
1344}
1345
1346std::optional<StreamConflicts::TreeKey>
1347StreamConflicts::treeKey(size_t s) const {
1348 const RoutedStream &stream = streams[s];
1349 if (!stream.packetID)
1350 return std::nullopt;
1351 return TreeKey{stream.src.tile, stream.src.port, *stream.packetID,
1352 s < numRequested};
1353}
1354
1355const StreamDeadlockAnalysis &StreamConflicts::getAnalysis() const {
1356 if (!analysis)
1357 analysis.emplace(device, streams);
1358 return *analysis;
1359}
1360
1361bool StreamConflicts::blocks(size_t s, size_t t) const {
1362 const RoutedStream &a = streams[s], &b = streams[t];
1363 if (a.src == b.src || a.dst == b.dst)
1364 return false;
1365 return getAnalysis().canBlock(s, t);
1366}
1367
1368// Trees from one source, or into one receiver, already wait on each other
1369// there whatever the routing.
1370bool StreamConflicts::related(size_t s, size_t t) const {
1371 if (streams[s].src == streams[t].src)
1372 return true;
1373 for (size_t m : treeMembers[treeOf[s]])
1374 for (size_t n : treeMembers[treeOf[t]])
1375 if (streams[m].dst == streams[n].dst)
1376 return true;
1377 return false;
1378}
1379
1380bool StreamConflicts::conflict(size_t s, size_t t) const {
1381 return !related(s, t) && (blocks(s, t) || blocks(t, s));
1382}
1383
1384// The chains holdCycle follows from a tree stuck at a receiver to the trees
1385// it waits on, which hold for any routing.
1386const DenseMap<size_t, std::pair<size_t, size_t>> &
1387StreamConflicts::waitsFrom(size_t a) const {
1388 std::optional<DenseMap<size_t, std::pair<size_t, size_t>>> &cached = waits[a];
1389 if (cached)
1390 return *cached;
1391 DenseMap<size_t, std::pair<size_t, size_t>> &reached = cached.emplace();
1392 std::deque<size_t> work{a};
1393 while (!work.empty()) {
1394 size_t u = work.front();
1395 work.pop_front();
1396 for (size_t g = 0; g < treeMembers.size(); g++) {
1397 if (g == a || reached.contains(g) ||
1398 !streams[treeMembers[g].front()].packetID)
1399 continue;
1400 auto by = [&]() -> std::optional<std::pair<size_t, size_t>> {
1401 for (size_t x : treeMembers[u])
1402 for (size_t m : treeMembers[g])
1403 if (blocks(x, m))
1404 return std::pair{x, m};
1405 return std::nullopt;
1406 }();
1407 if (!by)
1408 continue;
1409 reached[g] = *by;
1410 work.push_back(g);
1411 }
1412 }
1413 return reached;
1414}
1415
1416bool StreamConflicts::mustSeparate(size_t s, size_t t) const {
1417 if (related(s, t))
1418 return false;
1419 return blocks(s, t) || blocks(t, s) ||
1420 waitsFrom(treeOf[s]).contains(treeOf[t]) ||
1421 waitsFrom(treeOf[t]).contains(treeOf[s]);
1422}
1423
1424std::string StreamConflicts::explain(size_t s, size_t t) const {
1425 const StreamDeadlockAnalysis &a = getAnalysis();
1426 if (a.canBlock(s, t))
1427 return a.explainBlock(s, t);
1428 if (a.canBlock(t, s))
1429 return a.explainBlock(t, s);
1430 if (!waitsFrom(treeOf[s]).contains(treeOf[t]))
1431 std::swap(s, t);
1432 SmallVector<std::string> steps;
1433 for (size_t g = treeOf[t]; g != treeOf[s];) {
1434 auto [x, m] = waitsFrom(treeOf[s]).at(g);
1435 steps.push_back(a.explainBlock(x, m));
1436 g = treeOf[x];
1437 }
1438 std::reverse(steps.begin(), steps.end());
1439 return llvm::join(steps, " ");
1440}
1441
1442SmallVector<std::pair<size_t, size_t>> StreamConflicts::unavoidable() const {
1443 SmallVector<std::pair<size_t, size_t>> pairs;
1444 const StreamDeadlockAnalysis &a = getAnalysis();
1445 for (size_t s = 0; s < numRequested; s++)
1446 for (size_t t = 0; t < numRequested; t++) {
1447 // A tree's branches move as one, as a circuit broadcast's do, so a wait
1448 // between them is the design's own.
1449 if (s == t || treeOf[s] == treeOf[t] ||
1450 !(streams[s].packetID || streams[t].packetID) || !related(s, t) ||
1451 !a.canBlock(s, t))
1452 continue;
1453 if (a.assumptions(s, t).empty())
1454 pairs.push_back({s, t});
1455 else
1456 LLVM_DEBUG(llvm::dbgs() << "Unavoidable only by assumption: "
1457 << a.explainBlock(s, t) << "\n");
1458 }
1459 return pairs;
1460}
1461
1462namespace {
1463// A wait in the graph holdCycle searches: a head stuck at one node waits on
1464// one at `to`, for the reason `step` gives, if any.
1465struct WaitEdge {
1466 size_t to;
1467 std::optional<HoldCycle::Step> step;
1468 // For a link wait, each switchbox and arbiter above the link that granted
1469 // both trees it in turn.
1470 SmallVector<std::pair<TileID, int>, 4> orders = {};
1471};
1472// The graph holdCycle searches, built as it is walked. Node `entry` leads to
1473// every root.
1474struct WaitGraph {
1475 llvm::function_ref<ArrayRef<WaitEdge>(size_t)> successors;
1476 size_t entry;
1477};
1478using WaitNode = std::pair<const WaitGraph *, size_t>;
1479} // namespace
1480
1481namespace llvm {
1482template <>
1483struct GraphTraits<const WaitGraph *> {
1484 using NodeRef = WaitNode;
1485 struct ToNode {
1486 const WaitGraph *graph;
1487 NodeRef operator()(const WaitEdge &e) const { return {graph, e.to}; }
1488 };
1489 using ChildIteratorType = mapped_iterator<const WaitEdge *, ToNode>;
1490 static NodeRef getEntryNode(const WaitGraph *g) { return {g, g->entry}; }
1492 return map_iterator(n.first->successors(n.second).begin(), ToNode{n.first});
1493 }
1495 return map_iterator(n.first->successors(n.second).end(), ToNode{n.first});
1496 }
1497};
1498} // namespace llvm
1499
1500std::optional<HoldCycle>
1501StreamConflicts::holdCycle(ArrayRef<SmallVector<StreamHop, 8>> routes,
1502 bool forcedWaits, bool definite) const {
1503 // The packets one source sends with one id move down every branch as one.
1504 struct Tree {
1505 SmallVector<size_t, 2> members;
1506 SmallVector<std::pair<TileID, Port>, 8> hops;
1507 SmallVector<int, 8> parent;
1508 SmallVector<std::optional<int>, 8> arbiter;
1509 size_t base = 0;
1510 };
1511 std::vector<Tree> trees;
1512 std::map<TreeKey, size_t> treeIDs;
1513 for (size_t i = 0; i < streams.size(); i++) {
1514 std::optional<TreeKey> key = treeKey(i);
1515 if (!key || getAnalysis().silent(i))
1516 continue;
1517 auto [it, inserted] = treeIDs.try_emplace(*key, trees.size());
1518 if (inserted)
1519 trees.emplace_back();
1520 Tree &tree = trees[it->second];
1521 tree.members.push_back(i);
1522 int prev = -1;
1523 for (const StreamHop &hop : routes[i]) {
1524 std::pair<TileID, Port> key{hop.tile, hop.input};
1525 int h = llvm::find(tree.hops, key) - tree.hops.begin();
1526 if (h == static_cast<int>(tree.hops.size())) {
1527 tree.hops.push_back(key);
1528 tree.parent.push_back(prev);
1529 tree.arbiter.push_back(hop.arbiter);
1530 }
1531 prev = h;
1532 }
1533 }
1534
1535 // One source sends one tree's packet at a time. Trees into one receiver are
1536 // both in flight at once, and wait on each other at its master port however
1537 // they are routed, where both enter its switchbox for it; and trees with one
1538 // id wait on each other where they meet and below, going on as one. Those
1539 // waits count only with `forcedWaits`.
1540 auto sameSource = [&](size_t a, size_t b) {
1541 return streams[trees[a].members.front()].src ==
1542 streams[trees[b].members.front()].src;
1543 };
1544 auto forced = [&](size_t a, int ha, size_t b, int hb, TileID tile) {
1545 Port ina = trees[a].hops[ha].second, inb = trees[b].hops[hb].second;
1546 auto into = [&](size_t m, Port in) {
1547 return streams[m].dst.tile == tile && !routes[m].empty() &&
1548 routes[m].back().tile == tile && routes[m].back().input == in;
1549 };
1550 for (size_t m : trees[a].members)
1551 for (size_t n : trees[b].members)
1552 if (streams[m].dst == streams[n].dst && into(m, ina) && into(n, inb))
1553 return true;
1554 if (streams[trees[a].members.front()].packetID !=
1555 streams[trees[b].members.front()].packetID)
1556 return false;
1557 for (auto above : llvm::enumerate(trees[a].parent))
1558 if (above.value() == ha &&
1559 llvm::any_of(llvm::enumerate(trees[b].parent), [&](auto below) {
1560 return below.value() == hb &&
1561 trees[b].hops[below.index()] == trees[a].hops[above.index()];
1562 }))
1563 return true;
1564 return false;
1565 };
1566
1567 // Per tree, a node for a head of it stuck entering each hop or at each
1568 // receiver, one for it stuck anywhere, and one per hop for it stuck
1569 // anywhere past that hop, so still holding what it took there.
1570 enum class Kind { Hop, Receiver, Anywhere, Past };
1571 struct Node {
1572 size_t tree;
1573 Kind kind;
1574 size_t index;
1575 };
1576 std::vector<Node> nodes;
1577 for (size_t t = 0; t < trees.size(); t++) {
1578 Tree &tree = trees[t];
1579 tree.base = nodes.size();
1580 for (size_t h = 0; h < tree.hops.size(); h++)
1581 nodes.push_back({t, Kind::Hop, h});
1582 for (size_t m = 0; m < tree.members.size(); m++)
1583 nodes.push_back({t, Kind::Receiver, m});
1584 nodes.push_back({t, Kind::Anywhere, 0});
1585 for (size_t h = 0; h < tree.hops.size(); h++)
1586 nodes.push_back({t, Kind::Past, h});
1587 }
1588 auto receiverNode = [&](size_t t, size_t m) {
1589 return trees[t].base + trees[t].hops.size() + m;
1590 };
1591 auto anywhereNode = [&](size_t t) {
1592 return receiverNode(t, trees[t].members.size());
1593 };
1594 auto pastNode = [&](size_t t, size_t h) { return anywhereNode(t) + 1 + h; };
1595
1596 std::map<std::pair<TileID, Port>, SmallVector<std::pair<size_t, size_t>, 4>>
1597 entering;
1598 std::map<TileID, SmallVector<std::pair<size_t, size_t>, 8>> passing;
1599 for (size_t t = 0; t < trees.size(); t++)
1600 for (size_t h = 0; h < trees[t].hops.size(); h++) {
1601 entering[trees[t].hops[h]].push_back({t, h});
1602 passing[trees[t].hops[h].first].push_back({t, h});
1603 }
1604
1605 // The arbiters that granted two trees a hop they share in one order: the
1606 // one both took to leave the switchbox above it where they came into it
1607 // apart. Also each arbiter on their shared path below it, provided each
1608 // tree passes it only once.
1609 using Grant = std::pair<TileID, int>;
1610 auto orderedBy = [&](size_t a, int ha, size_t b, int hb) {
1611 SmallVector<Grant, 4> grants;
1612 auto once = [&](size_t t, const Grant &g) {
1613 return llvm::count_if(llvm::seq<size_t>(0, trees[t].hops.size()),
1614 [&](size_t h) {
1615 return trees[t].hops[h].first == g.first &&
1616 trees[t].arbiter[h] == g.second;
1617 }) == 1;
1618 };
1619 for (;;) {
1620 int pa = trees[a].parent[ha], pb = trees[b].parent[hb];
1621 if (pa < 0 || pb < 0)
1622 return grants;
1623 std::optional<int> arbiter = trees[a].arbiter[pa];
1624 bool shared = trees[a].hops[pa] == trees[b].hops[pb];
1625 if (trees[a].hops[pa].first == trees[b].hops[pb].first && arbiter &&
1626 arbiter == trees[b].arbiter[pb]) {
1627 Grant g{trees[a].hops[pa].first, *arbiter};
1628 if (!shared)
1629 grants.insert(grants.begin(), g);
1630 else if (once(a, g) && once(b, g))
1631 grants.push_back(g);
1632 }
1633 if (!shared)
1634 return grants;
1635 ha = pa;
1636 hb = pb;
1637 }
1638 };
1639
1640 using Edge = WaitEdge;
1641 SmallVector<size_t> roots;
1642 std::vector<std::optional<SmallVector<Edge, 4>>> edges(nodes.size() + 1);
1643 auto successors = [&](size_t n) -> ArrayRef<Edge> {
1644 if (edges[n])
1645 return *edges[n];
1646 SmallVector<Edge, 4> out;
1647 if (n == nodes.size()) {
1648 for (size_t root : roots)
1649 out.push_back({root, std::nullopt});
1650 return *(edges[n] = std::move(out));
1651 }
1652 const Node &node = nodes[n];
1653 const Tree &u = trees[node.tree];
1654 switch (node.kind) {
1655 case Kind::Hop: {
1656 auto [tile, input] = u.hops[node.index];
1657 size_t waiting = u.members.front();
1658 for (auto [t, ht] : entering.at({tile, input})) {
1659 if (t != node.tree && sameSource(node.tree, t))
1660 continue;
1661 size_t sharer = trees[t].members.front();
1662 bool sameId = streams[waiting].packetID == streams[sharer].packetID;
1663 if (t != node.tree && (!sameId || forcedWaits))
1664 out.push_back(
1665 {pastNode(t, ht),
1666 HoldCycle::Step{HoldCycle::Wait::Link, waiting, sharer, sharer,
1667 tile, input, input, -1, sameId},
1668 orderedBy(node.tree, node.index, t, ht)});
1669 std::optional<int> arbiter = trees[t].arbiter[ht];
1670 if (!arbiter)
1671 continue;
1672 // A tree's branches move as one, so where two come into a switchbox
1673 // apart onto one arbiter, the one holding it waits on the other.
1674 for (auto [v, hv] : passing.at(tile)) {
1675 Port holderInput = trees[v].hops[hv].second;
1676 bool self = v == node.tree && t == node.tree;
1677 if ((!self && (v == node.tree || v == t || sameSource(t, v))) ||
1678 holderInput == input || trees[v].arbiter[hv] != arbiter)
1679 continue;
1680 bool isForced = !self && forced(t, ht, v, hv, tile);
1681 if (isForced && !forcedWaits)
1682 continue;
1683 out.push_back(
1684 {pastNode(v, hv),
1686 trees[v].members.front(), tile, input,
1687 holderInput, *arbiter, isForced}});
1688 }
1689 }
1690 break;
1691 }
1692 case Kind::Receiver: {
1693 // A tree into the full receiver is stuck there however it is routed.
1694 size_t s = u.members[node.index];
1695 for (size_t g = 0; g < trees.size(); g++) {
1696 if (g == node.tree || llvm::any_of(trees[g].members, [&](size_t m) {
1697 return streams[m].dst == streams[s].dst;
1698 }))
1699 continue;
1700 for (size_t m : trees[g].members)
1701 if (blocks(s, m) &&
1702 (!definite || getAnalysis().assumptions(s, m).empty())) {
1703 out.push_back({anywhereNode(g),
1705 TileID{}, Port{}, Port{}, -1}});
1706 break;
1707 }
1708 }
1709 break;
1710 }
1711 case Kind::Anywhere:
1712 case Kind::Past: {
1713 llvm::SmallDenseSet<size_t, 8> behind;
1714 if (node.kind == Kind::Past)
1715 for (int h = node.index; h >= 0; h = u.parent[h])
1716 behind.insert(h);
1717 for (size_t h = 0; h < u.hops.size(); h++)
1718 if (!behind.contains(h))
1719 out.push_back({u.base + h, std::nullopt});
1720 for (size_t m = 0; m < u.members.size(); m++)
1721 out.push_back({receiverNode(node.tree, m), std::nullopt});
1722 break;
1723 }
1724 }
1725 return *(edges[n] = std::move(out));
1726 };
1727
1728 // A cycle of receivers alone waiting on each other is the design's own, so
1729 // only cycles through a wait some requested routing adds count.
1730 auto counts = [&](const Edge &e) {
1731 if (!e.step || e.step->wait == HoldCycle::Wait::Drain)
1732 return false;
1733 return e.step->waiting < numRequested || e.step->sharer < numRequested ||
1734 e.step->holding < numRequested;
1735 };
1736 for (size_t n = 0; n < nodes.size(); n++)
1737 if (nodes[n].kind == Kind::Hop && llvm::any_of(successors(n), counts))
1738 roots.push_back(n);
1739
1740 const WaitGraph graph{successors, nodes.size()};
1741 std::vector<int> component(nodes.size() + 1, -1);
1742 int components = 0;
1743 for (auto scc = llvm::scc_begin(&graph); !scc.isAtEnd(); ++scc, ++components)
1744 for (WaitNode n : *scc)
1745 component[n.second] = components;
1746
1747 // A counted wait within one component lies on a closed walk. No state has two
1748 // trees holding one arbiter (see HoldCycle), so a walk that needs that is no
1749 // deadlock. Nor is one where each packet is behind the next on links one
1750 // arbiter granted them all in one order, so a walk from a link wait must,
1751 // for each arbiter that ordered that link, also wait otherwise. The search
1752 // fixes or rules out a holder per arbiter until the shortest walk left
1753 // agrees. Each clash splits it in two, so past maxWalkSearches it keeps the
1754 // first walk, which at worst steers the router off a routing that cannot
1755 // deadlock.
1756 struct Holders {
1757 std::optional<size_t> fixed;
1758 SmallVector<size_t, 2> excluded;
1759 };
1760 using Constraints = std::map<Grant, Holders>;
1761 auto allowed = [](const Edge &edge, const Constraints &c) {
1762 if (!edge.step || edge.step->wait != HoldCycle::Wait::Arbiter)
1763 return true;
1764 auto it = c.find({edge.step->tile, edge.step->arbiter});
1765 if (it == c.end())
1766 return true;
1767 size_t holder = edge.step->holding;
1768 return it->second.fixed ? *it->second.fixed == holder
1769 : !llvm::is_contained(it->second.excluded, holder);
1770 };
1771 // Arbiters past these that ordered a link go untracked, which at worst steers
1772 // the router off a routing that cannot deadlock.
1773 constexpr size_t maxOrders = 8;
1774 auto closeWalk =
1775 [&](size_t x, const Edge &e,
1776 const Constraints &c) -> std::optional<SmallVector<const Edge *>> {
1777 if (!allowed(e, c))
1778 return std::nullopt;
1779 // A state is a node and, per arbiter that ordered e's link, whether the
1780 // walk there has waited other than on a link it ordered too.
1781 size_t k = std::min<size_t>(e.orders.size(), maxOrders);
1782 auto unordered = [&](const Edge &edge) {
1783 size_t mask = 0;
1784 for (size_t i = 0; i < k; i++)
1785 if (edge.step && !llvm::is_contained(edge.orders, e.orders[i]))
1786 mask |= size_t(1) << i;
1787 return mask;
1788 };
1789 size_t all = (size_t(1) << k) - 1;
1790 auto state = [&](size_t node, size_t mask) { return (node << k) | mask; };
1791 size_t start = state(e.to, 0), end = state(x, all);
1792 DenseMap<size_t, std::pair<size_t, const Edge *>> via;
1793 via[start] = {start, nullptr};
1794 std::deque<size_t> worklist{start};
1795 while (!via.contains(end)) {
1796 if (worklist.empty())
1797 return std::nullopt;
1798 size_t n = worklist.front();
1799 worklist.pop_front();
1800 for (const Edge &next : successors(n >> k)) {
1801 size_t to = state(next.to, (n & all) | unordered(next));
1802 if (component[next.to] == component[x] && allowed(next, c) &&
1803 via.try_emplace(to, n, &next).second)
1804 worklist.push_back(to);
1805 }
1806 }
1807 SmallVector<const Edge *> path;
1808 for (size_t n = end; n != start; n = via.at(n).first)
1809 path.push_back(via.at(n).second);
1810 path.push_back(&e);
1811 std::reverse(path.begin(), path.end());
1812 return path;
1813 };
1814 auto toCycle = [](ArrayRef<const Edge *> path) {
1815 HoldCycle cycle;
1816 for (const Edge *edge : path)
1817 if (edge->step)
1818 cycle.steps.push_back(*edge->step);
1819 return cycle;
1820 };
1821 constexpr int maxWalkSearches = 1024;
1822 for (size_t x : roots)
1823 for (const Edge &e : successors(x)) {
1824 if (!counts(e) || component[e.to] != component[x])
1825 continue;
1826 std::optional<SmallVector<const Edge *>> first;
1827 SmallVector<Constraints> pending{{}};
1828 int search = 0;
1829 for (; !pending.empty(); search++) {
1830 if (search == maxWalkSearches) {
1831 assert(first && "only a walk found adds pending constraints");
1832 LLVM_DEBUG(llvm::dbgs() << "Hold cycle search gave up after "
1833 << search << " walks\n");
1834 return toCycle(*first);
1835 }
1836 Constraints c = pending.pop_back_val();
1837 std::optional<SmallVector<const Edge *>> path = closeWalk(x, e, c);
1838 if (!path)
1839 continue;
1840 if (!first)
1841 first = path;
1842 std::map<Grant, size_t> held;
1843 std::optional<std::pair<Grant, size_t>> clash;
1844 for (const Edge *edge : *path) {
1845 if (!edge->step || edge->step->wait != HoldCycle::Wait::Arbiter)
1846 continue;
1847 auto [it, inserted] = held.try_emplace(
1848 {edge->step->tile, edge->step->arbiter}, edge->step->holding);
1849 if (!inserted && it->second != edge->step->holding) {
1850 clash = *it;
1851 break;
1852 }
1853 }
1854 if (!clash) {
1855 LLVM_DEBUG(llvm::dbgs() << "Hold cycle search closed a walk after "
1856 << search + 1 << " walks\n");
1857 return toCycle(*path);
1858 }
1859 Constraints fix = c, exclude = c;
1860 fix[clash->first].fixed = clash->second;
1861 exclude[clash->first].excluded.push_back(clash->second);
1862 pending.push_back(std::move(exclude));
1863 pending.push_back(std::move(fix));
1864 }
1865 LLVM_DEBUG(llvm::dbgs() << "Hold cycle search closed no walk after "
1866 << search << " walks\n");
1867 }
1868 return std::nullopt;
1869}
1870
1871std::string StreamConflicts::explain(const HoldCycle &cycle) const {
1872 std::string s;
1873 llvm::raw_string_ostream os(s);
1874 for (auto [i, step] : llvm::enumerate(cycle.steps)) {
1875 if (i)
1876 os << ' ';
1877 switch (step.wait) {
1879 os << describeStream(streams[step.waiting]) << " can queue behind "
1880 << describeStream(streams[step.holding]) << " on "
1881 << describePort(step.sharerInput) << " into tile (" << step.tile.col
1882 << ", " << step.tile.row << ").";
1883 break;
1885 os << describeStream(streams[step.holding]) << " can hold arbiter "
1886 << step.arbiter << " at tile (" << step.tile.col << ", "
1887 << step.tile.row << ") that " << describeStream(streams[step.sharer])
1888 << " needs";
1889 if (step.waiting != step.sharer)
1890 os << ", and " << describeStream(streams[step.waiting])
1891 << " can queue behind it";
1892 os << ".";
1893 break;
1895 os << getAnalysis().explainBlock(step.waiting, step.holding);
1896 break;
1897 }
1898 }
1899 return s;
1900}
constexpr int maxBDSteps
bool isShimNOCorPLTile(int col, int row) const
Return true if the given tile is either a ShimNOC or ShimPL tile.
bool hasProperty(ModelProperty Prop) const
llvm::SmallVector< std::pair< size_t, size_t > > unavoidable() const
The requested streams where the first can hold up the second however they are routed,...
bool mustSeparate(size_t s, size_t t) const
Whether a routing that puts packet streams s and t on one arbiter anywhere has a hold cycle: they con...
bool conflict(size_t s, size_t t) const
Whether s and t can deadlock if they share an arbiter or a link.
std::optional< HoldCycle > holdCycle(llvm::ArrayRef< llvm::SmallVector< StreamHop, 8 > > routes, bool forcedWaits=false, bool definite=false) const
A cycle of waits the packet streams can deadlock in when routed along routes, indexed like getStreams...
std::string explain(size_t s, size_t t) const
Why s and t conflict.
Which streams can deadlock against each other if they share an arbiter or a link.
bool canBlock(size_t f, size_t g) const
Whether stream f, stalled at its receiver, can keep stream g from ever arriving: f carries more than ...
std::string explainBlock(size_t f, size_t g) const
Why f can block g: the chain of waits from f's receiver to g, and which links of it are assumed for l...
bool silent(size_t f) const
Whether stream f carries nothing, so it neither holds nor waits.
llvm::SmallVector< std::string > assumptions(size_t f, size_t g) const
What explainBlock(f, g) takes on trust rather than reads off the design, one sentence each.
StreamDeadlockAnalysis(DeviceOp device, llvm::ArrayRef< RoutedStream > streams)
streams must outlive the analysis.
How much data a stream carries over a run and how much a receiver takes in before it has to wait on a...
StreamVolumeAnalysis(DeviceOp device, llvm::ArrayRef< RoutedStream > streams)
std::optional< uint64_t > sendVolume(const RoutedStream &stream) const
Bytes the stream's source sends with the stream's packet id, headers included where the receiver keep...
std::optional< uint64_t > receiveCapacity(const StreamEndpoint &endpoint) const
Bytes the receiver at endpoint accepts before it waits on another agent, or nullopt when it never doe...
bool canFill(const StreamEndpoint &endpoint, llvm::ArrayRef< RoutedStream > streams) const
Whether streams can send the receiver at endpoint more than it takes in before it waits on another ag...
std::optional< bool > maySendAfter(const RoutedStream &first, const RoutedStream &then) const
Whether the source both streams come from can send a packet of then after one of first; nullopt if it...
std::optional< unsigned > agentAt(const StreamEndpoint &endpoint, bool sending) const
The agent pushing data into (sending) or pulling data out of the fabric at endpoint,...
std::string describe(unsigned id) const
llvm::SmallVector< unsigned > waitChain(llvm::ArrayRef< unsigned > from, llvm::ArrayRef< unsigned > targets, llvm::ArrayRef< unsigned > avoid) const
A shortest chain of waits from an agent in from to one in targets that avoids avoid,...
llvm::SmallVector< unsigned > drainersOf(unsigned agent) const
Agents whose progress frees room in agent for more incoming data: a core frees itself,...
StreamWaitGraph(DeviceOp device, llvm::ArrayRef< RoutedStream > streams, const StreamVolumeAnalysis &volumes)
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
bool isDirectional(WireBundle bundle)
Definition AIEDialect.h:525
std::string describeStream(const RoutedStream &stream)
Names the stream by its endpoints and packet id, e.g.
const AIETargetModel & getTargetModel(mlir::Operation *op)
bool keepsPktHeader(TileID tile, Port master, std::optional< bool > keep)
std::vector< RoutedStream > requestedStreams(DeviceOp device)
The streams the aie.flow and aie.packet_flow ops ask for, one per source, destination and packet id,...
std::vector< RoutedStream > traceRoutedStreams(DeviceOp device)
Follows every stream from its source tile port through the configured switchboxes,...
std::string describeTilePort(TileID tile, Port port)
Names a tile port the way diagnostics do, e.g. "(0, 2) DMA:1".
struct Port { WireBundle bundle; int channel; bool operator==(const Port &rhs) const { return std::tie(bundle, channel)==std::tie(rhs.bundle, rhs.channel); } bool operator!=(const Port &rhs) const { return !(*this==rhs);} bool operator<(const Port &rhs) const { return std::tie(bundle, channel)< std::tie(rhs.bundle, rhs.channel); } friend std::ostream &operator<<(std::ostream &os, const Port &port) { os<< "("; os<< stringifyWireBundle(port.bundle).str(); os<< ": "<< std::to_string(port.channel)<< ")"; return os; } friend llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const Port &port) { os<< to_string(port); return os; } } Port
Definition AIEDialect.h:265
std::string describePort(Port port)
Names a port the way diagnostics do, e.g. "DMA:1".
static ChildIteratorType child_begin(NodeRef n)
mapped_iterator< const WaitEdge *, ToNode > ChildIteratorType
The BD chain a DMA channel runs, as one aie.dma_start, aie.dma or runtime task programs it.
llvm::SmallVector< mlir::Region * > regions
uint64_t passes
Times one start of the channel runs the chain: its repeat count plus one.
bool loops
Whether the BD chain runs forever.
size_t loopStart
The first of bds a looping chain returns to once it has run them all.
llvm::SmallVector< mlir::Block * > bds
A cycle of waits packet streams can deadlock in, given their routes.
llvm::SmallVector< Step, 4 > steps
@ Drain
waiting fills its receiver, and draining that waits on holding.
@ Link
waiting queues behind holding on the port both enter tile by.
@ Arbiter
waiting, or sharer it queues behind, needs the arbiter holding holds at tile; sharer enters by sharer...
One stream from a source tile port to a destination tile port, recovered from the physical switchbox ...
bool carries(std::optional< PacketInfoAttr > packet) const
Whether what a BD sends with header packet, or with none, goes on this stream.
int packetMask
The stream carries every id that agrees with packetID on these bits.
bool keepsPktHeader
The destination stores each packet's header along with its payload.
std::optional< int > packetID
The packet id carried, if any.
A tile port at the edge of the stream fabric.
A switchbox a stream passes: the port it enters by and, where it is packet switched there,...
A core, a DMA channel, or a tile's controller.
static std::optional< Agent > at(const StreamEndpoint &endpoint, bool sending)
Each agent at a stream endpoint: the core, DMA channel or controller pushing data into (sending) or p...
static Agent channel(const TileDMAChannel &dma)