Quick Search:

Mode

Context

Displaying 3 lines of context. None | Less | More | Full

Other Diffs

Ignore

Blank Lines Whitespace: Expand:

Diff

1.7
 
1.8
 
MAIN:pj:20050205144217
 
optim2.c
_>4242 #endif
 4343 
 4444 extern int saving;
<> 45+static int dfsnum;
4546 
 4647 void saveip(struct interpass *ip);
 4748 void deljumps(void);
     
 !
5758         int use;
 5859 } *rsv;
 5960 
<>60 -int bblocks_build(struct labelinfo *labinfo);
  61+int bblocks_build(struct labelinfo *labinfo, struct bblockinfo *bbinfo);
6162 void cfg_build(struct labelinfo *labinfo);
<> 63+void cfg_dfs(struct basicblock *bb, unsigned int parent,
  64+             struct bblockinfo *bbinfo);
  65+void dominators(struct bblockinfo *bbinfo);
6266 
 6367 
 6468 static CIRCLEQ_HEAD(, basicblock) bblocks = CIRCLEQ_HEAD_INITIALIZER(bblocks);
     
 !
261265         int regs;
 262266 #endif
 263267         struct labelinfo labinfo;
<> 268+        struct bblockinfo bbinfo;
264269 
 265270         SIMPLEQ_INSERT_TAIL(&ipole, ip, sqelem);
 266271 
     
 !
272277         //              deljumps();     /* Delete redundant jumps and dead code */
 273278         if (xssaflag) {
 274279                 CIRCLEQ_INIT(&bblocks);
<>275 -                if (bblocks_build(&labinfo)) {
  280+                if (bblocks_build(&labinfo, &bbinfo)) {
276281                         cfg_build(&labinfo);
<> 282+                        dominators(&bbinfo);
277283 #if 0
 278284                         if (xssaflag) {
 279285                                 dfg = dfg_build(cfg);
     
 !
370376  */
 371377 
 372378 int
<>373 -bblocks_build(struct labelinfo *labinfo)
  379+bblocks_build(struct labelinfo *labinfo, struct bblockinfo *bbinfo)
374380 {
 375381         struct interpass *ip;
 376382         struct basicblock *bb = NULL;
 377383         int leader = 1;
 378384         unsigned int low = UINT_MAX, high = 0;
<>379 -        int XXXcount = 0;
  385+        int count = 0;
380386         int i;
 381387 
 382388         /*
     
 !
395401                         bb->first = bb->last = ip;
 396402                         SIMPLEQ_INIT(&bb->children);
 397403                         SIMPLEQ_INIT(&bb->parents);
<> 404+                        bb->dfnum = 0;
  405+                        bb->dfparent = 0;
  406+                        bb->semi = 0;
  407+                        bb->ancestor = 0;
  408+                        bb->idom = 0;
  409+                        bb->samedom = 0;
  410+                        bb->bucket = NULL;
  411+                        bb->df = NULL;
398412                         CIRCLEQ_INSERT_TAIL(&bblocks, bb, bbelem);
 399413                         leader = 0;
<>400 -                        XXXcount++;
  414+                        count++;
401415                 }
 402416                 
 403417                 /* Prologue and epilogue in their own bblock */
     
 !
422436                         bb->first = bb->last = ip;
 423437                         SIMPLEQ_INIT(&bb->children);
 424438                         SIMPLEQ_INIT(&bb->parents);
<> 439+                        bb->dfnum = 0;
  440+                        bb->dfparent = 0;
  441+                        bb->semi = 0;
  442+                        bb->ancestor = 0;
  443+                        bb->idom = 0;
  444+                        bb->samedom = 0;
  445+                        bb->bucket = NULL;
  446+                        bb->df = NULL;
425447                         CIRCLEQ_INSERT_TAIL(&bblocks, bb, bbelem);
<>426 -                        XXXcount++;
  448+                        count++;
427449                         continue;
 428450                 }
 429451 
     
 !
489511                 bb->last = ip;
 490512         }
 491513 #ifdef PCC_DEBUG
<>492 -        printf("Basic blocks in func: %d\n", XXXcount);
  514+        printf("Basic blocks in func: %d\n", count);
493515         printf("Label range in func: %d\n %d", high - low + 1, low);
 494516 #endif
 495517 
 496518         labinfo->low = low;
 497519         labinfo->size = high - low + 1;
 498520         labinfo->arr = tmpalloc(labinfo->size * sizeof(struct basicblock *));
<>499 -        for(i = 0; i <= labinfo->size; i++) {
  521+        for (i = 0; i <= labinfo->size; i++) {
500522                 labinfo->arr[i] = NULL;
 501523         }
<> 524+        
  525+        bbinfo->size = count + 1;
  526+        bbinfo->arr = tmpalloc(bbinfo->size * sizeof(struct basicblock *));
  527+        for (i = 0; i <= bbinfo->size; i++) {
  528+                bbinfo->arr[i] = NULL;
  529+        }
502530 
 503531         /* Build the label table */
 504532         CIRCLEQ_FOREACH(bb, &bblocks, bbelem) {
     
 !
569597         }
 570598 }
 571599 
<_ 600+void
  601+cfg_dfs(struct basicblock *bb, unsigned int parent, struct bblockinfo *bbinfo)
  602+{
  603+        struct cfgnode *cnode;
  604+        
  605+        if (bb->dfnum != 0)
  606+                return;
  607+
  608+        bb->dfnum = ++dfsnum;
  609+        bb->dfparent = parent;
  610+        bbinfo->arr[bb->dfnum] = bb;
  611+        SIMPLEQ_FOREACH(cnode, &bb->children, cfgelem) {
  612+                cfg_dfs(cnode->bblock, bb->dfnum, bbinfo);
  613+        }
  614+}
  615+
  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+
  622+/*
  623+ * Algorithm 19.9, pp 414 from Appel.
  624+ */
  625+
  626+void
  627+dominators(struct bblockinfo *bbinfo)
  628+{
  629+        struct cfgnode *cnode;
  630+        struct basicblock *bb, *y, *v;
  631+        struct basicblock *s, *sprime, *p;
  632+        int i;
  633+
  634+        CIRCLEQ_FOREACH(bb, &bblocks, bbelem) {
  635+                bb->bucket = tmpalloc((bbinfo->size + 7)/8);
  636+        }
  637+
  638+        dfsnum = 0;
  639+        cfg_dfs(CIRCLEQ_FIRST(&bblocks), 0, bbinfo);
  640+
  641+        CIRCLEQ_FOREACH_REVERSE(bb, &bblocks, bbelem) {
  642+                if (bb->first->type == IP_PROLOG)
  643+                        continue;
  644+                p = s = bbinfo->arr[bb->dfparent];
  645+                SIMPLEQ_FOREACH(cnode, &bb->parents, cfgelem) {
  646+                        if (cnode->bblock->dfnum <= bb->dfnum)
  647+                                sprime = cnode->bblock;
  648+                        else
  649+                                sprime = ancestorwithlowestsemi(cnode->bblock,
  650+                                                                bbinfo);
  651+                        if (sprime->dfnum < s->dfnum)
  652+                                s = sprime;
  653+                }
  654+                bb->semi = s->dfnum;
  655+                s->bucket[bb->dfnum/8] |= (1 << (bb->dfnum & 3));
  656+                link(p, bb);
  657+                for (i = 1; i < bbinfo->size; i++) {
  658+                        if(p->bucket[i/8] & (1 << (i & 3))) {
  659+                                v = bbinfo->arr[i];
  660+                                y = ancestorwithlowestsemi(bbinfo->arr[i], bbinfo);
  661+                                if (y->semi == v->semi)
  662+                                        v->idom = p->dfnum;
  663+                                else
  664+                                        v->samedom = y->dfnum;
  665+                        }
  666+                }
  667+                memset(p->bucket, 0, (bbinfo->size + 7)/8);
  668+        }
  669+        CIRCLEQ_FOREACH(bb, &bblocks, bbelem) {
  670+                if (bb->first->type == IP_PROLOG)
  671+                        continue;
  672+                if (bb->samedom != 0)
  673+                        bb->idom = bbinfo->arr[bb->samedom]->idom;
  674+        }
  675+}
  676+
  677+
  678+struct basicblock *
  679+ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo)
  680+{
  681+        struct basicblock *u = bblock;
  682+        struct basicblock *v = bblock;
  683+
  684+        while (v->ancestor != 0) {
  685+                if (bbinfo->arr[v->semi]->dfnum <
  686+                    bbinfo->arr[u->semi]->dfnum)
  687+                        u = v;
  688+                v = bbinfo->arr[v->ancestor];
  689+        }
  690+        return u;
  691+}
  692+
  693+void
  694+link(struct basicblock *parent, struct basicblock *child)
  695+{
  696+        child->ancestor = parent->dfnum;
  697+}
  698+
  699+void
  700+computeDF(struct basicblock *bblock, struct bblockinfo *bbinfo)
  701+{
  702+        struct cfgnode *cnode;
  703+        int i;
  704+        
  705+        if (bblock->df)
  706+                comperr("Har redan DF, hm");
  707+        
  708+        if (!bblock->df)
  709+                bblock->df = tmpalloc((bbinfo->size + 7)/8);
  710+
  711+
  712+        SIMPLEQ_FOREACH(cnode, &bblock->children, cfgelem) {
  713+                if (cnode->bblock->idom != bblock->dfnum)
  714+                        BITSET(bblock->df, cnode->bblock->dfnum);
  715+        }
  716+        /* XXX succ != children? */
  717+        SIMPLEQ_FOREACH(cnode, &bblock->children, cfgelem) {
  718+                computeDF(cnode->bblock, bbinfo);
  719+                for (i = 1; i < bbinfo->size; i++) {
  720+                        if (TESTBIT(cnode->bblock->df, i) &&
  721+                            (cnode->bblock == bblock ||
  722+                             (bblock->idom != cnode->bblock->dfnum)))
  723+                            BITSET(bblock->df, i);
  724+                }
  725+        }
  726+}
FishEye: Open Source License registered to PCC.
Your maintenance has expired. You can renew your license at http://www.atlassian.com/fisheye/renew
Atlassian FishEye, CVS analysis. (Version:1.6.3 Build:build-336 2008-11-04) - Administration - Page generated 2014-09-22 14:12 +0200