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 #include "kernel/macc.h"
  27
  28 struct ConstEval
  29 {
  30         RTLIL::Module *module;
  31         SigMap assign_map;
  32         SigMap values_map;
  33         SigPool stop_signals;
  34         SigSet<RTLIL::Cell*> sig2driver;
  35         std::set<RTLIL::Cell*> busy;
  36         std::vector<SigMap> stack;
  37
  38         ConstEval(RTLIL::Module *module) : module(module), assign_map(module)
  39         {
  40                 CellTypes ct;
  41                 ct.setup_internals();
  42                 ct.setup_stdcells();
  43
  44                 for (auto &it : module->cells_) {
  45                         if (!ct.cell_known(it.second->type))
  46                                 continue;
  47                         for (auto &it2 : it.second->connections())
  48                                 if (ct.cell_output(it.second->type, it2.first))
  49                                         sig2driver.insert(assign_map(it2.second), it.second);
  50                 }
  51         }
  52
  53         void clear()
  54         {
  55                 values_map.clear();
  56                 stop_signals.clear();
  57         }
  58
  59         void push()
  60         {
  61                 stack.push_back(values_map);
  62         }
  63
  64         void pop()
  65         {
  66                 values_map.swap(stack.back());
  67                 stack.pop_back();
  68         }
  69
  70         void set(RTLIL::SigSpec sig, RTLIL::Const value)
  71         {
  72                 assign_map.apply(sig);
  73 #ifndef NDEBUG
  74                 RTLIL::SigSpec current_val = values_map(sig);
  75                 for (int i = 0; i < SIZE(current_val); i++)
  76                         log_assert(current_val[i].wire != NULL || current_val[i] == value.bits[i]);
  77 #endif
  78                 values_map.add(sig, RTLIL::SigSpec(value));
  79         }
  80
  81         void stop(RTLIL::SigSpec sig)
  82         {
  83                 assign_map.apply(sig);
  84                 stop_signals.add(sig);
  85         }
  86
  87         bool eval(RTLIL::Cell *cell, RTLIL::SigSpec &undef)
  88         {
  89                 if (cell->type == "$lcu")
  90                 {
  91                         RTLIL::SigSpec sig_p = cell->getPort("\\P");
  92                         RTLIL::SigSpec sig_g = cell->getPort("\\G");
  93                         RTLIL::SigSpec sig_ci = cell->getPort("\\CI");
  94                         RTLIL::SigSpec sig_co = values_map(assign_map(cell->getPort("\\CO")));
  95
  96                         if (sig_co.is_fully_const())
  97                                 return true;
  98
  99                         if (!eval(sig_p, undef, cell))
 100                                 return false;
 101
 102                         if (!eval(sig_g, undef, cell))
 103                                 return false;
 104
 105                         if (!eval(sig_ci, undef, cell))
 106                                 return false;
 107
 108                         if (sig_p.is_fully_def() && sig_g.is_fully_def() && sig_ci.is_fully_def())
 109                         {
 110                                 RTLIL::Const coval(RTLIL::Sx, SIZE(sig_co));
 111                                 bool carry = sig_ci.as_bool();
 112
 113                                 for (int i = 0; i < SIZE(coval); i++) {
 114                                         carry = (sig_g[i] == RTLIL::S1) || (sig_p[i] == RTLIL::S1 && carry);
 115                                         coval.bits[i] = carry ? RTLIL::S1 : RTLIL::S0;
 116                                 }
 117
 118                                 set(sig_co, coval);
 119                         }
 120                         else
 121                                 set(sig_co, RTLIL::Const(RTLIL::Sx, SIZE(sig_co)));
 122
 123                         return true;
 124                 }
 125
 126                 RTLIL::SigSpec sig_a, sig_b, sig_s, sig_y;
 127
 128                 log_assert(cell->hasPort("\\Y"));
 129                 sig_y = values_map(assign_map(cell->getPort("\\Y")));
 130                 if (sig_y.is_fully_const())
 131                         return true;
 132
 133                 if (cell->hasPort("\\S")) {
 134                         sig_s = cell->getPort("\\S");
 135                         if (!eval(sig_s, undef, cell))
 136                                 return false;
 137                 }
 138
 139                 if (cell->hasPort("\\A"))
 140                         sig_a = cell->getPort("\\A");
 141
 142                 if (cell->hasPort("\\B"))
 143                         sig_b = cell->getPort("\\B");
 144
 145                 if (cell->type == "$mux" || cell->type == "$pmux" || cell->type == "$_MUX_")
 146                 {
 147                         std::vector<RTLIL::SigSpec> y_candidates;
 148                         int count_maybe_set_s_bits = 0;
 149                         int count_set_s_bits = 0;
 150
 151                         for (int i = 0; i < sig_s.size(); i++)
 152                         {
 153                                 RTLIL::State s_bit = sig_s.extract(i, 1).as_const().bits.at(0);
 154                                 RTLIL::SigSpec b_slice = sig_b.extract(sig_y.size()*i, sig_y.size());
 155
 156                                 if (s_bit == RTLIL::State::Sx || s_bit == RTLIL::State::S1)
 157                                         y_candidates.push_back(b_slice);
 158
 159                                 if (s_bit == RTLIL::State::S1 || s_bit == RTLIL::State::Sx)
 160                                         count_maybe_set_s_bits++;
 161
 162                                 if (s_bit == RTLIL::State::S1)
 163                                         count_set_s_bits++;
 164                         }
 165
 166                         if (count_set_s_bits == 0)
 167                                 y_candidates.push_back(sig_a);
 168
 169                         std::vector<RTLIL::Const> y_values;
 170
 171                         log_assert(y_candidates.size() > 0);
 172                         for (auto &yc : y_candidates) {
 173                                 if (!eval(yc, undef, cell))
 174                                         return false;
 175                                 y_values.push_back(yc.as_const());
 176                         }
 177
 178                         if (y_values.size() > 1)
 179                         {
 180                                 std::vector<RTLIL::State> master_bits = y_values.at(0).bits;
 181
 182                                 for (size_t i = 1; i < y_values.size(); i++) {
 183                                         std::vector<RTLIL::State> &slave_bits = y_values.at(i).bits;
 184                                         log_assert(master_bits.size() == slave_bits.size());
 185                                         for (size_t j = 0; j < master_bits.size(); j++)
 186                                                 if (master_bits[j] != slave_bits[j])
 187                                                         master_bits[j] = RTLIL::State::Sx;
 188                                 }
 189
 190                                 set(sig_y, RTLIL::Const(master_bits));
 191                         }
 192                         else
 193                                 set(sig_y, y_values.front());
 194                 }
 195                 else if (cell->type == "$fa")
 196                 {
 197                         RTLIL::SigSpec sig_c = cell->getPort("\\C");
 198                         RTLIL::SigSpec sig_x = cell->getPort("\\X");
 199                         int width = SIZE(sig_c);
 200
 201                         if (!eval(sig_a, undef, cell))
 202                                 return false;
 203
 204                         if (!eval(sig_b, undef, cell))
 205                                 return false;
 206
 207                         if (!eval(sig_c, undef, cell))
 208                                 return false;
 209
 210                         RTLIL::Const t1 = const_xor(sig_a.as_const(), sig_b.as_const(), false, false, width);
 211                         RTLIL::Const val_y = const_xor(t1, sig_c.as_const(), false, false, width);
 212
 213                         RTLIL::Const t2 = const_and(sig_a.as_const(), sig_b.as_const(), false, false, width);
 214                         RTLIL::Const t3 = const_and(sig_c.as_const(), t1, false, false, width);
 215                         RTLIL::Const val_x = const_or(t2, t3, false, false, width);
 216
 217                         set(sig_y, val_y);
 218                         set(sig_x, val_x);
 219                 }
 220                 else if (cell->type == "$alu")
 221                 {
 222                         bool signed_a = cell->parameters.count("\\A_SIGNED") > 0 && cell->parameters["\\A_SIGNED"].as_bool();
 223                         bool signed_b = cell->parameters.count("\\B_SIGNED") > 0 && cell->parameters["\\B_SIGNED"].as_bool();
 224
 225                         RTLIL::SigSpec sig_ci = cell->getPort("\\CI");
 226                         RTLIL::SigSpec sig_bi = cell->getPort("\\BI");
 227
 228                         if (!eval(sig_a, undef, cell))
 229                                 return false;
 230
 231                         if (!eval(sig_b, undef, cell))
 232                                 return false;
 233
 234                         if (!eval(sig_ci, undef, cell))
 235                                 return false;
 236
 237                         if (!eval(sig_bi, undef, cell))
 238                                 return false;
 239
 240                         RTLIL::SigSpec sig_x = cell->getPort("\\X");
 241                         RTLIL::SigSpec sig_co = cell->getPort("\\CO");
 242
 243                         bool any_input_undef = !(sig_a.is_fully_def() && sig_b.is_fully_def() && sig_ci.is_fully_def() && sig_bi.is_fully_def());
 244                         sig_a.extend_u0(SIZE(sig_y), signed_a);
 245                         sig_b.extend_u0(SIZE(sig_y), signed_b);
 246
 247                         bool carry = sig_ci[0] == RTLIL::S1;
 248                         bool b_inv = sig_bi[0] == RTLIL::S1;
 249
 250                         for (int i = 0; i < SIZE(sig_y); i++)
 251                         {
 252                                 RTLIL::SigSpec x_inputs = { sig_a[i], sig_b[i], sig_bi[0] };
 253
 254                                 if (!x_inputs.is_fully_def()) {
 255                                         set(sig_x[i], RTLIL::Sx);
 256                                 } else {
 257                                         bool bit_a = sig_a[i] == RTLIL::S1;
 258                                         bool bit_b = (sig_b[i] == RTLIL::S1) != b_inv;
 259                                         bool bit_x = bit_a != bit_b;
 260                                         set(sig_x[i], bit_x ? RTLIL::S1 : RTLIL::S0);
 261                                 }
 262
 263                                 if (any_input_undef) {
 264                                         set(sig_y[i], RTLIL::Sx);
 265                                         set(sig_co[i], RTLIL::Sx);
 266                                 } else {
 267                                         bool bit_a = sig_a[i] == RTLIL::S1;
 268                                         bool bit_b = (sig_b[i] == RTLIL::S1) != b_inv;
 269                                         bool bit_y = (bit_a != bit_b) != carry;
 270                                         carry = (bit_a && bit_b) || (bit_a && carry) || (bit_b && carry);
 271                                         set(sig_y[i], bit_y ? RTLIL::S1 : RTLIL::S0);
 272                                         set(sig_co[i], carry ? RTLIL::S1 : RTLIL::S0);
 273                                 }
 274                         }
 275                 }
 276                 else if (cell->type == "$macc")
 277                 {
 278                         Macc macc;
 279                         macc.from_cell(cell);
 280
 281                         if (!eval(macc.bit_ports, undef, cell))
 282                                 return false;
 283
 284                         for (auto &port : macc.ports) {
 285                                 if (!eval(port.in_a, undef, cell))
 286                                         return false;
 287                                 if (!eval(port.in_b, undef, cell))
 288                                         return false;
 289                         }
 290
 291                         RTLIL::Const result(0, SIZE(cell->getPort("\\Y")));
 292                         if (!macc.eval(result))
 293                                 log_abort();
 294
 295                         set(cell->getPort("\\Y"), result);
 296                 }
 297                 else
 298                 {
 299                         RTLIL::SigSpec sig_c, sig_d;
 300
 301                         if (cell->type.in("$_AOI3_", "$_OAI3_", "$_AOI4_", "$_OAI4_")) {
 302                                 if (cell->hasPort("\\C"))
 303                                         sig_c = cell->getPort("\\C");
 304                                 if (cell->hasPort("\\D"))
 305                                         sig_d = cell->getPort("\\D");
 306                         }
 307
 308                         if (sig_a.size() > 0 && !eval(sig_a, undef, cell))
 309                                 return false;
 310                         if (sig_b.size() > 0 && !eval(sig_b, undef, cell))
 311                                 return false;
 312                         if (sig_c.size() > 0 && !eval(sig_c, undef, cell))
 313                                 return false;
 314                         if (sig_d.size() > 0 && !eval(sig_d, undef, cell))
 315                                 return false;
 316
 317                         set(sig_y, CellTypes::eval(cell, sig_a.as_const(), sig_b.as_const(),
 318                                         sig_c.as_const(), sig_d.as_const()));
 319                 }
 320
 321                 return true;
 322         }
 323
 324         bool eval(RTLIL::SigSpec &sig, RTLIL::SigSpec &undef, RTLIL::Cell *busy_cell = NULL)
 325         {
 326                 assign_map.apply(sig);
 327                 values_map.apply(sig);
 328
 329                 if (sig.is_fully_const())
 330                         return true;
 331
 332                 if (stop_signals.check_any(sig)) {
 333                         undef = stop_signals.extract(sig);
 334                         return false;
 335                 }
 336
 337                 if (busy_cell) {
 338                         if (busy.count(busy_cell) > 0) {
 339                                 undef = sig;
 340                                 return false;
 341                         }
 342                         busy.insert(busy_cell);
 343                 }
 344
 345                 std::set<RTLIL::Cell*> driver_cells;
 346                 sig2driver.find(sig, driver_cells);
 347                 for (auto cell : driver_cells) {
 348                         if (!eval(cell, undef)) {
 349                                 if (busy_cell)
 350                                         busy.erase(busy_cell);
 351                                 return false;
 352                         }
 353                 }
 354
 355                 if (busy_cell)
 356                         busy.erase(busy_cell);
 357
 358                 values_map.apply(sig);
 359                 if (sig.is_fully_const())
 360                         return true;
 361
 362                 for (auto &c : sig.chunks())
 363                         if (c.wire != NULL)
 364                                 undef.append(c);
 365                 return false;
 366         }
 367
 368         bool eval(RTLIL::SigSpec &sig)
 369         {
 370                 RTLIL::SigSpec undef;
 371                 return eval(sig, undef);
 372         }
 373 };
 374
 375 #endif