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 } 772