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;
  33
  34 static void rmunused_module_cells(RTLIL::Module *module)
  35 {
  36         SigMap assign_map(module);
  37         std::set<RTLIL::Cell*> queue, unused;
  38
  39         SigSet<RTLIL::Cell*> wire2driver;
  40         for (auto &it : module->cells) {
  41                 RTLIL::Cell *cell = it.second;
  42                 for (auto &it2 : cell->connections) {
  43                         if (!ct.cell_input(cell->type, it2.first)) {
  44                                 RTLIL::SigSpec sig = it2.second;
  45                                 assign_map.apply(sig);
  46                                 wire2driver.insert(sig, cell);
  47                         }
  48                 }
  49                 if (cell->type == "$memwr")
  50                         queue.insert(cell);
  51                 unused.insert(cell);
  52         }
  53
  54         for (auto &it : module->wires) {
  55                 RTLIL::Wire *wire = it.second;
  56                 if (wire->port_output) {
  57                         std::set<RTLIL::Cell*> cell_list;
  58                         RTLIL::SigSpec sig = RTLIL::SigSpec(wire);
  59                         assign_map.apply(sig);
  60                         wire2driver.find(sig, cell_list);
  61                         for (auto cell : cell_list)
  62                                 queue.insert(cell);
  63                 }
  64         }
  65
  66         while (queue.size() > 0)
  67         {
  68                 std::set<RTLIL::Cell*> new_queue;
  69                 for (auto cell : queue)
  70                         unused.erase(cell);
  71                 for (auto cell : queue) {
  72                         for (auto &it : cell->connections) {
  73                                 if (!ct.cell_output(cell->type, it.first)) {
  74                                         std::set<RTLIL::Cell*> cell_list;
  75                                         RTLIL::SigSpec sig = it.second;
  76                                         assign_map.apply(sig);
  77                                         wire2driver.find(sig, cell_list);
  78                                         for (auto cell : cell_list) {
  79                                                 if (unused.count(cell) > 0)
  80                                                         new_queue.insert(cell);
  81                                         }
  82                                 }
  83                         }
  84                 }
  85                 queue.swap(new_queue);
  86         }
  87
  88         for (auto cell : unused) {
  89                 log("  removing unused `%s' cell `%s'.\n", cell->type.c_str(), cell->name.c_str());
  90                 OPT_DID_SOMETHING = true;
  91                 module->cells.erase(cell->name);
  92                 delete cell;
  93         }
  94 }
  95
  96 static bool compare_signals(RTLIL::SigSpec &s1, RTLIL::SigSpec &s2)
  97 {
  98         assert(s1.width == 1);
  99         assert(s2.width == 1);
 100         assert(s1.chunks.size() == 1);
 101         assert(s2.chunks.size() == 1);
 102
 103         RTLIL::Wire *w1 = s1.chunks[0].wire;
 104         RTLIL::Wire *w2 = s2.chunks[0].wire;
 105
 106         if (w1 == NULL || w2 == NULL)
 107                 return w2 == NULL;
 108
 109         if (w1->port_input != w2->port_input)
 110                 return w2->port_input;
 111
 112         if (w1->name[0] != w2->name[0])
 113                 return w2->name[0] == '\\';
 114
 115         if (w1->attributes.size() != w2->attributes.size())
 116                 return w2->attributes.size() > w1->attributes.size();
 117
 118         return w2->name < w1->name;
 119 }
 120
 121 static bool check_public_name(RTLIL::IdString id)
 122 {
 123         if (id[0] == '$')
 124                 return false;
 125 #if 0
 126         if (id.find(".$") != std::string::npos)
 127                 return false;
 128 #endif
 129         return true;
 130 }
 131
 132 static void rmunused_module_signals(RTLIL::Module *module)
 133 {
 134         SigMap assign_map(module);
 135         for (auto &it : module->wires) {
 136                 RTLIL::Wire *wire = it.second;
 137                 for (int i = 0; i < wire->width; i++) {
 138                         RTLIL::SigSpec s1 = RTLIL::SigSpec(wire, 1, i), s2 = assign_map(s1);
 139                         if (!compare_signals(s1, s2))
 140                                 assign_map.add(s1);
 141                 }
 142         }
 143
 144         module->connections.clear();
 145
 146         SigPool used_signals;
 147         SigPool used_signals_nodrivers;
 148         for (auto &it : module->cells) {
 149                 RTLIL::Cell *cell = it.second;
 150                 for (auto &it2 : cell->connections) {
 151                         assign_map.apply(it2.second);
 152                         used_signals.add(it2.second);
 153                         if (!ct.cell_output(cell->type, it2.first))
 154                                 used_signals_nodrivers.add(it2.second);
 155                 }
 156         }
 157         for (auto &it : module->wires) {
 158                 RTLIL::Wire *wire = it.second;
 159                 if (wire->port_id > 0) {
 160                         RTLIL::SigSpec sig = RTLIL::SigSpec(wire);
 161                         assign_map.apply(sig);
 162                         used_signals.add(sig);
 163                         if (!wire->port_input)
 164                                 used_signals_nodrivers.add(sig);
 165                 }
 166         }
 167
 168         std::vector<RTLIL::Wire*> del_wires;
 169         for (auto &it : module->wires) {
 170                 RTLIL::Wire *wire = it.second;
 171                 if (check_public_name(wire->name)) {
 172                         RTLIL::SigSpec s1 = RTLIL::SigSpec(wire), s2 = s1;
 173                         assign_map.apply(s2);
 174                         if (!used_signals.check_any(s2) && wire->port_id == 0) {
 175                                 del_wires.push_back(wire);
 176                         } else {
 177                                 s1.expand();
 178                                 s2.expand();
 179                                 assert(s1.chunks.size() == s2.chunks.size());
 180                                 RTLIL::SigSig new_conn;
 181                                 for (size_t i = 0; i < s1.chunks.size(); i++)
 182                                         if (s1.chunks[i] != s2.chunks[i]) {
 183                                                 new_conn.first.append(s1.chunks[i]);
 184                                                 new_conn.second.append(s2.chunks[i]);
 185                                         }
 186                                 if (new_conn.first.width > 0) {
 187                                         new_conn.first.optimize();
 188                                         new_conn.second.optimize();
 189                                         used_signals.add(new_conn.first);
 190                                         used_signals.add(new_conn.second);
 191                                         module->connections.push_back(new_conn);
 192                                 }
 193                         }
 194                 } else {
 195                         if (!used_signals.check_any(RTLIL::SigSpec(wire)))
 196                                 del_wires.push_back(wire);
 197                 }
 198                 RTLIL::SigSpec sig = assign_map(RTLIL::SigSpec(wire));
 199                 if (!used_signals_nodrivers.check_any(sig)) {
 200                         std::string unused_bits;
 201                         sig.expand();
 202                         for (size_t i = 0; i < sig.chunks.size(); i++) {
 203                                 if (sig.chunks[i].wire == NULL)
 204                                         continue;
 205                                 if (!used_signals_nodrivers.check_any(sig)) {
 206                                         if (!unused_bits.empty())
 207                                                 unused_bits += " ";
 208                                         unused_bits += stringf("%zd", i);
 209                                 }
 210                         }
 211                         if (unused_bits.empty() || wire->port_id != 0)
 212                                 wire->attributes.erase("\\unused_bits");
 213                         else
 214                                 wire->attributes["\\unused_bits"] = RTLIL::Const(unused_bits);
 215                 } else {
 216                         wire->attributes.erase("\\unused_bits");
 217                 }
 218         }
 219
 220         int del_wires_count = 0;
 221         for (auto wire : del_wires)
 222                 if (!used_signals.check_any(RTLIL::SigSpec(wire))) {
 223                         if (check_public_name(wire->name)) {
 224                                 log("  removing unused non-port wire %s.\n", wire->name.c_str());
 225                                 del_wires_count++;
 226                         }
 227                         module->wires.erase(wire->name);
 228                         delete wire;
 229                 }
 230
 231         if (del_wires_count > 0)
 232                 log("  removed %d unused temporary wires.\n", del_wires_count);
 233 }
 234
 235 static void rmunused_module(RTLIL::Module *module)
 236 {
 237         log("Finding unused cells or wires in module %s..\n", module->name.c_str());
 238
 239         rmunused_module_cells(module);
 240         rmunused_module_signals(module);
 241 }
 242
 243 struct OptCleanPass : public Pass {
 244         OptCleanPass() : Pass("opt_clean", "remove unused cells and wires") { }
 245         virtual void help()
 246         {
 247                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 248                 log("\n");
 249                 log("    opt_clean [selection]\n");
 250                 log("\n");
 251                 log("This pass identifies wires and cells that are unused and removes them. Other\n");
 252                 log("passes often remove cells but leave the wires in the design or reconnect the\n");
 253                 log("wires but leave the old cells in the design. This pass can be used to clean up\n");
 254                 log("after the passes that do the actual work.\n");
 255                 log("\n");
 256                 log("This pass only operates on completely selected modules without processes.\n");
 257                 log("\n");
 258         }
 259         virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
 260         {
 261                 log_header("Executing OPT_CLEAN pass (remove unused cells and wires).\n");
 262                 log_push();
 263
 264                 extra_args(args, 1, design);
 265
 266                 ct.setup_internals();
 267                 ct.setup_internals_mem();
 268                 ct.setup_stdcells();
 269                 ct.setup_stdcells_mem();
 270
 271                 for (auto &mod_it : design->modules) {
 272                         if (!design->selected_whole_module(mod_it.first)) {
 273                                 if (design->selected(mod_it.second))
 274                                         log("Skipping module %s as it is only partially selected.\n", id2cstr(mod_it.second->name));
 275                                 continue;
 276                         }
 277                         if (mod_it.second->processes.size() > 0) {
 278                                 log("Skipping module %s as it contains processes.\n", mod_it.second->name.c_str());
 279                         } else {
 280                                 rmunused_module(mod_it.second);
 281                         }
 282                 }
 283
 284                 ct.clear();
 285                 log_pop();
 286         }
 287 } OptCleanPass;
 288