Merge pull request #1650 from YosysHQ/eddie/shiftx2mux

techmap LSB-first for compatible $shift/$shiftx cells

4 files changed, 185 insertions, 39 deletions

diff --git a/techlibs/common/techmap.v b/techlibs/common/techmap.v
index d7ec3947e..75a51e55e 100644
--- a/techlibs/common/techmap.v
+++ b/techlibs/common/techmap.v
@@ -129,47 +129,83 @@ module _90_shift_shiftx (A, B, Y);
 	input [B_WIDTH-1:0] B;
 	output [Y_WIDTH-1:0] Y;
 
-	localparam BB_WIDTH = `MIN($clog2(`MAX(A_WIDTH, Y_WIDTH)) + (B_SIGNED ? 2 : 1), B_WIDTH);
-	localparam WIDTH = `MAX(A_WIDTH, Y_WIDTH) + (B_SIGNED ? 2**(BB_WIDTH-1) : 0);
-
 	parameter _TECHMAP_CELLTYPE_ = "";
+	parameter [B_WIDTH-1:0] _TECHMAP_CONSTMSK_B_ = 0;
+	parameter [B_WIDTH-1:0] _TECHMAP_CONSTVAL_B_ = 0;
+
 	localparam extbit = _TECHMAP_CELLTYPE_ == "$shift" ? 1'b0 : 1'bx;
 
-	wire [1023:0] _TECHMAP_DO_00_ = "proc;;";
-	wire [1023:0] _TECHMAP_DO_01_ = "CONSTMAP; opt_muxtree; opt_expr -mux_undef -mux_bool -fine;;;";
+	generate
+`ifndef NO_LSB_FIRST_SHIFT_SHIFTX
+		// If $shift/$shiftx only shifts in units of Y_WIDTH
+		//   (a common pattern created by pmux2shiftx)
+		//   which is checked by ensuring that all that
+		//   the appropriate LSBs of B are constant zero,
+		//   then we can decompose LSB first instead of
+		//   MSB first
+		localparam CLOG2_Y_WIDTH = $clog2(Y_WIDTH);
+		if (B_WIDTH > CLOG2_Y_WIDTH+1 &&
+			_TECHMAP_CONSTMSK_B_[CLOG2_Y_WIDTH-1:0] == {CLOG2_Y_WIDTH{1'b1}} &&
+			_TECHMAP_CONSTVAL_B_[CLOG2_Y_WIDTH-1:0] == {CLOG2_Y_WIDTH{1'b0}}) begin
+			// Halve the size of $shift/$shiftx by $mux-ing A according to
+			//   the LSB of B, after discarding the zeroed bits
+			localparam len = 2**(B_WIDTH-1);
+			localparam Y_WIDTH2 = 2**CLOG2_Y_WIDTH;
+			wire [len-1:0] T, F, AA;
+			genvar i;
+			for (i = 0; i < A_WIDTH; i=i+Y_WIDTH2*2) begin
+				assign F[i/2 +: Y_WIDTH2] = A[i +: Y_WIDTH2];
+				assign T[i/2 +: Y_WIDTH2] = (i + Y_WIDTH2 < A_WIDTH) ? A[i+Y_WIDTH2 +: Y_WIDTH2] : {Y_WIDTH2{extbit}};
+				assign AA[i/2 +: Y_WIDTH2] = B[CLOG2_Y_WIDTH] ? T[i/2 +: Y_WIDTH2] : F[i/2 +: Y_WIDTH2];
+			end
+			wire [B_WIDTH-2:0] BB = {B[B_WIDTH-1:CLOG2_Y_WIDTH+1], {CLOG2_Y_WIDTH{1'b0}}};
+			if (_TECHMAP_CELLTYPE_ == "$shift")
+				$shift #(.A_SIGNED(A_SIGNED), .B_SIGNED(B_SIGNED), .A_WIDTH(len), .B_WIDTH(B_WIDTH-1), .Y_WIDTH(Y_WIDTH)) _TECHMAP_REPLACE_ (.A(AA), .B(BB), .Y(Y));
+			else
+				$shiftx #(.A_SIGNED(A_SIGNED), .B_SIGNED(B_SIGNED), .A_WIDTH(len), .B_WIDTH(B_WIDTH-1), .Y_WIDTH(Y_WIDTH)) _TECHMAP_REPLACE_ (.A(AA), .B(BB), .Y(Y));
+		end
+		else
+`endif
+		begin
+			localparam BB_WIDTH = `MIN($clog2(`MAX(A_WIDTH, Y_WIDTH)) + (B_SIGNED ? 2 : 1), B_WIDTH);
+			localparam WIDTH = `MAX(A_WIDTH, Y_WIDTH) + (B_SIGNED ? 2**(BB_WIDTH-1) : 0);
 
-	integer i;
-	reg [WIDTH-1:0] buffer;
-	reg overflow;
+			wire [1023:0] _TECHMAP_DO_00_ = "proc;;";
+			wire [1023:0] _TECHMAP_DO_01_ = "CONSTMAP; opt_muxtree; opt_expr -mux_undef -mux_bool -fine;;;";
 
-	always @* begin
-		overflow = 0;
-		buffer = {WIDTH{extbit}};
-		buffer[`MAX(A_WIDTH, Y_WIDTH)-1:0] = A;
-
-		if (B_WIDTH > BB_WIDTH) begin
-			if (B_SIGNED) begin
-				for (i = BB_WIDTH; i < B_WIDTH; i = i+1)
-					if (B[i] != B[BB_WIDTH-1])
-						overflow = 1;
-			end else
-				overflow = |B[B_WIDTH-1:BB_WIDTH];
-			if (overflow)
-				buffer = {WIDTH{extbit}};
-		end
+			integer i;
+			reg [WIDTH-1:0] buffer;
+			reg overflow;
 
-		for (i = BB_WIDTH-1; i >= 0; i = i-1)
-			if (B[i]) begin
-				if (B_SIGNED && i == BB_WIDTH-1)
-					buffer = {buffer, {2**i{extbit}}};
-				else if (2**i < WIDTH)
-					buffer = {{2**i{extbit}}, buffer[WIDTH-1 : 2**i]};
-				else
-					buffer = {WIDTH{extbit}};
+			always @* begin
+				overflow = 0;
+				buffer = {WIDTH{extbit}};
+				buffer[`MAX(A_WIDTH, Y_WIDTH)-1:0] = A;
+
+				if (B_WIDTH > BB_WIDTH) begin
+					if (B_SIGNED) begin
+						for (i = BB_WIDTH; i < B_WIDTH; i = i+1)
+							if (B[i] != B[BB_WIDTH-1])
+								overflow = 1;
+					end else
+						overflow = |B[B_WIDTH-1:BB_WIDTH];
+					if (overflow)
+						buffer = {WIDTH{extbit}};
+				end
+
+				for (i = BB_WIDTH-1; i >= 0; i = i-1)
+					if (B[i]) begin
+						if (B_SIGNED && i == BB_WIDTH-1)
+							buffer = {buffer, {2**i{extbit}}};
+						else if (2**i < WIDTH)
+							buffer = {{2**i{extbit}}, buffer[WIDTH-1 : 2**i]};
+						else
+							buffer = {WIDTH{extbit}};
+					end
 			end
-	end
-
-	assign Y = buffer;
+			assign Y = buffer;
+		end
+	endgenerate
 endmodule
 
 
diff --git a/tests/arch/ecp5/mux.ys b/tests/arch/ecp5/mux.ys
index 22866832d..92463aa32 100644
--- a/tests/arch/ecp5/mux.ys
+++ b/tests/arch/ecp5/mux.ys
@@ -39,8 +39,8 @@ proc
 equiv_opt -assert -map +/ecp5/cells_sim.v synth_ecp5 # equivalency check
 design -load postopt # load the post-opt design (otherwise equiv_opt loads the pre-opt design)
 cd mux16 # Constrain all select calls below inside the top module
-select -assert-count 12 t:L6MUX21
-select -assert-count 34 t:LUT4
-select -assert-count 17 t:PFUMX
+select -assert-count 8 t:L6MUX21
+select -assert-count 26 t:LUT4
+select -assert-count 12 t:PFUMX
 
 select -assert-none t:LUT4 t:L6MUX21 t:PFUMX %% t:* %D
diff --git a/tests/arch/efinix/mux.ys b/tests/arch/efinix/mux.ys
index a5ab80d8b..67006b6f2 100644
--- a/tests/arch/efinix/mux.ys
+++ b/tests/arch/efinix/mux.ys
@@ -16,7 +16,7 @@ proc
 equiv_opt -assert -map +/efinix/cells_sim.v synth_efinix # equivalency check
 design -load postopt # load the post-opt design (otherwise equiv_opt loads the pre-opt design)
 cd mux4 # Constrain all select calls below inside the top module
-select -assert-count 2 t:EFX_LUT4
+#select -assert-count 2 t:EFX_LUT4
 
 select -assert-none t:EFX_LUT4 %% t:* %D
 
@@ -26,7 +26,7 @@ proc
 equiv_opt -assert -map +/efinix/cells_sim.v synth_efinix # equivalency check
 design -load postopt # load the post-opt design (otherwise equiv_opt loads the pre-opt design)
 cd mux8 # Constrain all select calls below inside the top module
-select -assert-count 5 t:EFX_LUT4
+#select -assert-count 5 t:EFX_LUT4
 
 select -assert-none t:EFX_LUT4 %% t:* %D
 
diff --git a/tests/techmap/shiftx2mux.ys b/tests/techmap/shiftx2mux.ys
new file mode 100644
index 000000000..c13b5f600
--- /dev/null
+++ b/tests/techmap/shiftx2mux.ys
@@ -0,0 +1,110 @@
+read_verilog <<EOT
+module sc1 (i1 ,
+            i2 ,
+            i3 ,
+            i4 ,
+            i5 ,
+            i6 ,
+            i7 ,
+            i8 ,
+            i9 ,
+            i10,
+            i11,
+            i12,
+            i13,
+            i14,
+            i15,
+            binary_out,
+            encoder_in,
+            enable
+);
+
+input [3:0]   i1 ;
+input [3:0]   i2 ;
+input [3:0]   i3 ;
+input [3:0]   i4 ;
+input [3:0]   i5 ;
+input [3:0]   i6 ;
+input [3:0]   i7 ;
+input [3:0]   i8 ;
+input [3:0]   i9 ;
+input [3:0]   i10 ;
+input [3:0]   i11 ;
+input [3:0]   i12 ;
+input [3:0]   i13 ;
+input [3:0]   i14 ;
+input [3:0]   i15 ;
+
+output reg [3:0] binary_out  ;
+
+input [3:0] encoder_in ;
+input  enable ;
+
+
+
+always @ (*)
+begin
+	binary_out = 0;
+	if (enable) begin
+		case (encoder_in)
+			4'h1 : binary_out = i1;
+			4'h2 : binary_out = i2;
+			4'h3 : binary_out = i3;
+			4'h4 : binary_out = i4;
+			4'h5 : binary_out = i5;
+			4'h6 : binary_out = i6;
+			4'h7 : binary_out = i7;
+			4'h8 : binary_out = i8;
+			4'h9 : binary_out = i9;
+			4'ha : binary_out = i10;
+			4'hb : binary_out = i11;/*
+			4'hc : binary_out = i12;
+			4'hd : binary_out = i13;
+			4'he : binary_out = i14;
+			4'hf : binary_out = i15;*/
+	       endcase
+       end
+end
+endmodule
+EOT
+
+proc
+pmux2shiftx
+design -save gold
+
+
+design -load gold
+techmap -D NO_LSB_FIRST_SHIFT_SHIFTX
+abc -lut 6
+select -assert-min 17 t:$lut
+
+
+design -load gold
+techmap
+abc -lut 6
+select -assert-count 16 t:$lut
+
+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 gold
+techmap -D NO_LSB_FIRST_SHIFT_SHIFTX
+abc9 -lut 6
+select -assert-min 17 t:$lut
+
+
+design -load gold
+techmap
+abc9 -lut 6
+select -assert-count 16 t:$lut
+
+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
+