CIRCT  18.0.0git
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 
27 namespace circt {
28 namespace igraph {
29 
30 namespace detail {
31 /// This just maps a iterator of references to an iterator of addresses.
32 template <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 
50 class 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> {
56 public:
57  /// Get the instance-like op that this is tracking.
58  template <typename TTarget = InstanceOpInterface>
59  auto getInstance() {
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 
75 private:
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.
93  InstanceRecord *nextUse = nullptr;
94  InstanceRecord *prevUse = nullptr;
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.
101 class InstanceGraphNode : public llvm::ilist_node<InstanceGraphNode> {
102  using InstanceList = llvm::iplist<InstanceRecord>;
103 
104 public:
105  InstanceGraphNode() : module(nullptr) {}
106 
107  /// Get the module that this node is tracking.
108  template <typename TTarget = ModuleOpInterface>
109  auto getModule() {
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.
130  struct UseIterator
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 
163 private:
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 
196 public:
197  /// Create a new module graph of a circuit. Must be called on the parent
198  /// operation of ModuleOpInterface ops.
199  InstanceGraph(Operation *parent);
200  InstanceGraph(const InstanceGraph &) = delete;
201  virtual ~InstanceGraph() = default;
202 
203  /// Look up an InstanceGraphNode for a module.
204  InstanceGraphNode *lookup(ModuleOpInterface op);
205 
206  /// Lookup an module by name.
207  InstanceGraphNode *lookup(StringAttr name);
208 
209  /// Lookup an InstanceGraphNode for a module.
210  InstanceGraphNode *operator[](ModuleOpInterface op) { return lookup(op); }
211 
212  /// Look up the referenced module from an InstanceOp. This will use a
213  /// hashtable lookup to find the module, where
214  /// InstanceOp.getReferencedModule() will be a linear search through the IR.
215  template <typename TTarget = ModuleOpInterface>
216  auto getReferencedModule(InstanceOpInterface op) {
217  return cast<TTarget>(getReferencedModuleImpl(op).getOperation());
218  }
219 
220  /// Check if child is instantiated by a parent.
221  bool isAncestor(ModuleOpInterface child, ModuleOpInterface parent);
222 
223  /// Get the node corresponding to the top-level module of a circuit.
224  virtual InstanceGraphNode *getTopLevelNode() { return nullptr; }
225 
226  /// Get the nodes corresponding to the inferred top-level modules of a
227  /// circuit.
229 
230  /// Return the parent under which all nodes are nested.
231  Operation *getParent() { return parent; }
232 
233  /// Returns pointer to member of operation list.
234  static NodeList InstanceGraph::*getSublistAccess(Operation *) {
235  return &InstanceGraph::nodes;
236  }
237 
238  /// Iterate through all modules.
240  iterator begin() { return nodes.begin(); }
241  iterator end() { return nodes.end(); }
242 
243  //===-------------------------------------------------------------------------
244  // Methods to keep an InstanceGraph up to date.
245  //
246  // These methods are not thread safe. Make sure that modifications are
247  // properly synchronized or performed in a serial context. When the
248  // InstanceGraph is used as an analysis, this is only safe when the pass is
249  // on a CircuitOp or a ModuleOp.
250 
251  /// Add a newly created module to the instance graph.
252  virtual InstanceGraphNode *addModule(ModuleOpInterface module);
253 
254  /// Remove this module from the instance graph. This will also remove all
255  /// InstanceRecords in this module. All instances of this module must have
256  /// been removed from the graph.
257  virtual void erase(InstanceGraphNode *node);
258 
259  /// Replaces an instance of a module with another instance. The target module
260  /// of both InstanceOps must be the same.
261  virtual void replaceInstance(InstanceOpInterface inst,
262  InstanceOpInterface newInst);
263 
264 protected:
265  ModuleOpInterface getReferencedModuleImpl(InstanceOpInterface op);
266 
267  /// Get the node corresponding to the module. If the node has does not exist
268  /// yet, it will be created.
269  InstanceGraphNode *getOrAddNode(StringAttr name);
270 
271  /// The node under which all modules are nested.
272  Operation *parent;
273 
274  /// The storage for graph nodes, with deterministic iteration.
276 
277  /// This maps each operation to its graph node.
278  llvm::DenseMap<Attribute, InstanceGraphNode *> nodeMap;
279 
280  /// A caching of the inferred top level module(s).
281  llvm::SmallVector<InstanceGraphNode *> inferredTopLevelNodes;
282 };
283 
284 struct InstancePathCache;
285 
286 /**
287  * An instance path composed of a series of instances.
288  */
289 class InstancePath final {
290 public:
291  InstancePath() = default;
292 
293  InstanceOpInterface top() const {
294  assert(!empty() && "instance path is empty");
295  return path[0];
296  }
297 
298  InstanceOpInterface leaf() const {
299  assert(!empty() && "instance path is empty");
300  return path.back();
301  }
302 
303  InstancePath dropFront() const { return InstancePath(path.drop_front()); }
304 
305  InstanceOpInterface operator[](size_t idx) const { return path[idx]; }
306  ArrayRef<InstanceOpInterface>::iterator begin() const { return path.begin(); }
307  ArrayRef<InstanceOpInterface>::iterator end() const { return path.end(); }
308  size_t size() const { return path.size(); }
309  bool empty() const { return path.empty(); }
310 
311  /// Print the path to any stream-like object.
312  template <typename T>
313  void print(T &into) const {
314  into << "$root";
315  for (auto inst : path)
316  into << "/" << inst.getInstanceName() << ":"
317  << inst.getReferencedModuleName();
318  }
319 
320 private:
321  // Only the path cache is allowed to create paths.
322  friend struct InstancePathCache;
323  InstancePath(ArrayRef<InstanceOpInterface> path) : path(path) {}
324 
325  ArrayRef<InstanceOpInterface> path;
326 };
327 
328 template <typename T>
329 static T &operator<<(T &os, const InstancePath &path) {
330  return path.print(os);
331 }
332 
333 /// A data structure that caches and provides absolute paths to module instances
334 /// in the IR.
336  /// The instance graph of the IR.
338 
341  ArrayRef<InstancePath> getAbsolutePaths(ModuleOpInterface op);
342 
343  /// Replace an InstanceOp. This is required to keep the cache updated.
344  void replaceInstance(InstanceOpInterface oldOp, InstanceOpInterface newOp);
345 
346  /// Append an instance to a path.
347  InstancePath appendInstance(InstancePath path, InstanceOpInterface inst);
348 
349  /// Prepend an instance to a path.
350  InstancePath prependInstance(InstanceOpInterface inst, InstancePath path);
351 
352 private:
353  /// An allocator for individual instance paths and entire path lists.
354  llvm::BumpPtrAllocator allocator;
355 
356  /// Cached absolute instance paths.
357  DenseMap<Operation *, ArrayRef<InstancePath>> absolutePathsCache;
358 };
359 
360 } // namespace igraph
361 } // namespace circt
362 
363 // Graph traits for modules.
364 template <>
365 struct llvm::GraphTraits<circt::igraph::InstanceGraphNode *> {
367  using NodeRef = NodeType *;
368 
369  // Helper for getting the module referenced by the instance op.
371  return record->getTarget();
372  }
373 
375  llvm::mapped_iterator<NodeType::iterator, decltype(&getChild)>;
376 
377  static NodeRef getEntryNode(NodeRef node) { return node; }
379  return {node->begin(), &getChild};
380  }
382  return {node->end(), &getChild};
383  }
384 };
385 
386 // Provide graph traits for iterating the modules in inverse order.
387 template <>
388 struct llvm::GraphTraits<llvm::Inverse<circt::igraph::InstanceGraphNode *>> {
390  using NodeRef = NodeType *;
391 
392  // Helper for getting the module containing the instance op.
394  return record->getParent();
395  }
396 
398  llvm::mapped_iterator<NodeType::UseIterator, decltype(&getParent)>;
399 
400  static NodeRef getEntryNode(Inverse<NodeRef> inverse) {
401  return inverse.Graph;
402  }
404  return {node->usesBegin(), &getParent};
405  }
407  return {node->usesEnd(), &getParent};
408  }
409 };
410 
411 // Graph traits for the common instance graph.
412 template <>
413 struct llvm::GraphTraits<circt::igraph::InstanceGraph *>
414  : public llvm::GraphTraits<circt::igraph::InstanceGraphNode *> {
416 
418  return graph->getTopLevelNode();
419  }
420  // NOLINTNEXTLINE(readability-identifier-naming)
422  return graph->begin();
423  }
424  // NOLINTNEXTLINE(readability-identifier-naming)
426  return graph->end();
427  }
428 };
429 
430 // Graph traits for DOT labeling.
431 template <>
432 struct llvm::DOTGraphTraits<circt::igraph::InstanceGraph *>
433  : public llvm::DefaultDOTGraphTraits {
434  using DefaultDOTGraphTraits::DefaultDOTGraphTraits;
435 
438  // The name of the graph node is the module name.
439  return node->getModule().getModuleName().str();
440  }
441 
442  template <typename Iterator>
443  static std::string
446  // Set an edge label that is the name of the instance.
447  auto *instanceRecord = *it.getCurrent();
448  auto instanceOp = instanceRecord->getInstance();
449  return ("label=" + instanceOp.getInstanceName()).str();
450  }
451 };
452 
453 #endif // CIRCT_SUPPORT_INSTANCEGRAPH_H
lowerAnnotationsNoRefTypePorts FirtoolPreserveValuesMode value
Definition: Firtool.cpp:95
assert(baseType &&"element must be base type")
This is a Node in the InstanceGraph.
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.
InstanceList instances
List of instance operations in this 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.
ModuleOpInterface module
The module.
bool hasOneUse()
Return true if this module has exactly one use.
llvm::iterator_range< UseIterator > uses()
void recordUse(InstanceRecord *record)
Record that a module instantiates this module.
This graph tracks modules and where they are instantiated.
virtual ~InstanceGraph()=default
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.
auto getReferencedModule(InstanceOpInterface op)
Look up the referenced module from an InstanceOp.
FailureOr< llvm::ArrayRef< InstanceGraphNode * > > getInferredTopLevelNodes()
Get the nodes corresponding to the inferred top-level modules of a circuit.
ModuleOpInterface getReferencedModuleImpl(InstanceOpInterface op)
InstanceGraph(Operation *parent)
Create a new module graph 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.
InstanceGraphNode * operator[](ModuleOpInterface op)
Lookup an InstanceGraphNode for a module.
InstanceGraphNode * lookup(ModuleOpInterface op)
Look up an InstanceGraphNode for a module.
virtual InstanceGraphNode * getTopLevelNode()
Get the node corresponding to the top-level module of a circuit.
Operation * getParent()
Return the parent under which all nodes are nested.
detail::AddressIterator< NodeList::iterator > iterator
Iterate through all modules.
virtual void erase(InstanceGraphNode *node)
Remove this module from the instance graph.
InstanceGraph(const InstanceGraph &)=delete
InstanceGraphNode * getOrAddNode(StringAttr name)
Get the node corresponding to the module.
llvm::iplist< InstanceGraphNode > NodeList
This is the list of InstanceGraphNodes in the graph.
static NodeList InstanceGraph::* getSublistAccess(Operation *)
Returns pointer to member of operation list.
bool isAncestor(ModuleOpInterface child, ModuleOpInterface parent)
Check if child is instantiated by a parent.
An instance path composed of a series of instances.
InstanceOpInterface leaf() const
void print(T &into) const
Print the path to any stream-like object.
InstanceOpInterface operator[](size_t idx) const
ArrayRef< InstanceOpInterface > path
ArrayRef< InstanceOpInterface >::iterator end() const
InstancePath(ArrayRef< InstanceOpInterface > path)
ArrayRef< InstanceOpInterface >::iterator begin() const
InstancePath dropFront() const
InstanceOpInterface top() const
This is an edge in the InstanceGraph.
Definition: InstanceGraph.h:55
InstanceGraphNode * getTarget() const
Get the module which the instance-like is instantiating.
Definition: InstanceGraph.h:69
auto getInstance()
Get the instance-like op that this is tracking.
Definition: InstanceGraph.h:59
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.
Definition: InstanceGraph.h:91
InstanceRecord * nextUse
Intrusive linked list for other uses.
Definition: InstanceGraph.h:93
InstanceOpInterface instance
The InstanceLike that this is tracking.
Definition: InstanceGraph.h:88
InstanceGraphNode * getParent() const
Get the module where the instantiation lives.
Definition: InstanceGraph.h:66
InstanceRecord(InstanceGraphNode *parent, InstanceOpInterface instance, InstanceGraphNode *target)
Definition: InstanceGraph.h:79
InstanceGraphNode * parent
This is the module where the instantiation lives.
Definition: InstanceGraph.h:85
InstanceRecord(const InstanceRecord &)=delete
igraph::InstanceGraphNode InstanceGraphNode
std::map< std::string, std::set< std::string > > InstanceGraph
Iterates over the handshake::FuncOp's in the program to build an instance graph.
static T & operator<<(T &os, const InstancePath &path)
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
Definition: DebugAnalysis.h:21
bool operator==(const UseIterator &other) const
A data structure that caches and provides absolute paths to module instances in the IR.
ArrayRef< InstancePath > getAbsolutePaths(ModuleOpInterface op)
void replaceInstance(InstanceOpInterface oldOp, InstanceOpInterface newOp)
Replace an InstanceOp. This is required to keep the cache updated.
DenseMap< Operation *, ArrayRef< InstancePath > > absolutePathsCache
Cached absolute instance paths.
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.
InstancePathCache(InstanceGraph &instanceGraph)
This just maps a iterator of references to an iterator of addresses.
Definition: InstanceGraph.h:35
static Iterator::value_type * addrOf(typename Iterator::value_type &v) noexcept
Definition: InstanceGraph.h:40
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 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)