From 82cac0ae5d4e335719445857ab16ffdf05413222 Mon Sep 17 00:00:00 2001 From: lemon Date: Wed, 31 May 2023 23:31:58 +0200 Subject: regalloc skeleton --- Makefile | 5 ++-- amd64/all.h | 32 ++++++++++++++++++++++ amd64/sysv.c | 3 +++ common.h | 20 +++++++++++--- io.c | 24 ++++++++++------- ir.c | 24 ++++++++++++++++- ir.h | 39 ++++++++++++++++++++++----- irdump.c | 11 +++++--- mem.c | 4 +++ parse.c | 73 ++++++++++++++++++++++++++++++------------------- regalloc.c | 88 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ targ.c | 16 ++++++----- test.c | 19 +++++++++++++ 13 files changed, 298 insertions(+), 60 deletions(-) create mode 100644 amd64/all.h create mode 100644 amd64/sysv.c create mode 100644 regalloc.c diff --git a/Makefile b/Makefile index f9f3e12..90bac1b 100644 --- a/Makefile +++ b/Makefile @@ -1,4 +1,4 @@ -SRC=main.c io.c mem.c parse.c lex.c type.c targ.c eval.c ir.c irdump.c +SRC=main.c io.c mem.c parse.c lex.c type.c targ.c eval.c ir.c irdump.c regalloc.c amd64/sysv.c CFLAGS=-Wall -std=c11 -pedantic OBJ=$(patsubst %.c,obj/%.o,$(SRC)) OUT=cchomp @@ -16,7 +16,7 @@ $(OUT): $(OBJ) $(CC) $(CFLAGS) -o $@ $(OBJ) obj/%.o: %.c common.h - @mkdir -p obj/ + @mkdir -p `dirname $@` $(CC) $(CFLAGS) -c -o $@ $< obj/main.o: parse.h @@ -26,6 +26,7 @@ obj/irdump.o: ir.h op.def obj/lex.o: parse.h obj/eval.o: parse.h obj/io.o: parse.h keywords.def +obj/amd64/sysv.o: ir.h amd64/all.h clean: $(RM) -r obj/ $(OUT) diff --git a/amd64/all.h b/amd64/all.h new file mode 100644 index 0000000..ae21d3d --- /dev/null +++ b/amd64/all.h @@ -0,0 +1,32 @@ +#include "../ir.h" + + +#define LIST_REGS(_) \ + _(RAX) _(RCX) _(RDX) _(RBX) _(RSP) _(RBP) _(RSI) _(RDI) \ + _(R8) _(R9) _(R10) _(R11) _(R12) _(R13) _(R14) _(R15) \ + _(XMM0) _(XMM1) _(XMM2) _(XMM3) _(XMM4) _(XMM5) _(XMM6) _(XMM7) \ + _(XMM8) _(XMM9) _(XMM10) _(XMM11) _(XMM12) _(XMM13) _(XMM14) _(XMM15) + +enum { + Rxxx, +#define R(r) r, + LIST_REGS(R) +#undef R +}; + +const char amd64_rnames[][6] = { + "?", +#define R(r) #r, + LIST_REGS(R) +#undef R +}; + +const struct mctarg t_amd64_sysv = { + .gpr0 = RAX, .ngpr = R15 - RAX + 1, + .fpr0 = XMM0, .nfpr = XMM15 - XMM0 + 1, + .rcallee = {{1<entry = fn->curblk = alloc(&fn->arena, sizeof(struct block), 0); + memset(fn->entry, 0, sizeof *fn->entry); fn->entry->lprev = fn->entry->lnext = fn->entry; } @@ -264,4 +265,25 @@ putjump(struct function *fn, enum jumpkind j, union ref arg, struct block *t, st fn->curblk = NULL; } +static void +freefn(struct function *fn) +{ + struct block *blk = fn->entry; + do { + vfree(&blk->phi); + vfree(&blk->ins); + blk = blk->lnext; + } while (blk != fn->entry); +} + +void +irfini(struct function *fn) +{ + regalloc(fn); + efmt("after regalloc:\n"); + irdump(fn, fn->name); + + freefn(fn); +} + /* vim:set ts=3 sw=3 expandtab: */ diff --git a/ir.h b/ir.h index b8095d9..f1a511e 100644 --- a/ir.h +++ b/ir.h @@ -6,7 +6,7 @@ enum irclass { KF4, KF8, }; -#define kisint(k) in_range((k), KI4, KIP) +#define kisint(k) in_range((k), KI4, KPTR) #define kisflt(k) in_range((k), KF4, KF8) union irtype { @@ -56,7 +56,13 @@ struct phi { }; enum refkind { - RNONE, RTMP, RARG, RICON, RXCON, RSYM, REXT + RNONE, + RTMP, /* reference to another instruction's result */ + RARG, /* function argument */ + RICON, /* small integer constants */ + RXCON, /* other constants (incl. external symbols) */ + REXT, /* reference to extra data for Ocall and Ophi */ + RREG, /* machine register */ }; union ref { @@ -73,8 +79,8 @@ enum op { }; struct instr { - uchar op; - uchar cls; + uchar op, cls; + uchar reg, hint; union ref l, r; }; @@ -85,9 +91,9 @@ enum jumpkind { struct block { int id; struct block *s1, *s2; - struct { uchar t; union ref arg; } jmp; vec_of(ushort) phi; vec_of(ushort) ins; + struct { uchar t; union ref arg; } jmp; struct block *lprev, *lnext; }; @@ -101,13 +107,27 @@ struct function { bool globl; }; +enum { MAXREGS = 32 }; + +struct mctarg { + short gpr0, /* first gpr */ + ngpr, /* gpr count */ + fpr0, /* first fpr */ + nfpr; /* fpr count */ + struct bitset rcallee[1], /* callee-saved */ + rglob[1]; /* globally live (never used for regalloc) */ + const char (*rnames)[6]; +}; + extern uchar type2cls[]; extern uchar cls2siz[]; extern const uchar siz2intcls[]; -void irinit(struct function *); #define NOREF ((union ref) {0}) #define mkref(t, x) ((union ref) {{ (t), (x) }}) -#define mkzerocon() ((union irref){ RICON, 0 }) +#define mkzerocon() ((union ref) {{ RICON, 0 }}) +#define mkinstr(O, C, ...) ((struct instr) { .op = (O), .cls = (C), .reg=0,.hint=0, __VA_ARGS__ }) +void irinit(struct function *); +void irfini(struct function *); union irtype mkirtype(union type); union ref mkintcon(struct function *, enum irclass, vlong); union ref mkfltcon(struct function *, enum irclass, double); @@ -121,6 +141,11 @@ union ref addphi(struct function *, enum irclass cls, struct block **blk, union struct block *newblk(struct function *); void useblk(struct function *, struct block *); void putjump(struct function *, enum jumpkind, union ref arg, struct block *t, struct block *f); +void insertinstr(struct block *, int idx, struct instr); +void delinstr(struct block *, int idx); + void irdump(struct function *, const char *fname); +void regalloc(struct function *); + /* vim:set ts=3 sw=3 expandtab: */ diff --git a/irdump.c b/irdump.c index f225431..425c7d2 100644 --- a/irdump.c +++ b/irdump.c @@ -37,8 +37,8 @@ dumpref(enum op o, union ref ref) case KI4: efmt("%d", con->i4); break; case KI8: efmt("%ld", con->i8); break; case KPTR: efmt("%'x", con->i8); break; - case KF4: efmt("%f", con->fs); break; - case KF8: efmt("%f", con->fd); break; + case KF4: efmt("%fs", con->fs); break; + case KF8: efmt("%fd", con->fd); break; default: assert(0); } break; @@ -89,8 +89,11 @@ dumpinst(const struct instr *ins) { int i; efmt(" "); - if (ins->cls) - efmt("%s %%%d = ", clsname[ins->cls], ins - instr); + if (ins->cls) { + efmt("%s %%%d", clsname[ins->cls], ins - instr); + if (ins->reg) efmt("(%ls)", mctarg->rnames[ins->reg]); + efmt(" = "); + } efmt("%s ", opname[ins->op]); for (i = 0; i < opnarg[ins->op]; ++i) { if (i) efmt(", "); diff --git a/mem.c b/mem.c index c16fe54..07519d5 100644 --- a/mem.c +++ b/mem.c @@ -111,6 +111,10 @@ freearena(struct arena *ar) prev = ar->prev; if (ar->dyn) free(ar); + else { + assert(!prev); + ar->n = 0; + } } } diff --git a/parse.c b/parse.c index f243733..5b38637 100644 --- a/parse.c +++ b/parse.c @@ -954,7 +954,7 @@ expraddr(struct function *fn, const struct expr *ex) { struct decl *decl; union ref r; - struct instr ins; + struct instr ins = {0}; switch (ex->t) { case ESYM: @@ -1037,8 +1037,10 @@ cvt(struct function *fn, enum typetag to, enum typetag from, union ref ref) ins.cls = kto; ins.l = ref; if (kisflt(kto) || kisflt(kfrom)) { - if (kto == KPTR) kto = siz2intcls[cls2siz[kto]]; - if (kfrom == KPTR) kfrom = siz2intcls[cls2siz[kfrom]]; + if (ref.t == RICON) { + assert(kisflt(kto) && kisint(kfrom)); + return mkfltcon(fn, kto, kto == KF4 ? (float)ref.i : (double)ref.i); + } if (kisflt(kto) && kfrom == KI4) ins.op = issignedt(from) ? Ocvts4f : Ocvtu4f; else if (to == TYBOOL && kisflt(kfrom)) ins.op = Oneq, ins.r = mkfltcon(fn, kfrom, 0.0); else if (kisflt(kto) && kfrom == KI8) ins.op = issignedt(from) ? Ocvts8f : Ocvtu8f; @@ -1048,7 +1050,16 @@ cvt(struct function *fn, enum typetag to, enum typetag from, union ref ref) else if (kfrom == KF8) ins.op = issignedt(to) ? Ocvtf8s : Ocvtf8u; else assert(0); } else { - if (to == TYBOOL) ins.op = Oneq, ins.r = mkzerocon(); + if (to == TYBOOL) { + if (from == TYBOOL) return ref; + if (ref.t == RTMP) { + extern struct instr instr[]; + /* these instrs already have output range of [0,1] */ + if (in_range(instr[ref.idx].op, Oequ, Oulte) || instr[ref.idx].op == Onot) + return ref; + } + ins.op = Oneq, ins.r = mkzerocon(); + } else if (kfrom == KI4 && issignedt(from)) ins.op = Oexts4; else if (kfrom == KI4) ins.op = Oextu4; else ins.op = Ocopy; @@ -1059,7 +1070,7 @@ cvt(struct function *fn, enum typetag to, enum typetag from, union ref ref) static union ref narrow(struct function *fn, enum irclass to, enum typetag tt, union ref ref) { - struct instr ins; + struct instr ins = {0}; assert(isintt(tt) || tt == TYPTR); if (targ_primsizes[tt] >= cls2siz[to]) return ref; ins.cls = to; @@ -1098,12 +1109,12 @@ genptroff(struct function *fn, enum op op, uint siz, union ref ptr, off = mkintcon(fn, cls, idx.i * siz); else if ((siz & (siz-1)) == 0) /* is power of 2 */ off = addinstr(fn, - (struct instr) { Oshl, cls, .l = idx, .r = mkintcon(fn, cls, ilog2(siz)) }); + mkinstr(Oshl, cls, .l = idx, .r = mkintcon(fn, cls, ilog2(siz)))); else off = addinstr(fn, - (struct instr) { Omul, cls, .l = idx, .r = mkintcon(fn, cls, siz) }); + mkinstr(Omul, cls, .l = idx, .r = mkintcon(fn, cls, siz))); assert(in_range(op, Oadd, Osub)); - return addinstr(fn, (struct instr) { op, KPTR, .l = ptr, .r = off }); + return addinstr(fn, mkinstr(op, KPTR, .l = ptr, .r = off)); } union ref @@ -1111,12 +1122,12 @@ genptrdiff(struct function *fn, uint siz, union ref a, union ref b) { uint cls = type2cls[targ_ptrdifftype]; assert(siz > 0); - a = addinstr(fn, (struct instr) { Osub, cls, .l = a, .r = b }); + a = addinstr(fn, mkinstr(Osub, cls, .l = a, .r = b)); if (siz == 1) return a; else if ((siz & (siz-1)) == 0) /* is power of 2 */ - return addinstr(fn, (struct instr) { Osar, cls, a, mkintcon(fn, cls, ilog2(siz)) }); + return addinstr(fn, mkinstr(Osar, cls, a, mkintcon(fn, cls, ilog2(siz)))); else - return addinstr(fn, (struct instr) { Odiv, cls, a, mkintcon(fn, cls, siz) }); + return addinstr(fn, mkinstr(Odiv, cls, a, mkintcon(fn, cls, siz))); } /* used to emit the jumps in an in if (), while (), etc condition */ @@ -1173,8 +1184,8 @@ struct condphis { }; static void -condexprrec(struct function *fn, const struct expr *ex, bool tobool, - struct condphis *phis, struct block *end, struct block *zero) +condexprrec(struct function *fn, const struct expr *ex, struct condphis *phis, + int boolcon, struct block *end, struct block *zero) { struct block *tr, *fl, *next; union ref r; @@ -1184,31 +1195,37 @@ condexprrec(struct function *fn, const struct expr *ex, bool tobool, } if (ex->t == ELOGAND) { next = newblk(fn); - condexprrec(fn, &ex->sub[0], 0, phis, next, end); + condexprrec(fn, &ex->sub[0], phis, 0, next, end); useblk(fn, next); - condexprrec(fn, &ex->sub[1], 1, phis, end, zero); + condexprrec(fn, &ex->sub[1], phis, -2, end, zero); } else if (ex->t == ELOGIOR) { next = newblk(fn); - condexprrec(fn, &ex->sub[0], 1, phis, end, next); + condexprrec(fn, &ex->sub[0], phis, 1, end, next); useblk(fn, next); - condexprrec(fn, &ex->sub[1], 1, phis, end, zero); + condexprrec(fn, &ex->sub[1], phis, -2, end, zero); } else if (ex->t == ECOND) { tr = newblk(fn); fl = newblk(fn); condjump(fn, &ex->sub[0], tr, fl); useblk(fn, tr); - condexprrec(fn, &ex->sub[1], 0, phis, end, zero); + condexprrec(fn, &ex->sub[1], phis, -1, end, zero); useblk(fn, fl); - condexprrec(fn, &ex->sub[2], 0, phis, end, zero); + condexprrec(fn, &ex->sub[2], phis, -1, end, zero); } else { r = exprvalue(fn, ex); - if (tobool) r = cvt(fn, TYBOOL, ex->ty.t, r); vpush(&phis->blk, fn->curblk); - vpush(&phis->ref, r); - if (zero) - putjump(fn, Jbcnd, r, end, zero); + if (boolcon == -2) + r = cvt(fn, TYBOOL, ex->ty.t, r); + if (boolcon >= 0) + vpush(&phis->ref, mkintcon(fn, KI4, boolcon)); else + vpush(&phis->ref, r); + if (zero) { + putjump(fn, Jbcnd, r, end, zero); + } else { + assert(boolcon < 0); putjump(fn, Jb, NOREF, end, NULL); + } } } @@ -1223,7 +1240,7 @@ condexprvalue(struct function *fn, const struct expr *ex) VINIT(refbuf, arraylength(refbuf))}; struct block *dst = newblk(fn); union ref r; - condexprrec(fn, ex, 0, &phis, dst, NULL); + condexprrec(fn, ex, &phis, -1, dst, NULL); useblk(fn, dst); r = addphi(fn, type2cls[ex->ty.t], phis.blk.p, phis.ref.p, phis.blk.n); vfree(&phis.blk); @@ -1639,8 +1656,7 @@ block(struct parser *pr, struct function *fn) siz = typesize(decl.ty); nalloc = siz/align + ((siz&(align-1)) != 0); EMITS { - decl.id = addinstr(fn, - (struct instr) { op, KPTR, mkintcon(fn, KI4, nalloc) }).idx; + decl.id = addinstr(fn, mkinstr(op, KPTR, mkintcon(fn, KI4, nalloc))).idx; } if (st.varini) { putdecl(pr, &decl); @@ -1695,7 +1711,7 @@ function(struct parser *pr, struct function *fn, const char **pnames, const stru siz = typesize(arg.ty); nalloc = siz/align + ((siz&(align-1)) != 0); EMITS { - struct instr alloca = { op, KPTR, mkintcon(fn, KI4, nalloc) }; + struct instr alloca = { op, KPTR, .l = mkintcon(fn, KI4, nalloc) }; arg.id = addinstr(fn, alloca).idx; genstore(fn, arg.ty, mkref(RTMP, arg.id), mkref(RARG, i)); } @@ -2370,7 +2386,8 @@ parse(struct parser *pr) putdecl(pr, &decl); irinit(&fn); function(pr, &fn, st.pnames, st.pspans); - if (!nerror) irdump(&fn, decl.name); + /* if (!nerror) irdump(&fn, decl.name); */ + irfini(&fn); } else if (decl.name) { putdecl(pr, &decl); if (st.varini) { diff --git a/regalloc.c b/regalloc.c new file mode 100644 index 0000000..4edbcb1 --- /dev/null +++ b/regalloc.c @@ -0,0 +1,88 @@ +#include "ir.h" + +extern struct instr instr[]; +extern vec_of(struct call) calls; +extern vec_of(struct phi) phis; + +static struct bitset taken[1]; + +static int +nextreg(enum irclass cls) +{ + int r0, rend, i; + + if (kisint(cls)) { + r0 = mctarg->gpr0; + rend = mctarg->gpr0 + mctarg->ngpr; + } else if (kisflt(cls)) { + r0 = mctarg->fpr0; + rend = mctarg->fpr0 + mctarg->nfpr; + } else assert(0); + for (i = r0; i < rend; ++i) { + if (!bstest(taken, i)) { + bsset(taken, i); + return i; + } + } + assert(!"no more reg"); +} + +static void +use(struct block *blk, enum op op, int hint, union ref *ref) +{ + struct instr *ins; + if (ref->t == REXT) { + if (op == Ocall) { + struct call *call = &calls.p[ref->idx]; + for (int i = 0; i < call->narg; ++i) + use(blk, 0, 0, &call->args[i]); + } else if (op == Ophi) { + struct phi *phi = &phis.p[ref->idx]; + for (int i = 0; i < phi->n; ++i) + use(blk, 0, hint, &phi->ref[i]); + } else assert("ext?"); + return; + } else if (ref->t != RTMP) return; + + ins = &instr[ref->idx]; + if (in_range(ins->op, Oalloca1, Oalloca16)) return; + if (!ins->reg) { + if (op == -1) /* cond branch */ + if (in_range(ins->op, Oequ, Oulte) && ref->idx == blk->ins.p[blk->ins.n-1]) + /* result of comparison instr is only used to conditionally branch, + * doesn't usually need a reg (handled by isel) */ + return; + ins->reg = hint ? hint : nextreg(ins->cls); + } +} + +void +regalloc(struct function *fn) +{ + struct block *blk = fn->entry->lprev; + struct instr *ins; + + /* a dumb linear register allocator that visits instructions backwards + * starting at the end of the function, when encountering a use of a new + * temporary, it allocates a register for it. when encountering the definition + * of a temporary, it frees up its register + */ + do { + if (blk->jmp.arg.t) use(blk, blk->jmp.t == Jbcnd ? -1 : 0, 0, &blk->jmp.arg); + for (int i = blk->phi.n - 1; i >= 0; --i) { + ins = &instr[blk->phi.p[i]]; + bsclr(taken, ins->reg); + assert(ins->op == Ophi); + use(blk, Ophi, ins->reg, &ins->l); + } + for (int i = blk->ins.n - 1; i >= 0; --i) { + ins = &instr[blk->ins.p[i]]; + bsclr(taken, ins->reg); + if (ins->l.t) use(blk, ins->op, 0, &ins->l); + if (ins->r.t) use(blk, ins->op, 0, &ins->r); + } + blk = blk->lprev; + } while (blk != fn->entry->lprev); +} + +/* vim:set ts=3 sw=3 expandtab: */ diff --git a/targ.c b/targ.c index e323148..da3d86a 100644 --- a/targ.c +++ b/targ.c @@ -1,21 +1,24 @@ #include "common.h" -uchar targ_primsizes[TYPTR+1]; -uchar targ_primalign[TYPTR+1]; -enum typetag targ_sizetype, targ_ptrdifftype; -bool targ_charsigned, targ_bigendian; - +extern const struct mctarg t_amd64_sysv; static const struct targ { const char *name; struct { uchar longsize, vlongsize, ptrsize, valistsize; }; struct { uchar longalign, vlongalign, doublealign, ptralign; }; bool charsigned; uchar sizetype, ptrdifftype; + const struct mctarg *mctarg; } targs[] = { - { "amd64-sysv", {8, 8, 8, 24}, {8, 8, 8, 8}, 1, TYULONG, TYLONG }, + { "amd64-sysv", {8, 8, 8, 24}, {8, 8, 8, 8}, 1, TYULONG, TYLONG, &t_amd64_sysv }, { "i686-sysv", {4, 8, 4, 8}, {4, 4, 4, 4}, 1, TYUINT, TYINT } }; +uchar targ_primsizes[TYPTR+1]; +uchar targ_primalign[TYPTR+1]; +enum typetag targ_sizetype, targ_ptrdifftype; +bool targ_charsigned, targ_bigendian; +const struct mctarg *mctarg; + void targ_init(const char *starg) { @@ -40,4 +43,5 @@ targ_init(const char *starg) targ_ptrdifftype = t->ptrdifftype; targ_charsigned = t->charsigned; targ_bigendian = 0; + mctarg = t->mctarg; } diff --git a/test.c b/test.c index 5adb14f..5bb4e72 100644 --- a/test.c +++ b/test.c @@ -15,6 +15,7 @@ struct foo { int x, y, z; }; + int test0(struct foo *foo) { return foo->x ? foo->y : foo->z; } int test1(int x, int y, int z) { return x && y || z; } int test2(int x, int y, int z) { return x || y && z; } @@ -44,4 +45,22 @@ int test6(int x) return !!!!x; } +float sqr(float x) { return x * x; } + +int mula(int x, int y, int z) { + if (x < 0) + return -x * y + z; + return x * y + z; +} + +void *copy(char *d, char *s, int n) { + while (n--) + *d++ = *s++; + return d; +} + +int hmm(float x, int a, char *p, char *q) { + return x > 1 ? a || p : p < q && a > 0; +} + // -- cgit v1.2.3