1 files changed, 54 insertions, 13 deletions

diff --git a/passes/cmds/scc.cc b/passes/cmds/scc.cc
index f7f50ab2a..bb6d74474 100644
--- a/passes/cmds/scc.cc
+++ b/passes/cmds/scc.cc
@@ -2,11 +2,11 @@
  *  yosys -- Yosys Open SYnthesis Suite
  *
  *  Copyright (C) 2012  Clifford Wolf <clifford@clifford.at>
- *  
+ *
  *  Permission to use, copy, modify, and/or distribute this software for any
  *  purpose with or without fee is hereby granted, provided that the above
  *  copyright notice and this permission notice appear in all copies.
- *  
+ *
  *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
@@ -18,7 +18,7 @@
  */
 
 // [[CITE]] Tarjan's strongly connected components algorithm
-// Tarjan, R. E. (1972), "Depth-first search and linear graph algorithms", SIAM Journal on Computing 1 (2): 146–160, doi:10.1137/0201010
+// Tarjan, R. E. (1972), "Depth-first search and linear graph algorithms", SIAM Journal on Computing 1 (2): 146-160, doi:10.1137/0201010
 // http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm
 
 #include "kernel/register.h"
@@ -69,10 +69,10 @@ struct SccWorker
 		for (auto nextCell : cellToNextCell[cell])
 			if (cellLabels.count(nextCell) == 0) {
 				run(nextCell, depth+1, maxDepth);
-				cellLabels[cell].second = std::min(cellLabels[cell].second, cellLabels[nextCell].second);
+				cellLabels[cell].second = min(cellLabels[cell].second, cellLabels[nextCell].second);
 			} else
 			if (cellsOnStack.count(nextCell) > 0 && (maxDepth < 0 || cellDepth[nextCell] + maxDepth > depth)) {
-					cellLabels[cell].second = std::min(cellLabels[cell].second, cellLabels[nextCell].second);
+					cellLabels[cell].second = min(cellLabels[cell].second, cellLabels[nextCell].second);
 			}
 
 		if (cellLabels[cell].first == cellLabels[cell].second)
@@ -100,7 +100,8 @@ struct SccWorker
 		}
 	}
 
-	SccWorker(RTLIL::Design *design, RTLIL::Module *module, bool allCellTypes, int maxDepth) : design(design), module(module), sigmap(module)
+	SccWorker(RTLIL::Design *design, RTLIL::Module *module, bool nofeedbackMode, bool allCellTypes, int maxDepth) :
+			design(design), module(module), sigmap(module)
 	{
 		if (module->processes.size() > 0) {
 			log("Skipping module %s as it contains processes (run 'proc' pass first).\n", module->name.c_str());
@@ -167,10 +168,22 @@ struct SccWorker
 		labelCounter = 0;
 		cellLabels.clear();
 
-		while (workQueue.size() > 0) {
+		while (workQueue.size() > 0)
+		{
 			RTLIL::Cell *cell = *workQueue.begin();
 			log_assert(cellStack.size() == 0);
 			cellDepth.clear();
+
+			if (!nofeedbackMode && cellToNextCell[cell].count(cell)) {
+				log("Found an SCC:");
+				std::set<RTLIL::Cell*> scc;
+				log(" %s", RTLIL::id2cstr(cell->name));
+				cell2scc[cell] = sccList.size();
+				scc.insert(cell);
+				sccList.push_back(scc);
+				log("\n");
+			}
+
 			run(cell, 0, maxDepth);
 		}
 
@@ -212,10 +225,18 @@ struct SccPass : public Pass {
 		log("This command identifies strongly connected components (aka logic loops) in the\n");
 		log("design.\n");
 		log("\n");
+		log("    -expect <num>\n");
+		log("        expect to find exactly <num> SSCs. A different number of SSCs will\n");
+		log("        produce an error.\n");
+		log("\n");
 		log("    -max_depth <num>\n");
-		log("        limit to loops not longer than the specified number of cells. This can\n");
-		log("        e.g. be useful in identifying local loops in a module that turns out\n");
-		log("        to be one gigantic SCC.\n");
+		log("        limit to loops not longer than the specified number of cells. This\n");
+		log("        can e.g. be useful in identifying small local loops in a module that\n");
+		log("        implements one large SCC.\n");
+		log("\n");
+		log("    -nofeedback\n");
+		log("        do not count cells that have their output fed back into one of their\n");
+		log("        inputs as single-cell scc.\n");
 		log("\n");
 		log("    -all_cell_types\n");
 		log("        Usually this command only considers internal non-memory cells. With\n");
@@ -239,9 +260,11 @@ struct SccPass : public Pass {
 		std::map<std::string, std::string> setCellAttr, setWireAttr;
 		bool allCellTypes = false;
 		bool selectMode = false;
+		bool nofeedbackMode = false;
 		int maxDepth = -1;
+		int expect = -1;
 
-		log_header("Executing SCC pass (detecting logic loops).\n");
+		log_header(design, "Executing SCC pass (detecting logic loops).\n");
 
 		size_t argidx;
 		for (argidx = 1; argidx < args.size(); argidx++) {
@@ -249,6 +272,14 @@ struct SccPass : public Pass {
 				maxDepth = atoi(args[++argidx].c_str());
 				continue;
 			}
+			if (args[argidx] == "-expect" && argidx+1 < args.size()) {
+				expect = atoi(args[++argidx].c_str());
+				continue;
+			}
+			if (args[argidx] == "-nofeedback") {
+				nofeedbackMode = true;
+				continue;
+			}
 			if (args[argidx] == "-all_cell_types") {
 				allCellTypes = true;
 				continue;
@@ -282,16 +313,26 @@ struct SccPass : public Pass {
 			log_cmd_error("The -set*_attr options are not implemented at the moment!\n");
 
 		RTLIL::Selection newSelection(false);
+		int scc_counter = 0;
 
 		for (auto &mod_it : design->modules_)
 			if (design->selected(mod_it.second))
 			{
-				SccWorker worker(design, mod_it.second, allCellTypes, maxDepth);
+				SccWorker worker(design, mod_it.second, nofeedbackMode, allCellTypes, maxDepth);
+				scc_counter += GetSize(worker.sccList);
 
 				if (selectMode)
 					worker.select(newSelection);
 			}
 
+		if (expect >= 0) {
+			if (scc_counter == expect)
+				log("Found and expected %d SCCs.\n", scc_counter);
+			else
+				log_error("Found %d SCCs but expected %d.\n", scc_counter, expect);
+		} else
+			log("Found %d SCCs.\n", scc_counter);
+
 		if (selectMode) {
 			log_assert(origSelectPos >= 0);
 			design->selection_stack[origSelectPos] = newSelection;
@@ -299,5 +340,5 @@ struct SccPass : public Pass {
 		}
 	}
 } SccPass;
- 
+
 PRIVATE_NAMESPACE_END