Merge remote-tracking branch 'origin/clifford/fix1091' into xc7mux_wip

2 files changed, 239 insertions, 46 deletions

diff --git a/passes/techmap/muxcover.cc b/passes/techmap/muxcover.cc
index 8e44be148..b0722134e 100644
--- a/passes/techmap/muxcover.cc
+++ b/passes/techmap/muxcover.cc
@@ -23,6 +23,7 @@
 USING_YOSYS_NAMESPACE
 PRIVATE_NAMESPACE_BEGIN
 
+#define COST_DMUX   90
 #define COST_MUX2  100
 #define COST_MUX4  220
 #define COST_MUX8  460
@@ -57,7 +58,9 @@ struct MuxcoverWorker
 	bool use_mux8;
 	bool use_mux16;
 	bool nodecode;
+	bool nopartial;
 
+	int cost_dmux;
 	int cost_mux2;
 	int cost_mux4;
 	int cost_mux8;
@@ -69,6 +72,8 @@ struct MuxcoverWorker
 		use_mux8 = false;
 		use_mux16 = false;
 		nodecode = false;
+		nopartial = false;
+		cost_dmux = COST_DMUX;
 		cost_mux2 = COST_MUX2;
 		cost_mux4 = COST_MUX4;
 		cost_mux8 = COST_MUX8;
@@ -133,13 +138,20 @@ struct MuxcoverWorker
 		log("    Finished treeification: Found %d trees.\n", GetSize(tree_list));
 	}
 
-	bool follow_muxtree(SigBit &ret_bit, tree_t &tree, SigBit bit, const char *path)
+	bool follow_muxtree(SigBit &ret_bit, tree_t &tree, SigBit bit, const char *path, bool first_layer = true)
 	{
 		if (*path) {
-			if (tree.muxes.count(bit) == 0)
-				return false;
+			if (tree.muxes.count(bit) == 0) {
+				if (first_layer || nopartial)
+					return false;
+				if (path[0] == 'S')
+					ret_bit = State::Sx;
+				else
+					ret_bit = bit;
+				return true;
+			}
 			char port_name[3] = {'\\', *path, 0};
-			return follow_muxtree(ret_bit, tree, sigmap(tree.muxes.at(bit)->getPort(port_name)), path+1);
+			return follow_muxtree(ret_bit, tree, sigmap(tree.muxes.at(bit)->getPort(port_name)), path+1, false);
 		} else {
 			ret_bit = bit;
 			return true;
@@ -148,7 +160,7 @@ struct MuxcoverWorker
 
 	int prepare_decode_mux(SigBit &A, SigBit B, SigBit sel, SigBit bit)
 	{
-		if (A == B)
+		if (A == B || sel == State::Sx)
 			return 0;
 
 		tuple<SigBit, SigBit, SigBit> key(A, B, sel);
@@ -166,7 +178,10 @@ struct MuxcoverWorker
 		if (std::get<2>(entry))
 			return 0;
 
-		return cost_mux2 / GetSize(std::get<1>(entry));
+		if (A == State::Sx || B == State::Sx)
+			return 0;
+
+		return cost_dmux / GetSize(std::get<1>(entry));
 	}
 
 	void implement_decode_mux(SigBit ctrl_bit)
@@ -183,9 +198,32 @@ struct MuxcoverWorker
 		implement_decode_mux(std::get<0>(key));
 		implement_decode_mux(std::get<1>(key));
 
-		module->addMuxGate(NEW_ID, std::get<0>(key), std::get<1>(key), std::get<2>(key), ctrl_bit);
+		if (std::get<0>(key) == State::Sx) {
+			module->addBufGate(NEW_ID, std::get<1>(key), ctrl_bit);
+		} else if (std::get<1>(key) == State::Sx) {
+			module->addBufGate(NEW_ID, std::get<0>(key), ctrl_bit);
+		} else {
+			module->addMuxGate(NEW_ID, std::get<0>(key), std::get<1>(key), std::get<2>(key), ctrl_bit);
+			decode_mux_counter++;
+		}
 		std::get<2>(entry) = true;
-		decode_mux_counter++;
+	}
+
+	void find_best_covers(tree_t &tree, const vector<SigBit> &bits)
+	{
+		for (auto bit : bits)
+			find_best_cover(tree, bit);
+	}
+
+	int sum_best_covers(tree_t &tree, const vector<SigBit> &bits)
+	{
+		int sum = 0;
+		for (auto bit : pool<SigBit>(bits.begin(), bits.end())) {
+			int cost = tree.newmuxes.at(bit).cost;
+			log_debug("        Best cost for %s: %d\n", log_signal(bit), cost);
+			sum += cost;
+		}
+		return sum;
 	}
 
 	int find_best_cover(tree_t &tree, SigBit bit)
@@ -218,9 +256,13 @@ struct MuxcoverWorker
 			mux.inputs.push_back(B);
 			mux.selects.push_back(S1);
 
+			find_best_covers(tree, mux.inputs);
+			log_debug("        Decode cost for mux2 at %s: %d\n", log_signal(bit), mux.cost);
+
 			mux.cost += cost_mux2;
-			mux.cost += find_best_cover(tree, A);
-			mux.cost += find_best_cover(tree, B);
+			mux.cost += sum_best_covers(tree, mux.inputs);
+
+			log_debug("      Cost of mux2 at %s: %d\n", log_signal(bit), mux.cost);
 
 			best_mux = mux;
 		}
@@ -256,13 +298,15 @@ struct MuxcoverWorker
 				mux.selects.push_back(S1);
 				mux.selects.push_back(T1);
 
+				find_best_covers(tree, mux.inputs);
+				log_debug("        Decode cost for mux4 at %s: %d\n", log_signal(bit), mux.cost);
+
 				mux.cost += cost_mux4;
-				mux.cost += find_best_cover(tree, A);
-				mux.cost += find_best_cover(tree, B);
-				mux.cost += find_best_cover(tree, C);
-				mux.cost += find_best_cover(tree, D);
+				mux.cost += sum_best_covers(tree, mux.inputs);
 
-				if (best_mux.cost > mux.cost)
+				log_debug("      Cost of mux4 at %s: %d\n", log_signal(bit), mux.cost);
+
+				if (best_mux.cost >= mux.cost)
 					best_mux = mux;
 			}
 		}
@@ -319,17 +363,15 @@ struct MuxcoverWorker
 				mux.selects.push_back(T1);
 				mux.selects.push_back(U1);
 
+				find_best_covers(tree, mux.inputs);
+				log_debug("        Decode cost for mux8 at %s: %d\n", log_signal(bit), mux.cost);
+
 				mux.cost += cost_mux8;
-				mux.cost += find_best_cover(tree, A);
-				mux.cost += find_best_cover(tree, B);
-				mux.cost += find_best_cover(tree, C);
-				mux.cost += find_best_cover(tree, D);
-				mux.cost += find_best_cover(tree, E);
-				mux.cost += find_best_cover(tree, F);
-				mux.cost += find_best_cover(tree, G);
-				mux.cost += find_best_cover(tree, H);
-
-				if (best_mux.cost > mux.cost)
+				mux.cost += sum_best_covers(tree, mux.inputs);
+
+				log_debug("      Cost of mux8 at %s: %d\n", log_signal(bit), mux.cost);
+
+				if (best_mux.cost >= mux.cost)
 					best_mux = mux;
 			}
 		}
@@ -423,25 +465,15 @@ struct MuxcoverWorker
 				mux.selects.push_back(U1);
 				mux.selects.push_back(V1);
 
+				find_best_covers(tree, mux.inputs);
+				log_debug("        Decode cost for mux16 at %s: %d\n", log_signal(bit), mux.cost);
+
 				mux.cost += cost_mux16;
-				mux.cost += find_best_cover(tree, A);
-				mux.cost += find_best_cover(tree, B);
-				mux.cost += find_best_cover(tree, C);
-				mux.cost += find_best_cover(tree, D);
-				mux.cost += find_best_cover(tree, E);
-				mux.cost += find_best_cover(tree, F);
-				mux.cost += find_best_cover(tree, G);
-				mux.cost += find_best_cover(tree, H);
-				mux.cost += find_best_cover(tree, I);
-				mux.cost += find_best_cover(tree, J);
-				mux.cost += find_best_cover(tree, K);
-				mux.cost += find_best_cover(tree, L);
-				mux.cost += find_best_cover(tree, M);
-				mux.cost += find_best_cover(tree, N);
-				mux.cost += find_best_cover(tree, O);
-				mux.cost += find_best_cover(tree, P);
-
-				if (best_mux.cost > mux.cost)
+				mux.cost += sum_best_covers(tree, mux.inputs);
+
+				log_debug("      Cost of mux16 at %s: %d\n", log_signal(bit), mux.cost);
+
+				if (best_mux.cost >= mux.cost)
 					best_mux = mux;
 			}
 		}
@@ -537,6 +569,7 @@ struct MuxcoverWorker
 	void treecover(tree_t &tree)
 	{
 		int count_muxes_by_type[4] = {0, 0, 0, 0};
+		log_debug("    Searching for best cover for tree at %s.\n", log_signal(tree.root));
 		find_best_cover(tree, tree.root);
 		implement_best_cover(tree, tree.root, count_muxes_by_type);
 		log("    Replaced tree at %s: %d MUX2, %d MUX4, %d MUX8, %d MUX16\n", log_signal(tree.root),
@@ -553,12 +586,13 @@ struct MuxcoverWorker
 
 		log("  Covering trees:\n");
 
-		// pre-fill cache of decoder muxes
-		if (!nodecode)
+		if (!nodecode) {
+			log_debug("    Populating cache of decoder muxes.\n");
 			for (auto &tree : tree_list) {
 				find_best_cover(tree, tree.root);
 				tree.newmuxes.clear();
 			}
+		}
 
 		for (auto &tree : tree_list)
 			treecover(tree);
@@ -584,11 +618,19 @@ struct MuxcoverPass : public Pass {
 		log("        Default costs: $_MUX_ = %d, $_MUX4_ = %d,\n", COST_MUX2, COST_MUX4);
 		log("                       $_MUX8_ = %d, $_MUX16_ = %d\n", COST_MUX8, COST_MUX16);
 		log("\n");
+		log("    -dmux=cost\n");
+		log("        Use the specified cost for $_MUX_ cells used in decoders.\n");
+		log("        Default cost: %d\n", COST_DMUX);
+		log("\n");
 		log("    -nodecode\n");
 		log("        Do not insert decoder logic. This reduces the number of possible\n");
 		log("        substitutions, but guarantees that the resulting circuit is not\n");
 		log("        less efficient than the original circuit.\n");
 		log("\n");
+		log("    -nopartial\n");
+		log("        Do not consider mappings that use $_MUX<N>_ to select from less\n");
+		log("        than <N> different signals.\n");
+		log("\n");
 	}
 	void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
 	{
@@ -598,6 +640,8 @@ struct MuxcoverPass : public Pass {
 		bool use_mux8 = false;
 		bool use_mux16 = false;
 		bool nodecode = false;
+		bool nopartial = false;
+		int cost_dmux = COST_DMUX;
 		int cost_mux4 = COST_MUX4;
 		int cost_mux8 = COST_MUX8;
 		int cost_mux16 = COST_MUX16;
@@ -630,10 +674,18 @@ struct MuxcoverPass : public Pass {
 				}
 				continue;
 			}
+			if (arg.size() >= 6 && arg.substr(0,6) == "-dmux=") {
+				cost_dmux = atoi(arg.substr(6).c_str());
+				continue;
+			}
 			if (arg == "-nodecode") {
 				nodecode = true;
 				continue;
 			}
+			if (arg == "-nopartial") {
+				nopartial = true;
+				continue;
+			}
 			break;
 		}
 		extra_args(args, argidx, design);
@@ -650,10 +702,12 @@ struct MuxcoverPass : public Pass {
 			worker.use_mux4 = use_mux4;
 			worker.use_mux8 = use_mux8;
 			worker.use_mux16 = use_mux16;
+			worker.cost_dmux = cost_dmux;
 			worker.cost_mux4 = cost_mux4;
 			worker.cost_mux8 = cost_mux8;
 			worker.cost_mux16 = cost_mux16;
 			worker.nodecode = nodecode;
+			worker.nopartial = nopartial;
 			worker.run();
 		}
 	}
diff --git a/tests/various/muxcover.ys b/tests/various/muxcover.ys
index 7ac460f13..8ef619b46 100644
--- a/tests/various/muxcover.ys
+++ b/tests/various/muxcover.ys
@@ -13,7 +13,7 @@ read_verilog -formal <<EOT
 EOT
 
 
-## Examle usage for "pmuxtree" and "muxcover"
+## Example usage for "pmuxtree" and "muxcover"
 
 proc
 pmuxtree
@@ -49,3 +49,142 @@ hierarchy -top equiv
 equiv_simple -undef
 equiv_status -assert
 
+## Partial matching MUX4
+
+design -reset
+read_verilog -formal <<EOT
+module mux_if_bal_3_1 #(parameter N=3, parameter W=1) (input [N*W-1:0] i, input [$clog2(N)-1:0] s, output reg [W-1:0] o);
+always @* begin
+    o <= {{W{{1'bx}}}};
+    if (s[0] == 1'b0)
+     if (s[1] == 1'b0)
+      o <= i[0*W+:W];
+     else
+      o <= i[1*W+:W];
+    else
+     if (s[1] == 1'b0)
+      o <= i[2*W+:W];
+end
+endmodule
+EOT
+prep
+design -save gold
+
+techmap
+muxcover -mux4=150
+select -assert-count 0 t:$_MUX_
+select -assert-count 1 t:$_MUX4_
+select -assert-count 0 t:$_MUX8_
+select -assert-count 0 t:$_MUX16_
+techmap -map +/simcells.v t:$_MUX4_
+design -stash gate
+
+design -import gold -as gold
+design -import gate -as gate
+
+miter -equiv -flatten -make_assert -make_outputs gold gate miter
+sat -verify -prove-asserts -show-ports miter
+
+## Partial matching MUX8
+
+design -reset
+read_verilog -formal <<EOT
+module mux_if_bal_5_1 #(parameter N=5, parameter W=1) (input [N*W-1:0] i, input [$clog2(N)-1:0] s, output reg [W-1:0] o);
+always @* begin
+    o <= {{W{{1'bx}}}};
+    if (s[0] == 1'b0)
+     if (s[1] == 1'b0)
+      if (s[2] == 1'b0)
+       o <= i[0*W+:W];
+      else
+       o <= i[1*W+:W];
+     else
+      if (s[2] == 1'b0)
+       o <= i[2*W+:W];
+      else
+       o <= i[3*W+:W];
+    else
+     if (s[1] == 1'b0)
+      if (s[2] == 1'b0)
+       o <= i[4*W+:W];
+end
+endmodule
+EOT
+prep
+design -save gold
+
+techmap
+muxcover -mux4=150 -mux8=200
+clean
+opt_expr -mux_bool
+select -assert-count 0 t:$_MUX_
+select -assert-count 0 t:$_MUX4_
+select -assert-count 1 t:$_MUX8_
+select -assert-count 0 t:$_MUX16_
+techmap -map +/simcells.v t:$_MUX8_
+design -stash gate
+
+design -import gold -as gold
+design -import gate -as gate
+
+miter -equiv -flatten -make_assert -make_outputs gold gate miter
+sat -verify -prove-asserts -show-ports miter
+
+## Partial matching MUX16
+
+design -reset
+read_verilog -formal <<EOT
+module mux_if_bal_9_1 #(parameter N=9, parameter W=1) (input [N*W-1:0] i, input [$clog2(N)-1:0] s, output reg [W-1:0] o);
+always @* begin
+    o <= {{W{{1'bx}}}};
+    if (s[0] == 1'b0)
+     if (s[1] == 1'b0)
+      if (s[2] == 1'b0)
+       if (s[3] == 1'b0)
+        o <= i[0*W+:W];
+       else
+        o <= i[1*W+:W];
+      else
+       if (s[3] == 1'b0)
+        o <= i[2*W+:W];
+       else
+        o <= i[3*W+:W];
+     else
+      if (s[2] == 1'b0)
+       if (s[3] == 1'b0)
+        o <= i[4*W+:W];
+       else
+        o <= i[5*W+:W];
+      else
+       if (s[3] == 1'b0)
+        o <= i[6*W+:W];
+       else
+        o <= i[7*W+:W];
+    else
+     if (s[1] == 1'b0)
+      if (s[2] == 1'b0)
+       if (s[3] == 1'b0)
+        o <= i[8*W+:W];
+end
+endmodule
+EOT
+prep
+design -save gold
+
+techmap
+muxcover -mux4=150 -mux8=200 -mux16=250
+clean
+opt_expr -mux_bool
+select -assert-count 0 t:$_MUX_
+select -assert-count 0 t:$_MUX4_
+select -assert-count 0 t:$_MUX8_
+select -assert-count 1 t:$_MUX16_
+techmap -map +/simcells.v t:$_MUX16_
+design -stash gate
+
+design -import gold -as gold
+design -import gate -as gate
+
+miter -equiv -flatten -make_assert -make_outputs gold gate miter
+sat -verify -prove-asserts -show-ports miter
+