bound.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

#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 long
Rn(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 void
bfree(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 void
bsfree(BBset *b)
{
	bballoc--;
	b->link = bbsfree;
	bbsfree = b;
}

static void
dumpheap(void)
{
	int i;

	for(i = 1; i <= heapn; i++)
		print(" %d", heap[i]->damage);
}

static void
checkheap(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 void
downheap(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 void
upheap(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 void
heapremove(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 void
heapadd(BBset *s)
{
	int n;

	n = heapn + 1;
	heap[n] = s;
	s->index = n;
	heapn = n;
	upheap(n);

}

static void
bbsrecalc(BBset *s)
{
	if(s->recalc)
		return;
	s->recalc = 1;
	s->link = recalc;
	recalc = s;
	heapremove(s);
}

static void
bbadd(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 int
hashbb(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 void
enterbb(BB *b)
{
	Hval h;

	b->flags = hashbb(b, h);
	if(b->flags != Bbig)
		bbadd(b, h);
}

static void
preproc(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 int
p2len(Reg *r)
{
	int c;

	c = 0;
	for(r = r->p2; r != nil; r = r->p2link)
		c++;
	return c;
}

static void
calcdamage(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 void
wound(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 void
printbl(Reg *l)
{
	if(l == nil) {
		print("Z");
		return;
	}

	print("%ld", l->rpo);
	while((l = l->p2link) != nil)
		print(" %ld", l->rpo);
}

static void
appset(Reg *e, Reg *s)
{
	for(;;) {
		if(s->p2link == R) {
			s->p2link = e;
			return;
		}
		s = s->p2link;
	}
}

static Reg*
delset(Reg *e, Reg *s)
{
	Reg *c, *l;

	c = s;
	l = nil;
	for(;;) {
		if(e == c) {
			if(l == nil)
				return s->p2link;
			l->p2link = c->p2link;
			return s;
		}
		l = c;
		c = c->p2link;
		if(c == nil)
			return s;
	}
}

static void
redest(Reg *s, Reg *d)
{
	while(s != R) {
		s->s2 = d;
		s = s->p2link;
	}
}

static void
changedest(Reg *s, Reg *d, int x)
{
	Reg *l;

	if(bdebug) {
		print("change %ld [", s->rpo);
		printbl(s->p2);
		print("] -> %ld [", d->rpo);
		printbl(d->p2);
		print("]\n");
	}

	if(s->p2 == nil) {
//		print("deadjmp\n");
		return;
	}

	l = s->p2;
	for(;;) {
		if(bdebug)
			print("s2 %ld = %ld\n", l->rpo, d->rpo);
		l->s2 = d;
		wound(l);
		if(l->p2link == nil)
			break;
		l = l->p2link;
	}

	if(x) {
		l->p2link = delset(s, d->p2);
		d->p2 = s->p2;