sys/src/cmd/8c/peep.c

   1 #include "gc.h"
   2
   3 static int
   4 needc(Prog *p)
   5 {
   6         while(p != P) {
   7                 switch(p->as) {
   8                 case AADCL:
   9                 case ASBBL:
  10                 case ARCRL:
  11                         return 1;
  12                 case AADDL:
  13                 case ASUBL:
  14                 case AJMP:
  15                 case ARET:
  16                 case ACALL:
  17                         return 0;
  18                 default:
  19                         if(p->to.type == D_BRANCH)
  20                                 return 0;
  21                 }
  22                 p = p->link;
  23         }
  24         return 0;
  25 }
  26
  27 void
  28 peep(void)
  29 {
  30         Reg *r, *r1, *r2;
  31         Prog *p, *p1;
  32         int t;
  33
  34         /*
  35          * complete R structure
  36          */
  37         t = 0;
  38         for(r=firstr; r!=R; r=r1) {
  39                 r1 = r->link;
  40                 if(r1 == R)
  41                         break;
  42                 p = r->prog->link;
  43                 while(p != r1->prog)
  44                 switch(p->as) {
  45                 default:
  46                         r2 = rega();
  47                         r->link = r2;
  48                         r2->link = r1;
  49
  50                         r2->prog = p;
  51                         r2->p1 = r;
  52                         r->s1 = r2;
  53                         r2->s1 = r1;
  54                         r1->p1 = r2;
  55
  56                         r = r2;
  57                         t++;
  58
  59                 case ADATA:
  60                 case AGLOBL:
  61                 case ANAME:
  62                 case ASIGNAME:
  63                         p = p->link;
  64                 }
  65         }
  66
  67         pc = 0; /* speculating it won't kill */
  68
  69 loop1:
  70
  71         t = 0;
  72         for(r=firstr; r!=R; r=r->link) {
  73                 p = r->prog;
  74                 switch(p->as) {
  75                 case AMOVL:
  76                         if(regtyp(&p->to))
  77                         if(regtyp(&p->from)) {
  78                                 if(copyprop(r)) {
  79                                         excise(r);
  80                                         t++;
  81                                 }
  82                                 if(subprop(r) && copyprop(r)) {
  83                                         excise(r);
  84                                         t++;
  85                                 }
  86                         }
  87                         break;
  88
  89                 case AMOVBLSX:
  90                 case AMOVBLZX:
  91                 case AMOVWLSX:
  92                 case AMOVWLZX:
  93                         if(regtyp(&p->to)) {
  94                                 r1 = uniqs(r);
  95                                 if(r1 != R) {
  96                                         p1 = r1->prog;
  97                                         if(p->as == p1->as && p->to.type == p1->from.type)
  98                                                 p1->as = AMOVL;
  99                                 }
 100                         }
 101                         break;
 102                 case AADDL:
 103                 case AADDW:
 104                         if(p->from.type != D_CONST || needc(p->link))
 105                                 break;
 106                         if(p->from.offset == -1){
 107                                 if(p->as == AADDL)
 108                                         p->as = ADECL;
 109                                 else
 110                                         p->as = ADECW;
 111                                 p->from = zprog.from;
 112                         }
 113                         else if(p->from.offset == 1){
 114                                 if(p->as == AADDL)
 115                                         p->as = AINCL;
 116                                 else
 117                                         p->as = AINCW;
 118                                 p->from = zprog.from;
 119                         }
 120                         break;
 121                 case ASUBL:
 122                 case ASUBW:
 123                         if(p->from.type != D_CONST || needc(p->link))
 124                                 break;
 125                         if(p->from.offset == -1) {
 126                                 if(p->as == ASUBL)
 127                                         p->as = AINCL;
 128                                 else
 129                                         p->as = AINCW;
 130                                 p->from = zprog.from;
 131                         }
 132                         else if(p->from.offset == 1){
 133                                 if(p->as == ASUBL)
 134                                         p->as = ADECL;
 135                                 else
 136                                         p->as = ADECW;
 137                                 p->from = zprog.from;
 138                         }
 139                         break;
 140
 141                 case ACMPL:
 142                         if(p->to.type != D_CONST || p->to.offset != 0 || regtyp(&p->from) == 0)
 143                                 break;
 144                         if(p->link == P || (p->link->as != AJEQ && p->link->as != AJNE))
 145                                 break;
 146                         r1 = uniqp(r);
 147                         while(r1 != R && r1->prog->as == ANOP)
 148                                 r1 = uniqp(r1);
 149                         if(r1 == R || r1->prog->to.type != p->from.type)
 150                                 break;
 151                         p1 = r1->prog;
 152                         switch(p1->as){
 153                         case ASALL:
 154                         case ASARL:
 155                         case ASHLL:
 156                         case ASHRL:
 157                                 /* shift doesnt affect ZF when shift count is zero */
 158                                 if(p1->from.type != D_CONST || p1->from.offset == 0)
 159                                         break;
 160                         case AANDL:
 161                         case AORL:
 162                         case AXORL:
 163                         case ANEGL:
 164                         case AADDL:
 165                         case AADCL:
 166                         case ASUBL:
 167                         case ASBBL:
 168                         case AINCL:
 169                         case ADECL:
 170                                 excise(r);
 171                         }
 172                         break;
 173                 }
 174         }
 175         if(t)
 176                 goto loop1;
 177 }
 178
 179 void
 180 excise(Reg *r)
 181 {
 182         Prog *p;
 183
 184         p = r->prog;
 185         p->as = ANOP;
 186         p->from = zprog.from;
 187         p->to = zprog.to;
 188 }
 189
 190 Reg*
 191 uniqp(Reg *r)
 192 {
 193         Reg *r1;
 194
 195         r1 = r->p1;
 196         if(r1 == R) {
 197                 r1 = r->p2;
 198                 if(r1 == R || r1->p2link != R)
 199                         return R;
 200         } else
 201                 if(r->p2 != R)
 202                         return R;
 203         return r1;
 204 }
 205
 206 Reg*
 207 uniqs(Reg *r)
 208 {
 209         Reg *r1;
 210
 211         r1 = r->s1;
 212         if(r1 == R) {
 213                 r1 = r->s2;
 214                 if(r1 == R)
 215                         return R;
 216         } else
 217                 if(r->s2 != R)
 218                         return R;
 219         return r1;
 220 }
 221
 222 int
 223 regtyp(Adr *a)
 224 {
 225         int t;
 226
 227         t = a->type;
 228         if(t >= D_AX && t <= D_DI)
 229                 return 1;
 230         return 0;
 231 }
 232
 233 /*
 234  * the idea is to substitute
 235  * one register for another
 236  * from one MOV to another
 237  *      MOV     a, R0
 238  *      ADD     b, R0   / no use of R1
 239  *      MOV     R0, R1
 240  * would be converted to
 241  *      MOV     a, R1
 242  *      ADD     b, R1
 243  *      MOV     R1, R0
 244  * hopefully, then the former or latter MOV
 245  * will be eliminated by copy propagation.
 246  */
 247 int
 248 subprop(Reg *r0)
 249 {
 250         Prog *p;
 251         Adr *v1, *v2;
 252         Reg *r;
 253         int t;
 254
 255         p = r0->prog;
 256         v1 = &p->from;
 257         if(!regtyp(v1))
 258                 return 0;
 259         v2 = &p->to;
 260         if(!regtyp(v2))
 261                 return 0;
 262         for(r=uniqp(r0); r!=R; r=uniqp(r)) {
 263                 if(uniqs(r) == R)
 264                         break;
 265                 p = r->prog;
 266                 switch(p->as) {
 267                 case AIMULL:
 268                 case AIMULW:
 269                         if(p->to.type != D_NONE)
 270                                 break;
 271
 272                 case ADIVB:
 273                 case ADIVL:
 274                 case ADIVW:
 275                 case AIDIVB:
 276                 case AIDIVL:
 277                 case AIDIVW:
 278                 case AIMULB:
 279                 case AMULB:
 280                 case AMULL:
 281                 case AMULW:
 282
 283                 case AREP:
 284                 case AREPN:
 285                 case ALOOP:
 286                 case ALOOPNE:
 287
 288                 case ACWD:
 289                 case ACDQ:
 290
 291                 case ASTOSB:
 292                 case ASTOSL:
 293                 case AMOVSB:
 294                 case AMOVSL:
 295                 case AFSTSW:
 296
 297                 case ACALL:
 298                         return 0;
 299
 300                 case AROLB:
 301                 case AROLL:
 302                 case AROLW:
 303                 case ARORB:
 304                 case ARORL:
 305                 case ARORW:
 306                 case ASALB:
 307                 case ASALL:
 308                 case ASALW:
 309                 case ASARB:
 310                 case ASARL:
 311                 case ASARW:
 312                 case ASHLB:
 313                 case ASHLL:
 314                 case ASHLW:
 315                 case ASHRB:
 316                 case ASHRL:
 317                 case ASHRW:
 318                         if(p->from.type == D_CX && v1->type == D_CX)
 319                                 return 0;
 320                         break;
 321
 322                 case AORL:
 323                 case AANDL:
 324                 case AXORL:
 325                 case AADDL:
 326                 case AADCL:
 327                         /*
 328                          * can swap when:
 329                          *  ADD R2, R1
 330                          *  MOV R1, R2
 331                          * convert to:
 332                          *  ADD R1, R2
 333                          *  MOV R2, R1  / no use for R1
 334                          */
 335                         if(p->to.type == v1->type && p->from.type == v2->type){
 336                                 copysub(&p->from, v2, v1, 1);
 337                                 goto gotit;
 338                         }
 339                         break;
 340
 341                 case AMOVL:
 342                         if(p->to.type == v1->type)
 343                                 goto gotit;
 344                         break;
 345                 }
 346                 if(copyau(&p->from, v2) ||
 347                    copyau(&p->to, v2))
 348                         break;
 349                 if(copysub(&p->from, v1, v2, 0) ||
 350                    copysub(&p->to, v1, v2, 0))
 351                         break;
 352         }
 353         return 0;
 354
 355 gotit:
 356         copysub(&p->to, v1, v2, 1);
 357         if(debug['P']) {
 358                 print("gotit: %D->%D\n%P", v1, v2, r->prog);
 359                 if(p->from.type == v2->type)
 360                         print(" excise");
 361                 print("\n");
 362         }
 363         for(r=uniqs(r); r!=r0; r=uniqs(r)) {
 364                 p = r->prog;
 365                 copysub(&p->from, v1, v2, 1);
 366                 copysub(&p->to, v1, v2, 1);
 367                 if(debug['P'])
 368                         print("%P\n", r->prog);
 369         }
 370         t = v1->type;
 371         v1->type = v2->type;
 372         v2->type = t;
 373         if(debug['P'])
 374                 print("%P last\n", r->prog);
 375         return 1;
 376 }
 377
 378 /*
 379  * The idea is to remove redundant copies.
 380  *      v1->v2  F=0
 381  *      (use v2 s/v2/v1/)*
 382  *      set v1  F=1
 383  *      use v2  return fail
 384  *      -----------------
 385  *      v1->v2  F=0
 386  *      (use v2 s/v2/v1/)*
 387  *      set v1  F=1
 388  *      set v2  return success
 389  */
 390 int
 391 copyprop(Reg *r0)
 392 {
 393         Prog *p;
 394         Adr *v1, *v2;
 395         Reg *r;
 396
 397         p = r0->prog;
 398         v1 = &p->from;
 399         v2 = &p->to;
 400         if(copyas(v1, v2))
 401                 return 1;
 402         for(r=firstr; r!=R; r=r->link)
 403                 r->active = 0;
 404         return copy1(v1, v2, r0->s1, 0);
 405 }
 406
 407 int
 408 copy1(Adr *v1, Adr *v2, Reg *r, int f)
 409 {
 410         int t;
 411         Prog *p;
 412
 413         if(r->active) {
 414                 if(debug['P'])
 415                         print("act set; return 1\n");
 416                 return 1;
 417         }
 418         r->active = 1;
 419         if(debug['P'])
 420                 print("copy %D->%D f=%d\n", v1, v2, f);
 421         for(; r != R; r = r->s1) {
 422                 p = r->prog;
 423                 if(debug['P'])
 424                         print("%P", p);
 425                 if(!f && uniqp(r) == R) {
 426                         f = 1;
 427                         if(debug['P'])
 428                                 print("; merge; f=%d", f);
 429                 }
 430                 t = copyu(p, v2, A);
 431                 switch(t) {
 432                 case 2: /* rar, cant split */
 433                         if(debug['P'])
 434                                 print("; %D rar; return 0\n", v2);
 435                         return 0;
 436
 437                 case 3: /* set */
 438                         if(debug['P'])
 439                                 print("; %D set; return 1\n", v2);
 440                         return 1;
 441
 442                 case 1: /* used, substitute */
 443                 case 4: /* use and set */
 444                         if(f) {
 445                                 if(!debug['P'])
 446                                         return 0;
 447                                 if(t == 4)
 448                                         print("; %D used+set and f=%d; return 0\n", v2, f);
 449                                 else
 450                                         print("; %D used and f=%d; return 0\n", v2, f);
 451                                 return 0;
 452                         }
 453                         if(copyu(p, v2, v1)) {
 454                                 if(debug['P'])
 455                                         print("; sub fail; return 0\n");
 456                                 return 0;
 457                         }
 458                         if(debug['P'])
 459                                 print("; sub %D/%D", v2, v1);
 460                         if(t == 4) {
 461                                 if(debug['P'])
 462                                         print("; %D used+set; return 1\n", v2);
 463                                 return 1;
 464                         }
 465                         break;
 466                 }
 467                 if(!f) {
 468                         t = copyu(p, v1, A);
 469                         if(!f && (t == 2 || t == 3 || t == 4)) {
 470                                 f = 1;
 471                                 if(debug['P'])
 472                                         print("; %D set and !f; f=%d", v1, f);
 473                         }
 474                 }
 475                 if(debug['P'])
 476                         print("\n");
 477                 if(r->s2)
 478                         if(!copy1(v1, v2, r->s2, f))
 479                                 return 0;
 480         }
 481         return 1;
 482 }
 483
 484 /*
 485  * return
 486  * 1 if v only used (and substitute),
 487  * 2 if read-alter-rewrite
 488  * 3 if set
 489  * 4 if set and used
 490  * 0 otherwise (not touched)
 491  */
 492 int
 493 copyu(Prog *p, Adr *v, Adr *s)
 494 {
 495
 496         switch(p->as) {
 497
 498         default:
 499                 if(debug['P'])
 500                         print("unknown op %A\n", p->as);
 501                 return 2;
 502
 503         case ANEGB:
 504         case ANEGW:
 505         case ANEGL:
 506         case ANOTB:
 507         case ANOTW:
 508         case ANOTL:
 509                 if(copyas(&p->to, v))
 510                         return 2;
 511                 break;
 512
 513         case ALEAL:     /* lhs addr, rhs store */
 514                 if(copyas(&p->from, v))
 515                         return 2;
 516
 517
 518         case ANOP:      /* rhs store */
 519         case AMOVL:
 520         case AMOVBLSX:
 521         case AMOVBLZX:
 522         case AMOVWLSX:
 523         case AMOVWLZX:
 524                 if(copyas(&p->to, v)) {
 525                         if(s != A)
 526                                 return copysub(&p->from, v, s, 1);
 527                         if(copyau(&p->from, v))
 528                                 return 4;
 529                         return 3;
 530                 }
 531                 goto caseread;
 532
 533         case AROLB:
 534         case AROLL:
 535         case AROLW:
 536         case ARORB:
 537         case ARORL:
 538         case ARORW:
 539         case ASALB:
 540         case ASALL:
 541         case ASALW:
 542         case ASARB:
 543         case ASARL:
 544         case ASARW:
 545         case ASHLB:
 546         case ASHLL:
 547         case ASHLW:
 548         case ASHRB:
 549         case ASHRL:
 550         case ASHRW:
 551                 if(copyas(&p->to, v))
 552                         return 2;
 553                 if(copyas(&p->from, v))
 554                         if(p->from.type == D_CX)
 555                                 return 2;
 556                 goto caseread;
 557
 558         case AADDB:     /* rhs rar */
 559         case AADDL:
 560         case AADDW:
 561         case AANDB:
 562         case AANDL:
 563         case AANDW:
 564         case ADECL:
 565         case ADECW:
 566         case AINCL:
 567         case AINCW:
 568         case ASUBB:
 569         case ASUBL:
 570         case ASUBW:
 571         case AORB:
 572         case AORL:
 573         case AORW:
 574         case AXORB:
 575         case AXORL:
 576         case AXORW:
 577         case AMOVB:
 578         case AMOVW:
 579
 580         case AFMOVB:
 581         case AFMOVBP:
 582         case AFMOVD:
 583         case AFMOVDP:
 584         case AFMOVF:
 585         case AFMOVFP:
 586         case AFMOVL:
 587         case AFMOVLP:
 588         case AFMOVV:
 589         case AFMOVVP:
 590         case AFMOVW:
 591         case AFMOVWP:
 592         case AFMOVX:
 593         case AFMOVXP:
 594         case AFADDDP:
 595         case AFADDW:
 596         case AFADDL:
 597         case AFADDF:
 598         case AFADDD:
 599         case AFMULDP:
 600         case AFMULW:
 601         case AFMULL:
 602         case AFMULF:
 603         case AFMULD:
 604         case AFSUBDP:
 605         case AFSUBW:
 606         case AFSUBL:
 607         case AFSUBF:
 608         case AFSUBD:
 609         case AFSUBRDP:
 610         case AFSUBRW:
 611         case AFSUBRL:
 612         case AFSUBRF:
 613         case AFSUBRD:
 614         case AFDIVDP:
 615         case AFDIVW:
 616         case AFDIVL:
 617         case AFDIVF:
 618         case AFDIVD:
 619         case AFDIVRDP:
 620         case AFDIVRW:
 621         case AFDIVRL:
 622         case AFDIVRF:
 623         case AFDIVRD:
 624                 if(copyas(&p->to, v))
 625                         return 2;
 626                 goto caseread;
 627
 628         case ACMPL:     /* read only */
 629         case ACMPW:
 630         case ACMPB:
 631
 632         case AFCOMB:
 633         case AFCOMBP:
 634         case AFCOMD:
 635         case AFCOMDP:
 636         case AFCOMDPP:
 637         case AFCOMF:
 638         case AFCOMFP:
 639         case AFCOML:
 640         case AFCOMLP:
 641         case AFCOMW:
 642         case AFCOMWP:
 643         case AFUCOM:
 644         case AFUCOMP:
 645         case AFUCOMPP:
 646         caseread:
 647                 if(s != A) {
 648                         if(copysub(&p->from, v, s, 1))
 649                                 return 1;
 650                         return copysub(&p->to, v, s, 1);
 651                 }
 652                 if(copyau(&p->from, v))
 653                         return 1;
 654                 if(copyau(&p->to, v))
 655                         return 1;
 656                 break;
 657
 658         case AJGE:      /* no reference */
 659         case AJNE:
 660         case AJLE:
 661         case AJEQ:
 662         case AJHI:
 663         case AJLS:
 664         case AJMI:
 665         case AJPL:
 666         case AJGT:
 667         case AJLT:
 668         case AJCC:
 669         case AJCS:
 670
 671         case AADJSP:
 672         case AFLDZ:
 673         case AWAIT:
 674                 break;
 675
 676         case AIMULL:
 677         case AIMULW:
 678                 if(p->to.type != D_NONE) {
 679                         if(copyas(&p->to, v))
 680                                 return 2;
 681                         goto caseread;
 682                 }
 683
 684         case ADIVB:
 685         case ADIVL:
 686         case ADIVW:
 687         case AIDIVB:
 688         case AIDIVL:
 689         case AIDIVW:
 690         case AIMULB:
 691         case AMULB:
 692         case AMULL:
 693         case AMULW:
 694
 695         case ACWD:
 696         case ACDQ:
 697                 if(v->type == D_AX || v->type == D_DX)
 698                         return 2;
 699                 goto caseread;
 700
 701         case AREP:
 702         case AREPN:
 703                 if(v->type == D_CX)
 704                         return 2;
 705                 goto caseread;
 706
 707         case AMOVSB:
 708         case AMOVSL:
 709                 if(v->type == D_DI || v->type == D_SI)
 710                         return 2;
 711                 goto caseread;
 712
 713         case ASTOSB:
 714         case ASTOSL:
 715                 if(v->type == D_AX || v->type == D_DI)
 716                         return 2;
 717                 goto caseread;
 718
 719         case AFSTSW:
 720                 if(v->type == D_AX)
 721                         return 2;
 722                 goto caseread;
 723
 724         case AJMP:      /* funny */
 725                 if(s != A) {
 726                         if(copysub(&p->to, v, s, 1))
 727                                 return 1;
 728                         return 0;
 729                 }
 730                 if(copyau(&p->to, v))
 731                         return 1;
 732                 return 0;
 733
 734         case ARET:      /* funny */
 735                 if(v->type == REGRET)
 736                         return 2;
 737                 if(s != A)
 738                         return 1;
 739                 return 3;
 740
 741         case ACALL:     /* funny */
 742                 if(REGARG>=0 && v->type == REGARG)
 743                         return 2;
 744
 745                 if(s != A) {
 746                         if(copysub(&p->to, v, s, 1))
 747                                 return 1;
 748                         return 0;
 749                 }
 750                 if(copyau(&p->to, v))
 751                         return 4;
 752                 return 3;
 753         }
 754         return 0;
 755 }
 756
 757 /*
 758  * direct reference,
 759  * could be set/use depending on
 760  * semantics
 761  */
 762 int
 763 copyas(Adr *a, Adr *v)
 764 {
 765         if(a->type != v->type)
 766                 return 0;
 767         if(regtyp(v))
 768                 return 1;
 769         if(v->type == D_AUTO || v->type == D_PARAM)
 770                 if(v->offset == a->offset)
 771                         return 1;
 772         return 0;
 773 }
 774
 775 /*
 776  * either direct or indirect
 777  */
 778 int
 779 copyau(Adr *a, Adr *v)
 780 {
 781
 782         if(copyas(a, v))
 783                 return 1;
 784         if(regtyp(v)) {
 785                 if(a->type-D_INDIR == v->type)
 786                         return 1;
 787                 if(a->index == v->type)
 788                         return 1;
 789         }
 790         return 0;
 791 }
 792
 793 /*
 794  * substitute s for v in a
 795  * return failure to substitute
 796  */
 797 int
 798 copysub(Adr *a, Adr *v, Adr *s, int f)
 799 {
 800         int t;
 801
 802         if(copyas(a, v)) {
 803                 t = s->type;
 804                 if(t >= D_AX && t <= D_DI) {
 805                         if(f)
 806                                 a->type = t;
 807                 }
 808                 return 0;
 809         }
 810         if(regtyp(v)) {
 811                 t = v->type;
 812                 if(a->type == t+D_INDIR) {
 813                         if(s->type == D_BP && a->index != D_NONE)
 814                                 return 1;       /* can't use BP-base with index */
 815                         if(f)
 816                                 a->type = s->type+D_INDIR;
 817 //                      return 0;
 818                 }
 819                 if(a->index == t) {
 820                         if(f)
 821                                 a->index = s->type;
 822                         return 0;
 823                 }
 824                 return 0;
 825         }
 826         return 0;
 827 }