Add first draft of simple C back-end

6 files changed, 623 insertions, 0 deletions

diff --git a/backends/simplec/.gitignore b/backends/simplec/.gitignore
new file mode 100644
index 000000000..f08796168
--- /dev/null
+++ b/backends/simplec/.gitignore
@@ -0,0 +1,2 @@
+test00_tb
+test00_uut.c
diff --git a/backends/simplec/Makefile.inc b/backends/simplec/Makefile.inc
new file mode 100644
index 000000000..fee1376c5
--- /dev/null
+++ b/backends/simplec/Makefile.inc
@@ -0,0 +1,3 @@
+
+OBJS += backends/simplec/simplec.o
+
diff --git a/backends/simplec/simplec.cc b/backends/simplec/simplec.cc
new file mode 100644
index 000000000..3fd28fefe
--- /dev/null
+++ b/backends/simplec/simplec.cc
@@ -0,0 +1,521 @@
+/*
+ *  yosys -- Yosys Open SYnthesis Suite
+ *
+ *  Copyright (C) 2012  Clifford Wolf <clifford@clifford.at>
+ *
+ *  Permission to use, copy, modify, and/or distribute this software for any
+ *  purpose with or without fee is hereby granted, provided that the above
+ *  copyright notice and this permission notice appear in all copies.
+ *
+ *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ *  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ *  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ *  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ *  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ */
+
+#include "kernel/yosys.h"
+#include "kernel/sigtools.h"
+
+USING_YOSYS_NAMESPACE
+PRIVATE_NAMESPACE_BEGIN
+
+struct HierDirtyFlags;
+
+struct HierDirtyFlags
+{
+	int dirty;
+	Module *module;
+	IdString hiername;
+	HierDirtyFlags *parent;
+	pool<SigBit> dirty_bits;
+	pool<Cell*> dirty_cells;
+	dict<IdString, HierDirtyFlags*> children;
+
+	HierDirtyFlags(Module *module, IdString hiername, HierDirtyFlags *parent) : dirty(0), module(module), hiername(hiername), parent(parent)
+	{
+		for (Cell *cell : module->cells()) {
+			Module *mod = module->design->module(cell->type);
+			if (mod) children[cell->name] = new HierDirtyFlags(mod, cell->name, this);
+		}
+	}
+
+	~HierDirtyFlags()
+	{
+		for (auto &child : children)
+			delete child.second;
+	}
+
+	void set_dirty(SigBit bit)
+	{
+		if (dirty_bits.count(bit))
+			return;
+
+		dirty_bits.insert(bit);
+
+		HierDirtyFlags *p = this;
+		while (p != nullptr) {
+			p->dirty++;
+			p = p->parent;
+		}
+	}
+
+	void unset_dirty(SigBit bit)
+	{
+		if (dirty_bits.count(bit) == 0)
+			return;
+
+		dirty_bits.erase(bit);
+
+		HierDirtyFlags *p = this;
+		while (p != nullptr) {
+			p->dirty--;
+			log_assert(p->dirty >= 0);
+			p = p->parent;
+		}
+	}
+
+	void set_dirty(Cell *cell)
+	{
+		if (dirty_cells.count(cell))
+			return;
+
+		dirty_cells.insert(cell);
+
+		HierDirtyFlags *p = this;
+		while (p != nullptr) {
+			p->dirty++;
+			p = p->parent;
+		}
+	}
+
+	void unset_dirty(Cell *cell)
+	{
+		if (dirty_cells.count(cell) == 0)
+			return;
+
+		dirty_cells.erase(cell);
+
+		HierDirtyFlags *p = this;
+		while (p != nullptr) {
+			p->dirty--;
+			log_assert(p->dirty >= 0);
+			p = p->parent;
+		}
+	}
+};
+
+struct SimplecWorker
+{
+	bool verbose = false;
+	int max_uintsize = 32;
+
+	Design *design;
+	dict<Module*, SigMap> sigmaps;
+	HierDirtyFlags *dirty_flags = nullptr;
+
+	vector<string> signal_declarations;
+	pool<int> generated_sigtypes;
+
+	vector<string> util_declarations;
+	pool<string> generated_utils;
+
+	vector<string> struct_declarations;
+	pool<IdString> generated_structs;
+
+	vector<string> funct_declarations;
+
+	pool<string> reserved_cids;
+	dict<IdString, string> id2cid;
+
+	dict<Module*, dict<SigBit, pool<tuple<Cell*, IdString, int>>>> bit2cell;
+	dict<Module*, dict<SigBit, pool<SigBit>>> bit2output;
+
+	SimplecWorker(Design *design) : design(design)
+	{
+	}
+
+	string sigtype(int n)
+	{
+		string struct_name = stringf("signal%d_t", n);
+
+		if (generated_sigtypes.count(n) == 0)
+		{
+			signal_declarations.push_back("");
+			signal_declarations.push_back(stringf("#ifndef YOSYS_SIMPLEC_SIGNAL%d_T", n));
+			signal_declarations.push_back(stringf("#define YOSYS_SIMPLEC_SIGNAL%d_T", n));
+			signal_declarations.push_back(stringf("typedef struct {"));
+
+			for (int k = 8; k <= max_uintsize; k = 2*k)
+				if (n <= k && k <= max_uintsize) {
+					signal_declarations.push_back(stringf("  uint%d_t value_%d_0 : %d;", k, n-1, n));
+					goto end_struct;
+				}
+
+			for (int k = 0; k < n; k += max_uintsize) {
+				int bits = std::min(max_uintsize, n-k);
+				signal_declarations.push_back(stringf("  uint%d_t value_%d_%d : %d;", max_uintsize, k+bits-1, k, bits));
+			}
+
+		end_struct:
+			signal_declarations.push_back(stringf("} signal%d_t;", n));
+			signal_declarations.push_back(stringf("#endif"));
+			generated_sigtypes.insert(n);
+		}
+
+		return struct_name;
+	}
+
+	void util_ifdef_guard(string s)
+	{
+		for (int i = 0; i < GetSize(s); i++)
+			if ('a' <= s[i] && s[i] <= 'z')
+				s[i] -= 'a' - 'A';
+
+		util_declarations.push_back(stringf("#ifndef %s", s.c_str()));
+		util_declarations.push_back(stringf("#define %s", s.c_str()));
+	}
+
+	string util_get_bit(int n, int idx)
+	{
+		string util_name = stringf("yosys_simplec_get_bit_%d_of_%d", idx, n);
+
+		if (generated_utils.count(util_name) == 0)
+		{
+			util_ifdef_guard(util_name);
+			util_declarations.push_back(stringf("bool %s(const %s *sig)", util_name.c_str(), sigtype(n).c_str()));
+			util_declarations.push_back(stringf("{"));
+
+			int word_idx = idx / max_uintsize, word_offset = idx % max_uintsize;
+			string value_name = stringf("value_%d_%d", std::min(n-1, (word_idx+1)*max_uintsize-1), word_idx*max_uintsize);
+
+			util_declarations.push_back(stringf("  return (sig->%s >> %d) & 1;", value_name.c_str(), word_offset));
+
+			util_declarations.push_back(stringf("}"));
+			util_declarations.push_back(stringf("#endif"));
+			generated_utils.insert(util_name);
+		}
+
+		return util_name;
+	}
+
+	string util_set_bit(int n, int idx)
+	{
+		string util_name = stringf("yosys_simplec_set_bit_%d_of_%d", idx, n);
+
+		if (generated_utils.count(util_name) == 0)
+		{
+			util_ifdef_guard(util_name);
+			util_declarations.push_back(stringf("void %s(%s *sig, bool value)", util_name.c_str(), sigtype(n).c_str()));
+			util_declarations.push_back(stringf("{"));
+
+			int word_idx = idx / max_uintsize, word_offset = idx % max_uintsize;
+			string value_name = stringf("value_%d_%d", std::min(n-1, (word_idx+1)*max_uintsize-1), word_idx*max_uintsize);
+
+			util_declarations.push_back(stringf("  if (value)"));
+			util_declarations.push_back(stringf("    sig->%s |= 1UL << %d;", value_name.c_str(), word_offset));
+			util_declarations.push_back(stringf("  else"));
+			util_declarations.push_back(stringf("    sig->%s &= ~(1UL << %d);", value_name.c_str(), word_offset));
+
+			util_declarations.push_back(stringf("}"));
+			util_declarations.push_back(stringf("#endif"));
+			generated_utils.insert(util_name);
+		}
+
+		return util_name;
+	}
+
+	string cid(IdString id)
+	{
+		if (id2cid.count(id) == 0)
+		{
+			string s = id.str();
+			if (GetSize(s) < 2) log_abort();
+
+			if (s[0] == '\\')
+				s = s.substr(1);
+
+			if ('0' <= s[0] && s[0] <= '9') {
+				s = "_" + s;
+			}
+
+			for (int i = 0; i < GetSize(s); i++) {
+				if ('0' <= s[i] && s[i] <= '9') continue;
+				if ('A' <= s[i] && s[i] <= 'Z') continue;
+				if ('a' <= s[i] && s[i] <= 'z') continue;
+				s[i] = '_';
+			}
+
+			while (reserved_cids.count(s))
+				s += "_";
+
+			reserved_cids.insert(s);
+			id2cid[id] = s;
+		}
+
+		return id2cid.at(id);
+	}
+
+	void create_module_struct(Module *mod)
+	{
+		if (generated_structs.count(mod->name))
+			return;
+
+		generated_structs.insert(mod->name);
+		sigmaps[mod].set(mod);
+
+		for (Wire *w : mod->wires())
+		{
+			if (w->port_output)
+				for (auto bit : SigSpec(w))
+					bit2output[mod][sigmaps.at(mod)(bit)].insert(bit);
+		}
+
+		for (Cell *c : mod->cells())
+		{
+			for (auto &conn : c->connections())
+			{
+				if (!c->input(conn.first))
+					continue;
+
+				int idx = 0;
+				for (auto bit : sigmaps.at(mod)(conn.second))
+					bit2cell[mod][bit].insert(tuple<Cell*, IdString, int>(c, conn.first, idx++));
+			}
+
+			if (design->module(c->type))
+				create_module_struct(design->module(c->type));
+		}
+
+		struct_declarations.push_back("");
+		struct_declarations.push_back(stringf("struct %s_state_t {", cid(mod->name).c_str()));
+
+		for (Wire *w : mod->wires())
+			struct_declarations.push_back(stringf("  %s %s; // %s", sigtype(w->width).c_str(), cid(w->name).c_str(), log_id(w)));
+
+		for (Cell *c : mod->cells())
+			if (design->module(c->type))
+				struct_declarations.push_back(stringf("  struct %s_state_t %s; // %s", cid(c->type).c_str(), cid(c->name).c_str(), log_id(c)));
+
+		struct_declarations.push_back(stringf("};"));
+	}
+
+	void eval_cell(HierDirtyFlags *work, string &prefix, string &/* log_prefix */, Cell *cell)
+	{
+		if (cell->type.in("$_AND_", "$_NAND_", "$_OR_", "$_NOR_", "$_XOR_", "$_XNOR"))
+		{
+			SigBit a = sigmaps.at(work->module)(cell->getPort("\\A"));
+			SigBit b = sigmaps.at(work->module)(cell->getPort("\\B"));
+			SigBit y = sigmaps.at(work->module)(cell->getPort("\\Y"));
+
+			string a_expr = a.wire ? stringf("%s(&%s)", util_get_bit(a.wire->width, a.offset).c_str(), (prefix + cid(a.wire->name)).c_str()) : a.data ? "1" : "0";
+			string b_expr = b.wire ? stringf("%s(&%s)", util_get_bit(b.wire->width, b.offset).c_str(), (prefix + cid(b.wire->name)).c_str()) : b.data ? "1" : "0";
+			string expr;
+
+			if (cell->type == "$_AND_")  expr = stringf("%s & %s",    a_expr.c_str(), b_expr.c_str());
+			if (cell->type == "$_NAND_") expr = stringf("!(%s & %s)", a_expr.c_str(), b_expr.c_str());
+			if (cell->type == "$_OR_")   expr = stringf("%s | %s",    a_expr.c_str(), b_expr.c_str());
+			if (cell->type == "$_NOR_")  expr = stringf("!(%s | %s)", a_expr.c_str(), b_expr.c_str());
+			if (cell->type == "$_XOR_")  expr = stringf("%s ^ %s",    a_expr.c_str(), b_expr.c_str());
+			if (cell->type == "$_XNOR_") expr = stringf("!(%s ^ %s)", a_expr.c_str(), b_expr.c_str());
+
+			log_assert(y.wire);
+			funct_declarations.push_back(stringf("  %s(&%s, %s); // %s (%s)", util_set_bit(y.wire->width, y.offset).c_str(),
+					(prefix + cid(y.wire->name)).c_str(), expr.c_str(), log_id(cell), log_id(cell->type)));
+
+			work->set_dirty(y);
+			return;
+		}
+
+		log_error("No C model for %s available at the moment (FIXME).\n", log_id(cell->type));
+	}
+
+	void eval_dirty(HierDirtyFlags *work, string prefix, string log_prefix, string parent_prefix)
+	{
+		while (work->dirty)
+		{
+			while (!work->dirty_bits.empty() || !work->dirty_cells.empty())
+			{
+				if (!work->dirty_bits.empty())
+				{
+					SigSpec dirtysig(work->dirty_bits);
+					dirtysig.sort_and_unify();
+
+					for (SigChunk chunk : dirtysig.chunks())
+						funct_declarations.push_back(stringf("  // New dirty bits in %s: %s", log_prefix.c_str(), log_signal(chunk)));
+
+					for (SigBit bit : dirtysig)
+					{
+						if (bit2output[work->module].count(bit) && work->parent)
+							for (auto outbit : bit2output[work->module][bit])
+							{
+								Module *parent_mod = work->parent->module;
+								Cell *parent_cell = parent_mod->cell(work->hiername);
+
+								IdString port_name = outbit.wire->name;
+								int port_offset = outbit.offset;
+								SigBit parent_bit = sigmaps.at(parent_mod)(parent_cell->getPort(port_name)[port_offset]);
+
+								log_assert(bit.wire && parent_bit.wire);
+								funct_declarations.push_back(stringf("  %s(&%s, %s(&%s));",
+										util_set_bit(parent_bit.wire->width, parent_bit.offset).c_str(),
+										(parent_prefix + cid(parent_bit.wire->name)).c_str(),
+										util_get_bit(bit.wire->width, bit.offset).c_str(),
+										(prefix + cid(bit.wire->name)).c_str()));
+								work->parent->set_dirty(parent_bit);
+							}
+
+						for (auto &port : bit2cell[work->module][bit])
+						{
+							if (work->children.count(std::get<0>(port)->name)) {
+								HierDirtyFlags *child = work->children.at(std::get<0>(port)->name);
+								SigBit child_bit = sigmaps.at(child->module)(SigBit(child->module->wire(std::get<1>(port)), std::get<2>(port)));
+								log_assert(bit.wire && child_bit.wire);
+								funct_declarations.push_back(stringf("  %s(&%s, %s(&%s));",
+										util_set_bit(child_bit.wire->width, child_bit.offset).c_str(),
+										(prefix + cid(child->hiername) + "." + cid(child_bit.wire->name)).c_str(),
+										util_get_bit(bit.wire->width, bit.offset).c_str(),
+										(prefix + cid(bit.wire->name)).c_str()));
+								child->set_dirty(child_bit);
+							} else {
+								work->set_dirty(std::get<0>(port));
+							}
+						}
+						work->unset_dirty(bit);
+					}
+				}
+
+				if (!work->dirty_cells.empty())
+				{
+					Cell *cell = *work->dirty_cells.begin();
+					eval_cell(work, prefix, log_prefix, cell);
+					work->unset_dirty(cell);
+				}
+			}
+
+			for (auto &child : work->children)
+				eval_dirty(child.second, prefix + cid(child.first) + ".", log_prefix + "." + cid(child.first), prefix);
+		}
+	}
+
+	void run(Module *mod)
+	{
+		create_module_struct(mod);
+
+		dirty_flags = new HierDirtyFlags(mod, IdString(), nullptr);
+
+		funct_declarations.push_back("");
+		funct_declarations.push_back(stringf("void %s_init(struct %s_state_t *state)", cid(mod->name).c_str(), cid(mod->name).c_str()));
+		funct_declarations.push_back("{");
+		funct_declarations.push_back("}");
+
+		funct_declarations.push_back("");
+		funct_declarations.push_back(stringf("void %s_eval(struct %s_state_t *state)", cid(mod->name).c_str(), cid(mod->name).c_str()));
+		funct_declarations.push_back("{");
+
+		for (Wire *w : mod->wires()) {
+			if (w->port_input)
+				for (SigBit bit : sigmaps.at(mod)(w))
+					dirty_flags->set_dirty(bit);
+		}
+
+		eval_dirty(dirty_flags, "state->", log_id(mod), "");
+
+		funct_declarations.push_back("}");
+
+		funct_declarations.push_back("");
+		funct_declarations.push_back(stringf("void %s_tick(struct %s_state_t *state)", cid(mod->name).c_str(), cid(mod->name).c_str()));
+		funct_declarations.push_back("{");
+		funct_declarations.push_back("}");
+
+		delete dirty_flags;
+		dirty_flags = nullptr;
+	}
+
+	void write(std::ostream &f)
+	{
+		f << "#include <stdint.h>" << std::endl;
+		f << "#include <stdbool.h>" << std::endl;
+
+		for (auto &line : signal_declarations)
+			f << line << std::endl;
+
+		for (auto &line : util_declarations)
+			f << line << std::endl;
+
+		for (auto &line : struct_declarations)
+			f << line << std::endl;
+
+		for (auto &line : funct_declarations)
+			f << line << std::endl;
+	}
+};
+
+struct SimplecBackend : public Backend {
+	SimplecBackend() : Backend("simplec", "convert design to simple C code") { }
+	virtual void help()
+	{
+		//   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
+		log("\n");
+		log("    write_simplec [options] [filename]\n");
+		log("\n");
+		log("Write simple C code for simulating the design. The C code writen can be used to\n");
+		log("simulate the design in a C environment, but the purpose of this command is to\n");
+		log("generate code that works well with C-based formal verification.\n");
+		log("\n");
+		log("    -verbose\n");
+		log("        this will print the recursive walk used to export the modules.\n");
+		log("\n");
+		log("    -i8, -i16, -i32, -i64\n");
+		log("        set the maximum integer bit width to use in the generated code.\n");
+		log("\n");
+		log("THIS COMMAND IS UNDER CONSTRUCTION\n");
+		log("\n");
+	}
+	virtual void execute(std::ostream *&f, std::string filename, std::vector<std::string> args, RTLIL::Design *design)
+	{
+		SimplecWorker worker(design);
+
+		log_header(design, "Executing SIMPLEC backend.\n");
+
+		size_t argidx;
+		for (argidx = 1; argidx < args.size(); argidx++)
+		{
+			if (args[argidx] == "-verbose") {
+				worker.verbose = true;
+				continue;
+			}
+			if (args[argidx] == "-i8") {
+				worker.max_uintsize = 8;
+				continue;
+			}
+			if (args[argidx] == "-i16") {
+				worker.max_uintsize = 16;
+				continue;
+			}
+			if (args[argidx] == "-i32") {
+				worker.max_uintsize = 32;
+				continue;
+			}
+			if (args[argidx] == "-i64") {
+				worker.max_uintsize = 64;
+				continue;
+			}
+			break;
+		}
+		extra_args(f, filename, args, argidx);
+
+		Module *topmod = design->top_module();
+
+		if (topmod == nullptr)
+			log_error("Current design has no top module.\n");
+
+		worker.run(topmod);
+		worker.write(*f);
+	}
+} SimplecBackend;
+
+PRIVATE_NAMESPACE_END
diff --git a/backends/simplec/test00.sh b/backends/simplec/test00.sh
new file mode 100644
index 000000000..6a7560da0
--- /dev/null
+++ b/backends/simplec/test00.sh
@@ -0,0 +1,5 @@
+#!/bin/bash
+set -ex
+../../yosys -p 'synth -top test; write_simplec -i8 test00_uut.c' test00_uut.v
+clang -o test00_tb test00_tb.c
+./test00_tb
diff --git a/backends/simplec/test00_tb.c b/backends/simplec/test00_tb.c
new file mode 100644
index 000000000..650f121ca
--- /dev/null
+++ b/backends/simplec/test00_tb.c
@@ -0,0 +1,78 @@
+#include <stdio.h>
+#include <assert.h>
+#include "test00_uut.c"
+
+uint32_t xorshift32()
+{
+	static uint32_t x32 = 314159265;
+	x32 ^= x32 << 13;
+	x32 ^= x32 >> 17;
+	x32 ^= x32 << 5;
+	return x32;
+}
+
+int main()
+{
+	struct test_state_t state;
+	uint32_t a, b, c, x, y, z;
+
+	for (int i = 0; i < 100; i++)
+	{
+		a = xorshift32();
+		b = xorshift32();
+		c = xorshift32();
+
+		x = (a & b) | c;
+		y = a & (b | c);
+		z = a ^ b ^ c;
+
+		state.a.value_7_0   = a;
+		state.a.value_15_8  = a >> 8;
+		state.a.value_23_16 = a >> 16;
+		state.a.value_31_24 = a >> 24;
+
+		state.b.value_7_0   = b;
+		state.b.value_15_8  = b >> 8;
+		state.b.value_23_16 = b >> 16;
+		state.b.value_31_24 = b >> 24;
+
+		state.c.value_7_0   = c;
+		state.c.value_15_8  = c >> 8;
+		state.c.value_23_16 = c >> 16;
+		state.c.value_31_24 = c >> 24;
+
+		test_eval(&state);
+
+		uint32_t uut_x = 0;
+		uut_x |= (uint32_t)state.x.value_7_0;
+		uut_x |= (uint32_t)state.x.value_15_8  << 8;
+		uut_x |= (uint32_t)state.x.value_23_16 << 16;
+		uut_x |= (uint32_t)state.x.value_31_24 << 24;
+
+		uint32_t uut_y = 0;
+		uut_y |= (uint32_t)state.y.value_7_0;
+		uut_y |= (uint32_t)state.y.value_15_8  << 8;
+		uut_y |= (uint32_t)state.y.value_23_16 << 16;
+		uut_y |= (uint32_t)state.y.value_31_24 << 24;
+
+		uint32_t uut_z = 0;
+		uut_z |= (uint32_t)state.z.value_7_0;
+		uut_z |= (uint32_t)state.z.value_15_8  << 8;
+		uut_z |= (uint32_t)state.z.value_23_16 << 16;
+		uut_z |= (uint32_t)state.z.value_31_24 << 24;
+
+		printf("---\n");
+		printf("A: 0x%08x\n", a);
+		printf("B: 0x%08x\n", b);
+		printf("C: 0x%08x\n", c);
+		printf("X: 0x%08x 0x%08x\n", x, uut_x);
+		printf("Y: 0x%08x 0x%08x\n", y, uut_y);
+		printf("Z: 0x%08x 0x%08x\n", z, uut_z);
+
+		assert(x == uut_x);
+		assert(y == uut_y);
+		assert(z == uut_z);
+	}
+
+	return 0;
+}
diff --git a/backends/simplec/test00_uut.v b/backends/simplec/test00_uut.v
new file mode 100644
index 000000000..fd634cf82
--- /dev/null
+++ b/backends/simplec/test00_uut.v
@@ -0,0 +1,14 @@
+module test(input [31:0] a, b, c, output [31:0] x, y, z);
+  unit_x unit_x_inst (.a(a), .b(b), .c(c), .x(x));
+  unit_y unit_y_inst (.a(a), .b(b), .c(c), .y(y));
+  assign z = a ^ b ^ c;
+endmodule
+  
+module unit_x(input [31:0] a, b, c, output [31:0] x);
+  assign x = (a & b) | c;
+endmodule
+  
+module unit_y(input [31:0] a, b, c, output [31:0] y);
+  assign y = a & (b | c);
+endmodule
+