7 E_MEMSP = 1<<4, /* uses offset and size */
8 E_MEMSB = 1<<5, /* uses offset and size */
9 ANYMEM = E_MEM|E_MEMSP|E_MEMSB,
10 DELAY = BRANCH|LOAD|FCMP,
13 typedef struct Sch Sch;
14 typedef struct Dep Dep;
33 void regused(Sch*, Prog*);
34 int depend(Sch*, Sch*);
35 int conflict(Sch*, Sch*);
36 int offoverlap(Sch*, Sch*);
37 void dumpbits(Sch*, Dep*);
40 sched(Prog *p0, Prog *pe)
43 Sch sch[NSCHED], *s, *t, *u, *se, stmp;
46 * build side structure
49 for(p=p0;; p=p->link) {
50 memset(s, 0, sizeof(*s));
54 Bprint(&bso, "%P\t\tset", &s->p);
56 Bprint(&bso, "; used");
57 dumpbits(s, &s->used);
59 Bprint(&bso, "; compound");
61 Bprint(&bso, "; load");
62 if(s->p.mark & BRANCH)
63 Bprint(&bso, "; branch");
65 Bprint(&bso, "; fcmp");
75 * prepass to move things around
76 * does nothing, but tries to make
77 * the actual scheduler work better
79 for(s=sch; s<=se; s++) {
80 if(!(s->p.mark & LOAD))
82 /* always good to put nonconflict loads together */
83 for(t=s+1; t<=se; t++) {
84 if(!(t->p.mark & LOAD))
86 if(t->p.mark & BRANCH)
95 memmove(s+2, u, (uchar*)t - (uchar*)u);
101 /* put schedule fodder above load */
102 for(t=s+1; t<=se; t++) {
103 if(t->p.mark & BRANCH)
105 if(s > sch && conflict(s-1, t))
107 for(u=t-1; u>=s; u--)
111 memmove(s+1, s, (uchar*)t - (uchar*)s);
113 if(!(s->p.mark & LOAD))
119 for(s=se; s>=sch; s--) {
120 if(!(s->p.mark & DELAY))
123 if(!conflict(s, s+1))
126 * s is load, s+1 is immediate use of result or end of block
127 * t is the trial instruction to insert between s and s+1
130 for(t=s-1; t>=sch; t--) {
132 if(s->p.mark & BRANCH)
134 if(t->p.mark & DELAY)
135 if(s >= se || conflict(t, s+1))
137 for(u=t+1; u<=s; u++)
144 Bprint(&bso, "?l%P\n", &s->p);
147 if(s->p.mark & LOAD) {
151 if(s->p.mark & BRANCH) {
155 if(s->p.mark & FCMP) {
164 Bprint(&bso, "!l%P\n", &t->p);
165 Bprint(&bso, "%P\n", &s->p);
168 memmove(t, t+1, (uchar*)s - (uchar*)t);
176 if(s->p.mark & BRANCH)
183 /* Avoid HI/LO use->set */
185 for(s=sch; s<se-1; s++, t++) {
186 if((s->used.cc & E_PSR) == 0)
188 if(t->set.cc & E_PSR)
195 for(s=sch, p=p0; s<=se; s++, p=q) {
211 regused(Sch *s, Prog *realp)
213 int c, ar, ad, ld, sz;
218 s->comp = compound(p);
221 s->set.ireg |= 1<<REGTMP;
222 s->used.ireg |= 1<<REGTMP;
225 ar = 0; /* dest is really reference */
226 ad = 0; /* source/dest is really address */
227 ld = 0; /* opcode is load instruction */
228 sz = 20; /* size of load/store for overlap computation */
231 * flags based on opcode
236 autosize = p->to.offset + 4;
302 if(p->to.type == D_REG || p->to.type == D_FREG)
305 print("botch %P\n", p);
311 * flags based on 'to' field
315 c = aclass(&p->to) + 1;
321 print("unknown class %d %D\n", c, &p->to);
340 s->used.ireg |= 1<<c;
344 s->offset = regoff(&p->to);
359 s->used.ireg |= 1<<REGSP;
363 s->used.ireg |= 1<<REGSB;
367 s->used.ireg |= 1<<p->to.reg;
369 s->set.ireg |= 1<<p->to.reg;
373 s->used.ireg |= 1<<p->to.reg;
374 s->used.ireg |= 1<<p->to.offset;
376 s->set.ireg |= 1<<p->to.reg;
377 s->set.ireg |= 1<<p->to.offset;
381 /* do better -- determine double prec */
383 s->used.freg |= 1<<p->to.reg;
384 s->used.freg |= 1<<(p->to.reg|1);
386 s->set.freg |= 1<<p->to.reg;
387 s->set.freg |= 1<<(p->to.reg|1);
389 if(ld && p->from.type == D_REG)
394 s->used.ireg |= 1<<REGSP;
398 s->offset = regoff(&p->to);
401 s->used.cc |= E_MEMSP;
403 s->set.cc |= E_MEMSP;
407 s->used.ireg |= 1<<REGSB;
411 s->offset = regoff(&p->to);
414 s->used.cc |= E_MEMSB;
416 s->set.cc |= E_MEMSB;
421 * flags based on 'from' field
425 c = aclass(&p->from) + 1;
431 print("unknown class %d %D\n", c, &p->from);
449 s->used.ireg |= 1<<c;
453 s->offset = regoff(&p->from);
465 s->used.ireg |= 1<<REGSP;
469 s->used.ireg |= 1<<REGSB;
472 s->used.ireg |= 1<<p->from.reg;
475 s->used.ireg |= 1<<p->from.reg;
476 s->used.ireg |= 1<<p->from.offset;
479 /* do better -- determine double prec */
480 s->used.freg |= 1<<p->from.reg;
481 s->used.freg |= 1<<(p->from.reg|1);
482 if(ld && p->to.type == D_REG)
487 s->used.ireg |= 1<<REGSP;
493 s->offset = regoff(&p->from);
495 s->used.cc |= E_MEMSP;
499 s->used.ireg |= 1<<REGSB;
505 s->offset = regoff(&p->from);
507 s->used.cc |= E_MEMSB;
513 if(p->from.type == D_FREG || p->to.type == D_FREG) {
514 s->used.freg |= 1<<c;
515 s->used.freg |= 1<<(c|1);
517 s->used.ireg |= 1<<c;
522 * test to see if 2 instrictions can be
523 * interchanged without changing semantics
526 depend(Sch *sa, Sch *sb)
530 if(sa->set.ireg & (sb->set.ireg|sb->used.ireg))
532 if(sb->set.ireg & sa->used.ireg)
535 if(sa->set.freg & (sb->set.freg|sb->used.freg))
537 if(sb->set.freg & sa->used.freg)
542 * loads from same address cannot pass.
543 * this is for hardware fifo's and the like
545 if(sa->used.cc & sb->used.cc & E_MEM)
546 if(sa->p.reg == sb->p.reg)
547 if(regoff(&sa->p.from) == regoff(&sb->p.from))
550 x = (sa->set.cc & (sb->set.cc|sb->used.cc)) |
551 (sb->set.cc & sa->used.cc);
554 * allow SB and SP to pass each other.
555 * allow SB to pass SB iff doffsets are ok
556 * anything else conflicts
558 if(x != E_MEMSP && x != E_MEMSB)
560 x = sa->set.cc | sb->set.cc |
561 sa->used.cc | sb->used.cc;
564 if(offoverlap(sa, sb))
572 offoverlap(Sch *sa, Sch *sb)
575 if(sa->offset < sb->offset) {
576 if(sa->offset+sa->size > sb->offset)
580 if(sb->offset+sb->size > sa->offset)
586 * test 2 adjacent instructions
587 * and find out if inserted instructions
588 * are desired to prevent stalls.
591 conflict(Sch *sa, Sch *sb)
594 if(sa->set.ireg & sb->used.ireg)
596 if(sa->set.freg & sb->used.freg)
598 if(sa->set.cc & sb->used.cc)
612 if(p->to.type == D_REG && p->to.reg == REGSB)
618 dumpbits(Sch *s, Dep *d)
624 Bprint(&bso, " R%d", i);
627 Bprint(&bso, " F%d", i);
629 switch(d->cc & (1<<i)) {
633 Bprint(&bso, " PSR");
636 Bprint(&bso, " MEM%d", s->size);
639 Bprint(&bso, " SB%d", s->size);
642 Bprint(&bso, " SP%d", s->size);