From c016f6a4236fb970196f35c2afb0f2c7c237a77f Mon Sep 17 00:00:00 2001 From: Zachary Snow Date: Wed, 28 Jul 2021 17:34:24 -0400 Subject: [PATCH] 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. --- passes/proc/proc_rmdead.cc | 65 ++++++++- tests/proc/rmdead.v | 46 +++++++ tests/proc/rmdead.ys | 4 + tests/simple/case_large.v | 273 +++++++++++++++++++++++++++++++++++++ 4 files changed, 386 insertions(+), 2 deletions(-) create mode 100644 tests/proc/rmdead.v create mode 100644 tests/proc/rmdead.ys create mode 100644 tests/simple/case_large.v 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 patterns; + bool default_reached = false; + size_t max_patterns; +}; + +void proc_rmdead(RTLIL::SwitchRule *sw, int &counter, int &full_case_counter); + +template +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(sw, counter, full_case_counter); + else + proc_rmdead_impl(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 -- 2.30.2