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