From 6644f80d97ddd7923fc3b136508d50a1ed3f01d1 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Sat, 8 Feb 2014 14:39:15 +0100 Subject: Moved some passes to other source directories --- passes/scc/Makefile.inc | 3 - passes/scc/scc.cc | 299 ------------------------------------------------ 2 files changed, 302 deletions(-) delete mode 100644 passes/scc/Makefile.inc delete mode 100644 passes/scc/scc.cc (limited to 'passes/scc') diff --git a/passes/scc/Makefile.inc b/passes/scc/Makefile.inc deleted file mode 100644 index ca86e6e5..00000000 --- a/passes/scc/Makefile.inc +++ /dev/null @@ -1,3 +0,0 @@ - -OBJS += passes/scc/scc.o - diff --git a/passes/scc/scc.cc b/passes/scc/scc.cc deleted file mode 100644 index f8c351a4..00000000 --- a/passes/scc/scc.cc +++ /dev/null @@ -1,299 +0,0 @@ -/* - * 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 useful 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