ice40: Adapt the relut process passes to the new $lut <=> SB_LUT4 port map

[yosys.git] / passes / cmds / 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>

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