Imported GIT HEAD: 0.8+20190328git32bd0f2

7 files changed, 906 insertions, 110 deletions

diff --git a/passes/opt/Makefile.inc b/passes/opt/Makefile.inc
index 0d01e9d3..c3e0a2a4 100644
--- a/passes/opt/Makefile.inc
+++ b/passes/opt/Makefile.inc
@@ -12,5 +12,6 @@ OBJS += passes/opt/share.o
 OBJS += passes/opt/wreduce.o
 OBJS += passes/opt/opt_demorgan.o
 OBJS += passes/opt/rmports.o
+OBJS += passes/opt/opt_lut.o
 endif
 
diff --git a/passes/opt/opt_expr.cc b/passes/opt/opt_expr.cc
index 0ba233c6..a05db2a4 100644
--- a/passes/opt/opt_expr.cc
+++ b/passes/opt/opt_expr.cc
@@ -155,6 +155,13 @@ bool group_cell_inputs(RTLIL::Module *module, RTLIL::Cell *cell, bool commutativ
 			new_b.append_bit(it.first.second);
 		}
 
+		if (cell->type.in("$and", "$or") && i == GRP_CONST_A) {
+			log("  Direct Connection: %s (%s with %s)\n", log_signal(new_b), log_id(cell->type), log_signal(new_a));
+			module->connect(new_y, new_b);
+			module->connect(new_conn);
+			continue;
+		}
+
 		RTLIL::Cell *c = module->addCell(NEW_ID, cell->type);
 
 		c->setPort("\\A", new_a);
@@ -259,6 +266,22 @@ bool is_one_or_minus_one(const Const &value, bool is_signed, bool &is_negative)
 	return last_bit_one;
 }
 
+int get_highest_hot_index(RTLIL::SigSpec signal)
+{
+	for (int i = GetSize(signal) - 1; i >= 0; i--)
+	{
+		if (signal[i] == RTLIL::State::S0)
+			continue;
+
+		if (signal[i] == RTLIL::State::S1)
+			return i;
+
+		break;
+	}
+
+	return -1;
+}
+
 // if the signal has only one bit set, return the index of that bit.
 // otherwise return -1
 int get_onehot_bit_index(RTLIL::SigSpec signal)
@@ -1344,118 +1367,139 @@ void replace_const_cells(RTLIL::Design *design, RTLIL::Module *module, bool cons
 			}
 		}
 
-		// replace a<0 or a>=0 with the top bit of a
+		// simplify comparisons
 		if (do_fine && (cell->type == "$lt" || cell->type == "$ge" || cell->type == "$gt" || cell->type == "$le"))
 		{
-			//used to decide whether the signal needs to be negated
-			bool is_lt = false;
-
-			//references the variable signal in the comparison
-			RTLIL::SigSpec sigVar;
-
-			//references the constant signal in the comparison
-			RTLIL::SigSpec sigConst;
-
-			// note that this signal must be constant for the optimization
-			// to take place, but it is not checked beforehand.
-			// If new passes are added, this signal must be checked for const-ness
-
-			//width of the variable port
-			int width;
-			int const_width;
-
-			bool var_signed;
-
-			if (cell->type == "$lt" || cell->type == "$ge") {
-				is_lt = cell->type == "$lt" ? 1 : 0;
-				sigVar = cell->getPort("\\A");
-				sigConst = cell->getPort("\\B");
-				width = cell->parameters["\\A_WIDTH"].as_int();
-				const_width = cell->parameters["\\B_WIDTH"].as_int();
-				var_signed = cell->parameters["\\A_SIGNED"].as_bool();
-			} else
-			if (cell->type == "$gt" || cell->type == "$le") {
-				is_lt = cell->type == "$gt" ? 1 : 0;
-				sigVar = cell->getPort("\\B");
-				sigConst = cell->getPort("\\A");
-				width = cell->parameters["\\B_WIDTH"].as_int();
-				const_width = cell->parameters["\\A_WIDTH"].as_int();
-				var_signed = cell->parameters["\\B_SIGNED"].as_bool();
-			} else
-				log_abort();
+			IdString cmp_type = cell->type;
+			SigSpec var_sig = cell->getPort("\\A");
+			SigSpec const_sig = cell->getPort("\\B");
+			int var_width = cell->parameters["\\A_WIDTH"].as_int();
+			int const_width = cell->parameters["\\B_WIDTH"].as_int();
+			bool is_signed = cell->getParam("\\A_SIGNED").as_bool();
 
-			// replace a(signed) < 0 with the high bit of a
-			if (sigConst.is_fully_const() && sigConst.is_fully_zero() && var_signed == true)
+			if (!const_sig.is_fully_const())
 			{
-				RTLIL::SigSpec a_prime(RTLIL::State::S0, cell->parameters["\\Y_WIDTH"].as_int());
-				a_prime[0] = sigVar[width - 1];
-				if (is_lt) {
-					log("Replacing %s cell `%s' (implementing X<0) with X[%d]: %s\n",
-							log_id(cell->type), log_id(cell), width-1, log_signal(a_prime));
-					module->connect(cell->getPort("\\Y"), a_prime);
-					module->remove(cell);
-				} else {
-					log("Replacing %s cell `%s' (implementing X>=0) with ~X[%d]: %s\n",
-							log_id(cell->type), log_id(cell), width-1, log_signal(a_prime));
-					module->addNot(NEW_ID, a_prime, cell->getPort("\\Y"));
-					module->remove(cell);
-				}
-				did_something = true;
-				goto next_cell;
-			} else
-			if (sigConst.is_fully_const() && sigConst.is_fully_def() && var_signed == false)
+				std::swap(var_sig, const_sig);
+				std::swap(var_width, const_width);
+				if (cmp_type == "$gt")
+					cmp_type = "$lt";
+				else if (cmp_type == "$lt")
+					cmp_type = "$gt";
+				else if (cmp_type == "$ge")
+					cmp_type = "$le";
+				else if (cmp_type == "$le")
+					cmp_type = "$ge";
+			}
+
+			if (const_sig.is_fully_def() && const_sig.is_fully_const())
 			{
-				if (sigConst.is_fully_zero()) {
-					RTLIL::SigSpec a_prime(RTLIL::State::S0, 1);
-					if (is_lt) {
-						log("Replacing %s cell `%s' (implementing unsigned X<0) with constant false.\n",
-								log_id(cell->type), log_id(cell));
-						a_prime[0] = RTLIL::State::S0;
-					} else {
-						log("Replacing %s cell `%s' (implementing unsigned X>=0) with constant true.\n",
-								log_id(cell->type), log_id(cell));
-						a_prime[0] = RTLIL::State::S1;
+				std::string condition, replacement;
+				SigSpec replace_sig(State::S0, GetSize(cell->getPort("\\Y")));
+				bool replace = false;
+				bool remove = false;
+
+				if (!is_signed)
+				{ /* unsigned */
+					if (const_sig.is_fully_zero() && cmp_type == "$lt") {
+						condition   = "unsigned X<0";
+						replacement = "constant 0";
+						replace_sig[0] = State::S0;
+						replace = true;
+					}
+					if (const_sig.is_fully_zero() && cmp_type == "$ge") {
+						condition   = "unsigned X>=0";
+						replacement = "constant 1";
+						replace_sig[0] = State::S1;
+						replace = true;
+					}
+					if (const_width == var_width && const_sig.is_fully_ones() && cmp_type == "$gt") {
+						condition   = "unsigned X>~0";
+						replacement = "constant 0";
+						replace_sig[0] = State::S0;
+						replace = true;
+					}
+					if (const_width == var_width && const_sig.is_fully_ones() && cmp_type == "$le") {
+						condition   = "unsigned X<=~0";
+						replacement = "constant 1";
+						replace_sig[0] = State::S1;
+						replace = true;
 					}
-					module->connect(cell->getPort("\\Y"), a_prime);
-					module->remove(cell);
-					did_something = true;
-					goto next_cell;
-				}
 
-				int const_bit_set = get_onehot_bit_index(sigConst);
-				if (const_bit_set >= 0 && const_bit_set < width) {
-					int bit_set = const_bit_set;
-					RTLIL::SigSpec a_prime(RTLIL::State::S0, width - bit_set);
-					for (int i = bit_set; i < width; i++) {
-						a_prime[i - bit_set] = sigVar[i];
+					int const_bit_hot = get_onehot_bit_index(const_sig);
+					if (const_bit_hot >= 0 && const_bit_hot < var_width)
+					{
+						RTLIL::SigSpec var_high_sig(RTLIL::State::S0, var_width - const_bit_hot);
+						for (int i = const_bit_hot; i < var_width; i++) {
+							var_high_sig[i - const_bit_hot] = var_sig[i];
+						}
+
+						if (cmp_type == "$lt")
+						{
+							condition   = stringf("unsigned X<%s", log_signal(const_sig));
+							replacement = stringf("!X[%d:%d]", var_width - 1, const_bit_hot);
+							module->addLogicNot(NEW_ID, var_high_sig, cell->getPort("\\Y"));
+							remove = true;
+						}
+						if (cmp_type == "$ge")
+						{
+							condition   = stringf("unsigned X>=%s", log_signal(const_sig));
+							replacement = stringf("|X[%d:%d]", var_width - 1, const_bit_hot);
+							module->addReduceOr(NEW_ID, var_high_sig, cell->getPort("\\Y"));
+							remove = true;
+						}
 					}
-					if (is_lt) {
-						log("Replacing %s cell `%s' (implementing unsigned X<%s) with !X[%d:%d]: %s.\n",
-								log_id(cell->type), log_id(cell), log_signal(sigConst), width - 1, bit_set, log_signal(a_prime));
-						module->addLogicNot(NEW_ID, a_prime, cell->getPort("\\Y"));
-					} else {
-						log("Replacing %s cell `%s' (implementing unsigned X>=%s) with |X[%d:%d]: %s.\n",
-								log_id(cell->type), log_id(cell), log_signal(sigConst), width - 1, bit_set, log_signal(a_prime));
-						module->addReduceOr(NEW_ID, a_prime, cell->getPort("\\Y"));
+
+					int const_bit_set = get_highest_hot_index(const_sig);
+					if(const_bit_set >= var_width)
+					{
+						string cmp_name;
+						if (cmp_type == "$lt" || cmp_type == "$le")
+						{
+							if (cmp_type == "$lt") cmp_name = "<";
+							if (cmp_type == "$le") cmp_name = "<=";
+							condition   = stringf("unsigned X[%d:0]%s%s", var_width - 1, cmp_name.c_str(), log_signal(const_sig));
+							replacement = "constant 1";
+							replace_sig[0] = State::S1;
+							replace = true;
+						}
+						if (cmp_type == "$gt" || cmp_type == "$ge")
+						{
+							if (cmp_type == "$gt") cmp_name = ">";
+							if (cmp_type == "$ge") cmp_name = ">=";
+							condition   = stringf("unsigned X[%d:0]%s%s", var_width - 1, cmp_name.c_str(), log_signal(const_sig));
+							replacement = "constant 0";
+							replace_sig[0] = State::S0;
+							replace = true;
+						}
 					}
-					module->remove(cell);
-					did_something = true;
-					goto next_cell;
 				}
-				else if(const_bit_set >= width && const_bit_set >= 0){
-					RTLIL::SigSpec a_prime(RTLIL::State::S0, 1);
-					if(is_lt){
-						a_prime[0] = RTLIL::State::S1;
-						log("Replacing %s cell `%s' (implementing unsigned X[%d:0] < %s[%d:0]) with constant 0.\n", log_id(cell->type), log_id(cell), width-1, log_signal(sigConst),const_width-1);
+				else
+				{ /* signed */
+					if (const_sig.is_fully_zero() && cmp_type == "$lt")
+					{
+						condition   = "signed X<0";
+						replacement = stringf("X[%d]", var_width - 1);
+						replace_sig[0] = var_sig[var_width - 1];
+						replace = true;
 					}
-					else{
-						log("Replacing %s cell `%s' (implementing unsigned X[%d:0]>= %s[%d:0]) with constant 1.\n", log_id(cell->type), log_id(cell), width-1, log_signal(sigConst),const_width-1);
+					if (const_sig.is_fully_zero() && cmp_type == "$ge")
+					{
+						condition   = "signed X>=0";
+						replacement = stringf("X[%d]", var_width - 1);
+						module->addNot(NEW_ID, var_sig[var_width - 1], cell->getPort("\\Y"));
+						remove = true;
 					}
-					module->connect(cell->getPort("\\Y"), a_prime);
+				}
+
+				if (replace || remove)
+				{
+					log("Replacing %s cell `%s' (implementing %s) with %s.\n",
+							log_id(cell->type), log_id(cell), condition.c_str(), replacement.c_str());
+					if (replace)
+						module->connect(cell->getPort("\\Y"), replace_sig);
 					module->remove(cell);
 					did_something = true;
 					goto next_cell;
-
 				}
 			}
 		}
@@ -1477,7 +1521,7 @@ struct OptExprPass : public Pass {
 		log("    opt_expr [options] [selection]\n");
 		log("\n");
 		log("This pass performs const folding on internal cell types with constant inputs.\n");
-		log("It also performs some simple expression rewritring.\n");
+		log("It also performs some simple expression rewriting.\n");
 		log("\n");
 		log("    -mux_undef\n");
 		log("        remove 'undef' inputs from $mux, $pmux and $_MUX_ cells\n");
diff --git a/passes/opt/opt_lut.cc b/passes/opt/opt_lut.cc
new file mode 100644
index 00000000..26855fd7
--- /dev/null
+++ b/passes/opt/opt_lut.cc
@@ -0,0 +1,607 @@
+/*
+ *  yosys -- Yosys Open SYnthesis Suite
+ *
+ *  Copyright (C) 2018  whitequark <whitequark@whitequark.org>
+ *
+ *  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"
+#include "kernel/modtools.h"
+
+USING_YOSYS_NAMESPACE
+PRIVATE_NAMESPACE_BEGIN
+
+struct OptLutWorker
+{
+	dict<IdString, dict<int, IdString>> &dlogic;
+	RTLIL::Module *module;
+	ModIndex index;
+	SigMap sigmap;
+
+	pool<RTLIL::Cell*> luts;
+	dict<RTLIL::Cell*, int> luts_arity;
+	dict<RTLIL::Cell*, pool<RTLIL::Cell*>> luts_dlogics;
+	dict<RTLIL::Cell*, pool<int>> luts_dlogic_inputs;
+
+	int eliminated_count = 0, combined_count = 0;
+
+	bool evaluate_lut(RTLIL::Cell *lut, dict<SigBit, bool> inputs)
+	{
+		SigSpec lut_input = sigmap(lut->getPort("\\A"));
+		int lut_width = lut->getParam("\\WIDTH").as_int();
+		Const lut_table = lut->getParam("\\LUT");
+		int lut_index = 0;
+
+		for (int i = 0; i < lut_width; i++)
+		{
+			SigBit input = sigmap(lut_input[i]);
+			if (inputs.count(input))
+			{
+				lut_index |= inputs[input] << i;
+			}
+			else
+			{
+				lut_index |= SigSpec(lut_input[i]).as_bool() << i;
+			}
+		}
+
+		return lut_table.extract(lut_index).as_bool();
+	}
+
+	void show_stats_by_arity()
+	{
+		dict<int, int> arity_counts;
+		dict<IdString, int> dlogic_counts;
+		int max_arity = 0;
+
+		for (auto lut_arity : luts_arity)
+		{
+			max_arity = max(max_arity, lut_arity.second);
+			arity_counts[lut_arity.second]++;
+		}
+
+		for (auto &lut_dlogics : luts_dlogics)
+		{
+			for (auto &lut_dlogic : lut_dlogics.second)
+			{
+				dlogic_counts[lut_dlogic->type]++;
+			}
+		}
+
+		log("Number of LUTs: %8zu\n", luts.size());
+		for (int arity = 1; arity <= max_arity; arity++)
+		{
+			if (arity_counts[arity])
+				log("  %d-LUT %16d\n", arity, arity_counts[arity]);
+		}
+		for (auto &dlogic_count : dlogic_counts)
+		{
+			log("  with %-12s %4d\n", dlogic_count.first.c_str(), dlogic_count.second);
+		}
+	}
+
+	OptLutWorker(dict<IdString, dict<int, IdString>> &dlogic, RTLIL::Module *module, int limit) :
+		dlogic(dlogic), module(module), index(module), sigmap(module)
+	{
+		log("Discovering LUTs.\n");
+		for (auto cell : module->selected_cells())
+		{
+			if (cell->type == "$lut")
+			{
+				int lut_width = cell->getParam("\\WIDTH").as_int();
+				SigSpec lut_input = cell->getPort("\\A");
+				int lut_arity = 0;
+
+				log("Found $lut\\WIDTH=%d cell %s.%s.\n", lut_width, log_id(module), log_id(cell));
+				luts.insert(cell);
+
+				// First, find all dedicated logic we're connected to. This results in an overapproximation
+				// of such connections.
+				pool<RTLIL::Cell*> lut_all_dlogics;
+				for (int i = 0; i < lut_width; i++)
+				{
+					SigBit bit = lut_input[i];
+					for (auto &port : index.query_ports(bit))
+					{
+						if (dlogic.count(port.cell->type))
+						{
+							auto &dlogic_map = dlogic[port.cell->type];
+							if (dlogic_map.count(i))
+							{
+								if (port.port == dlogic_map[i])
+								{
+									lut_all_dlogics.insert(port.cell);
+								}
+							}
+						}
+					}
+				}
+
+				// Second, make sure that the connection to dedicated logic is legal. If it is not legal,
+				// it means one of the two things:
+				//   * The connection is spurious. I.e. this is dedicated logic that will be packed
+				//     with some other LUT, and it just happens to be connected to this LUT as well.
+				//   * The connection is illegal.
+				// In either of these cases, we don't need to concern ourselves with preserving the connection
+				// between this LUT and this dedicated logic cell.
+				pool<RTLIL::Cell*> lut_legal_dlogics;
+				pool<int> lut_dlogic_inputs;
+				for (auto lut_dlogic : lut_all_dlogics)
+				{
+					auto &dlogic_map = dlogic[lut_dlogic->type];
+					bool legal = true;
+					for (auto &dlogic_conn : dlogic_map)
+					{
+						if (lut_width <= dlogic_conn.first)
+						{
+							log("  LUT has illegal connection to %s cell %s.%s.\n", lut_dlogic->type.c_str(), log_id(module), log_id(lut_dlogic));
+							log("    LUT input A[%d] not present.\n", dlogic_conn.first);
+							legal = false;
+							break;
+						}
+						if (sigmap(lut_input[dlogic_conn.first]) != sigmap(lut_dlogic->getPort(dlogic_conn.second)))
+						{
+							log("  LUT has illegal connection to %s cell %s.%s.\n", lut_dlogic->type.c_str(), log_id(module), log_id(lut_dlogic));
+							log("    LUT input A[%d] (wire %s) not connected to %s port %s (wire %s).\n", dlogic_conn.first, log_signal(lut_input[dlogic_conn.first]), lut_dlogic->type.c_str(), dlogic_conn.second.c_str(), log_signal(lut_dlogic->getPort(dlogic_conn.second)));
+							legal = false;
+							break;
+						}
+					}
+
+					if (legal)
+					{
+						log("  LUT has legal connection to %s cell %s.%s.\n", lut_dlogic->type.c_str(), log_id(module), log_id(lut_dlogic));
+						lut_legal_dlogics.insert(lut_dlogic);
+						for (auto &dlogic_conn : dlogic_map)
+							lut_dlogic_inputs.insert(dlogic_conn.first);
+					}
+				}
+
+				// Third, determine LUT arity. An n-wide LUT that has k constant inputs and m inputs shared with dedicated
+				// logic implements an (n-k-m)-ary function.
+				for (int i = 0; i < lut_width; i++)
+				{
+					SigBit bit = lut_input[i];
+					if (bit.wire || lut_dlogic_inputs.count(i))
+						lut_arity++;
+				}
+
+				log("  Cell implements a %d-LUT.\n", lut_arity);
+				luts_arity[cell] = lut_arity;
+				luts_dlogics[cell] = lut_legal_dlogics;
+				luts_dlogic_inputs[cell] = lut_dlogic_inputs;
+			}
+		}
+		show_stats_by_arity();
+
+		log("\n");
+		log("Eliminating LUTs.\n");
+		pool<RTLIL::Cell*> worklist = luts;
+		while (worklist.size())
+		{
+			if (limit == 0)
+			{
+				log("Limit reached.\n");
+				break;
+			}
+
+			auto lut = worklist.pop();
+			SigSpec lut_input = sigmap(lut->getPort("\\A"));
+			pool<int> &lut_dlogic_inputs = luts_dlogic_inputs[lut];
+
+			vector<SigBit> lut_inputs;
+			for (auto &bit : lut_input)
+			{
+				if (bit.wire)
+					lut_inputs.push_back(sigmap(bit));
+			}
+
+			bool const0_match = true;
+			bool const1_match = true;
+			vector<bool> input_matches;
+			for (size_t i = 0; i < lut_inputs.size(); i++)
+				input_matches.push_back(true);
+
+			for (int eval = 0; eval < 1 << lut_inputs.size(); eval++)
+			{
+				dict<SigBit, bool> eval_inputs;
+				for (size_t i = 0; i < lut_inputs.size(); i++)
+					eval_inputs[lut_inputs[i]] = (eval >> i) & 1;
+				bool value = evaluate_lut(lut, eval_inputs);
+				if (value != 0)
+					const0_match = false;
+				if (value != 1)
+					const1_match = false;
+				for (size_t i = 0; i < lut_inputs.size(); i++)
+				{
+					if (value != eval_inputs[lut_inputs[i]])
+						input_matches[i] = false;
+				}
+			}
+
+			int input_match = -1;
+			for (size_t i = 0; i < lut_inputs.size(); i++)
+				if (input_matches[i])
+					input_match = i;
+
+			if (const0_match || const1_match || input_match != -1)
+			{
+				log("Found redundant cell %s.%s.\n", log_id(module), log_id(lut));
+
+				SigBit value;
+				if (const0_match)
+				{
+					log("  Cell evaluates constant 0.\n");
+					value = State::S0;
+				}
+				if (const1_match)
+				{
+					log("  Cell evaluates constant 1.\n");
+					value = State::S1;
+				}
+				if (input_match != -1) {
+					log("  Cell evaluates signal %s.\n", log_signal(lut_inputs[input_match]));
+					value = lut_inputs[input_match];
+				}
+
+				if (lut_dlogic_inputs.size())
+				{
+					log("  Not eliminating cell (connected to dedicated logic).\n");
+				}
+				else
+				{
+					SigSpec lut_output = lut->getPort("\\Y");
+					for (auto &port : index.query_ports(lut_output))
+					{
+						if (port.cell != lut && luts.count(port.cell))
+							worklist.insert(port.cell);
+					}
+
+					module->connect(lut_output, value);
+					sigmap.add(lut_output, value);
+
+					module->remove(lut);
+					luts.erase(lut);
+					luts_arity.erase(lut);
+					luts_dlogics.erase(lut);
+					luts_dlogic_inputs.erase(lut);
+
+					eliminated_count++;
+					if (limit > 0)
+						limit--;
+				}
+			}
+		}
+		show_stats_by_arity();
+
+		log("\n");
+		log("Combining LUTs.\n");
+		worklist = luts;
+		while (worklist.size())
+		{
+			if (limit == 0)
+			{
+				log("Limit reached.\n");
+				break;
+			}
+
+			auto lutA = worklist.pop();
+			SigSpec lutA_input = sigmap(lutA->getPort("\\A"));
+			SigSpec lutA_output = sigmap(lutA->getPort("\\Y")[0]);
+			int lutA_width = lutA->getParam("\\WIDTH").as_int();
+			int lutA_arity = luts_arity[lutA];
+			pool<int> &lutA_dlogic_inputs = luts_dlogic_inputs[lutA];
+
+			auto lutA_output_ports = index.query_ports(lutA->getPort("\\Y"));
+			if (lutA_output_ports.size() != 2)
+				continue;
+
+			for (auto &port : lutA_output_ports)
+			{
+				if (port.cell == lutA)
+					continue;
+
+				if (luts.count(port.cell))
+				{
+					auto lutB = port.cell;
+					SigSpec lutB_input = sigmap(lutB->getPort("\\A"));
+					SigSpec lutB_output = sigmap(lutB->getPort("\\Y")[0]);
+					int lutB_width = lutB->getParam("\\WIDTH").as_int();
+					int lutB_arity = luts_arity[lutB];
+					pool<int> &lutB_dlogic_inputs = luts_dlogic_inputs[lutB];
+
+					log("Found %s.%s (cell A) feeding %s.%s (cell B).\n", log_id(module), log_id(lutA), log_id(module), log_id(lutB));
+
+					if (index.query_is_output(lutA->getPort("\\Y")))
+					{
+						log("  Not combining LUTs (cascade connection feeds module output).\n");
+						continue;
+					}
+
+					pool<SigBit> lutA_inputs;
+					pool<SigBit> lutB_inputs;
+					for (auto &bit : lutA_input)
+					{
+						if (bit.wire)
+							lutA_inputs.insert(sigmap(bit));
+					}
+					for (auto &bit : lutB_input)
+					{
+						if (bit.wire)
+							lutB_inputs.insert(sigmap(bit));
+					}
+
+					pool<SigBit> common_inputs;
+					for (auto &bit : lutA_inputs)
+					{
+						if (lutB_inputs.count(bit))
+							common_inputs.insert(bit);
+					}
+
+					int lutM_arity = lutA_arity + lutB_arity - 1 - common_inputs.size();
+					if (lutA_dlogic_inputs.size())
+						log("  Cell A is a %d-LUT with %zu dedicated connections. ", lutA_arity, lutA_dlogic_inputs.size());
+					else
+						log("  Cell A is a %d-LUT. ", lutA_arity);
+					if (lutB_dlogic_inputs.size())
+						log("Cell B is a %d-LUT with %zu dedicated connections.\n", lutB_arity, lutB_dlogic_inputs.size());
+					else
+						log("Cell B is a %d-LUT.\n", lutB_arity);
+					log("  Cells share %zu input(s) and can be merged into one %d-LUT.\n", common_inputs.size(), lutM_arity);
+
+					const int COMBINE_A = 1, COMBINE_B = 2, COMBINE_EITHER = COMBINE_A | COMBINE_B;
+					int combine_mask = 0;
+					if (lutM_arity > lutA_width)
+					{
+						log("  Not combining LUTs into cell A (combined LUT wider than cell A).\n");
+					}
+					else if (lutB_dlogic_inputs.size() > 0)
+					{
+						log("  Not combining LUTs into cell A (cell B is connected to dedicated logic).\n");
+					}
+					else if (lutB->get_bool_attribute("\\lut_keep"))
+					{
+						log("  Not combining LUTs into cell A (cell B has attribute \\lut_keep).\n");
+					}
+					else
+					{
+						combine_mask |= COMBINE_A;
+					}
+					if (lutM_arity > lutB_width)
+					{
+						log("  Not combining LUTs into cell B (combined LUT wider than cell B).\n");
+					}
+					else if (lutA_dlogic_inputs.size() > 0)
+					{
+						log("  Not combining LUTs into cell B (cell A is connected to dedicated logic).\n");
+					}
+					else if (lutA->get_bool_attribute("\\lut_keep"))
+					{
+						log("  Not combining LUTs into cell B (cell A has attribute \\lut_keep).\n");
+					}
+					else
+					{
+						combine_mask |= COMBINE_B;
+					}
+
+					int combine = combine_mask;
+					if (combine == COMBINE_EITHER)
+					{
+						log("  Can combine into either cell.\n");
+						if (lutA_arity == 1)
+						{
+							log("    Cell A is a buffer or inverter, combining into cell B.\n");
+							combine = COMBINE_B;
+						}
+						else if (lutB_arity == 1)
+						{
+							log("    Cell B is a buffer or inverter, combining into cell A.\n");
+							combine = COMBINE_A;
+						}
+						else
+						{
+							log("    Arbitrarily combining into cell A.\n");
+							combine = COMBINE_A;
+						}
+					}
+
+					RTLIL::Cell *lutM, *lutR;
+					pool<SigBit> lutM_inputs, lutR_inputs;
+					pool<int> lutM_dlogic_inputs;
+					if (combine == COMBINE_A)
+					{
+						log("  Combining LUTs into cell A.\n");
+						lutM = lutA;
+						lutM_inputs = lutA_inputs;
+						lutM_dlogic_inputs = lutA_dlogic_inputs;
+						lutR = lutB;
+						lutR_inputs = lutB_inputs;
+					}
+					else if (combine == COMBINE_B)
+					{
+						log("  Combining LUTs into cell B.\n");
+						lutM = lutB;
+						lutM_inputs = lutB_inputs;
+						lutM_dlogic_inputs = lutB_dlogic_inputs;
+						lutR = lutA;
+						lutR_inputs = lutA_inputs;
+					}
+					else
+					{
+						log("  Cannot combine LUTs.\n");
+						continue;
+					}
+
+					pool<SigBit> lutR_unique;
+					for (auto &bit : lutR_inputs)
+					{
+						if (!common_inputs.count(bit) && bit != lutA_output)
+							lutR_unique.insert(bit);
+					}
+
+					int lutM_width = lutM->getParam("\\WIDTH").as_int();
+					SigSpec lutM_input = sigmap(lutM->getPort("\\A"));
+					std::vector<SigBit> lutM_new_inputs;
+					for (int i = 0; i < lutM_width; i++)
+					{
+						bool input_unused = false;
+						if (sigmap(lutM_input[i]) == lutA_output)
+							input_unused = true;
+						if (!lutM_input[i].wire && !lutM_dlogic_inputs.count(i))
+							input_unused = true;
+
+						if (input_unused && lutR_unique.size())
+						{
+							SigBit new_input = lutR_unique.pop();
+							log("    Connecting input %d as %s.\n", i, log_signal(new_input));
+							lutM_new_inputs.push_back(new_input);
+						}
+						else if (sigmap(lutM_input[i]) == lutA_output)
+						{
+							log("    Disconnecting cascade input %d.\n", i);
+							lutM_new_inputs.push_back(SigBit());
+						}
+						else
+						{
+							log("    Leaving input %d as %s.\n", i, log_signal(lutM_input[i]));
+							lutM_new_inputs.push_back(lutM_input[i]);
+						}
+					}
+					log_assert(lutR_unique.size() == 0);
+
+					RTLIL::Const lutM_new_table(State::Sx, 1 << lutM_width);
+					for (int eval = 0; eval < 1 << lutM_width; eval++)
+					{
+						dict<SigBit, bool> eval_inputs;
+						for (size_t i = 0; i < lutM_new_inputs.size(); i++)
+						{
+							eval_inputs[lutM_new_inputs[i]] = (eval >> i) & 1;
+						}
+						eval_inputs[lutA_output] = evaluate_lut(lutA, eval_inputs);
+						lutM_new_table[eval] = (RTLIL::State) evaluate_lut(lutB, eval_inputs);
+					}
+
+					log("  Cell A truth table: %s.\n", lutA->getParam("\\LUT").as_string().c_str());
+					log("  Cell B truth table: %s.\n", lutB->getParam("\\LUT").as_string().c_str());
+					log("  Merged truth table: %s.\n", lutM_new_table.as_string().c_str());
+
+					lutM->setParam("\\LUT", lutM_new_table);
+					lutM->setPort("\\A", lutM_new_inputs);
+					lutM->setPort("\\Y", lutB_output);
+
+					luts_arity[lutM] = lutM_arity;
+					luts.erase(lutR);
+					luts_arity.erase(lutR);
+					lutR->module->remove(lutR);
+
+					worklist.insert(lutM);
+					worklist.erase(lutR);
+
+					combined_count++;
+					if (limit > 0)
+						limit--;
+				}
+			}
+		}
+		show_stats_by_arity();
+	}
+};
+
+static void split(std::vector<std::string> &tokens, const std::string &text, char sep)
+{
+	size_t start = 0, end = 0;
+	while ((end = text.find(sep, start)) != std::string::npos) {
+		tokens.push_back(text.substr(start, end - start));
+		start = end + 1;
+	}
+	tokens.push_back(text.substr(start));
+}
+
+struct OptLutPass : public Pass {
+	OptLutPass() : Pass("opt_lut", "optimize LUT cells") { }
+	void help() YS_OVERRIDE
+	{
+		//   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
+		log("\n");
+		log("    opt_lut [options] [selection]\n");
+		log("\n");
+		log("This pass combines cascaded $lut cells with unused inputs.\n");
+		log("\n");
+		log("    -dlogic <type>:<cell-port>=<LUT-input>[:<cell-port>=<LUT-input>...]\n");
+		log("        preserve connections to dedicated logic cell <type> that has ports\n");
+		log("        <cell-port> connected to LUT inputs <LUT-input>. this includes\n");
+		log("        the case where both LUT and dedicated logic input are connected to\n");
+		log("        the same constant.\n");
+		log("\n");
+		log("    -limit N\n");
+		log("        only perform the first N combines, then stop. useful for debugging.\n");
+		log("\n");
+	}
+	void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
+	{
+		log_header(design, "Executing OPT_LUT pass (optimize LUTs).\n");
+
+		dict<IdString, dict<int, IdString>> dlogic;
+		int limit = -1;
+
+		size_t argidx;
+		for (argidx = 1; argidx < args.size(); argidx++)
+		{
+			if (args[argidx] == "-dlogic" && argidx+1 < args.size())
+			{
+				std::vector<std::string> tokens;
+				split(tokens, args[++argidx], ':');
+				if (tokens.size() < 2)
+					log_cmd_error("The -dlogic option requires at least one connection.\n");
+				IdString type = "\\" + tokens[0];
+				for (auto it = tokens.begin() + 1; it != tokens.end(); ++it) {
+					std::vector<std::string> conn_tokens;
+					split(conn_tokens, *it, '=');
+					if (conn_tokens.size() != 2)
+						log_cmd_error("Invalid format of -dlogic signal mapping.\n");
+					IdString logic_port = "\\" + conn_tokens[0];
+					int lut_input = atoi(conn_tokens[1].c_str());
+					dlogic[type][lut_input] = logic_port;
+				}
+				continue;
+			}
+			if (args[argidx] == "-limit" && argidx + 1 < args.size())
+			{
+				limit = atoi(args[++argidx].c_str());
+				continue;
+			}
+			break;
+		}
+		extra_args(args, argidx, design);
+
+		int eliminated_count = 0, combined_count = 0;
+		for (auto module : design->selected_modules())
+		{
+			OptLutWorker worker(dlogic, module, limit - eliminated_count - combined_count);
+			eliminated_count += worker.eliminated_count;
+			combined_count   += worker.combined_count;
+		}
+		if (eliminated_count)
+			design->scratchpad_set_bool("opt.did_something", true);
+		if (combined_count)
+			design->scratchpad_set_bool("opt.did_something", true);
+		log("\n");
+		log("Eliminated %d LUTs.\n", eliminated_count);
+		log("Combined %d LUTs.\n", combined_count);
+	}
+} OptLutPass;
+
+PRIVATE_NAMESPACE_END
diff --git a/passes/opt/opt_muxtree.cc b/passes/opt/opt_muxtree.cc
index 87c7ce9b..375697dc 100644
--- a/passes/opt/opt_muxtree.cc
+++ b/passes/opt/opt_muxtree.cc
@@ -36,6 +36,7 @@ struct OptMuxtreeWorker
 	RTLIL::Module *module;
 	SigMap assign_map;
 	int removed_count;
+	int glob_abort_cnt = 100000;
 
 	struct bitinfo_t {
 		bool seen_non_mux;
@@ -293,6 +294,9 @@ struct OptMuxtreeWorker
 
 	void eval_mux_port(knowledge_t &knowledge, int mux_idx, int port_idx, bool do_replace_known, bool do_enable_ports, int abort_count)
 	{
+		if (glob_abort_cnt == 0)
+			return;
+
 		muxinfo_t &muxinfo = mux2info[mux_idx];
 
 		if (do_enable_ports)
@@ -315,7 +319,7 @@ struct OptMuxtreeWorker
 			knowledge.visited_muxes[m] = true;
 			parent_muxes.push_back(m);
 		}
-		for (int m : parent_muxes)
+		for (int m : parent_muxes) {
 			if (root_enable_muxes.at(m))
 				continue;
 			else if (root_muxes.at(m)) {
@@ -327,6 +331,9 @@ struct OptMuxtreeWorker
 					eval_mux(knowledge, m, false, do_enable_ports, abort_count - 1);
 			} else
 				eval_mux(knowledge, m, do_replace_known, do_enable_ports, abort_count);
+			if (glob_abort_cnt == 0)
+				return;
+		}
 		for (int m : parent_muxes)
 			knowledge.visited_muxes[m] = false;
 
@@ -390,6 +397,12 @@ struct OptMuxtreeWorker
 
 	void eval_mux(knowledge_t &knowledge, int mux_idx, bool do_replace_known, bool do_enable_ports, int abort_count)
 	{
+		if (glob_abort_cnt == 0) {
+			log("  Giving up (too many iterations)\n");
+			return;
+		}
+		glob_abort_cnt--;
+
 		muxinfo_t &muxinfo = mux2info[mux_idx];
 
 		// set input ports to constants if we find known active or inactive signals
@@ -433,6 +446,9 @@ struct OptMuxtreeWorker
 				if (knowledge.known_inactive.at(portinfo.ctrl_sig))
 					continue;
 			eval_mux_port(knowledge, mux_idx, port_idx, do_replace_known, do_enable_ports, abort_count);
+
+			if (glob_abort_cnt == 0)
+				return;
 		}
 	}
 
diff --git a/passes/opt/opt_rmdff.cc b/passes/opt/opt_rmdff.cc
index 5880254c..e8570f0e 100644
--- a/passes/opt/opt_rmdff.cc
+++ b/passes/opt/opt_rmdff.cc
@@ -174,8 +174,6 @@ bool handle_dffsr(RTLIL::Module *mod, RTLIL::Cell *cell)
 			cell->unsetParam("\\CLR_POLARITY");
 			cell->unsetPort("\\SET");
 			cell->unsetPort("\\CLR");
-
-			return true;
 		}
 		else
 		{
@@ -186,11 +184,12 @@ bool handle_dffsr(RTLIL::Module *mod, RTLIL::Cell *cell)
 			cell->unsetParam("\\CLR_POLARITY");
 			cell->unsetPort("\\SET");
 			cell->unsetPort("\\CLR");
-
-			return true;
 		}
+
+		return true;
 	}
-	else
+
+	if (!hasreset)
 	{
 		IdString new_type;
 
@@ -207,8 +206,10 @@ bool handle_dffsr(RTLIL::Module *mod, RTLIL::Cell *cell)
 		cell->unsetPort("\\S");
 		cell->unsetPort("\\R");
 
-		return did_something;
+		return true;
 	}
+
+	return did_something;
 }
 
 bool handle_dlatch(RTLIL::Module *mod, RTLIL::Cell *dlatch)
diff --git a/passes/opt/share.cc b/passes/opt/share.cc
index b8028082..c85c2742 100644
--- a/passes/opt/share.cc
+++ b/passes/opt/share.cc
@@ -710,8 +710,12 @@ struct ShareWorker
 			RTLIL::Cell *supercell = module->addCell(NEW_ID, c1);
 			RTLIL::SigSpec addr1 = c1->getPort("\\ADDR");
 			RTLIL::SigSpec addr2 = c2->getPort("\\ADDR");
-			if (addr1 != addr2)
-				supercell->setPort("\\ADDR", module->Mux(NEW_ID, addr2, addr1, act));
+			if (GetSize(addr1) < GetSize(addr2))
+				addr1.extend_u0(GetSize(addr2));
+			else
+				addr2.extend_u0(GetSize(addr1));
+			supercell->setPort("\\ADDR", addr1 != addr2 ? module->Mux(NEW_ID, addr2, addr1, act) : addr1);
+			supercell->parameters["\\ABITS"] = RTLIL::Const(GetSize(addr1));
 			supercell_aux.insert(module->addPos(NEW_ID, supercell->getPort("\\DATA"), c2->getPort("\\DATA")));
 			supercell_aux.insert(supercell);
 			return supercell;
diff --git a/passes/opt/wreduce.cc b/passes/opt/wreduce.cc
index 0164f58d..52245ce3 100644
--- a/passes/opt/wreduce.cc
+++ b/passes/opt/wreduce.cc
@@ -38,7 +38,8 @@ struct WreduceConfig
 			"$shl", "$shr", "$sshl", "$sshr", "$shift", "$shiftx",
 			"$lt", "$le", "$eq", "$ne", "$eqx", "$nex", "$ge", "$gt",
 			"$add", "$sub", "$mul", // "$div", "$mod", "$pow",
-			"$mux", "$pmux"
+			"$mux", "$pmux",
+			"$dff", "$adff"
 		});
 	}
 };
@@ -52,6 +53,8 @@ struct WreduceWorker
 	std::set<Cell*, IdString::compare_ptr_by_name<Cell>> work_queue_cells;
 	std::set<SigBit> work_queue_bits;
 	pool<SigBit> keep_bits;
+	dict<SigBit, State> init_bits;
+	pool<SigBit> remove_init_bits;
 
 	WreduceWorker(WreduceConfig *config, Module *module) :
 			config(config), module(module), mi(module) { }
@@ -134,6 +137,91 @@ struct WreduceWorker
 		module->connect(sig_y.extract(n_kept, n_removed), sig_removed);
 	}
 
+	void run_cell_dff(Cell *cell)
+	{
+		// Reduce size of FF if inputs are just sign/zero extended or output bit is not used
+
+		SigSpec sig_d = mi.sigmap(cell->getPort("\\D"));
+		SigSpec sig_q = mi.sigmap(cell->getPort("\\Q"));
+		Const initval;
+
+		int width_before = GetSize(sig_q);
+
+		if (width_before == 0)
+			return;
+
+		bool zero_ext = sig_d[GetSize(sig_d)-1] == State::S0;
+		bool sign_ext = !zero_ext;
+
+		for (int i = 0; i < GetSize(sig_q); i++) {
+			SigBit bit = sig_q[i];
+			if (init_bits.count(bit))
+				initval.bits.push_back(init_bits.at(bit));
+			else
+				initval.bits.push_back(State::Sx);
+		}
+
+		for (int i = GetSize(sig_q)-1; i >= 0; i--)
+		{
+			if (zero_ext && sig_d[i] == State::S0 && (initval[i] == State::S0 || initval[i] == State::Sx)) {
+				module->connect(sig_q[i], State::S0);
+				remove_init_bits.insert(sig_q[i]);
+				sig_d.remove(i);
+				sig_q.remove(i);
+				continue;
+			}
+
+			if (sign_ext && i > 0 && sig_d[i] == sig_d[i-1] && initval[i] == initval[i-1]) {
+				module->connect(sig_q[i], sig_q[i-1]);
+				remove_init_bits.insert(sig_q[i]);
+				sig_d.remove(i);
+				sig_q.remove(i);
+				continue;
+			}
+
+			auto info = mi.query(sig_q[i]);
+			if (!info->is_output && GetSize(info->ports) == 1 && !keep_bits.count(mi.sigmap(sig_q[i]))) {
+				remove_init_bits.insert(sig_q[i]);
+				sig_d.remove(i);
+				sig_q.remove(i);
+				zero_ext = false;
+				sign_ext = false;
+				continue;
+			}
+
+			break;
+		}
+
+		if (width_before == GetSize(sig_q))
+			return;
+
+		if (GetSize(sig_q) == 0) {
+			log("Removed cell %s.%s (%s).\n", log_id(module), log_id(cell), log_id(cell->type));
+			module->remove(cell);
+			return;
+		}
+
+		log("Removed top %d bits (of %d) from FF cell %s.%s (%s).\n", width_before - GetSize(sig_q), width_before,
+				log_id(module), log_id(cell), log_id(cell->type));
+
+		for (auto bit : sig_d)
+			work_queue_bits.insert(bit);
+
+		for (auto bit : sig_q)
+			work_queue_bits.insert(bit);
+
+		// Narrow ARST_VALUE parameter to new size.
+		if (cell->parameters.count("\\ARST_VALUE")) {
+			Const arst_value = cell->getParam("\\ARST_VALUE");
+			arst_value.bits.resize(GetSize(sig_q));
+			cell->setParam("\\ARST_VALUE", arst_value);
+		}
+
+		cell->setPort("\\D", sig_d);
+		cell->setPort("\\Q", sig_q);
+		cell->fixup_parameters();
+	}
+
 	void run_reduce_inport(Cell *cell, char port, int max_port_size, bool &port_signed, bool &did_something)
 	{
 		port_signed = cell->getParam(stringf("\\%c_SIGNED", port)).as_bool();
@@ -176,6 +264,9 @@ struct WreduceWorker
 		if (cell->type.in("$mux", "$pmux"))
 			return run_cell_mux(cell);
 
+		if (cell->type.in("$dff", "$adff"))
+			return run_cell_dff(cell);
+
 		SigSpec sig = mi.sigmap(cell->getPort("\\Y"));
 
 		if (sig.has_const())
@@ -235,8 +326,11 @@ struct WreduceWorker
 		} else {
 			while (GetSize(sig) > 0)
 			{
-				auto info = mi.query(sig[GetSize(sig)-1]);
+				auto bit = sig[GetSize(sig)-1];
+				if (keep_bits.count(bit))
+					break;
 
+				auto info = mi.query(bit);
 				if (info->is_output || GetSize(info->ports) > 1)
 					break;
 
@@ -297,10 +391,21 @@ struct WreduceWorker
 
 	void run()
 	{
-		for (auto w : module->wires())
+		// create a copy as mi.sigmap will be updated as we process the module
+		SigMap init_attr_sigmap = mi.sigmap;
+
+		for (auto w : module->wires()) {
 			if (w->get_bool_attribute("\\keep"))
 				for (auto bit : mi.sigmap(w))
 					keep_bits.insert(bit);
+			if (w->attributes.count("\\init")) {
+				Const initval = w->attributes.at("\\init");
+				SigSpec initsig = init_attr_sigmap(w);
+				int width = std::min(GetSize(initval), GetSize(initsig));
+				for (int i = 0; i < width; i++)
+					init_bits[initsig[i]] = initval[i];
+			}
+		}
 
 		for (auto c : module->selected_cells())
 			work_queue_cells.insert(c);
@@ -348,6 +453,24 @@ struct WreduceWorker
 			module->connect(nw, SigSpec(w).extract(0, GetSize(nw)));
 			module->swap_names(w, nw);
 		}
+
+		if (!remove_init_bits.empty()) {
+			for (auto w : module->wires()) {
+				if (w->attributes.count("\\init")) {
+					Const initval = w->attributes.at("\\init");
+					Const new_initval(State::Sx, GetSize(w));
+					SigSpec initsig = init_attr_sigmap(w);
+					int width = std::min(GetSize(initval), GetSize(initsig));
+					for (int i = 0; i < width; i++) {
+						log_dump(initsig[i], remove_init_bits.count(initsig[i]));
+						if (!remove_init_bits.count(initsig[i]))
+							new_initval[i] = initval[i];
+					}
+					w->attributes.at("\\init") = new_initval;
+					log_dump(w->name, initval, new_initval);
+				}
+			}
+		}
 	}
 };