Quick Search:

Mode

Context

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

Other Diffs

Ignore

Blank Lines Whitespace: Expand:

Diff

1.31
 
1.32
 
MAIN:ragge:20050721150029
 
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);
<> 112+                BDEBUG(("Calling cfg_build\n"));
112113                 cfg_build(&labinfo);
<> 114+                BDEBUG(("Calling dominators\n"));
113115                 dominators(&bbinfo);
<> 116+                BDEBUG(("Calling computeDF\n"));
114117                 computeDF(DLIST_NEXT(&bblocks, bbelem), &bbinfo);
<> 118+                BDEBUG(("Calling remunreach\n"));
115119                 remunreach();
 116120 #if 0
 117121                 dfg = dfg_build(cfg);
 118122                 ssa = ssa_build(cfg, dfg);
 119123 #endif
 120124         }
 121125 
 122126 #ifdef PCC_DEBUG
 123127         if (epp->ipp_regs != MAXRVAR)
 124128                 comperr("register error");
 125129 #endif
 126130 
 127131         ipp->ipp_autos = epp->ipp_autos;
 128132         ipp->ipp_regs = epp->ipp_regs; // = regs;
 129133 
 130134 #ifdef MYOPTIM
 131135         myoptim((struct interpass *)ipp);
 132136 #endif
 133137 
 134138 if (xnewreg == 0) {
 135139         int tmpautooff;
 136140         NODE *p;
 137141 
 138142         p2autooff = p2maxautooff = AUTOINIT;
 139143         /* Must verify stack usage first */
 140144         DLIST_FOREACH(ip, &ipole, qelem) {
 141145                 if (ip->type == IP_STKOFF) {
 142146                         p2autooff = ip->ip_off;
 143147                         if (p2autooff > p2maxautooff)
 144148                                 p2maxautooff = p2autooff;
 145149                 }
 146150         }
 147151         p2autooff = p2maxautooff; /* don't have live range analysis yet */
 148152 
 149153         DLIST_FOREACH(ip, &ipole, qelem) {
 150154                 if (ip->type == IPSTK) {
 151155                         struct interpass *ip3;
 152156                         p2autooff = ip->ip_off;
 153157                         ip3 = ip;
 154158                         ip = DLIST_NEXT(ip, qelem);
 155159                         DLIST_REMOVE(ip3, qelem);
 156160                 }
 157161                         
 158162                 if (ip->type != IP_NODE)
 159163                         continue;
 160164 
 161165                 p = ip->ip_node;
 162166                 walkf(p, deltemp);
 163167 
 164168                 tmpautooff = p2autooff;
 165169 
 166170                 geninsn(p, FOREFF);
 167171                 if (sucomp(p) < 0) {
 168172                         /* Create STKOFF entry */
 169173                         struct interpass *ip3;
 170174                         DLIST_INSERT_BEFORE(ip, storesave, qelem);
 171175                         ip3 = ipnode(NULL);
 172176                         ip3->type = IPSTK;
 173177                         ip3->ip_off = tmpautooff;
 174178                         DLIST_INSERT_AFTER(ip, ip3, qelem);
 175179                         ip = DLIST_PREV(storesave, qelem);
 176180                         continue;
 177181                 }
 178182 
 179183                 p2autooff = tmpautooff;
 180184 
 181185                 genregs(p);
 182186                 mygenregs(p);
 183187         }
 184188 
 185189 } else {
 186190         /*
 187191          * Loop over instruction assignment until the register assignment
 188192          * code is satisfied.
 189193          */
 190194 #if 0
 191195         extern int tempmin, tempmax;
 192196 
 193197         tempmin = ip->ip_tmpnum;
 194198         tempmin = ie->ip_tmpnum;
 195199 #endif
 196200         do {
 197201                 /* do instruction assignment */
 198202                 DLIST_FOREACH(ip, &ipole, qelem) {
 199203                         if (ip->type != IP_NODE)
 200204                                 continue;
 201205                         geninsn(ip->ip_node, FOREFF);
 202206                         nsucomp(ip->ip_node);
 203207                 }
 204208         } while (ngenregs(&ipole));
 205209 }
 206210 
 207211         DLIST_FOREACH(ip, &ipole, qelem) {
 208212                 emit(ip);
 209213         }
 210214         DLIST_INIT(&ipole, qelem);
 211215 }
 212216 
 213217 /*
 214218  * Delete unused labels, excess of labels, gotos to gotos.
 215219  * This routine can be made much more efficient.
 216220  */
 217221 void
 218222 deljumps()
 219223 {
 220224         struct interpass *ip, *n, *ip2;
 221225         int gotone,low, high;
 222226         int *lblary, sz, o, i;
 223227 
 224228         low = ipp->ip_lblnum;
 225229         high = epp->ip_lblnum;
 226230 
 227231 #ifdef notyet
 228232         mark = tmpmark(); /* temporary used memory */
 229233 #endif
 230234 
 231235         sz = (high-low) * sizeof(int);
 232236         lblary = tmpalloc(sz);
 233237 
 234238 again:  gotone = 0;
 235239         memset(lblary, 0, sz);
 236240 
 237241         /* refcount and coalesce  all labels */
 238242         DLIST_FOREACH(ip, &ipole, qelem) {
 239243                 if (ip->type == IP_DEFLAB) {
 240244                         n = DLIST_NEXT(ip, qelem);
 241245                         while (n->type == IP_DEFLAB || n->type == IP_STKOFF) {
 242246                                 if (n->type == IP_DEFLAB &&
 243247                                     lblary[n->ip_lbl-low] >= 0)
 244248                                         lblary[n->ip_lbl-low] = -ip->ip_lbl;
 245249                                 n = DLIST_NEXT(n, qelem);
 246250                         }
 247251                 }
 248252                 if (ip->type != IP_NODE)
 249253                         continue;
 250254                 o = ip->ip_node->n_op;
 251255                 if (o == GOTO)
 252256                         i = ip->ip_node->n_left->n_lval;
 253257                 else if (o == CBRANCH)
 254258                         i = ip->ip_node->n_right->n_lval;
 255259                 else
 256260                         continue;
 257261                 lblary[i-low] |= 1;
 258262         }
 259263 
 260264         /* delete coalesced/unused labels and rename gotos */
 261265         DLIST_FOREACH(ip, &ipole, qelem) {
 262266                 n = DLIST_NEXT(ip, qelem);
 263267                 if (n->type == IP_DEFLAB) {
 264268                         if (lblary[n->ip_lbl-low] <= 0) {
 265269                                 DLIST_REMOVE(n, qelem);
 266270                                 gotone = 1;
 267271                         }
 268272                         continue;
 269273                 }
 270274                 if (n->type != IP_NODE)
 271275                         continue;
 272276                 o = n->ip_node->n_op;
 273277                 if (o == GOTO)
 274278                         i = n->ip_node->n_left->n_lval;
 275279                 else if (o == CBRANCH)
 276280                         i = n->ip_node->n_right->n_lval;
 277281                 else
 278282                         continue;
 279283                 if (lblary[i-low] < 0) {
 280284                         if (o == GOTO)
 281285                                 n->ip_node->n_left->n_lval = -lblary[i-low];
 282286                         else
 283287                                 n->ip_node->n_right->n_lval = -lblary[i-low];
 284288                 }
 285289         }
 286290 
 287291         /* Delete gotos to the next statement */
 288292         DLIST_FOREACH(ip, &ipole, qelem) {
 289293                 n = DLIST_NEXT(ip, qelem);
 290294                 if (n->type != IP_NODE)
 291295                         continue;
 292296                 o = n->ip_node->n_op;
 293297                 if (o == GOTO)
 294298                         i = n->ip_node->n_left->n_lval;
 295299                 else if (o == CBRANCH)
 296300                         i = n->ip_node->n_right->n_lval;
 297301                 else
 298302                         continue;
 299303                 ip2 = DLIST_NEXT(n, qelem);
 300304                 if (ip2->type != IP_DEFLAB)
 301305                         continue;
 302306                 if (ip2->ip_lbl == i) {
 303307                         tfree(n->ip_node);
 304308                         DLIST_REMOVE(n, qelem);
 305309                         gotone = 1;
 306310                 }
 307311         }
 308312 
 309313         if (gotone)
 310314                 goto again;
 311315 
 312316 #ifdef notyet
 313317         tmpfree(mark);
 314318 #endif
 315319 }
 316320 
 317321 void
 318322 optdump(struct interpass *ip)
 319323 {
 320324         static char *nm[] = { "node", "prolog", "newblk", "epilog", "locctr",
 321325                 "deflab", "defnam", "asm" };
 322326         printf("type %s\n", nm[ip->type-1]);
 323327         switch (ip->type) {
 324328         case IP_NODE:
 325329                 fwalk(ip->ip_node, e2print, 0);
 326330                 break;
 327331         case IP_DEFLAB:
 328332                 printf("label " LABFMT "\n", ip->ip_lbl);
 329333                 break;
 330334         case IP_ASM:
 331335                 printf(": %s\n", ip->ip_asm);
 332336                 break;
 333337         }
 334338 }
 335339 
 336340 /*
 337341  * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
 338342  *
 339343  * Also fills the labelinfo struct with information about which bblocks
 340344  * that contain which label.
 341345  */
 342346 
 343347 void
 344348 bblocks_build(struct labelinfo *labinfo, struct bblockinfo *bbinfo)
 345349 {
 346350         struct interpass *ip;
 347351         struct basicblock *bb = NULL;
<>348 -//      int leader = 1;
349352         int low, high;
 350353         int count = 0;
 351354         int i;
 352355 
 353356         BDEBUG(("bblocks_build (%p, %p)\n", labinfo, bbinfo));
 354357         low = ipp->ip_lblnum;
 355358         high = epp->ip_lblnum;
 356359 
 357360         /*
 358361          * First statement is a leader.
 359362          * Any statement that is target of a jump is a leader.
 360363          * Any statement that immediately follows a jump is a leader.
 361364          */
 362365         DLIST_FOREACH(ip, &ipole, qelem) {
<> 366+                /* ignore stackoff in beginning or end of bblocks */
  367+                if (ip->type == IP_STKOFF && bb == NULL)
  368+                        continue;
  369+
363370                 if (bb == NULL || (ip->type == IP_EPILOG) ||
 364371                     (ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) {
 365372                         bb = tmpalloc(sizeof(struct basicblock));
 366373                         bb->first = ip;
 367374                         SLIST_INIT(&bb->children);
 368375                         SLIST_INIT(&bb->parents);
 369376                         bb->dfnum = 0;
 370377                         bb->dfparent = 0;
 371378                         bb->semi = 0;
 372379                         bb->ancestor = 0;
 373380                         bb->idom = 0;
 374381                         bb->samedom = 0;
 375382                         bb->bucket = NULL;
 376383                         bb->df = NULL;
 377384                         bb->dfchildren = NULL;
 378385                         bb->Aorig = NULL;
 379386                         bb->Aphi = NULL;
 380387                         DLIST_INSERT_BEFORE(&bblocks, bb, bbelem);
 381388                         count++;
 382389                 }
 383390                 bb->last = ip;
 384391                 if ((ip->type == IP_NODE) && (ip->ip_node->n_op == GOTO ||
 385392                     ip->ip_node->n_op == CBRANCH))
 386393                         bb = NULL;
 387394                 if (ip->type == IP_PROLOG)
 388395                         bb = NULL;
 389396         }
<>390 -#if 0
 391 -        DLIST_FOREACH(ip, &ipole, qelem) {
 392 -                /* Garbage, skip it */
 393 -                if (leader) {
 394 -                        bb = tmpalloc(sizeof(struct basicblock));
 395 -                        bb->first = bb->last = ip;
 396 -                        SLIST_INIT(&bb->children);
 397 -                        SLIST_INIT(&bb->parents);
 398 -                        bb->dfnum = 0;
 399 -                        bb->dfparent = 0;
 400 -                        bb->semi = 0;
 401 -                        bb->ancestor = 0;
 402 -                        bb->idom = 0;
 403 -                        bb->samedom = 0;
 404 -                        bb->bucket = NULL;
 405 -                        bb->df = NULL;
 406 -                        bb->dfchildren = NULL;
 407 -                        bb->Aorig = NULL;
 408 -                        bb->Aphi = NULL;
 409 -                        DLIST_INSERT_BEFORE(&bblocks, bb, bbelem);
 410 -                        leader = 0;
 411 -                        count++;
 412 -                }
 413 -                
 414 -                /* Prologue and epilogue in their own bblock */
 415 -                if ((ip->type == IP_PROLOG) || (ip->type == IP_EPILOG)) {
 416 -                        bb->last = ip;
 417 -                        leader = 1;
 418 -                        continue;
 419 -                }
 420 -                
 421 -                /* Make sure each label is in a unique bblock */
 422 -                if (((ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) &&
 423 -                    bb->first != ip) {
 424 -                        bb = tmpalloc(sizeof(struct basicblock));
 425 -                        bb->first = bb->last = ip;
 426 -                        SLIST_INIT(&bb->children);
 427 -                        SLIST_INIT(&bb->parents);
 428 -                        bb->dfnum = 0;
 429 -                        bb->dfparent = 0;
 430 -                        bb->semi = 0;
 431 -                        bb->ancestor = 0;
 432 -                        bb->idom = 0;
 433 -                        bb->samedom = 0;
 434 -                        bb->bucket = NULL;
 435 -                        bb->df = NULL;
 436 -                        bb->dfchildren = NULL;
 437 -                        bb->Aorig = NULL;
 438 -                        bb->Aphi = NULL;
 439 -                        DLIST_INSERT_BEFORE(&bblocks, bb, bbelem);
 440 -                        count++;
 441 -                        continue;
 442 -                }
443397 
<>444 -                if (ip->type == IP_NODE) {
 445 -                        switch(ip->ip_node->n_op) {
 446 -                        case CBRANCH:
 447 -                        case GOTO:
 448 -                        case RETURN:
 449 -                                /* Jumps, last in bblock. */
 450 -                                leader = 1;
 451 -                                break;
 452 -
 453 -                        case NAME:
 454 -                        case ICON:
 455 -                        case FCON:
 456 -                        case REG:
 457 -                        case OREG:
 458 -                        case MOVE:
 459 -                        case PLUS:
 460 -                        case MINUS:
 461 -                        case DIV:
 462 -                        case MOD:
 463 -                        case MUL:
 464 -                        case AND:
 465 -                        case OR:
 466 -                        case ER:
 467 -                        case LS:
 468 -                        case COMPL:
 469 -                        case INCR:
 470 -                        case DECR:
 471 -                        case UMUL:
 472 -                        case UMINUS:
 473 -                        case EQ:
 474 -                        case NE:
 475 -                        case LE:
 476 -                        case GE:
 477 -                        case GT:
 478 -                        case ULE:
 479 -                        case ULT:
 480 -                        case UGE:
 481 -                        case UGT:
 482 -                        case ASSIGN:
 483 -                        case FORCE:
 484 -                        case FUNARG:
 485 -                        case CALL:
 486 -                        case UCALL:
 487 -                        case FORTCALL:
 488 -                        case UFORTCALL:
 489 -                        case STCALL:
 490 -                        case USTCALL:
 491 -                                /* Not jumps, continue with bblock. */
 492 -                                break;
 493 -
 494 -                        default:
 495 -                                comperr("optim2:bblocks_build() %d",ip->ip_node->n_op );
 496 -                                break;
 497 -                        }
 498 -                }
 499 -
 500 -                bb->last = ip;
 501 -        }
 502 -#endif
 503 -
504398         if (b2debug) {
<>505 -                printf("Basic blocks in func: %d\n", count);
  399+                printf("Basic blocks in func: %d, low %d, high %d\n",
  400+                    count, low, high);
506401                 DLIST_FOREACH(bb, &bblocks, bbelem) {
 507402                         printf("bb %p: first %p last %p\n", bb,
 508403                             bb->first, bb->last);
 509404                 }
 510405         }
 511406 
 512407         labinfo->low = low;
 513408         labinfo->size = high - low + 1;
 514409         labinfo->arr = tmpalloc(labinfo->size * sizeof(struct basicblock *));
 515410         for (i = 0; i <= labinfo->size; i++) {
 516411                 labinfo->arr[i] = NULL;
 517412         }
 518413         
 519414         bbinfo->size = count + 1;
 520415         bbinfo->arr = tmpalloc(bbinfo->size * sizeof(struct basicblock *));
 521416         for (i = 0; i <= bbinfo->size; i++) {
 522417                 bbinfo->arr[i] = NULL;
 523418         }
 524419 
<> 420+        /* Build the label table */
525421         DLIST_FOREACH(bb, &bblocks, bbelem) {
<>526 -                /* Build the label table */
 527 -                if (bb->first->type == IP_DEFLAB) {
  422+                if (bb->first->type == IP_DEFLAB)
528423                         labinfo->arr[bb->first->ip_lbl - low] = bb;
<>529 -                }
 530 -                if (bb->first->type == IP_EPILOG) {
 531 -                        labinfo->arr[bb->first->ip_lbl - low] = bb;
 532 -                }
533424         }
<> 425+
  426+        if (b2debug) {
  427+                printf("Label table:\n");
  428+                for (i = 0; i < labinfo->size; i++)
  429+                        if (labinfo->arr[i])
  430+                                printf("Label %d bblock %p\n", i+low,
  431+                                    labinfo->arr[i]);
  432+        }
534433 }
 535434 
 536435 /*
 537436  * Build the control flow graph.
 538437  */
 539438 
 540439 void
 541440 cfg_build(struct labelinfo *labinfo)
 542441 {
 543442         /* Child and parent nodes */
 544443         struct cfgnode *cnode;
 545444         struct cfgnode *pnode;
 546445         struct basicblock *bb;
 547446         
 548447         DLIST_FOREACH(bb, &bblocks, bbelem) {
 549448 
<>550 -printf("bb: %p\n", bb);
<_551449                 if (bb->first->type == IP_EPILOG) {
 552450                         break;
 553451                 }
 554452 
 555453                 cnode = tmpalloc(sizeof(struct cfgnode));
 556454                 pnode = tmpalloc(sizeof(struct cfgnode));
 557455                 pnode->bblock = bb;
 558456 
 559457                 if ((bb->last->type == IP_NODE) &&
 560458                     (bb->last->ip_node->n_op == GOTO)) {
 561459                         if (bb->last->ip_node->n_left->n_lval - labinfo->low >
 562460                             labinfo->size) {
 563461                                 comperr("Label out of range: %d, base %d",
 564462                                         bb->last->ip_node->n_left->n_lval,
 565463                                         labinfo->low);
 566464                         }
 567465                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_left->n_lval - labinfo->low];
 568466                         SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 569467                         SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 570468                         continue;
 571469                 }
 572470                 if ((bb->last->type == IP_NODE) &&
 573471                     (bb->last->ip_node->n_op == CBRANCH)) {
 574472                         if (bb->last->ip_node->n_right->n_lval - labinfo->low >
 575473                             labinfo->size)
 576474                                 comperr("Label out of range: %d",
 577475                                         bb->last->ip_node->n_left->n_lval);
 578476                         
 579477                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_right->n_lval - labinfo->low];
 580478                         SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 581479                         SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 582480                         cnode = tmpalloc(sizeof(struct cfgnode));
 583481                         pnode = tmpalloc(sizeof(struct cfgnode));
 584482                         pnode->bblock = bb;
 585483                 }
 586484 
 587485                 cnode->bblock = DLIST_NEXT(bb, bbelem);
 588486                 SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 589487                 SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 590488         }
 591489 }
 592490 
 593491 void
 594492 cfg_dfs(struct basicblock *bb, unsigned int parent, struct bblockinfo *bbinfo)
 595493 {
 596494         struct cfgnode *cnode;
 597495         
 598496         if (bb->dfnum != 0)
 599497                 return;
 600498 
 601499         bb->dfnum = ++dfsnum;
 602500         bb->dfparent = parent;
 603501         bbinfo->arr[bb->dfnum] = bb;
 604502         SLIST_FOREACH(cnode, &bb->children, cfgelem) {
 605503                 cfg_dfs(cnode->bblock, bb->dfnum, bbinfo);
 606504         }
 607505         /* Don't bring in unreachable nodes in the future */
 608506         bbinfo->size = dfsnum + 1;
 609507 }
 610508 
 611509 static bittype *
 612510 setalloc(int nelem)
 613511 {
 614512         bittype *b;
 615513         int sz = (nelem+NUMBITS-1)/NUMBITS;
 616514 
 617515         b = tmpalloc(sz * sizeof(bittype));
 618516         memset(b, 0, sz * sizeof(bittype));
 619517         return b;
 620518 }
 621519 
 622520 /*
 623521  * Algorithm 19.9, pp 414 from Appel.
 624522  */
 625523 
 626524 void
 627525 dominators(struct bblockinfo *bbinfo)
 628526 {
 629527         struct cfgnode *cnode;
 630528         struct basicblock *bb, *y, *v;
 631529         struct basicblock *s, *sprime, *p;
 632530         int h, i;
 633531 
 634532         DLIST_FOREACH(bb, &bblocks, bbelem) {
 635533                 bb->bucket = setalloc(bbinfo->size);
 636534                 bb->df = setalloc(bbinfo->size);
 637535                 bb->dfchildren = setalloc(bbinfo->size);
 638536         }
 639537 
 640538         dfsnum = 0;
 641539         cfg_dfs(DLIST_NEXT(&bblocks, bbelem), 0, bbinfo);
 642540 
 643541         if (b2debug) {
 644542                 struct basicblock *bbb;
 645543                 struct cfgnode *ccnode;
 646544 
 647545                 DLIST_FOREACH(bbb, &bblocks, bbelem) {
 648546                         printf("Basic block %d, parents: ", bbb->dfnum);
 649547                         SLIST_FOREACH(ccnode, &bbb->parents, cfgelem) {
 650548                                 printf("%d, ", ccnode->bblock->dfnum);
 651549                         }
 652550                         printf("\nChildren: ");
 653551                         SLIST_FOREACH(ccnode, &bbb->children, cfgelem) {
 654552                                 printf("%d, ", ccnode->bblock->dfnum);
 655553                         }
 656554                         printf("\n");
 657555                 }
 658556         }
 659557 
 660558         for(h = bbinfo->size - 1; h > 1; h--) {
 661559                 bb = bbinfo->arr[h];
 662560                 p = s = bbinfo->arr[bb->dfparent];
 663561                 SLIST_FOREACH(cnode, &bb->parents, cfgelem) {
 664562                         if (cnode->bblock->dfnum <= bb->dfnum)
 665563                                 sprime = cnode->bblock;
 666564                         else
 667565                                 sprime = bbinfo->arr[ancestorwithlowestsemi
 668566                                               (cnode->bblock, bbinfo)->semi];
 669567                         if (sprime->dfnum < s->dfnum)
 670568                                 s = sprime;
 671569                 }
 672570                 bb->semi = s->dfnum;
 673571                 BITSET(s->bucket, bb->dfnum);
 674572                 link(p, bb);
 675573                 for (i = 1; i < bbinfo->size; i++) {
 676574                         if(TESTBIT(p->bucket, i)) {
 677575                                 v = bbinfo->arr[i];
 678576                                 y = ancestorwithlowestsemi(v, bbinfo);
 679577                                 if (y->semi == v->semi)
 680578                                         v->idom = p->dfnum;
 681579                                 else
 682580                                         v->samedom = y->dfnum;
 683581                         }
 684582                 }
 685583                 memset(p->bucket, 0, (bbinfo->size + 7)/8);
 686584         }
 687585 
 688586         if (b2debug) {
 689587                 printf("Num\tSemi\tAncest\tidom\n");
 690588                 DLIST_FOREACH(bb, &bblocks, bbelem) {
 691589                         printf("%d\t%d\t%d\t%d\n", bb->dfnum, bb->semi,
 692590                             bb->ancestor, bb->idom);
 693591                 }
 694592         }
 695593 
 696594         for(h = 2; h < bbinfo->size; h++) {
 697595                 bb = bbinfo->arr[h];
 698596                 if (bb->samedom != 0) {
 699597                         bb->idom = bbinfo->arr[bb->samedom]->idom;
 700598                 }
 701599         }
 702600         DLIST_FOREACH(bb, &bblocks, bbelem) {
 703601                 if (bb->idom != 0 && bb->idom != bb->dfnum) {
 704602                         BDEBUG(("Setting child %d of %d\n",
 705603                             bb->dfnum, bbinfo->arr[bb->idom]->dfnum));
 706604                         BITSET(bbinfo->arr[bb->idom]->dfchildren, bb->dfnum);
 707605                 }
 708606         }
 709607 }
 710608 
 711609 
 712610 struct basicblock *
 713611 ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo)
 714612 {
 715613         struct basicblock *u = bblock;
 716614         struct basicblock *v = bblock;
 717615 
 718616         while (v->ancestor != 0) {
 719617                 if (bbinfo->arr[v->semi]->dfnum <
 720618                     bbinfo->arr[u->semi]->dfnum)
 721619                         u = v;
 722620                 v = bbinfo->arr[v->ancestor];
 723621         }
 724622         return u;
 725623 }
 726624 
 727625 void
 728626 link(struct basicblock *parent, struct basicblock *child)
 729627 {
 730628         child->ancestor = parent->dfnum;
 731629 }
 732630 
 733631 void
 734632 computeDF(struct basicblock *bblock, struct bblockinfo *bbinfo)
 735633 {
 736634         struct cfgnode *cnode;
 737635         int h, i;
 738636         
 739637         SLIST_FOREACH(cnode, &bblock->children, cfgelem) {
 740638                 if (cnode->bblock->idom != bblock->dfnum)
 741639                         BITSET(bblock->df, cnode->bblock->dfnum);
 742640         }
 743641         for (h = 1; h < bbinfo->size; h++) {
 744642                 if (!TESTBIT(bblock->dfchildren, h))
 745643                         continue;
 746644                 computeDF(bbinfo->arr[h], bbinfo);
 747645                 for (i = 1; i < bbinfo->size; i++) {
 748646                         if (TESTBIT(bbinfo->arr[h]->df, i) &&
 749647                             (bbinfo->arr[h] == bblock ||
 750648                              (bblock->idom != bbinfo->arr[h]->dfnum)))
 751649                             BITSET(bblock->df, i);
 752650                 }
 753651         }
 754652 }
 755653 
 756654 static struct basicblock *currbb;
 757655 static struct interpass *currip;
 758656 
 759657 /* Helper function for findTemps, Find assignment nodes. */
 760658 static void
 761659 findasg(NODE *p)
 762660 {
 763661         struct pvarinfo *pv;
 764662 
 765663         if (p->n_op != ASSIGN)
 766664                 return;
 767665 
 768666         if (p->n_left->n_op != TEMP)
 769667                 return;
 770668 
 771669         pv = tmpcalloc(sizeof(struct pvarinfo));
 772670         pv->next = defsites.arr[p->n_left->n_lval];
 773671         pv->bb = currbb;
 774672         pv->top = currip->ip_node;
 775673         pv->n = p->n_left;
 776674         BITSET(currbb->Aorig, p->n_left->n_lval);
 777675 
 778676         defsites.arr[p->n_left->n_lval] = pv;
 779677 }
 780678 
 781679 /* Walk the interpass looking for assignment nodes. */
 782680 void findTemps(struct interpass *ip)
 783681 {
 784682         if (ip->type != IP_NODE)
 785683                 return;
 786684 
 787685         currip = ip;
 788686 
 789687         walkf(ip->ip_node, findasg);
 790688 }
 791689 
 792690 /*
 793691  * Algorithm 19.6 from Appel.
 794692  */
 795693 
 796694 void
 797695 placePhiFunctions(struct bblockinfo *bbinfo)
 798696 {
 799697         struct basicblock *bb;
 800698         struct interpass *ip;
 801699         int maxtmp, i, j, k, l;
 802700         struct pvarinfo *n;
 803701         struct cfgnode *cnode;
 804702         TWORD ntype;
 805703         NODE *p;
 806704         struct pvarinfo *pv;
 807705 
 808706         bb = DLIST_NEXT(&bblocks, bbelem);
 809707         defsites.low = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
 810708         bb = DLIST_PREV(&bblocks, bbelem);
 811709         maxtmp = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
 812710         defsites.size = maxtmp - defsites.low + 1;
 813711         defsites.arr = tmpcalloc(defsites.size*sizeof(struct pvarinfo *));
 814712 
 815713         /* Find all defsites */
 816714         DLIST_FOREACH(bb, &bblocks, bbelem) {
 817715                 currbb = bb;
 818716                 ip = bb->first;
 819717                 bb->Aorig = setalloc(defsites.size);
 820718                 bb->Aphi = setalloc(defsites.size);
 821719                 
 822720 
 823721                 while (ip != bb->last) {
 824722                         findTemps(ip);
 825723                         ip = DLIST_NEXT(ip, qelem);
 826724                 }
 827725                 /* Make sure we get the last statement in the bblock */
 828726                 findTemps(ip);
 829727         }
 830728         /* For each variable */
 831729         for (i = defsites.low; i < defsites.size; i++) {
 832730                 /* While W not empty */
 833731                 while (defsites.arr[i] != NULL) {
 834732                         /* Remove some node n from W */
 835733                         n = defsites.arr[i];
 836734                         defsites.arr[i] = n->next;
 837735                         /* For each y in n->bb->df */
 838736                         for (j = 0; j < bbinfo->size; j++) {
 839737                                 if (!TESTBIT(n->bb->df, j))
 840738                                         continue;
 841739                                 
 842740                                 if (TESTBIT(bbinfo->arr[j]->Aphi, i))
 843741                                         continue;
 844742 
 845743                                 ntype = n->n->n_type;
 846744                                 k = 0;
 847745                                 /* Amount of predecessors for y */
 848746                                 SLIST_FOREACH(cnode, &n->bb->parents, cfgelem)
 849747                                         k++;
 850748                                 /* Construct phi(...) */
 851749                                 p = mklnode(TEMP, i, 0, ntype);
 852750                                 for (l = 0; l < k-1; l++)
 853751                                         p = mkbinode(PHI, p,
 854752                                             mklnode(TEMP, i, 0, ntype), ntype);
 855753                                 ip = ipnode(mkbinode(ASSIGN,
 856754                                     mklnode(TEMP, i, 0, ntype), p, ntype));
 857755                                 /* Insert phi at top of basic block */
 858756                                 DLIST_INSERT_BEFORE(((struct interpass*)&n->bb->first), ip, qelem);
 859757                                 n->bb->first = ip;
 860758                                 BITSET(bbinfo->arr[j]->Aphi, i);
 861759                                 if (!TESTBIT(bbinfo->arr[j]->Aorig, i)) {
 862760                                         pv = tmpalloc(sizeof(struct pvarinfo));
 863761                                         // XXXpj Ej fullständig information.
 864762                                         pv->bb = bbinfo->arr[j];
 865763                                         pv->next = defsites.arr[i]->next;
 866764                                         defsites.arr[i] = pv;
 867765                                 }
 868766                                         
 869767 
 870768                         }
 871769                 }
 872770         }
 873771 }
 874772 
 875773 /*
 876774  * Remove unreachable nodes in the CFG.
 877775  */
 878776 
 879777 void
 880778 remunreach(void)
 881779 {
 882780         struct basicblock *bb, *nbb;
 883781         struct interpass *next, *ctree;
 884782 
 885783         bb = DLIST_NEXT(&bblocks, bbelem);
 886784         while (bb != &bblocks) {
 887785                 nbb = DLIST_NEXT(bb, bbelem);
 888786 
 889787                 /* Code with dfnum 0 is unreachable */
 890788                 if (bb->dfnum != 0) {
 891789                         bb = nbb;
 892790                         continue;
 893791                 }
 894792 
 895793                 /* Need the epilogue node for other parts of the
 896794                    compiler, set its label to 0 and backend will
 897795                    handle it. */
 898796                 if (bb->first->type == IP_EPILOG) {
 899797                         bb->first->ip_lbl = 0;
 900798                         bb = nbb;
 901799                         continue;
 902800                 }
 903801 
 904802                 next = bb->first;
 905803                 do {
 906804                         ctree = next;
 907805                         next = DLIST_NEXT(ctree, qelem);
 908806                         
 909807                         if (ctree->type == IP_NODE)
 910808                                 tfree(ctree->ip_node);
 911809                         DLIST_REMOVE(ctree, qelem);
 912810                 } while (ctree != bb->last);
 913811                         
 914812                 DLIST_REMOVE(bb, bbelem);
 915813                 bb = nbb;
 916814         }
 917815 }
 918816 
 919817 void
 920818 printip(struct interpass *pole)
 921819 {
 922820         static char *foo[] = {
 923821            0, "NODE", "PROLOG", "STKOFF", "EPILOG", "DEFLAB", "DEFNAM", "ASM" };
 924822         struct interpass *ip;
 925823 
 926824         DLIST_FOREACH(ip, pole, qelem) {
 927825                 if (ip->type > MAXIP)
 928826                         printf("IP(%d) (%p): ", ip->type, ip);
 929827                 else
 930828                         printf("%s (%p): ", foo[ip->type], ip);
 931829                 switch (ip->type) {
 932830                 case IP_NODE: printf("\n");
 933831                         fwalk(ip->ip_node, e2print, 0); break;
 934832                 case IP_PROLOG:
 935833                         printf("%s\n",
 936834                             ((struct interpass_prolog *)ip)->ipp_name); break;
 937835                 case IP_STKOFF: printf("%d\n", ip->ip_off); break;
 938836                 case IP_EPILOG: printf("\n"); break;
 939837                 case IP_DEFLAB: printf(LABFMT "\n", ip->ip_lbl); break;
 940838                 }
 941839         }
 942840 }
FishEye: Open Source License registered to PCC.
Your maintenance has expired. You can renew your license at http://www.atlassian.com/fisheye/renew
Atlassian FishEye, CVS analysis. (Version:1.6.3 Build:build-336 2008-11-04) - Administration - Page generated 2014-10-31 21:49 +0100