1 #include "gc.h" 2 3 int xtramodes(Reg*, Adr*); 4 5 void 6 peep(void) 7 { 8 Reg *r, *r1, *r2; 9 Prog *p, *p1; 10 int t; 11 /* 12 * complete R structure 13 */ 14 t = 0; 15 for(r=firstr; r!=R; r=r1) { 16 r1 = r->link; 17 if(r1 == R) 18 break; 19 p = r->prog->link; 20 while(p != r1->prog) 21 switch(p->as) { 22 default: 23 r2 = rega(); 24 r->link = r2; 25 r2->link = r1; 26 27 r2->prog = p; 28 r2->p1 = r; 29 r->s1 = r2; 30 r2->s1 = r1; 31 r1->p1 = r2; 32 33 r = r2; 34 t++; 35 36 case ADATA: 37 case AGLOBL: 38 case ANAME: 39 case ASIGNAME: 40 p = p->link; 41 } 42 } 43 44 loop1: 45 t = 0; 46 for(r=firstr; r!=R; r=r->link) { 47 p = r->prog; 48 if(p->as == ASLL || p->as == ASRL || p->as == ASRA) { 49 /* 50 * elide shift into D_SHIFT operand of subsequent instruction 51 */ 52 if(shiftprop(r)) { 53 excise(r); 54 t++; 55 } 56 } 57 if(p->as == AMOVW || p->as == AMOVF || p->as == AMOVD) 58 if(regtyp(&p->to)) { 59 if(p->from.type == D_CONST) 60 constprop(&p->from, &p->to, r->s1); 61 else if(regtyp(&p->from)) 62 if(p->from.type == p->to.type) { 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 AEOR: 85 /* 86 * EOR -1,x,y => MVN x,y 87 */ 88 if(p->from.type == D_CONST && p->from.offset == -1) { 89 p->as = AMVN; 90 p->from.type = D_REG; 91 if(p->reg != NREG) 92 p->from.reg = p->reg; 93 else 94 p->from.reg = p->to.reg; 95 p->reg = NREG; 96 } 97 continue; 98 case AMOVH: 99 case AMOVHU: 100 case AMOVB: 101 case AMOVBU: 102 if(p->to.type != D_REG) 103 continue; 104 break; 105 } 106 r1 = r->link; 107 if(r1 == R) 108 continue; 109 p1 = r1->prog; 110 if(p1->as != p->as) 111 continue; 112 if(p1->from.type != D_REG || p1->from.reg != p->to.reg) 113 continue; 114 if(p1->to.type != D_REG || p1->to.reg != p->to.reg) 115 continue; 116 excise(r1); 117 } 118 119 for(r=firstr; r!=R; r=r->link) { 120 p = r->prog; 121 switch(p->as) { 122 case AMOVW: 123 case AMOVB: 124 case AMOVBU: 125 if(p->from.type == D_OREG && p->from.offset == 0) 126 xtramodes(r, &p->from); 127 else if(p->to.type == D_OREG && p->to.offset == 0) 128 xtramodes(r, &p->to); 129 else 130 continue; 131 break; 132 case ACMP: 133 /* 134 * elide CMP $0,x if calculation of x can set condition codes 135 */ 136 if(p->from.type != D_CONST || p->from.offset != 0) 137 continue; 138 r2 = r->s1; 139 if(r2 == R) 140 continue; 141 t = r2->prog->as; 142 switch(t) { 143 default: 144 continue; 145 case ABEQ: 146 case ABNE: 147 case ABMI: 148 case ABPL: 149 break; 150 case ABGE: 151 t = ABPL; 152 break; 153 case ABLT: 154 t = ABMI; 155 break; 156 case ABHI: 157 t = ABNE; 158 break; 159 case ABLS: 160 t = ABEQ; 161 break; 162 } 163 r1 = r; 164 do 165 r1 = uniqp(r1); 166 while (r1 != R && r1->prog->as == ANOP); 167 if(r1 == R) 168 continue; 169 p1 = r1->prog; 170 if(p1->to.type != D_REG) 171 continue; 172 if(p1->to.reg != p->reg) 173 if(!(p1->as == AMOVW && p1->from.type == D_REG && p1->from.reg == p->reg)) 174 continue; 175 switch(p1->as) { 176 default: 177 continue; 178 case AMOVW: 179 if(p1->from.type != D_REG) 180 continue; 181 case AAND: 182 case AEOR: 183 case AORR: 184 case ABIC: 185 case AMVN: 186 case ASUB: 187 case ARSB: 188 case AADD: 189 case AADC: 190 case ASBC: 191 case ARSC: 192 break; 193 } 194 p1->scond |= C_SBIT; 195 r2->prog->as = t; 196 excise(r); 197 continue; 198 } 199 } 200 201 predicate(); 202 } 203 204 void 205 excise(Reg *r) 206 { 207 Prog *p; 208 209 p = r->prog; 210 p->as = ANOP; 211 p->scond = zprog.scond; 212 p->from = zprog.from; 213 p->to = zprog.to; 214 p->reg = zprog.reg; /**/ 215 } 216 217 Reg* 218 uniqp(Reg *r) 219 { 220 Reg *r1; 221 222 r1 = r->p1; 223 if(r1 == R) { 224 r1 = r->p2; 225 if(r1 == R || r1->p2link != R) 226 return R; 227 } else 228 if(r->p2 != R) 229 return R; 230 return r1; 231 } 232 233 Reg* 234 uniqs(Reg *r) 235 { 236 Reg *r1; 237 238 r1 = r->s1; 239 if(r1 == R) { 240 r1 = r->s2; 241 if(r1 == R) 242 return R; 243 } else 244 if(r->s2 != R) 245 return R; 246 return r1; 247 } 248 249 int 250 regtyp(Adr *a) 251 { 252 253 if(a->type == D_REG) 254 return 1; 255 if(a->type == D_FREG) 256 return 1; 257 return 0; 258 } 259 260 /* 261 * the idea is to substitute 262 * one register for another 263 * from one MOV to another 264 * MOV a, R0 265 * ADD b, R0 / no use of R1 266 * MOV R0, R1 267 * would be converted to 268 * MOV a, R1 269 * ADD b, R1 270 * MOV R1, R0 271 * hopefully, then the former or latter MOV 272 * will be eliminated by copy propagation. 273 */ 274 int 275 subprop(Reg *r0) 276 { 277 Prog *p; 278 Adr *v1, *v2; 279 Reg *r; 280 int t; 281 282 p = r0->prog; 283 v1 = &p->from; 284 if(!regtyp(v1)) 285 return 0; 286 v2 = &p->to; 287 if(!regtyp(v2)) 288 return 0; 289 for(r=uniqp(r0); r!=R; r=uniqp(r)) { 290 if(uniqs(r) == R) 291 break; 292 p = r->prog; 293 switch(p->as) { 294 case ABL: 295 return 0; 296 297 case ACMP: 298 case ACMN: 299 case AADD: 300 case ASUB: 301 case ARSB: 302 case ASLL: 303 case ASRL: 304 case ASRA: 305 case AORR: 306 case AAND: 307 case AEOR: 308 case AMUL: 309 case ADIV: 310 case ADIVU: 311 312 case ACMPF: 313 case ACMPD: 314 case AADDD: 315 case AADDF: 316 case ASUBD: 317 case ASUBF: 318 case AMULD: 319 case AMULF: 320 case ADIVD: 321 case ADIVF: 322 if(p->to.type == v1->type) 323 if(p->to.reg == v1->reg) { 324 if(p->reg == NREG) 325 p->reg = p->to.reg; 326 goto gotit; 327 } 328 break; 329 330 case AMOVF: 331 case AMOVD: 332 case AMOVW: 333 if(p->to.type == v1->type) 334 if(p->to.reg == v1->reg) 335 goto gotit; 336 break; 337 338 case AMOVM: 339 t = 1<<v2->reg; 340 if((p->from.type == D_CONST && (p->from.offset&t)) || 341 (p->to.type == D_CONST && (p->to.offset&t))) 342 return 0; 343 break; 344 } 345 if(copyau(&p->from, v2) || 346 copyau1(p, v2) || 347 copyau(&p->to, v2)) 348 break; 349 if(copysub(&p->from, v1, v2, 0) || 350 copysub1(p, v1, v2, 0) || 351 copysub(&p->to, v1, v2, 0)) 352 break; 353 } 354 return 0; 355 356 gotit: 357 copysub(&p->to, v1, v2, 1); 358 if(debug['P']) { 359 print("gotit: %D->%D\n%P", v1, v2, r->prog); 360 if(p->from.type == v2->type) 361 print(" excise"); 362 print("\n"); 363 } 364 for(r=uniqs(r); r!=r0; r=uniqs(r)) { 365 p = r->prog; 366 copysub(&p->from, v1, v2, 1); 367 copysub1(p, v1, v2, 1); 368 copysub(&p->to, v1, v2, 1); 369 if(debug['P']) 370 print("%P\n", r->prog); 371 } 372 t = v1->reg; 373 v1->reg = v2->reg; 374 v2->reg = t; 375 if(debug['P']) 376 print("%P last\n", r->prog); 377 return 1; 378 } 379 380 /* 381 * The idea is to remove redundant copies. 382 * v1->v2 F=0 383 * (use v2 s/v2/v1/)* 384 * set v1 F=1 385 * use v2 return fail 386 * ----------------- 387 * v1->v2 F=0 388 * (use v2 s/v2/v1/)* 389 * set v1 F=1 390 * set v2 return success 391 */ 392 int 393 copyprop(Reg *r0) 394 { 395 Prog *p; 396 Adr *v1, *v2; 397 Reg *r; 398 399 p = r0->prog; 400 v1 = &p->from; 401 v2 = &p->to; 402 if(copyas(v1, v2)) 403 return 1; 404 for(r=firstr; r!=R; r=r->link) 405 r->active = 0; 406 return copy1(v1, v2, r0->s1, 0); 407 } 408 409 int 410 copy1(Adr *v1, Adr *v2, Reg *r, int f) 411 { 412 int t; 413 Prog *p; 414 415 if(r->active) { 416 if(debug['P']) 417 print("act set; return 1\n"); 418 return 1; 419 } 420 r->active = 1; 421 if(debug['P']) 422 print("copy %D->%D f=%d\n", v1, v2, f); 423 for(; r != R; r = r->s1) { 424 p = r->prog; 425 if(debug['P']) 426 print("%P", p); 427 if(!f && uniqp(r) == R) { 428 f = 1; 429 if(debug['P']) 430 print("; merge; f=%d", f); 431 } 432 t = copyu(p, v2, A); 433 switch(t) { 434 case 2: /* rar, cant split */ 435 if(debug['P']) 436 print("; %Drar; return 0\n", v2); 437 return 0; 438 439 case 3: /* set */ 440 if(debug['P']) 441 print("; %Dset; return 1\n", v2); 442 return 1; 443 444 case 1: /* used, substitute */ 445 case 4: /* use and set */ 446 if(f) { 447 if(!debug['P']) 448 return 0; 449 if(t == 4) 450 print("; %Dused+set and f=%d; return 0\n", v2, f); 451 else 452 print("; %Dused and f=%d; return 0\n", v2, f); 453 return 0; 454 } 455 if(copyu(p, v2, v1)) { 456 if(debug['P']) 457 print("; sub fail; return 0\n"); 458 return 0; 459 } 460 if(debug['P']) 461 print("; sub%D/%D", v2, v1); 462 if(t == 4) { 463 if(debug['P']) 464 print("; %Dused+set; return 1\n", v2); 465 return 1; 466 } 467 break; 468 } 469 if(!f) { 470 t = copyu(p, v1, A); 471 if(!f && (t == 2 || t == 3 || t == 4)) { 472 f = 1; 473 if(debug['P']) 474 print("; %Dset and !f; f=%d", v1, f); 475 } 476 } 477 if(debug['P']) 478 print("\n"); 479 if(r->s2) 480 if(!copy1(v1, v2, r->s2, f)) 481 return 0; 482 } 483 return 1; 484 } 485 486 /* 487 * The idea is to remove redundant constants. 488 * $c1->v1 489 * ($c1->v2 s/$c1/v1)* 490 * set v1 return 491 * The v1->v2 should be eliminated by copy propagation. 492 */ 493 void 494 constprop(Adr *c1, Adr *v1, Reg *r) 495 { 496 Prog *p; 497 498 if(debug['C']) 499 print("constprop %D->%D\n", c1, v1); 500 for(; r != R; r = r->s1) { 501 p = r->prog; 502 if(debug['C']) 503 print("%P", p); 504 if(uniqp(r) == R) { 505 if(debug['C']) 506 print("; merge; return\n"); 507 return; 508 } 509 if(p->as == AMOVW && copyas(&p->from, c1)) { 510 if(debug['C']) 511 print("; sub%D/%D", &p->from, v1); 512 p->from = *v1; 513 } else if(copyu(p, v1, A) > 1) { 514 if(debug['C']) 515 print("; %Dset; return\n", v1); 516 return; 517 } 518 if(debug['C']) 519 print("\n"); 520 if(r->s2) 521 constprop(c1, v1, r->s2); 522 } 523 } 524 525 /* 526 * ASLL x,y,w 527 * .. (not use w, not set x y w) 528 * AXXX w,a,b (a != w) 529 * .. (not use w) 530 * (set w) 531 * ----------- changed to 532 * .. 533 * AXXX (x<<y),a,b 534 * .. 535 */ 536 #define FAIL(msg) { if(debug['H']) print("\t%s; FAILURE\n", msg); return 0; } 537 int 538 shiftprop(Reg *r) 539 { 540 Reg *r1; 541 Prog *p, *p1, *p2; 542 int n, o; 543 Adr a; 544 545 p = r->prog; 546 if(p->to.type != D_REG) 547 FAIL("BOTCH: result not reg"); 548 n = p->to.reg; 549 a = zprog.from; 550 if(p->reg != NREG && p->reg != p->to.reg) { 551 a.type = D_REG; 552 a.reg = p->reg; 553 } 554 if(debug['H']) 555 print("shiftprop\n%P", p); 556 r1 = r; 557 for(;;) { 558 /* find first use of shift result; abort if shift operands or result are changed */ 559 r1 = uniqs(r1); 560 if(r1 == R) 561 FAIL("branch"); 562 if(uniqp(r1) == R) 563 FAIL("merge"); 564 p1 = r1->prog; 565 if(debug['H']) 566 print("\n%P", p1); 567 switch(copyu(p1, &p->to, A)) { 568 case 0: /* not used or set */ 569 if((p->from.type == D_REG && copyu(p1, &p->from, A) > 1) || 570 (a.type == D_REG && copyu(p1, &a, A) > 1)) 571 FAIL("args modified"); 572 continue; 573 case 3: /* set, not used */ 574 FAIL("BOTCH: noref"); 575 } 576 break; 577 } 578 /* check whether substitution can be done */ 579 switch(p1->as) { 580 default: 581 FAIL("non-dpi"); 582 case AAND: 583 case AEOR: 584 case AADD: 585 case AADC: 586 case AORR: 587 case ASUB: 588 case ARSB: 589 case ASBC: 590 case ARSC: 591 if(p1->reg == n || (p1->reg == NREG && p1->to.type == D_REG && p1->to.reg == n)) { 592 if(p1->from.type != D_REG) 593 FAIL("can't swap"); 594 p1->reg = p1->from.reg; 595 p1->from.reg = n; 596 switch(p1->as) { 597 case ASUB: 598 p1->as = ARSB; 599 break; 600 case ARSB: 601 p1->as = ASUB; 602 break; 603 case ASBC: 604 p1->as = ARSC; 605 break; 606 case ARSC: 607 p1->as = ASBC; 608 break; 609 } 610 if(debug['H']) 611 print("\t=>%P", p1); 612 } 613 case ABIC: 614 case ACMP: 615 case ACMN: 616 if(p1->reg == n) 617 FAIL("can't swap"); 618 if(p1->reg == NREG && p1->to.reg == n) 619 FAIL("shift result used twice"); 620 case AMVN: 621 if(p1->from.type == D_SHIFT) 622 FAIL("shift result used in shift"); 623 if(p1->from.type != D_REG || p1->from.reg != n) 624 FAIL("BOTCH: where is it used?"); 625 break; 626 } 627 /* check whether shift result is used subsequently */ 628 p2 = p1; 629 if(p1->to.reg != n) 630 for (;;) { 631 r1 = uniqs(r1); 632 if(r1 == R) 633 FAIL("inconclusive"); 634 p1 = r1->prog; 635 if(debug['H']) 636 print("\n%P", p1); 637 switch(copyu(p1, &p->to, A)) { 638 case 0: /* not used or set */ 639 continue; 640 case 3: /* set, not used */ 641 break; 642 default:/* used */ 643 FAIL("reused"); 644 } 645 break; 646 } 647 /* make the substitution */ 648 p2->from.type = D_SHIFT; 649 p2->from.reg = NREG; 650 o = p->reg; 651 if(o == NREG) 652 o = p->to.reg; 653 switch(p->from.type){ 654 case D_CONST: 655 o |= (p->from.offset&0x1f)<<7; 656 break; 657 case D_REG: 658 o |= (1<<4) | (p->from.reg<<8); 659 break; 660 } 661 switch(p->as){ 662 case ASLL: 663 o |= 0<<5; 664 break; 665 case ASRL: 666 o |= 1<<5; 667 break; 668 case ASRA: 669 o |= 2<<5; 670 break; 671 } 672 p2->from.offset = o; 673 if(debug['H']) 674 print("\t=>%P\tSUCCEED\n", p2); 675 return 1; 676 } 677 678 Reg* 679 findpre(Reg *r, Adr *v) 680 { 681 Reg *r1; 682 683 for(r1=uniqp(r); r1!=R; r=r1,r1=uniqp(r)) { 684 if(uniqs(r1) != r) 685 return R; 686 switch(copyu(r1->prog, v, A)) { 687 case 1: /* used */ 688 case 2: /* read-alter-rewrite */ 689 return R; 690 case 3: /* set */ 691 case 4: /* set and used */ 692 return r1; 693 } 694 } 695 return R; 696 } 697 698 Reg* 699 findinc(Reg *r, Reg *r2, Adr *v) 700 { 701 Reg *r1; 702 Prog *p; 703 704 705 for(r1=uniqs(r); r1!=R && r1!=r2; r=r1,r1=uniqs(r)) { 706 if(uniqp(r1) != r) 707 return R; 708 switch(copyu(r1->prog, v, A)) { 709 case 0: /* not touched */ 710 continue; 711 case 4: /* set and used */ 712 p = r1->prog; 713 if(p->as == AADD) 714 if(p->from.type == D_CONST) 715 if(p->from.offset > -4096 && p->from.offset < 4096) 716 return r1; 717 default: 718 return R; 719 } 720 } 721 return R; 722 } 723 724 int 725 nochange(Reg *r, Reg *r2, Prog *p) 726 { 727 Adr a[3]; 728 int i, n; 729 730 if(r == r2) 731 return 1; 732 n = 0; 733 if(p->reg != NREG && p->reg != p->to.reg) { 734 a[n].type = D_REG; 735 a[n++].reg = p->reg; 736 } 737 switch(p->from.type) { 738 case D_SHIFT: 739 a[n].type = D_REG; 740 a[n++].reg = p->from.offset&0xf; 741 case D_REG: 742 a[n].type = D_REG; 743 a[n++].reg = p->from.reg; 744 } 745 if(n == 0) 746 return 1; 747 for(; r!=R && r!=r2; r=uniqs(r)) { 748 p = r->prog; 749 for(i=0; i<n; i++) 750 if(copyu(p, &a[i], A) > 1) 751 return 0; 752 } 753 return 1; 754 } 755 756 int 757 findu1(Reg *r, Adr *v) 758 { 759 for(; r != R; r = r->s1) { 760 if(r->active) 761 return 0; 762 r->active = 1; 763 switch(copyu(r->prog, v, A)) { 764 case 1: /* used */ 765 case 2: /* read-alter-rewrite */ 766 case 4: /* set and used */ 767 return 1; 768 case 3: /* set */ 769 return 0; 770 } 771 if(r->s2) 772 if (findu1(r->s2, v)) 773 return 1; 774 } 775 return 0; 776 } 777 778 int 779 finduse(Reg *r, Adr *v) 780 { 781 Reg *r1; 782 783 for(r1=firstr; r1!=R; r1=r1->link) 784 r1->active = 0; 785 return findu1(r, v); 786 } 787 788 int 789 xtramodes(Reg *r, Adr *a) 790 { 791 Reg *r1, *r2, *r3; 792 Prog *p, *p1; 793 Adr v; 794 795 p = r->prog; 796 if(debug['h'] && p->as == AMOVB && p->from.type == D_OREG) /* byte load */ 797 return 0; 798 v = *a; 799 v.type = D_REG; 800 r1 = findpre(r, &v); 801 if(r1 != R) { 802 p1 = r1->prog; 803 if(p1->to.type == D_REG && p1->to.reg == v.reg) 804 switch(p1->as) { 805 case AADD: 806 if(p1->from.type == D_REG || 807 (p1->from.type == D_SHIFT && (p1->from.offset&(1<<4)) == 0 && 808 (p->as != AMOVB || (a == &p->from && (p1->from.offset&~0xf) == 0))) || 809 (p1->from.type == D_CONST && 810 p1->from.offset > -4096 && p1->from.offset < 4096)) 811 if(nochange(uniqs(r1), r, p1)) { 812 if(a != &p->from || v.reg != p->to.reg) 813 if (finduse(r->s1, &v)) { 814 if(p1->reg == NREG || p1->reg == v.reg) 815 /* pre-indexing */ 816 p->scond |= C_WBIT; 817 else return 0; 818 } 819 switch (p1->from.type) { 820 case D_REG: 821 /* register offset */ 822 a->type = D_SHIFT; 823 a->offset = p1->from.reg; 824 break; 825 case D_SHIFT: 826 /* scaled register offset */ 827 a->type = D_SHIFT; 828 case D_CONST: 829 /* immediate offset */ 830 a->offset = p1->from.offset; 831 break; 832 } 833 if(p1->reg != NREG) 834 a->reg = p1->reg; 835 excise(r1); 836 return 1; 837 } 838 break; 839 case AMOVW: 840 if(p1->from.type == D_REG) 841 if((r2 = findinc(r1, r, &p1->from)) != R) { 842 for(r3=uniqs(r2); r3->prog->as==ANOP; r3=uniqs(r3)) 843 ; 844 if(r3 == r) { 845 /* post-indexing */ 846 p1 = r2->prog; 847 a->reg = p1->to.reg; 848 a->offset = p1->from.offset; 849 p->scond |= C_PBIT; 850 if(!finduse(r, &r1->prog->to)) 851 excise(r1); 852 excise(r2); 853 return 1; 854 } 855 } 856 break; 857 } 858 } 859 if(a != &p->from || a->reg != p->to.reg) 860 if((r1 = findinc(r, R, &v)) != R) { 861 /* post-indexing */ 862 p1 = r1->prog; 863 a->offset = p1->from.offset; 864 p->scond |= C_PBIT; 865 excise(r1); 866 return 1; 867 } 868 return 0; 869 } 870 871 /* 872 * return 873 * 1 if v only used (and substitute), 874 * 2 if read-alter-rewrite 875 * 3 if set 876 * 4 if set and used 877 * 0 otherwise (not touched) 878 */ 879 int 880 copyu(Prog *p, Adr *v, Adr *s) 881 { 882 883 switch(p->as) { 884 885 default: 886 if(debug['P']) 887 print(" (?)"); 888 return 2; 889 890 case AMOVM: 891 if(v->type != D_REG) 892 return 0; 893 if(p->from.type == D_CONST) { /* read reglist, read/rar */ 894 if(s != A) { 895 if(p->from.offset&(1<<v->reg)) 896 return 1; 897 if(copysub(&p->to, v, s, 1)) 898 return 1; 899 return 0; 900 } 901 if(copyau(&p->to, v)) { 902 if(p->scond&C_WBIT) 903 return 2; 904 return 1; 905 } 906 if(p->from.offset&(1<<v->reg)) 907 return 1; 908 } else { /* read/rar, write reglist */ 909 if(s != A) { 910 if(p->to.offset&(1<<v->reg)) 911 return 1; 912 if(copysub(&p->from, v, s, 1)) 913 return 1; 914 return 0; 915 } 916 if(copyau(&p->from, v)) { 917 if(p->scond&C_WBIT) 918 return 2; 919 if(p->to.offset&(1<<v->reg)) 920 return 4; 921 return 1; 922 } 923 if(p->to.offset&(1<<v->reg)) 924 return 3; 925 } 926 return 0; 927 928 case ANOP: /* read, write */ 929 case AMOVW: 930 case AMOVF: 931 case AMOVD: 932 case AMOVH: 933 case AMOVHU: 934 case AMOVB: 935 case AMOVBU: 936 case AMOVDW: 937 case AMOVWD: 938 case AMOVFD: 939 case AMOVDF: 940 if(p->scond&(C_WBIT|C_PBIT)) 941 if(v->type == D_REG) { 942 if(p->from.type == D_OREG || p->from.type == D_SHIFT) { 943 if(p->from.reg == v->reg) 944 return 2; 945 } else { 946 if(p->to.reg == v->reg) 947 return 2; 948 } 949 } 950 if(s != A) { 951 if(copysub(&p->from, v, s, 1)) 952 return 1; 953 if(!copyas(&p->to, v)) 954 if(copysub(&p->to, v, s, 1)) 955 return 1; 956 return 0; 957 } 958 if(copyas(&p->to, v)) { 959 if(copyau(&p->from, v)) 960 return 4; 961 return 3; 962 } 963 if(copyau(&p->from, v)) 964 return 1; 965 if(copyau(&p->to, v)) 966 return 1; 967 return 0; 968 969 970 case AADD: /* read, read, write */ 971 case ASUB: 972 case ARSB: 973 case ASLL: 974 case ASRL: 975 case ASRA: 976 case AORR: 977 case AAND: 978 case AEOR: 979 case AMUL: 980 case ADIV: 981 case ADIVU: 982 case AADDF: 983 case AADDD: 984 case ASUBF: 985 case ASUBD: 986 case AMULF: 987 case AMULD: 988 case ADIVF: 989 case ADIVD: 990 991 case ACMPF: 992 case ACMPD: 993 case ACMP: 994 case ACMN: 995 case ACASE: 996 if(s != A) { 997 if(copysub(&p->from, v, s, 1)) 998 return 1; 999 if(copysub1(p, v, s, 1)) 1000 return 1; 1001 if(!copyas(&p->to, v)) 1002 if(copysub(&p->to, v, s, 1)) 1003 return 1; 1004 return 0; 1005 } 1006 if(copyas(&p->to, v)) { 1007 if(p->reg == NREG) 1008 p->reg = p->to.reg; 1009 if(copyau(&p->from, v)) 1010 return 4; 1011 if(copyau1(p, v)) 1012 return 4; 1013 return 3; 1014 } 1015 if(copyau(&p->from, v)) 1016 return 1; 1017 if(copyau1(p, v)) 1018 return 1; 1019 if(copyau(&p->to, v)) 1020 return 1; 1021 return 0; 1022 1023 case ABEQ: /* read, read */ 1024 case ABNE: 1025 case ABCS: 1026 case ABHS: 1027 case ABCC: 1028 case ABLO: 1029 case ABMI: 1030 case ABPL: 1031 case ABVS: 1032 case ABVC: 1033 case ABHI: 1034 case ABLS: 1035 case ABGE: 1036 case ABLT: 1037 case ABGT: 1038 case ABLE: 1039 if(s != A) { 1040 if(copysub(&p->from, v, s, 1)) 1041 return 1; 1042 return copysub1(p, v, s, 1); 1043 } 1044 if(copyau(&p->from, v)) 1045 return 1; 1046 if(copyau1(p, v)) 1047 return 1; 1048 return 0; 1049 1050 case AB: /* funny */ 1051 if(s != A) { 1052 if(copysub(&p->to, v, s, 1)) 1053 return 1; 1054 return 0; 1055 } 1056 if(copyau(&p->to, v)) 1057 return 1; 1058 return 0; 1059 1060 case ARET: /* funny */ 1061 if(v->type == D_REG) 1062 if(v->reg == REGRET) 1063 return 2; 1064 if(v->type == D_FREG) 1065 if(v->reg == FREGRET) 1066 return 2; 1067 1068 case ABL: /* funny */ 1069 if(v->type == D_REG) { 1070 if(v->reg <= REGEXT && v->reg > exregoffset) 1071 return 2; 1072 if(v->reg == REGARG) 1073 return 2; 1074 } 1075 if(v->type == D_FREG) 1076 if(v->reg <= FREGEXT && v->reg > exfregoffset) 1077 return 2; 1078 1079 if(s != A) { 1080 if(copysub(&p->to, v, s, 1)) 1081 return 1; 1082 return 0; 1083 } 1084 if(copyau(&p->to, v)) 1085 return 4; 1086 return 3; 1087 1088 case ATEXT: /* funny */ 1089 if(v->type == D_REG) 1090 if(v->reg == REGARG) 1091 return 3; 1092 return 0; 1093 } 1094 /* not reached */ 1095 } 1096 1097 int 1098 a2type(Prog *p) 1099 { 1100 1101 switch(p->as) { 1102 1103 case ACMP: 1104 case ACMN: 1105 1106 case AADD: 1107 case ASUB: 1108 case ARSB: 1109 case ASLL: 1110 case ASRL: 1111 case ASRA: 1112 case AORR: 1113 case AAND: 1114 case AEOR: 1115 case AMUL: 1116 case ADIV: 1117 case ADIVU: 1118 return D_REG; 1119 1120 case ACMPF: 1121 case ACMPD: 1122 1123 case AADDF: 1124 case AADDD: 1125 case ASUBF: 1126 case ASUBD: 1127 case AMULF: 1128 case AMULD: 1129 case ADIVF: 1130 case ADIVD: 1131 return D_FREG; 1132 } 1133 return D_NONE; 1134 } 1135 1136 /* 1137 * direct reference, 1138 * could be set/use depending on 1139 * semantics 1140 */ 1141 int 1142 copyas(Adr *a, Adr *v) 1143 { 1144 1145 if(regtyp(v)) { 1146 if(a->type == v->type) 1147 if(a->reg == v->reg) 1148 return 1; 1149 } else if(v->type == D_CONST) { /* for constprop */ 1150 if(a->type == v->type) 1151 if(a->name == v->name) 1152 if(a->sym == v->sym) 1153 if(a->reg == v->reg) 1154 if(a->offset == v->offset) 1155 return 1; 1156 } 1157 return 0; 1158 } 1159 1160 /* 1161 * either direct or indirect 1162 */ 1163 int 1164 copyau(Adr *a, Adr *v) 1165 { 1166 1167 if(copyas(a, v)) 1168 return 1; 1169 if(v->type == D_REG) { 1170 if(a->type == D_OREG) { 1171 if(v->reg == a->reg) 1172 return 1; 1173 } else if(a->type == D_SHIFT) { 1174 if((a->offset&0xf) == v->reg) 1175 return 1; 1176 if((a->offset&(1<<4)) && (a->offset>>8) == v->reg) 1177 return 1; 1178 } 1179 } 1180 return 0; 1181 } 1182 1183 int 1184 copyau1(Prog *p, Adr *v) 1185 { 1186 1187 if(regtyp(v)) { 1188 if(a2type(p) == v->type) 1189 if(p->reg == v->reg) { 1190 if(a2type(p) != v->type) 1191 print("botch a2type %P\n", p); 1192 return 1; 1193 } 1194 } 1195 return 0; 1196 } 1197 1198 /* 1199 * substitute s for v in a 1200 * return failure to substitute 1201 */ 1202 int 1203 copysub(Adr *a, Adr *v, Adr *s, int f) 1204 { 1205 1206 if(f) 1207 if(copyau(a, v)) { 1208 if(a->type == D_SHIFT) { 1209 if((a->offset&0xf) == v->reg) 1210 a->offset = (a->offset&~0xf)|s->reg; 1211 if((a->offset&(1<<4)) && (a->offset>>8) == v->reg) 1212 a->offset = (a->offset&~(0xf<<8))|(s->reg<<8); 1213 } else 1214 a->reg = s->reg; 1215 } 1216 return 0; 1217 } 1218 1219 int 1220 copysub1(Prog *p1, Adr *v, Adr *s, int f) 1221 { 1222 1223 if(f) 1224 if(copyau1(p1, v)) 1225 p1->reg = s->reg; 1226 return 0; 1227 } 1228 1229 struct { 1230 int opcode; 1231 int notopcode; 1232 int scond; 1233 int notscond; 1234 } predinfo[] = { 1235 { ABEQ, ABNE, 0x0, 0x1, }, 1236 { ABNE, ABEQ, 0x1, 0x0, }, 1237 { ABCS, ABCC, 0x2, 0x3, }, 1238 { ABHS, ABLO, 0x2, 0x3, }, 1239 { ABCC, ABCS, 0x3, 0x2, }, 1240 { ABLO, ABHS, 0x3, 0x2, }, 1241 { ABMI, ABPL, 0x4, 0x5, }, 1242 { ABPL, ABMI, 0x5, 0x4, }, 1243 { ABVS, ABVC, 0x6, 0x7, }, 1244 { ABVC, ABVS, 0x7, 0x6, }, 1245 { ABHI, ABLS, 0x8, 0x9, }, 1246 { ABLS, ABHI, 0x9, 0x8, }, 1247 { ABGE, ABLT, 0xA, 0xB, }, 1248 { ABLT, ABGE, 0xB, 0xA, }, 1249 { ABGT, ABLE, 0xC, 0xD, }, 1250 { ABLE, ABGT, 0xD, 0xC, }, 1251 }; 1252 1253 typedef struct { 1254 Reg *start; 1255 Reg *last; 1256 Reg *end; 1257 int len; 1258 } Joininfo; 1259 1260 enum { 1261 Join, 1262 Split, 1263 End, 1264 Branch, 1265 Setcond, 1266 Toolong 1267 }; 1268 1269 enum { 1270 Falsecond, 1271 Truecond, 1272 Delbranch, 1273 Keepbranch 1274 }; 1275 1276 int 1277 isbranch(Prog *p) 1278 { 1279 return (ABEQ <= p->as) && (p->as <= ABLE); 1280 } 1281 1282 int 1283 predicable(Prog *p) 1284 { 1285 if (isbranch(p) 1286 || p->as == ANOP 1287 || p->as == AXXX 1288 || p->as == ADATA 1289 || p->as == AGLOBL 1290 || p->as == AGOK 1291 || p->as == AHISTORY 1292 || p->as == ANAME 1293 || p->as == ASIGNAME 1294 || p->as == ATEXT 1295 || p->as == AWORD 1296 || p->as == ADYNT 1297 || p->as == AINIT 1298 || p->as == ABCASE 1299 || p->as == ACASE) 1300 return 0; 1301 return 1; 1302 } 1303 1304 /* 1305 * Depends on an analysis of the encodings performed by 5l. 1306 * These seem to be all of the opcodes that lead to the "S" bit 1307 * being set in the instruction encodings. 1308 * 1309 * C_SBIT may also have been set explicitly in p->scond. 1310 */ 1311 int 1312 modifiescpsr(Prog *p) 1313 { 1314 return (p->scond&C_SBIT) 1315 || p->as == ATST 1316 || p->as == ATEQ 1317 || p->as == ACMN 1318 || p->as == ACMP 1319 || p->as == AMULU 1320 || p->as == ADIVU 1321 || p->as == AMUL 1322 || p->as == ADIV 1323 || p->as == AMOD 1324 || p->as == AMODU 1325 || p->as == ABL; 1326 } 1327 1328 /* 1329 * Find the maximal chain of instructions starting with r which could 1330 * be executed conditionally 1331 */ 1332 int 1333 joinsplit(Reg *r, Joininfo *j) 1334 { 1335 j->start = r; 1336 j->last = r; 1337 j->len = 0; 1338 do { 1339 if (r->p2 && (r->p1 || r->p2->p2link)) { 1340 j->end = r; 1341 return Join; 1342 } 1343 if (r->s1 && r->s2) { 1344 j->end = r; 1345 return Split; 1346 } 1347 j->last = r; 1348 if (r->prog->as != ANOP) 1349 j->len++; 1350 if (!r->s1 && !r->s2) { 1351 j->end = r->link; 1352 return End; 1353 } 1354 if (r->s2) { 1355 j->end = r->s2; 1356 return Branch; 1357 } 1358 if (modifiescpsr(r->prog)) { 1359 j->end = r->s1; 1360 return Setcond; 1361 } 1362 r = r->s1; 1363 } while (j->len < 4); 1364 j->end = r; 1365 return Toolong; 1366 } 1367 1368 Reg * 1369 successor(Reg *r) 1370 { 1371 if (r->s1) 1372 return r->s1; 1373 else 1374 return r->s2; 1375 } 1376 1377 void 1378 applypred(Reg *rstart, Joininfo *j, int cond, int branch) 1379 { 1380 int pred; 1381 Reg *r; 1382 1383 if(j->len == 0) 1384 return; 1385 if (cond == Truecond) 1386 pred = predinfo[rstart->prog->as - ABEQ].scond; 1387 else 1388 pred = predinfo[rstart->prog->as - ABEQ].notscond; 1389 1390 for (r = j->start; ; r = successor(r)) { 1391 if (r->prog->as == AB) { 1392 if (r != j->last || branch == Delbranch) 1393 excise(r); 1394 else { 1395 if (cond == Truecond) 1396 r->prog->as = predinfo[rstart->prog->as - ABEQ].opcode; 1397 else 1398 r->prog->as = predinfo[rstart->prog->as - ABEQ].notopcode; 1399 } 1400 } 1401 else if (predicable(r->prog)) 1402 r->prog->scond = (r->prog->scond&~C_SCOND)|pred; 1403 if (r->s1 != r->link) { 1404 r->s1 = r->link; 1405 r->link->p1 = r; 1406 } 1407 if (r == j->last) 1408 break; 1409 } 1410 } 1411 1412 void 1413 predicate(void) 1414 { 1415 Reg *r; 1416 int t1, t2; 1417 Joininfo j1, j2; 1418 1419 for(r=firstr; r!=R; r=r->link) { 1420 if (isbranch(r->prog)) { 1421 t1 = joinsplit(r->s1, &j1); 1422 t2 = joinsplit(r->s2, &j2); 1423 if(j1.last->link != j2.start) 1424 continue; 1425 if(j1.end == j2.end) 1426 if((t1 == Branch && (t2 == Join || t2 == Setcond)) || 1427 (t2 == Join && (t1 == Join || t1 == Setcond))) { 1428 applypred(r, &j1, Falsecond, Delbranch); 1429 applypred(r, &j2, Truecond, Delbranch); 1430 excise(r); 1431 continue; 1432 } 1433 if(t1 == End || t1 == Branch) { 1434 applypred(r, &j1, Falsecond, Keepbranch); 1435 excise(r); 1436 continue; 1437 } 1438 } 1439 } 1440 } 1441