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