passes/opt/opt_share.cc

   1 /*
   2  *  yosys -- Yosys Open SYnthesis Suite
   3  *
   4  *  Copyright (C) 2012  Clifford Wolf <clifford@clifford.at>
   5  *                2019  Bogdan Vukobratovic <bogdan.vukobratovic@gmail.com>
   6  *
   7  *  Permission to use, copy, modify, and/or distribute this software for any
   8  *  purpose with or without fee is hereby granted, provided that the above
   9  *  copyright notice and this permission notice appear in all copies.
  10  *
  11  *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  12  *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  13  *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  14  *  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  15  *  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  16  *  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  17  *  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  18  *
  19  */
  20
  21 #include "kernel/log.h"
  22 #include "kernel/register.h"
  23 #include "kernel/rtlil.h"
  24 #include "kernel/sigtools.h"
  25 #include <algorithm>
  26
  27 #include <stdio.h>
  28 #include <stdlib.h>
  29
  30 USING_YOSYS_NAMESPACE
  31 PRIVATE_NAMESPACE_BEGIN
  32
  33 SigMap assign_map;
  34
  35 struct OpMuxConn {
  36         RTLIL::SigSpec sig;
  37         RTLIL::Cell *mux;
  38         RTLIL::Cell *op;
  39         int mux_port_id;
  40         int mux_port_offset;
  41         int op_outsig_offset;
  42
  43         bool operator<(const OpMuxConn &other) const
  44         {
  45                 if (mux != other.mux)
  46                         return mux < other.mux;
  47
  48                 if (mux_port_id != other.mux_port_id)
  49                         return mux_port_id < other.mux_port_id;
  50
  51                 return mux_port_offset < other.mux_port_offset;
  52         }
  53 };
  54
  55 // Helper class to track additiona information about a SigSpec, like whether it is signed and the semantics of the port it is connected to
  56 struct ExtSigSpec {
  57         RTLIL::SigSpec sig;
  58         RTLIL::SigSpec sign;
  59         bool is_signed;
  60         RTLIL::IdString semantics;
  61
  62         ExtSigSpec() {}
  63
  64         ExtSigSpec(RTLIL::SigSpec s, RTLIL::SigSpec sign = RTLIL::Const(0, 1), bool is_signed = false, RTLIL::IdString semantics = RTLIL::IdString()) : sig(s), sign(sign), is_signed(is_signed), semantics(semantics) {}
  65
  66         bool empty() const { return sig.empty(); }
  67
  68         bool operator<(const ExtSigSpec &other) const
  69         {
  70                 if (sig != other.sig)
  71                         return sig < other.sig;
  72
  73                 if (sign != other.sign)
  74                         return sign < other.sign;
  75
  76                 if (is_signed != other.is_signed)
  77                         return is_signed < other.is_signed;
  78
  79                 return semantics < other.semantics;
  80         }
  81
  82         bool operator==(const RTLIL::SigSpec &other) const { return (sign != RTLIL::Const(0, 1)) ? false : sig == other; }
  83         bool operator==(const ExtSigSpec &other) const { return is_signed == other.is_signed && sign == other.sign && sig == other.sig && semantics == other.semantics; }
  84 };
  85
  86 #define FINE_BITWISE_OPS ID($_AND_), ID($_NAND_), ID($_OR_), ID($_NOR_), ID($_XOR_), ID($_XNOR_), ID($_ANDNOT_), ID($_ORNOT_)
  87
  88 #define BITWISE_OPS FINE_BITWISE_OPS, ID($and), ID($or), ID($xor), ID($xnor)
  89
  90 #define REDUCTION_OPS ID($reduce_and), ID($reduce_or), ID($reduce_xor), ID($reduce_xnor), ID($reduce_bool), ID($reduce_nand)
  91
  92 #define LOGICAL_OPS ID($logic_and), ID($logic_or)
  93
  94 #define SHIFT_OPS ID($shl), ID($shr), ID($sshl), ID($sshr), ID($shift), ID($shiftx)
  95
  96 #define RELATIONAL_OPS ID($lt), ID($le), ID($eq), ID($ne), ID($eqx), ID($nex), ID($ge), ID($gt)
  97
  98 bool cell_supported(RTLIL::Cell *cell)
  99 {
 100         if (cell->type.in(ID($alu))) {
 101                 RTLIL::SigSpec sig_bi = cell->getPort(ID::BI);
 102                 RTLIL::SigSpec sig_ci = cell->getPort(ID::CI);
 103
 104                 if (sig_bi.is_fully_const() && sig_ci.is_fully_const() && sig_bi == sig_ci)
 105                         return true;
 106         } else if (cell->type.in(LOGICAL_OPS, SHIFT_OPS, BITWISE_OPS, RELATIONAL_OPS, ID($add), ID($sub), ID($mul), ID($div), ID($mod), ID($concat))) {
 107                 return true;
 108         }
 109
 110         return false;
 111 }
 112
 113 std::map<IdString, IdString> mergeable_type_map;
 114
 115 bool mergeable(RTLIL::Cell *a, RTLIL::Cell *b)
 116 {
 117         if (mergeable_type_map.empty()) {
 118                 mergeable_type_map.insert({ID($sub), ID($add)});
 119         }
 120         auto a_type = a->type;
 121         if (mergeable_type_map.count(a_type))
 122                 a_type = mergeable_type_map.at(a_type);
 123
 124         auto b_type = b->type;
 125         if (mergeable_type_map.count(b_type))
 126                 b_type = mergeable_type_map.at(b_type);
 127
 128         return a_type == b_type;
 129 }
 130
 131 RTLIL::IdString decode_port_semantics(RTLIL::Cell *cell, RTLIL::IdString port_name)
 132 {
 133         if (cell->type.in(ID($lt), ID($le), ID($ge), ID($gt), ID($div), ID($mod), ID($concat), SHIFT_OPS) && port_name == ID::B)
 134                 return port_name;
 135
 136         return "";
 137 }
 138
 139 RTLIL::SigSpec decode_port_sign(RTLIL::Cell *cell, RTLIL::IdString port_name) {
 140
 141         if (cell->type == ID($alu) && port_name == ID::B)
 142                 return cell->getPort(ID::BI);
 143         else if (cell->type == ID($sub) && port_name == ID::B)
 144                 return RTLIL::Const(1, 1);
 145
 146         return RTLIL::Const(0, 1);
 147 }
 148
 149 bool decode_port_signed(RTLIL::Cell *cell, RTLIL::IdString port_name)
 150 {
 151         if (cell->type.in(BITWISE_OPS, LOGICAL_OPS))
 152                 return false;
 153
 154         if (cell->hasParam(port_name.str() + "_SIGNED"))
 155                 return cell->getParam(port_name.str() + "_SIGNED").as_bool();
 156
 157         return false;
 158 }
 159
 160 ExtSigSpec decode_port(RTLIL::Cell *cell, RTLIL::IdString port_name, SigMap *sigmap)
 161 {
 162         auto sig = (*sigmap)(cell->getPort(port_name));
 163
 164         RTLIL::SigSpec sign = decode_port_sign(cell, port_name);
 165         RTLIL::IdString semantics = decode_port_semantics(cell, port_name);
 166
 167         bool is_signed = decode_port_signed(cell, port_name);
 168
 169         return ExtSigSpec(sig, sign, is_signed, semantics);
 170 }
 171
 172 void merge_operators(RTLIL::Module *module, RTLIL::Cell *mux, const std::vector<OpMuxConn> &ports, const ExtSigSpec &operand)
 173 {
 174         std::vector<ExtSigSpec> muxed_operands;
 175         int max_width = 0;
 176         for (const auto& p : ports) {
 177                 auto op = p.op;
 178
 179                 RTLIL::IdString muxed_port_name = ID::A;
 180                 if (decode_port(op, ID::A, &assign_map) == operand)
 181                         muxed_port_name = ID::B;
 182
 183                 auto operand = decode_port(op, muxed_port_name, &assign_map);
 184                 if (operand.sig.size() > max_width)
 185                         max_width = operand.sig.size();
 186
 187                 muxed_operands.push_back(operand);
 188         }
 189
 190         auto shared_op = ports[0].op;
 191
 192         if (std::any_of(muxed_operands.begin(), muxed_operands.end(), [&](ExtSigSpec &op) { return op.sign != muxed_operands[0].sign; }))
 193         max_width = std::max(max_width, shared_op->getParam(ID::Y_WIDTH).as_int());
 194
 195
 196         for (auto &operand : muxed_operands)
 197                 operand.sig.extend_u0(max_width, operand.is_signed);
 198
 199         for (const auto& p : ports) {
 200                 auto op = p.op;
 201                 if (op == shared_op)
 202                         continue;
 203                 module->remove(op);
 204         }
 205
 206         for (auto &muxed_op : muxed_operands)
 207                 if (muxed_op.sign != muxed_operands[0].sign)
 208                         muxed_op = ExtSigSpec(module->Neg(NEW_ID, muxed_op.sig, muxed_op.is_signed));
 209
 210         RTLIL::SigSpec mux_y = mux->getPort(ID::Y);
 211         RTLIL::SigSpec mux_a = mux->getPort(ID::A);
 212         RTLIL::SigSpec mux_b = mux->getPort(ID::B);
 213         RTLIL::SigSpec mux_s = mux->getPort(ID::S);
 214
 215         RTLIL::SigSpec shared_pmux_a = RTLIL::Const(RTLIL::State::Sx, max_width);
 216         RTLIL::SigSpec shared_pmux_b;
 217         RTLIL::SigSpec shared_pmux_s;
 218
 219         int conn_width = ports[0].sig.size();
 220         int conn_offset = ports[0].mux_port_offset;
 221
 222         shared_op->setPort(ID::Y, shared_op->getPort(ID::Y).extract(0, conn_width));
 223
 224         if (mux->type == ID($pmux)) {
 225                 shared_pmux_s = RTLIL::SigSpec();
 226
 227                 for (const auto &p : ports) {
 228                         shared_pmux_s.append(mux_s[p.mux_port_id]);
 229                         mux_b.replace(p.mux_port_id * mux_a.size() + conn_offset, shared_op->getPort(ID::Y));
 230                 }
 231         } else {
 232                 shared_pmux_s = RTLIL::SigSpec{mux_s, module->Not(NEW_ID, mux_s)};
 233                 mux_a.replace(conn_offset, shared_op->getPort(ID::Y));
 234                 mux_b.replace(conn_offset, shared_op->getPort(ID::Y));
 235         }
 236
 237         mux->setPort(ID::A, mux_a);
 238         mux->setPort(ID::B, mux_b);
 239         mux->setPort(ID::Y, mux_y);
 240         mux->setPort(ID::S, mux_s);
 241
 242         for (const auto &op : muxed_operands)
 243                 shared_pmux_b.append(op.sig);
 244
 245         auto mux_to_oper = module->Pmux(NEW_ID, shared_pmux_a, shared_pmux_b, shared_pmux_s);
 246
 247         if (shared_op->type.in(ID($alu))) {
 248                 RTLIL::SigSpec alu_x = shared_op->getPort(ID::X);
 249                 RTLIL::SigSpec alu_co = shared_op->getPort(ID::CO);
 250
 251                 shared_op->setPort(ID::X, alu_x.extract(0, conn_width));
 252                 shared_op->setPort(ID::CO, alu_co.extract(0, conn_width));
 253         }
 254
 255         bool is_fine = shared_op->type.in(FINE_BITWISE_OPS);
 256
 257         if (!is_fine)
 258                 shared_op->setParam(ID::Y_WIDTH, conn_width);
 259
 260         if (decode_port(shared_op, ID::A, &assign_map) == operand) {
 261                 shared_op->setPort(ID::B, mux_to_oper);
 262                 if (!is_fine)
 263                         shared_op->setParam(ID::B_WIDTH, max_width);
 264         } else {
 265                 shared_op->setPort(ID::A, mux_to_oper);
 266                 if (!is_fine)
 267                         shared_op->setParam(ID::A_WIDTH, max_width);
 268         }
 269 }
 270
 271 typedef struct {
 272         RTLIL::Cell *mux;
 273         std::vector<OpMuxConn> ports;
 274         ExtSigSpec shared_operand;
 275 } merged_op_t;
 276
 277
 278 template <typename T> void remove_val(std::vector<T> &v, const std::vector<T> &vals)
 279 {
 280         auto val_iter = vals.rbegin();
 281         for (auto i = v.rbegin(); i != v.rend(); ++i)
 282                 if ((val_iter != vals.rend()) && (*i == *val_iter)) {
 283                         v.erase(i.base() - 1);
 284                         ++val_iter;
 285                 }
 286 }
 287
 288 void check_muxed_operands(std::vector<const OpMuxConn *> &ports, const ExtSigSpec &shared_operand)
 289 {
 290         auto it = ports.begin();
 291         ExtSigSpec seed;
 292
 293         while (it != ports.end()) {
 294                 auto p = *it;
 295                 auto op = p->op;
 296
 297                 RTLIL::IdString muxed_port_name = ID::A;
 298                 if (decode_port(op, ID::A, &assign_map) == shared_operand) {
 299                         muxed_port_name = ID::B;
 300                 }
 301
 302                 auto operand = decode_port(op, muxed_port_name, &assign_map);
 303
 304                 if (seed.empty())
 305                         seed = operand;
 306
 307                 if (operand.is_signed != seed.is_signed) {
 308                         ports.erase(it);
 309                 } else {
 310                         ++it;
 311                 }
 312         }
 313 }
 314
 315 ExtSigSpec find_shared_operand(const OpMuxConn* seed, std::vector<const OpMuxConn *> &ports, const std::map<ExtSigSpec, std::set<RTLIL::Cell *>> &operand_to_users)
 316 {
 317         std::set<RTLIL::Cell *> ops_using_operand;
 318         std::set<RTLIL::Cell *> ops_set;
 319         for(const auto& p: ports)
 320                 ops_set.insert(p->op);
 321
 322         ExtSigSpec oper;
 323
 324         auto op_a = seed->op;
 325
 326         for (RTLIL::IdString port_name : {ID::A, ID::B}) {
 327                 oper = decode_port(op_a, port_name, &assign_map);
 328                 auto operand_users = operand_to_users.at(oper);
 329
 330                 if (operand_users.size() == 1)
 331                         continue;
 332
 333                 ops_using_operand.clear();
 334                 for (auto mux_ops: ops_set)
 335                         if (operand_users.count(mux_ops))
 336                                 ops_using_operand.insert(mux_ops);
 337
 338                 if (ops_using_operand.size() > 1) {
 339                         ports.erase(std::remove_if(ports.begin(), ports.end(), [&](const OpMuxConn *p) { return !ops_using_operand.count(p->op); }),
 340                                                 ports.end());
 341                         return oper;
 342                 }
 343         }
 344
 345         return ExtSigSpec();
 346 }
 347
 348 dict<RTLIL::SigSpec, OpMuxConn> find_valid_op_mux_conns(RTLIL::Module *module, dict<RTLIL::SigBit, RTLIL::SigSpec> &op_outbit_to_outsig,
 349                                                         dict<RTLIL::SigSpec, RTLIL::Cell *> outsig_to_operator,
 350                                                         dict<RTLIL::SigBit, RTLIL::SigSpec> &op_aux_to_outsig)
 351 {
 352         dict<RTLIL::SigSpec, int> op_outsig_user_track;
 353         dict<RTLIL::SigSpec, OpMuxConn> op_mux_conn_map;
 354
 355         std::function<void(RTLIL::SigSpec)> remove_outsig = [&](RTLIL::SigSpec outsig) {
 356                 for (auto op_outbit : outsig)
 357                         op_outbit_to_outsig.erase(op_outbit);
 358
 359                 if (op_mux_conn_map.count(outsig))
 360                         op_mux_conn_map.erase(outsig);
 361         };
 362
 363         std::function<void(RTLIL::SigBit)> remove_outsig_from_aux_bit = [&](RTLIL::SigBit auxbit) {
 364                 auto aux_outsig = op_aux_to_outsig.at(auxbit);
 365                 auto op = outsig_to_operator.at(aux_outsig);
 366                 auto op_outsig = assign_map(op->getPort(ID::Y));
 367                 remove_outsig(op_outsig);
 368
 369                 for (auto aux_outbit : aux_outsig)
 370                         op_aux_to_outsig.erase(aux_outbit);
 371         };
 372
 373         std::function<void(RTLIL::Cell *)> find_op_mux_conns = [&](RTLIL::Cell *mux) {
 374                 RTLIL::SigSpec sig;
 375                 int mux_port_size;
 376
 377                 if (mux->type.in(ID($mux), ID($_MUX_))) {
 378                         mux_port_size = mux->getPort(ID::A).size();
 379                         sig = RTLIL::SigSpec{mux->getPort(ID::B), mux->getPort(ID::A)};
 380                 } else {
 381                         mux_port_size = mux->getPort(ID::A).size();
 382                         sig = mux->getPort(ID::B);
 383                 }
 384
 385                 auto mux_insig = assign_map(sig);
 386
 387                 for (int i = 0; i < mux_insig.size(); ++i) {
 388                         if (op_aux_to_outsig.count(mux_insig[i])) {
 389                                 remove_outsig_from_aux_bit(mux_insig[i]);
 390                                 continue;
 391                         }
 392
 393                         if (!op_outbit_to_outsig.count(mux_insig[i]))
 394                                 continue;
 395
 396                         auto op_outsig = op_outbit_to_outsig.at(mux_insig[i]);
 397
 398                         if (op_mux_conn_map.count(op_outsig)) {
 399                                 remove_outsig(op_outsig);
 400                                 continue;
 401                         }
 402
 403                         int mux_port_id = i / mux_port_size;
 404                         int mux_port_offset = i % mux_port_size;
 405
 406                         int op_outsig_offset;
 407                         for (op_outsig_offset = 0; op_outsig[op_outsig_offset] != mux_insig[i]; ++op_outsig_offset)
 408                                 ;
 409
 410                         int j = op_outsig_offset;
 411                         do {
 412                                 if (!op_outbit_to_outsig.count(mux_insig[i]))
 413                                         break;
 414
 415                                 if (op_outbit_to_outsig.at(mux_insig[i]) != op_outsig)
 416                                         break;
 417
 418                                 ++i;
 419                                 ++j;
 420                         } while ((i / mux_port_size == mux_port_id) && (j < op_outsig.size()));
 421
 422                         int op_conn_width = j - op_outsig_offset;
 423                         OpMuxConn inp = {
 424                                 op_outsig.extract(op_outsig_offset, op_conn_width),
 425                                 mux,
 426                                 outsig_to_operator.at(op_outsig),
 427                                 mux_port_id,
 428                                 mux_port_offset,
 429                                 op_outsig_offset,
 430                         };
 431
 432                         op_mux_conn_map[op_outsig] = inp;
 433
 434                         --i;
 435                 }
 436         };
 437
 438         std::function<void(RTLIL::SigSpec)> remove_connected_ops = [&](RTLIL::SigSpec sig) {
 439                 auto mux_insig = assign_map(sig);
 440                 for (auto outbit : mux_insig) {
 441                         if (op_aux_to_outsig.count(outbit)) {
 442                                 remove_outsig_from_aux_bit(outbit);
 443                                 continue;
 444                         }
 445
 446                         if (!op_outbit_to_outsig.count(outbit))
 447                                 continue;
 448
 449                         remove_outsig(op_outbit_to_outsig.at(outbit));
 450                 }
 451         };
 452
 453         for (auto cell : module->cells()) {
 454                 if (cell->type.in(ID($mux), ID($_MUX_), ID($pmux))) {
 455                         remove_connected_ops(cell->getPort(ID::S));
 456                         find_op_mux_conns(cell);
 457                 } else {
 458                         for (auto &conn : cell->connections())
 459                                 if (cell->input(conn.first))
 460                                         remove_connected_ops(conn.second);
 461                 }
 462         }
 463
 464         for (auto w : module->wires()) {
 465                 if (!w->port_output)
 466                         continue;
 467
 468                 remove_connected_ops(w);
 469         }
 470
 471         return op_mux_conn_map;
 472 }
 473
 474 struct OptSharePass : public Pass {
 475         OptSharePass() : Pass("opt_share", "merge mutually exclusive cells of the same type that share an input signal") {}
 476         void help() YS_OVERRIDE
 477         {
 478                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 479                 log("\n");
 480                 log("    opt_share [selection]\n");
 481                 log("\n");
 482
 483                 log("This pass identifies mutually exclusive cells of the same type that:\n");
 484                 log("    (a) share an input signal,\n");
 485                 log("    (b) drive the same $mux, $_MUX_, or $pmux multiplexing cell,\n");
 486                 log("\n");
 487                 log("allowing the cell to be merged and the multiplexer to be moved from\n");
 488                 log("multiplexing its output to multiplexing the non-shared input signals.\n");
 489                 log("\n");
 490         }
 491         void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
 492         {
 493
 494                 log_header(design, "Executing OPT_SHARE pass.\n");
 495
 496                 extra_args(args, 1, design);
 497                 for (auto module : design->selected_modules()) {
 498                         assign_map.clear();
 499                         assign_map.set(module);
 500
 501                         std::map<ExtSigSpec, std::set<RTLIL::Cell *>> operand_to_users;
 502                         dict<RTLIL::SigSpec, RTLIL::Cell *> outsig_to_operator;
 503                         dict<RTLIL::SigBit, RTLIL::SigSpec> op_outbit_to_outsig;
 504                         dict<RTLIL::SigBit, RTLIL::SigSpec> op_aux_to_outsig;
 505                         bool any_shared_operands = false;
 506                         std::vector<ExtSigSpec> op_insigs;
 507
 508                         for (auto cell : module->cells()) {
 509                                 if (!cell_supported(cell))
 510                                         continue;
 511
 512                                 if (cell->type == ID($alu)) {
 513                                         for (RTLIL::IdString port_name : {ID::X, ID::CO}) {
 514                                                 auto mux_insig = assign_map(cell->getPort(port_name));
 515                                                 outsig_to_operator[mux_insig] = cell;
 516                                                 for (auto outbit : mux_insig)
 517                                                         op_aux_to_outsig[outbit] = mux_insig;
 518                                         }
 519                                 }
 520
 521                                 auto mux_insig = assign_map(cell->getPort(ID::Y));
 522                                 outsig_to_operator[mux_insig] = cell;
 523                                 for (auto outbit : mux_insig)
 524                                         op_outbit_to_outsig[outbit] = mux_insig;
 525
 526                                 for (RTLIL::IdString port_name : {ID::A, ID::B}) {
 527                                         auto op_insig = decode_port(cell, port_name, &assign_map);
 528                                         op_insigs.push_back(op_insig);
 529                                         operand_to_users[op_insig].insert(cell);
 530                                         if (operand_to_users[op_insig].size() > 1)
 531                                                 any_shared_operands = true;
 532                                 }
 533                         }
 534
 535                         if (!any_shared_operands)
 536                                 continue;
 537
 538                         // Operator outputs need to be exclusively connected to the $mux inputs in order to be mergeable. Hence we count to
 539                         // how many points are operator output bits connected.
 540                         dict<RTLIL::SigSpec, OpMuxConn> op_mux_conn_map =
 541                           find_valid_op_mux_conns(module, op_outbit_to_outsig, outsig_to_operator, op_aux_to_outsig);
 542
 543                         // Group op connections connected to same ports of the same $mux. Sort them in ascending order of their port offset
 544                         dict<RTLIL::Cell*, std::vector<std::set<OpMuxConn>>> mux_port_op_conns;
 545                         for (auto& val: op_mux_conn_map) {
 546                                 OpMuxConn p = val.second;
 547                                 auto& mux_port_conns = mux_port_op_conns[p.mux];
 548
 549                                 if (mux_port_conns.size() == 0) {
 550                                         int mux_port_num;
 551
 552                                         if (p.mux->type.in(ID($mux), ID($_MUX_)))
 553                                                 mux_port_num = 2;
 554                                         else
 555                                                 mux_port_num = p.mux->getPort(ID::S).size();
 556
 557                                         mux_port_conns.resize(mux_port_num);
 558                                 }
 559
 560                                 mux_port_conns[p.mux_port_id].insert(p);
 561                         }
 562
 563                         std::vector<merged_op_t> merged_ops;
 564                         for (auto& val: mux_port_op_conns) {
 565
 566                                 RTLIL::Cell* cell = val.first;
 567                                 auto &mux_port_conns = val.second;
 568
 569                                 const OpMuxConn *seed = NULL;
 570
 571                                 // Look through the bits of the $mux inputs and see which of them are connected to the operator
 572                                 // results. Operator results can be concatenated with other signals before led to the $mux.
 573                                 while (true) {
 574
 575                                         // Remove either the merged ports from the last iteration or the seed that failed to yield a merger
 576                                         if (seed != NULL) {
 577                                                 mux_port_conns[seed->mux_port_id].erase(*seed);
 578                                                 seed = NULL;
 579                                         }
 580
 581                                         // For a new merger, find the seed op connection that starts at lowest port offset among port connections
 582                                         for (auto &port_conns : mux_port_conns) {
 583                                                 if (!port_conns.size())
 584                                                         continue;
 585
 586                                                 const OpMuxConn *next_p = &(*port_conns.begin());
 587
 588                                                 if ((seed == NULL) || (seed->mux_port_offset > next_p->mux_port_offset))
 589                                                         seed = next_p;
 590                                         }
 591
 592                                         // Cannot find the seed -> nothing to do for this $mux anymore
 593                                         if (seed == NULL)
 594                                                 break;
 595
 596                                         // Find all other op connections that start from the same port offset, and whose ops can be merged with the seed op
 597                                         std::vector<const OpMuxConn *> mergeable_conns;
 598                                         for (auto &port_conns : mux_port_conns) {
 599                                                 if (!port_conns.size())
 600                                                         continue;
 601
 602                                                 const OpMuxConn *next_p = &(*port_conns.begin());
 603
 604                                                 if ((next_p->op_outsig_offset == seed->op_outsig_offset) &&
 605                                                     (next_p->mux_port_offset == seed->mux_port_offset) && mergeable(next_p->op, seed->op) &&
 606                                                     next_p->sig.size() == seed->sig.size())
 607                                                         mergeable_conns.push_back(next_p);
 608                                         }
 609
 610                                         // We need at least two mergeable connections for the merger
 611                                         if (mergeable_conns.size() < 2)
 612                                                 continue;
 613
 614                                         // Filter mergeable connections whose ops share an operand with seed connection's op
 615                                         auto shared_operand = find_shared_operand(seed, mergeable_conns, operand_to_users);
 616
 617                                         if (shared_operand.empty())
 618                                                 continue;
 619
 620                                         check_muxed_operands(mergeable_conns, shared_operand);
 621
 622                                         if (mergeable_conns.size() < 2)
 623                                                 continue;
 624
 625                                         // Remember the combination for the merger
 626                                         std::vector<OpMuxConn> merged_ports;
 627                                         for (auto p : mergeable_conns) {
 628                                                 merged_ports.push_back(*p);
 629                                                 mux_port_conns[p->mux_port_id].erase(*p);
 630                                         }
 631
 632                                         seed = NULL;
 633
 634                                         merged_ops.push_back(merged_op_t{cell, merged_ports, shared_operand});
 635
 636                                         design->scratchpad_set_bool("opt.did_something", true);
 637                                 }
 638
 639                         }
 640
 641                         for (auto &shared : merged_ops) {
 642                                 log("    Found cells that share an operand and can be merged by moving the %s %s in front "
 643                                     "of "
 644                                     "them:\n",
 645                                     log_id(shared.mux->type), log_id(shared.mux));
 646                                 for (const auto& op : shared.ports)
 647                                         log("        %s\n", log_id(op.op));
 648                                 log("\n");
 649
 650                                 merge_operators(module, shared.mux, shared.ports, shared.shared_operand);
 651                         }
 652                 }
 653         }
 654
 655 } OptSharePass;
 656
 657 PRIVATE_NAMESPACE_END