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