aboutsummaryrefslogtreecommitdiffhomepage
path: root/ir
diff options
context:
space:
mode:
Diffstat (limited to 'ir')
-rw-r--r--ir/abi0.c462
-rw-r--r--ir/builder.c307
-rw-r--r--ir/cfg.c130
-rw-r--r--ir/cse.c92
-rw-r--r--ir/dump.c319
-rw-r--r--ir/fold.c133
-rw-r--r--ir/inliner.c309
-rw-r--r--ir/intrin.c77
-rw-r--r--ir/intrin.def2
-rw-r--r--ir/ir.c689
-rw-r--r--ir/ir.h353
-rw-r--r--ir/mem2reg.c317
-rw-r--r--ir/op.def79
-rw-r--r--ir/regalloc.c1417
-rw-r--r--ir/simpl.c308
-rw-r--r--ir/ssa.c46
-rw-r--r--ir/stack.c33
17 files changed, 0 insertions, 5073 deletions
diff --git a/ir/abi0.c b/ir/abi0.c
deleted file mode 100644
index a3687d9..0000000
--- a/ir/abi0.c
+++ /dev/null
@@ -1,462 +0,0 @@
-#include "ir.h"
-
-/** This pass adds in ABI arguments/returns register mappings
- ** and lowers aggregate params/args/returns into scalars
- **
- ** invariant: all `call` instructions when doing this pass shall be preceded by
- ** exactly narg `arg` instructions with no other instructions in between
- **/
-
-struct abiargsvec { vec_of(struct abiarg); };
-
-static int
-abiret(struct abiarg abiret[2], struct abiargsvec *abiargs, uchar *r2off, int *ni, union irtype retty)
-{
- short r[2];
- uchar cls[2];
- int retreg = 0;
- retreg = mctarg->abiret(r, cls, r2off, ni, retty);
- if (retty.isagg) {
- if (!retreg) {
- vpush(abiargs, ((struct abiarg) { cls2type(KPTR), .reg = r[1] }));
- if (r[0] == -1) {
- memset(abiret, 0, 2*sizeof *abiret);
- } else {
- abiret[0].ty = cls2type(KPTR);
- abiret[0].reg = r[0];
- }
- }
- } else if (retty.cls) {
- assert(retreg == 1);
- }
- for (int i = 0; i < retreg; ++i) {
- abiret[i].ty = cls2type(cls[i]);
- abiret[i].isstk = 0;
- abiret[i].reg = r[i];
- }
- return retreg;
-}
-
-static int
-abiarg(struct abiargsvec *abiargs, uchar *r2off, int *ni, int *nf, int *ns, union irtype ty)
-{
- short r[2];
- uchar cls[2];
- int ret = mctarg->abiarg(r, cls, r2off, ni, nf, ns, ty);
- if (!ret) { /* in stack */
- vpush(abiargs, ((struct abiarg) { ty, .isstk = 1, .stk = r[0] }));
- } else if (ret == 1 && ty.isagg && cls[0] == KPTR) { /* aggregate by pointer */
- vpush(abiargs, ((struct abiarg) { cls2type(cls[0]), .reg = r[0] }));
- } else { /* by regs */
- vpush(abiargs, ((struct abiarg) { cls2type(cls[0]), .reg = r[0] }));
- if (ret == 2)
- vpush(abiargs, ((struct abiarg) { cls2type(cls[1]), .reg = r[1] }));
- }
- return ret;
-}
-
-static struct instr
-copyparam(struct function *fn, int *curi, int param, struct abiarg abi)
-{
- struct instr par = mkinstr(Oparam, abi.ty.cls, mkref(RICON, param), mktyperef(abi.ty));
- if (!abi.isstk) { /* reg */
- assert(!abi.ty.isagg);
- return par;
- }
- par.r = mktyperef((union irtype){.cls = KPTR});
- if (!abi.ty.isagg) { /* scalar in stack */
- enum op ld;
- par.cls = KPTR;
- if (abi.ty.cls == KPTR) abi.ty.cls = siz2intcls[cls2siz[abi.ty.cls]];
- switch (abi.ty.cls) {
- default: assert(0);
- case KI32: ld = Oloads32; break;
- case KI64: ld = Oloadi64; break;
- case KF32: ld = Oloadf32; break;
- case KF64: ld = Oloadf64; break;
- }
- return mkinstr(ld, abi.ty.cls, insertinstr(fn->entry, (*curi)++, par));
- } else { /* aggregate in stack */
- par.cls = KPTR;
- return par;
- }
-}
-
-static void
-patchparam(struct function *fn, int *curi, int *param, int tydat, int nabi, struct abiarg abi[2], uchar r2off)
-{
- struct block *blk = fn->entry;
- assert(in_range(nabi,1,2));
-
- for (; *curi < blk->ins.n; ++*curi) {
- struct instr *ins = &instrtab[blk->ins.p[*curi]];
- if (ins->op != Oparam) continue;
- assert(ins->r.t == RTYPE
- && ins->r.i == (tydat < 0 ? abi[0].ty : (union irtype){.isagg=1, .dat=tydat}).bits);
- if (abi[0].ty.isagg || tydat < 0) {
- /* aggregate in stack or scalar, just copy */
- assert(nabi == 1);
- *ins = copyparam(fn, curi, *param, abi[0]);
- } else { /* aggregate in registers, materialize */
- union ref alloc, r[2];
- struct instr st;
- const struct typedata *td;
- uint nalloc;
- uint align;
-
- assert(tydat >= 0);
- td = &typedata[tydat];
- assert(td->siz <= 16 && td->align <= 16);
- align = td->siz <= 4 ? 4 : alignup(td->align, 8);
- nalloc = td->siz/align + (td->siz%align != 0);
- *ins = mkinstr(Oalloca1 + ilog2(align), KPTR, mkref(RICON, nalloc));
- alloc = mkref(RTMP, ins - instrtab);
- r[0] = insertinstr(blk, ++*curi, copyparam(fn, NULL, *param, abi[0]));
- if (nabi > 1)
- r[1] = insertinstr(blk, ++*curi, copyparam(fn, NULL, ++*param, abi[1]));
- /* transform
- * %x = copy %p
- * into
- * %x = alloca...
- * store* %x, %a
- * store* %x + N, %b
- */
- st = mkinstr(cls2store[abi[0].ty.cls], 0, alloc, r[0]);
- insertinstr(blk, ++*curi, st);
- if (nabi > 1) {
- struct instr tmp = mkinstr(Oadd, KPTR, alloc, mkref(RICON, r2off));
- st = mkinstr(cls2store[abi[1].ty.cls], 0, insertinstr(blk, ++*curi, tmp), r[1]);
- insertinstr(blk, ++*curi, st);
- }
- }
- ++*param;
- ++*curi;
- break;
- }
-}
-
-static void
-load2regs(union ref out[2], union irtype typ, union ref src, int nabi, struct abiarg abi[2], uchar r2off, struct block *blk, int *curi)
-{
- uint align = typedata[typ.dat].align;
- uint siz = typedata[typ.dat].siz;
- if (src.t == RTMP && oisalloca(instrtab[src.i].op)) {
- /* use actual alignment as opposed to min required type alignment */
- uint aalign = 1 << (instrtab[src.i].op - Oalloca1);
- assert(aalign >= align);
- align = aalign;
- }
- /* deconstruct into
- * %a = load* %x
- * (%b = load* %x + N)
- */
- /* XXX this generates pretty bad code for small-alignment structs even on platforms where unaligned loads are available.. */
- if (align >= 4) {
- for (int i = 0; i < nabi; ++i) {
- struct instr ins = {0};
- union ref temp;
- switch (ins.cls = abi[i].ty.cls) {
- default: assert(0);
- case KI32: ins.op = Oloadu32; break;
- case KI64: ins.op = Oloadi64; break;
- case KF32: ins.op = Oloadf32; break;
- case KF64: ins.op = Oloadf64; break;
- }
- if (i == 0)
- ins.l = src;
- else {
- struct instr adr = mkinstr(Oadd, KPTR, src, mkref(RICON, r2off));
- ins.l = insertinstr(blk, (*curi)++, adr);
- }
- temp = insertinstr(blk, (*curi)++, ins);
- //insertinstr(blk, (*curi)++, mkarginstr(abi[i].ty, temp));
- out[i] = temp;
- }
- } else {
- for (int i = 0; i < nabi; ++i) {
- struct instr ld = {0};
- union ref reg, temp;
- uint n = cls2siz[abi[i].ty.cls] / align;
- assert(n > 0);
- ld.op = Oloadu8 + ilog2(align)*2;
- ld.cls = abi[i].ty.cls;
- for (int o = 0; o < n && (i*cls2siz[ld.cls])+o*align < siz; ++o) {
- if (i+o == 0)
- ld.l = src;
- else {
- struct instr adr = mkinstr(Oadd, KPTR, src, mkref(RICON, (i == 0 ? 0 : r2off) + o*align));
- ld.l = insertinstr(blk, (*curi)++, adr);
- }
- temp = insertinstr(blk, (*curi)++, ld);
- if (o > 0) {
- union ref t = insertinstr(blk, (*curi)++, mkinstr(Oshl, ld.cls, temp, mkref(RICON, o*align*8)));
- reg = insertinstr(blk, (*curi)++, mkinstr(Oior, ld.cls, reg, t));
- } else {
- reg = temp;
- }
- }
- //insertinstr(blk, arginst++, mkarginstr(abi[i].ty, reg));
- out[i] = reg;
- }
- }
-}
-
-static int
-patcharg(struct block *blk, int *icall, struct call *call,
- int argidx, int nabi, struct abiarg abi[2], uchar r2off)
-{
- int arginst = *icall - (call->narg - argidx);
- struct instr *arg = &instrtab[blk->ins.p[arginst]];
- assert(arg->op == Oarg && arg->l.t == RTYPE);
- if (ref2type(arg->l).isagg) { /* aggregate argument */
- if (abi[0].ty.isagg) { /* aggregate in stack */
- /* XXX do this better.. */
- /* ptr %dst = arg <stk dst> */
- /* (blit %dst, %src) */
- union ref dst = mkref(RTMP, arg - instrtab);
- uint align = typedata[abi->ty.dat].align, siz = typedata[abi->ty.dat].siz;
- union ref src = arg->r;
- if (src.t == RTMP && oisalloca(instrtab[src.i].op)) {
- align = 1 << (instrtab[src.i].op - Oalloca1);
- }
- assert(align <= 8);
- arg->cls = KPTR;
- arg->r = mkref(RICON, abi->stk);
- for (uint off = 0; off < siz; off += align) {
- union ref sadr = off == 0 ? src : insertinstr(blk, ++arginst, mkinstr(Oadd, KPTR, src, mkref(RICON, off)));
- union ref tmp = insertinstr(blk, ++arginst, mkinstr(Oloads8+2*ilog2(align), align < 8 ? KI32 : KI64, sadr));
- union ref dadr = off == 0 ? dst : insertinstr(blk, ++arginst, mkinstr(Oadd, KPTR, dst, mkref(RICON, off)));
- insertinstr(blk, ++arginst, mkinstr(Ostorei8+ilog2(align), 0, dadr, tmp));
- }
- *icall = arginst + (call->narg - argidx);
- return 1;
- } else if (abi[0].ty.cls == KPTR) { /* aggregate by pointer */
- arg->cls = KPTR;
- return 1;
- } else { /* aggregate in registers */
- union ref r[2];
- delinstr(blk, arginst);
- load2regs(r, ref2type(arg->l), arg->r, nabi, abi, r2off, blk, &arginst);
- for (int i = 0; i < nabi; ++i)
- insertinstr(blk, arginst++, mkinstr(Oarg, 0, mktyperef(abi[i].ty), r[i]));
- *icall = arginst + (call->narg - argidx - 1);
- return nabi;
- }
- } else { /* normal scalar argument */
- return 1;
- }
-}
-void
-abi0_call(struct function *fn, struct instr *ins, struct block *blk, int *curi)
-{
- union ref retmem;
- struct abiarg abiargsbuf[32];
- struct abiargsvec abiargs = {VINIT(abiargsbuf, countof(abiargsbuf))};
- bool sretarghidden = 0;
- int ni, nf, ns, vararg, nret = 0;
- struct call *call = &calltab.p[ins->r.i];
-
- vararg = call->vararg;
- ni = nf = ns = 0;
- assert(!ins->cls == !call->ret.bits);
- nret = abiret(call->abiret, &abiargs, &call->r2off, &ni, call->ret);
- if (call->ret.isagg) { /* adjust struct return */
- union irtype retty = call->ret;
- struct typedata *td = &typedata[retty.dat];
- uint align = td->align, ralign;
- struct instr alloca;
- int ialloca;
- for (int i = 0; i < nret; ++i)
- align = align < (ralign = cls2siz[call->abiret[i].ty.cls]) ? ralign : align;
- alloca = mkalloca(td->siz, align);
-
- sretarghidden = ni == 0;
- /* swap alloca and call temps so users of original call point to alloca */
- retmem = insertinstr(blk, ialloca = (*curi)++ - call->narg, *ins);
- *ins = alloca;
- blk->ins.p[ialloca] = ins - instrtab;
- blk->ins.p[*curi] = retmem.i;
- ins = &instrtab[retmem.i];
- retmem.i = blk->ins.p[ialloca];
-
- if (!nret) /* hidden pointer argument */
- insertinstr(blk, (*curi)++ - call->narg,
- mkinstr(Oarg, 0, mktyperef((union irtype){.cls=KPTR}), retmem));
- }
-
- /* adjust args */
- for (int i = 0, i2 = ni + sretarghidden; i < call->narg; ++i) {
- int arginst = *curi - (call->narg - i);
- struct instr *arg = &instrtab[blk->ins.p[arginst]];
- union irtype pty = ref2type(arg->l);
- uchar r2off;
- int first = abiargs.n;
- int ret = abiarg(&abiargs, &r2off, &ni, &nf, &ns, pty);
- ret = patcharg(blk, curi, call, i, ret, &abiargs.p[first], r2off);
- if (call->vararg == i) vararg = i2;
- i2 += ret;
- }
- call->argstksiz = ns;
- /* adjust return */
- if (call->ret.isagg) {
- ins->cls = 0;
- if (!nret) { /* hidden pointer argument */
- ins->cls = 0;
- if (!call->abiret[0].isstk) {
- /* the result location pointer is also returned by the callee, e.g. in x86 */
- ins->cls = KPTR;
- ++nret;
- /* even if this is not used, the register copy
- * must be emitted for the register allocator to know */
- }
- } else { /* aggregate returned in regs */
- union ref r[2];
- struct instr ret2;
- assert(in_range(nret, 1, 2));
- ins->cls = call->abiret[0].ty.cls;
- r[0] = mkref(RTMP, ins - instrtab);
- if (nret == 2) {
- ret2 = mkinstr(Ocall2r, call->abiret[1].ty.cls, r[0]);
- r[1] = insertinstr(blk, ++*curi, ret2);
- }
- for (int i = 0; i < nret; ++i) {
- struct instr store = { cls2store[call->abiret[i].ty.cls] };
- if (i == 0) {
- store.l = retmem;
- } else {
- struct instr addr = mkinstr(Oadd, KPTR, retmem, mkref(RICON, call->r2off));
- store.l = insertinstr(blk, ++*curi, addr);
- }
- store.r = r[i];
- insertinstr(blk, ++*curi, store);
- }
- }
- }
-
- if (call->ret.isagg) call->ret = (union irtype){0};
- call->vararg = vararg;
- call->abiarg = alloccopy(fn->arena, abiargs.p, abiargs.n * sizeof(struct abiarg), 0);
- call->narg = abiargs.n;
- vfree(&abiargs);
-}
-
-void
-abi0(struct function *fn)
-{
- struct abiarg abiargsbuf[32];
- uint nparam = typedata[fn->fnty.dat].nmemb;
- const union type *paramty = typedata[fn->fnty.dat].param;
- struct abiargsvec abiargs = {VINIT(abiargsbuf, countof(abiargsbuf))};
- int rvovar = -1;
- int ni = 0, nf = 0, ns = 0, istart = 0;
- uchar r2off;
- struct block *blk;
- union ref sret = {0};
-
- FREQUIRE(FNUSE);
-
- if (fn->retty.t == TYVOID) {
- fn->nabiret = 0;
- } else {
- fn->nabiret = abiret(fn->abiret, &abiargs, &r2off, &ni, mkirtype(fn->retty));
- if (!fn->nabiret && isagg(fn->retty)) { /* ret agg by hidden pointer */
- struct instr param = copyparam(fn, NULL, 0, abiargs.p[0]);
- sret = insertinstr(fn->entry, 0, param);
- ++istart;
- /* increment real param ordinals */
- for (int i = 1; i < fn->entry->ins.n; ++i) {
- struct instr *ins = &instrtab[fn->entry->ins.p[i]];
- if (ins->op == Oparam) ++ins->l.i;
- }
- }
- }
-
- /* adjust params */
- for (int i = 0, param = abiargs.n; i < nparam; ++i) {
- union irtype pty = mkirtype(paramty[i]);
- int first = abiargs.n;
- uchar r2off;
- int ret = abiarg(&abiargs, &r2off, &ni, &nf, &ns, pty);
- patchparam(fn, &istart, &param, pty.isagg ? pty.dat : -1, ret+!ret, &abiargs.p[first], r2off);
- }
- fn->abiarg = alloccopy(fn->arena, abiargs.p, abiargs.n * sizeof *abiargs.p, 0);
- fn->nabiarg = abiargs.n;
- vfree(&abiargs);
-
- if (!fn->nabiret && isagg(fn->retty)) {
- /* for structures returned by hidden pointer argument,
- * if all return instrs return local var X, make X point to the result location,
- * (return value optimization (RVO)) */
- blk = fn->entry;
- do {
- union ref arg = blk->jmp.arg[0];
- if (blk->jmp.t != Jret) continue;
- if (!arg.bits) continue;
- if (arg.t != RTMP || !oisalloca(instrtab[arg.i].op)) {
- rvovar = -1;
- break;
- }
- if (rvovar == -1) {
- rvovar = arg.i;
- } else if (arg.i != rvovar) {
- rvovar = -1;
- break;
- }
- } while ((blk = blk->lnext) != fn->entry);
- if (rvovar != -1)
- instrtab[rvovar] = mkinstr(Ocopy, KPTR, sret);
- }
-
- blk = fn->entry->lnext;
- int id = 1;
- do {
- /* adjust vaargs and calls */
- for (int iinstr = 0; iinstr < blk->ins.n; ++iinstr) {
- struct instr *ins = &instrtab[blk->ins.p[iinstr]];
- if (ins->op == Ovastart) mctarg->vastart(fn, blk, &iinstr);
- else if (ins->op == Ovaarg) mctarg->vaarg(fn, blk, &iinstr);
- else if (ins->op == Ocall) abi0_call(fn, ins, blk, &iinstr);
- }
-
- /* adjust returns */
- if (isagg(fn->retty) && blk->jmp.t == Jret && blk->jmp.arg[0].bits) {
- assert(!blk->jmp.arg[1].bits);
- if (fn->nabiret) { /* aggregate return in register(s) */
- union ref r[2];
- int curi = blk->ins.n;
- load2regs(r, mkirtype(fn->retty), blk->jmp.arg[0], fn->nabiret, fn->abiret, r2off, blk, &curi);
- for (int i = 0; i < fn->nabiret; ++i) {
- blk->jmp.arg[i] = r[i];
- adduse(blk, USERJUMP, r[i]);
- }
- } else {
- /* aggregate return (arg[0] is pointer to return value) */
- if (rvovar == -1) {
- /* blit %sret, %arg */
- union irtype typ = mkirtype(fn->retty);
- insertinstr(blk, blk->ins.n, mkarginstr(typ, sret));
- insertinstr(blk, blk->ins.n, mkarginstr(typ, blk->jmp.arg[0]));
- insertinstr(blk, blk->ins.n, mkintrin(INstructcopy, 0, 2));
- } else assert(blk->jmp.arg[0].bits == mkref(RTMP, rvovar).bits);
- if (fn->abiret[0].ty.cls) {
- blk->jmp.arg[0] = rvovar == -1 ? sret : mkref(RTMP, rvovar);
- adduse(blk, USERJUMP, blk->jmp.arg[0]);
- }
- else memset(blk->jmp.arg, 0, sizeof blk->jmp.arg);
- }
- }
- blk->id = id++;
- } while ((blk = blk->lnext) != fn->entry);
-
-
- /* vaargs might break these */
- if (!(fn->prop & FNUSE)) filluses(fn);
- fn->prop &= ~(FNBLKID | FNRPO);
-
- if (ccopt.dbg.a) {
- bfmt(ccopt.dbgout, "<< After abi0 >>\n");
- irdump(fn);
- }
-}
-
-/* vim:set ts=3 sw=3 expandtab: */
diff --git a/ir/builder.c b/ir/builder.c
deleted file mode 100644
index 206e66d..0000000
--- a/ir/builder.c
+++ /dev/null
@@ -1,307 +0,0 @@
-#include "ir.h"
-
-/* binary arithmetic builder with peephole optimizations */
-union ref
-irbinop(struct function *fn, enum op op, enum irclass k, union ref l, union ref r)
-{
- static const union ref ONE = {.t=RICON, .i=1};
- vlong iv;
- union ref c;
-
- if (foldbinop(&c, op, k, l, r))
- return c;
-
- switch (op) {
- case Oadd:
- if (l.bits == ZEROREF.bits) return r; /* 0 + x ==> x */
- if (r.bits == ZEROREF.bits) return l; /* x + 0 ==> x */
- break;
- case Osub:
- if (r.bits == ZEROREF.bits) return l; /* x - 0 ==> x */
- if (kisint(k) && l.bits == r.bits) return ZEROREF; /* x - x ==> 0 */
- break;
- case Omul:
- if (isnumcon(l)) rswap(l, r); /* put const in rhs */
- if (kisflt(k)) break;
- if (r.bits == ZEROREF.bits) /* x * 0 ==> 0 */
- return ZEROREF;
- if (r.bits == ONE.bits) /* x * 1 ==> x */
- return l;
- if (isintcon(r) && ispo2(iv = intconval(r))) {
- /* x * 2^y ==> x << y */
- op = Oshl;
- r = mkref(RICON, ilog2(iv));
- }
- break;
- case Odiv:
- break;
- case Oudiv:
- if (kisflt(k)) break;
- if (isintcon(r) && ispo2(iv = intconval(r))) {
- /* x / 2^y ==> x >> y */
- op = Oslr;
- r = mkref(RICON, ilog2(iv));
- }
- break;
- case Orem:
- break;
- case Ourem:
- if (kisflt(k)) break;
- if (isintcon(r) && ispo2(iv = intconval(r))) {
- /* x % 2^y ==> x & 2^y-1 */
- op = Oand;
- r = mkintcon(k, iv - 1);
- }
- break;
- case Oand:
- if (isnumcon(l)) rswap(l, r); /* put const in rhs */
- if (r.bits == ZEROREF.bits) /* x & 0 ==> 0 */
- return ZEROREF;
- break;
- case Oior:
- if (isnumcon(l)) rswap(l, r); /* put const in rhs */
- if (r.bits == ZEROREF.bits) /* x | 0 ==> x */
- return l;
- case Oxor:
- if (isnumcon(l)) rswap(l, r); /* put const in rhs */
- if (r.bits == ZEROREF.bits) /* x ^ 0 ==> x */
- return l;
- case Oshl: case Osar: case Oslr:
- if (r.bits == ZEROREF.bits) /* x shift 0 ==> x */
- return l;
- break;
- case Oequ:
- if (r.bits == l.bits && kisint(k))
- return ONE;
- break;
- case Oneq:
- if (r.bits == l.bits && kisint(k))
- return ZEROREF;
- break;
- case Olth: case Ogth:
- case Olte: case Ogte:
- break;
- case Oulth:
- if (r.bits == ZEROREF.bits) /* x u< 0 ==> f */
- return ZEROREF;
- break;
- case Ougth:
- if (l.bits == ZEROREF.bits) /* 0 u> x ==> f */
- return ZEROREF;
- break;
- case Oulte:
- if (l.bits == ZEROREF.bits) /* 0 u<= x ==> t */
- return ONE;
- break;
- case Ougte:
- if (r.bits == ZEROREF.bits) /* x u>= 0 ==> t */
- return ONE;
- break;
- default:
- assert(!"binop?");
- }
- return fn ? addinstr(fn, mkinstr(op, k, l, r)) : NOREF;
-}
-
-/* implements f32/f64 -> u64 conversion */
-static union ref
-cvtfu64(struct function *fn, enum irclass from, union ref x)
-{
- struct block *t, *f, *merge;
- union ref tmp, phiarg[2];
- /* if (x < 2p63) cvtfXs(x) else (cvtfXs(x - 2p63) | (1<<63)) */
- union ref max = mkfltcon(from, 0x1.0p63);
- enum op cvt = from == KF32 ? Ocvtf32s : Ocvtf64s;
- putcondbranch(fn, irbinop(fn, Olth, from, x, max), t = newblk(fn), f = newblk(fn));
-
- useblk(fn, t);
- phiarg[0] = irunop(fn, cvt, KI64, x);
- putbranch(fn, merge = newblk(fn));
-
- useblk(fn, f);
- tmp = irbinop(fn, Osub, from, x, max);
- tmp = irunop(fn, cvt, KI64, tmp);
- phiarg[1] = irbinop(fn, Oior, KI64, tmp, mkintcon(KI64, 1ull<<63));
- putbranch(fn, merge);
-
- useblk(fn, merge);
- return addphi(fn, KI64, phiarg);
-}
-
-/* implements u64 -> f32/f64 conversion */
-static union ref
-cvtu64f(struct function *fn, enum irclass to, union ref x)
-{
- struct block *t, *f, *merge;
- union ref t1, t2, phiarg[2];
-
- /* if ((s64)x >= 0) cvts64f(x) else cvts64f((x>>1)|(x&1))*2 */
-
- putcondbranch(fn, irbinop(fn, Ogte, KI64, x, ZEROREF), t = newblk(fn), f = newblk(fn));
-
- useblk(fn, t);
- phiarg[0] = irunop(fn, Ocvts64f, to, x);
- putbranch(fn, merge = newblk(fn));
-
- useblk(fn, f);
- t1 = irbinop(fn, Oslr, KI64, x, mkref(RICON, 1));
- t2 = irbinop(fn, Oand, KI64, x, mkref(RICON, 1));
- t1 = irbinop(fn, Oior, KI64, t1, t2);
- t1 = irunop(fn, Ocvts64f, to, t1);
- phiarg[1] = irbinop(fn, Oadd, to, t1, t1);
- putbranch(fn, merge);
-
- useblk(fn, merge);
- return addphi(fn, to, phiarg);
-}
-
-union ref
-irunop(struct function *fn, enum op op, enum irclass k, union ref a)
-{
- union ref c;
- struct instr *ins = NULL;
- if (foldunop(&c, op, k, a))
- return c;
- if (a.t == RTMP) ins = &instrtab[a.i];
- switch (op) {
- case Oneg:
- if (ins && ins->op == Oneg) /* -(-x) ==> x */
- return ins->l;
- break;
- case Onot:
- if (ins && ins->op == Onot) /* ~(~x) ==> x */
- return ins->l;
- break;
- case Ocvtf32s: case Ocvtf32f64: case Ocvtf64s:
- case Ocvtf64f32: case Ocvts32f: case Ocvtu32f:
- case Ocvts64f:
- break;
- case Ocvtf32u: case Ocvtf64u:
- if (target.arch == ISx86_64 && k == KI64 && fn) {
- /* this should probably be handled in a separate "arithmetic-lowering" pass, earlier than isel
- */
- return cvtfu64(fn, op == Ocvtf32u ? KF32 : KF64, a);
- }
- break;
- case Ocvtu64f:
- /* XXX see above */
- if (target.arch == ISx86_64 && fn)
- return cvtu64f(fn, k, a);
- case Oexts8: case Oextu8: case Oexts16: case Oextu16:
- case Oexts32: case Oextu32:
- case Ocopy:
- break;
- case Obswap16: case Obswap32: case Obswap64:
- break;
- default: assert(!"unop?");
- }
- return fn ? addinstr(fn, mkinstr(op, k, a)) : NOREF;
-}
-
-int allocinstr(void);
-
-union ref
-addinstr(struct function *fn, struct instr ins)
-{
- int new = allocinstr();
- assert(fn->curblk != NULL);
- instrtab[new] = ins;
- adduse(fn->curblk, new, ins.l);
- adduse(fn->curblk, new, ins.r);
- vpush(&fn->curblk->ins, new);
- return mkref(RTMP, new);
-}
-
-void
-useblk(struct function *fn, struct block *blk)
-{
- extern int nerror;
- if (fn->curblk && nerror == 0) assert(fn->curblk->jmp.t && "never finished block");
- if (blk) assert(!blk->jmp.t && "reusing built block");
- if (blk && !blk->lprev) { /* initialize */
- blk->lnext = fn->entry;
- blk->lprev = fn->entry->lprev;
- blk->lprev->lnext = blk;
- blk->id = fn->nblk++;
- fn->entry->lprev = blk;
- }
- fn->curblk = blk;
-}
-
-union ref
-addphi(struct function *fn, enum irclass cls, union ref *r)
-{
- assert(fn->curblk);
- if (fn->curblk->npred == 0) return UNDREF;
- if (fn->curblk->npred == 1) /* 1-argument phi is identity */
- return *r;
-
- union ref *refs = NULL;
- xbgrow(&refs, fn->curblk->npred);
- memcpy(refs, r, fn->curblk->npred * sizeof *r);
- vpush(&phitab, refs);
- /*assert(fn->curblk->ins.n == 0);*/
- int new = allocinstr();
- instrtab[new] = mkinstr(Ophi, cls, .l.i = phitab.n-1);
- for (int i = 0; i < fn->curblk->npred; ++i) {
- adduse(fn->curblk, new, r[i]);
- }
- 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; \
- fn->curblk->jmp.arg[1] = arg1; \
- fn->curblk->s1 = T; \
- fn->curblk->s2 = F; \
- fn->curblk = NULL;
-
-void
-putbranch(struct function *fn, struct block *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(fn->curblk && t && f);
- if (iscon(arg)) {
- bool truthy;
- if (isintcon(arg)) truthy = intconval(arg) != 0;
- else if (isfltcon(arg)) truthy = fltconval(arg) != 0.0;
- else if (isaddrcon(arg,0)) truthy = 1; /* XXX ok to assume symbols have non null addresses? */
- else goto Cond;
- putbranch(fn, truthy ? t : f);
- } else {
- Cond:
- adduse(fn->curblk, USERJUMP, arg);
- addpred(t, fn->curblk);
- addpred(f, fn->curblk);
- putjump(fn, Jb, arg, NOREF, t, f);
- }
-}
-
-void
-putreturn(struct function *fn, union ref r0, union ref r1)
-{
- assert(fn->curblk);
- adduse(fn->curblk, USERJUMP, r0);
- adduse(fn->curblk, USERJUMP, r1);
- putjump(fn, Jret, r0, r1, NULL, NULL);
-}
-
-void
-puttrap(struct function *fn)
-{
- assert(fn->curblk);
- putjump(fn, Jtrap, NOREF, NOREF, NULL, NULL);
-}
-
-#undef putjump
-
-/* vim:set ts=3 sw=3 expandtab: */
diff --git a/ir/cfg.c b/ir/cfg.c
deleted file mode 100644
index 86af3f3..0000000
--- a/ir/cfg.c
+++ /dev/null
@@ -1,130 +0,0 @@
-#include "ir.h"
-
-static void
-porec(int *nblk, struct block ***rpo, struct block *b)
-{
- if (wasvisited(b)) return;
- assert(*nblk > 0 && "nblk bad");
- --*nblk;
- markvisited(b);
- if (b->s2) porec(nblk, rpo, b->s2);
- if (b->s1) porec(nblk, rpo, b->s1);
- *--*rpo = b;
-}
-
-/* also blkid */
-void
-sortrpo(struct function *fn)
-{
- static struct block **rpobuf;
- struct block **rpoend, **rpo, *blk, *next;
- int i, ndead;
-
- xbgrow(&rpobuf, fn->nblk);
- rpo = rpoend = rpobuf + fn->nblk,
-
- startbbvisit();
- fn->entry->id = 0;
- int nblk = fn->nblk;
- porec(&nblk, &rpo, fn->entry);
- ndead = rpo - rpobuf;
- if (ndead > 0) for (blk = fn->entry->lprev; blk != fn->entry; blk = next) {
- next = blk->lprev;
- if (!wasvisited(blk)) {
- for (int i = 0; i < blk->ins.n; ++i) {
- /* if unreachable block has alloca pseudo-instrs, move them to the entry
- * to be able to delete it */
- if (oisalloca(instrtab[blk->ins.p[i]].op)) {
- vpush(&fn->entry->ins, blk->ins.p[i]);
- }
- }
- for (int i = 0; i < blk->npred; ++i)
- assert(!wasvisited(blkpred(blk, i)));
- freeblk(fn, blk);
- --ndead;
- }
- }
- for (i = 1, ++rpo; rpo < rpoend; ++rpo, ++i) {
- rpo[-1]->lnext = rpo[0];
- rpo[0]->lprev = rpo[-1];
- rpo[0]->id = i;
- }
- fn->entry->lprev = rpo[-1];
- rpo[-1]->lnext = fn->entry;
-
- fn->prop |= FNBLKID | FNRPO;
-}
-
-/* also blkid */
-void
-filldom(struct function *fn)
-{
- struct block *blk = fn->entry;
- int i = 0;
-
- FREQUIRE(FNRPO);
-
- /* Implements 'A Simple, Fast Dominance Algorithm' by K. Cooper, T. Harvey, and K. Kennedy */
- do blk->id = i++, blk->idom = NULL; while ((blk = blk->lnext) != fn->entry);
- fn->entry->idom = fn->entry;
- for (bool changed = 1; changed;) {
- changed = 0;
- do {
- int j;
- struct block *new = NULL;
- if (blk->npred == 0) continue;
- for (j = 0; j < blk->npred; ++j)
- if ((new = blkpred(blk, j))->id < blk->id) break;
- assert(new);
- for (int i = 0; i < blk->npred; ++i) {
- if (i == j) continue;
- struct block *p = blkpred(blk, i);
- if (p->idom) { /* new = intersect(p, new) */
- while (p != new) {
- while (p->id > new->id) p = p->idom;
- while (p->id < new->id) new = new->idom;
- }
- }
- }
- if (blk->idom != new) {
- blk->idom = new;
- changed = 1;
- }
- } while ((blk = blk->lnext) != fn->entry);
- }
- fn->prop |= FNBLKID | FNDOM;
-}
-
-static void
-loopmark(struct block *head, struct block *blk)
-{
- if (blk->id < head->id || blk->visit == head->id) return;
- blk->visit = head->id;
- ++blk->loop;
- for (int i = 0; i < blk->npred; ++i)
- loopmark(head, blkpred(blk, i));
-}
-
-void
-fillloop(struct function *fn)
-{
- struct block *b = fn->entry;
- int id = 0;
- FREQUIRE(FNRPO);
- do {
- b->id = id++;
- b->visit = -1u;
- b->loop = 0;
- } while ((b = b->lnext) != fn->entry);
- do {
- for (int i = 0; i < b->npred; ++i) {
- struct block *p = blkpred(b, i);
- if (p->id > b->id) { /* b is loop header */
- loopmark(b, p);
- }
- }
- } while ((b = b->lnext) != fn->entry);
- fn->prop |= FNBLKID;
-}
-
-/* vim:set ts=3 sw=3 expandtab: */
diff --git a/ir/cse.c b/ir/cse.c
deleted file mode 100644
index 23c5cf9..0000000
--- a/ir/cse.c
+++ /dev/null
@@ -1,92 +0,0 @@
-#include "ir.h"
-
-static inline bool
-pure(const struct instr *ins)
-{
- return oisarith(ins->op) || (oisload(ins->op) && !ins->keep);
-}
-
-static inline bool
-insequ(const struct instr *a, const struct instr *b)
-{
- if (a->op != b->op) return 0;
- enum op op = a->op;
- switch (opnarg[op]) {
- default: assert(0);
- case 2: if (a->r.bits != b->r.bits) return 0;
- case 1: if (a->l.bits != b->l.bits) return 0;
- }
- return 1;
-}
-
-static struct ht {
- uint t;
- ushort memno, cutoff;
- struct block *b;
-} *insht;
-static uint ninsht;
-
-static inline size_t
-hashins(const struct instr *ins)
-{
- return hashb(0, ins, sizeof *ins);
-}
-
-static bool
-doms(struct block *blk, struct block *b)
-{
- for (;; b = b->idom) {
- if (blk == b) return 1;
- if (blk == b->idom) return 1;
- if (blk->id > b->id) return 0;
- }
-}
-
-static int
-uniq(int t, struct block *blk, int cutoff, int memno)
-{
- assert((uint)t < MAXINSTR);
- struct instr *ins = &instrtab[t];
- if (!pure(ins)) return t;
- for (size_t h = hashins(&instrtab[t]), i = h;; ++i) {
- struct ht *p = &insht[i &= (ninsht-1)];
- if (!p->b) Put: {
- p->b = blk;
- p->memno = memno;
- p->cutoff = cutoff;
- return p->t = t;
- } else if (insequ(&instrtab[p->t], ins)) {
- if (p->cutoff == cutoff && (!oisload(ins->op) || p->memno == memno) && doms(p->b, blk))
- return p->t;
- goto Put;
- }
- }
-}
-
-void
-cselim(struct function *fn)
-{
- FREQUIRE(FNUSE | FNRPO | FNDOM | FNBLKID);
- extern int ninstr;
- for (ninsht = 32; ninsht <= ninstr; ninsht *= 2) ;
- insht = allocz(fn->passarena, ninsht * sizeof *insht, 0);
- int memno = 0, cutoff = 0;
- struct block *blk = fn->entry;
- do {
- ++memno;
- for (int i = 0; i < blk->ins.n; ++i) {
- int t = blk->ins.p[i], q;
- if ((q = uniq(t, blk, cutoff, memno)) != t) {
- replcuses(mkref(RTMP, t), mkref(RTMP, q));
- delinstr(blk, i--);
- } else if (oisstore(instrtab[t].op)) {
- /* assume everything alias everything */
- ++memno;
- } else if (instrtab[t].op == Ocall) {
- ++cutoff;
- }
- }
- } while ((blk = blk->lnext) != fn->entry);
-}
-
-/* vim:set ts=3 sw=3 expandtab: */
diff --git a/ir/dump.c b/ir/dump.c
deleted file mode 100644
index b0ce603..0000000
--- a/ir/dump.c
+++ /dev/null
@@ -1,319 +0,0 @@
-#include "ir.h"
-#include "../obj/obj.h"
-#include "../endian.h"
-
-static int nextdat;
-
-static struct wbuf *out = &bstdout;
-
-static bool
-prilitdat(const struct irdat *dat, const char *prefix)
-{
- uchar *p;
- switch (dat->section) {
- default: assert(0);
- case Sdata: p = objout.data.p + dat->off; break;
- case Srodata: p = objout.rodata.p + dat->off; break;
- case Stext: p = objout.textbegin + dat->off; break;
- }
- if (dat->ctype.t == TYARRAY && typechild(dat->ctype).t == TYCHAR && dat->siz-1 < 60 && p[dat->siz-1] == 0) {
- bfmt(out, "%s%'S", prefix, p, dat->siz-1);
- } else if (dat->ctype.t == TYFLOAT) {
- bfmt(out, "%s%f", prefix, rdf32targ(p));
- } else if (dat->ctype.t == TYDOUBLE) {
- bfmt(out, "%s%f", prefix, rdf64targ(p));
- } else if (dat->ctype.t == TYVLONG) {
- bfmt(out, "%s0x%lx", prefix, rd64targ(p));
- } else return 0;
- return 1;
-}
-
-static void
-pridat(const struct irdat *dat)
-{
- static const char *snames[] = { [Sdata] = ".data", [Srodata] = ".rodata", [Stext] = ".text" };
- uchar *p;
- switch (dat->section) {
- default: assert(0);
- case Sdata: p = objout.data.p + dat->off; break;
- case Srodata: p = objout.rodata.p + dat->off; break;
- case Stext: p = objout.textbegin + dat->off; break;
- }
- enum {
- MINZERO = 4,
- MAXLINE = 60,
- };
- int npri = 0;
- int strbegin = 0, nstr = 0;
- bfmt(out, "%s %ty %y(align %d, size %d):\n\t", snames[dat->section], dat->ctype, dat->name, dat->align, dat->siz);
- if (!prilitdat(dat, "lit: ")) {
- for (int i = 0; i < dat->siz; ++i) {
- int c = p[i];
- if (npri > MAXLINE) {
- npri = 0;
- bfmt(out, "\n\t");
- }
- if (aisprint(c)) {
- if (!nstr++) strbegin = i;
- } else {
- if (nstr) {
- npri += bfmt(out, "asc %'S,", p+strbegin, nstr);
- nstr = 0;
- bfmt(out, "b ");
- }
- npri += bfmt(out, "%d,", c);
- }
- }
- if (nstr) npri += bfmt(out, "asc %'S,", p+strbegin, nstr);
- }
- bfmt(out, "\n");
-}
-
-static const char *clsname[] = {
- "?", "i32", "i64", "ptr", "f32", "f64"
-};
-
-static void
-prityp(union irtype typ)
-{
- if (!typ.isagg)
- bfmt(out, clsname[typ.cls]);
- else {
- const struct typedata *td = &typedata[typ.dat];
- const char *tag = td->t == TYSTRUCT ? "struct" : "union";
- if (ttypenames[td->id])
- bfmt(out, "%s.%s.%d", tag, ttypenames[td->id], td->id);
- else
- bfmt(out, "%s.%d", tag, td->id);
- }
-}
-
-static const char *intrinname[] = {
- "?\??",
-#define _(b,...) #b,
-#include "intrin.def"
-#undef _
-};
-
-static void
-dumpref(enum op o, union ref ref)
-{
- struct xcon *con;
- switch (ref.t) {
- case RXXX:
- if (ref.bits == UNDREF.bits)
- bfmt(out, "undef");
- else
- bfmt(out, "??");
- break;
- case RTMP:
- bfmt(out, "%%%d", ref.i);
- if (instrtab[ref.i].reg)
- bfmt(out, "(%s)", mctarg->rnames[instrtab[ref.i].reg-1]);
- break;
- case RREG:
- bfmt(out, "%s", mctarg->rnames[ref.i]);
- break;
- case RICON:
- if (o == Ointrin) bfmt(out, "\"%s\"", intrinname[ref.i]);
- else bfmt(out, "%d", ref.i);
- break;
- case RXCON:
- con = &contab.p[ref.i];
- if (con->deref) bfmt(out, "*[");
- if (con->issym || con->isdat) {
- bfmt(out, "$%y", xcon2sym(ref.i));
- if (con->isdat) {
- struct irdat *dat = &dattab.p[con->dat];
- if (prilitdat(dat, " (= ")) {
- if (isscalar(dat->ctype)) {
- struct wbuf tmp = MEMBUF((char [1]){0}, 1);
- bfmt(&tmp, "%ty", dat->ctype);
- ioputc(out, *tmp.buf);
- }
- ioputc(out, ')');
- }
- }
- } else switch (con->cls) {
- case KI32: bfmt(out, "%d", (int)con->i); break;
- case KI64: bfmt(out, "%ld", con->i); break;
- case KPTR: bfmt(out, "%'lx", con->i); break;
- case KF32: bfmt(out, "%fs", con->f); break;
- case KF64: bfmt(out, "%fd", con->f); break;
- default: assert(0);
- }
- if (con->deref) bfmt(out, "]");
- break;
- case RTYPE:
- prityp(ref2type(ref));
- break;
- case RADDR:
- {
- const struct addr *addr = &addrtab.p[ref.i];
- bool k = 0;
- bfmt(out, "addr [");
- if ((k = addr->base.bits)) dumpref(0, addr->base);
- if (addr->index.bits) {
- if (k) bfmt(out, " + ");
- dumpref(0, addr->index);
- if (addr->shift)
- bfmt(out, " * %d", 1<<addr->shift);
- k = 1;
- }
- if (k && addr->disp) {
- bfmt(out, " %c %d", "-+"[addr->disp > 0], addr->disp < 0 ? -addr->disp : addr->disp);
- }
- assert(k);
- bfmt(out, "]");
- }
- break;
- case RSTACK:
- bfmt(out, "[stack %d]", ref.i);
- break;
- default: assert(!"ref");
- }
-}
-
-static void
-dumpcall(struct call *call)
-{
- if (call->ret.isagg) {
- bfmt(out, "sret ");
- prityp(call->ret);
- bfmt(out, ", ");
- }
- if (call->vararg < 0) {
- bfmt(out, "#%d", call->narg);
- } else {
- assert(call->vararg <= call->narg);
- bfmt(out, "#%d, ... #%d", call->vararg, call->narg - call->vararg);
- }
-}
-
-static void
-dumpinst(const struct instr *ins)
-{
- int i;
- if (ins->op == Omove) {
- bfmt(out, "move %s ", clsname[ins->cls]);
- } else {
- enum irclass cls = insrescls(*ins);
- if (ins->reg) {
- if (cls)
- bfmt(out, "%s ", clsname[cls]);
- bfmt(out, "(%%%d)%s = ", ins - instrtab, mctarg->rnames[ins->reg - 1]);
- } else if (cls) {
- bfmt(out, "%s %%%d", clsname[cls], ins - instrtab);
- bfmt(out, " = ");
- }
- bfmt(out, "%s ", opnames[ins->op]);
- if (oiscmp(ins->op))
- bfmt(out, "%s ", clsname[ins->cls]);
- }
- for (i = 0; i < opnarg[ins->op]; ++i) {
- if (i) bfmt(out, ", ");
- if (i == 1 && (ins->op == Ocall || ins->op == Ointrin)) {
- dumpcall(&calltab.p[ins->r.i]);
- } else {
- dumpref(ins->op, (&ins->l)[i]);
- }
- }
- if (oisalloca(ins->op) && ins->l.t == RICON) {
- bfmt(out, " \t; %d bytes", ins->l.i << (ins->op - Oalloca1));
- }
- bfmt(out, "\n");
-}
-
-void
-dumpblk(struct function *fn, struct block *blk)
-{
- static const char *jnames[] = { 0, "b", "ret", "trap" };
- int i;
- bfmt(out, " @%d:", blk->id);
- if (blk->npred) {
- bfmt(out, " \t; preds:");
- for (i = 0; i < blk->npred; ++i) {
- if (i) ioputc(out, ',');
- bfmt(out, " @%d", blkpred(blk, i)->id);
- }
- }
- if (fn->prop & FNDOM && blk->idom)
- bfmt(out, "\t; idom: @%d", blk->idom->id);
- if (blk->loop)
- bfmt(out, "\t; loop depth: %d", blk->loop);
- ioputc(out, '\n');
- for (i = 0; i < blk->phi.n; ++i) {
- struct instr *phi = &instrtab[blk->phi.p[i]];
- union ref *refs = phitab.p[phi->l.i];
- if (i == 0) bfmt(out, "%-4d", blk->inumstart);
- else bfmt(out, " |> ");
- bfmt(out, " %s ", clsname[phi->cls]);
- if (!phi->reg) bfmt(out, "%%%d = %s ", blk->phi.p[i], opnames[phi->op]);
- else bfmt(out, "(%%%d)%s = %s ", phi - instrtab, mctarg->rnames[phi->reg-1], opnames[phi->op]);
- for (int i = 0; i < blk->npred; ++i) {
- if (i) bfmt(out, ", ");
- bfmt(out, "@%d ", blkpred(blk, i)->id);
- dumpref(0, refs[i]);
- }
- ioputc(out, '\n');
- }
- for (i = 0; i < blk->ins.n; ++i) {
- bfmt(out, "%-4d ", blk->inumstart + 1 + i);
- dumpinst(&instrtab[blk->ins.p[i]]);
- }
- bfmt(out, "%-4d %s ", blk->inumstart + 1 + i, jnames[blk->jmp.t]);
- if (blk->jmp.t == Jret && blk->jmp.arg[0].bits && !fn->nabiret && isagg(fn->retty)) {
- /* un-lowered struct return */
- dumpref(0, mktyperef(mkirtype(fn->retty)));
- bfmt(out, " ");
- }
- for (i = 0; i < 2; ++i) {
- if (!blk->jmp.arg[i].bits) break;
- if (i > 0) bfmt(out, ", ");
- dumpref(0, blk->jmp.arg[i]);
- }
- if (i && blk->s1) bfmt(out, ", ");
- if (blk->s1 && blk->s2) bfmt(out, "@%d, @%d", blk->s1->id, blk->s2->id);
- else if (blk->s1) bfmt(out, "@%d", blk->s1->id);
- bfmt(out, "\n");
-}
-
-void
-irdump(struct function *fn)
-{
- struct block *blk;
-
- /* print datas that have never been printed before */
- while (nextdat < dattab.n) pridat(&dattab.p[nextdat++]);
-
- bfmt(out, "function %s : %ty\n", fn->name, fn->fnty);
- if (fn->abiarg || fn->nabiret) {
- bfmt(out, "abi: (");
- for (int i = 0; i < fn->nabiarg; ++i) {
- if (i > 0) bfmt(out, ", ");
- if (!fn->abiarg[i].isstk) {
- bfmt(out, "%s", mctarg->rnames[fn->abiarg[i].reg]);
- } else {
- prityp(fn->abiarg[i].ty);
- bfmt(out, " <stk>");
- }
- }
- bfmt(out, ")");
- if (fn->retty.t != TYVOID) {
- bfmt(out, " -> %s", mctarg->rnames[fn->abiret[0].reg]);
- if (fn->nabiret > 1)
- bfmt(out, ", %s", mctarg->rnames[fn->abiret[1].reg]);
- }
- bfmt(out, "\n");
- }
- numberinstrs(fn);
- blk = fn->entry;
- do {
- assert(blk->lprev->lnext == blk);
- dumpblk(fn, blk);
- assert(blk->lnext != NULL);
- } while ((blk = blk->lnext) != fn->entry);
- bfmt(out, "\n");
-}
-
-/* vim:set ts=3 sw=3 expandtab: */
diff --git a/ir/fold.c b/ir/fold.c
deleted file mode 100644
index 4c9861e..0000000
--- a/ir/fold.c
+++ /dev/null
@@ -1,133 +0,0 @@
-#include "ir.h"
-#include "../endian.h"
-#include <limits.h>
-
-#ifdef __clang__
-__attribute__((no_sanitize("float-cast-overflow"))) /* silence UBsan for float->int overflow */
-#endif
-static union ref
-foldint(enum op op, enum irclass k, union ref lr, union ref rr)
-{
- vlong x;
- union {
- vlong s;
- uvlong u;
- } l = {.s = intconval(lr)}, r = {.s = intconval(rr)};
- bool w = cls2siz[k] == 8;
- if (in_range(op, Odiv, Ourem)) assert(r.u != 0);
- switch (op) {
- case Ocopy: x = l.s; break;
- case Oneg: x = -l.s; break;
- case Onot: x = ~l.s; break;
-#define CVTF2I(TF, TI) do { \
- TF f = fltconval(lr); \
- if (f != f) x = 0; \
- else x = (TI)f; \
-} while (0)
- case Ocvtf32s: if (w) CVTF2I(float, vlong); else CVTF2I(float, int); break;
- case Ocvtf32u: if (w) CVTF2I(float, uvlong); else CVTF2I(float, uint); break;
- case Ocvtf64s: if (w) CVTF2I(double, vlong); else CVTF2I(double, int); break;
- case Ocvtf64u: if (w) CVTF2I(double, uvlong); else CVTF2I(double, uint); break;
-#undef CVTF2I
- case Oexts8: x = (schar)l.s; break;
- case Oextu8: x = (uchar)l.s; break;
- case Oexts16: x = (short)l.s; break;
- case Oextu16: x = (ushort)l.s; break;
- case Oexts32: x = (int)l.s; break;
- case Oextu32: x = (uint)l.s; break;
- case Obswap16: x = bswap16(l.u); break;
- case Obswap32: x = bswap32(l.u); break;
- case Obswap64: x = bswap64(l.u); break;
- case Oadd: x = l.u + r.u; break;
- case Osub: x = l.u - r.u; break;
- case Omul: x = l.u * r.u; break;
- case Odiv: if (r.s == -1 && (w ? l.s == LLONG_MIN : (int)l.s == INT_MIN)) x = l.s;
- else x = w ? l.s / r.s : (int)l.s / (int)r.s;
- break;
- case Oudiv: x = w ? l.u / r.u : (uint)l.u / (uint)r.u; break;
- case Orem: if (r.s == -1 && (w ? l.s == LLONG_MIN : (int)l.s == INT_MIN)) x = 0;
- else x = w ? l.s % r.s : (int)l.s % (int)r.s;
- break;
- case Ourem: x = w ? l.u % r.u : (uint)l.u % (uint)r.u; break;
- case Oand: x = l.u & r.u; break;
- case Oior: x = l.u | r.u; break;
- case Oxor: x = l.u ^ r.u; break;
- case Oshl: x = l.u << (r.u & (w ? 63 : 31)); break;
- case Oslr: x = w ? l.u >> (r.u&63) : (int)l.s >> (r.u&31); break;
- case Osar: x = w ? l.s >> (r.u&63) : (int)l.s >> (r.u&31); break;
- case Oequ: x = l.s == r.s; break;
- case Oneq: x = l.s != r.s; break;
- case Olth: x = l.s < r.s; break;
- case Ogth: x = l.s > r.s; break;
- case Olte: x = l.s <= r.s; break;
- case Ogte: x = l.s >= r.s; break;
- case Oulth: x = l.u < r.u; break;
- case Ougth: x = l.u > r.u; break;
- case Oulte: x = l.u <= r.u; break;
- case Ougte: x = l.u >= r.u; break;
- default: assert(0);
- }
- if (cls2siz[k] < 8) x = (int)x;
- return mkintcon(k, x);
-}
-
-static union ref
-foldflt(enum op op, enum irclass k, union ref lr, union ref rr)
-{
- int xi;
- double x, l = fltconval(lr), r = fltconval(rr);
- bool w = k == KF64;
- switch (op) {
- case Ocopy: x = l; break;
- case Oneg: x = -l; break;
- case Ocvtf32f64: x = (float)l; break;
- case Ocvtf64f32: x = (float)l; break;
- case Ocvts32f: x = (int)intconval(lr); break;
- case Ocvtu32f: x = (int)intconval(lr); break;
- case Ocvts64f: x = (vlong)intconval(lr); break;
- case Ocvtu64f: x = (uvlong)intconval(lr); break;
- case Oadd: x = l + r; break;
- case Osub: x = l - r; break;
- case Omul: x = l * r; break;
- case Odiv: x = l / r; break;
- case Oequ: xi = l == r; goto Cmp;
- case Oneq: xi = l != r; goto Cmp;
- case Olth: xi = l < r; goto Cmp;
- case Ogth: xi = l > r; goto Cmp;
- case Olte: xi = l <= r; goto Cmp;
- case Ogte: xi = l >= r; Cmp: return mkref(RICON, xi);
- default: assert(0);
- }
- if (!w) x = (float)x;
- return mkfltcon(k, x);
-}
-
-bool
-foldbinop(union ref *to, enum op op, enum irclass k, union ref l, union ref r)
-{
- if (!oisarith(op))
- return 0;
- if (!isnumcon(l) || !isnumcon(r)) return 0;
- if (in_range(op, Odiv, Ourem) && kisint(k) && intconval(r) == 0)
- return 0;
- if (kisint(k))
- *to = foldint(op, k, l, r);
- else
- *to = foldflt(op, k, l, r);
- return 1;
-}
-
-bool
-foldunop(union ref *to, enum op op, enum irclass k, union ref a)
-{
- if (!isnumcon(a)) return 0;
- if (op != Ocopy && !oisarith(op))
- return 0;
- if (kisint(k))
- *to = foldint(op, k, a, ZEROREF);
- else
- *to = foldflt(op, k, a, ZEROREF);
- return 1;
-}
-
-/* vim:set ts=3 sw=3 expandtab: */
diff --git a/ir/inliner.c b/ir/inliner.c
deleted file mode 100644
index b99d3dc..0000000
--- a/ir/inliner.c
+++ /dev/null
@@ -1,309 +0,0 @@
-#include "ir.h"
-
-struct savedfunc {
- uint ninstr;
- struct instr *instrtab;
- struct xcon *contab;
- struct call *calltab;
- union ref **phitab;
- struct block *entry;
- union type fnty, retty;
- struct abiarg *abiarg, abiret[2];
- ushort nabiarg, nabiret;
- ushort nretpoints;
-};
-
-enum { MAX_INLINED_FN_NINS = 50,
- MAX_INLINED_FN_NBLK = 16, };
-
-static pmap_of(struct savedfunc *) savedfns;
-
-bool
-maybeinlinee(struct function *fn)
-{
- static struct arena *savearena;
- extern int ninstr;
-
- // TODO better heuristics
- if (ccopt.o < OPT1) return 0;
- if (!fn->inlin && ccopt.o < OPT2) return 0;
- if (ninstr > MAX_INLINED_FN_NINS) return 0;
- if (fn->nblk > MAX_INLINED_FN_NBLK) return 0;
- for (int i = 0; i < fn->nabiarg; ++i) {
- /* TODO inlining functions with stack args */
- if (fn->abiarg[i].isstk) return 0;
- }
- if (fn->nabiret > 1) return 0; /* TODO 2reg scalar return */
-
- if (!savearena) {
- enum { N = 1<<12 };
- static union { char m[sizeof(struct arena) + N]; struct arena *_align; } amem;
- savearena = (void *)amem.m;
- savearena->cap = N;
- }
-
- if (ccopt.dbg.y) {
- bfmt(ccopt.dbgout, "> stashing '%s' for inlining\n", fn->name);
- }
- struct savedfunc *sv = allocz(&savearena, sizeof *sv, 0);
- sv->fnty = fn->fnty, sv->retty = fn->retty;
- if (fn->abiarg)
- sv->abiarg = alloccopy(&savearena, fn->abiarg, sizeof *sv->abiarg * fn->nabiarg, 0);
- sv->nabiarg = fn->nabiarg;
- if ((sv->nabiret = fn->nabiret) > 0)
- memcpy(sv->abiret, fn->abiret, sizeof sv->abiret);
- struct block *bmap[MAX_INLINED_FN_NBLK];
- struct block *b = fn->entry;
- int id = 0;
- do {
- b->id = id++;
- struct block *q = alloccopy(&savearena, b, sizeof *b, 0);
- if (q->phi.n)
- q->phi.p = alloccopy(&savearena, q->phi.p, sizeof *q->phi.p * q->phi.n, 0);
- if (q->ins.n)
- q->ins.p = alloccopy(&savearena, q->ins.p, sizeof *q->ins.p * q->ins.n, 0);
- if (q->npred > 1)
- q->_pred = alloccopy(&savearena, q->_pred, sizeof *q->_pred * q->npred, 0);
- q->lprev = NULL;
- q->idom = NULL;
- bmap[b->id] = q;
- sv->nretpoints += b->jmp.t == Jret;
- } while ((b = b->lnext) != fn->entry);
- b = sv->entry = bmap[0];
- do {
- if (b->s1) b->s1 = bmap[b->s1->id];
- if (b->s2) b->s2 = bmap[b->s2->id];
- if (b->npred == 1)
- b->_pred0 = bmap[b->_pred0->id];
- else for (int i = 0; i < b->npred; ++i)
- b->_pred[i] = bmap[b->_pred[i]->id];
- b->lnext = b->lnext == fn->entry ? NULL : bmap[b->lnext->id];
- } while ((b = b->lnext));
-
- sv->instrtab = alloccopy(&savearena, instrtab, sizeof *instrtab * (sv->ninstr = ninstr), 0);
- sv->contab = alloccopy(&savearena, contab.p, sizeof *contab.p * contab.n, 0);
- if (calltab.n) {
- sv->calltab = alloccopy(&savearena, calltab.p, sizeof *calltab.p * calltab.n, 0);
- for (int i = 0; i < calltab.n; ++i) {
- if (sv->calltab[i].abiarg)
- sv->calltab[i].abiarg = alloccopy(&savearena, sv->calltab[i].abiarg,
- sv->calltab[i].narg * sizeof *sv->calltab[i].abiarg, 0);
- }
- }
- if (phitab.n) {
- sv->phitab = alloc(&savearena, sizeof *phitab.p * phitab.n, 0);
- for (int i = 0; i < phitab.n; ++i) {
- sv->phitab[i] = alloccopy(&savearena, phitab.p[i], sizeof *phitab.p[i] * xbcap(phitab.p[i]), 0);
- }
- }
- pmap_set(&savedfns, fn->name, sv);
- return 1;
-}
-
-static union ref
-mapref(short *instrmap, struct savedfunc *sv, union ref r)
-{
- assert(r.bits);
- if (r.t == RTMP) return r.i = instrmap[r.i], r;
- if (r.t == RXCON) return newxcon(&sv->contab[r.i]);
- assert(r.t != RADDR);
- assert(r.t != RSTACK);
- return r;
-}
-
-static struct block *
-inlcall(struct function *fn, struct block *blk, int curi, struct savedfunc *sv)
-{
- int res = blk->ins.p[curi], res2;
- struct instr *ins = &instrtab[res];
- struct call *call = &calltab.p[ins->r.i];
- union ref retvals[64];
- union ref args[64];
- assert(sv->nabiret < 2 && sv->nretpoints < countof(retvals));
- for (int n = call->narg, i = curi-1; n > 0; --i) {
- assert(i >= 0);
- struct instr *ins = &instrtab[blk->ins.p[i]];
- if (ins->op == Oarg) {
- args[--n] = ins->r;
- *ins = mkinstr(Onop,0,);
- }
- }
- if (call->abiret[1].ty.bits) {
- assert(curi+1 < blk->ins.n);
- res2 = blk->ins.p[curi+1];
- assert(instrtab[res2].op == Ocall2r);
- }
- struct block *exit = blksplitafter(fn, blk, curi-1);
- if (!ins->cls) {
- *ins = mkinstr(Onop,0,);
- } else {
- if (sv->nretpoints == 1) {
- *ins = mkinstr(Ocopy, ins->cls, );
- } else {
- /* turn into a phi */
- *ins = mkinstr(Ophi, ins->cls, );
- exit->ins.p[0] = newinstr(blk, mkinstr(Onop,0,));
- vpush(&exit->phi, res);
- }
- }
-
- struct block *bmap[MAX_INLINED_FN_NBLK];
- short instrmap[MAX_INLINED_FN_NINS];
- for (struct block *b = sv->entry; b; b = b->lnext) {
- bmap[b->id] = newblk(fn);
- }
- for (int i = 0; i < sv->ninstr; ++i) {
- /* TODO don't wastefully allocate for tombstone instructions
- * - mark instructions some way when they are freed (put in instrfreelist)
- * */
- int allocinstr(void);
- instrmap[i] = allocinstr();
- }
-
- exit->npred = 0;
- exit->_pred0 = NULL;
- blk->s1 = bmap[0];
- int iret = 0;
- for (struct block *b = sv->entry, *prev = blk, *new; b; prev = new, b = b->lnext) {
- new = bmap[b->id];
- new->id = fn->nblk++;
- new->lprev = prev;
- prev->lnext = new;
- new->lnext = exit;
- exit->lprev = new;
- if (b->npred == 1) new->_pred0 = bmap[b->_pred0->id];
- else if (b->npred > 0) {
- xbgrow(&new->_pred, b->npred);
- for (int i = 0; i < b->npred; ++i)
- new->_pred[i] = bmap[b->_pred[i]->id];
- }
- new->npred = b->npred;
- vresize(&new->phi, b->phi.n);
- for (int i = 0; i < b->phi.n; ++i) {
- int t = b->phi.p[i];
- union ref *refs = NULL,
- *src = sv->phitab[sv->instrtab[t].l.i];
- xbgrow(&refs, b->npred);
- for (int i = 0; i < b->npred; ++i)
- refs[i] = mapref(instrmap, sv, src[i]);
- vpush(&phitab, refs);
- instrtab[instrmap[t]] = mkinstr(Ophi, sv->instrtab[t].cls, .l.i = phitab.n-1);
- new->phi.p[i] = instrmap[t];
- }
- vresize(&new->ins, b->ins.n);
- for (int i = 0; i < b->ins.n; ++i) {
- int t = b->ins.p[i];
- struct instr *ins = &instrtab[instrmap[t]];
- *ins = sv->instrtab[t];
- if (ins->op == Oparam) {
- ins->op = Ocopy;
- assert(ins->l.t == RICON && (uint) ins->l.i < call->narg);
- ins->l = args[ins->l.i];
- } else if (ins->op == Ocall || ins->op == Ointrin) {
- ins->l = mapref(instrmap, sv, ins->l);
- for (struct instr *ins2;
- ins->l.t == RTMP && (ins2 = &instrtab[ins->l.i])->op == Ocopy
- && (isaddrcon(ins2->l,0) || (ins2->l.t == RTMP && instrtab[ins->l.i].cls == KPTR));) {
- /* for an indirect function call, eagerly copy-propagate the callee. this allows
- * subsequent inlining of function pointers statically known after the inlining */
- ins->l = ins2->l;
- }
- vpush(&calltab, sv->calltab[ins->r.i]);
- ins->r.i = calltab.n-1;
- } else {
- if (ins->l.t) ins->l = mapref(instrmap, sv, ins->l);
- if (ins->r.t) ins->r = mapref(instrmap, sv, ins->r);
- }
- new->ins.p[i] = instrmap[t];
- }
- if (b->jmp.t == Jret) {
- new->jmp.t = Jb;
- new->s1 = exit;
- retvals[iret++] = b->jmp.arg[0].bits ? mapref(instrmap, sv, b->jmp.arg[0]) : UNDREF;
- addpred(exit, new);
- } else {
- new->jmp.t = b->jmp.t;
- for (int i = 0; i < 2; ++i) {
- if (!b->jmp.arg[i].bits) break;
- new->jmp.arg[i] = mapref(instrmap, sv, b->jmp.arg[i]);
- }
- }
- if (b->s1) {
- new->s1 = bmap[b->s1->id];
- if (b->s2) new->s2 = bmap[b->s2->id];
- }
- }
- exit->id = fn->nblk;
- fn->prop &= ~FNUSE;
- if (ins->cls && sv->nretpoints > 0) {
- assert(sv->nretpoints == exit->npred);
- if (sv->nretpoints == 1) {
- /* fill copy */
- ins->l = retvals[0];
- } else {
- /* fill phi */
- union ref *refs = NULL;
- xbgrow(&refs, sv->nretpoints);
- memcpy(refs, retvals, sizeof *refs * sv->nretpoints);
- vpush(&phitab, refs);
- ins->l = mkref(RXXX, phitab.n-1);
- }
- }
- bmap[0]->_pred0 = blk;
- bmap[0]->npred = 1;
- return exit;
-}
-
-enum { MAX_REC_INLINE = 16 };
-void
-doinline(struct function *fn)
-{
- if (calltab.n == 0) return;
- struct block *b = fn->entry;
- struct stack { /* stack of callees being inline expanded */
- struct block *b; /* block after the end of expansion */
- struct savedfunc *sv;
- } stkbuf[MAX_REC_INLINE], *stk = stkbuf + MAX_REC_INLINE, *stkend = stk;
- bool dumpbefore = 0;
- do {
- if (stk != stkend && b == stk->b)
- ++stk; /* pop */
- else if (stk == stkbuf) /* stack full? */
- continue;
- for (int i = 0; i < b->ins.n; ++i) {
- struct instr *ins = &instrtab[b->ins.p[i]];
- if (ins->op != Ocall) continue;
- if (!isaddrcon(ins->l,0)) continue;
- struct call *call = &calltab.p[ins->r.i];
- internstr fname = xcon2sym(ins->l.i);
- struct savedfunc **pcallee, *sv;
- if ((pcallee = pmap_get(&savedfns, fname))
- && (sv = *pcallee)->nabiarg == call->narg && call->vararg == -1
- && call->narg == sv->nabiarg
- && (!call->narg || !memcmp(sv->abiarg, call->abiarg, sizeof *sv->abiarg * sv->nabiarg))
- && !memcmp(sv->abiret, call->abiret, sizeof sv->abiret)) {
- for (struct stack *s = stk; s != stkend; ++s) {
- if (s->sv == sv) goto Skip; /* recursion encountered */
- }
- if (ccopt.dbg.y) {
- if (!dumpbefore) {
- bfmt(ccopt.dbgout, "<< Before inlining >>\n");
- irdump(fn);
- dumpbefore = 1;
- }
- }
-
- (--stk)->b = inlcall(fn, b, i, *pcallee);
- stk->sv = sv;
- if (ccopt.dbg.y) {
- bfmt(ccopt.dbgout, "<< After inlining '%s' (@%d-@%d) >>\n", fname, b->lnext->id, stk->b->id);
- irdump(fn);
- }
- break;
- }
- Skip:;
- }
- } while ((b = b->lnext) != fn->entry);
-}
-
-/* vim:set ts=3 sw=3 expandtab: */
diff --git a/ir/intrin.c b/ir/intrin.c
deleted file mode 100644
index ca49341..0000000
--- a/ir/intrin.c
+++ /dev/null
@@ -1,77 +0,0 @@
-#include "ir.h"
-
-struct arg { union ref *arg, *ty; };
-
-static int
-intrin(struct block *blk, int *curi, enum intrin in, struct arg *args, int narg, union irtype ret)
-{
- struct instr *this = &instrtab[blk->ins.p[*curi]];
- const struct typedata *td;
- union irtype ty;
- uint ncopy, step;
-
- switch (in) {
- case 0: assert(0);
- case INstructcopy:
- assert(narg == 2 && args[0].ty->bits == args[1].ty->bits);
- ty = ref2type(*args[0].ty);
- assert(ty.isagg);
- td = &typedata[ty.cls];
- step = td->align <= 8 ? td->align : 8;
- ncopy = td->siz / step;
- if (ncopy > 4) {
- enum irclass cls = siz2intcls[cls2siz[KPTR]];
- /* memcpy */
- *args[1].ty = *args[0].ty = mktyperef(cls2type(KPTR));
- insertinstr(blk, (*curi)++, mkarginstr(cls2type(cls), mkintcon(cls, td->siz)));
- *this = mkinstr(Ocall, 0, mksymref(intern("memcpy"), SFUNC), this->r);
- calltab.p[this->r.i].narg = 3;
- calltab.p[this->r.i].ret = cls2type(0);
- return 0;
- } else {
- delinstr(blk, (*curi)--);
- for (int off = 0; off < td->siz; off += step) {
- union ref psrc = *args[1].arg, pdst = *args[0].arg, src;
- if (off) {
- pdst = insertinstr(blk, ++*curi, mkinstr(Oadd, KPTR, *args[0].arg, mkref(RICON, off)));
- psrc = insertinstr(blk, ++*curi, mkinstr(Oadd, KPTR, *args[1].arg, mkref(RICON, off)));
- }
- src = insertinstr(blk, ++*curi, mkinstr(Oloads8 + 2*ilog2(step), step < 8 ? KI32 : KI64, psrc));
- insertinstr(blk, ++*curi, mkinstr(Ostorei8 + ilog2(step), 0, pdst, src));
- }
- return 1;
- }
- }
- assert(0);
-}
-
-void
-lowerintrin(struct function *fn)
-{
- struct block *blk = fn->entry;
- struct arg argsbuf[32];
- vec_of(struct arg) args = VINIT(argsbuf, countof(argsbuf));
-
- do {
- for (int i = 0; i < blk->ins.n; ++i) {
- struct instr *ins = &instrtab[blk->ins.p[i]];
- if (ins->op == Oarg)
- vpush(&args, ((struct arg){ &ins->r, &ins->l }));
- else if (ins->op == Ocall)
- vinit(&args, argsbuf, countof(argsbuf));
- else if (ins->op == Ointrin) {
- int arg0 = i - args.n;
- assert(calltab.p[ins->r.i].narg == args.n);
- if (intrin(blk, &i, ins->l.i, args.p, args.n, calltab.p[ins->r.i].ret))
- for (int j = args.n; j > 0; --j, --i)
- delinstr(blk, arg0);
- else
- abi0_call(fn, ins, blk, &i);
- vinit(&args, argsbuf, countof(argsbuf));
- }
- }
- assert(args.n == 0);
- } while ((blk = blk->lnext) != fn->entry);
-}
-
-/* vim:set ts=3 sw=3 expandtab: */
diff --git a/ir/intrin.def b/ir/intrin.def
deleted file mode 100644
index 2ccc3b5..0000000
--- a/ir/intrin.def
+++ /dev/null
@@ -1,2 +0,0 @@
-/* NAME NARG */
-_(structcopy, 2)
diff --git a/ir/ir.c b/ir/ir.c
deleted file mode 100644
index b612143..0000000
--- a/ir/ir.c
+++ /dev/null
@@ -1,689 +0,0 @@
-#include "ir.h"
-#include "../obj/obj.h"
-
-uchar type2cls[NTYPETAG];
-uchar cls2siz[] = { [KI32] = 4, [KI64] = 8, [KF32] = 4, [KF64] = 8 };
-uchar cls2load[] = {
- [KI32] = Oloadu32, [KI64] = Oloadi64,
- [KF32] = Oloadf32, [KF64] = Oloadf64, [KPTR] = -1
-}, cls2store[] = {
- [KI32] = Ostorei32, [KI64] = Ostorei64,
- [KF32] = Ostoref32, [KF64] = Ostoref64, [KPTR] = -1
-};
-const uchar siz2intcls[] = { [1] = KI32, [2] = KI32, [4] = KI32, [8] = KI64 };
-
-const char *opnames[] = {
- "?\??",
-#define _(o,...) #o,
-#include "op.def"
-#undef _
-};
-
-const uchar opnarg[] = {
- 0,
-#define _(o,n) n,
-#include "op.def"
-#undef _
-};
-
-struct instr instrtab[MAXINSTR];
-struct use *instruse[MAXINSTR];
-int ninstr;
-static int instrfreelist;
-static struct use *usefreelist;
-static struct arena **usearena;
-struct calltab calltab;
-struct phitab phitab;
-struct dattab dattab;
-struct contab contab;
-struct addrtab addrtab;
-static ushort *addrht;
-static int naddrht;
-int visitmark;
-
-void
-irinit(struct function *fn)
-{
- static struct call callsbuf[64];
- static union ref *phisbuf[64];
- static struct irdat datsbuf[64];
- static struct xcon consbuf[64];
- static struct addr addrsbuf[64];
-
- assert(fn->arena && !fn->passarena);
-
- ninstr = 0;
- instrfreelist = -1;
- usefreelist = NULL;
- usearena = fn->arena;
- vinit(&calltab, callsbuf, countof(callsbuf));
- for (int i = 0; i < phitab.n; ++i) xbfree(phitab.p[i]);
- vinit(&phitab, phisbuf, countof(phisbuf));
- vinit(&contab, consbuf, countof(consbuf));
- if (!dattab.p) vinit(&dattab, datsbuf, countof(datsbuf));
- naddrht = 128;
- if (!addrht) xbgrowz(&addrht, naddrht);
- else if (addrtab.n) memset(addrht, 0, xbcap(addrht) * sizeof *addrht);
- vinit(&addrtab, addrsbuf, countof(addrsbuf));
-
- if (!type2cls[TYINT]) {
- for (int i = TYBOOL; i <= TYUVLONG; ++i) {
- int siz = targ_primsizes[i];
- type2cls[i] = siz < 8 ? KI32 : KI64;
- }
- type2cls[TYFLOAT] = KF32;
- type2cls[TYDOUBLE] = KF64;
- type2cls[TYLDOUBLE] = KF64;
- type2cls[TYPTR] = KPTR;
- type2cls[TYARRAY] = KPTR;
- cls2siz[KPTR] = targ_primsizes[TYPTR];
- cls2load[KPTR] = targ_64bit ? Oloadi64 : Oloads32;
- cls2store[KPTR] = targ_64bit ? Ostorei64 : Ostorei32;
- }
- fn->entry = fn->curblk = allocz(fn->arena, sizeof(struct block), 0);
- fn->nblk = 1;
- fn->entry->lprev = fn->entry->lnext = fn->entry;
- fn->prop = FNUSE; /* builder keeps this */
-}
-
-static int
-newaddr(const struct addr *addr)
-{
- if (addrtab.n >= naddrht/4*3 /*75% load factor */) {
- xbgrowz(&addrht, naddrht*2);
- memset(addrht, 0, naddrht * sizeof *addrht);
- naddrht *= 2;
- for (int i = 0; i < addrtab.n; ++i) { /* rehash */
- const struct addr *addr = &addrtab.p[i];
- for (uint h = hashb(0, addr, sizeof *addr), j = h;; ++j) {
- if (!addrht[j &= naddrht - 1]) {
- addrht[j] = i+1;
- break;
- }
- }
- }
- }
- for (uint h = hashb(0, addr, sizeof *addr), i = h;; ++i) {
- i &= naddrht - 1;
- if (!addrht[i]) {
- vpush(&addrtab, *addr);
- return (addrht[i] = addrtab.n) - 1;
- } else if (!memcmp(&addrtab.p[addrht[i]-1], addr, sizeof *addr)) {
- return addrht[i] - 1;
- }
- }
-}
-
-union ref
-newxcon(const struct xcon *con)
-{
- assert((con->issym ^ con->isdat) || con->cls);
- vpush(&contab, *con);
- return mkref(RXCON, contab.n-1);
-}
-
-union irtype
-mkirtype(union type t)
-{
- if (t.t == TYVOID || isscalar(t))
- return (union irtype) { .cls = type2cls[scalartypet(t)] };
- assert(isagg(t));
- return (union irtype) { .isagg = 1, .dat = t.dat };
-}
-
-union ref
-mkintcon(enum irclass k, vlong i)
-{
- if (i < 1l << 28 && i >= -(1l << 28)) {
- return mkref(RICON, i);
- } else {
- struct xcon con = { .cls = k, .i = i };
- if (cls2siz[k] == 4) /* check upper half is zero or -1 */
- assert(in_range((i >> 32) + 1, 0, 1));
- return newxcon(&con);
- }
-}
-
-union ref
-mkfltcon(enum irclass k, double f)
-{
- struct xcon con = { .cls = k, .f = k == KF32 ? (float) f : f };
- return newxcon(&con);
-}
-
-union ref
-mksymref(internstr s, enum symflags symflags)
-{
- struct xcon con = { .issym = 1, .sym = s, .flag = symflags };
- return newxcon(&con);
-}
-
-union ref
-mkdatref(internstr name, union type ctype, uint siz, uint align,
- const void *bytes, uint n, bool deref, bool funclocal)
-{
- struct irdat dat = { .ctype = ctype, .align = align, .siz = siz, .name = name, .section = Srodata };
- if (funclocal && objout.code && align >= 4 && align <= targ_primsizes[TYPTR] && siz <= 16)
- dat.section = Stext;
-
- assert(n <= siz && siz && align);
- if (!name) {
- char buf[32];
- struct wbuf wbuf = MEMBUF(buf, sizeof buf);
-
- bfmt(&wbuf, ".L%c.%d", dat.section == Stext ? 'L' : 'D', dattab.n);
- ioputc(&wbuf, 0);
- assert(!wbuf.err);
- dat.name = name = intern(buf);
- }
- dat.off = objnewdat(name, dat.section, 0, siz, align);
- uchar *p = (dat.section == Stext ? objout.textbegin : objout.rodata.p) + dat.off;
- if (n) memcpy(p, bytes, n);
- if (dat.section != Stext) memset(p+n, 0, siz - n);
- vpush(&dattab, dat);
- return newxcon(&(struct xcon){.isdat = 1, .deref = deref, .dat = dattab.n - 1, .flag = SLOCAL});
-}
-
-internstr
-xcon2sym(int ref)
-{
- struct xcon con = contab.p[ref];
- assert(con.issym ^ con.isdat);
- return con.issym ? con.sym : dattab.p[con.dat].name;
-}
-
-struct instr
-mkalloca(uint siz, uint align)
-{
- struct instr ins = { .cls = KPTR };
- assert(ispo2(align) && align <= 16);
- ins.op = Oalloca1 + ilog2(align);
- ins.l = mkref(RICON, siz/align + (siz%align != 0));
- return ins;
-}
-
-union ref
-mkcallarg(union irtype ret, uint narg, int vararg)
-{
- struct call call = { .ret=ret, .narg=narg, .vararg=vararg };
- assert(vararg == -1 || (uint)vararg <= narg);
- vpush(&calltab, call);
- return mkref(RXXX, calltab.n-1);
-}
-
-union ref
-mkaddr(struct addr addr)
-{
- return mkref(RADDR, newaddr(&addr));
-}
-
-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 = NULL;
- xbgrow(&blk->_pred, 4);
- *blk->_pred = p0;
- }
- xbpush(&blk->_pred, &blk->npred, p);
-}
-
-void
-delpred(struct block *blk, struct block *p)
-{
- for (int i = 0; i < blk->npred; ++i) {
- if (blkpred(blk, i) == p) {
- for (int j = 0; j < blk->phi.n; ++j) {
- union ref *phiargs = phitab.p[instrtab[blk->phi.p[j]].l.i];
- for (int k = i; k < blk->npred - 1; ++k) {
- phiargs[k] = phiargs[k + 1];
- }
- }
- for (int k = i; k < blk->npred - 1; ++k) {
- blkpred(blk, k) = blkpred(blk, k + 1);
- }
- if (--blk->npred == 1) {
- struct block *p0 = blk->_pred[0];
- xbfree(blk->_pred);
- blk->_pred0 = p0;
- }
- return;
- }
- }
- //assert(0&&"blk not in p");
-}
-
-struct block *
-newblk(struct function *fn)
-{
- struct block *blk = allocz(fn->arena, sizeof(struct block), 0);
- blk->id = -1;
- return blk;
-}
-
-void
-freeblk(struct function *fn, struct block *blk)
-{
- if (blk->npred > 1)
- xbfree(blk->_pred);
- blk->npred = 0;
- blk->_pred = NULL;
-
- for (int i = 0; i < blk->phi.n; ++i) {
- int ui = blk->phi.p[i];
- union ref *r = phitab.p[instrtab[ui].l.i];
- for (int j = 0; j < blk->npred; ++j) {
- deluse(blk, ui, *r);
- }
- }
- for (int i = 0; i < blk->ins.n; ++i) {
- int ui = blk->ins.p[i];
- struct instr *ins = &instrtab[ui];
- if (ins->l.t == RTMP) deluse(blk, ui, ins->l);
- if (ins->r.t == RTMP) deluse(blk, ui, ins->r);
- }
- for (int i = 0; i < 2; ++i) {
- if (blk->jmp.arg[i].t == RTMP) deluse(blk, USERJUMP, blk->jmp.arg[i]);
- }
- if (blk->s1) delpred(blk->s1, blk);
- if (blk->s2) delpred(blk->s2, blk);
- vfree(&blk->phi);
- vfree(&blk->ins);
- if (blk->id != -1)
- --fn->nblk;
- if (blk->lprev) blk->lprev->lnext = blk->lnext;
- if (blk->lnext) blk->lnext->lprev = blk->lprev;
- blk->id = 1u<<31;
-}
-
-struct block *
-insertblk(struct function *fn, struct block *pred, struct block *subst)
-{
- struct block *new = newblk(fn);
- struct block **s = pred->s1 == subst ? &pred->s1 : &pred->s2;
- assert(*s == subst);
- new->lnext = pred->lnext;
- new->lprev = pred;
- pred->lnext->lprev = new;
- pred->lnext = new;
- *s = new;
- new->jmp.t = Jb;
- new->s1 = subst;
- addpred(new, pred);
- for (int i = 0; i < subst->npred; ++i) {
- if (blkpred(subst, i) == pred) {
- blkpred(subst, i) = new;
- ++fn->nblk;
- return new;
- }
- }
- assert(0);
-}
-
-struct block *
-blksplitafter(struct function *fn, struct block *blk, int idx)
-{
- struct block *new = newblk(fn);
- ++fn->nblk;
- new->lprev = blk;
- new->lnext = blk->lnext;
- blk->lnext = new;
- new->lnext->lprev = new;
- if (idx == -1) {
- new->ins = blk->ins;
- memset(&blk->ins, 0, sizeof blk->ins);
- } else {
- if (idx < blk->ins.n-1)
- vpushn(&new->ins, &blk->ins.p[idx+1], blk->ins.n-idx-1);
- blk->ins.n -= new->ins.n;
- }
- new->jmp = blk->jmp;
- blk->jmp.t = Jb;
- memset(blk->jmp.arg, 0, sizeof blk->jmp.arg);
- for (int i = 0; i < 2; ++i) {
- struct block *s = (&blk->s1)[i];
- if (s) for (int i = 0; i < s->npred; ++i) {
- if (blkpred(s, i) == blk)
- blkpred(s, i) = new;
- }
- }
- new->s1 = blk->s1, new->s2 = blk->s2;
- blk->s1 = new, blk->s2 = NULL;
- addpred(new, blk);
- fn->prop &= ~FNUSE;
- return new;
-}
-
-int
-allocinstr(void)
-{
- int t;
- if (instrfreelist != -1) {
- t = instrfreelist;
- memcpy(&instrfreelist, &instrtab[t], sizeof(int));
- if (instruse[t]) deluses(t);
- } else {
- assert(ninstr < countof(instrtab));
- t = ninstr++;
- instruse[t] = NULL;
- }
- return t;
-}
-
-void
-adduse(struct block *ublk, int ui, union ref r) {
- if (r.t != RTMP) return;
- struct use *use;
- if (usefreelist) {
- use = usefreelist;
- usefreelist = usefreelist->next;
- } else {
- use = alloc(usearena, sizeof *use, 0);
- }
- assert(use != instruse[r.i]);
- use->next = instruse[r.i];
- use->blk = ublk,
- use->u = ui;
- instruse[r.i] = use;
-}
-
-bool
-deluse(struct block *ublk, int ui, union ref r) {
- if (r.t != RTMP) return 0;
-
- for (struct use **puse = &instruse[r.i]; *puse; puse = &(*puse)->next) {
- struct use *use = *puse;
- if (use->blk == ublk && use->u == ui) {
- *puse = use->next;
- use->blk = 0;
- use->u = 0;
- use->next = usefreelist;
- usefreelist = use;
- return 1;
- }
- }
- return 0;
-}
-
-void
-filluses(struct function *fn)
-{
- struct block *blk = fn->entry;
-
- for (int i = 0; i < ninstr; ++i)
- deluses(i);
-
- do {
- for (int i = 0; i < blk->phi.n; ++i) {
- int ins = blk->phi.p[i];
- union ref *phi = phitab.p[instrtab[ins].l.i];
- for (int i = 0; i < blk->npred; ++i)
- adduse(blk, ins, phi[i]);
- }
- for (int i = 0; i < blk->ins.n; ++i) {
- int ins = blk->ins.p[i];
- adduse(blk, ins, instrtab[ins].l);
- adduse(blk, ins, instrtab[ins].r);
- }
- adduse(blk, USERJUMP, blk->jmp.arg[0]);
- adduse(blk, USERJUMP, blk->jmp.arg[1]);
- } while ((blk = blk->lnext) != fn->entry);
-
- fn->prop |= FNUSE;
-}
-
-int
-newinstr(struct block *at, struct instr ins)
-{
- int new = allocinstr();
- instrtab[new] = ins;
- if (at) {
- adduse(at, new, ins.l);
- adduse(at, new, ins.r);
- }
- return new;
-}
-
-union ref
-insertinstr(struct block *blk, int idx, struct instr ins)
-{
- int new = newinstr(blk, ins);
- if (idx == blk->ins.n) vpush(&blk->ins, new);
- else {
- assert(idx >= 0 && idx < blk->ins.n);
- vpush_(&blk->ins._vb, sizeof *blk->ins.p);
- vresize(&blk->ins, blk->ins.n);
- for (int i = blk->ins.n++; i > idx; --i)
- blk->ins.p[i] = blk->ins.p[i - 1];
- blk->ins.p[idx] = new;
- }
- return mkref(RTMP, new);
-}
-
-union ref
-insertphi(struct block *blk, enum irclass cls)
-{
- int new = allocinstr();
- union ref *refs = NULL;
- assert(blk->npred > 0);
- xbgrowz(&refs, blk->npred);
- vpush(&phitab, refs);
- instrtab[new] = mkinstr(Ophi, cls, mkref(RXXX, phitab.n - 1));
- vpush(&blk->phi, new);
- return mkref(RTMP, new);
-}
-
-uint
-numberinstrs(struct function *fn)
-{
- struct block *blk = fn->entry;
- int start = 0;
- do {
- blk->inumstart = start;
- start += blk->ins.n+2;
- } while ((blk = blk->lnext) != fn->entry);
- return start-1;
-}
-
-static bool
-reachablerec(struct function *fn, struct block *blk)
-{
- if (blk == fn->entry) return 1;
- markvisited(blk);
- if (blk->npred == 1 && !wasvisited(blkpred(blk, 0)))
- return reachablerec(fn, blkpred(blk, 0));
- else for (int i = 0; i < blk->npred; ++i) {
- struct block *p = blkpred(blk, i);
- if (!wasvisited(p) && reachablerec(fn, p)) return 1;
- }
- return 0;
-}
-
-bool
-blkreachable(struct function *fn, struct block *blk)
-{
- startbbvisit();
- return reachablerec(fn, blk);
-}
-
-/* require use */
-void
-replcuses(union ref from, union ref to)
-{
- assert(from.t == RTMP);
- for (struct use *use = instruse[from.i], *next; use; use = next) {
- union ref *u;
- int n, j;
- next = use->next;
- if (use->u == from.i) continue;
- if (use->u == USERJUMP) {
- u = &use->blk->jmp.arg[0];
- n = 2;
- } else if (instrtab[use->u].op == Ophi) {
- u = phitab.p[instrtab[use->u].l.i];
- n = use->blk->npred;
- if (use->blk->phi.n == 0) continue; /* shouldn't happen */
- } else {
- u = &instrtab[use->u].l;
- n = 2;
- }
-
- for (j = 0; j < n; ++j) {
- if (u[j].bits == from.bits) {
- u[j].bits = to.bits;
- adduse(use->blk, use->u, to);
- next = use;
- break;
- }
- }
- }
-}
-
-void
-deluses(int ins)
-{
- for (struct use *use = instruse[ins], *next; use; use = next) {
- next = use->next;
- use->blk = 0;
- use->u = 0;
- use->next = usefreelist;
- usefreelist = use;
- }
- instruse[ins] = NULL;
-}
-
-void
-delinstr(struct block *blk, int idx)
-{
- int t = blk->ins.p[idx];
- assert(idx >= 0 && idx < blk->ins.n);
- for (int i = 0; i < 2; ++i) {
- deluse(blk, t, (&instrtab[t].l)[i]);
- }
- memcpy(&instrtab[t], &instrfreelist, sizeof(int));
- instrfreelist = t;
- deluses(t);
- for (int i = idx; i < blk->ins.n - 1; ++i)
- blk->ins.p[i] = blk->ins.p[i + 1];
- --blk->ins.n;
-}
-
-void
-delphi(struct block *blk, int idx)
-{
- int t = blk->phi.p[idx];
- assert(idx >= 0 && idx < blk->phi.n);
- memcpy(&instrtab[t], &instrfreelist, sizeof(int));
- instrfreelist = t;
- deluses(t);
- for (int i = idx; i < blk->phi.n - 1; ++i)
- blk->phi.p[i] = blk->phi.p[i + 1];
- --blk->phi.n;
-}
-
-void
-delnops(struct block *blk)
-{
- int i, n, t;
- /* delete trailing nops */
- while (blk->ins.n > 0 && instrtab[t = blk->ins.p[blk->ins.n - 1]].op == Onop) {
- --blk->ins.n;
- deluses(t);
- memcpy(&instrtab[t], &instrfreelist, sizeof(int));
- instrfreelist = t;
- }
- /* delete rest of nops */
- for (i = blk->ins.n - 2, n = 0; i >= 0; --i) {
- if (instrtab[t = blk->ins.p[i]].op == Onop) {
- deluses(t);
- memcpy(&instrtab[t], &instrfreelist, sizeof(int));
- instrfreelist = t;
- ++n;
- } else if (n) {
- memmove(blk->ins.p+i+1, blk->ins.p+i+1+n, (blk->ins.n - n - i - 1)*sizeof *blk->ins.p);
- blk->ins.n -= n;
- n = 0;
- }
- }
- if (n)
- memmove(blk->ins.p, blk->ins.p + n, (blk->ins.n -= n)*sizeof *blk->ins.p);
-}
-
-void
-fillblkids(struct function *fn)
-{
- int i = 0;
- struct block *blk = fn->entry;
- do blk->id = i++; while ((blk = blk->lnext) != fn->entry);
-
- fn->prop |= FNBLKID;
-}
-
-/** Misc **/
-
-static void
-freefn(struct function *fn)
-{
- struct block *blk = fn->entry;
- do {
- if (blk->npred > 1) xbfree(blk->_pred);
- vfree(&blk->phi);
- vfree(&blk->ins);
- } while ((blk = blk->lnext) != fn->entry);
-}
-
-void
-irfini(struct function *fn)
-{
- extern int nerror;
- static union { char m[sizeof(struct arena) + (4<<10)]; struct arena *_align; } amem;
- struct arena *passarena = (void *)&amem.m;
- fn->passarena = &passarena;
- if (nerror) {
- freefn(fn);
- return;
- }
-
- abi0(fn);
- lowerintrin(fn);
- if (ccopt.o > OPT0) {
- mem2reg(fn);
- freearena(fn->passarena);
- copyopt(fn);
- }
- if (ccopt.o >= OPT1) {
- doinline(fn);
- filldom(fn);
- if (!(fn->prop & FNUSE)) filluses(fn);
- cselim(fn);
- freearena(fn->passarena);
- simpl(fn);
- freearena(fn->passarena);
- }
- if (maybeinlinee(fn)) {
- // goto Fin; XXX do this by having inline function rematerialization when symbol is actually referenced
- }
- lowerstack(fn);
- freearena(fn->passarena);
- if (ccopt.dbg.o) {
- bfmt(ccopt.dbgout, "<< Before isel >>\n");
- irdump(fn);
- }
- mctarg->isel(fn);
- regalloc(fn);
- freearena(fn->passarena);
- if (objout.code)
- mctarg->emit(fn);
-
-//Fin:
- freearena(fn->passarena);
- freefn(fn);
-}
-
-/* vim:set ts=3 sw=3 expandtab: */
diff --git a/ir/ir.h b/ir/ir.h
deleted file mode 100644
index ab3e474..0000000
--- a/ir/ir.h
+++ /dev/null
@@ -1,353 +0,0 @@
-#include "../common.h"
-#include "../type.h"
-
-enum irclass {
- KXXX,
- KI32, KI64, KPTR,
- KF32, KF64,
-};
-
-#define kisint(k) in_range((k), KI32, KPTR)
-#define kisflt(k) in_range((k), KF32, KF64)
-
-union irtype {
- struct { ushort _ : 1, cls : 15; };
- struct { ushort isagg : 1, dat : 15; };
- ushort bits;
-};
-
-struct irdat {
- uchar align : 6, globl : 1;
- uchar section;
- union type ctype;
- uint siz;
- uint off;
- internstr name;
-};
-
-enum symflags {
- SLOCAL = 1,
- SFUNC = 2,
-};
-struct xcon {
- bool issym, isdat, deref;
- uchar cls;
- uchar flag;
- union {
- internstr sym;
- int dat;
- vlong i;
- double f;
- };
-};
-
-struct abiarg {
- union irtype ty;
- union {
- struct { ushort _ : 1, reg : 15; };
- struct { ushort isstk : 1, stk : 15; };
- };
-};
-
-struct call {
- union irtype ret;
- ushort narg;
- short vararg; /* first variadic arg or -1 */
- ushort argstksiz;
- struct abiarg *abiarg;
- struct abiarg abiret[2];
- uchar r2off;
-};
-
-enum refkind {
- RXXX, /* used for empty ref (zeros), undef, and the special args of call,phi,etc */
- RTMP, /* reference to another instruction's result */
- RREG, /* machine register */
- RICON, /* small integer constants */
- RXCON, /* other constants (incl. external symbols) */
- RADDR, /* target-specific addressing mode */
- RTYPE, /* irtype */
- RSTACK, /* stack base offset */
-};
-
-union ref {
- struct { unsigned t : 3; signed i : 29; };
- uint bits;
-};
-static_assert(sizeof(union ref) == 4);
-
-struct addr {
- union ref base, index;
- int shift, disp;
-};
-
-#define insrescls(ins) (oiscmp((ins).op) ? KI32 : (ins).cls)
-#define NOREF ((union ref) {0})
-#define UNDREF ((union ref) {{ 0, -1 }})
-#define ZEROREF ((union ref) {{ RICON, 0 }})
-#define mkref(t, x) ((union ref) {{ (t), (x) }})
-#define mktyperef(t) ((union ref) {{ RTYPE, (t).bits }})
-#define ref2type(r) ((union irtype) {.bits = (r).i})
-#define rswap(a,b) do { union ref _t = (a); (a) = (b); (b) = _t; } while (0)
-
-enum op {
- Oxxx,
-#define _(o,...) O##o,
-#include "op.def"
-#undef _
- NOPER,
-};
-
-#define oiscmp(o) in_range(o, Oequ, Ougte)
-#define oisarith(o) in_range(o, Oneg, Ougte)
-#define oisalloca(o) in_range(o, Oalloca1, Oalloca16)
-#define oisstore(o) in_range(o, Ostorei8, Ostoref64)
-#define oisload(o) in_range(o, Oloads8, Oloadf64)
-extern const char *opnames[];
-extern const uchar opnarg[];
-
-enum intrin {
- INxxx,
-#define _(b,...) IN##b,
-#include "intrin.def"
-#undef _
-};
-
-struct instr {
- uchar op,
- cls; /* operation data class; also result class except for cmp ops (always i32) */
- uchar skip : 1, /* ignore during codegen: forms part of one machine instruction */
- keep : 1; /* for codegen, keep instr even if result seems unused */
- uchar inplace : 1; /* set (by isel) for instructions which modify its first arg in place */
- uchar reg; /* 0 -> no reg; else reg + 1 */
- union ref l, r; /* args */
-};
-static_assert(sizeof(struct instr) == 4*3);
-
-enum jumpkind { JXXX, Jb, Jret, Jtrap, };
-
-struct block {
- int id;
- int npred;
- int visit;
- ushort loop;
- int inumstart;
- union {
- struct block *_pred0;
- struct block **_pred;
- };
- struct block *lprev, *lnext;
- struct block *s1, *s2;
- struct block *idom;
- vec_of(ushort) phi;
- vec_of(ushort) ins;
- struct { uchar t; union ref arg[2]; } jmp;
-};
-
-#define blkpred(blk, i) 0[(blk)->npred < 2 ? &(blk)->_pred0 : &(blk)->_pred[i]]
-
-enum { USERJUMP = 0xFFFF };
-struct use { struct use *next; struct block *blk; ushort u; };
-
-enum { MAXREGS = 64 };
-/** register set **/
-typedef uvlong regset;
-#define BIT(x) (1ull<<(x))
-#define rsset(pS, r) (*(pS) |= 1ull << (r))
-#define rsclr(pS, r) (*(pS) &=~ (1ull << (r)))
-#define rstest(S, r) ((S) >> (r) & 1)
-static inline bool
-rsiter(int *i, uvlong rs)
-{
- if (*i > 63) return 0;
- uvlong mask = -(1ull << *i);
- if ((rs & mask) == 0) return 0;
- *i = lowestsetbit(rs & mask);
- return 1;
-}
-
-enum {
- FNBLKID = 1<<0,
- FNUSE = 1<<1,
- FNRPO = 1<<2,
- FNDOM = 1<<3,
-};
-struct function {
- struct arena **arena, **passarena;
- internstr name;
- struct block *entry, *curblk;
- struct use *use;
- short *nuse;
- union type fnty, retty;
- struct abiarg *abiarg, abiret[2];
- uint prop;
- uint nblk;
- int stksiz;
- ushort nabiarg, nabiret;
- bool globl;
- bool isleaf;
- bool inlin;
- regset regusage;
-};
-
-#define FREQUIRE(_prop) assert((fn->prop & (_prop)) == (_prop) && "preconditions not met")
-
-enum objkind { OBJELF };
-
-struct mctarg {
- short gpr0, /* first gpr */
- ngpr, /* gpr count */
- bpr, /* frame/base pointer reg */
- gprscratch, fprscratch, /* scratch registers for regalloc */
- fpr0, /* first fpr */
- nfpr; /* fpr count */
- regset rcallee, /* callee-saved */
- rglob; /* globally live (never used for regalloc) */
- const char (*rnames)[6];
- enum objkind objkind;
- /* abiret: lower return type:
- * scalar/small struct -> returns number of regs (1..2),
- * r & cls filled with reg and irclass of each scalar return,
- * for struct, r2off filled with byte offset within struct for 2nd reg
- * big struct -> returns 0, is passed via hidden pointer argument,
- * r[0] contains register for returning said pointer or -1,
- * r[1] contains register for hidden pointer argument,
- * *ni is set to 1 if said register is the first ABI integer argument
- */
- int (*abiret)(short r[2], uchar cls[2], uchar *r2off, int *ni, union irtype);
- /* abiarg: lower argument type:
- * scalar/small struct -> returns number of regs (1..2),
- * r & cls filled with reg and irclass of each scalar arg
- * for struct, r2off filled with byte offset within struct for 2nd reg
- * if reg == -1 -> stack
- * big struct -> returns 0,
- * if passed in stack cls[0] == 0, r[0] == negative SP offset
- * if passed by pointer cls[0] == KPTR, r[0] contains integer register
- * or negative SP offset if stack
- */
- int (*abiarg)(short r[2], uchar cls[2], uchar *r2off, int *ni, int *nf, int *ns, union irtype);
- void (*vastart)(struct function *, struct block *, int *curi);
- void (*vaarg)(struct function *, struct block *, int *curi);
- void (*isel)(struct function *);
- void (*emit)(struct function *);
-};
-
-enum { MAXINSTR = 1<<15 };
-
-/** ir.c **/
-extern uchar type2cls[];
-extern uchar cls2siz[];
-extern uchar cls2load[];
-extern uchar cls2store[];
-extern const uchar siz2intcls[];
-extern struct instr instrtab[];
-extern struct use *instruse[];
-extern struct calltab {vec_of(struct call);} calltab;
-extern struct phitab {vec_of(union ref *);} phitab;
-extern struct dattab {vec_of(struct irdat);} dattab;
-extern struct contab {vec_of(struct xcon);} contab;
-extern struct addrtab {vec_of(struct addr);} addrtab;
-extern int visitmark;
-#define mkinstr(O, C, ...) ((struct instr) { .op = (O), .cls = (C), .reg=0, __VA_ARGS__ })
-#define mkarginstr(ty, x) mkinstr(Oarg, 0, mktyperef(ty), (x))
-void irinit(struct function *);
-void irfini(struct function *);
-#define cls2type(k) ((union irtype){.cls=(k)})
-union irtype mkirtype(union type);
-union ref newxcon(const struct xcon *);
-union ref mkintcon(enum irclass, vlong);
-union ref mkfltcon(enum irclass, double);
-#define iscon(r) in_range((r).t, RICON, RXCON)
-#define concls(r) ((r).t == RICON ? KI32 : contab.p[(r).i].cls)
-#define isintcon(r) (iscon(r) && kisint(concls(r)))
-#define isfltcon(r) ((r).t == RXCON && kisflt(contab.p[(r).i].cls))
-#define isnumcon(r) ((r).t == RICON || ((r).t == RXCON && contab.p[(r).i].cls))
-#define isaddrcon(r,derefok) ((r).t == RXCON && !contab.p[(r).i].cls && (derefok || !contab.p[(r).i].deref))
-#define intconval(r) ((r).t == RICON ? (r).i : contab.p[(r).i].i)
-#define fltconval(r) ((r).t == RICON ? (r).i : contab.p[(r).i].f)
-union ref mksymref(internstr, enum symflags);
-union ref mkdatref(internstr sym, union type ctype, uint siz, uint align,
- const void *, uint n, bool deref, bool funclocal);
-internstr xcon2sym(int ref);
-struct instr mkalloca(uint siz, uint align);
-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);
-void addpred(struct block *blk, struct block *p);
-
-struct block *newblk(struct function *);
-void freeblk(struct function *, struct block *);
-struct block *insertblk(struct function *, struct block *pred, struct block *subst);
-struct block *blksplitafter(struct function *, struct block *, int idx);
-void adduse(struct block *ublk, int ui, union ref r);
-int newinstr(struct block *at, struct instr ins);
-union ref insertinstr(struct block *, int idx, struct instr);
-union ref insertphi(struct block *, enum irclass cls);
-void replcuses(union ref from, union ref to);
-bool deluse(struct block *ublk, int ui, union ref r);
-void deluses(int ins);
-void filluses(struct function *);
-void delinstr(struct block *, int idx);
-void delphi(struct block *, int idx);
-void delnops(struct block *blk);
-void delpred(struct block *blk, struct block *p);
-void fillblkids(struct function *);
-#define startbbvisit() (void)(++visitmark)
-#define wasvisited(blk) ((blk)->visit == visitmark)
-#define markvisited(blk) ((blk)->visit = visitmark)
-uint numberinstrs(struct function *);
-bool blkreachable(struct function *fn, struct block *blk);
-
-/** builder.c **/
-union ref irbinop(struct function *, enum op, enum irclass, union ref lhs, union ref rhs);
-union ref irunop(struct function *, enum op, enum irclass, union ref);
-union ref addinstr(struct function *, struct instr);
-union ref addphi(struct function *, enum irclass, union ref []);
-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 puttrap(struct function *);
-
-/** fold.c **/
-bool foldbinop(union ref *to, enum op, enum irclass, union ref l, union ref r);
-bool foldunop(union ref *to, enum op, enum irclass, union ref);
-
-/** irdump.c **/
-void irdump(struct function *);
-
-/** mem2reg.c **/
-void mem2reg(struct function *);
-
-/** ssa.c **/
-void copyopt(struct function *);
-
-/** cfg.c **/
-void sortrpo(struct function *);
-void filldom(struct function *);
-void fillloop(struct function *);
-
-/** abi0.c **/
-void abi0(struct function *);
-void abi0_call(struct function *, struct instr *, struct block *blk, int *curi);
-
-/** simpl.c **/
-void simpl(struct function *);
-
-/** cselim.c **/
-void cselim(struct function *);
-
-/** inliner.c **/
-bool maybeinlinee(struct function *);
-void doinline(struct function *);
-
-/** intrin.c **/
-void lowerintrin(struct function *);
-
-/** stack.c **/
-void lowerstack(struct function *);
-
-/** regalloc.c **/
-void regalloc(struct function *);
-
-/* vim:set ts=3 sw=3 expandtab: */
diff --git a/ir/mem2reg.c b/ir/mem2reg.c
deleted file mode 100644
index 7a5874c..0000000
--- a/ir/mem2reg.c
+++ /dev/null
@@ -1,317 +0,0 @@
-#include "ir.h"
-#include <stdlib.h> /* qsort */
-
-static const uchar loadszcls[] = {
- [Oloads8 - Oloads8] = 1|KI32<<4, [Oloadu8 - Oloads8] = 1|KI32<<4,
- [Oloads16 - Oloads8] = 2|KI32<<4, [Oloadu16 - Oloads8] = 2|KI32<<4,
- [Oloads32 - Oloads8] = 4|KI32<<4, [Oloadu32 - Oloads8] = 4|KI32<<4,
- [Oloadi64 - Oloads8] = 8|KI64<<4,
- [Oloadf32 - Oloads8] = 4|KF32<<4,
- [Oloadf64 - Oloads8] = 8|KF64<<4,
-};
-static const uchar load2ext[] = {
- [Oloads8 - Oloads8] = Oexts8, [Oloadu8 - Oloads8] = Oextu8,
- [Oloads16 - Oloads8] = Oexts16, [Oloadu16 - Oloads8] = Oextu16,
- [Oloads32 - Oloads8] = Oexts32, [Oloadu32 - Oloads8] = Oextu32,
- [Oloadi64 - Oloads8] = Ocopy,
-};
-static const uchar storesz[] = {
- [Ostorei8 - Ostorei8] = 1,
- [Ostorei16 - Ostorei8] = 2,
- [Ostorei32 - Ostorei8] = 4,
- [Ostorei64 - Ostorei8] = 8,
- [Ostoref32 - Ostorei8] = 4,
- [Ostoref64 - Ostorei8] = 8,
-};
-#define loadsz(o) (loadszcls[(o) - Oloads8] & 0xF)
-#define loadcls(o) (loadszcls[(o) - Oloads8] >> 4)
-#define load2ext(o) (load2ext[(o) - Oloads8])
-#define storesz(o) (storesz[(o) - Ostorei8])
-
-/* Implements algorithm in 'Simple and Efficient Construction of Static Single Assignment' (Braun et al) */
-
-struct ssabuilder {
- struct arena **arena;
- imap_of(union ref *) curdefs; /* map of var to (map of block to def of var) */
- struct bitset *sealed, /* set of sealed blocks */
- *marked; /* blocks marked, for 'Marker Algorithm' in the paper */
- int lastvisit;
- int nblk;
-};
-
-static union ref readvar(struct ssabuilder *, int var, enum irclass, struct block *);
-
-static union ref
-deltrivialphis(struct ssabuilder *sb, int var, struct block *blk, union ref phiref)
-{
- assert(instrtab[phiref.i].op == Ophi);
- union ref *args = phitab.p[instrtab[phiref.i].l.i];
- union ref same = {0};
- for (int i = 0; i < blk->npred; ++i) {
- if (args[i].bits == same.bits || args[i].bits == phiref.bits) {
- continue; /* unique value or self-reference */
- } if (same.bits != 0) {
- return phiref; /* non-trivial */
- }
- same = args[i];
- }
-
- if (same.bits == 0)
- same = UNDREF; /* the phi is unreachable or in the start block */
-
- /* replace uses */
- replcuses(phiref, same);
- union ref **pcurdefs = imap_get(&sb->curdefs, var);
- assert (pcurdefs);
- for (int i = blk->id; i < sb->nblk; ++i) {
- if ((*pcurdefs)[i].bits == phiref.bits)
- (*pcurdefs)[i] = same;
- }
-
- /* stops infinite recursion and marks phi for removal */
- instrtab[phiref.i].op = Onop;
-
- /* recursively try to remove all phi users as they might have become trivial */
-Redo:
- for (struct use *use = instruse[phiref.i]; use; use = use->next) {
- if (use->u != USERJUMP && instrtab[use->u].op == Ophi && use->u != phiref.i) {
- union ref it = mkref(RTMP, use->u);
- union ref vphi2 = deltrivialphis(sb, var, use->blk, it);
- if (vphi2.bits != it.bits) {
- same = vphi2;
- /* deletion happened so phiref use may have changed */
- goto Redo;
- }
- }
- }
- deluses(phiref.i);
-
- return same;
-}
-
-static union ref
-addphiargs(struct ssabuilder *sb, int var, enum irclass cls, struct block *blk, union ref phiref)
-{
- union ref *args = phitab.p[instrtab[phiref.i].l.i];
- for (int i = 0; i < blk->npred; ++i) {
- struct block *pred = blkpred(blk, i);
- args[i] = readvar(sb, var, cls, pred);
- adduse(blk, phiref.i, args[i]);
- }
- instrtab[phiref.i].r.bits = 0;
- return deltrivialphis(sb, var, blk, phiref);
-}
-
-static void
-writevar(struct ssabuilder *sb, int var, struct block *blk, union ref val)
-{
- union ref **pcurdefs;
- if (!(pcurdefs = imap_get(&sb->curdefs, var))) {
- pcurdefs = imap_set(&sb->curdefs, var, allocz(sb->arena, sb->nblk * sizeof(union ref), 0));
- }
- if (val.t == RTMP) assert(instrtab[val.i].op != Onop);
- (*pcurdefs)[blk->id] = val;
-}
-
-enum { RPENDINGPHI = 7 };
-static union ref
-readvarrec(struct ssabuilder *sb, int var, enum irclass cls, struct block *blk)
-{
- union ref val;
- assert(blk->npred > 0);
- if (!bstest(sb->sealed, blk->id)) { /* unsealed block */
- /* add pending phi */
- val = insertphi(blk, cls);
- instrtab[val.i].r = mkref(RPENDINGPHI, var);
- } else if (blk->npred == 1) { /* trivial case when block has a single predecessor */
- val = readvar(sb, var, cls, blkpred(blk, 0));
- } else if (!bstest(sb->marked, blk->id)) {
- /* Marker Algorithm to optimize the common case where a control flow join doesn't
- * need a phi function for the variable: mark the block in case we recursively reach
- * it again, collect defs from predecessors, only create a phi if they differ.
- * This avoids creating temporary trivial phi functions in acyclic data flow
- */
- bsset(sb->marked, blk->id);
- for (int i = 0; i < blk->npred; ++i) {
- struct block *pred = blkpred(blk, i);
- union ref it = readvar(sb, var, cls, pred);
- if (!bstest(sb->marked, blk->id)) {
- /* recursion reached this blk again, use its phi */
- union ref **pcurdefs = imap_get(&sb->curdefs, var);
- /* must have called writevar */
- assert(*pcurdefs && (*pcurdefs)[blk->id].bits);
- return (*pcurdefs)[blk->id];
- }
- if (i == 0) val = it;
- else if (it.bits != val.bits) /* found a different definition, must add phi */
- goto AddPhi;
- }
- bsclr(sb->marked, blk->id);
- } else { /* reached block while recursing */
- AddPhi:
- val = insertphi(blk, cls);
- writevar(sb, var, blk, val);
- val = addphiargs(sb, var, cls, blk, val);
- bsclr(sb->marked, blk->id);
- return val;
- }
- writevar(sb, var, blk, val);
- return val;
-}
-
-static union ref
-readvar(struct ssabuilder *sb, int var, enum irclass cls, struct block *blk)
-{
- union ref **pcurdefs;
- if ((pcurdefs = imap_get(&sb->curdefs, var)) && (*pcurdefs)[blk->id].bits)
- return (*pcurdefs)[blk->id];
- if (blk->npred == 0) /* entry block, var is read before being written to */
- return UNDREF;
- return readvarrec(sb, var, cls, blk);
-}
-
-static bool
-trysealrec(struct ssabuilder *sb, struct block *blk)
-{
-Recur:
- if (bstest(sb->sealed, blk->id)) return 1;
- if (blk->id > sb->lastvisit) return 0;
- markvisited(blk);
- for (int i = 0; i < blk->npred; ++i) {
- struct block *p = blkpred(blk, i);
- if (wasvisited(p)) continue;
- if (p->id > sb->lastvisit) return 0;
- }
-
- bsset(sb->sealed, blk->id);
- for (int i = 0; i < blk->phi.n; ++i) {
- struct instr *ins = &instrtab[blk->phi.p[i]];
- if (ins->r.t == RPENDINGPHI)
- addphiargs(sb, ins->r.i, ins->cls, blk, mkref(RTMP, blk->phi.p[i]));
- }
- if (blk->s1 && !blk->s2) {
- blk = blk->s1;
- goto Recur;
- } else if (blk->s1 && blk->s2) {
- trysealrec(sb, blk->s1);
- blk = blk->s2;
- goto Recur;
- }
- return 1;
-}
-
-static void
-tryseal(struct ssabuilder *sb, struct block *blk)
-{
- startbbvisit();
- trysealrec(sb, blk);
-}
-
-static int
-blkfindins(struct block *blk, int ins)
-{
- for (int i = 0; i < blk->phi.n; ++i)
- if (blk->phi.p[i] == ins) return -1;
- for (int i = 0; i < blk->ins.n; ++i)
- if (blk->ins.p[i] == ins) return i;
- assert(0 && "ins not in blk");
-}
-
-static int
-rcmpuse(const void *a, const void *b)
-{
- /* postorder sort */
- const struct use *ua = *(struct use **)a, *ub = *(struct use **)b;
- struct block *blk = ua->blk;
- if (ua->blk != ub->blk) return ub->blk->id - ua->blk->id;
- assert(ua->u != USERJUMP && ub->u != USERJUMP);
- return blkfindins(blk, ub->u) - blkfindins(blk, ua->u);
-}
-
-void
-mem2reg(struct function *fn)
-{
- struct ssabuilder sb = { fn->passarena, .nblk = fn->nblk };
-
- FREQUIRE(FNUSE);
-
- sb.sealed = allocz(sb.arena, BSSIZE(fn->nblk) * sizeof *sb.sealed, 0);
- sb.marked = allocz(sb.arena, BSSIZE(fn->nblk) * sizeof *sb.sealed, 0);
- sortrpo(fn);
-
- struct block *blk = fn->entry;
- do {
- for (int i = 0; i < blk->ins.n; ++i) {
- enum irclass k = 0;
- int sz = 0;
- enum op ext = Ocopy;
- int var = blk->ins.p[i];
- struct instr *ins = &instrtab[var];
- struct use *use;
-
- /* find allocas only used in loads/stores of uniform size */
- if (!oisalloca(ins->op) || !(use = instruse[var])) continue;
- struct use *usesbuf[64];
- vec_of(struct use *) uses = VINIT(usesbuf, countof(usesbuf));
- do {
- if (use->u == USERJUMP) goto Skip;
- struct instr *m = &instrtab[use->u];
- if (oisload(m->op) && (!sz || sz == loadsz(m->op))) {
- sz = loadsz(m->op);
- k = loadcls(m->op);
- if (sz < 4) ext = load2ext(m->op);
- } else if (oisstore(m->op) && m->l.bits == mkref(RTMP, var).bits
- && (!sz || sz == storesz(m->op))) {
- sz = storesz(m->op);
- } else goto Skip;
- vpush(&uses, use);
- } while ((use = use->next));
-
- /* visit uses in rpo */
- qsort(uses.p, uses.n, sizeof *uses.p, rcmpuse);
- for (int i = uses.n-1; i >= 0; --i) {
- use = uses.p[i];
- ins = &instrtab[use->u];
-
- if (oisstore(ins->op)) {
- writevar(&sb, var, use->blk, ins->r);
- *ins = mkinstr(Onop,0,);
- } else if (oisload(ins->op)) {
- union ref val = readvar(&sb, var, k = ins->cls, use->blk);
- adduse(use->blk, use->u, val);
- if (ext != Ocopy && isintcon(val)) { /* fold constant int extension */
- val = irunop(NULL, ext, k, val);
- assert(val.bits);
- ext = Ocopy;
- }
- *ins = mkinstr(ext, k, val);
- }
- }
- /* remove alloca */
- delinstr(blk, i--);
-
- Skip:
- vfree(&uses);
- }
-
- assert(sb.lastvisit == blk->id);
- ++sb.lastvisit;
- tryseal(&sb, blk);
- } while ((blk = blk->lnext) != fn->entry);
-
- do {
- /* remove phis marked for deletion */
- for (int i = 0; i < blk->phi.n; ++i)
- if (instrtab[blk->phi.p[i]].op == Onop)
- delphi(blk, i--);
- } while ((blk = blk->lnext) != fn->entry);
-
- imap_free(&sb.curdefs);
- if (ccopt.dbg.m) {
- bfmt(ccopt.dbgout, "<< After mem2reg >>\n");
- irdump(fn);
- }
-}
-
-
-/* vim:set ts=3 sw=3 expandtab: */
diff --git a/ir/op.def b/ir/op.def
deleted file mode 100644
index 4a18b4b..0000000
--- a/ir/op.def
+++ /dev/null
@@ -1,79 +0,0 @@
-/* OP NARG */
-_(nop, 0)
-_(copy, 1)
-_(move, 2)
-_(neg, 1)
-_(not, 1)
-_(cvtf32s, 1)
-_(cvtf32u, 1)
-_(cvtf32f64, 1)
-_(cvtf64s, 1)
-_(cvtf64u, 1)
-_(cvtf64f32, 1)
-_(cvts32f, 1)
-_(cvtu32f, 1)
-_(cvts64f, 1)
-_(cvtu64f, 1)
-_(exts8, 1)
-_(extu8, 1)
-_(exts16, 1)
-_(extu16, 1)
-_(exts32, 1)
-_(extu32, 1)
-_(bswap16, 1)
-_(bswap32, 1)
-_(bswap64, 1)
-_(add, 2)
-_(sub, 2)
-_(mul, 2)
-_(div, 2)
-_(udiv, 2)
-_(rem, 2)
-_(urem, 2)
-_(and, 2)
-_(ior, 2)
-_(xor, 2)
-_(shl, 2)
-_(sar, 2)
-_(slr, 2)
-_(equ, 2)
-_(neq, 2)
-_(lth, 2)
-_(gth, 2)
-_(lte, 2)
-_(gte, 2)
-_(ulth, 2)
-_(ugth, 2)
-_(ulte, 2)
-_(ugte, 2)
-_(alloca1, 1)
-_(alloca2, 1)
-_(alloca4, 1)
-_(alloca8, 1)
-_(alloca16, 1)
-_(loads8, 1)
-_(loadu8, 1)
-_(loads16, 1)
-_(loadu16, 1)
-_(loads32, 1)
-_(loadu32, 1)
-_(loadi64, 1)
-_(loadf32, 1)
-_(loadf64, 1)
-_(storei8, 2)
-_(storei16, 2)
-_(storei32, 2)
-_(storei64, 2)
-_(storef32, 2)
-_(storef64, 2)
-_(param, 2)
-_(arg, 2)
-_(call, 2)
-_(call2r, 1)
-_(intrin, 2)
-_(phi, 1)
-_(swap, 2)
-_(vastart, 1)
-_(vaarg, 2)
-/* machine-specific instructions */
-_(xvaprologue, 1)
diff --git a/ir/regalloc.c b/ir/regalloc.c
deleted file mode 100644
index 1200c77..0000000
--- a/ir/regalloc.c
+++ /dev/null
@@ -1,1417 +0,0 @@
-#include "ir.h"
-
-/** Implements linear scan register allocation **/
-/* Some references:
- * Linear Scan Register Allocation on SSA Form (Wimmer 2010)
- - https://c9x.me/compile/bib/Wimmer10a.pdf
- * Linear Scan Register Allocation in the Context of SSA Form
- and Register Constraints (Mössenböck 2002)
- - https://bernsteinbear.com/assets/img/linear-scan-ra-context-ssa.pdf
- */
-
-#if 1
-#define DBG(...) if(ccopt.dbg.r) bfmt(ccopt.dbgout, __VA_ARGS__)
-#else
-#define DBG(...) ((void)0)
-#endif
-
-/* The algorithm used here to introduce phis for temporaries whose definitions
- * appear later than some of its uses is very similar to that in mem2reg() */
-
-static int livelastblk;
-struct pendingphi { ushort var, phi; };
-static vec_of(struct pendingphi) *pendingphis;
-static int npendingphi;
-static ushort **curdefs;
-static union ref readvar(struct bitset *defined, enum irclass cls, int var, struct block *blk);
-
-static void
-fillphi(struct bitset *defined, union ref phi, enum irclass cls, int var, struct block *blk)
-{
- union ref *args = phitab.p[instrtab[phi.i].l.i];
- assert(blk->npred > 0);
- for (int i = 0; i < blk->npred; ++i)
- args[i] = readvar(defined, cls, var, blk);
-}
-
-static union ref
-readvar(struct bitset *defined, enum irclass cls, int var, struct block *blk)
-{
- union ref val;
-
- if (bstest(defined, var)) return mkref(RTMP, var);
- assert(cls && "?");
-
- /* memoed definition */
- if (xbcap(curdefs) > blk->id && xbcap(curdefs[blk->id]) > var && curdefs[blk->id][var])
- return mkref(RTMP, curdefs[blk->id][var]);
-
- xbgrowz(&curdefs, blk->id + 1);
- if (blk->id > livelastblk) {
- ++npendingphi;
- val = insertphi(blk, cls);
- xbgrowz(&pendingphis, blk->id + 1);
- vpush(&pendingphis[blk->id], ((struct pendingphi) { var, val.i }));
- } else if (blk->npred == 1) {
- val = readvar(defined, cls, var, blkpred(blk, 0));
- } else {
- val = insertphi(blk, cls);
- fillphi(defined, val, cls, var, blk);
- }
- xbgrowz(&curdefs[blk->id], var + 1);
- assert(val.i > 0);
- curdefs[blk->id][var] = val.i;
- return val;
-}
-
-static void
-liveuse(struct bitset *defined, struct instr *ins, union ref *r, struct block *blk)
-{
- int var;
- if (r->t == RADDR) {
- liveuse(defined, ins, &addrtab.p[r->i].base, blk);
- liveuse(defined, ins, &addrtab.p[r->i].index, blk);
- return;
- } else if (r->t != RTMP) return;
- var = r->i;
- if (bstest(defined, var)) return;
-
- *r = readvar(defined, insrescls(instrtab[r->i]), var, blk);
-}
-
-/* regalloc() assumes every use of a temporary is visited before its definition
- * so this pass fixes cases where that would not apply by introducing phi functions */
-static void
-fixlive(struct function *fn)
-{
- extern int ninstr;
- struct block *blk = fn->entry;
- struct bitset definedbuf[4] = {0};
- struct bitset *defined = definedbuf;
-
- if (BSSIZE(ninstr) >= countof(definedbuf))
- defined = xcalloc(sizeof *defined * BSSIZE(ninstr));
- npendingphi = 0;
-
- do {
- for (int i = 0; i < blk->phi.n; ++i) {
- int var = blk->phi.p[i];
- bsset(defined, var);
- }
-
- for (int i = 0; i < blk->ins.n; ++i) {
- int var = blk->ins.p[i];
- struct instr *ins = &instrtab[var];
- if (ins->l.t) liveuse(defined, ins, &ins->l, blk);
- if (ins->r.t) liveuse(defined, ins, &ins->r, blk);
- bsset(defined, var);
- }
- } while ((blk = blk->lnext) != fn->entry);
-
- do {
- vec_of(struct pendingphi) *pphi;
-
- if (!npendingphi) break;
- if (xbcap(pendingphis) <= blk->id) break;
-
- pphi = (void *)&pendingphis[blk->id];
- npendingphi -= pphi->n;
- for (int i = 0; i < pphi->n; ++i) {
- fillphi(defined, mkref(RTMP, pphi->p[i].phi), instrtab[pphi->p[i].phi].cls, pphi->p[i].var, blk);
- }
- vfree(pphi);
- } while ((blk = blk->lnext) != fn->entry);
-
- if (ccopt.dbg.l) {
- bfmt(ccopt.dbgout, "<< After liveness fixup >>\n");
- irdump(fn);
- }
- if (defined != definedbuf) free(defined);
-}
-
-static regset gpregset, fpregset;
-
-#define isfpr(reg) in_range((reg), mctarg->fpr0, mctarg->fpr0 + mctarg->nfpr - 1)
-#define isgpr(reg) in_range((reg), mctarg->gpr0, mctarg->gpr0 + mctarg->nfpr - 1)
-
-/* an allocated physical register or stack slot */
-enum { ADEAD, AREG, ASTACK };
-union alloc { struct { ushort t : 2, a : 14; }; ushort bits; };
-#define afree() ((union alloc) { .t=ADEAD })
-#define areg(r) ((union alloc) { .t=AREG, .a=(r) })
-#define astack(s) ((union alloc) { .t=ASTACK, .a=(s) })
-
-enum { MAXSPILL = 512 };
-
-/* half-closed instr range [from, to) */
-struct range { ushort from, to; };
-#define mkrange(f,t) ((struct range){(f), (t)})
-
-/* a temporary's lifetime interval */
-struct interval {
- struct interval *next; /* for linked list of active,inactive,handled sets in linear scan */
- union alloc alloc;
- schar rhint : 7; /* register hint */
- bool fpr : 1; /* needs float register? */
- uint cost; /* spilling cost estimate */
-
- /* sorted ranges array */
- ushort nrange;
- union {
- struct range _rinl[2];
- struct range *_rdyn;
- };
-};
-
-struct rega {
- struct function *fn;
- struct arena **arena;
-
- int intercount; /* number of actual intervals */
- int ninter; /* size of inter */
- struct interval *inter; /* map of tmp -> interval */
- struct fixinterval {
- struct fixinterval *next;
- regset rs;
- struct range range;
- } *fixed; /* linked list of fixed intervals, always sorted */
-
- struct bitset freestk[BSSIZE(MAXSPILL)]; /* free stack slots */
- int maxstk, /* highest stack slot used */
- stktop;
-};
-
-#define stkslotref(fn, off) \
- (mkaddr((struct addr){.base = mkref(RREG, mctarg->bpr), .disp = -(fn)->stksiz - 8 - (off)}))
-
-/* Parallel moves algorithm from QBE: https://c9x.me/git/qbe.git/tree/rega.c?id=e493a7f23352f51acc0a1e12284ab19d7894488a#n201 */
-
-enum { PMTOMOVE, PMMOVING, PMDONE };
-struct pmstate {
- struct function *fn;
- int npmove;
- struct pmove {
- uchar k; /* enum irclass */
- uchar stat; /* PMTOMOVE|MOVING|DONE */
- union alloc dst, src;
- } pmove[MAXREGS];
-};
-
-static void
-pmadd(struct pmstate *pms, enum irclass k, union alloc dst, union alloc src)
-{
- if (!memcmp(&dst, &src, sizeof dst)) return;
- assert(pms->npmove < MAXREGS);
- pms->pmove[pms->npmove++] = (struct pmove) { k, PMTOMOVE, dst, src };
-}
-
-#define mkmove(k, rd, rs) mkinstr(Omove, k, mkref(RREG, rd), mkref(RREG, rs))
-static void
-emitmove(struct function *fn, enum irclass k, union alloc dst, union alloc src, struct block *blk, int curi)
-{
- struct instr mv = {.keep = 1};
- int reg;
- if (dst.t == AREG && src.t == AREG) {
- insertinstr(blk, curi, mkmove(k, dst.a, src.a));
- return;
- }
- if (src.t == ASTACK) {
- switch (mv.cls = k) {
- default: assert(0);
- case KI32: mv.op = Oloads32; break;
- case KI64: mv.op = Oloadi64; break;
- case KPTR: mv.op = targ_64bit ? Oloadi64 : Oloads32; break;
- case KF32: mv.op = Oloadf32; break;
- case KF64: mv.op = Oloadf64; break;
- }
- if (dst.t == AREG)
- reg = dst.a;
- else
- reg = kisint(k) ? mctarg->gprscratch : mctarg->fprscratch;
- mv.reg = reg+1;
- mv.l = stkslotref(fn, src.a*8);
- insertinstr(blk, curi++, mv);
- } else reg = src.a;
- if (dst.t == ASTACK) {
- mv = mkinstr(cls2store[k], 0, stkslotref(fn, dst.a*8), mkref(RREG, reg));
- insertinstr(blk, curi, mv);
- }
-}
-
-static int
-pmrec(struct pmstate *pms, int i, struct block *blk, int curi, enum irclass *k)
-{
- struct pmove *pm = &pms->pmove[i];
- if (pm->dst.bits == pm->src.bits) {
- pm->stat = PMDONE;
- return -1;
- }
-
- /* widen when necessary */
- assert(kisint(pm->k) == kisint(*k));
- if (cls2siz[pm->k] > cls2siz[*k])
- *k = pm->k;
-
- int j, c;
- for (j = 0; j < pms->npmove; ++j) {
- if (pms->pmove[j].dst.bits == pm->src.bits)
- break;
- }
- if (j == pms->npmove) goto Done;
- switch (pms->pmove[j].stat) {
- default: assert(0);
- case PMMOVING:
- c = j;
- Swap:
- if (pm->src.t == AREG && pm->dst.t == AREG) {
- insertinstr(blk, curi,
- mkinstr(Oswap, *k, mkref(RREG, pm->dst.a), mkref(RREG, pm->src.a), .keep = 1));
- } else if (pm->src.t != pm->dst.t) {
- union alloc reg, stk, regtmp;
- if (pm->src.t == AREG)
- reg = pm->src, stk = pm->dst;
- else
- stk = pm->src, reg = pm->dst;
- assert(reg.t == AREG && stk.t == ASTACK);
- regtmp = areg(kisint(*k) ? mctarg->gprscratch : mctarg->fprscratch);
- emitmove(pms->fn, *k, regtmp, stk, blk, curi++);
- insertinstr(blk, curi++,
- mkinstr(Oswap, *k, mkref(RREG, reg.a), mkref(RREG, regtmp.a), .keep = 1));
- emitmove(pms->fn, *k, stk, regtmp, blk, curi++);
- } else {
- /* FIXME using scratch gpr and fpr for this is hackish */
- assert(pm->src.t == ASTACK && pm->dst.t == ASTACK);
- int r1 = mctarg->gprscratch, r2 = mctarg->fprscratch;
- enum irclass k1 = siz2intcls[cls2siz[*k]], k2 = KF32 + (cls2siz[*k] == 8);
- emitmove(pms->fn, k1, areg(r1), pm->src, blk, curi++);
- emitmove(pms->fn, k2, areg(r2), pm->dst, blk, curi++);
- emitmove(pms->fn, k1, pm->dst, areg(r1), blk, curi++);
- emitmove(pms->fn, k2, pm->src, areg(r2), blk, curi++);
- }
- break;
- case PMTOMOVE:
- pm->stat = PMMOVING;
- c = pmrec(pms, j, blk, curi, k);
- if (c == i) {
- c = -1;
- break;
- } else if (c != -1) {
- goto Swap;
- }
- /* fallthru */
- case PMDONE:
- Done:
- c = -1;
- emitmove(pms->fn, *k, pm->dst, pm->src, blk, curi);
- break;
- }
-
- pm->stat = PMDONE;
- return c;
-}
-
-static void
-emitpm(struct pmstate *pms, struct block *blk)
-{
- int curi = blk->ins.n;
- for (int i = 0; i < pms->npmove; ++i) {
- if (pms->pmove[i].stat == PMTOMOVE) {
- pmrec(pms, i, blk, curi, &(enum irclass) { pms->pmove[i].k });
- }
- }
-}
-
-/* remove phis by inserting parallel moves */
-static void
-lowerphis(struct rega *ra, struct block *blk, struct block *suc)
-{
- int predno;
- struct block *n = NULL;
-
- if (!blk->npred && blk != ra->fn->entry) {
- assert(!blk->phi.n);
- blk->ins.n = 0;
- return;
- }
- if (!blk->s2) n = blk;
-
- for (predno = 0; predno < suc->npred; ++predno)
- if (blkpred(suc, predno) == blk)
- break;
- assert(predno < suc->npred);
-
- struct pmstate pms;
- pms.fn = ra->fn;
- pms.npmove = 0;
- /* ensure phi args go to the same slot as phi with parallel copies */
- for (int i = 0; i < suc->phi.n; ++i) {
- struct instr *phi = &instrtab[suc->phi.p[i]];
- union ref *arg = &phitab.p[phi->l.i][predno];
- union alloc from, to;
-
- if (arg->t == RREG) continue;
- assert(arg->t == RTMP);
- DBG("resolve phi @%d, @%d, %%%d <- %%%d\n", blk->id, suc->id, phi - instrtab, arg->i);
- if (instrtab[arg->i].reg) {
- from = areg(instrtab[arg->i].reg - 1);
- DBG(" it had R%d\n", from.a);
- } else {
- from = ra->inter[arg->i].alloc;
- assert(from.t != ADEAD);
- DBG(" found %c%d\n", " RS"[from.t], from.a);
- if (from.t == AREG)
- instrtab[arg->i].reg = from.a+1;
- }
- if (phi->reg) {
- to = areg(phi->reg - 1);
- DBG(" phi had R%d\n", to.a);
- } else {
- to = ra->inter[phi - instrtab].alloc;
- if (to.t == ADEAD) {
- DBG(" skip dead phi\n");
- continue;
- }
- DBG(" found phi %c%d\n", " RS"[to.t], to.a);
- if (to.t == AREG)
- phi->reg = to.a+1;
- }
- DBG(" > phi move %c%d -> %c%d\n", " RS"[from.t], from.a, " RS"[to.t], to.a);
- if (!n) n = insertblk(ra->fn, blk, suc);
- pmadd(&pms, phi->cls, to, from);
- }
- if (n) emitpm(&pms, n);
-}
-
-/* generate copies for phi operands to transform into conventional-SSA */
-static void
-fixcssa(struct function *fn)
-{
- struct block *blk = fn->entry;
- do {
- if (!blk->phi.n) continue;
- for (int p = 0; p < blk->npred; ++p) {
- struct block *n, *pred = blkpred(blk, p);
- if (!pred->s2) {
- /* pred only has 1 successor (blk), so insert move directly in it */
- n = pred;
- } else {
- n = insertblk(fn, pred, blk);
- assert(n->jmp.t == Jb && n->s1 == blk);
- }
- for (int i = 0; i < blk->phi.n; ++i) {
- int phi = blk->phi.p[i];
- union ref *args = phitab.p[instrtab[phi].l.i];
- args[p] = insertinstr(n, n->ins.n, mkinstr(Ocopy, instrtab[phi].cls, args[p]));
- }
- }
- } while ((blk = blk->lnext) != fn->entry);
-
- fn->prop &= ~FNBLKID;
-}
-
-static inline bool
-rangeoverlap(struct range a, struct range b)
-{
- return a.from < b.to && b.from < a.to;
-}
-
-static void
-pushrange(struct interval *it, struct range r)
-{
- if (it->nrange < 2) it->_rinl[it->nrange++] = r;
- else if (it->nrange > 2) xbpush(&it->_rdyn, &it->nrange, r);
- else {
- struct range *d = NULL;
- xbgrow(&d, 4);
- memcpy(d, it->_rinl, 2*sizeof *d);
- d[it->nrange++] = r;
- it->_rdyn = d;
- }
-}
-#define itrange(it, i) ((it)->nrange <= 2 ? (it)->_rinl : (it)->_rdyn)[i]
-
-static inline int
-intervalbeg(struct interval *it)
-{
- assert(it->nrange);
- return itrange(it, 0).from;
-}
-
-static inline int
-intervalend(struct interval *it)
-{
- assert(it->nrange);
- return itrange(it, it->nrange-1).to;
-}
-
-static bool
-intersoverlap(struct interval *a, struct interval *b)
-{
- for (int i = 0, j = 0; i < a->nrange && j < b->nrange; ) {
- struct range r1 = itrange(a, i), r2 = itrange(b, j);
- if (rangeoverlap(r1, r2)) return 1;
- if (r1.to <= r2.from) ++i;
- else ++j;
- }
- return 0;
-}
-
-static inline void
-incrcost(struct interval *it, struct block *blk)
-{
- /* treat each loop as executing instr 8 times */
- it->cost += 1 << (blk->loop * 3);
-}
-
-static bool
-intervaldef(struct rega *ra, int t, struct block *blk, int pos, int reghint)
-{
- struct interval *it = &ra->inter[t];
- if (it->nrange) {
- ushort *beg = &itrange(it, 0).from;
- assert(*beg <= pos);
- incrcost(it, blk);
- *beg = pos;
- return 1;
- }
- return 0;
-}
-
-static void
-addrange(struct rega *ra, int t, struct range new, int reghint)
-{
- struct interval *it = &ra->inter[t];
- struct range *fst;
- int n;
-
- if (!it->nrange) {
- ++ra->intercount;
- it->rhint = reghint;
- it->fpr = kisflt(insrescls(instrtab[t]));
- pushrange(it, new);
- return;
- }
-
- fst = &itrange(it, 0);
- /* fully covered by first range? */
- if (fst->from <= new.from && fst->to >= new.to) return;
- /* overlaps with first range ? */
- if (fst->from <= new.to && new.to < fst->to) {
- fst->from = new.from;
- } else {
- /* put new range at the start */
- pushrange(it, new);
- memmove(&itrange(it, 1), &itrange(it, 0), sizeof(struct range) * (it->nrange - 1));
- itrange(it, 0) = new;
- }
-
- /* new range might cover existing ranges (loop header lives),
- * check and succesively merge */
- fst = &itrange(it, 0);
- n = 0;
- for (int i = 1; i < it->nrange; ++i) {
- struct range other = itrange(it, i);
- if (fst->to >= other.from) {
- fst->to = fst->to > other.to ? fst->to : other.to;
- ++n;
- } else break;
- }
-
- if (n > 0) {
- for (int i = 1; i + n < it->nrange; ++i)
- itrange(it, i) = itrange(it, i+n);
- if (it->nrange > 2 && it->nrange - n <= 2) {
- struct range *dyn = it->_rdyn;
- memcpy(it->_rinl, dyn, (it->nrange - n) * sizeof *dyn);
- xbfree(dyn);
- }
- it->nrange -= n;
- }
-}
-
-static void
-usereg(struct rega *ra, int reg, struct block *blk, int pos)
-{
- struct fixinterval *fxit;
- if (rstest(mctarg->rglob, reg)) return; /* regalloc never allocates globally live regs, so don't need intervals for those */
- for (struct fixinterval *prev = NULL, *fxit = ra->fixed; fxit; prev = fxit, fxit = fxit->next) {
- if (fxit->range.from > pos) break;
- if (fxit->rs == BIT(reg) && fxit->range.from <= pos && pos < fxit->range.to) {
- /* contained by existing interval */
- fxit->range.from = blk->inumstart;
- /* insert at head */
- //DBG(">>>extend REG %s range %d-%d\n", mctarg->rnames[reg], fxit->range.from, fxit->range.to);
- if (prev) {
- prev->next = fxit->next;
- fxit->next = ra->fixed;
- ra->fixed = fxit;
- }
- return;
- }
- }
- fxit = alloc(ra->arena, sizeof *fxit, 0);
- fxit->next = ra->fixed;
- fxit->range = (struct range) {blk->inumstart, pos};
- fxit->rs = BIT(reg);
- ra->fixed = fxit;
-}
-
-static bool
-defreg(struct rega *ra, int reg, int pos) {
- if (rstest(mctarg->rglob, reg)) return 1;
- for (struct fixinterval *prev = NULL, *fxit = ra->fixed; fxit; prev = fxit, fxit = fxit->next) {
- if (fxit->rs == BIT(reg)) {
- if (fxit->range.from <= pos) {
- fxit->range.from = pos;
- struct fixinterval **at = &ra->fixed;
- if ((*at)->range.from > pos) {
- /* keep sorted */
- //DBG("moved %s\n", mctarg->rnames[reg]);
- if (prev) prev->next = fxit->next;
- while ((*at)->range.from < pos) at = &(*at)->next;
- fxit->next = *at;
- *at = fxit;
- }
- //DBG(">>>def REG %s range %d-%d\n", mctarg->rnames[reg], fxit->range.from, fxit->range.to);
- return 1;
- }
- break;
- }
- }
- return 0;
-}
-
-/* lifetime interval construction */
-static void
-buildintervals(struct rega *ra)
-{
- extern int ninstr;
- struct block *blk, *last;
- struct bitset **livein = alloc(ra->arena, ra->fn->nblk * sizeof *livein, 0);
- size_t bssize = BSSIZE(ninstr);
- struct loops { /* list of loops */
- struct loops *next;
- struct block *hdr, *end;
- } *loops = NULL;
- for (int i = 0; i < ra->fn->nblk; ++i)
- livein[i] = allocz(ra->arena, bssize * sizeof *livein[i], 0);
- ra->inter = allocz(ra->arena, ninstr * sizeof *ra->inter, 0);
- ra->ninter = ninstr;
-
- uint n = numberinstrs(ra->fn);
- assert((ushort)n == n && "too many instrs for struct range");
- /* visit blocks in reverse, to build lifetime intervals */
- blk = last = ra->fn->entry->lprev;
- do {
- struct bitset *live = livein[blk->id];
- /* live = union of successor.liveIn for each successor of b */
- if (blk->s1) bsunion(live, livein[blk->s1->id], bssize);
- if (blk->s2) bsunion(live, livein[blk->s2->id], bssize);
-
- /* for each phi function phi of successors of b do
- * live.add(phi.inputOf(b))
- */
- for (struct block *suc = blk->s1; suc; suc = blk->s2) {
- int predno;
- for (predno = 0; blkpred(suc, predno) != blk; ++predno) ;
- for (int i = 0; i < suc->phi.n; ++i) {
- struct instr *phi = &instrtab[suc->phi.p[i]];
- union ref *arg = &phitab.p[phi->l.i][predno];
- assert(arg->t == RTMP);
- bsset(live, arg->i);
- incrcost(&ra->inter[arg->i], blk);
- }
- if (suc == blk->s2) break;
- }
-
- /* for each opd in live do
- * intervals[opd].addRange(b.from, b.to)
- */
- for (uint i = 0; bsiter(&i, live, bssize); ++i) {
- addrange(ra, i, mkrange(blk->inumstart, blk->inumstart + blk->ins.n + 2), -1);
- }
-
- /* for each operation op of b in reverse order do */
- struct instr *ins = NULL;
- union ref queue[8] = { blk->jmp.arg[0], blk->jmp.arg[1] };
- goto Branchopd;
- for (int curi, pos ; curi >= 0; --curi) {
- int out = blk->ins.p[curi], reghint;
- ins = &instrtab[out];
- pos = blk->inumstart + 1 + curi;
- /* for each output operand opd of op do
- * intervals[opd].setFrom(op.id)
- * live.remove(opd)
- */
- reghint = ins && ins->op == Ocopy && ins->l.t == RREG ? ins->l.i : -1;
- if (!intervaldef(ra, out, blk, pos, reghint)) {
- if (insrescls(*ins) && ins->op != Omove && !ins->keep && !(ins->op == Ocopy && ins->l.t == RREG)) {
- /* dead */
- *ins = mkinstr(Onop,0,);
- }
- }
- bsclr(live, out);
-
- /* gather fixed intervals */
- if (ins->op == Omove) {
- assert(ins->l.t == RREG);
- if (ins->l.bits == ins->r.bits) {/* special case `move Rx,Rx`: clobber reg, not a real use */
- usereg(ra, ins->l.i, blk, pos);
- assert(defreg(ra, ins->l.i, pos));
- } else if (!defreg(ra, ins->l.i, pos)) {
- if (ins->keep) { /* clobber here */
- usereg(ra, ins->l.i, blk, pos);
- assert(defreg(ra, ins->l.i, pos));
- } else {
- /* dead register use. for example if
- * move RCX, %1
- * %2 = shl 1, RCX
- * and %2 is dead, the move to RCX can be killed */
- *ins = mkinstr(Onop,0,);
- }
- } else {
- rsset(&ra->fn->regusage, ins->l.i);
- }
- if (ins->l.bits == ins->r.bits)
- continue;
- } else if (ins->op == Ocall) {
- struct call *call = &calltab.p[ins->r.i];
- regset rclob = (gpregset | fpregset) &~ (mctarg->rglob | mctarg->rcallee);
- ra->fn->isleaf = 0;
-
- for (int i = 0; i < 2; ++i) {
- if (call->abiret[i].ty.bits) {
- int reg = call->abiret[i].reg;
- rsclr(&rclob, reg);
- defreg(ra, reg, pos);
- }
- }
- if (rclob) {
- struct fixinterval *fxit = alloc(ra->arena, sizeof *fxit, 0);
- fxit->next = ra->fixed;
- fxit->range = mkrange(pos, pos);
- fxit->rs = rclob;
- ra->fixed = fxit;
- }
- for (int j = call->narg - 1; j >= 0; --j) {
- struct abiarg abi = call->abiarg[j];
- if (!abi.isstk) {
- usereg(ra, abi.reg, blk, pos);
- }
- }
- }
-
- /* for each input operand opd of op do
- * intervals[opd].addRange(b.from, op.id)
- * live.add(opd)
- */
- reghint = (ins && ins->op == Omove && ins->l.t == RREG) ? ins->l.i : -1;
- queue[0] = ins->r, queue[1] = ins->l;
- if (0) {
- Branchopd:
- reghint = -1;
- curi = blk->ins.n;
- pos = blk->inumstart + blk->ins.n + 1;
- }
- for (int nqueue = ins && ins->op == Omove ? 1 : 2; nqueue > 0;) {
- union ref r = queue[--nqueue];
-
- /* do not allocate a reg for a cmp op used as branch argument, since it's a pseudo op */
- if (curi == blk->ins.n && blk->jmp.t == Jb && r.t == RTMP && instrtab[r.i].keep)
- continue;
-
- if (r.t == RTMP) {
- assert(instrtab[r.i].op != Onop);
- incrcost(&ra->inter[r.i], blk);
- addrange(ra, r.i, mkrange(blk->inumstart, pos), reghint);
- bsset(live, r.i);
- } else if (r.t == RREG) {
- usereg(ra, r.i, blk, pos);
- } else if (r.t == RADDR) {
- reghint = -1;
- queue[nqueue++] = addrtab.p[r.i].base;
- queue[nqueue++] = addrtab.p[r.i].index;
- }
- }
- }
-
- /* for each phi function phi of b do
- * live.remove(phi.output)
- */
- for (int i = 0; i < blk->phi.n; ++i) {
- int phi = blk->phi.p[i];
- bsclr(live, phi);
- for (int i = 0; i < blk->npred; ++i)
- incrcost(&ra->inter[phi], blkpred(blk, i));
- }
-
- /* if b is loop header then
- * loopEnd = last block of the loop starting at b
- * for each opd in live do
- * intervals[opd].addRange(b.from, loopEnd.to)
- */
- struct block *loopend = NULL;
- for (int i = 0; i < blk->npred; ++i) {
- struct block *pred = blkpred(blk, i);
- if (pred->id > blk->id)
- loopend = loopend && loopend->id > pred->id ? loopend : pred;
- }
- if (loopend) {
- if (loops) DBG("@lp @%d\n", blk->id);
- for (struct loops *l = loops; l; l = l->next) {
- /* a nested loop might end later than loopend, which lengthens this outer loop. */
- /* XXX is this correct? more loop analysis might be required? */
- if (l->hdr->id > loopend->id) break;
- DBG(" check <@%d-@%d>\n", l->hdr->id, l->end->id);
- if (l->hdr->id > blk->id && l->hdr->id < loopend->id && l->end->id > loopend->id)
- loopend = l->end;
- }
- DBG("loop header @%d (to @%d)\n", blk->id, loopend->id);
- /* append to loop list */
- loops = alloccopy(ra->arena, &(struct loops){loops, blk, loopend}, sizeof *loops, 0);
- for (uint opd = 0; bsiter(&opd, live, bssize); ++opd) {
- // DBG(" i have live %%%d\n", opd);
- addrange(ra, opd, mkrange(blk->inumstart, loopend->inumstart + loopend->ins.n+1), -1);
- }
- }
- } while ((blk = blk->lprev) != last);
-
- if (ccopt.dbg.r) {
- for (int var = 0; var < ninstr; ++var) {
- struct interval *it = &ra->inter[var];
- if (!it->nrange) continue;
- DBG("lifetime of %%%d: ", var);
- for (int i = 0; i < it->nrange; ++i) {
- struct range r = itrange(it, i);
- DBG("[%d,%d)%s", r.from, r.to, i < it->nrange-1 ? ", " : "");
- }
- DBG(" spill cost: %d\n", it->cost);
- }
- for (struct fixinterval *fx = ra->fixed; fx; fx = fx->next) {
- DBG("fixed {");
- for (int r = 0, f=1; rsiter(&r, fx->rs); ++r, f=0)
- DBG(&" %s"[f], mctarg->rnames[r]);
- DBG("}: [%d,%d)\n", fx->range.from, fx->range.to);
- }
- }
-}
-
-static bool
-itcontainspos(struct interval *it, int pos)
-{
- for (int i = 0; i < it->nrange; ++i) {
- struct range r = itrange(it, i);
- if (r.from > pos) return 0;
- if (pos < r.to) return 1;
- }
- return 0;
-}
-
-/* quicksort */
-static void
-sortintervals(struct interval **xs, int lo, int hi)
-{
- assert(lo >= 0 && hi >= 0);
- while (lo < hi) {
- /* partition */
- int i = lo - 1, p = hi + 1,
- pivot = intervalbeg(xs[lo]);
- for (;;) {
- struct interval *tmp;
- do ++i; while (intervalbeg(xs[i]) < pivot);
- do --p; while (intervalbeg(xs[p]) > pivot);
- if (i >= p) break;
- /* swap */
- tmp = xs[i];
- xs[i] = xs[p];
- xs[p] = tmp;
- }
- /* recur */
- if (p + 1 >= hi) {
- hi = p;
- } else {
- if (lo < p)
- sortintervals(xs, lo, p);
- lo = p + 1;
- }
- }
-}
-
-static union alloc
-allocstk(struct rega *ra)
-{
- uint s = 0;
- if (bsiter(&s, ra->freestk, BSSIZE(MAXSPILL))) {
- bsclr(ra->freestk, s);
- if (ra->stktop < s) ra->stktop = s+1;
- } else {
- s = ra->stktop++;
- }
- if (ra->maxstk < s+1) ra->maxstk = s+1;
- return astack(s);
-}
-
-static void
-freestk(struct rega *ra, int slot)
-{
- DBG("FREE stk %d\n",slot);
- if (slot < MAXSPILL)
- bsset(ra->freestk, slot);
- else if (slot == ra->stktop - 1)
- --ra->stktop;
-}
-
-#define interval2temp(it) (int)(it - ra->inter)
-
-static void
-linearscan(struct rega *ra)
-{
- if (!ra->intercount) return;
-
- /* sort intervals */
- struct interval **unhandled = alloc(ra->arena, sizeof *unhandled * ra->intercount, 0);
- int nunhandled = 0;
- for (int i = 0; i < ra->ninter; ++i) {
- if (!ra->inter[i].nrange) continue;
- unhandled[nunhandled++] = &ra->inter[i];
- }
- assert(nunhandled == ra->intercount);
- sortintervals(unhandled, 0, nunhandled-1);
-
- regset freeregs = (gpregset | fpregset) &~ (mctarg->rglob | (1ull<<mctarg->gprscratch) | (1ull<<mctarg->fprscratch));
- memset(ra->freestk, 0xFF, sizeof ra->freestk);
-
- /* LINEAR SCAN */
- struct interval *actives[2] = {0}, /* gpr set and fpr set */
- *inactives[2] = {0},
- *spilled = NULL, **spilled_tail = &spilled;
- for (struct interval **pcurrent = unhandled; nunhandled > 0; ++pcurrent, --nunhandled) {
- struct interval *current = *pcurrent;
- int pos = intervalbeg(current);
-
- struct interval **active = &actives[current->fpr], **inactive = &inactives[current->fpr],
- **lnk, *it, *next;
- /* Expire old intervals */
- /* check for intervals in active that are handled or inactive */
- for (lnk = active, it = *lnk; (next = it?it->next:0), it; it = next) {
- assert(it->alloc.t == AREG);
- /* ends before position? */
- if (intervalend(it) <= pos) {
- /* move from active to handled */
- *lnk = next;
- //DBG(" unblock %s %X\n", mctarg->rnames[it->alloc.a], ra->free);
- rsset(&freeregs, it->alloc.a);
- } else if (!itcontainspos(it, pos)) { /* it does not cover position? */
- /* move from active to inactive */
- *lnk = next;
- it->next = *inactive;
- *inactive = it;
- rsset(&freeregs, it->alloc.a);
- DBG(" >> %%%zd unblock %s\n", interval2temp(it), mctarg->rnames[it->alloc.a]);
- } else lnk = &it->next;
- }
- /* check for intervals in inactive that are handled or active */
- for (lnk = inactive, it = *lnk; (next = it?it->next:0), it; it = next) {
- assert(it->alloc.t == AREG);
- /* ends before position? */
- if (intervalend(it) <= pos) {
- /* move from inactive to handled */
- *lnk = next;
- } else if (itcontainspos(it, pos)) { /* it covers position? */
- /* move from inactive to active */
- *lnk = next;
- it->next = *active;
- *active = it;
- assert(it->alloc.t == AREG);
- assert(rstest(freeregs, it->alloc.a));
- rsclr(&freeregs, it->alloc.a);
- DBG(" << %%%zd reblock %s\n", interval2temp(it), mctarg->rnames[it->alloc.a]);
- } else lnk = &it->next;
- }
-
- /** find a register for current **/
-
- int this = interval2temp(current);
- regset avail = freeregs & (current->fpr ? fpregset : gpregset),
- fixexcl = 0, excl = 0;
- struct instr *ins = &instrtab[this];
- int reg = 0;
-
- /* exclude regs from overlapping fixed intervals */
- int end = intervalend(current);
- for (struct fixinterval *last = NULL, *fxit = ra->fixed; fxit;
- last = fxit, fxit = fxit->next) {
- if (last) assert(last->range.from <= fxit->range.from && "unsorted fixintervals");
- if (fxit->range.to <= pos) {
- ra->fixed = fxit->next;
- continue;
- } else if (fxit->range.from >= end) {
- break;
- }
-
- for (int i = 0; i < current->nrange; ++i) {
- if (rangeoverlap(fxit->range, itrange(current, i))) {
- fixexcl |= fxit->rs;
- }
- }
- }
- /* exclude regs from overlapping inactive intervals */
- for (struct interval *it = *inactive; it; it = it->next) {
- if (it->alloc.t == AREG && intersoverlap(it, current)) {
- rsset(&excl, it->alloc.a);
- }
- }
- /* for 2-address instrs, exclude reg from 2nd arg (unless arg#1 == arg#2) */
- if (ins->inplace && opnarg[ins->op] == 2) {
- int xreg;
- if (ins->r.t == RREG) rsset(&excl, ins->r.i);
- else if (ins->r.t == RTMP && (xreg = instrtab[ins->r.i].reg)) {
- if (ins->r.bits != ins->l.bits)
- rsset(&fixexcl, xreg-1);
- }
- }
- excl |= fixexcl;
- avail &= ~excl;
-
- if (!avail) { /* no regs left, must spill */
- struct interval **ptospill = NULL, *tospill = current;
- /* heuristic: look for longest-lived active interval with lower spill cost */
- int curend = intervalend(current);
- for (lnk = active, it = *lnk; (next = it ? it->next : 0), it; it = next) {
- int end = intervalend(it);
- if (it->cost < tospill->cost && end > curend && !rstest(fixexcl, it->alloc.a)) {
- ptospill = lnk;
- tospill = it;
- reg = tospill->alloc.a;
- }
- lnk = &it->next;
- }
-
- /* insert in spilled, keep sorted */
- if (ptospill) {
- *ptospill = tospill->next; /* remove from active */
- int from = intervalbeg(tospill);
- lnk = &spilled;
- /* XXX potentially slow linear search */
- while (*lnk && intervalbeg(*lnk) < from)
- lnk = &(*lnk)->next;
- tospill->next = *lnk;
- *lnk = tospill;
- } else { /* tospill == current, so we can just append and keep it sorted */
- *spilled_tail = tospill;
- tospill->next = NULL;
- }
- if (!tospill->next) /* update spilled list tail */
- spilled_tail = &tospill->next;
-
- assert(spilled != NULL);
- if (tospill == current) {
- DBG("spilled %%%d\n", this);
- continue;
- } else {
- instrtab[interval2temp(tospill)].reg = 0;
- DBG("%%%d takes %s from %%%d (spilled)\n", this, mctarg->rnames[reg],
- interval2temp(tospill));
- goto GotReg;
- }
- }
-
- /* have free regs, try to use hint */
- if (current->rhint >= 0)
- DBG("have hint %s for %%%zd\n",
- mctarg->rnames[current->rhint], interval2temp(current));
- if (current->rhint >= 0 && rstest(avail, current->rhint)) {
- DBG(" (used hint)\n");
- reg = current->rhint;
- goto GotReg;
- } else {
- /* for two-address instructions, try to use the reg of left arg */
- if (ins->op != Ophi && (opnarg[ins->op] == 1 || (opnarg[ins->op] == 2 && ins->inplace))) {
- DBG(" %%%d try %d,%d\n", this, ins->l.t,ins->l.i);
- if (ins->l.t == RREG && rstest(avail, reg = ins->l.i))
- goto GotReg;
- if (ins->l.t == RTMP)
- if ((reg = instrtab[ins->l.i].reg-1) >= 0)
- if (rstest(avail, reg))
- goto GotReg;
- /* for phi, try to use reg of any arg */
- } else if (ins->op == Ophi) {
- union ref *arg = phitab.p[ins->l.i];
- for (int i = 0; i < xbcap(arg); ++i) {
- if (arg->t == RREG && rstest(avail, reg = arg->i)) goto GotReg;
- if (arg->t == RTMP)
- if ((reg = instrtab[arg->i].reg-1) >= 0)
- if (rstest(avail, reg))
- goto GotReg;
- }
- }
-
- /* no hints to use */
- if (avail &~ mctarg->rcallee) /* prefer caller-saved regs */
- avail &=~ mctarg->rcallee;
- /* and pick first available reg */
- reg = lowestsetbit(avail);
- }
- GotReg:
- current->alloc = areg(reg);
- ins->reg = reg + 1;
- DBG("%%%d got %s\n", this, mctarg->rnames[reg]);
- rsclr(&freeregs, reg);
- rsset(&ra->fn->regusage, reg);
-
- /* add current to active */
- current->next = *active;
- *active = current;
- }
-
- if (ccopt.dbg.r) {
- DBG("regusage: ");
- for (int r = 0; r < MAXREGS; ++r) {
- if (rstest(ra->fn->regusage, r)) DBG(" %s", mctarg->rnames[r]);
- }
- DBG("\n");
- }
- /* allocate stack slots for spilled intervals
- * this is like another (simplified) linear scan pass */
- struct interval *active = NULL;
- int prevpos = -1;
- if (spilled) DBG("spilled:\n");
- for (struct interval *current = spilled, *next; current; current = next) {
- int pos = intervalbeg(current);
- DBG(" %%%zd: [%d,%d)\n", interval2temp(current), pos, intervalend(current));
- assert(pos >= prevpos && "unsorted spilled?");
- prevpos = pos;
- /* Expire old intervals */
- struct interval **lnk, *it, *lnext;
- for (lnk = &active, it = *lnk; (lnext = it ? it->next : 0), it; it = lnext) {
- /* ends before position? */
- if (intervalend(it) <= pos) {
- /* move from active to handled */
- *lnk = lnext;
- freestk(ra, it->alloc.a);
- } else lnk = &it->next;
- }
- /* allocate a stack slot for current and move to active */
- current->alloc = allocstk(ra);
- DBG(" got stk%d\n", current->alloc.a);
- next = current->next;
- current->next = active;
- active = current;
- }
-}
-
-static bool
-isstoreimm(union ref r)
-{
- if (r.t == RTMP) return 1; /* register OK */
- if (isintcon(r)) switch (target.arch) {
- case ISxxx: assert(0);
- /* TODO don't hard code this architecture dependent dispatch */
- case ISx86_64: return concls(r) == KI32; /* x86: MOV [addr], imm32 */
- case ISaarch64: return r.i == 0; /* arm doesn't have STR <imm>, but has zero register */
- }
- return 0;
-}
-
-/* replace temps with physical regs, add loads & stores for spilled temps */
-static bool
-devirt(struct rega *ra, struct block *blk)
-{
- bool allnops = 1;
- struct function *fn = ra->fn;
- union alloc spillsave[4] = {0};
- memset(ra->freestk, 0, BSSIZE(MAXSPILL) * sizeof *ra->freestk);
-
- for (int curi = 0; curi < blk->ins.n; ++curi) {
- int temp = blk->ins.p[curi];
- struct instr *ins = &instrtab[temp];
- struct interval *it;
- union alloc *alloc;
- struct addr newaddr;
- union ref *argref[4];
- int curi0;
- int naddr = 0;
- int nargref = 0;
- int nspill = 0;
-
- /** devirtualize operands **/
- for (int i = 0; i < 2; ++i) {
- union ref *r = &i[&ins->l];
- if (r->t == RADDR) {
- struct addr *a = &addrtab.p[r->i];
- ++naddr;
- newaddr = *a;
- argref[nargref++] = &newaddr.base;
- argref[nargref++] = &newaddr.index;
- } else {
- argref[nargref++] = r;
- }
- }
- for (int i = 0; i < nargref; ++i) {
- union ref *r = argref[i];
- int tr;
- if (r->t == RTMP && (it = &ra->inter[r->i])->nrange > 0) {
- alloc = &it->alloc;
- if (alloc->t == ASTACK && ins->op == Omove && kisint(ins->cls) == kisint(instrtab[r->i].cls)) {
- /* move [reg], [stk] -> [reg] = load [stk] */
- assert(r == &ins->r && ins->l.t == RREG);
- ins->reg = ins->l.i+1;
- ins->op = cls2load[instrtab[r->i].cls];
- ins->l = stkslotref(fn, alloc->a*8);
- ins->r = NOREF;
- } else if (alloc->t == ASTACK && ins->op == Ocopy && r == &ins->l && ins->reg && kisint(ins->cls) == kisint(instrtab[r->i].cls)) {
- /* [reg] = copy [stk] -> [reg] = load [stk] */
- ins->op = cls2load[instrtab[r->i].cls];
- ins->l = stkslotref(fn, alloc->a*8);
- } else if (alloc->t == ASTACK) {
- /* ref was spilled, gen load to scratch register and use it */
- struct instr ld = {.cls = insrescls(instrtab[r->i])};
- int reg = kisint(ld.cls) ? mctarg->gprscratch : mctarg->fprscratch;
- bool dosave = 0;
- /* pick scratch register, or any register that doesn't conflict with this instr's srcs/dst */
- if (nspill > 0) {
- regset avail = (kisflt(ld.cls) ? fpregset : gpregset) &~ mctarg->rglob;
- if (ins->reg) rsclr(&avail, ins->reg-1);
- for (int j = 0; j < nargref; ++j) {
- struct interval *it;
- if (argref[j]->t == RREG) rsclr(&avail, argref[j]->i);
- else if (argref[j]->t == RTMP) {
- it = &ra->inter[argref[j]->i];
- if (it->alloc.t == AREG) rsclr(&avail, it->alloc.a);
- }
- }
- assert(avail != 0);
- if (avail &~ (fn->regusage | mctarg->rcallee)) avail &= ~(fn->regusage | mctarg->rcallee);
- reg = lowestsetbit(avail);
- /* if not the designated scratch register, we need to save+restore */
- if (rstest(fn->regusage, reg) || rstest(mctarg->rcallee, reg)) {
- dosave = 1;
- if (!spillsave[nspill-1].t) spillsave[nspill-1] = allocstk(ra);
- emitmove(fn, isgpr(reg) ? KPTR : KF64, spillsave[nspill-1], areg(reg), blk, curi++);
- }
- }
- ld.reg = reg+1;
- ld.op = cls2load[ld.cls];
- ld.l = stkslotref(fn, alloc->a*8);
- insertinstr(blk, curi++, ld);
- *r = mkref(RREG, reg);
- if (nspill > 0 && dosave) {
- emitmove(fn, isgpr(reg) ? KPTR : KF64, areg(reg), spillsave[nspill-1], blk, curi+1);
- }
- ++nspill;
- } else if ((tr = instrtab[r->i].reg)) {
- assert(alloc && alloc->t == AREG && alloc->a == tr-1);
- *r = mkref(RREG, tr-1);
- }
- }
- }
- if (nspill > 1) assert(ins->op != Ocall);
- if (naddr) {
- union ref *r = ins->l.t == RADDR ? &ins->l : &ins->r;
- *r = mkaddr(newaddr);
- }
-
- /* devirtualize destination */
- curi0 = curi;
- alloc = temp < ra->ninter && (it = &ra->inter[temp]) && it->nrange ? &it->alloc : NULL;
- if (alloc && alloc->t == ASTACK) {
- enum irclass cls = insrescls(*ins);
- int store = cls2store[cls];
- /* t was spilled, gen store */
- if (ins->op == Ocopy && (ins->l.t == RREG || isstoreimm(ins->l))) {
- ins->op = store;
- ins->r = ins->l;
- ins->l = stkslotref(fn, alloc->a*8);
- } else {
- bool dosave = 0;
- int reg = kisint(insrescls(*ins)) ? mctarg->gprscratch : mctarg->fprscratch;
- if (nspill > 0) {
- regset avail = (kisflt(cls) ? fpregset : gpregset) &~ mctarg->rglob;
- for (int j = 0; j < nargref; ++j) {
- if (argref[j]->t == RREG) rsclr(&avail, argref[j]->i);
- }
- assert(avail != 0);
- if (avail &~ (fn->regusage | mctarg->rcallee)) avail &= ~(fn->regusage | mctarg->rcallee);
- /* if not the designated scratch register, we need to save+restore */
- reg = lowestsetbit(avail);
- if (rstest(fn->regusage, reg) || rstest(mctarg->rcallee, reg)) {
- dosave = 1;
- if (!spillsave[nspill-1].t) spillsave[nspill-1] = allocstk(ra);
- emitmove(fn, isgpr(reg) ? KPTR : KF64, spillsave[nspill-1], areg(reg), blk, curi++);
- curi0 = curi;
- }
- }
- ins->reg = reg+1;
- insertinstr(blk, ++curi,
- mkinstr(store, 0, stkslotref(fn, alloc->a*8), mkref(RREG, reg)));
- if (nspill > 0 && dosave) {
- emitmove(fn, isgpr(reg) ? KPTR : KF64, areg(reg),
- spillsave[nspill-1], blk, ++curi);
- }
- }
- }
- if (!ins->reg && insrescls(*ins) && ins->op != Omove && !ins->keep && !oisstore(ins->op)) {
- /* dead */
- Nop:
- ins->op = Onop;
- } else if (ins->op == Omove && ins->r.t == RREG && ins->l.i == ins->r.i) {
- /* move r1,r2 / r1=r2 */
- goto Nop;
- } else if (ins->op == Ocopy && ins->l.t == RREG && ins->reg-1 == ins->l.i) {
- /* r1 = copy r2 / r1=r2 */
- goto Nop;
- } else if (ins->op != Onop) {
- allnops = 0;
- }
- if (ins->inplace && ins->l.t == RREG && ins->reg && ins->reg-1 != ins->l.i) {
- /* fixup in-place (two-address) instructions */
- allnops = 0;
- insertinstr(blk, curi0, mkmove(ins->cls, ins->reg-1, ins->l.i));
- ++curi;
- ins->l.i = ins->reg-1;
- }
- if (!ins->reg && in_range(ins->op, Oloads8, Oloadf64)) {
- assert(ins->keep);
- ins->reg = kisint(ins->cls) ? mctarg->gprscratch+1 : mctarg->fprscratch+1;
- }
- }
-
- if (allnops) vfree(&blk->ins);
- return allnops;
-}
-
-static void
-fini(struct rega *ra)
-{
- int id = 0;
- struct function *fn = ra->fn;
- struct block *blk = fn->entry;
-
- do {
- blk->id = id++;
- bool allnops = devirt(ra, blk);
- if (allnops && !blk->s2 && blk->npred > 0) { /* remove no-op blocks */
- bool delet = 1;
- for (int i = 0; i < blk->npred; ++i) {
- struct block *p = blkpred(blk, i);
- if (p == blk || (p->s2 && !blk->s1))
- delet = 0;
- }
- for (int i = 0; i < blk->npred; ++i) {
- struct block *p = blkpred(blk, i);
- if (!p->s2 && !blk->s1) {
- /* simplify:
- *
- * @p:
- * ...
- * b @blk
- * @blk:
- * NOP
- * ret/trap
- */
- assert(p->s1 == blk);
- p->jmp.t = blk->jmp.t;
- p->s1 = NULL;
- } else if (blk->s1 && blk->s1 != blk) {
- /* simplify:
- *
- * @p:
- * ...
- * b %x, @blk, @other
- * @blk:
- * NOP
- * b @next
- */
- struct block *next = blk->s1;
- if (p->s1 == blk) p->s1 = next;
- else if (p->s2 == blk) p->s2 = next;
- else continue;
- for (int i = 0; i < next->npred; ++i) {
- if (blkpred(next, i) == blk) {
- blkpred(next, i) = p;
- goto NextPred;
- }
- }
- addpred(next, p);
- }
- NextPred:;
- }
- if (delet) {
- freeblk(fn, blk);
- --id;
- }
- } else if (allnops) {
- vfree(&blk->ins);
- }
- } while ((blk = blk->lnext) != fn->entry);
-}
-
-void
-regalloc(struct function *fn)
-{
- struct rega ra = {fn, .arena = fn->passarena};
- struct block *blk, *last;
-
- /* setup */
- if (!fpregset || !gpregset) {
- for (int r = 0; r < MAXREGS; ++r) {
- if (isfpr(r))
- rsset(&fpregset, r);
- else if (isgpr(r))
- rsset(&gpregset, r);
- }
- }
- fn->regusage = 0;
- fn->stksiz = alignup(fn->stksiz, 8);
- fn->isleaf = 1;
-
- /* put into reverse post order */
- sortrpo(fn);
-
- /* fix liveness ranges */
- fixlive(fn);
-
- /* transform into CSSA */
- fixcssa(fn);
-
- fillblkids(fn);
- fillloop(fn);
-
- if (ccopt.dbg.r) {
- bfmt(ccopt.dbgout, "<< Before linear scan >>\n");
- irdump(fn);
- }
-
- /* linear scan: build lifetime intervals */
- buildintervals(&ra);
-
- /* linear scan: assign physical registers and stack slots */
- linearscan(&ra);
-
- /* get out of SSA */
- blk = last = fn->entry->lprev;
- do {
- if (blk->id < 0) continue;
- for (int i = 0; i < blk->npred; ++i) {
- lowerphis(&ra, blkpred(blk, i), blk);
- }
- vfree(&blk->phi);
- } while ((blk = blk->lprev) != last);
-
- /* devirtualize & final cleanup */
- fini(&ra);
- fn->stksiz += ra.maxstk*8;
- if (fn->stksiz > 1<<24) error(NULL, "'%s' stack frame too big", fn->name);
-
- for (struct interval *it = ra.inter; ra.intercount > 0; ++it) {
- if (it->nrange > 2) xbfree(it->_rdyn);
- if (it->nrange > 0) --ra.intercount;
- }
-
- if (ccopt.dbg.r) {
- bfmt(ccopt.dbgout, "<< After regalloc >>\n");
- irdump(fn);
- }
-}
-
-/* vim:set ts=3 sw=3 expandtab: */
diff --git a/ir/simpl.c b/ir/simpl.c
deleted file mode 100644
index a01879a..0000000
--- a/ir/simpl.c
+++ /dev/null
@@ -1,308 +0,0 @@
-#include "ir.h"
-
-static int
-mulk(struct instr *ins, struct block *blk, int *curi)
-{
- vlong iv = intconval(ins->r);
- enum irclass cls = ins->cls;
- assert((uvlong)iv > 1 && "trivial mul not handled by irbinop() ?");
- bool neg = iv < 0;
- if (neg) iv = -iv;
- /* This can be generalized to any sequence of shifts and
- * adds/subtracts, but whether that's worth it depends on the number of them
- * and the microarchitecture.. clang seems to stop after two shifts. Should
- * we compute approximate cost of instrs to determine? For now just handle
- * the po2 (+/- 1) case */
- if (ispo2(iv)) {
- /* x * 2^y ==> x << y */
- ins->op = Oshl;
- ins->r = mkref(RICON, ilog2(iv));
- } else if (ispo2(iv-1)) {
- /* x * 5 ==> (x << 2) + x */
- ins->op = Oadd;
- ins->r = ins->l;
- ins->l = insertinstr(blk, (*curi)++, mkinstr(Oshl, cls, ins->l, mkref(RICON, ilog2(iv-1))));
- } else if (ispo2(iv+1)) {
- /* x * 7 ==> (x << 3) - x */
- ins->op = Osub;
- ins->r = ins->l;
- ins->l = insertinstr(blk, (*curi)++, mkinstr(Oshl, cls, ins->l, mkref(RICON, ilog2(iv+1))));
- } else return 0;
- if (neg) {
- ins->l = insertinstr(blk, (*curi)++, *ins);
- ins->op = Oneg;
- ins->r = NOREF;
- }
- return 1;
-}
-
-static int
-divmodk(struct instr *ins, struct block *blk, int *curi)
-{
- enum op op = ins->op;
- enum irclass cls = ins->cls;
- vlong iv = intconval(ins->r);
- uint nbit = 8 * cls2siz[cls];
- bool neg = (op == Odiv || op == Orem) && iv < 0;
- if (ispo2(iv) || (neg && ispo2(-iv))) { /* simple po2 cases */
- union ref temp;
- uint s = ilog2(neg ? -iv : iv);
- switch (op) {
- default: assert(0);
- case Oudiv: /* x / 2^s ==> x >> s */
- ins->op = Oslr, ins->r = mkref(RICON, s);
- return 1;
- case Ourem: /* x % 2^s ==> x & 2^s-1 */
- ins->op = Oand, ins->r = mkintcon(cls, iv - 1);
- return 1;
- case Odiv: case Orem:
- /* have to adjust to round negatives toward zero */
- /* x' = (((x < 0 ? -1 : 0) >>> (Nbit - s)) + x) */
- temp = insertinstr(blk, (*curi)++, mkinstr(Osar, cls, ins->l, mkref(RICON, nbit - 1)));
- temp = insertinstr(blk, (*curi)++, mkinstr(Oslr, cls, temp, mkref(RICON, nbit - s)));
- temp = insertinstr(blk, (*curi)++, mkinstr(Oadd, cls, ins->l, temp));
- if (op == Odiv) {
- /* (-) (x' >> s) */
- struct instr sar = mkinstr(Osar, cls, temp, mkref(RICON, s));
- if (!neg) *ins = sar;
- else {
- temp = insertinstr(blk, (*curi)++, sar);
- ins->op = Oneg, ins->l = temp, ins->r = NOREF;
- }
- } else {
- /* x - (x' & -(2^s)) */
- temp = insertinstr(blk, (*curi)++, mkinstr(Oand, cls, temp, mkintcon(cls, neg ? iv : -iv)));
- ins->op = Osub, ins->r = temp;
- }
- break;
- return 0;
- }
- }
- return 0;
-}
-
-static int
-doins(struct instr *ins, struct block *blk, int *curi)
-{
- int narg = opnarg[ins->op];
- if (oisarith(ins->op)) {
- union ref r = narg == 1 ? irunop(NULL, ins->op, ins->cls, ins->l)
- : irbinop(NULL, ins->op, ins->cls, ins->l, ins->r);
- if (r.bits) {
- *ins = mkinstr(Onop,0,);
- replcuses(mkref(RTMP, ins - instrtab), r);
- return 1;
- }
- }
- enum irclass k = ins->cls;
- switch (ins->op) {
- case Ocopy:
- if ((ins->l.t == RTMP && k == instrtab[ins->l.i].cls)
- || (isnumcon(ins->l) && k == concls(ins->l))
- || (kisint(k) && ins->l.t == RICON)) {
- union ref it = ins->l;
- *ins = mkinstr(Onop,0,);
- replcuses(mkref(RTMP, ins - instrtab), it);
- return 1;
- }
- break;
- case Omul:
- if (kisflt(k)) break;
- if (isnumcon(ins->l)) rswap(ins->l, ins->r); /* put const in rhs */
- if (isintcon(ins->r)) return mulk(ins, blk, curi);
- break;
- case Odiv: case Oudiv: case Orem: case Ourem:
- if (kisflt(k)) break;
- if (isintcon(ins->r)) return divmodk(ins, blk, curi);
- break;
- case Oequ: case Oneq:
- if (ins->l.t == RTMP && isintcon(ins->r)) {
- /* optimize `x <op> C <cmp> Q` */
- /* could apply with add/sub to lth/lte/gth/gte iff no signed wraparound, which isn't assumed */
- struct instr *lhs = &instrtab[ins->l.i];
- enum op o = lhs->op;
- if (ins->cls == lhs->cls && (o == Oadd || o == Osub || o == Oxor) && isintcon(lhs->r)) {
- uvlong c = intconval(ins->r), q = intconval(lhs->r);
- switch (o) { default: assert(0);
- case Oadd: c -= q; break; /* x + 3 == C ==> x == C - 3 */
- case Osub: c += q; break; /* x - 3 == C ==> x == C + 3 */
- case Oxor: c ^= q; break; /* x ^ 3 == C ==> x == C ^ 3 */
- }
- ins->l = lhs->l, ins->r = mkintcon(ins->cls, c);
- deluse(blk, ins - instrtab, mkref(RTMP, lhs - instrtab));
- if (!instruse[lhs - instrtab]) *lhs = mkinstr(Onop,0,);
- return 1;
- }
- }
- }
- return 0;
-}
-
-static void
-jmpfind(struct block **final, struct block **pblk)
-{
- struct block **p2 = &final[(*pblk)->id];
- if (*p2 && !(*p2)->phi.n) {
- jmpfind(final, p2);
- *pblk = *p2;
- }
-}
-
-static void
-fillpredsrec(struct block *blk)
-{
- while (blk && !wasvisited(blk)) {
- markvisited(blk);
- if (!blk->s1) return;
- if (!blk->s1->phi.n) addpred(blk->s1, blk);
- if (!blk->s2) {
- blk = blk->s1;
- continue;
- }
- if (!blk->s2->phi.n) addpred(blk->s2, blk);
- fillpredsrec(blk->s1);
- blk = blk->s2;
- }
-}
-
-static void
-fillpreds(struct function *fn)
-{
- struct block *blk = fn->entry, *next;
- do {
- if (blk->phi.n) continue;
- if (blk->npred > 1)
- xbfree(blk->_pred);
- blk->npred = 0;
- blk->_pred = NULL;
- } while ((blk = blk->lnext) != fn->entry);
- startbbvisit();
- fillpredsrec(fn->entry);
- blk = fn->entry->lnext;
- do { /* remove dead blocks */
- next = blk->lnext;
- if (!blk->npred) freeblk(fn, blk);
- } while ((blk = next) != fn->entry);
-}
-
-static void
-mergeblks(struct function *fn, struct block *p, struct block *s)
-{
- assert(s->npred == 1 && !s->phi.n);
- vpushn(&p->ins, s->ins.p, s->ins.n);
- p->jmp = p->s1->jmp;
- for (int i = 0; i < 2; ++i) {
- struct block *ss = (&s->s1)[i];
- if (ss) for (int j = 0; j < ss->npred; ++j) {
- if (blkpred(ss, j) == s) {
- blkpred(ss, j) = p;
- break;
- }
- }
- }
- /* breaks use for temps used in s */
- if (s->ins.n || s->jmp.arg[0].t == RTMP || s->jmp.arg[1].t == RTMP)
- fn->prop &= ~FNUSE;
- p->s1 = s->s1;
- p->s2 = s->s2;
- freeblk(fn, s);
-}
-
-void
-simpl(struct function *fn)
-{
- FREQUIRE(FNUSE);
- int inschange = 0,
- blkchange = 0;
- struct block **jmpfinal = allocz(fn->passarena, fn->nblk * sizeof *jmpfinal, 0);
- struct block *blk = fn->entry;
-
- do {
- /* merge blocks:
- * @blk:
- * ... (1)
- * b @s
- * @s:
- * ... (2)
- * b {...}
- *=>
- * @blk:
- * ... (1)
- * ... (2)
- * b {...}
- * */
- if (blk != fn->entry) while (blk->s1 && !blk->s2 && blk->s1->npred == 1 && !blk->phi.n) {
- mergeblks(fn, blk, blk->s1);
- }
- } while ((blk = blk->lnext) != fn->entry);
-
- if (!(fn->prop & FNUSE)) filluses(fn);
-
- do {
- for (int i = 0; i < blk->phi.n; ++i) {
- int phi = blk->phi.p[i];
- /* delete trivial phis */
- union ref *args = phitab.p[instrtab[phi].l.i],
- same = *args;
- if (same.t == RTMP && instrtab[same.i].op == Ophi) goto Next;
- if (blk->npred > 1) for (int j = 1; j < blk->npred; ++j) {
- if (args[j].bits != same.bits) goto Next;
- }
- if (!(fn->prop & FNUSE)) filluses(fn);
- replcuses(mkref(RTMP, phi), same);
- delphi(blk, i);
- Next:;
- }
-
- int curi = 0;
- DoIns:
- for (; curi < blk->ins.n; ++curi) {
- struct instr *ins = &instrtab[blk->ins.p[curi]];
- if (ins->op != Onop) {
- if (!(fn->prop & FNUSE)) filluses(fn);
- inschange += doins(ins, blk, &curi);
- }
- }
-
- if (blk->s2 && isintcon(blk->jmp.arg[0])) {
- /* simplify known conditional branch */
- struct block *s = intconval(blk->jmp.arg[0]) ? blk->s1 : blk->s2;
- delpred(s == blk->s1 ? blk->s2 : blk->s1, blk);
- blk->s1 = s, blk->s2 = NULL;
- blk->jmp.arg[0] = NOREF;
- if (blk->s1 && !blk->s2 && blk->s1->npred == 1 && blk->s1->phi.n == 0) {
- mergeblks(fn, blk, blk->s1);
- goto DoIns;
- }
- }
-
- if (blk != fn->entry && blk->npred == 0) {
- freeblk(fn, blk);
- } else if (!blk->phi.n && !blk->ins.n) { /* thread jumps.. */
- if (blk->jmp.t == Jb && !blk->s2) {
- jmpfind(jmpfinal, &blk->s1);
- if (blk->s1 != blk) {
- ++blkchange;
- jmpfinal[blk->id] = blk->s1;
- }
- }
- }
- } while ((blk = blk->lnext) != fn->entry);
-
- if (blkchange) {
- do {
- if (blk->s1) jmpfind(jmpfinal, &blk->s1);
- if (blk->s2) jmpfind(jmpfinal, &blk->s2);
- if (blk->s1 && blk->s1 == blk->s2) {
- memset(blk->jmp.arg, 0, sizeof blk->jmp.arg);
- blk->s2 = NULL;
- }
- } while ((blk = blk->lnext) != fn->entry);
- fillpreds(fn);
- sortrpo(fn);
- }
- if (!(fn->prop & FNUSE)) filluses(fn);
- fn->prop &= ~FNDOM;
-}
-
-/* vim:set ts=3 sw=3 expandtab: */
diff --git a/ir/ssa.c b/ir/ssa.c
deleted file mode 100644
index 6598fba..0000000
--- a/ir/ssa.c
+++ /dev/null
@@ -1,46 +0,0 @@
-#include "ir.h"
-
-void
-copyopt(struct function *fn)
-{
- struct block *blk = fn->entry;
-
- FREQUIRE(FNUSE);
- do {
- for (int i = 0; i < blk->phi.n; ++i) {
- /* simplify same-arg phi */
- int phi = blk->phi.p[i];
- union ref *arg = phitab.p[instrtab[phi].l.i];
- for (int j = 1; j < blk->npred; ++j) {
- if (arg[j].bits != arg->bits) goto Next;
- }
- /* being conservative here because phis could have circular dependencies? */
- if (arg->t != RTMP || instrtab[arg->i].op != Ophi) {
- replcuses(mkref(RTMP, phi), *arg);
- delphi(blk, i--);
- }
- Next:;
- }
- for (int i = 0; i < blk->ins.n; ++i) {
- union ref var = mkref(RTMP, blk->ins.p[i]);
- struct instr *ins = &instrtab[var.i];
- enum irclass k;
-
- if (ins->op == Ocopy) {
- union ref arg = ins->l;
- if (arg.t == RTMP) k = insrescls(instrtab[arg.i]);
- else if (arg.t == RICON) k = cls2siz[ins->cls] == 4 ? KI32 : KI64;
- else if (arg.t == RXCON) k = isnumcon(arg) ? concls(arg) : KPTR;
- else continue;
- if (ins->cls != k) continue;
-
- replcuses(var, arg);
- *ins = mkinstr(Onop,0,);
- deluses(var.i);
- }
- }
- delnops(blk);
- } while ((blk = blk->lnext) != fn->entry);
-}
-
-/* vim:set ts=3 sw=3 expandtab: */
diff --git a/ir/stack.c b/ir/stack.c
deleted file mode 100644
index 40a7b1d..0000000
--- a/ir/stack.c
+++ /dev/null
@@ -1,33 +0,0 @@
-#include "ir.h"
-
-void
-lowerstack(struct function *fn)
-{
- fn->stksiz = 0;
- FREQUIRE(FNUSE);
-
- struct block *blk = fn->entry;
- do {
- for (int i = 0; i < blk->ins.n; ++i) {
- int t = blk->ins.p[i];
- struct instr *ins = &instrtab[t];
- if (oisalloca(ins->op)) {
- uint alignlog2 = ins->op - Oalloca1;
- assert(ins->l.i > 0);
- uint siz = ins->l.i << alignlog2;
- fn->stksiz += siz;
- fn->stksiz = alignup(fn->stksiz, 1 << alignlog2);
- if (fn->stksiz > (1<<20)-1) error(NULL, "'%s' stack frame too big", fn->name);
- *ins = mkinstr(Onop,0,);
- replcuses(mkref(RTMP, t), mkref(RSTACK, fn->stksiz));
- }
- }
- } while ((blk = blk->lnext) != fn->entry);
-
- if (ccopt.dbg.s) {
- bfmt(ccopt.dbgout, "<< After stack >>\n");
- irdump(fn);
- }
-}
-
-/* vim:set ts=3 sw=3 expandtab: */
generated by cgit v1.2.3 (git 2.39.1) at 2026-05-02 04:53:04 +0000