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 == AFMOVF || p->as == AFMOVD) 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 regzer(Adr *a) 150 { 151 152 if(a->type == D_CONST) 153 if(a->sym == S) 154 if(a->offset == 0) 155 return 1; 156 if(a->type == D_REG) 157 if(a->reg == 0) 158 return 1; 159 return 0; 160 } 161 162 regtyp(Adr *a) 163 { 164 165 if(a->type == D_REG) { 166 if(a->reg != 0) 167 return 1; 168 return 0; 169 } 170 if(a->type == D_FREG) 171 return 1; 172 return 0; 173 } 174 175 /* 176 * the idea is to substitute 177 * one register for another 178 * from one MOV to another 179 * MOV a, R0 180 * ADD b, R0 / no use of R1 181 * MOV R0, R1 182 * would be converted to 183 * MOV a, R1 184 * ADD b, R1 185 * MOV R1, R0 186 * hopefully, then the former or latter MOV 187 * will be eliminated by copy propagation. 188 */ 189 int 190 subprop(Reg *r0) 191 { 192 Prog *p; 193 Adr *v1, *v2; 194 Reg *r; 195 int t; 196 197 p = r0->prog; 198 v1 = &p->from; 199 if(!regtyp(v1)) 200 return 0; 201 v2 = &p->to; 202 if(!regtyp(v2)) 203 return 0; 204 for(r=uniqp(r0); r!=R; r=uniqp(r)) { 205 if(uniqs(r) == R) 206 break; 207 p = r->prog; 208 switch(p->as) { 209 case AJMPL: 210 return 0; 211 212 case AADD: 213 case ASUB: 214 case ASLL: 215 case ASRL: 216 case ASRA: 217 case AOR: 218 case AAND: 219 case AXOR: 220 case AMUL: 221 case ADIV: 222 case ADIVL: 223 case AMOD: 224 case AMODL: 225 226 case AFADDD: 227 case AFADDF: 228 case AFSUBD: 229 case AFSUBF: 230 case AFMULD: 231 case AFMULF: 232 case AFDIVD: 233 case AFDIVF: 234 if(p->to.type == v1->type) 235 if(p->to.reg == v1->reg) { 236 if(p->reg == NREG) 237 p->reg = p->to.reg; 238 goto gotit; 239 } 240 break; 241 242 case AFMOVF: 243 case AFMOVD: 244 case AMOVW: 245 if(p->to.type == v1->type) 246 if(p->to.reg == v1->reg) 247 goto gotit; 248 break; 249 } 250 if(copyau(&p->from, v2) || 251 copyau1(p, v2) || 252 copyau(&p->to, v2)) 253 break; 254 if(copysub(&p->from, v1, v2, 0) || 255 copysub1(p, v1, v2, 0) || 256 copysub(&p->to, v1, v2, 0)) 257 break; 258 } 259 return 0; 260 261 gotit: 262 copysub(&p->to, v1, v2, 1); 263 if(debug['P']) { 264 print("gotit: %D->%D\n%P", v1, v2, r->prog); 265 if(p->from.type == v2->type) 266 print(" excise"); 267 print("\n"); 268 } 269 for(r=uniqs(r); r!=r0; r=uniqs(r)) { 270 p = r->prog; 271 copysub(&p->from, v1, v2, 1); 272 copysub1(p, v1, v2, 1); 273 copysub(&p->to, v1, v2, 1); 274 if(debug['P']) 275 print("%P\n", r->prog); 276 } 277 t = v1->reg; 278 v1->reg = v2->reg; 279 v2->reg = t; 280 if(debug['P']) 281 print("%P last\n", r->prog); 282 return 1; 283 } 284 285 /* 286 * The idea is to remove redundant copies. 287 * v1->v2 F=0 288 * (use v2 s/v2/v1/)* 289 * set v1 F=1 290 * use v2 return fail 291 * ----------------- 292 * v1->v2 F=0 293 * (use v2 s/v2/v1/)* 294 * set v1 F=1 295 * set v2 return success 296 */ 297 int 298 copyprop(Reg *r0) 299 { 300 Prog *p; 301 Adr *v1, *v2; 302 Reg *r; 303 304 p = r0->prog; 305 v1 = &p->from; 306 v2 = &p->to; 307 if(copyas(v1, v2)) 308 return 1; 309 for(r=firstr; r!=R; r=r->link) 310 r->active = 0; 311 return copy1(v1, v2, r0->s1, 0); 312 } 313 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 * return 392 * 1 if v only used (and substitute), 393 * 2 if read-alter-rewrite 394 * 3 if set 395 * 4 if set and used 396 * 0 otherwise (not touched) 397 */ 398 int 399 copyu(Prog *p, Adr *v, Adr *s) 400 { 401 402 switch(p->as) { 403 404 default: 405 if(debug['P']) 406 print(" (???)"); 407 return 2; 408 409 410 case ANOP: /* read, write */ 411 case AMOVW: 412 case AMOVH: 413 case AMOVHU: 414 case AMOVB: 415 case AMOVBU: 416 417 case AFMOVF: 418 case AFMOVD: 419 case AFMOVDW: 420 case AFMOVWD: 421 case AFMOVFW: 422 case AFMOVWF: 423 case AFMOVFD: 424 case AFMOVDF: 425 if(s != A) { 426 if(copysub(&p->from, v, s, 1)) 427 return 1; 428 if(!copyas(&p->to, v)) 429 if(copysub(&p->to, v, s, 1)) 430 return 1; 431 return 0; 432 } 433 if(copyas(&p->to, v)) { 434 if(copyau(&p->from, v)) 435 return 4; 436 return 3; 437 } 438 if(copyau(&p->from, v)) 439 return 1; 440 if(copyau(&p->to, v)) 441 return 1; 442 return 0; 443 444 case AADD: /* read read write */ 445 case ASUB: 446 case ASLL: 447 case ASRL: 448 case ASRA: 449 case AOR: 450 case AAND: 451 case AXOR: 452 case AMUL: 453 case ADIV: 454 case ADIVL: 455 case AMOD: 456 case AMODL: 457 458 case AFADDF: 459 case AFADDD: 460 case AFSUBF: 461 case AFSUBD: 462 case AFMULF: 463 case AFMULD: 464 case AFDIVF: 465 case AFDIVD: 466 if(s != A) { 467 if(copysub(&p->from, v, s, 1)) 468 return 1; 469 if(copysub1(p, v, s, 1)) 470 return 1; 471 if(!copyas(&p->to, v)) 472 if(copysub(&p->to, v, s, 1)) 473 return 1; 474 return 0; 475 } 476 if(copyas(&p->to, v)) { 477 if(p->reg == NREG) 478 p->reg = p->to.reg; 479 if(copyau(&p->from, v)) 480 return 4; 481 if(copyau1(p, v)) 482 return 4; 483 return 3; 484 } 485 if(copyau(&p->from, v)) 486 return 1; 487 if(copyau1(p, v)) 488 return 1; 489 if(copyau(&p->to, v)) 490 return 1; 491 return 0; 492 493 case ABA: /* no reference */ 494 case ABCC: 495 case ABCS: 496 case ABE: 497 case ABG: 498 case ABGE: 499 case ABGU: 500 case ABL: 501 case ABLE: 502 case ABLEU: 503 case ABN: 504 case ABNE: 505 case ABNEG: 506 case ABPOS: 507 case ABVC: 508 case ABVS: 509 case AFBA: 510 case AFBE: 511 case AFBG: 512 case AFBGE: 513 case AFBL: 514 case AFBLE: 515 case AFBNE: 516 case AFBN: 517 case AFBLG: 518 case AFBO: 519 case AFBU: 520 case AFBUE: 521 case AFBUG: 522 case AFBUGE: 523 case AFBUL: 524 case AFBULE: 525 break; 526 527 case ACMP: /* read read */ 528 case AFCMPD: 529 case AFCMPF: 530 if(s != A) { 531 if(copysub(&p->from, v, s, 1)) 532 return 1; 533 return copysub(&p->to, v, s, 1); 534 } 535 if(copyau(&p->from, v)) 536 return 1; 537 if(copyau(&p->to, v)) 538 return 1; 539 break; 540 541 case AJMP: /* funny */ 542 if(s != A) { 543 if(copysub(&p->to, v, s, 1)) 544 return 1; 545 return 0; 546 } 547 if(copyau(&p->to, v)) 548 return 1; 549 return 0; 550 551 case ARETURN: /* funny */ 552 if(v->type == D_REG) 553 if(v->reg == REGRET) 554 return 2; 555 if(v->type == D_FREG) 556 if(v->reg == FREGRET) 557 return 2; 558 559 case AJMPL: /* funny */ 560 if(v->type == D_REG) { 561 if(v->reg <= REGEXT && v->reg > exregoffset) 562 return 2; 563 if(v->reg == REGARG) 564 return 2; 565 } 566 if(v->type == D_FREG) { 567 if(v->reg <= FREGEXT && v->reg > exfregoffset) 568 return 2; 569 } 570 571 if(s != A) { 572 if(copysub(&p->to, v, s, 1)) 573 return 1; 574 return 0; 575 } 576 if(copyau(&p->to, v)) 577 return 4; 578 return 3; 579 580 case ATEXT: /* funny */ 581 if(v->type == D_REG) 582 if(v->reg == REGARG) 583 return 3; 584 return 0; 585 } 586 return 0; 587 } 588 589 int 590 a2type(Prog *p) 591 { 592 593 switch(p->as) { 594 case AADD: 595 case ASUB: 596 case ASLL: 597 case ASRL: 598 case ASRA: 599 case AOR: 600 case AAND: 601 case AXOR: 602 case AMUL: 603 case ADIV: 604 case ADIVL: 605 case AMOD: 606 case AMODL: 607 return D_REG; 608 609 case AFADDF: 610 case AFADDD: 611 case AFSUBF: 612 case AFSUBD: 613 case AFMULF: 614 case AFMULD: 615 case AFDIVF: 616 case AFDIVD: 617 return D_FREG; 618 } 619 return D_NONE; 620 } 621 622 /* 623 * direct reference, 624 * could be set/use depending on 625 * semantics 626 */ 627 int 628 copyas(Adr *a, Adr *v) 629 { 630 631 if(regtyp(v)) 632 if(a->type == v->type) 633 if(a->reg == v->reg) 634 return 1; 635 return 0; 636 } 637 638 /* 639 * either direct or indirect 640 */ 641 int 642 copyau(Adr *a, Adr *v) 643 { 644 645 if(copyas(a, v)) 646 return 1; 647 if(v->type == D_REG) 648 if(a->type == D_OREG) 649 if(v->reg == a->reg) 650 return 1; 651 return 0; 652 } 653 654 int 655 copyau1(Prog *p, Adr *v) 656 { 657 658 if(regtyp(v)) 659 if(p->from.type == v->type || p->to.type == v->type) 660 if(p->reg == v->reg) { 661 if(a2type(p) != v->type) 662 print("botch a2type %P\n", p); 663 return 1; 664 } 665 return 0; 666 } 667 668 /* 669 * substitute s for v in a 670 * return failure to substitute 671 */ 672 int 673 copysub(Adr *a, Adr *v, Adr *s, int f) 674 { 675 676 if(f) 677 if(copyau(a, v)) 678 a->reg = s->reg; 679 return 0; 680 } 681 682 int 683 copysub1(Prog *p1, Adr *v, Adr *s, int f) 684 { 685 686 if(f) 687 if(copyau1(p1, v)) 688 p1->reg = s->reg; 689 return 0; 690 } 691