sys/src/cmd/5c/reg.c

   1 #include "gc.h"
   2
   3 void    addsplits(void);
   4
   5 Reg*
   6 rega(void)
   7 {
   8         Reg *r;
   9
  10         r = freer;
  11         if(r == R) {
  12                 r = alloc(sizeof(*r));
  13         } else
  14                 freer = r->link;
  15
  16         *r = zreg;
  17         return r;
  18 }
  19
  20 int
  21 rcmp(const void *a1, const void *a2)
  22 {
  23         Rgn *p1, *p2;
  24         int c1, c2;
  25
  26         p1 = (Rgn*)a1;
  27         p2 = (Rgn*)a2;
  28         c1 = p2->cost;
  29         c2 = p1->cost;
  30         if(c1 -= c2)
  31                 return c1;
  32         return p2->varno - p1->varno;
  33 }
  34
  35 void
  36 regopt(Prog *p)
  37 {
  38         Reg *r, *r1, *r2;
  39         Prog *p1;
  40         int i, z;
  41         long initpc, val, npc;
  42         ulong vreg;
  43         Bits bit;
  44         struct
  45         {
  46                 long    m;
  47                 long    c;
  48                 Reg*    p;
  49         } log5[6], *lp;
  50
  51         firstr = R;
  52         lastr = R;
  53         nvar = 0;
  54         regbits = 0;
  55         for(z=0; z<BITS; z++) {
  56                 externs.b[z] = 0;
  57                 params.b[z] = 0;
  58                 consts.b[z] = 0;
  59                 addrs.b[z] = 0;
  60         }
  61
  62         /*
  63          * pass 1
  64          * build aux data structure
  65          * allocate pcs
  66          * find use and set of variables
  67          */
  68         val = 5L * 5L * 5L * 5L * 5L;
  69         lp = log5;
  70         for(i=0; i<5; i++) {
  71                 lp->m = val;
  72                 lp->c = 0;
  73                 lp->p = R;
  74                 val /= 5L;
  75                 lp++;
  76         }
  77         val = 0;
  78         for(; p != P; p = p->link) {
  79                 switch(p->as) {
  80                 case ADATA:
  81                 case AGLOBL:
  82                 case ANAME:
  83                 case ASIGNAME:
  84                         continue;
  85                 }
  86                 r = rega();
  87                 if(firstr == R) {
  88                         firstr = r;
  89                         lastr = r;
  90                 } else {
  91                         lastr->link = r;
  92                         r->p1 = lastr;
  93                         lastr->s1 = r;
  94                         lastr = r;
  95                 }
  96                 r->prog = p;
  97                 r->pc = val;
  98                 val++;
  99
 100                 lp = log5;
 101                 for(i=0; i<5; i++) {
 102                         lp->c--;
 103                         if(lp->c <= 0) {
 104                                 lp->c = lp->m;
 105                                 if(lp->p != R)
 106                                         lp->p->log5 = r;
 107                                 lp->p = r;
 108                                 (lp+1)->c = 0;
 109                                 break;
 110                         }
 111                         lp++;
 112                 }
 113
 114                 r1 = r->p1;
 115                 if(r1 != R)
 116                 switch(r1->prog->as) {
 117                 case ARET:
 118                 case AB:
 119                 case ARFE:
 120                         r->p1 = R;
 121                         r1->s1 = R;
 122                 }
 123
 124                 /*
 125                  * left side always read
 126                  */
 127                 bit = mkvar(&p->from, p->as==AMOVW);
 128                 for(z=0; z<BITS; z++)
 129                         r->use1.b[z] |= bit.b[z];
 130
 131                 /*
 132                  * right side depends on opcode
 133                  */
 134                 bit = mkvar(&p->to, 0);
 135                 if(bany(&bit))
 136                 switch(p->as) {
 137                 default:
 138                         diag(Z, "reg: unknown asop: %A", p->as);
 139                         break;
 140
 141                 /*
 142                  * right side write
 143                  */
 144                 case ANOP:
 145                 case AMOVB:
 146                 case AMOVBU:
 147                 case AMOVH:
 148                 case AMOVHU:
 149                 case AMOVW:
 150                 case AMOVF:
 151                 case AMOVD:
 152                         for(z=0; z<BITS; z++)
 153                                 r->set.b[z] |= bit.b[z];
 154                         break;
 155
 156                 /*
 157                  * funny
 158                  */
 159                 case ABL:
 160                         for(z=0; z<BITS; z++)
 161                                 addrs.b[z] |= bit.b[z];
 162                         break;
 163                 }
 164
 165                 if(p->as == AMOVM) {
 166                         if(p->from.type == D_CONST)
 167                                 z = p->from.offset;
 168                         else
 169                                 z = p->to.offset;
 170                         for(i=0; z; i++) {
 171                                 if(z&1)
 172                                         regbits |= RtoB(i);
 173                                 z >>= 1;
 174                         }
 175                 }
 176         }
 177         if(firstr == R)
 178                 return;
 179         initpc = pc - val;
 180         npc = val;
 181
 182         /*
 183          * pass 2
 184          * turn branch references to pointers
 185          * build back pointers
 186          */
 187         for(r = firstr; r != R; r = r->link) {
 188                 p = r->prog;
 189                 if(p->to.type == D_BRANCH) {
 190                         val = p->to.offset - initpc;
 191                         r1 = firstr;
 192                         while(r1 != R) {
 193                                 r2 = r1->log5;
 194                                 if(r2 != R && val >= r2->pc) {
 195                                         r1 = r2;
 196                                         continue;
 197                                 }
 198                                 if(r1->pc == val)
 199                                         break;
 200                                 r1 = r1->link;
 201                         }
 202                         if(r1 == R) {
 203                                 nearln = p->lineno;
 204                                 diag(Z, "ref not found\n%P", p);
 205                                 continue;
 206                         }
 207                         if(r1 == r) {
 208                                 nearln = p->lineno;
 209                                 diag(Z, "ref to self\n%P", p);
 210                                 continue;
 211                         }
 212                         r->s2 = r1;
 213                         r->p2link = r1->p2;
 214                         r1->p2 = r;
 215                 }
 216         }
 217         if(debug['R']) {
 218                 p = firstr->prog;
 219                 print("\n%L %D\n", p->lineno, &p->from);
 220         }
 221
 222         /*
 223          * pass 2.5
 224          * find looping structure
 225          */
 226         for(r = firstr; r != R; r = r->link)
 227                 r->active = 0;
 228         change = 0;
 229         loopit(firstr, npc);
 230
 231         /*
 232          * pass 3
 233          * iterate propagating usage
 234          *      back until flow graph is complete
 235          */
 236 loop1:
 237         change = 0;
 238         for(r = firstr; r != R; r = r->link)
 239                 r->active = 0;
 240         for(r = firstr; r != R; r = r->link)
 241                 if(r->prog->as == ARET)
 242                         prop(r, zbits, zbits);
 243 loop11:
 244         /* pick up unreachable code */
 245         i = 0;
 246         for(r = firstr; r != R; r = r1) {
 247                 r1 = r->link;
 248                 if(r1 && r1->active && !r->active) {
 249                         prop(r, zbits, zbits);
 250                         i = 1;
 251                 }
 252         }
 253         if(i)
 254                 goto loop11;
 255         if(change)
 256                 goto loop1;
 257
 258
 259         /*
 260          * pass 4
 261          * iterate propagating register/variable synchrony
 262          *      forward until graph is complete
 263          */
 264 loop2:
 265         change = 0;
 266         for(r = firstr; r != R; r = r->link)
 267                 r->active = 0;
 268         synch(firstr, zbits);
 269         if(change)
 270                 goto loop2;
 271
 272         addsplits();
 273
 274         if(debug['R'] && debug['v']) {
 275                 print("\nprop structure:\n");
 276                 for(r = firstr; r != R; r = r->link) {
 277                         print("%ld:%P", r->loop, r->prog);
 278                         for(z=0; z<BITS; z++)
 279                                 bit.b[z] = r->set.b[z] |
 280                                         r->refahead.b[z] | r->calahead.b[z] |
 281                                         r->refbehind.b[z] | r->calbehind.b[z] |
 282                                         r->use1.b[z] | r->use2.b[z];
 283                         if(bany(&bit)) {
 284                                 print("\t");
 285                                 if(bany(&r->use1))
 286                                         print(" u1=%B", r->use1);
 287                                 if(bany(&r->use2))
 288                                         print(" u2=%B", r->use2);
 289                                 if(bany(&r->set))
 290                                         print(" st=%B", r->set);
 291                                 if(bany(&r->refahead))
 292                                         print(" ra=%B", r->refahead);
 293                                 if(bany(&r->calahead))
 294                                         print(" ca=%B", r->calahead);
 295                                 if(bany(&r->refbehind))
 296                                         print(" rb=%B", r->refbehind);
 297                                 if(bany(&r->calbehind))
 298                                         print(" cb=%B", r->calbehind);
 299                         }
 300                         print("\n");
 301                 }
 302         }
 303
 304         /*
 305          * pass 5
 306          * isolate regions
 307          * calculate costs (paint1)
 308          */
 309         r = firstr;
 310         if(r) {
 311                 for(z=0; z<BITS; z++)
 312                         bit.b[z] = (r->refahead.b[z] | r->calahead.b[z]) &
 313                           ~(externs.b[z] | params.b[z] | addrs.b[z] | consts.b[z]);
 314                 if(bany(&bit)) {
 315                         nearln = r->prog->lineno;
 316                         warn(Z, "used and not set: %B", bit);
 317                         if(debug['R'] && !debug['w'])
 318                                 print("used and not set: %B\n", bit);
 319                 }
 320         }
 321
 322         for(r = firstr; r != R; r = r->link)
 323                 r->act = zbits;
 324         rgp = region;
 325         nregion = 0;
 326         for(r = firstr; r != R; r = r->link) {
 327                 for(z=0; z<BITS; z++)
 328                         bit.b[z] = r->set.b[z] &
 329                           ~(r->refahead.b[z] | r->calahead.b[z] | addrs.b[z]);
 330                 if(bany(&bit)) {
 331                         nearln = r->prog->lineno;
 332                         warn(Z, "set and not used: %B", bit);
 333                         if(debug['R'])
 334                                 print("set and not used: %B\n", bit);
 335                         excise(r);
 336                 }
 337                 for(z=0; z<BITS; z++)
 338                         bit.b[z] = LOAD(r) & ~(r->act.b[z] | addrs.b[z]);
 339                 while(bany(&bit)) {
 340                         i = bnum(bit);
 341                         rgp->enter = r;
 342                         rgp->varno = i;
 343                         change = 0;
 344                         if(debug['R'] && debug['v'])
 345                                 print("\n");
 346                         paint1(r, i);
 347                         bit.b[i/32] &= ~(1L<<(i%32));
 348                         if(change <= 0) {
 349                                 if(debug['R'])
 350                                         print("%L $%d: %B\n",
 351                                                 r->prog->lineno, change, blsh(i));
 352                                 continue;
 353                         }
 354                         rgp->cost = change;
 355                         nregion++;
 356                         if(nregion >= NRGN) {
 357                                 warn(Z, "too many regions");
 358                                 goto brk;
 359                         }
 360                         rgp++;
 361                 }
 362         }
 363 brk:
 364         qsort(region, nregion, sizeof(region[0]), rcmp);
 365
 366         /*
 367          * pass 6
 368          * determine used registers (paint2)
 369          * replace code (paint3)
 370          */
 371         rgp = region;
 372         for(i=0; i<nregion; i++) {
 373                 bit = blsh(rgp->varno);
 374                 vreg = paint2(rgp->enter, rgp->varno);
 375                 vreg = allreg(vreg, rgp);
 376                 if(debug['R']) {
 377                         if(rgp->regno >= NREG)
 378                                 print("%L $%d F%d: %B\n",
 379                                         rgp->enter->prog->lineno,
 380                                         rgp->cost,
 381                                         rgp->regno-NREG,
 382                                         bit);
 383                         else
 384                                 print("%L $%d R%d: %B\n",
 385                                         rgp->enter->prog->lineno,
 386                                         rgp->cost,
 387                                         rgp->regno,
 388                                         bit);
 389                 }
 390                 if(rgp->regno != 0)
 391                         paint3(rgp->enter, rgp->varno, vreg, rgp->regno);
 392                 rgp++;
 393         }
 394         /*
 395          * pass 7
 396          * peep-hole on basic block
 397          */
 398         if(!debug['R'] || debug['P'])
 399                 peep();
 400
 401         /*
 402          * pass 8
 403          * recalculate pc
 404          */
 405         val = initpc;
 406         for(r = firstr; r != R; r = r1) {
 407                 r->pc = val;
 408                 p = r->prog;
 409                 p1 = P;
 410                 r1 = r->link;
 411                 if(r1 != R)
 412                         p1 = r1->prog;
 413                 for(; p != p1; p = p->link) {
 414                         switch(p->as) {
 415                         default:
 416                                 val++;
 417                                 break;
 418
 419                         case ANOP:
 420                         case ADATA:
 421                         case AGLOBL:
 422                         case ANAME:
 423                         case ASIGNAME:
 424                                 break;
 425                         }
 426                 }
 427         }
 428         pc = val;
 429
 430         /*
 431          * fix up branches
 432          */
 433         if(debug['R'])
 434                 if(bany(&addrs))
 435                         print("addrs: %B\n", addrs);
 436
 437         r1 = 0; /* set */
 438         for(r = firstr; r != R; r = r->link) {
 439                 p = r->prog;
 440                 if(p->to.type == D_BRANCH)
 441                         p->to.offset = r->s2->pc;
 442                 r1 = r;
 443         }
 444
 445         /*
 446          * last pass
 447          * eliminate nops
 448          * free aux structures
 449          */
 450         for(p = firstr->prog; p != P; p = p->link){
 451                 while(p->link && p->link->as == ANOP)
 452                         p->link = p->link->link;
 453         }
 454         if(r1 != R) {
 455                 r1->link = freer;
 456                 freer = firstr;
 457         }
 458 }
 459
 460 void
 461 addsplits(void)
 462 {
 463         Reg *r, *r1;
 464         int z, i;
 465         Bits bit;
 466
 467         for(r = firstr; r != R; r = r->link) {
 468                 if(r->loop > 1)
 469                         continue;
 470                 if(r->prog->as == ABL)
 471                         continue;
 472                 for(r1 = r->p2; r1 != R; r1 = r1->p2link) {
 473                         if(r1->loop <= 1)
 474                                 continue;
 475                         for(z=0; z<BITS; z++)
 476                                 bit.b[z] = r1->calbehind.b[z] &
 477                                         (r->refahead.b[z] | r->use1.b[z] | r->use2.b[z]) &
 478                                         ~(r->calahead.b[z] & addrs.b[z]);
 479                         while(bany(&bit)) {
 480                                 i = bnum(bit);
 481                                 bit.b[i/32] &= ~(1L << (i%32));
 482                         }
 483                 }
 484         }
 485 }
 486
 487 /*
 488  * add mov b,rn
 489  * just after r
 490  */
 491 void
 492 addmove(Reg *r, int bn, int rn, int f)
 493 {
 494         Prog *p, *p1;
 495         Adr *a;
 496         Var *v;
 497
 498         p1 = alloc(sizeof(*p1));
 499         *p1 = zprog;
 500         p = r->prog;
 501
 502         p1->link = p->link;
 503         p->link = p1;
 504         p1->lineno = p->lineno;
 505
 506         v = var + bn;
 507
 508         a = &p1->to;
 509         a->sym = v->sym;
 510         a->name = v->name;
 511         a->offset = v->offset;
 512         a->etype = v->etype;
 513         a->type = D_OREG;
 514         if(a->etype == TARRAY || a->sym == S)
 515                 a->type = D_CONST;
 516
 517         p1->as = AMOVW;
 518         if(v->etype == TCHAR || v->etype == TUCHAR)
 519                 p1->as = AMOVB;
 520         if(v->etype == TSHORT || v->etype == TUSHORT)
 521                 p1->as = AMOVH;
 522         if(v->etype == TFLOAT)
 523                 p1->as = AMOVF;
 524         if(v->etype == TDOUBLE)
 525                 p1->as = AMOVD;
 526
 527         p1->from.type = D_REG;
 528         p1->from.reg = rn;
 529         if(rn >= NREG) {
 530                 p1->from.type = D_FREG;
 531                 p1->from.reg = rn-NREG;
 532         }
 533         if(!f) {
 534                 p1->from = *a;
 535                 *a = zprog.from;
 536                 a->type = D_REG;
 537                 a->reg = rn;
 538                 if(rn >= NREG) {
 539                         a->type = D_FREG;
 540                         a->reg = rn-NREG;
 541                 }
 542                 if(v->etype == TUCHAR)
 543                         p1->as = AMOVBU;
 544                 if(v->etype == TUSHORT)
 545                         p1->as = AMOVHU;
 546         }
 547         if(debug['R'])
 548                 print("%P\t.a%P\n", p, p1);
 549 }
 550
 551 Bits
 552 mkvar(Adr *a, int docon)
 553 {
 554         Var *v;
 555         int i, t, n, et, z;
 556         long o;
 557         Bits bit;
 558         Sym *s;
 559
 560         t = a->type;
 561         if(t == D_REG && a->reg != NREG)
 562                 regbits |= RtoB(a->reg);
 563         if(t == D_FREG && a->reg != NREG)
 564                 regbits |= FtoB(a->reg);
 565         s = a->sym;
 566         o = a->offset;
 567         et = a->etype;
 568         if(s == S) {
 569                 if(t != D_CONST || !docon || a->reg != NREG)
 570                         goto none;
 571                 et = TLONG;
 572         }
 573         if(t == D_CONST) {
 574                 if(s == S && sval(o))
 575                         goto none;
 576         }
 577
 578         n = a->name;
 579         v = var;
 580         for(i=0; i<nvar; i++) {
 581                 if(s == v->sym)
 582                 if(n == v->name)
 583                 if(o == v->offset)
 584                         goto out;
 585                 v++;
 586         }
 587         if(s)
 588                 if(s->name[0] == '.')
 589                         goto none;
 590         if(nvar >= NVAR) {
 591                 if(debug['w'] > 1 && s)
 592                         warn(Z, "variable not optimized: %s", s->name);
 593                 goto none;
 594         }
 595         i = nvar;
 596         nvar++;
 597         v = &var[i];
 598         v->sym = s;
 599         v->offset = o;
 600         v->etype = et;
 601         v->name = n;
 602         if(debug['R'])
 603                 print("bit=%2d et=%2d %D\n", i, et, a);
 604 out:
 605         bit = blsh(i);
 606         if(n == D_EXTERN || n == D_STATIC)
 607                 for(z=0; z<BITS; z++)
 608                         externs.b[z] |= bit.b[z];
 609         if(n == D_PARAM)
 610                 for(z=0; z<BITS; z++)
 611                         params.b[z] |= bit.b[z];
 612         if(v->etype != et || !typechlpfd[et])   /* funny punning */
 613                 for(z=0; z<BITS; z++)
 614                         addrs.b[z] |= bit.b[z];
 615         if(t == D_CONST) {
 616                 if(s == S) {
 617                         for(z=0; z<BITS; z++)
 618                                 consts.b[z] |= bit.b[z];
 619                         return bit;
 620                 }
 621                 if(et != TARRAY)
 622                         for(z=0; z<BITS; z++)
 623                                 addrs.b[z] |= bit.b[z];
 624                 for(z=0; z<BITS; z++)
 625                         params.b[z] |= bit.b[z];
 626                 return bit;
 627         }
 628         if(t == D_OREG)
 629                 return bit;
 630
 631 none:
 632         return zbits;
 633 }
 634
 635 void
 636 prop(Reg *r, Bits ref, Bits cal)
 637 {
 638         Reg *r1, *r2;
 639         int z;
 640
 641         for(r1 = r; r1 != R; r1 = r1->p1) {
 642                 for(z=0; z<BITS; z++) {
 643                         ref.b[z] |= r1->refahead.b[z];
 644                         if(ref.b[z] != r1->refahead.b[z]) {
 645                                 r1->refahead.b[z] = ref.b[z];
 646                                 change++;
 647                         }
 648                         cal.b[z] |= r1->calahead.b[z];
 649                         if(cal.b[z] != r1->calahead.b[z]) {
 650                                 r1->calahead.b[z] = cal.b[z];
 651                                 change++;
 652                         }
 653                 }
 654                 switch(r1->prog->as) {
 655                 case ABL:
 656                         for(z=0; z<BITS; z++) {
 657                                 cal.b[z] |= ref.b[z] | externs.b[z];
 658                                 ref.b[z] = 0;
 659                         }
 660                         break;
 661
 662                 case ATEXT:
 663                         for(z=0; z<BITS; z++) {
 664                                 cal.b[z] = 0;
 665                                 ref.b[z] = 0;
 666                         }
 667                         break;
 668
 669                 case ARET:
 670                         for(z=0; z<BITS; z++) {
 671                                 cal.b[z] = externs.b[z];
 672                                 ref.b[z] = 0;
 673                         }
 674                 }
 675                 for(z=0; z<BITS; z++) {
 676                         ref.b[z] = (ref.b[z] & ~r1->set.b[z]) |
 677                                 r1->use1.b[z] | r1->use2.b[z];
 678                         cal.b[z] &= ~(r1->set.b[z] | r1->use1.b[z] | r1->use2.b[z]);
 679                         r1->refbehind.b[z] = ref.b[z];
 680                         r1->calbehind.b[z] = cal.b[z];
 681                 }
 682                 if(r1->active)
 683                         break;
 684                 r1->active = 1;
 685         }
 686         for(; r != r1; r = r->p1)
 687                 for(r2 = r->p2; r2 != R; r2 = r2->p2link)
 688                         prop(r2, r->refbehind, r->calbehind);
 689 }
 690
 691 /*
 692  * find looping structure
 693  *
 694  * 1) find reverse postordering
 695  * 2) find approximate dominators,
 696  *      the actual dominators if the flow graph is reducible
 697  *      otherwise, dominators plus some other non-dominators.
 698  *      See Matthew S. Hecht and Jeffrey D. Ullman,
 699  *      "Analysis of a Simple Algorithm for Global Data Flow Problems",
 700  *      Conf.  Record of ACM Symp. on Principles of Prog. Langs, Boston, Massachusetts,
 701  *      Oct. 1-3, 1973, pp.  207-217.
 702  * 3) find all nodes with a predecessor dominated by the current node.
 703  *      such a node is a loop head.
 704  *      recursively, all preds with a greater rpo number are in the loop
 705  */
 706 long
 707 postorder(Reg *r, Reg **rpo2r, long n)
 708 {
 709         Reg *r1;
 710
 711         r->rpo = 1;
 712         r1 = r->s1;
 713         if(r1 && !r1->rpo)
 714                 n = postorder(r1, rpo2r, n);
 715         r1 = r->s2;
 716         if(r1 && !r1->rpo)
 717                 n = postorder(r1, rpo2r, n);
 718         rpo2r[n] = r;
 719         n++;
 720         return n;
 721 }
 722
 723 long
 724 rpolca(long *idom, long rpo1, long rpo2)
 725 {
 726         long t;
 727
 728         if(rpo1 == -1)
 729                 return rpo2;
 730         while(rpo1 != rpo2){
 731                 if(rpo1 > rpo2){
 732                         t = rpo2;
 733                         rpo2 = rpo1;
 734                         rpo1 = t;
 735                 }
 736                 while(rpo1 < rpo2){
 737                         t = idom[rpo2];
 738                         if(t >= rpo2)
 739                                 fatal(Z, "bad idom");
 740                         rpo2 = t;
 741                 }
 742         }
 743         return rpo1;
 744 }
 745
 746 int
 747 doms(long *idom, long r, long s)
 748 {
 749         while(s > r)
 750                 s = idom[s];
 751         return s == r;
 752 }
 753
 754 int
 755 loophead(long *idom, Reg *r)
 756 {
 757         long src;
 758
 759         src = r->rpo;
 760         if(r->p1 != R && doms(idom, src, r->p1->rpo))
 761                 return 1;
 762         for(r = r->p2; r != R; r = r->p2link)
 763                 if(doms(idom, src, r->rpo))
 764                         return 1;
 765         return 0;
 766 }
 767
 768 void
 769 loopmark(Reg **rpo2r, long head, Reg *r)
 770 {
 771         if(r->rpo < head || r->active == head)
 772                 return;
 773         r->active = head;
 774         r->loop += LOOP;
 775         if(r->p1 != R)
 776                 loopmark(rpo2r, head, r->p1);
 777         for(r = r->p2; r != R; r = r->p2link)
 778                 loopmark(rpo2r, head, r);
 779 }
 780
 781 void
 782 loopit(Reg *r, long nr)
 783 {
 784         Reg *r1;
 785         long i, d, me;
 786
 787         if(nr > maxnr) {
 788                 rpo2r = alloc(nr * sizeof(Reg*));
 789                 idom = alloc(nr * sizeof(long));
 790                 maxnr = nr;
 791         }
 792
 793         d = postorder(r, rpo2r, 0);
 794         if(d > nr)
 795                 fatal(Z, "too many reg nodes");
 796         nr = d;
 797         for(i = 0; i < nr / 2; i++){
 798                 r1 = rpo2r[i];
 799                 rpo2r[i] = rpo2r[nr - 1 - i];
 800                 rpo2r[nr - 1 - i] = r1;
 801         }
 802         for(i = 0; i < nr; i++)
 803                 rpo2r[i]->rpo = i;
 804
 805         idom[0] = 0;
 806         for(i = 0; i < nr; i++){
 807                 r1 = rpo2r[i];
 808                 me = r1->rpo;
 809                 d = -1;
 810                 if(r1->p1 != R && r1->p1->rpo < me)
 811                         d = r1->p1->rpo;
 812                 for(r1 = r1->p2; r1 != nil; r1 = r1->p2link)
 813                         if(r1->rpo < me)
 814                                 d = rpolca(idom, d, r1->rpo);
 815                 idom[i] = d;
 816         }
 817
 818         for(i = 0; i < nr; i++){
 819                 r1 = rpo2r[i];
 820                 r1->loop++;
 821                 if(r1->p2 != R && loophead(idom, r1))
 822                         loopmark(rpo2r, i, r1);
 823         }
 824 }
 825
 826 void
 827 synch(Reg *r, Bits dif)
 828 {
 829         Reg *r1;
 830         int z;
 831
 832         for(r1 = r; r1 != R; r1 = r1->s1) {
 833                 for(z=0; z<BITS; z++) {
 834                         dif.b[z] = (dif.b[z] &
 835                                 ~(~r1->refbehind.b[z] & r1->refahead.b[z])) |
 836                                         r1->set.b[z] | r1->regdiff.b[z];
 837                         if(dif.b[z] != r1->regdiff.b[z]) {
 838                                 r1->regdiff.b[z] = dif.b[z];
 839                                 change++;
 840                         }
 841                 }
 842                 if(r1->active)
 843                         break;
 844                 r1->active = 1;
 845                 for(z=0; z<BITS; z++)
 846                         dif.b[z] &= ~(~r1->calbehind.b[z] & r1->calahead.b[z]);
 847                 if(r1->s2 != R)
 848                         synch(r1->s2, dif);
 849         }
 850 }
 851
 852 ulong
 853 allreg(ulong b, Rgn *r)
 854 {
 855         Var *v;
 856         int i;
 857
 858         v = var + r->varno;
 859         r->regno = 0;
 860         switch(v->etype) {
 861
 862         default:
 863                 diag(Z, "unknown etype %d/%d", bitno(b), v->etype);
 864                 break;
 865
 866         case TCHAR:
 867         case TUCHAR:
 868         case TSHORT:
 869         case TUSHORT:
 870         case TINT:
 871         case TUINT:
 872         case TLONG:
 873         case TULONG:
 874         case TIND:
 875         case TARRAY:
 876                 i = BtoR(~b);
 877                 if(i && r->cost >= 0) {
 878                         r->regno = i;
 879                         return RtoB(i);
 880                 }
 881                 break;
 882
 883         case TVLONG:
 884         case TDOUBLE:
 885         case TFLOAT:
 886                 i = BtoF(~b);
 887                 if(i && r->cost >= 0) {
 888                         r->regno = i+NREG;
 889                         return FtoB(i);
 890                 }
 891                 break;
 892         }
 893         return 0;
 894 }
 895
 896 void
 897 paint1(Reg *r, int bn)
 898 {
 899         Reg *r1;
 900         Prog *p;
 901         int z;
 902         ulong bb;
 903
 904         z = bn/32;
 905         bb = 1L<<(bn%32);
 906         if(r->act.b[z] & bb)
 907                 return;
 908         for(;;) {
 909                 if(!(r->refbehind.b[z] & bb))
 910                         break;
 911                 r1 = r->p1;
 912                 if(r1 == R)
 913                         break;
 914                 if(!(r1->refahead.b[z] & bb))
 915                         break;
 916                 if(r1->act.b[z] & bb)
 917                         break;
 918                 r = r1;
 919         }
 920
 921         if(LOAD(r) & ~(r->set.b[z] & ~(r->use1.b[z]|r->use2.b[z])) & bb) {
 922                 change -= CLOAD * r->loop;
 923                 if(debug['R'] && debug['v'])
 924                         print("%ld%P\tld %B $%d\n", r->loop,
 925                                 r->prog, blsh(bn), change);
 926         }
 927         for(;;) {
 928                 r->act.b[z] |= bb;
 929                 p = r->prog;
 930
 931                 if(r->use1.b[z] & bb) {
 932                         change += CREF * r->loop;
 933                         if(debug['R'] && debug['v'])
 934                                 print("%ld%P\tu1 %B $%d\n", r->loop,
 935                                         p, blsh(bn), change);
 936                 }
 937
 938                 if((r->use2.b[z]|r->set.b[z]) & bb) {
 939                         change += CREF * r->loop;
 940                         if(debug['R'] && debug['v'])
 941                                 print("%ld%P\tu2 %B $%d\n", r->loop,
 942                                         p, blsh(bn), change);
 943                 }
 944
 945                 if(STORE(r) & r->regdiff.b[z] & bb) {
 946                         change -= CLOAD * r->loop;
 947                         if(debug['R'] && debug['v'])
 948                                 print("%ld%P\tst %B $%d\n", r->loop,
 949                                         p, blsh(bn), change);
 950                 }
 951
 952                 if(r->refbehind.b[z] & bb)
 953                         for(r1 = r->p2; r1 != R; r1 = r1->p2link)
 954                                 if(r1->refahead.b[z] & bb)
 955                                         paint1(r1, bn);
 956
 957                 if(!(r->refahead.b[z] & bb))
 958                         break;
 959                 r1 = r->s2;
 960                 if(r1 != R)
 961                         if(r1->refbehind.b[z] & bb)
 962                                 paint1(r1, bn);
 963                 r = r->s1;
 964                 if(r == R)
 965                         break;
 966                 if(r->act.b[z] & bb)
 967                         break;
 968                 if(!(r->refbehind.b[z] & bb))
 969                         break;
 970         }
 971 }
 972
 973 ulong
 974 paint2(Reg *r, int bn)
 975 {
 976         Reg *r1;
 977         int z;
 978         ulong bb, vreg;
 979
 980         z = bn/32;
 981         bb = 1L << (bn%32);
 982         vreg = regbits;
 983         if(!(r->act.b[z] & bb))
 984                 return vreg;
 985         for(;;) {
 986                 if(!(r->refbehind.b[z] & bb))
 987                         break;
 988                 r1 = r->p1;
 989                 if(r1 == R)
 990                         break;
 991                 if(!(r1->refahead.b[z] & bb))
 992                         break;
 993                 if(!(r1->act.b[z] & bb))
 994                         break;
 995                 r = r1;
 996         }
 997         for(;;) {
 998                 r->act.b[z] &= ~bb;
 999
1000                 vreg |= r->regu;
1001
1002                 if(r->refbehind.b[z] & bb)
1003                         for(r1 = r->p2; r1 != R; r1 = r1->p2link)
1004                                 if(r1->refahead.b[z] & bb)
1005                                         vreg |= paint2(r1, bn);
1006
1007                 if(!(r->refahead.b[z] & bb))
1008                         break;
1009                 r1 = r->s2;
1010                 if(r1 != R)
1011                         if(r1->refbehind.b[z] & bb)
1012                                 vreg |= paint2(r1, bn);
1013                 r = r->s1;
1014                 if(r == R)
1015                         break;
1016                 if(!(r->act.b[z] & bb))
1017                         break;
1018                 if(!(r->refbehind.b[z] & bb))
1019                         break;
1020         }
1021         return vreg;
1022 }
1023
1024 void
1025 paint3(Reg *r, int bn, long rb, int rn)
1026 {
1027         Reg *r1;
1028         Prog *p;
1029         int z;
1030         ulong bb;
1031
1032         z = bn/32;
1033         bb = 1L << (bn%32);
1034         if(r->act.b[z] & bb)
1035                 return;
1036         for(;;) {
1037                 if(!(r->refbehind.b[z] & bb))
1038                         break;
1039                 r1 = r->p1;
1040                 if(r1 == R)
1041                         break;
1042                 if(!(r1->refahead.b[z] & bb))
1043                         break;
1044                 if(r1->act.b[z] & bb)
1045                         break;
1046                 r = r1;
1047         }
1048
1049         if(LOAD(r) & ~(r->set.b[z] & ~(r->use1.b[z]|r->use2.b[z])) & bb)
1050                 addmove(r, bn, rn, 0);
1051         for(;;) {
1052                 r->act.b[z] |= bb;
1053                 p = r->prog;
1054
1055                 if(r->use1.b[z] & bb) {
1056                         if(debug['R'])
1057                                 print("%P", p);
1058                         addreg(&p->from, rn);
1059                         if(debug['R'])
1060                                 print("\t.c%P\n", p);
1061                 }
1062                 if((r->use2.b[z]|r->set.b[z]) & bb) {
1063                         if(debug['R'])
1064                                 print("%P", p);
1065                         addreg(&p->to, rn);
1066                         if(debug['R'])
1067                                 print("\t.c%P\n", p);
1068                 }
1069
1070                 if(STORE(r) & r->regdiff.b[z] & bb)
1071                         addmove(r, bn, rn, 1);
1072                 r->regu |= rb;
1073
1074                 if(r->refbehind.b[z] & bb)
1075                         for(r1 = r->p2; r1 != R; r1 = r1->p2link)
1076                                 if(r1->refahead.b[z] & bb)
1077                                         paint3(r1, bn, rb, rn);
1078
1079                 if(!(r->refahead.b[z] & bb))
1080                         break;
1081                 r1 = r->s2;
1082                 if(r1 != R)
1083                         if(r1->refbehind.b[z] & bb)
1084                                 paint3(r1, bn, rb, rn);
1085                 r = r->s1;
1086                 if(r == R)
1087                         break;
1088                 if(r->act.b[z] & bb)
1089                         break;
1090                 if(!(r->refbehind.b[z] & bb))
1091                         break;
1092         }
1093 }
1094
1095 void
1096 addreg(Adr *a, int rn)
1097 {
1098
1099         a->sym = 0;
1100         a->name = D_NONE;
1101         a->type = D_REG;
1102         a->reg = rn;
1103         if(rn >= NREG) {
1104                 a->type = D_FREG;
1105                 a->reg = rn-NREG;
1106         }
1107 }
1108
1109 /*
1110  *      bit     reg
1111  *      0       R0
1112  *      1       R1
1113  *      ...     ...
1114  *      10      R10
1115  */
1116 long
1117 RtoB(int r)
1118 {
1119
1120         if(r >= REGMIN && r <= REGMAX)
1121                 return 1L << r;
1122         return 0;
1123 }
1124
1125 int
1126 BtoR(long b)
1127 {
1128         b &= 0x01fcL;   // excluded R9 and R10 for m and g
1129         if(b == 0)
1130                 return 0;
1131         return bitno(b);
1132 }
1133
1134 /*
1135  *      bit     reg
1136  *      18      F2
1137  *      19      F3
1138  *      ...     ...
1139  *      23      F7
1140  */
1141 long
1142 FtoB(int f)
1143 {
1144
1145         if(f < 2 || f > NFREG-1)
1146                 return 0;
1147         return 1L << (f + 16);
1148 }
1149
1150 int
1151 BtoF(long b)
1152 {
1153
1154         b &= 0xfc0000L;
1155         if(b == 0)
1156                 return 0;
1157         return bitno(b) - 16;
1158 }