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"
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"
32#define DEBUG_TYPE "aie-stream-dependency"
40std::optional<TileID> tileOf(Value tile) {
41 if (
auto tileOp = dyn_cast_or_null<TileOp>(tile.getDefiningOp()))
42 return tileOp.getTileID();
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());
52 if (
auto start = dyn_cast<DMAStartOp>(op)) {
53 std::optional<TileID> tile = parentTile(op);
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) {
67 auto next = dyn_cast<NextBDOp>(b->getTerminator());
68 b = next ? next.getDest() :
nullptr;
72 if (
auto dma = dyn_cast<DMAOp>(op)) {
73 std::optional<TileID> tile = parentTile(op);
77 {*tile, dma.getChannelDir(), dma.getChannelIndex()}};
78 p.
passes += dma.getRepeatCount();
79 for (Region &r : dma.getBds())
81 p.
loops = dma.getLoop();
84 if (
auto task = dyn_cast<AIEX::DMAConfigureTaskOp>(op)) {
85 std::optional<TileID> tile = tileOf(task.getTile());
89 op, {*tile, task.getDirection(),
static_cast<int>(task.getChannel())}};
90 p.
regions.push_back(&task.getBody());
91 p.
passes += task.getRepeatCount();
94 if (
auto task = dyn_cast<AIEX::DMAConfigureTaskForOp>(op)) {
95 auto alloc = ShimDMAAllocationOp::getForSymbol(
96 device, task.getAlloc().getRootReference());
99 std::optional<TileID> tile = tileOf(alloc.getTile());
103 {*tile, alloc.getChannelDir(),
104 static_cast<int>(alloc.getChannelIndex())}};
105 p.
regions.push_back(&task.getBody());
106 p.
passes += task.getRepeatCount();
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));
125template <
typename OpT>
127 llvm::function_ref<
void(OpT)> fn) {
128 for (Block *b : p.
bds)
129 for (
auto op : b->getOps<OpT>())
132 r->walk([&](OpT op) { fn(op); });
135std::optional<TileDMAChannel> channelOfSymbol(DeviceOp device,
137 auto alloc = ShimDMAAllocationOp::getForSymbol(device, symbol);
140 std::optional<TileID> tile = tileOf(alloc.getTile());
144 static_cast<int>(alloc.getChannelIndex())};
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)
158 Operation *op = v.getDefiningOp();
159 if (isa_and_nonnull<AIEX::DMAConfigureTaskOp, AIEX::DMAConfigureTaskForOp,
160 AIEX::DMAStartBdChainOp, AIEX::DMAStartBdChainForOp>(
162 creators.push_back(op);
166 op ? op : cast<BlockArgument>(v).getOwner()->getParentOp();
167 auto branch = dyn_cast_or_null<RegionBranchOpInterface>(owner);
170 RegionBranchInverseSuccessorMapping mapping;
171 branch.getSuccessorInputOperandMapping(mapping);
172 auto it = mapping.find(v);
173 if (it == mapping.end())
175 for (OpOperand *operand : it->second)
176 worklist.push_back(operand->get());
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))
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());
201 if (!llvm::is_contained(keys, *key))
202 keys.push_back(*key);
210void walkLoopsTwice(Region ®ion, function_ref<
void(Operation *)> fn) {
211 for (Operation &op : region.getOps()) {
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);
222std::map<TileDMAChannel, std::set<int>> collectSentPacketIDs(DeviceOp device) {
223 std::map<TileDMAChannel, std::set<int>> ids;
225 if (p.
dma.
dir != DMAChannelDir::MM2S)
227 forEachInProgram<DMABDOp>(p, [&](DMABDOp bd) {
228 if (std::optional<PacketInfoAttr> packet = bd.getPacket())
229 ids[p.
dma].insert(packet->assignedId());
232 for (
auto alloc : device.getOps<ShimDMAAllocationOp>()) {
233 std::optional<PacketInfoAttr> packet = alloc.getPacket();
234 std::optional<TileID> tile = tileOf(alloc.getTile());
236 ids[{*tile, alloc.getChannelDir(),
237 static_cast<int>(alloc.getChannelIndex())}]
238 .insert(packet->assignedId());
240 device.walk([&](AIEX::NpuDmaMemcpyNdOp memcpy) {
241 std::optional<PacketInfoAttr> packet = memcpy.getPacket();
244 if (std::optional<TileDMAChannel> key =
245 channelOfSymbol(device, memcpy.getMetadata().getRootReference()))
246 ids[*key].insert(packet->assignedId());
253 explicit StreamTracer(DeviceOp device)
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);
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()))
270 traceFrom({tile, p}, sb, p);
271 return std::move(streams);
276 Interconnect interconnect;
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))
295 std::optional<std::set<int>> ids;
297 if (src.
port.bundle == WireBundle::DMA) {
298 auto it = sentIDs.find({src.
tile, DMAChannelDir::MM2S, src.
port.channel});
299 if (it != sentIDs.end())
303 step(src, {interconnect, input}, std::nullopt);
307 step(src, {interconnect, input}, id);
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}};
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}};
326 WireBundle in = WireBundle::South;
327 switch (out.bundle) {
328 case WireBundle::North:
330 in = WireBundle::South;
332 case WireBundle::South:
334 in = WireBundle::North;
336 case WireBundle::East:
338 in = WireBundle::West;
342 in = WireBundle::East;
345 if (
auto sb = switchboxes.find(next); sb != switchboxes.end())
346 return Hop{sb->second, {in, out.channel}};
353 std::pair<Operation *, Port> input{hop.interconnect, hop.input};
354 if (!onPath.insert(input).second)
356 llvm::scope_exit leave([&] { onPath.erase(input); });
357 auto sb = dyn_cast<SwitchboxOp>(hop.interconnect.getOperation());
358 Block &b = hop.interconnect.getConnections().front();
360 auto next = [&](
Port out, std::optional<int> nextID,
363 path.push_back({sb.getTileOp().getTileID(), hop.input, arbiter});
364 llvm::scope_exit backtrack([&] {
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});
372 step(src, std::get<Hop>(to), nextID);
375 for (
auto connect : b.getOps<ConnectOp>())
376 if (connect.sourcePort() == hop.input)
377 next(connect.destPort(),
id, std::nullopt);
379 for (
auto rules : b.getOps<PacketRulesOp>()) {
380 if (rules.sourcePort() != hop.input)
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());
391 for (
int packetID =
id.value_or(0); packetID <=
id.value_or(maxPacketID);
393 for (
auto rule : rules.getRules().front().getOps<PacketRuleOp>())
394 if ((packetID & rule.maskInt()) ==
395 (rule.valueInt() & rule.maskInt())) {
396 route(rule, packetID);
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;
408 llvm::DenseSet<std::pair<Operation *, Port>> onPath;
409 SmallVector<StreamHop, 8> path;
416 return StreamTracer(device).trace();
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)
426 {{*srcTile, {flow.getSourceBundle(), flow.sourceIndex()}},
427 {*dstTile, {flow.getDestBundle(), flow.destIndex()}},
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());
443 for (
auto dst : b.getOps<PacketDestOp>())
444 if (std::optional<TileID> dstTile = tileOf(dst.getTile()))
446 {{*srcTile, src.port()},
447 {*dstTile, dst.port()},
450 keepAt.lookup({*dstTile, dst.port()})),
452 static_cast<int>(flow.getMask().value_or(~0))});
459 ArrayRef<RoutedStream> streams)
460 : device(device), streams(streams) {
462 programs[p.dma].push_back(std::move(p));
463 for (
const auto &[dma, channelPrograms] : programs)
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);
475static SmallVector<Block *> chainBlocks(
const DmaChannelProgram &p) {
476 SmallVector<Block *> sequence(p.
bds);
478 sequence.push_back(&r->front());
485static size_t blockAt(
const DmaChannelProgram &p,
size_t size, uint64_t step) {
489 return start + (step - start) % (size - start);
493static std::optional<int64_t> lockAmount(UseLockOp use) {
495 if (!use.getLock().getDefiningOp<LockOp>() ||
496 !matchPattern(use.getValue(), m_ConstantInt(&amount)))
498 return amount.getSExtValue();
502static std::optional<uint64_t> lockTokens(UseLockOp use) {
503 std::optional<int64_t> n = lockAmount(use);
511std::optional<uint64_t>
513 if (stream.
src.
port.bundle != WireBundle::DMA)
517 constexpr uint64_t pktHeaderBytes = 4;
518 auto headerBytes = [&](std::optional<PacketInfoAttr> packet) -> uint64_t {
521 auto bytesOf = [&](DMABDOp bd) -> uint64_t {
522 if (!stream.
carries(bd.getPacket()))
524 return bd.getLenInBytes() + headerBytes(bd.getPacket());
528 if (
auto it = programs.find(dma); it != programs.end()) {
530 bool carried =
false;
532 forEachInProgram<DMABDOp>(p, [&](DMABDOp bd) {
533 if (!stream.
carries(bd.getPacket()))
536 bytes += bytesOf(bd);
542 std::optional<uint64_t> looped = loopedVolume(p, bytesOf);
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()))
556 for (Operation *user : p.
op->getUsers()) {
557 if (isa<AIEX::DMAAwaitTaskOp, AIEX::DMAFreeTaskOp>(user))
561 auto start = dyn_cast<AIEX::DMAStartTaskOp>(user);
562 if (!start || start.hasRepeatParameter())
564 if (user->getParentOfType<LoopLikeOpInterface>())
569 total += bytes * runs;
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();
577 packet = ShimDMAAllocationOp::getForSymbol(
578 device, memcpy.getMetadata().getRootReference())
582 auto type = dyn_cast<BaseMemRefType>(memcpy.getMemref().getType());
583 if (memcpy->getParentOfType<LoopLikeOpInterface>() || !type ||
584 !type.getElementType().isIntOrFloat())
586 std::optional<SmallVector<int64_t>> sizes =
587 getConstantIntValues(memcpy.getMixedSizes());
590 uint64_t elements = 1;
591 for (int64_t n : *sizes)
595 uint64_t runs = sizes->front();
597 total += elements * type.getElementTypeBitWidth() / 8 +
598 runs * headerBytes(packet);
606std::optional<uint64_t> StreamVolumeAnalysis::loopedVolume(
608 function_ref<uint64_t(DMABDOp)> bytesOf)
const {
610 if (!walkLoop(program, [&](DMABDOp bd) { bytes += bytesOf(bd); }))
616 function_ref<
void(DMABDOp)> visit)
const {
619 !visiting.insert(&p).second)
621 llvm::scope_exit done([&] { visiting.erase(&p); });
622 SmallVector<Block *> sequence = chainBlocks(p);
623 if (sequence.empty())
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()))
633 auto it = tokens.find(lock);
634 if (it == tokens.end()) {
635 std::optional<uint64_t> others = tokensFromOthers(lock, &p);
638 it = tokens.try_emplace(lock, lock.getInit().value_or(0) + *others)
643 else if (it->second < *n)
647 }
else if (
auto bd = dyn_cast<DMABDOp>(bdOp)) {
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))
662 if (isa<CoreOp>(parent))
668std::optional<uint64_t>
669StreamVolumeAnalysis::tokensFromOthers(LockOp lock,
670 const DmaChannelProgram *self)
const {
671 llvm::SetVector<const DmaChannelProgram *> releasers;
673 for (Operation *user : lock->getUsers()) {
674 auto use = dyn_cast<UseLockOp>(user);
679 auto owner = lockUseProgram.find(use);
680 if (owner == lockUseProgram.end()) {
681 std::optional<uint64_t> n = lockTokens(use);
682 if (!onceInCore(use) || !n)
687 if (owner->second != self)
688 releasers.insert(owner->second);
690 for (
const DmaChannelProgram *program : releasers) {
691 std::optional<uint64_t> n = releasesOver(*program, lock);
702 if (first.
src != then.
src)
708 if (first.
src.
port.bundle != WireBundle::DMA)
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))
717 bool sent =
false, after =
false;
718 auto visit = [&](DMABDOp bd) {
719 after |= sent && then.
carries(bd.getPacket());
720 sent |= first.
carries(bd.getPacket());
723 if (!walkLoop(p, visit))
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>())
735std::optional<uint64_t>
738 if (!isa<DMAStartOp, DMAOp>(p.
op))
740 SmallVector<Block *> sequence = chainBlocks(p);
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);
751 return perPass * p.
passes;
754 if (p.
dma.
dir != DMAChannelDir::S2MM || sequence.empty())
757 uint64_t received = 0;
758 for (
const RoutedStream &s : streams) {
759 if (s.dst != endpoint)
761 std::optional<uint64_t> bytes = sendVolume(s);
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)
772 filled += bd.getLenInBytes();
773 }
else if (
auto use = dyn_cast<UseLockOp>(bdOp)) {
774 if (!use.release() || use.getLock().getDefiningOp() != lock)
776 std::optional<uint64_t> n = lockTokens(use);
786static std::optional<uint64_t> programCapacity(
const DmaChannelProgram &p,
788 if (!isa<DMAStartOp, DMAOp>(p.
op))
792 SmallVector<Block *> sequence = chainBlocks(p);
793 if (sequence.empty())
800 DenseMap<Operation *, int64_t> lockValues;
804 std::optional<DenseMap<Operation *, int64_t>> cycleLocks;
805 uint64_t cycleBytes = 0;
807 for (uint64_t step = 0;; step++) {
808 if (!p.
loops && step >= p.
passes * sequence.size())
810 size_t i = blockAt(p, sequence.size(), step);
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;
820 (p.
passes - step / sequence.size()) * (bytes - cycleBytes);
822 cycleLocks = lockValues;
826 if (step >=
static_cast<uint64_t
>(
maxBDSteps))
828 for (Operation &bdOp : *sequence[i]) {
829 if (
auto use = dyn_cast<UseLockOp>(bdOp)) {
830 std::optional<int64_t> n = lockAmount(use);
833 auto lock = use.getLock().getDefiningOp<LockOp>();
835 lockValues.try_emplace(lock, lock.getInit().value_or(0))
840 else if (value != *n)
842 }
else if (use.release()) {
844 }
else if (!use.acquireGE() || value < *n) {
849 }
else if (
auto bd = dyn_cast<DMABDOp>(bdOp)) {
850 bytes += bd.getLenInBytes();
856std::optional<uint64_t>
858 if (endpoint.
port.bundle != WireBundle::DMA)
860 auto it = programs.find(
861 {endpoint.
tile, DMAChannelDir::S2MM, endpoint.
port.channel});
862 if (it == programs.end())
864 std::optional<uint64_t> capacity;
866 if (std::optional<uint64_t> c = programCapacity(p, device))
867 capacity = std::min(*c, capacity.value_or(*c));
872 ArrayRef<RoutedStream> streams)
const {
878 if (s.dst != endpoint)
880 std::optional<uint64_t> bytes =
sendVolume(s);
885 return sent > *capacity;
889 ArrayRef<RoutedStream> streams,
891 std::set<TileDMAChannel> neverFull;
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];
902 DenseMap<Operation *, llvm::SetVector<unsigned>> acquirers, releasers;
903 auto noteLock = [&](UseLockOp use,
unsigned agent) {
904 Operation *lock = use.getLock().getDefiningOp();
907 if (use.getAction() == LockAction::Release)
908 releasers[lock].insert(agent);
910 acquirers[lock].insert(agent);
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); });
922 modeled.insert(agent);
923 forEachInProgram<UseLockOp>(p,
924 [&](UseLockOp use) { noteLock(use, agent); });
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())
932 for (
unsigned p : waiting->second)
933 for (
unsigned q : it->second)
934 if (p != q && waitsOnLocks(p))
935 addEdge(p, q, EdgeKind::Lock);
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)
946 addEdge(*from, *to, EdgeKind::Stream,
true);
947 addEdge(*to, *from, EdgeKind::Stream,
false,
true);
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()))
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())},
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>{};
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)});
1005 if (isa<AIEX::NpuMaskPollOp>(op))
1006 return SmallVector<TileDMAChannel>{};
1007 return std::nullopt;
1009 llvm::SetVector<TileDMAChannel, SmallVector<TileDMAChannel>,
1010 std::set<TileDMAChannel>>
1012 sequence.walk([&](Operation *op) {
1013 if (std::optional<SmallVector<TileDMAChannel>> keys = issued(op))
1014 issuedKeys.insert(keys->begin(), keys->end());
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)
1025 addEdge(agent, w, EdgeKind::Host);
1028 for (unsigned a = 0; a < numStreamAgents; a++)
1029 if (agents[a].kind == Agent::Kind::Channel)
1030 for (unsigned w : waited)
1032 addEdge(a, w, EdgeKind::Host);
1033 }
else if (std::optional<SmallVector<TileDMAChannel>> keys =
1036 keys->empty() ? issuedKeys.getArrayRef() : ArrayRef(*keys)) {
1038 for (
unsigned a = 0; a < numStreamAgents; a++)
1040 agents[a].dma.tile.col == key.tile.col)
1051 for (Agent &a : agents)
1052 a.onShim = a.kind == Agent::Kind::Channel &&
1054 for (
unsigned a = 0; a < agents.size(); a++) {
1055 if (modeled.contains(a) || agents[a].kind == Agent::Kind::Controller ||
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);
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)"
1072 << (e.kind == EdgeKind::Lock && !modeled.contains(a)
1079std::optional<StreamWaitGraph::Agent>
1081 if (endpoint.
port.bundle == WireBundle::Core)
1083 if (endpoint.
port.bundle == WireBundle::TileControl && sending)
1085 if (endpoint.
port.bundle == WireBundle::DMA)
1087 sending ? DMAChannelDir::MM2S : DMAChannelDir::S2MM,
1088 endpoint.
port.channel});
1091 return std::nullopt;
1094unsigned StreamWaitGraph::getOrCreate(
const Agent &agent) {
1095 auto [it, inserted] =
1096 agentIDs.try_emplace({agent.
kind, agent.
dma}, agents.size());
1098 agents.push_back(agent);
1099 edges.emplace_back();
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;
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) {
1116 e.receives |= receives;
1120 edges[from].push_back({to, kind, sends, receives});
1124 bool sending)
const {
1125 if (std::optional<Agent> agent =
Agent::at(endpoint, sending))
1126 return lookup(*agent);
1127 return std::nullopt;
1133 SmallVector<unsigned> drainers;
1134 for (
const Edge &e : edges[agent])
1135 if (e.kind != EdgeKind::Stream)
1136 drainers.push_back(e.to);
1140SmallVector<unsigned>
1142 ArrayRef<unsigned> avoid)
const {
1155 llvm::SparseBitVector<> took;
1156 std::optional<size_t> parent;
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))
1167 seen[next.agent].push_back(states.size());
1168 worklist.push_back(states.size());
1169 states.push_back(std::move(next));
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());
1185 for (
const Edge &e : edges[a]) {
1186 const State &state = states[index];
1187 if (state.taking && e.receives && !e.sends &&
1190 if (llvm::is_contained(avoid, e.to) || state.took.test(e.to))
1192 bool takes = e.kind == EdgeKind::Stream && e.sends &&
1194 llvm::SparseBitVector<> took = state.took;
1197 visit({e.to, takes, std::move(took), index});
1204 const Agent &a = agents[id];
1206 llvm::raw_string_ostream os(s);
1211 os <<
"TileControl";
1218 ArrayRef<RoutedStream> streams)
1219 : streams(streams), volumes(device, streams),
1220 graph(device, streams, volumes), stalls(streams.size()),
1221 silence(streams.size()) {}
1223bool StreamDeadlockAnalysis::canStall(
size_t f)
const {
1224 std::optional<bool> &stall = stalls[f];
1226 stall = volumes.
canFill(streams[f].dst, streams);
1230SmallVector<unsigned> StreamDeadlockAnalysis::blockingChain(
size_t f,
1233 std::optional<unsigned> fDst = graph.
agentAt(fs.
dst,
false);
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))
1245 for (std::optional<unsigned> a :
1247 if (a && !llvm::is_contained(own, *a))
1248 targets.push_back(*a);
1249 if (targets.empty())
1251 return graph.waitChain(drainers, targets, avoid);
1255 if (
auto it = blocks.find({f, g}); it != blocks.end())
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();
1264 std::optional<bool> &quiet = silence[f];
1266 quiet = volumes.sendVolume(streams[f]) == std::optional<uint64_t>(0);
1272 SmallVector<unsigned> chain = blockingChain(f, g);
1274 llvm::raw_string_ostream os(s);
1275 os <<
describeStream(fs) <<
" can fill its receiver, and draining that "
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 "
1290 SmallVector<std::string> assumed;
1292 if (other.dst == fs.
dst && !volumes.sendVolume(other)) {
1294 " carries is unknown, so it is assumed to overrun its "
1298 if (fs.
src == gs.src && !volumes.maySendAfter(fs, gs))
1299 assumed.push_back(
"Both come from " +
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))
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." :
"."));
1319 llvm::raw_string_ostream os(s);
1320 os << (stream.
packetID ?
"packet flow " :
"flow ")
1324 os <<
" (id " << *stream.
packetID <<
")";
1330 numRequested(streams.size()) {
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);
1343 waits.resize(treeMembers.size());
1346std::optional<StreamConflicts::TreeKey>
1347StreamConflicts::treeKey(
size_t s)
const {
1350 return std::nullopt;
1357 analysis.emplace(device, streams);
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)
1365 return getAnalysis().canBlock(s, t);
1370bool StreamConflicts::related(
size_t s,
size_t t)
const {
1371 if (streams[s].src == streams[t].src)
1373 for (
size_t m : treeMembers[treeOf[s]])
1374 for (
size_t n : treeMembers[treeOf[t]])
1375 if (streams[m].dst == streams[n].dst)
1381 return !related(s, t) && (blocks(s, t) || blocks(t, s));
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];
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();
1396 for (
size_t g = 0; g < treeMembers.size(); g++) {
1397 if (g == a || reached.contains(g) ||
1398 !streams[treeMembers[g].front()].packetID)
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])
1404 return std::pair{x, m};
1405 return std::nullopt;
1419 return blocks(s, t) || blocks(t, s) ||
1420 waitsFrom(treeOf[s]).contains(treeOf[t]) ||
1421 waitsFrom(treeOf[t]).contains(treeOf[s]);
1430 if (!waitsFrom(treeOf[s]).contains(treeOf[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);
1438 std::reverse(steps.begin(), steps.end());
1439 return llvm::join(steps,
" ");
1443 SmallVector<std::pair<size_t, size_t>> pairs;
1445 for (
size_t s = 0; s < numRequested; s++)
1446 for (
size_t t = 0; t < numRequested; t++) {
1449 if (s == t || treeOf[s] == treeOf[t] ||
1450 !(streams[s].packetID || streams[t].packetID) || !related(s, t) ||
1454 pairs.push_back({s, t});
1456 LLVM_DEBUG(llvm::dbgs() <<
"Unavoidable only by assumption: "
1467 std::optional<HoldCycle::Step> step;
1470 SmallVector<std::pair<TileID, int>, 4> orders = {};
1475 llvm::function_ref<ArrayRef<WaitEdge>(
size_t)> successors;
1478using WaitNode = std::pair<const WaitGraph *, size_t>;
1483struct GraphTraits<const WaitGraph *> {
1492 return map_iterator(n.first->successors(n.second).begin(),
ToNode{n.first});
1495 return map_iterator(n.first->successors(n.second).end(),
ToNode{n.first});
1500std::optional<HoldCycle>
1502 bool forcedWaits,
bool definite)
const {
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;
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))
1517 auto [it, inserted] = treeIDs.try_emplace(*key, trees.size());
1519 trees.emplace_back();
1520 Tree &tree = trees[it->second];
1521 tree.members.push_back(i);
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);
1540 auto sameSource = [&](
size_t a,
size_t b) {
1541 return streams[trees[a].members.front()].src ==
1542 streams[trees[b].members.front()].src;
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;
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))
1554 if (streams[trees[a].members.front()].packetID !=
1555 streams[trees[b].members.front()].packetID)
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()];
1570 enum class Kind { Hop, Receiver, Anywhere, Past };
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});
1588 auto receiverNode = [&](
size_t t,
size_t m) {
1589 return trees[t].base + trees[t].hops.size() + m;
1591 auto anywhereNode = [&](
size_t t) {
1592 return receiverNode(t, trees[t].members.size());
1594 auto pastNode = [&](
size_t t,
size_t h) {
return anywhereNode(t) + 1 + h; };
1596 std::map<std::pair<TileID, Port>, SmallVector<std::pair<size_t, size_t>, 4>>
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});
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()),
1615 return trees[t].hops[h].first == g.first &&
1616 trees[t].arbiter[h] == g.second;
1620 int pa = trees[a].parent[ha], pb = trees[b].parent[hb];
1621 if (pa < 0 || pb < 0)
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};
1629 grants.insert(grants.begin(), g);
1630 else if (once(a, g) && once(b, g))
1631 grants.push_back(g);
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> {
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));
1652 const Node &node = nodes[n];
1653 const Tree &u = trees[node.tree];
1654 switch (node.kind) {
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))
1661 size_t sharer = trees[t].members.front();
1662 bool sameId = streams[waiting].packetID == streams[sharer].packetID;
1663 if (t != node.tree && (!sameId || forcedWaits))
1667 tile, input, input, -1, sameId},
1668 orderedBy(node.tree, node.index, t, ht)});
1669 std::optional<int> arbiter = trees[t].arbiter[ht];
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)
1680 bool isForced = !self && forced(t, ht, v, hv, tile);
1681 if (isForced && !forcedWaits)
1686 trees[v].members.front(), tile, input,
1687 holderInput, *arbiter, isForced}});
1692 case Kind::Receiver: {
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;
1700 for (
size_t m : trees[g].members)
1702 (!definite || getAnalysis().assumptions(s, m).empty())) {
1703 out.push_back({anywhereNode(g),
1711 case Kind::Anywhere:
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])
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});
1725 return *(edges[n] = std::move(out));
1730 auto counts = [&](
const Edge &e) {
1733 return e.step->waiting < numRequested || e.step->sharer < numRequested ||
1734 e.step->holding < numRequested;
1736 for (
size_t n = 0; n < nodes.size(); n++)
1737 if (nodes[n].kind == Kind::Hop && llvm::any_of(successors(n), counts))
1740 const WaitGraph graph{successors, nodes.size()};
1741 std::vector<int> component(nodes.size() + 1, -1);
1743 for (
auto scc = llvm::scc_begin(&graph); !scc.isAtEnd(); ++scc, ++components)
1744 for (WaitNode n : *scc)
1745 component[n.second] = components;
1757 std::optional<size_t> fixed;
1758 SmallVector<size_t, 2> excluded;
1760 using Constraints = std::map<Grant, Holders>;
1761 auto allowed = [](
const Edge &edge,
const Constraints &c) {
1764 auto it = c.find({edge.step->tile, edge.step->arbiter});
1767 size_t holder = edge.step->holding;
1768 return it->second.fixed ? *it->second.fixed == holder
1769 : !llvm::is_contained(it->second.excluded, holder);
1773 constexpr size_t maxOrders = 8;
1775 [&](
size_t x,
const Edge &e,
1776 const Constraints &c) -> std::optional<SmallVector<const Edge *>> {
1778 return std::nullopt;
1781 size_t k = std::min<size_t>(e.orders.size(), maxOrders);
1782 auto unordered = [&](
const Edge &edge) {
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;
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);
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);
1811 std::reverse(path.begin(), path.end());
1814 auto toCycle = [](ArrayRef<const Edge *> path) {
1816 for (
const Edge *edge : path)
1818 cycle.
steps.push_back(*edge->step);
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])
1826 std::optional<SmallVector<const Edge *>> first;
1827 SmallVector<Constraints> pending{{}};
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);
1836 Constraints c = pending.pop_back_val();
1837 std::optional<SmallVector<const Edge *>> path = closeWalk(x, e, c);
1842 std::map<Grant, size_t> held;
1843 std::optional<std::pair<Grant, size_t>> clash;
1844 for (
const Edge *edge : *path) {
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) {
1855 LLVM_DEBUG(llvm::dbgs() <<
"Hold cycle search closed a walk after "
1856 << search + 1 <<
" walks\n");
1857 return toCycle(*path);
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));
1865 LLVM_DEBUG(llvm::dbgs() <<
"Hold cycle search closed no walk after "
1866 << search <<
" walks\n");
1868 return std::nullopt;
1873 llvm::raw_string_ostream os(s);
1874 for (
auto [i, step] : llvm::enumerate(cycle.
steps)) {
1877 switch (step.wait) {
1879 os <<
describeStream(streams[step.waiting]) <<
" can queue behind "
1881 <<
describePort(step.sharerInput) <<
" into tile (" << step.tile.col
1882 <<
", " << step.tile.row <<
").";
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])
1889 if (step.waiting != step.sharer)
1891 <<
" can queue behind it";
1895 os << getAnalysis().explainBlock(step.waiting, step.holding);
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,...
StreamConflicts(DeviceOp device)
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)
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
std::string describePort(Port port)
Names a port the way diagnostics do, e.g. "DMA:1".
NodeRef operator()(const WaitEdge &e) const
static ChildIteratorType child_begin(NodeRef n)
static NodeRef getEntryNode(const WaitGraph *g)
mapped_iterator< const WaitEdge *, ToNode > ChildIteratorType
static ChildIteratorType child_end(NodeRef n)
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 Agent core(TileID tile)
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)
static Agent controller(TileID tile)
One DMA channel of one tile.