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