kernel/satgen.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 SATGEN_H
  21 #define SATGEN_H
  22
  23 #include "kernel/rtlil.h"
  24 #include "kernel/sigtools.h"
  25 #include "kernel/celltypes.h"
  26
  27 #include "libs/ezsat/ezminisat.h"
  28 typedef ezMiniSAT ezDefaultSAT;
  29
  30 struct SatGen
  31 {
  32         ezSAT *ez;
  33         SigMap *sigmap;
  34         std::string prefix;
  35         SigPool initial_state;
  36         std::map<std::string, RTLIL::SigSpec> asserts_a, asserts_en;
  37         bool ignore_div_by_zero;
  38         bool model_undef;
  39
  40         SatGen(ezSAT *ez, SigMap *sigmap, std::string prefix = std::string()) :
  41                         ez(ez), sigmap(sigmap), prefix(prefix), ignore_div_by_zero(false), model_undef(false)
  42         {
  43         }
  44
  45         void setContext(SigMap *sigmap, std::string prefix = std::string())
  46         {
  47                 this->sigmap = sigmap;
  48                 this->prefix = prefix;
  49         }
  50
  51         std::vector<int> importSigSpecWorker(RTLIL::SigSpec &sig, std::string &pf, bool undef_mode, bool dup_undef)
  52         {
  53                 log_assert(!undef_mode || model_undef);
  54                 sigmap->apply(sig);
  55
  56                 std::vector<int> vec;
  57                 vec.reserve(SIZE(sig));
  58
  59                 for (auto &bit : sig)
  60                         if (bit.wire == NULL) {
  61                                 if (model_undef && dup_undef && bit == RTLIL::State::Sx)
  62                                         vec.push_back(ez->frozen_literal());
  63                                 else
  64                                         vec.push_back(bit == (undef_mode ? RTLIL::State::Sx : RTLIL::State::S1) ? ez->TRUE : ez->FALSE);
  65                         } else {
  66                                 std::string name = pf + stringf(bit.wire->width == 1 ?  "%s" : "%s [%d]", RTLIL::id2cstr(bit.wire->name), bit.offset);
  67                                 vec.push_back(ez->frozen_literal(name));
  68                         }
  69                 return vec;
  70         }
  71
  72         std::vector<int> importSigSpec(RTLIL::SigSpec sig, int timestep = -1)
  73         {
  74                 log_assert(timestep != 0);
  75                 std::string pf = prefix + (timestep == -1 ? "" : stringf("@%d:", timestep));
  76                 return importSigSpecWorker(sig, pf, false, false);
  77         }
  78
  79         std::vector<int> importDefSigSpec(RTLIL::SigSpec sig, int timestep = -1)
  80         {
  81                 log_assert(timestep != 0);
  82                 std::string pf = prefix + (timestep == -1 ? "" : stringf("@%d:", timestep));
  83                 return importSigSpecWorker(sig, pf, false, true);
  84         }
  85
  86         std::vector<int> importUndefSigSpec(RTLIL::SigSpec sig, int timestep = -1)
  87         {
  88                 log_assert(timestep != 0);
  89                 std::string pf = "undef:" + prefix + (timestep == -1 ? "" : stringf("@%d:", timestep));
  90                 return importSigSpecWorker(sig, pf, true, false);
  91         }
  92
  93         void getAsserts(RTLIL::SigSpec &sig_a, RTLIL::SigSpec &sig_en, int timestep = -1)
  94         {
  95                 std::string pf = prefix + (timestep == -1 ? "" : stringf("@%d:", timestep));
  96                 sig_a = asserts_a[pf];
  97                 sig_en = asserts_en[pf];
  98         }
  99
 100         int importAsserts(int timestep = -1)
 101         {
 102                 std::vector<int> check_bits, enable_bits;
 103                 std::string pf = prefix + (timestep == -1 ? "" : stringf("@%d:", timestep));
 104                 if (model_undef) {
 105                         check_bits = ez->vec_and(ez->vec_not(importUndefSigSpec(asserts_a[pf], timestep)), importDefSigSpec(asserts_a[pf], timestep));
 106                         enable_bits = ez->vec_and(ez->vec_not(importUndefSigSpec(asserts_en[pf], timestep)), importDefSigSpec(asserts_en[pf], timestep));
 107                 } else {
 108                         check_bits = importDefSigSpec(asserts_a[pf], timestep);
 109                         enable_bits = importDefSigSpec(asserts_en[pf], timestep);
 110                 }
 111                 return ez->vec_reduce_and(ez->vec_or(check_bits, ez->vec_not(enable_bits)));
 112         }
 113
 114         int signals_eq(RTLIL::SigSpec lhs, RTLIL::SigSpec rhs, int timestep_lhs = -1, int timestep_rhs = -1)
 115         {
 116                 if (timestep_rhs < 0)
 117                         timestep_rhs = timestep_lhs;
 118
 119                 log_assert(lhs.size() == rhs.size());
 120
 121                 std::vector<int> vec_lhs = importSigSpec(lhs, timestep_lhs);
 122                 std::vector<int> vec_rhs = importSigSpec(rhs, timestep_rhs);
 123
 124                 if (!model_undef)
 125                         return ez->vec_eq(vec_lhs, vec_rhs);
 126
 127                 std::vector<int> undef_lhs = importUndefSigSpec(lhs, timestep_lhs);
 128                 std::vector<int> undef_rhs = importUndefSigSpec(rhs, timestep_rhs);
 129
 130                 std::vector<int> eq_bits;
 131                 for (int i = 0; i < lhs.size(); i++)
 132                         eq_bits.push_back(ez->AND(ez->IFF(undef_lhs.at(i), undef_rhs.at(i)),
 133                                         ez->IFF(ez->OR(vec_lhs.at(i), undef_lhs.at(i)), ez->OR(vec_rhs.at(i), undef_rhs.at(i)))));
 134                 return ez->expression(ezSAT::OpAnd, eq_bits);
 135         }
 136
 137         void extendSignalWidth(std::vector<int> &vec_a, std::vector<int> &vec_b, RTLIL::Cell *cell, size_t y_width = 0, bool forced_signed = false)
 138         {
 139                 bool is_signed = forced_signed;
 140                 if (!forced_signed && cell->parameters.count("\\A_SIGNED") > 0 && cell->parameters.count("\\B_SIGNED") > 0)
 141                         is_signed = cell->parameters["\\A_SIGNED"].as_bool() && cell->parameters["\\B_SIGNED"].as_bool();
 142                 while (vec_a.size() < vec_b.size() || vec_a.size() < y_width)
 143                         vec_a.push_back(is_signed && vec_a.size() > 0 ? vec_a.back() : ez->FALSE);
 144                 while (vec_b.size() < vec_a.size() || vec_b.size() < y_width)
 145                         vec_b.push_back(is_signed && vec_b.size() > 0 ? vec_b.back() : ez->FALSE);
 146         }
 147
 148         void extendSignalWidth(std::vector<int> &vec_a, std::vector<int> &vec_b, std::vector<int> &vec_y, RTLIL::Cell *cell, bool forced_signed = false)
 149         {
 150                 extendSignalWidth(vec_a, vec_b, cell, vec_y.size(), forced_signed);
 151                 while (vec_y.size() < vec_a.size())
 152                         vec_y.push_back(ez->literal());
 153         }
 154
 155         void extendSignalWidthUnary(std::vector<int> &vec_a, std::vector<int> &vec_y, RTLIL::Cell *cell, bool forced_signed = false)
 156         {
 157                 bool is_signed = forced_signed || (cell->parameters.count("\\A_SIGNED") > 0 && cell->parameters["\\A_SIGNED"].as_bool());
 158                 while (vec_a.size() < vec_y.size())
 159                         vec_a.push_back(is_signed && vec_a.size() > 0 ? vec_a.back() : ez->FALSE);
 160                 while (vec_y.size() < vec_a.size())
 161                         vec_y.push_back(ez->literal());
 162         }
 163
 164         void undefGating(std::vector<int> &vec_y, std::vector<int> &vec_yy, std::vector<int> &vec_undef)
 165         {
 166                 log_assert(model_undef);
 167                 log_assert(vec_y.size() == vec_yy.size());
 168                 if (vec_y.size() > vec_undef.size()) {
 169                         std::vector<int> trunc_y(vec_y.begin(), vec_y.begin() + vec_undef.size());
 170                         std::vector<int> trunc_yy(vec_yy.begin(), vec_yy.begin() + vec_undef.size());
 171                         ez->assume(ez->expression(ezSAT::OpAnd, ez->vec_or(vec_undef, ez->vec_iff(trunc_y, trunc_yy))));
 172                 } else {
 173                         log_assert(vec_y.size() == vec_undef.size());
 174                         ez->assume(ez->expression(ezSAT::OpAnd, ez->vec_or(vec_undef, ez->vec_iff(vec_y, vec_yy))));
 175                 }
 176         }
 177
 178         bool importCell(RTLIL::Cell *cell, int timestep = -1)
 179         {
 180                 bool arith_undef_handled = false;
 181                 bool is_arith_compare = cell->type == "$lt" || cell->type == "$le" || cell->type == "$ge" || cell->type == "$gt";
 182
 183                 if (model_undef && (cell->type == "$add" || cell->type == "$sub" || cell->type == "$mul" || cell->type == "$div" || cell->type == "$mod" || is_arith_compare))
 184                 {
 185                         std::vector<int> undef_a = importUndefSigSpec(cell->getPort("\\A"), timestep);
 186                         std::vector<int> undef_b = importUndefSigSpec(cell->getPort("\\B"), timestep);
 187                         std::vector<int> undef_y = importUndefSigSpec(cell->getPort("\\Y"), timestep);
 188                         if (is_arith_compare)
 189                                 extendSignalWidth(undef_a, undef_b, cell, true);
 190                         else
 191                                 extendSignalWidth(undef_a, undef_b, undef_y, cell, true);
 192
 193                         int undef_any_a = ez->expression(ezSAT::OpOr, undef_a);
 194                         int undef_any_b = ez->expression(ezSAT::OpOr, undef_b);
 195                         int undef_y_bit = ez->OR(undef_any_a, undef_any_b);
 196
 197                         if (cell->type == "$div" || cell->type == "$mod") {
 198                                 std::vector<int> b = importSigSpec(cell->getPort("\\B"), timestep);
 199                                 undef_y_bit = ez->OR(undef_y_bit, ez->NOT(ez->expression(ezSAT::OpOr, b)));
 200                         }
 201
 202                         if (is_arith_compare) {
 203                                 for (size_t i = 1; i < undef_y.size(); i++)
 204                                         ez->SET(ez->FALSE, undef_y.at(i));
 205                                 ez->SET(undef_y_bit, undef_y.at(0));
 206                         } else {
 207                                 std::vector<int> undef_y_bits(undef_y.size(), undef_y_bit);
 208                                 ez->assume(ez->vec_eq(undef_y_bits, undef_y));
 209                         }
 210
 211                         arith_undef_handled = true;
 212                 }
 213
 214                 if (cell->type == "$_AND_" || cell->type == "$_OR_" || cell->type == "$_XOR_" ||
 215                                 cell->type == "$and" || cell->type == "$or" || cell->type == "$xor" || cell->type == "$xnor" ||
 216                                 cell->type == "$add" || cell->type == "$sub")
 217                 {
 218                         std::vector<int> a = importDefSigSpec(cell->getPort("\\A"), timestep);
 219                         std::vector<int> b = importDefSigSpec(cell->getPort("\\B"), timestep);
 220                         std::vector<int> y = importDefSigSpec(cell->getPort("\\Y"), timestep);
 221                         extendSignalWidth(a, b, y, cell);
 222
 223                         std::vector<int> yy = model_undef ? ez->vec_var(y.size()) : y;
 224
 225                         if (cell->type == "$and" || cell->type == "$_AND_")
 226                                 ez->assume(ez->vec_eq(ez->vec_and(a, b), yy));
 227                         if (cell->type == "$or" || cell->type == "$_OR_")
 228                                 ez->assume(ez->vec_eq(ez->vec_or(a, b), yy));
 229                         if (cell->type == "$xor" || cell->type == "$_XOR_")
 230                                 ez->assume(ez->vec_eq(ez->vec_xor(a, b), yy));
 231                         if (cell->type == "$xnor")
 232                                 ez->assume(ez->vec_eq(ez->vec_not(ez->vec_xor(a, b)), yy));
 233                         if (cell->type == "$add")
 234                                 ez->assume(ez->vec_eq(ez->vec_add(a, b), yy));
 235                         if (cell->type == "$sub")
 236                                 ez->assume(ez->vec_eq(ez->vec_sub(a, b), yy));
 237
 238                         if (model_undef && !arith_undef_handled)
 239                         {
 240                                 std::vector<int> undef_a = importUndefSigSpec(cell->getPort("\\A"), timestep);
 241                                 std::vector<int> undef_b = importUndefSigSpec(cell->getPort("\\B"), timestep);
 242                                 std::vector<int> undef_y = importUndefSigSpec(cell->getPort("\\Y"), timestep);
 243                                 extendSignalWidth(undef_a, undef_b, undef_y, cell, false);
 244
 245                                 if (cell->type == "$and" || cell->type == "$_AND_") {
 246                                         std::vector<int> a0 = ez->vec_and(ez->vec_not(a), ez->vec_not(undef_a));
 247                                         std::vector<int> b0 = ez->vec_and(ez->vec_not(b), ez->vec_not(undef_b));
 248                                         std::vector<int> yX = ez->vec_and(ez->vec_or(undef_a, undef_b), ez->vec_not(ez->vec_or(a0, b0)));
 249                                         ez->assume(ez->vec_eq(yX, undef_y));
 250                                 }
 251                                 else if (cell->type == "$or" || cell->type == "$_OR_") {
 252                                         std::vector<int> a1 = ez->vec_and(a, ez->vec_not(undef_a));
 253                                         std::vector<int> b1 = ez->vec_and(b, ez->vec_not(undef_b));
 254                                         std::vector<int> yX = ez->vec_and(ez->vec_or(undef_a, undef_b), ez->vec_not(ez->vec_or(a1, b1)));
 255                                         ez->assume(ez->vec_eq(yX, undef_y));
 256                                 }
 257                                 else if (cell->type == "$xor" || cell->type == "$_XOR_" || cell->type == "$xnor") {
 258                                         std::vector<int> yX = ez->vec_or(undef_a, undef_b);
 259                                         ez->assume(ez->vec_eq(yX, undef_y));
 260                                 }
 261                                 else
 262                                         log_abort();
 263
 264                                 undefGating(y, yy, undef_y);
 265                         }
 266                         else if (model_undef)
 267                         {
 268                                 std::vector<int> undef_y = importUndefSigSpec(cell->getPort("\\Y"), timestep);
 269                                 undefGating(y, yy, undef_y);
 270                         }
 271                         return true;
 272                 }
 273
 274                 if (cell->type == "$_INV_" || cell->type == "$not")
 275                 {
 276                         std::vector<int> a = importDefSigSpec(cell->getPort("\\A"), timestep);
 277                         std::vector<int> y = importDefSigSpec(cell->getPort("\\Y"), timestep);
 278                         extendSignalWidthUnary(a, y, cell);
 279
 280                         std::vector<int> yy = model_undef ? ez->vec_var(y.size()) : y;
 281                         ez->assume(ez->vec_eq(ez->vec_not(a), yy));
 282
 283                         if (model_undef) {
 284                                 std::vector<int> undef_a = importUndefSigSpec(cell->getPort("\\A"), timestep);
 285                                 std::vector<int> undef_y = importUndefSigSpec(cell->getPort("\\Y"), timestep);
 286                                 extendSignalWidthUnary(undef_a, undef_y, cell, true);
 287                                 ez->assume(ez->vec_eq(undef_a, undef_y));
 288                                 undefGating(y, yy, undef_y);
 289                         }
 290                         return true;
 291                 }
 292
 293                 if (cell->type == "$_MUX_" || cell->type == "$mux")
 294                 {
 295                         std::vector<int> a = importDefSigSpec(cell->getPort("\\A"), timestep);
 296                         std::vector<int> b = importDefSigSpec(cell->getPort("\\B"), timestep);
 297                         std::vector<int> s = importDefSigSpec(cell->getPort("\\S"), timestep);
 298                         std::vector<int> y = importDefSigSpec(cell->getPort("\\Y"), timestep);
 299
 300                         std::vector<int> yy = model_undef ? ez->vec_var(y.size()) : y;
 301                         ez->assume(ez->vec_eq(ez->vec_ite(s.at(0), b, a), yy));
 302
 303                         if (model_undef)
 304                         {
 305                                 std::vector<int> undef_a = importUndefSigSpec(cell->getPort("\\A"), timestep);
 306                                 std::vector<int> undef_b = importUndefSigSpec(cell->getPort("\\B"), timestep);
 307                                 std::vector<int> undef_s = importUndefSigSpec(cell->getPort("\\S"), timestep);
 308                                 std::vector<int> undef_y = importUndefSigSpec(cell->getPort("\\Y"), timestep);
 309
 310                                 std::vector<int> unequal_ab = ez->vec_not(ez->vec_iff(a, b));
 311                                 std::vector<int> undef_ab = ez->vec_or(unequal_ab, ez->vec_or(undef_a, undef_b));
 312                                 std::vector<int> yX = ez->vec_ite(undef_s.at(0), undef_ab, ez->vec_ite(s.at(0), undef_b, undef_a));
 313                                 ez->assume(ez->vec_eq(yX, undef_y));
 314                                 undefGating(y, yy, undef_y);
 315                         }
 316                         return true;
 317                 }
 318
 319                 if (cell->type == "$pmux" || cell->type == "$safe_pmux")
 320                 {
 321                         std::vector<int> a = importDefSigSpec(cell->getPort("\\A"), timestep);
 322                         std::vector<int> b = importDefSigSpec(cell->getPort("\\B"), timestep);
 323                         std::vector<int> s = importDefSigSpec(cell->getPort("\\S"), timestep);
 324                         std::vector<int> y = importDefSigSpec(cell->getPort("\\Y"), timestep);
 325
 326                         std::vector<int> yy = model_undef ? ez->vec_var(y.size()) : y;
 327
 328                         std::vector<int> tmp = a;
 329                         for (size_t i = 0; i < s.size(); i++) {
 330                                 std::vector<int> part_of_b(b.begin()+i*a.size(), b.begin()+(i+1)*a.size());
 331                                 tmp = ez->vec_ite(s.at(i), part_of_b, tmp);
 332                         }
 333                         if (cell->type == "$safe_pmux")
 334                                 tmp = ez->vec_ite(ez->onehot(s, true), tmp, a);
 335                         ez->assume(ez->vec_eq(tmp, yy));
 336
 337                         if (model_undef)
 338                         {
 339                                 std::vector<int> undef_a = importUndefSigSpec(cell->getPort("\\A"), timestep);
 340                                 std::vector<int> undef_b = importUndefSigSpec(cell->getPort("\\B"), timestep);
 341                                 std::vector<int> undef_s = importUndefSigSpec(cell->getPort("\\S"), timestep);
 342                                 std::vector<int> undef_y = importUndefSigSpec(cell->getPort("\\Y"), timestep);
 343
 344                                 int maybe_one_hot = ez->FALSE;
 345                                 int maybe_many_hot = ez->FALSE;
 346
 347                                 int sure_one_hot = ez->FALSE;
 348                                 int sure_many_hot = ez->FALSE;
 349
 350                                 std::vector<int> bits_set = std::vector<int>(undef_y.size(), ez->FALSE);
 351                                 std::vector<int> bits_clr = std::vector<int>(undef_y.size(), ez->FALSE);
 352
 353                                 for (size_t i = 0; i < s.size(); i++)
 354                                 {
 355                                         std::vector<int> part_of_b(b.begin()+i*a.size(), b.begin()+(i+1)*a.size());
 356                                         std::vector<int> part_of_undef_b(undef_b.begin()+i*a.size(), undef_b.begin()+(i+1)*a.size());
 357
 358                                         int maybe_s = ez->OR(s.at(i), undef_s.at(i));
 359                                         int sure_s = ez->AND(s.at(i), ez->NOT(undef_s.at(i)));
 360
 361                                         maybe_one_hot = ez->OR(maybe_one_hot, maybe_s);
 362                                         maybe_many_hot = ez->OR(maybe_many_hot, ez->AND(maybe_one_hot, maybe_s));
 363
 364                                         sure_one_hot = ez->OR(sure_one_hot, sure_s);
 365                                         sure_many_hot = ez->OR(sure_many_hot, ez->AND(sure_one_hot, sure_s));
 366
 367                                         bits_set = ez->vec_ite(maybe_s, ez->vec_or(bits_set, ez->vec_or(bits_set, ez->vec_or(part_of_b, part_of_undef_b))), bits_set);
 368                                         bits_clr = ez->vec_ite(maybe_s, ez->vec_or(bits_clr, ez->vec_or(bits_clr, ez->vec_or(ez->vec_not(part_of_b), part_of_undef_b))), bits_clr);
 369                                 }
 370
 371                                 int maybe_a = ez->NOT(maybe_one_hot);
 372
 373                                 if (cell->type == "$safe_pmux") {
 374                                         maybe_a = ez->OR(maybe_a, maybe_many_hot);
 375                                         bits_set = ez->vec_ite(sure_many_hot, ez->vec_or(a, undef_a), bits_set);
 376                                         bits_clr = ez->vec_ite(sure_many_hot, ez->vec_or(ez->vec_not(a), undef_a), bits_clr);
 377                                 }
 378
 379                                 bits_set = ez->vec_ite(maybe_a, ez->vec_or(bits_set, ez->vec_or(bits_set, ez->vec_or(a, undef_a))), bits_set);
 380                                 bits_clr = ez->vec_ite(maybe_a, ez->vec_or(bits_clr, ez->vec_or(bits_clr, ez->vec_or(ez->vec_not(a), undef_a))), bits_clr);
 381
 382                                 ez->assume(ez->vec_eq(ez->vec_not(ez->vec_xor(bits_set, bits_clr)), undef_y));
 383                                 undefGating(y, yy, undef_y);
 384                         }
 385                         return true;
 386                 }
 387
 388                 if (cell->type == "$pos" || cell->type == "$bu0" || cell->type == "$neg")
 389                 {
 390                         std::vector<int> a = importDefSigSpec(cell->getPort("\\A"), timestep);
 391                         std::vector<int> y = importDefSigSpec(cell->getPort("\\Y"), timestep);
 392                         extendSignalWidthUnary(a, y, cell);
 393
 394                         std::vector<int> yy = model_undef ? ez->vec_var(y.size()) : y;
 395
 396                         if (cell->type == "$pos" || cell->type == "$bu0") {
 397                                 ez->assume(ez->vec_eq(a, yy));
 398                         } else {
 399                                 std::vector<int> zero(a.size(), ez->FALSE);
 400                                 ez->assume(ez->vec_eq(ez->vec_sub(zero, a), yy));
 401                         }
 402
 403                         if (model_undef)
 404                         {
 405                                 std::vector<int> undef_a = importUndefSigSpec(cell->getPort("\\A"), timestep);
 406                                 std::vector<int> undef_y = importUndefSigSpec(cell->getPort("\\Y"), timestep);
 407                                 extendSignalWidthUnary(undef_a, undef_y, cell, cell->type != "$bu0");
 408
 409                                 if (cell->type == "$pos" || cell->type == "$bu0") {
 410                                         ez->assume(ez->vec_eq(undef_a, undef_y));
 411                                 } else {
 412                                         int undef_any_a = ez->expression(ezSAT::OpOr, undef_a);
 413                                         std::vector<int> undef_y_bits(undef_y.size(), undef_any_a);
 414                                         ez->assume(ez->vec_eq(undef_y_bits, undef_y));
 415                                 }
 416
 417                                 undefGating(y, yy, undef_y);
 418                         }
 419                         return true;
 420                 }
 421
 422                 if (cell->type == "$reduce_and" || cell->type == "$reduce_or" || cell->type == "$reduce_xor" ||
 423                                 cell->type == "$reduce_xnor" || cell->type == "$reduce_bool" || cell->type == "$logic_not")
 424                 {
 425                         std::vector<int> a = importDefSigSpec(cell->getPort("\\A"), timestep);
 426                         std::vector<int> y = importDefSigSpec(cell->getPort("\\Y"), timestep);
 427
 428                         std::vector<int> yy = model_undef ? ez->vec_var(y.size()) : y;
 429
 430                         if (cell->type == "$reduce_and")
 431                                 ez->SET(ez->expression(ez->OpAnd, a), yy.at(0));
 432                         if (cell->type == "$reduce_or" || cell->type == "$reduce_bool")
 433                                 ez->SET(ez->expression(ez->OpOr, a), yy.at(0));
 434                         if (cell->type == "$reduce_xor")
 435                                 ez->SET(ez->expression(ez->OpXor, a), yy.at(0));
 436                         if (cell->type == "$reduce_xnor")
 437                                 ez->SET(ez->NOT(ez->expression(ez->OpXor, a)), yy.at(0));
 438                         if (cell->type == "$logic_not")
 439                                 ez->SET(ez->NOT(ez->expression(ez->OpOr, a)), yy.at(0));
 440                         for (size_t i = 1; i < y.size(); i++)
 441                                 ez->SET(ez->FALSE, yy.at(i));
 442
 443                         if (model_undef)
 444                         {
 445                                 std::vector<int> undef_a = importUndefSigSpec(cell->getPort("\\A"), timestep);
 446                                 std::vector<int> undef_y = importUndefSigSpec(cell->getPort("\\Y"), timestep);
 447                                 int aX = ez->expression(ezSAT::OpOr, undef_a);
 448
 449                                 if (cell->type == "$reduce_and") {
 450                                         int a0 = ez->expression(ezSAT::OpOr, ez->vec_and(ez->vec_not(a), ez->vec_not(undef_a)));
 451                                         ez->assume(ez->IFF(ez->AND(ez->NOT(a0), aX), undef_y.at(0)));
 452                                 }
 453                                 else if (cell->type == "$reduce_or" || cell->type == "$reduce_bool" || cell->type == "$logic_not") {
 454                                         int a1 = ez->expression(ezSAT::OpOr, ez->vec_and(a, ez->vec_not(undef_a)));
 455                                         ez->assume(ez->IFF(ez->AND(ez->NOT(a1), aX), undef_y.at(0)));
 456                                 }
 457                                 else if (cell->type == "$reduce_xor" || cell->type == "$reduce_xnor") {
 458                                         ez->assume(ez->IFF(aX, undef_y.at(0)));
 459                                 } else
 460                                         log_abort();
 461
 462                                 for (size_t i = 1; i < undef_y.size(); i++)
 463                                         ez->SET(ez->FALSE, undef_y.at(i));
 464
 465                                 undefGating(y, yy, undef_y);
 466                         }
 467                         return true;
 468                 }
 469
 470                 if (cell->type == "$logic_and" || cell->type == "$logic_or")
 471                 {
 472                         std::vector<int> vec_a = importDefSigSpec(cell->getPort("\\A"), timestep);
 473                         std::vector<int> vec_b = importDefSigSpec(cell->getPort("\\B"), timestep);
 474
 475                         int a = ez->expression(ez->OpOr, vec_a);
 476                         int b = ez->expression(ez->OpOr, vec_b);
 477                         std::vector<int> y = importDefSigSpec(cell->getPort("\\Y"), timestep);
 478
 479                         std::vector<int> yy = model_undef ? ez->vec_var(y.size()) : y;
 480
 481                         if (cell->type == "$logic_and")
 482                                 ez->SET(ez->expression(ez->OpAnd, a, b), yy.at(0));
 483                         else
 484                                 ez->SET(ez->expression(ez->OpOr, a, b), yy.at(0));
 485                         for (size_t i = 1; i < y.size(); i++)
 486                                 ez->SET(ez->FALSE, yy.at(i));
 487
 488                         if (model_undef)
 489                         {
 490                                 std::vector<int> undef_a = importUndefSigSpec(cell->getPort("\\A"), timestep);
 491                                 std::vector<int> undef_b = importUndefSigSpec(cell->getPort("\\B"), timestep);
 492                                 std::vector<int> undef_y = importUndefSigSpec(cell->getPort("\\Y"), timestep);
 493
 494                                 int a0 = ez->NOT(ez->OR(ez->expression(ezSAT::OpOr, vec_a), ez->expression(ezSAT::OpOr, undef_a)));
 495                                 int b0 = ez->NOT(ez->OR(ez->expression(ezSAT::OpOr, vec_b), ez->expression(ezSAT::OpOr, undef_b)));
 496                                 int a1 = ez->expression(ezSAT::OpOr, ez->vec_and(vec_a, ez->vec_not(undef_a)));
 497                                 int b1 = ez->expression(ezSAT::OpOr, ez->vec_and(vec_b, ez->vec_not(undef_b)));
 498                                 int aX = ez->expression(ezSAT::OpOr, undef_a);
 499                                 int bX = ez->expression(ezSAT::OpOr, undef_b);
 500
 501                                 if (cell->type == "$logic_and")
 502                                         ez->SET(ez->AND(ez->OR(aX, bX), ez->NOT(ez->AND(a1, b1)), ez->NOT(a0), ez->NOT(b0)), undef_y.at(0));
 503                                 else if (cell->type == "$logic_or")
 504                                         ez->SET(ez->AND(ez->OR(aX, bX), ez->NOT(ez->AND(a0, b0)), ez->NOT(a1), ez->NOT(b1)), undef_y.at(0));
 505                                 else
 506                                         log_abort();
 507
 508                                 for (size_t i = 1; i < undef_y.size(); i++)
 509                                         ez->SET(ez->FALSE, undef_y.at(i));
 510
 511                                 undefGating(y, yy, undef_y);
 512                         }
 513                         return true;
 514                 }
 515
 516                 if (cell->type == "$lt" || cell->type == "$le" || cell->type == "$eq" || cell->type == "$ne" || cell->type == "$eqx" || cell->type == "$nex" || cell->type == "$ge" || cell->type == "$gt")
 517                 {
 518                         bool is_signed = cell->parameters["\\A_SIGNED"].as_bool() && cell->parameters["\\B_SIGNED"].as_bool();
 519                         std::vector<int> a = importDefSigSpec(cell->getPort("\\A"), timestep);
 520                         std::vector<int> b = importDefSigSpec(cell->getPort("\\B"), timestep);
 521                         std::vector<int> y = importDefSigSpec(cell->getPort("\\Y"), timestep);
 522                         extendSignalWidth(a, b, cell);
 523
 524                         std::vector<int> yy = model_undef ? ez->vec_var(y.size()) : y;
 525
 526                         if (model_undef && (cell->type == "$eqx" || cell->type == "$nex")) {
 527                                 std::vector<int> undef_a = importUndefSigSpec(cell->getPort("\\A"), timestep);
 528                                 std::vector<int> undef_b = importUndefSigSpec(cell->getPort("\\B"), timestep);
 529                                 extendSignalWidth(undef_a, undef_b, cell, true);
 530                                 a = ez->vec_or(a, undef_a);
 531                                 b = ez->vec_or(b, undef_b);
 532                         }
 533
 534                         if (cell->type == "$lt")
 535                                 ez->SET(is_signed ? ez->vec_lt_signed(a, b) : ez->vec_lt_unsigned(a, b), yy.at(0));
 536                         if (cell->type == "$le")
 537                                 ez->SET(is_signed ? ez->vec_le_signed(a, b) : ez->vec_le_unsigned(a, b), yy.at(0));
 538                         if (cell->type == "$eq" || cell->type == "$eqx")
 539                                 ez->SET(ez->vec_eq(a, b), yy.at(0));
 540                         if (cell->type == "$ne" || cell->type == "$nex")
 541                                 ez->SET(ez->vec_ne(a, b), yy.at(0));
 542                         if (cell->type == "$ge")
 543                                 ez->SET(is_signed ? ez->vec_ge_signed(a, b) : ez->vec_ge_unsigned(a, b), yy.at(0));
 544                         if (cell->type == "$gt")
 545                                 ez->SET(is_signed ? ez->vec_gt_signed(a, b) : ez->vec_gt_unsigned(a, b), yy.at(0));
 546                         for (size_t i = 1; i < y.size(); i++)
 547                                 ez->SET(ez->FALSE, yy.at(i));
 548
 549                         if (model_undef && (cell->type == "$eqx" || cell->type == "$nex"))
 550                         {
 551                                 std::vector<int> undef_a = importUndefSigSpec(cell->getPort("\\A"), timestep);
 552                                 std::vector<int> undef_b = importUndefSigSpec(cell->getPort("\\B"), timestep);
 553                                 std::vector<int> undef_y = importUndefSigSpec(cell->getPort("\\Y"), timestep);
 554                                 extendSignalWidth(undef_a, undef_b, cell, true);
 555
 556                                 if (cell->type == "$eqx")
 557                                         yy.at(0) = ez->AND(yy.at(0), ez->vec_eq(undef_a, undef_b));
 558                                 else
 559                                         yy.at(0) = ez->OR(yy.at(0), ez->vec_ne(undef_a, undef_b));
 560
 561                                 for (size_t i = 0; i < y.size(); i++)
 562                                         ez->SET(ez->FALSE, undef_y.at(i));
 563
 564                                 ez->assume(ez->vec_eq(y, yy));
 565                         }
 566                         else if (model_undef && (cell->type == "$eq" || cell->type == "$ne"))
 567                         {
 568                                 std::vector<int> undef_a = importUndefSigSpec(cell->getPort("\\A"), timestep);
 569                                 std::vector<int> undef_b = importUndefSigSpec(cell->getPort("\\B"), timestep);
 570                                 std::vector<int> undef_y = importUndefSigSpec(cell->getPort("\\Y"), timestep);
 571                                 extendSignalWidth(undef_a, undef_b, cell, true);
 572
 573                                 int undef_any_a = ez->expression(ezSAT::OpOr, undef_a);
 574                                 int undef_any_b = ez->expression(ezSAT::OpOr, undef_b);
 575                                 int undef_any = ez->OR(undef_any_a, undef_any_b);
 576
 577                                 std::vector<int> masked_a_bits = ez->vec_or(a, ez->vec_or(undef_a, undef_b));
 578                                 std::vector<int> masked_b_bits = ez->vec_or(b, ez->vec_or(undef_a, undef_b));
 579
 580                                 int masked_ne = ez->vec_ne(masked_a_bits, masked_b_bits);
 581                                 int undef_y_bit = ez->AND(undef_any, ez->NOT(masked_ne));
 582
 583                                 for (size_t i = 1; i < undef_y.size(); i++)
 584                                         ez->SET(ez->FALSE, undef_y.at(i));
 585                                 ez->SET(undef_y_bit, undef_y.at(0));
 586
 587                                 undefGating(y, yy, undef_y);
 588                         }
 589                         else
 590                         {
 591                                 if (model_undef) {
 592                                         std::vector<int> undef_y = importUndefSigSpec(cell->getPort("\\Y"), timestep);
 593                                         undefGating(y, yy, undef_y);
 594                                 }
 595                                 log_assert(!model_undef || arith_undef_handled);
 596                         }
 597                         return true;
 598                 }
 599
 600                 if (cell->type == "$shl" || cell->type == "$shr" || cell->type == "$sshl" || cell->type == "$sshr" || cell->type == "$shift" || cell->type == "$shiftx")
 601                 {
 602                         std::vector<int> a = importDefSigSpec(cell->getPort("\\A"), timestep);
 603                         std::vector<int> b = importDefSigSpec(cell->getPort("\\B"), timestep);
 604                         std::vector<int> y = importDefSigSpec(cell->getPort("\\Y"), timestep);
 605
 606                         int extend_bit = ez->FALSE;
 607
 608                         if (cell->type != "$shift" && cell->type != "$shiftx" && cell->parameters["\\A_SIGNED"].as_bool())
 609                                 extend_bit = a.back();
 610
 611                         while (y.size() < a.size())
 612                                 y.push_back(ez->literal());
 613                         while (y.size() > a.size())
 614                                 a.push_back(extend_bit);
 615
 616                         std::vector<int> yy = model_undef ? ez->vec_var(y.size()) : y;
 617                         std::vector<int> shifted_a;
 618
 619                         if (cell->type == "$shl" || cell->type == "$sshl")
 620                                 shifted_a = ez->vec_shift_left(a, b, false, ez->FALSE, ez->FALSE);
 621
 622                         if (cell->type == "$shr")
 623                                 shifted_a = ez->vec_shift_right(a, b, false, ez->FALSE, ez->FALSE);
 624
 625                         if (cell->type == "$sshr")
 626                                 shifted_a = ez->vec_shift_right(a, b, false, cell->parameters["\\A_SIGNED"].as_bool() ? a.back() : ez->FALSE, ez->FALSE);
 627
 628                         if (cell->type == "$shift" || cell->type == "$shiftx")
 629                                 shifted_a = ez->vec_shift_right(a, b, cell->parameters["\\B_SIGNED"].as_bool(), ez->FALSE, ez->FALSE);
 630
 631                         ez->assume(ez->vec_eq(shifted_a, yy));
 632
 633                         if (model_undef)
 634                         {
 635                                 std::vector<int> undef_a = importUndefSigSpec(cell->getPort("\\A"), timestep);
 636                                 std::vector<int> undef_b = importUndefSigSpec(cell->getPort("\\B"), timestep);
 637                                 std::vector<int> undef_y = importUndefSigSpec(cell->getPort("\\Y"), timestep);
 638                                 std::vector<int> undef_a_shifted;
 639
 640                                 if (cell->type != "$shift" && cell->type != "$shiftx" && cell->parameters["\\A_SIGNED"].as_bool())
 641                                         extend_bit = undef_a.back();
 642
 643                                 while (undef_y.size() < undef_a.size())
 644                                         undef_y.push_back(ez->literal());
 645                                 while (undef_y.size() > undef_a.size())
 646                                         undef_a.push_back(extend_bit);
 647
 648                                 if (cell->type == "$shl" || cell->type == "$sshl")
 649                                         undef_a_shifted = ez->vec_shift_left(undef_a, b, false, ez->FALSE, ez->FALSE);
 650
 651                                 if (cell->type == "$shr")
 652                                         undef_a_shifted = ez->vec_shift_right(undef_a, b, false, ez->FALSE, ez->FALSE);
 653
 654                                 if (cell->type == "$sshr")
 655                                         undef_a_shifted = ez->vec_shift_right(undef_a, b, false, cell->parameters["\\A_SIGNED"].as_bool() ? undef_a.back() : ez->FALSE, ez->FALSE);
 656
 657                                 if (cell->type == "$shift")
 658                                         undef_a_shifted = ez->vec_shift_right(undef_a, b, cell->parameters["\\B_SIGNED"].as_bool(), ez->FALSE, ez->FALSE);
 659
 660                                 if (cell->type == "$shiftx")
 661                                         undef_a_shifted = ez->vec_shift_right(undef_a, b, cell->parameters["\\B_SIGNED"].as_bool(), ez->TRUE, ez->TRUE);
 662
 663                                 int undef_any_b = ez->expression(ezSAT::OpOr, undef_b);
 664                                 std::vector<int> undef_all_y_bits(undef_y.size(), undef_any_b);
 665                                 ez->assume(ez->vec_eq(ez->vec_or(undef_a_shifted, undef_all_y_bits), undef_y));
 666                                 undefGating(y, yy, undef_y);
 667                         }
 668                         return true;
 669                 }
 670
 671                 if (cell->type == "$mul")
 672                 {
 673                         std::vector<int> a = importDefSigSpec(cell->getPort("\\A"), timestep);
 674                         std::vector<int> b = importDefSigSpec(cell->getPort("\\B"), timestep);
 675                         std::vector<int> y = importDefSigSpec(cell->getPort("\\Y"), timestep);
 676                         extendSignalWidth(a, b, y, cell);
 677
 678                         std::vector<int> yy = model_undef ? ez->vec_var(y.size()) : y;
 679
 680                         std::vector<int> tmp(a.size(), ez->FALSE);
 681                         for (int i = 0; i < int(a.size()); i++)
 682                         {
 683                                 std::vector<int> shifted_a(a.size(), ez->FALSE);
 684                                 for (int j = i; j < int(a.size()); j++)
 685                                         shifted_a.at(j) = a.at(j-i);
 686                                 tmp = ez->vec_ite(b.at(i), ez->vec_add(tmp, shifted_a), tmp);
 687                         }
 688                         ez->assume(ez->vec_eq(tmp, yy));
 689
 690                         if (model_undef) {
 691                                 log_assert(arith_undef_handled);
 692                                 std::vector<int> undef_y = importUndefSigSpec(cell->getPort("\\Y"), timestep);
 693                                 undefGating(y, yy, undef_y);
 694                         }
 695                         return true;
 696                 }
 697
 698                 if (cell->type == "$div" || cell->type == "$mod")
 699                 {
 700                         std::vector<int> a = importDefSigSpec(cell->getPort("\\A"), timestep);
 701                         std::vector<int> b = importDefSigSpec(cell->getPort("\\B"), timestep);
 702                         std::vector<int> y = importDefSigSpec(cell->getPort("\\Y"), timestep);
 703                         extendSignalWidth(a, b, y, cell);
 704
 705                         std::vector<int> yy = model_undef ? ez->vec_var(y.size()) : y;
 706
 707                         std::vector<int> a_u, b_u;
 708                         if (cell->parameters["\\A_SIGNED"].as_bool() && cell->parameters["\\B_SIGNED"].as_bool()) {
 709                                 a_u = ez->vec_ite(a.back(), ez->vec_neg(a), a);
 710                                 b_u = ez->vec_ite(b.back(), ez->vec_neg(b), b);
 711                         } else {
 712                                 a_u = a;
 713                                 b_u = b;
 714                         }
 715
 716                         std::vector<int> chain_buf = a_u;
 717                         std::vector<int> y_u(a_u.size(), ez->FALSE);
 718                         for (int i = int(a.size())-1; i >= 0; i--)
 719                         {
 720                                 chain_buf.insert(chain_buf.end(), chain_buf.size(), ez->FALSE);
 721
 722                                 std::vector<int> b_shl(i, ez->FALSE);
 723                                 b_shl.insert(b_shl.end(), b_u.begin(), b_u.end());
 724                                 b_shl.insert(b_shl.end(), chain_buf.size()-b_shl.size(), ez->FALSE);
 725
 726                                 y_u.at(i) = ez->vec_ge_unsigned(chain_buf, b_shl);
 727                                 chain_buf = ez->vec_ite(y_u.at(i), ez->vec_sub(chain_buf, b_shl), chain_buf);
 728
 729                                 chain_buf.erase(chain_buf.begin() + a_u.size(), chain_buf.end());
 730                         }
 731
 732                         std::vector<int> y_tmp = ignore_div_by_zero ? yy : ez->vec_var(y.size());
 733                         if (cell->type == "$div") {
 734                                 if (cell->parameters["\\A_SIGNED"].as_bool() && cell->parameters["\\B_SIGNED"].as_bool())
 735                                         ez->assume(ez->vec_eq(y_tmp, ez->vec_ite(ez->XOR(a.back(), b.back()), ez->vec_neg(y_u), y_u)));
 736                                 else
 737                                         ez->assume(ez->vec_eq(y_tmp, y_u));
 738                         } else {
 739                                 if (cell->parameters["\\A_SIGNED"].as_bool() && cell->parameters["\\B_SIGNED"].as_bool())
 740                                         ez->assume(ez->vec_eq(y_tmp, ez->vec_ite(a.back(), ez->vec_neg(chain_buf), chain_buf)));
 741                                 else
 742                                         ez->assume(ez->vec_eq(y_tmp, chain_buf));
 743                         }
 744
 745                         if (ignore_div_by_zero) {
 746                                 ez->assume(ez->expression(ezSAT::OpOr, b));
 747                         } else {
 748                                 std::vector<int> div_zero_result;
 749                                 if (cell->type == "$div") {
 750                                         if (cell->parameters["\\A_SIGNED"].as_bool() && cell->parameters["\\B_SIGNED"].as_bool()) {
 751                                                 std::vector<int> all_ones(y.size(), ez->TRUE);
 752                                                 std::vector<int> only_first_one(y.size(), ez->FALSE);
 753                                                 only_first_one.at(0) = ez->TRUE;
 754                                                 div_zero_result = ez->vec_ite(a.back(), only_first_one, all_ones);
 755                                         } else {
 756                                                 div_zero_result.insert(div_zero_result.end(), cell->getPort("\\A").size(), ez->TRUE);
 757                                                 div_zero_result.insert(div_zero_result.end(), y.size() - div_zero_result.size(), ez->FALSE);
 758                                         }
 759                                 } else {
 760                                         int copy_a_bits = std::min(cell->getPort("\\A").size(), cell->getPort("\\B").size());
 761                                         div_zero_result.insert(div_zero_result.end(), a.begin(), a.begin() + copy_a_bits);
 762                                         if (cell->parameters["\\A_SIGNED"].as_bool() && cell->parameters["\\B_SIGNED"].as_bool())
 763                                                 div_zero_result.insert(div_zero_result.end(), y.size() - div_zero_result.size(), div_zero_result.back());
 764                                         else
 765                                                 div_zero_result.insert(div_zero_result.end(), y.size() - div_zero_result.size(), ez->FALSE);
 766                                 }
 767                                 ez->assume(ez->vec_eq(yy, ez->vec_ite(ez->expression(ezSAT::OpOr, b), y_tmp, div_zero_result)));
 768                         }
 769
 770                         if (model_undef) {
 771                                 log_assert(arith_undef_handled);
 772                                 std::vector<int> undef_y = importUndefSigSpec(cell->getPort("\\Y"), timestep);
 773                                 undefGating(y, yy, undef_y);
 774                         }
 775                         return true;
 776                 }
 777
 778                 if (cell->type == "$slice")
 779                 {
 780                         RTLIL::SigSpec a = cell->getPort("\\A");
 781                         RTLIL::SigSpec y = cell->getPort("\\Y");
 782                         ez->assume(signals_eq(a.extract(cell->parameters.at("\\OFFSET").as_int(), y.size()), y, timestep));
 783                         return true;
 784                 }
 785
 786                 if (cell->type == "$concat")
 787                 {
 788                         RTLIL::SigSpec a = cell->getPort("\\A");
 789                         RTLIL::SigSpec b = cell->getPort("\\B");
 790                         RTLIL::SigSpec y = cell->getPort("\\Y");
 791
 792                         RTLIL::SigSpec ab = a;
 793                         ab.append(b);
 794
 795                         ez->assume(signals_eq(ab, y, timestep));
 796                         return true;
 797                 }
 798
 799                 if (timestep > 0 && (cell->type == "$dff" || cell->type == "$_DFF_N_" || cell->type == "$_DFF_P_"))
 800                 {
 801                         if (timestep == 1)
 802                         {
 803                                 initial_state.add((*sigmap)(cell->getPort("\\Q")));
 804                         }
 805                         else
 806                         {
 807                                 std::vector<int> d = importDefSigSpec(cell->getPort("\\D"), timestep-1);
 808                                 std::vector<int> q = importDefSigSpec(cell->getPort("\\Q"), timestep);
 809
 810                                 std::vector<int> qq = model_undef ? ez->vec_var(q.size()) : q;
 811                                 ez->assume(ez->vec_eq(d, qq));
 812
 813                                 if (model_undef)
 814                                 {
 815                                         std::vector<int> undef_d = importUndefSigSpec(cell->getPort("\\D"), timestep-1);
 816                                         std::vector<int> undef_q = importUndefSigSpec(cell->getPort("\\Q"), timestep);
 817
 818                                         ez->assume(ez->vec_eq(undef_d, undef_q));
 819                                         undefGating(q, qq, undef_q);
 820                                 }
 821                         }
 822                         return true;
 823                 }
 824
 825                 if (cell->type == "$assert")
 826                 {
 827                         std::string pf = prefix + (timestep == -1 ? "" : stringf("@%d:", timestep));
 828                         asserts_a[pf].append((*sigmap)(cell->getPort("\\A")));
 829                         asserts_en[pf].append((*sigmap)(cell->getPort("\\EN")));
 830                         return true;
 831                 }
 832
 833                 // Unsupported internal cell types: $pow $lut
 834                 // .. and all sequential cells except $dff and $_DFF_[NP]_
 835                 return false;
 836         }
 837 };
 838
 839 #endif
 840