Quick Search:

Mode

Context

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

Other Diffs

Ignore

Blank Lines Whitespace: Expand:

Diff

1.30
 
1.31
 
MAIN:ragge:20050701181741
 
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 static struct basicblock bblocks;
 7171 
 7272 void
 7373 saveip(struct interpass *ip)
 7474 {
 7575         static int inftn;
 7676 
 7777 #if 0
 7878         int regs;
 7979 #endif
 8080         struct labelinfo labinfo;
 8181         struct bblockinfo bbinfo;
 8282 
 8383         if (ip->type == IP_PROLOG) {
 8484                 DLIST_INIT(&ipole, qelem);
 8585                 inftn = 1;
 8686         } else if (inftn == 0)
 8787                 comperr("saveip");
 8888 
 8989         DLIST_INSERT_BEFORE(&ipole, ip, qelem);
 9090 
 9191         if (ip->type != IP_EPILOG)
 9292                 return;
 9393         inftn = 0;
 9494         ipp = (struct interpass_prolog *)DLIST_NEXT(&ipole, qelem);
 9595         epp = (struct interpass_prolog *)ip;
 9696 
 9797         if (b2debug) {
 9898                 printf("initial links\n");
 9999                 printip(&ipole);
 100100         }
 101101 
 102102         if (xdeljumps)
 103103                 deljumps();     /* Delete redundant jumps and dead code */
 104104 
 105105         if (b2debug) {
 106106                 printf("links after deljumps\n");
 107107                 printip(&ipole);
 108108         }
 109109         if (xssaflag) {
 110110                 DLIST_INIT(&bblocks, bbelem);
 111111                 bblocks_build(&labinfo, &bbinfo);
 112112                 cfg_build(&labinfo);
 113113                 dominators(&bbinfo);
 114114                 computeDF(DLIST_NEXT(&bblocks, bbelem), &bbinfo);
 115115                 remunreach();
 116116 #if 0
 117117                 dfg = dfg_build(cfg);
 118118                 ssa = ssa_build(cfg, dfg);
 119119 #endif
 120120         }
 121121 
 122122 #ifdef PCC_DEBUG
 123123         if (epp->ipp_regs != MAXRVAR)
 124124                 comperr("register error");
 125125 #endif
 126126 
 127127         ipp->ipp_autos = epp->ipp_autos;
 128128         ipp->ipp_regs = epp->ipp_regs; // = regs;
 129129 
 130130 #ifdef MYOPTIM
 131131         myoptim((struct interpass *)ipp);
 132132 #endif
 133133 
 134134 if (xnewreg == 0) {
 135135         int tmpautooff;
 136136         NODE *p;
 137137 
 138138         p2autooff = p2maxautooff = AUTOINIT;
 139139         /* Must verify stack usage first */
 140140         DLIST_FOREACH(ip, &ipole, qelem) {
 141141                 if (ip->type == IP_STKOFF) {
 142142                         p2autooff = ip->ip_off;
 143143                         if (p2autooff > p2maxautooff)
 144144                                 p2maxautooff = p2autooff;
 145145                 }
 146146         }
 147147         p2autooff = p2maxautooff; /* don't have live range analysis yet */
 148148 
 149149         DLIST_FOREACH(ip, &ipole, qelem) {
 150150                 if (ip->type == IPSTK) {
 151151                         struct interpass *ip3;
 152152                         p2autooff = ip->ip_off;
 153153                         ip3 = ip;
 154154                         ip = DLIST_NEXT(ip, qelem);
 155155                         DLIST_REMOVE(ip3, qelem);
 156156                 }
 157157                         
 158158                 if (ip->type != IP_NODE)
 159159                         continue;
 160160 
 161161                 p = ip->ip_node;
 162162                 walkf(p, deltemp);
 163163 
 164164                 tmpautooff = p2autooff;
 165165 
 166166                 geninsn(p, FOREFF);
 167167                 if (sucomp(p) < 0) {
 168168                         /* Create STKOFF entry */
 169169                         struct interpass *ip3;
 170170                         DLIST_INSERT_BEFORE(ip, storesave, qelem);
 171171                         ip3 = ipnode(NULL);
 172172                         ip3->type = IPSTK;
 173173                         ip3->ip_off = tmpautooff;
 174174                         DLIST_INSERT_AFTER(ip, ip3, qelem);
 175175                         ip = DLIST_PREV(storesave, qelem);
 176176                         continue;
 177177                 }
 178178 
 179179                 p2autooff = tmpautooff;
 180180 
 181181                 genregs(p);
 182182                 mygenregs(p);
 183183         }
 184184 
 185185 } else {
 186186         /*
 187187          * Loop over instruction assignment until the register assignment
 188188          * code is satisfied.
 189189          */
 190190 #if 0
 191191         extern int tempmin, tempmax;
 192192 
 193193         tempmin = ip->ip_tmpnum;
 194194         tempmin = ie->ip_tmpnum;
 195195 #endif
 196196         do {
 197197                 /* do instruction assignment */
 198198                 DLIST_FOREACH(ip, &ipole, qelem) {
 199199                         if (ip->type != IP_NODE)
 200200                                 continue;
 201201                         geninsn(ip->ip_node, FOREFF);
 202202                         nsucomp(ip->ip_node);
 203203                 }
 204204         } while (ngenregs(&ipole));
 205205 }
 206206 
 207207         DLIST_FOREACH(ip, &ipole, qelem) {
 208208                 emit(ip);
 209209         }
 210210         DLIST_INIT(&ipole, qelem);
 211211 }
 212212 
 213213 /*
 214214  * Delete unused labels, excess of labels, gotos to gotos.
 215215  * This routine can be made much more efficient.
 216216  */
 217217 void
 218218 deljumps()
 219219 {
 220220         struct interpass *ip, *n, *ip2;
 221221         int gotone,low, high;
 222222         int *lblary, sz, o, i;
 223223 
 224224         low = ipp->ip_lblnum;
 225225         high = epp->ip_lblnum;
 226226 
 227227 #ifdef notyet
 228228         mark = tmpmark(); /* temporary used memory */
 229229 #endif
 230230 
 231231         sz = (high-low) * sizeof(int);
 232232         lblary = tmpalloc(sz);
 233233 
 234234 again:  gotone = 0;
 235235         memset(lblary, 0, sz);
 236236 
 237237         /* refcount and coalesce  all labels */
 238238         DLIST_FOREACH(ip, &ipole, qelem) {
 239239                 if (ip->type == IP_DEFLAB) {
 240240                         n = DLIST_NEXT(ip, qelem);
 241241                         while (n->type == IP_DEFLAB || n->type == IP_STKOFF) {
 242242                                 if (n->type == IP_DEFLAB &&
 243243                                     lblary[n->ip_lbl-low] >= 0)
 244244                                         lblary[n->ip_lbl-low] = -ip->ip_lbl;
 245245                                 n = DLIST_NEXT(n, qelem);
 246246                         }
 247247                 }
 248248                 if (ip->type != IP_NODE)
 249249                         continue;
 250250                 o = ip->ip_node->n_op;
 251251                 if (o == GOTO)
 252252                         i = ip->ip_node->n_left->n_lval;
 253253                 else if (o == CBRANCH)
 254254                         i = ip->ip_node->n_right->n_lval;
 255255                 else
 256256                         continue;
 257257                 lblary[i-low] |= 1;
 258258         }
 259259 
 260260         /* delete coalesced/unused labels and rename gotos */
 261261         DLIST_FOREACH(ip, &ipole, qelem) {
 262262                 n = DLIST_NEXT(ip, qelem);
 263263                 if (n->type == IP_DEFLAB) {
 264264                         if (lblary[n->ip_lbl-low] <= 0) {
 265265                                 DLIST_REMOVE(n, qelem);
 266266                                 gotone = 1;
 267267                         }
 268268                         continue;
 269269                 }
 270270                 if (n->type != IP_NODE)
 271271                         continue;
 272272                 o = n->ip_node->n_op;
 273273                 if (o == GOTO)
 274274                         i = n->ip_node->n_left->n_lval;
 275275                 else if (o == CBRANCH)
 276276                         i = n->ip_node->n_right->n_lval;
 277277                 else
 278278                         continue;
 279279                 if (lblary[i-low] < 0) {
 280280                         if (o == GOTO)
 281281                                 n->ip_node->n_left->n_lval = -lblary[i-low];
 282282                         else
 283283                                 n->ip_node->n_right->n_lval = -lblary[i-low];
 284284                 }
 285285         }
 286286 
 287287         /* Delete gotos to the next statement */
 288288         DLIST_FOREACH(ip, &ipole, qelem) {
 289289                 n = DLIST_NEXT(ip, qelem);
 290290                 if (n->type != IP_NODE)
 291291                         continue;
 292292                 o = n->ip_node->n_op;
 293293                 if (o == GOTO)
 294294                         i = n->ip_node->n_left->n_lval;
 295295                 else if (o == CBRANCH)
 296296                         i = n->ip_node->n_right->n_lval;
 297297                 else
 298298                         continue;
 299299                 ip2 = DLIST_NEXT(n, qelem);
 300300                 if (ip2->type != IP_DEFLAB)
 301301                         continue;
 302302                 if (ip2->ip_lbl == i) {
 303303                         tfree(n->ip_node);
 304304                         DLIST_REMOVE(n, qelem);
 305305                         gotone = 1;
 306306                 }
 307307         }
 308308 
 309309         if (gotone)
 310310                 goto again;
 311311 
 312312 #ifdef notyet
 313313         tmpfree(mark);
 314314 #endif
 315315 }
 316316 
 317317 void
 318318 optdump(struct interpass *ip)
 319319 {
 320320         static char *nm[] = { "node", "prolog", "newblk", "epilog", "locctr",
 321321                 "deflab", "defnam", "asm" };
 322322         printf("type %s\n", nm[ip->type-1]);
 323323         switch (ip->type) {
 324324         case IP_NODE:
 325325                 fwalk(ip->ip_node, e2print, 0);
 326326                 break;
 327327         case IP_DEFLAB:
 328328                 printf("label " LABFMT "\n", ip->ip_lbl);
 329329                 break;
 330330         case IP_ASM:
 331331                 printf(": %s\n", ip->ip_asm);
 332332                 break;
 333333         }
 334334 }
 335335 
 336336 /*
 337337  * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
 338338  *
 339339  * Also fills the labelinfo struct with information about which bblocks
 340340  * that contain which label.
 341341  */
 342342 
 343343 void
 344344 bblocks_build(struct labelinfo *labinfo, struct bblockinfo *bbinfo)
 345345 {
 346346         struct interpass *ip;
 347347         struct basicblock *bb = NULL;
<>348 -        int leader = 1;
  348+//      int leader = 1;
349349         int low, high;
 350350         int count = 0;
 351351         int i;
 352352 
 353353         BDEBUG(("bblocks_build (%p, %p)\n", labinfo, bbinfo));
 354354         low = ipp->ip_lblnum;
 355355         high = epp->ip_lblnum;
 356356 
 357357         /*
 358358          * First statement is a leader.
 359359          * Any statement that is target of a jump is a leader.
 360360          * Any statement that immediately follows a jump is a leader.
 361361          */
<>362 -
363362         DLIST_FOREACH(ip, &ipole, qelem) {
<> 363+                if (bb == NULL || (ip->type == IP_EPILOG) ||
  364+                    (ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) {
  365+                        bb = tmpalloc(sizeof(struct basicblock));
  366+                        bb->first = ip;
  367+                        SLIST_INIT(&bb->children);
  368+                        SLIST_INIT(&bb->parents);
  369+                        bb->dfnum = 0;
  370+                        bb->dfparent = 0;
  371+                        bb->semi = 0;
  372+                        bb->ancestor = 0;
  373+                        bb->idom = 0;
  374+                        bb->samedom = 0;
  375+                        bb->bucket = NULL;
  376+                        bb->df = NULL;
  377+                        bb->dfchildren = NULL;
  378+                        bb->Aorig = NULL;
  379+                        bb->Aphi = NULL;
  380+                        DLIST_INSERT_BEFORE(&bblocks, bb, bbelem);
  381+                        count++;
  382+                }
  383+                bb->last = ip;
  384+                if ((ip->type == IP_NODE) && (ip->ip_node->n_op == GOTO ||
  385+                    ip->ip_node->n_op == CBRANCH))
  386+                        bb = NULL;
  387+                if (ip->type == IP_PROLOG)
  388+                        bb = NULL;
  389+        }
  390+#if 0
  391+        DLIST_FOREACH(ip, &ipole, qelem) {
364392                 /* Garbage, skip it */
 365393                 if (leader) {
 366394                         bb = tmpalloc(sizeof(struct basicblock));
 367395                         bb->first = bb->last = ip;
 368396                         SLIST_INIT(&bb->children);
 369397                         SLIST_INIT(&bb->parents);
 370398                         bb->dfnum = 0;
 371399                         bb->dfparent = 0;
 372400                         bb->semi = 0;
 373401                         bb->ancestor = 0;
 374402                         bb->idom = 0;
 375403                         bb->samedom = 0;
 376404                         bb->bucket = NULL;
 377405                         bb->df = NULL;
 378406                         bb->dfchildren = NULL;
 379407                         bb->Aorig = NULL;
 380408                         bb->Aphi = NULL;
 381409                         DLIST_INSERT_BEFORE(&bblocks, bb, bbelem);
 382410                         leader = 0;
 383411                         count++;
 384412                 }
 385413                 
 386414                 /* Prologue and epilogue in their own bblock */
 387415                 if ((ip->type == IP_PROLOG) || (ip->type == IP_EPILOG)) {
 388416                         bb->last = ip;
<>389 -                        if (ip->type == IP_EPILOG)
 390 -                                high = MAX(ip->ip_lbl, high);
391417                         leader = 1;
 392418                         continue;
 393419                 }
 394420                 
 395421                 /* Make sure each label is in a unique bblock */
 396422                 if (((ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) &&
 397423                     bb->first != ip) {
 398424                         bb = tmpalloc(sizeof(struct basicblock));
 399425                         bb->first = bb->last = ip;
 400426                         SLIST_INIT(&bb->children);
 401427                         SLIST_INIT(&bb->parents);
 402428                         bb->dfnum = 0;
 403429                         bb->dfparent = 0;
 404430                         bb->semi = 0;
 405431                         bb->ancestor = 0;
 406432                         bb->idom = 0;
 407433                         bb->samedom = 0;
 408434                         bb->bucket = NULL;
 409435                         bb->df = NULL;
 410436                         bb->dfchildren = NULL;
 411437                         bb->Aorig = NULL;
 412438                         bb->Aphi = NULL;
 413439                         DLIST_INSERT_BEFORE(&bblocks, bb, bbelem);
 414440                         count++;
 415441                         continue;
 416442                 }
 417443 
 418444                 if (ip->type == IP_NODE) {
 419445                         switch(ip->ip_node->n_op) {
 420446                         case CBRANCH:
 421447                         case GOTO:
 422448                         case RETURN:
 423449                                 /* Jumps, last in bblock. */
 424450                                 leader = 1;
 425451                                 break;
 426452 
 427453                         case NAME:
 428454                         case ICON:
 429455                         case FCON:
 430456                         case REG:
 431457                         case OREG:
 432458                         case MOVE:
 433459                         case PLUS:
 434460                         case MINUS:
 435461                         case DIV:
 436462                         case MOD:
 437463                         case MUL:
 438464                         case AND:
 439465                         case OR:
 440466                         case ER:
 441467                         case LS:
 442468                         case COMPL:
 443469                         case INCR:
 444470                         case DECR:
 445471                         case UMUL:
 446472                         case UMINUS:
 447473                         case EQ:
 448474                         case NE:
 449475                         case LE:
 450476                         case GE:
 451477                         case GT:
 452478                         case ULE:
 453479                         case ULT:
 454480                         case UGE:
 455481                         case UGT:
 456482                         case ASSIGN:
 457483                         case FORCE:
 458484                         case FUNARG:
 459485                         case CALL:
 460486                         case UCALL:
 461487                         case FORTCALL:
 462488                         case UFORTCALL:
 463489                         case STCALL:
 464490                         case USTCALL:
 465491                                 /* Not jumps, continue with bblock. */
 466492                                 break;
 467493 
 468494                         default:
 469495                                 comperr("optim2:bblocks_build() %d",ip->ip_node->n_op );
 470496                                 break;
 471497                         }
 472498                 }
 473499 
 474500                 bb->last = ip;
 475501         }
<> 502+#endif
476503 
<>477 -        BDEBUG(("Basic blocks in func: %d\n", count));
 478 -        BDEBUG(("Label range in func: %d\n", high - low + 1));
  504+        if (b2debug) {
  505+                printf("Basic blocks in func: %d\n", count);
  506+                DLIST_FOREACH(bb, &bblocks, bbelem) {
  507+                        printf("bb %p: first %p last %p\n", bb,
  508+                            bb->first, bb->last);
  509+                }
  510+        }
479511 
<>480 -
481512         labinfo->low = low;
 482513         labinfo->size = high - low + 1;
 483514         labinfo->arr = tmpalloc(labinfo->size * sizeof(struct basicblock *));
 484515         for (i = 0; i <= labinfo->size; i++) {
 485516                 labinfo->arr[i] = NULL;
 486517         }
 487518         
 488519         bbinfo->size = count + 1;
 489520         bbinfo->arr = tmpalloc(bbinfo->size * sizeof(struct basicblock *));
 490521         for (i = 0; i <= bbinfo->size; i++) {
 491522                 bbinfo->arr[i] = NULL;
 492523         }
 493524 
 494525         DLIST_FOREACH(bb, &bblocks, bbelem) {
 495526                 /* Build the label table */
 496527                 if (bb->first->type == IP_DEFLAB) {
 497528                         labinfo->arr[bb->first->ip_lbl - low] = bb;
 498529                 }
 499530                 if (bb->first->type == IP_EPILOG) {
 500531                         labinfo->arr[bb->first->ip_lbl - low] = bb;
 501532                 }
 502533         }
 503534 }
 504535 
 505536 /*
 506537  * Build the control flow graph.
 507538  */
 508539 
 509540 void
 510541 cfg_build(struct labelinfo *labinfo)
 511542 {
 512543         /* Child and parent nodes */
 513544         struct cfgnode *cnode;
 514545         struct cfgnode *pnode;
 515546         struct basicblock *bb;
 516547         
 517548         DLIST_FOREACH(bb, &bblocks, bbelem) {
 518549 
<> 550+printf("bb: %p\n", bb);
<_519551                 if (bb->first->type == IP_EPILOG) {
 520552                         break;
 521553                 }
 522554 
 523555                 cnode = tmpalloc(sizeof(struct cfgnode));
 524556                 pnode = tmpalloc(sizeof(struct cfgnode));
 525557                 pnode->bblock = bb;
 526558 
 527559                 if ((bb->last->type == IP_NODE) &&
 528560                     (bb->last->ip_node->n_op == GOTO)) {
 529561                         if (bb->last->ip_node->n_left->n_lval - labinfo->low >
 530562                             labinfo->size) {
 531563                                 comperr("Label out of range: %d, base %d",
 532564                                         bb->last->ip_node->n_left->n_lval,
 533565                                         labinfo->low);
 534566                         }
 535567                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_left->n_lval - labinfo->low];
 536568                         SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 537569                         SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 538570                         continue;
 539571                 }
 540572                 if ((bb->last->type == IP_NODE) &&
 541573                     (bb->last->ip_node->n_op == CBRANCH)) {
 542574                         if (bb->last->ip_node->n_right->n_lval - labinfo->low >
 543575                             labinfo->size)
 544576                                 comperr("Label out of range: %d",
 545577                                         bb->last->ip_node->n_left->n_lval);
 546578                         
 547579                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_right->n_lval - labinfo->low];
 548580                         SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 549581                         SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 550582                         cnode = tmpalloc(sizeof(struct cfgnode));
 551583                         pnode = tmpalloc(sizeof(struct cfgnode));
 552584                         pnode->bblock = bb;
 553585                 }
 554586 
 555587                 cnode->bblock = DLIST_NEXT(bb, bbelem);
 556588                 SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 557589                 SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 558590         }
 559591 }
 560592 
 561593 void
 562594 cfg_dfs(struct basicblock *bb, unsigned int parent, struct bblockinfo *bbinfo)
 563595 {
 564596         struct cfgnode *cnode;
 565597         
 566598         if (bb->dfnum != 0)
 567599                 return;
 568600 
 569601         bb->dfnum = ++dfsnum;
 570602         bb->dfparent = parent;
 571603         bbinfo->arr[bb->dfnum] = bb;
 572604         SLIST_FOREACH(cnode, &bb->children, cfgelem) {
 573605                 cfg_dfs(cnode->bblock, bb->dfnum, bbinfo);
 574606         }
 575607         /* Don't bring in unreachable nodes in the future */
 576608         bbinfo->size = dfsnum + 1;
 577609 }
 578610 
 579611 static bittype *
 580612 setalloc(int nelem)
 581613 {
 582614         bittype *b;
 583615         int sz = (nelem+NUMBITS-1)/NUMBITS;
 584616 
 585617         b = tmpalloc(sz * sizeof(bittype));
 586618         memset(b, 0, sz * sizeof(bittype));
 587619         return b;
 588620 }
 589621 
 590622 /*
 591623  * Algorithm 19.9, pp 414 from Appel.
 592624  */
 593625 
 594626 void
 595627 dominators(struct bblockinfo *bbinfo)
 596628 {
 597629         struct cfgnode *cnode;
 598630         struct basicblock *bb, *y, *v;
 599631         struct basicblock *s, *sprime, *p;
 600632         int h, i;
 601633 
 602634         DLIST_FOREACH(bb, &bblocks, bbelem) {
 603635                 bb->bucket = setalloc(bbinfo->size);
 604636                 bb->df = setalloc(bbinfo->size);
 605637                 bb->dfchildren = setalloc(bbinfo->size);
 606638         }
 607639 
 608640         dfsnum = 0;
 609641         cfg_dfs(DLIST_NEXT(&bblocks, bbelem), 0, bbinfo);
 610642 
 611643         if (b2debug) {
 612644                 struct basicblock *bbb;
 613645                 struct cfgnode *ccnode;
 614646 
 615647                 DLIST_FOREACH(bbb, &bblocks, bbelem) {
 616648                         printf("Basic block %d, parents: ", bbb->dfnum);
 617649                         SLIST_FOREACH(ccnode, &bbb->parents, cfgelem) {
 618650                                 printf("%d, ", ccnode->bblock->dfnum);
 619651                         }
 620652                         printf("\nChildren: ");
 621653                         SLIST_FOREACH(ccnode, &bbb->children, cfgelem) {
 622654                                 printf("%d, ", ccnode->bblock->dfnum);
 623655                         }
 624656                         printf("\n");
 625657                 }
 626658         }
 627659 
 628660         for(h = bbinfo->size - 1; h > 1; h--) {
 629661                 bb = bbinfo->arr[h];
 630662                 p = s = bbinfo->arr[bb->dfparent];
 631663                 SLIST_FOREACH(cnode, &bb->parents, cfgelem) {
 632664                         if (cnode->bblock->dfnum <= bb->dfnum)
 633665                                 sprime = cnode->bblock;
 634666                         else
 635667                                 sprime = bbinfo->arr[ancestorwithlowestsemi
 636668                                               (cnode->bblock, bbinfo)->semi];
 637669                         if (sprime->dfnum < s->dfnum)
 638670                                 s = sprime;
 639671                 }
 640672                 bb->semi = s->dfnum;
 641673                 BITSET(s->bucket, bb->dfnum);
 642674                 link(p, bb);
 643675                 for (i = 1; i < bbinfo->size; i++) {
 644676                         if(TESTBIT(p->bucket, i)) {
 645677                                 v = bbinfo->arr[i];
 646678                                 y = ancestorwithlowestsemi(v, bbinfo);
 647679                                 if (y->semi == v->semi)
 648680                                         v->idom = p->dfnum;
 649681                                 else
 650682                                         v->samedom = y->dfnum;
 651683                         }
 652684                 }
 653685                 memset(p->bucket, 0, (bbinfo->size + 7)/8);
 654686         }
 655687 
 656688         if (b2debug) {
 657689                 printf("Num\tSemi\tAncest\tidom\n");
 658690                 DLIST_FOREACH(bb, &bblocks, bbelem) {
 659691                         printf("%d\t%d\t%d\t%d\n", bb->dfnum, bb->semi,
 660692                             bb->ancestor, bb->idom);
 661693                 }
 662694         }
 663695 
 664696         for(h = 2; h < bbinfo->size; h++) {
 665697                 bb = bbinfo->arr[h];
 666698                 if (bb->samedom != 0) {
 667699                         bb->idom = bbinfo->arr[bb->samedom]->idom;
 668700                 }
 669701         }
 670702         DLIST_FOREACH(bb, &bblocks, bbelem) {
 671703                 if (bb->idom != 0 && bb->idom != bb->dfnum) {
 672704                         BDEBUG(("Setting child %d of %d\n",
 673705                             bb->dfnum, bbinfo->arr[bb->idom]->dfnum));
 674706                         BITSET(bbinfo->arr[bb->idom]->dfchildren, bb->dfnum);
 675707                 }
 676708         }
 677709 }
 678710 
 679711 
 680712 struct basicblock *
 681713 ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo)
 682714 {
 683715         struct basicblock *u = bblock;
 684716         struct basicblock *v = bblock;
 685717 
 686718         while (v->ancestor != 0) {
 687719                 if (bbinfo->arr[v->semi]->dfnum <
 688720                     bbinfo->arr[u->semi]->dfnum)
 689721                         u = v;
 690722                 v = bbinfo->arr[v->ancestor];
 691723         }
 692724         return u;
 693725 }
 694726 
 695727 void
 696728 link(struct basicblock *parent, struct basicblock *child)
 697729 {
 698730         child->ancestor = parent->dfnum;
 699731 }
 700732 
 701733 void
 702734 computeDF(struct basicblock *bblock, struct bblockinfo *bbinfo)
 703735 {
 704736         struct cfgnode *cnode;
 705737         int h, i;
 706738         
 707739         SLIST_FOREACH(cnode, &bblock->children, cfgelem) {
 708740                 if (cnode->bblock->idom != bblock->dfnum)
 709741                         BITSET(bblock->df, cnode->bblock->dfnum);
 710742         }
 711743         for (h = 1; h < bbinfo->size; h++) {
 712744                 if (!TESTBIT(bblock->dfchildren, h))
 713745                         continue;
 714746                 computeDF(bbinfo->arr[h], bbinfo);
 715747                 for (i = 1; i < bbinfo->size; i++) {
 716748                         if (TESTBIT(bbinfo->arr[h]->df, i) &&
 717749                             (bbinfo->arr[h] == bblock ||
 718750                              (bblock->idom != bbinfo->arr[h]->dfnum)))
 719751                             BITSET(bblock->df, i);
 720752                 }
 721753         }
 722754 }
 723755 
 724756 static struct basicblock *currbb;
 725757 static struct interpass *currip;
 726758 
 727759 /* Helper function for findTemps, Find assignment nodes. */
 728760 static void
 729761 findasg(NODE *p)
 730762 {
 731763         struct pvarinfo *pv;
 732764 
 733765         if (p->n_op != ASSIGN)
 734766                 return;
 735767 
 736768         if (p->n_left->n_op != TEMP)
 737769                 return;
 738770 
 739771         pv = tmpcalloc(sizeof(struct pvarinfo));
 740772         pv->next = defsites.arr[p->n_left->n_lval];
 741773         pv->bb = currbb;
 742774         pv->top = currip->ip_node;
 743775         pv->n = p->n_left;
 744776         BITSET(currbb->Aorig, p->n_left->n_lval);
 745777 
 746778         defsites.arr[p->n_left->n_lval] = pv;
 747779 }
 748780 
 749781 /* Walk the interpass looking for assignment nodes. */
 750782 void findTemps(struct interpass *ip)
 751783 {
 752784         if (ip->type != IP_NODE)
 753785                 return;
 754786 
 755787         currip = ip;
 756788 
 757789         walkf(ip->ip_node, findasg);
 758790 }
 759791 
 760792 /*
 761793  * Algorithm 19.6 from Appel.
 762794  */
 763795 
 764796 void
 765797 placePhiFunctions(struct bblockinfo *bbinfo)
 766798 {
 767799         struct basicblock *bb;
 768800         struct interpass *ip;
 769801         int maxtmp, i, j, k, l;
 770802         struct pvarinfo *n;
 771803         struct cfgnode *cnode;
 772804         TWORD ntype;
 773805         NODE *p;
 774806         struct pvarinfo *pv;
 775807 
 776808         bb = DLIST_NEXT(&bblocks, bbelem);
 777809         defsites.low = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
 778810         bb = DLIST_PREV(&bblocks, bbelem);
 779811         maxtmp = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
 780812         defsites.size = maxtmp - defsites.low + 1;
 781813         defsites.arr = tmpcalloc(defsites.size*sizeof(struct pvarinfo *));
 782814 
 783815         /* Find all defsites */
 784816         DLIST_FOREACH(bb, &bblocks, bbelem) {
 785817                 currbb = bb;
 786818                 ip = bb->first;
 787819                 bb->Aorig = setalloc(defsites.size);
 788820                 bb->Aphi = setalloc(defsites.size);
 789821                 
 790822 
 791823                 while (ip != bb->last) {
 792824                         findTemps(ip);
 793825                         ip = DLIST_NEXT(ip, qelem);
 794826                 }
 795827                 /* Make sure we get the last statement in the bblock */
 796828                 findTemps(ip);
 797829         }
 798830         /* For each variable */
 799831         for (i = defsites.low; i < defsites.size; i++) {
 800832                 /* While W not empty */
 801833                 while (defsites.arr[i] != NULL) {
 802834                         /* Remove some node n from W */
 803835                         n = defsites.arr[i];
 804836                         defsites.arr[i] = n->next;
 805837                         /* For each y in n->bb->df */
 806838                         for (j = 0; j < bbinfo->size; j++) {
 807839                                 if (!TESTBIT(n->bb->df, j))
 808840                                         continue;
 809841                                 
 810842                                 if (TESTBIT(bbinfo->arr[j]->Aphi, i))
 811843                                         continue;
 812844 
 813845                                 ntype = n->n->n_type;
 814846                                 k = 0;
 815847                                 /* Amount of predecessors for y */
 816848                                 SLIST_FOREACH(cnode, &n->bb->parents, cfgelem)
 817849                                         k++;
 818850                                 /* Construct phi(...) */
 819851                                 p = mklnode(TEMP, i, 0, ntype);
 820852                                 for (l = 0; l < k-1; l++)
 821853                                         p = mkbinode(PHI, p,
 822854                                             mklnode(TEMP, i, 0, ntype), ntype);
 823855                                 ip = ipnode(mkbinode(ASSIGN,
 824856                                     mklnode(TEMP, i, 0, ntype), p, ntype));
 825857                                 /* Insert phi at top of basic block */
 826858                                 DLIST_INSERT_BEFORE(((struct interpass*)&n->bb->first), ip, qelem);
 827859                                 n->bb->first = ip;
 828860                                 BITSET(bbinfo->arr[j]->Aphi, i);
 829861                                 if (!TESTBIT(bbinfo->arr[j]->Aorig, i)) {
 830862                                         pv = tmpalloc(sizeof(struct pvarinfo));
 831863                                         // XXXpj Ej fullständig information.
 832864                                         pv->bb = bbinfo->arr[j];
 833865                                         pv->next = defsites.arr[i]->next;
 834866                                         defsites.arr[i] = pv;
 835867                                 }
 836868                                         
 837869 
 838870                         }
 839871                 }
 840872         }
 841873 }
 842874 
 843875 /*
 844876  * Remove unreachable nodes in the CFG.
 845877  */
 846878 
 847879 void
 848880 remunreach(void)
 849881 {
 850882         struct basicblock *bb, *nbb;
 851883         struct interpass *next, *ctree;
 852884 
 853885         bb = DLIST_NEXT(&bblocks, bbelem);
 854886         while (bb != &bblocks) {
 855887                 nbb = DLIST_NEXT(bb, bbelem);
 856888 
 857889                 /* Code with dfnum 0 is unreachable */
 858890                 if (bb->dfnum != 0) {
 859891                         bb = nbb;
 860892                         continue;
 861893                 }
 862894 
 863895                 /* Need the epilogue node for other parts of the
 864896                    compiler, set its label to 0 and backend will
 865897                    handle it. */
 866898                 if (bb->first->type == IP_EPILOG) {
 867899                         bb->first->ip_lbl = 0;
 868900                         bb = nbb;
 869901                         continue;
 870902                 }
 871903 
 872904                 next = bb->first;
 873905                 do {
 874906                         ctree = next;
 875907                         next = DLIST_NEXT(ctree, qelem);
 876908                         
 877909                         if (ctree->type == IP_NODE)
 878910                                 tfree(ctree->ip_node);
 879911                         DLIST_REMOVE(ctree, qelem);
 880912                 } while (ctree != bb->last);
 881913                         
 882914                 DLIST_REMOVE(bb, bbelem);
 883915                 bb = nbb;
 884916         }
 885917 }
 886918 
 887919 void
 888920 printip(struct interpass *pole)
 889921 {
 890922         static char *foo[] = {
 891923            0, "NODE", "PROLOG", "STKOFF", "EPILOG", "DEFLAB", "DEFNAM", "ASM" };
 892924         struct interpass *ip;
 893925 
 894926         DLIST_FOREACH(ip, pole, qelem) {
 895927                 if (ip->type > MAXIP)
 896928                         printf("IP(%d) (%p): ", ip->type, ip);
 897929                 else
 898930                         printf("%s (%p): ", foo[ip->type], ip);
 899931                 switch (ip->type) {
 900932                 case IP_NODE: printf("\n");
 901933                         fwalk(ip->ip_node, e2print, 0); break;
 902934                 case IP_PROLOG:
 903935                         printf("%s\n",
 904936                             ((struct interpass_prolog *)ip)->ipp_name); break;
 905937                 case IP_STKOFF: printf("%d\n", ip->ip_off); break;
 906938                 case IP_EPILOG: printf("\n"); break;
 907939                 case IP_DEFLAB: printf(LABFMT "\n", ip->ip_lbl); break;
 908940                 }
 909941         }
 910942 }
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-23 20:26 +0200