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 "opt_status.h"
  21 #include "kernel/register.h"
  22 #include "kernel/sigtools.h"
  23 #include "kernel/log.h"
  24 #include "kernel/celltypes.h"
  25 #include <stdlib.h>
  26 #include <assert.h>
  27 #include <stdio.h>
  28 #include <set>
  29
  30 using RTLIL::id2cstr;
  31
  32 static CellTypes ct, ct_reg;
  33 static int count_rm_cells, count_rm_wires;
  34
  35 static void rmunused_module_cells(RTLIL::Module *module, bool verbose)
  36 {
  37         SigMap assign_map(module);
  38         std::set<RTLIL::Cell*, RTLIL::sort_by_name<RTLIL::Cell>> queue, unused;
  39
  40         SigSet<RTLIL::Cell*> wire2driver;
  41         for (auto &it : module->cells) {
  42                 RTLIL::Cell *cell = it.second;
  43                 for (auto &it2 : cell->connections) {
  44                         if (!ct.cell_input(cell->type, it2.first)) {
  45                                 RTLIL::SigSpec sig = it2.second;
  46                                 assign_map.apply(sig);
  47                                 wire2driver.insert(sig, cell);
  48                         }
  49                 }
  50                 if (cell->type == "$memwr" || cell->type == "$assert" || cell->get_bool_attribute("\\keep"))
  51                         queue.insert(cell);
  52                 unused.insert(cell);
  53         }
  54
  55         for (auto &it : module->wires) {
  56                 RTLIL::Wire *wire = it.second;
  57                 if (wire->port_output || wire->get_bool_attribute("\\keep")) {
  58                         std::set<RTLIL::Cell*> cell_list;
  59                         RTLIL::SigSpec sig = RTLIL::SigSpec(wire);
  60                         assign_map.apply(sig);
  61                         wire2driver.find(sig, cell_list);
  62                         for (auto cell : cell_list)
  63                                 queue.insert(cell);
  64                 }
  65         }
  66
  67         while (queue.size() > 0)
  68         {
  69                 std::set<RTLIL::Cell*, RTLIL::sort_by_name<RTLIL::Cell>> new_queue;
  70                 for (auto cell : queue)
  71                         unused.erase(cell);
  72                 for (auto cell : queue) {
  73                         for (auto &it : cell->connections) {
  74                                 if (!ct.cell_output(cell->type, it.first)) {
  75                                         std::set<RTLIL::Cell*> cell_list;
  76                                         RTLIL::SigSpec sig = it.second;
  77                                         assign_map.apply(sig);
  78                                         wire2driver.find(sig, cell_list);
  79                                         for (auto cell : cell_list) {
  80                                                 if (unused.count(cell) > 0)
  81                                                         new_queue.insert(cell);
  82                                         }
  83                                 }
  84                         }
  85                 }
  86                 queue.swap(new_queue);
  87         }
  88
  89         for (auto cell : unused) {
  90                 if (verbose)
  91                         log("  removing unused `%s' cell `%s'.\n", cell->type.c_str(), cell->name.c_str());
  92                 OPT_DID_SOMETHING = true;
  93                 module->cells.erase(cell->name);
  94                 count_rm_cells++;
  95                 delete cell;
  96         }
  97 }
  98
  99 static bool compare_signals(RTLIL::SigSpec &s1, RTLIL::SigSpec &s2, SigPool &regs, SigPool &conns)
 100 {
 101         assert(s1.width == 1);
 102         assert(s2.width == 1);
 103         assert(s1.chunks.size() == 1);
 104         assert(s2.chunks.size() == 1);
 105
 106         RTLIL::Wire *w1 = s1.chunks[0].wire;
 107         RTLIL::Wire *w2 = s2.chunks[0].wire;
 108
 109         if (w1 == NULL || w2 == NULL)
 110                 return w2 == NULL;
 111
 112         if (w1->port_input != w2->port_input)
 113                 return w2->port_input;
 114
 115         if (w1->name[0] == '\\' && w2->name[0] == '\\') {
 116                 if (regs.check_any(s1) != regs.check_any(s2))
 117                         return regs.check_any(s2);
 118                 if (conns.check_any(s1) != conns.check_any(s2))
 119                         return conns.check_any(s2);
 120         }
 121
 122         if (w1->port_output != w2->port_output)
 123                 return w2->port_output;
 124
 125         if (w1->name[0] != w2->name[0])
 126                 return w2->name[0] == '\\';
 127
 128         if (w1->attributes.size() != w2->attributes.size())
 129                 return w2->attributes.size() > w1->attributes.size();
 130
 131         return w2->name < w1->name;
 132 }
 133
 134 static bool check_public_name(RTLIL::IdString id)
 135 {
 136         if (id[0] == '$')
 137                 return false;
 138         if (id.substr(0, 2) == "\\_" && (id[id.size()-1] == '_' || id.find("_[") != std::string::npos))
 139                 return false;
 140         if (id.find(".$") != std::string::npos)
 141                 return false;
 142         return true;
 143 }
 144
 145 static void rmunused_module_signals(RTLIL::Module *module, bool purge_mode, bool verbose)
 146 {
 147         SigPool register_signals;
 148         SigPool connected_signals;
 149
 150         if (!purge_mode)
 151                 for (auto &it : module->cells) {
 152                         RTLIL::Cell *cell = it.second;
 153                         if (ct_reg.cell_known(cell->type))
 154                                 for (auto &it2 : cell->connections)
 155                                         if (ct_reg.cell_output(cell->type, it2.first))
 156                                                 register_signals.add(it2.second);
 157                         for (auto &it2 : cell->connections)
 158                                 connected_signals.add(it2.second);
 159                 }
 160
 161         SigMap assign_map(module);
 162         for (auto &it : module->wires) {
 163                 RTLIL::Wire *wire = it.second;
 164                 for (int i = 0; i < wire->width; i++) {
 165                         RTLIL::SigSpec s1 = RTLIL::SigSpec(wire, 1, i), s2 = assign_map(s1);
 166                         if (!compare_signals(s1, s2, register_signals, connected_signals))
 167                                 assign_map.add(s1);
 168                 }
 169         }
 170
 171         module->connections.clear();
 172
 173         SigPool used_signals;
 174         SigPool used_signals_nodrivers;
 175         for (auto &it : module->cells) {
 176                 RTLIL::Cell *cell = it.second;
 177                 for (auto &it2 : cell->connections) {
 178                         assign_map.apply(it2.second);
 179                         used_signals.add(it2.second);
 180                         if (!ct.cell_output(cell->type, it2.first))
 181                                 used_signals_nodrivers.add(it2.second);
 182                 }
 183         }
 184         for (auto &it : module->wires) {
 185                 RTLIL::Wire *wire = it.second;
 186                 if (wire->port_id > 0) {
 187                         RTLIL::SigSpec sig = RTLIL::SigSpec(wire);
 188                         assign_map.apply(sig);
 189                         used_signals.add(sig);
 190                         if (!wire->port_input)
 191                                 used_signals_nodrivers.add(sig);
 192                 }
 193                 if (wire->get_bool_attribute("\\keep")) {
 194                         RTLIL::SigSpec sig = RTLIL::SigSpec(wire);
 195                         assign_map.apply(sig);
 196                         used_signals.add(sig);
 197                 }
 198         }
 199
 200         std::vector<RTLIL::Wire*> del_wires;
 201         for (auto &it : module->wires) {
 202                 RTLIL::Wire *wire = it.second;
 203                 if ((!purge_mode && check_public_name(wire->name)) || wire->port_id != 0) {
 204                         RTLIL::SigSpec s1 = RTLIL::SigSpec(wire), s2 = s1;
 205                         assign_map.apply(s2);
 206                         if (!used_signals.check_any(s2) && wire->port_id == 0) {
 207                                 del_wires.push_back(wire);
 208                         } else {
 209                                 s1.expand();
 210                                 s2.expand();
 211                                 assert(s1.chunks.size() == s2.chunks.size());
 212                                 RTLIL::SigSig new_conn;
 213                                 for (size_t i = 0; i < s1.chunks.size(); i++)
 214                                         if (s1.chunks[i] != s2.chunks[i]) {
 215                                                 new_conn.first.append(s1.chunks[i]);
 216                                                 new_conn.second.append(s2.chunks[i]);
 217                                         }
 218                                 if (new_conn.first.width > 0) {
 219                                         new_conn.first.optimize();
 220                                         new_conn.second.optimize();
 221                                         used_signals.add(new_conn.first);
 222                                         used_signals.add(new_conn.second);
 223                                         module->connections.push_back(new_conn);
 224                                 }
 225                         }
 226                 } else {
 227                         if (!used_signals.check_any(RTLIL::SigSpec(wire)))
 228                                 del_wires.push_back(wire);
 229                 }
 230                 RTLIL::SigSpec sig = assign_map(RTLIL::SigSpec(wire));
 231                 if (!used_signals_nodrivers.check_any(sig)) {
 232                         std::string unused_bits;
 233                         sig.expand();
 234                         for (size_t i = 0; i < sig.chunks.size(); i++) {
 235                                 if (sig.chunks[i].wire == NULL)
 236                                         continue;
 237                                 if (!used_signals_nodrivers.check_any(sig)) {
 238                                         if (!unused_bits.empty())
 239                                                 unused_bits += " ";
 240                                         unused_bits += stringf("%zd", i);
 241                                 }
 242                         }
 243                         if (unused_bits.empty() || wire->port_id != 0)
 244                                 wire->attributes.erase("\\unused_bits");
 245                         else
 246                                 wire->attributes["\\unused_bits"] = RTLIL::Const(unused_bits);
 247                 } else {
 248                         wire->attributes.erase("\\unused_bits");
 249                 }
 250         }
 251
 252         int del_wires_count = 0;
 253         for (auto wire : del_wires)
 254                 if (!used_signals.check_any(RTLIL::SigSpec(wire))) {
 255                         if (check_public_name(wire->name) && verbose) {
 256                                 log("  removing unused non-port wire %s.\n", wire->name.c_str());
 257                                 del_wires_count++;
 258                         }
 259                         module->wires.erase(wire->name);
 260                         count_rm_wires++;
 261                         delete wire;
 262                 }
 263
 264         if (del_wires_count > 0)
 265                 log("  removed %d unused temporary wires.\n", del_wires_count);
 266 }
 267
 268 static void rmunused_module(RTLIL::Module *module, bool purge_mode, bool verbose)
 269 {
 270         if (verbose)
 271                 log("Finding unused cells or wires in module %s..\n", module->name.c_str());
 272
 273         rmunused_module_cells(module, verbose);
 274         rmunused_module_signals(module, purge_mode, verbose);
 275 }
 276
 277 struct OptCleanPass : public Pass {
 278         OptCleanPass() : Pass("opt_clean", "remove unused cells and wires") { }
 279         virtual void help()
 280         {
 281                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 282                 log("\n");
 283                 log("    opt_clean [options] [selection]\n");
 284                 log("\n");
 285                 log("This pass identifies wires and cells that are unused and removes them. Other\n");
 286                 log("passes often remove cells but leave the wires in the design or reconnect the\n");
 287                 log("wires but leave the old cells in the design. This pass can be used to clean up\n");
 288                 log("after the passes that do the actual work.\n");
 289                 log("\n");
 290                 log("This pass only operates on completely selected modules without processes.\n");
 291                 log("\n");
 292                 log("    -purge\n");
 293                 log("        also remove internal nets if they have a public name\n");
 294                 log("\n");
 295         }
 296         virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
 297         {
 298                 bool purge_mode = false;
 299
 300                 log_header("Executing OPT_CLEAN pass (remove unused cells and wires).\n");
 301                 log_push();
 302
 303                 size_t argidx;
 304                 for (argidx = 1; argidx < args.size(); argidx++) {
 305                         if (args[argidx] == "-purge") {
 306                                 purge_mode = true;
 307                                 continue;
 308                         }
 309                         break;
 310                 }
 311                 extra_args(args, argidx, design);
 312
 313                 ct.setup_internals();
 314                 ct.setup_internals_mem();
 315                 ct.setup_stdcells();
 316                 ct.setup_stdcells_mem();
 317
 318                 ct_reg.setup_internals_mem();
 319                 ct_reg.setup_stdcells_mem();
 320
 321                 for (auto &mod_it : design->modules) {
 322                         if (!design->selected_whole_module(mod_it.first)) {
 323                                 if (design->selected(mod_it.second))
 324                                         log("Skipping module %s as it is only partially selected.\n", id2cstr(mod_it.second->name));
 325                                 continue;
 326                         }
 327                         if (mod_it.second->processes.size() > 0) {
 328                                 log("Skipping module %s as it contains processes.\n", mod_it.second->name.c_str());
 329                         } else {
 330                                 rmunused_module(mod_it.second, purge_mode, true);
 331                         }
 332                 }
 333
 334                 ct.clear();
 335                 ct_reg.clear();
 336                 log_pop();
 337         }
 338 } OptCleanPass;
 339
 340 struct CleanPass : public Pass {
 341         CleanPass() : Pass("clean", "remove unused cells and wires") { }
 342         virtual void help()
 343         {
 344                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 345                 log("\n");
 346                 log("    clean [options] [selection]\n");
 347                 log("\n");
 348                 log("This is identical to 'opt_clean', but less verbose.\n");
 349                 log("\n");
 350                 log("When commands are seperated using the ';;' token, this command will be executed\n");
 351                 log("between the commands.\n");
 352                 log("\n");
 353                 log("When commands are seperated using the ';;;' token, this command will be executed\n");
 354                 log("in -purge mode between the commands.\n");
 355                 log("\n");
 356         }
 357         virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
 358         {
 359                 bool purge_mode = false;
 360
 361                 size_t argidx;
 362                 for (argidx = 1; argidx < args.size(); argidx++) {
 363                         if (args[argidx] == "-purge") {
 364                                 purge_mode = true;
 365                                 continue;
 366                         }
 367                         break;
 368                 }
 369                 if (argidx < args.size())
 370                         extra_args(args, argidx, design);
 371
 372                 ct.setup_internals();
 373                 ct.setup_internals_mem();
 374                 ct.setup_stdcells();
 375                 ct.setup_stdcells_mem();
 376
 377                 ct_reg.setup_internals_mem();
 378                 ct_reg.setup_stdcells_mem();
 379
 380                 count_rm_cells = 0;
 381                 count_rm_wires = 0;
 382
 383                 for (auto &mod_it : design->modules) {
 384                         if (design->selected_whole_module(mod_it.first) && mod_it.second->processes.size() == 0)
 385                                 do {
 386                                         OPT_DID_SOMETHING = false;
 387                                         rmunused_module(mod_it.second, purge_mode, false);
 388                                 } while (OPT_DID_SOMETHING);
 389                 }
 390
 391                 if (count_rm_cells > 0 || count_rm_wires > 0)
 392                         log("Removed %d unused cells and %d unused wires.\n", count_rm_cells, count_rm_wires);
 393
 394                 ct.clear();
 395                 ct_reg.clear();
 396         }
 397 } CleanPass;
 398