CIRCT  18.0.0git
InstanceGraph.cpp
Go to the documentation of this file.
1 //===- InstanceGraph.cpp - 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 
10 #include "mlir/IR/BuiltinOps.h"
11 #include "mlir/IR/Threading.h"
12 
13 using namespace circt;
14 using namespace igraph;
15 
17  // Update the prev node to point to the next node.
18  if (prevUse)
20  else
22  // Update the next node to point to the prev node.
23  if (nextUse)
25  getParent()->instances.erase(this);
26 }
27 
28 InstanceRecord *InstanceGraphNode::addInstance(InstanceOpInterface instance,
29  InstanceGraphNode *target) {
30  auto *instanceRecord = new InstanceRecord(this, instance, target);
31  target->recordUse(instanceRecord);
32  instances.push_back(instanceRecord);
33  return instanceRecord;
34 }
35 
37  record->nextUse = firstUse;
38  if (firstUse)
39  firstUse->prevUse = record;
40  firstUse = record;
41 }
42 
44  // Try to insert an InstanceGraphNode. If its not inserted, it returns
45  // an iterator pointing to the node.
46  auto *&node = nodeMap[name];
47  if (!node) {
48  node = new InstanceGraphNode();
49  nodes.push_back(node);
50  }
51  return node;
52 }
53 
54 InstanceGraph::InstanceGraph(Operation *parent) : parent(parent) {
55  assert(parent->hasTrait<mlir::OpTrait::SingleBlock>() &&
56  "top-level operation must have a single block");
57  SmallVector<std::pair<ModuleOpInterface, SmallVector<InstanceOpInterface>>>
58  moduleToInstances;
59  // First accumulate modules inside the parent op.
60  for (auto module :
61  parent->getRegion(0).front().getOps<igraph::ModuleOpInterface>())
62  moduleToInstances.push_back({module, {}});
63 
64  // Populate instances in the module parallelly.
65  mlir::parallelFor(parent->getContext(), 0, moduleToInstances.size(),
66  [&](size_t idx) {
67  auto module = moduleToInstances[idx].first;
68  auto &instances = moduleToInstances[idx].second;
69  // Find all instance operations in the module body.
70  module.walk([&](InstanceOpInterface instanceOp) {
71  instances.push_back(instanceOp);
72  });
73  });
74 
75  // Construct an instance graph sequentially.
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) {
81  // Add an edge to indicate that this module instantiates the target.
82  auto *targetNode = getOrAddNode(instanceOp.getReferencedModuleNameAttr());
83  currentNode->addInstance(instanceOp, targetNode);
84  }
85  }
86 }
87 
88 InstanceGraphNode *InstanceGraph::addModule(ModuleOpInterface module) {
89  assert(!nodeMap.count(module.getModuleNameAttr()) && "module already added");
90  auto *node = new InstanceGraphNode();
91  node->module = module;
92  nodeMap[module.getModuleNameAttr()] = node;
93  nodes.push_back(node);
94  return node;
95 }
96 
97 void InstanceGraph::erase(InstanceGraphNode *node) {
98  assert(node->noUses() &&
99  "all instances of this module must have been erased.");
100  // Erase all instances inside this module.
101  for (auto *instance : llvm::make_early_inc_range(*node))
102  instance->erase();
103  nodeMap.erase(node->getModule().getModuleNameAttr());
104  nodes.erase(node);
105 }
106 
107 InstanceGraphNode *InstanceGraph::lookup(StringAttr name) {
108  auto it = nodeMap.find(name);
109  assert(it != nodeMap.end() && "Module not in InstanceGraph!");
110  return it->second;
111 }
112 
113 InstanceGraphNode *InstanceGraph::lookup(ModuleOpInterface op) {
114  return lookup(cast<ModuleOpInterface>(op).getModuleNameAttr());
115 }
116 
117 ModuleOpInterface
118 InstanceGraph::getReferencedModuleImpl(InstanceOpInterface op) {
119  return lookup(op.getReferencedModuleNameAttr())->getModule();
120 }
121 
122 void InstanceGraph::replaceInstance(InstanceOpInterface inst,
123  InstanceOpInterface newInst) {
124  assert(inst.getReferencedModuleName() == newInst.getReferencedModuleName() &&
125  "Both instances must be targeting the same module");
126 
127  // Find the instance record of this instance.
128  auto *node = lookup(inst.getReferencedModuleNameAttr());
129  auto it = llvm::find_if(node->uses(), [&](InstanceRecord *record) {
130  return record->getInstance() == inst;
131  });
132  assert(it != node->usesEnd() && "Instance of module not recorded in graph");
133 
134  // We can just replace the instance op in the InstanceRecord without updating
135  // any instance lists.
136  (*it)->instance = newInst;
137 }
138 
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);
145  seen.insert(cn);
146  while (!worklist.empty()) {
147  auto *node = worklist.back();
148  worklist.pop_back();
149  if (node->getModule() == parent)
150  return true;
151  for (auto *use : node->uses()) {
152  auto *mod = use->getParent();
153  if (!seen.count(mod)) {
154  seen.insert(mod);
155  worklist.push_back(mod);
156  }
157  }
158  }
159  return false;
160 }
161 
163 InstanceGraph::getInferredTopLevelNodes() {
164  if (!inferredTopLevelNodes.empty())
165  return {inferredTopLevelNodes};
166 
167  /// Topologically sort the instance graph.
168  llvm::SetVector<InstanceGraphNode *> visited, marked;
169  llvm::SetVector<InstanceGraphNode *> candidateTopLevels(this->begin(),
170  this->end());
171  SmallVector<InstanceGraphNode *> cycleTrace;
172 
173  // Recursion function; returns true if a cycle was detected.
174  std::function<bool(InstanceGraphNode *, SmallVector<InstanceGraphNode *>)>
175  cycleUtil =
176  [&](InstanceGraphNode *node, SmallVector<InstanceGraphNode *> trace) {
177  if (visited.contains(node))
178  return false;
179  trace.push_back(node);
180  if (marked.contains(node)) {
181  // Cycle detected.
182  cycleTrace = trace;
183  return true;
184  }
185  marked.insert(node);
186  for (auto use : *node) {
187  InstanceGraphNode *targetModule = use->getTarget();
188  candidateTopLevels.remove(targetModule);
189  if (cycleUtil(targetModule, trace))
190  return true; // Cycle detected.
191  }
192  marked.remove(node);
193  visited.insert(node);
194  return false;
195  };
196 
197  bool cyclic = false;
198  for (auto moduleIt : *this) {
199  if (visited.contains(moduleIt))
200  continue;
201 
202  cyclic |= cycleUtil(moduleIt, {});
203  if (cyclic)
204  break;
205  }
206 
207  if (cyclic) {
208  auto err = getParent()->emitOpError();
209  err << "cannot deduce top level module - cycle "
210  "detected in instance graph (";
211  llvm::interleave(
212  cycleTrace, err,
213  [&](auto node) { err << node->getModule().getModuleName(); }, "->");
214  err << ").";
215  return err;
216  }
217  assert(!candidateTopLevels.empty() &&
218  "if non-cyclic, there should be at least 1 candidate top level");
219 
220  inferredTopLevelNodes = llvm::SmallVector<InstanceGraphNode *>(
221  candidateTopLevels.begin(), candidateTopLevels.end());
222  return {inferredTopLevelNodes};
223 }
224 
226 
227 // NOLINTBEGIN(misc-no-recursion)
228 ArrayRef<InstancePath>
229 InstancePathCache::getAbsolutePaths(ModuleOpInterface op) {
230  InstanceGraphNode *node = instanceGraph[op];
231 
232  if (node == instanceGraph.getTopLevelNode()) {
233  return empty;
234  }
235 
236  // Fast path: hit the cache.
237  auto cached = absolutePathsCache.find(op);
238  if (cached != absolutePathsCache.end())
239  return cached->second;
240 
241  // For each instance, collect the instance paths to its parent and append the
242  // instance itself to each.
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())));
251  }
252  } else {
253  extendedPaths.emplace_back(empty);
254  }
255  }
256 
257  // Move the list of paths into the bump allocator for later quick retrieval.
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());
263  }
264  absolutePathsCache.insert({op, pathList});
265  return pathList;
266 }
267 // NOLINTEND(misc-no-recursion)
268 
269 InstancePath InstancePathCache::appendInstance(InstancePath path,
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;
275  return InstancePath(ArrayRef(newPath, n));
276 }
277 
278 InstancePath InstancePathCache::prependInstance(InstanceOpInterface inst,
279  InstancePath path) {
280  size_t n = path.size() + 1;
281  auto *newPath = allocator.Allocate<InstanceOpInterface>(n);
282  std::copy(path.begin(), path.end(), newPath + 1);
283  newPath[0] = inst;
284  return InstancePath(ArrayRef(newPath, n));
285 }
286 
287 void InstancePathCache::replaceInstance(InstanceOpInterface oldOp,
288  InstanceOpInterface newOp) {
289 
290  instanceGraph.replaceInstance(oldOp, newOp);
291 
292  // Iterate over all the paths, and search for the old InstanceOpInterface. If
293  // found, then replace it with the new InstanceOpInterface, and create a new
294  // copy of the paths and update the cache.
295  auto instanceExists = [&](const ArrayRef<InstancePath> &paths) -> bool {
296  return llvm::any_of(
297  paths, [&](InstancePath p) { return llvm::is_contained(p, oldOp); });
298  };
299 
300  for (auto &iter : absolutePathsCache) {
301  if (!instanceExists(iter.getSecond()))
302  continue;
303  SmallVector<InstancePath, 8> updatedPaths;
304  for (auto path : iter.getSecond()) {
305  const auto *iter = llvm::find(path, oldOp);
306  if (iter == path.end()) {
307  // path does not contain the oldOp, just copy it as is.
308  updatedPaths.push_back(path);
309  continue;
310  }
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())));
315  }
316  // Move the list of paths into the bump allocator for later quick
317  // retrieval.
318  auto *paths = allocator.Allocate<InstancePath>(updatedPaths.size());
319  llvm::copy(updatedPaths, paths);
320  iter.getSecond() = ArrayRef<InstancePath>(paths, updatedPaths.size());
321  }
322 }
323 
324 #include "circt/Support/InstanceGraphInterface.cpp.inc"
assert(baseType &&"element must be base type")
static InstancePath empty
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.
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.
Definition: InstanceGraph.h:55
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
InstanceGraphNode * getParent() const
Get the module where the instantiation lives.
Definition: InstanceGraph.h:66
igraph::InstanceGraphNode InstanceGraphNode
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
Definition: DebugAnalysis.h:21