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