passes/opt/share.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 "kernel/yosys.h"
  21 #include "kernel/satgen.h"
  22 #include "kernel/sigtools.h"
  23 #include "kernel/modtools.h"
  24 #include "kernel/utils.h"
  25 #include "kernel/macc.h"
  26
  27 USING_YOSYS_NAMESPACE
  28 PRIVATE_NAMESPACE_BEGIN
  29
  30 typedef RTLIL::IdString::compare_ptr_by_name<RTLIL::Cell> cell_ptr_cmp;
  31 typedef std::pair<RTLIL::SigSpec, RTLIL::Const> ssc_pair_t;
  32
  33 struct ShareWorkerConfig
  34 {
  35         int limit;
  36         bool opt_force;
  37         bool opt_aggressive;
  38         bool opt_fast;
  39         pool<RTLIL::IdString> generic_uni_ops, generic_bin_ops, generic_cbin_ops, generic_other_ops;
  40 };
  41
  42 struct ShareWorker
  43 {
  44         ShareWorkerConfig config;
  45         pool<RTLIL::IdString> generic_ops;
  46
  47         RTLIL::Design *design;
  48         RTLIL::Module *module;
  49
  50         CellTypes fwd_ct, cone_ct;
  51         ModWalker modwalker;
  52         ModIndex mi;
  53
  54         pool<RTLIL::Cell*> cells_to_remove;
  55         pool<RTLIL::Cell*> recursion_state;
  56
  57         SigMap topo_sigmap;
  58         std::map<RTLIL::Cell*, std::set<RTLIL::Cell*, cell_ptr_cmp>, cell_ptr_cmp> topo_cell_drivers;
  59         std::map<RTLIL::SigBit, std::set<RTLIL::Cell*, cell_ptr_cmp>> topo_bit_drivers;
  60
  61         std::vector<std::pair<RTLIL::SigBit, RTLIL::SigBit>> exclusive_ctrls;
  62
  63
  64         // ------------------------------------------------------------------------------
  65         // Find terminal bits -- i.e. bits that do not (exclusively) feed into a mux tree
  66         // ------------------------------------------------------------------------------
  67
  68         pool<RTLIL::SigBit> terminal_bits;
  69
  70         void find_terminal_bits()
  71         {
  72                 pool<RTLIL::SigBit> queue_bits;
  73                 pool<RTLIL::Cell*> visited_cells;
  74
  75                 queue_bits.insert(modwalker.signal_outputs.begin(), modwalker.signal_outputs.end());
  76
  77                 for (auto &it : module->cells_)
  78                         if (!fwd_ct.cell_known(it.second->type)) {
  79                                 pool<RTLIL::SigBit> &bits = modwalker.cell_inputs[it.second];
  80                                 queue_bits.insert(bits.begin(), bits.end());
  81                         }
  82
  83                 terminal_bits.insert(queue_bits.begin(), queue_bits.end());
  84
  85                 while (!queue_bits.empty())
  86                 {
  87                         pool<ModWalker::PortBit> portbits;
  88                         modwalker.get_drivers(portbits, queue_bits);
  89                         queue_bits.clear();
  90
  91                         for (auto &pbit : portbits) {
  92                                 if (pbit.cell->type == "$mux" || pbit.cell->type == "$pmux") {
  93                                         pool<RTLIL::SigBit> bits = modwalker.sigmap(pbit.cell->getPort("\\S")).to_sigbit_pool();
  94                                         terminal_bits.insert(bits.begin(), bits.end());
  95                                         queue_bits.insert(bits.begin(), bits.end());
  96                                         visited_cells.insert(pbit.cell);
  97                                 }
  98                                 if (fwd_ct.cell_known(pbit.cell->type) && visited_cells.count(pbit.cell) == 0) {
  99                                         pool<RTLIL::SigBit> &bits = modwalker.cell_inputs[pbit.cell];
 100                                         terminal_bits.insert(bits.begin(), bits.end());
 101                                         queue_bits.insert(bits.begin(), bits.end());
 102                                         visited_cells.insert(pbit.cell);
 103                                 }
 104                         }
 105                 }
 106         }
 107
 108
 109         // ---------------------------------------------------
 110         // Code for sharing and comparing MACC cells
 111         // ---------------------------------------------------
 112
 113         static int bits_macc_port(const Macc::port_t &p, int width)
 114         {
 115                 if (GetSize(p.in_a) == 0 || GetSize(p.in_b) == 0)
 116                         return min(max(GetSize(p.in_a), GetSize(p.in_b)), width);
 117                 return min(GetSize(p.in_a), width) * min(GetSize(p.in_b), width) / 2;
 118         }
 119
 120         static int bits_macc(const Macc &m, int width)
 121         {
 122                 int bits = GetSize(m.bit_ports);
 123                 for (auto &p : m.ports)
 124                         bits += bits_macc_port(p, width);
 125                 return bits;
 126         }
 127
 128         static int bits_macc(RTLIL::Cell *c)
 129         {
 130                 Macc m(c);
 131                 int width = GetSize(c->getPort("\\Y"));
 132                 return bits_macc(m, width);
 133         }
 134
 135         static bool cmp_macc_ports(const Macc::port_t &p1, const Macc::port_t &p2)
 136         {
 137                 bool mul1 = GetSize(p1.in_a) && GetSize(p1.in_b);
 138                 bool mul2 = GetSize(p2.in_a) && GetSize(p2.in_b);
 139
 140                 int w1 = mul1 ? GetSize(p1.in_a) * GetSize(p1.in_b) : GetSize(p1.in_a) + GetSize(p1.in_b);
 141                 int w2 = mul2 ? GetSize(p2.in_a) * GetSize(p2.in_b) : GetSize(p2.in_a) + GetSize(p2.in_b);
 142
 143                 if (mul1 != mul2)
 144                         return mul1;
 145
 146                 if (w1 != w2)
 147                         return w1 > w2;
 148
 149                 if (p1.is_signed != p2.is_signed)
 150                         return p1.is_signed < p2.is_signed;
 151
 152                 if (p1.do_subtract != p2.do_subtract)
 153                         return p1.do_subtract < p2.do_subtract;
 154
 155                 if (p1.in_a != p2.in_a)
 156                         return p1.in_a < p2.in_a;
 157
 158                 if (p1.in_b != p2.in_b)
 159                         return p1.in_b < p2.in_b;
 160
 161                 return false;
 162         }
 163
 164         int share_macc_ports(Macc::port_t &p1, Macc::port_t &p2, int w1, int w2,
 165                         RTLIL::SigSpec act = RTLIL::SigSpec(), Macc *supermacc = nullptr, pool<RTLIL::Cell*> *supercell_aux = nullptr)
 166         {
 167                 if (p1.do_subtract != p2.do_subtract)
 168                         return -1;
 169
 170                 bool mul1 = GetSize(p1.in_a) && GetSize(p1.in_b);
 171                 bool mul2 = GetSize(p2.in_a) && GetSize(p2.in_b);
 172
 173                 if (mul1 != mul2)
 174                         return -1;
 175
 176                 bool force_signed = false, force_not_signed = false;
 177
 178                 if ((GetSize(p1.in_a) && GetSize(p1.in_a) < w1) || (GetSize(p1.in_b) && GetSize(p1.in_b) < w1)) {
 179                         if (p1.is_signed)
 180                                 force_signed = true;
 181                         else
 182                                 force_not_signed = true;
 183                 }
 184
 185                 if ((GetSize(p2.in_a) && GetSize(p2.in_a) < w2) || (GetSize(p2.in_b) && GetSize(p2.in_b) < w2)) {
 186                         if (p2.is_signed)
 187                                 force_signed = true;
 188                         else
 189                                 force_not_signed = true;
 190                 }
 191
 192                 if (force_signed && force_not_signed)
 193                         return -1;
 194
 195                 if (supermacc)
 196                 {
 197                         RTLIL::SigSpec sig_a1 = p1.in_a, sig_b1 = p1.in_b;
 198                         RTLIL::SigSpec sig_a2 = p2.in_a, sig_b2 = p2.in_b;
 199
 200                         RTLIL::SigSpec sig_a = GetSize(sig_a1) > GetSize(sig_a2) ? sig_a1 : sig_a2;
 201                         RTLIL::SigSpec sig_b = GetSize(sig_b1) > GetSize(sig_b2) ? sig_b1 : sig_b2;
 202
 203                         sig_a1.extend_u0(GetSize(sig_a), p1.is_signed);
 204                         sig_b1.extend_u0(GetSize(sig_b), p1.is_signed);
 205
 206                         sig_a2.extend_u0(GetSize(sig_a), p2.is_signed);
 207                         sig_b2.extend_u0(GetSize(sig_b), p2.is_signed);
 208
 209                         if (supercell_aux && GetSize(sig_a)) {
 210                                 sig_a = module->addWire(NEW_ID, GetSize(sig_a));
 211                                 supercell_aux->insert(module->addMux(NEW_ID, sig_a2, sig_a1, act, sig_a));
 212                         }
 213
 214                         if (supercell_aux && GetSize(sig_b)) {
 215                                 sig_b = module->addWire(NEW_ID, GetSize(sig_b));
 216                                 supercell_aux->insert(module->addMux(NEW_ID, sig_b2, sig_b1, act, sig_b));
 217                         }
 218
 219                         Macc::port_t p;
 220                         p.in_a = sig_a;
 221                         p.in_b = sig_b;
 222                         p.is_signed = force_signed;
 223                         p.do_subtract = p1.do_subtract;
 224                         supermacc->ports.push_back(p);
 225                 }
 226
 227                 int score = 1000 + abs(GetSize(p1.in_a) - GetSize(p2.in_a)) * max(abs(GetSize(p1.in_b) - GetSize(p2.in_b)), 1);
 228
 229                 for (int i = 0; i < min(GetSize(p1.in_a), GetSize(p2.in_a)); i++)
 230                         if (p1.in_a[i] == p2.in_a[i] && score > 0)
 231                                 score--;
 232
 233                 for (int i = 0; i < min(GetSize(p1.in_b), GetSize(p2.in_b)); i++)
 234                         if (p1.in_b[i] == p2.in_b[i] && score > 0)
 235                                 score--;
 236
 237                 return score;
 238         }
 239
 240         int share_macc(RTLIL::Cell *c1, RTLIL::Cell *c2,
 241                         RTLIL::SigSpec act = RTLIL::SigSpec(), RTLIL::Cell *supercell = nullptr, pool<RTLIL::Cell*> *supercell_aux = nullptr)
 242         {
 243                 Macc m1(c1), m2(c2), supermacc;
 244
 245                 int w1 = GetSize(c1->getPort("\\Y")), w2 = GetSize(c2->getPort("\\Y"));
 246                 int width = max(w1, w2);
 247
 248                 m1.optimize(w1);
 249                 m2.optimize(w2);
 250
 251                 std::sort(m1.ports.begin(), m1.ports.end(), cmp_macc_ports);
 252                 std::sort(m2.ports.begin(), m2.ports.end(), cmp_macc_ports);
 253
 254                 std::set<int> m1_unmapped, m2_unmapped;
 255
 256                 for (int i = 0; i < GetSize(m1.ports); i++)
 257                         m1_unmapped.insert(i);
 258
 259                 for (int i = 0; i < GetSize(m2.ports); i++)
 260                         m2_unmapped.insert(i);
 261
 262                 while (1)
 263                 {
 264                         int best_i = -1, best_j = -1, best_score = 0;
 265
 266                         for (int i : m1_unmapped)
 267                         for (int j : m2_unmapped) {
 268                                 int score = share_macc_ports(m1.ports[i], m2.ports[j], w1, w2);
 269                                 if (score >= 0 && (best_i < 0 || best_score > score))
 270                                         best_i = i, best_j = j, best_score = score;
 271                         }
 272
 273                         if (best_i >= 0) {
 274                                 m1_unmapped.erase(best_i);
 275                                 m2_unmapped.erase(best_j);
 276                                 share_macc_ports(m1.ports[best_i], m2.ports[best_j], w1, w2, act, &supermacc, supercell_aux);
 277                         } else
 278                                 break;
 279                 }
 280
 281                 for (int i : m1_unmapped)
 282                 {
 283                         RTLIL::SigSpec sig_a = m1.ports[i].in_a;
 284                         RTLIL::SigSpec sig_b = m1.ports[i].in_b;
 285
 286                         if (supercell_aux && GetSize(sig_a)) {
 287                                 sig_a = module->addWire(NEW_ID, GetSize(sig_a));
 288                                 supercell_aux->insert(module->addMux(NEW_ID, RTLIL::SigSpec(0, GetSize(sig_a)), m1.ports[i].in_a, act, sig_a));
 289                         }
 290
 291                         if (supercell_aux && GetSize(sig_b)) {
 292                                 sig_b = module->addWire(NEW_ID, GetSize(sig_b));
 293                                 supercell_aux->insert(module->addMux(NEW_ID, RTLIL::SigSpec(0, GetSize(sig_b)), m1.ports[i].in_b, act, sig_b));
 294                         }
 295
 296                         Macc::port_t p;
 297                         p.in_a = sig_a;
 298                         p.in_b = sig_b;
 299                         p.is_signed = m1.ports[i].is_signed;
 300                         p.do_subtract = m1.ports[i].do_subtract;
 301                         supermacc.ports.push_back(p);
 302                 }
 303
 304                 for (int i : m2_unmapped)
 305                 {
 306                         RTLIL::SigSpec sig_a = m2.ports[i].in_a;
 307                         RTLIL::SigSpec sig_b = m2.ports[i].in_b;
 308
 309                         if (supercell_aux && GetSize(sig_a)) {
 310                                 sig_a = module->addWire(NEW_ID, GetSize(sig_a));
 311                                 supercell_aux->insert(module->addMux(NEW_ID, m2.ports[i].in_a, RTLIL::SigSpec(0, GetSize(sig_a)), act, sig_a));
 312                         }
 313
 314                         if (supercell_aux && GetSize(sig_b)) {
 315                                 sig_b = module->addWire(NEW_ID, GetSize(sig_b));
 316                                 supercell_aux->insert(module->addMux(NEW_ID, m2.ports[i].in_b, RTLIL::SigSpec(0, GetSize(sig_b)), act, sig_b));
 317                         }
 318
 319                         Macc::port_t p;
 320                         p.in_a = sig_a;
 321                         p.in_b = sig_b;
 322                         p.is_signed = m2.ports[i].is_signed;
 323                         p.do_subtract = m2.ports[i].do_subtract;
 324                         supermacc.ports.push_back(p);
 325                 }
 326
 327                 if (supercell)
 328                 {
 329                         RTLIL::SigSpec sig_y = module->addWire(NEW_ID, width);
 330
 331                         supercell_aux->insert(module->addPos(NEW_ID, sig_y, c1->getPort("\\Y")));
 332                         supercell_aux->insert(module->addPos(NEW_ID, sig_y, c2->getPort("\\Y")));
 333
 334                         supercell->setParam("\\Y_WIDTH", width);
 335                         supercell->setPort("\\Y", sig_y);
 336
 337                         supermacc.optimize(width);
 338                         supermacc.to_cell(supercell);
 339                 }
 340
 341                 return bits_macc(supermacc, width);
 342         }
 343
 344
 345         // ---------------------------------------------------
 346         // Find shareable cells and compatible groups of cells
 347         // ---------------------------------------------------
 348
 349         pool<RTLIL::Cell*> shareable_cells;
 350
 351         void find_shareable_cells()
 352         {
 353                 for (auto cell : module->cells())
 354                 {
 355                         if (!design->selected(module, cell) || !modwalker.ct.cell_known(cell->type))
 356                                 continue;
 357
 358                         for (auto &bit : modwalker.cell_outputs[cell])
 359                                 if (terminal_bits.count(bit))
 360                                         goto not_a_muxed_cell;
 361
 362                         if (0)
 363                 not_a_muxed_cell:
 364                                 continue;
 365
 366                         if (config.opt_force) {
 367                                 shareable_cells.insert(cell);
 368                                 continue;
 369                         }
 370
 371                         if (cell->type == "$memrd") {
 372                                 if (cell->parameters.at("\\CLK_ENABLE").as_bool())
 373                                         continue;
 374                                 if (config.opt_aggressive || !modwalker.sigmap(cell->getPort("\\ADDR")).is_fully_const())
 375                                         shareable_cells.insert(cell);
 376                                 continue;
 377                         }
 378
 379                         if (cell->type == "$mul" || cell->type == "$div" || cell->type == "$mod") {
 380                                 if (config.opt_aggressive || cell->parameters.at("\\Y_WIDTH").as_int() >= 4)
 381                                         shareable_cells.insert(cell);
 382                                 continue;
 383                         }
 384
 385                         if (cell->type == "$shl" || cell->type == "$shr" || cell->type == "$sshl" || cell->type == "$sshr") {
 386                                 if (config.opt_aggressive || cell->parameters.at("\\Y_WIDTH").as_int() >= 8)
 387                                         shareable_cells.insert(cell);
 388                                 continue;
 389                         }
 390
 391                         if (generic_ops.count(cell->type)) {
 392                                 if (config.opt_aggressive)
 393                                         shareable_cells.insert(cell);
 394                                 continue;
 395                         }
 396                 }
 397         }
 398
 399         bool is_shareable_pair(RTLIL::Cell *c1, RTLIL::Cell *c2)
 400         {
 401                 if (c1->type != c2->type)
 402                         return false;
 403
 404                 if (c1->type == "$memrd")
 405                 {
 406                         if (c1->parameters.at("\\MEMID").decode_string() != c2->parameters.at("\\MEMID").decode_string())
 407                                 return false;
 408
 409                         return true;
 410                 }
 411
 412                 if (config.generic_uni_ops.count(c1->type))
 413                 {
 414                         if (!config.opt_aggressive)
 415                         {
 416                                 int a1_width = c1->parameters.at("\\A_WIDTH").as_int();
 417                                 int y1_width = c1->parameters.at("\\Y_WIDTH").as_int();
 418
 419                                 int a2_width = c2->parameters.at("\\A_WIDTH").as_int();
 420                                 int y2_width = c2->parameters.at("\\Y_WIDTH").as_int();
 421
 422                                 if (max(a1_width, a2_width) > 2 * min(a1_width, a2_width)) return false;
 423                                 if (max(y1_width, y2_width) > 2 * min(y1_width, y2_width)) return false;
 424                         }
 425
 426                         return true;
 427                 }
 428
 429                 if (config.generic_bin_ops.count(c1->type) || c1->type == "$alu")
 430                 {
 431                         if (!config.opt_aggressive)
 432                         {
 433                                 int a1_width = c1->parameters.at("\\A_WIDTH").as_int();
 434                                 int b1_width = c1->parameters.at("\\B_WIDTH").as_int();
 435                                 int y1_width = c1->parameters.at("\\Y_WIDTH").as_int();
 436
 437                                 int a2_width = c2->parameters.at("\\A_WIDTH").as_int();
 438                                 int b2_width = c2->parameters.at("\\B_WIDTH").as_int();
 439                                 int y2_width = c2->parameters.at("\\Y_WIDTH").as_int();
 440
 441                                 if (max(a1_width, a2_width) > 2 * min(a1_width, a2_width)) return false;
 442                                 if (max(b1_width, b2_width) > 2 * min(b1_width, b2_width)) return false;
 443                                 if (max(y1_width, y2_width) > 2 * min(y1_width, y2_width)) return false;
 444                         }
 445
 446                         return true;
 447                 }
 448
 449                 if (config.generic_cbin_ops.count(c1->type))
 450                 {
 451                         if (!config.opt_aggressive)
 452                         {
 453                                 int a1_width = c1->parameters.at("\\A_WIDTH").as_int();
 454                                 int b1_width = c1->parameters.at("\\B_WIDTH").as_int();
 455                                 int y1_width = c1->parameters.at("\\Y_WIDTH").as_int();
 456
 457                                 int a2_width = c2->parameters.at("\\A_WIDTH").as_int();
 458                                 int b2_width = c2->parameters.at("\\B_WIDTH").as_int();
 459                                 int y2_width = c2->parameters.at("\\Y_WIDTH").as_int();
 460
 461                                 int min1_width = min(a1_width, b1_width);
 462                                 int max1_width = max(a1_width, b1_width);
 463
 464                                 int min2_width = min(a2_width, b2_width);
 465                                 int max2_width = max(a2_width, b2_width);
 466
 467                                 if (max(min1_width, min2_width) > 2 * min(min1_width, min2_width)) return false;
 468                                 if (max(max1_width, max2_width) > 2 * min(max1_width, max2_width)) return false;
 469                                 if (max(y1_width, y2_width) > 2 * min(y1_width, y2_width)) return false;
 470                         }
 471
 472                         return true;
 473                 }
 474
 475                 if (c1->type == "$macc")
 476                 {
 477                         if (!config.opt_aggressive)
 478                                 if (share_macc(c1, c2) > 2 * min(bits_macc(c1), bits_macc(c2))) return false;
 479
 480                         return true;
 481                 }
 482
 483                 for (auto &it : c1->parameters)
 484                         if (c2->parameters.count(it.first) == 0 || c2->parameters.at(it.first) != it.second)
 485                                 return false;
 486
 487                 for (auto &it : c2->parameters)
 488                         if (c1->parameters.count(it.first) == 0 || c1->parameters.at(it.first) != it.second)
 489                                 return false;
 490
 491                 return true;
 492         }
 493
 494         void find_shareable_partners(std::vector<RTLIL::Cell*> &results, RTLIL::Cell *cell)
 495         {
 496                 results.clear();
 497                 for (auto c : shareable_cells)
 498                         if (c != cell && is_shareable_pair(c, cell))
 499                                 results.push_back(c);
 500         }
 501
 502
 503         // -----------------------
 504         // Create replacement cell
 505         // -----------------------
 506
 507         RTLIL::Cell *make_supercell(RTLIL::Cell *c1, RTLIL::Cell *c2, RTLIL::SigSpec act, pool<RTLIL::Cell*> &supercell_aux)
 508         {
 509                 log_assert(c1->type == c2->type);
 510
 511                 if (config.generic_uni_ops.count(c1->type))
 512                 {
 513                         if (c1->parameters.at("\\A_SIGNED").as_bool() != c2->parameters.at("\\A_SIGNED").as_bool())
 514                         {
 515                                 RTLIL::Cell *unsigned_cell = c1->parameters.at("\\A_SIGNED").as_bool() ? c2 : c1;
 516                                 if (unsigned_cell->getPort("\\A").to_sigbit_vector().back() != RTLIL::State::S0) {
 517                                         unsigned_cell->parameters.at("\\A_WIDTH") = unsigned_cell->parameters.at("\\A_WIDTH").as_int() + 1;
 518                                         RTLIL::SigSpec new_a = unsigned_cell->getPort("\\A");
 519                                         new_a.append_bit(RTLIL::State::S0);
 520                                         unsigned_cell->setPort("\\A", new_a);
 521                                 }
 522                                 unsigned_cell->parameters.at("\\A_SIGNED") = true;
 523                                 unsigned_cell->check();
 524                         }
 525
 526                         bool a_signed = c1->parameters.at("\\A_SIGNED").as_bool();
 527                         log_assert(a_signed == c2->parameters.at("\\A_SIGNED").as_bool());
 528
 529                         RTLIL::SigSpec a1 = c1->getPort("\\A");
 530                         RTLIL::SigSpec y1 = c1->getPort("\\Y");
 531
 532                         RTLIL::SigSpec a2 = c2->getPort("\\A");
 533                         RTLIL::SigSpec y2 = c2->getPort("\\Y");
 534
 535                         int a_width = max(a1.size(), a2.size());
 536                         int y_width = max(y1.size(), y2.size());
 537
 538                         a1.extend_u0(a_width, a_signed);
 539                         a2.extend_u0(a_width, a_signed);
 540
 541                         RTLIL::SigSpec a = module->addWire(NEW_ID, a_width);
 542                         supercell_aux.insert(module->addMux(NEW_ID, a2, a1, act, a));
 543
 544                         RTLIL::Wire *y = module->addWire(NEW_ID, y_width);
 545
 546                         RTLIL::Cell *supercell = module->addCell(NEW_ID, c1->type);
 547                         supercell->parameters["\\A_SIGNED"] = a_signed;
 548                         supercell->parameters["\\A_WIDTH"] = a_width;
 549                         supercell->parameters["\\Y_WIDTH"] = y_width;
 550                         supercell->setPort("\\A", a);
 551                         supercell->setPort("\\Y", y);
 552
 553                         supercell_aux.insert(module->addPos(NEW_ID, y, y1));
 554                         supercell_aux.insert(module->addPos(NEW_ID, y, y2));
 555
 556                         supercell_aux.insert(supercell);
 557                         return supercell;
 558                 }
 559
 560                 if (config.generic_bin_ops.count(c1->type) || config.generic_cbin_ops.count(c1->type) || c1->type == "$alu")
 561                 {
 562                         bool modified_src_cells = false;
 563
 564                         if (config.generic_cbin_ops.count(c1->type))
 565                         {
 566                                 int score_unflipped = max(c1->parameters.at("\\A_WIDTH").as_int(), c2->parameters.at("\\A_WIDTH").as_int()) +
 567                                                 max(c1->parameters.at("\\B_WIDTH").as_int(), c2->parameters.at("\\B_WIDTH").as_int());
 568
 569                                 int score_flipped = max(c1->parameters.at("\\A_WIDTH").as_int(), c2->parameters.at("\\B_WIDTH").as_int()) +
 570                                                 max(c1->parameters.at("\\B_WIDTH").as_int(), c2->parameters.at("\\A_WIDTH").as_int());
 571
 572                                 if (score_flipped < score_unflipped)
 573                                 {
 574                                         RTLIL::SigSpec tmp = c2->getPort("\\A");
 575                                         c2->setPort("\\A", c2->getPort("\\B"));
 576                                         c2->setPort("\\B", tmp);
 577
 578                                         std::swap(c2->parameters.at("\\A_WIDTH"), c2->parameters.at("\\B_WIDTH"));
 579                                         std::swap(c2->parameters.at("\\A_SIGNED"), c2->parameters.at("\\B_SIGNED"));
 580                                         modified_src_cells = true;
 581                                 }
 582                         }
 583
 584                         if (c1->parameters.at("\\A_SIGNED").as_bool() != c2->parameters.at("\\A_SIGNED").as_bool())
 585
 586                         {
 587                                 RTLIL::Cell *unsigned_cell = c1->parameters.at("\\A_SIGNED").as_bool() ? c2 : c1;
 588                                 if (unsigned_cell->getPort("\\A").to_sigbit_vector().back() != RTLIL::State::S0) {
 589                                         unsigned_cell->parameters.at("\\A_WIDTH") = unsigned_cell->parameters.at("\\A_WIDTH").as_int() + 1;
 590                                         RTLIL::SigSpec new_a = unsigned_cell->getPort("\\A");
 591                                         new_a.append_bit(RTLIL::State::S0);
 592                                         unsigned_cell->setPort("\\A", new_a);
 593                                 }
 594                                 unsigned_cell->parameters.at("\\A_SIGNED") = true;
 595                                 modified_src_cells = true;
 596                         }
 597
 598                         if (c1->parameters.at("\\B_SIGNED").as_bool() != c2->parameters.at("\\B_SIGNED").as_bool())
 599                         {
 600                                 RTLIL::Cell *unsigned_cell = c1->parameters.at("\\B_SIGNED").as_bool() ? c2 : c1;
 601                                 if (unsigned_cell->getPort("\\B").to_sigbit_vector().back() != RTLIL::State::S0) {
 602                                         unsigned_cell->parameters.at("\\B_WIDTH") = unsigned_cell->parameters.at("\\B_WIDTH").as_int() + 1;
 603                                         RTLIL::SigSpec new_b = unsigned_cell->getPort("\\B");
 604                                         new_b.append_bit(RTLIL::State::S0);
 605                                         unsigned_cell->setPort("\\B", new_b);
 606                                 }
 607                                 unsigned_cell->parameters.at("\\B_SIGNED") = true;
 608                                 modified_src_cells = true;
 609                         }
 610
 611                         if (modified_src_cells) {
 612                                 c1->check();
 613                                 c2->check();
 614                         }
 615
 616                         bool a_signed = c1->parameters.at("\\A_SIGNED").as_bool();
 617                         bool b_signed = c1->parameters.at("\\B_SIGNED").as_bool();
 618
 619                         log_assert(a_signed == c2->parameters.at("\\A_SIGNED").as_bool());
 620                         log_assert(b_signed == c2->parameters.at("\\B_SIGNED").as_bool());
 621
 622                         if (c1->type == "$shl" || c1->type == "$shr" || c1->type == "$sshl" || c1->type == "$sshr")
 623                                 b_signed = false;
 624
 625                         RTLIL::SigSpec a1 = c1->getPort("\\A");
 626                         RTLIL::SigSpec b1 = c1->getPort("\\B");
 627                         RTLIL::SigSpec y1 = c1->getPort("\\Y");
 628
 629                         RTLIL::SigSpec a2 = c2->getPort("\\A");
 630                         RTLIL::SigSpec b2 = c2->getPort("\\B");
 631                         RTLIL::SigSpec y2 = c2->getPort("\\Y");
 632
 633                         int a_width = max(a1.size(), a2.size());
 634                         int b_width = max(b1.size(), b2.size());
 635                         int y_width = max(y1.size(), y2.size());
 636
 637                         if (c1->type == "$shr" && a_signed)
 638                         {
 639                                 a_width = max(y_width, a_width);
 640
 641                                 if (a1.size() < y1.size()) a1.extend_u0(y1.size(), true);
 642                                 if (a2.size() < y2.size()) a2.extend_u0(y2.size(), true);
 643
 644                                 a1.extend_u0(a_width, false);
 645                                 a2.extend_u0(a_width, false);
 646                         }
 647                         else
 648                         {
 649                                 a1.extend_u0(a_width, a_signed);
 650                                 a2.extend_u0(a_width, a_signed);
 651                         }
 652
 653                         b1.extend_u0(b_width, b_signed);
 654                         b2.extend_u0(b_width, b_signed);
 655
 656                         RTLIL::SigSpec a = module->addWire(NEW_ID, a_width);
 657                         RTLIL::SigSpec b = module->addWire(NEW_ID, b_width);
 658
 659                         supercell_aux.insert(module->addMux(NEW_ID, a2, a1, act, a));
 660                         supercell_aux.insert(module->addMux(NEW_ID, b2, b1, act, b));
 661
 662                         RTLIL::Wire *y = module->addWire(NEW_ID, y_width);
 663                         RTLIL::Wire *x = c1->type == "$alu" ? module->addWire(NEW_ID, y_width) : nullptr;
 664                         RTLIL::Wire *co = c1->type == "$alu" ? module->addWire(NEW_ID, y_width) : nullptr;
 665
 666                         RTLIL::Cell *supercell = module->addCell(NEW_ID, c1->type);
 667                         supercell->parameters["\\A_SIGNED"] = a_signed;
 668                         supercell->parameters["\\B_SIGNED"] = b_signed;
 669                         supercell->parameters["\\A_WIDTH"] = a_width;
 670                         supercell->parameters["\\B_WIDTH"] = b_width;
 671                         supercell->parameters["\\Y_WIDTH"] = y_width;
 672                         supercell->setPort("\\A", a);
 673                         supercell->setPort("\\B", b);
 674                         supercell->setPort("\\Y", y);
 675                         if (c1->type == "$alu") {
 676                                 RTLIL::Wire *ci = module->addWire(NEW_ID), *bi = module->addWire(NEW_ID);
 677                                 supercell_aux.insert(module->addMux(NEW_ID, c2->getPort("\\CI"), c1->getPort("\\CI"), act, ci));
 678                                 supercell_aux.insert(module->addMux(NEW_ID, c2->getPort("\\BI"), c1->getPort("\\BI"), act, bi));
 679                                 supercell->setPort("\\CI", ci);
 680                                 supercell->setPort("\\BI", bi);
 681                                 supercell->setPort("\\CO", co);
 682                                 supercell->setPort("\\X", x);
 683                         }
 684                         supercell->check();
 685
 686                         supercell_aux.insert(module->addPos(NEW_ID, y, y1));
 687                         supercell_aux.insert(module->addPos(NEW_ID, y, y2));
 688                         if (c1->type == "$alu") {
 689                                 supercell_aux.insert(module->addPos(NEW_ID, co, c1->getPort("\\CO")));
 690                                 supercell_aux.insert(module->addPos(NEW_ID, co, c2->getPort("\\CO")));
 691                                 supercell_aux.insert(module->addPos(NEW_ID, x, c1->getPort("\\X")));
 692                                 supercell_aux.insert(module->addPos(NEW_ID, x, c2->getPort("\\X")));
 693                         }
 694
 695                         supercell_aux.insert(supercell);
 696                         return supercell;
 697                 }
 698
 699                 if (c1->type == "$macc")
 700                 {
 701                         RTLIL::Cell *supercell = module->addCell(NEW_ID, c1->type);
 702                         supercell_aux.insert(supercell);
 703                         share_macc(c1, c2, act, supercell, &supercell_aux);
 704                         supercell->check();
 705                         return supercell;
 706                 }
 707
 708                 if (c1->type == "$memrd")
 709                 {
 710                         RTLIL::Cell *supercell = module->addCell(NEW_ID, c1);
 711                         RTLIL::SigSpec addr1 = c1->getPort("\\ADDR");
 712                         RTLIL::SigSpec addr2 = c2->getPort("\\ADDR");
 713                         if (GetSize(addr1) < GetSize(addr2))
 714                                 addr1.extend_u0(GetSize(addr2));
 715                         else
 716                                 addr2.extend_u0(GetSize(addr1));
 717                         supercell->setPort("\\ADDR", addr1 != addr2 ? module->Mux(NEW_ID, addr2, addr1, act) : addr1);
 718                         supercell->parameters["\\ABITS"] = RTLIL::Const(GetSize(addr1));
 719                         supercell_aux.insert(module->addPos(NEW_ID, supercell->getPort("\\DATA"), c2->getPort("\\DATA")));
 720                         supercell_aux.insert(supercell);
 721                         return supercell;
 722                 }
 723
 724                 log_abort();
 725         }
 726
 727
 728         // -------------------------------------------
 729         // Finding forbidden control inputs for a cell
 730         // -------------------------------------------
 731
 732         std::map<RTLIL::Cell*, pool<RTLIL::SigBit>, cell_ptr_cmp> forbidden_controls_cache;
 733
 734         const pool<RTLIL::SigBit> &find_forbidden_controls(RTLIL::Cell *cell)
 735         {
 736                 if (recursion_state.count(cell)) {
 737                         static pool<RTLIL::SigBit> empty_controls_set;
 738                         return empty_controls_set;
 739                 }
 740
 741                 if (forbidden_controls_cache.count(cell))
 742                         return forbidden_controls_cache.at(cell);
 743
 744                 pool<ModWalker::PortBit> pbits;
 745                 pool<RTLIL::Cell*> consumer_cells;
 746
 747                 modwalker.get_consumers(pbits, modwalker.cell_outputs[cell]);
 748
 749                 for (auto &bit : pbits) {
 750                         if ((bit.cell->type == "$mux" || bit.cell->type == "$pmux") && bit.port == "\\S")
 751                                 forbidden_controls_cache[cell].insert(bit.cell->getPort("\\S").extract(bit.offset, 1));
 752                         consumer_cells.insert(bit.cell);
 753                 }
 754
 755                 recursion_state.insert(cell);
 756
 757                 for (auto c : consumer_cells)
 758                         if (fwd_ct.cell_known(c->type)) {
 759                                 const pool<RTLIL::SigBit> &bits = find_forbidden_controls(c);
 760                                 forbidden_controls_cache[cell].insert(bits.begin(), bits.end());
 761                         }
 762
 763                 log_assert(recursion_state.count(cell) != 0);
 764                 recursion_state.erase(cell);
 765
 766                 return forbidden_controls_cache[cell];
 767         }
 768
 769
 770         // --------------------------------------------------------
 771         // Finding control inputs and activation pattern for a cell
 772         // --------------------------------------------------------
 773
 774         std::map<RTLIL::Cell*, pool<ssc_pair_t>, cell_ptr_cmp> activation_patterns_cache;
 775
 776         bool sort_check_activation_pattern(ssc_pair_t &p)
 777         {
 778                 std::map<RTLIL::SigBit, RTLIL::State> p_bits;
 779
 780                 std::vector<RTLIL::SigBit> p_first_bits = p.first;
 781                 for (int i = 0; i < GetSize(p_first_bits); i++) {
 782                         RTLIL::SigBit b = p_first_bits[i];
 783                         RTLIL::State v = p.second.bits[i];
 784                         if (p_bits.count(b) && p_bits.at(b) != v)
 785                                 return false;
 786                         p_bits[b] = v;
 787                 }
 788
 789                 p.first = RTLIL::SigSpec();
 790                 p.second.bits.clear();
 791
 792                 for (auto &it : p_bits) {
 793                         p.first.append_bit(it.first);
 794                         p.second.bits.push_back(it.second);
 795                 }
 796
 797                 return true;
 798         }
 799
 800         void optimize_activation_patterns(pool<ssc_pair_t> &patterns)
 801         {
 802                 // TODO: Remove patterns that are contained in other patterns
 803
 804                 dict<SigSpec, pool<Const>> db;
 805                 bool did_something = false;
 806
 807                 for (auto const &p : patterns)
 808                 {
 809                         auto &sig = p.first;
 810                         auto &val = p.second;
 811                         int len = GetSize(sig);
 812
 813                         for (int i = 0; i < len; i++)
 814                         {
 815                                 auto otherval = val;
 816
 817                                 if (otherval.bits[i] == State::S0)
 818                                         otherval.bits[i] = State::S1;
 819                                 else if (otherval.bits[i] == State::S1)
 820                                         otherval.bits[i] = State::S0;
 821                                 else
 822                                         continue;
 823
 824                                 if (db[sig].count(otherval))
 825                                 {
 826                                         auto newsig = sig;
 827                                         newsig.remove(i);
 828
 829                                         auto newval = val;
 830                                         newval.bits.erase(newval.bits.begin() + i);
 831
 832                                         db[newsig].insert(newval);
 833                                         db[sig].erase(otherval);
 834
 835                                         did_something = true;
 836                                         goto next_pattern;
 837                                 }
 838                         }
 839
 840                         db[sig].insert(val);
 841                 next_pattern:;
 842                 }
 843
 844                 if (!did_something)
 845                         return;
 846
 847                 patterns.clear();
 848                 for (auto &it : db)
 849                 for (auto &val : it.second)
 850                         patterns.insert(make_pair(it.first, val));
 851
 852                 optimize_activation_patterns(patterns);
 853         }
 854
 855         const pool<ssc_pair_t> &find_cell_activation_patterns(RTLIL::Cell *cell, const char *indent)
 856         {
 857                 if (recursion_state.count(cell)) {
 858                         static pool<ssc_pair_t> empty_patterns_set;
 859                         return empty_patterns_set;
 860                 }
 861
 862                 if (activation_patterns_cache.count(cell))
 863                         return activation_patterns_cache.at(cell);
 864
 865                 const pool<RTLIL::SigBit> &cell_out_bits = modwalker.cell_outputs[cell];
 866                 pool<RTLIL::Cell*> driven_cells, driven_data_muxes;
 867
 868                 for (auto &bit : cell_out_bits)
 869                 {
 870                         if (terminal_bits.count(bit)) {
 871                                 // Terminal cells are always active: unconditional activation pattern
 872                                 activation_patterns_cache[cell].insert(ssc_pair_t());
 873                                 return activation_patterns_cache.at(cell);
 874                         }
 875                         for (auto &pbit : modwalker.signal_consumers[bit]) {
 876                                 log_assert(fwd_ct.cell_known(pbit.cell->type));
 877                                 if ((pbit.cell->type == "$mux" || pbit.cell->type == "$pmux") && (pbit.port == "\\A" || pbit.port == "\\B"))
 878                                         driven_data_muxes.insert(pbit.cell);
 879                                 else
 880                                         driven_cells.insert(pbit.cell);
 881                         }
 882                 }
 883
 884                 recursion_state.insert(cell);
 885
 886                 for (auto c : driven_data_muxes)
 887                 {
 888                         const pool<ssc_pair_t> &c_patterns = find_cell_activation_patterns(c, indent);
 889
 890                         bool used_in_a = false;
 891                         std::set<int> used_in_b_parts;
 892
 893                         int width = c->parameters.at("\\WIDTH").as_int();
 894                         std::vector<RTLIL::SigBit> sig_a = modwalker.sigmap(c->getPort("\\A"));
 895                         std::vector<RTLIL::SigBit> sig_b = modwalker.sigmap(c->getPort("\\B"));
 896                         std::vector<RTLIL::SigBit> sig_s = modwalker.sigmap(c->getPort("\\S"));
 897
 898                         for (auto &bit : sig_a)
 899                                 if (cell_out_bits.count(bit))
 900                                         used_in_a = true;
 901
 902                         for (int i = 0; i < GetSize(sig_b); i++)
 903                                 if (cell_out_bits.count(sig_b[i]))
 904                                         used_in_b_parts.insert(i / width);
 905
 906                         if (used_in_a)
 907                                 for (auto p : c_patterns) {
 908                                         for (int i = 0; i < GetSize(sig_s); i++)
 909                                                 p.first.append_bit(sig_s[i]), p.second.bits.push_back(RTLIL::State::S0);
 910                                         if (sort_check_activation_pattern(p))
 911                                                 activation_patterns_cache[cell].insert(p);
 912                                 }
 913
 914                         for (int idx : used_in_b_parts)
 915                                 for (auto p : c_patterns) {
 916                                         p.first.append_bit(sig_s[idx]), p.second.bits.push_back(RTLIL::State::S1);
 917                                         if (sort_check_activation_pattern(p))
 918                                                 activation_patterns_cache[cell].insert(p);
 919                                 }
 920                 }
 921
 922                 for (auto c : driven_cells) {
 923                         const pool<ssc_pair_t> &c_patterns = find_cell_activation_patterns(c, indent);
 924                         activation_patterns_cache[cell].insert(c_patterns.begin(), c_patterns.end());
 925                 }
 926
 927                 log_assert(recursion_state.count(cell) != 0);
 928                 recursion_state.erase(cell);
 929
 930                 optimize_activation_patterns(activation_patterns_cache[cell]);
 931                 if (activation_patterns_cache[cell].empty()) {
 932                         log("%sFound cell that is never activated: %s\n", indent, log_id(cell));
 933                         RTLIL::SigSpec cell_outputs = modwalker.cell_outputs[cell];
 934                         module->connect(RTLIL::SigSig(cell_outputs, RTLIL::SigSpec(RTLIL::State::Sx, cell_outputs.size())));
 935                         cells_to_remove.insert(cell);
 936                 }
 937
 938                 return activation_patterns_cache[cell];
 939         }
 940
 941         RTLIL::SigSpec bits_from_activation_patterns(const pool<ssc_pair_t> &activation_patterns)
 942         {
 943                 std::set<RTLIL::SigBit> all_bits;
 944                 for (auto &it : activation_patterns) {
 945                         std::vector<RTLIL::SigBit> bits = it.first;
 946                         all_bits.insert(bits.begin(), bits.end());
 947                 }
 948
 949                 RTLIL::SigSpec signal;
 950                 for (auto &bit : all_bits)
 951                         signal.append_bit(bit);
 952
 953                 return signal;
 954         }
 955
 956         void filter_activation_patterns(pool<ssc_pair_t> &out,
 957                         const pool<ssc_pair_t> &in, const std::set<RTLIL::SigBit> &filter_bits)
 958         {
 959                 for (auto &p : in)
 960                 {
 961                         std::vector<RTLIL::SigBit> p_first = p.first;
 962                         ssc_pair_t new_p;
 963
 964                         for (int i = 0; i < GetSize(p_first); i++)
 965                                 if (filter_bits.count(p_first[i]) == 0) {
 966                                         new_p.first.append_bit(p_first[i]);
 967                                         new_p.second.bits.push_back(p.second.bits.at(i));
 968                                 }
 969
 970                         out.insert(new_p);
 971                 }
 972         }
 973
 974         RTLIL::SigSpec make_cell_activation_logic(const pool<ssc_pair_t> &activation_patterns, pool<RTLIL::Cell*> &supercell_aux)
 975         {
 976                 RTLIL::Wire *all_cases_wire = module->addWire(NEW_ID, 0);
 977
 978                 for (auto &p : activation_patterns) {
 979                         all_cases_wire->width++;
 980                         supercell_aux.insert(module->addEq(NEW_ID, p.first, p.second, RTLIL::SigSpec(all_cases_wire, all_cases_wire->width - 1)));
 981                 }
 982
 983                 if (all_cases_wire->width == 1)
 984                         return all_cases_wire;
 985
 986                 RTLIL::Wire *result_wire = module->addWire(NEW_ID);
 987                 supercell_aux.insert(module->addReduceOr(NEW_ID, all_cases_wire, result_wire));
 988                 return result_wire;
 989         }
 990
 991
 992         // -------------------------------------------------------------------------------------
 993         // Helper functions used to make sure that this pass does not introduce new logic loops.
 994         // -------------------------------------------------------------------------------------
 995
 996         bool module_has_scc()
 997         {
 998                 CellTypes ct;
 999                 ct.setup_internals();
1000                 ct.setup_stdcells();
1001
1002                 TopoSort<RTLIL::Cell*, cell_ptr_cmp> toposort;
1003                 toposort.analyze_loops = false;
1004
1005                 topo_sigmap.set(module);
1006                 topo_bit_drivers.clear();
1007
1008                 dict<RTLIL::Cell*, pool<RTLIL::SigBit>> cell_to_bits;
1009                 dict<RTLIL::SigBit, pool<RTLIL::Cell*>> bit_to_cells;
1010
1011                 for (auto cell : module->cells())
1012                         if (ct.cell_known(cell->type))
1013                                 for (auto &conn : cell->connections()) {
1014                                         if (ct.cell_output(cell->type, conn.first))
1015                                                 for (auto bit : topo_sigmap(conn.second)) {
1016                                                         cell_to_bits[cell].insert(bit);
1017                                                         topo_bit_drivers[bit].insert(cell);
1018                                                 }
1019                                         else
1020                                                 for (auto bit : topo_sigmap(conn.second))
1021                                                         bit_to_cells[bit].insert(cell);
1022                                 }
1023
1024                 for (auto &it : cell_to_bits)
1025                 {
1026                         RTLIL::Cell *c1 = it.first;
1027
1028                         for (auto bit : it.second)
1029                         for (auto c2 : bit_to_cells[bit])
1030                                 toposort.edge(c1, c2);
1031                 }
1032
1033                 bool found_scc = !toposort.sort();
1034                 topo_cell_drivers = std::move(toposort.database);
1035
1036                 if (found_scc && toposort.analyze_loops)
1037                         for (auto &loop : toposort.loops) {
1038                                 log("### loop ###\n");
1039                                 for (auto &c : loop)
1040                                         log("%s (%s)\n", log_id(c), log_id(c->type));
1041                         }
1042
1043                 return found_scc;
1044         }
1045
1046         bool find_in_input_cone_worker(RTLIL::Cell *root, RTLIL::Cell *needle, pool<RTLIL::Cell*> &stop)
1047         {
1048                 if (root == needle)
1049                         return true;
1050
1051                 if (stop.count(root))
1052                         return false;
1053
1054                 stop.insert(root);
1055
1056                 for (auto c : topo_cell_drivers[root])
1057                         if (find_in_input_cone_worker(c, needle, stop))
1058                                 return true;
1059                 return false;
1060         }
1061
1062         bool find_in_input_cone(RTLIL::Cell *root, RTLIL::Cell *needle)
1063         {
1064                 pool<RTLIL::Cell*> stop;
1065                 return find_in_input_cone_worker(root, needle, stop);
1066         }
1067
1068         bool is_part_of_scc(RTLIL::Cell *cell)
1069         {
1070                 CellTypes ct;
1071                 ct.setup_internals();
1072                 ct.setup_stdcells();
1073
1074                 pool<RTLIL::Cell*> queue, covered;
1075                 queue.insert(cell);
1076
1077                 while (!queue.empty())
1078                 {
1079                         pool<RTLIL::Cell*> new_queue;
1080
1081                         for (auto c : queue) {
1082                                 if (!ct.cell_known(c->type))
1083                                         continue;
1084                                 for (auto &conn : c->connections())
1085                                         if (ct.cell_input(c->type, conn.first))
1086                                                 for (auto bit : conn.second)
1087                                                         for (auto &pi : mi.query_ports(bit))
1088                                                                 if (ct.cell_known(pi.cell->type) && ct.cell_output(pi.cell->type, pi.port))
1089                                                                         new_queue.insert(pi.cell);
1090                                 covered.insert(c);
1091                         }
1092
1093                         queue.clear();
1094                         for (auto c : new_queue) {
1095                                 if (cells_to_remove.count(c))
1096                                         continue;
1097                                 if (c == cell)
1098                                         return true;
1099                                 if (!covered.count(c))
1100                                         queue.insert(c);
1101                         }
1102                 }
1103
1104                 return false;
1105         }
1106
1107
1108         // -------------
1109         // Setup and run
1110         // -------------
1111
1112         void remove_cell(Cell *cell)
1113         {
1114                 shareable_cells.erase(cell);
1115                 forbidden_controls_cache.erase(cell);
1116                 activation_patterns_cache.erase(cell);
1117                 module->remove(cell);
1118         }
1119
1120         ShareWorker(ShareWorkerConfig config, RTLIL::Design *design, RTLIL::Module *module) :
1121                         config(config), design(design), module(module), mi(module)
1122         {
1123         #ifndef NDEBUG
1124                 bool before_scc = module_has_scc();
1125         #endif
1126
1127                 generic_ops.insert(config.generic_uni_ops.begin(), config.generic_uni_ops.end());
1128                 generic_ops.insert(config.generic_bin_ops.begin(), config.generic_bin_ops.end());
1129                 generic_ops.insert(config.generic_cbin_ops.begin(), config.generic_cbin_ops.end());
1130                 generic_ops.insert(config.generic_other_ops.begin(), config.generic_other_ops.end());
1131
1132                 fwd_ct.setup_internals();
1133
1134                 cone_ct.setup_internals();
1135                 cone_ct.cell_types.erase("$mul");
1136                 cone_ct.cell_types.erase("$mod");
1137                 cone_ct.cell_types.erase("$div");
1138                 cone_ct.cell_types.erase("$pow");
1139                 cone_ct.cell_types.erase("$shl");
1140                 cone_ct.cell_types.erase("$shr");
1141                 cone_ct.cell_types.erase("$sshl");
1142                 cone_ct.cell_types.erase("$sshr");
1143
1144                 modwalker.setup(design, module);
1145
1146                 find_terminal_bits();
1147                 find_shareable_cells();
1148
1149                 if (shareable_cells.size() < 2)
1150                         return;
1151
1152                 log("Found %d cells in module %s that may be considered for resource sharing.\n",
1153                                 GetSize(shareable_cells), log_id(module));
1154
1155                 for (auto cell : module->cells())
1156                         if (cell->type == "$pmux")
1157                                 for (auto bit : cell->getPort("\\S"))
1158                                 for (auto other_bit : cell->getPort("\\S"))
1159                                         if (bit < other_bit)
1160                                                 exclusive_ctrls.push_back(std::pair<RTLIL::SigBit, RTLIL::SigBit>(bit, other_bit));
1161
1162                 while (!shareable_cells.empty() && config.limit != 0)
1163                 {
1164                         RTLIL::Cell *cell = *shareable_cells.begin();
1165                         shareable_cells.erase(cell);
1166
1167                         log("  Analyzing resource sharing options for %s (%s):\n", log_id(cell), log_id(cell->type));
1168
1169                         const pool<ssc_pair_t> &cell_activation_patterns = find_cell_activation_patterns(cell, "    ");
1170                         RTLIL::SigSpec cell_activation_signals = bits_from_activation_patterns(cell_activation_patterns);
1171
1172                         if (cell_activation_patterns.empty()) {
1173                                 log("    Cell is never active. Sharing is pointless, we simply remove it.\n");
1174                                 cells_to_remove.insert(cell);
1175                                 continue;
1176                         }
1177
1178                         if (cell_activation_patterns.count(ssc_pair_t())) {
1179                                 log("    Cell is always active. Therefore no sharing is possible.\n");
1180                                 continue;
1181                         }
1182
1183                         log("    Found %d activation_patterns using ctrl signal %s.\n", GetSize(cell_activation_patterns), log_signal(cell_activation_signals));
1184
1185                         std::vector<RTLIL::Cell*> candidates;
1186                         find_shareable_partners(candidates, cell);
1187
1188                         if (candidates.empty()) {
1189                                 log("    No candidates found.\n");
1190                                 continue;
1191                         }
1192
1193                         log("    Found %d candidates:", GetSize(candidates));
1194                         for (auto c : candidates)
1195                                 log(" %s", log_id(c));
1196                         log("\n");
1197
1198                         for (auto other_cell : candidates)
1199                         {
1200                                 log("    Analyzing resource sharing with %s (%s):\n", log_id(other_cell), log_id(other_cell->type));
1201
1202                                 const pool<ssc_pair_t> &other_cell_activation_patterns = find_cell_activation_patterns(other_cell, "      ");
1203                                 RTLIL::SigSpec other_cell_activation_signals = bits_from_activation_patterns(other_cell_activation_patterns);
1204
1205                                 if (other_cell_activation_patterns.empty()) {
1206                                         log("      Cell is never active. Sharing is pointless, we simply remove it.\n");
1207                                         shareable_cells.erase(other_cell);
1208                                         cells_to_remove.insert(other_cell);
1209                                         continue;
1210                                 }
1211
1212                                 if (other_cell_activation_patterns.count(ssc_pair_t())) {
1213                                         log("      Cell is always active. Therefore no sharing is possible.\n");
1214                                         shareable_cells.erase(other_cell);
1215                                         continue;
1216                                 }
1217
1218                                 log("      Found %d activation_patterns using ctrl signal %s.\n",
1219                                                 GetSize(other_cell_activation_patterns), log_signal(other_cell_activation_signals));
1220
1221                                 const pool<RTLIL::SigBit> &cell_forbidden_controls = find_forbidden_controls(cell);
1222                                 const pool<RTLIL::SigBit> &other_cell_forbidden_controls = find_forbidden_controls(other_cell);
1223
1224                                 std::set<RTLIL::SigBit> union_forbidden_controls;
1225                                 union_forbidden_controls.insert(cell_forbidden_controls.begin(), cell_forbidden_controls.end());
1226                                 union_forbidden_controls.insert(other_cell_forbidden_controls.begin(), other_cell_forbidden_controls.end());
1227
1228                                 if (!union_forbidden_controls.empty())
1229                                         log("      Forbidden control signals for this pair of cells: %s\n", log_signal(union_forbidden_controls));
1230
1231                                 pool<ssc_pair_t> filtered_cell_activation_patterns;
1232                                 pool<ssc_pair_t> filtered_other_cell_activation_patterns;
1233
1234                                 filter_activation_patterns(filtered_cell_activation_patterns, cell_activation_patterns, union_forbidden_controls);
1235                                 filter_activation_patterns(filtered_other_cell_activation_patterns, other_cell_activation_patterns, union_forbidden_controls);
1236
1237                                 optimize_activation_patterns(filtered_cell_activation_patterns);
1238                                 optimize_activation_patterns(filtered_other_cell_activation_patterns);
1239
1240                                 ezSatPtr ez;
1241                                 SatGen satgen(ez.get(), &modwalker.sigmap);
1242
1243                                 pool<RTLIL::Cell*> sat_cells;
1244                                 std::set<RTLIL::SigBit> bits_queue;
1245
1246                                 std::vector<int> cell_active, other_cell_active;
1247                                 RTLIL::SigSpec all_ctrl_signals;
1248
1249                                 for (auto &p : filtered_cell_activation_patterns) {
1250                                         log("      Activation pattern for cell %s: %s = %s\n", log_id(cell), log_signal(p.first), log_signal(p.second));
1251                                         cell_active.push_back(ez->vec_eq(satgen.importSigSpec(p.first), satgen.importSigSpec(p.second)));
1252                                         all_ctrl_signals.append(p.first);
1253                                 }
1254
1255                                 for (auto &p : filtered_other_cell_activation_patterns) {
1256                                         log("      Activation pattern for cell %s: %s = %s\n", log_id(other_cell), log_signal(p.first), log_signal(p.second));
1257                                         other_cell_active.push_back(ez->vec_eq(satgen.importSigSpec(p.first), satgen.importSigSpec(p.second)));
1258                                         all_ctrl_signals.append(p.first);
1259                                 }
1260
1261                                 for (auto &bit : cell_activation_signals.to_sigbit_vector())
1262                                         bits_queue.insert(bit);
1263
1264                                 for (auto &bit : other_cell_activation_signals.to_sigbit_vector())
1265                                         bits_queue.insert(bit);
1266
1267                                 while (!bits_queue.empty())
1268                                 {
1269                                         pool<ModWalker::PortBit> portbits;
1270                                         modwalker.get_drivers(portbits, bits_queue);
1271                                         bits_queue.clear();
1272
1273                                         for (auto &pbit : portbits)
1274                                                 if (sat_cells.count(pbit.cell) == 0 && cone_ct.cell_known(pbit.cell->type)) {
1275                                                         if (config.opt_fast && modwalker.cell_outputs[pbit.cell].size() >= 4)
1276                                                                 continue;
1277                                                         // log("      Adding cell %s (%s) to SAT problem.\n", log_id(pbit.cell), log_id(pbit.cell->type));
1278                                                         bits_queue.insert(modwalker.cell_inputs[pbit.cell].begin(), modwalker.cell_inputs[pbit.cell].end());
1279                                                         satgen.importCell(pbit.cell);
1280                                                         sat_cells.insert(pbit.cell);
1281                                                 }
1282
1283                                         if (config.opt_fast && sat_cells.size() > 100)
1284                                                 break;
1285                                 }
1286
1287                                 for (auto it : exclusive_ctrls)
1288                                         if (satgen.importedSigBit(it.first) && satgen.importedSigBit(it.second)) {
1289                                                 log("      Adding exclusive control bits: %s vs. %s\n", log_signal(it.first), log_signal(it.second));
1290                                                 int sub1 = satgen.importSigBit(it.first);
1291                                                 int sub2 = satgen.importSigBit(it.second);
1292                                                 ez->assume(ez->NOT(ez->AND(sub1, sub2)));
1293                                         }
1294
1295                                 if (!ez->solve(ez->expression(ez->OpOr, cell_active))) {
1296                                         log("      According to the SAT solver the cell %s is never active. Sharing is pointless, we simply remove it.\n", log_id(cell));
1297                                         cells_to_remove.insert(cell);
1298                                         break;
1299                                 }
1300
1301                                 if (!ez->solve(ez->expression(ez->OpOr, other_cell_active))) {
1302                                         log("      According to the SAT solver the cell %s is never active. Sharing is pointless, we simply remove it.\n", log_id(other_cell));
1303                                         cells_to_remove.insert(other_cell);
1304                                         shareable_cells.erase(other_cell);
1305                                         continue;
1306                                 }
1307
1308                                 ez->non_incremental();
1309
1310                                 all_ctrl_signals.sort_and_unify();
1311                                 std::vector<int> sat_model = satgen.importSigSpec(all_ctrl_signals);
1312                                 std::vector<bool> sat_model_values;
1313
1314                                 int sub1 = ez->expression(ez->OpOr, cell_active);
1315                                 int sub2 = ez->expression(ez->OpOr, other_cell_active);
1316                                 ez->assume(ez->AND(sub1, sub2));
1317
1318                                 log("      Size of SAT problem: %d cells, %d variables, %d clauses\n",
1319                                                 GetSize(sat_cells), ez->numCnfVariables(), ez->numCnfClauses());
1320
1321                                 if (ez->solve(sat_model, sat_model_values)) {
1322                                         log("      According to the SAT solver this pair of cells can not be shared.\n");
1323                                         log("      Model from SAT solver: %s = %d'", log_signal(all_ctrl_signals), GetSize(sat_model_values));
1324                                         for (int i = GetSize(sat_model_values)-1; i >= 0; i--)
1325                                                 log("%c", sat_model_values[i] ? '1' : '0');
1326                                         log("\n");
1327                                         continue;
1328                                 }
1329
1330                                 log("      According to the SAT solver this pair of cells can be shared.\n");
1331
1332                                 if (find_in_input_cone(cell, other_cell)) {
1333                                         log("      Sharing not possible: %s is in input cone of %s.\n", log_id(other_cell), log_id(cell));
1334                                         continue;
1335                                 }
1336
1337                                 if (find_in_input_cone(other_cell, cell)) {
1338                                         log("      Sharing not possible: %s is in input cone of %s.\n", log_id(cell), log_id(other_cell));
1339                                         continue;
1340                                 }
1341
1342                                 shareable_cells.erase(other_cell);
1343
1344                                 int cell_select_score = 0;
1345                                 int other_cell_select_score = 0;
1346
1347                                 for (auto &p : filtered_cell_activation_patterns)
1348                                         cell_select_score += p.first.size();
1349
1350                                 for (auto &p : filtered_other_cell_activation_patterns)
1351                                         other_cell_select_score += p.first.size();
1352
1353                                 RTLIL::Cell *supercell;
1354                                 pool<RTLIL::Cell*> supercell_aux;
1355                                 if (cell_select_score <= other_cell_select_score) {
1356                                         RTLIL::SigSpec act = make_cell_activation_logic(filtered_cell_activation_patterns, supercell_aux);
1357                                         supercell = make_supercell(cell, other_cell, act, supercell_aux);
1358                                         log("      Activation signal for %s: %s\n", log_id(cell), log_signal(act));
1359                                 } else {
1360                                         RTLIL::SigSpec act = make_cell_activation_logic(filtered_other_cell_activation_patterns, supercell_aux);
1361                                         supercell = make_supercell(other_cell, cell, act, supercell_aux);
1362                                         log("      Activation signal for %s: %s\n", log_id(other_cell), log_signal(act));
1363                                 }
1364
1365                                 log("      New cell: %s (%s)\n", log_id(supercell), log_id(supercell->type));
1366
1367                                 cells_to_remove.insert(cell);
1368                                 cells_to_remove.insert(other_cell);
1369
1370                                 for (auto c : supercell_aux)
1371                                         if (is_part_of_scc(c))
1372                                                 goto do_rollback;
1373
1374                                 if (0) {
1375                         do_rollback:
1376                                         log("      New topology contains loops! Rolling back..\n");
1377                                         cells_to_remove.erase(cell);
1378                                         cells_to_remove.erase(other_cell);
1379                                         shareable_cells.insert(other_cell);
1380                                         for (auto cc : supercell_aux)
1381                                                 remove_cell(cc);
1382                                         continue;
1383                                 }
1384
1385                                 pool<ssc_pair_t> supercell_activation_patterns;
1386                                 supercell_activation_patterns.insert(filtered_cell_activation_patterns.begin(), filtered_cell_activation_patterns.end());
1387                                 supercell_activation_patterns.insert(filtered_other_cell_activation_patterns.begin(), filtered_other_cell_activation_patterns.end());
1388                                 optimize_activation_patterns(supercell_activation_patterns);
1389                                 activation_patterns_cache[supercell] = supercell_activation_patterns;
1390                                 shareable_cells.insert(supercell);
1391
1392                                 for (auto bit : topo_sigmap(all_ctrl_signals))
1393                                         for (auto c : topo_bit_drivers[bit])
1394                                                 topo_cell_drivers[supercell].insert(c);
1395
1396                                 topo_cell_drivers[supercell].insert(topo_cell_drivers[cell].begin(), topo_cell_drivers[cell].end());
1397                                 topo_cell_drivers[supercell].insert(topo_cell_drivers[other_cell].begin(), topo_cell_drivers[other_cell].end());
1398
1399                                 topo_cell_drivers[cell] = { supercell };
1400                                 topo_cell_drivers[other_cell] = { supercell };
1401
1402                                 if (config.limit > 0)
1403                                         config.limit--;
1404
1405                                 break;
1406                         }
1407                 }
1408
1409                 if (!cells_to_remove.empty()) {
1410                         log("Removing %d cells in module %s:\n", GetSize(cells_to_remove), log_id(module));
1411                         for (auto c : cells_to_remove) {
1412                                 log("  Removing cell %s (%s).\n", log_id(c), log_id(c->type));
1413                                 remove_cell(c);
1414                         }
1415                 }
1416
1417                 log_assert(recursion_state.empty());
1418
1419         #ifndef NDEBUG
1420                 bool after_scc = before_scc || module_has_scc();
1421                 log_assert(before_scc == after_scc);
1422         #endif
1423         }
1424 };
1425
1426 struct SharePass : public Pass {
1427         SharePass() : Pass("share", "perform sat-based resource sharing") { }
1428         void help() YS_OVERRIDE
1429         {
1430                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
1431                 log("\n");
1432                 log("    share [options] [selection]\n");
1433                 log("\n");
1434                 log("This pass merges shareable resources into a single resource. A SAT solver\n");
1435                 log("is used to determine if two resources are share-able.\n");
1436                 log("\n");
1437                 log("  -force\n");
1438                 log("    Per default the selection of cells that is considered for sharing is\n");
1439                 log("    narrowed using a list of cell types. With this option all selected\n");
1440                 log("    cells are considered for resource sharing.\n");
1441                 log("\n");
1442                 log("    IMPORTANT NOTE: If the -all option is used then no cells with internal\n");
1443                 log("    state must be selected!\n");
1444                 log("\n");
1445                 log("  -aggressive\n");
1446                 log("    Per default some heuristics are used to reduce the number of cells\n");
1447                 log("    considered for resource sharing to only large resources. This options\n");
1448                 log("    turns this heuristics off, resulting in much more cells being considered\n");
1449                 log("    for resource sharing.\n");
1450                 log("\n");
1451                 log("  -fast\n");
1452                 log("    Only consider the simple part of the control logic in SAT solving, resulting\n");
1453                 log("    in much easier SAT problems at the cost of maybe missing some opportunities\n");
1454                 log("    for resource sharing.\n");
1455                 log("\n");
1456                 log("  -limit N\n");
1457                 log("    Only perform the first N merges, then stop. This is useful for debugging.\n");
1458                 log("\n");
1459         }
1460         void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
1461         {
1462                 ShareWorkerConfig config;
1463
1464                 config.limit = -1;
1465                 config.opt_force = false;
1466                 config.opt_aggressive = false;
1467                 config.opt_fast = false;
1468
1469                 config.generic_uni_ops.insert("$not");
1470                 // config.generic_uni_ops.insert("$pos");
1471                 config.generic_uni_ops.insert("$neg");
1472
1473                 config.generic_cbin_ops.insert("$and");
1474                 config.generic_cbin_ops.insert("$or");
1475                 config.generic_cbin_ops.insert("$xor");
1476                 config.generic_cbin_ops.insert("$xnor");
1477
1478                 config.generic_bin_ops.insert("$shl");
1479                 config.generic_bin_ops.insert("$shr");
1480                 config.generic_bin_ops.insert("$sshl");
1481                 config.generic_bin_ops.insert("$sshr");
1482
1483                 config.generic_bin_ops.insert("$lt");
1484                 config.generic_bin_ops.insert("$le");
1485                 config.generic_bin_ops.insert("$eq");
1486                 config.generic_bin_ops.insert("$ne");
1487                 config.generic_bin_ops.insert("$eqx");
1488                 config.generic_bin_ops.insert("$nex");
1489                 config.generic_bin_ops.insert("$ge");
1490                 config.generic_bin_ops.insert("$gt");
1491
1492                 config.generic_cbin_ops.insert("$add");
1493                 config.generic_cbin_ops.insert("$mul");
1494
1495                 config.generic_bin_ops.insert("$sub");
1496                 config.generic_bin_ops.insert("$div");
1497                 config.generic_bin_ops.insert("$mod");
1498                 // config.generic_bin_ops.insert("$pow");
1499
1500                 config.generic_uni_ops.insert("$logic_not");
1501                 config.generic_cbin_ops.insert("$logic_and");
1502                 config.generic_cbin_ops.insert("$logic_or");
1503
1504                 config.generic_other_ops.insert("$alu");
1505                 config.generic_other_ops.insert("$macc");
1506
1507                 log_header(design, "Executing SHARE pass (SAT-based resource sharing).\n");
1508
1509                 size_t argidx;
1510                 for (argidx = 1; argidx < args.size(); argidx++) {
1511                         if (args[argidx] == "-force") {
1512                                 config.opt_force = true;
1513                                 continue;
1514                         }
1515                         if (args[argidx] == "-aggressive") {
1516                                 config.opt_aggressive = true;
1517                                 continue;
1518                         }
1519                         if (args[argidx] == "-fast") {
1520                                 config.opt_fast = true;
1521                                 continue;
1522                         }
1523                         if (args[argidx] == "-limit" && argidx+1 < args.size()) {
1524                                 config.limit = atoi(args[++argidx].c_str());
1525                                 continue;
1526                         }
1527                         break;
1528                 }
1529                 extra_args(args, argidx, design);
1530
1531                 for (auto &mod_it : design->modules_)
1532                         if (design->selected(mod_it.second))
1533                                 ShareWorker(config, design, mod_it.second);
1534         }
1535 } SharePass;
1536
1537 PRIVATE_NAMESPACE_END