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