#include "gc.h"#include "bound.h" static	BB*	bbfree;static	BBset*	bbsfree;static	int	bballoc;static	int	bbsalloc;static	BB	bbz;static	BBset	bbsz;static	BB*	firstbb;static	BB*	lastbb;static	BB*	wounded;static	BB*	bbaux;static	BBset*	recalc;static	BBset*	bbhash[BBHASH];static	BB**	ordered;static	int	bcount;static	BBset**	heap;static	int	heapn;static	int	bsize;static	char	bbbuff[BBBSIZE];static	int	bchange; #define	bdebug	(debug['v'])#define	dbg	0#define	bcheck	0 static longRn(Reg *r){	if(r == R)		return -1;	return r->rpo;} static BB*bba(void){	BB *b; 	bballoc++;	b = bbfree;	if(b == nil) {		b = alloc(sizeof(*b));	} else		bbfree = b->link; 	*b = bbz;	return b;} static voidbfree(BB *b){	bballoc--;	b->link = bbfree;	bbfree = b;} static BBset*bbsa(void){	BBset *b; 	bballoc++;	b = bbsfree;	if(b == nil) {		b = alloc(sizeof(*b));	} else		bbsfree = b->link; 	*b = bbsz;	return b;} static voidbsfree(BBset *b){	bballoc--;	b->link = bbsfree;	bbsfree = b;} static voiddumpheap(void){	int i; 	for(i = 1; i <= heapn; i++)		print(" %d", heap[i]->damage);} static voidcheckheap(void){	int N, N2, n, c; 	N = heapn;	N2 = N >> 1;	for(n = 1; n <= N2; n++) {		c = n << 1;		if((heap[c]->damage > heap[n]->damage)		|| ((c < N) && (heap[c + 1]->damage > heap[n]->damage))) {			print("bad heap (%d:%d) %d [", n, heap[n]->damage, heapn);			dumpheap();			print(" ]\n");			abort();		}	}} static voiddownheap(int n){	int N, N2, d, c;	BBset *s, *t, *u; 	s = heap[n];	d = s->damage;//print("down %d %d", n, d);	N = heapn;	N2 = N >> 1;	while(n <= N2) {		c = n << 1;		t = heap[c];		if(c < N) {			u = heap[c + 1];			if(t->damage < u->damage) {				t = u;				c++;			}		}//print(" [%d %d]", c, t->damage);		if(t->damage < d)			break;		heap[n] = t;		t->index = n;		n = c;	}	heap[n] = s;	s->index = n;//print("\n");//checkheap();} static voidupheap(int n){	int f, d;	BBset *s, *t; 	s = heap[n];	d = s->damage;//print("up %d %d", n, d);	while(n > 1) {		f = n >> 1;		t = heap[f];//print(" [%d %d]", f, t->damage);		if(t->damage >= d)			break;		heap[n] = t;		t->index = n;		n = f;	}	heap[n] = s;	s->index = n;//print("\n");//checkheap();} static voidheapremove(BBset *s){	int x;	BBset *t; 	x = s->index;	s->index = 0;	if(x == 0)		return;	if(x == heapn) {		heapn--;		return;	}	t = heap[heapn--];	heap[x] = t;	t->index = x;	if(s->damage < t->damage)		upheap(x);	else		downheap(x);} static voidheapadd(BBset *s){	int n; 	n = heapn + 1;	heap[n] = s;	s->index = n;	heapn = n;	upheap(n); } static voidbbsrecalc(BBset *s){	if(s->recalc)		return;	s->recalc = 1;	s->link = recalc;	recalc = s;	heapremove(s);} static voidbbadd(BB *b, Hval h){	int k;	BBset *s; 	k = h[0] & BBMASK;	for(s = bbhash[k]; s != nil; s = s->next) {		if(BBEQ(s->hash, h)) {			b->set = s;			b->link = s->ents;			s->ents = b;			bbsrecalc(s);			return;		}	}	s = bbsa();	s->next = bbhash[k];	bbhash[k] = s;	b->set = s;	b->link = nil;	s->ents = b;	BBCP(s->hash, h);	bbsrecalc(s);} static inthashbb(BB *b, Hval h){	Reg *r;	Prog *p;	char *s;	int c, f, i, n; 	r = b->first;	s = bbbuff;	i = 0;	n = BBBSIZE;	for(;;) {		p = r->prog;		if(p->as != ANOP) {			if(p->to.type == D_BRANCH)				p->to.offset = r->s2->rpo;			c = snprint(s, n, "%P", p);			s += c;			n -= c;			i++;		}		if(r == b->last)			break;		r = r->link;	}	if(n == 0)		return Bbig;	b->len = i;	BBMKHASH(bbbuff, BBBSIZE - n, h);	f = b->flags;	if(i == 1 && r->prog->as == AJMP && b->first->p1 == R)		f = Bjo;	else if(b->first->p1 != R)		f |= Bpre;	if(bdebug)		print("A %x %s %ux %ux\n", f, bbbuff, h[0], h[1]);	return f;} static voidenterbb(BB *b){	Hval h; 	b->flags = hashbb(b, h);	if(b->flags != Bbig)		bbadd(b, h);} static voidpreproc(BB *b, int x){	BB *n;	Reg *r; 	ordered[x] = b;	if(b->last->rpo - b->first->rpo > BBBIG) {		b->flags = Bbig;		return;	}	if(b->first->p2 == nil) {		b->flags = Bdel;		return;	}	switch(b->last->prog->as) {	case ARET:	case AJMP:	case AIRETL:		break; 	default:		b->flags = Bdel;		n = bba();		n->first = b->first;		for(r = b->last->link; r != R; r = r->link) {			switch(r->prog->as) {			case ARET:			case AJMP:			case AIRETL:				n->last = r;				n->flags = Bpin;				enterbb(n);				if(n->flags & Bpin) {					n->aux = bbaux;					bbaux = n;				}				else					bfree(n);				return;			}		}		bfree(n);		return;	}	enterbb(b);} static intp2len(Reg *r){	int c; 	c = 0;	for(r = r->p2; r != nil; r = r->p2link)		c++;	return c;} static voidcalcdamage(BBset *s){	BB *f;	int d, t; 	s->recalc = 0;	f = s->ents;	if(f == nil)		return;	if(f->flags & Bjo) {		if(bdebug)			print("add %ld jo\n", f->first->rpo);		s->damage = COSTJO;		heapadd(s);		return;	}	if(f->link == nil) {		if(bdebug)			print("solo %x %x\n", s->hash[0], s->hash[1]);		return;	} 	d = 0;	t = 0;	while(f != nil) {		if((f->flags & (Bpre|Bpin)) == 0 && f->last->link != R) {			t = 1;			d += (f->last->rpo - f->first->rpo) >> 1;		}		d += p2len(f->first);		f = f->link;	} 	if(t == 0) {		if(bdebug)			print("all pre %ld\n", s->ents->first->rpo);		return;	} 	if(bdebug)		print("add %ld %d\n", s->ents->first->rpo, d);	if(d > COSTHI)		d = COSTHI;	s->damage = d;	heapadd(s);} static Reg*findjump(BB *b){	Reg *r, *l; 	r = b->first;	l = b->last; 	for(;;) {		if(r->prog->as == AJMP)			break;		if(r == l) {			diag(Z, "findjump botch");			break;		}		r = r->link;	}	return r;} static BB*findset(int r){	BB *s, **p;	int n, n2; 	if(r < ordered[0]->first->rpo)		return nil;	n = bcount;	p = ordered;	while(n > 0) {		n2 = n >> 1;		s = p[n2];		if(r < s->first->rpo) {			n = n2;			continue;		}		if(r > s->last->rpo) {			n2++;			p += n2;			n -= n2;			continue;		}		return s;	}	diag(Z, "findset botch");	return nil;} static voidwound(Reg *r){	BB *b, *p, **n;	BBset *s; 	b = findset(r->rpo);	if(b == nil)		return;	s = b->set;	if(s == nil)		return;	for(n = &s->ents; (p = *n) != nil; n = &(*n)->link) {		if(p == b) {			*n = b->link;			b->link = wounded;			wounded = b;			bbsrecalc(s);			return;		}	}} static voidprintbl(Reg *l){	if(l == nil) {		print("Z");		return;	} 	print("%ld", l->rpo);	while((l = l->p2link) != nil)		print(" %ld", l->rpo);} static voidappset(Reg *e, Reg *s){	for(;;) {		if(s->p2link == R) {			s->p2link = e;			return;		}		s = s->p2link;	}} static Reg*delset(Reg *e, Reg *s){

Lines 1–500 of 1117. Load more