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