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 copyu(Prog *p, Adr *v, Adr *s) 407 { 408 409 switch(p->as) { 410 411 default: 412 if(debug['P']) 413 print(" (?)"); 414 return 2; 415 416 417 case ANOP: /* read, write */ 418 case AMOVW: 419 case AMOVF: 420 case AMOVD: 421 case AMOVH: 422 case AMOVHU: 423 case AMOVB: 424 case AMOVBU: 425 case AMOVDW: 426 case AMOVWD: 427 case AMOVFD: 428 case AMOVDF: 429 if(s != A) { 430 if(copysub(&p->from, v, s, 1)) 431 return 1; 432 if(!copyas(&p->to, v)) 433 if(copysub(&p->to, v, s, 1)) 434 return 1; 435 return 0; 436 } 437 if(copyas(&p->to, v)) { 438 if(copyau(&p->from, v)) 439 return 4; 440 return 3; 441 } 442 if(copyau(&p->from, v)) 443 return 1; 444 if(copyau(&p->to, v)) 445 return 1; 446 return 0; 447 448 case ASGT: /* read, read, write */ 449 case ASGTU: 450 451 case AADD: 452 case AADDU: 453 case ASUB: 454 case ASUBU: 455 case ASLL: 456 case ASRL: 457 case ASRA: 458 case AOR: 459 case ANOR: 460 case AAND: 461 case AXOR: 462 case AMUL: 463 case AMULU: 464 case ADIV: 465 case ADIVU: 466 467 case AADDF: 468 case AADDD: 469 case ASUBF: 470 case ASUBD: 471 case AMULF: 472 case AMULD: 473 case ADIVF: 474 case ADIVD: 475 if(s != A) { 476 if(copysub(&p->from, v, s, 1)) 477 return 1; 478 if(copysub1(p, v, s, 1)) 479 return 1; 480 if(!copyas(&p->to, v)) 481 if(copysub(&p->to, v, s, 1)) 482 return 1; 483 return 0; 484 } 485 if(copyas(&p->to, v)) { 486 if(p->reg == NREG) 487 p->reg = p->to.reg; 488 if(copyau(&p->from, v)) 489 return 4; 490 if(copyau1(p, v)) 491 return 4; 492 return 3; 493 } 494 if(copyau(&p->from, v)) 495 return 1; 496 if(copyau1(p, v)) 497 return 1; 498 if(copyau(&p->to, v)) 499 return 1; 500 return 0; 501 502 case ABEQ: /* read, read */ 503 case ABNE: 504 case ABGTZ: 505 case ABGEZ: 506 case ABLTZ: 507 case ABLEZ: 508 509 case ACMPEQD: 510 case ACMPEQF: 511 case ACMPGED: 512 case ACMPGEF: 513 case ACMPGTD: 514 case ACMPGTF: 515 case ABFPF: 516 case ABFPT: 517 if(s != A) { 518 if(copysub(&p->from, v, s, 1)) 519 return 1; 520 return copysub1(p, v, s, 1); 521 } 522 if(copyau(&p->from, v)) 523 return 1; 524 if(copyau1(p, v)) 525 return 1; 526 return 0; 527 528 case AJMP: /* funny */ 529 if(s != A) { 530 if(copysub(&p->to, v, s, 1)) 531 return 1; 532 return 0; 533 } 534 if(copyau(&p->to, v)) 535 return 1; 536 return 0; 537 538 case ARET: /* funny */ 539 if(v->type == D_REG) 540 if(v->reg == REGRET) 541 return 2; 542 if(v->type == D_FREG) 543 if(v->reg == FREGRET) 544 return 2; 545 546 case AJAL: /* funny */ 547 if(v->type == D_REG) { 548 if(v->reg <= REGEXT && v->reg > exregoffset) 549 return 2; 550 if(REGARG && v->reg == REGARG) 551 return 2; 552 } 553 if(v->type == D_FREG) 554 if(v->reg <= FREGEXT && v->reg > exfregoffset) 555 return 2; 556 557 if(s != A) { 558 if(copysub(&p->to, v, s, 1)) 559 return 1; 560 return 0; 561 } 562 if(copyau(&p->to, v)) 563 return 4; 564 return 3; 565 566 case ATEXT: /* funny */ 567 if(v->type == D_REG) 568 if(v->reg == REGARG) 569 return 3; 570 return 0; 571 } 572 /* not reached */ 573 } 574 575 int 576 a2type(Prog *p) 577 { 578 579 switch(p->as) { 580 case ABEQ: 581 case ABNE: 582 case ABGTZ: 583 case ABGEZ: 584 case ABLTZ: 585 case ABLEZ: 586 587 case ASGT: 588 case ASGTU: 589 590 case AADD: 591 case AADDU: 592 case ASUB: 593 case ASUBU: 594 case ASLL: 595 case ASRL: 596 case ASRA: 597 case AOR: 598 case AAND: 599 case AXOR: 600 case AMUL: 601 case AMULU: 602 case ADIV: 603 case ADIVU: 604 return D_REG; 605 606 case ACMPEQD: 607 case ACMPEQF: 608 case ACMPGED: 609 case ACMPGEF: 610 case ACMPGTD: 611 case ACMPGTF: 612 613 case AADDF: 614 case AADDD: 615 case ASUBF: 616 case ASUBD: 617 case AMULF: 618 case AMULD: 619 case ADIVF: 620 case ADIVD: 621 return D_FREG; 622 } 623 return D_NONE; 624 } 625 626 /* 627 * direct reference, 628 * could be set/use depending on 629 * semantics 630 */ 631 int 632 copyas(Adr *a, Adr *v) 633 { 634 635 if(regtyp(v)) 636 if(a->type == v->type) 637 if(a->reg == v->reg) 638 return 1; 639 return 0; 640 } 641 642 /* 643 * either direct or indirect 644 */ 645 int 646 copyau(Adr *a, Adr *v) 647 { 648 649 if(copyas(a, v)) 650 return 1; 651 if(v->type == D_REG) 652 if(a->type == D_OREG) 653 if(v->reg == a->reg) 654 return 1; 655 return 0; 656 } 657 658 int 659 copyau1(Prog *p, Adr *v) 660 { 661 662 if(regtyp(v)) 663 if(p->from.type == v->type || p->to.type == v->type) 664 if(p->reg == v->reg) { 665 if(a2type(p) != v->type) 666 print("botch a2type %P\n", p); 667 return 1; 668 } 669 return 0; 670 } 671 672 /* 673 * substitute s for v in a 674 * return failure to substitute 675 */ 676 int 677 copysub(Adr *a, Adr *v, Adr *s, int f) 678 { 679 680 if(f) 681 if(copyau(a, v)) 682 a->reg = s->reg; 683 return 0; 684 } 685 686 int 687 copysub1(Prog *p1, Adr *v, Adr *s, int f) 688 { 689 690 if(f) 691 if(copyau1(p1, v)) 692 p1->reg = s->reg; 693 return 0; 694 } 695