ref: 6dce09cec3bf6a689fa9a3f838df67d7d48d9d1a
dir: /limbo/optim.c/
#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 "<nil>"; 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("$%zd", 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(" %zd ", i->pc); if(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 %zd %s\n", o-opflags, instname[i]); } j = (o->flags&(Muse|Mdef)) != 0; k = SM(o->size) != 0; if(j != k) fatal("M %zd %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 %zd %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); }