kernel/consteval.h

   1 /*
   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 CONSTEVAL_H
  21 #define CONSTEVAL_H
  22
  23 #include "kernel/rtlil.h"
  24 #include "kernel/sigtools.h"
  25 #include "kernel/celltypes.h"
  26
  27 struct ConstEval
  28 {
  29         RTLIL::Module *module;
  30         SigMap assign_map;
  31         SigMap values_map;
  32         SigPool stop_signals;
  33         SigSet<RTLIL::Cell*> sig2driver;
  34         std::set<RTLIL::Cell*> busy;
  35         std::vector<SigMap> stack;
  36
  37         ConstEval(RTLIL::Module *module) : module(module), assign_map(module)
  38         {
  39                 CellTypes ct;
  40                 ct.setup_internals();
  41                 ct.setup_stdcells();
  42
  43                 for (auto &it : module->cells_) {
  44                         if (!ct.cell_known(it.second->type))
  45                                 continue;
  46                         for (auto &it2 : it.second->connections())
  47                                 if (ct.cell_output(it.second->type, it2.first))
  48                                         sig2driver.insert(assign_map(it2.second), it.second);
  49                 }
  50         }
  51
  52         void clear()
  53         {
  54                 values_map.clear();
  55                 stop_signals.clear();
  56         }
  57
  58         void push()
  59         {
  60                 stack.push_back(values_map);
  61         }
  62
  63         void pop()
  64         {
  65                 values_map.swap(stack.back());
  66                 stack.pop_back();
  67         }
  68
  69         void set(RTLIL::SigSpec sig, RTLIL::Const value)
  70         {
  71                 assign_map.apply(sig);
  72 #ifndef NDEBUG
  73                 RTLIL::SigSpec current_val = values_map(sig);
  74                 for (int i = 0; i < SIZE(current_val); i++)
  75                         assert(current_val[i].wire != NULL || current_val[i] == value.bits[i]);
  76 #endif
  77                 values_map.add(sig, RTLIL::SigSpec(value));
  78         }
  79
  80         void stop(RTLIL::SigSpec sig)
  81         {
  82                 assign_map.apply(sig);
  83                 stop_signals.add(sig);
  84         }
  85
  86         bool eval(RTLIL::Cell *cell, RTLIL::SigSpec &undef)
  87         {
  88                 RTLIL::SigSpec sig_a, sig_b, sig_s, sig_y;
  89
  90                 assert(cell->has("\\Y"));
  91                 sig_y = values_map(assign_map(cell->get("\\Y")));
  92                 if (sig_y.is_fully_const())
  93                         return true;
  94
  95                 if (cell->has("\\S")) {
  96                         sig_s = cell->get("\\S");
  97                         if (!eval(sig_s, undef, cell))
  98                                 return false;
  99                 }
 100
 101                 if (cell->has("\\A"))
 102                         sig_a = cell->get("\\A");
 103
 104                 if (cell->has("\\B"))
 105                         sig_b = cell->get("\\B");
 106
 107                 if (cell->type == "$mux" || cell->type == "$pmux" || cell->type == "$safe_pmux" || cell->type == "$_MUX_")
 108                 {
 109                         std::vector<RTLIL::SigSpec> y_candidates;
 110                         int count_maybe_set_s_bits = 0;
 111                         int count_set_s_bits = 0;
 112
 113                         for (int i = 0; i < sig_s.size(); i++)
 114                         {
 115                                 RTLIL::State s_bit = sig_s.extract(i, 1).as_const().bits.at(0);
 116                                 RTLIL::SigSpec b_slice = sig_b.extract(sig_y.size()*i, sig_y.size());
 117
 118                                 if (s_bit == RTLIL::State::Sx || s_bit == RTLIL::State::S1)
 119                                         y_candidates.push_back(b_slice);
 120
 121                                 if (s_bit == RTLIL::State::S1 || s_bit == RTLIL::State::Sx)
 122                                         count_maybe_set_s_bits++;
 123
 124                                 if (s_bit == RTLIL::State::S1)
 125                                         count_set_s_bits++;
 126                         }
 127
 128                         if (cell->type == "$safe_pmux" && count_set_s_bits > 1)
 129                                 y_candidates.clear();
 130
 131                         if ((cell->type == "$safe_pmux" && count_maybe_set_s_bits > 1) || count_set_s_bits == 0)
 132                                 y_candidates.push_back(sig_a);
 133
 134                         std::vector<RTLIL::Const> y_values;
 135
 136                         assert(y_candidates.size() > 0);
 137                         for (auto &yc : y_candidates) {
 138                                 if (!eval(yc, undef, cell))
 139                                         return false;
 140                                 y_values.push_back(yc.as_const());
 141                         }
 142
 143                         if (y_values.size() > 1)
 144                         {
 145                                 std::vector<RTLIL::State> master_bits = y_values.at(0).bits;
 146
 147                                 for (size_t i = 1; i < y_values.size(); i++) {
 148                                         std::vector<RTLIL::State> &slave_bits = y_values.at(i).bits;
 149                                         assert(master_bits.size() == slave_bits.size());
 150                                         for (size_t j = 0; j < master_bits.size(); j++)
 151                                                 if (master_bits[j] != slave_bits[j])
 152                                                         master_bits[j] = RTLIL::State::Sx;
 153                                 }
 154
 155                                 set(sig_y, RTLIL::Const(master_bits));
 156                         }
 157                         else
 158                                 set(sig_y, y_values.front());
 159                 }
 160                 else
 161                 {
 162                         if (sig_a.size() > 0 && !eval(sig_a, undef, cell))
 163                                 return false;
 164                         if (sig_b.size() > 0 && !eval(sig_b, undef, cell))
 165                                 return false;
 166                         set(sig_y, CellTypes::eval(cell, sig_a.as_const(), sig_b.as_const()));
 167                 }
 168
 169                 return true;
 170         }
 171
 172         bool eval(RTLIL::SigSpec &sig, RTLIL::SigSpec &undef, RTLIL::Cell *busy_cell = NULL)
 173         {
 174                 assign_map.apply(sig);
 175                 values_map.apply(sig);
 176
 177                 if (sig.is_fully_const())
 178                         return true;
 179
 180                 if (stop_signals.check_any(sig)) {
 181                         undef = stop_signals.extract(sig);
 182                         return false;
 183                 }
 184
 185                 if (busy_cell) {
 186                         if (busy.count(busy_cell) > 0) {
 187                                 undef = sig;
 188                                 return false;
 189                         }
 190                         busy.insert(busy_cell);
 191                 }
 192
 193                 std::set<RTLIL::Cell*> driver_cells;
 194                 sig2driver.find(sig, driver_cells);
 195                 for (auto cell : driver_cells) {
 196                         if (!eval(cell, undef)) {
 197                                 if (busy_cell)
 198                                         busy.erase(busy_cell);
 199                                 return false;
 200                         }
 201                 }
 202
 203                 if (busy_cell)
 204                         busy.erase(busy_cell);
 205
 206                 values_map.apply(sig);
 207                 if (sig.is_fully_const())
 208                         return true;
 209
 210                 for (auto &c : sig.chunks())
 211                         if (c.wire != NULL)
 212                                 undef.append(c);
 213                 return false;
 214         }
 215
 216         bool eval(RTLIL::SigSpec &sig)
 217         {
 218                 RTLIL::SigSpec undef;
 219                 return eval(sig, undef);
 220         }
 221 };
 222
 223 #endif