diff options
26 files changed, 1110 insertions, 1 deletions
@@ -686,6 +686,7 @@ test: $(TARGETS) $(EXTRA_TARGETS) +cd tests/asicworld && bash run-test.sh $(SEEDOPT) # +cd tests/realmath && bash run-test.sh $(SEEDOPT) +cd tests/share && bash run-test.sh $(SEEDOPT) + +cd tests/opt_share && bash run-test.sh $(SEEDOPT) +cd tests/fsm && bash run-test.sh $(SEEDOPT) +cd tests/techmap && bash run-test.sh +cd tests/memories && bash run-test.sh $(ABCOPT) $(SEEDOPT) diff --git a/passes/opt/Makefile.inc b/passes/opt/Makefile.inc index ea3646330..eb07e9452 100644 --- a/passes/opt/Makefile.inc +++ b/passes/opt/Makefile.inc @@ -4,6 +4,7 @@ OBJS += passes/opt/opt_merge.o OBJS += passes/opt/opt_muxtree.o OBJS += passes/opt/opt_reduce.o OBJS += passes/opt/opt_rmdff.o +OBJS += passes/opt/opt_share.o OBJS += passes/opt/opt_clean.o OBJS += passes/opt/opt_expr.o @@ -16,4 +17,3 @@ OBJS += passes/opt/opt_lut.o OBJS += passes/opt/pmux2shiftx.o OBJS += passes/opt/muxpack.o endif - diff --git a/passes/opt/opt_share.cc b/passes/opt/opt_share.cc new file mode 100644 index 000000000..a2ec9cc37 --- /dev/null +++ b/passes/opt/opt_share.cc @@ -0,0 +1,657 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * 2019 Bogdan Vukobratovic <bogdan.vukobratovic@gmail.com> + * + * 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/rtlil.h" +#include "kernel/sigtools.h" +#include <algorithm> + +#include <stdio.h> +#include <stdlib.h> + +USING_YOSYS_NAMESPACE +PRIVATE_NAMESPACE_BEGIN + +SigMap assign_map; + +struct OpMuxConn { + RTLIL::SigSpec sig; + RTLIL::Cell *mux; + RTLIL::Cell *op; + int mux_port_id; + int mux_port_offset; + int op_outsig_offset; + + bool operator<(const OpMuxConn &other) const + { + if (mux != other.mux) + return mux < other.mux; + + if (mux_port_id != other.mux_port_id) + return mux_port_id < other.mux_port_id; + + return mux_port_offset < other.mux_port_offset; + } +}; + +// Helper class to track additiona information about a SigSpec, like whether it is signed and the semantics of the port it is connected to +struct ExtSigSpec { + RTLIL::SigSpec sig; + RTLIL::SigSpec sign; + bool is_signed; + RTLIL::IdString semantics; + + ExtSigSpec() {} + + ExtSigSpec(RTLIL::SigSpec s, RTLIL::SigSpec sign = RTLIL::Const(0, 1), bool is_signed = false, RTLIL::IdString semantics = RTLIL::IdString()) : sig(s), sign(sign), is_signed(is_signed), semantics(semantics) {} + + bool empty() const { return sig.empty(); } + + bool operator<(const ExtSigSpec &other) const + { + if (sig != other.sig) + return sig < other.sig; + + if (sign != other.sign) + return sign < other.sign; + + if (is_signed != other.is_signed) + return is_signed < other.is_signed; + + return semantics < other.semantics; + } + + bool operator==(const RTLIL::SigSpec &other) const { return (sign != RTLIL::Const(0, 1)) ? false : sig == other; } + bool operator==(const ExtSigSpec &other) const { return is_signed == other.is_signed && sign == other.sign && sig == other.sig && semantics == other.semantics; } +}; + +#define BITWISE_OPS "$_AND_", "$_NAND_", "$_OR_", "$_NOR_", "$_XOR_", "$_XNOR_", "$_ANDNOT_", "$_ORNOT_", "$and", "$or", "$xor", "$xnor" + +#define REDUCTION_OPS "$reduce_and", "$reduce_or", "$reduce_xor", "$reduce_xnor", "$reduce_bool", "$reduce_nand" + +#define LOGICAL_OPS "$logic_and", "$logic_or" + +#define SHIFT_OPS "$shl", "$shr", "$sshl", "$sshr", "$shift", "$shiftx" + +#define RELATIONAL_OPS "$lt", "$le", "$eq", "$ne", "$eqx", "$nex", "$ge", "$gt" + +bool cell_supported(RTLIL::Cell *cell) +{ + + if (cell->type.in("$alu")) { + RTLIL::SigSpec sig_bi = cell->getPort("\\BI"); + RTLIL::SigSpec sig_ci = cell->getPort("\\CI"); + + if (sig_bi.is_fully_const() && sig_ci.is_fully_const() && sig_bi == sig_ci) + return true; + } else if (cell->type.in(LOGICAL_OPS, SHIFT_OPS, BITWISE_OPS, RELATIONAL_OPS, "$add", "$sub", "$mul", "$div", "$mod", "$concat")) { + return true; + } + + return false; +} + +std::map<std::string, std::string> mergeable_type_map{ + {"$sub", "$add"}, +}; + +bool mergeable(RTLIL::Cell *a, RTLIL::Cell *b) +{ + auto a_type = a->type; + if (mergeable_type_map.count(a_type.str())) + a_type = mergeable_type_map.at(a_type.str()); + + auto b_type = b->type; + if (mergeable_type_map.count(b_type.str())) + b_type = mergeable_type_map.at(b_type.str()); + + return a_type == b_type; +} + +RTLIL::IdString decode_port_semantics(RTLIL::Cell *cell, RTLIL::IdString port_name) +{ + if (cell->type.in("$lt", "$le", "$ge", "$gt", "$div", "$mod", "$concat", SHIFT_OPS) && port_name == "\\B") + return port_name; + + return ""; +} + +RTLIL::SigSpec decode_port_sign(RTLIL::Cell *cell, RTLIL::IdString port_name) { + + if (cell->type == "$alu" && port_name == "\\B") + return cell->getPort("\\BI"); + else if (cell->type == "$sub" && port_name == "\\B") + return RTLIL::Const(1, 1); + + return RTLIL::Const(0, 1); +} + +bool decode_port_signed(RTLIL::Cell *cell, RTLIL::IdString port_name) +{ + if (cell->type.in(BITWISE_OPS, LOGICAL_OPS)) + return false; + + if (cell->hasParam(port_name.str() + "_SIGNED")) + return cell->getParam(port_name.str() + "_SIGNED").as_bool(); + + return false; + +} + +ExtSigSpec decode_port(RTLIL::Cell *cell, RTLIL::IdString port_name, SigMap *sigmap) +{ + auto sig = (*sigmap)(cell->getPort(port_name)); + + RTLIL::SigSpec sign = decode_port_sign(cell, port_name); + RTLIL::IdString semantics = decode_port_semantics(cell, port_name); + + bool is_signed = decode_port_signed(cell, port_name); + + return ExtSigSpec(sig, sign, is_signed, semantics); +} + +void merge_operators(RTLIL::Module *module, RTLIL::Cell *mux, const std::vector<OpMuxConn> &ports, const ExtSigSpec &operand) +{ + + std::vector<ExtSigSpec> muxed_operands; + int max_width = 0; + for (const auto& p : ports) { + auto op = p.op; + + RTLIL::IdString muxed_port_name = "\\A"; + if (decode_port(op, "\\A", &assign_map) == operand) + muxed_port_name = "\\B"; + + auto operand = decode_port(op, muxed_port_name, &assign_map); + if (operand.sig.size() > max_width) + max_width = operand.sig.size(); + + muxed_operands.push_back(operand); + } + + auto shared_op = ports[0].op; + + if (std::any_of(muxed_operands.begin(), muxed_operands.end(), [&](ExtSigSpec &op) { return op.sign != muxed_operands[0].sign; })) + if (max_width < shared_op->getParam("\\Y_WIDTH").as_int()) + max_width = shared_op->getParam("\\Y_WIDTH").as_int(); + + + for (auto &operand : muxed_operands) + operand.sig.extend_u0(max_width, operand.is_signed); + + for (const auto& p : ports) { + auto op = p.op; + if (op == shared_op) + continue; + module->remove(op); + } + + for (auto &muxed_op : muxed_operands) + if (muxed_op.sign != muxed_operands[0].sign) + muxed_op = ExtSigSpec(module->Neg(NEW_ID, muxed_op.sig, muxed_op.is_signed)); + + + RTLIL::SigSpec mux_y = mux->getPort("\\Y"); + RTLIL::SigSpec mux_a = mux->getPort("\\A"); + RTLIL::SigSpec mux_b = mux->getPort("\\B"); + RTLIL::SigSpec mux_s = mux->getPort("\\S"); + + RTLIL::SigSpec shared_pmux_a = RTLIL::Const(RTLIL::State::Sx, max_width); + RTLIL::SigSpec shared_pmux_b; + RTLIL::SigSpec shared_pmux_s; + + int conn_width = ports[0].sig.size(); + int conn_offset = ports[0].mux_port_offset; + + shared_op->setPort("\\Y", shared_op->getPort("\\Y").extract(0, conn_width)); + + if (mux->type == "$pmux") { + shared_pmux_s = RTLIL::SigSpec(); + + for (const auto &p : ports) { + shared_pmux_s.append(mux_s[p.mux_port_id]); + mux_b.replace(p.mux_port_id * mux_a.size() + conn_offset, shared_op->getPort("\\Y")); + } + } else { + shared_pmux_s = RTLIL::SigSpec{mux_s, module->Not(NEW_ID, mux_s)}; + mux_a.replace(conn_offset, shared_op->getPort("\\Y")); + mux_b.replace(conn_offset, shared_op->getPort("\\Y")); + } + + mux->setPort("\\A", mux_a); + mux->setPort("\\B", mux_b); + mux->setPort("\\Y", mux_y); + mux->setPort("\\S", mux_s); + + for (const auto &op : muxed_operands) + shared_pmux_b.append(op.sig); + + auto mux_to_oper = module->Pmux(NEW_ID, shared_pmux_a, shared_pmux_b, shared_pmux_s); + + if (shared_op->type.in("$alu")) { + RTLIL::SigSpec alu_x = shared_op->getPort("\\X"); + RTLIL::SigSpec alu_co = shared_op->getPort("\\CO"); + + shared_op->setPort("\\X", alu_x.extract(0, conn_width)); + shared_op->setPort("\\CO", alu_co.extract(0, conn_width)); + } + + shared_op->setParam("\\Y_WIDTH", conn_width); + + if (decode_port(shared_op, "\\A", &assign_map) == operand) { + shared_op->setPort("\\B", mux_to_oper); + shared_op->setParam("\\B_WIDTH", max_width); + } else { + shared_op->setPort("\\A", mux_to_oper); + shared_op->setParam("\\A_WIDTH", max_width); + } + +} + +typedef struct { + RTLIL::Cell *mux; + std::vector<OpMuxConn> ports; + ExtSigSpec shared_operand; +} merged_op_t; + + +template <typename T> void remove_val(std::vector<T> &v, const std::vector<T> &vals) +{ + auto val_iter = vals.rbegin(); + for (auto i = v.rbegin(); i != v.rend(); ++i) + if ((val_iter != vals.rend()) && (*i == *val_iter)) { + v.erase(i.base() - 1); + ++val_iter; + } +} + +void check_muxed_operands(std::vector<const OpMuxConn *> &ports, const ExtSigSpec &shared_operand) +{ + + auto it = ports.begin(); + ExtSigSpec seed; + + while (it != ports.end()) { + auto p = *it; + auto op = p->op; + + RTLIL::IdString muxed_port_name = "\\A"; + if (decode_port(op, "\\A", &assign_map) == shared_operand) { + muxed_port_name = "\\B"; + } + + auto operand = decode_port(op, muxed_port_name, &assign_map); + + if (seed.empty()) + seed = operand; + + if (operand.is_signed != seed.is_signed) { + ports.erase(it); + } else { + ++it; + } + } +} + +ExtSigSpec find_shared_operand(const OpMuxConn* seed, std::vector<const OpMuxConn *> &ports, const std::map<ExtSigSpec, std::set<RTLIL::Cell *>> &operand_to_users) +{ + std::set<RTLIL::Cell *> ops_using_operand; + std::set<RTLIL::Cell *> ops_set; + for(const auto& p: ports) + ops_set.insert(p->op); + + ExtSigSpec oper; + + auto op_a = seed->op; + + for (RTLIL::IdString port_name : {"\\A", "\\B"}) { + oper = decode_port(op_a, port_name, &assign_map); + auto operand_users = operand_to_users.at(oper); + + if (operand_users.size() == 1) + continue; + + ops_using_operand.clear(); + for (auto mux_ops: ops_set) + if (operand_users.count(mux_ops)) + ops_using_operand.insert(mux_ops); + + if (ops_using_operand.size() > 1) { + ports.erase(std::remove_if(ports.begin(), ports.end(), [&](const OpMuxConn *p) { return !ops_using_operand.count(p->op); }), + ports.end()); + return oper; + } + } + + return ExtSigSpec(); +} + +dict<RTLIL::SigSpec, OpMuxConn> find_valid_op_mux_conns(RTLIL::Module *module, dict<RTLIL::SigBit, RTLIL::SigSpec> &op_outbit_to_outsig, + dict<RTLIL::SigSpec, RTLIL::Cell *> outsig_to_operator, + dict<RTLIL::SigBit, RTLIL::SigSpec> &op_aux_to_outsig) +{ + dict<RTLIL::SigSpec, int> op_outsig_user_track; + dict<RTLIL::SigSpec, OpMuxConn> op_mux_conn_map; + + std::function<void(RTLIL::SigSpec)> remove_outsig = [&](RTLIL::SigSpec outsig) { + for (auto op_outbit : outsig) + op_outbit_to_outsig.erase(op_outbit); + + if (op_mux_conn_map.count(outsig)) + op_mux_conn_map.erase(outsig); + }; + + std::function<void(RTLIL::SigBit)> remove_outsig_from_aux_bit = [&](RTLIL::SigBit auxbit) { + auto aux_outsig = op_aux_to_outsig.at(auxbit); + auto op = outsig_to_operator.at(aux_outsig); + auto op_outsig = assign_map(op->getPort("\\Y")); + remove_outsig(op_outsig); + + for (auto aux_outbit : aux_outsig) + op_aux_to_outsig.erase(aux_outbit); + }; + + std::function<void(RTLIL::Cell *)> + find_op_mux_conns = [&](RTLIL::Cell *mux) { + RTLIL::SigSpec sig; + int mux_port_size; + + if (mux->type.in("$mux", "$_MUX_")) { + mux_port_size = mux->getPort("\\A").size(); + sig = RTLIL::SigSpec{mux->getPort("\\B"), mux->getPort("\\A")}; + } else { + mux_port_size = mux->getPort("\\A").size(); + sig = mux->getPort("\\B"); + } + + auto mux_insig = assign_map(sig); + + for (int i = 0; i < mux_insig.size(); ++i) { + if (op_aux_to_outsig.count(mux_insig[i])) { + remove_outsig_from_aux_bit(mux_insig[i]); + continue; + } + + if (!op_outbit_to_outsig.count(mux_insig[i])) + continue; + + auto op_outsig = op_outbit_to_outsig.at(mux_insig[i]); + + if (op_mux_conn_map.count(op_outsig)) { + remove_outsig(op_outsig); + continue; + } + + int mux_port_id = i / mux_port_size; + int mux_port_offset = i % mux_port_size; + + int op_outsig_offset; + for (op_outsig_offset = 0; op_outsig[op_outsig_offset] != mux_insig[i]; ++op_outsig_offset) + ; + + int j = op_outsig_offset; + do { + if (!op_outbit_to_outsig.count(mux_insig[i])) + break; + + if (op_outbit_to_outsig.at(mux_insig[i]) != op_outsig) + break; + + ++i; + ++j; + } while ((i / mux_port_size == mux_port_id) && (j < op_outsig.size())); + + int op_conn_width = j - op_outsig_offset; + OpMuxConn inp = { + op_outsig.extract(op_outsig_offset, op_conn_width), + mux, + outsig_to_operator.at(op_outsig), + mux_port_id, + mux_port_offset, + op_outsig_offset, + }; + + op_mux_conn_map[op_outsig] = inp; + + --i; + } + }; + + std::function<void(RTLIL::SigSpec)> remove_connected_ops = [&](RTLIL::SigSpec sig) { + auto mux_insig = assign_map(sig); + for (auto outbit : mux_insig) { + if (op_aux_to_outsig.count(outbit)) { + remove_outsig_from_aux_bit(outbit); + continue; + } + + if (!op_outbit_to_outsig.count(outbit)) + continue; + + remove_outsig(op_outbit_to_outsig.at(outbit)); + } + }; + + for (auto cell : module->cells()) { + if (cell->type.in("$mux", "$_MUX_", "$pmux")) { + remove_connected_ops(cell->getPort("\\S")); + find_op_mux_conns(cell); + } else { + for (auto &conn : cell->connections()) + if (cell->input(conn.first)) + remove_connected_ops(conn.second); + } + } + + for (auto w : module->wires()) { + if (!w->port_output) + continue; + + remove_connected_ops(w); + } + + return op_mux_conn_map; +} + +struct OptSharePass : public Pass { + OptSharePass() : Pass("opt_share", "merge mutually exclusive cells of the same type that share an input signal") {} + void help() YS_OVERRIDE + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" opt_share [selection]\n"); + log("\n"); + + log("This pass identifies mutually exclusive cells of the same type that:\n"); + log(" (a) share an input signal,\n"); + log(" (b) drive the same $mux, $_MUX_, or $pmux multiplexing cell,\n"); + log("\n"); + log("allowing the cell to be merged and the multiplexer to be moved from\n"); + log("multiplexing its output to multiplexing the non-shared input signals.\n"); + log("\n"); + } + void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE + { + + log_header(design, "Executing OPT_SHARE pass.\n"); + + extra_args(args, 1, design); + for (auto module : design->selected_modules()) { + assign_map.clear(); + assign_map.set(module); + + std::map<ExtSigSpec, std::set<RTLIL::Cell *>> operand_to_users; + dict<RTLIL::SigSpec, RTLIL::Cell *> outsig_to_operator; + dict<RTLIL::SigBit, RTLIL::SigSpec> op_outbit_to_outsig; + dict<RTLIL::SigBit, RTLIL::SigSpec> op_aux_to_outsig; + bool any_shared_operands = false; + std::vector<ExtSigSpec> op_insigs; + + for (auto cell : module->cells()) { + if (!cell_supported(cell)) + continue; + + if (cell->type == "$alu") { + for (RTLIL::IdString port_name : {"\\X", "\\CO"}) { + auto mux_insig = assign_map(cell->getPort(port_name)); + outsig_to_operator[mux_insig] = cell; + for (auto outbit : mux_insig) + op_aux_to_outsig[outbit] = mux_insig; + } + } + + auto mux_insig = assign_map(cell->getPort("\\Y")); + outsig_to_operator[mux_insig] = cell; + for (auto outbit : mux_insig) + op_outbit_to_outsig[outbit] = mux_insig; + + for (RTLIL::IdString port_name : {"\\A", "\\B"}) { + auto op_insig = decode_port(cell, port_name, &assign_map); + op_insigs.push_back(op_insig); + operand_to_users[op_insig].insert(cell); + if (operand_to_users[op_insig].size() > 1) + any_shared_operands = true; + } + } + + if (!any_shared_operands) + continue; + + // Operator outputs need to be exclusively connected to the $mux inputs in order to be mergeable. Hence we count to + // how many points are operator output bits connected. + dict<RTLIL::SigSpec, OpMuxConn> op_mux_conn_map = + find_valid_op_mux_conns(module, op_outbit_to_outsig, outsig_to_operator, op_aux_to_outsig); + + // Group op connections connected to same ports of the same $mux. Sort them in ascending order of their port offset + dict<RTLIL::Cell*, std::vector<std::set<OpMuxConn>>> mux_port_op_conns; + for (auto& val: op_mux_conn_map) { + OpMuxConn p = val.second; + auto& mux_port_conns = mux_port_op_conns[p.mux]; + + if (mux_port_conns.size() == 0) { + int mux_port_num; + + if (p.mux->type.in("$mux", "$_MUX_")) + mux_port_num = 2; + else + mux_port_num = p.mux->getPort("\\S").size(); + + mux_port_conns.resize(mux_port_num); + } + + mux_port_conns[p.mux_port_id].insert(p); + } + + std::vector<merged_op_t> merged_ops; + for (auto& val: mux_port_op_conns) { + + RTLIL::Cell* cell = val.first; + auto &mux_port_conns = val.second; + + const OpMuxConn *seed = NULL; + + // Look through the bits of the $mux inputs and see which of them are connected to the operator + // results. Operator results can be concatenated with other signals before led to the $mux. + while (true) { + + // Remove either the merged ports from the last iteration or the seed that failed to yield a merger + if (seed != NULL) { + mux_port_conns[seed->mux_port_id].erase(*seed); + seed = NULL; + } + + // For a new merger, find the seed op connection that starts at lowest port offset among port connections + for (auto &port_conns : mux_port_conns) { + if (!port_conns.size()) + continue; + + const OpMuxConn *next_p = &(*port_conns.begin()); + + if ((seed == NULL) || (seed->mux_port_offset > next_p->mux_port_offset)) + seed = next_p; + } + + // Cannot find the seed -> nothing to do for this $mux anymore + if (seed == NULL) + break; + + // Find all other op connections that start from the same port offset, and whose ops can be merged with the seed op + std::vector<const OpMuxConn *> mergeable_conns; + for (auto &port_conns : mux_port_conns) { + if (!port_conns.size()) + continue; + + const OpMuxConn *next_p = &(*port_conns.begin()); + + if ((next_p->op_outsig_offset == seed->op_outsig_offset) && + (next_p->mux_port_offset == seed->mux_port_offset) && mergeable(next_p->op, seed->op) && + next_p->sig.size() == seed->sig.size()) + mergeable_conns.push_back(next_p); + } + + // We need at least two mergeable connections for the merger + if (mergeable_conns.size() < 2) + continue; + + // Filter mergeable connections whose ops share an operand with seed connection's op + auto shared_operand = find_shared_operand(seed, mergeable_conns, operand_to_users); + + if (shared_operand.empty()) + continue; + + check_muxed_operands(mergeable_conns, shared_operand); + + if (mergeable_conns.size() < 2) + continue; + + // Remember the combination for the merger + std::vector<OpMuxConn> merged_ports; + for (auto p : mergeable_conns) { + merged_ports.push_back(*p); + mux_port_conns[p->mux_port_id].erase(*p); + } + + seed = NULL; + + merged_ops.push_back(merged_op_t{cell, merged_ports, shared_operand}); + + design->scratchpad_set_bool("opt.did_something", true); + } + + } + + for (auto &shared : merged_ops) { + log(" Found cells that share an operand and can be merged by moving the %s %s in front " + "of " + "them:\n", + log_id(shared.mux->type), log_id(shared.mux)); + for (const auto& op : shared.ports) + log(" %s\n", log_id(op.op)); + log("\n"); + + merge_operators(module, shared.mux, shared.ports, shared.shared_operand); + } + } + } + +} OptSharePass; + +PRIVATE_NAMESPACE_END diff --git a/tests/opt/opt_share_add_sub.v b/tests/opt/opt_share_add_sub.v new file mode 100644 index 000000000..d918f27cc --- /dev/null +++ b/tests/opt/opt_share_add_sub.v @@ -0,0 +1,10 @@ +module opt_share_test( + input [15:0] a, + input [15:0] b, + input sel, + output [15:0] res, + ); + + assign res = {sel ? a + b : a - b}; + +endmodule diff --git a/tests/opt/opt_share_add_sub.ys b/tests/opt/opt_share_add_sub.ys new file mode 100644 index 000000000..4a5406791 --- /dev/null +++ b/tests/opt/opt_share_add_sub.ys @@ -0,0 +1,13 @@ +read_verilog opt_share_add_sub.v +proc;; +copy opt_share_test merged + +alumacc merged +opt merged +opt_share merged +opt_clean merged + +miter -equiv -flatten -ignore_gold_x -make_outputs -make_outcmp opt_share_test merged miter +sat -set-def-inputs -verify -prove trigger 0 -show-inputs -show-outputs miter + +select -assert-count 1 -module merged t:$alu diff --git a/tests/opt/opt_share_cat.v b/tests/opt/opt_share_cat.v new file mode 100644 index 000000000..7fb97fef5 --- /dev/null +++ b/tests/opt/opt_share_cat.v @@ -0,0 +1,15 @@ +module opt_share_test( + input [15:0] a, + input [15:0] b, + input [15:0] c, + input [15:0] d, + input sel, + output [63:0] res, + ); + + reg [31: 0] cat1 = {a+b, c+d}; + reg [31: 0] cat2 = {a-b, c-d}; + + assign res = {b, sel ? cat1 : cat2, a}; + +endmodule diff --git a/tests/opt/opt_share_cat.ys b/tests/opt/opt_share_cat.ys new file mode 100644 index 000000000..7de69bfde --- /dev/null +++ b/tests/opt/opt_share_cat.ys @@ -0,0 +1,13 @@ +read_verilog opt_share_cat.v +proc;; +copy opt_share_test merged + +alumacc merged +opt merged +opt_share merged +opt_clean merged + +miter -equiv -flatten -ignore_gold_x -make_outputs -make_outcmp opt_share_test merged miter +sat -set-def-inputs -verify -prove trigger 0 -show-inputs -show-outputs miter + +select -assert-count 2 -module merged t:$alu diff --git a/tests/opt/opt_share_cat_multiuser.v b/tests/opt/opt_share_cat_multiuser.v new file mode 100644 index 000000000..b250689d9 --- /dev/null +++ b/tests/opt/opt_share_cat_multiuser.v @@ -0,0 +1,22 @@ +module opt_share_test( + input [15:0] a, + input [15:0] b, + input [15:0] c, + input [15:0] d, + input sel, + output reg [47:0] res, + ); + + wire [15:0] add_res = a+b; + wire [15:0] sub_res = a-b; + wire [31: 0] cat1 = {add_res, c+d}; + wire [31: 0] cat2 = {sub_res, c-d}; + + always @* begin + case(sel) + 0: res = {cat1, add_res}; + 1: res = {cat2, add_res}; + endcase + end + +endmodule diff --git a/tests/opt/opt_share_cat_multiuser.ys b/tests/opt/opt_share_cat_multiuser.ys new file mode 100644 index 000000000..6a82fbd79 --- /dev/null +++ b/tests/opt/opt_share_cat_multiuser.ys @@ -0,0 +1,13 @@ +read_verilog opt_share_cat_multiuser.v +proc;; +copy opt_share_test merged + +alumacc merged +opt merged +opt_share merged +opt_clean merged + +miter -equiv -flatten -ignore_gold_x -make_outputs -make_outcmp opt_share_test merged miter +sat -set-def-inputs -verify -prove trigger 0 -show-inputs -show-outputs miter + +select -assert-count 3 -module merged t:$alu diff --git a/tests/opt/opt_share_diff_port_widths.v b/tests/opt/opt_share_diff_port_widths.v new file mode 100644 index 000000000..1a37c80a6 --- /dev/null +++ b/tests/opt/opt_share_diff_port_widths.v @@ -0,0 +1,21 @@ +module opt_share_test( + input [15:0] a, + input [15:0] b, + input [15:0] c, + input [1:0] sel, + output reg [15:0] res + ); + + wire [15:0] add0_res = a+b; + wire [15:0] add1_res = a+c; + + always @* begin + case(sel) + 0: res = add0_res[10:0]; + 1: res = add1_res[10:0]; + 2: res = a - b; + default: res = 32'bx; + endcase + end + +endmodule diff --git a/tests/opt/opt_share_diff_port_widths.ys b/tests/opt/opt_share_diff_port_widths.ys new file mode 100644 index 000000000..ec5e9f7b0 --- /dev/null +++ b/tests/opt/opt_share_diff_port_widths.ys @@ -0,0 +1,13 @@ +read_verilog opt_share_diff_port_widths.v +proc;; +copy opt_share_test merged + +alumacc merged +opt merged +opt_share merged +opt_clean merged + +miter -equiv -flatten -ignore_gold_x -make_outputs -make_outcmp opt_share_test merged miter +sat -set-def-inputs -verify -prove trigger 0 -show-inputs -show-outputs miter + +select -assert-count 2 -module merged t:$alu diff --git a/tests/opt/opt_share_extend.v b/tests/opt/opt_share_extend.v new file mode 100644 index 000000000..d39f19069 --- /dev/null +++ b/tests/opt/opt_share_extend.v @@ -0,0 +1,18 @@ +module opt_share_test( + input signed [7:0] a, + input signed [10:0] b, + input signed [15:0] c, + input [1:0] sel, + output reg signed [15:0] res + ); + + always @* begin + case(sel) + 0: res = a + b; + 1: res = a - b; + 2: res = a + c; + default: res = 16'bx; + endcase + end + +endmodule diff --git a/tests/opt/opt_share_extend.ys b/tests/opt/opt_share_extend.ys new file mode 100644 index 000000000..c553ee0fb --- /dev/null +++ b/tests/opt/opt_share_extend.ys @@ -0,0 +1,13 @@ +read_verilog opt_share_extend.v +proc;; +copy opt_share_test merged + +alumacc merged +opt merged +opt_share merged +opt_clean merged + +miter -equiv -flatten -ignore_gold_x -make_outputs -make_outcmp opt_share_test merged miter +sat -set-def-inputs -verify -prove trigger 0 -show-inputs -show-outputs miter + +select -assert-count 1 -module merged t:$alu diff --git a/tests/opt/opt_share_large_pmux_cat.v b/tests/opt/opt_share_large_pmux_cat.v new file mode 100644 index 000000000..416ba3766 --- /dev/null +++ b/tests/opt/opt_share_large_pmux_cat.v @@ -0,0 +1,21 @@ +module opt_share_test( + input [15:0] a, + input [15:0] b, + input [15:0] c, + input [2:0] sel, + output reg [31:0] res + ); + + always @* begin + case(sel) + 0: res = {a + b, a}; + 1: res = {a - b, b}; + 2: res = {a + c, c}; + 3: res = {a - c, a}; + 4: res = {b, b}; + 5: res = {c, c}; + default: res = 32'bx; + endcase + end + +endmodule diff --git a/tests/opt/opt_share_large_pmux_cat.ys b/tests/opt/opt_share_large_pmux_cat.ys new file mode 100644 index 000000000..4186ca52e --- /dev/null +++ b/tests/opt/opt_share_large_pmux_cat.ys @@ -0,0 +1,13 @@ +read_verilog opt_share_large_pmux_cat.v +proc;; +copy opt_share_test merged + +alumacc merged +opt merged +opt_share merged +opt_clean merged + +miter -equiv -flatten -ignore_gold_x -make_outputs -make_outcmp opt_share_test merged miter +sat -set-def-inputs -verify -prove trigger 0 -show-inputs -show-outputs miter + +select -assert-count 1 -module merged t:$alu diff --git a/tests/opt/opt_share_large_pmux_cat_multipart.v b/tests/opt/opt_share_large_pmux_cat_multipart.v new file mode 100644 index 000000000..34d2bd9a8 --- /dev/null +++ b/tests/opt/opt_share_large_pmux_cat_multipart.v @@ -0,0 +1,25 @@ +module opt_share_test( + input [15:0] a, + input [15:0] b, + input [15:0] c, + input [15:0] d, + input [2:0] sel, + output reg [31:0] res + ); + + wire [15:0] add0_res = a+d; + + always @* begin + case(sel) + 0: res = {add0_res, a}; + 1: res = {a - b, add0_res[7], 15'b0}; + 2: res = {b-a, b}; + 3: res = {d, b - c}; + 4: res = {d, b - a}; + 5: res = {c, d}; + 6: res = {a - c, b-d}; + default: res = 32'bx; + endcase + end + +endmodule diff --git a/tests/opt/opt_share_large_pmux_cat_multipart.ys b/tests/opt/opt_share_large_pmux_cat_multipart.ys new file mode 100644 index 000000000..610bb8c6c --- /dev/null +++ b/tests/opt/opt_share_large_pmux_cat_multipart.ys @@ -0,0 +1,14 @@ +read_verilog opt_share_large_pmux_cat_multipart.v +proc;; +copy opt_share_test merged + +alumacc merged +opt merged + +opt_share merged +opt_clean merged + +miter -equiv -flatten -ignore_gold_x -make_outputs -make_outcmp opt_share_test merged miter +sat -set-def-inputs -verify -prove trigger 0 -show-inputs -show-outputs miter + +select -assert-count 4 -module merged t:$alu diff --git a/tests/opt/opt_share_large_pmux_multipart.v b/tests/opt/opt_share_large_pmux_multipart.v new file mode 100644 index 000000000..535adf96f --- /dev/null +++ b/tests/opt/opt_share_large_pmux_multipart.v @@ -0,0 +1,23 @@ +module opt_share_test( + input [15:0] a, + input [15:0] b, + input [15:0] c, + input [15:0] d, + input [2:0] sel, + output reg [15:0] res + ); + + always @* begin + case(sel) + 0: res = a + d; + 1: res = a - b; + 2: res = b; + 3: res = b - c; + 4: res = b - a; + 5: res = c; + 6: res = a - c; + default: res = 16'bx; + endcase + end + +endmodule diff --git a/tests/opt/opt_share_large_pmux_multipart.ys b/tests/opt/opt_share_large_pmux_multipart.ys new file mode 100644 index 000000000..11182df1a --- /dev/null +++ b/tests/opt/opt_share_large_pmux_multipart.ys @@ -0,0 +1,13 @@ +read_verilog opt_share_large_pmux_multipart.v +proc;; +copy opt_share_test merged + +alumacc merged +opt merged +opt_share merged +opt_clean merged + +miter -equiv -flatten -ignore_gold_x -make_outputs -make_outcmp opt_share_test merged miter +sat -set-def-inputs -verify -prove trigger 0 -show-inputs -show-outputs miter + +select -assert-count 2 -module merged t:$alu diff --git a/tests/opt/opt_share_large_pmux_part.v b/tests/opt/opt_share_large_pmux_part.v new file mode 100644 index 000000000..a9008fb5a --- /dev/null +++ b/tests/opt/opt_share_large_pmux_part.v @@ -0,0 +1,21 @@ +module opt_share_test( + input [15:0] a, + input [15:0] b, + input [15:0] c, + input [2:0] sel, + output reg [15:0] res + ); + + always @* begin + case(sel) + 0: res = a + b; + 1: res = a - b; + 2: res = a + c; + 3: res = a - c; + 4: res = b; + 5: res = c; + default: res = 16'bx; + endcase + end + +endmodule diff --git a/tests/opt/opt_share_large_pmux_part.ys b/tests/opt/opt_share_large_pmux_part.ys new file mode 100644 index 000000000..6b594a3d6 --- /dev/null +++ b/tests/opt/opt_share_large_pmux_part.ys @@ -0,0 +1,13 @@ +read_verilog opt_share_large_pmux_part.v +proc;; +copy opt_share_test merged + +alumacc merged +opt merged +opt_share merged +opt_clean merged + +miter -equiv -flatten -ignore_gold_x -make_outputs -make_outcmp opt_share_test merged miter +sat -set-def-inputs -verify -prove trigger 0 -show-inputs -show-outputs miter + +select -assert-count 1 -module merged t:$alu diff --git a/tests/opt/opt_share_mux_tree.v b/tests/opt/opt_share_mux_tree.v new file mode 100644 index 000000000..cc5ae4eb9 --- /dev/null +++ b/tests/opt/opt_share_mux_tree.v @@ -0,0 +1,18 @@ +module opt_share_test( + input [15:0] a, + input [15:0] b, + input [15:0] c, + input [1:0] sel, + output reg [15:0] res + ); + + always @* begin + case(sel) + 0: res = a + b; + 1: res = a - b; + 2: res = a + c; + default: res = 16'bx; + endcase + end + +endmodule diff --git a/tests/opt/opt_share_mux_tree.ys b/tests/opt/opt_share_mux_tree.ys new file mode 100644 index 000000000..58473039f --- /dev/null +++ b/tests/opt/opt_share_mux_tree.ys @@ -0,0 +1,13 @@ +read_verilog opt_share_mux_tree.v +proc;; +copy opt_share_test merged + +alumacc merged +opt merged +opt_share merged +opt_clean merged + +miter -equiv -flatten -ignore_gold_x -make_outputs -make_outcmp opt_share_test merged miter +sat -set-def-inputs -verify -prove trigger 0 -show-inputs -show-outputs miter + +select -assert-count 1 -module merged t:$alu diff --git a/tests/opt_share/.gitignore b/tests/opt_share/.gitignore new file mode 100644 index 000000000..9c595a6fb --- /dev/null +++ b/tests/opt_share/.gitignore @@ -0,0 +1 @@ +temp diff --git a/tests/opt_share/generate.py b/tests/opt_share/generate.py new file mode 100644 index 000000000..2ec92f7de --- /dev/null +++ b/tests/opt_share/generate.py @@ -0,0 +1,86 @@ +#!/usr/bin/env python3 + +import argparse +import sys +import random +from contextlib import contextmanager + + +@contextmanager +def redirect_stdout(new_target): + old_target, sys.stdout = sys.stdout, new_target + try: + yield new_target + finally: + sys.stdout = old_target + + +def random_plus_x(): + return "%s x" % random.choice(['+', '+', '+', '-', '-', '|', '&', '^']) + + +def maybe_plus_x(expr): + if random.randint(0, 4) == 0: + return "(%s %s)" % (expr, random_plus_x()) + else: + return expr + + +parser = argparse.ArgumentParser( + formatter_class=argparse.ArgumentDefaultsHelpFormatter) +parser.add_argument('-S', '--seed', type=int, help='seed for PRNG') +parser.add_argument('-c', + '--count', + type=int, + default=100, + help='number of test cases to generate') +args = parser.parse_args() + +if args.seed is not None: + print("PRNG seed: %d" % args.seed) + random.seed(args.seed) + +for idx in range(args.count): + with open('temp/uut_%05d.v' % idx, 'w') as f: + with redirect_stdout(f): + print('module uut_%05d(a, b, c, s, y);' % (idx)) + op = random.choice([ + random.choice(['+', '-', '*', '/', '%']), + random.choice(['<', '<=', '==', '!=', '===', '!==', '>=', + '>']), + random.choice(['<<', '>>', '<<<', '>>>']), + random.choice(['|', '&', '^', '~^', '||', '&&']), + ]) + print(' input%s [%d:0] a;' % (random.choice(['', ' signed']), 8)) + print(' input%s [%d:0] b;' % (random.choice(['', ' signed']), 8)) + print(' input%s [%d:0] c;' % (random.choice(['', ' signed']), 8)) + print(' input s;') + print(' output [%d:0] y;' % 8) + ops1 = ['a', 'b'] + ops2 = ['a', 'c'] + random.shuffle(ops1) + random.shuffle(ops2) + cast1 = random.choice(['', '$signed', '$unsigned']) + cast2 = random.choice(['', '$signed', '$unsigned']) + print(' assign y = (s ? %s(%s %s %s) : %s(%s %s %s));' % + (cast1, ops1[0], op, ops1[1], + cast2, ops2[0], op, ops2[1])) + print('endmodule') + + with open('temp/uut_%05d.ys' % idx, 'w') as f: + with redirect_stdout(f): + print('read_verilog temp/uut_%05d.v' % idx) + print('proc;;') + print('copy uut_%05d gold' % idx) + print('rename uut_%05d gate' % idx) + print('tee -a temp/all_share_log.txt log') + print('tee -a temp/all_share_log.txt log #job# uut_%05d' % idx) + print('tee -a temp/all_share_log.txt opt gate') + print('tee -a temp/all_share_log.txt opt_share gate') + print('tee -a temp/all_share_log.txt opt_clean gate') + print( + 'miter -equiv -flatten -ignore_gold_x -make_outputs -make_outcmp gold gate miter' + ) + print( + 'sat -set-def-inputs -verify -prove trigger 0 -show-inputs -show-outputs miter' + ) diff --git a/tests/opt_share/run-test.sh b/tests/opt_share/run-test.sh new file mode 100755 index 000000000..e01552646 --- /dev/null +++ b/tests/opt_share/run-test.sh @@ -0,0 +1,39 @@ +#!/bin/bash + +# run this test many times: +# time bash -c 'for ((i=0; i<100; i++)); do echo "-- $i --"; bash run-test.sh || exit 1; done' + +set -e + +OPTIND=1 +count=100 +seed="" # default to no seed specified +while getopts "c:S:" opt +do + case "$opt" in + c) count="$OPTARG" ;; + S) seed="-S $OPTARG" ;; + esac +done +shift "$((OPTIND-1))" + +rm -rf temp +mkdir -p temp +echo "generating tests.." +python3 generate.py -c $count $seed + +echo "running tests.." +for i in $( ls temp/*.ys | sed 's,[^0-9],,g; s,^0*\(.\),\1,g;' ); do + echo -n "[$i]" + idx=$( printf "%05d" $i ) + ../../yosys -ql temp/uut_${idx}.log temp/uut_${idx}.ys +done +echo + +failed_share=$( echo $( gawk '/^#job#/ { j=$2; db[j]=0; } /^Removing [246] cells/ { delete db[j]; } END { for (j in db) print(j); }' temp/all_share_log.txt ) ) +if [ -n "$failed_share" ]; then + echo "Resource sharing failed for the following test cases: $failed_share" + false +fi + +exit 0 |