From 8bf9cb407d929255ae985b33a537ac6d489553c5 Mon Sep 17 00:00:00 2001
From: =?utf8?q?Marcelina=20Ko=C5=9Bcielnicka?= <mwk@0x04.net>
Date: Mon, 12 Jul 2021 20:04:59 +0200
Subject: [PATCH] kernel/mem: Add a coalesce_inits helper.

While this helper is already useful to squash sequential initializations
into one in cxxrtl, its main purpose is to squash overlapping masked memory
initializations (when they land) and avoid having to deal with them in
cxxrtl runtime.
---
 backends/cxxrtl/cxxrtl_backend.cc |  6 ++-
 kernel/mem.cc                     | 72 +++++++++++++++++++++++++++++++
 kernel/mem.h                      |  7 +++
 3 files changed, 84 insertions(+), 1 deletion(-)

diff --git a/backends/cxxrtl/cxxrtl_backend.cc b/backends/cxxrtl/cxxrtl_backend.cc
index ddb954073..70a3add5d 100644
--- a/backends/cxxrtl/cxxrtl_backend.cc
+++ b/backends/cxxrtl/cxxrtl_backend.cc
@@ -1835,6 +1835,8 @@ struct CxxrtlWorker {
 			f << ",\n";
 			inc_indent();
 				for (auto &init : mem->inits) {
+					if (init.removed)
+						continue;
 					dump_attrs(&init);
 					int words = GetSize(init.data) / mem->width;
 					f << indent << "memory<" << mem->width << ">::init<" << words << "> { "
@@ -2488,8 +2490,10 @@ struct CxxrtlWorker {
 
 			std::vector<Mem> &memories = mod_memories[module];
 			memories = Mem::get_all_memories(module);
-			for (auto &mem : memories)
+			for (auto &mem : memories) {
 				mem.narrow();
+				mem.coalesce_inits();
+			}
 
 			if (module->get_bool_attribute(ID(cxxrtl_blackbox))) {
 				for (auto port : module->ports) {
diff --git a/kernel/mem.cc b/kernel/mem.cc
index 96f71428d..e95118d4c 100644
--- a/kernel/mem.cc
+++ b/kernel/mem.cc
@@ -282,6 +282,78 @@ void Mem::clear_inits() {
 		init.removed = true;
 }
 
+void Mem::coalesce_inits() {
+	// start address -> end address
+	std::map<int, int> chunks;
+	// Figure out chunk boundaries.
+	for (auto &init : inits) {
+		if (init.removed)
+			continue;
+		int addr = init.addr.as_int();
+		int addr_e = addr + GetSize(init.data) / width;
+		auto it_e = chunks.upper_bound(addr_e);
+		auto it = it_e;
+		while (it != chunks.begin()) {
+			--it;
+			if (it->second < addr) {
+				++it;
+				break;
+			}
+		}
+		if (it == it_e) {
+			// No overlapping inits — add this one to index.
+			chunks[addr] = addr_e;
+		} else {
+			// We have an overlap — all chunks in the [it, it_e)
+			// range will be merged with this init.
+			if (it->first < addr)
+				addr = it->first;
+			auto it_last = it_e;
+			it_last--;
+			if (it_last->second > addr_e)
+				addr_e = it_last->second;
+			chunks.erase(it, it_e);
+			chunks[addr] = addr_e;
+		}
+	}
+	// Group inits by the chunk they belong to.
+	dict<int, std::vector<int>> inits_by_chunk;
+	for (int i = 0; i < GetSize(inits); i++) {
+		auto &init = inits[i];
+		if (init.removed)
+			continue;
+		auto it = chunks.upper_bound(init.addr.as_int());
+		--it;
+		inits_by_chunk[it->first].push_back(i);
+		int addr = init.addr.as_int();
+		int addr_e = addr + GetSize(init.data) / width;
+		log_assert(addr >= it->first && addr_e <= it->second);
+	}
+	// Process each chunk.
+	for (auto &it : inits_by_chunk) {
+		int caddr = it.first;
+		int caddr_e = chunks[caddr];
+		auto &chunk_inits = it.second;
+		if (GetSize(chunk_inits) == 1) {
+			continue;
+		}
+		Const cdata(State::Sx, (caddr_e - caddr) * width);
+		for (int idx : chunk_inits) {
+			auto &init = inits[idx];
+			int offset = (init.addr.as_int() - caddr) * width;
+			log_assert(offset >= 0);
+			log_assert(offset + GetSize(init.data) <= GetSize(cdata));
+			for (int i = 0; i < GetSize(init.data); i++)
+				cdata.bits[i+offset] = init.data.bits[i];
+			init.removed = true;
+		}
+		MemInit new_init;
+		new_init.addr = caddr;
+		new_init.data = cdata;
+		inits.push_back(new_init);
+	}
+}
+
 Const Mem::get_init_data() const {
 	Const init_data(State::Sx, width * size);
 	for (auto &init : inits) {
diff --git a/kernel/mem.h b/kernel/mem.h
index 6ea18f26f..62403e00c 100644
--- a/kernel/mem.h
+++ b/kernel/mem.h
@@ -97,6 +97,13 @@ struct Mem : RTLIL::AttrObject {
 	// Marks all inits as removed.
 	void clear_inits();
 
+	// Coalesces inits: whenever two inits have overlapping or touching
+	// address ranges, they are combined into one, with the higher-priority
+	// one's data overwriting the other.  Running this results in
+	// an inits list equivalent to the original, in which all entries
+	// cover disjoint (and non-touching) address ranges.
+	void coalesce_inits();
+
 	// Checks consistency of this memory and all its ports/inits, using
 	// log_assert.
 	void check();
-- 
2.30.2