passes/cmds/scc.cc - third_party/yosys - Git at Google

 /*
  *  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
  *  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  *  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  *  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  *  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  *
  */

 // [[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
 // http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm

 #include "kernel/register.h"
 #include "kernel/celltypes.h"
 #include "kernel/sigtools.h"
 #include "kernel/log.h"
 #include <stdlib.h>
 #include <stdio.h>
 #include <set>

 USING_YOSYS_NAMESPACE
 PRIVATE_NAMESPACE_BEGIN

 struct SccWorker
 {
 	RTLIL::Design *design;
 	RTLIL::Module *module;
 	SigMap sigmap;
 	CellTypes ct;

 	std::set<RTLIL::Cell*> workQueue;
 	std::map<RTLIL::Cell*, std::set<RTLIL::Cell*>> cellToNextCell;
 	std::map<RTLIL::Cell*, RTLIL::SigSpec> cellToPrevSig, cellToNextSig;

 	std::map<RTLIL::Cell*, std::pair<int, int>> cellLabels;
 	std::map<RTLIL::Cell*, int> cellDepth;
 	std::set<RTLIL::Cell*> cellsOnStack;
 	std::vector<RTLIL::Cell*> cellStack;
 	int labelCounter;

 	std::map<RTLIL::Cell*, int> cell2scc;
 	std::vector<std::set<RTLIL::Cell*>> sccList;

 	void run(RTLIL::Cell *cell, int depth, int maxDepth)
 	{
 		log_assert(workQueue.count(cell) > 0);

 		workQueue.erase(cell);
 		cellLabels[cell] = std::pair<int, int>(labelCounter, labelCounter);
 		labelCounter++;

 		cellsOnStack.insert(cell);
 		cellStack.push_back(cell);

 		if (maxDepth >= 0)
 			cellDepth[cell] = depth;

 		for (auto nextCell : cellToNextCell[cell])
 			if (cellLabels.count(nextCell) == 0) {
 				run(nextCell, depth+1, maxDepth);
 				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 = min(cellLabels[cell].second, cellLabels[nextCell].second);
 			}

 		if (cellLabels[cell].first == cellLabels[cell].second)
 		{
 			if (cellStack.back() == cell)
 			{
 				cellStack.pop_back();
 				cellsOnStack.erase(cell);
 			}
 			else
 			{
 				log("Found an SCC:");
 				std::set<RTLIL::Cell*> scc;
 				while (cellsOnStack.count(cell) > 0) {
 					RTLIL::Cell *c = cellStack.back();
 					cellStack.pop_back();
 					cellsOnStack.erase(c);
 					log(" %s", RTLIL::id2cstr(c->name));
 					cell2scc[c] = sccList.size();
 					scc.insert(c);
 				}
 				sccList.push_back(scc);
 				log("\n");
 			}
 		}
 	}

 	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());
 			return;
 		}

 		if (allCellTypes) {
 			ct.setup(design);
 		} else {
 			ct.setup_internals();
 			ct.setup_stdcells();
 		}

 		SigPool selectedSignals;
 		SigSet<RTLIL::Cell*> sigToNextCells;

 		for (auto &it : module->wires_)
 			if (design->selected(module, it.second))
 				selectedSignals.add(sigmap(RTLIL::SigSpec(it.second)));

 		for (auto &it : module->cells_)
 		{
 			RTLIL::Cell *cell = it.second;

 			if (!design->selected(module, cell))
 				continue;

 			if (!allCellTypes && !ct.cell_known(cell->type))
 				continue;

 			workQueue.insert(cell);

 			RTLIL::SigSpec inputSignals, outputSignals;

 			for (auto &conn : cell->connections())
 			{
 				bool isInput = true, isOutput = true;

 				if (ct.cell_known(cell->type)) {
 					isInput = ct.cell_input(cell->type, conn.first);
 					isOutput = ct.cell_output(cell->type, conn.first);
 				}

 				RTLIL::SigSpec sig = selectedSignals.extract(sigmap(conn.second));
 				sig.sort_and_unify();

 				if (isInput)
 					inputSignals.append(sig);
 				if (isOutput)
 					outputSignals.append(sig);
 			}

 			inputSignals.sort_and_unify();
 			outputSignals.sort_and_unify();

 			cellToPrevSig[cell] = inputSignals;
 			cellToNextSig[cell] = outputSignals;
 			sigToNextCells.insert(inputSignals, cell);
 		}

 		for (auto cell : workQueue)
 		{
 			cellToNextCell[cell] = sigToNextCells.find(cellToNextSig[cell]);

 			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");
 			}
 		}

 		labelCounter = 0;
 		cellLabels.clear();

 		while (!workQueue.empty())
 		{
 			RTLIL::Cell *cell = *workQueue.begin();
 			log_assert(cellStack.size() == 0);
 			cellDepth.clear();

 			run(cell, 0, maxDepth);
 		}

 		log("Found %d SCCs in module %s.\n", int(sccList.size()), RTLIL::id2cstr(module->name));
 	}

 	void select(RTLIL::Selection &sel)
 	{
 		for (int i = 0; i < int(sccList.size()); i++)
 		{
 			std::set<RTLIL::Cell*> &cells = sccList[i];
 			RTLIL::SigSpec prevsig, nextsig, sig;

 			for (auto cell : cells) {
 				sel.selected_members[module->name].insert(cell->name);
 				prevsig.append(cellToPrevSig[cell]);
 				nextsig.append(cellToNextSig[cell]);
 			}

 			prevsig.sort_and_unify();
 			nextsig.sort_and_unify();
 			sig = prevsig.extract(nextsig);

 			for (auto &chunk : sig.chunks())
 				if (chunk.wire != NULL)
 					sel.selected_members[module->name].insert(chunk.wire->name);
 		}
 	}
 };

 struct SccPass : public Pass {
 	SccPass() : Pass("scc", "detect strongly connected components (logic loops)") { }
 	void help() YS_OVERRIDE
 	{
 		//   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 		log("\n");
 		log("    scc [options] [selection]\n");
 		log("\n");
 		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\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");
 		log("        this option set, all cells are considered. For unknown cells all ports\n");
 		log("        are assumed to be bidirectional 'inout' ports.\n");
 		log("\n");
 		log("    -set_attr <name> <value>\n");
 		log("        set the specified attribute on all cells that are part of a logic\n");
 		log("        loop. the special token {} in the value is replaced with a unique\n");
 		log("        identifier for the logic loop.\n");
 		log("\n");
 		log("    -select\n");
 		log("        replace the current selection with a selection of all cells and wires\n");
 		log("        that are part of a found logic loop\n");
 		log("\n");
 	}
 	void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
 	{
 		std::map<std::string, std::string> setAttr;
 		bool allCellTypes = false;
 		bool selectMode = false;
 		bool nofeedbackMode = false;
 		int maxDepth = -1;
 		int expect = -1;

 		log_header(design, "Executing SCC pass (detecting logic loops).\n");

 		size_t argidx;
 		for (argidx = 1; argidx < args.size(); argidx++) {
 			if (args[argidx] == "-max_depth" && argidx+1 < args.size()) {
 				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;
 			}
 			if (args[argidx] == "-set_attr" && argidx+2 < args.size()) {
 				setAttr[args[argidx+1]] = args[argidx+2];
 				argidx += 2;
 				continue;
 			}
 			if (args[argidx] == "-select") {
 				selectMode = true;
 				continue;
 			}
 			break;
 		}
 		int origSelectPos = design->selection_stack.size() - 1;
 		extra_args(args, argidx, design);

 		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, nofeedbackMode, allCellTypes, maxDepth);

 				if (!setAttr.empty())
 				{
 					for (const auto &cells : worker.sccList)
 					{
 						for (auto attr : setAttr)
 						{
 							IdString attr_name(RTLIL::escape_id(attr.first));
 							string attr_valstr = attr.second;
 							string index = stringf("%d", scc_counter);

 							for (size_t pos = 0; (pos = attr_valstr.find("{}", pos)) != string::npos; pos += index.size())
 								attr_valstr.replace(pos, 2, index);

 							Const attr_value(attr_valstr);

 							for (auto cell : cells)
 								cell->attributes[attr_name] = attr_value;
 						}

 						scc_counter++;
 					}
 				}
 				else
 				{
 					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;
 			design->selection_stack[origSelectPos].optimize(design);
 		}
 	}
 } SccPass;

 PRIVATE_NAMESPACE_END
	/*
	* 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
	* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
	* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
	* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
	* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
	*
	*/

	// [[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
	// http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm

	#include "kernel/register.h"
	#include "kernel/celltypes.h"
	#include "kernel/sigtools.h"
	#include "kernel/log.h"
	#include <stdlib.h>
	#include <stdio.h>
	#include <set>

	USING_YOSYS_NAMESPACE
	PRIVATE_NAMESPACE_BEGIN

	struct SccWorker
	{
	RTLIL::Design *design;
	RTLIL::Module *module;
	SigMap sigmap;
	CellTypes ct;

	std::set<RTLIL::Cell*> workQueue;
	std::map<RTLIL::Cell, std::set<RTLIL::Cell>> cellToNextCell;
	std::map<RTLIL::Cell*, RTLIL::SigSpec> cellToPrevSig, cellToNextSig;

	std::map<RTLIL::Cell*, std::pair<int, int>> cellLabels;
	std::map<RTLIL::Cell*, int> cellDepth;
	std::set<RTLIL::Cell*> cellsOnStack;
	std::vector<RTLIL::Cell*> cellStack;
	int labelCounter;

	std::map<RTLIL::Cell*, int> cell2scc;
	std::vector<std::set<RTLIL::Cell*>> sccList;

	void run(RTLIL::Cell *cell, int depth, int maxDepth)
	{
	log_assert(workQueue.count(cell) > 0);

	workQueue.erase(cell);
	cellLabels[cell] = std::pair<int, int>(labelCounter, labelCounter);
	labelCounter++;

	cellsOnStack.insert(cell);
	cellStack.push_back(cell);

	if (maxDepth >= 0)
	cellDepth[cell] = depth;

	for (auto nextCell : cellToNextCell[cell])
	if (cellLabels.count(nextCell) == 0) {
	run(nextCell, depth+1, maxDepth);
	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 = min(cellLabels[cell].second, cellLabels[nextCell].second);
	}

	if (cellLabels[cell].first == cellLabels[cell].second)
	{
	if (cellStack.back() == cell)
	{
	cellStack.pop_back();
	cellsOnStack.erase(cell);
	}
	else
	{
	log("Found an SCC:");
	std::set<RTLIL::Cell*> scc;
	while (cellsOnStack.count(cell) > 0) {
	RTLIL::Cell *c = cellStack.back();
	cellStack.pop_back();
	cellsOnStack.erase(c);
	log(" %s", RTLIL::id2cstr(c->name));
	cell2scc[c] = sccList.size();
	scc.insert(c);
	}
	sccList.push_back(scc);
	log("\n");
	}
	}
	}

	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());
	return;
	}

	if (allCellTypes) {
	ct.setup(design);
	} else {
	ct.setup_internals();
	ct.setup_stdcells();
	}

	SigPool selectedSignals;
	SigSet<RTLIL::Cell*> sigToNextCells;

	for (auto &it : module->wires_)
	if (design->selected(module, it.second))
	selectedSignals.add(sigmap(RTLIL::SigSpec(it.second)));

	for (auto &it : module->cells_)
	{
	RTLIL::Cell *cell = it.second;

	if (!design->selected(module, cell))
	continue;

	if (!allCellTypes && !ct.cell_known(cell->type))
	continue;

	workQueue.insert(cell);

	RTLIL::SigSpec inputSignals, outputSignals;

	for (auto &conn : cell->connections())
	{
	bool isInput = true, isOutput = true;

	if (ct.cell_known(cell->type)) {
	isInput = ct.cell_input(cell->type, conn.first);
	isOutput = ct.cell_output(cell->type, conn.first);
	}

	RTLIL::SigSpec sig = selectedSignals.extract(sigmap(conn.second));
	sig.sort_and_unify();

	if (isInput)
	inputSignals.append(sig);
	if (isOutput)
	outputSignals.append(sig);
	}

	inputSignals.sort_and_unify();
	outputSignals.sort_and_unify();

	cellToPrevSig[cell] = inputSignals;
	cellToNextSig[cell] = outputSignals;
	sigToNextCells.insert(inputSignals, cell);
	}

	for (auto cell : workQueue)
	{
	cellToNextCell[cell] = sigToNextCells.find(cellToNextSig[cell]);

	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");
	}
	}

	labelCounter = 0;
	cellLabels.clear();

	while (!workQueue.empty())
	{
	RTLIL::Cell cell = workQueue.begin();
	log_assert(cellStack.size() == 0);
	cellDepth.clear();

	run(cell, 0, maxDepth);
	}

	log("Found %d SCCs in module %s.\n", int(sccList.size()), RTLIL::id2cstr(module->name));
	}

	void select(RTLIL::Selection &sel)
	{
	for (int i = 0; i < int(sccList.size()); i++)
	{
	std::set<RTLIL::Cell*> &cells = sccList[i];
	RTLIL::SigSpec prevsig, nextsig, sig;

	for (auto cell : cells) {
	sel.selected_members[module->name].insert(cell->name);
	prevsig.append(cellToPrevSig[cell]);
	nextsig.append(cellToNextSig[cell]);
	}

	prevsig.sort_and_unify();
	nextsig.sort_and_unify();
	sig = prevsig.extract(nextsig);

	for (auto &chunk : sig.chunks())
	if (chunk.wire != NULL)
	sel.selected_members[module->name].insert(chunk.wire->name);
	}
	}
	};

	struct SccPass : public Pass {
	SccPass() : Pass("scc", "detect strongly connected components (logic loops)") { }
	void help() YS_OVERRIDE
	{
	// \|---v---\|---v---\|---v---\|---v---\|---v---\|---v---\|---v---\|---v---\|---v---\|---v---\|
	log("\n");
	log(" scc [options] [selection]\n");
	log("\n");
	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\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");
	log(" this option set, all cells are considered. For unknown cells all ports\n");
	log(" are assumed to be bidirectional 'inout' ports.\n");
	log("\n");
	log(" -set_attr <name> <value>\n");
	log(" set the specified attribute on all cells that are part of a logic\n");
	log(" loop. the special token {} in the value is replaced with a unique\n");
	log(" identifier for the logic loop.\n");
	log("\n");
	log(" -select\n");
	log(" replace the current selection with a selection of all cells and wires\n");
	log(" that are part of a found logic loop\n");
	log("\n");
	}
	void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
	{
	std::map<std::string, std::string> setAttr;
	bool allCellTypes = false;
	bool selectMode = false;
	bool nofeedbackMode = false;
	int maxDepth = -1;
	int expect = -1;

	log_header(design, "Executing SCC pass (detecting logic loops).\n");

	size_t argidx;
	for (argidx = 1; argidx < args.size(); argidx++) {
	if (args[argidx] == "-max_depth" && argidx+1 < args.size()) {
	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;
	}
	if (args[argidx] == "-set_attr" && argidx+2 < args.size()) {
	setAttr[args[argidx+1]] = args[argidx+2];
	argidx += 2;
	continue;
	}
	if (args[argidx] == "-select") {
	selectMode = true;
	continue;
	}
	break;
	}
	int origSelectPos = design->selection_stack.size() - 1;
	extra_args(args, argidx, design);

	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, nofeedbackMode, allCellTypes, maxDepth);

	if (!setAttr.empty())
	{
	for (const auto &cells : worker.sccList)
	{
	for (auto attr : setAttr)
	{
	IdString attr_name(RTLIL::escape_id(attr.first));
	string attr_valstr = attr.second;
	string index = stringf("%d", scc_counter);

	for (size_t pos = 0; (pos = attr_valstr.find("{}", pos)) != string::npos; pos += index.size())
	attr_valstr.replace(pos, 2, index);

	Const attr_value(attr_valstr);

	for (auto cell : cells)
	cell->attributes[attr_name] = attr_value;
	}

	scc_counter++;
	}
	}
	else
	{
	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;
	design->selection_stack[origSelectPos].optimize(design);
	}
	}
	} SccPass;

	PRIVATE_NAMESPACE_END