Merge branch 'master' into master

10 files changed, 367 insertions, 4 deletions

diff --git a/CHANGELOG b/CHANGELOG
index 650a6aeaf..e0b0eb05e 100644
--- a/CHANGELOG
+++ b/CHANGELOG
@@ -61,6 +61,7 @@ Yosys 0.9 .. Yosys 0.9-dev
     - Added "abc9 -dff"
     - Added "synth_xilinx -dff"
     - Improved support of $readmem[hb] Memory Content File inclusion
+    - Added "opt_lut_ins" pass
 
 Yosys 0.8 .. Yosys 0.9
 ----------------------
diff --git a/passes/opt/Makefile.inc b/passes/opt/Makefile.inc
index 002c1a6a1..3133927bb 100644
--- a/passes/opt/Makefile.inc
+++ b/passes/opt/Makefile.inc
@@ -15,6 +15,7 @@ OBJS += passes/opt/wreduce.o
 OBJS += passes/opt/opt_demorgan.o
 OBJS += passes/opt/rmports.o
 OBJS += passes/opt/opt_lut.o
+OBJS += passes/opt/opt_lut_ins.o
 OBJS += passes/opt/pmux2shiftx.o
 OBJS += passes/opt/muxpack.o
 endif
diff --git a/passes/opt/opt_lut_ins.cc b/passes/opt/opt_lut_ins.cc
new file mode 100644
index 000000000..cf5248ced
--- /dev/null
+++ b/passes/opt/opt_lut_ins.cc
@@ -0,0 +1,278 @@
+/*
+ *  yosys -- Yosys Open SYnthesis Suite
+ *
+ *  Copyright (C) 2012  Clifford Wolf <clifford@clifford.at>
+ *
+ *  Permission to use, copy, modify, and/or distribute this software for any
+ *  purpose with or without fee is hereby granted, provided that the above
+ *  copyright notice and this permission notice appear in all copies.
+ *
+ *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ *  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ *  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ *  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ *  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ */
+
+#include "kernel/yosys.h"
+#include "kernel/sigtools.h"
+
+USING_YOSYS_NAMESPACE
+PRIVATE_NAMESPACE_BEGIN
+
+struct OptLutInsPass : public Pass {
+	OptLutInsPass() : Pass("opt_lut_ins", "discard unused LUT inputs") { }
+	void help() YS_OVERRIDE
+	{
+		//   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
+		log("\n");
+		log("    opt_lut_ins [options] [selection]\n");
+		log("\n");
+		log("This pass removes unused inputs from LUT cells (that is, inputs that can not\n");
+		log("influence the output signal given this LUT's value).  While such LUTs cannot\n");
+		log("be directly emitted by ABC, they can be a result of various post-ABC\n");
+		log("transformations, such as mapping wide LUTs (not all sub-LUTs will use the\n");
+		log("full set of inputs) or optimizations such as xilinx_dffopt.\n");
+		log("\n");
+		log("    -tech <technology>\n");
+		log("        Instead of generic $lut cells, operate on LUT cells specific\n");
+		log("        to the given technology.  Valid values are: xilinx, ecp5, gowin.\n");
+		log("\n");
+	}
+	void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
+	{
+		log_header(design, "Executing OPT_LUT_INS pass (discard unused LUT inputs).\n");
+		string techname;
+
+		size_t argidx;
+		for (argidx = 1; argidx < args.size(); argidx++)
+		{
+			if (args[argidx] == "-tech" && argidx+1 < args.size()) {
+				techname = args[++argidx];
+				continue;
+			}
+			break;
+		}
+		extra_args(args, argidx, design);
+
+		if (techname != "" && techname != "xilinx" && techname != "ecp5" && techname != "gowin")
+			log_cmd_error("Unsupported technology: '%s'\n", techname.c_str());
+
+		for (auto module : design->selected_modules())
+		{
+			log("Optimizing LUTs in %s.\n", log_id(module));
+
+			std::vector<Cell *> remove_cells;
+			// Gather LUTs.
+			for (auto cell : module->selected_cells())
+			{
+				if (cell->get_bool_attribute(ID::keep))
+					continue;
+				Const lut;
+				std::vector<SigBit> inputs;
+				std::vector<SigBit> output;
+				bool ignore_const = false;
+				if (techname == "") {
+					if (cell->type != ID($lut))
+						continue;
+					inputs = cell->getPort(ID::A).bits();
+					output = cell->getPort(ID::Y);
+					lut = cell->getParam(ID(LUT));
+				} else if (techname == "xilinx" || techname == "gowin") {
+					if (cell->type == ID(LUT1)) {
+						inputs = {
+							cell->getPort(ID(I0)),
+						};
+					} else if (cell->type == ID(LUT2)) {
+						inputs = {
+							cell->getPort(ID(I0)),
+							cell->getPort(ID(I1)),
+						};
+					} else if (cell->type == ID(LUT3)) {
+						inputs = {
+							cell->getPort(ID(I0)),
+							cell->getPort(ID(I1)),
+							cell->getPort(ID(I2)),
+						};
+					} else if (cell->type == ID(LUT4)) {
+						inputs = {
+							cell->getPort(ID(I0)),
+							cell->getPort(ID(I1)),
+							cell->getPort(ID(I2)),
+							cell->getPort(ID(I3)),
+						};
+					} else if (cell->type == ID(LUT5)) {
+						inputs = {
+							cell->getPort(ID(I0)),
+							cell->getPort(ID(I1)),
+							cell->getPort(ID(I2)),
+							cell->getPort(ID(I3)),
+							cell->getPort(ID(I4)),
+						};
+					} else if (cell->type == ID(LUT6)) {
+						inputs = {
+							cell->getPort(ID(I0)),
+							cell->getPort(ID(I1)),
+							cell->getPort(ID(I2)),
+							cell->getPort(ID(I3)),
+							cell->getPort(ID(I4)),
+							cell->getPort(ID(I5)),
+						};
+					} else {
+						// Not a LUT.
+						continue;
+					}
+					lut = cell->getParam(ID(INIT));
+					if (techname == "xilinx")
+						output = cell->getPort(ID(O));
+					else
+						output = cell->getPort(ID(F));
+				} else if (techname == "ecp5") {
+					if (cell->type == ID(LUT4)) {
+						inputs = {
+							cell->getPort(ID::A),
+							cell->getPort(ID::B),
+							cell->getPort(ID(C)),
+							cell->getPort(ID(D)),
+						};
+						lut = cell->getParam(ID(INIT));
+						output = cell->getPort(ID(Z));
+						ignore_const = true;
+					} else {
+						// Not a LUT.
+						continue;
+					}
+				}
+				std::vector<int> swizzle;
+				std::vector<SigBit> new_inputs;
+				bool doit = false;
+				for (int i = 0; i < GetSize(inputs); i++) {
+					SigBit input = inputs[i];
+					if (!input.wire) {
+						if (input.data == State::S1)
+							swizzle.push_back(-2);
+						else
+							swizzle.push_back(-1);
+						// For ECP5, smaller LUTs are
+						// implemented as LUT4s with
+						// extra const inputs.  Do not
+						// consider that to be a reason
+						// to redo a LUT.
+						if (!ignore_const)
+							doit = true;
+					} else {
+						bool redundant = true;
+						for (int j = 0; j < GetSize(lut); j++) {
+							if (lut[j] != lut[j ^ 1 << i])
+								redundant = false;
+						}
+						if (redundant) {
+							swizzle.push_back(-1);
+							doit = true;
+						} else {
+							swizzle.push_back(GetSize(new_inputs));
+							new_inputs.push_back(input);
+						}
+					}
+				}
+				if (!doit)
+					continue;
+				log("  Optimizing lut %s (%d -> %d)\n", log_id(cell), GetSize(inputs), GetSize(new_inputs));
+				if (techname == "ecp5") {
+					// Pad the LUT to 4 inputs, adding consts from the front.
+					int extra = 4 - GetSize(new_inputs);
+					log_assert(extra >= 0);
+					if (extra) {
+						for (int i = 0; i < extra; i++)
+							new_inputs.insert(new_inputs.begin(), State::S0);
+						for (auto &swz : swizzle)
+							if (swz >= 0)
+								swz += extra;
+					}
+				}
+				Const new_lut(0, 1 << GetSize(new_inputs));
+				for (int i = 0; i < GetSize(new_lut); i++) {
+					int lidx = 0;
+					for (int j = 0; j < GetSize(inputs); j++) {
+						int val;
+						if (swizzle[j] == -2) {
+							val = 1;
+						} else if (swizzle[j] == -1) {
+							val = 0;
+						} else {
+							val = (i >> swizzle[j]) & 1;
+						}
+						lidx |= val << j;
+					}
+					new_lut[i] = lut[lidx];
+				}
+				// For ecp5, do not replace with a const driver — the nextpnr
+				// packer requires a complete set of LUTs for wide LUT muxes.
+				if (new_inputs.empty() && techname != "ecp5") {
+					// const driver.
+					remove_cells.push_back(cell);
+					module->connect(output, new_lut[0]);
+				} else {
+					if (techname == "") {
+						cell->setParam(ID(LUT), new_lut);
+						cell->setParam(ID(WIDTH), GetSize(new_inputs));
+						cell->setPort(ID::A, new_inputs);
+					} else if (techname == "ecp5") {
+						log_assert(GetSize(new_inputs) == 4);
+						cell->setParam(ID(INIT), new_lut);
+						cell->setPort(ID::A, new_inputs[0]);
+						cell->setPort(ID::B, new_inputs[1]);
+						cell->setPort(ID(C), new_inputs[2]);
+						cell->setPort(ID(D), new_inputs[3]);
+					} else {
+						// xilinx, gowin
+						cell->setParam(ID(INIT), new_lut);
+						if (techname == "xilinx")
+							log_assert(GetSize(new_inputs) <= 6);
+						else
+							log_assert(GetSize(new_inputs) <= 4);
+						if (GetSize(new_inputs) == 1)
+							cell->type = ID(LUT1);
+						else if (GetSize(new_inputs) == 2)
+							cell->type = ID(LUT2);
+						else if (GetSize(new_inputs) == 3)
+							cell->type = ID(LUT3);
+						else if (GetSize(new_inputs) == 4)
+							cell->type = ID(LUT4);
+						else if (GetSize(new_inputs) == 5)
+							cell->type = ID(LUT5);
+						else if (GetSize(new_inputs) == 6)
+							cell->type = ID(LUT6);
+						else
+							log_assert(0);
+						cell->unsetPort(ID(I0));
+						cell->unsetPort(ID(I1));
+						cell->unsetPort(ID(I2));
+						cell->unsetPort(ID(I3));
+						cell->unsetPort(ID(I4));
+						cell->unsetPort(ID(I5));
+						cell->setPort(ID(I0), new_inputs[0]);
+						if (GetSize(new_inputs) >= 2)
+							cell->setPort(ID(I1), new_inputs[1]);
+						if (GetSize(new_inputs) >= 3)
+							cell->setPort(ID(I2), new_inputs[2]);
+						if (GetSize(new_inputs) >= 4)
+							cell->setPort(ID(I3), new_inputs[3]);
+						if (GetSize(new_inputs) >= 5)
+							cell->setPort(ID(I4), new_inputs[4]);
+						if (GetSize(new_inputs) >= 6)
+							cell->setPort(ID(I5), new_inputs[5]);
+					}
+				}
+			}
+			for (auto cell : remove_cells)
+				module->remove(cell);
+		}
+	}
+} XilinxDffOptPass;
+
+PRIVATE_NAMESPACE_END
+
diff --git a/techlibs/ecp5/synth_ecp5.cc b/techlibs/ecp5/synth_ecp5.cc
index 6583f43fd..bce20f604 100644
--- a/techlibs/ecp5/synth_ecp5.cc
+++ b/techlibs/ecp5/synth_ecp5.cc
@@ -343,6 +343,7 @@ struct SynthEcp5Pass : public ScriptPass
 			else
 				run("techmap -map +/ecp5/cells_map.v", "(with -D NO_LUT in vpr mode)");
 
+			run("opt_lut_ins -tech ecp5");
 			run("clean");
 		}
 
diff --git a/techlibs/gowin/synth_gowin.cc b/techlibs/gowin/synth_gowin.cc
index c5b41b503..99dd3834b 100644
--- a/techlibs/gowin/synth_gowin.cc
+++ b/techlibs/gowin/synth_gowin.cc
@@ -246,6 +246,7 @@ struct SynthGowinPass : public ScriptPass
 		if (check_label("map_cells"))
 		{
 			run("techmap -map +/gowin/cells_map.v");
+			run("opt_lut_ins -tech gowin");
 			run("setundef -undriven -params -zero");
 			run("hilomap -singleton -hicell VCC V -locell GND G");
 			if (!noiopads || help_mode)
diff --git a/techlibs/xilinx/synth_xilinx.cc b/techlibs/xilinx/synth_xilinx.cc
index 8119d307c..5a28bb139 100644
--- a/techlibs/xilinx/synth_xilinx.cc
+++ b/techlibs/xilinx/synth_xilinx.cc
@@ -597,6 +597,7 @@ struct SynthXilinxPass : public ScriptPass
 				techmap_args += stringf(" -map %s", ff_map_file.c_str());
 			run("techmap " + techmap_args);
 			run("xilinx_dffopt");
+			run("opt_lut_ins -tech xilinx");
 		}
 
 		if (check_label("finalize")) {
diff --git a/tests/arch/ecp5/opt_lut_ins.ys b/tests/arch/ecp5/opt_lut_ins.ys
new file mode 100644
index 000000000..2bc546912
--- /dev/null
+++ b/tests/arch/ecp5/opt_lut_ins.ys
@@ -0,0 +1,32 @@
+read_ilang << EOF
+
+module \top
+
+  wire input 1 \A
+  wire input 2 \B
+  wire input 3 \C
+  wire input 4 \D
+
+  wire output 5 \Z
+
+  cell \LUT4 $0
+    parameter \INIT 16'1111110011000000
+    connect \A \A
+    connect \B \B
+    connect \C \C
+    connect \D \D
+    connect \Z \Z
+  end
+end
+
+EOF
+
+read_verilog -lib +/ecp5/cells_sim.v
+
+equiv_opt -assert -map +/ecp5/cells_sim.v opt_lut_ins -tech ecp5
+
+design -load postopt
+
+select -assert-count 1 top/t:LUT4
+select -assert-count 0 top/w:A %co top/t:LUT4 %i
+select -assert-count 1 top/w:B %co top/t:LUT4 %i
diff --git a/tests/arch/gowin/mux.ys b/tests/arch/gowin/mux.ys
index afad29a89..33b092284 100644
--- a/tests/arch/gowin/mux.ys
+++ b/tests/arch/gowin/mux.ys
@@ -18,13 +18,13 @@ proc
 equiv_opt -assert -map +/gowin/cells_sim.v synth_gowin # 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 4 t:LUT4
+select -assert-count 4 t:LUT*
 select -assert-count 2 t:MUX2_LUT5
 select -assert-count 1 t:MUX2_LUT6
 select -assert-count 6 t:IBUF
 select -assert-count 1 t:OBUF
 
-select -assert-none t:LUT4 t:MUX2_LUT6 t:MUX2_LUT5 t:IBUF t:OBUF %% t:* %D
+select -assert-none t:LUT* t:MUX2_LUT6 t:MUX2_LUT5 t:IBUF t:OBUF %% t:* %D
 
 design -load read
 hierarchy -top mux8
@@ -35,7 +35,7 @@ cd mux8 # Constrain all select calls below inside the top module
 select -assert-count 11 t:IBUF
 select -assert-count 1 t:OBUF
 
-select -assert-none t:LUT4 t:MUX2_LUT6 t:MUX2_LUT5 t:IBUF t:OBUF %% t:* %D
+select -assert-none t:LUT* t:MUX2_LUT6 t:MUX2_LUT5 t:IBUF t:OBUF %% t:* %D
 
 design -load read
 hierarchy -top mux16
@@ -46,4 +46,4 @@ cd mux16 # Constrain all select calls below inside the top module
 select -assert-count 20 t:IBUF
 select -assert-count 1 t:OBUF
 
-select -assert-none t:LUT4 t:MUX2_LUT6 t:MUX2_LUT5 t:MUX2_LUT6 t:MUX2_LUT7 t:MUX2_LUT8 t:IBUF t:OBUF %% t:* %D
+select -assert-none t:GND t:VCC t:LUT* t:MUX2_LUT6 t:MUX2_LUT5 t:MUX2_LUT6 t:MUX2_LUT7 t:MUX2_LUT8 t:IBUF t:OBUF %% t:* %D
diff --git a/tests/arch/xilinx/opt_lut_ins.ys b/tests/arch/xilinx/opt_lut_ins.ys
new file mode 100644
index 000000000..a01d02179
--- /dev/null
+++ b/tests/arch/xilinx/opt_lut_ins.ys
@@ -0,0 +1,25 @@
+read_ilang << EOF
+
+module \top
+
+  wire width 4 input 1 \A
+
+  wire output 2 \O
+
+  cell \LUT4 $0
+    parameter \INIT 16'1111110011000000
+    connect \I0 \A [0]
+    connect \I1 \A [1]
+    connect \I2 \A [2]
+    connect \I3 \A [3]
+    connect \O \O
+  end
+end
+
+EOF
+
+equiv_opt -assert -map +/xilinx/cells_sim.v opt_lut_ins -tech xilinx
+
+design -load postopt
+
+select -assert-count 1 t:LUT3
diff --git a/tests/opt/opt_lut_ins.ys b/tests/opt/opt_lut_ins.ys
new file mode 100644
index 000000000..82460b164
--- /dev/null
+++ b/tests/opt/opt_lut_ins.ys
@@ -0,0 +1,23 @@
+read_ilang << EOF
+
+module \top
+
+  wire width 4 input 1 \A
+
+  wire output 2 \Y
+
+  cell $lut \lut
+    parameter \LUT 16'1111110011000000
+    parameter \WIDTH 4
+    connect \A \A
+    connect \Y \Y
+  end
+end
+
+EOF
+
+equiv_opt -assert opt_lut_ins
+
+design -load postopt
+
+select -assert-count 1 t:$lut r:WIDTH=3 %i