Quick Search:

Mode

Context

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

Other Diffs

Ignore

Blank Lines Whitespace: Expand:

Diff

1.76
 
1.77
 
MAIN:ragge:20100521160828
 
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 /* main switch for new things not yet ready for all-day use */
 4747 /* #define ENABLE_NEW */
 4848 
 4949 
 5050 static int dfsnum;
 5151 
 5252 void saveip(struct interpass *ip);
 5353 void deljumps(struct p2env *);
 5454 void optdump(struct interpass *ip);
 5555 void printip(struct interpass *pole);
 5656 
 5757 static struct varinfo defsites;
 5858 struct interpass *storesave;
 5959 
 6060 void bblocks_build(struct p2env *);
 6161 void cfg_build(struct p2env *);
 6262 void cfg_dfs(struct basicblock *bb, unsigned int parent,
 6363              struct bblockinfo *bbinfo);
 6464 void dominators(struct p2env *);
 6565 struct basicblock *
 6666 ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo);
 6767 void link(struct basicblock *parent, struct basicblock *child);
 6868 void computeDF(struct p2env *, struct basicblock *bblock);
 6969 void printDF(struct p2env *p2e);
 7070 void findTemps(struct interpass *ip);
 7171 void placePhiFunctions(struct p2env *);
 7272 void renamevar(struct p2env *p2e,struct basicblock *bblock);
 7373 void removephi(struct p2env *p2e);
 7474 void remunreach(struct p2env *);
<> 75+static void liveanal(struct p2env *p2e);
7576 
 7677 /* create "proper" basic blocks, add labels where needed (so bblocks have labels) */
 7778 /* run before bb generate */
 7879 static void add_labels(struct p2env*) ;
 7980 
 8081 /* Perform trace scheduling, try to get rid of gotos as much as possible */
 8182 void TraceSchedule(struct p2env*) ;
 8283 
 8384 #ifdef ENABLE_NEW
 8485 static void do_cse(struct p2env* p2e) ;
 8586 #endif
 8687 
 8788 /* Walk the complete set, performing a function on each node.
 8889  * if type is given, apply function on only that type */
 8990 void WalkAll(struct p2env* p2e, void (*f) (NODE*, void*), void* arg, int type) ;
 9091 
 9192 void BBLiveDead(struct basicblock* bblock, int what, unsigned int variable) ;
 9293 
 9394 /* Fill the live/dead code */
 9495 void LiveDead(struct p2env* p2e, int what, unsigned int variable) ;
 9596 
 9697 #ifdef PCC_DEBUG
 9798 void printflowdiagram(struct p2env *, char *);
 9899 #endif
 99100 
 100101 void
 101102 optimize(struct p2env *p2e)
 102103 {
 103104         struct interpass *ipole = &p2e->ipole;
 104105 
 105106         if (b2debug) {
 106107                 printf("initial links\n");
 107108                 printip(ipole);
 108109         }
 109110 
 110111         if (xdeljumps)
 111112                 deljumps(p2e); /* Delete redundant jumps and dead code */
 112113 
 113114         if (xssaflag)
 114115                 add_labels(p2e) ;
 115116 #ifdef ENABLE_NEW
 116117         do_cse(p2e);
 117118 #endif
 118119 
 119120 #ifdef PCC_DEBUG
 120121         if (b2debug) {
 121122                 printf("links after deljumps\n");
 122123                 printip(ipole);
 123124         }
 124125 #endif
 125126         if (xssaflag || xtemps) {
 126127                 bblocks_build(p2e);
 127128                 BDEBUG(("Calling cfg_build\n"));
 128129                 cfg_build(p2e);
 129130         
 130131 #ifdef PCC_DEBUG
 131132                 printflowdiagram(p2e, "first");
 132133 #endif
 133134         }
 134135         if (xssaflag) {
<> 136+                BDEBUG(("Calling liveanal\n"));
  137+                liveanal(p2e);
135138                 BDEBUG(("Calling dominators\n"));
 136139                 dominators(p2e);
 137140                 BDEBUG(("Calling computeDF\n"));
 138141                 computeDF(p2e, DLIST_NEXT(&p2e->bblocks, bbelem));
 139142 
 140143                 if (b2debug) {
 141144                         printDF(p2e);
 142145                 }
 143146 
 144147                 BDEBUG(("Calling placePhiFunctions\n"));
 145148 
 146149                 placePhiFunctions(p2e);
 147150 
 148151                 BDEBUG(("Calling renamevar\n"));
 149152 
 150153                 renamevar(p2e,DLIST_NEXT(&p2e->bblocks, bbelem));
 151154 
 152155                 BDEBUG(("Calling removephi\n"));
 153156 
 154157 #ifdef PCC_DEBUG
 155158                 printflowdiagram(p2e, "ssa");
 156159 #endif
 157160 
 158161                 removephi(p2e);
 159162 
 160163                 BDEBUG(("Calling remunreach\n"));
 161164 /*              remunreach(p2e); */
 162165                 
 163166                 /*
 164167                  * Recalculate basic blocks and cfg that was destroyed
 165168                  * by removephi
 166169                  */
 167170                 /* first, clean up all what deljumps should have done, and more */
 168171 
 169172                 /* TODO: add the basic blocks done by the ssa code by hand.
 170173                  * The trace scheduler should not change the order in
 171174                  * which blocks are executed or what data is calculated.
 172175                  * Thus, the BBlock order should remain correct.
 173176                  */
 174177 
 175178 #ifdef ENABLE_NEW
 176179                 bblocks_build(p2e, &labinfo, &bbinfo);
 177180                 BDEBUG(("Calling cfg_build\n"));
 178181                 cfg_build(p2e, &labinfo);
 179182 
 180183                 TraceSchedule(p2e);
 181184 #ifdef PCC_DEBUG
 182185                 printflowdiagram(p2e, &labinfo, &bbinfo,"sched_trace");
 183186 
 184187                 if (b2debug) {
 185188                         printf("after tracesched\n");
 186189                         printip(ipole);
 187190                         fflush(stdout) ;
 188191                 }
 189192 #endif
 190193 #endif
 191194 
 192195                 /* Now, clean up the gotos we do not need any longer */
 193196                 if (xdeljumps)
 194197                         deljumps(p2e); /* Delete redundant jumps and dead code */
 195198 
 196199                 bblocks_build(p2e);
 197200                 BDEBUG(("Calling cfg_build\n"));
 198201                 cfg_build(p2e);
 199202 
 200203 #ifdef PCC_DEBUG
 201204                 printflowdiagram(p2e, "no_phi");
 202205 
 203206                 if (b2debug) {
 204207                         printf("new tree\n");
 205208                         printip(ipole);
 206209                 }
 207210 #endif
 208211         }
 209212 
 210213 #ifdef PCC_DEBUG
 211214         {
 212215                 int i;
 213216                 for (i = NIPPREGS; i--; )
 214217                         if (p2e->epp->ipp_regs[i] != 0)
 215218                                 comperr("register error");
 216219         }
 217220 #endif
 218221 
 219222         myoptim(ipole);
 220223 }
 221224 
 222225 /*
 223226  * Delete unused labels, excess of labels, gotos to gotos.
 224227  * This routine can be made much more efficient.
 225228  *
 226229  * Layout of the statement list here (_must_ look this way!):
 227230  *      PROLOG
 228231  *      LABEL   - states beginning of function argument moves
 229232  *      ...code to save/move arguments
 230233  *      LABEL   - states beginning of execution code
 231234  *      ...code + labels in function in function
 232235  *      EPILOG
 233236  *
 234237  * This version of deljumps is based on the c2 implementation
 235238  * that were included in 2BSD.
 236239  */
 237240 #define LABEL 1
 238241 #define JBR     2
 239242 #define CBR     3
 240243 #define STMT    4
 241244 #define EROU    5
 242245 struct dlnod {
 243246         int op;
 244247         struct interpass *dlip;
 245248         struct dlnod *forw;
 246249         struct dlnod *back;
 247250         struct dlnod *ref;
 248251         int labno;
 249252         int refc;
 250253 };
 251254 
 252255 #ifdef DLJDEBUG
 253256 static void
 254257 dumplink(struct dlnod *dl)
 255258 {
 256259         printf("dumplink %p\n", dl);
 257260         for (; dl; dl = dl->forw) {
 258261                 if (dl->op == STMT) {
 259262                         printf("STMT(%p)\n", dl);
 260263                         fwalk(dl->dlip->ip_node, e2print, 0);
 261264                 } else if (dl->op == EROU) {
 262265                         printf("EROU(%p)\n", dl);
 263266                 } else {
 264267                         static char *str[] = { 0, "LABEL", "JBR", "CBR" };
 265268                         printf("%s(%p) %d refc %d ref %p\n", str[dl->op],
 266269                             dl, dl->labno, dl->refc, dl->ref);
 267270                 }
 268271         }
 269272         printf("end dumplink\n");
 270273 }
 271274 #endif
 272275 
 273276 /*
 274277  * Create the linked list that we can work on.
 275278  */
 276279 static void
 277280 listsetup(struct interpass *ipole, struct dlnod *dl)
 278281 {
 279282         struct interpass *ip = DLIST_NEXT(ipole, qelem);
 280283         struct interpass *nip;
 281284         struct dlnod *p, *lastp;
 282285         NODE *q;
 283286 
 284287         lastp = dl;
 285288         while (ip->type != IP_DEFLAB)
 286289                 ip = DLIST_NEXT(ip,qelem);
 287290         ip = DLIST_NEXT(ip,qelem);
 288291         while (ip->type != IP_DEFLAB)
 289292                 ip = DLIST_NEXT(ip,qelem);
 290293         /* Now ip is at the beginning */
 291294         for (;;) {
 292295                 ip = DLIST_NEXT(ip,qelem);
 293296                 if (ip == ipole)
 294297                         break;
 295298                 p = tmpalloc(sizeof(struct dlnod));
 296299                 p->labno = 0;
 297300                 p->dlip = ip;
 298301                 switch (ip->type) {
 299302                 case IP_DEFLAB:
 300303                         p->op = LABEL;
 301304                         p->labno = ip->ip_lbl;
 302305                         break;
 303306 
 304307                 case IP_NODE:
 305308                         q = ip->ip_node;
 306309                         switch (q->n_op) {
 307310                         case GOTO:
 308311                                 p->op = JBR;
 309312                                 p->labno = q->n_left->n_lval;
 310313                                 break;
 311314                         case CBRANCH:
 312315                                 p->op = CBR;
 313316                                 p->labno = q->n_right->n_lval;
 314317                                 break;
 315318                         case ASSIGN:
 316319                                 /* remove ASSIGN to self for regs */
 317320                                 if (q->n_left->n_op == REG &&
 318321                                     q->n_right->n_op == REG &&
 319322                                     regno(q->n_left) == regno(q->n_right)) {
 320323                                         nip = DLIST_PREV(ip, qelem);
 321324                                         tfree(q);
 322325                                         DLIST_REMOVE(ip, qelem);
 323326                                         ip = nip;
 324327                                         continue;
 325328                                 }
 326329                                 /* FALLTHROUGH */
 327330                         default:
 328331                                 p->op = STMT;
 329332                                 break;
 330333                         }
 331334                         break;
 332335 
 333336                 case IP_ASM:
 334337                         p->op = STMT;
 335338                         break;
 336339 
 337340                 case IP_EPILOG:
 338341                         p->op = EROU;
 339342                         break;
 340343 
 341344                 default:
 342345                         comperr("listsetup: bad ip node %d", ip->type);
 343346                 }
 344347                 p->forw = 0;
 345348                 p->back = lastp;
 346349                 lastp->forw = p;
 347350                 lastp = p;
 348351                 p->ref = 0;
 349352         }
 350353 }
 351354 
 352355 static struct dlnod *
 353356 nonlab(struct dlnod *p)
 354357 {
 355358         while (p && p->op==LABEL)
 356359                 p = p->forw;
 357360         return(p);
 358361 }
 359362 
 360363 static void
 361364 iprem(struct dlnod *p)
 362365 {
 363366         if (p->dlip->type == IP_NODE)
 364367                 tfree(p->dlip->ip_node);
 365368         DLIST_REMOVE(p->dlip, qelem);
 366369 }
 367370 
 368371 static void
 369372 decref(struct dlnod *p)
 370373 {
 371374         if (--p->refc <= 0) {
 372375                 iprem(p);
 373376                 p->back->forw = p->forw;
 374377                 p->forw->back = p->back;
 375378         }
 376379 }
 377380 
 378381 static void
 379382 setlab(struct dlnod *p, int labno)
 380383 {
 381384         p->labno = labno;
 382385         if (p->op == JBR)
 383386                 p->dlip->ip_node->n_left->n_lval = labno;
 384387         else if (p->op == CBR) {
 385388                 p->dlip->ip_node->n_right->n_lval = labno;
 386389                 p->dlip->ip_node->n_left->n_label = labno;
 387390         } else
 388391                 comperr("setlab bad op %d", p->op);
 389392 }
 390393 
 391394 /*
 392395  * Label reference counting and removal of unused labels.
 393396  */
 394397 #define LABHS 127
 395398 static void
 396399 refcount(struct p2env *p2e, struct dlnod *dl)
 397400 {
 398401         struct dlnod *p, *lp;
 399402         struct dlnod *labhash[LABHS];
 400403         struct dlnod **hp, *tp;
 401404 
 402405         /* Clear label hash */
 403406         for (hp = labhash; hp < &labhash[LABHS];)
 404407                 *hp++ = 0;
 405408         /* Enter labels into hash.  Later overwrites earlier */
 406409         for (p = dl->forw; p!=0; p = p->forw)
 407410                 if (p->op==LABEL) {
 408411                         labhash[p->labno % LABHS] = p;
 409412                         p->refc = 0;
 410413                 }
 411414 
 412415         /* search for jumps to labels and fill in reference */
 413416         for (p = dl->forw; p!=0; p = p->forw) {
 414417                 if (p->op==JBR || p->op==CBR) {
 415418                         p->ref = 0;
 416419                         lp = labhash[p->labno % LABHS];
 417420                         if (lp==0 || p->labno!=lp->labno)
 418421                             for (lp = dl->forw; lp!=0; lp = lp->forw) {
 419422                                 if (lp->op==LABEL && p->labno==lp->labno)
 420423                                         break;
 421424                             }
 422425                         if (lp) {
 423426                                 tp = nonlab(lp)->back;
 424427                                 if (tp!=lp) {
 425428                                         setlab(p, tp->labno);
 426429                                         lp = tp;
 427430                                 }
 428431                                 p->ref = lp;
 429432                                 lp->refc++;
 430433                         }
 431434                 }
 432435         }
 433436         for (p = dl->forw; p!=0; p = p->forw)
 434437                 if (p->op==LABEL && p->refc==0 && (lp = nonlab(p))->op)
 435438                         decref(p);
 436439 }
 437440 
 438441 static int nchange;
 439442 
 440443 static struct dlnod *
 441444 codemove(struct dlnod *p)
 442445 {
 443446         struct dlnod *p1, *p2, *p3;
 444447 #ifdef notyet
 445448         struct dlnod *t, *tl;
 446449         int n;
 447450 #endif
 448451 
 449452         p1 = p;
 450453         if (p1->op!=JBR || (p2 = p1->ref)==0)
 451454                 return(p1);
 452455         while (p2->op == LABEL)
 453456                 if ((p2 = p2->back) == 0)
 454457                         return(p1);
 455458         if (p2->op!=JBR)
 456459                 goto ivloop;
 457460         if (p1==p2)
 458461                 return(p1);
 459462         p2 = p2->forw;
 460463         p3 = p1->ref;
 461464         while (p3) {
 462465                 if (p3->op==JBR) {
 463466                         if (p1==p3 || p1->forw==p3 || p1->back==p3)
 464467                                 return(p1);
 465468                         nchange++;
 466469                         p1->back->forw = p2;
 467470                         p1->dlip->qelem.q_back->qelem.q_forw = p2->dlip;
 468471 
 469472                         p1->forw->back = p3;
 470473                         p1->dlip->qelem.q_forw->qelem.q_back = p3->dlip;
 471474 
 472475 
 473476                         p2->back->forw = p3->forw;
 474477                         p2->dlip->qelem.q_back->qelem.q_forw = p3->forw->dlip;
 475478 
 476479                         p3->forw->back = p2->back;
 477480                         p3->dlip->qelem.q_forw->qelem.q_back = p2->back->dlip;
 478481 
 479482                         p2->back = p1->back;
 480483                         p2->dlip->qelem.q_back = p1->dlip->qelem.q_back;
 481484 
 482485                         p3->forw = p1->forw;
 483486                         p3->dlip->qelem.q_forw = p1->forw->dlip;
 484487 
 485488                         decref(p1->ref);
 486489                         if (p1->dlip->type == IP_NODE)
 487490                                 tfree(p1->dlip->ip_node);
 488491 
 489492                         return(p2);
 490493                 } else
 491494                         p3 = p3->forw;
 492495         }
 493496         return(p1);
 494497 
 495498 ivloop:
 496499         if (p1->forw->op!=LABEL)
 497500                 return(p1);
 498501         return(p1);
 499502 
 500503 #ifdef notyet
 501504         p3 = p2 = p2->forw;
 502505         n = 16;
 503506         do {
 504507                 if ((p3 = p3->forw) == 0 || p3==p1 || --n==0)
 505508                         return(p1);
 506509         } while (p3->op!=CBR || p3->labno!=p1->forw->labno);
 507510         do
 508511                 if ((p1 = p1->back) == 0)
 509512                         return(p);
 510513         while (p1!=p3);
 511514         p1 = p;
 512515         tl = insertl(p1);
 513516         p3->subop = revbr[p3->subop];
 514517         decref(p3->ref);
 515518                 p2->back->forw = p1;
 516519         p3->forw->back = p1;
 517520         p1->back->forw = p2;
 518521         p1->forw->back = p3;
 519522         t = p1->back;
 520523         p1->back = p2->back;
 521524         p2->back = t;
 522525         t = p1->forw;
 523526         p1->forw = p3->forw;
 524527         p3->forw = t;
 525528         p2 = insertl(p1->forw);
 526529         p3->labno = p2->labno;
 527530         p3->ref = p2;
 528531         decref(tl);
 529532         if (tl->refc<=0)
 530533                 nrlab--;
 531534         nchange++;
 532535         return(p3);
 533536 #endif
 534537 }
 535538 
 536539 static void
 537540 iterate(struct p2env *p2e, struct dlnod *dl)
 538541 {
 539542         struct dlnod *p, *rp, *p1;
 540543         extern int negrel[];
 541544         extern size_t negrelsize;
 542545         int i;
 543546 
 544547         nchange = 0;
 545548         for (p = dl->forw; p!=0; p = p->forw) {
 546549                 if ((p->op==JBR||p->op==CBR) && p->ref) {
 547550                         /* Resolves:
 548551                          * jbr L7
 549552                          * ...
 550553                          * L7: jbr L8
 551554                          */
 552555                         rp = nonlab(p->ref);
 553556                         if (rp->op==JBR && rp->labno && p->labno!=rp->labno) {
 554557                                 setlab(p, rp->labno);
 555558                                 decref(p->ref);
 556559                                 rp->ref->refc++;
 557560                                 p->ref = rp->ref;
 558561                                 nchange++;
 559562                         }
 560563                 }
 561564                 if (p->op==CBR && (p1 = p->forw)->op==JBR) {
 562565                         /* Resolves:
 563566                          * cbr L7
 564567                          * jbr L8
 565568                          * L7:
 566569                          */
 567570                         rp = p->ref;
 568571                         do
 569572                                 rp = rp->back;
 570573                         while (rp->op==LABEL);
 571574                         if (rp==p1) {
 572575                                 decref(p->ref);
 573576                                 p->ref = p1->ref;
 574577                                 setlab(p, p1->labno);
 575578 
 576579                                 iprem(p1);
 577580 
 578581                                 p1->forw->back = p;
 579582                                 p->forw = p1->forw;
 580583 
 581584                                 i = p->dlip->ip_node->n_left->n_op;
 582585                                 if (i < EQ || i - EQ >= (int)negrelsize)
 583586                                         comperr("deljumps: unexpected op");
 584587                                 p->dlip->ip_node->n_left->n_op = negrel[i - EQ];
 585588                                 nchange++;
 586589                         }
 587590                 }
 588591                 if (p->op == JBR) {
 589592                         /* Removes dead code */
 590593                         while (p->forw && p->forw->op!=LABEL &&
 591594                             p->forw->op!=EROU) {
 592595                                 nchange++;
 593596                                 if (p->forw->ref)
 594597                                         decref(p->forw->ref);
 595598 
 596599                                 iprem(p->forw);
 597600 
 598601                                 p->forw = p->forw->forw;
 599602                                 p->forw->back = p;
 600603                         }
 601604                         rp = p->forw;
 602605                         while (rp && rp->op==LABEL) {
 603606                                 if (p->ref == rp) {
 604607                                         p->back->forw = p->forw;
 605608                                         p->forw->back = p->back;
 606609                                         iprem(p);
 607610                                         p = p->back;
 608611                                         decref(rp);
 609612                                         nchange++;
 610613                                         break;
 611614                                 }
 612615                                 rp = rp->forw;
 613616                         }
 614617                 }
 615618                 if (p->op == JBR) {
 616619                         /* xjump(p); * needs tree rewrite; not yet */
 617620                         p = codemove(p);
 618621                 }
 619622         }
 620623 }
 621624 
 622625 void
 623626 deljumps(struct p2env *p2e)
 624627 {
 625628         struct interpass *ipole = &p2e->ipole;
 626629         struct dlnod dln;
 627630         MARK mark;
 628631 
 629632         markset(&mark);
 630633 
 631634         memset(&dln, 0, sizeof(dln));
 632635         listsetup(ipole, &dln);
 633636         do {
 634637                 refcount(p2e, &dln);
 635638                 do {
 636639                         iterate(p2e, &dln);
 637640                 } while (nchange);
 638641 #ifdef notyet
 639642                 comjump();
 640643 #endif
 641644         } while (nchange);
 642645 
 643646         markfree(&mark);
 644647 }
 645648 
 646649 void
 647650 optdump(struct interpass *ip)
 648651 {
 649652         static char *nm[] = { "node", "prolog", "newblk", "epilog", "locctr",
 650653                 "deflab", "defnam", "asm" };
 651654         printf("type %s\n", nm[ip->type-1]);
 652655         switch (ip->type) {
 653656         case IP_NODE:
 654657 #ifdef PCC_DEBUG
 655658                 fwalk(ip->ip_node, e2print, 0);
 656659 #endif
 657660                 break;
 658661         case IP_DEFLAB:
 659662                 printf("label " LABFMT "\n", ip->ip_lbl);
 660663                 break;
 661664         case IP_ASM:
 662665                 printf(": %s\n", ip->ip_asm);
 663666                 break;
 664667         }
 665668 }
 666669 
 667670 /*
 668671  * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
 669672  *
 670673  * Also fills the labelinfo struct with information about which bblocks
 671674  * that contain which label.
 672675  */
 673676 
 674677 void
 675678 bblocks_build(struct p2env *p2e)
 676679 {
 677680         struct interpass *ipole = &p2e->ipole;
 678681         struct interpass *ip;
 679682         struct basicblock *bb = NULL;
 680683         int low, high;
 681684         int count = 0;
 682685         int i;
 683686 
 684687         BDEBUG(("bblocks_build (%p, %p)\n", &p2e->labinfo, &p2e->bbinfo));
 685688         low = p2e->ipp->ip_lblnum;
 686689         high = p2e->epp->ip_lblnum;
 687690 
 688691         /*
 689692          * First statement is a leader.
 690693          * Any statement that is target of a jump is a leader.
 691694          * Any statement that immediately follows a jump is a leader.
 692695          */
 693696         DLIST_INIT(&p2e->bblocks, bbelem);
 694697         DLIST_FOREACH(ip, ipole, qelem) {
 695698                 if (bb == NULL || (ip->type == IP_EPILOG) ||
 696699                     (ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) {
 697700                         bb = tmpalloc(sizeof(struct basicblock));
 698701                         bb->first = ip;
 699702                         SLIST_INIT(&bb->children);
 700703                         SLIST_INIT(&bb->parents);
 701704                         bb->dfnum = 0;
 702705                         bb->dfparent = 0;
 703706                         bb->semi = 0;
 704707                         bb->ancestor = 0;
 705708                         bb->idom = 0;
 706709                         bb->samedom = 0;
 707710                         bb->bucket = NULL;
 708711                         bb->df = NULL;
 709712                         bb->dfchildren = NULL;
 710713                         bb->Aorig = NULL;
 711714                         bb->Aphi = NULL;
 712715                         SLIST_INIT(&bb->phi);
 713716                         bb->bbnum = count;
 714717                         DLIST_INSERT_BEFORE(&p2e->bblocks, bb, bbelem);
 715718                         count++;
 716719                 }
 717720                 bb->last = ip;
 718721                 if ((ip->type == IP_NODE) && (ip->ip_node->n_op == GOTO ||
 719722                     ip->ip_node->n_op == CBRANCH))
 720723                         bb = NULL;
 721724                 if (ip->type == IP_PROLOG)
 722725                         bb = NULL;
 723726         }
 724727         p2e->nbblocks = count;
 725728 
 726729         if (b2debug) {
 727730                 printf("Basic blocks in func: %d, low %d, high %d\n",
 728731                     count, low, high);
 729732                 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 730733                         printf("bb(%d) %p: first %p last %p\n", bb->bbnum, bb,
 731734                             bb->first, bb->last);
 732735                 }
 733736         }
 734737 
 735738         p2e->labinfo.low = low;
 736739         p2e->labinfo.size = high - low + 1;
 737740         p2e->labinfo.arr = tmpalloc(p2e->labinfo.size * sizeof(struct basicblock *));
 738741         for (i = 0; i < p2e->labinfo.size; i++) {
 739742                 p2e->labinfo.arr[i] = NULL;
 740743         }
 741744         
 742745         p2e->bbinfo.size = count + 1;
 743746         p2e->bbinfo.arr = tmpalloc(p2e->bbinfo.size * sizeof(struct basicblock *));
 744747         for (i = 0; i < p2e->bbinfo.size; i++) {
 745748                 p2e->bbinfo.arr[i] = NULL;
 746749         }
 747750 
 748751         /* Build the label table */
 749752         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 750753                 if (bb->first->type == IP_DEFLAB)
 751754                         p2e->labinfo.arr[bb->first->ip_lbl - low] = bb;
 752755         }
 753756 
 754757         if (b2debug) {
 755758                 static void printip2(struct interpass *);
 756759                 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 757760                         printf("bblock %d\n", bb->bbnum);
 758761                         for (ip = bb->first; ip != bb->last;
 759762                             ip = DLIST_NEXT(ip, qelem)) {
 760763                                 printip2(ip);
 761764                         }
 762765                         printip2(ip);
 763766                 }
 764767 
 765768                 printf("Label table:\n");
 766769                 for (i = 0; i < p2e->labinfo.size; i++)
 767770                         if (p2e->labinfo.arr[i])
 768771                                 printf("Label %d bblock %p\n", i+low,
 769772                                     p2e->labinfo.arr[i]);
 770773         }
 771774 }
 772775 
 773776 /*
 774777  * Build the control flow graph.
 775778  */
 776779 
 777780 void
 778781 cfg_build(struct p2env *p2e)
 779782 {
 780783         /* Child and parent nodes */
 781784         struct cfgnode *cnode;
 782785         struct cfgnode *pnode;
 783786         struct basicblock *bb;
 784787         
 785788         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 786789 
 787790                 if (bb->first->type == IP_EPILOG) {
 788791                         break;
 789792                 }
 790793 
 791794                 cnode = tmpalloc(sizeof(struct cfgnode));
 792795                 pnode = tmpalloc(sizeof(struct cfgnode));
 793796                 pnode->bblock = bb;
 794797 
 795798                 if ((bb->last->type == IP_NODE) &&
 796799                     (bb->last->ip_node->n_op == GOTO) &&
 797800                     (bb->last->ip_node->n_left->n_op == ICON))  {
 798801                         if (bb->last->ip_node->n_left->n_lval - p2e->labinfo.low >
 799802                             p2e->labinfo.size) {
 800803                                 comperr("Label out of range: %d, base %d",
 801804                                         bb->last->ip_node->n_left->n_lval,
 802805                                         p2e->labinfo.low);
 803806                         }
 804807                         cnode->bblock = p2e->labinfo.arr[bb->last->ip_node->n_left->n_lval - p2e->labinfo.low];
 805808                         SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 806809                         SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 807810                         continue;
 808811                 }
 809812                 if ((bb->last->type == IP_NODE) &&
 810813                     (bb->last->ip_node->n_op == CBRANCH)) {
 811814                         if (bb->last->ip_node->n_right->n_lval - p2e->labinfo.low >
 812815                             p2e->labinfo.size)
 813816                                 comperr("Label out of range: %d",
 814817                                         bb->last->ip_node->n_left->n_lval);
 815818 
 816819                         cnode->bblock = p2e->labinfo.arr[bb->last->ip_node->n_right->n_lval - p2e->labinfo.low];
 817820                         SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 818821                         SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 819822                         cnode = tmpalloc(sizeof(struct cfgnode));
 820823                         pnode = tmpalloc(sizeof(struct cfgnode));
 821824                         pnode->bblock = bb;
 822825                 }
 823826 
 824827                 cnode->bblock = DLIST_NEXT(bb, bbelem);
 825828                 SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 826829                 SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 827830         }
 828831 }
 829832 
 830833 void
 831834 cfg_dfs(struct basicblock *bb, unsigned int parent, struct bblockinfo *bbinfo)
 832835 {
 833836         struct cfgnode *cnode;
 834837         
 835838         if (bb->dfnum != 0)
 836839                 return;
 837840 
 838841         bb->dfnum = ++dfsnum;
 839842         bb->dfparent = parent;
 840843         bbinfo->arr[bb->dfnum] = bb;
 841844         SLIST_FOREACH(cnode, &bb->children, cfgelem) {
 842845                 cfg_dfs(cnode->bblock, bb->dfnum, bbinfo);
 843846         }
 844847         /* Don't bring in unreachable nodes in the future */
 845848         bbinfo->size = dfsnum + 1;
 846849 }
 847850 
 848851 static bittype *
 849852 setalloc(int nelem)
 850853 {
 851854         bittype *b;
 852855         int sz = (nelem+NUMBITS-1)/NUMBITS;
 853856 
 854857         b = tmpalloc(sz * sizeof(bittype));
 855858         memset(b, 0, sz * sizeof(bittype));
 856859         return b;
 857860 }
 858861 
 859862 /*
 860863  * Algorithm 19.9, pp 414 from Appel.
 861864  */
 862865 
 863866 void
 864867 dominators(struct p2env *p2e)
 865868 {
 866869         struct cfgnode *cnode;
 867870         struct basicblock *bb, *y, *v;
 868871         struct basicblock *s, *sprime, *p;
 869872         int h, i;
 870873 
 871874         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 872875                 bb->bucket = setalloc(p2e->bbinfo.size);
 873876                 bb->df = setalloc(p2e->bbinfo.size);
 874877                 bb->dfchildren = setalloc(p2e->bbinfo.size);
 875878         }
 876879 
 877880         dfsnum = 0;
 878881         cfg_dfs(DLIST_NEXT(&p2e->bblocks, bbelem), 0, &p2e->bbinfo);
 879882 
 880883         if (b2debug) {
 881884                 struct basicblock *bbb;
 882885                 struct cfgnode *ccnode;
 883886 
 884887                 DLIST_FOREACH(bbb, &p2e->bblocks, bbelem) {
 885888                         printf("Basic block %d, parents: ", bbb->dfnum);
 886889                         SLIST_FOREACH(ccnode, &bbb->parents, cfgelem) {
 887890                                 printf("%d, ", ccnode->bblock->dfnum);
 888891                         }
 889892                         printf("\nChildren: ");
 890893                         SLIST_FOREACH(ccnode, &bbb->children, cfgelem) {
 891894                                 printf("%d, ", ccnode->bblock->dfnum);
 892895                         }
 893896                         printf("\n");
 894897                 }
 895898         }
 896899 
 897900         for(h = p2e->bbinfo.size - 1; h > 1; h--) {
 898901                 bb = p2e->bbinfo.arr[h];
 899902                 p = s = p2e->bbinfo.arr[bb->dfparent];
 900903                 SLIST_FOREACH(cnode, &bb->parents, cfgelem) {
 901904                         if (cnode->bblock->dfnum ==0)
 902905                                 continue; /* Ignore unreachable code */
 903906 
 904907                         if (cnode->bblock->dfnum <= bb->dfnum)
 905908                                 sprime = cnode->bblock;
 906909                         else
 907910                                 sprime = p2e->bbinfo.arr[ancestorwithlowestsemi
 908911                                               (cnode->bblock, &p2e->bbinfo)->semi];
 909912                         if (sprime->dfnum < s->dfnum)
 910913                                 s = sprime;
 911914                 }
 912915                 bb->semi = s->dfnum;
 913916                 BITSET(s->bucket, bb->dfnum);
 914917                 link(p, bb);
 915918                 for (i = 1; i < p2e->bbinfo.size; i++) {
 916919                         if(TESTBIT(p->bucket, i)) {
 917920                                 v = p2e->bbinfo.arr[i];
 918921                                 y = ancestorwithlowestsemi(v, &p2e->bbinfo);
 919922                                 if (y->semi == v->semi)
 920923                                         v->idom = p->dfnum;
 921924                                 else
 922925                                         v->samedom = y->dfnum;
 923926                         }
 924927                 }
 925928                 memset(p->bucket, 0, (p2e->bbinfo.size + 7)/8);
 926929         }
 927930 
 928931         if (b2debug) {
 929932                 printf("Num\tSemi\tAncest\tidom\n");
 930933                 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 931934                         printf("%d\t%d\t%d\t%d\n", bb->dfnum, bb->semi,
 932935                             bb->ancestor, bb->idom);
 933936                 }
 934937         }
 935938 
 936939         for(h = 2; h < p2e->bbinfo.size; h++) {
 937940                 bb = p2e->bbinfo.arr[h];
 938941                 if (bb->samedom != 0) {
 939942                         bb->idom = p2e->bbinfo.arr[bb->samedom]->idom;
 940943                 }
 941944         }
 942945         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 943946                 if (bb->idom != 0 && bb->idom != bb->dfnum) {
 944947                         BDEBUG(("Setting child %d of %d\n",
 945948                             bb->dfnum, p2e->bbinfo.arr[bb->idom]->dfnum));
 946949                         BITSET(p2e->bbinfo.arr[bb->idom]->dfchildren, bb->dfnum);
 947950                 }
 948951         }
 949952 }
 950953 
 951954 
 952955 struct basicblock *
 953956 ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo)
 954957 {
 955958         struct basicblock *u = bblock;
 956959         struct basicblock *v = bblock;
 957960 
 958961         while (v->ancestor != 0) {
 959962                 if (bbinfo->arr[v->semi]->dfnum <
 960963                     bbinfo->arr[u->semi]->dfnum)
 961964                         u = v;
 962965                 v = bbinfo->arr[v->ancestor];
 963966         }
 964967         return u;
 965968 }
 966969 
 967970 void
 968971 link(struct basicblock *parent, struct basicblock *child)
 969972 {
 970973         child->ancestor = parent->dfnum;
 971974 }
 972975 
 973976 void
 974977 computeDF(struct p2env *p2e, struct basicblock *bblock)
 975978 {
 976979         struct cfgnode *cnode;
 977980         int h, i;
 978981         
 979982         SLIST_FOREACH(cnode, &bblock->children, cfgelem) {
 980983                 if (cnode->bblock->idom != bblock->dfnum)
 981984                         BITSET(bblock->df, cnode->bblock->dfnum);
 982985         }
 983986         for (h = 1; h < p2e->bbinfo.size; h++) {
 984987                 if (!TESTBIT(bblock->dfchildren, h))
 985988                         continue;
 986989                 computeDF(p2e, p2e->bbinfo.arr[h]);
 987990                 for (i = 1; i < p2e->bbinfo.size; i++) {
 988991                         if (TESTBIT(p2e->bbinfo.arr[h]->df, i) &&
 989992                             (p2e->bbinfo.arr[i] == bblock ||
 990993                              (bblock->dfnum != p2e->bbinfo.arr[i]->idom)))
 991994                             BITSET(bblock->df, i);
 992995                 }
 993996         }
 994997 }
 995998 
 996999 void printDF(struct p2env *p2e)
 9971000 {
 9981001         struct basicblock *bb;
 9991002         int i;
 10001003 
 10011004         printf("Dominance frontiers:\n");
 10021005    
 10031006         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 10041007                 printf("bb %d : ", bb->dfnum);
 10051008         
 10061009                 for (i=1; i < p2e->bbinfo.size;i++) {
 10071010                         if (TESTBIT(bb->df,i)) {
 10081011                                 printf("%d ",i);
 10091012                         }
 10101013                 }
 10111014            
 10121015                 printf("\n");
 10131016         }
 10141017    
 10151018 }
 10161019 
 10171020 
 10181021 
 10191022 static struct basicblock *currbb;
 10201023 static struct interpass *currip;
 10211024 
 10221025 /* Helper function for findTemps, Find assignment nodes. */
 10231026 static void
 10241027 searchasg(NODE *p, void *arg)
 10251028 {
 10261029         struct pvarinfo *pv;
 10271030         int tempnr;
 10281031         struct varstack *stacke;
 10291032    
 10301033         if (p->n_op != ASSIGN)
 10311034                 return;
 10321035 
 10331036         if (p->n_left->n_op != TEMP)
 10341037                 return;
 10351038 
 10361039         tempnr=regno(p->n_left)-defsites.low;
 10371040    
 10381041         BITSET(currbb->Aorig, tempnr);
 10391042         
 10401043         pv = tmpcalloc(sizeof(struct pvarinfo));
 10411044         pv->next = defsites.arr[tempnr];
 10421045         pv->bb = currbb;
 10431046         pv->n_type = p->n_left->n_type;
 10441047         
 10451048         defsites.arr[tempnr] = pv;
 10461049         
 10471050         
 10481051         if (SLIST_FIRST(&defsites.stack[tempnr])==NULL) {
 10491052                 stacke=tmpcalloc(sizeof (struct varstack));
 10501053                 stacke->tmpregno=0;
 10511054                 SLIST_INSERT_FIRST(&defsites.stack[tempnr],stacke,varstackelem);
 10521055         }
 10531056 }
 10541057 
 10551058 /* Walk the interpass looking for assignment nodes. */
 10561059 void findTemps(struct interpass *ip)
 10571060 {
 10581061         if (ip->type != IP_NODE)
 10591062                 return;
 10601063 
 10611064         currip = ip;
 10621065 
 10631066         walkf(ip->ip_node, searchasg, 0);
 10641067 }
 10651068 
 10661069 /*
 10671070  * Algorithm 19.6 from Appel.
 10681071  */
 10691072 
 10701073 void
 10711074 placePhiFunctions(struct p2env *p2e)
 10721075 {
 10731076         struct basicblock *bb;
 10741077         struct basicblock *y;
 10751078         struct interpass *ip;
 10761079         int maxtmp, i, j, k;
 10771080         struct pvarinfo *n;
 10781081         struct cfgnode *cnode;
 10791082         TWORD ntype;
 10801083         struct pvarinfo *pv;
 10811084         struct phiinfo *phi;
 10821085         int phifound;
 10831086 
 10841087         bb = DLIST_NEXT(&p2e->bblocks, bbelem);
 10851088         defsites.low = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
 10861089         bb = DLIST_PREV(&p2e->bblocks, bbelem);
 10871090         maxtmp = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
 10881091         defsites.size = maxtmp - defsites.low + 1;
 10891092         defsites.arr = tmpcalloc(defsites.size*sizeof(struct pvarinfo *));
 10901093         defsites.stack = tmpcalloc(defsites.size*sizeof(SLIST_HEAD(, varstack)));
 10911094         
 10921095         for (i=0;i<defsites.size;i++)
 10931096                 SLIST_INIT(&defsites.stack[i]); 
 10941097         
 10951098         /* Find all defsites */
 10961099         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 10971100                 currbb = bb;
 10981101                 ip = bb->first;
 10991102                 bb->Aorig = setalloc(defsites.size);
 11001103                 bb->Aphi = setalloc(defsites.size);
 11011104                 
 11021105                 while (ip != bb->last) {
 11031106                         findTemps(ip);
 11041107                         ip = DLIST_NEXT(ip, qelem);
 11051108                 }
 11061109                 /* Make sure we get the last statement in the bblock */
 11071110                 findTemps(ip);
 11081111         }
 11091112 
 11101113         /* For each variable */
 11111114         for (i = 0; i < defsites.size; i++) {
 11121115                 /* While W not empty */
 11131116                 while (defsites.arr[i] != NULL) {
 11141117                         /* Remove some node n from W */
 11151118                         n = defsites.arr[i];
 11161119                         defsites.arr[i] = n->next;
 11171120                         /* For each y in n->bb->df */
 11181121                         for (j = 0; j < p2e->bbinfo.size; j++) {
 11191122                                 if (!TESTBIT(n->bb->df, j))
 11201123                                         continue;
 11211124                                 
 11221125                                 if (TESTBIT(p2e->bbinfo.arr[j]->Aphi, i))
 11231126                                         continue;
 11241127 
 11251128                                 y=p2e->bbinfo.arr[j];
 11261129                                 ntype = n->n_type;
 11271130                                 k = 0;
 11281131                                 /* Amount of predecessors for y */
 11291132                                 SLIST_FOREACH(cnode, &y->parents, cfgelem)
 11301133                                         k++;
 11311134                                 /* Construct phi(...)
 11321135                                 */
 11331136                            
 11341137                                 phifound=0;
 11351138                            
 11361139                                 SLIST_FOREACH(phi, &y->phi, phielem) {
 11371140                                     if (phi->tmpregno==i+defsites.low)
 11381141                                         phifound++;
 11391142                                 }
 11401143                            
 11411144                                 if (phifound==0) {
 11421145                                         if (b2debug)
 11431146                                             printf("Phi in %d(%d) (%p) for %d\n",
 11441147                                             y->dfnum,y->bbnum,y,i+defsites.low);
 11451148 
<> 1149+                                        /* If no live in, no phi node needed */
  1150+                                        if (!TESTBIT(y->in,
  1151+                                            (i+defsites.low-p2e->ipp->ip_tmpnum+MAXREGS))) {
  1152+                                        if (b2debug)
  1153+                                        printf("tmp %d bb %d unused, no phi\n",
  1154+                                            i+defsites.low, y->bbnum);
  1155+                                                /* No live in */
  1156+                                                BITSET(p2e->bbinfo.arr[j]->Aphi, i);
  1157+                                                continue;
  1158+                                        }
  1159+
11461160                                         phi = tmpcalloc(sizeof(struct phiinfo));
 11471161                            
 11481162                                         phi->tmpregno=i+defsites.low;
 11491163                                         phi->size=k;
 11501164                                         phi->n_type=ntype;
 11511165                                         phi->intmpregno=tmpcalloc(k*sizeof(int));
 11521166                            
 11531167                                         SLIST_INSERT_LAST(&y->phi,phi,phielem);
 11541168                                 } else {
 11551169                                     if (b2debug)
 11561170                                         printf("Phi already in %d for %d\n",y->dfnum,i+defsites.low);
 11571171                                 }
 11581172 
 11591173                                 BITSET(p2e->bbinfo.arr[j]->Aphi, i);
 11601174                                 if (!TESTBIT(p2e->bbinfo.arr[j]->Aorig, i)) {
 11611175                                         pv = tmpalloc(sizeof(struct pvarinfo));
 11621176                                         pv->bb = y;
 11631177                                         pv->n_type=ntype;
 11641178                                         pv->next = defsites.arr[i];
 11651179                                         defsites.arr[i] = pv;
 11661180                                 }
<>1167 -                                        
 1168 -
11691181                         }
 11701182                 }
 11711183         }
 11721184 }
 11731185 
 11741186 /* Helper function for renamevar. */
 11751187 static void
 11761188 renamevarhelper(struct p2env *p2e,NODE *t,void *poplistarg)
 11771189 {       
 11781190         SLIST_HEAD(, varstack) *poplist=poplistarg;
 11791191         int opty;
 11801192         int tempnr;
 11811193         int newtempnr;
 11821194         int x;
 11831195         struct varstack *stacke;
 11841196         
 11851197         if (t->n_op == ASSIGN && t->n_left->n_op == TEMP) {
 11861198                 renamevarhelper(p2e,t->n_right,poplist);
 11871199                                 
 11881200                 tempnr=regno(t->n_left)-defsites.low;
 11891201                 
 11901202                 newtempnr=p2e->epp->ip_tmpnum++;
 11911203                 regno(t->n_left)=newtempnr;
 11921204                 
 11931205                 stacke=tmpcalloc(sizeof (struct varstack));
 11941206                 stacke->tmpregno=newtempnr;
 11951207                 SLIST_INSERT_FIRST(&defsites.stack[tempnr],stacke,varstackelem);
 11961208                 
 11971209                 stacke=tmpcalloc(sizeof (struct varstack));
 11981210                 stacke->tmpregno=tempnr;
 11991211                 SLIST_INSERT_FIRST(poplist,stacke,varstackelem);
 12001212         } else {
 12011213                 if (t->n_op == TEMP) {
 12021214                         tempnr=regno(t)-defsites.low;
 12031215                 
 12041216                         if (SLIST_FIRST(&defsites.stack[tempnr])!=NULL) {
 12051217                                 x=SLIST_FIRST(&defsites.stack[tempnr])->tmpregno;
 12061218                                 regno(t)=x;
 12071219                         }
 12081220                 }
 12091221                 
 12101222                 opty = optype(t->n_op);
 12111223                 
 12121224                 if (opty != LTYPE)
 12131225                         renamevarhelper(p2e, t->n_left,poplist);
 12141226                 if (opty == BITYPE)
 12151227                         renamevarhelper(p2e, t->n_right,poplist);
 12161228         }
 12171229 }
 12181230 
 12191231 
 12201232 void
 12211233 renamevar(struct p2env *p2e,struct basicblock *bb)
 12221234 {
 12231235         struct interpass *ip;
 12241236         int h,j;
 12251237         SLIST_HEAD(, varstack) poplist;
 12261238         struct varstack *stacke;
 12271239         struct cfgnode *cfgn;
 12281240         struct cfgnode *cfgn2;
 12291241         int tmpregno,newtmpregno;
 12301242         struct phiinfo *phi;
 12311243 
 12321244         SLIST_INIT(&poplist);
 12331245 
 12341246         SLIST_FOREACH(phi,&bb->phi,phielem) {
 12351247                 tmpregno=phi->tmpregno-defsites.low;
 12361248                 
 12371249                 newtmpregno=p2e->epp->ip_tmpnum++;
 12381250                 phi->newtmpregno=newtmpregno;
 12391251 
 12401252                 stacke=tmpcalloc(sizeof (struct varstack));
 12411253                 stacke->tmpregno=newtmpregno;
 12421254                 SLIST_INSERT_FIRST(&defsites.stack[tmpregno],stacke,varstackelem);
 12431255                 
 12441256                 stacke=tmpcalloc(sizeof (struct varstack));
 12451257                 stacke->tmpregno=tmpregno;
 12461258                 SLIST_INSERT_FIRST(&poplist,stacke,varstackelem);               
 12471259         }
 12481260 
 12491261 
 12501262         ip=bb->first;
 12511263 
 12521264         while (1) {             
 12531265                 if ( ip->type == IP_NODE) {
 12541266                         renamevarhelper(p2e,ip->ip_node,&poplist);
 12551267                 }
 12561268 
 12571269                 if (ip==bb->last)
 12581270                         break;
 12591271 
 12601272                 ip = DLIST_NEXT(ip, qelem);
 12611273         }
 12621274 
 12631275         SLIST_FOREACH(cfgn,&bb->children,cfgelem) {
 12641276                 j=0;
 12651277 
 12661278                 SLIST_FOREACH(cfgn2, &cfgn->bblock->parents, cfgelem) {
 12671279                         if (cfgn2->bblock->dfnum==bb->dfnum)
 12681280                                 break;
 12691281                         
 12701282                         j++;
 12711283                 }
 12721284 
 12731285                 SLIST_FOREACH(phi,&cfgn->bblock->phi,phielem) {
 12741286                         phi->intmpregno[j]=SLIST_FIRST(&defsites.stack[phi->tmpregno-defsites.low])->tmpregno;
 12751287                 }
 12761288                 
 12771289         }
 12781290 
 12791291         for (h = 1; h < p2e->bbinfo.size; h++) {
 12801292                 if (!TESTBIT(bb->dfchildren, h))
 12811293                         continue;
 12821294 
 12831295                 renamevar(p2e,p2e->bbinfo.arr[h]);
 12841296         }
 12851297 
 12861298         SLIST_FOREACH(stacke,&poplist,varstackelem) {
 12871299                 tmpregno=stacke->tmpregno;
 12881300                 
 12891301                 defsites.stack[tmpregno].q_forw=defsites.stack[tmpregno].q_forw->varstackelem.q_forw;
 12901302         }
 12911303 }
 12921304 
 12931305 enum pred_type {
 12941306     pred_unknown    = 0,
 12951307     pred_goto       = 1,
 12961308     pred_cond       = 2,
 12971309     pred_falltrough = 3,
 12981310 } ;
 12991311 
 13001312 void
 13011313 removephi(struct p2env *p2e)
 13021314 {
 13031315         struct basicblock *bb,*bbparent;
 13041316         struct cfgnode *cfgn;
 13051317         struct phiinfo *phi;
 13061318         int i;
 13071319         struct interpass *ip;
 13081320         struct interpass *pip;
 13091321         TWORD n_type;
 13101322 
 13111323         enum pred_type complex = pred_unknown ;
 13121324 
 13131325         int label=0;
 13141326         int newlabel;
 13151327 
 13161328         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {              
 13171329                 SLIST_FOREACH(phi,&bb->phi,phielem) {
 13181330                         /* Look at only one, notice break at end */
 13191331                         i=0;
 13201332                         
 13211333                         SLIST_FOREACH(cfgn, &bb->parents, cfgelem) {
 13221334                                 bbparent=cfgn->bblock;
 13231335                                 
 13241336                                 pip=bbparent->last;
 13251337                                 
 13261338                                 complex = pred_unknown ;
 13271339                                 
 13281340                                 BDEBUG(("removephi: %p in %d",pip,bb->dfnum));
 13291341 
 13301342                                 if (pip->type == IP_NODE && pip->ip_node->n_op == GOTO) {
 13311343                                         BDEBUG((" GOTO "));
 13321344                                         label = (int)pip->ip_node->n_left->n_lval;
 13331345                                         complex = pred_goto ;
 13341346                                 } else if (pip->type == IP_NODE && pip->ip_node->n_op == CBRANCH) {
 13351347                                         BDEBUG((" CBRANCH "));
 13361348                                         label = (int)pip->ip_node->n_right->n_lval;
 13371349                                         
 13381350                                         if (bb==p2e->labinfo.arr[label - p2e->ipp->ip_lblnum])
 13391351                                                 complex = pred_cond ;
 13401352                                         else
 13411353                                                 complex = pred_falltrough ;
 13421354 
 13431355                                 } else if (DLIST_PREV(bb, bbelem) == bbparent) {
 13441356                                         complex = pred_falltrough ;
 13451357                                 } else {
 13461358                                             /* PANIC */
 13471359                                         comperr("Assumption blown in rem-phi") ;
 13481360                                 }
 13491361       
 13501362                                 BDEBUG((" Complex: %d ",complex)) ;
 13511363 
 13521364                                 switch (complex) {
 13531365                                   case pred_goto:
 13541366                                         /* gotos can only go to this place. No bounce tab needed */
 13551367                                         SLIST_FOREACH(phi,&bb->phi,phielem) {
 13561368                                                 if (phi->intmpregno[i]>0) {
 13571369                                                         n_type=phi->n_type;
 13581370                                                         ip = ipnode(mkbinode(ASSIGN,
 13591371                                                              mktemp(phi->newtmpregno, n_type),
 13601372                                                              mktemp(phi->intmpregno[i],n_type),
 13611373                                                              n_type));
 13621374                                                         BDEBUG(("(%p, %d -> %d) ", ip, phi->intmpregno[i], phi->newtmpregno));
 13631375                                 
 13641376                                                         DLIST_INSERT_BEFORE((bbparent->last), ip, qelem);
 13651377                                                 }
 13661378                                         }
 13671379                                         break ;
 13681380                                   case pred_cond:
 13691381                                         /* Here, we need a jump pad */
 13701382                                         newlabel=getlab2();
 13711383                         
 13721384                                         ip = tmpalloc(sizeof(struct interpass));
 13731385                                         ip->type = IP_DEFLAB;
 13741386                                         /* Line number?? ip->lineno; */
 13751387                                         ip->ip_lbl = newlabel;
 13761388                                         DLIST_INSERT_BEFORE((bb->first), ip, qelem);
 13771389 
 13781390                                         SLIST_FOREACH(phi,&bb->phi,phielem) {
 13791391                                                 if (phi->intmpregno[i]>0) {
 13801392                                                         n_type=phi->n_type;
 13811393                                                         ip = ipnode(mkbinode(ASSIGN,
 13821394                                                              mktemp(phi->newtmpregno, n_type),
 13831395                                                              mktemp(phi->intmpregno[i],n_type),
 13841396                                                              n_type));
 13851397 
 13861398                                                         BDEBUG(("(%p, %d -> %d) ", ip, phi->intmpregno[i], phi->newtmpregno));
 13871399                                                         DLIST_INSERT_BEFORE((bb->first), ip, qelem);
 13881400                                                 }
 13891401                                         }
 13901402                                         /* add a jump to us */
 13911403                                         ip = ipnode(mkunode(GOTO, mklnode(ICON, label, 0, INT), 0, INT));
 13921404                                         DLIST_INSERT_BEFORE((bb->first), ip, qelem);
 13931405                                         pip->ip_node->n_right->n_lval=newlabel;
 13941406                                         if (!logop(pip->ip_node->n_left->n_op))
 13951407                                                 comperr("SSA not logop");
 13961408                                         pip->ip_node->n_left->n_label=newlabel;
 13971409                                         break ;
 13981410                                   case pred_falltrough:
 13991411                                         if (bb->first->type == IP_DEFLAB) {
 14001412                                                 label = bb->first->ip_lbl;
 14011413                                                 BDEBUG(("falltrough label %d\n", label));
 14021414                                         } else {
 14031415                                                 comperr("BBlock has no label?") ;
 14041416                                         }
 14051417 
 14061418                                         /*
 14071419                                          * add a jump to us. We _will_ be, or already have, added code in between.
 14081420                                          * The code is created in the wrong order and switched at the insert, thus
 14091421                                          * comming out correctly
 14101422                                          */
 14111423 
 14121424                                         ip = ipnode(mkunode(GOTO, mklnode(ICON, label, 0, INT), 0, INT));
 14131425                                         DLIST_INSERT_AFTER((bbparent->last), ip, qelem);
 14141426 
 14151427                                         /* Add the code to the end, add a jump to us. */
 14161428                                         SLIST_FOREACH(phi,&bb->phi,phielem) {
 14171429                                                 if (phi->intmpregno[i]>0) {
 14181430                                                         n_type=phi->n_type;
 14191431                                                         ip = ipnode(mkbinode(ASSIGN,
 14201432                                                                 mktemp(phi->newtmpregno, n_type),
 14211433                                                                 mktemp(phi->intmpregno[i],n_type),
 14221434                                                                 n_type));
 14231435 
 14241436                                                         BDEBUG(("(%p, %d -> %d) ", ip, phi->intmpregno[i], phi->newtmpregno));
 14251437                                                         DLIST_INSERT_AFTER((bbparent->last), ip, qelem);
 14261438                                                 }
 14271439                                         }
 14281440                                         break ;
 14291441                                 default:
 14301442                                         comperr("assumption blown, complex is %d\n", complex) ;
 14311443                                 }
 14321444                                 BDEBUG(("\n"));
 14331445                                 i++;
 14341446                         }
 14351447                         break;
 14361448                 }
 14371449         }
 14381450 }
 14391451 
 14401452    
 14411453 /*
 14421454  * Remove unreachable nodes in the CFG.
 14431455  */
 14441456 
 14451457 void
 14461458 remunreach(struct p2env *p2e)
 14471459 {
 14481460         struct basicblock *bb, *nbb;
 14491461         struct interpass *next, *ctree;
 14501462 
 14511463         bb = DLIST_NEXT(&p2e->bblocks, bbelem);
 14521464         while (bb != &p2e->bblocks) {
 14531465                 nbb = DLIST_NEXT(bb, bbelem);
 14541466 
 14551467                 /* Code with dfnum 0 is unreachable */
 14561468                 if (bb->dfnum != 0) {
 14571469                         bb = nbb;
 14581470                         continue;
 14591471                 }
 14601472 
 14611473                 /* Need the epilogue node for other parts of the
 14621474                    compiler, set its label to 0 and backend will
 14631475                    handle it. */
 14641476                 if (bb->first->type == IP_EPILOG) {
 14651477                         bb->first->ip_lbl = 0;
 14661478                         bb = nbb;
 14671479                         continue;
 14681480                 }
 14691481 
 14701482                 next = bb->first;
 14711483                 do {
 14721484                         ctree = next;
 14731485                         next = DLIST_NEXT(ctree, qelem);
 14741486                         
 14751487                         if (ctree->type == IP_NODE)
 14761488                                 tfree(ctree->ip_node);
 14771489                         DLIST_REMOVE(ctree, qelem);
 14781490                 } while (ctree != bb->last);
 14791491                         
 14801492                 DLIST_REMOVE(bb, bbelem);
 14811493                 bb = nbb;
 14821494         }
 14831495 }
 14841496 
 14851497 static void
 14861498 printip2(struct interpass *ip)
 14871499 {
 14881500         static char *foo[] = {
 14891501            0, "NODE", "PROLOG", "STKOFF", "EPILOG", "DEFLAB", "DEFNAM", "ASM" };
 14901502         struct interpass_prolog *ipplg, *epplg;
 14911503         unsigned i;
 14921504 
 14931505         if (ip->type > MAXIP)
 14941506                 printf("IP(%d) (%p): ", ip->type, ip);
 14951507         else
 14961508                 printf("%s (%p): ", foo[ip->type], ip);
 14971509         switch (ip->type) {
 14981510         case IP_NODE: printf("\n");
 14991511 #ifdef PCC_DEBUG
 15001512         fwalk(ip->ip_node, e2print, 0); break;
 15011513 #endif
 15021514         case IP_PROLOG:
 15031515                 ipplg = (struct interpass_prolog *)ip;
 15041516                 printf("%s %s regs",
 15051517                     ipplg->ipp_name, ipplg->ipp_vis ? "(local)" : "");
 15061518                 for (i = 0; i < NIPPREGS; i++)
 15071519                         printf("%s0x%lx", i? ":" : " ",
 15081520                             (long) ipplg->ipp_regs[i]);
 15091521                 printf(" autos %d mintemp %d minlbl %d\n",
 15101522                     ipplg->ipp_autos, ipplg->ip_tmpnum, ipplg->ip_lblnum);
 15111523                 break;
 15121524         case IP_EPILOG:
 15131525                 epplg = (struct interpass_prolog *)ip;
 15141526                 printf("%s %s regs",
 15151527                     epplg->ipp_name, epplg->ipp_vis ? "(local)" : "");
 15161528                 for (i = 0; i < NIPPREGS; i++)
 15171529                         printf("%s0x%lx", i? ":" : " ",
 15181530                             (long) epplg->ipp_regs[i]);
 15191531                 printf(" autos %d mintemp %d minlbl %d\n",
 15201532                     epplg->ipp_autos, epplg->ip_tmpnum, epplg->ip_lblnum);
 15211533                 break;
 15221534         case IP_DEFLAB: printf(LABFMT "\n", ip->ip_lbl); break;
 15231535         case IP_DEFNAM: printf("\n"); break;
 15241536         case IP_ASM: printf("%s\n", ip->ip_asm); break;
 15251537         default:
 15261538                 break;
 15271539         }
 15281540 }
 15291541 
 15301542 void
 15311543 printip(struct interpass *pole)
 15321544 {
 15331545         struct interpass *ip;
 15341546 
 15351547         DLIST_FOREACH(ip, pole, qelem)
 15361548                 printip2(ip);
 15371549 }
 15381550 
 15391551 #ifdef PCC_DEBUG
 15401552 void flownodeprint(NODE *p,FILE *flowdiagramfile);
 15411553 
 15421554 void
 15431555 flownodeprint(NODE *p,FILE *flowdiagramfile)
 15441556 {       
 15451557         int opty;
 15461558         char *o;
 15471559 
 15481560         fprintf(flowdiagramfile,"{");
 15491561 
 15501562         o=opst[p->n_op];
 15511563         
 15521564         while (*o != 0) {
 15531565                 if (*o=='<' || *o=='>')
 15541566                         fputc('\\',flowdiagramfile);
 15551567                 
 15561568                 fputc(*o,flowdiagramfile);
 15571569                 o++;
 15581570         }
 15591571         
 15601572         
 15611573         switch( p->n_op ) {                     
 15621574                 case REG:
 15631575                         fprintf(flowdiagramfile, " %s", rnames[p->n_rval] );
 15641576                         break;
 15651577                         
 15661578                 case TEMP:
 15671579                         fprintf(flowdiagramfile, " %d", regno(p));
 15681580                         break;
 15691581                         
 15701582                 case XASM:
 15711583                 case XARG:
 15721584                         fprintf(flowdiagramfile, " '%s'", p->n_name);
 15731585                         break;
 15741586                         
 15751587                 case ICON:
 15761588                 case NAME:
 15771589                 case OREG:
 15781590                         fprintf(flowdiagramfile, " " );
 15791591                         adrput(flowdiagramfile, p );
 15801592                         break;
 15811593                         
 15821594                 case STCALL:
 15831595                 case USTCALL:
 15841596                 case STARG:
 15851597                 case STASG:
 15861598                         fprintf(flowdiagramfile, " size=%d", p->n_stsize );
 15871599                         fprintf(flowdiagramfile, " align=%d", p->n_stalign );
 15881600                         break;
 15891601         }
 15901602         
 15911603         opty = optype(p->n_op);
 15921604         
 15931605         if (opty != LTYPE) {
 15941606                 fprintf(flowdiagramfile,"| {");
 15951607         
 15961608                 flownodeprint(p->n_left,flowdiagramfile);
 15971609         
 15981610                 if (opty == BITYPE) {
 15991611                         fprintf(flowdiagramfile,"|");
 16001612                         flownodeprint(p->n_right,flowdiagramfile);
 16011613                 }
 16021614                 fprintf(flowdiagramfile,"}");
 16031615         }
 16041616         
 16051617         fprintf(flowdiagramfile,"}");
 16061618 }
 16071619 
 16081620 void
 16091621 printflowdiagram(struct p2env *p2e, char *type) {
 16101622         struct basicblock *bbb;
 16111623         struct cfgnode *ccnode;
 16121624         struct interpass *ip;
 16131625         struct interpass_prolog *plg;
 16141626         struct phiinfo *phi;
 16151627         char *name;
 16161628         char *filename;
 16171629         int filenamesize;
 16181630         char *ext=".dot";
 16191631         FILE *flowdiagramfile;
 16201632         
 16211633         if (!g2debug)
 16221634                 return;
 16231635         
 16241636         bbb=DLIST_NEXT(&p2e->bblocks, bbelem);
 16251637         ip=bbb->first;
 16261638 
 16271639         if (ip->type != IP_PROLOG)
 16281640                 return;
 16291641         plg = (struct interpass_prolog *)ip;
 16301642 
 16311643         name=plg->ipp_name;
 16321644         
 16331645         filenamesize=strlen(name)+1+strlen(type)+strlen(ext)+1;
 16341646         filename=tmpalloc(filenamesize);
 16351647         snprintf(filename,filenamesize,"%s-%s%s",name,type,ext);
 16361648         
 16371649         flowdiagramfile=fopen(filename,"w");
 16381650         
 16391651         fprintf(flowdiagramfile,"digraph {\n");
 16401652         fprintf(flowdiagramfile,"rankdir=LR\n");
 16411653         
 16421654         DLIST_FOREACH(bbb, &p2e->bblocks, bbelem) {
 16431655                 ip=bbb->first;
 16441656                 
 16451657                 fprintf(flowdiagramfile,"bb%p [shape=record ",bbb);
 16461658                 
 16471659                 if (ip->type==IP_PROLOG)
 16481660                         fprintf(flowdiagramfile,"root ");
 16491661 
 16501662                 fprintf(flowdiagramfile,"label=\"");
 16511663                 
 16521664                 SLIST_FOREACH(phi,&bbb->phi,phielem) {
 16531665                         fprintf(flowdiagramfile,"Phi %d|",phi->tmpregno);
 16541666                 }               
 16551667                 
 16561668                 
 16571669                 while (1) {
 16581670                         switch (ip->type) {
 16591671                                 case IP_NODE:
 16601672                                         flownodeprint(ip->ip_node,flowdiagramfile);
 16611673                                         break;
 16621674                                         
 16631675                                 case IP_DEFLAB:
 16641676                                         fprintf(flowdiagramfile,"Label: %d", ip->ip_lbl);
 16651677                                         break;
 16661678                                         
 16671679                                 case IP_PROLOG:
 16681680                                         plg = (struct interpass_prolog *)ip;
 16691681         
 16701682                                         fprintf(flowdiagramfile,"%s %s",plg->ipp_name,type);
 16711683                                         break;
 16721684                         }
 16731685                         
 16741686                         fprintf(flowdiagramfile,"|");
 16751687                         fprintf(flowdiagramfile,"|");
 16761688                         
 16771689                         if (ip==bbb->last)
 16781690                                 break;
 16791691                         
 16801692                         ip = DLIST_NEXT(ip, qelem);
 16811693                 }
 16821694                 fprintf(flowdiagramfile,"\"]\n");
 16831695                 
 16841696                 SLIST_FOREACH(ccnode, &bbb->children, cfgelem) {
 16851697                         char *color="black";
 16861698                         struct interpass *pip=bbb->last;
 16871699 
 16881700                         if (pip->type == IP_NODE && pip->ip_node->n_op == CBRANCH) {
 16891701                                 int label = (int)pip->ip_node->n_right->n_lval;
 16901702                                 
 16911703                                 if (ccnode->bblock==p2e->labinfo.arr[label - p2e->ipp->ip_lblnum])
 16921704                                         color="red";
 16931705                         }
 16941706                         
 16951707                         fprintf(flowdiagramfile,"bb%p -> bb%p [color=%s]\n", bbb,ccnode->bblock,color);
 16961708                 }
 16971709         }
 16981710         
 16991711         fprintf(flowdiagramfile,"}\n");
 17001712         fclose(flowdiagramfile);
 17011713 }
 17021714 
 17031715 #endif
 17041716 
 17051717 /* walk all the programm */
 17061718 void WalkAll(struct p2env* p2e, void (*f) (NODE*, void*), void* arg, int type)
 17071719 {
 17081720         struct interpass *ipole = &p2e->ipole;
 17091721         struct interpass *ip ;
 17101722         if (0 != type) {
 17111723                 DLIST_FOREACH(ip, ipole, qelem) {
 17121724                         if (ip->type == IP_NODE && ip->ip_node->n_op == type)
 17131725                                 walkf(ip->ip_node, f, arg) ;
 17141726                 }
 17151727         } else {
 17161728                 DLIST_FOREACH(ip, ipole, qelem) {
 17171729                         if (ip->type == IP_NODE)
 17181730                                 walkf(ip->ip_node, f, arg) ;
 17191731                 }
 17201732         }
 17211733 }
 17221734 #if 0
 17231735 static int is_goto_label(struct interpass*g, struct interpass* l)
 17241736 {
 17251737         if (!g || !l)
 17261738                 return 0 ;
 17271739         if (g->type != IP_NODE) return 0 ;
 17281740         if (l->type != IP_DEFLAB) return 0 ;
 17291741         if (g->ip_node->n_op != GOTO) return 0 ;
 17301742         if (g->ip_node->n_left->n_lval != l->ip_lbl) return 0 ;
 17311743         return 1 ;
 17321744 }
 17331745 #endif
 17341746 
 17351747 /*
 17361748  * iterate over the basic blocks.
 17371749  * In case a block has only one successor and that one has only one pred, and the link is a goto:
 17381750  * place the second one immediately behind the first one (in terms of nodes, means cut&resplice).
 17391751  * This should take care of a lot of jumps.
 17401752  * one problem: Cannot move the first or last basic block (prolog/epilog). This is taken care of by
 17411753  * moving block #1 to #2, not #2 to #1
 17421754  * More complex (on the back cooker;) : first coalesc the inner loops (L1 cache), then go from inside out.
 17431755  */
 17441756 
 17451757 static unsigned long count_blocks(struct p2env* p2e)
 17461758 {
 17471759         struct basicblock* bb ;
 17481760         unsigned long count = 0 ;
 17491761         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 17501762                 ++count ;
 17511763         }
 17521764         return count ;
 17531765 }
 17541766 
 17551767 struct block_map {
 17561768         struct basicblock* block ;
 17571769         unsigned long index ;
 17581770         unsigned long thread ;
 17591771 } ;
 17601772 
 17611773 static unsigned long map_blocks(struct p2env* p2e, struct block_map* map, unsigned long count)
 17621774 {
 17631775         struct basicblock* bb ;
 17641776         unsigned long indx = 0 ;
 17651777         int ignore = 2 ;
 17661778         unsigned long thread ;
 17671779         unsigned long changes ;
 17681780 
 17691781         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 17701782                 map[indx].block = bb ;
 17711783                 map[indx].index = indx ;
 17721784 
 17731785                 /* ignore the first 2 labels, maybe up to 3 BBs */
 17741786                 if (ignore) {
 17751787                         if (bb->first->type == IP_DEFLAB)
 17761788                                 --ignore;
 17771789 
 17781790                         map[indx].thread = 1 ;  /* these are "fixed" */
 17791791                 } else
 17801792                         map[indx].thread = 0 ;
 17811793 
 17821794                 indx++ ;
 17831795         }
 17841796 
 17851797         thread = 1 ;
 17861798         do {
 17871799                 changes = 0 ;
 17881800                 
 17891801                 for (indx=0; indx < count; indx++) {
 17901802                         /* find block without trace */
 17911803                         if (map[indx].thread == 0) {
 17921804                                 /* do new thread */
 17931805                                 struct cfgnode *cnode ;
 17941806                                 struct basicblock *block2 = 0;
 17951807                                 unsigned long i ;
 17961808                                 unsigned long added ;
 17971809                                 
 17981810                                 BDEBUG (("new thread %ld at block %ld\n", thread, indx)) ;
 17991811 
 18001812                                 bb = map[indx].block ;
 18011813                                 do {
 18021814                                         added = 0 ;
 18031815 
 18041816                                         for (i=0; i < count; i++) {
 18051817                                                 if (map[i].block == bb && map[i].thread == 0) {
 18061818                                                         map[i].thread = thread ;
 18071819 
 18081820                                                         BDEBUG(("adding block %ld to trace %ld\n", i, thread)) ;
 18091821 
 18101822                                                         changes ++ ;
 18111823                                                         added++ ;
 18121824 
 18131825                                                         /*
 18141826                                                          * pick one from followers. For now (simple), pick the
 18151827                                                          * one who is directly following us. If none of that exists,
 18161828                                                          * this code picks the last one.
 18171829                                                          */
 18181830 
 18191831                                                         SLIST_FOREACH(cnode, &bb->children, cfgelem) {
 18201832                                                                 block2=cnode->bblock ;
 18211833 #if 1
 18221834                                                                 if (i+1 < count && map[i+1].block == block2)
 18231835                                                                         break ; /* pick that one */
 18241836 #else
 18251837                                                                 if (block2) break ;
 18261838 #endif
 18271839                                                         }
 18281840 
 18291841                                                         if (block2)
 18301842                                                                 bb = block2 ;
 18311843                                                 }
 18321844                                         }
 18331845                                 } while (added) ;
 18341846                                 thread++ ;
 18351847                         }
 18361848                 }
 18371849         } while (changes);
 18381850 
 18391851         /* Last block is also a thread on it's own, and the highest one. */
 18401852 /*
 18411853         thread++ ;
 18421854         map[count-1].thread = thread ;
 18431855 */
 18441856         if (b2debug) {
 18451857                 printf("Threads\n");
 18461858                 for (indx=0; indx < count; indx++) {
 18471859                         printf("Block #%ld (lbl %d) Thread %ld\n", indx, map[indx].block->first->ip_lbl, map[indx].thread);
 18481860                 }
 18491861         }
 18501862         return thread ;
 18511863 }
 18521864 
 18531865 
 18541866 void TraceSchedule(struct p2env* p2e)
 18551867 {
 18561868         struct block_map* map ;
 18571869         unsigned long block_count = count_blocks(p2e);
 18581870         unsigned long i ;
 18591871         unsigned long threads;
 18601872         struct interpass *front, *back ;
 18611873 
 18621874         map = tmpalloc(block_count * sizeof(struct block_map));
 18631875 
 18641876         threads = map_blocks(p2e, map, block_count) ;
 18651877 
 18661878         back = map[0].block->last ;
 18671879         for (i=1; i < block_count; i++) {
 18681880                 /* collect the trace */
 18691881                 unsigned long j ;
 18701882                 unsigned long thread = map[i].thread ;
 18711883                 if (thread) {
 18721884                         BDEBUG(("Thread %ld\n", thread)) ;
 18731885                         for (j=i; j < block_count; j++) {
 18741886                                 if (map[j].thread == thread) {
 18751887                                         front = map[j].block->first ;
 18761888 
 18771889                                         BDEBUG(("Trace %ld, old BB %ld, next BB %ld\t",
 18781890                                                 thread, i, j)) ;
 18791891                                         BDEBUG(("Label %d\n", front->ip_lbl)) ;
 18801892                                         DLIST_NEXT(back, qelem) = front ;
 18811893                                         DLIST_PREV(front, qelem) = back ;
 18821894                                         map[j].thread = 0 ;     /* done */
 18831895                                         back = map[j].block->last ;
 18841896                                         DLIST_NEXT(back, qelem) = 0 ;
 18851897                                 }
 18861898                         }
 18871899                 }
 18881900         }
 18891901         DLIST_NEXT(back, qelem) = &(p2e->ipole) ;
 18901902         DLIST_PREV(&p2e->ipole, qelem) = back ;
 18911903 }
 18921904 
 18931905 static void add_labels(struct p2env* p2e)
 18941906 {
 18951907         struct interpass *ipole = &p2e->ipole ;
 18961908         struct interpass *ip ;
 18971909 
 18981910         DLIST_FOREACH(ip, ipole, qelem) {
 18991911                 if (ip->type == IP_NODE && ip->ip_node->n_op == CBRANCH) {
 19001912                         struct interpass *n = DLIST_NEXT(ip, qelem);
 19011913                         if (n && n->type != IP_DEFLAB) {
 19021914                                 struct interpass* lab;
 19031915                                 int newlabel=getlab2() ;
 19041916 
 19051917                                 BDEBUG(("add_label L%d\n", newlabel));
 19061918 
 19071919                                 lab = tmpalloc(sizeof(struct interpass));
 19081920                                 lab->type = IP_DEFLAB;
 19091921                                 /* Line number?? ip->lineno; */
 19101922                                 lab->ip_lbl = newlabel;
 19111923                                 DLIST_INSERT_AFTER(ip, lab, qelem);
 19121924                         }
 19131925                 }
 19141926         }
 19151927 }
 19161928 
 19171929 /* node map */
 19181930 #ifdef ENABLE_NEW
 19191931 struct node_map {
 19201932         NODE* node ;            /* the node */
 19211933         unsigned int node_num ; /* node is equal to that one */
 19221934         unsigned int var_num ;  /* node computes this variable */
 19231935 } ;
 19241936 
 19251937 static unsigned long nodes_counter ;
 19261938 static void node_map_count_walker(NODE* n, void* x)
 19271939 {
 19281940         nodes_counter ++ ;
 19291941 }
 19301942 
 19311943 static void do_cse(struct p2env* p2e)
 19321944 {
 19331945         nodes_counter = 0 ;
 19341946         WalkAll(p2e, node_map_count_walker, 0, 0) ;
 19351947         BDEBUG(("Found %ld nodes\n", nodes_counter)) ;
 19361948 }
 19371949 #endif
 19381950 
<_ 1951+#define BITALLOC(ptr,all,sz) { \
  1952+        int sz__s = BIT2BYTE(sz); ptr = all(sz__s); memset(ptr, 0, sz__s); }
  1953+#define VALIDREG(p)     (p->n_op == REG && TESTBIT(validregs, regno(p)))
  1954+#define XCHECK(x) if (x < 0 || x >= xbits) printf("x out of range %d\n", x)
  1955+#define RUP(x) (((x)+NUMBITS-1)/NUMBITS)
  1956+#define SETCOPY(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] = f[i]
  1957+#define SETSET(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] |= f[i]
  1958+#define SETCLEAR(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] &= ~f[i]
  1959+#define SETCMP(v,t,f,i,n) for (i = 0; i < RUP(n); i++) \
  1960+        if (t[i] != f[i]) v = 1
  1961+
  1962+static int xxx, xbits;
  1963+/*
  1964+ * Set/clear long term liveness for regs and temps.
  1965+ */
  1966+static void
  1967+unionize(NODE *p, struct basicblock *bb, int suboff)
  1968+{
  1969+        int o, ty;
  1970+
  1971+        if ((o = p->n_op) == TEMP || VALIDREG(p)) {
  1972+                int b = regno(p);
  1973+                if (o == TEMP)
  1974+                        b = b - suboff + MAXREGS;
  1975+XCHECK(b);
  1976+                BITSET(bb->gen, b);
  1977+        }
  1978+        if (asgop(o)) {
  1979+                if (p->n_left->n_op == TEMP || VALIDREG(p)) {
  1980+                        int b = regno(p->n_left);
  1981+                        if (p->n_left->n_op == TEMP)
  1982+                                b = b - suboff + MAXREGS;
  1983+XCHECK(b);
  1984+                        BITCLEAR(bb->gen, b);
  1985+                        BITSET(bb->killed, b);
  1986+                        unionize(p->n_right, bb, suboff);
  1987+                        return;
  1988+                }
  1989+        }
  1990+        ty = optype(o);
  1991+        if (ty != LTYPE)
  1992+                unionize(p->n_left, bb, suboff);
  1993+        if (ty == BITYPE)
  1994+                unionize(p->n_right, bb, suboff);
  1995+}
  1996+
  1997+/*
  1998+ * Found an extended assembler node, so growel out gen/killed nodes.
  1999+ */
  2000+static void
  2001+xasmionize(NODE *p, void *arg)
  2002+{
  2003+        struct basicblock *bb = arg;
  2004+        int cw, b;
  2005+
  2006+        if (p->n_op == ICON && p->n_type == STRTY)
  2007+                return; /* dummy end marker */
  2008+
  2009+        cw = xasmcode(p->n_name);
  2010+        if (XASMVAL(cw) == 'n' || XASMVAL(cw) == 'm')
  2011+                return; /* no flow analysis */
  2012+        p = p->n_left;
  2013+ 
  2014+        if (XASMVAL(cw) == 'g' && p->n_op != TEMP && p->n_op != REG)
  2015+                return; /* no flow analysis */
  2016+
  2017+        b = regno(p);
  2018+#if 0
  2019+        if (XASMVAL(cw) == 'r' && p->n_op == TEMP)
  2020+                addnotspill(b);
  2021+#endif
  2022+#define MKTOFF(r)       ((r) - xxx)
  2023+        if (XASMISOUT(cw)) {
  2024+                if (p->n_op == TEMP) {
  2025+                        BITCLEAR(bb->gen, MKTOFF(b));
  2026+                        BITSET(bb->killed, MKTOFF(b));
  2027+                } else if (p->n_op == REG) {
  2028+                        BITCLEAR(bb->gen, b);
  2029+                        BITSET(bb->killed, b);  
  2030+                } else
  2031+                        uerror("bad xasm node type %d", p->n_op);
  2032+        }
  2033+        if (XASMISINP(cw)) {
  2034+                if (p->n_op == TEMP) {
  2035+                        BITSET(bb->gen, MKTOFF(b));
  2036+                } else if (p->n_op == REG) {
  2037+                        BITSET(bb->gen, b);
  2038+                } else if (optype(p->n_op) != LTYPE) {
  2039+                        if (XASMVAL(cw) == 'r')
  2040+                                uerror("couldn't find available register");
  2041+                        else
  2042+                                uerror("bad xasm node type2");
  2043+                }
  2044+        }
  2045+}
  2046+
  2047+/*
  2048+ * Do variable liveness analysis.  Only analyze the long-lived
  2049+ * variables, and save the live-on-exit temporaries in a bit-field
  2050+ * at the end of each basic block. This bit-field is later used
  2051+ * when doing short-range liveness analysis in Build().
  2052+ */
  2053+void
  2054+liveanal(struct p2env *p2e)
  2055+{
  2056+        struct basicblock *bb;
  2057+        struct interpass *ip;
  2058+        struct cfgnode *cn;
  2059+        bittype *saved;
  2060+        int i, mintemp, again;
  2061+
  2062+        xbits = p2e->epp->ip_tmpnum - p2e->ipp->ip_tmpnum + MAXREGS;
  2063+        mintemp = p2e->ipp->ip_tmpnum;
  2064+
  2065+        /* Just fetch space for the temporaries from heap */
  2066+        DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
  2067+                BITALLOC(bb->gen,tmpalloc,xbits);
  2068+                BITALLOC(bb->killed,tmpalloc,xbits);
  2069+                BITALLOC(bb->in,tmpalloc,xbits);
  2070+                BITALLOC(bb->out,tmpalloc,xbits);
  2071+        }
  2072+        BITALLOC(saved,tmpalloc,xbits);
  2073+
  2074+        xxx = mintemp;
  2075+        /*
  2076+         * generate the gen-killed sets for all basic blocks.
  2077+         */
  2078+        DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
  2079+                for (ip = bb->last; ; ip = DLIST_PREV(ip, qelem)) {
  2080+                        /* gen/killed is 'p', this node is 'n' */
  2081+                        if (ip->type == IP_NODE) {
  2082+                                if (ip->ip_node->n_op == XASM)
  2083+                                        flist(ip->ip_node->n_left,
  2084+                                            xasmionize, bb);
  2085+                                else
  2086+                                        unionize(ip->ip_node, bb, mintemp);
  2087+                        }
  2088+                        if (ip == bb->first)
  2089+                                break;
  2090+                }
  2091+                memcpy(bb->in, bb->gen, BIT2BYTE(xbits));
  2092+#ifdef PCC_DEBUG
  2093+#define PRTRG(x) printf("%d ", i < MAXREGS ? i : i + p2e->ipp->ip_tmpnum-MAXREGS)
  2094+                if (b2debug > 1) {
  2095+                        printf("basic block %d\ngen: ", bb->bbnum);
  2096+                        for (i = 0; i < xbits; i++)
  2097+                                if (TESTBIT(bb->gen, i))
  2098+                                        PRTRG(i);
  2099+                        printf("\nkilled: ");
  2100+                        for (i = 0; i < xbits; i++)
  2101+                                if (TESTBIT(bb->killed, i))
  2102+                                        PRTRG(i);
  2103+                        printf("\n");
  2104+                }
  2105+#endif
  2106+        }
  2107+        /* do liveness analysis on basic block level */
  2108+        do {
  2109+                int j;
  2110+
  2111+                again = 0;
  2112+                /* XXX - loop should be in reversed execution-order */
  2113+                DLIST_FOREACH_REVERSE(bb, &p2e->bblocks, bbelem) {
  2114+                        SETCOPY(saved, bb->out, j, xbits);
  2115+                        SLIST_FOREACH(cn, &bb->children, cfgelem) {
  2116+                                SETSET(bb->out, cn->bblock->in, j, xbits);
  2117+                        }
  2118+                        SETCMP(again, saved, bb->out, j, xbits);
  2119+                        SETCOPY(saved, bb->in, j, xbits);
  2120+                        SETCOPY(bb->in, bb->out, j, xbits);
  2121+                        SETCLEAR(bb->in, bb->killed, j, xbits);
  2122+                        SETSET(bb->in, bb->gen, j, xbits);
  2123+                        SETCMP(again, saved, bb->in, j, xbits);
  2124+                }
  2125+        } while (again);
  2126+
  2127+#ifdef PCC_DEBUG
  2128+        DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
  2129+                if (b2debug) {
  2130+                        printf("all basic block %d\nin: ", bb->bbnum);
  2131+                        for (i = 0; i < xbits; i++)
  2132+                                if (TESTBIT(bb->in, i))
  2133+                                        PRTRG(i);
  2134+                        printf("\nout: ");
  2135+                        for (i = 0; i < xbits; i++)
  2136+                                if (TESTBIT(bb->out, i))
  2137+                                        PRTRG(i);
  2138+                        printf("\n");
  2139+                }
  2140+        }
  2141+#endif
  2142+}
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-09-16 13:25 +0200