sys/src/cmd/kc/peep.c

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