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 == AMOVF || p->as == AMOVD) 47 if(regtyp(&p->to)) { 48 if(p->from.type == D_CONST) 49 constprop(&p->from, &p->to, r->s1); 50 else if(regtyp(&p->from)) 51 if(p->from.type == p->to.type) { 52 if(copyprop(r)) { 53 excise(r); 54 t++; 55 } else 56 if(subprop(r) && copyprop(r)) { 57 excise(r); 58 t++; 59 } 60 } 61 } 62 } 63 if(t) 64 goto loop1; 65 /* 66 * look for MOVB x,R; MOVB R,R 67 */ 68 for(r=firstr; r!=R; r=r->link) { 69 p = r->prog; 70 switch(p->as) { 71 default: 72 continue; 73 case AEOR: 74 /* 75 * EOR -1,x,y => MVN x,y 76 */ 77 if(p->from.type == D_CONST && p->from.offset == -1) { 78 p->as = AMVN; 79 p->from.type = D_REG; 80 if(p->reg != NREG) 81 p->from.reg = p->reg; 82 else 83 p->from.reg = p->to.reg; 84 p->reg = NREG; 85 } 86 continue; 87 case AMOVH: 88 case AMOVHU: 89 case AMOVB: 90 case AMOVBU: 91 if(p->to.type != D_REG) 92 continue; 93 break; 94 } 95 r1 = r->link; 96 if(r1 == R) 97 continue; 98 p1 = r1->prog; 99 if(p1->as != p->as) 100 continue; 101 if(p1->from.type != D_REG || p1->from.reg != p->to.reg) 102 continue; 103 if(p1->to.type != D_REG || p1->to.reg != p->to.reg) 104 continue; 105 excise(r1); 106 } 107 } 108 109 void 110 excise(Reg *r) 111 { 112 Prog *p; 113 114 p = r->prog; 115 p->as = ANOP; 116 p->from = zprog.from; 117 p->to = zprog.to; 118 p->reg = zprog.reg; /**/ 119 } 120 121 Reg* 122 uniqp(Reg *r) 123 { 124 Reg *r1; 125 126 r1 = r->p1; 127 if(r1 == R) { 128 r1 = r->p2; 129 if(r1 == R || r1->p2link != R) 130 return R; 131 } else 132 if(r->p2 != R) 133 return R; 134 return r1; 135 } 136 137 Reg* 138 uniqs(Reg *r) 139 { 140 Reg *r1; 141 142 r1 = r->s1; 143 if(r1 == R) { 144 r1 = r->s2; 145 if(r1 == R) 146 return R; 147 } else 148 if(r->s2 != R) 149 return R; 150 return r1; 151 } 152 153 int 154 regtyp(Adr *a) 155 { 156 157 if(a->type == D_REG) 158 return 1; 159 if(a->type == D_FREG) 160 return 1; 161 return 0; 162 } 163 164 /* 165 * the idea is to substitute 166 * one register for another 167 * from one MOV to another 168 * MOV a, R0 169 * ADD b, R0 / no use of R1 170 * MOV R0, R1 171 * would be converted to 172 * MOV a, R1 173 * ADD b, R1 174 * MOV R1, R0 175 * hopefully, then the former or latter MOV 176 * will be eliminated by copy propagation. 177 */ 178 int 179 subprop(Reg *r0) 180 { 181 Prog *p; 182 Adr *v1, *v2; 183 Reg *r; 184 int t; 185 186 p = r0->prog; 187 v1 = &p->from; 188 if(!regtyp(v1)) 189 return 0; 190 v2 = &p->to; 191 if(!regtyp(v2)) 192 return 0; 193 for(r=uniqp(r0); r!=R; r=uniqp(r)) { 194 if(uniqs(r) == R) 195 break; 196 p = r->prog; 197 switch(p->as) { 198 case ABL: 199 case ABX: 200 return 0; 201 202 // case ACMP: 203 // case ACMN: 204 case AADD: 205 case ASUB: 206 // case ASLL: 207 // case ASRL: 208 // case ASRA: 209 // case AORR: 210 // case AAND: 211 // case AEOR: 212 // case AMUL: 213 // case ADIV: 214 // case ADIVU: 215 216 // case ACMPF: 217 // case ACMPD: 218 // case AADDD: 219 // case AADDF: 220 // case ASUBD: 221 // case ASUBF: 222 // case AMULD: 223 // case AMULF: 224 // case ADIVD: 225 // case ADIVF: 226 if(p->to.type == v1->type) 227 if(p->to.reg == v1->reg) { 228 if(p->reg == NREG) 229 p->reg = p->to.reg; 230 goto gotit; 231 } 232 break; 233 234 case AMOVF: 235 case AMOVD: 236 case AMOVW: 237 if(p->to.type == v1->type) 238 if(p->to.reg == v1->reg) 239 goto gotit; 240 break; 241 242 case AMOVM: 243 t = 1<<v2->reg; 244 if((p->from.type == D_CONST && (p->from.offset&t)) || 245 (p->to.type == D_CONST && (p->to.offset&t))) 246 return 0; 247 break; 248 } 249 if(copyau(&p->from, v2) || 250 copyau1(p, v2) || 251 copyau(&p->to, v2)) 252 break; 253 if(copysub(&p->from, v1, v2, 0) || 254 copysub1(p, v1, v2, 0) || 255 copysub(&p->to, v1, v2, 0)) 256 break; 257 } 258 return 0; 259 260 gotit: 261 copysub(&p->to, v1, v2, 1); 262 if(debug['P']) { 263 print("gotit: %D->%D\n%P", v1, v2, r->prog); 264 if(p->from.type == v2->type) 265 print(" excise"); 266 print("\n"); 267 } 268 for(r=uniqs(r); r!=r0; r=uniqs(r)) { 269 p = r->prog; 270 copysub(&p->from, v1, v2, 1); 271 copysub1(p, v1, v2, 1); 272 copysub(&p->to, v1, v2, 1); 273 if(debug['P']) 274 print("%P\n", r->prog); 275 } 276 t = v1->reg; 277 v1->reg = v2->reg; 278 v2->reg = t; 279 if(debug['P']) 280 print("%P last\n", r->prog); 281 return 1; 282 } 283 284 /* 285 * The idea is to remove redundant copies. 286 * v1->v2 F=0 287 * (use v2 s/v2/v1/)* 288 * set v1 F=1 289 * use v2 return fail 290 * ----------------- 291 * v1->v2 F=0 292 * (use v2 s/v2/v1/)* 293 * set v1 F=1 294 * set v2 return success 295 */ 296 int 297 copyprop(Reg *r0) 298 { 299 Prog *p; 300 Adr *v1, *v2; 301 Reg *r; 302 303 p = r0->prog; 304 v1 = &p->from; 305 v2 = &p->to; 306 if(copyas(v1, v2)) 307 return 1; 308 for(r=firstr; r!=R; r=r->link) 309 r->active = 0; 310 return copy1(v1, v2, r0->s1, 0); 311 } 312 313 int 314 copy1(Adr *v1, Adr *v2, Reg *r, int f) 315 { 316 int t; 317 Prog *p; 318 319 if(r->active) { 320 if(debug['P']) 321 print("act set; return 1\n"); 322 return 1; 323 } 324 r->active = 1; 325 if(debug['P']) 326 print("copy %D->%D f=%d\n", v1, v2, f); 327 for(; r != R; r = r->s1) { 328 p = r->prog; 329 if(debug['P']) 330 print("%P", p); 331 if(!f && uniqp(r) == R) { 332 f = 1; 333 if(debug['P']) 334 print("; merge; f=%d", f); 335 } 336 t = copyu(p, v2, A); 337 switch(t) { 338 case 2: /* rar, cant split */ 339 if(debug['P']) 340 print("; %Drar; return 0\n", v2); 341 return 0; 342 343 case 3: /* set */ 344 if(debug['P']) 345 print("; %Dset; return 1\n", v2); 346 return 1; 347 348 case 1: /* used, substitute */ 349 case 4: /* use and set */ 350 if(f) { 351 if(!debug['P']) 352 return 0; 353 if(t == 4) 354 print("; %Dused+set and f=%d; return 0\n", v2, f); 355 else 356 print("; %Dused and f=%d; return 0\n", v2, f); 357 return 0; 358 } 359 if(copyu(p, v2, v1)) { 360 if(debug['P']) 361 print("; sub fail; return 0\n"); 362 return 0; 363 } 364 if(debug['P']) 365 print("; sub%D/%D", v2, v1); 366 if(t == 4) { 367 if(debug['P']) 368 print("; %Dused+set; return 1\n", v2); 369 return 1; 370 } 371 break; 372 } 373 if(!f) { 374 t = copyu(p, v1, A); 375 if(!f && (t == 2 || t == 3 || t == 4)) { 376 f = 1; 377 if(debug['P']) 378 print("; %Dset and !f; f=%d", v1, f); 379 } 380 } 381 if(debug['P']) 382 print("\n"); 383 if(r->s2) 384 if(!copy1(v1, v2, r->s2, f)) 385 return 0; 386 } 387 return 1; 388 } 389 390 /* 391 * The idea is to remove redundant constants. 392 * $c1->v1 393 * ($c1->v2 s/$c1/v1)* 394 * set v1 return 395 * The v1->v2 should be eliminated by copy propagation. 396 */ 397 void 398 constprop(Adr *c1, Adr *v1, Reg *r) 399 { 400 Prog *p; 401 402 if(debug['C']) 403 print("constprop %D->%D\n", c1, v1); 404 for(; r != R; r = r->s1) { 405 p = r->prog; 406 if(debug['C']) 407 print("%P", p); 408 if(uniqp(r) == R) { 409 if(debug['C']) 410 print("; merge; return\n"); 411 return; 412 } 413 if(p->as == AMOVW && copyas(&p->from, c1)) { 414 if(debug['C']) 415 print("; sub%D/%D", &p->from, v1); 416 p->from = *v1; 417 } else if(copyu(p, v1, A) > 1) { 418 if(debug['C']) 419 print("; %Dset; return\n", v1); 420 return; 421 } 422 if(debug['C']) 423 print("\n"); 424 if(r->s2) 425 constprop(c1, v1, r->s2); 426 } 427 } 428 429 /* 430 * return 431 * 1 if v only used (and substitute), 432 * 2 if read-alter-rewrite 433 * 3 if set 434 * 4 if set and used 435 * 0 otherwise (not touched) 436 */ 437 int 438 copyu(Prog *p, Adr *v, Adr *s) 439 { 440 441 switch(p->as) { 442 443 default: 444 if(debug['P']) 445 print(" (?)"); 446 return 2; 447 448 case AMOVM: 449 if(v->type != D_REG) 450 return 0; 451 if(p->from.type == D_CONST) { /* read reglist, read/rar */ 452 if(s != A) { 453 if(p->from.offset&(1<<v->reg)) 454 return 1; 455 if(copysub(&p->to, v, s, 1)) 456 diag(Z, "movm dst being replaced"); // was return 1; 457 return 0; 458 } 459 if(copyau(&p->to, v)) 460 return 2; // register updated in thumb // was return 1; 461 if(p->from.offset&(1<<v->reg)) 462 return 1; 463 } else { /* read/rar, write reglist */ 464 if(s != A) { 465 if(p->to.offset&(1<<v->reg)) 466 return 1; 467 if(copysub(&p->from, v, s, 1)) 468 diag(Z, "movm src being replaced"); // was return 1; 469 return 0; 470 } 471 if(copyau(&p->from, v)) { 472 // if(p->to.offset&(1<<v->reg)) 473 // return 4; 474 return 2; // register updated in thumb // was return 1; 475 } 476 if(p->to.offset&(1<<v->reg)) 477 return 3; 478 } 479 return 0; 480 481 case ANOP: /* read, write */ 482 case AMOVW: 483 case AMOVF: 484 case AMOVD: 485 case AMOVH: 486 case AMOVHU: 487 case AMOVB: 488 case AMOVBU: 489 case AMOVDW: 490 case AMOVWD: 491 case AMOVFD: 492 case AMOVDF: 493 if(s != A) { 494 if(copysub(&p->from, v, s, 1)) 495 return 1; 496 if(!copyas(&p->to, v)) 497 if(copysub(&p->to, v, s, 1)) 498 return 1; 499 return 0; 500 } 501 if(copyas(&p->to, v)) { 502 if(copyau(&p->from, v)) 503 return 4; 504 return 3; 505 } 506 if(copyau(&p->from, v)) 507 return 1; 508 if(copyau(&p->to, v)) 509 return 1; 510 return 0; 511 512 case ASLL: 513 case ASRL: 514 case ASRA: 515 case AORR: 516 case AAND: 517 case AEOR: 518 case AMUL: 519 case ADIV: 520 case ADIVU: 521 case AADDF: 522 case AADDD: 523 case ASUBF: 524 case ASUBD: 525 case AMULF: 526 case AMULD: 527 case ADIVF: 528 case ADIVD: 529 case ACMPF: 530 case ACMPD: 531 case ACMP: 532 case ACMN: 533 if(copyas(&p->to, v)) 534 return 2; 535 /*FALLTHROUGH*/ 536 537 case AADD: /* read, read, write */ 538 case ASUB: 539 if(s != A) { 540 if(copysub(&p->from, v, s, 1)) 541 return 1; 542 if(copysub1(p, v, s, 1)) 543 return 1; 544 if(!copyas(&p->to, v)) 545 if(copysub(&p->to, v, s, 1)) 546 return 1; 547 return 0; 548 } 549 if(copyas(&p->to, v)) { 550 if(p->reg == NREG) 551 p->reg = p->to.reg; 552 if(copyau(&p->from, v)) 553 return 4; 554 if(copyau1(p, v)) 555 return 4; 556 return 3; 557 } 558 if(copyau(&p->from, v)) 559 return 1; 560 if(copyau1(p, v)) 561 return 1; 562 if(copyau(&p->to, v)) 563 return 1; 564 return 0; 565 566 case ABEQ: /* read, read */ 567 case ABNE: 568 case ABCS: 569 case ABHS: 570 case ABCC: 571 case ABLO: 572 case ABMI: 573 case ABPL: 574 case ABVS: 575 case ABVC: 576 case ABHI: 577 case ABLS: 578 case ABGE: 579 case ABLT: 580 case ABGT: 581 case ABLE: 582 if(s != A) { 583 if(copysub(&p->from, v, s, 1)) 584 return 1; 585 return copysub1(p, v, s, 1); 586 } 587 if(copyau(&p->from, v)) 588 return 1; 589 if(copyau1(p, v)) 590 return 1; 591 return 0; 592 593 case AB: /* funny */ 594 if(s != A) { 595 if(copysub(&p->to, v, s, 1)) 596 return 1; 597 return 0; 598 } 599 if(copyau(&p->to, v)) 600 return 1; 601 return 0; 602 603 case ARET: /* funny */ 604 if(v->type == D_REG) 605 if(v->reg == REGRET) 606 return 2; 607 if(v->type == D_FREG) 608 if(v->reg == FREGRET) 609 return 2; 610 611 case ABL: /* funny */ 612 case ABX: 613 if(v->type == D_REG) { 614 if(v->reg <= REGEXT && v->reg > exregoffset) 615 return 2; 616 if(v->reg == REGARG) 617 return 2; 618 } 619 if(v->type == D_FREG) 620 if(v->reg <= FREGEXT && v->reg > exfregoffset) 621 return 2; 622 623 if(s != A) { 624 if(copysub(&p->to, v, s, 1)) 625 return 1; 626 return 0; 627 } 628 if(copyau(&p->to, v)) 629 return 4; 630 return 3; 631 632 case ATEXT: /* funny */ 633 if(v->type == D_REG) 634 if(v->reg == REGARG) 635 return 3; 636 return 0; 637 } 638 /* not reached */ 639 } 640 641 int 642 a2type(Prog *p) 643 { 644 645 switch(p->as) { 646 647 case ACMP: 648 case ACMN: 649 650 case AADD: 651 case ASUB: 652 case ASLL: 653 case ASRL: 654 case ASRA: 655 case AORR: 656 case AAND: 657 case AEOR: 658 case AMUL: 659 case ADIV: 660 case ADIVU: 661 return D_REG; 662 663 case ACMPF: 664 case ACMPD: 665 666 case AADDF: 667 case AADDD: 668 case ASUBF: 669 case ASUBD: 670 case AMULF: 671 case AMULD: 672 case ADIVF: 673 case ADIVD: 674 return D_FREG; 675 } 676 return D_NONE; 677 } 678 679 /* 680 * direct reference, 681 * could be set/use depending on 682 * semantics 683 */ 684 int 685 copyas(Adr *a, Adr *v) 686 { 687 688 if(regtyp(v)) { 689 if(a->type == v->type) 690 if(a->reg == v->reg) 691 return 1; 692 } else if(v->type == D_CONST) { /* for constprop */ 693 if(a->type == v->type) 694 if(a->name == v->name) 695 if(a->sym == v->sym) 696 if(a->reg == v->reg) 697 if(a->offset == v->offset) 698 return 1; 699 } 700 return 0; 701 } 702 703 /* 704 * either direct or indirect 705 */ 706 int 707 copyau(Adr *a, Adr *v) 708 { 709 710 if(copyas(a, v)) 711 return 1; 712 if(v->type == D_REG) { 713 if(a->type == D_OREG) { 714 if(v->reg == a->reg) 715 return 1; 716 } 717 } 718 return 0; 719 } 720 721 int 722 copyau1(Prog *p, Adr *v) 723 { 724 725 if(regtyp(v)) { 726 if(a2type(p) == v->type) 727 if(p->reg == v->reg) { 728 if(a2type(p) != v->type) 729 print("botch a2type %P\n", p); 730 return 1; 731 } 732 } 733 return 0; 734 } 735 736 /* 737 * substitute s for v in a 738 * return failure to substitute 739 */ 740 int 741 copysub(Adr *a, Adr *v, Adr *s, int f) 742 { 743 744 if(f) 745 if(copyau(a, v)) { 746 a->reg = s->reg; 747 } 748 return 0; 749 } 750 751 int 752 copysub1(Prog *p1, Adr *v, Adr *s, int f) 753 { 754 755 if(f) 756 if(copyau1(p1, v)) 757 p1->reg = s->reg; 758 return 0; 759 } 760