passes/fsm/fsm_expand.cc - third_party/yosys - Git at Google

 /*
  *  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>

 USING_YOSYS_NAMESPACE
 PRIVATE_NAMESPACE_BEGIN

 struct FsmExpand
 {
 	RTLIL::Module *module;
 	RTLIL::Cell *fsm_cell;
 	bool full_mode;

 	SigMap assign_map;
 	SigSet<RTLIL::Cell*, RTLIL::sort_by_name_id<RTLIL::Cell>> sig2driver, sig2user;
 	CellTypes ct;

 	std::set<RTLIL::Cell*, RTLIL::sort_by_name_id<RTLIL::Cell>> merged_set;
 	std::set<RTLIL::Cell*, RTLIL::sort_by_name_id<RTLIL::Cell>> current_set;
 	std::set<RTLIL::Cell*, RTLIL::sort_by_name_id<RTLIL::Cell>> no_candidate_set;

 	bool already_optimized;
 	int limit_transitions;

 	bool is_cell_merge_candidate(RTLIL::Cell *cell)
 	{
 		if (full_mode || cell->type == "$_MUX_")
 			return true;

 		if (cell->type.in("$mux", "$pmux"))
 			if (cell->getPort("\\A").size() < 2)
 				return true;

 		int in_bits = 0;
 		RTLIL::SigSpec new_signals;

 		if (cell->hasPort("\\A")) {
 			in_bits += GetSize(cell->getPort("\\A"));
 			new_signals.append(assign_map(cell->getPort("\\A")));
 		}

 		if (cell->hasPort("\\B")) {
 			in_bits += GetSize(cell->getPort("\\B"));
 			new_signals.append(assign_map(cell->getPort("\\B")));
 		}

 		if (cell->hasPort("\\S")) {
 			in_bits += GetSize(cell->getPort("\\S"));
 			new_signals.append(assign_map(cell->getPort("\\S")));
 		}

 		if (in_bits > 8)
 			return false;

 		if (cell->hasPort("\\Y"))
 			new_signals.append(assign_map(cell->getPort("\\Y")));

 		new_signals.sort_and_unify();
 		new_signals.remove_const();

 		new_signals.remove(assign_map(fsm_cell->getPort("\\CTRL_IN")));
 		new_signals.remove(assign_map(fsm_cell->getPort("\\CTRL_OUT")));

 		if (new_signals.size() > 3)
 			return false;

 		return true;
 	}

 	void create_current_set()
 	{
 		std::vector<RTLIL::Cell*> cell_list;

 		for (auto c : sig2driver.find(assign_map(fsm_cell->getPort("\\CTRL_IN"))))
 			cell_list.push_back(c);

 		for (auto c : sig2user.find(assign_map(fsm_cell->getPort("\\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();

 		std::vector<RTLIL::Const> truth_tab;

 		for (int i = 0; i < (1 << input_sig.size()); i++) {
 			RTLIL::Const in_val(i, input_sig.size());
 			RTLIL::SigSpec A, B, S;
 			if (cell->hasPort("\\A"))
 				A = assign_map(cell->getPort("\\A"));
 			if (cell->hasPort("\\B"))
 				B = assign_map(cell->getPort("\\B"));
 			if (cell->hasPort("\\S"))
 				S = assign_map(cell->getPort("\\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));
 			log_assert(A.is_fully_const());
 			log_assert(B.is_fully_const());
 			log_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.size();
 		RTLIL::SigSpec new_ctrl_in = fsm_cell->getPort("\\CTRL_IN");
 		new_ctrl_in.append(input_sig);
 		fsm_cell->setPort("\\CTRL_IN", new_ctrl_in);

 		fsm_data.num_outputs += output_sig.size();
 		RTLIL::SigSpec new_ctrl_out = fsm_cell->getPort("\\CTRL_OUT");
 		new_ctrl_out.append(output_sig);
 		fsm_cell->setPort("\\CTRL_OUT", new_ctrl_out);

 		if (GetSize(input_sig) > 10)
 			log_warning("Cell %s.%s (%s) has %d input bits, merging into FSM %s.%s might be problematic.\n",
 					log_id(cell->module), log_id(cell), log_id(cell->type),
 					GetSize(input_sig), log_id(fsm_cell->module), log_id(fsm_cell));

 		if (GetSize(fsm_data.transition_table) > 10000)
 			log_warning("Transition table for FSM %s.%s already has %d rows, merging more cells "
 					"into this FSM might be problematic.\n", log_id(fsm_cell->module), log_id(fsm_cell),
 					GetSize(fsm_data.transition_table));

 		std::vector<FsmData::transition_t> new_transition_table;
 		for (auto &tr : fsm_data.transition_table) {
 			for (int i = 0; i < (1 << input_sig.size()); i++) {
 				FsmData::transition_t new_tr = tr;
 				RTLIL::Const in_val(i, input_sig.size());
 				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::Design *design, RTLIL::Module *mod, bool full)
 	{
 		module = mod;
 		fsm_cell = cell;
 		full_mode = full;

 		assign_map.set(module);
 		ct.setup_internals();
 		ct.setup_stdcells();

 		for (auto &cell_it : module->cells_) {
 			RTLIL::Cell *c = cell_it.second;
 			if (ct.cell_known(c->type) && design->selected(mod, c))
 				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->remove(c);

 		if (merged_set.size() > 0 && !already_optimized)
 			FsmData::optimize_fsm(fsm_cell, module);

 		log("  merged %d cells into FSM.\n", GetSize(merged_set));
 	}
 };

 struct FsmExpandPass : public Pass {
 	FsmExpandPass() : Pass("fsm_expand", "expand FSM cells by merging logic into it") { }
 	void help() YS_OVERRIDE
 	{
 		//   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 		log("\n");
 		log("    fsm_expand [-full] [selection]\n");
 		log("\n");
 		log("The fsm_extract pass is conservative about the cells that belong to a finite\n");
 		log("state machine. This pass can be used to merge additional auxiliary gates into\n");
 		log("the finite state machine.\n");
 		log("\n");
 		log("By default, fsm_expand is still a bit conservative regarding merging larger\n");
 		log("word-wide cells. Call with -full to consider all cells for merging.\n");
 		log("\n");
 	}
 	void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
 	{
 		bool full_mode = false;

 		log_header(design, "Executing FSM_EXPAND pass (merging auxiliary logic into FSMs).\n");

 		size_t argidx;
 		for (argidx = 1; argidx < args.size(); argidx++) {
 			if (args[argidx] == "-full") {
 				full_mode = true;
 				continue;
 			}
 			break;
 		}
 		extra_args(args, argidx, design);

 		for (auto &mod_it : design->modules_) {
 			if (!design->selected(mod_it.second))
 				continue;
 			std::vector<RTLIL::Cell*> fsm_cells;
 			for (auto &cell_it : mod_it.second->cells_)
 				if (cell_it.second->type == "$fsm" && design->selected(mod_it.second, cell_it.second))
 					fsm_cells.push_back(cell_it.second);
 			for (auto c : fsm_cells) {
 				FsmExpand fsm_expand(c, design, mod_it.second, full_mode);
 				fsm_expand.execute();
 			}
 		}
 	}
 } FsmExpandPass;

 PRIVATE_NAMESPACE_END
	/*
	* 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>

	USING_YOSYS_NAMESPACE
	PRIVATE_NAMESPACE_BEGIN

	struct FsmExpand
	{
	RTLIL::Module *module;
	RTLIL::Cell *fsm_cell;
	bool full_mode;

	SigMap assign_map;
	SigSet<RTLIL::Cell*, RTLIL::sort_by_name_id<RTLIL::Cell>> sig2driver, sig2user;
	CellTypes ct;

	std::set<RTLIL::Cell*, RTLIL::sort_by_name_id<RTLIL::Cell>> merged_set;
	std::set<RTLIL::Cell*, RTLIL::sort_by_name_id<RTLIL::Cell>> current_set;
	std::set<RTLIL::Cell*, RTLIL::sort_by_name_id<RTLIL::Cell>> no_candidate_set;

	bool already_optimized;
	int limit_transitions;

	bool is_cell_merge_candidate(RTLIL::Cell *cell)
	{
	if (full_mode \|\| cell->type == "$_MUX_")
	return true;

	if (cell->type.in("$mux", "$pmux"))
	if (cell->getPort("\\A").size() < 2)
	return true;

	int in_bits = 0;
	RTLIL::SigSpec new_signals;

	if (cell->hasPort("\\A")) {
	in_bits += GetSize(cell->getPort("\\A"));
	new_signals.append(assign_map(cell->getPort("\\A")));
	}

	if (cell->hasPort("\\B")) {
	in_bits += GetSize(cell->getPort("\\B"));
	new_signals.append(assign_map(cell->getPort("\\B")));
	}

	if (cell->hasPort("\\S")) {
	in_bits += GetSize(cell->getPort("\\S"));
	new_signals.append(assign_map(cell->getPort("\\S")));
	}

	if (in_bits > 8)
	return false;

	if (cell->hasPort("\\Y"))
	new_signals.append(assign_map(cell->getPort("\\Y")));

	new_signals.sort_and_unify();
	new_signals.remove_const();

	new_signals.remove(assign_map(fsm_cell->getPort("\\CTRL_IN")));
	new_signals.remove(assign_map(fsm_cell->getPort("\\CTRL_OUT")));

	if (new_signals.size() > 3)
	return false;

	return true;
	}

	void create_current_set()
	{
	std::vector<RTLIL::Cell*> cell_list;

	for (auto c : sig2driver.find(assign_map(fsm_cell->getPort("\\CTRL_IN"))))
	cell_list.push_back(c);

	for (auto c : sig2user.find(assign_map(fsm_cell->getPort("\\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();

	std::vector<RTLIL::Const> truth_tab;

	for (int i = 0; i < (1 << input_sig.size()); i++) {
	RTLIL::Const in_val(i, input_sig.size());
	RTLIL::SigSpec A, B, S;
	if (cell->hasPort("\\A"))
	A = assign_map(cell->getPort("\\A"));
	if (cell->hasPort("\\B"))
	B = assign_map(cell->getPort("\\B"));
	if (cell->hasPort("\\S"))
	S = assign_map(cell->getPort("\\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));
	log_assert(A.is_fully_const());
	log_assert(B.is_fully_const());
	log_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.size();
	RTLIL::SigSpec new_ctrl_in = fsm_cell->getPort("\\CTRL_IN");
	new_ctrl_in.append(input_sig);
	fsm_cell->setPort("\\CTRL_IN", new_ctrl_in);

	fsm_data.num_outputs += output_sig.size();
	RTLIL::SigSpec new_ctrl_out = fsm_cell->getPort("\\CTRL_OUT");
	new_ctrl_out.append(output_sig);
	fsm_cell->setPort("\\CTRL_OUT", new_ctrl_out);

	if (GetSize(input_sig) > 10)
	log_warning("Cell %s.%s (%s) has %d input bits, merging into FSM %s.%s might be problematic.\n",
	log_id(cell->module), log_id(cell), log_id(cell->type),
	GetSize(input_sig), log_id(fsm_cell->module), log_id(fsm_cell));

	if (GetSize(fsm_data.transition_table) > 10000)
	log_warning("Transition table for FSM %s.%s already has %d rows, merging more cells "
	"into this FSM might be problematic.\n", log_id(fsm_cell->module), log_id(fsm_cell),
	GetSize(fsm_data.transition_table));

	std::vector<FsmData::transition_t> new_transition_table;
	for (auto &tr : fsm_data.transition_table) {
	for (int i = 0; i < (1 << input_sig.size()); i++) {
	FsmData::transition_t new_tr = tr;
	RTLIL::Const in_val(i, input_sig.size());
	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::Design design, RTLIL::Module *mod, bool full)
	{
	module = mod;
	fsm_cell = cell;
	full_mode = full;

	assign_map.set(module);
	ct.setup_internals();
	ct.setup_stdcells();

	for (auto &cell_it : module->cells_) {
	RTLIL::Cell *c = cell_it.second;
	if (ct.cell_known(c->type) && design->selected(mod, c))
	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->remove(c);

	if (merged_set.size() > 0 && !already_optimized)
	FsmData::optimize_fsm(fsm_cell, module);

	log(" merged %d cells into FSM.\n", GetSize(merged_set));
	}
	};

	struct FsmExpandPass : public Pass {
	FsmExpandPass() : Pass("fsm_expand", "expand FSM cells by merging logic into it") { }
	void help() YS_OVERRIDE
	{
	// \|---v---\|---v---\|---v---\|---v---\|---v---\|---v---\|---v---\|---v---\|---v---\|---v---\|
	log("\n");
	log(" fsm_expand [-full] [selection]\n");
	log("\n");
	log("The fsm_extract pass is conservative about the cells that belong to a finite\n");
	log("state machine. This pass can be used to merge additional auxiliary gates into\n");
	log("the finite state machine.\n");
	log("\n");
	log("By default, fsm_expand is still a bit conservative regarding merging larger\n");
	log("word-wide cells. Call with -full to consider all cells for merging.\n");
	log("\n");
	}
	void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
	{
	bool full_mode = false;

	log_header(design, "Executing FSM_EXPAND pass (merging auxiliary logic into FSMs).\n");

	size_t argidx;
	for (argidx = 1; argidx < args.size(); argidx++) {
	if (args[argidx] == "-full") {
	full_mode = true;
	continue;
	}
	break;
	}
	extra_args(args, argidx, design);

	for (auto &mod_it : design->modules_) {
	if (!design->selected(mod_it.second))
	continue;
	std::vector<RTLIL::Cell*> fsm_cells;
	for (auto &cell_it : mod_it.second->cells_)
	if (cell_it.second->type == "$fsm" && design->selected(mod_it.second, cell_it.second))
	fsm_cells.push_back(cell_it.second);
	for (auto c : fsm_cells) {
	FsmExpand fsm_expand(c, design, mod_it.second, full_mode);
	fsm_expand.execute();
	}
	}
	}
	} FsmExpandPass;

	PRIVATE_NAMESPACE_END