Quick Search:

Mode

Context

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

Other Diffs

Ignore

Blank Lines Whitespace: Expand:

Diff

1.43
 
1.44
 
MAIN:ragge:20060620060243
 
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;
<> 70+static struct interpass *cvpole;
7071 
 7172 struct addrof {
 7273         struct addrof *next;
 7374         int tempnum;
 7475         int oregoff;
 7576 } *otlink;
 7677 
 7778 static int
 7879 getoff(int num)
 7980 {
 8081         struct addrof *w;
 8182 
 8283         for (w = otlink; w; w = w->next)
 8384                 if (w->tempnum == num)
 8485                         return w->oregoff;
 8586         return 0;
 8687 }
 8788 
 8889 /*
<> 90+ * Use stack argument addresses instead of copying if & is used on a var.
  91+ */
  92+static int
  93+setargs(int tval, struct addrof *w)
  94+{
  95+        struct interpass *ip;
  96+        NODE *p;
  97+
  98+        ip = DLIST_NEXT(cvpole, qelem); /* PROLOG */
  99+        ip = DLIST_NEXT(ip, qelem); /* first DEFLAB */
  100+        ip = DLIST_NEXT(ip, qelem); /* first NODE */
  101+        for (; ip->type != IP_DEFLAB; ip = DLIST_NEXT(ip, qelem)) {
  102+                p = ip->ip_node;
  103+#ifdef PCC_DEBUG
  104+                if (p->n_op != ASSIGN || p->n_left->n_op != TEMP)
  105+                        comperr("temparg");
  106+#endif
  107+                if (p->n_right->n_op != OREG)
  108+                        continue; /* arg in register */
  109+                if (tval != p->n_left->n_lval)
  110+                        continue; /* wrong assign */
  111+                w->oregoff = p->n_right->n_lval;
  112+                tfree(p);
  113+                DLIST_REMOVE(ip, qelem);
  114+                return 1;
  115+        }
  116+        return 0;
  117+}
  118+
  119+/*
89120  * Search for ADDROF elements and, if found, record them.
 90121  */
 91122 static void
 92123 findaddrof(NODE *p)
 93124 {
 94125         struct addrof *w;
 95126 
 96127         if (p->n_op != ADDROF)
 97128                 return;
 98129         if (getoff(p->n_left->n_lval))
 99130                 return;
 100131         w = tmpalloc(sizeof(struct addrof));
 101132         w->tempnum = p->n_left->n_lval;
<>102 -        w->oregoff = BITOOR(freetemp(szty(p->n_left->n_type)));
  133+        if (setargs(p->n_left->n_lval, w) == 0)
  134+                w->oregoff = BITOOR(freetemp(szty(p->n_left->n_type)));
103135         w->next = otlink;
 104136         otlink = w;
 105137 }
 106138 
<> 139+
107140 /*
 108141  * Convert address-taken temps to OREGs.
 109142  */
 110143 static void
 111144 cvtaddrof(NODE *p)
 112145 {
 113146         NODE *l;
 114147         int n;
 115148 
 116149         if (p->n_op != ADDROF && p->n_op != TEMP)
 117150                 return;
 118151         if (p->n_op == TEMP) {
 119152                 n = getoff(p->n_lval);
 120153                 if (n == 0)
 121154                         return;
 122155                 p->n_op = OREG;
 123156                 p->n_lval = n;
 124157                 p->n_rval = FPREG;
 125158         } else {
 126159                 l = p->n_left;
 127160                 l->n_type = p->n_type;
 128161                 p->n_right = mklnode(ICON, l->n_lval, 0, l->n_type);
 129162                 p->n_op = PLUS;
 130163                 l->n_op = REG;
 131164                 l->n_lval = 0;
 132165                 l->n_rval = FPREG;
 133166                 
 134167         }
 135168 }
 136169 
 137170 void
 138171 optimize(struct interpass *ipole)
 139172 {
 140173         struct interpass *ip;
 141174         struct labelinfo labinfo;
 142175         struct bblockinfo bbinfo;
 143176 
 144177         ipp = (struct interpass_prolog *)DLIST_NEXT(ipole, qelem);
 145178         epp = (struct interpass_prolog *)DLIST_PREV(ipole, qelem);
 146179 
 147180         if (b2debug) {
 148181                 printf("initial links\n");
 149182                 printip(ipole);
 150183         }
 151184 
 152185         /*
 153186          * Convert ADDROF TEMP to OREGs.
 154187          */
 155188         if (xtemps) {
 156189                 otlink = NULL;
<> 190+                cvpole = ipole;
<_157191                 DLIST_FOREACH(ip, ipole, qelem) {
 158192                         if (ip->type != IP_NODE)
 159193                                 continue;
 160194                         walkf(ip->ip_node, findaddrof);
 161195                 }
 162196                 if (otlink) {
 163197                         DLIST_FOREACH(ip, ipole, qelem) {
 164198                                 if (ip->type != IP_NODE)
 165199                                         continue;
 166200                                 walkf(ip->ip_node, cvtaddrof);
 167201                         }
 168202                 }
 169203         }
 170204                 
 171205         if (xdeljumps)
 172206                 deljumps(ipole); /* Delete redundant jumps and dead code */
 173207 
 174208 #ifdef PCC_DEBUG
 175209         if (b2debug) {
 176210                 printf("links after deljumps\n");
 177211                 printip(ipole);
 178212         }
 179213 #endif
 180214         if (xssaflag || xtemps) {
 181215                 DLIST_INIT(&bblocks, bbelem);
 182216                 bblocks_build(ipole, &labinfo, &bbinfo);
 183217                 BDEBUG(("Calling cfg_build\n"));
 184218                 cfg_build(&labinfo);
 185219         }
 186220         if (xssaflag) {
 187221                 BDEBUG(("Calling dominators\n"));
 188222                 dominators(&bbinfo);
 189223                 BDEBUG(("Calling computeDF\n"));
 190224                 computeDF(DLIST_NEXT(&bblocks, bbelem), &bbinfo);
 191225                 BDEBUG(("Calling remunreach\n"));
 192226                 remunreach();
 193227 #if 0
 194228                 dfg = dfg_build(cfg);
 195229                 ssa = ssa_build(cfg, dfg);
 196230 #endif
 197231         }
 198232 
 199233 #ifdef PCC_DEBUG
 200234         if (epp->ipp_regs != 0)
 201235                 comperr("register error");
 202236 #endif
 203237 
 204238 #ifdef MYOPTIM
 205239         myoptim((struct interpass *)ipp);
 206240 #endif
 207241 }
 208242 
 209243 /*
 210244  * Delete unused labels, excess of labels, gotos to gotos.
 211245  * This routine can be made much more efficient.
 212246  */
 213247 void
 214248 deljumps(struct interpass *ipole)
 215249 {
 216250         struct interpass *ip, *n, *ip2;
 217251         int gotone,low, high;
 218252         int *lblary, sz, o, i;
 219253 
 220254         low = ipp->ip_lblnum;
 221255         high = epp->ip_lblnum;
 222256 
 223257 #ifdef notyet
 224258         mark = tmpmark(); /* temporary used memory */
 225259 #endif
 226260 
 227261         sz = (high-low) * sizeof(int);
 228262         lblary = tmpalloc(sz);
 229263 
 230264 again:  gotone = 0;
 231265         memset(lblary, 0, sz);
 232266 
 233267         /* refcount and coalesce all labels */
 234268         DLIST_FOREACH(ip, ipole, qelem) {
 235269                 if (ip->type == IP_DEFLAB) {
 236270                         n = DLIST_NEXT(ip, qelem);
 237271                         while (n->type == IP_DEFLAB) {
 238272                                 if (n->type == IP_DEFLAB &&
 239273                                     lblary[n->ip_lbl-low] >= 0)
 240274                                         lblary[n->ip_lbl-low] = -ip->ip_lbl;
 241275                                 n = DLIST_NEXT(n, qelem);
 242276                         }
 243277                 }
 244278                 if (ip->type != IP_NODE)
 245279                         continue;
 246280                 o = ip->ip_node->n_op;
 247281                 if (o == GOTO)
 248282                         i = ip->ip_node->n_left->n_lval;
 249283                 else if (o == CBRANCH)
 250284                         i = ip->ip_node->n_right->n_lval;
 251285                 else
 252286                         continue;
 253287                 lblary[i-low] |= 1;
 254288         }
 255289 
 256290         /* delete coalesced/unused labels and rename gotos */
 257291         DLIST_FOREACH(ip, ipole, qelem) {
 258292                 n = DLIST_NEXT(ip, qelem);
 259293                 if (n->type == IP_DEFLAB) {
 260294                         if (lblary[n->ip_lbl-low] <= 0) {
 261295                                 DLIST_REMOVE(n, qelem);
 262296                                 gotone = 1;
 263297                         }
 264298                         continue;
 265299                 }
 266300                 if (n->type != IP_NODE)
 267301                         continue;
 268302                 o = n->ip_node->n_op;
 269303                 if (o == GOTO)
 270304                         i = n->ip_node->n_left->n_lval;
 271305                 else if (o == CBRANCH)
 272306                         i = n->ip_node->n_right->n_lval;
 273307                 else
 274308                         continue;
 275309                 if (lblary[i-low] < 0) {
 276310                         if (o == GOTO)
 277311                                 n->ip_node->n_left->n_lval = -lblary[i-low];
 278312                         else
 279313                                 n->ip_node->n_right->n_lval = -lblary[i-low];
 280314                 }
 281315         }
 282316 
 283317         /* Delete gotos to the next statement */
 284318         DLIST_FOREACH(ip, ipole, qelem) {
 285319                 n = DLIST_NEXT(ip, qelem);
 286320                 if (n->type != IP_NODE)
 287321                         continue;
 288322                 o = n->ip_node->n_op;
 289323                 if (o == GOTO)
 290324                         i = n->ip_node->n_left->n_lval;
 291325                 else if (o == CBRANCH)
 292326                         i = n->ip_node->n_right->n_lval;
 293327                 else
 294328                         continue;
 295329 
 296330                 ip2 = n;
 297331                 ip2 = DLIST_NEXT(ip2, qelem);
 298332 
 299333                 if (ip2->type != IP_DEFLAB)
 300334                         continue;
 301335                 if (ip2->ip_lbl == i) {
 302336                         tfree(n->ip_node);
 303337                         DLIST_REMOVE(n, qelem);
 304338                         gotone = 1;
 305339                 }
 306340         }
 307341 
 308342         if (gotone)
 309343                 goto again;
 310344 
 311345 #ifdef notyet
 312346         tmpfree(mark);
 313347 #endif
 314348 }
 315349 
 316350 void
 317351 optdump(struct interpass *ip)
 318352 {
 319353         static char *nm[] = { "node", "prolog", "newblk", "epilog", "locctr",
 320354                 "deflab", "defnam", "asm" };
 321355         printf("type %s\n", nm[ip->type-1]);
 322356         switch (ip->type) {
 323357         case IP_NODE:
 324358                 fwalk(ip->ip_node, e2print, 0);
 325359                 break;
 326360         case IP_DEFLAB:
 327361                 printf("label " LABFMT "\n", ip->ip_lbl);
 328362                 break;
 329363         case IP_ASM:
 330364                 printf(": %s\n", ip->ip_asm);
 331365                 break;
 332366         }
 333367 }
 334368 
 335369 /*
 336370  * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
 337371  *
 338372  * Also fills the labelinfo struct with information about which bblocks
 339373  * that contain which label.
 340374  */
 341375 
 342376 void
 343377 bblocks_build(struct interpass *ipole, struct labelinfo *labinfo,
 344378     struct bblockinfo *bbinfo)
 345379 {
 346380         struct interpass *ip;
 347381         struct basicblock *bb = NULL;
 348382         int low, high;
 349383         int count = 0;
 350384         int i;
 351385 
 352386         BDEBUG(("bblocks_build (%p, %p)\n", labinfo, bbinfo));
 353387         low = ipp->ip_lblnum;
 354388         high = epp->ip_lblnum;
 355389 
 356390         /*
 357391          * First statement is a leader.
 358392          * Any statement that is target of a jump is a leader.
 359393          * Any statement that immediately follows a jump is a leader.
 360394          */
 361395         DLIST_FOREACH(ip, ipole, qelem) {
 362396                 if (bb == NULL || (ip->type == IP_EPILOG) ||
 363397                     (ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) {
 364398                         bb = tmpalloc(sizeof(struct basicblock));
 365399                         bb->first = ip;
 366400                         SLIST_INIT(&bb->children);
 367401                         SLIST_INIT(&bb->parents);
 368402                         bb->dfnum = 0;
 369403                         bb->dfparent = 0;
 370404                         bb->semi = 0;
 371405                         bb->ancestor = 0;
 372406                         bb->idom = 0;
 373407                         bb->samedom = 0;
 374408                         bb->bucket = NULL;
 375409                         bb->df = NULL;
 376410                         bb->dfchildren = NULL;
 377411                         bb->Aorig = NULL;
 378412                         bb->Aphi = NULL;
 379413                         bb->bbnum = count;
 380414                         DLIST_INSERT_BEFORE(&bblocks, bb, bbelem);
 381415                         count++;
 382416                 }
 383417                 bb->last = ip;
 384418                 if ((ip->type == IP_NODE) && (ip->ip_node->n_op == GOTO ||
 385419                     ip->ip_node->n_op == CBRANCH))
 386420                         bb = NULL;
 387421                 if (ip->type == IP_PROLOG)
 388422                         bb = NULL;
 389423         }
 390424         nbblocks = count;
 391425 
 392426         if (b2debug) {
 393427                 printf("Basic blocks in func: %d, low %d, high %d\n",
 394428                     count, low, high);
 395429                 DLIST_FOREACH(bb, &bblocks, bbelem) {
 396430                         printf("bb %p: first %p last %p\n", bb,
 397431                             bb->first, bb->last);
 398432                 }
 399433         }
 400434 
 401435         labinfo->low = low;
 402436         labinfo->size = high - low + 1;
 403437         labinfo->arr = tmpalloc(labinfo->size * sizeof(struct basicblock *));
 404438         for (i = 0; i < labinfo->size; i++) {
 405439                 labinfo->arr[i] = NULL;
 406440         }
 407441         
 408442         bbinfo->size = count + 1;
 409443         bbinfo->arr = tmpalloc(bbinfo->size * sizeof(struct basicblock *));
 410444         for (i = 0; i < bbinfo->size; i++) {
 411445                 bbinfo->arr[i] = NULL;
 412446         }
 413447 
 414448         /* Build the label table */
 415449         DLIST_FOREACH(bb, &bblocks, bbelem) {
 416450                 if (bb->first->type == IP_DEFLAB)
 417451                         labinfo->arr[bb->first->ip_lbl - low] = bb;
 418452         }
 419453 
 420454         if (b2debug) {
 421455                 printf("Label table:\n");
 422456                 for (i = 0; i < labinfo->size; i++)
 423457                         if (labinfo->arr[i])
 424458                                 printf("Label %d bblock %p\n", i+low,
 425459                                     labinfo->arr[i]);
 426460         }
 427461 }
 428462 
 429463 /*
 430464  * Build the control flow graph.
 431465  */
 432466 
 433467 void
 434468 cfg_build(struct labelinfo *labinfo)
 435469 {
 436470         /* Child and parent nodes */
 437471         struct cfgnode *cnode;
 438472         struct cfgnode *pnode;
 439473         struct basicblock *bb;
 440474         
 441475         DLIST_FOREACH(bb, &bblocks, bbelem) {
 442476 
 443477                 if (bb->first->type == IP_EPILOG) {
 444478                         break;
 445479                 }
 446480 
 447481                 cnode = tmpalloc(sizeof(struct cfgnode));
 448482                 pnode = tmpalloc(sizeof(struct cfgnode));
 449483                 pnode->bblock = bb;
 450484 
 451485                 if ((bb->last->type == IP_NODE) &&
 452486                     (bb->last->ip_node->n_op == GOTO)) {
 453487                         if (bb->last->ip_node->n_left->n_lval - labinfo->low >
 454488                             labinfo->size) {
 455489                                 comperr("Label out of range: %d, base %d",
 456490                                         bb->last->ip_node->n_left->n_lval,
 457491                                         labinfo->low);
 458492                         }
 459493                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_left->n_lval - labinfo->low];
 460494                         SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 461495                         SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 462496                         continue;
 463497                 }
 464498                 if ((bb->last->type == IP_NODE) &&
 465499                     (bb->last->ip_node->n_op == CBRANCH)) {
 466500                         if (bb->last->ip_node->n_right->n_lval - labinfo->low >
 467501                             labinfo->size)
 468502                                 comperr("Label out of range: %d",
 469503                                         bb->last->ip_node->n_left->n_lval);
 470504                         
 471505                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_right->n_lval - labinfo->low];
 472506                         SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 473507                         SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 474508                         cnode = tmpalloc(sizeof(struct cfgnode));
 475509                         pnode = tmpalloc(sizeof(struct cfgnode));
 476510                         pnode->bblock = bb;
 477511                 }
 478512 
 479513                 cnode->bblock = DLIST_NEXT(bb, bbelem);
 480514                 SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 481515                 SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 482516         }
 483517 }
 484518 
 485519 void
 486520 cfg_dfs(struct basicblock *bb, unsigned int parent, struct bblockinfo *bbinfo)
 487521 {
 488522         struct cfgnode *cnode;
 489523         
 490524         if (bb->dfnum != 0)
 491525                 return;
 492526 
 493527         bb->dfnum = ++dfsnum;
 494528         bb->dfparent = parent;
 495529         bbinfo->arr[bb->dfnum] = bb;
 496530         SLIST_FOREACH(cnode, &bb->children, cfgelem) {
 497531                 cfg_dfs(cnode->bblock, bb->dfnum, bbinfo);
 498532         }
 499533         /* Don't bring in unreachable nodes in the future */
 500534         bbinfo->size = dfsnum + 1;
 501535 }
 502536 
 503537 static bittype *
 504538 setalloc(int nelem)
 505539 {
 506540         bittype *b;
 507541         int sz = (nelem+NUMBITS-1)/NUMBITS;
 508542 
 509543         b = tmpalloc(sz * sizeof(bittype));
 510544         memset(b, 0, sz * sizeof(bittype));
 511545         return b;
 512546 }
 513547 
 514548 /*
 515549  * Algorithm 19.9, pp 414 from Appel.
 516550  */
 517551 
 518552 void
 519553 dominators(struct bblockinfo *bbinfo)
 520554 {
 521555         struct cfgnode *cnode;
 522556         struct basicblock *bb, *y, *v;
 523557         struct basicblock *s, *sprime, *p;
 524558         int h, i;
 525559 
 526560         DLIST_FOREACH(bb, &bblocks, bbelem) {
 527561                 bb->bucket = setalloc(bbinfo->size);
 528562                 bb->df = setalloc(bbinfo->size);
 529563                 bb->dfchildren = setalloc(bbinfo->size);
 530564         }
 531565 
 532566         dfsnum = 0;
 533567         cfg_dfs(DLIST_NEXT(&bblocks, bbelem), 0, bbinfo);
 534568 
 535569         if (b2debug) {
 536570                 struct basicblock *bbb;
 537571                 struct cfgnode *ccnode;
 538572 
 539573                 DLIST_FOREACH(bbb, &bblocks, bbelem) {
 540574                         printf("Basic block %d, parents: ", bbb->dfnum);
 541575                         SLIST_FOREACH(ccnode, &bbb->parents, cfgelem) {
 542576                                 printf("%d, ", ccnode->bblock->dfnum);
 543577                         }
 544578                         printf("\nChildren: ");
 545579                         SLIST_FOREACH(ccnode, &bbb->children, cfgelem) {
 546580                                 printf("%d, ", ccnode->bblock->dfnum);
 547581                         }
 548582                         printf("\n");
 549583                 }
 550584         }
 551585 
 552586         for(h = bbinfo->size - 1; h > 1; h--) {
 553587                 bb = bbinfo->arr[h];
 554588                 p = s = bbinfo->arr[bb->dfparent];
 555589                 SLIST_FOREACH(cnode, &bb->parents, cfgelem) {
 556590                         if (cnode->bblock->dfnum <= bb->dfnum)
 557591                                 sprime = cnode->bblock;
 558592                         else
 559593                                 sprime = bbinfo->arr[ancestorwithlowestsemi
 560594                                               (cnode->bblock, bbinfo)->semi];
 561595                         if (sprime->dfnum < s->dfnum)
 562596                                 s = sprime;
 563597                 }
 564598                 bb->semi = s->dfnum;
 565599                 BITSET(s->bucket, bb->dfnum);
 566600                 link(p, bb);
 567601                 for (i = 1; i < bbinfo->size; i++) {
 568602                         if(TESTBIT(p->bucket, i)) {
 569603                                 v = bbinfo->arr[i];
 570604                                 y = ancestorwithlowestsemi(v, bbinfo);
 571605                                 if (y->semi == v->semi)
 572606                                         v->idom = p->dfnum;
 573607                                 else
 574608                                         v->samedom = y->dfnum;
 575609                         }
 576610                 }
 577611                 memset(p->bucket, 0, (bbinfo->size + 7)/8);
 578612         }
 579613 
 580614         if (b2debug) {
 581615                 printf("Num\tSemi\tAncest\tidom\n");
 582616                 DLIST_FOREACH(bb, &bblocks, bbelem) {
 583617                         printf("%d\t%d\t%d\t%d\n", bb->dfnum, bb->semi,
 584618                             bb->ancestor, bb->idom);
 585619                 }
 586620         }
 587621 
 588622         for(h = 2; h < bbinfo->size; h++) {
 589623                 bb = bbinfo->arr[h];
 590624                 if (bb->samedom != 0) {
 591625                         bb->idom = bbinfo->arr[bb->samedom]->idom;
 592626                 }
 593627         }
 594628         DLIST_FOREACH(bb, &bblocks, bbelem) {
 595629                 if (bb->idom != 0 && bb->idom != bb->dfnum) {
 596630                         BDEBUG(("Setting child %d of %d\n",
 597631                             bb->dfnum, bbinfo->arr[bb->idom]->dfnum));
 598632                         BITSET(bbinfo->arr[bb->idom]->dfchildren, bb->dfnum);
 599633                 }
 600634         }
 601635 }
 602636 
 603637 
 604638 struct basicblock *
 605639 ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo)
 606640 {
 607641         struct basicblock *u = bblock;
 608642         struct basicblock *v = bblock;
 609643 
 610644         while (v->ancestor != 0) {
 611645                 if (bbinfo->arr[v->semi]->dfnum <
 612646                     bbinfo->arr[u->semi]->dfnum)
 613647                         u = v;
 614648                 v = bbinfo->arr[v->ancestor];
 615649         }
 616650         return u;
 617651 }
 618652 
 619653 void
 620654 link(struct basicblock *parent, struct basicblock *child)
 621655 {
 622656         child->ancestor = parent->dfnum;
 623657 }
 624658 
 625659 void
 626660 computeDF(struct basicblock *bblock, struct bblockinfo *bbinfo)
 627661 {
 628662         struct cfgnode *cnode;
 629663         int h, i;
 630664         
 631665         SLIST_FOREACH(cnode, &bblock->children, cfgelem) {
 632666                 if (cnode->bblock->idom != bblock->dfnum)
 633667                         BITSET(bblock->df, cnode->bblock->dfnum);
 634668         }
 635669         for (h = 1; h < bbinfo->size; h++) {
 636670                 if (!TESTBIT(bblock->dfchildren, h))
 637671                         continue;
 638672                 computeDF(bbinfo->arr[h], bbinfo);
 639673                 for (i = 1; i < bbinfo->size; i++) {
 640674                         if (TESTBIT(bbinfo->arr[h]->df, i) &&
 641675                             (bbinfo->arr[h] == bblock ||
 642676                              (bblock->idom != bbinfo->arr[h]->dfnum)))
 643677                             BITSET(bblock->df, i);
 644678                 }
 645679         }
 646680 }
 647681 
 648682 static struct basicblock *currbb;
 649683 static struct interpass *currip;
 650684 
 651685 /* Helper function for findTemps, Find assignment nodes. */
 652686 static void
 653687 searchasg(NODE *p)
 654688 {
 655689         struct pvarinfo *pv;
 656690 
 657691         if (p->n_op != ASSIGN)
 658692                 return;
 659693 
 660694         if (p->n_left->n_op != TEMP)
 661695                 return;
 662696 
 663697         pv = tmpcalloc(sizeof(struct pvarinfo));
 664698         pv->next = defsites.arr[p->n_left->n_lval];
 665699         pv->bb = currbb;
 666700         pv->top = currip->ip_node;
 667701         pv->n = p->n_left;
 668702         BITSET(currbb->Aorig, p->n_left->n_lval);
 669703 
 670704         defsites.arr[p->n_left->n_lval] = pv;
 671705 }
 672706 
 673707 /* Walk the interpass looking for assignment nodes. */
 674708 void findTemps(struct interpass *ip)
 675709 {
 676710         if (ip->type != IP_NODE)
 677711                 return;
 678712 
 679713         currip = ip;
 680714 
 681715         walkf(ip->ip_node, searchasg);
 682716 }
 683717 
 684718 /*
 685719  * Algorithm 19.6 from Appel.
 686720  */
 687721 
 688722 void
 689723 placePhiFunctions(struct bblockinfo *bbinfo)
 690724 {
 691725         struct basicblock *bb;
 692726         struct interpass *ip;
 693727         int maxtmp, i, j, k, l;
 694728         struct pvarinfo *n;
 695729         struct cfgnode *cnode;
 696730         TWORD ntype;
 697731         NODE *p;
 698732         struct pvarinfo *pv;
 699733 
 700734         bb = DLIST_NEXT(&bblocks, bbelem);
 701735         defsites.low = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
 702736         bb = DLIST_PREV(&bblocks, bbelem);
 703737         maxtmp = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
 704738         defsites.size = maxtmp - defsites.low + 1;
 705739         defsites.arr = tmpcalloc(defsites.size*sizeof(struct pvarinfo *));
 706740 
 707741         /* Find all defsites */
 708742         DLIST_FOREACH(bb, &bblocks, bbelem) {
 709743                 currbb = bb;
 710744                 ip = bb->first;
 711745                 bb->Aorig = setalloc(defsites.size);
 712746                 bb->Aphi = setalloc(defsites.size);
 713747                 
 714748 
 715749                 while (ip != bb->last) {
 716750                         findTemps(ip);
 717751                         ip = DLIST_NEXT(ip, qelem);
 718752                 }
 719753                 /* Make sure we get the last statement in the bblock */
 720754                 findTemps(ip);
 721755         }
 722756         /* For each variable */
 723757         for (i = defsites.low; i < defsites.size; i++) {
 724758                 /* While W not empty */
 725759                 while (defsites.arr[i] != NULL) {
 726760                         /* Remove some node n from W */
 727761                         n = defsites.arr[i];
 728762                         defsites.arr[i] = n->next;
 729763                         /* For each y in n->bb->df */
 730764                         for (j = 0; j < bbinfo->size; j++) {
 731765                                 if (!TESTBIT(n->bb->df, j))
 732766                                         continue;
 733767                                 
 734768                                 if (TESTBIT(bbinfo->arr[j]->Aphi, i))
 735769                                         continue;
 736770 
 737771                                 ntype = n->n->n_type;
 738772                                 k = 0;
 739773                                 /* Amount of predecessors for y */
 740774                                 SLIST_FOREACH(cnode, &n->bb->parents, cfgelem)
 741775                                         k++;
 742776                                 /* Construct phi(...) */
 743777                                 p = mklnode(TEMP, i, 0, ntype);
 744778                                 for (l = 0; l < k-1; l++)
 745779                                         p = mkbinode(PHI, p,
 746780                                             mklnode(TEMP, i, 0, ntype), ntype);
 747781                                 ip = ipnode(mkbinode(ASSIGN,
 748782                                     mklnode(TEMP, i, 0, ntype), p, ntype));
 749783                                 /* Insert phi at top of basic block */
 750784                                 DLIST_INSERT_BEFORE(((struct interpass*)&n->bb->first), ip, qelem);
 751785                                 n->bb->first = ip;
 752786                                 BITSET(bbinfo->arr[j]->Aphi, i);
 753787                                 if (!TESTBIT(bbinfo->arr[j]->Aorig, i)) {
 754788                                         pv = tmpalloc(sizeof(struct pvarinfo));
 755789                                         // XXXpj Ej fullständig information.
 756790                                         pv->bb = bbinfo->arr[j];
 757791                                         pv->next = defsites.arr[i]->next;
 758792                                         defsites.arr[i] = pv;
 759793                                 }
 760794                                         
 761795 
 762796                         }
 763797                 }
 764798         }
 765799 }
 766800 
 767801 /*
 768802  * Remove unreachable nodes in the CFG.
 769803  */
 770804 
 771805 void
 772806 remunreach(void)
 773807 {
 774808         struct basicblock *bb, *nbb;
 775809         struct interpass *next, *ctree;
 776810 
 777811         bb = DLIST_NEXT(&bblocks, bbelem);
 778812         while (bb != &bblocks) {
 779813                 nbb = DLIST_NEXT(bb, bbelem);
 780814 
 781815                 /* Code with dfnum 0 is unreachable */
 782816                 if (bb->dfnum != 0) {
 783817                         bb = nbb;
 784818                         continue;
 785819                 }
 786820 
 787821                 /* Need the epilogue node for other parts of the
 788822                    compiler, set its label to 0 and backend will
 789823                    handle it. */
 790824                 if (bb->first->type == IP_EPILOG) {
 791825                         bb->first->ip_lbl = 0;
 792826                         bb = nbb;
 793827                         continue;
 794828                 }
 795829 
 796830                 next = bb->first;
 797831                 do {
 798832                         ctree = next;
 799833                         next = DLIST_NEXT(ctree, qelem);
 800834                         
 801835                         if (ctree->type == IP_NODE)
 802836                                 tfree(ctree->ip_node);
 803837                         DLIST_REMOVE(ctree, qelem);
 804838                 } while (ctree != bb->last);
 805839                         
 806840                 DLIST_REMOVE(bb, bbelem);
 807841                 bb = nbb;
 808842         }
 809843 }
 810844 
 811845 void
 812846 printip(struct interpass *pole)
 813847 {
 814848         static char *foo[] = {
 815849            0, "NODE", "PROLOG", "STKOFF", "EPILOG", "DEFLAB", "DEFNAM", "ASM" };
 816850         struct interpass *ip;
 817851         struct interpass_prolog *ipp, *epp;
 818852 
 819853         DLIST_FOREACH(ip, pole, qelem) {
 820854                 if (ip->type > MAXIP)
 821855                         printf("IP(%d) (%p): ", ip->type, ip);
 822856                 else
 823857                         printf("%s (%p): ", foo[ip->type], ip);
 824858                 switch (ip->type) {
 825859                 case IP_NODE: printf("\n");
 826860                         fwalk(ip->ip_node, e2print, 0); break;
 827861                 case IP_PROLOG:
 828862                         ipp = (struct interpass_prolog *)ip;
 829863                         printf("%s %s regs %x autos %d mintemp %d minlbl %d\n",
 830864                             ipp->ipp_name, ipp->ipp_vis ? "(local)" : "",
 831865                             ipp->ipp_regs, ipp->ipp_autos, ipp->ip_tmpnum,
 832866                             ipp->ip_lblnum);
 833867                         break;
 834868                 case IP_EPILOG:
 835869                         epp = (struct interpass_prolog *)ip;
 836870                         printf("%s %s regs %x autos %d mintemp %d minlbl %d\n",
 837871                             epp->ipp_name, epp->ipp_vis ? "(local)" : "",
 838872                             epp->ipp_regs, epp->ipp_autos, epp->ip_tmpnum,
 839873                             epp->ip_lblnum);
 840874                         break;
 841875                 case IP_DEFLAB: printf(LABFMT "\n", ip->ip_lbl); break;
 842876                 case IP_DEFNAM: printf("\n"); break;
 843877                 case IP_ASM: printf("%s\n", ip->ip_asm); break;
 844878                 default:
 845879                         break;
 846880                 }
 847881         }
 848882 }
FishEye: Open Source License registered to PCC.
Your maintenance has expired. You can renew your license at http://www.atlassian.com/fisheye/renew
Atlassian FishEye, CVS analysis. (Version:1.6.3 Build:build-336 2008-11-04) - Administration - Page generated 2014-09-24 04:28 +0200