Merge pull request #1885 from Xiretza/mod-rem-cells

Fix modulo/remainder semantics

7 files changed, 65 insertions, 15 deletions

diff --git a/passes/cmds/stat.cc b/passes/cmds/stat.cc
index 6c4bc0e5b..30436d829 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($divfloor), 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..e11958bd6 100644
--- a/passes/memory/memory_share.cc
+++ b/passes/memory/memory_share.cc
@@ -715,6 +715,8 @@ 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($divfloor));
 		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..e5b8bda95 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($divfloor), 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", "$divfloor", "$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,8 @@ skip_identity:
 		FOLD_2ARG_CELL(mul)
 		FOLD_2ARG_CELL(div)
 		FOLD_2ARG_CELL(mod)
+		FOLD_2ARG_CELL(divfloor)
+		FOLD_2ARG_CELL(modfloor)
 		FOLD_2ARG_CELL(pow)
 
 		FOLD_1ARG_CELL(pos)
@@ -1583,9 +1585,11 @@ skip_identity:
 			}
 		}
 
-		if (!keepdc && cell->type.in(ID($div), ID($mod)))
+		if (!keepdc && cell->type.in(ID($div), ID($mod), ID($divfloor), 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));
 
@@ -1610,11 +1614,13 @@ skip_identity:
 				for (int i = 1; i < (b_signed ? sig_b.size()-1 : sig_b.size()); i++)
 					if (b_val == (1 << i))
 					{
-						if (cell->type == ID($div))
+						if (cell->type.in(ID($div), ID($divfloor)))
 						{
 							cover("opt.opt_expr.div_shift");
 
-							log_debug("Replacing divide-by-%d cell `%s' in module `%s' with shift-by-%d.\n",
+							bool is_truncating = cell->type == ID($div);
+							log_debug("Replacing %s-divide-by-%d cell `%s' in module `%s' with shift-by-%d.\n",
+									is_truncating ? "truncating" : "flooring",
 									b_val, cell->name.c_str(), module->name.c_str(), i);
 
 							std::vector<RTLIL::SigBit> new_b = RTLIL::SigSpec(i, 6);
@@ -1622,17 +1628,35 @@ skip_identity:
 							while (GetSize(new_b) > 1 && new_b.back() == RTLIL::State::S0)
 								new_b.pop_back();
 
-							cell->type = ID($shr);
+							cell->type = ID($sshr);
 							cell->parameters[ID::B_WIDTH] = GetSize(new_b);
 							cell->parameters[ID::B_SIGNED] = false;
 							cell->setPort(ID::B, new_b);
+
+							// Truncating division is the same as flooring division, except when
+							// the result is negative and there is a remainder - then trunc = floor + 1
+							if (is_truncating && a_signed) {
+								Wire *flooring = module->addWire(NEW_ID, sig_y.size());
+								cell->setPort(ID::Y, flooring);
+
+								Wire *result_neg = module->addWire(NEW_ID);
+								module->addXor(NEW_ID, sig_a[sig_a.size()-1], sig_b[sig_b.size()-1], result_neg);
+								Wire *rem_nonzero = module->addWire(NEW_ID);
+								module->addReduceOr(NEW_ID, sig_a.extract(0, i), rem_nonzero);
+								Wire *should_add = module->addWire(NEW_ID);
+								module->addAnd(NEW_ID, result_neg, rem_nonzero, should_add);
+								module->addAdd(NEW_ID, flooring, should_add, sig_y);
+							}
+
 							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<RTLIL::SigBit> new_b = RTLIL::SigSpec(State::S1, i);
@@ -1643,6 +1667,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..cbace7bac 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($divfloor), 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($divfloor), 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..988253edf 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($divfloor), ID($modfloor))) {
 				if (config.opt_aggressive || cell->parameters.at(ID::Y_WIDTH).as_int() >= 4)
 					shareable_cells.insert(cell);
 				continue;
@@ -1133,6 +1133,8 @@ 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($divfloor));
 		cone_ct.cell_types.erase(ID($pow));
 		cone_ct.cell_types.erase(ID($shl));
 		cone_ct.cell_types.erase(ID($shr));
@@ -1512,6 +1514,8 @@ 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($divfloor));
+		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..f60f2f8a8 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($divfloor), 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($divfloor), 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..c6801007d 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($divfloor), 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,8 @@ struct TestCellPass : public Pass {
 		cell_types[ID($mul)] = "ABSY";
 		cell_types[ID($div)] = "ABSY";
 		cell_types[ID($mod)] = "ABSY";
+		cell_types[ID($divfloor)] = "ABSY";
+		cell_types[ID($modfloor)] = "ABSY";
 		// cell_types[ID($pow)] = "ABsY";
 
 		cell_types[ID($logic_not)] = "ASY";