From 2b6d00e9ff2153a3cd5d03bd92d6777814eb6897 Mon Sep 17 00:00:00 2001
From: David Given <dg@cowlark.com>
Date: Sat, 17 Dec 2016 22:25:26 +0100
Subject: [PATCH] Add a bitmap library to modules/src/data; mcgg now computers
 register bitmaps.

---
 modules/src/data/bitmap.c | 61 +++++++++++++++++++++++++++++++++
 modules/src/data/bitmap.h | 16 +++++++++
 util/mcgg/build.lua       |  3 +-
 util/mcgg/iburg.c         |  2 +-
 util/mcgg/iburg.h         |  3 +-
 util/mcgg/mcgg.h          | 19 ++---------
 util/mcgg/mcgg_common.h   | 21 ++++++++++++
 util/mcgg/registers.c     | 72 ++++++++++++++++++++++++++++++++++++---
 util/mcgg/registers.h     |  3 ++
 9 files changed, 175 insertions(+), 25 deletions(-)
 create mode 100644 modules/src/data/bitmap.c
 create mode 100644 modules/src/data/bitmap.h
 create mode 100644 util/mcgg/mcgg_common.h

diff --git a/modules/src/data/bitmap.c b/modules/src/data/bitmap.c
new file mode 100644
index 000000000..363d22d49
--- /dev/null
+++ b/modules/src/data/bitmap.c
@@ -0,0 +1,61 @@
+#include <stdlib.h>
+#include <stdbool.h>
+#include <strings.h>
+#include <assert.h>
+#include "bitmap.h"
+
+unsigned int* bitmap_alloc(int size)
+{
+	return calloc(WORDS_FOR_BITMAP_SIZE(size), sizeof(unsigned int));
+}
+
+void bitmap_set(unsigned int* bitmap, int size, int bit)
+{
+	int word = bit / BITS_PER_WORD;
+	bit = bit & (BITS_PER_WORD - 1);
+
+	assert((bit >= 0) && (bit < size));
+	bitmap[word] |= 1<<bit;
+}
+
+bool bitmap_get(unsigned int* bitmap, int size, int bit)
+{
+	int word = bit / BITS_PER_WORD;
+	bit = bit & (BITS_PER_WORD - 1);
+
+	assert((bit >= 0) && (bit < size));
+	return bitmap[word] & (1<<bit);
+}
+
+int bitmap_findfirst(unsigned int* bitmap, int size)
+{
+	int word;
+
+	for (word=0; word<WORDS_FOR_BITMAP_SIZE(size); word++)
+	{
+		unsigned int w = bitmap[word];
+		if (w)
+			return ffs(w) + word*BITS_PER_WORD;
+	}
+
+	return -1;
+}
+
+void bitmap_and(unsigned int* dest, int size, unsigned int* src)
+{
+	int word;
+	int words = ((size-1) / BITS_PER_WORD) + 1;
+
+	for (word=0; word<words; word++)
+		dest[word] &= src[word];
+}
+
+void bitmap_or(unsigned int* dest, int size, unsigned int* src)
+{
+	int word;
+	int words = ((size-1) / BITS_PER_WORD) + 1;
+
+	for (word=0; word<words; word++)
+		dest[word] |= src[word];
+}
+
diff --git a/modules/src/data/bitmap.h b/modules/src/data/bitmap.h
new file mode 100644
index 000000000..d3bd23603
--- /dev/null
+++ b/modules/src/data/bitmap.h
@@ -0,0 +1,16 @@
+#ifndef BITMAP_H
+#define BITMAP_H
+
+extern unsigned int* bitmap_alloc(int size);
+
+extern void bitmap_set(unsigned int* bitmap, int size, int bit);
+extern bool bitmap_get(unsigned int* bitmap, int size, int bit);
+extern int bitmap_findfirst(unsigned int* bitmap, int size);
+extern void bitmap_and(unsigned int* dest, int size, unsigned int* src);
+extern void bitmap_or(unsigned int* dest, int size, unsigned int* src);
+
+#define BITS_PER_WORD (sizeof(unsigned int)*8)
+#define WORDS_FOR_BITMAP_SIZE(n) (((n-1) / BITS_PER_WORD) + 1)
+
+#endif
+
diff --git a/util/mcgg/build.lua b/util/mcgg/build.lua
index 955536998..1bd242a10 100644
--- a/util/mcgg/build.lua
+++ b/util/mcgg/build.lua
@@ -34,7 +34,8 @@ clibrary {
 	hdrs = {
 		matching(filenamesof("+ircodes"), "%.h$"),
 		"./ircodes.h",
-		"./mcgg.h"
+		"./mcgg.h",
+		"./mcgg_common.h",
 	},
 }
 
diff --git a/util/mcgg/iburg.c b/util/mcgg/iburg.c
index 75f6b267f..8b5e2cccc 100644
--- a/util/mcgg/iburg.c
+++ b/util/mcgg/iburg.c
@@ -14,7 +14,6 @@
 #include "ircodes.h"
 #include "astring.h"
 #include "smap.h"
-#include "mcgg.h"
 #include "registers.h"
 
 static char rcsid[] = "$Id$";
@@ -160,6 +159,7 @@ int main(int argc, char* argv[])
 	yyin = infp;
 	yyparse();
 
+	analyse_registers();
 	emitregisterattrs();
 	emitregisters();
 	emitdefs(nts, ntnumber);
diff --git a/util/mcgg/iburg.h b/util/mcgg/iburg.h
index 961beca33..f9ea1efb1 100644
--- a/util/mcgg/iburg.h
+++ b/util/mcgg/iburg.h
@@ -4,6 +4,7 @@
 #include "em_arith.h"
 #include "stringlist.h"
 #include "array.h"
+#include "mcgg_common.h"
 
 extern char* stringf(char* fmt, ...);
 
@@ -136,6 +137,4 @@ extern void print(const char* fmt, ...);
 extern void printh(const char* fmt, ...);
 extern void printlineno(void);
 
-#include "mcgg.h"
-
 #endif
diff --git a/util/mcgg/mcgg.h b/util/mcgg/mcgg.h
index fdfc2c598..e4baa7cf7 100644
--- a/util/mcgg/mcgg.h
+++ b/util/mcgg/mcgg.h
@@ -1,16 +1,7 @@
 #ifndef MCGG_H
 #define MCGG_H
 
-/* Excruciating macro which packs ir opcodes and sizes into an int for iburg's benefit.
- *
- * Types are mapped to: I=1, F=2, L=3, D=4
- */
-#define ir_to_esn(iropcode, type) \
-	((iropcode)*5 + \
-		(((type) == 'I') ? 1 : \
-		 ((type) == 'F') ? 2 : \
-		 ((type) == 'L') ? 3 : \
-         ((type) == 'D') ? 4 : 0))
+#include "mcgg_common.h"
 
 #define STATE_TYPE void*
 
@@ -36,8 +27,6 @@ extern const short *burm_nts[];
 extern NODEPTR_TYPE* burm_kids(NODEPTR_TYPE p, int eruleno, NODEPTR_TYPE kids[]);
 extern void burm_trace(NODEPTR_TYPE p, int ruleno, int cost, int bestcost);
 
-extern void yyerror(char *fmt, ...);
-
 struct burm_emitter_data
 {
     void (*emit_string)(const char* data);
@@ -70,16 +59,12 @@ struct burm_register_data
     uint32_t attrs;
     const char** names;
     const struct burm_register_data** aliases;
+    burm_register_bitmap_t bitmap;
 };
 
 extern const struct burm_register_data burm_register_data[];
 extern const char* burm_register_class_names[];
 
-enum
-{
-    NONTERM_STMT = 1
-};
-
 #endif
 
 /* vim: set sw=4 ts=4 expandtab : */
diff --git a/util/mcgg/mcgg_common.h b/util/mcgg/mcgg_common.h
new file mode 100644
index 000000000..09bc86d83
--- /dev/null
+++ b/util/mcgg/mcgg_common.h
@@ -0,0 +1,21 @@
+#ifndef MCGG_COMMON_H
+#define MCGG_COMMON_H
+
+/* Excruciating macro which packs ir opcodes and sizes into an int for iburg's benefit.
+ *
+ * Types are mapped to: I=1, F=2, L=3, D=4
+ */
+#define ir_to_esn(iropcode, type) \
+	((iropcode)*5 + \
+		(((type) == 'I') ? 1 : \
+		 ((type) == 'F') ? 2 : \
+		 ((type) == 'L') ? 3 : \
+         ((type) == 'D') ? 4 : 0))
+
+enum
+{
+    NONTERM_STMT = 1
+};
+
+#endif
+
diff --git a/util/mcgg/registers.c b/util/mcgg/registers.c
index b35a6f940..f8ca3d116 100644
--- a/util/mcgg/registers.c
+++ b/util/mcgg/registers.c
@@ -3,7 +3,6 @@
 #include <stdint.h>
 #include <stdbool.h>
 #include <assert.h>
-#include "mcgg.h"
 #include "registers.h"
 #include "smap.h"
 #include "array.h"
@@ -11,10 +10,17 @@
 #include "iburg.h"
 #include "registers.h"
 #include "hashtable.h"
+#include "bitmap.h"
 
 static struct hashtable registers = HASHTABLE_OF_STRINGS;
 static struct hashtable registerattrs = HASHTABLE_OF_STRINGS;
 
+static struct reg** real_registers;
+static int real_register_count;
+
+static struct reg** fake_registers;
+static int fake_register_count;
+
 struct reg* makereg(const char* id)
 {
 	struct reg* p = hashtable_get(&registers, (void*)id);
@@ -25,7 +31,6 @@ struct reg* makereg(const char* id)
 	p = calloc(1, sizeof(*p));
 	p->name = id;
 	p->number = number++;
-	array_append(&p->aliases, p);
 	hashtable_put(&registers, (void*)id, p);
 
 	return p;
@@ -89,9 +94,11 @@ void addregaliases(struct reg* reg, struct stringlist* aliases)
 		struct reg* r = hashtable_get(&registers, (void*)f->data);
 		if (!r)
 			yyerror("register '%s' is not defined here", f->data);
+		if (r->aliases.count > 0)
+			yyerror("can't alias '%s' to '%s' because the latter isn't a true hardware register",
+				reg->name, r->name);
 
 		array_appendu(&reg->aliases, r);
-		array_appendu(&r->aliases, reg);
 
 		f = f->next;
 	}
@@ -105,6 +112,56 @@ struct regattr* getregattr(const char* id)
 	return p;
 }
 
+void analyse_registers(void)
+{
+	struct reg* regs[registers.size];
+	struct hashtable_iterator hit = {};
+	int i, j;
+
+	while (hashtable_next(&registers, &hit))
+	{
+		struct reg* r = hit.value;
+		assert((r->number >= 0) && (r->number < registers.size));
+		regs[r->number] = r;
+	}
+
+	real_registers = calloc(registers.size, sizeof(struct reg*));
+	fake_registers = calloc(registers.size, sizeof(struct reg*));
+	real_register_count = 0;
+	fake_register_count = 0;
+
+	for (i=0; i<registers.size; i++)
+	{
+		struct reg* r = regs[i];
+		if (r->aliases.count > 0)
+			fake_registers[fake_register_count++] = r;
+		else
+			real_registers[real_register_count++] = r;
+	}
+
+	for (i=0; i<real_register_count; i++)
+	{
+		struct reg* r = real_registers[i];
+		r->bitmap = bitmap_alloc(real_register_count);
+		bitmap_set(r->bitmap, real_register_count, i);
+	}
+
+	for (i=0; i<fake_register_count; i++)
+	{
+		struct reg* r = fake_registers[i];
+		r->bitmap = bitmap_alloc(real_register_count);
+
+		for (j=0; j<r->aliases.count; j++)
+		{
+			struct reg* alias = r->aliases.item[j];
+			bitmap_or(r->bitmap, real_register_count, alias->bitmap);
+		}
+	}
+
+	printh("typedef unsigned int %Pregister_bitmap_t[%d];\n",
+		WORDS_FOR_BITMAP_SIZE(real_register_count));
+}
+
 void emitregisterattrs(void)
 {
 	int i;
@@ -180,8 +237,15 @@ void emitregisters(void)
 
 		assert(r->number == i);
 
-		print("%1{ \"%s\", 0x%x, %Pregister_names_%d_%s, %Pregister_aliases_%d_%s },\n",
+		print("%1{\n%2\"%s\", 0x%x, %Pregister_names_%d_%s, %Pregister_aliases_%d_%s,\n",
 			r->name, r->attrs, i, r->name, i, r->name);
+		print("%2{ ");
+		for (j=0; j<WORDS_FOR_BITMAP_SIZE(real_register_count); j++)
+		{
+			print("0x%x, ", r->bitmap[j]);
+		}
+		print("},\n");
+		print("%1},\n");
 	}
 
 	print("%1{ NULL }\n");
diff --git a/util/mcgg/registers.h b/util/mcgg/registers.h
index 51bcfc499..828ab5a2a 100644
--- a/util/mcgg/registers.h
+++ b/util/mcgg/registers.h
@@ -9,6 +9,7 @@ struct reg
 	int number;                /* identifying number */
 	uint32_t attrs;            /* bitfield of register attributes */
 	struct stringlist* names;  /* register names */
+	unsigned int* bitmap;      /* hardware register bitmap */
 	ARRAYOF(struct reg) aliases; /* registers that this one aliases */
 };
 
@@ -25,6 +26,8 @@ extern void addregattr(struct reg* reg, const char* regattr);
 extern void addregaliases(struct reg* reg, struct stringlist* aliases);
 extern struct regattr* getregattr(const char* name);
 
+extern void analyse_registers(void);
+
 extern void emitregisterattrs(void);
 extern void emitregisters(void);
 
-- 
2.34.1