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 bit : sigmap(it2.second))
  95                                         if (bit.wire != nullptr)
  96                                                 wire2driver[bit].insert(cell);
  97                 }
  98                 if (keep_cache.query(cell))
  99                         queue.insert(cell);
 100                 else
 101                         unused.insert(cell);
 102         }
 103
 104         for (auto &it : module->wires_) {
 105                 Wire *wire = it.second;
 106                 if (wire->port_output || wire->get_bool_attribute("\\keep")) {
 107                         for (auto bit : sigmap(wire))
 108                         for (auto c : wire2driver[bit])
 109                                 queue.insert(c), unused.erase(c);
 110                 }
 111         }
 112
 113         while (!queue.empty())
 114         {
 115                 pool<SigBit> bits;
 116                 for (auto cell : queue)
 117                 for (auto &it : cell->connections())
 118                         if (!ct_all.cell_known(cell->type) || ct_all.cell_input(cell->type, it.first))
 119                                 for (auto bit : sigmap(it.second))
 120                                         bits.insert(bit);
 121
 122                 queue.clear();
 123                 for (auto bit : bits)
 124                 for (auto c : wire2driver[bit])
 125                         if (unused.count(c))
 126                                 queue.insert(c), unused.erase(c);
 127         }
 128
 129         unused.sort(RTLIL::sort_by_name_id<RTLIL::Cell>());
 130
 131         for (auto cell : unused) {
 132                 if (verbose)
 133                         log("  removing unused `%s' cell `%s'.\n", cell->type.c_str(), cell->name.c_str());
 134                 module->design->scratchpad_set_bool("opt.did_something", true);
 135                 module->remove(cell);
 136                 count_rm_cells++;
 137         }
 138 }
 139
 140 int count_nontrivial_wire_attrs(RTLIL::Wire *w)
 141 {
 142         int count = w->attributes.size();
 143         count -= w->attributes.count("\\src");
 144         count -= w->attributes.count("\\unused_bits");
 145         return count;
 146 }
 147
 148 bool compare_signals(RTLIL::SigBit &s1, RTLIL::SigBit &s2, SigPool &regs, SigPool &conns, pool<RTLIL::Wire*> &direct_wires)
 149 {
 150         RTLIL::Wire *w1 = s1.wire;
 151         RTLIL::Wire *w2 = s2.wire;
 152
 153         if (w1 == NULL || w2 == NULL)
 154                 return w2 == NULL;
 155
 156         if (w1->port_input != w2->port_input)
 157                 return w2->port_input;
 158
 159         if ((w1->port_input && w1->port_output) != (w2->port_input && w2->port_output))
 160                 return !(w2->port_input && w2->port_output);
 161
 162         if (w1->name[0] == '\\' && w2->name[0] == '\\') {
 163                 if (regs.check_any(s1) != regs.check_any(s2))
 164                         return regs.check_any(s2);
 165                 if (direct_wires.count(w1) != direct_wires.count(w2))
 166                         return direct_wires.count(w2) != 0;
 167                 if (conns.check_any(s1) != conns.check_any(s2))
 168                         return conns.check_any(s2);
 169         }
 170
 171         if (w1->port_output != w2->port_output)
 172                 return w2->port_output;
 173
 174         if (w1->name[0] != w2->name[0])
 175                 return w2->name[0] == '\\';
 176
 177         int attrs1 = count_nontrivial_wire_attrs(w1);
 178         int attrs2 = count_nontrivial_wire_attrs(w2);
 179
 180         if (attrs1 != attrs2)
 181                 return attrs2 > attrs1;
 182
 183         return strcmp(w2->name.c_str(), w1->name.c_str()) < 0;
 184 }
 185
 186 bool check_public_name(RTLIL::IdString id)
 187 {
 188         const std::string &id_str = id.str();
 189         if (id_str[0] == '$')
 190                 return false;
 191         if (id_str.substr(0, 2) == "\\_" && (id_str[id_str.size()-1] == '_' || id_str.find("_[") != std::string::npos))
 192                 return false;
 193         if (id_str.find(".$") != std::string::npos)
 194                 return false;
 195         return true;
 196 }
 197
 198 void rmunused_module_signals(RTLIL::Module *module, bool purge_mode, bool verbose)
 199 {
 200         SigPool register_signals;
 201         SigPool connected_signals;
 202
 203         if (!purge_mode)
 204                 for (auto &it : module->cells_) {
 205                         RTLIL::Cell *cell = it.second;
 206                         if (ct_reg.cell_known(cell->type))
 207                                 for (auto &it2 : cell->connections())
 208                                         if (ct_reg.cell_output(cell->type, it2.first))
 209                                                 register_signals.add(it2.second);
 210                         for (auto &it2 : cell->connections())
 211                                 connected_signals.add(it2.second);
 212                 }
 213
 214         SigMap assign_map(module);
 215         pool<RTLIL::SigSpec> direct_sigs;
 216         pool<RTLIL::Wire*> direct_wires;
 217         for (auto &it : module->cells_) {
 218                 RTLIL::Cell *cell = it.second;
 219                 if (ct_all.cell_known(cell->type))
 220                         for (auto &it2 : cell->connections())
 221                                 if (ct_all.cell_output(cell->type, it2.first))
 222                                         direct_sigs.insert(assign_map(it2.second));
 223         }
 224         for (auto &it : module->wires_) {
 225                 if (direct_sigs.count(assign_map(it.second)) || it.second->port_input)
 226                         direct_wires.insert(it.second);
 227         }
 228
 229         for (auto &it : module->wires_) {
 230                 RTLIL::Wire *wire = it.second;
 231                 for (int i = 0; i < wire->width; i++) {
 232                         RTLIL::SigBit s1 = RTLIL::SigBit(wire, i), s2 = assign_map(s1);
 233                         if (!compare_signals(s1, s2, register_signals, connected_signals, direct_wires))
 234                                 assign_map.add(s1);
 235                 }
 236         }
 237
 238         module->connections_.clear();
 239
 240         SigPool used_signals;
 241         SigPool used_signals_nodrivers;
 242         for (auto &it : module->cells_) {
 243                 RTLIL::Cell *cell = it.second;
 244                 for (auto &it2 : cell->connections_) {
 245                         assign_map.apply(it2.second);
 246                         used_signals.add(it2.second);
 247                         if (!ct_all.cell_output(cell->type, it2.first))
 248                                 used_signals_nodrivers.add(it2.second);
 249                 }
 250         }
 251         for (auto &it : module->wires_) {
 252                 RTLIL::Wire *wire = it.second;
 253                 if (wire->port_id > 0) {
 254                         RTLIL::SigSpec sig = RTLIL::SigSpec(wire);
 255                         assign_map.apply(sig);
 256                         used_signals.add(sig);
 257                         if (!wire->port_input)
 258                                 used_signals_nodrivers.add(sig);
 259                 }
 260                 if (wire->get_bool_attribute("\\keep")) {
 261                         RTLIL::SigSpec sig = RTLIL::SigSpec(wire);
 262                         assign_map.apply(sig);
 263                         used_signals.add(sig);
 264                 }
 265         }
 266
 267         std::vector<RTLIL::Wire*> maybe_del_wires;
 268         for (auto wire : module->wires())
 269         {
 270                 if ((!purge_mode && check_public_name(wire->name)) || wire->port_id != 0 || wire->get_bool_attribute("\\keep") || wire->attributes.count("\\init")) {
 271                         RTLIL::SigSpec s1 = RTLIL::SigSpec(wire), s2 = s1;
 272                         assign_map.apply(s2);
 273                         if (!used_signals.check_any(s2) && wire->port_id == 0 && !wire->get_bool_attribute("\\keep")) {
 274                                 maybe_del_wires.push_back(wire);
 275                         } else {
 276                                 log_assert(GetSize(s1) == GetSize(s2));
 277                                 RTLIL::SigSig new_conn;
 278                                 for (int i = 0; i < GetSize(s1); i++)
 279                                         if (s1[i] != s2[i]) {
 280                                                 new_conn.first.append_bit(s1[i]);
 281                                                 new_conn.second.append_bit(s2[i]);
 282                                         }
 283                                 if (new_conn.first.size() > 0) {
 284                                         used_signals.add(new_conn.first);
 285                                         used_signals.add(new_conn.second);
 286                                         module->connect(new_conn);
 287                                 }
 288                         }
 289                 } else {
 290                         if (!used_signals.check_any(RTLIL::SigSpec(wire)))
 291                                 maybe_del_wires.push_back(wire);
 292                 }
 293
 294                 RTLIL::SigSpec sig = assign_map(RTLIL::SigSpec(wire));
 295                 if (!used_signals_nodrivers.check_any(sig)) {
 296                         std::string unused_bits;
 297                         for (int i = 0; i < GetSize(sig); i++) {
 298                                 if (sig[i].wire == NULL)
 299                                         continue;
 300                                 if (!used_signals_nodrivers.check(sig[i])) {
 301                                         if (!unused_bits.empty())
 302                                                 unused_bits += " ";
 303                                         unused_bits += stringf("%d", i);
 304                                 }
 305                         }
 306                         if (unused_bits.empty() || wire->port_id != 0)
 307                                 wire->attributes.erase("\\unused_bits");
 308                         else
 309                                 wire->attributes["\\unused_bits"] = RTLIL::Const(unused_bits);
 310                 } else {
 311                         wire->attributes.erase("\\unused_bits");
 312                 }
 313         }
 314
 315
 316         pool<RTLIL::Wire*> del_wires;
 317
 318         int del_wires_count = 0;
 319         for (auto wire : maybe_del_wires)
 320                 if (!used_signals.check_any(RTLIL::SigSpec(wire))) {
 321                         if (check_public_name(wire->name) && verbose) {
 322                                 log("  removing unused non-port wire %s.\n", wire->name.c_str());
 323                         }
 324                         del_wires.insert(wire);
 325                         del_wires_count++;
 326                 }
 327
 328         module->remove(del_wires);
 329         count_rm_wires += del_wires.size();
 330
 331         if (verbose && del_wires_count > 0)
 332                 log("  removed %d unused temporary wires.\n", del_wires_count);
 333 }
 334
 335 bool rmunused_module_init(RTLIL::Module *module, bool purge_mode, bool verbose)
 336 {
 337         bool did_something = false;
 338         CellTypes fftypes;
 339         fftypes.setup_internals_mem();
 340
 341         SigMap sigmap(module);
 342         dict<SigBit, State> qbits;
 343
 344         for (auto cell : module->cells())
 345                 if (fftypes.cell_known(cell->type) && cell->hasPort("\\Q"))
 346                 {
 347                         SigSpec sig = cell->getPort("\\Q");
 348
 349                         for (int i = 0; i < GetSize(sig); i++)
 350                         {
 351                                 SigBit bit = sig[i];
 352
 353                                 if (bit.wire == nullptr || bit.wire->attributes.count("\\init") == 0)
 354                                         continue;
 355
 356                                 Const init = bit.wire->attributes.at("\\init");
 357
 358                                 if (i >= GetSize(init) || init[i] == State::Sx || init[i] == State::Sz)
 359                                         continue;
 360
 361                                 sigmap.add(bit);
 362                                 qbits[bit] = init[i];
 363                         }
 364                 }
 365
 366         for (auto wire : module->wires())
 367         {
 368                 if (!purge_mode && wire->name[0] == '\\')
 369                         continue;
 370
 371                 if (wire->attributes.count("\\init") == 0)
 372                         continue;
 373
 374                 Const init = wire->attributes.at("\\init");
 375
 376                 for (int i = 0; i < GetSize(wire) && i < GetSize(init); i++)
 377                 {
 378                         if (init[i] == State::Sx || init[i] == State::Sz)
 379                                 continue;
 380
 381                         SigBit wire_bit = SigBit(wire, i);
 382                         SigBit mapped_wire_bit = sigmap(wire_bit);
 383
 384                         if (wire_bit == mapped_wire_bit)
 385                                 goto next_wire;
 386
 387                         if (qbits.count(sigmap(SigBit(wire, i))) == 0)
 388                                 goto next_wire;
 389
 390                         if (qbits.at(sigmap(SigBit(wire, i))) != init[i])
 391                                 goto next_wire;
 392                 }
 393
 394                 if (verbose)
 395                         log("  removing redundent init attribute on %s.\n", log_id(wire));
 396
 397                 wire->attributes.erase("\\init");
 398                 did_something = true;
 399         next_wire:;
 400         }
 401
 402         return did_something;
 403 }
 404
 405 void rmunused_module(RTLIL::Module *module, bool purge_mode, bool verbose, bool rminit)
 406 {
 407         if (verbose)
 408                 log("Finding unused cells or wires in module %s..\n", module->name.c_str());
 409
 410         std::vector<RTLIL::Cell*> delcells;
 411         for (auto cell : module->cells())
 412                 if (cell->type.in("$pos", "$_BUF_")) {
 413                         bool is_signed = cell->type == "$pos" && cell->getParam("\\A_SIGNED").as_bool();
 414                         RTLIL::SigSpec a = cell->getPort("\\A");
 415                         RTLIL::SigSpec y = cell->getPort("\\Y");
 416                         a.extend_u0(GetSize(y), is_signed);
 417                         module->connect(y, a);
 418                         delcells.push_back(cell);
 419                 }
 420         for (auto cell : delcells) {
 421                 if (verbose)
 422                         log("  removing buffer cell `%s': %s = %s\n", cell->name.c_str(),
 423                                         log_signal(cell->getPort("\\Y")), log_signal(cell->getPort("\\A")));
 424                 module->remove(cell);
 425         }
 426         if (!delcells.empty())
 427                 module->design->scratchpad_set_bool("opt.did_something", true);
 428
 429         rmunused_module_cells(module, verbose);
 430         rmunused_module_signals(module, purge_mode, verbose);
 431
 432         if (rminit && rmunused_module_init(module, purge_mode, verbose))
 433                 rmunused_module_signals(module, purge_mode, verbose);
 434 }
 435
 436 struct OptCleanPass : public Pass {
 437         OptCleanPass() : Pass("opt_clean", "remove unused cells and wires") { }
 438         virtual void help()
 439         {
 440                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 441                 log("\n");
 442                 log("    opt_clean [options] [selection]\n");
 443                 log("\n");
 444                 log("This pass identifies wires and cells that are unused and removes them. Other\n");
 445                 log("passes often remove cells but leave the wires in the design or reconnect the\n");
 446                 log("wires but leave the old cells in the design. This pass can be used to clean up\n");
 447                 log("after the passes that do the actual work.\n");
 448                 log("\n");
 449                 log("This pass only operates on completely selected modules without processes.\n");
 450                 log("\n");
 451                 log("    -purge\n");
 452                 log("        also remove internal nets if they have a public name\n");
 453                 log("\n");
 454         }
 455         virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
 456         {
 457                 bool purge_mode = false;
 458
 459                 log_header(design, "Executing OPT_CLEAN pass (remove unused cells and wires).\n");
 460                 log_push();
 461
 462                 size_t argidx;
 463                 for (argidx = 1; argidx < args.size(); argidx++) {
 464                         if (args[argidx] == "-purge") {
 465                                 purge_mode = true;
 466                                 continue;
 467                         }
 468                         break;
 469                 }
 470                 extra_args(args, argidx, design);
 471
 472                 keep_cache.reset(design);
 473
 474                 ct_reg.setup_internals_mem();
 475                 ct_reg.setup_stdcells_mem();
 476
 477                 ct_all.setup(design);
 478
 479                 for (auto module : design->selected_whole_modules_warn()) {
 480                         if (module->has_processes_warn())
 481                                 continue;
 482                         rmunused_module(module, purge_mode, true, true);
 483                 }
 484
 485                 if (count_rm_cells > 0 || count_rm_wires > 0)
 486                         log("Removed %d unused cells and %d unused wires.\n", count_rm_cells, count_rm_wires);
 487
 488                 design->optimize();
 489                 design->sort();
 490                 design->check();
 491
 492                 keep_cache.reset();
 493                 ct_reg.clear();
 494                 ct_all.clear();
 495                 log_pop();
 496         }
 497 } OptCleanPass;
 498
 499 struct CleanPass : public Pass {
 500         CleanPass() : Pass("clean", "remove unused cells and wires") { }
 501         virtual void help()
 502         {
 503                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 504                 log("\n");
 505                 log("    clean [options] [selection]\n");
 506                 log("\n");
 507                 log("This is identical to 'opt_clean', but less verbose.\n");
 508                 log("\n");
 509                 log("When commands are separated using the ';;' token, this command will be executed\n");
 510                 log("between the commands.\n");
 511                 log("\n");
 512                 log("When commands are separated using the ';;;' token, this command will be executed\n");
 513                 log("in -purge mode between the commands.\n");
 514                 log("\n");
 515         }
 516         virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
 517         {
 518                 bool purge_mode = false;
 519
 520                 size_t argidx;
 521                 for (argidx = 1; argidx < args.size(); argidx++) {
 522                         if (args[argidx] == "-purge") {
 523                                 purge_mode = true;
 524                                 continue;
 525                         }
 526                         break;
 527                 }
 528                 if (argidx < args.size())
 529                         extra_args(args, argidx, design);
 530
 531                 keep_cache.reset(design);
 532
 533                 ct_reg.setup_internals_mem();
 534                 ct_reg.setup_stdcells_mem();
 535
 536                 ct_all.setup(design);
 537
 538                 count_rm_cells = 0;
 539                 count_rm_wires = 0;
 540
 541                 for (auto module : design->selected_whole_modules()) {
 542                         if (module->has_processes())
 543                                 continue;
 544                         rmunused_module(module, purge_mode, false, false);
 545                 }
 546
 547                 if (count_rm_cells > 0 || count_rm_wires > 0)
 548                         log("Removed %d unused cells and %d unused wires.\n", count_rm_cells, count_rm_wires);
 549
 550                 design->optimize();
 551                 design->sort();
 552                 design->check();
 553
 554                 keep_cache.reset();
 555                 ct_reg.clear();
 556                 ct_all.clear();
 557         }
 558 } CleanPass;
 559
 560 PRIVATE_NAMESPACE_END