proc_rmdead: use explicit pattern set when there are no wildcards

If width of a case expression was large, explicit patterns could cause
the existing logic to take an extremely long time, or exhaust the
maximum size of the underlying set. For cases where all of the patterns
are fully defined and there are no constants in the case expression,
this change uses a simple set to track which patterns have been seen.

4 files changed, 386 insertions, 2 deletions

diff --git a/passes/proc/proc_rmdead.cc b/passes/proc/proc_rmdead.cc
index d49fd7ed3..2ec11415a 100644
--- a/passes/proc/proc_rmdead.cc
+++ b/passes/proc/proc_rmdead.cc
@@ -28,9 +28,62 @@
 USING_YOSYS_NAMESPACE
 PRIVATE_NAMESPACE_BEGIN
 
-void proc_rmdead(RTLIL::SwitchRule *sw, int &counter, int &full_case_counter)
+static bool can_use_fully_defined_pool(RTLIL::SwitchRule *sw)
+{
+	if (!GetSize(sw->signal))
+		return false;
+
+	for (const RTLIL::SigBit &bit : sw->signal)
+		if (bit.wire == NULL)
+			return false;
+
+	for (const RTLIL::CaseRule *cas : sw->cases)
+		for (const RTLIL::SigSpec &sig : cas->compare)
+			if (!sig.is_fully_def())
+				return false;
+
+	return true;
+}
+
+// This replicates the necessary parts of BitPatternPool's interface, but rather
+// than storing remaining patterns, this explicitly stores which fully-defined
+// constants have already been matched.
+struct FullyDefinedPool
+{
+	FullyDefinedPool(const RTLIL::SigSpec &signal)
+		: max_patterns{signal.size() >= 32 ? 0ul : 1ul << signal.size()}
+	{}
+
+	bool take(RTLIL::SigSpec sig)
+	{
+		if (default_reached || patterns.count(sig))
+			return false;
+		patterns.insert(sig);
+		return true;
+	}
+
+	void take_all()
+	{
+		default_reached = true;
+	}
+
+	bool empty()
+	{
+		return default_reached ||
+			(max_patterns && max_patterns == patterns.size());
+	}
+
+	pool<RTLIL::SigSpec> patterns;
+	bool default_reached = false;
+	size_t max_patterns;
+};
+
+void proc_rmdead(RTLIL::SwitchRule *sw, int &counter, int &full_case_counter);
+
+template <class Pool>
+static void proc_rmdead_impl(RTLIL::SwitchRule *sw, int &counter, int &full_case_counter)
 {
-	BitPatternPool pool(sw->signal);
+	Pool pool(sw->signal);
 
 	for (size_t i = 0; i < sw->cases.size(); i++)
 	{
@@ -68,6 +121,14 @@ void proc_rmdead(RTLIL::SwitchRule *sw, int &counter, int &full_case_counter)
 	}
 }
 
+void proc_rmdead(RTLIL::SwitchRule *sw, int &counter, int &full_case_counter)
+{
+	if (can_use_fully_defined_pool(sw))
+		proc_rmdead_impl<FullyDefinedPool>(sw, counter, full_case_counter);
+	else
+		proc_rmdead_impl<BitPatternPool>(sw, counter, full_case_counter);
+}
+
 struct ProcRmdeadPass : public Pass {
 	ProcRmdeadPass() : Pass("proc_rmdead", "eliminate dead trees in decision trees") { }
 	void help() override
diff --git a/tests/proc/rmdead.v b/tests/proc/rmdead.v
new file mode 100644
index 000000000..2be89e533
--- /dev/null
+++ b/tests/proc/rmdead.v
@@ -0,0 +1,46 @@
+module top (
+    input wire signed x,
+    output reg [31:0] y
+);
+    wire signed fail = ~x;
+
+    always @*
+        case (x)
+            1'b0: y = 0;
+            1'b1: y = 1;
+            default: y = fail;
+        endcase
+
+    always @*
+        case (x)
+            2'sb00: y = 0;
+            2'sb00: y = fail;
+        endcase
+
+    always @*
+        case (x)
+            2'sb00: y = 0;
+            default: y = fail;
+            2'sb01: y = 1;
+            2'sb10: y = 2;
+            2'sb11: y = 3;
+            2'sb00: y = fail;
+            2'sb01: y = fail;
+            2'sb10: y = fail;
+            2'sb11: y = fail;
+        endcase
+
+
+    always @*
+        case ({x, x})
+            2'b00: y = 0;
+            2'b01: y = 1;
+            2'b10: y = 2;
+            2'b11: y = 3;
+            default: y = fail;
+            2'b00: y = fail;
+            2'b01: y = fail;
+            2'b10: y = fail;
+            2'b11: y = fail;
+        endcase
+endmodule
diff --git a/tests/proc/rmdead.ys b/tests/proc/rmdead.ys
new file mode 100644
index 000000000..697d899e3
--- /dev/null
+++ b/tests/proc/rmdead.ys
@@ -0,0 +1,4 @@
+read_verilog rmdead.v
+proc
+opt_clean
+select -assert-count 0 w:fail
diff --git a/tests/simple/case_large.v b/tests/simple/case_large.v
new file mode 100644
index 000000000..a96ce86fe
--- /dev/null
+++ b/tests/simple/case_large.v
@@ -0,0 +1,273 @@
+module top (
+    input wire [127:0] x,
+    output reg [31:0] y
+);
+    localparam A = 32'hDEAD_BEEF;
+    localparam B = 32'h0BAD_0B01;
+    localparam C = 32'hC001_D00D;
+    localparam D = 32'h1234_5678;
+
+    always @*
+        case (x)
+
+            {C,A,D,B}: y = 142;
+            {C,A,D,A}: y = 141;
+            {D,D,A,A}: y = 241;
+            {A,C,C,D}: y = 44;
+            {A,A,A,C}: y = 3;
+            {A,B,A,C}: y = 19;
+            {A,D,C,C}: y = 59;
+            {A,A,C,C}: y = 11;
+            {D,C,B,B}: y = 230;
+            {A,A,D,D}: y = 16;
+            {A,C,A,A}: y = 33;
+            {A,D,D,D}: y = 64;
+            {D,B,C,B}: y = 218;
+            {A,C,B,D}: y = 40;
+            {C,A,B,B}: y = 134;
+            {A,C,C,C}: y = 43;
+            {D,A,D,D}: y = 208;
+            {A,B,C,A}: y = 25;
+            {B,A,B,B}: y = 70;
+            {A,C,B,B}: y = 38;
+            {C,C,C,B}: y = 170;
+            {C,D,A,C}: y = 179;
+            {B,C,D,B}: y = 110;
+            {A,D,A,C}: y = 51;
+            {C,C,B,B}: y = 166;
+            {D,D,D,B}: y = 254;
+            {C,A,D,C}: y = 143;
+            {C,D,D,B}: y = 190;
+            {C,B,A,A}: y = 145;
+            {C,B,A,C}: y = 147;
+            {B,C,C,B}: y = 106;
+            {C,D,C,A}: y = 185;
+            {C,D,B,D}: y = 184;
+            {D,D,D,D}: y = 256;
+            {D,C,C,C}: y = 235;
+            {D,C,D,B}: y = 238;
+            {A,B,D,C}: y = 31;
+            {A,C,A,D}: y = 36;
+            {C,B,C,B}: y = 154;
+            {A,B,A,A}: y = 17;
+            {C,B,B,A}: y = 149;
+            {B,B,D,C}: y = 95;
+            {B,D,C,B}: y = 122;
+            {D,B,A,A}: y = 209;
+            {B,A,B,A}: y = 69;
+            {B,A,D,A}: y = 77;
+            {A,B,B,B}: y = 22;
+            {C,C,C,C}: y = 171;
+            {C,A,C,B}: y = 138;
+            {B,A,D,D}: y = 80;
+            {C,D,D,C}: y = 191;
+            {B,A,A,C}: y = 67;
+            {D,C,D,C}: y = 239;
+            {C,D,D,D}: y = 192;
+            {C,D,B,B}: y = 182;
+            {B,B,A,C}: y = 83;
+            {D,A,A,D}: y = 196;
+            {A,C,C,B}: y = 42;
+            {B,C,A,A}: y = 97;
+            {A,D,B,A}: y = 53;
+            {D,D,B,C}: y = 247;
+            {A,A,C,A}: y = 9;
+            {D,A,C,B}: y = 202;
+            {A,C,B,C}: y = 39;
+            {B,C,B,A}: y = 101;
+            {B,B,B,C}: y = 87;
+            {C,B,A,B}: y = 146;
+            {B,D,A,D}: y = 116;
+            {A,B,D,D}: y = 32;
+            {B,A,B,C}: y = 71;
+            {C,A,A,A}: y = 129;
+            {B,A,D,C}: y = 79;
+            {B,A,C,B}: y = 74;
+            {B,B,D,B}: y = 94;
+            {B,B,C,C}: y = 91;
+            {D,C,C,A}: y = 233;
+            {C,A,B,A}: y = 133;
+            {D,A,B,A}: y = 197;
+            {D,B,B,D}: y = 216;
+            {C,C,A,C}: y = 163;
+            {D,D,B,A}: y = 245;
+            {B,A,D,B}: y = 78;
+            {A,B,C,D}: y = 28;
+            {C,C,C,D}: y = 172;
+            {D,C,A,D}: y = 228;
+            {A,C,D,A}: y = 45;
+            {B,D,C,C}: y = 123;
+            {C,B,A,D}: y = 148;
+            {B,D,B,B}: y = 118;
+            {A,D,A,B}: y = 50;
+            {C,B,B,C}: y = 151;
+            {A,A,A,A}: y = 1;
+            {A,A,B,B}: y = 6;
+            {B,B,B,B}: y = 86;
+            {A,D,A,A}: y = 49;
+            {A,A,A,B}: y = 2;
+            {B,D,D,A}: y = 125;
+            {C,C,D,B}: y = 174;
+            {D,A,D,B}: y = 206;
+            {D,D,B,D}: y = 248;
+            {A,A,A,D}: y = 4;
+            {B,A,A,B}: y = 66;
+            {B,C,C,A}: y = 105;
+            {B,C,C,C}: y = 107;
+            {D,D,D,C}: y = 255;
+            {B,C,D,D}: y = 112;
+            {A,D,B,C}: y = 55;
+            {C,C,C,A}: y = 169;
+            {C,D,B,C}: y = 183;
+            {A,A,B,D}: y = 8;
+            {D,C,B,A}: y = 229;
+            {C,B,D,A}: y = 157;
+            {A,D,D,C}: y = 63;
+            {D,A,D,A}: y = 205;
+            {A,A,B,C}: y = 7;
+            {A,C,A,B}: y = 34;
+            {C,B,D,C}: y = 159;
+            {C,C,D,D}: y = 176;
+            {D,D,D,A}: y = 253;
+            {A,B,B,D}: y = 24;
+            {B,B,C,A}: y = 89;
+            {B,D,C,A}: y = 121;
+            {A,B,C,C}: y = 27;
+            {A,A,D,C}: y = 15;
+            {A,B,B,A}: y = 21;
+            {A,D,A,D}: y = 52;
+            {D,D,C,C}: y = 251;
+            {C,D,A,B}: y = 178;
+            {A,A,D,B}: y = 14;
+            {D,B,D,B}: y = 222;
+            {A,C,C,A}: y = 41;
+            {D,D,A,C}: y = 243;
+            {A,C,D,B}: y = 46;
+            {B,B,B,D}: y = 88;
+            {D,B,B,B}: y = 214;
+            {C,C,B,D}: y = 168;
+            {A,D,D,A}: y = 61;
+            {D,A,C,C}: y = 203;
+            {D,C,A,C}: y = 227;
+            {C,D,C,D}: y = 188;
+            {D,B,D,D}: y = 224;
+            {A,C,D,C}: y = 47;
+            {B,A,B,D}: y = 72;
+            {A,B,B,C}: y = 23;
+            {C,C,D,A}: y = 173;
+            {D,B,C,C}: y = 219;
+            {D,B,C,A}: y = 217;
+            {A,D,C,D}: y = 60;
+            {B,B,D,A}: y = 93;
+            {A,D,C,A}: y = 57;
+            {C,C,A,A}: y = 161;
+            {C,B,B,D}: y = 152;
+            {B,B,B,A}: y = 85;
+            {B,D,A,A}: y = 113;
+            {D,C,D,A}: y = 237;
+            {B,C,B,C}: y = 103;
+            {A,B,C,B}: y = 26;
+            {C,D,A,D}: y = 180;
+            {A,D,B,D}: y = 56;
+            {D,C,A,B}: y = 226;
+            {D,B,B,C}: y = 215;
+            {D,A,B,C}: y = 199;
+            {B,D,A,C}: y = 115;
+            {C,B,C,D}: y = 156;
+            {B,D,D,B}: y = 126;
+            {D,D,C,B}: y = 250;
+            {D,C,C,D}: y = 236;
+            {B,C,B,D}: y = 104;
+            {C,B,C,A}: y = 153;
+            {C,B,B,B}: y = 150;
+            {C,D,C,B}: y = 186;
+            {C,D,C,C}: y = 187;
+            {A,D,B,B}: y = 54;
+            {D,C,C,B}: y = 234;
+            {C,B,D,D}: y = 160;
+            {A,B,A,D}: y = 20;
+            {C,C,B,A}: y = 165;
+            {C,D,D,A}: y = 189;
+            {C,C,D,C}: y = 175;
+            {D,B,D,C}: y = 223;
+            {B,C,A,B}: y = 98;
+            {C,C,A,B}: y = 162;
+            {B,C,D,A}: y = 109;
+            {D,A,B,D}: y = 200;
+            {B,D,C,D}: y = 124;
+            {D,D,C,A}: y = 249;
+            {B,A,C,C}: y = 75;
+            {A,A,C,B}: y = 10;
+            {C,A,B,D}: y = 136;
+            {B,B,C,D}: y = 92;
+            {D,D,C,D}: y = 252;
+            {B,C,A,D}: y = 100;
+            {C,A,C,C}: y = 139;
+            {C,A,C,D}: y = 140;
+            {D,C,A,A}: y = 225;
+            {A,D,C,B}: y = 58;
+            {D,B,C,D}: y = 220;
+            {D,C,B,D}: y = 232;
+            {B,A,C,D}: y = 76;
+            {B,B,D,D}: y = 96;
+            {D,D,B,B}: y = 246;
+            {C,D,A,A}: y = 177;
+            {D,D,A,B}: y = 242;
+            {A,A,D,A}: y = 13;
+            {B,B,A,D}: y = 84;
+            {B,C,D,C}: y = 111;
+            {D,A,A,B}: y = 194;
+            {C,A,B,C}: y = 135;
+            {D,A,A,C}: y = 195;
+            {B,B,A,B}: y = 82;
+            {D,C,D,D}: y = 240;
+            {B,C,C,D}: y = 108;
+            {D,B,A,C}: y = 211;
+            {A,C,D,D}: y = 48;
+            {D,A,A,A}: y = 193;
+            {C,A,A,B}: y = 130;
+            {D,B,A,D}: y = 212;
+            {D,A,B,B}: y = 198;
+            {A,C,B,A}: y = 37;
+            {B,D,B,D}: y = 120;
+            {C,C,B,C}: y = 167;
+            {D,B,A,B}: y = 210;
+            {A,B,A,B}: y = 18;
+            {B,C,B,B}: y = 102;
+            {B,B,A,A}: y = 81;
+            {D,D,A,D}: y = 244;
+            {A,B,D,B}: y = 30;
+            {A,C,A,C}: y = 35;
+            {A,A,C,D}: y = 12;
+            {B,D,B,C}: y = 119;
+            {B,C,A,C}: y = 99;
+            {D,A,C,A}: y = 201;
+            {B,A,A,D}: y = 68;
+            {C,A,A,D}: y = 132;
+            {B,A,C,A}: y = 73;
+            {C,C,A,D}: y = 164;
+            {B,D,B,A}: y = 117;
+            {A,D,D,B}: y = 62;
+            {B,D,D,C}: y = 127;
+            {A,B,D,A}: y = 29;
+            {C,D,B,A}: y = 181;
+            {B,B,C,B}: y = 90;
+            {B,D,A,B}: y = 114;
+            {B,D,D,D}: y = 128;
+            {C,A,C,A}: y = 137;
+            {A,A,B,A}: y = 5;
+            {C,A,D,D}: y = 144;
+            {D,C,B,C}: y = 231;
+            {D,A,C,D}: y = 204;
+            {C,A,A,C}: y = 131;
+            {C,B,D,B}: y = 158;
+            {B,A,A,A}: y = 65;
+            {D,A,D,C}: y = 207;
+            {D,B,B,A}: y = 213;
+            {D,B,D,A}: y = 221;
+            {C,B,C,C}: y = 155;
+
+            default: y = 0;
+
+        endcase
+endmodule