aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--README.md89
-rw-r--r--include/qbt/abi.h258
-rw-r--r--include/qbt/asm.h10
-rw-r--r--include/qbt/nodes.h21
-rw-r--r--include/qbt/opt.h7
-rw-r--r--include/qbt/regalloc.h8
-rw-r--r--include/qbt/ssa.h8
-rw-r--r--src/abi.c96
-rw-r--r--src/asm.c277
-rw-r--r--src/main.c7
-rw-r--r--src/nodes.c21
-rw-r--r--src/opt.c12
-rw-r--r--src/parser.y128
-rw-r--r--src/regalloc.c90
-rw-r--r--src/ssa.c8
-rw-r--r--tests/1.qbt15
-rw-r--r--tests/2.qbt4
-rw-r--r--tests/3.qbt13
-rw-r--r--tests/4.qbt18
-rw-r--r--tests/5.qbt5
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') => ();
+ => ();
+}
generated by cgit v1.3 (git 2.53.0) at 2026-08-27 02:31:56 +0000