Fixed bug in "hierarchy" for parametric designs
[yosys.git] / 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/yosys.h"
21 #include <stdlib.h>
22 #include <stdio.h>
23 #include <set>
24
25 #ifndef _WIN32
26 # include <unistd.h>
27 #endif
28
29
30 USING_YOSYS_NAMESPACE
31 PRIVATE_NAMESPACE_BEGIN
32
33 struct generate_port_decl_t {
34 bool input, output;
35 string portname;
36 int index;
37 };
38
39 void generate(RTLIL::Design *design, const std::vector<std::string> &celltypes, const std::vector<generate_port_decl_t> &portdecls)
40 {
41 std::set<RTLIL::IdString> found_celltypes;
42
43 for (auto i1 : design->modules_)
44 for (auto i2 : i1.second->cells_)
45 {
46 RTLIL::Cell *cell = i2.second;
47 if (design->has(cell->type))
48 continue;
49 if (cell->type.substr(0, 1) == "$" && cell->type.substr(0, 3) != "$__")
50 continue;
51 for (auto &pattern : celltypes)
52 if (patmatch(pattern.c_str(), RTLIL::unescape_id(cell->type).c_str()))
53 found_celltypes.insert(cell->type);
54 }
55
56 for (auto &celltype : found_celltypes)
57 {
58 std::set<RTLIL::IdString> portnames;
59 std::set<RTLIL::IdString> parameters;
60 std::map<RTLIL::IdString, int> portwidths;
61 log("Generate module for cell type %s:\n", celltype.c_str());
62
63 for (auto i1 : design->modules_)
64 for (auto i2 : i1.second->cells_)
65 if (i2.second->type == celltype) {
66 for (auto &conn : i2.second->connections()) {
67 if (conn.first[0] != '$')
68 portnames.insert(conn.first);
69 portwidths[conn.first] = std::max(portwidths[conn.first], conn.second.size());
70 }
71 for (auto &para : i2.second->parameters)
72 parameters.insert(para.first);
73 }
74
75 for (auto &decl : portdecls)
76 if (decl.index > 0)
77 portnames.insert(decl.portname);
78
79 std::set<int> indices;
80 for (int i = 0; i < int(portnames.size()); i++)
81 indices.insert(i+1);
82
83 std::vector<generate_port_decl_t> ports(portnames.size());
84
85 for (auto &decl : portdecls)
86 if (decl.index > 0) {
87 portwidths[decl.portname] = std::max(portwidths[decl.portname], 1);
88 portwidths[decl.portname] = std::max(portwidths[decl.portname], portwidths[stringf("$%d", decl.index)]);
89 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));
90 if (indices.count(decl.index) > ports.size())
91 log_error("Port index (%d) exceeds number of found ports (%d).\n", decl.index, int(ports.size()));
92 if (indices.count(decl.index) == 0)
93 log_error("Conflict on port index %d.\n", decl.index);
94 indices.erase(decl.index);
95 portnames.erase(decl.portname);
96 ports[decl.index-1] = decl;
97 }
98
99 while (portnames.size() > 0) {
100 RTLIL::IdString portname = *portnames.begin();
101 for (auto &decl : portdecls)
102 if (decl.index == 0 && patmatch(decl.portname.c_str(), RTLIL::unescape_id(portname).c_str())) {
103 generate_port_decl_t d = decl;
104 d.portname = portname.str();
105 d.index = *indices.begin();
106 log_assert(!indices.empty());
107 indices.erase(d.index);
108 ports[d.index-1] = d;
109 portwidths[d.portname] = std::max(portwidths[d.portname], 1);
110 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));
111 goto found_matching_decl;
112 }
113 log_error("Can't match port %s.\n", RTLIL::id2cstr(portname));
114 found_matching_decl:;
115 portnames.erase(portname);
116 }
117
118 log_assert(indices.empty());
119
120 RTLIL::Module *mod = new RTLIL::Module;
121 mod->name = celltype;
122 mod->attributes["\\blackbox"] = RTLIL::Const(1);
123 design->add(mod);
124
125 for (auto &decl : ports) {
126 RTLIL::Wire *wire = mod->addWire(decl.portname, portwidths.at(decl.portname));
127 wire->port_id = decl.index;
128 wire->port_input = decl.input;
129 wire->port_output = decl.output;
130 }
131
132 mod->fixup_ports();
133
134 for (auto &para : parameters)
135 log(" ignoring parameter %s.\n", RTLIL::id2cstr(para));
136
137 log(" module %s created.\n", RTLIL::id2cstr(mod->name));
138 }
139 }
140
141 bool expand_module(RTLIL::Design *design, RTLIL::Module *module, bool flag_check, std::vector<std::string> &libdirs)
142 {
143 bool did_something = false;
144 std::map<RTLIL::Cell*, std::pair<int, int>> array_cells;
145 std::string filename;
146
147 for (auto &cell_it : module->cells_)
148 {
149 RTLIL::Cell *cell = cell_it.second;
150
151 if (cell->type.substr(0, 7) == "$array:") {
152 int pos_idx = cell->type.str().find_first_of(':');
153 int pos_num = cell->type.str().find_first_of(':', pos_idx + 1);
154 int pos_type = cell->type.str().find_first_of(':', pos_num + 1);
155 int idx = atoi(cell->type.str().substr(pos_idx + 1, pos_num).c_str());
156 int num = atoi(cell->type.str().substr(pos_num + 1, pos_type).c_str());
157 array_cells[cell] = std::pair<int, int>(idx, num);
158 cell->type = cell->type.str().substr(pos_type + 1);
159 }
160
161 if (design->modules_.count(cell->type) == 0)
162 {
163 if (design->modules_.count("$abstract" + cell->type.str()))
164 {
165 cell->type = design->modules_.at("$abstract" + cell->type.str())->derive(design, cell->parameters);
166 cell->parameters.clear();
167 did_something = true;
168 continue;
169 }
170
171 if (cell->type[0] == '$')
172 continue;
173
174 for (auto &dir : libdirs)
175 {
176 filename = dir + "/" + RTLIL::unescape_id(cell->type) + ".v";
177 if (check_file_exists(filename)) {
178 std::vector<std::string> args;
179 args.push_back(filename);
180 Frontend::frontend_call(design, NULL, filename, "verilog");
181 goto loaded_module;
182 }
183
184 filename = dir + "/" + RTLIL::unescape_id(cell->type) + ".il";
185 if (check_file_exists(filename)) {
186 std::vector<std::string> args;
187 args.push_back(filename);
188 Frontend::frontend_call(design, NULL, filename, "ilang");
189 goto loaded_module;
190 }
191 }
192
193 if (flag_check && cell->type[0] != '$')
194 log_error("Module `%s' referenced in module `%s' in cell `%s' is not part of the design.\n",
195 cell->type.c_str(), module->name.c_str(), cell->name.c_str());
196 continue;
197
198 loaded_module:
199 if (design->modules_.count(cell->type) == 0)
200 log_error("File `%s' from libdir does not declare module `%s'.\n", filename.c_str(), cell->type.c_str());
201 did_something = true;
202 } else
203 if (flag_check)
204 {
205 RTLIL::Module *mod = design->module(cell->type);
206 for (auto &conn : cell->connections())
207 if (conn.first[0] == '$' && '0' <= conn.first[1] && conn.first[1] <= '9') {
208 int id = atoi(conn.first.c_str()+1);
209 if (id <= 0 || id > GetSize(mod->ports))
210 log_error("Module `%s' referenced in module `%s' in cell `%s' has only %d ports, requested port %d.\n",
211 log_id(cell->type), log_id(module), log_id(cell), GetSize(mod->ports), id);
212 } else if (mod->wire(conn.first) == nullptr || mod->wire(conn.first)->port_id == 0)
213 log_error("Module `%s' referenced in module `%s' in cell `%s' does not have a port named '%s'.\n",
214 log_id(cell->type), log_id(module), log_id(cell), log_id(conn.first));
215 }
216
217 if (cell->parameters.size() == 0)
218 continue;
219
220 if (design->modules_.at(cell->type)->get_bool_attribute("\\blackbox"))
221 continue;
222
223 RTLIL::Module *mod = design->modules_[cell->type];
224 cell->type = mod->derive(design, cell->parameters);
225 cell->parameters.clear();
226 did_something = true;
227 }
228
229 for (auto &it : array_cells)
230 {
231 RTLIL::Cell *cell = it.first;
232 int idx = it.second.first, num = it.second.second;
233
234 if (design->modules_.count(cell->type) == 0)
235 log_error("Array cell `%s.%s' of unknown type `%s'.\n", RTLIL::id2cstr(module->name), RTLIL::id2cstr(cell->name), RTLIL::id2cstr(cell->type));
236
237 RTLIL::Module *mod = design->modules_[cell->type];
238
239 for (auto &conn : cell->connections_) {
240 int conn_size = conn.second.size();
241 RTLIL::IdString portname = conn.first;
242 if (portname.substr(0, 1) == "$") {
243 int port_id = atoi(portname.substr(1).c_str());
244 for (auto &wire_it : mod->wires_)
245 if (wire_it.second->port_id == port_id) {
246 portname = wire_it.first;
247 break;
248 }
249 }
250 if (mod->wires_.count(portname) == 0)
251 log_error("Array cell `%s.%s' connects to unknown port `%s'.\n", RTLIL::id2cstr(module->name), RTLIL::id2cstr(cell->name), RTLIL::id2cstr(conn.first));
252 int port_size = mod->wires_.at(portname)->width;
253 if (conn_size == port_size)
254 continue;
255 if (conn_size != port_size*num)
256 log_error("Array cell `%s.%s' has invalid port vs. signal size for port `%s'.\n", RTLIL::id2cstr(module->name), RTLIL::id2cstr(cell->name), RTLIL::id2cstr(conn.first));
257 conn.second = conn.second.extract(port_size*idx, port_size);
258 }
259 }
260
261 return did_something;
262 }
263
264 void hierarchy_worker(RTLIL::Design *design, std::set<RTLIL::Module*> &used, RTLIL::Module *mod, int indent)
265 {
266 if (used.count(mod) > 0)
267 return;
268
269 if (indent == 0)
270 log("Top module: %s\n", mod->name.c_str());
271 else if (!mod->get_bool_attribute("\\blackbox"))
272 log("Used module: %*s%s\n", indent, "", mod->name.c_str());
273 used.insert(mod);
274
275 for (auto cell : mod->cells()) {
276 std::string celltype = cell->type.str();
277 if (celltype.substr(0, 7) == "$array:") {
278 int pos_idx = celltype.find_first_of(':');
279 int pos_num = celltype.find_first_of(':', pos_idx + 1);
280 int pos_type = celltype.find_first_of(':', pos_num + 1);
281 celltype = celltype.substr(pos_type + 1);
282 }
283 if (design->module(celltype))
284 hierarchy_worker(design, used, design->module(celltype), indent+4);
285 }
286 }
287
288 void hierarchy_clean(RTLIL::Design *design, RTLIL::Module *top, bool purge_lib)
289 {
290 std::set<RTLIL::Module*> used;
291 hierarchy_worker(design, used, top, 0);
292
293 std::vector<RTLIL::Module*> del_modules;
294 for (auto &it : design->modules_)
295 if (used.count(it.second) == 0)
296 del_modules.push_back(it.second);
297
298 int del_counter = 0;
299 for (auto mod : del_modules) {
300 if (mod->name.substr(0, 9) == "$abstract")
301 continue;
302 if (!purge_lib && mod->get_bool_attribute("\\blackbox"))
303 continue;
304 log("Removing unused module `%s'.\n", mod->name.c_str());
305 design->modules_.erase(mod->name);
306 del_counter++;
307 delete mod;
308 }
309
310 log("Removed %d unused modules.\n", del_counter);
311 }
312
313 bool set_keep_assert(std::map<RTLIL::Module*, bool> &cache, RTLIL::Module *mod)
314 {
315 if (cache.count(mod) == 0)
316 for (auto c : mod->cells()) {
317 RTLIL::Module *m = mod->design->module(c->type);
318 if ((m != nullptr && set_keep_assert(cache, m)) || c->type == "$assert")
319 return cache[mod] = true;
320 }
321 return cache[mod];
322 }
323
324 struct HierarchyPass : public Pass {
325 HierarchyPass() : Pass("hierarchy", "check, expand and clean up design hierarchy") { }
326 virtual void help()
327 {
328 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
329 log("\n");
330 log(" hierarchy [-check] [-top <module>]\n");
331 log(" hierarchy -generate <cell-types> <port-decls>\n");
332 log("\n");
333 log("In parametric designs, a module might exists in several variations with\n");
334 log("different parameter values. This pass looks at all modules in the current\n");
335 log("design an re-runs the language frontends for the parametric modules as\n");
336 log("needed.\n");
337 log("\n");
338 log(" -check\n");
339 log(" also check the design hierarchy. this generates an error when\n");
340 log(" an unknown module is used as cell type.\n");
341 log("\n");
342 log(" -purge_lib\n");
343 log(" by default the hierarchy command will not remove library (blackbox)\n");
344 log(" module. use this options to also remove unused blackbox modules.\n");
345 log("\n");
346 log(" -libdir <directory>\n");
347 log(" search for files named <module_name>.v in the specified directory\n");
348 log(" for unknown modules and automatically run read_verilog for each\n");
349 log(" unknown module.\n");
350 log("\n");
351 log(" -keep_positionals\n");
352 log(" per default this pass also converts positional arguments in cells\n");
353 log(" to arguments using port names. this option disables this behavior.\n");
354 log("\n");
355 log(" -nokeep_asserts\n");
356 log(" per default this pass sets the \"keep\" attribute on all modules\n");
357 log(" that directly or indirectly contain one or more $assert cells. this\n");
358 log(" option disables this behavior.\n");
359 log("\n");
360 log(" -top <module>\n");
361 log(" use the specified top module to built a design hierarchy. modules\n");
362 log(" outside this tree (unused modules) are removed.\n");
363 log("\n");
364 log(" when the -top option is used, the 'top' attribute will be set on the\n");
365 log(" specified top module. otherwise a module with the 'top' attribute set\n");
366 log(" will implicitly be used as top module, if such a module exists.\n");
367 log("\n");
368 log("In -generate mode this pass generates blackbox modules for the given cell\n");
369 log("types (wildcards supported). For this the design is searched for cells that\n");
370 log("match the given types and then the given port declarations are used to\n");
371 log("determine the direction of the ports. The syntax for a port declaration is:\n");
372 log("\n");
373 log(" {i|o|io}[@<num>]:<portname>\n");
374 log("\n");
375 log("Input ports are specified with the 'i' prefix, output ports with the 'o'\n");
376 log("prefix and inout ports with the 'io' prefix. The optional <num> specifies\n");
377 log("the position of the port in the parameter list (needed when instanciated\n");
378 log("using positional arguments). When <num> is not specified, the <portname> can\n");
379 log("also contain wildcard characters.\n");
380 log("\n");
381 log("This pass ignores the current selection and always operates on all modules\n");
382 log("in the current design.\n");
383 log("\n");
384 }
385 virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
386 {
387 log_header("Executing HIERARCHY pass (managing design hierarchy).\n");
388
389 bool flag_check = false;
390 bool purge_lib = false;
391 RTLIL::Module *top_mod = NULL;
392 std::vector<std::string> libdirs;
393
394 bool generate_mode = false;
395 bool keep_positionals = false;
396 bool nokeep_asserts = false;
397 std::vector<std::string> generate_cells;
398 std::vector<generate_port_decl_t> generate_ports;
399
400 size_t argidx;
401 for (argidx = 1; argidx < args.size(); argidx++)
402 {
403 if (args[argidx] == "-generate" && !flag_check && !top_mod) {
404 generate_mode = true;
405 log("Entering generate mode.\n");
406 while (++argidx < args.size()) {
407 const char *p = args[argidx].c_str();
408 generate_port_decl_t decl;
409 if (p[0] == 'i' && p[1] == 'o')
410 decl.input = true, decl.output = true, p += 2;
411 else if (*p == 'i')
412 decl.input = true, decl.output = false, p++;
413 else if (*p == 'o')
414 decl.input = false, decl.output = true, p++;
415 else
416 goto is_celltype;
417 if (*p == '@') {
418 char *endptr;
419 decl.index = strtol(++p, &endptr, 10);
420 if (decl.index < 1)
421 goto is_celltype;
422 p = endptr;
423 } else
424 decl.index = 0;
425 if (*(p++) != ':')
426 goto is_celltype;
427 if (*p == 0)
428 goto is_celltype;
429 decl.portname = p;
430 log("Port declaration: %s", decl.input ? decl.output ? "inout" : "input" : "output");
431 if (decl.index >= 1)
432 log(" [at position %d]", decl.index);
433 log(" %s\n", decl.portname.c_str());
434 generate_ports.push_back(decl);
435 continue;
436 is_celltype:
437 log("Celltype: %s\n", args[argidx].c_str());
438 generate_cells.push_back(RTLIL::unescape_id(args[argidx]));
439 }
440 continue;
441 }
442 if (args[argidx] == "-check") {
443 flag_check = true;
444 continue;
445 }
446 if (args[argidx] == "-purge_lib") {
447 purge_lib = true;
448 continue;
449 }
450 if (args[argidx] == "-keep_positionals") {
451 keep_positionals = true;
452 continue;
453 }
454 if (args[argidx] == "-nokeep_asserts") {
455 nokeep_asserts = true;
456 continue;
457 }
458 if (args[argidx] == "-libdir" && argidx+1 < args.size()) {
459 libdirs.push_back(args[++argidx]);
460 continue;
461 }
462 if (args[argidx] == "-top") {
463 if (++argidx >= args.size())
464 log_cmd_error("Option -top requires an additional argument!\n");
465 top_mod = design->modules_.count(RTLIL::escape_id(args[argidx])) ? design->modules_.at(RTLIL::escape_id(args[argidx])) : NULL;
466 if (top_mod == NULL && design->modules_.count("$abstract" + RTLIL::escape_id(args[argidx]))) {
467 dict<RTLIL::IdString, RTLIL::Const> empty_parameters;
468 design->modules_.at("$abstract" + RTLIL::escape_id(args[argidx]))->derive(design, empty_parameters);
469 top_mod = design->modules_.count(RTLIL::escape_id(args[argidx])) ? design->modules_.at(RTLIL::escape_id(args[argidx])) : NULL;
470 }
471 if (top_mod == NULL)
472 log_cmd_error("Module `%s' not found!\n", args[argidx].c_str());
473 continue;
474 }
475 break;
476 }
477 extra_args(args, argidx, design, false);
478
479 if (generate_mode) {
480 generate(design, generate_cells, generate_ports);
481 return;
482 }
483
484 log_push();
485
486 if (top_mod == NULL)
487 for (auto &mod_it : design->modules_)
488 if (mod_it.second->get_bool_attribute("\\top"))
489 top_mod = mod_it.second;
490
491 bool did_something = true;
492 while (did_something)
493 {
494 did_something = false;
495
496 std::set<RTLIL::Module*> used_modules;
497 if (top_mod != NULL) {
498 log_header("Analyzing design hierarchy..\n");
499 hierarchy_worker(design, used_modules, top_mod, 0);
500 } else {
501 for (auto mod : design->modules())
502 used_modules.insert(mod);
503 }
504
505 for (auto module : used_modules) {
506 if (expand_module(design, module, flag_check, libdirs))
507 did_something = true;
508 }
509 }
510
511 if (top_mod != NULL) {
512 log_header("Analyzing design hierarchy..\n");
513 hierarchy_clean(design, top_mod, purge_lib);
514 }
515
516 if (top_mod != NULL) {
517 for (auto &mod_it : design->modules_)
518 if (mod_it.second == top_mod)
519 mod_it.second->attributes["\\top"] = RTLIL::Const(1);
520 else
521 mod_it.second->attributes.erase("\\top");
522 }
523
524 if (!nokeep_asserts) {
525 std::map<RTLIL::Module*, bool> cache;
526 for (auto mod : design->modules())
527 if (set_keep_assert(cache, mod)) {
528 log("Module %s directly or indirectly contains $assert cells -> setting \"keep\" attribute.\n", log_id(mod));
529 mod->set_bool_attribute("\\keep");
530 }
531 }
532
533 if (!keep_positionals)
534 {
535 std::set<RTLIL::Module*> pos_mods;
536 std::map<std::pair<RTLIL::Module*,int>, RTLIL::IdString> pos_map;
537 std::vector<std::pair<RTLIL::Module*,RTLIL::Cell*>> pos_work;
538
539 for (auto &mod_it : design->modules_)
540 for (auto &cell_it : mod_it.second->cells_) {
541 RTLIL::Cell *cell = cell_it.second;
542 if (design->modules_.count(cell->type) == 0)
543 continue;
544 for (auto &conn : cell->connections())
545 if (conn.first[0] == '$' && '0' <= conn.first[1] && conn.first[1] <= '9') {
546 pos_mods.insert(design->modules_.at(cell->type));
547 pos_work.push_back(std::pair<RTLIL::Module*,RTLIL::Cell*>(mod_it.second, cell));
548 break;
549 }
550 }
551
552 for (auto module : pos_mods)
553 for (auto &wire_it : module->wires_) {
554 RTLIL::Wire *wire = wire_it.second;
555 if (wire->port_id > 0)
556 pos_map[std::pair<RTLIL::Module*,int>(module, wire->port_id)] = wire->name;
557 }
558
559 for (auto &work : pos_work) {
560 RTLIL::Module *module = work.first;
561 RTLIL::Cell *cell = work.second;
562 log("Mapping positional arguments of cell %s.%s (%s).\n",
563 RTLIL::id2cstr(module->name), RTLIL::id2cstr(cell->name), RTLIL::id2cstr(cell->type));
564 dict<RTLIL::IdString, RTLIL::SigSpec> new_connections;
565 for (auto &conn : cell->connections())
566 if (conn.first[0] == '$' && '0' <= conn.first[1] && conn.first[1] <= '9') {
567 int id = atoi(conn.first.c_str()+1);
568 std::pair<RTLIL::Module*,int> key(design->modules_.at(cell->type), id);
569 if (pos_map.count(key) == 0) {
570 log(" Failed to map positional argument %d of cell %s.%s (%s).\n",
571 id, RTLIL::id2cstr(module->name), RTLIL::id2cstr(cell->name), RTLIL::id2cstr(cell->type));
572 new_connections[conn.first] = conn.second;
573 } else
574 new_connections[pos_map.at(key)] = conn.second;
575 } else
576 new_connections[conn.first] = conn.second;
577 cell->connections_ = new_connections;
578 }
579 }
580
581 log_pop();
582 }
583 } HierarchyPass;
584
585 PRIVATE_NAMESPACE_END