produce some very limited assembly output

+ Several subsystems missing critical features, but enough to do some
  basic things like calling procedures, printing to screen and doing loops

20 files changed, 1019 insertions, 76 deletions

diff --git a/README.md b/README.md
new file mode 100644
index 0000000..3c8feec
--- /dev/null
+++ b/README.md
@@ -0,0 +1,89 @@
+# qbt
+
+Optimizing middle/back end for triscv.
+
+# ABI
+
+| Register | Name |
+|----------|------|
+| x0       | x0
+| x1       | sp
+| x2       | fp
+| x3       | gp
+| x4       | a0
+| x5       | a1
+| x6       | a2
+| x7       | a3
+| x8       | a4
+| x9       | a5
+| x10      | a6
+| x11      | t0
+| x12      | t1
+| x13      | t2
+| x14      | t3
+| x15      | t4
+| x16      | t5
+| x17      | t6
+| x18      | s0
+| x19      | s1
+| x20      | s2
+| x21      | s3
+| x22      | s4
+| x23      | s5
+| x24      | s6
+| x25      | tp
+| x26      | ra
+| x27      | a7
+| x28      | a8
+| x29      | a9
+| x30      | a10
+| x31      | a11
+| x32      | a12
+| x33      | a13
+| x34      | a14
+| x35      | a15
+| x36      | a16
+| x37      | a17
+| x38      | a19
+| x39      | a20
+| x40      | a20
+| x41      | a21
+| x42      | a22
+| x43      | a23
+| x44      | a24
+| x45      | t7
+| x46      | t8
+| x47      | t9
+| x48      | t10
+| x49      | t11
+| x50      | t12
+| x51      | t13
+| x52      | t14
+| x53      | t15
+| x54      | t16
+| x55      | t17
+| x56      | t18
+| x57      | t19
+| x58      | t20
+| x59      | t21
+| x60      | t22
+| x61      | t23
+| x62      | t24
+| x63      | s7
+| x64      | s8
+| x65      | s9
+| x66      | s10
+| x67      | s11
+| x68      | s12
+| x69      | s13
+| x70      | s14
+| x71      | s15
+| x72      | s16
+| x73      | s17
+| x74      | s18
+| x75      | s19
+| x76      | s20
+| x77      | s21
+| x78      | s22
+| x79      | s23
+| x80      | s24
diff --git a/include/qbt/abi.h b/include/qbt/abi.h
new file mode 100644
index 0000000..cc33dfc
--- /dev/null
+++ b/include/qbt/abi.h
@@ -0,0 +1,258 @@
+#ifndef ABI_H
+#define ABI_H
+
+#include <qbt/nodes.h>
+
+enum {
+	RX0,
+	RX1,
+	RX2,
+	RX3,
+	RX4,
+	RX5,
+	RX6,
+	RX7,
+	RX8,
+	RX9,
+	RX10,
+	RX11,
+	RX12,
+	RX13,
+	RX14,
+	RX15,
+	RX16,
+	RX17,
+	RX18,
+	RX19,
+	RX20,
+	RX21,
+	RX22,
+	RX23,
+	RX24,
+	RX25,
+	RX26,
+	RX27,
+	RX28,
+	RX29,
+	RX30,
+	RX31,
+	RX32,
+	RX33,
+	RX34,
+	RX35,
+	RX36,
+	RX37,
+	RX38,
+	RX39,
+	RX40,
+	RX41,
+	RX42,
+	RX43,
+	RX44,
+	RX45,
+	RX46,
+	RX47,
+	RX48,
+	RX49,
+	RX50,
+	RX51,
+	RX52,
+	RX53,
+	RX54,
+	RX55,
+	RX56,
+	RX57,
+	RX58,
+	RX59,
+	RX60,
+	RX61,
+	RX62,
+	RX63,
+	RX64,
+	RX65,
+	RX66,
+	RX67,
+	RX68,
+	RX69,
+	RX70,
+	RX71,
+	RX72,
+	RX73,
+	RX74,
+	RX75,
+	RX76,
+	RX77,
+	RX78,
+	RX79,
+	RX80,
+};
+
+enum {
+	RSP = RX1,
+	RFP,
+	RGP,
+	RA0,
+	RA1,
+	RA2,
+	RA3,
+	RA4,
+	RA5,
+	RA6,
+	RT0,
+	RT1,
+	RT2,
+	RT3,
+	RT4,
+	RT5,
+	RT6,
+	RS0,
+	RS1,
+	RS2,
+	RS3,
+	RS4,
+	RS5,
+	RS6,
+	RTP,
+	RRA,
+	RA7,
+	RA8,
+	RA9,
+	RA10,
+	RA11,
+	RA12,
+	RA13,
+	RA14,
+	RA15,
+	RA16,
+	RA17,
+	RA18,
+	RA19,
+	RA20,
+	RA21,
+	RA22,
+	RA23,
+	RA24,
+	RT7,
+	RT8,
+	RT9,
+	RT10,
+	RT11,
+	RT12,
+	RT13,
+	RT14,
+	RT15,
+	RT16,
+	RT17,
+	RT18,
+	RT19,
+	RT20,
+	RT21,
+	RT22,
+	RT23,
+	RT24,
+	RS7,
+	RS8,
+	RS9,
+	RS10,
+	RS11,
+	RS12,
+	RS13,
+	RS14,
+	RS15,
+	RS16,
+	RS17,
+	RS18,
+	RS19,
+	RS20,
+	RS21,
+	RS22,
+	RS23,
+	RS24,
+};
+
+#define FOREACH_REG(M)\
+	M(RX0)\
+	M(RX1)\
+	M(RX2)\
+	M(RX3)\
+	M(RX4)\
+	M(RX5)\
+	M(RX6)\
+	M(RX7)\
+	M(RX8)\
+	M(RX9)\
+	M(RX10)\
+	M(RX11)\
+	M(RX12)\
+	M(RX13)\
+	M(RX14)\
+	M(RX15)\
+	M(RX16)\
+	M(RX17)\
+	M(RX18)\
+	M(RX19)\
+	M(RX20)\
+	M(RX21)\
+	M(RX22)\
+	M(RX23)\
+	M(RX24)\
+	M(RX25)\
+	M(RX26)\
+	M(RX27)\
+	M(RX28)\
+	M(RX29)\
+	M(RX30)\
+	M(RX31)\
+	M(RX32)\
+	M(RX33)\
+	M(RX34)\
+	M(RX35)\
+	M(RX36)\
+	M(RX37)\
+	M(RX38)\
+	M(RX39)\
+	M(RX40)\
+	M(RX41)\
+	M(RX42)\
+	M(RX43)\
+	M(RX44)\
+	M(RX45)\
+	M(RX46)\
+	M(RX47)\
+	M(RX48)\
+	M(RX49)\
+	M(RX50)\
+	M(RX51)\
+	M(RX52)\
+	M(RX53)\
+	M(RX54)\
+	M(RX55)\
+	M(RX56)\
+	M(RX57)\
+	M(RX58)\
+	M(RX59)\
+	M(RX60)\
+	M(RX61)\
+	M(RX62)\
+	M(RX63)\
+	M(RX64)\
+	M(RX65)\
+	M(RX66)\
+	M(RX67)\
+	M(RX68)\
+	M(RX69)\
+	M(RX70)\
+	M(RX71)\
+	M(RX72)\
+	M(RX73)\
+	M(RX74)\
+	M(RX75)\
+	M(RX76)\
+	M(RX77)\
+	M(RX78)\
+	M(RX79)\
+	M(RX80)
+
+void abi0(struct fn *f);
+
+#endif /* ABI_H */
diff --git a/include/qbt/asm.h b/include/qbt/asm.h
new file mode 100644
index 0000000..10f3f3f
--- /dev/null
+++ b/include/qbt/asm.h
@@ -0,0 +1,10 @@
+#ifndef ASM_H
+#define ASM_H
+
+#include <stdio.h>
+
+#include <qbt/nodes.h>
+
+void output(struct fn *fn, FILE *f);
+
+#endif /* ASM_H */
diff --git a/include/qbt/nodes.h b/include/qbt/nodes.h
index 0821663..011d718 100644
--- a/include/qbt/nodes.h
+++ b/include/qbt/nodes.h
@@ -38,6 +38,7 @@ enum insn_type {
 	J,
 	RET,
 	ARG,
+	RETARG,
 	PARAM,
 	RETVAL,
 };
@@ -73,10 +74,20 @@ enum insn_type {
 	M(BGT)\
 	M(J)\
 	M(ARG)\
+	M(RETARG)\
 	M(PARAM)\
 	M(RET)\
 	M(RETVAL)\
 
+static inline const char *op_str(enum insn_type n) {
+#define CASE(I) case I: return #I;
+	switch (n) {
+		FOREACH_INSN_TYPE(CASE);
+	}
+#undef CASE
+	return "unknown";
+}
+
 enum val_class {
 	REG,
 	TMP,
@@ -123,6 +134,8 @@ struct fn {
 	const char *name;
 	size_t ntmp;
 	size_t nblk;
+	size_t max_callee_save;
+	bool has_calls;
 	struct vec blks;
 	struct vec labels;
 	struct vec tmps;
@@ -147,6 +160,14 @@ static inline struct val noclass()
 	};
 }
 
+static inline struct val reg_val(int64_t r)
+{
+	return (struct val){
+		.class = REG,
+		.r = r
+	};
+}
+
 static inline struct val imm_ref(const char *s)
 {
 	return (struct val){
diff --git a/include/qbt/opt.h b/include/qbt/opt.h
new file mode 100644
index 0000000..b218b7e
--- /dev/null
+++ b/include/qbt/opt.h
@@ -0,0 +1,7 @@
+#ifndef OPT_H
+#define OPT_H
+
+#include <qbt/nodes.h>
+void optimize(struct fn *fn);
+
+#endif /* OPT_H */
diff --git a/include/qbt/regalloc.h b/include/qbt/regalloc.h
new file mode 100644
index 0000000..a318e7e
--- /dev/null
+++ b/include/qbt/regalloc.h
@@ -0,0 +1,8 @@
+#ifndef REGALLOC_H
+#define REGALLOC_H
+
+#include <qbt/nodes.h>
+
+void regalloc(struct fn *f);
+
+#endif /* REGALLOC_H */
diff --git a/include/qbt/ssa.h b/include/qbt/ssa.h
new file mode 100644
index 0000000..32a7534
--- /dev/null
+++ b/include/qbt/ssa.h
@@ -0,0 +1,8 @@
+#ifndef SSA_H
+#define SSA_H
+
+#include <qbt/nodes.h>
+
+void ssa(struct fn *f);
+
+#endif /* SSA_H */
diff --git a/src/abi.c b/src/abi.c
new file mode 100644
index 0000000..cb92190
--- /dev/null
+++ b/src/abi.c
@@ -0,0 +1,96 @@
+#include <assert.h>
+#include <stdlib.h>
+#include <qbt/abi.h>
+
+static const int64_t ar_map[] = {
+	RA0, RA1, RA2, RA3, RA4, RA5, RA6, RA7, RA8, RA9,
+	RA10, RA11, RA12, RA13, RA14, RA15, RA16, RA17, RA18, RA19,
+	RA20, RA21, RA22, RA23, RA24
+};
+
+static struct val nth_ar(int64_t nth)
+{
+	return reg_val(ar_map[nth]);
+}
+
+static struct insn rewrite_param(struct insn n)
+{
+	assert(n.type == PARAM);
+	assert(n.in[1].class == IMM);
+	int64_t nth_param = n.in[1].v;
+	assert(nth_param >= 0 && nth_param < 25
+			&& "stack argument passing not yet supported");
+
+	return insn_create(MOVE, I27, n.out, nth_ar(nth_param), noclass());
+}
+
+static struct insn rewrite_retval(struct insn n)
+{
+	assert(n.type == RETVAL);
+	assert(n.in[1].class == IMM);
+	int64_t nth_retval = n.in[1].v;
+	assert(nth_retval >= 0 && nth_retval < 25);
+	return insn_create(MOVE, I27, n.out, nth_ar(nth_retval), noclass());
+}
+
+static struct insn rewrite_arg(struct insn n)
+{
+	assert(n.type == ARG);
+	assert(n.in[1].class == IMM);
+	int64_t nth_arg = n.in[1].v;
+	assert(nth_arg >= 0 && nth_arg < 25);
+
+	if (n.in[0].class == TMP || n.in[0].class == REG)
+		return insn_create(MOVE, I27, nth_ar(nth_arg), n.in[0], noclass());
+	else if (n.in[0].class == IMM || n.in[0].class == REF)
+		return insn_create(COPY, I27, nth_ar(nth_arg), n.in[0], noclass());
+
+	assert("illegal arg type");
+	abort();
+}
+
+static struct insn rewrite_retarg(struct insn n)
+{
+	assert(n.type == RETARG);
+	assert(n.in[1].class == IMM);
+	int64_t nth_arg = n.in[1].v;
+	assert(nth_arg >= 0 && nth_arg < 25);
+
+	if (n.in[0].class == TMP || n.in[0].class == REG)
+		return insn_create(MOVE, I27, nth_ar(nth_arg), n.in[0], noclass());
+	else if (n.in[0].class == IMM || n.in[0].class == REF)
+		return insn_create(COPY, I27, nth_ar(nth_arg), n.in[0], noclass());
+
+	assert("illegal retval type");
+	abort();
+}
+
+void abi0(struct fn *f)
+{
+	foreach_blk(bi, f->blks) {
+		struct blk *b = blk_at(f->blks, bi);
+		foreach_insn(i, b->insns) {
+			struct insn n = insn_at(b->insns, i);
+			if (n.type == PARAM) {
+				struct insn p = rewrite_param(n);
+				insn_at(b->insns, i) = p;
+			}
+
+			else if (n.type == RETVAL) {
+				struct insn r = rewrite_retval(n);
+				insn_at(b->insns, i) = r;
+			}
+
+			else if (n.type == ARG) {
+				struct insn a = rewrite_arg(n);
+				insn_at(b->insns, i) = a;
+			}
+
+			else if (n.type == RETARG) {
+				struct insn a = rewrite_retarg(n);
+				insn_at(b->insns, i) = a;
+			}
+		}
+	}
+}
+
diff --git a/src/asm.c b/src/asm.c
new file mode 100644
index 0000000..eb0bead
--- /dev/null
+++ b/src/asm.c
@@ -0,0 +1,277 @@
+#include <stdlib.h>
+#include <assert.h>
+#include <qbt/abi.h>
+#include <qbt/asm.h>
+
+static const char *rname(struct val v)
+{
+	assert(v.class == REG);
+	/** @todo use ABI names? */
+	switch (v.r) {
+		case RX0: return "x0";
+		case RX1: return "x1";
+		case RX2: return "x2";
+		case RX3: return "x3";
+		case RX4: return "x4";
+		case RX5: return "x5";
+		case RX6: return "x6";
+		case RX7: return "x7";
+		case RX8: return "x8";
+		case RX9: return "x9";
+		case RX10: return "x10";
+		case RX11: return "x11";
+		case RX12: return "x12";
+		case RX13: return "x13";
+		case RX14: return "x14";
+		case RX15: return "x15";
+		case RX16: return "x16";
+		case RX17: return "x17";
+		case RX18: return "x18";
+		case RX19: return "x19";
+		case RX20: return "x20";
+		case RX21: return "x21";
+		case RX22: return "x22";
+		case RX23: return "x23";
+		case RX24: return "x24";
+		case RX25: return "x25";
+		case RX26: return "x26";
+		case RX27: return "x27";
+		case RX28: return "x28";
+		case RX29: return "x29";
+		case RX30: return "x30";
+		case RX31: return "x31";
+		case RX32: return "x32";
+		case RX33: return "x33";
+		case RX34: return "x34";
+		case RX35: return "x35";
+		case RX36: return "x36";
+		case RX37: return "x37";
+		case RX38: return "x38";
+		case RX39: return "x39";
+		case RX40: return "x40";
+		case RX41: return "x41";
+		case RX42: return "x42";
+		case RX43: return "x43";
+		case RX44: return "x44";
+		case RX45: return "x45";
+		case RX46: return "x46";
+		case RX47: return "x47";
+		case RX48: return "x48";
+		case RX49: return "x49";
+		case RX50: return "x50";
+		case RX51: return "x51";
+		case RX52: return "x52";
+		case RX53: return "x53";
+		case RX54: return "x54";
+		case RX55: return "x55";
+		case RX56: return "x56";
+		case RX57: return "x57";
+		case RX58: return "x58";
+		case RX59: return "x59";
+		case RX60: return "x60";
+		case RX61: return "x61";
+		case RX62: return "x62";
+		case RX63: return "x63";
+		case RX64: return "x64";
+		case RX65: return "x65";
+		case RX66: return "x66";
+		case RX67: return "x67";
+		case RX68: return "x68";
+		case RX69: return "x69";
+		case RX70: return "x70";
+		case RX71: return "x71";
+		case RX72: return "x72";
+		case RX73: return "x73";
+		case RX74: return "x74";
+		case RX75: return "x75";
+		case RX76: return "x76";
+		case RX77: return "x77";
+		case RX78: return "x78";
+		case RX79: return "x79";
+		case RX80: return "x80";
+	}
+
+	assert(0 && "illegal register");
+	abort();
+}
+
+static void save_state(struct fn *f, FILE *o)
+{
+	/* stack frame:
+	 * last frame
+	 * ra
+	 * s0
+	 * ...
+	 * local variables
+	 * <- sp
+	 */
+	fprintf(o, "st w fp, -3(sp)\n");
+	if (f->has_calls)
+		fprintf(o, "st w ra, -6(fp)\n");
+
+	fprintf(o, "mv fp, sp\n");
+	fprintf(o, "addi sp, sp, -%zi\n", f->max_callee_save * 3 + 6);
+
+	for (size_t i = 0; i < f->max_callee_save; ++i) {
+		fprintf(o, "st w s%zi, -%zi(fp)\n",
+				i, 3 * i + 9);
+	}
+}
+
+static void restore_state(struct fn *f, FILE *o)
+{
+	for (size_t i = 0; i < f->max_callee_save; ++i) {
+		fprintf(o, "ld w s%zi, -%zi(fp)\n",
+				i, 3 * i + 9);
+	}
+
+	if (f->has_calls)
+		fprintf(o, "ld w ra, -6(fp)\n");
+
+	fprintf(o, "ld w fp, -3(fp)\n");
+	fprintf(o, "mv sp, fp\n");
+}
+
+static void output_move(struct insn n, FILE *o)
+{
+	fprintf(o, "mv %s, %s\n",
+			rname(n.out), rname(n.in[0]));
+}
+
+static void output_add(struct insn n, FILE *o)
+{
+	if (n.in[1].class == REG) {
+		fprintf(o, "add %s, %s, %s\n",
+				rname(n.out), rname(n.in[0]), rname(n.in[1]));
+		return;
+	}
+	else if (n.in[1].class == IMM) {
+		/** @todo fix for values larger than what addi allows, mark one
+		 * temporary register reserved for the compiler? */
+		fprintf(o, "addi %s, %s, %lli\n",
+				rname(n.out), rname(n.in[0]), (long long int)n.in[1].v);
+		return;
+	}
+
+	assert(0 && "illegal value type for add");
+	abort();
+}
+
+static void output_sub(struct insn n, FILE *o)
+{
+	if (n.in[1].class == REG) {
+		fprintf(o, "sub %s, %s, %s\n",
+				rname(n.out), rname(n.in[0]), rname(n.in[1]));
+		return;
+	}
+	else if (n.in[1].class == IMM) {
+		if (n.in[1].v >= 0)
+			fprintf(o, "addi %s, %s, -%lli\n",
+				rname(n.out), rname(n.in[0]), (long long int)n.in[1].v);
+		else /* double negative */
+			fprintf(o, "addi %s, %s, %lli\n",
+				rname(n.out), rname(n.in[0]), (long long int)n.in[1].v);
+		return;
+	}
+
+	assert(0 && "illegal value type for sub");
+	abort();
+}
+
+static void output_copy(struct insn n, FILE *o)
+{
+	fprintf(o, "li %s, %lli\n",
+			rname(n.out), (long long int)n.in[0].v);
+}
+
+static void output_call(struct insn n, FILE *o)
+{
+	if (n.in[0].class == REF) {
+		fprintf(o, "call ra, %s\n", n.in[0].s);
+		return;
+	}
+	else if (n.in[0].class == REG) {
+		fprintf(o, "jalr ra, 0(%s)\n", rname(n.in[0]));
+		return;
+	}
+
+	assert(0 && "illegal value type for call");
+	abort();
+}
+
+static void output_insn(struct insn n, FILE *o)
+{
+	/* 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 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;
+		default: fprintf(stderr, "unimplemented insn: %s\n", op_str(n.type));
+			 abort();
+	}
+}
+
+static void output_blt(struct blk *b, struct fn *f, FILE *o)
+{
+	assert(b->s2);
+	fprintf(o, "blt %s, %s, .%s.%lli\n",
+			rname(b->cmp[0]), rname(b->cmp[1]),
+				f->name, (long long int)b->s2->id);
+}
+
+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);
+}
+
+static void output_ret(struct fn *f, FILE *o)
+{
+	restore_state(f, o);
+	fprintf(o, "ret ra\n");
+}
+
+static void output_j(struct blk *b, struct fn *f, FILE *o)
+{
+	/* the jump is directly to a following block, no need to do anything */
+	if (!b->to)
+		return;
+
+	fprintf(o, "j .%s.%lli\n", f->name, (long long int)b->s1->id);
+}
+
+static void output_branch(struct blk *b, struct fn *f, FILE *o)
+{
+	switch (b->btype) {
+		case RET: output_ret(f, o); break;
+		case J:   output_j(b, f, o); break;
+		case BLT: output_blt(b, f, o); break;
+		case BLE: output_ble(b, f, o); break;
+		default: fprintf(stderr, "unimplemented branch: %s\n", op_str(b->btype));
+			 abort();
+	}
+}
+
+void output(struct fn *f, FILE *o)
+{
+	fprintf(o, "%s:\n", f->name);
+	save_state(f, o);
+	foreach_blk(bi, f->blks) {
+		struct blk *b = blk_at(f->blks, bi);
+		fprintf(o, ".%s.%lli:\n",
+				f->name, (long long int)b->id);
+
+		foreach_insn(i, b->insns) {
+			struct insn n = insn_at(b->insns, i);
+			output_insn(n, o);
+		}
+
+		output_branch(b, f, o);
+	}
+}
diff --git a/src/main.c b/src/main.c
index a0eeb42..d6abb2d 100644
--- a/src/main.c
+++ b/src/main.c
@@ -4,6 +4,8 @@
 #include <limits.h>
 
 #include <qbt/parser.h>
+#include <qbt/opt.h>
+#include <qbt/asm.h>
 #include <qbt/debug.h>
 
 static char *read_file(const char *file, FILE *f)
@@ -56,6 +58,11 @@ int main(int argc, char *argv[])
 	foreach_fn(i, p->fns) {
 		struct fn_map m = fn_at(p->fns, i);
 		dump_function(m.fn);
+		// also handles things like register mapping etc.
+		optimize(m.fn);
+		dump_function(m.fn);
+		// for now
+		output(m.fn, stdout);
 	}
 
 	destroy_parser(p);
diff --git a/src/nodes.c b/src/nodes.c
index 9eb0113..4c5e97a 100644
--- a/src/nodes.c
+++ b/src/nodes.c
@@ -104,6 +104,8 @@ struct fn *new_function()
 	f->blks = vec_create(sizeof(struct blk *));
 	f->tmps = vec_create(sizeof(struct tmp_map));
 	f->labels = vec_create(sizeof(struct label_map));
+	f->has_calls = false;
+	f->max_callee_save = 0;
 	/* empty block */
 	new_block(f);
 	return f;
@@ -134,15 +136,6 @@ void new_label(struct fn *f, struct blk *b, const char *name)
 	vec_append(&f->labels, &(struct label_map){.id = name, .b = b});
 }
 
-static const char *op_str(enum insn_type n) {
-#define CASE(I) case I: return #I;
-	switch (n) {
-		FOREACH_INSN_TYPE(CASE);
-	}
-#undef CASE
-	return "unknown";
-}
-
 void dump_val(struct val val) {
 	long long r = val.r;
 	long long v = val.v;
@@ -160,7 +153,7 @@ void dump_val(struct val val) {
 
 void dump_insn(struct insn i)
 {
-	printf("\t");
+	printf("//\t");
 
 	if (hasclass(i.out)) {
 		dump_val(i.out);
@@ -189,7 +182,7 @@ bool return_blk(struct blk *b)
 
 void dump_block(struct blk *b)
 {
-	printf("\t/*** block %lld ", (long long)b->id);
+	printf("//\t/*** block %lld ", (long long)b->id);
 	if (b->name) printf("(%s) ", b->name);
 	printf("***/\n");
 
@@ -199,20 +192,20 @@ void dump_block(struct blk *b)
 	}
 
 	if (return_blk(b)) {
-		printf("\n");
+		printf("//\tRETURN\n");
 		return;
 	}
 
 	if (b->btype != J) {
 		assert(b->s2);
 		struct blk *s2 = b->s2;
-		printf("\t%s ", op_str(b->btype));
+		printf("//\t%s ", op_str(b->btype));
 		dump_val(b->cmp[0]);
 		printf(" ");
 		dump_val(b->cmp[1]);
 		printf(" -> %lli\n", (long long)s2->id);
 	}
-	printf("\n");
+	printf("//\n");
 }
 
 void dump_function(struct fn *f) {
diff --git a/src/opt.c b/src/opt.c
new file mode 100644
index 0000000..3036950
--- /dev/null
+++ b/src/opt.c
@@ -0,0 +1,12 @@
+#include <qbt/opt.h>
+#include <qbt/regalloc.h>
+#include <qbt/ssa.h>
+#include <qbt/abi.h>
+
+void optimize(struct fn *f)
+{
+	ssa(f);
+	abi0(f);
+	/* ... do more stuff ... */
+	regalloc(f);
+}
diff --git a/src/parser.y b/src/parser.y
index 4a70341..4edcdcf 100644
--- a/src/parser.y
+++ b/src/parser.y
@@ -12,11 +12,6 @@
 #include <qbt/debug.h>
 #include <qbt/nodes.h>
 
-struct ret_helper {
-	const char *r;
-	enum val_type t;
-};
-
 %}
 
 %locations
@@ -31,7 +26,6 @@ struct ret_helper {
 
 %union {
 	struct val val;
-	struct ret_helper ret;
 	enum val_type type;
 	int64_t integer;
 	char *str;
@@ -77,8 +71,10 @@ struct ret_helper {
 %nterm <type> type
 
 %nterm <str> id addr local label
-%nterm <val> arg opt_arg
-%nterm <ret> call_ret opt_call_ret
+%nterm <val> arg
+%nterm <val> ret
+
+%nterm <integer> placeholder
 
 %{
 
@@ -201,6 +197,22 @@ static inline void do_new_label(struct parser *p, const char *s)
 	new_label(p->f, p->b, s);
 }
 
+static inline size_t do_cur_insn(struct parser *p)
+{
+	return vec_len(&p->b->insns);
+}
+
+static inline void do_ins_replace(struct parser *p, size_t i, struct insn n)
+{
+	insn_at(p->b->insns, i) = n;
+}
+
+#define INS_REPLACE(i, n)\
+	do_ins_replace(parser, i, n)
+
+#define CUR_INSN()\
+	do_cur_insn(parser)
+
 #define INSADD(o, t, r, a0, a1)\
 	do_insadd(parser, o, t, r, a0, a1)
 
@@ -260,7 +272,7 @@ data
 param
 	: type id {
 		struct val t = IDALLOC($[id]);
-		INSADD(PARAM, $[type], t, imm_val(parser->idx++, I27), noclass());
+		INSADD(PARAM, $[type], t, noclass(), imm_val(parser->idx++, I27));
 	}
 
 params
@@ -272,17 +284,6 @@ opt_params
 	: params
 	| {}
 
-ret
-	: type
-
-opt_ret
-	: ret
-	| {}
-
-/* only three return args permitted (keep things simple for now) */
-rets
-	: opt_ret "," opt_ret "," opt_ret
-
 label
 	: id ":" {
 		if (empty_block(parser->b)) {
@@ -299,7 +300,7 @@ arg
 		$$ = IDTOVAL($[id]);
 	}
 	| type int {
-		$$ = imm_val($[type], $[int]);
+		$$ = imm_val($[int], $[type]);
 	}
 
 arith
@@ -439,14 +440,24 @@ branch
 		NEW_BLOCK(J, noclass(), noclass(), $[local]);
 	}
 
+ret
+	: id {
+		$$ = IDALLOC($[id]);
+	}
+
 call_ret
-	: type id {
-		$$ = (struct ret_helper){.r = $[id], .t = $[type]};
+	: ret {
+		INSADD(RETVAL, NOTYPE, $[ret], noclass(), imm_val(parser->idx++, I27));
 	}
 
-opt_call_ret
-	: call_ret
-	| { $$ = (struct ret_helper){.r = NULL, .t = NOTYPE}; }
+call_rets
+	: call_ret "," call_rets
+	| call_ret ","
+	| call_ret
+
+opt_call_rets
+	: call_rets
+	| {}
 
 call_arg
 	: arg {
@@ -466,43 +477,43 @@ opt_call_args
 reset_index
 	: {parser->idx = 0;}
 
-call
-	: "(" opt_call_ret "," opt_call_ret "," opt_call_ret ")"
-	"=" addr reset_index "(" opt_call_args ")" {
-		/* call args should have inserted their own nodes */
-		INSADD(CALL, NOTYPE, noclass(), imm_ref($[addr]), noclass());
-
-		if ($2.r) {
-			struct val t = IDALLOC($2.r);
-			INSADD(RETVAL, $2.t, t, noclass(), imm_val(0, I27));
-		}
-
-		if ($4.r) {
-			struct val t = IDALLOC($4.r);
-			INSADD(RETVAL, $4.t, t, noclass(), imm_val(1, I27));
-		}
-
-		if ($6.r) {
-			struct val t = IDALLOC($6.r);
-			INSADD(RETVAL, $6.t, t, noclass(), imm_val(2, I27));
-		}
+placeholder
+	: {
+		$$ = CUR_INSN();
+		INSADD(CALL, NOTYPE, noclass(), noclass(), noclass());
 	}
 
-opt_arg
-	: arg
-	| { $$ = noclass(); }
+call
+	: addr reset_index "(" opt_call_args ")"
+	  "=>" placeholder reset_index "(" opt_call_rets ")" {
+		/* kind of hacky but works */
+		INS_REPLACE($[placeholder],
+			insn_create(CALL, NOTYPE,
+				noclass(), imm_ref($[addr]), noclass()));
+	}
+	| id reset_index "(" opt_call_args ")"
+	  "=>" placeholder reset_index "(" opt_call_rets ")" {
+		INS_REPLACE($[placeholder],
+			insn_create(CALL, NOTYPE,
+				noclass(), IDTOVAL($[id]), noclass()));
+	  }
 
-return
-	: "=>" "(" opt_arg "," opt_arg "," opt_arg ")" {
-		if (!hasnoclass($3))
-			INSADD(RET, NOTYPE, noclass(), $3, imm_val(0, I27));
+proc_ret
+	: id {
+		INSADD(RETARG, NOTYPE, noclass(), IDTOVAL($[id]), imm_val(parser->idx++, I27));
+	}
 
-		if (!hasnoclass($5))
-			INSADD(RET, NOTYPE, noclass(), $5, imm_val(1, I27));
+proc_rets
+	: proc_ret "," proc_rets
+	| proc_ret ","
+	| proc_ret
 
-		if (!hasnoclass($7))
-			INSADD(RET, NOTYPE, noclass(), $7, imm_val(2, I27));
+opt_proc_rets
+	: proc_rets
+	| {}
 
+return
+	: "=>" reset_index "(" opt_proc_rets ")" {
 		NEW_BLOCK(RET, noclass(), noclass(), NULL);
 	}
 
@@ -524,8 +535,9 @@ body
 	| label
 	| insn ";"
 
+/** @todo add in return type checking? */
 function
-	: id reset_index "(" opt_params "=>" rets ")" "{" body "}" {
+	: id reset_index "(" opt_params ")" "{" body "}" {
 		NEW_FUNCTION($[id]);
 	}
 
diff --git a/src/regalloc.c b/src/regalloc.c
new file mode 100644
index 0000000..474e5a4
--- /dev/null
+++ b/src/regalloc.c
@@ -0,0 +1,90 @@
+#include <assert.h>
+
+#include <qbt/regalloc.h>
+#include <qbt/vec.h>
+#include <qbt/abi.h>
+
+static const int64_t tr_map[] = {
+	RS0, RS1, RS2, RS3, RS4, RS5, RS6, RS7, RS8, RS9,
+	RS10, RS11, RS12, RS13, RS14, RS15, RS16, RS17, RS18, RS19,
+	RS20, RS21, RS22, RS23, RS24
+};
+
+#define reg_at(v, i)\
+	vect_at(int64_t, v, i)
+
+static struct val rewrite_tmp(struct vec rmap, struct val t)
+{
+	assert(t.class == TMP);
+	assert(t.r < (int64_t)vec_len(&rmap));
+	int64_t r = reg_at(rmap, t.r);
+	assert(r);
+	return reg_val(r);
+}
+
+static size_t cur_reg = 0;
+static void add_rewrite_rule(struct vec *rmap, struct val t)
+{
+	assert(t.class == TMP);
+	assert(cur_reg < 25
+			&& "ran out of temp registers, time to implement proper regalloc!");
+	/* note <=, we go one 'beyond' just to make sure that 0 fits */
+	while ((int64_t)vec_len(rmap) <= t.r) {
+		int64_t zero = 0;
+		vec_append(rmap, &zero);
+	}
+
+	if (reg_at(*rmap, t.r) == 0)
+		reg_at(*rmap, t.r) = tr_map[cur_reg++];
+}
+
+void regalloc(struct fn *f)
+{
+	/* very ugly, fix once we get the proper regalloc implemented */
+	cur_reg = 0;
+	struct vec rmap = vec_create(sizeof(int64_t));
+
+	/* here we would ideally do some kind of lifetime checking, to start
+	 * with we only assign to different temporary registers, we have enough
+	 * of them to work for some smaller test functions */
+	/* lifetime info would probably also be useful for saving callee-save
+	 * registers during calls, so that should probably also be done during
+	 * register allocation? maybe? */
+	foreach_blk(bi, f->blks) {
+		struct blk *b = blk_at(f->blks, bi);
+		foreach_insn(i, b->insns) {
+			struct insn n = insn_at(b->insns, i);
+			if (n.in[0].class == TMP) {
+				n.in[0] = rewrite_tmp(rmap, n.in[0]);
+			}
+
+			if (n.in[1].class == TMP) {
+				n.in[1] = rewrite_tmp(rmap, n.in[1]);
+			}
+
+			if (n.out.class == TMP) {
+				add_rewrite_rule(&rmap, n.out);
+				n.out = rewrite_tmp(rmap, n.out);
+			}
+
+			/* write back changes */
+			insn_at(b->insns, i) = n;
+
+			/* do this here since the register allocation is the
+			 * last stage before actually lowering to assembly, so
+			 * no possibility of dead code elimination or stuff like
+			 * that */
+			if (n.type == CALL)
+				f->has_calls = true;
+		}
+
+		if (b->cmp[0].class == TMP)
+			b->cmp[0] = rewrite_tmp(rmap, b->cmp[0]);
+
+		if (b->cmp[1].class == TMP)
+			b->cmp[1] = rewrite_tmp(rmap, b->cmp[1]);
+	}
+
+	f->max_callee_save = cur_reg;
+	vec_destroy(&rmap);
+}
diff --git a/src/ssa.c b/src/ssa.c
new file mode 100644
index 0000000..a9d6e6c
--- /dev/null
+++ b/src/ssa.c
@@ -0,0 +1,8 @@
+#include <qbt/ssa.h>
+
+void 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
+	 * (i.e. it must be taken as a block parameter) */
+}
diff --git a/tests/1.qbt b/tests/1.qbt
index e45553a..e87fddc 100644
--- a/tests/1.qbt
+++ b/tests/1.qbt
@@ -1,12 +1,19 @@
+do_stuff (i27 a0, i27 a1)
+{
+	i27 r0 = a0 + a1;
+	i27 r1 = a0 - a1;
+	=> (r0, r1);
+}
+
 /* this is a function of some kind */
-do_stuff (i27 a0, i27 a1 => i27,,)
+main (i27 a0, i27 a1)
 {
 	i27 r0 = a0 + a1;
 	/* r0 is reassigned */
-	(i27 r0, i27 r1,) = &do_more_stuff (r0, i9 29);
+	&do_stuff (r0, i9 29) => (r0, r1);
 	r0 < r1 -> somewhere_else;
-	=> (r1,,);
+	=> (r1);
 
 	somewhere_else:
-	=> (r0,,);
+	=> (r0);
 }
diff --git a/tests/2.qbt b/tests/2.qbt
new file mode 100644
index 0000000..9c63342
--- /dev/null
+++ b/tests/2.qbt
@@ -0,0 +1,4 @@
+main()
+{
+	=> ();
+}
diff --git a/tests/3.qbt b/tests/3.qbt
new file mode 100644
index 0000000..7d3217a
--- /dev/null
+++ b/tests/3.qbt
@@ -0,0 +1,13 @@
+main()
+{
+	i27 i = 0;
+	i27 max = 1000000000;
+	i27 sum = 0;
+
+top:
+	i27 sum = sum + i;
+	i27 i = i + i27 1;
+	i < max -> top;
+	&_putchar(sum) => ();
+	=> ();
+}
diff --git a/tests/4.qbt b/tests/4.qbt
new file mode 100644
index 0000000..0a5734a
--- /dev/null
+++ b/tests/4.qbt
@@ -0,0 +1,18 @@
+main()
+{
+	&_putchar (i9 'H') => ();
+	&_putchar (i9 'e') => ();
+	&_putchar (i9 'l') => ();
+	&_putchar (i9 'l') => ();
+	&_putchar (i9 'o') => ();
+	&_putchar (i9 ',') => ();
+	&_putchar (i9 ' ') => ();
+	&_putchar (i9 'W') => ();
+	&_putchar (i9 'o') => ();
+	&_putchar (i9 'r') => ();
+	&_putchar (i9 'l') => ();
+	&_putchar (i9 'd') => ();
+	&_putchar (i9 '!') => ();
+	&_putchar (i9 '\n') => ();
+	=> ();
+}
diff --git a/tests/5.qbt b/tests/5.qbt
new file mode 100644
index 0000000..213592e
--- /dev/null
+++ b/tests/5.qbt
@@ -0,0 +1,5 @@
+main()
+{
+	&_putchar(i9 'H') => ();
+	=> ();
+}