From 17163cf43a6b6eec9aac44f6a4463dda54b8ed68 Mon Sep 17 00:00:00 2001 From: Xiretza Date: Wed, 8 Apr 2020 19:30:47 +0200 Subject: 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. --- kernel/calc.cc | 25 +++++++++++++++++++++++++ kernel/celledges.cc | 2 +- kernel/celltypes.h | 3 ++- kernel/rtlil.cc | 3 ++- kernel/rtlil.h | 3 +++ kernel/satgen.h | 31 ++++++++++++++++++++++--------- 6 files changed, 55 insertions(+), 12 deletions(-) (limited to 'kernel') 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()) -- cgit v1.2.3