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"
43 #define DEBUG_TYPE "check-comb-loops"
45 using namespace circt;
46 using namespace firrtl;
68 auto stackSize = visitingStack.size() - 1;
69 visitingStack.back().append(values.begin(), values.end());
71 llvm::for_each(values, [&](Value v) { valToStackMap[v] = stackSize; });
74 return valToStackMap.find(v) != valToStackMap.end();
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();
84 llvm::for_each(poppedVals, [&](Value pv) {
87 valToStackMap.erase(pv);
99 DenseMap<FieldRef, SetOfFieldRefs> &portPaths)
100 : module(module), instanceGraph(instanceGraph), portPaths(portPaths) {}
103 LLVM_DEBUG(
llvm::dbgs() <<
"\n processing module :" << module.getName());
104 SmallVector<Value> worklist;
108 preprocess(worklist);
110 llvm::DenseSet<Value> visited;
112 SmallVector<Value> dfsStack;
113 SmallVector<FieldRef> inputArgFields;
115 SmallVector<Value, 8> children;
119 SmallVector<FieldRef, 2> inputArgFieldsTemp;
120 SmallVector<Value> aliasingValues;
123 for (
auto root : worklist) {
125 inputArgFields.clear();
126 LLVM_DEBUG(
llvm::dbgs() <<
"\n Starting traversal from root :"
128 if (
auto inArg = dyn_cast<BlockArgument>(root)) {
129 if (module.getPortDirection(inArg.getArgNumber()) ==
Direction::In)
136 while (!dfsStack.empty()) {
137 auto dfsVal = dfsStack.back();
139 unsigned dfsSize = dfsStack.size();
150 inputArgFieldsTemp.clear();
153 aliasingValues = {dfsVal};
154 auto aToVIter = aliasingValuesMap.find(dfsVal);
155 if (aToVIter != aliasingValuesMap.end()) {
156 aliasingValues.append(aToVIter->getSecond().begin(),
157 aToVIter->getSecond().end());
161 forallRefersTo(dfsVal, [&](
FieldRef ref) {
165 handlePorts(ref, children);
168 if (
auto arg = dyn_cast<BlockArgument>(ref.
getValue()))
169 if (module.getPortDirection(arg.getArgNumber()) ==
Direction::In)
170 inputArgFieldsTemp.push_back(ref);
174 if (!inputArgFieldsTemp.empty())
175 inputArgFields = std::move(inputArgFieldsTemp);
178 visited.insert(aliasingValues.begin(), aliasingValues.end());
180 for (
auto dfsFromVal : aliasingValues) {
182 for (
auto &use : dfsFromVal.getUses()) {
184 TypeSwitch<Operation *, Value>(use.getOwner())
186 .Case<RegOp, RegResetOp>([](
auto _) {
return Value(); })
188 .Case<Forceable>([](
auto op) {
return op.getDataRaw(); })
190 .Case<FConnectLike>([&](FConnectLike
connect) -> Value {
191 if (use.getOperandNumber() == 1) {
193 if (handleConnects(dst, inputArgFields).succeeded())
200 .Default([](
auto op) -> Value {
201 if (op->getNumResults() == 1)
202 return op->getResult(0);
205 if (childVal && type_isa<FIRRTLType>(childVal.getType()))
206 children.push_back(childVal);
209 for (
auto childVal : children) {
212 if (!visited.contains(childVal))
213 dfsStack.push_back(childVal);
218 reportLoopFound(childVal, visiting);
223 if (dfsSize != dfsStack.size())
232 auto popped = dfsStack.pop_back_val();
250 for (BlockArgument arg : module.getArguments()) {
251 auto argType = type_cast<FIRRTLType>(arg.getType());
252 if (type_isa<RefType>(argType))
254 if (module.getPortDirection(arg.getArgNumber()) ==
Direction::In)
255 worklist.push_back(arg);
256 if (!argType.isGround())
257 setValRefsTo(arg,
FieldRef(arg, 0));
259 DenseSet<Value> memPorts;
261 for (
auto &op : module.getOps()) {
262 TypeSwitch<Operation *>(&op)
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));
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();
282 auto addressFieldId =
284 if (fieldIndex == enableFieldId || fieldIndex == dataFieldId ||
285 fieldIndex == addressFieldId) {
286 setValRefsTo(memPort,
FieldRef(memPort, 0));
290 SmallVector<FieldRef, 4> fields;
295 fields.push_back(subBase.getSubField(fieldIndex));
300 for (
auto f : fields)
301 setValRefsTo(res, f);
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;
313 fields.push_back(subBase.getSubField(index));
318 for (
auto f : fields)
319 setValRefsTo(res, f);
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;
333 for (size_t index = 0; index < vecType.getNumElements();
335 fields.push_back(subBase.getSubField(
336 1 + index * (hw::FieldIdImpl::getMaxFieldID(
337 vecType.getElementType()) +
343 for (
auto f : fields)
344 setValRefsTo(res, f);
348 [&](InstanceOp ins) { handleInstanceOp(ins, worklist); })
349 .Case<MemOp>([&](MemOp mem) {
350 if (!(mem.getReadLatency() == 0)) {
353 for (
auto memPort : mem.getResults()) {
354 if (!type_isa<FIRRTLBaseType>(memPort.getType()))
356 memPorts.insert(memPort);
359 .Default([&](
auto) {});
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);
376 if (
auto inst = dyn_cast_or_null<InstanceOp>(ref.
getDefiningOp())) {
377 auto res = cast<OpResult>(ref.
getValue());
378 auto portNum = res.getResultNumber();
380 dyn_cast_or_null<FModuleOp>(*instanceGraph.getReferencedModule(inst));
384 auto pathIter = portPaths.find(modArg);
385 if (pathIter == portPaths.end())
387 for (
auto modOutPort : pathIter->second) {
389 cast<BlockArgument>(modOutPort.getValue()).getArgNumber();
390 if (modOutPort.getFieldID() == 0) {
391 children.push_back(inst.getResult(outPortNum));
394 FieldRef instanceOutPort(inst.getResult(outPortNum),
395 modOutPort.getFieldID());
396 llvm::append_range(children, fieldToVals[instanceOutPort]);
398 }
else if (
auto mem = dyn_cast<MemOp>(ref.
getDefiningOp())) {
399 if (mem.getReadLatency() > 0)
402 auto type = type_cast<BundleType>(memPort.getType());
408 for (
auto dataField : fieldToVals[
FieldRef(memPort, dataFieldId)])
409 children.push_back(dataField);
419 if (isa_and_nonnull<SubfieldOp, SubindexOp, SubaccessOp>(
420 v.getDefiningOp())) {
427 auto errorDiag = mlir::emitError(
428 module.getLoc(),
"detected combinational cycle in a FIRRTL module");
430 SmallVector<Value, 16> path;
431 path.push_back(childVal);
433 childVal, [&](Value visitingVal) { path.push_back(visitingVal); });
434 assert(path.back() == childVal);
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";
445 errorDiag.append(
", sample path: ");
447 bool lastWasDots =
false;
448 errorDiag << module.getName() <<
".{" <<
getName(*it);
450 llvm::concat<Value>(llvm::make_range(std::next(it), path.end()),
451 llvm::make_range(path.begin(), std::next(it)))) {
454 errorDiag <<
" <- " << name;
458 errorDiag <<
" <- ...";
466 SmallVector<FieldRef> &inputArgFields) {
468 bool onlyFieldZero =
true;
469 auto pathsToOutPort = [&](
FieldRef dstFieldRef) {
470 if (dstFieldRef.getFieldID() != 0)
471 onlyFieldZero =
false;
472 if (!isa<BlockArgument>(dstFieldRef.getValue())) {
475 onlyFieldZero =
false;
476 for (
auto inArg : inputArgFields) {
477 portPaths[inArg].insert(dstFieldRef);
481 forallRefersTo(dst, pathsToOutPort);
484 if (isa<RegOp, RegResetOp, SubfieldOp, SubaccessOp, SubindexOp>(
485 dst.getDefiningOp()))
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);
500 fToVIter->getSecond().insert(val);
502 fieldToVals[ref].insert(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)
514 }
else if (baseCase) {
516 if (f(base).failed())
522 for (
const auto &valRef : valRefersTo) {
524 for (
auto node : valRef.second)
527 for (
const auto &dtv : fieldToVals) {
529 <<
" ::" << dtv.first.getValue();
530 for (
auto val : dtv.second)
533 for (
const auto &p : portPaths) {
535 <<
" has comb path from :";
536 for (
const auto &src : p.second)
561 auto &instanceGraph = getAnalysis<InstanceGraph>();
562 DenseMap<FieldRef, SetOfFieldRefs> portPaths;
566 for (
auto *igNode : llvm::post_order<InstanceGraph *>(&instanceGraph)) {
567 if (
auto module = dyn_cast<FModuleOp>(*igNode->getModule())) {
570 return signalPassFailure();
574 markAllAnalysesPreserved();
579 return std::make_unique<CheckCombLoopsPass>();
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.
unsigned getFieldID() const
Get the field ID of this FieldRef, which is a unique identifier mapped to a specific field in a bundl...
Value getValue() const
Get the Value which created this location.
Operation * getDefiningOp() const
Get the operation which defines this field.
This graph tracks modules and where they are instantiated.
def connect(destination, source)
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...
mlir::raw_indented_ostream & dbgs()
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.
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={})