Quick Search:

Mode

Context

Displaying the whole file. None | Less | More | Full

Other Diffs

Ignore

Blank Lines Whitespace: Expand:

Diff

1.82
 
1.83
 
MAIN:ragge:20120817205958
 
optim2.c
_>11 /*      $Id$    */
 22 /*
 33  * Copyright (c) 2004 Anders Magnusson (ragge@ludd.luth.se).
 44  * All rights reserved.
 55  *
 66  * Redistribution and use in source and binary forms, with or without
 77  * modification, are permitted provided that the following conditions
 88  * are met:
 99  * 1. Redistributions of source code must retain the above copyright
 1010  *    notice, this list of conditions and the following disclaimer.
 1111  * 2. Redistributions in binary form must reproduce the above copyright
 1212  *    notice, this list of conditions and the following disclaimer in the
 1313  *    documentation and/or other materials provided with the distribution.
 1414  * 3. The name of the author may not be used to endorse or promote products
 1515  *    derived from this software without specific prior written permission
 1616  *
 1717  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 1818  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 1919  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 2020  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 2121  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 2222  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 2323  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 2424  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 2525  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 2626  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 2727  */
 2828 
 2929 #include "pass2.h"
 3030 
 3131 #include <string.h>
 3232 #include <stdlib.h>
 3333 
 3434 #ifndef MIN
 3535 #define MIN(a,b) (((a)<(b))?(a):(b))
 3636 #endif
 3737 
 3838 #ifndef MAX
 3939 #define MAX(a,b) (((a) > (b)) ? (a) : (b))
 4040 #endif
 4141 
 4242 #define BDEBUG(x)       if (b2debug) printf x
 4343 
 4444 #define mktemp(n, t)    mklnode(TEMP, 0, n, t)
 4545 
 4646 #define CHADD(bb,c)     { if (bb->ch[0] == 0) bb->ch[0] = c; \
 4747                           else if (bb->ch[1] == 0) bb->ch[1] = c; \
 4848                           else comperr("triple cfnodes"); }
 4949 #define FORCH(cn, chp)  \
 5050         for (cn = &chp[0]; cn < &chp[2] && cn[0]; cn++)
 5151 
 5252 /* main switch for new things not yet ready for all-day use */
 5353 /* #define ENABLE_NEW */
 5454 
 5555 
 5656 static int dfsnum;
 5757 
 5858 void saveip(struct interpass *ip);
 5959 void deljumps(struct p2env *);
 6060 void optdump(struct interpass *ip);
 6161 void printip(struct interpass *pole);
 6262 
 6363 static struct varinfo defsites;
 6464 struct interpass *storesave;
 6565 
 6666 void bblocks_build(struct p2env *);
 6767 void cfg_build(struct p2env *);
 6868 void cfg_dfs(struct basicblock *bb, unsigned int parent,
 6969              struct bblockinfo *bbinfo);
 7070 void dominators(struct p2env *);
 7171 struct basicblock *
 7272 ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo);
 7373 void link(struct basicblock *parent, struct basicblock *child);
 7474 void computeDF(struct p2env *, struct basicblock *bblock);
 7575 void printDF(struct p2env *p2e);
 7676 void findTemps(struct interpass *ip);
 7777 void placePhiFunctions(struct p2env *);
 7878 void renamevar(struct p2env *p2e,struct basicblock *bblock);
 7979 void removephi(struct p2env *p2e);
 8080 void remunreach(struct p2env *);
 8181 static void liveanal(struct p2env *p2e);
 8282 static void printip2(struct interpass *);
 8383 
 8484 /* create "proper" basic blocks, add labels where needed (so bblocks have labels) */
 8585 /* run before bb generate */
 8686 static void add_labels(struct p2env*) ;
 8787 
 8888 /* Perform trace scheduling, try to get rid of gotos as much as possible */
 8989 void TraceSchedule(struct p2env*) ;
 9090 
 9191 #ifdef ENABLE_NEW
 9292 static void do_cse(struct p2env* p2e) ;
 9393 #endif
 9494 
 9595 /* Walk the complete set, performing a function on each node.
 9696  * if type is given, apply function on only that type */
 9797 void WalkAll(struct p2env* p2e, void (*f) (NODE*, void*), void* arg, int type) ;
 9898 
 9999 void BBLiveDead(struct basicblock* bblock, int what, unsigned int variable) ;
 100100 
 101101 /* Fill the live/dead code */
 102102 void LiveDead(struct p2env* p2e, int what, unsigned int variable) ;
 103103 
 104104 #ifdef PCC_DEBUG
 105105 void printflowdiagram(struct p2env *, char *);
 106106 #endif
 107107 
 108108 void
 109109 optimize(struct p2env *p2e)
 110110 {
 111111         struct interpass *ipole = &p2e->ipole;
 112112 
 113113         if (b2debug) {
 114114                 printf("initial links\n");
 115115                 printip(ipole);
 116116         }
 117117 
 118118         if (xdeljumps)
 119119                 deljumps(p2e); /* Delete redundant jumps and dead code */
 120120 
 121121         if (xssa)
 122122                 add_labels(p2e) ;
 123123 #ifdef ENABLE_NEW
 124124         do_cse(p2e);
 125125 #endif
 126126 
 127127 #ifdef PCC_DEBUG
 128128         if (b2debug) {
 129129                 printf("links after deljumps\n");
 130130                 printip(ipole);
 131131         }
 132132 #endif
 133133         if (xssa || xtemps) {
 134134                 bblocks_build(p2e);
 135135                 BDEBUG(("Calling cfg_build\n"));
 136136                 cfg_build(p2e);
 137137         
 138138 #ifdef PCC_DEBUG
 139139                 printflowdiagram(p2e, "first");
 140140 #endif
 141141         }
 142142         if (xssa) {
 143143                 BDEBUG(("Calling liveanal\n"));
 144144                 liveanal(p2e);
 145145                 BDEBUG(("Calling dominators\n"));
 146146                 dominators(p2e);
 147147                 BDEBUG(("Calling computeDF\n"));
 148148                 computeDF(p2e, DLIST_NEXT(&p2e->bblocks, bbelem));
 149149 
 150150                 if (b2debug) {
 151151                         printDF(p2e);
 152152                 }
 153153 
 154154                 BDEBUG(("Calling placePhiFunctions\n"));
 155155 
 156156                 placePhiFunctions(p2e);
 157157 
 158158                 BDEBUG(("Calling renamevar\n"));
 159159 
 160160                 renamevar(p2e,DLIST_NEXT(&p2e->bblocks, bbelem));
 161161 
 162162                 BDEBUG(("Calling removephi\n"));
 163163 
 164164 #ifdef PCC_DEBUG
 165165                 printflowdiagram(p2e, "ssa");
 166166 #endif
 167167 
 168168                 removephi(p2e);
 169169 
 170170                 BDEBUG(("Calling remunreach\n"));
 171171 /*              remunreach(p2e); */
 172172                 
 173173                 /*
 174174                  * Recalculate basic blocks and cfg that was destroyed
 175175                  * by removephi
 176176                  */
 177177                 /* first, clean up all what deljumps should have done, and more */
 178178 
 179179                 /* TODO: add the basic blocks done by the ssa code by hand.
 180180                  * The trace scheduler should not change the order in
 181181                  * which blocks are executed or what data is calculated.
 182182                  * Thus, the BBlock order should remain correct.
 183183                  */
 184184 
 185185 #ifdef ENABLE_NEW
 186186                 bblocks_build(p2e);
 187187                 BDEBUG(("Calling cfg_build\n"));
 188188                 cfg_build(p2e);
 189189 
 190190                 TraceSchedule(p2e);
 191191 #ifdef PCC_DEBUG
 192192                 printflowdiagram(p2e, "sched_trace");
 193193 
 194194                 if (b2debug) {
 195195                         printf("after tracesched\n");
 196196                         printip(ipole);
 197197                         fflush(stdout) ;
 198198                 }
 199199 #endif
 200200 #endif
 201201 
 202202                 /* Now, clean up the gotos we do not need any longer */
 203203                 if (xdeljumps)
 204204                         deljumps(p2e); /* Delete redundant jumps and dead code */
 205205 
 206206                 bblocks_build(p2e);
 207207                 BDEBUG(("Calling cfg_build\n"));
 208208                 cfg_build(p2e);
 209209 
 210210 #ifdef PCC_DEBUG
 211211                 printflowdiagram(p2e, "no_phi");
 212212 
 213213                 if (b2debug) {
 214214                         printf("new tree\n");
 215215                         printip(ipole);
 216216                 }
 217217 #endif
 218218         }
 219219 
 220220 #ifdef PCC_DEBUG
 221221         {
 222222                 int i;
 223223                 for (i = NIPPREGS; i--; )
 224224                         if (p2e->epp->ipp_regs[i] != 0)
 225225                                 comperr("register error");
 226226         }
 227227 #endif
 228228 
 229229         myoptim(ipole);
 230230 }
 231231 
 232232 /*
 233233  * Delete unused labels, excess of labels, gotos to gotos.
 234234  * This routine can be made much more efficient.
 235235  *
 236236  * Layout of the statement list here (_must_ look this way!):
 237237  *      PROLOG
 238238  *      LABEL   - states beginning of function argument moves
 239239  *      ...code to save/move arguments
 240240  *      LABEL   - states beginning of execution code
 241241  *      ...code + labels in function in function
 242242  *      EPILOG
 243243  *
 244244  * This version of deljumps is based on the c2 implementation
 245245  * that were included in 2BSD.
 246246  */
 247247 #define LABEL 1
 248248 #define JBR     2
 249249 #define CBR     3
 250250 #define STMT    4
 251251 #define EROU    5
 252252 struct dlnod {
 253253         int op;
 254254         struct interpass *dlip;
 255255         struct dlnod *forw;
 256256         struct dlnod *back;
 257257         struct dlnod *ref;
 258258         int labno;
 259259         int refc;
 260260 };
 261261 
 262262 #ifdef DLJDEBUG
 263263 static void
 264264 dumplink(struct dlnod *dl)
 265265 {
 266266         printf("dumplink %p\n", dl);
 267267         for (; dl; dl = dl->forw) {
 268268                 if (dl->op == STMT) {
 269269                         printf("STMT(%p)\n", dl);
 270270                         fwalk(dl->dlip->ip_node, e2print, 0);
 271271                 } else if (dl->op == EROU) {
 272272                         printf("EROU(%p)\n", dl);
 273273                 } else {
 274274                         static char *str[] = { 0, "LABEL", "JBR", "CBR" };
 275275                         printf("%s(%p) %d refc %d ref %p\n", str[dl->op],
 276276                             dl, dl->labno, dl->refc, dl->ref);
 277277                 }
 278278         }
 279279         printf("end dumplink\n");
 280280 }
 281281 #endif
 282282 
 283283 /*
 284284  * Create the linked list that we can work on.
 285285  */
 286286 static void
 287287 listsetup(struct interpass *ipole, struct dlnod *dl)
 288288 {
 289289         struct interpass *ip = DLIST_NEXT(ipole, qelem);
 290290         struct interpass *nip;
 291291         struct dlnod *p, *lastp;
 292292         NODE *q;
 293293 
 294294         lastp = dl;
 295295         while (ip->type != IP_DEFLAB)
 296296                 ip = DLIST_NEXT(ip,qelem);
 297297         ip = DLIST_NEXT(ip,qelem);
 298298         while (ip->type != IP_DEFLAB)
 299299                 ip = DLIST_NEXT(ip,qelem);
 300300         /* Now ip is at the beginning */
 301301         for (;;) {
 302302                 ip = DLIST_NEXT(ip,qelem);
 303303                 if (ip == ipole)
 304304                         break;
 305305                 p = tmpalloc(sizeof(struct dlnod));
 306306                 p->labno = 0;
 307307                 p->dlip = ip;
 308308                 switch (ip->type) {
 309309                 case IP_DEFLAB:
 310310                         p->op = LABEL;
 311311                         p->labno = ip->ip_lbl;
 312312                         break;
 313313 
 314314                 case IP_NODE:
 315315                         q = ip->ip_node;
 316316                         switch (q->n_op) {
 317317                         case GOTO:
 318318                                 p->op = JBR;
 319319                                 p->labno = q->n_left->n_lval;
 320320                                 break;
 321321                         case CBRANCH:
 322322                                 p->op = CBR;
 323323                                 p->labno = q->n_right->n_lval;
 324324                                 break;
 325325                         case ASSIGN:
 326326                                 /* remove ASSIGN to self for regs */
 327327                                 if (q->n_left->n_op == REG &&
 328328                                     q->n_right->n_op == REG &&
 329329                                     regno(q->n_left) == regno(q->n_right)) {
 330330                                         nip = DLIST_PREV(ip, qelem);
 331331                                         tfree(q);
 332332                                         DLIST_REMOVE(ip, qelem);
 333333                                         ip = nip;
 334334                                         continue;
 335335                                 }
 336336                                 /* FALLTHROUGH */
 337337                         default:
 338338                                 p->op = STMT;
 339339                                 break;
 340340                         }
 341341                         break;
 342342 
 343343                 case IP_ASM:
 344344                         p->op = STMT;
 345345                         break;
 346346 
 347347                 case IP_EPILOG:
 348348                         p->op = EROU;
 349349                         break;
 350350 
 351351                 default:
 352352                         comperr("listsetup: bad ip node %d", ip->type);
 353353                 }
 354354                 p->forw = 0;
 355355                 p->back = lastp;
 356356                 lastp->forw = p;
 357357                 lastp = p;
 358358                 p->ref = 0;
 359359         }
 360360 }
 361361 
 362362 static struct dlnod *
 363363 nonlab(struct dlnod *p)
 364364 {
 365365         while (p && p->op==LABEL)
 366366                 p = p->forw;
 367367         return(p);
 368368 }
 369369 
 370370 static void
 371371 iprem(struct dlnod *p)
 372372 {
 373373         if (p->dlip->type == IP_NODE)
 374374                 tfree(p->dlip->ip_node);
 375375         DLIST_REMOVE(p->dlip, qelem);
 376376 }
 377377 
 378378 static void
 379379 decref(struct dlnod *p)
 380380 {
 381381         if (--p->refc <= 0) {
 382382                 iprem(p);
 383383                 p->back->forw = p->forw;
 384384                 p->forw->back = p->back;
 385385         }
 386386 }
 387387 
 388388 static void
 389389 setlab(struct dlnod *p, int labno)
 390390 {
 391391         p->labno = labno;
 392392         if (p->op == JBR)
 393393                 p->dlip->ip_node->n_left->n_lval = labno;
 394394         else if (p->op == CBR) {
 395395                 p->dlip->ip_node->n_right->n_lval = labno;
 396396                 p->dlip->ip_node->n_left->n_label = labno;
 397397         } else
 398398                 comperr("setlab bad op %d", p->op);
 399399 }
 400400 
 401401 /*
 402402  * Label reference counting and removal of unused labels.
 403403  */
 404404 #define LABHS 127
 405405 static void
 406406 refcount(struct p2env *p2e, struct dlnod *dl)
 407407 {
 408408         struct dlnod *p, *lp;
 409409         struct dlnod *labhash[LABHS];
 410410         struct dlnod **hp, *tp;
 411411 
 412412         /* Clear label hash */
 413413         for (hp = labhash; hp < &labhash[LABHS];)
 414414                 *hp++ = 0;
 415415         /* Enter labels into hash.  Later overwrites earlier */
 416416         for (p = dl->forw; p!=0; p = p->forw)
 417417                 if (p->op==LABEL) {
 418418                         labhash[p->labno % LABHS] = p;
 419419                         p->refc = 0;
 420420                 }
 421421 
 422422         /* search for jumps to labels and fill in reference */
 423423         for (p = dl->forw; p!=0; p = p->forw) {
 424424                 if (p->op==JBR || p->op==CBR) {
 425425                         p->ref = 0;
 426426                         lp = labhash[p->labno % LABHS];
 427427                         if (lp==0 || p->labno!=lp->labno)
 428428                             for (lp = dl->forw; lp!=0; lp = lp->forw) {
 429429                                 if (lp->op==LABEL && p->labno==lp->labno)
 430430                                         break;
 431431                             }
 432432                         if (lp) {
 433433                                 tp = nonlab(lp)->back;
 434434                                 if (tp!=lp) {
 435435                                         setlab(p, tp->labno);
 436436                                         lp = tp;
 437437                                 }
 438438                                 p->ref = lp;
 439439                                 lp->refc++;
 440440                         }
 441441                 }
 442442         }
 443443         for (p = dl->forw; p!=0; p = p->forw)
 444444                 if (p->op==LABEL && p->refc==0 && (lp = nonlab(p))->op)
 445445                         decref(p);
 446446 }
 447447 
 448448 static int nchange;
 449449 
 450450 static struct dlnod *
 451451 codemove(struct dlnod *p)
 452452 {
 453453         struct dlnod *p1, *p2, *p3;
 454454 #ifdef notyet
 455455         struct dlnod *t, *tl;
 456456         int n;
 457457 #endif
 458458 
 459459         p1 = p;
 460460         if (p1->op!=JBR || (p2 = p1->ref)==0)
 461461                 return(p1);
 462462         while (p2->op == LABEL)
 463463                 if ((p2 = p2->back) == 0)
 464464                         return(p1);
 465465         if (p2->op!=JBR)
 466466                 goto ivloop;
 467467         if (p1==p2)
 468468                 return(p1);
 469469         p2 = p2->forw;
 470470         p3 = p1->ref;
 471471         while (p3) {
 472472                 if (p3->op==JBR) {
 473473                         if (p1==p3 || p1->forw==p3 || p1->back==p3)
 474474                                 return(p1);
 475475                         nchange++;
 476476                         p1->back->forw = p2;
 477477                         p1->dlip->qelem.q_back->qelem.q_forw = p2->dlip;
 478478 
 479479                         p1->forw->back = p3;
 480480                         p1->dlip->qelem.q_forw->qelem.q_back = p3->dlip;
 481481 
 482482 
 483483                         p2->back->forw = p3->forw;
 484484                         p2->dlip->qelem.q_back->qelem.q_forw = p3->forw->dlip;
 485485 
 486486                         p3->forw->back = p2->back;
 487487                         p3->dlip->qelem.q_forw->qelem.q_back = p2->back->dlip;
 488488 
 489489                         p2->back = p1->back;
 490490                         p2->dlip->qelem.q_back = p1->dlip->qelem.q_back;
 491491 
 492492                         p3->forw = p1->forw;
 493493                         p3->dlip->qelem.q_forw = p1->forw->dlip;
 494494 
 495495                         decref(p1->ref);
 496496                         if (p1->dlip->type == IP_NODE)
 497497                                 tfree(p1->dlip->ip_node);
 498498 
 499499                         return(p2);
 500500                 } else
 501501                         p3 = p3->forw;
 502502         }
 503503         return(p1);
 504504 
 505505 ivloop:
 506506         if (p1->forw->op!=LABEL)
 507507                 return(p1);
 508508         return(p1);
 509509 
 510510 #ifdef notyet
 511511         p3 = p2 = p2->forw;
 512512         n = 16;
 513513         do {
 514514                 if ((p3 = p3->forw) == 0 || p3==p1 || --n==0)
 515515                         return(p1);
 516516         } while (p3->op!=CBR || p3->labno!=p1->forw->labno);
 517517         do
 518518                 if ((p1 = p1->back) == 0)
 519519                         return(p);
 520520         while (p1!=p3);
 521521         p1 = p;
 522522         tl = insertl(p1);
 523523         p3->subop = revbr[p3->subop];
 524524         decref(p3->ref);
 525525                 p2->back->forw = p1;
 526526         p3->forw->back = p1;
 527527         p1->back->forw = p2;
 528528         p1->forw->back = p3;
 529529         t = p1->back;
 530530         p1->back = p2->back;
 531531         p2->back = t;
 532532         t = p1->forw;
 533533         p1->forw = p3->forw;
 534534         p3->forw = t;
 535535         p2 = insertl(p1->forw);
 536536         p3->labno = p2->labno;
 537537         p3->ref = p2;
 538538         decref(tl);
 539539         if (tl->refc<=0)
 540540                 nrlab--;
 541541         nchange++;
 542542         return(p3);
 543543 #endif
 544544 }
 545545 
 546546 static void
 547547 iterate(struct p2env *p2e, struct dlnod *dl)
 548548 {
 549549         struct dlnod *p, *rp, *p1;
 550550         extern int negrel[];
 551551         extern size_t negrelsize;
 552552         int i;
 553553 
 554554         nchange = 0;
 555555         for (p = dl->forw; p!=0; p = p->forw) {
 556556                 if ((p->op==JBR||p->op==CBR) && p->ref) {
 557557                         /* Resolves:
 558558                          * jbr L7
 559559                          * ...
 560560                          * L7: jbr L8
 561561                          */
 562562                         rp = nonlab(p->ref);
 563563                         if (rp->op==JBR && rp->labno && p->labno!=rp->labno) {
 564564                                 setlab(p, rp->labno);
 565565                                 decref(p->ref);
 566566                                 rp->ref->refc++;
 567567                                 p->ref = rp->ref;
 568568                                 nchange++;
 569569                         }
 570570                 }
 571571                 if (p->op==CBR && (p1 = p->forw)->op==JBR) {
 572572                         /* Resolves:
 573573                          * cbr L7
 574574                          * jbr L8
 575575                          * L7:
 576576                          */
 577577                         rp = p->ref;
 578578                         do
 579579                                 rp = rp->back;
 580580                         while (rp->op==LABEL);
 581581                         if (rp==p1) {
 582582                                 decref(p->ref);
 583583                                 p->ref = p1->ref;
 584584                                 setlab(p, p1->labno);
 585585 
 586586                                 iprem(p1);
 587587 
 588588                                 p1->forw->back = p;
 589589                                 p->forw = p1->forw;
 590590 
 591591                                 i = p->dlip->ip_node->n_left->n_op;
 592592                                 if (i < EQ || i - EQ >= (int)negrelsize)
 593593                                         comperr("deljumps: unexpected op");
 594594                                 p->dlip->ip_node->n_left->n_op = negrel[i - EQ];
 595595                                 nchange++;
 596596                         }
 597597                 }
 598598                 if (p->op == JBR) {
 599599                         /* Removes dead code */
 600600                         while (p->forw && p->forw->op!=LABEL &&
 601601                             p->forw->op!=EROU) {
 602602                                 nchange++;
 603603                                 if (p->forw->ref)
 604604                                         decref(p->forw->ref);
 605605 
 606606                                 iprem(p->forw);
 607607 
 608608                                 p->forw = p->forw->forw;
 609609                                 p->forw->back = p;
 610610                         }
 611611                         rp = p->forw;
 612612                         while (rp && rp->op==LABEL) {
 613613                                 if (p->ref == rp) {
 614614                                         p->back->forw = p->forw;
 615615                                         p->forw->back = p->back;
 616616                                         iprem(p);
 617617                                         p = p->back;
 618618                                         decref(rp);
 619619                                         nchange++;
 620620                                         break;
 621621                                 }
 622622                                 rp = rp->forw;
 623623                         }
 624624                 }
 625625                 if (p->op == JBR) {
 626626                         /* xjump(p); * needs tree rewrite; not yet */
 627627                         p = codemove(p);
 628628                 }
 629629         }
 630630 }
 631631 
 632632 void
 633633 deljumps(struct p2env *p2e)
 634634 {
 635635         struct interpass *ipole = &p2e->ipole;
 636636         struct dlnod dln;
 637637         MARK mark;
 638638 
 639639         markset(&mark);
 640640 
 641641         memset(&dln, 0, sizeof(dln));
 642642         listsetup(ipole, &dln);
 643643         do {
 644644                 refcount(p2e, &dln);
 645645                 do {
 646646                         iterate(p2e, &dln);
 647647                 } while (nchange);
 648648 #ifdef notyet
 649649                 comjump();
 650650 #endif
 651651         } while (nchange);
 652652 
 653653         markfree(&mark);
 654654 }
 655655 
 656656 void
 657657 optdump(struct interpass *ip)
 658658 {
 659659         static char *nm[] = { "node", "prolog", "newblk", "epilog", "locctr",
 660660                 "deflab", "defnam", "asm" };
 661661         printf("type %s\n", nm[ip->type-1]);
 662662         switch (ip->type) {
 663663         case IP_NODE:
 664664 #ifdef PCC_DEBUG
 665665                 fwalk(ip->ip_node, e2print, 0);
 666666 #endif
 667667                 break;
 668668         case IP_DEFLAB:
 669669                 printf("label " LABFMT "\n", ip->ip_lbl);
 670670                 break;
 671671         case IP_ASM:
 672672                 printf(": %s\n", ip->ip_asm);
 673673                 break;
 674674         }
 675675 }
 676676 
 677677 /*
 678678  * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
 679679  *
 680680  * Also fills the labelinfo struct with information about which bblocks
 681681  * that contain which label.
 682682  */
 683683 
 684684 void
 685685 bblocks_build(struct p2env *p2e)
 686686 {
 687687         struct interpass *ipole = &p2e->ipole;
 688688         struct interpass *ip;
 689689         struct basicblock *bb = NULL;
 690690         int low, high;
 691691         int count = 0;
 692692         int i;
 693693 
 694694         BDEBUG(("bblocks_build (%p, %p)\n", &p2e->labinfo, &p2e->bbinfo));
 695695         low = p2e->ipp->ip_lblnum;
 696696         high = p2e->epp->ip_lblnum;
 697697 
 698698         /*
 699699          * First statement is a leader.
 700700          * Any statement that is target of a jump is a leader.
 701701          * Any statement that immediately follows a jump is a leader.
 702702          */
 703703         DLIST_INIT(&p2e->bblocks, bbelem);
 704704         DLIST_FOREACH(ip, ipole, qelem) {
 705705                 if (bb == NULL || (ip->type == IP_EPILOG) ||
 706706                     (ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) {
 707707                         bb = tmpalloc(sizeof(struct basicblock));
 708708                         bb->first = ip;
 709709                         SLIST_INIT(&bb->parents);
<>710 -                        bb->ch[0] = bb->ch[1] = NULL;
  710+                        SLIST_INIT(&bb->child);
711711                         bb->dfnum = 0;
 712712                         bb->dfparent = 0;
 713713                         bb->semi = 0;
 714714                         bb->ancestor = 0;
 715715                         bb->idom = 0;
 716716                         bb->samedom = 0;
 717717                         bb->bucket = NULL;
 718718                         bb->df = NULL;
 719719                         bb->dfchildren = NULL;
 720720                         bb->Aorig = NULL;
 721721                         bb->Aphi = NULL;
 722722                         SLIST_INIT(&bb->phi);
 723723                         bb->bbnum = count;
 724724                         DLIST_INSERT_BEFORE(&p2e->bblocks, bb, bbelem);
 725725                         count++;
 726726                 }
 727727                 bb->last = ip;
 728728                 if ((ip->type == IP_NODE) && (ip->ip_node->n_op == GOTO ||
 729729                     ip->ip_node->n_op == CBRANCH))
 730730                         bb = NULL;
 731731                 if (ip->type == IP_PROLOG)
 732732                         bb = NULL;
 733733         }
 734734         p2e->nbblocks = count;
 735735 
 736736         if (b2debug) {
 737737                 printf("Basic blocks in func: %d, low %d, high %d\n",
 738738                     count, low, high);
 739739                 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 740740                         printf("bb(%d) %p: first %p last %p\n", bb->bbnum, bb,
 741741                             bb->first, bb->last);
 742742                 }
 743743         }
 744744 
 745745         p2e->labinfo.low = low;
 746746         p2e->labinfo.size = high - low + 1;
 747747         p2e->labinfo.arr = tmpalloc(p2e->labinfo.size * sizeof(struct basicblock *));
 748748         for (i = 0; i < p2e->labinfo.size; i++) {
 749749                 p2e->labinfo.arr[i] = NULL;
 750750         }
 751751         
 752752         p2e->bbinfo.size = count + 1;
 753753         p2e->bbinfo.arr = tmpalloc(p2e->bbinfo.size * sizeof(struct basicblock *));
 754754         for (i = 0; i < p2e->bbinfo.size; i++) {
 755755                 p2e->bbinfo.arr[i] = NULL;
 756756         }
 757757 
 758758         /* Build the label table */
 759759         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 760760                 if (bb->first->type == IP_DEFLAB)
 761761                         p2e->labinfo.arr[bb->first->ip_lbl - low] = bb;
 762762         }
 763763 
 764764         if (b2debug) {
 765765                 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 766766                         printf("bblock %d\n", bb->bbnum);
 767767                         for (ip = bb->first; ip != bb->last;
 768768                             ip = DLIST_NEXT(ip, qelem)) {
 769769                                 printip2(ip);
 770770                         }
 771771                         printip2(ip);
 772772                 }
 773773 
 774774                 printf("Label table:\n");
 775775                 for (i = 0; i < p2e->labinfo.size; i++)
 776776                         if (p2e->labinfo.arr[i])
 777777                                 printf("Label %d bblock %p\n", i+low,
 778778                                     p2e->labinfo.arr[i]);
 779779         }
 780780 }
 781781 
 782782 /*
 783783  * Build the control flow graph.
 784784  */
 785785 
 786786 void
 787787 cfg_build(struct p2env *p2e)
 788788 {
 789789         /* Child and parent nodes */
 790790         struct cfgnode *cnode;
 791791         struct cfgnode *pnode;
 792792         struct basicblock *bb;
 793793         
 794794         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 795795 
 796796                 if (bb->first->type == IP_EPILOG) {
 797797                         break;
 798798                 }
 799799 
 800800                 cnode = tmpalloc(sizeof(struct cfgnode));
 801801                 pnode = tmpalloc(sizeof(struct cfgnode));
 802802                 pnode->bblock = bb;
 803803 
 804804                 if ((bb->last->type == IP_NODE) &&
 805805                     (bb->last->ip_node->n_op == GOTO) &&
 806806                     (bb->last->ip_node->n_left->n_op == ICON))  {
 807807                         if (bb->last->ip_node->n_left->n_lval - p2e->labinfo.low >
 808808                             p2e->labinfo.size) {
 809809                                 comperr("Label out of range: %d, base %d",
 810810                                         bb->last->ip_node->n_left->n_lval,
 811811                                         p2e->labinfo.low);
 812812                         }
 813813                         cnode->bblock = p2e->labinfo.arr[bb->last->ip_node->n_left->n_lval - p2e->labinfo.low];
 814814                         SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
<>815 -                        CHADD(bb, cnode);
  815+                        SLIST_INSERT_LAST(&bb->child, cnode, chld);
816816                         continue;
 817817                 }
 818818                 if ((bb->last->type == IP_NODE) &&
 819819                     (bb->last->ip_node->n_op == CBRANCH)) {
 820820                         if (bb->last->ip_node->n_right->n_lval - p2e->labinfo.low >
 821821                             p2e->labinfo.size)
 822822                                 comperr("Label out of range: %d",
 823823                                         bb->last->ip_node->n_left->n_lval);
 824824 
 825825                         cnode->bblock = p2e->labinfo.arr[bb->last->ip_node->n_right->n_lval - p2e->labinfo.low];
 826826                         SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
<>827 -                        CHADD(bb, cnode);
  827+                        SLIST_INSERT_LAST(&bb->child, cnode, chld);
828828                         cnode = tmpalloc(sizeof(struct cfgnode));
 829829                         pnode = tmpalloc(sizeof(struct cfgnode));
 830830                         pnode->bblock = bb;
 831831                 }
 832832 
 833833                 cnode->bblock = DLIST_NEXT(bb, bbelem);
 834834                 SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
<>835 -                CHADD(bb, cnode);
  835+                SLIST_INSERT_LAST(&bb->child, cnode, chld);
836836         }
 837837 }
 838838 
 839839 void
 840840 cfg_dfs(struct basicblock *bb, unsigned int parent, struct bblockinfo *bbinfo)
 841841 {
<>842 -        struct cfgnode **cn;
  842+        struct cfgnode *cn;
843843 
 844844         if (bb->dfnum != 0)
 845845                 return;
 846846 
 847847         bb->dfnum = ++dfsnum;
 848848         bb->dfparent = parent;
 849849         bbinfo->arr[bb->dfnum] = bb;
<>850 -        FORCH(cn, bb->ch)
 851 -                cfg_dfs((*cn)->bblock, bb->dfnum, bbinfo);
  850+        SLIST_FOREACH(cn, &bb->child, chld)
  851+                cfg_dfs(cn->bblock, bb->dfnum, bbinfo);
852852         /* Don't bring in unreachable nodes in the future */
 853853         bbinfo->size = dfsnum + 1;
 854854 }
 855855 
 856856 static bittype *
 857857 setalloc(int nelem)
 858858 {
 859859         bittype *b;
 860860         int sz = (nelem+NUMBITS-1)/NUMBITS;
 861861 
 862862         b = tmpalloc(sz * sizeof(bittype));
 863863         memset(b, 0, sz * sizeof(bittype));
 864864         return b;
 865865 }
 866866 
 867867 /*
 868868  * Algorithm 19.9, pp 414 from Appel.
 869869  */
 870870 
 871871 void
 872872 dominators(struct p2env *p2e)
 873873 {
 874874         struct cfgnode *cnode;
 875875         struct basicblock *bb, *y, *v;
 876876         struct basicblock *s, *sprime, *p;
 877877         int h, i;
 878878 
 879879         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 880880                 bb->bucket = setalloc(p2e->bbinfo.size);
 881881                 bb->df = setalloc(p2e->bbinfo.size);
 882882                 bb->dfchildren = setalloc(p2e->bbinfo.size);
 883883         }
 884884 
 885885         dfsnum = 0;
 886886         cfg_dfs(DLIST_NEXT(&p2e->bblocks, bbelem), 0, &p2e->bbinfo);
 887887 
 888888         if (b2debug) {
 889889                 struct basicblock *bbb;
<>890 -                struct cfgnode *ccnode, **cn;
  890+                struct cfgnode *ccnode, *cn;
891891 
 892892                 DLIST_FOREACH(bbb, &p2e->bblocks, bbelem) {
 893893                         printf("Basic block %d, parents: ", bbb->dfnum);
 894894                         SLIST_FOREACH(ccnode, &bbb->parents, cfgelem) {
 895895                                 printf("%d, ", ccnode->bblock->dfnum);
 896896                         }
 897897                         printf("\nChildren: ");
<>898 -                        FORCH(cn, bbb->ch)
 899 -                                printf("%d, ", (*cn)->bblock->dfnum);
  898+                        SLIST_FOREACH(cn, &bbb->child, chld)
  899+                                printf("%d, ", cn->bblock->dfnum);
900900                         printf("\n");
 901901                 }
 902902         }
 903903 
 904904         for(h = p2e->bbinfo.size - 1; h > 1; h--) {
 905905                 bb = p2e->bbinfo.arr[h];
 906906                 p = s = p2e->bbinfo.arr[bb->dfparent];
 907907                 SLIST_FOREACH(cnode, &bb->parents, cfgelem) {
 908908                         if (cnode->bblock->dfnum ==0)
 909909                                 continue; /* Ignore unreachable code */
 910910 
 911911                         if (cnode->bblock->dfnum <= bb->dfnum)
 912912                                 sprime = cnode->bblock;
 913913                         else
 914914                                 sprime = p2e->bbinfo.arr[ancestorwithlowestsemi
 915915                                               (cnode->bblock, &p2e->bbinfo)->semi];
 916916                         if (sprime->dfnum < s->dfnum)
 917917                                 s = sprime;
 918918                 }
 919919                 bb->semi = s->dfnum;
 920920                 BITSET(s->bucket, bb->dfnum);
 921921                 link(p, bb);
 922922                 for (i = 1; i < p2e->bbinfo.size; i++) {
 923923                         if(TESTBIT(p->bucket, i)) {
 924924                                 v = p2e->bbinfo.arr[i];
 925925                                 y = ancestorwithlowestsemi(v, &p2e->bbinfo);
 926926                                 if (y->semi == v->semi)
 927927                                         v->idom = p->dfnum;
 928928                                 else
 929929                                         v->samedom = y->dfnum;
 930930                         }
 931931                 }
 932932                 memset(p->bucket, 0, (p2e->bbinfo.size + 7)/8);
 933933         }
 934934 
 935935         if (b2debug) {
 936936                 printf("Num\tSemi\tAncest\tidom\n");
 937937                 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 938938                         printf("%d\t%d\t%d\t%d\n", bb->dfnum, bb->semi,
 939939                             bb->ancestor, bb->idom);
 940940                 }
 941941         }
 942942 
 943943         for(h = 2; h < p2e->bbinfo.size; h++) {
 944944                 bb = p2e->bbinfo.arr[h];
 945945                 if (bb->samedom != 0) {
 946946                         bb->idom = p2e->bbinfo.arr[bb->samedom]->idom;
 947947                 }
 948948         }
 949949         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 950950                 if (bb->idom != 0 && bb->idom != bb->dfnum) {
 951951                         BDEBUG(("Setting child %d of %d\n",
 952952                             bb->dfnum, p2e->bbinfo.arr[bb->idom]->dfnum));
 953953                         BITSET(p2e->bbinfo.arr[bb->idom]->dfchildren, bb->dfnum);
 954954                 }
 955955         }
 956956 }
 957957 
 958958 
 959959 struct basicblock *
 960960 ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo)
 961961 {
 962962         struct basicblock *u = bblock;
 963963         struct basicblock *v = bblock;
 964964 
 965965         while (v->ancestor != 0) {
 966966                 if (bbinfo->arr[v->semi]->dfnum <
 967967                     bbinfo->arr[u->semi]->dfnum)
 968968                         u = v;
 969969                 v = bbinfo->arr[v->ancestor];
 970970         }
 971971         return u;
 972972 }
 973973 
 974974 void
 975975 link(struct basicblock *parent, struct basicblock *child)
 976976 {
 977977         child->ancestor = parent->dfnum;
 978978 }
 979979 
 980980 void
 981981 computeDF(struct p2env *p2e, struct basicblock *bblock)
 982982 {
<>983 -        struct cfgnode **cn;
  983+        struct cfgnode *cn;
984984         int h, i;
 985985         
<>986 -        FORCH(cn, bblock->ch) {
 987 -                if ((*cn)->bblock->idom != bblock->dfnum)
 988 -                        BITSET(bblock->df, (*cn)->bblock->dfnum);
  986+        SLIST_FOREACH(cn, &bblock->child, chld) {
  987+                if (cn->bblock->idom != bblock->dfnum)
  988+                        BITSET(bblock->df, cn->bblock->dfnum);
989989         }
 990990         for (h = 1; h < p2e->bbinfo.size; h++) {
 991991                 if (!TESTBIT(bblock->dfchildren, h))
 992992                         continue;
 993993                 computeDF(p2e, p2e->bbinfo.arr[h]);
 994994                 for (i = 1; i < p2e->bbinfo.size; i++) {
 995995                         if (TESTBIT(p2e->bbinfo.arr[h]->df, i) &&
 996996                             (p2e->bbinfo.arr[i] == bblock ||
 997997                              (bblock->dfnum != p2e->bbinfo.arr[i]->idom)))
 998998                             BITSET(bblock->df, i);
 999999                 }
 10001000         }
 10011001 }
 10021002 
 10031003 void printDF(struct p2env *p2e)
 10041004 {
 10051005         struct basicblock *bb;
 10061006         int i;
 10071007 
 10081008         printf("Dominance frontiers:\n");
 10091009    
 10101010         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 10111011                 printf("bb %d : ", bb->dfnum);
 10121012         
 10131013                 for (i=1; i < p2e->bbinfo.size;i++) {
 10141014                         if (TESTBIT(bb->df,i)) {
 10151015                                 printf("%d ",i);
 10161016                         }
 10171017                 }
 10181018            
 10191019                 printf("\n");
 10201020         }
 10211021    
 10221022 }
 10231023 
 10241024 
 10251025 
 10261026 static struct basicblock *currbb;
 10271027 static struct interpass *currip;
 10281028 
 10291029 /* Helper function for findTemps, Find assignment nodes. */
 10301030 static void
 10311031 searchasg(NODE *p, void *arg)
 10321032 {
 10331033         struct pvarinfo *pv;
 10341034         int tempnr;
 10351035         struct varstack *stacke;
 10361036    
 10371037         if (p->n_op != ASSIGN)
 10381038                 return;
 10391039 
 10401040         if (p->n_left->n_op != TEMP)
 10411041                 return;
 10421042 
 10431043         tempnr=regno(p->n_left)-defsites.low;
 10441044    
 10451045         BITSET(currbb->Aorig, tempnr);
 10461046         
 10471047         pv = tmpcalloc(sizeof(struct pvarinfo));
 10481048         pv->next = defsites.arr[tempnr];
 10491049         pv->bb = currbb;
 10501050         pv->n_type = p->n_left->n_type;
 10511051         
 10521052         defsites.arr[tempnr] = pv;
 10531053         
 10541054         
 10551055         if (SLIST_FIRST(&defsites.stack[tempnr])==NULL) {
 10561056                 stacke=tmpcalloc(sizeof (struct varstack));
 10571057                 stacke->tmpregno=0;
 10581058                 SLIST_INSERT_FIRST(&defsites.stack[tempnr],stacke,varstackelem);
 10591059         }
 10601060 }
 10611061 
 10621062 /* Walk the interpass looking for assignment nodes. */
 10631063 void findTemps(struct interpass *ip)
 10641064 {
 10651065         if (ip->type != IP_NODE)
 10661066                 return;
 10671067 
 10681068         currip = ip;
 10691069 
 10701070         walkf(ip->ip_node, searchasg, 0);
 10711071 }
 10721072 
 10731073 /*
 10741074  * Algorithm 19.6 from Appel.
 10751075  */
 10761076 
 10771077 void
 10781078 placePhiFunctions(struct p2env *p2e)
 10791079 {
 10801080         struct basicblock *bb;
 10811081         struct basicblock *y;
 10821082         struct interpass *ip;
 10831083         int maxtmp, i, j, k;
 10841084         struct pvarinfo *n;
 10851085         struct cfgnode *cnode;
 10861086         TWORD ntype;
 10871087         struct pvarinfo *pv;
 10881088         struct phiinfo *phi;
 10891089         int phifound;
 10901090 
 10911091         bb = DLIST_NEXT(&p2e->bblocks, bbelem);
 10921092         defsites.low = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
 10931093         bb = DLIST_PREV(&p2e->bblocks, bbelem);
 10941094         maxtmp = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
 10951095         defsites.size = maxtmp - defsites.low + 1;
 10961096         defsites.arr = tmpcalloc(defsites.size*sizeof(struct pvarinfo *));
 10971097         defsites.stack = tmpcalloc(defsites.size*sizeof(SLIST_HEAD(, varstack)));
 10981098         
 10991099         for (i=0;i<defsites.size;i++)
 11001100                 SLIST_INIT(&defsites.stack[i]); 
 11011101         
 11021102         /* Find all defsites */
 11031103         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 11041104                 currbb = bb;
 11051105                 ip = bb->first;
 11061106                 bb->Aorig = setalloc(defsites.size);
 11071107                 bb->Aphi = setalloc(defsites.size);
 11081108                 
 11091109                 while (ip != bb->last) {
 11101110                         findTemps(ip);
 11111111                         ip = DLIST_NEXT(ip, qelem);
 11121112                 }
 11131113                 /* Make sure we get the last statement in the bblock */
 11141114                 findTemps(ip);
 11151115         }
 11161116 
 11171117         /* For each variable */
 11181118         for (i = 0; i < defsites.size; i++) {
 11191119                 /* While W not empty */
 11201120                 while (defsites.arr[i] != NULL) {
 11211121                         /* Remove some node n from W */
 11221122                         n = defsites.arr[i];
 11231123                         defsites.arr[i] = n->next;
 11241124                         /* For each y in n->bb->df */
 11251125                         for (j = 0; j < p2e->bbinfo.size; j++) {
 11261126                                 if (!TESTBIT(n->bb->df, j))
 11271127                                         continue;
 11281128                                 
 11291129                                 if (TESTBIT(p2e->bbinfo.arr[j]->Aphi, i))
 11301130                                         continue;
 11311131 
 11321132                                 y=p2e->bbinfo.arr[j];
 11331133                                 ntype = n->n_type;
 11341134                                 k = 0;
 11351135                                 /* Amount of predecessors for y */
 11361136                                 SLIST_FOREACH(cnode, &y->parents, cfgelem)
 11371137                                         k++;
 11381138                                 /* Construct phi(...)
 11391139                                 */
 11401140                            
 11411141                                 phifound=0;
 11421142                            
 11431143                                 SLIST_FOREACH(phi, &y->phi, phielem) {
 11441144                                     if (phi->tmpregno==i+defsites.low)
 11451145                                         phifound++;
 11461146                                 }
 11471147                            
 11481148                                 if (phifound==0) {
 11491149                                         if (b2debug)
 11501150                                             printf("Phi in %d(%d) (%p) for %d\n",
 11511151                                             y->dfnum,y->bbnum,y,i+defsites.low);
 11521152 
 11531153                                         /* If no live in, no phi node needed */
 11541154                                         if (!TESTBIT(y->in,
 11551155                                             (i+defsites.low-p2e->ipp->ip_tmpnum+MAXREGS))) {
 11561156                                         if (b2debug)
 11571157                                         printf("tmp %d bb %d unused, no phi\n",
 11581158                                             i+defsites.low, y->bbnum);
 11591159                                                 /* No live in */
 11601160                                                 BITSET(p2e->bbinfo.arr[j]->Aphi, i);
 11611161                                                 continue;
 11621162                                         }
 11631163 
 11641164                                         phi = tmpcalloc(sizeof(struct phiinfo));
 11651165                            
 11661166                                         phi->tmpregno=i+defsites.low;
 11671167                                         phi->size=k;
 11681168                                         phi->n_type=ntype;
 11691169                                         phi->intmpregno=tmpcalloc(k*sizeof(int));
 11701170                            
 11711171                                         SLIST_INSERT_LAST(&y->phi,phi,phielem);
 11721172                                 } else {
 11731173                                     if (b2debug)
 11741174                                         printf("Phi already in %d for %d\n",y->dfnum,i+defsites.low);
 11751175                                 }
 11761176 
 11771177                                 BITSET(p2e->bbinfo.arr[j]->Aphi, i);
 11781178                                 if (!TESTBIT(p2e->bbinfo.arr[j]->Aorig, i)) {
 11791179                                         pv = tmpalloc(sizeof(struct pvarinfo));
 11801180                                         pv->bb = y;
 11811181                                         pv->n_type=ntype;
 11821182                                         pv->next = defsites.arr[i];
 11831183                                         defsites.arr[i] = pv;
 11841184                                 }
 11851185                         }
 11861186                 }
 11871187         }
 11881188 }
 11891189 
 11901190 /* Helper function for renamevar. */
 11911191 static void
 11921192 renamevarhelper(struct p2env *p2e,NODE *t,void *poplistarg)
 11931193 {       
 11941194         SLIST_HEAD(, varstack) *poplist=poplistarg;
 11951195         int opty;
 11961196         int tempnr;
 11971197         int newtempnr;
 11981198         int x;
 11991199         struct varstack *stacke;
 12001200         
 12011201         if (t->n_op == ASSIGN && t->n_left->n_op == TEMP) {
 12021202                 renamevarhelper(p2e,t->n_right,poplist);
 12031203                                 
 12041204                 tempnr=regno(t->n_left)-defsites.low;
 12051205                 
 12061206                 newtempnr=p2e->epp->ip_tmpnum++;
 12071207                 regno(t->n_left)=newtempnr;
 12081208                 
 12091209                 stacke=tmpcalloc(sizeof (struct varstack));
 12101210                 stacke->tmpregno=newtempnr;
 12111211                 SLIST_INSERT_FIRST(&defsites.stack[tempnr],stacke,varstackelem);
 12121212                 
 12131213                 stacke=tmpcalloc(sizeof (struct varstack));
 12141214                 stacke->tmpregno=tempnr;
 12151215                 SLIST_INSERT_FIRST(poplist,stacke,varstackelem);
 12161216         } else {
 12171217                 if (t->n_op == TEMP) {
 12181218                         tempnr=regno(t)-defsites.low;
 12191219                 
 12201220                         if (SLIST_FIRST(&defsites.stack[tempnr])!=NULL) {
 12211221                                 x=SLIST_FIRST(&defsites.stack[tempnr])->tmpregno;
 12221222                                 regno(t)=x;
 12231223                         }
 12241224                 }
 12251225                 
 12261226                 opty = optype(t->n_op);
 12271227                 
 12281228                 if (opty != LTYPE)
 12291229                         renamevarhelper(p2e, t->n_left,poplist);
 12301230                 if (opty == BITYPE)
 12311231                         renamevarhelper(p2e, t->n_right,poplist);
 12321232         }
 12331233 }
 12341234 
 12351235 
 12361236 void
 12371237 renamevar(struct p2env *p2e,struct basicblock *bb)
 12381238 {
 12391239         struct interpass *ip;
 12401240         int h,j;
 12411241         SLIST_HEAD(, varstack) poplist;
 12421242         struct varstack *stacke;
<>1243 -        struct cfgnode *cfgn2, **cn;
  1243+        struct cfgnode *cfgn2, *cn;
12441244         int tmpregno,newtmpregno;
 12451245         struct phiinfo *phi;
 12461246 
 12471247         SLIST_INIT(&poplist);
 12481248 
 12491249         SLIST_FOREACH(phi,&bb->phi,phielem) {
 12501250                 tmpregno=phi->tmpregno-defsites.low;
 12511251                 
 12521252                 newtmpregno=p2e->epp->ip_tmpnum++;
 12531253                 phi->newtmpregno=newtmpregno;
 12541254 
 12551255                 stacke=tmpcalloc(sizeof (struct varstack));
 12561256                 stacke->tmpregno=newtmpregno;
 12571257                 SLIST_INSERT_FIRST(&defsites.stack[tmpregno],stacke,varstackelem);
 12581258                 
 12591259                 stacke=tmpcalloc(sizeof (struct varstack));
 12601260                 stacke->tmpregno=tmpregno;
 12611261                 SLIST_INSERT_FIRST(&poplist,stacke,varstackelem);               
 12621262         }
 12631263 
 12641264 
 12651265         ip=bb->first;
 12661266 
 12671267         while (1) {             
 12681268                 if ( ip->type == IP_NODE) {
 12691269                         renamevarhelper(p2e,ip->ip_node,&poplist);
 12701270                 }
 12711271 
 12721272                 if (ip==bb->last)
 12731273                         break;
 12741274 
 12751275                 ip = DLIST_NEXT(ip, qelem);
 12761276         }
 12771277 
<>1278 -        FORCH(cn, bb->ch) {
  1278+        SLIST_FOREACH(cn, &bb->child, chld) {
12791279                 j=0;
 12801280 
<>1281 -                SLIST_FOREACH(cfgn2, &(*cn)->bblock->parents, cfgelem) {
  1281+                SLIST_FOREACH(cfgn2, &cn->bblock->parents, cfgelem) {
12821282                         if (cfgn2->bblock->dfnum==bb->dfnum)
 12831283                                 break;
 12841284                         
 12851285                         j++;
 12861286                 }
 12871287 
<>1288 -                SLIST_FOREACH(phi,&(*cn)->bblock->phi,phielem) {
  1288+                SLIST_FOREACH(phi,&cn->bblock->phi,phielem) {
12891289                         phi->intmpregno[j]=SLIST_FIRST(&defsites.stack[phi->tmpregno-defsites.low])->tmpregno;
 12901290                 }
 12911291         }
 12921292 
 12931293         for (h = 1; h < p2e->bbinfo.size; h++) {
 12941294                 if (!TESTBIT(bb->dfchildren, h))
 12951295                         continue;
 12961296 
 12971297                 renamevar(p2e,p2e->bbinfo.arr[h]);
 12981298         }
 12991299 
 13001300         SLIST_FOREACH(stacke,&poplist,varstackelem) {
 13011301                 tmpregno=stacke->tmpregno;
 13021302                 
 13031303                 defsites.stack[tmpregno].q_forw=defsites.stack[tmpregno].q_forw->varstackelem.q_forw;
 13041304         }
 13051305 }
 13061306 
 13071307 enum pred_type {
 13081308     pred_unknown    = 0,
 13091309     pred_goto       = 1,
 13101310     pred_cond       = 2,
 13111311     pred_falltrough = 3,
 13121312 } ;
 13131313 
 13141314 void
 13151315 removephi(struct p2env *p2e)
 13161316 {
 13171317         struct basicblock *bb,*bbparent;
 13181318         struct cfgnode *cfgn;
 13191319         struct phiinfo *phi;
 13201320         int i;
 13211321         struct interpass *ip;
 13221322         struct interpass *pip;
 13231323         TWORD n_type;
 13241324 
 13251325         enum pred_type complex = pred_unknown ;
 13261326 
 13271327         int label=0;
 13281328         int newlabel;
 13291329 
 13301330         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {              
 13311331                 SLIST_FOREACH(phi,&bb->phi,phielem) {
 13321332                         /* Look at only one, notice break at end */
 13331333                         i=0;
 13341334                         
 13351335                         SLIST_FOREACH(cfgn, &bb->parents, cfgelem) {
 13361336                                 bbparent=cfgn->bblock;
 13371337                                 
 13381338                                 pip=bbparent->last;
 13391339                                 
 13401340                                 complex = pred_unknown ;
 13411341                                 
 13421342                                 BDEBUG(("removephi: %p in %d",pip,bb->dfnum));
 13431343 
 13441344                                 if (pip->type == IP_NODE && pip->ip_node->n_op == GOTO) {
 13451345                                         BDEBUG((" GOTO "));
 13461346                                         label = (int)pip->ip_node->n_left->n_lval;
 13471347                                         complex = pred_goto ;
 13481348                                 } else if (pip->type == IP_NODE && pip->ip_node->n_op == CBRANCH) {
 13491349                                         BDEBUG((" CBRANCH "));
 13501350                                         label = (int)pip->ip_node->n_right->n_lval;
 13511351                                         
 13521352                                         if (bb==p2e->labinfo.arr[label - p2e->ipp->ip_lblnum])
 13531353                                                 complex = pred_cond ;
 13541354                                         else
 13551355                                                 complex = pred_falltrough ;
 13561356 
 13571357                                 } else if (DLIST_PREV(bb, bbelem) == bbparent) {
 13581358                                         complex = pred_falltrough ;
 13591359                                 } else {
 13601360                                             /* PANIC */
 13611361                                         comperr("Assumption blown in rem-phi") ;
 13621362                                 }
 13631363       
 13641364                                 BDEBUG((" Complex: %d ",complex)) ;
 13651365 
 13661366                                 switch (complex) {
 13671367                                   case pred_goto:
 13681368                                         /* gotos can only go to this place. No bounce tab needed */
 13691369                                         SLIST_FOREACH(phi,&bb->phi,phielem) {
 13701370                                                 if (phi->intmpregno[i]>0) {
 13711371                                                         n_type=phi->n_type;
 13721372                                                         ip = ipnode(mkbinode(ASSIGN,
 13731373                                                              mktemp(phi->newtmpregno, n_type),
 13741374                                                              mktemp(phi->intmpregno[i],n_type),
 13751375                                                              n_type));
 13761376                                                         BDEBUG(("(%p, %d -> %d) ", ip, phi->intmpregno[i], phi->newtmpregno));
 13771377                                 
 13781378                                                         DLIST_INSERT_BEFORE((bbparent->last), ip, qelem);
 13791379                                                 }
 13801380                                         }
 13811381                                         break ;
 13821382                                   case pred_cond:
 13831383                                         /* Here, we need a jump pad */
 13841384                                         newlabel=getlab2();
 13851385                         
 13861386                                         ip = tmpalloc(sizeof(struct interpass));
 13871387                                         ip->type = IP_DEFLAB;
 13881388                                         /* Line number?? ip->lineno; */
 13891389                                         ip->ip_lbl = newlabel;
 13901390                                         DLIST_INSERT_BEFORE((bb->first), ip, qelem);
 13911391 
 13921392                                         SLIST_FOREACH(phi,&bb->phi,phielem) {
 13931393                                                 if (phi->intmpregno[i]>0) {
 13941394                                                         n_type=phi->n_type;
 13951395                                                         ip = ipnode(mkbinode(ASSIGN,
 13961396                                                              mktemp(phi->newtmpregno, n_type),
 13971397                                                              mktemp(phi->intmpregno[i],n_type),
 13981398                                                              n_type));
 13991399 
 14001400                                                         BDEBUG(("(%p, %d -> %d) ", ip, phi->intmpregno[i], phi->newtmpregno));
 14011401                                                         DLIST_INSERT_BEFORE((bb->first), ip, qelem);
 14021402                                                 }
 14031403                                         }
 14041404                                         /* add a jump to us */
 14051405                                         ip = ipnode(mkunode(GOTO, mklnode(ICON, label, 0, INT), 0, INT));
 14061406                                         DLIST_INSERT_BEFORE((bb->first), ip, qelem);
 14071407                                         pip->ip_node->n_right->n_lval=newlabel;
 14081408                                         if (!logop(pip->ip_node->n_left->n_op))
 14091409                                                 comperr("SSA not logop");
 14101410                                         pip->ip_node->n_left->n_label=newlabel;
 14111411                                         break ;
 14121412                                   case pred_falltrough:
 14131413                                         if (bb->first->type == IP_DEFLAB) {
 14141414                                                 label = bb->first->ip_lbl;
 14151415                                                 BDEBUG(("falltrough label %d\n", label));
 14161416                                         } else {
 14171417                                                 comperr("BBlock has no label?") ;
 14181418                                         }
 14191419 
 14201420                                         /*
 14211421                                          * add a jump to us. We _will_ be, or already have, added code in between.
 14221422                                          * The code is created in the wrong order and switched at the insert, thus
 14231423                                          * comming out correctly
 14241424                                          */
 14251425 
 14261426                                         ip = ipnode(mkunode(GOTO, mklnode(ICON, label, 0, INT), 0, INT));
 14271427                                         DLIST_INSERT_AFTER((bbparent->last), ip, qelem);
 14281428 
 14291429                                         /* Add the code to the end, add a jump to us. */
 14301430                                         SLIST_FOREACH(phi,&bb->phi,phielem) {
 14311431                                                 if (phi->intmpregno[i]>0) {
 14321432                                                         n_type=phi->n_type;
 14331433                                                         ip = ipnode(mkbinode(ASSIGN,
 14341434                                                                 mktemp(phi->newtmpregno, n_type),
 14351435                                                                 mktemp(phi->intmpregno[i],n_type),
 14361436                                                                 n_type));
 14371437 
 14381438                                                         BDEBUG(("(%p, %d -> %d) ", ip, phi->intmpregno[i], phi->newtmpregno));
 14391439                                                         DLIST_INSERT_AFTER((bbparent->last), ip, qelem);
 14401440                                                 }
 14411441                                         }
 14421442                                         break ;
 14431443                                 default:
 14441444                                         comperr("assumption blown, complex is %d\n", complex) ;
 14451445                                 }
 14461446                                 BDEBUG(("\n"));
 14471447                                 i++;
 14481448                         }
 14491449                         break;
 14501450                 }
 14511451         }
 14521452 }
 14531453 
 14541454    
 14551455 /*
 14561456  * Remove unreachable nodes in the CFG.
 14571457  */
 14581458 
 14591459 void
 14601460 remunreach(struct p2env *p2e)
 14611461 {
 14621462         struct basicblock *bb, *nbb;
 14631463         struct interpass *next, *ctree;
 14641464 
 14651465         bb = DLIST_NEXT(&p2e->bblocks, bbelem);
 14661466         while (bb != &p2e->bblocks) {
 14671467                 nbb = DLIST_NEXT(bb, bbelem);
 14681468 
 14691469                 /* Code with dfnum 0 is unreachable */
 14701470                 if (bb->dfnum != 0) {
 14711471                         bb = nbb;
 14721472                         continue;
 14731473                 }
 14741474 
 14751475                 /* Need the epilogue node for other parts of the
 14761476                    compiler, set its label to 0 and backend will
 14771477                    handle it. */
 14781478                 if (bb->first->type == IP_EPILOG) {
 14791479                         bb->first->ip_lbl = 0;
 14801480                         bb = nbb;
 14811481                         continue;
 14821482                 }
 14831483 
 14841484                 next = bb->first;
 14851485                 do {
 14861486                         ctree = next;
 14871487                         next = DLIST_NEXT(ctree, qelem);
 14881488                         
 14891489                         if (ctree->type == IP_NODE)
 14901490                                 tfree(ctree->ip_node);
 14911491                         DLIST_REMOVE(ctree, qelem);
 14921492                 } while (ctree != bb->last);
 14931493                         
 14941494                 DLIST_REMOVE(bb, bbelem);
 14951495                 bb = nbb;
 14961496         }
 14971497 }
 14981498 
 14991499 static void
 15001500 printip2(struct interpass *ip)
 15011501 {
 15021502         static char *foo[] = {
 15031503            0, "NODE", "PROLOG", "STKOFF", "EPILOG", "DEFLAB", "DEFNAM", "ASM" };
 15041504         struct interpass_prolog *ipplg, *epplg;
 15051505         unsigned i;
 15061506 
 15071507         if (ip->type > MAXIP)
 15081508                 printf("IP(%d) (%p): ", ip->type, ip);
 15091509         else
 15101510                 printf("%s (%p): ", foo[ip->type], ip);
 15111511         switch (ip->type) {
 15121512         case IP_NODE: printf("\n");
 15131513 #ifdef PCC_DEBUG
 15141514         fwalk(ip->ip_node, e2print, 0); break;
 15151515 #endif
 15161516         case IP_PROLOG:
 15171517                 ipplg = (struct interpass_prolog *)ip;
 15181518                 printf("%s %s regs",
 15191519                     ipplg->ipp_name, ipplg->ipp_vis ? "(local)" : "");
 15201520                 for (i = 0; i < NIPPREGS; i++)
 15211521                         printf("%s0x%lx", i? ":" : " ",
 15221522                             (long) ipplg->ipp_regs[i]);
 15231523                 printf(" autos %d mintemp %d minlbl %d\n",
 15241524                     ipplg->ipp_autos, ipplg->ip_tmpnum, ipplg->ip_lblnum);
 15251525                 break;
 15261526         case IP_EPILOG:
 15271527                 epplg = (struct interpass_prolog *)ip;
 15281528                 printf("%s %s regs",
 15291529                     epplg->ipp_name, epplg->ipp_vis ? "(local)" : "");
 15301530                 for (i = 0; i < NIPPREGS; i++)
 15311531                         printf("%s0x%lx", i? ":" : " ",
 15321532                             (long) epplg->ipp_regs[i]);
 15331533                 printf(" autos %d mintemp %d minlbl %d\n",
 15341534                     epplg->ipp_autos, epplg->ip_tmpnum, epplg->ip_lblnum);
 15351535                 break;
 15361536         case IP_DEFLAB: printf(LABFMT "\n", ip->ip_lbl); break;
 15371537         case IP_DEFNAM: printf("\n"); break;
 15381538         case IP_ASM: printf("%s\n", ip->ip_asm); break;
 15391539         default:
 15401540                 break;
 15411541         }
 15421542 }
 15431543 
 15441544 void
 15451545 printip(struct interpass *pole)
 15461546 {
 15471547         struct interpass *ip;
 15481548 
 15491549         DLIST_FOREACH(ip, pole, qelem)
 15501550                 printip2(ip);
 15511551 }
 15521552 
 15531553 #ifdef PCC_DEBUG
 15541554 void flownodeprint(NODE *p,FILE *flowdiagramfile);
 15551555 
 15561556 void
 15571557 flownodeprint(NODE *p,FILE *flowdiagramfile)
 15581558 {       
 15591559         int opty;
 15601560         char *o;
 15611561 
 15621562         fprintf(flowdiagramfile,"{");
 15631563 
 15641564         o=opst[p->n_op];
 15651565         
 15661566         while (*o != 0) {
 15671567                 if (*o=='<' || *o=='>')
 15681568                         fputc('\\',flowdiagramfile);
 15691569                 
 15701570                 fputc(*o,flowdiagramfile);
 15711571                 o++;
 15721572         }
 15731573         
 15741574         
 15751575         switch( p->n_op ) {                     
 15761576                 case REG:
 15771577                         fprintf(flowdiagramfile, " %s", rnames[p->n_rval] );
 15781578                         break;
 15791579                         
 15801580                 case TEMP:
 15811581                         fprintf(flowdiagramfile, " %d", regno(p));
 15821582                         break;
 15831583                         
 15841584                 case XASM:
 15851585                 case XARG:
 15861586                         fprintf(flowdiagramfile, " '%s'", p->n_name);
 15871587                         break;
 15881588                         
 15891589                 case ICON:
 15901590                 case NAME:
 15911591                 case OREG:
 15921592                         fprintf(flowdiagramfile, " " );
 15931593                         adrput(flowdiagramfile, p );
 15941594                         break;
 15951595                         
 15961596                 case STCALL:
 15971597                 case USTCALL:
 15981598                 case STARG:
 15991599                 case STASG:
 16001600                         fprintf(flowdiagramfile, " size=%d", p->n_stsize );
 16011601                         fprintf(flowdiagramfile, " align=%d", p->n_stalign );
 16021602                         break;
 16031603         }
 16041604         
 16051605         opty = optype(p->n_op);
 16061606         
 16071607         if (opty != LTYPE) {
 16081608                 fprintf(flowdiagramfile,"| {");
 16091609         
 16101610                 flownodeprint(p->n_left,flowdiagramfile);
 16111611         
 16121612                 if (opty == BITYPE) {
 16131613                         fprintf(flowdiagramfile,"|");
 16141614                         flownodeprint(p->n_right,flowdiagramfile);
 16151615                 }
 16161616                 fprintf(flowdiagramfile,"}");
 16171617         }
 16181618         
 16191619         fprintf(flowdiagramfile,"}");
 16201620 }
 16211621 
 16221622 void
 16231623 printflowdiagram(struct p2env *p2e, char *type) {
 16241624         struct basicblock *bbb;
<>1625 -        struct cfgnode **cn;
  1625+        struct cfgnode *cn;
16261626         struct interpass *ip;
 16271627         struct interpass_prolog *plg;
 16281628         struct phiinfo *phi;
 16291629         char *name;
 16301630         char *filename;
 16311631         int filenamesize;
 16321632         char *ext=".dot";
 16331633         FILE *flowdiagramfile;
 16341634         
 16351635         if (!g2debug)
 16361636                 return;
 16371637         
 16381638         bbb=DLIST_NEXT(&p2e->bblocks, bbelem);
 16391639         ip=bbb->first;
 16401640 
 16411641         if (ip->type != IP_PROLOG)
 16421642                 return;
 16431643         plg = (struct interpass_prolog *)ip;
 16441644 
 16451645         name=plg->ipp_name;
 16461646         
 16471647         filenamesize=strlen(name)+1+strlen(type)+strlen(ext)+1;
 16481648         filename=tmpalloc(filenamesize);
 16491649         snprintf(filename,filenamesize,"%s-%s%s",name,type,ext);
 16501650         
 16511651         flowdiagramfile=fopen(filename,"w");
 16521652         
 16531653         fprintf(flowdiagramfile,"digraph {\n");
 16541654         fprintf(flowdiagramfile,"rankdir=LR\n");
 16551655         
 16561656         DLIST_FOREACH(bbb, &p2e->bblocks, bbelem) {
 16571657                 ip=bbb->first;
 16581658                 
 16591659                 fprintf(flowdiagramfile,"bb%p [shape=record ",bbb);
 16601660                 
 16611661                 if (ip->type==IP_PROLOG)
 16621662                         fprintf(flowdiagramfile,"root ");
 16631663 
 16641664                 fprintf(flowdiagramfile,"label=\"");
 16651665                 
 16661666                 SLIST_FOREACH(phi,&bbb->phi,phielem) {
 16671667                         fprintf(flowdiagramfile,"Phi %d|",phi->tmpregno);
 16681668                 }               
 16691669                 
 16701670                 
 16711671                 while (1) {
 16721672                         switch (ip->type) {
 16731673                                 case IP_NODE:
 16741674                                         flownodeprint(ip->ip_node,flowdiagramfile);
 16751675                                         break;
 16761676                                         
 16771677                                 case IP_DEFLAB:
 16781678                                         fprintf(flowdiagramfile,"Label: %d", ip->ip_lbl);
 16791679                                         break;
 16801680                                         
 16811681                                 case IP_PROLOG:
 16821682                                         plg = (struct interpass_prolog *)ip;
 16831683         
 16841684                                         fprintf(flowdiagramfile,"%s %s",plg->ipp_name,type);
 16851685                                         break;
 16861686                         }
 16871687                         
 16881688                         fprintf(flowdiagramfile,"|");
 16891689                         fprintf(flowdiagramfile,"|");
 16901690                         
 16911691                         if (ip==bbb->last)
 16921692                                 break;
 16931693                         
 16941694                         ip = DLIST_NEXT(ip, qelem);
 16951695                 }
 16961696                 fprintf(flowdiagramfile,"\"]\n");
 16971697                 
<>1698 -                FORCH(cn, bbb->ch) {
  1698+                SLIST_FOREACH(cn, &bbb->child, chld) {
16991699                         char *color="black";
 17001700                         struct interpass *pip=bbb->last;
 17011701 
 17021702                         if (pip->type == IP_NODE && pip->ip_node->n_op == CBRANCH) {
 17031703                                 int label = (int)pip->ip_node->n_right->n_lval;
 17041704                                 
<>1705 -                                if ((*cn)->bblock==p2e->labinfo.arr[label - p2e->ipp->ip_lblnum])
  1705+                                if (cn->bblock==p2e->labinfo.arr[label - p2e->ipp->ip_lblnum])
17061706                                         color="red";
 17071707                         }
 17081708                         
<>1709 -                        fprintf(flowdiagramfile,"bb%p -> bb%p [color=%s]\n", bbb,(*cn)->bblock,color);
  1709+                        fprintf(flowdiagramfile,"bb%p -> bb%p [color=%s]\n", bbb,cn->bblock,color);
17101710                 }
 17111711         }
 17121712         
 17131713         fprintf(flowdiagramfile,"}\n");
 17141714         fclose(flowdiagramfile);
 17151715 }
 17161716 
 17171717 #endif
 17181718 
 17191719 /* walk all the programm */
 17201720 void WalkAll(struct p2env* p2e, void (*f) (NODE*, void*), void* arg, int type)
 17211721 {
 17221722         struct interpass *ipole = &p2e->ipole;
 17231723         struct interpass *ip ;
 17241724         if (0 != type) {
 17251725                 DLIST_FOREACH(ip, ipole, qelem) {
 17261726                         if (ip->type == IP_NODE && ip->ip_node->n_op == type)
 17271727                                 walkf(ip->ip_node, f, arg) ;
 17281728                 }
 17291729         } else {
 17301730                 DLIST_FOREACH(ip, ipole, qelem) {
 17311731                         if (ip->type == IP_NODE)
 17321732                                 walkf(ip->ip_node, f, arg) ;
 17331733                 }
 17341734         }
 17351735 }
 17361736 #if 0
 17371737 static int is_goto_label(struct interpass*g, struct interpass* l)
 17381738 {
 17391739         if (!g || !l)
 17401740                 return 0 ;
 17411741         if (g->type != IP_NODE) return 0 ;
 17421742         if (l->type != IP_DEFLAB) return 0 ;
 17431743         if (g->ip_node->n_op != GOTO) return 0 ;
 17441744         if (g->ip_node->n_left->n_lval != l->ip_lbl) return 0 ;
 17451745         return 1 ;
 17461746 }
 17471747 #endif
 17481748 
 17491749 /*
 17501750  * iterate over the basic blocks.
 17511751  * In case a block has only one successor and that one has only one pred, and the link is a goto:
 17521752  * place the second one immediately behind the first one (in terms of nodes, means cut&resplice).
 17531753  * This should take care of a lot of jumps.
 17541754  * one problem: Cannot move the first or last basic block (prolog/epilog). This is taken care of by
 17551755  * moving block #1 to #2, not #2 to #1
 17561756  * More complex (on the back cooker;) : first coalesc the inner loops (L1 cache), then go from inside out.
 17571757  */
 17581758 
 17591759 static unsigned long count_blocks(struct p2env* p2e)
 17601760 {
 17611761         struct basicblock* bb ;
 17621762         unsigned long count = 0 ;
 17631763         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 17641764                 ++count ;
 17651765         }
 17661766         return count ;
 17671767 }
 17681768 
 17691769 struct block_map {
 17701770         struct basicblock* block ;
 17711771         unsigned long index ;
 17721772         unsigned long thread ;
 17731773 } ;
 17741774 
 17751775 static unsigned long map_blocks(struct p2env* p2e, struct block_map* map, unsigned long count)
 17761776 {
 17771777         struct basicblock* bb ;
 17781778         unsigned long indx = 0 ;
 17791779         int ignore = 2 ;
 17801780         unsigned long thread ;
 17811781         unsigned long changes ;
 17821782 
 17831783         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 17841784                 map[indx].block = bb ;
 17851785                 map[indx].index = indx ;
 17861786 
 17871787                 /* ignore the first 2 labels, maybe up to 3 BBs */
 17881788                 if (ignore) {
 17891789                         if (bb->first->type == IP_DEFLAB)
 17901790                                 --ignore;
 17911791 
 17921792                         map[indx].thread = 1 ;  /* these are "fixed" */
 17931793                 } else
 17941794                         map[indx].thread = 0 ;
 17951795 
 17961796                 indx++ ;
 17971797         }
 17981798 
 17991799         thread = 1 ;
 18001800         do {
 18011801                 changes = 0 ;
 18021802                 
 18031803                 for (indx=0; indx < count; indx++) {
 18041804                         /* find block without trace */
 18051805                         if (map[indx].thread == 0) {
 18061806                                 /* do new thread */
<>1807 -                                struct cfgnode **cn ;
  1807+                                struct cfgnode *cn ;
18081808                                 struct basicblock *block2 = 0;
 18091809                                 unsigned long i ;
 18101810                                 unsigned long added ;
 18111811                                 
 18121812                                 BDEBUG (("new thread %ld at block %ld\n", thread, indx)) ;
 18131813 
 18141814                                 bb = map[indx].block ;
 18151815                                 do {
 18161816                                         added = 0 ;
 18171817 
 18181818                                         for (i=0; i < count; i++) {
 18191819                                                 if (map[i].block == bb && map[i].thread == 0) {
 18201820                                                         map[i].thread = thread ;
 18211821 
 18221822                                                         BDEBUG(("adding block %ld to trace %ld\n", i, thread)) ;
 18231823 
 18241824                                                         changes ++ ;
 18251825                                                         added++ ;
 18261826 
 18271827                                                         /*
 18281828                                                          * pick one from followers. For now (simple), pick the
 18291829                                                          * one who is directly following us. If none of that exists,
 18301830                                                          * this code picks the last one.
 18311831                                                          */
 18321832 
<>1833 -                                                        FORCH(cn, bb->ch) {
 1834 -                                                                block2=(*cn)->bblock ;
  1833+                                                        SLIST_FOREACH(cn, &bb->child, chld) {
  1834+                                                                block2=cn->bblock ;
18351835 #if 1
 18361836                                                                 if (i+1 < count && map[i+1].block == block2)
 18371837                                                                         break ; /* pick that one */
 18381838 #else
 18391839                                                                 if (block2) break ;
 18401840 #endif
 18411841                                                         }
 18421842 
 18431843                                                         if (block2)
 18441844                                                                 bb = block2 ;
 18451845                                                 }
 18461846                                         }
 18471847                                 } while (added) ;
 18481848                                 thread++ ;
 18491849                         }
 18501850                 }
 18511851         } while (changes);
 18521852 
 18531853         /* Last block is also a thread on it's own, and the highest one. */
 18541854 /*
 18551855         thread++ ;
 18561856         map[count-1].thread = thread ;
 18571857 */
 18581858         if (b2debug) {
 18591859                 printf("Threads\n");
 18601860                 for (indx=0; indx < count; indx++) {
 18611861                         printf("Block #%ld (lbl %d) Thread %ld\n", indx, map[indx].block->first->ip_lbl, map[indx].thread);
 18621862                 }
 18631863         }
 18641864         return thread ;
 18651865 }
 18661866 
 18671867 
 18681868 void TraceSchedule(struct p2env* p2e)
 18691869 {
 18701870         struct block_map* map ;
 18711871         unsigned long block_count = count_blocks(p2e);
 18721872         unsigned long i ;
 18731873         unsigned long threads;
 18741874         struct interpass *front, *back ;
 18751875 
 18761876         map = tmpalloc(block_count * sizeof(struct block_map));
 18771877 
 18781878         threads = map_blocks(p2e, map, block_count) ;
 18791879 
 18801880         back = map[0].block->last ;
 18811881         for (i=1; i < block_count; i++) {
 18821882                 /* collect the trace */
 18831883                 unsigned long j ;
 18841884                 unsigned long thread = map[i].thread ;
 18851885                 if (thread) {
 18861886                         BDEBUG(("Thread %ld\n", thread)) ;
 18871887                         for (j=i; j < block_count; j++) {
 18881888                                 if (map[j].thread == thread) {
 18891889                                         front = map[j].block->first ;
 18901890 
 18911891                                         BDEBUG(("Trace %ld, old BB %ld, next BB %ld\t",
 18921892                                                 thread, i, j)) ;
 18931893                                         BDEBUG(("Label %d\n", front->ip_lbl)) ;
 18941894                                         DLIST_NEXT(back, qelem) = front ;
 18951895                                         DLIST_PREV(front, qelem) = back ;
 18961896                                         map[j].thread = 0 ;     /* done */
 18971897                                         back = map[j].block->last ;
 18981898                                         DLIST_NEXT(back, qelem) = 0 ;
 18991899                                 }
 19001900                         }
 19011901                 }
 19021902         }
 19031903         DLIST_NEXT(back, qelem) = &(p2e->ipole) ;
 19041904         DLIST_PREV(&p2e->ipole, qelem) = back ;
 19051905 }
 19061906 
 19071907 static void add_labels(struct p2env* p2e)
 19081908 {
 19091909         struct interpass *ipole = &p2e->ipole ;
 19101910         struct interpass *ip ;
 19111911 
 19121912         DLIST_FOREACH(ip, ipole, qelem) {
 19131913                 if (ip->type == IP_NODE && ip->ip_node->n_op == CBRANCH) {
 19141914                         struct interpass *n = DLIST_NEXT(ip, qelem);
 19151915                         if (n && n->type != IP_DEFLAB) {
 19161916                                 struct interpass* lab;
 19171917                                 int newlabel=getlab2() ;
 19181918 
 19191919                                 BDEBUG(("add_label L%d\n", newlabel));
 19201920 
 19211921                                 lab = tmpalloc(sizeof(struct interpass));
 19221922                                 lab->type = IP_DEFLAB;
 19231923                                 /* Line number?? ip->lineno; */
 19241924                                 lab->ip_lbl = newlabel;
 19251925                                 DLIST_INSERT_AFTER(ip, lab, qelem);
 19261926                         }
 19271927                 }
 19281928         }
 19291929 }
 19301930 
 19311931 /* node map */
 19321932 #ifdef ENABLE_NEW
 19331933 struct node_map {
 19341934         NODE* node ;            /* the node */
 19351935         unsigned int node_num ; /* node is equal to that one */
 19361936         unsigned int var_num ;  /* node computes this variable */
 19371937 } ;
 19381938 
 19391939 static unsigned long nodes_counter ;
 19401940 static void node_map_count_walker(NODE* n, void* x)
 19411941 {
 19421942         nodes_counter ++ ;
 19431943 }
 19441944 
 19451945 static void do_cse(struct p2env* p2e)
 19461946 {
 19471947         nodes_counter = 0 ;
 19481948         WalkAll(p2e, node_map_count_walker, 0, 0) ;
 19491949         BDEBUG(("Found %ld nodes\n", nodes_counter)) ;
 19501950 }
 19511951 #endif
 19521952 
 19531953 #define BITALLOC(ptr,all,sz) { \
 19541954         int sz__s = BIT2BYTE(sz); ptr = all(sz__s); memset(ptr, 0, sz__s); }
 19551955 #define VALIDREG(p)     (p->n_op == REG && TESTBIT(validregs, regno(p)))
 19561956 #define XCHECK(x) if (x < 0 || x >= xbits) printf("x out of range %d\n", x)
 19571957 #define RUP(x) (((x)+NUMBITS-1)/NUMBITS)
 19581958 #define SETCOPY(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] = f[i]
 19591959 #define SETSET(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] |= f[i]
 19601960 #define SETCLEAR(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] &= ~f[i]
 19611961 #define SETCMP(v,t,f,i,n) for (i = 0; i < RUP(n); i++) \
 19621962         if (t[i] != f[i]) v = 1
 19631963 
 19641964 static int xxx, xbits;
 19651965 /*
 19661966  * Set/clear long term liveness for regs and temps.
 19671967  */
 19681968 static void
 19691969 unionize(NODE *p, struct basicblock *bb, int suboff)
 19701970 {
 19711971         int o, ty;
 19721972 
 19731973         if ((o = p->n_op) == TEMP || VALIDREG(p)) {
 19741974                 int b = regno(p);
 19751975                 if (o == TEMP)
 19761976                         b = b - suboff + MAXREGS;
 19771977 XCHECK(b);
 19781978                 BITSET(bb->gen, b);
 19791979         }
 19801980         if (asgop(o)) {
 19811981                 if (p->n_left->n_op == TEMP || VALIDREG(p)) {
 19821982                         int b = regno(p->n_left);
 19831983                         if (p->n_left->n_op == TEMP)
 19841984                                 b = b - suboff + MAXREGS;
 19851985 XCHECK(b);
 19861986                         BITCLEAR(bb->gen, b);
 19871987                         BITSET(bb->killed, b);
 19881988                         unionize(p->n_right, bb, suboff);
 19891989                         return;
 19901990                 }
 19911991         }
 19921992         ty = optype(o);
 19931993         if (ty != LTYPE)
 19941994                 unionize(p->n_left, bb, suboff);
 19951995         if (ty == BITYPE)
 19961996                 unionize(p->n_right, bb, suboff);
 19971997 }
 19981998 
 19991999 /*
 20002000  * Found an extended assembler node, so growel out gen/killed nodes.
 20012001  */
 20022002 static void
 20032003 xasmionize(NODE *p, void *arg)
 20042004 {
 20052005         struct basicblock *bb = arg;
 20062006         int cw, b;
 20072007 
 20082008         if (p->n_op == ICON && p->n_type == STRTY)
 20092009                 return; /* dummy end marker */
 20102010 
 20112011         cw = xasmcode(p->n_name);
 20122012         if (XASMVAL(cw) == 'n' || XASMVAL(cw) == 'm')
 20132013                 return; /* no flow analysis */
 20142014         p = p->n_left;
 20152015  
 20162016         if (XASMVAL(cw) == 'g' && p->n_op != TEMP && p->n_op != REG)
 20172017                 return; /* no flow analysis */
 20182018 
 20192019         b = regno(p);
 20202020 #if 0
 20212021         if (XASMVAL(cw) == 'r' && p->n_op == TEMP)
 20222022                 addnotspill(b);
 20232023 #endif
 20242024 #define MKTOFF(r)       ((r) - xxx)
 20252025         if (XASMISOUT(cw)) {
 20262026                 if (p->n_op == TEMP) {
 20272027                         BITCLEAR(bb->gen, MKTOFF(b));
 20282028                         BITSET(bb->killed, MKTOFF(b));
 20292029                 } else if (p->n_op == REG) {
 20302030                         BITCLEAR(bb->gen, b);
 20312031                         BITSET(bb->killed, b);  
 20322032                 } else
 20332033                         uerror("bad xasm node type %d", p->n_op);
 20342034         }
 20352035         if (XASMISINP(cw)) {
 20362036                 if (p->n_op == TEMP) {
 20372037                         BITSET(bb->gen, MKTOFF(b));
 20382038                 } else if (p->n_op == REG) {
 20392039                         BITSET(bb->gen, b);
 20402040                 } else if (optype(p->n_op) != LTYPE) {
 20412041                         if (XASMVAL(cw) == 'r')
 20422042                                 uerror("couldn't find available register");
 20432043                         else
 20442044                                 uerror("bad xasm node type2");
 20452045                 }
 20462046         }
 20472047 }
 20482048 
 20492049 /*
 20502050  * Do variable liveness analysis.  Only analyze the long-lived
 20512051  * variables, and save the live-on-exit temporaries in a bit-field
 20522052  * at the end of each basic block. This bit-field is later used
 20532053  * when doing short-range liveness analysis in Build().
 20542054  */
 20552055 void
 20562056 liveanal(struct p2env *p2e)
 20572057 {
 20582058         struct basicblock *bb;
 20592059         struct interpass *ip;
 20602060         bittype *saved;
 20612061         int mintemp, again;
 20622062 
 20632063         xbits = p2e->epp->ip_tmpnum - p2e->ipp->ip_tmpnum + MAXREGS;
 20642064         mintemp = p2e->ipp->ip_tmpnum;
 20652065 
 20662066         /* Just fetch space for the temporaries from heap */
 20672067         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 20682068                 BITALLOC(bb->gen,tmpalloc,xbits);
 20692069                 BITALLOC(bb->killed,tmpalloc,xbits);
 20702070                 BITALLOC(bb->in,tmpalloc,xbits);
 20712071                 BITALLOC(bb->out,tmpalloc,xbits);
 20722072         }
 20732073         BITALLOC(saved,tmpalloc,xbits);
 20742074 
 20752075         xxx = mintemp;
 20762076         /*
 20772077          * generate the gen-killed sets for all basic blocks.
 20782078          */
 20792079         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 20802080                 for (ip = bb->last; ; ip = DLIST_PREV(ip, qelem)) {
 20812081                         /* gen/killed is 'p', this node is 'n' */
 20822082                         if (ip->type == IP_NODE) {
 20832083                                 if (ip->ip_node->n_op == XASM)
 20842084                                         flist(ip->ip_node->n_left,
 20852085                                             xasmionize, bb);
 20862086                                 else
 20872087                                         unionize(ip->ip_node, bb, mintemp);
 20882088                         }
 20892089                         if (ip == bb->first)
 20902090                                 break;
 20912091                 }
 20922092                 memcpy(bb->in, bb->gen, BIT2BYTE(xbits));
 20932093 #ifdef PCC_DEBUG
 20942094 #define PRTRG(x) printf("%d ", x < MAXREGS ? x : x + p2e->ipp->ip_tmpnum-MAXREGS)
 20952095                 if (b2debug > 1) {
 20962096                         int i;
 20972097 
 20982098                         printf("basic block %d\ngen: ", bb->bbnum);
 20992099                         for (i = 0; i < xbits; i++)
 21002100                                 if (TESTBIT(bb->gen, i))
 21012101                                         PRTRG(i);
 21022102                         printf("\nkilled: ");
 21032103                         for (i = 0; i < xbits; i++)
 21042104                                 if (TESTBIT(bb->killed, i))
 21052105                                         PRTRG(i);
 21062106                         printf("\n");
 21072107                 }
 21082108 #endif
 21092109         }
 21102110         /* do liveness analysis on basic block level */
 21112111         do {
<>2112 -                struct cfgnode **cn;
  2112+                struct cfgnode *cn;
21132113                 int j;
 21142114 
 21152115                 again = 0;
 21162116                 /* XXX - loop should be in reversed execution-order */
 21172117                 DLIST_FOREACH_REVERSE(bb, &p2e->bblocks, bbelem) {
 21182118                         SETCOPY(saved, bb->out, j, xbits);
<>2119 -                        FORCH(cn, bb->ch) {
 2120 -                                SETSET(bb->out, cn[0]->bblock->in, j, xbits);
  2119+                        SLIST_FOREACH(cn, &bb->child, chld) {
  2120+                                SETSET(bb->out, cn->bblock->in, j, xbits);
<_21212121                         }
 21222122                         SETCMP(again, saved, bb->out, j, xbits);
 21232123                         SETCOPY(saved, bb->in, j, xbits);
 21242124                         SETCOPY(bb->in, bb->out, j, xbits);
 21252125                         SETCLEAR(bb->in, bb->killed, j, xbits);
 21262126                         SETSET(bb->in, bb->gen, j, xbits);
 21272127                         SETCMP(again, saved, bb->in, j, xbits);
 21282128                 }
 21292129         } while (again);
 21302130 
 21312131 #ifdef PCC_DEBUG
 21322132         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 21332133                 if (b2debug) {
 21342134                         int i;
 21352135 
 21362136                         printf("all basic block %d\nin: ", bb->bbnum);
 21372137                         for (i = 0; i < xbits; i++)
 21382138                                 if (TESTBIT(bb->in, i))
 21392139                                         PRTRG(i);
 21402140                         printf("\nout: ");
 21412141                         for (i = 0; i < xbits; i++)
 21422142                                 if (TESTBIT(bb->out, i))
 21432143                                         PRTRG(i);
 21442144                         printf("\n");
 21452145                 }
 21462146         }
 21472147 #endif
 21482148 }
FishEye: Open Source License registered to PCC.
Your maintenance has expired. You can renew your license at http://www.atlassian.com/fisheye/renew
Atlassian FishEye, CVS analysis. (Version:1.6.3 Build:build-336 2008-11-04) - Administration - Page generated 2014-10-01 18:20 +0200