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 == AMOV) 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_R0 && t <= D_R0+31) 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 ABAL: 151 return 0; 152 153 case AADDI: /* 3-op */ 154 case AADDO: 155 case AAND: 156 case ASUBI: 157 case ASUBO: 158 case AOR: 159 case AXOR: 160 case ASHLI: 161 case ASHRI: 162 case ASHLO: 163 case ASHRO: 164 case AMULI: 165 case AMULO: 166 case ADIVI: 167 case ADIVO: 168 case AREMI: 169 case AREMO: 170 if(p->type != D_NONE) 171 return 0; 172 break; /* botch */ 173 if(p->to.type == v1->type) { 174 if(p->type == D_NONE) 175 p->type = p->to.type; 176 goto gotit; 177 } 178 break; 179 180 case AMOV: 181 if(p->to.type == v1->type) 182 goto gotit; 183 break; 184 } 185 if(copyau(&p->from, v2) || 186 copyau(&p->to, v2)) 187 break; 188 if(copysub(&p->from, v1, v2, 0) || 189 copysub(&p->to, v1, v2, 0)) 190 break; 191 } 192 return 0; 193 194 gotit: 195 copysub(&p->to, v1, v2, 1); 196 if(debug['P']) { 197 print("gotit: %D->%D\n%P", v1, v2, r->prog); 198 if(p->from.type == v2->type) 199 print(" excise"); 200 print("\n"); 201 } 202 for(r=uniqs(r); r!=r0; r=uniqs(r)) { 203 p = r->prog; 204 copysub(&p->from, v1, v2, 1); 205 copysub(&p->to, v1, v2, 1); 206 if(debug['P']) 207 print("%P\n", r->prog); 208 } 209 t = v1->type; 210 v1->type = v2->type; 211 v2->type = t; 212 if(debug['P']) 213 print("%P last\n", r->prog); 214 return 1; 215 } 216 217 /* 218 * The idea is to remove redundant copies. 219 * v1->v2 F=0 220 * (use v2 s/v2/v1/)* 221 * set v1 F=1 222 * use v2 return fail 223 * ----------------- 224 * v1->v2 F=0 225 * (use v2 s/v2/v1/)* 226 * set v1 F=1 227 * set v2 return success 228 */ 229 int 230 copyprop(Reg *r0) 231 { 232 Prog *p; 233 Adr *v1, *v2; 234 Reg *r; 235 236 p = r0->prog; 237 v1 = &p->from; 238 v2 = &p->to; 239 if(copyas(v1, v2)) 240 return 1; 241 for(r=firstr; r!=R; r=r->link) 242 r->active = 0; 243 return copy1(v1, v2, r0->s1, 0); 244 } 245 246 int 247 copy1(Adr *v1, Adr *v2, Reg *r, int f) 248 { 249 int t; 250 Prog *p; 251 252 if(r->active) { 253 if(debug['P']) 254 print("act set; return 1\n"); 255 return 1; 256 } 257 r->active = 1; 258 if(debug['P']) 259 print("copy %D->%D f=%d\n", v1, v2, f); 260 for(; r != R; r = r->s1) { 261 p = r->prog; 262 if(debug['P']) 263 print("%P", p); 264 if(!f && uniqp(r) == R) { 265 f = 1; 266 if(debug['P']) 267 print("; merge; f=%d", f); 268 } 269 t = copyu(p, v2, A); 270 switch(t) { 271 case 2: /* rar, cant split */ 272 if(debug['P']) 273 print("; %D rar; return 0\n", v2); 274 return 0; 275 276 case 3: /* set */ 277 if(debug['P']) 278 print("; %D set; return 1\n", v2); 279 return 1; 280 281 case 1: /* used, substitute */ 282 case 4: /* use and set */ 283 if(f) { 284 if(!debug['P']) 285 return 0; 286 if(t == 4) 287 print("; %D used+set and f=%d; return 0\n", v2, f); 288 else 289 print("; %D used and f=%d; return 0\n", v2, f); 290 return 0; 291 } 292 if(copyu(p, v2, v1)) { 293 if(debug['P']) 294 print("; sub fail; return 0\n"); 295 return 0; 296 } 297 if(debug['P']) 298 print("; sub %D/%D", v2, v1); 299 if(t == 4) { 300 if(debug['P']) 301 print("; %D used+set; return 1\n", v2); 302 return 1; 303 } 304 break; 305 } 306 if(!f) { 307 t = copyu(p, v1, A); 308 if(!f && (t == 2 || t == 3 || t == 4)) { 309 f = 1; 310 if(debug['P']) 311 print("; %D set and !f; f=%d", v1, f); 312 } 313 } 314 if(debug['P']) 315 print("\n"); 316 if(r->s2) 317 if(!copy1(v1, v2, r->s2, f)) 318 return 0; 319 } 320 return 1; 321 } 322 323 /* 324 * return 325 * 1 if v only used (and substitute), 326 * 2 if read-alter-rewrite 327 * 3 if set 328 * 4 if set and used 329 * 0 otherwise (not touched) 330 */ 331 copyu(Prog *p, Adr *v, Adr *s) 332 { 333 334 switch(p->as) { 335 336 default: 337 print("default -- rar %P\n", p); 338 case ASHLI: 339 case ASHRI: 340 case ASHLO: 341 case ASHRO: 342 case AMULI: 343 case AMULO: 344 case ADIVI: 345 case ADIVO: 346 case AREMI: 347 case AREMO: 348 if(debug['P']) 349 print("unknown op %A\n", p->as); 350 return 2; 351 352 case AMOVA: /* lhs addr, rhs store */ 353 if(copyas(&p->from, v)) 354 return 2; 355 356 357 case ANOP: /* rhs store */ 358 case AMOV: 359 case AMOVOB: 360 case AMOVIB: 361 case AMOVOS: 362 case AMOVIS: 363 if(copyas(&p->to, v)) { 364 if(s != A) 365 return copysub(&p->from, v, s, 1); 366 if(copyau(&p->from, v)) 367 return 4; 368 return 3; 369 } 370 goto caseread; 371 372 373 case AADDI: /* rhs rar */ 374 case AADDO: 375 case AAND: 376 case ASUBI: 377 case ASUBO: 378 case AOR: 379 case AXOR: 380 if(copyas(&p->to, v)) 381 return 2; 382 goto caseread; 383 384 case ACMPI: /* read only */ 385 case ACMPO: 386 387 caseread: 388 if(p->type != D_NONE) 389 return 2; /* botch */ 390 if(s != A) { 391 if(copysub(&p->from, v, s, 1)) 392 return 1; 393 return copysub(&p->to, v, s, 1); 394 } 395 if(copyau(&p->from, v)) 396 return 1; 397 if(copyau(&p->to, v)) 398 return 1; 399 break; 400 401 case AB: /* no reference */ 402 case ABNE: 403 case ABE: 404 case ABL: 405 case ABLE: 406 case ABG: 407 case ABGE: 408 break; 409 410 case ARTS: /* funny */ 411 case ABAL: /* funny */ 412 if(v->type == REGRET) 413 return 2; 414 415 if(s != A) { 416 if(s->type == REGRET) 417 return 2; 418 if(copysub(&p->to, v, s, 1)) 419 return 1; 420 return 0; 421 } 422 if(copyau(&p->to, v)) 423 return 4; 424 return 3; 425 } 426 return 0; 427 } 428 429 /* 430 * direct reference, 431 * could be set/use depending on 432 * semantics 433 */ 434 int 435 copyas(Adr *a, Adr *v) 436 { 437 if(a->type != v->type) 438 return 0; 439 if(regtyp(v)) 440 return 1; 441 if(v->type == D_AUTO || v->type == D_PARAM) 442 if(v->offset == a->offset) 443 return 1; 444 return 0; 445 } 446 447 int 448 copyas1(Prog *p, Adr *v) 449 { 450 if(p->type != v->type) 451 return 0; 452 if(regtyp(v)) 453 return 1; 454 return 0; 455 } 456 457 /* 458 * either direct or indirect 459 */ 460 int 461 copyau(Adr *a, Adr *v) 462 { 463 464 if(copyas(a, v)) 465 return 1; 466 if(regtyp(v)) { 467 if(a->type-D_INDIR == v->type) 468 return 1; 469 if(a->index == v->type) 470 return 1; 471 } 472 return 0; 473 } 474 475 /* 476 * substitute s for v in a 477 * return failure to substitute 478 */ 479 int 480 copysub(Adr *a, Adr *v, Adr *s, int f) 481 { 482 int t; 483 484 if(copyas(a, v)) { 485 t = s->type; 486 if(t >= D_R0 && t <= D_R0+31) { 487 if(f) 488 a->type = t; 489 } 490 return 0; 491 } 492 if(regtyp(v)) { 493 t = v->type; 494 if(a->type == t+D_INDIR) { 495 if(f) 496 a->type = s->type+D_INDIR; 497 return 0; 498 } 499 if(a->index == t) { 500 if(f) 501 a->index = s->type; 502 return 0; 503 } 504 return 0; 505 } 506 return 0; 507 } 508 509 /* 510 * substitute s for v in p 511 * return failure to substitute 512 */ 513 int 514 copysub1(Prog *p, Adr *v, Adr *s, int f) 515 { 516 int t; 517 518 if(copyas1(p, v)) { 519 t = s->type; 520 if(t >= D_R0 && t <= D_R0+31) { 521 if(f) 522 p->type = t; 523 } 524 return 0; 525 } 526 return 0; 527 } 528