123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801 |
- #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 + 4;
- ad = 1;
- break;
- case ABL:
- s->set.cc |= E_LR;
- ar = 1;
- ad = 1;
- break;
- case ABR:
- ar = 1;
- ad = 1;
- break;
- case ACMP:
- 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:
- upd = 1;
- sz = 4;
- ld = 1;
- break;
- case AFMOVS:
- case AMOVW:
- 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_SREG:
- 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_SREG:
- 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;
- }
- }
|