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