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