9 E_MEMSP = 1<<4, /* uses offset and size */
10 E_MEMSB = 1<<5, /* uses offset and size */
11 ANYMEM = E_MEM|E_MEMSP|E_MEMSB,
12 DELAY = BRANCH|LOAD|FCMP,
15 typedef struct Sch Sch;
16 typedef struct Dep Dep;
35 void regsused(Sch*, Prog*);
36 int depend(Sch*, Sch*);
37 int conflict(Sch*, Sch*);
38 int offoverlap(Sch*, Sch*);
39 void dumpbits(Sch*, Dep*);
42 sched(Prog *p0, Prog *pe)
45 Sch sch[NSCHED], *s, *t, *u, *se, stmp;
48 * build side structure
51 for(p=p0;; p=p->link) {
52 memset(s, 0, sizeof(*s));
56 Bprint(&bso, "%P\t\tset", &s->p);
58 Bprint(&bso, "; used");
59 dumpbits(s, &s->used);
61 Bprint(&bso, "; compound");
63 Bprint(&bso, "; load");
64 if(s->p.mark & BRANCH)
65 Bprint(&bso, "; branch");
67 Bprint(&bso, "; fcmp");
77 * prepass to move things around
78 * does nothing, but tries to make
79 * the actual scheduler work better
81 for(s=sch; s<=se; s++) {
82 if(!(s->p.mark & LOAD))
84 /* always good to put nonconflict loads together */
85 for(t=s+1; t<=se; t++) {
86 if(!(t->p.mark & LOAD))
88 if(t->p.mark & BRANCH || t->set.ireg & (1<<REGSP))
97 memmove(s+2, u, (uchar*)t - (uchar*)u);
103 /* put schedule fodder above load */
104 for(t=s+1; t<=se; t++) {
105 if(t->p.mark & BRANCH || t->set.ireg & (1<<REGSP))
107 if(s > sch && conflict(s-1, t))
109 for(u=t-1; u>=s; u--)
113 memmove(s+1, s, (uchar*)t - (uchar*)s);
115 if(!(s->p.mark & LOAD))
121 for(s=se; s>=sch; s--) {
122 if(!(s->p.mark & DELAY))
125 if(!conflict(s, s+1))
128 * s is load, s+1 is immediate use of result or end of block
129 * t is the trial instruction to insert between s and s+1
132 for(t=s-1; t>=sch; t--) {
134 if(s->p.mark & BRANCH)
136 if(t->p.mark & DELAY)
137 if(s >= se || conflict(t, s+1))
139 for(u=t+1; u<=s; u++)
146 Bprint(&bso, "?l%P\n", &s->p);
149 if(s->p.mark & LOAD) {
153 if(s->p.mark & BRANCH) {
157 if(s->p.mark & FCMP) {
166 Bprint(&bso, "!l%P\n", &t->p);
167 Bprint(&bso, "%P\n", &s->p);
170 memmove(t, t+1, (uchar*)s - (uchar*)t);
178 if(s->p.mark & BRANCH)
185 /* Avoid HI/LO use->set */
187 for(s=sch; s<se-1; s++, t++) {
188 if((s->used.cc & E_HILO) == 0)
190 if(t->set.cc & E_HILO)
197 for(s=sch, p=p0; s<=se; s++, p=q) {
213 regsused(Sch *s, Prog *realp)
215 int c, ar, ad, ld, sz;
220 s->comp = compound(p);
223 s->set.ireg |= 1<<REGTMP;
224 s->used.ireg |= 1<<REGTMP;
227 ar = 0; /* dest is really reference */
228 ad = 0; /* source/dest is really address */
229 ld = 0; /* opcode is load instruction */
230 sz = 20; /* size of load/store for overlap computation */
233 * flags based on opcode
238 autosize = p->to.offset + 4;
251 s->set.ireg |= 1<<REGLINK;
338 if(p->to.type == D_REG || p->to.type == D_FREG)
341 print("botch %P\n", p);
347 * flags based on 'to' field
351 c = aclass(&p->to) + 1;
357 print("unknown class %d %D\n", c, &p->to);
386 s->used.ireg |= 1<<c;
390 s->soffset = regoff(&p->to);
405 s->used.ireg |= 1<<REGSP;
409 s->used.ireg |= 1<<REGSB;
413 s->used.ireg |= 1<<p->to.reg;
415 s->set.ireg |= 1<<p->to.reg;
418 /* do better -- determine double prec */
420 s->used.freg |= 1<<p->to.reg;
421 s->used.freg |= 1<<(p->to.reg|1);
423 s->set.freg |= 1<<p->to.reg;
424 s->set.freg |= 1<<(p->to.reg|1);
426 if(ld && p->from.type == D_REG)
431 s->used.ireg |= 1<<REGSP;
435 s->soffset = regoff(&p->to);
438 s->used.cc |= E_MEMSP;
440 s->set.cc |= E_MEMSP;
444 s->used.ireg |= 1<<REGSB;
448 s->soffset = regoff(&p->to);
451 s->used.cc |= E_MEMSB;
453 s->set.cc |= E_MEMSB;
458 * flags based on 'from' field
462 c = aclass(&p->from) + 1;
468 print("unknown class %d %D\n", c, &p->from);
484 s->used.cc |= E_HILO;
496 s->used.ireg |= 1<<c;
500 s->soffset = regoff(&p->from);
512 s->used.ireg |= 1<<REGSP;
516 s->used.ireg |= 1<<REGSB;
519 s->used.ireg |= 1<<p->from.reg;
522 /* do better -- determine double prec */
523 s->used.freg |= 1<<p->from.reg;
524 s->used.freg |= 1<<(p->from.reg|1);
525 if(ld && p->to.type == D_REG)
530 s->used.ireg |= 1<<REGSP;
536 s->soffset = regoff(&p->from);
538 s->used.cc |= E_MEMSP;
542 s->used.ireg |= 1<<REGSB;
548 s->soffset = regoff(&p->from);
550 s->used.cc |= E_MEMSB;
556 if(p->from.type == D_FREG || p->to.type == D_FREG) {
557 s->used.freg |= 1<<c;
558 s->used.freg |= 1<<(c|1);
560 s->used.ireg |= 1<<c;
562 s->set.ireg &= ~(1<<REGZERO); /* R0 cant be set */
566 * test to see if 2 instrictions can be
567 * interchanged without changing semantics
570 depend(Sch *sa, Sch *sb)
574 if(sa->set.ireg & (sb->set.ireg|sb->used.ireg))
576 if(sb->set.ireg & sa->used.ireg)
579 if(sa->set.freg & (sb->set.freg|sb->used.freg))
581 if(sb->set.freg & sa->used.freg)
586 * loads from same address cannot pass.
587 * this is for hardware fifo's and the like
589 if(sa->used.cc & sb->used.cc & E_MEM)
590 if(sa->p.reg == sb->p.reg)
591 if(regoff(&sa->p.from) == regoff(&sb->p.from))
594 x = (sa->set.cc & (sb->set.cc|sb->used.cc)) |
595 (sb->set.cc & sa->used.cc);
598 * allow SB and SP to pass each other.
599 * allow SB to pass SB iff doffsets are ok
600 * anything else conflicts
602 if(x != E_MEMSP && x != E_MEMSB)
604 x = sa->set.cc | sb->set.cc |
605 sa->used.cc | sb->used.cc;
608 if(offoverlap(sa, sb))
616 offoverlap(Sch *sa, Sch *sb)
619 if(sa->soffset < sb->soffset) {
620 if(sa->soffset+sa->size > sb->soffset)
624 if(sb->soffset+sb->size > sa->soffset)
630 * test 2 adjacent instructions
631 * and find out if inserted instructions
632 * are desired to prevent stalls.
635 conflict(Sch *sa, Sch *sb)
637 if(sa->set.ireg & sb->used.ireg)
639 if(sa->set.freg & sb->used.freg)
641 if(sa->set.cc & sb->used.cc)
655 if(p->to.type == D_REG && p->to.reg == REGSB)
661 dumpbits(Sch *s, Dep *d)
667 Bprint(&bso, " R%d", i);
670 Bprint(&bso, " F%d", i);
672 switch(d->cc & (1<<i)) {
676 Bprint(&bso, " HILO");
679 Bprint(&bso, " FCR");
682 Bprint(&bso, " MCR");
685 Bprint(&bso, " MEM%d", s->size);
688 Bprint(&bso, " SB%d", s->size);
691 Bprint(&bso, " SP%d", s->size);