passes/hierarchy/hierarchy.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/log.h"
  22 #include <stdlib.h>
  23 #include <stdio.h>
  24 #include <fnmatch.h>
  25 #include <set>
  26
  27 namespace {
  28         struct generate_port_decl_t {
  29                 bool input, output;
  30                 std::string portname;
  31                 int index;
  32         };
  33 }
  34
  35 static void generate(RTLIL::Design *design, const std::vector<std::string> &celltypes, const std::vector<generate_port_decl_t> &portdecls)
  36 {
  37         std::set<std::string> found_celltypes;
  38
  39         for (auto i1 : design->modules)
  40         for (auto i2 : i1.second->cells)
  41         {
  42                 RTLIL::Cell *cell = i2.second;
  43                 if (cell->type[0] == '$' || design->modules.count(cell->type) > 0)
  44                         continue;
  45                 for (auto &pattern : celltypes)
  46                         if (!fnmatch(pattern.c_str(), RTLIL::unescape_id(cell->type).c_str(), FNM_NOESCAPE))
  47                                 found_celltypes.insert(cell->type);
  48         }
  49
  50         for (auto &celltype : found_celltypes)
  51         {
  52                 std::set<std::string> portnames;
  53                 std::set<std::string> parameters;
  54                 std::map<std::string, int> portwidths;
  55                 log("Generate module for cell type %s:\n", celltype.c_str());
  56
  57                 for (auto i1 : design->modules)
  58                 for (auto i2 : i1.second->cells)
  59                         if (i2.second->type == celltype) {
  60                                 for (auto &conn : i2.second->connections) {
  61                                         if (conn.first[0] != '$')
  62                                                 portnames.insert(conn.first);
  63                                         portwidths[conn.first] = std::max(portwidths[conn.first], conn.second.width);
  64                                 }
  65                                 for (auto &para : i2.second->parameters)
  66                                         parameters.insert(para.first);
  67                         }
  68
  69                 for (auto &decl : portdecls)
  70                         if (decl.index > 0)
  71                                 portnames.insert(decl.portname);
  72
  73                 std::set<int> indices;
  74                 for (int i = 0; i < int(portnames.size()); i++)
  75                         indices.insert(i+1);
  76
  77                 std::vector<generate_port_decl_t> ports(portnames.size());
  78
  79                 for (auto &decl : portdecls)
  80                         if (decl.index > 0) {
  81                                 portwidths[decl.portname] = std::max(portwidths[decl.portname], 1);
  82                                 portwidths[decl.portname] = std::max(portwidths[decl.portname], portwidths[stringf("$%d", decl.index)]);
  83                                 log("  port %d: %s [%d:0] %s\n", decl.index, decl.input ? decl.output ? "inout" : "input" : "output", portwidths[decl.portname]-1, RTLIL::id2cstr(decl.portname));
  84                                 if (indices.count(decl.index) > ports.size())
  85                                         log_error("Port index (%d) exceeds number of found ports (%d).\n", decl.index, int(ports.size()));
  86                                 if (indices.count(decl.index) == 0)
  87                                         log_error("Conflict on port index %d.\n", decl.index);
  88                                 indices.erase(decl.index);
  89                                 portnames.erase(decl.portname);
  90                                 ports[decl.index-1] = decl;
  91                         }
  92
  93                 while (portnames.size() > 0) {
  94                         std::string portname = *portnames.begin();
  95                         for (auto &decl : portdecls)
  96                                 if (decl.index == 0 && !fnmatch(decl.portname.c_str(), RTLIL::unescape_id(portname).c_str(), FNM_NOESCAPE)) {
  97                                         generate_port_decl_t d = decl;
  98                                         d.portname = portname;
  99                                         d.index = *indices.begin();
 100                                         assert(!indices.empty());
 101                                         indices.erase(d.index);
 102                                         ports[d.index-1] = d;
 103                                         portwidths[d.portname] = std::max(portwidths[d.portname], 1);
 104                                         log("  port %d: %s [%d:0] %s\n", d.index, d.input ? d.output ? "inout" : "input" : "output", portwidths[d.portname]-1, RTLIL::id2cstr(d.portname));
 105                                         goto found_matching_decl;
 106                                 }
 107                         log_error("Can't match port %s.\n", RTLIL::id2cstr(portname));
 108                 found_matching_decl:;
 109                         portnames.erase(portname);
 110                 }
 111
 112                 assert(indices.empty());
 113
 114                 RTLIL::Module *mod = new RTLIL::Module;
 115                 mod->name = celltype;
 116                 mod->attributes["\\blackbox"] = RTLIL::Const(1);
 117                 design->modules[mod->name] = mod;
 118
 119                 for (auto &decl : ports) {
 120                         RTLIL::Wire *wire = new RTLIL::Wire;
 121                         wire->name = decl.portname;
 122                         wire->width = portwidths.at(decl.portname);
 123                         wire->port_id = decl.index;
 124                         wire->port_input = decl.input;
 125                         wire->port_output = decl.output;
 126                         mod->add(wire);
 127                 }
 128
 129                 for (auto &para : parameters)
 130                         log("  ignoring parameter %s.\n", RTLIL::id2cstr(para));
 131
 132                 log("  module %s created.\n", RTLIL::id2cstr(mod->name));
 133         }
 134 }
 135
 136 static bool expand_module(RTLIL::Design *design, RTLIL::Module *module, bool flag_check)
 137 {
 138         bool did_something = false;
 139
 140         for (auto &cell_it : module->cells) {
 141                 RTLIL::Cell *cell = cell_it.second;
 142                 if (design->modules.count(cell->type) == 0) {
 143                         if (flag_check && cell->type[0] != '$')
 144                                 log_error("Module `%s' referenced in module `%s' in cell `%s' is not part of the design.\n",
 145                                                 cell->type.c_str(), module->name.c_str(), cell->name.c_str());
 146                         continue;
 147                 }
 148                 if (cell->parameters.size() == 0)
 149                         continue;
 150                 if (design->modules.at(cell->type)->get_bool_attribute("\\blackbox"))
 151                         continue;
 152                 RTLIL::Module *mod = design->modules[cell->type];
 153                 cell->type = mod->derive(design, cell->parameters, cell->signed_parameters);
 154                 cell->parameters.clear();
 155                 did_something = true;
 156         }
 157
 158         if (did_something)
 159                 return did_something;
 160
 161         std::map<RTLIL::SigSpec, int> auto_wires;
 162
 163         for (auto &wire_it : module->wires) {
 164                 if (wire_it.second->auto_width)
 165                         auto_wires[RTLIL::SigSpec(wire_it.second)] = -1;
 166         }
 167
 168         for (auto &cell_it : module->cells)
 169         for (auto &conn : cell_it.second->connections)
 170         for (auto &awit : auto_wires) {
 171                 if (awit.second >= 0 || conn.second != awit.first)
 172                         continue;
 173                 if (design->modules.count(cell_it.second->type) == 0) {
 174                         log("WARNING: Module `%s' used in auto-delaration of the wire `%s.%s' cannot be found.\n",
 175                                         cell_it.second->type.c_str(), module->name.c_str(), log_signal(awit.first));
 176                         continue;
 177                 }
 178                 RTLIL::Module *mod = design->modules[cell_it.second->type];
 179                 RTLIL::Wire *wire = NULL;
 180                 if (mod->wires.count(conn.first) == 0) {
 181                         for (auto &wire_it : mod->wires) {
 182                                 if (wire_it.second->port_id == 0)
 183                                         continue;
 184                                 char buffer[100];
 185                                 snprintf(buffer, 100, "$%d", wire_it.second->port_id);
 186                                 if (buffer == conn.first) {
 187                                         wire = wire_it.second;
 188                                         break;
 189                                 }
 190                         }
 191                 } else
 192                         wire = mod->wires[conn.first];
 193                 if (!wire || wire->port_id == 0)
 194                         log_error("No port `%s' found in `%s' but used by instanciation in `%s'!\n",
 195                                         conn.first.c_str(), mod->name.c_str(), module->name.c_str());
 196                 if (wire->auto_width)
 197                         log_error("Signal `%s' found in `%s' and used by instanciation in `%s' for an auto wire is an auto-wire itself!\n",
 198                                         log_signal(awit.first), mod->name.c_str(), module->name.c_str());
 199                 awit.second = wire->width;
 200         }
 201
 202         std::map<RTLIL::IdString, int> auto_sizes;
 203         for (auto &awit : auto_wires) {
 204                 if (awit.second < 0)
 205                         log("Can't further resolve auto-wire `%s.%s' (width %d) using cell ports.\n",
 206                                         module->name.c_str(), awit.first.chunks[0].wire->name.c_str(),
 207                                         awit.first.chunks[0].wire->width);
 208                 else
 209                         auto_sizes[awit.first.chunks[0].wire->name] = awit.second;
 210         }
 211
 212         if (auto_sizes.size() > 0) {
 213                 module->update_auto_wires(auto_sizes);
 214                 log_header("Continuing HIERARCHY pass.\n");
 215                 did_something = true;
 216         }
 217
 218         return did_something;
 219 }
 220
 221 static void hierarchy_worker(RTLIL::Design *design, std::set<RTLIL::Module*> &used, RTLIL::Module *mod, int indent)
 222 {
 223         if (used.count(mod) > 0)
 224                 return;
 225
 226         if (indent == 0)
 227                 log("Top module:  %s\n", mod->name.c_str());
 228         else
 229                 log("Used module: %*s%s\n", indent, "", mod->name.c_str());
 230         used.insert(mod);
 231
 232         for (auto &it : mod->cells) {
 233                 if (design->modules.count(it.second->type) > 0)
 234                         hierarchy_worker(design, used, design->modules[it.second->type], indent+4);
 235         }
 236 }
 237
 238 static void hierarchy(RTLIL::Design *design, RTLIL::Module *top)
 239 {
 240         std::set<RTLIL::Module*> used;
 241         hierarchy_worker(design, used, top, 0);
 242
 243         std::vector<RTLIL::Module*> del_modules;
 244         for (auto &it : design->modules)
 245                 if (used.count(it.second) == 0)
 246                         del_modules.push_back(it.second);
 247
 248         for (auto mod : del_modules) {
 249                 log("Removing unused module `%s'.\n", mod->name.c_str());
 250                 design->modules.erase(mod->name);
 251                 delete mod;
 252         }
 253
 254         log("Removed %zd unused modules.\n", del_modules.size());
 255 }
 256
 257 struct HierarchyPass : public Pass {
 258         HierarchyPass() : Pass("hierarchy", "check, expand and clean up design hierarchy") { }
 259         virtual void help()
 260         {
 261                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 262                 log("\n");
 263                 log("    hierarchy [-check] [-top <module>]\n");
 264                 log("    hierarchy -generate <cell-types> <port-decls>\n");
 265                 log("\n");
 266                 log("In parametric designs, a module might exists in serveral variations with\n");
 267                 log("different parameter values. This pass looks at all modules in the current\n");
 268                 log("design an re-runs the language frontends for the parametric modules as\n");
 269                 log("needed.\n");
 270                 log("\n");
 271                 log("    -check\n");
 272                 log("        also check the design hierarchy. this generates an error when\n");
 273                 log("        an unknown module is used as cell type.\n");
 274                 log("\n");
 275                 log("    -keep_positionals\n");
 276                 log("        per default this pass also converts positional arguments in cells\n");
 277                 log("        to arguments using port names. this option disables this behavior.\n");
 278                 log("\n");
 279                 log("    -top <module>\n");
 280                 log("        use the specified top module to built a design hierarchy. modules\n");
 281                 log("        outside this tree (unused modules) are removed.\n");
 282                 log("\n");
 283                 log("        when the -top option is used, the 'top' attribute will be set on the\n");
 284                 log("        specified top module. otherwise a module with the 'top' attribute set\n");
 285                 log("        will implicitly be used as top module, if such a module exists.\n");
 286                 log("\n");
 287                 log("In -generate mode this pass generates blackbox modules for the given cell\n");
 288                 log("types (wildcards supported). For this the design is searched for cells that\n");
 289                 log("match the given types and then the given port declarations are used to\n");
 290                 log("determine the direction of the ports. The syntax for a port declaration is:\n");
 291                 log("\n");
 292                 log("    {i|o|io}[@<num>]:<portname>\n");
 293                 log("\n");
 294                 log("Input ports are specified with the 'i' prefix, output ports with the 'o'\n");
 295                 log("prefix and inout ports with the 'io' prefix. The optional <num> specifies\n");
 296                 log("the position of the port in the parameter list (needed when instanciated\n");
 297                 log("using positional arguments). When <num> is not specified, the <portname> can\n");
 298                 log("also contain wildcard characters.\n");
 299                 log("\n");
 300                 log("This pass ignores the current selection and always operates on all modules\n");
 301                 log("in the current design.\n");
 302                 log("\n");
 303         }
 304         virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
 305         {
 306                 log_header("Executing HIERARCHY pass (managing design hierarchy).\n");
 307
 308                 bool flag_check = false;
 309                 RTLIL::Module *top_mod = NULL;
 310
 311                 bool generate_mode = false;
 312                 bool keep_positionals = false;
 313                 std::vector<std::string> generate_cells;
 314                 std::vector<generate_port_decl_t> generate_ports;
 315
 316                 size_t argidx;
 317                 for (argidx = 1; argidx < args.size(); argidx++)
 318                 {
 319                         if (args[argidx] == "-generate" && !flag_check && !top_mod) {
 320                                 generate_mode = true;
 321                                 log("Entering generate mode.\n");
 322                                 while (++argidx < args.size()) {
 323                                         const char *p = args[argidx].c_str();
 324                                         generate_port_decl_t decl;
 325                                         if (p[0] == 'i' && p[1] == 'o')
 326                                                 decl.input = true, decl.output = true, p += 2;
 327                                         else if (*p == 'i')
 328                                                 decl.input = true, decl.output = false, p++;
 329                                         else if (*p == 'o')
 330                                                 decl.input = false, decl.output = true, p++;
 331                                         else
 332                                                 goto is_celltype;
 333                                         if (*p == '@') {
 334                                                 char *endptr;
 335                                                 decl.index = strtol(++p, &endptr, 10);
 336                                                 if (decl.index < 1)
 337                                                         goto is_celltype;
 338                                                 p = endptr;
 339                                         } else
 340                                                 decl.index = 0;
 341                                         if (*(p++) != ':')
 342                                                 goto is_celltype;
 343                                         if (*p == 0)
 344                                                 goto is_celltype;
 345                                         decl.portname = p;
 346                                         log("Port declaration: %s", decl.input ? decl.output ? "inout" : "input" : "output");
 347                                         if (decl.index >= 1)
 348                                                 log(" [at position %d]", decl.index);
 349                                         log(" %s\n", decl.portname.c_str());
 350                                         generate_ports.push_back(decl);
 351                                         continue;
 352                                 is_celltype:
 353                                         log("Celltype: %s\n", args[argidx].c_str());
 354                                         generate_cells.push_back(RTLIL::unescape_id(args[argidx]));
 355                                 }
 356                                 continue;
 357                         }
 358                         if (args[argidx] == "-check") {
 359                                 flag_check = true;
 360                                 continue;
 361                         }
 362                         if (args[argidx] == "-keep_positionals") {
 363                                 keep_positionals = true;
 364                                 continue;
 365                         }
 366                         if (args[argidx] == "-top") {
 367                                 if (++argidx >= args.size())
 368                                         log_cmd_error("Option -top requires an additional argument!\n");
 369                                 if (args[argidx][0] != '$' && args[argidx][0] != '\\')
 370                                         top_mod = design->modules.count("\\" + args[argidx]) > 0 ? design->modules["\\" + args[argidx]] : NULL;
 371                                 else
 372                                         top_mod = design->modules.count(args[argidx]) > 0 ? design->modules[args[argidx]] : NULL;
 373                                 if (top_mod == NULL)
 374                                         log_cmd_error("Module `%s' not found!\n", args[argidx].c_str());
 375                                 continue;
 376                         }
 377                         break;
 378                 }
 379                 extra_args(args, argidx, design, false);
 380
 381                 if (generate_mode) {
 382                         generate(design, generate_cells, generate_ports);
 383                         return;
 384                 }
 385
 386                 log_push();
 387
 388                 if (top_mod == NULL)
 389                         for (auto &mod_it : design->modules)
 390                                 if (mod_it.second->get_bool_attribute("\\top"))
 391                                         top_mod = mod_it.second;
 392
 393                 if (top_mod != NULL)
 394                         hierarchy(design, top_mod);
 395
 396                 bool did_something = true;
 397                 bool did_something_once = false;
 398                 while (did_something) {
 399                         did_something = false;
 400                         std::vector<std::string> modnames;
 401                         modnames.reserve(design->modules.size());
 402                         for (auto &mod_it : design->modules)
 403                                 modnames.push_back(mod_it.first);
 404                         for (auto &modname : modnames) {
 405                                 if (design->modules.count(modname) == 0)
 406                                         continue;
 407                                 if (expand_module(design, design->modules[modname], flag_check))
 408                                         did_something = true;
 409                         }
 410                         if (did_something)
 411                                 did_something_once = true;
 412                 }
 413
 414                 if (top_mod != NULL && did_something_once) {
 415                         log_header("Re-running hierarchy analysis..\n");
 416                         hierarchy(design, top_mod);
 417                 }
 418
 419                 if (top_mod != NULL) {
 420                         for (auto &mod_it : design->modules)
 421                                 if (mod_it.second == top_mod)
 422                                         mod_it.second->attributes["\\top"] = RTLIL::Const(1);
 423                                 else
 424                                         mod_it.second->attributes.erase("\\top");
 425                 }
 426
 427                 if (!keep_positionals)
 428                 {
 429                         std::set<RTLIL::Module*> pos_mods;
 430                         std::map<std::pair<RTLIL::Module*,int>, RTLIL::IdString> pos_map;
 431                         std::vector<std::pair<RTLIL::Module*,RTLIL::Cell*>> pos_work;
 432
 433                         for (auto &mod_it : design->modules)
 434                         for (auto &cell_it : mod_it.second->cells) {
 435                                 RTLIL::Cell *cell = cell_it.second;
 436                                 if (design->modules.count(cell->type) == 0)
 437                                         continue;
 438                                 for (auto &conn : cell->connections)
 439                                         if (conn.first[0] == '$' && '0' <= conn.first[1] && conn.first[1] <= '9') {
 440                                                 pos_mods.insert(design->modules.at(cell->type));
 441                                                 pos_work.push_back(std::pair<RTLIL::Module*,RTLIL::Cell*>(mod_it.second, cell));
 442                                                 break;
 443                                         }
 444                         }
 445
 446                         for (auto module : pos_mods)
 447                         for (auto &wire_it : module->wires) {
 448                                 RTLIL::Wire *wire = wire_it.second;
 449                                 if (wire->port_id > 0)
 450                                         pos_map[std::pair<RTLIL::Module*,int>(module, wire->port_id)] = wire->name;
 451                         }
 452
 453                         for (auto &work : pos_work) {
 454                                 RTLIL::Module *module = work.first;
 455                                 RTLIL::Cell *cell = work.second;
 456                                 log("Mapping positional arguments of cell %s.%s (%s).\n",
 457                                                 RTLIL::id2cstr(module->name), RTLIL::id2cstr(cell->name), RTLIL::id2cstr(cell->type));
 458                                 std::map<RTLIL::IdString, RTLIL::SigSpec> new_connections;
 459                                 for (auto &conn : cell->connections)
 460                                         if (conn.first[0] == '$' && '0' <= conn.first[1] && conn.first[1] <= '9') {
 461                                                 int id = atoi(conn.first.c_str()+1);
 462                                                 std::pair<RTLIL::Module*,int> key(design->modules.at(cell->type), id);
 463                                                 if (pos_map.count(key) == 0) {
 464                                                         log("  Failed to map positional argument %d of cell %s.%s (%s).\n",
 465                                                                         id, RTLIL::id2cstr(module->name), RTLIL::id2cstr(cell->name), RTLIL::id2cstr(cell->type));
 466                                                         new_connections[conn.first] = conn.second;
 467                                                 } else
 468                                                         new_connections[pos_map.at(key)] = conn.second;
 469                                         } else
 470                                                 new_connections[conn.first] = conn.second;
 471                                 cell->connections = new_connections;
 472                         }
 473                 }
 474
 475                 log_pop();
 476         }
 477 } HierarchyPass;
 478