kernel/consteval.h

   1 /*
   2  *  yosys -- Yosys Open SYnthesis Suite
   3  *
   4  *  Copyright (C) 2012  Claire Xenia Wolf <claire@yosyshq.com>
   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                 }
 139
 140                 if (cell->hasPort(ID::A))
 141                         sig_a = cell->getPort(ID::A);
 142
 143                 if (cell->hasPort(ID::B))
 144                         sig_b = cell->getPort(ID::B);
 145
 146                 if (cell->type.in(ID($mux), ID($pmux), ID($_MUX_), ID($_NMUX_)))
 147                 {
 148                         std::vector<RTLIL::SigSpec> y_candidates;
 149                         int count_maybe_set_s_bits = 0;
 150                         int count_set_s_bits = 0;
 151
 152                         if (!eval(sig_s, undef, cell))
 153                                 return false;
 154
 155                         for (int i = 0; i < sig_s.size(); i++)
 156                         {
 157                                 RTLIL::State s_bit = sig_s.extract(i, 1).as_const().bits.at(0);
 158                                 RTLIL::SigSpec b_slice = sig_b.extract(sig_y.size()*i, sig_y.size());
 159
 160                                 if (s_bit == RTLIL::State::Sx || s_bit == RTLIL::State::S1)
 161                                         y_candidates.push_back(b_slice);
 162
 163                                 if (s_bit == RTLIL::State::S1 || s_bit == RTLIL::State::Sx)
 164                                         count_maybe_set_s_bits++;
 165
 166                                 if (s_bit == RTLIL::State::S1)
 167                                         count_set_s_bits++;
 168                         }
 169
 170                         if (count_set_s_bits == 0)
 171                                 y_candidates.push_back(sig_a);
 172
 173                         std::vector<RTLIL::Const> y_values;
 174
 175                         log_assert(y_candidates.size() > 0);
 176                         for (auto &yc : y_candidates) {
 177                                 if (!eval(yc, undef, cell))
 178                                         return false;
 179                                 if (cell->type == ID($_NMUX_))
 180                                         y_values.push_back(RTLIL::const_not(yc.as_const(), Const(), false, false, GetSize(yc)));
 181                                 else
 182                                         y_values.push_back(yc.as_const());
 183                         }
 184
 185                         if (y_values.size() > 1)
 186                         {
 187                                 std::vector<RTLIL::State> master_bits = y_values.at(0).bits;
 188
 189                                 for (size_t i = 1; i < y_values.size(); i++) {
 190                                         std::vector<RTLIL::State> &slave_bits = y_values.at(i).bits;
 191                                         log_assert(master_bits.size() == slave_bits.size());
 192                                         for (size_t j = 0; j < master_bits.size(); j++)
 193                                                 if (master_bits[j] != slave_bits[j])
 194                                                         master_bits[j] = RTLIL::State::Sx;
 195                                 }
 196
 197                                 set(sig_y, RTLIL::Const(master_bits));
 198                         }
 199                         else
 200                                 set(sig_y, y_values.front());
 201                 }
 202                 else if (cell->type == ID($bmux))
 203                 {
 204                         if (!eval(sig_s, undef, cell))
 205                                 return false;
 206
 207                         if (sig_s.is_fully_def()) {
 208                                 int sel = sig_s.as_int();
 209                                 int width = GetSize(sig_y);
 210                                 SigSpec res = sig_a.extract(sel * width, width);
 211                                 if (!eval(res, undef, cell))
 212                                         return false;
 213                                 set(sig_y, res.as_const());
 214                         } else {
 215                                 if (!eval(sig_a, undef, cell))
 216                                         return false;
 217                                 set(sig_y, const_bmux(sig_a.as_const(), sig_s.as_const()));
 218                         }
 219                 }
 220                 else if (cell->type == ID($demux))
 221                 {
 222                         if (!eval(sig_a, undef, cell))
 223                                 return false;
 224                         if (sig_a.is_fully_zero()) {
 225                                 set(sig_y, Const(0, GetSize(sig_y)));
 226                         } else {
 227                                 if (!eval(sig_s, undef, cell))
 228                                         return false;
 229                                 set(sig_y, const_demux(sig_a.as_const(), sig_s.as_const()));
 230                         }
 231                 }
 232                 else if (cell->type == ID($fa))
 233                 {
 234                         RTLIL::SigSpec sig_c = cell->getPort(ID::C);
 235                         RTLIL::SigSpec sig_x = cell->getPort(ID::X);
 236                         int width = GetSize(sig_c);
 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_c, undef, cell))
 245                                 return false;
 246
 247                         RTLIL::Const t1 = const_xor(sig_a.as_const(), sig_b.as_const(), false, false, width);
 248                         RTLIL::Const val_y = const_xor(t1, sig_c.as_const(), false, false, width);
 249
 250                         RTLIL::Const t2 = const_and(sig_a.as_const(), sig_b.as_const(), false, false, width);
 251                         RTLIL::Const t3 = const_and(sig_c.as_const(), t1, false, false, width);
 252                         RTLIL::Const val_x = const_or(t2, t3, false, false, width);
 253
 254                         for (int i = 0; i < GetSize(val_y); i++)
 255                                 if (val_y.bits[i] == RTLIL::Sx)
 256                                         val_x.bits[i] = RTLIL::Sx;
 257
 258                         set(sig_y, val_y);
 259                         set(sig_x, val_x);
 260                 }
 261                 else if (cell->type == ID($alu))
 262                 {
 263                         bool signed_a = cell->parameters.count(ID::A_SIGNED) > 0 && cell->parameters[ID::A_SIGNED].as_bool();
 264                         bool signed_b = cell->parameters.count(ID::B_SIGNED) > 0 && cell->parameters[ID::B_SIGNED].as_bool();
 265
 266                         RTLIL::SigSpec sig_ci = cell->getPort(ID::CI);
 267                         RTLIL::SigSpec sig_bi = cell->getPort(ID::BI);
 268
 269                         if (!eval(sig_a, undef, cell))
 270                                 return false;
 271
 272                         if (!eval(sig_b, undef, cell))
 273                                 return false;
 274
 275                         if (!eval(sig_ci, undef, cell))
 276                                 return false;
 277
 278                         if (!eval(sig_bi, undef, cell))
 279                                 return false;
 280
 281                         RTLIL::SigSpec sig_x = cell->getPort(ID::X);
 282                         RTLIL::SigSpec sig_co = cell->getPort(ID::CO);
 283
 284                         bool any_input_undef = !(sig_a.is_fully_def() && sig_b.is_fully_def() && sig_ci.is_fully_def() && sig_bi.is_fully_def());
 285                         sig_a.extend_u0(GetSize(sig_y), signed_a);
 286                         sig_b.extend_u0(GetSize(sig_y), signed_b);
 287
 288                         bool carry = sig_ci[0] == State::S1;
 289                         bool b_inv = sig_bi[0] == State::S1;
 290
 291                         for (int i = 0; i < GetSize(sig_y); i++)
 292                         {
 293                                 RTLIL::SigSpec x_inputs = { sig_a[i], sig_b[i], sig_bi[0] };
 294
 295                                 if (!x_inputs.is_fully_def()) {
 296                                         set(sig_x[i], RTLIL::Sx);
 297                                 } else {
 298                                         bool bit_a = sig_a[i] == State::S1;
 299                                         bool bit_b = (sig_b[i] == State::S1) != b_inv;
 300                                         bool bit_x = bit_a != bit_b;
 301                                         set(sig_x[i], bit_x ? State::S1 : State::S0);
 302                                 }
 303
 304                                 if (any_input_undef) {
 305                                         set(sig_y[i], RTLIL::Sx);
 306                                         set(sig_co[i], RTLIL::Sx);
 307                                 } else {
 308                                         bool bit_a = sig_a[i] == State::S1;
 309                                         bool bit_b = (sig_b[i] == State::S1) != b_inv;
 310                                         bool bit_y = (bit_a != bit_b) != carry;
 311                                         carry = (bit_a && bit_b) || (bit_a && carry) || (bit_b && carry);
 312                                         set(sig_y[i], bit_y ? State::S1 : State::S0);
 313                                         set(sig_co[i], carry ? State::S1 : State::S0);
 314                                 }
 315                         }
 316                 }
 317                 else if (cell->type == ID($macc))
 318                 {
 319                         Macc macc;
 320                         macc.from_cell(cell);
 321
 322                         if (!eval(macc.bit_ports, undef, cell))
 323                                 return false;
 324
 325                         for (auto &port : macc.ports) {
 326                                 if (!eval(port.in_a, undef, cell))
 327                                         return false;
 328                                 if (!eval(port.in_b, undef, cell))
 329                                         return false;
 330                         }
 331
 332                         RTLIL::Const result(0, GetSize(cell->getPort(ID::Y)));
 333                         if (!macc.eval(result))
 334                                 log_abort();
 335
 336                         set(cell->getPort(ID::Y), result);
 337                 }
 338                 else
 339                 {
 340                         RTLIL::SigSpec sig_c, sig_d;
 341
 342                         if (cell->type.in(ID($_AOI3_), ID($_OAI3_), ID($_AOI4_), ID($_OAI4_))) {
 343                                 if (cell->hasPort(ID::C))
 344                                         sig_c = cell->getPort(ID::C);
 345                                 if (cell->hasPort(ID::D))
 346                                         sig_d = cell->getPort(ID::D);
 347                         }
 348
 349                         if (sig_a.size() > 0 && !eval(sig_a, undef, cell))
 350                                 return false;
 351                         if (sig_b.size() > 0 && !eval(sig_b, undef, cell))
 352                                 return false;
 353                         if (sig_c.size() > 0 && !eval(sig_c, undef, cell))
 354                                 return false;
 355                         if (sig_d.size() > 0 && !eval(sig_d, undef, cell))
 356                                 return false;
 357
 358                         bool eval_err = false;
 359                         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);
 360
 361                         if (eval_err)
 362                                 return false;
 363
 364                         set(sig_y, eval_ret);
 365                 }
 366
 367                 return true;
 368         }
 369
 370         bool eval(RTLIL::SigSpec &sig, RTLIL::SigSpec &undef, RTLIL::Cell *busy_cell = NULL)
 371         {
 372                 assign_map.apply(sig);
 373                 values_map.apply(sig);
 374
 375                 if (sig.is_fully_const())
 376                         return true;
 377
 378                 if (stop_signals.check_any(sig)) {
 379                         undef = stop_signals.extract(sig);
 380                         return false;
 381                 }
 382
 383                 if (busy_cell) {
 384                         if (busy.count(busy_cell) > 0) {
 385                                 undef = sig;
 386                                 return false;
 387                         }
 388                         busy.insert(busy_cell);
 389                 }
 390
 391                 std::set<RTLIL::Cell*> driver_cells;
 392                 sig2driver.find(sig, driver_cells);
 393                 for (auto cell : driver_cells) {
 394                         if (!eval(cell, undef)) {
 395                                 if (busy_cell)
 396                                         busy.erase(busy_cell);
 397                                 return false;
 398                         }
 399                 }
 400
 401                 if (busy_cell)
 402                         busy.erase(busy_cell);
 403
 404                 values_map.apply(sig);
 405                 if (sig.is_fully_const())
 406                         return true;
 407
 408                 if (defaultval != RTLIL::State::Sm) {
 409                         for (auto &bit : sig)
 410                                 if (bit.wire) bit = defaultval;
 411                         return true;
 412                 }
 413
 414                 for (auto &c : sig.chunks())
 415                         if (c.wire != NULL)
 416                                 undef.append(c);
 417                 return false;
 418         }
 419
 420         bool eval(RTLIL::SigSpec &sig)
 421         {
 422                 RTLIL::SigSpec undef;
 423                 return eval(sig, undef);
 424         }
 425 };
 426
 427 YOSYS_NAMESPACE_END
 428
 429 #endif