passes/techmap/alumacc.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/sigtools.h"
  22 #include "kernel/macc.h"
  23
  24 struct AlumaccWorker
  25 {
  26         RTLIL::Module *module;
  27         SigMap sigmap;
  28
  29         struct maccnode_t {
  30                 Macc macc;
  31                 RTLIL::Cell *cell;
  32                 RTLIL::SigSpec y;
  33                 int users;
  34         };
  35
  36         struct alunode_t
  37         {
  38                 std::vector<RTLIL::Cell*> cells;
  39                 RTLIL::SigSpec a, b, c, y;
  40                 std::vector<std::tuple<bool, bool, bool, bool, RTLIL::SigSpec>> cmp;
  41                 bool is_signed, invert_b;
  42
  43                 RTLIL::Cell *alu_cell;
  44                 RTLIL::SigSpec cached_lt, cached_gt, cached_eq, cached_ne;
  45                 RTLIL::SigSpec cached_cf, cached_of, cached_sf;
  46
  47                 RTLIL::SigSpec get_lt() {
  48                         if (SIZE(cached_lt) == 0)
  49                                 cached_lt = is_signed ? alu_cell->module->Xor(NEW_ID, get_of(), get_sf()) : get_cf();
  50                         return cached_lt;
  51                 }
  52
  53                 RTLIL::SigSpec get_gt() {
  54                         if (SIZE(cached_gt) == 0)
  55                                 cached_gt = alu_cell->module->Not(NEW_ID, alu_cell->module->Or(NEW_ID, get_lt(), get_eq()));
  56                         return cached_gt;
  57                 }
  58
  59                 RTLIL::SigSpec get_eq() {
  60                         if (SIZE(cached_eq) == 0)
  61                                 cached_eq = alu_cell->module->ReduceAnd(NEW_ID, alu_cell->getPort("\\X"));
  62                         return cached_eq;
  63                 }
  64
  65                 RTLIL::SigSpec get_ne() {
  66                         if (SIZE(cached_ne) == 0)
  67                                 cached_ne = alu_cell->module->Not(NEW_ID, get_eq());
  68                         return cached_ne;
  69                 }
  70
  71                 RTLIL::SigSpec get_cf() {
  72                         if (SIZE(cached_cf) == 0) {
  73                                 cached_cf = alu_cell->getPort("\\CO");
  74                                 log_assert(SIZE(cached_cf) >= 1);
  75                                 cached_cf = alu_cell->module->Not(NEW_ID, cached_cf[SIZE(cached_cf)-1]);
  76                         }
  77                         return cached_cf;
  78                 }
  79
  80                 RTLIL::SigSpec get_of() {
  81                         if (SIZE(cached_of) == 0) {
  82                                 cached_of = {alu_cell->getPort("\\CO"), alu_cell->getPort("\\CI")};
  83                                 log_assert(SIZE(cached_of) >= 2);
  84                                 cached_of = alu_cell->module->Xor(NEW_ID, cached_of[SIZE(cached_of)-1], cached_of[SIZE(cached_of)-2]);
  85                         }
  86                         return cached_of;
  87                 }
  88
  89                 RTLIL::SigSpec get_sf() {
  90                         if (SIZE(cached_sf) == 0) {
  91                                 cached_sf = alu_cell->getPort("\\Y");
  92                                 cached_sf = cached_sf[SIZE(cached_sf)-1];
  93                         }
  94                         return cached_sf;
  95                 }
  96         };
  97
  98         std::map<RTLIL::SigBit, int> bit_users;
  99         std::map<RTLIL::SigSpec, maccnode_t*> sig_macc;
 100         std::map<RTLIL::SigSig, std::set<alunode_t*>> sig_alu;
 101         int macc_counter, alu_counter;
 102
 103         AlumaccWorker(RTLIL::Module *module) : module(module), sigmap(module)
 104         {
 105                 macc_counter = 0;
 106                 alu_counter = 0;
 107         }
 108
 109         void count_bit_users()
 110         {
 111                 for (auto port : module->ports)
 112                         for (auto bit : sigmap(module->wire(port)))
 113                                 bit_users[bit]++;
 114
 115                 for (auto cell : module->cells())
 116                 for (auto &conn : cell->connections())
 117                         for (auto bit : sigmap(conn.second))
 118                                 bit_users[bit]++;
 119         }
 120
 121         void extract_macc()
 122         {
 123                 for (auto cell : module->selected_cells())
 124                 {
 125                         if (!cell->type.in("$pos", "$neg", "$add", "$sub", "$mul"))
 126                                 continue;
 127
 128                         log("  creating $macc model for %s (%s).\n", log_id(cell), log_id(cell->type));
 129
 130                         maccnode_t *n = new maccnode_t;
 131                         Macc::port_t new_port;
 132
 133                         n->cell = cell;
 134                         n->y = sigmap(cell->getPort("\\Y"));
 135                         n->users = 0;
 136
 137                         for (auto bit : n->y)
 138                                 n->users = std::max(n->users, bit_users.at(bit) - 1);
 139
 140                         if (cell->type.in("$pos", "$neg"))
 141                         {
 142                                 new_port.in_a = sigmap(cell->getPort("\\A"));
 143                                 new_port.is_signed = cell->getParam("\\A_SIGNED").as_bool();
 144                                 new_port.do_subtract = cell->type == "$neg";
 145                                 n->macc.ports.push_back(new_port);
 146                         }
 147
 148                         if (cell->type.in("$add", "$sub"))
 149                         {
 150                                 new_port.in_a = sigmap(cell->getPort("\\A"));
 151                                 new_port.is_signed = cell->getParam("\\A_SIGNED").as_bool();
 152                                 new_port.do_subtract = false;
 153                                 n->macc.ports.push_back(new_port);
 154
 155                                 new_port.in_a = sigmap(cell->getPort("\\B"));
 156                                 new_port.is_signed = cell->getParam("\\B_SIGNED").as_bool();
 157                                 new_port.do_subtract = cell->type == "$sub";
 158                                 n->macc.ports.push_back(new_port);
 159                         }
 160
 161                         if (cell->type.in("$mul"))
 162                         {
 163                                 new_port.in_a = sigmap(cell->getPort("\\A"));
 164                                 new_port.in_b = sigmap(cell->getPort("\\B"));
 165                                 new_port.is_signed = cell->getParam("\\A_SIGNED").as_bool();
 166                                 new_port.do_subtract = false;
 167                                 n->macc.ports.push_back(new_port);
 168                         }
 169
 170                         log_assert(sig_macc.count(n->y) == 0);
 171                         sig_macc[n->y] = n;
 172                 }
 173         }
 174
 175         void merge_macc()
 176         {
 177                 while (1)
 178                 {
 179                         std::set<maccnode_t*> delete_nodes;
 180
 181                         for (auto &it : sig_macc)
 182                         {
 183                                 auto n = it.second;
 184
 185                                 if (delete_nodes.count(n))
 186                                         continue;
 187
 188                                 for (int i = 0; i < SIZE(n->macc.ports); i++)
 189                                 {
 190                                         auto &port = n->macc.ports[i];
 191
 192                                         if (SIZE(port.in_b) > 0 || sig_macc.count(port.in_a) == 0)
 193                                                 continue;
 194
 195                                         auto other_n = sig_macc.at(port.in_a);
 196
 197                                         if (other_n->users > 1)
 198                                                 continue;
 199
 200                                         if (SIZE(other_n->y) != SIZE(n->y))
 201                                                 continue;
 202
 203                                         log("  merging $macc model for %s into %s.\n", log_id(other_n->cell), log_id(n->cell));
 204
 205                                         bool do_subtract = port.do_subtract;
 206                                         for (int j = 0; j < SIZE(other_n->macc.ports); j++) {
 207                                                 if (do_subtract)
 208                                                         other_n->macc.ports[j].do_subtract = !other_n->macc.ports[j].do_subtract;
 209                                                 if (j == 0)
 210                                                         n->macc.ports[i--] = other_n->macc.ports[j];
 211                                                 else
 212                                                         n->macc.ports.push_back(other_n->macc.ports[j]);
 213                                         }
 214
 215                                         delete_nodes.insert(other_n);
 216                                 }
 217                         }
 218
 219                         if (delete_nodes.empty())
 220                                 break;
 221
 222                         for (auto n : delete_nodes) {
 223                                 sig_macc.erase(n->y);
 224                                 delete n;
 225                         }
 226                 }
 227         }
 228
 229         void macc_to_alu()
 230         {
 231                 std::set<maccnode_t*> delete_nodes;
 232
 233                 for (auto &it : sig_macc)
 234                 {
 235                         auto n = it.second;
 236                         RTLIL::SigSpec A, B, C = n->macc.bit_ports;
 237                         bool a_signed = false, b_signed = false;
 238                         bool subtract_b = false;
 239                         alunode_t *alunode;
 240
 241                         for (auto &port : n->macc.ports)
 242                                 if (SIZE(port.in_b) > 0) {
 243                                         goto next_macc;
 244                                 } else if (SIZE(port.in_a) == 1 && !port.is_signed && !port.do_subtract) {
 245                                         C.append(port.in_a);
 246                                 } else if (SIZE(A) || port.do_subtract) {
 247                                         if (SIZE(B))
 248                                                 goto next_macc;
 249                                         B = port.in_a;
 250                                         b_signed = port.is_signed;
 251                                         subtract_b = port.do_subtract;
 252                                 } else {
 253                                         if (SIZE(A))
 254                                                 goto next_macc;
 255                                         A = port.in_a;
 256                                         a_signed = port.is_signed;
 257                                 }
 258
 259                         if (!a_signed || !b_signed) {
 260                                 if (SIZE(A) == SIZE(n->y))
 261                                         a_signed = false;
 262                                 if (SIZE(B) == SIZE(n->y))
 263                                         b_signed = false;
 264                                 if (a_signed != b_signed)
 265                                         goto next_macc;
 266                         }
 267
 268                         if (SIZE(A) == 0 && SIZE(C) > 0) {
 269                                 A = C[0];
 270                                 C.remove(0);
 271                         }
 272
 273                         if (SIZE(B) == 0 && SIZE(C) > 0) {
 274                                 B = C[0];
 275                                 C.remove(0);
 276                         }
 277
 278                         if (subtract_b)
 279                                 C.append(RTLIL::S1);
 280
 281                         if (SIZE(C) > 1)
 282                                 goto next_macc;
 283
 284                         if (!subtract_b && B < A && SIZE(B))
 285                                 std::swap(A, B);
 286
 287                         log("  creating $alu model for $macc %s.\n", log_id(n->cell));
 288
 289                         alunode = new alunode_t;
 290                         alunode->cells.push_back(n->cell);
 291                         alunode->is_signed = a_signed;
 292                         alunode->invert_b = subtract_b;
 293
 294                         alunode->a = A;
 295                         alunode->b = B;
 296                         alunode->c = C;
 297                         alunode->y = n->y;
 298
 299                         sig_alu[RTLIL::SigSig(A, B)].insert(alunode);
 300                         delete_nodes.insert(n);
 301                 next_macc:;
 302                 }
 303
 304                 for (auto n : delete_nodes) {
 305                         sig_macc.erase(n->y);
 306                         delete n;
 307                 }
 308         }
 309
 310         void replace_macc()
 311         {
 312                 for (auto &it : sig_macc)
 313                 {
 314                         auto n = it.second;
 315                         auto cell = module->addCell(NEW_ID, "$macc");
 316                         macc_counter++;
 317
 318                         log("  creating $macc cell for %s: %s\n", log_id(n->cell), log_id(cell));
 319
 320                         n->macc.to_cell(cell);
 321                         cell->setPort("\\Y", n->y);
 322                         cell->fixup_parameters();
 323                         module->remove(n->cell);
 324                         delete n;
 325                 }
 326
 327                 sig_macc.clear();
 328         }
 329
 330         void extract_cmp_alu()
 331         {
 332                 std::vector<RTLIL::Cell*> lge_cells, eq_cells;
 333
 334                 for (auto cell : module->selected_cells())
 335                 {
 336                         if (cell->type.in("$lt", "$le", "$ge", "$gt"))
 337                                 lge_cells.push_back(cell);
 338                         if (cell->type.in("$eq", "$eqx", "$ne", "$nex"))
 339                                 eq_cells.push_back(cell);
 340                 }
 341
 342                 for (auto cell : lge_cells)
 343                 {
 344                         log("  creating $alu model for %s (%s):", log_id(cell), log_id(cell->type));
 345
 346                         bool cmp_less = cell->type.in("$lt", "$le");
 347                         bool cmp_equal = cell->type.in("$le", "$ge");
 348                         bool is_signed = cell->getParam("\\A_SIGNED").as_bool();
 349
 350                         RTLIL::SigSpec A = sigmap(cell->getPort("\\A"));
 351                         RTLIL::SigSpec B = sigmap(cell->getPort("\\B"));
 352                         RTLIL::SigSpec Y = sigmap(cell->getPort("\\Y"));
 353
 354                         if (B < A && SIZE(B)) {
 355                                 cmp_less = !cmp_less;
 356                                 std::swap(A, B);
 357                         }
 358
 359                         alunode_t *n = nullptr;
 360
 361                         for (auto node : sig_alu[RTLIL::SigSig(A, B)])
 362                                 if (node->is_signed == is_signed && node->invert_b && node->c == RTLIL::S1) {
 363                                         n = node;
 364                                         break;
 365                                 }
 366
 367                         if (n == nullptr) {
 368                                 n = new alunode_t;
 369                                 n->a = A;
 370                                 n->b = B;
 371                                 n->c = RTLIL::S1;
 372                                 n->y = module->addWire(NEW_ID, std::max(SIZE(A), SIZE(B)));
 373                                 n->is_signed = is_signed;
 374                                 n->invert_b = true;
 375                                 sig_alu[RTLIL::SigSig(A, B)].insert(n);
 376                                 log(" new $alu\n");
 377                         } else {
 378                                 log(" merged with %s.\n", log_id(n->cells.front()));
 379                         }
 380
 381                         n->cells.push_back(cell);
 382                         n->cmp.push_back(std::make_tuple(cmp_less, !cmp_less, cmp_equal, false, Y));
 383                 }
 384
 385                 for (auto cell : eq_cells)
 386                 {
 387                         bool cmp_equal = cell->type.in("$eq", "$eqx");
 388                         bool is_signed = cell->getParam("\\A_SIGNED").as_bool();
 389
 390                         RTLIL::SigSpec A = sigmap(cell->getPort("\\A"));
 391                         RTLIL::SigSpec B = sigmap(cell->getPort("\\B"));
 392                         RTLIL::SigSpec Y = sigmap(cell->getPort("\\Y"));
 393
 394                         if (B < A && SIZE(B))
 395                                 std::swap(A, B);
 396
 397                         alunode_t *n = nullptr;
 398
 399                         for (auto node : sig_alu[RTLIL::SigSig(A, B)])
 400                                 if (node->is_signed == is_signed && node->invert_b && node->c == RTLIL::S1) {
 401                                         n = node;
 402                                         break;
 403                                 }
 404
 405                         if (n != nullptr) {
 406                                 log("  creating $alu model for %s (%s): merged with %s.\n", log_id(cell), log_id(cell->type), log_id(n->cells.front()));
 407                                 n->cells.push_back(cell);
 408                                 n->cmp.push_back(std::make_tuple(false, false, cmp_equal, !cmp_equal, Y));
 409                         }
 410                 }
 411         }
 412
 413         void replace_alu()
 414         {
 415                 for (auto &it1 : sig_alu)
 416                 for (auto n : it1.second)
 417                 {
 418                         if (SIZE(n->b) == 0 && SIZE(n->c) == 0 && SIZE(n->cmp) == 0)
 419                         {
 420                                 n->alu_cell = module->addPos(NEW_ID, n->a, n->y, n->is_signed);
 421
 422                                 log("  creating $pos cell for ");
 423                                 for (int i = 0; i < SIZE(n->cells); i++)
 424                                         log("%s%s", i ? ", ": "", log_id(n->cells[i]));
 425                                 log(": %s\n", log_id(n->alu_cell));
 426
 427                                 goto delete_node;
 428                         }
 429
 430                         n->alu_cell = module->addCell(NEW_ID, "$alu");
 431                         alu_counter++;
 432
 433                         log("  creating $alu cell for ");
 434                         for (int i = 0; i < SIZE(n->cells); i++)
 435                                 log("%s%s", i ? ", ": "", log_id(n->cells[i]));
 436                         log(": %s\n", log_id(n->alu_cell));
 437
 438                         n->alu_cell->setPort("\\A", n->a);
 439                         n->alu_cell->setPort("\\B", n->b);
 440                         n->alu_cell->setPort("\\CI", SIZE(n->c) ? n->c : RTLIL::S0);
 441                         n->alu_cell->setPort("\\BI", n->invert_b ? RTLIL::S1 : RTLIL::S0);
 442                         n->alu_cell->setPort("\\Y", n->y);
 443                         n->alu_cell->setPort("\\X", module->addWire(NEW_ID, SIZE(n->y)));
 444                         n->alu_cell->setPort("\\CO", module->addWire(NEW_ID, SIZE(n->y)));
 445                         n->alu_cell->fixup_parameters(n->is_signed, n->is_signed);
 446                         log_cell(n->alu_cell);
 447
 448                         for (auto &it : n->cmp)
 449                         {
 450                                 bool cmp_lt = std::get<0>(it);
 451                                 bool cmp_gt = std::get<1>(it);
 452                                 bool cmp_eq = std::get<2>(it);
 453                                 bool cmp_ne = std::get<3>(it);
 454                                 RTLIL::SigSpec cmp_y = std::get<4>(it);
 455
 456                                 RTLIL::SigSpec sig;
 457                                 if (cmp_lt) sig.append(n->get_lt());
 458                                 if (cmp_gt) sig.append(n->get_gt());
 459                                 if (cmp_eq) sig.append(n->get_eq());
 460                                 if (cmp_ne) sig.append(n->get_ne());
 461
 462                                 if (SIZE(sig) > 1)
 463                                         sig = module->ReduceOr(NEW_ID, sig);
 464
 465                                 sig.extend(SIZE(cmp_y));
 466                                 module->connect(cmp_y, sig);
 467                         }
 468
 469                 delete_node:
 470                         for (auto c : n->cells)
 471                                 module->remove(c);
 472                         delete n;
 473                 }
 474
 475                 sig_alu.clear();
 476         }
 477
 478         void run()
 479         {
 480                 log("Extracting $alu and $macc cells in module %s:\n", log_id(module));
 481
 482                 count_bit_users();
 483                 extract_macc();
 484                 merge_macc();
 485                 macc_to_alu();
 486                 replace_macc();
 487                 extract_cmp_alu();
 488                 replace_alu();
 489
 490                 log("  created %d $alu and %d $macc cells.\n", alu_counter, macc_counter);
 491         }
 492 };
 493
 494 struct AlumaccPass : public Pass {
 495         AlumaccPass() : Pass("alumacc", "extract ALU and MACC cells") { }
 496         virtual void help()
 497         {
 498                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 499                 log("\n");
 500                 log("    alumacc [selection]\n");
 501                 log("\n");
 502                 log("This pass translates arithmetic operations $add, $mul, $lt, etc. to $alu and\n");
 503                 log("$macc cells.\n");
 504                 log("\n");
 505         }
 506         virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
 507         {
 508                 log_header("Executing ALUMACC pass (create $alu and $macc cells).\n");
 509
 510                 size_t argidx;
 511                 for (argidx = 1; argidx < args.size(); argidx++) {
 512                         // if (args[argidx] == "-foobar") {
 513                         //      foobar_mode = true;
 514                         //      continue;
 515                         // }
 516                         break;
 517                 }
 518                 extra_args(args, argidx, design);
 519
 520                 for (auto mod : design->selected_modules())
 521                         if (!mod->has_processes_warn()) {
 522                                 AlumaccWorker worker(mod);
 523                                 worker.run();
 524                         }
 525         }
 526 } AlumaccPass;
 527