1 /* Id: optim2.c,v 1.78 2010/05/24 05:11:07 ragge Exp */ 2 /* $NetBSD: optim2.c,v 1.1.1.3 2010/06/03 18:57:56 plunky Exp $ */ 3 /* 4 * Copyright (c) 2004 Anders Magnusson (ragge@ludd.luth.se). 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. The name of the author may not be used to endorse or promote products 16 * derived from this software without specific prior written permission 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 */ 29 30 #include "pass2.h" 31 32 #include <string.h> 33 #include <stdlib.h> 34 35 #ifndef MIN 36 #define MIN(a,b) (((a)<(b))?(a):(b)) 37 #endif 38 39 #ifndef MAX 40 #define MAX(a,b) (((a) > (b)) ? (a) : (b)) 41 #endif 42 43 #define BDEBUG(x) if (b2debug) printf x 44 45 #define mktemp(n, t) mklnode(TEMP, 0, n, t) 46 47 /* main switch for new things not yet ready for all-day use */ 48 /* #define ENABLE_NEW */ 49 50 51 static int dfsnum; 52 53 void saveip(struct interpass *ip); 54 void deljumps(struct p2env *); 55 void optdump(struct interpass *ip); 56 void printip(struct interpass *pole); 57 58 static struct varinfo defsites; 59 struct interpass *storesave; 60 61 void bblocks_build(struct p2env *); 62 void cfg_build(struct p2env *); 63 void cfg_dfs(struct basicblock *bb, unsigned int parent, 64 struct bblockinfo *bbinfo); 65 void dominators(struct p2env *); 66 struct basicblock * 67 ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo); 68 void link(struct basicblock *parent, struct basicblock *child); 69 void computeDF(struct p2env *, struct basicblock *bblock); 70 void printDF(struct p2env *p2e); 71 void findTemps(struct interpass *ip); 72 void placePhiFunctions(struct p2env *); 73 void renamevar(struct p2env *p2e,struct basicblock *bblock); 74 void removephi(struct p2env *p2e); 75 void remunreach(struct p2env *); 76 static void liveanal(struct p2env *p2e); 77 static void printip2(struct interpass *); 78 79 /* create "proper" basic blocks, add labels where needed (so bblocks have labels) */ 80 /* run before bb generate */ 81 static void add_labels(struct p2env*) ; 82 83 /* Perform trace scheduling, try to get rid of gotos as much as possible */ 84 void TraceSchedule(struct p2env*) ; 85 86 #ifdef ENABLE_NEW 87 static void do_cse(struct p2env* p2e) ; 88 #endif 89 90 /* Walk the complete set, performing a function on each node. 91 * if type is given, apply function on only that type */ 92 void WalkAll(struct p2env* p2e, void (*f) (NODE*, void*), void* arg, int type) ; 93 94 void BBLiveDead(struct basicblock* bblock, int what, unsigned int variable) ; 95 96 /* Fill the live/dead code */ 97 void LiveDead(struct p2env* p2e, int what, unsigned int variable) ; 98 99 #ifdef PCC_DEBUG 100 void printflowdiagram(struct p2env *, char *); 101 #endif 102 103 void 104 optimize(struct p2env *p2e) 105 { 106 struct interpass *ipole = &p2e->ipole; 107 108 if (b2debug) { 109 printf("initial links\n"); 110 printip(ipole); 111 } 112 113 if (xdeljumps) 114 deljumps(p2e); /* Delete redundant jumps and dead code */ 115 116 if (xssaflag) 117 add_labels(p2e) ; 118 #ifdef ENABLE_NEW 119 do_cse(p2e); 120 #endif 121 122 #ifdef PCC_DEBUG 123 if (b2debug) { 124 printf("links after deljumps\n"); 125 printip(ipole); 126 } 127 #endif 128 if (xssaflag || xtemps) { 129 bblocks_build(p2e); 130 BDEBUG(("Calling cfg_build\n")); 131 cfg_build(p2e); 132 133 #ifdef PCC_DEBUG 134 printflowdiagram(p2e, "first"); 135 #endif 136 } 137 if (xssaflag) { 138 BDEBUG(("Calling liveanal\n")); 139 liveanal(p2e); 140 BDEBUG(("Calling dominators\n")); 141 dominators(p2e); 142 BDEBUG(("Calling computeDF\n")); 143 computeDF(p2e, DLIST_NEXT(&p2e->bblocks, bbelem)); 144 145 if (b2debug) { 146 printDF(p2e); 147 } 148 149 BDEBUG(("Calling placePhiFunctions\n")); 150 151 placePhiFunctions(p2e); 152 153 BDEBUG(("Calling renamevar\n")); 154 155 renamevar(p2e,DLIST_NEXT(&p2e->bblocks, bbelem)); 156 157 BDEBUG(("Calling removephi\n")); 158 159 #ifdef PCC_DEBUG 160 printflowdiagram(p2e, "ssa"); 161 #endif 162 163 removephi(p2e); 164 165 BDEBUG(("Calling remunreach\n")); 166 /* remunreach(p2e); */ 167 168 /* 169 * Recalculate basic blocks and cfg that was destroyed 170 * by removephi 171 */ 172 /* first, clean up all what deljumps should have done, and more */ 173 174 /* TODO: add the basic blocks done by the ssa code by hand. 175 * The trace scheduler should not change the order in 176 * which blocks are executed or what data is calculated. 177 * Thus, the BBlock order should remain correct. 178 */ 179 180 #ifdef ENABLE_NEW 181 bblocks_build(p2e, &labinfo, &bbinfo); 182 BDEBUG(("Calling cfg_build\n")); 183 cfg_build(p2e, &labinfo); 184 185 TraceSchedule(p2e); 186 #ifdef PCC_DEBUG 187 printflowdiagram(p2e, &labinfo, &bbinfo,"sched_trace"); 188 189 if (b2debug) { 190 printf("after tracesched\n"); 191 printip(ipole); 192 fflush(stdout) ; 193 } 194 #endif 195 #endif 196 197 /* Now, clean up the gotos we do not need any longer */ 198 if (xdeljumps) 199 deljumps(p2e); /* Delete redundant jumps and dead code */ 200 201 bblocks_build(p2e); 202 BDEBUG(("Calling cfg_build\n")); 203 cfg_build(p2e); 204 205 #ifdef PCC_DEBUG 206 printflowdiagram(p2e, "no_phi"); 207 208 if (b2debug) { 209 printf("new tree\n"); 210 printip(ipole); 211 } 212 #endif 213 } 214 215 #ifdef PCC_DEBUG 216 { 217 int i; 218 for (i = NIPPREGS; i--; ) 219 if (p2e->epp->ipp_regs[i] != 0) 220 comperr("register error"); 221 } 222 #endif 223 224 myoptim(ipole); 225 } 226 227 /* 228 * Delete unused labels, excess of labels, gotos to gotos. 229 * This routine can be made much more efficient. 230 * 231 * Layout of the statement list here (_must_ look this way!): 232 * PROLOG 233 * LABEL - states beginning of function argument moves 234 * ...code to save/move arguments 235 * LABEL - states beginning of execution code 236 * ...code + labels in function in function 237 * EPILOG 238 * 239 * This version of deljumps is based on the c2 implementation 240 * that were included in 2BSD. 241 */ 242 #define LABEL 1 243 #define JBR 2 244 #define CBR 3 245 #define STMT 4 246 #define EROU 5 247 struct dlnod { 248 int op; 249 struct interpass *dlip; 250 struct dlnod *forw; 251 struct dlnod *back; 252 struct dlnod *ref; 253 int labno; 254 int refc; 255 }; 256 257 #ifdef DLJDEBUG 258 static void 259 dumplink(struct dlnod *dl) 260 { 261 printf("dumplink %p\n", dl); 262 for (; dl; dl = dl->forw) { 263 if (dl->op == STMT) { 264 printf("STMT(%p)\n", dl); 265 fwalk(dl->dlip->ip_node, e2print, 0); 266 } else if (dl->op == EROU) { 267 printf("EROU(%p)\n", dl); 268 } else { 269 static char *str[] = { 0, "LABEL", "JBR", "CBR" }; 270 printf("%s(%p) %d refc %d ref %p\n", str[dl->op], 271 dl, dl->labno, dl->refc, dl->ref); 272 } 273 } 274 printf("end dumplink\n"); 275 } 276 #endif 277 278 /* 279 * Create the linked list that we can work on. 280 */ 281 static void 282 listsetup(struct interpass *ipole, struct dlnod *dl) 283 { 284 struct interpass *ip = DLIST_NEXT(ipole, qelem); 285 struct interpass *nip; 286 struct dlnod *p, *lastp; 287 NODE *q; 288 289 lastp = dl; 290 while (ip->type != IP_DEFLAB) 291 ip = DLIST_NEXT(ip,qelem); 292 ip = DLIST_NEXT(ip,qelem); 293 while (ip->type != IP_DEFLAB) 294 ip = DLIST_NEXT(ip,qelem); 295 /* Now ip is at the beginning */ 296 for (;;) { 297 ip = DLIST_NEXT(ip,qelem); 298 if (ip == ipole) 299 break; 300 p = tmpalloc(sizeof(struct dlnod)); 301 p->labno = 0; 302 p->dlip = ip; 303 switch (ip->type) { 304 case IP_DEFLAB: 305 p->op = LABEL; 306 p->labno = ip->ip_lbl; 307 break; 308 309 case IP_NODE: 310 q = ip->ip_node; 311 switch (q->n_op) { 312 case GOTO: 313 p->op = JBR; 314 p->labno = q->n_left->n_lval; 315 break; 316 case CBRANCH: 317 p->op = CBR; 318 p->labno = q->n_right->n_lval; 319 break; 320 case ASSIGN: 321 /* remove ASSIGN to self for regs */ 322 if (q->n_left->n_op == REG && 323 q->n_right->n_op == REG && 324 regno(q->n_left) == regno(q->n_right)) { 325 nip = DLIST_PREV(ip, qelem); 326 tfree(q); 327 DLIST_REMOVE(ip, qelem); 328 ip = nip; 329 continue; 330 } 331 /* FALLTHROUGH */ 332 default: 333 p->op = STMT; 334 break; 335 } 336 break; 337 338 case IP_ASM: 339 p->op = STMT; 340 break; 341 342 case IP_EPILOG: 343 p->op = EROU; 344 break; 345 346 default: 347 comperr("listsetup: bad ip node %d", ip->type); 348 } 349 p->forw = 0; 350 p->back = lastp; 351 lastp->forw = p; 352 lastp = p; 353 p->ref = 0; 354 } 355 } 356 357 static struct dlnod * 358 nonlab(struct dlnod *p) 359 { 360 while (p && p->op==LABEL) 361 p = p->forw; 362 return(p); 363 } 364 365 static void 366 iprem(struct dlnod *p) 367 { 368 if (p->dlip->type == IP_NODE) 369 tfree(p->dlip->ip_node); 370 DLIST_REMOVE(p->dlip, qelem); 371 } 372 373 static void 374 decref(struct dlnod *p) 375 { 376 if (--p->refc <= 0) { 377 iprem(p); 378 p->back->forw = p->forw; 379 p->forw->back = p->back; 380 } 381 } 382 383 static void 384 setlab(struct dlnod *p, int labno) 385 { 386 p->labno = labno; 387 if (p->op == JBR) 388 p->dlip->ip_node->n_left->n_lval = labno; 389 else if (p->op == CBR) { 390 p->dlip->ip_node->n_right->n_lval = labno; 391 p->dlip->ip_node->n_left->n_label = labno; 392 } else 393 comperr("setlab bad op %d", p->op); 394 } 395 396 /* 397 * Label reference counting and removal of unused labels. 398 */ 399 #define LABHS 127 400 static void 401 refcount(struct p2env *p2e, struct dlnod *dl) 402 { 403 struct dlnod *p, *lp; 404 struct dlnod *labhash[LABHS]; 405 struct dlnod **hp, *tp; 406 407 /* Clear label hash */ 408 for (hp = labhash; hp < &labhash[LABHS];) 409 *hp++ = 0; 410 /* Enter labels into hash. Later overwrites earlier */ 411 for (p = dl->forw; p!=0; p = p->forw) 412 if (p->op==LABEL) { 413 labhash[p->labno % LABHS] = p; 414 p->refc = 0; 415 } 416 417 /* search for jumps to labels and fill in reference */ 418 for (p = dl->forw; p!=0; p = p->forw) { 419 if (p->op==JBR || p->op==CBR) { 420 p->ref = 0; 421 lp = labhash[p->labno % LABHS]; 422 if (lp==0 || p->labno!=lp->labno) 423 for (lp = dl->forw; lp!=0; lp = lp->forw) { 424 if (lp->op==LABEL && p->labno==lp->labno) 425 break; 426 } 427 if (lp) { 428 tp = nonlab(lp)->back; 429 if (tp!=lp) { 430 setlab(p, tp->labno); 431 lp = tp; 432 } 433 p->ref = lp; 434 lp->refc++; 435 } 436 } 437 } 438 for (p = dl->forw; p!=0; p = p->forw) 439 if (p->op==LABEL && p->refc==0 && (lp = nonlab(p))->op) 440 decref(p); 441 } 442 443 static int nchange; 444 445 static struct dlnod * 446 codemove(struct dlnod *p) 447 { 448 struct dlnod *p1, *p2, *p3; 449 #ifdef notyet 450 struct dlnod *t, *tl; 451 int n; 452 #endif 453 454 p1 = p; 455 if (p1->op!=JBR || (p2 = p1->ref)==0) 456 return(p1); 457 while (p2->op == LABEL) 458 if ((p2 = p2->back) == 0) 459 return(p1); 460 if (p2->op!=JBR) 461 goto ivloop; 462 if (p1==p2) 463 return(p1); 464 p2 = p2->forw; 465 p3 = p1->ref; 466 while (p3) { 467 if (p3->op==JBR) { 468 if (p1==p3 || p1->forw==p3 || p1->back==p3) 469 return(p1); 470 nchange++; 471 p1->back->forw = p2; 472 p1->dlip->qelem.q_back->qelem.q_forw = p2->dlip; 473 474 p1->forw->back = p3; 475 p1->dlip->qelem.q_forw->qelem.q_back = p3->dlip; 476 477 478 p2->back->forw = p3->forw; 479 p2->dlip->qelem.q_back->qelem.q_forw = p3->forw->dlip; 480 481 p3->forw->back = p2->back; 482 p3->dlip->qelem.q_forw->qelem.q_back = p2->back->dlip; 483 484 p2->back = p1->back; 485 p2->dlip->qelem.q_back = p1->dlip->qelem.q_back; 486 487 p3->forw = p1->forw; 488 p3->dlip->qelem.q_forw = p1->forw->dlip; 489 490 decref(p1->ref); 491 if (p1->dlip->type == IP_NODE) 492 tfree(p1->dlip->ip_node); 493 494 return(p2); 495 } else 496 p3 = p3->forw; 497 } 498 return(p1); 499 500 ivloop: 501 if (p1->forw->op!=LABEL) 502 return(p1); 503 return(p1); 504 505 #ifdef notyet 506 p3 = p2 = p2->forw; 507 n = 16; 508 do { 509 if ((p3 = p3->forw) == 0 || p3==p1 || --n==0) 510 return(p1); 511 } while (p3->op!=CBR || p3->labno!=p1->forw->labno); 512 do 513 if ((p1 = p1->back) == 0) 514 return(p); 515 while (p1!=p3); 516 p1 = p; 517 tl = insertl(p1); 518 p3->subop = revbr[p3->subop]; 519 decref(p3->ref); 520 p2->back->forw = p1; 521 p3->forw->back = p1; 522 p1->back->forw = p2; 523 p1->forw->back = p3; 524 t = p1->back; 525 p1->back = p2->back; 526 p2->back = t; 527 t = p1->forw; 528 p1->forw = p3->forw; 529 p3->forw = t; 530 p2 = insertl(p1->forw); 531 p3->labno = p2->labno; 532 p3->ref = p2; 533 decref(tl); 534 if (tl->refc<=0) 535 nrlab--; 536 nchange++; 537 return(p3); 538 #endif 539 } 540 541 static void 542 iterate(struct p2env *p2e, struct dlnod *dl) 543 { 544 struct dlnod *p, *rp, *p1; 545 extern int negrel[]; 546 extern size_t negrelsize; 547 int i; 548 549 nchange = 0; 550 for (p = dl->forw; p!=0; p = p->forw) { 551 if ((p->op==JBR||p->op==CBR) && p->ref) { 552 /* Resolves: 553 * jbr L7 554 * ... 555 * L7: jbr L8 556 */ 557 rp = nonlab(p->ref); 558 if (rp->op==JBR && rp->labno && p->labno!=rp->labno) { 559 setlab(p, rp->labno); 560 decref(p->ref); 561 rp->ref->refc++; 562 p->ref = rp->ref; 563 nchange++; 564 } 565 } 566 if (p->op==CBR && (p1 = p->forw)->op==JBR) { 567 /* Resolves: 568 * cbr L7 569 * jbr L8 570 * L7: 571 */ 572 rp = p->ref; 573 do 574 rp = rp->back; 575 while (rp->op==LABEL); 576 if (rp==p1) { 577 decref(p->ref); 578 p->ref = p1->ref; 579 setlab(p, p1->labno); 580 581 iprem(p1); 582 583 p1->forw->back = p; 584 p->forw = p1->forw; 585 586 i = p->dlip->ip_node->n_left->n_op; 587 if (i < EQ || i - EQ >= (int)negrelsize) 588 comperr("deljumps: unexpected op"); 589 p->dlip->ip_node->n_left->n_op = negrel[i - EQ]; 590 nchange++; 591 } 592 } 593 if (p->op == JBR) { 594 /* Removes dead code */ 595 while (p->forw && p->forw->op!=LABEL && 596 p->forw->op!=EROU) { 597 nchange++; 598 if (p->forw->ref) 599 decref(p->forw->ref); 600 601 iprem(p->forw); 602 603 p->forw = p->forw->forw; 604 p->forw->back = p; 605 } 606 rp = p->forw; 607 while (rp && rp->op==LABEL) { 608 if (p->ref == rp) { 609 p->back->forw = p->forw; 610 p->forw->back = p->back; 611 iprem(p); 612 p = p->back; 613 decref(rp); 614 nchange++; 615 break; 616 } 617 rp = rp->forw; 618 } 619 } 620 if (p->op == JBR) { 621 /* xjump(p); * needs tree rewrite; not yet */ 622 p = codemove(p); 623 } 624 } 625 } 626 627 void 628 deljumps(struct p2env *p2e) 629 { 630 struct interpass *ipole = &p2e->ipole; 631 struct dlnod dln; 632 MARK mark; 633 634 markset(&mark); 635 636 memset(&dln, 0, sizeof(dln)); 637 listsetup(ipole, &dln); 638 do { 639 refcount(p2e, &dln); 640 do { 641 iterate(p2e, &dln); 642 } while (nchange); 643 #ifdef notyet 644 comjump(); 645 #endif 646 } while (nchange); 647 648 markfree(&mark); 649 } 650 651 void 652 optdump(struct interpass *ip) 653 { 654 static char *nm[] = { "node", "prolog", "newblk", "epilog", "locctr", 655 "deflab", "defnam", "asm" }; 656 printf("type %s\n", nm[ip->type-1]); 657 switch (ip->type) { 658 case IP_NODE: 659 #ifdef PCC_DEBUG 660 fwalk(ip->ip_node, e2print, 0); 661 #endif 662 break; 663 case IP_DEFLAB: 664 printf("label " LABFMT "\n", ip->ip_lbl); 665 break; 666 case IP_ASM: 667 printf(": %s\n", ip->ip_asm); 668 break; 669 } 670 } 671 672 /* 673 * Build the basic blocks, algorithm 9.1, pp 529 in Compilers. 674 * 675 * Also fills the labelinfo struct with information about which bblocks 676 * that contain which label. 677 */ 678 679 void 680 bblocks_build(struct p2env *p2e) 681 { 682 struct interpass *ipole = &p2e->ipole; 683 struct interpass *ip; 684 struct basicblock *bb = NULL; 685 int low, high; 686 int count = 0; 687 int i; 688 689 BDEBUG(("bblocks_build (%p, %p)\n", &p2e->labinfo, &p2e->bbinfo)); 690 low = p2e->ipp->ip_lblnum; 691 high = p2e->epp->ip_lblnum; 692 693 /* 694 * First statement is a leader. 695 * Any statement that is target of a jump is a leader. 696 * Any statement that immediately follows a jump is a leader. 697 */ 698 DLIST_INIT(&p2e->bblocks, bbelem); 699 DLIST_FOREACH(ip, ipole, qelem) { 700 if (bb == NULL || (ip->type == IP_EPILOG) || 701 (ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) { 702 bb = tmpalloc(sizeof(struct basicblock)); 703 bb->first = ip; 704 SLIST_INIT(&bb->children); 705 SLIST_INIT(&bb->parents); 706 bb->dfnum = 0; 707 bb->dfparent = 0; 708 bb->semi = 0; 709 bb->ancestor = 0; 710 bb->idom = 0; 711 bb->samedom = 0; 712 bb->bucket = NULL; 713 bb->df = NULL; 714 bb->dfchildren = NULL; 715 bb->Aorig = NULL; 716 bb->Aphi = NULL; 717 SLIST_INIT(&bb->phi); 718 bb->bbnum = count; 719 DLIST_INSERT_BEFORE(&p2e->bblocks, bb, bbelem); 720 count++; 721 } 722 bb->last = ip; 723 if ((ip->type == IP_NODE) && (ip->ip_node->n_op == GOTO || 724 ip->ip_node->n_op == CBRANCH)) 725 bb = NULL; 726 if (ip->type == IP_PROLOG) 727 bb = NULL; 728 } 729 p2e->nbblocks = count; 730 731 if (b2debug) { 732 printf("Basic blocks in func: %d, low %d, high %d\n", 733 count, low, high); 734 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { 735 printf("bb(%d) %p: first %p last %p\n", bb->bbnum, bb, 736 bb->first, bb->last); 737 } 738 } 739 740 p2e->labinfo.low = low; 741 p2e->labinfo.size = high - low + 1; 742 p2e->labinfo.arr = tmpalloc(p2e->labinfo.size * sizeof(struct basicblock *)); 743 for (i = 0; i < p2e->labinfo.size; i++) { 744 p2e->labinfo.arr[i] = NULL; 745 } 746 747 p2e->bbinfo.size = count + 1; 748 p2e->bbinfo.arr = tmpalloc(p2e->bbinfo.size * sizeof(struct basicblock *)); 749 for (i = 0; i < p2e->bbinfo.size; i++) { 750 p2e->bbinfo.arr[i] = NULL; 751 } 752 753 /* Build the label table */ 754 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { 755 if (bb->first->type == IP_DEFLAB) 756 p2e->labinfo.arr[bb->first->ip_lbl - low] = bb; 757 } 758 759 if (b2debug) { 760 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { 761 printf("bblock %d\n", bb->bbnum); 762 for (ip = bb->first; ip != bb->last; 763 ip = DLIST_NEXT(ip, qelem)) { 764 printip2(ip); 765 } 766 printip2(ip); 767 } 768 769 printf("Label table:\n"); 770 for (i = 0; i < p2e->labinfo.size; i++) 771 if (p2e->labinfo.arr[i]) 772 printf("Label %d bblock %p\n", i+low, 773 p2e->labinfo.arr[i]); 774 } 775 } 776 777 /* 778 * Build the control flow graph. 779 */ 780 781 void 782 cfg_build(struct p2env *p2e) 783 { 784 /* Child and parent nodes */ 785 struct cfgnode *cnode; 786 struct cfgnode *pnode; 787 struct basicblock *bb; 788 789 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { 790 791 if (bb->first->type == IP_EPILOG) { 792 break; 793 } 794 795 cnode = tmpalloc(sizeof(struct cfgnode)); 796 pnode = tmpalloc(sizeof(struct cfgnode)); 797 pnode->bblock = bb; 798 799 if ((bb->last->type == IP_NODE) && 800 (bb->last->ip_node->n_op == GOTO) && 801 (bb->last->ip_node->n_left->n_op == ICON)) { 802 if (bb->last->ip_node->n_left->n_lval - p2e->labinfo.low > 803 p2e->labinfo.size) { 804 comperr("Label out of range: %d, base %d", 805 bb->last->ip_node->n_left->n_lval, 806 p2e->labinfo.low); 807 } 808 cnode->bblock = p2e->labinfo.arr[bb->last->ip_node->n_left->n_lval - p2e->labinfo.low]; 809 SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem); 810 SLIST_INSERT_LAST(&bb->children, cnode, cfgelem); 811 continue; 812 } 813 if ((bb->last->type == IP_NODE) && 814 (bb->last->ip_node->n_op == CBRANCH)) { 815 if (bb->last->ip_node->n_right->n_lval - p2e->labinfo.low > 816 p2e->labinfo.size) 817 comperr("Label out of range: %d", 818 bb->last->ip_node->n_left->n_lval); 819 820 cnode->bblock = p2e->labinfo.arr[bb->last->ip_node->n_right->n_lval - p2e->labinfo.low]; 821 SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem); 822 SLIST_INSERT_LAST(&bb->children, cnode, cfgelem); 823 cnode = tmpalloc(sizeof(struct cfgnode)); 824 pnode = tmpalloc(sizeof(struct cfgnode)); 825 pnode->bblock = bb; 826 } 827 828 cnode->bblock = DLIST_NEXT(bb, bbelem); 829 SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem); 830 SLIST_INSERT_LAST(&bb->children, cnode, cfgelem); 831 } 832 } 833 834 void 835 cfg_dfs(struct basicblock *bb, unsigned int parent, struct bblockinfo *bbinfo) 836 { 837 struct cfgnode *cnode; 838 839 if (bb->dfnum != 0) 840 return; 841 842 bb->dfnum = ++dfsnum; 843 bb->dfparent = parent; 844 bbinfo->arr[bb->dfnum] = bb; 845 SLIST_FOREACH(cnode, &bb->children, cfgelem) { 846 cfg_dfs(cnode->bblock, bb->dfnum, bbinfo); 847 } 848 /* Don't bring in unreachable nodes in the future */ 849 bbinfo->size = dfsnum + 1; 850 } 851 852 static bittype * 853 setalloc(int nelem) 854 { 855 bittype *b; 856 int sz = (nelem+NUMBITS-1)/NUMBITS; 857 858 b = tmpalloc(sz * sizeof(bittype)); 859 memset(b, 0, sz * sizeof(bittype)); 860 return b; 861 } 862 863 /* 864 * Algorithm 19.9, pp 414 from Appel. 865 */ 866 867 void 868 dominators(struct p2env *p2e) 869 { 870 struct cfgnode *cnode; 871 struct basicblock *bb, *y, *v; 872 struct basicblock *s, *sprime, *p; 873 int h, i; 874 875 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { 876 bb->bucket = setalloc(p2e->bbinfo.size); 877 bb->df = setalloc(p2e->bbinfo.size); 878 bb->dfchildren = setalloc(p2e->bbinfo.size); 879 } 880 881 dfsnum = 0; 882 cfg_dfs(DLIST_NEXT(&p2e->bblocks, bbelem), 0, &p2e->bbinfo); 883 884 if (b2debug) { 885 struct basicblock *bbb; 886 struct cfgnode *ccnode; 887 888 DLIST_FOREACH(bbb, &p2e->bblocks, bbelem) { 889 printf("Basic block %d, parents: ", bbb->dfnum); 890 SLIST_FOREACH(ccnode, &bbb->parents, cfgelem) { 891 printf("%d, ", ccnode->bblock->dfnum); 892 } 893 printf("\nChildren: "); 894 SLIST_FOREACH(ccnode, &bbb->children, cfgelem) { 895 printf("%d, ", ccnode->bblock->dfnum); 896 } 897 printf("\n"); 898 } 899 } 900 901 for(h = p2e->bbinfo.size - 1; h > 1; h--) { 902 bb = p2e->bbinfo.arr[h]; 903 p = s = p2e->bbinfo.arr[bb->dfparent]; 904 SLIST_FOREACH(cnode, &bb->parents, cfgelem) { 905 if (cnode->bblock->dfnum ==0) 906 continue; /* Ignore unreachable code */ 907 908 if (cnode->bblock->dfnum <= bb->dfnum) 909 sprime = cnode->bblock; 910 else 911 sprime = p2e->bbinfo.arr[ancestorwithlowestsemi 912 (cnode->bblock, &p2e->bbinfo)->semi]; 913 if (sprime->dfnum < s->dfnum) 914 s = sprime; 915 } 916 bb->semi = s->dfnum; 917 BITSET(s->bucket, bb->dfnum); 918 link(p, bb); 919 for (i = 1; i < p2e->bbinfo.size; i++) { 920 if(TESTBIT(p->bucket, i)) { 921 v = p2e->bbinfo.arr[i]; 922 y = ancestorwithlowestsemi(v, &p2e->bbinfo); 923 if (y->semi == v->semi) 924 v->idom = p->dfnum; 925 else 926 v->samedom = y->dfnum; 927 } 928 } 929 memset(p->bucket, 0, (p2e->bbinfo.size + 7)/8); 930 } 931 932 if (b2debug) { 933 printf("Num\tSemi\tAncest\tidom\n"); 934 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { 935 printf("%d\t%d\t%d\t%d\n", bb->dfnum, bb->semi, 936 bb->ancestor, bb->idom); 937 } 938 } 939 940 for(h = 2; h < p2e->bbinfo.size; h++) { 941 bb = p2e->bbinfo.arr[h]; 942 if (bb->samedom != 0) { 943 bb->idom = p2e->bbinfo.arr[bb->samedom]->idom; 944 } 945 } 946 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { 947 if (bb->idom != 0 && bb->idom != bb->dfnum) { 948 BDEBUG(("Setting child %d of %d\n", 949 bb->dfnum, p2e->bbinfo.arr[bb->idom]->dfnum)); 950 BITSET(p2e->bbinfo.arr[bb->idom]->dfchildren, bb->dfnum); 951 } 952 } 953 } 954 955 956 struct basicblock * 957 ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo) 958 { 959 struct basicblock *u = bblock; 960 struct basicblock *v = bblock; 961 962 while (v->ancestor != 0) { 963 if (bbinfo->arr[v->semi]->dfnum < 964 bbinfo->arr[u->semi]->dfnum) 965 u = v; 966 v = bbinfo->arr[v->ancestor]; 967 } 968 return u; 969 } 970 971 void 972 link(struct basicblock *parent, struct basicblock *child) 973 { 974 child->ancestor = parent->dfnum; 975 } 976 977 void 978 computeDF(struct p2env *p2e, struct basicblock *bblock) 979 { 980 struct cfgnode *cnode; 981 int h, i; 982 983 SLIST_FOREACH(cnode, &bblock->children, cfgelem) { 984 if (cnode->bblock->idom != bblock->dfnum) 985 BITSET(bblock->df, cnode->bblock->dfnum); 986 } 987 for (h = 1; h < p2e->bbinfo.size; h++) { 988 if (!TESTBIT(bblock->dfchildren, h)) 989 continue; 990 computeDF(p2e, p2e->bbinfo.arr[h]); 991 for (i = 1; i < p2e->bbinfo.size; i++) { 992 if (TESTBIT(p2e->bbinfo.arr[h]->df, i) && 993 (p2e->bbinfo.arr[i] == bblock || 994 (bblock->dfnum != p2e->bbinfo.arr[i]->idom))) 995 BITSET(bblock->df, i); 996 } 997 } 998 } 999 1000 void printDF(struct p2env *p2e) 1001 { 1002 struct basicblock *bb; 1003 int i; 1004 1005 printf("Dominance frontiers:\n"); 1006 1007 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { 1008 printf("bb %d : ", bb->dfnum); 1009 1010 for (i=1; i < p2e->bbinfo.size;i++) { 1011 if (TESTBIT(bb->df,i)) { 1012 printf("%d ",i); 1013 } 1014 } 1015 1016 printf("\n"); 1017 } 1018 1019 } 1020 1021 1022 1023 static struct basicblock *currbb; 1024 static struct interpass *currip; 1025 1026 /* Helper function for findTemps, Find assignment nodes. */ 1027 static void 1028 searchasg(NODE *p, void *arg) 1029 { 1030 struct pvarinfo *pv; 1031 int tempnr; 1032 struct varstack *stacke; 1033 1034 if (p->n_op != ASSIGN) 1035 return; 1036 1037 if (p->n_left->n_op != TEMP) 1038 return; 1039 1040 tempnr=regno(p->n_left)-defsites.low; 1041 1042 BITSET(currbb->Aorig, tempnr); 1043 1044 pv = tmpcalloc(sizeof(struct pvarinfo)); 1045 pv->next = defsites.arr[tempnr]; 1046 pv->bb = currbb; 1047 pv->n_type = p->n_left->n_type; 1048 1049 defsites.arr[tempnr] = pv; 1050 1051 1052 if (SLIST_FIRST(&defsites.stack[tempnr])==NULL) { 1053 stacke=tmpcalloc(sizeof (struct varstack)); 1054 stacke->tmpregno=0; 1055 SLIST_INSERT_FIRST(&defsites.stack[tempnr],stacke,varstackelem); 1056 } 1057 } 1058 1059 /* Walk the interpass looking for assignment nodes. */ 1060 void findTemps(struct interpass *ip) 1061 { 1062 if (ip->type != IP_NODE) 1063 return; 1064 1065 currip = ip; 1066 1067 walkf(ip->ip_node, searchasg, 0); 1068 } 1069 1070 /* 1071 * Algorithm 19.6 from Appel. 1072 */ 1073 1074 void 1075 placePhiFunctions(struct p2env *p2e) 1076 { 1077 struct basicblock *bb; 1078 struct basicblock *y; 1079 struct interpass *ip; 1080 int maxtmp, i, j, k; 1081 struct pvarinfo *n; 1082 struct cfgnode *cnode; 1083 TWORD ntype; 1084 struct pvarinfo *pv; 1085 struct phiinfo *phi; 1086 int phifound; 1087 1088 bb = DLIST_NEXT(&p2e->bblocks, bbelem); 1089 defsites.low = ((struct interpass_prolog *)bb->first)->ip_tmpnum; 1090 bb = DLIST_PREV(&p2e->bblocks, bbelem); 1091 maxtmp = ((struct interpass_prolog *)bb->first)->ip_tmpnum; 1092 defsites.size = maxtmp - defsites.low + 1; 1093 defsites.arr = tmpcalloc(defsites.size*sizeof(struct pvarinfo *)); 1094 defsites.stack = tmpcalloc(defsites.size*sizeof(SLIST_HEAD(, varstack))); 1095 1096 for (i=0;i<defsites.size;i++) 1097 SLIST_INIT(&defsites.stack[i]); 1098 1099 /* Find all defsites */ 1100 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { 1101 currbb = bb; 1102 ip = bb->first; 1103 bb->Aorig = setalloc(defsites.size); 1104 bb->Aphi = setalloc(defsites.size); 1105 1106 while (ip != bb->last) { 1107 findTemps(ip); 1108 ip = DLIST_NEXT(ip, qelem); 1109 } 1110 /* Make sure we get the last statement in the bblock */ 1111 findTemps(ip); 1112 } 1113 1114 /* For each variable */ 1115 for (i = 0; i < defsites.size; i++) { 1116 /* While W not empty */ 1117 while (defsites.arr[i] != NULL) { 1118 /* Remove some node n from W */ 1119 n = defsites.arr[i]; 1120 defsites.arr[i] = n->next; 1121 /* For each y in n->bb->df */ 1122 for (j = 0; j < p2e->bbinfo.size; j++) { 1123 if (!TESTBIT(n->bb->df, j)) 1124 continue; 1125 1126 if (TESTBIT(p2e->bbinfo.arr[j]->Aphi, i)) 1127 continue; 1128 1129 y=p2e->bbinfo.arr[j]; 1130 ntype = n->n_type; 1131 k = 0; 1132 /* Amount of predecessors for y */ 1133 SLIST_FOREACH(cnode, &y->parents, cfgelem) 1134 k++; 1135 /* Construct phi(...) 1136 */ 1137 1138 phifound=0; 1139 1140 SLIST_FOREACH(phi, &y->phi, phielem) { 1141 if (phi->tmpregno==i+defsites.low) 1142 phifound++; 1143 } 1144 1145 if (phifound==0) { 1146 if (b2debug) 1147 printf("Phi in %d(%d) (%p) for %d\n", 1148 y->dfnum,y->bbnum,y,i+defsites.low); 1149 1150 /* If no live in, no phi node needed */ 1151 if (!TESTBIT(y->in, 1152 (i+defsites.low-p2e->ipp->ip_tmpnum+MAXREGS))) { 1153 if (b2debug) 1154 printf("tmp %d bb %d unused, no phi\n", 1155 i+defsites.low, y->bbnum); 1156 /* No live in */ 1157 BITSET(p2e->bbinfo.arr[j]->Aphi, i); 1158 continue; 1159 } 1160 1161 phi = tmpcalloc(sizeof(struct phiinfo)); 1162 1163 phi->tmpregno=i+defsites.low; 1164 phi->size=k; 1165 phi->n_type=ntype; 1166 phi->intmpregno=tmpcalloc(k*sizeof(int)); 1167 1168 SLIST_INSERT_LAST(&y->phi,phi,phielem); 1169 } else { 1170 if (b2debug) 1171 printf("Phi already in %d for %d\n",y->dfnum,i+defsites.low); 1172 } 1173 1174 BITSET(p2e->bbinfo.arr[j]->Aphi, i); 1175 if (!TESTBIT(p2e->bbinfo.arr[j]->Aorig, i)) { 1176 pv = tmpalloc(sizeof(struct pvarinfo)); 1177 pv->bb = y; 1178 pv->n_type=ntype; 1179 pv->next = defsites.arr[i]; 1180 defsites.arr[i] = pv; 1181 } 1182 } 1183 } 1184 } 1185 } 1186 1187 /* Helper function for renamevar. */ 1188 static void 1189 renamevarhelper(struct p2env *p2e,NODE *t,void *poplistarg) 1190 { 1191 SLIST_HEAD(, varstack) *poplist=poplistarg; 1192 int opty; 1193 int tempnr; 1194 int newtempnr; 1195 int x; 1196 struct varstack *stacke; 1197 1198 if (t->n_op == ASSIGN && t->n_left->n_op == TEMP) { 1199 renamevarhelper(p2e,t->n_right,poplist); 1200 1201 tempnr=regno(t->n_left)-defsites.low; 1202 1203 newtempnr=p2e->epp->ip_tmpnum++; 1204 regno(t->n_left)=newtempnr; 1205 1206 stacke=tmpcalloc(sizeof (struct varstack)); 1207 stacke->tmpregno=newtempnr; 1208 SLIST_INSERT_FIRST(&defsites.stack[tempnr],stacke,varstackelem); 1209 1210 stacke=tmpcalloc(sizeof (struct varstack)); 1211 stacke->tmpregno=tempnr; 1212 SLIST_INSERT_FIRST(poplist,stacke,varstackelem); 1213 } else { 1214 if (t->n_op == TEMP) { 1215 tempnr=regno(t)-defsites.low; 1216 1217 if (SLIST_FIRST(&defsites.stack[tempnr])!=NULL) { 1218 x=SLIST_FIRST(&defsites.stack[tempnr])->tmpregno; 1219 regno(t)=x; 1220 } 1221 } 1222 1223 opty = optype(t->n_op); 1224 1225 if (opty != LTYPE) 1226 renamevarhelper(p2e, t->n_left,poplist); 1227 if (opty == BITYPE) 1228 renamevarhelper(p2e, t->n_right,poplist); 1229 } 1230 } 1231 1232 1233 void 1234 renamevar(struct p2env *p2e,struct basicblock *bb) 1235 { 1236 struct interpass *ip; 1237 int h,j; 1238 SLIST_HEAD(, varstack) poplist; 1239 struct varstack *stacke; 1240 struct cfgnode *cfgn; 1241 struct cfgnode *cfgn2; 1242 int tmpregno,newtmpregno; 1243 struct phiinfo *phi; 1244 1245 SLIST_INIT(&poplist); 1246 1247 SLIST_FOREACH(phi,&bb->phi,phielem) { 1248 tmpregno=phi->tmpregno-defsites.low; 1249 1250 newtmpregno=p2e->epp->ip_tmpnum++; 1251 phi->newtmpregno=newtmpregno; 1252 1253 stacke=tmpcalloc(sizeof (struct varstack)); 1254 stacke->tmpregno=newtmpregno; 1255 SLIST_INSERT_FIRST(&defsites.stack[tmpregno],stacke,varstackelem); 1256 1257 stacke=tmpcalloc(sizeof (struct varstack)); 1258 stacke->tmpregno=tmpregno; 1259 SLIST_INSERT_FIRST(&poplist,stacke,varstackelem); 1260 } 1261 1262 1263 ip=bb->first; 1264 1265 while (1) { 1266 if ( ip->type == IP_NODE) { 1267 renamevarhelper(p2e,ip->ip_node,&poplist); 1268 } 1269 1270 if (ip==bb->last) 1271 break; 1272 1273 ip = DLIST_NEXT(ip, qelem); 1274 } 1275 1276 SLIST_FOREACH(cfgn,&bb->children,cfgelem) { 1277 j=0; 1278 1279 SLIST_FOREACH(cfgn2, &cfgn->bblock->parents, cfgelem) { 1280 if (cfgn2->bblock->dfnum==bb->dfnum) 1281 break; 1282 1283 j++; 1284 } 1285 1286 SLIST_FOREACH(phi,&cfgn->bblock->phi,phielem) { 1287 phi->intmpregno[j]=SLIST_FIRST(&defsites.stack[phi->tmpregno-defsites.low])->tmpregno; 1288 } 1289 1290 } 1291 1292 for (h = 1; h < p2e->bbinfo.size; h++) { 1293 if (!TESTBIT(bb->dfchildren, h)) 1294 continue; 1295 1296 renamevar(p2e,p2e->bbinfo.arr[h]); 1297 } 1298 1299 SLIST_FOREACH(stacke,&poplist,varstackelem) { 1300 tmpregno=stacke->tmpregno; 1301 1302 defsites.stack[tmpregno].q_forw=defsites.stack[tmpregno].q_forw->varstackelem.q_forw; 1303 } 1304 } 1305 1306 enum pred_type { 1307 pred_unknown = 0, 1308 pred_goto = 1, 1309 pred_cond = 2, 1310 pred_falltrough = 3, 1311 } ; 1312 1313 void 1314 removephi(struct p2env *p2e) 1315 { 1316 struct basicblock *bb,*bbparent; 1317 struct cfgnode *cfgn; 1318 struct phiinfo *phi; 1319 int i; 1320 struct interpass *ip; 1321 struct interpass *pip; 1322 TWORD n_type; 1323 1324 enum pred_type complex = pred_unknown ; 1325 1326 int label=0; 1327 int newlabel; 1328 1329 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { 1330 SLIST_FOREACH(phi,&bb->phi,phielem) { 1331 /* Look at only one, notice break at end */ 1332 i=0; 1333 1334 SLIST_FOREACH(cfgn, &bb->parents, cfgelem) { 1335 bbparent=cfgn->bblock; 1336 1337 pip=bbparent->last; 1338 1339 complex = pred_unknown ; 1340 1341 BDEBUG(("removephi: %p in %d",pip,bb->dfnum)); 1342 1343 if (pip->type == IP_NODE && pip->ip_node->n_op == GOTO) { 1344 BDEBUG((" GOTO ")); 1345 label = (int)pip->ip_node->n_left->n_lval; 1346 complex = pred_goto ; 1347 } else if (pip->type == IP_NODE && pip->ip_node->n_op == CBRANCH) { 1348 BDEBUG((" CBRANCH ")); 1349 label = (int)pip->ip_node->n_right->n_lval; 1350 1351 if (bb==p2e->labinfo.arr[label - p2e->ipp->ip_lblnum]) 1352 complex = pred_cond ; 1353 else 1354 complex = pred_falltrough ; 1355 1356 } else if (DLIST_PREV(bb, bbelem) == bbparent) { 1357 complex = pred_falltrough ; 1358 } else { 1359 /* PANIC */ 1360 comperr("Assumption blown in rem-phi") ; 1361 } 1362 1363 BDEBUG((" Complex: %d ",complex)) ; 1364 1365 switch (complex) { 1366 case pred_goto: 1367 /* gotos can only go to this place. No bounce tab needed */ 1368 SLIST_FOREACH(phi,&bb->phi,phielem) { 1369 if (phi->intmpregno[i]>0) { 1370 n_type=phi->n_type; 1371 ip = ipnode(mkbinode(ASSIGN, 1372 mktemp(phi->newtmpregno, n_type), 1373 mktemp(phi->intmpregno[i],n_type), 1374 n_type)); 1375 BDEBUG(("(%p, %d -> %d) ", ip, phi->intmpregno[i], phi->newtmpregno)); 1376 1377 DLIST_INSERT_BEFORE((bbparent->last), ip, qelem); 1378 } 1379 } 1380 break ; 1381 case pred_cond: 1382 /* Here, we need a jump pad */ 1383 newlabel=getlab2(); 1384 1385 ip = tmpalloc(sizeof(struct interpass)); 1386 ip->type = IP_DEFLAB; 1387 /* Line number?? ip->lineno; */ 1388 ip->ip_lbl = newlabel; 1389 DLIST_INSERT_BEFORE((bb->first), ip, qelem); 1390 1391 SLIST_FOREACH(phi,&bb->phi,phielem) { 1392 if (phi->intmpregno[i]>0) { 1393 n_type=phi->n_type; 1394 ip = ipnode(mkbinode(ASSIGN, 1395 mktemp(phi->newtmpregno, n_type), 1396 mktemp(phi->intmpregno[i],n_type), 1397 n_type)); 1398 1399 BDEBUG(("(%p, %d -> %d) ", ip, phi->intmpregno[i], phi->newtmpregno)); 1400 DLIST_INSERT_BEFORE((bb->first), ip, qelem); 1401 } 1402 } 1403 /* add a jump to us */ 1404 ip = ipnode(mkunode(GOTO, mklnode(ICON, label, 0, INT), 0, INT)); 1405 DLIST_INSERT_BEFORE((bb->first), ip, qelem); 1406 pip->ip_node->n_right->n_lval=newlabel; 1407 if (!logop(pip->ip_node->n_left->n_op)) 1408 comperr("SSA not logop"); 1409 pip->ip_node->n_left->n_label=newlabel; 1410 break ; 1411 case pred_falltrough: 1412 if (bb->first->type == IP_DEFLAB) { 1413 label = bb->first->ip_lbl; 1414 BDEBUG(("falltrough label %d\n", label)); 1415 } else { 1416 comperr("BBlock has no label?") ; 1417 } 1418 1419 /* 1420 * add a jump to us. We _will_ be, or already have, added code in between. 1421 * The code is created in the wrong order and switched at the insert, thus 1422 * comming out correctly 1423 */ 1424 1425 ip = ipnode(mkunode(GOTO, mklnode(ICON, label, 0, INT), 0, INT)); 1426 DLIST_INSERT_AFTER((bbparent->last), ip, qelem); 1427 1428 /* Add the code to the end, add a jump to us. */ 1429 SLIST_FOREACH(phi,&bb->phi,phielem) { 1430 if (phi->intmpregno[i]>0) { 1431 n_type=phi->n_type; 1432 ip = ipnode(mkbinode(ASSIGN, 1433 mktemp(phi->newtmpregno, n_type), 1434 mktemp(phi->intmpregno[i],n_type), 1435 n_type)); 1436 1437 BDEBUG(("(%p, %d -> %d) ", ip, phi->intmpregno[i], phi->newtmpregno)); 1438 DLIST_INSERT_AFTER((bbparent->last), ip, qelem); 1439 } 1440 } 1441 break ; 1442 default: 1443 comperr("assumption blown, complex is %d\n", complex) ; 1444 } 1445 BDEBUG(("\n")); 1446 i++; 1447 } 1448 break; 1449 } 1450 } 1451 } 1452 1453 1454 /* 1455 * Remove unreachable nodes in the CFG. 1456 */ 1457 1458 void 1459 remunreach(struct p2env *p2e) 1460 { 1461 struct basicblock *bb, *nbb; 1462 struct interpass *next, *ctree; 1463 1464 bb = DLIST_NEXT(&p2e->bblocks, bbelem); 1465 while (bb != &p2e->bblocks) { 1466 nbb = DLIST_NEXT(bb, bbelem); 1467 1468 /* Code with dfnum 0 is unreachable */ 1469 if (bb->dfnum != 0) { 1470 bb = nbb; 1471 continue; 1472 } 1473 1474 /* Need the epilogue node for other parts of the 1475 compiler, set its label to 0 and backend will 1476 handle it. */ 1477 if (bb->first->type == IP_EPILOG) { 1478 bb->first->ip_lbl = 0; 1479 bb = nbb; 1480 continue; 1481 } 1482 1483 next = bb->first; 1484 do { 1485 ctree = next; 1486 next = DLIST_NEXT(ctree, qelem); 1487 1488 if (ctree->type == IP_NODE) 1489 tfree(ctree->ip_node); 1490 DLIST_REMOVE(ctree, qelem); 1491 } while (ctree != bb->last); 1492 1493 DLIST_REMOVE(bb, bbelem); 1494 bb = nbb; 1495 } 1496 } 1497 1498 static void 1499 printip2(struct interpass *ip) 1500 { 1501 static char *foo[] = { 1502 0, "NODE", "PROLOG", "STKOFF", "EPILOG", "DEFLAB", "DEFNAM", "ASM" }; 1503 struct interpass_prolog *ipplg, *epplg; 1504 unsigned i; 1505 1506 if (ip->type > MAXIP) 1507 printf("IP(%d) (%p): ", ip->type, ip); 1508 else 1509 printf("%s (%p): ", foo[ip->type], ip); 1510 switch (ip->type) { 1511 case IP_NODE: printf("\n"); 1512 #ifdef PCC_DEBUG 1513 fwalk(ip->ip_node, e2print, 0); break; 1514 #endif 1515 case IP_PROLOG: 1516 ipplg = (struct interpass_prolog *)ip; 1517 printf("%s %s regs", 1518 ipplg->ipp_name, ipplg->ipp_vis ? "(local)" : ""); 1519 for (i = 0; i < NIPPREGS; i++) 1520 printf("%s0x%lx", i? ":" : " ", 1521 (long) ipplg->ipp_regs[i]); 1522 printf(" autos %d mintemp %d minlbl %d\n", 1523 ipplg->ipp_autos, ipplg->ip_tmpnum, ipplg->ip_lblnum); 1524 break; 1525 case IP_EPILOG: 1526 epplg = (struct interpass_prolog *)ip; 1527 printf("%s %s regs", 1528 epplg->ipp_name, epplg->ipp_vis ? "(local)" : ""); 1529 for (i = 0; i < NIPPREGS; i++) 1530 printf("%s0x%lx", i? ":" : " ", 1531 (long) epplg->ipp_regs[i]); 1532 printf(" autos %d mintemp %d minlbl %d\n", 1533 epplg->ipp_autos, epplg->ip_tmpnum, epplg->ip_lblnum); 1534 break; 1535 case IP_DEFLAB: printf(LABFMT "\n", ip->ip_lbl); break; 1536 case IP_DEFNAM: printf("\n"); break; 1537 case IP_ASM: printf("%s\n", ip->ip_asm); break; 1538 default: 1539 break; 1540 } 1541 } 1542 1543 void 1544 printip(struct interpass *pole) 1545 { 1546 struct interpass *ip; 1547 1548 DLIST_FOREACH(ip, pole, qelem) 1549 printip2(ip); 1550 } 1551 1552 #ifdef PCC_DEBUG 1553 void flownodeprint(NODE *p,FILE *flowdiagramfile); 1554 1555 void 1556 flownodeprint(NODE *p,FILE *flowdiagramfile) 1557 { 1558 int opty; 1559 char *o; 1560 1561 fprintf(flowdiagramfile,"{"); 1562 1563 o=opst[p->n_op]; 1564 1565 while (*o != 0) { 1566 if (*o=='<' || *o=='>') 1567 fputc('\\',flowdiagramfile); 1568 1569 fputc(*o,flowdiagramfile); 1570 o++; 1571 } 1572 1573 1574 switch( p->n_op ) { 1575 case REG: 1576 fprintf(flowdiagramfile, " %s", rnames[p->n_rval] ); 1577 break; 1578 1579 case TEMP: 1580 fprintf(flowdiagramfile, " %d", regno(p)); 1581 break; 1582 1583 case XASM: 1584 case XARG: 1585 fprintf(flowdiagramfile, " '%s'", p->n_name); 1586 break; 1587 1588 case ICON: 1589 case NAME: 1590 case OREG: 1591 fprintf(flowdiagramfile, " " ); 1592 adrput(flowdiagramfile, p ); 1593 break; 1594 1595 case STCALL: 1596 case USTCALL: 1597 case STARG: 1598 case STASG: 1599 fprintf(flowdiagramfile, " size=%d", p->n_stsize ); 1600 fprintf(flowdiagramfile, " align=%d", p->n_stalign ); 1601 break; 1602 } 1603 1604 opty = optype(p->n_op); 1605 1606 if (opty != LTYPE) { 1607 fprintf(flowdiagramfile,"| {"); 1608 1609 flownodeprint(p->n_left,flowdiagramfile); 1610 1611 if (opty == BITYPE) { 1612 fprintf(flowdiagramfile,"|"); 1613 flownodeprint(p->n_right,flowdiagramfile); 1614 } 1615 fprintf(flowdiagramfile,"}"); 1616 } 1617 1618 fprintf(flowdiagramfile,"}"); 1619 } 1620 1621 void 1622 printflowdiagram(struct p2env *p2e, char *type) { 1623 struct basicblock *bbb; 1624 struct cfgnode *ccnode; 1625 struct interpass *ip; 1626 struct interpass_prolog *plg; 1627 struct phiinfo *phi; 1628 char *name; 1629 char *filename; 1630 int filenamesize; 1631 char *ext=".dot"; 1632 FILE *flowdiagramfile; 1633 1634 if (!g2debug) 1635 return; 1636 1637 bbb=DLIST_NEXT(&p2e->bblocks, bbelem); 1638 ip=bbb->first; 1639 1640 if (ip->type != IP_PROLOG) 1641 return; 1642 plg = (struct interpass_prolog *)ip; 1643 1644 name=plg->ipp_name; 1645 1646 filenamesize=strlen(name)+1+strlen(type)+strlen(ext)+1; 1647 filename=tmpalloc(filenamesize); 1648 snprintf(filename,filenamesize,"%s-%s%s",name,type,ext); 1649 1650 flowdiagramfile=fopen(filename,"w"); 1651 1652 fprintf(flowdiagramfile,"digraph {\n"); 1653 fprintf(flowdiagramfile,"rankdir=LR\n"); 1654 1655 DLIST_FOREACH(bbb, &p2e->bblocks, bbelem) { 1656 ip=bbb->first; 1657 1658 fprintf(flowdiagramfile,"bb%p [shape=record ",bbb); 1659 1660 if (ip->type==IP_PROLOG) 1661 fprintf(flowdiagramfile,"root "); 1662 1663 fprintf(flowdiagramfile,"label=\""); 1664 1665 SLIST_FOREACH(phi,&bbb->phi,phielem) { 1666 fprintf(flowdiagramfile,"Phi %d|",phi->tmpregno); 1667 } 1668 1669 1670 while (1) { 1671 switch (ip->type) { 1672 case IP_NODE: 1673 flownodeprint(ip->ip_node,flowdiagramfile); 1674 break; 1675 1676 case IP_DEFLAB: 1677 fprintf(flowdiagramfile,"Label: %d", ip->ip_lbl); 1678 break; 1679 1680 case IP_PROLOG: 1681 plg = (struct interpass_prolog *)ip; 1682 1683 fprintf(flowdiagramfile,"%s %s",plg->ipp_name,type); 1684 break; 1685 } 1686 1687 fprintf(flowdiagramfile,"|"); 1688 fprintf(flowdiagramfile,"|"); 1689 1690 if (ip==bbb->last) 1691 break; 1692 1693 ip = DLIST_NEXT(ip, qelem); 1694 } 1695 fprintf(flowdiagramfile,"\"]\n"); 1696 1697 SLIST_FOREACH(ccnode, &bbb->children, cfgelem) { 1698 char *color="black"; 1699 struct interpass *pip=bbb->last; 1700 1701 if (pip->type == IP_NODE && pip->ip_node->n_op == CBRANCH) { 1702 int label = (int)pip->ip_node->n_right->n_lval; 1703 1704 if (ccnode->bblock==p2e->labinfo.arr[label - p2e->ipp->ip_lblnum]) 1705 color="red"; 1706 } 1707 1708 fprintf(flowdiagramfile,"bb%p -> bb%p [color=%s]\n", bbb,ccnode->bblock,color); 1709 } 1710 } 1711 1712 fprintf(flowdiagramfile,"}\n"); 1713 fclose(flowdiagramfile); 1714 } 1715 1716 #endif 1717 1718 /* walk all the programm */ 1719 void WalkAll(struct p2env* p2e, void (*f) (NODE*, void*), void* arg, int type) 1720 { 1721 struct interpass *ipole = &p2e->ipole; 1722 struct interpass *ip ; 1723 if (0 != type) { 1724 DLIST_FOREACH(ip, ipole, qelem) { 1725 if (ip->type == IP_NODE && ip->ip_node->n_op == type) 1726 walkf(ip->ip_node, f, arg) ; 1727 } 1728 } else { 1729 DLIST_FOREACH(ip, ipole, qelem) { 1730 if (ip->type == IP_NODE) 1731 walkf(ip->ip_node, f, arg) ; 1732 } 1733 } 1734 } 1735 #if 0 1736 static int is_goto_label(struct interpass*g, struct interpass* l) 1737 { 1738 if (!g || !l) 1739 return 0 ; 1740 if (g->type != IP_NODE) return 0 ; 1741 if (l->type != IP_DEFLAB) return 0 ; 1742 if (g->ip_node->n_op != GOTO) return 0 ; 1743 if (g->ip_node->n_left->n_lval != l->ip_lbl) return 0 ; 1744 return 1 ; 1745 } 1746 #endif 1747 1748 /* 1749 * iterate over the basic blocks. 1750 * In case a block has only one successor and that one has only one pred, and the link is a goto: 1751 * place the second one immediately behind the first one (in terms of nodes, means cut&resplice). 1752 * This should take care of a lot of jumps. 1753 * one problem: Cannot move the first or last basic block (prolog/epilog). This is taken care of by 1754 * moving block #1 to #2, not #2 to #1 1755 * More complex (on the back cooker;) : first coalesc the inner loops (L1 cache), then go from inside out. 1756 */ 1757 1758 static unsigned long count_blocks(struct p2env* p2e) 1759 { 1760 struct basicblock* bb ; 1761 unsigned long count = 0 ; 1762 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { 1763 ++count ; 1764 } 1765 return count ; 1766 } 1767 1768 struct block_map { 1769 struct basicblock* block ; 1770 unsigned long index ; 1771 unsigned long thread ; 1772 } ; 1773 1774 static unsigned long map_blocks(struct p2env* p2e, struct block_map* map, unsigned long count) 1775 { 1776 struct basicblock* bb ; 1777 unsigned long indx = 0 ; 1778 int ignore = 2 ; 1779 unsigned long thread ; 1780 unsigned long changes ; 1781 1782 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { 1783 map[indx].block = bb ; 1784 map[indx].index = indx ; 1785 1786 /* ignore the first 2 labels, maybe up to 3 BBs */ 1787 if (ignore) { 1788 if (bb->first->type == IP_DEFLAB) 1789 --ignore; 1790 1791 map[indx].thread = 1 ; /* these are "fixed" */ 1792 } else 1793 map[indx].thread = 0 ; 1794 1795 indx++ ; 1796 } 1797 1798 thread = 1 ; 1799 do { 1800 changes = 0 ; 1801 1802 for (indx=0; indx < count; indx++) { 1803 /* find block without trace */ 1804 if (map[indx].thread == 0) { 1805 /* do new thread */ 1806 struct cfgnode *cnode ; 1807 struct basicblock *block2 = 0; 1808 unsigned long i ; 1809 unsigned long added ; 1810 1811 BDEBUG (("new thread %ld at block %ld\n", thread, indx)) ; 1812 1813 bb = map[indx].block ; 1814 do { 1815 added = 0 ; 1816 1817 for (i=0; i < count; i++) { 1818 if (map[i].block == bb && map[i].thread == 0) { 1819 map[i].thread = thread ; 1820 1821 BDEBUG(("adding block %ld to trace %ld\n", i, thread)) ; 1822 1823 changes ++ ; 1824 added++ ; 1825 1826 /* 1827 * pick one from followers. For now (simple), pick the 1828 * one who is directly following us. If none of that exists, 1829 * this code picks the last one. 1830 */ 1831 1832 SLIST_FOREACH(cnode, &bb->children, cfgelem) { 1833 block2=cnode->bblock ; 1834 #if 1 1835 if (i+1 < count && map[i+1].block == block2) 1836 break ; /* pick that one */ 1837 #else 1838 if (block2) break ; 1839 #endif 1840 } 1841 1842 if (block2) 1843 bb = block2 ; 1844 } 1845 } 1846 } while (added) ; 1847 thread++ ; 1848 } 1849 } 1850 } while (changes); 1851 1852 /* Last block is also a thread on it's own, and the highest one. */ 1853 /* 1854 thread++ ; 1855 map[count-1].thread = thread ; 1856 */ 1857 if (b2debug) { 1858 printf("Threads\n"); 1859 for (indx=0; indx < count; indx++) { 1860 printf("Block #%ld (lbl %d) Thread %ld\n", indx, map[indx].block->first->ip_lbl, map[indx].thread); 1861 } 1862 } 1863 return thread ; 1864 } 1865 1866 1867 void TraceSchedule(struct p2env* p2e) 1868 { 1869 struct block_map* map ; 1870 unsigned long block_count = count_blocks(p2e); 1871 unsigned long i ; 1872 unsigned long threads; 1873 struct interpass *front, *back ; 1874 1875 map = tmpalloc(block_count * sizeof(struct block_map)); 1876 1877 threads = map_blocks(p2e, map, block_count) ; 1878 1879 back = map[0].block->last ; 1880 for (i=1; i < block_count; i++) { 1881 /* collect the trace */ 1882 unsigned long j ; 1883 unsigned long thread = map[i].thread ; 1884 if (thread) { 1885 BDEBUG(("Thread %ld\n", thread)) ; 1886 for (j=i; j < block_count; j++) { 1887 if (map[j].thread == thread) { 1888 front = map[j].block->first ; 1889 1890 BDEBUG(("Trace %ld, old BB %ld, next BB %ld\t", 1891 thread, i, j)) ; 1892 BDEBUG(("Label %d\n", front->ip_lbl)) ; 1893 DLIST_NEXT(back, qelem) = front ; 1894 DLIST_PREV(front, qelem) = back ; 1895 map[j].thread = 0 ; /* done */ 1896 back = map[j].block->last ; 1897 DLIST_NEXT(back, qelem) = 0 ; 1898 } 1899 } 1900 } 1901 } 1902 DLIST_NEXT(back, qelem) = &(p2e->ipole) ; 1903 DLIST_PREV(&p2e->ipole, qelem) = back ; 1904 } 1905 1906 static void add_labels(struct p2env* p2e) 1907 { 1908 struct interpass *ipole = &p2e->ipole ; 1909 struct interpass *ip ; 1910 1911 DLIST_FOREACH(ip, ipole, qelem) { 1912 if (ip->type == IP_NODE && ip->ip_node->n_op == CBRANCH) { 1913 struct interpass *n = DLIST_NEXT(ip, qelem); 1914 if (n && n->type != IP_DEFLAB) { 1915 struct interpass* lab; 1916 int newlabel=getlab2() ; 1917 1918 BDEBUG(("add_label L%d\n", newlabel)); 1919 1920 lab = tmpalloc(sizeof(struct interpass)); 1921 lab->type = IP_DEFLAB; 1922 /* Line number?? ip->lineno; */ 1923 lab->ip_lbl = newlabel; 1924 DLIST_INSERT_AFTER(ip, lab, qelem); 1925 } 1926 } 1927 } 1928 } 1929 1930 /* node map */ 1931 #ifdef ENABLE_NEW 1932 struct node_map { 1933 NODE* node ; /* the node */ 1934 unsigned int node_num ; /* node is equal to that one */ 1935 unsigned int var_num ; /* node computes this variable */ 1936 } ; 1937 1938 static unsigned long nodes_counter ; 1939 static void node_map_count_walker(NODE* n, void* x) 1940 { 1941 nodes_counter ++ ; 1942 } 1943 1944 static void do_cse(struct p2env* p2e) 1945 { 1946 nodes_counter = 0 ; 1947 WalkAll(p2e, node_map_count_walker, 0, 0) ; 1948 BDEBUG(("Found %ld nodes\n", nodes_counter)) ; 1949 } 1950 #endif 1951 1952 #define BITALLOC(ptr,all,sz) { \ 1953 int sz__s = BIT2BYTE(sz); ptr = all(sz__s); memset(ptr, 0, sz__s); } 1954 #define VALIDREG(p) (p->n_op == REG && TESTBIT(validregs, regno(p))) 1955 #define XCHECK(x) if (x < 0 || x >= xbits) printf("x out of range %d\n", x) 1956 #define RUP(x) (((x)+NUMBITS-1)/NUMBITS) 1957 #define SETCOPY(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] = f[i] 1958 #define SETSET(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] |= f[i] 1959 #define SETCLEAR(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] &= ~f[i] 1960 #define SETCMP(v,t,f,i,n) for (i = 0; i < RUP(n); i++) \ 1961 if (t[i] != f[i]) v = 1 1962 1963 static int xxx, xbits; 1964 /* 1965 * Set/clear long term liveness for regs and temps. 1966 */ 1967 static void 1968 unionize(NODE *p, struct basicblock *bb, int suboff) 1969 { 1970 int o, ty; 1971 1972 if ((o = p->n_op) == TEMP || VALIDREG(p)) { 1973 int b = regno(p); 1974 if (o == TEMP) 1975 b = b - suboff + MAXREGS; 1976 XCHECK(b); 1977 BITSET(bb->gen, b); 1978 } 1979 if (asgop(o)) { 1980 if (p->n_left->n_op == TEMP || VALIDREG(p)) { 1981 int b = regno(p->n_left); 1982 if (p->n_left->n_op == TEMP) 1983 b = b - suboff + MAXREGS; 1984 XCHECK(b); 1985 BITCLEAR(bb->gen, b); 1986 BITSET(bb->killed, b); 1987 unionize(p->n_right, bb, suboff); 1988 return; 1989 } 1990 } 1991 ty = optype(o); 1992 if (ty != LTYPE) 1993 unionize(p->n_left, bb, suboff); 1994 if (ty == BITYPE) 1995 unionize(p->n_right, bb, suboff); 1996 } 1997 1998 /* 1999 * Found an extended assembler node, so growel out gen/killed nodes. 2000 */ 2001 static void 2002 xasmionize(NODE *p, void *arg) 2003 { 2004 struct basicblock *bb = arg; 2005 int cw, b; 2006 2007 if (p->n_op == ICON && p->n_type == STRTY) 2008 return; /* dummy end marker */ 2009 2010 cw = xasmcode(p->n_name); 2011 if (XASMVAL(cw) == 'n' || XASMVAL(cw) == 'm') 2012 return; /* no flow analysis */ 2013 p = p->n_left; 2014 2015 if (XASMVAL(cw) == 'g' && p->n_op != TEMP && p->n_op != REG) 2016 return; /* no flow analysis */ 2017 2018 b = regno(p); 2019 #if 0 2020 if (XASMVAL(cw) == 'r' && p->n_op == TEMP) 2021 addnotspill(b); 2022 #endif 2023 #define MKTOFF(r) ((r) - xxx) 2024 if (XASMISOUT(cw)) { 2025 if (p->n_op == TEMP) { 2026 BITCLEAR(bb->gen, MKTOFF(b)); 2027 BITSET(bb->killed, MKTOFF(b)); 2028 } else if (p->n_op == REG) { 2029 BITCLEAR(bb->gen, b); 2030 BITSET(bb->killed, b); 2031 } else 2032 uerror("bad xasm node type %d", p->n_op); 2033 } 2034 if (XASMISINP(cw)) { 2035 if (p->n_op == TEMP) { 2036 BITSET(bb->gen, MKTOFF(b)); 2037 } else if (p->n_op == REG) { 2038 BITSET(bb->gen, b); 2039 } else if (optype(p->n_op) != LTYPE) { 2040 if (XASMVAL(cw) == 'r') 2041 uerror("couldn't find available register"); 2042 else 2043 uerror("bad xasm node type2"); 2044 } 2045 } 2046 } 2047 2048 /* 2049 * Do variable liveness analysis. Only analyze the long-lived 2050 * variables, and save the live-on-exit temporaries in a bit-field 2051 * at the end of each basic block. This bit-field is later used 2052 * when doing short-range liveness analysis in Build(). 2053 */ 2054 void 2055 liveanal(struct p2env *p2e) 2056 { 2057 struct basicblock *bb; 2058 struct interpass *ip; 2059 struct cfgnode *cn; 2060 bittype *saved; 2061 int i, mintemp, again; 2062 2063 xbits = p2e->epp->ip_tmpnum - p2e->ipp->ip_tmpnum + MAXREGS; 2064 mintemp = p2e->ipp->ip_tmpnum; 2065 2066 /* Just fetch space for the temporaries from heap */ 2067 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { 2068 BITALLOC(bb->gen,tmpalloc,xbits); 2069 BITALLOC(bb->killed,tmpalloc,xbits); 2070 BITALLOC(bb->in,tmpalloc,xbits); 2071 BITALLOC(bb->out,tmpalloc,xbits); 2072 } 2073 BITALLOC(saved,tmpalloc,xbits); 2074 2075 xxx = mintemp; 2076 /* 2077 * generate the gen-killed sets for all basic blocks. 2078 */ 2079 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { 2080 for (ip = bb->last; ; ip = DLIST_PREV(ip, qelem)) { 2081 /* gen/killed is 'p', this node is 'n' */ 2082 if (ip->type == IP_NODE) { 2083 if (ip->ip_node->n_op == XASM) 2084 flist(ip->ip_node->n_left, 2085 xasmionize, bb); 2086 else 2087 unionize(ip->ip_node, bb, mintemp); 2088 } 2089 if (ip == bb->first) 2090 break; 2091 } 2092 memcpy(bb->in, bb->gen, BIT2BYTE(xbits)); 2093 #ifdef PCC_DEBUG 2094 #define PRTRG(x) printf("%d ", i < MAXREGS ? i : i + p2e->ipp->ip_tmpnum-MAXREGS) 2095 if (b2debug > 1) { 2096 printf("basic block %d\ngen: ", bb->bbnum); 2097 for (i = 0; i < xbits; i++) 2098 if (TESTBIT(bb->gen, i)) 2099 PRTRG(i); 2100 printf("\nkilled: "); 2101 for (i = 0; i < xbits; i++) 2102 if (TESTBIT(bb->killed, i)) 2103 PRTRG(i); 2104 printf("\n"); 2105 } 2106 #endif 2107 } 2108 /* do liveness analysis on basic block level */ 2109 do { 2110 int j; 2111 2112 again = 0; 2113 /* XXX - loop should be in reversed execution-order */ 2114 DLIST_FOREACH_REVERSE(bb, &p2e->bblocks, bbelem) { 2115 SETCOPY(saved, bb->out, j, xbits); 2116 SLIST_FOREACH(cn, &bb->children, cfgelem) { 2117 SETSET(bb->out, cn->bblock->in, j, xbits); 2118 } 2119 SETCMP(again, saved, bb->out, j, xbits); 2120 SETCOPY(saved, bb->in, j, xbits); 2121 SETCOPY(bb->in, bb->out, j, xbits); 2122 SETCLEAR(bb->in, bb->killed, j, xbits); 2123 SETSET(bb->in, bb->gen, j, xbits); 2124 SETCMP(again, saved, bb->in, j, xbits); 2125 } 2126 } while (again); 2127 2128 #ifdef PCC_DEBUG 2129 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { 2130 if (b2debug) { 2131 printf("all basic block %d\nin: ", bb->bbnum); 2132 for (i = 0; i < xbits; i++) 2133 if (TESTBIT(bb->in, i)) 2134 PRTRG(i); 2135 printf("\nout: "); 2136 for (i = 0; i < xbits; i++) 2137 if (TESTBIT(bb->out, i)) 2138 PRTRG(i); 2139 printf("\n"); 2140 } 2141 } 2142 #endif 2143 } 2144