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 #ifdef YOSYS_ENABLE_MINISAT
  28 #  include "libs/ezsat/ezminisat.h"
  29 typedef ezMiniSAT ezDefaultSAT;
  30 #else
  31 #  include "libs/ezsat/ezsat.h"
  32 typedef ezSAT ezDefaultSAT;
  33 #endif
  34
  35 struct SatGen
  36 {
  37         ezSAT *ez;
  38         RTLIL::Design *design;
  39         SigMap *sigmap;
  40         std::string prefix;
  41         SigPool initial_state;
  42
  43         SatGen(ezSAT *ez, RTLIL::Design *design, SigMap *sigmap, std::string prefix = std::string()) :
  44                         ez(ez), design(design), sigmap(sigmap), prefix(prefix)
  45         {
  46         }
  47
  48         void setContext(RTLIL::Design *design, SigMap *sigmap, std::string prefix = std::string())
  49         {
  50                 this->design = design;
  51                 this->sigmap = sigmap;
  52                 this->prefix = prefix;
  53         }
  54
  55         std::vector<int> importSigSpec(RTLIL::SigSpec &sig, int timestep = -1)
  56         {
  57                 assert(timestep < 0 || timestep > 0);
  58                 RTLIL::SigSpec s = sig;
  59                 sigmap->apply(s);
  60                 s.expand();
  61
  62                 std::vector<int> vec;
  63                 vec.reserve(s.chunks.size());
  64
  65                 for (auto &c : s.chunks)
  66                         if (c.wire == NULL) {
  67                                 vec.push_back(c.data.as_bool() ? ez->TRUE : ez->FALSE);
  68                         } else {
  69                                 std::string name = prefix;
  70                                 name += timestep == -1 ? "" : stringf("@%d:", timestep);
  71                                 name += stringf(c.wire->width == 1 ?  "%s" : "%s [%d]", RTLIL::id2cstr(c.wire->name), c.offset);
  72                                 vec.push_back(ez->literal(name));
  73                         }
  74                 return vec;
  75         }
  76
  77         void extendSignalWidth(std::vector<int> &vec_a, std::vector<int> &vec_b, RTLIL::Cell *cell, size_t y_width = 0)
  78         {
  79                 bool is_signed = false;
  80                 if (cell->parameters.count("\\A_SIGNED") > 0 && cell->parameters.count("\\B_SIGNED") > 0)
  81                         is_signed = cell->parameters["\\A_SIGNED"].as_bool() && cell->parameters["\\B_SIGNED"].as_bool();
  82                 while (vec_a.size() < vec_b.size() || vec_a.size() < y_width)
  83                         vec_a.push_back(is_signed && vec_a.size() > 0 ? vec_a.back() : ez->FALSE);
  84                 while (vec_b.size() < vec_a.size() || vec_b.size() < y_width)
  85                         vec_b.push_back(is_signed && vec_b.size() > 0 ? vec_b.back() : ez->FALSE);
  86         }
  87
  88         void extendSignalWidth(std::vector<int> &vec_a, std::vector<int> &vec_b, std::vector<int> &vec_y, RTLIL::Cell *cell)
  89         {
  90                 extendSignalWidth(vec_a, vec_b, cell, vec_y.size());
  91                 while (vec_y.size() < vec_a.size())
  92                         vec_y.push_back(ez->literal());
  93         }
  94
  95         bool importCell(RTLIL::Cell *cell, int timestep = -1)
  96         {
  97                 if (cell->type == "$_AND_" || cell->type == "$_OR_" || cell->type == "$_XOR_" ||
  98                                 cell->type == "$and" || cell->type == "$or" || cell->type == "$xor" || cell->type == "$xnor" ||
  99                                 cell->type == "$add" || cell->type == "$sub") {
 100                         std::vector<int> a = importSigSpec(cell->connections.at("\\A"), timestep);
 101                         std::vector<int> b = importSigSpec(cell->connections.at("\\B"), timestep);
 102                         std::vector<int> y = importSigSpec(cell->connections.at("\\Y"), timestep);
 103                         extendSignalWidth(a, b, y, cell);
 104                         if (cell->type == "$and" || cell->type == "$_AND_")
 105                                 ez->assume(ez->vec_eq(ez->vec_and(a, b), y));
 106                         if (cell->type == "$or" || cell->type == "$_OR_")
 107                                 ez->assume(ez->vec_eq(ez->vec_or(a, b), y));
 108                         if (cell->type == "$xor" || cell->type == "$_XOR_")
 109                                 ez->assume(ez->vec_eq(ez->vec_xor(a, b), y));
 110                         if (cell->type == "$xnor")
 111                                 ez->assume(ez->vec_eq(ez->vec_not(ez->vec_xor(a, b)), y));
 112                         if (cell->type == "$add")
 113                                 ez->assume(ez->vec_eq(ez->vec_add(a, b), y));
 114                         if (cell->type == "$sub")
 115                                 ez->assume(ez->vec_eq(ez->vec_sub(a, b), y));
 116                         return true;
 117                 }
 118
 119                 if (cell->type == "$_INV_" || cell->type == "$not") {
 120                         std::vector<int> a = importSigSpec(cell->connections.at("\\A"), timestep);
 121                         std::vector<int> y = importSigSpec(cell->connections.at("\\Y"), timestep);
 122                         ez->assume(ez->vec_eq(ez->vec_not(a), y));
 123                         return true;
 124                 }
 125
 126                 if (cell->type == "$_MUX_" || cell->type == "$mux") {
 127                         std::vector<int> a = importSigSpec(cell->connections.at("\\A"), timestep);
 128                         std::vector<int> b = importSigSpec(cell->connections.at("\\B"), timestep);
 129                         std::vector<int> s = importSigSpec(cell->connections.at("\\S"), timestep);
 130                         std::vector<int> y = importSigSpec(cell->connections.at("\\Y"), timestep);
 131                         ez->assume(ez->vec_eq(ez->vec_ite(s.at(0), b, a), y));
 132                         return true;
 133                 }
 134
 135                 if (cell->type == "$pmux" || cell->type == "$safe_pmux") {
 136                         std::vector<int> a = importSigSpec(cell->connections.at("\\A"), timestep);
 137                         std::vector<int> b = importSigSpec(cell->connections.at("\\B"), timestep);
 138                         std::vector<int> s = importSigSpec(cell->connections.at("\\S"), timestep);
 139                         std::vector<int> y = importSigSpec(cell->connections.at("\\Y"), timestep);
 140                         std::vector<int> tmp = a;
 141                         for (size_t i = 0; i < s.size(); i++) {
 142                                 std::vector<int> part_of_b(b.begin()+i*a.size(), b.begin()+(i+1)*a.size());
 143                                 tmp = ez->vec_ite(s.at(i), part_of_b, tmp);
 144                         }
 145                         if (cell->type == "$safe_pmux")
 146                                 tmp = ez->vec_ite(ez->onehot(s, true), tmp, a);
 147                         ez->assume(ez->vec_eq(tmp, y));
 148                         return true;
 149                 }
 150
 151                 if (cell->type == "$pos" || cell->type == "$neg") {
 152                         std::vector<int> a = importSigSpec(cell->connections.at("\\A"), timestep);
 153                         std::vector<int> y = importSigSpec(cell->connections.at("\\Y"), timestep);
 154                         if (cell->type == "$pos") {
 155                                 ez->assume(ez->vec_eq(a, y));
 156                         } else {
 157                                 std::vector<int> zero(a.size(), ez->FALSE);
 158                                 ez->assume(ez->vec_eq(ez->vec_sub(zero, a), y));
 159                         }
 160                         return true;
 161                 }
 162
 163                 if (cell->type == "$reduce_and" || cell->type == "$reduce_or" || cell->type == "$reduce_xor" ||
 164                                 cell->type == "$reduce_xnor" || cell->type == "$reduce_bool" || cell->type == "$logic_not") {
 165                         std::vector<int> a = importSigSpec(cell->connections.at("\\A"), timestep);
 166                         std::vector<int> y = importSigSpec(cell->connections.at("\\Y"), timestep);
 167                         if (cell->type == "$reduce_and")
 168                                 ez->SET(ez->expression(ez->OpAnd, a), y.at(0));
 169                         if (cell->type == "$reduce_or" || cell->type == "$reduce_bool")
 170                                 ez->SET(ez->expression(ez->OpOr, a), y.at(0));
 171                         if (cell->type == "$reduce_xor")
 172                                 ez->SET(ez->expression(ez->OpXor, a), y.at(0));
 173                         if (cell->type == "$reduce_xnor")
 174                                 ez->SET(ez->NOT(ez->expression(ez->OpXor, a)), y.at(0));
 175                         if (cell->type == "$logic_not")
 176                                 ez->SET(ez->NOT(ez->expression(ez->OpOr, a)), y.at(0));
 177                         for (size_t i = 1; i < y.size(); i++)
 178                                 ez->SET(0, y.at(0));
 179                         return true;
 180                 }
 181
 182                 if (cell->type == "$logic_and" || cell->type == "$logic_or") {
 183                         int a = ez->expression(ez->OpOr, importSigSpec(cell->connections.at("\\A"), timestep));
 184                         int b = ez->expression(ez->OpOr, importSigSpec(cell->connections.at("\\B"), timestep));
 185                         std::vector<int> y = importSigSpec(cell->connections.at("\\Y"), timestep);
 186                         if (cell->type == "$logic_and")
 187                                 ez->SET(ez->expression(ez->OpAnd, a, b), y.at(0));
 188                         else
 189                                 ez->SET(ez->expression(ez->OpOr, a, b), y.at(0));
 190                         for (size_t i = 1; i < y.size(); i++)
 191                                 ez->SET(0, y.at(0));
 192                         return true;
 193                 }
 194
 195                 if (cell->type == "$lt" || cell->type == "$le" || cell->type == "$eq" || cell->type == "$ne" || cell->type == "$ge" || cell->type == "$gt") {
 196                         bool is_signed = cell->parameters["\\A_SIGNED"].as_bool() && cell->parameters["\\B_SIGNED"].as_bool();
 197                         std::vector<int> a = importSigSpec(cell->connections.at("\\A"), timestep);
 198                         std::vector<int> b = importSigSpec(cell->connections.at("\\B"), timestep);
 199                         std::vector<int> y = importSigSpec(cell->connections.at("\\Y"), timestep);
 200                         extendSignalWidth(a, b, cell);
 201                         if (cell->type == "$lt")
 202                                 ez->SET(is_signed ? ez->vec_lt_signed(a, b) : ez->vec_lt_unsigned(a, b), y.at(0));
 203                         if (cell->type == "$le")
 204                                 ez->SET(is_signed ? ez->vec_le_signed(a, b) : ez->vec_le_unsigned(a, b), y.at(0));
 205                         if (cell->type == "$eq")
 206                                 ez->SET(ez->vec_eq(a, b), y.at(0));
 207                         if (cell->type == "$ne")
 208                                 ez->SET(ez->vec_ne(a, b), y.at(0));
 209                         if (cell->type == "$ge")
 210                                 ez->SET(is_signed ? ez->vec_ge_signed(a, b) : ez->vec_ge_unsigned(a, b), y.at(0));
 211                         if (cell->type == "$gt")
 212                                 ez->SET(is_signed ? ez->vec_gt_signed(a, b) : ez->vec_gt_unsigned(a, b), y.at(0));
 213                         for (size_t i = 1; i < y.size(); i++)
 214                                 ez->SET(0, y.at(0));
 215                         return true;
 216                 }
 217
 218                 if (cell->type == "$shl" || cell->type == "$shr" || cell->type == "$sshl" || cell->type == "$sshr") {
 219                         std::vector<int> a = importSigSpec(cell->connections.at("\\A"), timestep);
 220                         std::vector<int> b = importSigSpec(cell->connections.at("\\B"), timestep);
 221                         std::vector<int> y = importSigSpec(cell->connections.at("\\Y"), timestep);
 222                         char shift_left = cell->type == "$shl" || cell->type == "$sshl";
 223                         bool sign_extend = cell->type == "$sshr" && cell->parameters["\\A_SIGNED"].as_bool();
 224                         while (y.size() < a.size())
 225                                 y.push_back(ez->literal());
 226                         while (y.size() > a.size())
 227                                 a.push_back(cell->parameters["\\A_SIGNED"].as_bool() ? a.back() : ez->FALSE);
 228                         std::vector<int> tmp = a;
 229                         for (size_t i = 0; i < b.size(); i++)
 230                         {
 231                                 std::vector<int> tmp_shifted(tmp.size());
 232                                 for (size_t j = 0; j < tmp.size(); j++) {
 233                                         int idx = j + (1 << i) * (shift_left ? -1 : +1);
 234                                         tmp_shifted.at(j) = (0 <= idx && idx < int(tmp.size())) ? tmp.at(idx) : sign_extend ? tmp.back() : ez->FALSE;
 235                                 }
 236                                 tmp = ez->vec_ite(b.at(i), tmp_shifted, tmp);
 237                         }
 238                         ez->assume(ez->vec_eq(tmp, y));
 239                         return true;
 240                 }
 241
 242                 if (cell->type == "$mul") {
 243                         std::vector<int> a = importSigSpec(cell->connections.at("\\A"), timestep);
 244                         std::vector<int> b = importSigSpec(cell->connections.at("\\B"), timestep);
 245                         std::vector<int> y = importSigSpec(cell->connections.at("\\Y"), timestep);
 246                         extendSignalWidth(a, b, y, cell);
 247                         std::vector<int> tmp(a.size(), ez->FALSE);
 248                         for (int i = 0; i < int(a.size()); i++)
 249                         {
 250                                 std::vector<int> shifted_a(a.size(), ez->FALSE);
 251                                 for (int j = i; j < int(a.size()); j++)
 252                                         shifted_a.at(j) = a.at(j-i);
 253                                 tmp = ez->vec_ite(b.at(i), ez->vec_add(tmp, shifted_a), tmp);
 254                         }
 255                         ez->assume(ez->vec_eq(tmp, y));
 256                         return true;
 257                 }
 258
 259                 if (timestep > 0 && (cell->type == "$dff" || cell->type == "$_DFF_N_" || cell->type == "$_DFF_P_")) {
 260                         if (timestep == 1) {
 261                                 initial_state.add((*sigmap)(cell->connections.at("\\Q")));
 262                         } else {
 263                                 std::vector<int> d = importSigSpec(cell->connections.at("\\D"), timestep-1);
 264                                 std::vector<int> q = importSigSpec(cell->connections.at("\\Q"), timestep);
 265                                 ez->assume(ez->vec_eq(d, q));
 266                         }
 267                         return true;
 268                 }
 269
 270                 // Unsupported internal cell types: $div $mod $pow
 271                 // .. and all sequential cells except $dff and $_DFF_[NP]_
 272                 return false;
 273         }
 274 };
 275
 276 #endif
 277