diff options
Diffstat (limited to 'passes')
47 files changed, 7909 insertions, 0 deletions
diff --git a/passes/abc/Makefile.inc b/passes/abc/Makefile.inc new file mode 100644 index 000000000..25aadcdc0 --- /dev/null +++ b/passes/abc/Makefile.inc @@ -0,0 +1,4 @@ + +OBJS += passes/abc/abc.o +OBJS += passes/abc/vlparse.o + diff --git a/passes/abc/abc.cc b/passes/abc/abc.cc new file mode 100644 index 000000000..251d0ba09 --- /dev/null +++ b/passes/abc/abc.cc @@ -0,0 +1,645 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/register.h" +#include "kernel/sigtools.h" +#include "kernel/log.h" +#include "vlparse.h" +#include <unistd.h> +#include <stdlib.h> +#include <assert.h> +#include <stdio.h> +#include <string.h> +#include <dirent.h> +#include <sstream> + +struct gate_t +{ + int id; + char type; + int in1, in2, in3; + bool is_port; + RTLIL::SigSpec sig; +}; + +static int map_autoidx; +static SigMap assign_map; +static RTLIL::Module *module; +static std::vector<gate_t> signal_list; +static std::map<RTLIL::SigSpec, int> signal_map; + +static int map_signal(RTLIL::SigSpec sig, char gate_type = -1, int in1 = -1, int in2 = -1, int in3 = -1) +{ + assert(sig.width == 1); + assert(sig.chunks.size() == 1); + + assign_map.apply(sig); + + if (signal_map.count(sig) == 0) { + gate_t gate; + gate.id = signal_list.size(); + gate.type = -1; + gate.in1 = -1; + gate.in2 = -1; + gate.in3 = -1; + gate.is_port = false; + gate.sig = sig; + signal_list.push_back(gate); + signal_map[sig] = gate.id; + } + + gate_t &gate = signal_list[signal_map[sig]]; + + if (gate_type >= 0) + gate.type = gate_type; + if (in1 >= 0) + gate.in1 = in1; + if (in2 >= 0) + gate.in2 = in2; + if (in3 >= 0) + gate.in3 = in3; + + return gate.id; +} + +static void mark_port(RTLIL::SigSpec sig) +{ + assign_map.apply(sig); + sig.expand(); + for (auto &c : sig.chunks) { + if (c.wire != NULL && signal_map.count(c) > 0) + signal_list[signal_map[c]].is_port = true; + } +} + +static void extract_cell(RTLIL::Cell *cell) +{ + if (cell->type == "$_INV_") + { + RTLIL::SigSpec sig_a = cell->connections["\\A"]; + RTLIL::SigSpec sig_y = cell->connections["\\Y"]; + + assign_map.apply(sig_a); + assign_map.apply(sig_y); + + map_signal(sig_y, 'n', map_signal(sig_a)); + + module->cells.erase(cell->name); + delete cell; + return; + } + + if (cell->type == "$_AND_" || cell->type == "$_OR_" || cell->type == "$_XOR_") + { + RTLIL::SigSpec sig_a = cell->connections["\\A"]; + RTLIL::SigSpec sig_b = cell->connections["\\B"]; + RTLIL::SigSpec sig_y = cell->connections["\\Y"]; + + assign_map.apply(sig_a); + assign_map.apply(sig_b); + assign_map.apply(sig_y); + + if (cell->type == "$_AND_") + map_signal(sig_y, 'a', map_signal(sig_a), map_signal(sig_b)); + else if (cell->type == "$_OR_") + map_signal(sig_y, 'o', map_signal(sig_a), map_signal(sig_b)); + else if (cell->type == "$_XOR_") + map_signal(sig_y, 'x', map_signal(sig_a), map_signal(sig_b)); + else + abort(); + + module->cells.erase(cell->name); + delete cell; + return; + } + + if (cell->type == "$_MUX_") + { + RTLIL::SigSpec sig_a = cell->connections["\\A"]; + RTLIL::SigSpec sig_b = cell->connections["\\B"]; + RTLIL::SigSpec sig_s = cell->connections["\\S"]; + RTLIL::SigSpec sig_y = cell->connections["\\Y"]; + + assign_map.apply(sig_a); + assign_map.apply(sig_b); + assign_map.apply(sig_s); + assign_map.apply(sig_y); + + map_signal(sig_y, 'm', map_signal(sig_a), map_signal(sig_b), map_signal(sig_s)); + + module->cells.erase(cell->name); + delete cell; + return; + } +} + +static std::string remap_name(std::string abc_name) +{ + std::stringstream sstr; + sstr << "$abc$" << map_autoidx << "$" << abc_name.substr(1); + return sstr.str(); +} + +static void dump_loop_graph(FILE *f, int &nr, std::map<int, std::set<int>> &edges, std::set<int> &workpool, std::vector<int> &in_counts) +{ + if (f == NULL) + return; + + log("Dumping loop state graph to slide %d.\n", ++nr); + + fprintf(f, "digraph slide%d {\n", nr); + fprintf(f, " rankdir=\"LR\";\n"); + + std::set<int> nodes; + for (auto &e : edges) { + nodes.insert(e.first); + for (auto n : e.second) + nodes.insert(n); + } + + for (auto n : nodes) + fprintf(f, " n%d [label=\"%s\\nid=%d, count=%d\"%s];\n", n, log_signal(signal_list[n].sig), + n, in_counts[n], workpool.count(n) ? ", shape=box" : ""); + + for (auto &e : edges) + for (auto n : e.second) + fprintf(f, " n%d -> n%d;\n", e.first, n); + + fprintf(f, "}\n"); +} + +static void handle_loops() +{ + // http://en.wikipedia.org/wiki/Topological_sorting + + std::map<int, std::set<int>> edges; + std::vector<int> in_edges_count(signal_list.size()); + std::set<int> workpool; + + FILE *dot_f = NULL; + int dot_nr = 0; + + // uncomment for troubleshooting the loop detection code + // dot_f = fopen("test.dot", "w"); + + for (auto &g : signal_list) { + if (g.type == -1) { + workpool.insert(g.id); + } + if (g.in1 >= 0) { + edges[g.in1].insert(g.id); + in_edges_count[g.id]++; + } + if (g.in2 >= 0 && g.in2 != g.in1) { + edges[g.in2].insert(g.id); + in_edges_count[g.id]++; + } + if (g.in3 >= 0 && g.in3 != g.in2 && g.in3 != g.in1) { + edges[g.in3].insert(g.id); + in_edges_count[g.id]++; + } + } + + dump_loop_graph(dot_f, dot_nr, edges, workpool, in_edges_count); + + while (workpool.size() > 0) + { + int id = *workpool.begin(); + workpool.erase(id); + + // log("Removing non-loop node %d from graph: %s\n", id, log_signal(signal_list[id].sig)); + + for (int id2 : edges[id]) { + assert(in_edges_count[id2] > 0); + if (--in_edges_count[id2] == 0) + workpool.insert(id2); + } + edges.erase(id); + + dump_loop_graph(dot_f, dot_nr, edges, workpool, in_edges_count); + + while (workpool.size() == 0) + { + if (edges.size() == 0) + break; + + int id1 = edges.begin()->first; + + for (auto &edge_it : edges) { + int id2 = edge_it.first; + RTLIL::Wire *w1 = signal_list[id1].sig.chunks[0].wire; + RTLIL::Wire *w2 = signal_list[id2].sig.chunks[0].wire; + if (w1 != NULL) + continue; + else if (w2 == NULL) + id1 = id2; + else if (w1->name[0] == '$' && w2->name[0] == '\\') + id1 = id2; + else if (w1->name[0] == '\\' && w2->name[0] == '$') + continue; + else if (edges[id1].size() < edges[id2].size()) + id1 = id2; + else if (edges[id1].size() > edges[id2].size()) + continue; + else if (w1->name > w2->name) + id1 = id2; + } + + if (edges[id1].size() == 0) { + edges.erase(id1); + continue; + } + + RTLIL::Wire *wire = new RTLIL::Wire; + std::stringstream sstr; + sstr << "$abcloop$" << (RTLIL::autoidx++); + wire->name = sstr.str(); + module->wires[wire->name] = wire; + + bool first_line = true; + for (int id2 : edges[id1]) { + if (first_line) + log("Breaking loop using new signal %s: %s -> %s\n", log_signal(RTLIL::SigSpec(wire)), + log_signal(signal_list[id1].sig), log_signal(signal_list[id2].sig)); + else + log(" %*s %s -> %s\n", int(strlen(log_signal(RTLIL::SigSpec(wire)))), "", + log_signal(signal_list[id1].sig), log_signal(signal_list[id2].sig)); + first_line = false; + } + + int id3 = map_signal(RTLIL::SigSpec(wire)); + signal_list[id1].is_port = true; + signal_list[id3].is_port = true; + assert(id3 == int(in_edges_count.size())); + in_edges_count.push_back(0); + workpool.insert(id3); + + for (int id2 : edges[id1]) { + if (signal_list[id2].in1 == id1) + signal_list[id2].in1 = id3; + if (signal_list[id2].in2 == id1) + signal_list[id2].in2 = id3; + if (signal_list[id2].in3 == id1) + signal_list[id2].in3 = id3; + } + edges[id1].swap(edges[id3]); + + module->connections.push_back(RTLIL::SigSig(signal_list[id3].sig, signal_list[id1].sig)); + dump_loop_graph(dot_f, dot_nr, edges, workpool, in_edges_count); + } + } + + if (dot_f != NULL) + fclose(dot_f); +} + +static void abc_module(RTLIL::Module *current_module, std::string script_file, std::string exe_file, std::string liberty_file, bool cleanup) +{ + module = current_module; + map_autoidx = RTLIL::autoidx++; + + signal_map.clear(); + signal_list.clear(); + assign_map.set(module); + + char tempdir_name[] = "/tmp/yosys-abc-XXXXXX"; + if (!cleanup) + tempdir_name[0] = tempdir_name[4] = '_'; + char *p = mkdtemp(tempdir_name); + log_header("Extracting gate logic of module `%s' to `%s/input.v'..\n", module->name.c_str(), tempdir_name); + assert(p != NULL); + + std::vector<RTLIL::Cell*> cells; + cells.reserve(module->cells.size()); + for (auto &it : module->cells) + cells.push_back(it.second); + for (auto c : cells) + extract_cell(c); + + for (auto &wire_it : module->wires) { + if (wire_it.second->port_id > 0) + mark_port(RTLIL::SigSpec(wire_it.second)); + } + + for (auto &cell_it : module->cells) + for (auto &port_it : cell_it.second->connections) + mark_port(port_it.second); + + handle_loops(); + + if (asprintf(&p, "%s/input.v", tempdir_name) < 0) abort(); + FILE *f = fopen(p, "wt"); + assert(f != NULL); + free(p); + + fprintf(f, "module logic ("); + bool first = true; + for (auto &si : signal_list) { + if (!si.is_port) + continue; + if (!first) + fprintf(f, ", "); + fprintf(f, "n%d", si.id); + first = false; + } + fprintf(f, "); // %s\n", module->name.c_str()); + + int count_input = 0, count_output = 0; + for (auto &si : signal_list) { + if (si.is_port) { + if (si.type >= 0) + count_output++; + else + count_input++; + } + fprintf(f, "%s n%d; // %s\n", si.is_port ? si.type >= 0 ? + "output" : "input" : "wire", si.id, log_signal(si.sig)); + } + for (auto &si : signal_list) { + assert(si.sig.width == 1 && si.sig.chunks.size() == 1); + if (si.sig.chunks[0].wire == NULL) + fprintf(f, "assign n%d = %c;\n", si.id, si.sig.chunks[0].data.bits[0] == RTLIL::State::S1 ? '1' : '0'); + } + + int count_gates = 0; + for (auto &si : signal_list) { + if (si.type == 'n') + fprintf(f, "not (n%d, n%d);\n", si.id, si.in1); + else if (si.type == 'a') + fprintf(f, "and (n%d, n%d, n%d);\n", si.id, si.in1, si.in2); + else if (si.type == 'o') + fprintf(f, "or (n%d, n%d, n%d);\n", si.id, si.in1, si.in2); + else if (si.type == 'x') + fprintf(f, "xor (n%d, n%d, n%d);\n", si.id, si.in1, si.in2); + else if (si.type == 'm') + fprintf(f, "assign n%d = n%d ? n%d : n%d;\n", si.id, si.in3, si.in2, si.in1); + else if (si.type >= 0) + abort(); + if (si.type >= 0) + count_gates++; + } + + fprintf(f, "endmodule\n"); + fclose(f); + + log("Extracted %d gates and %zd wires to a logic network with %d inputs and %d outputs.\n", + count_gates, signal_list.size(), count_input, count_output); + log_push(); + + if (count_output > 0) + { + log_header("Executing ABC.\n"); + + if (asprintf(&p, "%s/stdcells.genlib", tempdir_name) < 0) abort(); + f = fopen(p, "wt"); + assert(f != NULL); + fprintf(f, "GATE ZERO 1 Y=CONST0;\n"); + fprintf(f, "GATE ONE 1 Y=CONST1;\n"); + fprintf(f, "GATE BUF 1 Y=A; PIN * NONINV 1 999 1 0 1 0\n"); + fprintf(f, "GATE INV 1 Y=!A; PIN * INV 1 999 1 0 1 0\n"); + fprintf(f, "GATE AND 1 Y=A*B; PIN * NONINV 1 999 1 0 1 0\n"); + fprintf(f, "GATE OR 1 Y=A+B; PIN * NONINV 1 999 1 0 1 0\n"); + fprintf(f, "GATE XOR 1 Y=(A*!B)+(!A*B); PIN * UNKNOWN 1 999 1 0 1 0\n"); + fprintf(f, "GATE MUX 1 Y=(A*B)+(S*B)+(!S*A); PIN * UNKNOWN 1 999 1 0 1 0\n"); + fclose(f); + free(p); + + char buffer[1024]; + if (!liberty_file.empty()) + snprintf(buffer, 1024, "%s -c 'read_verilog %s/input.v; read_liberty %s; " + "map; write_verilog %s/output.v' 2>&1", exe_file.c_str(), tempdir_name, liberty_file.c_str(), tempdir_name); + else + if (!script_file.empty()) + snprintf(buffer, 1024, "%s -c 'read_verilog %s/input.v; source %s; " + "map; write_verilog %s/output.v' 2>&1", exe_file.c_str(), tempdir_name, script_file.c_str(), tempdir_name); + else + snprintf(buffer, 1024, "%s -c 'read_verilog %s/input.v; read_library %s/stdcells.genlib; " + "map; write_verilog %s/output.v' 2>&1", exe_file.c_str(), tempdir_name, tempdir_name, tempdir_name); + f = popen(buffer, "r"); + while (fgets(buffer, 1024, f) != NULL) + log("ABC: %s", buffer); + fclose(f); + + if (asprintf(&p, "%s/output.v", tempdir_name) < 0) abort(); + f = fopen(p, "rt"); + if (f == NULL) + log_error("Can't open ABC output file `%s'.\n", p); +#if 0 + RTLIL::Design *mapped_design = new RTLIL::Design; + frontend_register["verilog"]->execute(f, p, std::vector<std::string>(), mapped_design); +#else + RTLIL::Design *mapped_design = abc_parse_verilog(f); +#endif + fclose(f); + free(p); + + log_header("Re-integrating ABC results.\n"); + RTLIL::Module *mapped_mod = mapped_design->modules["\\logic"]; + if (mapped_mod == NULL) + log_error("ABC output file does not contain a module `logic'.\n"); + for (auto &it : mapped_mod->wires) { + RTLIL::Wire *w = it.second; + RTLIL::Wire *wire = new RTLIL::Wire; + wire->name = remap_name(w->name); + module->wires[wire->name] = wire; + } + + std::map<std::string, int> cell_stats; + if (liberty_file.empty() && script_file.empty()) + { + for (auto &it : mapped_mod->cells) { + RTLIL::Cell *c = it.second; + cell_stats[c->type.substr(1)]++; + if (c->type == "\\ZERO" || c->type == "\\ONE") { + RTLIL::SigSig conn; + conn.first = RTLIL::SigSpec(module->wires[remap_name(c->connections["\\Y"].chunks[0].wire->name)]); + conn.second = RTLIL::SigSpec(c->type == "\\ZERO" ? 0 : 1, 1); + module->connections.push_back(conn); + continue; + } + if (c->type == "\\BUF") { + RTLIL::SigSig conn; + conn.first = RTLIL::SigSpec(module->wires[remap_name(c->connections["\\Y"].chunks[0].wire->name)]); + conn.second = RTLIL::SigSpec(module->wires[remap_name(c->connections["\\A"].chunks[0].wire->name)]); + module->connections.push_back(conn); + continue; + } + if (c->type == "\\INV") { + RTLIL::Cell *cell = new RTLIL::Cell; + cell->type = "$_INV_"; + cell->name = remap_name(c->name); + cell->connections["\\A"] = RTLIL::SigSpec(module->wires[remap_name(c->connections["\\A"].chunks[0].wire->name)]); + cell->connections["\\Y"] = RTLIL::SigSpec(module->wires[remap_name(c->connections["\\Y"].chunks[0].wire->name)]); + module->cells[cell->name] = cell; + continue; + } + if (c->type == "\\AND" || c->type == "\\OR" || c->type == "\\XOR") { + RTLIL::Cell *cell = new RTLIL::Cell; + cell->type = "$_" + c->type.substr(1) + "_"; + cell->name = remap_name(c->name); + cell->connections["\\A"] = RTLIL::SigSpec(module->wires[remap_name(c->connections["\\A"].chunks[0].wire->name)]); + cell->connections["\\B"] = RTLIL::SigSpec(module->wires[remap_name(c->connections["\\B"].chunks[0].wire->name)]); + cell->connections["\\Y"] = RTLIL::SigSpec(module->wires[remap_name(c->connections["\\Y"].chunks[0].wire->name)]); + module->cells[cell->name] = cell; + continue; + } + if (c->type == "\\MUX") { + RTLIL::Cell *cell = new RTLIL::Cell; + cell->type = "$_MUX_"; + cell->name = remap_name(c->name); + cell->connections["\\A"] = RTLIL::SigSpec(module->wires[remap_name(c->connections["\\A"].chunks[0].wire->name)]); + cell->connections["\\B"] = RTLIL::SigSpec(module->wires[remap_name(c->connections["\\B"].chunks[0].wire->name)]); + cell->connections["\\S"] = RTLIL::SigSpec(module->wires[remap_name(c->connections["\\S"].chunks[0].wire->name)]); + cell->connections["\\Y"] = RTLIL::SigSpec(module->wires[remap_name(c->connections["\\Y"].chunks[0].wire->name)]); + module->cells[cell->name] = cell; + continue; + } + assert(0); + } + } + else + { + for (auto &it : mapped_mod->cells) { + RTLIL::Cell *c = it.second; + cell_stats[c->type.substr(1)]++; + if (c->type == "$_const0_" || c->type == "$_const1_") { + RTLIL::SigSig conn; + conn.first = RTLIL::SigSpec(module->wires[remap_name(c->connections["\\Y"].chunks[0].wire->name)]); + conn.second = RTLIL::SigSpec(c->type == "$_const0_" ? 0 : 1, 1); + module->connections.push_back(conn); + continue; + } + RTLIL::Cell *cell = new RTLIL::Cell; + cell->type = c->type; + cell->name = remap_name(c->name); + for (auto &conn : c->connections) + cell->connections[conn.first] = RTLIL::SigSpec(module->wires[remap_name(conn.second.chunks[0].wire->name)]); + module->cells[cell->name] = cell; + } + } + + for (auto &it : cell_stats) + log("ABC RESULTS: %15s cells: %8d\n", it.first.c_str(), it.second); + int in_wires = 0, out_wires = 0; + for (auto &si : signal_list) + if (si.is_port) { + char buffer[100]; + snprintf(buffer, 100, "\\n%d", si.id); + RTLIL::SigSig conn; + if (si.type >= 0) { + conn.first = si.sig; + conn.second = RTLIL::SigSpec(module->wires[remap_name(buffer)]); + out_wires++; + } else { + conn.first = RTLIL::SigSpec(module->wires[remap_name(buffer)]); + conn.second = si.sig; + in_wires++; + } + module->connections.push_back(conn); + } + log("ABC RESULTS: internal signals: %8d\n", int(signal_list.size()) - in_wires - out_wires); + log("ABC RESULTS: input signals: %8d\n", in_wires); + log("ABC RESULTS: output signals: %8d\n", out_wires); + + delete mapped_design; + } + else + { + log("Don't call ABC as there is nothing to map.\n"); + } + + if (cleanup) + { + log_header("Removing temp directory `%s':\n", tempdir_name); + + struct dirent **namelist; + int n = scandir(tempdir_name, &namelist, 0, alphasort); + assert(n >= 0); + for (int i = 0; i < n; i++) { + if (strcmp(namelist[i]->d_name, ".") && strcmp(namelist[i]->d_name, "..")) { + if (asprintf(&p, "%s/%s", tempdir_name, namelist[i]->d_name) < 0) abort(); + log("Removing `%s'.\n", p); + remove(p); + free(p); + } + free(namelist[i]); + } + free(namelist); + log("Removing `%s'.\n", tempdir_name); + rmdir(tempdir_name); + } + + log_pop(); +} + +struct AbcPass : public Pass { + AbcPass() : Pass("abc") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing ABC pass (technology mapping using ABC).\n"); + log_push(); + + std::string exe_file = "abc"; + std::string script_file, liberty_file; + bool cleanup = true; + + size_t argidx; + char *pwd = get_current_dir_name(); + for (argidx = 1; argidx < args.size(); argidx++) { + std::string arg = args[argidx]; + if (arg == "-exe" && argidx+1 < args.size()) { + exe_file = args[++argidx]; + continue; + } + if (arg == "-script" && argidx+1 < args.size() && liberty_file.empty()) { + script_file = args[++argidx]; + if (!script_file.empty() && script_file[0] != '/') + script_file = std::string(pwd) + "/" + script_file; + continue; + } + if (arg == "-liberty" && argidx+1 < args.size() && script_file.empty()) { + liberty_file = args[++argidx]; + if (!liberty_file.empty() && liberty_file[0] != '/') + liberty_file = std::string(pwd) + "/" + liberty_file; + continue; + } + if (arg == "-nocleanup") { + cleanup = false; + continue; + } + break; + } + free(pwd); + extra_args(args, argidx, design); + + for (auto &mod_it : design->modules) { + if (mod_it.second->processes.size() > 0) + log("Skipping module %s as it contains processes.\n", mod_it.second->name.c_str()); + else + abc_module(mod_it.second, script_file, exe_file, liberty_file, cleanup); + } + + assign_map.clear(); + signal_list.clear(); + signal_map.clear(); + + log_pop(); + } +} AbcPass; + diff --git a/passes/abc/vlparse.cc b/passes/abc/vlparse.cc new file mode 100644 index 000000000..5c0cb7e24 --- /dev/null +++ b/passes/abc/vlparse.cc @@ -0,0 +1,198 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "vlparse.h" +#include "kernel/log.h" +#include <stdio.h> +#include <string> + +static int lex_line, lex_tok; +static std::string lex_str; + +static int token(int tok) +{ + lex_tok = tok; +#if 0 + if (lex_tok == 256) + fprintf(stderr, "STR in line %d: >>%s<<\n", lex_line, lex_str.c_str()); + else if (tok >= 32 && tok < 255) + fprintf(stderr, "CHAR in line %d: >>%c<<\n", lex_line, lex_tok); + else + fprintf(stderr, "CHAR in line %d: %d\n", lex_line, lex_tok); +#endif + return tok; +} + +static int lex(FILE *f) +{ + int ch = getc(f); + + while (ch == ' ' || ch == '\t' || ch == '\n') { + if (ch == '\n') + lex_line++; + ch = getc(f); + } + + if (ch <= 0 || 255 < ch) + return token(lex_tok); + + if (('a' <= ch && ch <= 'z') || ('A' <= ch && ch <= 'Z') || + ('0' <= ch && ch <= '9') || ch == '_') { + lex_str = char(ch); + while (1) { + ch = getc(f); + if (('a' <= ch && ch <= 'z') || ('A' <= ch && ch <= 'Z') || + ('0' <= ch && ch <= '9') || ch == '_') { + lex_str += char(ch); + continue; + } + break; + } + ungetc(ch, f); + return token(256); + } + + if (ch == '/') { + ch = getc(f); + if (ch == '/') { + while (ch != '\n') + ch = getc(f); + ungetc(ch, f); + return lex(f); + } + ungetc(ch, f); + return token('/'); + } + + return token(ch); +} + +RTLIL::Design *abc_parse_verilog(FILE *f) +{ + RTLIL::Design *design = new RTLIL::Design; + RTLIL::Module *module; + RTLIL::Wire *wire; + RTLIL::Cell *cell; + + int port_count = 1; + lex_line = 1; + + // parse module header + if (lex(f) != 256 || lex_str != "module") + goto error; + if (lex(f) != 256) + goto error; + + module = new RTLIL::Module; + module->name = "\\" + lex_str; + design->modules[module->name] = module; + + if (lex(f) != '(') + goto error; + while (lex(f) != ')') { + if (lex_tok != 256 && lex_tok != ',') + goto error; + } + if (lex(f) != ';') + goto error; + + // parse module body + while (1) + { + if (lex(f) != 256) + goto error; + + if (lex_str == "endmodule") + return design; + + if (lex_str == "input" || lex_str == "output" || lex_str == "wire") + { + std::string mode = lex_str; + while (lex(f) != ';') { + if (lex_tok != 256 && lex_tok != ',') + goto error; + if (lex_tok == 256) { + // printf("%s [%s]\n", mode.c_str(), lex_str.c_str()); + wire = new RTLIL::Wire; + wire->name = "\\" + lex_str; + if (mode == "input") { + wire->port_id = port_count++; + wire->port_input = true; + } + if (mode == "output") { + wire->port_id = port_count++; + wire->port_output = true; + } + module->wires[wire->name] = wire; + } + } + } + else + { + std::string cell_type = lex_str; + + if (lex(f) != 256) + goto error; + + std::string cell_name = lex_str; + + if (lex(f) != '(') + goto error; + + // printf("cell [%s] [%s]\n", cell_type.c_str(), cell_name.c_str()); + cell = new RTLIL::Cell; + cell->type = "\\" + cell_type; + cell->name = "\\" + cell_name; + module->cells[cell->name] = cell; + + lex(f); + while (lex_tok != ')') + { + if (lex_tok != '.' || lex(f) != 256) + goto error; + + std::string cell_port = lex_str; + + if (lex(f) != '(' || lex(f) != 256) + goto error; + + std::string wire_name = lex_str; + + // printf(" [%s] <- [%s]\n", cell_port.c_str(), wire_name.c_str()); + if (module->wires.count("\\" + wire_name) == 0) + goto error; + cell->connections["\\" + cell_port] = RTLIL::SigSpec(module->wires["\\" + wire_name]); + + if (lex(f) != ')' || (lex(f) != ',' && lex_tok != ')')) + goto error; + while (lex_tok == ',') + lex(f); + } + + if (lex(f) != ';') + goto error; + } + } + +error: + log_error("Syntax error in line %d!\n", lex_line); + // delete design; + // return NULL; +} + diff --git a/passes/abc/vlparse.h b/passes/abc/vlparse.h new file mode 100644 index 000000000..9514c4190 --- /dev/null +++ b/passes/abc/vlparse.h @@ -0,0 +1,28 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#ifndef ABC_VLPARSE +#define ABC_VLPARSE + +#include "kernel/rtlil.h" + +extern RTLIL::Design *abc_parse_verilog(FILE *f); + +#endif + diff --git a/passes/dfflibmap/Makefile.inc b/passes/dfflibmap/Makefile.inc new file mode 100644 index 000000000..ed92b299c --- /dev/null +++ b/passes/dfflibmap/Makefile.inc @@ -0,0 +1,10 @@ + +OBJS += passes/dfflibmap/dfflibmap.o +OBJS += passes/dfflibmap/libparse.o + +TARGETS += filterlib +GENFILES += passes/dfflibmap/filterlib.o + +filterlib: passes/dfflibmap/filterlib.o + $(CXX) -o filterlib $(LDFLAGS) $^ $(LDLIBS) + diff --git a/passes/dfflibmap/dfflibmap.cc b/passes/dfflibmap/dfflibmap.cc new file mode 100644 index 000000000..86e8bcbf6 --- /dev/null +++ b/passes/dfflibmap/dfflibmap.cc @@ -0,0 +1,326 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/register.h" +#include "kernel/log.h" +#include "libparse.h" +#include <string.h> + +using namespace PASS_DFFLIBMAP; + +struct cell_mapping { + std::string cell_name; + std::map<std::string, char> ports; +}; +static std::map<std::string, cell_mapping> cell_mappings; + +static void logmap(std::string dff) +{ + if (cell_mappings.count(dff) == 0) { + log(" unmapped dff cell: %s\n", dff.c_str()); + } else { + log(" %s %s(", cell_mappings[dff].cell_name.c_str(), dff.substr(1).c_str()); + bool first = true; + for (auto &port : cell_mappings[dff].ports) { + char arg[3] = { port.second, 0, 0 }; + if ('a' <= arg[0] && arg[0] <= 'z') + arg[1] = arg[0] - ('a' - 'A'), arg[0] = '~'; + log("%s.%s(%s)", first ? "" : ", ", port.first.c_str(), arg); + first = false; + } + log(");\n"); + } +} + +static void logmap_all() +{ + logmap("$_DFF_N_"); + logmap("$_DFF_P_"); + logmap("$_DFF_NN0_"); + logmap("$_DFF_NN1_"); + logmap("$_DFF_NP0_"); + logmap("$_DFF_NP1_"); + logmap("$_DFF_PN0_"); + logmap("$_DFF_PN1_"); + logmap("$_DFF_PP0_"); + logmap("$_DFF_PP1_"); +} + +static bool parse_pin(LibertyAst *cell, LibertyAst *attr, std::string &pin_name, bool &pin_pol) +{ + if (cell == NULL || attr == NULL || attr->value.empty()) + return false; + + std::string value = attr->value; + + for (size_t pos = value.find_first_of("\" \t"); pos != std::string::npos; pos = value.find_first_of("\" \t")) + value.erase(pos, 1); + + if (value[value.size()-1] == '\'') { + pin_name = value.substr(0, value.size()-1); + pin_pol = false; + } else { + pin_name = value; + pin_pol = true; + } + + for (auto child : cell->children) + if (child->id == "pin" && child->args.size() == 1 && child->args[0] == pin_name) + return true; + return false; +} + +static void find_cell(LibertyAst *ast, std::string cell_type, bool clkpol, bool has_reset, bool rstpol, bool rstval) +{ + LibertyAst *best_cell = NULL; + std::map<std::string, char> best_cell_ports; + int best_cell_pins = 0; + + if (ast->id != "library") + log_error("Format error in liberty file.\n"); + + for (auto cell : ast->children) + { + if (cell->id != "cell" || cell->args.size() != 1) + continue; + + LibertyAst *ff = cell->find("ff"); + if (ff == NULL) + continue; + + std::string cell_clk_pin, cell_rst_pin, cell_next_pin; + bool cell_clk_pol, cell_rst_pol, cell_next_pol; + + if (!parse_pin(cell, ff->find("clocked_on"), cell_clk_pin, cell_clk_pol) || cell_clk_pol != clkpol) + continue; + if (!parse_pin(cell, ff->find("next_state"), cell_next_pin, cell_next_pol)) + continue; + if (has_reset && rstval == false) { + if (!parse_pin(cell, ff->find("clear"), cell_rst_pin, cell_rst_pol) || cell_rst_pol != rstpol) + continue; + } + if (has_reset && rstval == true) { + if (!parse_pin(cell, ff->find("preset"), cell_rst_pin, cell_rst_pol) || cell_rst_pol != rstpol) + continue; + } + + std::map<std::string, char> this_cell_ports; + this_cell_ports[cell_clk_pin] = 'C'; + if (has_reset) + this_cell_ports[cell_rst_pin] = 'R'; + this_cell_ports[cell_next_pin] = 'D'; + + int num_pins = 0; + bool found_output = false; + for (auto pin : cell->children) + { + if (pin->id != "pin" || pin->args.size() != 1) + continue; + + LibertyAst *dir = pin->find("direction"); + if (dir == NULL || dir->value == "internal") + continue; + num_pins++; + + if (dir->value == "input" && this_cell_ports.count(pin->args[0]) == 0) + goto continue_cell_loop; + + LibertyAst *func = pin->find("function"); + if (dir->value == "output" && func != NULL) { + std::string value = func->value; + for (size_t pos = value.find_first_of("\" \t"); pos != std::string::npos; pos = value.find_first_of("\" \t")) + value.erase(pos, 1); + if ((cell_next_pol == true && value == ff->args[0]) || (cell_next_pol == false && value == ff->args[1])) { + this_cell_ports[pin->args[0]] = 'Q'; + found_output = true; + } + } + + if (this_cell_ports.count(pin->args[0]) == 0) + this_cell_ports[pin->args[0]] = 0; + } + + if (!found_output || (best_cell != NULL && num_pins > best_cell_pins)) + continue; + + best_cell = cell; + best_cell_pins = num_pins; + best_cell_ports.swap(this_cell_ports); + continue_cell_loop:; + } + + if (best_cell != NULL) { + log(" cell %s is a direct match for cell type %s.\n", best_cell->args[0].c_str(), cell_type.substr(1).c_str()); + cell_mappings[cell_type].cell_name = best_cell->args[0]; + cell_mappings[cell_type].ports = best_cell_ports; + } +} + +static bool expand_cellmap_worker(std::string from, std::string to, std::string inv) +{ + if (cell_mappings.count(to) > 0) + return false; + + log(" create mapping for %s from mapping for %s.\n", to.c_str(), from.c_str()); + cell_mappings[to].cell_name = cell_mappings[from].cell_name; + cell_mappings[to].ports = cell_mappings[from].ports; + + for (auto &it : cell_mappings[to].ports) { + if (inv.find(it.second) == std::string::npos) + continue; + if ('a' <= it.second && it.second <= 'z') + it.second -= 'a' - 'A'; + else if ('A' <= it.second && it.second <= 'Z') + it.second += 'a' - 'A'; + } + return true; +} + +static bool expand_cellmap(std::string pattern, std::string inv) +{ + std::vector<std::pair<std::string, std::string>> from_to_list; + bool return_status = false; + + for (auto &it : cell_mappings) { + std::string from = it.first, to = it.first; + if (from.size() != pattern.size()) + continue; + for (size_t i = 0; i < from.size(); i++) { + if (pattern[i] == '*') { + to[i] = from[i] == 'P' ? 'N' : + from[i] == 'N' ? 'P' : + from[i] == '1' ? '0' : + from[i] == '0' ? '1' : '*'; + } else + if (pattern[i] != '?' && pattern[i] != from[i]) + goto pattern_failed; + } + from_to_list.push_back(std::pair<std::string, std::string>(from, to)); + pattern_failed:; + } + + for (auto &it : from_to_list) + return_status = return_status || expand_cellmap_worker(it.first, it.second, inv); + return return_status; +} + +static void dfflibmap(RTLIL::Module *module) +{ + log("Mapping DFF cells in module `%s':\n", module->name.c_str()); + + std::vector<RTLIL::Cell*> cell_list; + for (auto &it : module->cells) { + if (cell_mappings.count(it.second->type) > 0) + cell_list.push_back(it.second); + } + + std::map<std::string, int> stats; + for (auto cell : cell_list) { + cell_mapping &cm = cell_mappings[cell->type]; + RTLIL::Cell *new_cell = new RTLIL::Cell; + new_cell->name = cell->name; + new_cell->type = "\\" + cm.cell_name; + for (auto &port : cm.ports) { + RTLIL::SigSpec sig; + if ('A' <= port.second && port.second <= 'Z') { + sig = cell->connections[std::string("\\") + port.second]; + } else + if ('a' <= port.second && port.second <= 'z') { + sig = cell->connections[std::string("\\") + char(port.second - ('a' - 'A'))]; + RTLIL::Cell *inv_cell = new RTLIL::Cell; + RTLIL::Wire *inv_wire = new RTLIL::Wire; + inv_cell->name = stringf("$dfflibmap$inv$%d", RTLIL::autoidx); + inv_wire->name = stringf("$dfflibmap$sig$%d", RTLIL::autoidx++); + inv_cell->type = "$_INV_"; + inv_cell->connections[port.second == 'q' ? "\\Y" : "\\A"] = sig; + sig = RTLIL::SigSpec(inv_wire); + inv_cell->connections[port.second == 'q' ? "\\A" : "\\Y"] = sig; + module->cells[inv_cell->name] = inv_cell; + module->wires[inv_wire->name] = inv_wire; + } + new_cell->connections["\\" + port.first] = sig; + } + stats[stringf(" mapped %%d %s cells to %s cells.\n", cell->type.c_str(), new_cell->type.c_str())]++; + module->cells[cell->name] = new_cell; + delete cell; + } + + for (auto &stat: stats) + log(stat.first.c_str(), stat.second); +} + +struct DfflibmapPass : public Pass { + DfflibmapPass() : Pass("dfflibmap") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing DFFLIBMAP pass (mapping DFF cells to sequential cells from liberty file).\n"); + + std::string liberty_file; + + size_t argidx; + for (argidx = 1; argidx < args.size(); argidx++) + { + std::string arg = args[argidx]; + if (arg == "-liberty" && argidx+1 < args.size()) { + liberty_file = args[++argidx]; + continue; + } + break; + } + extra_args(args, argidx, design); + + if (liberty_file.empty()) + log_cmd_error("Missing `-liberty liberty_file' option!\n"); + + FILE *f = fopen(liberty_file.c_str(), "r"); + if (f == NULL) + log_cmd_error("Can't open liberty file `%s': %s\n", liberty_file.c_str(), strerror(errno)); + LibertyParer libparser(f); + fclose(f); + + find_cell(libparser.ast, "$_DFF_N_", false, false, false, false); + find_cell(libparser.ast, "$_DFF_P_", true, false, false, false); + find_cell(libparser.ast, "$_DFF_NN0_", false, true, false, false); + find_cell(libparser.ast, "$_DFF_NN1_", false, true, false, true); + find_cell(libparser.ast, "$_DFF_NP0_", false, true, true, false); + find_cell(libparser.ast, "$_DFF_NP1_", false, true, true, true); + find_cell(libparser.ast, "$_DFF_PN0_", true, true, false, false); + find_cell(libparser.ast, "$_DFF_PN1_", true, true, false, true); + find_cell(libparser.ast, "$_DFF_PP0_", true, true, true, false); + find_cell(libparser.ast, "$_DFF_PP1_", true, true, true, true); + + bool keep_running = true; + while (keep_running) { + keep_running = false; + keep_running |= expand_cellmap("$_DFF_*_", "C"); + keep_running |= expand_cellmap("$_DFF_*??_", "C"); + keep_running |= expand_cellmap("$_DFF_?*?_", "R"); + keep_running |= expand_cellmap("$_DFF_??*_", "DQ"); + } + + log(" final dff cell mappings:\n"); + logmap_all(); + + for (auto &it : design->modules) + dfflibmap(it.second); + + cell_mappings.clear(); + } +} DfflibmapPass; + diff --git a/passes/dfflibmap/filterlib.cc b/passes/dfflibmap/filterlib.cc new file mode 100644 index 000000000..05cfa6d24 --- /dev/null +++ b/passes/dfflibmap/filterlib.cc @@ -0,0 +1,4 @@ + +#define FILTERLIB +#include "libparse.cc" + diff --git a/passes/dfflibmap/libparse.cc b/passes/dfflibmap/libparse.cc new file mode 100644 index 000000000..8fc03b5c9 --- /dev/null +++ b/passes/dfflibmap/libparse.cc @@ -0,0 +1,629 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "libparse.h" +#include <stdlib.h> +#include <string.h> + +#ifndef FILTERLIB +#include "kernel/log.h" +#endif + +using namespace PASS_DFFLIBMAP; + +std::set<std::string> LibertyAst::blacklist; +std::set<std::string> LibertyAst::whitelist; + +LibertyAst::~LibertyAst() +{ + for (auto child : children) + delete child; + children.clear(); +} + +LibertyAst *LibertyAst::find(std::string name) +{ + if (this == NULL) + return NULL; + for (auto child : children) + if (child->id == name) + return child; + return NULL; +} + +void LibertyAst::dump(FILE *f, std::string indent, std::string path, bool path_ok) +{ + if (whitelist.count(path + "/*") > 0) + path_ok = true; + + path += "/" + id; + + if (blacklist.count(id) > 0 || blacklist.count(path) > 0) + return; + if (whitelist.size() > 0 && whitelist.count(id) == 0 && whitelist.count(path) == 0 && !path_ok) { + fprintf(stderr, "Automatically added to blacklist: %s\n", path.c_str()); + blacklist.insert(id); + return; + } + + fprintf(f, "%s%s", indent.c_str(), id.c_str()); + if (!args.empty()) { + for (size_t i = 0; i < args.size(); i++) + fprintf(f, "%s%s", i > 0 ? ", " : "(", args[i].c_str()); + fprintf(f, ")"); + } + if (!value.empty()) + fprintf(f, " : %s", value.c_str()); + if (!children.empty()) { + fprintf(f, " {\n"); + for (size_t i = 0; i < children.size(); i++) + children[i]->dump(f, indent + " ", path, path_ok); + fprintf(f, "%s}\n", indent.c_str()); + } else + fprintf(f, " ;\n"); +} + +int LibertyParer::lexer(std::string &str) +{ + int c; + + do { + c = fgetc(f); + } while (c == ' ' || c == '\t' || c == '\r'); + + if (('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z') || ('0' <= c && c <= '9') || c == '_' || c == '-' || c == '.') { + str = c; + while (1) { + c = fgetc(f); + if (('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z') || ('0' <= c && c <= '9') || c == '_' || c == '-' || c == '.') + str += c; + else + break; + } + ungetc(c, f); + // fprintf(stderr, "LEX: identifier >>%s<<\n", str.c_str()); + return 'v'; + } + + if (c == '"') { + str = c; + while (1) { + c = fgetc(f); + if (c == '\n') + line++; + str += c; + if (c == '"') + break; + } + // fprintf(stderr, "LEX: string >>%s<<\n", str.c_str()); + return 'v'; + } + + if (c == '/') { + c = fgetc(f); + if (c == '*') { + int last_c = 0; + while (c > 0 && (last_c != '*' || c != '/')) { + last_c = c; + c = fgetc(f); + if (c == '\n') + line++; + } + return lexer(str); + } + ungetc(c, f); + // fprintf(stderr, "LEX: char >>/<<\n"); + return '/'; + } + + if (c == '\\') { + c = fgetc(f); + if (c == '\r') + c = fgetc(f); + if (c == '\n') + return lexer(str); + ungetc(c, f); + return '\\'; + } + + if (c == '\n') { + line++; + return ';'; + } + + // if (c >= 32 && c < 255) + // fprintf(stderr, "LEX: char >>%c<<\n", c); + // else + // fprintf(stderr, "LEX: char %d\n", c); + return c; +} + +LibertyAst *LibertyParer::parse() +{ + std::string str; + + int tok = lexer(str); + + while (tok == ';') + tok = lexer(str); + + if (tok == '}' || tok < 0) + return NULL; + + if (tok != 'v') + error(); + + LibertyAst *ast = new LibertyAst; + ast->id = str; + + while (1) + { + tok = lexer(str); + + if (tok == ';') + break; + + if (tok == ':' && ast->value.empty()) { + tok = lexer(ast->value); + if (tok != 'v') + error(); + continue; + } + + if (tok == '(') { + while (1) { + std::string arg; + tok = lexer(arg); + if (tok == ',') + continue; + if (tok == ')') + break; + if (tok != 'v') + error(); + ast->args.push_back(arg); + } + continue; + } + + if (tok == '{') { + while (1) { + LibertyAst *child = parse(); + if (child == NULL) + break; + ast->children.push_back(child); + } + break; + } + + error(); + } + + return ast; +} + +#ifndef FILTERLIB + +void LibertyParer::error() +{ + log_error("Syntax error in line %d.\n", line); +} + +#else + +void LibertyParer::error() +{ + fprintf(stderr, "Syntax error in line %d.\n", line); + exit(1); +} + +/**** BEGIN: http://svn.clifford.at/tools/trunk/examples/check.h ****/ + +// This is to not confuse the VIM syntax highlighting +#define CHECK_VAL_OPEN ( +#define CHECK_VAL_CLOSE ) + +#define CHECK(result, check) \ + CHECK_VAL_OPEN{ \ + auto _R = (result); \ + if (!(_R check)) { \ + fprintf(stderr, "Error from '%s' (%ld %s) in %s:%d.\n", \ + #result, (long int)_R, #check, __FILE__, __LINE__); \ + abort(); \ + } \ + _R; \ + }CHECK_VAL_CLOSE + +#define CHECK_NV(result, check) \ + do { \ + auto _R = (result); \ + if (!(_R check)) { \ + fprintf(stderr, "Error from '%s' (%ld %s) in %s:%d.\n", \ + #result, (long int)_R, #check, __FILE__, __LINE__); \ + abort(); \ + } \ + } while(0) + +#define CHECK_COND(result) \ + do { \ + if (!(result)) { \ + fprintf(stderr, "Error from '%s' in %s:%d.\n", \ + #result, __FILE__, __LINE__); \ + abort(); \ + } \ + } while(0) + +/**** END: http://svn.clifford.at/tools/trunk/examples/check.h ****/ + +std::string func2vl(std::string str) +{ + for (size_t pos = str.find_first_of("\" \t"); pos != std::string::npos; pos = str.find_first_of("\" \t")) { + char c_left = pos > 0 ? str[pos-1] : ' '; + char c_right = pos+1 < str.size() ? str[pos+1] : ' '; + if (std::string("\" \t*+").find(c_left) != std::string::npos) + str.erase(pos, 1); + else if (std::string("\" \t*+").find(c_right) != std::string::npos) + str.erase(pos, 1); + else + str[pos] = '*'; + } + + std::vector<size_t> group_start; + for (size_t pos = 0; pos < str.size(); pos++) { + if (str[pos] == '(') + group_start.push_back(pos); + if (str[pos] == ')' && group_start.size() > 0) { + if (pos+1 < str.size() && str[pos+1] == '\'') { + std::string group = str.substr(group_start.back(), pos-group_start.back()+1); + str[group_start.back()] = '~'; + str.replace(group_start.back()+1, group.size(), group); + pos++; + } + group_start.pop_back(); + } + if (str[pos] == '\'' && pos > 0) { + size_t start = str.find_last_of("()'*+^&| ", pos-1)+1; + std::string group = str.substr(start, pos-start); + str[start] = '~'; + str.replace(start+1, group.size(), group); + } + if (str[pos] == '*') + str[pos] = '&'; + if (str[pos] == '+') + str[pos] = '|'; + } + + return str; +} + +void event2vl(LibertyAst *ast, std::string &edge, std::string &expr) +{ + edge.clear(); + expr.clear(); + + if (ast != NULL) { + expr = func2vl(ast->value); + if (expr.size() > 0 && expr[0] == '~') + edge = "negedge " + expr.substr(1); + else + edge = "posedge " + expr; + } +} + +void clear_preset_var(std::string var, std::string type) +{ + if (type.find('L') != std::string::npos) { + printf(" %s <= 0;\n", var.c_str()); + return; + } + if (type.find('H') != std::string::npos) { + printf(" %s <= 1;\n", var.c_str()); + return; + } + if (type.find('T') != std::string::npos) { + printf(" %s <= ~%s;\n", var.c_str(), var.c_str()); + return; + } + if (type.find('X') != std::string::npos) { + printf(" %s <= 'bx;\n", var.c_str()); + return; + } +} + +void gen_verilogsim_cell(LibertyAst *ast) +{ + if (ast->find("statetable") != NULL) + return; + + CHECK_NV(ast->args.size(), == 1); + printf("module %s (", ast->args[0].c_str()); + bool first = true; + for (auto child : ast->children) { + if (child->id != "pin") + continue; + CHECK_NV(child->args.size(), == 1); + printf("%s%s", first ? "" : ", ", child->args[0].c_str()); + first = false; + } + printf(");\n"); + + for (auto child : ast->children) { + if (child->id != "ff" && child->id != "latch") + continue; + printf(" reg "); + first = true; + for (auto arg : child->args) { + printf("%s%s", first ? "" : ", ", arg.c_str()); + first = false; + } + printf(";\n"); + } + + for (auto child : ast->children) { + if (child->id != "pin") + continue; + CHECK_NV(child->args.size(), == 1); + LibertyAst *dir = CHECK(child->find("direction"), != NULL); + LibertyAst *func = child->find("function"); + printf(" %s %s;\n", dir->value.c_str(), child->args[0].c_str()); + if (func != NULL) + printf(" assign %s = %s; // %s\n", child->args[0].c_str(), func2vl(func->value).c_str(), func->value.c_str()); + } + + for (auto child : ast->children) + { + if (child->id != "ff" || child->args.size() != 2) + continue; + + std::string iq_var = child->args[0]; + std::string iqn_var = child->args[1]; + + std::string clock_edge, clock_expr; + event2vl(child->find("clocked_on"), clock_edge, clock_expr); + + std::string clear_edge, clear_expr; + event2vl(child->find("clear"), clear_edge, clear_expr); + + std::string preset_edge, preset_expr; + event2vl(child->find("preset"), preset_edge, preset_expr); + + std::string edge = ""; + if (!clock_edge.empty()) + edge += (edge.empty() ? "" : ", ") + clock_edge; + if (!clear_edge.empty()) + edge += (edge.empty() ? "" : ", ") + clear_edge; + if (!preset_edge.empty()) + edge += (edge.empty() ? "" : ", ") + preset_edge; + + if (edge.empty()) + continue; + + printf(" always @(%s) begin\n", edge.c_str()); + + const char *else_prefix = ""; + if (!clear_expr.empty() && !preset_expr.empty()) { + printf(" %sif ((%s) && (%s)) begin\n", else_prefix, clear_expr.c_str(), preset_expr.c_str()); + clear_preset_var(iq_var, CHECK(child->find("clear_preset_var1"), != NULL)->value); + clear_preset_var(iqn_var, CHECK(child->find("clear_preset_var2"), != NULL)->value); + printf(" end\n"); + else_prefix = "else "; + } + if (!clear_expr.empty()) { + printf(" %sif (%s) begin\n", else_prefix, clear_expr.c_str()); + printf(" %s <= 0;\n", iq_var.c_str()); + printf(" %s <= 1;\n", iqn_var.c_str()); + printf(" end\n"); + else_prefix = "else "; + } + if (!preset_expr.empty()) { + printf(" %sif (%s) begin\n", else_prefix, preset_expr.c_str()); + printf(" %s <= 1;\n", iq_var.c_str()); + printf(" %s <= 0;\n", iqn_var.c_str()); + printf(" end\n"); + else_prefix = "else "; + } + if (*else_prefix) + printf(" %sbegin\n", else_prefix); + std::string expr = CHECK(child->find("next_state"), != NULL)->value; + printf(" // %s\n", expr.c_str()); + printf(" %s <= %s;\n", iq_var.c_str(), func2vl(expr).c_str()); + printf(" %s <= ~(%s);\n", iqn_var.c_str(), func2vl(expr).c_str()); + if (*else_prefix) + printf(" end\n"); + + printf(" end\n"); + } + + for (auto child : ast->children) + { + if (child->id != "latch" || child->args.size() != 2) + continue; + + std::string iq_var = child->args[0]; + std::string iqn_var = child->args[1]; + + std::string enable_edge, enable_expr; + event2vl(child->find("enable"), enable_edge, enable_expr); + + std::string clear_edge, clear_expr; + event2vl(child->find("clear"), clear_edge, clear_expr); + + std::string preset_edge, preset_expr; + event2vl(child->find("preset"), preset_edge, preset_expr); + + printf(" always @* begin\n"); + + const char *else_prefix = ""; + if (!clear_expr.empty() && !preset_expr.empty()) { + printf(" %sif ((%s) && (%s)) begin\n", else_prefix, clear_expr.c_str(), preset_expr.c_str()); + clear_preset_var(iq_var, CHECK(child->find("clear_preset_var1"), != NULL)->value); + clear_preset_var(iqn_var, CHECK(child->find("clear_preset_var2"), != NULL)->value); + printf(" end\n"); + else_prefix = "else "; + } + if (!clear_expr.empty()) { + printf(" %sif (%s) begin\n", else_prefix, clear_expr.c_str()); + printf(" %s <= 0;\n", iq_var.c_str()); + printf(" %s <= 1;\n", iqn_var.c_str()); + printf(" end\n"); + else_prefix = "else "; + } + if (!preset_expr.empty()) { + printf(" %sif (%s) begin\n", else_prefix, preset_expr.c_str()); + printf(" %s <= 1;\n", iq_var.c_str()); + printf(" %s <= 0;\n", iqn_var.c_str()); + printf(" end\n"); + else_prefix = "else "; + } + if (!enable_expr.empty()) { + printf(" %sif (%s) begin\n", else_prefix, enable_expr.c_str()); + std::string expr = CHECK(child->find("data_in"), != NULL)->value; + printf(" %s <= %s;\n", iq_var.c_str(), func2vl(expr).c_str()); + printf(" %s <= ~(%s);\n", iqn_var.c_str(), func2vl(expr).c_str()); + printf(" end\n"); + else_prefix = "else "; + } + + printf(" end\n"); + } + + printf("endmodule\n"); +} + +void gen_verilogsim(LibertyAst *ast) +{ + CHECK_COND(ast->id == "library"); + + for (auto child : ast->children) + if (child->id == "cell" && !child->find("dont_use")) + gen_verilogsim_cell(child); +} + +void usage() +{ + fprintf(stderr, "Usage: filterlib [rules-file [liberty-file]]\n"); + fprintf(stderr, " or: filterlib -verilogsim [liberty-file]\n"); + exit(1); +} + +int main(int argc, char **argv) +{ + bool flag_verilogsim = false; + + if (argc > 3) + usage(); + + if (argc > 1) + { + if (!strcmp(argv[1], "-verilogsim")) + flag_verilogsim = true; + if (!strcmp(argv[1], "-") || !strcmp(argv[1], "-verilogsim")) + { + LibertyAst::whitelist.insert("/library"); + LibertyAst::whitelist.insert("/library/cell"); + LibertyAst::whitelist.insert("/library/cell/area"); + LibertyAst::whitelist.insert("/library/cell/cell_footprint"); + LibertyAst::whitelist.insert("/library/cell/dont_touch"); + LibertyAst::whitelist.insert("/library/cell/dont_use"); + LibertyAst::whitelist.insert("/library/cell/ff"); + LibertyAst::whitelist.insert("/library/cell/ff/*"); + LibertyAst::whitelist.insert("/library/cell/latch"); + LibertyAst::whitelist.insert("/library/cell/latch/*"); + LibertyAst::whitelist.insert("/library/cell/pin"); + LibertyAst::whitelist.insert("/library/cell/pin/clock"); + LibertyAst::whitelist.insert("/library/cell/pin/direction"); + LibertyAst::whitelist.insert("/library/cell/pin/driver_type"); + LibertyAst::whitelist.insert("/library/cell/pin/function"); + LibertyAst::whitelist.insert("/library/cell/pin_opposite"); + LibertyAst::whitelist.insert("/library/cell/pin/state_function"); + LibertyAst::whitelist.insert("/library/cell/pin/three_state"); + LibertyAst::whitelist.insert("/library/cell/statetable"); + LibertyAst::whitelist.insert("/library/cell/statetable/*"); + } + else + { + FILE *f = fopen(argv[1], "r"); + if (f == NULL) { + fprintf(stderr, "Can't open rules file `%s'.\n", argv[1]); + usage(); + } + + char buffer[1024]; + while (fgets(buffer, 1024, f) != NULL) + { + char mode = 0; + std::string id; + for (char *p = buffer; *p; p++) + { + if (*p == '-' || *p == '+') { + if (mode != 0) + goto syntax_error; + mode = *p; + continue; + } + if (*p == ' ' || *p == '\t' || *p == '\r' || *p == '\n' || *p == '#') { + if (!id.empty()) { + if (mode == '-') + LibertyAst::blacklist.insert(id); + else + if (mode == '+') + LibertyAst::whitelist.insert(id); + else + goto syntax_error; + } + id.clear(); + if (*p == '#') + break; + continue; + } + id += *p; + continue; + + syntax_error: + fprintf(stderr, "Syntax error in rules file:\n%s", buffer); + exit(1); + } + } + } + } + + FILE *f = stdin; + if (argc == 3) { + f = fopen(argv[2], "r"); + if (f == NULL) { + fprintf(stderr, "Can't open liberty file `%s'.\n", argv[2]); + usage(); + } + } + + LibertyParer parser(f); + if (parser.ast) { + if (flag_verilogsim) + gen_verilogsim(parser.ast); + else + parser.ast->dump(stdout); + } + + if (argc == 3) + fclose(f); + + return 0; +} + +#endif + diff --git a/passes/dfflibmap/libparse.h b/passes/dfflibmap/libparse.h new file mode 100644 index 000000000..8c4a2f5ca --- /dev/null +++ b/passes/dfflibmap/libparse.h @@ -0,0 +1,56 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#ifndef LIBPARSE_H +#define LIBPARSE_H + +#include <stdio.h> +#include <string> +#include <vector> +#include <set> + +namespace PASS_DFFLIBMAP +{ + struct LibertyAst + { + std::string id, value; + std::vector<std::string> args; + std::vector<LibertyAst*> children; + ~LibertyAst(); + LibertyAst *find(std::string name); + void dump(FILE *f, std::string indent = "", std::string path = "", bool path_ok = false); + static std::set<std::string> blacklist; + static std::set<std::string> whitelist; + }; + + struct LibertyParer + { + FILE *f; + int line; + LibertyAst *ast; + LibertyParer(FILE *f) : f(f), line(1), ast(parse()) {} + ~LibertyParer() { if (ast) delete ast; } + int lexer(std::string &str); + LibertyAst *parse(); + void error(); + }; +} + +#endif + diff --git a/passes/fsm/Makefile.inc b/passes/fsm/Makefile.inc new file mode 100644 index 000000000..38623e49e --- /dev/null +++ b/passes/fsm/Makefile.inc @@ -0,0 +1,11 @@ + +OBJS += passes/fsm/fsm.o +OBJS += passes/fsm/fsm_detect.o +OBJS += passes/fsm/fsm_extract.o +OBJS += passes/fsm/fsm_opt.o +OBJS += passes/fsm/fsm_expand.o +OBJS += passes/fsm/fsm_recode.o +OBJS += passes/fsm/fsm_info.o +OBJS += passes/fsm/fsm_export.o +OBJS += passes/fsm/fsm_map.o + diff --git a/passes/fsm/fsm.cc b/passes/fsm/fsm.cc new file mode 100644 index 000000000..61322fbd3 --- /dev/null +++ b/passes/fsm/fsm.cc @@ -0,0 +1,91 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/register.h" +#include "kernel/log.h" +#include <stdlib.h> +#include <stdio.h> + +struct FsmPass : public Pass { + FsmPass() : Pass("fsm") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + bool flag_nomap = false; + bool flag_norecode = false; + bool flag_expand = false; + bool flag_export = false; + std::string fm_set_fsm_file_opt; + + log_header("Executing FSM pass (extract and optimize FSM).\n"); + log_push(); + + size_t argidx; + for (argidx = 1; argidx < args.size(); argidx++) { + std::string arg = args[argidx]; + if (arg == "-fm_set_fsm_file" && argidx+1 < args.size() && fm_set_fsm_file_opt.empty()) { + fm_set_fsm_file_opt = " -fm_set_fsm_file " + args[++argidx]; + continue; + } + if (arg == "-norecode") { + flag_norecode = true; + continue; + } + if (arg == "-nomap") { + flag_nomap = true; + continue; + } + if (arg == "-expand") { + flag_expand = true; + continue; + } + if (arg == "-export") { + flag_export = true; + continue; + } + break; + } + extra_args(args, argidx, design); + + Pass::call(design, "fsm_detect"); + Pass::call(design, "fsm_extract"); + + Pass::call(design, "fsm_opt"); + Pass::call(design, "opt_rmunused"); + Pass::call(design, "fsm_opt"); + + if (flag_expand) { + Pass::call(design, "fsm_expand"); + Pass::call(design, "opt_rmunused"); + Pass::call(design, "fsm_opt"); + } + + if (!flag_norecode) + Pass::call(design, "fsm_recode" + fm_set_fsm_file_opt); + Pass::call(design, "fsm_info"); + + if (!flag_nomap) + Pass::call(design, "fsm_map"); + + if (flag_export) + Pass::call(design, "fsm_export"); + + log_pop(); + } +} FsmPass; + diff --git a/passes/fsm/fsm_detect.cc b/passes/fsm/fsm_detect.cc new file mode 100644 index 000000000..067ed171f --- /dev/null +++ b/passes/fsm/fsm_detect.cc @@ -0,0 +1,160 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/log.h" +#include "kernel/register.h" +#include "kernel/sigtools.h" +#include "kernel/consteval.h" +#include "kernel/celltypes.h" +#include "fsmdata.h" + +static RTLIL::Module *module; +static SigMap assign_map; +typedef std::pair<RTLIL::Cell*,std::string> sig2driver_entry_t; +static SigSet<sig2driver_entry_t> sig2driver, sig2user; +static std::set<RTLIL::Cell*> muxtree_cells; +static SigPool sig_at_port; + +static bool check_state_mux_tree(RTLIL::SigSpec old_sig, RTLIL::SigSpec sig) +{ + if (sig_at_port.check_any(assign_map(sig))) + return false; + + if (sig.is_fully_const() || old_sig == sig) + return true; + + std::set<sig2driver_entry_t> cellport_list; + sig2driver.find(sig, cellport_list); + for (auto &cellport : cellport_list) { + if ((cellport.first->type != "$mux" && cellport.first->type != "$pmux" && cellport.first->type != "$safe_pmux") || cellport.second != "\\Y") + return false; + RTLIL::SigSpec sig_a = assign_map(cellport.first->connections["\\A"]); + RTLIL::SigSpec sig_b = assign_map(cellport.first->connections["\\B"]); + if (!check_state_mux_tree(old_sig, sig_a)) + return false; + for (int i = 0; i < sig_b.width; i += sig_a.width) + if (!check_state_mux_tree(old_sig, sig_b.extract(i, sig_a.width))) + return false; + muxtree_cells.insert(cellport.first); + } + + return true; +} + +static bool check_state_users(RTLIL::SigSpec sig) +{ + if (sig_at_port.check_any(assign_map(sig))) + return false; + + std::set<sig2driver_entry_t> cellport_list; + sig2user.find(sig, cellport_list); + for (auto &cellport : cellport_list) { + RTLIL::Cell *cell = cellport.first; + if (muxtree_cells.count(cell) > 0) + continue; + if (cellport.second != "\\A" && cellport.second != "\\B") + return false; + if (cell->connections.count("\\A") == 0 || cell->connections.count("\\B") == 0 || cell->connections.count("\\Y") == 0) + return false; + for (auto &port_it : cell->connections) + if (port_it.first != "\\A" && port_it.first != "\\B" && port_it.first != "\\Y") + return false; + if (assign_map(cell->connections["\\A"]) == sig && cell->connections["\\B"].is_fully_const()) + continue; + if (assign_map(cell->connections["\\B"]) == sig && cell->connections["\\A"].is_fully_const()) + continue; + return false; + } + + return true; +} + +static void detect_fsm(RTLIL::Wire *wire) +{ + if (wire->attributes.count("\\fsm_encoding") > 0 || wire->width <= 1) + return; + if (sig_at_port.check_any(assign_map(RTLIL::SigSpec(wire)))) + return; + + std::set<sig2driver_entry_t> cellport_list; + sig2driver.find(RTLIL::SigSpec(wire), cellport_list); + for (auto &cellport : cellport_list) { + if ((cellport.first->type != "$dff" && cellport.first->type != "$adff") || cellport.second != "\\Q") + continue; + muxtree_cells.clear(); + RTLIL::SigSpec sig_q = assign_map(cellport.first->connections["\\Q"]); + RTLIL::SigSpec sig_d = assign_map(cellport.first->connections["\\D"]); + if (sig_q == RTLIL::SigSpec(wire) && check_state_mux_tree(sig_q, sig_d) && check_state_users(sig_q)) { + log("Found FSM state register %s in module %s.\n", wire->name.c_str(), module->name.c_str()); + wire->attributes["\\fsm_encoding"] = RTLIL::Const("auto"); + return; + } + } +} + +struct FsmDetectPass : public Pass { + FsmDetectPass() : Pass("fsm_detect") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing FSM_DETECT pass (finding FSMs in design).\n"); + extra_args(args, 1, design); + + CellTypes ct; + ct.setup_internals(); + ct.setup_internals_mem(); + ct.setup_stdcells(); + ct.setup_stdcells_mem(); + + for (auto &mod_it : design->modules) + { + module = mod_it.second; + assign_map.set(module); + + sig2driver.clear(); + sig2user.clear(); + sig_at_port.clear(); + for (auto &cell_it : module->cells) + for (auto &conn_it : cell_it.second->connections) { + if (ct.cell_output(cell_it.second->type, conn_it.first)) { + RTLIL::SigSpec sig = conn_it.second; + assign_map.apply(sig); + sig2driver.insert(sig, sig2driver_entry_t(cell_it.second, conn_it.first)); + } + if (!ct.cell_known(cell_it.second->type) || ct.cell_input(cell_it.second->type, conn_it.first)) { + RTLIL::SigSpec sig = conn_it.second; + assign_map.apply(sig); + sig2user.insert(sig, sig2driver_entry_t(cell_it.second, conn_it.first)); + } + } + + for (auto &wire_it : module->wires) + if (wire_it.second->port_id != 0) + sig_at_port.add(assign_map(RTLIL::SigSpec(wire_it.second))); + + for (auto &wire_it : module->wires) + detect_fsm(wire_it.second); + } + + assign_map.clear(); + sig2driver.clear(); + sig2user.clear(); + muxtree_cells.clear(); + } +} FsmDetectPass; + diff --git a/passes/fsm/fsm_expand.cc b/passes/fsm/fsm_expand.cc new file mode 100644 index 000000000..0d5bc7695 --- /dev/null +++ b/passes/fsm/fsm_expand.cc @@ -0,0 +1,255 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/log.h" +#include "kernel/register.h" +#include "kernel/sigtools.h" +#include "kernel/consteval.h" +#include "kernel/celltypes.h" +#include "fsmdata.h" +#include <string.h> + +struct FsmExpand +{ + RTLIL::Module *module; + RTLIL::Cell *fsm_cell; + SigMap assign_map; + SigSet<RTLIL::Cell*> sig2driver, sig2user; + CellTypes ct; + + std::set<RTLIL::Cell*> merged_set; + std::set<RTLIL::Cell*> current_set; + std::set<RTLIL::Cell*> no_candidate_set; + + bool already_optimized; + int limit_transitions; + + bool is_cell_merge_candidate(RTLIL::Cell *cell) + { + RTLIL::SigSpec new_signals; + if (cell->connections.count("\\A") > 0) + new_signals.append(assign_map(cell->connections["\\A"])); + if (cell->connections.count("\\B") > 0) + new_signals.append(assign_map(cell->connections["\\B"])); + if (cell->connections.count("\\S") > 0) + new_signals.append(assign_map(cell->connections["\\S"])); + + new_signals.sort_and_unify(); + new_signals.remove_const(); + + if (new_signals.width > 4) + return false; + + new_signals.remove(assign_map(fsm_cell->connections["\\CTRL_IN"])); + new_signals.remove(assign_map(fsm_cell->connections["\\CTRL_OUT"])); + + if (cell->connections.count("\\Y") > 0) { + new_signals.append(assign_map(cell->connections["\\Y"])); + new_signals.sort_and_unify(); + new_signals.remove_const(); + new_signals.remove(assign_map(fsm_cell->connections["\\CTRL_IN"])); + new_signals.remove(assign_map(fsm_cell->connections["\\CTRL_OUT"])); + } + + if (new_signals.width > 2) + return false; + + return true; + } + + void create_current_set() + { + std::vector<RTLIL::Cell*> cell_list; + + for (auto c : sig2driver.find(assign_map(fsm_cell->connections["\\CTRL_IN"]))) + cell_list.push_back(c); + + for (auto c : sig2user.find(assign_map(fsm_cell->connections["\\CTRL_OUT"]))) + cell_list.push_back(c); + + current_set.clear(); + for (auto c : cell_list) + { + if (merged_set.count(c) > 0 || current_set.count(c) > 0 || no_candidate_set.count(c) > 0) + continue; + for (auto &p : c->connections) { + if (p.first != "\\A" && p.first != "\\B" && p.first != "\\S" && p.first != "\\Y") + goto next_cell; + } + if (!is_cell_merge_candidate(c)) { + no_candidate_set.insert(c); + continue; + } + current_set.insert(c); + next_cell:; + } + } + + void optimze_as_needed() + { + if (already_optimized) + return; + + int trans_num = fsm_cell->parameters["\\TRANS_NUM"].as_int(); + if (trans_num > limit_transitions) + { + log(" grown transition table to %d entries -> optimize.\n", trans_num); + FsmData::optimize_fsm(fsm_cell, module); + already_optimized = true; + + trans_num = fsm_cell->parameters["\\TRANS_NUM"].as_int(); + log(" transition table size after optimizaton: %d\n", trans_num); + limit_transitions = 16 * trans_num; + } + } + + void merge_cell_into_fsm(RTLIL::Cell *cell) + { + optimze_as_needed(); + + log(" merging %s cell %s.\n", cell->type.c_str(), cell->name.c_str()); + merged_set.insert(cell); + already_optimized = false; + + RTLIL::SigSpec input_sig, output_sig; + + for (auto &p : cell->connections) + if (ct.cell_output(cell->type, p.first)) + output_sig.append(assign_map(p.second)); + else + input_sig.append(assign_map(p.second)); + input_sig.sort_and_unify(); + input_sig.remove_const(); + + assert(input_sig.width <= 4); + std::vector<RTLIL::Const> truth_tab; + + for (int i = 0; i < (1 << input_sig.width); i++) { + RTLIL::Const in_val(i, input_sig.width); + RTLIL::SigSpec A, B, S; + if (cell->connections.count("\\A") > 0) + A = assign_map(cell->connections["\\A"]); + if (cell->connections.count("\\B") > 0) + B = assign_map(cell->connections["\\B"]); + if (cell->connections.count("\\S") > 0) + S = assign_map(cell->connections["\\S"]); + A.replace(input_sig, RTLIL::SigSpec(in_val)); + B.replace(input_sig, RTLIL::SigSpec(in_val)); + S.replace(input_sig, RTLIL::SigSpec(in_val)); + assert(A.is_fully_const()); + assert(B.is_fully_const()); + assert(S.is_fully_const()); + truth_tab.push_back(ct.eval(cell, A.as_const(), B.as_const(), S.as_const())); + } + + FsmData fsm_data; + fsm_data.copy_from_cell(fsm_cell); + + fsm_data.num_inputs += input_sig.width; + fsm_cell->connections["\\CTRL_IN"].append(input_sig); + + fsm_data.num_outputs += output_sig.width; + fsm_cell->connections["\\CTRL_OUT"].append(output_sig); + + std::vector<FsmData::transition_t> new_transition_table; + for (auto &tr : fsm_data.transition_table) { + for (int i = 0; i < (1 << input_sig.width); i++) { + FsmData::transition_t new_tr = tr; + RTLIL::Const in_val(i, input_sig.width); + RTLIL::Const out_val = truth_tab[i]; + RTLIL::SigSpec ctrl_in = new_tr.ctrl_in; + RTLIL::SigSpec ctrl_out = new_tr.ctrl_out; + ctrl_in.append(in_val); + ctrl_out.append(out_val); + new_tr.ctrl_in = ctrl_in.as_const(); + new_tr.ctrl_out = ctrl_out.as_const(); + new_transition_table.push_back(new_tr); + } + } + fsm_data.transition_table.swap(new_transition_table); + new_transition_table.clear(); + + fsm_data.copy_to_cell(fsm_cell); + } + + FsmExpand(RTLIL::Cell *cell, RTLIL::Module *mod) + { + module = mod; + fsm_cell = cell; + + assign_map.set(module); + ct.setup_internals(); + + for (auto &cell_it : module->cells) { + RTLIL::Cell *c = cell_it.second; + if (ct.cell_known(c->type)) + for (auto &p : c->connections) { + if (ct.cell_output(c->type, p.first)) + sig2driver.insert(assign_map(p.second), c); + else + sig2user.insert(assign_map(p.second), c); + } + } + } + + void execute() + { + log("\n"); + log("Expanding FSM `%s' from module `%s':\n", fsm_cell->name.c_str(), module->name.c_str()); + + already_optimized = false; + limit_transitions = 16 * fsm_cell->parameters["\\TRANS_NUM"].as_int(); + + for (create_current_set(); current_set.size() > 0; create_current_set()) { + for (auto c : current_set) + merge_cell_into_fsm(c); + } + + for (auto c : merged_set) { + module->cells.erase(c->name); + delete c; + } + + if (merged_set.size() > 0 && !already_optimized) + FsmData::optimize_fsm(fsm_cell, module); + + log(" merged %zd cells into FSM.\n", merged_set.size()); + } +}; + +struct FsmExpandPass : public Pass { + FsmExpandPass() : Pass("fsm_expand") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing FSM_EXPAND pass (re-assigning FSM state encoding).\n"); + extra_args(args, 1, design); + + for (auto &mod_it : design->modules) { + std::vector<RTLIL::Cell*> fsm_cells; + for (auto &cell_it : mod_it.second->cells) + if (cell_it.second->type == "$fsm") + fsm_cells.push_back(cell_it.second); + for (auto c : fsm_cells) { + FsmExpand fsm_expand(c, mod_it.second); + fsm_expand.execute(); + } + } + } +} FsmExpandPass; + diff --git a/passes/fsm/fsm_export.cc b/passes/fsm/fsm_export.cc new file mode 100644 index 000000000..0219f4ebd --- /dev/null +++ b/passes/fsm/fsm_export.cc @@ -0,0 +1,103 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * Copyright (C) 2012 Martin Schmölzer <martin@schmoelzer.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/log.h" +#include "kernel/register.h" +#include "kernel/sigtools.h" +#include "kernel/consteval.h" +#include "kernel/celltypes.h" +#include "fsmdata.h" +#include <string> +#include <iostream> +#include <fstream> + +/** + * Convert signal into a KISS-compatible textual representation. + */ +std::string kiss_convert_signal(const RTLIL::SigSpec &sig) { + if (!sig.is_fully_const()) { + throw 0; + } + + return sig.as_const().as_string(); +} + +/** + * Exports each Finite State Machine (FSM) in the design to a file in KISS2 format. + */ +struct FsmExportPass : public Pass { + FsmExportPass() : Pass("fsm_export") { + } + + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + FsmData fsm_data; + std::string kiss_name; + std::ofstream kiss_file; + size_t i; + FsmData::transition_t tr; + + log_header("Executing FSM_EXPORT pass (exporting FSMs in KISS2 file format).\n"); + extra_args(args, 1, design); + + for (auto &mod_it : design->modules) + for (auto &cell_it : mod_it.second->cells) + if (cell_it.second->type == "$fsm") { + kiss_name.assign(mod_it.first.c_str()); + kiss_name.append("-" + cell_it.second->name + ".kiss2"); + fsm_data.copy_from_cell(cell_it.second); + + log("\n"); + log("Exporting FSM `%s' from module `%s' to file `%s'.\n", + cell_it.second->name.c_str(), + mod_it.first.c_str(), + kiss_name.c_str()); + + kiss_file.open(kiss_name, std::ios::out | std::ios::trunc); + + if (!kiss_file.is_open()) { + log_error("Could not open file \"%s\" with write access.\n", kiss_name.c_str()); + return; + } + + kiss_file << ".start_kiss" << std::endl; + kiss_file << ".i " << std::dec << fsm_data.num_inputs << std::endl; + kiss_file << ".o " << std::dec << fsm_data.num_outputs << std::endl; + kiss_file << ".r s" << std::dec << fsm_data.reset_state << std::endl; + + for (i = 0; i < fsm_data.transition_table.size(); i++) { + tr = fsm_data.transition_table[i]; + + try { + kiss_file << kiss_convert_signal(tr.ctrl_in) << ' '; + kiss_file << 's' << tr.state_in << ' '; + kiss_file << 's' << tr.state_out << ' '; + kiss_file << kiss_convert_signal(tr.ctrl_out) << std::endl; + } + catch (int) { + log_error("exporting an FSM input or output signal failed.\n"); + } + } + + kiss_file << ".end_kiss" << std::endl << ".end" << std::endl; + kiss_file.close(); + } + } +} FsmExportPass; diff --git a/passes/fsm/fsm_extract.cc b/passes/fsm/fsm_extract.cc new file mode 100644 index 000000000..bdcb1d45a --- /dev/null +++ b/passes/fsm/fsm_extract.cc @@ -0,0 +1,359 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/log.h" +#include "kernel/register.h" +#include "kernel/sigtools.h" +#include "kernel/consteval.h" +#include "kernel/celltypes.h" +#include "fsmdata.h" + +static RTLIL::Module *module; +static SigMap assign_map; +typedef std::pair<RTLIL::Cell*,std::string> sig2driver_entry_t; +static SigSet<sig2driver_entry_t> sig2driver, sig2trigger; + +static bool find_states(RTLIL::SigSpec sig, const RTLIL::SigSpec &dff_out, RTLIL::SigSpec &ctrl, std::map<RTLIL::Const, int> &states, RTLIL::Const *reset_state = NULL) +{ + sig.extend(dff_out.width, false); + + if (sig == dff_out) + return true; + + assign_map.apply(sig); + if (sig.is_fully_const()) { + sig.optimize(); + assert(sig.chunks.size() == 1); + if (states.count(sig.chunks[0].data) == 0) { + log(" found state code: %s\n", log_signal(sig)); + states[sig.chunks[0].data] = -1; + } + return true; + } + + std::set<sig2driver_entry_t> cellport_list; + sig2driver.find(sig, cellport_list); + for (auto &cellport : cellport_list) { + if ((cellport.first->type != "$mux" && cellport.first->type != "$pmux" && cellport.first->type != "$safe_pmux") || cellport.second != "\\Y") { + log(" unexpected cell type %s (%s) found in state selection tree.\n", + cellport.first->type.c_str(), cellport.first->name.c_str()); + return false; + } + RTLIL::SigSpec sig_a = assign_map(cellport.first->connections["\\A"]); + RTLIL::SigSpec sig_b = assign_map(cellport.first->connections["\\B"]); + RTLIL::SigSpec sig_s = assign_map(cellport.first->connections["\\S"]); + if (reset_state && RTLIL::SigSpec(*reset_state).is_fully_undef()) + do { + if (sig_a.is_fully_def()) + *reset_state = sig_a.as_const(); + else if (sig_b.is_fully_def()) + *reset_state = sig_b.as_const(); + else + break; + log(" found reset state: %s (guessed from mux tree)\n", log_signal(*reset_state)); + } while (0); + if (ctrl.extract(sig_s).width == 0) { + log(" found ctrl input: %s\n", log_signal(sig_s)); + ctrl.append(sig_s); + } + if (!find_states(sig_a, dff_out, ctrl, states)) + return false; + for (int i = 0; i < sig_b.width/sig_a.width; i++) { + if (!find_states(sig_b.extract(i*sig_a.width, sig_a.width), dff_out, ctrl, states)) + return false; + } + } + + return true; +} + +static RTLIL::Const sig2const(ConstEval &ce, RTLIL::SigSpec sig, RTLIL::State noconst_state, RTLIL::SigSpec dont_care = RTLIL::SigSpec()) +{ + if (dont_care.width > 0) { + sig.expand(); + for (auto &chunk : sig.chunks) { + assert(chunk.width == 1); + if (dont_care.extract(chunk).width > 0) + chunk.wire = NULL, chunk.data = RTLIL::Const(noconst_state); + } + sig.optimize(); + } + + ce.assign_map.apply(sig); + ce.values_map.apply(sig); + + sig.expand(); + for (auto &chunk : sig.chunks) { + assert(chunk.width == 1); + if (chunk.wire != NULL) + chunk.wire = NULL, chunk.data = RTLIL::Const(noconst_state); + } + sig.optimize(); + + if (sig.width == 0) + return RTLIL::Const(); + assert(sig.chunks.size() == 1 && sig.chunks[0].wire == NULL); + return sig.chunks[0].data; +} + +static void find_transitions(ConstEval &ce, ConstEval &ce_nostop, FsmData &fsm_data, std::map<RTLIL::Const, int> &states, int state_in, RTLIL::SigSpec ctrl_in, RTLIL::SigSpec ctrl_out, RTLIL::SigSpec dff_in, RTLIL::SigSpec dont_care) +{ + RTLIL::SigSpec undef, constval; + + if (ce.eval(ctrl_out, undef) && ce.eval(dff_in, undef)) { + assert(ctrl_out.is_fully_const() && dff_in.is_fully_const()); + FsmData::transition_t tr; + tr.state_in = state_in; + tr.state_out = states[ce.values_map(ce.assign_map(dff_in)).as_const()]; + tr.ctrl_in = sig2const(ce, ctrl_in, RTLIL::State::Sa, dont_care); + tr.ctrl_out = sig2const(ce, ctrl_out, RTLIL::State::Sx); + RTLIL::Const log_state_in = RTLIL::Const(RTLIL::State::Sx, fsm_data.state_bits); + if (state_in >= 0) + log_state_in = fsm_data.state_table[tr.state_in]; + if (dff_in.is_fully_def()) { + fsm_data.transition_table.push_back(tr); + log(" transition: %10s %s -> %10s %s\n", + log_signal(log_state_in), log_signal(tr.ctrl_in), + log_signal(fsm_data.state_table[tr.state_out]), log_signal(tr.ctrl_out)); + } else { + log(" transition: %10s %s -> %10s %s <ignored undef transistion!>\n", + log_signal(log_state_in), log_signal(tr.ctrl_in), + log_signal(fsm_data.state_table[tr.state_out]), log_signal(tr.ctrl_out)); + } + return; + } + + assert(undef.width > 0); + assert(ce.stop_signals.check_all(undef)); + + undef = undef.extract(0, 1); + constval = undef; + + if (ce_nostop.eval(constval)) + { + ce.push(); + dont_care.append(undef); + ce.set(undef, constval.as_const()); + find_transitions(ce, ce_nostop, fsm_data, states, state_in, ctrl_in, ctrl_out, dff_in, dont_care); + ce.pop(); + } + else + { + ce.push(), ce_nostop.push(); + ce.set(undef, RTLIL::Const(0, 1)); + ce_nostop.set(undef, RTLIL::Const(0, 1)); + find_transitions(ce, ce_nostop, fsm_data, states, state_in, ctrl_in, ctrl_out, dff_in, dont_care); + ce.pop(), ce_nostop.pop(); + + ce.push(), ce_nostop.push(); + ce.set(undef, RTLIL::Const(1, 1)); + ce_nostop.set(undef, RTLIL::Const(1, 1)); + find_transitions(ce, ce_nostop, fsm_data, states, state_in, ctrl_in, ctrl_out, dff_in, dont_care); + ce.pop(), ce_nostop.pop(); + } +} + +static void extract_fsm(RTLIL::Wire *wire) +{ + log("Extracting FSM `%s' from module `%s'.\n", wire->name.c_str(), module->name.c_str()); + + // get input and output signals for state ff + + RTLIL::SigSpec dff_out = assign_map(RTLIL::SigSpec(wire)); + RTLIL::SigSpec dff_in(RTLIL::State::Sm, wire->width); + RTLIL::Const reset_state(RTLIL::State::Sx, wire->width); + + RTLIL::SigSpec clk = RTLIL::SigSpec(0, 1); + RTLIL::SigSpec arst = RTLIL::SigSpec(0, 1); + bool clk_polarity = true; + bool arst_polarity = true; + + std::set<sig2driver_entry_t> cellport_list; + sig2driver.find(dff_out, cellport_list); + for (auto &cellport : cellport_list) { + if ((cellport.first->type != "$dff" && cellport.first->type != "$adff") || cellport.second != "\\Q") + continue; + log(" found %s cell for state register: %s\n", cellport.first->type.c_str(), cellport.first->name.c_str()); + RTLIL::SigSpec sig_q = assign_map(cellport.first->connections["\\Q"]); + RTLIL::SigSpec sig_d = assign_map(cellport.first->connections["\\D"]); + clk = cellport.first->connections["\\CLK"]; + clk_polarity = cellport.first->parameters["\\CLK_POLARITY"].as_bool(); + if (cellport.first->type == "$adff") { + arst = cellport.first->connections["\\ARST"]; + arst_polarity = cellport.first->parameters["\\ARST_POLARITY"].as_bool(); + reset_state = cellport.first->parameters["\\ARST_VALUE"]; + } + sig_q.replace(dff_out, sig_d, &dff_in); + break; + } + + log(" root of input selection tree: %s\n", log_signal(dff_in)); + if (dff_in.has_marked_bits()) { + log(" fsm extraction failed: incomplete input selection tree root.\n"); + return; + } + + // find states and control inputs + + RTLIL::SigSpec ctrl_in; + std::map<RTLIL::Const, int> states; + if (!arst.is_fully_const()) { + log(" found reset state: %s (from async reset)\n", log_signal(reset_state)); + states[reset_state] = -1; + } + if (!find_states(dff_in, dff_out, ctrl_in, states, &reset_state)) { + log(" fsm extraction failed: state selection tree is not closed.\n"); + return; + } + + // find control outputs + // (add the state signals to the list of control outputs. if everything goes right, this signals + // become unused and can then be removed from the fsm control output) + + RTLIL::SigSpec ctrl_out = dff_in; + cellport_list.clear(); + sig2trigger.find(dff_out, cellport_list); + for (auto &cellport : cellport_list) { + RTLIL::SigSpec sig_a = assign_map(cellport.first->connections["\\A"]); + RTLIL::SigSpec sig_b = assign_map(cellport.first->connections["\\B"]); + RTLIL::SigSpec sig_y = assign_map(cellport.first->connections["\\Y"]); + if (cellport.second == "\\A" && !sig_b.is_fully_const()) + continue; + if (cellport.second == "\\B" && !sig_a.is_fully_const()) + continue; + log(" found ctrl output: %s\n", log_signal(sig_y)); + ctrl_out.append(sig_y); + } + ctrl_in.remove(ctrl_out); + + log(" ctrl inputs: %s\n", log_signal(ctrl_in)); + log(" ctrl outputs: %s\n", log_signal(ctrl_out)); + + // Initialize fsm data struct + + FsmData fsm_data; + fsm_data.num_inputs = ctrl_in.width; + fsm_data.num_outputs = ctrl_out.width; + fsm_data.state_bits = wire->width; + fsm_data.reset_state = -1; + for (auto &it : states) { + it.second = fsm_data.state_table.size(); + fsm_data.state_table.push_back(it.first); + } + if (!arst.is_fully_const() || RTLIL::SigSpec(reset_state).is_fully_def()) + fsm_data.reset_state = states[reset_state]; + + // Create transition table + + ConstEval ce(module), ce_nostop(module); + ce.stop(ctrl_in); + for (int state_idx = 0; state_idx < int(fsm_data.state_table.size()); state_idx++) { + ce.push(), ce_nostop.push(); + ce.set(dff_out, fsm_data.state_table[state_idx]); + ce_nostop.set(dff_out, fsm_data.state_table[state_idx]); + find_transitions(ce, ce_nostop, fsm_data, states, state_idx, ctrl_in, ctrl_out, dff_in, RTLIL::SigSpec()); + ce.pop(), ce_nostop.pop(); + } + + // create fsm cell + + RTLIL::Cell *fsm_cell = new RTLIL::Cell; + fsm_cell->name = stringf("$fsm$%s$%d", wire->name.c_str(), RTLIL::autoidx++); + fsm_cell->type = "$fsm"; + fsm_cell->connections["\\CLK"] = clk; + fsm_cell->connections["\\ARST"] = arst; + fsm_cell->parameters["\\CLK_POLARITY"] = RTLIL::Const(clk_polarity ? 1 : 0, 1); + fsm_cell->parameters["\\ARST_POLARITY"] = RTLIL::Const(arst_polarity ? 1 : 0, 1); + fsm_cell->connections["\\CTRL_IN"] = ctrl_in; + fsm_cell->connections["\\CTRL_OUT"] = ctrl_out; + fsm_cell->parameters["\\NAME"] = RTLIL::Const(wire->name); + fsm_data.copy_to_cell(fsm_cell); + module->cells[fsm_cell->name] = fsm_cell; + + // rename original state wire + + module->wires.erase(wire->name); + wire->attributes.erase("\\fsm_encoding"); + wire->name = stringf("$fsm$oldstate%s", wire->name.c_str()); + module->wires[wire->name] = wire; + + // unconnect control outputs from old drivers + + cellport_list.clear(); + sig2driver.find(ctrl_out, cellport_list); + for (auto &cellport : cellport_list) { + RTLIL::SigSpec port_sig = assign_map(cellport.first->connections[cellport.second]); + RTLIL::SigSpec unconn_sig = port_sig.extract(ctrl_out); + RTLIL::Wire *unconn_wire = new RTLIL::Wire; + unconn_wire->name = stringf("$fsm_unconnect$%s$%d", log_signal(unconn_sig), RTLIL::autoidx++); + unconn_wire->width = unconn_sig.width; + module->wires[unconn_wire->name] = unconn_wire; + port_sig.replace(unconn_sig, RTLIL::SigSpec(unconn_wire), &cellport.first->connections[cellport.second]); + } +} + +struct FsmExtractPass : public Pass { + FsmExtractPass() : Pass("fsm_extract") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing FSM_EXTRACT pass (extracting FSM from design).\n"); + extra_args(args, 1, design); + + CellTypes ct; + ct.setup_internals(); + ct.setup_internals_mem(); + ct.setup_stdcells(); + ct.setup_stdcells_mem(); + + for (auto &mod_it : design->modules) + { + module = mod_it.second; + assign_map.set(module); + + sig2driver.clear(); + sig2trigger.clear(); + for (auto &cell_it : module->cells) + for (auto &conn_it : cell_it.second->connections) { + if (ct.cell_output(cell_it.second->type, conn_it.first)) { + RTLIL::SigSpec sig = conn_it.second; + assign_map.apply(sig); + sig2driver.insert(sig, sig2driver_entry_t(cell_it.second, conn_it.first)); + } + if (ct.cell_input(cell_it.second->type, conn_it.first) && cell_it.second->connections.count("\\Y") > 0 && + cell_it.second->connections["\\Y"].width == 1 && (conn_it.first == "\\A" || conn_it.first == "\\B")) { + RTLIL::SigSpec sig = conn_it.second; + assign_map.apply(sig); + sig2trigger.insert(sig, sig2driver_entry_t(cell_it.second, conn_it.first)); + } + } + + std::vector<RTLIL::Wire*> wire_list; + for (auto &wire_it : module->wires) + if (wire_it.second->attributes.count("\\fsm_encoding") > 0 && wire_it.second->attributes["\\fsm_encoding"].str != "none") + wire_list.push_back(wire_it.second); + for (auto wire : wire_list) + extract_fsm(wire); + } + + assign_map.clear(); + sig2driver.clear(); + sig2trigger.clear(); + } +} FsmExtractPass; + diff --git a/passes/fsm/fsm_info.cc b/passes/fsm/fsm_info.cc new file mode 100644 index 000000000..83f065760 --- /dev/null +++ b/passes/fsm/fsm_info.cc @@ -0,0 +1,46 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/log.h" +#include "kernel/register.h" +#include "kernel/sigtools.h" +#include "kernel/consteval.h" +#include "kernel/celltypes.h" +#include "fsmdata.h" +#include <string.h> + +struct FsmInfoPass : public Pass { + FsmInfoPass() : Pass("fsm_info") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing FSM_INFO pass (dumping all available information on FSM cells).\n"); + extra_args(args, 1, design); + + for (auto &mod_it : design->modules) + for (auto &cell_it : mod_it.second->cells) + if (cell_it.second->type == "$fsm") { + log("\n"); + log("FSM `%s' from module `%s':\n", cell_it.second->name.c_str(), mod_it.first.c_str()); + FsmData fsm_data; + fsm_data.copy_from_cell(cell_it.second); + fsm_data.log_info(cell_it.second); + } + } +} FsmInfoPass; + diff --git a/passes/fsm/fsm_map.cc b/passes/fsm/fsm_map.cc new file mode 100644 index 000000000..4319dc044 --- /dev/null +++ b/passes/fsm/fsm_map.cc @@ -0,0 +1,356 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/log.h" +#include "kernel/register.h" +#include "kernel/sigtools.h" +#include "kernel/consteval.h" +#include "kernel/celltypes.h" +#include "fsmdata.h" +#include <string.h> + +static void implement_pattern_cache(RTLIL::Module *module, std::map<RTLIL::Const, std::set<int>> &pattern_cache, std::set<int> &fullstate_cache, int num_states, RTLIL::Wire *state_onehot, RTLIL::SigSpec &ctrl_in, RTLIL::SigSpec output) +{ + RTLIL::SigSpec cases_vector; + + for (int in_state : fullstate_cache) + cases_vector.append(RTLIL::SigSpec(state_onehot, 1, in_state)); + + for (auto &it : pattern_cache) + { + RTLIL::Const pattern = it.first; + RTLIL::SigSpec eq_sig_a, eq_sig_b, or_sig; + + for (size_t j = 0; j < pattern.bits.size(); j++) + if (pattern.bits[j] == RTLIL::State::S0 || pattern.bits[j] == RTLIL::State::S1) { + eq_sig_a.append(ctrl_in.extract(j, 1)); + eq_sig_b.append(RTLIL::SigSpec(pattern.bits[j])); + } + eq_sig_a.optimize(); + eq_sig_b.optimize(); + + for (int in_state : it.second) + if (fullstate_cache.count(in_state) == 0) + or_sig.append(RTLIL::SigSpec(state_onehot, 1, in_state)); + or_sig.optimize(); + + if (or_sig.width == 0) + continue; + + RTLIL::SigSpec and_sig; + + if (eq_sig_a.width > 0) + { + RTLIL::Wire *eq_wire = new RTLIL::Wire; + eq_wire->name = NEW_ID; + module->add(eq_wire); + + RTLIL::Cell *eq_cell = new RTLIL::Cell; + eq_cell->name = NEW_ID; + eq_cell->type = "$eq"; + eq_cell->connections["\\A"] = eq_sig_a; + eq_cell->connections["\\B"] = eq_sig_b; + eq_cell->connections["\\Y"] = RTLIL::SigSpec(eq_wire); + eq_cell->parameters["\\A_SIGNED"] = RTLIL::Const(false); + eq_cell->parameters["\\B_SIGNED"] = RTLIL::Const(false); + eq_cell->parameters["\\A_WIDTH"] = RTLIL::Const(eq_sig_a.width); + eq_cell->parameters["\\B_WIDTH"] = RTLIL::Const(eq_sig_b.width); + eq_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1); + module->add(eq_cell); + + and_sig.append(RTLIL::SigSpec(eq_wire)); + } + + if (or_sig.width == 1) + { + and_sig.append(or_sig); + } + else if (or_sig.width < num_states && int(it.second.size()) < num_states) + { + RTLIL::Wire *or_wire = new RTLIL::Wire; + or_wire->name = NEW_ID; + module->add(or_wire); + + RTLIL::Cell *or_cell = new RTLIL::Cell; + or_cell->name = NEW_ID; + or_cell->type = "$reduce_or"; + or_cell->connections["\\A"] = or_sig; + or_cell->connections["\\Y"] = RTLIL::SigSpec(or_wire); + or_cell->parameters["\\A_SIGNED"] = RTLIL::Const(false); + or_cell->parameters["\\A_WIDTH"] = RTLIL::Const(or_sig.width); + or_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1); + module->add(or_cell); + + and_sig.append(RTLIL::SigSpec(or_wire)); + } + + switch (and_sig.width) + { + case 2: + { + RTLIL::Wire *and_wire = new RTLIL::Wire; + and_wire->name = NEW_ID; + module->add(and_wire); + + RTLIL::Cell *and_cell = new RTLIL::Cell; + and_cell->name = NEW_ID; + and_cell->type = "$and"; + and_cell->connections["\\A"] = and_sig.extract(0, 1); + and_cell->connections["\\B"] = and_sig.extract(1, 1); + and_cell->connections["\\Y"] = RTLIL::SigSpec(and_wire); + and_cell->parameters["\\A_SIGNED"] = RTLIL::Const(false); + and_cell->parameters["\\B_SIGNED"] = RTLIL::Const(false); + and_cell->parameters["\\A_WIDTH"] = RTLIL::Const(1); + and_cell->parameters["\\B_WIDTH"] = RTLIL::Const(1); + and_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1); + module->add(and_cell); + + cases_vector.append(RTLIL::SigSpec(and_wire)); + break; + } + case 1: + cases_vector.append(and_sig); + break; + case 0: + cases_vector.append(RTLIL::SigSpec(1, 1)); + break; + default: + assert(!"This should never happen!"); + } + } + + if (cases_vector.width > 1) { + RTLIL::Cell *or_cell = new RTLIL::Cell; + or_cell->name = NEW_ID; + or_cell->type = "$reduce_or"; + or_cell->connections["\\A"] = cases_vector; + or_cell->connections["\\Y"] = output; + or_cell->parameters["\\A_SIGNED"] = RTLIL::Const(false); + or_cell->parameters["\\A_WIDTH"] = RTLIL::Const(cases_vector.width); + or_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1); + module->add(or_cell); + } else if (cases_vector.width == 1) { + module->connections.push_back(RTLIL::SigSig(output, cases_vector)); + } else { + module->connections.push_back(RTLIL::SigSig(output, RTLIL::SigSpec(0, 1))); + } +} + +static void map_fsm(RTLIL::Cell *fsm_cell, RTLIL::Module *module) +{ + log("Mapping FSM `%s' from module `%s'.\n", fsm_cell->name.c_str(), module->name.c_str()); + + FsmData fsm_data; + fsm_data.copy_from_cell(fsm_cell); + + RTLIL::SigSpec ctrl_in = fsm_cell->connections["\\CTRL_IN"]; + RTLIL::SigSpec ctrl_out = fsm_cell->connections["\\CTRL_OUT"]; + + // create state register + + RTLIL::Wire *state_wire = new RTLIL::Wire; + state_wire->name = fsm_cell->parameters["\\NAME"].str; + while (module->count_id(state_wire->name) > 0) + state_wire->name += "_"; + state_wire->width = fsm_data.state_bits; + module->add(state_wire); + + RTLIL::Wire *next_state_wire = new RTLIL::Wire; + next_state_wire->name = NEW_ID; + next_state_wire->width = fsm_data.state_bits; + module->add(next_state_wire); + + RTLIL::Cell *state_dff = new RTLIL::Cell; + state_dff->name = NEW_ID; + if (fsm_cell->connections["\\ARST"].is_fully_const()) { + state_dff->type = "$dff"; + } else { + state_dff->type = "$adff"; + state_dff->parameters["\\ARST_POLARITY"] = fsm_cell->parameters["\\ARST_POLARITY"]; + state_dff->parameters["\\ARST_VALUE"] = fsm_data.state_table[fsm_data.reset_state]; + state_dff->connections["\\ARST"] = fsm_cell->connections["\\ARST"]; + } + state_dff->parameters["\\WIDTH"] = RTLIL::Const(fsm_data.state_bits); + state_dff->parameters["\\CLK_POLARITY"] = fsm_cell->parameters["\\CLK_POLARITY"]; + state_dff->connections["\\CLK"] = fsm_cell->connections["\\CLK"]; + state_dff->connections["\\D"] = RTLIL::SigSpec(next_state_wire); + state_dff->connections["\\Q"] = RTLIL::SigSpec(state_wire); + module->add(state_dff); + + // decode state register + + bool encoding_is_onehot = true; + + RTLIL::Wire *state_onehot = new RTLIL::Wire; + state_onehot->name = NEW_ID; + state_onehot->width = fsm_data.state_table.size(); + module->add(state_onehot); + + for (size_t i = 0; i < fsm_data.state_table.size(); i++) + { + RTLIL::Const state = fsm_data.state_table[i]; + RTLIL::SigSpec sig_a, sig_b; + + for (size_t j = 0; j < state.bits.size(); j++) + if (state.bits[j] == RTLIL::State::S0 || state.bits[j] == RTLIL::State::S1) { + sig_a.append(RTLIL::SigSpec(state_wire, 1, j)); + sig_b.append(RTLIL::SigSpec(state.bits[j])); + } + sig_a.optimize(); + sig_b.optimize(); + + if (sig_b == RTLIL::SigSpec(RTLIL::State::S1)) + { + module->connections.push_back(RTLIL::SigSig(RTLIL::SigSpec(state_onehot, 1, i), sig_a)); + } + else + { + if (sig_b.as_bool() || sig_b.width != fsm_data.state_bits) + encoding_is_onehot = false; + + RTLIL::Cell *eq_cell = new RTLIL::Cell; + eq_cell->name = NEW_ID; + eq_cell->type = "$eq"; + eq_cell->connections["\\A"] = sig_a; + eq_cell->connections["\\B"] = sig_b; + eq_cell->connections["\\Y"] = RTLIL::SigSpec(state_onehot, 1, i); + eq_cell->parameters["\\A_SIGNED"] = RTLIL::Const(false); + eq_cell->parameters["\\B_SIGNED"] = RTLIL::Const(false); + eq_cell->parameters["\\A_WIDTH"] = RTLIL::Const(sig_a.width); + eq_cell->parameters["\\B_WIDTH"] = RTLIL::Const(sig_b.width); + eq_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1); + module->add(eq_cell); + } + } + + // generate next_state signal + + RTLIL::Wire *next_state_onehot = new RTLIL::Wire; + next_state_onehot->name = NEW_ID; + next_state_onehot->width = fsm_data.state_table.size(); + module->add(next_state_onehot); + + for (size_t i = 0; i < fsm_data.state_table.size(); i++) + { + std::map<RTLIL::Const, std::set<int>> pattern_cache; + std::set<int> fullstate_cache; + + for (size_t j = 0; j < fsm_data.state_table.size(); j++) + fullstate_cache.insert(j); + + for (auto &tr : fsm_data.transition_table) { + if (tr.state_out == int(i)) + pattern_cache[tr.ctrl_in].insert(tr.state_in); + else + fullstate_cache.erase(tr.state_in); + } + + implement_pattern_cache(module, pattern_cache, fullstate_cache, fsm_data.state_table.size(), state_onehot, ctrl_in, RTLIL::SigSpec(next_state_onehot, 1, i)); + } + + if (encoding_is_onehot) + { + for (size_t i = 0; i < fsm_data.state_table.size(); i++) { + RTLIL::Const state = fsm_data.state_table[i]; + int bit_idx = -1; + for (size_t j = 0; j < state.bits.size(); j++) + if (state.bits[j] == RTLIL::State::S1) + bit_idx = j; + if (bit_idx >= 0) + module->connections.push_back(RTLIL::SigSig(RTLIL::SigSpec(next_state_wire, 1, bit_idx), RTLIL::SigSpec(next_state_onehot, 1, i))); + } + } + else + { + RTLIL::SigSpec sig_a, sig_b, sig_s; + int reset_state = fsm_data.reset_state; + if (reset_state < 0) + reset_state = 0; + + for (size_t i = 0; i < fsm_data.state_table.size(); i++) { + RTLIL::Const state = fsm_data.state_table[i]; + if (int(i) == fsm_data.reset_state) { + sig_a = RTLIL::SigSpec(state); + } else { + sig_b.append(RTLIL::SigSpec(state)); + sig_s.append(RTLIL::SigSpec(next_state_onehot, 1, i)); + } + } + + RTLIL::Cell *mux_cell = new RTLIL::Cell; + mux_cell->name = NEW_ID; + mux_cell->type = "$safe_pmux"; + mux_cell->connections["\\A"] = sig_a; + mux_cell->connections["\\B"] = sig_b; + mux_cell->connections["\\S"] = sig_s; + mux_cell->connections["\\Y"] = RTLIL::SigSpec(next_state_wire); + mux_cell->parameters["\\WIDTH"] = RTLIL::Const(sig_a.width); + mux_cell->parameters["\\S_WIDTH"] = RTLIL::Const(sig_s.width); + module->add(mux_cell); + } + + // Generate ctrl_out signal + + RTLIL::Wire *ctrl_out_wire = new RTLIL::Wire; + ctrl_out_wire->name = NEW_ID; + ctrl_out_wire->width = fsm_data.num_outputs; + module->add(ctrl_out_wire); + + for (int i = 0; i < fsm_data.num_outputs; i++) + { + std::map<RTLIL::Const, std::set<int>> pattern_cache; + std::set<int> fullstate_cache; + + for (size_t j = 0; j < fsm_data.state_table.size(); j++) + fullstate_cache.insert(j); + + for (auto &tr : fsm_data.transition_table) { + if (tr.ctrl_out.bits[i] == RTLIL::State::S1) + pattern_cache[tr.ctrl_in].insert(tr.state_in); + else + fullstate_cache.erase(tr.state_in); + } + + implement_pattern_cache(module, pattern_cache, fullstate_cache, fsm_data.state_table.size(), state_onehot, ctrl_in, ctrl_out.extract(i, 1)); + } + + // Remove FSM cell + + module->cells.erase(fsm_cell->name); + delete fsm_cell; +} + +struct FsmMapPass : public Pass { + FsmMapPass() : Pass("fsm_map") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing FSM_MAP pass (simple optimizations of FSMs).\n"); + extra_args(args, 1, design); + + for (auto &mod_it : design->modules) { + std::vector<RTLIL::Cell*> fsm_cells; + for (auto &cell_it : mod_it.second->cells) + if (cell_it.second->type == "$fsm") + fsm_cells.push_back(cell_it.second); + for (auto cell : fsm_cells) + map_fsm(cell, mod_it.second); + } + } +} FsmMapPass; + diff --git a/passes/fsm/fsm_opt.cc b/passes/fsm/fsm_opt.cc new file mode 100644 index 000000000..8ba9679fd --- /dev/null +++ b/passes/fsm/fsm_opt.cc @@ -0,0 +1,285 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/log.h" +#include "kernel/register.h" +#include "kernel/sigtools.h" +#include "kernel/consteval.h" +#include "kernel/celltypes.h" +#include "fsmdata.h" +#include <string.h> + +struct FsmOpt +{ + FsmData fsm_data; + RTLIL::Cell *cell; + RTLIL::Module *module; + + bool signal_is_unused(RTLIL::SigSpec sig) + { + assert(sig.width == 1); + sig.optimize(); + + RTLIL::Wire *wire = sig.chunks[0].wire; + int bit = sig.chunks[0].offset; + + if (!wire || wire->attributes.count("\\unused_bits") == 0) + return false; + + char *str = strdup(wire->attributes["\\unused_bits"].str.c_str()); + for (char *tok = strtok(str, " "); tok != NULL; tok = strtok(NULL, " ")) { + if (tok[0] && bit == atoi(tok)) + return true; + } + free(str); + + return false; + } + + void opt_const_and_unused_inputs() + { + RTLIL::SigSpec ctrl_in = cell->connections["\\CTRL_IN"]; + std::vector<bool> ctrl_in_used(ctrl_in.width); + + std::vector<FsmData::transition_t> new_transition_table; + for (auto &tr : fsm_data.transition_table) { + for (int i = 0; i < ctrl_in.width; i++) { + RTLIL::SigSpec ctrl_bit = ctrl_in.extract(i, 1); + if (ctrl_bit.is_fully_const()) { + if (tr.ctrl_in.bits[i] <= RTLIL::State::S1 && RTLIL::SigSpec(tr.ctrl_in.bits[i]) != ctrl_bit) + goto delete_this_transition; + continue; + } + if (tr.ctrl_in.bits[i] <= RTLIL::State::S1) + ctrl_in_used[i] = true; + } + new_transition_table.push_back(tr); + delete_this_transition:; + } + + for (int i = int(ctrl_in_used.size())-1; i >= 0; i--) { + if (!ctrl_in_used[i]) { + log(" Removing unused input signal %s.\n", log_signal(cell->connections["\\CTRL_IN"].extract(i, 1))); + for (auto &tr : new_transition_table) { + RTLIL::SigSpec tmp(tr.ctrl_in); + tmp.remove(i, 1); + tr.ctrl_in = tmp.as_const(); + } + cell->connections["\\CTRL_IN"].remove(i, 1); + fsm_data.num_inputs--; + } + } + + fsm_data.transition_table.swap(new_transition_table); + new_transition_table.clear(); + } + + void opt_unused_outputs() + { + for (int i = 0; i < fsm_data.num_outputs; i++) { + RTLIL::SigSpec sig = cell->connections["\\CTRL_OUT"].extract(i, 1); + if (signal_is_unused(sig)) { + log(" Removing unused output signal %s.\n", log_signal(sig)); + cell->connections["\\CTRL_OUT"].remove(i, 1); + for (auto &tr : fsm_data.transition_table) { + RTLIL::SigSpec tmp(tr.ctrl_out); + tmp.remove(i, 1); + tr.ctrl_out = tmp.as_const(); + } + fsm_data.num_outputs--; + i--; + } + } + } + + void opt_alias_inputs() + { + RTLIL::SigSpec &ctrl_in = cell->connections["\\CTRL_IN"]; + + for (int i = 0; i < ctrl_in.width; i++) + for (int j = i+1; j < ctrl_in.width; j++) + if (ctrl_in.extract(i, 1) == ctrl_in.extract(j, 1)) + { + log(" Optimize handling of signal %s that is connected to inputs %d and %d.\n", log_signal(ctrl_in.extract(i, 1)), i, j); + std::vector<FsmData::transition_t> new_transition_table; + + for (auto tr : fsm_data.transition_table) + { + RTLIL::State &si = tr.ctrl_in.bits[i]; + RTLIL::State &sj = tr.ctrl_in.bits[j]; + + if (si > RTLIL::State::S1) + si = sj; + else if (sj > RTLIL::State::S1) + sj = si; + + if (si == sj) { + RTLIL::SigSpec tmp(tr.ctrl_in); + tmp.remove(j, 1); + tr.ctrl_in = tmp.as_const(); + new_transition_table.push_back(tr); + } + } + + ctrl_in.remove(j--, 1); + fsm_data.num_inputs--; + + fsm_data.transition_table.swap(new_transition_table); + new_transition_table.clear(); + } + } + + void opt_feedback_inputs() + { + RTLIL::SigSpec &ctrl_in = cell->connections["\\CTRL_IN"]; + RTLIL::SigSpec &ctrl_out = cell->connections["\\CTRL_OUT"]; + + for (int j = 0; j < ctrl_out.width; j++) + for (int i = 0; i < ctrl_in.width; i++) + if (ctrl_in.extract(i, 1) == ctrl_out.extract(j, 1)) + { + log(" Optimize handling of signal %s that is connected to input %d and output %d.\n", log_signal(ctrl_in.extract(i, 1)), i, j); + std::vector<FsmData::transition_t> new_transition_table; + + for (auto tr : fsm_data.transition_table) + { + RTLIL::State &si = tr.ctrl_in.bits[i]; + RTLIL::State &sj = tr.ctrl_out.bits[j]; + + if (si > RTLIL::State::S1 || si == sj) { + RTLIL::SigSpec tmp(tr.ctrl_in); + tmp.remove(i, 1); + tr.ctrl_in = tmp.as_const(); + new_transition_table.push_back(tr); + } + } + + ctrl_in.remove(i--, 1); + fsm_data.num_inputs--; + + fsm_data.transition_table.swap(new_transition_table); + new_transition_table.clear(); + } + } + + void opt_find_dont_care_worker(std::set<RTLIL::Const> &set, int bit, FsmData::transition_t &tr, bool &did_something) + { + std::set<RTLIL::Const> new_set; + + for (auto &pattern : set) + { + if (pattern.bits[bit] > RTLIL::State::S1) { + new_set.insert(pattern); + continue; + } + + RTLIL::Const other_pattern = pattern; + + if (pattern.bits[bit] == RTLIL::State::S1) + other_pattern.bits[bit] = RTLIL::State::S0; + else + other_pattern.bits[bit] = RTLIL::State::S1; + + if (set.count(other_pattern) > 0) { + log(" Merging pattern %s and %s from group (%d %d %s).\n", log_signal(pattern), log_signal(other_pattern), + tr.state_in, tr.state_out, log_signal(tr.ctrl_out)); + other_pattern.bits[bit] = RTLIL::State::Sa; + new_set.insert(other_pattern); + did_something = true; + continue; + } + + new_set.insert(pattern); + } + + set.swap(new_set); + } + + void opt_find_dont_care() + { + typedef std::pair<std::pair<int, int>, RTLIL::Const> group_t; + std::map<group_t, std::set<RTLIL::Const>> transitions_by_group; + + for (auto &tr : fsm_data.transition_table) { + group_t group(std::pair<int, int>(tr.state_in, tr.state_out), tr.ctrl_out); + transitions_by_group[group].insert(tr.ctrl_in); + } + + fsm_data.transition_table.clear(); + for (auto &it : transitions_by_group) + { + FsmData::transition_t tr; + tr.state_in = it.first.first.first; + tr.state_out = it.first.first.second; + tr.ctrl_out = it.first.second; + + bool did_something = true; + while (did_something) { + did_something = false; + for (int i = 0; i < fsm_data.num_inputs; i++) + opt_find_dont_care_worker(it.second, i, tr, did_something); + } + + for (auto &ci : it.second) { + tr.ctrl_in = ci; + fsm_data.transition_table.push_back(tr); + } + } + } + + FsmOpt(RTLIL::Cell *cell, RTLIL::Module *module) + { + log("Optimizing FSM `%s' from module `%s'.\n", cell->name.c_str(), module->name.c_str()); + + fsm_data.copy_from_cell(cell); + this->cell = cell; + this->module = module; + + opt_unused_outputs(); + + opt_alias_inputs(); + opt_feedback_inputs(); + opt_find_dont_care(); + + opt_const_and_unused_inputs(); + + fsm_data.copy_to_cell(cell); + } +}; + +void FsmData::optimize_fsm(RTLIL::Cell *cell, RTLIL::Module *module) +{ + FsmOpt fsmopt(cell, module); +} + +struct FsmOptPass : public Pass { + FsmOptPass() : Pass("fsm_opt") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing FSM_OPT pass (simple optimizations of FSMs).\n"); + extra_args(args, 1, design); + + for (auto &mod_it : design->modules) + for (auto &cell_it : mod_it.second->cells) { + if (cell_it.second->type == "$fsm") + FsmData::optimize_fsm(cell_it.second, mod_it.second); + } + } +} FsmOptPass; + diff --git a/passes/fsm/fsm_recode.cc b/passes/fsm/fsm_recode.cc new file mode 100644 index 000000000..5e258f269 --- /dev/null +++ b/passes/fsm/fsm_recode.cc @@ -0,0 +1,114 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/log.h" +#include "kernel/register.h" +#include "kernel/sigtools.h" +#include "kernel/consteval.h" +#include "kernel/celltypes.h" +#include "fsmdata.h" +#include <string.h> + +static void fm_set_fsm_print(RTLIL::Cell *cell, RTLIL::Module *module, FsmData &fsm_data, const char *prefix, FILE *f) +{ + fprintf(f, "set_fsm_state_vector {"); + for (int i = fsm_data.state_bits-1; i >= 0; i--) + fprintf(f, " %s_reg[%d]", cell->parameters["\\NAME"].str[0] == '\\' ? + cell->parameters["\\NAME"].str.substr(1).c_str() : cell->parameters["\\NAME"].str.c_str(), i); + fprintf(f, " } -name {%s_%s} {%s:/WORK/%s}\n", + prefix, RTLIL::unescape_id(cell->parameters["\\NAME"].str).c_str(), + prefix, RTLIL::unescape_id(module->name).c_str()); + + fprintf(f, "set_fsm_encoding {"); + for (size_t i = 0; i < fsm_data.state_table.size(); i++) { + fprintf(f, " s%zd=2#", i); + for (int j = int(fsm_data.state_table[i].bits.size())-1; j >= 0; j--) + fprintf(f, "%c", fsm_data.state_table[i].bits[j] == RTLIL::State::S1 ? '1' : '0'); + } + fprintf(f, " } -name {%s_%s} {%s:/WORK/%s}\n", + prefix, RTLIL::unescape_id(cell->parameters["\\NAME"].str).c_str(), + prefix, RTLIL::unescape_id(module->name).c_str()); +} + +static void fsm_recode(RTLIL::Cell *cell, RTLIL::Module *module, FILE *fm_set_fsm_file) +{ + FsmData fsm_data; + fsm_data.copy_from_cell(cell); + + log("Recoding FSM `%s' from module `%s':\n", cell->name.c_str(), module->name.c_str()); + + if (fm_set_fsm_file != NULL) + fm_set_fsm_print(cell, module, fsm_data, "r", fm_set_fsm_file); + + fsm_data.state_bits = fsm_data.state_table.size(); + if (fsm_data.reset_state >= 0) + fsm_data.state_bits--; + + int bit_pos = 0; + for (size_t i = 0; i < fsm_data.state_table.size(); i++) + { + RTLIL::Const new_code; + if (int(i) == fsm_data.reset_state) + new_code = RTLIL::Const(RTLIL::State::S0, fsm_data.state_bits); + else { + RTLIL::Const state_code(RTLIL::State::Sa, fsm_data.state_bits); + state_code.bits[bit_pos++] = RTLIL::State::S1; + new_code = state_code; + } + + log(" %s -> %s\n", fsm_data.state_table[i].as_string().c_str(), new_code.as_string().c_str()); + fsm_data.state_table[i] = new_code; + } + + if (fm_set_fsm_file != NULL) + fm_set_fsm_print(cell, module, fsm_data, "i", fm_set_fsm_file); + + fsm_data.copy_to_cell(cell); +} + +struct FsmRecodePass : public Pass { + FsmRecodePass() : Pass("fsm_recode") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + FILE *fm_set_fsm_file = NULL; + + log_header("Executing FSM_RECODE pass (re-assigning FSM state encoding).\n"); + size_t argidx; + for (argidx = 1; argidx < args.size(); argidx++) { + std::string arg = args[argidx]; + if (arg == "-fm_set_fsm_file" && argidx+1 < args.size() && fm_set_fsm_file == NULL) { + fm_set_fsm_file = fopen(args[++argidx].c_str(), "w"); + if (fm_set_fsm_file == NULL) + log_error("Can't open fm_set_fsm_file `%s' for writing: %s\n", args[argidx].c_str(), strerror(errno)); + continue; + } + break; + } + extra_args(args, argidx, design); + + for (auto &mod_it : design->modules) + for (auto &cell_it : mod_it.second->cells) + if (cell_it.second->type == "$fsm") + fsm_recode(cell_it.second, mod_it.second, fm_set_fsm_file); + + if (fm_set_fsm_file != NULL) + fclose(fm_set_fsm_file); + } +} FsmRecodePass; + diff --git a/passes/fsm/fsmdata.h b/passes/fsm/fsmdata.h new file mode 100644 index 000000000..f43b25fe9 --- /dev/null +++ b/passes/fsm/fsmdata.h @@ -0,0 +1,177 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#ifndef FSMDATA_H +#define FSMDATA_H + +#include "kernel/rtlil.h" +#include "kernel/log.h" + +struct FsmData +{ + int num_inputs, num_outputs, state_bits, reset_state; + struct transition_t { int state_in, state_out; RTLIL::Const ctrl_in, ctrl_out; }; + std::vector<transition_t> transition_table; + std::vector<RTLIL::Const> state_table; + + void copy_to_cell(RTLIL::Cell *cell) + { + cell->parameters["\\CTRL_IN_WIDTH"] = RTLIL::Const(num_inputs); + cell->parameters["\\CTRL_OUT_WIDTH"] = RTLIL::Const(num_outputs); + + int state_num_log2 = 0; + for (int i = state_table.size(); i > 0; i = i >> 1) + state_num_log2++; + state_num_log2 = std::max(state_num_log2, 1); + + cell->parameters["\\STATE_BITS"] = RTLIL::Const(state_bits); + cell->parameters["\\STATE_NUM"] = RTLIL::Const(state_table.size()); + cell->parameters["\\STATE_NUM_LOG2"] = RTLIL::Const(state_num_log2); + cell->parameters["\\STATE_RST"] = RTLIL::Const(reset_state); + cell->parameters["\\STATE_TABLE"] = RTLIL::Const(); + + for (int i = 0; i < int(state_table.size()); i++) { + std::vector<RTLIL::State> &bits_table = cell->parameters["\\STATE_TABLE"].bits; + std::vector<RTLIL::State> &bits_state = state_table[i].bits; + bits_table.insert(bits_table.end(), bits_state.begin(), bits_state.end()); + } + + cell->parameters["\\TRANS_NUM"] = RTLIL::Const(transition_table.size()); + cell->parameters["\\TRANS_TABLE"] = RTLIL::Const(); + for (int i = 0; i < int(transition_table.size()); i++) + { + std::vector<RTLIL::State> &bits_table = cell->parameters["\\TRANS_TABLE"].bits; + transition_t &tr = transition_table[i]; + + RTLIL::Const const_state_in = RTLIL::Const(tr.state_in, state_num_log2); + RTLIL::Const const_state_out = RTLIL::Const(tr.state_out, state_num_log2); + std::vector<RTLIL::State> &bits_state_in = const_state_in.bits; + std::vector<RTLIL::State> &bits_state_out = const_state_out.bits; + + std::vector<RTLIL::State> &bits_ctrl_in = tr.ctrl_in.bits; + std::vector<RTLIL::State> &bits_ctrl_out = tr.ctrl_out.bits; + + // append lsb first + bits_table.insert(bits_table.end(), bits_ctrl_out.begin(), bits_ctrl_out.end()); + bits_table.insert(bits_table.end(), bits_state_out.begin(), bits_state_out.end()); + bits_table.insert(bits_table.end(), bits_ctrl_in.begin(), bits_ctrl_in.end()); + bits_table.insert(bits_table.end(), bits_state_in.begin(), bits_state_in.end()); + } + } + + void copy_from_cell(RTLIL::Cell *cell) + { + num_inputs = cell->parameters["\\CTRL_IN_WIDTH"].as_int(); + num_outputs = cell->parameters["\\CTRL_OUT_WIDTH"].as_int(); + + state_bits = cell->parameters["\\STATE_BITS"].as_int(); + reset_state = cell->parameters["\\STATE_RST"].as_int(); + + int state_num = cell->parameters["\\STATE_NUM"].as_int(); + int state_num_log2 = cell->parameters["\\STATE_NUM_LOG2"].as_int(); + int trans_num = cell->parameters["\\TRANS_NUM"].as_int(); + + if (reset_state < 0 || reset_state >= state_num) + reset_state = -1; + + RTLIL::Const state_table = cell->parameters["\\STATE_TABLE"]; + RTLIL::Const trans_table = cell->parameters["\\TRANS_TABLE"]; + + for (int i = 0; i < state_num; i++) { + RTLIL::Const state_code; + int off_begin = i*state_bits, off_end = off_begin + state_bits; + state_code.bits.insert(state_code.bits.begin(), state_table.bits.begin()+off_begin, state_table.bits.begin()+off_end); + this->state_table.push_back(state_code); + } + + for (int i = 0; i < trans_num; i++) + { + auto off_ctrl_out = trans_table.bits.begin() + i*(num_inputs+num_outputs+2*state_num_log2); + auto off_state_out = off_ctrl_out + num_outputs; + auto off_ctrl_in = off_state_out + state_num_log2; + auto off_state_in = off_ctrl_in + num_inputs; + auto off_end = off_state_in + state_num_log2; + + RTLIL::Const state_in, state_out, ctrl_in, ctrl_out; + ctrl_out.bits.insert(state_in.bits.begin(), off_ctrl_out, off_state_out); + state_out.bits.insert(state_out.bits.begin(), off_state_out, off_ctrl_in); + ctrl_in.bits.insert(ctrl_in.bits.begin(), off_ctrl_in, off_state_in); + state_in.bits.insert(state_in.bits.begin(), off_state_in, off_end); + + transition_t tr; + tr.state_in = state_in.as_int(); + tr.state_out = state_out.as_int(); + tr.ctrl_in = ctrl_in; + tr.ctrl_out = ctrl_out; + + if (tr.state_in < 0 || tr.state_in >= state_num) + tr.state_in = -1; + if (tr.state_out < 0 || tr.state_out >= state_num) + tr.state_out = -1; + + transition_table.push_back(tr); + } + } + + void log_info(RTLIL::Cell *cell) + { + log("-------------------------------------\n"); + log("\n"); + log(" Information on FSM %s (%s):\n", cell->name.c_str(), cell->parameters["\\NAME"].str.c_str()); + log("\n"); + log(" Number of input signals: %3d\n", num_inputs); + log(" Number of output signals: %3d\n", num_outputs); + log(" Number of state bits: %3d\n", state_bits); + + log("\n"); + log(" Input signals:\n"); + RTLIL::SigSpec sig_in = cell->connections["\\CTRL_IN"]; + sig_in.expand(); + for (size_t i = 0; i < sig_in.chunks.size(); i++) + log(" %3zd: %s\n", i, log_signal(sig_in.chunks[i])); + + log("\n"); + log(" Output signals:\n"); + RTLIL::SigSpec sig_out = cell->connections["\\CTRL_OUT"]; + sig_out.expand(); + for (size_t i = 0; i < sig_out.chunks.size(); i++) + log(" %3zd: %s\n", i, log_signal(sig_out.chunks[i])); + + log("\n"); + log(" State encoding:\n"); + for (size_t i = 0; i < state_table.size(); i++) + log(" %3zd: %10s%s\n", i, log_signal(state_table[i], false), + int(i) == reset_state ? " <RESET STATE>" : ""); + + log("\n"); + log(" Transition Table (state_in, ctrl_in, state_out, ctrl_out):\n"); + for (size_t i = 0; i < transition_table.size(); i++) { + transition_t &tr = transition_table[i]; + log(" %5zd: %5d %s -> %5d %s\n", i, tr.state_in, log_signal(tr.ctrl_in), tr.state_out, log_signal(tr.ctrl_out)); + } + + log("\n"); + log("-------------------------------------\n"); + } + + // implemented in fsm_opt.cc + static void optimize_fsm(RTLIL::Cell *cell, RTLIL::Module *module); +}; + +#endif diff --git a/passes/hierarchy/Makefile.inc b/passes/hierarchy/Makefile.inc new file mode 100644 index 000000000..37cc287ac --- /dev/null +++ b/passes/hierarchy/Makefile.inc @@ -0,0 +1,3 @@ + +OBJS += passes/hierarchy/hierarchy.o + diff --git a/passes/hierarchy/hierarchy.cc b/passes/hierarchy/hierarchy.cc new file mode 100644 index 000000000..c8cd77a16 --- /dev/null +++ b/passes/hierarchy/hierarchy.cc @@ -0,0 +1,194 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/register.h" +#include "kernel/log.h" +#include <stdlib.h> +#include <stdio.h> +#include <set> + +static bool expand_module(RTLIL::Design *design, RTLIL::Module *module, bool flag_check) +{ + bool did_something = false; + + for (auto &cell_it : module->cells) { + RTLIL::Cell *cell = cell_it.second; + if (design->modules.count(cell->type) == 0) { + if (flag_check && cell->type[0] != '$') + log_error("Module `%s' referenced in module `%s' in cell `%s' is not part of the design.\n", + cell->type.c_str(), module->name.c_str(), cell->name.c_str()); + continue; + } + if (cell->parameters.size() == 0) + continue; + RTLIL::Module *mod = design->modules[cell->type]; + cell->type = mod->derive(design, cell->parameters); + cell->parameters.clear(); + } + + if (did_something) + return did_something; + + std::map<RTLIL::SigSpec, int> auto_wires; + + for (auto &wire_it : module->wires) { + if (wire_it.second->auto_width) + auto_wires[RTLIL::SigSpec(wire_it.second)] = -1; + } + + for (auto &cell_it : module->cells) + for (auto &conn : cell_it.second->connections) + for (auto &awit : auto_wires) { + if (awit.second >= 0 || conn.second != awit.first) + continue; + if (design->modules.count(cell_it.second->type) == 0) { + log("WARNING: Module `%s' used in auto-delaration of the wire `%s.%s' cannot be found.\n", + cell_it.second->type.c_str(), module->name.c_str(), log_signal(awit.first)); + continue; + } + RTLIL::Module *mod = design->modules[cell_it.second->type]; + RTLIL::Wire *wire = NULL; + if (mod->wires.count(conn.first) == 0) { + for (auto &wire_it : mod->wires) { + if (wire_it.second->port_id == 0) + continue; + char buffer[100]; + snprintf(buffer, 100, "$%d", wire_it.second->port_id); + if (buffer == conn.first) { + wire = wire_it.second; + break; + } + } + } else + wire = mod->wires[conn.first]; + if (!wire || wire->port_id == 0) + log_error("No port `%s' found in `%s' but used by instanciation in `%s'!\n", + conn.first.c_str(), mod->name.c_str(), module->name.c_str()); + if (wire->auto_width) + log_error("Signal `%s' found in `%s' and used by instanciation in `%s' for an auto wire is an auto-wire itself!\n", + log_signal(awit.first), mod->name.c_str(), module->name.c_str()); + awit.second = wire->width; + } + + std::map<RTLIL::IdString, int> auto_sizes; + for (auto &awit : auto_wires) { + if (awit.second < 0) + log("Can't further resolve auto-wire `%s.%s' (width %d) using cell ports.\n", + module->name.c_str(), awit.first.chunks[0].wire->name.c_str(), + awit.first.chunks[0].wire->width); + else + auto_sizes[awit.first.chunks[0].wire->name] = awit.second; + } + + if (auto_sizes.size() > 0) { + module->update_auto_wires(auto_sizes); + log_header("Continuing EXPAND pass.\n"); + did_something = true; + } + + return did_something; +} + +static void hierarchy_worker(RTLIL::Design *design, std::set<RTLIL::Module*> &used, RTLIL::Module *mod, bool is_top = false) +{ + if (used.count(mod) > 0) + return; + + log("%s module: %s\n", is_top ? "Top" : "Used", mod->name.c_str()); + used.insert(mod); + + for (auto &it : mod->cells) { + if (design->modules.count(it.second->type) > 0) + hierarchy_worker(design, used, design->modules[it.second->type]); + } +} + +static void hierarchy(RTLIL::Design *design, RTLIL::Module *top) +{ + std::set<RTLIL::Module*> used; + hierarchy_worker(design, used, top, true); + + std::vector<RTLIL::Module*> del_modules; + for (auto &it : design->modules) + if (used.count(it.second) == 0) + del_modules.push_back(it.second); + + for (auto mod : del_modules) { + log("Removing unused module `%s'.\n", mod->name.c_str()); + design->modules.erase(mod->name); + delete mod; + } + + log("Removed %zd unused modules.\n", del_modules.size()); +} + +struct HierarchyPass : public Pass { + HierarchyPass() : Pass("hierarchy") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing HIERARCHY pass (removing modules outside design hierarchy).\n"); + + bool flag_check = false; + RTLIL::Module *top_mod = NULL; + + size_t argidx; + for (argidx = 1; argidx < args.size(); argidx++) + { + if (args[argidx] == "-check") { + flag_check = true; + continue; + } + if (args[argidx] == "-top") { + if (++argidx >= args.size()) + log_cmd_error("Option -top requires an additional argument!\n"); + if (args[argidx][0] != '$' && args[argidx][0] != '\\') + top_mod = design->modules.count("\\" + args[argidx]) > 0 ? design->modules["\\" + args[argidx]] : NULL; + else + top_mod = design->modules.count(args[argidx]) > 0 ? design->modules[args[argidx]] : NULL; + if (top_mod == NULL) + log_cmd_error("Module `%s' not found!\n", args[argidx].c_str()); + continue; + } + break; + } + extra_args(args, argidx, design); + + if (top_mod != NULL) + hierarchy(design, top_mod); + + bool did_something = true; + while (did_something) { + did_something = false; + std::vector<std::string> modnames; + modnames.reserve(design->modules.size()); + for (auto &mod_it : design->modules) + modnames.push_back(mod_it.first); + for (auto &modname : modnames) { + if (design->modules.count(modname) == 0) + continue; + if (expand_module(design, design->modules[modname], flag_check)) + did_something = true; + } + } + + if (top_mod != NULL) + hierarchy(design, top_mod); + } +} HierarchyPass; + diff --git a/passes/memory/Makefile.inc b/passes/memory/Makefile.inc new file mode 100644 index 000000000..cffdefe85 --- /dev/null +++ b/passes/memory/Makefile.inc @@ -0,0 +1,6 @@ + +OBJS += passes/memory/memory.o +OBJS += passes/memory/memory_dff.o +OBJS += passes/memory/memory_collect.o +OBJS += passes/memory/memory_map.o + diff --git a/passes/memory/memory.cc b/passes/memory/memory.cc new file mode 100644 index 000000000..c5533b630 --- /dev/null +++ b/passes/memory/memory.cc @@ -0,0 +1,40 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/register.h" +#include "kernel/log.h" +#include <stdlib.h> +#include <stdio.h> + +struct MemoryPass : public Pass { + MemoryPass() : Pass("memory") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing MEMORY pass.\n"); + log_push(); + + extra_args(args, 1, design); + Pass::call(design, "memory_dff"); + Pass::call(design, "memory_collect"); + Pass::call(design, "memory_map"); + + log_pop(); + } +} MemoryPass; + diff --git a/passes/memory/memory_collect.cc b/passes/memory/memory_collect.cc new file mode 100644 index 000000000..b89b97695 --- /dev/null +++ b/passes/memory/memory_collect.cc @@ -0,0 +1,182 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/register.h" +#include "kernel/log.h" +#include <sstream> +#include <stdlib.h> +#include <assert.h> + +static void handle_memory(RTLIL::Module *module, RTLIL::Memory *memory) +{ + log("Collecting $memrd and $memwr for memory `%s' in module `%s':\n", + memory->name.c_str(), module->name.c_str()); + + int addr_bits = 0; + while ((1 << addr_bits) < memory->size) + addr_bits++; + + int wr_ports = 0; + RTLIL::SigSpec sig_wr_clk; + RTLIL::SigSpec sig_wr_clk_enable; + RTLIL::SigSpec sig_wr_clk_polarity; + RTLIL::SigSpec sig_wr_addr; + RTLIL::SigSpec sig_wr_data; + RTLIL::SigSpec sig_wr_en; + + int rd_ports = 0; + RTLIL::SigSpec sig_rd_clk; + RTLIL::SigSpec sig_rd_clk_enable; + RTLIL::SigSpec sig_rd_clk_polarity; + RTLIL::SigSpec sig_rd_addr; + RTLIL::SigSpec sig_rd_data; + + std::vector<std::string> del_cell_ids; + + for (auto &cell_it : module->cells) + { + RTLIL::Cell *cell = cell_it.second; + + if (cell->type == "$memwr" && cell->parameters["\\MEMID"].str == memory->name) + { + wr_ports++; + del_cell_ids.push_back(cell->name); + + RTLIL::SigSpec clk = cell->connections["\\CLK"]; + RTLIL::SigSpec clk_enable = RTLIL::SigSpec(cell->parameters["\\CLK_ENABLE"]); + RTLIL::SigSpec clk_polarity = RTLIL::SigSpec(cell->parameters["\\CLK_POLARITY"]); + RTLIL::SigSpec addr = cell->connections["\\ADDR"]; + RTLIL::SigSpec data = cell->connections["\\DATA"]; + RTLIL::SigSpec en = cell->connections["\\EN"]; + + clk.extend(1, false); + clk_enable.extend(1, false); + clk_polarity.extend(1, false); + addr.extend(addr_bits, false); + data.extend(memory->width, false); + en.extend(1, false); + + sig_wr_clk.append(clk); + sig_wr_clk_enable.append(clk_enable); + sig_wr_clk_polarity.append(clk_polarity); + sig_wr_addr.append(addr); + sig_wr_data.append(data); + sig_wr_en.append(en); + } + + if (cell->type == "$memrd" && cell->parameters["\\MEMID"].str == memory->name) + { + rd_ports++; + del_cell_ids.push_back(cell->name); + + RTLIL::SigSpec clk = cell->connections["\\CLK"]; + RTLIL::SigSpec clk_enable = RTLIL::SigSpec(cell->parameters["\\CLK_ENABLE"]); + RTLIL::SigSpec clk_polarity = RTLIL::SigSpec(cell->parameters["\\CLK_POLARITY"]); + RTLIL::SigSpec addr = cell->connections["\\ADDR"]; + RTLIL::SigSpec data = cell->connections["\\DATA"]; + + clk.extend(1, false); + clk_enable.extend(1, false); + clk_polarity.extend(1, false); + addr.extend(addr_bits, false); + data.extend(memory->width, false); + + sig_rd_clk.append(clk); + sig_rd_clk_enable.append(clk_enable); + sig_rd_clk_polarity.append(clk_polarity); + sig_rd_addr.append(addr); + sig_rd_data.append(data); + } + } + + std::stringstream sstr; + sstr << "$mem$" << memory->name << "$" << (RTLIL::autoidx++); + + RTLIL::Cell *mem = new RTLIL::Cell; + mem->name = sstr.str(); + mem->type = "$mem"; + + mem->parameters["\\MEMID"] = RTLIL::Const(memory->name); + mem->parameters["\\WIDTH"] = RTLIL::Const(memory->width); + mem->parameters["\\OFFSET"] = RTLIL::Const(memory->start_offset); + mem->parameters["\\SIZE"] = RTLIL::Const(memory->size); + mem->parameters["\\ABITS"] = RTLIL::Const(addr_bits); + + sig_wr_clk_enable.optimize(); + sig_wr_clk_polarity.optimize(); + + assert(sig_wr_clk.width == wr_ports); + assert(sig_wr_clk_enable.width == wr_ports && sig_wr_clk_enable.is_fully_const()); + assert(sig_wr_clk_polarity.width == wr_ports && sig_wr_clk_polarity.is_fully_const()); + assert(sig_wr_addr.width == wr_ports * addr_bits); + assert(sig_wr_data.width == wr_ports * memory->width); + assert(sig_wr_en.width == wr_ports); + + mem->parameters["\\WR_PORTS"] = RTLIL::Const(wr_ports); + mem->parameters["\\WR_CLK_ENABLE"] = wr_ports ? sig_wr_clk_enable.chunks[0].data : RTLIL::Const(0, 0); + mem->parameters["\\WR_CLK_POLARITY"] = wr_ports ? sig_wr_clk_enable.chunks[0].data : RTLIL::Const(0, 0); + + mem->connections["\\WR_CLK"] = sig_wr_clk; + mem->connections["\\WR_ADDR"] = sig_wr_addr; + mem->connections["\\WR_DATA"] = sig_wr_data; + mem->connections["\\WR_EN"] = sig_wr_en; + + sig_rd_clk_enable.optimize(); + sig_rd_clk_polarity.optimize(); + + assert(sig_rd_clk.width == rd_ports); + assert(sig_rd_clk_enable.width == rd_ports && sig_rd_clk_enable.is_fully_const()); + assert(sig_rd_clk_polarity.width == rd_ports && sig_rd_clk_polarity.is_fully_const()); + assert(sig_rd_addr.width == rd_ports * addr_bits); + assert(sig_rd_data.width == rd_ports * memory->width); + + mem->parameters["\\RD_PORTS"] = RTLIL::Const(rd_ports); + mem->parameters["\\RD_CLK_ENABLE"] = rd_ports ? sig_rd_clk_enable.chunks[0].data : RTLIL::Const(0, 0); + mem->parameters["\\RD_CLK_POLARITY"] = rd_ports ? sig_rd_clk_enable.chunks[0].data : RTLIL::Const(0, 0); + + mem->connections["\\RD_CLK"] = sig_rd_clk; + mem->connections["\\RD_ADDR"] = sig_rd_addr; + mem->connections["\\RD_DATA"] = sig_rd_data; + + for (auto &id : del_cell_ids) { + delete module->cells[id]; + module->cells.erase(id); + } + module->cells[mem->name] = mem; +} + +static void handle_module(RTLIL::Module *module) +{ + for (auto &mem_it : module->memories) { + handle_memory(module, mem_it.second); + delete mem_it.second; + } + module->memories.clear(); +} + +struct MemoryCollectPass : public Pass { + MemoryCollectPass() : Pass("memory_collect") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) { + log_header("Executing MEMORY_COLLECT pass (generating $mem cells).\n"); + extra_args(args, 1, design); + for (auto &mod_it : design->modules) + handle_module(mod_it.second); + } +} MemoryCollectPass; + diff --git a/passes/memory/memory_dff.cc b/passes/memory/memory_dff.cc new file mode 100644 index 000000000..e188a7af8 --- /dev/null +++ b/passes/memory/memory_dff.cc @@ -0,0 +1,200 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/register.h" +#include "kernel/log.h" +#include <stdlib.h> +#include <assert.h> +#include <sstream> + +static void normalize_sig(RTLIL::Module *module, RTLIL::SigSpec &sig) +{ + for (auto &conn : module->connections) + sig.replace(conn.first, conn.second); +} + +static bool find_sig_before_dff(RTLIL::Module *module, RTLIL::SigSpec &sig, RTLIL::SigSpec &clk, bool &clk_polarity, bool after = false) +{ + bool replaced_bits = false; + normalize_sig(module, sig); + sig.expand(); + + for (size_t i = 0; i < sig.chunks.size(); i++) + { + RTLIL::SigChunk &chunk = sig.chunks[i]; + + if (chunk.wire == NULL) + continue; + + for (auto &cell_it : module->cells) + { + RTLIL::Cell *cell = cell_it.second; + + if (cell->type != "$dff") + continue; + + if (clk != RTLIL::SigSpec(RTLIL::State::Sx)) { + if (cell->connections["\\CLK"] != clk) + continue; + if (cell->parameters["\\CLK_POLARITY"].as_bool() != clk_polarity) + continue; + } + + RTLIL::SigSpec q_norm = cell->connections[after ? "\\D" : "\\Q"]; + normalize_sig(module, q_norm); + + RTLIL::SigSpec d = q_norm.extract(chunk, &cell->connections[after ? "\\Q" : "\\D"]); + if (d.width != 1) + continue; + + assert(d.chunks.size() == 1); + chunk = d.chunks[0]; + clk = cell->connections["\\CLK"]; + clk_polarity = cell->parameters["\\CLK_POLARITY"].as_bool(); + replaced_bits = true; + goto replaced_this_bit; + } + + return false; + replaced_this_bit:; + } + + sig.optimize(); + return replaced_bits; +} + +static void handle_wr_cell(RTLIL::Module *module, RTLIL::Cell *cell) +{ + log("Checking cell `%s' in module `%s': ", cell->name.c_str(), module->name.c_str()); + + RTLIL::SigSpec clk = RTLIL::SigSpec(RTLIL::State::Sx); + bool clk_polarity = 0; + + RTLIL::SigSpec sig_addr = cell->connections["\\ADDR"]; + if (!find_sig_before_dff(module, sig_addr, clk, clk_polarity)) { + log("no (compatible) $dff for address input found.\n"); + return; + } + + RTLIL::SigSpec sig_data = cell->connections["\\DATA"]; + if (!find_sig_before_dff(module, sig_data, clk, clk_polarity)) { + log("no (compatible) $dff for data input found.\n"); + return; + } + + RTLIL::SigSpec sig_en = cell->connections["\\EN"]; + if (!find_sig_before_dff(module, sig_en, clk, clk_polarity)) { + log("no (compatible) $dff for enable input found.\n"); + return; + } + + cell->connections["\\CLK"] = clk; + cell->connections["\\ADDR"] = sig_addr; + cell->connections["\\DATA"] = sig_data; + cell->connections["\\EN"] = sig_en; + cell->parameters["\\CLK_ENABLE"] = RTLIL::Const(1); + cell->parameters["\\CLK_POLARITY"] = RTLIL::Const(clk_polarity); + log("merged $dff to cell.\n"); +} + +#if 1 +static void handle_rd_cell(RTLIL::Module*, RTLIL::Cell*) +{ + // merging dffs into read ports isn't neccessary for memory_map. + // we'd loose the information if the register is on the address or + // data port and wouldn't get any benefits. +} +#else +static void disconnect_dff(RTLIL::Module *module, RTLIL::SigSpec sig) +{ + normalize_sig(module, sig); + sig.sort_and_unify(); + + std::stringstream sstr; + sstr << "$memory_dff_disconnected$" << (RTLIL::autoidx++); + + RTLIL::Wire *wire = new RTLIL::Wire; + wire->name = sstr.str(); + wire->width = sig.width; + module->wires[wire->name] = wire; + + RTLIL::SigSpec newsig(wire); + + for (auto &cell_it : module->cells) { + RTLIL::Cell *cell = cell_it.second; + if (cell->type == "$dff") + cell->connections["\\Q"].replace(sig, newsig); + } +} + +static void handle_rd_cell(RTLIL::Module *module, RTLIL::Cell *cell) +{ + log("Checking cell `%s' in module `%s': ", cell->name.c_str(), module->name.c_str()); + + bool clk_polarity = 0; + + RTLIL::SigSpec clk_addr = RTLIL::SigSpec(RTLIL::State::Sx); + RTLIL::SigSpec sig_addr = cell->connections["\\ADDR"]; + if (find_sig_before_dff(module, sig_addr, clk_addr, clk_polarity)) + { + cell->connections["\\CLK"] = clk_addr; + cell->connections["\\ADDR"] = sig_addr; + cell->parameters["\\CLK_ENABLE"] = RTLIL::Const(1); + cell->parameters["\\CLK_POLARITY"] = RTLIL::Const(clk_polarity); + log("merged address $dff to cell.\n"); + return; + } + + RTLIL::SigSpec clk_data = RTLIL::SigSpec(RTLIL::State::Sx); + RTLIL::SigSpec sig_data = cell->connections["\\DATA"]; + if (find_sig_before_dff(module, sig_data, clk_data, clk_polarity, true)) + { + disconnect_dff(module, sig_data); + cell->connections["\\CLK"] = clk_data; + cell->connections["\\DATA"] = sig_data; + cell->parameters["\\CLK_ENABLE"] = RTLIL::Const(1); + cell->parameters["\\CLK_POLARITY"] = RTLIL::Const(clk_polarity); + log("merged data $dff to cell.\n"); + return; + } + + log("no (compatible) $dff found.\n"); +} +#endif + +static void handle_module(RTLIL::Module *module) +{ + for (auto &cell_it : module->cells) { + if (cell_it.second->type == "$memwr" && !cell_it.second->parameters["\\CLK_ENABLE"].as_bool()) + handle_wr_cell(module, cell_it.second); + if (cell_it.second->type == "$memrd" && !cell_it.second->parameters["\\CLK_ENABLE"].as_bool()) + handle_rd_cell(module, cell_it.second); + } +} + +struct MemoryDffPass : public Pass { + MemoryDffPass() : Pass("memory_dff") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) { + log_header("Executing MEMORY_DFF pass (merging $dff cells to $memrd and $memwr).\n"); + extra_args(args, 1, design); + for (auto &mod_it : design->modules) + handle_module(mod_it.second); + } +} MemoryDffPass; + diff --git a/passes/memory/memory_map.cc b/passes/memory/memory_map.cc new file mode 100644 index 000000000..e7783083b --- /dev/null +++ b/passes/memory/memory_map.cc @@ -0,0 +1,334 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/register.h" +#include "kernel/log.h" +#include <sstream> +#include <set> +#include <stdlib.h> +#include <assert.h> + +static std::string genid(std::string name, std::string token1 = "", int i = -1, std::string token2 = "", int j = -1, std::string token3 = "", int k = -1, std::string token4 = "") +{ + std::stringstream sstr; + sstr << "$memory" << name << token1; + + if (i >= 0) + sstr << "[" << i << "]"; + + sstr << token2; + + if (j >= 0) + sstr << "[" << j << "]"; + + sstr << token3; + + if (k >= 0) + sstr << "[" << k << "]"; + + sstr << token4 << "$" << (RTLIL::autoidx++); + return sstr.str(); +} + +static void handle_cell(RTLIL::Module *module, RTLIL::Cell *cell) +{ + std::set<int> static_ports; + std::map<int, RTLIL::SigSpec> static_cells_map; + int mem_size = cell->parameters["\\SIZE"].as_int(); + int mem_width = cell->parameters["\\WIDTH"].as_int(); + int mem_offset = cell->parameters["\\OFFSET"].as_int(); + int mem_abits = cell->parameters["\\ABITS"].as_int(); + + // delete unused memory cell + if (cell->parameters["\\RD_PORTS"].as_int() == 0 && cell->parameters["\\WR_PORTS"].as_int() == 0) { + module->cells.erase(cell->name); + delete cell; + return; + } + + // all write ports must share the same clock + RTLIL::SigSpec clocks = cell->connections["\\WR_CLK"]; + RTLIL::Const clocks_pol = cell->parameters["\\WR_CLK_POLARITY"]; + RTLIL::Const clocks_en = cell->parameters["\\WR_CLK_ENABLE"]; + RTLIL::SigSpec refclock; + RTLIL::State refclock_pol = RTLIL::State::Sx; + for (int i = 0; i < clocks.width; i++) { + RTLIL::SigSpec wr_en = cell->connections["\\WR_EN"].extract(i, 1); + if (wr_en.is_fully_const() && wr_en.as_int() == 0) { + static_ports.insert(i); + continue; + } + if (clocks_en.bits[i] != RTLIL::State::S1) { + RTLIL::SigSpec wr_addr = cell->connections["\\WR_ADDR"].extract(i*mem_abits, mem_abits); + RTLIL::SigSpec wr_data = cell->connections["\\WR_DATA"].extract(i*mem_width, mem_width); + if (wr_addr.is_fully_const()) { + // FIXME: Actually we should check for wr_en.is_fully_const() also and + // create a $adff cell with this ports wr_en input as reset pin when wr_en + // is not a simple static 1. + static_cells_map[wr_addr.as_int()] = wr_data; + static_ports.insert(i); + continue; + } + log("Not mapping memory cell %s in module %s (write port %d has no clock).\n", + cell->name.c_str(), module->name.c_str(), i); + return; + } + if (refclock.width == 0) { + refclock = clocks.extract(i, 1); + refclock_pol = clocks_pol.bits[i]; + } + if (clocks.extract(i, 1) != refclock || clocks_pol.bits[i] != refclock_pol) { + log("Not mapping memory cell %s in module %s (write clock %d is incompatible with other clocks).\n", + cell->name.c_str(), module->name.c_str(), i); + return; + } + } + + log("Mapping memory cell %s in module %s:\n", cell->name.c_str(), module->name.c_str()); + + std::vector<RTLIL::SigSpec> data_reg_in; + std::vector<RTLIL::SigSpec> data_reg_out; + + int count_static = 0; + + for (int i = 0; i < mem_size; i++) + { + if (static_cells_map.count(i) > 0) + { + data_reg_in.push_back(RTLIL::SigSpec(RTLIL::State::Sz, mem_width)); + data_reg_out.push_back(static_cells_map[i]); + count_static++; + } + else + { + RTLIL::Cell *c = new RTLIL::Cell; + c->name = genid(cell->name, "", i); + c->type = "$dff"; + c->parameters["\\WIDTH"] = cell->parameters["\\WIDTH"]; + c->parameters["\\CLK_POLARITY"] = RTLIL::Const(clocks_pol.bits[0]); + c->connections["\\CLK"] = clocks.extract(0, 1); + module->cells[c->name] = c; + + RTLIL::Wire *w_in = new RTLIL::Wire; + w_in->name = genid(cell->name, "", i, "$d"); + w_in->width = mem_width; + module->wires[w_in->name] = w_in; + data_reg_in.push_back(RTLIL::SigSpec(w_in)); + c->connections["\\D"] = data_reg_in.back(); + + RTLIL::Wire *w_out = new RTLIL::Wire; + w_out->name = stringf("%s[%d]", cell->parameters["\\MEMID"].str.c_str(), i); + if (module->wires.count(w_out->name) > 0) + w_out->name = genid(cell->name, "", i, "$q"); + w_out->width = mem_width; + w_out->start_offset = mem_offset; + module->wires[w_out->name] = w_out; + data_reg_out.push_back(RTLIL::SigSpec(w_out)); + c->connections["\\Q"] = data_reg_out.back(); + } + } + + log(" created %d $dff cells and %d static cells of width %d.\n", mem_size-count_static, count_static, mem_width); + + int count_dff = 0, count_mux = 0, count_wrmux = 0; + + for (int i = 0; i < cell->parameters["\\RD_PORTS"].as_int(); i++) + { + RTLIL::SigSpec rd_addr = cell->connections["\\RD_ADDR"].extract(i*mem_abits, mem_abits); + + std::vector<RTLIL::SigSpec> rd_signals; + rd_signals.push_back(cell->connections["\\RD_DATA"].extract(i*mem_width, mem_width)); + + if (cell->parameters["\\RD_CLK_ENABLE"].bits[i] == RTLIL::State::S1) + { +#if 1 + RTLIL::Cell *c = new RTLIL::Cell; + c->name = genid(cell->name, "$rdreg", i); + c->type = "$dff"; + c->parameters["\\WIDTH"] = RTLIL::Const(mem_abits); + c->parameters["\\CLK_POLARITY"] = RTLIL::Const(cell->parameters["\\RD_CLK_POLARITY"].bits[i]); + c->connections["\\CLK"] = cell->connections["\\RD_CLK"].extract(i, 1); + c->connections["\\D"] = rd_addr; + module->cells[c->name] = c; + count_dff++; + + RTLIL::Wire *w = new RTLIL::Wire; + w->name = genid(cell->name, "$rdreg", i, "$q"); + w->width = mem_abits; + module->wires[w->name] = w; + + c->connections["\\Q"] = RTLIL::SigSpec(w); + rd_addr = RTLIL::SigSpec(w); +#else + RTLIL::Cell *c = new RTLIL::Cell; + c->name = genid(cell->name, "$rdreg", i); + c->type = "$dff"; + c->parameters["\\WIDTH"] = cell->parameters["\\WIDTH"]; + c->parameters["\\CLK_POLARITY"] = RTLIL::Const(cell->parameters["\\RD_CLK_POLARITY"].bits[i]); + c->connections["\\CLK"] = cell->connections["\\RD_CLK"].extract(i, 1); + c->connections["\\Q"] = rd_signals.back(); + module->cells[c->name] = c; + count_dff++; + + RTLIL::Wire *w = new RTLIL::Wire; + w->name = genid(cell->name, "$rdreg", i, "$d"); + w->width = mem_width; + module->wires[w->name] = w; + + rd_signals.clear(); + rd_signals.push_back(RTLIL::SigSpec(w)); + c->connections["\\D"] = rd_signals.back(); +#endif + } + + for (int j = 0; j < mem_abits; j++) + { + std::vector<RTLIL::SigSpec> next_rd_signals; + + for (size_t k = 0; k < rd_signals.size(); k++) + { + RTLIL::Cell *c = new RTLIL::Cell; + c->name = genid(cell->name, "$rdmux", i, "", j, "", k); + c->type = "$mux"; + c->parameters["\\WIDTH"] = cell->parameters["\\WIDTH"]; + c->connections["\\Y"] = rd_signals[k]; + c->connections["\\S"] = rd_addr.extract(mem_abits-j-1, 1); + module->cells[c->name] = c; + count_mux++; + + RTLIL::Wire *w = new RTLIL::Wire; + w->name = genid(cell->name, "$rdmux", i, "", j, "", k, "$a"); + w->width = mem_width; + module->wires[w->name] = w; + c->connections["\\A"] = RTLIL::SigSpec(w); + + w = new RTLIL::Wire; + w->name = genid(cell->name, "$rdmux", i, "", j, "", k, "$b"); + w->width = mem_width; + module->wires[w->name] = w; + c->connections["\\B"] = RTLIL::SigSpec(w); + + next_rd_signals.push_back(c->connections["\\A"]); + next_rd_signals.push_back(c->connections["\\B"]); + } + + next_rd_signals.swap(rd_signals); + } + + for (int j = 0; j < mem_size; j++) + module->connections.push_back(RTLIL::SigSig(rd_signals[j], data_reg_out[j])); + } + + log(" read interface: %d $dff and %d $mux cells.\n", count_dff, count_mux); + + for (int i = 0; i < mem_size; i++) + { + if (static_cells_map.count(i) > 0) + continue; + + RTLIL::SigSpec sig = data_reg_out[i]; + + for (int j = 0; j < cell->parameters["\\WR_PORTS"].as_int(); j++) + { + RTLIL::SigSpec wr_addr = cell->connections["\\WR_ADDR"].extract(j*mem_abits, mem_abits); + RTLIL::SigSpec wr_data = cell->connections["\\WR_DATA"].extract(j*mem_width, mem_width); + RTLIL::SigSpec wr_en = cell->connections["\\WR_EN"].extract(j, 1); + + RTLIL::Cell *c = new RTLIL::Cell; + c->name = genid(cell->name, "$wreq", i, "", j); + c->type = "$eq"; + c->parameters["\\A_SIGNED"] = RTLIL::Const(0); + c->parameters["\\B_SIGNED"] = RTLIL::Const(0); + c->parameters["\\A_WIDTH"] = cell->parameters["\\ABITS"]; + c->parameters["\\B_WIDTH"] = cell->parameters["\\ABITS"]; + c->parameters["\\Y_WIDTH"] = RTLIL::Const(1); + c->connections["\\A"] = RTLIL::SigSpec(i, mem_abits); + c->connections["\\B"] = wr_addr; + module->cells[c->name] = c; + count_wrmux++; + + RTLIL::Wire *w = new RTLIL::Wire; + w->name = genid(cell->name, "$wreq", i, "", j, "$y"); + module->wires[w->name] = w; + c->connections["\\Y"] = RTLIL::SigSpec(w); + + c = new RTLIL::Cell; + c->name = genid(cell->name, "$wren", i, "", j); + c->type = "$and"; + c->parameters["\\A_SIGNED"] = RTLIL::Const(0); + c->parameters["\\B_SIGNED"] = RTLIL::Const(0); + c->parameters["\\A_WIDTH"] = RTLIL::Const(1); + c->parameters["\\B_WIDTH"] = RTLIL::Const(1); + c->parameters["\\Y_WIDTH"] = RTLIL::Const(1); + c->connections["\\A"] = RTLIL::SigSpec(w); + c->connections["\\B"] = wr_en; + module->cells[c->name] = c; + + w = new RTLIL::Wire; + w->name = genid(cell->name, "$wren", i, "", j, "$y"); + module->wires[w->name] = w; + c->connections["\\Y"] = RTLIL::SigSpec(w); + + c = new RTLIL::Cell; + c->name = genid(cell->name, "$wrmux", i, "", j); + c->type = "$mux"; + c->parameters["\\WIDTH"] = cell->parameters["\\WIDTH"]; + c->connections["\\A"] = sig; + c->connections["\\B"] = wr_data; + c->connections["\\S"] = RTLIL::SigSpec(w); + module->cells[c->name] = c; + + w = new RTLIL::Wire; + w->name = genid(cell->name, "$wrmux", i, "", j, "$y"); + w->width = mem_width; + module->wires[w->name] = w; + c->connections["\\Y"] = RTLIL::SigSpec(w); + sig = RTLIL::SigSpec(w); + } + + module->connections.push_back(RTLIL::SigSig(data_reg_in[i], sig)); + } + + log(" write interface: %d blocks of $eq, $and and $mux cells.\n", count_wrmux); + + module->cells.erase(cell->name); + delete cell; + return; +} + +static void handle_module(RTLIL::Module *module) +{ + std::vector<RTLIL::Cell*> cells; + for (auto &it : module->cells) + if (it.second->type == "$mem") + cells.push_back(it.second); + for (auto cell : cells) + handle_cell(module, cell); +} + +struct MemoryMapPass : public Pass { + MemoryMapPass() : Pass("memory_map") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) { + log_header("Executing MEMORY_MAP pass (converting $mem cells to logic and flip-flops).\n"); + extra_args(args, 1, design); + for (auto &mod_it : design->modules) + handle_module(mod_it.second); + } +} MemoryMapPass; + diff --git a/passes/opt/Makefile.inc b/passes/opt/Makefile.inc new file mode 100644 index 000000000..3602b96bd --- /dev/null +++ b/passes/opt/Makefile.inc @@ -0,0 +1,9 @@ + +OBJS += passes/opt/opt.o +OBJS += passes/opt/opt_share.o +OBJS += passes/opt/opt_muxtree.o +OBJS += passes/opt/opt_reduce.o +OBJS += passes/opt/opt_rmdff.o +OBJS += passes/opt/opt_rmunused.o +OBJS += passes/opt/opt_const.o + diff --git a/passes/opt/opt.cc b/passes/opt/opt.cc new file mode 100644 index 000000000..9e33f78ca --- /dev/null +++ b/passes/opt/opt.cc @@ -0,0 +1,62 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "opt_status.h" +#include "kernel/register.h" +#include "kernel/log.h" +#include <stdlib.h> +#include <stdio.h> + +bool OPT_DID_SOMETHING; + +struct OptPass : public Pass { + OptPass() : Pass("opt") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing OPT pass (performing simple optimizations).\n"); + log_push(); + + extra_args(args, 1, design); + + log_header("Optimizing in-memory representation of design.\n"); + design->optimize(); + + Pass::call(design, "opt_const"); + Pass::call(design, "opt_share -nomux"); + while (1) { + OPT_DID_SOMETHING = false; + Pass::call(design, "opt_muxtree"); + Pass::call(design, "opt_reduce"); + Pass::call(design, "opt_share"); + Pass::call(design, "opt_rmdff"); + Pass::call(design, "opt_rmunused"); + Pass::call(design, "opt_const"); + if (OPT_DID_SOMETHING == false) + break; + log_header("Rerunning OPT passes. (Maybe there is more to do..)\n"); + } + + log_header("Optimizing in-memory representation of design.\n"); + design->optimize(); + + log_header("Finished OPT passes. (There is nothing left to do.)\n"); + log_pop(); + } +} OptPass; + diff --git a/passes/opt/opt_const.cc b/passes/opt/opt_const.cc new file mode 100644 index 000000000..9edea6709 --- /dev/null +++ b/passes/opt/opt_const.cc @@ -0,0 +1,263 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#undef MUX_UNDEF_SEL_TO_UNDEF_RESULTS + +#include "opt_status.h" +#include "kernel/register.h" +#include "kernel/sigtools.h" +#include "kernel/log.h" +#include <stdlib.h> +#include <assert.h> +#include <stdio.h> +#include <set> + +bool did_something; + +void replace_cell(RTLIL::Module *module, RTLIL::Cell *cell, std::string info, std::string out_port, RTLIL::SigSpec out_val) +{ + RTLIL::SigSpec Y = cell->connections[out_port]; + log("Replacing %s cell `%s' (%s) in module `%s' with constant driver `%s = %s'.\n", + cell->type.c_str(), cell->name.c_str(), info.c_str(), + module->name.c_str(), log_signal(Y), log_signal(out_val)); + OPT_DID_SOMETHING = true; + // ILANG_BACKEND::dump_cell(stderr, "--> ", cell); + module->connections.push_back(RTLIL::SigSig(Y, out_val)); + module->cells.erase(cell->name); + delete cell; + did_something = true; +} + +void replace_const_cells(RTLIL::Module *module) +{ + SigMap assign_map(module); + + std::vector<RTLIL::Cell*> cells; + cells.reserve(module->cells.size()); + for (auto &cell_it : module->cells) + cells.push_back(cell_it.second); + + for (auto cell : cells) + { +#define ACTION_DO(_p_, _s_) do { replace_cell(module, cell, input.as_string(), _p_, _s_); goto next_cell; } while (0) +#define ACTION_DO_Y(_v_) ACTION_DO("\\Y", RTLIL::SigSpec(RTLIL::State::S ## _v_)) + + if (cell->type == "$_INV_") { + RTLIL::SigSpec input = cell->connections["\\A"]; + assign_map.apply(input); + if (input.match("1")) ACTION_DO_Y(0); + if (input.match("0")) ACTION_DO_Y(1); + if (input.match("*")) ACTION_DO_Y(x); + } + + if (cell->type == "$_AND_") { + RTLIL::SigSpec input; + input.append(cell->connections["\\B"]); + input.append(cell->connections["\\A"]); + assign_map.apply(input); + if (input.match(" 0")) ACTION_DO_Y(0); + if (input.match("0 ")) ACTION_DO_Y(0); + if (input.match("11")) ACTION_DO_Y(1); + if (input.match(" *")) ACTION_DO_Y(x); + if (input.match("* ")) ACTION_DO_Y(x); + } + + if (cell->type == "$_OR_") { + RTLIL::SigSpec input; + input.append(cell->connections["\\B"]); + input.append(cell->connections["\\A"]); + assign_map.apply(input); + if (input.match(" 1")) ACTION_DO_Y(1); + if (input.match("1 ")) ACTION_DO_Y(1); + if (input.match("00")) ACTION_DO_Y(0); + if (input.match(" *")) ACTION_DO_Y(x); + if (input.match("* ")) ACTION_DO_Y(x); + } + + if (cell->type == "$_XOR_") { + RTLIL::SigSpec input; + input.append(cell->connections["\\B"]); + input.append(cell->connections["\\A"]); + assign_map.apply(input); + if (input.match("00")) ACTION_DO_Y(0); + if (input.match("01")) ACTION_DO_Y(1); + if (input.match("10")) ACTION_DO_Y(1); + if (input.match("11")) ACTION_DO_Y(0); + if (input.match(" *")) ACTION_DO_Y(x); + if (input.match("* ")) ACTION_DO_Y(x); + } + + if (cell->type == "$_MUX_") { + RTLIL::SigSpec input; + input.append(cell->connections["\\S"]); + input.append(cell->connections["\\B"]); + input.append(cell->connections["\\A"]); + assign_map.apply(input); + if (input.extract(2, 1) == input.extract(1, 1)) + ACTION_DO("\\Y", input.extract(2, 1)); + if (input.match(" 0")) ACTION_DO("\\Y", input.extract(2, 1)); + if (input.match(" 1")) ACTION_DO("\\Y", input.extract(1, 1)); +#ifdef MUX_UNDEF_SEL_TO_UNDEF_RESULTS + if (input.match("01 ")) ACTION_DO("\\Y", input.extract(0, 1)); + if (input.match(" *")) ACTION_DO_Y(x); +#endif + } + + if (cell->type == "$eq" || cell->type == "$ne") + { + if (cell->parameters["\\A_WIDTH"].as_int() != cell->parameters["\\B_WIDTH"].as_int()) { + int width = std::max(cell->parameters["\\A_WIDTH"].as_int(), cell->parameters["\\B_WIDTH"].as_int()); + cell->connections["\\A"].extend(width, cell->parameters["\\A_SIGNED"].as_bool()); + cell->connections["\\B"].extend(width, cell->parameters["\\B_SIGNED"].as_bool()); + cell->parameters["\\A_WIDTH"] = width; + cell->parameters["\\B_WIDTH"] = width; + } + + RTLIL::SigSpec a = cell->connections["\\A"]; + RTLIL::SigSpec b = cell->connections["\\B"]; + RTLIL::SigSpec new_a, new_b; + a.expand(), b.expand(); + + assert(a.chunks.size() == b.chunks.size()); + for (size_t i = 0; i < a.chunks.size(); i++) { + if (a.chunks[i].wire == NULL && a.chunks[i].data.bits[0] > RTLIL::State::S1) + continue; + if (b.chunks[i].wire == NULL && b.chunks[i].data.bits[0] > RTLIL::State::S1) + continue; + new_a.append(a.chunks[i]); + new_b.append(b.chunks[i]); + } + + if (new_a.width != a.width) { + new_a.optimize(); + new_b.optimize(); + cell->connections["\\A"] = new_a; + cell->connections["\\B"] = new_b; + cell->parameters["\\A_WIDTH"] = new_a.width; + cell->parameters["\\B_WIDTH"] = new_b.width; + } + + if (new_a.width == 0) { + replace_cell(module, cell, "empty", "\\Y", RTLIL::SigSpec(cell->type == "$eq" ? RTLIL::State::S1 : RTLIL::State::S0)); + goto next_cell; + } + } + +#define FOLD_1ARG_CELL(_t) \ + if (cell->type == "$" #_t) { \ + RTLIL::SigSpec a = cell->connections["\\A"]; \ + assign_map.apply(a); \ + if (a.is_fully_const()) { \ + a.optimize(); \ + RTLIL::Const dummy_arg(RTLIL::State::S0, 1); \ + RTLIL::SigSpec y(RTLIL::const_ ## _t(a.chunks[0].data, dummy_arg, \ + cell->parameters["\\A_SIGNED"].as_bool(), false, \ + cell->parameters["\\Y_WIDTH"].as_int())); \ + replace_cell(module, cell, stringf("%s", log_signal(a)), "\\Y", y); \ + goto next_cell; \ + } \ + } +#define FOLD_2ARG_CELL(_t) \ + if (cell->type == "$" #_t) { \ + RTLIL::SigSpec a = cell->connections["\\A"]; \ + RTLIL::SigSpec b = cell->connections["\\B"]; \ + assign_map.apply(a), assign_map.apply(b); \ + if (a.is_fully_const() && b.is_fully_const()) { \ + a.optimize(), b.optimize(); \ + RTLIL::SigSpec y(RTLIL::const_ ## _t(a.chunks[0].data, b.chunks[0].data, \ + cell->parameters["\\A_SIGNED"].as_bool(), \ + cell->parameters["\\B_SIGNED"].as_bool(), \ + cell->parameters["\\Y_WIDTH"].as_int())); \ + replace_cell(module, cell, stringf("%s, %s", log_signal(a), log_signal(b)), "\\Y", y); \ + goto next_cell; \ + } \ + } + + FOLD_1ARG_CELL(not) + FOLD_2ARG_CELL(and) + FOLD_2ARG_CELL(or) + FOLD_2ARG_CELL(xor) + FOLD_2ARG_CELL(xnor) + + FOLD_1ARG_CELL(reduce_and) + FOLD_1ARG_CELL(reduce_or) + FOLD_1ARG_CELL(reduce_xor) + FOLD_1ARG_CELL(reduce_xnor) + FOLD_1ARG_CELL(reduce_bool) + + FOLD_1ARG_CELL(logic_not) + FOLD_2ARG_CELL(logic_and) + FOLD_2ARG_CELL(logic_or) + + FOLD_2ARG_CELL(shl) + FOLD_2ARG_CELL(shr) + FOLD_2ARG_CELL(sshl) + FOLD_2ARG_CELL(sshr) + + FOLD_2ARG_CELL(lt) + FOLD_2ARG_CELL(le) + FOLD_2ARG_CELL(eq) + FOLD_2ARG_CELL(ne) + FOLD_2ARG_CELL(gt) + FOLD_2ARG_CELL(ge) + + FOLD_2ARG_CELL(add) + FOLD_2ARG_CELL(sub) + FOLD_2ARG_CELL(mul) + FOLD_2ARG_CELL(div) + FOLD_2ARG_CELL(mod) + FOLD_2ARG_CELL(pow) + + FOLD_1ARG_CELL(pos) + FOLD_1ARG_CELL(neg) + + if (cell->type == "$mux") { + RTLIL::SigSpec input = cell->connections["\\S"]; + assign_map.apply(input); + if (input.is_fully_const()) + ACTION_DO("\\Y", input.as_bool() ? cell->connections["\\B"] : cell->connections["\\A"]); + } + + next_cell:; +#undef ACTION_DO +#undef ACTION_DO_Y +#undef FOLD_1ARG_CELL +#undef FOLD_2ARG_CELL + } +} + +struct OptConstPass : public Pass { + OptConstPass() : Pass("opt_const") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing OPT_CONST pass (perform const folding).\n"); + log_push(); + + extra_args(args, 1, design); + + for (auto &mod_it : design->modules) + do { + did_something = false; + replace_const_cells(mod_it.second); + } while (did_something); + + log_pop(); + } +} OptConstPass; + diff --git a/passes/opt/opt_muxtree.cc b/passes/opt/opt_muxtree.cc new file mode 100644 index 000000000..d1f4e7b10 --- /dev/null +++ b/passes/opt/opt_muxtree.cc @@ -0,0 +1,417 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "opt_status.h" +#include "kernel/register.h" +#include "kernel/sigtools.h" +#include "kernel/log.h" +#include "kernel/celltypes.h" +#include <stdlib.h> +#include <assert.h> +#include <stdio.h> +#include <set> + +struct OptMuxtreeWorker +{ + RTLIL::Design *design; + RTLIL::Module *module; + SigMap assign_map; + int removed_count; + + typedef std::pair<RTLIL::Wire*,int> bitDef_t; + + struct bitinfo_t { + int num; + bitDef_t bit; + bool seen_non_mux; + std::vector<int> mux_users; + std::vector<int> mux_drivers; + }; + + std::map<bitDef_t, int> bit2num; + std::vector<bitinfo_t> bit2info; + + struct portinfo_t { + std::vector<int> ctrl_sigs; + std::vector<int> input_sigs; + std::vector<int> input_muxes; + bool const_activated; + bool enabled; + }; + + struct muxinfo_t { + RTLIL::Cell *cell; + std::vector<portinfo_t> ports; + }; + + std::vector<muxinfo_t> mux2info; + + OptMuxtreeWorker(RTLIL::Design *design, RTLIL::Module *module) : + design(design), module(module), assign_map(module), removed_count(0) + { + log("Running muxtree optimizier on module %s..\n", module->name.c_str()); + + log(" Creating internal representation of mux trees.\n"); + + // Populate bit2info[]: + // .seen_non_mux + // .mux_users + // .mux_drivers + // Populate mux2info[].ports[]: + // .ctrl_sigs + // .input_sigs + // .const_activated + for (auto &cell_it : module->cells) + { + RTLIL::Cell *cell = cell_it.second; + if (cell->type == "$mux" || cell->type == "$pmux" || cell->type == "$safe_pmux") + { + RTLIL::SigSpec sig_a = cell->connections["\\A"]; + RTLIL::SigSpec sig_b = cell->connections["\\B"]; + RTLIL::SigSpec sig_s = cell->connections["\\S"]; + RTLIL::SigSpec sig_y = cell->connections["\\Y"]; + + muxinfo_t muxinfo; + muxinfo.cell = cell; + + for (int i = 0; i < sig_s.width; i++) { + RTLIL::SigSpec sig = sig_b.extract(i*sig_a.width, sig_a.width); + RTLIL::SigSpec ctrl_sig = assign_map(sig_s.extract(i, 1)); + portinfo_t portinfo; + for (int idx : sig2bits(sig)) { + add_to_list(bit2info[idx].mux_users, mux2info.size()); + add_to_list(portinfo.input_sigs, idx); + } + for (int idx : sig2bits(ctrl_sig)) + add_to_list(portinfo.ctrl_sigs, idx); + portinfo.const_activated = ctrl_sig.is_fully_const() && ctrl_sig.as_bool(); + portinfo.enabled = false; + muxinfo.ports.push_back(portinfo); + } + + portinfo_t portinfo; + for (int idx : sig2bits(sig_a)) { + add_to_list(bit2info[idx].mux_users, mux2info.size()); + add_to_list(portinfo.input_sigs, idx); + } + portinfo.const_activated = false; + portinfo.enabled = false; + muxinfo.ports.push_back(portinfo); + + for (int idx : sig2bits(sig_y)) + add_to_list(bit2info[idx].mux_drivers, mux2info.size()); + + for (int idx : sig2bits(sig_s)) + bit2info[idx].seen_non_mux = true; + + mux2info.push_back(muxinfo); + } + else + { + for (auto &it : cell->connections) { + for (int idx : sig2bits(it.second)) + bit2info[idx].seen_non_mux = true; + } + } + } + for (auto &it : module->wires) { + if (it.second->port_output) + for (int idx : sig2bits(RTLIL::SigSpec(it.second))) + bit2info[idx].seen_non_mux = true; + } + + if (mux2info.size() == 0) { + log(" No muxes found in this module.\n"); + return; + } + + // Populate mux2info[].ports[]: + // .input_muxes + for (size_t i = 0; i < bit2info.size(); i++) + for (int j : bit2info[i].mux_users) + for (auto &p : mux2info[j].ports) { + if (is_in_list(p.input_sigs, i)) + for (int k : bit2info[i].mux_drivers) + add_to_list(p.input_muxes, k); + } + + log(" Evaluating internal representation of mux trees.\n"); + + std::set<int> root_muxes; + for (auto &bi : bit2info) { + if (!bi.seen_non_mux) + continue; + for (int mux_idx : bi.mux_drivers) + root_muxes.insert(mux_idx); + } + for (int mux_idx : root_muxes) + eval_root_mux(mux_idx); + + log(" Analyzing evaluation results.\n"); + + for (auto &mi : mux2info) + { + std::vector<int> live_ports; + for (size_t port_idx = 0; port_idx < mi.ports.size(); port_idx++) { + portinfo_t &pi = mi.ports[port_idx]; + if (pi.enabled) { + live_ports.push_back(port_idx); + } else { + log(" dead port %zd/%zd on %s %s.\n", port_idx+1, mi.ports.size(), + mi.cell->type.c_str(), mi.cell->name.c_str()); + OPT_DID_SOMETHING = true; + removed_count++; + } + } + + if (live_ports.size() == mi.ports.size()) + continue; + + if (live_ports.size() == 0) { + module->cells.erase(mi.cell->name); + delete mi.cell; + continue; + } + + RTLIL::SigSpec sig_a = mi.cell->connections["\\A"]; + RTLIL::SigSpec sig_b = mi.cell->connections["\\B"]; + RTLIL::SigSpec sig_s = mi.cell->connections["\\S"]; + RTLIL::SigSpec sig_y = mi.cell->connections["\\Y"]; + + RTLIL::SigSpec sig_ports = sig_b; + sig_ports.append(sig_a); + + if (live_ports.size() == 1) + { + RTLIL::SigSpec sig_in = sig_ports.extract(live_ports[0]*sig_a.width, sig_a.width); + module->connections.push_back(RTLIL::SigSig(sig_y, sig_in)); + module->cells.erase(mi.cell->name); + delete mi.cell; + } + else + { + RTLIL::SigSpec new_sig_a, new_sig_b, new_sig_s; + + for (size_t i = 0; i < live_ports.size(); i++) { + RTLIL::SigSpec sig_in = sig_ports.extract(live_ports[i]*sig_a.width, sig_a.width); + if (i == live_ports.size()-1) { + new_sig_a = sig_in; + } else { + new_sig_b.append(sig_in); + new_sig_s.append(sig_s.extract(live_ports[i], 1)); + } + } + + mi.cell->connections["\\A"] = new_sig_a; + mi.cell->connections["\\B"] = new_sig_b; + mi.cell->connections["\\S"] = new_sig_s; + if (new_sig_s.width == 1) { + mi.cell->type = "$mux"; + mi.cell->attributes.erase("\\S_WIDTH"); + } else { + mi.cell->attributes["\\S_WIDTH"] = RTLIL::Const(new_sig_s.width); + } + } + } + } + + bool list_is_subset(const std::vector<int> &sub, const std::vector<int> &super) + { + for (int v : sub) + if (!is_in_list(super, v)) + return false; + return true; + } + + bool is_in_list(const std::vector<int> &list, int value) + { + for (int v : list) + if (v == value) + return true; + return false; + } + + void add_to_list(std::vector<int> &list, int value) + { + if (!is_in_list(list, value)) + list.push_back(value); + } + + std::vector<int> sig2bits(RTLIL::SigSpec sig) + { + std::vector<int> results; + assign_map.apply(sig); + sig.expand(); + for (auto &c : sig.chunks) + if (c.wire != NULL) { + bitDef_t bit(c.wire, c.offset); + if (bit2num.count(bit) == 0) { + bitinfo_t info; + info.num = bit2info.size(); + info.bit = bit; + info.seen_non_mux = false; + bit2info.push_back(info); + bit2num[info.bit] = info.num; + } + results.push_back(bit2num[bit]); + } + return results; + } + + struct knowledge_t + { + // database of known inactive signals + // the 2nd integer is a reference counter used to manage the + // list. when it is non-zero the signal in known to be inactive + std::map<int, int> known_inactive; + + // database of known active signals + // the 2nd dimension is the list of or-ed signals. so we know that + // for each i there is a j so that known_active[i][j] points to an + // inactive control signal. + std::vector<std::vector<int>> known_active; + + // this is just used to keep track of visited muxes in order to prohibit + // endless recursion in mux loops + std::set<int> visited_muxes; + }; + + void eval_mux_port(knowledge_t &knowledge, int mux_idx, int port_idx) + { + muxinfo_t &muxinfo = mux2info[mux_idx]; + muxinfo.ports[port_idx].enabled = true; + + for (size_t i = 0; i < muxinfo.ports.size(); i++) { + if (int(i) == port_idx) + continue; + for (int b : muxinfo.ports[i].ctrl_sigs) + knowledge.known_inactive[b]++; + } + + if (port_idx < int(muxinfo.ports.size())-1 && !muxinfo.ports[port_idx].const_activated) + knowledge.known_active.push_back(muxinfo.ports[port_idx].ctrl_sigs); + + for (int m : muxinfo.ports[port_idx].input_muxes) { + if (knowledge.visited_muxes.count(m) > 0) + continue; + knowledge.visited_muxes.insert(m); + eval_mux(knowledge, m); + knowledge.visited_muxes.erase(m); + } + + if (port_idx < int(muxinfo.ports.size())-1 && !muxinfo.ports[port_idx].const_activated) + knowledge.known_active.pop_back(); + + for (size_t i = 0; i < muxinfo.ports.size(); i++) { + if (int(i) == port_idx) + continue; + for (int b : muxinfo.ports[i].ctrl_sigs) + knowledge.known_inactive[b]--; + } + } + + void eval_mux(knowledge_t &knowledge, int mux_idx) + { + muxinfo_t &muxinfo = mux2info[mux_idx]; + + // if there is a constant activated port we just use it + for (size_t port_idx = 0; port_idx < muxinfo.ports.size()-1; port_idx++) + { + portinfo_t &portinfo = muxinfo.ports[port_idx]; + if (portinfo.const_activated) { + eval_mux_port(knowledge, mux_idx, port_idx); + return; + } + } + + // compare ports with known_active signals. if we find a match, only this + // port can be active. do not include the last port (its the default port + // that has no control signals). + for (size_t port_idx = 0; port_idx < muxinfo.ports.size()-1; port_idx++) + { + portinfo_t &portinfo = muxinfo.ports[port_idx]; + for (size_t i = 0; i < knowledge.known_active.size(); i++) { + if (list_is_subset(knowledge.known_active[i], portinfo.ctrl_sigs)) { + eval_mux_port(knowledge, mux_idx, port_idx); + return; + } + } + } + + // compare ports with known_inactive and known_active signals. If all control + // signals of the port are know_inactive or if the control signals of all other + // ports are known_active this port can't be activated. this loop includes the + // default port but no known_inactive match is performed on the default port. + for (size_t port_idx = 0; port_idx < muxinfo.ports.size(); port_idx++) + { + portinfo_t &portinfo = muxinfo.ports[port_idx]; + + if (port_idx < muxinfo.ports.size()-1) { + bool found_non_known_inactive = false; + for (int i : portinfo.ctrl_sigs) + if (knowledge.known_inactive[i] == 0) + found_non_known_inactive = true; + if (!found_non_known_inactive) + continue; + } + + bool port_active = true; + std::vector<int> other_ctrl_sig; + for (size_t i = 0; i < muxinfo.ports.size()-1; i++) { + if (i == port_idx) + continue; + other_ctrl_sig.insert(other_ctrl_sig.end(), + muxinfo.ports[i].ctrl_sigs.begin(), muxinfo.ports[i].ctrl_sigs.end()); + } + for (size_t i = 0; i < knowledge.known_active.size(); i++) { + if (list_is_subset(knowledge.known_active[i], other_ctrl_sig)) + port_active = false; + } + if (port_active) + eval_mux_port(knowledge, mux_idx, port_idx); + } + } + + void eval_root_mux(int mux_idx) + { + knowledge_t knowledge; + eval_mux(knowledge, mux_idx); + } +}; + +struct OptMuxtreePass : public Pass { + OptMuxtreePass() : Pass("opt_muxtree") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing OPT_MUXTREE pass (detect dead branches in mux trees).\n"); + extra_args(args, 1, design); + + int total_count = 0; + for (auto &mod_it : design->modules) { + if (mod_it.second->processes.size() > 0) { + log("Skipping module %s as it contains processes.\n", mod_it.second->name.c_str()); + } else { + OptMuxtreeWorker worker(design, mod_it.second); + total_count += worker.removed_count; + } + } + log("Removed %d multiplexer ports.\n", total_count); + } +} OptMuxtreePass; + diff --git a/passes/opt/opt_reduce.cc b/passes/opt/opt_reduce.cc new file mode 100644 index 000000000..9a1b263a0 --- /dev/null +++ b/passes/opt/opt_reduce.cc @@ -0,0 +1,236 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "opt_status.h" +#include "kernel/register.h" +#include "kernel/sigtools.h" +#include "kernel/log.h" +#include "kernel/sha1.h" +#include "kernel/celltypes.h" +#include <stdlib.h> +#include <assert.h> +#include <stdio.h> +#include <set> + +struct OptReduceWorker +{ + RTLIL::Design *design; + RTLIL::Module *module; + SigMap assign_map; + + int total_count; + bool did_something; + + void opt_reduce(std::set<RTLIL::Cell*> &cells, SigSet<RTLIL::Cell*> &drivers, RTLIL::Cell *cell) + { + if (cells.count(cell) == 0) + return; + cells.erase(cell); + + RTLIL::SigSpec sig_a = assign_map(cell->connections["\\A"]); + sig_a.sort_and_unify(); + sig_a.expand(); + + RTLIL::SigSpec new_sig_a; + for (auto &chunk : sig_a.chunks) + { + if (chunk.wire == NULL && chunk.data.bits[0] == RTLIL::State::S0) { + if (cell->type == "$reduce_and") { + new_sig_a = RTLIL::SigSpec(RTLIL::State::S0); + break; + } + continue; + } + if (chunk.wire == NULL && chunk.data.bits[0] == RTLIL::State::S1) { + if (cell->type == "$reduce_or") { + new_sig_a = RTLIL::SigSpec(RTLIL::State::S1); + break; + } + continue; + } + if (chunk.wire == NULL) { + new_sig_a = RTLIL::SigSpec(RTLIL::State::Sx); + break; + } + + bool imported_children = false; + for (auto child_cell : drivers.find(chunk)) { + if (child_cell->type == cell->type) { + opt_reduce(cells, drivers, child_cell); + new_sig_a.append(child_cell->connections["\\A"]); + imported_children = true; + } + } + if (!imported_children) + new_sig_a.append(chunk); + } + new_sig_a.sort_and_unify(); + + if (new_sig_a != sig_a || sig_a.width != cell->connections["\\A"].width) { + log(" New input vector for %s cell %s: %s\n", cell->type.c_str(), cell->name.c_str(), log_signal(new_sig_a)); + did_something = true; + OPT_DID_SOMETHING = true; + total_count++; + } + + cell->connections["\\A"] = new_sig_a; + cell->parameters["\\A_WIDTH"] = RTLIL::Const(new_sig_a.width); + return; + } + + void opt_mux(RTLIL::Cell *cell) + { + RTLIL::SigSpec sig_a = assign_map(cell->connections["\\A"]); + RTLIL::SigSpec sig_b = assign_map(cell->connections["\\B"]); + RTLIL::SigSpec sig_s = assign_map(cell->connections["\\S"]); + + RTLIL::SigSpec new_sig_b, new_sig_s; + std::set<RTLIL::SigSpec> handled_sig; + + handled_sig.insert(sig_a); + for (int i = 0; i < sig_s.width; i++) + { + RTLIL::SigSpec this_b = sig_b.extract(i*sig_a.width, sig_a.width); + if (handled_sig.count(this_b) > 0) + continue; + + RTLIL::SigSpec this_s = sig_s.extract(i, 1); + for (int j = i+1; j < sig_s.width; j++) { + RTLIL::SigSpec that_b = sig_b.extract(j*sig_a.width, sig_a.width); + if (this_b == that_b) + this_s.append(sig_s.extract(j, 1)); + } + + if (this_s.width > 1) + { + RTLIL::Wire *reduce_or_wire = new RTLIL::Wire; + reduce_or_wire->name = NEW_ID; + module->wires[reduce_or_wire->name] = reduce_or_wire; + + RTLIL::Cell *reduce_or_cell = new RTLIL::Cell; + reduce_or_cell->name = NEW_ID; + reduce_or_cell->type = "$reduce_or"; + reduce_or_cell->connections["\\A"] = this_s; + reduce_or_cell->parameters["\\A_WIDTH"] = RTLIL::Const(this_s.width); + reduce_or_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1); + module->cells[reduce_or_cell->name] = reduce_or_cell; + + this_s = RTLIL::SigSpec(reduce_or_wire); + reduce_or_cell->connections["\\Y"] = this_s; + } + + new_sig_b.append(this_b); + new_sig_s.append(this_s); + handled_sig.insert(this_b); + } + + if (new_sig_s.width != sig_s.width) { + log(" New ctrl vector for %s cell %s: %s\n", cell->type.c_str(), cell->name.c_str(), log_signal(new_sig_s)); + did_something = true; + OPT_DID_SOMETHING = true; + total_count++; + } + + if (new_sig_s.width == 0) + { + module->connections.push_back(RTLIL::SigSig(cell->connections["\\Y"], cell->connections["\\A"])); + assign_map.add(cell->connections["\\Y"], cell->connections["\\A"]); + module->cells.erase(cell->name); + delete cell; + } + else + { + cell->connections["\\B"] = new_sig_b; + cell->connections["\\S"] = new_sig_s; + if (new_sig_s.width > 1) { + cell->parameters["\\S_WIDTH"] = RTLIL::Const(new_sig_s.width); + } else { + cell->type = "$mux"; + cell->parameters.erase("\\S_WIDTH"); + } + } + } + + OptReduceWorker(RTLIL::Design *design, RTLIL::Module *module) : + design(design), module(module), assign_map(module) + { + log(" Optimizing cells in module %s.\n", module->name.c_str()); + + total_count = 0; + did_something = true; + + while (did_something) + { + did_something = false; + + // merge trees of reduce_* cells to one single cell and unify input vectors + // (only handle recduce_and and reduce_or for various reasons) + + const char *type_list[] = { "$reduce_or", "$reduce_and" }; + for (auto type : type_list) + { + SigSet<RTLIL::Cell*> drivers; + std::set<RTLIL::Cell*> cells; + + for (auto &cell_it : module->cells) { + RTLIL::Cell *cell = cell_it.second; + if (cell->type != type || !design->selected(module, cell)) + continue; + drivers.insert(assign_map(cell->connections["\\Y"]), cell); + cells.insert(cell); + } + + while (cells.size() > 0) { + RTLIL::Cell *cell = *cells.begin(); + opt_reduce(cells, drivers, cell); + } + } + + // merge identical inputs on $mux and $pmux cells + + for (auto &cell_it : module->cells) + { + RTLIL::Cell *cell = cell_it.second; + if ((cell->type != "$mux" && cell->type != "$pmux" && cell->type != "$safe_pmux") || !design->selected(module, cell)) + continue; + opt_mux(cell); + } + } + } +}; + +struct OptReducePass : public Pass { + OptReducePass() : Pass("opt_reduce") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing OPT_REDUCE pass (consolidate $*mux and $reduce_* inputs).\n"); + extra_args(args, 1, design); + + int total_count = 0; + for (auto &mod_it : design->modules) { + if (!design->selected(mod_it.second)) + continue; + OptReduceWorker worker(design, mod_it.second); + total_count += worker.total_count; + } + + log("Performed a total of %d changes.\n", total_count); + } +} OptReducePass; + diff --git a/passes/opt/opt_rmdff.cc b/passes/opt/opt_rmdff.cc new file mode 100644 index 000000000..384a4d85f --- /dev/null +++ b/passes/opt/opt_rmdff.cc @@ -0,0 +1,135 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "opt_status.h" +#include "kernel/register.h" +#include "kernel/sigtools.h" +#include "kernel/log.h" +#include <stdlib.h> +#include <stdio.h> + +static SigMap assign_map; + +static bool handle_dff(RTLIL::Module *mod, RTLIL::Cell *dff) +{ + RTLIL::SigSpec sig_d, sig_q, sig_c, sig_r; + RTLIL::Const val_cp, val_rp, val_rv; + + if (dff->type == "$_DFF_N_" || dff->type == "$_DFF_P_") { + sig_d = dff->connections["\\D"]; + sig_q = dff->connections["\\Q"]; + sig_c = dff->connections["\\C"]; + val_cp = RTLIL::Const(dff->type == "$_DFF_P_", 1); + } + else if (dff->type.substr(0,6) == "$_DFF_" && dff->type.substr(9) == "_" && + (dff->type[6] == 'N' || dff->type[6] == 'P') && + (dff->type[7] == 'N' || dff->type[7] == 'P') && + (dff->type[8] == '0' || dff->type[8] == '1')) { + sig_d = dff->connections["\\D"]; + sig_q = dff->connections["\\Q"]; + sig_c = dff->connections["\\C"]; + sig_r = dff->connections["\\R"]; + val_cp = RTLIL::Const(dff->type[6] == 'P', 1); + val_rp = RTLIL::Const(dff->type[7] == 'P', 1); + val_rv = RTLIL::Const(dff->type[8] == '1', 1); + } + else if (dff->type == "$dff") { + sig_d = dff->connections["\\D"]; + sig_q = dff->connections["\\Q"]; + sig_c = dff->connections["\\CLK"]; + val_cp = RTLIL::Const(dff->parameters["\\CLK_POLARITY"].as_bool(), 1); + } + else if (dff->type == "$adff") { + sig_d = dff->connections["\\D"]; + sig_q = dff->connections["\\Q"]; + sig_c = dff->connections["\\CLK"]; + sig_r = dff->connections["\\ARST"]; + val_cp = RTLIL::Const(dff->parameters["\\CLK_POLARITY"].as_bool(), 1); + val_rp = RTLIL::Const(dff->parameters["\\ARST_POLARITY"].as_bool(), 1); + val_rv = dff->parameters["\\ARST_VALUE"]; + } + else + log_error("abort."); + + assign_map.apply(sig_d); + assign_map.apply(sig_q); + assign_map.apply(sig_c); + assign_map.apply(sig_r); + + if (sig_d.is_fully_const() && sig_r.width == 0) { + RTLIL::SigSig conn(sig_q, sig_d); + mod->connections.push_back(conn); + goto delete_dff; + } + + if (sig_d == sig_q && sig_r.width == 0) { + goto delete_dff; + } + + return false; + +delete_dff: + log("Removing %s (%s) from module %s.\n", dff->name.c_str(), dff->type.c_str(), mod->name.c_str()); + OPT_DID_SOMETHING = true; + mod->cells.erase(dff->name); + delete dff; + return true; +} + +struct OptRmdffPass : public Pass { + OptRmdffPass() : Pass("opt_rmdff") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + int total_count = 0; + log_header("Executing OPT_RMDFF pass (remove dff with constant values).\n"); + + extra_args(args, 1, design); + + for (auto &mod_it : design->modules) + { + assign_map.set(mod_it.second); + + std::vector<std::string> dff_list; + for (auto &it : mod_it.second->cells) { + if (it.second->type == "$_DFF_N_") dff_list.push_back(it.first); + if (it.second->type == "$_DFF_P_") dff_list.push_back(it.first); + if (it.second->type == "$_DFF_NN0_") dff_list.push_back(it.first); + if (it.second->type == "$_DFF_NN1_") dff_list.push_back(it.first); + if (it.second->type == "$_DFF_NP0_") dff_list.push_back(it.first); + if (it.second->type == "$_DFF_NP1_") dff_list.push_back(it.first); + if (it.second->type == "$_DFF_PN0_") dff_list.push_back(it.first); + if (it.second->type == "$_DFF_PN1_") dff_list.push_back(it.first); + if (it.second->type == "$_DFF_PP0_") dff_list.push_back(it.first); + if (it.second->type == "$_DFF_PP1_") dff_list.push_back(it.first); + if (it.second->type == "$dff") dff_list.push_back(it.first); + if (it.second->type == "$adff") dff_list.push_back(it.first); + } + + for (auto &id : dff_list) { + if (mod_it.second->cells.count(id) > 0 && + handle_dff(mod_it.second, mod_it.second->cells[id])) + total_count++; + } + } + + assign_map.clear(); + log("Replaced %d DFF cells.\n", total_count); + } +} OptRmdffPass; + diff --git a/passes/opt/opt_rmunused.cc b/passes/opt/opt_rmunused.cc new file mode 100644 index 000000000..29a6f2bc4 --- /dev/null +++ b/passes/opt/opt_rmunused.cc @@ -0,0 +1,239 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "opt_status.h" +#include "kernel/register.h" +#include "kernel/sigtools.h" +#include "kernel/log.h" +#include "kernel/celltypes.h" +#include <stdlib.h> +#include <assert.h> +#include <stdio.h> +#include <set> + +static CellTypes ct; + +static void rmunused_module_cells(RTLIL::Module *module) +{ + SigMap assign_map(module); + std::set<RTLIL::Cell*> queue, unused; + + SigSet<RTLIL::Cell*> wire2driver; + for (auto &it : module->cells) { + RTLIL::Cell *cell = it.second; + for (auto &it2 : cell->connections) { + if (!ct.cell_input(cell->type, it2.first)) { + RTLIL::SigSpec sig = it2.second; + assign_map.apply(sig); + wire2driver.insert(sig, cell); + } + } + if (cell->type == "$memwr") + queue.insert(cell); + unused.insert(cell); + } + + for (auto &it : module->wires) { + RTLIL::Wire *wire = it.second; + if (wire->port_output) { + std::set<RTLIL::Cell*> cell_list; + RTLIL::SigSpec sig = RTLIL::SigSpec(wire); + assign_map.apply(sig); + wire2driver.find(sig, cell_list); + for (auto cell : cell_list) + queue.insert(cell); + } + } + + while (queue.size() > 0) + { + std::set<RTLIL::Cell*> new_queue; + for (auto cell : queue) + unused.erase(cell); + for (auto cell : queue) { + for (auto &it : cell->connections) { + if (!ct.cell_output(cell->type, it.first)) { + std::set<RTLIL::Cell*> cell_list; + RTLIL::SigSpec sig = it.second; + assign_map.apply(sig); + wire2driver.find(sig, cell_list); + for (auto cell : cell_list) { + if (unused.count(cell) > 0) + new_queue.insert(cell); + } + } + } + } + queue.swap(new_queue); + } + + for (auto cell : unused) { + log(" removing unused `%s' cell `%s'.\n", cell->type.c_str(), cell->name.c_str()); + OPT_DID_SOMETHING = true; + module->cells.erase(cell->name); + delete cell; + } +} + +static bool compare_signals(RTLIL::SigSpec &s1, RTLIL::SigSpec &s2) +{ + assert(s1.width == 1); + assert(s2.width == 1); + assert(s1.chunks.size() == 1); + assert(s2.chunks.size() == 1); + + RTLIL::Wire *w1 = s1.chunks[0].wire; + RTLIL::Wire *w2 = s2.chunks[0].wire; + + if (w1 == NULL || w2 == NULL) + return w2 == NULL; + + if (w1->port_input != w2->port_input) + return w2->port_input; + + if (w1->name[0] != w2->name[0]) + return w2->name[0] == '\\'; + + if (w1->attributes.size() != w2->attributes.size()) + return w2->attributes.size() > w1->attributes.size(); + + return w2->name < w1->name; +} + +static void rmunused_module_signals(RTLIL::Module *module) +{ + SigMap assign_map(module); + for (auto &it : module->wires) { + RTLIL::Wire *wire = it.second; + for (int i = 0; i < wire->width; i++) { + RTLIL::SigSpec s1 = RTLIL::SigSpec(wire, 1, i), s2 = assign_map(s1); + if (!compare_signals(s1, s2)) + assign_map.add(s1); + } + } + + module->connections.clear(); + + SigPool used_signals; + SigPool used_signals_nodrivers; + for (auto &it : module->cells) { + RTLIL::Cell *cell = it.second; + for (auto &it2 : cell->connections) { + assign_map.apply(it2.second); + used_signals.add(it2.second); + if (!ct.cell_output(cell->type, it2.first)) + used_signals_nodrivers.add(it2.second); + } + } + + std::vector<RTLIL::Wire*> del_wires; + for (auto &it : module->wires) { + RTLIL::Wire *wire = it.second; + if (wire->name[0] == '\\') { + RTLIL::SigSpec s1 = RTLIL::SigSpec(wire), s2 = s1; + assign_map.apply(s2); + if (!used_signals.check_any(s2) && wire->port_id == 0) { + log(" removing unused non-port wire %s.\n", wire->name.c_str()); + del_wires.push_back(wire); + } else { + s1.expand(); + s2.expand(); + assert(s1.chunks.size() == s2.chunks.size()); + RTLIL::SigSig new_conn; + for (size_t i = 0; i < s1.chunks.size(); i++) + if (s1.chunks[i] != s2.chunks[i]) { + new_conn.first.append(s1.chunks[i]); + new_conn.second.append(s2.chunks[i]); + } + if (new_conn.first.width > 0) { + new_conn.first.optimize(); + new_conn.second.optimize(); + module->connections.push_back(new_conn); + } + } + } else { + if (!used_signals.check_any(RTLIL::SigSpec(wire))) + del_wires.push_back(wire); + } + RTLIL::SigSpec sig = assign_map(RTLIL::SigSpec(wire)); + if (!used_signals_nodrivers.check_any(sig)) { + std::string unused_bits; + sig.expand(); + for (size_t i = 0; i < sig.chunks.size(); i++) { + if (sig.chunks[i].wire == NULL) + continue; + if (!used_signals_nodrivers.check_any(sig)) { + if (!unused_bits.empty()) + unused_bits += " "; + unused_bits += stringf("%zd", i); + } + } + if (unused_bits.empty() || wire->port_id != 0) + wire->attributes.erase("\\unused_bits"); + else + wire->attributes["\\unused_bits"] = RTLIL::Const(unused_bits); + } else { + wire->attributes.erase("\\unused_bits"); + } + } + + for (auto wire : del_wires) { + module->wires.erase(wire->name); + delete wire; + } + + if (del_wires.size() > 0) + log(" removed %zd unused temporary wires.\n", del_wires.size()); +} + +static void rmunused_module(RTLIL::Module *module) +{ + log("Finding unused cells or wires in module %s..\n", module->name.c_str()); + + rmunused_module_cells(module); + rmunused_module_signals(module); +} + +struct OptRmUnusedPass : public Pass { + OptRmUnusedPass() : Pass("opt_rmunused") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing OPT_RMUNUSED pass (remove unused cells and wires).\n"); + log_push(); + + extra_args(args, 1, design); + + ct.setup_internals(); + ct.setup_internals_mem(); + ct.setup_stdcells(); + ct.setup_stdcells_mem(); + + for (auto &mod_it : design->modules) { + if (mod_it.second->processes.size() > 0) { + log("Skipping module %s as it contains processes.\n", mod_it.second->name.c_str()); + } else { + rmunused_module(mod_it.second); + } + } + + ct.clear(); + log_pop(); + } +} OptRmUnusedPass; + diff --git a/passes/opt/opt_share.cc b/passes/opt/opt_share.cc new file mode 100644 index 000000000..ecad8b436 --- /dev/null +++ b/passes/opt/opt_share.cc @@ -0,0 +1,250 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "opt_status.h" +#include "kernel/register.h" +#include "kernel/sigtools.h" +#include "kernel/log.h" +#include "kernel/sha1.h" +#include "kernel/celltypes.h" +#include <stdlib.h> +#include <assert.h> +#include <stdio.h> +#include <set> + +#define USE_CELL_HASH_CACHE + +struct OptShareWorker +{ + RTLIL::Design *design; + RTLIL::Module *module; + SigMap assign_map; + + CellTypes ct; + int total_count; +#ifdef USE_CELL_HASH_CACHE + std::map<const RTLIL::Cell*, std::string> cell_hash_cache; +#endif + +#ifdef USE_CELL_HASH_CACHE + std::string int_to_hash_string(unsigned int v) + { + if (v == 0) + return "0"; + std::string str = ""; + while (v > 0) { + str += 'a' + (v & 15); + v = v >> 4; + } + return str; + } + + std::string hash_cell_parameters_and_connections(const RTLIL::Cell *cell) + { + if (cell_hash_cache.count(cell) > 0) + return cell_hash_cache[cell]; + + std::string hash_string = cell->type + "\n"; + + for (auto &it : cell->parameters) + hash_string += "P " + it.first + "=" + it.second.as_string() + "\n"; + + for (auto &it : cell->connections) { + if (ct.cell_output(cell->type, it.first)) + continue; + RTLIL::SigSpec sig = it.second; + assign_map.apply(sig); + hash_string += "C " + it.first + "="; + for (auto &chunk : sig.chunks) { + if (chunk.wire) + hash_string += "{" + chunk.wire->name + " " + + int_to_hash_string(chunk.offset) + " " + + int_to_hash_string(chunk.width) + "}"; + else + hash_string += chunk.data.as_string(); + } + hash_string += "\n"; + } + + unsigned char hash[20]; + char hash_hex_string[41]; + sha1::calc(hash_string.c_str(), hash_string.size(), hash); + sha1::toHexString(hash, hash_hex_string); + cell_hash_cache[cell] = hash_hex_string; + + return cell_hash_cache[cell]; + } +#endif + + bool compare_cell_parameters_and_connections(const RTLIL::Cell *cell1, const RTLIL::Cell *cell2, bool <) + { +#ifdef USE_CELL_HASH_CACHE + std::string hash1 = hash_cell_parameters_and_connections(cell1); + std::string hash2 = hash_cell_parameters_and_connections(cell2); + + if (hash1 != hash2) { + lt = hash1 < hash2; + return true; + } +#endif + + if (cell1->parameters != cell2->parameters) { + lt = cell1->parameters < cell2->parameters; + return true; + } + + std::map<RTLIL::IdString, RTLIL::SigSpec> conn1 = cell1->connections; + std::map<RTLIL::IdString, RTLIL::SigSpec> conn2 = cell2->connections; + + for (auto &it : conn1) { + if (ct.cell_output(cell1->type, it.first)) + it.second = RTLIL::SigSpec(); + else + assign_map.apply(it.second); + } + + for (auto &it : conn2) { + if (ct.cell_output(cell2->type, it.first)) + it.second = RTLIL::SigSpec(); + else + assign_map.apply(it.second); + } + + if (conn1 != conn2) { + lt = conn1 < conn2; + return true; + } + + return false; + } + + bool compare_cells(const RTLIL::Cell *cell1, const RTLIL::Cell *cell2) + { + if (cell1->type != cell2->type) + return cell1->type < cell2->type; + + if (!ct.cell_known(cell1->type)) + return cell1 < cell2; + + bool lt; + if (compare_cell_parameters_and_connections(cell1, cell2, lt)) + return lt; + + return false; + } + + struct CompareCells { + OptShareWorker *that; + CompareCells(OptShareWorker *that) : that(that) {} + bool operator()(const RTLIL::Cell *cell1, const RTLIL::Cell *cell2) const { + return that->compare_cells(cell1, cell2); + } + }; + + OptShareWorker(RTLIL::Design *design, RTLIL::Module *module, bool mode_nomux) : + design(design), module(module), assign_map(module) + { + total_count = 0; + ct.setup_internals(); + ct.setup_internals_mem(); + ct.setup_stdcells(); + ct.setup_stdcells_mem(); + + if (mode_nomux) { + ct.cell_types.erase("$mux"); + ct.cell_types.erase("$pmux"); + ct.cell_types.erase("$safe_pmux"); + } + + log("Finding identical cells in module `%s'.\n", module->name.c_str()); + assign_map.set(module); + + bool did_something = true; + while (did_something) + { +#ifdef USE_CELL_HASH_CACHE + cell_hash_cache.clear(); +#endif + std::vector<RTLIL::Cell*> cells; + cells.reserve(module->cells.size()); + for (auto &it : module->cells) { + if (ct.cell_known(it.second->type) && design->selected(module, it.second)) + cells.push_back(it.second); + } + + did_something = false; + std::map<RTLIL::Cell*, RTLIL::Cell*, CompareCells> sharemap(CompareCells(this)); + for (auto cell : cells) + { + if (sharemap.count(cell) > 0) { + did_something = true; + log(" Cell `%s' is identical to cell `%s'.\n", cell->name.c_str(), sharemap[cell]->name.c_str()); + for (auto &it : cell->connections) { + if (ct.cell_output(cell->type, it.first)) { + RTLIL::SigSpec other_sig = sharemap[cell]->connections[it.first]; + log(" Redirecting output %s: %s = %s\n", it.first.c_str(), + log_signal(it.second), log_signal(other_sig)); + module->connections.push_back(RTLIL::SigSig(it.second, other_sig)); + assign_map.add(it.second, other_sig); + } + } + log(" Removing %s cell `%s' from module `%s'.\n", cell->type.c_str(), cell->name.c_str(), module->name.c_str()); + module->cells.erase(cell->name); + OPT_DID_SOMETHING = true; + total_count++; + delete cell; + } else { + sharemap[cell] = cell; + } + } + } + } +}; + +struct OptSharePass : public Pass { + OptSharePass() : Pass("opt_share") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing OPT_SHARE pass (detect identical cells).\n"); + + bool mode_nomux = false; + + size_t argidx; + for (argidx = 1; argidx < args.size(); argidx++) { + std::string arg = args[argidx]; + if (arg == "-nomux") { + mode_nomux = true; + continue; + } + break; + } + extra_args(args, argidx, design); + + int total_count = 0; + for (auto &mod_it : design->modules) { + if (!design->selected(mod_it.second)) + continue; + OptShareWorker worker(design, mod_it.second, mode_nomux); + total_count += worker.total_count; + } + + log("Removed a total of %d cells.\n", total_count); + } +} OptSharePass; + diff --git a/passes/opt/opt_status.h b/passes/opt/opt_status.h new file mode 100644 index 000000000..3d12baa7d --- /dev/null +++ b/passes/opt/opt_status.h @@ -0,0 +1,26 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#ifndef OPT_STATUS_H +#define OPT_STATUS_H + +extern bool OPT_DID_SOMETHING; + +#endif + diff --git a/passes/proc/Makefile.inc b/passes/proc/Makefile.inc new file mode 100644 index 000000000..68564e055 --- /dev/null +++ b/passes/proc/Makefile.inc @@ -0,0 +1,8 @@ + +OBJS += passes/proc/proc.o +OBJS += passes/proc/proc_clean.o +OBJS += passes/proc/proc_rmdead.o +OBJS += passes/proc/proc_arst.o +OBJS += passes/proc/proc_mux.o +OBJS += passes/proc/proc_dff.o + diff --git a/passes/proc/proc.cc b/passes/proc/proc.cc new file mode 100644 index 000000000..c0f502c83 --- /dev/null +++ b/passes/proc/proc.cc @@ -0,0 +1,44 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/register.h" +#include "kernel/log.h" +#include <stdlib.h> +#include <stdio.h> + +struct ProcPass : public Pass { + ProcPass() : Pass("proc") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing PROC pass (convert processes to netlists).\n"); + log_push(); + + extra_args(args, 1, design); + + Pass::call(design, "proc_clean"); + Pass::call(design, "proc_rmdead"); + Pass::call(design, "proc_arst"); + Pass::call(design, "proc_mux"); + Pass::call(design, "proc_dff"); + Pass::call(design, "proc_clean"); + + log_pop(); + } +} ProcPass; + diff --git a/passes/proc/proc_arst.cc b/passes/proc/proc_arst.cc new file mode 100644 index 000000000..8e57d0efc --- /dev/null +++ b/passes/proc/proc_arst.cc @@ -0,0 +1,191 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/register.h" +#include "kernel/sigtools.h" +#include "kernel/log.h" +#include <stdlib.h> +#include <stdio.h> + +static bool check_signal(RTLIL::Module *mod, RTLIL::SigSpec signal, RTLIL::SigSpec ref, bool &polarity) +{ + if (signal.width != 1) + return false; + if (signal == ref) + return true; + + for (auto &cell_it : mod->cells) { + RTLIL::Cell *cell = cell_it.second; + if (cell->type == "$reduce_or" && cell->connections["\\Y"] == signal) + return check_signal(mod, cell->connections["\\A"], ref, polarity); + if (cell->type == "$reduce_bool" && cell->connections["\\Y"] == signal) + return check_signal(mod, cell->connections["\\A"], ref, polarity); + if (cell->type == "$logic_not" && cell->connections["\\Y"] == signal) { + polarity = !polarity; + return check_signal(mod, cell->connections["\\A"], ref, polarity); + } + if (cell->type == "$not" && cell->connections["\\Y"] == signal) { + polarity = !polarity; + return check_signal(mod, cell->connections["\\A"], ref, polarity); + } + if (cell->type == "$eq" && cell->connections["\\Y"] == signal) { + if (cell->connections["\\A"].is_fully_const()) { + if (!cell->connections["\\A"].as_bool()) + polarity = !polarity; + return check_signal(mod, cell->connections["\\B"], ref, polarity); + } + if (cell->connections["\\B"].is_fully_const()) { + if (!cell->connections["\\B"].as_bool()) + polarity = !polarity; + return check_signal(mod, cell->connections["\\A"], ref, polarity); + } + } + if (cell->type == "$ne" && cell->connections["\\Y"] == signal) { + if (cell->connections["\\A"].is_fully_const()) { + if (cell->connections["\\A"].as_bool()) + polarity = !polarity; + return check_signal(mod, cell->connections["\\B"], ref, polarity); + } + if (cell->connections["\\B"].is_fully_const()) { + if (cell->connections["\\B"].as_bool()) + polarity = !polarity; + return check_signal(mod, cell->connections["\\A"], ref, polarity); + } + } + } + + return false; +} + +static void apply_const(RTLIL::Module *mod, const RTLIL::SigSpec rspec, RTLIL::SigSpec &rval, RTLIL::CaseRule *cs, RTLIL::SigSpec const_sig, bool polarity, bool unknown) +{ + for (auto &action : cs->actions) { + if (unknown) + rspec.replace(action.first, RTLIL::SigSpec(RTLIL::State::Sm, action.second.width), &rval); + else + rspec.replace(action.first, action.second, &rval); + } + + for (auto sw : cs->switches) { + if (sw->signal.width == 0) { + for (auto cs2 : sw->cases) + apply_const(mod, rspec, rval, cs2, const_sig, polarity, unknown); + } + bool this_polarity = polarity; + if (check_signal(mod, sw->signal, const_sig, this_polarity)) { + for (auto cs2 : sw->cases) { + for (auto comp : cs2->compare) + if (comp == RTLIL::SigSpec(this_polarity, 1)) + goto matched_case; + if (cs2->compare.size() == 0) { + matched_case: + apply_const(mod, rspec, rval, cs2, const_sig, polarity, false); + break; + } + } + } else { + for (auto cs2 : sw->cases) + apply_const(mod, rspec, rval, cs2, const_sig, polarity, true); + } + } +} + +static void eliminate_const(RTLIL::Module *mod, RTLIL::CaseRule *cs, RTLIL::SigSpec const_sig, bool polarity) +{ + for (auto sw : cs->switches) { + bool this_polarity = polarity; + if (check_signal(mod, sw->signal, const_sig, this_polarity)) { + bool found_rem_path = false; + for (size_t i = 0; i < sw->cases.size(); i++) { + RTLIL::CaseRule *cs2 = sw->cases[i]; + for (auto comp : cs2->compare) + if (comp == RTLIL::SigSpec(this_polarity, 1)) + goto matched_case; + if (found_rem_path) { + matched_case: + sw->cases.erase(sw->cases.begin() + (i--)); + delete cs2; + continue; + } + found_rem_path = true; + cs2->compare.clear(); + } + sw->signal = RTLIL::SigSpec(); + } else { + for (auto cs2 : sw->cases) + eliminate_const(mod, cs2, const_sig, polarity); + } + } +} + +static void proc_arst(RTLIL::Module *mod, RTLIL::Process *proc, SigMap &assign_map) +{ + if (proc->root_case.switches.size() != 1) + return; + + RTLIL::SigSpec root_sig = proc->root_case.switches[0]->signal; + + for (auto &sync : proc->syncs) { + if (sync->type == RTLIL::SyncType::STp || sync->type == RTLIL::SyncType::STn) { + bool polarity = sync->type == RTLIL::SyncType::STp; + if (check_signal(mod, root_sig, sync->signal, polarity)) { + log("Found async reset %s in `%s.%s'.\n", log_signal(sync->signal), mod->name.c_str(), proc->name.c_str()); + sync->type = sync->type == RTLIL::SyncType::STp ? RTLIL::SyncType::ST1 : RTLIL::SyncType::ST0; + for (auto &action : sync->actions) { + RTLIL::SigSpec rspec = action.second; + RTLIL::SigSpec rval = RTLIL::SigSpec(RTLIL::State::Sm, rspec.width); + RTLIL::SigSpec last_rval; + for (int count = 0; rval != last_rval; count++) { + last_rval = rval; + apply_const(mod, rspec, rval, &proc->root_case, root_sig, polarity, false); + assign_map.apply(rval); + if (rval.is_fully_const()) + break; + if (count > 100) + log_error("Async reset %s yields endless loop at value %s for signal %s.\n", + log_signal(sync->signal), log_signal(rval), log_signal(action.first)); + rspec = rval; + } + if (rval.has_marked_bits()) + log_error("Async reset %s yields non-constant value %s for signal %s.\n", + log_signal(sync->signal), log_signal(rval), log_signal(action.first)); + action.second = rval; + } + eliminate_const(mod, &proc->root_case, root_sig, polarity); + } + } + } +} + +struct ProcArstPass : public Pass { + ProcArstPass() : Pass("proc_arst") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing PROC_ARST pass (detect async resets in processes).\n"); + + extra_args(args, 1, design); + + for (auto &mod_it : design->modules) { + SigMap assign_map(mod_it.second); + for (auto &proc_it : mod_it.second->processes) + proc_arst(mod_it.second, proc_it.second, assign_map); + } + } +} ProcArstPass; + diff --git a/passes/proc/proc_clean.cc b/passes/proc/proc_clean.cc new file mode 100644 index 000000000..ec9fade30 --- /dev/null +++ b/passes/proc/proc_clean.cc @@ -0,0 +1,160 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/register.h" +#include "kernel/log.h" +#include <stdlib.h> +#include <stdio.h> + +static void switch_clean(RTLIL::SwitchRule *sw, RTLIL::CaseRule *parent, bool &did_something, int &count); +static void case_clean(RTLIL::CaseRule *cs, bool &did_something, int &count); + +static void switch_clean(RTLIL::SwitchRule *sw, RTLIL::CaseRule *parent, bool &did_something, int &count) +{ + if (sw->signal.width > 0 && sw->signal.is_fully_const()) + { + int found_matching_case_idx = -1; + for (int i = 0; i < int(sw->cases.size()) && found_matching_case_idx < 0; i++) + { + RTLIL::CaseRule *cs = sw->cases[i]; + if (cs->compare.size() == 0) + break; + for (int j = 0; j < int(cs->compare.size()); j++) { + RTLIL::SigSpec &val = cs->compare[j]; + if (!val.is_fully_const()) + continue; + if (val == sw->signal) { + cs->compare.clear(); + found_matching_case_idx = i; + break; + } else + cs->compare.erase(cs->compare.begin()+(j--)); + } + if (cs->compare.size() == 0 && found_matching_case_idx < 0) { + sw->cases.erase(sw->cases.begin()+(i--)); + delete cs; + } + } + while (found_matching_case_idx >= 0 && int(sw->cases.size()) > found_matching_case_idx+1) { + delete sw->cases.back(); + sw->cases.pop_back(); + } + if (found_matching_case_idx == 0) + sw->signal = RTLIL::SigSpec(); + } + + if (sw->cases.size() == 1 && (sw->signal.width == 0 || sw->cases[0]->compare.empty())) + { + did_something = true; + for (auto &action : sw->cases[0]->actions) + parent->actions.push_back(action); + for (auto sw2 : sw->cases[0]->switches) + parent->switches.push_back(sw2); + sw->cases[0]->switches.clear(); + delete sw->cases[0]; + sw->cases.clear(); + } + else + { + bool all_cases_are_empty = true; + for (auto cs : sw->cases) { + if (cs->actions.size() != 0 || cs->switches.size() != 0) + all_cases_are_empty = false; + case_clean(cs, did_something, count); + } + if (all_cases_are_empty) { + did_something = true; + for (auto cs : sw->cases) + delete cs; + sw->cases.clear(); + } + } +} + +static void case_clean(RTLIL::CaseRule *cs, bool &did_something, int &count) +{ + for (size_t i = 0; i < cs->actions.size(); i++) { + if (cs->actions[i].first.width == 0) { + did_something = true; + cs->actions.erase(cs->actions.begin() + (i--)); + } + } + for (size_t i = 0; i < cs->switches.size(); i++) { + RTLIL::SwitchRule *sw = cs->switches[i]; + if (sw->cases.size() == 0) { + cs->switches.erase(cs->switches.begin() + (i--)); + did_something = true; + delete sw; + count++; + } else + switch_clean(sw, cs, did_something, count); + } +} + +static void proc_clean(RTLIL::Module *mod, RTLIL::Process *proc, int &total_count) +{ + int count = 0; + bool did_something = true; + for (size_t i = 0; i < proc->syncs.size(); i++) { + for (size_t j = 0; j < proc->syncs[i]->actions.size(); j++) + if (proc->syncs[i]->actions[j].first.width == 0) + proc->syncs[i]->actions.erase(proc->syncs[i]->actions.begin() + (j--)); + if (proc->syncs[i]->actions.size() == 0) { + delete proc->syncs[i]; + proc->syncs.erase(proc->syncs.begin() + (i--)); + } + } + while (did_something) { + did_something = false; + case_clean(&proc->root_case, did_something, count); + } + if (count > 0) + log("Found and cleaned up %d empty switch%s in `%s.%s'.\n", count, count == 1 ? "" : "es", mod->name.c_str(), proc->name.c_str()); + total_count += count; +} + +struct ProcCleanPass : public Pass { + ProcCleanPass() : Pass("proc_clean") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + int total_count = 0; + log_header("Executing PROC_CLEAN pass (remove empty switches from decision trees).\n"); + + extra_args(args, 1, design); + + for (auto &mod_it : design->modules) { + std::vector<std::string> delme; + for (auto &proc_it : mod_it.second->processes) { + proc_clean(mod_it.second, proc_it.second, total_count); + if (proc_it.second->syncs.size() == 0 && proc_it.second->root_case.switches.size() == 0 && + proc_it.second->root_case.actions.size() == 0) { + log("Removing empty process `%s.%s'.\n", mod_it.first.c_str(), proc_it.second->name.c_str()); + delme.push_back(proc_it.first); + } + } + for (auto &id : delme) { + delete mod_it.second->processes[id]; + mod_it.second->processes.erase(id); + } + } + + log("Cleaned up %d empty switch%s.\n", total_count, total_count == 1 ? "" : "es"); + } +} ProcCleanPass; + diff --git a/passes/proc/proc_dff.cc b/passes/proc/proc_dff.cc new file mode 100644 index 000000000..ccacc72d2 --- /dev/null +++ b/passes/proc/proc_dff.cc @@ -0,0 +1,178 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/register.h" +#include "kernel/sigtools.h" +#include "kernel/consteval.h" +#include "kernel/log.h" +#include <sstream> +#include <stdlib.h> +#include <stdio.h> +#include <assert.h> + +static RTLIL::SigSpec find_any_lvalue(const RTLIL::Process *proc) +{ + RTLIL::SigSpec lvalue; + + for (auto sync : proc->syncs) + for (auto &action : sync->actions) + if (action.first.width > 0) { + lvalue = action.first; + lvalue.sort_and_unify(); + break; + } + + for (auto sync : proc->syncs) { + RTLIL::SigSpec this_lvalue; + for (auto &action : sync->actions) + this_lvalue.append(action.first); + this_lvalue.sort_and_unify(); + RTLIL::SigSpec common_sig = this_lvalue.extract(lvalue); + if (common_sig.width > 0) + lvalue = common_sig; + } + + return lvalue; +} + +static void gen_dff(RTLIL::Module *mod, RTLIL::SigSpec sig_in, RTLIL::Const val_rst, RTLIL::SigSpec sig_out, + bool clk_polarity, bool arst_polarity, RTLIL::SigSpec clk, RTLIL::SigSpec *arst, RTLIL::Process *proc) +{ + std::stringstream sstr; + sstr << "$procdff$" << (RTLIL::autoidx++); + + RTLIL::Cell *cell = new RTLIL::Cell; + cell->name = sstr.str(); + cell->type = arst ? "$adff" : "$dff"; + cell->attributes = proc->attributes; + mod->cells[cell->name] = cell; + + cell->parameters["\\WIDTH"] = RTLIL::Const(sig_in.width); + if (arst) { + cell->parameters["\\ARST_POLARITY"] = RTLIL::Const(arst_polarity, 1); + cell->parameters["\\ARST_VALUE"] = val_rst; + } + cell->parameters["\\CLK_POLARITY"] = RTLIL::Const(clk_polarity, 1); + + cell->connections["\\D"] = sig_in; + cell->connections["\\Q"] = sig_out; + if (arst) + cell->connections["\\ARST"] = *arst; + cell->connections["\\CLK"] = clk; + + log(" created %s cell `%s' with %s edge clock", cell->type.c_str(), cell->name.c_str(), clk_polarity ? "positive" : "negative"); + if (arst) + log(" and %s level reset", arst_polarity ? "positive" : "negative"); + log(".\n"); +} + +static void proc_dff(RTLIL::Module *mod, RTLIL::Process *proc, ConstEval &ce) +{ + while (1) + { + RTLIL::SigSpec sig = find_any_lvalue(proc); + + if (sig.width == 0) + break; + + log("Creating register for signal `%s.%s' using process `%s.%s'.\n", + mod->name.c_str(), log_signal(sig), mod->name.c_str(), proc->name.c_str()); + + RTLIL::SigSpec insig = RTLIL::SigSpec(RTLIL::State::Sz, sig.width); + RTLIL::SigSpec rstval = RTLIL::SigSpec(RTLIL::State::Sz, sig.width); + RTLIL::SyncRule *sync_level = NULL; + RTLIL::SyncRule *sync_edge = NULL; + RTLIL::SyncRule *sync_always = NULL; + + for (auto sync : proc->syncs) + for (auto &action : sync->actions) + { + if (action.first.extract(sig).width == 0) + continue; + + if (sync->type == RTLIL::SyncType::ST0 || sync->type == RTLIL::SyncType::ST1) { + if (sync_level != NULL && sync_level != sync) + log_error("Multiple level sensitive events found for this signal!\n"); + sig.replace(action.first, action.second, &rstval); + sync_level = sync; + } + else if (sync->type == RTLIL::SyncType::STp || sync->type == RTLIL::SyncType::STn) { + if (sync_edge != NULL && sync_edge != sync) + log_error("Multiple edge sensitive events found for this signal!\n"); + sig.replace(action.first, action.second, &insig); + sync_edge = sync; + } + else if (sync->type == RTLIL::SyncType::STa) { + if (sync_always != NULL && sync_always != sync) + log_error("Multiple always events found for this signal!\n"); + sig.replace(action.first, action.second, &insig); + sync_always = sync; + } + else { + log_error("Event with any-edge sensitivity found for this signal!\n"); + } + + action.first.remove2(sig, &action.second); + } + + ce.assign_map.apply(insig); + ce.assign_map.apply(rstval); + ce.assign_map.apply(sig); + + insig.optimize(); + rstval.optimize(); + sig.optimize(); + + if (sync_always) { + if (sync_edge || sync_level) + log_error("Mixed always event with edge and/or level sensitive events!\n"); + log(" created direct connection (no actual register cell created).\n"); + mod->connections.push_back(RTLIL::SigSig(sig, insig)); + continue; + } + + if (!sync_edge) + log_error("Missing edge-sensitive event for this signal!\n"); + + if (!rstval.is_fully_const() && !ce.eval(rstval)) + log_error("Async reset value `%s' is not constant!\n", log_signal(rstval)); + + gen_dff(mod, insig, rstval.chunks[0].data, sig, + sync_edge->type == RTLIL::SyncType::STp, + sync_level && sync_level->type == RTLIL::SyncType::ST1, + sync_edge->signal, sync_level ? &sync_level->signal : NULL, proc); + } +} + +struct ProcDffPass : public Pass { + ProcDffPass() : Pass("proc_dff") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing PROC_DFF pass (convert process syncs to FFs).\n"); + + extra_args(args, 1, design); + + for (auto &mod_it : design->modules) { + ConstEval ce(mod_it.second); + for (auto &proc_it : mod_it.second->processes) + proc_dff(mod_it.second, proc_it.second, ce); + } + } +} ProcDffPass; + diff --git a/passes/proc/proc_mux.cc b/passes/proc/proc_mux.cc new file mode 100644 index 000000000..4d50597d1 --- /dev/null +++ b/passes/proc/proc_mux.cc @@ -0,0 +1,294 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/register.h" +#include "kernel/bitpattern.h" +#include "kernel/log.h" +#include <sstream> +#include <stdlib.h> +#include <stdio.h> +#include <assert.h> + +static RTLIL::SigSpec find_any_lvalue(const RTLIL::CaseRule *cs) +{ + for (auto &action : cs->actions) { + if (action.first.width) + return action.first; + } + + for (auto sw : cs->switches) + for (auto cs2 : sw->cases) { + RTLIL::SigSpec sig = find_any_lvalue(cs2); + if (sig.width) + return sig; + } + + return RTLIL::SigSpec(); +} + +static void extract_core_signal(const RTLIL::CaseRule *cs, RTLIL::SigSpec &sig) +{ + for (auto &action : cs->actions) { + RTLIL::SigSpec lvalue = action.first.extract(sig); + if (lvalue.width) + sig = lvalue; + } + + for (auto sw : cs->switches) + for (auto cs2 : sw->cases) + extract_core_signal(cs2, sig); +} + +static RTLIL::SigSpec gen_cmp(RTLIL::Module *mod, const RTLIL::SigSpec &signal, const std::vector<RTLIL::SigSpec> &compare, RTLIL::SwitchRule *sw) +{ + std::stringstream sstr; + sstr << "$procmux$" << (RTLIL::autoidx++); + + RTLIL::Wire *cmp_wire = new RTLIL::Wire; + cmp_wire->name = sstr.str() + "_CMP"; + cmp_wire->width = 0; + mod->wires[cmp_wire->name] = cmp_wire; + + for (auto comp : compare) + { + RTLIL::SigSpec sig = signal; + sig.expand(); + comp.expand(); + + // get rid of don't-care bits + assert(sig.width == comp.width); + for (int i = 0; i < comp.width; i++) + if (comp.chunks[i].wire == NULL && comp.chunks[i].data.bits[0] == RTLIL::State::Sa) { + sig.remove(i, 1); + comp.remove(i--, 1); + } + if (comp.width == 0) + return RTLIL::SigSpec(); + sig.optimize(); + comp.optimize(); + + if (sig.width == 1 && comp == RTLIL::SigSpec(1,1)) + { + mod->connections.push_back(RTLIL::SigSig(RTLIL::SigSpec(cmp_wire, 1, cmp_wire->width++), sig)); + } + else + { + // create compare cell + RTLIL::Cell *eq_cell = new RTLIL::Cell; + std::stringstream sstr2; + sstr2 << sstr.str() << "_CMP" << cmp_wire->width; + eq_cell->name = sstr2.str(); + eq_cell->type = "$eq"; + eq_cell->attributes = sw->attributes; + mod->cells[eq_cell->name] = eq_cell; + + eq_cell->parameters["\\A_SIGNED"] = RTLIL::Const(0); + eq_cell->parameters["\\B_SIGNED"] = RTLIL::Const(0); + + eq_cell->parameters["\\A_WIDTH"] = RTLIL::Const(sig.width); + eq_cell->parameters["\\B_WIDTH"] = RTLIL::Const(comp.width); + eq_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1); + + eq_cell->connections["\\A"] = sig; + eq_cell->connections["\\B"] = comp; + eq_cell->connections["\\Y"] = RTLIL::SigSpec(cmp_wire, 1, cmp_wire->width++); + } + } + + RTLIL::Wire *ctrl_wire; + if (cmp_wire->width == 1) + { + ctrl_wire = cmp_wire; + } + else + { + ctrl_wire = new RTLIL::Wire; + ctrl_wire->name = sstr.str() + "_CTRL"; + ctrl_wire->width = 1; + mod->wires[ctrl_wire->name] = ctrl_wire; + + // reduce cmp vector to one logic signal + RTLIL::Cell *any_cell = new RTLIL::Cell; + any_cell->name = sstr.str() + "_ANY"; + any_cell->type = "$reduce_or"; + any_cell->attributes = sw->attributes; + mod->cells[any_cell->name] = any_cell; + + any_cell->parameters["\\A_SIGNED"] = RTLIL::Const(0); + any_cell->parameters["\\A_WIDTH"] = RTLIL::Const(cmp_wire->width); + any_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1); + + any_cell->connections["\\A"] = cmp_wire; + any_cell->connections["\\Y"] = RTLIL::SigSpec(ctrl_wire); + } + + return RTLIL::SigSpec(ctrl_wire); +} + +static RTLIL::SigSpec gen_mux(RTLIL::Module *mod, const RTLIL::SigSpec &signal, const std::vector<RTLIL::SigSpec> &compare, RTLIL::SigSpec when_signal, RTLIL::SigSpec else_signal, RTLIL::Cell *&last_mux_cell, RTLIL::SwitchRule *sw) +{ + assert(when_signal.width == else_signal.width); + + std::stringstream sstr; + sstr << "$procmux$" << (RTLIL::autoidx++); + + // the trivial cases + if (compare.size() == 0 || when_signal == else_signal) + return when_signal; + + // compare results + RTLIL::SigSpec ctrl_sig = gen_cmp(mod, signal, compare, sw); + if (ctrl_sig.width == 0) + return when_signal; + assert(ctrl_sig.width == 1); + + // prepare multiplexer output signal + RTLIL::Wire *result_wire = new RTLIL::Wire; + result_wire->name = sstr.str() + "_Y"; + result_wire->width = when_signal.width; + mod->wires[result_wire->name] = result_wire; + + // create the multiplexer itself + RTLIL::Cell *mux_cell = new RTLIL::Cell; + mux_cell->name = sstr.str(); + mux_cell->type = "$mux"; + mux_cell->attributes = sw->attributes; + mod->cells[mux_cell->name] = mux_cell; + + mux_cell->parameters["\\WIDTH"] = RTLIL::Const(when_signal.width); + mux_cell->connections["\\A"] = else_signal; + mux_cell->connections["\\B"] = when_signal; + mux_cell->connections["\\S"] = ctrl_sig; + mux_cell->connections["\\Y"] = RTLIL::SigSpec(result_wire); + + last_mux_cell = mux_cell; + return RTLIL::SigSpec(result_wire); +} + +static void append_pmux(RTLIL::Module *mod, const RTLIL::SigSpec &signal, const std::vector<RTLIL::SigSpec> &compare, RTLIL::SigSpec when_signal, RTLIL::Cell *last_mux_cell, RTLIL::SwitchRule *sw) +{ + assert(last_mux_cell != NULL); + assert(when_signal.width == last_mux_cell->connections["\\A"].width); + + std::stringstream sstr; + sstr << "$procmux$" << (RTLIL::autoidx++); + + RTLIL::SigSpec ctrl_sig = gen_cmp(mod, signal, compare, sw); + assert(ctrl_sig.width == 1); + last_mux_cell->type = "$pmux"; + last_mux_cell->connections["\\S"].append(ctrl_sig); + last_mux_cell->connections["\\B"].append(when_signal); + last_mux_cell->parameters["\\S_WIDTH"] = last_mux_cell->connections["\\S"].width; +} + +static RTLIL::SigSpec signal_to_mux_tree(RTLIL::Module *mod, RTLIL::CaseRule *cs, const RTLIL::SigSpec &sig, const RTLIL::SigSpec &defval) +{ + RTLIL::SigSpec result = defval; + + for (auto &action : cs->actions) { + sig.replace(action.first, action.second, &result); + action.first.remove2(sig, &action.second); + } + + for (auto sw : cs->switches) + { + // detect groups of parallel cases + std::vector<int> pgroups(sw->cases.size()); + if (sw->attributes.count("\\parallel_case") == 0) { + BitPatternPool pool(sw->signal.width); + bool extra_group_for_next_case = false; + for (size_t i = 0; i < sw->cases.size(); i++) { + RTLIL::CaseRule *cs2 = sw->cases[i]; + if (i != 0) { + pgroups[i] = pgroups[i-1]; + if (extra_group_for_next_case) { + pgroups[i] = pgroups[i-1]+1; + extra_group_for_next_case = false; + } + for (auto pat : cs2->compare) + if (!pat.is_fully_const() || !pool.has_all(pat)) + pgroups[i] = pgroups[i-1]+1; + if (cs2->compare.empty()) + pgroups[i] = pgroups[i-1]+1; + if (pgroups[i] != pgroups[i-1]) + pool = BitPatternPool(sw->signal.width); + } + for (auto pat : cs2->compare) + if (!pat.is_fully_const()) + extra_group_for_next_case = true; + else + pool.take(pat); + } + } + + // evaluate in reverse order to give the first entry the top priority + RTLIL::SigSpec initial_val = result; + RTLIL::Cell *last_mux_cell = NULL; + for (size_t i = 0; i < sw->cases.size(); i++) { + int case_idx = sw->cases.size() - i - 1; + RTLIL::CaseRule *cs2 = sw->cases[case_idx]; + RTLIL::SigSpec value = signal_to_mux_tree(mod, cs2, sig, initial_val); + if (last_mux_cell && pgroups[case_idx] == pgroups[case_idx+1]) + append_pmux(mod, sw->signal, cs2->compare, value, last_mux_cell, sw); + else + result = gen_mux(mod, sw->signal, cs2->compare, value, result, last_mux_cell, sw); + } + } + + return result; +} + +static void proc_mux(RTLIL::Module *mod, RTLIL::Process *proc) +{ + bool first = true; + while (1) + { + RTLIL::SigSpec sig = find_any_lvalue(&proc->root_case); + + if (sig.width == 0) + break; + + if (first) { + log("Creating decoders for process `%s.%s'.\n", mod->name.c_str(), proc->name.c_str()); + first = false; + } + + extract_core_signal(&proc->root_case, sig); + + log(" creating decoder for signal `%s'.\n", log_signal(sig)); + + RTLIL::SigSpec value = signal_to_mux_tree(mod, &proc->root_case, sig, RTLIL::SigSpec(RTLIL::State::Sx, sig.width)); + mod->connections.push_back(RTLIL::SigSig(sig, value)); + } +} + +struct ProcMuxPass : public Pass { + ProcMuxPass() : Pass("proc_mux") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing PROC_MUX pass (convert decision trees to multiplexers).\n"); + + extra_args(args, 1, design); + + for (auto &mod_it : design->modules) + for (auto &proc_it : mod_it.second->processes) + proc_mux(mod_it.second, proc_it.second); + } +} ProcMuxPass; + diff --git a/passes/proc/proc_rmdead.cc b/passes/proc/proc_rmdead.cc new file mode 100644 index 000000000..ca2070cad --- /dev/null +++ b/passes/proc/proc_rmdead.cc @@ -0,0 +1,87 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/register.h" +#include "kernel/bitpattern.h" +#include "kernel/log.h" +#include <sstream> +#include <stdlib.h> +#include <stdio.h> +#include <assert.h> +#include <set> + +static void proc_rmdead(RTLIL::SwitchRule *sw, int &counter) +{ + BitPatternPool pool(sw->signal); + + for (size_t i = 0; i < sw->cases.size(); i++) + { + bool is_default = sw->cases[i]->compare.size() == 0 && !pool.empty(); + + for (size_t j = 0; j < sw->cases[i]->compare.size(); j++) { + RTLIL::SigSpec sig = sw->cases[i]->compare[j]; + if (!sig.is_fully_const()) + continue; + if (!pool.take(sig)) + sw->cases[i]->compare.erase(sw->cases[i]->compare.begin() + (j--)); + } + + if (!is_default) { + if (sw->cases[i]->compare.size() == 0) { + delete sw->cases[i]; + sw->cases.erase(sw->cases.begin() + (i--)); + counter++; + continue; + } + if (pool.empty()) + sw->cases[i]->compare.clear(); + } + + for (auto switch_it : sw->cases[i]->switches) + proc_rmdead(switch_it, counter); + + if (is_default) + pool.take_all(); + } +} + +struct ProcRmdeadPass : public Pass { + ProcRmdeadPass() : Pass("proc_rmdead") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing PROC_RMDEAD pass (remove dead branches from decision trees).\n"); + + extra_args(args, 1, design); + + int total_counter = 0; + for (auto &mod_it : design->modules) + for (auto &proc_it : mod_it.second->processes) { + int counter = 0; + for (auto switch_it : proc_it.second->root_case.switches) + proc_rmdead(switch_it, counter); + if (counter > 0) + log("Removed %d dead cases from process %s in module %s.\n", counter, + proc_it.first.c_str(), mod_it.first.c_str()); + total_counter += counter; + } + + log("Removed a total of %d dead cases.\n", total_counter); + } +} ProcRmdeadPass; + diff --git a/passes/submod/Makefile.inc b/passes/submod/Makefile.inc new file mode 100644 index 000000000..b0c00eae1 --- /dev/null +++ b/passes/submod/Makefile.inc @@ -0,0 +1,3 @@ + +OBJS += passes/submod/submod.o + diff --git a/passes/submod/submod.cc b/passes/submod/submod.cc new file mode 100644 index 000000000..ba1b4b08b --- /dev/null +++ b/passes/submod/submod.cc @@ -0,0 +1,273 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/register.h" +#include "kernel/celltypes.h" +#include "kernel/log.h" +#include <stdlib.h> +#include <stdio.h> +#include <set> + +struct SubmodWorker +{ + CellTypes ct; + RTLIL::Design *design; + RTLIL::Module *module; + + struct SubModule + { + std::string name, full_name; + std::set<RTLIL::Cell*> cells; + }; + + std::map<std::string, SubModule> submodules; + + struct wire_flags_t { + RTLIL::Wire *new_wire; + bool is_int_driven, is_int_used, is_ext_driven, is_ext_used; + wire_flags_t() : new_wire(NULL), is_int_driven(false), is_int_used(false), is_ext_driven(false), is_ext_used(false) { } + }; + std::map<RTLIL::Wire*, wire_flags_t> wire_flags; + bool flag_found_something; + + void flag_wire(RTLIL::Wire *wire, bool create, bool set_int_driven, bool set_int_used, bool set_ext_driven, bool set_ext_used) + { + if (wire_flags.count(wire) == 0) { + if (!create) + return; + wire_flags[wire] = wire_flags_t(); + } + if (set_int_driven) + wire_flags[wire].is_int_driven = true; + if (set_int_used) + wire_flags[wire].is_int_used = true; + if (set_ext_driven) + wire_flags[wire].is_ext_driven = true; + if (set_ext_used) + wire_flags[wire].is_ext_used = true; + flag_found_something = true; + } + + void flag_signal(RTLIL::SigSpec &sig, bool create, bool set_int_driven, bool set_int_used, bool set_ext_driven, bool set_ext_used) + { + for (auto &c : sig.chunks) + if (c.wire != NULL) + flag_wire(c.wire, create, set_int_driven, set_int_used, set_ext_driven, set_ext_used); + } + + void handle_submodule(SubModule &submod) + { + log("Creating submodule %s (%s) of module %s.\n", submod.name.c_str(), submod.full_name.c_str(), module->name.c_str()); + + wire_flags.clear(); + for (RTLIL::Cell *cell : submod.cells) { + if (ct.cell_known(cell->type)) { + for (auto &conn : cell->connections) + flag_signal(conn.second, true, ct.cell_output(cell->type, conn.first), ct.cell_input(cell->type, conn.first), false, false); + } else { + log("WARNING: Port directions for cell %s (%s) are unknown. Assuming inout for all ports.\n", cell->name.c_str(), cell->type.c_str()); + for (auto &conn : cell->connections) + flag_signal(conn.second, true, true, true, false, false); + } + } + for (auto &it : module->cells) { + RTLIL::Cell *cell = it.second; + if (submod.cells.count(cell) > 0) + continue; + if (ct.cell_known(cell->type)) { + for (auto &conn : cell->connections) + flag_signal(conn.second, false, false, false, ct.cell_output(cell->type, conn.first), ct.cell_input(cell->type, conn.first)); + } else { + flag_found_something = false; + for (auto &conn : cell->connections) + flag_signal(conn.second, false, false, false, true, true); + if (flag_found_something) + log("WARNING: Port directions for cell %s (%s) are unknown. Assuming inout for all ports.\n", cell->name.c_str(), cell->type.c_str()); + } + } + + RTLIL::Module *new_mod = new RTLIL::Module; + new_mod->name = submod.full_name; + design->modules[new_mod->name] = new_mod; + int port_counter = 1, auto_name_counter = 1; + + std::set<std::string> all_wire_names; + for (auto &it : wire_flags) { + all_wire_names.insert(it.first->name); + } + + for (auto &it : wire_flags) + { + RTLIL::Wire *wire = it.first; + wire_flags_t &flags = it.second; + + if (wire->port_input) + flags.is_ext_driven = true; + if (wire->port_output) + flags.is_ext_used = true; + + RTLIL::Wire *new_wire = new RTLIL::Wire; + new_wire->name = wire->name; + new_wire->width = wire->width; + new_wire->start_offset = wire->start_offset; + new_wire->attributes = wire->attributes; + + if (flags.is_int_driven && flags.is_ext_used) + new_wire->port_output = true; + if (flags.is_ext_driven && flags.is_int_used) + new_wire->port_input = true; + + if (flags.is_int_driven && flags.is_ext_driven) + new_wire->port_input = true, new_wire->port_output = true; + + if (new_wire->port_input || new_wire->port_output) { + new_wire->port_id = port_counter++; + while (new_wire->name[0] == '$') { + std::string new_wire_name = stringf("\\n%d", auto_name_counter++); + if (all_wire_names.count(new_wire_name) == 0) { + all_wire_names.insert(new_wire_name); + new_wire->name = new_wire_name; + } + } + } + + if (new_wire->port_input && new_wire->port_output) + log(" signal %s: inout %s\n", wire->name.c_str(), new_wire->name.c_str()); + else if (new_wire->port_input) + log(" signal %s: input %s\n", wire->name.c_str(), new_wire->name.c_str()); + else if (new_wire->port_output) + log(" signal %s: output %s\n", wire->name.c_str(), new_wire->name.c_str()); + else + log(" signal %s: internal\n", wire->name.c_str()); + + new_mod->wires[new_wire->name] = new_wire; + flags.new_wire = new_wire; + } + + for (RTLIL::Cell *cell : submod.cells) { + RTLIL::Cell *new_cell = new RTLIL::Cell(*cell); + for (auto &conn : new_cell->connections) + for (auto &c : conn.second.chunks) + if (c.wire != NULL) { + assert(wire_flags.count(c.wire) > 0); + c.wire = wire_flags[c.wire].new_wire; + } + log(" cell %s (%s)\n", new_cell->name.c_str(), new_cell->type.c_str()); + new_mod->cells[new_cell->name] = new_cell; + module->cells.erase(cell->name); + delete cell; + } + submod.cells.clear(); + + RTLIL::Cell *new_cell = new RTLIL::Cell; + new_cell->name = submod.full_name; + new_cell->type = submod.full_name; + for (auto &it : wire_flags) + { + RTLIL::Wire *old_wire = it.first; + RTLIL::Wire *new_wire = it.second.new_wire; + if (new_wire->port_id > 0) + new_cell->connections[new_wire->name] = RTLIL::SigSpec(old_wire); + } + module->cells[new_cell->name] = new_cell; + } + + SubmodWorker(RTLIL::Design *design, RTLIL::Module *module) : design(design), module(module) + { + if (!design->selected_whole_module(module->name)) + return; + + if (module->processes.size() > 0) { + log("Skipping module %s as it contains processes (run 'proc' pass first).\n", module->name.c_str()); + return; + } + + if (module->memories.size() > 0) { + log("Skipping module %s as it contains memories (run 'memory' pass first).\n", module->name.c_str()); + return; + } + + ct.setup_internals(); + ct.setup_internals_mem(); + ct.setup_stdcells(); + ct.setup_stdcells_mem(); + + for (auto &it : module->wires) + it.second->attributes.erase("\\submod"); + + for (auto &it : module->cells) + { + RTLIL::Cell *cell = it.second; + if (cell->attributes.count("\\submod") == 0 || cell->attributes["\\submod"].str.size() == 0) { + cell->attributes.erase("\\submod"); + continue; + } + + std::string submod_str = cell->attributes["\\submod"].str; + cell->attributes.erase("\\submod"); + + if (submodules.count(submod_str) == 0) { + submodules[submod_str].name = submod_str; + submodules[submod_str].full_name = module->name + "_" + submod_str; + while (design->modules.count(submodules[submod_str].full_name) != 0 || + module->count_id(submodules[submod_str].full_name) != 0) + submodules[submod_str].full_name += "_"; + } + + submodules[submod_str].cells.insert(cell); + } + + for (auto &it : submodules) + handle_submodule(it.second); + } +}; + +struct SubmodPass : public Pass { + SubmodPass() : Pass("submod") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing SUBMOD pass (moving cells to submodes as requested).\n"); + log_push(); + + Pass::call(design, "opt_rmunused"); + log_header("Continuing SUBMOD pass.\n"); + + extra_args(args, 1, design); + + std::set<std::string> handled_modules; + + bool did_something = true; + while (did_something) { + did_something = false; + std::vector<std::string> queued_modules; + for (auto &mod_it : design->modules) + if (handled_modules.count(mod_it.first) == 0) + queued_modules.push_back(mod_it.first); + for (auto &modname : queued_modules) + if (design->modules.count(modname) != 0) { + SubmodWorker worker(design, design->modules[modname]); + handled_modules.insert(modname); + did_something = true; + } + } + + Pass::call(design, "opt_rmunused"); + } +} SubmodPass; + diff --git a/passes/techmap/Makefile.inc b/passes/techmap/Makefile.inc new file mode 100644 index 000000000..ba365525d --- /dev/null +++ b/passes/techmap/Makefile.inc @@ -0,0 +1,11 @@ + +GENFILES += passes/techmap/stdcells.inc +OBJS += passes/techmap/techmap.o + +passes/techmap/stdcells.inc: techlibs/stdcells.v + od -v -td1 -w1 $< | awk 'BEGIN { print "static char stdcells_code[] = {"; } $$2 != "" { print $$2 ","; } \ + END { print 0 "};"; }' | fmt > $@.new + mv $@.new $@ + +passes/techmap/techmap.o: passes/techmap/stdcells.inc + diff --git a/passes/techmap/techmap.cc b/passes/techmap/techmap.cc new file mode 100644 index 000000000..99fa15b92 --- /dev/null +++ b/passes/techmap/techmap.cc @@ -0,0 +1,207 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/register.h" +#include "kernel/log.h" +#include <stdlib.h> +#include <assert.h> +#include <stdio.h> +#include <string.h> + +#include "passes/techmap/stdcells.inc" + +static void apply_prefix(std::string prefix, std::string &id) +{ + if (id[0] == '\\') + id = prefix + "." + id.substr(1); + else + id = prefix + "." + id; +} + +static void apply_prefix(std::string prefix, RTLIL::SigSpec &sig, RTLIL::Module *module) +{ + for (size_t i = 0; i < sig.chunks.size(); i++) { + if (sig.chunks[i].wire == NULL) + continue; + std::string wire_name = sig.chunks[i].wire->name; + apply_prefix(prefix, wire_name); + assert(module->wires.count(wire_name) > 0); + sig.chunks[i].wire = module->wires[wire_name]; + } +} + +std::map<std::pair<RTLIL::IdString, std::map<RTLIL::IdString, RTLIL::Const>>, RTLIL::Module*> techmap_cache; + +static bool techmap_module(RTLIL::Module *module, RTLIL::Design *map) +{ + bool did_something = false; + + std::vector<std::string> cell_names; + + for (auto &cell_it : module->cells) + cell_names.push_back(cell_it.first); + + for (auto &cell_name : cell_names) + { + if (module->cells.count(cell_name) == 0) + continue; + + RTLIL::Cell *cell = module->cells[cell_name]; + + if (map->modules.count(cell->type) == 0) + continue; + + RTLIL::Module *tpl = map->modules[cell->type]; + std::pair<RTLIL::IdString, std::map<RTLIL::IdString, RTLIL::Const>> key(cell->type, cell->parameters); + + if (techmap_cache.count(key) > 0) { + tpl = techmap_cache[key]; + } else { + std::string derived_name = cell->type; + if (cell->parameters.size() != 0) { + derived_name = tpl->derive(map, cell->parameters); + tpl = map->modules[derived_name]; + log_header("Continuing TECHMAP pass.\n"); + } + for (auto &cit : tpl->cells) + if (cit.second->type == "\\TECHMAP_FAILED") { + log("Not using module `%s' from techmap as it contains a TECHMAP_FAILED marker cell.\n", derived_name.c_str()); + tpl = NULL; + break; + } + techmap_cache[key] = tpl; + } + + if (tpl == NULL) + goto next_cell; + + log("Mapping `%s.%s' using `%s'.\n", module->name.c_str(), cell_name.c_str(), tpl->name.c_str()); + + if (tpl->memories.size() != 0) + log_error("Technology map yielded memories -> this is not supported."); + + if (tpl->processes.size() != 0) + log_error("Technology map yielded processes -> this is not supported."); + + for (auto &it : tpl->wires) { + RTLIL::Wire *w = new RTLIL::Wire(*it.second); + apply_prefix(cell_name, w->name); + w->port_input = false; + w->port_output = false; + w->port_id = 0; + module->wires[w->name] = w; + } + + for (auto &it : tpl->cells) { + RTLIL::Cell *c = new RTLIL::Cell(*it.second); + if (c->type.substr(0, 2) == "\\$") + c->type = c->type.substr(1); + apply_prefix(cell_name, c->name); + for (auto &it2 : c->connections) + apply_prefix(cell_name, it2.second, module); + module->cells[c->name] = c; + } + + for (auto &it : tpl->connections) { + RTLIL::SigSig c = it; + apply_prefix(cell_name, c.first, module); + apply_prefix(cell_name, c.second, module); + module->connections.push_back(c); + } + + for (auto &it : cell->connections) { + assert(tpl->wires.count(it.first)); + assert(tpl->wires[it.first]->port_id > 0); + RTLIL::Wire *w = tpl->wires[it.first]; + RTLIL::SigSig c; + if (w->port_output) { + c.first = it.second; + c.second = RTLIL::SigSpec(w); + apply_prefix(cell_name, c.second, module); + } else { + c.first = RTLIL::SigSpec(w); + c.second = it.second; + apply_prefix(cell_name, c.first, module); + } + if (c.second.width > c.first.width) + c.second.remove(c.first.width, c.second.width - c.first.width); + if (c.second.width < c.first.width) + c.second.append(RTLIL::SigSpec(RTLIL::State::S0, c.first.width - c.second.width)); + assert(c.first.width == c.second.width); + module->connections.push_back(c); + } + + delete cell; + module->cells.erase(cell_name); + did_something = true; + next_cell:; + } + + return did_something; +} + +struct TechmapPass : public Pass { + TechmapPass() : Pass("techmap") { } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + log_header("Executing TECHMAP pass (map to technology primitives).\n"); + log_push(); + + std::string filename; + + size_t argidx; + for (argidx = 1; argidx < args.size(); argidx++) { + if (args[argidx] == "-map" && argidx+1 < args.size()) { + filename = args[++argidx]; + continue; + } + break; + } + extra_args(args, argidx, design); + + RTLIL::Design *map = new RTLIL::Design; + FILE *f = filename.empty() ? fmemopen(stdcells_code, strlen(stdcells_code), "rt") : fopen(filename.c_str(), "rt"); + if (f == NULL) + log_error("Can't open map file `%s'\n", filename.c_str()); + Frontend::frontend_call(map, f, filename.empty() ? "<stdcells.v>" : filename, "verilog"); + fclose(f); + + std::map<RTLIL::IdString, RTLIL::Module*> modules_new; + for (auto &it : map->modules) { + if (it.first.substr(0, 2) == "\\$") + it.second->name = it.first.substr(1); + modules_new[it.second->name] = it.second; + } + map->modules.swap(modules_new); + + bool did_something = true; + while (did_something) { + did_something = false; + for (auto &mod_it : design->modules) + if (techmap_module(mod_it.second, map)) + did_something = true; + } + + log("No more expansions possible.\n"); + techmap_cache.clear(); + delete map; + log_pop(); + } +} TechmapPass; + |