From f4be2429f38faba0c54862055f808cb242a7eb49 Mon Sep 17 00:00:00 2001 From: Kimplul Date: Wed, 3 Apr 2024 18:36:21 +0300 Subject: make regalloc work with ssa form + Still not ideal register allocator, but can be improved with some heuristics and potentially completely replaced in the future if so desired with graph coloring or something. --- README.md | 6 +- include/qbt/abi.h | 162 ++++++++++++------------ include/qbt/nodes.h | 168 +++++++++++++------------ include/qbt/parser.h | 12 +- include/qbt/vec.h | 8 +- src/abi.c | 14 ++- src/asm.c | 241 +++++++++++++++++++----------------- src/nodes.c | 8 +- src/regalloc.c | 339 ++++++++++++++++++++++++++++++++++++++++++--------- src/ssa.c | 4 +- src/vec.c | 13 +- 11 files changed, 624 insertions(+), 351 deletions(-) diff --git a/README.md b/README.md index 3c8feec..0352759 100644 --- a/README.md +++ b/README.md @@ -50,7 +50,7 @@ Optimizing middle/back end for triscv. | x41 | a21 | x42 | a22 | x43 | a23 -| x44 | a24 +| x44 | tmp0 | x45 | t7 | x46 | t8 | x47 | t9 @@ -68,7 +68,7 @@ Optimizing middle/back end for triscv. | x59 | t21 | x60 | t22 | x61 | t23 -| x62 | t24 +| x62 | tmp1 | x63 | s7 | x64 | s8 | x65 | s9 @@ -86,4 +86,4 @@ Optimizing middle/back end for triscv. | x77 | s21 | x78 | s22 | x79 | s23 -| x80 | s24 +| x80 | tmp2 diff --git a/include/qbt/abi.h b/include/qbt/abi.h index cc33dfc..2a915b2 100644 --- a/include/qbt/abi.h +++ b/include/qbt/abi.h @@ -170,87 +170,87 @@ enum { 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)\ +#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); diff --git a/include/qbt/nodes.h b/include/qbt/nodes.h index d3ddc5f..ff30b12 100644 --- a/include/qbt/nodes.h +++ b/include/qbt/nodes.h @@ -43,46 +43,46 @@ enum insn_type { RETVAL, }; -#define FOREACH_INSN_TYPE(M)\ - M(ADD)\ - M(SUB)\ - M(MUL)\ - M(DIV)\ - M(REM)\ - M(CALL)\ - M(LABEL)\ - M(STORE)\ - M(LOAD)\ - M(ALLOC)\ - M(COPY)\ - M(MOVE)\ - M(EQ)\ - M(NE)\ - M(LE)\ - M(GE)\ - M(LT)\ - M(GT)\ - M(NOT)\ - M(NEG)\ - M(LSHIFT)\ - M(RSHIFT)\ - M(BEQ)\ - M(BNE)\ - M(BLE)\ - M(BGE)\ - M(BLT)\ - M(BGT)\ - M(J)\ - M(ARG)\ - M(RETARG)\ - M(PARAM)\ - M(RET)\ - M(RETVAL)\ +#define FOREACH_INSN_TYPE(M) \ + M(ADD) \ + M(SUB) \ + M(MUL) \ + M(DIV) \ + M(REM) \ + M(CALL) \ + M(LABEL) \ + M(STORE) \ + M(LOAD) \ + M(ALLOC) \ + M(COPY) \ + M(MOVE) \ + M(EQ) \ + M(NE) \ + M(LE) \ + M(GE) \ + M(LT) \ + M(GT) \ + M(NOT) \ + M(NEG) \ + M(LSHIFT) \ + M(RSHIFT) \ + M(BEQ) \ + M(BNE) \ + M(BLE) \ + M(BGE) \ + M(BLT) \ + 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); + FOREACH_INSN_TYPE(CASE); } #undef CASE return "unknown"; @@ -105,8 +105,8 @@ struct val { enum val_class class; int64_t r; union { - int64_t v; - const char *s; + int64_t v; + const char *s; }; }; @@ -162,53 +162,53 @@ static inline bool hasnoclass(struct val v) static inline struct val noclass() { return (struct val){ - .class = NOCLASS, - .r = 0, - .v = 0, + .class = NOCLASS, + .r = 0, + .v = 0, }; } static inline struct val reg_val(int64_t r) { return (struct val){ - .class = REG, - .r = r + .class = REG, + .r = r }; } static inline struct val imm_ref(const char *s) { return (struct val){ - .class = REF, - .r = 0, - .s = s, + .class = REF, + .r = 0, + .s = s, }; } static inline struct val mem_val(int64_t base, int64_t offset) { return (struct val){ - .class = MEM, - .r = base, - .v = offset, + .class = MEM, + .r = base, + .v = offset, }; } static inline struct val imm_val(int64_t imm, int64_t type) { return (struct val) { - .class = IMM, - .r = type, - .v = imm, + .class = IMM, + .r = type, + .v = imm, }; } static inline struct val tmp_val(int64_t t) { return (struct val) { - .class = TMP, - .r = t, - .v = 0, + .class = TMP, + .r = t, + .v = 0, }; } @@ -218,34 +218,38 @@ static inline bool same_val(struct val v1, struct val v2) return false; switch (v1.class) { - case REG: return v1.r == v2.r; - case TMP: return v1.r == v2.r; - case IMM: return v1.v == v2.v; - case MEM: return v1.v == v2.v; - case REF: return v1.r == v2.r && v1.v == v2.v; - case NOCLASS: return true; + case REG: return v1.r == v2.r; + case TMP: return v1.r == v2.r; + case IMM: return v1.v == v2.v; + case MEM: return v1.v == v2.v; + case REF: return v1.r == v2.r && v1.v == v2.v; + case NOCLASS: return true; } /* shouldn't be reachable */ return false; } -static inline struct insn insn_create(enum insn_type o, enum val_type t, struct val r, struct val a0, struct val a1) +static inline struct insn insn_create(enum insn_type o, enum val_type t, + struct val r, struct val a0, + struct val a1) { return (struct insn) { - .type = o, - .vtype = t, - .out = r, - .in = {a0, a1} + .type = o, + .vtype = t, + .out = r, + .in = {a0, a1} }; } int64_t idalloc(struct fn *f, const char *id); int64_t idmatch(struct fn *f, const char *id); -void insadd(struct blk *b, enum insn_type o, enum val_type t, struct val r, struct val a0, struct val a1); +void insadd(struct blk *b, enum insn_type o, enum val_type t, struct val r, + struct val a0, struct val a1); -void finish_block(struct blk *b, enum insn_type cmp, struct val a0, struct val a1, const char *label); +void finish_block(struct blk *b, enum insn_type cmp, struct val a0, + struct val a1, const char *label); struct blk *new_block(struct fn *f); void destroy_block(struct blk *b); @@ -270,40 +274,46 @@ struct label_map { struct blk *b; }; -#define tmp_at(v, i)\ +#define val_at(v, i) \ + vect_at(struct val, v, i) + +#define foreach_val(iter, vals) \ + foreach_vec(iter, vals) + +#define tmp_at(v, i) \ vect_at(struct tmp_map, v, i) #define foreach_tmp(iter, tmps) \ foreach_vec(iter, tmps) -#define blk_at(v, i)\ +#define blk_at(v, i) \ vect_at(struct blk *, v, i) -#define blk_back(v)\ +#define blk_back(v) \ vect_at(struct blk *, v, vec_len(&v) - 1) -#define blk_pop(v)\ +#define blk_pop(v) \ vect_pop(struct blk *, v) -#define foreach_blk(iter, blocks)\ +#define foreach_blk(iter, blocks) \ foreach_vec(iter, blocks) -#define foreach_blk_param(iter, block_params)\ +#define foreach_blk_param(iter, block_params) \ foreach_vec(iter, block_params) -#define blk_param_at(v, i)\ +#define blk_param_at(v, i) \ vect_at(struct val, v, i) -#define label_at(v, i)\ +#define label_at(v, i) \ vect_at(struct label_map, v, i) -#define foreach_label(iter, labels)\ +#define foreach_label(iter, labels) \ foreach_vec(iter, labels) -#define insn_at(v, i)\ +#define insn_at(v, i) \ vect_at(struct insn, v, i) -#define foreach_insn(iter, insns)\ +#define foreach_insn(iter, insns) \ foreach_vec(iter, insns) #endif /* NODES_H */ diff --git a/include/qbt/parser.h b/include/qbt/parser.h index 34912c9..df17bea 100644 --- a/include/qbt/parser.h +++ b/include/qbt/parser.h @@ -44,22 +44,22 @@ struct parser *create_parser(); void parse(struct parser *p, const char *fname, const char *buf); void destroy_parser(struct parser *p); -#define foreach_fn(iter, v)\ +#define foreach_fn(iter, v) \ foreach_vec(iter, v) -#define foreach_data(iter, v)\ +#define foreach_data(iter, v) \ foreach_vec(iter, v) -#define foreach_str(iter, v)\ +#define foreach_str(iter, v) \ foreach_vec(iter, v) -#define fn_at(v, i)\ +#define fn_at(v, i) \ vect_at(struct fn_map, v, i) -#define data_at(v, i)\ +#define data_at(v, i) \ vect_at(struct data_map, v, i) -#define str_at(v, i)\ +#define str_at(v, i) \ vect_at(char *, v, i) #endif /* PARSER_H */ diff --git a/include/qbt/vec.h b/include/qbt/vec.h index 727c110..471e127 100644 --- a/include/qbt/vec.h +++ b/include/qbt/vec.h @@ -12,18 +12,20 @@ struct vec { struct vec vec_create(size_t s); void vec_destroy(struct vec *v); +void vec_reset(struct vec *v); + size_t vec_len(struct vec *v); void *vec_at(struct vec *v, size_t i); void *vec_pop(struct vec *v); void vec_append(struct vec *v, void *n); -#define foreach_vec(iter, v)\ +#define foreach_vec(iter, v) \ for (size_t iter = 0, __n = vec_len(&v); iter < __n; ++iter) -#define vect_at(type, v, i)\ +#define vect_at(type, v, i) \ *(type *)vec_at(&v, i) -#define vect_pop(type, v)\ +#define vect_pop(type, v) \ *(type *)vec_pop(&v) #endif /* VEC_H */ diff --git a/src/abi.c b/src/abi.c index cb92190..80f34e4 100644 --- a/src/abi.c +++ b/src/abi.c @@ -19,7 +19,7 @@ static struct insn rewrite_param(struct insn n) 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"); + && "stack argument passing not yet supported"); return insn_create(MOVE, I27, n.out, nth_ar(nth_param), noclass()); } @@ -41,9 +41,11 @@ static struct insn rewrite_arg(struct insn n) 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()); + 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()); + return insn_create(COPY, I27, nth_ar(nth_arg), n.in[0], + noclass()); assert("illegal arg type"); abort(); @@ -57,9 +59,11 @@ static struct insn rewrite_retarg(struct insn n) 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()); + 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()); + return insn_create(COPY, I27, nth_ar(nth_arg), n.in[0], + noclass()); assert("illegal retval type"); abort(); diff --git a/src/asm.c b/src/asm.c index e177c4e..fd4d68a 100644 --- a/src/asm.c +++ b/src/asm.c @@ -8,87 +8,87 @@ 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"; + 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"); @@ -114,7 +114,7 @@ static void save_state(struct fn *f, FILE *o) for (size_t i = 0; i < f->max_callee_save; ++i) { fprintf(o, "st w s%zi, -%zi(fp)\n", - i, 3 * i + 9); + i, 3 * i + 9); } } @@ -122,7 +122,7 @@ 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); + i, 3 * i + 9); } if (f->has_calls) @@ -134,22 +134,23 @@ static void restore_state(struct fn *f, FILE *o) static void output_move(struct insn n, FILE *o) { - fprintf(o, "mv %s, %s\n", - rname(n.out), rname(n.in[0])); + if (!same_val(n.out, n.in[0])) + 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])); + 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); + rname(n.out), rname(n.in[0]), (long long int)n.in[1].v); return; } @@ -161,16 +162,18 @@ 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])); + 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); + 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); + rname(n.out), rname(n.in[0]), + (long long int)n.in[1].v); return; } @@ -181,7 +184,7 @@ static void output_sub(struct insn n, FILE *o) 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); + rname(n.out), (long long int)n.in[0].v); } static void output_call(struct insn n, FILE *o) @@ -205,13 +208,13 @@ static void output_insn(struct insn n, FILE *o) * 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(); + 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(); } } @@ -219,16 +222,16 @@ 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); + 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); + 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) @@ -249,12 +252,25 @@ static void output_j(struct blk *b, struct fn *f, FILE *o) 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(); + 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(); + } +} + +static void output_moves(struct vec *params, struct vec *args, FILE *o) +{ + /* move arguments to parameters */ + assert(vec_len(params) == vec_len(args)); + foreach_blk_param(pi, *params) { + struct val p = blk_param_at(*params, pi); + struct val a = blk_param_at(*args, pi); + struct insn i = insn_create(MOVE, NOTYPE, p, a, noclass()); + output_move(i, o); } } @@ -265,13 +281,20 @@ void output(struct fn *f, FILE *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); + f->name, (long long int)b->id); foreach_insn(i, b->insns) { struct insn n = insn_at(b->insns, i); output_insn(n, o); } + if (b->s2) + output_moves(&b->s2->params, &b->args2, o); + output_branch(b, f, o); + + /* J is again the special case */ + if (b->s1 && b->btype != J) + output_moves(&b->s1->params, &b->args1, o); } } diff --git a/src/nodes.c b/src/nodes.c index a6ff0b8..05f96fe 100644 --- a/src/nodes.c +++ b/src/nodes.c @@ -6,7 +6,8 @@ #include #include -void insadd(struct blk *b, enum insn_type o, enum val_type t, struct val r, struct val a0, struct val a1) +void insadd(struct blk *b, enum insn_type o, enum val_type t, struct val r, + struct val a0, struct val a1) { struct insn i = insn_create(o, t, r, a0, a1); vec_append(&b->insns, &i); @@ -35,7 +36,8 @@ int64_t idmatch(struct fn *f, const char *id) return -1; } -void finish_block(struct blk *b, enum insn_type cmp, struct val a0, struct val a1, const char *label) +void finish_block(struct blk *b, enum insn_type cmp, struct val a0, + struct val a1, const char *label) { assert(cmp >= BEQ && cmp <= RET && "illegal comparison type for block"); b->btype = cmp; @@ -198,7 +200,7 @@ void dump_block(struct blk *b) { printf("//\t/*** block %lld ", (long long)b->id); if (b->name) printf("\"%s\" ", b->name); - + printf("("); foreach_blk_param(pi, b->params) { struct val v = blk_param_at(b->params, pi); diff --git a/src/regalloc.c b/src/regalloc.c index 474e5a4..68e68a2 100644 --- a/src/regalloc.c +++ b/src/regalloc.c @@ -1,90 +1,317 @@ #include +#include #include #include #include +/* first try to use temporaries, then callee-save, then finally args. + * Idea is that callee-save cost is paid once at the start of the function call, + * after that they're free. Argument registers are generally important to keep + * free to make sure function calls in loops etc. don't have to shuffle + * registers around as much */ static const int64_t tr_map[] = { + RT0, RT1, RT2, RT3, RT4, RT5, RT6, RT7, RT8, RT9, + RT10, RT11, RT12, RT13, RT14, RT15, RT16, RT17, RT18, RT19, + RT20, RT21, RT22, RT23, + 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 + RS20, RS21, RS22, RS23, + + RA0, RA1, RA2, RA3, RA4, RA5, RA6, RA7, RA8, RA9, + RA10, RA11, RA12, RA13, RA14, RA15, RA16, RA17, RA18, RA19, + RA20, RA21, RA22, RA23, }; -#define reg_at(v, i)\ - vect_at(int64_t, v, i) +#define reg_at(v, i) \ + vect_at(struct val, v, i) -static struct val rewrite_tmp(struct vec rmap, struct val t) +static bool has_rewrite_rule(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); + if (t.r >= (int64_t)vec_len(rmap)) + return false; + + struct val r = reg_at(*rmap, t.r); + return r.class != NOCLASS; } -static size_t cur_reg = 0; -static void add_rewrite_rule(struct vec *rmap, struct val t) +static struct val rewrite_tmp(struct vec *rmap, struct val t) { assert(t.class == TMP); - assert(cur_reg < 25 - && "ran out of temp registers, time to implement proper regalloc!"); + assert(t.r < (int64_t)vec_len(rmap)); + struct val r = reg_at(*rmap, t.r); + assert(r.class != NOCLASS); + return r; +} + +static void add_rewrite_rule(struct vec *rmap, struct val from, struct val to) +{ + assert(from.class == TMP); + assert(to.class == REG); /* 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); + while ((int64_t)vec_len(rmap) <= from.r) { + struct val no = noclass(); + vec_append(rmap, &no); } - if (reg_at(*rmap, t.r) == 0) - reg_at(*rmap, t.r) = tr_map[cur_reg++]; + reg_at(*rmap, from.r) = to; } -void regalloc(struct fn *f) +static void add_hint(struct vec *hints, struct val from, struct val to) { - /* 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]); - } + /* kind of a hack */ + add_rewrite_rule(hints, from, to); +} - if (n.in[1].class == TMP) { - n.in[1] = rewrite_tmp(rmap, n.in[1]); - } +static struct val get_hint(struct vec *hints, struct val from) +{ + if ((int64_t)vec_len(hints) <= from.r) + return noclass(); - if (n.out.class == TMP) { - add_rewrite_rule(&rmap, n.out); - n.out = rewrite_tmp(rmap, n.out); - } + return rewrite_tmp(hints, from); +} + +struct lifetime { + struct val v; + size_t start; + size_t end; + size_t used; +}; + +#define lifetime_at(lifetimes, i) \ + vect_at(struct lifetime, lifetimes, i) + +#define foreach_lifetime(iter, lifetimes) \ + foreach_vec(iter, lifetimes) + +static void add_def(struct vec *lifetimes, struct val v, size_t i) +{ + while ((int64_t)vec_len(lifetimes) <= v.r) { + vec_append(lifetimes, &(struct lifetime){noclass(), 0, 0, 0}); + } + + /* I guess a def isn't techincally a 'use' but good enough, we assume + * that unused variables have already been removed by some earlier stage + * (not currently true but that's the intention) */ + lifetime_at(*lifetimes, v.r) = (struct lifetime){v, i, 0, 1}; +} + +static void add_use(struct vec *lifetimes, struct val v, size_t i) +{ + assert((int64_t)vec_len(lifetimes) > v.r); + struct lifetime l = lifetime_at(*lifetimes, v.r); + assert(l.used); + l.used++; + l.end = i; + lifetime_at(*lifetimes, v.r) = l; +} + +static void collect_lifetimes(struct blk *b, struct vec *hints, + struct vec *lifetimes) +{ + foreach_blk_param(pi, b->params) { + struct val v = blk_param_at(b->params, pi); + add_def(lifetimes, v, 0); + } + + size_t pos = 1; + foreach_insn(ii, b->insns) { + struct insn i = insn_at(b->insns, ii); + if (i.in[0].class == TMP) + add_use(lifetimes, i.in[0], pos); + + if (i.in[1].class == TMP) + add_use(lifetimes, i.in[1], pos); + + if (i.out.class == TMP) + add_def(lifetimes, i.out, pos); + + /* collect some early hints */ + if (i.type == MOVE) { + /* input arguments, retvals */ + if (i.out.class == TMP && i.in[0].class == REG) + add_hint(hints, i.out, i.in[0]); + + if (i.out.class == REG && i.in[0].class == TMP) + add_hint(hints, i.in[0], i.out); + } + + pos++; + } + + if (b->cmp[0].class == TMP) + add_use(lifetimes, b->cmp[0], pos); + + if (b->cmp[1].class == TMP) + add_use(lifetimes, b->cmp[1], pos); + + foreach_blk_param(pi, b->args1) { + struct val v = blk_param_at(b->args1, pi); + add_use(lifetimes, v, pos); + } + + foreach_blk_param(pi, b->args2) { + struct val v = blk_param_at(b->args2, pi); + add_use(lifetimes, v, pos); + } +} + +static void build_active(struct vec *active, struct vec *lifetimes, size_t i) +{ + struct lifetime ref = lifetime_at(*lifetimes, i); + foreach_lifetime(li, *lifetimes) { + struct lifetime l = lifetime_at(*lifetimes, li); + if (l.used == 0) + continue; - /* write back changes */ - insn_at(b->insns, i) = n; + if (l.end < ref.start) + continue; - /* 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 (l.start > ref.end) + continue; + + vec_append(active, &l); + } +} + +static void build_reserved(struct vec *reserved, struct vec *active, + struct vec *rmap) +{ + foreach_lifetime(li, *active) { + struct lifetime l = lifetime_at(*active, li); + if (l.used == 0) + continue; + + if (has_rewrite_rule(rmap, l.v)) { + struct val act = rewrite_tmp(rmap, l.v); + vec_append(reserved, &act); + } + } +} + +static bool reg_free(struct vec *reserved, struct val f) +{ + assert(f.class == REG); + /* not the fastest way in the world, but good enough for now */ + foreach_val(ri, *reserved) { + struct val r = val_at(*reserved, ri); + if (same_val(r, f)) + return false; + } + + return true; +} + +static struct val find_free_reg(struct vec *reserved) +{ + for (size_t i = 0; i < sizeof(tr_map) / sizeof(tr_map[0]); ++i) { + struct val r = reg_val(tr_map[i]); + if (reg_free(reserved, r)) + return r; + } + + /* handle spill case later */ + assert(0 && + "ran out of registers, time to implement proper spill handling"); + abort(); +} + +static void build_rmap(struct vec *hints, struct vec *lifetimes, + struct vec *rmap) +{ + struct vec active = vec_create(sizeof(struct lifetime)); + struct vec reserved = vec_create(sizeof(struct val)); + + foreach_lifetime(li, *lifetimes) { + struct lifetime l = lifetime_at(*lifetimes, li); + if (l.used == 0) + continue; + + vec_reset(&active); + build_active(&active, lifetimes, li); + build_reserved(&reserved, &active, rmap); + + struct val h = get_hint(hints, l.v); + if (h.class != NOCLASS) { + if (reg_free(&reserved, h)) { + add_rewrite_rule(rmap, l.v, h); + continue; + } } - if (b->cmp[0].class == TMP) - b->cmp[0] = rewrite_tmp(rmap, b->cmp[0]); + /* eventually we should select the spill register only for the + * least used register, but that's a bit more complicated than + * just this linear scan */ + struct val f = find_free_reg(&reserved); + add_rewrite_rule(rmap, l.v, f); + } +} + +/* has_calls is kind of in an iffy place but I guess it's fine */ +static void do_rewrites(struct blk *b, struct vec *rmap, struct fn *f) +{ + foreach_blk_param(pi, b->params) { + struct val p = blk_param_at(b->params, pi); + blk_param_at(b->params, pi) = rewrite_tmp(rmap, p); + } + + foreach_insn(ii, b->insns) { + struct insn i = insn_at(b->insns, ii); + if (i.in[0].class == TMP) + i.in[0] = rewrite_tmp(rmap, i.in[0]); + + if (i.in[1].class == TMP) + i.in[1] = rewrite_tmp(rmap, i.in[1]); + + if (i.out.class == TMP) + i.out = rewrite_tmp(rmap, i.out); + + /** @todo save caller-save at callsites here */ + if (i.type == CALL) + f->has_calls = true; + + /* write back changes, christ I forget this a lot */ + insn_at(b->insns, ii) = i; + } + + 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]); + + foreach_blk_param(pi, b->args1) { + struct val p = blk_param_at(b->args1, pi); + blk_param_at(b->args1, pi) = rewrite_tmp(rmap, p); + } + + foreach_blk_param(pi, b->args2) { + struct val p = blk_param_at(b->args2, pi); + blk_param_at(b->args2, pi) = rewrite_tmp(rmap, p); + } +} + +/* assumes ssa form */ +void regalloc(struct fn *f) +{ + struct vec hints = vec_create(sizeof(struct val)); + struct vec lifetimes = vec_create(sizeof(struct lifetime)); + struct vec rmap = vec_create(sizeof(struct val)); - if (b->cmp[1].class == TMP) - b->cmp[1] = rewrite_tmp(rmap, b->cmp[1]); + /* here it would probably make sense to iterate through lifetimes in + * order of priority, like loop nesting/count etc */ + foreach_blk(bi, f->blks) { + struct blk *b = blk_at(f->blks, bi); + vec_reset(&lifetimes); + /** @todo collect hints from args/params */ + collect_lifetimes(b, &hints, &lifetimes); + build_rmap(&hints, &lifetimes, &rmap); + do_rewrites(b, &rmap, f); + /** @todo forward_hints(b, &hints, &rmap) */ } - f->max_callee_save = cur_reg; + vec_destroy(&hints); + vec_destroy(&lifetimes); vec_destroy(&rmap); } diff --git a/src/ssa.c b/src/ssa.c index 59e7254..96d1eb1 100644 --- a/src/ssa.c +++ b/src/ssa.c @@ -78,7 +78,7 @@ static void build_params(struct blk *b, int visited) struct val in2 = i.in[1]; if (in2.class == TMP && !has_val(&generated, in2)) add_val(&required, in2); - + struct val out = i.out; if (out.class == TMP) { add_val(&generated, out); @@ -147,7 +147,7 @@ static void collect_params(struct blk *b, int visited) } } -#define tmpval_at(rmap, i)\ +#define tmpval_at(rmap, i) \ vect_at(struct val, rmap, i) static void add_rewrite_rule(struct vec *rmap, struct val from, struct val to) diff --git a/src/vec.c b/src/vec.c index 4ba92fb..e487162 100644 --- a/src/vec.c +++ b/src/vec.c @@ -7,13 +7,18 @@ struct vec vec_create(size_t ns) { return (struct vec) { - .n = 0, - .s = 1, - .ns = ns, - .buf = malloc(ns), + .n = 0, + .s = 1, + .ns = ns, + .buf = malloc(ns), }; } +void vec_reset(struct vec *v) +{ + v->n = 0; +} + size_t vec_len(struct vec *v) { return v->n; -- cgit v1.3