Added functionality to dff2dffe pass

1 files changed, 167 insertions, 2 deletions

diff --git a/passes/techmap/dff2dffe.cc b/passes/techmap/dff2dffe.cc
index 6a1261f4..74f31f14 100644
--- a/passes/techmap/dff2dffe.cc
+++ b/passes/techmap/dff2dffe.cc
@@ -19,6 +19,7 @@
 
 #include "kernel/yosys.h"
 #include "kernel/sigtools.h"
+#include "kernel/celltypes.h"
 
 USING_YOSYS_NAMESPACE
 PRIVATE_NAMESPACE_BEGIN
@@ -27,14 +28,178 @@ struct Dff2dffeWorker
 {
 	RTLIL::Module *module;
 	SigMap sigmap;
+	CellTypes ct;
 
-	Dff2dffeWorker(RTLIL::Module *module) : module(module), sigmap(module)
+	typedef std::pair<RTLIL::Cell*, int> cell_int_t;
+	std::map<RTLIL::SigBit, cell_int_t> bit2mux;
+	std::vector<RTLIL::Cell*> dff_cells;
+	std::map<RTLIL::SigBit, int> bitusers;
+
+	typedef std::map<RTLIL::SigBit, bool> pattern_t;
+	typedef std::set<pattern_t> patterns_t;
+
+	Dff2dffeWorker(RTLIL::Module *module) : module(module), sigmap(module), ct(module->design)
 	{
+		for (auto wire : module->wires()) {
+			if (wire->port_output)
+				for (auto bit : sigmap(wire))
+					bitusers[bit]++;
+		}
+
+		for (auto cell : module->cells()) {
+			if (cell->type == "$mux" || cell->type == "$pmux") {
+				RTLIL::SigSpec sig_y = sigmap(cell->getPort("\\Y"));
+				for (int i = 0; i < GetSize(sig_y); i++)
+					bit2mux[sig_y[i]] = cell_int_t(cell, i);
+			}
+			if (cell->type == "$dff")
+				dff_cells.push_back(cell);
+			for (auto conn : cell->connections()) {
+				if (ct.cell_output(cell->type, conn.first))
+					continue;
+				for (auto bit : sigmap(conn.second))
+					bitusers[bit]++;
+			}
+		}
+	}
+
+	patterns_t find_muxtree_feedback_patterns(RTLIL::SigBit d, RTLIL::SigBit q, pattern_t path)
+	{
+		patterns_t ret;
+
+		if (d == q) {
+			ret.insert(path);
+			return ret;
+		}
+
+		if (bit2mux.count(d) == 0 || bitusers[d] > 1)
+			return ret;
+
+		cell_int_t mux_cell_int = bit2mux.at(d);
+		RTLIL::SigSpec sig_a = sigmap(mux_cell_int.first->getPort("\\A"));
+		RTLIL::SigSpec sig_b = sigmap(mux_cell_int.first->getPort("\\B"));
+		RTLIL::SigSpec sig_s = sigmap(mux_cell_int.first->getPort("\\S"));
+		int width = GetSize(sig_a), index = mux_cell_int.second;
+
+		for (int i = 0; i < GetSize(sig_s); i++)
+			if (path.count(sig_s[i]) && path.at(sig_s[i]))
+			{
+				ret = find_muxtree_feedback_patterns(sig_b[i*width + index], q, path);
+
+				if (sig_b[i*width + index] == q) {
+					RTLIL::SigSpec s = mux_cell_int.first->getPort("\\B");
+					s[i*width + index] = RTLIL::Sx;
+					mux_cell_int.first->setPort("\\B", s);
+				}
+
+				return ret;
+			}
+
+		pattern_t path_else = path;
+
+		for (int i = 0; i < GetSize(sig_s); i++)
+		{
+			if (path.count(sig_s[i]))
+				continue;
+
+			pattern_t path_this = path;
+			path_else[sig_s[i]] = false;
+			path_this[sig_s[i]] = true;
+
+			for (auto &pat : find_muxtree_feedback_patterns(sig_b[i*width + index], q, path_this))
+				ret.insert(pat);
+
+			if (sig_b[i*width + index] == q) {
+				RTLIL::SigSpec s = mux_cell_int.first->getPort("\\B");
+				s[i*width + index] = RTLIL::Sx;
+				mux_cell_int.first->setPort("\\B", s);
+			}
+		}
+
+		for (auto &pat : find_muxtree_feedback_patterns(sig_a[index], q, path_else))
+			ret.insert(pat);
+
+		if (sig_a[index] == q) {
+			RTLIL::SigSpec s = mux_cell_int.first->getPort("\\A");
+			s[index] = RTLIL::Sx;
+			mux_cell_int.first->setPort("\\A", s);
+		}
+
+		return ret;
+	}
+
+	void simplify_patterns(patterns_t&)
+	{
+		// TBD
+	}
+
+	RTLIL::SigSpec make_patterns_logic(patterns_t patterns)
+	{
+		RTLIL::SigSpec or_input;
+		for (auto pat : patterns) {
+			RTLIL::SigSpec s1, s2;
+			for (auto it : pat) {
+				s1.append(it.first);
+				s2.append(it.second);
+			}
+			or_input.append(module->Ne(NEW_ID, s1, s2));
+		}
+		if (GetSize(or_input) == 0)
+			return RTLIL::S1;
+		if (GetSize(or_input) == 1)
+			return or_input;
+		return module->ReduceOr(NEW_ID, or_input);
+	}
+
+	void handle_dff_cell(RTLIL::Cell *dff_cell)
+	{
+		RTLIL::SigSpec sig_d = sigmap(dff_cell->getPort("\\D"));
+		RTLIL::SigSpec sig_q = sigmap(dff_cell->getPort("\\Q"));
+
+		std::map<patterns_t, std::set<int>> grouped_patterns;
+		std::set<int> remaining_indices;
+
+		for (int i = 0 ; i < GetSize(sig_d); i++) {
+			patterns_t patterns = find_muxtree_feedback_patterns(sig_d[i], sig_q[i], pattern_t());
+			if (!patterns.empty()) {
+				simplify_patterns(patterns);
+				grouped_patterns[patterns].insert(i);
+			} else
+				remaining_indices.insert(i);
+		}
+
+		for (auto &it : grouped_patterns) {
+			RTLIL::SigSpec new_sig_d, new_sig_q;
+			for (int i : it.second) {
+				new_sig_d.append(sig_d[i]);
+				new_sig_q.append(sig_q[i]);
+			}
+			RTLIL::Cell *new_cell = module->addDffe(NEW_ID, dff_cell->getPort("\\CLK"), make_patterns_logic(it.first),
+					new_sig_d, new_sig_q, dff_cell->getParam("\\CLK_POLARITY").as_bool(), true);
+			log("  created $dffe cell %s for %s -> %s.\n", log_id(new_cell), log_signal(new_sig_d), log_signal(new_sig_q));
+		}
+
+		if (remaining_indices.empty()) {
+			log("  removing now obsolete cell %s.\n", log_id(dff_cell));
+			module->remove(dff_cell);
+		} else if (GetSize(remaining_indices) != GetSize(sig_d)) {
+			log("  removing %d now obsolete bits from cell %s.\n", GetSize(sig_d) - GetSize(remaining_indices), log_id(dff_cell));
+			RTLIL::SigSpec new_sig_d, new_sig_q;
+			for (int i : remaining_indices) {
+				new_sig_d.append(sig_d[i]);
+				new_sig_q.append(sig_q[i]);
+			}
+			dff_cell->setPort("\\D", new_sig_d);
+			dff_cell->setPort("\\Q", new_sig_q);
+			dff_cell->setParam("\\WIDTH", GetSize(remaining_indices));
+		}
 	}
 
 	void run()
 	{
 		log("Transforming $dff to $dffe cells in module %s:\n", log_id(module));
+		for (auto dff_cell : dff_cells)
+			handle_dff_cell(dff_cell);
 	}
 };
 
@@ -47,7 +212,7 @@ struct Dff2dffePass : public Pass {
 		log("    dff2dffe [selection]\n");
 		log("\n");
 		log("This pass transforms $dff cells driven by a tree of multiplexers with one or\n");
-		log("more feedback paths to a $dffe cells.\n");
+		log("more feedback paths to $dffe cells.\n");
 		log("\n");
 	}
 	virtual void execute(std::vector<std::string> args, RTLIL::Design *design)