src/liblink/sched9.c

// cmd/9l/sched.c from Vita Nuova.
//
//	Copyright © 1994-1999 Lucent Technologies Inc.  All rights reserved.
//	Portions Copyright © 1995-1997 C H Forsyth (forsyth@terzarima.net)
//	Portions Copyright © 1997-1999 Vita Nuova Limited
//	Portions Copyright © 2000-2008 Vita Nuova Holdings Limited (www.vitanuova.com)
//	Portions Copyright © 2004,2006 Bruce Ellis
//	Portions Copyright © 2005-2007 C H Forsyth (forsyth@terzarima.net)
//	Revisions Copyright © 2000-2008 Lucent Technologies Inc. and others
//	Portions Copyright © 2009 The Go Authors.  All rights reserved.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

// +build ignore

#include	"l.h"

enum
{
	E_ICC	= 1<<0,
	E_FCC	= 1<<1,
	E_MEM	= 1<<2,
	E_MEMSP	= 1<<3,	/* uses offset and size */
	E_MEMSB	= 1<<4,	/* uses offset and size */
	E_LR	= 1<<5,
	E_CR = 1<<6,
	E_CTR = 1<<7,
	E_XER = 1<<8,

	E_CR0 = 0xF<<0,
	E_CR1 = 0xF<<4,

	ANYMEM	= E_MEM|E_MEMSP|E_MEMSB,
	ALL	= ~0,
};

typedef	struct	Sch	Sch;
typedef	struct	Dep	Dep;

struct	Dep
{
	ulong	ireg;
	ulong	freg;
	ulong	cc;
	ulong	cr;
};
struct	Sch
{
	Prog	p;
	Dep	set;
	Dep	used;
	long	soffset;
	char	size;
	char	comp;
};

void	regused(Sch*, Prog*);
int	depend(Sch*, Sch*);
int	conflict(Sch*, Sch*);
int	offoverlap(Sch*, Sch*);
void	dumpbits(Sch*, Dep*);

void
sched(Prog *p0, Prog *pe)
{
	Prog *p, *q;
	Sch sch[NSCHED], *s, *t, *u, *se, stmp;

	if(!debug['Q'])
		return;
	/*
	 * build side structure
	 */
	s = sch;
	for(p=p0;; p=p->link) {
		memset(s, 0, sizeof(*s));
		s->p = *p;
		regused(s, p);
		if(debug['X']) {
			Bprint(&bso, "%P\tset", &s->p);
			dumpbits(s, &s->set);
			Bprint(&bso, "; used");
			dumpbits(s, &s->used);
			if(s->comp)
				Bprint(&bso, "; compound");
			if(s->p.mark & LOAD)
				Bprint(&bso, "; load");
			if(s->p.mark & BRANCH)
				Bprint(&bso, "; branch");
			if(s->p.mark & FCMP)
				Bprint(&bso, "; fcmp");
			Bprint(&bso, "\n");
		}
		s++;
		if(p == pe)
			break;
	}
	se = s;

	for(s=se-1; s>=sch; s--) {

		/*
		 * load delay. interlocked.
		 */
		if(s->p.mark & LOAD) {
			if(s >= se-1)
				continue;
			if(!conflict(s, (s+1)))
				continue;
			/*
			 * s is load, s+1 is immediate use of result
			 * t is the trial instruction to insert between s and s+1
			 */
			for(t=s-1; t>=sch; t--) {
				if(t->p.mark & BRANCH)
					goto no2;
				if(t->p.mark & FCMP)
					if((s+1)->p.mark & BRANCH)
						goto no2;
				if(t->p.mark & LOAD)
					if(conflict(t, (s+1)))
						goto no2;
				for(u=t+1; u<=s; u++)
					if(depend(u, t))
						goto no2;
				goto out2;
			no2:;
			}
			if(debug['X'])
				Bprint(&bso, "?l%P\n", &s->p);
			continue;
		out2:
			if(debug['X']) {
				Bprint(&bso, "!l%P\n", &t->p);
				Bprint(&bso, "%P\n", &s->p);
			}
			stmp = *t;
			memmove(t, t+1, (uchar*)s - (uchar*)t);
			*s = stmp;
			s--;
			continue;
		}

		/*
		 * fop2 delay.
		 */
		if(s->p.mark & FCMP) {
			if(s >= se-1)
				continue;
			if(!((s+1)->p.mark & BRANCH))
				continue;
			/* t is the trial instruction to use */
			for(t=s-1; t>=sch; t--) {
				for(u=t+1; u<=s; u++)
					if(depend(u, t))
						goto no3;
				goto out3;
			no3:;
			}
			if(debug['X'])
				Bprint(&bso, "?f%P\n", &s->p);
			continue;
		out3:
			if(debug['X']) {
				Bprint(&bso, "!f%P\n", &t->p);
				Bprint(&bso, "%P\n", &s->p);
			}
			stmp = *t;
			memmove(t, t+1, (uchar*)s - (uchar*)t);
			*s = stmp;
			s--;
			continue;
		}
	}

	/*
	 * put it all back
	 */
	for(s=sch, p=p0; s<se; s++, p=q) {
		q = p->link;
		if(q != s->p.link) {
			*p = s->p;
			p->link = q;
		}
	}
	if(debug['X'])
		Bprint(&bso, "\n");
}

void
regused(Sch *s, Prog *realp)
{
	int c, ar, ad, ld, sz, nr, upd;
	ulong m;
	Prog *p;

	p = &s->p;
	s->comp = compound(p);
	if(s->comp) {
		s->set.ireg |= 1<<REGTMP;
		s->used.ireg |= 1<<REGTMP;
	}
	ar = 0;		/* dest is really reference */
	ad = 0;		/* source/dest is really address */
	ld = 0;		/* opcode is load instruction */
	sz = 32*4;		/* size of load/store for overlap computation */
	nr = 0;	/* source/dest is not really reg */
	upd = 0;	/* move with update; changes reg */

/*
 * flags based on opcode
 */
	switch(p->as) {
	case ATEXT:
		curtext = realp;
		autosize = p->to.offset + 8;
		ad = 1;
		break;
	case ABL:
		s->set.cc |= E_LR;
		ar = 1;
		ad = 1;
		break;
	case ABR:
		ar = 1;
		ad = 1;
		break;
	case ACMP:
	case ACMPU:
	case ACMPW:
	case ACMPWU:
		s->set.cc |= E_ICC;
		if(p->reg == 0)
			s->set.cr |= E_CR0;
		else
			s->set.cr |= (0xF<<((p->reg&7)*4));
		ar = 1;
		break;
	case AFCMPO:
	case AFCMPU:
		s->set.cc |= E_FCC;
		if(p->reg == 0)
			s->set.cr |= E_CR0;
		else
			s->set.cr |= (0xF<<((p->reg&7)*4));
		ar = 1;
		break;
	case ACRAND:
	case ACRANDN:
	case ACREQV:
	case ACRNAND:
	case ACRNOR:
	case ACROR:
	case ACRORN:
	case ACRXOR:
		s->used.cr |= 1<<p->from.reg;
		s->set.cr |= 1<<p->to.reg;
		nr = 1;
		break;
	case ABCL:	/* tricky */
		s->used.cc |= E_FCC|E_ICC;
		s->used.cr = ALL;
		s->set.cc |= E_LR;
		ar = 1;
		break;
	case ABC:		/* tricky */
		s->used.cc |= E_FCC|E_ICC;
		s->used.cr = ALL;
		ar = 1;
		break;
	case ABEQ:
	case ABGE:
	case ABGT:
	case ABLE:
	case ABLT:
	case ABNE:
	case ABVC:
	case ABVS:
		s->used.cc |= E_ICC;
		s->used.cr |= E_CR0;
		ar = 1;
		break;
	case ALSW:
	case AMOVMW:
		/* could do better */
		sz = 32*4;
		ld = 1;
		break;
	case AMOVBU:
	case AMOVBZU:
		upd = 1;
		sz = 1;
		ld = 1;
		break;
	case AMOVB:
	case AMOVBZ:
		sz = 1;
		ld = 1;
		break;
	case AMOVHU:
	case AMOVHZU:
		upd = 1;
		sz = 2;
		ld = 1;
		break;
	case AMOVH:
	case AMOVHBR:
	case AMOVHZ:
		sz = 2;
		ld = 1;
		break;
	case AFMOVSU:
	case AMOVWU:
	case AMOVWZU:
		upd = 1;
		sz = 4;
		ld = 1;
		break;
	case AFMOVS:
	case AMOVW:
	case AMOVWZ:
	case AMOVWBR:
	case ALWAR:
		sz = 4;
		ld = 1;
		break;
	case AFMOVDU:
		upd = 1;
		sz = 8;
		ld = 1;
		break;
	case AFMOVD:
		sz = 8;
		ld = 1;
		break;
	case AFMOVDCC:
		sz = 8;
		ld = 1;
		s->set.cc |= E_FCC;
		s->set.cr |= E_CR1;
		break;
	case AMOVFL:
	case AMOVCRFS:
	case AMTFSB0:
	case AMTFSB0CC:
	case AMTFSB1:
	case AMTFSB1CC:
		s->set.ireg = ALL;
		s->set.freg = ALL;
		s->set.cc = ALL;
		s->set.cr = ALL;
		break;
	case AADDCC:
	case AADDVCC:
	case AADDCCC:
	case AADDCVCC:
	case AADDMECC:
	case AADDMEVCC:
	case AADDECC:
	case AADDEVCC:
	case AADDZECC:
	case AADDZEVCC:
	case AANDCC:
	case AANDNCC:
	case ACNTLZWCC:
	case ADIVWCC:
	case ADIVWVCC:
	case ADIVWUCC:
	case ADIVWUVCC:
	case AEQVCC:
	case AEXTSBCC:
	case AEXTSHCC:
	case AMULHWCC:
	case AMULHWUCC:
	case AMULLWCC:
	case AMULLWVCC:
	case ANANDCC:
	case ANEGCC:
	case ANEGVCC:
	case ANORCC:
	case AORCC:
	case AORNCC:
	case AREMCC:
	case AREMVCC:
	case AREMUCC:
	case AREMUVCC:
	case ARLWMICC:
	case ARLWNMCC:
	case ASLWCC:
	case ASRAWCC:
	case ASRWCC:
	case ASTWCCC:
	case ASUBCC:
	case ASUBVCC:
	case ASUBCCC:
	case ASUBCVCC:
	case ASUBMECC:
	case ASUBMEVCC:
	case ASUBECC:
	case ASUBEVCC:
	case ASUBZECC:
	case ASUBZEVCC:
	case AXORCC:
		s->set.cc |= E_ICC;
		s->set.cr |= E_CR0;
		break;
	case AFABSCC:
	case AFADDCC:
	case AFADDSCC:
	case AFCTIWCC:
	case AFCTIWZCC:
	case AFDIVCC:
	case AFDIVSCC:
	case AFMADDCC:
	case AFMADDSCC:
	case AFMSUBCC:
	case AFMSUBSCC:
	case AFMULCC:
	case AFMULSCC:
	case AFNABSCC:
	case AFNEGCC:
	case AFNMADDCC:
	case AFNMADDSCC:
	case AFNMSUBCC:
	case AFNMSUBSCC:
	case AFRSPCC:
	case AFSUBCC:
	case AFSUBSCC:
		s->set.cc |= E_FCC;
		s->set.cr |= E_CR1;
		break;
	}

/*
 * flags based on 'to' field
 */
	c = p->to.class;
	if(c == 0) {
		c = aclass(&p->to) + 1;
		p->to.class = c;
	}
	c--;
	switch(c) {
	default:
		print("unknown class %d %D\n", c, &p->to);

	case C_NONE:
	case C_ZCON:
	case C_SCON:
	case C_UCON:
	case C_LCON:
	case C_ADDCON:
	case C_ANDCON:
	case C_SBRA:
	case C_LBRA:
		break;
	case C_CREG:
		c = p->to.reg;
		if(c == NREG)
			s->set.cr = ALL;
		else
			s->set.cr |= (0xF << ((p->from.reg&7)*4));
		s->set.cc = ALL;
		break;
	case C_SPR:
	case C_FPSCR:
	case C_MSR:
	case C_XER:
		s->set.ireg = ALL;
		s->set.freg = ALL;
		s->set.cc = ALL;
		s->set.cr = ALL;
		break;
	case C_LR:
		s->set.cc |= E_LR;
		break;
	case C_CTR:
		s->set.cc |= E_CTR;
		break;
	case C_ZOREG:
	case C_SOREG:
	case C_LOREG:
		c = p->to.reg;
		s->used.ireg |= 1<<c;
		if(upd)
			s->set.ireg |= 1<<c;
		if(ad)
			break;
		s->size = sz;
		s->soffset = regoff(&p->to);

		m = ANYMEM;
		if(c == REGSB)
			m = E_MEMSB;
		if(c == REGSP)
			m = E_MEMSP;

		if(ar)
			s->used.cc |= m;
		else
			s->set.cc |= m;
		break;
	case C_SACON:
	case C_LACON:
		s->used.ireg |= 1<<REGSP;
		if(upd)
			s->set.ireg |= 1<<c;
		break;
	case C_SECON:
	case C_LECON:
		s->used.ireg |= 1<<REGSB;
		if(upd)
			s->set.ireg |= 1<<c;
		break;
	case C_REG:
		if(nr)
			break;
		if(ar)
			s->used.ireg |= 1<<p->to.reg;
		else
			s->set.ireg |= 1<<p->to.reg;
		break;
	case C_FREG:
		if(ar)
			s->used.freg |= 1<<p->to.reg;
		else
			s->set.freg |= 1<<p->to.reg;
		break;
	case C_SAUTO:
	case C_LAUTO:
		s->used.ireg |= 1<<REGSP;
		if(upd)
			s->set.ireg |= 1<<c;
		if(ad)
			break;
		s->size = sz;
		s->soffset = regoff(&p->to);

		if(ar)
			s->used.cc |= E_MEMSP;
		else
			s->set.cc |= E_MEMSP;
		break;
	case C_SEXT:
	case C_LEXT:
		s->used.ireg |= 1<<REGSB;
		if(upd)
			s->set.ireg |= 1<<c;
		if(ad)
			break;
		s->size = sz;
		s->soffset = regoff(&p->to);

		if(ar)
			s->used.cc |= E_MEMSB;
		else
			s->set.cc |= E_MEMSB;
		break;
	}

/*
 * flags based on 'from' field
 */
	c = p->from.class;
	if(c == 0) {
		c = aclass(&p->from) + 1;
		p->from.class = c;
	}
	c--;
	switch(c) {
	default:
		print("unknown class %d %D\n", c, &p->from);

	case C_NONE:
	case C_ZCON:
	case C_SCON:
	case C_UCON:
	case C_LCON:
	case C_ADDCON:
	case C_ANDCON:
	case C_SBRA:
	case C_LBRA:
		c = p->from.reg;
		if(c != NREG)
			s->used.ireg |= 1<<c;
		break;
	case C_CREG:
		c = p->from.reg;
		if(c == NREG)
			s->used.cr = ALL;
		else
			s->used.cr |= (0xF << ((p->from.reg&7)*4));
		s->used.cc = ALL;
		break;
	case C_SPR:
	case C_FPSCR:
	case C_MSR:
	case C_XER:
		s->set.ireg = ALL;
		s->set.freg = ALL;
		s->set.cc = ALL;
		s->set.cr = ALL;
		break;
	case C_LR:
		s->used.cc |= E_LR;
		break;
	case C_CTR:
		s->used.cc |= E_CTR;
		break;
	case C_ZOREG:
	case C_SOREG:
	case C_LOREG:
		c = p->from.reg;
		s->used.ireg |= 1<<c;
		if(ld)
			p->mark |= LOAD;
		if(ad)
			break;
		s->size = sz;
		s->soffset = regoff(&p->from);

		m = ANYMEM;
		if(c == REGSB)
			m = E_MEMSB;
		if(c == REGSP)
			m = E_MEMSP;

		s->used.cc |= m;
		break;
	case C_SACON:
	case C_LACON:
		s->used.ireg |= 1<<REGSP;
		break;
	case C_SECON:
	case C_LECON:
		s->used.ireg |= 1<<REGSB;
		break;
	case C_REG:
		if(nr)
			break;
		s->used.ireg |= 1<<p->from.reg;
		break;
	case C_FREG:
		s->used.freg |= 1<<p->from.reg;
		break;
	case C_SAUTO:
	case C_LAUTO:
		s->used.ireg |= 1<<REGSP;
		if(ld)
			p->mark |= LOAD;
		if(ad)
			break;
		s->size = sz;
		s->soffset = regoff(&p->from);

		s->used.cc |= E_MEMSP;
		break;
	case C_SEXT:
	case C_LEXT:
		s->used.ireg |= 1<<REGSB;
		if(ld)
			p->mark |= LOAD;
		if(ad)
			break;
		s->size = sz;
		s->soffset = regoff(&p->from);

		s->used.cc |= E_MEMSB;
		break;
	}
	
	c = p->reg;
	if(c != NREG) {
		if(p->from.type == D_FREG || p->to.type == D_FREG)
			s->used.freg |= 1<<c;
		else
			s->used.ireg |= 1<<c;
	}
}

/*
 * test to see if 2 instrictions can be
 * interchanged without changing semantics
 */
int
depend(Sch *sa, Sch *sb)
{
	ulong x;

	if(sa->set.ireg & (sb->set.ireg|sb->used.ireg))
		return 1;
	if(sb->set.ireg & sa->used.ireg)
		return 1;

	if(sa->set.freg & (sb->set.freg|sb->used.freg))
		return 1;
	if(sb->set.freg & sa->used.freg)
		return 1;

	if(sa->set.cr & (sb->set.cr|sb->used.cr))
		return 1;
	if(sb->set.cr & sa->used.cr)
		return 1;


	x = (sa->set.cc & (sb->set.cc|sb->used.cc)) |
		(sb->set.cc & sa->used.cc);
	if(x) {
		/*
		 * allow SB and SP to pass each other.
		 * allow SB to pass SB iff doffsets are ok
		 * anything else conflicts
		 */
		if(x != E_MEMSP && x != E_MEMSB)
			return 1;
		x = sa->set.cc | sb->set.cc |
			sa->used.cc | sb->used.cc;
		if(x & E_MEM)
			return 1;
		if(offoverlap(sa, sb))
			return 1;
	}

	return 0; 
}

int
offoverlap(Sch *sa, Sch *sb)
{

	if(sa->soffset < sb->soffset) {
		if(sa->soffset+sa->size > sb->soffset)
			return 1;
		return 0;
	}
	if(sb->soffset+sb->size > sa->soffset)
		return 1;
	return 0;
}

/*
 * test 2 adjacent instructions
 * and find out if inserted instructions
 * are desired to prevent stalls.
 * first instruction is a load instruction.
 */
int
conflict(Sch *sa, Sch *sb)
{

	if(sa->set.ireg & sb->used.ireg)
		return 1;
	if(sa->set.freg & sb->used.freg)
		return 1;
	if(sa->set.cr & sb->used.cr)
		return 1;
	return 0;
}

int
compound(Prog *p)
{
	Optab *o;

	o = oplook(p);
	if(o->size != 4)
		return 1;
	if(p->to.type == D_REG && p->to.reg == REGSB)
		return 1;
	return 0;
}

void
dumpbits(Sch *s, Dep *d)
{
	int i;

	for(i=0; i<32; i++)
		if(d->ireg & (1<<i))
			Bprint(&bso, " R%d", i);
	for(i=0; i<32; i++)
		if(d->freg & (1<<i))
			Bprint(&bso, " F%d", i);
	for(i=0; i<32; i++)
		if(d->cr & (1<<i))
			Bprint(&bso, " C%d", i);
	for(i=0; i<32; i++)
		switch(d->cc & (1<<i)) {
		default:
			break;
		case E_ICC:
			Bprint(&bso, " ICC");
			break;
		case E_FCC:
			Bprint(&bso, " FCC");
			break;
		case E_LR:
			Bprint(&bso, " LR");
			break;
		case E_CR:
			Bprint(&bso, " CR");
			break;
		case E_CTR:
			Bprint(&bso, " CTR");
			break;
		case E_XER:
			Bprint(&bso, " XER");
			break;
		case E_MEM:
			Bprint(&bso, " MEM%d", s->size);
			break;
		case E_MEMSB:
			Bprint(&bso, " SB%d", s->size);
			break;
		case E_MEMSP:
			Bprint(&bso, " SP%d", s->size);
			break;
		}
}