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