scc.cc

Go to the documentation of this file.

/*
 *  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 = 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();
            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)") { }
    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 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 unknown 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) {
            log_assert(origSelectPos >= 0);
            design->selection_stack[origSelectPos] = newSelection;
            design->selection_stack[origSelectPos].optimize(design);
        }
    }
} SccPass;
 
PRIVATE_NAMESPACE_END