diff options
Diffstat (limited to 'passes/cmds')
| -rw-r--r-- | passes/cmds/Makefile.inc | 3 | ||||
| -rw-r--r-- | passes/cmds/edgetypes.cc | 106 | ||||
| -rw-r--r-- | passes/cmds/plugin.cc | 2 | ||||
| -rw-r--r-- | passes/cmds/qwp.cc | 840 | ||||
| -rw-r--r-- | passes/cmds/scc.cc | 4 | ||||
| -rw-r--r-- | passes/cmds/show.cc | 2 | ||||
| -rw-r--r-- | passes/cmds/splice.cc | 2 | ||||
| -rw-r--r-- | passes/cmds/splitnets.cc | 25 | ||||
| -rw-r--r-- | passes/cmds/stat.cc | 4 | ||||
| -rw-r--r-- | passes/cmds/torder.cc | 123 |
10 files changed, 1097 insertions, 14 deletions
diff --git a/passes/cmds/Makefile.inc b/passes/cmds/Makefile.inc index e4b40c41c..01ada7739 100644 --- a/passes/cmds/Makefile.inc +++ b/passes/cmds/Makefile.inc @@ -14,6 +14,7 @@ OBJS += passes/cmds/setattr.o OBJS += passes/cmds/copy.o OBJS += passes/cmds/splice.o OBJS += passes/cmds/scc.o +OBJS += passes/cmds/torder.o OBJS += passes/cmds/logcmd.o OBJS += passes/cmds/tee.o OBJS += passes/cmds/write_file.o @@ -22,4 +23,6 @@ OBJS += passes/cmds/cover.o OBJS += passes/cmds/trace.o OBJS += passes/cmds/plugin.o OBJS += passes/cmds/check.o +OBJS += passes/cmds/qwp.o +OBJS += passes/cmds/edgetypes.o diff --git a/passes/cmds/edgetypes.cc b/passes/cmds/edgetypes.cc new file mode 100644 index 000000000..7b75a009f --- /dev/null +++ b/passes/cmds/edgetypes.cc @@ -0,0 +1,106 @@ +/* + * 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/yosys.h" +#include "kernel/sigtools.h" + +USING_YOSYS_NAMESPACE +PRIVATE_NAMESPACE_BEGIN + +struct EdgetypePass : public Pass { + EdgetypePass() : Pass("edgetypes", "list all types of edges in selection") { } + virtual void help() + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" edgetypes [options] [selection]\n"); + log("\n"); + log("This command lists all unique types of 'edges' found in the selection. An 'edge'\n"); + log("is a 4-tuple of source and sink cell type and port name.\n"); + log("\n"); + } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + size_t argidx; + for (argidx = 1; argidx < args.size(); argidx++) { + // if (args[argidx] == "-ltr") { + // config.ltr = true; + // continue; + // } + break; + } + extra_args(args, argidx, design); + + pool<string> edge_cache; + + for (auto module : design->selected_modules()) + { + SigMap sigmap(module); + dict<SigBit, pool<tuple<IdString, IdString, int>>> bit_sources, bit_sinks; + pool<std::pair<IdString, IdString>> multibit_ports; + + for (auto cell : module->selected_cells()) + for (auto conn : cell->connections()) + { + IdString cell_type = cell->type; + IdString port_name = conn.first; + SigSpec sig = sigmap(conn.second); + + if (GetSize(sig) > 1) + multibit_ports.insert(std::pair<IdString, IdString>(cell_type, port_name)); + + for (int i = 0; i < GetSize(sig); i++) { + if (cell->output(port_name)) + bit_sources[sig[i]].insert(tuple<IdString, IdString, int>(cell_type, port_name, i)); + if (cell->input(port_name)) + bit_sinks[sig[i]].insert(tuple<IdString, IdString, int>(cell_type, port_name, i)); + } + } + + for (auto &it : bit_sources) + for (auto &source : it.second) + for (auto &sink : bit_sinks[it.first]) + { + auto source_cell_type = std::get<0>(source); + auto source_port_name = std::get<1>(source); + auto source_bit_index = std::get<2>(source); + + auto sink_cell_type = std::get<0>(sink); + auto sink_port_name = std::get<1>(sink); + auto sink_bit_index = std::get<2>(sink); + + string source_str = multibit_ports.count(std::pair<IdString, IdString>(source_cell_type, source_port_name)) ? + stringf("%s.%s[%d]", log_id(source_cell_type), log_id(source_port_name), source_bit_index) : + stringf("%s.%s", log_id(source_cell_type), log_id(source_port_name)); + + string sink_str = multibit_ports.count(std::pair<IdString, IdString>(sink_cell_type, sink_port_name)) ? + stringf("%s.%s[%d]", log_id(sink_cell_type), log_id(sink_port_name), sink_bit_index) : + stringf("%s.%s", log_id(sink_cell_type), log_id(sink_port_name)); + + edge_cache.insert(source_str + " " + sink_str); + } + } + + edge_cache.sort(); + for (auto &str : edge_cache) + log("%s\n", str.c_str()); + } +} EdgetypePass; + +PRIVATE_NAMESPACE_END diff --git a/passes/cmds/plugin.cc b/passes/cmds/plugin.cc index f7c65bbde..e2d80d9bf 100644 --- a/passes/cmds/plugin.cc +++ b/passes/cmds/plugin.cc @@ -115,7 +115,7 @@ struct PluginPass : public Pass { log("\n"); int max_alias_len = 1; for (auto &it : loaded_plugin_aliases) - max_alias_len = std::max(max_alias_len, GetSize(it.first)); + max_alias_len = max(max_alias_len, GetSize(it.first)); for (auto &it : loaded_plugin_aliases) log("Alias: %-*s %s\n", max_alias_len, it.first.c_str(), it.second.c_str()); } diff --git a/passes/cmds/qwp.cc b/passes/cmds/qwp.cc new file mode 100644 index 000000000..8ec815a72 --- /dev/null +++ b/passes/cmds/qwp.cc @@ -0,0 +1,840 @@ +/* + * 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/yosys.h" +#include "kernel/sigtools.h" + +#undef LOG_MATRICES +#undef PYPLOT_EDGES + +USING_YOSYS_NAMESPACE +PRIVATE_NAMESPACE_BEGIN + +static uint32_t xorshift32_state; + +static double xorshift32() +{ + xorshift32_state ^= xorshift32_state << 13; + xorshift32_state ^= xorshift32_state >> 17; + xorshift32_state ^= xorshift32_state << 5; + return (xorshift32_state % 1000000) / 1e6; +} + +struct QwpConfig +{ + bool ltr; + bool alpha; + double grid; + + std::ofstream dump_file; + + QwpConfig() { + ltr = false; + alpha = false; + grid = 1.0 / 16; + } +}; + +struct QwpWorker +{ + QwpConfig &config; + Module *module; + char direction; + + struct Node { + Cell *cell; + bool tied, alt_tied; + + // pos = position in current direction + // alt_pos = position in the other direction + double pos, alt_pos; + + Node() { + cell = nullptr; + tied = false; + pos = xorshift32(); + alt_tied = false; + alt_pos = xorshift32(); + } + + void tie(double v) { + tied = true; + pos = v; + } + + void alt_tie(double v) { + alt_tied = true; + alt_pos = v; + } + + void swap_alt() { + std::swap(tied, alt_tied); + std::swap(pos, alt_pos); + } + + void proj_left(double midpos) { + cell = nullptr; + tie(pos > midpos ? midpos : pos); + } + + void proj_right(double midpos) { + cell = nullptr; + tie(pos < midpos ? midpos : pos); + } + }; + + vector<Node> nodes; + dict<pair<int, int>, double> edges; + dict<Cell*, int> cell_to_node; + + // worker state variables + double midpos; + double radius; + double alt_midpos; + double alt_radius; + + QwpWorker(QwpConfig &config, Module *module, char direction = 'x') : config(config), module(module), direction(direction) + { + log_assert(direction == 'x' || direction == 'y'); + } + + void load_module() + { + log_assert(direction == 'x'); + + SigMap sigmap(module); + dict<SigBit, pool<int>> bits_to_nodes; + + if (config.ltr || config.alpha) + { + dict<Wire*, double> alpha_inputs, alpha_outputs; + + if (config.alpha) + { + dict<string, Wire*> alpha_order; + + for (auto wire : module->wires()) { + if (wire->port_input || wire->port_output) + alpha_order[wire->name.str()] = wire; + } + + alpha_order.sort(); + + for (auto &it : alpha_order) { + if (it.second->port_input) { + int idx = GetSize(alpha_inputs); + alpha_inputs[it.second] = idx + 0.5; + } + if (it.second->port_output) { + int idx = GetSize(alpha_outputs); + alpha_outputs[it.second] = idx + 0.5; + } + } + } + + for (auto wire : module->wires()) + { + if (!wire->port_input && !wire->port_output) + continue; + + int idx = GetSize(nodes); + nodes.push_back(Node()); + + if (config.ltr) { + if (wire->port_input) + nodes[idx].tie(0.0); + else + nodes[idx].tie(1.0); + } + + if (config.alpha) { + if (wire->port_input) + nodes[idx].alt_tie(alpha_inputs.at(wire) / GetSize(alpha_inputs)); + else + nodes[idx].alt_tie(alpha_outputs.at(wire) / GetSize(alpha_outputs)); + } + + for (auto bit : sigmap(wire)) + bits_to_nodes[bit].insert(idx); + } + } + + for (auto cell : module->selected_cells()) + { + log_assert(cell_to_node.count(cell) == 0); + int idx = GetSize(nodes); + nodes.push_back(Node()); + + cell_to_node[cell] = GetSize(nodes); + nodes[idx].cell = cell; + + for (auto &conn : cell->connections()) + for (auto bit : sigmap(conn.second)) + bits_to_nodes[bit].insert(idx); + } + + for (auto &it : bits_to_nodes) + { + if (GetSize(it.second) > 100) + continue; + + for (int idx1 : it.second) + for (int idx2 : it.second) + if (idx1 < idx2) + edges[pair<int, int>(idx1, idx2)] += 1.0 / GetSize(it.second); + } + } + + void solve(bool alt_mode = false) + { + // A := constraint_matrix + // y := constraint_rhs_vector + // + // AA = A' * A + // Ay = A' * y + // + // M := [AA Ay] + + // Row major order + int N = GetSize(nodes), N1 = N+1; + vector<double> M(N * N1); + + // Edge constraints: + // A[i,:] := [ 0 0 .... 0 weight 0 ... 0 -weight 0 ... 0 0], y[i] := 0 + // + // i.e. nonzero columns in A[i,:] at the two node indices. + for (auto &edge : edges) + { + int idx1 = edge.first.first; + int idx2 = edge.first.second; + double weight = edge.second * (1.0 + xorshift32() * 1e-3); + + M[idx1 + idx1*N1] += weight * weight; + M[idx2 + idx2*N1] += weight * weight; + + M[idx1 + idx2*N1] += -weight * weight; + M[idx2 + idx1*N1] += -weight * weight; + } + + // Node constraints: + // A[i,:] := [ 0 0 .... 0 weight 0 ... 0 0], y[i] := weight * pos + // + // i.e. nonzero column in A[i,:] at the node index + // + // "tied" nodes have a large weight, pinning them in position. Untied + // nodes have a small weight, giving then a tiny preference to stay at + // the current position, making sure that AA never is singular. + for (int idx = 0; idx < GetSize(nodes); idx++) + { + auto &node = nodes[idx]; + double rhs = (alt_mode ? node.alt_pos : node.pos); + + double weight = 1e-3; + if (alt_mode ? node.alt_tied : node.tied) + weight = 1e3; + weight *= (1.0 + xorshift32() * 1e-3); + + M[idx + idx*N1] += weight * weight; + M[N + idx*N1] += rhs * weight * weight; + } + +#ifdef LOG_MATRICES + log("\n"); + for (int i = 0; i < N; i++) { + for (int j = 0; j < N+1; j++) + log(" %10.2e", M[(N+1)*i + j]); + log("\n"); + } +#endif + + // Solve "AA*x = Ay" + // (least squares fit for "A*x = y") + // + // Using gaussian elimination to get M := [Id x] + + vector<int> pivot_cache; + vector<int> queue; + + for (int i = 0; i < N; i++) + queue.push_back(i); + + // gaussian elimination + for (int i = 0; i < N; i++) + { + // find best row + int best_row = queue.front(); + int best_row_queue_idx = 0; + double best_row_absval = 0; + + for (int k = 0; k < GetSize(queue); k++) { + int row = queue[k]; + double absval = fabs(M[i + row*N1]); + if (absval > best_row_absval) { + best_row = row; + best_row_queue_idx = k; + best_row_absval = absval; + } + } + + int row = best_row; + pivot_cache.push_back(row); + + queue[best_row_queue_idx] = queue.back(); + queue.pop_back(); + + // normalize row + for (int k = i+1; k < N1; k++) + M[k + row*N1] /= M[i + row*N1]; + M[i + row*N1] = 1.0; + + // elimination + for (int other_row : queue) { + double d = M[i + other_row*N1]; + for (int k = i+1; k < N1; k++) + M[k + other_row*N1] -= d*M[k + row*N1]; + M[i + other_row*N1] = 0.0; + } + } + + log_assert(queue.empty()); + log_assert(GetSize(pivot_cache) == N); + + // back substitution + for (int i = N-1; i >= 0; i--) + for (int j = i+1; j < N; j++) + { + int row = pivot_cache[i]; + int other_row = pivot_cache[j]; + M[N + row*N1] -= M[j + row*N1] * M[N + other_row*N1]; + M[j + row*N1] = 0.0; + } + +#ifdef LOG_MATRICES + log("\n"); + for (int i = 0; i < N; i++) { + for (int j = 0; j < N+1; j++) + log(" %10.2e", M[(N+1)*i + j]); + log("\n"); + } +#endif + + // update node positions + for (int i = 0; i < N; i++) + { + double v = M[(N+1)*i + N]; + double c = alt_mode ? alt_midpos : midpos; + double r = alt_mode ? alt_radius : radius; + + if (std::isfinite(v)) { + v = min(v, c+r); + v = max(v, c-r); + } else { + v = c; + } + + if (alt_mode) { + if (!nodes[i].alt_tied) + nodes[i].alt_pos = v; + } else { + if (!nodes[i].tied) + nodes[i].pos = v; + } + } + } + + void log_cell_coordinates(int indent, bool log_all_nodes = false) + { + for (auto &node : nodes) + { + if (node.cell == nullptr && !log_all_nodes) + continue; + + for (int i = 0; i < indent; i++) + log(" "); + + if (direction == 'x') + log("X=%.2f, Y=%.2f", node.pos, node.alt_pos); + else + log("X=%.2f, Y=%.2f", node.alt_pos, node.pos); + + if (node.tied) + log(" [%c-tied]", direction); + + if (node.alt_tied) + log(" [%c-tied]", direction == 'x' ? 'y' : 'x'); + + if (node.cell != nullptr) + log(" %s (%s)", log_id(node.cell), log_id(node.cell->type)); + else + log(" (none)"); + + log("\n"); + } + } + + void dump_svg(const pool<int> *green_nodes = nullptr, double median = -1) + { + double x_center = direction == 'x' ? midpos : alt_midpos; + double y_center = direction == 'y' ? midpos : alt_midpos; + + double x_radius = direction == 'x' ? radius : alt_radius; + double y_radius = direction == 'y' ? radius : alt_radius; + + config.dump_file << stringf("<svg height=\"240\" width=\"470\">\n"); + config.dump_file << stringf("<rect x=\"0\" y=\"0\" width=\"470\" height=\"240\" style=\"fill:rgb(250,250,200);\" />\n"); + config.dump_file << stringf("<rect x=\"20\" y=\"20\" width=\"200\" height=\"200\" style=\"fill:rgb(200,200,200);\" />\n"); + config.dump_file << stringf("<rect x=\"250\" y=\"20\" width=\"200\" height=\"200\" style=\"fill:rgb(200,200,200);\" />\n"); + + double win_x = 250 + 200 * (direction == 'x' ? midpos - radius : alt_midpos - alt_radius); + double win_y = 20 + 200 * (direction == 'y' ? midpos - radius : alt_midpos - alt_radius); + + double win_w = 200 * (direction == 'x' ? 2*radius : 2*alt_radius); + double win_h = 200 * (direction == 'y' ? 2*radius : 2*alt_radius); + + config.dump_file << stringf("<rect x=\"%.2f\" y=\"%.2f\" width=\"%.2f\" height=\"%.2f\" " + "style=\"stroke:rgb(0,0,0);stroke-width:1;fill:none\" />\n", win_x, win_y, win_w, win_h); + + if (median >= 0) + { + double x1 = 20.0, x2 = 220.0, y1 = 20.0, y2 = 220.0; + + if (direction == 'x') + x1 = x2 = 120 + 100 * (median - x_center) / x_radius; + else + y1 = y2 = 120 + 100 * (median - y_center) / y_radius; + + config.dump_file << stringf("<line x1=\"%.2f\" y1=\"%.2f\" x2=\"%.2f\" y2=\"%.2f\" " + "style=\"stroke:rgb(150,0,150);stroke-width:1\" />\n", x1, y1, x2, y2); + } + + for (auto &edge : edges) + { + auto &node1 = nodes[edge.first.first]; + auto &node2 = nodes[edge.first.second]; + + double x1 = direction == 'x' ? node1.pos : node1.alt_pos; + double y1 = direction == 'y' ? node1.pos : node1.alt_pos; + + double x2 = direction == 'x' ? node2.pos : node2.alt_pos; + double y2 = direction == 'y' ? node2.pos : node2.alt_pos; + + x1 = 120 + 100 * (x1 - x_center) / x_radius; + y1 = 120 + 100 * (y1 - y_center) / y_radius; + + x2 = 120 + 100 * (x2 - x_center) / x_radius; + y2 = 120 + 100 * (y2 - y_center) / y_radius; + + config.dump_file << stringf("<line x1=\"%.2f\" y1=\"%.2f\" x2=\"%.2f\" y2=\"%.2f\" " + "style=\"stroke:rgb(0,0,0);stroke-width:1\" />\n", x1, y1, x2, y2); + } + + for (int i = 0; i < GetSize(nodes); i++) + { + auto &node = nodes[i]; + + double x = direction == 'x' ? node.pos : node.alt_pos; + double y = direction == 'y' ? node.pos : node.alt_pos; + + x = 120 + 100 * (x - x_center) / x_radius; + y = 120 + 100 * (y - y_center) / y_radius; + + const char *color = node.cell == nullptr ? "blue" : "red"; + + if (green_nodes != nullptr && green_nodes->count(i)) + color = "green"; + + config.dump_file << stringf("<circle cx=\"%.2f\" cy=\"%.2f\" r=\"3\" fill=\"%s\"/>\n", x, y, color); + } + + config.dump_file << stringf("</svg>\n"); + } + + void run_worker(int indent) + { + int count_cells = 0; + + for (auto &node : nodes) + if (node.cell != nullptr) + count_cells++; + + for (int i = 0; i < indent; i++) + log(" "); + + string range_str; + + if (direction == 'x') + range_str = stringf("X=%.2f:%.2f, Y=%.2f:%.2f", + midpos - radius, midpos + radius, + alt_midpos - alt_radius, alt_midpos + alt_radius); + else + range_str = stringf("X=%.2f:%.2f, Y=%.2f:%.2f", + alt_midpos - alt_radius, alt_midpos + alt_radius, + midpos - radius, midpos + radius); + + log("%c-qwp on %s with %d cells, %d nodes, and %d edges.\n", direction, + range_str.c_str(), count_cells, GetSize(nodes), GetSize(edges)); + + solve(); + solve(true); + + // detect median position and check for break condition + + vector<pair<double, int>> sorted_pos; + for (int i = 0; i < GetSize(nodes); i++) + if (nodes[i].cell != nullptr) + sorted_pos.push_back(pair<double, int>(nodes[i].pos, i)); + + std::sort(sorted_pos.begin(), sorted_pos.end()); + int median_sidx = GetSize(sorted_pos)/2; + double median = sorted_pos[median_sidx].first; + + double left_scale = radius / (median - (midpos - radius)); + double right_scale = radius / ((midpos + radius) - median); + + if (config.dump_file.is_open()) + { + config.dump_file << stringf("<h4>LSQ %c-Solution for %s:</h4>\n", direction, range_str.c_str()); + + pool<int> green_nodes; + for (int i = 0; i < median_sidx; i++) + green_nodes.insert(sorted_pos[i].second); + + dump_svg(&green_nodes, median); + } + + for (auto &node : nodes) + { + double rel_pos = node.pos - median; + if (rel_pos < 0) { + node.pos = midpos + left_scale*rel_pos; + if (std::isfinite(node.pos)) { + node.pos = min(node.pos, midpos); + node.pos = max(node.pos, midpos - radius); + } else + node.pos = midpos - radius/2; + } else { + node.pos = midpos + right_scale*rel_pos; + if (std::isfinite(node.pos)) { + node.pos = max(node.pos, midpos); + node.pos = min(node.pos, midpos + radius); + } else + node.pos = midpos + radius/2; + } + } + + if (GetSize(sorted_pos) < 2 || (2*radius <= config.grid && 2*alt_radius <= config.grid)) { + log_cell_coordinates(indent + 1); + return; + } + + // create child workers + + char child_direction = direction == 'x' ? 'y' : 'x'; + + QwpWorker left_worker(config, module, child_direction); + QwpWorker right_worker(config, module, child_direction); + + // duplicate nodes into child workers + + dict<int, int> left_nodes, right_nodes; + + for (int k = 0; k < GetSize(sorted_pos); k++) + { + int i = sorted_pos[k].second; + + if (k < median_sidx) { + left_nodes[i] = GetSize(left_worker.nodes); + left_worker.nodes.push_back(nodes[i]); + if (left_worker.nodes.back().pos > midpos) + left_worker.nodes.back().pos = midpos; + left_worker.nodes.back().swap_alt(); + } else { + right_nodes[i] = GetSize(right_worker.nodes); + right_worker.nodes.push_back(nodes[i]); + if (right_worker.nodes.back().pos < midpos) + right_worker.nodes.back().pos = midpos; + right_worker.nodes.back().swap_alt(); + } + } + + // duplicate edges into child workers, project nodes as needed + + for (auto &edge : edges) + { + int idx1 = edge.first.first; + int idx2 = edge.first.second; + double weight = edge.second; + + if (nodes[idx1].cell == nullptr && nodes[idx2].cell == nullptr) + continue; + + int left_idx1 = left_nodes.count(idx1) ? left_nodes.at(idx1) : -1; + int left_idx2 = left_nodes.count(idx2) ? left_nodes.at(idx2) : -1; + + int right_idx1 = right_nodes.count(idx1) ? right_nodes.at(idx1) : -1; + int right_idx2 = right_nodes.count(idx2) ? right_nodes.at(idx2) : -1; + + if (left_idx1 >= 0 && left_worker.nodes[left_idx1].cell && left_idx2 < 0) { + left_idx2 = left_nodes[idx2] = GetSize(left_worker.nodes); + left_worker.nodes.push_back(nodes[idx2]); + left_worker.nodes.back().proj_left(midpos); + left_worker.nodes.back().swap_alt(); + } else + if (left_idx2 >= 0 && left_worker.nodes[left_idx2].cell && left_idx1 < 0) { + left_idx1 = left_nodes[idx1] = GetSize(left_worker.nodes); + left_worker.nodes.push_back(nodes[idx1]); + left_worker.nodes.back().proj_left(midpos); + left_worker.nodes.back().swap_alt(); + } + + if (right_idx1 >= 0 && right_worker.nodes[right_idx1].cell && right_idx2 < 0) { + right_idx2 = right_nodes[idx2] = GetSize(right_worker.nodes); + right_worker.nodes.push_back(nodes[idx2]); + right_worker.nodes.back().proj_right(midpos); + right_worker.nodes.back().swap_alt(); + } else + if (right_idx2 >= 0 && right_worker.nodes[right_idx2].cell && right_idx1 < 0) { + right_idx1 = right_nodes[idx1] = GetSize(right_worker.nodes); + right_worker.nodes.push_back(nodes[idx1]); + right_worker.nodes.back().proj_right(midpos); + right_worker.nodes.back().swap_alt(); + } + + if (left_idx1 >= 0 && left_idx2 >= 0) + left_worker.edges[pair<int, int>(left_idx1, left_idx2)] += weight; + + if (right_idx1 >= 0 && right_idx2 >= 0) + right_worker.edges[pair<int, int>(right_idx1, right_idx2)] += weight; + } + + // run child workers + + left_worker.midpos = right_worker.midpos = alt_midpos; + left_worker.radius = right_worker.radius = alt_radius; + + left_worker.alt_midpos = midpos - radius/2; + right_worker.alt_midpos = midpos + radius/2; + left_worker.alt_radius = right_worker.alt_radius = radius/2; + + left_worker.run_worker(indent+1); + right_worker.run_worker(indent+1); + + // re-integrate results + + for (auto &it : left_nodes) + if (left_worker.nodes[it.second].cell != nullptr) { + nodes[it.first].pos = left_worker.nodes[it.second].alt_pos; + nodes[it.first].alt_pos = left_worker.nodes[it.second].pos; + } + + for (auto &it : right_nodes) + if (right_worker.nodes[it.second].cell != nullptr) { + nodes[it.first].pos = right_worker.nodes[it.second].alt_pos; + nodes[it.first].alt_pos = right_worker.nodes[it.second].pos; + } + + if (config.dump_file.is_open()) { + config.dump_file << stringf("<h4>Final %c-Solution for %s:</h4>\n", direction, range_str.c_str()); + dump_svg(); + } + } + + void histogram(const vector<double> &values) + { + if (values.empty()) { + log("no data\n"); + return; + } + + double min_value = values.front(); + double max_value = values.front(); + + for (auto &v : values) { + min_value = min(min_value, v); + max_value = max(max_value, v); + } + + if (fabs(max_value - min_value) < 0.001) { + log("all values in range %f .. %f\n", min_value, max_value); + return; + } + + vector<int> buckets(60); + int max_bucket_val = 0; + + for (auto &v : values) { + int idx = min(int(GetSize(buckets) * (v - min_value) / (max_value - min_value)), GetSize(buckets)-1); + max_bucket_val = max(max_bucket_val, ++buckets.at(idx)); + } + + for (int i = 4; i >= 0; i--) { + for (int k = 0; k < GetSize(buckets); k++) { + int v = 10 * buckets[k] / max_bucket_val; + if (v >= 2*i+1) + log(v == 2*i+1 ? "." : ":"); + else + log(i == 0 ? (buckets[k] > 0 ? "," : "_") : " "); + } + log("\n"); + } + log("%-30f%30f\n", min_value, max_value); + } + + void run() + { + log("\n"); + log("Running qwp on module %s..\n", log_id(module)); + + if (config.dump_file.is_open()) + config.dump_file << stringf("<h3>QWP protocol for module %s:</h3>\n", log_id(module)); + + load_module(); + + midpos = 0.5; + radius = 0.5; + alt_midpos = 0.5; + alt_radius = 0.5; + run_worker(1); + + for (auto &node : nodes) + if (node.cell != nullptr) + node.cell->attributes["\\qwp_position"] = stringf("%f %f", node.pos, node.alt_pos); + + vector<double> edge_lengths; + vector<double> weighted_edge_lengths; + + double total_edge_length = 0; + double total_weighted_edge_length = 0; + + for (auto &edge : edges) + { + auto &node1 = nodes[edge.first.first]; + auto &node2 = nodes[edge.first.second]; + + double distance = sqrt(pow(node1.pos - node2.pos, 2) + pow(node1.alt_pos - node2.alt_pos, 2)); + double weighted_distance = distance * edge.second; + + edge_lengths.push_back(distance); + weighted_edge_lengths.push_back(weighted_distance); + + total_edge_length += distance; + total_weighted_edge_length += weighted_distance; + } + + log("\n"); + log("Summary for module %s:\n", log_id(module)); + log("Number of edges: %d\n", GetSize(edges)); + log("Total edge length: %f\n", total_edge_length); + log("Total weighted edge length: %f\n", total_weighted_edge_length); + + log("\n"); + log("Histogram over edge lengths:\n"); + histogram(edge_lengths); + + log("\n"); + log("Histogram over weighted edge lengths:\n"); + histogram(weighted_edge_lengths); + } +}; + +struct QwpPass : public Pass { + QwpPass() : Pass("qwp", "quadratic wirelength placer") { } + virtual void help() + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" qwp [options] [selection]\n"); + log("\n"); + log("This command runs quadratic wirelength placement on the selected modules and\n"); + log("annotates the cells in the design with 'qwp_position' attributes.\n"); + log("\n"); + log(" -ltr\n"); + log(" Add left-to-right constraints: constrain all inputs on the left border\n"); + log(" outputs to the right border.\n"); + log("\n"); + log(" -alpha\n"); + log(" Add constraints for inputs/outputs to be placed in alphanumerical\n"); + log(" order along the y-axis (top-to-bottom).\n"); + log("\n"); + log(" -grid N\n"); + log(" Number of grid divisions in x- and y-direction. (default=16)\n"); + log("\n"); + log(" -dump <html_file_name>\n"); + log(" Dump a protocol of the placement algorithm to the html file.\n"); + log("\n"); + log("Note: This implementation of a quadratic wirelength placer uses exact\n"); + log("dense matrix operations. It is only a toy-placer for small circuits.\n"); + log("\n"); + } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + QwpConfig config; + xorshift32_state = 123456789; + + log_header("Executing QWP pass (quadratic wirelength placer).\n"); + + size_t argidx; + for (argidx = 1; argidx < args.size(); argidx++) { + if (args[argidx] == "-ltr") { + config.ltr = true; + continue; + } + if (args[argidx] == "-alpha") { + config.alpha = true; + continue; + } + if (args[argidx] == "-grid" && argidx+1 < args.size()) { + config.grid = 1.0 / atoi(args[++argidx].c_str()); + continue; + } + if (args[argidx] == "-dump" && argidx+1 < args.size()) { + config.dump_file.open(args[++argidx], std::ofstream::trunc); + continue; + } + break; + } + extra_args(args, argidx, design); + + for (auto module : design->selected_modules()) + { + QwpWorker worker(config, module); + worker.run(); + +#ifdef PYPLOT_EDGES + log("\n"); + log("plt.figure(figsize=(10, 10));\n"); + + for (auto &edge : worker.edges) { + log("plt.plot([%.2f, %.2f], [%.2f, %.2f], \"r-\");\n", + worker.nodes[edge.first.first].pos, + worker.nodes[edge.first.second].pos, + worker.nodes[edge.first.first].alt_pos, + worker.nodes[edge.first.second].alt_pos); + } + + for (auto &node : worker.nodes) { + const char *style = node.cell != nullptr ? "ko" : "ks"; + log("plt.plot([%.2f], [%.2f], \"%s\");\n", node.pos, node.alt_pos, style); + } +#endif + } + } +} QwpPass; + +PRIVATE_NAMESPACE_END diff --git a/passes/cmds/scc.cc b/passes/cmds/scc.cc index 43a43b4fc..532026f26 100644 --- a/passes/cmds/scc.cc +++ b/passes/cmds/scc.cc @@ -69,10 +69,10 @@ struct SccWorker for (auto nextCell : cellToNextCell[cell]) if (cellLabels.count(nextCell) == 0) { run(nextCell, depth+1, maxDepth); - cellLabels[cell].second = std::min(cellLabels[cell].second, cellLabels[nextCell].second); + cellLabels[cell].second = min(cellLabels[cell].second, cellLabels[nextCell].second); } else if (cellsOnStack.count(nextCell) > 0 && (maxDepth < 0 || cellDepth[nextCell] + maxDepth > depth)) { - cellLabels[cell].second = std::min(cellLabels[cell].second, cellLabels[nextCell].second); + cellLabels[cell].second = min(cellLabels[cell].second, cellLabels[nextCell].second); } if (cellLabels[cell].first == cellLabels[cell].second) diff --git a/passes/cmds/show.cc b/passes/cmds/show.cc index 3035e7301..3b03d6802 100644 --- a/passes/cmds/show.cc +++ b/passes/cmds/show.cc @@ -552,7 +552,7 @@ struct ShowWorker continue; if (design->selected_whole_module(module->name)) { if (module->get_bool_attribute("\\blackbox")) { - log("Skipping blackbox module %s.\n", id2cstr(module->name)); + // log("Skipping blackbox module %s.\n", id2cstr(module->name)); continue; } else if (module->cells_.empty() && module->connections().empty() && module->processes.empty()) { diff --git a/passes/cmds/splice.cc b/passes/cmds/splice.cc index 4ce2ec11c..2556fb740 100644 --- a/passes/cmds/splice.cc +++ b/passes/cmds/splice.cc @@ -64,7 +64,7 @@ struct SpliceWorker return sliced_signals_cache.at(sig); int offset = 0; - int p = driven_bits_map.at(sig.extract(0, 1).to_single_sigbit()) - 1; + int p = driven_bits_map.at(sig.extract(0, 1).as_bit()) - 1; while (driven_bits.at(p) != RTLIL::State::Sm) p--, offset++; diff --git a/passes/cmds/splitnets.cc b/passes/cmds/splitnets.cc index 3cd857f41..a64c48791 100644 --- a/passes/cmds/splitnets.cc +++ b/passes/cmds/splitnets.cc @@ -50,7 +50,7 @@ struct SplitnetsWorker new_wire_name += format.substr(1, 1); RTLIL::Wire *new_wire = module->addWire(module->uniquify(new_wire_name), width); - new_wire->port_id = wire->port_id; + new_wire->port_id = wire->port_id ? wire->port_id + offset : 0; new_wire->port_input = wire->port_input; new_wire->port_output = wire->port_output; @@ -130,14 +130,24 @@ struct SplitnetsPass : public Pass { } extra_args(args, argidx, design); - for (auto &mod_it : design->modules_) + for (auto module : design->selected_modules()) { - RTLIL::Module *module = mod_it.second; - if (!design->selected(module)) - continue; - SplitnetsWorker worker; + if (flag_ports) + { + int normalized_port_factor = 0; + + for (auto wire : module->wires()) + if (wire->port_id != 0) { + normalized_port_factor = max(normalized_port_factor, wire->port_id+1); + normalized_port_factor = max(normalized_port_factor, GetSize(wire)+1); + } + + for (auto wire : module->wires()) + wire->port_id *= normalized_port_factor; + } + if (flag_driver) { CellTypes ct(design); @@ -194,7 +204,8 @@ struct SplitnetsPass : public Pass { delete_wires.insert(it.first); module->remove(delete_wires); - module->fixup_ports(); + if (flag_ports) + module->fixup_ports(); } } } SplitnetsPass; diff --git a/passes/cmds/stat.cc b/passes/cmds/stat.cc index 0aa76467f..af56a9e20 100644 --- a/passes/cmds/stat.cc +++ b/passes/cmds/stat.cc @@ -110,7 +110,7 @@ struct statdata_t int width_a = it.second->hasPort("\\A") ? GetSize(it.second->getPort("\\A")) : 0; int width_b = it.second->hasPort("\\B") ? GetSize(it.second->getPort("\\B")) : 0; int width_y = it.second->hasPort("\\Y") ? GetSize(it.second->getPort("\\Y")) : 0; - cell_type = stringf("%s_%d", cell_type.c_str(), std::max<int>({width_a, width_b, width_y})); + cell_type = stringf("%s_%d", cell_type.c_str(), max<int>({width_a, width_b, width_y})); } else if (cell_type.in("$mux", "$pmux")) cell_type = stringf("%s_%d", cell_type.c_str(), GetSize(it.second->getPort("\\Y"))); @@ -223,7 +223,7 @@ struct StatPass : public Pass { data.log_data(); } - if (top_mod != NULL) + if (top_mod != NULL && GetSize(mod_stat) > 1) { log("\n"); log("=== design hierarchy ===\n"); diff --git a/passes/cmds/torder.cc b/passes/cmds/torder.cc new file mode 100644 index 000000000..50317c023 --- /dev/null +++ b/passes/cmds/torder.cc @@ -0,0 +1,123 @@ +/* + * 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/yosys.h" +#include "kernel/celltypes.h" +#include "kernel/sigtools.h" +#include "kernel/utils.h" + +USING_YOSYS_NAMESPACE +PRIVATE_NAMESPACE_BEGIN + +struct TorderPass : public Pass { + TorderPass() : Pass("torder", "print cells in topological order") { } + virtual void help() + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" torder [options] [selection]\n"); + log("\n"); + log("This command prints the selected cells in topological order.\n"); + log("\n"); + log(" -stop <cell_type> <cell_port>\n"); + log(" do not use the specified cell port in topological sorting\n"); + log("\n"); + log(" -noautostop\n"); + log(" by default Q outputs of internal FF cells and memory read port outputs\n"); + log(" are not used in topological sorting. this option deactivates that.\n"); + log("\n"); + } + virtual void execute(std::vector<std::string> args, RTLIL::Design *design) + { + bool noautostop = false; + dict<IdString, pool<IdString>> stop_db; + + log_header("Executing TORDER pass (print cells in topological order).\n"); + + size_t argidx; + for (argidx = 1; argidx < args.size(); argidx++) { + if (args[argidx] == "-stop" && argidx+2 < args.size()) { + IdString cell_type = RTLIL::escape_id(args[++argidx]); + IdString cell_port = RTLIL::escape_id(args[++argidx]); + stop_db[cell_type].insert(cell_port); + continue; + } + if (args[argidx] == "-noautostop") { + noautostop = true; + continue; + } + break; + } + extra_args(args, argidx, design); + + for (auto module : design->selected_modules()) + { + log("module %s\n", log_id(module)); + + SigMap sigmap(module); + dict<SigBit, pool<IdString>> bit_drivers, bit_users; + TopoSort<IdString, RTLIL::sort_by_id_str> toposort; + + for (auto cell : module->selected_cells()) + for (auto conn : cell->connections()) + { + if (stop_db.count(cell->type) && stop_db.at(cell->type).count(conn.first)) + continue; + + if (!noautostop && yosys_celltypes.cell_known(cell->type)) { + if (conn.first.in("\\Q", "\\CTRL_OUT", "\\RD_DATA")) + continue; + if (cell->type == "$memrd" && conn.first == "\\DATA") + continue; + } + + if (cell->input(conn.first)) + for (auto bit : sigmap(conn.second)) + bit_users[bit].insert(cell->name); + + if (cell->output(conn.first)) + for (auto bit : sigmap(conn.second)) + bit_drivers[bit].insert(cell->name); + + toposort.node(cell->name); + } + + for (auto &it : bit_users) + if (bit_drivers.count(it.first)) + for (auto driver_cell : bit_drivers.at(it.first)) + for (auto user_cell : it.second) + toposort.edge(driver_cell, user_cell); + + toposort.analyze_loops = true; + toposort.sort(); + + for (auto &it : toposort.loops) { + log(" loop"); + for (auto cell : it) + log(" %s", log_id(cell)); + log("\n"); + } + + for (auto cell : toposort.sorted) + log(" cell %s\n", log_id(cell)); + } + } +} TorderPass; + +PRIVATE_NAMESPACE_END |