diff options
| -rw-r--r-- | amd64/isel.c | 8 | ||||
| -rw-r--r-- | c.c | 38 | ||||
| -rw-r--r-- | common.h | 23 | ||||
| -rw-r--r-- | ir.c | 120 | ||||
| -rw-r--r-- | ir.h | 25 | ||||
| -rw-r--r-- | irdump.c | 20 | ||||
| -rw-r--r-- | regalloc.c | 10 | ||||
| -rw-r--r-- | ssa.c | 6 |
8 files changed, 135 insertions, 115 deletions
diff --git a/amd64/isel.c b/amd64/isel.c index e5aa281..3f83312 100644 --- a/amd64/isel.c +++ b/amd64/isel.c @@ -413,10 +413,10 @@ amd64_isel(struct function *fn) do { int i; for (i = 0; i < blk->phi.n; ++i) { - struct phi *phi = &phitab.p[instrtab[blk->phi.p[i]].l.i]; - for (int i = 0; i < phi->n; ++i) { - int curi = phi->blk[i]->ins.n; - fixarg(&phi->ref[i], NULL, phi->blk[i], &curi); + union ref *phi = phitab.p[instrtab[blk->phi.p[i]].l.i]; + for (int i = 0; i < blk->npred; ++i) { + int curi = blkpred(blk, i)->ins.n; + fixarg(&phi[i], NULL, blkpred(blk, i), &curi); } } iflagsrc = -1; @@ -1255,7 +1255,6 @@ Loop: } struct condphis { - vec_of(struct block *) blk; vec_of(union ref) ref; }; @@ -1289,7 +1288,6 @@ condexprrec(struct function *fn, const struct expr *ex, struct condphis *phis, condexprrec(fn, &ex->sub[2], phis, -1, end, zero); } else { r = exprvalue(fn, ex); - vpush(&phis->blk, fn->curblk); if (boolcon == -2) r = cvt(fn, TYBOOL, ex->ty.t, r); if (boolcon >= 0) @@ -1305,6 +1303,23 @@ condexprrec(struct function *fn, const struct expr *ex, struct condphis *phis, } } +/* the naive way to generate something like a ? b : c ? d : e, uses multiple phis, + * this code reduces such nested conditional expressions into one phi */ +static union ref +condexprvalue(struct function *fn, const struct expr *ex) +{ + union ref refbuf[8]; + struct condphis phis = { VINIT(refbuf, arraylength(refbuf)) }; + struct block *dst = newblk(fn); + union ref r; + condexprrec(fn, ex, &phis, -1, dst, NULL); + useblk(fn, dst); + assert(fn->curblk->npred == phis.ref.n); + r = addphi(fn, type2cls[ex->ty.t], phis.ref.p); + vfree(&phis.ref); + return r; +} + static union ref compilecall(struct function *fn, const struct expr *ex) { @@ -1335,25 +1350,6 @@ compilecall(struct function *fn, const struct expr *ex) return addinstr(fn, ins); } -/* the naive way to generate something like a ? b : c ? d : e, uses multiple phis, - * this code reduces such nested conditional expressions into one phi */ -static union ref -condexprvalue(struct function *fn, const struct expr *ex) -{ - struct block *blkbuf[8]; - union ref refbuf[8]; - struct condphis phis = { VINIT(blkbuf, arraylength(blkbuf)), - VINIT(refbuf, arraylength(refbuf))}; - struct block *dst = newblk(fn); - union ref r; - 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); - vfree(&phis.ref); - return r; -} - static union ref compileexpr(struct function *fn, const struct expr *ex, bool discard) { @@ -329,10 +329,32 @@ struct arena { #define vec_of(T) struct { T *p; int _cap; uint n; } +/* libc *alloc wrappers */ extern void *xcalloc(size_t n, const char *); extern void *xrealloc(void *, size_t n, const char *); #define xcalloc(n) xcalloc(n, __func__) #define xrealloc(p,n) xrealloc(p, n, __func__) + +/* growable buffer that stores its capacity in the allocated memory */ +#define xbnew_(n) (void *)(1 + (size_t *)xcalloc(sizeof(size_t) + (n))) +#define xbcap_(p) ((size_t *)(p))[-1] +static inline void +xbgrow_(void **p, size_t n) +{ + if (!n) return; + if (!*p) { *p = xbnew_(n); xbcap_(*p) = n; assert(n>0); } + else if (xbcap_(*p) < n) { + size_t k = xbcap_(*p); + assert(k > 0); + do k *= 2; while (k < n); + *p = 1 + (size_t *)xrealloc(&xbcap_(*(p)), sizeof(size_t) + k); + xbcap_(*p) = k; + }; +} +#define xbgrow(p, n) xbgrow_((void **)(p), (n) * sizeof**(p)) +#define xbpush(p, n, x) (xbgrow(p, (*(n) + 1)), (*(p))[(*(n))++] = (x)) +#define xbfree(p) ((p) ? free(&xbcap_(p)) : (void)0) + struct arena *newarena(uint chunksiz); void *alloc(struct arena **, uint siz, uint align); static inline void * @@ -341,6 +363,7 @@ alloccopy(struct arena **arena, const void *src, uint siz, uint align) return memcpy(alloc(arena, siz, align), src, siz); } void freearena(struct arena *); + void vinit_(void **p, int *pcap, void *inlbuf, int cap, uint siz); void vpush_(void **p, int *pcap, uint *pn, uint siz); void *vpushn_(void **p, int *pcap, uint *pn, uint siz, const void *dat, uint ndat); @@ -27,12 +27,13 @@ void irinit(struct function *fn) { static struct call callsbuf[64]; - static struct phi phisbuf[64]; + static union ref *phisbuf[64]; static struct irdat datsbuf[64]; ninstr = 0; instrfreelist = -1; vinit(&calltab, callsbuf, arraylength(callsbuf)); + for (int i = 0; i < phitab.n; ++i) xbfree(phitab.p[i]); vinit(&phitab, phisbuf, arraylength(phisbuf)); vinit(&dattab, datsbuf, arraylength(datsbuf)); if (naddrht >= arraylength(addrht)/2) @@ -218,6 +219,23 @@ mkaddr(struct addr addr) return mkref(RMORE, addaddr(&addr)); } +static inline void +addpred(struct block *blk, struct block *p) +{ + if (blk->npred == 0) { + blk->_pred0 = p; + ++blk->npred; + return; + } + if (blk->npred == 1) { + struct block *p0 = blk->_pred0; + blk->_pred = 0; + xbgrow(&blk->_pred, 4); + *blk->_pred = p0; + } + xbpush(&blk->_pred, &blk->npred, p); +} + static inline int newinstr(void) { @@ -230,15 +248,6 @@ newinstr(void) return ninstr++; } -union ref -addinstr(struct function *fn, struct instr ins) -{ - int new = newinstr(); - assert(fn->curblk != NULL); - instrtab[new] = ins; - vpush(&fn->curblk->ins, new); - return mkref(RTMP, new); -} union ref insertinstr(struct block *blk, int idx, struct instr ins) @@ -268,51 +277,7 @@ delinstr(struct block *blk, int idx) --blk->ins.n; } -union ref -addphi2(struct function *fn, enum irclass cls, - struct block *b1, union ref r1, struct block *b2, union ref r2) -{ - int new; - struct phi phi = { .n = 2, .cap = -1 }; - struct instr ins = { Ophi, cls }; - - phi.blk = alloc(&fn->arena, 2*sizeof(struct block *) + 2*sizeof r1, 0); - phi.ref = (union ref *)((char *)phi.blk + 2*sizeof(struct block *)); - phi.blk[0] = b1; - phi.ref[0] = r1; - phi.blk[1] = b2; - phi.ref[1] = r2; - vpush(&phitab, phi); - ins.l = mkref(RMORE, phitab.n-1); - assert(fn->curblk != NULL); - assert(fn->curblk->ins.n == 0); - new = newinstr(); - instrtab[new] = ins; - vpush(&fn->curblk->phi, new); - return mkref(RTMP, new); -} - -union ref -addphi(struct function *fn, enum irclass cls, struct block **blk, union ref *ref, uint n) -{ - int new; - struct phi phi = { .n = n, .cap = -1 }; - struct instr ins = { Ophi, cls }; - - assert(n > 0); - phi.blk = alloc(&fn->arena, n*sizeof(struct block *) + n*sizeof(union ref), 0); - phi.ref = (union ref *)((char *)phi.blk + n*sizeof(struct block *)); - memcpy(phi.blk, blk, n * sizeof(struct block *)); - memcpy(phi.ref, ref, n * sizeof(union ref)); - vpush(&phitab, phi); - ins.l = mkref(RMORE, phitab.n-1); - assert(fn->curblk != NULL); - assert(fn->curblk->ins.n == 0); - new = newinstr(); - instrtab[new] = ins; - vpush(&fn->curblk->phi, new); - return mkref(RTMP, new); -} +/** IR builders **/ struct block * newblk(struct function *fn) @@ -339,6 +304,36 @@ useblk(struct function *fn, struct block *blk) fn->curblk = blk; } +union ref +addinstr(struct function *fn, struct instr ins) +{ + int new = newinstr(); + assert(fn->curblk != NULL); + instrtab[new] = ins; + vpush(&fn->curblk->ins, new); + return mkref(RTMP, new); +} + +union ref +addphi(struct function *fn, enum irclass cls, union ref *r) +{ + int new; + struct instr ins = { Ophi, cls }; + union ref **prefs; + + vpush(&phitab, NULL); + prefs = &phitab.p[phitab.n - 1]; + xbgrow(prefs, fn->curblk->npred); + memcpy(*prefs, r, fn->curblk->npred * sizeof *r); + ins.l = mkref(RMORE, phitab.n-1); + assert(fn->curblk != NULL); + assert(fn->curblk->ins.n == 0); + new = newinstr(); + instrtab[new] = ins; + vpush(&fn->curblk->phi, new); + return mkref(RTMP, new); +} + #define putjump(fn, j, arg0, arg1, T, F) \ fn->curblk->jmp.t = j; \ fn->curblk->jmp.arg[0] = arg0; \ @@ -350,14 +345,17 @@ useblk(struct function *fn, struct block *blk) void putbranch(struct function *fn, struct block *blk) { - assert(blk); + assert(fn->curblk && blk); + addpred(blk, fn->curblk); putjump(fn, Jb, NOREF, NOREF, blk, NULL); } void putcondbranch(struct function *fn, union ref arg, struct block *t, struct block *f) { - assert(t && f); + assert(fn->curblk && t && f); + addpred(t, fn->curblk); + addpred(f, fn->curblk); putjump(fn, Jb, arg, NOREF, t, f); } @@ -369,13 +367,15 @@ putreturn(struct function *fn, union ref r0, union ref r1) #undef putjump +/** Misc **/ + void blkreplref(struct block *blk, int i0, union ref from, union ref to) { if (i0 == 0) for (int i = 0; i < blk->phi.n; ++i) { - struct phi *phi = &phitab.p[instrtab[blk->phi.p[i]].l.i]; - for (int i = 0; i < phi->n; ++i) - if (phi->ref[i].bits == to.bits) phi->ref[i] = from; + union ref *phi = phitab.p[instrtab[blk->phi.p[i]].l.i]; + for (int i = 0; i < blk->npred; ++i) + if (phi[i].bits == to.bits) phi[i] = from; } for (int i = i0; i < blk->ins.n; ++i) { @@ -58,12 +58,6 @@ struct call { struct abiarg abiret[2]; }; -struct phi { - struct block **blk; - union ref *ref; - int n, cap; -}; - enum refkind { RNONE, RTMP, /* reference to another instruction's result */ @@ -125,11 +119,16 @@ enum jumpkind { struct block { int id; + int npred; + union { + struct block *_pred0; + struct block **_pred; + }; + struct block *lprev, *lnext; struct block *s1, *s2; vec_of(ushort) phi; vec_of(ushort) ins; struct { uchar t; union ref arg[2]; } jmp; - struct block *lprev, *lnext; }; enum { MAXREGS = 64 }; @@ -194,7 +193,7 @@ extern const uchar siz2intcls[]; extern struct instr instrtab[]; extern struct xcon conht[]; extern struct calltab {vec_of(struct call);} calltab; -extern struct phitab {vec_of(struct phi);} phitab; +extern struct phitab {vec_of(union ref *);} phitab; extern struct dattab {vec_of(struct irdat);} dattab; extern struct addr addrht[]; #define insrescls(ins) (oiscmp((ins).op) ? KI4 : (ins).cls) @@ -226,17 +225,19 @@ void conputdat(struct irdat *, uint off, enum typetag t, const void *dat); union ref mkcallarg(union irtype ret, uint narg, int vararg); #define mkintrin(B, C, N) mkinstr(Ointrin, C, {.t=RICON,B}, mkcallarg((union irtype){{0}},N,-1)) union ref mkaddr(struct addr); -union ref addinstr(struct function *, struct instr); union ref insertinstr(struct block *, int idx, struct instr); void delinstr(struct block *, int idx); -union ref addphi2(struct function *, enum irclass cls, - struct block *b1, union ref r1, struct block *b2, union ref r2); -union ref addphi(struct function *, enum irclass cls, struct block **blk, union ref *ref, uint n); +#define blkpred(blk, i) 0[(blk)->npred < 2 ? &(blk)->_pred0 : &(blk)->_pred[i]] + +/* IR builder functions */ +union ref addinstr(struct function *, struct instr); +union ref addphi(struct function *, enum irclass, union ref []); struct block *newblk(struct function *); void useblk(struct function *, struct block *); void putbranch(struct function *, struct block *); void putcondbranch(struct function *, union ref arg, struct block *t, struct block *f); void putreturn(struct function *, union ref r0, union ref r1); + void blkreplref(struct block *, int, union ref from, union ref to); void replref(struct function *, struct block *, int, union ref from, union ref to); @@ -104,15 +104,7 @@ dumpref(enum op o, union ref ref) prityp(ref2type(ref)); break; case RMORE: - if (o == Ophi) { - struct phi *phi = &phitab.p[ref.i]; - assert(phitab.n > ref.i); - for (int i = 0; i < phi->n; ++i) { - if (i) efmt(", "); - efmt("@%d ", phi->blk[i]->id); - dumpref(0, phi->ref[i]); - } - } else { + { const struct addr *addr = &addrht[ref.i]; bool k = 0; efmt("addr ["); @@ -197,7 +189,15 @@ dumpblk(struct function *fn, struct block *blk) int i; efmt(" @%d:\n", blk->id); for (i = 0; i < blk->phi.n; ++i) { - dumpinst(&instrtab[blk->phi.p[i]]); + struct instr *phi = &instrtab[blk->phi.p[i]]; + union ref *refs = phitab.p[phi->l.i]; + efmt(" %s %%%d = phi ", clsname[phi->cls], blk->phi.p[i]); + for (int i = 0; i < blk->npred; ++i) { + if (i) efmt(", "); + efmt("@%d ", blkpred(blk, i)->id); + dumpref(0, refs[i]); + } + efmt("\n"); } for (i = 0; i < blk->ins.n; ++i) { dumpinst(&instrtab[blk->ins.p[i]]); @@ -368,16 +368,16 @@ regalloc(struct function *fn) } } for (int i = blk->phi.n - 1; i >= 0; --i) { - struct phi *phi; + union ref *phi; ins = &instrtab[blk->phi.p[i]]; assert(ins->op == Ophi); - phi = &phitab.p[ins->l.i]; + phi = phitab.p[ins->l.i]; if (ins->reg) { /* introduce necessary moves in each pred, * XXX this doesn't work for backwards branches */ - for (int i = 0; i < phi->n; ++i) { - struct instr mov = mkinstr(Omove, insrescls(*ins), mkref(RREG, ins->reg-1), phi->ref[i]); - insertinstr(phi->blk[i], phi->blk[i]->ins.n, mov); + for (int i = 0; i < blk->npred; ++i) { + struct instr mov = mkinstr(Omove, insrescls(*ins), mkref(RREG, ins->reg-1), phi[i]); + insertinstr(blkpred(blk, i), blkpred(blk, i)->ins.n, mov); } } def(&ra, ins, NULL, 0); @@ -30,9 +30,9 @@ ssauses(struct function *fn) do { for (int i = 0; i < blk->phi.n; ++i) { int ins = blk->phi.p[i]; - struct phi *phi = &phitab.p[instrtab[ins].l.i]; - for (int i = 0; i < phi->n; ++i) { - USE(phi->ref[i], 0, ins); + union ref *phi = phitab.p[instrtab[ins].l.i]; + for (int i = 0; i < blk->npred; ++i) { + USE(phi[i], 0, ins); } } for (int i = 0; i < blk->ins.n; ++i) { |