initial import

11 files changed, 1957 insertions, 0 deletions

diff --git a/passes/fsm/Makefile.inc b/passes/fsm/Makefile.inc
new file mode 100644
index 000000000..38623e49e
--- /dev/null
+++ b/passes/fsm/Makefile.inc
@@ -0,0 +1,11 @@
+
+OBJS += passes/fsm/fsm.o
+OBJS += passes/fsm/fsm_detect.o
+OBJS += passes/fsm/fsm_extract.o
+OBJS += passes/fsm/fsm_opt.o
+OBJS += passes/fsm/fsm_expand.o
+OBJS += passes/fsm/fsm_recode.o
+OBJS += passes/fsm/fsm_info.o
+OBJS += passes/fsm/fsm_export.o
+OBJS += passes/fsm/fsm_map.o
+
diff --git a/passes/fsm/fsm.cc b/passes/fsm/fsm.cc
new file mode 100644
index 000000000..61322fbd3
--- /dev/null
+++ b/passes/fsm/fsm.cc
@@ -0,0 +1,91 @@
+/*
+ *  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/register.h"
+#include "kernel/log.h"
+#include <stdlib.h>
+#include <stdio.h>
+
+struct FsmPass : public Pass {
+	FsmPass() : Pass("fsm") { }
+	virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
+	{
+		bool flag_nomap = false;
+		bool flag_norecode = false;
+		bool flag_expand = false;
+		bool flag_export = false;
+		std::string fm_set_fsm_file_opt;
+
+		log_header("Executing FSM pass (extract and optimize FSM).\n");
+		log_push();
+
+		size_t argidx;
+		for (argidx = 1; argidx < args.size(); argidx++) {
+			std::string arg = args[argidx];
+			if (arg == "-fm_set_fsm_file" && argidx+1 < args.size() && fm_set_fsm_file_opt.empty()) {
+				fm_set_fsm_file_opt = " -fm_set_fsm_file " + args[++argidx];
+				continue;
+			}
+			if (arg == "-norecode") {
+				flag_norecode = true;
+				continue;
+			}
+			if (arg == "-nomap") {
+				flag_nomap = true;
+				continue;
+			}
+			if (arg == "-expand") {
+				flag_expand = true;
+				continue;
+			}
+			if (arg == "-export") {
+				flag_export = true;
+				continue;
+			}
+			break;
+		}
+		extra_args(args, argidx, design);
+
+		Pass::call(design, "fsm_detect");
+		Pass::call(design, "fsm_extract");
+
+		Pass::call(design, "fsm_opt");
+		Pass::call(design, "opt_rmunused");
+		Pass::call(design, "fsm_opt");
+
+		if (flag_expand) {
+			Pass::call(design, "fsm_expand");
+			Pass::call(design, "opt_rmunused");
+			Pass::call(design, "fsm_opt");
+		}
+
+		if (!flag_norecode)
+			Pass::call(design, "fsm_recode" + fm_set_fsm_file_opt);
+		Pass::call(design, "fsm_info");
+
+		if (!flag_nomap)
+			Pass::call(design, "fsm_map");
+
+		if (flag_export)
+			Pass::call(design, "fsm_export");
+
+		log_pop();
+	}
+} FsmPass;
+ 
diff --git a/passes/fsm/fsm_detect.cc b/passes/fsm/fsm_detect.cc
new file mode 100644
index 000000000..067ed171f
--- /dev/null
+++ b/passes/fsm/fsm_detect.cc
@@ -0,0 +1,160 @@
+/*
+ *  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/log.h"
+#include "kernel/register.h"
+#include "kernel/sigtools.h"
+#include "kernel/consteval.h"
+#include "kernel/celltypes.h"
+#include "fsmdata.h"
+
+static RTLIL::Module *module;
+static SigMap assign_map;
+typedef std::pair<RTLIL::Cell*,std::string> sig2driver_entry_t;
+static SigSet<sig2driver_entry_t> sig2driver, sig2user;
+static std::set<RTLIL::Cell*> muxtree_cells;
+static SigPool sig_at_port;
+
+static bool check_state_mux_tree(RTLIL::SigSpec old_sig, RTLIL::SigSpec sig)
+{
+	if (sig_at_port.check_any(assign_map(sig)))
+		return false;
+
+	if (sig.is_fully_const() || old_sig == sig)
+		return true;
+
+	std::set<sig2driver_entry_t> cellport_list;
+	sig2driver.find(sig, cellport_list);
+	for (auto &cellport : cellport_list) {
+		if ((cellport.first->type != "$mux" && cellport.first->type != "$pmux" && cellport.first->type != "$safe_pmux") || cellport.second != "\\Y")
+			return false;
+		RTLIL::SigSpec sig_a = assign_map(cellport.first->connections["\\A"]);
+		RTLIL::SigSpec sig_b = assign_map(cellport.first->connections["\\B"]);
+		if (!check_state_mux_tree(old_sig, sig_a))
+			return false;
+		for (int i = 0; i < sig_b.width; i += sig_a.width)
+			if (!check_state_mux_tree(old_sig, sig_b.extract(i, sig_a.width)))
+				return false;
+		muxtree_cells.insert(cellport.first);
+	}
+
+	return true;
+}
+
+static bool check_state_users(RTLIL::SigSpec sig)
+{
+	if (sig_at_port.check_any(assign_map(sig)))
+		return false;
+
+	std::set<sig2driver_entry_t> cellport_list;
+	sig2user.find(sig, cellport_list);
+	for (auto &cellport : cellport_list) {
+		RTLIL::Cell *cell = cellport.first;
+		if (muxtree_cells.count(cell) > 0)
+			continue;
+		if (cellport.second != "\\A" && cellport.second != "\\B")
+			return false;
+		if (cell->connections.count("\\A") == 0 || cell->connections.count("\\B") == 0 || cell->connections.count("\\Y") == 0)
+			return false;
+		for (auto &port_it : cell->connections)
+			if (port_it.first != "\\A" && port_it.first != "\\B" && port_it.first != "\\Y")
+				return false;
+		if (assign_map(cell->connections["\\A"]) == sig && cell->connections["\\B"].is_fully_const())
+			continue;
+		if (assign_map(cell->connections["\\B"]) == sig && cell->connections["\\A"].is_fully_const())
+			continue;
+		return false;
+	}
+
+	return true;
+}
+
+static void detect_fsm(RTLIL::Wire *wire)
+{
+	if (wire->attributes.count("\\fsm_encoding") > 0 || wire->width <= 1)
+		return;
+	if (sig_at_port.check_any(assign_map(RTLIL::SigSpec(wire))))
+		return;
+
+	std::set<sig2driver_entry_t> cellport_list;
+	sig2driver.find(RTLIL::SigSpec(wire), cellport_list);
+	for (auto &cellport : cellport_list) {
+		if ((cellport.first->type != "$dff" && cellport.first->type != "$adff") || cellport.second != "\\Q")
+			continue;
+		muxtree_cells.clear();
+		RTLIL::SigSpec sig_q = assign_map(cellport.first->connections["\\Q"]);
+		RTLIL::SigSpec sig_d = assign_map(cellport.first->connections["\\D"]);
+		if (sig_q == RTLIL::SigSpec(wire) && check_state_mux_tree(sig_q, sig_d) && check_state_users(sig_q)) {
+			log("Found FSM state register %s in module %s.\n", wire->name.c_str(), module->name.c_str());
+			wire->attributes["\\fsm_encoding"] = RTLIL::Const("auto");
+			return;
+		}
+	}
+}
+
+struct FsmDetectPass : public Pass {
+	FsmDetectPass() : Pass("fsm_detect") { }
+	virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
+	{
+		log_header("Executing FSM_DETECT pass (finding FSMs in design).\n");
+		extra_args(args, 1, design);
+
+		CellTypes ct;
+		ct.setup_internals();
+		ct.setup_internals_mem();
+		ct.setup_stdcells();
+		ct.setup_stdcells_mem();
+
+		for (auto &mod_it : design->modules)
+		{
+			module = mod_it.second;
+			assign_map.set(module);
+
+			sig2driver.clear();
+			sig2user.clear();
+			sig_at_port.clear();
+			for (auto &cell_it : module->cells)
+				for (auto &conn_it : cell_it.second->connections) {
+					if (ct.cell_output(cell_it.second->type, conn_it.first)) {
+						RTLIL::SigSpec sig = conn_it.second;
+						assign_map.apply(sig);
+						sig2driver.insert(sig, sig2driver_entry_t(cell_it.second, conn_it.first));
+					}
+					if (!ct.cell_known(cell_it.second->type) || ct.cell_input(cell_it.second->type, conn_it.first)) {
+						RTLIL::SigSpec sig = conn_it.second;
+						assign_map.apply(sig);
+						sig2user.insert(sig, sig2driver_entry_t(cell_it.second, conn_it.first));
+					}
+				}
+
+			for (auto &wire_it : module->wires)
+				if (wire_it.second->port_id != 0)
+					sig_at_port.add(assign_map(RTLIL::SigSpec(wire_it.second)));
+
+			for (auto &wire_it : module->wires)
+				detect_fsm(wire_it.second);
+		}
+
+		assign_map.clear();
+		sig2driver.clear();
+		sig2user.clear();
+		muxtree_cells.clear();
+	}
+} FsmDetectPass;
+ 
diff --git a/passes/fsm/fsm_expand.cc b/passes/fsm/fsm_expand.cc
new file mode 100644
index 000000000..0d5bc7695
--- /dev/null
+++ b/passes/fsm/fsm_expand.cc
@@ -0,0 +1,255 @@
+/*
+ *  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/log.h"
+#include "kernel/register.h"
+#include "kernel/sigtools.h"
+#include "kernel/consteval.h"
+#include "kernel/celltypes.h"
+#include "fsmdata.h"
+#include <string.h>
+
+struct FsmExpand
+{
+	RTLIL::Module *module;
+	RTLIL::Cell *fsm_cell;
+	SigMap assign_map;
+	SigSet<RTLIL::Cell*> sig2driver, sig2user;
+	CellTypes ct;
+
+	std::set<RTLIL::Cell*> merged_set;
+	std::set<RTLIL::Cell*> current_set;
+	std::set<RTLIL::Cell*> no_candidate_set;
+
+	bool already_optimized;
+	int limit_transitions;
+
+	bool is_cell_merge_candidate(RTLIL::Cell *cell)
+	{
+		RTLIL::SigSpec new_signals;
+		if (cell->connections.count("\\A") > 0)
+			new_signals.append(assign_map(cell->connections["\\A"]));
+		if (cell->connections.count("\\B") > 0)
+			new_signals.append(assign_map(cell->connections["\\B"]));
+		if (cell->connections.count("\\S") > 0)
+			new_signals.append(assign_map(cell->connections["\\S"]));
+
+		new_signals.sort_and_unify();
+		new_signals.remove_const();
+
+		if (new_signals.width > 4)
+			return false;
+
+		new_signals.remove(assign_map(fsm_cell->connections["\\CTRL_IN"]));
+		new_signals.remove(assign_map(fsm_cell->connections["\\CTRL_OUT"]));
+
+		if (cell->connections.count("\\Y") > 0) {
+			new_signals.append(assign_map(cell->connections["\\Y"]));
+			new_signals.sort_and_unify();
+			new_signals.remove_const();
+			new_signals.remove(assign_map(fsm_cell->connections["\\CTRL_IN"]));
+			new_signals.remove(assign_map(fsm_cell->connections["\\CTRL_OUT"]));
+		}
+
+		if (new_signals.width > 2)
+			return false;
+
+		return true;
+	}
+
+	void create_current_set()
+	{
+		std::vector<RTLIL::Cell*> cell_list;
+
+		for (auto c : sig2driver.find(assign_map(fsm_cell->connections["\\CTRL_IN"])))
+			cell_list.push_back(c);
+
+		for (auto c : sig2user.find(assign_map(fsm_cell->connections["\\CTRL_OUT"])))
+			cell_list.push_back(c);
+
+		current_set.clear();
+		for (auto c : cell_list)
+		{
+			if (merged_set.count(c) > 0 || current_set.count(c) > 0 || no_candidate_set.count(c) > 0)
+				continue;
+			for (auto &p : c->connections) {
+				if (p.first != "\\A" && p.first != "\\B" && p.first != "\\S" && p.first != "\\Y")
+					goto next_cell;
+			}
+			if (!is_cell_merge_candidate(c)) {
+				no_candidate_set.insert(c);
+				continue;
+			}
+			current_set.insert(c);
+		next_cell:;
+		}
+	}
+
+	void optimze_as_needed()
+	{
+		if (already_optimized)
+			return;
+
+		int trans_num = fsm_cell->parameters["\\TRANS_NUM"].as_int();
+		if (trans_num > limit_transitions)
+		{
+			log("  grown transition table to %d entries -> optimize.\n", trans_num);
+			FsmData::optimize_fsm(fsm_cell, module);
+			already_optimized = true;
+
+			trans_num = fsm_cell->parameters["\\TRANS_NUM"].as_int();
+			log("  transition table size after optimizaton: %d\n", trans_num);
+			limit_transitions = 16 * trans_num;
+		}
+	}
+
+	void merge_cell_into_fsm(RTLIL::Cell *cell)
+	{
+		optimze_as_needed();
+
+		log("  merging %s cell %s.\n", cell->type.c_str(), cell->name.c_str());
+		merged_set.insert(cell);
+		already_optimized = false;
+
+		RTLIL::SigSpec input_sig, output_sig;
+
+		for (auto &p : cell->connections)
+			if (ct.cell_output(cell->type, p.first))
+				output_sig.append(assign_map(p.second));
+			else
+				input_sig.append(assign_map(p.second));
+		input_sig.sort_and_unify();
+		input_sig.remove_const();
+
+		assert(input_sig.width <= 4);
+		std::vector<RTLIL::Const> truth_tab;
+
+		for (int i = 0; i < (1 << input_sig.width); i++) {
+			RTLIL::Const in_val(i, input_sig.width);
+			RTLIL::SigSpec A, B, S;
+			if (cell->connections.count("\\A") > 0)
+				A = assign_map(cell->connections["\\A"]);
+			if (cell->connections.count("\\B") > 0)
+				B = assign_map(cell->connections["\\B"]);
+			if (cell->connections.count("\\S") > 0)
+				S = assign_map(cell->connections["\\S"]);
+			A.replace(input_sig, RTLIL::SigSpec(in_val));
+			B.replace(input_sig, RTLIL::SigSpec(in_val));
+			S.replace(input_sig, RTLIL::SigSpec(in_val));
+			assert(A.is_fully_const());
+			assert(B.is_fully_const());
+			assert(S.is_fully_const());
+			truth_tab.push_back(ct.eval(cell, A.as_const(), B.as_const(), S.as_const()));
+		}
+
+		FsmData fsm_data;
+		fsm_data.copy_from_cell(fsm_cell);
+
+		fsm_data.num_inputs += input_sig.width;
+		fsm_cell->connections["\\CTRL_IN"].append(input_sig);
+
+		fsm_data.num_outputs += output_sig.width;
+		fsm_cell->connections["\\CTRL_OUT"].append(output_sig);
+
+		std::vector<FsmData::transition_t> new_transition_table;
+		for (auto &tr : fsm_data.transition_table) {
+			for (int i = 0; i < (1 << input_sig.width); i++) {
+				FsmData::transition_t new_tr = tr;
+				RTLIL::Const in_val(i, input_sig.width);
+				RTLIL::Const out_val = truth_tab[i];
+				RTLIL::SigSpec ctrl_in = new_tr.ctrl_in;
+				RTLIL::SigSpec ctrl_out = new_tr.ctrl_out;
+				ctrl_in.append(in_val);
+				ctrl_out.append(out_val);
+				new_tr.ctrl_in = ctrl_in.as_const();
+				new_tr.ctrl_out = ctrl_out.as_const();
+				new_transition_table.push_back(new_tr);
+			}
+		}
+		fsm_data.transition_table.swap(new_transition_table);
+		new_transition_table.clear();
+
+		fsm_data.copy_to_cell(fsm_cell);
+	}
+
+	FsmExpand(RTLIL::Cell *cell, RTLIL::Module *mod)
+	{
+		module = mod;
+		fsm_cell = cell;
+
+		assign_map.set(module);
+		ct.setup_internals();
+
+		for (auto &cell_it : module->cells) {
+			RTLIL::Cell *c = cell_it.second;
+			if (ct.cell_known(c->type))
+				for (auto &p : c->connections) {
+					if (ct.cell_output(c->type, p.first))
+						sig2driver.insert(assign_map(p.second), c);
+					else
+						sig2user.insert(assign_map(p.second), c);
+				}
+		}
+	}
+
+	void execute()
+	{
+		log("\n");
+		log("Expanding FSM `%s' from module `%s':\n", fsm_cell->name.c_str(), module->name.c_str());
+
+		already_optimized = false;
+		limit_transitions =  16 * fsm_cell->parameters["\\TRANS_NUM"].as_int();
+
+		for (create_current_set(); current_set.size() > 0; create_current_set()) {
+			for (auto c : current_set)
+				merge_cell_into_fsm(c);
+		}
+
+		for (auto c : merged_set) {
+			module->cells.erase(c->name);
+			delete c;
+		}
+
+		if (merged_set.size() > 0 && !already_optimized)
+			FsmData::optimize_fsm(fsm_cell, module);
+
+		log("  merged %zd cells into FSM.\n", merged_set.size());
+	}
+};
+
+struct FsmExpandPass : public Pass {
+	FsmExpandPass() : Pass("fsm_expand") { }
+	virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
+	{
+		log_header("Executing FSM_EXPAND pass (re-assigning FSM state encoding).\n");
+		extra_args(args, 1, design);
+
+		for (auto &mod_it : design->modules) {
+			std::vector<RTLIL::Cell*> fsm_cells;
+			for (auto &cell_it : mod_it.second->cells)
+				if (cell_it.second->type == "$fsm")
+					fsm_cells.push_back(cell_it.second);
+			for (auto c : fsm_cells) {
+				FsmExpand fsm_expand(c, mod_it.second);
+				fsm_expand.execute();
+			}
+		}
+	}
+} FsmExpandPass;
+ 
diff --git a/passes/fsm/fsm_export.cc b/passes/fsm/fsm_export.cc
new file mode 100644
index 000000000..0219f4ebd
--- /dev/null
+++ b/passes/fsm/fsm_export.cc
@@ -0,0 +1,103 @@
+/*
+ *  yosys -- Yosys Open SYnthesis Suite
+ *
+ *  Copyright (C) 2012  Clifford Wolf <clifford@clifford.at>
+ *  Copyright (C) 2012  Martin Schmölzer <martin@schmoelzer.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/log.h"
+#include "kernel/register.h"
+#include "kernel/sigtools.h"
+#include "kernel/consteval.h"
+#include "kernel/celltypes.h"
+#include "fsmdata.h"
+#include <string>
+#include <iostream>
+#include <fstream>
+
+/**
+ * Convert signal into a KISS-compatible textual representation.
+ */
+std::string kiss_convert_signal(const RTLIL::SigSpec &sig) {
+	if (!sig.is_fully_const()) {
+		throw 0;
+	}
+
+	return sig.as_const().as_string();
+}
+
+/**
+ * Exports each Finite State Machine (FSM) in the design to a file in KISS2 format.
+ */
+struct FsmExportPass : public Pass {
+	FsmExportPass() : Pass("fsm_export") {
+	}
+
+	virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
+	{
+		FsmData       fsm_data;
+		std::string   kiss_name;
+		std::ofstream kiss_file;
+		size_t        i;
+		FsmData::transition_t tr;
+
+		log_header("Executing FSM_EXPORT pass (exporting FSMs in KISS2 file format).\n");
+		extra_args(args, 1, design);
+
+		for (auto &mod_it : design->modules)
+			for (auto &cell_it : mod_it.second->cells)
+				if (cell_it.second->type == "$fsm") {
+					kiss_name.assign(mod_it.first.c_str());
+					kiss_name.append("-" + cell_it.second->name + ".kiss2");
+					fsm_data.copy_from_cell(cell_it.second);
+
+					log("\n");
+					log("Exporting FSM `%s' from module `%s' to file `%s'.\n",
+							cell_it.second->name.c_str(),
+							mod_it.first.c_str(),
+							kiss_name.c_str());
+
+					kiss_file.open(kiss_name, std::ios::out | std::ios::trunc);
+
+					if (!kiss_file.is_open()) {
+						log_error("Could not open file \"%s\" with write access.\n", kiss_name.c_str());
+						return;
+					}
+
+					kiss_file << ".start_kiss" << std::endl;
+					kiss_file << ".i " << std::dec << fsm_data.num_inputs << std::endl;
+					kiss_file << ".o " << std::dec << fsm_data.num_outputs << std::endl;
+					kiss_file << ".r s" << std::dec << fsm_data.reset_state << std::endl;
+
+					for (i = 0; i < fsm_data.transition_table.size(); i++) {
+						tr = fsm_data.transition_table[i];
+
+						try {
+							kiss_file << kiss_convert_signal(tr.ctrl_in) << ' ';
+							kiss_file << 's' << tr.state_in << ' ';
+							kiss_file << 's' << tr.state_out << ' ';
+							kiss_file << kiss_convert_signal(tr.ctrl_out) << std::endl;
+						}
+						catch (int) {
+							log_error("exporting an FSM input or output signal failed.\n");
+						}
+					}
+
+					kiss_file << ".end_kiss" << std::endl << ".end" << std::endl;
+					kiss_file.close();
+				}
+	}
+} FsmExportPass;
diff --git a/passes/fsm/fsm_extract.cc b/passes/fsm/fsm_extract.cc
new file mode 100644
index 000000000..bdcb1d45a
--- /dev/null
+++ b/passes/fsm/fsm_extract.cc
@@ -0,0 +1,359 @@
+/*
+ *  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/log.h"
+#include "kernel/register.h"
+#include "kernel/sigtools.h"
+#include "kernel/consteval.h"
+#include "kernel/celltypes.h"
+#include "fsmdata.h"
+
+static RTLIL::Module *module;
+static SigMap assign_map;
+typedef std::pair<RTLIL::Cell*,std::string> sig2driver_entry_t;
+static SigSet<sig2driver_entry_t> sig2driver, sig2trigger;
+
+static bool find_states(RTLIL::SigSpec sig, const RTLIL::SigSpec &dff_out, RTLIL::SigSpec &ctrl, std::map<RTLIL::Const, int> &states, RTLIL::Const *reset_state = NULL)
+{
+	sig.extend(dff_out.width, false);
+
+	if (sig == dff_out)
+		return true;
+
+	assign_map.apply(sig);
+	if (sig.is_fully_const()) {
+		sig.optimize();
+		assert(sig.chunks.size() == 1);
+		if (states.count(sig.chunks[0].data) == 0) {
+			log("  found state code: %s\n", log_signal(sig));
+			states[sig.chunks[0].data] = -1;
+		}
+		return true;
+	}
+
+	std::set<sig2driver_entry_t> cellport_list;
+	sig2driver.find(sig, cellport_list);
+	for (auto &cellport : cellport_list) {
+		if ((cellport.first->type != "$mux" && cellport.first->type != "$pmux" && cellport.first->type != "$safe_pmux") || cellport.second != "\\Y") {
+			log("  unexpected cell type %s (%s) found in state selection tree.\n",
+					cellport.first->type.c_str(), cellport.first->name.c_str());
+			return false;
+		}
+		RTLIL::SigSpec sig_a = assign_map(cellport.first->connections["\\A"]);
+		RTLIL::SigSpec sig_b = assign_map(cellport.first->connections["\\B"]);
+		RTLIL::SigSpec sig_s = assign_map(cellport.first->connections["\\S"]);
+		if (reset_state && RTLIL::SigSpec(*reset_state).is_fully_undef())
+			do {
+				if (sig_a.is_fully_def())
+					*reset_state = sig_a.as_const();
+				else if (sig_b.is_fully_def())
+					*reset_state = sig_b.as_const();
+				else
+					break;
+				log("  found reset state: %s (guessed from mux tree)\n", log_signal(*reset_state));
+			} while (0);
+		if (ctrl.extract(sig_s).width == 0) {
+			log("  found ctrl input: %s\n", log_signal(sig_s));
+			ctrl.append(sig_s);
+		}
+		if (!find_states(sig_a, dff_out, ctrl, states))
+			return false;
+		for (int i = 0; i < sig_b.width/sig_a.width; i++) {
+			if (!find_states(sig_b.extract(i*sig_a.width, sig_a.width), dff_out, ctrl, states))
+				return false;
+		}
+	}
+
+	return true;
+}
+
+static RTLIL::Const sig2const(ConstEval &ce, RTLIL::SigSpec sig, RTLIL::State noconst_state, RTLIL::SigSpec dont_care = RTLIL::SigSpec())
+{
+	if (dont_care.width > 0) {
+		sig.expand();
+		for (auto &chunk : sig.chunks) {
+			assert(chunk.width == 1);
+			if (dont_care.extract(chunk).width > 0)
+				chunk.wire = NULL, chunk.data = RTLIL::Const(noconst_state);
+		}
+		sig.optimize();
+	}
+
+	ce.assign_map.apply(sig);
+	ce.values_map.apply(sig);
+
+	sig.expand();
+	for (auto &chunk : sig.chunks) {
+		assert(chunk.width == 1);
+		if (chunk.wire != NULL)
+			chunk.wire = NULL, chunk.data = RTLIL::Const(noconst_state);
+	}
+	sig.optimize();
+
+	if (sig.width == 0)
+		return RTLIL::Const();
+	assert(sig.chunks.size() == 1 && sig.chunks[0].wire == NULL);
+	return sig.chunks[0].data;
+}
+
+static void find_transitions(ConstEval &ce, ConstEval &ce_nostop, FsmData &fsm_data, std::map<RTLIL::Const, int> &states, int state_in, RTLIL::SigSpec ctrl_in, RTLIL::SigSpec ctrl_out, RTLIL::SigSpec dff_in, RTLIL::SigSpec dont_care)
+{
+	RTLIL::SigSpec undef, constval;
+
+	if (ce.eval(ctrl_out, undef) && ce.eval(dff_in, undef)) {
+		assert(ctrl_out.is_fully_const() && dff_in.is_fully_const());
+		FsmData::transition_t tr;
+		tr.state_in = state_in;
+		tr.state_out = states[ce.values_map(ce.assign_map(dff_in)).as_const()];
+		tr.ctrl_in = sig2const(ce, ctrl_in, RTLIL::State::Sa, dont_care);
+		tr.ctrl_out = sig2const(ce, ctrl_out, RTLIL::State::Sx);
+		RTLIL::Const log_state_in = RTLIL::Const(RTLIL::State::Sx, fsm_data.state_bits);
+		if (state_in >= 0)
+			log_state_in = fsm_data.state_table[tr.state_in];
+		if (dff_in.is_fully_def()) {
+			fsm_data.transition_table.push_back(tr);
+			log("  transition: %10s %s -> %10s %s\n",
+					log_signal(log_state_in), log_signal(tr.ctrl_in),
+					log_signal(fsm_data.state_table[tr.state_out]), log_signal(tr.ctrl_out));
+		} else {
+			log("  transition: %10s %s -> %10s %s  <ignored undef transistion!>\n",
+					log_signal(log_state_in), log_signal(tr.ctrl_in),
+					log_signal(fsm_data.state_table[tr.state_out]), log_signal(tr.ctrl_out));
+		}
+		return;
+	}
+
+	assert(undef.width > 0);
+	assert(ce.stop_signals.check_all(undef));
+
+	undef = undef.extract(0, 1);
+	constval = undef;
+
+	if (ce_nostop.eval(constval))
+	{
+		ce.push();
+		dont_care.append(undef);
+		ce.set(undef, constval.as_const());
+		find_transitions(ce, ce_nostop, fsm_data, states, state_in, ctrl_in, ctrl_out, dff_in, dont_care);
+		ce.pop();
+	}
+	else
+	{
+		ce.push(), ce_nostop.push();
+		ce.set(undef, RTLIL::Const(0, 1));
+		ce_nostop.set(undef, RTLIL::Const(0, 1));
+		find_transitions(ce, ce_nostop, fsm_data, states, state_in, ctrl_in, ctrl_out, dff_in, dont_care);
+		ce.pop(), ce_nostop.pop();
+
+		ce.push(), ce_nostop.push();
+		ce.set(undef, RTLIL::Const(1, 1));
+		ce_nostop.set(undef, RTLIL::Const(1, 1));
+		find_transitions(ce, ce_nostop, fsm_data, states, state_in, ctrl_in, ctrl_out, dff_in, dont_care);
+		ce.pop(), ce_nostop.pop();
+	}
+}
+
+static void extract_fsm(RTLIL::Wire *wire)
+{
+	log("Extracting FSM `%s' from module `%s'.\n", wire->name.c_str(), module->name.c_str());
+
+	// get input and output signals for state ff 
+
+	RTLIL::SigSpec dff_out = assign_map(RTLIL::SigSpec(wire));
+	RTLIL::SigSpec dff_in(RTLIL::State::Sm, wire->width);
+	RTLIL::Const reset_state(RTLIL::State::Sx, wire->width);
+
+	RTLIL::SigSpec clk = RTLIL::SigSpec(0, 1);
+	RTLIL::SigSpec arst = RTLIL::SigSpec(0, 1);
+	bool clk_polarity = true;
+	bool arst_polarity = true;
+
+	std::set<sig2driver_entry_t> cellport_list;
+	sig2driver.find(dff_out, cellport_list);
+	for (auto &cellport : cellport_list) {
+		if ((cellport.first->type != "$dff" && cellport.first->type != "$adff") || cellport.second != "\\Q")
+			continue;
+		log("  found %s cell for state register: %s\n", cellport.first->type.c_str(), cellport.first->name.c_str());
+		RTLIL::SigSpec sig_q = assign_map(cellport.first->connections["\\Q"]);
+		RTLIL::SigSpec sig_d = assign_map(cellport.first->connections["\\D"]);
+		clk = cellport.first->connections["\\CLK"];
+		clk_polarity = cellport.first->parameters["\\CLK_POLARITY"].as_bool();
+		if (cellport.first->type == "$adff") {
+			arst = cellport.first->connections["\\ARST"];
+			arst_polarity = cellport.first->parameters["\\ARST_POLARITY"].as_bool();
+			reset_state = cellport.first->parameters["\\ARST_VALUE"];
+		}
+		sig_q.replace(dff_out, sig_d, &dff_in);
+		break;
+	}
+
+	log("  root of input selection tree: %s\n", log_signal(dff_in));
+	if (dff_in.has_marked_bits()) {
+		log("  fsm extraction failed: incomplete input selection tree root.\n");
+		return;
+	}
+
+	// find states and control inputs
+
+	RTLIL::SigSpec ctrl_in;
+	std::map<RTLIL::Const, int> states;
+	if (!arst.is_fully_const()) {
+		log("  found reset state: %s (from async reset)\n", log_signal(reset_state));
+		states[reset_state] = -1;
+	}
+	if (!find_states(dff_in, dff_out, ctrl_in, states, &reset_state)) {
+		log("  fsm extraction failed: state selection tree is not closed.\n");
+		return;
+	}
+
+	// find control outputs
+	// (add the state signals to the list of control outputs. if everything goes right, this signals
+	// become unused and can then be removed from the fsm control output)
+
+	RTLIL::SigSpec ctrl_out = dff_in;
+	cellport_list.clear();
+	sig2trigger.find(dff_out, cellport_list);
+	for (auto &cellport : cellport_list) {
+		RTLIL::SigSpec sig_a = assign_map(cellport.first->connections["\\A"]);
+		RTLIL::SigSpec sig_b = assign_map(cellport.first->connections["\\B"]);
+		RTLIL::SigSpec sig_y = assign_map(cellport.first->connections["\\Y"]);
+		if (cellport.second == "\\A" && !sig_b.is_fully_const())
+			continue;
+		if (cellport.second == "\\B" && !sig_a.is_fully_const())
+			continue;
+		log("  found ctrl output: %s\n", log_signal(sig_y));
+		ctrl_out.append(sig_y);
+	}
+	ctrl_in.remove(ctrl_out);
+
+	log("  ctrl inputs: %s\n", log_signal(ctrl_in));
+	log("  ctrl outputs: %s\n", log_signal(ctrl_out));
+
+	// Initialize fsm data struct
+
+	FsmData fsm_data;
+	fsm_data.num_inputs = ctrl_in.width;
+	fsm_data.num_outputs = ctrl_out.width;
+	fsm_data.state_bits = wire->width;
+	fsm_data.reset_state = -1;
+	for (auto &it : states) {
+		it.second = fsm_data.state_table.size();
+		fsm_data.state_table.push_back(it.first);
+	}
+	if (!arst.is_fully_const() || RTLIL::SigSpec(reset_state).is_fully_def())
+		fsm_data.reset_state = states[reset_state];
+
+	// Create transition table
+
+	ConstEval ce(module), ce_nostop(module);
+	ce.stop(ctrl_in);
+	for (int state_idx = 0; state_idx < int(fsm_data.state_table.size()); state_idx++) {
+		ce.push(), ce_nostop.push();
+		ce.set(dff_out, fsm_data.state_table[state_idx]);
+		ce_nostop.set(dff_out, fsm_data.state_table[state_idx]);
+		find_transitions(ce, ce_nostop, fsm_data, states, state_idx, ctrl_in, ctrl_out, dff_in, RTLIL::SigSpec());
+		ce.pop(), ce_nostop.pop();
+	}
+
+	// create fsm cell
+
+	RTLIL::Cell *fsm_cell = new RTLIL::Cell;
+	fsm_cell->name = stringf("$fsm$%s$%d", wire->name.c_str(), RTLIL::autoidx++);
+	fsm_cell->type = "$fsm";
+	fsm_cell->connections["\\CLK"] = clk;
+	fsm_cell->connections["\\ARST"] = arst;
+	fsm_cell->parameters["\\CLK_POLARITY"] = RTLIL::Const(clk_polarity ? 1 : 0, 1);
+	fsm_cell->parameters["\\ARST_POLARITY"] = RTLIL::Const(arst_polarity ? 1 : 0, 1);
+	fsm_cell->connections["\\CTRL_IN"] = ctrl_in;
+	fsm_cell->connections["\\CTRL_OUT"] = ctrl_out;
+	fsm_cell->parameters["\\NAME"] = RTLIL::Const(wire->name);
+	fsm_data.copy_to_cell(fsm_cell);
+	module->cells[fsm_cell->name] = fsm_cell;
+
+	// rename original state wire
+
+	module->wires.erase(wire->name);
+	wire->attributes.erase("\\fsm_encoding");
+	wire->name = stringf("$fsm$oldstate%s", wire->name.c_str());
+	module->wires[wire->name] = wire;
+
+	// unconnect control outputs from old drivers
+
+	cellport_list.clear();
+	sig2driver.find(ctrl_out, cellport_list);
+	for (auto &cellport : cellport_list) {
+		RTLIL::SigSpec port_sig = assign_map(cellport.first->connections[cellport.second]);
+		RTLIL::SigSpec unconn_sig = port_sig.extract(ctrl_out);
+		RTLIL::Wire *unconn_wire = new RTLIL::Wire;
+		unconn_wire->name = stringf("$fsm_unconnect$%s$%d", log_signal(unconn_sig), RTLIL::autoidx++);
+		unconn_wire->width = unconn_sig.width;
+		module->wires[unconn_wire->name] = unconn_wire;
+		port_sig.replace(unconn_sig, RTLIL::SigSpec(unconn_wire), &cellport.first->connections[cellport.second]);
+	}
+}
+
+struct FsmExtractPass : public Pass {
+	FsmExtractPass() : Pass("fsm_extract") { }
+	virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
+	{
+		log_header("Executing FSM_EXTRACT pass (extracting FSM from design).\n");
+		extra_args(args, 1, design);
+
+		CellTypes ct;
+		ct.setup_internals();
+		ct.setup_internals_mem();
+		ct.setup_stdcells();
+		ct.setup_stdcells_mem();
+
+		for (auto &mod_it : design->modules)
+		{
+			module = mod_it.second;
+			assign_map.set(module);
+
+			sig2driver.clear();
+			sig2trigger.clear();
+			for (auto &cell_it : module->cells)
+				for (auto &conn_it : cell_it.second->connections) {
+					if (ct.cell_output(cell_it.second->type, conn_it.first)) {
+						RTLIL::SigSpec sig = conn_it.second;
+						assign_map.apply(sig);
+						sig2driver.insert(sig, sig2driver_entry_t(cell_it.second, conn_it.first));
+					}
+					if (ct.cell_input(cell_it.second->type, conn_it.first) && cell_it.second->connections.count("\\Y") > 0 &&
+							cell_it.second->connections["\\Y"].width == 1 && (conn_it.first == "\\A" || conn_it.first == "\\B")) {
+						RTLIL::SigSpec sig = conn_it.second;
+						assign_map.apply(sig);
+						sig2trigger.insert(sig, sig2driver_entry_t(cell_it.second, conn_it.first));
+					}
+				}
+
+			std::vector<RTLIL::Wire*> wire_list;
+			for (auto &wire_it : module->wires)
+				if (wire_it.second->attributes.count("\\fsm_encoding") > 0 && wire_it.second->attributes["\\fsm_encoding"].str != "none")
+					wire_list.push_back(wire_it.second);
+			for (auto wire : wire_list)
+				extract_fsm(wire);
+		}
+
+		assign_map.clear();
+		sig2driver.clear();
+		sig2trigger.clear();
+	}
+} FsmExtractPass;
+ 
diff --git a/passes/fsm/fsm_info.cc b/passes/fsm/fsm_info.cc
new file mode 100644
index 000000000..83f065760
--- /dev/null
+++ b/passes/fsm/fsm_info.cc
@@ -0,0 +1,46 @@
+/*
+ *  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/log.h"
+#include "kernel/register.h"
+#include "kernel/sigtools.h"
+#include "kernel/consteval.h"
+#include "kernel/celltypes.h"
+#include "fsmdata.h"
+#include <string.h>
+
+struct FsmInfoPass : public Pass {
+	FsmInfoPass() : Pass("fsm_info") { }
+	virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
+	{
+		log_header("Executing FSM_INFO pass (dumping all available information on FSM cells).\n");
+		extra_args(args, 1, design);
+
+		for (auto &mod_it : design->modules)
+		for (auto &cell_it : mod_it.second->cells)
+			if (cell_it.second->type == "$fsm") {
+				log("\n");
+				log("FSM `%s' from module `%s':\n", cell_it.second->name.c_str(), mod_it.first.c_str());
+				FsmData fsm_data;
+				fsm_data.copy_from_cell(cell_it.second);
+				fsm_data.log_info(cell_it.second);
+			}
+	}
+} FsmInfoPass;
+ 
diff --git a/passes/fsm/fsm_map.cc b/passes/fsm/fsm_map.cc
new file mode 100644
index 000000000..4319dc044
--- /dev/null
+++ b/passes/fsm/fsm_map.cc
@@ -0,0 +1,356 @@
+/*
+ *  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/log.h"
+#include "kernel/register.h"
+#include "kernel/sigtools.h"
+#include "kernel/consteval.h"
+#include "kernel/celltypes.h"
+#include "fsmdata.h"
+#include <string.h>
+
+static void implement_pattern_cache(RTLIL::Module *module, std::map<RTLIL::Const, std::set<int>> &pattern_cache, std::set<int> &fullstate_cache, int num_states, RTLIL::Wire *state_onehot, RTLIL::SigSpec &ctrl_in, RTLIL::SigSpec output)
+{
+	RTLIL::SigSpec cases_vector;
+
+	for (int in_state : fullstate_cache)
+		cases_vector.append(RTLIL::SigSpec(state_onehot, 1, in_state));
+
+	for (auto &it : pattern_cache)
+	{
+		RTLIL::Const pattern = it.first;
+		RTLIL::SigSpec eq_sig_a, eq_sig_b, or_sig;
+
+		for (size_t j = 0; j < pattern.bits.size(); j++)
+			if (pattern.bits[j] == RTLIL::State::S0 || pattern.bits[j] == RTLIL::State::S1) {
+				eq_sig_a.append(ctrl_in.extract(j, 1));
+				eq_sig_b.append(RTLIL::SigSpec(pattern.bits[j]));
+			}
+		eq_sig_a.optimize();
+		eq_sig_b.optimize();
+
+		for (int in_state : it.second)
+			if (fullstate_cache.count(in_state) == 0)
+				or_sig.append(RTLIL::SigSpec(state_onehot, 1, in_state));
+		or_sig.optimize();
+
+		if (or_sig.width == 0)
+			continue;
+
+		RTLIL::SigSpec and_sig;
+
+		if (eq_sig_a.width > 0)
+		{
+			RTLIL::Wire *eq_wire = new RTLIL::Wire;
+			eq_wire->name = NEW_ID;
+			module->add(eq_wire);
+
+			RTLIL::Cell *eq_cell = new RTLIL::Cell;
+			eq_cell->name = NEW_ID;
+			eq_cell->type = "$eq";
+			eq_cell->connections["\\A"] = eq_sig_a;
+			eq_cell->connections["\\B"] = eq_sig_b;
+			eq_cell->connections["\\Y"] = RTLIL::SigSpec(eq_wire);
+			eq_cell->parameters["\\A_SIGNED"] = RTLIL::Const(false);
+			eq_cell->parameters["\\B_SIGNED"] = RTLIL::Const(false);
+			eq_cell->parameters["\\A_WIDTH"] = RTLIL::Const(eq_sig_a.width);
+			eq_cell->parameters["\\B_WIDTH"] = RTLIL::Const(eq_sig_b.width);
+			eq_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1);
+			module->add(eq_cell);
+
+			and_sig.append(RTLIL::SigSpec(eq_wire));
+		}
+
+		if (or_sig.width == 1)
+		{
+			and_sig.append(or_sig);
+		}
+		else if (or_sig.width < num_states && int(it.second.size()) < num_states)
+		{
+			RTLIL::Wire *or_wire = new RTLIL::Wire;
+			or_wire->name = NEW_ID;
+			module->add(or_wire);
+
+			RTLIL::Cell *or_cell = new RTLIL::Cell;
+			or_cell->name = NEW_ID;
+			or_cell->type = "$reduce_or";
+			or_cell->connections["\\A"] = or_sig;
+			or_cell->connections["\\Y"] = RTLIL::SigSpec(or_wire);
+			or_cell->parameters["\\A_SIGNED"] = RTLIL::Const(false);
+			or_cell->parameters["\\A_WIDTH"] = RTLIL::Const(or_sig.width);
+			or_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1);
+			module->add(or_cell);
+
+			and_sig.append(RTLIL::SigSpec(or_wire));
+		}
+
+		switch (and_sig.width)
+		{
+		case 2:
+			{
+				RTLIL::Wire *and_wire = new RTLIL::Wire;
+				and_wire->name = NEW_ID;
+				module->add(and_wire);
+
+				RTLIL::Cell *and_cell = new RTLIL::Cell;
+				and_cell->name = NEW_ID;
+				and_cell->type = "$and";
+				and_cell->connections["\\A"] = and_sig.extract(0, 1);
+				and_cell->connections["\\B"] = and_sig.extract(1, 1);
+				and_cell->connections["\\Y"] = RTLIL::SigSpec(and_wire);
+				and_cell->parameters["\\A_SIGNED"] = RTLIL::Const(false);
+				and_cell->parameters["\\B_SIGNED"] = RTLIL::Const(false);
+				and_cell->parameters["\\A_WIDTH"] = RTLIL::Const(1);
+				and_cell->parameters["\\B_WIDTH"] = RTLIL::Const(1);
+				and_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1);
+				module->add(and_cell);
+
+				cases_vector.append(RTLIL::SigSpec(and_wire));
+				break;
+			}
+		case 1:
+			cases_vector.append(and_sig);
+			break;
+		case 0:
+			cases_vector.append(RTLIL::SigSpec(1, 1));
+			break;
+		default:
+			assert(!"This should never happen!");
+		}
+	}
+
+	if (cases_vector.width > 1) {
+		RTLIL::Cell *or_cell = new RTLIL::Cell;
+		or_cell->name = NEW_ID;
+		or_cell->type = "$reduce_or";
+		or_cell->connections["\\A"] = cases_vector;
+		or_cell->connections["\\Y"] = output;
+		or_cell->parameters["\\A_SIGNED"] = RTLIL::Const(false);
+		or_cell->parameters["\\A_WIDTH"] = RTLIL::Const(cases_vector.width);
+		or_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1);
+		module->add(or_cell);
+	} else if (cases_vector.width == 1) {
+		module->connections.push_back(RTLIL::SigSig(output, cases_vector));
+	} else {
+		module->connections.push_back(RTLIL::SigSig(output, RTLIL::SigSpec(0, 1)));
+	}
+}
+
+static void map_fsm(RTLIL::Cell *fsm_cell, RTLIL::Module *module)
+{
+	log("Mapping FSM `%s' from module `%s'.\n", fsm_cell->name.c_str(), module->name.c_str());
+
+	FsmData fsm_data;
+	fsm_data.copy_from_cell(fsm_cell);
+
+	RTLIL::SigSpec ctrl_in = fsm_cell->connections["\\CTRL_IN"];
+	RTLIL::SigSpec ctrl_out = fsm_cell->connections["\\CTRL_OUT"];
+
+	// create state register
+
+	RTLIL::Wire *state_wire = new RTLIL::Wire;
+	state_wire->name = fsm_cell->parameters["\\NAME"].str;
+	while (module->count_id(state_wire->name) > 0)
+		state_wire->name += "_";
+	state_wire->width = fsm_data.state_bits;
+	module->add(state_wire);
+
+	RTLIL::Wire *next_state_wire = new RTLIL::Wire;
+	next_state_wire->name = NEW_ID;
+	next_state_wire->width = fsm_data.state_bits;
+	module->add(next_state_wire);
+
+	RTLIL::Cell *state_dff = new RTLIL::Cell;
+	state_dff->name = NEW_ID;
+	if (fsm_cell->connections["\\ARST"].is_fully_const()) {
+		state_dff->type = "$dff";
+	} else {
+		state_dff->type = "$adff";
+		state_dff->parameters["\\ARST_POLARITY"] = fsm_cell->parameters["\\ARST_POLARITY"];
+		state_dff->parameters["\\ARST_VALUE"] = fsm_data.state_table[fsm_data.reset_state];
+		state_dff->connections["\\ARST"] = fsm_cell->connections["\\ARST"];
+	}
+	state_dff->parameters["\\WIDTH"] = RTLIL::Const(fsm_data.state_bits);
+	state_dff->parameters["\\CLK_POLARITY"] = fsm_cell->parameters["\\CLK_POLARITY"];
+	state_dff->connections["\\CLK"] = fsm_cell->connections["\\CLK"];
+	state_dff->connections["\\D"] = RTLIL::SigSpec(next_state_wire);
+	state_dff->connections["\\Q"] = RTLIL::SigSpec(state_wire);
+	module->add(state_dff);
+
+	// decode state register
+
+	bool encoding_is_onehot = true;
+
+	RTLIL::Wire *state_onehot = new RTLIL::Wire;
+	state_onehot->name = NEW_ID;
+	state_onehot->width = fsm_data.state_table.size();
+	module->add(state_onehot);
+
+	for (size_t i = 0; i < fsm_data.state_table.size(); i++)
+	{
+		RTLIL::Const state = fsm_data.state_table[i];
+		RTLIL::SigSpec sig_a, sig_b;
+
+		for (size_t j = 0; j < state.bits.size(); j++)
+			if (state.bits[j] == RTLIL::State::S0 || state.bits[j] == RTLIL::State::S1) {
+				sig_a.append(RTLIL::SigSpec(state_wire, 1, j));
+				sig_b.append(RTLIL::SigSpec(state.bits[j]));
+			}
+		sig_a.optimize();
+		sig_b.optimize();
+
+		if (sig_b == RTLIL::SigSpec(RTLIL::State::S1))
+		{
+			module->connections.push_back(RTLIL::SigSig(RTLIL::SigSpec(state_onehot, 1, i), sig_a));
+		}
+		else
+		{
+			if (sig_b.as_bool() || sig_b.width != fsm_data.state_bits)
+				encoding_is_onehot = false;
+
+			RTLIL::Cell *eq_cell = new RTLIL::Cell;
+			eq_cell->name = NEW_ID;
+			eq_cell->type = "$eq";
+			eq_cell->connections["\\A"] = sig_a;
+			eq_cell->connections["\\B"] = sig_b;
+			eq_cell->connections["\\Y"] = RTLIL::SigSpec(state_onehot, 1, i);
+			eq_cell->parameters["\\A_SIGNED"] = RTLIL::Const(false);
+			eq_cell->parameters["\\B_SIGNED"] = RTLIL::Const(false);
+			eq_cell->parameters["\\A_WIDTH"] = RTLIL::Const(sig_a.width);
+			eq_cell->parameters["\\B_WIDTH"] = RTLIL::Const(sig_b.width);
+			eq_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1);
+			module->add(eq_cell);
+		}
+	}
+
+	// generate next_state signal
+
+	RTLIL::Wire *next_state_onehot = new RTLIL::Wire;
+	next_state_onehot->name = NEW_ID;
+	next_state_onehot->width = fsm_data.state_table.size();
+	module->add(next_state_onehot);
+
+	for (size_t i = 0; i < fsm_data.state_table.size(); i++)
+	{
+		std::map<RTLIL::Const, std::set<int>> pattern_cache;
+		std::set<int> fullstate_cache;
+
+		for (size_t j = 0; j < fsm_data.state_table.size(); j++)
+			fullstate_cache.insert(j);
+
+		for (auto &tr : fsm_data.transition_table) {
+			if (tr.state_out == int(i))
+				pattern_cache[tr.ctrl_in].insert(tr.state_in);
+			else
+				fullstate_cache.erase(tr.state_in);
+		}
+
+		implement_pattern_cache(module, pattern_cache, fullstate_cache, fsm_data.state_table.size(), state_onehot, ctrl_in, RTLIL::SigSpec(next_state_onehot, 1, i));
+	}
+
+	if (encoding_is_onehot)
+	{
+		for (size_t i = 0; i < fsm_data.state_table.size(); i++) {
+			RTLIL::Const state = fsm_data.state_table[i];
+			int bit_idx = -1;
+			for (size_t j = 0; j < state.bits.size(); j++)
+				if (state.bits[j] == RTLIL::State::S1)
+					bit_idx = j;
+			if (bit_idx >= 0)
+				module->connections.push_back(RTLIL::SigSig(RTLIL::SigSpec(next_state_wire, 1, bit_idx), RTLIL::SigSpec(next_state_onehot, 1, i)));
+		}
+	}
+	else
+	{
+		RTLIL::SigSpec sig_a, sig_b, sig_s;
+		int reset_state = fsm_data.reset_state;
+		if (reset_state < 0)
+			reset_state = 0;
+
+		for (size_t i = 0; i < fsm_data.state_table.size(); i++) {
+			RTLIL::Const state = fsm_data.state_table[i];
+			if (int(i) == fsm_data.reset_state) {
+				sig_a = RTLIL::SigSpec(state);
+			} else {
+				sig_b.append(RTLIL::SigSpec(state));
+				sig_s.append(RTLIL::SigSpec(next_state_onehot, 1, i));
+			}
+		}
+
+		RTLIL::Cell *mux_cell = new RTLIL::Cell;
+		mux_cell->name = NEW_ID;
+		mux_cell->type = "$safe_pmux";
+		mux_cell->connections["\\A"] = sig_a;
+		mux_cell->connections["\\B"] = sig_b;
+		mux_cell->connections["\\S"] = sig_s;
+		mux_cell->connections["\\Y"] = RTLIL::SigSpec(next_state_wire);
+		mux_cell->parameters["\\WIDTH"] = RTLIL::Const(sig_a.width);
+		mux_cell->parameters["\\S_WIDTH"] = RTLIL::Const(sig_s.width);
+		module->add(mux_cell);
+	}
+
+	// Generate ctrl_out signal
+
+	RTLIL::Wire *ctrl_out_wire = new RTLIL::Wire;
+	ctrl_out_wire->name = NEW_ID;
+	ctrl_out_wire->width = fsm_data.num_outputs;
+	module->add(ctrl_out_wire);
+
+	for (int i = 0; i < fsm_data.num_outputs; i++)
+	{
+		std::map<RTLIL::Const, std::set<int>> pattern_cache;
+		std::set<int> fullstate_cache;
+
+		for (size_t j = 0; j < fsm_data.state_table.size(); j++)
+			fullstate_cache.insert(j);
+
+		for (auto &tr : fsm_data.transition_table) {
+			if (tr.ctrl_out.bits[i] == RTLIL::State::S1)
+				pattern_cache[tr.ctrl_in].insert(tr.state_in);
+			else
+				fullstate_cache.erase(tr.state_in);
+		}
+
+		implement_pattern_cache(module, pattern_cache, fullstate_cache, fsm_data.state_table.size(), state_onehot, ctrl_in, ctrl_out.extract(i, 1));
+	}
+
+	// Remove FSM cell
+
+	module->cells.erase(fsm_cell->name);
+	delete fsm_cell;
+}
+
+struct FsmMapPass : public Pass {
+	FsmMapPass() : Pass("fsm_map") { }
+	virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
+	{
+		log_header("Executing FSM_MAP pass (simple optimizations of FSMs).\n");
+		extra_args(args, 1, design);
+
+		for (auto &mod_it : design->modules) {
+			std::vector<RTLIL::Cell*> fsm_cells;
+			for (auto &cell_it : mod_it.second->cells)
+				if (cell_it.second->type == "$fsm")
+					fsm_cells.push_back(cell_it.second);
+			for (auto cell : fsm_cells)
+					map_fsm(cell, mod_it.second);
+		}
+	}
+} FsmMapPass;
+ 
diff --git a/passes/fsm/fsm_opt.cc b/passes/fsm/fsm_opt.cc
new file mode 100644
index 000000000..8ba9679fd
--- /dev/null
+++ b/passes/fsm/fsm_opt.cc
@@ -0,0 +1,285 @@
+/*
+ *  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/log.h"
+#include "kernel/register.h"
+#include "kernel/sigtools.h"
+#include "kernel/consteval.h"
+#include "kernel/celltypes.h"
+#include "fsmdata.h"
+#include <string.h>
+
+struct FsmOpt
+{
+	FsmData fsm_data;
+	RTLIL::Cell *cell;
+	RTLIL::Module *module;
+	
+	bool signal_is_unused(RTLIL::SigSpec sig)
+	{
+		assert(sig.width == 1);
+		sig.optimize();
+
+		RTLIL::Wire *wire = sig.chunks[0].wire;
+		int bit = sig.chunks[0].offset;
+
+		if (!wire || wire->attributes.count("\\unused_bits") == 0)
+			return false;
+		
+		char *str = strdup(wire->attributes["\\unused_bits"].str.c_str());
+		for (char *tok = strtok(str, " "); tok != NULL; tok = strtok(NULL, " ")) {
+			if (tok[0] && bit == atoi(tok))
+				return true;
+		}
+		free(str);
+
+		return false;
+	}
+
+	void opt_const_and_unused_inputs()
+	{
+		RTLIL::SigSpec ctrl_in = cell->connections["\\CTRL_IN"];
+		std::vector<bool> ctrl_in_used(ctrl_in.width);
+
+		std::vector<FsmData::transition_t> new_transition_table;
+		for (auto &tr : fsm_data.transition_table) {
+			for (int i = 0; i < ctrl_in.width; i++) {
+				RTLIL::SigSpec ctrl_bit = ctrl_in.extract(i, 1);
+				if (ctrl_bit.is_fully_const()) {
+					if (tr.ctrl_in.bits[i] <= RTLIL::State::S1 && RTLIL::SigSpec(tr.ctrl_in.bits[i]) != ctrl_bit)
+						goto delete_this_transition;
+					continue;
+				}
+				if (tr.ctrl_in.bits[i] <= RTLIL::State::S1)
+					ctrl_in_used[i] = true;
+			}
+			new_transition_table.push_back(tr);
+		delete_this_transition:;
+		}
+
+		for (int i = int(ctrl_in_used.size())-1; i >= 0; i--) {
+			if (!ctrl_in_used[i]) {
+				log("  Removing unused input signal %s.\n", log_signal(cell->connections["\\CTRL_IN"].extract(i, 1)));
+				for (auto &tr : new_transition_table) {
+					RTLIL::SigSpec tmp(tr.ctrl_in);
+					tmp.remove(i, 1);
+					tr.ctrl_in = tmp.as_const();
+				}
+				cell->connections["\\CTRL_IN"].remove(i, 1);
+				fsm_data.num_inputs--;
+			}
+		}
+
+		fsm_data.transition_table.swap(new_transition_table);
+		new_transition_table.clear();
+	}
+
+	void opt_unused_outputs()
+	{
+		for (int i = 0; i < fsm_data.num_outputs; i++) {
+			RTLIL::SigSpec sig = cell->connections["\\CTRL_OUT"].extract(i, 1);
+			if (signal_is_unused(sig)) {
+				log("  Removing unused output signal %s.\n", log_signal(sig));
+				cell->connections["\\CTRL_OUT"].remove(i, 1);
+				for (auto &tr : fsm_data.transition_table) {
+					RTLIL::SigSpec tmp(tr.ctrl_out);
+					tmp.remove(i, 1);
+					tr.ctrl_out = tmp.as_const();
+				}
+				fsm_data.num_outputs--;
+				i--;
+			}
+		}
+	}
+
+	void opt_alias_inputs()
+	{
+		RTLIL::SigSpec &ctrl_in = cell->connections["\\CTRL_IN"];
+
+		for (int i = 0; i < ctrl_in.width; i++)
+		for (int j = i+1; j < ctrl_in.width; j++)
+			if (ctrl_in.extract(i, 1) == ctrl_in.extract(j, 1))
+			{
+				log("  Optimize handling of signal %s that is connected to inputs %d and %d.\n", log_signal(ctrl_in.extract(i, 1)), i, j);
+				std::vector<FsmData::transition_t> new_transition_table;
+
+				for (auto tr : fsm_data.transition_table)
+				{
+					RTLIL::State &si = tr.ctrl_in.bits[i];
+					RTLIL::State &sj = tr.ctrl_in.bits[j];
+
+					if (si > RTLIL::State::S1)
+						si = sj;
+					else if (sj > RTLIL::State::S1)
+						sj = si;
+
+					if (si == sj) {
+						RTLIL::SigSpec tmp(tr.ctrl_in);
+						tmp.remove(j, 1);
+						tr.ctrl_in = tmp.as_const();
+						new_transition_table.push_back(tr);
+					}
+				}
+
+				ctrl_in.remove(j--, 1);
+				fsm_data.num_inputs--;
+
+				fsm_data.transition_table.swap(new_transition_table);
+				new_transition_table.clear();
+			}
+	}
+
+	void opt_feedback_inputs()
+	{
+		RTLIL::SigSpec &ctrl_in = cell->connections["\\CTRL_IN"];
+		RTLIL::SigSpec &ctrl_out = cell->connections["\\CTRL_OUT"];
+
+		for (int j = 0; j < ctrl_out.width; j++)
+		for (int i = 0; i < ctrl_in.width; i++)
+			if (ctrl_in.extract(i, 1) == ctrl_out.extract(j, 1))
+			{
+				log("  Optimize handling of signal %s that is connected to input %d and output %d.\n", log_signal(ctrl_in.extract(i, 1)), i, j);
+				std::vector<FsmData::transition_t> new_transition_table;
+
+				for (auto tr : fsm_data.transition_table)
+				{
+					RTLIL::State &si = tr.ctrl_in.bits[i];
+					RTLIL::State &sj = tr.ctrl_out.bits[j];
+
+					if (si > RTLIL::State::S1 || si == sj) {
+						RTLIL::SigSpec tmp(tr.ctrl_in);
+						tmp.remove(i, 1);
+						tr.ctrl_in = tmp.as_const();
+						new_transition_table.push_back(tr);
+					}
+				}
+
+				ctrl_in.remove(i--, 1);
+				fsm_data.num_inputs--;
+
+				fsm_data.transition_table.swap(new_transition_table);
+				new_transition_table.clear();
+			}
+	}
+
+	void opt_find_dont_care_worker(std::set<RTLIL::Const> &set, int bit, FsmData::transition_t &tr, bool &did_something)
+	{
+		std::set<RTLIL::Const> new_set;
+
+		for (auto &pattern : set)
+		{
+			if (pattern.bits[bit] > RTLIL::State::S1) {
+				new_set.insert(pattern);
+				continue;
+			}
+
+			RTLIL::Const other_pattern = pattern;
+
+			if (pattern.bits[bit] == RTLIL::State::S1)
+				other_pattern.bits[bit] = RTLIL::State::S0;
+			else
+				other_pattern.bits[bit] = RTLIL::State::S1;
+
+			if (set.count(other_pattern) > 0) {
+				log("  Merging pattern %s and %s from group (%d %d %s).\n", log_signal(pattern), log_signal(other_pattern),
+						tr.state_in, tr.state_out, log_signal(tr.ctrl_out));
+				other_pattern.bits[bit] = RTLIL::State::Sa;
+				new_set.insert(other_pattern);
+				did_something = true;
+				continue;
+			}
+
+			new_set.insert(pattern);
+		}
+
+		set.swap(new_set);
+	}
+
+	void opt_find_dont_care()
+	{
+		typedef std::pair<std::pair<int, int>, RTLIL::Const> group_t;
+		std::map<group_t, std::set<RTLIL::Const>> transitions_by_group;
+
+		for (auto &tr : fsm_data.transition_table) {
+			group_t group(std::pair<int, int>(tr.state_in, tr.state_out), tr.ctrl_out);
+			transitions_by_group[group].insert(tr.ctrl_in);
+		}
+
+		fsm_data.transition_table.clear();
+		for (auto &it : transitions_by_group)
+		{
+			FsmData::transition_t tr;
+			tr.state_in = it.first.first.first;
+			tr.state_out = it.first.first.second;
+			tr.ctrl_out = it.first.second;
+
+			bool did_something = true;
+			while (did_something) {
+				did_something = false;
+				for (int i = 0; i < fsm_data.num_inputs; i++)
+					opt_find_dont_care_worker(it.second, i, tr, did_something);
+			}
+
+			for (auto &ci : it.second) {
+				tr.ctrl_in = ci;
+				fsm_data.transition_table.push_back(tr);
+			}
+		}
+	}
+
+	FsmOpt(RTLIL::Cell *cell, RTLIL::Module *module)
+	{
+		log("Optimizing FSM `%s' from module `%s'.\n", cell->name.c_str(), module->name.c_str());
+
+		fsm_data.copy_from_cell(cell);
+		this->cell = cell;
+		this->module = module;
+
+		opt_unused_outputs();
+
+		opt_alias_inputs();
+		opt_feedback_inputs();
+		opt_find_dont_care();
+
+		opt_const_and_unused_inputs();
+
+		fsm_data.copy_to_cell(cell);
+	}
+};
+
+void FsmData::optimize_fsm(RTLIL::Cell *cell, RTLIL::Module *module)
+{
+	FsmOpt fsmopt(cell, module);
+}
+
+struct FsmOptPass : public Pass {
+	FsmOptPass() : Pass("fsm_opt") { }
+	virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
+	{
+		log_header("Executing FSM_OPT pass (simple optimizations of FSMs).\n");
+		extra_args(args, 1, design);
+
+		for (auto &mod_it : design->modules)
+		for (auto &cell_it : mod_it.second->cells) {
+			if (cell_it.second->type == "$fsm")
+				FsmData::optimize_fsm(cell_it.second, mod_it.second);
+		}
+	}
+} FsmOptPass;
+ 
diff --git a/passes/fsm/fsm_recode.cc b/passes/fsm/fsm_recode.cc
new file mode 100644
index 000000000..5e258f269
--- /dev/null
+++ b/passes/fsm/fsm_recode.cc
@@ -0,0 +1,114 @@
+/*
+ *  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/log.h"
+#include "kernel/register.h"
+#include "kernel/sigtools.h"
+#include "kernel/consteval.h"
+#include "kernel/celltypes.h"
+#include "fsmdata.h"
+#include <string.h>
+
+static void fm_set_fsm_print(RTLIL::Cell *cell, RTLIL::Module *module, FsmData &fsm_data, const char *prefix, FILE *f)
+{
+	fprintf(f, "set_fsm_state_vector {");
+	for (int i = fsm_data.state_bits-1; i >= 0; i--)
+		fprintf(f, " %s_reg[%d]", cell->parameters["\\NAME"].str[0] == '\\' ?
+				cell->parameters["\\NAME"].str.substr(1).c_str() : cell->parameters["\\NAME"].str.c_str(), i);
+	fprintf(f, " } -name {%s_%s} {%s:/WORK/%s}\n",
+			prefix, RTLIL::unescape_id(cell->parameters["\\NAME"].str).c_str(),
+			prefix, RTLIL::unescape_id(module->name).c_str());
+
+	fprintf(f, "set_fsm_encoding {");
+	for (size_t i = 0; i < fsm_data.state_table.size(); i++) {
+		fprintf(f, " s%zd=2#", i);
+		for (int j = int(fsm_data.state_table[i].bits.size())-1; j >= 0; j--)
+			fprintf(f, "%c", fsm_data.state_table[i].bits[j] == RTLIL::State::S1 ? '1' : '0');
+	}
+	fprintf(f, " } -name {%s_%s} {%s:/WORK/%s}\n",
+			prefix, RTLIL::unescape_id(cell->parameters["\\NAME"].str).c_str(),
+			prefix, RTLIL::unescape_id(module->name).c_str());
+}
+
+static void fsm_recode(RTLIL::Cell *cell, RTLIL::Module *module, FILE *fm_set_fsm_file)
+{
+	FsmData fsm_data;
+	fsm_data.copy_from_cell(cell);
+
+	log("Recoding FSM `%s' from module `%s':\n", cell->name.c_str(), module->name.c_str());
+
+	if (fm_set_fsm_file != NULL)
+		fm_set_fsm_print(cell, module, fsm_data, "r", fm_set_fsm_file);
+
+	fsm_data.state_bits = fsm_data.state_table.size();
+	if (fsm_data.reset_state >= 0)
+		fsm_data.state_bits--;
+
+	int bit_pos = 0;
+	for (size_t i = 0; i < fsm_data.state_table.size(); i++)
+	{
+		RTLIL::Const new_code;
+		if (int(i) == fsm_data.reset_state)
+			new_code = RTLIL::Const(RTLIL::State::S0, fsm_data.state_bits);
+		else {
+			RTLIL::Const state_code(RTLIL::State::Sa, fsm_data.state_bits);
+			state_code.bits[bit_pos++] = RTLIL::State::S1;
+			new_code = state_code;
+		}
+
+		log("  %s -> %s\n", fsm_data.state_table[i].as_string().c_str(), new_code.as_string().c_str());
+		fsm_data.state_table[i] = new_code;
+	}
+
+	if (fm_set_fsm_file != NULL)
+		fm_set_fsm_print(cell, module, fsm_data, "i", fm_set_fsm_file);
+
+	fsm_data.copy_to_cell(cell);
+}
+
+struct FsmRecodePass : public Pass {
+	FsmRecodePass() : Pass("fsm_recode") { }
+	virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
+	{
+		FILE *fm_set_fsm_file = NULL;
+
+		log_header("Executing FSM_RECODE pass (re-assigning FSM state encoding).\n");
+		size_t argidx;
+		for (argidx = 1; argidx < args.size(); argidx++) {
+			std::string arg = args[argidx];
+			if (arg == "-fm_set_fsm_file" && argidx+1 < args.size() && fm_set_fsm_file == NULL) {
+				fm_set_fsm_file = fopen(args[++argidx].c_str(), "w");
+				if (fm_set_fsm_file == NULL)
+					log_error("Can't open fm_set_fsm_file `%s' for writing: %s\n", args[argidx].c_str(), strerror(errno));
+				continue;
+			}
+			break;
+		}
+		extra_args(args, argidx, design);
+
+		for (auto &mod_it : design->modules)
+		for (auto &cell_it : mod_it.second->cells)
+			if (cell_it.second->type == "$fsm")
+				fsm_recode(cell_it.second, mod_it.second, fm_set_fsm_file);
+
+		if (fm_set_fsm_file != NULL)
+			fclose(fm_set_fsm_file);
+	}
+} FsmRecodePass;
+ 
diff --git a/passes/fsm/fsmdata.h b/passes/fsm/fsmdata.h
new file mode 100644
index 000000000..f43b25fe9
--- /dev/null
+++ b/passes/fsm/fsmdata.h
@@ -0,0 +1,177 @@
+/*
+ *  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.
+ *
+ */
+
+#ifndef FSMDATA_H
+#define FSMDATA_H
+
+#include "kernel/rtlil.h"
+#include "kernel/log.h"
+
+struct FsmData
+{
+	int num_inputs, num_outputs, state_bits, reset_state;
+	struct transition_t { int state_in, state_out; RTLIL::Const ctrl_in, ctrl_out; };
+	std::vector<transition_t> transition_table;
+	std::vector<RTLIL::Const> state_table;
+
+	void copy_to_cell(RTLIL::Cell *cell)
+	{
+		cell->parameters["\\CTRL_IN_WIDTH"] = RTLIL::Const(num_inputs);
+		cell->parameters["\\CTRL_OUT_WIDTH"] = RTLIL::Const(num_outputs);
+
+		int state_num_log2 = 0;
+		for (int i = state_table.size(); i > 0; i = i >> 1)
+			state_num_log2++;
+		state_num_log2 = std::max(state_num_log2, 1);
+
+		cell->parameters["\\STATE_BITS"] = RTLIL::Const(state_bits);
+		cell->parameters["\\STATE_NUM"] = RTLIL::Const(state_table.size());
+		cell->parameters["\\STATE_NUM_LOG2"] = RTLIL::Const(state_num_log2);
+		cell->parameters["\\STATE_RST"] = RTLIL::Const(reset_state);
+		cell->parameters["\\STATE_TABLE"] = RTLIL::Const();
+
+		for (int i = 0; i < int(state_table.size()); i++) {
+			std::vector<RTLIL::State> &bits_table = cell->parameters["\\STATE_TABLE"].bits;
+			std::vector<RTLIL::State> &bits_state = state_table[i].bits;
+			bits_table.insert(bits_table.end(), bits_state.begin(), bits_state.end());
+		}
+
+		cell->parameters["\\TRANS_NUM"] = RTLIL::Const(transition_table.size());
+		cell->parameters["\\TRANS_TABLE"] = RTLIL::Const();
+		for (int i = 0; i < int(transition_table.size()); i++)
+		{
+			std::vector<RTLIL::State> &bits_table = cell->parameters["\\TRANS_TABLE"].bits;
+			transition_t &tr = transition_table[i];
+
+			RTLIL::Const const_state_in = RTLIL::Const(tr.state_in, state_num_log2);
+			RTLIL::Const const_state_out = RTLIL::Const(tr.state_out, state_num_log2);
+			std::vector<RTLIL::State> &bits_state_in = const_state_in.bits;
+			std::vector<RTLIL::State> &bits_state_out = const_state_out.bits;
+
+			std::vector<RTLIL::State> &bits_ctrl_in = tr.ctrl_in.bits;
+			std::vector<RTLIL::State> &bits_ctrl_out = tr.ctrl_out.bits;
+
+			// append lsb first
+			bits_table.insert(bits_table.end(), bits_ctrl_out.begin(), bits_ctrl_out.end());
+			bits_table.insert(bits_table.end(), bits_state_out.begin(), bits_state_out.end());
+			bits_table.insert(bits_table.end(), bits_ctrl_in.begin(), bits_ctrl_in.end());
+			bits_table.insert(bits_table.end(), bits_state_in.begin(), bits_state_in.end());
+		}
+	}
+
+	void copy_from_cell(RTLIL::Cell *cell)
+	{
+		num_inputs = cell->parameters["\\CTRL_IN_WIDTH"].as_int();
+		num_outputs = cell->parameters["\\CTRL_OUT_WIDTH"].as_int();
+
+		state_bits = cell->parameters["\\STATE_BITS"].as_int();
+		reset_state = cell->parameters["\\STATE_RST"].as_int();
+
+		int state_num = cell->parameters["\\STATE_NUM"].as_int();
+		int state_num_log2 = cell->parameters["\\STATE_NUM_LOG2"].as_int();
+		int trans_num = cell->parameters["\\TRANS_NUM"].as_int();
+
+		if (reset_state < 0 || reset_state >= state_num)
+			reset_state = -1;
+
+		RTLIL::Const state_table = cell->parameters["\\STATE_TABLE"];
+		RTLIL::Const trans_table = cell->parameters["\\TRANS_TABLE"];
+
+		for (int i = 0; i < state_num; i++) {
+			RTLIL::Const state_code;
+			int off_begin = i*state_bits, off_end = off_begin + state_bits;
+			state_code.bits.insert(state_code.bits.begin(), state_table.bits.begin()+off_begin, state_table.bits.begin()+off_end);
+			this->state_table.push_back(state_code);
+		}
+
+		for (int i = 0; i < trans_num; i++)
+		{
+			auto off_ctrl_out = trans_table.bits.begin() + i*(num_inputs+num_outputs+2*state_num_log2);
+			auto off_state_out = off_ctrl_out + num_outputs;
+			auto off_ctrl_in = off_state_out + state_num_log2;
+			auto off_state_in = off_ctrl_in + num_inputs;
+			auto off_end = off_state_in + state_num_log2;
+
+			RTLIL::Const state_in, state_out, ctrl_in, ctrl_out;
+			ctrl_out.bits.insert(state_in.bits.begin(), off_ctrl_out, off_state_out);
+			state_out.bits.insert(state_out.bits.begin(), off_state_out, off_ctrl_in);
+			ctrl_in.bits.insert(ctrl_in.bits.begin(), off_ctrl_in, off_state_in);
+			state_in.bits.insert(state_in.bits.begin(), off_state_in, off_end);
+
+			transition_t tr;
+			tr.state_in = state_in.as_int();
+			tr.state_out = state_out.as_int();
+			tr.ctrl_in = ctrl_in;
+			tr.ctrl_out = ctrl_out;
+
+			if (tr.state_in < 0 || tr.state_in >= state_num)
+				tr.state_in = -1;
+			if (tr.state_out < 0 || tr.state_out >= state_num)
+				tr.state_out = -1;
+
+			transition_table.push_back(tr);
+		}
+	}
+
+	void log_info(RTLIL::Cell *cell)
+	{
+		log("-------------------------------------\n");
+		log("\n");
+		log("  Information on FSM %s (%s):\n", cell->name.c_str(), cell->parameters["\\NAME"].str.c_str());
+		log("\n");
+		log("  Number of input signals:  %3d\n", num_inputs);
+		log("  Number of output signals: %3d\n", num_outputs);
+		log("  Number of state bits:     %3d\n", state_bits);
+
+		log("\n");
+		log("  Input signals:\n");
+		RTLIL::SigSpec sig_in = cell->connections["\\CTRL_IN"];
+		sig_in.expand();
+		for (size_t i = 0; i < sig_in.chunks.size(); i++)
+			log("  %3zd: %s\n", i, log_signal(sig_in.chunks[i]));
+
+		log("\n");
+		log("  Output signals:\n");
+		RTLIL::SigSpec sig_out = cell->connections["\\CTRL_OUT"];
+		sig_out.expand();
+		for (size_t i = 0; i < sig_out.chunks.size(); i++)
+			log("  %3zd: %s\n", i, log_signal(sig_out.chunks[i]));
+
+		log("\n");
+		log("  State encoding:\n");
+		for (size_t i = 0; i < state_table.size(); i++)
+			log("  %3zd: %10s%s\n", i, log_signal(state_table[i], false),
+					int(i) == reset_state ? "  <RESET STATE>" : "");
+
+		log("\n");
+		log("  Transition Table (state_in, ctrl_in, state_out, ctrl_out):\n");
+		for (size_t i = 0; i < transition_table.size(); i++) {
+			transition_t &tr = transition_table[i];
+			log("  %5zd: %5d %s   -> %5d %s\n", i, tr.state_in, log_signal(tr.ctrl_in), tr.state_out, log_signal(tr.ctrl_out));
+		}
+
+		log("\n");
+		log("-------------------------------------\n");
+	}
+
+	// implemented in fsm_opt.cc
+	static void optimize_fsm(RTLIL::Cell *cell, RTLIL::Module *module);
+};
+
+#endif