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