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 == ID($lcu))
  93                 {
  94                         RTLIL::SigSpec sig_p = cell->getPort(ID::P);
  95                         RTLIL::SigSpec sig_g = cell->getPort(ID::G);
  96                         RTLIL::SigSpec sig_ci = cell->getPort(ID::CI);
  97                         RTLIL::SigSpec sig_co = values_map(assign_map(cell->getPort(ID::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] == State::S1) || (sig_p[i] == RTLIL::S1 && carry);
 118                                         coval.bits[i] = carry ? State::S1 : State::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(ID::Y));
 132                 sig_y = values_map(assign_map(cell->getPort(ID::Y)));
 133                 if (sig_y.is_fully_const())
 134                         return true;
 135
 136                 if (cell->hasPort(ID::S)) {
 137                         sig_s = cell->getPort(ID::S);
 138                         if (!eval(sig_s, undef, cell))
 139                                 return false;
 140                 }
 141
 142                 if (cell->hasPort(ID::A))
 143                         sig_a = cell->getPort(ID::A);
 144
 145                 if (cell->hasPort(ID::B))
 146                         sig_b = cell->getPort(ID::B);
 147
 148                 if (cell->type.in(ID($mux), ID($pmux), ID($_MUX_), ID($_NMUX_)))
 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                                 if (cell->type == ID($_NMUX_))
 179                                         y_values.push_back(RTLIL::const_not(yc.as_const(), Const(), false, false, GetSize(yc)));
 180                                 else
 181                                         y_values.push_back(yc.as_const());
 182                         }
 183
 184                         if (y_values.size() > 1)
 185                         {
 186                                 std::vector<RTLIL::State> master_bits = y_values.at(0).bits;
 187
 188                                 for (size_t i = 1; i < y_values.size(); i++) {
 189                                         std::vector<RTLIL::State> &slave_bits = y_values.at(i).bits;
 190                                         log_assert(master_bits.size() == slave_bits.size());
 191                                         for (size_t j = 0; j < master_bits.size(); j++)
 192                                                 if (master_bits[j] != slave_bits[j])
 193                                                         master_bits[j] = RTLIL::State::Sx;
 194                                 }
 195
 196                                 set(sig_y, RTLIL::Const(master_bits));
 197                         }
 198                         else
 199                                 set(sig_y, y_values.front());
 200                 }
 201                 else if (cell->type == ID($fa))
 202                 {
 203                         RTLIL::SigSpec sig_c = cell->getPort(ID::C);
 204                         RTLIL::SigSpec sig_x = cell->getPort(ID::X);
 205                         int width = GetSize(sig_c);
 206
 207                         if (!eval(sig_a, undef, cell))
 208                                 return false;
 209
 210                         if (!eval(sig_b, undef, cell))
 211                                 return false;
 212
 213                         if (!eval(sig_c, undef, cell))
 214                                 return false;
 215
 216                         RTLIL::Const t1 = const_xor(sig_a.as_const(), sig_b.as_const(), false, false, width);
 217                         RTLIL::Const val_y = const_xor(t1, sig_c.as_const(), false, false, width);
 218
 219                         RTLIL::Const t2 = const_and(sig_a.as_const(), sig_b.as_const(), false, false, width);
 220                         RTLIL::Const t3 = const_and(sig_c.as_const(), t1, false, false, width);
 221                         RTLIL::Const val_x = const_or(t2, t3, false, false, width);
 222
 223                         for (int i = 0; i < GetSize(val_y); i++)
 224                                 if (val_y.bits[i] == RTLIL::Sx)
 225                                         val_x.bits[i] = RTLIL::Sx;
 226
 227                         set(sig_y, val_y);
 228                         set(sig_x, val_x);
 229                 }
 230                 else if (cell->type == ID($alu))
 231                 {
 232                         bool signed_a = cell->parameters.count(ID::A_SIGNED) > 0 && cell->parameters[ID::A_SIGNED].as_bool();
 233                         bool signed_b = cell->parameters.count(ID::B_SIGNED) > 0 && cell->parameters[ID::B_SIGNED].as_bool();
 234
 235                         RTLIL::SigSpec sig_ci = cell->getPort(ID::CI);
 236                         RTLIL::SigSpec sig_bi = cell->getPort(ID::BI);
 237
 238                         if (!eval(sig_a, undef, cell))
 239                                 return false;
 240
 241                         if (!eval(sig_b, undef, cell))
 242                                 return false;
 243
 244                         if (!eval(sig_ci, undef, cell))
 245                                 return false;
 246
 247                         if (!eval(sig_bi, undef, cell))
 248                                 return false;
 249
 250                         RTLIL::SigSpec sig_x = cell->getPort(ID::X);
 251                         RTLIL::SigSpec sig_co = cell->getPort(ID::CO);
 252
 253                         bool any_input_undef = !(sig_a.is_fully_def() && sig_b.is_fully_def() && sig_ci.is_fully_def() && sig_bi.is_fully_def());
 254                         sig_a.extend_u0(GetSize(sig_y), signed_a);
 255                         sig_b.extend_u0(GetSize(sig_y), signed_b);
 256
 257                         bool carry = sig_ci[0] == State::S1;
 258                         bool b_inv = sig_bi[0] == State::S1;
 259
 260                         for (int i = 0; i < GetSize(sig_y); i++)
 261                         {
 262                                 RTLIL::SigSpec x_inputs = { sig_a[i], sig_b[i], sig_bi[0] };
 263
 264                                 if (!x_inputs.is_fully_def()) {
 265                                         set(sig_x[i], RTLIL::Sx);
 266                                 } else {
 267                                         bool bit_a = sig_a[i] == State::S1;
 268                                         bool bit_b = (sig_b[i] == State::S1) != b_inv;
 269                                         bool bit_x = bit_a != bit_b;
 270                                         set(sig_x[i], bit_x ? State::S1 : State::S0);
 271                                 }
 272
 273                                 if (any_input_undef) {
 274                                         set(sig_y[i], RTLIL::Sx);
 275                                         set(sig_co[i], RTLIL::Sx);
 276                                 } else {
 277                                         bool bit_a = sig_a[i] == State::S1;
 278                                         bool bit_b = (sig_b[i] == State::S1) != b_inv;
 279                                         bool bit_y = (bit_a != bit_b) != carry;
 280                                         carry = (bit_a && bit_b) || (bit_a && carry) || (bit_b && carry);
 281                                         set(sig_y[i], bit_y ? State::S1 : State::S0);
 282                                         set(sig_co[i], carry ? State::S1 : State::S0);
 283                                 }
 284                         }
 285                 }
 286                 else if (cell->type == ID($macc))
 287                 {
 288                         Macc macc;
 289                         macc.from_cell(cell);
 290
 291                         if (!eval(macc.bit_ports, undef, cell))
 292                                 return false;
 293
 294                         for (auto &port : macc.ports) {
 295                                 if (!eval(port.in_a, undef, cell))
 296                                         return false;
 297                                 if (!eval(port.in_b, undef, cell))
 298                                         return false;
 299                         }
 300
 301                         RTLIL::Const result(0, GetSize(cell->getPort(ID::Y)));
 302                         if (!macc.eval(result))
 303                                 log_abort();
 304
 305                         set(cell->getPort(ID::Y), result);
 306                 }
 307                 else
 308                 {
 309                         RTLIL::SigSpec sig_c, sig_d;
 310
 311                         if (cell->type.in(ID($_AOI3_), ID($_OAI3_), ID($_AOI4_), ID($_OAI4_))) {
 312                                 if (cell->hasPort(ID::C))
 313                                         sig_c = cell->getPort(ID::C);
 314                                 if (cell->hasPort(ID::D))
 315                                         sig_d = cell->getPort(ID::D);
 316                         }
 317
 318                         if (sig_a.size() > 0 && !eval(sig_a, undef, cell))
 319                                 return false;
 320                         if (sig_b.size() > 0 && !eval(sig_b, undef, cell))
 321                                 return false;
 322                         if (sig_c.size() > 0 && !eval(sig_c, undef, cell))
 323                                 return false;
 324                         if (sig_d.size() > 0 && !eval(sig_d, undef, cell))
 325                                 return false;
 326
 327                         bool eval_err = false;
 328                         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);
 329
 330                         if (eval_err)
 331                                 return false;
 332
 333                         set(sig_y, eval_ret);
 334                 }
 335
 336                 return true;
 337         }
 338
 339         bool eval(RTLIL::SigSpec &sig, RTLIL::SigSpec &undef, RTLIL::Cell *busy_cell = NULL)
 340         {
 341                 assign_map.apply(sig);
 342                 values_map.apply(sig);
 343
 344                 if (sig.is_fully_const())
 345                         return true;
 346
 347                 if (stop_signals.check_any(sig)) {
 348                         undef = stop_signals.extract(sig);
 349                         return false;
 350                 }
 351
 352                 if (busy_cell) {
 353                         if (busy.count(busy_cell) > 0) {
 354                                 undef = sig;
 355                                 return false;
 356                         }
 357                         busy.insert(busy_cell);
 358                 }
 359
 360                 std::set<RTLIL::Cell*> driver_cells;
 361                 sig2driver.find(sig, driver_cells);
 362                 for (auto cell : driver_cells) {
 363                         if (!eval(cell, undef)) {
 364                                 if (busy_cell)
 365                                         busy.erase(busy_cell);
 366                                 return false;
 367                         }
 368                 }
 369
 370                 if (busy_cell)
 371                         busy.erase(busy_cell);
 372
 373                 values_map.apply(sig);
 374                 if (sig.is_fully_const())
 375                         return true;
 376
 377                 if (defaultval != RTLIL::State::Sm) {
 378                         for (auto &bit : sig)
 379                                 if (bit.wire) bit = defaultval;
 380                         return true;
 381                 }
 382
 383                 for (auto &c : sig.chunks())
 384                         if (c.wire != NULL)
 385                                 undef.append(c);
 386                 return false;
 387         }
 388
 389         bool eval(RTLIL::SigSpec &sig)
 390         {
 391                 RTLIL::SigSpec undef;
 392                 return eval(sig, undef);
 393         }
 394 };
 395
 396 YOSYS_NAMESPACE_END
 397
 398 #endif