diff options
Diffstat (limited to 'kernel/satgen_algo.h')
-rw-r--r-- | kernel/satgen_algo.h | 158 |
1 files changed, 158 insertions, 0 deletions
diff --git a/kernel/satgen_algo.h b/kernel/satgen_algo.h new file mode 100644 index 000000000..483dfad5c --- /dev/null +++ b/kernel/satgen_algo.h @@ -0,0 +1,158 @@ +/* -*- 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 + +struct DriverMap : public std::map<RTLIL::SigBit, std::pair<RTLIL::Cell *, std::set<RTLIL::SigBit>>> { + RTLIL::Module *module; + SigMap sigmap; + + using map_t = std::map<RTLIL::SigBit, std::pair<RTLIL::Cell *, std::set<RTLIL::SigBit>>>; + + struct DriverMapConeWireIterator : public std::iterator<std::input_iterator_tag, const RTLIL::SigBit *> { + using set_iter_t = std::set<RTLIL::SigBit>::iterator; + + DriverMap *drvmap; + const RTLIL::SigBit *sig; + std::stack<std::pair<set_iter_t, set_iter_t>> dfs; + + DriverMapConeWireIterator(DriverMap *drvmap) : DriverMapConeWireIterator(drvmap, NULL) {} + + DriverMapConeWireIterator(DriverMap *drvmap, const RTLIL::SigBit *sig) : drvmap(drvmap), sig(sig) {} + + inline const RTLIL::SigBit &operator*() const { return *sig; }; + inline bool operator!=(const DriverMapConeWireIterator &other) const { return sig != other.sig; } + inline bool operator==(const DriverMapConeWireIterator &other) const { return sig == other.sig; } + inline void operator++() + { + if (drvmap->count(*sig)) { + std::pair<RTLIL::Cell *, std::set<RTLIL::SigBit>> &drv = drvmap->at(*sig); + dfs.push(std::make_pair(drv.second.begin(), drv.second.end())); + sig = &(*dfs.top().first); + } else { + while (1) { + auto &inputs_iter = dfs.top(); + + inputs_iter.first++; + if (inputs_iter.first != inputs_iter.second) { + sig = &(*inputs_iter.first); + return; + } else { + dfs.pop(); + if (dfs.empty()) { + sig = NULL; + return; + } + } + } + } + } + }; + + struct DriverMapConeWireIterable { + DriverMap *drvmap; + const RTLIL::SigBit *sig; + + DriverMapConeWireIterable(DriverMap *drvmap, const RTLIL::SigBit *sig) : drvmap(drvmap), sig(sig) {} + + inline DriverMapConeWireIterator begin() { return DriverMapConeWireIterator(drvmap, sig); } + inline DriverMapConeWireIterator end() { return DriverMapConeWireIterator(drvmap); } + }; + + struct DriverMapConeCellIterator : public std::iterator<std::input_iterator_tag, const RTLIL::Cell *> { + DriverMap *drvmap; + const RTLIL::SigBit *sig; + + DriverMapConeWireIterator sig_iter; + + DriverMapConeCellIterator(DriverMap *drvmap) : DriverMapConeCellIterator(drvmap, NULL) {} + + DriverMapConeCellIterator(DriverMap *drvmap, const RTLIL::SigBit *sig) : drvmap(drvmap), sig(sig), sig_iter(drvmap, sig) + { + if ((sig != NULL) && (!drvmap->count(*sig_iter))) { + ++(*this); + } + } + + inline RTLIL::Cell *operator*() const + { + std::pair<RTLIL::Cell *, std::set<RTLIL::SigBit>> &drv = drvmap->at(*sig); + return drv.first; + }; + inline bool operator!=(const DriverMapConeCellIterator &other) const { return sig_iter != other.sig_iter; } + inline bool operator==(const DriverMapConeCellIterator &other) const { return sig_iter == other.sig_iter; } + inline void operator++() + { + do { + ++sig_iter; + if (sig_iter.sig == NULL) { + return; + } + } while (!drvmap->count(*sig_iter)); + } + }; + + struct DriverMapConeCellIterable { + DriverMap *drvmap; + const RTLIL::SigBit *sig; + + DriverMapConeCellIterable(DriverMap *drvmap, const RTLIL::SigBit *sig) : drvmap(drvmap), sig(sig) {} + + inline DriverMapConeCellIterator begin() { return DriverMapConeCellIterator(drvmap, sig); } + inline DriverMapConeCellIterator end() { return DriverMapConeCellIterator(drvmap); } + }; + + DriverMap(RTLIL::Module *module) : module(module), sigmap(module) + { + CellTypes ct; + ct.setup_internals(); + ct.setup_stdcells(); + + for (auto &it : module->cells_) { + if (ct.cell_known(it.second->type)) { + std::set<RTLIL::SigBit> inputs, outputs; + for (auto &port : it.second->connections()) { + std::vector<RTLIL::SigBit> bits = sigmap(port.second).to_sigbit_vector(); + if (ct.cell_output(it.second->type, port.first)) + outputs.insert(bits.begin(), bits.end()); + else + inputs.insert(bits.begin(), bits.end()); + } + std::pair<RTLIL::Cell *, std::set<RTLIL::SigBit>> drv(it.second, inputs); + for (auto &bit : outputs) + (*this)[bit] = drv; + } + } + } + + DriverMapConeWireIterable cone(const RTLIL::SigBit &sig) { return DriverMapConeWireIterable(this, &sig); } + DriverMapConeCellIterable cell_cone(const RTLIL::SigBit &sig) { return DriverMapConeCellIterable(this, &sig); } +}; + +YOSYS_NAMESPACE_END + +#endif |