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 (addr1 != addr2)
 714                                 supercell->setPort("\\ADDR", module->Mux(NEW_ID, addr2, addr1, act));
 715                         supercell_aux.insert(module->addPos(NEW_ID, supercell->getPort("\\DATA"), c2->getPort("\\DATA")));
 716                         supercell_aux.insert(supercell);
 717                         return supercell;
 718                 }
 719
 720                 log_abort();
 721         }
 722
 723
 724         // -------------------------------------------
 725         // Finding forbidden control inputs for a cell
 726         // -------------------------------------------
 727
 728         std::map<RTLIL::Cell*, pool<RTLIL::SigBit>, cell_ptr_cmp> forbidden_controls_cache;
 729
 730         const pool<RTLIL::SigBit> &find_forbidden_controls(RTLIL::Cell *cell)
 731         {
 732                 if (recursion_state.count(cell)) {
 733                         static pool<RTLIL::SigBit> empty_controls_set;
 734                         return empty_controls_set;
 735                 }
 736
 737                 if (forbidden_controls_cache.count(cell))
 738                         return forbidden_controls_cache.at(cell);
 739
 740                 pool<ModWalker::PortBit> pbits;
 741                 pool<RTLIL::Cell*> consumer_cells;
 742
 743                 modwalker.get_consumers(pbits, modwalker.cell_outputs[cell]);
 744
 745                 for (auto &bit : pbits) {
 746                         if ((bit.cell->type == "$mux" || bit.cell->type == "$pmux") && bit.port == "\\S")
 747                                 forbidden_controls_cache[cell].insert(bit.cell->getPort("\\S").extract(bit.offset, 1));
 748                         consumer_cells.insert(bit.cell);
 749                 }
 750
 751                 recursion_state.insert(cell);
 752
 753                 for (auto c : consumer_cells)
 754                         if (fwd_ct.cell_known(c->type)) {
 755                                 const pool<RTLIL::SigBit> &bits = find_forbidden_controls(c);
 756                                 forbidden_controls_cache[cell].insert(bits.begin(), bits.end());
 757                         }
 758
 759                 log_assert(recursion_state.count(cell) != 0);
 760                 recursion_state.erase(cell);
 761
 762                 return forbidden_controls_cache[cell];
 763         }
 764
 765
 766         // --------------------------------------------------------
 767         // Finding control inputs and activation pattern for a cell
 768         // --------------------------------------------------------
 769
 770         std::map<RTLIL::Cell*, pool<ssc_pair_t>, cell_ptr_cmp> activation_patterns_cache;
 771
 772         bool sort_check_activation_pattern(ssc_pair_t &p)
 773         {
 774                 std::map<RTLIL::SigBit, RTLIL::State> p_bits;
 775
 776                 std::vector<RTLIL::SigBit> p_first_bits = p.first;
 777                 for (int i = 0; i < GetSize(p_first_bits); i++) {
 778                         RTLIL::SigBit b = p_first_bits[i];
 779                         RTLIL::State v = p.second.bits[i];
 780                         if (p_bits.count(b) && p_bits.at(b) != v)
 781                                 return false;
 782                         p_bits[b] = v;
 783                 }
 784
 785                 p.first = RTLIL::SigSpec();
 786                 p.second.bits.clear();
 787
 788                 for (auto &it : p_bits) {
 789                         p.first.append_bit(it.first);
 790                         p.second.bits.push_back(it.second);
 791                 }
 792
 793                 return true;
 794         }
 795
 796         void optimize_activation_patterns(pool<ssc_pair_t> &patterns)
 797         {
 798                 // TODO: Remove patterns that are contained in other patterns
 799
 800                 dict<SigSpec, pool<Const>> db;
 801                 bool did_something = false;
 802
 803                 for (auto const &p : patterns)
 804                 {
 805                         auto &sig = p.first;
 806                         auto &val = p.second;
 807                         int len = GetSize(sig);
 808
 809                         for (int i = 0; i < len; i++)
 810                         {
 811                                 auto otherval = val;
 812
 813                                 if (otherval.bits[i] == State::S0)
 814                                         otherval.bits[i] = State::S1;
 815                                 else if (otherval.bits[i] == State::S1)
 816                                         otherval.bits[i] = State::S0;
 817                                 else
 818                                         continue;
 819
 820                                 if (db[sig].count(otherval))
 821                                 {
 822                                         auto newsig = sig;
 823                                         newsig.remove(i);
 824
 825                                         auto newval = val;
 826                                         newval.bits.erase(newval.bits.begin() + i);
 827
 828                                         db[newsig].insert(newval);
 829                                         db[sig].erase(otherval);
 830
 831                                         did_something = true;
 832                                         goto next_pattern;
 833                                 }
 834                         }
 835
 836                         db[sig].insert(val);
 837                 next_pattern:;
 838                 }
 839
 840                 if (!did_something)
 841                         return;
 842
 843                 patterns.clear();
 844                 for (auto &it : db)
 845                 for (auto &val : it.second)
 846                         patterns.insert(make_pair(it.first, val));
 847
 848                 optimize_activation_patterns(patterns);
 849         }
 850
 851         const pool<ssc_pair_t> &find_cell_activation_patterns(RTLIL::Cell *cell, const char *indent)
 852         {
 853                 if (recursion_state.count(cell)) {
 854                         static pool<ssc_pair_t> empty_patterns_set;
 855                         return empty_patterns_set;
 856                 }
 857
 858                 if (activation_patterns_cache.count(cell))
 859                         return activation_patterns_cache.at(cell);
 860
 861                 const pool<RTLIL::SigBit> &cell_out_bits = modwalker.cell_outputs[cell];
 862                 pool<RTLIL::Cell*> driven_cells, driven_data_muxes;
 863
 864                 for (auto &bit : cell_out_bits)
 865                 {
 866                         if (terminal_bits.count(bit)) {
 867                                 // Terminal cells are always active: unconditional activation pattern
 868                                 activation_patterns_cache[cell].insert(ssc_pair_t());
 869                                 return activation_patterns_cache.at(cell);
 870                         }
 871                         for (auto &pbit : modwalker.signal_consumers[bit]) {
 872                                 log_assert(fwd_ct.cell_known(pbit.cell->type));
 873                                 if ((pbit.cell->type == "$mux" || pbit.cell->type == "$pmux") && (pbit.port == "\\A" || pbit.port == "\\B"))
 874                                         driven_data_muxes.insert(pbit.cell);
 875                                 else
 876                                         driven_cells.insert(pbit.cell);
 877                         }
 878                 }
 879
 880                 recursion_state.insert(cell);
 881
 882                 for (auto c : driven_data_muxes)
 883                 {
 884                         const pool<ssc_pair_t> &c_patterns = find_cell_activation_patterns(c, indent);
 885
 886                         bool used_in_a = false;
 887                         std::set<int> used_in_b_parts;
 888
 889                         int width = c->parameters.at("\\WIDTH").as_int();
 890                         std::vector<RTLIL::SigBit> sig_a = modwalker.sigmap(c->getPort("\\A"));
 891                         std::vector<RTLIL::SigBit> sig_b = modwalker.sigmap(c->getPort("\\B"));
 892                         std::vector<RTLIL::SigBit> sig_s = modwalker.sigmap(c->getPort("\\S"));
 893
 894                         for (auto &bit : sig_a)
 895                                 if (cell_out_bits.count(bit))
 896                                         used_in_a = true;
 897
 898                         for (int i = 0; i < GetSize(sig_b); i++)
 899                                 if (cell_out_bits.count(sig_b[i]))
 900                                         used_in_b_parts.insert(i / width);
 901
 902                         if (used_in_a)
 903                                 for (auto p : c_patterns) {
 904                                         for (int i = 0; i < GetSize(sig_s); i++)
 905                                                 p.first.append_bit(sig_s[i]), p.second.bits.push_back(RTLIL::State::S0);
 906                                         if (sort_check_activation_pattern(p))
 907                                                 activation_patterns_cache[cell].insert(p);
 908                                 }
 909
 910                         for (int idx : used_in_b_parts)
 911                                 for (auto p : c_patterns) {
 912                                         p.first.append_bit(sig_s[idx]), p.second.bits.push_back(RTLIL::State::S1);
 913                                         if (sort_check_activation_pattern(p))
 914                                                 activation_patterns_cache[cell].insert(p);
 915                                 }
 916                 }
 917
 918                 for (auto c : driven_cells) {
 919                         const pool<ssc_pair_t> &c_patterns = find_cell_activation_patterns(c, indent);
 920                         activation_patterns_cache[cell].insert(c_patterns.begin(), c_patterns.end());
 921                 }
 922
 923                 log_assert(recursion_state.count(cell) != 0);
 924                 recursion_state.erase(cell);
 925
 926                 optimize_activation_patterns(activation_patterns_cache[cell]);
 927                 if (activation_patterns_cache[cell].empty()) {
 928                         log("%sFound cell that is never activated: %s\n", indent, log_id(cell));
 929                         RTLIL::SigSpec cell_outputs = modwalker.cell_outputs[cell];
 930                         module->connect(RTLIL::SigSig(cell_outputs, RTLIL::SigSpec(RTLIL::State::Sx, cell_outputs.size())));
 931                         cells_to_remove.insert(cell);
 932                 }
 933
 934                 return activation_patterns_cache[cell];
 935         }
 936
 937         RTLIL::SigSpec bits_from_activation_patterns(const pool<ssc_pair_t> &activation_patterns)
 938         {
 939                 std::set<RTLIL::SigBit> all_bits;
 940                 for (auto &it : activation_patterns) {
 941                         std::vector<RTLIL::SigBit> bits = it.first;
 942                         all_bits.insert(bits.begin(), bits.end());
 943                 }
 944
 945                 RTLIL::SigSpec signal;
 946                 for (auto &bit : all_bits)
 947                         signal.append_bit(bit);
 948
 949                 return signal;
 950         }
 951
 952         void filter_activation_patterns(pool<ssc_pair_t> &out,
 953                         const pool<ssc_pair_t> &in, const std::set<RTLIL::SigBit> &filter_bits)
 954         {
 955                 for (auto &p : in)
 956                 {
 957                         std::vector<RTLIL::SigBit> p_first = p.first;
 958                         ssc_pair_t new_p;
 959
 960                         for (int i = 0; i < GetSize(p_first); i++)
 961                                 if (filter_bits.count(p_first[i]) == 0) {
 962                                         new_p.first.append_bit(p_first[i]);
 963                                         new_p.second.bits.push_back(p.second.bits.at(i));
 964                                 }
 965
 966                         out.insert(new_p);
 967                 }
 968         }
 969
 970         RTLIL::SigSpec make_cell_activation_logic(const pool<ssc_pair_t> &activation_patterns, pool<RTLIL::Cell*> &supercell_aux)
 971         {
 972                 RTLIL::Wire *all_cases_wire = module->addWire(NEW_ID, 0);
 973
 974                 for (auto &p : activation_patterns) {
 975                         all_cases_wire->width++;
 976                         supercell_aux.insert(module->addEq(NEW_ID, p.first, p.second, RTLIL::SigSpec(all_cases_wire, all_cases_wire->width - 1)));
 977                 }
 978
 979                 if (all_cases_wire->width == 1)
 980                         return all_cases_wire;
 981
 982                 RTLIL::Wire *result_wire = module->addWire(NEW_ID);
 983                 supercell_aux.insert(module->addReduceOr(NEW_ID, all_cases_wire, result_wire));
 984                 return result_wire;
 985         }
 986
 987
 988         // -------------------------------------------------------------------------------------
 989         // Helper functions used to make sure that this pass does not introduce new logic loops.
 990         // -------------------------------------------------------------------------------------
 991
 992         bool module_has_scc()
 993         {
 994                 CellTypes ct;
 995                 ct.setup_internals();
 996                 ct.setup_stdcells();
 997
 998                 TopoSort<RTLIL::Cell*, cell_ptr_cmp> toposort;
 999                 toposort.analyze_loops = false;
1000
1001                 topo_sigmap.set(module);
1002                 topo_bit_drivers.clear();
1003
1004                 dict<RTLIL::Cell*, pool<RTLIL::SigBit>> cell_to_bits;
1005                 dict<RTLIL::SigBit, pool<RTLIL::Cell*>> bit_to_cells;
1006
1007                 for (auto cell : module->cells())
1008                         if (ct.cell_known(cell->type))
1009                                 for (auto &conn : cell->connections()) {
1010                                         if (ct.cell_output(cell->type, conn.first))
1011                                                 for (auto bit : topo_sigmap(conn.second)) {
1012                                                         cell_to_bits[cell].insert(bit);
1013                                                         topo_bit_drivers[bit].insert(cell);
1014                                                 }
1015                                         else
1016                                                 for (auto bit : topo_sigmap(conn.second))
1017                                                         bit_to_cells[bit].insert(cell);
1018                                 }
1019
1020                 for (auto &it : cell_to_bits)
1021                 {
1022                         RTLIL::Cell *c1 = it.first;
1023
1024                         for (auto bit : it.second)
1025                         for (auto c2 : bit_to_cells[bit])
1026                                 toposort.edge(c1, c2);
1027                 }
1028
1029                 bool found_scc = !toposort.sort();
1030                 topo_cell_drivers = std::move(toposort.database);
1031
1032                 if (found_scc && toposort.analyze_loops)
1033                         for (auto &loop : toposort.loops) {
1034                                 log("### loop ###\n");
1035                                 for (auto &c : loop)
1036                                         log("%s (%s)\n", log_id(c), log_id(c->type));
1037                         }
1038
1039                 return found_scc;
1040         }
1041
1042         bool find_in_input_cone_worker(RTLIL::Cell *root, RTLIL::Cell *needle, pool<RTLIL::Cell*> &stop)
1043         {
1044                 if (root == needle)
1045                         return true;
1046
1047                 if (stop.count(root))
1048                         return false;
1049
1050                 stop.insert(root);
1051
1052                 for (auto c : topo_cell_drivers[root])
1053                         if (find_in_input_cone_worker(c, needle, stop))
1054                                 return true;
1055                 return false;
1056         }
1057
1058         bool find_in_input_cone(RTLIL::Cell *root, RTLIL::Cell *needle)
1059         {
1060                 pool<RTLIL::Cell*> stop;
1061                 return find_in_input_cone_worker(root, needle, stop);
1062         }
1063
1064         bool is_part_of_scc(RTLIL::Cell *cell)
1065         {
1066                 CellTypes ct;
1067                 ct.setup_internals();
1068                 ct.setup_stdcells();
1069
1070                 pool<RTLIL::Cell*> queue, covered;
1071                 queue.insert(cell);
1072
1073                 while (!queue.empty())
1074                 {
1075                         pool<RTLIL::Cell*> new_queue;
1076
1077                         for (auto c : queue) {
1078                                 if (!ct.cell_known(c->type))
1079                                         continue;
1080                                 for (auto &conn : c->connections())
1081                                         if (ct.cell_input(c->type, conn.first))
1082                                                 for (auto bit : conn.second)
1083                                                         for (auto &pi : mi.query_ports(bit))
1084                                                                 if (ct.cell_known(pi.cell->type) && ct.cell_output(pi.cell->type, pi.port))
1085                                                                         new_queue.insert(pi.cell);
1086                                 covered.insert(c);
1087                         }
1088
1089                         queue.clear();
1090                         for (auto c : new_queue) {
1091                                 if (cells_to_remove.count(c))
1092                                         continue;
1093                                 if (c == cell)
1094                                         return true;
1095                                 if (!covered.count(c))
1096                                         queue.insert(c);
1097                         }
1098                 }
1099
1100                 return false;
1101         }
1102
1103
1104         // -------------
1105         // Setup and run
1106         // -------------
1107
1108         void remove_cell(Cell *cell)
1109         {
1110                 shareable_cells.erase(cell);
1111                 forbidden_controls_cache.erase(cell);
1112                 activation_patterns_cache.erase(cell);
1113                 module->remove(cell);
1114         }
1115
1116         ShareWorker(ShareWorkerConfig config, RTLIL::Design *design, RTLIL::Module *module) :
1117                         config(config), design(design), module(module), mi(module)
1118         {
1119         #ifndef NDEBUG
1120                 bool before_scc = module_has_scc();
1121         #endif
1122
1123                 generic_ops.insert(config.generic_uni_ops.begin(), config.generic_uni_ops.end());
1124                 generic_ops.insert(config.generic_bin_ops.begin(), config.generic_bin_ops.end());
1125                 generic_ops.insert(config.generic_cbin_ops.begin(), config.generic_cbin_ops.end());
1126                 generic_ops.insert(config.generic_other_ops.begin(), config.generic_other_ops.end());
1127
1128                 fwd_ct.setup_internals();
1129
1130                 cone_ct.setup_internals();
1131                 cone_ct.cell_types.erase("$mul");
1132                 cone_ct.cell_types.erase("$mod");
1133                 cone_ct.cell_types.erase("$div");
1134                 cone_ct.cell_types.erase("$pow");
1135                 cone_ct.cell_types.erase("$shl");
1136                 cone_ct.cell_types.erase("$shr");
1137                 cone_ct.cell_types.erase("$sshl");
1138                 cone_ct.cell_types.erase("$sshr");
1139
1140                 modwalker.setup(design, module);
1141
1142                 find_terminal_bits();
1143                 find_shareable_cells();
1144
1145                 if (shareable_cells.size() < 2)
1146                         return;
1147
1148                 log("Found %d cells in module %s that may be considered for resource sharing.\n",
1149                                 GetSize(shareable_cells), log_id(module));
1150
1151                 for (auto cell : module->cells())
1152                         if (cell->type == "$pmux")
1153                                 for (auto bit : cell->getPort("\\S"))
1154                                 for (auto other_bit : cell->getPort("\\S"))
1155                                         if (bit < other_bit)
1156                                                 exclusive_ctrls.push_back(std::pair<RTLIL::SigBit, RTLIL::SigBit>(bit, other_bit));
1157
1158                 while (!shareable_cells.empty() && config.limit != 0)
1159                 {
1160                         RTLIL::Cell *cell = *shareable_cells.begin();
1161                         shareable_cells.erase(cell);
1162
1163                         log("  Analyzing resource sharing options for %s (%s):\n", log_id(cell), log_id(cell->type));
1164
1165                         const pool<ssc_pair_t> &cell_activation_patterns = find_cell_activation_patterns(cell, "    ");
1166                         RTLIL::SigSpec cell_activation_signals = bits_from_activation_patterns(cell_activation_patterns);
1167
1168                         if (cell_activation_patterns.empty()) {
1169                                 log("    Cell is never active. Sharing is pointless, we simply remove it.\n");
1170                                 cells_to_remove.insert(cell);
1171                                 continue;
1172                         }
1173
1174                         if (cell_activation_patterns.count(ssc_pair_t())) {
1175                                 log("    Cell is always active. Therefore no sharing is possible.\n");
1176                                 continue;
1177                         }
1178
1179                         log("    Found %d activation_patterns using ctrl signal %s.\n", GetSize(cell_activation_patterns), log_signal(cell_activation_signals));
1180
1181                         std::vector<RTLIL::Cell*> candidates;
1182                         find_shareable_partners(candidates, cell);
1183
1184                         if (candidates.empty()) {
1185                                 log("    No candidates found.\n");
1186                                 continue;
1187                         }
1188
1189                         log("    Found %d candidates:", GetSize(candidates));
1190                         for (auto c : candidates)
1191                                 log(" %s", log_id(c));
1192                         log("\n");
1193
1194                         for (auto other_cell : candidates)
1195                         {
1196                                 log("    Analyzing resource sharing with %s (%s):\n", log_id(other_cell), log_id(other_cell->type));
1197
1198                                 const pool<ssc_pair_t> &other_cell_activation_patterns = find_cell_activation_patterns(other_cell, "      ");
1199                                 RTLIL::SigSpec other_cell_activation_signals = bits_from_activation_patterns(other_cell_activation_patterns);
1200
1201                                 if (other_cell_activation_patterns.empty()) {
1202                                         log("      Cell is never active. Sharing is pointless, we simply remove it.\n");
1203                                         shareable_cells.erase(other_cell);
1204                                         cells_to_remove.insert(other_cell);
1205                                         continue;
1206                                 }
1207
1208                                 if (other_cell_activation_patterns.count(ssc_pair_t())) {
1209                                         log("      Cell is always active. Therefore no sharing is possible.\n");
1210                                         shareable_cells.erase(other_cell);
1211                                         continue;
1212                                 }
1213
1214                                 log("      Found %d activation_patterns using ctrl signal %s.\n",
1215                                                 GetSize(other_cell_activation_patterns), log_signal(other_cell_activation_signals));
1216
1217                                 const pool<RTLIL::SigBit> &cell_forbidden_controls = find_forbidden_controls(cell);
1218                                 const pool<RTLIL::SigBit> &other_cell_forbidden_controls = find_forbidden_controls(other_cell);
1219
1220                                 std::set<RTLIL::SigBit> union_forbidden_controls;
1221                                 union_forbidden_controls.insert(cell_forbidden_controls.begin(), cell_forbidden_controls.end());
1222                                 union_forbidden_controls.insert(other_cell_forbidden_controls.begin(), other_cell_forbidden_controls.end());
1223
1224                                 if (!union_forbidden_controls.empty())
1225                                         log("      Forbidden control signals for this pair of cells: %s\n", log_signal(union_forbidden_controls));
1226
1227                                 pool<ssc_pair_t> filtered_cell_activation_patterns;
1228                                 pool<ssc_pair_t> filtered_other_cell_activation_patterns;
1229
1230                                 filter_activation_patterns(filtered_cell_activation_patterns, cell_activation_patterns, union_forbidden_controls);
1231                                 filter_activation_patterns(filtered_other_cell_activation_patterns, other_cell_activation_patterns, union_forbidden_controls);
1232
1233                                 optimize_activation_patterns(filtered_cell_activation_patterns);
1234                                 optimize_activation_patterns(filtered_other_cell_activation_patterns);
1235
1236                                 ezSatPtr ez;
1237                                 SatGen satgen(ez.get(), &modwalker.sigmap);
1238
1239                                 pool<RTLIL::Cell*> sat_cells;
1240                                 std::set<RTLIL::SigBit> bits_queue;
1241
1242                                 std::vector<int> cell_active, other_cell_active;
1243                                 RTLIL::SigSpec all_ctrl_signals;
1244
1245                                 for (auto &p : filtered_cell_activation_patterns) {
1246                                         log("      Activation pattern for cell %s: %s = %s\n", log_id(cell), log_signal(p.first), log_signal(p.second));
1247                                         cell_active.push_back(ez->vec_eq(satgen.importSigSpec(p.first), satgen.importSigSpec(p.second)));
1248                                         all_ctrl_signals.append(p.first);
1249                                 }
1250
1251                                 for (auto &p : filtered_other_cell_activation_patterns) {
1252                                         log("      Activation pattern for cell %s: %s = %s\n", log_id(other_cell), log_signal(p.first), log_signal(p.second));
1253                                         other_cell_active.push_back(ez->vec_eq(satgen.importSigSpec(p.first), satgen.importSigSpec(p.second)));
1254                                         all_ctrl_signals.append(p.first);
1255                                 }
1256
1257                                 for (auto &bit : cell_activation_signals.to_sigbit_vector())
1258                                         bits_queue.insert(bit);
1259
1260                                 for (auto &bit : other_cell_activation_signals.to_sigbit_vector())
1261                                         bits_queue.insert(bit);
1262
1263                                 while (!bits_queue.empty())
1264                                 {
1265                                         pool<ModWalker::PortBit> portbits;
1266                                         modwalker.get_drivers(portbits, bits_queue);
1267                                         bits_queue.clear();
1268
1269                                         for (auto &pbit : portbits)
1270                                                 if (sat_cells.count(pbit.cell) == 0 && cone_ct.cell_known(pbit.cell->type)) {
1271                                                         if (config.opt_fast && modwalker.cell_outputs[pbit.cell].size() >= 4)
1272                                                                 continue;
1273                                                         // log("      Adding cell %s (%s) to SAT problem.\n", log_id(pbit.cell), log_id(pbit.cell->type));
1274                                                         bits_queue.insert(modwalker.cell_inputs[pbit.cell].begin(), modwalker.cell_inputs[pbit.cell].end());
1275                                                         satgen.importCell(pbit.cell);
1276                                                         sat_cells.insert(pbit.cell);
1277                                                 }
1278
1279                                         if (config.opt_fast && sat_cells.size() > 100)
1280                                                 break;
1281                                 }
1282
1283                                 for (auto it : exclusive_ctrls)
1284                                         if (satgen.importedSigBit(it.first) && satgen.importedSigBit(it.second)) {
1285                                                 log("      Adding exclusive control bits: %s vs. %s\n", log_signal(it.first), log_signal(it.second));
1286                                                 int sub1 = satgen.importSigBit(it.first);
1287                                                 int sub2 = satgen.importSigBit(it.second);
1288                                                 ez->assume(ez->NOT(ez->AND(sub1, sub2)));
1289                                         }
1290
1291                                 if (!ez->solve(ez->expression(ez->OpOr, cell_active))) {
1292                                         log("      According to the SAT solver the cell %s is never active. Sharing is pointless, we simply remove it.\n", log_id(cell));
1293                                         cells_to_remove.insert(cell);
1294                                         break;
1295                                 }
1296
1297                                 if (!ez->solve(ez->expression(ez->OpOr, other_cell_active))) {
1298                                         log("      According to the SAT solver the cell %s is never active. Sharing is pointless, we simply remove it.\n", log_id(other_cell));
1299                                         cells_to_remove.insert(other_cell);
1300                                         shareable_cells.erase(other_cell);
1301                                         continue;
1302                                 }
1303
1304                                 ez->non_incremental();
1305
1306                                 all_ctrl_signals.sort_and_unify();
1307                                 std::vector<int> sat_model = satgen.importSigSpec(all_ctrl_signals);
1308                                 std::vector<bool> sat_model_values;
1309
1310                                 int sub1 = ez->expression(ez->OpOr, cell_active);
1311                                 int sub2 = ez->expression(ez->OpOr, other_cell_active);
1312                                 ez->assume(ez->AND(sub1, sub2));
1313
1314                                 log("      Size of SAT problem: %d cells, %d variables, %d clauses\n",
1315                                                 GetSize(sat_cells), ez->numCnfVariables(), ez->numCnfClauses());
1316
1317                                 if (ez->solve(sat_model, sat_model_values)) {
1318                                         log("      According to the SAT solver this pair of cells can not be shared.\n");
1319                                         log("      Model from SAT solver: %s = %d'", log_signal(all_ctrl_signals), GetSize(sat_model_values));
1320                                         for (int i = GetSize(sat_model_values)-1; i >= 0; i--)
1321                                                 log("%c", sat_model_values[i] ? '1' : '0');
1322                                         log("\n");
1323                                         continue;
1324                                 }
1325
1326                                 log("      According to the SAT solver this pair of cells can be shared.\n");
1327
1328                                 if (find_in_input_cone(cell, other_cell)) {
1329                                         log("      Sharing not possible: %s is in input cone of %s.\n", log_id(other_cell), log_id(cell));
1330                                         continue;
1331                                 }
1332
1333                                 if (find_in_input_cone(other_cell, cell)) {
1334                                         log("      Sharing not possible: %s is in input cone of %s.\n", log_id(cell), log_id(other_cell));
1335                                         continue;
1336                                 }
1337
1338                                 shareable_cells.erase(other_cell);
1339
1340                                 int cell_select_score = 0;
1341                                 int other_cell_select_score = 0;
1342
1343                                 for (auto &p : filtered_cell_activation_patterns)
1344                                         cell_select_score += p.first.size();
1345
1346                                 for (auto &p : filtered_other_cell_activation_patterns)
1347                                         other_cell_select_score += p.first.size();
1348
1349                                 RTLIL::Cell *supercell;
1350                                 pool<RTLIL::Cell*> supercell_aux;
1351                                 if (cell_select_score <= other_cell_select_score) {
1352                                         RTLIL::SigSpec act = make_cell_activation_logic(filtered_cell_activation_patterns, supercell_aux);
1353                                         supercell = make_supercell(cell, other_cell, act, supercell_aux);
1354                                         log("      Activation signal for %s: %s\n", log_id(cell), log_signal(act));
1355                                 } else {
1356                                         RTLIL::SigSpec act = make_cell_activation_logic(filtered_other_cell_activation_patterns, supercell_aux);
1357                                         supercell = make_supercell(other_cell, cell, act, supercell_aux);
1358                                         log("      Activation signal for %s: %s\n", log_id(other_cell), log_signal(act));
1359                                 }
1360
1361                                 log("      New cell: %s (%s)\n", log_id(supercell), log_id(supercell->type));
1362
1363                                 cells_to_remove.insert(cell);
1364                                 cells_to_remove.insert(other_cell);
1365
1366                                 for (auto c : supercell_aux)
1367                                         if (is_part_of_scc(c))
1368                                                 goto do_rollback;
1369
1370                                 if (0) {
1371                         do_rollback:
1372                                         log("      New topology contains loops! Rolling back..\n");
1373                                         cells_to_remove.erase(cell);
1374                                         cells_to_remove.erase(other_cell);
1375                                         shareable_cells.insert(other_cell);
1376                                         for (auto cc : supercell_aux)
1377                                                 remove_cell(cc);
1378                                         continue;
1379                                 }
1380
1381                                 pool<ssc_pair_t> supercell_activation_patterns;
1382                                 supercell_activation_patterns.insert(filtered_cell_activation_patterns.begin(), filtered_cell_activation_patterns.end());
1383                                 supercell_activation_patterns.insert(filtered_other_cell_activation_patterns.begin(), filtered_other_cell_activation_patterns.end());
1384                                 optimize_activation_patterns(supercell_activation_patterns);
1385                                 activation_patterns_cache[supercell] = supercell_activation_patterns;
1386                                 shareable_cells.insert(supercell);
1387
1388                                 for (auto bit : topo_sigmap(all_ctrl_signals))
1389                                         for (auto c : topo_bit_drivers[bit])
1390                                                 topo_cell_drivers[supercell].insert(c);
1391
1392                                 topo_cell_drivers[supercell].insert(topo_cell_drivers[cell].begin(), topo_cell_drivers[cell].end());
1393                                 topo_cell_drivers[supercell].insert(topo_cell_drivers[other_cell].begin(), topo_cell_drivers[other_cell].end());
1394
1395                                 topo_cell_drivers[cell] = { supercell };
1396                                 topo_cell_drivers[other_cell] = { supercell };
1397
1398                                 if (config.limit > 0)
1399                                         config.limit--;
1400
1401                                 break;
1402                         }
1403                 }
1404
1405                 if (!cells_to_remove.empty()) {
1406                         log("Removing %d cells in module %s:\n", GetSize(cells_to_remove), log_id(module));
1407                         for (auto c : cells_to_remove) {
1408                                 log("  Removing cell %s (%s).\n", log_id(c), log_id(c->type));
1409                                 remove_cell(c);
1410                         }
1411                 }
1412
1413                 log_assert(recursion_state.empty());
1414
1415         #ifndef NDEBUG
1416                 bool after_scc = before_scc || module_has_scc();
1417                 log_assert(before_scc == after_scc);
1418         #endif
1419         }
1420 };
1421
1422 struct SharePass : public Pass {
1423         SharePass() : Pass("share", "perform sat-based resource sharing") { }
1424         void help() YS_OVERRIDE
1425         {
1426                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
1427                 log("\n");
1428                 log("    share [options] [selection]\n");
1429                 log("\n");
1430                 log("This pass merges shareable resources into a single resource. A SAT solver\n");
1431                 log("is used to determine if two resources are share-able.\n");
1432                 log("\n");
1433                 log("  -force\n");
1434                 log("    Per default the selection of cells that is considered for sharing is\n");
1435                 log("    narrowed using a list of cell types. With this option all selected\n");
1436                 log("    cells are considered for resource sharing.\n");
1437                 log("\n");
1438                 log("    IMPORTANT NOTE: If the -all option is used then no cells with internal\n");
1439                 log("    state must be selected!\n");
1440                 log("\n");
1441                 log("  -aggressive\n");
1442                 log("    Per default some heuristics are used to reduce the number of cells\n");
1443                 log("    considered for resource sharing to only large resources. This options\n");
1444                 log("    turns this heuristics off, resulting in much more cells being considered\n");
1445                 log("    for resource sharing.\n");
1446                 log("\n");
1447                 log("  -fast\n");
1448                 log("    Only consider the simple part of the control logic in SAT solving, resulting\n");
1449                 log("    in much easier SAT problems at the cost of maybe missing some opportunities\n");
1450                 log("    for resource sharing.\n");
1451                 log("\n");
1452                 log("  -limit N\n");
1453                 log("    Only perform the first N merges, then stop. This is useful for debugging.\n");
1454                 log("\n");
1455         }
1456         void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
1457         {
1458                 ShareWorkerConfig config;
1459
1460                 config.limit = -1;
1461                 config.opt_force = false;
1462                 config.opt_aggressive = false;
1463                 config.opt_fast = false;
1464
1465                 config.generic_uni_ops.insert("$not");
1466                 // config.generic_uni_ops.insert("$pos");
1467                 config.generic_uni_ops.insert("$neg");
1468
1469                 config.generic_cbin_ops.insert("$and");
1470                 config.generic_cbin_ops.insert("$or");
1471                 config.generic_cbin_ops.insert("$xor");
1472                 config.generic_cbin_ops.insert("$xnor");
1473
1474                 config.generic_bin_ops.insert("$shl");
1475                 config.generic_bin_ops.insert("$shr");
1476                 config.generic_bin_ops.insert("$sshl");
1477                 config.generic_bin_ops.insert("$sshr");
1478
1479                 config.generic_bin_ops.insert("$lt");
1480                 config.generic_bin_ops.insert("$le");
1481                 config.generic_bin_ops.insert("$eq");
1482                 config.generic_bin_ops.insert("$ne");
1483                 config.generic_bin_ops.insert("$eqx");
1484                 config.generic_bin_ops.insert("$nex");
1485                 config.generic_bin_ops.insert("$ge");
1486                 config.generic_bin_ops.insert("$gt");
1487
1488                 config.generic_cbin_ops.insert("$add");
1489                 config.generic_cbin_ops.insert("$mul");
1490
1491                 config.generic_bin_ops.insert("$sub");
1492                 config.generic_bin_ops.insert("$div");
1493                 config.generic_bin_ops.insert("$mod");
1494                 // config.generic_bin_ops.insert("$pow");
1495
1496                 config.generic_uni_ops.insert("$logic_not");
1497                 config.generic_cbin_ops.insert("$logic_and");
1498                 config.generic_cbin_ops.insert("$logic_or");
1499
1500                 config.generic_other_ops.insert("$alu");
1501                 config.generic_other_ops.insert("$macc");
1502
1503                 log_header(design, "Executing SHARE pass (SAT-based resource sharing).\n");
1504
1505                 size_t argidx;
1506                 for (argidx = 1; argidx < args.size(); argidx++) {
1507                         if (args[argidx] == "-force") {
1508                                 config.opt_force = true;
1509                                 continue;
1510                         }
1511                         if (args[argidx] == "-aggressive") {
1512                                 config.opt_aggressive = true;
1513                                 continue;
1514                         }
1515                         if (args[argidx] == "-fast") {
1516                                 config.opt_fast = true;
1517                                 continue;
1518                         }
1519                         if (args[argidx] == "-limit" && argidx+1 < args.size()) {
1520                                 config.limit = atoi(args[++argidx].c_str());
1521                                 continue;
1522                         }
1523                         break;
1524                 }
1525                 extra_args(args, argidx, design);
1526
1527                 for (auto &mod_it : design->modules_)
1528                         if (design->selected(mod_it.second))
1529                                 ShareWorker(config, design, mod_it.second);
1530         }
1531 } SharePass;
1532
1533 PRIVATE_NAMESPACE_END