10#include "mlir/IR/BuiltinOps.h"
11#include "mlir/IR/Threading.h"
14using 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 for (
auto targetNameAttr : instanceOp.getReferencedModuleNamesAttr()) {
83 auto *targetNode = getOrAddNode(cast<StringAttr>(targetNameAttr));
84 currentNode->addInstance(instanceOp, targetNode);
91 assert(!
nodeMap.count(module.getModuleNameAttr()) &&
"module already added");
93 node->module =
module;
94 nodeMap[
module.getModuleNameAttr()] = node;
95 nodes.push_back(node);
101 "all instances of this module must have been erased.");
103 for (
auto *instance :
llvm::make_early_inc_range(*node))
117 InstanceOpInterface newInst) {
118 assert(inst.getReferencedModuleNamesAttr() ==
119 newInst.getReferencedModuleNamesAttr() &&
120 "Both instances must be targeting the same modules");
123 for (Attribute targetNameAttr : inst.getReferencedModuleNamesAttr()) {
125 auto *node =
lookup(cast<StringAttr>(targetNameAttr));
127 if (record->getInstance() == inst) {
130 record->instance = newInst;
137 ModuleOpInterface child, ModuleOpInterface parent,
139 DenseSet<InstanceGraphNode *> seen;
140 SmallVector<InstanceGraphNode *> worklist;
142 worklist.push_back(cn);
144 while (!worklist.empty()) {
145 auto *node = worklist.back();
149 for (
auto *use : node->
uses()) {
150 if (skipInstance(use))
152 auto *mod = use->getParent();
153 if (!seen.count(mod)) {
155 worklist.push_back(mod);
162FailureOr<llvm::ArrayRef<InstanceGraphNode *>>
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, {});
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");
221 candidateTopLevels.begin(), candidateTopLevels.end());
227ArrayRef<InstancePath>
232ArrayRef<InstancePath>
251 auto cached = cache.find(op);
252 if (cached != cache.end())
253 return cached->second;
257 SmallVector<InstancePath, 8> extendedPaths;
258 for (
auto *inst : node->
uses()) {
259 if (
auto module = inst->getParent()->getModule()) {
260 auto instPaths =
getPaths(module, top, cache);
261 extendedPaths.reserve(instPaths.size());
262 for (
auto path : instPaths) {
264 path, cast<InstanceOpInterface>(*inst->getInstance())));
266 }
else if (inst->getParent() == top) {
269 extendedPaths.emplace_back(
empty);
274 ArrayRef<InstancePath> pathList;
275 if (!extendedPaths.empty()) {
277 std::copy(extendedPaths.begin(), extendedPaths.end(), paths);
278 pathList = ArrayRef<InstancePath>(paths, extendedPaths.size());
280 cache.insert({op, pathList});
287 for (
unsigned i = 0, n =
path.size(); i < n; ++i) {
290 into <<
"/" << inst.getInstanceName() <<
":";
291 auto names = inst.getReferencedModuleNamesAttr();
292 if (names.size() == 1) {
294 into << cast<StringAttr>(names[0]).getValue();
300 ->getParentOfType<ModuleOpInterface>()
305 llvm::interleaveComma(names, into, [&](Attribute name) {
306 into << cast<StringAttr>(name).getValue();
315 InstanceOpInterface inst) {
316 size_t n = path.
size() + 1;
317 auto *newPath =
allocator.Allocate<InstanceOpInterface>(n);
318 std::copy(path.
begin(), path.
end(), newPath);
319 newPath[path.
size()] = inst;
325 size_t n = path.
size() + 1;
326 auto *newPath =
allocator.Allocate<InstanceOpInterface>(n);
327 std::copy(path.
begin(), path.
end(), newPath + 1);
333 InstanceOpInterface newOp) {
340 auto instanceExists = [&](
const ArrayRef<InstancePath> &paths) ->
bool {
342 paths, [&](
InstancePath p) {
return llvm::is_contained(p, oldOp); });
345 for (
auto &iter : cache) {
346 if (!instanceExists(iter.getSecond()))
348 SmallVector<InstancePath, 8> updatedPaths;
349 for (
auto path : iter.getSecond()) {
350 const auto *iter = llvm::find(path, oldOp);
351 if (iter == path.end()) {
353 updatedPaths.push_back(path);
356 auto *newPath =
allocator.Allocate<InstanceOpInterface>(path.size());
357 llvm::copy(path, newPath);
358 newPath[iter - path.begin()] = newOp;
359 updatedPaths.push_back(
InstancePath(ArrayRef(newPath, path.size())));
364 llvm::copy(updatedPaths, paths);
365 iter.getSecond() = ArrayRef<InstancePath>(paths, updatedPaths.size());
370 updateCache(iter.getSecond());
373#include "circt/Support/InstanceGraphInterface.cpp.inc"
assert(baseType &&"element must be base type")
static InstancePath empty
This is a Node in the InstanceGraph.
llvm::iterator_range< UseIterator > uses()
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.
ModuleOpInterface InstanceList instances
The module.
void recordUse(InstanceRecord *record)
Record that a module instantiates this module.
InstanceGraphNode * lookupOrNull(StringAttr name)
Lookup an module by name.
Operation * getParent()
Return the parent under which all nodes are nested.
virtual InstanceGraphNode * addModule(ModuleOpInterface module)
Add a newly created module to the instance graph.
Operation * parent
The node under which all modules are nested.
llvm::DenseMap< Attribute, InstanceGraphNode * > nodeMap
This maps each operation to its graph node.
virtual void replaceInstance(InstanceOpInterface inst, InstanceOpInterface newInst)
Replaces an instance of a module with another instance.
virtual InstanceGraphNode * getTopLevelNode()
Get the node corresponding to the top-level module of a circuit.
FailureOr< llvm::ArrayRef< InstanceGraphNode * > > getInferredTopLevelNodes()
Get the nodes corresponding to the inferred top-level modules of a circuit.
llvm::SmallVector< InstanceGraphNode * > inferredTopLevelNodes
A caching of the inferred top level module(s).
NodeList nodes
The storage for graph nodes, with deterministic iteration.
virtual void erase(InstanceGraphNode *node)
Remove this module from the instance graph.
InstanceGraphNode * lookup(ModuleOpInterface op)
Look up an InstanceGraphNode for a module.
bool isAncestor(ModuleOpInterface child, ModuleOpInterface parent, llvm::function_ref< bool(InstanceRecord *)> skipInstance=[](InstanceRecord *_) { return false;})
Check if child is instantiated by a parent.
InstanceGraphNode * getOrAddNode(StringAttr name)
Get the node corresponding to the module.
InstanceGraph(Operation *parent)
Create a new module graph of a circuit.
An instance path composed of a series of instances.
ArrayRef< InstanceOpInterface > path
void print(llvm::raw_ostream &into) const
Print the path to any stream-like object.
ArrayRef< InstanceOpInterface >::iterator begin() const
ArrayRef< InstanceOpInterface >::iterator end() const
This is an edge in the InstanceGraph.
InstanceGraphNode * getParent() const
Get the module where the instantiation lives.
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.
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
ArrayRef< InstancePath > getPaths(ModuleOpInterface op, InstanceGraphNode *top, PathsCache &cache)
DenseMap< Operation *, ArrayRef< InstancePath > > PathsCache
ArrayRef< InstancePath > getAbsolutePaths(ModuleOpInterface op)
ArrayRef< InstancePath > getRelativePaths(ModuleOpInterface op, InstanceGraphNode *node)
DenseMap< InstanceGraphNode *, PathsCache > relativePathsCache
Cached relative instance paths.
void replaceInstance(InstanceOpInterface oldOp, InstanceOpInterface newOp)
Replace an InstanceOp. This is required to keep the cache updated.
InstancePath prependInstance(InstanceOpInterface inst, InstancePath path)
Prepend an instance to a path.
InstancePath appendInstance(InstancePath path, InstanceOpInterface inst)
Append an instance to a path.
llvm::BumpPtrAllocator allocator
An allocator for individual instance paths and entire path lists.
InstanceGraph & instanceGraph
The instance graph of the IR.
PathsCache absolutePathsCache
Cached absolute instance paths.