Merge pull request #1303 from YosysHQ/bogdanvuk/opt_share

Implement opt_share from @bogdanvuk

23 files changed, 451 insertions, 0 deletions

diff --git a/tests/opt/opt_share_add_sub.v b/tests/opt/opt_share_add_sub.v
new file mode 100644
index 000000000..d918f27cc
--- /dev/null
+++ b/tests/opt/opt_share_add_sub.v
@@ -0,0 +1,10 @@
+module opt_share_test(
+  input [15:0]  a,
+  input [15:0]  b,
+  input         sel,
+  output [15:0] res,
+  );
+
+  assign res = {sel ? a + b : a - b};
+
+endmodule
diff --git a/tests/opt/opt_share_add_sub.ys b/tests/opt/opt_share_add_sub.ys
new file mode 100644
index 000000000..4a5406791
--- /dev/null
+++ b/tests/opt/opt_share_add_sub.ys
@@ -0,0 +1,13 @@
+read_verilog opt_share_add_sub.v
+proc;;
+copy opt_share_test merged
+
+alumacc merged
+opt merged
+opt_share merged
+opt_clean merged
+
+miter -equiv -flatten -ignore_gold_x -make_outputs -make_outcmp opt_share_test merged miter
+sat -set-def-inputs -verify -prove trigger 0 -show-inputs -show-outputs miter
+
+select -assert-count 1 -module merged t:$alu
diff --git a/tests/opt/opt_share_cat.v b/tests/opt/opt_share_cat.v
new file mode 100644
index 000000000..7fb97fef5
--- /dev/null
+++ b/tests/opt/opt_share_cat.v
@@ -0,0 +1,15 @@
+module opt_share_test(
+  input [15:0]  a,
+  input [15:0]  b,
+  input [15:0]  c,
+  input [15:0]  d,
+  input         sel,
+  output [63:0] res,
+  );
+
+  reg [31: 0]   cat1 = {a+b, c+d};
+  reg [31: 0]   cat2 = {a-b, c-d};
+
+  assign res = {b, sel ? cat1 : cat2, a};
+
+endmodule
diff --git a/tests/opt/opt_share_cat.ys b/tests/opt/opt_share_cat.ys
new file mode 100644
index 000000000..7de69bfde
--- /dev/null
+++ b/tests/opt/opt_share_cat.ys
@@ -0,0 +1,13 @@
+read_verilog opt_share_cat.v
+proc;;
+copy opt_share_test merged
+
+alumacc merged
+opt merged
+opt_share merged
+opt_clean merged
+
+miter -equiv -flatten -ignore_gold_x -make_outputs -make_outcmp opt_share_test merged miter
+sat -set-def-inputs -verify -prove trigger 0 -show-inputs -show-outputs miter
+
+select -assert-count 2 -module merged t:$alu
diff --git a/tests/opt/opt_share_cat_multiuser.v b/tests/opt/opt_share_cat_multiuser.v
new file mode 100644
index 000000000..b250689d9
--- /dev/null
+++ b/tests/opt/opt_share_cat_multiuser.v
@@ -0,0 +1,22 @@
+module opt_share_test(
+  input [15:0]      a,
+  input [15:0]      b,
+  input [15:0]      c,
+  input [15:0]      d,
+  input             sel,
+  output reg [47:0] res,
+  );
+
+  wire [15:0]       add_res = a+b;
+  wire [15:0]       sub_res = a-b;
+  wire [31: 0]      cat1 = {add_res, c+d};
+  wire [31: 0]      cat2 = {sub_res, c-d};
+
+  always @* begin
+    case(sel)
+      0: res = {cat1, add_res};
+      1: res = {cat2, add_res};
+    endcase
+  end
+
+endmodule
diff --git a/tests/opt/opt_share_cat_multiuser.ys b/tests/opt/opt_share_cat_multiuser.ys
new file mode 100644
index 000000000..6a82fbd79
--- /dev/null
+++ b/tests/opt/opt_share_cat_multiuser.ys
@@ -0,0 +1,13 @@
+read_verilog opt_share_cat_multiuser.v
+proc;;
+copy opt_share_test merged
+
+alumacc merged
+opt merged
+opt_share merged
+opt_clean merged
+
+miter -equiv -flatten -ignore_gold_x -make_outputs -make_outcmp opt_share_test merged miter
+sat -set-def-inputs -verify -prove trigger 0 -show-inputs -show-outputs miter
+
+select -assert-count 3 -module merged t:$alu
diff --git a/tests/opt/opt_share_diff_port_widths.v b/tests/opt/opt_share_diff_port_widths.v
new file mode 100644
index 000000000..1a37c80a6
--- /dev/null
+++ b/tests/opt/opt_share_diff_port_widths.v
@@ -0,0 +1,21 @@
+module opt_share_test(
+  input [15:0]       a,
+  input [15:0]       b,
+  input [15:0]       c,
+  input [1:0]      sel,
+  output reg [15:0] res
+  );
+
+  wire [15:0]       add0_res = a+b;
+  wire [15:0]       add1_res = a+c;
+
+  always @* begin
+    case(sel)
+      0: res = add0_res[10:0];
+      1: res = add1_res[10:0];
+      2: res = a - b;
+      default: res = 32'bx;
+    endcase
+  end
+
+endmodule
diff --git a/tests/opt/opt_share_diff_port_widths.ys b/tests/opt/opt_share_diff_port_widths.ys
new file mode 100644
index 000000000..ec5e9f7b0
--- /dev/null
+++ b/tests/opt/opt_share_diff_port_widths.ys
@@ -0,0 +1,13 @@
+read_verilog opt_share_diff_port_widths.v
+proc;;
+copy opt_share_test merged
+
+alumacc merged
+opt merged
+opt_share merged
+opt_clean merged
+
+miter -equiv -flatten -ignore_gold_x -make_outputs -make_outcmp opt_share_test merged miter
+sat -set-def-inputs -verify -prove trigger 0 -show-inputs -show-outputs miter
+
+select -assert-count 2 -module merged t:$alu
diff --git a/tests/opt/opt_share_extend.v b/tests/opt/opt_share_extend.v
new file mode 100644
index 000000000..d39f19069
--- /dev/null
+++ b/tests/opt/opt_share_extend.v
@@ -0,0 +1,18 @@
+module opt_share_test(
+  input signed [7:0]       a,
+  input signed [10:0]      b,
+  input signed [15:0]      c,
+  input [1:0]              sel,
+  output reg signed [15:0] res
+  );
+
+  always @* begin
+    case(sel)
+      0: res = a + b;
+      1: res = a - b;
+      2: res = a + c;
+      default: res = 16'bx;
+    endcase
+  end
+
+endmodule
diff --git a/tests/opt/opt_share_extend.ys b/tests/opt/opt_share_extend.ys
new file mode 100644
index 000000000..c553ee0fb
--- /dev/null
+++ b/tests/opt/opt_share_extend.ys
@@ -0,0 +1,13 @@
+read_verilog opt_share_extend.v
+proc;;
+copy opt_share_test merged
+
+alumacc merged
+opt merged
+opt_share merged
+opt_clean merged
+
+miter -equiv -flatten -ignore_gold_x -make_outputs -make_outcmp opt_share_test merged miter
+sat -set-def-inputs -verify -prove trigger 0 -show-inputs -show-outputs miter
+
+select -assert-count 1 -module merged t:$alu
diff --git a/tests/opt/opt_share_large_pmux_cat.v b/tests/opt/opt_share_large_pmux_cat.v
new file mode 100644
index 000000000..416ba3766
--- /dev/null
+++ b/tests/opt/opt_share_large_pmux_cat.v
@@ -0,0 +1,21 @@
+module opt_share_test(
+  input [15:0]      a,
+  input [15:0]      b,
+  input [15:0]      c,
+  input [2:0]       sel,
+  output reg [31:0] res
+  );
+
+  always @* begin
+    case(sel)
+      0: res = {a + b, a};
+      1: res = {a - b, b};
+      2: res = {a + c, c};
+      3: res = {a - c, a};
+      4: res = {b, b};
+      5: res = {c, c};
+      default: res = 32'bx;
+    endcase
+  end
+
+endmodule
diff --git a/tests/opt/opt_share_large_pmux_cat.ys b/tests/opt/opt_share_large_pmux_cat.ys
new file mode 100644
index 000000000..4186ca52e
--- /dev/null
+++ b/tests/opt/opt_share_large_pmux_cat.ys
@@ -0,0 +1,13 @@
+read_verilog opt_share_large_pmux_cat.v
+proc;;
+copy opt_share_test merged
+
+alumacc merged
+opt merged
+opt_share merged
+opt_clean merged
+
+miter -equiv -flatten -ignore_gold_x -make_outputs -make_outcmp opt_share_test merged miter
+sat -set-def-inputs -verify -prove trigger 0 -show-inputs -show-outputs miter
+
+select -assert-count 1 -module merged t:$alu
diff --git a/tests/opt/opt_share_large_pmux_cat_multipart.v b/tests/opt/opt_share_large_pmux_cat_multipart.v
new file mode 100644
index 000000000..34d2bd9a8
--- /dev/null
+++ b/tests/opt/opt_share_large_pmux_cat_multipart.v
@@ -0,0 +1,25 @@
+module opt_share_test(
+  input [15:0]      a,
+  input [15:0]      b,
+  input [15:0]      c,
+  input [15:0]      d,
+  input [2:0]       sel,
+  output reg [31:0] res
+  );
+
+  wire [15:0]       add0_res = a+d;
+
+  always @* begin
+    case(sel)
+      0: res = {add0_res, a};
+      1: res = {a - b, add0_res[7], 15'b0};
+      2: res = {b-a, b};
+      3: res = {d, b - c};
+      4: res = {d, b - a};
+      5: res = {c, d};
+      6: res = {a - c, b-d};
+      default: res = 32'bx;
+    endcase
+  end
+
+endmodule
diff --git a/tests/opt/opt_share_large_pmux_cat_multipart.ys b/tests/opt/opt_share_large_pmux_cat_multipart.ys
new file mode 100644
index 000000000..610bb8c6c
--- /dev/null
+++ b/tests/opt/opt_share_large_pmux_cat_multipart.ys
@@ -0,0 +1,14 @@
+read_verilog opt_share_large_pmux_cat_multipart.v
+proc;;
+copy opt_share_test merged
+
+alumacc merged
+opt merged
+
+opt_share merged
+opt_clean merged
+
+miter -equiv -flatten -ignore_gold_x -make_outputs -make_outcmp opt_share_test merged miter
+sat -set-def-inputs -verify -prove trigger 0 -show-inputs -show-outputs miter
+
+select -assert-count 4 -module merged t:$alu
diff --git a/tests/opt/opt_share_large_pmux_multipart.v b/tests/opt/opt_share_large_pmux_multipart.v
new file mode 100644
index 000000000..535adf96f
--- /dev/null
+++ b/tests/opt/opt_share_large_pmux_multipart.v
@@ -0,0 +1,23 @@
+module opt_share_test(
+  input [15:0]      a,
+  input [15:0]      b,
+  input [15:0]      c,
+  input [15:0]      d,
+  input [2:0]       sel,
+  output reg [15:0] res
+  );
+
+  always @* begin
+    case(sel)
+      0: res = a + d;
+      1: res = a - b;
+      2: res = b;
+      3: res = b - c;
+      4: res = b - a;
+      5: res = c;
+      6: res = a - c;
+      default: res = 16'bx;
+    endcase
+  end
+
+endmodule
diff --git a/tests/opt/opt_share_large_pmux_multipart.ys b/tests/opt/opt_share_large_pmux_multipart.ys
new file mode 100644
index 000000000..11182df1a
--- /dev/null
+++ b/tests/opt/opt_share_large_pmux_multipart.ys
@@ -0,0 +1,13 @@
+read_verilog opt_share_large_pmux_multipart.v
+proc;;
+copy opt_share_test merged
+
+alumacc merged
+opt merged
+opt_share merged
+opt_clean merged
+
+miter -equiv -flatten -ignore_gold_x -make_outputs -make_outcmp opt_share_test merged miter
+sat -set-def-inputs -verify -prove trigger 0 -show-inputs -show-outputs miter
+
+select -assert-count 2 -module merged t:$alu
diff --git a/tests/opt/opt_share_large_pmux_part.v b/tests/opt/opt_share_large_pmux_part.v
new file mode 100644
index 000000000..a9008fb5a
--- /dev/null
+++ b/tests/opt/opt_share_large_pmux_part.v
@@ -0,0 +1,21 @@
+module opt_share_test(
+  input [15:0]      a,
+  input [15:0]      b,
+  input [15:0]      c,
+  input [2:0]       sel,
+  output reg [15:0] res
+  );
+
+  always @* begin
+    case(sel)
+      0: res = a + b;
+      1: res = a - b;
+      2: res = a + c;
+      3: res = a - c;
+      4: res = b;
+      5: res = c;
+      default: res = 16'bx;
+    endcase
+  end
+
+endmodule
diff --git a/tests/opt/opt_share_large_pmux_part.ys b/tests/opt/opt_share_large_pmux_part.ys
new file mode 100644
index 000000000..6b594a3d6
--- /dev/null
+++ b/tests/opt/opt_share_large_pmux_part.ys
@@ -0,0 +1,13 @@
+read_verilog opt_share_large_pmux_part.v
+proc;;
+copy opt_share_test merged
+
+alumacc merged
+opt merged
+opt_share merged
+opt_clean merged
+
+miter -equiv -flatten -ignore_gold_x -make_outputs -make_outcmp opt_share_test merged miter
+sat -set-def-inputs -verify -prove trigger 0 -show-inputs -show-outputs miter
+
+select -assert-count 1 -module merged t:$alu
diff --git a/tests/opt/opt_share_mux_tree.v b/tests/opt/opt_share_mux_tree.v
new file mode 100644
index 000000000..cc5ae4eb9
--- /dev/null
+++ b/tests/opt/opt_share_mux_tree.v
@@ -0,0 +1,18 @@
+module opt_share_test(
+  input [15:0]      a,
+  input [15:0]      b,
+  input [15:0]      c,
+  input [1:0]       sel,
+  output reg [15:0] res
+  );
+
+  always @* begin
+    case(sel)
+      0: res = a + b;
+      1: res = a - b;
+      2: res = a + c;
+      default: res = 16'bx;
+    endcase
+  end
+
+endmodule
diff --git a/tests/opt/opt_share_mux_tree.ys b/tests/opt/opt_share_mux_tree.ys
new file mode 100644
index 000000000..58473039f
--- /dev/null
+++ b/tests/opt/opt_share_mux_tree.ys
@@ -0,0 +1,13 @@
+read_verilog opt_share_mux_tree.v
+proc;;
+copy opt_share_test merged
+
+alumacc merged
+opt merged
+opt_share merged
+opt_clean merged
+
+miter -equiv -flatten -ignore_gold_x -make_outputs -make_outcmp opt_share_test merged miter
+sat -set-def-inputs -verify -prove trigger 0 -show-inputs -show-outputs miter
+
+select -assert-count 1 -module merged t:$alu
diff --git a/tests/opt_share/.gitignore b/tests/opt_share/.gitignore
new file mode 100644
index 000000000..9c595a6fb
--- /dev/null
+++ b/tests/opt_share/.gitignore
@@ -0,0 +1 @@
+temp
diff --git a/tests/opt_share/generate.py b/tests/opt_share/generate.py
new file mode 100644
index 000000000..2ec92f7de
--- /dev/null
+++ b/tests/opt_share/generate.py
@@ -0,0 +1,86 @@
+#!/usr/bin/env python3
+
+import argparse
+import sys
+import random
+from contextlib import contextmanager
+
+
+@contextmanager
+def redirect_stdout(new_target):
+    old_target, sys.stdout = sys.stdout, new_target
+    try:
+        yield new_target
+    finally:
+        sys.stdout = old_target
+
+
+def random_plus_x():
+    return "%s x" % random.choice(['+', '+', '+', '-', '-', '|', '&', '^'])
+
+
+def maybe_plus_x(expr):
+    if random.randint(0, 4) == 0:
+        return "(%s %s)" % (expr, random_plus_x())
+    else:
+        return expr
+
+
+parser = argparse.ArgumentParser(
+    formatter_class=argparse.ArgumentDefaultsHelpFormatter)
+parser.add_argument('-S', '--seed', type=int, help='seed for PRNG')
+parser.add_argument('-c',
+                    '--count',
+                    type=int,
+                    default=100,
+                    help='number of test cases to generate')
+args = parser.parse_args()
+
+if args.seed is not None:
+    print("PRNG seed: %d" % args.seed)
+    random.seed(args.seed)
+
+for idx in range(args.count):
+    with open('temp/uut_%05d.v' % idx, 'w') as f:
+        with redirect_stdout(f):
+            print('module uut_%05d(a, b, c, s, y);' % (idx))
+            op = random.choice([
+                random.choice(['+', '-', '*', '/', '%']),
+                random.choice(['<', '<=', '==', '!=', '===', '!==', '>=',
+                               '>']),
+                random.choice(['<<', '>>', '<<<', '>>>']),
+                random.choice(['|', '&', '^', '~^', '||', '&&']),
+            ])
+            print('  input%s [%d:0] a;' % (random.choice(['', ' signed']), 8))
+            print('  input%s [%d:0] b;' % (random.choice(['', ' signed']), 8))
+            print('  input%s [%d:0] c;' % (random.choice(['', ' signed']), 8))
+            print('  input s;')
+            print('  output [%d:0] y;' % 8)
+            ops1 = ['a', 'b']
+            ops2 = ['a', 'c']
+            random.shuffle(ops1)
+            random.shuffle(ops2)
+            cast1 = random.choice(['', '$signed', '$unsigned'])
+            cast2 = random.choice(['', '$signed', '$unsigned'])
+            print('  assign y = (s ? %s(%s %s %s) : %s(%s %s %s));' %
+                  (cast1, ops1[0], op, ops1[1],
+                   cast2, ops2[0], op, ops2[1]))
+            print('endmodule')
+
+    with open('temp/uut_%05d.ys' % idx, 'w') as f:
+        with redirect_stdout(f):
+            print('read_verilog temp/uut_%05d.v' % idx)
+            print('proc;;')
+            print('copy uut_%05d gold' % idx)
+            print('rename uut_%05d gate' % idx)
+            print('tee -a temp/all_share_log.txt log')
+            print('tee -a temp/all_share_log.txt log #job# uut_%05d' % idx)
+            print('tee -a temp/all_share_log.txt opt gate')
+            print('tee -a temp/all_share_log.txt opt_share gate')
+            print('tee -a temp/all_share_log.txt opt_clean gate')
+            print(
+                'miter -equiv -flatten -ignore_gold_x -make_outputs -make_outcmp gold gate miter'
+            )
+            print(
+                'sat -set-def-inputs -verify -prove trigger 0 -show-inputs -show-outputs miter'
+            )
diff --git a/tests/opt_share/run-test.sh b/tests/opt_share/run-test.sh
new file mode 100755
index 000000000..e01552646
--- /dev/null
+++ b/tests/opt_share/run-test.sh
@@ -0,0 +1,39 @@
+#!/bin/bash
+
+# run this test many times:
+# time bash -c 'for ((i=0; i<100; i++)); do echo "-- $i --"; bash run-test.sh || exit 1; done'
+
+set -e
+
+OPTIND=1
+count=100
+seed=""    # default to no seed specified
+while getopts "c:S:" opt
+do
+  case "$opt" in
+		c) count="$OPTARG" ;;
+		S) seed="-S $OPTARG" ;;
+  esac
+done
+shift "$((OPTIND-1))"
+
+rm -rf temp
+mkdir -p temp
+echo "generating tests.."
+python3 generate.py -c $count $seed
+
+echo "running tests.."
+for i in $( ls temp/*.ys | sed 's,[^0-9],,g; s,^0*\(.\),\1,g;' ); do
+	echo -n "[$i]"
+	idx=$( printf "%05d" $i )
+	../../yosys -ql temp/uut_${idx}.log temp/uut_${idx}.ys
+done
+echo
+
+failed_share=$( echo $( gawk '/^#job#/ { j=$2; db[j]=0; } /^Removing [246] cells/ { delete db[j]; } END { for (j in db) print(j); }' temp/all_share_log.txt ) )
+if [ -n "$failed_share" ]; then
+	echo "Resource sharing failed for the following test cases: $failed_share"
+	false
+fi
+
+exit 0