Merge remote-tracking branch 'origin/xaig' into xc7mux

7 files changed, 235 insertions, 35 deletions

diff --git a/passes/memory/memory_dff.cc b/passes/memory/memory_dff.cc
index 220d29295..5215cce44 100644
--- a/passes/memory/memory_dff.cc
+++ b/passes/memory/memory_dff.cc
@@ -182,11 +182,17 @@ struct MemoryDffWorker
 
 		if (mux_cells_a.count(sig_data) || mux_cells_b.count(sig_data))
 		{
-			bool enable_invert = mux_cells_a.count(sig_data) != 0;
-			Cell *mux = enable_invert ? mux_cells_a.at(sig_data) : mux_cells_b.at(sig_data);
-			SigSpec check_q = sigmap(mux->getPort(enable_invert ? "\\B" : "\\A"));
+			RTLIL::SigSpec en;
+			RTLIL::SigSpec check_q;
+
+			do {
+				bool enable_invert = mux_cells_a.count(sig_data) != 0;
+				Cell *mux = enable_invert ? mux_cells_a.at(sig_data) : mux_cells_b.at(sig_data);
+				check_q = sigmap(mux->getPort(enable_invert ? "\\B" : "\\A"));
+				sig_data = sigmap(mux->getPort("\\Y"));
+				en.append(enable_invert ? module->LogicNot(NEW_ID, mux->getPort("\\S")) : mux->getPort("\\S"));
+			} while (mux_cells_a.count(sig_data) || mux_cells_b.count(sig_data));
 
-			sig_data = sigmap(mux->getPort("\\Y"));
 			for (auto bit : sig_data)
 				if (sigbit_users_count[bit] > 1)
 					goto skip_ff_after_read_merging;
@@ -195,7 +201,7 @@ struct MemoryDffWorker
 			{
 				disconnect_dff(sig_data);
 				cell->setPort("\\CLK", clk_data);
-				cell->setPort("\\EN", enable_invert ? module->LogicNot(NEW_ID, mux->getPort("\\S")) : mux->getPort("\\S"));
+				cell->setPort("\\EN", en.size() > 1 ? module->ReduceAnd(NEW_ID, en) : en);
 				cell->setPort("\\DATA", sig_data);
 				cell->parameters["\\CLK_ENABLE"] = RTLIL::Const(1);
 				cell->parameters["\\CLK_POLARITY"] = RTLIL::Const(clk_polarity);
diff --git a/passes/opt/muxpack.cc b/passes/opt/muxpack.cc
index b6f3313bf..6697d6ca1 100644
--- a/passes/opt/muxpack.cc
+++ b/passes/opt/muxpack.cc
@@ -29,53 +29,84 @@ struct ExclusiveDatabase
 	Module *module;
 	const SigMap &sigmap;
 
-	dict<SigBit, SigSpec> sig_cmp_prev;
-	dict<SigSpec, pool<SigSpec>> sig_exclusive;
+	dict<SigBit, std::pair<SigSpec,std::vector<Const>>> sig_cmp_prev;
 
 	ExclusiveDatabase(Module *module, const SigMap &sigmap) : module(module), sigmap(sigmap)
 	{
-		SigSpec a_port, b_port, y_port;
+		SigSpec const_sig, nonconst_sig;
+		SigBit y_port;
+		pool<Cell*> reduce_or;
 		for (auto cell : module->cells()) {
 			if (cell->type == "$eq") {
-				a_port = sigmap(cell->getPort("\\A"));
-				b_port = sigmap(cell->getPort("\\B"));
-				if (!b_port.is_fully_const()) {
-					if (!a_port.is_fully_const())
+				nonconst_sig = sigmap(cell->getPort("\\A"));
+				const_sig = sigmap(cell->getPort("\\B"));
+				if (!const_sig.is_fully_const()) {
+					if (!nonconst_sig.is_fully_const())
 						continue;
-					std::swap(a_port, b_port);
+					std::swap(nonconst_sig, const_sig);
 				}
 				y_port = sigmap(cell->getPort("\\Y"));
 			}
 			else if (cell->type == "$logic_not") {
-				a_port = sigmap(cell->getPort("\\A"));
-				b_port = Const(RTLIL::S0, GetSize(a_port));
+				nonconst_sig = sigmap(cell->getPort("\\A"));
+				const_sig = Const(RTLIL::S0, GetSize(nonconst_sig));
 				y_port = sigmap(cell->getPort("\\Y"));
 			}
+			else if (cell->type == "$reduce_or") {
+				reduce_or.insert(cell);
+				continue;
+			}
 			else continue;
 
-			auto r = sig_exclusive[a_port].insert(b_port.as_const());
-			if (!r.second)
+			log_assert(!nonconst_sig.empty());
+			log_assert(!const_sig.empty());
+			sig_cmp_prev[y_port] = std::make_pair(nonconst_sig,std::vector<Const>{const_sig.as_const()});
+		}
+
+		for (auto cell : reduce_or) {
+			nonconst_sig = SigSpec();
+			std::vector<Const> values;
+			SigSpec a_port = sigmap(cell->getPort("\\A"));
+			for (auto bit : a_port) {
+				auto it = sig_cmp_prev.find(bit);
+				if (it == sig_cmp_prev.end()) {
+					nonconst_sig = SigSpec();
+					break;
+				}
+				if (nonconst_sig.empty())
+					nonconst_sig = it->second.first;
+				else if (nonconst_sig != it->second.first) {
+					nonconst_sig = SigSpec();
+					break;
+				}
+				for (auto value : it->second.second)
+					values.push_back(value);
+			}
+			if (nonconst_sig.empty())
 				continue;
-			sig_cmp_prev[y_port] = a_port;
+			y_port = sigmap(cell->getPort("\\Y"));
+			sig_cmp_prev[y_port] = std::make_pair(nonconst_sig,std::move(values));
 		}
 	}
 
-	bool query(const SigSpec& sig1, const SigSpec& sig2) const
+	bool query(const SigSpec &sig) const
 	{
-		// FIXME: O(N^2)
-		for (auto bit1 : sig1.bits()) {
-			auto it = sig_cmp_prev.find(bit1);
+		SigSpec nonconst_sig;
+		pool<Const> const_values;
+
+		for (auto bit : sig.bits()) {
+			auto it = sig_cmp_prev.find(bit);
 			if (it == sig_cmp_prev.end())
 				return false;
 
-			for (auto bit2 : sig2.bits()) {
-				auto jt = sig_cmp_prev.find(bit2);
-				if (jt == sig_cmp_prev.end())
-					return false;
+			if (nonconst_sig.empty())
+				nonconst_sig = it->second.first;
+			else if (nonconst_sig != it->second.first)
+				return false;
 
-				if (it->second != jt->second)
+			for (auto value : it->second.second)
+				if (!const_values.insert(value).second)
 					return false;
-			}
 		}
 
 		return true;
@@ -178,8 +209,8 @@ struct MuxpackWorker
 				Cell *prev_cell = sig_chain_prev.at(a_sig);
 				log_assert(prev_cell);
 				SigSpec s_sig = sigmap(cell->getPort("\\S"));
-				SigSpec next_s_sig = sigmap(prev_cell->getPort("\\S"));
-				if (!excl_db.query(s_sig, next_s_sig))
+				s_sig.append(sigmap(prev_cell->getPort("\\S")));
+				if (!excl_db.query(s_sig))
 					goto start_cell;
 			}
 
@@ -305,9 +336,9 @@ struct MuxpackPass : public Pass {
 		log("constructs) and $mux cells (e.g. those created by if-else constructs) into\n");
 		log("$pmux cells.\n");
 		log("\n");
-		log("This optimisation is conservative --- it will only pack $mux or $pmux cells with\n");
-		log("other such cells if it can be certain that the select lines are mutually\n");
-		log("exclusive.\n");
+		log("This optimisation is conservative --- it will only pack $mux or $pmux cells\n");
+		log("whose select lines are driven by '$eq' cells with other such cells if it can be\n");
+		log("certain that their select inputs are mutually exclusive.\n");
 		log("\n");
 	}
 	void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
diff --git a/tests/memories/issue00335.v b/tests/memories/issue00335.v
new file mode 100644
index 000000000..f3b6e5dfe
--- /dev/null
+++ b/tests/memories/issue00335.v
@@ -0,0 +1,28 @@
+// expect-wr-ports 1
+// expect-rd-ports 1
+// expect-rd-clk \clk
+
+module ram2 (input clk,
+             input             sel,
+             input             we, 
+             input [SIZE-1:0]  adr, 
+             input [63:0]      dat_i, 
+             output reg [63:0] dat_o);
+   parameter  SIZE = 5; // Address size
+
+   reg [63:0] mem [0:(1 << SIZE)-1];
+   integer    i;
+
+   initial begin
+      for (i = 0; i < (1<<SIZE) - 1; i = i + 1)
+        mem[i] <= 0;
+   end
+   
+   always @(posedge clk)
+     if (sel) begin
+       if (~we)
+         dat_o <= mem[adr];
+       else
+         mem[adr] <= dat_i;
+     end
+endmodule
diff --git a/tests/memories/issue00710.v b/tests/memories/issue00710.v
new file mode 100644
index 000000000..7a5fad1c2
--- /dev/null
+++ b/tests/memories/issue00710.v
@@ -0,0 +1,17 @@
+// expect-wr-ports 1
+// expect-rd-ports 1
+// expect-rd-clk \clk
+
+module top(input clk, input we, re, reset, input [7:0] addr, wdata, output reg [7:0] rdata);
+
+reg [7:0] bram[0:255];
+(* keep *) reg dummy;
+
+always @(posedge clk)
+	if (reset)
+		dummy <= 1'b0;
+	else if (re)
+		rdata <= bram[addr];
+	else if (we)
+		bram[addr] <= wdata;
+endmodule
diff --git a/tests/memories/run-test.sh b/tests/memories/run-test.sh
index 734a96682..d0537bb98 100755
--- a/tests/memories/run-test.sh
+++ b/tests/memories/run-test.sh
@@ -14,7 +14,7 @@ shift "$((OPTIND-1))"
 
 bash ../tools/autotest.sh $seed -G *.v
 
-for f in `egrep -l 'expect-(wr|rd)-ports' *.v`; do
+for f in `egrep -l 'expect-(wr-ports|rd-ports|rd-clk)' *.v`; do
 	echo -n "Testing expectations for $f .."
 	../../yosys -qp "proc; opt; memory -nomap;; dump -outfile ${f%.v}.dmp t:\$mem" $f
 	if grep -q expect-wr-ports $f; then
@@ -25,6 +25,10 @@ for f in `egrep -l 'expect-(wr|rd)-ports' *.v`; do
 		grep -q "parameter \\\\RD_PORTS $(gawk '/expect-rd-ports/ { print $3; }' $f)\$" ${f%.v}.dmp ||
 				{ echo " ERROR: Unexpected number of read ports."; false; }
 	fi
+	if grep -q expect-rd-clk $f; then
+		grep -q "connect \\\\RD_CLK \\$(gawk '/expect-rd-clk/ { print $3; }' $f)\$" ${f%.v}.dmp ||
+				{ echo " ERROR: Unexpected read clock."; false; }
+	fi
 	echo " ok."
 done
 
diff --git a/tests/various/muxpack.v b/tests/various/muxpack.v
index 3a1086dbf..33ece1f16 100644
--- a/tests/various/muxpack.v
+++ b/tests/various/muxpack.v
@@ -187,7 +187,8 @@ module case_nonexclusive_select (
 );
         always @* begin
             case (x)
-                0, 2: o = b;
+                0: o = b;
+                2: o = b;
                 1: o = c;
                 default: begin
                     o = a;
@@ -197,3 +198,62 @@ module case_nonexclusive_select (
         endcase
         end
 endmodule
+
+module case_nonoverlap (
+        input wire [2:0] x,
+        input wire a, b, c, d, e,
+        output reg o
+);
+        always @* begin
+            case (x)
+                0, 2: o = b; // Creates $reduce_or
+                1: o = c;
+                default:
+                    case (x)
+                        3: o = d; 4: o = d; // Creates $reduce_or
+                        5: o = e;
+                        default: o = 1'b0;
+                    endcase
+        endcase
+        end
+endmodule
+
+module case_overlap (
+        input wire [2:0] x,
+        input wire a, b, c, d, e,
+        output reg o
+);
+        always @* begin
+            case (x)
+                0, 2: o = b; // Creates $reduce_or
+                1: o = c;
+                default:
+                    case (x)
+                        0: o = 1'b1; // OVERLAP!
+                        3, 4: o = d; // Creates $reduce_or
+                        5: o = e;
+                        default: o = 1'b0;
+                    endcase
+        endcase
+        end
+endmodule
+
+module case_overlap2 (
+        input wire [2:0] x,
+        input wire a, b, c, d, e,
+        output reg o
+);
+        always @* begin
+            case (x)
+                0: o = b; 2: o = b; // Creates $reduce_or
+                1: o = c;
+                default:
+                    case (x)
+                        0: o = d; 2: o = d; // Creates $reduce_or
+                        3: o = d; 4: o = d; // Creates $reduce_or
+                        5: o = e;
+                        default: o = 1'b0;
+                    endcase
+        endcase
+        end
+endmodule
diff --git a/tests/various/muxpack.ys b/tests/various/muxpack.ys
index 579dad8d3..af23fcec8 100644
--- a/tests/various/muxpack.ys
+++ b/tests/various/muxpack.ys
@@ -212,3 +212,57 @@ 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
+
+design -load read
+hierarchy -top case_nonoverlap
+#prep # Do not prep otherwise $pmux's overlapping entry will get removed
+proc
+design -save gold
+opt -fast -mux_undef
+select -assert-count 2 t:$pmux
+muxpack
+opt
+stat
+select -assert-count 0 t:$mux
+select -assert-count 1 t:$pmux
+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
+
+design -load read
+hierarchy -top case_overlap
+#prep # Do not prep otherwise $pmux's overlapping entry will get removed
+proc
+design -save gold
+opt -fast -mux_undef
+select -assert-count 2 t:$pmux
+muxpack
+opt
+stat
+select -assert-count 0 t:$mux
+select -assert-count 2 t:$pmux
+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
+
+design -load read
+hierarchy -top case_overlap2
+#prep # Do not prep otherwise $pmux's overlapping entry will get removed
+proc
+design -save gold
+opt -fast -mux_undef
+select -assert-count 2 t:$pmux
+muxpack
+opt
+stat
+select -assert-count 0 t:$mux
+select -assert-count 2 t:$pmux
+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