12#include "mlir/IR/IRMapping.h"
13#include "mlir/Pass/Pass.h"
21#include "llvm/ADT/DenseSet.h"
22#include "llvm/ADT/STLExtras.h"
23#include "llvm/ADT/SmallBitVector.h"
26#define GEN_PASS_DEF_AIEFINDFLOWS
27#include "aie/Dialect/AIE/Transforms/AIEPasses.h.inc"
30#define DEBUG_TYPE "aie-find-flows"
51 llvm::SmallVector<Operation *, 3> ops;
65 llvm::SmallVector<Via, 4> vias;
67 llvm::SmallVector<Operation *, 8> usedOps;
68 bool isPacket =
false;
75 llvm::SmallVector<Operation *, 3>
ops;
80 bool splitFanouts =
false;
81 mutable llvm::DenseSet<std::pair<Operation *, int>> fanoutIngresses;
82 mutable llvm::DenseSet<std::pair<Operation *, int>> fanoutEgressSeeds;
83 mutable llvm::SmallVector<CircuitFanoutSeed, 8> circuitFanoutSeeds;
84 mutable std::set<std::tuple<Operation *, int, int>> packetMergeEgresses;
85 mutable llvm::DenseSet<Operation *> packetMergeOps;
87 static int encodePort(
Port p) {
88 return static_cast<int>(p.bundle) * 64 + p.channel;
98 auto scan = [&](Operation *sw, Region &connections) {
99 llvm::SmallVector<Port, 8> sources;
100 Block &b = connections.front();
101 for (
auto connectOp : b.getOps<ConnectOp>()) {
102 if (!llvm::is_contained(sources, connectOp.sourcePort())) {
103 sources.push_back(connectOp.sourcePort());
106 for (
auto rulesOp : b.getOps<PacketRulesOp>()) {
107 if (!llvm::is_contained(sources, rulesOp.sourcePort())) {
108 sources.push_back(rulesOp.sourcePort());
112 for (
Port p : sources) {
113 if (getConnectionsThroughSwitchbox(connections, p).size() > 1) {
114 fanoutIngresses.insert({sw, encodePort(p)});
118 const int idMask = device.getTargetModel().getPacketIdMask();
119 using MergeKey = std::pair<int, int>;
120 std::map<MergeKey, SmallVector<Port, 4>> mergeIngresses;
121 std::map<MergeKey, SmallVector<Operation *, 8>> mergeOps;
122 for (PacketRulesOp rules : b.getOps<PacketRulesOp>()) {
123 for (
int id = 0;
id <= idMask; ++id) {
124 PacketRuleOp selected;
125 for (PacketRuleOp rule :
126 rules.getRules().front().getOps<PacketRuleOp>()) {
127 if ((
id & rule.maskInt()) == rule.valueInt()) {
134 for (MasterSetOp masterSet : b.getOps<MasterSetOp>()) {
135 if (!llvm::is_contained(masterSet.getAmsels(), selected.getAmsel()))
137 MergeKey key{encodePort(masterSet.destPort()),
id};
138 if (!llvm::is_contained(mergeIngresses[key], rules.sourcePort()))
139 mergeIngresses[key].push_back(rules.sourcePort());
141 {selected.getOperation(), masterSet.getOperation(),
142 selected.getAmsel().getDefiningOp()})
143 if (!llvm::is_contained(mergeOps[key], op))
144 mergeOps[key].push_back(op);
148 for (
const auto &[key, ingresses] : mergeIngresses) {
149 if (ingresses.size() < 2)
151 auto [egress, id] = key;
152 packetMergeEgresses.insert({sw, egress,
id});
153 packetMergeOps.insert_range(mergeOps[key]);
156 for (
auto switchOp : device.getOps<SwitchboxOp>()) {
157 scan(switchOp, switchOp.getConnections());
163 return fanoutEgressSeeds;
166 return circuitFanoutSeeds;
169 return packetMergeOps;
172 return packetMergeEgresses;
175 return {
static_cast<WireBundle
>(e / 64), e % 64};
179 std::optional<PortConnection>
180 getConnectionThroughWire(Operation *op,
Port masterPort)
const {
181 LLVM_DEBUG(llvm::dbgs() <<
"Wire:" << *op <<
" "
182 << stringifyWireBundle(masterPort.bundle) <<
" "
183 << masterPort.channel <<
"\n");
184 for (
auto wireOp : device.getOps<WireOp>()) {
185 if (wireOp.getSource().getDefiningOp() == op &&
186 wireOp.getSourceBundle() == masterPort.bundle) {
187 Operation *other = wireOp.getDest().getDefiningOp();
188 Port otherPort = {wireOp.getDestBundle(), masterPort.channel};
189 LLVM_DEBUG(llvm::dbgs() <<
"Connects To:" << *other <<
" "
190 << stringifyWireBundle(otherPort.bundle) <<
" "
191 << otherPort.channel <<
"\n");
195 if (wireOp.getDest().getDefiningOp() == op &&
196 wireOp.getDestBundle() == masterPort.bundle) {
197 Operation *other = wireOp.getSource().getDefiningOp();
198 Port otherPort = {wireOp.getSourceBundle(), masterPort.channel};
199 LLVM_DEBUG(llvm::dbgs() <<
"Connects To:" << *other <<
" "
200 << stringifyWireBundle(otherPort.bundle) <<
" "
201 << otherPort.channel <<
"\n");
205 LLVM_DEBUG(llvm::dbgs() <<
"*** Missing Wire!\n");
209 std::vector<PortMaskValue>
210 getConnectionsThroughSwitchbox(Region &r,
Port sourcePort)
const {
211 LLVM_DEBUG(llvm::dbgs() <<
"Switchbox:\n");
212 Block &b = r.front();
213 std::vector<PortMaskValue> portSet;
214 for (
auto connectOp : b.getOps<ConnectOp>()) {
215 if (connectOp.sourcePort() == sourcePort) {
217 portSet.push_back({connectOp.destPort(), maskValue, {connectOp}});
218 LLVM_DEBUG(llvm::dbgs()
219 <<
"To:" << stringifyWireBundle(connectOp.destPort().bundle)
220 <<
" " << connectOp.destPort().channel <<
"\n");
223 for (
auto connectOp : b.getOps<PacketRulesOp>()) {
224 if (connectOp.sourcePort() == sourcePort) {
225 LLVM_DEBUG(llvm::dbgs()
227 << stringifyWireBundle(connectOp.sourcePort().bundle) <<
" "
228 << sourcePort.channel <<
"\n");
230 for (
auto ruleOp : connectOp.getRules().front().getOps<PacketRuleOp>())
231 for (
auto masterSetOp : b.getOps<MasterSetOp>())
232 for (Value amsel : masterSetOp.getAmsels()) {
233 if (ruleOp.getAmsel() == amsel) {
234 LLVM_DEBUG(llvm::dbgs()
236 << stringifyWireBundle(masterSetOp.destPort().bundle)
237 <<
" " << masterSetOp.destPort().channel <<
"\n");
238 MaskValue maskValue = {ruleOp.maskInt(), ruleOp.valueInt()};
240 {masterSetOp.destPort(),
242 {ruleOp, masterSetOp, amsel.getDefiningOp()}});
250 std::vector<PacketConnection> maskSwitchboxConnections(
251 Operation *switchOp,
Port ingressPort, ArrayRef<Via> currentVias,
252 ArrayRef<Operation *> currentUsedOps,
253 const std::vector<PortMaskValue> &nextPortMaskValues,
MaskValue maskValue,
254 bool currentIsPacket,
bool keepPartialFlows,
255 std::vector<PacketConnection> &partialEndpoints)
const {
256 std::vector<PacketConnection> worklist;
259 Operation *takenBy =
nullptr;
263 if (
auto sb = dyn_cast<SwitchboxOp>(switchOp)) {
264 viaTile = sb.getTile();
266 for (
auto &nextPortMaskValue : nextPortMaskValues) {
267 Port nextPort = nextPortMaskValue.port;
268 MaskValue nextMaskValue = nextPortMaskValue.mv;
269 Operation *rule = nextPortMaskValue.ops.front();
270 if (!isa<PacketRuleOp>(rule)) {
273 if (takenBy && rule != takenBy) {
276 int maskConflicts = nextMaskValue.mask & maskValue.mask;
277 LLVM_DEBUG(llvm::dbgs() <<
"Mask: " << maskValue.mask <<
" "
278 << maskValue.value <<
"\n");
279 LLVM_DEBUG(llvm::dbgs() <<
"NextMask: " << nextMaskValue.mask <<
" "
280 << nextMaskValue.value <<
"\n");
281 LLVM_DEBUG(llvm::dbgs() << maskConflicts <<
"\n");
283 if ((maskConflicts & nextMaskValue.value) !=
284 (maskConflicts & maskValue.value)) {
288 if (rule && (nextMaskValue.mask & ~maskValue.mask) == 0) {
291 MaskValue newMaskValue = {maskValue.mask | nextMaskValue.mask,
293 (nextMaskValue.mask & nextMaskValue.value)};
294 bool reachesMerge =
false;
295 int maxPacketId = device.getTargetModel().getMaxPacketId();
296 for (
int id = 0;
id <= maxPacketId; ++id) {
297 if ((
id & newMaskValue.mask) != newMaskValue.value)
299 if (packetMergeEgresses.count({switchOp, encodePort(nextPort), id})) {
305 partialEndpoints.push_back({{switchOp, ingressPort},
307 llvm::to_vector(currentVias),
308 llvm::to_vector(currentUsedOps),
309 currentIsPacket || rule !=
nullptr});
312 SmallVector<Via, 4> newVias(currentVias.begin(), currentVias.end());
314 newVias.push_back({viaTile, ingressPort, nextPort});
316 SmallVector<Operation *, 8> newUsedOps(currentUsedOps.begin(),
317 currentUsedOps.end());
318 newUsedOps.append(nextPortMaskValue.ops.begin(),
319 nextPortMaskValue.ops.end());
320 auto nextConnection = getConnectionThroughWire(switchOp, nextPort);
322 if (!nextConnection) {
326 if (keepPartialFlows) {
327 partialEndpoints.push_back({{switchOp, nextPort},
331 currentIsPacket || rule !=
nullptr});
336 worklist.push_back({*nextConnection, newMaskValue, newVias, newUsedOps,
337 currentIsPacket || rule !=
nullptr});
345 return getConnectionThroughWire(op, port);
352 if (
auto sb = dyn_cast<SwitchboxOp>(op)) {
353 r = &sb.getConnections();
354 }
else if (
auto sm = dyn_cast<ShimMuxOp>(op)) {
355 r = &sm.getConnections();
360 Block &b = r->front();
361 for (
auto connectOp : b.getOps<ConnectOp>()) {
362 if (connectOp.destPort() == port) {
366 for (
auto masterSetOp : b.getOps<MasterSetOp>()) {
367 if (masterSetOp.destPort() == port) {
374 std::vector<PacketConnection>
traverse(std::vector<PacketConnection> worklist,
375 bool keepPartialFlows)
const {
376 std::vector<PacketConnection> connectedTiles;
377 while (!worklist.empty()) {
380 Operation *other = t.portConnection.op;
381 Port otherPort = t.portConnection.port;
385 connectedTiles.push_back(t);
388 Region *connections =
nullptr;
389 if (
auto switchOp = dyn_cast_or_null<SwitchboxOp>(other)) {
390 connections = &switchOp.getConnections();
391 }
else if (
auto switchOp = dyn_cast_or_null<ShimMuxOp>(other)) {
392 connections = &switchOp.getConnections();
395 LLVM_DEBUG(llvm::dbgs()
396 <<
"*** Connection Terminated at unknown operation: ");
397 LLVM_DEBUG(other->dump());
404 fanoutIngresses.count({other, encodePort(otherPort)})) {
405 connectedTiles.push_back(t);
407 getConnectionsThroughSwitchbox(*connections, otherPort)) {
408 if (isa<ConnectOp>(pmv.ops.front())) {
410 return seed.op == other && seed.ingress == otherPort &&
411 seed.egress == pmv.port;
413 if (!llvm::any_of(circuitFanoutSeeds, sameSeed)) {
414 circuitFanoutSeeds.push_back(
415 {other, otherPort, pmv.port, pmv.ops});
418 fanoutEgressSeeds.insert({other, encodePort(pmv.port)});
423 std::vector<PortMaskValue> nextPortMaskValues =
424 getConnectionsThroughSwitchbox(*connections, otherPort);
425 std::vector<PacketConnection> partialEndpoints;
426 std::vector<PacketConnection> newWorkList = maskSwitchboxConnections(
427 other, otherPort, t.vias, t.usedOps, nextPortMaskValues, maskValue,
428 t.isPacket, keepPartialFlows, partialEndpoints);
429 worklist.insert(worklist.end(), newWorkList.begin(), newWorkList.end());
430 connectedTiles.insert(connectedTiles.end(), partialEndpoints.begin(),
431 partialEndpoints.end());
432 if (!nextPortMaskValues.empty() && newWorkList.empty() &&
433 partialEndpoints.empty()) {
436 LLVM_DEBUG(llvm::dbgs() <<
"No rule matched incoming packet here: ");
437 LLVM_DEBUG(other->dump());
440 return connectedTiles;
447 std::vector<PacketConnection>
450 LLVM_DEBUG(llvm::dbgs()
451 <<
"getConnectedTile(" << stringifyWireBundle(port.bundle) <<
" "
452 << port.channel <<
")");
453 LLVM_DEBUG(tileOp.dump());
455 auto t = getConnectionThroughWire(tileOp.getOperation(), port);
464 std::vector<PacketConnection>
466 bool keepPartialFlows,
477 std::vector<PacketConnection>
479 bool keepPartialFlows,
481 auto t = getConnectionThroughWire(switchOp, egressPort);
489 std::vector<PacketConnection>
491 bool keepPartialFlows)
const {
492 auto connection = getConnectionThroughWire(seed.
op, seed.
egress);
496 Value tile = cast<SwitchboxOp>(seed.
op).getTile();
497 SmallVector<Operation *, 8> usedOps(seed.
ops.begin(), seed.
ops.end());
503 return traverse({std::move(branch)}, keepPartialFlows);
511static constexpr int kCircuitFlow = -1;
512using FlowKey = std::tuple<int, int, int, int, int, int, int, int, int, int>;
518static std::optional<FlowKey> tryGetFlowKey(Value srcTileValue,
Port srcPort,
519 Value destTileValue,
Port destPort,
520 int packetID,
int packetMask) {
521 auto coords = [](Value v) -> std::optional<std::pair<int, int>> {
522 auto tile = llvm::dyn_cast_or_null<TileLike>(v.getDefiningOp());
525 std::optional<int> col = tile.tryGetCol();
526 std::optional<int> row = tile.tryGetRow();
529 return std::make_pair(*col, *row);
531 std::optional<std::pair<int, int>> src = coords(srcTileValue);
532 std::optional<std::pair<int, int>> dest = coords(destTileValue);
537 static_cast<int>(srcPort.bundle),
541 static_cast<int>(destPort.bundle),
549static Value resolveEndpointTile(Operation *op) {
550 if (isa<TileOp>(op)) {
551 return op->getResult(0);
553 if (
auto element = dyn_cast<TileElement>(op)) {
554 return element.getTile();
566 llvm::DenseSet<Operation *>
kept;
567 std::vector<std::pair<PacketFlowOp, SmallVector<Operation *, 8>>>
packetFlows;
570static void emitFlows(OpBuilder &rewriter, Location loc, Value srcTile,
571 WireBundle srcBundle,
int srcChannel,
572 const std::vector<PacketConnection> &endpoints,
573 bool emitVias,
bool dropIntraTile,
int idMask,
575 AIEDialect::IsCtrlPktOverlayAttrHelper overlay(rewriter.getContext());
576 AIEDialect::PriorityRouteAttrHelper prioritizedRule(rewriter.getContext());
578 Operation *destOp = c.portConnection.op;
579 Port destPort = c.portConnection.port;
581 Value destTile = resolveEndpointTile(destOp);
586 bool marked = llvm::any_of(c.usedOps, [&](Operation *op) {
587 Operation *rulesParent =
588 isa_and_nonnull<PacketRuleOp>(op) ? op->getParentOp() : nullptr;
589 return lifted.fixed.contains(op) ||
590 (op && overlay.isAttrPresent(op) &&
591 !(isa<ConnectOp>(op) && isa<ShimMuxOp>(op->getParentOp()))) ||
592 (rulesParent && overlay.isAttrPresent(rulesParent));
595 for (Operation *op : c.usedOps) {
597 lifted.
kept.insert(op);
604 if (emitVias && c.vias.empty()) {
609 bool isPacket = c.isPacket;
613 std::optional<FlowKey> key =
614 tryGetFlowKey(srcTile, {srcBundle, srcChannel}, destTile, destPort,
615 isPacket ? maskValue.value : kCircuitFlow,
616 isPacket ? maskValue.mask : 0);
617 if (key && !seen.insert(*key).second) {
621 for (Operation *op : c.usedOps) {
632 BoolAttr keepPktHeader, priorityRoute;
633 bool markedDest =
false;
634 std::optional<bool> markedSource;
635 for (Operation *op : c.usedOps) {
636 if (
auto ms = dyn_cast_or_null<MasterSetOp>(op)) {
637 if (ms.getDestBundle() == destPort.bundle &&
638 ms.getDestChannel() == destPort.channel) {
639 keepPktHeader = ms.getKeepPktHeaderAttr();
640 markedDest = prioritizedRule.isAttrPresent(ms);
643 if (!markedSource && isa_and_nonnull<PacketRuleOp>(op))
644 markedSource = prioritizedRule.isAttrPresent(op) ||
645 prioritizedRule.isAttrPresent(op->getParentOp());
647 if (markedDest && markedSource.value_or(
false)) {
648 priorityRoute = rewriter.getBoolAttr(
true);
658 if (maskValue.mask != idMask) {
659 mask = rewriter.getI8IntegerAttr(maskValue.mask);
661 MLIRContext *ctx = rewriter.getContext();
662 SmallVector<Value> viaTiles;
663 SmallVector<int32_t> ingressBundles, ingressChannels, egressBundles,
666 for (
const Via &via : c.vias) {
667 viaTiles.push_back(via.
tile);
668 ingressBundles.push_back(
static_cast<int32_t
>(via.
ingress.bundle));
669 ingressChannels.push_back(via.
ingress.channel);
670 egressBundles.push_back(
static_cast<int32_t
>(via.
egress.bundle));
671 egressChannels.push_back(via.
egress.channel);
674 auto ib = viaTiles.empty() ? nullptr
675 : DenseI32ArrayAttr::get(ctx, ingressBundles);
676 auto ic = viaTiles.empty() ? nullptr
677 : DenseI32ArrayAttr::get(ctx, ingressChannels);
678 auto eb = viaTiles.empty() ? nullptr
679 : DenseI32ArrayAttr::get(ctx, egressBundles);
680 auto ec = viaTiles.empty() ? nullptr
681 : DenseI32ArrayAttr::get(ctx, egressChannels);
682 auto flowOp = PacketFlowOp::create(
683 rewriter, loc, rewriter.getI8IntegerAttr(maskValue.value), mask,
684 keepPktHeader, priorityRoute, viaTiles, ib, ic, eb, ec);
685 PacketFlowOp::ensureTerminator(flowOp.getPorts(), rewriter, loc);
686 OpBuilder::InsertPoint ip = rewriter.saveInsertionPoint();
687 rewriter.setInsertionPoint(flowOp.getPorts().front().getTerminator());
688 PacketSourceOp::create(rewriter, loc, srcTile, srcBundle, srcChannel);
689 PacketDestOp::create(rewriter, loc, destTile, destPort.bundle,
691 rewriter.restoreInsertionPoint(ip);
692 lifted.
packetFlows.emplace_back(flowOp, c.usedOps);
697 if (c.usedOps.empty()) {
702 if (dropIntraTile && destTile == srcTile && isa<TileOp>(destOp)) {
705 for (Operation *op : c.usedOps) {
710 MLIRContext *ctx = rewriter.getContext();
711 SmallVector<Value> viaTiles;
712 SmallVector<int32_t> ingressBundles, ingressChannels, egressBundles,
715 for (
const Via &via : c.vias) {
716 viaTiles.push_back(via.
tile);
717 ingressBundles.push_back(
static_cast<int32_t
>(via.
ingress.bundle));
718 ingressChannels.push_back(via.
ingress.channel);
719 egressBundles.push_back(
static_cast<int32_t
>(via.
egress.bundle));
720 egressChannels.push_back(via.
egress.channel);
723 auto ib = viaTiles.empty() ? nullptr
724 : DenseI32ArrayAttr::get(ctx, ingressBundles);
725 auto ic = viaTiles.empty() ? nullptr
726 : DenseI32ArrayAttr::get(ctx, ingressChannels);
728 viaTiles.empty() ? nullptr : DenseI32ArrayAttr::get(ctx, egressBundles);
729 auto ec = viaTiles.empty() ? nullptr
730 : DenseI32ArrayAttr::get(ctx, egressChannels);
731 FlowOp::create(rewriter, loc, srcTile, srcBundle, srcChannel, destTile,
732 destPort.bundle, destPort.channel, viaTiles, ib, ic, eb, ec);
741static std::vector<PacketConnection> exactPacketEndpoints(
742 std::vector<PacketConnection> endpoints,
int idMask,
743 llvm::function_ref<std::vector<PacketConnection>(
MaskValue)> trace,
746 if (llvm::none_of(endpoints, isPacket)) {
749 std::vector<PacketConnection> result;
750 llvm::copy_if(endpoints, std::back_inserter(result),
754 if (a.portConnection.op != b.portConnection.op ||
755 a.portConnection.port != b.portConnection.port ||
756 a.vias.size() != b.vias.size()) {
759 return llvm::equal(a.vias, b.vias, [](
const Via &x,
const Via &y) {
760 return x.tile == y.tile && x.ingress == y.ingress && x.egress == y.egress;
764 return a.portConnection.op == b.portConnection.op &&
765 a.portConnection.port == b.portConnection.port;
767 SmallVector<PacketConnection> paths;
770 return emitVias ? samePath(connection, path) : sameDest(connection, path);
772 if (it != paths.end()) {
773 return static_cast<unsigned>(it - paths.begin());
775 paths.push_back(connection);
776 return static_cast<unsigned>(paths.size() - 1);
785 std::map<SmallVector<unsigned>, SmallVector<int>> idsByDests;
786 std::map<std::pair<int, unsigned>, SmallVector<Operation *, 8>> opsTo;
787 for (
int id = 0;
id <= idMask; ++id) {
788 SmallVector<unsigned> reached;
793 unsigned path = pathIndex(c);
794 if (!llvm::is_contained(reached, path)) {
795 reached.push_back(path);
797 SmallVector<Operation *, 8> &ops = opsTo[{id, path}];
798 for (Operation *op : c.usedOps) {
799 if (!llvm::is_contained(ops, op)) {
804 if (!reached.empty()) {
806 idsByDests[reached].push_back(
id);
811 auto disjointCubes = [&](ArrayRef<int> ids) {
812 llvm::SmallBitVector left(idMask + 1);
816 SmallVector<MaskValue> cubes;
818 MaskValue best = {idMask, left.find_first()};
820 for (
int mask = 0; mask <= idMask; ++mask) {
821 int size = 1 << llvm::popcount(
static_cast<unsigned>(idMask & ~mask));
822 if (size <= bestSize) {
825 for (
int value = 0; value <= idMask && size > bestSize; ++value) {
826 if ((value & mask) != value) {
830 for (
int id = value;
id <= idMask && inside; ++id) {
831 inside = (
id & mask) != value || left.test(
id);
834 best = {mask, value};
839 for (
int id = 0;
id <= idMask; ++id) {
840 if ((
id & best.mask) == best.value) {
844 cubes.push_back(best);
850 SmallVector<std::pair<const SmallVector<unsigned> *, ArrayRef<int>>> groups;
851 for (
const auto &[reached, ids] : idsByDests) {
852 groups.push_back({&reached, ids});
854 llvm::sort(groups, [](
const auto &a,
const auto &b) {
855 return a.second.front() < b.second.front();
857 for (
const auto &[reached, ids] : groups) {
858 SmallVector<MaskValue> cubes = disjointCubes(ids);
859 for (
unsigned path : *reached) {
861 SmallVector<Operation *, 8> ops;
863 if ((
id & cube.mask) != cube.value) {
866 for (Operation *op : opsTo[{id, path}]) {
867 if (!llvm::is_contained(ops, op)) {
873 {paths[path].portConnection, cube, paths[path].vias, ops,
true});
881 OpBuilder &rewriter,
bool keepPartialFlows,
884 Operation *Op = op.getOperation();
885 rewriter.setInsertionPoint(Op->getBlock()->getTerminator());
887 std::vector bundles = {WireBundle::Core, WireBundle::DMA};
888 for (WireBundle bundle : bundles) {
889 LLVM_DEBUG(llvm::dbgs()
890 << op << stringifyWireBundle(bundle) <<
" has "
891 << op.getNumSourceConnections(bundle) <<
" Connections\n");
892 for (
size_t i = 0; i < op.getNumSourceConnections(bundle); i++) {
893 Port port = {bundle, (int)i};
894 std::vector<PacketConnection> tiles = exactPacketEndpoints(
897 return analysis.getConnectedTiles(op, port, keepPartialFlows,
901 LLVM_DEBUG(llvm::dbgs() << tiles.size() <<
" Flows\n");
902 emitFlows(rewriter, Op->getLoc(), Op->getResult(0), bundle, (
int)i, tiles,
903 emitVias,
false, idMask, seen, lifted);
914static void findFlowsFromInterconnect(Operation *switchOp,
917 bool keepPartialFlows,
bool emitVias,
920 Region *connections =
nullptr;
921 if (
auto sb = dyn_cast<SwitchboxOp>(switchOp)) {
922 connections = &sb.getConnections();
923 }
else if (
auto sm = dyn_cast<ShimMuxOp>(switchOp)) {
924 connections = &sm.getConnections();
929 rewriter.setInsertionPoint(switchOp->getBlock()->getTerminator());
932 llvm::SmallVector<Port, 8> sourcePorts;
933 auto addPort = [&](
Port p) {
934 if (!llvm::is_contained(sourcePorts, p)) {
935 sourcePorts.push_back(p);
938 Block &b = connections->front();
939 for (
auto connectOp : b.getOps<ConnectOp>()) {
940 addPort(connectOp.sourcePort());
942 for (
auto rulesOp : b.getOps<PacketRulesOp>()) {
943 addPort(rulesOp.sourcePort());
946 for (
Port p : sourcePorts) {
948 WireBundle srcBundle = p.bundle;
949 int srcChannel = p.channel;
950 if (
auto up = analysis.
upstreamOf(switchOp, p)) {
951 Operation *upOp = up->op;
952 Port upPort = up->port;
956 if (upPort.bundle == WireBundle::Core ||
957 upPort.bundle == WireBundle::DMA) {
960 srcTile = resolveEndpointTile(upOp);
961 srcBundle = upPort.bundle;
962 srcChannel = upPort.channel;
963 }
else if (analysis.
drivesPort(upOp, upPort)) {
968 srcTile = resolveEndpointTile(switchOp);
972 srcTile = resolveEndpointTile(switchOp);
977 std::vector<PacketConnection> tiles = exactPacketEndpoints(
981 return analysis.getConnectedTilesFromInput(switchOp, p,
982 keepPartialFlows, claim);
985 emitFlows(rewriter, switchOp->getLoc(), srcTile, srcBundle, srcChannel,
986 tiles, emitVias,
true, idMask, seen, lifted);
993 registry.insert<func::FuncDialect>();
994 registry.insert<AIEDialect>();
1000 Block &b = connections.front();
1001 return b.getOps<ConnectOp>().empty() && b.getOps<PacketRulesOp>().empty() &&
1002 b.getOps<MasterSetOp>().empty() && b.getOps<AMSelOp>().empty();
1007 DeviceOp d = getOperation();
1008 ModuleOp module = d->getParentOfType<ModuleOp>();
1009 if (d.getSymNameAttr() &&
1010 llvm::any_of(module.getOps<DeviceOp>(), [&](DeviceOp user) {
1011 return user.getOverlayAttr() && user.getOverlayAttr().getValue() ==
1012 d.getSymNameAttr().getValue();
1016 d.getTargetModel().validate();
1022 const int idMask = d.getTargetModel().getPacketIdMask();
1025 if (
auto ref = d.getOverlayAttr()) {
1026 if (
auto overlay = module.lookupSymbol<DeviceOp>(ref.getValue())) {
1027 std::set<std::pair<TileID, Port>> outputs;
1028 auto output = [](Operation &op) -> std::optional<Port> {
1029 if (
auto connect = dyn_cast<ConnectOp>(op))
1030 return connect.destPort();
1031 if (
auto master = dyn_cast<MasterSetOp>(op))
1032 return master.destPort();
1033 return std::nullopt;
1035 for (
auto box : overlay.getOps<SwitchboxOp>())
1036 for (Operation &op : box.getConnections().front())
1037 if (
auto port = output(op))
1038 outputs.emplace(box.getTileOp().getTileID(), *port);
1039 for (
auto box : d.getOps<SwitchboxOp>())
1040 for (Operation &op : box.getConnections().front())
1041 if (
auto port = output(op))
1042 if (outputs.count({box.getTileOp().getTileID(), *port}))
1043 lifted.
fixed.insert(&op);
1048 OpBuilder builder = OpBuilder::atBlockTerminator(d.getBody());
1049 for (
auto tile : d.getOps<TileOp>()) {
1050 findFlowsFrom(tile, analysis, builder, clKeepPartialFlows, clEmitVias,
1051 idMask, seen, lifted);
1055 if (clKeepPartialFlows) {
1056 for (
auto switchOp : d.getOps<SwitchboxOp>()) {
1057 findFlowsFromInterconnect(switchOp, analysis, builder,
1058 clKeepPartialFlows, clEmitVias, idMask, seen,
1061 for (
auto shimMuxOp : d.getOps<ShimMuxOp>()) {
1062 findFlowsFromInterconnect(shimMuxOp, analysis, builder,
1063 clKeepPartialFlows, clEmitVias, idMask, seen,
1069 builder.setInsertionPoint(d.getBody()->getTerminator());
1072 Value srcTile = resolveEndpointTile(seed.
op);
1076 std::vector<PacketConnection> tiles =
1078 clKeepPartialFlows);
1079 emitFlows(builder, seed.
op->getLoc(), srcTile, seed.
ingress.bundle,
1080 seed.
ingress.channel, tiles, clEmitVias,
1081 false, idMask, seen, lifted);
1083 llvm::DenseSet<std::pair<Operation *, int>> seeded;
1084 bool progress =
true;
1087 llvm::SmallVector<std::pair<Operation *, int>> snapshot(
1090 for (
auto &seed : snapshot) {
1091 if (!seeded.insert(seed).second) {
1095 Operation *switchOp = seed.first;
1097 Value srcTile = resolveEndpointTile(switchOp);
1101 std::vector<PacketConnection> tiles =
1103 clKeepPartialFlows);
1104 emitFlows(builder, switchOp->getLoc(), srcTile, egress.bundle,
1105 egress.channel, tiles, clEmitVias,
true,
1106 idMask, seen, lifted);
1110 for (
const auto &[switchOp, encodedEgress,
id] :
1113 Value srcTile = resolveEndpointTile(switchOp);
1116 std::vector<PacketConnection> tiles =
1118 switchOp, egress, clKeepPartialFlows, {idMask,
id});
1119 emitFlows(builder, switchOp->getLoc(), srcTile, egress.bundle,
1120 egress.channel, tiles, clEmitVias,
1121 true, idMask, seen, lifted);
1125 if (!clRemoveLifted) {
1135 for (
bool changed =
true; changed;) {
1137 for (
auto &[flow, usedOps] : lifted.
packetFlows) {
1138 if (!flow || llvm::none_of(usedOps, [&](Operation *op) {
1139 return isa_and_nonnull<PacketRuleOp>(op) &&
1140 lifted.
kept.contains(op);
1144 for (Operation *op : usedOps) {
1146 lifted.
kept.insert(op);
1154 for (Operation *op : lifted.
consumed) {
1155 if (isa<ConnectOp, PacketRuleOp, MasterSetOp>(op) &&
1156 !lifted.
kept.contains(op)) {
1160 AIEDialect::IsCtrlPktOverlayAttrHelper overlay(&getContext());
1161 auto cleanupInterconnect = [&](Region &connections) {
1163 llvm::make_early_inc_range(connections.getOps<AMSelOp>())) {
1164 if (amselOp.use_empty() && !overlay.isAttrPresent(amselOp)) {
1169 llvm::make_early_inc_range(connections.getOps<PacketRulesOp>())) {
1170 if (rulesOp.getRules().front().getOps<PacketRuleOp>().empty()) {
1175 for (
auto switchOp : d.getOps<SwitchboxOp>()) {
1176 cleanupInterconnect(switchOp.getConnections());
1178 for (
auto shimMuxOp : d.getOps<ShimMuxOp>()) {
1179 cleanupInterconnect(shimMuxOp.getConnections());
1185 llvm::DenseSet<Operation *> retained;
1186 auto retainNonEmpty = [&](Operation *op, Region &connections) {
1188 retained.insert(op);
1191 for (
auto switchOp : d.getOps<SwitchboxOp>()) {
1192 retainNonEmpty(switchOp, switchOp.getConnections());
1194 for (
auto shimMuxOp : d.getOps<ShimMuxOp>()) {
1195 retainNonEmpty(shimMuxOp, shimMuxOp.getConnections());
1198 llvm::DenseSet<Operation *> wiredToRetained;
1199 for (
auto wireOp : llvm::make_early_inc_range(d.getOps<WireOp>())) {
1200 Operation *src = wireOp.getSource().getDefiningOp();
1201 Operation *dst = wireOp.getDest().getDefiningOp();
1202 if (!retained.contains(src) && !retained.contains(dst)) {
1206 wiredToRetained.insert(src);
1207 wiredToRetained.insert(dst);
1212 auto eraseIfUnused = [&](Operation *op, Region &connections) {
1215 for (
auto switchOp : llvm::make_early_inc_range(d.getOps<SwitchboxOp>())) {
1216 if (eraseIfUnused(switchOp, switchOp.getConnections())) {
1220 for (
auto shimMuxOp : llvm::make_early_inc_range(d.getOps<ShimMuxOp>())) {
1221 if (eraseIfUnused(shimMuxOp, shimMuxOp.getConnections())) {
1229 return std::make_unique<AIEFindFlowsPass>();
std::tuple< int, int, int, int, int, int, int, int, int, int > FlowKey
struct PortMaskValue { Port port; MaskValue mv; llvm::SmallVector< Operation *, 3 > ops;} PortMaskValue
struct MaskValue { int mask; int value;} MaskValue
std::set< FlowKey > FlowKeySet
struct PacketConnection { PortConnection portConnection; MaskValue mv; llvm::SmallVector< Via, 4 > vias; llvm::SmallVector< Operation *, 8 > usedOps; bool isPacket=false;} PacketConnection
struct PortConnection { Operation *op; Port port;} PortConnection
std::vector< PacketConnection > getConnectedTilesFromEgress(Operation *switchOp, Port egressPort, bool keepPartialFlows, MaskValue claim={0, 0}) const
std::set< std::tuple< Operation *, int, int > > & getPacketMergeEgresses()
std::optional< PortConnection > upstreamOf(Operation *op, Port port) const
void enableSectionSplitting()
static Port decodePort(int e)
std::vector< PacketConnection > getConnectedTilesFromCircuitFanout(const CircuitFanoutSeed &seed, bool keepPartialFlows) const
std::vector< PacketConnection > getConnectedTilesFromInput(Operation *switchOp, Port inputPort, bool keepPartialFlows, MaskValue claim={0, 0}) const
const llvm::DenseSet< Operation * > & getPacketMergeOps() const
llvm::SmallVector< CircuitFanoutSeed, 8 > & getCircuitFanoutSeeds()
llvm::DenseSet< std::pair< Operation *, int > > & getFanoutEgressSeeds()
bool drivesPort(Operation *op, Port port) const
std::vector< PacketConnection > traverse(std::vector< PacketConnection > worklist, bool keepPartialFlows) const
std::vector< PacketConnection > getConnectedTiles(TileOp tileOp, Port port, bool keepPartialFlows, MaskValue claim={0, 0}) const
ConnectivityAnalysis(DeviceOp &d)
std::unique_ptr< mlir::OperationPass< DeviceOp > > createAIEFindFlowsPass()
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
void getDependentDialects(DialectRegistry ®istry) const override
void runOnOperation() override
static bool isEmptyInterconnect(Region &connections)
llvm::SmallVector< Operation *, 3 > ops
llvm::DenseSet< Operation * > kept
llvm::DenseSet< Operation * > fixed
std::vector< std::pair< PacketFlowOp, SmallVector< Operation *, 8 > > > packetFlows
llvm::DenseSet< Operation * > consumed