Quick Search:

Mode

Context

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

Other Diffs

Ignore

Blank Lines Whitespace: Expand:

Diff

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