From cd5767d61ba31e8990db0913b6a08f2563c49565 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Fri, 15 Mar 2013 10:24:08 +0100 Subject: Added scc pass (find logic loops) --- passes/scc/Makefile.inc | 3 + passes/scc/scc.cc | 297 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 300 insertions(+) create mode 100644 passes/scc/Makefile.inc create mode 100644 passes/scc/scc.cc (limited to 'passes') diff --git a/passes/scc/Makefile.inc b/passes/scc/Makefile.inc new file mode 100644 index 00000000..ca86e6e5 --- /dev/null +++ b/passes/scc/Makefile.inc @@ -0,0 +1,3 @@ + +OBJS += passes/scc/scc.o + diff --git a/passes/scc/scc.cc b/passes/scc/scc.cc new file mode 100644 index 00000000..e665fd09 --- /dev/null +++ b/passes/scc/scc.cc @@ -0,0 +1,297 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf + * + * 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 +#include +#include + +struct SccWorker +{ + RTLIL::Design *design; + RTLIL::Module *module; + SigMap sigmap; + CellTypes ct; + + std::set workQueue; + std::map> cellToNextCell; + std::map cellToPrevSig, cellToNextSig; + + std::map> cellLabels; + std::map cellDepth; + std::set cellsOnStack; + std::vector cellStack; + int labelCounter; + + std::map cell2scc; + std::vector> sccList; + + void run(RTLIL::Cell *cell, int depth, int maxDepth) + { + assert(workQueue.count(cell) > 0); + + workQueue.erase(cell); + cellLabels[cell] = std::pair(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 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 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 &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 \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 \n"); + log(" -set_cell_attr \n"); + log(" -set_wire_attr \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 args, RTLIL::Design *design) + { + std::map 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; + -- cgit v1.2.3