MLIR-AIE 1.4.6.dev
AIECreatePathFindFlows.cpp
Go to the documentation of this file.
1//===- AIECreatePathfindFlows.cpp -------------------------------*- C++ -*-===//
2//
3// Copyright (C) 2021-2022 Xilinx, Inc.
4// Copyright (C) 2022-2026 Advanced Micro Devices, Inc.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
14
15#include "mlir/IR/PatternMatch.h"
16#include "mlir/Pass/Pass.h"
17#include "mlir/Transforms/DialectConversion.h"
18#include "llvm/ADT/DenseSet.h"
19#include "llvm/ADT/EquivalenceClasses.h"
20#include "llvm/ADT/STLExtras.h"
21#include "llvm/ADT/ScopeExit.h"
22#include "llvm/ADT/SmallBitVector.h"
23#include "llvm/Support/Debug.h"
24#include "llvm/Support/MathExtras.h"
25
26#include <algorithm>
27#include <cstdint>
28#include <deque>
29#include <numeric>
30#include <optional>
31#include <set>
32
33using namespace mlir;
34using namespace xilinx;
35using namespace xilinx::AIE;
36
37#define DEBUG_TYPE "aie-create-pathfinder-flows"
38
39namespace xilinx::AIE {
40#define GEN_PASS_DEF_AIEROUTEPATHFINDERFLOWS
41#include "aie/Dialect/AIE/Transforms/AIEPasses.h.inc"
42} // namespace xilinx::AIE
43
44using PhysPort = std::pair<TileID, Port>;
45
46/// (mask, value, amsel) by slave port, in slot order.
48 std::map<PhysPort, SmallVector<std::tuple<int, int, int>, 2>>;
49
52 // The packet ids each tree carries.
53 std::map<PathEndPoint, std::set<int>> ids;
55};
56
57static PriorityRules priorityRules(DeviceOp d) {
58 const int numArbiters = d.getTargetModel().getNumArbiters();
59 AIEDialect::PriorityRouteAttrHelper priority(d.getContext());
60 PriorityRules rules;
61 for (SwitchboxOp box : d.getOps<SwitchboxOp>())
62 for (PacketRulesOp port : box.getOps<PacketRulesOp>())
63 for (PacketRuleOp rule : port.getRules().front().getOps<PacketRuleOp>())
64 if (priority.isAttrPresent(port) || priority.isAttrPresent(rule)) {
65 auto amsel = cast<AMSelOp>(rule.getAmsel().getDefiningOp());
66 rules[{box.getTileOp().getTileID(),
67 {port.getSourceBundle(), port.sourceIndex()}}]
68 .push_back(
69 {rule.maskInt(), rule.valueInt(),
70 amsel.arbiterIndex() + amsel.getMselValue() * numArbiters});
71 }
72 return rules;
73}
74
75// The backtracking searches for an arbiter plan and for a set of streams that
76// cannot share an arbiter are exact up to this many steps.
77constexpr int maxSearchSteps = 100000;
78// The hold-cycle search replans a tile at most this many times.
79constexpr int maxHoldCycleReplans = 256;
80
81static constexpr llvm::StringLiteral sharedReceiverCycleReason =
82 "Packet flows into receivers they share can deadlock holding arbiters "
83 "across switchboxes, and no routing found avoids it: ";
84static constexpr llvm::StringLiteral allowDeadlockProneHint =
85 " Set allow-deadlock-prone (aiecc --allow-deadlock-prone-routing) to "
86 "route them anyway.";
87
88namespace {
89struct PacketPlan;
90
91/// \brief Routes flows in a device by lowering them to stream-switch
92/// configurations.
93///
94/// Overall flow:
95/// 1. Report flows that can deadlock however they are routed.
96/// 2. Route the prioritized packet flows alone and pin their trees.
97/// 3. Route every flow with Pathfinder, planning the arbiters and packet rules
98/// on each routing found and steering off those that cannot be used,
99/// relaxing the packet constraints if no routing is found.
100/// 4. Lower the circuit flows to connects, and the packet flows as planned.
101/// 5. Add the wires between switchboxes and tiles.
102struct AIEPathfinderPass
103 : xilinx::AIE::impl::AIERoutePathfinderFlowsBase<AIEPathfinderPass> {
104 using Base =
105 xilinx::AIE::impl::AIERoutePathfinderFlowsBase<AIEPathfinderPass>;
106 AIEPathfinderPass() = default;
107 AIEPathfinderPass(const AIERoutePathfinderFlowsOptions &options)
108 : Base(options) {}
109 std::vector<std::pair<TileID, Port>> avoidedPorts;
110 void runOnOperation() override;
111 LogicalResult runOnFlow(DeviceOp d, DynamicTileAnalysis &analyzer);
112 /// Lowers the packet flows as `plan` says, on the routing `analyzer` found,
113 /// warning of a hold cycle left through receivers flows share if `warn`.
114 LogicalResult runOnPacketFlow(DeviceOp d, OpBuilder &builder,
115 DynamicTileAnalysis &analyzer,
116 const StreamConflicts &conflicts,
117 const PacketPlan &plan, bool warn);
118 llvm::Expected<PacketPlan> route(DeviceOp d, DynamicTileAnalysis &analyzer,
119 const StreamConflicts &conflicts,
120 const PinnedRoutes &pinned,
121 bool circuitSwitchHops,
122 bool prioritize = true);
123};
124
125// allocates channels between switchboxes ( but does not assign them)
126// instantiates shim-muxes AND allocates channels ( no need to rip these up in )
127struct ConvertFlowsToInterconnect : OpConversionPattern<FlowOp> {
128 using OpConversionPattern::OpConversionPattern;
129 DeviceOp &device;
130 DynamicTileAnalysis &analyzer;
131 ConvertFlowsToInterconnect(MLIRContext *context, DeviceOp &d,
132 DynamicTileAnalysis &a, PatternBenefit benefit = 1)
133 : OpConversionPattern(context, benefit), device(d), analyzer(a) {}
134
135 void addConnection(ConversionPatternRewriter &rewriter,
136 // could be a shim-mux or a switchbox.
137 Interconnect op, FlowOp flowOp, WireBundle inBundle,
138 int inIndex, WireBundle outBundle, int outIndex) const {
139
140 Region &r = op.getConnections();
141 Block &b = r.front();
142 auto point = rewriter.saveInsertionPoint();
143 rewriter.setInsertionPoint(b.getTerminator());
144
145 ConnectOp::create(rewriter, flowOp.getLoc(), inBundle, inIndex, outBundle,
146 outIndex);
147
148 rewriter.restoreInsertionPoint(point);
149
150 LLVM_DEBUG(llvm::dbgs()
151 << "\t\taddConnection() (" << op.colIndex() << ","
152 << op.rowIndex() << ") " << stringifyWireBundle(inBundle)
153 << inIndex << " -> " << stringifyWireBundle(outBundle)
154 << outIndex << "\n");
155 }
156
157 mlir::LogicalResult
158 matchAndRewrite(FlowOp flowOp, OpAdaptor adaptor,
159 ConversionPatternRewriter &rewriter) const override {
160 Operation *Op = flowOp.getOperation();
161 DeviceOp d = flowOp->getParentOfType<DeviceOp>();
162 if (!d) {
163 flowOp->emitOpError("This operation must be contained within a device");
164 return failure();
165 }
166 rewriter.setInsertionPoint(d.getBody()->getTerminator());
167
168 auto srcTile = cast<TileOp>(flowOp.getSource().getDefiningOp());
169 TileID srcCoords = {srcTile.colIndex(), srcTile.rowIndex()};
170 auto srcBundle = flowOp.getSourceBundle();
171 auto srcChannel = flowOp.getSourceChannel();
172 Port srcPort = {srcBundle, srcChannel};
173
174 LLVM_DEBUG({
175 auto dstTile = cast<TileOp>(flowOp.getDest().getDefiningOp());
176 llvm::dbgs() << "\n\t---Begin rewrite() for flowOp: (" << srcCoords.col
177 << ", " << srcCoords.row << ")"
178 << stringifyWireBundle(srcBundle) << srcChannel << " -> ("
179 << dstTile.colIndex() << ", " << dstTile.rowIndex() << ")"
180 << stringifyWireBundle(flowOp.getDestBundle())
181 << flowOp.getDestChannel() << "\n\t";
182 });
183
184 // if the flow (aka "net") for this FlowOp hasn't been processed yet,
185 // add all switchbox connections to implement the flow
186 TileID srcSbId = {srcCoords.col, srcCoords.row};
187 PathEndPoint srcPoint = {srcSbId, srcPort};
188 if (analyzer.processedFlows.count(srcPoint)) {
189 // This FlowOp is a broadcast sibling of a flow whose route was already
190 // materialized (the analyzer merges all destinations sharing a source
191 // into one net, so the first sibling emitted connections for every
192 // destination). Erase it and report success so the erase is committed.
193 LLVM_DEBUG(llvm::dbgs() << "Flow already processed!\n");
194 rewriter.eraseOp(Op);
195 return success();
196 }
197 const SwitchSettings &settings = analyzer.routing.settings.at(srcPoint);
198 // add connections for all the Switchboxes in SwitchSettings
199 for (const auto &[tileId, setting] : settings) {
200 int col = tileId.col;
201 int row = tileId.row;
202 SwitchboxOp swOp = analyzer.getSwitchbox(rewriter, col, row);
203 int shimCh = srcChannel;
204 bool isShim = analyzer.getTile(rewriter, tileId).isShimNOCorPLTile();
205
206 // TODO: must reserve N3, N7, S2, S3 for DMA connections
207 bool srcUsesShimMux = srcBundle == WireBundle::DMA ||
208 srcBundle == WireBundle::PLIO ||
209 srcBundle == WireBundle::NOC;
210 if (isShim && tileId == srcSbId && srcUsesShimMux) {
211
212 shimCh = shimMuxChannelFrom(srcPort);
213 ShimMuxOp shimMuxOp = analyzer.getShimMux(rewriter, col);
214 addConnection(rewriter, cast<Interconnect>(shimMuxOp.getOperation()),
215 flowOp, srcBundle, srcChannel, WireBundle::North, shimCh);
216 }
217 assert(setting.srcs.size() == setting.dsts.size());
218 for (size_t i = 0; i < setting.srcs.size(); i++) {
219 Port src = setting.srcs[i];
220 Port dest = setting.dsts[i];
221
222 // A flow can start and end at one shim (see shimMuxChannelFrom).
223 if (isShim && tileId == srcSbId && srcUsesShimMux && src == srcPort)
224 src = {WireBundle::South, shimCh};
225 if (isShim && (dest.bundle == WireBundle::DMA ||
226 dest.bundle == WireBundle::PLIO ||
227 dest.bundle == WireBundle::NOC)) {
228 int destCh = shimMuxChannelTo(dest);
229
230 ShimMuxOp shimMuxOp = analyzer.getShimMux(rewriter, col);
231 addConnection(rewriter, cast<Interconnect>(shimMuxOp.getOperation()),
232 flowOp, WireBundle::North, destCh, dest.bundle,
233 dest.channel);
234 dest = {WireBundle::South, destCh};
235 }
236 addConnection(rewriter, cast<Interconnect>(swOp.getOperation()), flowOp,
237 src.bundle, src.channel, dest.bundle, dest.channel);
238 }
239
240 LLVM_DEBUG(llvm::dbgs() << tileId << ": " << setting << " | " << "\n");
241 }
242
243 LLVM_DEBUG(llvm::dbgs()
244 << "\n\t\tFinished adding ConnectOps to implement flowOp.\n");
245
246 analyzer.processedFlows.insert(srcPoint);
247 rewriter.eraseOp(Op);
248 return success();
249 }
250};
251
252} // namespace
253
254LogicalResult AIEPathfinderPass::runOnFlow(DeviceOp d,
255 DynamicTileAnalysis &analyzer) {
256 // Apply rewrite rule to switchboxes to add assignments to every 'connect'
257 // operation inside
258 ConversionTarget target(getContext());
259 target.addLegalOp<TileOp>();
260 target.addLegalOp<ConnectOp>();
261 target.addLegalOp<SwitchboxOp>();
262 target.addLegalOp<ShimMuxOp>();
263 target.addLegalOp<EndOp>();
264
265 RewritePatternSet patterns(&getContext());
266 patterns.insert<ConvertFlowsToInterconnect>(d.getContext(), d, analyzer);
267 if (failed(applyPartialConversion(d, target, std::move(patterns))))
268 return failure();
269 return success();
270}
271
272/// The switchbox a master port feeds, and the slave port it feeds there.
273static std::optional<std::pair<TileID, Port>> linkedInput(TileID tile,
274 Port out) {
275 switch (out.bundle) {
276 case WireBundle::East:
277 return std::pair{TileID{tile.col + 1, tile.row},
278 Port{WireBundle::West, out.channel}};
279 case WireBundle::West:
280 return std::pair{TileID{tile.col - 1, tile.row},
281 Port{WireBundle::East, out.channel}};
282 case WireBundle::North:
283 return std::pair{TileID{tile.col, tile.row + 1},
284 Port{WireBundle::South, out.channel}};
285 case WireBundle::South:
286 return std::pair{TileID{tile.col, tile.row - 1},
287 Port{WireBundle::North, out.channel}};
288 default:
289 return std::nullopt;
290 }
291}
292
293/// Whether the connection out of `out` at `tile` leads, through `settings`, to
294/// `finalPort` at `finalTile`.
295static bool findPathToDest(const SwitchSettings &settings, TileID tile,
296 Port out, TileID finalTile, Port finalPort) {
297 if (tile == finalTile && out == finalPort)
298 return true;
299 std::optional<std::pair<TileID, Port>> next = linkedInput(tile, out);
300 if (!next)
301 return false;
302 TileID neighbour = next->first;
303 Port in = next->second;
304 auto setting = settings.find(neighbour);
305 if (setting == settings.end())
306 return false;
307 return llvm::any_of(
308 llvm::zip(setting->second.srcs, setting->second.dsts), [&](auto link) {
309 auto [src, dest] = link;
310 return src == in &&
311 findPathToDest(settings, neighbour, dest, finalTile, finalPort);
312 });
313}
314
315/// Every node `successors` reaches from `start`, with the node a breadth-first
316/// search first reaches it from; `start` maps to itself. Stops once `goal` is
317/// reached, if given.
318template <typename Node, typename Successors>
319static std::map<Node, Node>
320breadthFirstParents(Node start, Successors successors,
321 std::optional<Node> goal = std::nullopt) {
322 std::map<Node, Node> parent{{start, start}};
323 std::deque<Node> work{start};
324 while (!work.empty() && !(goal && parent.count(*goal))) {
325 Node u = work.front();
326 work.pop_front();
327 for (Node v : successors(u))
328 if (parent.try_emplace(v, u).second)
329 work.push_back(v);
330 }
331 return parent;
332}
333
334namespace {
335struct CoverCube {
336 int mask;
337 int value;
338 // cov[i] is set iff this cube matches match id i.
339 llvm::SmallBitVector cov;
340};
341} // namespace
342
343// Minimum set cover by branch-and-bound: find the fewest `cubes` whose coverage
344// (cube.cov) unions to every match id still set in `uncovered`. `sel` is the
345// current partial pick; `bestSel`/`bestSize` hold the smallest full cover so
346// far and are updated in place.
347static void bnbMinCover(ArrayRef<CoverCube> cubes,
348 const llvm::SmallBitVector &uncovered,
349 SmallVectorImpl<int> &sel, int &bestSize,
350 SmallVectorImpl<int> &bestSel) {
351
352 // base case
353 if (uncovered.none()) {
354 if (static_cast<int>(sel.size()) < bestSize) {
355 bestSize = static_cast<int>(sel.size());
356 bestSel.assign(sel.begin(), sel.end());
357 }
358 return;
359 }
360
361 // bound: adding a cube would only tie the best
362 if (static_cast<int>(sel.size()) + 1 >= bestSize) {
363 return;
364 }
365
366 // most constrained variable: find the least-covered, uncovered matchId
367 int pick = -1;
368 int pickCount = static_cast<int>(cubes.size()) + 1;
369
370 for (int id = uncovered.find_first(); id != -1;
371 id = uncovered.find_next(id)) {
372 int c = 0;
373
374 for (const CoverCube &cb : cubes) {
375 if (cb.cov.test(id)) {
376 c++;
377 }
378 }
379
380 if (c < pickCount) {
381 pickCount = c;
382 pick = id;
383 }
384 }
385
386 // branch: try each cube that covers the chosen id, recursing on the rest.
387 for (int i = 0; i < static_cast<int>(cubes.size()); ++i) {
388 if (!cubes[i].cov.test(pick)) {
389 continue;
390 }
391
392 sel.push_back(i);
393 llvm::SmallBitVector next = uncovered;
394 next.reset(cubes[i].cov); // next &= ~cov
395 bnbMinCover(cubes, next, sel, bestSize, bestSel);
396 sel.pop_back();
397 }
398}
399
400static bool cubesIntersect(std::pair<int, int> a, std::pair<int, int> b) {
401 return ((a.second ^ b.second) & a.first & b.first) == 0;
402}
403
404// Cover `matchIds` (a group's packet ids) with the fewest (mask, value) rules
405// that match every specified id and no cube in `avoidCubes` (what the other
406// groups on the same slave port claim). A rule matches id x iff
407// (x & mask) == value; ids no cube claims are don't-cares, free to over-claim.
408//
409// Based on Quine-McCluskey:
410// 1. Enumerate prime implicants: maximal cubes (a cube is one (mask, value))
411// that match >=1 matchIds and no avoid cube.
412// 2. Pick the fewest of those cubes that cover all match ids (bnbMinCover).
413// 3. Tighten each chosen cube to the smallest enclosing cube of the ids it
414// took, so it claims no more don't-cares than necessary; the one-cube case
415// reduces to the old common-bits mask.
416static SmallVector<std::pair<int, int>>
417computeSubcubeCover(const SmallVector<int, 4> &matchIds,
418 ArrayRef<std::pair<int, int>> avoidCubes, int idBits) {
419
420 // id space and full mask, sized from the target's packet-id width.
421 const int numIds = 1 << idBits;
422 const int idMask = numIds - 1;
423
424 auto hitsAvoid = [&](int mask, int value) {
425 return llvm::any_of(avoidCubes, [&](std::pair<int, int> c) {
426 return cubesIntersect({mask, value}, c);
427 });
428 };
429
430 llvm::SmallBitVector matchMask(numIds);
431 for (int id : matchIds) {
432 matchMask.set(id);
433 }
434
435 // phase 1: enumerate prime implicants. small (3^idBits), so brute force.
436 SmallVector<CoverCube> primes;
437 for (int mask = 0; mask < numIds; ++mask) {
438 for (int value = 0; value < numIds; ++value) {
439 // valid cube := value covered by mask, avoids properly
440 if ((value & mask) != value) {
441 continue;
442 }
443 if (hitsAvoid(mask, value)) {
444 continue;
445 }
446
447 // record covering
448 llvm::SmallBitVector cov(numIds);
449 for (int id : matchIds) {
450 if ((id & mask) == value) {
451 cov.set(id);
452 }
453 }
454
455 if (cov.none()) {
456 continue;
457 }
458
459 // prime = maximal, i.e., no checked mask bit can be dropped without
460 // covering an avoidId.
461 bool isPrime = true;
462 for (int b = 0; b < idBits; ++b) {
463 if (!((mask >> b) & 1)) {
464 continue;
465 }
466
467 if (!hitsAvoid(mask & ~(1 << b), value & ~(1 << b))) {
468 isPrime = false;
469 break;
470 }
471 }
472
473 if (isPrime) {
474 primes.push_back({mask, value, std::move(cov)});
475 }
476 }
477 }
478
479 // phase 2: pick the fewest primes that cover every match id (bnb).
480 SmallVector<int> sel, bestSel;
481 int bestSize = static_cast<int>(matchIds.size()) + 1;
482
483 bnbMinCover(primes, matchMask, sel, bestSize, bestSel);
484
485 SmallVector<std::pair<int, int>> chosen;
486 for (int i : bestSel) {
487 chosen.push_back({primes[i].mask, primes[i].value});
488 }
489
490 if (chosen.empty()) {
491 // unreachable: a single-id cube always covers
492 for (int id : matchIds) {
493 chosen.push_back({idMask, id});
494 }
495 }
496
497 // phase 3: tighten each chosen cube to match only the ids it took.
498 // maximal -> over-claim don't-cares -> more mask bits narrow the cube.
499 //
500 // e.g., {2,4} avoid {0}:
501 // prime (mask 00010, value 00010): 2 & 00010 = 00010 == value -> hit
502 // 6 & 00010 = 00010 == value -> also hit
503 // tight (mask 11111, value 00010): 2 & 11111 = 00010 == value -> hit
504 // 6 & 11111 = 00110 != value -> dropped
505 // 0 & 11111 = 00000 != value -> avoided
506
507 SmallVector<SmallVector<int, 4>, 4> assigned(chosen.size());
508 for (int id : matchIds) {
509 for (int c = 0; c < static_cast<int>(chosen.size()); ++c) {
510 if ((id & chosen[c].first) == chosen[c].second) {
511 assigned[c].push_back(id);
512 break;
513 }
514 }
515 }
516
517 SmallVector<std::pair<int, int>> cover;
518 for (const SmallVector<int, 4> &ids : assigned) {
519 if (ids.empty()) {
520 continue;
521 }
522
523 int mask = idMask;
524 for (int i = 0; i < idBits; ++i) {
525 int bit = (ids.front() >> i) & 1;
526 for (int id : ids) {
527 if (((id >> i) & 1) != bit) {
528 mask &= ~(1 << i);
529 break;
530 }
531 }
532 }
533 cover.push_back({mask, ids.front() & mask});
534 }
535
536 return cover;
537}
538
539// A group's rules (see GroupClaims): the stated ones, then a cover of the
540// derived ids that avoids them and `avoid`, whatever else claims ids on the
541// port.
542static SmallVector<std::pair<int, int>>
543groupRules(ArrayRef<std::pair<int, int>> stated, ArrayRef<int> derived,
544 ArrayRef<std::pair<int, int>> avoid, int idBits) {
545 SmallVector<std::pair<int, int>> rules(stated);
546 if (derived.empty())
547 return rules;
548 SmallVector<std::pair<int, int>> derivedAvoid(avoid);
549 derivedAvoid.append(stated.begin(), stated.end());
550 llvm::append_range(rules, computeSubcubeCover(SmallVector<int, 4>(derived),
551 derivedAvoid, idBits));
552 return rules;
553}
554
555namespace {
556struct GroupClaims {
557 ArrayRef<std::pair<int, int>> stated;
558 ArrayRef<int> derived;
559 bool priority = false;
560};
561
562/// A packet rule of a slave port, and the group it selects.
563struct PortRule {
564 int mask;
565 int value;
566 size_t group;
567};
568} // namespace
569
570static uint64_t cubeIds(int mask, int value, int idBits) {
571 uint64_t ids = 0;
572 for (int id = 0; id < (1 << idBits); ++id)
573 if ((id & mask) == (value & mask))
574 ids |= uint64_t(1) << id;
575 return ids;
576}
577
578// The fewest rules, at most `budget`, that send every id a group claims to
579// that group, where a packet takes the first rule it matches. A rule may then
580// claim ids of another group that an earlier rule already takes.
581static std::optional<SmallVector<PortRule>>
582orderedRules(ArrayRef<GroupClaims> groups,
583 ArrayRef<std::pair<int, int>> existing, int idBits,
584 size_t budget) {
585 if (idBits > 6)
586 return std::nullopt;
587 const int idMask = (1 << idBits) - 1;
588 SmallVector<uint64_t> claims;
589 for (const GroupClaims &group : groups) {
590 uint64_t ids = 0;
591 for (auto [mask, value] : group.stated)
592 ids |= cubeIds(mask, value, idBits);
593 for (int id : group.derived)
594 ids |= uint64_t(1) << id;
595 claims.push_back(ids);
596 }
597 uint64_t claimed = 0;
598 for (uint64_t ids : claims)
599 claimed |= ids;
600 uint64_t taken = 0;
601 for (auto [mask, value] : existing)
602 taken |= cubeIds(mask, value, idBits);
603 if (taken & claimed)
604 return std::nullopt;
605 SmallVector<uint64_t> cubes;
606 for (int mask = 0; mask <= idMask; ++mask)
607 for (int value = 0; value <= idMask; ++value)
608 if ((value & mask) == value)
609 cubes.push_back(cubeIds(mask, value, idBits));
610
611 // A rule is worth only the claimed ids it newly takes, all of one group, so
612 // the tightest cube around them serves, and fewer ids of the same group
613 // never serve better.
614 SmallVector<PortRule> rules;
615 std::set<std::pair<uint64_t, size_t>> dead;
616 auto search = [&](auto &self, uint64_t taken, size_t left) -> bool {
617 uint64_t open = claimed & ~taken;
618 size_t openGroups =
619 llvm::count_if(claims, [&](uint64_t ids) { return ids & open; });
620 if (openGroups == 0)
621 return true;
622 if (openGroups > left || dead.count({taken, left}))
623 return false;
624 SmallVector<std::pair<uint64_t, size_t>> moves;
625 for (uint64_t cube : cubes)
626 for (auto [g, ids] : llvm::enumerate(claims))
627 if ((cube & open) && (cube & open & ~ids) == 0 &&
628 !llvm::is_contained(moves, std::pair{cube & open, g}))
629 moves.push_back({cube & open, g});
630 llvm::stable_sort(moves, [](auto a, auto b) {
631 return llvm::popcount(a.first) > llvm::popcount(b.first);
632 });
633 SmallVector<std::pair<uint64_t, size_t>> tried;
634 for (auto [own, g] : moves) {
635 if (llvm::any_of(tried, [&, own = own, g = g](auto t) {
636 return t.second == g && (t.first & own) == own;
637 }))
638 continue;
639 tried.push_back({own, g});
640 int all = idMask, any = 0;
641 for (int id = 0; id <= idMask; ++id)
642 if ((own >> id) & 1) {
643 all &= id;
644 any |= id;
645 }
646 int mask = idMask & ~(all ^ any);
647 rules.push_back({mask, all, g});
648 if (self(self, taken | own, left - 1))
649 return true;
650 rules.pop_back();
651 }
652 dead.insert({taken, left});
653 return false;
654 };
655 for (size_t length = 1; length <= budget; ++length)
656 if (search(search, taken, length))
657 return rules;
658 return std::nullopt;
659}
660
661// The rules of a slave port, in slot order after the `existing` ones. Each
662// group takes its own cover, which claims no id another group claims, unless
663// those outnumber the free slots and first-match order fits them.
664static SmallVector<PortRule> portRules(ArrayRef<GroupClaims> groups,
665 ArrayRef<std::pair<int, int>> existing,
666 int idBits, size_t slots) {
667 const int idMask = (1 << idBits) - 1;
668 SmallVector<PortRule> rules;
669 for (auto [g, group] : llvm::enumerate(groups)) {
670 SmallVector<std::pair<int, int>> avoid(existing);
671 for (auto [o, other] : llvm::enumerate(groups)) {
672 if (o == g)
673 continue;
674 avoid.append(other.stated.begin(), other.stated.end());
675 for (int id : other.derived)
676 avoid.push_back({idMask, id});
677 }
678 for (auto [mask, value] :
679 groupRules(group.stated, group.derived, avoid, idBits))
680 rules.push_back({mask, value, g});
681 }
682 if (existing.size() + rules.size() <= slots || existing.size() >= slots)
683 return rules;
684 if (std::optional<SmallVector<PortRule>> ordered =
685 orderedRules(groups, existing, idBits, slots - existing.size()))
686 return *ordered;
687 return rules;
688}
689
690static SmallVector<PortRule>
691slavePortRules(ArrayRef<GroupClaims> groups,
692 ArrayRef<std::pair<int, int>> existing, int idBits,
693 size_t slots) {
694 SmallVector<std::pair<int, int>> taken(existing);
695 SmallVector<PortRule> rules;
696 for (bool priority : {true, false}) {
697 SmallVector<size_t, 4> members;
698 SmallVector<GroupClaims> claims;
699 for (auto [g, group] : llvm::enumerate(groups))
700 if (group.priority == priority) {
701 members.push_back(g);
702 claims.push_back(group);
703 }
704 if (claims.empty())
705 continue;
706 for (const PortRule &r : portRules(claims, taken, idBits, slots))
707 rules.push_back({r.mask, r.value, members[r.group]});
708 for (const PortRule &r : rules)
709 if (groups[r.group].priority == priority)
710 taken.push_back({r.mask, r.value});
711 }
712 return rules;
713}
714
715namespace {
716/// Packets with one id entering a switchbox on one slave port, and the master
717/// ports they leave by.
718struct SlaveFlow {
719 Port slave;
720 int id;
721 SmallVector<Port, 4> masters;
722 bool isPriority;
723};
724
725/// The amsel each slave flow takes, and the master ports each amsel selects
726/// (see planArbiters).
727struct ArbiterPlan {
728 std::map<std::pair<Port, int>, int> slaveAmsels;
729 std::map<int, SmallVector<Port, 4>> amselMasters;
730};
731
732/// The master ports `flows` tie to one arbiter: a slave flow's arbiter takes
733/// every master port it leaves by (see planArbiters).
734template <typename SlaveFlows>
735llvm::EquivalenceClasses<Port> tiedMasters(SlaveFlows &&flows) {
736 llvm::EquivalenceClasses<Port> tied;
737 for (const SlaveFlow &f : flows)
738 for (Port m : f.masters)
739 tied.unionSets(f.masters.front(), m);
740 return tied;
741}
742
743/// Chooses arbiters for a switchbox's slave flows so that no two flows that
744/// can deadlock (`conflict`) and enter on different slave ports share one.
745/// A master port is tied to one arbiter, so every master port a slave flow
746/// leaves by takes that flow's arbiter; the master ports linked that way form
747/// a unit, and each master set in a unit takes an msel. A flow never takes
748/// an arbiter `excluded` rules out for it. Units are colored onto arbiters by
749/// backtracking, which is exact up to a step budget. On failure, fills
750/// `blocking` with the conflicting pairs that stood in the way; it stays empty
751/// when the master sets alone outnumber the free msels.
752std::optional<ArbiterPlan>
753planArbiters(const AIETargetModel &targetModel, ArrayRef<SlaveFlow> flows,
754 llvm::function_ref<bool(size_t, size_t)> conflict,
755 llvm::function_ref<bool(size_t, int)> excluded,
756 const std::set<int> &reservedAmsels,
757 SmallVectorImpl<std::pair<size_t, size_t>> &blocking) {
758 const int numArbiters = targetModel.getNumArbiters();
759 const int numMselsPerArbiter = targetModel.getNumMselsPerArbiter();
760 auto amselOf = [&](int arbiter, int msel) {
761 return arbiter + msel * numArbiters;
762 };
763
764 llvm::EquivalenceClasses<Port> tied = tiedMasters(flows);
765
766 struct Unit {
767 SmallVector<size_t, 4> flows;
768 SmallVector<SmallVector<Port, 4>, 2> masterSets;
769 bool isPriority = false;
770 };
771 std::vector<Unit> units;
772 std::map<Port, size_t> unitOf;
773 SmallVector<size_t, 8> flowUnit;
774 for (auto [i, f] : llvm::enumerate(flows)) {
775 auto [it, inserted] =
776 unitOf.try_emplace(tied.getLeaderValue(f.masters.front()), 0);
777 if (inserted) {
778 it->second = units.size();
779 units.emplace_back();
780 }
781 Unit &unit = units[it->second];
782 flowUnit.push_back(it->second);
783 unit.flows.push_back(i);
784 unit.isPriority |= f.isPriority;
785 if (!llvm::is_contained(unit.masterSets, f.masters))
786 unit.masterSets.push_back(f.masters);
787 }
788 for (Unit &unit : units) {
789 auto *priorityEnd = std::stable_partition(
790 unit.masterSets.begin(), unit.masterSets.end(),
791 [&](const SmallVector<Port, 4> &masters) {
792 return llvm::any_of(unit.flows, [&](size_t f) {
793 return flows[f].isPriority && flows[f].masters == masters;
794 });
795 });
796 std::sort(unit.masterSets.begin(), priorityEnd);
797 }
798
799 auto clash = [&](size_t a, size_t b) {
800 return flows[a].slave != flows[b].slave && conflict(a, b);
801 };
802 for (const Unit &unit : units)
803 for (auto [k, a] : llvm::enumerate(unit.flows))
804 for (size_t b : llvm::drop_begin(unit.flows, k + 1))
805 if (clash(a, b))
806 blocking.push_back({a, b});
807 if (!blocking.empty())
808 return std::nullopt;
809
810 std::vector<llvm::SmallDenseSet<size_t, 4>> neighbors(units.size());
811 SmallVector<std::pair<size_t, size_t>, 4> crossPairs;
812 for (size_t a = 0; a < flows.size(); a++)
813 for (size_t b = a + 1; b < flows.size(); b++)
814 if (flowUnit[a] != flowUnit[b] && clash(a, b)) {
815 neighbors[flowUnit[a]].insert(flowUnit[b]);
816 neighbors[flowUnit[b]].insert(flowUnit[a]);
817 crossPairs.push_back({a, b});
818 }
819
820 SmallVector<SmallVector<int, 4>, 6> freeMsels(numArbiters);
821 SmallVector<SmallVector<size_t, 4>, 6> excludedUnits(numArbiters);
822 for (int a = 0; a < numArbiters; a++) {
823 for (int m = 0; m < numMselsPerArbiter; m++)
824 if (!reservedAmsels.count(amselOf(a, m)))
825 freeMsels[a].push_back(m);
826 for (size_t f = 0; f < flows.size(); f++)
827 if (excluded(f, a) && !llvm::is_contained(excludedUnits[a], flowUnit[f]))
828 excludedUnits[a].push_back(flowUnit[f]);
829 }
830 size_t mostFree = 0;
831 for (const SmallVector<int, 4> &free : freeMsels)
832 mostFree = std::max(mostFree, free.size());
833 if (llvm::any_of(units, [&](const Unit &unit) {
834 return unit.masterSets.size() > mostFree;
835 }))
836 return std::nullopt;
837
838 // Most constrained first.
839 SmallVector<size_t, 8> order(units.size());
840 std::iota(order.begin(), order.end(), 0);
841 llvm::stable_sort(order, [&](size_t a, size_t b) {
842 return std::make_pair(neighbors[a].size(), units[a].masterSets.size()) >
843 std::make_pair(neighbors[b].size(), units[b].masterSets.size());
844 });
845
846 SmallVector<int, 8> arbiterOf(units.size(), -1);
847 SmallVector<size_t, 6> load(numArbiters, 0);
848 int steps = 0;
849 auto place = [&](auto &self, size_t depth) -> bool {
850 if (depth == order.size())
851 return true;
852 if (++steps > maxSearchSteps) {
853 LLVM_DEBUG(llvm::dbgs() << "Arbiter search gave up after "
854 << maxSearchSteps << " steps\n");
855 return false;
856 }
857 size_t u = order[depth];
858 SmallVector<int, 6> candidates(numArbiters);
859 std::iota(candidates.begin(), candidates.end(), 0);
860 if (units[u].isPriority)
861 std::reverse(candidates.begin(), candidates.end());
862 else
863 llvm::stable_sort(candidates, [&](int a, int b) {
864 return load[a] + numMselsPerArbiter - freeMsels[a].size() <
865 load[b] + numMselsPerArbiter - freeMsels[b].size();
866 });
867 std::set<std::pair<size_t, SmallVector<size_t, 4>>> triedEmpty;
868 for (int a : candidates) {
869 if (load[a] + units[u].masterSets.size() > freeMsels[a].size())
870 continue;
871 if (llvm::is_contained(excludedUnits[a], u) ||
872 llvm::any_of(neighbors[u],
873 [&](size_t v) { return arbiterOf[v] == a; }))
874 continue;
875 // Empty arbiters with as many free msels, ruled out for the same units,
876 // are interchangeable.
877 if (load[a] == 0 &&
878 !triedEmpty.insert({freeMsels[a].size(), excludedUnits[a]}).second)
879 continue;
880 arbiterOf[u] = a;
881 load[a] += units[u].masterSets.size();
882 if (self(self, depth + 1))
883 return true;
884 load[a] -= units[u].masterSets.size();
885 arbiterOf[u] = -1;
886 }
887 return false;
888 };
889 if (!place(place, 0)) {
890 blocking.append(crossPairs.begin(), crossPairs.end());
891 return std::nullopt;
892 }
893
894 SmallVector<size_t, 8> mselOrder(units.size());
895 std::iota(mselOrder.begin(), mselOrder.end(), 0);
896 llvm::stable_sort(mselOrder, [&](size_t a, size_t b) {
897 if (!units[a].isPriority || !units[b].isPriority)
898 return units[a].isPriority > units[b].isPriority;
899 return units[a].masterSets.front() < units[b].masterSets.front();
900 });
901 ArbiterPlan plan;
902 SmallVector<size_t, 6> low(numArbiters, 0), high(numArbiters, 0);
903 for (size_t u : mselOrder) {
904 const Unit &unit = units[u];
905 int a = arbiterOf[u];
906 std::map<SmallVector<Port, 4>, int> setAmsel;
907 for (const SmallVector<Port, 4> &masters : unit.masterSets) {
908 int msel = unit.isPriority
909 ? freeMsels[a][freeMsels[a].size() - 1 - high[a]++]
910 : freeMsels[a][low[a]++];
911 setAmsel[masters] = amselOf(a, msel);
912 plan.amselMasters[amselOf(a, msel)] = masters;
913 }
914 for (size_t f : unit.flows)
915 plan.slaveAmsels[{flows[f].slave, flows[f].id}] =
916 setAmsel.at(flows[f].masters);
917 }
918 return plan;
919}
920
921/// The tiles other than `src` and `dst` that every route between them passes.
922SmallVector<TileID> cutTiles(const AIETargetModel &targetModel, TileID src,
923 TileID dst) {
924 auto neighbors = [&](TileID t) {
925 SmallVector<TileID, 4> next;
926 for (auto [bundle, dc, dr] : {std::tuple{WireBundle::North, 0, 1},
927 {WireBundle::South, 0, -1},
928 {WireBundle::East, 1, 0},
929 {WireBundle::West, -1, 0}}) {
930 TileID n{t.col + dc, t.row + dr};
931 if (n.col >= 0 && n.col < targetModel.columns() && n.row >= 0 &&
932 n.row < targetModel.rows() &&
933 targetModel.getNumDestSwitchboxConnections(t.col, t.row, bundle) > 0)
934 next.push_back(n);
935 }
936 return next;
937 };
938 auto reach = [&](std::optional<TileID> avoid) {
939 return breadthFirstParents(
940 src,
941 [&](TileID t) {
942 SmallVector<TileID, 4> next = neighbors(t);
943 llvm::erase(next, avoid);
944 return next;
945 },
946 std::optional{dst});
947 };
948 std::map<TileID, TileID> via = reach(std::nullopt);
949 if (!via.count(dst))
950 return {};
951 SmallVector<TileID> interior;
952 for (TileID t = via.at(dst); t != src; t = via.at(t))
953 interior.push_back(t);
954 llvm::erase_if(interior, [&](TileID t) { return reach(t).count(dst) > 0; });
955 return interior;
956}
957
958/// The tile, port and id of each packet a prioritized flow (priority_route)
959/// sends.
960struct PrioritizedPackets {
961 std::set<std::tuple<TileID, Port, int>> packets;
962 bool contains(const RoutedStream &s) const {
963 return s.packetID && packets.count({s.src.tile, s.src.port, *s.packetID});
964 }
965};
966
967PrioritizedPackets prioritizedPackets(DeviceOp device) {
968 PrioritizedPackets prioritized;
969 for (PacketFlowOp flow : device.getOps<PacketFlowOp>())
970 if (flow.getPriorityRoute().value_or(false))
971 for (auto src : flow.getPorts().getOps<PacketSourceOp>())
972 prioritized.packets.insert(
973 {cast<TileOp>(src.getTile().getDefiningOp()).getTileID(),
974 src.port(), flow.IDInt()});
975 return prioritized;
976}
977
978/// The largest set of `candidates` that must be kept apart pairwise
979/// (StreamConflicts::mustSeparate). The search stops once it finds one larger
980/// than `limit` or runs out of steps.
981SmallVector<size_t, 8> largestApartSet(const StreamConflicts &conflicts,
982 ArrayRef<size_t> candidates,
983 size_t limit) {
984 SmallVector<size_t, 8> clique, best;
985 int steps = 0;
986 auto grow = [&](auto &self, ArrayRef<size_t> cands) -> void {
987 if (clique.size() > best.size())
988 best = clique;
989 for (auto [k, s] : llvm::enumerate(cands)) {
990 if (best.size() > limit || ++steps > maxSearchSteps ||
991 clique.size() + cands.size() - k <= best.size())
992 return;
993 SmallVector<size_t, 8> next;
994 for (size_t t : cands.drop_front(k + 1))
995 if (conflicts.mustSeparate(s, t))
996 next.push_back(t);
997 clique.push_back(s);
998 self(self, next);
999 clique.pop_back();
1000 }
1001 };
1002 grow(grow, candidates);
1003 return best;
1004}
1005
1006/// The amsels, as arbiter + msel * arbiters, the input's switchboxes already
1007/// configure, by tile. An amsel no master set uses still has rules steering
1008/// packets to it.
1009std::map<TileID, std::set<int>> configuredAmsels(DeviceOp device) {
1010 const int numArbiters = device.getTargetModel().getNumArbiters();
1011 std::map<TileID, std::set<int>> amsels;
1012 for (auto swboxOp : device.getOps<SwitchboxOp>())
1013 for (auto amselOp : swboxOp.getConnections().getOps<AMSelOp>())
1014 amsels[swboxOp.getTileOp().getTileID()].insert(
1015 amselOp.arbiterIndex() + amselOp.getMselValue() * numArbiters);
1016 return amsels;
1017}
1018
1019/// Packet streams take an arbiter at the tile they end at whatever the
1020/// routing, and where `pinsHops` says hops cannot be circuit switched, or the
1021/// stream is prioritized, at the tile they start at and every tile each of
1022/// their routes passes too. Two that must be kept apart pass any tile on
1023/// different slave ports -- sharing one means they merged, unsafely, upstream
1024/// -- so a set of them that must be kept apart pairwise needs an arbiter
1025/// apiece. Says why no routing can work if some tile has such a set larger
1026/// than its free arbiters.
1027std::optional<std::string>
1028tooFewArbiters(DeviceOp device, const StreamConflicts &conflicts,
1029 llvm::function_ref<bool(TileID)> pinsHops,
1030 const PrioritizedPackets &prioritized) {
1031 const AIETargetModel &targetModel = device.getTargetModel();
1032 const int numArbiters = targetModel.getNumArbiters();
1033 const int numMselsPerArbiter = targetModel.getNumMselsPerArbiter();
1034 std::map<TileID, SmallVector<size_t, 8>> pinned;
1035 for (auto [i, s] : llvm::enumerate(conflicts.getRequestedStreams())) {
1036 if (!s.packetID)
1037 continue;
1038 pinned[s.dst.tile].push_back(i);
1039 if (s.src.tile == s.dst.tile)
1040 continue;
1041 bool circuitless = prioritized.contains(s);
1042 if (circuitless || pinsHops(s.src.tile))
1043 pinned[s.src.tile].push_back(i);
1044 for (TileID t : cutTiles(targetModel, s.src.tile, s.dst.tile))
1045 if (circuitless || pinsHops(t))
1046 pinned[t].push_back(i);
1047 }
1048 std::map<TileID, std::set<int>> reserved = configuredAmsels(device);
1049
1050 ArrayRef<RoutedStream> streams = conflicts.getStreams();
1051 for (const auto &[tileId, candidates] : pinned) {
1052 const std::set<int> &taken = reserved[tileId];
1053 size_t free = 0;
1054 for (int a = 0; a < numArbiters; a++)
1055 free += llvm::any_of(llvm::seq(numMselsPerArbiter), [&](int m) {
1056 return !taken.count(a + m * numArbiters);
1057 });
1058 // Streams that must be kept apart have distinct sources and destinations.
1059 std::set<std::pair<TileID, Port>> srcs, dsts;
1060 for (size_t s : candidates) {
1061 srcs.insert({streams[s].src.tile, streams[s].src.port});
1062 dsts.insert({streams[s].dst.tile, streams[s].dst.port});
1063 }
1064 if (std::min(srcs.size(), dsts.size()) <= free)
1065 continue;
1066 SmallVector<size_t, 8> best = largestApartSet(conflicts, candidates, free);
1067 if (best.size() <= free)
1068 continue;
1069
1070 std::string reason;
1071 llvm::raw_string_ostream os(reason);
1072 if (best.size() == 1) {
1073 os << "at tile (" << tileId.col << ", " << tileId.row << "), "
1074 << describeStream(streams[best[0]])
1075 << " takes an arbiter whatever the routing, but the switchbox has "
1076 "none free";
1077 return reason;
1078 }
1079 os << "at tile (" << tileId.col << ", " << tileId.row << "), no two of ";
1080 llvm::interleave(
1081 best, os, [&](size_t s) { os << describeStream(streams[s]); }, ", ");
1082 os << " can share an arbiter, and each takes one there whatever the "
1083 "routing, but the switchbox has "
1084 << free << " free. For example, " << conflicts.explain(best[0], best[1]);
1085 return reason;
1086 }
1087 return std::nullopt;
1088}
1089
1090/// Where a stream leaves a tile it is known to pass: by which master port from
1091/// which slave port, if known.
1092struct Leaving {
1093 size_t stream;
1094 std::optional<Port> slave;
1095 Port master;
1096};
1097
1098/// Where each stream leaves each tile on the trees in `pinnedTrees`, and the
1099/// tiles those trees pass.
1100std::pair<std::map<TileID, SmallVector<Leaving, 8>>, std::set<TileID>>
1101leavingPinnedTrees(const StreamConflicts &conflicts,
1102 const PacketTrees &pinnedTrees,
1103 const PrioritizedPackets &prioritized) {
1104 // Each hop of a pinned tree by the hop before it, unset where two lead to it.
1105 std::map<PathEndPoint, std::map<PathEndPoint, std::optional<PathEndPoint>>>
1106 preds;
1107 for (const auto &[src, hops] : pinnedTrees)
1108 for (const TreeHop &hop : hops) {
1109 auto [it, first] = preds[src].try_emplace(hop.to, hop.from);
1110 if (!first && it->second && !(*it->second == hop.from))
1111 it->second.reset();
1112 }
1113 std::map<TileID, SmallVector<Leaving, 8>> leaving;
1114 std::set<TileID> onTrees;
1115 for (auto [i, s] : llvm::enumerate(conflicts.getRequestedStreams())) {
1116 if (!s.packetID)
1117 continue;
1118 // Only the prioritized packets of a source take its tree.
1119 auto tree = prioritized.contains(s) ? preds.find({s.src.tile, s.src.port})
1120 : preds.end();
1121 SmallVector<std::pair<Port, PathEndPoint>, 8> hops;
1122 PathEndPoint at{s.dst.tile, s.dst.port}, src{s.src.tile, s.src.port};
1123 for (size_t n = 0;
1124 tree != preds.end() && !(at == src) && n <= tree->second.size(); n++) {
1125 auto pred = tree->second.find(at);
1126 if (pred == tree->second.end() || !pred->second)
1127 break;
1128 if (pred->second->coords == at.coords)
1129 hops.push_back({pred->second->port, at});
1130 at = *pred->second;
1131 }
1132 if (!(at == src)) {
1133 leaving[s.dst.tile].push_back({i, std::nullopt, s.dst.port});
1134 continue;
1135 }
1136 for (auto [slave, hop] : hops) {
1137 leaving[hop.coords].push_back({i, slave, hop.port});
1138 onTrees.insert(hop.coords);
1139 }
1140 }
1141 return {std::move(leaving), std::move(onTrees)};
1142}
1143
1144/// A visit of `here` on one arbiter with another: the other visit, and the
1145/// master port they leave by or the slave port they share a packet rule on.
1146struct ArbiterLink {
1147 size_t visit;
1148 Port port;
1149 bool rule;
1150};
1151
1152/// Says why `a` and `b`, which must be kept apart, end up on one arbiter at
1153/// `tileId` through the visits in `chain`.
1154std::string explainSharedArbiter(TileID tileId, size_t a, size_t b,
1155 ArrayRef<ArbiterLink> chain,
1156 ArrayRef<Leaving> here,
1157 const StreamConflicts &conflicts) {
1158 ArrayRef<RoutedStream> streams = conflicts.getStreams();
1159 std::string reason;
1160 llvm::raw_string_ostream os(reason);
1161 os << "at tile (" << tileId.col << ", " << tileId.row
1162 << "), the routes prioritized flows (priority_route) keep put "
1163 << describeStream(streams[a]) << " and " << describeStream(streams[b])
1164 << " on one arbiter: " << describeStream(streams[a]);
1165 for (auto [k, link] : llvm::enumerate(chain))
1166 os << (k == 0 ? "" : ", which")
1167 << (link.rule ? " takes one packet rule on " : " leaves by ")
1168 << describePort(link.port) << " with "
1169 << describeStream(streams[here[link.visit].stream]);
1170 os << ", and a master port or packet rule takes one arbiter. "
1171 << conflicts.explain(a, b);
1172 return reason;
1173}
1174
1175/// Says why no routing can work if two streams that must be kept apart leave
1176/// `tileId` by master ports that streams leaving by one each join, which puts
1177/// them on one arbiter.
1178std::optional<std::string> sharedArbiterAt(TileID tileId,
1179 ArrayRef<Leaving> here,
1180 const StreamConflicts &conflicts) {
1181 ArrayRef<RoutedStream> streams = conflicts.getStreams();
1182 // A stream packet switched at a master port takes its one arbiter, and
1183 // packets with one id on a slave port take one packet rule's arbiter.
1184 // The visits on one arbiter with each. A stream passing a tile twice takes
1185 // an arbiter on each visit, so the nodes are visits.
1186 std::map<size_t, SmallVector<ArbiterLink, 4>> with;
1187 for (auto [x, l] : llvm::enumerate(here))
1188 for (auto [y, m] : llvm::enumerate(here)) {
1189 if (x == y)
1190 continue;
1191 if (l.master == m.master)
1192 with[x].push_back({y, l.master, false});
1193 else if (l.slave && m.slave && *l.slave == *m.slave &&
1194 streams[l.stream].packetID == streams[m.stream].packetID)
1195 with[x].push_back({y, *l.slave, true});
1196 }
1197 for (size_t x : llvm::make_first_range(with)) {
1198 // The chain of visits that joins `x` to each visit it reaches.
1199 std::map<size_t, size_t> via = breadthFirstParents(x, [&](size_t u) {
1200 return llvm::map_range(
1201 with.at(u), [](const ArbiterLink &link) { return link.visit; });
1202 });
1203 size_t a = here[x].stream;
1204 for (size_t y : llvm::make_first_range(via)) {
1205 size_t b = here[y].stream;
1206 if (b <= a || !conflicts.mustSeparate(a, b))
1207 continue;
1208 SmallVector<ArbiterLink, 4> chain;
1209 for (size_t v = y; v != x; v = via.at(v))
1210 chain.push_back(
1211 *llvm::find_if(with.at(via.at(v)), [&](const ArbiterLink &link) {
1212 return link.visit == v;
1213 }));
1214 std::reverse(chain.begin(), chain.end());
1215 return explainSharedArbiter(tileId, a, b, chain, here, conflicts);
1216 }
1217 }
1218 return std::nullopt;
1219}
1220
1221/// A RoutingFailure if no routing can work because the arbiters packet streams
1222/// take whatever the routing do not fit: too few free ones at a tile, or, as a
1223/// PinnedRoutingFailure, two streams that must be kept apart put on one by the
1224/// trees in `pinnedTrees`, which prioritized sources keep.
1225llvm::Error unroutableArbiters(DeviceOp device,
1226 const StreamConflicts &conflicts,
1227 llvm::function_ref<bool(TileID)> pinsHops,
1228 const PacketTrees &pinnedTrees) {
1229 PrioritizedPackets prioritized = prioritizedPackets(device);
1230 if (std::optional<std::string> reason =
1231 tooFewArbiters(device, conflicts, pinsHops, prioritized))
1232 return llvm::make_error<RoutingFailure>(std::move(*reason));
1233 if (pinnedTrees.empty())
1234 return llvm::Error::success();
1235 auto [leaving, onTrees] =
1236 leavingPinnedTrees(conflicts, pinnedTrees, prioritized);
1237 for (TileID tileId : onTrees)
1238 if (std::optional<std::string> reason =
1239 sharedArbiterAt(tileId, leaving[tileId], conflicts))
1240 return llvm::make_error<PinnedRoutingFailure>(std::move(*reason));
1241 return llvm::Error::success();
1242}
1243} // namespace
1244
1245static void getOrCreateConnect(OpBuilder &builder, ShimMuxOp shimMux,
1246 Location loc, WireBundle srcBundle, int srcCh,
1247 WireBundle destBundle, int destCh) {
1248 for (auto connect : shimMux.getConnections().getOps<ConnectOp>())
1249 if (connect.getSourceBundle() == srcBundle &&
1250 connect.getSourceChannel() == srcCh &&
1251 connect.getDestBundle() == destBundle &&
1252 connect.getDestChannel() == destCh)
1253 return;
1254 ConnectOp::create(builder, loc, srcBundle, srcCh, destBundle, destCh);
1255}
1256
1257static PathEndPoint sourceOf(FlowOp flow) {
1258 auto tile = cast<TileOp>(flow.getSource().getDefiningOp());
1259 return PathEndPoint{tile.getTileID(),
1260 {flow.getSourceBundle(), flow.getSourceChannel()}};
1261}
1262
1263// The router names a shim DMA by its own port; move the rules and master sets
1264// that use one behind the shim mux, onto the South channel it reaches the
1265// switchbox by (see shimMuxChannelFrom).
1266static void lowerShimDMAPorts(DeviceOp device, OpBuilder &builder,
1267 DynamicTileAnalysis &analyzer) {
1268 for (auto switchbox : device.getOps<SwitchboxOp>()) {
1269 TileOp tileOp = switchbox.getTileOp();
1270 if (!tileOp.isShimNOCTile())
1271 continue;
1272 auto connectInMux = [&](Location loc, Port src, Port dst) {
1273 builder.setInsertionPointAfter(tileOp);
1274 ShimMuxOp shimMux = analyzer.getShimMux(builder, tileOp.colIndex());
1275 builder.setInsertionPointToStart(&shimMux.getConnections().front());
1276 getOrCreateConnect(builder, shimMux, loc, src.bundle, src.channel,
1277 dst.bundle, dst.channel);
1278 };
1279 for (Operation &op : switchbox.getConnections().front()) {
1280 if (auto rules = dyn_cast<PacketRulesOp>(op);
1281 rules && rules.getSourceBundle() == WireBundle::DMA) {
1282 int ch = shimMuxChannelFrom(rules.sourcePort());
1283 connectInMux(rules.getLoc(), rules.sourcePort(),
1284 {WireBundle::North, ch});
1285 rules.setSourceBundle(WireBundle::South);
1286 rules.setSourceChannel(ch);
1287 }
1288 if (auto masterSet = dyn_cast<MasterSetOp>(op);
1289 masterSet && masterSet.getDestBundle() == WireBundle::DMA) {
1290 int ch = shimMuxChannelTo(masterSet.destPort());
1291 connectInMux(masterSet.getLoc(), {WireBundle::North, ch},
1292 masterSet.destPort());
1293 masterSet.setDestBundle(WireBundle::South);
1294 masterSet.setDestChannel(ch);
1295 }
1296 }
1297 }
1298}
1299
1300namespace {
1301// How runOnPacketFlow lowers the packet flows on one routing: the connections
1302// the routing lays down and the arbiters planned for them.
1303struct PacketPlan {
1304 LogicalResult emit(DeviceOp device, OpBuilder &builder,
1305 DynamicTileAnalysis &analyzer) const;
1306 SmallVector<std::pair<int, int>, 2>
1307 statedCubes(const std::pair<PhysPort, int> &slaveFlow, int idMask) const;
1308
1309 // A hold cycle through waits at receivers the trees share that no arbiter
1310 // assignment found breaks.
1311 std::optional<HoldCycle> sharedReceiverCycle;
1312
1313 // The master ports packets with each flow ID leave by, keyed by the slave
1314 // port they enter.
1315 std::map<std::pair<PhysPort, int>, SmallVector<PhysPort, 4>> packetFlows;
1316 SmallVector<std::pair<PhysPort, int>, 4> slavePorts;
1317 // Where the packet flows entering each slave port with each ID were
1318 // written, so the routing they become points back at them.
1319 std::map<std::pair<PhysPort, int>, SmallVector<Location, 1>> slaveFlowLocs;
1320 // The packet flows' locations in the order the flows were written.
1321 DenseMap<Location, unsigned> flowLocOrder;
1322 // The flows behind `slaveFlows`, fused, or `fallback` if none.
1323 Location locOf(ArrayRef<std::pair<PhysPort, int>> slaveFlows,
1324 Location fallback) const;
1325 // Flag to keep packet header at packet flow destination
1326 DenseMap<PhysPort, BoolAttr> keepPktHeaderAttr;
1327 // The slave ports and IDs that carry prioritized packets. A switchbox routes
1328 // on the ID alone, so a flow sharing both with a priority flow is one too.
1329 DenseSet<std::pair<PhysPort, int>> prioritizedFlows;
1330 DenseSet<std::pair<PhysPort, int>> markedFlows;
1331 DenseSet<PhysPort> priorityMasterPorts;
1332
1333 // Packet-rule masks the flows state, keyed by the slave port the stream
1334 // enters and the flow ID. One ID may reach a port under two masks, so the
1335 // ID alone does not identify the claim, and flows sharing both may each
1336 // state a mask of their own, which the port then claims together.
1337 std::map<std::pair<PhysPort, int>, std::set<int>> pinnedMasks;
1338
1339 // A switchbox with more packet master ports than free arbiters has to put
1340 // two master ports on one arbiter, and an arbiter holds its grant until
1341 // tlast, so one stalled packet then holds up an unrelated flow. A hop that
1342 // alone uses both its ports needs no arbiter: a circuit connection passes the
1343 // header and tlast through, and the next switchbox routes the packet as
1344 // before. The last hop stays packet-switched, since it drops the header.
1345 // A circuit may broadcast, so a slave port qualifies with all the master
1346 // ports it reaches, provided it alone feeds them and every packet goes to
1347 // all of them.
1348 std::map<TileID, SmallVector<Connect, 4>> circuitHops;
1349 std::map<TileID, ArbiterPlan> plans;
1350};
1351
1352// Plans the packet flows on a routing, leaving the IR alone. Where no plan
1353// fits, the faults say which connections are in the way.
1354struct PacketFlowRouting : PacketPlan {
1355 using FlowKey = std::pair<Port, int>;
1356
1357 PacketFlowRouting(DeviceOp device, const Routing &routing,
1358 const StreamConflicts &conflicts,
1359 const PinnedRoutes &pinned, bool routeCircuit,
1360 bool circuitSwitchHops, bool prioritize)
1361 : device(device), routing(routing), conflicts(conflicts), pinned(pinned),
1362 prioritize(prioritize), routeCircuit(routeCircuit),
1363 circuitSwitchHops(circuitSwitchHops),
1364 targetModel(device.getTargetModel()),
1365 numArbiters(targetModel.getNumArbiters()),
1366 numMselsPerArbiter(targetModel.getNumMselsPerArbiter()),
1367 maxPacketId(targetModel.getMaxPacketId()),
1368 idBits(targetModel.getPacketIdBits()),
1369 idMask(targetModel.getPacketIdMask()) {}
1370
1371 llvm::Expected<PacketPlan> plan();
1372 void collectFlows();
1373 void findCircuitHops();
1374 void collectSlaveFlows();
1375 void checkRules();
1376 void planTiles();
1377 std::optional<std::string> breakHoldCycles();
1378 RoutingFaults faults() const;
1379
1380 const SwitchSettings &settingsOf(const PathEndPoint &src,
1381 std::optional<int> id = std::nullopt);
1382 std::optional<std::pair<size_t, size_t>>
1383 conflictingStreams(TileID tileId, const SlaveFlow &a, const SlaveFlow &b);
1384 std::optional<ArbiterPlan>
1385 planTile(TileID tileId, SmallVectorImpl<std::pair<size_t, size_t>> &blocking);
1386 void moveFlow(TileID tileId, FlowKey key, bool priority = false);
1387 void moveUnit(TileID tileId, FlowKey key);
1388 void splitFlow(TileID tileId, FlowKey key, ArrayRef<FlowKey> partners);
1389
1390 DeviceOp device;
1391 const Routing &routing;
1392 const StreamConflicts &conflicts;
1393 const PinnedRoutes &pinned;
1394 // Whether prioritized flows not pinned are prioritized here.
1395 bool prioritize;
1396 bool routeCircuit;
1397 bool circuitSwitchHops;
1398 const AIETargetModel &targetModel;
1399 const int numArbiters;
1400 const int numMselsPerArbiter;
1401 const uint32_t maxPacketId;
1402 const int idBits;
1403 const int idMask;
1404
1405 // The streams each slave flow carries, for asking whether two flows can
1406 // deadlock on an arbiter. Flows with one source, destination and id may
1407 // state different masks, so carry different ids, and each is a stream of
1408 // its own.
1409 struct StreamEnds {
1410 PathEndPoint src, dst;
1411 int id;
1412 bool operator<(const StreamEnds &rhs) const {
1413 return std::tie(src, dst, id) < std::tie(rhs.src, rhs.dst, rhs.id);
1414 }
1415 };
1416 std::map<StreamEnds, SmallVector<size_t, 1>> packetStreamIndex;
1417 DenseMap<std::pair<PhysPort, int>, SmallVector<size_t, 2>> slaveFlowStreams;
1418 // Each source's part of a SlaveFlow (see SlaveFlow). A switchbox routes on
1419 // the id alone, so sources sharing an id there go everywhere any of them
1420 // does.
1421 std::map<std::pair<PhysPort, int>, std::map<PathEndPoint, std::set<Port>>>
1422 slaveFlowSources;
1423 // Every stream's hops, source first; the requested ones as this routing
1424 // lays them, the rest as the design already does.
1425 std::vector<SmallVector<StreamHop, 8>> routes;
1426 // Sources routed as circuits, which runOnFlow lowers.
1427 std::set<PathEndPoint> circuitSources;
1428 const SwitchSettings noSettings;
1429
1430 // The logical model of all the switchboxes.
1431 std::map<TileID, SmallVector<std::pair<Connect, int>, 8>> switchboxes;
1432 // <arbiter, msel> slots (per tile) that packet-switch configuration in the
1433 // input IR already occupies. Kept apart from masterAMSels so the allocator
1434 // run does not re-emit those ops.
1435 std::map<TileID, std::set<int>> reservedAmsels;
1436 // Each switchbox has its arbiters planned as a whole (see planArbiters).
1437 // Where that is impossible the routing is unusable, and the connections of
1438 // the flows in the way are what the router has to move.
1439 std::map<TileID, std::map<FlowKey, SlaveFlow>> tileSlaveFlows;
1440 std::map<TileID, SmallVector<SlaveFlow, 8>> tileFlows;
1441 // What the search below learns: flows to keep on different arbiters, and
1442 // flows to keep off an arbiter that flows already in the design take.
1443 std::set<std::tuple<TileID, FlowKey, FlowKey>> apart;
1444 std::set<std::tuple<TileID, FlowKey, int>> offArbiter;
1445 std::set<std::pair<TileID, Connect>> hazardConnections;
1446 std::set<std::pair<TileID, Connect>> priorityConnections;
1447 // The TreeSplits (see TreeSplit) the routing check asks for. `key` branches
1448 // from the flows of its source that tie it to one of `partners`, where
1449 // nothing else does. The next routing may reach the tile by another slave
1450 // port, so the split holds for the tile.
1451 std::set<TreeSplit> hazardSplits;
1452 std::set<std::pair<PathEndPoint, PathEndPoint>> hazardApart;
1453 std::set<std::pair<PathEndPoint, PathEndPoint>> hazardTogether;
1454 std::set<PathEndPoint> hazardUntrunk;
1455 std::set<TileID> crowdedTiles;
1456 std::optional<std::string> planFailure;
1457 std::optional<std::pair<Location, std::string>> incomplete;
1458};
1459} // namespace
1460
1461void PacketFlowRouting::collectFlows() {
1462 for (auto [i, s] : llvm::enumerate(conflicts.getStreams()))
1463 if (s.packetID)
1464 packetStreamIndex[{{s.src.tile, s.src.port},
1465 {s.dst.tile, s.dst.port},
1466 *s.packetID}]
1467 .push_back(i);
1468 for (const RoutedStream &s : conflicts.getStreams())
1469 routes.push_back(s.hops);
1470
1471 if (routeCircuit)
1472 for (FlowOp flow : device.getOps<FlowOp>())
1473 circuitSources.insert(sourceOf(flow));
1474
1475 for (PacketFlowOp pktFlowOp : device.getOps<PacketFlowOp>()) {
1476 Region &r = pktFlowOp.getPorts();
1477 Block &b = r.front();
1478 int flowID = pktFlowOp.IDInt();
1479 SmallVector<std::pair<TileID, Port>, 4> sources;
1480
1481 // Pass 1: collect all sources (order-independent; supports fan-in).
1482 for (Operation &Op : b.getOperations()) {
1483 if (auto pktSource = dyn_cast<PacketSourceOp>(Op)) {
1484 auto srcTile = cast<TileOp>(pktSource.getTile().getDefiningOp());
1485 sources.push_back(
1486 {{srcTile.colIndex(), srcTile.rowIndex()}, pktSource.port()});
1487 }
1488 }
1489 // Pass 2: lower each (source, destination) pair so fan-in flows lay
1490 // down switchbox connections for every source, not just the last one.
1491 for (Operation &Op : b.getOperations()) {
1492 auto pktDest = dyn_cast<PacketDestOp>(Op);
1493 if (!pktDest)
1494 continue;
1495 auto destTile = cast<TileOp>(pktDest.getTile().getDefiningOp());
1496 Port destPort = pktDest.port();
1497 TileID destCoords = {destTile.colIndex(), destTile.rowIndex()};
1498 // Assign "keep_pkt_header flag"
1499 auto keep = pktFlowOp.getKeepPktHeader();
1500 keepPktHeaderAttr[{destTile.getTileID(), destPort}] =
1501 keep ? BoolAttr::get(Op.getContext(), *keep) : nullptr;
1502
1503 for (auto &[srcCoords, srcPort] : sources) {
1504 TileID srcSB = {srcCoords.col, srcCoords.row};
1505 PathEndPoint srcPoint = {srcSB, srcPort};
1506 if (circuitSources.count(srcPoint))
1507 continue;
1508 const SwitchSettings &settings = settingsOf(srcPoint, flowID);
1509 // The requested streams this flow asks for here; with none, the
1510 // stream the design already routes.
1511 SmallVector<size_t, 1> flowStreams;
1512 if (auto stream = packetStreamIndex.find(
1513 {srcPoint, {destCoords, destPort}, flowID});
1514 stream != packetStreamIndex.end()) {
1515 int mask = static_cast<int>(pktFlowOp.getMask().value_or(~0));
1516 for (size_t i : stream->second)
1517 if (i < conflicts.getRequestedStreams().size() &&
1518 conflicts.getStreams()[i].packetMask == mask)
1519 flowStreams.push_back(i);
1520 if (flowStreams.empty())
1521 flowStreams.push_back(stream->second.front());
1522 }
1523 for (size_t stream : flowStreams) {
1524 SmallVector<StreamHop, 8> &hops = routes[stream];
1525 hops.clear();
1526 // A route may pass a switchbox more than once, but no connection.
1527 size_t connections = 0;
1528 for (const auto &[_, setting] : settings)
1529 connections += setting.srcs.size();
1530 std::optional<std::pair<TileID, Port>> at{{srcSB, srcPort}};
1531 while (at && hops.size() <= connections) {
1532 auto [tile, input] = *at;
1533 hops.push_back({tile, input, std::nullopt});
1534 at.reset();
1535 auto setting = settings.find(tile);
1536 if (setting == settings.end())
1537 break;
1538 for (auto [src, dest] :
1539 llvm::zip(setting->second.srcs, setting->second.dsts))
1540 if (src == input && !(tile == destCoords && dest == destPort) &&
1541 findPathToDest(settings, tile, dest, destCoords, destPort)) {
1542 at = linkedInput(tile, dest);
1543 break;
1544 }
1545 }
1546 }
1547 // Track whether the source's own switch connection survives routing.
1548 bool srcRouted = false;
1549 // add connections for all the Switchboxes in SwitchSettings
1550 for (const auto &[curr, setting] : settings) {
1551 assert(setting.srcs.size() == setting.dsts.size());
1552 TileID currTile = {curr.col, curr.row};
1553 for (size_t i = 0; i < setting.srcs.size(); i++) {
1554 Port src = setting.srcs[i];
1555 Port dest = setting.dsts[i];
1556 // reject false broadcast
1557 if (!findPathToDest(settings, currTile, dest, destCoords, destPort))
1558 continue;
1559 if (currTile == srcSB && src.bundle == srcPort.bundle &&
1560 src.channel == srcPort.channel)
1561 srcRouted = true;
1562 Connect connect = {{src.bundle, src.channel},
1563 {dest.bundle, dest.channel}};
1564 if (std::find(
1565 switchboxes[currTile].begin(), switchboxes[currTile].end(),
1566 std::pair{connect, flowID}) == switchboxes[currTile].end())
1567 switchboxes[currTile].push_back({connect, flowID});
1568 // Keyed by slave port as well as ID, since IDs are reused across
1569 // unrelated flows.
1570 PhysPort slavePort = {currTile, {src.bundle, src.channel}};
1571 std::pair<PhysPort, int> slaveFlow = {slavePort, flowID};
1572 for (size_t stream : flowStreams)
1573 if (!llvm::is_contained(slaveFlowStreams[slaveFlow], stream))
1574 slaveFlowStreams[slaveFlow].push_back(stream);
1575 slaveFlowSources[slaveFlow][srcPoint].insert(dest);
1576 if (!llvm::is_contained(slaveFlowLocs[slaveFlow],
1577 pktFlowOp.getLoc()))
1578 slaveFlowLocs[slaveFlow].push_back(pktFlowOp.getLoc());
1579 flowLocOrder.try_emplace(pktFlowOp.getLoc(), flowLocOrder.size());
1580 if (std::optional<uint8_t> mask = pktFlowOp.getMask()) {
1581 pinnedMasks[{{currTile, {src.bundle, src.channel}}, flowID}]
1582 .insert(*mask);
1583 }
1584 if (pktFlowOp.getPriorityRoute().value_or(false)) {
1585 markedFlows.insert(slaveFlow);
1586 if (prioritize || pinned.trees.count(srcPoint)) {
1587 prioritizedFlows.insert(slaveFlow);
1588 }
1589 }
1590 }
1591 }
1592 if (!srcRouted && !incomplete)
1593 incomplete = {
1594 pktFlowOp.getLoc(),
1595 "packet flow source " + describeTilePort(srcCoords, srcPort) +
1596 " could not be routed to destination " +
1597 describeTilePort(destCoords, destPort) +
1598 "; the pathfinder produced an incomplete routing for this "
1599 "placement."};
1600 }
1601 }
1602 }
1603}
1604
1605Location PacketPlan::locOf(ArrayRef<std::pair<PhysPort, int>> slaveFlows,
1606 Location fallback) const {
1607 SmallVector<Location, 2> locs;
1608 for (const auto &flow : slaveFlows)
1609 if (auto found = slaveFlowLocs.find(flow); found != slaveFlowLocs.end())
1610 for (Location loc : found->second)
1611 if (!llvm::is_contained(locs, loc))
1612 locs.push_back(loc);
1613 if (locs.empty())
1614 return fallback;
1615 llvm::sort(locs, [&](Location a, Location b) {
1616 return flowLocOrder.lookup(a) < flowLocOrder.lookup(b);
1617 });
1618 return FusedLoc::get(fallback.getContext(), locs);
1619}
1620
1621// The rules the flows through `slaveFlow` state. A full-width mask selects the
1622// id alone, which the cover states just as well, so only a wider claim becomes
1623// a rule of its own.
1624SmallVector<std::pair<int, int>, 2>
1625PacketPlan::statedCubes(const std::pair<PhysPort, int> &slaveFlow,
1626 int idMask) const {
1627 SmallVector<std::pair<int, int>, 2> cubes;
1628 auto it = pinnedMasks.find(slaveFlow);
1629 if (it != pinnedMasks.end())
1630 for (int mask : it->second)
1631 if (mask != idMask)
1632 cubes.push_back({mask, slaveFlow.second});
1633 return cubes;
1634}
1635
1636const SwitchSettings &PacketFlowRouting::settingsOf(const PathEndPoint &src,
1637 std::optional<int> id) {
1638 if (id)
1639 if (auto own = routing.idSettings.find({src, *id});
1640 own != routing.idSettings.end())
1641 return own->second;
1642 auto it = routing.settings.find(src);
1643 return it == routing.settings.end() ? noSettings : it->second;
1644}
1645
1646void PacketFlowRouting::findCircuitHops() {
1647 // Seed the reserved set from the packet-switch configuration the switchboxes
1648 // already carry, so this run allocates around it instead of over it.
1649 reservedAmsels = configuredAmsels(device);
1650
1651 // Ports the input's own aie.switchbox ops already drive, circuit or packet.
1652 std::set<PhysPort> claimedSlaves, claimedMasters;
1653 for (auto swbox : device.getOps<SwitchboxOp>()) {
1654 TileID tileId = swbox.getTileOp().getTileID();
1655 Region &ops = swbox.getConnections();
1656 for (auto connect : ops.getOps<ConnectOp>()) {
1657 claimedSlaves.insert({tileId, connect.sourcePort()});
1658 claimedMasters.insert({tileId, connect.destPort()});
1659 }
1660 for (auto rules : ops.getOps<PacketRulesOp>())
1661 claimedSlaves.insert({tileId, rules.sourcePort()});
1662 for (auto masterSet : ops.getOps<MasterSetOp>())
1663 claimedMasters.insert({tileId, masterSet.destPort()});
1664 }
1665 // Circuits not yet lowered claim their ports all the same.
1666 if (routeCircuit)
1667 for (FlowOp flow : device.getOps<FlowOp>())
1668 for (const auto &[tileId, setting] : settingsOf(sourceOf(flow))) {
1669 for (Port p : setting.srcs)
1670 claimedSlaves.insert({tileId, p});
1671 for (Port p : setting.dsts)
1672 claimedMasters.insert({tileId, p});
1673 }
1674 for (auto &[tileId, connects] : switchboxes) {
1675 if (!circuitSwitchHops ||
1676 targetModel.isShimNOCorPLTile(tileId.col, tileId.row))
1677 continue;
1678 std::set<Port> masters;
1679 for (const auto &[conn, flowID] : connects)
1680 masters.insert(conn.dst);
1681 SmallVector<Port, 8> slaves;
1682 for (const auto &[conn, flowID] : connects)
1683 if (!llvm::is_contained(slaves, conn.src))
1684 slaves.push_back(conn.src);
1685 const std::set<int> &reserved = reservedAmsels[tileId];
1686 size_t freeArbiters = llvm::count_if(llvm::seq(0, numArbiters), [&](int a) {
1687 return llvm::none_of(llvm::seq(0, numMselsPerArbiter), [&](int m) {
1688 return reserved.count(a + m * numArbiters);
1689 });
1690 });
1691 for (Port slave : slaves) {
1692 if (masters.size() <= freeArbiters)
1693 break;
1694 std::set<Port> reached;
1695 std::map<int, std::set<Port>> reachedByID;
1696 for (const auto &[conn, flowID] : connects)
1697 if (conn.src == slave) {
1698 reached.insert(conn.dst);
1699 reachedByID[flowID].insert(conn.dst);
1700 }
1701 bool exclusive =
1702 !claimedSlaves.count({tileId, slave}) &&
1703 llvm::all_of(reached,
1704 [&, tileId = tileId](Port m) {
1705 return isDirectional(m.bundle) &&
1706 !claimedMasters.count({tileId, m});
1707 }) &&
1708 llvm::all_of(
1709 reachedByID,
1710 [&](const auto &ids) { return ids.second == reached; }) &&
1711 llvm::all_of(connects, [&, tileId = tileId](const auto &entry) {
1712 const auto &[other, otherID] = entry;
1713 if (!reached.count(other.dst))
1714 return true;
1715 return other.src == slave &&
1716 !prioritizedFlows.contains({{tileId, slave}, otherID});
1717 });
1718 if (!exclusive)
1719 continue;
1720 for (Port m : reached) {
1721 circuitHops[tileId].push_back({slave, m});
1722 masters.erase(m);
1723 }
1724 llvm::erase_if(connects, [&](const auto &entry) {
1725 return entry.first.src == slave;
1726 });
1727 }
1728 }
1729}
1730
1731void PacketFlowRouting::collectSlaveFlows() {
1732 LLVM_DEBUG(llvm::dbgs() << "Check switchboxes\n");
1733
1734 for (const auto &[tileId, connects] : switchboxes) {
1735 LLVM_DEBUG(llvm::dbgs() << "***switchbox*** " << tileId.col << " "
1736 << tileId.row << '\n');
1737 for (const auto &[conn, flowID] : connects) {
1738 Port sourcePort = conn.src;
1739 Port destPort = conn.dst;
1740 auto sourceFlow =
1741 std::make_pair(std::make_pair(tileId, sourcePort), flowID);
1742 packetFlows[sourceFlow].push_back({tileId, destPort});
1743 if (markedFlows.contains(sourceFlow))
1744 priorityMasterPorts.insert({tileId, destPort});
1745 slavePorts.push_back(sourceFlow);
1746 LLVM_DEBUG(llvm::dbgs() << "flowID " << flowID << ':'
1747 << stringifyWireBundle(sourcePort.bundle) << " "
1748 << sourcePort.channel << " -> "
1749 << stringifyWireBundle(destPort.bundle) << " "
1750 << destPort.channel << "\n");
1751 }
1752 }
1753
1754 for (const auto &[flow, dests] : packetFlows) {
1755 SlaveFlow &f = tileSlaveFlows[flow.first.first]
1756 .try_emplace({flow.first.second, flow.second},
1757 SlaveFlow{flow.first.second,
1758 flow.second,
1759 {},
1760 prioritizedFlows.contains(flow)})
1761 .first->second;
1762 for (const PhysPort &dest : dests)
1763 if (!llvm::is_contained(f.masters, dest.second))
1764 f.masters.push_back(dest.second);
1765 llvm::sort(f.masters);
1766 }
1767 for (const auto &[tileId, byFlow] : tileSlaveFlows)
1768 for (const auto &[key, f] : byFlow)
1769 tileFlows[tileId].push_back(f);
1770}
1771
1772std::optional<std::pair<size_t, size_t>>
1773PacketFlowRouting::conflictingStreams(TileID tileId, const SlaveFlow &a,
1774 const SlaveFlow &b) {
1775 auto as = slaveFlowStreams.find({{tileId, a.slave}, a.id});
1776 auto bs = slaveFlowStreams.find({{tileId, b.slave}, b.id});
1777 if (as == slaveFlowStreams.end() || bs == slaveFlowStreams.end())
1778 return std::nullopt;
1779 for (size_t s : as->second)
1780 for (size_t t : bs->second)
1781 if (conflicts.conflict(s, t))
1782 return std::pair{s, t};
1783 return std::nullopt;
1784}
1785
1786std::optional<ArbiterPlan> PacketFlowRouting::planTile(
1787 TileID tileId, SmallVectorImpl<std::pair<size_t, size_t>> &blocking) {
1788 ArrayRef<SlaveFlow> flows = tileFlows.at(tileId);
1789 auto key = [&](size_t f) { return FlowKey{flows[f].slave, flows[f].id}; };
1790 auto conflict = [&](size_t a, size_t b) {
1791 return apart.count(
1792 {tileId, std::min(key(a), key(b)), std::max(key(a), key(b))}) ||
1793 conflictingStreams(tileId, flows[a], flows[b]);
1794 };
1795 auto excluded = [&](size_t f, int arbiter) {
1796 return offArbiter.count({tileId, key(f), arbiter}) > 0;
1797 };
1798 SmallVector<size_t, 8> priority, others;
1799 for (auto [i, f] : llvm::enumerate(flows))
1800 (f.isPriority ? priority : others).push_back(i);
1801 if (priority.empty() || (others.empty() && pinned.rules.empty()))
1802 return planArbiters(targetModel, flows, conflict, excluded,
1803 reservedAmsels[tileId], blocking);
1804
1805 auto subset = [&](ArrayRef<size_t> members) {
1806 SmallVector<SlaveFlow, 8> sub;
1807 for (size_t m : members)
1808 sub.push_back(flows[m]);
1809 return sub;
1810 };
1811 auto keepPinned = [&]() -> std::optional<ArbiterPlan> {
1812 ArbiterPlan kept;
1813 for (size_t f : priority) {
1814 Port slave = flows[f].slave;
1815 if (slave.bundle == WireBundle::DMA &&
1816 targetModel.isShimNOCTile(tileId.col, tileId.row))
1817 slave = {WireBundle::South, shimMuxChannelFrom(slave)};
1818 auto rules = pinned.rules.find({tileId, slave});
1819 const std::tuple<int, int, int> *rule = nullptr;
1820 if (rules != pinned.rules.end())
1821 rule = llvm::find_if(rules->second, [&](const auto &r) {
1822 auto [mask, value, amsel] = r;
1823 return (flows[f].id & mask) == (value & mask);
1824 });
1825 if (!rule || rule == rules->second.end())
1826 return std::nullopt;
1827 int amsel = std::get<2>(*rule);
1828 if (excluded(f, amsel % numArbiters) ||
1829 reservedAmsels[tileId].count(amsel) ||
1830 kept.amselMasters.try_emplace(amsel, flows[f].masters)
1831 .first->second != flows[f].masters)
1832 return std::nullopt;
1833 kept.slaveAmsels[key(f)] = amsel;
1834 }
1835 for (auto [k, a] : llvm::enumerate(priority))
1836 for (size_t b : llvm::drop_begin(priority, k + 1))
1837 if (kept.slaveAmsels.at(key(a)) % numArbiters ==
1838 kept.slaveAmsels.at(key(b)) % numArbiters &&
1839 flows[a].slave != flows[b].slave && conflict(a, b)) {
1840 return std::nullopt;
1841 }
1842 return kept;
1843 };
1844 SmallVector<std::pair<size_t, size_t>, 4> stuck;
1845 std::optional<ArbiterPlan> plan;
1846 if (!pinned.rules.empty())
1847 plan = keepPinned();
1848 if (!plan) {
1849 plan = planArbiters(
1850 targetModel, subset(priority),
1851 [&](size_t a, size_t b) { return conflict(priority[a], priority[b]); },
1852 [&](size_t f, int arbiter) { return excluded(priority[f], arbiter); },
1853 reservedAmsels[tileId], stuck);
1854 if (!plan) {
1855 for (auto [a, b] : stuck)
1856 blocking.push_back({priority[a], priority[b]});
1857 return std::nullopt;
1858 }
1859 }
1860 if (others.empty())
1861 return plan;
1862
1863 auto around = [&](ArbiterPlan plan, ArrayRef<size_t> planned,
1864 ArrayRef<size_t> pending,
1865 SmallVectorImpl<std::pair<size_t, size_t>> &blocking)
1866 -> std::optional<ArbiterPlan> {
1867 auto arbiterOf = [&](size_t f) {
1868 return plan.slaveAmsels.at(key(f)) % numArbiters;
1869 };
1870 SmallVector<size_t, 8> placed(planned), rest;
1871 for (size_t f : pending) {
1872 auto same = llvm::find_if(plan.amselMasters, [&](const auto &entry) {
1873 return entry.second == flows[f].masters;
1874 });
1875 if (same == plan.amselMasters.end()) {
1876 rest.push_back(f);
1877 continue;
1878 }
1879 for (size_t g : placed)
1880 if (arbiterOf(g) == same->first % numArbiters &&
1881 flows[g].slave != flows[f].slave && conflict(f, g))
1882 blocking.push_back({g, f});
1883 if (excluded(f, same->first % numArbiters))
1884 blocking.push_back({planned.front(), f});
1885 plan.slaveAmsels[key(f)] = same->first;
1886 placed.push_back(f);
1887 }
1888 if (!blocking.empty())
1889 return std::nullopt;
1890 if (rest.empty())
1891 return plan;
1892
1893 // A master port is tied to one arbiter, so a flow leaving by a master port
1894 // the plan has tied takes that arbiter.
1895 llvm::EquivalenceClasses<Port> tied = tiedMasters(flows);
1896 std::map<Port, std::set<int>> tiedArbiters;
1897 std::set<int> reserved = reservedAmsels[tileId];
1898 for (const auto &[amsel, masters] : plan.amselMasters) {
1899 reserved.insert(amsel);
1900 tiedArbiters[tied.getLeaderValue(masters.front())].insert(amsel %
1901 numArbiters);
1902 }
1903 SmallVector<std::pair<size_t, size_t>, 4> stuck;
1904 std::optional<ArbiterPlan> rested = planArbiters(
1905 targetModel, subset(rest),
1906 [&](size_t a, size_t b) { return conflict(rest[a], rest[b]); },
1907 [&](size_t f, int arbiter) {
1908 auto arbiters = tiedArbiters.find(
1909 tied.getLeaderValue(flows[rest[f]].masters.front()));
1910 return excluded(rest[f], arbiter) ||
1911 (arbiters != tiedArbiters.end() &&
1912 (arbiters->second.size() > 1 ||
1913 !arbiters->second.count(arbiter))) ||
1914 llvm::any_of(placed, [&](size_t g) {
1915 return arbiterOf(g) == arbiter &&
1916 flows[g].slave != flows[rest[f]].slave &&
1917 conflict(rest[f], g);
1918 });
1919 },
1920 reserved, stuck);
1921 if (!rested) {
1922 for (auto [a, b] : stuck)
1923 blocking.push_back({rest[a], rest[b]});
1924 for (size_t f : rest)
1925 for (size_t g : placed)
1926 if (flows[g].slave != flows[f].slave && conflict(f, g))
1927 blocking.push_back({g, f});
1928 return std::nullopt;
1929 }
1930 plan.slaveAmsels.insert(rested->slaveAmsels.begin(),
1931 rested->slaveAmsels.end());
1932 plan.amselMasters.insert(rested->amselMasters.begin(),
1933 rested->amselMasters.end());
1934 return plan;
1935 };
1936 SmallVector<std::pair<size_t, size_t>, 4> first;
1937 if (std::optional<ArbiterPlan> placed =
1938 around(*plan, priority, others, first))
1939 return placed;
1940
1941 llvm::EquivalenceClasses<Port> tied = tiedMasters(flows);
1942 SmallVector<size_t, 8> joint(priority), rest;
1943 for (size_t f : others) {
1944 bool tiedToPriority = llvm::any_of(priority, [&](size_t g) {
1945 return tied.isEquivalent(flows[g].masters.front(),
1946 flows[f].masters.front());
1947 });
1948 (tiedToPriority ? joint : rest).push_back(f);
1949 }
1950 stuck.clear();
1951 std::optional<ArbiterPlan> together;
1952 if (joint.size() > priority.size())
1953 together = planArbiters(
1954 targetModel, subset(joint),
1955 [&](size_t a, size_t b) { return conflict(joint[a], joint[b]); },
1956 [&](size_t f, int arbiter) { return excluded(joint[f], arbiter); },
1957 reservedAmsels[tileId], stuck);
1958 if (!together) {
1959 blocking.append(first.begin(), first.end());
1960 return std::nullopt;
1961 }
1962 return around(*together, joint, rest, blocking);
1963}
1964
1965void PacketFlowRouting::moveFlow(TileID tileId, FlowKey key, bool priority) {
1966 auto move = [&](const Connect &c) {
1967 hazardConnections.insert({tileId, c});
1968 if (priority)
1969 priorityConnections.insert({tileId, c});
1970 };
1971 auto flows = tileSlaveFlows.find(tileId);
1972 if (flows != tileSlaveFlows.end())
1973 if (auto f = flows->second.find(key); f != flows->second.end())
1974 for (Port m : f->second.masters)
1975 move({key.first, m});
1976 for (const Connect &hop : circuitHops[tileId])
1977 if (hop.src == key.first)
1978 move(hop);
1979}
1980
1981// Moves `key` with its whole unit (see planArbiters): a flow's arbiter is
1982// fixed by every flow reaching its master ports too.
1983void PacketFlowRouting::moveUnit(TileID tileId, FlowKey key) {
1984 moveFlow(tileId, key);
1985 auto flows = tileSlaveFlows.find(tileId);
1986 if (flows == tileSlaveFlows.end())
1987 return;
1988 auto self = flows->second.find(key);
1989 if (self == flows->second.end())
1990 return;
1991 llvm::EquivalenceClasses<Port> tied =
1992 tiedMasters(llvm::make_second_range(flows->second));
1993 for (const auto &[other, f] : flows->second)
1994 if (f.masters.size() > 1 &&
1995 tied.isEquivalent(f.masters.front(), self->second.masters.front()))
1996 moveFlow(tileId, other);
1997}
1998
1999void PacketFlowRouting::splitFlow(TileID tileId, FlowKey key,
2000 ArrayRef<FlowKey> partners) {
2001 auto flows = tileSlaveFlows.find(tileId);
2002 if (flows == tileSlaveFlows.end())
2003 return;
2004 auto self = flows->second.find(key);
2005 if (self == flows->second.end())
2006 return;
2007 auto onlySource = [&](FlowKey k) -> std::optional<PathEndPoint> {
2008 auto sources = slaveFlowSources.find({{tileId, k.first}, k.second});
2009 if (sources == slaveFlowSources.end() || sources->second.size() != 1)
2010 return std::nullopt;
2011 return sources->second.begin()->first;
2012 };
2013 std::optional<PathEndPoint> src = onlySource(key);
2014 if (!src)
2015 return;
2016 auto sharesMaster = [&](const auto &f, const std::set<Port> &ports) {
2017 return llvm::any_of(f.masters, [&](Port m) { return ports.count(m); });
2018 };
2019 std::set<Port> own(self->second.masters.begin(), self->second.masters.end());
2020 std::set<FlowKey> siblings;
2021 for (const auto &[other, f] : flows->second)
2022 if (other != key && other.first == key.first && sharesMaster(f, own) &&
2023 onlySource(other) == src)
2024 siblings.insert(other);
2025 // The masters tied to `partner`'s arbiter, not through `key`, nor through
2026 // its siblings if `skipSiblings`.
2027 auto tied = [&](FlowKey partner, bool skipSiblings) {
2028 llvm::EquivalenceClasses<Port> classes =
2029 tiedMasters(llvm::make_filter_range(
2030 llvm::make_second_range(flows->second), [&](const SlaveFlow &f) {
2031 FlowKey other{f.slave, f.id};
2032 return other != key && !(skipSiblings && siblings.count(other));
2033 }));
2034 auto unit = classes.members(flows->second.at(partner).masters.front());
2035 return std::set<Port>(unit.begin(), unit.end());
2036 };
2037 auto split = [&](FlowKey other,
2038 std::optional<PathEndPoint> apart = std::nullopt) {
2039 int a = key.second, b = other.second;
2040 if (!apart && a > b)
2041 std::swap(a, b);
2042 hazardSplits.insert({*src, tileId, a, b, apart});
2043 };
2044 for (FlowKey partner : partners) {
2045 if (partner == key || !flows->second.count(partner))
2046 continue;
2047 if (siblings.count(partner)) {
2048 split(partner);
2049 continue;
2050 }
2051 std::set<Port> partnerUnit = tied(partner, true);
2052 if (sharesMaster(self->second, partnerUnit))
2053 continue;
2054 // A sibling sharing a routing port with the partner's tree ties `key` to
2055 // its arbiter; leaving that port undoes the tie, so move off before split.
2056 bool unjoined = false;
2057 for (FlowKey other : siblings)
2058 for (Port m : flows->second.find(other)->second.masters)
2059 if (partnerUnit.count(m) && isDirectional(m.bundle)) {
2060 hazardConnections.insert({tileId, {other.first, m}});
2061 unjoined = true;
2062 }
2063 if (unjoined)
2064 continue;
2065 std::set<Port> unit = tied(partner, false);
2066 for (FlowKey other : siblings) {
2067 const SlaveFlow &f = flows->second.find(other)->second;
2068 if (!sharesMaster(f, unit))
2069 continue;
2070 // Where the sibling only ties `key` to the partner's arbiter by
2071 // destinations on this tile, those can reach it by a slave port of
2072 // their own, and `key` keeps sharing the rest of the tree.
2073 SmallVector<PathEndPoint, 2> apart;
2074 for (Port m : f.masters)
2075 if (partnerUnit.count(m))
2076 apart.push_back({tileId, m});
2077 if (PathEndPoint{tileId, key.first} == *src || apart.empty() ||
2078 !llvm::all_of(apart, [&](const PathEndPoint &p) {
2079 return packetStreamIndex.count({*src, p, other.second});
2080 })) {
2081 split(other);
2082 continue;
2083 }
2084 for (const PathEndPoint &p : apart)
2085 split(other, p);
2086 }
2087 }
2088}
2089
2090// Plans the arbiters of every switchbox on the routing. Where that fails, the
2091// RoutingFailure names the connections in the way.
2092llvm::Expected<PacketPlan> PacketFlowRouting::plan() {
2093 collectFlows();
2094 findCircuitHops();
2095 collectSlaveFlows();
2096 checkRules();
2097 planTiles();
2098 if (!planFailure)
2099 planFailure = breakHoldCycles();
2100 if (planFailure)
2101 return llvm::make_error<RoutingFailure>(std::move(*planFailure), faults());
2102 return PacketPlan(std::move(*this));
2103}
2104
2105RoutingFaults PacketFlowRouting::faults() const {
2106 RoutingFaults faults;
2107 faults.connections.assign(hazardConnections.begin(), hazardConnections.end());
2108 faults.splits.assign(hazardSplits.begin(), hazardSplits.end());
2109 faults.crowded.assign(crowdedTiles.begin(), crowdedTiles.end());
2110 faults.apart.assign(hazardApart.begin(), hazardApart.end());
2111 faults.together.assign(hazardTogether.begin(), hazardTogether.end());
2112 faults.untrunk.assign(hazardUntrunk.begin(), hazardUntrunk.end());
2113 faults.onlyPriorityMasters = !priorityConnections.empty() &&
2114 hazardSplits.empty() && crowdedTiles.empty() &&
2115 hazardApart.empty() && hazardUntrunk.empty() &&
2116 hazardConnections == priorityConnections;
2117 return faults;
2118}
2119
2120void PacketFlowRouting::checkRules() {
2121 // A slave port holds a few packet rules, and how many its flows need depends
2122 // on which ids leave by the same master ports.
2123 std::map<PhysPort, SmallVector<std::pair<int, int>>> existingCubes;
2124 for (auto swbox : device.getOps<SwitchboxOp>())
2125 for (auto rules : swbox.getConnections().getOps<PacketRulesOp>())
2126 for (auto rule : rules.getRules().getOps<PacketRuleOp>())
2127 existingCubes[{swbox.getTileOp().getTileID(), rules.sourcePort()}]
2128 .push_back({rule.maskInt(), rule.valueInt()});
2129 struct RuleGroup {
2130 SmallVector<std::pair<int, int>, 4> stated;
2131 SmallVector<int, 4> derived;
2132 };
2133 for (const auto &[slaveFlow, sources] : slaveFlowSources) {
2134 const auto &[first, firstMasters] = *sources.begin();
2135 auto other = llvm::find_if(
2136 sources, [&, &firstMasters = firstMasters](const auto &source) {
2137 return source.second != firstMasters;
2138 });
2139 if (other == sources.end())
2140 continue;
2141 const auto &[slavePort, id] = slaveFlow;
2142 TileID tileId = slavePort.first;
2143 moveFlow(tileId, {slavePort.second, id});
2144 if (planFailure)
2145 continue;
2146 const PathEndPoint &second = other->first;
2147 planFailure = llvm::formatv(
2148 "at tile ({0}, {1}), packets with id {2} from {3} and {4} enter on {5} "
2149 "and leave by different ports; a switchbox routes on the id alone, so "
2150 "each source's packets would also go where the other's do.",
2151 tileId.col, tileId.row, id, describeTilePort(first.coords, first.port),
2152 describeTilePort(second.coords, second.port),
2153 describePort(slavePort.second));
2154 }
2155 for (const auto &[tileId, byFlow] : tileSlaveFlows) {
2156 auto newRules =
2157 [&, tileId = tileId, &byFlow = byFlow](
2158 Port slave, std::optional<std::pair<PathEndPoint, Port>> without,
2159 bool priorityOnly,
2160 SmallVector<SmallVector<Port, 4>> *groupMasters = nullptr) {
2161 std::map<std::pair<bool, SmallVector<Port, 4>>, RuleGroup> groups;
2162 for (const auto &[key, f] : byFlow) {
2163 if (f.slave != slave || (priorityOnly && !f.isPriority))
2164 continue;
2165 SmallVector<Port, 4> masters = f.masters;
2166 auto sources = slaveFlowSources.find({{tileId, slave}, f.id});
2167 if (without && sources != slaveFlowSources.end()) {
2168 std::set<Port> kept;
2169 for (const auto &[src, ports] : sources->second)
2170 for (Port m : ports)
2171 if (!(src == without->first) || m != without->second)
2172 kept.insert(m);
2173 masters.assign(kept.begin(), kept.end());
2174 }
2175 if (masters.empty())
2176 continue;
2177 RuleGroup &group = groups[{f.isPriority, masters}];
2178 auto cubes = statedCubes({{tileId, f.slave}, f.id}, idMask);
2179 if (cubes.empty())
2180 group.derived.push_back(f.id);
2181 for (auto cube : cubes)
2182 if (!llvm::is_contained(group.stated, cube))
2183 group.stated.push_back(cube);
2184 }
2185 SmallVector<GroupClaims> claims;
2186 for (const auto &[masters, group] : groups) {
2187 claims.push_back({group.stated, group.derived, masters.first});
2188 if (groupMasters)
2189 groupMasters->push_back(masters.second);
2190 }
2191 return slavePortRules(claims, existingCubes[{tileId, slave}], idBits,
2192 targetModel.getNumSlaveSlots());
2193 };
2194 auto rulesNeeded =
2195 [&, tileId = tileId](
2196 Port slave,
2197 std::optional<std::pair<PathEndPoint, Port>> without = {}) {
2198 return existingCubes[{tileId, slave}].size() +
2199 newRules(slave, without, false).size();
2200 };
2201 // Packets for a destination on the tile that reach it by a slave port of
2202 // their own take their rules with them. The source's tree splits apart the
2203 // destination that frees the most rules on `slave`, if one frees any.
2204 auto splitRules = [&, tileId = tileId, &byFlow = byFlow](Port slave) {
2205 std::map<PathEndPoint, std::map<PathEndPoint, std::set<int>>> dstIds;
2206 for (const auto &[key, f] : byFlow) {
2207 if (f.slave != slave)
2208 continue;
2209 auto streams = slaveFlowStreams.find({{tileId, slave}, f.id});
2210 if (streams == slaveFlowStreams.end())
2211 continue;
2212 for (size_t i : streams->second) {
2213 const RoutedStream &s = conflicts.getStreams()[i];
2214 dstIds[{s.src.tile, s.src.port}][{s.dst.tile, s.dst.port}].insert(
2215 f.id);
2216 }
2217 }
2218 std::optional<std::pair<PathEndPoint, PathEndPoint>> best;
2219 size_t fewest = rulesNeeded(slave);
2220 for (const auto &[src, dsts] : dstIds)
2221 for (const auto &[dst, ids] : dsts)
2222 if (dst.coords == tileId && dsts.size() > 1)
2223 if (size_t n = rulesNeeded(slave, {{src, dst.port}}); n < fewest) {
2224 fewest = n;
2225 best = {src, dst};
2226 }
2227 if (!best)
2228 return false;
2229 const auto &[src, apart] = *best;
2230 const std::set<int> &apartIds = dstIds[src][apart];
2231 for (const auto &[dst, ids] : dstIds[src]) {
2232 auto carries = [&, &src = src, &dst = dst](int id) {
2233 return packetStreamIndex.count({src, dst, id}) > 0;
2234 };
2235 auto b = llvm::find_if_not(apartIds, carries);
2236 if (!(dst == apart) && b != apartIds.end())
2237 hazardSplits.insert({src, tileId, *ids.begin(), *b, apart});
2238 }
2239 return true;
2240 };
2241 // Flows on one slave port that leave by different master ports must not
2242 // claim a common id, and a mask written on an aie.packet_flow claims every
2243 // id it matches.
2244 auto claim = [&, tileId = tileId](const SlaveFlow &f) {
2245 auto cubes = statedCubes({{tileId, f.slave}, f.id}, idMask);
2246 if (cubes.empty())
2247 cubes.push_back({idMask, f.id});
2248 return cubes;
2249 };
2250 for (auto a = byFlow.begin(); a != byFlow.end(); ++a)
2251 for (auto b = std::next(a); b != byFlow.end(); ++b) {
2252 const SlaveFlow &fa = a->second, &fb = b->second;
2253 if (fa.slave != fb.slave || fa.masters == fb.masters)
2254 continue;
2255 std::optional<std::pair<std::pair<int, int>, std::pair<int, int>>>
2256 overlap;
2257 for (auto own : claim(fa))
2258 for (auto other : claim(fb))
2259 if (!overlap && cubesIntersect(own, other))
2260 overlap = {own, other};
2261 if (!overlap)
2262 continue;
2263 auto [own, other] = *overlap;
2264 moveFlow(tileId, a->first);
2265 moveFlow(tileId, b->first);
2266 if (planFailure)
2267 continue;
2268 int witness = (own.second & own.first) |
2269 (other.second & other.first & ~own.first);
2270 planFailure = llvm::formatv(
2271 "at tile ({0}, {1}), packet flows through {2} claim rule (mask "
2272 "0x{3:X-}, id 0x{4:X-}) and rule (mask 0x{5:X-}, id 0x{6:X-}), "
2273 "which both match id 0x{7:X-}; widen one mask to carry both, or "
2274 "route them apart.",
2275 tileId.col, tileId.row, describePort(fa.slave), own.first,
2276 own.second, other.first, other.second, witness);
2277 }
2278 std::set<Port> slaves;
2279 for (const auto &[key, f] : byFlow)
2280 slaves.insert(f.slave);
2281 std::set<Port> priorityMasters;
2282 std::set<SmallVector<Port, 4>> prioritySets;
2283 for (const auto &[key, f] : byFlow)
2284 if (f.isPriority && !pinned.rules.empty()) {
2285 priorityMasters.insert(f.masters.begin(), f.masters.end());
2286 prioritySets.insert(f.masters);
2287 }
2288 for (const auto &[key, f] : byFlow) {
2289 const Port *shared = llvm::find_if(
2290 f.masters, [&](Port m) { return priorityMasters.count(m); });
2291 if (f.isPriority || shared == f.masters.end() ||
2292 prioritySets.count(f.masters))
2293 continue;
2294 moveFlow(tileId, key, /*priority=*/true);
2295 if (!planFailure)
2296 planFailure = llvm::formatv(
2297 "at tile ({0}, {1}), packets with id {2} entering on {3} leave by "
2298 "{4}, a master port of the prioritized flows, but not by one of "
2299 "their fixed master sets.",
2300 tileId.col, tileId.row, f.id, describePort(f.slave),
2301 describePort(*shared));
2302 }
2303 for (Port slave : pinned.rules.empty() ? std::set<Port>{} : slaves) {
2304 SmallVector<SmallVector<Port, 4>> ruleMasters;
2305 SmallVector<PortRule> priority = newRules(slave, {}, true, &ruleMasters);
2306 for (const auto &[key, f] : byFlow) {
2307 if (f.slave != slave || f.isPriority)
2308 continue;
2309 for (auto own : claim(f)) {
2310 const auto *rule =
2311 llvm::find_if(priority, [&, &f = f](const PortRule &r) {
2312 return cubesIntersect(own, {r.mask, r.value}) &&
2313 ruleMasters[r.group] != f.masters;
2314 });
2315 if (rule == priority.end())
2316 continue;
2317 moveFlow(tileId, key);
2318 if (!planFailure)
2319 planFailure = llvm::formatv(
2320 "at tile ({0}, {1}), the packet rule (mask 0x{2:X-}, id "
2321 "0x{3:X-}) of the prioritized flows on "
2322 "{4} also matches packet id 0x{5:X-}, and priority routing "
2323 "keeps their rules; use an id the rule does not match, "
2324 "or route the flow apart.",
2325 tileId.col, tileId.row, rule->mask, rule->value,
2326 describePort(slave), f.id);
2327 break;
2328 }
2329 }
2330 }
2331 for (Port slave : slaves) {
2332 size_t needed = rulesNeeded(slave);
2333 if (needed <= targetModel.getNumSlaveSlots())
2334 continue;
2335 for (const auto &[key, f] : byFlow)
2336 if (f.slave == slave)
2337 moveFlow(tileId, key);
2338 if (!splitRules(slave))
2339 crowdedTiles.insert(tileId);
2340 if (planFailure)
2341 continue;
2342 planFailure = llvm::formatv(
2343 "at tile ({0}, {1}), the packet flows entering on {2} need {3} "
2344 "packet rules, and a slave port holds {4}.",
2345 tileId.col, tileId.row, describePort(slave), needed,
2346 targetModel.getNumSlaveSlots());
2347 }
2348 }
2349}
2350
2351void PacketFlowRouting::planTiles() {
2352 for (const auto &[tileId, flows] : tileFlows) {
2353 SmallVector<std::pair<size_t, size_t>, 4> blocking;
2354 if (std::optional<ArbiterPlan> plan = planTile(tileId, blocking)) {
2355 plans[tileId] = std::move(*plan);
2356 continue;
2357 }
2358 LLVM_DEBUG({
2359 llvm::dbgs() << "No arbiter plan at tile (" << tileId.col << ", "
2360 << tileId.row << "):\n";
2361 for (const SlaveFlow &f : flows) {
2362 llvm::dbgs() << " " << describePort(f.slave) << " id " << f.id
2363 << " ->";
2364 for (Port m : f.masters)
2365 llvm::dbgs() << ' ' << describePort(m);
2366 llvm::dbgs() << '\n';
2367 }
2368 for (auto [a, b] : blocking)
2369 llvm::dbgs() << " blocking " << a << ' ' << b << '\n';
2370 });
2371 std::string reason;
2372 llvm::raw_string_ostream os(reason);
2373 if (blocking.empty()) {
2374 // Ids a source sends out by master sets that overlap tie those sets to
2375 // one arbiter, so its tree branches them apart to free msels.
2376 for (const SlaveFlow &f : flows)
2377 for (const SlaveFlow &g : flows)
2378 if (f.slave == g.slave && f.id < g.id && f.masters != g.masters &&
2379 llvm::any_of(
2380 f.masters,
2381 [&](Port m) { return llvm::is_contained(g.masters, m); })) {
2382 FlowKey keys[] = {{f.slave, f.id}, {g.slave, g.id}};
2383 splitFlow(tileId, keys[0], keys);
2384 }
2385 for (const SlaveFlow &f : flows)
2386 moveFlow(tileId, {f.slave, f.id});
2387 crowdedTiles.insert(tileId);
2388 if (planFailure)
2389 continue;
2390 os << "at tile (" << tileId.col << ", " << tileId.row
2391 << "), the packet flows need more arbiter msels than the switchbox "
2392 "has free.";
2393 planFailure = std::move(reason);
2394 continue;
2395 }
2396 for (auto [a, b] : blocking) {
2397 FlowKey keys[] = {{flows[a].slave, flows[a].id},
2398 {flows[b].slave, flows[b].id}};
2399 for (FlowKey key : keys) {
2400 moveUnit(tileId, key);
2401 splitFlow(tileId, key, keys);
2402 }
2403 }
2404 if (planFailure)
2405 continue;
2406 std::optional<std::pair<size_t, size_t>> pair = conflictingStreams(
2407 tileId, flows[blocking.front().first], flows[blocking.front().second]);
2408 assert(pair && apart.empty() && offArbiter.empty() &&
2409 "before the hold-cycle search, only stream conflicts block a plan");
2410 auto [s, t] = *pair;
2411 os << describeStream(conflicts.getStreams()[s]) << " and "
2412 << describeStream(conflicts.getStreams()[t])
2413 << " can deadlock if they share an arbiter, and no routing found keeps "
2414 "them apart (last tried: tile ("
2415 << tileId.col << ", " << tileId.row << ")). " << conflicts.explain(s, t);
2416 planFailure = std::move(reason);
2417 }
2418}
2419
2420std::optional<std::string> PacketFlowRouting::breakHoldCycles() {
2421 // A packet holds every arbiter it has taken until its tail passes, so waits
2422 // chain from switchbox to switchbox, and planning each alone can close a
2423 // cycle of them. Breaking any one shared arbiter of such a cycle breaks it,
2424 // so the search tries each in turn, up to a budget.
2425 auto arbitrate = [&]() {
2426 for (size_t s = 0; s < conflicts.getRequestedStreams().size(); s++) {
2427 if (!conflicts.getStreams()[s].packetID)
2428 continue;
2429 for (StreamHop &hop : routes[s]) {
2430 hop.arbiter.reset();
2431 auto plan = plans.find(hop.tile);
2432 if (plan == plans.end())
2433 continue;
2434 auto amsel = plan->second.slaveAmsels.find(
2435 {hop.input, *conflicts.getStreams()[s].packetID});
2436 if (amsel != plan->second.slaveAmsels.end())
2437 hop.arbiter = amsel->second % numArbiters;
2438 }
2439 }
2440 };
2441 ArrayRef<RoutedStream> streams = conflicts.getStreams();
2442 size_t numRequested = conflicts.getRequestedStreams().size();
2443 // Every cycle the search meets: the routing moves the flows of each, as the
2444 // first may run only through flows it cannot move.
2445 SmallVector<HoldCycle, 2> cycles;
2446 int replans = 0;
2447 bool forcedWaits = false, definite = false;
2448 auto search = [&](auto &self) -> bool {
2449 arbitrate();
2450 std::optional<HoldCycle> cycle =
2451 conflicts.holdCycle(routes, forcedWaits, definite);
2452 // Waits `definite` drops still count where no receiver is shared, so a
2453 // replan must not close a cycle the first search broke.
2454 if (!cycle && definite)
2455 cycle = conflicts.holdCycle(routes);
2456 if (!cycle)
2457 return true;
2458 cycles.push_back(*cycle);
2459 LLVM_DEBUG(llvm::dbgs()
2460 << "Hold cycle: " << conflicts.explain(*cycle) << '\n');
2461 for (const HoldCycle::Step &step : cycle->steps) {
2462 if (step.wait != HoldCycle::Wait::Arbiter || step.forced)
2463 continue;
2464 FlowKey sharer{step.sharerInput, *streams[step.sharer].packetID};
2465 FlowKey holder{step.holderInput, *streams[step.holding].packetID};
2466 bool sharerNew = step.sharer < numRequested;
2467 bool holderNew = step.holding < numRequested;
2468 std::optional<std::tuple<TileID, FlowKey, FlowKey>> pair;
2469 std::optional<std::tuple<TileID, FlowKey, int>> off;
2470 if (sharerNew && holderNew)
2471 pair = {step.tile, std::min(sharer, holder), std::max(sharer, holder)};
2472 else if (sharerNew || holderNew)
2473 off = {step.tile, sharerNew ? sharer : holder, step.arbiter};
2474 else
2475 continue;
2476 if (replans == maxHoldCycleReplans)
2477 return false;
2478 if ((pair && !apart.insert(*pair).second) ||
2479 (off && !offArbiter.insert(*off).second))
2480 continue;
2481 replans++;
2482 ArbiterPlan saved = plans.at(step.tile);
2483 SmallVector<std::pair<size_t, size_t>, 4> blocking;
2484 if (std::optional<ArbiterPlan> plan = planTile(step.tile, blocking)) {
2485 plans[step.tile] = std::move(*plan);
2486 if (self(self))
2487 return true;
2488 plans[step.tile] = std::move(saved);
2489 }
2490 if (pair)
2491 apart.erase(*pair);
2492 if (off)
2493 offArbiter.erase(*off);
2494 }
2495 return false;
2496 };
2497 // The routing moves the flows of each cycle the search met, but for those
2498 // waiting at a receiver they share.
2499 auto move = [&] {
2500 arbitrate();
2501 for (const HoldCycle &cycle : cycles)
2502 for (const HoldCycle::Step &step : cycle.steps) {
2503 if (step.wait == HoldCycle::Wait::Arbiter && step.forced &&
2504 step.sharer < numRequested && step.holding < numRequested &&
2505 streams[step.sharer].packetID && streams[step.holding].packetID) {
2506 PathEndPoint a{streams[step.sharer].src.tile,
2507 streams[step.sharer].src.port},
2508 b{streams[step.holding].src.tile, streams[step.holding].src.port};
2509 if (!(a == b))
2510 hazardTogether.insert(std::minmax(a, b));
2511 }
2512 if (step.wait != HoldCycle::Wait::Drain && !step.forced) {
2513 SmallVector<FlowKey, 3> keys;
2514 for (auto [s, input] : {std::pair{step.waiting, step.sharerInput},
2515 std::pair{step.sharer, step.sharerInput},
2516 std::pair{step.holding, step.holderInput}})
2517 if (std::optional<int> id = streams[s].packetID;
2518 s < numRequested && id)
2519 keys.push_back({input, *id});
2520 for (FlowKey key : keys) {
2521 moveUnit(step.tile, key);
2522 splitFlow(step.tile, key, keys);
2523 }
2524 // On a link, `waiting` queues behind `holding` itself.
2525 size_t behind =
2526 step.wait == HoldCycle::Wait::Link ? step.waiting : step.sharer;
2527 if (behind >= numRequested || step.holding >= numRequested ||
2528 !streams[behind].packetID || !streams[step.holding].packetID)
2529 continue;
2530 PathEndPoint a{streams[behind].src.tile, streams[behind].src.port},
2531 b{streams[step.holding].src.tile, streams[step.holding].src.port};
2532 // holdCycle relates one source's trees only to themselves.
2533 if (!(a == b))
2534 hazardApart.insert(std::minmax(a, b));
2535 else if (step.wait == HoldCycle::Wait::Arbiter)
2536 hazardUntrunk.insert(a);
2537 }
2538 }
2539 };
2540 if (!search(search)) {
2541 move();
2542 return "packet flows can deadlock holding arbiters across "
2543 "switchboxes, and no arbiter assignment found avoids it. " +
2544 conflicts.explain(cycles.front());
2545 }
2546 // Trees into a receiver they share wait on each other at its master port
2547 // whatever the plan, so a cycle through such waits can only be broken
2548 // elsewhere along it. Where none of it can, the routing fails, unless some
2549 // plan has such cycles only by assumption.
2550 cycles.clear();
2551 replans = 0;
2552 forcedWaits = true;
2553 if (!search(search)) {
2554 LLVM_DEBUG(llvm::dbgs() << "Hold cycle at a shared receiver: "
2555 << conflicts.explain(cycles.front()) << '\n');
2556 cycles.clear();
2557 replans = 0;
2558 definite = true;
2559 if (!search(search)) {
2560 move();
2561 sharedReceiverCycle = cycles.front();
2562 }
2563 }
2564 return std::nullopt;
2565}
2566
2567LogicalResult PacketPlan::emit(DeviceOp device, OpBuilder &builder,
2568 DynamicTileAnalysis &analyzer) const {
2569 const AIETargetModel &targetModel = device.getTargetModel();
2570 const int numArbiters = targetModel.getNumArbiters();
2571 const int numMselsPerArbiter = targetModel.getNumMselsPerArbiter();
2572 const uint32_t maxPacketId = targetModel.getMaxPacketId();
2573 const int idBits = targetModel.getPacketIdBits();
2574 const int idMask = targetModel.getPacketIdMask();
2575 AIEDialect::PriorityRouteAttrHelper priority(builder.getContext());
2576 UnitAttr unit = builder.getUnitAttr();
2577
2578 // A master port can only be associated with one arbiter, and each arbiter
2579 // has numMselsPerArbiter msels, so a tile has numArbiters x
2580 // numMselsPerArbiter "logical" arbiters.
2581 //
2582 // A map from Tile and master selectValue to the ports targetted by that
2583 // master select.
2584 std::map<std::pair<TileID, int>, SmallVector<Port, 4>> masterAMSels;
2585 DenseMap<std::pair<PhysPort, int>, int> slaveAMSels;
2586 for (const auto &[tileId, plan] : plans) {
2587 for (const auto &[amsel, masters] : plan.amselMasters)
2588 masterAMSels[{tileId, amsel}].append(masters.begin(), masters.end());
2589 for (const auto &[flow, amsel] : plan.slaveAmsels)
2590 slaveAMSels[{{tileId, flow.first}, flow.second}] = amsel;
2591 }
2592
2593 // Compute the master set IDs
2594 // A map from a switchbox output port to its associated amsel values
2595 std::map<PhysPort, SmallVector<int, 4>> mastersets;
2596 for (const auto &[tileAmsel, ports] : masterAMSels)
2597 for (Port port : ports)
2598 mastersets[{tileAmsel.first, port}].push_back(tileAmsel.second);
2599
2600 LLVM_DEBUG({
2601 llvm::dbgs() << "CHECK mastersets\n";
2602 for (const auto &[master, values] : mastersets) {
2603 llvm::dbgs() << "master " << master.first << " "
2604 << stringifyWireBundle(master.second.bundle) << " : "
2605 << master.second.channel << '\n';
2606 for (int value : values)
2607 llvm::dbgs() << "amsel: " << value << '\n';
2608 }
2609 });
2610
2611 // Prioritized flows group apart from the others; the ids of a group share its
2612 // packet rules.
2613 SmallVector<SmallVector<std::pair<PhysPort, int>, 4>, 4> slaveGroups;
2614 SmallVector<std::pair<PhysPort, int>, 4> workList(slavePorts);
2615 while (!workList.empty()) {
2616 std::pair<PhysPort, int> slave = workList.pop_back_val();
2617 const SmallVector<PhysPort, 4> &dests = packetFlows.at(slave);
2618 auto *group = llvm::find_if(slaveGroups, [&](const auto &candidate) {
2619 const SmallVector<PhysPort, 4> &groupDests =
2620 packetFlows.at(candidate.front());
2621 return candidate.front().first.second == slave.first.second &&
2622 prioritizedFlows.contains(candidate.front()) ==
2623 prioritizedFlows.contains(slave) &&
2624 groupDests.size() == dests.size() &&
2625 llvm::all_of(dests, [&](const PhysPort &dest) {
2626 return llvm::is_contained(groupDests, dest);
2627 });
2628 });
2629 if (group != slaveGroups.end())
2630 group->push_back(slave);
2631 else
2632 slaveGroups.push_back({slave});
2633 }
2634
2635 // What each group claims on its slave port, as cubes, split into the rules
2636 // its flows state and the ids left for the cover to describe.
2637 SmallVector<SmallVector<std::pair<int, int>, 4>, 4> statedRules(
2638 slaveGroups.size());
2639 SmallVector<SmallVector<int, 4>, 4> derivedIds(slaveGroups.size());
2640 for (size_t gi = 0; gi < slaveGroups.size(); ++gi) {
2641 for (auto member : slaveGroups[gi]) {
2642 auto cubes = statedCubes(member, idMask);
2643 if (cubes.empty()) {
2644 derivedIds[gi].push_back(member.second);
2645 continue;
2646 }
2647 for (auto cube : cubes)
2648 if (!llvm::is_contained(statedRules[gi], cube))
2649 statedRules[gi].push_back(cube);
2650 }
2651 }
2652
2653 // Everything a group claims, for the other groups on its port to avoid.
2654 [[maybe_unused]] auto claimsOf = [&](size_t gi) {
2655 SmallVector<std::pair<int, int>, 8> claims(statedRules[gi].begin(),
2656 statedRules[gi].end());
2657 for (int id : derivedIds[gi])
2658 claims.push_back({idMask, id});
2659 return claims;
2660 };
2661
2662 // Realize the routes in MLIR
2663
2664 // Update tiles map if any new tile op declaration is needed for constructing
2665 // the flow.
2666 std::map<TileID, Operation *> tiles;
2667 for (auto tileOp : device.getOps<TileOp>())
2668 tiles[tileOp.getTileID()] = tileOp;
2669 for (const PhysPort &master : llvm::make_first_range(mastersets))
2670 tiles.try_emplace(master.first, analyzer.getTile(builder, master.first));
2671
2672 for (Operation *tileOp : llvm::make_second_range(tiles)) {
2673 TileOp tile = cast<TileOp>(tileOp);
2674 TileID tileId = tile.getTileID();
2675 Location tileLoc = tile.getLoc();
2676
2677 // Create a switchbox for the routes and insert inside it.
2678 builder.setInsertionPointAfter(tileOp);
2679 SwitchboxOp swbox =
2680 analyzer.getSwitchbox(builder, tile.colIndex(), tile.rowIndex());
2681 SwitchboxOp::ensureTerminator(swbox.getConnections(), builder, tileLoc);
2682 Block &b = swbox.getConnections().front();
2683 builder.setInsertionPoint(b.getTerminator());
2684
2685 if (auto hops = circuitHops.find(tileId); hops != circuitHops.end())
2686 for (const Connect &hop : hops->second) {
2687 SmallVector<std::pair<PhysPort, int>, 4> passing;
2688 for (const auto &flow : llvm::make_first_range(slaveFlowLocs))
2689 if (flow.first == PhysPort{tileId, hop.src})
2690 passing.push_back(flow);
2691 ConnectOp::create(builder, locOf(passing, tileLoc), hop.src.bundle,
2692 hop.src.channel, hop.dst.bundle, hop.dst.channel);
2693 }
2694
2695 // The master sets of this tile, in port order, and the amsels they take.
2696 auto tileMastersets =
2697 llvm::make_filter_range(mastersets, [&](const auto &entry) {
2698 return entry.first.first == tileId;
2699 });
2700 llvm::SmallBitVector amselNeeded(numMselsPerArbiter * numArbiters);
2701 for (const auto &[master, amsels] : tileMastersets)
2702 for (int amsel : amsels)
2703 amselNeeded.set(amsel);
2704 std::map<int, AMSelOp> amselOps;
2705 for (int msel = 0; msel < numMselsPerArbiter; msel++)
2706 for (int arbiter = 0; arbiter < numArbiters; arbiter++)
2707 if (int amsel = arbiter + msel * numArbiters; amselNeeded.test(amsel))
2708 amselOps[amsel] = AMSelOp::create(builder, tileLoc, arbiter, msel);
2709 for (const auto &[master, msels] : tileMastersets) {
2710 SmallVector<Value, 4> amsels;
2711 for (int msel : msels)
2712 amsels.push_back(amselOps.at(msel));
2713 SmallVector<std::pair<PhysPort, int>, 4> feeding;
2714 for (const auto &[flow, dests] : packetFlows)
2715 if (llvm::is_contained(dests, master))
2716 feeding.push_back(flow);
2717 auto msOp = MasterSetOp::create(
2718 builder, locOf(feeding, tileLoc), builder.getIndexType(),
2719 master.second.bundle, master.second.channel, amsels,
2720 keepPktHeaderAttr.lookup(master));
2721 if (priorityMasterPorts.contains(master))
2722 priority.setAttr(msOp, unit);
2723 }
2724
2725 // Generate the packet rules, adding to any the switchbox already has.
2726 DenseMap<Port, PacketRulesOp> slaveRules;
2727 DenseMap<Port, SmallVector<PacketRuleOp>> existingRules;
2728 struct PortPlan {
2729 SmallVector<size_t, 4> groups;
2730 SmallVector<PortRule> rules;
2731 size_t emitted = 0;
2732 };
2733 std::map<Port, PortPlan> portPlans;
2734 for (auto rulesOp : b.getOps<PacketRulesOp>()) {
2735 slaveRules[rulesOp.sourcePort()] = rulesOp;
2736 llvm::append_range(existingRules[rulesOp.sourcePort()],
2737 rulesOp.getRules().getOps<PacketRuleOp>());
2738 }
2739 for (size_t gi = 0; gi < slaveGroups.size(); ++gi) {
2740 const auto &group = slaveGroups[gi];
2741 builder.setInsertionPoint(b.getTerminator());
2742
2743 auto port = group.front().first;
2744 if (tileId != port.first)
2745 continue;
2746
2747 Port slave = port.second;
2748
2749 SmallVector<int, 4> matchIds =
2750 llvm::to_vector<4>(llvm::make_second_range(group));
2751 for (int id : matchIds)
2752 if (id > static_cast<int>(maxPacketId)) {
2753 SmallVector<std::pair<PhysPort, int>> offending;
2754 for (const auto &flow : group)
2755 if (flow.second == id)
2756 offending.push_back(flow);
2757 return mlir::emitError(locOf(offending, tileLoc))
2758 << "packet id " << id << " exceeds the maximum of "
2759 << maxPacketId;
2760 }
2761
2762 // Rules the switchbox already has, e.g. hand-authored, match first.
2763 for (PacketRuleOp rule : existingRules.lookup(slave))
2764 for (int id : matchIds)
2765 if ((id & rule.maskInt()) == rule.valueInt()) {
2766 rule->emitOpError("can lead to false packet id match for id ")
2767 << id << ", which is not supposed to pass through this port.";
2768 rule->emitRemark("Please consider changing all uses of packet id ")
2769 << id << " to avoid deadlock.";
2770 return failure();
2771 }
2772
2773 // Groups on one slave port carry different destination sets, so
2774 // checkRules let no two of them claim the same id.
2775 assert(llvm::all_of(
2776 llvm::seq<size_t>(0, slaveGroups.size()),
2777 [&](size_t oi) {
2778 return oi == gi || slaveGroups[oi].front().first != port ||
2779 llvm::none_of(claimsOf(gi), [&](auto own) {
2780 return llvm::any_of(claimsOf(oi), [&](auto other) {
2781 return cubesIntersect(own, other);
2782 });
2783 });
2784 }) &&
2785 "groups on one slave port claim the same id");
2786
2787 // The rules of the slave port, planned at its first group, go out in
2788 // order: each group adds those up to its last.
2789 auto [planIt, fresh] = portPlans.try_emplace(slave);
2790 PortPlan &plan = planIt->second;
2791 if (fresh) {
2792 SmallVector<GroupClaims> claims;
2793 for (size_t oi = 0; oi < slaveGroups.size(); ++oi) {
2794 if (slaveGroups[oi].front().first != port)
2795 continue;
2796 plan.groups.push_back(oi);
2797 claims.push_back(
2798 {statedRules[oi], derivedIds[oi],
2799 prioritizedFlows.contains(slaveGroups[oi].front())});
2800 }
2801 SmallVector<std::pair<int, int>> existing;
2802 for (PacketRuleOp rule : existingRules.lookup(slave))
2803 existing.push_back({rule.maskInt(), rule.valueInt()});
2804 plan.rules = slavePortRules(claims, existing, idBits,
2805 targetModel.getNumSlaveSlots());
2806 LLVM_DEBUG({
2807 llvm::dbgs() << "packet rules " << describePort(slave) << ":";
2808 for (const PortRule &r : plan.rules)
2809 llvm::dbgs() << " rule(" << r.mask << ", " << r.value
2810 << ") -> group " << plan.groups[r.group];
2811 llvm::dbgs() << '\n';
2812 });
2813 }
2814
2815 assert(
2816 llvm::all_of(
2817 llvm::seq(0, idMask + 1),
2818 [&](int id) {
2819 bool own = llvm::is_contained(derivedIds[gi], id) ||
2820 llvm::any_of(statedRules[gi], [&](auto c) {
2821 return (id & c.first) == (c.second & c.first);
2822 });
2823 const auto *first =
2824 llvm::find_if(plan.rules, [&](const PortRule &r) {
2825 return (id & r.mask) == r.value;
2826 });
2827 return !own ||
2828 (first != plan.rules.end() &&
2829 slaveAMSels.at(
2830 slaveGroups[plan.groups[first->group]].front()) ==
2831 slaveAMSels.at(slaveGroups[gi].front()));
2832 }) &&
2833 "packet rules send a claimed id elsewhere");
2834
2835 size_t last = plan.emitted;
2836 for (size_t r = plan.emitted; r < plan.rules.size(); ++r)
2837 if (plan.groups[plan.rules[r].group] == gi)
2838 last = r + 1;
2839
2840 PacketRulesOp packetrules = slaveRules.lookup(slave);
2841 if (!packetrules) {
2842 packetrules = PacketRulesOp::create(builder, locOf(group, tileLoc),
2843 slave.bundle, slave.channel);
2844 PacketRulesOp::ensureTerminator(packetrules.getRules(), builder,
2845 tileLoc);
2846 slaveRules[slave] = packetrules;
2847 } else {
2848 // After the amsels its new rules use, and located at their flows too.
2849 packetrules->moveBefore(b.getTerminator());
2850 if (Location more = locOf(group, tileLoc); more != tileLoc)
2851 packetrules->setLoc(FusedLoc::get(builder.getContext(),
2852 {packetrules->getLoc(), more}));
2853 }
2854
2855 Block &rules = packetrules.getRules().front();
2856
2857 assert(llvm::range_size(rules.getOps<PacketRuleOp>()) +
2858 (last - plan.emitted) <=
2859 targetModel.getNumSlaveSlots() &&
2860 "checkRules lets a slave port take more rules than it holds");
2861
2862 builder.setInsertionPoint(rules.getTerminator());
2863 for (; plan.emitted < last; ++plan.emitted) {
2864 const PortRule &r = plan.rules[plan.emitted];
2865 const auto &ruleGroup = slaveGroups[plan.groups[r.group]];
2866 auto rule = PacketRuleOp::create(
2867 builder, locOf(ruleGroup, tileLoc), r.mask, r.value,
2868 amselOps.at(slaveAMSels.at(ruleGroup.front())));
2869 if (llvm::all_of(ruleGroup, [&](const auto &member) {
2870 return markedFlows.contains(member);
2871 }))
2872 priority.setAttr(rule, unit);
2873 }
2874 }
2875
2876 for (auto rulesOp : b.getOps<PacketRulesOp>()) {
2877 auto rules = rulesOp.getRules().front().getOps<PacketRuleOp>();
2878 if (rules.empty() || !llvm::all_of(rules, [&](PacketRuleOp rule) {
2879 return priority.isAttrPresent(rule);
2880 }))
2881 continue;
2882 priority.setAttr(rulesOp, unit);
2883 for (auto rule : rules)
2884 priority.removeAttr(rule);
2885 }
2886 }
2887 return success();
2888}
2889
2890LogicalResult AIEPathfinderPass::runOnPacketFlow(
2891 DeviceOp device, OpBuilder &builder, DynamicTileAnalysis &analyzer,
2892 const StreamConflicts &conflicts, const PacketPlan &plan, bool warn) {
2893 if (warn && plan.sharedReceiverCycle)
2894 emitWarning(device.getLoc(), sharedReceiverCycleReason)
2895 << conflicts.explain(*plan.sharedReceiverCycle);
2896 if (failed(plan.emit(device, builder, analyzer)))
2897 return failure();
2898 lowerShimDMAPorts(device, builder, analyzer);
2899 for (PacketFlowOp flow :
2900 llvm::make_early_inc_range(device.getOps<PacketFlowOp>()))
2901 flow.erase();
2902 return success();
2903}
2904
2905// A copy of `d` in a module like its own, as the analyses look up through it.
2906static DeviceOp cloneInScratch(DeviceOp d, OwningOpRef<ModuleOp> &scratch) {
2907 scratch = ModuleOp::create(d.getLoc());
2908 if (Operation *parent = d->getParentOp())
2909 (*scratch)->setAttrs(parent->getAttrDictionary());
2910 DeviceOp copy = d.clone();
2911 scratch->push_back(copy);
2912 return copy;
2913}
2914
2915// The router names a shim DMA by its own port, and the end of
2916// runOnPacketFlow moves it behind the shim mux onto a South channel. Rules and
2917// master sets a previous run left there are moved back first, so new flows on
2918// the same DMA channel share them.
2919static void unmuxShimDMAPacketPorts(DeviceOp device) {
2920 for (auto shimMux : device.getOps<ShimMuxOp>()) {
2921 auto hasConnect = [&](Port src, Port dst) {
2922 return llvm::any_of(shimMux.getConnections().getOps<ConnectOp>(),
2923 [&](ConnectOp c) {
2924 return c.sourcePort() == src && c.destPort() == dst;
2925 });
2926 };
2927 for (auto switchbox : device.getOps<SwitchboxOp>()) {
2928 if (switchbox.getTileOp() != shimMux.getTileOp())
2929 continue;
2930 for (auto rules : switchbox.getConnections().getOps<PacketRulesOp>())
2931 for (int ch : {0, 1}) {
2932 Port dma{WireBundle::DMA, ch};
2933 Port north{WireBundle::North, shimMuxChannelFrom(dma)};
2934 if (rules.sourcePort() == Port{WireBundle::South, north.channel} &&
2935 hasConnect(dma, north)) {
2936 rules.setSourceBundle(WireBundle::DMA);
2937 rules.setSourceChannel(ch);
2938 break;
2939 }
2940 }
2941 for (auto masterSet : switchbox.getConnections().getOps<MasterSetOp>())
2942 for (int ch : {0, 1}) {
2943 Port dma{WireBundle::DMA, ch};
2944 Port north{WireBundle::North, shimMuxChannelTo(dma)};
2945 if (masterSet.destPort() == Port{WireBundle::South, north.channel} &&
2946 hasConnect(north, dma)) {
2947 masterSet.setDestBundle(WireBundle::DMA);
2948 masterSet.setDestChannel(ch);
2949 break;
2950 }
2951 }
2952 }
2953 }
2954}
2955
2956llvm::Expected<PacketPlan> AIEPathfinderPass::route(
2957 DeviceOp d, DynamicTileAnalysis &analyzer, const StreamConflicts &conflicts,
2958 const PinnedRoutes &pinned, bool circuitSwitchHops, bool prioritize) {
2959 // Packet flows that can deadlock must not share an arbiter. Every routing
2960 // the router finds is checked by planning the arbiters on it, and one that
2961 // cannot be planned counts as illegal, so routing and allocation agree.
2962 std::map<PathEndPoint, SmallVector<size_t, 4>> streamsFrom;
2963 PacketConstraints constraints;
2964 constraints.pinned = pinned.trees;
2965 constraints.pinnedIds = pinned.ids;
2966 constraints.prioritize = prioritize;
2967 if (clRoutePacket && !d.getOps<PacketFlowOp>().empty()) {
2968 const AIETargetModel &targetModel = d.getTargetModel();
2969 if (llvm::Error err = unroutableArbiters(
2970 d, conflicts,
2971 [&](TileID tile) {
2972 return !circuitSwitchHops ||
2973 targetModel.isShimNOCorPLTile(tile.col, tile.row);
2974 },
2975 pinned.trees))
2976 return std::move(err);
2977 for (auto [i, s] : llvm::enumerate(conflicts.getRequestedStreams()))
2978 if (s.packetID)
2979 streamsFrom[{s.src.tile, s.src.port}].push_back(i);
2980 constraints.apartAcross = [&](llvm::function_ref<bool(TileID)> low, bool up,
2981 size_t limit) {
2982 ArrayRef<RoutedStream> streams = conflicts.getStreams();
2983 SmallVector<size_t, 16> crossing;
2984 std::set<std::pair<TileID, Port>> srcs, dsts;
2985 for (auto [i, s] : llvm::enumerate(conflicts.getRequestedStreams()))
2986 if (s.packetID && low(s.src.tile) == up && low(s.dst.tile) != up) {
2987 crossing.push_back(i);
2988 srcs.insert({s.src.tile, s.src.port});
2989 dsts.insert({s.dst.tile, s.dst.port});
2990 }
2991 PacketsApart apart;
2992 // Streams kept apart have distinct sources and destinations.
2993 size_t most = std::min(srcs.size(), dsts.size());
2994 SmallVector<size_t, 8> best =
2995 most > limit
2996 ? largestApartSet(conflicts, crossing, limit)
2997 : SmallVector<size_t, 8>(
2998 crossing.begin(),
2999 crossing.begin() + std::min<size_t>(1, crossing.size()));
3000 for (size_t s : best)
3001 apart.flows.push_back(describeStream(streams[s]));
3002 if (best.size() > 1)
3003 apart.why = conflicts.explain(best[0], best[1]);
3004 return apart;
3005 };
3006 constraints.conflict = [&](const PathEndPoint &a, const std::set<int> &aIds,
3007 const PathEndPoint &b,
3008 const std::set<int> &bIds) {
3009 auto as = streamsFrom.find(a), bs = streamsFrom.find(b);
3010 if (as == streamsFrom.end() || bs == streamsFrom.end())
3011 return false;
3012 ArrayRef<RoutedStream> streams = conflicts.getStreams();
3013 for (size_t s : as->second)
3014 for (size_t t : bs->second)
3015 if (aIds.count(*streams[s].packetID) &&
3016 bIds.count(*streams[t].packetID) && conflicts.conflict(s, t))
3017 return true;
3018 return false;
3019 };
3020 constraints.check = [&](const Routing &routing) -> llvm::Error {
3021 PacketFlowRouting check(d, routing, conflicts, pinned, clRouteCircuit,
3022 circuitSwitchHops, prioritize);
3023 llvm::Expected<PacketPlan> plan = check.plan();
3024 if (!plan)
3025 return plan.takeError();
3026 RoutingFaults all = check.faults(), faults;
3027 faults.connections = std::move(all.connections);
3028 faults.apart = std::move(all.apart);
3029 faults.together = std::move(all.together);
3030 if (!plan->sharedReceiverCycle ||
3031 (faults.connections.empty() && faults.apart.empty() &&
3032 faults.together.empty()))
3033 return llvm::Error::success();
3034 return llvm::make_error<DeadlockProneRouting>(
3035 conflicts.explain(*plan->sharedReceiverCycle), std::move(faults));
3036 };
3037 }
3038 analyzer.pathfinder.setPacketConstraints(std::move(constraints));
3039 llvm::Error routed = analyzer.runAnalysis(d);
3040 analyzer.pathfinder.setPacketConstraints({});
3041 if (routed)
3042 return std::move(routed);
3043 if (!clRoutePacket)
3044 return PacketPlan();
3045 PacketFlowRouting found(d, analyzer.routing, conflicts, pinned,
3046 clRouteCircuit, circuitSwitchHops, prioritize);
3047 llvm::Expected<PacketPlan> plan = found.plan();
3048 if (found.incomplete) {
3049 llvm::consumeError(plan.takeError());
3050 return llvm::make_error<RoutingFailure>(std::move(found.incomplete->second),
3051 RoutingFaults{},
3052 found.incomplete->first);
3053 }
3054 // The routing found may still leave a hold cycle through receivers flows
3055 // share, as the check lets one through where it names nothing to move.
3056 if (!plan || clAllowDeadlockProne)
3057 return plan;
3058 const std::optional<HoldCycle> &cycle = plan->sharedReceiverCycle;
3059 if (!cycle)
3060 return plan;
3061 return llvm::make_error<DeadlockProneRouting>(
3062 (llvm::Twine(sharedReceiverCycleReason) + conflicts.explain(*cycle) +
3063 allowDeadlockProneHint)
3064 .str());
3065}
3066
3067static LogicalResult checkFixedFlowEndpoints(DeviceOp device) {
3068 DenseMap<PhysPort, Operation *> inputs, outputs;
3069 for (SwitchboxOp box : device.getOps<SwitchboxOp>()) {
3070 TileID tile = box.getTileOp().getTileID();
3071 for (ConnectOp connect : box.getOps<ConnectOp>()) {
3072 inputs[{tile, connect.sourcePort()}] = connect;
3073 outputs[{tile, connect.destPort()}] = connect;
3074 }
3075 for (MasterSetOp master : box.getOps<MasterSetOp>())
3076 outputs[{tile, master.destPort()}] = master;
3077 for (PacketRulesOp rules : box.getOps<PacketRulesOp>())
3078 inputs[{tile, rules.sourcePort()}] = rules;
3079 }
3080 AIEDialect::IsCtrlPktOverlayAttrHelper overlay(device.getContext());
3081 auto check = [&](Operation *flow, Value value, Port port,
3082 bool source) -> LogicalResult {
3083 auto tile = cast<TileOp>(value.getDefiningOp());
3084 auto &reservations = source ? inputs : outputs;
3085 Operation *reserved = reservations.lookup({tile.getTileID(), port});
3086 if (!reserved && tile.isShimNOCorPLTile() &&
3087 llvm::is_contained({WireBundle::DMA, WireBundle::NOC, WireBundle::PLIO},
3088 port.bundle)) {
3089 Port south{WireBundle::South,
3090 source ? shimMuxChannelFrom(port) : shimMuxChannelTo(port)};
3091 reserved = reservations.lookup({tile.getTileID(), south});
3092 }
3093 auto packet = dyn_cast<PacketFlowOp>(flow);
3094 if (!reserved || (packet && isa<PacketRulesOp>(reserved)))
3095 return success();
3096 bool fromOverlay = overlay.isAttrPresent(reserved);
3097 if (auto rules = dyn_cast<PacketRulesOp>(reserved))
3098 fromOverlay |= llvm::any_of(
3099 rules.getRules().getOps<PacketRuleOp>(),
3100 [&](PacketRuleOp rule) { return overlay.isAttrPresent(rule); });
3101 auto diag = emitError(flow->getLoc());
3102 diag << "Unable to find a legal routing: ";
3103 if (packet)
3104 diag << "packet flow " << packet.IDInt();
3105 else
3106 diag << "circuit flow";
3107 diag << (source ? " starts at " : " ends at ")
3108 << describeTilePort(tile.getTileID(), port) << ", whose "
3109 << (source ? "input" : "output") << " port is reserved by ";
3110 if (fromOverlay)
3111 diag << "the control packet overlay";
3112 else
3113 diag << "a fixed " << reserved->getName();
3114 diag.attachNote(reserved->getLoc())
3115 << (source ? "input" : "output") << " port reserved here by "
3116 << reserved->getName();
3117 return failure();
3118 };
3119 for (PacketFlowOp flow : device.getOps<PacketFlowOp>()) {
3120 for (PacketSourceOp source : flow.getPorts().getOps<PacketSourceOp>())
3121 if (failed(check(flow, source.getTile(), source.port(), true)))
3122 return failure();
3123 for (PacketDestOp dest : flow.getPorts().getOps<PacketDestOp>())
3124 if (failed(check(flow, dest.getTile(), dest.port(), false)))
3125 return failure();
3126 }
3127 for (FlowOp flow : device.getOps<FlowOp>())
3128 if (failed(check(flow, flow.getSource(),
3129 {flow.getSourceBundle(), flow.getSourceChannel()},
3130 true)) ||
3131 failed(check(flow, flow.getDest(),
3132 {flow.getDestBundle(), flow.getDestChannel()}, false)))
3133 return failure();
3134 return success();
3135}
3136
3137void AIEPathfinderPass::runOnOperation() {
3138
3139 // create analysis pass with routing graph for entire device
3140 LLVM_DEBUG(llvm::dbgs() << "---Begin AIEPathfinderPass---\n");
3141
3142 DeviceOp d = getOperation();
3143 if (failed(verifyDMAChannelsResolved(d)))
3144 return signalPassFailure();
3145 OpBuilder builder = OpBuilder::atBlockTerminator(d.getBody());
3146 if (clRoutePacket)
3147 unmuxShimDMAPacketPorts(d);
3148 if (failed(checkFixedFlowEndpoints(d)))
3149 return signalPassFailure();
3150
3151 StreamConflicts conflicts(d);
3152 if (auto pairs = conflicts.unavoidable(); !pairs.empty()) {
3153 InFlightDiagnostic diag =
3154 (clAllowDeadlockProne ? emitWarning(d.getLoc()) : emitError(d.getLoc()))
3155 << "Flows can deadlock however they are routed: "
3156 << conflicts.explain(pairs[0].first, pairs[0].second);
3157 if (pairs.size() > 1)
3158 diag << " So can " << pairs.size() - 1 << " other pair"
3159 << (pairs.size() > 2 ? "s" : "") << " of flows.";
3160 if (!clAllowDeadlockProne) {
3161 diag << allowDeadlockProneHint;
3162 return signalPassFailure();
3163 }
3164 }
3165 DynamicTileAnalysis analyzer;
3166 // A prioritized flow keeps the route it takes alone, so route the
3167 // prioritized flows without the rest of the design first, and pin their
3168 // trees for the rest to route around. Packets sharing a source and id with
3169 // a prioritized flow go with it (see prioritizedFlows); other packets from
3170 // their sources route freely.
3171 auto sourcesOf = [](PacketFlowOp flow) {
3172 return llvm::map_range(
3173 flow.getPorts().getOps<PacketSourceOp>(), [](PacketSourceOp src) {
3174 return PathEndPoint{
3175 cast<TileOp>(src.getTile().getDefiningOp()).getTileID(),
3176 src.port()};
3177 });
3178 };
3179 std::set<PathEndPoint> prioritized;
3180 std::set<std::pair<PathEndPoint, int>> prioritizedIds;
3181 for (PacketFlowOp flow : d.getOps<PacketFlowOp>())
3182 if (flow.getPriorityRoute().value_or(false))
3183 for (PathEndPoint src : sourcesOf(flow)) {
3184 prioritized.insert(src);
3185 prioritizedIds.insert({src, flow.IDInt()});
3186 }
3187 auto isPrioritized = [&](PacketFlowOp flow) {
3188 return llvm::any_of(sourcesOf(flow), [&](const PathEndPoint &src) {
3189 return prioritizedIds.count({src, flow.IDInt()}) > 0;
3190 });
3191 };
3192 auto routesAlone = isPrioritized;
3193 bool pinned = false;
3194 PinnedRoutes priority;
3195 bool othersToRoute = !d.getOps<FlowOp>().empty() ||
3196 !llvm::all_of(d.getOps<PacketFlowOp>(), routesAlone);
3197 // With no other flows to route, this routing is the route-alone one, so it
3198 // keeps off the avoided ports too.
3199 if (!othersToRoute)
3200 analyzer.avoidedPorts = avoidedPorts;
3201 if (clRoutePacket && !prioritized.empty() && othersToRoute) {
3202 OwningOpRef<ModuleOp> scratch;
3203 DeviceOp alone = cloneInScratch(d, scratch);
3204 SmallVector<Operation *> others;
3205 for (Operation &op : alone.getBody()->without_terminator()) {
3206 auto flow = dyn_cast<PacketFlowOp>(op);
3207 if (flow ? !routesAlone(flow) : isa<FlowOp>(op))
3208 others.push_back(&op);
3209 }
3210 for (Operation *op : others)
3211 op->dropAllReferences();
3212 for (Operation *op : others)
3213 op->erase();
3214 std::map<PathEndPoint, std::set<int>> aloneIds;
3215 for (PacketFlowOp flow : alone.getOps<PacketFlowOp>())
3216 for (auto src : flow.getPorts().getOps<PacketSourceOp>()) {
3217 auto tile = cast<TileOp>(src.getTile().getDefiningOp());
3218 aloneIds[{{tile.colIndex(), tile.rowIndex()}, src.port()}].insert(
3219 flow.IDInt());
3220 }
3221 DynamicTileAnalysis aloneAnalyzer;
3222 aloneAnalyzer.avoidedPorts = avoidedPorts;
3223 StreamConflicts aloneConflicts(alone);
3224 llvm::Expected<PacketPlan> alonePlan =
3225 route(alone, aloneAnalyzer, aloneConflicts, {},
3226 /*circuitSwitchHops=*/false);
3227 if (!alonePlan) {
3228 llvm::consumeError(alonePlan.takeError());
3229 } else {
3230 // The design's own routing keeps these trees, so it warns of any hold
3231 // cycle they leave.
3232 OpBuilder aloneBuilder = OpBuilder::atBlockTerminator(alone.getBody());
3233 if (failed(runOnPacketFlow(alone, aloneBuilder, aloneAnalyzer,
3234 aloneConflicts, *alonePlan, /*warn=*/false)))
3235 return signalPassFailure();
3236 priority = PinnedRoutes{aloneAnalyzer.routing.packetTrees,
3237 std::move(aloneIds), priorityRules(alone)};
3238 pinned = true;
3239 }
3240 }
3241 // If routing fails, the router relaxes how it routes packet flows (see
3242 // Pathfinder::relax) and tries again. The error is the first attempt's, or
3243 // the first to find a routing allow-deadlock-prone would take, as that is
3244 // all that keeps the design from routing.
3245 auto routeRelaxing = [&](DeviceOp dev, DynamicTileAnalysis &an,
3246 const StreamConflicts &c, const PinnedRoutes &pin,
3247 bool prioritize =
3248 true) -> llvm::Expected<PacketPlan> {
3249 // Every attempt of the ladder routes `dev` under the same constraints, so
3250 // one that replays an earlier attempt is skipped (see findPaths).
3251 std::vector<PathfinderAttempt> attempts;
3252 an.pathfinder.attempts = &attempts;
3253 llvm::scope_exit detach([&] { an.pathfinder.attempts = nullptr; });
3254 llvm::Expected<PacketPlan> plan =
3255 route(dev, an, c, pin, clCircuitSwitchHops, prioritize);
3256 if (plan)
3257 return plan;
3258 llvm::Error first = plan.takeError();
3259 while (an.pathfinder.relax()) {
3260 plan = route(dev, an, c, pin, clCircuitSwitchHops, prioritize);
3261 if (plan) {
3262 llvm::consumeError(std::move(first));
3263 return plan;
3264 }
3265 llvm::Error err = plan.takeError();
3266 if (err.isA<DeadlockProneRouting>() && !first.isA<DeadlockProneRouting>())
3267 std::swap(first, err);
3268 llvm::consumeError(std::move(err));
3269 }
3270 return std::move(first);
3271 };
3272 llvm::Expected<PacketPlan> plan =
3273 routeRelaxing(d, analyzer, conflicts, priority);
3274 if (!plan && !prioritized.empty()) {
3275 llvm::Error err = plan.takeError();
3276 priority = {};
3277 DynamicTileAnalysis freeAnalyzer;
3278 plan = routeRelaxing(d, freeAnalyzer, conflicts, priority,
3279 /*prioritize=*/false);
3280 if (plan) {
3281 llvm::consumeError(std::move(err));
3282 analyzer = std::move(freeAnalyzer);
3283 } else {
3284 llvm::Error freeErr = plan.takeError();
3285 if (freeErr.isA<DeadlockProneRouting>() ||
3286 !err.isA<DeadlockProneRouting>())
3287 std::swap(err, freeErr);
3288 llvm::consumeError(std::move(freeErr));
3289 plan = std::move(err);
3290 }
3291 pinned = false;
3292 }
3293 if (!plan) {
3294 llvm::handleAllErrors(plan.takeError(), [&](RoutingFailure &f) {
3295 // Say whether the pinned trees are what stands in the way: the design
3296 // routes if they may move.
3297 if (pinned && !f.reason.empty() &&
3298 !f.isA(PinnedRoutingFailure::classID())) {
3299 OwningOpRef<ModuleOp> scratch;
3300 DeviceOp free = cloneInScratch(d, scratch);
3301 DynamicTileAnalysis freeAnalyzer;
3302 StreamConflicts freeConflicts(free);
3303 llvm::Expected<PacketPlan> freePlan = routeRelaxing(
3304 free, freeAnalyzer, freeConflicts, {}, /*prioritize=*/false);
3305 if (!freePlan) {
3306 llvm::consumeError(freePlan.takeError());
3307 } else {
3308 f.reason = describePrioritized(llvm::to_vector(llvm::map_range(
3309 prioritized,
3310 [](const PathEndPoint &src) {
3311 return describeTilePort(src.coords, src.port);
3312 }))) +
3313 ", and the other flows route only if it moves. Around "
3314 "it, " +
3315 f.reason;
3316 }
3317 }
3318 emitError(f.loc.value_or(d.getLoc())) << f.message();
3319 });
3320 signalPassFailure();
3321 return;
3322 }
3323 for (auto flowOp : d.getOps<FlowOp>()) {
3324 if (!flowOp.getVias().empty()) {
3325 flowOp.emitOpError("cannot be routed while it carries via waypoints; run "
3326 "--aie-split-flow-vias first to lower the vias into "
3327 "switchbox connections");
3328 signalPassFailure();
3329 return;
3330 }
3331 }
3332 for (auto flowOp : d.getOps<PacketFlowOp>()) {
3333 if (!flowOp.getVias().empty()) {
3334 flowOp.emitOpError("cannot be routed while it carries via waypoints; run "
3335 "--aie-split-flow-vias first to lower the vias into "
3336 "switchbox connections");
3337 signalPassFailure();
3338 return;
3339 }
3340 }
3341
3342 if (clRouteCircuit && failed(runOnFlow(d, analyzer))) {
3343 signalPassFailure();
3344 return;
3345 }
3346 if (clRoutePacket && failed(runOnPacketFlow(d, builder, analyzer, conflicts,
3347 *plan, /*warn=*/true))) {
3348 signalPassFailure();
3349 return;
3350 }
3351 // Populate wires between switchboxes and tiles. Re-running the pass on
3352 // already-routed IR must not duplicate the wires a previous run emitted, so
3353 // key the wires already present and emit only the missing ones.
3354 builder.setInsertionPoint(d.getBody()->getTerminator());
3355 llvm::DenseSet<std::tuple<Value, int, Value, int>> existingWires;
3356 // aie.wire is a physical connection, so the IR may spell one adjacency in
3357 // either operand order.
3358 auto recordWire = [&](Value source, int sourceBundle, Value dest,
3359 int destBundle) {
3360 bool absent =
3361 !existingWires.contains({source, sourceBundle, dest, destBundle}) &&
3362 !existingWires.contains({dest, destBundle, source, sourceBundle});
3363 existingWires.insert({source, sourceBundle, dest, destBundle});
3364 existingWires.insert({dest, destBundle, source, sourceBundle});
3365 return absent;
3366 };
3367 for (auto wire : d.getOps<WireOp>()) {
3368 recordWire(wire.getSource(), static_cast<int>(wire.getSourceBundle()),
3369 wire.getDest(), static_cast<int>(wire.getDestBundle()));
3370 }
3371 auto wire = [&](Location loc, Value source, WireBundle sourceBundle,
3372 Value dest, WireBundle destBundle) {
3373 if (recordWire(source, static_cast<int>(sourceBundle), dest,
3374 static_cast<int>(destBundle))) {
3375 WireOp::create(builder, loc, source, sourceBundle, dest, destBundle);
3376 }
3377 };
3378 for (int col = 0; col <= analyzer.getMaxCol(); col++) {
3379 for (int row = 0; row <= analyzer.getMaxRow(); row++) {
3380 TileOp tile = analyzer.lookupTile({col, row});
3381 SwitchboxOp sw = analyzer.lookupSwitchbox({col, row});
3382 if (!tile || !sw)
3383 continue;
3384 Location loc = tile.getLoc();
3385 // connections east-west between stream switches
3386 if (col > 0)
3387 if (SwitchboxOp westsw = analyzer.lookupSwitchbox({col - 1, row}))
3388 wire(loc, westsw, WireBundle::East, sw, WireBundle::West);
3389 if (row > 0) {
3390 // connections between abstract 'core' of tile
3391 wire(loc, tile, WireBundle::Core, sw, WireBundle::Core);
3392 // connections between abstract 'dma' of tile
3393 wire(loc, tile, WireBundle::DMA, sw, WireBundle::DMA);
3394 // connections north-south inside array ( including connection to shim
3395 // row)
3396 if (SwitchboxOp southsw = analyzer.lookupSwitchbox({col, row - 1}))
3397 wire(loc, southsw, WireBundle::North, sw, WireBundle::South);
3398 } else if (tile.isShimNOCTile()) {
3399 if (ShimMuxOp shimsw = analyzer.lookupShimMux(col)) {
3400 wire(loc, shimsw,
3401 WireBundle::North, // Changed to connect into the north
3402 sw, WireBundle::South);
3403 // abstract 'DMA' connection on tile is attached to shim mux ( in
3404 // row 0 )
3405 wire(loc, tile, WireBundle::DMA, shimsw, WireBundle::DMA);
3406 }
3407 }
3408 }
3409 }
3410}
3411
3412std::unique_ptr<OperationPass<DeviceOp>> AIE::createAIEPathfinderPass() {
3413 return std::make_unique<AIEPathfinderPass>();
3414}
3415
3416std::unique_ptr<OperationPass<DeviceOp>>
3417AIE::createAIEPathfinderPass(const AIERoutePathfinderFlowsOptions &options) {
3418 return std::make_unique<AIEPathfinderPass>(options);
3419}
3420
3421std::unique_ptr<OperationPass<DeviceOp>>
3422AIE::createAIEPathfinderPass(const AIERoutePathfinderFlowsOptions &options,
3423 ArrayRef<std::pair<TileID, Port>> avoidedPorts) {
3424 auto pass = std::make_unique<AIEPathfinderPass>(options);
3425 pass->avoidedPorts.assign(avoidedPorts.begin(), avoidedPorts.end());
3426 return pass;
3427}
constexpr int maxSearchSteps
std::pair< TileID, Port > PhysPort
constexpr int maxHoldCycleReplans
std::map< PhysPort, SmallVector< std::tuple< int, int, int >, 2 > > PriorityRules
(mask, value, amsel) by slave port, in slot order.
std::tuple< int, int, int, int, int, int, int, int, int, int > FlowKey
virtual uint32_t getNumMselsPerArbiter() const =0
Return the number of master select values per stream-switch arbiter.
virtual uint32_t getNumArbiters() const =0
Return the number of arbiters per stream switch.
bool isShimNOCorPLTile(int col, int row) const
Return true if the given tile is either a ShimNOC or ShimPL tile.
virtual int rows() const =0
Return the number of rows in the device.
bool isShimNOCTile(int col, int row) const
Return true if the given tile is a ShimNOC tile.
virtual uint32_t getMaxPacketId() const =0
Return the largest packet id the stream switch can route.
virtual int columns() const =0
Return the number of columns in the device.
int getPacketIdBits() const
Bits a packet id spans, and the mask a switch's id match uses.
virtual uint32_t getNumDestSwitchboxConnections(int col, int row, WireBundle bundle) const =0
Return the number of destinations of connections inside a switchbox.
virtual uint32_t getNumSlaveSlots() const =0
Return the number of packet-rule slots per stream-switch slave port.
ShimMuxOp getShimMux(mlir::OpBuilder &builder, int col)
SwitchboxOp getSwitchbox(mlir::OpBuilder &builder, int col, int row)
SwitchboxOp lookupSwitchbox(TileID tile) const
TileOp lookupTile(TileID tile) const
TileOp getTile(mlir::OpBuilder &builder, int col, int row)
llvm::Error runAnalysis(DeviceOp &device)
std::set< PathEndPoint > processedFlows
ShimMuxOp lookupShimMux(int col) const
std::vector< std::pair< TileID, Port > > avoidedPorts
void setPacketConstraints(PacketConstraints c)
std::optional< mlir::Location > loc
The streams a device asks for or already routes, and which pairs of them must not share an arbiter or...
llvm::ArrayRef< RoutedStream > getRequestedStreams() const
The streams the flow ops ask for, which come first in getStreams().
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...
llvm::ArrayRef< RoutedStream > getStreams() const
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.
int shimMuxChannelTo(Port dst)
struct Connect { Port src; Port dst; bool operator==(const Connect &rhs) const { return std::tie(src, dst)==std::tie(rhs.src, rhs.dst); } bool operator!=(const Connect &rhs) const { return !(*this==rhs);} bool operator<(const Connect &rhs) const { return std::tie(src, dst)< std::tie(rhs.src, rhs.dst); } } Connect
Definition AIEDialect.h:299
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)
mlir::LogicalResult verifyDMAChannelsResolved(DeviceOp device)
int shimMuxChannelFrom(Port src)
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::map< TileID, SwitchSetting > SwitchSettings
std::unique_ptr< mlir::OperationPass< DeviceOp > > createAIEPathfinderPass()
std::string describePort(Port port)
Names a port the way diagnostics do, e.g. "DMA:1".
std::map< PathEndPoint, std::vector< TreeHop > > PacketTrees
std::map< PathEndPoint, std::set< int > > ids
bool forced
The wait holds however the arbiters are planned, as sharer and holding go into a receiver they share ...
std::map< PathEndPoint, std::set< int > > pinnedIds
std::vector< std::string > flows
std::optional< int > packetID
The packet id carried, if any.
std::vector< std::pair< TileID, Connect > > connections
std::vector< PathEndPoint > untrunk
std::vector< std::pair< PathEndPoint, PathEndPoint > > together
std::vector< TreeSplit > splits
std::vector< TileID > crowded
std::vector< std::pair< PathEndPoint, PathEndPoint > > apart
std::map< PathEndPoint, SwitchSettings > settings
std::map< std::pair< PathEndPoint, int >, SwitchSettings > idSettings