kernel/algo.h

   1 /* -*- c++ -*-
   2  *  yosys -- Yosys Open SYnthesis Suite
   3  *
   4  *  Copyright (C) 2012  Clifford Wolf <clifford@clifford.at>
   5  *
   6  *  Permission to use, copy, modify, and/or distribute this software for any
   7  *  purpose with or without fee is hereby granted, provided that the above
   8  *  copyright notice and this permission notice appear in all copies.
   9  *
  10  *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  11  *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  12  *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  13  *  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  14  *  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  15  *  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  16  *  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  17  *
  18  */
  19
  20 #ifndef SATGEN_ALGO_H
  21 #define SATGEN_ALGO_H
  22
  23 #include "kernel/celltypes.h"
  24 #include "kernel/rtlil.h"
  25 #include "kernel/sigtools.h"
  26 #include <stack>
  27
  28 YOSYS_NAMESPACE_BEGIN
  29
  30 CellTypes comb_cells_filt()
  31 {
  32         CellTypes ct;
  33
  34         ct.setup_internals();
  35         ct.setup_stdcells();
  36
  37         return ct;
  38 }
  39
  40 struct Netlist {
  41         RTLIL::Module *module;
  42         SigMap sigmap;
  43         CellTypes ct;
  44         dict<RTLIL::SigBit, Cell *> sigbit_driver_map;
  45         dict<RTLIL::Cell *, std::set<RTLIL::SigBit>> cell_inputs_map;
  46
  47         Netlist(RTLIL::Module *module) : module(module), sigmap(module), ct(module->design) { setup_netlist(module, ct); }
  48
  49         Netlist(RTLIL::Module *module, const CellTypes &ct) : module(module), sigmap(module), ct(ct) { setup_netlist(module, ct); }
  50
  51         RTLIL::Cell *driver_cell(RTLIL::SigBit sig) const
  52         {
  53                 sig = sigmap(sig);
  54                 if (!sigbit_driver_map.count(sig)) {
  55                         return NULL;
  56                 }
  57
  58                 return sigbit_driver_map.at(sig);
  59         }
  60
  61         RTLIL::SigBit& driver_port(RTLIL::SigBit sig)
  62         {
  63                 RTLIL::Cell *cell = driver_cell(sig);
  64
  65                 for (auto &port : cell->connections_) {
  66                         if (ct.cell_output(cell->type, port.first)) {
  67                                 RTLIL::SigSpec port_sig = sigmap(port.second);
  68                                 for (int i = 0; i < GetSize(port_sig); i++) {
  69                                         if (port_sig[i] == sig) {
  70                                                 return port.second[i];
  71                                         }
  72                                 }
  73                         }
  74                 }
  75         }
  76
  77         void setup_netlist(RTLIL::Module *module, const CellTypes &ct)
  78         {
  79                 for (auto cell : module->cells()) {
  80                         if (ct.cell_known(cell->type)) {
  81                                 std::set<RTLIL::SigBit> inputs, outputs;
  82                                 for (auto &port : cell->connections()) {
  83                                         std::vector<RTLIL::SigBit> bits = sigmap(port.second).to_sigbit_vector();
  84                                         if (ct.cell_output(cell->type, port.first))
  85                                                 outputs.insert(bits.begin(), bits.end());
  86                                         else
  87                                                 inputs.insert(bits.begin(), bits.end());
  88                                 }
  89                                 cell_inputs_map[cell] = inputs;
  90                                 for (auto &bit : outputs) {
  91                                         sigbit_driver_map[bit] = cell;
  92                                 };
  93                         }
  94                 }
  95         }
  96 };
  97
  98 namespace detail
  99 {
 100 struct NetlistConeWireIter : public std::iterator<std::input_iterator_tag, RTLIL::SigBit> {
 101         using set_iter_t = std::set<RTLIL::SigBit>::iterator;
 102
 103         const Netlist &net;
 104         RTLIL::SigBit sig;
 105         bool sentinel;
 106         CellTypes *cell_filter;
 107
 108         std::stack<std::pair<set_iter_t, set_iter_t>> dfs_path_stack;
 109         std::set<RTLIL::Cell *> cells_visited;
 110
 111         NetlistConeWireIter(const Netlist &net) : net(net), sentinel(true), cell_filter(NULL) {}
 112
 113         NetlistConeWireIter(const Netlist &net, RTLIL::SigBit sig, CellTypes *cell_filter = NULL)
 114             : net(net), sig(sig), sentinel(false), cell_filter(cell_filter)
 115         {
 116         }
 117
 118         const RTLIL::SigBit &operator*() const { return sig; };
 119         bool operator!=(const NetlistConeWireIter &other) const
 120         {
 121                 if (sentinel || other.sentinel) {
 122                         return sentinel != other.sentinel;
 123                 } else {
 124                         return sig != other.sig;
 125                 }
 126         }
 127
 128         bool operator==(const NetlistConeWireIter &other) const
 129         {
 130                 if (sentinel || other.sentinel) {
 131                         return sentinel == other.sentinel;
 132                 } else {
 133                         return sig == other.sig;
 134                 }
 135         }
 136
 137         void next_sig_in_dag()
 138         {
 139                 while (1) {
 140                         if (dfs_path_stack.empty()) {
 141                                 sentinel = true;
 142                                 return;
 143                         }
 144
 145                         auto &cell_inputs_iter = dfs_path_stack.top().first;
 146                         auto &cell_inputs_iter_guard = dfs_path_stack.top().second;
 147
 148                         cell_inputs_iter++;
 149                         if (cell_inputs_iter != cell_inputs_iter_guard) {
 150                                 sig = *cell_inputs_iter;
 151                                 return;
 152                         } else {
 153                                 dfs_path_stack.pop();
 154                         }
 155                 }
 156         }
 157
 158         NetlistConeWireIter &operator++()
 159         {
 160                 RTLIL::Cell *cell = net.driver_cell(sig);
 161
 162                 if (!cell) {
 163                         next_sig_in_dag();
 164                         return *this;
 165                 }
 166
 167                 if (cells_visited.count(cell)) {
 168                         next_sig_in_dag();
 169                         return *this;
 170                 }
 171
 172                 if ((cell_filter) && (!cell_filter->cell_known(cell->type))) {
 173                         next_sig_in_dag();
 174                         return *this;
 175                 }
 176
 177                 auto &inputs = net.cell_inputs_map.at(cell);
 178                 dfs_path_stack.push(std::make_pair(inputs.begin(), inputs.end()));
 179                 cells_visited.insert(cell);
 180                 sig = (*dfs_path_stack.top().first);
 181                 return *this;
 182         }
 183 };
 184
 185 struct NetlistConeWireIterable {
 186         const Netlist &net;
 187         RTLIL::SigBit sig;
 188         CellTypes *cell_filter;
 189
 190         NetlistConeWireIterable(const Netlist &net, RTLIL::SigBit sig, CellTypes *cell_filter = NULL) : net(net), sig(sig), cell_filter(cell_filter)
 191         {
 192         }
 193
 194         NetlistConeWireIter begin() { return NetlistConeWireIter(net, sig, cell_filter); }
 195         NetlistConeWireIter end() { return NetlistConeWireIter(net); }
 196 };
 197
 198 struct NetlistConeCellIter : public std::iterator<std::input_iterator_tag, RTLIL::Cell *> {
 199         const Netlist &net;
 200
 201         NetlistConeWireIter sig_iter;
 202
 203         NetlistConeCellIter(const Netlist &net) : net(net), sig_iter(net) {}
 204
 205         NetlistConeCellIter(const Netlist &net, RTLIL::SigBit sig, CellTypes *cell_filter = NULL) : net(net), sig_iter(net, sig, cell_filter)
 206         {
 207                 if ((!sig_iter.sentinel) && (!has_driver_cell(*sig_iter))) {
 208                         ++(*this);
 209                 }
 210         }
 211
 212         bool has_driver_cell(const RTLIL::SigBit &s) { return net.sigbit_driver_map.count(s); }
 213
 214         RTLIL::Cell *operator*() const { return net.sigbit_driver_map.at(*sig_iter); };
 215
 216         bool operator!=(const NetlistConeCellIter &other) const { return sig_iter != other.sig_iter; }
 217         bool operator==(const NetlistConeCellIter &other) const { return sig_iter == other.sig_iter; }
 218         NetlistConeCellIter &operator++()
 219         {
 220                 while (true) {
 221                         ++sig_iter;
 222                         if (sig_iter.sentinel) {
 223                                 return *this;
 224                         }
 225
 226                         RTLIL::Cell* cell = net.driver_cell(*sig_iter);
 227
 228                         if (!cell) {
 229                                 continue;
 230                         }
 231
 232                         if ((sig_iter.cell_filter) && (!sig_iter.cell_filter->cell_known(cell->type))) {
 233                                 continue;
 234                         }
 235
 236                         if (!sig_iter.cells_visited.count(cell)) {
 237                                 return *this;
 238                         }
 239                 }
 240         }
 241 };
 242
 243 struct NetlistConeCellIterable {
 244         const Netlist &net;
 245         RTLIL::SigBit sig;
 246         CellTypes *cell_filter;
 247
 248         NetlistConeCellIterable(const Netlist &net, RTLIL::SigBit sig, CellTypes *cell_filter = NULL) : net(net), sig(sig), cell_filter(cell_filter)
 249         {
 250         }
 251
 252         NetlistConeCellIter begin() { return NetlistConeCellIter(net, sig, cell_filter); }
 253         NetlistConeCellIter end() { return NetlistConeCellIter(net); }
 254 };
 255
 256 // struct NetlistConeInputsIter : public std::iterator<std::input_iterator_tag, const RTLIL::Cell *> {
 257 //      const Netlist &net;
 258 //      RTLIL::SigBit sig;
 259
 260 //      NetlistConeWireIter sig_iter;
 261
 262 //      bool has_driver_cell(const RTLIL::SigBit &s) { return net.sigbit_driver_map.count(s); }
 263
 264 //      NetlistConeInputsIter(const Netlist &net, RTLIL::SigBit sig = NULL) : net(net), sig(sig), sig_iter(net, sig)
 265 //      {
 266 //              if ((sig != NULL) && (has_driver_cell(sig_iter))) {
 267 //                      ++(*this);
 268 //              }
 269 //      }
 270
 271 //      const RTLIL::SigBit &operator*() const { return sig_iter; };
 272 //      bool operator!=(const NetlistConeInputsIter &other) const { return sig_iter != other.sig_iter; }
 273 //      bool operator==(const NetlistConeInputsIter &other) const { return sig_iter == other.sig_iter; }
 274 //      NetlistConeInputsIter &operator++()
 275 //      {
 276 //              do {
 277 //                      ++sig_iter;
 278 //                      if (sig_iter->empty()) {
 279 //                              return *this;
 280 //                      }
 281 //              } while (has_driver_cell(sig_iter));
 282
 283 //              return *this;
 284 //      }
 285 // };
 286
 287 // struct NetlistConeInputsIterable {
 288 //      const Netlist &net;
 289 //      RTLIL::SigBit sig;
 290
 291 //      NetlistConeInputsIterable(const Netlist &net, RTLIL::SigBit sig) : net(net), sig(sig) {}
 292
 293 //      NetlistConeInputsIter begin() { return NetlistConeInputsIter(net, sig); }
 294 //      NetlistConeInputsIter end() { return NetlistConeInputsIter(net); }
 295 // };
 296 } // namespace detail
 297
 298 detail::NetlistConeWireIterable cone(const Netlist &net, RTLIL::SigBit sig, CellTypes *cell_filter = NULL)
 299 {
 300         return detail::NetlistConeWireIterable(net, net.sigmap(sig), cell_filter = cell_filter);
 301 }
 302
 303 // detail::NetlistConeInputsIterable cone_inputs(RTLIL::SigBit sig) { return NetlistConeInputsIterable(this, &sig); }
 304 detail::NetlistConeCellIterable cell_cone(const Netlist &net, RTLIL::SigBit sig, CellTypes *cell_filter = NULL)
 305 {
 306         return detail::NetlistConeCellIterable(net, net.sigmap(sig), cell_filter);
 307 }
 308
 309 YOSYS_NAMESPACE_END
 310
 311 #endif