diff options
Diffstat (limited to 'kernel/algo.h')
-rw-r--r-- | kernel/algo.h | 239 |
1 files changed, 239 insertions, 0 deletions
diff --git a/kernel/algo.h b/kernel/algo.h new file mode 100644 index 000000000..6ab96a875 --- /dev/null +++ b/kernel/algo.h @@ -0,0 +1,239 @@ +/* -*- c++ -*- + * 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. + * + */ + +#ifndef SATGEN_ALGO_H +#define SATGEN_ALGO_H + +#include "kernel/celltypes.h" +#include "kernel/rtlil.h" +#include "kernel/sigtools.h" +#include <stack> + +YOSYS_NAMESPACE_BEGIN + +CellTypes comb_cells_filt() +{ + CellTypes ct; + + ct.setup_internals(); + ct.setup_stdcells(); + + return ct; +} + +struct Netlist { + RTLIL::Module *module; + SigMap sigmap; + dict<RTLIL::SigBit, Cell *> sigbit_driver_map; + dict<RTLIL::Cell *, std::set<RTLIL::SigBit>> cell_inputs_map; + + Netlist(RTLIL::Module *module) : module(module), sigmap(module) + { + CellTypes ct(module->design); + setup_netlist(module, ct); + } + + Netlist(RTLIL::Module *module, const CellTypes &ct) : module(module), sigmap(module) { setup_netlist(module, ct); } + + void setup_netlist(RTLIL::Module *module, const CellTypes &ct) + { + for (auto cell : module->cells()) { + if (ct.cell_known(cell->type)) { + std::set<RTLIL::SigBit> inputs, outputs; + for (auto &port : cell->connections()) { + std::vector<RTLIL::SigBit> bits = sigmap(port.second).to_sigbit_vector(); + if (ct.cell_output(cell->type, port.first)) + outputs.insert(bits.begin(), bits.end()); + else + inputs.insert(bits.begin(), bits.end()); + } + cell_inputs_map[cell] = inputs; + for (auto &bit : outputs) { + sigbit_driver_map[bit] = cell; + }; + } + } + } +}; + +namespace detail +{ +struct NetlistConeWireIter : public std::iterator<std::input_iterator_tag, const RTLIL::SigBit *> { + using set_iter_t = std::set<RTLIL::SigBit>::iterator; + + const Netlist &net; + const RTLIL::SigBit *p_sig; + std::stack<std::pair<set_iter_t, set_iter_t>> dfs_path_stack; + std::set<RTLIL::Cell *> cells_visited; + + NetlistConeWireIter(const Netlist &net, const RTLIL::SigBit *p_sig = NULL) : net(net), p_sig(p_sig) {} + + const RTLIL::SigBit &operator*() const { return *p_sig; }; + bool operator!=(const NetlistConeWireIter &other) const { return p_sig != other.p_sig; } + bool operator==(const NetlistConeWireIter &other) const { return p_sig == other.p_sig; } + + void next_sig_in_dag() + { + while (1) { + if (dfs_path_stack.empty()) { + p_sig = NULL; + return; + } + + auto &cell_inputs_iter = dfs_path_stack.top().first; + auto &cell_inputs_iter_guard = dfs_path_stack.top().second; + + cell_inputs_iter++; + if (cell_inputs_iter != cell_inputs_iter_guard) { + p_sig = &(*cell_inputs_iter); + return; + } else { + dfs_path_stack.pop(); + } + } + } + + NetlistConeWireIter &operator++() + { + if (net.sigbit_driver_map.count(*p_sig)) { + auto drv = net.sigbit_driver_map.at(*p_sig); + + if (!cells_visited.count(drv)) { + auto &inputs = net.cell_inputs_map.at(drv); + dfs_path_stack.push(std::make_pair(inputs.begin(), inputs.end())); + cells_visited.insert(drv); + p_sig = &(*dfs_path_stack.top().first); + } else { + next_sig_in_dag(); + } + } else { + next_sig_in_dag(); + } + return *this; + } +}; + +struct NetlistConeWireIterable { + const Netlist &net; + const RTLIL::SigBit *p_sig; + + NetlistConeWireIterable(const Netlist &net, const RTLIL::SigBit *p_sig) : net(net), p_sig(p_sig) {} + + NetlistConeWireIter begin() { return NetlistConeWireIter(net, p_sig); } + NetlistConeWireIter end() { return NetlistConeWireIter(net); } +}; + +struct NetlistConeCellIter : public std::iterator<std::input_iterator_tag, const RTLIL::Cell *> { + const Netlist &net; + const RTLIL::SigBit *p_sig; + + NetlistConeWireIter sig_iter; + + NetlistConeCellIter(const Netlist &net, const RTLIL::SigBit *p_sig = NULL) : net(net), p_sig(p_sig), sig_iter(net, p_sig) + { + if ((p_sig != NULL) && (!has_driver_cell(*sig_iter))) { + ++(*this); + } + } + + bool has_driver_cell(const RTLIL::SigBit &s) { return net.sigbit_driver_map.count(s); } + + RTLIL::Cell *operator*() const { return net.sigbit_driver_map.at(*sig_iter); }; + + bool operator!=(const NetlistConeCellIter &other) const { return sig_iter != other.sig_iter; } + bool operator==(const NetlistConeCellIter &other) const { return sig_iter == other.sig_iter; } + NetlistConeCellIter &operator++() + { + while (true) { + ++sig_iter; + if (sig_iter.p_sig == NULL) { + return *this; + } + + if (has_driver_cell(*sig_iter)) { + auto cell = net.sigbit_driver_map.at(*sig_iter); + + if (!sig_iter.cells_visited.count(cell)) { + return *this; + } + } + }; + } +}; + +struct NetlistConeCellIterable { + const Netlist &net; + const RTLIL::SigBit *p_sig; + + NetlistConeCellIterable(const Netlist &net, const RTLIL::SigBit *p_sig) : net(net), p_sig(p_sig) {} + + NetlistConeCellIter begin() { return NetlistConeCellIter(net, p_sig); } + NetlistConeCellIter end() { return NetlistConeCellIter(net); } +}; + +struct NetlistConeInputsIter : public std::iterator<std::input_iterator_tag, const RTLIL::Cell *> { + const Netlist &net; + const RTLIL::SigBit *p_sig; + + NetlistConeWireIter sig_iter; + + bool has_driver_cell(const RTLIL::SigBit &s) { return net.sigbit_driver_map.count(s); } + + NetlistConeInputsIter(const Netlist &net, const RTLIL::SigBit *p_sig = NULL) : net(net), p_sig(p_sig), sig_iter(net, p_sig) + { + if ((p_sig != NULL) && (has_driver_cell(*sig_iter))) { + ++(*this); + } + } + + const RTLIL::SigBit &operator*() const { return *sig_iter; }; + bool operator!=(const NetlistConeInputsIter &other) const { return sig_iter != other.sig_iter; } + bool operator==(const NetlistConeInputsIter &other) const { return sig_iter == other.sig_iter; } + NetlistConeInputsIter &operator++() + { + do { + ++sig_iter; + if (sig_iter.p_sig == NULL) { + return *this; + } + } while (has_driver_cell(*sig_iter)); + + return *this; + } +}; + +struct NetlistConeInputsIterable { + const Netlist &net; + const RTLIL::SigBit *p_sig; + + NetlistConeInputsIterable(const Netlist &net, const RTLIL::SigBit *p_sig) : net(net), p_sig(p_sig) {} + + NetlistConeInputsIter begin() { return NetlistConeInputsIter(net, p_sig); } + NetlistConeInputsIter end() { return NetlistConeInputsIter(net); } +}; +} // namespace detail + +detail::NetlistConeWireIterable cone(const Netlist &net, const RTLIL::SigBit &sig) { return detail::NetlistConeWireIterable(net, &sig); } + +// detail::NetlistConeInputsIterable cone_inputs(const RTLIL::SigBit &sig) { return NetlistConeInputsIterable(this, &sig); } +detail::NetlistConeCellIterable cell_cone(const Netlist &net, const RTLIL::SigBit &sig) { return detail::NetlistConeCellIterable(net, &sig); } + +YOSYS_NAMESPACE_END + +#endif |