From 17163cf43a6b6eec9aac44f6a4463dda54b8ed68 Mon Sep 17 00:00:00 2001 From: Xiretza Date: Wed, 8 Apr 2020 19:30:47 +0200 Subject: [PATCH] Add flooring modulo operator The $div and $mod cells use truncating division semantics (rounding towards 0), as defined by e.g. Verilog. Another rounding mode, flooring (rounding towards negative infinity), can be used in e.g. VHDL. The new $modfloor cell provides this flooring modulo (also known as "remainder" in several languages, but this name is ambiguous). This commit also fixes the handling of $mod in opt_expr, which was previously optimized as if it was $modfloor. --- backends/btor/btor.cc | 14 +++-- backends/btor/test_cells.sh | 2 +- backends/firrtl/firrtl.cc | 1 + backends/smt2/smt2.cc | 10 ++++ backends/smv/smv.cc | 5 +- backends/smv/test_cells.sh | 4 +- backends/verilog/verilog_backend.cc | 34 +++++++++++++ kernel/calc.cc | 25 +++++++++ kernel/celledges.cc | 2 +- kernel/celltypes.h | 3 +- kernel/rtlil.cc | 3 +- kernel/rtlil.h | 3 ++ kernel/satgen.h | 31 +++++++---- manual/PRESENTATION_Prog.tex | 2 +- passes/cmds/stat.cc | 2 +- passes/memory/memory_share.cc | 1 + passes/opt/opt_expr.cc | 33 ++++++++++-- passes/opt/opt_share.cc | 4 +- passes/opt/share.cc | 4 +- passes/opt/wreduce.cc | 4 +- passes/tests/test_cell.cc | 3 +- techlibs/common/simlib.v | 48 ++++++++++++++++++ techlibs/common/techmap.v | 79 +++++++++++++++++++++++++++-- 23 files changed, 280 insertions(+), 37 deletions(-) diff --git a/backends/btor/btor.cc b/backends/btor/btor.cc index 14c8484e8..2816d3246 100644 --- a/backends/btor/btor.cc +++ b/backends/btor/btor.cc @@ -266,20 +266,26 @@ struct BtorWorker goto okay; } - if (cell->type.in(ID($div), ID($mod))) + if (cell->type.in(ID($div), ID($mod), ID($modfloor))) { + bool a_signed = cell->hasParam(ID::A_SIGNED) ? cell->getParam(ID::A_SIGNED).as_bool() : false; + bool b_signed = cell->hasParam(ID::B_SIGNED) ? cell->getParam(ID::B_SIGNED).as_bool() : false; + string btor_op; if (cell->type == ID($div)) btor_op = "div"; + // "rem" = truncating modulo if (cell->type == ID($mod)) btor_op = "rem"; + // "mod" = flooring modulo + if (cell->type == ID($modfloor)) { + // "umod" doesn't exist because it's the same as "urem" + btor_op = a_signed || b_signed ? "mod" : "rem"; + } log_assert(!btor_op.empty()); int width = GetSize(cell->getPort(ID::Y)); width = std::max(width, GetSize(cell->getPort(ID::A))); width = std::max(width, GetSize(cell->getPort(ID::B))); - bool a_signed = cell->hasParam(ID::A_SIGNED) ? cell->getParam(ID::A_SIGNED).as_bool() : false; - bool b_signed = cell->hasParam(ID::B_SIGNED) ? cell->getParam(ID::B_SIGNED).as_bool() : false; - int nid_a = get_sig_nid(cell->getPort(ID::A), width, a_signed); int nid_b = get_sig_nid(cell->getPort(ID::B), width, b_signed); diff --git a/backends/btor/test_cells.sh b/backends/btor/test_cells.sh index e0f1a0514..e8d35acf8 100644 --- a/backends/btor/test_cells.sh +++ b/backends/btor/test_cells.sh @@ -6,7 +6,7 @@ rm -rf test_cells.tmp mkdir -p test_cells.tmp cd test_cells.tmp -../../../yosys -p 'test_cell -n 5 -w test all /$alu /$fa /$lcu /$lut /$sop /$macc /$mul /$div /$mod' +../../../yosys -p 'test_cell -n 5 -w test all /$alu /$fa /$lcu /$lut /$sop /$macc /$mul /$div /$mod /$modfloor' for fn in test_*.il; do ../../../yosys -p " diff --git a/backends/firrtl/firrtl.cc b/backends/firrtl/firrtl.cc index a90b0b87a..b1d8500bb 100644 --- a/backends/firrtl/firrtl.cc +++ b/backends/firrtl/firrtl.cc @@ -585,6 +585,7 @@ struct FirrtlWorker firrtl_is_signed = a_signed | b_signed; firrtl_width = a_width; } else if (cell->type == ID($mod)) { + // "rem" = truncating modulo primop = "rem"; firrtl_width = min(a_width, b_width); } else if (cell->type.in(ID($and), ID($_AND_))) { diff --git a/backends/smt2/smt2.cc b/backends/smt2/smt2.cc index 3e67e55f2..26f17bcb3 100644 --- a/backends/smt2/smt2.cc +++ b/backends/smt2/smt2.cc @@ -590,7 +590,17 @@ struct Smt2Worker if (cell->type == ID($sub)) return export_bvop(cell, "(bvsub A B)"); if (cell->type == ID($mul)) return export_bvop(cell, "(bvmul A B)"); if (cell->type == ID($div)) return export_bvop(cell, "(bvUdiv A B)", 'd'); + // "rem" = truncating modulo if (cell->type == ID($mod)) return export_bvop(cell, "(bvUrem A B)", 'd'); + // "mod" = flooring modulo + if (cell->type == ID($modfloor)) { + // bvumod doesn't exist because it's the same as bvurem + if (cell->getParam(ID::A_SIGNED).as_bool()) { + return export_bvop(cell, "(bvsmod A B)", 'd'); + } else { + return export_bvop(cell, "(bvurem A B)", 'd'); + } + } if (cell->type.in(ID($reduce_and), ID($reduce_or), ID($reduce_bool)) && 2*GetSize(cell->getPort(ID::A).chunks()) < GetSize(cell->getPort(ID::A))) { diff --git a/backends/smv/smv.cc b/backends/smv/smv.cc index 7113ebc97..2fc7099f4 100644 --- a/backends/smv/smv.cc +++ b/backends/smv/smv.cc @@ -358,7 +358,8 @@ struct SmvWorker continue; } - if (cell->type.in(ID($div), ID($mod))) + // SMV has a "mod" operator, but its semantics don't seem to be well-defined - to be safe, don't generate it at all + if (cell->type.in(ID($div)/*, ID($mod), ID($modfloor)*/)) { int width_y = GetSize(cell->getPort(ID::Y)); int width = max(width_y, GetSize(cell->getPort(ID::A))); @@ -366,7 +367,7 @@ struct SmvWorker string expr_a, expr_b, op; if (cell->type == ID($div)) op = "/"; - if (cell->type == ID($mod)) op = "mod"; + //if (cell->type == ID($mod)) op = "mod"; if (cell->getParam(ID::A_SIGNED).as_bool()) { diff --git a/backends/smv/test_cells.sh b/backends/smv/test_cells.sh index 63de465c0..ae832ce00 100644 --- a/backends/smv/test_cells.sh +++ b/backends/smv/test_cells.sh @@ -7,8 +7,8 @@ mkdir -p test_cells.tmp cd test_cells.tmp # don't test $mul to reduce runtime -# don't test $div and $mod to reduce runtime and avoid "div by zero" message -../../../yosys -p 'test_cell -n 5 -w test all /$alu /$fa /$lcu /$lut /$macc /$mul /$div /$mod' +# don't test $div/$mod/$modfloor to reduce runtime and avoid "div by zero" message +../../../yosys -p 'test_cell -n 5 -w test all /$alu /$fa /$lcu /$lut /$macc /$mul /$div /$mod /$modfloor' cat > template.txt << "EOT" %module main diff --git a/backends/verilog/verilog_backend.cc b/backends/verilog/verilog_backend.cc index 11b2ae10f..368b76793 100644 --- a/backends/verilog/verilog_backend.cc +++ b/backends/verilog/verilog_backend.cc @@ -740,6 +740,40 @@ bool dump_cell_expr(std::ostream &f, std::string indent, RTLIL::Cell *cell) #undef HANDLE_UNIOP #undef HANDLE_BINOP + if (cell->type == ID($modfloor)) + { + // wire truncated = $signed(A) % $signed(B); + // assign Y = (A[-1] == B[-1]) || truncated == 0 ? truncated : $signed(B) + $signed(truncated); + + if (cell->getParam(ID::A_SIGNED).as_bool() && cell->getParam(ID::B_SIGNED).as_bool()) { + SigSpec sig_a = cell->getPort(ID::A); + SigSpec sig_b = cell->getPort(ID::B); + + std::string temp_id = next_auto_id(); + f << stringf("%s" "wire [%d:0] %s = ", indent.c_str(), GetSize(cell->getPort(ID::A))-1, temp_id.c_str()); + dump_cell_expr_port(f, cell, "A", true); + f << stringf(" %% "); + dump_attributes(f, "", cell->attributes, ' '); + dump_cell_expr_port(f, cell, "B", true); + f << stringf(";\n"); + + f << stringf("%s" "assign ", indent.c_str()); + dump_sigspec(f, cell->getPort(ID::Y)); + f << stringf(" = ("); + dump_sigspec(f, sig_a.extract(sig_a.size()-1)); + f << stringf(" == "); + dump_sigspec(f, sig_b.extract(sig_b.size()-1)); + f << stringf(") || %s == 0 ? %s : ", temp_id.c_str(), temp_id.c_str()); + dump_cell_expr_port(f, cell, "B", true); + f << stringf(" + $signed(%s);\n", temp_id.c_str()); + return true; + } else { + // same as truncating modulo + dump_cell_expr_binop(f, indent, cell, "%"); + return true; + } + } + if (cell->type == ID($shift)) { f << stringf("%s" "assign ", indent.c_str()); diff --git a/kernel/calc.cc b/kernel/calc.cc index 4a4840771..38a529128 100644 --- a/kernel/calc.cc +++ b/kernel/calc.cc @@ -489,6 +489,7 @@ RTLIL::Const RTLIL::const_mul(const RTLIL::Const &arg1, const RTLIL::Const &arg2 return big2const(y, result_len >= 0 ? result_len : max(arg1.bits.size(), arg2.bits.size()), min(undef_bit_pos, 0)); } +// truncating division RTLIL::Const RTLIL::const_div(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len) { int undef_bit_pos = -1; @@ -502,6 +503,7 @@ RTLIL::Const RTLIL::const_div(const RTLIL::Const &arg1, const RTLIL::Const &arg2 return big2const(result_neg ? -(a / b) : (a / b), result_len >= 0 ? result_len : max(arg1.bits.size(), arg2.bits.size()), min(undef_bit_pos, 0)); } +// truncating modulo RTLIL::Const RTLIL::const_mod(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len) { int undef_bit_pos = -1; @@ -515,6 +517,29 @@ RTLIL::Const RTLIL::const_mod(const RTLIL::Const &arg1, const RTLIL::Const &arg2 return big2const(result_neg ? -(a % b) : (a % b), result_len >= 0 ? result_len : max(arg1.bits.size(), arg2.bits.size()), min(undef_bit_pos, 0)); } +RTLIL::Const RTLIL::const_modfloor(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len) +{ + int undef_bit_pos = -1; + BigInteger a = const2big(arg1, signed1, undef_bit_pos); + BigInteger b = const2big(arg2, signed2, undef_bit_pos); + if (b.isZero()) + return RTLIL::Const(RTLIL::State::Sx, result_len); + + BigInteger::Sign a_sign = a.getSign(); + BigInteger::Sign b_sign = b.getSign(); + a = a_sign == BigInteger::negative ? -a : a; + b = b_sign == BigInteger::negative ? -b : b; + BigInteger truncated = a_sign == BigInteger::negative ? -(a % b) : (a % b); + BigInteger modulo; + + if (truncated == 0 || (a_sign == b_sign)) { + modulo = truncated; + } else { + modulo = b_sign == BigInteger::negative ? truncated - b : truncated + b; + } + return big2const(modulo, result_len >= 0 ? result_len : max(arg1.bits.size(), arg2.bits.size()), min(undef_bit_pos, 0)); +} + RTLIL::Const RTLIL::const_pow(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len) { int undef_bit_pos = -1; diff --git a/kernel/celledges.cc b/kernel/celledges.cc index 54e0168e2..488ee9d02 100644 --- a/kernel/celledges.cc +++ b/kernel/celledges.cc @@ -187,7 +187,7 @@ bool YOSYS_NAMESPACE_PREFIX AbstractCellEdgesDatabase::add_edges_from_cell(RTLIL return true; } - // FIXME: $mul $div $mod $slice $concat + // FIXME: $mul $div $mod $modfloor $slice $concat // FIXME: $lut $sop $alu $lcu $macc $fa return false; diff --git a/kernel/celltypes.h b/kernel/celltypes.h index 450865ce9..37c251f7e 100644 --- a/kernel/celltypes.h +++ b/kernel/celltypes.h @@ -114,7 +114,7 @@ struct CellTypes ID($and), ID($or), ID($xor), ID($xnor), ID($shl), ID($shr), ID($sshl), ID($sshr), ID($shift), ID($shiftx), ID($lt), ID($le), ID($eq), ID($ne), ID($eqx), ID($nex), ID($ge), ID($gt), - ID($add), ID($sub), ID($mul), ID($div), ID($mod), ID($pow), + ID($add), ID($sub), ID($mul), ID($div), ID($mod), ID($modfloor), ID($pow), ID($logic_and), ID($logic_or), ID($concat), ID($macc) }; @@ -304,6 +304,7 @@ struct CellTypes HANDLE_CELL_TYPE(mul) HANDLE_CELL_TYPE(div) HANDLE_CELL_TYPE(mod) + HANDLE_CELL_TYPE(modfloor) HANDLE_CELL_TYPE(pow) HANDLE_CELL_TYPE(pos) HANDLE_CELL_TYPE(neg) diff --git a/kernel/rtlil.cc b/kernel/rtlil.cc index 196e301b6..f2480ba5a 100644 --- a/kernel/rtlil.cc +++ b/kernel/rtlil.cc @@ -948,7 +948,7 @@ namespace { return; } - if (cell->type.in(ID($add), ID($sub), ID($mul), ID($div), ID($mod), ID($pow))) { + if (cell->type.in(ID($add), ID($sub), ID($mul), ID($div), ID($mod), ID($modfloor), ID($pow))) { param_bool(ID::A_SIGNED); param_bool(ID::B_SIGNED); port(ID::A, param(ID::A_WIDTH)); @@ -1949,6 +1949,7 @@ DEF_METHOD(Sub, max(sig_a.size(), sig_b.size()), ID($sub)) DEF_METHOD(Mul, max(sig_a.size(), sig_b.size()), ID($mul)) DEF_METHOD(Div, max(sig_a.size(), sig_b.size()), ID($div)) DEF_METHOD(Mod, max(sig_a.size(), sig_b.size()), ID($mod)) +DEF_METHOD(ModFloor, max(sig_a.size(), sig_b.size()), ID($modfloor)) DEF_METHOD(LogicAnd, 1, ID($logic_and)) DEF_METHOD(LogicOr, 1, ID($logic_or)) #undef DEF_METHOD diff --git a/kernel/rtlil.h b/kernel/rtlil.h index 423c0b4bd..6bb759928 100644 --- a/kernel/rtlil.h +++ b/kernel/rtlil.h @@ -466,6 +466,7 @@ namespace RTLIL RTLIL::Const const_sub (const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len); RTLIL::Const const_mul (const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len); RTLIL::Const const_div (const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len); + RTLIL::Const const_modfloor (const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len); RTLIL::Const const_mod (const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len); RTLIL::Const const_pow (const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len); @@ -1204,6 +1205,7 @@ public: RTLIL::Cell* addMul (RTLIL::IdString name, const RTLIL::SigSpec &sig_a, const RTLIL::SigSpec &sig_b, const RTLIL::SigSpec &sig_y, bool is_signed = false, const std::string &src = ""); RTLIL::Cell* addDiv (RTLIL::IdString name, const RTLIL::SigSpec &sig_a, const RTLIL::SigSpec &sig_b, const RTLIL::SigSpec &sig_y, bool is_signed = false, const std::string &src = ""); RTLIL::Cell* addMod (RTLIL::IdString name, const RTLIL::SigSpec &sig_a, const RTLIL::SigSpec &sig_b, const RTLIL::SigSpec &sig_y, bool is_signed = false, const std::string &src = ""); + RTLIL::Cell* addModFloor (RTLIL::IdString name, const RTLIL::SigSpec &sig_a, const RTLIL::SigSpec &sig_b, const RTLIL::SigSpec &sig_y, bool is_signed = false, const std::string &src = ""); RTLIL::Cell* addPow (RTLIL::IdString name, const RTLIL::SigSpec &sig_a, const RTLIL::SigSpec &sig_b, const RTLIL::SigSpec &sig_y, bool a_signed = false, bool b_signed = false, const std::string &src = ""); RTLIL::Cell* addLogicNot (RTLIL::IdString name, const RTLIL::SigSpec &sig_a, const RTLIL::SigSpec &sig_y, bool is_signed = false, const std::string &src = ""); @@ -1303,6 +1305,7 @@ public: RTLIL::SigSpec Mul (RTLIL::IdString name, const RTLIL::SigSpec &sig_a, const RTLIL::SigSpec &sig_b, bool is_signed = false, const std::string &src = ""); RTLIL::SigSpec Div (RTLIL::IdString name, const RTLIL::SigSpec &sig_a, const RTLIL::SigSpec &sig_b, bool is_signed = false, const std::string &src = ""); RTLIL::SigSpec Mod (RTLIL::IdString name, const RTLIL::SigSpec &sig_a, const RTLIL::SigSpec &sig_b, bool is_signed = false, const std::string &src = ""); + RTLIL::SigSpec ModFloor (RTLIL::IdString name, const RTLIL::SigSpec &sig_a, const RTLIL::SigSpec &sig_b, bool is_signed = false, const std::string &src = ""); RTLIL::SigSpec Pow (RTLIL::IdString name, const RTLIL::SigSpec &sig_a, const RTLIL::SigSpec &sig_b, bool a_signed = false, bool b_signed = false, const std::string &src = ""); RTLIL::SigSpec LogicNot (RTLIL::IdString name, const RTLIL::SigSpec &sig_a, bool is_signed = false, const std::string &src = ""); diff --git a/kernel/satgen.h b/kernel/satgen.h index 88b84b7e6..1d257aa2c 100644 --- a/kernel/satgen.h +++ b/kernel/satgen.h @@ -279,7 +279,7 @@ struct SatGen bool arith_undef_handled = false; bool is_arith_compare = cell->type.in(ID($lt), ID($le), ID($ge), ID($gt)); - if (model_undef && (cell->type.in(ID($add), ID($sub), ID($mul), ID($div), ID($mod)) || is_arith_compare)) + if (model_undef && (cell->type.in(ID($add), ID($sub), ID($mul), ID($div), ID($mod), ID($modfloor)) || is_arith_compare)) { std::vector undef_a = importUndefSigSpec(cell->getPort(ID::A), timestep); std::vector undef_b = importUndefSigSpec(cell->getPort(ID::B), timestep); @@ -293,7 +293,7 @@ struct SatGen int undef_any_b = ez->expression(ezSAT::OpOr, undef_b); int undef_y_bit = ez->OR(undef_any_a, undef_any_b); - if (cell->type.in(ID($div), ID($mod))) { + if (cell->type.in(ID($div), ID($mod), ID($modfloor))) { std::vector b = importSigSpec(cell->getPort(ID::B), timestep); undef_y_bit = ez->OR(undef_y_bit, ez->NOT(ez->expression(ezSAT::OpOr, b))); } @@ -935,7 +935,7 @@ struct SatGen return true; } - if (cell->type.in(ID($div), ID($mod))) + if (cell->type.in(ID($div), ID($mod), ID($modfloor))) { std::vector a = importDefSigSpec(cell->getPort(ID::A), timestep); std::vector b = importDefSigSpec(cell->getPort(ID::B), timestep); @@ -970,16 +970,28 @@ struct SatGen } std::vector y_tmp = ignore_div_by_zero ? yy : ez->vec_var(y.size()); + + // modulo calculation + std::vector modulo_trunc; + int floored_eq_trunc; + if (cell->parameters[ID::A_SIGNED].as_bool() && cell->parameters[ID::B_SIGNED].as_bool()) { + modulo_trunc = ez->vec_ite(a.back(), ez->vec_neg(chain_buf), chain_buf); + // floor == trunc when sgn(a) == sgn(b) or trunc == 0 + floored_eq_trunc = ez->OR(ez->IFF(a.back(), b.back()), ez->NOT(ez->expression(ezSAT::OpOr, modulo_trunc))); + } else { + modulo_trunc = chain_buf; + floored_eq_trunc = ez->CONST_TRUE; + } + if (cell->type == ID($div)) { if (cell->parameters[ID::A_SIGNED].as_bool() && cell->parameters[ID::B_SIGNED].as_bool()) ez->assume(ez->vec_eq(y_tmp, ez->vec_ite(ez->XOR(a.back(), b.back()), ez->vec_neg(y_u), y_u))); else ez->assume(ez->vec_eq(y_tmp, y_u)); - } else { - if (cell->parameters[ID::A_SIGNED].as_bool() && cell->parameters[ID::B_SIGNED].as_bool()) - ez->assume(ez->vec_eq(y_tmp, ez->vec_ite(a.back(), ez->vec_neg(chain_buf), chain_buf))); - else - ez->assume(ez->vec_eq(y_tmp, chain_buf)); + } else if (cell->type == ID($mod)) { + ez->assume(ez->vec_eq(y_tmp, modulo_trunc)); + } else if (cell->type == ID($modfloor)) { + ez->assume(ez->vec_eq(y_tmp, ez->vec_ite(floored_eq_trunc, modulo_trunc, ez->vec_add(modulo_trunc, b)))); } if (ignore_div_by_zero) { @@ -996,7 +1008,8 @@ struct SatGen div_zero_result.insert(div_zero_result.end(), cell->getPort(ID::A).size(), ez->CONST_TRUE); div_zero_result.insert(div_zero_result.end(), y.size() - div_zero_result.size(), ez->CONST_FALSE); } - } else { + } else if (cell->type.in(ID($mod), ID($modfloor))) { + // a mod 0 = a int copy_a_bits = min(cell->getPort(ID::A).size(), cell->getPort(ID::B).size()); div_zero_result.insert(div_zero_result.end(), a.begin(), a.begin() + copy_a_bits); if (cell->parameters[ID::A_SIGNED].as_bool() && cell->parameters[ID::B_SIGNED].as_bool()) diff --git a/manual/PRESENTATION_Prog.tex b/manual/PRESENTATION_Prog.tex index b85eda892..4652731e9 100644 --- a/manual/PRESENTATION_Prog.tex +++ b/manual/PRESENTATION_Prog.tex @@ -307,7 +307,7 @@ cell name from the internal cell library: \begin{lstlisting}[xleftmargin=1cm, basicstyle=\ttfamily\fontsize{6pt}{7pt}\selectfont] $not $pos $neg $and $or $xor $xnor $reduce_and $reduce_or $reduce_xor $reduce_xnor $reduce_bool $shl $shr $sshl $sshr $lt $le $eq $ne $eqx $nex $ge $gt $add $sub $mul $div $mod -$pow $logic_not $logic_and $logic_or $mux $pmux $slice $concat $lut $assert $sr $dff +$modfloor $pow $logic_not $logic_and $logic_or $mux $pmux $slice $concat $lut $assert $sr $dff $dffsr $adff $dlatch $dlatchsr $memrd $memwr $mem $fsm $_NOT_ $_AND_ $_OR_ $_XOR_ $_MUX_ $_SR_NN_ $_SR_NP_ $_SR_PN_ $_SR_PP_ $_DFF_N_ $_DFF_P_ $_DFF_NN0_ $_DFF_NN1_ $_DFF_NP0_ $_DFF_NP1_ $_DFF_PN0_ $_DFF_PN1_ $_DFF_PP0_ $_DFF_PP1_ $_DFFSR_NNN_ $_DFFSR_NNP_ $_DFFSR_NPN_ $_DFFSR_NPP_ $_DFFSR_PNN_ diff --git a/passes/cmds/stat.cc b/passes/cmds/stat.cc index 6c4bc0e5b..e979685e0 100644 --- a/passes/cmds/stat.cc +++ b/passes/cmds/stat.cc @@ -109,7 +109,7 @@ struct statdata_t ID($lut), ID($and), ID($or), ID($xor), ID($xnor), ID($shl), ID($shr), ID($sshl), ID($sshr), ID($shift), ID($shiftx), ID($lt), ID($le), ID($eq), ID($ne), ID($eqx), ID($nex), ID($ge), ID($gt), - ID($add), ID($sub), ID($mul), ID($div), ID($mod), ID($pow), ID($alu))) { + ID($add), ID($sub), ID($mul), ID($div), ID($mod), ID($modfloor), ID($pow), ID($alu))) { int width_a = cell->hasPort(ID::A) ? GetSize(cell->getPort(ID::A)) : 0; int width_b = cell->hasPort(ID::B) ? GetSize(cell->getPort(ID::B)) : 0; int width_y = cell->hasPort(ID::Y) ? GetSize(cell->getPort(ID::Y)) : 0; diff --git a/passes/memory/memory_share.cc b/passes/memory/memory_share.cc index 477246687..c9ac03a6a 100644 --- a/passes/memory/memory_share.cc +++ b/passes/memory/memory_share.cc @@ -715,6 +715,7 @@ struct MemoryShareWorker cone_ct.cell_types.erase(ID($mul)); cone_ct.cell_types.erase(ID($mod)); cone_ct.cell_types.erase(ID($div)); + cone_ct.cell_types.erase(ID($modfloor)); cone_ct.cell_types.erase(ID($pow)); cone_ct.cell_types.erase(ID($shl)); cone_ct.cell_types.erase(ID($shr)); diff --git a/passes/opt/opt_expr.cc b/passes/opt/opt_expr.cc index 777a24777..1b33435b1 100644 --- a/passes/opt/opt_expr.cc +++ b/passes/opt/opt_expr.cc @@ -864,7 +864,7 @@ void replace_const_cells(RTLIL::Design *design, RTLIL::Module *module, bool cons skip_fine_alu: if (cell->type.in(ID($reduce_xor), ID($reduce_xnor), ID($shift), ID($shiftx), ID($shl), ID($shr), ID($sshl), ID($sshr), - ID($lt), ID($le), ID($ge), ID($gt), ID($neg), ID($add), ID($sub), ID($mul), ID($div), ID($mod), ID($pow))) + ID($lt), ID($le), ID($ge), ID($gt), ID($neg), ID($add), ID($sub), ID($mul), ID($div), ID($mod), ID($modfloor), ID($pow))) { RTLIL::SigSpec sig_a = assign_map(cell->getPort(ID::A)); RTLIL::SigSpec sig_b = cell->hasPort(ID::B) ? assign_map(cell->getPort(ID::B)) : RTLIL::SigSpec(); @@ -883,7 +883,7 @@ skip_fine_alu: if (0) { found_the_x_bit: cover_list("opt.opt_expr.xbit", "$reduce_xor", "$reduce_xnor", "$shl", "$shr", "$sshl", "$sshr", "$shift", "$shiftx", - "$lt", "$le", "$ge", "$gt", "$neg", "$add", "$sub", "$mul", "$div", "$mod", "$pow", cell->type.str()); + "$lt", "$le", "$ge", "$gt", "$neg", "$add", "$sub", "$mul", "$div", "$mod", "$modfloor", "$pow", cell->type.str()); if (cell->type.in(ID($reduce_xor), ID($reduce_xnor), ID($lt), ID($le), ID($ge), ID($gt))) replace_cell(assign_map, module, cell, "x-bit in input", ID::Y, RTLIL::State::Sx); else @@ -1469,6 +1469,7 @@ skip_identity: FOLD_2ARG_CELL(mul) FOLD_2ARG_CELL(div) FOLD_2ARG_CELL(mod) + FOLD_2ARG_CELL(modfloor) FOLD_2ARG_CELL(pow) FOLD_1ARG_CELL(pos) @@ -1583,9 +1584,11 @@ skip_identity: } } - if (!keepdc && cell->type.in(ID($div), ID($mod))) + if (!keepdc && cell->type.in(ID($div), ID($mod), ID($modfloor))) { + bool a_signed = cell->parameters[ID::A_SIGNED].as_bool(); bool b_signed = cell->parameters[ID::B_SIGNED].as_bool(); + SigSpec sig_a = assign_map(cell->getPort(ID::A)); SigSpec sig_b = assign_map(cell->getPort(ID::B)); SigSpec sig_y = assign_map(cell->getPort(ID::Y)); @@ -1628,11 +1631,13 @@ skip_identity: cell->setPort(ID::B, new_b); cell->check(); } - else + else if (cell->type.in(ID($mod), ID($modfloor))) { cover("opt.opt_expr.mod_mask"); - log_debug("Replacing modulo-by-%d cell `%s' in module `%s' with bitmask.\n", + bool is_truncating = cell->type == ID($mod); + log_debug("Replacing %s-modulo-by-%d cell `%s' in module `%s' with bitmask.\n", + is_truncating ? "truncating" : "flooring", b_val, cell->name.c_str(), module->name.c_str()); std::vector new_b = RTLIL::SigSpec(State::S1, i); @@ -1643,6 +1648,24 @@ skip_identity: cell->type = ID($and); cell->parameters[ID::B_WIDTH] = GetSize(new_b); cell->setPort(ID::B, new_b); + + // truncating modulo has the same masked bits as flooring modulo, but + // the sign bits are those of A (except when R=0) + if (is_truncating && a_signed) { + Wire *flooring = module->addWire(NEW_ID, sig_y.size()); + cell->setPort(ID::Y, flooring); + SigSpec truncating = SigSpec(flooring).extract(0, i); + + Wire *rem_nonzero = module->addWire(NEW_ID); + module->addReduceOr(NEW_ID, truncating, rem_nonzero); + SigSpec a_sign = sig_a[sig_a.size()-1]; + Wire *extend_bit = module->addWire(NEW_ID); + module->addAnd(NEW_ID, a_sign, rem_nonzero, extend_bit); + + truncating.append(extend_bit); + module->addPos(NEW_ID, truncating, sig_y, true); + } + cell->check(); } diff --git a/passes/opt/opt_share.cc b/passes/opt/opt_share.cc index 1f69c98f4..b08a8172f 100644 --- a/passes/opt/opt_share.cc +++ b/passes/opt/opt_share.cc @@ -103,7 +103,7 @@ bool cell_supported(RTLIL::Cell *cell) 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, ID($add), ID($sub), ID($mul), ID($div), ID($mod), ID($concat))) { + } else if (cell->type.in(LOGICAL_OPS, SHIFT_OPS, BITWISE_OPS, RELATIONAL_OPS, ID($add), ID($sub), ID($mul), ID($div), ID($mod), ID($modfloor), ID($concat))) { return true; } @@ -130,7 +130,7 @@ bool mergeable(RTLIL::Cell *a, RTLIL::Cell *b) RTLIL::IdString decode_port_semantics(RTLIL::Cell *cell, RTLIL::IdString port_name) { - if (cell->type.in(ID($lt), ID($le), ID($ge), ID($gt), ID($div), ID($mod), ID($concat), SHIFT_OPS) && port_name == ID::B) + if (cell->type.in(ID($lt), ID($le), ID($ge), ID($gt), ID($div), ID($mod), ID($modfloor), ID($concat), SHIFT_OPS) && port_name == ID::B) return port_name; return ""; diff --git a/passes/opt/share.cc b/passes/opt/share.cc index 2839507b0..1c8942df0 100644 --- a/passes/opt/share.cc +++ b/passes/opt/share.cc @@ -376,7 +376,7 @@ struct ShareWorker continue; } - if (cell->type.in(ID($mul), ID($div), ID($mod))) { + if (cell->type.in(ID($mul), ID($div), ID($mod), ID($modfloor))) { if (config.opt_aggressive || cell->parameters.at(ID::Y_WIDTH).as_int() >= 4) shareable_cells.insert(cell); continue; @@ -1133,6 +1133,7 @@ struct ShareWorker cone_ct.cell_types.erase(ID($mul)); cone_ct.cell_types.erase(ID($mod)); cone_ct.cell_types.erase(ID($div)); + cone_ct.cell_types.erase(ID($modfloor)); cone_ct.cell_types.erase(ID($pow)); cone_ct.cell_types.erase(ID($shl)); cone_ct.cell_types.erase(ID($shr)); @@ -1512,6 +1513,7 @@ struct SharePass : public Pass { config.generic_bin_ops.insert(ID($sub)); config.generic_bin_ops.insert(ID($div)); config.generic_bin_ops.insert(ID($mod)); + config.generic_bin_ops.insert(ID($modfloor)); // config.generic_bin_ops.insert(ID($pow)); config.generic_uni_ops.insert(ID($logic_not)); diff --git a/passes/opt/wreduce.cc b/passes/opt/wreduce.cc index 195400bf0..17b957d23 100644 --- a/passes/opt/wreduce.cc +++ b/passes/opt/wreduce.cc @@ -37,7 +37,7 @@ struct WreduceConfig ID($and), ID($or), ID($xor), ID($xnor), ID($shl), ID($shr), ID($sshl), ID($sshr), ID($shift), ID($shiftx), ID($lt), ID($le), ID($eq), ID($ne), ID($eqx), ID($nex), ID($ge), ID($gt), - ID($add), ID($sub), ID($mul), // ID($div), ID($mod), ID($pow), + ID($add), ID($sub), ID($mul), // ID($div), ID($mod), ID($modfloor), ID($pow), ID($mux), ID($pmux), ID($dff), ID($adff) }); @@ -545,7 +545,7 @@ struct WreducePass : public Pass { } } - if (c->type.in(ID($div), ID($mod), ID($pow))) + if (c->type.in(ID($div), ID($mod), ID($modfloor), ID($pow))) { SigSpec A = c->getPort(ID::A); int original_a_width = GetSize(A); diff --git a/passes/tests/test_cell.cc b/passes/tests/test_cell.cc index cdbe922b2..bc5ff598e 100644 --- a/passes/tests/test_cell.cc +++ b/passes/tests/test_cell.cc @@ -264,7 +264,7 @@ static void create_gold_module(RTLIL::Design *design, RTLIL::IdString cell_type, cell->setPort(ID::Y, wire); } - if (muxdiv && cell_type.in(ID($div), ID($mod))) { + if (muxdiv && cell_type.in(ID($div), ID($mod), ID($modfloor))) { auto b_not_zero = module->ReduceBool(NEW_ID, cell->getPort(ID::B)); auto div_out = module->addWire(NEW_ID, GetSize(cell->getPort(ID::Y))); module->addMux(NEW_ID, RTLIL::SigSpec(0, GetSize(div_out)), div_out, b_not_zero, cell->getPort(ID::Y)); @@ -839,6 +839,7 @@ struct TestCellPass : public Pass { cell_types[ID($mul)] = "ABSY"; cell_types[ID($div)] = "ABSY"; cell_types[ID($mod)] = "ABSY"; + cell_types[ID($modfloor)] = "ABSY"; // cell_types[ID($pow)] = "ABsY"; cell_types[ID($logic_not)] = "ASY"; diff --git a/techlibs/common/simlib.v b/techlibs/common/simlib.v index 2cdddeabb..57fc07caa 100644 --- a/techlibs/common/simlib.v +++ b/techlibs/common/simlib.v @@ -1021,6 +1021,14 @@ endmodule // -------------------------------------------------------- +// |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| +//- +//- $mod (A, B, Y) +//- +//- Modulo/remainder of division with truncated result (rounded towards 0). +//- +//- Invariant: $div(A, B) * B + $mod(A, B) == A +//- module \$mod (A, B, Y); parameter A_SIGNED = 0; @@ -1043,6 +1051,46 @@ endgenerate endmodule +// -------------------------------------------------------- + +// |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| +//- +//- $modfloor (A, B, Y) +//- +//- Modulo/remainder of division with floored result (rounded towards negative infinity). +//- +//- Invariant: $divfloor(A, B) * B + $modfloor(A, B) == A +//- +module \$modfloor (A, B, Y); + +parameter A_SIGNED = 0; +parameter B_SIGNED = 0; +parameter A_WIDTH = 0; +parameter B_WIDTH = 0; +parameter Y_WIDTH = 0; + +input [A_WIDTH-1:0] A; +input [B_WIDTH-1:0] B; +output [Y_WIDTH-1:0] Y; + +generate + if (A_SIGNED && B_SIGNED) begin:BLOCK1 + localparam WIDTH = B_WIDTH >= Y_WIDTH ? B_WIDTH : Y_WIDTH; + wire [WIDTH-1:0] B_buf, Y_trunc; + assign B_buf = $signed(B); + assign Y_trunc = $signed(A) % $signed(B); + // flooring mod is the same as truncating mod for positive division results (A and B have + // the same sign), as well as when there's no remainder. + // For all other cases, they behave as `floor - trunc = B` + assign Y = (A[A_WIDTH-1] == B[B_WIDTH-1]) || Y_trunc == 0 ? Y_trunc : $signed(B_buf) + $signed(Y_trunc); + end else begin:BLOCK2 + // no difference between truncating and flooring for unsigned + assign Y = A % B; + end +endgenerate + +endmodule + // -------------------------------------------------------- `ifndef SIMLIB_NOPOW diff --git a/techlibs/common/techmap.v b/techlibs/common/techmap.v index c1efc378b..95223180d 100644 --- a/techlibs/common/techmap.v +++ b/techlibs/common/techmap.v @@ -364,7 +364,8 @@ module \$__div_mod_u (A, B, Y, R); end endgenerate endmodule -module \$__div_mod (A, B, Y, R); +// truncating signed division/modulo +module \$__div_mod_trunc (A, B, Y, R); parameter A_SIGNED = 0; parameter B_SIGNED = 0; parameter A_WIDTH = 1; @@ -420,7 +421,7 @@ module _90_div (A, B, Y); (* force_downto *) output [Y_WIDTH-1:0] Y; - \$__div_mod #( + \$__div_mod_trunc #( .A_SIGNED(A_SIGNED), .B_SIGNED(B_SIGNED), .A_WIDTH(A_WIDTH), @@ -448,7 +449,79 @@ module _90_mod (A, B, Y); (* force_downto *) output [Y_WIDTH-1:0] Y; - \$__div_mod #( + \$__div_mod_trunc #( + .A_SIGNED(A_SIGNED), + .B_SIGNED(B_SIGNED), + .A_WIDTH(A_WIDTH), + .B_WIDTH(B_WIDTH), + .Y_WIDTH(Y_WIDTH) + ) div_mod ( + .A(A), + .B(B), + .R(Y) + ); +endmodule + +// flooring signed division/modulo +module \$__div_mod_floor (A, B, Y, R); + parameter A_SIGNED = 0; + parameter B_SIGNED = 0; + parameter A_WIDTH = 1; + parameter B_WIDTH = 1; + parameter Y_WIDTH = 1; + + localparam WIDTH = + A_WIDTH >= B_WIDTH && A_WIDTH >= Y_WIDTH ? A_WIDTH : + B_WIDTH >= A_WIDTH && B_WIDTH >= Y_WIDTH ? B_WIDTH : Y_WIDTH; + + input [A_WIDTH-1:0] A; + input [B_WIDTH-1:0] B; + output [Y_WIDTH-1:0] Y, R; + + wire [WIDTH-1:0] A_buf, B_buf; + \$pos #(.A_SIGNED(A_SIGNED), .A_WIDTH(A_WIDTH), .Y_WIDTH(WIDTH)) A_conv (.A(A), .Y(A_buf)); + \$pos #(.A_SIGNED(B_SIGNED), .A_WIDTH(B_WIDTH), .Y_WIDTH(WIDTH)) B_conv (.A(B), .Y(B_buf)); + + wire [WIDTH-1:0] A_buf_u, B_buf_u, Y_u, R_u, R_s; + assign A_buf_u = A_SIGNED && A_buf[WIDTH-1] ? -A_buf : A_buf; + assign B_buf_u = B_SIGNED && B_buf[WIDTH-1] ? -B_buf : B_buf; + + \$__div_mod_u #( + .WIDTH(WIDTH) + ) div_mod_u ( + .A(A_buf_u), + .B(B_buf_u), + .Y(Y_u), + .R(R_u) + ); + + // For negative results, if there was a remainder, subtract one to turn + // the round towards 0 into a round towards -inf + assign Y = A_SIGNED && B_SIGNED && (A_buf[WIDTH-1] != B_buf[WIDTH-1]) ? (R_u == 0 ? -Y_u : -Y_u-1) : Y_u; + + // truncating modulo + assign R_s = A_SIGNED && B_SIGNED && A_buf[WIDTH-1] ? -R_u : R_u; + // Flooring modulo differs from truncating modulo only if it is nonzero and + // A and B have different signs - then `floor - trunc = B` + assign R = (R_s != 0) && A_SIGNED && B_SIGNED && (A_buf[WIDTH-1] != B_buf[WIDTH-1]) ? $signed(B_buf) + $signed(R_s) : R_s; +endmodule + +(* techmap_celltype = "$modfloor" *) +module _90_modfloor (A, B, Y); + parameter A_SIGNED = 0; + parameter B_SIGNED = 0; + parameter A_WIDTH = 1; + parameter B_WIDTH = 1; + parameter Y_WIDTH = 1; + + (* force_downto *) + input [A_WIDTH-1:0] A; + (* force_downto *) + input [B_WIDTH-1:0] B; + (* force_downto *) + output [Y_WIDTH-1:0] Y; + + \$__div_mod_floor #( .A_SIGNED(A_SIGNED), .B_SIGNED(B_SIGNED), .A_WIDTH(A_WIDTH), -- 2.30.2