passes/opt/opt_const.cc

   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 #include "opt_status.h"
  21 #include "kernel/register.h"
  22 #include "kernel/sigtools.h"
  23 #include "kernel/celltypes.h"
  24 #include "kernel/log.h"
  25 #include <stdlib.h>
  26 #include <assert.h>
  27 #include <stdio.h>
  28 #include <algorithm>
  29
  30 static bool did_something;
  31
  32 static void replace_undriven(RTLIL::Design *design, RTLIL::Module *module)
  33 {
  34         CellTypes ct(design);
  35         SigMap sigmap(module);
  36         SigPool driven_signals;
  37         SigPool used_signals;
  38         SigPool all_signals;
  39
  40         for (auto &it : module->cells)
  41         for (auto &conn : it.second->connections) {
  42                 if (!ct.cell_known(it.second->type) || ct.cell_output(it.second->type, conn.first))
  43                         driven_signals.add(sigmap(conn.second));
  44                 if (!ct.cell_known(it.second->type) || ct.cell_input(it.second->type, conn.first))
  45                         used_signals.add(sigmap(conn.second));
  46         }
  47
  48         for (auto &it : module->wires) {
  49                 if (it.second->port_input)
  50                         driven_signals.add(sigmap(it.second));
  51                 if (it.second->port_output)
  52                         used_signals.add(sigmap(it.second));
  53                 all_signals.add(sigmap(it.second));
  54         }
  55
  56         all_signals.del(driven_signals);
  57         RTLIL::SigSpec undriven_signals = all_signals.export_all();
  58
  59         for (auto &c : undriven_signals.chunks())
  60         {
  61                 RTLIL::SigSpec sig = c;
  62
  63                 if (c.wire->name[0] == '$')
  64                         sig = used_signals.extract(sig);
  65                 if (sig.size() == 0)
  66                         continue;
  67
  68                 log("Setting undriven signal in %s to undef: %s\n", RTLIL::id2cstr(module->name), log_signal(c));
  69                 module->connections.push_back(RTLIL::SigSig(c, RTLIL::SigSpec(RTLIL::State::Sx, c.width)));
  70                 OPT_DID_SOMETHING = true;
  71         }
  72 }
  73
  74 static void replace_cell(RTLIL::Module *module, RTLIL::Cell *cell, std::string info, std::string out_port, RTLIL::SigSpec out_val)
  75 {
  76         RTLIL::SigSpec Y = cell->connections[out_port];
  77         out_val.extend_u0(Y.size(), false);
  78
  79         log("Replacing %s cell `%s' (%s) in module `%s' with constant driver `%s = %s'.\n",
  80                         cell->type.c_str(), cell->name.c_str(), info.c_str(),
  81                         module->name.c_str(), log_signal(Y), log_signal(out_val));
  82         // ILANG_BACKEND::dump_cell(stderr, "--> ", cell);
  83         module->connections.push_back(RTLIL::SigSig(Y, out_val));
  84         module->cells.erase(cell->name);
  85         delete cell;
  86         OPT_DID_SOMETHING = true;
  87         did_something = true;
  88 }
  89
  90 static bool group_cell_inputs(RTLIL::Module *module, RTLIL::Cell *cell, bool commutative, bool extend_u0, SigMap &sigmap)
  91 {
  92         std::string b_name = cell->connections.count("\\B") ? "\\B" : "\\A";
  93
  94         bool a_signed = cell->parameters.at("\\A_SIGNED").as_bool();
  95         bool b_signed = cell->parameters.at(b_name + "_SIGNED").as_bool();
  96
  97         RTLIL::SigSpec sig_a = sigmap(cell->connections.at("\\A"));
  98         RTLIL::SigSpec sig_b = sigmap(cell->connections.at(b_name));
  99         RTLIL::SigSpec sig_y = sigmap(cell->connections.at("\\Y"));
 100
 101         if (extend_u0) {
 102                 sig_a.extend_u0(sig_y.size(), a_signed);
 103                 sig_b.extend_u0(sig_y.size(), b_signed);
 104         } else {
 105                 sig_a.extend(sig_y.size(), a_signed);
 106                 sig_b.extend(sig_y.size(), b_signed);
 107         }
 108
 109         std::vector<RTLIL::SigBit> bits_a = sig_a, bits_b = sig_b, bits_y = sig_y;
 110
 111         enum { GRP_DYN, GRP_CONST_A, GRP_CONST_B, GRP_CONST_AB, GRP_N };
 112         std::map<std::pair<RTLIL::SigBit, RTLIL::SigBit>, std::set<RTLIL::SigBit>> grouped_bits[GRP_N];
 113
 114         for (int i = 0; i < SIZE(bits_y); i++)
 115         {
 116                 int group_idx = GRP_DYN;
 117                 RTLIL::SigBit bit_a = bits_a[i], bit_b = bits_b[i];
 118
 119                 if (cell->type == "$or" && (bit_a == RTLIL::State::S1 || bit_b == RTLIL::State::S1))
 120                         bit_a = bit_b = RTLIL::State::S1;
 121
 122                 if (cell->type == "$and" && (bit_a == RTLIL::State::S0 || bit_b == RTLIL::State::S0))
 123                         bit_a = bit_b = RTLIL::State::S0;
 124
 125                 if (bit_a.wire == NULL && bit_b.wire == NULL)
 126                         group_idx = GRP_CONST_AB;
 127                 else if (bit_a.wire == NULL)
 128                         group_idx = GRP_CONST_A;
 129                 else if (bit_b.wire == NULL && commutative)
 130                         group_idx = GRP_CONST_A, std::swap(bit_a, bit_b);
 131                 else if (bit_b.wire == NULL)
 132                         group_idx = GRP_CONST_B;
 133
 134                 grouped_bits[group_idx][std::pair<RTLIL::SigBit, RTLIL::SigBit>(bit_a, bit_b)].insert(bits_y[i]);
 135         }
 136
 137         for (int i = 0; i < GRP_N; i++)
 138                 if (SIZE(grouped_bits[i]) == SIZE(bits_y))
 139                         return false;
 140
 141         log("Replacing %s cell `%s' in module `%s' with cells using grouped bits:\n",
 142                         log_id(cell->type), log_id(cell), log_id(module));
 143
 144         for (int i = 0; i < GRP_N; i++)
 145         {
 146                 if (grouped_bits[i].empty())
 147                         continue;
 148
 149                 RTLIL::Wire *new_y = module->addWire(NEW_ID, SIZE(grouped_bits[i]));
 150                 RTLIL::SigSpec new_a, new_b;
 151                 RTLIL::SigSig new_conn;
 152
 153                 for (auto &it : grouped_bits[i]) {
 154                         for (auto &bit : it.second) {
 155                                 new_conn.first.append_bit(bit);
 156                                 new_conn.second.append_bit(RTLIL::SigBit(new_y, new_a.size()));
 157                         }
 158                         new_a.append_bit(it.first.first);
 159                         new_b.append_bit(it.first.second);
 160                 }
 161
 162                 RTLIL::Cell *c = module->addCell(NEW_ID, cell->type);
 163
 164                 c->connections["\\A"] = new_a;
 165                 c->parameters["\\A_WIDTH"] = new_a.size();
 166                 c->parameters["\\A_SIGNED"] = false;
 167
 168                 if (b_name == "\\B") {
 169                         c->connections["\\B"] = new_b;
 170                         c->parameters["\\B_WIDTH"] = new_b.size();
 171                         c->parameters["\\B_SIGNED"] = false;
 172                 }
 173
 174                 c->connections["\\Y"] = new_y;
 175                 c->parameters["\\Y_WIDTH"] = new_y->width;
 176                 c->check();
 177
 178                 module->connections.push_back(new_conn);
 179
 180                 log("  New cell `%s': A=%s", log_id(c), log_signal(new_a));
 181                 if (b_name == "\\B")
 182                         log(", B=%s", log_signal(new_b));
 183                 log("\n");
 184         }
 185
 186         module->remove(cell);
 187         OPT_DID_SOMETHING = true;
 188         did_something = true;
 189         return true;
 190 }
 191
 192 static void replace_const_cells(RTLIL::Design *design, RTLIL::Module *module, bool consume_x, bool mux_undef, bool mux_bool, bool do_fine, bool keepdc)
 193 {
 194         if (!design->selected(module))
 195                 return;
 196
 197         SigMap assign_map(module);
 198         std::map<RTLIL::SigSpec, RTLIL::SigSpec> invert_map;
 199
 200         std::vector<RTLIL::Cell*> cells;
 201         cells.reserve(module->cells.size());
 202         for (auto &cell_it : module->cells)
 203                 if (design->selected(module, cell_it.second)) {
 204                         if ((cell_it.second->type == "$_INV_" || cell_it.second->type == "$not" || cell_it.second->type == "$logic_not") &&
 205                                         cell_it.second->connections["\\A"].size() == 1 && cell_it.second->connections["\\Y"].size() == 1)
 206                                 invert_map[assign_map(cell_it.second->connections["\\Y"])] = assign_map(cell_it.second->connections["\\A"]);
 207                         cells.push_back(cell_it.second);
 208                 }
 209
 210         for (auto cell : cells)
 211         {
 212 #define ACTION_DO(_p_, _s_) do { replace_cell(module, cell, input.as_string(), _p_, _s_); goto next_cell; } while (0)
 213 #define ACTION_DO_Y(_v_) ACTION_DO("\\Y", RTLIL::SigSpec(RTLIL::State::S ## _v_))
 214
 215                 if (do_fine)
 216                 {
 217                         if (cell->type == "$not" || cell->type == "$pos" || cell->type == "$bu0" ||
 218                                         cell->type == "$and" || cell->type == "$or" || cell->type == "$xor" || cell->type == "$xnor")
 219                                 if (group_cell_inputs(module, cell, true, cell->type != "$pos", assign_map))
 220                                         goto next_cell;
 221
 222                         if (cell->type == "$reduce_and")
 223                         {
 224                                 RTLIL::SigSpec sig_a = assign_map(cell->connections.at("\\A"));
 225
 226                                 RTLIL::State new_a = RTLIL::State::S1;
 227                                 for (auto &bit : sig_a.to_sigbit_vector())
 228                                         if (bit == RTLIL::State::Sx) {
 229                                                 if (new_a == RTLIL::State::S1)
 230                                                         new_a = RTLIL::State::Sx;
 231                                         } else if (bit == RTLIL::State::S0) {
 232                                                 new_a = RTLIL::State::S0;
 233                                                 break;
 234                                         } else if (bit.wire != NULL) {
 235                                                 new_a = RTLIL::State::Sm;
 236                                         }
 237
 238                                 if (new_a != RTLIL::State::Sm && RTLIL::SigSpec(new_a) != sig_a) {
 239                                         log("Replacing port A of %s cell `%s' in module `%s' with constant driver: %s -> %s\n",
 240                                                         cell->type.c_str(), cell->name.c_str(), module->name.c_str(), log_signal(sig_a), log_signal(new_a));
 241                                         cell->connections.at("\\A") = sig_a = new_a;
 242                                         cell->parameters.at("\\A_WIDTH") = 1;
 243                                         OPT_DID_SOMETHING = true;
 244                                         did_something = true;
 245                                 }
 246                         }
 247
 248                         if (cell->type == "$logic_not" || cell->type == "$logic_and" || cell->type == "$logic_or" || cell->type == "$reduce_or" || cell->type == "$reduce_bool")
 249                         {
 250                                 RTLIL::SigSpec sig_a = assign_map(cell->connections.at("\\A"));
 251
 252                                 RTLIL::State new_a = RTLIL::State::S0;
 253                                 for (auto &bit : sig_a.to_sigbit_vector())
 254                                         if (bit == RTLIL::State::Sx) {
 255                                                 if (new_a == RTLIL::State::S0)
 256                                                         new_a = RTLIL::State::Sx;
 257                                         } else if (bit == RTLIL::State::S1) {
 258                                                 new_a = RTLIL::State::S1;
 259                                                 break;
 260                                         } else if (bit.wire != NULL) {
 261                                                 new_a = RTLIL::State::Sm;
 262                                         }
 263
 264                                 if (new_a != RTLIL::State::Sm && RTLIL::SigSpec(new_a) != sig_a) {
 265                                         log("Replacing port A of %s cell `%s' in module `%s' with constant driver: %s -> %s\n",
 266                                                         cell->type.c_str(), cell->name.c_str(), module->name.c_str(), log_signal(sig_a), log_signal(new_a));
 267                                         cell->connections.at("\\A") = sig_a = new_a;
 268                                         cell->parameters.at("\\A_WIDTH") = 1;
 269                                         OPT_DID_SOMETHING = true;
 270                                         did_something = true;
 271                                 }
 272                         }
 273
 274                         if (cell->type == "$logic_and" || cell->type == "$logic_or")
 275                         {
 276                                 RTLIL::SigSpec sig_b = assign_map(cell->connections.at("\\B"));
 277
 278                                 RTLIL::State new_b = RTLIL::State::S0;
 279                                 for (auto &bit : sig_b.to_sigbit_vector())
 280                                         if (bit == RTLIL::State::Sx) {
 281                                                 if (new_b == RTLIL::State::S0)
 282                                                         new_b = RTLIL::State::Sx;
 283                                         } else if (bit == RTLIL::State::S1) {
 284                                                 new_b = RTLIL::State::S1;
 285                                                 break;
 286                                         } else if (bit.wire != NULL) {
 287                                                 new_b = RTLIL::State::Sm;
 288                                         }
 289
 290                                 if (new_b != RTLIL::State::Sm && RTLIL::SigSpec(new_b) != sig_b) {
 291                                         log("Replacing port B of %s cell `%s' in module `%s' with constant driver: %s -> %s\n",
 292                                                         cell->type.c_str(), cell->name.c_str(), module->name.c_str(), log_signal(sig_b), log_signal(new_b));
 293                                         cell->connections.at("\\B") = sig_b = new_b;
 294                                         cell->parameters.at("\\B_WIDTH") = 1;
 295                                         OPT_DID_SOMETHING = true;
 296                                         did_something = true;
 297                                 }
 298                         }
 299                 }
 300
 301                 if (cell->type == "$logic_or" && (assign_map(cell->connections.at("\\A")) == RTLIL::State::S1 || assign_map(cell->connections.at("\\B")) == RTLIL::State::S1)) {
 302                         replace_cell(module, cell, "one high", "\\Y", RTLIL::State::S1);
 303                         goto next_cell;
 304                 }
 305
 306                 if (cell->type == "$logic_and" && (assign_map(cell->connections.at("\\A")) == RTLIL::State::S0 || assign_map(cell->connections.at("\\B")) == RTLIL::State::S0)) {
 307                         replace_cell(module, cell, "one low", "\\Y", RTLIL::State::S0);
 308                         goto next_cell;
 309                 }
 310
 311                 if (cell->type == "$reduce_xor" || cell->type == "$reduce_xnor" ||
 312                                 cell->type == "$shl" || cell->type == "$shr" || cell->type == "$sshl" || cell->type == "$sshr" ||
 313                                 cell->type == "$lt" || cell->type == "$le" || cell->type == "$ge" || cell->type == "$gt" ||
 314                                 cell->type == "$neg" || cell->type == "$add" || cell->type == "$sub" ||
 315                                 cell->type == "$mul" || cell->type == "$div" || cell->type == "$mod" || cell->type == "$pow")
 316                 {
 317                         RTLIL::SigSpec sig_a = assign_map(cell->connections.at("\\A"));
 318                         RTLIL::SigSpec sig_b = cell->connections.count("\\B") ? assign_map(cell->connections.at("\\B")) : RTLIL::SigSpec();
 319
 320                         if (cell->type == "$shl" || cell->type == "$shr" || cell->type == "$sshl" || cell->type == "$sshr")
 321                                 sig_a = RTLIL::SigSpec();
 322
 323                         for (auto &bit : sig_a.to_sigbit_vector())
 324                                 if (bit == RTLIL::State::Sx)
 325                                         goto found_the_x_bit;
 326
 327                         for (auto &bit : sig_b.to_sigbit_vector())
 328                                 if (bit == RTLIL::State::Sx)
 329                                         goto found_the_x_bit;
 330
 331                         if (0) {
 332                 found_the_x_bit:
 333                                 if (cell->type == "$reduce_xor" || cell->type == "$reduce_xnor" ||
 334                                                 cell->type == "$lt" || cell->type == "$le" || cell->type == "$ge" || cell->type == "$gt")
 335                                         replace_cell(module, cell, "x-bit in input", "\\Y", RTLIL::State::Sx);
 336                                 else
 337                                         replace_cell(module, cell, "x-bit in input", "\\Y", RTLIL::SigSpec(RTLIL::State::Sx, cell->connections.at("\\Y").size()));
 338                                 goto next_cell;
 339                         }
 340                 }
 341
 342                 if ((cell->type == "$_INV_" || cell->type == "$not" || cell->type == "$logic_not") && cell->connections["\\Y"].size() == 1 &&
 343                                 invert_map.count(assign_map(cell->connections["\\A"])) != 0) {
 344                         replace_cell(module, cell, "double_invert", "\\Y", invert_map.at(assign_map(cell->connections["\\A"])));
 345                         goto next_cell;
 346                 }
 347
 348                 if ((cell->type == "$_MUX_" || cell->type == "$mux") && invert_map.count(assign_map(cell->connections["\\S"])) != 0) {
 349                         RTLIL::SigSpec tmp = cell->connections["\\A"];
 350                         cell->connections["\\A"] = cell->connections["\\B"];
 351                         cell->connections["\\B"] = tmp;
 352                         cell->connections["\\S"] = invert_map.at(assign_map(cell->connections["\\S"]));
 353                         OPT_DID_SOMETHING = true;
 354                         did_something = true;
 355                         goto next_cell;
 356                 }
 357
 358                 if (cell->type == "$_INV_") {
 359                         RTLIL::SigSpec input = cell->connections["\\A"];
 360                         assign_map.apply(input);
 361                         if (input.match("1")) ACTION_DO_Y(0);
 362                         if (input.match("0")) ACTION_DO_Y(1);
 363                         if (input.match("*")) ACTION_DO_Y(x);
 364                 }
 365
 366                 if (cell->type == "$_AND_") {
 367                         RTLIL::SigSpec input;
 368                         input.append(cell->connections["\\B"]);
 369                         input.append(cell->connections["\\A"]);
 370                         assign_map.apply(input);
 371                         if (input.match(" 0")) ACTION_DO_Y(0);
 372                         if (input.match("0 ")) ACTION_DO_Y(0);
 373                         if (input.match("11")) ACTION_DO_Y(1);
 374                         if (input.match("**")) ACTION_DO_Y(x);
 375                         if (input.match("1*")) ACTION_DO_Y(x);
 376                         if (input.match("*1")) ACTION_DO_Y(x);
 377                         if (consume_x) {
 378                                 if (input.match(" *")) ACTION_DO_Y(0);
 379                                 if (input.match("* ")) ACTION_DO_Y(0);
 380                         }
 381                         if (input.match(" 1")) ACTION_DO("\\Y", input.extract(1, 1));
 382                         if (input.match("1 ")) ACTION_DO("\\Y", input.extract(0, 1));
 383                 }
 384
 385                 if (cell->type == "$_OR_") {
 386                         RTLIL::SigSpec input;
 387                         input.append(cell->connections["\\B"]);
 388                         input.append(cell->connections["\\A"]);
 389                         assign_map.apply(input);
 390                         if (input.match(" 1")) ACTION_DO_Y(1);
 391                         if (input.match("1 ")) ACTION_DO_Y(1);
 392                         if (input.match("00")) ACTION_DO_Y(0);
 393                         if (input.match("**")) ACTION_DO_Y(x);
 394                         if (input.match("0*")) ACTION_DO_Y(x);
 395                         if (input.match("*0")) ACTION_DO_Y(x);
 396                         if (consume_x) {
 397                                 if (input.match(" *")) ACTION_DO_Y(1);
 398                                 if (input.match("* ")) ACTION_DO_Y(1);
 399                         }
 400                         if (input.match(" 0")) ACTION_DO("\\Y", input.extract(1, 1));
 401                         if (input.match("0 ")) ACTION_DO("\\Y", input.extract(0, 1));
 402                 }
 403
 404                 if (cell->type == "$_XOR_") {
 405                         RTLIL::SigSpec input;
 406                         input.append(cell->connections["\\B"]);
 407                         input.append(cell->connections["\\A"]);
 408                         assign_map.apply(input);
 409                         if (input.match("00")) ACTION_DO_Y(0);
 410                         if (input.match("01")) ACTION_DO_Y(1);
 411                         if (input.match("10")) ACTION_DO_Y(1);
 412                         if (input.match("11")) ACTION_DO_Y(0);
 413                         if (input.match(" *")) ACTION_DO_Y(x);
 414                         if (input.match("* ")) ACTION_DO_Y(x);
 415                         if (input.match(" 0")) ACTION_DO("\\Y", input.extract(1, 1));
 416                         if (input.match("0 ")) ACTION_DO("\\Y", input.extract(0, 1));
 417                 }
 418
 419                 if (cell->type == "$_MUX_") {
 420                         RTLIL::SigSpec input;
 421                         input.append(cell->connections["\\S"]);
 422                         input.append(cell->connections["\\B"]);
 423                         input.append(cell->connections["\\A"]);
 424                         assign_map.apply(input);
 425                         if (input.extract(2, 1) == input.extract(1, 1))
 426                                 ACTION_DO("\\Y", input.extract(2, 1));
 427                         if (input.match("  0")) ACTION_DO("\\Y", input.extract(2, 1));
 428                         if (input.match("  1")) ACTION_DO("\\Y", input.extract(1, 1));
 429                         if (input.match("01 ")) ACTION_DO("\\Y", input.extract(0, 1));
 430                         if (input.match("10 ")) {
 431                                 cell->type = "$_INV_";
 432                                 cell->connections["\\A"] = input.extract(0, 1);
 433                                 cell->connections.erase("\\B");
 434                                 cell->connections.erase("\\S");
 435                                 goto next_cell;
 436                         }
 437                         if (input.match("11 ")) ACTION_DO_Y(1);
 438                         if (input.match("00 ")) ACTION_DO_Y(0);
 439                         if (input.match("** ")) ACTION_DO_Y(x);
 440                         if (input.match("01*")) ACTION_DO_Y(x);
 441                         if (input.match("10*")) ACTION_DO_Y(x);
 442                         if (mux_undef) {
 443                                 if (input.match("*  ")) ACTION_DO("\\Y", input.extract(1, 1));
 444                                 if (input.match(" * ")) ACTION_DO("\\Y", input.extract(2, 1));
 445                                 if (input.match("  *")) ACTION_DO("\\Y", input.extract(2, 1));
 446                         }
 447                 }
 448
 449                 if (cell->type == "$eq" || cell->type == "$ne" || cell->type == "$eqx" || cell->type == "$nex")
 450                 {
 451                         RTLIL::SigSpec a = cell->connections["\\A"];
 452                         RTLIL::SigSpec b = cell->connections["\\B"];
 453
 454                         if (cell->parameters["\\A_WIDTH"].as_int() != cell->parameters["\\B_WIDTH"].as_int()) {
 455                                 int width = std::max(cell->parameters["\\A_WIDTH"].as_int(), cell->parameters["\\B_WIDTH"].as_int());
 456                                 a.extend_u0(width, cell->parameters["\\A_SIGNED"].as_bool() && cell->parameters["\\B_SIGNED"].as_bool());
 457                                 b.extend_u0(width, cell->parameters["\\A_SIGNED"].as_bool() && cell->parameters["\\B_SIGNED"].as_bool());
 458                         }
 459
 460                         RTLIL::SigSpec new_a, new_b;
 461                         a.expand(), b.expand();
 462
 463                         assert(a.chunks().size() == b.chunks().size());
 464                         for (size_t i = 0; i < a.chunks().size(); i++) {
 465                                 if (a.chunks()[i].wire == NULL && b.chunks()[i].wire == NULL && a.chunks()[i].data.bits[0] != b.chunks()[i].data.bits[0] &&
 466                                                 a.chunks()[i].data.bits[0] <= RTLIL::State::S1 && b.chunks()[i].data.bits[0] <= RTLIL::State::S1) {
 467                                         RTLIL::SigSpec new_y = RTLIL::SigSpec((cell->type == "$eq" || cell->type == "$eqx") ?  RTLIL::State::S0 : RTLIL::State::S1);
 468                                         new_y.extend(cell->parameters["\\Y_WIDTH"].as_int(), false);
 469                                         replace_cell(module, cell, "empty", "\\Y", new_y);
 470                                         goto next_cell;
 471                                 }
 472                                 if (a.chunks()[i] == b.chunks()[i])
 473                                         continue;
 474                                 new_a.append(a.chunks()[i]);
 475                                 new_b.append(b.chunks()[i]);
 476                         }
 477
 478                         if (new_a.size() == 0) {
 479                                 RTLIL::SigSpec new_y = RTLIL::SigSpec((cell->type == "$eq" || cell->type == "$eqx") ?  RTLIL::State::S1 : RTLIL::State::S0);
 480                                 new_y.extend(cell->parameters["\\Y_WIDTH"].as_int(), false);
 481                                 replace_cell(module, cell, "empty", "\\Y", new_y);
 482                                 goto next_cell;
 483                         }
 484
 485                         if (new_a.size() < a.size() || new_b.size() < b.size()) {
 486                                 new_a.optimize();
 487                                 new_b.optimize();
 488                                 cell->connections["\\A"] = new_a;
 489                                 cell->connections["\\B"] = new_b;
 490                                 cell->parameters["\\A_WIDTH"] = new_a.size();
 491                                 cell->parameters["\\B_WIDTH"] = new_b.size();
 492                         }
 493                 }
 494
 495                 if ((cell->type == "$eq" || cell->type == "$ne") && cell->parameters["\\Y_WIDTH"].as_int() == 1 &&
 496                                 cell->parameters["\\A_WIDTH"].as_int() == 1 && cell->parameters["\\B_WIDTH"].as_int() == 1)
 497                 {
 498                         RTLIL::SigSpec a = assign_map(cell->connections["\\A"]);
 499                         RTLIL::SigSpec b = assign_map(cell->connections["\\B"]);
 500
 501                         if (a.is_fully_const()) {
 502                                 RTLIL::SigSpec tmp;
 503                                 tmp = a, a = b, b = tmp;
 504                                 cell->connections["\\A"] = a;
 505                                 cell->connections["\\B"] = b;
 506                         }
 507
 508                         if (b.is_fully_const()) {
 509                                 if (b.as_bool() == (cell->type == "$eq")) {
 510                                         RTLIL::SigSpec input = b;
 511                                         ACTION_DO("\\Y", cell->connections["\\A"]);
 512                                 } else {
 513                                         cell->type = "$not";
 514                                         cell->parameters.erase("\\B_WIDTH");
 515                                         cell->parameters.erase("\\B_SIGNED");
 516                                         cell->connections.erase("\\B");
 517                                 }
 518                                 goto next_cell;
 519                         }
 520                 }
 521
 522                 if (!keepdc)
 523                 {
 524                         bool identity_bu0 = false;
 525                         bool identity_wrt_a = false;
 526                         bool identity_wrt_b = false;
 527
 528                         if (cell->type == "$add" || cell->type == "$sub" || cell->type == "$or" || cell->type == "$xor")
 529                         {
 530                                 RTLIL::SigSpec a = assign_map(cell->connections["\\A"]);
 531                                 RTLIL::SigSpec b = assign_map(cell->connections["\\B"]);
 532
 533                                 if (cell->type != "$sub" && a.is_fully_const() && a.as_bool() == false)
 534                                         identity_wrt_b = true;
 535
 536                                 if (b.is_fully_const() && b.as_bool() == false)
 537                                         identity_wrt_a = true;
 538                         }
 539
 540                         if (cell->type == "$shl" || cell->type == "$shr" || cell->type == "$sshl" || cell->type == "$sshr")
 541                         {
 542                                 RTLIL::SigSpec b = assign_map(cell->connections["\\B"]);
 543
 544                                 if (b.is_fully_const() && b.as_bool() == false)
 545                                         identity_wrt_a = true, identity_bu0 = true;
 546                         }
 547
 548                         if (cell->type == "$mul")
 549                         {
 550                                 RTLIL::SigSpec a = assign_map(cell->connections["\\A"]);
 551                                 RTLIL::SigSpec b = assign_map(cell->connections["\\B"]);
 552
 553                                 if (a.is_fully_const() && a.size() <= 32 && a.as_int() == 1)
 554                                         identity_wrt_b = true;
 555
 556                                 if (b.is_fully_const() && b.size() <= 32 && b.as_int() == 1)
 557                                         identity_wrt_a = true;
 558                         }
 559
 560                         if (cell->type == "$div")
 561                         {
 562                                 RTLIL::SigSpec b = assign_map(cell->connections["\\B"]);
 563
 564                                 if (b.is_fully_const() && b.size() <= 32 && b.as_int() == 1)
 565                                         identity_wrt_a = true;
 566                         }
 567
 568                         if (identity_wrt_a || identity_wrt_b)
 569                         {
 570                                 log("Replacing %s cell `%s' in module `%s' with identity for port %c.\n",
 571                                         cell->type.c_str(), cell->name.c_str(), module->name.c_str(), identity_wrt_a ? 'A' : 'B');
 572
 573                                 if (!identity_wrt_a) {
 574                                         cell->connections.at("\\A") = cell->connections.at("\\B");
 575                                         cell->parameters.at("\\A_WIDTH") = cell->parameters.at("\\B_WIDTH");
 576                                         cell->parameters.at("\\A_SIGNED") = cell->parameters.at("\\B_SIGNED");
 577                                 }
 578
 579                                 cell->type = identity_bu0 ? "$bu0" : "$pos";
 580                                 cell->connections.erase("\\B");
 581                                 cell->parameters.erase("\\B_WIDTH");
 582                                 cell->parameters.erase("\\B_SIGNED");
 583                                 cell->check();
 584
 585                                 OPT_DID_SOMETHING = true;
 586                                 did_something = true;
 587                                 goto next_cell;
 588                         }
 589                 }
 590
 591                 if (mux_bool && (cell->type == "$mux" || cell->type == "$_MUX_") &&
 592                                 cell->connections["\\A"] == RTLIL::SigSpec(0, 1) && cell->connections["\\B"] == RTLIL::SigSpec(1, 1)) {
 593                         replace_cell(module, cell, "mux_bool", "\\Y", cell->connections["\\S"]);
 594                         goto next_cell;
 595                 }
 596
 597                 if (mux_bool && (cell->type == "$mux" || cell->type == "$_MUX_") &&
 598                                 cell->connections["\\A"] == RTLIL::SigSpec(1, 1) && cell->connections["\\B"] == RTLIL::SigSpec(0, 1)) {
 599                         cell->connections["\\A"] = cell->connections["\\S"];
 600                         cell->connections.erase("\\B");
 601                         cell->connections.erase("\\S");
 602                         if (cell->type == "$mux") {
 603                                 cell->parameters["\\A_WIDTH"] = cell->parameters["\\WIDTH"];
 604                                 cell->parameters["\\Y_WIDTH"] = cell->parameters["\\WIDTH"];
 605                                 cell->parameters["\\A_SIGNED"] = 0;
 606                                 cell->parameters.erase("\\WIDTH");
 607                                 cell->type = "$not";
 608                         } else
 609                                 cell->type = "$_INV_";
 610                         OPT_DID_SOMETHING = true;
 611                         did_something = true;
 612                         goto next_cell;
 613                 }
 614
 615                 if (consume_x && mux_bool && (cell->type == "$mux" || cell->type == "$_MUX_") && cell->connections["\\A"] == RTLIL::SigSpec(0, 1)) {
 616                         cell->connections["\\A"] = cell->connections["\\S"];
 617                         cell->connections.erase("\\S");
 618                         if (cell->type == "$mux") {
 619                                 cell->parameters["\\A_WIDTH"] = cell->parameters["\\WIDTH"];
 620                                 cell->parameters["\\B_WIDTH"] = cell->parameters["\\WIDTH"];
 621                                 cell->parameters["\\Y_WIDTH"] = cell->parameters["\\WIDTH"];
 622                                 cell->parameters["\\A_SIGNED"] = 0;
 623                                 cell->parameters["\\B_SIGNED"] = 0;
 624                                 cell->parameters.erase("\\WIDTH");
 625                                 cell->type = "$and";
 626                         } else
 627                                 cell->type = "$_AND_";
 628                         OPT_DID_SOMETHING = true;
 629                         did_something = true;
 630                         goto next_cell;
 631                 }
 632
 633                 if (consume_x && mux_bool && (cell->type == "$mux" || cell->type == "$_MUX_") && cell->connections["\\B"] == RTLIL::SigSpec(1, 1)) {
 634                         cell->connections["\\B"] = cell->connections["\\S"];
 635                         cell->connections.erase("\\S");
 636                         if (cell->type == "$mux") {
 637                                 cell->parameters["\\A_WIDTH"] = cell->parameters["\\WIDTH"];
 638                                 cell->parameters["\\B_WIDTH"] = cell->parameters["\\WIDTH"];
 639                                 cell->parameters["\\Y_WIDTH"] = cell->parameters["\\WIDTH"];
 640                                 cell->parameters["\\A_SIGNED"] = 0;
 641                                 cell->parameters["\\B_SIGNED"] = 0;
 642                                 cell->parameters.erase("\\WIDTH");
 643                                 cell->type = "$or";
 644                         } else
 645                                 cell->type = "$_OR_";
 646                         OPT_DID_SOMETHING = true;
 647                         did_something = true;
 648                         goto next_cell;
 649                 }
 650
 651                 if (mux_undef && (cell->type == "$mux" || cell->type == "$pmux")) {
 652                         RTLIL::SigSpec new_a, new_b, new_s;
 653                         int width = cell->connections.at("\\A").size();
 654                         if ((cell->connections.at("\\A").is_fully_undef() && cell->connections.at("\\B").is_fully_undef()) ||
 655                                         cell->connections.at("\\S").is_fully_undef()) {
 656                                 replace_cell(module, cell, "mux undef", "\\Y", cell->connections.at("\\A"));
 657                                 goto next_cell;
 658                         }
 659                         for (int i = 0; i < cell->connections.at("\\S").size(); i++) {
 660                                 RTLIL::SigSpec old_b = cell->connections.at("\\B").extract(i*width, width);
 661                                 RTLIL::SigSpec old_s = cell->connections.at("\\S").extract(i, 1);
 662                                 if (old_b.is_fully_undef() || old_s.is_fully_undef())
 663                                         continue;
 664                                 new_b.append(old_b);
 665                                 new_s.append(old_s);
 666                         }
 667                         new_a = cell->connections.at("\\A");
 668                         if (new_a.is_fully_undef() && new_s.size() > 0) {
 669                                 new_a = new_b.extract((new_s.size()-1)*width, width);
 670                                 new_b = new_b.extract(0, (new_s.size()-1)*width);
 671                                 new_s = new_s.extract(0, new_s.size()-1);
 672                         }
 673                         if (new_s.size() == 0) {
 674                                 replace_cell(module, cell, "mux undef", "\\Y", new_a);
 675                                 goto next_cell;
 676                         }
 677                         if (new_a == RTLIL::SigSpec(RTLIL::State::S0) && new_b == RTLIL::SigSpec(RTLIL::State::S1)) {
 678                                 replace_cell(module, cell, "mux undef", "\\Y", new_s);
 679                                 goto next_cell;
 680                         }
 681                         if (cell->connections.at("\\S").size() != new_s.size()) {
 682                                 cell->connections.at("\\A") = new_a;
 683                                 cell->connections.at("\\B") = new_b;
 684                                 cell->connections.at("\\S") = new_s;
 685                                 if (new_s.size() > 1) {
 686                                         cell->type = "$pmux";
 687                                         cell->parameters["\\S_WIDTH"] = new_s.size();
 688                                 } else {
 689                                         cell->type = "$mux";
 690                                         cell->parameters.erase("\\S_WIDTH");
 691                                 }
 692                                 OPT_DID_SOMETHING = true;
 693                                 did_something = true;
 694                         }
 695                 }
 696
 697 #define FOLD_1ARG_CELL(_t) \
 698                 if (cell->type == "$" #_t) { \
 699                         RTLIL::SigSpec a = cell->connections["\\A"]; \
 700                         assign_map.apply(a); \
 701                         if (a.is_fully_const()) { \
 702                                 RTLIL::Const dummy_arg(RTLIL::State::S0, 1); \
 703                                 RTLIL::SigSpec y(RTLIL::const_ ## _t(a.as_const(), dummy_arg, \
 704                                                 cell->parameters["\\A_SIGNED"].as_bool(), false, \
 705                                                 cell->parameters["\\Y_WIDTH"].as_int())); \
 706                                 replace_cell(module, cell, stringf("%s", log_signal(a)), "\\Y", y); \
 707                                 goto next_cell; \
 708                         } \
 709                 }
 710 #define FOLD_2ARG_CELL(_t) \
 711                 if (cell->type == "$" #_t) { \
 712                         RTLIL::SigSpec a = cell->connections["\\A"]; \
 713                         RTLIL::SigSpec b = cell->connections["\\B"]; \
 714                         assign_map.apply(a), assign_map.apply(b); \
 715                         if (a.is_fully_const() && b.is_fully_const()) { \
 716                                 RTLIL::SigSpec y(RTLIL::const_ ## _t(a.as_const(), b.as_const(), \
 717                                                 cell->parameters["\\A_SIGNED"].as_bool(), \
 718                                                 cell->parameters["\\B_SIGNED"].as_bool(), \
 719                                                 cell->parameters["\\Y_WIDTH"].as_int())); \
 720                                 replace_cell(module, cell, stringf("%s, %s", log_signal(a), log_signal(b)), "\\Y", y); \
 721                                 goto next_cell; \
 722                         } \
 723                 }
 724
 725                 FOLD_1ARG_CELL(not)
 726                 FOLD_2ARG_CELL(and)
 727                 FOLD_2ARG_CELL(or)
 728                 FOLD_2ARG_CELL(xor)
 729                 FOLD_2ARG_CELL(xnor)
 730
 731                 FOLD_1ARG_CELL(reduce_and)
 732                 FOLD_1ARG_CELL(reduce_or)
 733                 FOLD_1ARG_CELL(reduce_xor)
 734                 FOLD_1ARG_CELL(reduce_xnor)
 735                 FOLD_1ARG_CELL(reduce_bool)
 736
 737                 FOLD_1ARG_CELL(logic_not)
 738                 FOLD_2ARG_CELL(logic_and)
 739                 FOLD_2ARG_CELL(logic_or)
 740
 741                 FOLD_2ARG_CELL(shl)
 742                 FOLD_2ARG_CELL(shr)
 743                 FOLD_2ARG_CELL(sshl)
 744                 FOLD_2ARG_CELL(sshr)
 745
 746                 FOLD_2ARG_CELL(lt)
 747                 FOLD_2ARG_CELL(le)
 748                 FOLD_2ARG_CELL(eq)
 749                 FOLD_2ARG_CELL(ne)
 750                 FOLD_2ARG_CELL(gt)
 751                 FOLD_2ARG_CELL(ge)
 752
 753                 FOLD_2ARG_CELL(add)
 754                 FOLD_2ARG_CELL(sub)
 755                 FOLD_2ARG_CELL(mul)
 756                 FOLD_2ARG_CELL(div)
 757                 FOLD_2ARG_CELL(mod)
 758                 FOLD_2ARG_CELL(pow)
 759
 760                 FOLD_1ARG_CELL(pos)
 761                 FOLD_1ARG_CELL(bu0)
 762                 FOLD_1ARG_CELL(neg)
 763
 764                 // be very conservative with optimizing $mux cells as we do not want to break mux trees
 765                 if (cell->type == "$mux") {
 766                         RTLIL::SigSpec input = assign_map(cell->connections["\\S"]);
 767                         RTLIL::SigSpec inA = assign_map(cell->connections["\\A"]);
 768                         RTLIL::SigSpec inB = assign_map(cell->connections["\\B"]);
 769                         if (input.is_fully_const())
 770                                 ACTION_DO("\\Y", input.as_bool() ? cell->connections["\\B"] : cell->connections["\\A"]);
 771                         else if (inA == inB)
 772                                 ACTION_DO("\\Y", cell->connections["\\A"]);
 773                 }
 774
 775                 if (!keepdc && cell->type == "$mul")
 776                 {
 777                         bool a_signed = cell->parameters["\\A_SIGNED"].as_bool();
 778                         bool b_signed = cell->parameters["\\B_SIGNED"].as_bool();
 779                         bool swapped_ab = false;
 780
 781                         RTLIL::SigSpec sig_a = assign_map(cell->connections["\\A"]);
 782                         RTLIL::SigSpec sig_b = assign_map(cell->connections["\\B"]);
 783                         RTLIL::SigSpec sig_y = assign_map(cell->connections["\\Y"]);
 784
 785                         if (sig_b.is_fully_const() && sig_b.size() <= 32)
 786                                 std::swap(sig_a, sig_b), std::swap(a_signed, b_signed), swapped_ab = true;
 787
 788                         if (sig_a.is_fully_def() && sig_a.size() <= 32)
 789                         {
 790                                 int a_val = sig_a.as_int();
 791
 792                                 if (a_val == 0)
 793                                 {
 794                                         log("Replacing multiply-by-zero cell `%s' in module `%s' with zero-driver.\n",
 795                                                         cell->name.c_str(), module->name.c_str());
 796
 797                                         module->connections.push_back(RTLIL::SigSig(sig_y, RTLIL::SigSpec(0, sig_y.size())));
 798                                         module->remove(cell);
 799
 800                                         OPT_DID_SOMETHING = true;
 801                                         did_something = true;
 802                                         goto next_cell;
 803                                 }
 804
 805                                 for (int i = 1; i < (a_signed ? sig_a.size()-1 : sig_a.size()); i++)
 806                                         if (a_val == (1 << i))
 807                                         {
 808                                                 log("Replacing multiply-by-%d cell `%s' in module `%s' with shift-by-%d.\n",
 809                                                                 a_val, cell->name.c_str(), module->name.c_str(), i);
 810
 811                                                 if (!swapped_ab) {
 812                                                         cell->connections["\\A"] = cell->connections["\\B"];
 813                                                         cell->parameters["\\A_WIDTH"] = cell->parameters["\\B_WIDTH"];
 814                                                         cell->parameters["\\A_SIGNED"] = cell->parameters["\\B_SIGNED"];
 815                                                 }
 816
 817                                                 std::vector<RTLIL::SigBit> new_b = RTLIL::SigSpec(i, 6);
 818
 819                                                 while (SIZE(new_b) > 1 && new_b.back() == RTLIL::State::S0)
 820                                                         new_b.pop_back();
 821
 822                                                 cell->type = "$shl";
 823                                                 cell->parameters["\\B_WIDTH"] = SIZE(new_b);
 824                                                 cell->parameters["\\B_SIGNED"] = false;
 825                                                 cell->connections["\\B"] = new_b;
 826                                                 cell->check();
 827
 828                                                 OPT_DID_SOMETHING = true;
 829                                                 did_something = true;
 830                                                 goto next_cell;
 831                                         }
 832                         }
 833                 }
 834
 835         next_cell:;
 836 #undef ACTION_DO
 837 #undef ACTION_DO_Y
 838 #undef FOLD_1ARG_CELL
 839 #undef FOLD_2ARG_CELL
 840         }
 841 }
 842
 843 struct OptConstPass : public Pass {
 844         OptConstPass() : Pass("opt_const", "perform const folding") { }
 845         virtual void help()
 846         {
 847                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 848                 log("\n");
 849                 log("    opt_const [options] [selection]\n");
 850                 log("\n");
 851                 log("This pass performs const folding on internal cell types with constant inputs.\n");
 852                 log("\n");
 853                 log("    -mux_undef\n");
 854                 log("        remove 'undef' inputs from $mux, $pmux and $_MUX_ cells\n");
 855                 log("\n");
 856                 log("    -mux_bool\n");
 857                 log("        replace $mux cells with inverters or buffers when possible\n");
 858                 log("\n");
 859                 log("    -undriven\n");
 860                 log("        replace undriven nets with undef (x) constants\n");
 861                 log("\n");
 862                 log("    -keepdc\n");
 863                 log("        some optimizations change the behavior of the circuit with respect to\n");
 864                 log("        don't-care bits. for example in 'a+0' a single x-bit in 'a' will cause\n");
 865                 log("        all result bits to be set to x. this behavior changes when 'a+0' is\n");
 866                 log("        replaced by 'a'. the -keepdc option disables all such optimizations.\n");
 867                 log("\n");
 868                 log("    -fine\n");
 869                 log("        perform fine-grain optimizations\n");
 870                 log("\n");
 871         }
 872         virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
 873         {
 874                 bool mux_undef = false;
 875                 bool mux_bool = false;
 876                 bool undriven = false;
 877                 bool do_fine = false;
 878                 bool keepdc = false;
 879
 880                 log_header("Executing OPT_CONST pass (perform const folding).\n");
 881                 log_push();
 882
 883                 size_t argidx;
 884                 for (argidx = 1; argidx < args.size(); argidx++) {
 885                         if (args[argidx] == "-mux_undef") {
 886                                 mux_undef = true;
 887                                 continue;
 888                         }
 889                         if (args[argidx] == "-mux_bool") {
 890                                 mux_bool = true;
 891                                 continue;
 892                         }
 893                         if (args[argidx] == "-undriven") {
 894                                 undriven = true;
 895                                 continue;
 896                         }
 897                         if (args[argidx] == "-fine") {
 898                                 do_fine = true;
 899                                 continue;
 900                         }
 901                         if (args[argidx] == "-keepdc") {
 902                                 keepdc = true;
 903                                 continue;
 904                         }
 905                         break;
 906                 }
 907                 extra_args(args, argidx, design);
 908
 909                 for (auto &mod_it : design->modules)
 910                 {
 911                         if (undriven)
 912                                 replace_undriven(design, mod_it.second);
 913
 914                         do {
 915                                 do {
 916                                         did_something = false;
 917                                         replace_const_cells(design, mod_it.second, false, mux_undef, mux_bool, do_fine, keepdc);
 918                                 } while (did_something);
 919                                 replace_const_cells(design, mod_it.second, true, mux_undef, mux_bool, do_fine, keepdc);
 920                         } while (did_something);
 921                 }
 922
 923                 log_pop();
 924         }
 925 } OptConstPass;
 926