13 #ifndef CIRCT_SUPPORT_INSTANCEGRAPH_H
14 #define CIRCT_SUPPORT_INSTANCEGRAPH_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"
32 template <
typename It>
34 :
public llvm::mapped_iterator<It, typename It::pointer (*)(
35 typename It::reference)> {
39 static typename Iterator::value_type *
40 addrOf(
typename Iterator::value_type &v) noexcept {
41 return std::addressof(v);
44 :
llvm::mapped_iterator<It, typename
Iterator::pointer (*)(
45 typename
Iterator::reference)>(iterator,
55 :
public llvm::ilist_node_with_parent<InstanceRecord, InstanceGraphNode> {
58 template <
typename TTarget = InstanceOpInterface>
62 return dyn_cast_or_null<TTarget>(
instance.getOperation());
108 template <
typename TTarget = ModuleOpInterface>
112 return cast<TTarget>(
module.getOperation());
131 :
public llvm::iterator_facade_base<
132 UseIterator, std::forward_iterator_tag, InstanceRecord *> {
136 using llvm::iterator_facade_base<
UseIterator, std::forward_iterator_tag,
154 llvm::iterator_range<UseIterator>
uses() {
215 template <
typename TTarget = ModuleOpInterface>
262 InstanceOpInterface newInst);
278 llvm::DenseMap<Attribute, InstanceGraphNode *>
nodeMap;
293 InstanceOpInterface
top()
const {
298 InstanceOpInterface
leaf()
const {
306 ArrayRef<InstanceOpInterface>::iterator
begin()
const {
return path.begin(); }
307 ArrayRef<InstanceOpInterface>::iterator
end()
const {
return path.end(); }
312 template <
typename T>
315 for (
auto inst :
path)
316 into <<
"/" << inst.getInstanceName() <<
":"
317 << inst.getReferencedModuleName();
325 ArrayRef<InstanceOpInterface>
path;
328 template <
typename T>
330 return path.
print(os);
344 void replaceInstance(InstanceOpInterface oldOp, InstanceOpInterface newOp);
379 return {node->
begin(), &getChild};
382 return {node->
end(), &getChild};
388 struct llvm::GraphTraits<
llvm::Inverse<circt::igraph::InstanceGraphNode *>> {
401 return inverse.Graph;
407 return {node->
usesEnd(), &getParent};
414 :
public llvm::GraphTraits<circt::igraph::InstanceGraphNode *> {
422 return graph->
begin();
433 :
public llvm::DefaultDOTGraphTraits {
434 using DefaultDOTGraphTraits::DefaultDOTGraphTraits;
439 return node->
getModule().getModuleName().str();
442 template <
typename Iterator>
447 auto *instanceRecord = *it.getCurrent();
448 auto instanceOp = instanceRecord->getInstance();
449 return (
"label=" + instanceOp.getInstanceName()).str();
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.
InstanceGraphNode * getTarget() const
Get the module which the instance-like is instantiating.
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 * getParent() const
Get the module where the instantiation lives.
InstanceRecord(InstanceGraphNode *parent, InstanceOpInterface instance, InstanceGraphNode *target)
InstanceGraphNode * parent
This is the module where the instantiation lives.
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...
Iterator for module uses.
UseIterator(InstanceGraphNode *node)
bool operator==(const UseIterator &other) const
InstanceRecord * operator*() const
UseIterator & operator++()
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.
AddressIterator(Iterator iterator)
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 NodeRef getEntryNode(NodeRef node)
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)
static ChildIteratorType child_end(NodeRef node)
static ChildIteratorType child_begin(NodeRef node)
static NodeRef getEntryNode(Inverse< NodeRef > inverse)