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("  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         module->connections_.clear();
 246
 247         SigPool used_signals;
 248         SigPool used_signals_nodrivers;
 249         for (auto &it : module->cells_) {
 250                 RTLIL::Cell *cell = it.second;
 251                 for (auto &it2 : cell->connections_) {
 252                         assign_map.apply(it2.second);
 253                         used_signals.add(it2.second);
 254                         if (!ct_all.cell_output(cell->type, it2.first))
 255                                 used_signals_nodrivers.add(it2.second);
 256                 }
 257         }
 258         for (auto &it : module->wires_) {
 259                 RTLIL::Wire *wire = it.second;
 260                 if (wire->port_id > 0) {
 261                         RTLIL::SigSpec sig = RTLIL::SigSpec(wire);
 262                         assign_map.apply(sig);
 263                         used_signals.add(sig);
 264                         if (!wire->port_input)
 265                                 used_signals_nodrivers.add(sig);
 266                 }
 267                 if (wire->get_bool_attribute("\\keep")) {
 268                         RTLIL::SigSpec sig = RTLIL::SigSpec(wire);
 269                         assign_map.apply(sig);
 270                         used_signals.add(sig);
 271                 }
 272         }
 273
 274         std::vector<RTLIL::Wire*> maybe_del_wires;
 275         for (auto wire : module->wires())
 276         {
 277                 if ((!purge_mode && check_public_name(wire->name)) || wire->port_id != 0 || wire->get_bool_attribute("\\keep") || wire->attributes.count("\\init")) {
 278                         RTLIL::SigSpec s1 = RTLIL::SigSpec(wire), s2 = s1;
 279                         assign_map.apply(s2);
 280                         if (!used_signals.check_any(s2) && wire->port_id == 0 && !wire->get_bool_attribute("\\keep")) {
 281                                 maybe_del_wires.push_back(wire);
 282                         } else {
 283                                 log_assert(GetSize(s1) == GetSize(s2));
 284                                 RTLIL::SigSig new_conn;
 285                                 for (int i = 0; i < GetSize(s1); i++)
 286                                         if (s1[i] != s2[i]) {
 287                                                 new_conn.first.append_bit(s1[i]);
 288                                                 new_conn.second.append_bit(s2[i]);
 289                                         }
 290                                 if (new_conn.first.size() > 0) {
 291                                         used_signals.add(new_conn.first);
 292                                         used_signals.add(new_conn.second);
 293                                         module->connect(new_conn);
 294                                 }
 295                         }
 296                 } else {
 297                         if (!used_signals.check_any(RTLIL::SigSpec(wire)))
 298                                 maybe_del_wires.push_back(wire);
 299                 }
 300
 301                 RTLIL::SigSpec sig = assign_map(RTLIL::SigSpec(wire));
 302                 if (!used_signals_nodrivers.check_any(sig)) {
 303                         std::string unused_bits;
 304                         for (int i = 0; i < GetSize(sig); i++) {
 305                                 if (sig[i].wire == NULL)
 306                                         continue;
 307                                 if (!used_signals_nodrivers.check(sig[i])) {
 308                                         if (!unused_bits.empty())
 309                                                 unused_bits += " ";
 310                                         unused_bits += stringf("%d", i);
 311                                 }
 312                         }
 313                         if (unused_bits.empty() || wire->port_id != 0)
 314                                 wire->attributes.erase("\\unused_bits");
 315                         else
 316                                 wire->attributes["\\unused_bits"] = RTLIL::Const(unused_bits);
 317                 } else {
 318                         wire->attributes.erase("\\unused_bits");
 319                 }
 320         }
 321
 322
 323         pool<RTLIL::Wire*> del_wires;
 324
 325         int del_wires_count = 0;
 326         for (auto wire : maybe_del_wires)
 327                 if (!used_signals.check_any(RTLIL::SigSpec(wire))) {
 328                         if (check_public_name(wire->name) && verbose) {
 329                                 log("  removing unused non-port wire %s.\n", wire->name.c_str());
 330                         }
 331                         del_wires.insert(wire);
 332                         del_wires_count++;
 333                 }
 334
 335         module->remove(del_wires);
 336         count_rm_wires += del_wires.size();
 337
 338         if (verbose && del_wires_count > 0)
 339                 log("  removed %d unused temporary wires.\n", del_wires_count);
 340 }
 341
 342 bool rmunused_module_init(RTLIL::Module *module, bool purge_mode, bool verbose)
 343 {
 344         bool did_something = false;
 345         CellTypes fftypes;
 346         fftypes.setup_internals_mem();
 347
 348         SigMap sigmap(module);
 349         dict<SigBit, State> qbits;
 350
 351         for (auto cell : module->cells())
 352                 if (fftypes.cell_known(cell->type) && cell->hasPort("\\Q"))
 353                 {
 354                         SigSpec sig = cell->getPort("\\Q");
 355
 356                         for (int i = 0; i < GetSize(sig); i++)
 357                         {
 358                                 SigBit bit = sig[i];
 359
 360                                 if (bit.wire == nullptr || bit.wire->attributes.count("\\init") == 0)
 361                                         continue;
 362
 363                                 Const init = bit.wire->attributes.at("\\init");
 364
 365                                 if (i >= GetSize(init) || init[i] == State::Sx || init[i] == State::Sz)
 366                                         continue;
 367
 368                                 sigmap.add(bit);
 369                                 qbits[bit] = init[i];
 370                         }
 371                 }
 372
 373         for (auto wire : module->wires())
 374         {
 375                 if (!purge_mode && wire->name[0] == '\\')
 376                         continue;
 377
 378                 if (wire->attributes.count("\\init") == 0)
 379                         continue;
 380
 381                 Const init = wire->attributes.at("\\init");
 382
 383                 for (int i = 0; i < GetSize(wire) && i < GetSize(init); i++)
 384                 {
 385                         if (init[i] == State::Sx || init[i] == State::Sz)
 386                                 continue;
 387
 388                         SigBit wire_bit = SigBit(wire, i);
 389                         SigBit mapped_wire_bit = sigmap(wire_bit);
 390
 391                         if (wire_bit == mapped_wire_bit)
 392                                 goto next_wire;
 393
 394                         if (qbits.count(sigmap(SigBit(wire, i))) == 0)
 395                                 goto next_wire;
 396
 397                         if (qbits.at(sigmap(SigBit(wire, i))) != init[i])
 398                                 goto next_wire;
 399                 }
 400
 401                 if (verbose)
 402                         log("  removing redundant init attribute on %s.\n", log_id(wire));
 403
 404                 wire->attributes.erase("\\init");
 405                 did_something = true;
 406         next_wire:;
 407         }
 408
 409         return did_something;
 410 }
 411
 412 void rmunused_module(RTLIL::Module *module, bool purge_mode, bool verbose, bool rminit)
 413 {
 414         if (verbose)
 415                 log("Finding unused cells or wires in module %s..\n", module->name.c_str());
 416
 417         std::vector<RTLIL::Cell*> delcells;
 418         for (auto cell : module->cells())
 419                 if (cell->type.in("$pos", "$_BUF_")) {
 420                         bool is_signed = cell->type == "$pos" && cell->getParam("\\A_SIGNED").as_bool();
 421                         RTLIL::SigSpec a = cell->getPort("\\A");
 422                         RTLIL::SigSpec y = cell->getPort("\\Y");
 423                         a.extend_u0(GetSize(y), is_signed);
 424                         module->connect(y, a);
 425                         delcells.push_back(cell);
 426                 }
 427         for (auto cell : delcells) {
 428                 if (verbose)
 429                         log("  removing buffer cell `%s': %s = %s\n", cell->name.c_str(),
 430                                         log_signal(cell->getPort("\\Y")), log_signal(cell->getPort("\\A")));
 431                 module->remove(cell);
 432         }
 433         if (!delcells.empty())
 434                 module->design->scratchpad_set_bool("opt.did_something", true);
 435
 436         rmunused_module_cells(module, verbose);
 437         rmunused_module_signals(module, purge_mode, verbose);
 438
 439         if (rminit && rmunused_module_init(module, purge_mode, verbose))
 440                 rmunused_module_signals(module, purge_mode, verbose);
 441 }
 442
 443 struct OptCleanPass : public Pass {
 444         OptCleanPass() : Pass("opt_clean", "remove unused cells and wires") { }
 445         void help() YS_OVERRIDE
 446         {
 447                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 448                 log("\n");
 449                 log("    opt_clean [options] [selection]\n");
 450                 log("\n");
 451                 log("This pass identifies wires and cells that are unused and removes them. Other\n");
 452                 log("passes often remove cells but leave the wires in the design or reconnect the\n");
 453                 log("wires but leave the old cells in the design. This pass can be used to clean up\n");
 454                 log("after the passes that do the actual work.\n");
 455                 log("\n");
 456                 log("This pass only operates on completely selected modules without processes.\n");
 457                 log("\n");
 458                 log("    -purge\n");
 459                 log("        also remove internal nets if they have a public name\n");
 460                 log("\n");
 461         }
 462         void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
 463         {
 464                 bool purge_mode = false;
 465
 466                 log_header(design, "Executing OPT_CLEAN pass (remove unused cells and wires).\n");
 467                 log_push();
 468
 469                 size_t argidx;
 470                 for (argidx = 1; argidx < args.size(); argidx++) {
 471                         if (args[argidx] == "-purge") {
 472                                 purge_mode = true;
 473                                 continue;
 474                         }
 475                         break;
 476                 }
 477                 extra_args(args, argidx, design);
 478
 479                 keep_cache.reset(design);
 480
 481                 ct_reg.setup_internals_mem();
 482                 ct_reg.setup_stdcells_mem();
 483
 484                 ct_all.setup(design);
 485
 486                 for (auto module : design->selected_whole_modules_warn()) {
 487                         if (module->has_processes_warn())
 488                                 continue;
 489                         rmunused_module(module, purge_mode, true, true);
 490                 }
 491
 492                 if (count_rm_cells > 0 || count_rm_wires > 0)
 493                         log("Removed %d unused cells and %d unused wires.\n", count_rm_cells, count_rm_wires);
 494
 495                 design->optimize();
 496                 design->sort();
 497                 design->check();
 498
 499                 keep_cache.reset();
 500                 ct_reg.clear();
 501                 ct_all.clear();
 502                 log_pop();
 503         }
 504 } OptCleanPass;
 505
 506 struct CleanPass : public Pass {
 507         CleanPass() : Pass("clean", "remove unused cells and wires") { }
 508         void help() YS_OVERRIDE
 509         {
 510                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 511                 log("\n");
 512                 log("    clean [options] [selection]\n");
 513                 log("\n");
 514                 log("This is identical to 'opt_clean', but less verbose.\n");
 515                 log("\n");
 516                 log("When commands are separated using the ';;' token, this command will be executed\n");
 517                 log("between the commands.\n");
 518                 log("\n");
 519                 log("When commands are separated using the ';;;' token, this command will be executed\n");
 520                 log("in -purge mode between the commands.\n");
 521                 log("\n");
 522         }
 523         void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
 524         {
 525                 bool purge_mode = false;
 526
 527                 size_t argidx;
 528                 for (argidx = 1; argidx < args.size(); argidx++) {
 529                         if (args[argidx] == "-purge") {
 530                                 purge_mode = true;
 531                                 continue;
 532                         }
 533                         break;
 534                 }
 535                 if (argidx < args.size())
 536                         extra_args(args, argidx, design);
 537
 538                 keep_cache.reset(design);
 539
 540                 ct_reg.setup_internals_mem();
 541                 ct_reg.setup_stdcells_mem();
 542
 543                 ct_all.setup(design);
 544
 545                 count_rm_cells = 0;
 546                 count_rm_wires = 0;
 547
 548                 for (auto module : design->selected_whole_modules()) {
 549                         if (module->has_processes())
 550                                 continue;
 551                         rmunused_module(module, purge_mode, false, false);
 552                 }
 553
 554                 if (count_rm_cells > 0 || count_rm_wires > 0)
 555                         log("Removed %d unused cells and %d unused wires.\n", count_rm_cells, count_rm_wires);
 556
 557                 design->optimize();
 558                 design->sort();
 559                 design->check();
 560
 561                 keep_cache.reset();
 562                 ct_reg.clear();
 563                 ct_all.clear();
 564         }
 565 } CleanPass;
 566
 567 PRIVATE_NAMESPACE_END