Quick Search:

Mode

Context

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

Other Diffs

Ignore

Blank Lines Whitespace: Expand:

Diff

1.8
 
1.9
 
MAIN:pj:20050206114953
 
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 #include "external.h"
 3131 
 3232 #include <string.h>
 3333 #include <stdlib.h>
 3434 #include <machine/limits.h>
 3535 
 3636 #ifndef MIN
 3737 #define MIN(a,b) (((a)<(b))?(a):(b))
 3838 #endif
 3939 
 4040 #ifndef MAX
 4141 #define MAX(a,b) (((a) > (b)) ? (a) : (b))
 4242 #endif
 4343 
 4444 extern int saving;
 4545 static int dfsnum;
 4646 
 4747 void saveip(struct interpass *ip);
 4848 void deljumps(void);
 4949 void deltemp(NODE *p);
 5050 void optdump(struct interpass *ip);
 5151 
 5252 static SIMPLEQ_HEAD(, interpass) ipole = SIMPLEQ_HEAD_INITIALIZER(ipole);
 5353 
 5454 static struct rsv {
 5555         struct rsv *next;
 5656         int fpoff;
 5757         TWORD type;
 5858         int use;
 5959 } *rsv;
 6060 
 6161 int bblocks_build(struct labelinfo *labinfo, struct bblockinfo *bbinfo);
 6262 void cfg_build(struct labelinfo *labinfo);
 6363 void cfg_dfs(struct basicblock *bb, unsigned int parent,
 6464              struct bblockinfo *bbinfo);
 6565 void dominators(struct bblockinfo *bbinfo);
<> 66+struct basicblock *
  67+ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo);
  68+void link(struct basicblock *parent, struct basicblock *child);
  69+void computeDF(struct basicblock *bblock, struct bblockinfo *bbinfo);
6670 
 6771 
 6872 static CIRCLEQ_HEAD(, basicblock) bblocks = CIRCLEQ_HEAD_INITIALIZER(bblocks);
 6973 
 7074 static void
 7175 addcand(TWORD type, int off, int avoid)
 7276 {
 7377         struct rsv *w = rsv;
 7478 
 7579         while (w != NULL) {
 7680                 if (w->type == type && w->fpoff == off) {
 7781                         if (avoid)
 7882                                 w->use = -1;
 7983                         else if (w->use > 0)
 8084                                 w->use++;
 8185                         return;
 8286                 }
 8387                 w = w->next;
 8488         }
 8589         w = tmpalloc(sizeof(*w));
 8690         w->type = type;
 8791         w->fpoff = off;
 8892         w->use = avoid ? -1 : 1;
 8993         w->next = rsv;
 9094         rsv = w;
 9195 }
 9296 
 9397 /*
 9498  * walk through the tree and count the number of (possible)
 9599  * temporary nodes.
 96100  */
 97101 static void
 98102 cntuse(NODE *p)
 99103 {
 100104         NODE *l = p->n_left;
 101105         NODE *r = p->n_right;
 102106 
 103107         if (p->n_op == UMUL && l->n_op == REG && l->n_rval == FPREG) {
 104108                 /* found a candidate for register */
 105109                 addcand(p->n_type, 0, ISVOL(p->n_qual << TSHIFT));
 106110         } else if (p->n_op == UMUL && l->n_op == PLUS &&
 107111             l->n_right->n_op == ICON &&
 108112              (l->n_left->n_op == REG && l->n_left->n_rval == FPREG)) {
 109113                 /* The same as above */
 110114                 addcand(p->n_type, l->n_right->n_lval,
 111115                     ISVOL(p->n_qual << TSHIFT));
 112116         } else if (p->n_op == PLUS && l->n_op == REG && l->n_rval == FPREG &&
 113117             p->n_right->n_op == ICON) {
 114118                 /* Address taken of temporary, avoid register */
 115119                 addcand(DECREF(p->n_type), r->n_lval, 1);
 116120         } else {
 117121                 if (optype(p->n_op) == BITYPE)
 118122                         cntuse(r);
 119123                 if (optype(p->n_op) != LTYPE)
 120124                         cntuse(l);
 121125         }
 122126 }
 123127 
 124128 /*
 125129  * Insert a node into the register stack.
 126130  */
 127131 static void
 128132 insert(struct rsv *w, struct rsv **saved, int maxregs)
 129133 {
 130134         int i, j, size;
 131135 
 132136         size = szty(w->type);
 133137 
 134138         /* Find reg move position */
 135139         for (i = 0; i < maxregs; i++) {
 136140                 if (saved[i] == NULL)
 137141                         continue;
 138142                 if (saved[i]->use > w->use)
 139143                         break;
 140144         }
 141145         /* Move down other regs */
 142146         for (j = size; j < i; j++)
 143147                 saved[j-size] = saved[j];
 144148 
 145149         /* Insert new reg pointer */
 146150         if (i-size >= 0) {
 147151                 saved[i-size] = w;
 148152                 for (j = i-size+1; j < i; j++)
 149153                         saved[j] = NULL;
 150154         }
 151155 }
 152156 
 153157 /* Help routine to rconvert() */
 154158 static int
 155159 matches(TWORD type, int off, struct rsv **rsv, int maxregs)
 156160 {
 157161         int i;
 158162 
 159163         for (i = 0; i < maxregs; i++)
 160164                 if (rsv[i] && rsv[i]->type == type && rsv[i]->fpoff == off)
 161165                         return i;
 162166         return -1;
 163167 }
 164168 
 165169 /* Help routine to rconvert() */
 166170 static void
 167171 modify(NODE *p, int reg)
 168172 {
 169173         tfree(p->n_left);
 170174         p->n_op = REG;
 171175         p->n_rval = p->n_rall = reg + MINRVAR;
 172176         p->n_lval = 0;
 173177 }
 174178 
 175179 /*
 176180  * walk through the tree and convert nodes to registers
 177181  */
 178182 static void
 179183 rconvert(NODE *p, struct rsv **rsv, int maxregs)
 180184 {
 181185         NODE *l = p->n_left;
 182186         NODE *r = p->n_right;
 183187         int i;
 184188 
 185189         if (p->n_op == UMUL && l->n_op == REG && l->n_rval == FPREG) {
 186190                 /* found a candidate for register */
 187191                 if ((i = matches(p->n_type, 0, rsv, maxregs)) >= 0)
 188192                         modify(p, i);
 189193         } else if (p->n_op == UMUL && l->n_op == PLUS &&
 190194             l->n_right->n_op == ICON &&
 191195              (l->n_left->n_op == REG && l->n_left->n_rval == FPREG)) {
 192196                 /* The same as above */
 193197                 if ((i = matches(p->n_type,
 194198                     l->n_right->n_lval, rsv, maxregs)) >= 0)
 195199                         modify(p, i);
 196200 #if 0
 197201         } else if (p->n_op == PLUS && l->n_op == REG && l->n_rval == FPREG &&
 198202             p->n_right->n_op == ICON) {
 199203                 /* Address taken of temporary, avoid register */
 200204                 addcand(DECREF(p->n_type), r->n_lval, 1);
 201205 #endif
 202206         } else {
 203207                 if (optype(p->n_op) == BITYPE)
 204208                         rconvert(r, rsv, maxregs);
 205209                 if (optype(p->n_op) != LTYPE)
 206210                         rconvert(l, rsv, maxregs);
 207211         }
 208212 }
 209213 
 210214 /*
 211215  * Assign non-temporary registers to variables.
 212216  * Cannot do it if:
 213217  * - address is taken of the temporary
 214218  * - variable is declared "volatile".
 215219  */
 216220 int asgregs(void);
 217221 int
 218222 asgregs(void)
 219223 {
 220224         struct interpass *ip;
 221225         struct rsv *w, **saved;
 222226         int i, maxregs = MAXRVAR - MINRVAR + 1;
 223227 
 224228         if (maxregs == 0)
 225229                 return MAXRVAR; /* No register usage */
 226230         rsv = NULL;
 227231 
 228232         /* Loop over the function to do a usage count */
 229233         SIMPLEQ_FOREACH(ip, &ipole, sqelem) {
 230234                 if (ip->type != IP_NODE)
 231235                         continue;
 232236                 cntuse(ip->ip_node);
 233237         }
 234238         /* Check which nodes that shall be converted to registers */
 235239         saved = tmpalloc(sizeof(struct rsv *) * maxregs);
 236240         memset(saved, 0, sizeof(struct rsv *) * maxregs);
 237241         w = rsv;
 238242         for (w = rsv; w; w = w->next) {
 239243                 if (w->use < 0)
 240244                         continue; /* Not allowed to be in register */
 241245 
 242246                 /* XXX check here if type is allowed to be in register */
 243247 
 244248                 insert(w, saved, maxregs);
 245249         }
 246250 
 247251         /* Convert found nodes to registers */
 248252         SIMPLEQ_FOREACH(ip, &ipole, sqelem) {
 249253                 if (ip->type != IP_NODE)
 250254                         continue;
 251255                 rconvert(ip->ip_node, saved, maxregs);
 252256         }
 253257         for (i = 0; i < maxregs; i++)
 254258                 if (saved[i] != NULL)
 255259                         break;
 256260         return MINRVAR+i-1;
 257261 }
 258262 
 259263 void
 260264 saveip(struct interpass *ip)
 261265 {
 262266         struct interpass_prolog *ipp, *epp;
 263267 
 264268 #if 0
 265269         int regs;
 266270 #endif
 267271         struct labelinfo labinfo;
 268272         struct bblockinfo bbinfo;
 269273 
 270274         SIMPLEQ_INSERT_TAIL(&ipole, ip, sqelem);
 271275 
 272276         if (ip->type != IP_EPILOG)
 273277                 return;
 274278         epp = (struct interpass_prolog *)ip;
 275279         saving = -1;
 276280 
 277281         //              deljumps();     /* Delete redundant jumps and dead code */
 278282         if (xssaflag) {
 279283                 CIRCLEQ_INIT(&bblocks);
 280284                 if (bblocks_build(&labinfo, &bbinfo)) {
 281285                         cfg_build(&labinfo);
 282286                         dominators(&bbinfo);
<> 287+                        computeDF(CIRCLEQ_FIRST(&bblocks), &bbinfo);
283288 #if 0
 284289                         if (xssaflag) {
 285290                                 dfg = dfg_build(cfg);
 286291                                 ssa = ssa_build(cfg, dfg);
 287292                         }
 288293 #endif
 289294                 }
 290295  
 291296         }
 292297 #if 0
 293298         regs = asgregs();       /* Assign non-temporary registers */
 294299 #endif
 295300 
 296301 #ifdef PCC_DEBUG
 297302         if (epp->ipp_regs != MAXRVAR)
 298303                 comperr("register error");
 299304 #endif
 300305 
 301306         ipp = (struct interpass_prolog *)SIMPLEQ_FIRST(&ipole);
 302307         ipp->ipp_autos = epp->ipp_autos;
 303308         ipp->ipp_regs = epp->ipp_regs; // = regs;
 304309 
 305310 #ifdef MYOPTIM
 306311         myoptim((struct interpass *)ipp);
 307312 #endif
 308313 
 309314         while ((ip = SIMPLEQ_FIRST(&ipole))) {
 310315                 SIMPLEQ_REMOVE_HEAD(&ipole, sqelem);
 311316                 pass2_compile(ip);
 312317         }
 313318 }
 314319 
 315320 void
 316321 deljumps()
 317322 {
 318323         struct interpass *ip, *n;
 319324         int gotone;
 320325 
 321326 again:  gotone = 0;
 322327 
 323328         SIMPLEQ_FOREACH(ip, &ipole, sqelem) {
 324329                 if (ip->type == IP_EPILOG)
 325330                         return;
 326331                 if (ip->type != IP_NODE)
 327332                         continue;
 328333                 n = ip->sqelem.sqe_next;
 329334                 /* Check for nodes without side effects */
 330335                 if (ip->ip_node->n_op != GOTO)
 331336                         continue;
 332337                 switch (n->type) {
 333338                 case IP_NODE:
 334339                         tfree(n->ip_node);
 335340                         ip->sqelem.sqe_next = n->sqelem.sqe_next;
 336341                         break;
 337342                 case IP_DEFLAB:
 338343                         if (ip->ip_node->n_left->n_lval != n->ip_lbl)
 339344                                 continue;
 340345                         tfree(ip->ip_node);
 341346                         *ip = *n;
 342347                         break;
 343348                 default:
 344349                         continue;
 345350                 }
 346351                 gotone = 1;
 347352         }
 348353         if (gotone)
 349354                 goto again;
 350355 }
 351356 
 352357 void
 353358 optdump(struct interpass *ip)
 354359 {
 355360         static char *nm[] = { "node", "prolog", "newblk", "epilog", "locctr",
 356361                 "deflab", "defnam", "asm" };
 357362         printf("type %s\n", nm[ip->type-1]);
 358363         switch (ip->type) {
 359364         case IP_NODE:
 360365                 fwalk(ip->ip_node, e2print, 0);
 361366                 break;
 362367         case IP_DEFLAB:
 363368                 printf("label " LABFMT "\n", ip->ip_lbl);
 364369                 break;
 365370         case IP_ASM:
 366371                 printf(": %s\n", ip->ip_asm);
 367372                 break;
 368373         }
 369374 }
 370375 
 371376 /*
 372377  * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
 373378  *
 374379  * Also fills the labelinfo struct with information about which bblocks
 375380  * that contain which label.
 376381  */
 377382 
 378383 int
 379384 bblocks_build(struct labelinfo *labinfo, struct bblockinfo *bbinfo)
 380385 {
 381386         struct interpass *ip;
 382387         struct basicblock *bb = NULL;
 383388         int leader = 1;
 384389         unsigned int low = UINT_MAX, high = 0;
 385390         int count = 0;
 386391         int i;
 387392 
 388393         /*
 389394          * First statement is a leader.
 390395          * Any statement that is target of a jump is a leader.
 391396          * Any statement that immediately follows a jump is a leader.
 392397          */
 393398 
 394399         SIMPLEQ_FOREACH(ip, &ipole, sqelem) {
 395400                 /* Garbage, skip it */
 396401                 if ((ip->type == IP_LOCCTR) || (ip->type == IP_NEWBLK))
 397402                         continue;
 398403 
 399404                 if (leader) {
 400405                         bb = tmpalloc(sizeof(struct basicblock));
 401406                         bb->first = bb->last = ip;
 402407                         SIMPLEQ_INIT(&bb->children);
 403408                         SIMPLEQ_INIT(&bb->parents);
 404409                         bb->dfnum = 0;
 405410                         bb->dfparent = 0;
 406411                         bb->semi = 0;
 407412                         bb->ancestor = 0;
 408413                         bb->idom = 0;
 409414                         bb->samedom = 0;
 410415                         bb->bucket = NULL;
 411416                         bb->df = NULL;
 412417                         CIRCLEQ_INSERT_TAIL(&bblocks, bb, bbelem);
 413418                         leader = 0;
 414419                         count++;
 415420                 }
 416421                 
 417422                 /* Prologue and epilogue in their own bblock */
 418423                 if ((ip->type == IP_PROLOG) || (ip->type == IP_EPILOG)) {
 419424                         bb->last = ip;
 420425                         if (ip->type == IP_EPILOG)
 421426                                 high = MAX(ip->ip_lbl, high);
 422427                         leader = 1;
 423428                         continue;
 424429                 }
 425430                 
 426431                 /* Keep track of highest and lowest label number */
 427432                 if (ip->type == IP_DEFLAB) {
 428433                         low = MIN(ip->ip_lbl, low);
 429434                         high = MAX(ip->ip_lbl, high);
 430435                 }
 431436 
 432437                 /* Make sure each label is in a unique bblock */
 433438                 if (((ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) &&
 434439                     bb->first != ip) {
 435440                         bb = tmpalloc(sizeof(struct basicblock));
 436441                         bb->first = bb->last = ip;
 437442                         SIMPLEQ_INIT(&bb->children);
 438443                         SIMPLEQ_INIT(&bb->parents);
 439444                         bb->dfnum = 0;
 440445                         bb->dfparent = 0;
 441446                         bb->semi = 0;
 442447                         bb->ancestor = 0;
 443448                         bb->idom = 0;
 444449                         bb->samedom = 0;
 445450                         bb->bucket = NULL;
 446451                         bb->df = NULL;
 447452                         CIRCLEQ_INSERT_TAIL(&bblocks, bb, bbelem);
 448453                         count++;
 449454                         continue;
 450455                 }
 451456 
 452457                 if (ip->type == IP_ASM)
 453458                         return 0;
 454459 
 455460                 if (ip->type == IP_NODE) {
 456461                         switch(ip->ip_node->n_op) {
 457462                         case CBRANCH:
 458463                         case GOTO:
 459464                         case RETURN:
 460465                                 /* Jumps, last in bblock. */
 461466                                 leader = 1;
 462467                                 break;
 463468 
 464469                         case NAME:
 465470                         case ICON:
 466471                         case FCON:
 467472                         case REG:
 468473                         case OREG:
 469474                         case MOVE:
 470475                         case PLUS:
 471476                         case MINUS:
 472477                         case DIV:
 473478                         case MOD:
 474479                         case MUL:
 475480                         case AND:
 476481                         case OR:
 477482                         case ER:
 478483                         case LS:
 479484                         case COMPL:
 480485                         case INCR:
 481486                         case DECR:
 482487                         case UMUL:
 483488                         case UMINUS:
 484489                         case EQ:
 485490                         case NE:
 486491                         case LE:
 487492                         case GE:
 488493                         case GT:
 489494                         case ULE:
 490495                         case ULT:
 491496                         case UGE:
 492497                         case UGT:
 493498                         case ASSIGN:
 494499                         case FORCE:
 495500                         case FUNARG:
 496501                         case CALL:
 497502                         case UCALL:
 498503                         case FORTCALL:
 499504                         case UFORTCALL:
 500505                         case STCALL:
 501506                         case USTCALL:
 502507                                 /* Not jumps, continue with bblock. */
 503508                                 break;
 504509 
 505510                         default:
 506511                                 comperr("optim2:bblocks_build() %d",ip->ip_node->n_op );
 507512                                 break;
 508513                         }
 509514                 }
 510515 
 511516                 bb->last = ip;
 512517         }
 513518 #ifdef PCC_DEBUG
 514519         printf("Basic blocks in func: %d\n", count);
 515520         printf("Label range in func: %d\n %d", high - low + 1, low);
 516521 #endif
 517522 
 518523         labinfo->low = low;
 519524         labinfo->size = high - low + 1;
 520525         labinfo->arr = tmpalloc(labinfo->size * sizeof(struct basicblock *));
 521526         for (i = 0; i <= labinfo->size; i++) {
 522527                 labinfo->arr[i] = NULL;
 523528         }
 524529         
 525530         bbinfo->size = count + 1;
 526531         bbinfo->arr = tmpalloc(bbinfo->size * sizeof(struct basicblock *));
 527532         for (i = 0; i <= bbinfo->size; i++) {
 528533                 bbinfo->arr[i] = NULL;
 529534         }
 530535 
 531536         /* Build the label table */
 532537         CIRCLEQ_FOREACH(bb, &bblocks, bbelem) {
 533538                 if (bb->first->type == IP_DEFLAB) {
 534539                         labinfo->arr[bb->first->ip_lbl - low] = bb;
 535540                 }
 536541                 if (bb->first->type == IP_EPILOG) {
 537542                         labinfo->arr[bb->first->ip_lbl - low] = bb;
 538543                 }
 539544         }
 540545 
 541546         return 1;
 542547 }
 543548 
 544549 /*
 545550  * Build the control flow graph.
 546551  */
 547552 
 548553 void
 549554 cfg_build(struct labelinfo *labinfo)
 550555 {
 551556         /* Child and parent nodes */
 552557         struct cfgnode *cnode;
 553558         struct cfgnode *pnode;
 554559         struct basicblock *bb;
 555560         
 556561         CIRCLEQ_FOREACH(bb, &bblocks, bbelem) {
 557562 
 558563                 if (bb->first->type == IP_EPILOG) {
 559564                         break;
 560565                 }
 561566 
 562567                 cnode = tmpalloc(sizeof(struct cfgnode));
 563568                 pnode = tmpalloc(sizeof(struct cfgnode));
 564569                 pnode->bblock = bb;
 565570 
 566571                 if ((bb->last->type == IP_NODE) &&
 567572                     (bb->last->ip_node->n_op == GOTO)) {
 568573                         if (bb->last->ip_node->n_left->n_lval - labinfo->low >
 569574                             labinfo->size) {
 570575                                 comperr("Label out of range: %d, base %d",
 571576                                         bb->last->ip_node->n_left->n_lval,
 572577                                         labinfo->low);
 573578                         }
 574579                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_left->n_lval - labinfo->low];
 575580                         SIMPLEQ_INSERT_TAIL(&cnode->bblock->parents, pnode, cfgelem);
 576581                         SIMPLEQ_INSERT_TAIL(&bb->children, cnode, cfgelem);
 577582                         continue;
 578583                 }
 579584                 if ((bb->last->type == IP_NODE) &&
 580585                     (bb->last->ip_node->n_op == CBRANCH)) {
 581586                         if (bb->last->ip_node->n_right->n_lval - labinfo->low >
 582587                             labinfo->size)
 583588                                 comperr("Label out of range: %d",
 584589                                         bb->last->ip_node->n_left->n_lval);
 585590                         
 586591                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_right->n_lval - labinfo->low];
 587592                         SIMPLEQ_INSERT_TAIL(&cnode->bblock->parents, pnode, cfgelem);
 588593                         SIMPLEQ_INSERT_TAIL(&bb->children, cnode, cfgelem);
 589594                         cnode = tmpalloc(sizeof(struct cfgnode));
 590595                         pnode = tmpalloc(sizeof(struct cfgnode));
 591596                         pnode->bblock = bb;
 592597                 }
 593598 
 594599                 cnode->bblock = CIRCLEQ_NEXT(bb, bbelem);
 595600                 SIMPLEQ_INSERT_TAIL(&cnode->bblock->parents, pnode, cfgelem);
 596601                 SIMPLEQ_INSERT_TAIL(&bb->children, cnode, cfgelem);
 597602         }
 598603 }
 599604 
 600605 void
 601606 cfg_dfs(struct basicblock *bb, unsigned int parent, struct bblockinfo *bbinfo)
 602607 {
 603608         struct cfgnode *cnode;
 604609         
 605610         if (bb->dfnum != 0)
 606611                 return;
 607612 
 608613         bb->dfnum = ++dfsnum;
 609614         bb->dfparent = parent;
 610615         bbinfo->arr[bb->dfnum] = bb;
 611616         SIMPLEQ_FOREACH(cnode, &bb->children, cfgelem) {
 612617                 cfg_dfs(cnode->bblock, bb->dfnum, bbinfo);
 613618         }
 614619 }
 615620 
<>616 -struct basicblock *
 617 -ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo);
 618 -void link(struct basicblock *parent, struct basicblock *child);
 619 -void
 620 -computeDF(struct basicblock *bblock, struct bblockinfo *bbinfo);
 621 -
622621 /*
 623622  * Algorithm 19.9, pp 414 from Appel.
 624623  */
 625624 
 626625 void
 627626 dominators(struct bblockinfo *bbinfo)
 628627 {
 629628         struct cfgnode *cnode;
 630629         struct basicblock *bb, *y, *v;
 631630         struct basicblock *s, *sprime, *p;
 632631         int i;
 633632 
 634633         CIRCLEQ_FOREACH(bb, &bblocks, bbelem) {
 635634                 bb->bucket = tmpalloc((bbinfo->size + 7)/8);
<> 635+                memset(bb->bucket, 0, (bbinfo->size + 7)/8);
636636         }
 637637 
 638638         dfsnum = 0;
 639639         cfg_dfs(CIRCLEQ_FIRST(&bblocks), 0, bbinfo);
 640640 
 641641         CIRCLEQ_FOREACH_REVERSE(bb, &bblocks, bbelem) {
 642642                 if (bb->first->type == IP_PROLOG)
 643643                         continue;
 644644                 p = s = bbinfo->arr[bb->dfparent];
 645645                 SIMPLEQ_FOREACH(cnode, &bb->parents, cfgelem) {
 646646                         if (cnode->bblock->dfnum <= bb->dfnum)
 647647                                 sprime = cnode->bblock;
 648648                         else
 649649                                 sprime = ancestorwithlowestsemi(cnode->bblock,
 650650                                                                 bbinfo);
 651651                         if (sprime->dfnum < s->dfnum)
 652652                                 s = sprime;
 653653                 }
 654654                 bb->semi = s->dfnum;
 655655                 s->bucket[bb->dfnum/8] |= (1 << (bb->dfnum & 3));
 656656                 link(p, bb);
 657657                 for (i = 1; i < bbinfo->size; i++) {
 658658                         if(p->bucket[i/8] & (1 << (i & 3))) {
 659659                                 v = bbinfo->arr[i];
 660660                                 y = ancestorwithlowestsemi(bbinfo->arr[i], bbinfo);
 661661                                 if (y->semi == v->semi)
 662662                                         v->idom = p->dfnum;
 663663                                 else
 664664                                         v->samedom = y->dfnum;
 665665                         }
 666666                 }
 667667                 memset(p->bucket, 0, (bbinfo->size + 7)/8);
 668668         }
 669669         CIRCLEQ_FOREACH(bb, &bblocks, bbelem) {
 670670                 if (bb->first->type == IP_PROLOG)
 671671                         continue;
 672672                 if (bb->samedom != 0)
 673673                         bb->idom = bbinfo->arr[bb->samedom]->idom;
 674674         }
 675675 }
 676676 
 677677 
 678678 struct basicblock *
 679679 ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo)
 680680 {
 681681         struct basicblock *u = bblock;
 682682         struct basicblock *v = bblock;
 683683 
 684684         while (v->ancestor != 0) {
 685685                 if (bbinfo->arr[v->semi]->dfnum <
 686686                     bbinfo->arr[u->semi]->dfnum)
 687687                         u = v;
 688688                 v = bbinfo->arr[v->ancestor];
 689689         }
 690690         return u;
 691691 }
 692692 
 693693 void
 694694 link(struct basicblock *parent, struct basicblock *child)
 695695 {
 696696         child->ancestor = parent->dfnum;
 697697 }
 698698 
 699699 void
 700700 computeDF(struct basicblock *bblock, struct bblockinfo *bbinfo)
 701701 {
 702702         struct cfgnode *cnode;
 703703         int i;
 704704         
 705705         if (bblock->df)
 706706                 comperr("Har redan DF, hm");
 707707         
<>708 -        if (!bblock->df)
  708+        if (!bblock->df) {
709709                 bblock->df = tmpalloc((bbinfo->size + 7)/8);
<> 710+                memset(bblock->df, 0, (bbinfo->size + 7)/8);
  711+        }
<_710712 
 711713 
 712714         SIMPLEQ_FOREACH(cnode, &bblock->children, cfgelem) {
 713715                 if (cnode->bblock->idom != bblock->dfnum)
 714716                         BITSET(bblock->df, cnode->bblock->dfnum);
 715717         }
 716718         /* XXX succ != children? */
 717719         SIMPLEQ_FOREACH(cnode, &bblock->children, cfgelem) {
 718720                 computeDF(cnode->bblock, bbinfo);
 719721                 for (i = 1; i < bbinfo->size; i++) {
 720722                         if (TESTBIT(cnode->bblock->df, i) &&
 721723                             (cnode->bblock == bblock ||
 722724                              (bblock->idom != cnode->bblock->dfnum)))
 723725                             BITSET(bblock->df, i);
 724726                 }
 725727         }
 726728 }
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-07-10 10:32 +0200