Quick Search:

Mode

Context

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

Other Diffs

Ignore

Blank Lines Whitespace: Expand:

Diff

1.42
 
1.43
 
MAIN:ragge:20060604132605
 
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 static int dfsnum;
 4545 
 4646 void saveip(struct interpass *ip);
 4747 void deljumps(struct interpass *);
 4848 void optdump(struct interpass *ip);
 4949 void printip(struct interpass *pole);
 5050 
 5151 static struct varinfo defsites;
 5252 struct interpass *storesave;
 5353 static struct interpass_prolog *ipp, *epp; /* prolog/epilog */
 5454 
 5555 void bblocks_build(struct interpass *, struct labelinfo *, struct bblockinfo *);
 5656 void cfg_build(struct labelinfo *labinfo);
 5757 void cfg_dfs(struct basicblock *bb, unsigned int parent,
 5858              struct bblockinfo *bbinfo);
 5959 void dominators(struct bblockinfo *bbinfo);
 6060 struct basicblock *
 6161 ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo);
 6262 void link(struct basicblock *parent, struct basicblock *child);
 6363 void computeDF(struct basicblock *bblock, struct bblockinfo *bbinfo);
 6464 void findTemps(struct interpass *ip);
 6565 void placePhiFunctions(struct bblockinfo *bbinfo);
 6666 void remunreach(void);
 6767 
 6868 struct basicblock bblocks;
 6969 int nbblocks;
 7070 
 7171 struct addrof {
 7272         struct addrof *next;
 7373         int tempnum;
 7474         int oregoff;
 7575 } *otlink;
 7676 
 7777 static int
 7878 getoff(int num)
 7979 {
 8080         struct addrof *w;
 8181 
 8282         for (w = otlink; w; w = w->next)
 8383                 if (w->tempnum == num)
 8484                         return w->oregoff;
 8585         return 0;
 8686 }
 8787 
 8888 /*
 8989  * Search for ADDROF elements and, if found, record them.
 9090  */
 9191 static void
 9292 findaddrof(NODE *p)
 9393 {
 9494         struct addrof *w;
 9595 
 9696         if (p->n_op != ADDROF)
 9797                 return;
 9898         if (getoff(p->n_left->n_lval))
 9999                 return;
 100100         w = tmpalloc(sizeof(struct addrof));
 101101         w->tempnum = p->n_left->n_lval;
 102102         w->oregoff = BITOOR(freetemp(szty(p->n_left->n_type)));
 103103         w->next = otlink;
 104104         otlink = w;
 105105 }
 106106 
 107107 /*
 108108  * Convert address-taken temps to OREGs.
 109109  */
 110110 static void
 111111 cvtaddrof(NODE *p)
 112112 {
 113113         NODE *l;
 114114         int n;
 115115 
 116116         if (p->n_op != ADDROF && p->n_op != TEMP)
 117117                 return;
 118118         if (p->n_op == TEMP) {
 119119                 n = getoff(p->n_lval);
 120120                 if (n == 0)
 121121                         return;
 122122                 p->n_op = OREG;
 123123                 p->n_lval = n;
 124124                 p->n_rval = FPREG;
 125125         } else {
 126126                 l = p->n_left;
 127127                 l->n_type = p->n_type;
 128128                 p->n_right = mklnode(ICON, l->n_lval, 0, l->n_type);
 129129                 p->n_op = PLUS;
 130130                 l->n_op = REG;
 131131                 l->n_lval = 0;
 132132                 l->n_rval = FPREG;
 133133                 
 134134         }
 135135 }
 136136 
 137137 void
 138138 optimize(struct interpass *ipole)
 139139 {
 140140         struct interpass *ip;
 141141         struct labelinfo labinfo;
 142142         struct bblockinfo bbinfo;
 143143 
 144144         ipp = (struct interpass_prolog *)DLIST_NEXT(ipole, qelem);
 145145         epp = (struct interpass_prolog *)DLIST_PREV(ipole, qelem);
 146146 
 147147         if (b2debug) {
 148148                 printf("initial links\n");
 149149                 printip(ipole);
 150150         }
 151151 
 152152         /*
 153153          * Convert ADDROF TEMP to OREGs.
 154154          */
 155155         if (xtemps) {
 156156                 otlink = NULL;
 157157                 DLIST_FOREACH(ip, ipole, qelem) {
 158158                         if (ip->type != IP_NODE)
 159159                                 continue;
 160160                         walkf(ip->ip_node, findaddrof);
 161161                 }
 162162                 if (otlink) {
 163163                         DLIST_FOREACH(ip, ipole, qelem) {
 164164                                 if (ip->type != IP_NODE)
 165165                                         continue;
 166166                                 walkf(ip->ip_node, cvtaddrof);
 167167                         }
 168168                 }
 169169         }
 170170                 
 171171         if (xdeljumps)
 172172                 deljumps(ipole); /* Delete redundant jumps and dead code */
 173173 
 174174 #ifdef PCC_DEBUG
 175175         if (b2debug) {
 176176                 printf("links after deljumps\n");
 177177                 printip(ipole);
 178178         }
 179179 #endif
 180180         if (xssaflag || xtemps) {
 181181                 DLIST_INIT(&bblocks, bbelem);
 182182                 bblocks_build(ipole, &labinfo, &bbinfo);
 183183                 BDEBUG(("Calling cfg_build\n"));
 184184                 cfg_build(&labinfo);
 185185         }
 186186         if (xssaflag) {
 187187                 BDEBUG(("Calling dominators\n"));
 188188                 dominators(&bbinfo);
 189189                 BDEBUG(("Calling computeDF\n"));
 190190                 computeDF(DLIST_NEXT(&bblocks, bbelem), &bbinfo);
 191191                 BDEBUG(("Calling remunreach\n"));
 192192                 remunreach();
 193193 #if 0
 194194                 dfg = dfg_build(cfg);
 195195                 ssa = ssa_build(cfg, dfg);
 196196 #endif
 197197         }
 198198 
 199199 #ifdef PCC_DEBUG
 200200         if (epp->ipp_regs != 0)
 201201                 comperr("register error");
 202202 #endif
 203203 
 204204 #ifdef MYOPTIM
 205205         myoptim((struct interpass *)ipp);
 206206 #endif
 207207 }
 208208 
 209209 /*
 210210  * Delete unused labels, excess of labels, gotos to gotos.
 211211  * This routine can be made much more efficient.
 212212  */
 213213 void
 214214 deljumps(struct interpass *ipole)
 215215 {
 216216         struct interpass *ip, *n, *ip2;
 217217         int gotone,low, high;
 218218         int *lblary, sz, o, i;
 219219 
 220220         low = ipp->ip_lblnum;
 221221         high = epp->ip_lblnum;
 222222 
 223223 #ifdef notyet
 224224         mark = tmpmark(); /* temporary used memory */
 225225 #endif
 226226 
 227227         sz = (high-low) * sizeof(int);
 228228         lblary = tmpalloc(sz);
 229229 
 230230 again:  gotone = 0;
 231231         memset(lblary, 0, sz);
 232232 
 233233         /* refcount and coalesce all labels */
 234234         DLIST_FOREACH(ip, ipole, qelem) {
 235235                 if (ip->type == IP_DEFLAB) {
 236236                         n = DLIST_NEXT(ip, qelem);
 237237                         while (n->type == IP_DEFLAB) {
 238238                                 if (n->type == IP_DEFLAB &&
 239239                                     lblary[n->ip_lbl-low] >= 0)
 240240                                         lblary[n->ip_lbl-low] = -ip->ip_lbl;
 241241                                 n = DLIST_NEXT(n, qelem);
 242242                         }
 243243                 }
 244244                 if (ip->type != IP_NODE)
 245245                         continue;
 246246                 o = ip->ip_node->n_op;
 247247                 if (o == GOTO)
 248248                         i = ip->ip_node->n_left->n_lval;
 249249                 else if (o == CBRANCH)
 250250                         i = ip->ip_node->n_right->n_lval;
 251251                 else
 252252                         continue;
 253253                 lblary[i-low] |= 1;
 254254         }
 255255 
 256256         /* delete coalesced/unused labels and rename gotos */
 257257         DLIST_FOREACH(ip, ipole, qelem) {
 258258                 n = DLIST_NEXT(ip, qelem);
 259259                 if (n->type == IP_DEFLAB) {
 260260                         if (lblary[n->ip_lbl-low] <= 0) {
 261261                                 DLIST_REMOVE(n, qelem);
 262262                                 gotone = 1;
 263263                         }
 264264                         continue;
 265265                 }
 266266                 if (n->type != IP_NODE)
 267267                         continue;
 268268                 o = n->ip_node->n_op;
 269269                 if (o == GOTO)
 270270                         i = n->ip_node->n_left->n_lval;
 271271                 else if (o == CBRANCH)
 272272                         i = n->ip_node->n_right->n_lval;
 273273                 else
 274274                         continue;
 275275                 if (lblary[i-low] < 0) {
 276276                         if (o == GOTO)
 277277                                 n->ip_node->n_left->n_lval = -lblary[i-low];
 278278                         else
 279279                                 n->ip_node->n_right->n_lval = -lblary[i-low];
 280280                 }
 281281         }
 282282 
 283283         /* Delete gotos to the next statement */
 284284         DLIST_FOREACH(ip, ipole, qelem) {
 285285                 n = DLIST_NEXT(ip, qelem);
 286286                 if (n->type != IP_NODE)
 287287                         continue;
 288288                 o = n->ip_node->n_op;
 289289                 if (o == GOTO)
 290290                         i = n->ip_node->n_left->n_lval;
 291291                 else if (o == CBRANCH)
 292292                         i = n->ip_node->n_right->n_lval;
 293293                 else
 294294                         continue;
 295295 
 296296                 ip2 = n;
 297297                 ip2 = DLIST_NEXT(ip2, qelem);
 298298 
 299299                 if (ip2->type != IP_DEFLAB)
 300300                         continue;
 301301                 if (ip2->ip_lbl == i) {
 302302                         tfree(n->ip_node);
 303303                         DLIST_REMOVE(n, qelem);
 304304                         gotone = 1;
 305305                 }
 306306         }
 307307 
 308308         if (gotone)
 309309                 goto again;
 310310 
 311311 #ifdef notyet
 312312         tmpfree(mark);
 313313 #endif
 314314 }
 315315 
 316316 void
 317317 optdump(struct interpass *ip)
 318318 {
 319319         static char *nm[] = { "node", "prolog", "newblk", "epilog", "locctr",
 320320                 "deflab", "defnam", "asm" };
 321321         printf("type %s\n", nm[ip->type-1]);
 322322         switch (ip->type) {
 323323         case IP_NODE:
 324324                 fwalk(ip->ip_node, e2print, 0);
 325325                 break;
 326326         case IP_DEFLAB:
 327327                 printf("label " LABFMT "\n", ip->ip_lbl);
 328328                 break;
 329329         case IP_ASM:
 330330                 printf(": %s\n", ip->ip_asm);
 331331                 break;
 332332         }
 333333 }
 334334 
 335335 /*
 336336  * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
 337337  *
 338338  * Also fills the labelinfo struct with information about which bblocks
 339339  * that contain which label.
 340340  */
 341341 
 342342 void
 343343 bblocks_build(struct interpass *ipole, struct labelinfo *labinfo,
 344344     struct bblockinfo *bbinfo)
 345345 {
 346346         struct interpass *ip;
 347347         struct basicblock *bb = NULL;
 348348         int low, high;
 349349         int count = 0;
 350350         int i;
 351351 
 352352         BDEBUG(("bblocks_build (%p, %p)\n", labinfo, bbinfo));
 353353         low = ipp->ip_lblnum;
 354354         high = epp->ip_lblnum;
 355355 
 356356         /*
 357357          * First statement is a leader.
 358358          * Any statement that is target of a jump is a leader.
 359359          * Any statement that immediately follows a jump is a leader.
 360360          */
 361361         DLIST_FOREACH(ip, ipole, qelem) {
 362362                 if (bb == NULL || (ip->type == IP_EPILOG) ||
 363363                     (ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) {
 364364                         bb = tmpalloc(sizeof(struct basicblock));
 365365                         bb->first = ip;
 366366                         SLIST_INIT(&bb->children);
 367367                         SLIST_INIT(&bb->parents);
 368368                         bb->dfnum = 0;
 369369                         bb->dfparent = 0;
 370370                         bb->semi = 0;
 371371                         bb->ancestor = 0;
 372372                         bb->idom = 0;
 373373                         bb->samedom = 0;
 374374                         bb->bucket = NULL;
 375375                         bb->df = NULL;
 376376                         bb->dfchildren = NULL;
 377377                         bb->Aorig = NULL;
 378378                         bb->Aphi = NULL;
 379379                         bb->bbnum = count;
 380380                         DLIST_INSERT_BEFORE(&bblocks, bb, bbelem);
 381381                         count++;
 382382                 }
 383383                 bb->last = ip;
 384384                 if ((ip->type == IP_NODE) && (ip->ip_node->n_op == GOTO ||
 385385                     ip->ip_node->n_op == CBRANCH))
 386386                         bb = NULL;
 387387                 if (ip->type == IP_PROLOG)
 388388                         bb = NULL;
 389389         }
 390390         nbblocks = count;
 391391 
 392392         if (b2debug) {
 393393                 printf("Basic blocks in func: %d, low %d, high %d\n",
 394394                     count, low, high);
 395395                 DLIST_FOREACH(bb, &bblocks, bbelem) {
 396396                         printf("bb %p: first %p last %p\n", bb,
 397397                             bb->first, bb->last);
 398398                 }
 399399         }
 400400 
 401401         labinfo->low = low;
 402402         labinfo->size = high - low + 1;
 403403         labinfo->arr = tmpalloc(labinfo->size * sizeof(struct basicblock *));
 404404         for (i = 0; i < labinfo->size; i++) {
 405405                 labinfo->arr[i] = NULL;
 406406         }
 407407         
 408408         bbinfo->size = count + 1;
 409409         bbinfo->arr = tmpalloc(bbinfo->size * sizeof(struct basicblock *));
 410410         for (i = 0; i < bbinfo->size; i++) {
 411411                 bbinfo->arr[i] = NULL;
 412412         }
 413413 
 414414         /* Build the label table */
 415415         DLIST_FOREACH(bb, &bblocks, bbelem) {
 416416                 if (bb->first->type == IP_DEFLAB)
 417417                         labinfo->arr[bb->first->ip_lbl - low] = bb;
 418418         }
 419419 
 420420         if (b2debug) {
 421421                 printf("Label table:\n");
 422422                 for (i = 0; i < labinfo->size; i++)
 423423                         if (labinfo->arr[i])
 424424                                 printf("Label %d bblock %p\n", i+low,
 425425                                     labinfo->arr[i]);
 426426         }
 427427 }
 428428 
 429429 /*
 430430  * Build the control flow graph.
 431431  */
 432432 
 433433 void
 434434 cfg_build(struct labelinfo *labinfo)
 435435 {
 436436         /* Child and parent nodes */
 437437         struct cfgnode *cnode;
 438438         struct cfgnode *pnode;
 439439         struct basicblock *bb;
 440440         
 441441         DLIST_FOREACH(bb, &bblocks, bbelem) {
 442442 
 443443                 if (bb->first->type == IP_EPILOG) {
 444444                         break;
 445445                 }
 446446 
 447447                 cnode = tmpalloc(sizeof(struct cfgnode));
 448448                 pnode = tmpalloc(sizeof(struct cfgnode));
 449449                 pnode->bblock = bb;
 450450 
 451451                 if ((bb->last->type == IP_NODE) &&
 452452                     (bb->last->ip_node->n_op == GOTO)) {
 453453                         if (bb->last->ip_node->n_left->n_lval - labinfo->low >
 454454                             labinfo->size) {
 455455                                 comperr("Label out of range: %d, base %d",
 456456                                         bb->last->ip_node->n_left->n_lval,
 457457                                         labinfo->low);
 458458                         }
 459459                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_left->n_lval - labinfo->low];
 460460                         SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 461461                         SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 462462                         continue;
 463463                 }
 464464                 if ((bb->last->type == IP_NODE) &&
 465465                     (bb->last->ip_node->n_op == CBRANCH)) {
 466466                         if (bb->last->ip_node->n_right->n_lval - labinfo->low >
 467467                             labinfo->size)
 468468                                 comperr("Label out of range: %d",
 469469                                         bb->last->ip_node->n_left->n_lval);
 470470                         
 471471                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_right->n_lval - labinfo->low];
 472472                         SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 473473                         SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 474474                         cnode = tmpalloc(sizeof(struct cfgnode));
 475475                         pnode = tmpalloc(sizeof(struct cfgnode));
 476476                         pnode->bblock = bb;
 477477                 }
 478478 
 479479                 cnode->bblock = DLIST_NEXT(bb, bbelem);
 480480                 SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 481481                 SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 482482         }
 483483 }
 484484 
 485485 void
 486486 cfg_dfs(struct basicblock *bb, unsigned int parent, struct bblockinfo *bbinfo)
 487487 {
 488488         struct cfgnode *cnode;
 489489         
 490490         if (bb->dfnum != 0)
 491491                 return;
 492492 
 493493         bb->dfnum = ++dfsnum;
 494494         bb->dfparent = parent;
 495495         bbinfo->arr[bb->dfnum] = bb;
 496496         SLIST_FOREACH(cnode, &bb->children, cfgelem) {
 497497                 cfg_dfs(cnode->bblock, bb->dfnum, bbinfo);
 498498         }
 499499         /* Don't bring in unreachable nodes in the future */
 500500         bbinfo->size = dfsnum + 1;
 501501 }
 502502 
 503503 static bittype *
 504504 setalloc(int nelem)
 505505 {
 506506         bittype *b;
 507507         int sz = (nelem+NUMBITS-1)/NUMBITS;
 508508 
 509509         b = tmpalloc(sz * sizeof(bittype));
 510510         memset(b, 0, sz * sizeof(bittype));
 511511         return b;
 512512 }
 513513 
 514514 /*
 515515  * Algorithm 19.9, pp 414 from Appel.
 516516  */
 517517 
 518518 void
 519519 dominators(struct bblockinfo *bbinfo)
 520520 {
 521521         struct cfgnode *cnode;
 522522         struct basicblock *bb, *y, *v;
 523523         struct basicblock *s, *sprime, *p;
 524524         int h, i;
 525525 
 526526         DLIST_FOREACH(bb, &bblocks, bbelem) {
 527527                 bb->bucket = setalloc(bbinfo->size);
 528528                 bb->df = setalloc(bbinfo->size);
 529529                 bb->dfchildren = setalloc(bbinfo->size);
 530530         }
 531531 
 532532         dfsnum = 0;
 533533         cfg_dfs(DLIST_NEXT(&bblocks, bbelem), 0, bbinfo);
 534534 
 535535         if (b2debug) {
 536536                 struct basicblock *bbb;
 537537                 struct cfgnode *ccnode;
 538538 
 539539                 DLIST_FOREACH(bbb, &bblocks, bbelem) {
 540540                         printf("Basic block %d, parents: ", bbb->dfnum);
 541541                         SLIST_FOREACH(ccnode, &bbb->parents, cfgelem) {
 542542                                 printf("%d, ", ccnode->bblock->dfnum);
 543543                         }
 544544                         printf("\nChildren: ");
 545545                         SLIST_FOREACH(ccnode, &bbb->children, cfgelem) {
 546546                                 printf("%d, ", ccnode->bblock->dfnum);
 547547                         }
 548548                         printf("\n");
 549549                 }
 550550         }
 551551 
 552552         for(h = bbinfo->size - 1; h > 1; h--) {
 553553                 bb = bbinfo->arr[h];
 554554                 p = s = bbinfo->arr[bb->dfparent];
 555555                 SLIST_FOREACH(cnode, &bb->parents, cfgelem) {
 556556                         if (cnode->bblock->dfnum <= bb->dfnum)
 557557                                 sprime = cnode->bblock;
 558558                         else
 559559                                 sprime = bbinfo->arr[ancestorwithlowestsemi
 560560                                               (cnode->bblock, bbinfo)->semi];
 561561                         if (sprime->dfnum < s->dfnum)
 562562                                 s = sprime;
 563563                 }
 564564                 bb->semi = s->dfnum;
 565565                 BITSET(s->bucket, bb->dfnum);
 566566                 link(p, bb);
 567567                 for (i = 1; i < bbinfo->size; i++) {
 568568                         if(TESTBIT(p->bucket, i)) {
 569569                                 v = bbinfo->arr[i];
 570570                                 y = ancestorwithlowestsemi(v, bbinfo);
 571571                                 if (y->semi == v->semi)
 572572                                         v->idom = p->dfnum;
 573573                                 else
 574574                                         v->samedom = y->dfnum;
 575575                         }
 576576                 }
 577577                 memset(p->bucket, 0, (bbinfo->size + 7)/8);
 578578         }
 579579 
 580580         if (b2debug) {
 581581                 printf("Num\tSemi\tAncest\tidom\n");
 582582                 DLIST_FOREACH(bb, &bblocks, bbelem) {
 583583                         printf("%d\t%d\t%d\t%d\n", bb->dfnum, bb->semi,
 584584                             bb->ancestor, bb->idom);
 585585                 }
 586586         }
 587587 
 588588         for(h = 2; h < bbinfo->size; h++) {
 589589                 bb = bbinfo->arr[h];
 590590                 if (bb->samedom != 0) {
 591591                         bb->idom = bbinfo->arr[bb->samedom]->idom;
 592592                 }
 593593         }
 594594         DLIST_FOREACH(bb, &bblocks, bbelem) {
 595595                 if (bb->idom != 0 && bb->idom != bb->dfnum) {
 596596                         BDEBUG(("Setting child %d of %d\n",
 597597                             bb->dfnum, bbinfo->arr[bb->idom]->dfnum));
 598598                         BITSET(bbinfo->arr[bb->idom]->dfchildren, bb->dfnum);
 599599                 }
 600600         }
 601601 }
 602602 
 603603 
 604604 struct basicblock *
 605605 ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo)
 606606 {
 607607         struct basicblock *u = bblock;
 608608         struct basicblock *v = bblock;
 609609 
 610610         while (v->ancestor != 0) {
 611611                 if (bbinfo->arr[v->semi]->dfnum <
 612612                     bbinfo->arr[u->semi]->dfnum)
 613613                         u = v;
 614614                 v = bbinfo->arr[v->ancestor];
 615615         }
 616616         return u;
 617617 }
 618618 
 619619 void
 620620 link(struct basicblock *parent, struct basicblock *child)
 621621 {
 622622         child->ancestor = parent->dfnum;
 623623 }
 624624 
 625625 void
 626626 computeDF(struct basicblock *bblock, struct bblockinfo *bbinfo)
 627627 {
 628628         struct cfgnode *cnode;
 629629         int h, i;
 630630         
 631631         SLIST_FOREACH(cnode, &bblock->children, cfgelem) {
 632632                 if (cnode->bblock->idom != bblock->dfnum)
 633633                         BITSET(bblock->df, cnode->bblock->dfnum);
 634634         }
 635635         for (h = 1; h < bbinfo->size; h++) {
 636636                 if (!TESTBIT(bblock->dfchildren, h))
 637637                         continue;
 638638                 computeDF(bbinfo->arr[h], bbinfo);
 639639                 for (i = 1; i < bbinfo->size; i++) {
 640640                         if (TESTBIT(bbinfo->arr[h]->df, i) &&
 641641                             (bbinfo->arr[h] == bblock ||
 642642                              (bblock->idom != bbinfo->arr[h]->dfnum)))
 643643                             BITSET(bblock->df, i);
 644644                 }
 645645         }
 646646 }
 647647 
 648648 static struct basicblock *currbb;
 649649 static struct interpass *currip;
 650650 
 651651 /* Helper function for findTemps, Find assignment nodes. */
 652652 static void
 653653 searchasg(NODE *p)
 654654 {
 655655         struct pvarinfo *pv;
 656656 
 657657         if (p->n_op != ASSIGN)
 658658                 return;
 659659 
 660660         if (p->n_left->n_op != TEMP)
 661661                 return;
 662662 
 663663         pv = tmpcalloc(sizeof(struct pvarinfo));
 664664         pv->next = defsites.arr[p->n_left->n_lval];
 665665         pv->bb = currbb;
 666666         pv->top = currip->ip_node;
 667667         pv->n = p->n_left;
 668668         BITSET(currbb->Aorig, p->n_left->n_lval);
 669669 
 670670         defsites.arr[p->n_left->n_lval] = pv;
 671671 }
 672672 
 673673 /* Walk the interpass looking for assignment nodes. */
 674674 void findTemps(struct interpass *ip)
 675675 {
 676676         if (ip->type != IP_NODE)
 677677                 return;
 678678 
 679679         currip = ip;
 680680 
 681681         walkf(ip->ip_node, searchasg);
 682682 }
 683683 
 684684 /*
 685685  * Algorithm 19.6 from Appel.
 686686  */
 687687 
 688688 void
 689689 placePhiFunctions(struct bblockinfo *bbinfo)
 690690 {
 691691         struct basicblock *bb;
 692692         struct interpass *ip;
 693693         int maxtmp, i, j, k, l;
 694694         struct pvarinfo *n;
 695695         struct cfgnode *cnode;
 696696         TWORD ntype;
 697697         NODE *p;
 698698         struct pvarinfo *pv;
 699699 
 700700         bb = DLIST_NEXT(&bblocks, bbelem);
 701701         defsites.low = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
 702702         bb = DLIST_PREV(&bblocks, bbelem);
 703703         maxtmp = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
 704704         defsites.size = maxtmp - defsites.low + 1;
 705705         defsites.arr = tmpcalloc(defsites.size*sizeof(struct pvarinfo *));
 706706 
 707707         /* Find all defsites */
 708708         DLIST_FOREACH(bb, &bblocks, bbelem) {
 709709                 currbb = bb;
 710710                 ip = bb->first;
 711711                 bb->Aorig = setalloc(defsites.size);
 712712                 bb->Aphi = setalloc(defsites.size);
 713713                 
 714714 
 715715                 while (ip != bb->last) {
 716716                         findTemps(ip);
 717717                         ip = DLIST_NEXT(ip, qelem);
 718718                 }
 719719                 /* Make sure we get the last statement in the bblock */
 720720                 findTemps(ip);
 721721         }
 722722         /* For each variable */
 723723         for (i = defsites.low; i < defsites.size; i++) {
 724724                 /* While W not empty */
 725725                 while (defsites.arr[i] != NULL) {
 726726                         /* Remove some node n from W */
 727727                         n = defsites.arr[i];
 728728                         defsites.arr[i] = n->next;
 729729                         /* For each y in n->bb->df */
 730730                         for (j = 0; j < bbinfo->size; j++) {
 731731                                 if (!TESTBIT(n->bb->df, j))
 732732                                         continue;
 733733                                 
 734734                                 if (TESTBIT(bbinfo->arr[j]->Aphi, i))
 735735                                         continue;
 736736 
 737737                                 ntype = n->n->n_type;
 738738                                 k = 0;
 739739                                 /* Amount of predecessors for y */
 740740                                 SLIST_FOREACH(cnode, &n->bb->parents, cfgelem)
 741741                                         k++;
 742742                                 /* Construct phi(...) */
 743743                                 p = mklnode(TEMP, i, 0, ntype);
 744744                                 for (l = 0; l < k-1; l++)
 745745                                         p = mkbinode(PHI, p,
 746746                                             mklnode(TEMP, i, 0, ntype), ntype);
 747747                                 ip = ipnode(mkbinode(ASSIGN,
 748748                                     mklnode(TEMP, i, 0, ntype), p, ntype));
 749749                                 /* Insert phi at top of basic block */
 750750                                 DLIST_INSERT_BEFORE(((struct interpass*)&n->bb->first), ip, qelem);
 751751                                 n->bb->first = ip;
 752752                                 BITSET(bbinfo->arr[j]->Aphi, i);
 753753                                 if (!TESTBIT(bbinfo->arr[j]->Aorig, i)) {
 754754                                         pv = tmpalloc(sizeof(struct pvarinfo));
 755755                                         // XXXpj Ej fullständig information.
 756756                                         pv->bb = bbinfo->arr[j];
 757757                                         pv->next = defsites.arr[i]->next;
 758758                                         defsites.arr[i] = pv;
 759759                                 }
 760760                                         
 761761 
 762762                         }
 763763                 }
 764764         }
 765765 }
 766766 
 767767 /*
 768768  * Remove unreachable nodes in the CFG.
 769769  */
 770770 
 771771 void
 772772 remunreach(void)
 773773 {
 774774         struct basicblock *bb, *nbb;
 775775         struct interpass *next, *ctree;
 776776 
 777777         bb = DLIST_NEXT(&bblocks, bbelem);
 778778         while (bb != &bblocks) {
 779779                 nbb = DLIST_NEXT(bb, bbelem);
 780780 
 781781                 /* Code with dfnum 0 is unreachable */
 782782                 if (bb->dfnum != 0) {
 783783                         bb = nbb;
 784784                         continue;
 785785                 }
 786786 
 787787                 /* Need the epilogue node for other parts of the
 788788                    compiler, set its label to 0 and backend will
 789789                    handle it. */
 790790                 if (bb->first->type == IP_EPILOG) {
 791791                         bb->first->ip_lbl = 0;
 792792                         bb = nbb;
 793793                         continue;
 794794                 }
 795795 
 796796                 next = bb->first;
 797797                 do {
 798798                         ctree = next;
 799799                         next = DLIST_NEXT(ctree, qelem);
 800800                         
 801801                         if (ctree->type == IP_NODE)
 802802                                 tfree(ctree->ip_node);
 803803                         DLIST_REMOVE(ctree, qelem);
 804804                 } while (ctree != bb->last);
 805805                         
 806806                 DLIST_REMOVE(bb, bbelem);
 807807                 bb = nbb;
 808808         }
 809809 }
 810810 
 811811 void
 812812 printip(struct interpass *pole)
 813813 {
 814814         static char *foo[] = {
 815815            0, "NODE", "PROLOG", "STKOFF", "EPILOG", "DEFLAB", "DEFNAM", "ASM" };
 816816         struct interpass *ip;
 817817         struct interpass_prolog *ipp, *epp;
 818818 
 819819         DLIST_FOREACH(ip, pole, qelem) {
<>820 -                if (ip->type >= MAXIP)
  820+                if (ip->type > MAXIP)
<_821821                         printf("IP(%d) (%p): ", ip->type, ip);
 822822                 else
 823823                         printf("%s (%p): ", foo[ip->type], ip);
 824824                 switch (ip->type) {
 825825                 case IP_NODE: printf("\n");
 826826                         fwalk(ip->ip_node, e2print, 0); break;
 827827                 case IP_PROLOG:
 828828                         ipp = (struct interpass_prolog *)ip;
 829829                         printf("%s %s regs %x autos %d mintemp %d minlbl %d\n",
 830830                             ipp->ipp_name, ipp->ipp_vis ? "(local)" : "",
 831831                             ipp->ipp_regs, ipp->ipp_autos, ipp->ip_tmpnum,
 832832                             ipp->ip_lblnum);
 833833                         break;
 834834                 case IP_EPILOG:
 835835                         epp = (struct interpass_prolog *)ip;
 836836                         printf("%s %s regs %x autos %d mintemp %d minlbl %d\n",
 837837                             epp->ipp_name, epp->ipp_vis ? "(local)" : "",
 838838                             epp->ipp_regs, epp->ipp_autos, epp->ip_tmpnum,
 839839                             epp->ip_lblnum);
 840840                         break;
 841841                 case IP_DEFLAB: printf(LABFMT "\n", ip->ip_lbl); break;
 842842                 case IP_DEFNAM: printf("\n"); break;
 843843                 case IP_ASM: printf("%s\n", ip->ip_asm); break;
 844844                 default:
 845845                         break;
 846846                 }
 847847         }
 848848 }
FishEye: Open Source License registered to PCC.
Your maintenance has expired. You can renew your license at http://www.atlassian.com/fisheye/renew
Atlassian FishEye, CVS analysis. (Version:1.6.3 Build:build-336 2008-11-04) - Administration - Page generated 2014-10-30 18:31 +0100