CIRCT  18.0.0git
CheckCombLoops.cpp
Go to the documentation of this file.
1 //===- CheckCombLoops.cpp - FIRRTL check combinational cycles ------------===//
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 implements the FIRRTL combinational cycles detection pass. The
10 // algorithm handles aggregates and sub-index/field/access ops.
11 // 1. Traverse each module in the Instance Graph bottom up.
12 // 2. Preprocess step: Gather all the Value which serve as the root for the
13 // DFS traversal. The input arguments and wire ops and Instance results
14 // are the roots.
15 // Then populate the map for Value to all the FieldRefs it can refer to,
16 // and another map of FieldRef to all the Values that refer to it.
17 // (A single Value can refer to multiple FieldRefs, if the Value is the
18 // result of a SubAccess op. Multiple values can refer to the same
19 // FieldRef, since multiple SubIndex/Field ops with the same fieldIndex
20 // can exist in the IR). We also maintain an aliasingValuesMap that maps
21 // each Value to the set of Values that can refer to the same FieldRef.
22 // 3. Start from DFS traversal from the root. Push the root to the DFS stack.
23 // 4. Pop a Value from the DFS stack, add all the Values that alias with it
24 // to the Visiting set. Add all the unvisited children of the Values in the
25 // alias set to the DFS stack.
26 // 5. If any child is already present in the Visiting set, then a cycle is
27 // found.
28 //
29 //===----------------------------------------------------------------------===//
30 
31 #include "PassDetails.h"
36 #include "llvm/ADT/DenseMap.h"
37 #include "llvm/ADT/DepthFirstIterator.h"
38 #include "llvm/ADT/PostOrderIterator.h"
39 #include "llvm/ADT/SCCIterator.h"
40 #include "llvm/ADT/SmallSet.h"
41 #include <variant>
42 
43 #define DEBUG_TYPE "check-comb-loops"
44 
45 using namespace circt;
46 using namespace firrtl;
47 
48 using SetOfFieldRefs = DenseSet<FieldRef>;
49 
50 /// A value is in VisitingSet if its subtree is still being traversed. That is,
51 /// all its children have not yet been visited. If any Value is visited while
52 /// its still in the `VisitingSet`, that implies a back edge and a cycle.
53 struct VisitingSet {
54 private:
55  /// The stack is maintained to keep track of the cycle, if one is found. This
56  /// is required for an iterative DFS traversal, its implicitly recorded for a
57  /// recursive version of this algorithm. Each entry in the stack is a list of
58  /// aliasing Values, which were visited at the same time.
59  SmallVector<SmallVector<Value, 2>> visitingStack;
60  /// This map of the Visiting values, is for faster query, to check if a Value
61  /// is in VisitingSet. It also records the corresponding index into the
62  /// visitingStack, for faster pop until the Value.
63  DenseMap<Value, unsigned> valToStackMap;
64 
65 public:
66  void appendEmpty() { visitingStack.push_back({}); }
67  void appendToEnd(SmallVector<Value> &values) {
68  auto stackSize = visitingStack.size() - 1;
69  visitingStack.back().append(values.begin(), values.end());
70  // Record the stack location where this Value is pushed.
71  llvm::for_each(values, [&](Value v) { valToStackMap[v] = stackSize; });
72  }
73  bool contains(Value v) {
74  return valToStackMap.find(v) != valToStackMap.end();
75  }
76  // Pop all the Values which were visited after v. Then invoke f (if present)
77  // on a popped value for each index.
78  void popUntilVal(Value v,
79  const llvm::function_ref<void(Value poppedVal)> f = {}) {
80  auto valPos = valToStackMap[v];
81  while (visitingStack.size() != valPos) {
82  auto poppedVals = visitingStack.pop_back_val();
83  Value poppedVal;
84  llvm::for_each(poppedVals, [&](Value pv) {
85  if (!poppedVal)
86  poppedVal = pv;
87  valToStackMap.erase(pv);
88  });
89  if (f && poppedVal)
90  f(poppedVal);
91  }
92  }
93 };
94 
96 
97 public:
98  DiscoverLoops(FModuleOp module, InstanceGraph &instanceGraph,
99  DenseMap<FieldRef, SetOfFieldRefs> &portPaths)
100  : module(module), instanceGraph(instanceGraph), portPaths(portPaths) {}
101 
102  LogicalResult processModule() {
103  LLVM_DEBUG(llvm::dbgs() << "\n processing module :" << module.getName());
104  SmallVector<Value> worklist;
105  // Traverse over ports and ops, to populate the worklist and get the
106  // FieldRef corresponding to every Value. Also process the InstanceOps and
107  // get the paths that exist between the ports of the referenced module.
108  preprocess(worklist);
109 
110  llvm::DenseSet<Value> visited;
111  VisitingSet visiting;
112  SmallVector<Value> dfsStack;
113  SmallVector<FieldRef> inputArgFields;
114  // Record all the children of Value being visited.
115  SmallVector<Value, 8> children;
116  // If this is an input port field, then record it. This is used to
117  // discover paths from input to output ports. Only the last input port
118  // that is visited on the DFS traversal is recorded.
119  SmallVector<FieldRef, 2> inputArgFieldsTemp;
120  SmallVector<Value> aliasingValues;
121 
122  // worklist is the list of roots, to begin the traversal from.
123  for (auto root : worklist) {
124  dfsStack = {root};
125  inputArgFields.clear();
126  LLVM_DEBUG(llvm::dbgs() << "\n Starting traversal from root :"
127  << getFieldName(FieldRef(root, 0)).first);
128  if (auto inArg = dyn_cast<BlockArgument>(root)) {
129  if (module.getPortDirection(inArg.getArgNumber()) == Direction::In)
130  // This is required, such that paths to output port can be discovered.
131  // If there is an overlapping path from two input ports to an output
132  // port, then the already visited nodes must be re-visited to discover
133  // the comb paths to the output port.
134  visited.clear();
135  }
136  while (!dfsStack.empty()) {
137  auto dfsVal = dfsStack.back();
138  if (!visiting.contains(dfsVal)) {
139  unsigned dfsSize = dfsStack.size();
140 
141  LLVM_DEBUG(llvm::dbgs() << "\n Stack pop :"
142  << getFieldName(FieldRef(dfsVal, 0)).first
143  << "," << dfsVal;);
144 
145  // Visiting set will contain all the values which alias with the
146  // dfsVal, this is required to detect back edges to aliasing Values.
147  // That is fieldRefs that can refer to the same memory location.
148  visiting.appendEmpty();
149  children.clear();
150  inputArgFieldsTemp.clear();
151  // All the Values that refer to the same FieldRef are added to the
152  // aliasingValues.
153  aliasingValues = {dfsVal};
154  auto aToVIter = aliasingValuesMap.find(dfsVal);
155  if (aToVIter != aliasingValuesMap.end()) {
156  aliasingValues.append(aToVIter->getSecond().begin(),
157  aToVIter->getSecond().end());
158  }
159  // If `dfsVal` is a subfield, then get all the FieldRefs that it
160  // refers to and then get all the values that alias with it.
161  forallRefersTo(dfsVal, [&](FieldRef ref) {
162  // If this subfield refers to instance/mem results(input port), then
163  // add the output port FieldRefs that exist in the referenced module
164  // comb paths to the children.
165  handlePorts(ref, children);
166  // Get all the values that refer to this FieldRef, and add them to
167  // the aliasing values.
168  if (auto arg = dyn_cast<BlockArgument>(ref.getValue()))
169  if (module.getPortDirection(arg.getArgNumber()) == Direction::In)
170  inputArgFieldsTemp.push_back(ref);
171 
172  return success();
173  });
174  if (!inputArgFieldsTemp.empty())
175  inputArgFields = std::move(inputArgFieldsTemp);
176 
177  visiting.appendToEnd(aliasingValues);
178  visited.insert(aliasingValues.begin(), aliasingValues.end());
179  // Add the Value to `children`, to which a path exists from `dfsVal`.
180  for (auto dfsFromVal : aliasingValues) {
181 
182  for (auto &use : dfsFromVal.getUses()) {
183  auto childVal =
184  TypeSwitch<Operation *, Value>(use.getOwner())
185  // Registers stop walk for comb loops.
186  .Case<RegOp, RegResetOp>([](auto _) { return Value(); })
187  // For non-register declarations, look at data result.
188  .Case<Forceable>([](auto op) { return op.getDataRaw(); })
189  // Handle connect ops specially.
190  .Case<FConnectLike>([&](FConnectLike connect) -> Value {
191  if (use.getOperandNumber() == 1) {
192  auto dst = connect.getDest();
193  if (handleConnects(dst, inputArgFields).succeeded())
194  return dst;
195  }
196  return {};
197  })
198  // For everything else (e.g., expressions), if has single
199  // result use that.
200  .Default([](auto op) -> Value {
201  if (op->getNumResults() == 1)
202  return op->getResult(0);
203  return {};
204  });
205  if (childVal && type_isa<FIRRTLType>(childVal.getType()))
206  children.push_back(childVal);
207  }
208  }
209  for (auto childVal : children) {
210  // This childVal can be ignored, if
211  // It is a Register or a subfield of a register.
212  if (!visited.contains(childVal))
213  dfsStack.push_back(childVal);
214  // If the childVal is a sub, then check if it aliases with any of
215  // the predecessors (the visiting set).
216  if (visiting.contains(childVal)) {
217  // Comb Cycle Detected !!
218  reportLoopFound(childVal, visiting);
219  return failure();
220  }
221  }
222  // child nodes added, continue the DFS
223  if (dfsSize != dfsStack.size())
224  continue;
225  }
226  // FieldRef is an SCC root node, pop the visiting stack to remove the
227  // nodes that are no longer active predecessors, that is their sub-tree
228  // is already explored. All the Values reachable from `dfsVal` have been
229  // explored, remove it and its children from the visiting stack.
230  visiting.popUntilVal(dfsVal);
231 
232  auto popped = dfsStack.pop_back_val();
233  (void)popped;
234  LLVM_DEBUG({
235  llvm::dbgs() << "\n dfs popped :"
236  << getFieldName(FieldRef(popped, 0)).first;
237  dump();
238  });
239  }
240  }
241 
242  return success();
243  }
244 
245  // Preprocess the module ops to get the
246  // 1. roots for DFS traversal,
247  // 2. FieldRef corresponding to each Value.
248  void preprocess(SmallVector<Value> &worklist) {
249  // All the input ports are added to the worklist.
250  for (BlockArgument arg : module.getArguments()) {
251  auto argType = type_cast<FIRRTLType>(arg.getType());
252  if (type_isa<RefType>(argType))
253  continue;
254  if (module.getPortDirection(arg.getArgNumber()) == Direction::In)
255  worklist.push_back(arg);
256  if (!argType.isGround())
257  setValRefsTo(arg, FieldRef(arg, 0));
258  }
259  DenseSet<Value> memPorts;
260 
261  for (auto &op : module.getOps()) {
262  TypeSwitch<Operation *>(&op)
263  // Wire is added to the worklist
264  .Case<WireOp>([&](WireOp wire) {
265  worklist.push_back(wire.getResult());
266  auto ty = type_dyn_cast<FIRRTLBaseType>(wire.getResult().getType());
267  if (ty && !ty.isGround())
268  setValRefsTo(wire.getResult(), FieldRef(wire.getResult(), 0));
269  })
270  // All sub elements are added to the worklist.
271  .Case<SubfieldOp>([&](SubfieldOp sub) {
272  auto res = sub.getResult();
273  bool isValid = false;
274  auto fieldIndex = sub.getAccessedField().getFieldID();
275  if (memPorts.contains(sub.getInput())) {
276  auto memPort = sub.getInput();
277  BundleType type = memPort.getType();
278  auto enableFieldId =
279  type.getFieldID((unsigned)ReadPortSubfield::en);
280  auto dataFieldId =
281  type.getFieldID((unsigned)ReadPortSubfield::data);
282  auto addressFieldId =
283  type.getFieldID((unsigned)ReadPortSubfield::addr);
284  if (fieldIndex == enableFieldId || fieldIndex == dataFieldId ||
285  fieldIndex == addressFieldId) {
286  setValRefsTo(memPort, FieldRef(memPort, 0));
287  } else
288  return;
289  }
290  SmallVector<FieldRef, 4> fields;
291  forallRefersTo(
292  sub.getInput(),
293  [&](FieldRef subBase) {
294  isValid = true;
295  fields.push_back(subBase.getSubField(fieldIndex));
296  return success();
297  },
298  false);
299  if (isValid) {
300  for (auto f : fields)
301  setValRefsTo(res, f);
302  }
303  })
304  .Case<SubindexOp>([&](SubindexOp sub) {
305  auto res = sub.getResult();
306  bool isValid = false;
307  auto index = sub.getAccessedField().getFieldID();
308  SmallVector<FieldRef, 4> fields;
309  forallRefersTo(
310  sub.getInput(),
311  [&](FieldRef subBase) {
312  isValid = true;
313  fields.push_back(subBase.getSubField(index));
314  return success();
315  },
316  false);
317  if (isValid) {
318  for (auto f : fields)
319  setValRefsTo(res, f);
320  }
321  })
322  .Case<SubaccessOp>([&](SubaccessOp sub) {
323  FVectorType vecType = sub.getInput().getType();
324  auto res = sub.getResult();
325  bool isValid = false;
326  SmallVector<FieldRef, 4> fields;
327  forallRefersTo(
328  sub.getInput(),
329  [&](FieldRef subBase) {
330  isValid = true;
331  // The result of a subaccess can refer to multiple storage
332  // locations corresponding to all the possible indices.
333  for (size_t index = 0; index < vecType.getNumElements();
334  ++index)
335  fields.push_back(subBase.getSubField(
336  1 + index * (hw::FieldIdImpl::getMaxFieldID(
337  vecType.getElementType()) +
338  1)));
339  return success();
340  },
341  false);
342  if (isValid) {
343  for (auto f : fields)
344  setValRefsTo(res, f);
345  }
346  })
347  .Case<InstanceOp>(
348  [&](InstanceOp ins) { handleInstanceOp(ins, worklist); })
349  .Case<MemOp>([&](MemOp mem) {
350  if (!(mem.getReadLatency() == 0)) {
351  return;
352  }
353  for (auto memPort : mem.getResults()) {
354  if (!type_isa<FIRRTLBaseType>(memPort.getType()))
355  continue;
356  memPorts.insert(memPort);
357  }
358  })
359  .Default([&](auto) {});
360  }
361  }
362 
363  void handleInstanceOp(InstanceOp ins, SmallVector<Value> &worklist) {
364  for (auto port : ins.getResults()) {
365  if (auto type = type_dyn_cast<FIRRTLBaseType>(port.getType())) {
366  worklist.push_back(port);
367  if (!type.isGround())
368  setValRefsTo(port, FieldRef(port, 0));
369  } else if (auto type = type_dyn_cast<PropertyType>(port.getType())) {
370  worklist.push_back(port);
371  }
372  }
373  }
374 
375  void handlePorts(FieldRef ref, SmallVectorImpl<Value> &children) {
376  if (auto inst = dyn_cast_or_null<InstanceOp>(ref.getDefiningOp())) {
377  auto res = cast<OpResult>(ref.getValue());
378  auto portNum = res.getResultNumber();
379  auto refMod =
380  dyn_cast_or_null<FModuleOp>(*instanceGraph.getReferencedModule(inst));
381  if (!refMod)
382  return;
383  FieldRef modArg(refMod.getArgument(portNum), ref.getFieldID());
384  auto pathIter = portPaths.find(modArg);
385  if (pathIter == portPaths.end())
386  return;
387  for (auto modOutPort : pathIter->second) {
388  auto outPortNum =
389  cast<BlockArgument>(modOutPort.getValue()).getArgNumber();
390  if (modOutPort.getFieldID() == 0) {
391  children.push_back(inst.getResult(outPortNum));
392  continue;
393  }
394  FieldRef instanceOutPort(inst.getResult(outPortNum),
395  modOutPort.getFieldID());
396  llvm::append_range(children, fieldToVals[instanceOutPort]);
397  }
398  } else if (auto mem = dyn_cast<MemOp>(ref.getDefiningOp())) {
399  if (mem.getReadLatency() > 0)
400  return;
401  auto memPort = ref.getValue();
402  auto type = type_cast<BundleType>(memPort.getType());
403  auto enableFieldId = type.getFieldID((unsigned)ReadPortSubfield::en);
404  auto dataFieldId = type.getFieldID((unsigned)ReadPortSubfield::data);
405  auto addressFieldId = type.getFieldID((unsigned)ReadPortSubfield::addr);
406  if (ref.getFieldID() == enableFieldId ||
407  ref.getFieldID() == addressFieldId) {
408  for (auto dataField : fieldToVals[FieldRef(memPort, dataFieldId)])
409  children.push_back(dataField);
410  }
411  }
412  }
413 
414  void reportLoopFound(Value childVal, VisitingSet visiting) {
415  // TODO: Work harder to provide best information possible to user,
416  // especially across instances or when we trace through aliasing values.
417  // We're about to exit, and can afford to do some slower work here.
418  auto getName = [&](Value v) {
419  if (isa_and_nonnull<SubfieldOp, SubindexOp, SubaccessOp>(
420  v.getDefiningOp())) {
421  assert(!valRefersTo[v].empty());
422  // Pick representative of the "alias set", not deterministic.
423  return getFieldName(*valRefersTo[v].begin()).first;
424  }
425  return getFieldName(FieldRef(v, 0)).first;
426  };
427  auto errorDiag = mlir::emitError(
428  module.getLoc(), "detected combinational cycle in a FIRRTL module");
429 
430  SmallVector<Value, 16> path;
431  path.push_back(childVal);
432  visiting.popUntilVal(
433  childVal, [&](Value visitingVal) { path.push_back(visitingVal); });
434  assert(path.back() == childVal);
435  path.pop_back();
436 
437  // Find a value we can name
438  auto *it =
439  llvm::find_if(path, [&](Value v) { return !getName(v).empty(); });
440  if (it == path.end()) {
441  errorDiag.append(", but unable to find names for any involved values.");
442  errorDiag.attachNote(childVal.getLoc()) << "cycle detected here";
443  return;
444  }
445  errorDiag.append(", sample path: ");
446 
447  bool lastWasDots = false;
448  errorDiag << module.getName() << ".{" << getName(*it);
449  for (auto v :
450  llvm::concat<Value>(llvm::make_range(std::next(it), path.end()),
451  llvm::make_range(path.begin(), std::next(it)))) {
452  auto name = getName(v);
453  if (!name.empty()) {
454  errorDiag << " <- " << name;
455  lastWasDots = false;
456  } else {
457  if (!lastWasDots)
458  errorDiag << " <- ...";
459  lastWasDots = true;
460  }
461  }
462  errorDiag << "}";
463  }
464 
465  LogicalResult handleConnects(Value dst,
466  SmallVector<FieldRef> &inputArgFields) {
467 
468  bool onlyFieldZero = true;
469  auto pathsToOutPort = [&](FieldRef dstFieldRef) {
470  if (dstFieldRef.getFieldID() != 0)
471  onlyFieldZero = false;
472  if (!isa<BlockArgument>(dstFieldRef.getValue())) {
473  return failure();
474  }
475  onlyFieldZero = false;
476  for (auto inArg : inputArgFields) {
477  portPaths[inArg].insert(dstFieldRef);
478  }
479  return success();
480  };
481  forallRefersTo(dst, pathsToOutPort);
482 
483  if (onlyFieldZero) {
484  if (isa<RegOp, RegResetOp, SubfieldOp, SubaccessOp, SubindexOp>(
485  dst.getDefiningOp()))
486  return failure();
487  }
488  return success();
489  }
490 
491  void setValRefsTo(Value val, FieldRef ref) {
492  assert(val && ref && " Value and Ref cannot be null");
493  valRefersTo[val].insert(ref);
494  auto fToVIter = fieldToVals.find(ref);
495  if (fToVIter != fieldToVals.end()) {
496  for (auto aliasingVal : fToVIter->second) {
497  aliasingValuesMap[val].insert(aliasingVal);
498  aliasingValuesMap[aliasingVal].insert(val);
499  }
500  fToVIter->getSecond().insert(val);
501  } else
502  fieldToVals[ref].insert(val);
503  }
504 
505  void
506  forallRefersTo(Value val,
507  const llvm::function_ref<LogicalResult(FieldRef &refNode)> f,
508  bool baseCase = true) {
509  auto refersToIter = valRefersTo.find(val);
510  if (refersToIter != valRefersTo.end()) {
511  for (auto ref : refersToIter->second)
512  if (f(ref).failed())
513  return;
514  } else if (baseCase) {
515  FieldRef base(val, 0);
516  if (f(base).failed())
517  return;
518  }
519  }
520 
521  void dump() {
522  for (const auto &valRef : valRefersTo) {
523  llvm::dbgs() << "\n val :" << valRef.first;
524  for (auto node : valRef.second)
525  llvm::dbgs() << "\n Refers to :" << getFieldName(node).first;
526  }
527  for (const auto &dtv : fieldToVals) {
528  llvm::dbgs() << "\n Field :" << getFieldName(dtv.first).first
529  << " ::" << dtv.first.getValue();
530  for (auto val : dtv.second)
531  llvm::dbgs() << "\n val :" << val;
532  }
533  for (const auto &p : portPaths) {
534  llvm::dbgs() << "\n Output port : " << getFieldName(p.first).first
535  << " has comb path from :";
536  for (const auto &src : p.second)
537  llvm::dbgs() << "\n Input port : " << getFieldName(src).first;
538  }
539  }
540 
541  FModuleOp module;
543  /// Map of a Value to all the FieldRefs that it refers to.
544  DenseMap<Value, SetOfFieldRefs> valRefersTo;
545 
546  DenseMap<Value, DenseSet<Value>> aliasingValuesMap;
547 
548  DenseMap<FieldRef, DenseSet<Value>> fieldToVals;
549  /// Comb paths that exist between module ports. This is maintained across
550  /// modules.
551  DenseMap<FieldRef, SetOfFieldRefs> &portPaths;
552 };
553 
554 /// This pass constructs a local graph for each module to detect combinational
555 /// cycles. To capture the cross-module combinational cycles, this pass inlines
556 /// the combinational paths between IOs of its subinstances into a subgraph and
557 /// encodes them in a `combPathsMap`.
558 class CheckCombLoopsPass : public CheckCombLoopsBase<CheckCombLoopsPass> {
559 public:
560  void runOnOperation() override {
561  auto &instanceGraph = getAnalysis<InstanceGraph>();
562  DenseMap<FieldRef, SetOfFieldRefs> portPaths;
563  // Traverse modules in a post order to make sure the combinational paths
564  // between IOs of a module have been detected and recorded in `portPaths`
565  // before we handle its parent modules.
566  for (auto *igNode : llvm::post_order<InstanceGraph *>(&instanceGraph)) {
567  if (auto module = dyn_cast<FModuleOp>(*igNode->getModule())) {
568  DiscoverLoops rdf(module, instanceGraph, portPaths);
569  if (rdf.processModule().failed()) {
570  return signalPassFailure();
571  }
572  }
573  }
574  markAllAnalysesPreserved();
575  }
576 };
577 
578 std::unique_ptr<mlir::Pass> circt::firrtl::createCheckCombLoopsPass() {
579  return std::make_unique<CheckCombLoopsPass>();
580 }
assert(baseType &&"element must be base type")
DenseSet< FieldRef > SetOfFieldRefs
static void dump(DIVariable &variable, raw_indented_ostream &os)
static InstancePath empty
This pass constructs a local graph for each module to detect combinational cycles.
void runOnOperation() override
LogicalResult processModule()
void reportLoopFound(Value childVal, VisitingSet visiting)
void handleInstanceOp(InstanceOp ins, SmallVector< Value > &worklist)
DenseMap< Value, SetOfFieldRefs > valRefersTo
Map of a Value to all the FieldRefs that it refers to.
void preprocess(SmallVector< Value > &worklist)
DenseMap< FieldRef, DenseSet< Value > > fieldToVals
DiscoverLoops(FModuleOp module, InstanceGraph &instanceGraph, DenseMap< FieldRef, SetOfFieldRefs > &portPaths)
void forallRefersTo(Value val, const llvm::function_ref< LogicalResult(FieldRef &refNode)> f, bool baseCase=true)
InstanceGraph & instanceGraph
DenseMap< FieldRef, SetOfFieldRefs > & portPaths
Comb paths that exist between module ports.
LogicalResult handleConnects(Value dst, SmallVector< FieldRef > &inputArgFields)
DenseMap< Value, DenseSet< Value > > aliasingValuesMap
void setValRefsTo(Value val, FieldRef ref)
void handlePorts(FieldRef ref, SmallVectorImpl< Value > &children)
This class represents a reference to a specific field or element of an aggregate value.
Definition: FieldRef.h:28
unsigned getFieldID() const
Get the field ID of this FieldRef, which is a unique identifier mapped to a specific field in a bundl...
Definition: FieldRef.h:59
Value getValue() const
Get the Value which created this location.
Definition: FieldRef.h:37
Operation * getDefiningOp() const
Get the operation which defines this field.
Definition: FieldRef.cpp:19
This graph tracks modules and where they are instantiated.
def connect(destination, source)
Definition: support.py:37
std::unique_ptr< mlir::Pass > createCheckCombLoopsPass()
std::pair< std::string, bool > getFieldName(const FieldRef &fieldRef, bool nameSafe=false)
Get a string identifier representing the FieldRef.
StringAttr getName(ArrayAttr names, size_t idx)
Return the name at the specified index of the ArrayAttr or null if it cannot be determined.
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
Definition: DebugAnalysis.h:21
mlir::raw_indented_ostream & dbgs()
Definition: Utility.h:28
A value is in VisitingSet if its subtree is still being traversed.
DenseMap< Value, unsigned > valToStackMap
This map of the Visiting values, is for faster query, to check if a Value is in VisitingSet.
bool contains(Value v)
SmallVector< SmallVector< Value, 2 > > visitingStack
The stack is maintained to keep track of the cycle, if one is found.
void appendToEnd(SmallVector< Value > &values)
void popUntilVal(Value v, const llvm::function_ref< void(Value poppedVal)> f={})
void appendEmpty()