diff options
Diffstat (limited to 'src')
53 files changed, 8122 insertions, 0 deletions
diff --git a/src/.gitignore b/src/.gitignore new file mode 100644 index 0000000..0416fa9 --- /dev/null +++ b/src/.gitignore @@ -0,0 +1,5 @@ +qbe +doc +.comfile +*.o +*.out diff --git a/src/.tag b/src/.tag new file mode 100644 index 0000000..5b8c210 --- /dev/null +++ b/src/.tag @@ -0,0 +1,11 @@ +Look slot( + +Get lisc.h +Get parse.c +Get isel.c +Get spill.c +Get rega.c +Get emit.c + +New +|fmt diff --git a/src/Makefile b/src/Makefile new file mode 100644 index 0000000..b9c87df --- /dev/null +++ b/src/Makefile @@ -0,0 +1,17 @@ +BIN = qbe +OBJ = main.o util.o parse.o mem.o ssa.o copy.o live.o isel.o spill.o rega.o emit.o + +CFLAGS = -Wall -Wextra -std=c99 -g -pedantic + +$(BIN): $(OBJ) + $(CC) $(LDFLAGS) $(OBJ) -o $@ + +$(OBJ): all.h + +.PHONY: clean check syndoc +clean: + rm -f $(BIN) $(OBJ) +check: $(BIN) + test/go.sh all +syndoc: + unison -auto doc ssh://qcar@h/data/d/ssa-doc diff --git a/src/all.h b/src/all.h new file mode 100644 index 0000000..e0542da --- /dev/null +++ b/src/all.h @@ -0,0 +1,554 @@ +#include <assert.h> +#include <inttypes.h> +#include <limits.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#define MAKESURE(what, x) typedef char make_sure_##what[(x)?1:-1] + +typedef unsigned int uint; +typedef unsigned short ushort; +typedef unsigned long ulong; +typedef unsigned long bits; + +typedef struct BSet BSet; +typedef struct Ref Ref; +typedef struct OpDesc OpDesc; +typedef struct Ins Ins; +typedef struct Phi Phi; +typedef struct Blk Blk; +typedef struct Use Use; +typedef struct Tmp Tmp; +typedef struct Con Con; +typedef struct Addr Mem; +typedef struct Fn Fn; +typedef struct Typ Typ; +typedef struct Dat Dat; + +enum Reg { + RXX, + + RAX, /* caller-save */ + RCX, + RDX, + RSI, + RDI, + R8, + R9, + R10, + R11, + + RBX, /* callee-save */ + R12, + R13, + R14, + R15, + + RBP, /* reserved */ + RSP, + + XMM0, /* sse */ + XMM1, + XMM2, + XMM3, + XMM4, + XMM5, + XMM6, + XMM7, + XMM8, + XMM9, + XMM10, + XMM11, + XMM12, + XMM13, + XMM14, + XMM15, + + Tmp0, /* first non-reg temporary */ + + NIReg = R12 - RAX + 1, + NFReg = XMM14 - XMM0 + 1, + NISave = 9, + NFSave = NFReg, + NRSave = NISave + NFSave, + NRClob = 5, +}; + +enum { + NString = 32, + NPred = 63, + NIns = 8192, + NAlign = 3, + NSeg = 32, + NTyp = 128, + NBit = CHAR_BIT * sizeof(bits), +}; + +MAKESURE(NBit_is_enough, NBit >= (int)Tmp0); + +#define BIT(n) ((bits)1 << (n)) + +struct BSet { + uint nt; + bits *t; +}; + +struct Ref { + uint16_t type:2; + uint16_t val:14; +}; + +enum Alt { + AType, + ACall, + AMem, + + AShift = 12, + AMask = (1<<AShift) - 1 +}; + +enum { + RTmp, + RCon, + RSlot, + RAlt, + + RAType = RAlt + AType, + RACall = RAlt + ACall, + RAMem = RAlt + AMem, + + NRef = (1<<14) - 1 +}; + +#define R (Ref){0, 0} +#define TMP(x) (Ref){RTmp, x} +#define CON(x) (Ref){RCon, x} +#define CON_Z CON(0) /* reserved zero constant */ +#define SLOT(x) (Ref){RSlot, x} +#define TYPE(x) (Ref){RAlt, (x)|(AType<<AShift)} +#define CALL(x) (Ref){RAlt, (x)|(ACall<<AShift)} +#define MEM(x) (assert(x<(1<<AShift) && "too many mems"), \ + (Ref){RAlt, (x)|(AMem<<AShift)}) + +static inline int req(Ref a, Ref b) +{ + return a.type == b.type && a.val == b.val; +} + +static inline int rtype(Ref r) +{ + if (req(r, R)) + return -1; + if (r.type == RAlt) + return RAlt + (r.val >> AShift); + return r.type; +} + +static inline int isreg(Ref r) +{ + return rtype(r) == RTmp && r.val < Tmp0; +} + +enum ICmp { +#define ICMPS(X) \ + X(ule) \ + X(ult) \ + X(sle) \ + X(slt) \ + X(sgt) \ + X(sge) \ + X(ugt) \ + X(uge) \ + X(eq) \ + X(ne) /* make sure icmpop() below works! */ + +#define X(c) IC##c, + ICMPS(X) +#undef X + NICmp, + + ICXnp = NICmp, /* x64 specific */ + ICXp, + NXICmp +}; + +static inline int icmpop(int c) +{ + return c >= ICeq ? c : ICuge - c; +} + +enum FCmp { +#define FCMPS(X) \ + X(le) \ + X(lt) \ + X(gt) \ + X(ge) \ + X(ne) \ + X(eq) \ + X(o) \ + X(uo) + +#define X(c) FC##c, + FCMPS(X) +#undef X + NFCmp +}; + +enum Class { + Kw, + Kl, + Ks, + Kd +}; + +#define KWIDE(k) ((k)&1) +#define KBASE(k) ((k)>>1) + +enum Op { + OXXX, + + /* public instructions */ + OAdd, + OSub, + ODiv, + ORem, + OUDiv, + OURem, + OMul, + OAnd, + OOr, + OXor, + OSar, + OShr, + OShl, + OCmpw, + OCmpw1 = OCmpw + NICmp-1, + OCmpl, + OCmpl1 = OCmpl + NICmp-1, + OCmps, + OCmps1 = OCmps + NFCmp-1, + OCmpd, + OCmpd1 = OCmpd + NFCmp-1, + + OStored, + OStores, + OStorel, + OStorew, + OStoreh, + OStoreb, +#define isstore(o) (OStored <= o && o <= OStoreb) + OLoadsw, /* needs to match OExt (mem.c) */ + OLoaduw, + OLoadsh, + OLoaduh, + OLoadsb, + OLoadub, + OLoad, +#define isload(o) (OLoadsw <= o && o <= OLoad) + OExtsw, + OExtuw, + OExtsh, + OExtuh, + OExtsb, + OExtub, +#define isext(o) (OExtsw <= o && o <= OExtub) + + OExts, + OTruncd, + OFtosi, + OSitof, + OCast, + + OAlloc, + OAlloc1 = OAlloc + NAlign-1, + + OCopy, + NPubOp, + + /* function instructions */ + OPar = NPubOp, + OParc, + OArg, + OArgc, + OCall, + + /* reserved instructions */ + ONop, + OAddr, + OSwap, + OSign, + OSAlloc, + OXIDiv, + OXDiv, + OXCmp, + OXSet, + OXSetnp = OXSet + ICXnp, + OXSetp = OXSet + ICXp, + OXTest, + NOp +}; + +enum Jmp { + JXXX, + JRet0, + JRetw, + JRetl, + JRets, + JRetd, + JRetc, +#define isret(j) (JRet0 <= j && j <= JRetc) + JJmp, + JJnz, + JXJc, + JXJnp = JXJc + ICXnp, + JXJp = JXJc + ICXp, + NJmp +}; + +struct OpDesc { + char *name; + int nmem; + char argcls[2][4]; + uint sflag:1; /* sets the zero flag */ + uint lflag:1; /* leaves flags */ +}; + +struct Ins { + ushort op:14; + Ref to; + Ref arg[2]; + ushort cls:2; +}; + +struct Phi { + Ref to; + Ref arg[NPred]; + Blk *blk[NPred]; + uint narg; + int cls; + Phi *link; +}; + +struct Blk { + Phi *phi; + Ins *ins; + uint nins; + struct { + short type; + Ref arg; + } jmp; + Blk *s1; + Blk *s2; + Blk *link; + + int id; + int visit; + + Blk *idom; + Blk *dom, *dlink; + Blk **fron; + int nfron; + + Blk **pred; + uint npred; + BSet in[1], out[1], gen[1]; + int nlive[2]; + int loop; + char name[NString]; +}; + +struct Use { + enum { + UXXX, + UPhi, + UIns, + UJmp, + } type; + int bid; + union { + Ins *ins; + Phi *phi; + } u; +}; + +struct Tmp { + char name[NString]; + Use *use; + uint ndef, nuse; + uint cost; + short slot; + short cls; + struct { + int r; + bits m; + } hint; + int phi; + int visit; +}; + +struct Con { + enum { + CUndef, + CBits, + CAddr, + } type; + char label[NString]; + union { + int64_t i; + double d; + float s; + } bits; + char flt; /* for printing, see parse.c */ +}; + +typedef struct Addr Addr; + +struct Addr { /* x64 addressing */ + Con offset; + Ref base; + Ref index; + int scale; +}; + +struct Fn { + Blk *start; + Tmp *tmp; + Con *con; + Mem *mem; + int ntmp; + int ncon; + int nmem; + int nblk; + int retty; /* index in typ[], -1 if no aggregate return */ + Ref retr; + Blk **rpo; + bits reg; + int slot; + char name[NString]; +}; + +struct Typ { + char name[NString]; + int dark; + uint size; + int align; + + struct { + uint isflt:1; + uint ispad:1; + uint len:30; + } seg[NSeg+1]; +}; + +struct Dat { + enum { + DStart, + DEnd, + DName, + DAlign, + DB, + DH, + DW, + DL, + DZ + } type; + union { + int64_t num; + double fltd; + float flts; + char *str; + struct { + char *nam; + int64_t off; + } ref; + } u; + char isref; + char isstr; +}; + + +/* main.c */ +extern char debug['Z'+1]; + +/* util.c */ +extern Typ typ[NTyp]; +extern Ins insb[NIns], *curi; +void diag(char *) __attribute__((noreturn)); +void *emalloc(size_t); +void *alloc(size_t); +void freeall(void); +Blk *blknew(void); +void emit(int, int, Ref, Ref, Ref); +void emiti(Ins); +void idup(Ins **, Ins *, ulong); +Ins *icpy(Ins *, Ins *, ulong); +void *vnew(ulong, size_t); +void vgrow(void *, ulong); +int phicls(int, Tmp *); +Ref newtmp(char *, int, Fn *); +Ref getcon(int64_t, Fn *); +void addcon(Con *, Con *); +void dumpts(BSet *, Tmp *, FILE *); + +void bsinit(BSet *, uint); +void bszero(BSet *); +uint bscount(BSet *); +void bsset(BSet *, uint); +void bsclr(BSet *, uint); +void bscopy(BSet *, BSet *); +void bsunion(BSet *, BSet *); +void bsinter(BSet *, BSet *); +void bsdiff(BSet *, BSet *); +int bsequal(BSet *, BSet *); +int bsiter(BSet *, uint *); + +static inline int +bshas(BSet *bs, uint elt) +{ + assert(elt < bs->nt * NBit); + return (bs->t[elt/NBit] & BIT(elt%NBit)) != 0; +} + +/* parse.c */ +extern OpDesc opdesc[NOp]; +void parse(FILE *, char *, void (Dat *), void (Fn *)); +void printfn(Fn *, FILE *); +void printref(Ref, Fn *, FILE *); +void err(char *, ...); + +/* mem.c */ +void memopt(Fn *); + +/* ssa.c */ +void filluse(Fn *); +void fillpreds(Fn *); +void fillrpo(Fn *); +void ssa(Fn *); + +/* copy.c */ +void copy(Fn *); + +/* live.c */ +void liveon(BSet *, Blk *, Blk *); +void filllive(Fn *); + +/* isel.c */ +extern int rsave[/* NRSave */]; +extern int rclob[/* NRClob */]; +bits retregs(Ref, int[2]); +bits argregs(Ref, int[2]); +void isel(Fn *); + +/* spill.c */ +void fillcost(Fn *); +void spill(Fn *); + +/* rega.c */ +void rega(Fn *); + +/* emit.c */ +void emitfn(Fn *, FILE *); +void emitdat(Dat *, FILE *); +int stashfp(int64_t, int); +void emitfin(FILE *); diff --git a/src/copy.c b/src/copy.c new file mode 100644 index 0000000..ef2d01d --- /dev/null +++ b/src/copy.c @@ -0,0 +1,159 @@ +#include "all.h" + +typedef struct RList RList; +struct RList { + int t; + RList *l; +}; + +static Ref +copyof(Ref r, Ref *cp) +{ + if (rtype(r) == RTmp) + return cp[r.val]; + else + return r; +} + +static void +update(Ref r, Ref rcp, Ref *cp, RList **w) +{ + RList *l; + + if (!req(cp[r.val], rcp)) { + cp[r.val] = rcp; + l = emalloc(sizeof *l); + l->t = r.val; + l->l = *w; + *w = l; + } +} + +static void +visitphi(Phi *p, Ref *cp, RList **w) +{ + uint a; + Ref r, r1; + + r = R; + for (a=0; a<p->narg; a++) { + r1 = copyof(p->arg[a], cp); + if (req(r1, R)) + continue; + if (req(r, R) || req(r, r1)) + r = r1; + else { + r = p->to; + break; + } + } + assert(!req(r, R)); + update(p->to, r, cp, w); +} + +static void +visitins(Ins *i, Ref *cp, RList **w) +{ + Ref r; + + if (i->op == OCopy) { + r = copyof(i->arg[0], cp); + update(i->to, r, cp, w); + } else if (!req(i->to, R)) { + assert(rtype(i->to) == RTmp); + update(i->to, i->to, cp, w); + } +} + +void +copy(Fn *fn) +{ + Blk *b; + Ref *cp, r; + RList *w, *w1; + Use *u, *u1; + Ins *i; + Phi *p, **pp; + uint a; + int t; + + w = 0; + cp = emalloc(fn->ntmp * sizeof cp[0]); + for (b=fn->start; b; b=b->link) { + for (p=b->phi; p; p=p->link) + visitphi(p, cp, &w); + for (i=b->ins; i-b->ins < b->nins; i++) + visitins(i, cp, &w); + } + while ((w1=w)) { + t = w->t; + w = w->l; + free(w1); + u = fn->tmp[t].use; + u1 = u + fn->tmp[t].nuse; + for (; u<u1; u++) + switch (u->type) { + default: + diag("copy: invalid use"); + case UPhi: + visitphi(u->u.phi, cp, &w); + break; + case UIns: + visitins(u->u.ins, cp, &w); + break; + case UJmp: + break; + } + } + for (b=fn->start; b; b=b->link) { + for (pp=&b->phi; (p=*pp);) { + r = cp[p->to.val]; + if (!req(r, p->to)) { + *pp = p->link; + continue; + } + for (a=0; a<p->narg; a++) + if (rtype(p->arg[a]) == RTmp) { + r = cp[p->arg[a].val]; + assert(!req(r, R)); + p->arg[a] = r; + } + pp=&p->link; + } + for (i=b->ins; i-b->ins < b->nins; i++) { + r = cp[i->to.val]; + if (!req(r, i->to)) { + *i = (Ins){.op = ONop}; + continue; + } + for (a=0; a<2; a++) + if (rtype(i->arg[a]) == RTmp) { + r = cp[i->arg[a].val]; + assert(!req(r, R)); + i->arg[a] = r; + } + } + if (rtype(b->jmp.arg) == RTmp) { + r = cp[b->jmp.arg.val]; + assert(!req(r, R)); + b->jmp.arg = r; + } + } + if (debug['C']) { + fprintf(stderr, "\n> Copy information:"); + for (t=Tmp0; t<fn->ntmp; t++) { + if (req(cp[t], R)) { + fprintf(stderr, "\n%10s not seen!", + fn->tmp[t].name); + } + else if (!req(cp[t], TMP(t))) { + fprintf(stderr, "\n%10s copy of ", + fn->tmp[t].name); + printref(cp[t], fn, stderr); + } + } + fprintf(stderr, "\n\n> After copy elimination:\n"); + printfn(fn, stderr); + } + free(cp); +} diff --git a/src/emit.c b/src/emit.c new file mode 100644 index 0000000..b9dc782 --- /dev/null +++ b/src/emit.c @@ -0,0 +1,666 @@ +#include "all.h" + +enum { + SLong = 0, + SWord = 1, + SShort = 2, + SByte = 3, + + Ki = -1, /* matches Kw and Kl */ + Ka = -2, /* matches all classes */ +}; + +/* Instruction format strings: + * + * if the format string starts with -, the instruction + * is assumed to be 3-address and is put in 2-address + * mode using an extra mov if necessary + * + * if the format string starts with +, the same as the + * above applies, but commutativity is also assumed + * + * %k is used to set the class of the instruction, + * it'll expand to "l", "q", "ss", "sd", depending + * on the instruction class + * %0 designates the first argument + * %1 designates the second argument + * %= designates the result + * + * if %k is not used, a prefix to 0, 1, or = must be + * added, it can be: + * M - memory reference + * L - long (64 bits) + * W - word (32 bits) + * H - short (16 bits) + * B - byte (8 bits) + * S - single precision float + * D - double precision float + */ +static struct { + short op; + short cls; + char *asm; +} omap[] = { + { OAdd, Ka, "+add%k %1, %=" }, + { OSub, Ka, "-sub%k %1, %=" }, + { OAnd, Ki, "+and%k %1, %=" }, + { OOr, Ki, "+or%k %1, %=" }, + { OXor, Ki, "+xor%k %1, %=" }, + { OSar, Ki, "-sar%k %B1, %=" }, + { OShr, Ki, "-shr%k %B1, %=" }, + { OShl, Ki, "-shl%k %B1, %=" }, + { OMul, Ki, "+imul%k %1, %=" }, + { OMul, Ks, "+mulss %1, %=" }, /* fixme */ + { OMul, Kd, "+mulsd %1, %=" }, + { ODiv, Ka, "-div%k %1, %=" }, + { OStorel, Ka, "movq %L0, %M1" }, + { OStorew, Ka, "movl %W0, %M1" }, + { OStoreh, Ka, "movw %H0, %M1" }, + { OStoreb, Ka, "movb %B0, %M1" }, + { OStores, Ka, "movss %S0, %M1" }, + { OStored, Ka, "movsd %D0, %M1" }, + { OLoad, Ka, "mov%k %M0, %=" }, + { OLoadsw, Kl, "movslq %M0, %L=" }, + { OLoadsw, Kw, "movl %M0, %W=" }, + { OLoaduw, Ki, "movl %M0, %W=" }, + { OLoadsh, Ki, "movsw%k %M0, %=" }, + { OLoaduh, Ki, "movzw%k %M0, %=" }, + { OLoadsb, Ki, "movsb%k %M0, %=" }, + { OLoadub, Ki, "movzb%k %M0, %=" }, + { OExtsw, Kl, "movslq %W0, %L=" }, + { OExtuw, Kl, "movl %W0, %W=" }, + { OExtsh, Ki, "movsw%k %H0, %=" }, + { OExtuh, Ki, "movzw%k %H0, %=" }, + { OExtsb, Ki, "movsb%k %B0, %=" }, + { OExtub, Ki, "movzb%k %B0, %=" }, + + { OExts, Kd, "cvtss2sd %0, %=" }, /* see if factorization is possible */ + { OTruncd, Ks, "cvttsd2ss %0, %=" }, + { OFtosi, Kw, "cvttss2si %0, %=" }, + { OFtosi, Kl, "cvttsd2si %0, %=" }, + { OSitof, Ks, "cvtsi2ss %W0, %=" }, + { OSitof, Kd, "cvtsi2sd %L0, %=" }, + { OCast, Ki, "movq %D0, %L=" }, + { OCast, Ka, "movq %L0, %D=" }, + + { OAddr, Ki, "lea%k %M0, %=" }, + { OSwap, Ki, "xchg%k %0, %1" }, + { OSign, Kl, "cqto" }, + { OSign, Kw, "cltd" }, + { OXDiv, Ki, "div%k %0" }, + { OXIDiv, Ki, "idiv%k %0" }, + { OXCmp, Ks, "comiss %S0, %S1" }, /* fixme, Kf */ + { OXCmp, Kd, "comisd %D0, %D1" }, + { OXCmp, Ki, "cmp%k %0, %1" }, + { OXTest, Ki, "test%k %0, %1" }, + { OXSet+ICeq, Ki, "setz %B=\n\tmovzb%k %B=, %=" }, + { OXSet+ICsle, Ki, "setle %B=\n\tmovzb%k %B=, %=" }, + { OXSet+ICslt, Ki, "setl %B=\n\tmovzb%k %B=, %=" }, + { OXSet+ICsgt, Ki, "setg %B=\n\tmovzb%k %B=, %=" }, + { OXSet+ICsge, Ki, "setge %B=\n\tmovzb%k %B=, %=" }, + { OXSet+ICne, Ki, "setnz %B=\n\tmovzb%k %B=, %=" }, + { OXSet+ICXnp, Ki, "setnp %B=\n\tmovsb%k %B=, %=" }, + { OXSet+ICXp, Ki, "setp %B=\n\tmovsb%k %B=, %=" }, + { NOp, 0, 0 } +}; + +static char *rname[][4] = { + [RAX] = {"rax", "eax", "ax", "al"}, + [RBX] = {"rbx", "ebx", "bx", "bl"}, + [RCX] = {"rcx", "ecx", "cx", "cl"}, + [RDX] = {"rdx", "edx", "dx", "dl"}, + [RSI] = {"rsi", "esi", "si", "sil"}, + [RDI] = {"rdi", "edi", "di", "dil"}, + [RBP] = {"rbp", "ebp", "bp", "bpl"}, + [RSP] = {"rsp", "esp", "sp", "spl"}, + [R8 ] = {"r8" , "r8d", "r8w", "r8b"}, + [R9 ] = {"r9" , "r9d", "r9w", "r9b"}, + [R10] = {"r10", "r10d", "r10w", "r10b"}, + [R11] = {"r11", "r11d", "r11w", "r11b"}, + [R12] = {"r12", "r12d", "r12w", "r12b"}, + [R13] = {"r13", "r13d", "r13w", "r13b"}, + [R14] = {"r14", "r14d", "r14w", "r14b"}, + [R15] = {"r15", "r15d", "r15w", "r15b"}, +}; + + +static int +slot(int s, Fn *fn) +{ + struct { int i:14; } x; + + /* sign extend s using a bitfield */ + x.i = s; + assert(NAlign == 3); + if (x.i < 0) + return -4 * x.i; + else { + assert(fn->slot >= x.i); + return -4 * (fn->slot - x.i); + } +} + +static void +emitcon(Con *con, FILE *f) +{ + switch (con->type) { + default: + diag("emit: invalid constant"); + case CAddr: + fputs(con->label, f); + if (con->bits.i) + fprintf(f, "%+"PRId64, con->bits.i); + break; + case CBits: + fprintf(f, "%"PRId64, con->bits.i); + break; + } +} + +static char * +regtoa(int reg, int sz) +{ + static char buf[6]; + + if (reg >= XMM0) { + sprintf(buf, "xmm%d", reg-XMM0); + return buf; + } else + return rname[reg][sz]; +} + +static Ref +getarg(char c, Ins *i) +{ + switch (c) { + default: + diag("emit: 0, 1, = expected in format"); + case '0': + return i->arg[0]; + case '1': + return i->arg[1]; + case '=': + return i->to; + } +} + +static void emitins(Ins, Fn *, FILE *); + +static void +emitcopy(Ref r1, Ref r2, int k, Fn *fn, FILE *f) +{ + Ins icp; + + icp.op = OCopy; + icp.arg[0] = r2; + icp.to = r1; + icp.cls = k; + emitins(icp, fn, f); +} + +static void +emitf(char *s, Ins *i, Fn *fn, FILE *f) +{ + static char clstoa[][3] = {"l", "q", "ss", "sd"}; + char c; + int sz; + Ref ref; + Mem *m; + Con off; + + switch (*s) { + case '+': + if (req(i->arg[1], i->to)) { + ref = i->arg[0]; + i->arg[0] = i->arg[1]; + i->arg[1] = ref; + } + /* fall through */ + case '-': + if (req(i->arg[1], i->to) && !req(i->arg[0], i->to)) + diag("emit: cannot convert to 2-address"); + emitcopy(i->to, i->arg[0], i->cls, fn, f); + s++; + break; + } + + fputc('\t', f); +Next: + while ((c = *s++) != '%') + if (!c) { + fputc('\n', f); + return; + } else + fputc(c, f); + switch ((c = *s++)) { + default: + diag("emit: invalid escape"); + case '%': + fputc('%', f); + break; + case 'k': + fputs(clstoa[i->cls], f); + break; + case '0': + case '1': + case '=': + sz = KWIDE(i->cls) ? SLong : SWord; + s--; + /* fall through */ + case 'D': + case 'S': + Ref: + c = *s++; + ref = getarg(c, i); + switch (rtype(ref)) { + default: + diag("emit: invalid reference"); + case RTmp: + assert(isreg(ref)); + fprintf(f, "%%%s", regtoa(ref.val, sz)); + break; + case RSlot: + fprintf(f, "%d(%%rbp)", slot(ref.val, fn)); + break; + case RAMem: + Mem: + m = &fn->mem[ref.val & AMask]; + if (rtype(m->base) == RSlot) { + off.type = CBits; + off.bits.i = slot(m->base.val, fn); + addcon(&m->offset, &off); + m->base = TMP(RBP); + } + if (m->offset.type != CUndef) + emitcon(&m->offset, f); + if (req(m->base, R) && req(m->index, R)) + break; + fputc('(', f); + if (!req(m->base, R)) + fprintf(f, "%%%s", regtoa(m->base.val, SLong)); + if (!req(m->index, R)) + fprintf(f, ", %%%s, %d", + regtoa(m->index.val, SLong), + m->scale + ); + fputc(')', f); + break; + case RCon: + fputc('$', f); + emitcon(&fn->con[ref.val], f); + break; + } + break; + case 'L': + sz = SLong; + goto Ref; + case 'W': + sz = SWord; + goto Ref; + case 'H': + sz = SShort; + goto Ref; + case 'B': + sz = SByte; + goto Ref; + case 'M': + c = *s++; + ref = getarg(c, i); + switch (rtype(ref)) { + default: + diag("emit: invalid memory reference"); + case RAMem: + goto Mem; + case RSlot: + fprintf(f, "%d(%%rbp)", slot(ref.val, fn)); + break; + case RCon: + emitcon(&fn->con[ref.val], f); + fprintf(f, "(%%rip)"); + break; + case RTmp: + assert(isreg(ref)); + fprintf(f, "(%%%s)", regtoa(ref.val, SLong)); + break; + } + break; + } + goto Next; +} + +static void +emitins(Ins i, Fn *fn, FILE *f) +{ + Ref r; + int64_t val; + int o; + + switch (i.op) { + default: + Table: + /* most instructions are just pulled out of + * the table omap[], some special cases are + * detailed below */ + for (o=0;; o++) { + /* this linear search should really be a binary + * search */ + if (omap[o].op == NOp) + diag("emit: no entry found for instruction"); + if (omap[o].op == i.op) + if (omap[o].cls == i.cls + || (omap[o].cls == Ki && KBASE(i.cls) == 0) + || (omap[o].cls == Ka)) + break; + } + emitf(omap[o].asm, &i, fn, f); + break; + case ONop: + /* just do nothing for nops, they are inserted + * by some passes */ + break; + case OMul: + /* here, we try to use the 3-addresss form + * of multiplication when possible */ + if (rtype(i.arg[1]) == RCon) { + r = i.arg[0]; + i.arg[0] = i.arg[1]; + i.arg[1] = r; + } + if (KBASE(i.cls) == 0 /* only available for ints */ + && rtype(i.arg[0]) == RCon + && rtype(i.arg[1]) == RTmp) { + emitf("imul%k %0, %1, %=", &i, fn, f); + break; + } + goto Table; + case OSub: + /* we have to use the negation trick to handle + * some 3-address substractions */ + if (req(i.to, i.arg[1])) { + emitf("neg%k %=", &i, fn, f); + emitf("add%k %0, %=", &i, fn, f); + break; + } + goto Table; + case OCopy: + /* make sure we don't emit useless copies, + * also, we can use a trick to load 64-bits + * registers, it's detailed in my note below + * http://c9x.me/art/notes.html?09/19/2015 */ + if (req(i.to, R) || req(i.arg[0], R)) + break; + if (isreg(i.to) + && rtype(i.arg[0]) == RCon + && i.cls == Kl + && fn->con[i.arg[0].val].type == CBits + && (val = fn->con[i.arg[0].val].bits.i) >= 0 + && val <= UINT32_MAX) { + emitf("movl %W0, %W=", &i, fn, f); + } else if (!req(i.arg[0], i.to)) + emitf("mov%k %0, %=", &i, fn, f); + break; + case OCall: + /* calls simply have a weird syntax in AT&T + * assembly... */ + switch (rtype(i.arg[0])) { + default: + diag("emit: invalid call instruction"); + case RCon: + fprintf(f, "\tcallq "); + emitcon(&fn->con[i.arg[0].val], f); + fprintf(f, "\n"); + break; + case RTmp: + emitf("callq *%L0", &i, fn, f); + break; + } + break; + case OSAlloc: + /* there is no good reason why this is here + * maybe we should split OSAlloc in 2 different + * instructions depending on the result + */ + emitf("subq %L0, %%rsp", &i, fn, f); + if (!req(i.to, R)) + emitcopy(i.to, TMP(RSP), Kl, fn, f); + break; + case OSwap: + if (KBASE(i.cls) == 0) + goto Table; + /* for floats, there is no swap instruction + * so we use xmm15 as a temporary + */ + emitcopy(TMP(XMM0+15), i.arg[0], i.cls, fn, f); + emitcopy(i.arg[0], i.arg[1], i.cls, fn, f); + emitcopy(i.arg[1], TMP(XMM0+15), i.cls, fn, f); + break; + } +} + +static int +cneg(int cmp) +{ + switch (cmp) { + default: diag("emit: cneg() unhandled comparison"); + case ICule: return ICugt; + case ICult: return ICuge; + case ICsle: return ICsgt; + case ICslt: return ICsge; + case ICsgt: return ICsle; + case ICsge: return ICslt; + case ICugt: return ICule; + case ICuge: return ICult; + case ICeq: return ICne; + case ICne: return ICeq; + case ICXnp: return ICXp; + case ICXp: return ICXnp; + } +} + +static int +framesz(Fn *fn) +{ + int i, o, f; + + assert(NAlign == 3); + for (i=0, o=0; i<NRClob; i++) + o ^= 1 & (fn->reg >> rclob[i]); + f = fn->slot; + f = (f + 3) & -4; + return 4*f + 8*o; +} + +void +emitfn(Fn *fn, FILE *f) +{ + static char *ctoa[] = { + [ICeq] = "z", + [ICule] = "be", + [ICult] = "b", + [ICsle] = "le", + [ICslt] = "l", + [ICsgt] = "g", + [ICsge] = "ge", + [ICugt] = "a", + [ICuge] = "ae", + [ICne] = "nz", + [ICXnp] = "np", + [ICXp] = "p" + }; + Blk *b, *s; + Ins *i, itmp; + int *r, c, fs; + + fprintf(f, + ".text\n" + ".globl %s\n" + ".type %s, @function\n" + "%s:\n" + "\tpush %%rbp\n" + "\tmov %%rsp, %%rbp\n", + fn->name, fn->name, fn->name + ); + fs = framesz(fn); + if (fs) + fprintf(f, "\tsub $%d, %%rsp\n", fs); + for (r=rclob; r-rclob < NRClob; r++) + if (fn->reg & BIT(*r)) { + itmp.arg[0] = TMP(*r); + emitf("pushq %L0", &itmp, fn, f); + } + + for (b=fn->start; b; b=b->link) { + fprintf(f, ".L%s:\n", b->name); + for (i=b->ins; i!=&b->ins[b->nins]; i++) + emitins(*i, fn, f); + switch (b->jmp.type) { + case JRet0: + for (r=&rclob[NRClob]; r>rclob;) + if (fn->reg & BIT(*--r)) { + itmp.arg[0] = TMP(*r); + emitf("popq %L0", &itmp, fn, f); + } + fprintf(f, + "\tleave\n" + "\tret\n" + ); + break; + case JJmp: + if (b->s1 != b->link) + fprintf(f, "\tjmp .L%s\n", b->s1->name); + break; + default: + c = b->jmp.type - JXJc; + if (0 <= c && c <= NXICmp) { + if (b->link == b->s2) { + s = b->s1; + } else if (b->link == b->s1) { + c = cneg(c); + s = b->s2; + } else + diag("emit: unhandled jump (1)"); + fprintf(f, "\tj%s .L%s\n", ctoa[c], s->name); + break; + } + diag("emit: unhandled jump (2)"); + } + } + +} + +void +emitdat(Dat *d, FILE *f) +{ + static int align; + static char *dtoa[] = { + [DAlign] = ".align", + [DB] = "\t.byte", + [DH] = "\t.value", + [DW] = "\t.long", + [DL] = "\t.quad" + }; + + switch (d->type) { + case DStart: + align = 0; + fprintf(f, ".data\n"); + break; + case DEnd: + break; + case DName: + if (!align) + fprintf(f, ".align 8\n"); + fprintf(f, + ".globl %s\n" + ".type %s, @object\n" + "%s:\n", + d->u.str, d->u.str, d->u.str + ); + break; + case DZ: + fprintf(f, "\t.fill %"PRId64",1,0\n", d->u.num); + break; + default: + if (d->type == DAlign) + align = 1; + + if (d->isstr) { + if (d->type != DB) + err("strings only supported for 'b' currently"); + fprintf(f, "\t.ascii \"%s\"\n", d->u.str); + } + else if (d->isref) { + fprintf(f, "%s %s%+"PRId64"\n", + dtoa[d->type], d->u.ref.nam, + d->u.ref.off); + } + else { + fprintf(f, "%s %"PRId64"\n", + dtoa[d->type], d->u.num); + } + break; + } +} + +typedef struct FBits FBits; + +struct FBits { + int64_t bits; + int wide; + FBits *link; +}; + +static FBits *stash; + +int +stashfp(int64_t n, int w) +{ + FBits **pb, *b; + int i; + + /* does a dumb de-dup of fp constants + * this should be the linker's job */ + for (pb=&stash, i=0; (b=*pb); pb=&b->link, i++) + if (n == b->bits && w == b->wide) + return i; + b = emalloc(sizeof *b); + b->bits = n; + b->wide = w; + b->link = 0; + *pb = b; + return i; +} + +void +emitfin(FILE *f) +{ + FBits *b; + int i; + + if (!stash) + return; + fprintf(f, "/* floating point constants */\n"); + fprintf(f, ".data\n.align 8\n"); + for (b=stash, i=0; b; b=b->link, i++) + if (b->wide) + fprintf(f, + ".Lfp%d:\n" + "\t.quad %"PRId64 + " /* %f */\n", + i, b->bits, + *(double *)&b->bits + ); + for (b=stash, i=0; b; b=b->link, i++) + if (!b->wide) + fprintf(f, + ".Lfp%d:\n" + "\t.long %"PRId64 + " /* %lf */\n", + i, b->bits & 0xffffffff, + *(float *)&b->bits + ); + while ((b=stash)) { + stash = b->link; + free(b); + } +} diff --git a/src/isel.c b/src/isel.c new file mode 100644 index 0000000..48e29ef --- /dev/null +++ b/src/isel.c @@ -0,0 +1,1135 @@ +#include "all.h" +#include <limits.h> + +/* For x86_64, do the following: + * + * - lower calls + * - check that constants are used only in + * places allowed + * - ensure immediates always fit in 32b + * - explicit machine register contraints + * on instructions like division. + * - implement fast locals (the streak of + * constant allocX in the first basic block) + * - recognize complex addressing modes + * + * Invariant: the use counts that are used + * in sel() must be sound. This + * is not so trivial, maybe the + * dce should be moved out... + */ + +typedef struct ANum ANum; +typedef struct AClass AClass; +typedef struct RAlloc RAlloc; + +struct ANum { + char n, l, r; + Ins *i; + Ref mem; +}; + +static void amatch(Addr *, Ref, ANum *, Fn *, int); + +static int +fcmptoi(int fc) +{ + switch (fc) { + default: diag("isel: fcmptoi defaulted"); + case FCle: return ICule; + case FClt: return ICult; + case FCgt: return ICugt; + case FCge: return ICuge; + case FCne: return ICne; + case FCeq: return ICeq; + case FCo: return ICXnp; + case FCuo: return ICXp; + } +} + +static int +iscmp(int op, int *pk, int *pc) +{ + int k, c; + + if (OCmpw <= op && op <= OCmpw1) { + c = op - OCmpw; + k = Kw; + } + else if (OCmpl <= op && op <= OCmpl1) { + c = op - OCmpl; + k = Kl; + } + else if (OCmps <= op && op <= OCmps1) { + c = fcmptoi(op - OCmps); + k = Ks; + } + else if (OCmpd <= op && op <= OCmpd1) { + c = fcmptoi(op - OCmpd); + k = Kd; + } + else + return 0; + if (pk) + *pk = k; + if (pc) + *pc = c; + return 1; +} + +static int +noimm(Ref r, Fn *fn) +{ + int64_t val; + + if (rtype(r) != RCon) + return 0; + switch (fn->con[r.val].type) { + default: + diag("isel: invalid constant"); + case CAddr: + /* we only support the 'small' + * code model of the ABI, this + * means that we can always + * address data with 32bits + */ + return 0; + case CBits: + val = fn->con[r.val].bits.i; + return (val < INT32_MIN || val > INT32_MAX); + } +} + +static int +rslot(Ref r, Fn *fn) +{ + if (rtype(r) != RTmp) + return -1; + return fn->tmp[r.val].slot; +} + +static int +argcls(Ins *i, int n) +{ + return opdesc[i->op].argcls[n][i->cls]; +} + +static void +fixarg(Ref *r, int k, int phi, Fn *fn) +{ + Addr a; + Ref r0, r1; + int s, n; + + r1 = r0 = *r; + s = rslot(r0, fn); + if (KBASE(k) == 1 && rtype(r0) == RCon) { + /* load floating points from memory + * slots, they can't be used as + * immediates + */ + r1 = MEM(fn->nmem); + vgrow(&fn->mem, ++fn->nmem); + memset(&a, 0, sizeof a); + a.offset.type = CAddr; + n = stashfp(fn->con[r0.val].bits.i, KWIDE(k)); + sprintf(a.offset.label, ".Lfp%d", n); + fn->mem[fn->nmem-1] = a; + } + else if (!phi && k == Kl && noimm(r0, fn)) { + /* load constants that do not fit in + * a 32bit signed integer into a + * long temporary + */ + r1 = newtmp("isel", Kl, fn); + emit(OCopy, Kl, r1, r0, R); + } + else if (s != -1) { + /* load fast locals' addresses into + * temporaries right before the + * instruction + */ + r1 = newtmp("isel", Kl, fn); + emit(OAddr, Kl, r1, SLOT(s), R); + } + *r = r1; +} + +static void +chuse(Ref r, int du, Fn *fn) +{ + if (rtype(r) == RTmp) + fn->tmp[r.val].nuse += du; +} + +static void +seladdr(Ref *r, ANum *an, Fn *fn) +{ + Addr a; + Ref r0, r1; + + r0 = *r; + if (rtype(r0) == RTmp) { + chuse(r0, -1, fn); + r1 = an[r0.val].mem; + if (req(r1, R)) { + amatch(&a, r0, an, fn, 1); + vgrow(&fn->mem, ++fn->nmem); + fn->mem[fn->nmem-1] = a; + r1 = MEM(fn->nmem-1); + chuse(a.base, +1, fn); + chuse(a.index, +1, fn); + if (rtype(a.base) != RTmp) + if (rtype(a.index) != RTmp) + an[r0.val].mem = r1; + } + *r = r1; + } +} + +static void +selcmp(Ref arg[2], int k, Fn *fn) +{ + Ref r; + + if (rtype(arg[0]) == RCon) { + r = arg[1]; + arg[1] = arg[0]; + arg[0] = r; + } + assert(rtype(arg[0]) != RCon); + emit(OXCmp, k, R, arg[1], arg[0]); + fixarg(&curi->arg[0], k, 0, fn); +} + +static void +sel(Ins i, ANum *an, Fn *fn) +{ + Ref r0, r1; + int x, k, kc; + int64_t val; + Ins *i0; + + if (rtype(i.to) == RTmp) + if (!isreg(i.to) && !isreg(i.arg[0]) && !isreg(i.arg[1])) + if (fn->tmp[i.to.val].nuse == 0) { + chuse(i.arg[0], -1, fn); + chuse(i.arg[1], -1, fn); + return; + } + i0 = curi; + k = i.cls; + switch (i.op) { + case ODiv: + case ORem: + case OUDiv: + case OURem: + if (i.op == ODiv || i.op == OUDiv) + r0 = TMP(RAX), r1 = TMP(RDX); + else + r0 = TMP(RDX), r1 = TMP(RAX); + emit(OCopy, k, i.to, r0, R); + emit(OCopy, k, R, r1, R); + if (rtype(i.arg[1]) == RCon) { + /* immediates not allowed for + * divisions in x86 + */ + r0 = newtmp("isel", k, fn); + } else + r0 = i.arg[1]; + if (i.op == ODiv || i.op == ORem) { + emit(OXIDiv, k, R, r0, R); + emit(OSign, k, TMP(RDX), TMP(RAX), R); + } else { + emit(OXDiv, k, R, r0, R); + emit(OCopy, k, TMP(RDX), CON_Z, R); + } + emit(OCopy, k, TMP(RAX), i.arg[0], R); + if (rtype(i.arg[1]) == RCon) + emit(OCopy, k, r0, i.arg[1], R); + break; + case OSar: + case OShr: + case OShl: + if (rtype(i.arg[1]) == RCon) + goto Emit; + r0 = i.arg[1]; + i.arg[1] = TMP(RCX); + emit(OCopy, Kw, R, TMP(RCX), R); + emiti(i); + emit(OCopy, Kw, TMP(RCX), r0, R); + break; + case ONop: + break; + case OStored: + case OStores: + case OStorel: + case OStorew: + case OStoreh: + case OStoreb: + if (rtype(i.arg[0]) == RCon) { + if (i.op == OStored) + i.op = OStorel; + if (i.op == OStores) + i.op = OStorew; + } + seladdr(&i.arg[1], an, fn); + goto Emit; + case_OLoad: + seladdr(&i.arg[0], an, fn); + goto Emit; + case OCall: + case OSAlloc: + case OCopy: + case OAdd: + case OSub: + case OMul: + case OAnd: + case OOr: + case OXor: + case OXTest: + case OFtosi: + case OSitof: + case OExts: + case OTruncd: + case OCast: + case_OExt: +Emit: + emiti(i); + fixarg(&curi->arg[0], argcls(curi, 0), 0, fn); + fixarg(&curi->arg[1], argcls(curi, 1), 0, fn); + break; + case OAlloc: + case OAlloc+1: + case OAlloc+2: /* == OAlloc1 */ + /* we need to make sure + * the stack remains aligned + * (rsp = 0) mod 16 + */ + if (rtype(i.arg[0]) == RCon) { + assert(fn->con[i.arg[0].val].type == CBits); + val = fn->con[i.arg[0].val].bits.i; + val = (val + 15) & ~INT64_C(15); + if (val < 0 || val > INT32_MAX) + diag("isel: alloc too large"); + emit(OSAlloc, Kl, i.to, getcon(val, fn), R); + } else { + /* r0 = (i.arg[0] + 15) & -16 */ + r0 = newtmp("isel", Kl, fn); + r1 = newtmp("isel", Kl, fn); + emit(OSAlloc, Kl, i.to, r0, R); + emit(OAnd, Kl, r0, r1, getcon(-16, fn)); + emit(OAdd, Kl, r1, i.arg[0], getcon(15, fn)); + } + break; + default: + if (isext(i.op)) + goto case_OExt; + if (isload(i.op)) + goto case_OLoad; + if (iscmp(i.op, &kc, &x)) { + if (rtype(i.arg[0]) == RCon) + x = icmpop(x); + emit(OXSet+x, k, i.to, R, R); + selcmp(i.arg, kc, fn); + break; + } + diag("isel: non-exhaustive implementation"); + } + + while (i0 > curi && --i0) + if (rslot(i0->arg[0], fn) != -1 + || rslot(i0->arg[1], fn) != -1) + diag("isel: usupported address argument"); +} + +static Ins * +flagi(Ins *i0, Ins *i) +{ + while (i>i0) { + i--; + if (opdesc[i->op].sflag) + return i; + if (opdesc[i->op].lflag) + continue; + return 0; + } + return 0; +} + +struct AClass { + int inmem; + int align; + uint size; + int cls[2]; +}; + +static void +aclass(AClass *a, Typ *t) +{ + int e, s, n, cls; + uint sz, al; + + sz = t->size; + al = 1u << t->align; + + /* the ABI requires sizes to be rounded + * up to the nearest multiple of 8, moreover + * it makes it easy load and store structures + * in registers + */ + if (al < 8) + al = 8; + sz = (sz + al-1) & -al; + + a->size = sz; + a->align = t->align; + + if (t->dark || sz > 16) { + /* large or unaligned structures are + * required to be passed in memory + */ + a->inmem = 1; + return; + } + + a->inmem = 0; + for (e=0, s=0; e<2; e++) { + cls = -1; + for (n=0; n<8 && t->seg[s].len; s++) { + if (t->seg[s].ispad) { + /* don't change anything */ + } + else if (t->seg[s].isflt) { + if (cls == -1) + cls = Kd; + } + else + cls = Kl; + n += t->seg[s].len; + } + assert(n <= 8); + a->cls[e] = cls; + } +} + +static void +blit(Ref rstk, uint soff, Ref rsrc, uint sz, Fn *fn) +{ + Ref r, r1; + uint boff; + + /* it's an impolite blit, we might go across the end + * of the source object a little bit... */ + for (boff=0; sz>0; sz-=8, soff+=8, boff+=8) { + r = newtmp("abi", Kl, fn); + r1 = newtmp("abi", Kl, fn); + emit(OStorel, 0, R, r, r1); + emit(OAdd, Kl, r1, rstk, getcon(soff, fn)); + r1 = newtmp("abi", Kl, fn); + emit(OLoad, Kl, r, r1, R); + emit(OAdd, Kl, r1, rsrc, getcon(boff, fn)); + chuse(rsrc, +1, fn); + chuse(rstk, +1, fn); + } +} + +static int +retr(Ref reg[2], AClass *aret) +{ + static int retreg[2][2] = {{RAX, RDX}, {XMM0, XMM0+1}}; + int n, k, ca, nr[2]; + + nr[0] = nr[1] = 0; + ca = 0; + for (n=0; aret->cls[n]>=0 && n<2; n++) { + k = KBASE(aret->cls[n]); + reg[n] = TMP(retreg[k][nr[k]++]); + ca += 1 << (2 * k); + } + return ca; +} + +static void +selret(Blk *b, Fn *fn) +{ + int j, k, ca; + Ref r, r0, reg[2]; + AClass aret; + + j = b->jmp.type; + + if (!isret(j) || j == JRet0) + return; + + r0 = b->jmp.arg; + b->jmp.type = JRet0; + + if (j == JRetc) { + aclass(&aret, &typ[fn->retty]); + if (aret.inmem) { + assert(rtype(fn->retr) == RTmp); + emit(OCopy, Kl, TMP(RAX), fn->retr, R); + chuse(fn->retr, +1, fn); + blit(fn->retr, 0, r0, aret.size, fn); + ca = 1; + } else { + ca = retr(reg, &aret); + if (aret.size > 8) { + r = newtmp("abi", Kl, fn); + emit(OLoad, Kl, reg[1], r, R); + emit(OAdd, Kl, r, r0, getcon(8, fn)); + chuse(r0, +1, fn); + } + emit(OLoad, Kl, reg[0], r0, R); + } + } else { + k = j - JRetw; + if (KBASE(k) == 0) { + emit(OCopy, k, TMP(RAX), r0, R); + ca = 1; + } else { + emit(OCopy, k, TMP(XMM0), r0, R); + ca = 1 << 2; + } + } + + b->jmp.arg = CALL(ca); +} + +static void +seljmp(Blk *b, Fn *fn) +{ + Ref r; + int c, k; + Ins *fi; + + if (b->jmp.type == JRet0 || b->jmp.type == JJmp) + return; + assert(b->jmp.type == JJnz); + r = b->jmp.arg; + b->jmp.arg = R; + assert(!req(r, R)); + if (rtype(r) == RCon) { + b->jmp.type = JJmp; + if (req(r, CON_Z)) + b->s1 = b->s2; + b->s2 = 0; + return; + } + fi = flagi(b->ins, &b->ins[b->nins]); + if (fi && req(fi->to, r)) { + if (iscmp(fi->op, &k, &c)) { + if (rtype(fi->arg[0]) == RCon) + c = icmpop(c); + b->jmp.type = JXJc + c; + if (fn->tmp[r.val].nuse == 1) { + assert(fn->tmp[r.val].ndef == 1); + selcmp(fi->arg, k, fn); + *fi = (Ins){.op = ONop}; + } + return; + } + if (fi->op == OAnd && fn->tmp[r.val].nuse == 1 + && (rtype(fi->arg[0]) == RTmp || + rtype(fi->arg[1]) == RTmp)) { + fi->op = OXTest; + fi->to = R; + b->jmp.type = JXJc + ICne; + if (rtype(fi->arg[1]) == RCon) { + r = fi->arg[1]; + fi->arg[1] = fi->arg[0]; + fi->arg[0] = r; + } + return; + } + /* since flags are not tracked in liveness, + * the result of the flag-setting instruction + * has to be marked as live + */ + if (fn->tmp[r.val].nuse == 1) + emit(OCopy, Kw, R, r, R); + b->jmp.type = JXJc + ICne; + return; + } + selcmp((Ref[2]){r, CON_Z}, Kw, fn); /* todo, add long branch if non-zero */ + b->jmp.type = JXJc + ICne; +} + +static int +classify(Ins *i0, Ins *i1, AClass *ac, int op, AClass *aret) +{ + int nint, ni, nsse, ns, n, *pn; + AClass *a; + Ins *i; + + if (aret && aret->inmem) + nint = 5; /* hidden argument */ + else + nint = 6; + nsse = 8; + for (i=i0, a=ac; i<i1; i++, a++) { + if (i->op == op) { + if (KBASE(i->cls) == 0) + pn = &nint; + else + pn = &nsse; + if (*pn > 0) { + --*pn; + a->inmem = 0; + } else + a->inmem = 2; + a->align = 3; + a->size = 8; + a->cls[0] = i->cls; + } else { + n = i->arg[0].val & AMask; + aclass(a, &typ[n]); + if (a->inmem) + continue; + ni = ns = 0; + for (n=0; n<2; n++) + if (KBASE(a->cls[n]) == 0) + ni++; + else + ns++; + if (nint >= ni && nsse >= ns) { + nint -= ni; + nsse -= ns; + } else + a->inmem = 1; + } + } + + return ((6-nint) << 4) | ((8-nsse) << 8); +} + +int rsave[] = { + RDI, RSI, RDX, RCX, R8, R9, R10, R11, RAX, + XMM0, XMM1, XMM2, XMM3, XMM4, XMM5, XMM6, XMM7, + XMM8, XMM9, XMM10, XMM11, XMM12, XMM13, XMM14 +}; +int rclob[] = {RBX, R12, R13, R14, R15}; + +MAKESURE(rsave_has_correct_size, sizeof rsave == NRSave * sizeof(int)); +MAKESURE(rclob_has_correct_size, sizeof rclob == NRClob * sizeof(int)); + +bits +retregs(Ref r, int p[2]) +{ + bits b; + int ni, nf; + + assert(rtype(r) == RACall); + b = 0; + ni = r.val & 3; + nf = (r.val >> 2) & 3; + if (ni >= 1) + b |= BIT(RAX); + if (ni >= 2) + b |= BIT(RDX); + if (nf >= 1) + b |= BIT(XMM0); + if (nf >= 2) + b |= BIT(XMM1); + if (p) { + p[0] = ni; + p[1] = nf; + } + return b; +} + +bits +argregs(Ref r, int p[2]) +{ + bits b; + int j, ni, nf; + + assert(rtype(r) == RACall); + b = 0; + ni = (r.val >> 4) & 15; + nf = (r.val >> 8) & 15; + for (j=0; j<ni; j++) + b |= BIT(rsave[j]); + for (j=0; j<nf; j++) + b |= BIT(XMM0+j); + if (p) { + p[0] = ni + 1; + p[1] = nf; + } + return b | BIT(RAX); +} + +static Ref +rarg(int ty, int *ni, int *ns) +{ + if (KBASE(ty) == 0) + return TMP(rsave[(*ni)++]); + else + return TMP(XMM0 + (*ns)++); +} + +struct RAlloc { + Ins i; + RAlloc *link; +}; + +static void +selcall(Fn *fn, Ins *i0, Ins *i1, RAlloc **rap) +{ + Ins *i; + AClass *ac, *a, aret; + int ca, ni, ns; + uint stk, off; + Ref r, r1, r2, reg[2], regcp[2]; + RAlloc *ra; + + ac = alloc((i1-i0) * sizeof ac[0]); + if (!req(i1->arg[1], R)) { + assert(rtype(i1->arg[1]) == RAType); + aclass(&aret, &typ[i1->arg[1].val & AMask]); + ca = classify(i0, i1, ac, OArg, &aret); + } else + ca = classify(i0, i1, ac, OArg, 0); + + for (stk=0, a=&ac[i1-i0]; a>ac;) + if ((--a)->inmem) { + assert(a->align <= 4); + stk += a->size; + if (a->align == 4) + stk += stk & 15; + } + stk += stk & 15; + if (stk) { + r = getcon(-(int64_t)stk, fn); + emit(OSAlloc, Kl, R, r, R); + } + + if (!req(i1->arg[1], R)) { + if (aret.inmem) { + /* get the return location from eax + * it saves one callee-save reg */ + r1 = newtmp("abi", Kl, fn); + emit(OCopy, Kl, i1->to, TMP(RAX), R); + ca += 1; + } else { + if (aret.size > 8) { + r = newtmp("abi", Kl, fn); + regcp[1] = newtmp("abi", aret.cls[1], fn); + emit(OStorel, 0, R, regcp[1], r); + emit(OAdd, Kl, r, i1->to, getcon(8, fn)); + chuse(i1->to, +1, fn); + ca += 1 << (2 * KBASE(aret.cls[1])); + } + regcp[0] = newtmp("abi", aret.cls[0], fn); + emit(OStorel, 0, R, regcp[0], i1->to); + ca += 1 << (2 * KBASE(aret.cls[0])); + retr(reg, &aret); + if (aret.size > 8) + emit(OCopy, aret.cls[1], regcp[1], reg[1], R); + emit(OCopy, aret.cls[0], regcp[0], reg[0], R); + r1 = i1->to; + } + /* allocate return pad */ + ra = alloc(sizeof *ra); + assert(NAlign == 3); + aret.align -= 2; + if (aret.align < 0) + aret.align = 0; + ra->i.op = OAlloc + aret.align; + ra->i.cls = Kl; + ra->i.to = r1; + ra->i.arg[0] = getcon(aret.size, fn); + ra->link = (*rap); + *rap = ra; + } else { + ra = 0; + if (KBASE(i1->cls) == 0) { + emit(OCopy, i1->cls, i1->to, TMP(RAX), R); + ca += 1; + } else { + emit(OCopy, i1->cls, i1->to, TMP(XMM0), R); + ca += 1 << 2; + } + } + emit(OCall, i1->cls, R, i1->arg[0], CALL(ca)); + emit(OCopy, Kw, TMP(RAX), getcon((ca >> 8) & 15, fn), R); + + ni = ns = 0; + if (ra && aret.inmem) + emit(OCopy, Kl, rarg(Kl, &ni, &ns), ra->i.to, R); /* pass hidden argument */ + for (i=i0, a=ac; i<i1; i++, a++) { + if (a->inmem) + continue; + r1 = rarg(a->cls[0], &ni, &ns); + if (i->op == OArgc) { + if (a->size > 8) { + r2 = rarg(a->cls[1], &ni, &ns); + r = newtmp("abi", Kl, fn); + emit(OLoad, a->cls[1], r2, r, R); + emit(OAdd, Kl, r, i->arg[1], getcon(8, fn)); + chuse(i->arg[1], +1, fn); + } + emit(OLoad, a->cls[0], r1, i->arg[1], R); + } else + emit(OCopy, i->cls, r1, i->arg[0], R); + } + + if (!stk) + return; + + r = newtmp("abi", Kl, fn); + chuse(r, -1, fn); + for (i=i0, a=ac, off=0; i<i1; i++, a++) { + if (!a->inmem) + continue; + if (i->op == OArgc) { + if (a->align == 4) + off += off & 15; + blit(r, off, i->arg[1], a->size, fn); + } else { + r1 = newtmp("abi", Kl, fn); + emit(OStorel, 0, R, i->arg[0], r1); + emit(OAdd, Kl, r1, r, getcon(off, fn)); + chuse(r, +1, fn); + } + off += a->size; + } + emit(OSAlloc, Kl, r, getcon(stk, fn), R); +} + +static void +selpar(Fn *fn, Ins *i0, Ins *i1) +{ + AClass *ac, *a, aret; + Ins *i; + int ni, ns, s, al; + Ref r, r1; + + ac = alloc((i1-i0) * sizeof ac[0]); + curi = insb; + ni = ns = 0; + + if (fn->retty >= 0) { + aclass(&aret, &typ[fn->retty]); + if (aret.inmem) { + r = newtmp("abi", Kl, fn); + *curi++ = (Ins){OCopy, r, {rarg(Kl, &ni, &ns)}, Kl}; + fn->retr = r; + } + classify(i0, i1, ac, OPar, &aret); + } else + classify(i0, i1, ac, OPar, 0); + + assert(NAlign == 3); + + s = 4; + for (i=i0, a=ac; i<i1; i++, a++) { + switch (a->inmem) { + case 1: + assert(a->align <= 4); + if (a->align == 4) + s = (s+3) & -4; + fn->tmp[i->to.val].slot = -s; /* HACK! */ + s += a->size / 4; + continue; + case 2: + *curi++ = (Ins){OLoad, i->to, {SLOT(-s)}, i->cls}; + s += 2; + continue; + } + r1 = rarg(a->cls[0], &ni, &ns); + if (i->op == OParc) { + r = newtmp("abi", Kl, fn); + *curi++ = (Ins){OCopy, r, {r1}, Kl}; + a->cls[0] = r.val; + if (a->size > 8) { + r1 = rarg(a->cls[1], &ni, &ns); + r = newtmp("abi", Kl, fn); + *curi++ = (Ins){OCopy, r, {r1}, Kl}; + a->cls[1] = r.val; + } + } else + *curi++ = (Ins){OCopy, i->to, {r1}, i->cls}; + } + for (i=i0, a=ac; i<i1; i++, a++) { + if (i->op != OParc || a->inmem) + continue; + assert(NAlign == 3); + for (al=0; a->align >> (al+2); al++) + ; + r = TMP(a->cls[0]); + r1 = i->to; + *curi++ = (Ins){OAlloc+al, r1, {getcon(a->size, fn)}, Kl}; + *curi++ = (Ins){OStorel, R, {r, r1}, 0}; + if (a->size > 8) { + r = newtmp("abi", Kl, fn); + *curi++ = (Ins){OAdd, r, {r1, getcon(8, fn)}, Kl}; + r1 = TMP(a->cls[1]); + *curi++ = (Ins){OStorel, R, {r1, r}, 0}; + } + } +} + +static int +aref(Ref r, ANum *ai) +{ + switch (rtype(r)) { + default: + diag("isel: aref defaulted"); + case RCon: + return 2; + case RTmp: + return ai[r.val].n; + } +} + +static int +ascale(Ref r, Con *con) +{ + int64_t n; + + if (rtype(r) != RCon) + return 0; + if (con[r.val].type != CBits) + return 0; + n = con[r.val].bits.i; + return n == 1 || n == 2 || n == 4 || n == 8; +} + +static void +anumber(ANum *ai, Blk *b, Con *con) +{ + /* This should be made obsolete by a proper + * reassoc pass. + * + * Rules: + * + * RTmp(_) -> 0 tmp + * ( RTmp(_) -> 1 slot ) + * RCon(_) -> 2 con + * 0 * 2 -> 3 s * i (when constant is 1,2,4,8) + */ + static char add[10][10] = { + [2] [2] = 2, /* folding */ + [2] [5] = 5, [5] [2] = 5, + [2] [6] = 6, [6] [2] = 6, + [2] [7] = 7, [7] [2] = 7, + [0] [0] = 4, /* 4: b + s * i */ + [0] [3] = 4, [3] [0] = 4, + [2] [3] = 5, [3] [2] = 5, /* 5: o + s * i */ + [0] [2] = 6, [2] [0] = 6, /* 6: o + b */ + [2] [4] = 7, [4] [2] = 7, /* 7: o + b + s * i */ + [0] [5] = 7, [5] [0] = 7, + [6] [3] = 7, [3] [6] = 7, + + }; + int a, a1, a2, n1, n2, t1, t2; + Ins *i; + + for (i=b->ins; i-b->ins < b->nins; i++) { + if (rtype(i->to) == RTmp) + ai[i->to.val].i = i; + if (i->op != OAdd && i->op != OMul) + continue; + a1 = aref(i->arg[0], ai); + a2 = aref(i->arg[1], ai); + t1 = a1 != 1 && a1 != 2; + t2 = a2 != 1 && a2 != 2; + if (i->op == OAdd) { + a = add[n1 = a1][n2 = a2]; + if (t1 && a < add[0][a2]) + a = add[n1 = 0][n2 = a2]; + if (t2 && a < add[a1][0]) + a = add[n1 = a1][n2 = 0]; + if (t1 && t2 && a < add[0][0]) + a = add[n1 = 0][n2 = 0]; + } else { + n1 = n2 = a = 0; + if (ascale(i->arg[0], con) && t2) + a = 3, n1 = 2, n2 = 0; + if (t1 && ascale(i->arg[1], con)) + a = 3, n1 = 0, n2 = 2; + } + ai[i->to.val].n = a; + ai[i->to.val].l = n1; + ai[i->to.val].r = n2; + } +} + +static void +amatch(Addr *a, Ref r, ANum *ai, Fn *fn, int top) +{ + Ins *i; + int nl, nr, t, s; + Ref al, ar; + + if (top) + memset(a, 0, sizeof *a); + if (rtype(r) == RCon) { + addcon(&a->offset, &fn->con[r.val]); + return; + } + assert(rtype(r) == RTmp); + i = ai[r.val].i; + nl = ai[r.val].l; + nr = ai[r.val].r; + if (i) { + if (nl > nr) { + al = i->arg[1]; + ar = i->arg[0]; + t = nl, nl = nr, nr = t; + } else { + al = i->arg[0]; + ar = i->arg[1]; + } + } + switch (ai[r.val].n) { + default: + diag("isel: amatch defaulted"); + case 3: /* s * i */ + if (!top) { + a->index = al; + a->scale = fn->con[ar.val].bits.i; + } else + a->base = r; + break; + case 4: /* b + s * i */ + switch (nr) { + case 0: + if (fn->tmp[ar.val].slot != -1) { + al = i->arg[1]; + ar = i->arg[0]; + } + a->index = ar; + a->scale = 1; + break; + case 3: + amatch(a, ar, ai, fn, 0); + break; + } + r = al; + case 0: + s = fn->tmp[r.val].slot; + if (s != -1) + r = SLOT(s); + a->base = r; + break; + case 2: /* constants */ + case 5: /* o + s * i */ + case 6: /* o + b */ + case 7: /* o + b + s * i */ + amatch(a, ar, ai, fn, 0); + amatch(a, al, ai, fn, 0); + break; + } +} + +/* instruction selection + * requires use counts (as given by parsing) + */ +void +isel(Fn *fn) +{ + Blk *b, **sb; + Ins *i, *i0, *ip; + Phi *p; + uint a; + int n, al; + int64_t sz; + ANum *ainfo; + RAlloc *ral; + + for (n=0; n<fn->ntmp; n++) + fn->tmp[n].slot = -1; + fn->slot = 0; + + /* lower arguments */ + for (b=fn->start, i=b->ins; i-b->ins < b->nins; i++) + if (i->op != OPar && i->op != OParc) + break; + selpar(fn, b->ins, i); + n = b->nins - (i - b->ins) + (curi - insb); + i0 = alloc(n * sizeof(Ins)); + ip = icpy(ip = i0, insb, curi - insb); + ip = icpy(ip, i, &b->ins[b->nins] - i); + b->nins = n; + b->ins = i0; + + /* lower function calls and returns */ + ral = 0; + b = fn->start; + do { + if (!(b = b->link)) + b = fn->start; /* do it last */ + curi = &insb[NIns]; + selret(b, fn); + for (i=&b->ins[b->nins]; i!=b->ins;) { + if ((--i)->op == OCall) { + for (i0=i; i0>b->ins; i0--) + if ((i0-1)->op != OArg) + if ((i0-1)->op != OArgc) + break; + selcall(fn, i0, i, &ral); + i = i0; + continue; + } + assert(i->op != OArg && i->op != OArgc); + emiti(*i); + } + if (b == fn->start) + for (; ral; ral=ral->link) + emiti(ral->i); + b->nins = &insb[NIns] - curi; + idup(&b->ins, curi, b->nins); + } while (b != fn->start); + + if (debug['A']) { + fprintf(stderr, "\n> After call lowering:\n"); + printfn(fn, stderr); + } + + /* assign slots to fast allocs */ + b = fn->start; + assert(NAlign == 3 && "change n=4 and sz /= 4 below"); + for (al=OAlloc, n=4; al<=OAlloc1; al++, n*=2) + for (i=b->ins; i-b->ins < b->nins; i++) + if (i->op == al) { + if (rtype(i->arg[0]) != RCon) + break; + sz = fn->con[i->arg[0].val].bits.i; + if (sz < 0 || sz >= INT_MAX-3) + diag("isel: invalid alloc size"); + sz = (sz + n-1) & -n; + sz /= 4; + fn->tmp[i->to.val].slot = fn->slot; + fn->slot += sz; + *i = (Ins){.op = ONop}; + } + + /* process basic blocks */ + n = fn->ntmp; + ainfo = emalloc(n * sizeof ainfo[0]); + for (b=fn->start; b; b=b->link) { + curi = &insb[NIns]; + for (sb=(Blk*[3]){b->s1, b->s2, 0}; *sb; sb++) + for (p=(*sb)->phi; p; p=p->link) { + for (a=0; p->blk[a] != b; a++) + assert(a+1 < p->narg); + fixarg(&p->arg[a], p->cls, 1, fn); + } + memset(ainfo, 0, n * sizeof ainfo[0]); + anumber(ainfo, b, fn->con); + seljmp(b, fn); + for (i=&b->ins[b->nins]; i!=b->ins;) + sel(*--i, ainfo, fn); + b->nins = &insb[NIns] - curi; + idup(&b->ins, curi, b->nins); + } + free(ainfo); + + if (debug['I']) { + fprintf(stderr, "\n> After instruction selection:\n"); + printfn(fn, stderr); + } +} diff --git a/src/live.c b/src/live.c new file mode 100644 index 0000000..44806e1 --- /dev/null +++ b/src/live.c @@ -0,0 +1,174 @@ +#include "all.h" + +void +liveon(BSet *v, Blk *b, Blk *s) +{ + Phi *p; + uint a; + + bscopy(v, s->in); + for (p=s->phi; p; p=p->link) { + bsclr(v, p->to.val); + for (a=0; a<p->narg; a++) + if (p->blk[a] == b) + if (rtype(p->arg[a]) == RTmp) + bsset(v, p->arg[a].val); + } +} + +static int +phitmp(int t, Tmp *tmp) +{ + int tp; + + tp = tmp[t].phi; + return tp ? tp : t; +} + +static void +phifix(int t1, short *phi, Tmp *tmp) +{ + int t, t2; + + /* detect temporaries arguments + * of the same phi node that + * interfere and separate them + */ + t = phitmp(t1, tmp); + t2 = phi[t]; + if (t2 && t2 != t1) { + if (t != t1) { + tmp[t1].phi = t1; + t = t1; + } else { + tmp[t2].phi = t2; + phi[t2] = t2; + } + } + phi[t] = t1; +} + +static void +bset(Ref r, Blk *b, int *nlv, short *phi, Tmp *tmp) +{ + + if (rtype(r) != RTmp) + return; + bsset(b->gen, r.val); + phifix(r.val, phi, tmp); + if (!bshas(b->in, r.val)) { + nlv[KBASE(tmp[r.val].cls)]++; + bsset(b->in, r.val); + } +} + +/* liveness analysis + * requires rpo computation + */ +void +filllive(Fn *f) +{ + Blk *b; + Ins *i; + int k, t, m[2], n, chg, nlv[2]; + short *phi; + BSet u[1], v[1]; + Mem *ma; + + bsinit(u, f->ntmp); + bsinit(v, f->ntmp); + phi = emalloc(f->ntmp * sizeof phi[0]); + for (b=f->start; b; b=b->link) { + bsinit(b->in, f->ntmp); + bsinit(b->out, f->ntmp); + bsinit(b->gen, f->ntmp); + } + chg = 1; +Again: + for (n=f->nblk-1; n>=0; n--) { + b = f->rpo[n]; + + bscopy(u, b->out); + if (b->s1) { + liveon(v, b, b->s1); + bsunion(b->out, v); + } + if (b->s2) { + liveon(v, b, b->s2); + bsunion(b->out, v); + } + chg |= !bsequal(b->out, u); + + memset(phi, 0, f->ntmp * sizeof phi[0]); + memset(nlv, 0, sizeof nlv); + bscopy(b->in, b->out); + for (t=0; t<f->ntmp; t++) + if (bshas(b->in, t)) { + phifix(t, phi, f->tmp); + nlv[KBASE(f->tmp[t].cls)]++; + } + if (rtype(b->jmp.arg) == RACall) { + assert(bscount(b->in) == 0 && nlv[0] == 0 && nlv[1] == 0); + b->in->t[0] |= retregs(b->jmp.arg, nlv); + } else + bset(b->jmp.arg, b, nlv, phi, f->tmp); + for (k=0; k<2; k++) + b->nlive[k] = nlv[k]; + for (i=&b->ins[b->nins]; i!=b->ins;) { + if ((--i)->op == OCall && rtype(i->arg[1]) == RACall) { + b->in->t[0] &= ~retregs(i->arg[1], m); + for (k=0; k<2; k++) + nlv[k] -= m[k]; + if (nlv[0] + NISave > b->nlive[0]) + b->nlive[0] = nlv[0] + NISave; + if (nlv[1] + NFSave > b->nlive[1]) + b->nlive[1] = nlv[1] + NFSave; + b->in->t[0] |= argregs(i->arg[1], m); + for (k=0; k<2; k++) + nlv[k] += m[k]; + } + if (!req(i->to, R)) { + assert(rtype(i->to) == RTmp); + t = i->to.val; + if (bshas(b->in, i->to.val)) + nlv[KBASE(f->tmp[t].cls)]--; + bsset(b->gen, t); + bsclr(b->in, t); + phi[phitmp(t, f->tmp)] = 0; + } + for (k=0; k<2; k++) + switch (rtype(i->arg[k])) { + case RAMem: + ma = &f->mem[i->arg[k].val & AMask]; + bset(ma->base, b, nlv, phi, f->tmp); + bset(ma->index, b, nlv, phi, f->tmp); + break; + default: + bset(i->arg[k], b, nlv, phi, f->tmp); + break; + } + for (k=0; k<2; k++) + if (nlv[k] > b->nlive[k]) + b->nlive[k] = nlv[k]; + } + } + if (chg) { + chg = 0; + goto Again; + } + free(phi); + + if (debug['L']) { + fprintf(stderr, "\n> Liveness analysis:\n"); + for (b=f->start; b; b=b->link) { + fprintf(stderr, "\t%-10sin: ", b->name); + dumpts(b->in, f->tmp, stderr); + fprintf(stderr, "\t out: "); + dumpts(b->out, f->tmp, stderr); + fprintf(stderr, "\t gen: "); + dumpts(b->gen, f->tmp, stderr); + fprintf(stderr, "\t live: "); + fprintf(stderr, "%d %d\n", b->nlive[0], b->nlive[1]); + } + } +} diff --git a/src/main.c b/src/main.c new file mode 100644 index 0000000..b8cd7d6 --- /dev/null +++ b/src/main.c @@ -0,0 +1,117 @@ +#include "all.h" +#include <ctype.h> +#include <getopt.h> + +char debug['Z'+1] = { + ['P'] = 0, /* parsing */ + ['A'] = 0, /* abi lowering */ + ['I'] = 0, /* instruction selection */ + ['L'] = 0, /* liveness */ + ['M'] = 0, /* memory optimization */ + ['N'] = 0, /* ssa construction */ + ['C'] = 0, /* copy elimination */ + ['S'] = 0, /* spilling */ + ['R'] = 0, /* reg. allocation */ +}; + +static FILE *outf; +static int dbg; + +static void +data(Dat *d) +{ + if (dbg) + return; + if (d->type == DEnd) { + fputs("/* end data */\n\n", outf); + freeall(); + } + emitdat(d, outf); +} + +static void +func(Fn *fn) +{ + int n; + + if (dbg) + fprintf(stderr, "**** Function %s ****", fn->name); + if (debug['P']) { + fprintf(stderr, "\n> After parsing:\n"); + printfn(fn, stderr); + } + fillrpo(fn); + fillpreds(fn); + filluse(fn); + memopt(fn); + ssa(fn); + filluse(fn); + copy(fn); + filluse(fn); + isel(fn); + filllive(fn); + fillcost(fn); + spill(fn); + rega(fn); + fillrpo(fn); + assert(fn->rpo[0] == fn->start); + for (n=0;; n++) + if (n == fn->nblk-1) { + fn->rpo[n]->link = 0; + break; + } else + fn->rpo[n]->link = fn->rpo[n+1]; + if (!dbg) { + emitfn(fn, outf); + fprintf(outf, "/* end function %s */\n\n", fn->name); + } else + fprintf(stderr, "\n"); + freeall(); +} + +int +main(int ac, char *av[]) +{ + FILE *inf; + char *f; + int c; + + outf = stdout; + while ((c = getopt(ac, av, "d:o:")) != -1) + switch (c) { + case 'd': + for (; *optarg; optarg++) + if (isalpha(*optarg)) { + debug[toupper(*optarg)] = 1; + dbg = 1; + } + break; + case 'o': + if (strcmp(optarg, "-") != 0) + outf = fopen(optarg, "w"); + break; + default: + fprintf(stderr, "usage: %s [-d <flags>] [-o out] {file.ssa, -}\n", av[0]); + exit(1); + } + + do { + f = av[optind]; + if (!f || strcmp(f, "-") == 0) { + inf = stdin; + f = "-"; + } else { + inf = fopen(f, "r"); + if (!inf) { + fprintf(stderr, "cannot open '%s'\n", f); + exit(1); + } + } + parse(inf, f, data, func); + } while (++optind < ac); + + if (!dbg) + emitfin(outf); + + exit(0); +} diff --git a/src/mem.c b/src/mem.c new file mode 100644 index 0000000..bda43d7 --- /dev/null +++ b/src/mem.c @@ -0,0 +1,81 @@ +#include "all.h" + +/* Memory optimization: + * + * - replace alloced slots used only in + * load/store operations + * Assumption: all the accesses have the + * same size (this could be wrong...) + */ + +/* require use, maintains use counts */ +void +memopt(Fn *fn) +{ + Blk *b; + Ins *i, *l; + Tmp *t; + Use *u, *ue; + int a; + + b = fn->start; + for (i=b->ins; i-b->ins < b->nins; i++) { + if (OAlloc > i->op || i->op > OAlloc1) + continue; + assert(NAlign == 3); + assert(rtype(i->to) == RTmp); + t = &fn->tmp[i->to.val]; + for (u=t->use; u != &t->use[t->nuse]; u++) { + if (u->type != UIns) + goto NextIns; + l = u->u.ins; + if (!isload(l->op) + && (!isstore(l->op) || req(i->to, l->arg[0]))) + goto NextIns; + } + /* get rid of the alloc and replace uses */ + *i = (Ins){.op = ONop}; + t->ndef--; + ue = &t->use[t->nuse]; + for (u=t->use; u!=ue; u++) { + l = u->u.ins; + if (isstore(l->op)) { + if (l->op == OStores) + l->cls = Kd; + else if (l->op == OStored) + l->cls = Kd; + else if (l->op == OStorel) + l->cls = Kl; + else + l->cls = Kw; + l->op = OCopy; + l->to = l->arg[1]; + l->arg[1] = R; + t->nuse--; + t->ndef++; + } else + /* try to turn loads into copies so we + * can eliminate them later */ + switch(l->op) { + case OLoad: + l->op = OCopy; + break; + case OLoadsw: + case OLoaduw: + l->cls = Kw; + l->op = OCopy; + break; + default: + /* keep l->cls */ + a = l->op - OLoadsw; + l->op = OExtsw + a; + break; + } + } + NextIns:; + } + if (debug['M']) { + fprintf(stderr, "\n> After memory optimization:\n"); + printfn(fn, stderr); + } +} diff --git a/src/parse.c b/src/parse.c new file mode 100644 index 0000000..903e909 --- /dev/null +++ b/src/parse.c @@ -0,0 +1,1081 @@ +#include "all.h" +#include <ctype.h> +#include <stdarg.h> + +enum { + Kx = -1, /* Invalid operand */ + Km = Kl, /* Memory pointer (for x64) */ +}; + +OpDesc opdesc[NOp] = { +#define A(a,b,c,d) {[Kw]=K##a, [Kl]=K##b, [Ks]=K##c, [Kd]=K##d} + + /* NAME NM ARGCLS0 ARGCLS1 SF LF */ + [OAdd] = { "add", 2, {A(w,l,s,d), A(w,l,s,d)}, 1, 0 }, + [OSub] = { "sub", 2, {A(w,l,s,d), A(w,l,s,d)}, 1, 0 }, + [ODiv] = { "div", 2, {A(w,l,s,d), A(w,l,s,d)}, 0, 0 }, + [ORem] = { "rem", 2, {A(w,l,x,x), A(w,l,x,x)}, 0, 0 }, + [OUDiv] = { "udiv", 2, {A(w,l,s,d), A(w,l,s,d)}, 0, 0 }, + [OURem] = { "urem", 2, {A(w,l,x,x), A(w,l,x,x)}, 0, 0 }, + [OMul] = { "mul", 2, {A(w,l,s,d), A(w,l,s,d)}, 0, 0 }, + [OAnd] = { "and", 2, {A(w,l,s,d), A(w,l,s,d)}, 1, 0 }, + [OOr] = { "or", 2, {A(w,l,s,d), A(w,l,s,d)}, 1, 0 }, + [OXor] = { "xor", 2, {A(w,l,s,d), A(w,l,s,d)}, 1, 0 }, + [OSar] = { "sar", 1, {A(w,l,x,x), A(w,w,x,x)}, 1, 0 }, + [OShr] = { "shr", 1, {A(w,l,x,x), A(w,w,x,x)}, 1, 0 }, + [OShl] = { "shl", 1, {A(w,l,x,x), A(w,w,x,x)}, 1, 0 }, + [OStored] = { "stored", 0, {A(d,d,d,d), A(m,m,m,m)}, 0, 1 }, + [OStores] = { "stores", 0, {A(s,s,s,s), A(m,m,m,m)}, 0, 1 }, + [OStorel] = { "storel", 0, {A(l,l,l,l), A(m,m,m,m)}, 0, 1 }, + [OStorew] = { "storew", 0, {A(w,w,w,w), A(m,m,m,m)}, 0, 1 }, + [OStoreh] = { "storeh", 0, {A(w,w,w,w), A(m,m,m,m)}, 0, 1 }, + [OStoreb] = { "storeb", 0, {A(w,w,w,w), A(m,m,m,m)}, 0, 1 }, + [OLoad] = { "load", 0, {A(m,m,m,m), A(x,x,x,x)}, 0, 1 }, + [OLoadsw] = { "loadsw", 0, {A(m,m,x,x), A(x,x,x,x)}, 0, 1 }, + [OLoaduw] = { "loaduw", 0, {A(m,m,x,x), A(x,x,x,x)}, 0, 1 }, + [OLoadsh] = { "loadsh", 0, {A(m,m,x,x), A(x,x,x,x)}, 0, 1 }, + [OLoaduh] = { "loaduh", 0, {A(m,m,x,x), A(x,x,x,x)}, 0, 1 }, + [OLoadsb] = { "loadsb", 0, {A(m,m,x,x), A(x,x,x,x)}, 0, 1 }, + [OLoadub] = { "loadub", 0, {A(m,m,x,x), A(x,x,x,x)}, 0, 1 }, + [OExtsw] = { "extsw", 0, {A(w,w,w,w), A(x,x,x,x)}, 0, 1 }, + [OExtuw] = { "extuw", 0, {A(w,w,w,w), A(x,x,x,x)}, 0, 1 }, + [OExtsh] = { "extsh", 0, {A(w,w,w,w), A(x,x,x,x)}, 0, 1 }, + [OExtuh] = { "extuh", 0, {A(w,w,w,w), A(x,x,x,x)}, 0, 1 }, + [OExtsb] = { "extsb", 0, {A(w,w,w,w), A(x,x,x,x)}, 0, 1 }, + [OExtub] = { "extub", 0, {A(w,w,w,w), A(x,x,x,x)}, 0, 1 }, + [OExts] = { "exts", 0, {A(w,w,w,w), A(x,x,x,x)}, 0, 1 }, + [OTruncd] = { "truncd", 0, {A(d,d,d,d), A(x,x,x,x)}, 0, 1 }, + [OFtosi] = { "ftosi", 0, {A(s,d,x,x), A(x,x,x,x)}, 0, 1 }, + [OSitof] = { "sitof", 0, {A(x,x,w,l), A(x,x,x,x)}, 0, 1 }, + [OCast] = { "cast", 0, {A(s,d,w,l), A(x,x,x,x)}, 0, 1 }, + [OCopy] = { "copy", 1, {A(w,l,s,d), A(x,x,x,x)}, 0, 1 }, + [ONop] = { "nop", 0, {A(x,x,x,x), A(x,x,x,x)}, 0, 1 }, + [OSwap] = { "swap", 2, {A(w,l,s,d), A(w,l,s,d)}, 0, 0 }, + [OSign] = { "sign", 0, {A(w,l,x,x), A(x,x,x,x)}, 0, 0 }, + [OSAlloc] = { "salloc", 0, {A(x,l,x,x), A(x,x,x,x)}, 0, 0 }, + [OXDiv] = { "xdiv", 1, {A(w,l,x,x), A(x,x,x,x)}, 0, 0 }, + [OXCmp] = { "xcmp", 1, {A(w,l,s,d), A(w,l,s,d)}, 1, 0 }, + [OXTest] = { "xtest", 1, {A(w,l,x,x), A(w,l,x,x)}, 1, 0 }, + [OAddr] = { "addr", 0, {A(m,m,x,x), A(x,x,x,x)}, 0, 1 }, + [OPar] = { "parn", 0, {A(x,x,x,x), A(x,x,x,x)}, 0, 0 }, + [OParc] = { "parc", 0, {A(x,x,x,x), A(x,x,x,x)}, 0, 0 }, + [OArg] = { "arg", 0, {A(x,x,x,x), A(x,x,x,x)}, 0, 0 }, + [OArgc] = { "argc", 0, {A(x,x,x,x), A(x,x,x,x)}, 0, 0 }, + [OCall] = { "call", 0, {A(m,m,m,m), A(x,x,x,x)}, 0, 0 }, + [OXSetnp] = { "xsetnp", 0, {A(x,x,x,x), A(x,x,x,x)}, 0, 0 }, + [OXSetp] = { "xsetp", 0, {A(x,x,x,x), A(x,x,x,x)}, 0, 0 }, + [OAlloc] = { "alloc4", 1, {A(l,l,l,l), A(x,x,x,x)}, 0, 0 }, + [OAlloc+1] = { "alloc8", 1, {A(l,l,l,l), A(x,x,x,x)}, 0, 0 }, + [OAlloc+2] = { "alloc16", 1, {A(l,l,l,l), A(x,x,x,x)}, 0, 0 }, +#define X(c) \ + [OCmpw+IC##c] = { "c" #c "w", 0, {A(w,w,x,x), A(w,w,x,x)}, 1, 0 }, \ + [OCmpl+IC##c] = { "c" #c "l", 0, {A(l,l,x,x), A(l,l,x,x)}, 1, 0 }, \ + [OXSet+IC##c] = { "xset" #c, 0, {A(x,x,x,x), A(x,x,x,x)}, 0, 1 }, + ICMPS(X) +#undef X +#define X(c) \ + [OCmps+FC##c] = { "c" #c "s", 0, {A(s,s,x,x), A(s,s,x,x)}, 1, 0 }, \ + [OCmpd+FC##c] = { "c" #c "d", 0, {A(d,d,x,x), A(d,d,x,x)}, 1, 0 }, + FCMPS(X) +#undef X + +}; +#undef A + +typedef enum { + PXXX, + PLbl, + PPhi, + PIns, + PEnd, +} PState; + +enum { + TXXX = NPubOp, + TCall, + TPhi, + TJmp, + TJnz, + TRet, + TFunc, + TType, + TData, + TAlign, + TL, + TW, + TH, + TB, + TD, + TS, + TZ, + + TInt, + TFlts, + TFltd, + TTmp, + TLbl, + TGlo, + TTyp, + TStr, + + TPlus, + TEq, + TComma, + TLParen, + TRParen, + TLBrace, + TRBrace, + TNL, + TEOF, +}; + + +static FILE *inf; +static char *inpath; +static int thead; +static struct { + char chr; + double fltd; + float flts; + int64_t num; + char *str; +} tokval; +static int lnum; + +static Tmp *tmp; +static Con *con; +static int ntmp; +static int ncon; +static Phi **plink; +static Blk **bmap; +static Blk *curb; +static Blk **blink; +static int nblk; +static int rcls; +static int ntyp; + + +void +err(char *s, ...) +{ + char buf[100], *p, *end; + va_list ap; + + p = buf; + end = buf + sizeof(buf); + + va_start(ap, s); + p += snprintf(p, end - p, "%s:%d: ", inpath, lnum); + p += vsnprintf(p, end - p, s, ap); + va_end(ap); + + diag(buf); +} + +static int +lex() +{ + static struct { + char *str; + int tok; + } tmap[] = { + { "call", TCall }, + { "phi", TPhi }, + { "jmp", TJmp }, + { "jnz", TJnz }, + { "ret", TRet }, + { "function", TFunc }, + { "type", TType }, + { "data", TData }, + { "align", TAlign }, + { "l", TL }, + { "w", TW }, + { "h", TH }, + { "b", TB }, + { "d", TD }, + { "s", TS }, + { "z", TZ }, + { "loadw", OLoad }, /* for convenience */ + { "loadl", OLoad }, + { "loads", OLoad }, + { "loadd", OLoad }, + { "alloc1", OAlloc }, + { "alloc2", OAlloc }, + { 0, TXXX } + }; + static char tok[NString]; + int c, i; + int t; + + do + c = fgetc(inf); + while (isblank(c)); + t = TXXX; + tokval.chr = c; + switch (c) { + case EOF: + return TEOF; + case ',': + return TComma; + case '(': + return TLParen; + case ')': + return TRParen; + case '{': + return TLBrace; + case '}': + return TRBrace; + case '=': + return TEq; + case '+': + return TPlus; + case 's': + if (fscanf(inf, "_%f", &tokval.flts) != 1) + break; + return TFlts; + case 'd': + if (fscanf(inf, "_%lf", &tokval.fltd) != 1) + break; + return TFltd; + case '%': + t = TTmp; + goto Alpha; + case '@': + t = TLbl; + goto Alpha; + case '$': + t = TGlo; + goto Alpha; + case ':': + t = TTyp; + goto Alpha; + case '#': + while (fgetc(inf) != '\n') + ; + case '\n': + lnum++; + return TNL; + } + if (isdigit(c) || c == '-' || c == '+') { + ungetc(c, inf); + if (fscanf(inf, "%"SCNd64, &tokval.num) != 1) + err("invalid integer literal"); + return TInt; + } + if (c == '"') { + tokval.str = vnew(0, 1); + for (i=0;; i++) { + c = fgetc(inf); + vgrow(&tokval.str, i+1); + if (c == '"') + if (!i || tokval.str[i-1] != '\\') { + tokval.str[i] = 0; + return TStr; + } + tokval.str[i] = c; + } + } + if (0) +Alpha: c = fgetc(inf); + if (!isalpha(c) && c != '.' && c != '_') + err("lexing failure: invalid character %c (%d)", c, c); + i = 0; + do { + if (i >= NString-1) + err("identifier too long"); + tok[i++] = c; + c = fgetc(inf); + } while (isalpha(c) || c == '$' || c == '.' || c == '_' || isdigit(c)); + tok[i] = 0; + ungetc(c, inf); + tokval.str = tok; + if (t != TXXX) { + return t; + } + for (i=0; i<NPubOp; i++) + if (opdesc[i].name) + if (strcmp(tok, opdesc[i].name) == 0) + return i; + for (i=0; tmap[i].str; i++) + if (strcmp(tok, tmap[i].str) == 0) + return tmap[i].tok; + err("unknown keyword %s", tokval.str); + return TXXX; +} + +static int +peek() +{ + if (thead == TXXX) + thead = lex(); + return thead; +} + +static int +next() +{ + int t; + + t = peek(); + thead = TXXX; + return t; +} + +static int +nextnl() +{ + int t; + + while ((t = next()) == TNL) + ; + return t; +} + +static void +expect(int t) +{ + static char *ttoa[] = { + [TLbl] = "label", + [TComma] = ",", + [TEq] = "=", + [TNL] = "newline", + [TLParen] = "(", + [TRParen] = ")", + [TLBrace] = "{", + [TRBrace] = "}", + [TEOF] = 0, + }; + char buf[128], *s1, *s2; + int t1; + + t1 = next(); + if (t == t1) + return; + s1 = ttoa[t] ? ttoa[t] : "??"; + s2 = ttoa[t1] ? ttoa[t1] : "??"; + sprintf(buf, "%s expected, got %s instead", s1, s2); + err(buf); +} + +static Ref +tmpref(char *v) +{ + int t; + + for (t=Tmp0; t<ntmp; t++) + if (strcmp(v, tmp[t].name) == 0) + return TMP(t); + vgrow(&tmp, ++ntmp); + strcpy(tmp[t].name, v); + return TMP(t); +} + +static Ref +parseref() +{ + Con c; + int i; + + memset(&c, 0, sizeof c); + switch (next()) { + case TTmp: + return tmpref(tokval.str); + case TInt: + c.type = CBits; + c.bits.i = tokval.num; + goto Look; + case TFlts: + c.type = CBits; + c.bits.s = tokval.flts; + c.flt = 1; + goto Look; + case TFltd: + c.type = CBits; + c.bits.d = tokval.fltd; + c.flt = 2; + goto Look; + case TGlo: + c.type = CAddr; + strcpy(c.label, tokval.str); + Look: + for (i=0; i<ncon; i++) + if (con[i].type == c.type + && con[i].bits.i == c.bits.i + && strcmp(con[i].label, c.label) == 0) + return CON(i); + vgrow(&con, ++ncon); + con[i] = c; + return CON(i); + default: + return R; + } +} + +static int +parsecls(int *tyn) +{ + int i; + + switch (next()) { + default: + err("invalid class specifier"); + case TTyp: + for (i=0; i<ntyp; i++) + if (strcmp(tokval.str, typ[i].name) == 0) { + *tyn = i; + return 4; + } + err("undefined type"); + case TW: + return Kw; + case TL: + return Kl; + case TS: + return Ks; + case TD: + return Kd; + } +} + +static void +parserefl(int arg) +{ + int k, t, ty; + Ref r; + + expect(TLParen); + if (peek() == TRParen) { + next(); + return; + } + for (;;) { + if (curi - insb >= NIns) + err("too many instructions (1)"); + k = parsecls(&ty); + r = parseref(); + if (req(r, R)) + err("invalid reference argument"); + if (!arg && rtype(r) != RTmp) + err("invalid function parameter"); + if (k == 4) + if (arg) + *curi = (Ins){OArgc, R, {TYPE(ty), r}, Kl}; + else + *curi = (Ins){OParc, r, {TYPE(ty)}, Kl}; + else + if (arg) + *curi = (Ins){OArg, R, {r}, k}; + else + *curi = (Ins){OPar, r, {R}, k}; + curi++; + t = next(); + if (t == TRParen) + break; + if (t != TComma) + err(", or ) expected"); + } +} + +static Blk * +findblk(char *name) +{ + int i; + + for (i=0; i<nblk; i++) + if (strcmp(bmap[i]->name, name) == 0) + return bmap[i]; + vgrow(&bmap, ++nblk); + bmap[i] = blknew(); + strcpy(bmap[i]->name, name); + return bmap[i]; +} + +static void +closeblk() +{ + curb->nins = curi - insb; + idup(&curb->ins, insb, curb->nins); + blink = &curb->link; + curi = insb; +} + +static PState +parseline(PState ps) +{ + Ref arg[NPred] = {R}; + Blk *blk[NPred]; + Phi *phi; + Ref r; + Blk *b; + int t, op, i, k, ty; + + t = nextnl(); + if (ps == PLbl && t != TLbl && t != TRBrace) + err("label or } expected"); + switch (t) { + default: + if (isstore(t)) { + /* operations without result */ + r = R; + k = 0; + op = t; + goto DoOp; + } + err("label, instruction or jump expected"); + case TRBrace: + return PEnd; + case TTmp: + break; + case TLbl: + b = findblk(tokval.str); + if (b->jmp.type != JXXX) + err("multiple definitions of block"); + if (curb && curb->jmp.type == JXXX) { + closeblk(); + curb->jmp.type = JJmp; + curb->s1 = b; + } + *blink = b; + curb = b; + plink = &curb->phi; + expect(TNL); + return PPhi; + case TRet: + curb->jmp.type = (int[]){ + JRetw, JRetl, + JRets, JRetd, + JRetc, JRet0 + }[rcls]; + if (rcls < 5) { + r = parseref(); + if (req(r, R)) + err("return value expected"); + curb->jmp.arg = r; + } + goto Close; + case TJmp: + curb->jmp.type = JJmp; + goto Jump; + case TJnz: + curb->jmp.type = JJnz; + r = parseref(); + if (req(r, R)) + err("invalid argument for jnz jump"); + curb->jmp.arg = r; + expect(TComma); + Jump: + expect(TLbl); + curb->s1 = findblk(tokval.str); + if (curb->jmp.type != JJmp) { + expect(TComma); + expect(TLbl); + curb->s2 = findblk(tokval.str); + } + Close: + expect(TNL); + closeblk(); + return PLbl; + } + r = tmpref(tokval.str); + expect(TEq); + k = parsecls(&ty); + op = next(); +DoOp: + if (op == TPhi) { + if (ps != PPhi) + err("unexpected phi instruction"); + op = -1; + } + if (op == TCall) { + arg[0] = parseref(); + parserefl(1); + expect(TNL); + op = OCall; + if (k == 4) { + k = Kl; + arg[1] = TYPE(ty); + } else + arg[1] = R; + goto Ins; + } + if (k == 4) + err("size class must be w, l, s, or d"); + if (op >= NPubOp) + err("invalid instruction"); + i = 0; + if (peek() != TNL) + for (;;) { + if (i == NPred) + err("too many arguments"); + if (op == -1) { + expect(TLbl); + blk[i] = findblk(tokval.str); + } + arg[i] = parseref(); + if (req(arg[i], R)) + err("invalid instruction argument"); + i++; + t = peek(); + if (t == TNL) + break; + if (t != TComma) + err(", or end of line expected"); + next(); + } + next(); + if (op != -1) { + Ins: + if (curi - insb >= NIns) + err("too many instructions (2)"); + curi->op = op; + curi->cls = k; + curi->to = r; + curi->arg[0] = arg[0]; + curi->arg[1] = arg[1]; + curi++; + return PIns; + } else { + phi = alloc(sizeof *phi); + phi->to = r; + phi->cls = k; + memcpy(phi->arg, arg, i * sizeof arg[0]); + memcpy(phi->blk, blk, i * sizeof blk[0]); + phi->narg = i; + *plink = phi; + plink = &phi->link; + return PPhi; + } +} + +static Fn * +parsefn() +{ + PState ps; + Fn *fn; + + ntmp = Tmp0; + ncon = 1; /* first constant must be 0 */ + curb = 0; + nblk = 0; + curi = insb; + tmp = vnew(ntmp, sizeof tmp[0]); + con = vnew(ncon, sizeof con[0]); + bmap = vnew(nblk, sizeof bmap[0]); + con[0].type = CBits; + fn = alloc(sizeof *fn); + blink = &fn->start; + fn->retty = -1; + if (peek() != TGlo) + rcls = parsecls(&fn->retty); + else + rcls = 5; + if (next() != TGlo) + err("function name expected"); + strcpy(fn->name, tokval.str); + parserefl(0); + if (nextnl() != TLBrace) + err("function body must start with {"); + ps = PLbl; + do + ps = parseline(ps); + while (ps != PEnd); + if (!curb) + err("empty file"); + if (curb->jmp.type == JXXX) + err("last block misses jump"); + fn->tmp = tmp; + fn->con = con; + fn->mem = vnew(0, sizeof fn->mem[0]); + fn->ntmp = ntmp; + fn->ncon = ncon; + fn->nmem = 0; + fn->nblk = nblk; + fn->rpo = 0; + return fn; +} + +static void +parsetyp() +{ + Typ *ty; + int t, n, sz, al, s, a, c, flt; + + if (ntyp >= NTyp) + err("too many type definitions"); + ty = &typ[ntyp++]; + ty->align = -1; + if (nextnl() != TTyp || nextnl() != TEq) + err("type name, then = expected"); + strcpy(ty->name, tokval.str); + t = nextnl(); + if (t == TAlign) { + if (nextnl() != TInt) + err("alignment expected"); + for (al=0; tokval.num /= 2; al++) + ; + ty->align = al; + t = nextnl(); + } + if (t != TLBrace) + err("type body must start with {"); + t = nextnl(); + if (t == TInt) { + ty->dark = 1; + ty->size = tokval.num; + if (ty->align == -1) + err("dark types need alignment"); + t = nextnl(); + } else { + ty->dark = 0; + n = -1; + sz = 0; + al = 0; + for (;;) { + flt = 0; + switch (t) { + default: err("invalid size specifier %c", tokval.chr); + case TD: flt = 1; + case TL: s = 8; a = 3; break; + case TS: flt = 1; + case TW: s = 4; a = 2; break; + case TH: s = 2; a = 1; break; + case TB: s = 1; a = 0; break; + } + if (a > al) + al = a; + if ((a = sz & (s-1))) { + a = s - a; + if (++n < NSeg) { + /* padding segment */ + ty->seg[n].ispad = 1; + ty->seg[n].len = a; + } + } + t = nextnl(); + if (t == TInt) { + c = tokval.num; + t = nextnl(); + } else + c = 1; + while (c-- > 0) { + if (++n < NSeg) { + ty->seg[n].isflt = flt; + ty->seg[n].ispad = 0; + ty->seg[n].len = s; + } + sz += a + s; + } + if (t != TComma) + break; + t = nextnl(); + } + if (++n >= NSeg) + ty->dark = 1; + else + ty->seg[n].len = 0; + if (ty->align == -1) + ty->align = al; + else + al = ty->align; + a = (1 << al) - 1; + ty->size = (sz + a) & ~a; + } + if (t != TRBrace) + err("expected closing }"); +} + +static void +parsedatref(Dat *d) +{ + int t; + + d->isref = 1; + d->u.ref.nam = tokval.str; + d->u.ref.off = 0; + t = peek(); + if (t == TPlus) { + next(); + if (next() != TInt) + err("invalid token after offset in ref"); + d->u.ref.off = tokval.num; + } +} + +static void +parsedatstr(Dat *d) +{ + d->isstr = 1; + d->u.str = tokval.str; +} + +static void +parsedat(void cb(Dat *)) +{ + char s[NString]; + int t; + Dat d; + + d.type = DStart; + d.isstr = 0; + d.isref = 0; + cb(&d); + if (nextnl() != TGlo || nextnl() != TEq) + err("data name, then = expected"); + strcpy(s, tokval.str); + t = nextnl(); + if (t == TAlign) { + if (nextnl() != TInt) + err("alignment expected"); + d.type = DAlign; + d.u.num = tokval.num; + cb(&d); + t = nextnl(); + } + d.type = DName; + d.u.str = s; + cb(&d); + + if (t != TLBrace) + err("expected data contents in { .. }"); + for (;;) { + switch (nextnl()) { + default: err("invalid size specifier %c in data", tokval.chr); + case TRBrace: goto Done; + case TL: d.type = DL; break; + case TW: d.type = DW; break; + case TH: d.type = DH; break; + case TB: d.type = DB; break; + case TS: d.type = DW; break; + case TD: d.type = DL; break; + case TZ: d.type = DZ; break; + } + t = nextnl(); + do { + d.isref = 0; + d.isstr = 0; + memset(&d.u, 0, sizeof d.u); + if (t == TFlts) + d.u.flts = tokval.flts; + else if (t == TFltd) + d.u.fltd = tokval.fltd; + else if (t == TInt) + d.u.num = tokval.num; + else if (t == TGlo) + parsedatref(&d); + else if (t == TStr) + parsedatstr(&d); + else + err("constant literal expected"); + cb(&d); + t = nextnl(); + } while (t == TInt || t == TFlts || t == TFltd); + if (t == TRBrace) + break; + if (t != TComma) + err(", or } expected"); + } +Done: + d.type = DEnd; + cb(&d); +} + +void +parse(FILE *f, char *path, void data(Dat *), void func(Fn *)) +{ + inf = f; + inpath = path; + lnum = 1; + thead = TXXX; + ntyp = 0; + for (;;) + switch (nextnl()) { + case TFunc: + func(parsefn()); + break; + case TType: + parsetyp(); + break; + case TData: + parsedat(data); + break; + case TEOF: + return; + default: + err("top-level definition expected"); + break; + } +} + +static void +printcon(Con *c, FILE *f) +{ + switch (c->type) { + case CUndef: + break; + case CAddr: + fprintf(f, "$%s", c->label); + if (c->bits.i) + fprintf(f, "%+"PRIi64, c->bits.i); + break; + case CBits: + if (c->flt == 1) + fprintf(f, "s_%f", c->bits.s); + else if (c->flt == 2) + fprintf(f, "d_%lf", c->bits.d); + else + fprintf(f, "%"PRIi64, c->bits.i); + break; + } +} + +void +printref(Ref r, Fn *fn, FILE *f) +{ + int i; + Mem *m; + + switch (rtype(r)) { + case RTmp: + if (r.val < Tmp0) + fprintf(f, "R%d", r.val); + else + fprintf(f, "%%%s", fn->tmp[r.val].name); + break; + case RCon: + printcon(&fn->con[r.val], f); + break; + case RSlot: + fprintf(f, "S%d", r.val); + break; + case RACall: + fprintf(f, "%03x", r.val & AMask); + break; + case RAType: + fprintf(f, ":%s", typ[r.val & AMask].name); + break; + case RAMem: + i = 0; + m = &fn->mem[r.val & AMask]; + fputc('[', f); + if (m->offset.type != CUndef) { + printcon(&m->offset, f); + i = 1; + } + if (!req(m->base, R)) { + if (i) + fprintf(f, " + "); + printref(m->base, fn, f); + i = 1; + } + if (!req(m->index, R)) { + if (i) + fprintf(f, " + "); + fprintf(f, "%d * ", m->scale); + printref(m->index, fn, f); + } + fputc(']', f); + break; + } +} + +void +printfn(Fn *fn, FILE *f) +{ + static char *jtoa[NJmp] = { + [JRet0] = "ret", + [JRetw] = "retw", + [JRetl] = "retl", + [JRetc] = "retc", + [JRets] = "rets", + [JRetd] = "retd", + [JJnz] = "jnz", + [JXJnp] = "xjnp", + [JXJp] = "xjp", + #define X(c) [JXJc+IC##c] = "xj" #c, + ICMPS(X) + #undef X + }; + static char prcls[NOp] = { + [OArg] = 1, + [OSwap] = 1, + [OXCmp] = 1, + [OXTest] = 1, + [OXDiv] = 1, + [OXIDiv] = 1, + }; + static char ktoc[] = "wlsd"; + Blk *b; + Phi *p; + Ins *i; + uint n; + + fprintf(f, "function $%s() {\n", fn->name); + for (b=fn->start; b; b=b->link) { + fprintf(f, "@%s\n", b->name); + for (p=b->phi; p; p=p->link) { + fprintf(f, "\t"); + printref(p->to, fn, f); + fprintf(f, " =%c phi ", ktoc[p->cls]); + assert(p->narg); + for (n=0;; n++) { + fprintf(f, "@%s ", p->blk[n]->name); + printref(p->arg[n], fn, f); + if (n == p->narg-1) { + fprintf(f, "\n"); + break; + } else + fprintf(f, ", "); + } + } + for (i=b->ins; i-b->ins < b->nins; i++) { + fprintf(f, "\t"); + if (!req(i->to, R)) { + printref(i->to, fn, f); + fprintf(f, " =%c ", ktoc[i->cls]); + } + assert(opdesc[i->op].name); + fprintf(f, "%s", opdesc[i->op].name); + if (req(i->to, R) && prcls[i->op]) + fputc(ktoc[i->cls], f); + if (!req(i->arg[0], R)) { + fprintf(f, " "); + printref(i->arg[0], fn, f); + } + if (!req(i->arg[1], R)) { + fprintf(f, ", "); + printref(i->arg[1], fn, f); + } + fprintf(f, "\n"); + } + switch (b->jmp.type) { + case JRet0: + case JRetw: + case JRetl: + case JRets: + case JRetd: + case JRetc: + fprintf(f, "\t%s", jtoa[b->jmp.type]); + if (b->jmp.type != JRet0 || !req(b->jmp.arg, R)) { + fprintf(f, " "); + printref(b->jmp.arg, fn, f); + } + if (b->jmp.type == JRetc) + fprintf(f, ", :%s", typ[fn->retty].name); + fprintf(f, "\n"); + break; + case JJmp: + if (b->s1 != b->link) + fprintf(f, "\tjmp @%s\n", b->s1->name); + break; + default: + fprintf(f, "\t%s ", jtoa[b->jmp.type]); + if (b->jmp.type == JJnz) { + printref(b->jmp.arg, fn, f); + fprintf(f, ", "); + } + fprintf(f, "@%s, @%s\n", b->s1->name, b->s2->name); + break; + } + } + fprintf(f, "}\n"); +} diff --git a/src/rega.c b/src/rega.c new file mode 100644 index 0000000..7f8edcf --- /dev/null +++ b/src/rega.c @@ -0,0 +1,598 @@ +#include "all.h" + +#ifdef TEST_PMOV + #undef assert + #define assert(x) assert_test(#x, x) +#endif + +typedef struct RMap RMap; + +struct RMap { + int t[NIReg+NFReg]; + int r[NIReg+NFReg]; + BSet b[1]; + int n; +}; + +static bits regu; /* registers used */ +static Tmp *tmp; /* function temporaries */ +static Mem *mem; /* function mem references */ +static struct { + Ref src, dst; + int cls; +} *pm; /* parallel move constructed */ +static int cpm, npm; /* capacity and size of pm */ + +static int * +hint(int t) +{ + return &tmp[phicls(t, tmp)].hint.r; +} + +static void +sethint(int t, int r) +{ + bits m; + + m = tmp[phicls(t, tmp)].hint.m; + if (*hint(t) == -1) + if (!(BIT(r) & m)) + *hint(t) = r; +} + +static void +rcopy(RMap *ma, RMap *mb) +{ + memcpy(ma->t, mb->t, sizeof ma->t); + memcpy(ma->r, mb->r, sizeof ma->r); + bscopy(ma->b, mb->b); + ma->n = mb->n; +} + +static int +rfind(RMap *m, int t) +{ + int i; + + for (i=0; i<m->n; i++) + if (m->t[i] == t) + return m->r[i]; + return -1; +} + +static Ref +rref(RMap *m, int t) +{ + int r, s; + + r = rfind(m, t); + if (r == -1) { + s = tmp[t].slot; + assert(s != -1 && "should have spilled"); + return SLOT(s); + } else + return TMP(r); +} + +static void +radd(RMap *m, int t, int r) +{ + assert((t >= Tmp0 || t == r) && "invalid temporary"); + assert(((RAX <= r && r < RAX + NIReg) || (XMM0 <= r && r < XMM0 + NFReg)) && "invalid register"); + assert(!bshas(m->b, t) && "temporary has mapping"); + assert(!bshas(m->b, r) && "register already allocated"); + assert(m->n <= NIReg+NFReg && "too many mappings"); + bsset(m->b, t); + bsset(m->b, r); + m->t[m->n] = t; + m->r[m->n] = r; + m->n++; + regu |= BIT(r); +} + +static Ref +ralloc(RMap *m, int t) +{ + bits regs; + int r, r0, r1; + + if (t < Tmp0) { + assert(bshas(m->b, t)); + return TMP(t); + } + if (bshas(m->b, t)) { + r = rfind(m, t); + assert(r != -1); + return TMP(r); + } + r = *hint(t); + if (r == -1 || bshas(m->b, r)) { + regs = tmp[phicls(t, tmp)].hint.m; + regs |= m->b->t[0]; + switch (KBASE(tmp[t].cls)) { + case 0: + r0 = RAX; + r1 = RAX + NIReg; + break; + case 1: + r0 = XMM0; + r1 = XMM0 + NFReg; + break; + } + for (r=r0; r<r1; r++) + if (!(regs & BIT(r))) + goto Found; + for (r=r0; r<r1; r++) + if (!bshas(m->b, r)) + goto Found; + diag("rega: no more regs"); + } +Found: + radd(m, t, r); + sethint(t, r); + return TMP(r); +} + +static int +rfree(RMap *m, int t) +{ + int i, r; + + if (!bshas(m->b, t)) + return -1; + for (i=0; m->t[i] != t; i++) + assert(i+1 < m->n); + r = m->r[i]; + bsclr(m->b, t); + bsclr(m->b, r); + m->n--; + memmove(&m->t[i], &m->t[i+1], (m->n-i) * sizeof m->t[0]); + memmove(&m->r[i], &m->r[i+1], (m->n-i) * sizeof m->r[0]); + return r; +} + +static void +mdump(RMap *m) +{ + int i; + + for (i=0; i<m->n; i++) + fprintf(stderr, " (%s, R%d)", + tmp[m->t[i]].name, + m->r[i]); + fprintf(stderr, "\n"); +} + +static void +pmadd(Ref src, Ref dst, int k) +{ + if (npm == cpm) { + cpm = cpm * 2 + 16; + pm = realloc(pm, cpm * sizeof pm[0]); + if (!pm) + diag("pmadd: out of memory"); + } + pm[npm].src = src; + pm[npm].dst = dst; + pm[npm].cls = k; + npm++; +} + +enum PMStat { ToMove, Moving, Moved }; + +static Ref +pmrec(enum PMStat *status, int i, int *k) +{ + Ref swp, swp1; + int j, k1; + + /* note, this routine might emit + * too many large instructions: + * + * , x -- x + * x -- x -- x | + * ` x -- x + * + * if only the first move is wide + * the whole cycle will be wide, + * this is safe but not necessary + */ + + if (req(pm[i].src, pm[i].dst)) + return R; + status[i] = Moving; + assert(KBASE(*k) == KBASE(pm[i].cls)); + assert((Kw|1) == Kl && (Ks|1) == Kd); + *k |= KWIDE(pm[i].cls); /* see above */ + swp = R; + for (j=0; j<npm; j++) { + if (req(pm[j].src, pm[i].dst)) + switch (status[j]) { + case ToMove: + k1 = *k; + swp1 = pmrec(status, j, &k1); + if (!req(swp1, R)) { + assert(req(swp, R)); + swp = swp1; + *k = k1; + } + break; + case Moving: + assert(req(swp, R)); + swp = pm[i].dst; + break; + case Moved: + break; + } + } + status[i] = Moved; + if (req(swp, R)) { + *curi++ = (Ins){OCopy, pm[i].dst, {pm[i].src}, pm[i].cls}; + return R; + } else if (!req(swp, pm[i].src)) { + *curi++ = (Ins){OSwap, R, {pm[i].src, pm[i].dst}, *k}; + return swp; + } else + return R; + +} + +static void +pmgen() +{ + int i, k; + enum PMStat *status; + + status = alloc(npm * sizeof status[0]); + assert(!npm || status[npm-1] == ToMove); + curi = insb; + for (i=0; i<npm; i++) + if (status[i] == ToMove) { + k = pm[i].cls; + pmrec(status, i, &k); + } +} + +static void +move(int r, Ref to, RMap *m) +{ + int n, t, r1; + + r1 = req(to, R) ? -1 : rfree(m, to.val); + if (bshas(m->b, r) && r1 != r) { + /* r is used and not by to */ + for (n=0; m->r[n] != r; n++) + assert(n+1 < m->n); + t = m->t[n]; + rfree(m, t); + bsset(m->b, r); + ralloc(m, t); + bsclr(m->b, r); + } + t = req(to, R) ? r : to.val; + radd(m, t, r); +} + +static int +regcpy(Ins *i) +{ + return i->op == OCopy && isreg(i->arg[0]); +} + +static Ins * +dopm(Blk *b, Ins *i, RMap *m) +{ + RMap m0; + int n, r, r1, t, s; + Ins *i0, *i1, *ip, *ir; + bits def; + + m0 = *m; + i1 = ++i; + do { + i--; + move(i->arg[0].val, i->to, m); + } while (i != b->ins && regcpy(i-1)); + assert(m0.n <= m->n); + if (i != b->ins && (i-1)->op == OCall) { + def = retregs((i-1)->arg[1], 0); + for (r=0; r<NRSave; r++) + if (!(BIT(rsave[r]) & def)) + move(rsave[r], R, m); + } + for (npm=0, n=0; n<m->n; n++) { + t = m->t[n]; + s = tmp[t].slot; + r1 = m->r[n]; + r = rfind(&m0, t); + if (r != -1) + pmadd(TMP(r1), TMP(r), tmp[t].cls); + else if (s != -1) + pmadd(TMP(r1), SLOT(s), tmp[t].cls); + } + for (ip=i; ip<i1; ip++) { + if (!req(ip->to, R)) + rfree(m, ip->to.val); + r = ip->arg[0].val; + if (rfind(m, r) == -1) + radd(m, r, r); + } + pmgen(); +#ifdef TEST_PMOV + return 0; +#endif + n = b->nins - (i1 - i) + (curi - insb); + i0 = alloc(n * sizeof(Ins)); + ip = icpy(ip = i0, b->ins, i - b->ins); + ip = icpy(ir = ip, insb, curi - insb); + ip = icpy(ip, i1, &b->ins[b->nins] - i1); + b->nins = n; + b->ins = i0; + return ir; +} + +static int +prio(Ref r1, Ref r2) +{ + /* trivial heuristic to begin with, + * later we can use the distance to + * the definition instruction + */ + (void) r2; + return *hint(r1.val) != -1; +} + +static void +insert(Ref *r, Ref **rs, int p) +{ + int i; + + rs[i = p] = r; + while (i-- > 0 && prio(*r, *rs[i])) { + rs[i+1] = rs[i]; + rs[i] = r; + } +} + +static void +doblk(Blk *b, RMap *cur) +{ + int x, r, nr; + bits rs; + Ins *i; + Mem *m; + Ref *ra[4]; + + if (rtype(b->jmp.arg) == RTmp) + b->jmp.arg = ralloc(cur, b->jmp.arg.val); + else if (rtype(b->jmp.arg) == RACall) { + /* add return registers */ + rs = retregs(b->jmp.arg, 0); + for (r=0; rs; rs/=2, r++) + if (rs & 1) + radd(cur, r, r); + } + for (i=&b->ins[b->nins]; i!=b->ins;) { + switch ((--i)->op) { + case OCall: + rs = argregs(i->arg[1], 0); + for (r=0; r<NRSave; r++) + if (!(BIT(rsave[r]) & rs)) + rfree(cur, rsave[r]); + break; + case OCopy: + if (isreg(i->arg[0])) { + i = dopm(b, i, cur); + continue; + } + if (isreg(i->to)) + if (rtype(i->arg[0]) == RTmp) + sethint(i->arg[0].val, i->to.val); + /* fall through */ + default: + if (!req(i->to, R)) { + assert(rtype(i->to) == RTmp); + r = rfree(cur, i->to.val); + if (r == -1 && !isreg(i->to)) { + *i = (Ins){.op = ONop}; + continue; + } + if (i->to.val >= Tmp0) + i->to = TMP(r); + } + break; + } + for (x=0, nr=0; x<2; x++) + switch (rtype(i->arg[x])) { + case RAMem: + m = &mem[i->arg[x].val & AMask]; + if (rtype(m->base) == RTmp) + insert(&m->base, ra, nr++); + if (rtype(m->index) == RTmp) + insert(&m->index, ra, nr++); + break; + case RTmp: + insert(&i->arg[x], ra, nr++); + break; + } + for (r=0; r<nr; r++) + *ra[r] = ralloc(cur, ra[r]->val); + } +} + +/* register allocation + * depends on rpo, phi, cost, (and obviously spill) + */ +void +rega(Fn *fn) +{ + int j, n, t, r, r1, x, rl[Tmp0]; + Blk *b, *b1, *s, ***ps, *blist; + RMap *end, *beg, cur, old; + Ins *i; + Phi *p; + uint u; + Ref src, dst; + + /* 1. setup */ + regu = 0; + tmp = fn->tmp; + mem = fn->mem; + end = alloc(fn->nblk * sizeof end[0]); + beg = alloc(fn->nblk * sizeof beg[0]); + for (n=0; n<fn->nblk; n++) { + bsinit(end[n].b, fn->ntmp); + bsinit(beg[n].b, fn->ntmp); + } + bsinit(cur.b, fn->ntmp); + bsinit(old.b, fn->ntmp); + + for (t=Tmp0; t<fn->ntmp; t++) + *hint(t) = -1; + for (b=fn->start, i=b->ins; i-b->ins < b->nins; i++) + if (i->op != OCopy || !isreg(i->arg[0])) + break; + else { + assert(rtype(i->to) == RTmp); + sethint(i->to.val, i->arg[0].val); + } + + /* 2. assign registers following post-order */ + for (n=fn->nblk-1; n>=0; n--) { + b = fn->rpo[n]; + cur.n = 0; + bszero(cur.b); + for (x=0; x<2; x++) + for (t=Tmp0; t<fn->ntmp; t++) { + assert(bshas(b->out, t) || + !bshas(cur.b, t)); + if (bshas(b->out, t)) + if (!bshas(cur.b, t)) + if (x || (r=*hint(t)) != -1) + if (x || !bshas(cur.b, r)) + ralloc(&cur, t); + } + rcopy(&end[n], &cur); + doblk(b, &cur); + bscopy(b->in, cur.b); + for (p=b->phi; p; p=p->link) + if (rtype(p->to) == RTmp) { + bsclr(b->in, p->to.val); + /* heuristic 0: + * if the phi destination has an + * argument from a frequent block + * that was already allocated to + * 'r', use 'r' as the new hint + */ + memset(rl, 0, sizeof rl); + for (u=0; u<p->narg; u++) { + t = p->arg[u].val; + b1 = p->blk[u]; + if (rtype(p->arg[u]) == RTmp) + if ((r=rfind(&end[b1->id], t)) != -1) + rl[r] += b1->loop; + } + for (x=0, j=0; j<Tmp0; j++) + if (rl[j] > rl[x]) + x = j; + if (rl[x] >= b->loop) + *hint(p->to.val) = x; + } + if (b->npred > 1) { + /* heuristic 1: + * attempt to satisfy hints + * when it's simple and we have + * multiple predecessors + */ + rcopy(&old, &cur); + curi = &insb[NIns]; + for (j=0; j<old.n; j++) { + t = old.t[j]; + r = *hint(t); + r1 = rfind(&cur, t); + if (r != -1 && r != r1) + if (!bshas(cur.b, r)) { + rfree(&cur, t); + radd(&cur, t, r); + x = tmp[t].cls; + emit(OCopy, x, TMP(r1), TMP(r), R); + } + } + if ((j = &insb[NIns] - curi)) { + b->nins += j; + i = alloc(b->nins * sizeof(Ins)); + icpy(icpy(i, curi, j), b->ins, b->nins-j); + b->ins = i; + } + } + rcopy(&beg[n], &cur); + } + if (debug['R']) { + fprintf(stderr, "\n> Register mappings:\n"); + for (n=0; n<fn->nblk; n++) { + b = fn->rpo[n]; + fprintf(stderr, "\t%-10s beg", b->name); + mdump(&beg[n]); + fprintf(stderr, "\t end"); + mdump(&end[n]); + } + fprintf(stderr, "\n"); + } + + /* 3. compose glue code */ + blist = 0; + for (b=fn->start;; b=b->link) { + ps = (Blk**[3]){&b->s1, &b->s2, (Blk*[1]){0}}; + for (; (s=**ps); ps++) { + npm = 0; + for (p=s->phi; p; p=p->link) { + dst = p->to; + assert(rtype(dst)==RSlot || rtype(dst)==RTmp); + if (rtype(dst) == RTmp) { + r = rfind(&beg[s->id], dst.val); + if (r == -1) + continue; + dst = TMP(r); + } + for (u=0; p->blk[u]!=b; u++) + assert(u+1 < p->narg); + src = p->arg[u]; + if (rtype(src) == RTmp) + src = rref(&end[b->id], src.val); + pmadd(src, dst, p->cls); + } + for (t=Tmp0; t<fn->ntmp; t++) + if (bshas(s->in, t)) { + src = rref(&end[b->id], t); + dst = rref(&beg[s->id], t); + pmadd(src, dst, tmp[t].cls); + } + pmgen(); + if (curi == insb) + continue; + b1 = blknew(); + b1->loop = (b->loop+s->loop) / 2; + b1->link = blist; + blist = b1; + fn->nblk++; + sprintf(b1->name, "%s_%s", b->name, s->name); + b1->nins = curi - insb; + idup(&b1->ins, insb, b1->nins); + b1->jmp.type = JJmp; + b1->s1 = s; + **ps = b1; + } + if (!b->link) { + b->link = blist; + break; + } + } + for (b=fn->start; b; b=b->link) + b->phi = 0; + fn->reg = regu; + + if (debug['R']) { + fprintf(stderr, "\n> After register allocation:\n"); + printfn(fn, stderr); + } +} diff --git a/src/spill.c b/src/spill.c new file mode 100644 index 0000000..72f8106 --- /dev/null +++ b/src/spill.c @@ -0,0 +1,507 @@ +#include "all.h" + +static void +loopmark(Blk *hd, Blk *b, Phi *p) +{ + int k, head; + uint n, a; + + head = hd->id; + if (b->id < head) + return; + for (; p; p=p->link) + for (a=0; a<p->narg; a++) + if (p->blk[a] == b) + if (rtype(p->arg[a]) == RTmp) + bsset(hd->gen, p->arg[a].val); + if (b->visit == head) + return; + b->visit = head; + b->loop *= 10; + /* aggregate looping information at + * loop headers */ + bsunion(hd->gen, b->gen); + for (k=0; k<2; k++) + if (b->nlive[k] > hd->nlive[k]) + hd->nlive[k] = b->nlive[k]; + for (n=0; n<b->npred; n++) + loopmark(hd, b->pred[n], b->phi); +} + +static void +tmpuse(Ref r, int use, int loop, Fn *fn) +{ + Mem *m; + Tmp *t; + + if (rtype(r) == RAMem) { + m = &fn->mem[r.val & AMask]; + tmpuse(m->base, 1, loop, fn); + tmpuse(m->index, 1, loop, fn); + } + else if (rtype(r) == RTmp && r.val >= Tmp0) { + t = &fn->tmp[r.val]; + t->nuse += use; + t->ndef += !use; + t->cost += loop; + } +} + +/* evaluate spill costs of temporaries, + * this also fills usage information + * requires rpo, preds + */ +void +fillcost(Fn *fn) +{ + int n, hd; + uint a; + Blk *b; + Ins *i; + Tmp *t; + Phi *p; + + for (b=fn->start; b; b=b->link) { + b->loop = 1; + b->visit = -1; + } + if (debug['S']) + fprintf(stderr, "\n> Loop information:\n"); + for (n=0; n<fn->nblk; n++) { + b = fn->rpo[n]; + hd = 0; + for (a=0; a<b->npred; a++) + if (b->pred[a]->id >= n) { + loopmark(b, b->pred[a], b->phi); + hd = 1; + } + if (hd && debug['S']) { + fprintf(stderr, "\t%-10s", b->name); + fprintf(stderr, " (% 3d ", b->nlive[0]); + fprintf(stderr, "% 3d) ", b->nlive[1]); + dumpts(b->gen, fn->tmp, stderr); + } + } + for (t=fn->tmp; t-fn->tmp < fn->ntmp; t++) { + t->cost = t-fn->tmp < Tmp0 ? 1e6 : 0; + t->nuse = 0; + t->ndef = 0; + } + for (b=fn->start; b; b=b->link) { + for (p=b->phi; p; p=p->link) { + /* todo, the cost computation + * for p->to is not great... */ + tmpuse(p->to, 0, 0, fn); + for (a=0; a<p->narg; a++) { + n = p->blk[a]->loop; + assert(b->npred==p->narg && + "wrong cfg"); + n /= b->npred; + tmpuse(p->arg[a], 1, n, fn); + } + } + n = b->loop; + for (i=b->ins; i-b->ins < b->nins; i++) { + tmpuse(i->to, 0, n, fn); + tmpuse(i->arg[0], 1, n, fn); + tmpuse(i->arg[1], 1, n, fn); + } + tmpuse(b->jmp.arg, 1, n, fn); + } + if (debug['S']) { + fprintf(stderr, "\n> Spill costs:\n"); + for (n=Tmp0; n<fn->ntmp; n++) + fprintf(stderr, "\t%-10s %d\n", + fn->tmp[n].name, + fn->tmp[n].cost); + fprintf(stderr, "\n"); + } +} + +static BSet *fst; /* temps to prioritize in registers (for tcmp1) */ +static Tmp *tmp; /* current temporaries (for tcmpX) */ +static int ntmp; /* current # of temps (for limit) */ +static int locs; /* stack size used by locals */ +static int slot4; /* next slot of 4 bytes */ +static int slot8; /* ditto, 8 bytes */ +static BSet mask[2][1]; /* class masks */ + +static int +tcmp0(const void *pa, const void *pb) +{ + return tmp[*(int *)pb].cost - tmp[*(int *)pa].cost; +} + +static int +tcmp1(const void *pa, const void *pb) +{ + int c; + + c = bshas(fst, *(int *)pb) - bshas(fst, *(int *)pa); + return c ? c : tcmp0(pa, pb); +} + +static Ref +slot(int t) +{ + int s; + + if (t < Tmp0) + diag("spill: cannot spill register"); + s = tmp[t].slot; + if (s == -1) { + assert(NAlign == 3); + /* nice logic to pack stack slots + * on demand, there can be only + * one hole and slot4 points to it + * + * invariant: slot4 <= slot8 + */ + if (KWIDE(tmp[t].cls)) { + s = slot8; + if (slot4 == slot8) + slot4 += 2; + slot8 += 2; + } else { + s = slot4; + if (slot4 == slot8) { + slot8 += 2; + slot4 += 1; + } else + slot4 = slot8; + } + s += locs; + tmp[t].slot = s; + } + return SLOT(s); +} + +static void +limit(BSet *b, int k, BSet *f) +{ + static int *tarr, maxt; + int i, nt; + uint t; + + nt = bscount(b); + if (nt <= k) + return; + if (nt > maxt) { + free(tarr); + tarr = emalloc(nt * sizeof tarr[0]); + maxt = nt; + } + for (i=0, t=0; bsiter(b, &t); t++) { + bsclr(b, t); + tarr[i++] = t; + } + if (!f) + qsort(tarr, nt, sizeof tarr[0], tcmp0); + else { + fst = f; + qsort(tarr, nt, sizeof tarr[0], tcmp1); + } + for (i=0; i<k && i<nt; i++) + bsset(b, tarr[i]); + for (; i<nt; i++) + slot(tarr[i]); +} + +static void +limit2(BSet *b1, int k1, int k2, BSet *fst) +{ + BSet b2[1]; + + bsinit(b2, ntmp); /* todo, free those */ + bscopy(b2, b1); + bsinter(b1, mask[0]); + bsinter(b2, mask[1]); + limit(b1, NIReg - k1, fst); + limit(b2, NFReg - k2, fst); + bsunion(b1, b2); +} + +static void +sethint(BSet *u, bits r) +{ + uint t; + + for (t=Tmp0; bsiter(u, &t); t++) + tmp[phicls(t, tmp)].hint.m |= r; +} + +static void +reloads(BSet *u, BSet *v) +{ + uint t; + + for (t=Tmp0; bsiter(u, &t); t++) + if (!bshas(v, t)) + emit(OLoad, tmp[t].cls, TMP(t), slot(t), R); +} + +static void +store(Ref r, int s) +{ + static int kstore[] = { + [Kw] = OStorew, [Kl] = OStorel, + [Ks] = OStores, [Kd] = OStored, + }; + + if (s != -1) + emit(kstore[tmp[r.val].cls], 0, R, r, SLOT(s)); +} + +static int +regcpy(Ins *i) +{ + return i->op == OCopy && isreg(i->arg[0]); +} + +static Ins * +dopm(Blk *b, Ins *i, BSet *v) +{ + int n, t; + BSet u[1]; + Ins *i1; + bits r; + + bsinit(u, ntmp); /* todo, free those */ + /* consecutive copies from + * registers need to be handled + * as one large instruction + * + * fixme: there is an assumption + * that calls are always followed + * by copy instructions here, this + * might not be true if previous + * passes change + */ + i1 = ++i; + do { + i--; + t = i->to.val; + if (!req(i->to, R)) + if (bshas(v, t)) { + bsclr(v, t); + store(i->to, tmp[t].slot); + } + bsset(v, i->arg[0].val); + } while (i != b->ins && regcpy(i-1)); + bscopy(u, v); + if (i != b->ins && (i-1)->op == OCall) { + v->t[0] &= ~retregs((i-1)->arg[1], 0); + limit2(v, NISave, NFSave, 0); + for (r=0, n=0; n<NRSave; n++) + r |= BIT(rsave[n]); + v->t[0] |= argregs((i-1)->arg[1], 0); + } else { + limit2(v, 0, 0, 0); + r = v->t[0]; + } + sethint(v, r); + reloads(u, v); + do + emiti(*--i1); + while (i1 != i); + return i; +} + +/* spill code insertion + * requires spill costs, rpo, liveness + * + * Note: this will replace liveness + * information (in, out) with temporaries + * that must be in registers at block + * borders + * + * Be careful with: + * - OCopy instructions to ensure register + * constraints + */ +void +spill(Fn *fn) +{ + Blk *b, *s1, *s2, *hd, **bp; + int j, n, l, t, k, lvarg[2]; + BSet u[1], v[1], w[1]; + Ins *i; + Phi *p; + Mem *m; + bits r; + + tmp = fn->tmp; + ntmp = fn->ntmp; + bsinit(u, ntmp); + bsinit(v, ntmp); + bsinit(w, ntmp); + bsinit(mask[0], ntmp); + bsinit(mask[1], ntmp); + locs = fn->slot; + slot4 = 0; + slot8 = 0; + for (t=0; t<ntmp; t++) { + k = 0; + if (t >= XMM0 && t < XMM0 + NFReg) + k = 1; + else if (t >= Tmp0) + k = KBASE(tmp[t].cls); + bsset(mask[k], t); + } + + for (bp=&fn->rpo[fn->nblk]; bp!=fn->rpo;) { + b = *--bp; + /* invariant: all bocks with bigger rpo got + * their in,out updated. */ + + /* 1. find temporaries in registers at + * the end of the block (put them in v) */ + curi = 0; + s1 = b->s1; + s2 = b->s2; + hd = 0; + if (s1 && s1->id <= n) + hd = s1; + if (s2 && s2->id <= n) + if (!hd || s2->id >= hd->id) + hd = s2; + r = 0; + bszero(v); + if (hd) { + /* back-edge */ + for (k=0; k<2; k++) { + n = k == 0 ? NIReg : NFReg; + bscopy(u, b->out); + bsinter(u, mask[k]); + bscopy(w, u); + bsinter(u, hd->gen); + bsdiff(w, hd->gen); + if ((int)bscount(u) < n) { /* fixme */ + j = bscount(w); /* live through */ + l = hd->nlive[k]; + limit(w, n - (l - j), 0); + bsunion(u, w); + } else + limit(u, n, 0); + bsunion(v, u); + } + } else if (s1) { + liveon(v, b, s1); + if (s2) { + liveon(u, b, s2); + bscopy(w, u); + bsinter(w, v); + bsunion(v, u); + } + limit2(v, 0, 0, w); + } else if (rtype(b->jmp.arg) == RACall) { + /* return */ + r = retregs(b->jmp.arg, 0); + v->t[0] |= r; + } + bscopy(b->out, v); + + /* 2. process the block instructions */ + curi = &insb[NIns]; + for (i=&b->ins[b->nins]; i!=b->ins;) { + i--; + if (regcpy(i)) { + i = dopm(b, i, v); + continue; + } + bszero(w); + if (!req(i->to, R)) { + assert(rtype(i->to) == RTmp); + t = i->to.val; + if (bshas(v, t)) + bsclr(v, t); + else { + /* make sure we have a reg + * for the result */ + bsset(v, t); + bsset(w, t); + } + } + j = opdesc[i->op].nmem; + for (n=0; n<2; n++) + if (rtype(i->arg[n]) == RAMem) + j--; + for (n=0; n<2; n++) + switch (rtype(i->arg[n])) { + case RAMem: + t = i->arg[n].val; + m = &fn->mem[t & AMask]; + if (rtype(m->base) == RTmp) { + bsset(v, m->base.val); + bsset(w, m->base.val); + } + if (rtype(m->index) == RTmp) { + bsset(v, m->index.val); + bsset(w, m->index.val); + } + break; + case RTmp: + t = i->arg[n].val; + lvarg[n] = bshas(v, t); + bsset(v, t); + if (j-- <= 0) + bsset(w, t); + break; + } + bscopy(u, v); + limit2(v, 0, 0, w); + for (n=0; n<2; n++) + if (rtype(i->arg[n]) == RTmp) { + t = i->arg[n].val; + if (!bshas(v, t)) { + /* do not reload if the + * the temporary was dead + */ + if (!lvarg[n]) + bsclr(u, t); + i->arg[n] = slot(t); + } + } + reloads(u, v); + if (!req(i->to, R)) { + t = i->to.val; + store(i->to, tmp[t].slot); + bsclr(v, t); + } + emiti(*i); + r = v->t[0] & (BIT(Tmp0)-1); + if (r) + sethint(v, r); + } + assert(!r || b==fn->start); + + for (p=b->phi; p; p=p->link) { + assert(rtype(p->to) == RTmp); + t = p->to.val; + if (bshas(v, t)) { + bsclr(v, t); + store(p->to, tmp[t].slot); + } else if (bshas(b->in, t)) + /* only if the phi is live */ + p->to = slot(p->to.val); + } + bscopy(b->in, v); + b->nins = &insb[NIns] - curi; + idup(&b->ins, curi, b->nins); + } + + /* align the locals to a 16 byte boundary */ + assert(NAlign == 3); + slot8 += slot8 & 3; + fn->slot += slot8; + + if (debug['S']) { + fprintf(stderr, "\n> Block information:\n"); + for (b=fn->start; b; b=b->link) { + printf("\t%-10s (% 5d) ", b->name, b->loop); + dumpts(b->out, fn->tmp, stdout); + } + fprintf(stderr, "\n> After spilling:\n"); + printfn(fn, stderr); + } +} diff --git a/src/ssa.c b/src/ssa.c new file mode 100644 index 0000000..0c163aa --- /dev/null +++ b/src/ssa.c @@ -0,0 +1,516 @@ +#include "all.h" +#include <stdarg.h> + +static void +adduse(Tmp *tmp, int ty, Blk *b, ...) +{ + Use *u; + int n; + va_list ap; + + va_start(ap, b); + n = tmp->nuse; + vgrow(&tmp->use, ++tmp->nuse); + u = &tmp->use[n]; + u->type = ty; + u->bid = b->id; + switch (ty) { + default: + diag("ssa: adduse defaulted"); + case UPhi: + u->u.phi = va_arg(ap, Phi *); + break; + case UIns: + u->u.ins = va_arg(ap, Ins *); + break; + case UJmp: + break; + } + va_end(ap); +} + +/* fill usage, phi, and class information + */ +void +filluse(Fn *fn) +{ + Blk *b; + Phi *p; + Ins *i; + int m, t; + uint a; + Tmp *tmp; + + /* todo, is this the correct file? */ + tmp = fn->tmp; + for (t=0; t<fn->ntmp; t++) { + tmp[t].ndef = 0; + tmp[t].nuse = 0; + tmp[t].phi = 0; + tmp[t].cls = 0; + if (tmp[t].use == 0) + tmp[t].use = vnew(0, sizeof(Use)); + } + for (b=fn->start; b; b=b->link) { + for (p=b->phi; p; p=p->link) { + assert(rtype(p->to) == RTmp); + t = p->to.val; + tmp[t].ndef++; + tmp[t].cls = p->cls; + tmp[t].phi = p->to.val; + for (a=0; a<p->narg; a++) + if (rtype(p->arg[a]) == RTmp) { + t = p->arg[a].val; + adduse(&tmp[t], UPhi, b, p); + if (!tmp[t].phi) + tmp[t].phi = p->to.val; + } + } + for (i=b->ins; i-b->ins < b->nins; i++) { + if (!req(i->to, R)) { + assert(rtype(i->to) == RTmp); + t = i->to.val; + tmp[t].ndef++; + tmp[t].cls = i->cls; + } + for (m=0; m<2; m++) + if (rtype(i->arg[m]) == RTmp) { + t = i->arg[m].val; + adduse(&tmp[t], UIns, b, i); + } + } + if (rtype(b->jmp.arg) == RTmp) + adduse(&tmp[b->jmp.arg.val], UJmp, b); + } +} + +static void +addpred(Blk *bp, Blk *bc) +{ + uint i; + + if (!bc->pred) { + bc->pred = alloc(bc->npred * sizeof bc->pred[0]); + for (i=0; i<bc->npred; i++) + bc->pred[i] = 0; + } + for (i=0; bc->pred[i]; i++) + ; + bc->pred[i] = bp; +} + +/* fill predecessors information in blocks + */ +void +fillpreds(Fn *f) +{ + Blk *b; + + for (b=f->start; b; b=b->link) { + b->npred = 0; + b->pred = 0; + } + for (b=f->start; b; b=b->link) { + if (b->s1) + b->s1->npred++; + if (b->s2) + b->s2->npred++; + } + for (b=f->start; b; b=b->link) { + if (b->s1) + addpred(b, b->s1); + if (b->s2) + addpred(b, b->s2); + } +} + +static int +rporec(Blk *b, int x) +{ + Blk *s1, *s2; + + if (!b || b->id >= 0) + return x; + b->id = 1; + s1 = b->s1; + s2 = b->s2; + if (s1 && s2 && s1->loop > s2->loop) { + s1 = b->s2; + s2 = b->s1; + } + x = rporec(s1, x); + x = rporec(s2, x); + b->id = x; + assert(x >= 0); + return x - 1; +} + +/* fill the rpo information in blocks + */ +void +fillrpo(Fn *f) +{ + int n; + Blk *b, **p; + + for (b=f->start; b; b=b->link) + b->id = -1; + n = 1 + rporec(f->start, f->nblk-1); + f->nblk -= n; + f->rpo = alloc(f->nblk * sizeof f->rpo[0]); + for (p=&f->start; *p;) { + b = *p; + if (b->id == -1) { + *p = b->link; + /* todo, free block */ + } else { + b->id -= n; + f->rpo[b->id] = b; + p=&(*p)->link; + } + } +} + +/* for dominators computation, read + * "A Simple, Fast Dominance Algorithm" + * by K. Cooper, T. Harvey, and K. Kennedy. + */ + +static Blk * +inter(Blk *b1, Blk *b2) +{ + Blk *bt; + + if (b1 == 0) + return b2; + while (b1 != b2) { + if (b1->id < b2->id) { + bt = b1; + b1 = b2; + b2 = bt; + } + while (b1->id > b2->id) { + b1 = b1->idom; + assert(b1); + } + } + return b1; +} + +static void +filldom(Fn *fn) +{ + Blk *b, *d; + int ch, n; + uint p; + + for (b=fn->start; b; b=b->link) { + b->idom = 0; + b->dom = 0; + b->dlink = 0; + } + do { + ch = 0; + for (n=1; n<fn->nblk; n++) { + b = fn->rpo[n]; + d = 0; + for (p=0; p<b->npred; p++) + if (b->pred[p]->idom + || b->pred[p] == fn->start) + d = inter(d, b->pred[p]); + if (d != b->idom) { + ch++; + b->idom = d; + } + } + } while (ch); + for (b=fn->start; b; b=b->link) + if ((d=b->idom)) { + assert(d != b); + b->dlink = d->dom; + d->dom = b; + } +} + +static int +sdom(Blk *b1, Blk *b2) +{ + assert(b1 && b2); + if (b1 == b2) + return 0; + while (b2->id > b1->id) + b2 = b2->idom; + return b1 == b2; +} + +static int +dom(Blk *b1, Blk *b2) +{ + return b1 == b2 || sdom(b1, b2); +} + +static void +addfron(Blk *a, Blk *b) +{ + int n; + + for (n=0; n<a->nfron; n++) + if (a->fron[n] == b) + return; + if (!a->nfron) + a->fron = vnew(++a->nfron, sizeof a->fron[0]); + else + vgrow(&a->fron, ++a->nfron); + a->fron[a->nfron-1] = b; +} + +static void +fillfron(Fn *fn) +{ + Blk *a, *b; + + for (b=fn->start; b; b=b->link) { + if (b->s1) + for (a=b; !sdom(a, b->s1); a=a->idom) + addfron(a, b->s1); + if (b->s2) + for (a=b; !sdom(a, b->s2); a=a->idom) + addfron(a, b->s2); + } +} + +static Ref +refindex(int t, Fn *fn) +{ + return newtmp(fn->tmp[t].name, fn->tmp[t].cls, fn); +} + +static void +phiins(Fn *fn) +{ + BSet u[1], defs[1]; + Blk *a, *b, **blist, **be, **bp; + Ins *i; + Phi *p; + Ref r; + int t, n, k, nt; + + bsinit(u, fn->nblk); + bsinit(defs, fn->nblk); + blist = emalloc(fn->nblk * sizeof blist[0]); + be = &blist[fn->nblk]; + nt = fn->ntmp; + for (t=Tmp0; t<nt; t++) { + fn->tmp[t].visit = 0; + if (fn->tmp[t].phi != 0) + continue; + bszero(u); + k = -1; + bp = be; + for (b=fn->start; b; b=b->link) { + b->visit = 0; + r = R; + for (i=b->ins; i-b->ins < b->nins; i++) { + if (!req(r, R)) { + if (req(i->arg[0], TMP(t))) + i->arg[0] = r; + if (req(i->arg[1], TMP(t))) + i->arg[1] = r; + } + if (req(i->to, TMP(t))) { + if (!bshas(b->out, t)) { + if (fn->tmp[t].ndef == 1) + r = TMP(t); + else + r = refindex(t, fn); + i->to = r; + } else { + if (!bshas(u, b->id)) { + bsset(u, b->id); + *--bp = b; + } + if (k == -1) + k = i->cls; + assert(k == i->cls); + } + } + } + if (!req(r, R) && req(b->jmp.arg, TMP(t))) + b->jmp.arg = r; + } + bscopy(defs, u); + while (bp != be) { + fn->tmp[t].visit = t; + b = *bp++; + bsclr(u, b->id); + for (n=0; n<b->nfron; n++) { + a = b->fron[n]; + if (a->visit++ == 0) + if (bshas(a->in, t)) { + p = alloc(sizeof *p); + p->cls = k; + p->to = TMP(t); + p->link = a->phi; + a->phi = p; + if (!bshas(defs, a->id)) + if (!bshas(u, a->id)) { + bsset(u, a->id); + *--bp = a; + } + } + } + } + } + free(blist); +} + +typedef struct Name Name; +struct Name { + Ref r; + Blk *b; + Name *up; +}; + +static Name *namel; + +static Name * +nnew(Ref r, Blk *b, Name *up) +{ + Name *n; + + if (namel) { + n = namel; + namel = n->up; + } else + /* could use alloc, here + * but namel should be reset + */ + n = emalloc(sizeof *n); + n->r = r; + n->b = b; + n->up = up; + return n; +} + +static void +nfree(Name *n) +{ + n->up = namel; + namel = n; +} + +static void +rendef(Ref *r, Blk *b, Name **stk, Fn *fn) +{ + Ref r1; + int t; + + t = r->val; + if (req(*r, R) || !fn->tmp[t].visit) + return; + r1 = refindex(t, fn); + fn->tmp[r1.val].visit = t; + stk[t] = nnew(r1, b, stk[t]); + *r = r1; +} + +static Ref +getstk(int t, Blk *b, Name **stk) +{ + Name *n, *n1; + + n = stk[t]; + while (n && !dom(n->b, b)) { + n1 = n; + n = n->up; + nfree(n1); + } + stk[t] = n; + if (!n) { + /* uh, oh, warn */ + return CON_Z; + } else + return n->r; +} + +static void +renblk(Blk *b, Name **stk, Fn *fn) +{ + Phi *p; + Ins *i; + Blk *s, **ps, *succ[3]; + int t, m; + + for (p=b->phi; p; p=p->link) + rendef(&p->to, b, stk, fn); + for (i=b->ins; i-b->ins < b->nins; i++) { + for (m=0; m<2; m++) { + t = i->arg[m].val; + if (rtype(i->arg[m]) == RTmp) + if (fn->tmp[t].visit) + i->arg[m] = getstk(t, b, stk); + } + rendef(&i->to, b, stk, fn); + } + t = b->jmp.arg.val; + if (rtype(b->jmp.arg) == RTmp) + if (fn->tmp[t].visit) + b->jmp.arg = getstk(t, b, stk); + succ[0] = b->s1; + succ[1] = b->s2; + succ[2] = 0; + for (ps=succ; (s=*ps); ps++) + for (p=s->phi; p; p=p->link) { + t = p->to.val; + if ((t=fn->tmp[t].visit)) { + m = p->narg++; + if (m == NPred) + diag("ssa: too many phi arguments"); + p->arg[m] = getstk(t, b, stk); + p->blk[m] = b; + } + } + for (s=b->dom; s; s=s->dlink) + renblk(s, stk, fn); +} + +/* require ndef */ +void +ssa(Fn *fn) +{ + Name **stk, *n; + int d, nt; + Blk *b, *b1; + + nt = fn->ntmp; + stk = emalloc(nt * sizeof stk[0]); + d = debug['L']; + debug['L'] = 0; + filldom(fn); + if (debug['N']) { + fprintf(stderr, "\n> Dominators:\n"); + for (b1=fn->start; b1; b1=b1->link) { + if (!b1->dom) + continue; + fprintf(stderr, "%10s:", b1->name); + for (b=b1->dom; b; b=b->dlink) + fprintf(stderr, " %s", b->name); + fprintf(stderr, "\n"); + } + } + fillfron(fn); + filllive(fn); + phiins(fn); + renblk(fn->start, stk, fn); + while (nt--) + while ((n=stk[nt])) { + stk[nt] = n->up; + nfree(n); + } + debug['L'] = d; + free(stk); + if (debug['N']) { + fprintf(stderr, "\n> After SSA construction:\n"); + printfn(fn, stderr); + } +} diff --git a/src/test/_alt.ssa b/src/test/_alt.ssa new file mode 100644 index 0000000..3f89e5e --- /dev/null +++ b/src/test/_alt.ssa @@ -0,0 +1,25 @@ +# an example with reducible control +# flow graph that exposes poor +# handling of looping constructs + +function $test() { +@start + %ten =w copy 10 + %dum =w copy 0 # dummy live-through temporary +@loop + %alt =w phi @start 0, @left %alt1, @right %alt1 + %cnt =w phi @start 100, @left %cnt, @right %cnt1 + %alt1 =w sub 1, %alt + jnz %alt1, @right, @left +@left + %x =w phi @loop 10, @left %x1 + %x1 =w sub %x, 1 + %z =w copy %x + jnz %z, @left, @loop +@right + %cnt1 =w sub %cnt, %ten + jnz %cnt1, @loop, @end +@end + %ret =w add %cnt, %dum + ret +} diff --git a/src/test/_dragon.ssa b/src/test/_dragon.ssa new file mode 100644 index 0000000..b169e1b --- /dev/null +++ b/src/test/_dragon.ssa @@ -0,0 +1,33 @@ +# a moderately complex test for +# dominators computation from +# the dragon book +# because branching is limited to +# two, I had to split some blocks + +function $dragon() { +@start +@b1 + jnz 0, @b2, @b3 +@b2 + jmp @b3 +@b3 + jmp @b4.1 +@b4.1 + jnz 0, @b3, @b4.2 +@b4.2 + jnz 0, @b5, @b6 +@b5 + jmp @b7 +@b6 + jmp @b7 +@b7 + jnz 0, @b8.1, @b4.1 +@b8.1 + jnz 0, @b3, @b8.2 +@b8.2 + jnz 0, @b9, @b10 +@b9 + jmp @b1 +@b10 + jmp @b7 +} diff --git a/src/test/_fix1.ssa b/src/test/_fix1.ssa new file mode 100644 index 0000000..e89307f --- /dev/null +++ b/src/test/_fix1.ssa @@ -0,0 +1,15 @@ +function $test() { +@start + %x =w copy 1 +@loop + jnz %x, @noz, @isz +@noz + %x =w copy 0 + jmp @end +@isz + %x =w copy 1 + jmp @loop +@end + %z =w add 10, %x + ret +} diff --git a/src/test/_fix2.ssa b/src/test/_fix2.ssa new file mode 100644 index 0000000..89f236d --- /dev/null +++ b/src/test/_fix2.ssa @@ -0,0 +1,15 @@ +function $test() { +@start + %x =w copy 1 +@loop + jnz %x, @noz, @isz +@noz + %x =w copy 0 + jnz %x, @loop, @end +@isz + %x =w copy 1 + jmp @loop +@end + %z =w add 10, %x + ret +} diff --git a/src/test/_fix3.ssa b/src/test/_fix3.ssa new file mode 100644 index 0000000..283e5a1 --- /dev/null +++ b/src/test/_fix3.ssa @@ -0,0 +1,20 @@ +function w $test() { +@start + %x =w copy 100 + %s =w copy 0 +@l + %c =w cslew %x, 10 + jnz %c, @a, @b +@a + %s =w add %s, %x + %x =w sub %x, 1 + jmp @c +@b + %s =w sub %s, %x + jmp @c +@c + %x =w sub %x, 1 + jnz %x, @l, @end +@end + ret %s +} diff --git a/src/test/_fix4.ssa b/src/test/_fix4.ssa new file mode 100644 index 0000000..181768d --- /dev/null +++ b/src/test/_fix4.ssa @@ -0,0 +1,27 @@ +function $test() { +@start + %x =w copy 3 + %n =w copy 2 +@loop + %c =w ceqw %n, 10000 + jnz %c, @end, @next +@next + %t =w copy 3 + %x =w add %x, 2 +@tloop + %s =w mul %t, %t + %c =w csgtw %s, %x + jnz %c, @prime, @test +@test + %r =w rem %x, %t + jnz %r, @tnext, @loop +@tnext + %t =w add %t, 2 + jmp @tloop +@prime + %n =w add %n, 1 + jmp @loop +@end + storew %x, $a + ret +} diff --git a/src/test/_live.ssa b/src/test/_live.ssa new file mode 100644 index 0000000..fce4cb9 --- /dev/null +++ b/src/test/_live.ssa @@ -0,0 +1,21 @@ +# this control flow graph is irreducible +# yet, we expecet the liveness analysis +# to work properly and make %x live in +# the block @left +# +# nothing should ever be live at the entry + +function $test() { +@start + %b =w copy 0 + %x =w copy 10 + jnz 0, @loop, @left +@left + jmp @inloop +@loop + %x1 =w add %x, 1 +@inloop + %b1 =w add %b, 1 +@endloop + jmp @loop +} diff --git a/src/test/_rpo.ssa b/src/test/_rpo.ssa new file mode 100644 index 0000000..a10c6b1 --- /dev/null +++ b/src/test/_rpo.ssa @@ -0,0 +1,12 @@ +function $test() { +@start + jmp @foo +@baz + jnz 1, @end, @foo +@bar + jmp @end +@foo + jnz 0, @bar, @baz +@end + ret +} diff --git a/src/test/_spill1.ssa b/src/test/_spill1.ssa new file mode 100644 index 0000000..df5e4c2 --- /dev/null +++ b/src/test/_spill1.ssa @@ -0,0 +1,22 @@ +# test with NReg == 3 +# there must be a spill +# happening on %c +# +# if you replace the sub +# by an add or comment +# the two marked lines +# there should be no +# spill +# + +function $test() { +@start + %f =w copy 0 # here + %b =w copy 1 + %c =w copy 2 + %a =w sub %b, %c + %d =w copy %b + %e =w copy %f # and there + %g =w copy %a + ret +} diff --git a/src/test/_spill2.ssa b/src/test/_spill2.ssa new file mode 100644 index 0000000..d462d0b --- /dev/null +++ b/src/test/_spill2.ssa @@ -0,0 +1,22 @@ +# stupid spilling test + +function $test() { +@start + %x1 =w copy 10 + %x2 =w add %x1, %x1 + %x3 =w sub %x2, %x1 + %x4 =w add %x3, %x1 + %x5 =w sub %x4, %x1 + %x6 =w add %x5, %x1 + %x7 =w sub %x6, %x1 + %x8 =w add %x7, %x1 + %x9 =w sub %x8, %x8 + %x10 =w add %x9, %x7 + %x11 =w sub %x10, %x6 + %x12 =w add %x11, %x5 + %x13 =w sub %x12, %x4 + %x14 =w add %x13, %x3 + %x15 =w sub %x14, %x2 + %x16 =w add %x15, %x1 + ret +} diff --git a/src/test/_spill3.ssa b/src/test/_spill3.ssa new file mode 100644 index 0000000..cdfda2d --- /dev/null +++ b/src/test/_spill3.ssa @@ -0,0 +1,24 @@ +# make sure comparisons +# never get their two +# operands in memory +# run with NReg == 3, or +# adapt it! + +function $test() { +@start + %a =w loadw $a + %b =w loadw $a + +@loop + %c =w phi @start 0, @loop %f + %d =w phi @start 0, @loop %g + %e =w phi @start 0, @loop %h + %f =w add %c, %d + %g =w add %c, %e + %h =w add %e, %d + %x =w cslew %a, %b + jnz %x, @loop, @end + +@end + ret +} diff --git a/src/test/abi1.ssa b/src/test/abi1.ssa new file mode 100644 index 0000000..69cce44 --- /dev/null +++ b/src/test/abi1.ssa @@ -0,0 +1,59 @@ +# test calling into C with two +# large struct arguments (passed +# on the stack) + +type :mem = { b 17 } + +function $alpha(l %p, w %l, l %n) { +@ini + %pe =l add %p, %n +@lop + %p1 =l phi @ini %p, @lop %p2 + %l1 =w phi @ini %l, @lop %l2 + storeb %l1, %p1 + %p2 =l add %p1, 1 + %l2 =w add %l1, 1 + %c1 =w ceql %p1, %pe + jnz %c1, @end, @lop +@end + storeb 0, %pe + ret +} + +function $test() { +@start + %p =l alloc4 17 + %q =l alloc4 17 + %r0 =w call $alpha(l %p, w 65, l 16) + %r1 =w call $alpha(l %q, w 97, l 16) + %r2 =w call $fcb(:mem %p, w 1, w 2, w 3, w 4, w 5, w 6, w 7, w 8, w 9, :mem %q) + ret +} + + +# >>> driver +# #include <stdio.h> +# typedef struct { char t[17]; } mem; +# extern void test(); +# void fcb(mem m, int i1, int i2, int i3, int i4, int i5, int i6, int i7, int i8, int i9, mem n) { +# printf("fcb: m = (mem){ t = \"%s\" }\n", m.t); +# printf(" n = (mem){ t = \"%s\" }\n", n.t); +# #define T(n) printf(" i%d = %d\n", n, i##n); +# T(1) T(2) T(3) T(4) T(5) T(6) T(7) T(8) T(9) +# } +# int main() { test(); return 0; } +# <<< + +# >>> output +# fcb: m = (mem){ t = "ABCDEFGHIJKLMNOP" } +# n = (mem){ t = "abcdefghijklmnop" } +# i1 = 1 +# i2 = 2 +# i3 = 3 +# i4 = 4 +# i5 = 5 +# i6 = 6 +# i7 = 7 +# i8 = 8 +# i9 = 9 +# <<< diff --git a/src/test/abi2.ssa b/src/test/abi2.ssa new file mode 100644 index 0000000..b82c80c --- /dev/null +++ b/src/test/abi2.ssa @@ -0,0 +1,18 @@ +type :fps = { s, b, s } + +function s $sum(:fps %p) { +@start + %f1 =s load %p + %p8 =l add 8, %p + %f2 =s load %p8 + %s =s add %f1, %f2 + ret %s +} + +# >>> driver +# typedef struct { float f1; char b; float f2; } fps; +# extern float sum(fps); +# int main() { fps x = { 1.23, -1, 2.34 }; return !(sum(x) == 1.23f+2.34f); } +# /* Note the f suffixes above are important +# * otherwise C does double operations. */ +# <<< diff --git a/src/test/abi3.ssa b/src/test/abi3.ssa new file mode 100644 index 0000000..608d1db --- /dev/null +++ b/src/test/abi3.ssa @@ -0,0 +1,43 @@ +type :four = {l, b, w} + +data $z = { w 0 } + +function $test() { + @start + %a =w loadw $z + %y =w add %a, %a + + %s =l alloc8 16 # allocate a :four struct + %s1 =l add %s, 12 # get address of the w + storel 4, %s # set the l + storew 5, %s1 # set the w + + # only the last argument should be on the stack + %f =l add $F, %y + %x =w call %f(w %y, w 1, w 2, w 3, :four %s, w 6) + + # store the result in the + # global variable a + + %x1 =w add %y, %x + storew %x1, $a + ret +} + +# >>> driver +# #include <stdio.h> +# struct four { long l; char c; int i; }; +# extern void test(void); +# int F(int a0, int a1, int a2, int a3, struct four s, int a6) { +# printf("%d %d %d %d %d %d %d\n", +# a0, a1, a2, a3, (int)s.l, s.i, a6); +# return 42; +# } +# int a; +# int main() { test(); printf("%d\n", a); return 0; } +# <<< + +# >>> output +# 0 1 2 3 4 5 6 +# 42 +# <<< diff --git a/src/test/abi4.ssa b/src/test/abi4.ssa new file mode 100644 index 0000000..4c3d89b --- /dev/null +++ b/src/test/abi4.ssa @@ -0,0 +1,38 @@ +# return a large struct to C + +type :mem = { b 17 } + +function $alpha(l %p, w %l, l %n) { +@ini + %pe =l add %p, %n +@lop + %p1 =l phi @ini %p, @lop %p2 + %l1 =w phi @ini %l, @lop %l2 + storeb %l1, %p1 + %p2 =l add %p1, 1 + %l2 =w add %l1, 1 + %c1 =w ceql %p1, %pe + jnz %c1, @end, @lop +@end + storeb 0, %pe + ret +} + +function :mem $test() { +@start + %p =l alloc4 17 + %r0 =w call $alpha(l %p, w 65, l 16) + ret %p +} + + +# >>> driver +# #include <stdio.h> +# typedef struct { char t[17]; } mem; +# extern mem test(void); +# int main() { mem m = test(); printf("%s\n", m.t); return 0; } +# <<< + +# >>> output +# ABCDEFGHIJKLMNOP +# <<< diff --git a/src/test/abi5.ssa b/src/test/abi5.ssa new file mode 100644 index 0000000..4c5eaea --- /dev/null +++ b/src/test/abi5.ssa @@ -0,0 +1,105 @@ +# returning structs from C + +type :st1 = { b 17 } +type :st2 = { w } +type :st3 = { s, w } +type :st4 = { w, d } +type :st5 = { s, l } +type :st6 = { b 16 } +type :st7 = { s, d } +type :st8 = { w 4 } + +data $fmt1 = { b "t1: %s\n", b 0 } +data $fmt2 = { b "t2: %d\n", b 0 } +data $fmt3 = { b "t3: %f %d\n", b 0 } +data $fmt4 = { b "t4: %d %f\n", b 0 } +data $fmt5 = { b "t5: %f %lld\n", b 0 } +data $fmt6 = { b "t6: %s\n", b 0 } +data $fmt7 = { b "t7: %f %f\n", b 0 } +data $fmt8 = { b "t8: %d %d %d %d\n", b 0 } + +function $test() { +@start + %r1 =:st1 call $t1() + %i1 =w call $printf(l $fmt1, l %r1) + + %r2 =:st2 call $t2() + %w2 =w loadw %r2 + %i2 =w call $printf(l $fmt2, w %w2) + + %r3 =:st3 call $t3() + %s3 =s loads %r3 + %r34 =l add %r3, 4 + %w3 =w loadw %r34 + %p3 =d exts %s3 + %i3 =w call $printf(l $fmt3, d %p3, w %w3) + + %r4 =:st4 call $t4() + %w4 =w loadw %r4 + %r48 =l add 8, %r4 + %d4 =d loadd %r48 + %i4 =w call $printf(l $fmt4, w %w4, d %d4) + + %r5 =:st5 call $t5() + %s5 =s loads %r5 + %d5 =d exts %s5 + %r58 =l add %r5, 8 + %l5 =l loadl %r58 + %i5 =w call $printf(l $fmt5, d %d5, l %l5) + + %r6 =:st6 call $t6() + %i6 =w call $printf(l $fmt6, l %r6) + + %r7 =:st7 call $t7() + %s7 =s loads %r7 + %d71 =d exts %s7 + %r78 =l add %r7, 8 + %d72 =d loadd %r78 + %i7 =w call $printf(l $fmt7, d %d71, d %d72) + + %r8 =:st8 call $t8() + %r84 =l add 4, %r8 + %r88 =l add 4, %r84 + %r812 =l add 4, %r88 + %w81 =w loadw %r8 + %w82 =w loadw %r84 + %w83 =w loadw %r88 + %w84 =w loadw %r812 + %i8 =w call $printf(l $fmt8, w %w81, w %w82, w %w83, w %w84) + + ret +} + + +# >>> driver +# #include <stdio.h> +# typedef struct { char t[17]; } st1; +# typedef struct { int i; } st2; +# typedef struct { float f; int i; } st3; +# typedef struct { int i; double d; } st4; +# typedef struct { float f; long l; } st5; +# typedef struct { char t[16]; } st6; +# typedef struct { float f; double d; } st7; +# typedef struct { int i[4]; } st8; +# extern void test(void); +# st1 t1() { return (st1){"abcdefghijklmnop"}; } +# st2 t2() { return (st2){2}; } +# st3 t3() { return (st3){3.0,30}; } +# st4 t4() { return (st4){4,-40}; } +# st5 t5() { return (st5){5.5,-55}; } +# st6 t6() { return (st6){"abcdefghijklmno"}; } +# st7 t7() { return (st7){7.77,77.7}; } +# st8 t8() { return (st8){-8,88,-888,8888}; } +# int main() { test(); return 0; } +# <<< + +# >>> output +# t1: abcdefghijklmnop +# t2: 2 +# t3: 3.000000 30 +# t4: 4 -40.000000 +# t5: 5.500000 -55 +# t6: abcdefghijklmno +# t7: 7.770000 77.700000 +# t8: -8 88 -888 8888 +# <<< diff --git a/src/test/align.ssa b/src/test/align.ssa new file mode 100644 index 0000000..84d1fb9 --- /dev/null +++ b/src/test/align.ssa @@ -0,0 +1,16 @@ +function $test() { +@start + %x =l alloc16 16 + %y =l add %x, 8 + %m =w rem %y, 16 + storew %m, %y + %n =w loadw %y + storew %n, $a + ret +} + +# >>> driver +# extern void test(void); +# int a; +# int main() { test(); return !(a == 8 || a == -8); } +# <<< diff --git a/src/test/collatz.ssa b/src/test/collatz.ssa new file mode 100644 index 0000000..373ecac --- /dev/null +++ b/src/test/collatz.ssa @@ -0,0 +1,61 @@ +# a solution for N=1000 to +# https://projecteuler.net/problem=14 +# we use a fast local array to +# memoize small collatz numbers + +function $test() { +@start + %mem =l alloc4 4000 +@loop + %n =w phi @start 1, @newm %n9, @oldm %n9 + %cmax =w phi @start 0, @newm %c, @oldm %cmax + %fin =w csltw %n, 1000 + jnz %fin, @cloop, @end +@cloop + %n0 =w phi @loop %n, @odd %n2, @even %n3 + %c0 =w phi @loop 0, @odd %c1, @even %c1 + %no1 =w cnew %n0, 1 + jnz %no1, @iter0, @endcl +@iter0 + %ism =w csltw %n0, %n + jnz %ism, @getmemo, @iter1 +@iter1 + %c1 =w add %c0, 1 + %p =w and %n0, 1 + jnz %p, @odd, @even +@odd + %n1 =w mul 3, %n0 + %n2 =w add %n1, 1 + jmp @cloop +@even + %n3 =w div %n0, 2 + jmp @cloop +@getmemo # get the count for n0 in mem + %n0l =l extsw %n0 + %idx0 =l mul %n0l, 4 + %loc0 =l add %idx0, %mem + %cn0 =w loadw %loc0 + %c2 =w add %c0, %cn0 +@endcl # store the count for n in mem + %c =w phi @getmemo %c2, @cloop %c0 + %nl =l extsw %n + %idx1 =l mul %nl, 4 + %loc1 =l add %idx1, %mem + storew %c, %loc1 + %n9 =w add 1, %n + %big =w cslew %cmax, %c + jnz %big, @newm, @oldm +@newm + jmp @loop +@oldm + jmp @loop +@end + storew %cmax, $a + ret +} + +# >>> driver +# extern void test(void); +# int a; +# int main() { test(); return !(a == 178); } +# <<< diff --git a/src/test/cprime.ssa b/src/test/cprime.ssa new file mode 100644 index 0000000..1ca60e1 --- /dev/null +++ b/src/test/cprime.ssa @@ -0,0 +1,103 @@ +# generated by Andrew Chambers' +# compiler from the C program +# following in comments + +function w $main() { +@start + %v0 =l alloc8 4 + %v1 =l alloc8 4 + %v2 =l alloc8 4 + %v3 =l alloc8 4 + %v4 =l alloc8 4 + storew 5, %v1 + storew 11, %v2 + storew 12, %v3 +@L0 + %v5 =w loadw %v1 + %v6 =w cnew %v5, 201 + jnz %v6, @L8, @L1 +@L8 + storew 1, %v4 + %v7 =w loadw %v3 + %v8 =w rem %v7, 2 + %v9 =w ceqw %v8, 0 + jnz %v9, @L9, @L5 +@L9 + storew 0, %v4 +@L5 + storew 3, %v0 +@L2 + %v10 =w loadw %v0 + %v11 =w loadw %v3 + %v12 =w csltw %v10, %v11 + jnz %v12, @L10, @L3 +@L10 + %v13 =w loadw %v3 + %v14 =w loadw %v0 + %v15 =w rem %v13, %v14 + %v16 =w ceqw %v15, 0 + jnz %v16, @L11, @L4 +@L11 + storew 0, %v4 + jmp @L3 +@L4 + %v17 =w loadw %v0 + %v18 =w add %v17, 2 + storew %v18, %v0 + jmp @L2 +@L3 + %v19 =w loadw %v4 + jnz %v19, @L12, @L6 +@L12 + %v20 =w loadw %v3 + storew %v20, %v2 + %v21 =w loadw %v1 + %v22 =w add %v21, 1 + storew %v22, %v1 +@L6 + %v23 =w loadw %v3 + %v24 =w add %v23, 1 + storew %v24, %v3 + jmp @L0 +@L1 + %v25 =w loadw %v2 + %v26 =w cnew %v25, 1229 + jnz %v26, @L13, @L7 +@L13 + ret 1 +@L7 + ret 0 +@end + ret 0 +} + +# int +# main() +# { +# int i, n, p, next, isprime; +# +# n = 5; +# p = 11; +# next = 12; +# while(n != 201) { +# isprime = 1; +# if(next % 2 == 0) { +# isprime = 0; +# } else { +# for(i = 3; i < next; i = i + 2) { +# if(next % i == 0) { +# isprime = 0; +# break; +# } +# } +# } +# if(isprime) { +# p = next; +# n = n + 1; +# } +# next = next + 1; +# } +# if(p != 1229) +# return 1; +# return 0; +# } diff --git a/src/test/cup.ssa b/src/test/cup.ssa new file mode 100644 index 0000000..013394f --- /dev/null +++ b/src/test/cup.ssa @@ -0,0 +1,17 @@ +# counts up from -1988 to 1991 + +function $test() { +@start +@loop + %n0 =l phi @start -1988, @loop %n1 + %n1 =l add 1, %n0 + %cmp =w cslel 1991, %n1 + jnz %cmp, @end, @loop +@end + ret +} + +# >>> driver +# extern void test(void); +# int main() { test(); return 0; } +# <<< diff --git a/src/test/dark.ssa b/src/test/dark.ssa new file mode 100644 index 0000000..5046af3 --- /dev/null +++ b/src/test/dark.ssa @@ -0,0 +1,30 @@ +# a hack example, +# we use a dark type to get +# a pointer to the stack. + +type :magic = align 1 { 0 } + +data $ret = { l 0 } + +function $test(:magic %p) { +@start + %av =w loadw $a + %a1 =w add 1, %av + storew %a1, $a # increment $a + %r1 =l loadl $ret # fetch from $ret + %p1 =l add %p, -8 + %r2 =l loadl %p1 # get the return address + storel %r2, $ret # store it in $ret + %c =w ceql %r1, %r2 + jnz %c, @fin, @cal +@cal + %i =w call $test() # no argument given, intentionally! +@fin + ret +} + +# >>> driver +# extern void test(void); +# int a = 2; +# int main() { test(); return !(a == 5); } +# <<< diff --git a/src/test/double.ssa b/src/test/double.ssa new file mode 100644 index 0000000..d885d28 --- /dev/null +++ b/src/test/double.ssa @@ -0,0 +1,24 @@ +function $test() { +@start + %x1 =d copy d_0.1 + %x2 =d add d_0.2, %x1 + %x3 =d sub %x2, d_0.3 + +@loop + %x4 =d phi @start %x3, @loop %x5 + %i1 =w phi @start 0, @loop %i2 + %x5 =d add %x4, %x4 + %i2 =w add %i1, 1 + %c0 =w cled %x5, 4607182418800017408 # d_1.0 + jnz %c0, @loop, @end + +@end + storew %i2, $a + ret +} + +# >>> driver +# extern void test(void); +# int a; +# int main() { test(); return !(a == 55); } +# <<< diff --git a/src/test/echo.ssa b/src/test/echo.ssa new file mode 100644 index 0000000..d3c8a25 --- /dev/null +++ b/src/test/echo.ssa @@ -0,0 +1,32 @@ +function w $main(w %argc, l %argv) { +@start + %fmt =l alloc8 8 + storel 1663398693, %fmt # "%s%c" + %av0 =l add %argv, 8 + %ac0 =w sub %argc, 1 +@loop + %av =l phi @start %av0, @loop2 %av1 + %ac =w phi @start %ac0, @loop2 %ac1 + %c0 =w ceqw %ac, 0 + jnz %c0, @end, @loop1 +@loop1 + %c1 =w ceqw %ac, 1 + jnz %c1, @last, @nolast +@last + jmp @loop2 +@nolast + jmp @loop2 +@loop2 + %sep =w phi @last 10, @nolast 32 + %arg =l loadl %av + %r =w call $printf(l %fmt, l %arg, w %sep) + %av1 =l add %av, 8 + %ac1 =w sub %ac, 1 + jmp @loop +@end + ret 0 +} + +# >>> output +# a b c +# <<< diff --git a/src/test/eucl.ssa b/src/test/eucl.ssa new file mode 100644 index 0000000..f50fd2c --- /dev/null +++ b/src/test/eucl.ssa @@ -0,0 +1,24 @@ +# euclide's algorithm in ssa +# it is a fairly interesting +# ssa program because of the +# swap of b and a + +function $test() { +@start + +@loop + %a =w phi @start 380, @loop %r + %b =w phi @start 747, @loop %a + %r =w rem %b, %a + jnz %r, @loop, @end + +@end + storew %a, $a + ret +} + +# >>> driver +# extern void test(void); +# int a; +# int main() { test(); return !(a == 1); } +# <<< diff --git a/src/test/euclc.ssa b/src/test/euclc.ssa new file mode 100644 index 0000000..c76db2f --- /dev/null +++ b/src/test/euclc.ssa @@ -0,0 +1,29 @@ +function w $test() { +@l0 + %a =l alloc4 4 + %b =l alloc4 4 + %r =l alloc4 4 + storew 747, %a + storew 380, %b +@l1 + %t4 =w loadw %b + jnz %t4, @l2, @l3 +@l2 + %t7 =w loadw %a + %t8 =w loadw %b + %t6 =w rem %t7, %t8 + storew %t6, %r + %t10 =w loadw %b + storew %t10, %a + %t12 =w loadw %r + storew %t12, %b + jmp @l1 +@l3 + %t13 =w loadw %a + ret %t13 +} + +# >>> driver +# extern int test(void); +# int main() { return !(test() == 1); } +# <<< diff --git a/src/test/fpcnv.ssa b/src/test/fpcnv.ssa new file mode 100644 index 0000000..5fd3be9 --- /dev/null +++ b/src/test/fpcnv.ssa @@ -0,0 +1,27 @@ +# floating point casts and conversions + +function s $fneg(s %f) { +@fneg + %b0 =w cast %f + %b1 =w xor 2147483648, %b0 + %rs =s cast %b1 + ret %rs +} + +function d $ftrunc(d %f) { +@ftrunc + %l0 =l ftosi %f + %rt =d sitof %l0 + ret %rt +} + +# >>> driver +# extern float fneg(float); +# extern double ftrunc(double); +# int main() { +# if (fneg(1.23f) != -1.23f) return 1; +# if (ftrunc(3.1415) != 3.0) return 2; +# if (ftrunc(-1.234) != -1.0) return 3; +# return 0; +# } +# <<< diff --git a/src/test/go.sh b/src/test/go.sh new file mode 100755 index 0000000..35bf525 --- /dev/null +++ b/src/test/go.sh @@ -0,0 +1,116 @@ +#!/bin/sh + +TMP=/tmp/qbe.zzzz + +DRV=$TMP.c +ASM=$TMP.s +BIN=$TMP.bin +OUT=$TMP.out + +cleanup() { + rm -f $DRV $ASM $BIN $OUT +} + +extract() { + WHAT="$1" + FILE="$2" + + awk " + /^# >>> $WHAT/ { + p = 1 + next + } + /^# <<</ { + if (p) + p = 0 + } + p + " $FILE \ + | sed -e 's/# //' \ + | sed -e 's/#$//' +} + +once() { + T="$1" + + if ! test -f $T + then + echo "invalid test file $T" >&2 + exit 1 + fi + + echo "$T... " + + if ! ./qbe $T -o $ASM + then + echo "[qbe fail]" + return 1 + fi + + extract driver $T > $DRV + extract output $T > $OUT + + if test -s $DRV + then + LNK="$DRV $ASM" + else + LNK="$ASM" + fi + + if ! cc -g -o $BIN $LNK + then + echo "[cc fail]" + return 1 + fi + + if test -s $OUT + then + $BIN a b c | diff - $OUT + RET=$? + REASON="output" + else + $BIN a b c + RET=$? + REASON="returned $RET" + fi + + if test $RET -ne 0 + then + echo "[$REASON fail]" + return 1 + fi + + printf "\033[1A\033[45C[ok]\n" +} + + +#trap cleanup TERM QUIT + +if test -z "$1" +then + echo "usage: test/go.sh {all, SSAFILE}" 2>&1 + exit 1 +fi + +case $1 in + "all") + F=0 + for T in test/[!_]*.ssa + do + once $T + F=`expr $F + $?` + done + if test $F -ge 1 + then + echo + echo "$F test(s) failed!" + else + echo + echo "All is fine!" + fi + ;; + *) + once $1 + exit $? + ;; +esac diff --git a/src/test/loop.ssa b/src/test/loop.ssa new file mode 100644 index 0000000..c8c4ee0 --- /dev/null +++ b/src/test/loop.ssa @@ -0,0 +1,23 @@ +# simple looping program +# sums all integers from 100 to 0 + +function $test() { +@start + +@loop + %s =w phi @start 0, @loop %s1 + %n =w phi @start 100, @loop %n1 + %s1 =w add %s, %n + %n1 =w sub %n, 1 + jnz %n1, @loop, @end + +@end + storew %s1, $a + ret +} + +# >>> driver +# extern void test(void); +# int a; +# int main() { test(); return !(a == 5050); } +# <<< diff --git a/src/test/mandel.ssa b/src/test/mandel.ssa new file mode 100644 index 0000000..efefeb3 --- /dev/null +++ b/src/test/mandel.ssa @@ -0,0 +1,123 @@ +# Print the Mandelbrot set on the +# terminal line output. + +function w $mandel(d %x, d %y) { +@mandel + %cr =d sub %y, d_0.5 + %ci =d copy %x +@loop + %i =w phi @mandel 0, @loop1 %i1 + %zr =d phi @mandel d_0, @loop1 %zr1 + %zi =d phi @mandel d_0, @loop1 %zi1 + %i1 =w add 1, %i + %tmp =d mul %zr, %zi + %zr2 =d mul %zr, %zr + %zi2 =d mul %zi, %zi + %zrx =d sub %zr2, %zi2 + %zr1 =d add %zrx, %cr + %zix =d add %tmp, %tmp + %zi1 =d add %zix, %ci + %sum =d add %zi2, %zr2 + %cmp1 =w cgtd %sum, d_16 + jnz %cmp1, @reti, @loop1 +@loop1 + %cmp2 =w csgtw %i1, 1000 + jnz %cmp2, @ret0, @loop +@reti + ret %i1 +@ret0 + ret 0 +} + +function w $main() { +@main +@loopy + %y =d phi @main d_-1, @loopy1 %y1 +@loopx + %x =d phi @loopy d_-1, @loopx1 %x1 + %i =w call $mandel(d %x, d %y) + jnz %i, @out, @in +@in + %r0 =w call $putchar(w 42) # '*' + jmp @loopx1 +@out + %r1 =w call $putchar(w 32) # ' ' + jmp @loopx1 +@loopx1 + %x1 =d add %x, d_0.032 + %cmp1 =w cgtd %x1, d_1 + jnz %cmp1, @loopy1, @loopx +@loopy1 + %r2 =w call $putchar(w 10) # '\n' + %y1 =d add %y, d_0.032 + %cmp2 =w cgtd %y1, d_1 + jnz %cmp2, @ret, @loopy +@ret + ret 0 +} + +# >>> output +# # +# # +# # +# # +# * # +# **** # +# **** # +# *** # +# ***** # +# ********* # +# ************ # +# ***************** # +# **************** # +# *************** # +# **************** # +# **************** # +# ***************** # +# **************** # +# **************** # +# ************** # +# ************* # +# ************ # +# ********* # +# ***** # +# *********** # +# ***************** # +# ********************** # +# * *********************** ** # +# *************************** # +# ***************************** # +# * ******************************* ** # +# ** *********************************** # +# *********************************** * # +# *********************************** # +# ************************************* # +# ************************************* # +# *************************************** # +# *************************************** # +# *************************************** # +# **************************************** # +# * **************************************** # +# ********************************************** **** # +# **************************************************** # +# * ***************************************************** # +# * ***************************************************** # +# ***** **************************************** **** # +# * **************************************** * # +# **************************************** # +# *************************************** # +# **************************************** # +# *************************************** # +# **************************************** # +# ************************************ # +# *********************************** # +# ********************************* # +# ************************************ # +# *** ************* ************** *** # +# *********** ************ ** # +# ******** ******** # +# ** * * # +# # +# # +# # +# <<< diff --git a/src/test/max.ssa b/src/test/max.ssa new file mode 100644 index 0000000..547e9d4 --- /dev/null +++ b/src/test/max.ssa @@ -0,0 +1,33 @@ +# find the maximum value +# in a nul-terminated array +# of unsigned bytes +# +# the output is stored in $a + +data $arr = { b 10, b -60, b 10, b 100, b 200, b 0 } + +function $test() { +@start +@loop + %max =w phi @start -1, @new %byt, @old %max + %loc =l phi @start $arr, @new %loc1, @old %loc1 + %byt =w loadub %loc + %loc1 =l add 1, %loc + jnz %byt, @iter, @end +@iter + %cmp =w cslew %max, %byt + jnz %cmp, @new, @old +@new + jmp @loop +@old + jmp @loop +@end + storew %max, $a + ret +} + +# >>> driver +# extern void test(void); +# int a; +# int main() { test(); return !(a == 200); } +# <<< diff --git a/src/test/prime.ssa b/src/test/prime.ssa new file mode 100644 index 0000000..12d0273 --- /dev/null +++ b/src/test/prime.ssa @@ -0,0 +1,32 @@ +# find the 10,001st prime +# store it in a + +function $test() { +@start +@loop + %n =w phi @start 5, @tloop %n, @yes %n1 + %p =w phi @start 13, @tloop %p1, @yes %p1 + %p1 =w add %p, 2 +@tloop + %t =w phi @loop 3, @next %t1 + %r =w rem %p, %t + jnz %r, @next, @loop +@next + %t1 =w add 2, %t + %tsq =w mul %t1, %t1 + %c0 =w csgtw %tsq, %p + jnz %c0, @yes, @tloop +@yes + %n1 =w add 1, %n + %c1 =w ceqw 10001, %n1 + jnz %c1, @end, @loop +@end + storew %p, $a + ret +} + +# >>> driver +# extern void test(void); +# int a; +# int main() { test(); return !(a == 104743); } +# <<< diff --git a/src/test/puts10.ssa b/src/test/puts10.ssa new file mode 100644 index 0000000..1dcf227 --- /dev/null +++ b/src/test/puts10.ssa @@ -0,0 +1,29 @@ +function $main() { +@start + %y =l alloc4 4 + %y1 =l add %y, 1 + storeb 0, %y1 +@loop + %n =w phi @start 0, @loop %n1 + %c =w add %n, 48 + storeb %c, %y + %r =w call $puts(l %y) + %n1 =w add %n, 1 + %cmp =w cslew %n1, 9 + jnz %cmp, @loop, @end +@end + ret +} + +# >>> output +# 0 +# 1 +# 2 +# 3 +# 4 +# 5 +# 6 +# 7 +# 8 +# 9 +# <<< diff --git a/src/test/sum.ssa b/src/test/sum.ssa new file mode 100644 index 0000000..266054e --- /dev/null +++ b/src/test/sum.ssa @@ -0,0 +1,31 @@ +# Simple test for addressing modes. + +function w $sum(l %arr, w %num) { +@start +@loop + %n1 =w phi @start %num, @loop1 %n2 + %s0 =w phi @start 0, @loop1 %s1 + %n2 =w sub %n1, 1 + %c =w cslew %n1, 0 + jnz %c, @end, @loop1 +@loop1 + %idx0 =l extsw %n2 + %idx1 =l mul 4, %idx0 + %idx2 =l add %idx1, %arr + %w =w loadw %idx2 + %s1 =w add %w, %s0 + jmp @loop +@end + ret %s0 +} + +# >>> driver +# extern int sum(int *, int); +# int arr[] = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21 }; +# #define N sizeof arr / sizeof arr[0] +# int main() { +# int i, s; +# for (s=i=0; i<N; i++) s+=arr[i]; +# return !(sum(arr, N) == s); +# } +# <<< diff --git a/src/tools/abi.ml b/src/tools/abi.ml new file mode 100644 index 0000000..d845c74 --- /dev/null +++ b/src/tools/abi.ml @@ -0,0 +1,532 @@ +(* fuzzer *) + +type _ bty = + | Char: int bty + | Short: int bty + | Int: int bty + | Long: int bty + | Float: float bty + | Double: float bty + +type _ sty = + | Field: 'a bty * 'b sty -> ('a * 'b) sty + | Empty: unit sty + +type _ aty = + | Base: 'a bty -> 'a aty + | Struct: 'a sty -> 'a aty + +type anyb = AB: _ bty -> anyb (* kinda boring... *) +type anys = AS: _ sty -> anys +type anya = AA: _ aty -> anya +type testb = TB: 'a bty * 'a -> testb +type testa = TA: 'a aty * 'a -> testa + + +let align a x = + let m = x mod a in + if m <> 0 then x + (a-m) else x + +let btysize: type a. a bty -> int = function + | Char -> 1 + | Short -> 2 + | Int -> 4 + | Long -> 8 + | Float -> 4 + | Double -> 8 + +let btyalign = btysize + +let styempty: type a. a sty -> bool = function + | Field _ -> false + | Empty -> true + +let stysize s = + let rec f: type a. int -> a sty -> int = + fun sz -> function + | Field (b, s) -> + let a = btyalign b in + f (align a sz + btysize b) s + | Empty -> sz in + f 0 s + +let rec styalign: type a. a sty -> int = function + | Field (b, s) -> max (btyalign b) (styalign s) + | Empty -> 1 + + +(* Generate types and test vectors. *) +module Gen = struct + module R = Random + + let init = function + | None -> + let f = open_in "/dev/urandom" in + let seed = + Char.code (input_char f) lsl 8 + + Char.code (input_char f) in + close_in f; + R.init seed; + seed + | Some seed -> + R.init seed; + seed + + let int sz = + let bound = 1 lsl (8 * min sz 3 - 1) in + let i = R.int bound in + if R.bool () then - i else i + + let float () = + let f = R.float 1000. in + if R.bool () then -. f else f + + let testv: type a. a aty -> a = + let tb: type a. a bty -> a = function (* eh, dry... *) + | Float -> float () + | Double -> float () + | Char -> int (btysize Char) + | Short -> int (btysize Short) + | Int -> int (btysize Int) + | Long -> int (btysize Long) in + let rec ts: type a. a sty -> a = function + | Field (b, s) -> (tb b, ts s) + | Empty -> () in + function + | Base b -> tb b + | Struct s -> ts s + + let b () = (* uniform *) + match R.int 6 with + | 0 -> AB Char + | 1 -> AB Short + | 2 -> AB Int + | 3 -> AB Long + | 4 -> AB Float + | _ -> AB Double + + let smax = 5 (* max elements in structs *) + let structp = 0.3 (* odds of having a struct type *) + let amax = 8 (* max function arguments *) + + let s () = + let rec f n = + if n = 0 then AS Empty else + let AB bt = b () in + let AS st = f (n-1) in + AS (Field (bt, st)) in + f (1 + R.int (smax-1)) + + let a () = + if R.float 1.0 > structp then + let AB bt = b () in + AA (Base bt) + else + let AB bt = b () in + let AS st = s () in + AA (Struct (Field (bt, st))) + + let test () = + let AA ty = a () in + let t = testv ty in + TA (ty, t) + + let tests () = + let rec f n = + if n = 0 then [] else + test () :: f (n-1) in + f (R.int amax) + +end + + +(* Code generation for C *) +module OutC = struct + open Printf + + let ctypelong oc name = + let cb: type a. a bty -> unit = function + | Char -> fprintf oc "char" + | Short -> fprintf oc "short" + | Int -> fprintf oc "int" + | Long -> fprintf oc "long" + | Float -> fprintf oc "float" + | Double -> fprintf oc "double" in + let rec cs: type a. int -> a sty -> unit = + fun i -> function + | Field (b, s) -> + cb b; + fprintf oc " f%d; " i; + cs (i+1) s; + | Empty -> () in + function + | Base b -> + cb b; + | Struct s -> + fprintf oc "struct %s { " name; + cs 1 s; + fprintf oc "}"; + () + + let ctype: type a. out_channel -> string -> a aty -> unit = + fun oc name -> function + | Struct _ -> fprintf oc "struct %s" name + | t -> ctypelong oc "" t + + let base: type a. out_channel -> a bty * a -> unit = + fun oc -> function + | Char, i -> fprintf oc "%d" i + | Short, i -> fprintf oc "%d" i + | Int, i -> fprintf oc "%d" i + | Long, i -> fprintf oc "%d" i + | Float, f -> fprintf oc "%ff" f + | Double, f -> fprintf oc "%f" f + + let init oc name (TA (ty, t)) = + let inits s = + let rec f: type a. a sty * a -> unit = function + | Field (b, s), (tb, ts) -> + base oc (b, tb); + fprintf oc ", "; + f (s, ts) + | Empty, () -> () in + fprintf oc "{ "; + f s; + fprintf oc "}"; in + ctype oc name ty; + fprintf oc " %s = " name; + begin match (ty, t) with + | Base b, tb -> base oc (b, tb) + | Struct s, ts -> inits (s, ts) + end; + fprintf oc ";\n"; + () + + let extension = ".c" + + let comment oc s = + fprintf oc "/* %s */\n" s + + let prelude oc = List.iter (fprintf oc "%s\n") + [ "#include <stdio.h>" + ; "#include <stdlib.h>" + ; "" + ; "static void fail(char *chk)" + ; "{" + ; "\tfprintf(stderr, \"fail: checking %s\\n\", chk);" + ; "\tabort();" + ; "}" + ; "" + ] + + let typedef oc name = function + | TA (Struct ts, _) -> + ctypelong oc name (Struct ts); + fprintf oc ";\n"; + | _ -> () + + let check oc name = + let chkbase: type a. string -> a bty * a -> unit = + fun name t -> + fprintf oc "\tif (%s != " name; + base oc t; + fprintf oc ")\n\t\tfail(%S);\n" name; in + function + | TA (Base b, tb) -> chkbase name (b, tb) + | TA (Struct s, ts) -> + let rec f: type a. int -> a sty * a -> unit = + fun i -> function + | Field (b, s), (tb, ts) -> + chkbase (Printf.sprintf "%s.f%d" name i) (b, tb); + f (i+1) (s, ts); + | Empty, () -> () in + f 1 (s, ts) + + let argname i = "arg" ^ string_of_int (i+1) + + let proto oc (TA (tret, _)) args = + ctype oc "ret" tret; + fprintf oc " f("; + let narg = List.length args in + List.iteri (fun i (TA (targ, _)) -> + ctype oc (argname i) targ; + fprintf oc " %s" (argname i); + if i <> narg-1 then + fprintf oc ", "; + ) args; + fprintf oc ")"; + () + + let caller oc ret args = + let narg = List.length args in + prelude oc; + typedef oc "ret" ret; + List.iteri (fun i arg -> + typedef oc (argname i) arg; + ) args; + proto oc ret args; + fprintf oc ";\n\nint main()\n{\n"; + List.iteri (fun i arg -> + fprintf oc "\t"; + init oc (argname i) arg; + ) args; + fprintf oc "\t"; + let TA (tret, _) = ret in + ctype oc "ret" tret; + fprintf oc " ret;\n\n"; + fprintf oc "\tret = f("; + List.iteri (fun i _ -> + fprintf oc "%s" (argname i); + if i <> narg-1 then + fprintf oc ", "; + ) args; + fprintf oc ");\n"; + check oc "ret" ret; + fprintf oc "\n\treturn 0;\n}\n"; + () + + let callee oc ret args = + prelude oc; + typedef oc "ret" ret; + List.iteri (fun i arg -> + typedef oc (argname i) arg; + ) args; + fprintf oc "\n"; + proto oc ret args; + fprintf oc "\n{\n\t"; + init oc "ret" ret; + fprintf oc "\n"; + List.iteri (fun i arg -> + check oc (argname i) arg; + ) args; + fprintf oc "\n\treturn ret;\n}\n"; + () + +end + +(* Code generation for QBE *) +module OutIL = struct + open Printf + + let comment oc s = + fprintf oc "# %s\n" s + + let tmp, lbl = + let next = ref 0 in + (fun () -> incr next; "%t" ^ (string_of_int !next)), + (fun () -> incr next; "@l" ^ (string_of_int !next)) + + let bvalue: type a. a bty * a -> string = function + | Char, i -> sprintf "%d" i + | Short, i -> sprintf "%d" i + | Int, i -> sprintf "%d" i + | Long, i -> sprintf "%d" i + | Float, f -> sprintf "s_%f" f + | Double, f -> sprintf "d_%f" f + + let btype: type a. a bty -> string = function + | Char -> "w" + | Short -> "w" + | Int -> "w" + | Long -> "l" + | Float -> "s" + | Double -> "d" + + let extension = ".ssa" + + let argname i = "arg" ^ string_of_int (i+1) + + let siter oc base s g = + let rec f: type a. int -> int -> a sty * a -> unit = + fun id off -> function + | Field (b, s), (tb, ts) -> + let off = align (btyalign b) off in + let addr = tmp () in + fprintf oc "\t%s =l add %d, %s\n" addr off base; + g id addr (TB (b, tb)); + f (id + 1) (off + btysize b) (s, ts); + | Empty, () -> () in + f 0 0 s + + let bmemtype b = + if AB b = AB Char then "b" else + if AB b = AB Short then "h" else + btype b + + let init oc = function + | TA (Base b, tb) -> bvalue (b, tb) + | TA (Struct s, ts) -> + let base = tmp () in + fprintf oc "\t%s =l alloc%d %d\n" + base (styalign s) (stysize s); + siter oc base (s, ts) + begin fun _ addr (TB (b, tb)) -> + fprintf oc "\tstore%s %s, %s\n" + (bmemtype b) (bvalue (b, tb)) addr; + end; + base + + let check oc id name = + let bcheck = fun id name (b, tb) -> + let tcmp = tmp () in + let nxtl = lbl () in + fprintf oc "\t%s =w ceq%s %s, %s\n" + tcmp (btype b) name (bvalue (b, tb)); + fprintf oc "\tstorew %d, %%failcode\n" id; + fprintf oc "\tjnz %s, %s, @fail\n" tcmp nxtl; + fprintf oc "%s\n" nxtl; in + function + | TA (Base Char, i) -> + let tval = tmp () in + fprintf oc "\t%s =w extsb %s\n" tval name; + bcheck id tval (Int, i) + | TA (Base Short, i) -> + let tval = tmp () in + fprintf oc "\t%s =w extsh %s\n" tval name; + bcheck id tval (Int, i) + | TA (Base b, tb) -> + bcheck id name (b, tb) + | TA (Struct s, ts) -> + siter oc name (s, ts) + begin fun id' addr (TB (b, tb)) -> + let tval = tmp () in + let lsuffix = + if AB b = AB Char then "sb" else + if AB b = AB Short then "sh" else + "" in + fprintf oc "\t%s =%s load%s %s\n" + tval (btype b) lsuffix addr; + bcheck (100*id + id'+1) tval (b, tb); + end; + () + + let ttype name = function + | TA (Base b, _) -> btype b + | TA (Struct _, _) -> ":" ^ name + + let typedef oc name = + let rec f: type a. a sty -> unit = function + | Field (b, s) -> + fprintf oc "%s" (bmemtype b); + if not (styempty s) then + fprintf oc ", "; + f s; + | Empty -> () in + function + | TA (Struct ts, _) -> + fprintf oc "type :%s = { " name; + f ts; + fprintf oc " }\n"; + | _ -> () + + let postlude oc = List.iter (fprintf oc "%s\n") + [ "@fail" + ; "# failure code" + ; "\t%fcode =w loadw %failcode" + ; "\t%f0 =w call $printf(l $failstr, w %fcode)" + ; "\t%f1 =w call $abort()" + ; "\tret 0" + ; "}" + ; "" + ; "data $failstr = { b \"fail on check %d\\n\", b 0 }" + ] + + let caller oc ret args = + let narg = List.length args in + List.iteri (fun i arg -> + typedef oc (argname i) arg; + ) args; + typedef oc "ret" ret; + fprintf oc "\nfunction w $main() {\n"; + fprintf oc "@start\n"; + fprintf oc "\t%%failcode =l alloc4 4\n"; + let targs = List.mapi (fun i arg -> + comment oc ("define argument " ^ (string_of_int (i+1))); + (ttype (argname i) arg, init oc arg) + ) args in + comment oc "call test function"; + fprintf oc "\t%%ret =%s call $f(" (ttype "ret" ret); + List.iteri (fun i (ty, tmp) -> + fprintf oc "%s %s" ty tmp; + if i <> narg-1 then + fprintf oc ", "; + ) targs; + fprintf oc ")\n"; + comment oc "check the return value"; + check oc 0 "%ret" ret; + fprintf oc "\tret 0\n"; + postlude oc; + () + + let callee oc ret args = + let narg = List.length args in + List.iteri (fun i arg -> + typedef oc (argname i) arg; + ) args; + typedef oc "ret" ret; + fprintf oc "\nfunction %s $f(" (ttype "ret" ret); + List.iteri (fun i arg -> + let a = argname i in + fprintf oc "%s %%%s" (ttype a arg) a; + if i <> narg-1 then + fprintf oc ", "; + ) args; + fprintf oc ") {\n"; + fprintf oc "@start\n"; + fprintf oc "\t%%failcode =l alloc4 4\n"; + List.iteri (fun i arg -> + comment oc ("checking argument " ^ (string_of_int (i+1))); + check oc (i+1) ("%" ^ argname i) arg; + ) args; + comment oc "define the return value"; + let rettmp = init oc ret in + fprintf oc "\tret %s\n" rettmp; + postlude oc; + () + +end + + +module type OUT = sig + val extension: string + val comment: out_channel -> string -> unit + val caller: out_channel -> testa -> testa list -> unit + val callee: out_channel -> testa -> testa list -> unit +end + +let _ = + let usage code = + Printf.eprintf "usage: abi.ml [-s SEED] DIR {c,ssa} {c,ssa}\n"; + exit code in + + let outmod = function + | "c" -> (module OutC : OUT) + | "ssa" -> (module OutIL: OUT) + | _ -> usage 1 in + + let seed, dir, mcaller, mcallee = + match Sys.argv with + | [| _; "-s"; seed; dir; caller; callee |] -> + let seed = + try Some (int_of_string seed) with + Failure _ -> usage 1 in + seed, dir, outmod caller, outmod callee + | [| _; dir; caller; callee |] -> + None, dir, outmod caller, outmod callee + | [| _; "-h" |] -> + usage 0 + | _ -> + usage 1 in + + let seed = Gen.init seed in + let tret = Gen.test () in + let targs = Gen.tests () in + let module OCaller = (val mcaller : OUT) in + let module OCallee = (val mcallee : OUT) in + let ocaller = open_out (dir ^ "/caller" ^ OCaller.extension) in + let ocallee = open_out (dir ^ "/callee" ^ OCallee.extension) in + OCaller.comment ocaller (Printf.sprintf "seed %d" seed); + OCallee.comment ocallee (Printf.sprintf "seed %d" seed); + OCaller.caller ocaller tret targs; + OCallee.callee ocallee tret targs; + () diff --git a/src/tools/abitest.sh b/src/tools/abitest.sh new file mode 100755 index 0000000..d5b16e5 --- /dev/null +++ b/src/tools/abitest.sh @@ -0,0 +1,104 @@ +#!/bin/sh + +OCAMLC=/usr/bin/ocamlc +QBE=`pwd`/qbe + +failure() { + echo "Failure at stage:" $1 >&2 + exit 1 +} + +cleanup() { + rm -fr $TMP +} + +init() { + cp tools/abi.ml $TMP + pushd $TMP > /dev/null + + cat > Makefile << EOM + +.PHONY: test +test: caller.o callee.o + c99 -o \$@ caller.o callee.o +%.o: %.c + c99 -c -o \$@ \$< +%.o: %.ssa + $QBE -o \$*.s \$< + c99 -c -o \$@ \$*.s + +EOM + + if ! $OCAMLC abi.ml -o gentest + then + popd > /dev/null + cleanup + failure "abifuzz compilation" + fi + popd > /dev/null +} + +once() { + if test -z "$3" + then + $TMP/gentest $TMP $1 $2 + else + $TMP/gentest -s $3 $TMP $1 $2 + fi + make -C $TMP test > /dev/null || failure "building" + $TMP/test || failure "runtime" +} + +usage() { + echo "usage: abitest.sh [-callssa] [-callc] [-s SEED] [-n ITERATIONS]" >&2 + exit 1 +} + +N=1 +CALLER=c +CALLEE=ssa + +while test -n "$1" +do + case "$1" in + "-callssa") + ;; + "-callc") + CALLER=ssa + CALLEE=c + ;; + "-s") + test -n "$2" || usage + shift + SEED="$1" + ;; + "-n") + test -n "$2" || usage + shift + N="$1" + ;; + *) + usage + ;; + esac + shift +done + +TMP=`mktemp -d abifuzz.XXXXXX` + +init + +if test -n "$S" +then + once $CALLER $CALLEE $SEED +else + for n in `seq $N` + do + once $CALLER $CALLEE + echo "$n" | grep "00$" + done +fi + +echo "All done." + +cleanup diff --git a/src/tools/fptox.c b/src/tools/fptox.c new file mode 100644 index 0000000..a2bc155 --- /dev/null +++ b/src/tools/fptox.c @@ -0,0 +1,18 @@ +#include <stdio.h> +#include <stdlib.h> + +int +main(int ac, char *av[]) +{ + double d; + float f; + + if (ac < 2) { + usage: + fputs("usage: fptox NUMBER\n", stderr); + return 1; + } + f = d = strtod(av[1], 0); + printf("0x%08x 0x%016llx\n", *(unsigned *)&f, *(unsigned long long*)&d); + return 0; +} diff --git a/src/tools/pmov.c b/src/tools/pmov.c new file mode 100644 index 0000000..efbecd7 --- /dev/null +++ b/src/tools/pmov.c @@ -0,0 +1,252 @@ +/*% rm -f rega.o main.o && cc -g -std=c99 -Wall -DTEST_PMOV -o # % *.o + * + * This is a test framwork for the dopm() function + * in rega.c, use it when you want to modify it or + * all the parallel move functions. + * + * You might need to decrease NIReg to see it + * terminate, I used NIReg == 7 at most. + */ +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +static void assert_test(char *, int), fail(void), iexec(int *); + +#include "../rega.c" + +static RMap mbeg; +static Ins ins[NIReg], *ip; +static Blk dummyb = { .ins = ins }; + +int +main() +{ + Ins *i1; + unsigned long long tm, rm, cnt; + RMap mend; + int reg[NIReg], val[NIReg+1]; + int t, i, r, nr; + + tmp = (Tmp[Tmp0+NIReg]){{{0}}}; + for (t=0; t<Tmp0+NIReg; t++) + if (t >= Tmp0) { + tmp[t].cls = Kw; + tmp[t].hint.r = -1; + tmp[t].hint.m = 0; + tmp[t].slot = -1; + sprintf(tmp[t].name, "tmp%d", t-Tmp0+1); + } + + bsinit(mbeg.b, Tmp0+NIReg); + bsinit(mend.b, Tmp0+NIReg); + cnt = 0; + for (tm = 0; tm < 1ull << (2*NIReg); tm++) { + mbeg.n = 0; + bszero(mbeg.b); + ip = ins; + + /* find what temporaries are in copy and + * wether or not they are in register + */ + for (t=0; t<NIReg; t++) + switch ((tm >> (2*t)) & 3) { + case 0: + /* not in copy, not in reg */ + break; + case 1: + /* not in copy, in reg */ + radd(&mbeg, Tmp0+t, t+1); + break; + case 2: + /* in copy, not in reg */ + *ip++ = (Ins){OCopy, TMP(Tmp0+t), {R, R}, Kw}; + break; + case 3: + /* in copy, in reg */ + *ip++ = (Ins){OCopy, TMP(Tmp0+t), {R, R}, Kw}; + radd(&mbeg, Tmp0+t, t+1); + break; + } + + if (ip == ins) + /* cancel if the parallel move + * is empty + */ + goto Nxt; + + /* find registers for temporaries + * in mbeg + */ + nr = ip - ins; + rm = (1ull << (nr+1)) - 1; + for (i=0; i<nr; i++) + reg[i] = i+1; + + for (;;) { + /* set registers on copies + */ + for (i=0, i1=ins; i1<ip; i1++, i++) + i1->arg[0] = TMP(reg[i]); + + /* compile the parallel move + */ + rcopy(&mend, &mbeg); + dopm(&dummyb, ip-1, &mend); + cnt++; + + /* check that mend contain mappings for + * source registers and does not map any + * assigned temporary, then check that + * all temporaries in mend are mapped in + * mbeg and not used in the copy + */ + for (i1=ins; i1<ip; i1++) { + r = i1->arg[0].val; + assert(rfree(&mend, r) == r); + t = i1->to.val; + assert(!bshas(mend.b, t)); + } + for (i=0; i<mend.n; i++) { + t = mend.t[i]; + assert(bshas(mbeg.b, t)); + t -= Tmp0; + assert(((tm >> (2*t)) & 3) == 1); + } + + /* execute the code generated and check + * that all assigned temporaries got their + * value, and that all live variables's + * content got preserved + */ + for (i=1; i<=NIReg; i++) + val[i] = i; + iexec(val); + for (i1=ins; i1<ip; i1++) { + t = i1->to.val; + r = rfind(&mbeg, t); + if (r != -1) + assert(val[r] == i1->arg[0].val); + } + for (i=0; i<mend.n; i++) { + t = mend.t[i]; + r = mend.r[i]; + assert(val[t-Tmp0+1] == r); + } + + /* find the next register assignment */ + i = nr - 1; + for (;;) { + r = reg[i]; + rm &= ~(1ull<<r); + do + r++; + while (r <= NIReg && (rm & (1ull<<r))); + if (r == NIReg+1) { + if (i == 0) + goto Nxt; + i--; + } else { + rm |= (1ull<<r); + reg[i++] = r; + break; + } + } + for (; i<nr; i++) + for (r=1; r<=NIReg; r++) + if (!(rm & (1ull<<r))) { + rm |= (1ull<<r); + reg[i] = r; + break; + } + } + Nxt: ; + } + printf("%llu tests successful!\n", cnt); + exit(0); +} + + +/* execute what pmgen() wrote (swap, copy) */ + +#define validr(r) \ + rtype(r) == RTmp && \ + r.val > 0 && \ + r.val <= NIReg + +static void +iexec(int val[]) +{ + Ins *i; + int t; + + for (i=insb; i<curi; i++) + switch (i->op) { + default: + assert(!"iexec: missing case\n"); + exit(1); + case OSwap: + assert(validr(i->arg[0])); + assert(validr(i->arg[1])); + t = val[i->arg[0].val]; + val[i->arg[0].val] = val[i->arg[1].val]; + val[i->arg[1].val] = t; + break; + case OCopy: + assert(validr(i->to)); + assert(validr(i->arg[0])); + val[i->to.val] = val[i->arg[0].val]; + break; + } +} + + +/* failure diagnostics */ + +static int re; + +static void +replay() +{ + RMap mend; + + re = 1; + bsinit(mend.b, Tmp0+NIReg); + rcopy(&mend, &mbeg); + dopm(&dummyb, ip-1, &mend); +} + +static void +fail() +{ + Ins *i1; + int i; + + printf("\nIn registers: "); + for (i=0; i<mbeg.n; i++) + printf("%s(r%d) ", + tmp[mbeg.t[i]].name, + mbeg.r[i]); + printf("\n"); + printf("Parallel move:\n"); + for (i1=ins; i1<ip; i1++) + printf("\t %s <- r%d\n", + tmp[i1->to.val].name, + i1->arg[0].val); + replay(); + abort(); +} + +static void +assert_test(char *s, int x) +{ + if (x) + return; + if (re) + abort(); + printf("!assertion failure: %s\n", s); + fail(); +} + +/* symbols required by the linker */ +char debug['Z'+1]; diff --git a/src/tools/regress.sh b/src/tools/regress.sh new file mode 100755 index 0000000..4106b00 --- /dev/null +++ b/src/tools/regress.sh @@ -0,0 +1,17 @@ +#!/bin/sh + +for t in test/* +do + printf "Test $t ... " + + ./qbe $t >/tmp/out.0 2>&1 + ./qbe.1 $t >/tmp/out.1 2>&1 + + if diff /tmp/out.0 /tmp/out.1 > /dev/null + then + echo "OK" + else + echo "KO" + break + fi +done diff --git a/src/util.c b/src/util.c new file mode 100644 index 0000000..65b3ff8 --- /dev/null +++ b/src/util.c @@ -0,0 +1,329 @@ +#include "all.h" + +typedef struct Bitset Bitset; +typedef struct Vec Vec; + +struct Vec { + ulong mag; + size_t esz; + ulong cap; + union { + long long ll; + long double ld; + void *ptr; + } align[]; +}; + +enum { + VMin = 2, + VMag = 0xcabba9e, + NPtr = 256, +}; + +Typ typ[NTyp]; +Ins insb[NIns], *curi; + +static void *ptr[NPtr]; +static void **pool = ptr; +static int nptr = 1; + +void +diag(char *s) +{ + fputs(s, stderr); + fputc('\n', stderr); + abort(); +} + +void * +emalloc(size_t n) +{ + void *p; + + p = calloc(1, n); + if (!p) + diag("emalloc: out of memory"); + return p; +} + +void * +alloc(size_t n) +{ + void **pp; + + if (n == 0) + return 0; + if (nptr >= NPtr) { + pp = emalloc(NPtr * sizeof(void *)); + pp[0] = pool; + pool = pp; + nptr = 1; + } + return pool[nptr++] = emalloc(n); +} + +void +freeall() +{ + void **pp; + + for (;;) { + for (pp = &pool[1]; pp < &pool[nptr]; pp++) + free(*pp); + pp = pool[0]; + if (!pp) + break; + free(pool); + pool = pp; + nptr = NPtr; + } + nptr = 1; +} + +Blk * +blknew() +{ + static Blk z; + Blk *b; + + b = alloc(sizeof *b); + *b = z; + return b; +} + +void +emit(int op, int k, Ref to, Ref arg0, Ref arg1) +{ + if (curi == insb) + diag("emit: too many instructions"); + *--curi = (Ins){ + .op = op, .cls = k, + .to = to, .arg = {arg0, arg1} + }; +} + +void +emiti(Ins i) +{ + emit(i.op, i.cls, i.to, i.arg[0], i.arg[1]); +} + +void +idup(Ins **pd, Ins *s, ulong n) +{ + *pd = alloc(n * sizeof(Ins)); + memcpy(*pd, s, n * sizeof(Ins)); +} + +Ins * +icpy(Ins *d, Ins *s, ulong n) +{ + memcpy(d, s, n * sizeof(Ins)); + return d + n; +} + +void * +vnew(ulong len, size_t esz) +{ + ulong cap; + Vec *v; + + for (cap=VMin; cap<len; cap*=2) + ; + v = alloc(cap * esz + sizeof(Vec)); + v->mag = VMag; + v->cap = cap; + v->esz = esz; + return v + 1; +} + +void +vgrow(void *vp, ulong len) +{ + Vec *v; + void *v1; + + v = *(Vec **)vp - 1; + assert(v+1 && v->mag == VMag); + if (v->cap >= len) + return; + v1 = vnew(len, v->esz); + memcpy(v1, v+1, v->cap * v->esz); + *(Vec **)vp = v1; +} + +int +phicls(int t, Tmp *tmp /*, int c*/) +{ + if (tmp[t].phi) + return tmp[t].phi; + return t; +#if 0 + int t1; + + t1 = tmp[t].phi; + if (!t1) + t1 = t; + if (t != t1) { + t1 = phitmp(t1, tmp, c); + if (c) + tmp[t].phi = t1; + } + return t1; +#endif +} + +Ref +newtmp(char *prfx, int k, Fn *fn) +{ + static int n; + int t; + + t = fn->ntmp++; + vgrow(&fn->tmp, fn->ntmp); + sprintf(fn->tmp[t].name, "%s%d", prfx, ++n); + fn->tmp[t].cls = k; + fn->tmp[t].slot = -1; + fn->tmp[t].nuse = +1; + fn->tmp[t].ndef = +1; + return TMP(t); +} + +Ref +getcon(int64_t val, Fn *fn) +{ + int c; + + for (c=0; c<fn->ncon; c++) + if (fn->con[c].type == CBits && fn->con[c].bits.i == val) + return CON(c); + fn->ncon++; + vgrow(&fn->con, fn->ncon); + fn->con[c] = (Con){.type = CBits, .bits.i = val}; + return CON(c); +} + +void +addcon(Con *c0, Con *c1) +{ + if (c0->type == CUndef) + *c0 = *c1; + else { + if (c1->type == CAddr) { + if (c0->type == CAddr) + diag("addcon: adding two addresses"); + c0->type = CAddr; + strcpy(c0->label, c1->label); + } + c0->bits.i += c1->bits.i; + } +} + +void +bsinit(BSet *bs, uint n) +{ + n = (n + NBit-1) / NBit; + bs->nt = n; + bs->t = alloc(n * sizeof bs->t[0]); +} + +uint +bscount(BSet *bs) +{ + uint i, j, n; + + n = 0; + for (i=0; i<bs->nt; i++) + for (j=0; j<NBit; j++) + if (bs->t[i] & BIT(j)) + n++; + return n; +} + +static inline uint +bsmax(BSet *bs) +{ + return bs->nt * NBit; +} + +void +bsset(BSet *bs, uint elt) +{ + assert(elt < bsmax(bs)); + bs->t[elt/NBit] |= BIT(elt%NBit); +} + +void +bsclr(BSet *bs, uint elt) +{ + assert(elt < bsmax(bs)); + bs->t[elt/NBit] &= ~BIT(elt%NBit); +} + +#define BSOP(f, op) \ + void \ + f(BSet *a, BSet *b) \ + { \ + uint i; \ + \ + assert(a->nt == b->nt); \ + for (i=0; i<a->nt; i++) \ + a->t[i] op b->t[i]; \ + } + +BSOP(bscopy, =) +BSOP(bsunion, |=) +BSOP(bsinter, &=) +BSOP(bsdiff, &= ~) + +int +bsequal(BSet *a, BSet *b) +{ + uint i; + + assert(a->nt == b->nt); + for (i=0; i<a->nt; i++) + if (a->t[i] != b->t[i]) + return 0; + return 1; +} + +void +bszero(BSet *bs) +{ + memset(bs->t, 0, bs->nt * sizeof bs->t[0]); +} + +/* iterates on a bitset, use as follows + * + * for (i=0; bsiter(set, &i); i++) + * use(i); + * + */ +int +bsiter(BSet *bs, uint *elt) +{ + uint i; + + for (i=*elt;; i++) { + while (i < bsmax(bs) && !bs->t[i/NBit]) + i = (i + NBit) & -NBit; + if (i >= bsmax(bs)) + return 0; + if (bshas(bs, i)) { + *elt = i; + return 1; + } + } +} + +void +dumpts(BSet *bs, Tmp *tmp, FILE *f) +{ + uint t; + + fprintf(f, "["); + for (t=Tmp0; bsiter(bs, &t); t++) + fprintf(f, " %s", tmp[t].name); + fprintf(f, " ]\n"); +} |