1 #include "gc.h" 2 3 void 4 peep(void) 5 { 6 Reg *r, *r1, *r2; 7 Prog *p; 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 == AMOVL) 46 if(regtyp(&p->to)) 47 if(regtyp(&p->from)) { 48 if(copyprop(r)) { 49 excise(r); 50 t++; 51 } 52 if(subprop(r) && copyprop(r)) { 53 excise(r); 54 t++; 55 } 56 } 57 } 58 if(t) 59 goto loop1; 60 } 61 62 void 63 excise(Reg *r) 64 { 65 Prog *p; 66 67 p = r->prog; 68 p->as = ANOP; 69 p->from = zprog.from; 70 p->to = zprog.to; 71 } 72 73 Reg* 74 uniqp(Reg *r) 75 { 76 Reg *r1; 77 78 r1 = r->p1; 79 if(r1 == R) { 80 r1 = r->p2; 81 if(r1 == R || r1->p2link != R) 82 return R; 83 } else 84 if(r->p2 != R) 85 return R; 86 return r1; 87 } 88 89 Reg* 90 uniqs(Reg *r) 91 { 92 Reg *r1; 93 94 r1 = r->s1; 95 if(r1 == R) { 96 r1 = r->s2; 97 if(r1 == R) 98 return R; 99 } else 100 if(r->s2 != R) 101 return R; 102 return r1; 103 } 104 105 int 106 regtyp(Adr *a) 107 { 108 int t; 109 110 t = a->type; 111 if(t >= D_AX && t <= D_DI) 112 return 1; 113 return 0; 114 } 115 116 /* 117 * the idea is to substitute 118 * one register for another 119 * from one MOV to another 120 * MOV a, R0 121 * ADD b, R0 / no use of R1 122 * MOV R0, R1 123 * would be converted to 124 * MOV a, R1 125 * ADD b, R1 126 * MOV R1, R0 127 * hopefully, then the former or latter MOV 128 * will be eliminated by copy propagation. 129 */ 130 int 131 subprop(Reg *r0) 132 { 133 Prog *p; 134 Adr *v1, *v2; 135 Reg *r; 136 int t; 137 138 p = r0->prog; 139 v1 = &p->from; 140 if(!regtyp(v1)) 141 return 0; 142 v2 = &p->to; 143 if(!regtyp(v2)) 144 return 0; 145 for(r=uniqp(r0); r!=R; r=uniqp(r)) { 146 if(uniqs(r) == R) 147 break; 148 p = r->prog; 149 switch(p->as) { 150 case ACALL: 151 return 0; 152 153 case ADIVB: 154 case ADIVL: 155 case ADIVW: 156 case AIDIVB: 157 case AIDIVL: 158 case AIDIVW: 159 case AIMULB: 160 case AIMULL: 161 case AIMULW: 162 case AMULB: 163 case AMULL: 164 case AMULW: 165 166 case ASHLB: 167 case ASHLL: 168 case ASHLW: 169 case ASHRB: 170 case ASHRL: 171 case ASHRW: 172 173 case AREP: 174 case AREPN: 175 176 case ACWD: 177 case ACDQ: 178 179 case AMOVSL: 180 case AFSTSW: 181 return 0; 182 183 case AMOVL: 184 if(p->to.type == v1->type) 185 goto gotit; 186 break; 187 } 188 if(copyau(&p->from, v2) || 189 copyau(&p->to, v2)) 190 break; 191 if(copysub(&p->from, v1, v2, 0) || 192 copysub(&p->to, v1, v2, 0)) 193 break; 194 } 195 return 0; 196 197 gotit: 198 copysub(&p->to, v1, v2, 1); 199 if(debug['P']) { 200 print("gotit: %D->%D\n%P", v1, v2, r->prog); 201 if(p->from.type == v2->type) 202 print(" excise"); 203 print("\n"); 204 } 205 for(r=uniqs(r); r!=r0; r=uniqs(r)) { 206 p = r->prog; 207 copysub(&p->from, v1, v2, 1); 208 copysub(&p->to, v1, v2, 1); 209 if(debug['P']) 210 print("%P\n", r->prog); 211 } 212 t = v1->type; 213 v1->type = v2->type; 214 v2->type = t; 215 if(debug['P']) 216 print("%P last\n", r->prog); 217 return 1; 218 } 219 220 /* 221 * The idea is to remove redundant copies. 222 * v1->v2 F=0 223 * (use v2 s/v2/v1/)* 224 * set v1 F=1 225 * use v2 return fail 226 * ----------------- 227 * v1->v2 F=0 228 * (use v2 s/v2/v1/)* 229 * set v1 F=1 230 * set v2 return success 231 */ 232 int 233 copyprop(Reg *r0) 234 { 235 Prog *p; 236 Adr *v1, *v2; 237 Reg *r; 238 239 p = r0->prog; 240 v1 = &p->from; 241 v2 = &p->to; 242 if(copyas(v1, v2)) 243 return 1; 244 for(r=firstr; r!=R; r=r->link) 245 r->active = 0; 246 return copy1(v1, v2, r0->s1, 0); 247 } 248 249 int 250 copy1(Adr *v1, Adr *v2, Reg *r, int f) 251 { 252 int t; 253 Prog *p; 254 255 if(r->active) { 256 if(debug['P']) 257 print("act set; return 1\n"); 258 return 1; 259 } 260 r->active = 1; 261 if(debug['P']) 262 print("copy %D->%D f=%d\n", v1, v2, f); 263 for(; r != R; r = r->s1) { 264 p = r->prog; 265 if(debug['P']) 266 print("%P", p); 267 if(!f && uniqp(r) == R) { 268 f = 1; 269 if(debug['P']) 270 print("; merge; f=%d", f); 271 } 272 t = copyu(p, v2, A); 273 switch(t) { 274 case 2: /* rar, cant split */ 275 if(debug['P']) 276 print("; %D rar; return 0\n", v2); 277 return 0; 278 279 case 3: /* set */ 280 if(debug['P']) 281 print("; %D set; return 1\n", v2); 282 return 1; 283 284 case 1: /* used, substitute */ 285 case 4: /* use and set */ 286 if(f) { 287 if(!debug['P']) 288 return 0; 289 if(t == 4) 290 print("; %D used+set and f=%d; return 0\n", v2, f); 291 else 292 print("; %D used and f=%d; return 0\n", v2, f); 293 return 0; 294 } 295 if(copyu(p, v2, v1)) { 296 if(debug['P']) 297 print("; sub fail; return 0\n"); 298 return 0; 299 } 300 if(debug['P']) 301 print("; sub %D/%D", v2, v1); 302 if(t == 4) { 303 if(debug['P']) 304 print("; %D used+set; return 1\n", v2); 305 return 1; 306 } 307 break; 308 } 309 if(!f) { 310 t = copyu(p, v1, A); 311 if(!f && (t == 2 || t == 3 || t == 4)) { 312 f = 1; 313 if(debug['P']) 314 print("; %D set and !f; f=%d", v1, f); 315 } 316 } 317 if(debug['P']) 318 print("\n"); 319 if(r->s2) 320 if(!copy1(v1, v2, r->s2, f)) 321 return 0; 322 } 323 return 1; 324 } 325 326 /* 327 * return 328 * 1 if v only used (and substitute), 329 * 2 if read-alter-rewrite 330 * 3 if set 331 * 4 if set and used 332 * 0 otherwise (not touched) 333 */ 334 int 335 copyu(Prog *p, Adr *v, Adr *s) 336 { 337 338 switch(p->as) { 339 340 default: 341 if(debug['P']) 342 print("unknown op %A\n", p->as); 343 return 2; 344 345 case ALEAL: /* lhs addr, rhs store */ 346 if(copyas(&p->from, v)) 347 return 2; 348 349 350 case ANOP: /* rhs store */ 351 case AMOVL: 352 case AMOVBLSX: 353 case AMOVBLZX: 354 case AMOVWLSX: 355 case AMOVWLZX: 356 if(copyas(&p->to, v)) { 357 if(s != A) 358 return copysub(&p->from, v, s, 1); 359 if(copyau(&p->from, v)) 360 return 4; 361 return 3; 362 } 363 goto caseread; 364 365 case AROLB: 366 case AROLL: 367 case AROLW: 368 case ARORB: 369 case ARORL: 370 case ARORW: 371 case ASALB: 372 case ASALL: 373 case ASALW: 374 case ASARB: 375 case ASARL: 376 case ASARW: 377 case ASHLB: 378 case ASHLL: 379 case ASHLW: 380 case ASHRB: 381 case ASHRL: 382 case ASHRW: 383 if(copyas(&p->to, v)) 384 return 2; 385 if(copyas(&p->from, v)) 386 if(p->from.type == D_CX) 387 return 2; 388 goto caseread; 389 390 case AADDB: /* rhs rar */ 391 case AADDL: 392 case AADDW: 393 case AANDB: 394 case AANDL: 395 case AANDW: 396 case ASUBB: 397 case ASUBL: 398 case ASUBW: 399 case AORB: 400 case AORL: 401 case AORW: 402 case AXORB: 403 case AXORL: 404 case AXORW: 405 case AMOVB: 406 case AMOVW: 407 408 case AFMOVB: 409 case AFMOVBP: 410 case AFMOVD: 411 case AFMOVDP: 412 case AFMOVF: 413 case AFMOVFP: 414 case AFMOVL: 415 case AFMOVLP: 416 case AFMOVV: 417 case AFMOVVP: 418 case AFMOVW: 419 case AFMOVWP: 420 case AFMOVX: 421 case AFMOVXP: 422 case AFADDDP: 423 case AFADDW: 424 case AFADDL: 425 case AFADDF: 426 case AFADDD: 427 case AFMULDP: 428 case AFMULW: 429 case AFMULL: 430 case AFMULF: 431 case AFMULD: 432 case AFSUBDP: 433 case AFSUBW: 434 case AFSUBL: 435 case AFSUBF: 436 case AFSUBD: 437 case AFSUBRDP: 438 case AFSUBRW: 439 case AFSUBRL: 440 case AFSUBRF: 441 case AFSUBRD: 442 case AFDIVDP: 443 case AFDIVW: 444 case AFDIVL: 445 case AFDIVF: 446 case AFDIVD: 447 case AFDIVRDP: 448 case AFDIVRW: 449 case AFDIVRL: 450 case AFDIVRF: 451 case AFDIVRD: 452 if(copyas(&p->to, v)) 453 return 2; 454 goto caseread; 455 456 case ACMPL: /* read only */ 457 case ACMPW: 458 case ACMPB: 459 460 case AFCOMB: 461 case AFCOMBP: 462 case AFCOMD: 463 case AFCOMDP: 464 case AFCOMDPP: 465 case AFCOMF: 466 case AFCOMFP: 467 case AFCOML: 468 case AFCOMLP: 469 case AFCOMW: 470 case AFCOMWP: 471 case AFUCOM: 472 case AFUCOMP: 473 case AFUCOMPP: 474 caseread: 475 if(s != A) { 476 if(copysub(&p->from, v, s, 1)) 477 return 1; 478 return copysub(&p->to, v, s, 1); 479 } 480 if(copyau(&p->from, v)) 481 return 1; 482 if(copyau(&p->to, v)) 483 return 1; 484 break; 485 486 case AJGE: /* no reference */ 487 case AJNE: 488 case AJLE: 489 case AJEQ: 490 case AJHI: 491 case AJLS: 492 case AJMI: 493 case AJPL: 494 case AJGT: 495 case AJLT: 496 case AJCC: 497 case AJCS: 498 499 case AADJSP: 500 case AFLDZ: 501 case AWAIT: 502 break; 503 504 case ADIVB: 505 case ADIVL: 506 case ADIVW: 507 case AIDIVB: 508 case AIDIVL: 509 case AIDIVW: 510 case AIMULB: 511 case AIMULL: 512 case AIMULW: 513 case AMULB: 514 case AMULL: 515 case AMULW: 516 517 case ACWD: 518 case ACDQ: 519 if(v->type == D_AX || v->type == D_DX) 520 return 2; 521 goto caseread; 522 523 case AMOVSL: 524 case AREP: 525 case AREPN: 526 if(v->type == D_CX || v->type == D_DI || v->type == D_SI) 527 return 2; 528 goto caseread; 529 530 case AFSTSW: 531 if(v->type == D_AX) 532 return 2; 533 goto caseread; 534 535 case AJMP: /* funny */ 536 if(s != A) { 537 if(copysub(&p->to, v, s, 1)) 538 return 1; 539 return 0; 540 } 541 if(copyau(&p->to, v)) 542 return 1; 543 return 0; 544 545 case ARET: /* funny */ 546 if(v->type == REGRET) 547 return 2; 548 if(s != A) 549 return 1; 550 return 3; 551 552 case ACALL: /* funny */ 553 if(REGARG && v->type == REGARG) 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 return 0; 566 } 567 568 /* 569 * direct reference, 570 * could be set/use depending on 571 * semantics 572 */ 573 int 574 copyas(Adr *a, Adr *v) 575 { 576 if(a->type != v->type) 577 return 0; 578 if(regtyp(v)) 579 return 1; 580 if(v->type == D_AUTO || v->type == D_PARAM) 581 if(v->offset == a->offset) 582 return 1; 583 return 0; 584 } 585 586 /* 587 * either direct or indirect 588 */ 589 int 590 copyau(Adr *a, Adr *v) 591 { 592 593 if(copyas(a, v)) 594 return 1; 595 if(regtyp(v)) { 596 if(a->type-D_INDIR == v->type) 597 return 1; 598 if(a->index == v->type) 599 return 1; 600 } 601 return 0; 602 } 603 604 /* 605 * substitute s for v in a 606 * return failure to substitute 607 */ 608 int 609 copysub(Adr *a, Adr *v, Adr *s, int f) 610 { 611 int t; 612 613 if(copyas(a, v)) { 614 t = s->type; 615 if(t >= D_AX && t <= D_DI) { 616 if(f) 617 a->type = t; 618 } 619 return 0; 620 } 621 if(regtyp(v)) { 622 t = v->type; 623 if(a->type == t+D_INDIR) { 624 if(f) 625 a->type = s->type+D_INDIR; 626 return 0; 627 } 628 if(a->index == t) { 629 if(f) 630 a->index = s->type; 631 return 0; 632 } 633 return 0; 634 } 635 return 0; 636 } 637