add features that make machine generation easier

9 files changed, 269 insertions, 34 deletions

diff --git a/src/abi.c b/src/abi.c
index fede365..a16ef2d 100644
--- a/src/abi.c
+++ b/src/abi.c
@@ -102,6 +102,10 @@ void abi0(struct fn *f)
 				struct insn a = rewrite_retarg(n);
 				insn_at(b->insns, i) = a;
 			}
+			else if (n.type == CALL) {
+				set_insn_flags(&n, CALL_SETUP | CALL_TEARDOWN);
+				insn_at(b->insns, i) = n;
+			}
 		}
 	}
 }
diff --git a/src/asm.c b/src/asm.c
index 7eac389..e4b65cc 100644
--- a/src/asm.c
+++ b/src/asm.c
@@ -152,12 +152,14 @@ static void restore_state(struct fn *f, FILE *o)
 	if (f->has_calls)
 		fprintf(o, "ld w ra, -%zi(fp)\n", ra_fploc());
 
-	fprintf(o, "ld w fp, -%zi(fp)\n", fp_fploc());
 	fprintf(o, "mv sp, fp\n");
+	fprintf(o, "ld w fp, -%zi(fp)\n", fp_fploc());
 }
 
 static void output_move(struct insn n, FILE *o)
 {
+	/** @todo should this also handle casts or would it make more sense to
+	 * add an insn specifically for that? */
 	if (!same_val(n.out, n.in[0]))
 		fprintf(o, "mv %s, %s\n",
 		        rname(n.out), rname(n.in[0]));
@@ -244,17 +246,69 @@ static void output_restore(struct insn n, FILE *o, struct fn *f)
 			rname(r), call_save_fploc(f, i));
 }
 
+static void output_store(struct insn n, FILE *o)
+{
+	struct val offset = n.out;
+	struct val b = n.in[0];
+	struct val t = n.in[1];
+
+	assert(offset.class == IMM);
+	assert(b.class == REG);
+	assert(t.class == REG);
+
+	char width = 'w';
+	if (n.vtype == I9)
+		width = 't';
+
+	int64_t off = offset.v;
+	fprintf(o, "st %c %s, %lli(%s)\n",
+			width, rname(t), (long long int)off, rname(b));
+}
+
+static void output_load(struct insn n, FILE *o)
+{
+	struct val t = n.out;
+	struct val b = n.in[0];
+	struct val offset = n.in[1];
+
+	assert(offset.class == IMM);
+	assert(b.class == REG);
+	assert(t.class == REG);
+
+	char width = 'w';
+	if (n.vtype == I9)
+		width = 't';
+
+	int64_t off = offset.v;
+	fprintf(o, "ld %c %s, %lli(%s)\n",
+			width, rname(t), (long long int)off, rname(b));
+}
+
+static void output_lt(struct insn i, FILE *o)
+{
+	assert(i.type == LT);
+	if (i.in[1].class == IMM)
+		fprintf(o, "slti %s, %s, %lli\n",
+				rname(i.out), rname(i.in[0]), (long long)i.in[1].v);
+	else
+		fprintf(o, "slt %s, %s, %s\n",
+				rname(i.out), rname(i.in[0]), rname(i.in[1]));
+}
+
 static void output_insn(struct insn n, FILE *o, struct fn *f)
 {
 	/* one insn directly matches one or more assembly instructions,
 	 * we may be missing out on certain optimizations by not using some kind
 	 * of matching here but good enough for now */
 	switch (n.type) {
+	case LT: output_lt(n, o); break;
 	case MOVE: output_move(n, o); break;
 	case ADD: output_add(n, o); break;
 	case SUB: output_sub(n, o); break;
 	case COPY: output_copy(n, o); break;
 	case CALL: output_call(n, o); break;
+	case STORE: output_store(n, o); break;
+	case LOAD: output_load(n, o); break;
 	case SAVE: output_save(n, o, f); break;
 	case RESTORE: output_restore(n, o, f); break;
 	default: fprintf(stderr, "unimplemented insn: %s\n", op_str(n.type));
@@ -275,7 +329,29 @@ static void output_ble(struct blk *b, struct fn *f, FILE *o)
 	assert(b->s2);
 	fprintf(o, "ble %s, %s, .%s.%lli\n",
 	        rname(b->cmp[0]), rname(b->cmp[1]),
-	        f->name, (long long int)b->s2->id);
+	        f->name, (long long)b->s2->id);
+}
+
+static void output_bne(struct blk *b, struct fn *f, FILE *o)
+{
+	assert(b->s2);
+	fprintf(o, "bne %s, %s, .%s.%lli\n",
+			rname(b->cmp[0]), rname(b->cmp[1]),
+			f->name, (long long)b->s2->id);
+}
+
+static void output_bnz(struct blk *b, struct fn *f, FILE *o)
+{
+	assert(b->s2);
+	fprintf(o, "bne %s, x0, .%s.%lli\n",
+			rname(b->cmp[0]), f->name, (long long)b->s2->id);
+}
+
+static void output_bez(struct blk *b, struct fn *f, FILE *o)
+{
+	assert(b->s2);
+	fprintf(o, "beq %s, x0, .%s.%lli\n",
+			rname(b->cmp[0]), f->name, (long long)b->s2->id);
 }
 
 static void output_ret(struct fn *f, FILE *o)
@@ -290,7 +366,7 @@ static void output_j(struct blk *b, struct fn *f, FILE *o)
 	if (!b->to || b->s1 == b->s2)
 		return;
 
-	fprintf(o, "j .%s.%lli\n", f->name, (long long int)b->s2->id);
+	fprintf(o, "jal x0, .%s.%lli\n", f->name, (long long int)b->s2->id);
 }
 
 static void output_branch(struct blk *b, struct fn *f, FILE *o)
@@ -300,6 +376,9 @@ static void output_branch(struct blk *b, struct fn *f, FILE *o)
 	case J:   output_j(b, f, o); break;
 	case BLT: output_blt(b, f, o); break;
 	case BLE: output_ble(b, f, o); break;
+	case BNE: output_bne(b, f, o); break;
+	case BNZ: output_bnz(b, f, o); break;
+	case BEZ: output_bez(b, f, o); break;
 	default: fprintf(stderr, "unimplemented branch: %s\n",
 		         op_str(b->btype));
 		abort();
diff --git a/src/correct.c b/src/correct.c
new file mode 100644
index 0000000..2654218
--- /dev/null
+++ b/src/correct.c
@@ -0,0 +1,138 @@
+#include <qbt/opt.h>
+
+static size_t spill_ref(struct blk *b, size_t ii, struct insn i, size_t idx, size_t ri)
+{
+	struct val tmp = tmp_val(ri++);
+	struct insn new = insn_create(ADDR, I27, tmp, i.in[idx], noclass());
+	i.in[idx] = tmp;
+	insn_at(b->insns, ii) = i;
+	insn_insert(b, new, ii);
+	return ri;
+}
+
+static size_t spill_imm(struct blk *b, size_t ii, struct insn i, size_t idx, size_t ri)
+{
+	struct val tmp = tmp_val(ri++);
+	struct insn new = insn_create(COPY, I27, tmp, i.in[idx], noclass());
+	i.in[idx] = tmp;
+	insn_at(b->insns, ii) = i;
+	insn_insert(b, new, ii);
+	return ri;
+}
+
+static size_t correct_arith(struct blk *b, size_t ii, struct insn i, size_t ri)
+{
+	if (i.in[0].class == IMM) {
+		/* swap so that immediates are 'outermost' */
+		struct val tmp = i.in[0];
+		i.in[0] = i.in[1];
+		i.in[1] = tmp;
+		insn_at(b->insns, ii) = i;
+		return ri;
+	}
+
+	if (i.in[0].class == IMM)
+		return spill_imm(b, ii, i, 0, ri);
+
+	return ri;
+}
+
+static size_t correct_positional_arith(struct blk *b, size_t ii, struct insn i, size_t ri)
+{
+	if (i.in[0].class == IMM)
+		return spill_imm(b, ii, i, 0, ri);
+
+	return ri;
+}
+
+static size_t correct_branch(struct blk *b, size_t ii, struct insn i, size_t ri)
+{
+	if (i.in[0].class == IMM)
+		return spill_imm(b, ii, i, 0, ri);
+
+	if (i.in[1].class == IMM)
+		return spill_imm(b, ii, i, 1, ri);
+
+	return ri;
+}
+
+static size_t correct_relations(struct blk *b, size_t ii, struct insn i, size_t ri)
+{
+	if (i.in[0].class == IMM)
+		return spill_imm(b, ii, i, 0, ri);
+
+	return ri;
+}
+
+static size_t correct_insn(struct blk *b, size_t ii, struct insn i, size_t ri)
+{
+	/* replace references with instructions */
+	if (i.type != CALL && i.in[0].class == REF)
+		return spill_ref(b, ii, i, 0, ri);
+
+	if (i.in[1].class == REF)
+		return spill_ref(b, ii, i, 1, ri);
+
+	switch (i.type) {
+	case ADD:
+	case MUL:
+		return correct_arith(b, ii, i, ri);
+
+	case SUB:
+	case DIV:
+	case REM:
+	case LSHIFT:
+	case RSHIFT:
+		return correct_positional_arith(b, ii, i, ri);
+
+	case BEQ:
+	case BNE:
+	case BLE:
+	case BGE:
+	case BLT:
+	case BGT:
+	case BNZ:
+	case BEZ:
+		/* oh wait, this never triggers because branches are at the end
+		 * of blocks, duh */
+		return correct_branch(b, ii, i, ri);
+
+	case LT:
+	case LE:
+	case GT:
+	case GE:
+	case EQ:
+	case NE:
+		return correct_relations(b, ii, i, ri);
+
+	default:
+	}
+
+	return ri;
+}
+
+void correct(struct fn *f, size_t ri)
+{
+	/* some simpler corrections to make sure all instructions follow a
+	 * specific pattern. The textual version doesn't have these
+	 * restrictions, but they make our lives easier in the future. */
+	foreach_blk(bi, f->blks) {
+		struct blk *b = blk_at(f->blks, bi);
+		foreach_insn(ii, b->insns) {
+			struct insn i = insn_at(b->insns, ii);
+			ri = correct_insn(b, ii, i, ri);
+		}
+
+		if (b->cmp[0].class == IMM) {
+			struct val t = tmp_val(ri++);
+			insadd(b, COPY, I27, t, b->cmp[0], noclass());
+			b->cmp[0] = t;
+		}
+
+		if (b->cmp[1].class == IMM) {
+			struct val t = tmp_val(ri++);
+			insadd(b, COPY, I27, t, b->cmp[0], noclass());
+			b->cmp[1] = t;
+		}
+	}
+}
diff --git a/src/nodes.c b/src/nodes.c
index d5a22da..22fc454 100644
--- a/src/nodes.c
+++ b/src/nodes.c
@@ -107,8 +107,6 @@ void finish_function(struct fn *f, const char *name)
 		}
 
 		b->s2 = m.b;
-		if (b->btype == J)
-			b->s1 = b->s2;
 	}
 
 }
diff --git a/src/opt.c b/src/opt.c
index 882587d..dac19a6 100644
--- a/src/opt.c
+++ b/src/opt.c
@@ -2,7 +2,6 @@
 
 #include <qbt/opt.h>
 #include <qbt/regalloc.h>
-#include <qbt/ssa.h>
 #include <qbt/abi.h>
 
 void optimize(struct fn *f)
@@ -11,10 +10,14 @@ void optimize(struct fn *f)
 	dump_function(f);
 
 	/* unreachability is done in several steps I guess */
-	ssa(f);
+	size_t ri = ssa(f);
 	printf("\n// after SSA:\n");
 	dump_function(f);
 
+	correct(f, ri);
+	printf("\n// corrections:\n");
+	dump_function(f);
+
 	abi0(f);
 	printf("\n// after abi0:\n");
 	dump_function(f);
diff --git a/src/parser.y b/src/parser.y
index ec133eb..bda8f31 100644
--- a/src/parser.y
+++ b/src/parser.y
@@ -64,7 +64,6 @@
 %token LEXI9 "i9"
 %token LEXI27 "i27"
 
-%nterm <val> mem_loc
 %nterm <str> mem_base
 %nterm <integer> mem_off
 %nterm <integer> int
@@ -262,8 +261,7 @@ type
 	| "i27" { $$ = I27; }
 
 const
-	: "i9" int
-	| "i27" int
+	: int
 
 consts
 	: const "," consts
@@ -307,8 +305,8 @@ arg
 	: id {
 		$$ = IDTOVAL($[id]);
 	}
-	| type int {
-		$$ = imm_val($[int], $[type]);
+	| int {
+		$$ = imm_val($[int], NOTYPE);
 	}
 
 arith
@@ -359,17 +357,19 @@ mem_base
 mem_off
 	: int
 
-mem_loc
-	: "(" mem_base mem_off ")" {$$ = mem_val(IDTOVAL($[mem_base]).r, $[mem_off]);}
-
 mem
-	: type id "<<" mem_loc {
-		struct val t = IDALLOC($[id]);
-		INSADD(LOAD, $[type], t, $[mem_loc], noclass());
+	: type id "<<" mem_base mem_off {
+		struct val t = IDTOVAL($[id]);
+		struct val b = IDTOVAL($[mem_base]);
+		struct val o = imm_val($[mem_off], I27);
+		INSADD(LOAD, $[type], t, b, o);
 	}
-	| id ">>" type mem_loc {
-		struct val t = IDALLOC($[id]);
-		INSADD(STORE, $[type], noclass(), t, $[mem_loc]);
+	| id ">>" type mem_base mem_off {
+		struct val t = IDTOVAL($[id]);
+		struct val b = IDTOVAL($[mem_base]);
+		struct val o = imm_val($[mem_off], I27);
+		/* really not a huge fan or 'reusing' the output slot... */
+		INSADD(STORE, $[type], o, b, t);
 	}
 
 stack
@@ -444,6 +444,12 @@ branch
 	| arg ">"  arg "->" local {
 		NEW_BLOCK(BGT, $1, $3, $[local]);
 	}
+	| arg "->" local {
+		NEW_BLOCK(BNZ, $[arg], noclass(), $[local]);
+	}
+	| "!" arg "->" local {
+		NEW_BLOCK(BEZ, $[arg], noclass(), $[local]);
+	}
 	| "->" local {
 		NEW_BLOCK(J, noclass(), noclass(), $[local]);
 	}
diff --git a/src/regalloc.c b/src/regalloc.c
index ffefeb5..9c4d87e 100644
--- a/src/regalloc.c
+++ b/src/regalloc.c
@@ -387,35 +387,33 @@ static bool callee_save(struct val r)
 	return false;
 }
 
-static void insn_insert_before_call(struct blk *b, struct insn save, size_t pos)
+static void insn_insert_before_call(struct blk *b, struct insn save, ssize_t pos)
 {
 	assert((insn_at(b->insns, pos)).type == CALL);
 	struct insn setup;
 	do {
-		/* the first instruction in a block can be part of a call setup */
-		if (pos == 0)
+		if (pos < 0)
 			break;
 
-		pos--;
 		setup = insn_at(b->insns, pos);
+		pos--;
 	} while (has_insn_flag(setup, CALL_SETUP));
 
-	/* the do-while loop technically went one too far, fix */
-	insn_insert(b, save, pos == 0 ? 0 : pos + 1);
+	insn_insert(b, save, pos + 1);
 }
 
 static void insn_insert_after_call(struct blk *b, struct insn restore, size_t pos)
 {
 	assert((insn_at(b->insns, pos)).type == CALL);
-	size_t max = vec_len(&b->insns) - 1;
+	size_t max = vec_len(&b->insns);
 
 	struct insn setup;
 	do {
 		if (pos == max)
 			break;
 
-		pos++;
 		setup = insn_at(b->insns, pos);
+		pos++;
 	} while (has_insn_flag(setup, CALL_TEARDOWN));
 
 	insn_insert(b, restore, pos);
@@ -497,14 +495,22 @@ void regalloc(struct fn *f)
 		struct blk *b = blk_at(f->blks, bi);
 		vec_reset(&lifetimes);
 		vec_reset(&calls);
+
 		/** @todo collect hints from args/params */
 		collect_lifetimes(b, &hints, &lifetimes, &rmap, &calls);
-		f->max_callee_save = build_rmap(&hints, &lifetimes, &rmap);
+		size_t max_callee_save = build_rmap(&hints, &lifetimes, &rmap);
+
 		do_rewrites(b, &rmap);
-		f->max_call_save = do_call_saves(b, &lifetimes, &rmap, &calls);
+		size_t max_call_save = do_call_saves(b, &lifetimes, &rmap, &calls);
 		/** @todo forward_hints(b, &hints, &rmap) */
 		if (vec_len(&calls) != 0)
 			f->has_calls = true;
+
+		if (max_callee_save > f->max_callee_save)
+			f->max_callee_save = max_callee_save;
+
+		if (max_call_save > f->max_call_save)
+			f->max_call_save = max_call_save;
 	}
 
 	vec_destroy(&calls);
diff --git a/src/ssa.c b/src/ssa.c
index 96d1eb1..997f078 100644
--- a/src/ssa.c
+++ b/src/ssa.c
@@ -1,5 +1,4 @@
 #include <assert.h>
-#include <qbt/ssa.h>
 #include <qbt/unreachable.h>
 
 static void add_val(struct vec *map, struct val v)
@@ -221,7 +220,7 @@ static size_t rename_temps(struct blk *b, size_t i)
 	return i;
 }
 
-void ssa(struct fn *f)
+size_t ssa(struct fn *f)
 {
 	/* do a depth-first traversal of blocks, mark locations within as either
 	 * generated (i.e. we assign something to the register) or required
@@ -236,4 +235,6 @@ void ssa(struct fn *f)
 		struct blk *b = blk_at(f->blks, bi);
 		i = rename_temps(b, i);
 	}
+
+	return i;
 }
diff --git a/src/vec.c b/src/vec.c
index 7fb314e..344518b 100644
--- a/src/vec.c
+++ b/src/vec.c
@@ -58,7 +58,7 @@ void vec_insert(struct vec *v, void *n, size_t i)
 {
 	assert(i <= vec_len(v));
 	if (i == vec_len(v))
-		vec_append(v, n);
+		return vec_append(v, n);
 
 	v->n++;
 	if (v->n >= v->s) {