sys/src/cmd/vc/peep.c

   1 #include "gc.h"
   2
   3 void
   4 peep(void)
   5 {
   6         Reg *r, *r1, *r2;
   7         Prog *p, *p1;
   8         int t;
   9 /*
  10  * complete R structure
  11  */
  12         t = 0;
  13         for(r=firstr; r!=R; r=r1) {
  14                 r1 = r->link;
  15                 if(r1 == R)
  16                         break;
  17                 p = r->prog->link;
  18                 while(p != r1->prog)
  19                 switch(p->as) {
  20                 default:
  21                         r2 = rega();
  22                         r->link = r2;
  23                         r2->link = r1;
  24
  25                         r2->prog = p;
  26                         r2->p1 = r;
  27                         r->s1 = r2;
  28                         r2->s1 = r1;
  29                         r1->p1 = r2;
  30
  31                         r = r2;
  32                         t++;
  33
  34                 case ADATA:
  35                 case AGLOBL:
  36                 case ANAME:
  37                 case ASIGNAME:
  38                         p = p->link;
  39                 }
  40         }
  41
  42 loop1:
  43         t = 0;
  44         for(r=firstr; r!=R; r=r->link) {
  45                 p = r->prog;
  46                 if(p->as == AMOVW || p->as == AMOVF || p->as == AMOVD)
  47                 if(regtyp(&p->to)) {
  48                         if(regtyp(&p->from))
  49                         if(p->from.type == p->to.type) {
  50                                 if(copyprop(r)) {
  51                                         excise(r);
  52                                         t++;
  53                                 } else
  54                                 if(subprop(r) && copyprop(r)) {
  55                                         excise(r);
  56                                         t++;
  57                                 }
  58                         }
  59                         if(regzer(&p->from))
  60                         if(p->to.type == D_REG) {
  61                                 p->from.type = D_REG;
  62                                 p->from.reg = 0;
  63                                 if(copyprop(r)) {
  64                                         excise(r);
  65                                         t++;
  66                                 } else
  67                                 if(subprop(r) && copyprop(r)) {
  68                                         excise(r);
  69                                         t++;
  70                                 }
  71                         }
  72                 }
  73         }
  74         if(t)
  75                 goto loop1;
  76         /*
  77          * look for MOVB x,R; MOVB R,R
  78          */
  79         for(r=firstr; r!=R; r=r->link) {
  80                 p = r->prog;
  81                 switch(p->as) {
  82                 default:
  83                         continue;
  84                 case AMOVH:
  85                 case AMOVHU:
  86                 case AMOVB:
  87                 case AMOVBU:
  88                         if(p->to.type != D_REG)
  89                                 continue;
  90                         break;
  91                 }
  92                 r1 = r->link;
  93                 if(r1 == R)
  94                         continue;
  95                 p1 = r1->prog;
  96                 if(p1->as != p->as)
  97                         continue;
  98                 if(p1->from.type != D_REG || p1->from.reg != p->to.reg)
  99                         continue;
 100                 if(p1->to.type != D_REG || p1->to.reg != p->to.reg)
 101                         continue;
 102                 excise(r1);
 103         }
 104 }
 105
 106 void
 107 excise(Reg *r)
 108 {
 109         Prog *p;
 110
 111         p = r->prog;
 112         p->as = ANOP;
 113         p->from = zprog.from;
 114         p->to = zprog.to;
 115         p->reg = zprog.reg; /**/
 116 }
 117
 118 Reg*
 119 uniqp(Reg *r)
 120 {
 121         Reg *r1;
 122
 123         r1 = r->p1;
 124         if(r1 == R) {
 125                 r1 = r->p2;
 126                 if(r1 == R || r1->p2link != R)
 127                         return R;
 128         } else
 129                 if(r->p2 != R)
 130                         return R;
 131         return r1;
 132 }
 133
 134 Reg*
 135 uniqs(Reg *r)
 136 {
 137         Reg *r1;
 138
 139         r1 = r->s1;
 140         if(r1 == R) {
 141                 r1 = r->s2;
 142                 if(r1 == R)
 143                         return R;
 144         } else
 145                 if(r->s2 != R)
 146                         return R;
 147         return r1;
 148 }
 149
 150 int
 151 regzer(Adr *a)
 152 {
 153
 154         if(a->type == D_CONST)
 155                 if(a->sym == S)
 156                         if(a->offset == 0)
 157                                 return 1;
 158         if(a->type == D_REG)
 159                 if(a->reg == 0)
 160                         return 1;
 161         return 0;
 162 }
 163
 164 int
 165 regtyp(Adr *a)
 166 {
 167
 168         if(a->type == D_REG) {
 169                 if(a->reg != 0)
 170                         return 1;
 171                 return 0;
 172         }
 173         if(a->type == D_FREG)
 174                 return 1;
 175         return 0;
 176 }
 177
 178 /*
 179  * the idea is to substitute
 180  * one register for another
 181  * from one MOV to another
 182  *      MOV     a, R0
 183  *      ADD     b, R0   / no use of R1
 184  *      MOV     R0, R1
 185  * would be converted to
 186  *      MOV     a, R1
 187  *      ADD     b, R1
 188  *      MOV     R1, R0
 189  * hopefully, then the former or latter MOV
 190  * will be eliminated by copy propagation.
 191  */
 192 int
 193 subprop(Reg *r0)
 194 {
 195         Prog *p;
 196         Adr *v1, *v2;
 197         Reg *r;
 198         int t;
 199
 200         p = r0->prog;
 201         v1 = &p->from;
 202         if(!regtyp(v1))
 203                 return 0;
 204         v2 = &p->to;
 205         if(!regtyp(v2))
 206                 return 0;
 207         for(r=uniqp(r0); r!=R; r=uniqp(r)) {
 208                 if(uniqs(r) == R)
 209                         break;
 210                 p = r->prog;
 211                 switch(p->as) {
 212                 case AJAL:
 213                         return 0;
 214
 215                 case ASGT:
 216                 case ASGTU:
 217
 218                 case AADD:
 219                 case AADDU:
 220                 case ASUB:
 221                 case ASUBU:
 222                 case ASLL:
 223                 case ASRL:
 224                 case ASRA:
 225                 case AOR:
 226                 case AAND:
 227                 case AXOR:
 228                 case AMUL:
 229                 case AMULU:
 230                 case ADIV:
 231                 case ADIVU:
 232
 233                 case AADDD:
 234                 case AADDF:
 235                 case ASUBD:
 236                 case ASUBF:
 237                 case AMULD:
 238                 case AMULF:
 239                 case ADIVD:
 240                 case ADIVF:
 241                         if(p->to.type == v1->type)
 242                         if(p->to.reg == v1->reg) {
 243                                 if(p->reg == NREG)
 244                                         p->reg = p->to.reg;
 245                                 goto gotit;
 246                         }
 247                         break;
 248
 249                 case AMOVF:
 250                 case AMOVD:
 251                 case AMOVW:
 252                         if(p->to.type == v1->type)
 253                         if(p->to.reg == v1->reg)
 254                                 goto gotit;
 255                         break;
 256                 }
 257                 if(copyau(&p->from, v2) ||
 258                    copyau1(p, v2) ||
 259                    copyau(&p->to, v2))
 260                         break;
 261                 if(copysub(&p->from, v1, v2, 0) ||
 262                    copysub1(p, v1, v2, 0) ||
 263                    copysub(&p->to, v1, v2, 0))
 264                         break;
 265         }
 266         return 0;
 267
 268 gotit:
 269         copysub(&p->to, v1, v2, 1);
 270         if(debug['P']) {
 271                 print("gotit: %D->%D\n%P", v1, v2, r->prog);
 272                 if(p->from.type == v2->type)
 273                         print(" excise");
 274                 print("\n");
 275         }
 276         for(r=uniqs(r); r!=r0; r=uniqs(r)) {
 277                 p = r->prog;
 278                 copysub(&p->from, v1, v2, 1);
 279                 copysub1(p, v1, v2, 1);
 280                 copysub(&p->to, v1, v2, 1);
 281                 if(debug['P'])
 282                         print("%P\n", r->prog);
 283         }
 284         t = v1->reg;
 285         v1->reg = v2->reg;
 286         v2->reg = t;
 287         if(debug['P'])
 288                 print("%P last\n", r->prog);
 289         return 1;
 290 }
 291
 292 /*
 293  * The idea is to remove redundant copies.
 294  *      v1->v2  F=0
 295  *      (use v2 s/v2/v1/)*
 296  *      set v1  F=1
 297  *      use v2  return fail
 298  *      -----------------
 299  *      v1->v2  F=0
 300  *      (use v2 s/v2/v1/)*
 301  *      set v1  F=1
 302  *      set v2  return success
 303  */
 304 int
 305 copyprop(Reg *r0)
 306 {
 307         Prog *p;
 308         Adr *v1, *v2;
 309         Reg *r;
 310
 311         p = r0->prog;
 312         v1 = &p->from;
 313         v2 = &p->to;
 314         if(copyas(v1, v2))
 315                 return 1;
 316         for(r=firstr; r!=R; r=r->link)
 317                 r->active = 0;
 318         return copy1(v1, v2, r0->s1, 0);
 319 }
 320
 321 int
 322 copy1(Adr *v1, Adr *v2, Reg *r, int f)
 323 {
 324         int t;
 325         Prog *p;
 326
 327         if(r->active) {
 328                 if(debug['P'])
 329                         print("act set; return 1\n");
 330                 return 1;
 331         }
 332         r->active = 1;
 333         if(debug['P'])
 334                 print("copy %D->%D f=%d\n", v1, v2, f);
 335         for(; r != R; r = r->s1) {
 336                 p = r->prog;
 337                 if(debug['P'])
 338                         print("%P", p);
 339                 if(!f && uniqp(r) == R) {
 340                         f = 1;
 341                         if(debug['P'])
 342                                 print("; merge; f=%d", f);
 343                 }
 344                 t = copyu(p, v2, A);
 345                 switch(t) {
 346                 case 2: /* rar, cant split */
 347                         if(debug['P'])
 348                                 print("; %Drar; return 0\n", v2);
 349                         return 0;
 350
 351                 case 3: /* set */
 352                         if(debug['P'])
 353                                 print("; %Dset; return 1\n", v2);
 354                         return 1;
 355
 356                 case 1: /* used, substitute */
 357                 case 4: /* use and set */
 358                         if(f) {
 359                                 if(!debug['P'])
 360                                         return 0;
 361                                 if(t == 4)
 362                                         print("; %Dused+set and f=%d; return 0\n", v2, f);
 363                                 else
 364                                         print("; %Dused and f=%d; return 0\n", v2, f);
 365                                 return 0;
 366                         }
 367                         if(copyu(p, v2, v1)) {
 368                                 if(debug['P'])
 369                                         print("; sub fail; return 0\n");
 370                                 return 0;
 371                         }
 372                         if(debug['P'])
 373                                 print("; sub%D/%D", v2, v1);
 374                         if(t == 4) {
 375                                 if(debug['P'])
 376                                         print("; %Dused+set; return 1\n", v2);
 377                                 return 1;
 378                         }
 379                         break;
 380                 }
 381                 if(!f) {
 382                         t = copyu(p, v1, A);
 383                         if(!f && (t == 2 || t == 3 || t == 4)) {
 384                                 f = 1;
 385                                 if(debug['P'])
 386                                         print("; %Dset and !f; f=%d", v1, f);
 387                         }
 388                 }
 389                 if(debug['P'])
 390                         print("\n");
 391                 if(r->s2)
 392                         if(!copy1(v1, v2, r->s2, f))
 393                                 return 0;
 394         }
 395         return 1;
 396 }
 397
 398 /*
 399  * return
 400  * 1 if v only used (and substitute),
 401  * 2 if read-alter-rewrite
 402  * 3 if set
 403  * 4 if set and used
 404  * 0 otherwise (not touched)
 405  */
 406 copyu(Prog *p, Adr *v, Adr *s)
 407 {
 408
 409         switch(p->as) {
 410
 411         default:
 412                 if(debug['P'])
 413                         print(" (???)");
 414                 return 2;
 415
 416
 417         case ANOP:      /* read, write */
 418         case AMOVW:
 419         case AMOVF:
 420         case AMOVD:
 421         case AMOVH:
 422         case AMOVHU:
 423         case AMOVB:
 424         case AMOVBU:
 425         case AMOVDW:
 426         case AMOVWD:
 427         case AMOVFD:
 428         case AMOVDF:
 429                 if(s != A) {
 430                         if(copysub(&p->from, v, s, 1))
 431                                 return 1;
 432                         if(!copyas(&p->to, v))
 433                                 if(copysub(&p->to, v, s, 1))
 434                                         return 1;
 435                         return 0;
 436                 }
 437                 if(copyas(&p->to, v)) {
 438                         if(copyau(&p->from, v))
 439                                 return 4;
 440                         return 3;
 441                 }
 442                 if(copyau(&p->from, v))
 443                         return 1;
 444                 if(copyau(&p->to, v))
 445                         return 1;
 446                 return 0;
 447
 448         case ASGT:      /* read, read, write */
 449         case ASGTU:
 450
 451         case AADD:
 452         case AADDU:
 453         case ASUB:
 454         case ASUBU:
 455         case ASLL:
 456         case ASRL:
 457         case ASRA:
 458         case AOR:
 459         case ANOR:
 460         case AAND:
 461         case AXOR:
 462         case AMUL:
 463         case AMULU:
 464         case ADIV:
 465         case ADIVU:
 466
 467         case AADDF:
 468         case AADDD:
 469         case ASUBF:
 470         case ASUBD:
 471         case AMULF:
 472         case AMULD:
 473         case ADIVF:
 474         case ADIVD:
 475                 if(s != A) {
 476                         if(copysub(&p->from, v, s, 1))
 477                                 return 1;
 478                         if(copysub1(p, v, s, 1))
 479                                 return 1;
 480                         if(!copyas(&p->to, v))
 481                                 if(copysub(&p->to, v, s, 1))
 482                                         return 1;
 483                         return 0;
 484                 }
 485                 if(copyas(&p->to, v)) {
 486                         if(p->reg == NREG)
 487                                 p->reg = p->to.reg;
 488                         if(copyau(&p->from, v))
 489                                 return 4;
 490                         if(copyau1(p, v))
 491                                 return 4;
 492                         return 3;
 493                 }
 494                 if(copyau(&p->from, v))
 495                         return 1;
 496                 if(copyau1(p, v))
 497                         return 1;
 498                 if(copyau(&p->to, v))
 499                         return 1;
 500                 return 0;
 501
 502         case ABEQ:      /* read, read */
 503         case ABNE:
 504         case ABGTZ:
 505         case ABGEZ:
 506         case ABLTZ:
 507         case ABLEZ:
 508
 509         case ACMPEQD:
 510         case ACMPEQF:
 511         case ACMPGED:
 512         case ACMPGEF:
 513         case ACMPGTD:
 514         case ACMPGTF:
 515         case ABFPF:
 516         case ABFPT:
 517                 if(s != A) {
 518                         if(copysub(&p->from, v, s, 1))
 519                                 return 1;
 520                         return copysub1(p, v, s, 1);
 521                 }
 522                 if(copyau(&p->from, v))
 523                         return 1;
 524                 if(copyau1(p, v))
 525                         return 1;
 526                 return 0;
 527
 528         case AJMP:      /* funny */
 529                 if(s != A) {
 530                         if(copysub(&p->to, v, s, 1))
 531                                 return 1;
 532                         return 0;
 533                 }
 534                 if(copyau(&p->to, v))
 535                         return 1;
 536                 return 0;
 537
 538         case ARET:      /* funny */
 539                 if(v->type == D_REG)
 540                 if(v->reg == REGRET)
 541                         return 2;
 542                 if(v->type == D_FREG)
 543                 if(v->reg == FREGRET)
 544                         return 2;
 545
 546         case AJAL:      /* funny */
 547                 if(v->type == D_REG) {
 548                         if(v->reg <= REGEXT && v->reg > exregoffset)
 549                                 return 2;
 550                         if(REGARG && v->reg == REGARG)
 551                                 return 2;
 552                 }
 553                 if(v->type == D_FREG)
 554                         if(v->reg <= FREGEXT && v->reg > exfregoffset)
 555                                 return 2;
 556
 557                 if(s != A) {
 558                         if(copysub(&p->to, v, s, 1))
 559                                 return 1;
 560                         return 0;
 561                 }
 562                 if(copyau(&p->to, v))
 563                         return 4;
 564                 return 3;
 565
 566         case ATEXT:     /* funny */
 567                 if(v->type == D_REG)
 568                         if(v->reg == REGARG)
 569                                 return 3;
 570                 return 0;
 571         }
 572 }
 573
 574 int
 575 a2type(Prog *p)
 576 {
 577
 578         switch(p->as) {
 579         case ABEQ:
 580         case ABNE:
 581         case ABGTZ:
 582         case ABGEZ:
 583         case ABLTZ:
 584         case ABLEZ:
 585
 586         case ASGT:
 587         case ASGTU:
 588
 589         case AADD:
 590         case AADDU:
 591         case ASUB:
 592         case ASUBU:
 593         case ASLL:
 594         case ASRL:
 595         case ASRA:
 596         case AOR:
 597         case AAND:
 598         case AXOR:
 599         case AMUL:
 600         case AMULU:
 601         case ADIV:
 602         case ADIVU:
 603                 return D_REG;
 604
 605         case ACMPEQD:
 606         case ACMPEQF:
 607         case ACMPGED:
 608         case ACMPGEF:
 609         case ACMPGTD:
 610         case ACMPGTF:
 611
 612         case AADDF:
 613         case AADDD:
 614         case ASUBF:
 615         case ASUBD:
 616         case AMULF:
 617         case AMULD:
 618         case ADIVF:
 619         case ADIVD:
 620                 return D_FREG;
 621         }
 622         return D_NONE;
 623 }
 624
 625 /*
 626  * direct reference,
 627  * could be set/use depending on
 628  * semantics
 629  */
 630 int
 631 copyas(Adr *a, Adr *v)
 632 {
 633
 634         if(regtyp(v))
 635                 if(a->type == v->type)
 636                 if(a->reg == v->reg)
 637                         return 1;
 638         return 0;
 639 }
 640
 641 /*
 642  * either direct or indirect
 643  */
 644 int
 645 copyau(Adr *a, Adr *v)
 646 {
 647
 648         if(copyas(a, v))
 649                 return 1;
 650         if(v->type == D_REG)
 651                 if(a->type == D_OREG)
 652                         if(v->reg == a->reg)
 653                                 return 1;
 654         return 0;
 655 }
 656
 657 int
 658 copyau1(Prog *p, Adr *v)
 659 {
 660
 661         if(regtyp(v))
 662                 if(p->from.type == v->type || p->to.type == v->type)
 663                 if(p->reg == v->reg) {
 664                         if(a2type(p) != v->type)
 665                                 print("botch a2type %P\n", p);
 666                         return 1;
 667                 }
 668         return 0;
 669 }
 670
 671 /*
 672  * substitute s for v in a
 673  * return failure to substitute
 674  */
 675 int
 676 copysub(Adr *a, Adr *v, Adr *s, int f)
 677 {
 678
 679         if(f)
 680         if(copyau(a, v))
 681                 a->reg = s->reg;
 682         return 0;
 683 }
 684
 685 int
 686 copysub1(Prog *p1, Adr *v, Adr *s, int f)
 687 {
 688
 689         if(f)
 690         if(copyau1(p1, v))
 691                 p1->reg = s->reg;
 692         return 0;
 693 }