Quick Search:

Mode

Context

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

Other Diffs

Ignore

Blank Lines Whitespace: Expand:

Diff

1.74
 
1.75
 
MAIN:ragge:20100512170500
 
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 *);
 7575 
 7676 /* create "proper" basic blocks, add labels where needed (so bblocks have labels) */
 7777 /* run before bb generate */
 7878 static void add_labels(struct p2env*) ;
 7979 
 8080 /* Perform trace scheduling, try to get rid of gotos as much as possible */
 8181 void TraceSchedule(struct p2env*) ;
 8282 
 8383 #ifdef ENABLE_NEW
 8484 static void do_cse(struct p2env* p2e) ;
 8585 #endif
 8686 
 8787 /* Walk the complete set, performing a function on each node.
 8888  * if type is given, apply function on only that type */
 8989 void WalkAll(struct p2env* p2e, void (*f) (NODE*, void*), void* arg, int type) ;
 9090 
 9191 void BBLiveDead(struct basicblock* bblock, int what, unsigned int variable) ;
 9292 
 9393 /* Fill the live/dead code */
 9494 void LiveDead(struct p2env* p2e, int what, unsigned int variable) ;
 9595 
 9696 #ifdef PCC_DEBUG
 9797 void printflowdiagram(struct p2env *, char *);
 9898 #endif
 9999 
 100100 void
 101101 optimize(struct p2env *p2e)
 102102 {
 103103         struct interpass *ipole = &p2e->ipole;
 104104 
 105105         if (b2debug) {
 106106                 printf("initial links\n");
 107107                 printip(ipole);
 108108         }
 109109 
 110110         if (xdeljumps)
 111111                 deljumps(p2e); /* Delete redundant jumps and dead code */
 112112 
 113113         if (xssaflag)
 114114                 add_labels(p2e) ;
 115115 #ifdef ENABLE_NEW
 116116         do_cse(p2e);
 117117 #endif
 118118 
 119119 #ifdef PCC_DEBUG
 120120         if (b2debug) {
 121121                 printf("links after deljumps\n");
 122122                 printip(ipole);
 123123         }
 124124 #endif
 125125         if (xssaflag || xtemps) {
<>126 -                DLIST_INIT(&p2e->bblocks, bbelem);
127126                 bblocks_build(p2e);
 128127                 BDEBUG(("Calling cfg_build\n"));
 129128                 cfg_build(p2e);
 130129         
 131130 #ifdef PCC_DEBUG
 132131                 printflowdiagram(p2e, "first");
 133132 #endif
 134133         }
 135134         if (xssaflag) {
 136135                 BDEBUG(("Calling dominators\n"));
 137136                 dominators(p2e);
 138137                 BDEBUG(("Calling computeDF\n"));
 139138                 computeDF(p2e, DLIST_NEXT(&p2e->bblocks, bbelem));
 140139 
 141140                 if (b2debug) {
 142141                         printDF(p2e);
 143142                 }
 144143 
 145144                 BDEBUG(("Calling placePhiFunctions\n"));
 146145 
 147146                 placePhiFunctions(p2e);
 148147 
 149148                 BDEBUG(("Calling renamevar\n"));
 150149 
 151150                 renamevar(p2e,DLIST_NEXT(&p2e->bblocks, bbelem));
 152151 
 153152                 BDEBUG(("Calling removephi\n"));
 154153 
 155154 #ifdef PCC_DEBUG
 156155                 printflowdiagram(p2e, "ssa");
 157156 #endif
 158157 
 159158                 removephi(p2e);
 160159 
 161160                 BDEBUG(("Calling remunreach\n"));
 162161 /*              remunreach(p2e); */
 163162                 
 164163                 /*
 165164                  * Recalculate basic blocks and cfg that was destroyed
 166165                  * by removephi
 167166                  */
 168167                 /* first, clean up all what deljumps should have done, and more */
 169168 
 170169                 /* TODO: add the basic blocks done by the ssa code by hand.
 171170                  * The trace scheduler should not change the order in
 172171                  * which blocks are executed or what data is calculated.
 173172                  * Thus, the BBlock order should remain correct.
 174173                  */
 175174 
 176175 #ifdef ENABLE_NEW
<>177 -                DLIST_INIT(&p2e->bblocks, bbelem);
178176                 bblocks_build(p2e, &labinfo, &bbinfo);
 179177                 BDEBUG(("Calling cfg_build\n"));
 180178                 cfg_build(p2e, &labinfo);
 181179 
 182180                 TraceSchedule(p2e);
 183181 #ifdef PCC_DEBUG
 184182                 printflowdiagram(p2e, &labinfo, &bbinfo,"sched_trace");
 185183 
 186184                 if (b2debug) {
 187185                         printf("after tracesched\n");
 188186                         printip(ipole);
 189187                         fflush(stdout) ;
 190188                 }
 191189 #endif
 192190 #endif
 193191 
 194192                 /* Now, clean up the gotos we do not need any longer */
 195193                 if (xdeljumps)
 196194                         deljumps(p2e); /* Delete redundant jumps and dead code */
 197195 
<>198 -                DLIST_INIT(&p2e->bblocks, bbelem);
199196                 bblocks_build(p2e);
 200197                 BDEBUG(("Calling cfg_build\n"));
 201198                 cfg_build(p2e);
 202199 
 203200 #ifdef PCC_DEBUG
 204201                 printflowdiagram(p2e, "no_phi");
 205202 
 206203                 if (b2debug) {
 207204                         printf("new tree\n");
 208205                         printip(ipole);
 209206                 }
 210207 #endif
 211208         }
 212209 
 213210 #ifdef PCC_DEBUG
 214211         {
 215212                 int i;
 216213                 for (i = NIPPREGS; i--; )
 217214                         if (p2e->epp->ipp_regs[i] != 0)
 218215                                 comperr("register error");
 219216         }
 220217 #endif
 221218 
 222219         myoptim(ipole);
 223220 }
 224221 
 225222 /*
 226223  * Delete unused labels, excess of labels, gotos to gotos.
 227224  * This routine can be made much more efficient.
 228225  *
 229226  * Layout of the statement list here (_must_ look this way!):
 230227  *      PROLOG
 231228  *      LABEL   - states beginning of function argument moves
 232229  *      ...code to save/move arguments
 233230  *      LABEL   - states beginning of execution code
 234231  *      ...code + labels in function in function
 235232  *      EPILOG
 236233  *
 237234  * This version of deljumps is based on the c2 implementation
 238235  * that were included in 2BSD.
 239236  */
 240237 #define LABEL 1
 241238 #define JBR     2
 242239 #define CBR     3
 243240 #define STMT    4
 244241 #define EROU    5
 245242 struct dlnod {
 246243         int op;
 247244         struct interpass *dlip;
 248245         struct dlnod *forw;
 249246         struct dlnod *back;
 250247         struct dlnod *ref;
 251248         int labno;
 252249         int refc;
 253250 };
 254251 
 255252 #ifdef DLJDEBUG
 256253 static void
 257254 dumplink(struct dlnod *dl)
 258255 {
 259256         printf("dumplink %p\n", dl);
 260257         for (; dl; dl = dl->forw) {
 261258                 if (dl->op == STMT) {
 262259                         printf("STMT(%p)\n", dl);
 263260                         fwalk(dl->dlip->ip_node, e2print, 0);
 264261                 } else if (dl->op == EROU) {
 265262                         printf("EROU(%p)\n", dl);
 266263                 } else {
 267264                         static char *str[] = { 0, "LABEL", "JBR", "CBR" };
 268265                         printf("%s(%p) %d refc %d ref %p\n", str[dl->op],
 269266                             dl, dl->labno, dl->refc, dl->ref);
 270267                 }
 271268         }
 272269         printf("end dumplink\n");
 273270 }
 274271 #endif
 275272 
 276273 /*
 277274  * Create the linked list that we can work on.
 278275  */
 279276 static void
 280277 listsetup(struct interpass *ipole, struct dlnod *dl)
 281278 {
 282279         struct interpass *ip = DLIST_NEXT(ipole, qelem);
 283280         struct dlnod *p, *lastp;
 284281         NODE *q;
 285282 
 286283         lastp = dl;
 287284         while (ip->type != IP_DEFLAB)
 288285                 ip = DLIST_NEXT(ip,qelem);
 289286         ip = DLIST_NEXT(ip,qelem);
 290287         while (ip->type != IP_DEFLAB)
 291288                 ip = DLIST_NEXT(ip,qelem);
 292289         /* Now ip is at the beginning */
 293290         for (;;) {
 294291                 ip = DLIST_NEXT(ip,qelem);
 295292                 if (ip == ipole)
 296293                         break;
 297294                 p = tmpalloc(sizeof(struct dlnod));
 298295                 p->labno = 0;
 299296                 p->dlip = ip;
 300297                 switch (ip->type) {
 301298                 case IP_DEFLAB:
 302299                         p->op = LABEL;
 303300                         p->labno = ip->ip_lbl;
 304301                         break;
 305302 
 306303                 case IP_NODE:
 307304                         q = ip->ip_node;
 308305                         switch (q->n_op) {
 309306                         case GOTO:
 310307                                 p->op = JBR;
 311308                                 p->labno = q->n_left->n_lval;
 312309                                 break;
 313310                         case CBRANCH:
 314311                                 p->op = CBR;
 315312                                 p->labno = q->n_right->n_lval;
 316313                                 break;
 317314                         default:
 318315                                 p->op = STMT;
 319316                                 break;
 320317                         }
 321318                         break;
 322319 
 323320                 case IP_ASM:
 324321                         p->op = STMT;
 325322                         break;
 326323 
 327324                 case IP_EPILOG:
 328325                         p->op = EROU;
 329326                         break;
 330327 
 331328                 default:
 332329                         comperr("listsetup: bad ip node %d", ip->type);
 333330                 }
 334331                 p->forw = 0;
 335332                 p->back = lastp;
 336333                 lastp->forw = p;
 337334                 lastp = p;
 338335                 p->ref = 0;
 339336         }
 340337 }
 341338 
 342339 static struct dlnod *
 343340 nonlab(struct dlnod *p)
 344341 {
 345342         while (p && p->op==LABEL)
 346343                 p = p->forw;
 347344         return(p);
 348345 }
 349346 
 350347 static void
 351348 iprem(struct dlnod *p)
 352349 {
 353350         if (p->dlip->type == IP_NODE)
 354351                 tfree(p->dlip->ip_node);
 355352         DLIST_REMOVE(p->dlip, qelem);
 356353 }
 357354 
 358355 static void
 359356 decref(struct dlnod *p)
 360357 {
 361358         if (--p->refc <= 0) {
 362359                 iprem(p);
 363360                 p->back->forw = p->forw;
 364361                 p->forw->back = p->back;
 365362         }
 366363 }
 367364 
 368365 static void
 369366 setlab(struct dlnod *p, int labno)
 370367 {
 371368         p->labno = labno;
 372369         if (p->op == JBR)
 373370                 p->dlip->ip_node->n_left->n_lval = labno;
 374371         else if (p->op == CBR)
 375372                 p->dlip->ip_node->n_right->n_lval = labno;
 376373         else
 377374                 comperr("setlab bad op %d", p->op);
 378375 }
 379376 
 380377 /*
 381378  * Label reference counting and removal of unused labels.
 382379  */
 383380 #define LABHS 127
 384381 static void
 385382 refcount(struct p2env *p2e, struct dlnod *dl)
 386383 {
 387384         struct dlnod *p, *lp;
 388385         struct dlnod *labhash[LABHS];
 389386         struct dlnod **hp, *tp;
 390387 
 391388         /* Clear label hash */
 392389         for (hp = labhash; hp < &labhash[LABHS];)
 393390                 *hp++ = 0;
 394391         /* Enter labels into hash.  Later overwrites earlier */
 395392         for (p = dl->forw; p!=0; p = p->forw)
 396393                 if (p->op==LABEL) {
 397394                         labhash[p->labno % LABHS] = p;
 398395                         p->refc = 0;
 399396                 }
 400397 
 401398         /* search for jumps to labels and fill in reference */
 402399         for (p = dl->forw; p!=0; p = p->forw) {
 403400                 if (p->op==JBR || p->op==CBR) {
 404401                         p->ref = 0;
 405402                         lp = labhash[p->labno % LABHS];
 406403                         if (lp==0 || p->labno!=lp->labno)
 407404                             for (lp = dl->forw; lp!=0; lp = lp->forw) {
 408405                                 if (lp->op==LABEL && p->labno==lp->labno)
 409406                                         break;
 410407                             }
 411408                         if (lp) {
 412409                                 tp = nonlab(lp)->back;
 413410                                 if (tp!=lp) {
 414411                                         setlab(p, tp->labno);
 415412                                         lp = tp;
 416413                                 }
 417414                                 p->ref = lp;
 418415                                 lp->refc++;
 419416                         }
 420417                 }
 421418         }
 422419         for (p = dl->forw; p!=0; p = p->forw)
 423420                 if (p->op==LABEL && p->refc==0
 424421                  && (lp = nonlab(p))->op)
 425422                         decref(p);
 426423 }
 427424 
 428425 static int nchange;
 429426 
 430427 static struct dlnod *
 431428 codemove(struct dlnod *p)
 432429 {
 433430         struct dlnod *p1, *p2, *p3;
 434431 #ifdef notyet
 435432         struct dlnod *t, *tl;
 436433         int n;
 437434 #endif
 438435 
 439436         p1 = p;
 440437         if (p1->op!=JBR || (p2 = p1->ref)==0)
 441438                 return(p1);
 442439         while (p2->op == LABEL)
 443440                 if ((p2 = p2->back) == 0)
 444441                         return(p1);
 445442         if (p2->op!=JBR)
 446443                 goto ivloop;
 447444         if (p1==p2)
 448445                 return(p1);
 449446         p2 = p2->forw;
 450447         p3 = p1->ref;
 451448         while (p3) {
 452449                 if (p3->op==JBR) {
 453450                         if (p1==p3 || p1->forw==p3 || p1->back==p3)
 454451                                 return(p1);
 455452                         nchange++;
 456453                         p1->back->forw = p2;
 457454                         p1->dlip->qelem.q_back->qelem.q_forw = p2->dlip;
 458455 
 459456                         p1->forw->back = p3;
 460457                         p1->dlip->qelem.q_forw->qelem.q_back = p3->dlip;
 461458 
 462459 
 463460                         p2->back->forw = p3->forw;
 464461                         p2->dlip->qelem.q_back->qelem.q_forw = p3->forw->dlip;
 465462 
 466463                         p3->forw->back = p2->back;
 467464                         p3->dlip->qelem.q_forw->qelem.q_back = p2->back->dlip;
 468465 
 469466                         p2->back = p1->back;
 470467                         p2->dlip->qelem.q_back = p1->dlip->qelem.q_back;
 471468 
 472469                         p3->forw = p1->forw;
 473470                         p3->dlip->qelem.q_forw = p1->forw->dlip;
 474471 
 475472                         decref(p1->ref);
 476473                         if (p1->dlip->type == IP_NODE)
 477474                                 tfree(p1->dlip->ip_node);
 478475 
 479476                         return(p2);
 480477                 } else
 481478                         p3 = p3->forw;
 482479         }
 483480         return(p1);
 484481 
 485482 ivloop:
 486483         if (p1->forw->op!=LABEL)
 487484                 return(p1);
 488485         return(p1);
 489486 
 490487 #ifdef notyet
 491488         p3 = p2 = p2->forw;
 492489         n = 16;
 493490         do {
 494491                 if ((p3 = p3->forw) == 0 || p3==p1 || --n==0)
 495492                         return(p1);
 496493         } while (p3->op!=CBR || p3->labno!=p1->forw->labno);
 497494         do
 498495                 if ((p1 = p1->back) == 0)
 499496                         return(p);
 500497         while (p1!=p3);
 501498         p1 = p;
 502499         tl = insertl(p1);
 503500         p3->subop = revbr[p3->subop];
 504501         decref(p3->ref);
 505502                 p2->back->forw = p1;
 506503         p3->forw->back = p1;
 507504         p1->back->forw = p2;
 508505         p1->forw->back = p3;
 509506         t = p1->back;
 510507         p1->back = p2->back;
 511508         p2->back = t;
 512509         t = p1->forw;
 513510         p1->forw = p3->forw;
 514511         p3->forw = t;
 515512         p2 = insertl(p1->forw);
 516513         p3->labno = p2->labno;
 517514         p3->ref = p2;
 518515         decref(tl);
 519516         if (tl->refc<=0)
 520517                 nrlab--;
 521518         nchange++;
 522519         return(p3);
 523520 #endif
 524521 }
 525522 
 526523 static void
 527524 iterate(struct p2env *p2e, struct dlnod *dl)
 528525 {
 529526         struct dlnod *p, *rp, *p1;
 530527         extern int negrel[];
 531528         extern size_t negrelsize;
 532529         int i;
 533530 
 534531         nchange = 0;
 535532         for (p = dl->forw; p!=0; p = p->forw) {
 536533                 if ((p->op==JBR||p->op==CBR) && p->ref) {
 537534                         /* Resolves:
 538535                          * jbr L7
 539536                          * ...
 540537                          * L7: jbr L8
 541538                          */
 542539                         rp = nonlab(p->ref);
 543540                         if (rp->op==JBR && rp->labno && p->labno!=rp->labno) {
 544541                                 setlab(p, rp->labno);
 545542                                 decref(p->ref);
 546543                                 rp->ref->refc++;
 547544                                 p->ref = rp->ref;
 548545                                 nchange++;
 549546                         }
 550547                 }
 551548                 if (p->op==CBR && (p1 = p->forw)->op==JBR) {
 552549                         /* Resolves:
 553550                          * cbr L7
 554551                          * jbr L8
 555552                          * L7:
 556553                          */
 557554                         rp = p->ref;
 558555                         do
 559556                                 rp = rp->back;
 560557                         while (rp->op==LABEL);
 561558                         if (rp==p1) {
 562559                                 decref(p->ref);
 563560                                 p->ref = p1->ref;
 564561                                 setlab(p, p1->labno);
 565562 
 566563                                 iprem(p1);
 567564 
 568565                                 p1->forw->back = p;
 569566                                 p->forw = p1->forw;
 570567 
 571568                                 i = p->dlip->ip_node->n_left->n_op;
 572569                                 if (i < EQ || i - EQ >= (int)negrelsize)
 573570                                         comperr("deljumps: unexpected op");
 574571                                 p->dlip->ip_node->n_left->n_op = negrel[i - EQ];
 575572                                 nchange++;
 576573                         }
 577574                 }
 578575                 if (p->op == JBR) {
 579576                         /* Removes dead code */
 580577                         while (p->forw && p->forw->op!=LABEL &&
 581578                             p->forw->op!=EROU) {
 582579                                 nchange++;
 583580                                 if (p->forw->ref)
 584581                                         decref(p->forw->ref);
 585582 
 586583                                 iprem(p->forw);
 587584 
 588585                                 p->forw = p->forw->forw;
 589586                                 p->forw->back = p;
 590587                         }
 591588                         rp = p->forw;
 592589                         while (rp && rp->op==LABEL) {
 593590                                 if (p->ref == rp) {
 594591                                         p->back->forw = p->forw;
 595592                                         p->forw->back = p->back;
 596593                                         iprem(p);
 597594                                         p = p->back;
 598595                                         decref(rp);
 599596                                         nchange++;
 600597                                         break;
 601598                                 }
 602599                                 rp = rp->forw;
 603600                         }
 604601                 }
 605602                 if (p->op == JBR) {
 606603                         /* xjump(p); * needs tree rewrite; not yet */
 607604                         p = codemove(p);
 608605                 }
 609606         }
 610607 }
 611608 
 612609 void
 613610 deljumps(struct p2env *p2e)
 614611 {
 615612         struct interpass *ipole = &p2e->ipole;
 616613         struct dlnod dln;
 617614         MARK mark;
 618615 
 619616         markset(&mark);
 620617 
 621618         memset(&dln, 0, sizeof(dln));
 622619         listsetup(ipole, &dln);
 623620         do {
 624621                 refcount(p2e, &dln);
 625622                 do {
 626623                         iterate(p2e, &dln);
 627624                 } while (nchange);
 628625 #ifdef notyet
 629626                 comjump();
 630627 #endif
 631628         } while (nchange);
 632629 
 633630         markfree(&mark);
 634631 }
 635632 
 636633 void
 637634 optdump(struct interpass *ip)
 638635 {
 639636         static char *nm[] = { "node", "prolog", "newblk", "epilog", "locctr",
 640637                 "deflab", "defnam", "asm" };
 641638         printf("type %s\n", nm[ip->type-1]);
 642639         switch (ip->type) {
 643640         case IP_NODE:
 644641 #ifdef PCC_DEBUG
 645642                 fwalk(ip->ip_node, e2print, 0);
 646643 #endif
 647644                 break;
 648645         case IP_DEFLAB:
 649646                 printf("label " LABFMT "\n", ip->ip_lbl);
 650647                 break;
 651648         case IP_ASM:
 652649                 printf(": %s\n", ip->ip_asm);
 653650                 break;
 654651         }
 655652 }
 656653 
 657654 /*
 658655  * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
 659656  *
 660657  * Also fills the labelinfo struct with information about which bblocks
 661658  * that contain which label.
 662659  */
 663660 
 664661 void
 665662 bblocks_build(struct p2env *p2e)
 666663 {
 667664         struct interpass *ipole = &p2e->ipole;
 668665         struct interpass *ip;
 669666         struct basicblock *bb = NULL;
 670667         int low, high;
 671668         int count = 0;
 672669         int i;
 673670 
 674671         BDEBUG(("bblocks_build (%p, %p)\n", &p2e->labinfo, &p2e->bbinfo));
 675672         low = p2e->ipp->ip_lblnum;
 676673         high = p2e->epp->ip_lblnum;
 677674 
 678675         /*
 679676          * First statement is a leader.
 680677          * Any statement that is target of a jump is a leader.
 681678          * Any statement that immediately follows a jump is a leader.
 682679          */
<> 680+        DLIST_INIT(&p2e->bblocks, bbelem);
<_683681         DLIST_FOREACH(ip, ipole, qelem) {
 684682                 if (bb == NULL || (ip->type == IP_EPILOG) ||
 685683                     (ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) {
 686684                         bb = tmpalloc(sizeof(struct basicblock));
 687685                         bb->first = ip;
 688686                         SLIST_INIT(&bb->children);
 689687                         SLIST_INIT(&bb->parents);
 690688                         bb->dfnum = 0;
 691689                         bb->dfparent = 0;
 692690                         bb->semi = 0;
 693691                         bb->ancestor = 0;
 694692                         bb->idom = 0;
 695693                         bb->samedom = 0;
 696694                         bb->bucket = NULL;
 697695                         bb->df = NULL;
 698696                         bb->dfchildren = NULL;
 699697                         bb->Aorig = NULL;
 700698                         bb->Aphi = NULL;
 701699                         SLIST_INIT(&bb->phi);
 702700                         bb->bbnum = count;
 703701                         DLIST_INSERT_BEFORE(&p2e->bblocks, bb, bbelem);
 704702                         count++;
 705703                 }
 706704                 bb->last = ip;
 707705                 if ((ip->type == IP_NODE) && (ip->ip_node->n_op == GOTO ||
 708706                     ip->ip_node->n_op == CBRANCH))
 709707                         bb = NULL;
 710708                 if (ip->type == IP_PROLOG)
 711709                         bb = NULL;
 712710         }
 713711         p2e->nbblocks = count;
 714712 
 715713         if (b2debug) {
 716714                 printf("Basic blocks in func: %d, low %d, high %d\n",
 717715                     count, low, high);
 718716                 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 719717                         printf("bb(%d) %p: first %p last %p\n", bb->bbnum, bb,
 720718                             bb->first, bb->last);
 721719                 }
 722720         }
 723721 
 724722         p2e->labinfo.low = low;
 725723         p2e->labinfo.size = high - low + 1;
 726724         p2e->labinfo.arr = tmpalloc(p2e->labinfo.size * sizeof(struct basicblock *));
 727725         for (i = 0; i < p2e->labinfo.size; i++) {
 728726                 p2e->labinfo.arr[i] = NULL;
 729727         }
 730728         
 731729         p2e->bbinfo.size = count + 1;
 732730         p2e->bbinfo.arr = tmpalloc(p2e->bbinfo.size * sizeof(struct basicblock *));
 733731         for (i = 0; i < p2e->bbinfo.size; i++) {
 734732                 p2e->bbinfo.arr[i] = NULL;
 735733         }
 736734 
 737735         /* Build the label table */
 738736         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 739737                 if (bb->first->type == IP_DEFLAB)
 740738                         p2e->labinfo.arr[bb->first->ip_lbl - low] = bb;
 741739         }
 742740 
 743741         if (b2debug) {
 744742                 printf("Label table:\n");
 745743                 for (i = 0; i < p2e->labinfo.size; i++)
 746744                         if (p2e->labinfo.arr[i])
 747745                                 printf("Label %d bblock %p\n", i+low,
 748746                                     p2e->labinfo.arr[i]);
 749747         }
 750748 }
 751749 
 752750 /*
 753751  * Build the control flow graph.
 754752  */
 755753 
 756754 void
 757755 cfg_build(struct p2env *p2e)
 758756 {
 759757         /* Child and parent nodes */
 760758         struct cfgnode *cnode;
 761759         struct cfgnode *pnode;
 762760         struct basicblock *bb;
 763761         
 764762         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 765763 
 766764                 if (bb->first->type == IP_EPILOG) {
 767765                         break;
 768766                 }
 769767 
 770768                 cnode = tmpalloc(sizeof(struct cfgnode));
 771769                 pnode = tmpalloc(sizeof(struct cfgnode));
 772770                 pnode->bblock = bb;
 773771 
 774772                 if ((bb->last->type == IP_NODE) &&
 775773                     (bb->last->ip_node->n_op == GOTO) &&
 776774                     (bb->last->ip_node->n_left->n_op == ICON))  {
 777775                         if (bb->last->ip_node->n_left->n_lval - p2e->labinfo.low >
 778776                             p2e->labinfo.size) {
 779777                                 comperr("Label out of range: %d, base %d",
 780778                                         bb->last->ip_node->n_left->n_lval,
 781779                                         p2e->labinfo.low);
 782780                         }
 783781                         cnode->bblock = p2e->labinfo.arr[bb->last->ip_node->n_left->n_lval - p2e->labinfo.low];
 784782                         SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 785783                         SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 786784                         continue;
 787785                 }
 788786                 if ((bb->last->type == IP_NODE) &&
 789787                     (bb->last->ip_node->n_op == CBRANCH)) {
 790788                         if (bb->last->ip_node->n_right->n_lval - p2e->labinfo.low >
 791789                             p2e->labinfo.size)
 792790                                 comperr("Label out of range: %d",
 793791                                         bb->last->ip_node->n_left->n_lval);
 794792 
 795793                         cnode->bblock = p2e->labinfo.arr[bb->last->ip_node->n_right->n_lval - p2e->labinfo.low];
 796794                         SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 797795                         SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 798796                         cnode = tmpalloc(sizeof(struct cfgnode));
 799797                         pnode = tmpalloc(sizeof(struct cfgnode));
 800798                         pnode->bblock = bb;
 801799                 }
 802800 
 803801                 cnode->bblock = DLIST_NEXT(bb, bbelem);
 804802                 SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 805803                 SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 806804         }
 807805 }
 808806 
 809807 void
 810808 cfg_dfs(struct basicblock *bb, unsigned int parent, struct bblockinfo *bbinfo)
 811809 {
 812810         struct cfgnode *cnode;
 813811         
 814812         if (bb->dfnum != 0)
 815813                 return;
 816814 
 817815         bb->dfnum = ++dfsnum;
 818816         bb->dfparent = parent;
 819817         bbinfo->arr[bb->dfnum] = bb;
 820818         SLIST_FOREACH(cnode, &bb->children, cfgelem) {
 821819                 cfg_dfs(cnode->bblock, bb->dfnum, bbinfo);
 822820         }
 823821         /* Don't bring in unreachable nodes in the future */
 824822         bbinfo->size = dfsnum + 1;
 825823 }
 826824 
 827825 static bittype *
 828826 setalloc(int nelem)
 829827 {
 830828         bittype *b;
 831829         int sz = (nelem+NUMBITS-1)/NUMBITS;
 832830 
 833831         b = tmpalloc(sz * sizeof(bittype));
 834832         memset(b, 0, sz * sizeof(bittype));
 835833         return b;
 836834 }
 837835 
 838836 /*
 839837  * Algorithm 19.9, pp 414 from Appel.
 840838  */
 841839 
 842840 void
 843841 dominators(struct p2env *p2e)
 844842 {
 845843         struct cfgnode *cnode;
 846844         struct basicblock *bb, *y, *v;
 847845         struct basicblock *s, *sprime, *p;
 848846         int h, i;
 849847 
 850848         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 851849                 bb->bucket = setalloc(p2e->bbinfo.size);
 852850                 bb->df = setalloc(p2e->bbinfo.size);
 853851                 bb->dfchildren = setalloc(p2e->bbinfo.size);
 854852         }
 855853 
 856854         dfsnum = 0;
 857855         cfg_dfs(DLIST_NEXT(&p2e->bblocks, bbelem), 0, &p2e->bbinfo);
 858856 
 859857         if (b2debug) {
 860858                 struct basicblock *bbb;
 861859                 struct cfgnode *ccnode;
 862860 
 863861                 DLIST_FOREACH(bbb, &p2e->bblocks, bbelem) {
 864862                         printf("Basic block %d, parents: ", bbb->dfnum);
 865863                         SLIST_FOREACH(ccnode, &bbb->parents, cfgelem) {
 866864                                 printf("%d, ", ccnode->bblock->dfnum);
 867865                         }
 868866                         printf("\nChildren: ");
 869867                         SLIST_FOREACH(ccnode, &bbb->children, cfgelem) {
 870868                                 printf("%d, ", ccnode->bblock->dfnum);
 871869                         }
 872870                         printf("\n");
 873871                 }
 874872         }
 875873 
 876874         for(h = p2e->bbinfo.size - 1; h > 1; h--) {
 877875                 bb = p2e->bbinfo.arr[h];
 878876                 p = s = p2e->bbinfo.arr[bb->dfparent];
 879877                 SLIST_FOREACH(cnode, &bb->parents, cfgelem) {
 880878                         if (cnode->bblock->dfnum ==0)
 881879                                 continue; /* Ignore unreachable code */
 882880 
 883881                         if (cnode->bblock->dfnum <= bb->dfnum)
 884882                                 sprime = cnode->bblock;
 885883                         else
 886884                                 sprime = p2e->bbinfo.arr[ancestorwithlowestsemi
 887885                                               (cnode->bblock, &p2e->bbinfo)->semi];
 888886                         if (sprime->dfnum < s->dfnum)
 889887                                 s = sprime;
 890888                 }
 891889                 bb->semi = s->dfnum;
 892890                 BITSET(s->bucket, bb->dfnum);
 893891                 link(p, bb);
 894892                 for (i = 1; i < p2e->bbinfo.size; i++) {
 895893                         if(TESTBIT(p->bucket, i)) {
 896894                                 v = p2e->bbinfo.arr[i];
 897895                                 y = ancestorwithlowestsemi(v, &p2e->bbinfo);
 898896                                 if (y->semi == v->semi)
 899897                                         v->idom = p->dfnum;
 900898                                 else
 901899                                         v->samedom = y->dfnum;
 902900                         }
 903901                 }
 904902                 memset(p->bucket, 0, (p2e->bbinfo.size + 7)/8);
 905903         }
 906904 
 907905         if (b2debug) {
 908906                 printf("Num\tSemi\tAncest\tidom\n");
 909907                 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 910908                         printf("%d\t%d\t%d\t%d\n", bb->dfnum, bb->semi,
 911909                             bb->ancestor, bb->idom);
 912910                 }
 913911         }
 914912 
 915913         for(h = 2; h < p2e->bbinfo.size; h++) {
 916914                 bb = p2e->bbinfo.arr[h];
 917915                 if (bb->samedom != 0) {
 918916                         bb->idom = p2e->bbinfo.arr[bb->samedom]->idom;
 919917                 }
 920918         }
 921919         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 922920                 if (bb->idom != 0 && bb->idom != bb->dfnum) {
 923921                         BDEBUG(("Setting child %d of %d\n",
 924922                             bb->dfnum, p2e->bbinfo.arr[bb->idom]->dfnum));
 925923                         BITSET(p2e->bbinfo.arr[bb->idom]->dfchildren, bb->dfnum);
 926924                 }
 927925         }
 928926 }
 929927 
 930928 
 931929 struct basicblock *
 932930 ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo)
 933931 {
 934932         struct basicblock *u = bblock;
 935933         struct basicblock *v = bblock;
 936934 
 937935         while (v->ancestor != 0) {
 938936                 if (bbinfo->arr[v->semi]->dfnum <
 939937                     bbinfo->arr[u->semi]->dfnum)
 940938                         u = v;
 941939                 v = bbinfo->arr[v->ancestor];
 942940         }
 943941         return u;
 944942 }
 945943 
 946944 void
 947945 link(struct basicblock *parent, struct basicblock *child)
 948946 {
 949947         child->ancestor = parent->dfnum;
 950948 }
 951949 
 952950 void
 953951 computeDF(struct p2env *p2e, struct basicblock *bblock)
 954952 {
 955953         struct cfgnode *cnode;
 956954         int h, i;
 957955         
 958956         SLIST_FOREACH(cnode, &bblock->children, cfgelem) {
 959957                 if (cnode->bblock->idom != bblock->dfnum)
 960958                         BITSET(bblock->df, cnode->bblock->dfnum);
 961959         }
 962960         for (h = 1; h < p2e->bbinfo.size; h++) {
 963961                 if (!TESTBIT(bblock->dfchildren, h))
 964962                         continue;
 965963                 computeDF(p2e, p2e->bbinfo.arr[h]);
 966964                 for (i = 1; i < p2e->bbinfo.size; i++) {
 967965                         if (TESTBIT(p2e->bbinfo.arr[h]->df, i) &&
 968966                             (p2e->bbinfo.arr[i] == bblock ||
 969967                              (bblock->dfnum != p2e->bbinfo.arr[i]->idom)))
 970968                             BITSET(bblock->df, i);
 971969                 }
 972970         }
 973971 }
 974972 
 975973 void printDF(struct p2env *p2e)
 976974 {
 977975         struct basicblock *bb;
 978976         int i;
 979977 
 980978         printf("Dominance frontiers:\n");
 981979    
 982980         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 983981                 printf("bb %d : ", bb->dfnum);
 984982         
 985983                 for (i=1; i < p2e->bbinfo.size;i++) {
 986984                         if (TESTBIT(bb->df,i)) {
 987985                                 printf("%d ",i);
 988986                         }
 989987                 }
 990988            
 991989                 printf("\n");
 992990         }
 993991    
 994992 }
 995993 
 996994 
 997995 
 998996 static struct basicblock *currbb;
 999997 static struct interpass *currip;
 1000998 
 1001999 /* Helper function for findTemps, Find assignment nodes. */
 10021000 static void
 10031001 searchasg(NODE *p, void *arg)
 10041002 {
 10051003         struct pvarinfo *pv;
 10061004         int tempnr;
 10071005         struct varstack *stacke;
 10081006    
 10091007         if (p->n_op != ASSIGN)
 10101008                 return;
 10111009 
 10121010         if (p->n_left->n_op != TEMP)
 10131011                 return;
 10141012 
 10151013         tempnr=regno(p->n_left)-defsites.low;
 10161014    
 10171015         BITSET(currbb->Aorig, tempnr);
 10181016         
 10191017         pv = tmpcalloc(sizeof(struct pvarinfo));
 10201018         pv->next = defsites.arr[tempnr];
 10211019         pv->bb = currbb;
 10221020         pv->n_type = p->n_left->n_type;
 10231021         
 10241022         defsites.arr[tempnr] = pv;
 10251023         
 10261024         
 10271025         if (SLIST_FIRST(&defsites.stack[tempnr])==NULL) {
 10281026                 stacke=tmpcalloc(sizeof (struct varstack));
 10291027                 stacke->tmpregno=0;
 10301028                 SLIST_INSERT_FIRST(&defsites.stack[tempnr],stacke,varstackelem);
 10311029         }
 10321030 }
 10331031 
 10341032 /* Walk the interpass looking for assignment nodes. */
 10351033 void findTemps(struct interpass *ip)
 10361034 {
 10371035         if (ip->type != IP_NODE)
 10381036                 return;
 10391037 
 10401038         currip = ip;
 10411039 
 10421040         walkf(ip->ip_node, searchasg, 0);
 10431041 }
 10441042 
 10451043 /*
 10461044  * Algorithm 19.6 from Appel.
 10471045  */
 10481046 
 10491047 void
 10501048 placePhiFunctions(struct p2env *p2e)
 10511049 {
 10521050         struct basicblock *bb;
 10531051         struct basicblock *y;
 10541052         struct interpass *ip;
 10551053         int maxtmp, i, j, k;
 10561054         struct pvarinfo *n;
 10571055         struct cfgnode *cnode;
 10581056         TWORD ntype;
 10591057         struct pvarinfo *pv;
 10601058         struct phiinfo *phi;
 10611059         int phifound;
 10621060 
 10631061         bb = DLIST_NEXT(&p2e->bblocks, bbelem);
 10641062         defsites.low = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
 10651063         bb = DLIST_PREV(&p2e->bblocks, bbelem);
 10661064         maxtmp = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
 10671065         defsites.size = maxtmp - defsites.low + 1;
 10681066         defsites.arr = tmpcalloc(defsites.size*sizeof(struct pvarinfo *));
 10691067         defsites.stack = tmpcalloc(defsites.size*sizeof(SLIST_HEAD(, varstack)));
 10701068         
 10711069         for (i=0;i<defsites.size;i++)
 10721070                 SLIST_INIT(&defsites.stack[i]); 
 10731071         
 10741072         /* Find all defsites */
 10751073         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 10761074                 currbb = bb;
 10771075                 ip = bb->first;
 10781076                 bb->Aorig = setalloc(defsites.size);
 10791077                 bb->Aphi = setalloc(defsites.size);
 10801078                 
 10811079                 while (ip != bb->last) {
 10821080                         findTemps(ip);
 10831081                         ip = DLIST_NEXT(ip, qelem);
 10841082                 }
 10851083                 /* Make sure we get the last statement in the bblock */
 10861084                 findTemps(ip);
 10871085         }
 10881086    
 10891087         /* For each variable */
 10901088         for (i = 0; i < defsites.size; i++) {
 10911089                 /* While W not empty */
 10921090                 while (defsites.arr[i] != NULL) {
 10931091                         /* Remove some node n from W */
 10941092                         n = defsites.arr[i];
 10951093                         defsites.arr[i] = n->next;
 10961094                         /* For each y in n->bb->df */
 10971095                         for (j = 0; j < p2e->bbinfo.size; j++) {
 10981096                                 if (!TESTBIT(n->bb->df, j))
 10991097                                         continue;
 11001098                                 
 11011099                                 if (TESTBIT(p2e->bbinfo.arr[j]->Aphi, i))
 11021100                                         continue;
 11031101 
 11041102                                 y=p2e->bbinfo.arr[j];
 11051103                                 ntype = n->n_type;
 11061104                                 k = 0;
 11071105                                 /* Amount of predecessors for y */
 11081106                                 SLIST_FOREACH(cnode, &y->parents, cfgelem)
 11091107                                         k++;
 11101108                                 /* Construct phi(...)
 11111109                                 */
 11121110                            
 11131111                                 phifound=0;
 11141112                            
 11151113                                 SLIST_FOREACH(phi, &y->phi, phielem) {
 11161114                                     if (phi->tmpregno==i+defsites.low)
 11171115                                         phifound++;
 11181116                                 }
 11191117                            
 11201118                                 if (phifound==0) {
 11211119                                         if (b2debug)
 11221120                                             printf("Phi in %d (%p) for %d\n",y->dfnum,y,i+defsites.low);
 11231121 
 11241122                                         phi = tmpcalloc(sizeof(struct phiinfo));
 11251123                            
 11261124                                         phi->tmpregno=i+defsites.low;
 11271125                                         phi->size=k;
 11281126                                         phi->n_type=ntype;
 11291127                                         phi->intmpregno=tmpcalloc(k*sizeof(int));
 11301128                            
 11311129                                         SLIST_INSERT_LAST(&y->phi,phi,phielem);
 11321130                                 } else {
 11331131                                     if (b2debug)
 11341132                                         printf("Phi already in %d for %d\n",y->dfnum,i+defsites.low);
 11351133                                 }
 11361134 
 11371135                                 BITSET(p2e->bbinfo.arr[j]->Aphi, i);
 11381136                                 if (!TESTBIT(p2e->bbinfo.arr[j]->Aorig, i)) {
 11391137                                         pv = tmpalloc(sizeof(struct pvarinfo));
 11401138                                         pv->bb = y;
 11411139                                         pv->n_type=ntype;
 11421140                                         pv->next = defsites.arr[i];
 11431141                                         defsites.arr[i] = pv;
 11441142                                 }
 11451143                                         
 11461144 
 11471145                         }
 11481146                 }
 11491147         }
 11501148 }
 11511149 
 11521150 /* Helper function for renamevar. */
 11531151 static void
 11541152 renamevarhelper(struct p2env *p2e,NODE *t,void *poplistarg)
 11551153 {       
 11561154         SLIST_HEAD(, varstack) *poplist=poplistarg;
 11571155         int opty;
 11581156         int tempnr;
 11591157         int newtempnr;
 11601158         int x;
 11611159         struct varstack *stacke;
 11621160         
 11631161         if (t->n_op == ASSIGN && t->n_left->n_op == TEMP) {
 11641162                 renamevarhelper(p2e,t->n_right,poplist);
 11651163                                 
 11661164                 tempnr=regno(t->n_left)-defsites.low;
 11671165                 
 11681166                 newtempnr=p2e->epp->ip_tmpnum++;
 11691167                 regno(t->n_left)=newtempnr;
 11701168                 
 11711169                 stacke=tmpcalloc(sizeof (struct varstack));
 11721170                 stacke->tmpregno=newtempnr;
 11731171                 SLIST_INSERT_FIRST(&defsites.stack[tempnr],stacke,varstackelem);
 11741172                 
 11751173                 stacke=tmpcalloc(sizeof (struct varstack));
 11761174                 stacke->tmpregno=tempnr;
 11771175                 SLIST_INSERT_FIRST(poplist,stacke,varstackelem);
 11781176         } else {
 11791177                 if (t->n_op == TEMP) {
 11801178                         tempnr=regno(t)-defsites.low;
 11811179                 
 11821180                         if (SLIST_FIRST(&defsites.stack[tempnr])!=NULL) {
 11831181                                 x=SLIST_FIRST(&defsites.stack[tempnr])->tmpregno;
 11841182                                 regno(t)=x;
 11851183                         }
 11861184                 }
 11871185                 
 11881186                 opty = optype(t->n_op);
 11891187                 
 11901188                 if (opty != LTYPE)
 11911189                         renamevarhelper(p2e, t->n_left,poplist);
 11921190                 if (opty == BITYPE)
 11931191                         renamevarhelper(p2e, t->n_right,poplist);
 11941192         }
 11951193 }
 11961194 
 11971195 
 11981196 void
 11991197 renamevar(struct p2env *p2e,struct basicblock *bb)
 12001198 {
 12011199         struct interpass *ip;
 12021200         int h,j;
 12031201         SLIST_HEAD(, varstack) poplist;
 12041202         struct varstack *stacke;
 12051203         struct cfgnode *cfgn;
 12061204         struct cfgnode *cfgn2;
 12071205         int tmpregno,newtmpregno;
 12081206         struct phiinfo *phi;
 12091207         
 12101208         SLIST_INIT(&poplist);
 12111209         
 12121210         SLIST_FOREACH(phi,&bb->phi,phielem) {
 12131211                 tmpregno=phi->tmpregno-defsites.low;
 12141212                 
 12151213                 newtmpregno=p2e->epp->ip_tmpnum++;
 12161214                 phi->newtmpregno=newtmpregno;
 12171215                 
 12181216                 stacke=tmpcalloc(sizeof (struct varstack));
 12191217                 stacke->tmpregno=newtmpregno;
 12201218                 SLIST_INSERT_FIRST(&defsites.stack[tmpregno],stacke,varstackelem);
 12211219                 
 12221220                 stacke=tmpcalloc(sizeof (struct varstack));
 12231221                 stacke->tmpregno=tmpregno;
 12241222                 SLIST_INSERT_FIRST(&poplist,stacke,varstackelem);               
 12251223         }
 12261224         
 12271225         
 12281226         ip=bb->first;
 12291227         
 12301228         while (1) {             
 12311229                 if ( ip->type == IP_NODE) {
 12321230                         renamevarhelper(p2e,ip->ip_node,&poplist);
 12331231                 }
 12341232                 
 12351233                 if (ip==bb->last)
 12361234                         break;
 12371235                 
 12381236                 ip = DLIST_NEXT(ip, qelem);
 12391237         }
 12401238         
 12411239         SLIST_FOREACH(cfgn,&bb->children,cfgelem) {
 12421240                 j=0;
 12431241                 
 12441242                 SLIST_FOREACH(cfgn2, &cfgn->bblock->parents, cfgelem) {
 12451243                         if (cfgn2->bblock->dfnum==bb->dfnum)
 12461244                                 break;
 12471245                         
 12481246                         j++;
 12491247                 }
 12501248 
 12511249                 SLIST_FOREACH(phi,&cfgn->bblock->phi,phielem) {
 12521250                         phi->intmpregno[j]=SLIST_FIRST(&defsites.stack[phi->tmpregno-defsites.low])->tmpregno;
 12531251                 }
 12541252                 
 12551253         }
 12561254         
 12571255         for (h = 1; h < p2e->bbinfo.size; h++) {
 12581256                 if (!TESTBIT(bb->dfchildren, h))
 12591257                         continue;
 12601258                 
 12611259                 renamevar(p2e,p2e->bbinfo.arr[h]);
 12621260         }
 12631261         
 12641262         SLIST_FOREACH(stacke,&poplist,varstackelem) {
 12651263                 tmpregno=stacke->tmpregno;
 12661264                 
 12671265                 defsites.stack[tmpregno].q_forw=defsites.stack[tmpregno].q_forw->varstackelem.q_forw;
 12681266         }
 12691267 }
 12701268 
 12711269 enum pred_type {
 12721270     pred_unknown    = 0,
 12731271     pred_goto       = 1,
 12741272     pred_cond       = 2,
 12751273     pred_falltrough = 3,
 12761274 } ;
 12771275 
 12781276 void
 12791277 removephi(struct p2env *p2e)
 12801278 {
 12811279         struct basicblock *bb,*bbparent;
 12821280         struct cfgnode *cfgn;
 12831281         struct phiinfo *phi;
 12841282         int i;
 12851283         struct interpass *ip;
 12861284         struct interpass *pip;
 12871285         TWORD n_type;
 12881286 
 12891287         enum pred_type complex = pred_unknown ;
 12901288 
 12911289         int label=0;
 12921290         int newlabel;
 12931291         
 12941292         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {              
 12951293                 SLIST_FOREACH(phi,&bb->phi,phielem) {
 12961294                         /* Look at only one, notice break at end */
 12971295                         i=0;
 12981296                         
 12991297                         SLIST_FOREACH(cfgn, &bb->parents, cfgelem) {
 13001298                                 bbparent=cfgn->bblock;
 13011299                                 
 13021300                                 pip=bbparent->last;
 13031301                                 
 13041302                                 complex = pred_unknown ;
 13051303                                 
 13061304                                 BDEBUG(("removephi: %p in %d",pip,bb->dfnum));
 13071305 
 13081306                                 if (pip->type == IP_NODE && pip->ip_node->n_op == GOTO) {
 13091307                                         BDEBUG((" GOTO "));
 13101308                                         label = (int)pip->ip_node->n_left->n_lval;
 13111309                                         complex = pred_goto ;
 13121310                                 } else if (pip->type == IP_NODE && pip->ip_node->n_op == CBRANCH) {
 13131311                                         BDEBUG((" CBRANCH "));
 13141312                                         label = (int)pip->ip_node->n_right->n_lval;
 13151313                                         
 13161314                                         if (bb==p2e->labinfo.arr[label - p2e->ipp->ip_lblnum])
 13171315                                                 complex = pred_cond ;
 13181316                                         else
 13191317                                                 complex = pred_falltrough ;
 13201318 
 13211319                                 } else if (DLIST_PREV(bb, bbelem) == bbparent) {
 13221320                                         complex = pred_falltrough ;
 13231321                                 } else {
 13241322                                             /* PANIC */
 13251323                                         comperr("Assumption blown in rem-phi") ;
 13261324                                 }
 13271325       
 13281326                                 BDEBUG((" Complex: %d ",complex)) ;
 13291327 
 13301328                                 switch (complex) {
 13311329                                   case pred_goto:
 13321330                                         /* gotos can only go to this place. No bounce tab needed */
 13331331                                         SLIST_FOREACH(phi,&bb->phi,phielem) {
 13341332                                                 if (phi->intmpregno[i]>0) {
 13351333                                                         n_type=phi->n_type;
 13361334                                                         ip = ipnode(mkbinode(ASSIGN,
 13371335                                                              mktemp(phi->newtmpregno, n_type),
 13381336                                                              mktemp(phi->intmpregno[i],n_type),
 13391337                                                              n_type));
 13401338                                                         BDEBUG(("(%p, %d -> %d) ", ip, phi->intmpregno[i], phi->newtmpregno));
 13411339                                 
 13421340                                                         DLIST_INSERT_BEFORE((bbparent->last), ip, qelem);
 13431341                                                 }
 13441342                                         }
 13451343                                         break ;
 13461344                                   case pred_cond:
 13471345                                         /* Here, we need a jump pad */
 13481346                                         newlabel=getlab2();
 13491347                         
 13501348                                         ip = tmpalloc(sizeof(struct interpass));
 13511349                                         ip->type = IP_DEFLAB;
 13521350                                         /* Line number?? ip->lineno; */
 13531351                                         ip->ip_lbl = newlabel;
 13541352                                         DLIST_INSERT_BEFORE((bb->first), ip, qelem);
 13551353 
 13561354                                         SLIST_FOREACH(phi,&bb->phi,phielem) {
 13571355                                                 if (phi->intmpregno[i]>0) {
 13581356                                                         n_type=phi->n_type;
 13591357                                                         ip = ipnode(mkbinode(ASSIGN,
 13601358                                                              mktemp(phi->newtmpregno, n_type),
 13611359                                                              mktemp(phi->intmpregno[i],n_type),
 13621360                                                              n_type));
 13631361 
 13641362                                                         BDEBUG(("(%p, %d -> %d) ", ip, phi->intmpregno[i], phi->newtmpregno));
 13651363                                                         DLIST_INSERT_BEFORE((bb->first), ip, qelem);
 13661364                                                 }
 13671365                                         }
 13681366                                         /* add a jump to us */
 13691367                                         ip = ipnode(mkunode(GOTO, mklnode(ICON, label, 0, INT), 0, INT));
 13701368                                         DLIST_INSERT_BEFORE((bb->first), ip, qelem);
 13711369                                         pip->ip_node->n_right->n_lval=newlabel;
 13721370                                         break ;
 13731371                                   case pred_falltrough:
 13741372                                         if (bb->first->type == IP_DEFLAB) {
 13751373                                                 label = bb->first->ip_lbl;
 13761374                                                 BDEBUG(("falltrough label %d\n", label));
 13771375                                         } else {
 13781376                                                 comperr("BBlock has no label?") ;
 13791377                                         }
 13801378 
 13811379                                         /*
 13821380                                          * add a jump to us. We _will_ be, or already have, added code in between.
 13831381                                          * The code is created in the wrong order and switched at the insert, thus
 13841382                                          * comming out correctly
 13851383                                          */
 13861384 
 13871385                                         ip = ipnode(mkunode(GOTO, mklnode(ICON, label, 0, INT), 0, INT));
 13881386                                         DLIST_INSERT_AFTER((bbparent->last), ip, qelem);
 13891387 
 13901388                                         /* Add the code to the end, add a jump to us. */
 13911389                                         SLIST_FOREACH(phi,&bb->phi,phielem) {
 13921390                                                 if (phi->intmpregno[i]>0) {
 13931391                                                         n_type=phi->n_type;
 13941392                                                         ip = ipnode(mkbinode(ASSIGN,
 13951393                                                                 mktemp(phi->newtmpregno, n_type),
 13961394                                                                 mktemp(phi->intmpregno[i],n_type),
 13971395                                                                 n_type));
 13981396 
 13991397                                                         BDEBUG(("(%p, %d -> %d) ", ip, phi->intmpregno[i], phi->newtmpregno));
 14001398                                                         DLIST_INSERT_AFTER((bbparent->last), ip, qelem);
 14011399                                                 }
 14021400                                         }
 14031401                                         break ;
 14041402                                 default:
 14051403                                         comperr("assumption blown, complex is %d\n", complex) ;
 14061404                                 }
 14071405                                 BDEBUG(("\n"));
 14081406                                 i++;
 14091407                         }
 14101408                         break;
 14111409                 }
 14121410         }
 14131411 }
 14141412 
 14151413    
 14161414 /*
 14171415  * Remove unreachable nodes in the CFG.
 14181416  */
 14191417 
 14201418 void
 14211419 remunreach(struct p2env *p2e)
 14221420 {
 14231421         struct basicblock *bb, *nbb;
 14241422         struct interpass *next, *ctree;
 14251423 
 14261424         bb = DLIST_NEXT(&p2e->bblocks, bbelem);
 14271425         while (bb != &p2e->bblocks) {
 14281426                 nbb = DLIST_NEXT(bb, bbelem);
 14291427 
 14301428                 /* Code with dfnum 0 is unreachable */
 14311429                 if (bb->dfnum != 0) {
 14321430                         bb = nbb;
 14331431                         continue;
 14341432                 }
 14351433 
 14361434                 /* Need the epilogue node for other parts of the
 14371435                    compiler, set its label to 0 and backend will
 14381436                    handle it. */
 14391437                 if (bb->first->type == IP_EPILOG) {
 14401438                         bb->first->ip_lbl = 0;
 14411439                         bb = nbb;
 14421440                         continue;
 14431441                 }
 14441442 
 14451443                 next = bb->first;
 14461444                 do {
 14471445                         ctree = next;
 14481446                         next = DLIST_NEXT(ctree, qelem);
 14491447                         
 14501448                         if (ctree->type == IP_NODE)
 14511449                                 tfree(ctree->ip_node);
 14521450                         DLIST_REMOVE(ctree, qelem);
 14531451                 } while (ctree != bb->last);
 14541452                         
 14551453                 DLIST_REMOVE(bb, bbelem);
 14561454                 bb = nbb;
 14571455         }
 14581456 }
 14591457 
 14601458 void
 14611459 printip(struct interpass *pole)
 14621460 {
 14631461         static char *foo[] = {
 14641462            0, "NODE", "PROLOG", "STKOFF", "EPILOG", "DEFLAB", "DEFNAM", "ASM" };
 14651463         struct interpass *ip;
 14661464         struct interpass_prolog *ipplg, *epplg;
 14671465         unsigned i;
 14681466 
 14691467         DLIST_FOREACH(ip, pole, qelem) {
 14701468                 if (ip->type > MAXIP)
 14711469                         printf("IP(%d) (%p): ", ip->type, ip);
 14721470                 else
 14731471                         printf("%s (%p): ", foo[ip->type], ip);
 14741472                 switch (ip->type) {
 14751473                 case IP_NODE: printf("\n");
 14761474 #ifdef PCC_DEBUG
 14771475                         fwalk(ip->ip_node, e2print, 0); break;
 14781476 #endif
 14791477                 case IP_PROLOG:
 14801478                         ipplg = (struct interpass_prolog *)ip;
 14811479                         printf("%s %s regs",
 14821480                             ipplg->ipp_name, ipplg->ipp_vis ? "(local)" : "");
 14831481                         for (i = 0; i < NIPPREGS; i++)
 14841482                                 printf("%s0x%lx", i? ":" : " ",
 14851483                                     (long) ipplg->ipp_regs[i]);
 14861484                         printf(" autos %d mintemp %d minlbl %d\n",
 14871485                             ipplg->ipp_autos, ipplg->ip_tmpnum, ipplg->ip_lblnum);
 14881486                         break;
 14891487                 case IP_EPILOG:
 14901488                         epplg = (struct interpass_prolog *)ip;
 14911489                         printf("%s %s regs",
 14921490                             epplg->ipp_name, epplg->ipp_vis ? "(local)" : "");
 14931491                         for (i = 0; i < NIPPREGS; i++)
 14941492                                 printf("%s0x%lx", i? ":" : " ",
 14951493                                     (long) epplg->ipp_regs[i]);
 14961494                         printf(" autos %d mintemp %d minlbl %d\n",
 14971495                             epplg->ipp_autos, epplg->ip_tmpnum, epplg->ip_lblnum);
 14981496                         break;
 14991497                 case IP_DEFLAB: printf(LABFMT "\n", ip->ip_lbl); break;
 15001498                 case IP_DEFNAM: printf("\n"); break;
 15011499                 case IP_ASM: printf("%s\n", ip->ip_asm); break;
 15021500                 default:
 15031501                         break;
 15041502                 }
 15051503         }
 15061504 }
 15071505 
 15081506 #ifdef PCC_DEBUG
 15091507 void flownodeprint(NODE *p,FILE *flowdiagramfile);
 15101508 
 15111509 void
 15121510 flownodeprint(NODE *p,FILE *flowdiagramfile)
 15131511 {       
 15141512         int opty;
 15151513         char *o;
 15161514 
 15171515         fprintf(flowdiagramfile,"{");
 15181516 
 15191517         o=opst[p->n_op];
 15201518         
 15211519         while (*o != 0) {
 15221520                 if (*o=='<' || *o=='>')
 15231521                         fputc('\\',flowdiagramfile);
 15241522                 
 15251523                 fputc(*o,flowdiagramfile);
 15261524                 o++;
 15271525         }
 15281526         
 15291527         
 15301528         switch( p->n_op ) {                     
 15311529                 case REG:
 15321530                         fprintf(flowdiagramfile, " %s", rnames[p->n_rval] );
 15331531                         break;
 15341532                         
 15351533                 case TEMP:
 15361534                         fprintf(flowdiagramfile, " %d", regno(p));
 15371535                         break;
 15381536                         
 15391537                 case XASM:
 15401538                 case XARG:
 15411539                         fprintf(flowdiagramfile, " '%s'", p->n_name);
 15421540                         break;
 15431541                         
 15441542                 case ICON:
 15451543                 case NAME:
 15461544                 case OREG:
 15471545                         fprintf(flowdiagramfile, " " );
 15481546                         adrput(flowdiagramfile, p );
 15491547                         break;
 15501548                         
 15511549                 case STCALL:
 15521550                 case USTCALL:
 15531551                 case STARG:
 15541552                 case STASG:
 15551553                         fprintf(flowdiagramfile, " size=%d", p->n_stsize );
 15561554                         fprintf(flowdiagramfile, " align=%d", p->n_stalign );
 15571555                         break;
 15581556         }
 15591557         
 15601558         opty = optype(p->n_op);
 15611559         
 15621560         if (opty != LTYPE) {
 15631561                 fprintf(flowdiagramfile,"| {");
 15641562         
 15651563                 flownodeprint(p->n_left,flowdiagramfile);
 15661564         
 15671565                 if (opty == BITYPE) {
 15681566                         fprintf(flowdiagramfile,"|");
 15691567                         flownodeprint(p->n_right,flowdiagramfile);
 15701568                 }
 15711569                 fprintf(flowdiagramfile,"}");
 15721570         }
 15731571         
 15741572         fprintf(flowdiagramfile,"}");
 15751573 }
 15761574 
 15771575 void
 15781576 printflowdiagram(struct p2env *p2e, char *type) {
 15791577         struct basicblock *bbb;
 15801578         struct cfgnode *ccnode;
 15811579         struct interpass *ip;
 15821580         struct interpass_prolog *plg;
 15831581         struct phiinfo *phi;
 15841582         char *name;
 15851583         char *filename;
 15861584         int filenamesize;
 15871585         char *ext=".dot";
 15881586         FILE *flowdiagramfile;
 15891587         
 15901588         if (!g2debug)
 15911589                 return;
 15921590         
 15931591         bbb=DLIST_NEXT(&p2e->bblocks, bbelem);
 15941592         ip=bbb->first;
 15951593 
 15961594         if (ip->type != IP_PROLOG)
 15971595                 return;
 15981596         plg = (struct interpass_prolog *)ip;
 15991597 
 16001598         name=plg->ipp_name;
 16011599         
 16021600         filenamesize=strlen(name)+1+strlen(type)+strlen(ext)+1;
 16031601         filename=tmpalloc(filenamesize);
 16041602         snprintf(filename,filenamesize,"%s-%s%s",name,type,ext);
 16051603         
 16061604         flowdiagramfile=fopen(filename,"w");
 16071605         
 16081606         fprintf(flowdiagramfile,"digraph {\n");
 16091607         fprintf(flowdiagramfile,"rankdir=LR\n");
 16101608         
 16111609         DLIST_FOREACH(bbb, &p2e->bblocks, bbelem) {
 16121610                 ip=bbb->first;
 16131611                 
 16141612                 fprintf(flowdiagramfile,"bb%p [shape=record ",bbb);
 16151613                 
 16161614                 if (ip->type==IP_PROLOG)
 16171615                         fprintf(flowdiagramfile,"root ");
 16181616 
 16191617                 fprintf(flowdiagramfile,"label=\"");
 16201618                 
 16211619                 SLIST_FOREACH(phi,&bbb->phi,phielem) {
 16221620                         fprintf(flowdiagramfile,"Phi %d|",phi->tmpregno);
 16231621                 }               
 16241622                 
 16251623                 
 16261624                 while (1) {
 16271625                         switch (ip->type) {
 16281626                                 case IP_NODE:
 16291627                                         flownodeprint(ip->ip_node,flowdiagramfile);
 16301628                                         break;
 16311629                                         
 16321630                                 case IP_DEFLAB:
 16331631                                         fprintf(flowdiagramfile,"Label: %d", ip->ip_lbl);
 16341632                                         break;
 16351633                                         
 16361634                                 case IP_PROLOG:
 16371635                                         plg = (struct interpass_prolog *)ip;
 16381636         
 16391637                                         fprintf(flowdiagramfile,"%s %s",plg->ipp_name,type);
 16401638                                         break;
 16411639                         }
 16421640                         
 16431641                         fprintf(flowdiagramfile,"|");
 16441642                         fprintf(flowdiagramfile,"|");
 16451643                         
 16461644                         if (ip==bbb->last)
 16471645                                 break;
 16481646                         
 16491647                         ip = DLIST_NEXT(ip, qelem);
 16501648                 }
 16511649                 fprintf(flowdiagramfile,"\"]\n");
 16521650                 
 16531651                 SLIST_FOREACH(ccnode, &bbb->children, cfgelem) {
 16541652                         char *color="black";
 16551653                         struct interpass *pip=bbb->last;
 16561654 
 16571655                         if (pip->type == IP_NODE && pip->ip_node->n_op == CBRANCH) {
 16581656                                 int label = (int)pip->ip_node->n_right->n_lval;
 16591657                                 
 16601658                                 if (ccnode->bblock==p2e->labinfo.arr[label - p2e->ipp->ip_lblnum])
 16611659                                         color="red";
 16621660                         }
 16631661                         
 16641662                         fprintf(flowdiagramfile,"bb%p -> bb%p [color=%s]\n", bbb,ccnode->bblock,color);
 16651663                 }
 16661664         }
 16671665         
 16681666         fprintf(flowdiagramfile,"}\n");
 16691667         fclose(flowdiagramfile);
 16701668 }
 16711669 
 16721670 #endif
 16731671 
 16741672 /* walk all the programm */
 16751673 void WalkAll(struct p2env* p2e, void (*f) (NODE*, void*), void* arg, int type)
 16761674 {
 16771675         struct interpass *ipole = &p2e->ipole;
 16781676         struct interpass *ip ;
 16791677         if (0 != type) {
 16801678                 DLIST_FOREACH(ip, ipole, qelem) {
 16811679                         if (ip->type == IP_NODE && ip->ip_node->n_op == type)
 16821680                                 walkf(ip->ip_node, f, arg) ;
 16831681                 }
 16841682         } else {
 16851683                 DLIST_FOREACH(ip, ipole, qelem) {
 16861684                         if (ip->type == IP_NODE)
 16871685                                 walkf(ip->ip_node, f, arg) ;
 16881686                 }
 16891687         }
 16901688 }
 16911689 #if 0
 16921690 static int is_goto_label(struct interpass*g, struct interpass* l)
 16931691 {
 16941692         if (!g || !l)
 16951693                 return 0 ;
 16961694         if (g->type != IP_NODE) return 0 ;
 16971695         if (l->type != IP_DEFLAB) return 0 ;
 16981696         if (g->ip_node->n_op != GOTO) return 0 ;
 16991697         if (g->ip_node->n_left->n_lval != l->ip_lbl) return 0 ;
 17001698         return 1 ;
 17011699 }
 17021700 #endif
 17031701 
 17041702 /*
 17051703  * iterate over the basic blocks.
 17061704  * In case a block has only one successor and that one has only one pred, and the link is a goto:
 17071705  * place the second one immediately behind the first one (in terms of nodes, means cut&resplice).
 17081706  * This should take care of a lot of jumps.
 17091707  * one problem: Cannot move the first or last basic block (prolog/epilog). This is taken care of by
 17101708  * moving block #1 to #2, not #2 to #1
 17111709  * More complex (on the back cooker;) : first coalesc the inner loops (L1 cache), then go from inside out.
 17121710  */
 17131711 
 17141712 static unsigned long count_blocks(struct p2env* p2e)
 17151713 {
 17161714         struct basicblock* bb ;
 17171715         unsigned long count = 0 ;
 17181716         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 17191717                 ++count ;
 17201718         }
 17211719         return count ;
 17221720 }
 17231721 
 17241722 struct block_map {
 17251723         struct basicblock* block ;
 17261724         unsigned long index ;
 17271725         unsigned long thread ;
 17281726 } ;
 17291727 
 17301728 static unsigned long map_blocks(struct p2env* p2e, struct block_map* map, unsigned long count)
 17311729 {
 17321730         struct basicblock* bb ;
 17331731         unsigned long indx = 0 ;
 17341732         int ignore = 2 ;
 17351733         unsigned long thread ;
 17361734         unsigned long changes ;
 17371735 
 17381736         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 17391737                 map[indx].block = bb ;
 17401738                 map[indx].index = indx ;
 17411739 
 17421740                 /* ignore the first 2 labels, maybe up to 3 BBs */
 17431741                 if (ignore) {
 17441742                         if (bb->first->type == IP_DEFLAB)
 17451743                                 --ignore;
 17461744 
 17471745                         map[indx].thread = 1 ;  /* these are "fixed" */
 17481746                 } else
 17491747                         map[indx].thread = 0 ;
 17501748 
 17511749                 indx++ ;
 17521750         }
 17531751 
 17541752         thread = 1 ;
 17551753         do {
 17561754                 changes = 0 ;
 17571755                 
 17581756                 for (indx=0; indx < count; indx++) {
 17591757                         /* find block without trace */
 17601758                         if (map[indx].thread == 0) {
 17611759                                 /* do new thread */
 17621760                                 struct cfgnode *cnode ;
 17631761                                 struct basicblock *block2 = 0;
 17641762                                 unsigned long i ;
 17651763                                 unsigned long added ;
 17661764                                 
 17671765                                 BDEBUG (("new thread %ld at block %ld\n", thread, indx)) ;
 17681766 
 17691767                                 bb = map[indx].block ;
 17701768                                 do {
 17711769                                         added = 0 ;
 17721770 
 17731771                                         for (i=0; i < count; i++) {
 17741772                                                 if (map[i].block == bb && map[i].thread == 0) {
 17751773                                                         map[i].thread = thread ;
 17761774 
 17771775                                                         BDEBUG(("adding block %ld to trace %ld\n", i, thread)) ;
 17781776 
 17791777                                                         changes ++ ;
 17801778                                                         added++ ;
 17811779 
 17821780                                                         /*
 17831781                                                          * pick one from followers. For now (simple), pick the
 17841782                                                          * one who is directly following us. If none of that exists,
 17851783                                                          * this code picks the last one.
 17861784                                                          */
 17871785 
 17881786                                                         SLIST_FOREACH(cnode, &bb->children, cfgelem) {
 17891787                                                                 block2=cnode->bblock ;
 17901788 #if 1
 17911789                                                                 if (i+1 < count && map[i+1].block == block2)
 17921790                                                                         break ; /* pick that one */
 17931791 #else
 17941792                                                                 if (block2) break ;
 17951793 #endif
 17961794                                                         }
 17971795 
 17981796                                                         if (block2)
 17991797                                                                 bb = block2 ;
 18001798                                                 }
 18011799                                         }
 18021800                                 } while (added) ;
 18031801                                 thread++ ;
 18041802                         }
 18051803                 }
 18061804         } while (changes);
 18071805 
 18081806         /* Last block is also a thread on it's own, and the highest one. */
 18091807 /*
 18101808         thread++ ;
 18111809         map[count-1].thread = thread ;
 18121810 */
 18131811         if (b2debug) {
 18141812                 printf("Threads\n");
 18151813                 for (indx=0; indx < count; indx++) {
 18161814                         printf("Block #%ld (lbl %d) Thread %ld\n", indx, map[indx].block->first->ip_lbl, map[indx].thread);
 18171815                 }
 18181816         }
 18191817         return thread ;
 18201818 }
 18211819 
 18221820 
 18231821 void TraceSchedule(struct p2env* p2e)
 18241822 {
 18251823         struct block_map* map ;
 18261824         unsigned long block_count = count_blocks(p2e);
 18271825         unsigned long i ;
 18281826         unsigned long threads;
 18291827         struct interpass *front, *back ;
 18301828 
 18311829         map = tmpalloc(block_count * sizeof(struct block_map));
 18321830 
 18331831         threads = map_blocks(p2e, map, block_count) ;
 18341832 
 18351833         back = map[0].block->last ;
 18361834         for (i=1; i < block_count; i++) {
 18371835                 /* collect the trace */
 18381836                 unsigned long j ;
 18391837                 unsigned long thread = map[i].thread ;
 18401838                 if (thread) {
 18411839                         BDEBUG(("Thread %ld\n", thread)) ;
 18421840                         for (j=i; j < block_count; j++) {
 18431841                                 if (map[j].thread == thread) {
 18441842                                         front = map[j].block->first ;
 18451843 
 18461844                                         BDEBUG(("Trace %ld, old BB %ld, next BB %ld\t",
 18471845                                                 thread, i, j)) ;
 18481846                                         BDEBUG(("Label %d\n", front->ip_lbl)) ;
 18491847                                         DLIST_NEXT(back, qelem) = front ;
 18501848                                         DLIST_PREV(front, qelem) = back ;
 18511849                                         map[j].thread = 0 ;     /* done */
 18521850                                         back = map[j].block->last ;
 18531851                                         DLIST_NEXT(back, qelem) = 0 ;
 18541852                                 }
 18551853                         }
 18561854                 }
 18571855         }
 18581856         DLIST_NEXT(back, qelem) = &(p2e->ipole) ;
 18591857         DLIST_PREV(&p2e->ipole, qelem) = back ;
 18601858 }
 18611859 
 18621860 static void add_labels(struct p2env* p2e)
 18631861 {
 18641862         struct interpass *ipole = &p2e->ipole ;
 18651863         struct interpass *ip ;
 18661864 
 18671865         DLIST_FOREACH(ip, ipole, qelem) {
 18681866                 if (ip->type == IP_NODE && ip->ip_node->n_op == CBRANCH) {
 18691867                         struct interpass *n = DLIST_NEXT(ip, qelem);
 18701868                         if (n && n->type != IP_DEFLAB) {
 18711869                                 struct interpass* lab;
 18721870                                 int newlabel=getlab2() ;
 18731871 
 18741872                                 BDEBUG(("add_label L%d\n", newlabel));
 18751873 
 18761874                                 lab = tmpalloc(sizeof(struct interpass));
 18771875                                 lab->type = IP_DEFLAB;
 18781876                                 /* Line number?? ip->lineno; */
 18791877                                 lab->ip_lbl = newlabel;
 18801878                                 DLIST_INSERT_AFTER(ip, lab, qelem);
 18811879                         }
 18821880                 }
 18831881         }
 18841882 }
 18851883 
 18861884 /* node map */
 18871885 #ifdef ENABLE_NEW
 18881886 struct node_map {
 18891887         NODE* node ;            /* the node */
 18901888         unsigned int node_num ; /* node is equal to that one */
 18911889         unsigned int var_num ;  /* node computes this variable */
 18921890 } ;
 18931891 
 18941892 static unsigned long nodes_counter ;
 18951893 static void node_map_count_walker(NODE* n, void* x)
 18961894 {
 18971895         nodes_counter ++ ;
 18981896 }
 18991897 
 19001898 static void do_cse(struct p2env* p2e)
 19011899 {
 19021900         nodes_counter = 0 ;
 19031901         WalkAll(p2e, node_map_count_walker, 0, 0) ;
 19041902         BDEBUG(("Found %ld nodes\n", nodes_counter)) ;
 19051903 }
 19061904 #endif
 19071905 
FishEye: Open Source License registered to PCC.
Your maintenance has expired. You can renew your license at http://www.atlassian.com/fisheye/renew
Atlassian FishEye, CVS analysis. (Version:1.6.3 Build:build-336 2008-11-04) - Administration - Page generated 2014-10-31 13:10 +0100