diff options
Diffstat (limited to 'limbo/optim.c')
| -rw-r--r-- | limbo/optim.c | 1803 |
1 files changed, 1803 insertions, 0 deletions
diff --git a/limbo/optim.c b/limbo/optim.c new file mode 100644 index 00000000..a3ccdec3 --- /dev/null +++ b/limbo/optim.c @@ -0,0 +1,1803 @@ +#include "limbo.h" + +#define bzero bbzero /* bsd name space pollution */ +/* + (r, s) := f(); => r, s have def on same pc + s = g(); => this def kills previous r def (and s def) + solution: r has def pc, s has def pc+1 and next instruction has pc pc+2 +*/ + +#define BLEN (8*sizeof(ulong)) +#define BSHIFT 5 /* assumes ulong 4 */ +#define BMASK (BLEN-1) + +#define SIGN(n) (1<<(n-1)) +#define MSK(n) (SIGN(n)|(SIGN(n)-1)) +#define MASK(a, b) (MSK((b)-(a)+1)<<(a)) + +#define isnilsrc(s) ((s)->start.line == 0 && (s)->stop.line == 0 && (s)->start.pos == 0 && (s)->stop.pos == 0) + +#define limbovar(d) ((d)->sym->name[0] != '.') +#define structure(t) ((t)->kind == Tadt || (t)->kind == Ttuple) + +enum +{ + Bclr, + Band, + Bandinv, + Bstore, + Bandrev, + Bnoop, + Bxor, + Bor, + Bnor, + Bequiv, + Binv, + Bimpby, + Brev, + Bimp, + Bnand, + Bset, +}; + +enum +{ + Suse = 1, + Muse = 2, + Duse = 4, + Sdef = 8, + Mdef = 16, + Ddef = 32, + Tuse1 = 64, /* fixed point temporary */ + Tuse2 = 128, /* fixed point temporary */ + Mduse = 256, /* D used if M nil */ + + None = 0, + Unop = Suse|Ddef, + Cunop = Muse|Ddef, + Threop = Suse|Muse|Ddef, + Binop = Suse|Muse|Ddef|Mduse, + Mbinop = Suse|Mdef|Duse, /* strange */ + Abinop=Suse|Duse|Ddef, + Mabinop = Suse|Muse|Duse|Ddef, + Use1 = Suse, + Use2 = Suse|Duse, + Use3 = Suse|Muse|Duse, +}; + +enum +{ + Sshift = 10, + Mshift = 5, + Dshift = 0, +}; + +#define S(x) ((x)<<Sshift) +#define M(x) ((x)<<Mshift) +#define D(x) ((x)<<Dshift) + +#define SS(x) (((x)>>Sshift)&0x1f) +#define SM(x) (((x)>>Mshift)&0x1f) +#define SD(x) (((x)>>Dshift)&0x1f) + +enum +{ + I = 0, /* ignore */ + B = 1, /* byte */ + W = 4, /* int */ + P = 4, /* pointer */ + A = 4, /* array */ + C = 4, /* string */ + X = 4, /* fixed */ + R = 4, /* float */ + L = 8, /* big */ + F = 8, /* real */ + Sh = 2, /* short */ + Pc = 4, /* pc */ + Mp = 16, /* memory */ + + Bop2 = S(B)|D(B), + Bop = S(B)|M(B)|D(B), + Bopb = S(B)|M(B)|D(Pc), + Wop2 = S(W)|D(W), + Wop = S(W)|M(W)|D(W), + Wopb = S(W)|M(W)|D(Pc), + Lop2 = S(L)|D(L), + Lop = S(L)|M(L)|D(L), + Lopb = S(L)|M(L)|D(Pc), + Cop2 = Wop2, + Cop = Wop, + Copb = Wopb, + Fop2 = Lop2, + Fop = Lop, + Fopb = Lopb, + Xop = Wop, +}; + +typedef struct Array Array; +typedef struct Bits Bits; +typedef struct Blist Blist; +typedef struct Block Block; +typedef struct Idlist Idlist; +typedef struct Optab Optab; + +struct Array +{ + int n; + int m; + Block **a; +}; + +struct Bits +{ + int n; + ulong *b; +}; + +struct Blist +{ + Block *block; + Blist *next; +}; + +struct Block +{ + int dfn; + int flags; + Inst *first; + Inst *last; + Block *prev; + Block *next; + Blist *pred; + Blist *succ; + Bits kill; + Bits gen; + Bits in; + Bits out; +}; + +struct Idlist +{ + int id; + Idlist *next; +}; + +struct Optab +{ + short flags; + short size; +}; + +Block zblock; +Decl *regdecls; +Idlist *frelist; +Idlist *deflist; +Idlist *uselist; + +static void +addlist(Idlist **hd, int id) +{ + Idlist *il; + + if(frelist == nil) + il = (Idlist*)malloc(sizeof(Idlist)); + else{ + il = frelist; + frelist = frelist->next; + } + il->id = id; + il->next = *hd; + *hd = il; +} + +static void +freelist(Idlist **hd) +{ + Idlist *il; + + for(il = *hd; il != nil && il->next != nil; il = il->next) + ; + if(il != nil){ + il->next = frelist; + frelist = *hd; + *hd = nil; + } +} + +Optab opflags[] = { + /* INOP */ None, 0, + /* IALT */ Unop, S(Mp)|D(W), + /* INBALT */ Unop, S(Mp)|D(W), + /* IGOTO */ Use2, S(W)|D(I), + /* ICALL */ Use2, S(P)|D(Pc), + /* IFRAME */ Unop, S(W)|D(P), + /* ISPAWN */ Use2, S(P)|D(Pc), + /* IRUNT */ None, 0, + /* ILOAD */ Threop, S(C)|M(P)|D(P), + /* IMCALL */ Use3, S(P)|M(W)|D(P), + /* IMSPAWN */ Use3, S(P)|M(W)|D(P), + /* IMFRAME */ Threop, S(P)|M(W)|D(P), + /* IRET */ None, 0, + /* IJMP */ Duse, D(Pc), + /* ICASE */ Use2, S(W)|D(I), + /* IEXIT */ None, 0, + /* INEW */ Unop, S(W)|D(P), + /* INEWA */ Threop, S(W)|M(W)|D(P), + /* INEWCB */ Cunop, M(W)|D(P), + /* INEWCW */ Cunop, M(W)|D(P), + /* INEWCF */ Cunop, M(W)|D(P), + /* INEWCP */ Cunop, M(W)|D(P), + /* INEWCM */ Threop, S(W)|M(W)|D(P), + /* INEWCMP */ Threop, S(W)|M(W)|D(P), + /* ISEND */ Use2, S(Mp)|D(P), + /* IRECV */ Unop, S(P)|D(Mp), + /* ICONSB */ Abinop, S(B)|D(P), + /* ICONSW */ Abinop, S(W)|D(P), + /* ICONSP */ Abinop, S(P)|D(P), + /* ICONSF */ Abinop, S(F)|D(P), + /* ICONSM */ Mabinop, S(Mp)|M(W)|D(P), + /* ICONSMP */ Mabinop, S(Mp)|M(W)|D(P), + /* IHEADB */ Unop, S(P)|D(B), + /* IHEADW */ Unop, S(P)|D(W), + /* IHEADP */ Unop, S(P)|D(P), + /* IHEADF */ Unop, S(P)|D(F), + /* IHEADM */ Threop, S(P)|M(W)|D(Mp), + /* IHEADMP */ Threop, S(P)|M(W)|D(Mp), + /* ITAIL */ Unop, S(P)|D(P), + /* ILEA */ Ddef, S(Mp)|D(P), /* S done specially cos of ALT */ + /* IINDX */ Mbinop, S(P)|M(P)|D(W), + /* IMOVP */ Unop, S(P)|D(P), + /* IMOVM */ Threop, S(Mp)|M(W)|D(Mp), + /* IMOVMP */ Threop, S(Mp)|M(W)|D(Mp), + /* IMOVB */ Unop, Bop2, + /* IMOVW */ Unop, Wop2, + /* IMOVF */ Unop, Fop2, + /* ICVTBW */ Unop, S(B)|D(W), + /* ICVTWB */ Unop, S(W)|D(B), + /* ICVTFW */ Unop, S(F)|D(W), + /* ICVTWF */ Unop, S(W)|D(F), + /* ICVTCA */ Unop, S(C)|D(A), + /* ICVTAC */ Unop, S(A)|D(C), + /* ICVTWC */ Unop, S(W)|D(C), + /* ICVTCW */ Unop, S(C)|D(W), + /* ICVTFC */ Unop, S(F)|D(C), + /* ICVTCF */ Unop, S(C)|D(F), + /* IADDB */ Binop, Bop, + /* IADDW */ Binop, Wop, + /* IADDF */ Binop, Fop, + /* ISUBB */ Binop, Bop, + /* ISUBW */ Binop, Wop, + /* ISUBF */ Binop, Fop, + /* IMULB */ Binop, Bop, + /* IMULW */ Binop, Wop, + /* IMULF */ Binop, Fop, + /* IDIVB */ Binop, Bop, + /* IDIVW */ Binop, Wop, + /* IDIVF */ Binop, Fop, + /* IMODW */ Binop, Wop, + /* IMODB */ Binop, Bop, + /* IANDB */ Binop, Bop, + /* IANDW */ Binop, Wop, + /* IORB */ Binop, Bop, + /* IORW */ Binop, Wop, + /* IXORB */ Binop, Bop, + /* IXORW */ Binop, Wop, + /* ISHLB */ Binop, S(W)|M(B)|D(B), + /* ISHLW */ Binop, Wop, + /* ISHRB */ Binop, S(W)|M(B)|D(B), + /* ISHRW */ Binop, Wop, + /* IINSC */ Mabinop, S(W)|M(W)|D(C), + /* IINDC */ Threop, S(C)|M(W)|D(W), + /* IADDC */ Binop, Cop, + /* ILENC */ Unop, S(C)|D(W), + /* ILENA */ Unop, S(A)|D(W), + /* ILENL */ Unop, S(P)|D(W), + /* IBEQB */ Use3, Bopb, + /* IBNEB */ Use3, Bopb, + /* IBLTB */ Use3, Bopb, + /* IBLEB */ Use3, Bopb, + /* IBGTB */ Use3, Bopb, + /* IBGEB */ Use3, Bopb, + /* IBEQW */ Use3, Wopb, + /* IBNEW */ Use3, Wopb, + /* IBLTW */ Use3, Wopb, + /* IBLEW */ Use3, Wopb, + /* IBGTW */ Use3, Wopb, + /* IBGEW */ Use3, Wopb, + /* IBEQF */ Use3, Fopb, + /* IBNEF */ Use3, Fopb, + /* IBLTF */ Use3, Fopb, + /* IBLEF */ Use3, Fopb, + /* IBGTF */ Use3, Fopb, + /* IBGEF */ Use3, Fopb, + /* IBEQC */ Use3, Copb, + /* IBNEC */ Use3, Copb, + /* IBLTC */ Use3, Copb, + /* IBLEC */ Use3, Copb, + /* IBGTC */ Use3, Copb, + /* IBGEC */ Use3, Copb, + /* ISLICEA */ Mabinop, S(W)|M(W)|D(P), + /* ISLICELA */ Use3, S(P)|M(W)|D(P), + /* ISLICEC */ Mabinop, S(W)|M(W)|D(C), + /* IINDW */ Mbinop, S(P)|M(P)|D(W), + /* IINDF */ Mbinop, S(P)|M(P)|D(W), + /* IINDB */ Mbinop, S(P)|M(P)|D(W), + /* INEGF */ Unop, Fop2, + /* IMOVL */ Unop, Lop2, + /* IADDL */ Binop, Lop, + /* ISUBL */ Binop, Lop, + /* IDIVL */ Binop, Lop, + /* IMODL */ Binop, Lop, + /* IMULL */ Binop, Lop, + /* IANDL */ Binop, Lop, + /* IORL */ Binop, Lop, + /* IXORL */ Binop, Lop, + /* ISHLL */ Binop, S(W)|M(L)|D(L), + /* ISHRL */ Binop, S(W)|M(L)|D(L), + /* IBNEL */ Use3, Lopb, + /* IBLTL */ Use3, Lopb, + /* IBLEL */ Use3, Lopb, + /* IBGTL */ Use3, Lopb, + /* IBGEL */ Use3, Lopb, + /* IBEQL */ Use3, Lopb, + /* ICVTLF */ Unop, S(L)|D(F), + /* ICVTFL */ Unop, S(F)|D(L), + /* ICVTLW */ Unop, S(L)|D(W), + /* ICVTWL */ Unop, S(W)|D(L), + /* ICVTLC */ Unop, S(L)|D(C), + /* ICVTCL */ Unop, S(C)|D(L), + /* IHEADL */ Unop, S(P)|D(L), + /* ICONSL */ Abinop, S(L)|D(P), + /* INEWCL */ Cunop, M(W)|D(P), + /* ICASEC */ Use2, S(C)|D(I), + /* IINDL */ Mbinop, S(P)|M(P)|D(W), + /* IMOVPC */ Unop, S(W)|D(P), + /* ITCMP */ Use2, S(P)|D(P), + /* IMNEWZ */ Threop, S(P)|M(W)|D(P), + /* ICVTRF */ Unop, S(R)|D(F), + /* ICVTFR */ Unop, S(F)|D(R), + /* ICVTWS */ Unop, S(W)|D(Sh), + /* ICVTSW */ Unop, S(Sh)|D(W), + /* ILSRW */ Binop, Wop, + /* ILSRL */ Binop, S(W)|M(L)|D(L), + /* IECLR */ None, 0, + /* INEWZ */ Unop, S(W)|D(P), + /* INEWAZ */ Threop, S(W)|M(W)|D(P), + /* IRAISE */ Use1, S(P), + /* ICASEL */ Use2, S(L)|D(I), + /* IMULX */ Binop|Tuse2, Xop, + /* IDIVX */ Binop|Tuse2, Xop, + /* ICVTXX */ Threop, Xop, + /* IMULX0 */ Binop|Tuse1|Tuse2, Xop, + /* IDIVX0 */ Binop|Tuse1|Tuse2, Xop, + /* ICVTXX0 */ Threop|Tuse1, Xop, + /* IMULX1 */ Binop|Tuse1|Tuse2, Xop, + /* IDIVX1 */ Binop|Tuse1|Tuse2, Xop, + /* ICVTXX1 */ Threop|Tuse1, Xop, + /* ICVTFX */ Threop, S(F)|M(F)|D(X), + /* ICVTXF */ Threop, S(X)|M(F)|D(F), + /* IEXPW */ Binop, S(W)|M(W)|D(W), + /* IEXPL */ Binop, S(W)|M(L)|D(L), + /* IEXPF */ Binop, S(W)|M(F)|D(F), + /* ISELF */ Ddef, D(P), + /* IEXC */ None, 0, + /* IEXC0 */ None, 0, + /* INOOP */ None, 0, +}; + +/* +static int +pop(int i) +{ + i = (i & 0x55555555) + ((i>>1) & 0x55555555); + i = (i & 0x33333333) + ((i>>2) & 0x33333333); + i = (i & 0x0F0F0F0F) + ((i>>4) & 0x0F0F0F0F); + i = (i & 0x00FF00FF) + ((i>>8) & 0x00FF00FF); + i = (i & 0x0000FFFF) + ((i>>16) & 0x0000FFFF); + return i; +} +*/ + +static int +bitc(uint x) +{ + uint n; + + n = (x>>1)&0x77777777; + x -= n; + n = (n>>1)&0x77777777; + x -= n; + n = (n>>1)&0x77777777; + x -= n; + x = (x+(x>>4))&0x0f0f0f0f; + x *= 0x01010101; + return x>>24; +} + +/* +static int +top(uint x) +{ + int i; + + for(i = -1; x; i++) + x >>= 1; + return i; +} +*/ + +static int +topb(uint x) +{ + int i; + + if(x == 0) + return -1; + i = 0; + if(x&0xffff0000){ + i |= 16; + x >>= 16; + } + if(x&0xff00){ + i |= 8; + x >>= 8; + } + if(x&0xf0){ + i |= 4; + x >>= 4; + } + if(x&0xc){ + i |= 2; + x >>= 2; + } + if(x&0x2) + i |= 1; + return i; +} + +/* +static int +lowb(uint x) +{ + int i; + + if(x == 0) + return -1; + for(i = BLEN; x; i--) + x <<= 1; + return i; +} +*/ + +static int +lowb(uint x) +{ + int i; + + if(x == 0) + return -1; + i = 0; + if((x&0xffff) == 0){ + i |= 16; + x >>= 16; + } + if((x&0xff) == 0){ + i |= 8; + x >>= 8; + } + if((x&0xf) == 0){ + i |= 4; + x >>= 4; + } + if((x&0x3) == 0){ + i |= 2; + x >>= 2; + } + return i+1-(x&1); +} + +static void +pbit(int x, int n) +{ + int i, m; + + m = 1; + for(i = 0; i < BLEN; i++){ + if(x&m) + print("%d ", i+n); + m <<= 1; + } +} + +static ulong +bop(int o, ulong s, ulong d) +{ + switch(o){ + case Bclr: return 0; + case Band: return s & d; + case Bandinv: return s & ~d; + case Bstore: return s; + case Bandrev: return ~s & d; + case Bnoop: return d; + case Bxor: return s ^ d; + case Bor: return s | d; + case Bnor: return ~(s | d); + case Bequiv: return ~(s ^ d); + case Binv: return ~d; + case Bimpby: return s | ~d; + case Brev: return ~s; + case Bimp: return ~s | d; + case Bnand: return ~(s & d); + case Bset: return 0xffffffff; + } + return 0; +} + +static Bits +bnew(int n, int bits) +{ + Bits b; + + if(bits) + b.n = (n+BLEN-1)>>BSHIFT; + else + b.n = n; + b.b = allocmem(b.n*sizeof(ulong)); + memset(b.b, 0, b.n*sizeof(ulong)); + return b; +} + +static void +bfree(Bits b) +{ + free(b.b); +} + +static void +bset(Bits b, int n) +{ + b.b[n>>BSHIFT] |= 1<<(n&BMASK); +} + +static void +bclr(Bits b, int n) +{ + b.b[n>>BSHIFT] &= ~(1<<(n&BMASK)); +} + +static int +bmem(Bits b, int n) +{ + return b.b[n>>BSHIFT] & (1<<(n&BMASK)); +} + +static void +bsets(Bits b, int m, int n) +{ + int i, c1, c2; + + c1 = m>>BSHIFT; + c2 = n>>BSHIFT; + m &= BMASK; + n &= BMASK; + if(c1 == c2){ + b.b[c1] |= MASK(m, n); + return; + } + for(i = c1+1; i < c2; i++) + b.b[i] = 0xffffffff; + b.b[c1] |= MASK(m, BLEN-1); + b.b[c2] |= MASK(0, n); +} + +static void +bclrs(Bits b, int m, int n) +{ + int i, c1, c2; + + if(n < 0) + n = (b.n<<BSHIFT)-1; + c1 = m>>BSHIFT; + c2 = n>>BSHIFT; + m &= BMASK; + n &= BMASK; + if(c1 == c2){ + b.b[c1] &= ~MASK(m, n); + return; + } + for(i = c1+1; i < c2; i++) + b.b[i] = 0; + b.b[c1] &= ~MASK(m, BLEN-1); + b.b[c2] &= ~MASK(0, n); +} + +/* b = a op b */ +static Bits +boper(int o, Bits a, Bits b) +{ + int i, n; + + n = a.n; + if(b.n != n) + fatal("boper %d %d %d", o, a.n, b.n); + for(i = 0; i < n; i++) + b.b[i] = bop(o, a.b[i], b.b[i]); + return b; +} + +static int +beq(Bits a, Bits b) +{ + int i, n; + + n = a.n; + for(i = 0; i < n; i++) + if(a.b[i] != b.b[i]) + return 0; + return 1; +} + +static int +bzero(Bits b) +{ + int i, n; + + n = b.n; + for(i = 0; i < n; i++) + if(b.b[i] != 0) + return 0; + return 1; +} + +static int +bitcnt(Bits b) +{ + int i, m, n; + + m = b.n; + n = 0; + for(i = 0; i < m; i++) + n += bitc(b.b[i]); + return n; +} + +static int +topbit(Bits b) +{ + int i, n; + + n = b.n; + for(i = n-1; i >= 0; i--) + if(b.b[i] != 0) + return (i<<BSHIFT)+topb(b.b[i]); + return -1; +} + +static int +lowbit(Bits b) +{ + int i, n; + + n = b.n; + for(i = 0; i < n; i++) + if(b.b[i] != 0) + return (i<<BSHIFT)+lowb(b.b[i]); + return -1; +} + +static void +pbits(Bits b) +{ + int i, n; + + n = b.n; + for(i = 0; i < n; i++) + pbit(b.b[i], i<<BSHIFT); +} + +static char* +decname(Decl *d) +{ + if(d->sym == nil) + return "<??>"; + return d->sym->name; +} + +static void +warning(Inst *i, char *s, Decl *d, Decl *sd) +{ + int n; + char *f; + Decl *ds; + + n = 0; + for(ds = sd; ds != nil; ds = ds->next) + if(ds->link == d) + n += strlen(ds->sym->name)+1; + if(n == 0){ + warn(i->src.start, "%s: %s", d->sym->name, s); + return; + } + n += strlen(d->sym->name); + f = malloc(n+1); + strcpy(f, d->sym->name); + for(ds = sd; ds != nil; ds = ds->next){ + if(ds->link == d){ + strcat(f, "/"); + strcat(f, ds->sym->name); + } + } + warn(i->src.start, "%s: %s", f, s); + free(f); +} + +static int +inspc(Inst *in) +{ + int n; + Inst *i; + + n = 0; + for(i = in; i != nil; i = i->next) + i->pc = n++; + return n; +} + +static Inst* +pc2i(Block *b, int pc) +{ + Inst *i; + + for( ; b != nil; b = b->next){ + if(pc > b->last->pc) + continue; + for(i = b->first; ; i = i->next){ + if(i->pc == pc) + return i; + if(i == b->last) + fatal("pc2i a"); + } + } + fatal("pc2i b"); + return nil; +} + +static void +padr(int am, Addr *a, Inst *br) +{ + long reg; + + if(br != nil){ + print("$%ld", br->pc); + return; + } + reg = a->reg; + if(a->decl != nil && am != Adesc) + reg += a->decl->offset; + switch(am){ + case Anone: + print("-"); + break; + case Aimm: + case Apc: + case Adesc: + print("$%ld", a->offset); + break; + case Aoff: + print("$%ld", a->decl->iface->offset); + break; + case Anoff: + print("-$%ld", a->decl->iface->offset); + break; + case Afp: + print("%ld(fp)", reg); + break; + case Afpind: + print("%ld(%ld(fp))", a->offset, reg); + break; + case Amp: + print("%ld(mp)", reg); + break; + case Ampind: + print("%ld(%ld(mp))", a->offset, reg); + break; + case Aldt: + print("$%ld", reg); + break; + case Aerr: + default: + print("%ld(%ld(?%d?))", a->offset, reg, am); + break; + } +} + +static void +pins(Inst *i) +{ + /* print("%L %ld ", i->src.start, i->pc); */ + print(" %ld ", i->pc); + if(i->op >= 0 && i->op < MAXDIS) + print("%s", instname[i->op]); + else + print("noop"); + print(" "); + padr(i->sm, &i->s, nil); + print(", "); + padr(i->mm, &i->m, nil); + print(", "); + padr(i->dm, &i->d, i->branch); + print("\n"); +} + +static void +blfree(Blist *bl) +{ + Blist *nbl; + + for( ; bl != nil; bl = nbl){ + nbl = bl->next; + free(bl); + } +} + +static void +freebits(Bits *bs, int nv) +{ + int i; + + for(i = 0; i < nv; i++) + bfree(bs[i]); + free(bs); +} + +static void +freeblks(Block *b) +{ + Block *nb; + + for( ; b != nil; b = nb){ + blfree(b->pred); + blfree(b->succ); + bfree(b->kill); + bfree(b->gen); + bfree(b->in); + bfree(b->out); + nb = b->next; + free(b); + } +} + +static int +len(Decl *d) +{ + int n; + + n = 0; + for( ; d != nil; d = d->next) + n++; + return n; +} + +static Bits* +allocbits(int nv, int npc) +{ + int i; + Bits *defs; + + defs = (Bits*)allocmem(nv*sizeof(Bits)); + for(i = 0; i < nv; i++) + defs[i] = bnew(npc, 1); + return defs; +} + +static int +bitcount(Bits *bs, int nv) +{ + int i, n; + + n = 0; + for(i = 0; i < nv; i++) + n += bitcnt(bs[i]); + return n; +} + +static Block* +mkblock(Inst *i) +{ + Block *b; + + b = allocmem(sizeof(Block)); + *b = zblock; + b->first = b->last = i; + return b; +} + +static Blist* +mkblist(Block *b, Blist *nbl) +{ + Blist *bl; + + bl = allocmem(sizeof(Blist)); + bl->block = b; + bl->next = nbl; + return bl; +} + +static void +leader(Inst *i, Array *ab) +{ + int m, n; + Block *b, **a; + + if(i != nil && i->pc == 0){ + if((n = ab->n) == (m = ab->m)){ + a = ab->a; + ab->a = allocmem(2*m*sizeof(Block*)); + memcpy(ab->a, a, m*sizeof(Block*)); + ab->m = 2*m; + free(a); + } + b = mkblock(i); + b->dfn = n; + ab->a[n] = b; + i->pc = ab->n = n+1; + } +} + +static Block* +findb(Inst *i, Array *ab) +{ + if(i == nil) + return nil; + if(i->pc <= 0) + fatal("pc <= 0 in findb"); + return ab->a[i->pc-1]; +} + +static int +memb(Block *b, Blist *bl) +{ + for( ; bl != nil; bl = bl->next) + if(bl->block == b) + return 1; + return 0; +} + +static int +canfallthrough(Inst *i) +{ + if(i == nil) + return 0; + switch(i->op){ + case IGOTO: + case ICASE: + case ICASEL: + case ICASEC: + case IRET: + case IEXIT: + case IRAISE: + case IJMP: + return 0; + case INOOP: + return i->branch != nil; + } + return 1; +} + +static void +predsucc(Block *b1, Block *b2) +{ + if(b1 == nil || b2 == nil) + return; + if(!memb(b1, b2->pred)) + b2->pred = mkblist(b1, b2->pred); + if(!memb(b2, b1->succ)) + b1->succ = mkblist(b2, b1->succ); +} + +static Block* +mkblocks(Inst *in, int *nb) +{ + Inst *i; + Block *b, *firstb, *lastb; + Label *lab; + Array *ab; + int j, n; + + ab = allocmem(sizeof(Array)); + ab->n = 0; + ab->m = 16; + ab->a = allocmem(ab->m*sizeof(Block*)); + leader(in, ab); + for(i = in; i != nil; i = i->next){ + switch(i->op){ + case IGOTO: + case ICASE: + case ICASEL: + case ICASEC: + case INOOP: + if(i->op == INOOP && i->branch != nil){ + leader(i->branch, ab); + leader(i->next, ab); + break; + } + leader(i->d.decl->ty->cse->iwild, ab); + lab = i->d.decl->ty->cse->labs; + n = i->d.decl->ty->cse->nlab; + for(j = 0; j < n; j++) + leader(lab[j].inst, ab); + leader(i->next, ab); + break; + case IRET: + case IEXIT: + case IRAISE: + leader(i->next, ab); + break; + case IJMP: + leader(i->branch, ab); + leader(i->next, ab); + break; + default: + if(i->branch != nil){ + leader(i->branch, ab); + leader(i->next, ab); + } + break; + } + } + firstb = lastb = mkblock(nil); + for(i = in; i != nil; i = i->next){ + if(i->pc != 0){ + b = findb(i, ab); + b->prev = lastb; + lastb->next = b; + if(canfallthrough(lastb->last)) + predsucc(lastb, b); + lastb = b; + } + else + lastb->last = i; + switch(i->op){ + case IGOTO: + case ICASE: + case ICASEL: + case ICASEC: + case INOOP: + if(i->op == INOOP && i->branch != nil){ + b = findb(i->next, ab); + predsucc(lastb, b); + b = findb(i->branch, ab); + predsucc(lastb, b); + break; + } + b = findb(i->d.decl->ty->cse->iwild, ab); + predsucc(lastb, b); + lab = i->d.decl->ty->cse->labs; + n = i->d.decl->ty->cse->nlab; + for(j = 0; j < n; j++){ + b = findb(lab[j].inst, ab); + predsucc(lastb, b); + } + break; + case IRET: + case IEXIT: + case IRAISE: + break; + case IJMP: + b = findb(i->branch, ab); + predsucc(lastb, b); + break; + default: + if(i->branch != nil){ + b = findb(i->next, ab); + predsucc(lastb, b); + b = findb(i->branch, ab); + predsucc(lastb, b); + } + break; + } + } + *nb = ab->n; + free(ab->a); + free(ab); + b = firstb->next; + b->prev = nil; + return b; +} + +static int +back(Block *b1, Block *b2) +{ + return b1->dfn >= b2->dfn; +} + +static void +pblocks(Block *b, int nb) +{ + Inst *i; + Blist *bl; + + print("--------------------%d blocks--------------------\n", nb); + print("------------------------------------------------\n"); + for( ; b != nil; b = b->next){ + print("dfn=%d\n", b->dfn); + print(" pred "); + for(bl = b->pred; bl != nil; bl = bl->next) + print("%d%s ", bl->block->dfn, back(bl->block, b) ? "*" : ""); + print("\n"); + print(" succ "); + for(bl = b->succ; bl != nil; bl = bl->next) + print("%d%s ", bl->block->dfn, back(b, bl->block) ? "*" : ""); + print("\n"); + for(i = b->first; i != nil; i = i->next){ + // print(" %I\n", i); + pins(i); + if(i == b->last) + break; + } + } + print("------------------------------------------------\n"); +} + +static void +ckblocks(Inst *in, Block *b, int nb) +{ + int n; + Block *lastb; + + if(b->first != in) + fatal("A - %d", b->dfn); + n = 0; + lastb = nil; + for( ; b != nil; b = b->next){ + n++; + if(b->prev != lastb) + fatal("a - %d\n", b->dfn); + if(b->prev != nil && b->prev->next != b) + fatal("b - %d\n", b->dfn); + if(b->next != nil && b->next->prev != b) + fatal("c - %d\n", b->dfn); + + if(b->prev != nil && b->prev->last->next != b->first) + fatal("B - %d\n", b->dfn); + if(b->next != nil && b->last->next != b->next->first) + fatal("C - %d\n", b->dfn); + if(b->next == nil && b->last->next != nil) + fatal("D - %d\n", b->dfn); + + if(b->last->branch != nil && b->succ->block->first != b->last->branch) + fatal("0 - %d\n", b->dfn); + + lastb = b; + } + if(n != nb) + fatal("N - %d %d\n", n, nb); +} + +static void +dfs0(Block *b, int *n) +{ + Block *s; + Blist *bl; + + b->flags = 1; + for(bl = b->succ; bl != nil; bl = bl->next){ + s = bl->block; + if(s->flags == 0) + dfs0(s, n); + } + b->dfn = --(*n); +} + +static int +dfs(Block *b, int nb) +{ + int n, u; + Block *b0; + + b0 = b; + n = nb; + dfs0(b0, &n); + u = 0; + for(b = b0; b != nil; b = b->next){ + if(b->flags == 0){ /* unreachable: see foldbranch */ + fatal("found unreachable code"); + u++; + b->prev->next = b->next; + if(b->next){ + b->next->prev = b->prev; + b->prev->last->next = b->next->first; + } + else + b->prev->last->next = nil; + } + b->flags = 0; + } + if(u){ + for(b = b0; b != nil; b = b->next) + b->dfn -= u; + } + return nb-u; +} + +static void +loop0(Block *b) +{ + Block *p; + Blist *bl; + + b->flags = 1; + for(bl = b->pred; bl != nil; bl = bl->next){ + p = bl->block; + if(p->flags == 0) + loop0(p); + } +} + +/* b1->b2 a back edge */ +static void +loop(Block *b, Block *b1, Block *b2) +{ + if(0 && debug['o']) + print("back edge %d->%d\n", b1->dfn, b2->dfn); + b2->flags = 1; + if(b1->flags == 0) + loop0(b1); + if(0 && debug['o']) + print(" loop "); + for( ; b != nil; b = b->next){ + if(b->flags && 0 && debug['o']) + print("%d ", b->dfn); + b->flags = 0; + } + if(0 && debug['o']) + print("\n"); +} + +static void +loops(Block *b) +{ + Block *b0; + Blist *bl; + + b0 = b; + for( ; b != nil; b = b->next){ + for(bl = b->succ; bl != nil; bl = bl->next){ + if(back(b, bl->block)) + loop(b0, b, bl->block); + } + } +} + +static int +imm(int m, Addr *a) +{ + if(m == Aimm) + return a->offset; + fatal("bad immediate value"); + return -1; +} + +static int +desc(int m, Addr *a) +{ + if(m == Adesc) + return a->decl->desc->size; + fatal("bad descriptor value"); + return -1; +} + +static int +fpoff(int m, Addr *a) +{ + int off; + Decl *d; + + if(m == Afp || m == Afpind){ + off = a->reg; + if((d = a->decl) != nil) + off += d->offset; + return off; + } + return -1; +} + +static int +size(Inst *i) +{ + switch(i->op){ + case ISEND: + case IRECV: + case IALT: + case INBALT: + case ILEA: + return i->m.offset; + case IMOVM: + case IHEADM: + case ICONSM: + return imm(i->mm, &i->m); + case IMOVMP: + case IHEADMP: + case ICONSMP: + return desc(i->mm, &i->m); + break; + } + fatal("bad op in size"); + return -1; +} + +static Decl* +mkdec(int o) +{ + Decl *d; + + d = mkdecl(&nosrc, Dlocal, tint); + d->offset = o; + return d; +} + +static void +mkdecls(void) +{ + regdecls = mkdec(REGRET*IBY2WD); + regdecls->next = mkdec(STemp); + regdecls->next->next = mkdec(DTemp); +} + +static Decl* +sharedecls(Decl *d) +{ + Decl *ld; + + ld = d; + for(d = d->next ; d != nil; d = d->next){ + if(d->offset <= ld->offset) + break; + ld = d; + } + return d; +} + +static int +finddec(int o, int s, Decl *vars, int *nv, Inst *i) +{ + int m, n; + Decl *d; + + n = 0; + for(d = vars; d != nil; d = d->next){ + if(o >= d->offset && o < d->offset+d->ty->size){ + m = 1; + while(o+s > d->offset+d->ty->size){ + m++; + d = d->next; + } + *nv = m; + return n; + } + n++; + } + // print("%d %d missing\n", o, s); + pins(i); + fatal("missing decl"); + return -1; +} + +static void +setud(Bits *b, int id, int n, int pc) +{ + if(id < 0) + return; + while(--n >= 0) + bset(b[id++], pc); +} + +static void +ud(Inst *i, Decl *vars, Bits *uses, Bits *defs) +{ + ushort f; + int id, j, nv, pc, sz, s, m, d, ss, sm, sd; + Optab *t; + Idlist *l; + + pc = i->pc; + ss = 0; + t = &opflags[i->op]; + f = t->flags; + sz = t->size; + s = fpoff(i->sm, &i->s); + m = fpoff(i->mm, &i->m); + d = fpoff(i->dm, &i->d); + if(f&Mduse && i->mm == Anone) + f |= Duse; + if(s >= 0){ + if(i->sm == Afp){ + ss = SS(sz); + if(ss == Mp) + ss = size(i); + } + else + ss = IBY2WD; + id = finddec(s, ss, vars, &nv, i); + if(f&Suse) + setud(uses, id, nv, pc); + if(f&Sdef){ + if(i->sm == Afp) + setud(defs, id, nv, pc); + else + setud(uses, id, nv, pc); + } + } + if(m >= 0){ + if(i->mm == Afp){ + sm = SM(sz); + if(sm == Mp) + sm = size(i); + } + else + sm = IBY2WD; + id = finddec(m, sm, vars, &nv, i); + if(f&Muse) + setud(uses, id, nv, pc); + if(f&Mdef){ + if(i->mm == Afp) + setud(defs, id, nv, pc); + else + setud(uses, id, nv, pc); + } + } + if(d >= 0){ + if(i->dm == Afp){ + sd = SD(sz); + if(sd == Mp) + sd = size(i); + } + else + sd = IBY2WD; + id = finddec(d, sd, vars, &nv, i); + if(f&Duse) + setud(uses, id, nv, pc); + if(f&Ddef){ + if(i->dm == Afp) + setud(defs, id, nv, pc); + else + setud(uses, id, nv, pc); + } + } + if(f&Tuse1){ + id = finddec(STemp, IBY2WD, vars, &nv, i); + setud(uses, id, nv, pc); + } + if(f&Tuse2){ + id = finddec(DTemp, IBY2WD, vars, &nv, i); + setud(uses, id, nv, pc); + } + if(i->op == ILEA){ + if(s >= 0){ + id = finddec(s, ss, vars, &nv, i); + if(i->sm == Afp && i->m.reg == 0) + setud(defs, id, nv, pc); + else + setud(uses, id, nv, pc); + } + } + if(0) + switch(i->op){ + case ILEA: + if(s >= 0){ + id = finddec(s, ss, vars, &nv, i); + if(id < 0) + break; + for(j = 0; j < nv; j++){ + if(i->sm == Afp && i->m.reg == 0) + addlist(&deflist, id++); + else + addlist(&uselist, id++); + } + } + break; + case IALT: + case INBALT: + case ICALL: + case IMCALL: + for(l = deflist; l != nil; l = l->next){ + id = l->id; + bset(defs[id], pc); + } + for(l = uselist; l != nil; l = l->next){ + id = l->id; + bset(uses[id], pc); + } + freelist(&deflist); + freelist(&uselist); + break; + } +} + +static void +usedef(Inst *in, Decl *vars, Bits *uses, Bits *defs) +{ + Inst *i; + + for(i = in; i != nil; i = i->next) + ud(i, vars, uses, defs); +} + +static void +pusedef(Bits *ud, int nv, Decl *d, char *s) +{ + int i; + + print("%s\n", s); + for(i = 0; i < nv; i++){ + if(!bzero(ud[i])){ + print("\t%s(%ld): ", decname(d), d->offset); + pbits(ud[i]); + print("\n"); + } + d = d->next; + } +} + +static void +dummydefs(Bits *defs, int nv, int npc) +{ + int i; + + for(i = 0; i < nv; i++) + bset(defs[i], npc++); +} + +static void +dogenkill(Block *b, Bits *defs, int nv) +{ + int i, n, t; + Bits v; + + n = defs[0].n; + v = bnew(n, 0); + for( ; b != nil; b = b->next){ + b->gen = bnew(n, 0); + b->kill = bnew(n, 0); + b->in = bnew(n, 0); + b->out = bnew(n, 0); + for(i = 0; i < nv; i++){ + boper(Bclr, v, v); + bsets(v, b->first->pc, b->last->pc); + boper(Band, defs[i], v); + t = topbit(v); + if(t >= 0) + bset(b->gen, t); + else + continue; + boper(Bclr, v, v); + bsets(v, b->first->pc, b->last->pc); + boper(Binv, v, v); + boper(Band, defs[i], v); + boper(Bor, v, b->kill); + } + } + bfree(v); +} + +static void +udflow(Block *b, int nv, int npc) +{ + int iter; + Block *b0, *p; + Blist *bl; + Bits newin; + + b0 = b; + for(b = b0; b != nil; b = b->next) + boper(Bstore, b->gen, b->out); + newin = bnew(b0->in.n, 0); + iter = 1; + while(iter){ + iter = 0; + for(b = b0; b != nil; b = b->next){ + boper(Bclr, newin, newin); + for(bl = b->pred; bl != nil; bl = bl->next){ + p = bl->block; + boper(Bor, p->out, newin); + } + if(b == b0) + bsets(newin, npc, npc+nv-1); + if(!beq(b->in, newin)) + iter = 1; + boper(Bstore, newin, b->in); + boper(Bstore, b->in, b->out); + boper(Bandrev, b->kill, b->out); + boper(Bor, b->gen, b->out); + } + } + bfree(newin); +} + +static void +pflows(Block *b) +{ + for( ; b != nil; b = b->next){ + print("block %d\n", b->dfn); + print(" gen: "); pbits(b->gen); print("\n"); + print(" kill: "); pbits(b->kill); print("\n"); + print(" in: "); pbits(b->in); print("\n"); + print(" out: "); pbits(b->out); print("\n"); + } +} + +static int +set(Decl *d) +{ + if(d->store == Darg) + return 1; + if(d->sym == nil) /* || d->sym->name[0] == '.') */ + return 1; + if(tattr[d->ty->kind].isptr || d->ty->kind == Texception) + return 1; + return 0; +} + +static int +used(Decl *d) +{ + if(d->sym == nil ) /* || d->sym->name[0] == '.') */ + return 1; + return 0; +} + +static void +udchain(Block *b, Decl *ds, int nv, int npc, Bits *defs, Bits *uses, Decl *sd) +{ + int i, n, p, q; + Bits d, u, dd, ud; + Block *b0; + Inst *in; + + b0 = b; + n = defs[0].n; + u = bnew(n, 0); + d = bnew(n, 0); + dd = bnew(n, 0); + ud = bnew(n, 0); + for(i = 0; i < nv; i++){ + boper(Bstore, defs[i], ud); + bclr(ud, npc+i); + for(b = b0 ; b != nil; b = b->next){ + boper(Bclr, u, u); + bsets(u, b->first->pc, b->last->pc); + boper(Band, uses[i], u); + boper(Bclr, d, d); + bsets(d, b->first->pc, b->last->pc); + boper(Band, defs[i], d); + for(;;){ + p = topbit(u); + if(p < 0) + break; + bclr(u, p); + bclrs(d, p, -1); + q = topbit(d); + if(q >= 0){ + bclr(ud, q); + if(debug['o']) + print("udc b=%d v=%d(%s/%ld) u=%d d=%d\n", b->dfn, i, decname(ds), ds->offset, p, q); + } + else{ + boper(Bstore, defs[i], dd); + boper(Band, b->in, dd); + boper(Bandrev, dd, ud); + if(!bzero(dd)){ + if(debug['o']){ + print("udc b=%d v=%d(%s/%ld) u=%d d=", b->dfn, i, decname(ds), ds->offset, p); + pbits(dd); + print("\n"); + } + if(bmem(dd, npc+i) && !set(ds)) + warning(pc2i(b0, p), "used and not set", ds, sd); + } + else + fatal("no defs in udchain"); + } + } + } + for(;;){ + p = topbit(ud); + if(p < 0) + break; + bclr(ud, p); + if(!used(ds)){ + in = pc2i(b0, p); + if(isnilsrc(&in->src)) /* nilling code */ + in->op = INOOP; /* elim p from bitmaps ? */ + else if(limbovar(ds) && !structure(ds->ty)) + warning(in, "set and not used", ds, sd); + } + } + ds = ds->next; + } + bfree(u); + bfree(d); + bfree(dd); + bfree(ud); +} + +static void +ckflags(void) +{ + int i, j, k, n; + Optab *o; + + n = nelem(opflags); + o = opflags; + for(i = 0; i < n; i++){ + j = (o->flags&(Suse|Sdef)) != 0; + k = SS(o->size) != 0; + if(j != k){ + if(!(j == 0 && k == 1 && i == ILEA)) + fatal("S %ld %s\n", o-opflags, instname[i]); + } + j = (o->flags&(Muse|Mdef)) != 0; + k = SM(o->size) != 0; + if(j != k) + fatal("M %ld %s\n", o-opflags, instname[i]); + j = (o->flags&(Duse|Ddef)) != 0; + k = SD(o->size) != 0; + if(j != k){ + if(!(j == 1 && k == 0 && (i == IGOTO || i == ICASE || i == ICASEC || i == ICASEL))) + fatal("D %ld %s\n", o-opflags, instname[i]); + } + o++; + } +} + +void +optim(Inst *in, Decl *d) +{ + int nb, npc, nv, nd, nu; + Block *b; + Bits *uses, *defs; + Decl *sd; + + ckflags(); + if(debug['o']) + print("************************************************\nfunction %s\n************************************************\n", d->sym->name); + if(in == nil || errors > 0) + return; + d = d->ty->ids; + if(regdecls == nil) + mkdecls(); + regdecls->next->next->next = d; + d = regdecls; + sd = sharedecls(d); + if(debug['o']) + printdecls(d); + b = mkblocks(in, &nb); + ckblocks(in, b, nb); + npc = inspc(in); + nb = dfs(b, nb); + if(debug['o']) + pblocks(b, nb); + loops(b); + nv = len(d); + uses = allocbits(nv, npc+nv); + defs = allocbits(nv, npc+nv); + dummydefs(defs, nv, npc); + usedef(in, d, uses, defs); + if(debug['o']){ + pusedef(uses, nv, d, "uses"); + pusedef(defs, nv, d, "defs"); + } + nu = bitcount(uses, nv); + nd = bitcount(defs, nv); + dogenkill(b, defs, nv); + udflow(b, nv, npc); + if(debug['o']) + pflows(b); + udchain(b, d, nv, npc, defs, uses, sd); + freeblks(b); + freebits(uses, nv); + freebits(defs, nv); + if(debug['o']) + print("nb=%d npc=%d nv=%d nd=%d nu=%d\n", nb, npc, nv, nd, nu); +} + |