Loading [MathJax]/extensions/tex2jax.js
CIRCT 21.0.0git
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
InstanceGraph.h
Go to the documentation of this file.
1//===- InstanceGraph.h - Instance graph -------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines a generic instance graph for module- and instance-likes.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef CIRCT_SUPPORT_INSTANCEGRAPH_H
14#define CIRCT_SUPPORT_INSTANCEGRAPH_H
15
16#include "circt/Support/LLVM.h"
17#include "mlir/IR/OpDefinition.h"
18#include "llvm/ADT/GraphTraits.h"
19#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/iterator.h"
21#include "llvm/Support/DOTGraphTraits.h"
22
23/// The InstanceGraph op interface, see InstanceGraphInterface.td for more
24/// details.
26
27namespace circt {
28namespace igraph {
29
30namespace detail {
31/// This just maps a iterator of references to an iterator of addresses.
32template <typename It>
34 : public llvm::mapped_iterator<It, typename It::pointer (*)(
35 typename It::reference)> {
36 // This using statement is to get around a bug in MSVC. Without it, it
37 // tries to look up "It" as a member type of the parent class.
38 using Iterator = It;
39 static typename Iterator::value_type *
40 addrOf(typename Iterator::value_type &v) noexcept {
41 return std::addressof(v);
42 }
43 /* implicit */ AddressIterator(Iterator iterator)
44 : llvm::mapped_iterator<It, typename Iterator::pointer (*)(
45 typename Iterator::reference)>(iterator,
46 addrOf) {}
47};
48} // namespace detail
49
50class InstanceGraphNode;
51
52/// This is an edge in the InstanceGraph. This tracks a specific instantiation
53/// of a module.
55 : public llvm::ilist_node_with_parent<InstanceRecord, InstanceGraphNode> {
56public:
57 /// Get the instance-like op that this is tracking.
58 template <typename TTarget = InstanceOpInterface>
59 auto getInstance() {
60 if constexpr (std::is_same<TTarget, InstanceOpInterface>::value)
61 return instance;
62 return dyn_cast_or_null<TTarget>(instance.getOperation());
63 }
64
65 /// Get the module where the instantiation lives.
66 InstanceGraphNode *getParent() const { return parent; }
67
68 /// Get the module which the instance-like is instantiating.
69 InstanceGraphNode *getTarget() const { return target; }
70
71 /// Erase this instance record, removing it from the parent module and the
72 /// target's use-list.
73 void erase();
74
75private:
76 friend class InstanceGraph;
77 friend class InstanceGraphNode;
78
82 InstanceRecord(const InstanceRecord &) = delete;
83
84 /// This is the module where the instantiation lives.
86
87 /// The InstanceLike that this is tracking.
88 InstanceOpInterface instance;
89
90 /// This is the module which the instance-like is instantiating.
92 /// Intrusive linked list for other uses.
95};
96
97/// This is a Node in the InstanceGraph. Each node represents a Module in a
98/// Circuit. Both external modules and regular modules can be represented by
99/// this class. It is possible to efficiently iterate all modules instantiated
100/// by this module, as well as all instantiations of this module.
101class InstanceGraphNode : public llvm::ilist_node<InstanceGraphNode> {
102 using InstanceList = llvm::iplist<InstanceRecord>;
103
104public:
105 InstanceGraphNode() : module(nullptr) {}
106
107 /// Get the module that this node is tracking.
108 template <typename TTarget = ModuleOpInterface>
109 auto getModule() {
110 if constexpr (std::is_same<TTarget, ModuleOpInterface>::value)
111 return module;
112 return cast<TTarget>(module.getOperation());
113 }
114
115 /// Iterate the instance records in this module.
117 iterator begin() { return instances.begin(); }
118 iterator end() { return instances.end(); }
119
120 /// Return true if there are no more instances of this module.
121 bool noUses() { return !firstUse; }
122
123 /// Return true if this module has exactly one use.
124 bool hasOneUse() { return llvm::hasSingleElement(uses()); }
125
126 /// Get the number of direct instantiations of this module.
127 size_t getNumUses() { return std::distance(usesBegin(), usesEnd()); }
128
129 /// Iterator for module uses.
131 : public llvm::iterator_facade_base<
132 UseIterator, std::forward_iterator_tag, InstanceRecord *> {
133 UseIterator() : current(nullptr) {}
135 InstanceRecord *operator*() const { return current; }
136 using llvm::iterator_facade_base<UseIterator, std::forward_iterator_tag,
137 InstanceRecord *>::operator++;
139 assert(current && "incrementing past end");
141 return *this;
142 }
143 bool operator==(const UseIterator &other) const {
144 return current == other.current;
145 }
146
147 private:
149 };
150
151 /// Iterate the instance records which instantiate this module.
152 UseIterator usesBegin() { return {this}; }
153 UseIterator usesEnd() { return {}; }
154 llvm::iterator_range<UseIterator> uses() {
155 return llvm::make_range(usesBegin(), usesEnd());
156 }
157
158 /// Record a new instance op in the body of this module. Returns a newly
159 /// allocated InstanceRecord which will be owned by this node.
160 InstanceRecord *addInstance(InstanceOpInterface instance,
161 InstanceGraphNode *target);
162
163private:
164 friend class InstanceRecord;
165
167
168 /// Record that a module instantiates this module.
169 void recordUse(InstanceRecord *record);
170
171 /// The module.
172 ModuleOpInterface module;
173
174 /// List of instance operations in this module. This member owns the
175 /// InstanceRecords, which may be pointed to by other InstanceGraphNode's use
176 /// lists.
178
179 /// List of instances which instantiate this module.
181
182 // Provide access to the constructor.
183 friend class InstanceGraph;
184};
185
186/// This graph tracks modules and where they are instantiated. This is intended
187/// to be used as a cached analysis on circuits. This class can be used
188/// to walk the modules efficiently in a bottom-up or top-down order.
189///
190/// To use this class, retrieve a cached copy from the analysis manager:
191/// auto &instanceGraph = getAnalysis<InstanceGraph>(getOperation());
193 /// This is the list of InstanceGraphNodes in the graph.
194 using NodeList = llvm::iplist<InstanceGraphNode>;
195
196public:
197 /// Create a new module graph of a circuit. Must be called on the parent
198 /// operation of ModuleOpInterface ops.
200 InstanceGraph(const InstanceGraph &) = delete;
201 virtual ~InstanceGraph() = default;
202
203 /// Lookup an module by name. Returns null if no module with the given name
204 /// exists in the instance graph.
205 InstanceGraphNode *lookupOrNull(StringAttr name);
206
207 /// Look up an InstanceGraphNode for a module. Returns null if the module has
208 /// not been added to the instance graph.
209 InstanceGraphNode *lookupOrNull(ModuleOpInterface op) {
210 return lookup(op.getModuleNameAttr());
211 }
212
213 /// Look up an InstanceGraphNode for a module. Aborts if the module does not
214 /// exist.
215 InstanceGraphNode *lookup(ModuleOpInterface op) {
216 auto *node = lookupOrNull(op);
217 assert(node != nullptr && "Module not in InstanceGraph!");
218 return node;
219 }
220
221 /// Lookup an module by name. Aborts if the module does not exist.
222 InstanceGraphNode *lookup(StringAttr name) {
223 auto *node = lookupOrNull(name);
224 assert(node != nullptr && "Module not in InstanceGraph!");
225 return node;
226 }
227
228 /// Lookup an InstanceGraphNode for a module.
229 InstanceGraphNode *operator[](ModuleOpInterface op) { return lookup(op); }
230
231 /// Check if child is instantiated by a parent.
232 bool isAncestor(
233 ModuleOpInterface child, ModuleOpInterface parent,
234 llvm::function_ref<bool(InstanceRecord *)> skipInstance =
235 [](InstanceRecord *_) { return false; });
236
237 /// Get the node corresponding to the top-level module of a circuit.
238 virtual InstanceGraphNode *getTopLevelNode() { return nullptr; }
239
240 /// Get the nodes corresponding to the inferred top-level modules of a
241 /// circuit.
242 FailureOr<llvm::ArrayRef<InstanceGraphNode *>> getInferredTopLevelNodes();
243
244 /// Return the parent under which all nodes are nested.
245 Operation *getParent() { return parent; }
246
247 /// Returns pointer to member of operation list.
249 return &InstanceGraph::nodes;
250 }
251
252 /// Iterate through all modules.
254 iterator begin() { return nodes.begin(); }
255 iterator end() { return nodes.end(); }
256
257 //===-------------------------------------------------------------------------
258 // Methods to keep an InstanceGraph up to date.
259 //
260 // These methods are not thread safe. Make sure that modifications are
261 // properly synchronized or performed in a serial context. When the
262 // InstanceGraph is used as an analysis, this is only safe when the pass is
263 // on a CircuitOp or a ModuleOp.
264
265 /// Add a newly created module to the instance graph.
266 virtual InstanceGraphNode *addModule(ModuleOpInterface module);
267
268 /// Remove this module from the instance graph. This will also remove all
269 /// InstanceRecords in this module. All instances of this module must have
270 /// been removed from the graph.
271 virtual void erase(InstanceGraphNode *node);
272
273 /// Replaces an instance of a module with another instance. The target module
274 /// of both InstanceOps must be the same.
275 virtual void replaceInstance(InstanceOpInterface inst,
276 InstanceOpInterface newInst);
277
278protected:
279 ModuleOpInterface getReferencedModuleImpl(InstanceOpInterface op);
280
281 /// Get the node corresponding to the module. If the node has does not exist
282 /// yet, it will be created.
283 InstanceGraphNode *getOrAddNode(StringAttr name);
284
285 /// The node under which all modules are nested.
286 Operation *parent;
287
288 /// The storage for graph nodes, with deterministic iteration.
290
291 /// This maps each operation to its graph node.
292 llvm::DenseMap<Attribute, InstanceGraphNode *> nodeMap;
293
294 /// A caching of the inferred top level module(s).
295 llvm::SmallVector<InstanceGraphNode *> inferredTopLevelNodes;
296};
297
298struct InstancePathCache;
299
300/**
301 * An instance path composed of a series of instances.
302 */
303class InstancePath final {
304public:
305 InstancePath() = default;
306
307 InstanceOpInterface top() const {
308 assert(!empty() && "instance path is empty");
309 return path[0];
310 }
311
312 InstanceOpInterface leaf() const {
313 assert(!empty() && "instance path is empty");
314 return path.back();
315 }
316
317 InstancePath dropFront() const { return InstancePath(path.drop_front()); }
318
319 InstancePath dropBack() const { return InstancePath(path.drop_back()); }
320
321 InstanceOpInterface operator[](size_t idx) const { return path[idx]; }
322 ArrayRef<InstanceOpInterface>::iterator begin() const { return path.begin(); }
323 ArrayRef<InstanceOpInterface>::iterator end() const { return path.end(); }
324 ArrayRef<InstanceOpInterface> getPath() const { return path; }
325 size_t size() const { return path.size(); }
326 bool empty() const { return path.empty(); }
327
328 bool operator==(const InstancePath &that) const { return path == that.path; }
329
330 /// Print the path to any stream-like object.
331 void print(llvm::raw_ostream &into) const;
332
333private:
334 // Either path cache or DenseMapInfo is allowed to create paths.
335 friend struct InstancePathCache;
336 friend struct llvm::DenseMapInfo<InstancePath>;
337 InstancePath(ArrayRef<InstanceOpInterface> path) : path(path) {}
338
339 ArrayRef<InstanceOpInterface> path;
340};
341
342inline llvm::raw_ostream &operator<<(llvm::raw_ostream &os,
343 const InstancePath &path) {
344 path.print(os);
345 return os;
346}
347
348/// A data structure that caches and provides paths to module
349/// instances in the IR.
351 /// The instance graph of the IR.
353
356
357 // Return all absolute paths from the top-level node to the given module.
358 ArrayRef<InstancePath> getAbsolutePaths(ModuleOpInterface op);
359
360 // Return all relative paths from the given node to the given module.
361 ArrayRef<InstancePath> getRelativePaths(ModuleOpInterface op,
362 InstanceGraphNode *node);
363
364 /// Replace an InstanceOp. This is required to keep the cache updated.
365 void replaceInstance(InstanceOpInterface oldOp, InstanceOpInterface newOp);
366
367 /// Append an instance to a path.
368 InstancePath appendInstance(InstancePath path, InstanceOpInterface inst);
369
370 /// Prepend an instance to a path.
371 InstancePath prependInstance(InstanceOpInterface inst, InstancePath path);
372
373private:
374 using PathsCache = DenseMap<Operation *, ArrayRef<InstancePath>>;
375 ArrayRef<InstancePath> getPaths(ModuleOpInterface op, InstanceGraphNode *top,
376 PathsCache &cache);
377
378 /// An allocator for individual instance paths and entire path lists.
379 llvm::BumpPtrAllocator allocator;
380
381 /// Cached absolute instance paths.
383
384 /// Cached relative instance paths.
385 DenseMap<InstanceGraphNode *, PathsCache> relativePathsCache;
386};
387
388} // namespace igraph
389} // namespace circt
390
391// Graph traits for modules.
392template <>
393struct llvm::GraphTraits<circt::igraph::InstanceGraphNode *> {
395 using NodeRef = NodeType *;
396
397 // Helper for getting the module referenced by the instance op.
399 return record->getTarget();
400 }
401
403 llvm::mapped_iterator<NodeType::iterator, decltype(&getChild)>;
404
405 static NodeRef getEntryNode(NodeRef node) { return node; }
407 return {node->begin(), &getChild};
408 }
410 return {node->end(), &getChild};
411 }
412};
413
414// Provide graph traits for iterating the modules in inverse order.
415template <>
416struct llvm::GraphTraits<llvm::Inverse<circt::igraph::InstanceGraphNode *>> {
418 using NodeRef = NodeType *;
419
420 // Helper for getting the module containing the instance op.
422 return record->getParent();
423 }
424
426 llvm::mapped_iterator<NodeType::UseIterator, decltype(&getParent)>;
427
428 static NodeRef getEntryNode(Inverse<NodeRef> inverse) {
429 return inverse.Graph;
430 }
432 return {node->usesBegin(), &getParent};
433 }
435 return {node->usesEnd(), &getParent};
436 }
437};
438
439// Graph traits for the common instance graph.
440template <>
441struct llvm::GraphTraits<circt::igraph::InstanceGraph *>
442 : public llvm::GraphTraits<circt::igraph::InstanceGraphNode *> {
444
446 return graph->getTopLevelNode();
447 }
448 // NOLINTNEXTLINE(readability-identifier-naming)
450 return graph->begin();
451 }
452 // NOLINTNEXTLINE(readability-identifier-naming)
454 return graph->end();
455 }
456};
457
458// Graph traits for DOT labeling.
459template <>
460struct llvm::DOTGraphTraits<circt::igraph::InstanceGraph *>
461 : public llvm::DefaultDOTGraphTraits {
462 using DefaultDOTGraphTraits::DefaultDOTGraphTraits;
463
466 // The name of the graph node is the module name.
467 return node->getModule().getModuleName().str();
468 }
469
470 template <typename Iterator>
471 static std::string
474 // Set an edge label that is the name of the instance.
475 auto *instanceRecord = *it.getCurrent();
476 auto instanceOp = instanceRecord->getInstance();
477 return ("label=" + instanceOp.getInstanceName()).str();
478 }
479};
480
481// DenseMap traits for InstancePath.
482template <>
483struct llvm::DenseMapInfo<circt::igraph::InstancePath> {
487 return circt::igraph::InstancePath(ArrayRefInfo::getEmptyKey());
488 }
489
491 return circt::igraph::InstancePath(ArrayRefInfo::getTombstoneKey());
492 }
493
494 static llvm::hash_code getHashValue(circt::igraph::InstancePath path) {
495 auto range =
496 llvm::map_range(path, [](auto op) { return op.getAsOpaquePointer(); });
497 return llvm::hash_combine_range(range.begin(), range.end());
498 }
499
502 return ArrayRefInfo::isEqual(lhs.getPath(), rhs.getPath());
503 }
504};
505
506#endif // CIRCT_SUPPORT_INSTANCEGRAPH_H
assert(baseType &&"element must be base type")
This is a Node in the InstanceGraph.
llvm::iterator_range< UseIterator > uses()
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.
InstanceGraphNode(const InstanceGraphNode &)=delete
auto getModule()
Get the module that this node is tracking.
ModuleOpInterface InstanceList instances
The module.
UseIterator usesBegin()
Iterate the instance records which instantiate this module.
llvm::iplist< InstanceRecord > InstanceList
size_t getNumUses()
Get the number of direct instantiations of this module.
bool hasOneUse()
Return true if this module has exactly one use.
void recordUse(InstanceRecord *record)
Record that a module instantiates this module.
This graph tracks modules and where they are instantiated.
virtual ~InstanceGraph()=default
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 * lookup(StringAttr name)
Lookup an module by name. Aborts if the module does not exist.
detail::AddressIterator< NodeList::iterator > iterator
Iterate through all modules.
InstanceGraph(const InstanceGraph &)=delete
InstanceGraphNode * getOrAddNode(StringAttr name)
Get the node corresponding to the module.
InstanceGraphNode * operator[](ModuleOpInterface op)
Lookup an InstanceGraphNode for a module.
InstanceGraphNode * lookupOrNull(ModuleOpInterface op)
Look up an InstanceGraphNode for a module.
llvm::iplist< InstanceGraphNode > NodeList
This is the list of InstanceGraphNodes in the graph.
InstanceGraph(Operation *parent)
Create a new module graph of a circuit.
static NodeList InstanceGraph::* getSublistAccess(Operation *)
Returns pointer to member of operation list.
ModuleOpInterface getReferencedModuleImpl(InstanceOpInterface op)
An instance path composed of a series of instances.
InstanceOpInterface leaf() const
bool operator==(const InstancePath &that) const
InstanceOpInterface operator[](size_t idx) const
ArrayRef< InstanceOpInterface > path
ArrayRef< InstanceOpInterface > getPath() const
InstancePath(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
InstancePath dropFront() const
InstancePath dropBack() const
InstanceOpInterface top() const
This is an edge in the InstanceGraph.
InstanceGraphNode * getParent() const
Get the module where the instantiation lives.
auto getInstance()
Get the instance-like op that this is tracking.
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.
InstanceOpInterface instance
The InstanceLike that this is tracking.
InstanceGraphNode * getTarget() const
Get the module which the instance-like is instantiating.
InstanceRecord(InstanceGraphNode *parent, InstanceOpInterface instance, InstanceGraphNode *target)
InstanceGraphNode * parent
This is the module where the instantiation lives.
InstanceRecord(const InstanceRecord &)=delete
llvm::raw_ostream & operator<<(llvm::raw_ostream &os, const InstancePath &path)
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
bool operator==(const UseIterator &other) const
A data structure that caches and provides paths to module instances in the IR.
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.
InstancePathCache(InstanceGraph &instanceGraph)
This just maps a iterator of references to an iterator of addresses.
static Iterator::value_type * addrOf(typename Iterator::value_type &v) noexcept
static std::string getEdgeAttributes(const circt::igraph::InstanceGraphNode *node, Iterator it, circt::igraph::InstanceGraph *)
static std::string getNodeLabel(circt::igraph::InstanceGraphNode *node, circt::igraph::InstanceGraph *)
static circt::igraph::InstancePath getTombstoneKey()
static bool isEqual(circt::igraph::InstancePath lhs, circt::igraph::InstancePath rhs)
static llvm::hash_code getHashValue(circt::igraph::InstancePath path)
static circt::igraph::InstancePath getEmptyKey()
static ChildIteratorType child_begin(NodeRef node)
static NodeRef getChild(const circt::igraph::InstanceRecord *record)
llvm::mapped_iterator< NodeType::iterator, decltype(&getChild)> ChildIteratorType
static ChildIteratorType child_end(NodeRef node)
static nodes_iterator nodes_begin(circt::igraph::InstanceGraph *graph)
static NodeRef getEntryNode(circt::igraph::InstanceGraph *graph)
static nodes_iterator nodes_end(circt::igraph::InstanceGraph *graph)
llvm::mapped_iterator< NodeType::UseIterator, decltype(&getParent)> ChildIteratorType
static NodeRef getParent(const circt::igraph::InstanceRecord *record)