passes/opt/opt_clean.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/register.h"
  21 #include "kernel/sigtools.h"
  22 #include "kernel/log.h"
  23 #include "kernel/celltypes.h"
  24 #include <stdlib.h>
  25 #include <stdio.h>
  26 #include <set>
  27
  28 USING_YOSYS_NAMESPACE
  29 PRIVATE_NAMESPACE_BEGIN
  30
  31 using RTLIL::id2cstr;
  32
  33 struct keep_cache_t
  34 {
  35         Design *design;
  36         dict<Module*, bool> cache;
  37
  38         void reset(Design *design = nullptr)
  39         {
  40                 this->design = design;
  41                 cache.clear();
  42         }
  43
  44         bool query(Module *module)
  45         {
  46                 log_assert(design != nullptr);
  47
  48                 if (module == nullptr)
  49                         return false;
  50
  51                 if (cache.count(module))
  52                         return cache.at(module);
  53
  54                 cache[module] = true;
  55                 if (!module->get_bool_attribute("\\keep")) {
  56                         bool found_keep = false;
  57                         for (auto cell : module->cells())
  58                                 if (query(cell)) found_keep = true;
  59                         cache[module] = found_keep;
  60                 }
  61
  62                 return cache[module];
  63         }
  64
  65         bool query(Cell *cell)
  66         {
  67                 if (cell->type.in("$memwr", "$meminit", "$assert", "$assume", "$live", "$fair", "$cover"))
  68                         return true;
  69
  70                 if (cell->has_keep_attr())
  71                         return true;
  72
  73                 if (cell->module && cell->module->design)
  74                         return query(cell->module->design->module(cell->type));
  75
  76                 return false;
  77         }
  78 };
  79
  80 keep_cache_t keep_cache;
  81 CellTypes ct_reg, ct_all;
  82 int count_rm_cells, count_rm_wires;
  83
  84 void rmunused_module_cells(Module *module, bool verbose)
  85 {
  86         SigMap sigmap(module);
  87         pool<Cell*> queue, unused;
  88         dict<SigBit, pool<Cell*>> wire2driver;
  89
  90         for (auto &it : module->cells_) {
  91                 Cell *cell = it.second;
  92                 for (auto &it2 : cell->connections()) {
  93                         if (!ct_all.cell_known(cell->type) || ct_all.cell_output(cell->type, it2.first))
  94                                 for (auto raw_bit : it2.second) {
  95                                         if (raw_bit.wire == nullptr)
  96                                                 continue;
  97                                         auto bit = sigmap(raw_bit);
  98                                         if (bit.wire == nullptr)
  99                                                 log_warning("Driver-driver conflict for %s between cell %s.%s and constant %s in %s: Resolved using constant.\n",
 100                                                                 log_signal(raw_bit), log_id(cell), log_id(it2.first), log_signal(bit), log_id(module));
 101                                         if (bit.wire != nullptr)
 102                                                 wire2driver[bit].insert(cell);
 103                                 }
 104                 }
 105                 if (keep_cache.query(cell))
 106                         queue.insert(cell);
 107                 else
 108                         unused.insert(cell);
 109         }
 110
 111         for (auto &it : module->wires_) {
 112                 Wire *wire = it.second;
 113                 if (wire->port_output || wire->get_bool_attribute("\\keep")) {
 114                         for (auto bit : sigmap(wire))
 115                         for (auto c : wire2driver[bit])
 116                                 queue.insert(c), unused.erase(c);
 117                 }
 118         }
 119
 120         while (!queue.empty())
 121         {
 122                 pool<SigBit> bits;
 123                 for (auto cell : queue)
 124                 for (auto &it : cell->connections())
 125                         if (!ct_all.cell_known(cell->type) || ct_all.cell_input(cell->type, it.first))
 126                                 for (auto bit : sigmap(it.second))
 127                                         bits.insert(bit);
 128
 129                 queue.clear();
 130                 for (auto bit : bits)
 131                 for (auto c : wire2driver[bit])
 132                         if (unused.count(c))
 133                                 queue.insert(c), unused.erase(c);
 134         }
 135
 136         unused.sort(RTLIL::sort_by_name_id<RTLIL::Cell>());
 137
 138         for (auto cell : unused) {
 139                 if (verbose)
 140                         log_debug("  removing unused `%s' cell `%s'.\n", cell->type.c_str(), cell->name.c_str());
 141                 module->design->scratchpad_set_bool("opt.did_something", true);
 142                 module->remove(cell);
 143                 count_rm_cells++;
 144         }
 145 }
 146
 147 int count_nontrivial_wire_attrs(RTLIL::Wire *w)
 148 {
 149         int count = w->attributes.size();
 150         count -= w->attributes.count("\\src");
 151         count -= w->attributes.count("\\unused_bits");
 152         return count;
 153 }
 154
 155 bool compare_signals(RTLIL::SigBit &s1, RTLIL::SigBit &s2, SigPool &regs, SigPool &conns, pool<RTLIL::Wire*> &direct_wires)
 156 {
 157         RTLIL::Wire *w1 = s1.wire;
 158         RTLIL::Wire *w2 = s2.wire;
 159
 160         if (w1 == NULL || w2 == NULL)
 161                 return w2 == NULL;
 162
 163         if (w1->port_input != w2->port_input)
 164                 return w2->port_input;
 165
 166         if ((w1->port_input && w1->port_output) != (w2->port_input && w2->port_output))
 167                 return !(w2->port_input && w2->port_output);
 168
 169         if (w1->name[0] == '\\' && w2->name[0] == '\\') {
 170                 if (regs.check_any(s1) != regs.check_any(s2))
 171                         return regs.check_any(s2);
 172                 if (direct_wires.count(w1) != direct_wires.count(w2))
 173                         return direct_wires.count(w2) != 0;
 174                 if (conns.check_any(s1) != conns.check_any(s2))
 175                         return conns.check_any(s2);
 176         }
 177
 178         if (w1->port_output != w2->port_output)
 179                 return w2->port_output;
 180
 181         if (w1->name[0] != w2->name[0])
 182                 return w2->name[0] == '\\';
 183
 184         int attrs1 = count_nontrivial_wire_attrs(w1);
 185         int attrs2 = count_nontrivial_wire_attrs(w2);
 186
 187         if (attrs1 != attrs2)
 188                 return attrs2 > attrs1;
 189
 190         return strcmp(w2->name.c_str(), w1->name.c_str()) < 0;
 191 }
 192
 193 bool check_public_name(RTLIL::IdString id)
 194 {
 195         const std::string &id_str = id.str();
 196         if (id_str[0] == '$')
 197                 return false;
 198         if (id_str.substr(0, 2) == "\\_" && (id_str[id_str.size()-1] == '_' || id_str.find("_[") != std::string::npos))
 199                 return false;
 200         if (id_str.find(".$") != std::string::npos)
 201                 return false;
 202         return true;
 203 }
 204
 205 void rmunused_module_signals(RTLIL::Module *module, bool purge_mode, bool verbose)
 206 {
 207         SigPool register_signals;
 208         SigPool connected_signals;
 209
 210         if (!purge_mode)
 211                 for (auto &it : module->cells_) {
 212                         RTLIL::Cell *cell = it.second;
 213                         if (ct_reg.cell_known(cell->type))
 214                                 for (auto &it2 : cell->connections())
 215                                         if (ct_reg.cell_output(cell->type, it2.first))
 216                                                 register_signals.add(it2.second);
 217                         for (auto &it2 : cell->connections())
 218                                 connected_signals.add(it2.second);
 219                 }
 220
 221         SigMap assign_map(module);
 222         pool<RTLIL::SigSpec> direct_sigs;
 223         pool<RTLIL::Wire*> direct_wires;
 224         for (auto &it : module->cells_) {
 225                 RTLIL::Cell *cell = it.second;
 226                 if (ct_all.cell_known(cell->type))
 227                         for (auto &it2 : cell->connections())
 228                                 if (ct_all.cell_output(cell->type, it2.first))
 229                                         direct_sigs.insert(assign_map(it2.second));
 230         }
 231         for (auto &it : module->wires_) {
 232                 if (direct_sigs.count(assign_map(it.second)) || it.second->port_input)
 233                         direct_wires.insert(it.second);
 234         }
 235
 236         for (auto &it : module->wires_) {
 237                 RTLIL::Wire *wire = it.second;
 238                 for (int i = 0; i < wire->width; i++) {
 239                         RTLIL::SigBit s1 = RTLIL::SigBit(wire, i), s2 = assign_map(s1);
 240                         if (!compare_signals(s1, s2, register_signals, connected_signals, direct_wires))
 241                                 assign_map.add(s1);
 242                 }
 243         }
 244
 245         SigPool raw_used_signals_noaliases;
 246         for (auto &it : module->connections_)
 247                 raw_used_signals_noaliases.add(it.second);
 248
 249         module->connections_.clear();
 250
 251         SigPool used_signals;
 252         SigPool used_signals_nodrivers;
 253         for (auto &it : module->cells_) {
 254                 RTLIL::Cell *cell = it.second;
 255                 for (auto &it2 : cell->connections_) {
 256                         assign_map.apply(it2.second);
 257                         used_signals.add(it2.second);
 258                         raw_used_signals_noaliases.add(it2.second);
 259                         if (!ct_all.cell_output(cell->type, it2.first))
 260                                 used_signals_nodrivers.add(it2.second);
 261                 }
 262         }
 263         for (auto &it : module->wires_) {
 264                 RTLIL::Wire *wire = it.second;
 265                 if (wire->port_id > 0) {
 266                         RTLIL::SigSpec sig = RTLIL::SigSpec(wire);
 267                         assign_map.apply(sig);
 268                         used_signals.add(sig);
 269                         if (!wire->port_input)
 270                                 used_signals_nodrivers.add(sig);
 271                 }
 272                 if (wire->get_bool_attribute("\\keep")) {
 273                         RTLIL::SigSpec sig = RTLIL::SigSpec(wire);
 274                         assign_map.apply(sig);
 275                         used_signals.add(sig);
 276                 }
 277         }
 278
 279         std::vector<RTLIL::Wire*> maybe_del_wires;
 280         for (auto wire : module->wires())
 281         {
 282                 SigSpec s1 = SigSpec(wire), s2 = assign_map(s1);
 283                 log_assert(GetSize(s1) == GetSize(s2));
 284
 285                 Const initval;
 286                 if (wire->attributes.count("\\init"))
 287                         initval = wire->attributes.at("\\init");
 288                 if (GetSize(initval) != GetSize(wire))
 289                         initval.bits.resize(GetSize(wire), State::Sx);
 290                 if (initval.is_fully_undef())
 291                         wire->attributes.erase("\\init");
 292
 293                 bool maybe_del = false;
 294                 if (wire->port_id != 0 || wire->get_bool_attribute("\\keep") || !initval.is_fully_undef()) {
 295                         /* do not delete anything with "keep" or module ports or initialized wires */
 296                 } else
 297                 if (!purge_mode && check_public_name(wire->name)) {
 298                         /* do not get rid of public names unless in purge mode */
 299                 } else {
 300                         if (!raw_used_signals_noaliases.check_any(s1))
 301                                 maybe_del = true;
 302                         if (!used_signals_nodrivers.check_any(s2))
 303                                 maybe_del = true;
 304                 }
 305
 306                 if (maybe_del) {
 307                         maybe_del_wires.push_back(wire);
 308                 } else {
 309                         RTLIL::SigSig new_conn;
 310                         for (int i = 0; i < GetSize(s1); i++)
 311                                 if (s1[i] != s2[i]) {
 312                                         if (s2[i] == State::Sx && (initval[i] == State::S0 || initval[i] == State::S1)) {
 313                                                 s2[i] = initval[i];
 314                                                 initval[i] = State::Sx;
 315                                         }
 316                                         new_conn.first.append_bit(s1[i]);
 317                                         new_conn.second.append_bit(s2[i]);
 318                                 }
 319                         if (new_conn.first.size() > 0) {
 320                                 if (initval.is_fully_undef())
 321                                         wire->attributes.erase("\\init");
 322                                 else
 323                                         wire->attributes.at("\\init") = initval;
 324                                 used_signals.add(new_conn.first);
 325                                 used_signals.add(new_conn.second);
 326                                 module->connect(new_conn);
 327                         }
 328                 }
 329
 330                 if (!used_signals_nodrivers.check_all(s2)) {
 331                         std::string unused_bits;
 332                         for (int i = 0; i < GetSize(s2); i++) {
 333                                 if (s2[i].wire == NULL)
 334                                         continue;
 335                                 if (!used_signals_nodrivers.check(s2[i])) {
 336                                         if (!unused_bits.empty())
 337                                                 unused_bits += " ";
 338                                         unused_bits += stringf("%d", i);
 339                                 }
 340                         }
 341                         if (unused_bits.empty() || wire->port_id != 0)
 342                                 wire->attributes.erase("\\unused_bits");
 343                         else
 344                                 wire->attributes["\\unused_bits"] = RTLIL::Const(unused_bits);
 345                 } else {
 346                         wire->attributes.erase("\\unused_bits");
 347                 }
 348         }
 349
 350
 351         pool<RTLIL::Wire*> del_wires;
 352
 353         int del_wires_count = 0;
 354         for (auto wire : maybe_del_wires) {
 355                 SigSpec s1 = SigSpec(wire);
 356                 if (used_signals_nodrivers.check_any(s1)) {
 357                         SigSpec s2 = assign_map(s1);
 358                         Const initval;
 359                         if (wire->attributes.count("\\init"))
 360                                 initval = wire->attributes.at("\\init");
 361                         if (GetSize(initval) != GetSize(wire))
 362                                 initval.bits.resize(GetSize(wire), State::Sx);
 363                         RTLIL::SigSig new_conn;
 364                         for (int i = 0; i < GetSize(s1); i++)
 365                                 if (s1[i] != s2[i]) {
 366                                         if (s2[i] == State::Sx && (initval[i] == State::S0 || initval[i] == State::S1)) {
 367                                                 s2[i] = initval[i];
 368                                                 initval[i] = State::Sx;
 369                                         }
 370                                         new_conn.first.append_bit(s1[i]);
 371                                         new_conn.second.append_bit(s2[i]);
 372                                 }
 373                         if (new_conn.first.size() > 0) {
 374                                 if (initval.is_fully_undef())
 375                                         wire->attributes.erase("\\init");
 376                                 else
 377                                         wire->attributes.at("\\init") = initval;
 378                                 module->connect(new_conn);
 379                         }
 380                 } else {
 381                         if (ys_debug() || (check_public_name(wire->name) && verbose)) {
 382                                 log_debug("  removing unused non-port wire %s.\n", wire->name.c_str());
 383                         }
 384                         del_wires.insert(wire);
 385                         del_wires_count++;
 386                 }
 387         }
 388
 389         module->remove(del_wires);
 390         count_rm_wires += del_wires.size();
 391
 392         if (verbose && del_wires_count > 0)
 393                 log_debug("  removed %d unused temporary wires.\n", del_wires_count);
 394 }
 395
 396 bool rmunused_module_init(RTLIL::Module *module, bool purge_mode, bool verbose)
 397 {
 398         bool did_something = false;
 399         CellTypes fftypes;
 400         fftypes.setup_internals_mem();
 401
 402         SigMap sigmap(module);
 403         dict<SigBit, State> qbits;
 404
 405         for (auto cell : module->cells())
 406                 if (fftypes.cell_known(cell->type) && cell->hasPort("\\Q"))
 407                 {
 408                         SigSpec sig = cell->getPort("\\Q");
 409
 410                         for (int i = 0; i < GetSize(sig); i++)
 411                         {
 412                                 SigBit bit = sig[i];
 413
 414                                 if (bit.wire == nullptr || bit.wire->attributes.count("\\init") == 0)
 415                                         continue;
 416
 417                                 Const init = bit.wire->attributes.at("\\init");
 418
 419                                 if (i >= GetSize(init) || init[i] == State::Sx || init[i] == State::Sz)
 420                                         continue;
 421
 422                                 sigmap.add(bit);
 423                                 qbits[bit] = init[i];
 424                         }
 425                 }
 426
 427         for (auto wire : module->wires())
 428         {
 429                 if (!purge_mode && wire->name[0] == '\\')
 430                         continue;
 431
 432                 if (wire->attributes.count("\\init") == 0)
 433                         continue;
 434
 435                 Const init = wire->attributes.at("\\init");
 436
 437                 for (int i = 0; i < GetSize(wire) && i < GetSize(init); i++)
 438                 {
 439                         if (init[i] == State::Sx || init[i] == State::Sz)
 440                                 continue;
 441
 442                         SigBit wire_bit = SigBit(wire, i);
 443                         SigBit mapped_wire_bit = sigmap(wire_bit);
 444
 445                         if (wire_bit == mapped_wire_bit)
 446                                 goto next_wire;
 447
 448                         if (qbits.count(sigmap(SigBit(wire, i))) == 0)
 449                                 goto next_wire;
 450
 451                         if (qbits.at(sigmap(SigBit(wire, i))) != init[i])
 452                                 goto next_wire;
 453                 }
 454
 455                 if (verbose)
 456                         log_debug("  removing redundant init attribute on %s.\n", log_id(wire));
 457
 458                 wire->attributes.erase("\\init");
 459                 did_something = true;
 460         next_wire:;
 461         }
 462
 463         return did_something;
 464 }
 465
 466 void rmunused_module(RTLIL::Module *module, bool purge_mode, bool verbose, bool rminit)
 467 {
 468         if (verbose)
 469                 log("Finding unused cells or wires in module %s..\n", module->name.c_str());
 470
 471         std::vector<RTLIL::Cell*> delcells;
 472         for (auto cell : module->cells())
 473                 if (cell->type.in("$pos", "$_BUF_")) {
 474                         bool is_signed = cell->type == "$pos" && cell->getParam("\\A_SIGNED").as_bool();
 475                         RTLIL::SigSpec a = cell->getPort("\\A");
 476                         RTLIL::SigSpec y = cell->getPort("\\Y");
 477                         a.extend_u0(GetSize(y), is_signed);
 478                         module->connect(y, a);
 479                         delcells.push_back(cell);
 480                 }
 481         for (auto cell : delcells) {
 482                 if (verbose)
 483                         log_debug("  removing buffer cell `%s': %s = %s\n", cell->name.c_str(),
 484                                         log_signal(cell->getPort("\\Y")), log_signal(cell->getPort("\\A")));
 485                 module->remove(cell);
 486         }
 487         if (!delcells.empty())
 488                 module->design->scratchpad_set_bool("opt.did_something", true);
 489
 490         rmunused_module_cells(module, verbose);
 491         rmunused_module_signals(module, purge_mode, verbose);
 492
 493         if (rminit && rmunused_module_init(module, purge_mode, verbose))
 494                 rmunused_module_signals(module, purge_mode, verbose);
 495 }
 496
 497 struct OptCleanPass : public Pass {
 498         OptCleanPass() : Pass("opt_clean", "remove unused cells and wires") { }
 499         void help() YS_OVERRIDE
 500         {
 501                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 502                 log("\n");
 503                 log("    opt_clean [options] [selection]\n");
 504                 log("\n");
 505                 log("This pass identifies wires and cells that are unused and removes them. Other\n");
 506                 log("passes often remove cells but leave the wires in the design or reconnect the\n");
 507                 log("wires but leave the old cells in the design. This pass can be used to clean up\n");
 508                 log("after the passes that do the actual work.\n");
 509                 log("\n");
 510                 log("This pass only operates on completely selected modules without processes.\n");
 511                 log("\n");
 512                 log("    -purge\n");
 513                 log("        also remove internal nets if they have a public name\n");
 514                 log("\n");
 515         }
 516         void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
 517         {
 518                 bool purge_mode = false;
 519
 520                 log_header(design, "Executing OPT_CLEAN pass (remove unused cells and wires).\n");
 521                 log_push();
 522
 523                 size_t argidx;
 524                 for (argidx = 1; argidx < args.size(); argidx++) {
 525                         if (args[argidx] == "-purge") {
 526                                 purge_mode = true;
 527                                 continue;
 528                         }
 529                         break;
 530                 }
 531                 extra_args(args, argidx, design);
 532
 533                 keep_cache.reset(design);
 534
 535                 ct_reg.setup_internals_mem();
 536                 ct_reg.setup_stdcells_mem();
 537
 538                 ct_all.setup(design);
 539
 540                 count_rm_cells = 0;
 541                 count_rm_wires = 0;
 542
 543                 for (auto module : design->selected_whole_modules_warn()) {
 544                         if (module->has_processes_warn())
 545                                 continue;
 546                         rmunused_module(module, purge_mode, true, true);
 547                 }
 548
 549                 if (count_rm_cells > 0 || count_rm_wires > 0)
 550                         log("Removed %d unused cells and %d unused wires.\n", count_rm_cells, count_rm_wires);
 551
 552                 design->optimize();
 553                 design->sort();
 554                 design->check();
 555
 556                 keep_cache.reset();
 557                 ct_reg.clear();
 558                 ct_all.clear();
 559                 log_pop();
 560         }
 561 } OptCleanPass;
 562
 563 struct CleanPass : public Pass {
 564         CleanPass() : Pass("clean", "remove unused cells and wires") { }
 565         void help() YS_OVERRIDE
 566         {
 567                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 568                 log("\n");
 569                 log("    clean [options] [selection]\n");
 570                 log("\n");
 571                 log("This is identical to 'opt_clean', but less verbose.\n");
 572                 log("\n");
 573                 log("When commands are separated using the ';;' token, this command will be executed\n");
 574                 log("between the commands.\n");
 575                 log("\n");
 576                 log("When commands are separated using the ';;;' token, this command will be executed\n");
 577                 log("in -purge mode between the commands.\n");
 578                 log("\n");
 579         }
 580         void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
 581         {
 582                 bool purge_mode = false;
 583
 584                 size_t argidx;
 585                 for (argidx = 1; argidx < args.size(); argidx++) {
 586                         if (args[argidx] == "-purge") {
 587                                 purge_mode = true;
 588                                 continue;
 589                         }
 590                         break;
 591                 }
 592                 if (argidx < args.size())
 593                         extra_args(args, argidx, design);
 594
 595                 keep_cache.reset(design);
 596
 597                 ct_reg.setup_internals_mem();
 598                 ct_reg.setup_stdcells_mem();
 599
 600                 ct_all.setup(design);
 601
 602                 count_rm_cells = 0;
 603                 count_rm_wires = 0;
 604
 605                 for (auto module : design->selected_whole_modules()) {
 606                         if (module->has_processes())
 607                                 continue;
 608                         rmunused_module(module, purge_mode, ys_debug(), false);
 609                 }
 610
 611                 log_suppressed();
 612                 if (count_rm_cells > 0 || count_rm_wires > 0)
 613                         log("Removed %d unused cells and %d unused wires.\n", count_rm_cells, count_rm_wires);
 614
 615                 design->optimize();
 616                 design->sort();
 617                 design->check();
 618
 619                 keep_cache.reset();
 620                 ct_reg.clear();
 621                 ct_all.clear();
 622         }
 623 } CleanPass;
 624
 625 PRIVATE_NAMESPACE_END