Quick Search:

Mode

Context

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

Other Diffs

Ignore

Blank Lines Whitespace: Expand:

Diff

1.85
 
1.86
 
MAIN:plunky:20121107100717
 
optim2.c
_>11 /*      $Id$    */
 22 /*
 33  * Copyright (c) 2004 Anders Magnusson (ragge@ludd.luth.se).
 44  * All rights reserved.
 55  *
 66  * Redistribution and use in source and binary forms, with or without
 77  * modification, are permitted provided that the following conditions
 88  * are met:
 99  * 1. Redistributions of source code must retain the above copyright
 1010  *    notice, this list of conditions and the following disclaimer.
 1111  * 2. Redistributions in binary form must reproduce the above copyright
 1212  *    notice, this list of conditions and the following disclaimer in the
 1313  *    documentation and/or other materials provided with the distribution.
 1414  * 3. The name of the author may not be used to endorse or promote products
 1515  *    derived from this software without specific prior written permission
 1616  *
 1717  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 1818  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 1919  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 2020  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 2121  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 2222  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 2323  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 2424  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 2525  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 2626  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 2727  */
 2828 
 2929 #include "pass2.h"
 3030 
 3131 #include <string.h>
 3232 #include <stdlib.h>
 3333 
 3434 #ifndef MIN
 3535 #define MIN(a,b) (((a)<(b))?(a):(b))
 3636 #endif
 3737 
 3838 #ifndef MAX
 3939 #define MAX(a,b) (((a) > (b)) ? (a) : (b))
 4040 #endif
 4141 
 4242 #define BDEBUG(x)       if (b2debug) printf x
 4343 
 4444 #define mktemp(n, t)    mklnode(TEMP, 0, n, t)
 4545 
 4646 #define CHADD(bb,c)     { if (bb->ch[0] == 0) bb->ch[0] = c; \
 4747                           else if (bb->ch[1] == 0) bb->ch[1] = c; \
 4848                           else comperr("triple cfnodes"); }
 4949 #define FORCH(cn, chp)  \
 5050         for (cn = &chp[0]; cn < &chp[2] && cn[0]; cn++)
 5151 
 5252 /* main switch for new things not yet ready for all-day use */
 5353 /* #define ENABLE_NEW */
 5454 
 5555 
 5656 static int dfsnum;
 5757 
 5858 void saveip(struct interpass *ip);
 5959 void deljumps(struct p2env *);
 6060 void optdump(struct interpass *ip);
 6161 void printip(struct interpass *pole);
 6262 
 6363 static struct varinfo defsites;
 6464 struct interpass *storesave;
 6565 
 6666 void bblocks_build(struct p2env *);
 6767 void cfg_build(struct p2env *);
 6868 void cfg_dfs(struct basicblock *bb, unsigned int parent,
 6969              struct bblockinfo *bbinfo);
 7070 void dominators(struct p2env *);
 7171 struct basicblock *
 7272 ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo);
<>73 -void link(struct basicblock *parent, struct basicblock *child);
7473 void computeDF(struct p2env *, struct basicblock *bblock);
 7574 void printDF(struct p2env *p2e);
 7675 void findTemps(struct interpass *ip);
 7776 void placePhiFunctions(struct p2env *);
 7877 void renamevar(struct p2env *p2e,struct basicblock *bblock);
 7978 void removephi(struct p2env *p2e);
 8079 void remunreach(struct p2env *);
 8180 static void liveanal(struct p2env *p2e);
 8281 static void printip2(struct interpass *);
 8382 
 8483 /* create "proper" basic blocks, add labels where needed (so bblocks have labels) */
 8584 /* run before bb generate */
 8685 static void add_labels(struct p2env*) ;
 8786 
 8887 /* Perform trace scheduling, try to get rid of gotos as much as possible */
 8988 void TraceSchedule(struct p2env*) ;
 9089 
 9190 #ifdef ENABLE_NEW
 9291 static void do_cse(struct p2env* p2e) ;
 9392 #endif
 9493 
 9594 /* Walk the complete set, performing a function on each node.
 9695  * if type is given, apply function on only that type */
 9796 void WalkAll(struct p2env* p2e, void (*f) (NODE*, void*), void* arg, int type) ;
 9897 
 9998 void BBLiveDead(struct basicblock* bblock, int what, unsigned int variable) ;
 10099 
 101100 /* Fill the live/dead code */
 102101 void LiveDead(struct p2env* p2e, int what, unsigned int variable) ;
 103102 
 104103 #ifdef PCC_DEBUG
 105104 void printflowdiagram(struct p2env *, char *);
 106105 #endif
 107106 
 108107 void
 109108 optimize(struct p2env *p2e)
 110109 {
 111110         struct interpass *ipole = &p2e->ipole;
 112111 
 113112         if (b2debug) {
 114113                 printf("initial links\n");
 115114                 printip(ipole);
 116115         }
 117116 
 118117         if (xdeljumps)
 119118                 deljumps(p2e); /* Delete redundant jumps and dead code */
 120119 
 121120         if (xssa)
 122121                 add_labels(p2e) ;
 123122 #ifdef ENABLE_NEW
 124123         do_cse(p2e);
 125124 #endif
 126125 
 127126 #ifdef PCC_DEBUG
 128127         if (b2debug) {
 129128                 printf("links after deljumps\n");
 130129                 printip(ipole);
 131130         }
 132131 #endif
 133132         if (xssa || xtemps) {
 134133                 bblocks_build(p2e);
 135134                 BDEBUG(("Calling cfg_build\n"));
 136135                 cfg_build(p2e);
 137136         
 138137 #ifdef PCC_DEBUG
 139138                 printflowdiagram(p2e, "first");
 140139 #endif
 141140         }
 142141         if (xssa) {
 143142                 BDEBUG(("Calling liveanal\n"));
 144143                 liveanal(p2e);
 145144                 BDEBUG(("Calling dominators\n"));
 146145                 dominators(p2e);
 147146                 BDEBUG(("Calling computeDF\n"));
 148147                 computeDF(p2e, DLIST_NEXT(&p2e->bblocks, bbelem));
 149148 
 150149                 if (b2debug) {
 151150                         printDF(p2e);
 152151                 }
 153152 
 154153                 BDEBUG(("Calling placePhiFunctions\n"));
 155154 
 156155                 placePhiFunctions(p2e);
 157156 
 158157                 BDEBUG(("Calling renamevar\n"));
 159158 
 160159                 renamevar(p2e,DLIST_NEXT(&p2e->bblocks, bbelem));
 161160 
 162161                 BDEBUG(("Calling removephi\n"));
 163162 
 164163 #ifdef PCC_DEBUG
 165164                 printflowdiagram(p2e, "ssa");
 166165 #endif
 167166 
 168167                 removephi(p2e);
 169168 
 170169                 BDEBUG(("Calling remunreach\n"));
 171170 /*              remunreach(p2e); */
 172171                 
 173172                 /*
 174173                  * Recalculate basic blocks and cfg that was destroyed
 175174                  * by removephi
 176175                  */
 177176                 /* first, clean up all what deljumps should have done, and more */
 178177 
 179178                 /* TODO: add the basic blocks done by the ssa code by hand.
 180179                  * The trace scheduler should not change the order in
 181180                  * which blocks are executed or what data is calculated.
 182181                  * Thus, the BBlock order should remain correct.
 183182                  */
 184183 
 185184 #ifdef ENABLE_NEW
 186185                 bblocks_build(p2e);
 187186                 BDEBUG(("Calling cfg_build\n"));
 188187                 cfg_build(p2e);
 189188 
 190189                 TraceSchedule(p2e);
 191190 #ifdef PCC_DEBUG
 192191                 printflowdiagram(p2e, "sched_trace");
 193192 
 194193                 if (b2debug) {
 195194                         printf("after tracesched\n");
 196195                         printip(ipole);
 197196                         fflush(stdout) ;
 198197                 }
 199198 #endif
 200199 #endif
 201200 
 202201                 /* Now, clean up the gotos we do not need any longer */
 203202                 if (xdeljumps)
 204203                         deljumps(p2e); /* Delete redundant jumps and dead code */
 205204 
 206205                 bblocks_build(p2e);
 207206                 BDEBUG(("Calling cfg_build\n"));
 208207                 cfg_build(p2e);
 209208 
 210209 #ifdef PCC_DEBUG
 211210                 printflowdiagram(p2e, "no_phi");
 212211 
 213212                 if (b2debug) {
 214213                         printf("new tree\n");
 215214                         printip(ipole);
 216215                 }
 217216 #endif
 218217         }
 219218 
 220219 #ifdef PCC_DEBUG
 221220         {
 222221                 int i;
 223222                 for (i = NIPPREGS; i--; )
 224223                         if (p2e->epp->ipp_regs[i] != 0)
 225224                                 comperr("register error");
 226225         }
 227226 #endif
 228227 
 229228         myoptim(ipole);
 230229 }
 231230 
 232231 /*
 233232  * Delete unused labels, excess of labels, gotos to gotos.
 234233  * This routine can be made much more efficient.
 235234  *
 236235  * Layout of the statement list here (_must_ look this way!):
 237236  *      PROLOG
 238237  *      LABEL   - states beginning of function argument moves
 239238  *      ...code to save/move arguments
 240239  *      LABEL   - states beginning of execution code
 241240  *      ...code + labels in function in function
 242241  *      EPILOG
 243242  *
 244243  * This version of deljumps is based on the c2 implementation
 245244  * that were included in 2BSD.
 246245  */
 247246 #define LABEL 1
 248247 #define JBR     2
 249248 #define CBR     3
 250249 #define STMT    4
 251250 #define EROU    5
 252251 struct dlnod {
 253252         int op;
 254253         struct interpass *dlip;
 255254         struct dlnod *forw;
 256255         struct dlnod *back;
 257256         struct dlnod *ref;
 258257         int labno;
 259258         int refc;
 260259 };
 261260 
 262261 #ifdef DLJDEBUG
 263262 static void
 264263 dumplink(struct dlnod *dl)
 265264 {
 266265         printf("dumplink %p\n", dl);
 267266         for (; dl; dl = dl->forw) {
 268267                 if (dl->op == STMT) {
 269268                         printf("STMT(%p)\n", dl);
 270269                         fwalk(dl->dlip->ip_node, e2print, 0);
 271270                 } else if (dl->op == EROU) {
 272271                         printf("EROU(%p)\n", dl);
 273272                 } else {
 274273                         static char *str[] = { 0, "LABEL", "JBR", "CBR" };
 275274                         printf("%s(%p) %d refc %d ref %p\n", str[dl->op],
 276275                             dl, dl->labno, dl->refc, dl->ref);
 277276                 }
 278277         }
 279278         printf("end dumplink\n");
 280279 }
 281280 #endif
 282281 
 283282 /*
 284283  * Create the linked list that we can work on.
 285284  */
 286285 static void
 287286 listsetup(struct interpass *ipole, struct dlnod *dl)
 288287 {
 289288         struct interpass *ip = DLIST_NEXT(ipole, qelem);
 290289         struct interpass *nip;
 291290         struct dlnod *p, *lastp;
 292291         NODE *q;
 293292 
 294293         lastp = dl;
 295294         while (ip->type != IP_DEFLAB)
 296295                 ip = DLIST_NEXT(ip,qelem);
 297296         ip = DLIST_NEXT(ip,qelem);
 298297         while (ip->type != IP_DEFLAB)
 299298                 ip = DLIST_NEXT(ip,qelem);
 300299         /* Now ip is at the beginning */
 301300         for (;;) {
 302301                 ip = DLIST_NEXT(ip,qelem);
 303302                 if (ip == ipole)
 304303                         break;
 305304                 p = tmpalloc(sizeof(struct dlnod));
 306305                 p->labno = 0;
 307306                 p->dlip = ip;
 308307                 switch (ip->type) {
 309308                 case IP_DEFLAB:
 310309                         p->op = LABEL;
 311310                         p->labno = ip->ip_lbl;
 312311                         break;
 313312 
 314313                 case IP_NODE:
 315314                         q = ip->ip_node;
 316315                         switch (q->n_op) {
 317316                         case GOTO:
 318317                                 if (q->n_left->n_op == ICON) {
 319318                                         p->op = JBR;
 320319                                         p->labno = q->n_left->n_lval;
 321320                                 } else
 322321                                         p->op = STMT;
 323322                                 break;
 324323                         case CBRANCH:
 325324                                 p->op = CBR;
 326325                                 p->labno = q->n_right->n_lval;
 327326                                 break;
 328327                         case ASSIGN:
 329328                                 /* remove ASSIGN to self for regs */
 330329                                 if (q->n_left->n_op == REG &&
 331330                                     q->n_right->n_op == REG &&
 332331                                     regno(q->n_left) == regno(q->n_right)) {
 333332                                         nip = DLIST_PREV(ip, qelem);
 334333                                         tfree(q);
 335334                                         DLIST_REMOVE(ip, qelem);
 336335                                         ip = nip;
 337336                                         continue;
 338337                                 }
 339338                                 /* FALLTHROUGH */
 340339                         default:
 341340                                 p->op = STMT;
 342341                                 break;
 343342                         }
 344343                         break;
 345344 
 346345                 case IP_ASM:
 347346                         p->op = STMT;
 348347                         break;
 349348 
 350349                 case IP_EPILOG:
 351350                         p->op = EROU;
 352351                         break;
 353352 
 354353                 default:
 355354                         comperr("listsetup: bad ip node %d", ip->type);
 356355                 }
 357356                 p->forw = 0;
 358357                 p->back = lastp;
 359358                 lastp->forw = p;
 360359                 lastp = p;
 361360                 p->ref = 0;
 362361         }
 363362 }
 364363 
 365364 /*
 366365  * Traverse to the first statement behind a label.
 367366  */
 368367 static struct dlnod *
 369368 nonlab(struct dlnod *p)
 370369 {
 371370         while (p && p->op==LABEL)
 372371                 p = p->forw;
 373372         return(p);
 374373 }
 375374 
 376375 static void
 377376 iprem(struct dlnod *p)
 378377 {
 379378         if (p->dlip->type == IP_NODE)
 380379                 tfree(p->dlip->ip_node);
 381380         DLIST_REMOVE(p->dlip, qelem);
 382381 }
 383382 
 384383 static void
 385384 decref(struct dlnod *p)
 386385 {
 387386         if (--p->refc <= 0) {
 388387                 iprem(p);
 389388                 p->back->forw = p->forw;
 390389                 p->forw->back = p->back;
 391390         }
 392391 }
 393392 
 394393 /*
 395394  * Change a label number for jump/branch instruction to labno.
 396395  */
 397396 static void
 398397 setlab(struct dlnod *p, int labno)
 399398 {
 400399         p->labno = labno;
 401400         if (p->op == JBR)
 402401                 p->dlip->ip_node->n_left->n_lval = labno;
 403402         else if (p->op == CBR) {
 404403                 p->dlip->ip_node->n_right->n_lval = labno;
 405404                 p->dlip->ip_node->n_left->n_label = labno;
 406405         } else
 407406                 comperr("setlab bad op %d", p->op);
 408407 }
 409408 
 410409 /*
 411410  * See if a label is used outside of us.
 412411  */
 413412 static int
 414413 inuse(struct p2env *p2e, int lbl)
 415414 {
 416415         int *l;
 417416 
 418417         for (l = p2e->epp->ip_labels; *l; l++)
 419418                 if (*l == lbl)
 420419                         return 1;
 421420         return 0;
 422421 }
 423422 
 424423 /*
 425424  * Label reference counting and removal of unused labels.
 426425  */
 427426 #define LABHS 127
 428427 static void
 429428 refcount(struct p2env *p2e, struct dlnod *dl)
 430429 {
 431430         struct dlnod *p, *lp;
 432431         struct dlnod *labhash[LABHS];
 433432         struct dlnod **hp, *tp;
 434433 
 435434         /* Clear label hash */
 436435         for (hp = labhash; hp < &labhash[LABHS];)
 437436                 *hp++ = 0;
 438437         /* Enter labels into hash.  Later overwrites earlier */
 439438         for (p = dl->forw; p!=0; p = p->forw) {
 440439                 if (p->op==LABEL) {
 441440                         labhash[p->labno % LABHS] = p;
 442441                         p->refc = 0;
 443442                         if (inuse(p2e, p->labno))
 444443                                 p->refc = 1000; /* never remove */
 445444                 }
 446445         }
 447446         /* search for jumps to labels and fill in reference */
 448447         for (p = dl->forw; p!=0; p = p->forw) {
 449448                 if (p->op==JBR || p->op==CBR) {
 450449                         p->ref = 0;
 451450                         lp = labhash[p->labno % LABHS];
 452451                         if (lp==0 || p->labno!=lp->labno)
 453452                             for (lp = dl->forw; lp!=0; lp = lp->forw) {
 454453                                 if (lp->op==LABEL && p->labno==lp->labno)
 455454                                         break;
 456455                             }
 457456                         if (lp) {
 458457                                 tp = nonlab(lp)->back;
 459458                                 if (tp!=lp) {
 460459                                         setlab(p, tp->labno);
 461460                                         lp = tp;
 462461                                 }
 463462                                 p->ref = lp;
 464463                                 lp->refc++;
 465464                         }
 466465                 }
 467466         }
 468467         for (p = dl->forw; p!=0; p = p->forw)
 469468                 if (p->op==LABEL && p->refc==0 && (lp = nonlab(p))->op)
 470469                         decref(p);
 471470 }
 472471 
 473472 static int nchange;
 474473 
 475474 static struct dlnod *
 476475 codemove(struct dlnod *p)
 477476 {
 478477         struct dlnod *p1, *p2, *p3;
 479478 #ifdef notyet
 480479         struct dlnod *t, *tl;
 481480         int n;
 482481 #endif
 483482 
 484483         p1 = p;
 485484         if (p1->op!=JBR || (p2 = p1->ref)==0)
 486485                 return(p1);
 487486         while (p2->op == LABEL)
 488487                 if ((p2 = p2->back) == 0)
 489488                         return(p1);
 490489         if (p2->op!=JBR)
 491490                 goto ivloop;
 492491         if (p1==p2)
 493492                 return(p1);
 494493         p2 = p2->forw;
 495494         p3 = p1->ref;
 496495         while (p3) {
 497496                 if (p3->op==JBR) {
 498497                         if (p1==p3 || p1->forw==p3 || p1->back==p3)
 499498                                 return(p1);
 500499                         nchange++;
 501500                         p1->back->forw = p2;
 502501                         p1->dlip->qelem.q_back->qelem.q_forw = p2->dlip;
 503502 
 504503                         p1->forw->back = p3;
 505504                         p1->dlip->qelem.q_forw->qelem.q_back = p3->dlip;
 506505 
 507506 
 508507                         p2->back->forw = p3->forw;
 509508                         p2->dlip->qelem.q_back->qelem.q_forw = p3->forw->dlip;
 510509 
 511510                         p3->forw->back = p2->back;
 512511                         p3->dlip->qelem.q_forw->qelem.q_back = p2->back->dlip;
 513512 
 514513                         p2->back = p1->back;
 515514                         p2->dlip->qelem.q_back = p1->dlip->qelem.q_back;
 516515 
 517516                         p3->forw = p1->forw;
 518517                         p3->dlip->qelem.q_forw = p1->forw->dlip;
 519518 
 520519                         decref(p1->ref);
 521520                         if (p1->dlip->type == IP_NODE)
 522521                                 tfree(p1->dlip->ip_node);
 523522 
 524523                         return(p2);
 525524                 } else
 526525                         p3 = p3->forw;
 527526         }
 528527         return(p1);
 529528 
 530529 ivloop:
 531530         if (p1->forw->op!=LABEL)
 532531                 return(p1);
 533532         return(p1);
 534533 
 535534 #ifdef notyet
 536535         p3 = p2 = p2->forw;
 537536         n = 16;
 538537         do {
 539538                 if ((p3 = p3->forw) == 0 || p3==p1 || --n==0)
 540539                         return(p1);
 541540         } while (p3->op!=CBR || p3->labno!=p1->forw->labno);
 542541         do
 543542                 if ((p1 = p1->back) == 0)
 544543                         return(p);
 545544         while (p1!=p3);
 546545         p1 = p;
 547546         tl = insertl(p1);
 548547         p3->subop = revbr[p3->subop];
 549548         decref(p3->ref);
 550549                 p2->back->forw = p1;
 551550         p3->forw->back = p1;
 552551         p1->back->forw = p2;
 553552         p1->forw->back = p3;
 554553         t = p1->back;
 555554         p1->back = p2->back;
 556555         p2->back = t;
 557556         t = p1->forw;
 558557         p1->forw = p3->forw;
 559558         p3->forw = t;
 560559         p2 = insertl(p1->forw);
 561560         p3->labno = p2->labno;
 562561         p3->ref = p2;
 563562         decref(tl);
 564563         if (tl->refc<=0)
 565564                 nrlab--;
 566565         nchange++;
 567566         return(p3);
 568567 #endif
 569568 }
 570569 
 571570 static void
 572571 iterate(struct p2env *p2e, struct dlnod *dl)
 573572 {
 574573         struct dlnod *p, *rp, *p1;
 575574         extern int negrel[];
 576575         extern size_t negrelsize;
 577576         int i;
 578577 
 579578         nchange = 0;
 580579         for (p = dl->forw; p!=0; p = p->forw) {
 581580                 if ((p->op==JBR||p->op==CBR) && p->ref) {
 582581                         /* Resolves:
 583582                          * jbr L7
 584583                          * ...
 585584                          * L7: jbr L8
 586585                          */
 587586                         rp = nonlab(p->ref);
 588587                         if (rp->op==JBR && rp->labno && p->labno!=rp->labno) {
 589588                                 setlab(p, rp->labno);
 590589                                 decref(p->ref);
 591590                                 rp->ref->refc++;
 592591                                 p->ref = rp->ref;
 593592                                 nchange++;
 594593                         }
 595594                 }
 596595                 if (p->op==CBR && (p1 = p->forw)->op==JBR) {
 597596                         /* Resolves:
 598597                          * cbr L7
 599598                          * jbr L8
 600599                          * L7:
 601600                          */
 602601                         rp = p->ref;
 603602                         do
 604603                                 rp = rp->back;
 605604                         while (rp->op==LABEL);
 606605                         if (rp==p1) {
 607606                                 decref(p->ref);
 608607                                 p->ref = p1->ref;
 609608                                 setlab(p, p1->labno);
 610609 
 611610                                 iprem(p1);
 612611 
 613612                                 p1->forw->back = p;
 614613                                 p->forw = p1->forw;
 615614 
 616615                                 i = p->dlip->ip_node->n_left->n_op;
 617616                                 if (i < EQ || i - EQ >= (int)negrelsize)
 618617                                         comperr("deljumps: unexpected op");
 619618                                 p->dlip->ip_node->n_left->n_op = negrel[i - EQ];
 620619                                 nchange++;
 621620                         }
 622621                 }
 623622                 if (p->op == JBR) {
 624623                         /* Removes dead code */
 625624                         while (p->forw && p->forw->op!=LABEL &&
 626625                             p->forw->op!=EROU) {
 627626                                 nchange++;
 628627                                 if (p->forw->ref)
 629628                                         decref(p->forw->ref);
 630629 
 631630                                 iprem(p->forw);
 632631 
 633632                                 p->forw = p->forw->forw;
 634633                                 p->forw->back = p;
 635634                         }
 636635                         rp = p->forw;
 637636                         while (rp && rp->op==LABEL) {
 638637                                 if (p->ref == rp) {
 639638                                         p->back->forw = p->forw;
 640639                                         p->forw->back = p->back;
 641640                                         iprem(p);
 642641                                         p = p->back;
 643642                                         decref(rp);
 644643                                         nchange++;
 645644                                         break;
 646645                                 }
 647646                                 rp = rp->forw;
 648647                         }
 649648                 }
 650649                 if (p->op == JBR) {
 651650                         /* xjump(p); * needs tree rewrite; not yet */
 652651                         p = codemove(p);
 653652                 }
 654653         }
 655654 }
 656655 
 657656 void
 658657 deljumps(struct p2env *p2e)
 659658 {
 660659         struct interpass *ipole = &p2e->ipole;
 661660         struct dlnod dln;
 662661         MARK mark;
 663662 
 664663         markset(&mark);
 665664 
 666665         memset(&dln, 0, sizeof(dln));
 667666         listsetup(ipole, &dln);
 668667         do {
 669668                 refcount(p2e, &dln);
 670669                 do {
 671670                         iterate(p2e, &dln);
 672671                 } while (nchange);
 673672 #ifdef notyet
 674673                 comjump();
 675674 #endif
 676675         } while (nchange);
 677676 
 678677         markfree(&mark);
 679678 }
 680679 
 681680 void
 682681 optdump(struct interpass *ip)
 683682 {
 684683         static char *nm[] = { "node", "prolog", "newblk", "epilog", "locctr",
 685684                 "deflab", "defnam", "asm" };
 686685         printf("type %s\n", nm[ip->type-1]);
 687686         switch (ip->type) {
 688687         case IP_NODE:
 689688 #ifdef PCC_DEBUG
 690689                 fwalk(ip->ip_node, e2print, 0);
 691690 #endif
 692691                 break;
 693692         case IP_DEFLAB:
 694693                 printf("label " LABFMT "\n", ip->ip_lbl);
 695694                 break;
 696695         case IP_ASM:
 697696                 printf(": %s\n", ip->ip_asm);
 698697                 break;
 699698         }
 700699 }
 701700 
 702701 /*
 703702  * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
 704703  *
 705704  * Also fills the labelinfo struct with information about which bblocks
 706705  * that contain which label.
 707706  */
 708707 
 709708 void
 710709 bblocks_build(struct p2env *p2e)
 711710 {
 712711         struct interpass *ipole = &p2e->ipole;
 713712         struct interpass *ip;
 714713         struct basicblock *bb = NULL;
 715714         int low, high;
 716715         int count = 0;
 717716         int i;
 718717 
 719718         BDEBUG(("bblocks_build (%p, %p)\n", &p2e->labinfo, &p2e->bbinfo));
 720719         low = p2e->ipp->ip_lblnum;
 721720         high = p2e->epp->ip_lblnum;
 722721 
 723722         /*
 724723          * First statement is a leader.
 725724          * Any statement that is target of a jump is a leader.
 726725          * Any statement that immediately follows a jump is a leader.
 727726          */
 728727         DLIST_INIT(&p2e->bblocks, bbelem);
 729728         DLIST_FOREACH(ip, ipole, qelem) {
 730729                 if (bb == NULL || (ip->type == IP_EPILOG) ||
 731730                     (ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) {
 732731                         bb = tmpalloc(sizeof(struct basicblock));
 733732                         bb->first = ip;
 734733                         SLIST_INIT(&bb->parents);
 735734                         SLIST_INIT(&bb->child);
 736735                         bb->dfnum = 0;
 737736                         bb->dfparent = 0;
 738737                         bb->semi = 0;
 739738                         bb->ancestor = 0;
 740739                         bb->idom = 0;
 741740                         bb->samedom = 0;
 742741                         bb->bucket = NULL;
 743742                         bb->df = NULL;
 744743                         bb->dfchildren = NULL;
 745744                         bb->Aorig = NULL;
 746745                         bb->Aphi = NULL;
 747746                         SLIST_INIT(&bb->phi);
 748747                         bb->bbnum = count;
 749748                         DLIST_INSERT_BEFORE(&p2e->bblocks, bb, bbelem);
 750749                         count++;
 751750                 }
 752751                 bb->last = ip;
 753752                 if ((ip->type == IP_NODE) && (ip->ip_node->n_op == GOTO ||
 754753                     ip->ip_node->n_op == CBRANCH))
 755754                         bb = NULL;
 756755                 if (ip->type == IP_PROLOG)
 757756                         bb = NULL;
 758757         }
 759758         p2e->nbblocks = count;
 760759 
 761760         if (b2debug) {
 762761                 printf("Basic blocks in func: %d, low %d, high %d\n",
 763762                     count, low, high);
 764763                 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 765764                         printf("bb(%d) %p: first %p last %p\n", bb->bbnum, bb,
 766765                             bb->first, bb->last);
 767766                 }
 768767         }
 769768 
 770769         p2e->labinfo.low = low;
 771770         p2e->labinfo.size = high - low + 1;
 772771         p2e->labinfo.arr = tmpalloc(p2e->labinfo.size * sizeof(struct basicblock *));
 773772         for (i = 0; i < p2e->labinfo.size; i++) {
 774773                 p2e->labinfo.arr[i] = NULL;
 775774         }
 776775         
 777776         p2e->bbinfo.size = count + 1;
 778777         p2e->bbinfo.arr = tmpalloc(p2e->bbinfo.size * sizeof(struct basicblock *));
 779778         for (i = 0; i < p2e->bbinfo.size; i++) {
 780779                 p2e->bbinfo.arr[i] = NULL;
 781780         }
 782781 
 783782         /* Build the label table */
 784783         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 785784                 if (bb->first->type == IP_DEFLAB)
 786785                         p2e->labinfo.arr[bb->first->ip_lbl - low] = bb;
 787786         }
 788787 
 789788         if (b2debug) {
 790789                 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 791790                         printf("bblock %d\n", bb->bbnum);
 792791                         for (ip = bb->first; ip != bb->last;
 793792                             ip = DLIST_NEXT(ip, qelem)) {
 794793                                 printip2(ip);
 795794                         }
 796795                         printip2(ip);
 797796                 }
 798797 
 799798                 printf("Label table:\n");
 800799                 for (i = 0; i < p2e->labinfo.size; i++)
 801800                         if (p2e->labinfo.arr[i])
 802801                                 printf("Label %d bblock %p\n", i+low,
 803802                                     p2e->labinfo.arr[i]);
 804803         }
 805804 }
 806805 
 807806 /*
 808807  * Build the control flow graph.
 809808  */
 810809 
 811810 void
 812811 cfg_build(struct p2env *p2e)
 813812 {
 814813         /* Child and parent nodes */
 815814         struct cfgnode *cnode;
 816815         struct cfgnode *pnode;
 817816         struct basicblock *bb;
 818817         NODE *p;
 819818 
 820819 #ifdef notyet
 821820         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 822821                 if (bb->first->type == IP_EPILOG)
 823822                         break;
 824823 
 825824                 if (bb->last->type == IP_NODE) {
 826825                         p = bb->last->ip_node;
 827826                         switch (p->n_op) {
 828827                         case GOTO:
 829828                                 if (p->n_left->n_op == ICON) {
 830829                                         lbchk(p2e, p->n_left->n_lval);
 831830                                         fillcnode(p2e, p->n_left->n_lval, bb);
 832831                                 } else {
 833832                                 }
 834833                                 break;
 835834 
 836835                         case CBRANCH:
 837836                                 lbchk(p2e, p->n_right->n_lval);
 838837                                 fillcnode(p2e, p->n_right->n_lval, bb);
 839838                                 ...
 840839 
 841840                         default:
 842841                                 ...
 843842                         }
 844843                 } else {
 845844                         ...
 846845                 }
 847846         }
 848847 #endif
 849848 
 850849         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 851850                 if (bb->first->type == IP_EPILOG)
 852851                         break;
 853852         
 854853                 cnode = tmpalloc(sizeof(struct cfgnode));
 855854                 pnode = tmpalloc(sizeof(struct cfgnode));
 856855                 pnode->bblock = bb;
 857856 
 858857                 p = bb->last->ip_node;
 859858                 if (bb->last->type == IP_NODE && p->n_op == GOTO) {
 860859                         if (p->n_left->n_op == ICON) {
 861860                                 if (p->n_left->n_lval - p2e->labinfo.low > p2e->labinfo.size)
 862861                                         comperr("Label out of range: %d, base %d",
 863862                                             p->n_left->n_lval, p2e->labinfo.low);
 864863                                 cnode->bblock = p2e->labinfo.arr[p->n_left->n_lval - p2e->labinfo.low];
 865864                                 SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 866865                                 SLIST_INSERT_LAST(&bb->child, cnode, chld);
 867866                         } else {
 868867                                 int *l;
 869868                                 /* XXX assume all labels are valid as dest */
 870869                                 for (l = p2e->epp->ip_labels; *l; l++) {
 871870                                         cnode->bblock = p2e->labinfo.arr[*l - p2e->labinfo.low];
 872871                                         SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 873872                                         SLIST_INSERT_LAST(&bb->child, cnode, chld);
 874873                                         cnode = tmpalloc(sizeof(struct cfgnode));
 875874                                         pnode = tmpalloc(sizeof(struct cfgnode));
 876875                                         pnode->bblock = bb;
 877876                                 }
 878877                         }
 879878                         continue;
 880879                 }
 881880                 if ((bb->last->type == IP_NODE) && p->n_op == CBRANCH) {
 882881                         if (p->n_right->n_lval - p2e->labinfo.low > p2e->labinfo.size)
 883882                                 comperr("Label out of range: %d", p->n_left->n_lval);
 884883 
 885884                         cnode->bblock = p2e->labinfo.arr[p->n_right->n_lval - p2e->labinfo.low];
 886885                         SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 887886                         SLIST_INSERT_LAST(&bb->child, cnode, chld);
 888887                         cnode = tmpalloc(sizeof(struct cfgnode));
 889888                         pnode = tmpalloc(sizeof(struct cfgnode));
 890889                         pnode->bblock = bb;
 891890                 }
 892891 
 893892                 cnode->bblock = DLIST_NEXT(bb, bbelem);
 894893                 SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 895894                 SLIST_INSERT_LAST(&bb->child, cnode, chld);
 896895         }
 897896 }
 898897 
 899898 void
 900899 cfg_dfs(struct basicblock *bb, unsigned int parent, struct bblockinfo *bbinfo)
 901900 {
 902901         struct cfgnode *cn;
 903902 
 904903         if (bb->dfnum != 0)
 905904                 return;
 906905 
 907906         bb->dfnum = ++dfsnum;
 908907         bb->dfparent = parent;
 909908         bbinfo->arr[bb->dfnum] = bb;
 910909         SLIST_FOREACH(cn, &bb->child, chld)
 911910                 cfg_dfs(cn->bblock, bb->dfnum, bbinfo);
 912911         /* Don't bring in unreachable nodes in the future */
 913912         bbinfo->size = dfsnum + 1;
 914913 }
 915914 
 916915 static bittype *
 917916 setalloc(int nelem)
 918917 {
 919918         bittype *b;
 920919         int sz = (nelem+NUMBITS-1)/NUMBITS;
 921920 
 922921         b = tmpalloc(sz * sizeof(bittype));
 923922         memset(b, 0, sz * sizeof(bittype));
 924923         return b;
 925924 }
 926925 
 927926 /*
 928927  * Algorithm 19.9, pp 414 from Appel.
 929928  */
 930929 
 931930 void
 932931 dominators(struct p2env *p2e)
 933932 {
 934933         struct cfgnode *cnode;
 935934         struct basicblock *bb, *y, *v;
 936935         struct basicblock *s, *sprime, *p;
 937936         int h, i;
 938937 
 939938         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 940939                 bb->bucket = setalloc(p2e->bbinfo.size);
 941940                 bb->df = setalloc(p2e->bbinfo.size);
 942941                 bb->dfchildren = setalloc(p2e->bbinfo.size);
 943942         }
 944943 
 945944         dfsnum = 0;
 946945         cfg_dfs(DLIST_NEXT(&p2e->bblocks, bbelem), 0, &p2e->bbinfo);
 947946 
 948947         if (b2debug) {
 949948                 struct basicblock *bbb;
 950949                 struct cfgnode *ccnode, *cn;
 951950 
 952951                 DLIST_FOREACH(bbb, &p2e->bblocks, bbelem) {
 953952                         printf("Basic block %d, parents: ", bbb->dfnum);
 954953                         SLIST_FOREACH(ccnode, &bbb->parents, cfgelem) {
 955954                                 printf("%d, ", ccnode->bblock->dfnum);
 956955                         }
 957956                         printf("\nChildren: ");
 958957                         SLIST_FOREACH(cn, &bbb->child, chld)
 959958                                 printf("%d, ", cn->bblock->dfnum);
 960959                         printf("\n");
 961960                 }
 962961         }
 963962 
 964963         for(h = p2e->bbinfo.size - 1; h > 1; h--) {
 965964                 bb = p2e->bbinfo.arr[h];
 966965                 p = s = p2e->bbinfo.arr[bb->dfparent];
 967966                 SLIST_FOREACH(cnode, &bb->parents, cfgelem) {
 968967                         if (cnode->bblock->dfnum ==0)
 969968                                 continue; /* Ignore unreachable code */
 970969 
 971970                         if (cnode->bblock->dfnum <= bb->dfnum)
 972971                                 sprime = cnode->bblock;
 973972                         else
 974973                                 sprime = p2e->bbinfo.arr[ancestorwithlowestsemi
 975974                                               (cnode->bblock, &p2e->bbinfo)->semi];
 976975                         if (sprime->dfnum < s->dfnum)
 977976                                 s = sprime;
 978977                 }
 979978                 bb->semi = s->dfnum;
 980979                 BITSET(s->bucket, bb->dfnum);
<>981 -                link(p, bb);
  980+                bb->ancestor = p->dfnum;
982981                 for (i = 1; i < p2e->bbinfo.size; i++) {
 983982                         if(TESTBIT(p->bucket, i)) {
 984983                                 v = p2e->bbinfo.arr[i];
 985984                                 y = ancestorwithlowestsemi(v, &p2e->bbinfo);
 986985                                 if (y->semi == v->semi)
 987986                                         v->idom = p->dfnum;
 988987                                 else
 989988                                         v->samedom = y->dfnum;
 990989                         }
 991990                 }
 992991                 memset(p->bucket, 0, (p2e->bbinfo.size + 7)/8);
 993992         }
 994993 
 995994         if (b2debug) {
 996995                 printf("Num\tSemi\tAncest\tidom\n");
 997996                 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 998997                         printf("%d\t%d\t%d\t%d\n", bb->dfnum, bb->semi,
 999998                             bb->ancestor, bb->idom);
 1000999                 }
 10011000         }
 10021001 
 10031002         for(h = 2; h < p2e->bbinfo.size; h++) {
 10041003                 bb = p2e->bbinfo.arr[h];
 10051004                 if (bb->samedom != 0) {
 10061005                         bb->idom = p2e->bbinfo.arr[bb->samedom]->idom;
 10071006                 }
 10081007         }
 10091008         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 10101009                 if (bb->idom != 0 && bb->idom != bb->dfnum) {
 10111010                         BDEBUG(("Setting child %d of %d\n",
 10121011                             bb->dfnum, p2e->bbinfo.arr[bb->idom]->dfnum));
 10131012                         BITSET(p2e->bbinfo.arr[bb->idom]->dfchildren, bb->dfnum);
 10141013                 }
 10151014         }
 10161015 }
 10171016 
 10181017 
 10191018 struct basicblock *
 10201019 ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo)
 10211020 {
 10221021         struct basicblock *u = bblock;
 10231022         struct basicblock *v = bblock;
 10241023 
 10251024         while (v->ancestor != 0) {
 10261025                 if (bbinfo->arr[v->semi]->dfnum <
 10271026                     bbinfo->arr[u->semi]->dfnum)
 10281027                         u = v;
 10291028                 v = bbinfo->arr[v->ancestor];
 10301029         }
 10311030         return u;
 10321031 }
 10331032 
 10341033 void
<>1035 -link(struct basicblock *parent, struct basicblock *child)
 1036 -{
 1037 -        child->ancestor = parent->dfnum;
 1038 -}
 1039 -
 1040 -void
<_10411034 computeDF(struct p2env *p2e, struct basicblock *bblock)
 10421035 {
 10431036         struct cfgnode *cn;
 10441037         int h, i;
 10451038         
 10461039         SLIST_FOREACH(cn, &bblock->child, chld) {
 10471040                 if (cn->bblock->idom != bblock->dfnum)
 10481041                         BITSET(bblock->df, cn->bblock->dfnum);
 10491042         }
 10501043         for (h = 1; h < p2e->bbinfo.size; h++) {
 10511044                 if (!TESTBIT(bblock->dfchildren, h))
 10521045                         continue;
 10531046                 computeDF(p2e, p2e->bbinfo.arr[h]);
 10541047                 for (i = 1; i < p2e->bbinfo.size; i++) {
 10551048                         if (TESTBIT(p2e->bbinfo.arr[h]->df, i) &&
 10561049                             (p2e->bbinfo.arr[i] == bblock ||
 10571050                              (bblock->dfnum != p2e->bbinfo.arr[i]->idom)))
 10581051                             BITSET(bblock->df, i);
 10591052                 }
 10601053         }
 10611054 }
 10621055 
 10631056 void printDF(struct p2env *p2e)
 10641057 {
 10651058         struct basicblock *bb;
 10661059         int i;
 10671060 
 10681061         printf("Dominance frontiers:\n");
 10691062    
 10701063         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 10711064                 printf("bb %d : ", bb->dfnum);
 10721065         
 10731066                 for (i=1; i < p2e->bbinfo.size;i++) {
 10741067                         if (TESTBIT(bb->df,i)) {
 10751068                                 printf("%d ",i);
 10761069                         }
 10771070                 }
 10781071            
 10791072                 printf("\n");
 10801073         }
 10811074    
 10821075 }
 10831076 
 10841077 
 10851078 
 10861079 static struct basicblock *currbb;
 10871080 
 10881081 /* Helper function for findTemps, Find assignment nodes. */
 10891082 static void
 10901083 searchasg(NODE *p, void *arg)
 10911084 {
 10921085         struct pvarinfo *pv;
 10931086         int tempnr;
 10941087         struct varstack *stacke;
 10951088    
 10961089         if (p->n_op != ASSIGN)
 10971090                 return;
 10981091 
 10991092         if (p->n_left->n_op != TEMP)
 11001093                 return;
 11011094 
 11021095         tempnr=regno(p->n_left)-defsites.low;
 11031096    
 11041097         BITSET(currbb->Aorig, tempnr);
 11051098         
 11061099         pv = tmpcalloc(sizeof(struct pvarinfo));
 11071100         pv->next = defsites.arr[tempnr];
 11081101         pv->bb = currbb;
 11091102         pv->n_type = p->n_left->n_type;
 11101103         
 11111104         defsites.arr[tempnr] = pv;
 11121105         
 11131106         
 11141107         if (SLIST_FIRST(&defsites.stack[tempnr])==NULL) {
 11151108                 stacke=tmpcalloc(sizeof (struct varstack));
 11161109                 stacke->tmpregno=0;
 11171110                 SLIST_INSERT_FIRST(&defsites.stack[tempnr],stacke,varstackelem);
 11181111         }
 11191112 }
 11201113 
 11211114 /* Walk the interpass looking for assignment nodes. */
 11221115 void findTemps(struct interpass *ip)
 11231116 {
 11241117         if (ip->type != IP_NODE)
 11251118                 return;
 11261119 
 11271120         walkf(ip->ip_node, searchasg, 0);
 11281121 }
 11291122 
 11301123 /*
 11311124  * Algorithm 19.6 from Appel.
 11321125  */
 11331126 
 11341127 void
 11351128 placePhiFunctions(struct p2env *p2e)
 11361129 {
 11371130         struct basicblock *bb;
 11381131         struct basicblock *y;
 11391132         struct interpass *ip;
 11401133         int maxtmp, i, j, k;
 11411134         struct pvarinfo *n;
 11421135         struct cfgnode *cnode;
 11431136         TWORD ntype;
 11441137         struct pvarinfo *pv;
 11451138         struct phiinfo *phi;
 11461139         int phifound;
 11471140 
 11481141         bb = DLIST_NEXT(&p2e->bblocks, bbelem);
 11491142         defsites.low = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
 11501143         bb = DLIST_PREV(&p2e->bblocks, bbelem);
 11511144         maxtmp = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
 11521145         defsites.size = maxtmp - defsites.low + 1;
 11531146         defsites.arr = tmpcalloc(defsites.size*sizeof(struct pvarinfo *));
 11541147         defsites.stack = tmpcalloc(defsites.size*sizeof(SLIST_HEAD(, varstack)));
 11551148         
 11561149         for (i=0;i<defsites.size;i++)
 11571150                 SLIST_INIT(&defsites.stack[i]); 
 11581151         
 11591152         /* Find all defsites */
 11601153         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 11611154                 currbb = bb;
 11621155                 ip = bb->first;
 11631156                 bb->Aorig = setalloc(defsites.size);
 11641157                 bb->Aphi = setalloc(defsites.size);
 11651158                 
 11661159                 while (ip != bb->last) {
 11671160                         findTemps(ip);
 11681161                         ip = DLIST_NEXT(ip, qelem);
 11691162                 }
 11701163                 /* Make sure we get the last statement in the bblock */
 11711164                 findTemps(ip);
 11721165         }
 11731166 
 11741167         /* For each variable */
 11751168         for (i = 0; i < defsites.size; i++) {
 11761169                 /* While W not empty */
 11771170                 while (defsites.arr[i] != NULL) {
 11781171                         /* Remove some node n from W */
 11791172                         n = defsites.arr[i];
 11801173                         defsites.arr[i] = n->next;
 11811174                         /* For each y in n->bb->df */
 11821175                         for (j = 0; j < p2e->bbinfo.size; j++) {
 11831176                                 if (!TESTBIT(n->bb->df, j))
 11841177                                         continue;
 11851178                                 
 11861179                                 if (TESTBIT(p2e->bbinfo.arr[j]->Aphi, i))
 11871180                                         continue;
 11881181 
 11891182                                 y=p2e->bbinfo.arr[j];
 11901183                                 ntype = n->n_type;
 11911184                                 k = 0;
 11921185                                 /* Amount of predecessors for y */
 11931186                                 SLIST_FOREACH(cnode, &y->parents, cfgelem)
 11941187                                         k++;
 11951188                                 /* Construct phi(...)
 11961189                                 */
 11971190                            
 11981191                                 phifound=0;
 11991192                            
 12001193                                 SLIST_FOREACH(phi, &y->phi, phielem) {
 12011194                                     if (phi->tmpregno==i+defsites.low)
 12021195                                         phifound++;
 12031196                                 }
 12041197                            
 12051198                                 if (phifound==0) {
 12061199                                         if (b2debug)
 12071200                                             printf("Phi in %d(%d) (%p) for %d\n",
 12081201                                             y->dfnum,y->bbnum,y,i+defsites.low);
 12091202 
 12101203                                         /* If no live in, no phi node needed */
 12111204                                         if (!TESTBIT(y->in,
 12121205                                             (i+defsites.low-p2e->ipp->ip_tmpnum+MAXREGS))) {
 12131206                                         if (b2debug)
 12141207                                         printf("tmp %d bb %d unused, no phi\n",
 12151208                                             i+defsites.low, y->bbnum);
 12161209                                                 /* No live in */
 12171210                                                 BITSET(p2e->bbinfo.arr[j]->Aphi, i);
 12181211                                                 continue;
 12191212                                         }
 12201213 
 12211214                                         phi = tmpcalloc(sizeof(struct phiinfo));
 12221215                            
 12231216                                         phi->tmpregno=i+defsites.low;
 12241217                                         phi->size=k;
 12251218                                         phi->n_type=ntype;
 12261219                                         phi->intmpregno=tmpcalloc(k*sizeof(int));
 12271220                            
 12281221                                         SLIST_INSERT_LAST(&y->phi,phi,phielem);
 12291222                                 } else {
 12301223                                     if (b2debug)
 12311224                                         printf("Phi already in %d for %d\n",y->dfnum,i+defsites.low);
 12321225                                 }
 12331226 
 12341227                                 BITSET(p2e->bbinfo.arr[j]->Aphi, i);
 12351228                                 if (!TESTBIT(p2e->bbinfo.arr[j]->Aorig, i)) {
 12361229                                         pv = tmpalloc(sizeof(struct pvarinfo));
 12371230                                         pv->bb = y;
 12381231                                         pv->n_type=ntype;
 12391232                                         pv->next = defsites.arr[i];
 12401233                                         defsites.arr[i] = pv;
 12411234                                 }
 12421235                         }
 12431236                 }
 12441237         }
 12451238 }
 12461239 
 12471240 /* Helper function for renamevar. */
 12481241 static void
 12491242 renamevarhelper(struct p2env *p2e,NODE *t,void *poplistarg)
 12501243 {       
 12511244         SLIST_HEAD(, varstack) *poplist=poplistarg;
 12521245         int opty;
 12531246         int tempnr;
 12541247         int newtempnr;
 12551248         int x;
 12561249         struct varstack *stacke;
 12571250         
 12581251         if (t->n_op == ASSIGN && t->n_left->n_op == TEMP) {
 12591252                 renamevarhelper(p2e,t->n_right,poplist);
 12601253                                 
 12611254                 tempnr=regno(t->n_left)-defsites.low;
 12621255                 
 12631256                 newtempnr=p2e->epp->ip_tmpnum++;
 12641257                 regno(t->n_left)=newtempnr;
 12651258                 
 12661259                 stacke=tmpcalloc(sizeof (struct varstack));
 12671260                 stacke->tmpregno=newtempnr;
 12681261                 SLIST_INSERT_FIRST(&defsites.stack[tempnr],stacke,varstackelem);
 12691262                 
 12701263                 stacke=tmpcalloc(sizeof (struct varstack));
 12711264                 stacke->tmpregno=tempnr;
 12721265                 SLIST_INSERT_FIRST(poplist,stacke,varstackelem);
 12731266         } else {
 12741267                 if (t->n_op == TEMP) {
 12751268                         tempnr=regno(t)-defsites.low;
 12761269                 
 12771270                         if (SLIST_FIRST(&defsites.stack[tempnr])!=NULL) {
 12781271                                 x=SLIST_FIRST(&defsites.stack[tempnr])->tmpregno;
 12791272                                 regno(t)=x;
 12801273                         }
 12811274                 }
 12821275                 
 12831276                 opty = optype(t->n_op);
 12841277                 
 12851278                 if (opty != LTYPE)
 12861279                         renamevarhelper(p2e, t->n_left,poplist);
 12871280                 if (opty == BITYPE)
 12881281                         renamevarhelper(p2e, t->n_right,poplist);
 12891282         }
 12901283 }
 12911284 
 12921285 
 12931286 void
 12941287 renamevar(struct p2env *p2e,struct basicblock *bb)
 12951288 {
 12961289         struct interpass *ip;
 12971290         int h,j;
 12981291         SLIST_HEAD(, varstack) poplist;
 12991292         struct varstack *stacke;
 13001293         struct cfgnode *cfgn2, *cn;
 13011294         int tmpregno,newtmpregno;
 13021295         struct phiinfo *phi;
 13031296 
 13041297         SLIST_INIT(&poplist);
 13051298 
 13061299         SLIST_FOREACH(phi,&bb->phi,phielem) {
 13071300                 tmpregno=phi->tmpregno-defsites.low;
 13081301                 
 13091302                 newtmpregno=p2e->epp->ip_tmpnum++;
 13101303                 phi->newtmpregno=newtmpregno;
 13111304 
 13121305                 stacke=tmpcalloc(sizeof (struct varstack));
 13131306                 stacke->tmpregno=newtmpregno;
 13141307                 SLIST_INSERT_FIRST(&defsites.stack[tmpregno],stacke,varstackelem);
 13151308                 
 13161309                 stacke=tmpcalloc(sizeof (struct varstack));
 13171310                 stacke->tmpregno=tmpregno;
 13181311                 SLIST_INSERT_FIRST(&poplist,stacke,varstackelem);               
 13191312         }
 13201313 
 13211314 
 13221315         ip=bb->first;
 13231316 
 13241317         while (1) {             
 13251318                 if ( ip->type == IP_NODE) {
 13261319                         renamevarhelper(p2e,ip->ip_node,&poplist);
 13271320                 }
 13281321 
 13291322                 if (ip==bb->last)
 13301323                         break;
 13311324 
 13321325                 ip = DLIST_NEXT(ip, qelem);
 13331326         }
 13341327 
 13351328         SLIST_FOREACH(cn, &bb->child, chld) {
 13361329                 j=0;
 13371330 
 13381331                 SLIST_FOREACH(cfgn2, &cn->bblock->parents, cfgelem) {
 13391332                         if (cfgn2->bblock->dfnum==bb->dfnum)
 13401333                                 break;
 13411334                         
 13421335                         j++;
 13431336                 }
 13441337 
 13451338                 SLIST_FOREACH(phi,&cn->bblock->phi,phielem) {
 13461339                         phi->intmpregno[j]=SLIST_FIRST(&defsites.stack[phi->tmpregno-defsites.low])->tmpregno;
 13471340                 }
 13481341         }
 13491342 
 13501343         for (h = 1; h < p2e->bbinfo.size; h++) {
 13511344                 if (!TESTBIT(bb->dfchildren, h))
 13521345                         continue;
 13531346 
 13541347                 renamevar(p2e,p2e->bbinfo.arr[h]);
 13551348         }
 13561349 
 13571350         SLIST_FOREACH(stacke,&poplist,varstackelem) {
 13581351                 tmpregno=stacke->tmpregno;
 13591352                 
 13601353                 defsites.stack[tmpregno].q_forw=defsites.stack[tmpregno].q_forw->varstackelem.q_forw;
 13611354         }
 13621355 }
 13631356 
 13641357 enum pred_type {
 13651358     pred_unknown    = 0,
 13661359     pred_goto       = 1,
 13671360     pred_cond       = 2,
 13681361     pred_falltrough = 3,
 13691362 } ;
 13701363 
 13711364 void
 13721365 removephi(struct p2env *p2e)
 13731366 {
 13741367         struct basicblock *bb,*bbparent;
 13751368         struct cfgnode *cfgn;
 13761369         struct phiinfo *phi;
 13771370         int i;
 13781371         struct interpass *ip;
 13791372         struct interpass *pip;
 13801373         TWORD n_type;
 13811374 
 13821375         enum pred_type complex = pred_unknown ;
 13831376 
 13841377         int label=0;
 13851378         int newlabel;
 13861379 
 13871380         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {              
 13881381                 SLIST_FOREACH(phi,&bb->phi,phielem) {
 13891382                         /* Look at only one, notice break at end */
 13901383                         i=0;
 13911384                         
 13921385                         SLIST_FOREACH(cfgn, &bb->parents, cfgelem) {
 13931386                                 bbparent=cfgn->bblock;
 13941387                                 
 13951388                                 pip=bbparent->last;
 13961389                                 
 13971390                                 complex = pred_unknown ;
 13981391                                 
 13991392                                 BDEBUG(("removephi: %p in %d",pip,bb->dfnum));
 14001393 
 14011394                                 if (pip->type == IP_NODE && pip->ip_node->n_op == GOTO) {
 14021395                                         BDEBUG((" GOTO "));
 14031396                                         label = (int)pip->ip_node->n_left->n_lval;
 14041397                                         complex = pred_goto ;
 14051398                                 } else if (pip->type == IP_NODE && pip->ip_node->n_op == CBRANCH) {
 14061399                                         BDEBUG((" CBRANCH "));
 14071400                                         label = (int)pip->ip_node->n_right->n_lval;
 14081401                                         
 14091402                                         if (bb==p2e->labinfo.arr[label - p2e->ipp->ip_lblnum])
 14101403                                                 complex = pred_cond ;
 14111404                                         else
 14121405                                                 complex = pred_falltrough ;
 14131406 
 14141407                                 } else if (DLIST_PREV(bb, bbelem) == bbparent) {
 14151408                                         complex = pred_falltrough ;
 14161409                                 } else {
 14171410                                             /* PANIC */
 14181411                                         comperr("Assumption blown in rem-phi") ;
 14191412                                 }
 14201413       
 14211414                                 BDEBUG((" Complex: %d ",complex)) ;
 14221415 
 14231416                                 switch (complex) {
 14241417                                   case pred_goto:
 14251418                                         /* gotos can only go to this place. No bounce tab needed */
 14261419                                         SLIST_FOREACH(phi,&bb->phi,phielem) {
 14271420                                                 if (phi->intmpregno[i]>0) {
 14281421                                                         n_type=phi->n_type;
 14291422                                                         ip = ipnode(mkbinode(ASSIGN,
 14301423                                                              mktemp(phi->newtmpregno, n_type),
 14311424                                                              mktemp(phi->intmpregno[i],n_type),
 14321425                                                              n_type));
 14331426                                                         BDEBUG(("(%p, %d -> %d) ", ip, phi->intmpregno[i], phi->newtmpregno));
 14341427                                 
 14351428                                                         DLIST_INSERT_BEFORE((bbparent->last), ip, qelem);
 14361429                                                 }
 14371430                                         }
 14381431                                         break ;
 14391432                                   case pred_cond:
 14401433                                         /* Here, we need a jump pad */
 14411434                                         newlabel=getlab2();
 14421435                         
 14431436                                         ip = tmpalloc(sizeof(struct interpass));
 14441437                                         ip->type = IP_DEFLAB;
 14451438                                         /* Line number?? ip->lineno; */
 14461439                                         ip->ip_lbl = newlabel;
 14471440                                         DLIST_INSERT_BEFORE((bb->first), ip, qelem);
 14481441 
 14491442                                         SLIST_FOREACH(phi,&bb->phi,phielem) {
 14501443                                                 if (phi->intmpregno[i]>0) {
 14511444                                                         n_type=phi->n_type;
 14521445                                                         ip = ipnode(mkbinode(ASSIGN,
 14531446                                                              mktemp(phi->newtmpregno, n_type),
 14541447                                                              mktemp(phi->intmpregno[i],n_type),
 14551448                                                              n_type));
 14561449 
 14571450                                                         BDEBUG(("(%p, %d -> %d) ", ip, phi->intmpregno[i], phi->newtmpregno));
 14581451                                                         DLIST_INSERT_BEFORE((bb->first), ip, qelem);
 14591452                                                 }
 14601453                                         }
 14611454                                         /* add a jump to us */
 14621455                                         ip = ipnode(mkunode(GOTO, mklnode(ICON, label, 0, INT), 0, INT));
 14631456                                         DLIST_INSERT_BEFORE((bb->first), ip, qelem);
 14641457                                         pip->ip_node->n_right->n_lval=newlabel;
 14651458                                         if (!logop(pip->ip_node->n_left->n_op))
 14661459                                                 comperr("SSA not logop");
 14671460                                         pip->ip_node->n_left->n_label=newlabel;
 14681461                                         break ;
 14691462                                   case pred_falltrough:
 14701463                                         if (bb->first->type == IP_DEFLAB) {
 14711464                                                 label = bb->first->ip_lbl;
 14721465                                                 BDEBUG(("falltrough label %d\n", label));
 14731466                                         } else {
 14741467                                                 comperr("BBlock has no label?") ;
 14751468                                         }
 14761469 
 14771470                                         /*
 14781471                                          * add a jump to us. We _will_ be, or already have, added code in between.
 14791472                                          * The code is created in the wrong order and switched at the insert, thus
 14801473                                          * comming out correctly
 14811474                                          */
 14821475 
 14831476                                         ip = ipnode(mkunode(GOTO, mklnode(ICON, label, 0, INT), 0, INT));
 14841477                                         DLIST_INSERT_AFTER((bbparent->last), ip, qelem);
 14851478 
 14861479                                         /* Add the code to the end, add a jump to us. */
 14871480                                         SLIST_FOREACH(phi,&bb->phi,phielem) {
 14881481                                                 if (phi->intmpregno[i]>0) {
 14891482                                                         n_type=phi->n_type;
 14901483                                                         ip = ipnode(mkbinode(ASSIGN,
 14911484                                                                 mktemp(phi->newtmpregno, n_type),
 14921485                                                                 mktemp(phi->intmpregno[i],n_type),
 14931486                                                                 n_type));
 14941487 
 14951488                                                         BDEBUG(("(%p, %d -> %d) ", ip, phi->intmpregno[i], phi->newtmpregno));
 14961489                                                         DLIST_INSERT_AFTER((bbparent->last), ip, qelem);
 14971490                                                 }
 14981491                                         }
 14991492                                         break ;
 15001493                                 default:
 15011494                                         comperr("assumption blown, complex is %d\n", complex) ;
 15021495                                 }
 15031496                                 BDEBUG(("\n"));
 15041497                                 i++;
 15051498                         }
 15061499                         break;
 15071500                 }
 15081501         }
 15091502 }
 15101503 
 15111504    
 15121505 /*
 15131506  * Remove unreachable nodes in the CFG.
 15141507  */
 15151508 
 15161509 void
 15171510 remunreach(struct p2env *p2e)
 15181511 {
 15191512         struct basicblock *bb, *nbb;
 15201513         struct interpass *next, *ctree;
 15211514 
 15221515         bb = DLIST_NEXT(&p2e->bblocks, bbelem);
 15231516         while (bb != &p2e->bblocks) {
 15241517                 nbb = DLIST_NEXT(bb, bbelem);
 15251518 
 15261519                 /* Code with dfnum 0 is unreachable */
 15271520                 if (bb->dfnum != 0) {
 15281521                         bb = nbb;
 15291522                         continue;
 15301523                 }
 15311524 
 15321525                 /* Need the epilogue node for other parts of the
 15331526                    compiler, set its label to 0 and backend will
 15341527                    handle it. */
 15351528                 if (bb->first->type == IP_EPILOG) {
 15361529                         bb->first->ip_lbl = 0;
 15371530                         bb = nbb;
 15381531                         continue;
 15391532                 }
 15401533 
 15411534                 next = bb->first;
 15421535                 do {
 15431536                         ctree = next;
 15441537                         next = DLIST_NEXT(ctree, qelem);
 15451538                         
 15461539                         if (ctree->type == IP_NODE)
 15471540                                 tfree(ctree->ip_node);
 15481541                         DLIST_REMOVE(ctree, qelem);
 15491542                 } while (ctree != bb->last);
 15501543                         
 15511544                 DLIST_REMOVE(bb, bbelem);
 15521545                 bb = nbb;
 15531546         }
 15541547 }
 15551548 
 15561549 static void
 15571550 printip2(struct interpass *ip)
 15581551 {
 15591552         static char *foo[] = {
 15601553            0, "NODE", "PROLOG", "STKOFF", "EPILOG", "DEFLAB", "DEFNAM", "ASM" };
 15611554         struct interpass_prolog *ipplg, *epplg;
 15621555         unsigned i;
 15631556         int *l;
 15641557 
 15651558         if (ip->type > MAXIP)
 15661559                 printf("IP(%d) (%p): ", ip->type, ip);
 15671560         else
 15681561                 printf("%s (%p): ", foo[ip->type], ip);
 15691562         switch (ip->type) {
 15701563         case IP_NODE: printf("\n");
 15711564 #ifdef PCC_DEBUG
 15721565         fwalk(ip->ip_node, e2print, 0); break;
 15731566 #endif
 15741567         case IP_PROLOG:
 15751568                 ipplg = (struct interpass_prolog *)ip;
 15761569                 printf("%s %s regs",
 15771570                     ipplg->ipp_name, ipplg->ipp_vis ? "(local)" : "");
 15781571                 for (i = 0; i < NIPPREGS; i++)
 15791572                         printf("%s0x%lx", i? ":" : " ",
 15801573                             (long) ipplg->ipp_regs[i]);
 15811574                 printf(" autos %d mintemp %d minlbl %d\n",
 15821575                     ipplg->ipp_autos, ipplg->ip_tmpnum, ipplg->ip_lblnum);
 15831576                 break;
 15841577         case IP_EPILOG:
 15851578                 epplg = (struct interpass_prolog *)ip;
 15861579                 printf("%s %s regs",
 15871580                     epplg->ipp_name, epplg->ipp_vis ? "(local)" : "");
 15881581                 for (i = 0; i < NIPPREGS; i++)
 15891582                         printf("%s0x%lx", i? ":" : " ",
 15901583                             (long) epplg->ipp_regs[i]);
 15911584                 printf(" autos %d mintemp %d minlbl %d\ncgoto labels: ",
 15921585                     epplg->ipp_autos, epplg->ip_tmpnum, epplg->ip_lblnum);
 15931586                 for (l = epplg->ip_labels; *l; l++)
 15941587                         printf("%d ", *l);
 15951588                 printf("\n");
 15961589                 break;
 15971590         case IP_DEFLAB: printf(LABFMT "\n", ip->ip_lbl); break;
 15981591         case IP_DEFNAM: printf("\n"); break;
 15991592         case IP_ASM: printf("%s\n", ip->ip_asm); break;
 16001593         default:
 16011594                 break;
 16021595         }
 16031596 }
 16041597 
 16051598 void
 16061599 printip(struct interpass *pole)
 16071600 {
 16081601         struct interpass *ip;
 16091602 
 16101603         DLIST_FOREACH(ip, pole, qelem)
 16111604                 printip2(ip);
 16121605 }
 16131606 
 16141607 #ifdef PCC_DEBUG
 16151608 void flownodeprint(NODE *p,FILE *flowdiagramfile);
 16161609 
 16171610 void
 16181611 flownodeprint(NODE *p,FILE *flowdiagramfile)
 16191612 {       
 16201613         int opty;
 16211614         char *o;
 16221615 
 16231616         fprintf(flowdiagramfile,"{");
 16241617 
 16251618         o=opst[p->n_op];
 16261619         
 16271620         while (*o != 0) {
 16281621                 if (*o=='<' || *o=='>')
 16291622                         fputc('\\',flowdiagramfile);
 16301623                 
 16311624                 fputc(*o,flowdiagramfile);
 16321625                 o++;
 16331626         }
 16341627         
 16351628         
 16361629         switch( p->n_op ) {                     
 16371630                 case REG:
 16381631                         fprintf(flowdiagramfile, " %s", rnames[p->n_rval] );
 16391632                         break;
 16401633                         
 16411634                 case TEMP:
 16421635                         fprintf(flowdiagramfile, " %d", regno(p));
 16431636                         break;
 16441637                         
 16451638                 case XASM:
 16461639                 case XARG:
 16471640                         fprintf(flowdiagramfile, " '%s'", p->n_name);
 16481641                         break;
 16491642                         
 16501643                 case ICON:
 16511644                 case NAME:
 16521645                 case OREG:
 16531646                         fprintf(flowdiagramfile, " " );
 16541647                         adrput(flowdiagramfile, p );
 16551648                         break;
 16561649                         
 16571650                 case STCALL:
 16581651                 case USTCALL:
 16591652                 case STARG:
 16601653                 case STASG:
 16611654                         fprintf(flowdiagramfile, " size=%d", p->n_stsize );
 16621655                         fprintf(flowdiagramfile, " align=%d", p->n_stalign );
 16631656                         break;
 16641657         }
 16651658         
 16661659         opty = optype(p->n_op);
 16671660         
 16681661         if (opty != LTYPE) {
 16691662                 fprintf(flowdiagramfile,"| {");
 16701663         
 16711664                 flownodeprint(p->n_left,flowdiagramfile);
 16721665         
 16731666                 if (opty == BITYPE) {
 16741667                         fprintf(flowdiagramfile,"|");
 16751668                         flownodeprint(p->n_right,flowdiagramfile);
 16761669                 }
 16771670                 fprintf(flowdiagramfile,"}");
 16781671         }
 16791672         
 16801673         fprintf(flowdiagramfile,"}");
 16811674 }
 16821675 
 16831676 void
 16841677 printflowdiagram(struct p2env *p2e, char *type) {
 16851678         struct basicblock *bbb;
 16861679         struct cfgnode *cn;
 16871680         struct interpass *ip;
 16881681         struct interpass_prolog *plg;
 16891682         struct phiinfo *phi;
 16901683         char *name;
 16911684         char *filename;
 16921685         int filenamesize;
 16931686         char *ext=".dot";
 16941687         FILE *flowdiagramfile;
 16951688         
 16961689         if (!g2debug)
 16971690                 return;
 16981691         
 16991692         bbb=DLIST_NEXT(&p2e->bblocks, bbelem);
 17001693         ip=bbb->first;
 17011694 
 17021695         if (ip->type != IP_PROLOG)
 17031696                 return;
 17041697         plg = (struct interpass_prolog *)ip;
 17051698 
 17061699         name=plg->ipp_name;
 17071700         
 17081701         filenamesize=strlen(name)+1+strlen(type)+strlen(ext)+1;
 17091702         filename=tmpalloc(filenamesize);
 17101703         snprintf(filename,filenamesize,"%s-%s%s",name,type,ext);
 17111704         
 17121705         flowdiagramfile=fopen(filename,"w");
 17131706         
 17141707         fprintf(flowdiagramfile,"digraph {\n");
 17151708         fprintf(flowdiagramfile,"rankdir=LR\n");
 17161709         
 17171710         DLIST_FOREACH(bbb, &p2e->bblocks, bbelem) {
 17181711                 ip=bbb->first;
 17191712                 
 17201713                 fprintf(flowdiagramfile,"bb%p [shape=record ",bbb);
 17211714                 
 17221715                 if (ip->type==IP_PROLOG)
 17231716                         fprintf(flowdiagramfile,"root ");
 17241717 
 17251718                 fprintf(flowdiagramfile,"label=\"");
 17261719                 
 17271720                 SLIST_FOREACH(phi,&bbb->phi,phielem) {
 17281721                         fprintf(flowdiagramfile,"Phi %d|",phi->tmpregno);
 17291722                 }               
 17301723                 
 17311724                 
 17321725                 while (1) {
 17331726                         switch (ip->type) {
 17341727                                 case IP_NODE:
 17351728                                         flownodeprint(ip->ip_node,flowdiagramfile);
 17361729                                         break;
 17371730                                         
 17381731                                 case IP_DEFLAB:
 17391732                                         fprintf(flowdiagramfile,"Label: %d", ip->ip_lbl);
 17401733                                         break;
 17411734                                         
 17421735                                 case IP_PROLOG:
 17431736                                         plg = (struct interpass_prolog *)ip;
 17441737         
 17451738                                         fprintf(flowdiagramfile,"%s %s",plg->ipp_name,type);
 17461739                                         break;
 17471740                         }
 17481741                         
 17491742                         fprintf(flowdiagramfile,"|");
 17501743                         fprintf(flowdiagramfile,"|");
 17511744                         
 17521745                         if (ip==bbb->last)
 17531746                                 break;
 17541747                         
 17551748                         ip = DLIST_NEXT(ip, qelem);
 17561749                 }
 17571750                 fprintf(flowdiagramfile,"\"]\n");
 17581751                 
 17591752                 SLIST_FOREACH(cn, &bbb->child, chld) {
 17601753                         char *color="black";
 17611754                         struct interpass *pip=bbb->last;
 17621755 
 17631756                         if (pip->type == IP_NODE && pip->ip_node->n_op == CBRANCH) {
 17641757                                 int label = (int)pip->ip_node->n_right->n_lval;
 17651758                                 
 17661759                                 if (cn->bblock==p2e->labinfo.arr[label - p2e->ipp->ip_lblnum])
 17671760                                         color="red";
 17681761                         }
 17691762                         
 17701763                         fprintf(flowdiagramfile,"bb%p -> bb%p [color=%s]\n", bbb,cn->bblock,color);
 17711764                 }
 17721765         }
 17731766         
 17741767         fprintf(flowdiagramfile,"}\n");
 17751768         fclose(flowdiagramfile);
 17761769 }
 17771770 
 17781771 #endif
 17791772 
 17801773 /* walk all the programm */
 17811774 void WalkAll(struct p2env* p2e, void (*f) (NODE*, void*), void* arg, int type)
 17821775 {
 17831776         struct interpass *ipole = &p2e->ipole;
 17841777         struct interpass *ip ;
 17851778         if (0 != type) {
 17861779                 DLIST_FOREACH(ip, ipole, qelem) {
 17871780                         if (ip->type == IP_NODE && ip->ip_node->n_op == type)
 17881781                                 walkf(ip->ip_node, f, arg) ;
 17891782                 }
 17901783         } else {
 17911784                 DLIST_FOREACH(ip, ipole, qelem) {
 17921785                         if (ip->type == IP_NODE)
 17931786                                 walkf(ip->ip_node, f, arg) ;
 17941787                 }
 17951788         }
 17961789 }
 17971790 #if 0
 17981791 static int is_goto_label(struct interpass*g, struct interpass* l)
 17991792 {
 18001793         if (!g || !l)
 18011794                 return 0 ;
 18021795         if (g->type != IP_NODE) return 0 ;
 18031796         if (l->type != IP_DEFLAB) return 0 ;
 18041797         if (g->ip_node->n_op != GOTO) return 0 ;
 18051798         if (g->ip_node->n_left->n_lval != l->ip_lbl) return 0 ;
 18061799         return 1 ;
 18071800 }
 18081801 #endif
 18091802 
 18101803 /*
 18111804  * iterate over the basic blocks.
 18121805  * In case a block has only one successor and that one has only one pred, and the link is a goto:
 18131806  * place the second one immediately behind the first one (in terms of nodes, means cut&resplice).
 18141807  * This should take care of a lot of jumps.
 18151808  * one problem: Cannot move the first or last basic block (prolog/epilog). This is taken care of by
 18161809  * moving block #1 to #2, not #2 to #1
 18171810  * More complex (on the back cooker;) : first coalesc the inner loops (L1 cache), then go from inside out.
 18181811  */
 18191812 
 18201813 static unsigned long count_blocks(struct p2env* p2e)
 18211814 {
 18221815         struct basicblock* bb ;
 18231816         unsigned long count = 0 ;
 18241817         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 18251818                 ++count ;
 18261819         }
 18271820         return count ;
 18281821 }
 18291822 
 18301823 struct block_map {
 18311824         struct basicblock* block ;
 18321825         unsigned long index ;
 18331826         unsigned long thread ;
 18341827 } ;
 18351828 
 18361829 static unsigned long map_blocks(struct p2env* p2e, struct block_map* map, unsigned long count)
 18371830 {
 18381831         struct basicblock* bb ;
 18391832         unsigned long indx = 0 ;
 18401833         int ignore = 2 ;
 18411834         unsigned long thread ;
 18421835         unsigned long changes ;
 18431836 
 18441837         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 18451838                 map[indx].block = bb ;
 18461839                 map[indx].index = indx ;
 18471840 
 18481841                 /* ignore the first 2 labels, maybe up to 3 BBs */
 18491842                 if (ignore) {
 18501843                         if (bb->first->type == IP_DEFLAB)
 18511844                                 --ignore;
 18521845 
 18531846                         map[indx].thread = 1 ;  /* these are "fixed" */
 18541847                 } else
 18551848                         map[indx].thread = 0 ;
 18561849 
 18571850                 indx++ ;
 18581851         }
 18591852 
 18601853         thread = 1 ;
 18611854         do {
 18621855                 changes = 0 ;
 18631856                 
 18641857                 for (indx=0; indx < count; indx++) {
 18651858                         /* find block without trace */
 18661859                         if (map[indx].thread == 0) {
 18671860                                 /* do new thread */
 18681861                                 struct cfgnode *cn ;
 18691862                                 struct basicblock *block2 = 0;
 18701863                                 unsigned long i ;
 18711864                                 unsigned long added ;
 18721865                                 
 18731866                                 BDEBUG (("new thread %ld at block %ld\n", thread, indx)) ;
 18741867 
 18751868                                 bb = map[indx].block ;
 18761869                                 do {
 18771870                                         added = 0 ;
 18781871 
 18791872                                         for (i=0; i < count; i++) {
 18801873                                                 if (map[i].block == bb && map[i].thread == 0) {
 18811874                                                         map[i].thread = thread ;
 18821875 
 18831876                                                         BDEBUG(("adding block %ld to trace %ld\n", i, thread)) ;
 18841877 
 18851878                                                         changes ++ ;
 18861879                                                         added++ ;
 18871880 
 18881881                                                         /*
 18891882                                                          * pick one from followers. For now (simple), pick the
 18901883                                                          * one who is directly following us. If none of that exists,
 18911884                                                          * this code picks the last one.
 18921885                                                          */
 18931886 
 18941887                                                         SLIST_FOREACH(cn, &bb->child, chld) {
 18951888                                                                 block2=cn->bblock ;
 18961889 #if 1
 18971890                                                                 if (i+1 < count && map[i+1].block == block2)
 18981891                                                                         break ; /* pick that one */
 18991892 #else
 19001893                                                                 if (block2) break ;
 19011894 #endif
 19021895                                                         }
 19031896 
 19041897                                                         if (block2)
 19051898                                                                 bb = block2 ;
 19061899                                                 }
 19071900                                         }
 19081901                                 } while (added) ;
 19091902                                 thread++ ;
 19101903                         }
 19111904                 }
 19121905         } while (changes);
 19131906 
 19141907         /* Last block is also a thread on it's own, and the highest one. */
 19151908 /*
 19161909         thread++ ;
 19171910         map[count-1].thread = thread ;
 19181911 */
 19191912         if (b2debug) {
 19201913                 printf("Threads\n");
 19211914                 for (indx=0; indx < count; indx++) {
 19221915                         printf("Block #%ld (lbl %d) Thread %ld\n", indx, map[indx].block->first->ip_lbl, map[indx].thread);
 19231916                 }
 19241917         }
 19251918         return thread ;
 19261919 }
 19271920 
 19281921 
 19291922 void TraceSchedule(struct p2env* p2e)
 19301923 {
 19311924         struct block_map* map ;
 19321925         unsigned long block_count = count_blocks(p2e);
 19331926         unsigned long i ;
 19341927         unsigned long threads;
 19351928         struct interpass *front, *back ;
 19361929 
 19371930         map = tmpalloc(block_count * sizeof(struct block_map));
 19381931 
 19391932         threads = map_blocks(p2e, map, block_count) ;
 19401933 
 19411934         back = map[0].block->last ;
 19421935         for (i=1; i < block_count; i++) {
 19431936                 /* collect the trace */
 19441937                 unsigned long j ;
 19451938                 unsigned long thread = map[i].thread ;
 19461939                 if (thread) {
 19471940                         BDEBUG(("Thread %ld\n", thread)) ;
 19481941                         for (j=i; j < block_count; j++) {
 19491942                                 if (map[j].thread == thread) {
 19501943                                         front = map[j].block->first ;
 19511944 
 19521945                                         BDEBUG(("Trace %ld, old BB %ld, next BB %ld\t",
 19531946                                                 thread, i, j)) ;
 19541947                                         BDEBUG(("Label %d\n", front->ip_lbl)) ;
 19551948                                         DLIST_NEXT(back, qelem) = front ;
 19561949                                         DLIST_PREV(front, qelem) = back ;
 19571950                                         map[j].thread = 0 ;     /* done */
 19581951                                         back = map[j].block->last ;
 19591952                                         DLIST_NEXT(back, qelem) = 0 ;
 19601953                                 }
 19611954                         }
 19621955                 }
 19631956         }
 19641957         DLIST_NEXT(back, qelem) = &(p2e->ipole) ;
 19651958         DLIST_PREV(&p2e->ipole, qelem) = back ;
 19661959 }
 19671960 
 19681961 static void add_labels(struct p2env* p2e)
 19691962 {
 19701963         struct interpass *ipole = &p2e->ipole ;
 19711964         struct interpass *ip ;
 19721965 
 19731966         DLIST_FOREACH(ip, ipole, qelem) {
 19741967                 if (ip->type == IP_NODE && ip->ip_node->n_op == CBRANCH) {
 19751968                         struct interpass *n = DLIST_NEXT(ip, qelem);
 19761969                         if (n && n->type != IP_DEFLAB) {
 19771970                                 struct interpass* lab;
 19781971                                 int newlabel=getlab2() ;
 19791972 
 19801973                                 BDEBUG(("add_label L%d\n", newlabel));
 19811974 
 19821975                                 lab = tmpalloc(sizeof(struct interpass));
 19831976                                 lab->type = IP_DEFLAB;
 19841977                                 /* Line number?? ip->lineno; */
 19851978                                 lab->ip_lbl = newlabel;
 19861979                                 DLIST_INSERT_AFTER(ip, lab, qelem);
 19871980                         }
 19881981                 }
 19891982         }
 19901983 }
 19911984 
 19921985 /* node map */
 19931986 #ifdef ENABLE_NEW
 19941987 struct node_map {
 19951988         NODE* node ;            /* the node */
 19961989         unsigned int node_num ; /* node is equal to that one */
 19971990         unsigned int var_num ;  /* node computes this variable */
 19981991 } ;
 19991992 
 20001993 static unsigned long nodes_counter ;
 20011994 static void node_map_count_walker(NODE* n, void* x)
 20021995 {
 20031996         nodes_counter ++ ;
 20041997 }
 20051998 
 20061999 static void do_cse(struct p2env* p2e)
 20072000 {
 20082001         nodes_counter = 0 ;
 20092002         WalkAll(p2e, node_map_count_walker, 0, 0) ;
 20102003         BDEBUG(("Found %ld nodes\n", nodes_counter)) ;
 20112004 }
 20122005 #endif
 20132006 
 20142007 #define BITALLOC(ptr,all,sz) { \
 20152008         int sz__s = BIT2BYTE(sz); ptr = all(sz__s); memset(ptr, 0, sz__s); }
 20162009 #define VALIDREG(p)     (p->n_op == REG && TESTBIT(validregs, regno(p)))
 20172010 #define XCHECK(x) if (x < 0 || x >= xbits) printf("x out of range %d\n", x)
 20182011 #define RUP(x) (((x)+NUMBITS-1)/NUMBITS)
 20192012 #define SETCOPY(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] = f[i]
 20202013 #define SETSET(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] |= f[i]
 20212014 #define SETCLEAR(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] &= ~f[i]
 20222015 #define SETCMP(v,t,f,i,n) for (i = 0; i < RUP(n); i++) \
 20232016         if (t[i] != f[i]) v = 1
 20242017 
 20252018 static int xxx, xbits;
 20262019 /*
 20272020  * Set/clear long term liveness for regs and temps.
 20282021  */
 20292022 static void
 20302023 unionize(NODE *p, struct basicblock *bb, int suboff)
 20312024 {
 20322025         int o, ty;
 20332026 
 20342027         if ((o = p->n_op) == TEMP || VALIDREG(p)) {
 20352028                 int b = regno(p);
 20362029                 if (o == TEMP)
 20372030                         b = b - suboff + MAXREGS;
 20382031 XCHECK(b);
 20392032                 BITSET(bb->gen, b);
 20402033         }
 20412034         if (asgop(o)) {
 20422035                 if (p->n_left->n_op == TEMP || VALIDREG(p)) {
 20432036                         int b = regno(p->n_left);
 20442037                         if (p->n_left->n_op == TEMP)
 20452038                                 b = b - suboff + MAXREGS;
 20462039 XCHECK(b);
 20472040                         BITCLEAR(bb->gen, b);
 20482041                         BITSET(bb->killed, b);
 20492042                         unionize(p->n_right, bb, suboff);
 20502043                         return;
 20512044                 }
 20522045         }
 20532046         ty = optype(o);
 20542047         if (ty != LTYPE)
 20552048                 unionize(p->n_left, bb, suboff);
 20562049         if (ty == BITYPE)
 20572050                 unionize(p->n_right, bb, suboff);
 20582051 }
 20592052 
 20602053 /*
 20612054  * Found an extended assembler node, so growel out gen/killed nodes.
 20622055  */
 20632056 static void
 20642057 xasmionize(NODE *p, void *arg)
 20652058 {
 20662059         struct basicblock *bb = arg;
 20672060         int cw, b;
 20682061 
 20692062         if (p->n_op == ICON && p->n_type == STRTY)
 20702063                 return; /* dummy end marker */
 20712064 
 20722065         cw = xasmcode(p->n_name);
 20732066         if (XASMVAL(cw) == 'n' || XASMVAL(cw) == 'm')
 20742067                 return; /* no flow analysis */
 20752068         p = p->n_left;
 20762069  
 20772070         if (XASMVAL(cw) == 'g' && p->n_op != TEMP && p->n_op != REG)
 20782071                 return; /* no flow analysis */
 20792072 
 20802073         b = regno(p);
 20812074 #if 0
 20822075         if (XASMVAL(cw) == 'r' && p->n_op == TEMP)
 20832076                 addnotspill(b);
 20842077 #endif
 20852078 #define MKTOFF(r)       ((r) - xxx)
 20862079         if (XASMISOUT(cw)) {
 20872080                 if (p->n_op == TEMP) {
 20882081                         BITCLEAR(bb->gen, MKTOFF(b));
 20892082                         BITSET(bb->killed, MKTOFF(b));
 20902083                 } else if (p->n_op == REG) {
 20912084                         BITCLEAR(bb->gen, b);
 20922085                         BITSET(bb->killed, b);  
 20932086                 } else
 20942087                         uerror("bad xasm node type %d", p->n_op);
 20952088         }
 20962089         if (XASMISINP(cw)) {
 20972090                 if (p->n_op == TEMP) {
 20982091                         BITSET(bb->gen, MKTOFF(b));
 20992092                 } else if (p->n_op == REG) {
 21002093                         BITSET(bb->gen, b);
 21012094                 } else if (optype(p->n_op) != LTYPE) {
 21022095                         if (XASMVAL(cw) == 'r')
 21032096                                 uerror("couldn't find available register");
 21042097                         else
 21052098                                 uerror("bad xasm node type2");
 21062099                 }
 21072100         }
 21082101 }
 21092102 
 21102103 /*
 21112104  * Do variable liveness analysis.  Only analyze the long-lived
 21122105  * variables, and save the live-on-exit temporaries in a bit-field
 21132106  * at the end of each basic block. This bit-field is later used
 21142107  * when doing short-range liveness analysis in Build().
 21152108  */
 21162109 void
 21172110 liveanal(struct p2env *p2e)
 21182111 {
 21192112         struct basicblock *bb;
 21202113         struct interpass *ip;
 21212114         bittype *saved;
 21222115         int mintemp, again;
 21232116 
 21242117         xbits = p2e->epp->ip_tmpnum - p2e->ipp->ip_tmpnum + MAXREGS;
 21252118         mintemp = p2e->ipp->ip_tmpnum;
 21262119 
 21272120         /* Just fetch space for the temporaries from heap */
 21282121         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 21292122                 BITALLOC(bb->gen,tmpalloc,xbits);
 21302123                 BITALLOC(bb->killed,tmpalloc,xbits);
 21312124                 BITALLOC(bb->in,tmpalloc,xbits);
 21322125                 BITALLOC(bb->out,tmpalloc,xbits);
 21332126         }
 21342127         BITALLOC(saved,tmpalloc,xbits);
 21352128 
 21362129         xxx = mintemp;
 21372130         /*
 21382131          * generate the gen-killed sets for all basic blocks.
 21392132          */
 21402133         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 21412134                 for (ip = bb->last; ; ip = DLIST_PREV(ip, qelem)) {
 21422135                         /* gen/killed is 'p', this node is 'n' */
 21432136                         if (ip->type == IP_NODE) {
 21442137                                 if (ip->ip_node->n_op == XASM)
 21452138                                         flist(ip->ip_node->n_left,
 21462139                                             xasmionize, bb);
 21472140                                 else
 21482141                                         unionize(ip->ip_node, bb, mintemp);
 21492142                         }
 21502143                         if (ip == bb->first)
 21512144                                 break;
 21522145                 }
 21532146                 memcpy(bb->in, bb->gen, BIT2BYTE(xbits));
 21542147 #ifdef PCC_DEBUG
 21552148 #define PRTRG(x) printf("%d ", x < MAXREGS ? x : x + p2e->ipp->ip_tmpnum-MAXREGS)
 21562149                 if (b2debug > 1) {
 21572150                         int i;
 21582151 
 21592152                         printf("basic block %d\ngen: ", bb->bbnum);
 21602153                         for (i = 0; i < xbits; i++)
 21612154                                 if (TESTBIT(bb->gen, i))
 21622155                                         PRTRG(i);
 21632156                         printf("\nkilled: ");
 21642157                         for (i = 0; i < xbits; i++)
 21652158                                 if (TESTBIT(bb->killed, i))
 21662159                                         PRTRG(i);
 21672160                         printf("\n");
 21682161                 }
 21692162 #endif
 21702163         }
 21712164         /* do liveness analysis on basic block level */
 21722165         do {
 21732166                 struct cfgnode *cn;
 21742167                 int j;
 21752168 
 21762169                 again = 0;
 21772170                 /* XXX - loop should be in reversed execution-order */
 21782171                 DLIST_FOREACH_REVERSE(bb, &p2e->bblocks, bbelem) {
 21792172                         SETCOPY(saved, bb->out, j, xbits);
 21802173                         SLIST_FOREACH(cn, &bb->child, chld) {
 21812174                                 SETSET(bb->out, cn->bblock->in, j, xbits);
 21822175                         }
 21832176                         SETCMP(again, saved, bb->out, j, xbits);
 21842177                         SETCOPY(saved, bb->in, j, xbits);
 21852178                         SETCOPY(bb->in, bb->out, j, xbits);
 21862179                         SETCLEAR(bb->in, bb->killed, j, xbits);
 21872180                         SETSET(bb->in, bb->gen, j, xbits);
 21882181                         SETCMP(again, saved, bb->in, j, xbits);
 21892182                 }
 21902183         } while (again);
 21912184 
 21922185 #ifdef PCC_DEBUG
 21932186         DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
 21942187                 if (b2debug) {
 21952188                         int i;
 21962189 
 21972190                         printf("all basic block %d\nin: ", bb->bbnum);
 21982191                         for (i = 0; i < xbits; i++)
 21992192                                 if (TESTBIT(bb->in, i))
 22002193                                         PRTRG(i);
 22012194                         printf("\nout: ");
 22022195                         for (i = 0; i < xbits; i++)
 22032196                                 if (TESTBIT(bb->out, i))
 22042197                                         PRTRG(i);
 22052198                         printf("\n");
 22062199                 }
 22072200         }
 22082201 #endif
 22092202 }
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-08-21 04:22 +0200