10 #include "mlir/IR/BuiltinOps.h"
11 #include "mlir/IR/Threading.h"
13 using namespace circt;
14 using namespace igraph;
33 return instanceRecord;
49 nodes.push_back(node);
56 "top-level operation must have a single block");
57 SmallVector<std::pair<ModuleOpInterface, SmallVector<InstanceOpInterface>>>
61 parent->getRegion(0).front().getOps<igraph::ModuleOpInterface>())
62 moduleToInstances.push_back({module, {}});
65 mlir::parallelFor(
parent->getContext(), 0, moduleToInstances.size(),
67 auto module = moduleToInstances[idx].first;
68 auto &instances = moduleToInstances[idx].second;
70 module.walk([&](InstanceOpInterface instanceOp) {
71 instances.push_back(instanceOp);
76 for (
auto &[module, instances] : moduleToInstances) {
77 auto name = module.getModuleNameAttr();
78 auto *currentNode = getOrAddNode(name);
79 currentNode->module = module;
80 for (
auto instanceOp : instances) {
82 auto *targetNode = getOrAddNode(instanceOp.getReferencedModuleNameAttr());
83 currentNode->addInstance(instanceOp, targetNode);
89 assert(!nodeMap.count(module.getModuleNameAttr()) &&
"module already added");
91 node->module = module;
92 nodeMap[module.getModuleNameAttr()] = node;
93 nodes.push_back(node);
99 "all instances of this module must have been erased.");
101 for (
auto *instance : llvm::make_early_inc_range(*node))
103 nodeMap.erase(node->
getModule().getModuleNameAttr());
108 auto it = nodeMap.find(name);
109 assert(it != nodeMap.end() &&
"Module not in InstanceGraph!");
114 return lookup(cast<ModuleOpInterface>(op).getModuleNameAttr());
118 InstanceGraph::getReferencedModuleImpl(InstanceOpInterface op) {
119 return lookup(op.getReferencedModuleNameAttr())->getModule();
122 void InstanceGraph::replaceInstance(InstanceOpInterface inst,
123 InstanceOpInterface newInst) {
124 assert(inst.getReferencedModuleName() == newInst.getReferencedModuleName() &&
125 "Both instances must be targeting the same module");
128 auto *node = lookup(inst.getReferencedModuleNameAttr());
129 auto it = llvm::find_if(node->uses(), [&](
InstanceRecord *record) {
130 return record->getInstance() == inst;
132 assert(it != node->usesEnd() &&
"Instance of module not recorded in graph");
136 (*it)->instance = newInst;
139 bool InstanceGraph::isAncestor(ModuleOpInterface child,
140 ModuleOpInterface parent) {
141 DenseSet<InstanceGraphNode *> seen;
142 SmallVector<InstanceGraphNode *> worklist;
143 auto *cn = lookup(child);
144 worklist.push_back(cn);
146 while (!worklist.empty()) {
147 auto *node = worklist.back();
149 if (node->getModule() == parent)
151 for (
auto *use : node->uses()) {
152 auto *mod = use->getParent();
153 if (!seen.count(mod)) {
155 worklist.push_back(mod);
163 InstanceGraph::getInferredTopLevelNodes() {
164 if (!inferredTopLevelNodes.empty())
165 return {inferredTopLevelNodes};
168 llvm::SetVector<InstanceGraphNode *> visited, marked;
169 llvm::SetVector<InstanceGraphNode *> candidateTopLevels(this->begin(),
171 SmallVector<InstanceGraphNode *> cycleTrace;
177 if (visited.contains(node))
179 trace.push_back(node);
180 if (marked.contains(node)) {
186 for (
auto use : *node) {
188 candidateTopLevels.remove(targetModule);
189 if (cycleUtil(targetModule, trace))
193 visited.insert(node);
198 for (
auto moduleIt : *
this) {
199 if (visited.contains(moduleIt))
202 cyclic |= cycleUtil(moduleIt, {});
208 auto err = getParent()->emitOpError();
209 err <<
"cannot deduce top level module - cycle "
210 "detected in instance graph (";
213 [&](
auto node) { err << node->
getModule().getModuleName(); },
"->");
217 assert(!candidateTopLevels.empty() &&
218 "if non-cyclic, there should be at least 1 candidate top level");
220 inferredTopLevelNodes = llvm::SmallVector<InstanceGraphNode *>(
221 candidateTopLevels.begin(), candidateTopLevels.end());
222 return {inferredTopLevelNodes};
228 ArrayRef<InstancePath>
229 InstancePathCache::getAbsolutePaths(ModuleOpInterface op) {
232 if (node == instanceGraph.getTopLevelNode()) {
237 auto cached = absolutePathsCache.find(op);
238 if (cached != absolutePathsCache.end())
239 return cached->second;
243 SmallVector<InstancePath, 8> extendedPaths;
244 for (
auto *inst : node->
uses()) {
245 if (
auto module = inst->getParent()->getModule()) {
246 auto instPaths = getAbsolutePaths(module);
247 extendedPaths.reserve(instPaths.size());
248 for (
auto path : instPaths) {
249 extendedPaths.push_back(appendInstance(
250 path, cast<InstanceOpInterface>(*inst->getInstance())));
253 extendedPaths.emplace_back(
empty);
258 ArrayRef<InstancePath> pathList;
259 if (!extendedPaths.empty()) {
260 auto *paths = allocator.Allocate<
InstancePath>(extendedPaths.size());
261 std::copy(extendedPaths.begin(), extendedPaths.end(), paths);
262 pathList = ArrayRef<InstancePath>(paths, extendedPaths.size());
264 absolutePathsCache.insert({op, pathList});
270 InstanceOpInterface inst) {
271 size_t n = path.
size() + 1;
272 auto *newPath = allocator.Allocate<InstanceOpInterface>(n);
273 std::copy(path.
begin(), path.
end(), newPath);
274 newPath[path.
size()] = inst;
278 InstancePath InstancePathCache::prependInstance(InstanceOpInterface inst,
280 size_t n = path.
size() + 1;
281 auto *newPath = allocator.Allocate<InstanceOpInterface>(n);
282 std::copy(path.
begin(), path.
end(), newPath + 1);
287 void InstancePathCache::replaceInstance(InstanceOpInterface oldOp,
288 InstanceOpInterface newOp) {
290 instanceGraph.replaceInstance(oldOp, newOp);
295 auto instanceExists = [&](
const ArrayRef<InstancePath> &paths) ->
bool {
297 paths, [&](
InstancePath p) {
return llvm::is_contained(p, oldOp); });
300 for (
auto &iter : absolutePathsCache) {
301 if (!instanceExists(iter.getSecond()))
303 SmallVector<InstancePath, 8> updatedPaths;
304 for (
auto path : iter.getSecond()) {
305 const auto *iter = llvm::find(path, oldOp);
306 if (iter == path.end()) {
308 updatedPaths.push_back(path);
311 auto *newPath = allocator.Allocate<InstanceOpInterface>(path.size());
312 llvm::copy(path, newPath);
313 newPath[iter - path.begin()] = newOp;
314 updatedPaths.push_back(
InstancePath(ArrayRef(newPath, path.size())));
318 auto *paths = allocator.Allocate<
InstancePath>(updatedPaths.size());
319 llvm::copy(updatedPaths, paths);
320 iter.getSecond() = ArrayRef<InstancePath>(paths, updatedPaths.size());
324 #include "circt/Support/InstanceGraphInterface.cpp.inc"
assert(baseType &&"element must be base type")
static InstancePath empty
This is a Node in the InstanceGraph.
friend class InstanceRecord
InstanceRecord * firstUse
List of instances which instantiate this module.
bool noUses()
Return true if there are no more instances of this module.
InstanceRecord * addInstance(InstanceOpInterface instance, InstanceGraphNode *target)
Record a new instance op in the body of this module.
auto getModule()
Get the module that this node is tracking.
InstanceList instances
List of instance operations in this module.
llvm::iterator_range< UseIterator > uses()
void recordUse(InstanceRecord *record)
Record that a module instantiates this module.
Operation * parent
The node under which all modules are nested.
llvm::DenseMap< Attribute, InstanceGraphNode * > nodeMap
This maps each operation to its graph node.
InstanceGraph(Operation *parent)
Create a new module graph of a circuit.
NodeList nodes
The storage for graph nodes, with deterministic iteration.
InstanceGraphNode * getOrAddNode(StringAttr name)
Get the node corresponding to the module.
An instance path composed of a series of instances.
ArrayRef< InstanceOpInterface >::iterator end() const
ArrayRef< InstanceOpInterface >::iterator begin() const
This is an edge in the InstanceGraph.
void erase()
Erase this instance record, removing it from the parent module and the target's use-list.
InstanceGraphNode * target
This is the module which the instance-like is instantiating.
InstanceRecord * nextUse
Intrusive linked list for other uses.
InstanceGraphNode * getParent() const
Get the module where the instantiation lives.
igraph::InstanceGraphNode InstanceGraphNode
This file defines an intermediate representation for circuits acting as an abstraction for constraint...