# shithub: purgatorio

View raw version
```#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	SIGN(n)		(1<<(n-1))
#define	MSK(n)		(SIGN(n)|(SIGN(n)-1))

#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
{
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,
/* 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),
/* 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),
/* 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),
/* 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,
/* 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),
/* 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)
{
}

static void
bclr(Bits b, int n)
{
}

static int
bmem(Bits b, int n)
{
}

static void
bsets(Bits b, int m, int n)
{
int i, c1, c2;

c1 = m>>BSHIFT;
c2 = n>>BSHIFT;
if(c1 == c2){
return;
}
for(i = c1+1; i < c2; i++)
b.b[i] = 0xffffffff;
}

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;
if(c1 == c2){
return;
}
for(i = c1+1; i < c2; i++)
b.b[i] = 0;
}

/* 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)
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){
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
{
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:
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 < MAXDIS)
print("%s", instname[i->op]);
else
print("noop");
print("	");
print(", ");
print(", ");
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
{
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*));
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){
break;
}
lab = i->d.decl->ty->cse->labs;
n = i->d.decl->ty->cse->nlab;
for(j = 0; j < n; j++)
break;
case IRET:
case IEXIT:
case IRAISE:
break;
case IJMP:
break;
default:
if(i->branch != nil){
}
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
{
if(m == Aimm)
return a->offset;
return -1;
}

static int
{
return a->decl->desc->size;
return -1;
}

static int
{
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 ICONSM:
return imm(i->mm, &i->m);
case IMOVMP:
case ICONSMP:
return desc(i->mm, &i->m);
break;
}
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)
else
}
}
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);
}

```