path: root/passes/scc/scc.cc

/*
 *  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>

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)
	{
		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 = std::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);
			}

		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 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]);

		labelCounter = 0;
		cellLabels.clear();

		while (workQueue.size() > 0) {
			RTLIL::Cell *cell = *workQueue.begin();
			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)") { }
	virtual void help()
	{
		//   |---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("    -max_depth <num>\n");
		log("        limit to loops not longer than the specified number of cells. This can\n");
		log("        e.g. be usefull in identifying local loops in a module that turns out\n");
		log("        to be one gigantic 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 unkown cells all ports\n");
		log("        are assumed to be bidirectional 'inout' ports.\n");
		log("\n");
		log("    -set_attr <name> <value>\n");
		log("    -set_cell_attr <name> <value>\n");
		log("    -set_wire_attr <name> <value>\n");
		log("        set the specified attribute on all cells and/or wires that are part of\n");
		log("        a logic loop. the special token {} in the value is replaced with a\n");
		log("        unique 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");
	}
	virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
	{
		std::map<std::string, std::string> setCellAttr, setWireAttr;
		bool allCellTypes = false;
		bool selectMode = false;
		int maxDepth = -1;

		log_header("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] == "-all_cell_types") {
				allCellTypes = true;
				continue;
			}
			if (args[argidx] == "-set_attr" && argidx+2 < args.size()) {
				setCellAttr[args[argidx+1]] = args[argidx+2];
				setWireAttr[args[argidx+1]] = args[argidx+2];
				argidx += 2;
				continue;
			}
			if (args[argidx] == "-set_cell_attr" && argidx+2 < args.size()) {
				setCellAttr[args[argidx+1]] = args[argidx+2];
				argidx += 2;
				continue;
			}
			if (args[argidx] == "-set_wire_attr" && argidx+2 < args.size()) {
				setWireAttr[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);

		if (setCellAttr.size() > 0 || setWireAttr.size() > 0)
			log_cmd_error("The -set*_attr options are not implemented at the moment!\n");

		RTLIL::Selection newSelection(false);

		for (auto &mod_it : design->modules)
			if (design->selected(mod_it.second))
			{
				SccWorker worker(design, mod_it.second, allCellTypes, maxDepth);

				if (selectMode)
					worker.select(newSelection);
			}

		if (selectMode) {
			assert(origSelectPos >= 0);
			design->selection_stack[origSelectPos] = newSelection;
			design->selection_stack[origSelectPos].optimize(design);
		}
	}
} SccPass;