sys/src/cmd/5l/sched.c

   1 #include        "l.h"
   2
   3 enum
   4 {
   5         E_PSR   = 1<<0,
   6         E_MEM   = 1<<3,
   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,
  11 };
  12
  13 typedef struct  Sch     Sch;
  14 typedef struct  Dep     Dep;
  15
  16 struct  Dep
  17 {
  18         ulong   ireg;
  19         ulong   freg;
  20         ulong   cc;
  21 };
  22 struct  Sch
  23 {
  24         Prog    p;
  25         Dep     set;
  26         Dep     used;
  27         long    offset;
  28         char    size;
  29         char    nop;
  30         char    comp;
  31 };
  32
  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*);
  38
  39 void
  40 sched(Prog *p0, Prog *pe)
  41 {
  42         Prog *p, *q;
  43         Sch sch[NSCHED], *s, *t, *u, *se, stmp;
  44
  45         /*
  46          * build side structure
  47          */
  48         s = sch;
  49         for(p=p0;; p=p->link) {
  50                 memset(s, 0, sizeof(*s));
  51                 s->p = *p;
  52                 regused(s, p);
  53                 if(debug['X']) {
  54                         Bprint(&bso, "%P\t\tset", &s->p);
  55                         dumpbits(s, &s->set);
  56                         Bprint(&bso, "; used");
  57                         dumpbits(s, &s->used);
  58                         if(s->comp)
  59                                 Bprint(&bso, "; compound");
  60                         if(s->p.mark & LOAD)
  61                                 Bprint(&bso, "; load");
  62                         if(s->p.mark & BRANCH)
  63                                 Bprint(&bso, "; branch");
  64                         if(s->p.mark & FCMP)
  65                                 Bprint(&bso, "; fcmp");
  66                         Bprint(&bso, "\n");
  67                 }
  68                 if(p == pe)
  69                         break;
  70                 s++;
  71         }
  72         se = s;
  73
  74         /*
  75          * prepass to move things around
  76          * does nothing, but tries to make
  77          * the actual scheduler work better
  78          */
  79         for(s=sch; s<=se; s++) {
  80                 if(!(s->p.mark & LOAD))
  81                         continue;
  82                 /* always good to put nonconflict loads together */
  83                 for(t=s+1; t<=se; t++) {
  84                         if(!(t->p.mark & LOAD))
  85                                 continue;
  86                         if(t->p.mark & BRANCH)
  87                                 break;
  88                         if(conflict(s, t))
  89                                 break;
  90                         for(u=t-1; u>s; u--)
  91                                 if(depend(u, t))
  92                                         goto no11;
  93                         u = s+1;
  94                         stmp = *t;
  95                         memmove(s+2, u, (uchar*)t - (uchar*)u);
  96                         *u = stmp;
  97                         break;
  98                 }
  99         no11:
 100
 101                 /* put schedule fodder above load */
 102                 for(t=s+1; t<=se; t++) {
 103                         if(t->p.mark & BRANCH)
 104                                 break;
 105                         if(s > sch && conflict(s-1, t))
 106                                 continue;
 107                         for(u=t-1; u>=s; u--)
 108                                 if(depend(t, u))
 109                                         goto no1;
 110                         stmp = *t;
 111                         memmove(s+1, s, (uchar*)t - (uchar*)s);
 112                         *s = stmp;
 113                         if(!(s->p.mark & LOAD))
 114                                 break;
 115                 no1:;
 116                 }
 117         }
 118
 119         for(s=se; s>=sch; s--) {
 120                 if(!(s->p.mark & DELAY))
 121                         continue;
 122                 if(s < se)
 123                         if(!conflict(s, s+1))
 124                                 goto out3;
 125                 /*
 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
 128                  */
 129                 if(!debug['Y'])
 130                 for(t=s-1; t>=sch; t--) {
 131                         if(t->comp)
 132                                 if(s->p.mark & BRANCH)
 133                                         goto no2;
 134                         if(t->p.mark & DELAY)
 135                                 if(s >= se || conflict(t, s+1))
 136                                         goto no2;
 137                         for(u=t+1; u<=s; u++)
 138                                 if(depend(u, t))
 139                                         goto no2;
 140                         goto out2;
 141                 no2:;
 142                 }
 143                 if(debug['X'])
 144                         Bprint(&bso, "?l%P\n", &s->p);
 145                 s->nop = 1;
 146                 if(debug['v']) {
 147                         if(s->p.mark & LOAD) {
 148                                 nop.load.count++;
 149                                 nop.load.outof++;
 150                         }
 151                         if(s->p.mark & BRANCH) {
 152                                 nop.branch.count++;
 153                                 nop.branch.outof++;
 154                         }
 155                         if(s->p.mark & FCMP) {
 156                                 nop.fcmp.count++;
 157                                 nop.fcmp.outof++;
 158                         }
 159                 }
 160                 continue;
 161
 162         out2:
 163                 if(debug['X']) {
 164                         Bprint(&bso, "!l%P\n", &t->p);
 165                         Bprint(&bso, "%P\n", &s->p);
 166                 }
 167                 stmp = *t;
 168                 memmove(t, t+1, (uchar*)s - (uchar*)t);
 169                 *s = stmp;
 170                 s--;
 171
 172         out3:
 173                 if(debug['v']) {
 174                         if(s->p.mark & LOAD)
 175                                 nop.load.outof++;
 176                         if(s->p.mark & BRANCH)
 177                                 nop.branch.outof++;
 178                         if(s->p.mark & FCMP)
 179                                 nop.fcmp.outof++;
 180                 }
 181         }
 182
 183         /* Avoid HI/LO use->set */
 184         t = sch+1;
 185         for(s=sch; s<se-1; s++, t++) {
 186                 if((s->used.cc & E_PSR) == 0)
 187                         continue;
 188                 if(t->set.cc & E_PSR)
 189                         s->nop = 2;
 190         }
 191
 192         /*
 193          * put it all back
 194          */
 195         for(s=sch, p=p0; s<=se; s++, p=q) {
 196                 q = p->link;
 197                 if(q != s->p.link) {
 198                         *p = s->p;
 199                         p->link = q;
 200                 }
 201                 while(s->nop--)
 202                         addnop(p);
 203         }
 204         if(debug['X']) {
 205                 Bprint(&bso, "\n");
 206                 Bflush(&bso);
 207         }
 208 }
 209
 210 void
 211 regused(Sch *s, Prog *realp)
 212 {
 213         int c, ar, ad, ld, sz;
 214         ulong m;
 215         Prog *p;
 216
 217         p = &s->p;
 218         s->comp = compound(p);
 219         s->nop = 0;
 220         if(s->comp) {
 221                 s->set.ireg |= 1<<REGTMP;
 222                 s->used.ireg |= 1<<REGTMP;
 223         }
 224
 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 */
 229
 230 /*
 231  * flags based on opcode
 232  */
 233         switch(p->as) {
 234         case ATEXT:
 235                 curtext = realp;
 236                 autosize = p->to.offset + 4;
 237                 ad = 1;
 238                 break;
 239         case ABL:
 240                 c = p->reg;
 241                 if(c == NREG)
 242                         c = REGLINK;
 243                 s->set.ireg |= 1<<c;
 244                 ar = 1;
 245                 ad = 1;
 246                 break;
 247         case ACMP:
 248         case ACMPF:
 249         case ACMPD:
 250                 ar = 1;
 251                 s->set.cc |= E_PSR;
 252                 p->mark |= FCMP;
 253                 break;
 254         case AB:
 255                 ar = 1;
 256                 ad = 1;
 257                 break;
 258         case AMOVB:
 259         case AMOVBU:
 260                 sz = 1;
 261                 ld = 1;
 262                 break;
 263         case AMOVH:
 264         case AMOVHU:
 265                 sz = 2;
 266                 ld = 1;
 267                 break;
 268         case AMOVF:
 269         case AMOVW:
 270                 sz = 4;
 271                 ld = 1;
 272                 break;
 273         case AMOVD:
 274                 sz = 8;
 275                 ld = 1;
 276                 break;
 277         case ADIV:
 278         case ADIVU:
 279         case AMUL:
 280         case AMULU:
 281         case AMOD:
 282         case AMODU:
 283
 284         case AADD:
 285         case AAND:
 286         case ANOR:
 287         case AORR:
 288         case ASLL:
 289         case ASRA:
 290         case ASRL:
 291         case AROR:
 292         case ASUB:
 293         case AEOR:
 294
 295         case AADDD:
 296         case AADDF:
 297         case ASUBD:
 298         case ASUBF:
 299         case AMULF:
 300         case AMULD:
 301         case ADIVF:
 302                 if(p->reg == NREG) {
 303                         if(p->to.type == D_REG || p->to.type == D_FREG)
 304                                 p->reg = p->to.reg;
 305                         if(p->reg == NREG)
 306                                 print("botch %P\n", p);
 307                 }
 308                 break;
 309         }
 310
 311 /*
 312  * flags based on 'to' field
 313  */
 314         c = p->to.class;
 315         if(c == 0) {
 316                 c = aclass(&p->to) + 1;
 317                 p->to.class = c;
 318         }
 319         c--;
 320         switch(c) {
 321         default:
 322                 print("unknown class %d %D\n", c, &p->to);
 323
 324         case C_ZCON:
 325         case C_ICON:
 326         case C_SCON:
 327         case C_SICON:
 328         case C_LCON:
 329         case C_NONE:
 330         case C_SBRA:
 331         case C_LBRA:
 332                 break;
 333
 334         case C_PSR:
 335                 s->set.cc |= E_PSR;
 336                 break;
 337         case C_ZOREG:
 338         case C_SOREG:
 339         case C_LOREG:
 340                 c = p->to.reg;
 341                 s->used.ireg |= 1<<c;
 342                 if(ad)
 343                         break;
 344                 s->size = sz;
 345                 s->offset = regoff(&p->to);
 346
 347                 m = ANYMEM;
 348                 if(c == REGSB)
 349                         m = E_MEMSB;
 350                 if(c == REGSP)
 351                         m = E_MEMSP;
 352
 353                 if(ar)
 354                         s->used.cc |= m;
 355                 else
 356                         s->set.cc |= m;
 357                 break;
 358         case C_SACON:
 359         case C_LACON:
 360                 s->used.ireg |= 1<<REGSP;
 361                 break;
 362         case C_SECON:
 363         case C_LECON:
 364                 s->used.ireg |= 1<<REGSB;
 365                 break;
 366         case C_REG:
 367                 if(ar)
 368                         s->used.ireg |= 1<<p->to.reg;
 369                 else
 370                         s->set.ireg |= 1<<p->to.reg;
 371                 break;
 372         case C_REGREG:
 373                 if(ar){
 374                         s->used.ireg |= 1<<p->to.reg;
 375                         s->used.ireg |= 1<<p->to.offset;
 376                 }else{
 377                         s->set.ireg |= 1<<p->to.reg;
 378                         s->set.ireg |= 1<<p->to.offset;
 379                 }
 380                 break;
 381         case C_FREG:
 382                 /* do better -- determine double prec */
 383                 if(ar) {
 384                         s->used.freg |= 1<<p->to.reg;
 385                         s->used.freg |= 1<<(p->to.reg|1);
 386                 } else {
 387                         s->set.freg |= 1<<p->to.reg;
 388                         s->set.freg |= 1<<(p->to.reg|1);
 389                 }
 390                 if(ld && p->from.type == D_REG)
 391                         p->mark |= LOAD;
 392                 break;
 393         case C_SAUTO:
 394         case C_LAUTO:
 395                 s->used.ireg |= 1<<REGSP;
 396                 if(ad)
 397                         break;
 398                 s->size = sz;
 399                 s->offset = regoff(&p->to);
 400
 401                 if(ar)
 402                         s->used.cc |= E_MEMSP;
 403                 else
 404                         s->set.cc |= E_MEMSP;
 405                 break;
 406         case C_SEXT:
 407         case C_LEXT:
 408                 s->used.ireg |= 1<<REGSB;
 409                 if(ad)
 410                         break;
 411                 s->size = sz;
 412                 s->offset = regoff(&p->to);
 413
 414                 if(ar)
 415                         s->used.cc |= E_MEMSB;
 416                 else
 417                         s->set.cc |= E_MEMSB;
 418                 break;
 419         }
 420
 421 /*
 422  * flags based on 'from' field
 423  */
 424         c = p->from.class;
 425         if(c == 0) {
 426                 c = aclass(&p->from) + 1;
 427                 p->from.class = c;
 428         }
 429         c--;
 430         switch(c) {
 431         default:
 432                 print("unknown class %d %D\n", c, &p->from);
 433
 434         case C_ZCON:
 435         case C_ICON:
 436         case C_SCON:
 437         case C_SICON:
 438         case C_LCON:
 439         case C_NONE:
 440         case C_SBRA:
 441         case C_LBRA:
 442                 break;
 443         case C_PSR:
 444                 s->used.cc |= E_PSR;
 445                 break;
 446         case C_ZOREG:
 447         case C_SOREG:
 448         case C_LOREG:
 449                 c = p->from.reg;
 450                 s->used.ireg |= 1<<c;
 451                 if(ld)
 452                         p->mark |= LOAD;
 453                 s->size = sz;
 454                 s->offset = regoff(&p->from);
 455
 456                 m = ANYMEM;
 457                 if(c == REGSB)
 458                         m = E_MEMSB;
 459                 if(c == REGSP)
 460                         m = E_MEMSP;
 461
 462                 s->used.cc |= m;
 463                 break;
 464         case C_SACON:
 465         case C_LACON:
 466                 s->used.ireg |= 1<<REGSP;
 467                 break;
 468         case C_SECON:
 469         case C_LECON:
 470                 s->used.ireg |= 1<<REGSB;
 471                 break;
 472         case C_REG:
 473                 s->used.ireg |= 1<<p->from.reg;
 474                 break;
 475         case C_REGREG:
 476                 s->used.ireg |= 1<<p->from.reg;
 477                 s->used.ireg |= 1<<p->from.offset;
 478                 break;
 479         case C_FREG:
 480                 /* do better -- determine double prec */
 481                 s->used.freg |= 1<<p->from.reg;
 482                 s->used.freg |= 1<<(p->from.reg|1);
 483                 if(ld && p->to.type == D_REG)
 484                         p->mark |= LOAD;
 485                 break;
 486         case C_SAUTO:
 487         case C_LAUTO:
 488                 s->used.ireg |= 1<<REGSP;
 489                 if(ld)
 490                         p->mark |= LOAD;
 491                 if(ad)
 492                         break;
 493                 s->size = sz;
 494                 s->offset = regoff(&p->from);
 495
 496                 s->used.cc |= E_MEMSP;
 497                 break;
 498         case C_SEXT:
 499         case C_LEXT:
 500                 s->used.ireg |= 1<<REGSB;
 501                 if(ld)
 502                         p->mark |= LOAD;
 503                 if(ad)
 504                         break;
 505                 s->size = sz;
 506                 s->offset = regoff(&p->from);
 507
 508                 s->used.cc |= E_MEMSB;
 509                 break;
 510         }
 511
 512         c = p->reg;
 513         if(c != NREG) {
 514                 if(p->from.type == D_FREG || p->to.type == D_FREG) {
 515                         s->used.freg |= 1<<c;
 516                         s->used.freg |= 1<<(c|1);
 517                 } else
 518                         s->used.ireg |= 1<<c;
 519         }
 520 }
 521
 522 /*
 523  * test to see if 2 instrictions can be
 524  * interchanged without changing semantics
 525  */
 526 int
 527 depend(Sch *sa, Sch *sb)
 528 {
 529         ulong x;
 530
 531         if(sa->set.ireg & (sb->set.ireg|sb->used.ireg))
 532                 return 1;
 533         if(sb->set.ireg & sa->used.ireg)
 534                 return 1;
 535
 536         if(sa->set.freg & (sb->set.freg|sb->used.freg))
 537                 return 1;
 538         if(sb->set.freg & sa->used.freg)
 539                 return 1;
 540
 541         /*
 542          * special case.
 543          * loads from same address cannot pass.
 544          * this is for hardware fifo's and the like
 545          */
 546         if(sa->used.cc & sb->used.cc & E_MEM)
 547                 if(sa->p.reg == sb->p.reg)
 548                 if(regoff(&sa->p.from) == regoff(&sb->p.from))
 549                         return 1;
 550
 551         x = (sa->set.cc & (sb->set.cc|sb->used.cc)) |
 552                 (sb->set.cc & sa->used.cc);
 553         if(x) {
 554                 /*
 555                  * allow SB and SP to pass each other.
 556                  * allow SB to pass SB iff doffsets are ok
 557                  * anything else conflicts
 558                  */
 559                 if(x != E_MEMSP && x != E_MEMSB)
 560                         return 1;
 561                 x = sa->set.cc | sb->set.cc |
 562                         sa->used.cc | sb->used.cc;
 563                 if(x & E_MEM)
 564                         return 1;
 565                 if(offoverlap(sa, sb))
 566                         return 1;
 567         }
 568
 569         return 0;
 570 }
 571
 572 int
 573 offoverlap(Sch *sa, Sch *sb)
 574 {
 575
 576         if(sa->offset < sb->offset) {
 577                 if(sa->offset+sa->size > sb->offset)
 578                         return 1;
 579                 return 0;
 580         }
 581         if(sb->offset+sb->size > sa->offset)
 582                 return 1;
 583         return 0;
 584 }
 585
 586 /*
 587  * test 2 adjacent instructions
 588  * and find out if inserted instructions
 589  * are desired to prevent stalls.
 590  */
 591 int
 592 conflict(Sch *sa, Sch *sb)
 593 {
 594
 595         if(sa->set.ireg & sb->used.ireg)
 596                 return 1;
 597         if(sa->set.freg & sb->used.freg)
 598                 return 1;
 599         if(sa->set.cc & sb->used.cc)
 600                 return 1;
 601
 602         return 0;
 603 }
 604
 605 int
 606 compound(Prog *p)
 607 {
 608         Optab *o;
 609
 610         o = oplook(p);
 611         if(o->size != 4)
 612                 return 1;
 613         if(p->to.type == D_REG && p->to.reg == REGSB)
 614                 return 1;
 615         return 0;
 616 }
 617
 618 void
 619 dumpbits(Sch *s, Dep *d)
 620 {
 621         int i;
 622
 623         for(i=0; i<32; i++)
 624                 if(d->ireg & (1<<i))
 625                         Bprint(&bso, " R%d", i);
 626         for(i=0; i<32; i++)
 627                 if(d->freg & (1<<i))
 628                         Bprint(&bso, " F%d", i);
 629         for(i=0; i<32; i++)
 630                 switch(d->cc & (1<<i)) {
 631                 default:
 632                         break;
 633                 case E_PSR:
 634                         Bprint(&bso, " PSR");
 635                         break;
 636                 case E_MEM:
 637                         Bprint(&bso, " MEM%d", s->size);
 638                         break;
 639                 case E_MEMSB:
 640                         Bprint(&bso, " SB%d", s->size);
 641                         break;
 642                 case E_MEMSP:
 643                         Bprint(&bso, " SP%d", s->size);
 644                         break;
 645                 }
 646 }