MLIR-AIE 1.4.6.dev
AIEStructuralRank.cpp
Go to the documentation of this file.
1//===- AIEStructuralRank.cpp ------------------------------------*- C++ -*-===//
2//
3// Copyright (C) 2026 Advanced Micro Devices, Inc.
4// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
5//
6//===----------------------------------------------------------------------===//
7
9
10#include "mlir/IR/SymbolTable.h"
11
12#include <map>
13
14using namespace mlir;
15using namespace xilinx;
16using namespace xilinx::AIE;
17
18static bool isSymbolReference(Attribute value) {
19 auto array = dyn_cast<ArrayAttr>(value);
20 return isa<SymbolRefAttr>(value) ||
21 (array && llvm::all_of(array, llvm::IsaPred<SymbolRefAttr>));
22}
23
24/// An op's name and attributes. Symbol names and references are left out:
25/// what a reference names enters through a link instead, and a fifo name
26/// only says whether there is one. A consumed_by proof is left out too, so
27/// whether verification ran never moves a channel.
28static void describe(Operation *op, llvm::raw_ostream &os) {
29 os << op->getName();
30 for (NamedAttribute attr : op->getAttrs()) {
31 if (isSymbolReference(attr.getValue()) ||
32 attr.getName() == SymbolTable::getSymbolAttrName() ||
33 attr.getName() == "consumed_by")
34 continue;
35 os << ' ' << attr.getName();
36 if (attr.getName() != "fifoName")
37 os << '=' << attr.getValue();
38 }
39}
40
41std::string &StructuralGraph::add(Operation *op) {
42 nodes.push_back(op);
43 llvm::raw_string_ostream os(features[op]);
44 describe(op, os);
45 return features[op];
46}
47
48void StructuralGraph::link(Operation *from, Operation *to, StringRef label) {
49 links[from].push_back({label.str(), to});
50 links[to].push_back({(label + "~").str(), from});
51}
52
53DenseMap<Operation *, unsigned> StructuralGraph::rank() const {
54 DenseMap<Operation *, unsigned> rank;
55 unsigned classes = 0;
56 auto rerank = [&](auto &signature) {
57 SmallVector<Operation *> order(nodes);
58 llvm::stable_sort(order, [&](Operation *a, Operation *b) {
59 return signature.at(a) < signature.at(b);
60 });
61 classes = 0;
62 for (auto [index, op] : llvm::enumerate(order)) {
63 if (index && signature.at(order[index - 1]) < signature.at(op))
64 ++classes;
65 rank[op] = classes;
66 }
67 ++classes;
68 };
69 std::map<Operation *, std::string> initial;
70 for (Operation *op : nodes)
71 initial[op] = features.lookup(op);
72 rerank(initial);
73 for (unsigned previous = 0; classes != previous;) {
74 previous = classes;
75 std::map<Operation *,
76 std::pair<unsigned, SmallVector<std::pair<std::string, unsigned>>>>
77 signature;
78 for (Operation *op : nodes) {
79 auto &[own, around] = signature[op];
80 own = rank[op];
81 for (const auto &[label, other] : links.lookup(op))
82 around.push_back({label, rank[other]});
83 llvm::sort(around);
84 }
85 rerank(signature);
86 }
87 return rank;
88}
89
91 StructuralGraph graph;
92 // Where each nested op sits in its top-level op, for links into it.
93 DenseMap<Operation *, std::pair<Operation *, unsigned>> position;
94 for (Operation &op : device.getBody()->without_terminator()) {
95 if (isa<RuntimeSequenceOp>(op))
96 continue;
97 llvm::raw_string_ostream os(graph.add(&op));
98 unsigned index = 0;
99 op.walk<WalkOrder::PreOrder>([&](Operation *nested) {
100 position[nested] = {&op, index++};
101 if (nested != &op) {
102 os << " {";
103 describe(nested, os);
104 os << '}';
105 }
106 });
107 }
108 for (Operation *node : SmallVector<Operation *>(graph.nodes)) {
109 node->walk<WalkOrder::PreOrder>([&](Operation *nested) {
110 std::string at = std::to_string(position.lookup(nested).second);
111 for (auto [index, operand] : llvm::enumerate(nested->getOperands())) {
112 Operation *def = operand.getDefiningOp();
113 if (def && def->getParentOp() == device && graph.features.count(def))
114 graph.link(node, def, at + ":" + std::to_string(index));
115 }
116 for (NamedAttribute attr : nested->getAttrs()) {
117 if (!isSymbolReference(attr.getValue()))
118 continue;
119 SmallVector<SymbolRefAttr> refs;
120 if (auto ref = dyn_cast<SymbolRefAttr>(attr.getValue()))
121 refs.push_back(ref);
122 else
123 llvm::append_range(
124 refs,
125 cast<ArrayAttr>(attr.getValue()).getAsRange<SymbolRefAttr>());
126 for (auto [index, ref] : llvm::enumerate(refs)) {
127 auto it =
128 position.find(SymbolTable::lookupNearestSymbolFrom(nested, ref));
129 if (it == position.end())
130 continue;
131 auto [target, within] = it->second;
132 graph.link(node, target,
133 at + ":" + attr.getName().str() + ":" +
134 std::to_string(index) + "@" + std::to_string(within));
135 }
136 }
137 });
138 }
139 return graph;
140}
141
142StructuralGraph StructuralGraph::of(ModuleOp module) {
143 StructuralGraph graph;
144 for (DeviceOp device : module.getOps<DeviceOp>()) {
145 StructuralGraph own = of(device);
146 graph.add(device);
147 for (Operation *node : own.nodes) {
148 graph.nodes.push_back(node);
149 graph.features[node] = std::move(own.features[node]);
150 graph.link(device, node, "holds");
151 }
152 for (auto &[op, links] : own.links)
153 llvm::append_range(graph.links[op], links);
154 }
155 return graph;
156}
Ops and the labelled links between them, for ranking them by structure where a pass would otherwise f...
void link(mlir::Operation *from, mlir::Operation *to, llvm::StringRef label)
Link from to to under label, and to back to from.
llvm::SmallVector< mlir::Operation * > nodes
std::string & add(mlir::Operation *op)
Add op as a node whose features are its name and attributes, symbol names and references left out.
llvm::DenseMap< mlir::Operation *, unsigned > rank() const
Rank the nodes by their features and then, a round at a time until no class splits,...
llvm::DenseMap< mlir::Operation *, std::string > features
What each node is, before anything it links to is considered.
static StructuralGraph of(DeviceOp device)
The ops directly in device but its runtime sequences, each with the ops nested in it,...
llvm::DenseMap< mlir::Operation *, llvm::SmallVector< std::pair< std::string, mlir::Operation * > > > links