40 #include "llvm/ADT/DenseMap.h"
41 #include "llvm/ADT/EquivalenceClasses.h"
42 #include "llvm/ADT/PostOrderIterator.h"
44 #define DEBUG_TYPE "check-comb-loops"
46 using namespace circt;
47 using namespace firrtl;
60 SmallVector<std::pair<FieldRef, SmallVector<unsigned>>, 64>;
65 const DenseMap<FModuleLike, DrivenBysMapType> &otherModulePortPaths,
67 : module(module), instanceGraph(instanceGraph),
68 modulePortPaths(otherModulePortPaths), portPaths(thisModulePortPaths) {}
71 LLVM_DEBUG(llvm::dbgs() <<
"\n processing module :" << module.getName());
72 constructConnectivityGraph(module);
73 return dfsTraverse(drivenBy);
77 LLVM_DEBUG(llvm::dbgs() <<
"\n Module :" << module.getName());
80 for (
auto port : module.getArguments()) {
81 if (module.getPortDirection(port.getArgNumber()) !=
Direction::Out)
85 getOrAddNode(FieldRef(port, index));
89 bool foreignOps =
false;
90 walk(module, [&](Operation *op) {
91 llvm::TypeSwitch<Operation *>(op)
92 .Case<RegOp, RegResetOp>([&](
auto) {})
93 .Case<Forceable>([&](Forceable forceableOp) {
95 if (
auto node = dyn_cast<NodeOp>(op))
96 recordDataflow(node.getData(), node.getInput());
97 if (!forceableOp.isForceable() ||
98 forceableOp.getDataRef().use_empty())
100 auto data = forceableOp.getData();
101 auto ref = forceableOp.getDataRef();
103 recordDataflow(ref,
data);
104 recordProbe(
data, ref);
106 .Case<MemOp>([&](MemOp mem) { handleMemory(mem); })
107 .Case<RefSendOp>([&](RefSendOp send) {
108 recordDataflow(send.getResult(), send.getBase());
110 .Case<RefDefineOp>([&](RefDefineOp def) {
112 recordDataflow(def.getDest(), def.getSrc());
113 if (!def.getDest().getType().getForceable())
116 probesReferToSameData(def.getSrc(), def.getDest());
118 .Case<RefForceOp, RefForceInitialOp>(
119 [&](
auto ref) { handleRefForce(ref.getDest(), ref.getSrc()); })
120 .Case<InstanceOp>([&](
auto inst) { handleInstanceOp(inst); })
121 .Case<SubindexOp>([&](SubindexOp sub) {
122 recordValueRefersToFieldRef(
124 sub.getInput().getType().base().getFieldID(sub.getIndex()),
127 .Case<SubfieldOp>([&](SubfieldOp sub) {
128 recordValueRefersToFieldRef(
130 sub.getInput().getType().base().getFieldID(sub.getFieldIndex()),
133 .Case<SubaccessOp>([&](SubaccessOp sub) {
134 auto vecType = sub.getInput().getType().base();
135 auto input = sub.getInput();
136 auto result = sub.getResult();
139 for (
size_t index = 0; index < vecType.getNumElements(); ++index)
140 recordValueRefersToFieldRef(input, vecType.getFieldID(index),
143 .Case<RefSubOp>([&](RefSubOp sub) {
144 size_t fieldID = TypeSwitch<FIRRTLBaseType, size_t>(
145 sub.getInput().getType().getType())
146 .Case<FVectorType, BundleType>([&](
auto type) {
147 return type.getFieldID(sub.getIndex());
149 recordValueRefersToFieldRef(sub.getInput(), fieldID,
152 .Case<BundleCreateOp, VectorCreateOp>([&](
auto op) {
153 auto type = op.getType();
154 auto res = op.getResult();
155 auto getFieldId = [&](
unsigned index) {
157 TypeSwitch<FIRRTLBaseType, size_t>(type)
158 .Case<FVectorType, BundleType>(
159 [&](
auto type) {
return type.getFieldID(index); });
162 for (
auto [index, v] : llvm::enumerate(op.getOperands()))
163 recordValueRefersToFieldRef(res, getFieldId(index), v);
165 .Case<FConnectLike>([&](FConnectLike
connect) {
168 .Case<mlir::UnrealizedConversionCastOp>([&](
auto) {
172 for (
auto res : op->getResults())
173 for (
auto src : op->getOperands())
174 recordDataflow(res, src);
176 .Default([&](Operation *op) {
178 if (!op->getDialect() ||
179 !isa<FIRRTLDialect, chirrtl::CHIRRTLDialect>(
181 if (!foreignOps && op->getNumResults() > 0 &&
182 op->getNumOperands() > 0) {
183 op->emitRemark(
"Non-firrtl operations detected, combinatorial "
184 "loop checking may miss some loops.");
190 if (op->getNumResults() == 1) {
191 auto res = op->getResult(0);
192 for (
auto src : op->getOperands())
193 recordDataflow(res, src);
202 auto iter = valToFieldRefs.find(v);
203 if (iter == valToFieldRefs.end())
204 return getOrAddNode({v, 0});
205 return getOrAddNode(*iter->second.begin());
210 auto iter = nodes.find(f);
211 if (iter != nodes.end())
214 auto id = drivenBy.size();
218 drivenBy.push_back({f, {}});
226 auto srcNode = getOrAddNode(src);
227 auto dstNode = getOrAddNode(dst);
228 drivenBy[dstNode].second.push_back(srcNode);
234 if (
auto *def = srcVal.getDefiningOp())
235 if (def->hasTrait<OpTrait::ConstantLike>())
240 auto dstIt = valToFieldRefs.find(dstVal);
241 auto srcIt = valToFieldRefs.find(srcVal);
246 if (dstIt == valToFieldRefs.end())
247 if (
auto *def = dstVal.getDefiningOp())
248 if (isa<RegOp, RegResetOp, SubaccessOp, SubfieldOp, SubindexOp,
256 if (!(srcValType && dstValType))
257 return addDrivenBy({dstVal, 0}, {srcVal, 0});
263 if (dstValType && !dstValType.isGround())
268 if (srcValType == dstValType) {
275 }
else if (srcValType && !srcValType.isGround())
285 addDrivenBy(dst, src);
294 if (dstIt == valToFieldRefs.end() && srcIt == valToFieldRefs.end())
295 return addDef({dstVal, 0}, {srcVal, 0});
298 if (dstIt == valToFieldRefs.end() && srcIt != valToFieldRefs.end()) {
299 llvm::for_each(srcIt->getSecond(), [&](
const FieldRef &srcField) {
300 addDef(FieldRef(dstVal, 0), srcField);
306 if (dstIt != valToFieldRefs.end() && srcIt == valToFieldRefs.end()) {
307 llvm::for_each(dstIt->getSecond(), [&](
const FieldRef &dstField) {
308 addDef(dstField, FieldRef(srcVal, 0));
314 llvm::for_each(srcIt->second, [&](
const FieldRef &srcField) {
315 llvm::for_each(dstIt->second, [&](const FieldRef &dstField) {
316 addDef(dstField, srcField);
323 recordDataflow(dstProbe, srcVal);
324 auto dstNode = getOrAddNode(dstProbe);
326 auto leader = rwProbeClasses.findLeader(dstNode);
327 if (leader == rwProbeClasses.member_end())
329 auto iter = rwProbeRefersTo.find(*leader);
334 if (iter == rwProbeRefersTo.end())
337 assert(iter != rwProbeRefersTo.end());
338 if (iter->second != dstNode)
339 drivenBy[iter->second].second.push_back(getOrAddNode(srcVal));
346 auto refMod = inst.getReferencedModule<FModuleOp>(instanceGraph);
350 auto modulePaths = modulePortPaths.find(refMod);
351 if (modulePaths == modulePortPaths.end())
366 for (
auto &path : modulePaths->second) {
367 auto modSinkPortField = path.first;
369 cast<BlockArgument>(modSinkPortField.getValue()).getArgNumber();
370 FieldRef sinkPort(inst.getResult(sinkArgNum),
371 modSinkPortField.getFieldID());
372 auto sinkNode = getOrAddNode(sinkPort);
373 bool sinkPortIsForceable =
false;
374 if (
auto refResultType =
375 type_dyn_cast<RefType>(inst.getResult(sinkArgNum).getType()))
376 sinkPortIsForceable = refResultType.getForceable();
378 DenseSet<unsigned> setOfEquivalentRWProbes;
379 unsigned minArgNum = sinkArgNum;
380 unsigned basePortNode = sinkNode;
381 for (
auto &modSrcPortField : path.second) {
383 cast<BlockArgument>(modSrcPortField.getValue()).getArgNumber();
385 if (modSrcPortField == modSinkPortField)
388 FieldRef srcPort(inst.getResult(srcArgNum),
389 modSrcPortField.getFieldID());
390 bool srcPortIsForceable =
false;
391 if (
auto refResultType =
392 type_dyn_cast<RefType>(inst.getResult(srcArgNum).getType()))
393 srcPortIsForceable = refResultType.getForceable();
396 if (sinkPortIsForceable && srcPortIsForceable) {
397 auto srcNode = getOrAddNode(srcPort);
399 if (rwProbeClasses.findLeader(srcNode) !=
400 rwProbeClasses.member_end() &&
401 rwProbeClasses.findLeader(sinkNode) ==
402 rwProbeClasses.findLeader(srcNode))
405 auto drivenBysToSrcPort = modulePaths->second.find(modSrcPortField);
406 if (drivenBysToSrcPort != modulePaths->second.end())
407 if (llvm::find(drivenBysToSrcPort->second, modSinkPortField) !=
408 drivenBysToSrcPort->second.end()) {
414 setOfEquivalentRWProbes.insert(srcNode);
415 if (minArgNum > srcArgNum) {
418 minArgNum = srcArgNum;
419 basePortNode = srcNode;
424 addDrivenBy(sinkPort, srcPort);
426 if (setOfEquivalentRWProbes.empty())
430 for (
auto probe : setOfEquivalentRWProbes)
431 rwProbeClasses.unionSets(probe, sinkNode);
436 auto leader = rwProbeClasses.getLeaderValue(sinkNode);
437 rwProbeRefersTo[leader] = basePortNode;
439 setOfEquivalentRWProbes.insert(sinkNode);
441 for (
auto probe : setOfEquivalentRWProbes)
442 if (probe != basePortNode)
443 drivenBy[probe].second.push_back(basePortNode);
452 auto it = valToFieldRefs.find(base);
453 if (it != valToFieldRefs.end()) {
456 SmallVector<FieldRef> entry;
457 for (
auto &sub : it->second)
458 entry.emplace_back(sub.getValue(), sub.getFieldID() + fieldID);
460 valToFieldRefs[result].append(entry.begin(), entry.end());
464 if (
auto *def = base.getDefiningOp()) {
465 if (isa<RegOp, RegResetOp, SubfieldOp, SubindexOp, SubaccessOp>(def))
468 valToFieldRefs[result].emplace_back(base, fieldID);
472 if (mem.getReadLatency() > 0)
475 for (
auto memPort : mem.getResults())
477 if (
auto type = type_dyn_cast<BundleType>(memPort.getType())) {
481 addDrivenBy({memPort,
static_cast<unsigned int>(dataFieldId)},
482 {memPort,
static_cast<unsigned int>(enableFieldId)});
483 addDrivenBy({memPort,
static_cast<unsigned int>(dataFieldId)},
484 {memPort,
static_cast<unsigned int>(addressFieldId)});
491 auto numNodes = graph.size();
492 SmallVector<bool> onStack(numNodes,
false);
493 SmallVector<unsigned> dfsStack;
495 auto hasCycle = [&](
unsigned rootNode, DenseSet<unsigned> &visited,
496 bool recordPortPaths =
false) {
497 if (visited.contains(rootNode))
499 dfsStack.push_back(rootNode);
501 while (!dfsStack.empty()) {
502 auto currentNode = dfsStack.back();
504 if (!visited.contains(currentNode)) {
505 visited.insert(currentNode);
506 onStack[currentNode] =
true;
507 LLVM_DEBUG(llvm::dbgs()
509 << drivenBy[currentNode].first.getValue().getType()
510 << drivenBy[currentNode].first.getValue() <<
","
511 << drivenBy[currentNode].first.getFieldID() <<
"\n"
512 <<
getName(drivenBy[currentNode].first));
514 FieldRef currentF = drivenBy[currentNode].first;
515 if (recordPortPaths && currentNode != rootNode) {
516 if (isa<mlir::BlockArgument>(currentF.
getValue()))
517 portPaths[drivenBy[rootNode].first].insert(currentF);
520 addToPortPathsIfRWProbe(currentNode,
521 portPaths[drivenBy[rootNode].first]);
524 onStack[currentNode] =
false;
528 for (
auto neighbor : graph[currentNode].second) {
529 if (!visited.contains(neighbor)) {
530 dfsStack.push_back(neighbor);
531 }
else if (onStack[neighbor]) {
533 SmallVector<FieldRef, 16> path;
534 auto loopNode = neighbor;
537 SmallVector<unsigned>::iterator it =
538 llvm::find_if(drivenBy[loopNode].second,
539 [&](
unsigned node) {
return onStack[node]; });
540 if (it == drivenBy[loopNode].second.end())
543 path.push_back(drivenBy[loopNode].first);
545 }
while (loopNode != neighbor);
547 reportLoopFound(path, drivenBy[neighbor].first.getLoc());
555 DenseSet<unsigned> visited;
556 for (
unsigned node = 0; node < graph.size(); ++node) {
558 if (
auto arg = dyn_cast<BlockArgument>(drivenBy[node].first.getValue()))
559 if (module.getPortDirection(arg.getArgNumber()) ==
Direction::Out) {
566 if (hasCycle(node, visited,
isPort).failed())
573 auto errorDiag = mlir::emitError(
574 module.getLoc(),
"detected combinational cycle in a FIRRTL module");
576 std::string firstName;
579 return !firstName.empty();
581 if (it == path.end()) {
582 errorDiag.append(
", but unable to find names for any involved values.");
583 errorDiag.attachNote(loc) <<
"cycle detected here";
589 auto n =
getName(*findStartIt);
590 if (!n.empty() && n < firstName) {
595 errorDiag.append(
", sample path: ");
597 bool lastWasDots =
false;
598 errorDiag << module.getName() <<
".{" <<
getName(*it);
599 for (
auto v : llvm::concat<FieldRef>(
600 llvm::make_range(std::next(it), path.end()),
601 llvm::make_range(path.begin(), std::next(it)))) {
604 errorDiag <<
" <- " << name;
608 errorDiag <<
" <- ...";
617 llvm::dbgs() <<
"\n Connectivity Graph ==>";
618 for (
const auto &[index, i] : llvm::enumerate(drivenBy)) {
619 llvm::dbgs() <<
"\n ===>dst:" <<
getName(i.first)
620 <<
"::" << i.first.getValue();
621 for (
auto s : i.second)
622 llvm::dbgs() <<
"<---" <<
getName(drivenBy[s].first)
623 <<
"::" << drivenBy[s].first.getValue();
626 llvm::dbgs() <<
"\n Value to FieldRef :";
627 for (
const auto &fields : valToFieldRefs) {
628 llvm::dbgs() <<
"\n Val:" << fields.first;
629 for (
auto f : fields.second)
630 llvm::dbgs() <<
", FieldRef:" <<
getName(f) <<
"::" << f.getFieldID();
632 llvm::dbgs() <<
"\n Port paths:";
633 for (
const auto &p : portPaths) {
634 llvm::dbgs() <<
"\n Output :" <<
getName(p.first);
635 for (
auto i : p.second)
636 llvm::dbgs() <<
"\n Input :" <<
getName(i);
638 llvm::dbgs() <<
"\n rwprobes:";
639 for (
auto node : rwProbeRefersTo) {
640 llvm::dbgs() <<
"\n node:" <<
getName(drivenBy[node.first].first)
641 <<
"=> probe:" <<
getName(drivenBy[node.second].first);
643 for (
auto i = rwProbeClasses.begin(), e = rwProbeClasses.end(); i != e;
648 llvm::interleave(llvm::make_range(rwProbeClasses.member_begin(i),
649 rwProbeClasses.member_end()),
651 llvm::dbgs() <<
"\n dataflow at leader::" << i->getData() <<
"\n =>"
652 << rwProbeRefersTo[i->getData()];
653 llvm::dbgs() <<
"\n Done\n";
659 auto refNode = getOrAddNode(ref);
660 auto dataNode = getOrAddNode(
data);
661 rwProbeRefersTo[rwProbeClasses.getOrInsertLeaderValue(refNode)] = dataNode;
667 auto p1Node = getOrAddNode(probe1);
668 auto p2Node = getOrAddNode(probe2);
669 rwProbeClasses.unionSets(p1Node, p2Node);
673 DenseSet<FieldRef> &inputPortPaths) {
675 auto baseFieldRef = drivenBy[srcNode].first;
676 if (
auto defOp = dyn_cast_or_null<Forceable>(baseFieldRef.getDefiningOp()))
677 if (defOp.isForceable() && !defOp.getDataRef().use_empty()) {
680 rwProbeClasses.getLeaderValue(getOrAddNode(defOp.getDataRef()));
684 llvm::make_range(rwProbeClasses.member_begin(
685 rwProbeClasses.findValue(rwProbeNode)),
686 rwProbeClasses.member_end())) {
687 auto probeVal = drivenBy[probe].first;
690 if (probeVal.getValue().isa<BlockArgument>()) {
691 inputPortPaths.insert(probeVal);
735 auto &instanceGraph = getAnalysis<InstanceGraph>();
736 DenseMap<FModuleLike, DrivenBysMapType> modulePortPaths;
741 for (
auto *igNode : llvm::post_order<InstanceGraph *>(&instanceGraph)) {
742 if (
auto module = dyn_cast<FModuleOp>(*igNode->getModule())) {
744 modulePortPaths[module]);
746 return signalPassFailure();
750 markAllAnalysesPreserved();
755 return std::make_unique<CheckCombLoopsPass>();
assert(baseType &&"element must be base type")
static bool isPort(Value value)
Returns whether this value is either (1) a port on a ComponentOp or (2) a port on a cell interface.
DenseMap< FieldRef, DenseSet< FieldRef > > DrivenBysMapType
This pass constructs a local graph for each module to detect combinational cycles.
void runOnOperation() override
LogicalResult processModule()
unsigned getOrAddNode(Value v)
DenseMap< FieldRef, size_t > nodes
Map of FieldRef to its corresponding graph node.
SmallVector< std::pair< FieldRef, SmallVector< unsigned > >, 64 > DrivenByGraphType
Adjacency list representation.
DenseMap< Value, SmallVector< FieldRef > > valToFieldRefs
Map of values to the set of all FieldRefs (same base) that this may be directly derived from through ...
void handleRefForce(Value dstProbe, Value srcVal)
const DenseMap< FModuleLike, DrivenBysMapType > & modulePortPaths
Comb paths that exist between module ports.
static std::string getName(FieldRef v)
void constructConnectivityGraph(FModuleOp module)
DrivenBysMapType & portPaths
The comb paths between the ports of this module.
void recordValueRefersToFieldRef(Value base, unsigned fieldID, Value result)
void addDrivenBy(FieldRef dst, FieldRef src)
unsigned getOrAddNode(FieldRef f)
void recordProbe(Value data, Value ref)
InstanceGraph & instanceGraph
void handleMemory(MemOp mem)
DrivenByGraphType drivenBy
This is an adjacency list representation of the connectivity graph.
void recordDataflow(Value dstVal, Value srcVal)
void handleInstanceOp(InstanceOp inst)
void probesReferToSameData(Value probe1, Value probe2)
DenseMap< unsigned, unsigned > rwProbeRefersTo
The base value that the RWProbe refers to.
llvm::EquivalenceClasses< unsigned > rwProbeClasses
An eqv class of all the RWProbes that refer to the same base value.
void reportLoopFound(SmallVectorImpl< FieldRef > &path, Location loc)
LogicalResult dfsTraverse(const DrivenByGraphType &graph)
void addToPortPathsIfRWProbe(unsigned srcNode, DenseSet< FieldRef > &inputPortPaths)
DiscoverLoops(FModuleOp module, InstanceGraph &instanceGraph, const DenseMap< FModuleLike, DrivenBysMapType > &otherModulePortPaths, DrivenBysMapType &thisModulePortPaths)
This class represents a reference to a specific field or element of an aggregate value.
FieldRef getSubField(unsigned subFieldID) const
Get a reference to a subfield.
Value getValue() const
Get the Value which created this location.
This graph tracks modules and where they are instantiated.
def connect(destination, source)
std::unique_ptr< mlir::Pass > createCheckCombLoopsPass()
FIRRTLBaseType getBaseType(Type type)
If it is a base type, return it as is.
void walkGroundTypes(FIRRTLType firrtlType, llvm::function_ref< void(uint64_t, FIRRTLBaseType, bool)> fn)
Walk leaf ground types in the firrtlType and apply the function fn.
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.
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.