#include        "l.h"

enum
{
       E_PSR   = 1<<0,
       E_MEM   = 1<<3,
       E_MEMSP = 1<<4,         /* uses offset and size */
       E_MEMSB = 1<<5,         /* uses offset and size */
       ANYMEM  = E_MEM|E_MEMSP|E_MEMSB,
       DELAY   = BRANCH|LOAD|FCMP,
};

typedef struct  Sch     Sch;
typedef struct  Dep     Dep;

struct  Dep
{
       ulong   ireg;
       ulong   freg;
       ulong   cc;
};
struct  Sch
{
       Prog    p;
       Dep     set;
       Dep     used;
       long    offset;
       char    size;
       char    nop;
       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;

       /*
        * 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\t\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");
               }
               if(p == pe)
                       break;
               s++;
       }
       se = s;

       /*
        * prepass to move things around
        * does nothing, but tries to make
        * the actual scheduler work better
        */
       for(s=sch; s<=se; s++) {
               if(!(s->p.mark & LOAD))
                       continue;
               /* always good to put nonconflict loads together */
               for(t=s+1; t<=se; t++) {
                       if(!(t->p.mark & LOAD))
                               continue;
                       if(t->p.mark & BRANCH)
                               break;
                       if(conflict(s, t))
                               break;
                       for(u=t-1; u>s; u--)
                               if(depend(u, t))
                                       goto no11;
                       u = s+1;
                       stmp = *t;
                       memmove(s+2, u, (uchar*)t - (uchar*)u);
                       *u = stmp;
                       break;
               }
       no11:

               /* put schedule fodder above load */
               for(t=s+1; t<=se; t++) {
                       if(t->p.mark & BRANCH)
                               break;
                       if(s > sch && conflict(s-1, t))
                               continue;
                       for(u=t-1; u>=s; u--)
                               if(depend(t, u))
                                       goto no1;
                       stmp = *t;
                       memmove(s+1, s, (uchar*)t - (uchar*)s);
                       *s = stmp;
                       if(!(s->p.mark & LOAD))
                               break;
               no1:;
               }
       }

       for(s=se; s>=sch; s--) {
               if(!(s->p.mark & DELAY))
                       continue;
               if(s < se)
                       if(!conflict(s, s+1))
                               goto out3;
               /*
                * s is load, s+1 is immediate use of result or end of block
                * t is the trial instruction to insert between s and s+1
                */
               if(!debug['Y'])
               for(t=s-1; t>=sch; t--) {
                       if(t->comp)
                               if(s->p.mark & BRANCH)
                                       goto no2;
                       if(t->p.mark & DELAY)
                               if(s >= se || 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);
               s->nop = 1;
               if(debug['v']) {
                       if(s->p.mark & LOAD) {
                               nop.load.count++;
                               nop.load.outof++;
                       }
                       if(s->p.mark & BRANCH) {
                               nop.branch.count++;
                               nop.branch.outof++;
                       }
                       if(s->p.mark & FCMP) {
                               nop.fcmp.count++;
                               nop.fcmp.outof++;
                       }
               }
               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--;

       out3:
               if(debug['v']) {
                       if(s->p.mark & LOAD)
                               nop.load.outof++;
                       if(s->p.mark & BRANCH)
                               nop.branch.outof++;
                       if(s->p.mark & FCMP)
                               nop.fcmp.outof++;
               }
       }

       /* Avoid HI/LO use->set */
       t = sch+1;
       for(s=sch; s<se-1; s++, t++) {
               if((s->used.cc & E_PSR) == 0)
                       continue;
               if(t->set.cc & E_PSR)
                       s->nop = 2;
       }

       /*
        * 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;
               }
               while(s->nop--)
                       addnop(p);
       }
       if(debug['X']) {
               Bprint(&bso, "\n");
               Bflush(&bso);
       }
}

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

       p = &s->p;
       s->comp = compound(p);
       s->nop = 0;
       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 = 20;        /* size of load/store for overlap computation */

/*
* flags based on opcode
*/
       switch(p->as) {
       case ATEXT:
               curtext = realp;
               autosize = p->to.offset + 4;
               ad = 1;
               break;
       case ABL:
               c = p->reg;
               if(c == NREG)
                       c = REGLINK;
               s->set.ireg |= 1<<c;
               ar = 1;
               ad = 1;
               break;
       case ACMP:
       case ACMPF:
       case ACMPD:
               ar = 1;
               s->set.cc |= E_PSR;
               p->mark |= FCMP;
               break;
       case AB:
               ar = 1;
               ad = 1;
               break;
       case AMOVB:
       case AMOVBU:
               sz = 1;
               ld = 1;
               break;
       case AMOVH:
       case AMOVHU:
               sz = 2;
               ld = 1;
               break;
       case AMOVF:
       case AMOVW:
               sz = 4;
               ld = 1;
               break;
       case AMOVD:
               sz = 8;
               ld = 1;
               break;
       case ADIV:
       case ADIVU:
       case AMUL:
       case AMULU:
       case AMOD:
       case AMODU:

       case AADD:
       case AAND:
       case ANOR:
       case AORR:
       case ASLL:
       case ASRA:
       case ASRL:
       case AROR:
       case ASUB:
       case AEOR:

       case AADDD:
       case AADDF:
       case ASUBD:
       case ASUBF:
       case AMULF:
       case AMULD:
       case ADIVF:
               if(p->reg == NREG) {
                       if(p->to.type == D_REG || p->to.type == D_FREG)
                               p->reg = p->to.reg;
                       if(p->reg == NREG)
                               print("botch %P\n", p);
               }
               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_ZCON:
       case C_ICON:
       case C_SCON:
       case C_SICON:
       case C_LCON:
       case C_NONE:
       case C_SBRA:
       case C_LBRA:
               break;

       case C_PSR:
               s->set.cc |= E_PSR;
               break;
       case C_ZOREG:
       case C_SOREG:
       case C_LOREG:
               c = p->to.reg;
               s->used.ireg |= 1<<c;
               if(ad)
                       break;
               s->size = sz;
               s->offset = 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;
               break;
       case C_SECON:
       case C_LECON:
               s->used.ireg |= 1<<REGSB;
               break;
       case C_REG:
               if(ar)
                       s->used.ireg |= 1<<p->to.reg;
               else
                       s->set.ireg |= 1<<p->to.reg;
               break;
       case C_REGREG:
               if(ar){
                       s->used.ireg |= 1<<p->to.reg;
                       s->used.ireg |= 1<<p->to.offset;
               }else{
                       s->set.ireg |= 1<<p->to.reg;
                       s->set.ireg |= 1<<p->to.offset;
               }
               break;
       case C_FREG:
               /* do better -- determine double prec */
               if(ar) {
                       s->used.freg |= 1<<p->to.reg;
                       s->used.freg |= 1<<(p->to.reg|1);
               } else {
                       s->set.freg |= 1<<p->to.reg;
                       s->set.freg |= 1<<(p->to.reg|1);
               }
               if(ld && p->from.type == D_REG)
                       p->mark |= LOAD;
               break;
       case C_SAUTO:
       case C_LAUTO:
               s->used.ireg |= 1<<REGSP;
               if(ad)
                       break;
               s->size = sz;
               s->offset = 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(ad)
                       break;
               s->size = sz;
               s->offset = 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_ZCON:
       case C_ICON:
       case C_SCON:
       case C_SICON:
       case C_LCON:
       case C_NONE:
       case C_SBRA:
       case C_LBRA:
               break;
       case C_PSR:
               s->used.cc |= E_PSR;
               break;
       case C_ZOREG:
       case C_SOREG:
       case C_LOREG:
               c = p->from.reg;
               s->used.ireg |= 1<<c;
               if(ld)
                       p->mark |= LOAD;
               s->size = sz;
               s->offset = 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:
               s->used.ireg |= 1<<p->from.reg;
               break;
       case C_REGREG:
               s->used.ireg |= 1<<p->from.reg;
               s->used.ireg |= 1<<p->from.offset;
               break;
       case C_FREG:
               /* do better -- determine double prec */
               s->used.freg |= 1<<p->from.reg;
               s->used.freg |= 1<<(p->from.reg|1);
               if(ld && p->to.type == D_REG)
                       p->mark |= LOAD;
               break;
       case C_SAUTO:
       case C_LAUTO:
               s->used.ireg |= 1<<REGSP;
               if(ld)
                       p->mark |= LOAD;
               if(ad)
                       break;
               s->size = sz;
               s->offset = 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->offset = 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;
                       s->used.freg |= 1<<(c|1);
               } 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;

       /*
        * special case.
        * loads from same address cannot pass.
        * this is for hardware fifo's and the like
        */
       if(sa->used.cc & sb->used.cc & E_MEM)
               if(sa->p.reg == sb->p.reg)
               if(regoff(&sa->p.from) == regoff(&sb->p.from))
                       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->offset < sb->offset) {
               if(sa->offset+sa->size > sb->offset)
                       return 1;
               return 0;
       }
       if(sb->offset+sb->size > sa->offset)
               return 1;
       return 0;
}

/*
* test 2 adjacent instructions
* and find out if inserted instructions
* are desired to prevent stalls.
*/
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.cc & sb->used.cc)
               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++)
               switch(d->cc & (1<<i)) {
               default:
                       break;
               case E_PSR:
                       Bprint(&bso, " PSR");
                       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;
               }
}

You are viewing proxied material from sdf.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.