/* $Id: optim2.c,v 1.79 2010/06/04 07:18:46 ragge Exp $ */ /* * Copyright (c) 2004 Anders Magnusson (ragge@ludd.luth.se). * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 3. The name of the author may not be used to endorse or promote products * derived from this software without specific prior written permission * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #include "pass2.h" #include #include #ifndef MIN #define MIN(a,b) (((a)<(b))?(a):(b)) #endif #ifndef MAX #define MAX(a,b) (((a) > (b)) ? (a) : (b)) #endif #define BDEBUG(x) if (b2debug) printf x #define mktemp(n, t) mklnode(TEMP, 0, n, t) #define CHADD(bb,c) { if (bb->ch[0] == 0) bb->ch[0] = c; \ else if (bb->ch[1] == 0) bb->ch[1] = c; \ else comperr("triple cfnodes"); } #define FORCH(cn, chp) \ for (cn = &chp[0]; cn < &chp[2] && cn[0]; cn++) /* main switch for new things not yet ready for all-day use */ /* #define ENABLE_NEW */ static int dfsnum; void saveip(struct interpass *ip); void deljumps(struct p2env *); void optdump(struct interpass *ip); void printip(struct interpass *pole); static struct varinfo defsites; struct interpass *storesave; void bblocks_build(struct p2env *); void cfg_build(struct p2env *); void cfg_dfs(struct basicblock *bb, unsigned int parent, struct bblockinfo *bbinfo); void dominators(struct p2env *); struct basicblock * ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo); void link(struct basicblock *parent, struct basicblock *child); void computeDF(struct p2env *, struct basicblock *bblock); void printDF(struct p2env *p2e); void findTemps(struct interpass *ip); void placePhiFunctions(struct p2env *); void renamevar(struct p2env *p2e,struct basicblock *bblock); void removephi(struct p2env *p2e); void remunreach(struct p2env *); static void liveanal(struct p2env *p2e); static void printip2(struct interpass *); /* create "proper" basic blocks, add labels where needed (so bblocks have labels) */ /* run before bb generate */ static void add_labels(struct p2env*) ; /* Perform trace scheduling, try to get rid of gotos as much as possible */ void TraceSchedule(struct p2env*) ; #ifdef ENABLE_NEW static void do_cse(struct p2env* p2e) ; #endif /* Walk the complete set, performing a function on each node. * if type is given, apply function on only that type */ void WalkAll(struct p2env* p2e, void (*f) (NODE*, void*), void* arg, int type) ; void BBLiveDead(struct basicblock* bblock, int what, unsigned int variable) ; /* Fill the live/dead code */ void LiveDead(struct p2env* p2e, int what, unsigned int variable) ; #ifdef PCC_DEBUG void printflowdiagram(struct p2env *, char *); #endif void optimize(struct p2env *p2e) { struct interpass *ipole = &p2e->ipole; if (b2debug) { printf("initial links\n"); printip(ipole); } if (xdeljumps) deljumps(p2e); /* Delete redundant jumps and dead code */ if (xssaflag) add_labels(p2e) ; #ifdef ENABLE_NEW do_cse(p2e); #endif #ifdef PCC_DEBUG if (b2debug) { printf("links after deljumps\n"); printip(ipole); } #endif if (xssaflag || xtemps) { bblocks_build(p2e); BDEBUG(("Calling cfg_build\n")); cfg_build(p2e); #ifdef PCC_DEBUG printflowdiagram(p2e, "first"); #endif } if (xssaflag) { BDEBUG(("Calling liveanal\n")); liveanal(p2e); BDEBUG(("Calling dominators\n")); dominators(p2e); BDEBUG(("Calling computeDF\n")); computeDF(p2e, DLIST_NEXT(&p2e->bblocks, bbelem)); if (b2debug) { printDF(p2e); } BDEBUG(("Calling placePhiFunctions\n")); placePhiFunctions(p2e); BDEBUG(("Calling renamevar\n")); renamevar(p2e,DLIST_NEXT(&p2e->bblocks, bbelem)); BDEBUG(("Calling removephi\n")); #ifdef PCC_DEBUG printflowdiagram(p2e, "ssa"); #endif removephi(p2e); BDEBUG(("Calling remunreach\n")); /* remunreach(p2e); */ /* * Recalculate basic blocks and cfg that was destroyed * by removephi */ /* first, clean up all what deljumps should have done, and more */ /* TODO: add the basic blocks done by the ssa code by hand. * The trace scheduler should not change the order in * which blocks are executed or what data is calculated. * Thus, the BBlock order should remain correct. */ #ifdef ENABLE_NEW bblocks_build(p2e, &labinfo, &bbinfo); BDEBUG(("Calling cfg_build\n")); cfg_build(p2e, &labinfo); TraceSchedule(p2e); #ifdef PCC_DEBUG printflowdiagram(p2e, &labinfo, &bbinfo,"sched_trace"); if (b2debug) { printf("after tracesched\n"); printip(ipole); fflush(stdout) ; } #endif #endif /* Now, clean up the gotos we do not need any longer */ if (xdeljumps) deljumps(p2e); /* Delete redundant jumps and dead code */ bblocks_build(p2e); BDEBUG(("Calling cfg_build\n")); cfg_build(p2e); #ifdef PCC_DEBUG printflowdiagram(p2e, "no_phi"); if (b2debug) { printf("new tree\n"); printip(ipole); } #endif } #ifdef PCC_DEBUG { int i; for (i = NIPPREGS; i--; ) if (p2e->epp->ipp_regs[i] != 0) comperr("register error"); } #endif myoptim(ipole); } /* * Delete unused labels, excess of labels, gotos to gotos. * This routine can be made much more efficient. * * Layout of the statement list here (_must_ look this way!): * PROLOG * LABEL - states beginning of function argument moves * ...code to save/move arguments * LABEL - states beginning of execution code * ...code + labels in function in function * EPILOG * * This version of deljumps is based on the c2 implementation * that were included in 2BSD. */ #define LABEL 1 #define JBR 2 #define CBR 3 #define STMT 4 #define EROU 5 struct dlnod { int op; struct interpass *dlip; struct dlnod *forw; struct dlnod *back; struct dlnod *ref; int labno; int refc; }; #ifdef DLJDEBUG static void dumplink(struct dlnod *dl) { printf("dumplink %p\n", dl); for (; dl; dl = dl->forw) { if (dl->op == STMT) { printf("STMT(%p)\n", dl); fwalk(dl->dlip->ip_node, e2print, 0); } else if (dl->op == EROU) { printf("EROU(%p)\n", dl); } else { static char *str[] = { 0, "LABEL", "JBR", "CBR" }; printf("%s(%p) %d refc %d ref %p\n", str[dl->op], dl, dl->labno, dl->refc, dl->ref); } } printf("end dumplink\n"); } #endif /* * Create the linked list that we can work on. */ static void listsetup(struct interpass *ipole, struct dlnod *dl) { struct interpass *ip = DLIST_NEXT(ipole, qelem); struct interpass *nip; struct dlnod *p, *lastp; NODE *q; lastp = dl; while (ip->type != IP_DEFLAB) ip = DLIST_NEXT(ip,qelem); ip = DLIST_NEXT(ip,qelem); while (ip->type != IP_DEFLAB) ip = DLIST_NEXT(ip,qelem); /* Now ip is at the beginning */ for (;;) { ip = DLIST_NEXT(ip,qelem); if (ip == ipole) break; p = tmpalloc(sizeof(struct dlnod)); p->labno = 0; p->dlip = ip; switch (ip->type) { case IP_DEFLAB: p->op = LABEL; p->labno = ip->ip_lbl; break; case IP_NODE: q = ip->ip_node; switch (q->n_op) { case GOTO: p->op = JBR; p->labno = q->n_left->n_lval; break; case CBRANCH: p->op = CBR; p->labno = q->n_right->n_lval; break; case ASSIGN: /* remove ASSIGN to self for regs */ if (q->n_left->n_op == REG && q->n_right->n_op == REG && regno(q->n_left) == regno(q->n_right)) { nip = DLIST_PREV(ip, qelem); tfree(q); DLIST_REMOVE(ip, qelem); ip = nip; continue; } /* FALLTHROUGH */ default: p->op = STMT; break; } break; case IP_ASM: p->op = STMT; break; case IP_EPILOG: p->op = EROU; break; default: comperr("listsetup: bad ip node %d", ip->type); } p->forw = 0; p->back = lastp; lastp->forw = p; lastp = p; p->ref = 0; } } static struct dlnod * nonlab(struct dlnod *p) { while (p && p->op==LABEL) p = p->forw; return(p); } static void iprem(struct dlnod *p) { if (p->dlip->type == IP_NODE) tfree(p->dlip->ip_node); DLIST_REMOVE(p->dlip, qelem); } static void decref(struct dlnod *p) { if (--p->refc <= 0) { iprem(p); p->back->forw = p->forw; p->forw->back = p->back; } } static void setlab(struct dlnod *p, int labno) { p->labno = labno; if (p->op == JBR) p->dlip->ip_node->n_left->n_lval = labno; else if (p->op == CBR) { p->dlip->ip_node->n_right->n_lval = labno; p->dlip->ip_node->n_left->n_label = labno; } else comperr("setlab bad op %d", p->op); } /* * Label reference counting and removal of unused labels. */ #define LABHS 127 static void refcount(struct p2env *p2e, struct dlnod *dl) { struct dlnod *p, *lp; struct dlnod *labhash[LABHS]; struct dlnod **hp, *tp; /* Clear label hash */ for (hp = labhash; hp < &labhash[LABHS];) *hp++ = 0; /* Enter labels into hash. Later overwrites earlier */ for (p = dl->forw; p!=0; p = p->forw) if (p->op==LABEL) { labhash[p->labno % LABHS] = p; p->refc = 0; } /* search for jumps to labels and fill in reference */ for (p = dl->forw; p!=0; p = p->forw) { if (p->op==JBR || p->op==CBR) { p->ref = 0; lp = labhash[p->labno % LABHS]; if (lp==0 || p->labno!=lp->labno) for (lp = dl->forw; lp!=0; lp = lp->forw) { if (lp->op==LABEL && p->labno==lp->labno) break; } if (lp) { tp = nonlab(lp)->back; if (tp!=lp) { setlab(p, tp->labno); lp = tp; } p->ref = lp; lp->refc++; } } } for (p = dl->forw; p!=0; p = p->forw) if (p->op==LABEL && p->refc==0 && (lp = nonlab(p))->op) decref(p); } static int nchange; static struct dlnod * codemove(struct dlnod *p) { struct dlnod *p1, *p2, *p3; #ifdef notyet struct dlnod *t, *tl; int n; #endif p1 = p; if (p1->op!=JBR || (p2 = p1->ref)==0) return(p1); while (p2->op == LABEL) if ((p2 = p2->back) == 0) return(p1); if (p2->op!=JBR) goto ivloop; if (p1==p2) return(p1); p2 = p2->forw; p3 = p1->ref; while (p3) { if (p3->op==JBR) { if (p1==p3 || p1->forw==p3 || p1->back==p3) return(p1); nchange++; p1->back->forw = p2; p1->dlip->qelem.q_back->qelem.q_forw = p2->dlip; p1->forw->back = p3; p1->dlip->qelem.q_forw->qelem.q_back = p3->dlip; p2->back->forw = p3->forw; p2->dlip->qelem.q_back->qelem.q_forw = p3->forw->dlip; p3->forw->back = p2->back; p3->dlip->qelem.q_forw->qelem.q_back = p2->back->dlip; p2->back = p1->back; p2->dlip->qelem.q_back = p1->dlip->qelem.q_back; p3->forw = p1->forw; p3->dlip->qelem.q_forw = p1->forw->dlip; decref(p1->ref); if (p1->dlip->type == IP_NODE) tfree(p1->dlip->ip_node); return(p2); } else p3 = p3->forw; } return(p1); ivloop: if (p1->forw->op!=LABEL) return(p1); return(p1); #ifdef notyet p3 = p2 = p2->forw; n = 16; do { if ((p3 = p3->forw) == 0 || p3==p1 || --n==0) return(p1); } while (p3->op!=CBR || p3->labno!=p1->forw->labno); do if ((p1 = p1->back) == 0) return(p); while (p1!=p3); p1 = p; tl = insertl(p1); p3->subop = revbr[p3->subop]; decref(p3->ref); p2->back->forw = p1; p3->forw->back = p1; p1->back->forw = p2; p1->forw->back = p3; t = p1->back; p1->back = p2->back; p2->back = t; t = p1->forw; p1->forw = p3->forw; p3->forw = t; p2 = insertl(p1->forw); p3->labno = p2->labno; p3->ref = p2; decref(tl); if (tl->refc<=0) nrlab--; nchange++; return(p3); #endif } static void iterate(struct p2env *p2e, struct dlnod *dl) { struct dlnod *p, *rp, *p1; extern int negrel[]; extern size_t negrelsize; int i; nchange = 0; for (p = dl->forw; p!=0; p = p->forw) { if ((p->op==JBR||p->op==CBR) && p->ref) { /* Resolves: * jbr L7 * ... * L7: jbr L8 */ rp = nonlab(p->ref); if (rp->op==JBR && rp->labno && p->labno!=rp->labno) { setlab(p, rp->labno); decref(p->ref); rp->ref->refc++; p->ref = rp->ref; nchange++; } } if (p->op==CBR && (p1 = p->forw)->op==JBR) { /* Resolves: * cbr L7 * jbr L8 * L7: */ rp = p->ref; do rp = rp->back; while (rp->op==LABEL); if (rp==p1) { decref(p->ref); p->ref = p1->ref; setlab(p, p1->labno); iprem(p1); p1->forw->back = p; p->forw = p1->forw; i = p->dlip->ip_node->n_left->n_op; if (i < EQ || i - EQ >= (int)negrelsize) comperr("deljumps: unexpected op"); p->dlip->ip_node->n_left->n_op = negrel[i - EQ]; nchange++; } } if (p->op == JBR) { /* Removes dead code */ while (p->forw && p->forw->op!=LABEL && p->forw->op!=EROU) { nchange++; if (p->forw->ref) decref(p->forw->ref); iprem(p->forw); p->forw = p->forw->forw; p->forw->back = p; } rp = p->forw; while (rp && rp->op==LABEL) { if (p->ref == rp) { p->back->forw = p->forw; p->forw->back = p->back; iprem(p); p = p->back; decref(rp); nchange++; break; } rp = rp->forw; } } if (p->op == JBR) { /* xjump(p); * needs tree rewrite; not yet */ p = codemove(p); } } } void deljumps(struct p2env *p2e) { struct interpass *ipole = &p2e->ipole; struct dlnod dln; MARK mark; markset(&mark); memset(&dln, 0, sizeof(dln)); listsetup(ipole, &dln); do { refcount(p2e, &dln); do { iterate(p2e, &dln); } while (nchange); #ifdef notyet comjump(); #endif } while (nchange); markfree(&mark); } void optdump(struct interpass *ip) { static char *nm[] = { "node", "prolog", "newblk", "epilog", "locctr", "deflab", "defnam", "asm" }; printf("type %s\n", nm[ip->type-1]); switch (ip->type) { case IP_NODE: #ifdef PCC_DEBUG fwalk(ip->ip_node, e2print, 0); #endif break; case IP_DEFLAB: printf("label " LABFMT "\n", ip->ip_lbl); break; case IP_ASM: printf(": %s\n", ip->ip_asm); break; } } /* * Build the basic blocks, algorithm 9.1, pp 529 in Compilers. * * Also fills the labelinfo struct with information about which bblocks * that contain which label. */ void bblocks_build(struct p2env *p2e) { struct interpass *ipole = &p2e->ipole; struct interpass *ip; struct basicblock *bb = NULL; int low, high; int count = 0; int i; BDEBUG(("bblocks_build (%p, %p)\n", &p2e->labinfo, &p2e->bbinfo)); low = p2e->ipp->ip_lblnum; high = p2e->epp->ip_lblnum; /* * First statement is a leader. * Any statement that is target of a jump is a leader. * Any statement that immediately follows a jump is a leader. */ DLIST_INIT(&p2e->bblocks, bbelem); DLIST_FOREACH(ip, ipole, qelem) { if (bb == NULL || (ip->type == IP_EPILOG) || (ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) { bb = tmpalloc(sizeof(struct basicblock)); bb->first = ip; SLIST_INIT(&bb->parents); bb->ch[0] = bb->ch[1] = NULL; bb->dfnum = 0; bb->dfparent = 0; bb->semi = 0; bb->ancestor = 0; bb->idom = 0; bb->samedom = 0; bb->bucket = NULL; bb->df = NULL; bb->dfchildren = NULL; bb->Aorig = NULL; bb->Aphi = NULL; SLIST_INIT(&bb->phi); bb->bbnum = count; DLIST_INSERT_BEFORE(&p2e->bblocks, bb, bbelem); count++; } bb->last = ip; if ((ip->type == IP_NODE) && (ip->ip_node->n_op == GOTO || ip->ip_node->n_op == CBRANCH)) bb = NULL; if (ip->type == IP_PROLOG) bb = NULL; } p2e->nbblocks = count; if (b2debug) { printf("Basic blocks in func: %d, low %d, high %d\n", count, low, high); DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { printf("bb(%d) %p: first %p last %p\n", bb->bbnum, bb, bb->first, bb->last); } } p2e->labinfo.low = low; p2e->labinfo.size = high - low + 1; p2e->labinfo.arr = tmpalloc(p2e->labinfo.size * sizeof(struct basicblock *)); for (i = 0; i < p2e->labinfo.size; i++) { p2e->labinfo.arr[i] = NULL; } p2e->bbinfo.size = count + 1; p2e->bbinfo.arr = tmpalloc(p2e->bbinfo.size * sizeof(struct basicblock *)); for (i = 0; i < p2e->bbinfo.size; i++) { p2e->bbinfo.arr[i] = NULL; } /* Build the label table */ DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { if (bb->first->type == IP_DEFLAB) p2e->labinfo.arr[bb->first->ip_lbl - low] = bb; } if (b2debug) { DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { printf("bblock %d\n", bb->bbnum); for (ip = bb->first; ip != bb->last; ip = DLIST_NEXT(ip, qelem)) { printip2(ip); } printip2(ip); } printf("Label table:\n"); for (i = 0; i < p2e->labinfo.size; i++) if (p2e->labinfo.arr[i]) printf("Label %d bblock %p\n", i+low, p2e->labinfo.arr[i]); } } /* * Build the control flow graph. */ void cfg_build(struct p2env *p2e) { /* Child and parent nodes */ struct cfgnode *cnode; struct cfgnode *pnode; struct basicblock *bb; DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { if (bb->first->type == IP_EPILOG) { break; } cnode = tmpalloc(sizeof(struct cfgnode)); pnode = tmpalloc(sizeof(struct cfgnode)); pnode->bblock = bb; if ((bb->last->type == IP_NODE) && (bb->last->ip_node->n_op == GOTO) && (bb->last->ip_node->n_left->n_op == ICON)) { if (bb->last->ip_node->n_left->n_lval - p2e->labinfo.low > p2e->labinfo.size) { comperr("Label out of range: %d, base %d", bb->last->ip_node->n_left->n_lval, p2e->labinfo.low); } cnode->bblock = p2e->labinfo.arr[bb->last->ip_node->n_left->n_lval - p2e->labinfo.low]; SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem); CHADD(bb, cnode); continue; } if ((bb->last->type == IP_NODE) && (bb->last->ip_node->n_op == CBRANCH)) { if (bb->last->ip_node->n_right->n_lval - p2e->labinfo.low > p2e->labinfo.size) comperr("Label out of range: %d", bb->last->ip_node->n_left->n_lval); cnode->bblock = p2e->labinfo.arr[bb->last->ip_node->n_right->n_lval - p2e->labinfo.low]; SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem); CHADD(bb, cnode); cnode = tmpalloc(sizeof(struct cfgnode)); pnode = tmpalloc(sizeof(struct cfgnode)); pnode->bblock = bb; } cnode->bblock = DLIST_NEXT(bb, bbelem); SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem); CHADD(bb, cnode); } } void cfg_dfs(struct basicblock *bb, unsigned int parent, struct bblockinfo *bbinfo) { struct cfgnode **cn; if (bb->dfnum != 0) return; bb->dfnum = ++dfsnum; bb->dfparent = parent; bbinfo->arr[bb->dfnum] = bb; FORCH(cn, bb->ch) cfg_dfs((*cn)->bblock, bb->dfnum, bbinfo); /* Don't bring in unreachable nodes in the future */ bbinfo->size = dfsnum + 1; } static bittype * setalloc(int nelem) { bittype *b; int sz = (nelem+NUMBITS-1)/NUMBITS; b = tmpalloc(sz * sizeof(bittype)); memset(b, 0, sz * sizeof(bittype)); return b; } /* * Algorithm 19.9, pp 414 from Appel. */ void dominators(struct p2env *p2e) { struct cfgnode *cnode; struct basicblock *bb, *y, *v; struct basicblock *s, *sprime, *p; int h, i; DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { bb->bucket = setalloc(p2e->bbinfo.size); bb->df = setalloc(p2e->bbinfo.size); bb->dfchildren = setalloc(p2e->bbinfo.size); } dfsnum = 0; cfg_dfs(DLIST_NEXT(&p2e->bblocks, bbelem), 0, &p2e->bbinfo); if (b2debug) { struct basicblock *bbb; struct cfgnode *ccnode, **cn; DLIST_FOREACH(bbb, &p2e->bblocks, bbelem) { printf("Basic block %d, parents: ", bbb->dfnum); SLIST_FOREACH(ccnode, &bbb->parents, cfgelem) { printf("%d, ", ccnode->bblock->dfnum); } printf("\nChildren: "); FORCH(cn, bbb->ch) printf("%d, ", (*cn)->bblock->dfnum); printf("\n"); } } for(h = p2e->bbinfo.size - 1; h > 1; h--) { bb = p2e->bbinfo.arr[h]; p = s = p2e->bbinfo.arr[bb->dfparent]; SLIST_FOREACH(cnode, &bb->parents, cfgelem) { if (cnode->bblock->dfnum ==0) continue; /* Ignore unreachable code */ if (cnode->bblock->dfnum <= bb->dfnum) sprime = cnode->bblock; else sprime = p2e->bbinfo.arr[ancestorwithlowestsemi (cnode->bblock, &p2e->bbinfo)->semi]; if (sprime->dfnum < s->dfnum) s = sprime; } bb->semi = s->dfnum; BITSET(s->bucket, bb->dfnum); link(p, bb); for (i = 1; i < p2e->bbinfo.size; i++) { if(TESTBIT(p->bucket, i)) { v = p2e->bbinfo.arr[i]; y = ancestorwithlowestsemi(v, &p2e->bbinfo); if (y->semi == v->semi) v->idom = p->dfnum; else v->samedom = y->dfnum; } } memset(p->bucket, 0, (p2e->bbinfo.size + 7)/8); } if (b2debug) { printf("Num\tSemi\tAncest\tidom\n"); DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { printf("%d\t%d\t%d\t%d\n", bb->dfnum, bb->semi, bb->ancestor, bb->idom); } } for(h = 2; h < p2e->bbinfo.size; h++) { bb = p2e->bbinfo.arr[h]; if (bb->samedom != 0) { bb->idom = p2e->bbinfo.arr[bb->samedom]->idom; } } DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { if (bb->idom != 0 && bb->idom != bb->dfnum) { BDEBUG(("Setting child %d of %d\n", bb->dfnum, p2e->bbinfo.arr[bb->idom]->dfnum)); BITSET(p2e->bbinfo.arr[bb->idom]->dfchildren, bb->dfnum); } } } struct basicblock * ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo) { struct basicblock *u = bblock; struct basicblock *v = bblock; while (v->ancestor != 0) { if (bbinfo->arr[v->semi]->dfnum < bbinfo->arr[u->semi]->dfnum) u = v; v = bbinfo->arr[v->ancestor]; } return u; } void link(struct basicblock *parent, struct basicblock *child) { child->ancestor = parent->dfnum; } void computeDF(struct p2env *p2e, struct basicblock *bblock) { struct cfgnode **cn; int h, i; FORCH(cn, bblock->ch) { if ((*cn)->bblock->idom != bblock->dfnum) BITSET(bblock->df, (*cn)->bblock->dfnum); } for (h = 1; h < p2e->bbinfo.size; h++) { if (!TESTBIT(bblock->dfchildren, h)) continue; computeDF(p2e, p2e->bbinfo.arr[h]); for (i = 1; i < p2e->bbinfo.size; i++) { if (TESTBIT(p2e->bbinfo.arr[h]->df, i) && (p2e->bbinfo.arr[i] == bblock || (bblock->dfnum != p2e->bbinfo.arr[i]->idom))) BITSET(bblock->df, i); } } } void printDF(struct p2env *p2e) { struct basicblock *bb; int i; printf("Dominance frontiers:\n"); DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { printf("bb %d : ", bb->dfnum); for (i=1; i < p2e->bbinfo.size;i++) { if (TESTBIT(bb->df,i)) { printf("%d ",i); } } printf("\n"); } } static struct basicblock *currbb; static struct interpass *currip; /* Helper function for findTemps, Find assignment nodes. */ static void searchasg(NODE *p, void *arg) { struct pvarinfo *pv; int tempnr; struct varstack *stacke; if (p->n_op != ASSIGN) return; if (p->n_left->n_op != TEMP) return; tempnr=regno(p->n_left)-defsites.low; BITSET(currbb->Aorig, tempnr); pv = tmpcalloc(sizeof(struct pvarinfo)); pv->next = defsites.arr[tempnr]; pv->bb = currbb; pv->n_type = p->n_left->n_type; defsites.arr[tempnr] = pv; if (SLIST_FIRST(&defsites.stack[tempnr])==NULL) { stacke=tmpcalloc(sizeof (struct varstack)); stacke->tmpregno=0; SLIST_INSERT_FIRST(&defsites.stack[tempnr],stacke,varstackelem); } } /* Walk the interpass looking for assignment nodes. */ void findTemps(struct interpass *ip) { if (ip->type != IP_NODE) return; currip = ip; walkf(ip->ip_node, searchasg, 0); } /* * Algorithm 19.6 from Appel. */ void placePhiFunctions(struct p2env *p2e) { struct basicblock *bb; struct basicblock *y; struct interpass *ip; int maxtmp, i, j, k; struct pvarinfo *n; struct cfgnode *cnode; TWORD ntype; struct pvarinfo *pv; struct phiinfo *phi; int phifound; bb = DLIST_NEXT(&p2e->bblocks, bbelem); defsites.low = ((struct interpass_prolog *)bb->first)->ip_tmpnum; bb = DLIST_PREV(&p2e->bblocks, bbelem); maxtmp = ((struct interpass_prolog *)bb->first)->ip_tmpnum; defsites.size = maxtmp - defsites.low + 1; defsites.arr = tmpcalloc(defsites.size*sizeof(struct pvarinfo *)); defsites.stack = tmpcalloc(defsites.size*sizeof(SLIST_HEAD(, varstack))); for (i=0;ibblocks, bbelem) { currbb = bb; ip = bb->first; bb->Aorig = setalloc(defsites.size); bb->Aphi = setalloc(defsites.size); while (ip != bb->last) { findTemps(ip); ip = DLIST_NEXT(ip, qelem); } /* Make sure we get the last statement in the bblock */ findTemps(ip); } /* For each variable */ for (i = 0; i < defsites.size; i++) { /* While W not empty */ while (defsites.arr[i] != NULL) { /* Remove some node n from W */ n = defsites.arr[i]; defsites.arr[i] = n->next; /* For each y in n->bb->df */ for (j = 0; j < p2e->bbinfo.size; j++) { if (!TESTBIT(n->bb->df, j)) continue; if (TESTBIT(p2e->bbinfo.arr[j]->Aphi, i)) continue; y=p2e->bbinfo.arr[j]; ntype = n->n_type; k = 0; /* Amount of predecessors for y */ SLIST_FOREACH(cnode, &y->parents, cfgelem) k++; /* Construct phi(...) */ phifound=0; SLIST_FOREACH(phi, &y->phi, phielem) { if (phi->tmpregno==i+defsites.low) phifound++; } if (phifound==0) { if (b2debug) printf("Phi in %d(%d) (%p) for %d\n", y->dfnum,y->bbnum,y,i+defsites.low); /* If no live in, no phi node needed */ if (!TESTBIT(y->in, (i+defsites.low-p2e->ipp->ip_tmpnum+MAXREGS))) { if (b2debug) printf("tmp %d bb %d unused, no phi\n", i+defsites.low, y->bbnum); /* No live in */ BITSET(p2e->bbinfo.arr[j]->Aphi, i); continue; } phi = tmpcalloc(sizeof(struct phiinfo)); phi->tmpregno=i+defsites.low; phi->size=k; phi->n_type=ntype; phi->intmpregno=tmpcalloc(k*sizeof(int)); SLIST_INSERT_LAST(&y->phi,phi,phielem); } else { if (b2debug) printf("Phi already in %d for %d\n",y->dfnum,i+defsites.low); } BITSET(p2e->bbinfo.arr[j]->Aphi, i); if (!TESTBIT(p2e->bbinfo.arr[j]->Aorig, i)) { pv = tmpalloc(sizeof(struct pvarinfo)); pv->bb = y; pv->n_type=ntype; pv->next = defsites.arr[i]; defsites.arr[i] = pv; } } } } } /* Helper function for renamevar. */ static void renamevarhelper(struct p2env *p2e,NODE *t,void *poplistarg) { SLIST_HEAD(, varstack) *poplist=poplistarg; int opty; int tempnr; int newtempnr; int x; struct varstack *stacke; if (t->n_op == ASSIGN && t->n_left->n_op == TEMP) { renamevarhelper(p2e,t->n_right,poplist); tempnr=regno(t->n_left)-defsites.low; newtempnr=p2e->epp->ip_tmpnum++; regno(t->n_left)=newtempnr; stacke=tmpcalloc(sizeof (struct varstack)); stacke->tmpregno=newtempnr; SLIST_INSERT_FIRST(&defsites.stack[tempnr],stacke,varstackelem); stacke=tmpcalloc(sizeof (struct varstack)); stacke->tmpregno=tempnr; SLIST_INSERT_FIRST(poplist,stacke,varstackelem); } else { if (t->n_op == TEMP) { tempnr=regno(t)-defsites.low; if (SLIST_FIRST(&defsites.stack[tempnr])!=NULL) { x=SLIST_FIRST(&defsites.stack[tempnr])->tmpregno; regno(t)=x; } } opty = optype(t->n_op); if (opty != LTYPE) renamevarhelper(p2e, t->n_left,poplist); if (opty == BITYPE) renamevarhelper(p2e, t->n_right,poplist); } } void renamevar(struct p2env *p2e,struct basicblock *bb) { struct interpass *ip; int h,j; SLIST_HEAD(, varstack) poplist; struct varstack *stacke; struct cfgnode *cfgn2, **cn; int tmpregno,newtmpregno; struct phiinfo *phi; SLIST_INIT(&poplist); SLIST_FOREACH(phi,&bb->phi,phielem) { tmpregno=phi->tmpregno-defsites.low; newtmpregno=p2e->epp->ip_tmpnum++; phi->newtmpregno=newtmpregno; stacke=tmpcalloc(sizeof (struct varstack)); stacke->tmpregno=newtmpregno; SLIST_INSERT_FIRST(&defsites.stack[tmpregno],stacke,varstackelem); stacke=tmpcalloc(sizeof (struct varstack)); stacke->tmpregno=tmpregno; SLIST_INSERT_FIRST(&poplist,stacke,varstackelem); } ip=bb->first; while (1) { if ( ip->type == IP_NODE) { renamevarhelper(p2e,ip->ip_node,&poplist); } if (ip==bb->last) break; ip = DLIST_NEXT(ip, qelem); } FORCH(cn, bb->ch) { j=0; SLIST_FOREACH(cfgn2, &(*cn)->bblock->parents, cfgelem) { if (cfgn2->bblock->dfnum==bb->dfnum) break; j++; } SLIST_FOREACH(phi,&(*cn)->bblock->phi,phielem) { phi->intmpregno[j]=SLIST_FIRST(&defsites.stack[phi->tmpregno-defsites.low])->tmpregno; } } for (h = 1; h < p2e->bbinfo.size; h++) { if (!TESTBIT(bb->dfchildren, h)) continue; renamevar(p2e,p2e->bbinfo.arr[h]); } SLIST_FOREACH(stacke,&poplist,varstackelem) { tmpregno=stacke->tmpregno; defsites.stack[tmpregno].q_forw=defsites.stack[tmpregno].q_forw->varstackelem.q_forw; } } enum pred_type { pred_unknown = 0, pred_goto = 1, pred_cond = 2, pred_falltrough = 3, } ; void removephi(struct p2env *p2e) { struct basicblock *bb,*bbparent; struct cfgnode *cfgn; struct phiinfo *phi; int i; struct interpass *ip; struct interpass *pip; TWORD n_type; enum pred_type complex = pred_unknown ; int label=0; int newlabel; DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { SLIST_FOREACH(phi,&bb->phi,phielem) { /* Look at only one, notice break at end */ i=0; SLIST_FOREACH(cfgn, &bb->parents, cfgelem) { bbparent=cfgn->bblock; pip=bbparent->last; complex = pred_unknown ; BDEBUG(("removephi: %p in %d",pip,bb->dfnum)); if (pip->type == IP_NODE && pip->ip_node->n_op == GOTO) { BDEBUG((" GOTO ")); label = (int)pip->ip_node->n_left->n_lval; complex = pred_goto ; } else if (pip->type == IP_NODE && pip->ip_node->n_op == CBRANCH) { BDEBUG((" CBRANCH ")); label = (int)pip->ip_node->n_right->n_lval; if (bb==p2e->labinfo.arr[label - p2e->ipp->ip_lblnum]) complex = pred_cond ; else complex = pred_falltrough ; } else if (DLIST_PREV(bb, bbelem) == bbparent) { complex = pred_falltrough ; } else { /* PANIC */ comperr("Assumption blown in rem-phi") ; } BDEBUG((" Complex: %d ",complex)) ; switch (complex) { case pred_goto: /* gotos can only go to this place. No bounce tab needed */ SLIST_FOREACH(phi,&bb->phi,phielem) { if (phi->intmpregno[i]>0) { n_type=phi->n_type; ip = ipnode(mkbinode(ASSIGN, mktemp(phi->newtmpregno, n_type), mktemp(phi->intmpregno[i],n_type), n_type)); BDEBUG(("(%p, %d -> %d) ", ip, phi->intmpregno[i], phi->newtmpregno)); DLIST_INSERT_BEFORE((bbparent->last), ip, qelem); } } break ; case pred_cond: /* Here, we need a jump pad */ newlabel=getlab2(); ip = tmpalloc(sizeof(struct interpass)); ip->type = IP_DEFLAB; /* Line number?? ip->lineno; */ ip->ip_lbl = newlabel; DLIST_INSERT_BEFORE((bb->first), ip, qelem); SLIST_FOREACH(phi,&bb->phi,phielem) { if (phi->intmpregno[i]>0) { n_type=phi->n_type; ip = ipnode(mkbinode(ASSIGN, mktemp(phi->newtmpregno, n_type), mktemp(phi->intmpregno[i],n_type), n_type)); BDEBUG(("(%p, %d -> %d) ", ip, phi->intmpregno[i], phi->newtmpregno)); DLIST_INSERT_BEFORE((bb->first), ip, qelem); } } /* add a jump to us */ ip = ipnode(mkunode(GOTO, mklnode(ICON, label, 0, INT), 0, INT)); DLIST_INSERT_BEFORE((bb->first), ip, qelem); pip->ip_node->n_right->n_lval=newlabel; if (!logop(pip->ip_node->n_left->n_op)) comperr("SSA not logop"); pip->ip_node->n_left->n_label=newlabel; break ; case pred_falltrough: if (bb->first->type == IP_DEFLAB) { label = bb->first->ip_lbl; BDEBUG(("falltrough label %d\n", label)); } else { comperr("BBlock has no label?") ; } /* * add a jump to us. We _will_ be, or already have, added code in between. * The code is created in the wrong order and switched at the insert, thus * comming out correctly */ ip = ipnode(mkunode(GOTO, mklnode(ICON, label, 0, INT), 0, INT)); DLIST_INSERT_AFTER((bbparent->last), ip, qelem); /* Add the code to the end, add a jump to us. */ SLIST_FOREACH(phi,&bb->phi,phielem) { if (phi->intmpregno[i]>0) { n_type=phi->n_type; ip = ipnode(mkbinode(ASSIGN, mktemp(phi->newtmpregno, n_type), mktemp(phi->intmpregno[i],n_type), n_type)); BDEBUG(("(%p, %d -> %d) ", ip, phi->intmpregno[i], phi->newtmpregno)); DLIST_INSERT_AFTER((bbparent->last), ip, qelem); } } break ; default: comperr("assumption blown, complex is %d\n", complex) ; } BDEBUG(("\n")); i++; } break; } } } /* * Remove unreachable nodes in the CFG. */ void remunreach(struct p2env *p2e) { struct basicblock *bb, *nbb; struct interpass *next, *ctree; bb = DLIST_NEXT(&p2e->bblocks, bbelem); while (bb != &p2e->bblocks) { nbb = DLIST_NEXT(bb, bbelem); /* Code with dfnum 0 is unreachable */ if (bb->dfnum != 0) { bb = nbb; continue; } /* Need the epilogue node for other parts of the compiler, set its label to 0 and backend will handle it. */ if (bb->first->type == IP_EPILOG) { bb->first->ip_lbl = 0; bb = nbb; continue; } next = bb->first; do { ctree = next; next = DLIST_NEXT(ctree, qelem); if (ctree->type == IP_NODE) tfree(ctree->ip_node); DLIST_REMOVE(ctree, qelem); } while (ctree != bb->last); DLIST_REMOVE(bb, bbelem); bb = nbb; } } static void printip2(struct interpass *ip) { static char *foo[] = { 0, "NODE", "PROLOG", "STKOFF", "EPILOG", "DEFLAB", "DEFNAM", "ASM" }; struct interpass_prolog *ipplg, *epplg; unsigned i; if (ip->type > MAXIP) printf("IP(%d) (%p): ", ip->type, ip); else printf("%s (%p): ", foo[ip->type], ip); switch (ip->type) { case IP_NODE: printf("\n"); #ifdef PCC_DEBUG fwalk(ip->ip_node, e2print, 0); break; #endif case IP_PROLOG: ipplg = (struct interpass_prolog *)ip; printf("%s %s regs", ipplg->ipp_name, ipplg->ipp_vis ? "(local)" : ""); for (i = 0; i < NIPPREGS; i++) printf("%s0x%lx", i? ":" : " ", (long) ipplg->ipp_regs[i]); printf(" autos %d mintemp %d minlbl %d\n", ipplg->ipp_autos, ipplg->ip_tmpnum, ipplg->ip_lblnum); break; case IP_EPILOG: epplg = (struct interpass_prolog *)ip; printf("%s %s regs", epplg->ipp_name, epplg->ipp_vis ? "(local)" : ""); for (i = 0; i < NIPPREGS; i++) printf("%s0x%lx", i? ":" : " ", (long) epplg->ipp_regs[i]); printf(" autos %d mintemp %d minlbl %d\n", epplg->ipp_autos, epplg->ip_tmpnum, epplg->ip_lblnum); break; case IP_DEFLAB: printf(LABFMT "\n", ip->ip_lbl); break; case IP_DEFNAM: printf("\n"); break; case IP_ASM: printf("%s\n", ip->ip_asm); break; default: break; } } void printip(struct interpass *pole) { struct interpass *ip; DLIST_FOREACH(ip, pole, qelem) printip2(ip); } #ifdef PCC_DEBUG void flownodeprint(NODE *p,FILE *flowdiagramfile); void flownodeprint(NODE *p,FILE *flowdiagramfile) { int opty; char *o; fprintf(flowdiagramfile,"{"); o=opst[p->n_op]; while (*o != 0) { if (*o=='<' || *o=='>') fputc('\\',flowdiagramfile); fputc(*o,flowdiagramfile); o++; } switch( p->n_op ) { case REG: fprintf(flowdiagramfile, " %s", rnames[p->n_rval] ); break; case TEMP: fprintf(flowdiagramfile, " %d", regno(p)); break; case XASM: case XARG: fprintf(flowdiagramfile, " '%s'", p->n_name); break; case ICON: case NAME: case OREG: fprintf(flowdiagramfile, " " ); adrput(flowdiagramfile, p ); break; case STCALL: case USTCALL: case STARG: case STASG: fprintf(flowdiagramfile, " size=%d", p->n_stsize ); fprintf(flowdiagramfile, " align=%d", p->n_stalign ); break; } opty = optype(p->n_op); if (opty != LTYPE) { fprintf(flowdiagramfile,"| {"); flownodeprint(p->n_left,flowdiagramfile); if (opty == BITYPE) { fprintf(flowdiagramfile,"|"); flownodeprint(p->n_right,flowdiagramfile); } fprintf(flowdiagramfile,"}"); } fprintf(flowdiagramfile,"}"); } void printflowdiagram(struct p2env *p2e, char *type) { struct basicblock *bbb; struct cfgnode **cn; struct interpass *ip; struct interpass_prolog *plg; struct phiinfo *phi; char *name; char *filename; int filenamesize; char *ext=".dot"; FILE *flowdiagramfile; if (!g2debug) return; bbb=DLIST_NEXT(&p2e->bblocks, bbelem); ip=bbb->first; if (ip->type != IP_PROLOG) return; plg = (struct interpass_prolog *)ip; name=plg->ipp_name; filenamesize=strlen(name)+1+strlen(type)+strlen(ext)+1; filename=tmpalloc(filenamesize); snprintf(filename,filenamesize,"%s-%s%s",name,type,ext); flowdiagramfile=fopen(filename,"w"); fprintf(flowdiagramfile,"digraph {\n"); fprintf(flowdiagramfile,"rankdir=LR\n"); DLIST_FOREACH(bbb, &p2e->bblocks, bbelem) { ip=bbb->first; fprintf(flowdiagramfile,"bb%p [shape=record ",bbb); if (ip->type==IP_PROLOG) fprintf(flowdiagramfile,"root "); fprintf(flowdiagramfile,"label=\""); SLIST_FOREACH(phi,&bbb->phi,phielem) { fprintf(flowdiagramfile,"Phi %d|",phi->tmpregno); } while (1) { switch (ip->type) { case IP_NODE: flownodeprint(ip->ip_node,flowdiagramfile); break; case IP_DEFLAB: fprintf(flowdiagramfile,"Label: %d", ip->ip_lbl); break; case IP_PROLOG: plg = (struct interpass_prolog *)ip; fprintf(flowdiagramfile,"%s %s",plg->ipp_name,type); break; } fprintf(flowdiagramfile,"|"); fprintf(flowdiagramfile,"|"); if (ip==bbb->last) break; ip = DLIST_NEXT(ip, qelem); } fprintf(flowdiagramfile,"\"]\n"); FORCH(cn, bbb->ch) { char *color="black"; struct interpass *pip=bbb->last; if (pip->type == IP_NODE && pip->ip_node->n_op == CBRANCH) { int label = (int)pip->ip_node->n_right->n_lval; if ((*cn)->bblock==p2e->labinfo.arr[label - p2e->ipp->ip_lblnum]) color="red"; } fprintf(flowdiagramfile,"bb%p -> bb%p [color=%s]\n", bbb,(*cn)->bblock,color); } } fprintf(flowdiagramfile,"}\n"); fclose(flowdiagramfile); } #endif /* walk all the programm */ void WalkAll(struct p2env* p2e, void (*f) (NODE*, void*), void* arg, int type) { struct interpass *ipole = &p2e->ipole; struct interpass *ip ; if (0 != type) { DLIST_FOREACH(ip, ipole, qelem) { if (ip->type == IP_NODE && ip->ip_node->n_op == type) walkf(ip->ip_node, f, arg) ; } } else { DLIST_FOREACH(ip, ipole, qelem) { if (ip->type == IP_NODE) walkf(ip->ip_node, f, arg) ; } } } #if 0 static int is_goto_label(struct interpass*g, struct interpass* l) { if (!g || !l) return 0 ; if (g->type != IP_NODE) return 0 ; if (l->type != IP_DEFLAB) return 0 ; if (g->ip_node->n_op != GOTO) return 0 ; if (g->ip_node->n_left->n_lval != l->ip_lbl) return 0 ; return 1 ; } #endif /* * iterate over the basic blocks. * In case a block has only one successor and that one has only one pred, and the link is a goto: * place the second one immediately behind the first one (in terms of nodes, means cut&resplice). * This should take care of a lot of jumps. * one problem: Cannot move the first or last basic block (prolog/epilog). This is taken care of by * moving block #1 to #2, not #2 to #1 * More complex (on the back cooker;) : first coalesc the inner loops (L1 cache), then go from inside out. */ static unsigned long count_blocks(struct p2env* p2e) { struct basicblock* bb ; unsigned long count = 0 ; DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { ++count ; } return count ; } struct block_map { struct basicblock* block ; unsigned long index ; unsigned long thread ; } ; static unsigned long map_blocks(struct p2env* p2e, struct block_map* map, unsigned long count) { struct basicblock* bb ; unsigned long indx = 0 ; int ignore = 2 ; unsigned long thread ; unsigned long changes ; DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { map[indx].block = bb ; map[indx].index = indx ; /* ignore the first 2 labels, maybe up to 3 BBs */ if (ignore) { if (bb->first->type == IP_DEFLAB) --ignore; map[indx].thread = 1 ; /* these are "fixed" */ } else map[indx].thread = 0 ; indx++ ; } thread = 1 ; do { changes = 0 ; for (indx=0; indx < count; indx++) { /* find block without trace */ if (map[indx].thread == 0) { /* do new thread */ struct cfgnode **cn ; struct basicblock *block2 = 0; unsigned long i ; unsigned long added ; BDEBUG (("new thread %ld at block %ld\n", thread, indx)) ; bb = map[indx].block ; do { added = 0 ; for (i=0; i < count; i++) { if (map[i].block == bb && map[i].thread == 0) { map[i].thread = thread ; BDEBUG(("adding block %ld to trace %ld\n", i, thread)) ; changes ++ ; added++ ; /* * pick one from followers. For now (simple), pick the * one who is directly following us. If none of that exists, * this code picks the last one. */ FORCH(cn, bb->ch) { block2=(*cn)->bblock ; #if 1 if (i+1 < count && map[i+1].block == block2) break ; /* pick that one */ #else if (block2) break ; #endif } if (block2) bb = block2 ; } } } while (added) ; thread++ ; } } } while (changes); /* Last block is also a thread on it's own, and the highest one. */ /* thread++ ; map[count-1].thread = thread ; */ if (b2debug) { printf("Threads\n"); for (indx=0; indx < count; indx++) { printf("Block #%ld (lbl %d) Thread %ld\n", indx, map[indx].block->first->ip_lbl, map[indx].thread); } } return thread ; } void TraceSchedule(struct p2env* p2e) { struct block_map* map ; unsigned long block_count = count_blocks(p2e); unsigned long i ; unsigned long threads; struct interpass *front, *back ; map = tmpalloc(block_count * sizeof(struct block_map)); threads = map_blocks(p2e, map, block_count) ; back = map[0].block->last ; for (i=1; i < block_count; i++) { /* collect the trace */ unsigned long j ; unsigned long thread = map[i].thread ; if (thread) { BDEBUG(("Thread %ld\n", thread)) ; for (j=i; j < block_count; j++) { if (map[j].thread == thread) { front = map[j].block->first ; BDEBUG(("Trace %ld, old BB %ld, next BB %ld\t", thread, i, j)) ; BDEBUG(("Label %d\n", front->ip_lbl)) ; DLIST_NEXT(back, qelem) = front ; DLIST_PREV(front, qelem) = back ; map[j].thread = 0 ; /* done */ back = map[j].block->last ; DLIST_NEXT(back, qelem) = 0 ; } } } } DLIST_NEXT(back, qelem) = &(p2e->ipole) ; DLIST_PREV(&p2e->ipole, qelem) = back ; } static void add_labels(struct p2env* p2e) { struct interpass *ipole = &p2e->ipole ; struct interpass *ip ; DLIST_FOREACH(ip, ipole, qelem) { if (ip->type == IP_NODE && ip->ip_node->n_op == CBRANCH) { struct interpass *n = DLIST_NEXT(ip, qelem); if (n && n->type != IP_DEFLAB) { struct interpass* lab; int newlabel=getlab2() ; BDEBUG(("add_label L%d\n", newlabel)); lab = tmpalloc(sizeof(struct interpass)); lab->type = IP_DEFLAB; /* Line number?? ip->lineno; */ lab->ip_lbl = newlabel; DLIST_INSERT_AFTER(ip, lab, qelem); } } } } /* node map */ #ifdef ENABLE_NEW struct node_map { NODE* node ; /* the node */ unsigned int node_num ; /* node is equal to that one */ unsigned int var_num ; /* node computes this variable */ } ; static unsigned long nodes_counter ; static void node_map_count_walker(NODE* n, void* x) { nodes_counter ++ ; } static void do_cse(struct p2env* p2e) { nodes_counter = 0 ; WalkAll(p2e, node_map_count_walker, 0, 0) ; BDEBUG(("Found %ld nodes\n", nodes_counter)) ; } #endif #define BITALLOC(ptr,all,sz) { \ int sz__s = BIT2BYTE(sz); ptr = all(sz__s); memset(ptr, 0, sz__s); } #define VALIDREG(p) (p->n_op == REG && TESTBIT(validregs, regno(p))) #define XCHECK(x) if (x < 0 || x >= xbits) printf("x out of range %d\n", x) #define RUP(x) (((x)+NUMBITS-1)/NUMBITS) #define SETCOPY(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] = f[i] #define SETSET(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] |= f[i] #define SETCLEAR(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] &= ~f[i] #define SETCMP(v,t,f,i,n) for (i = 0; i < RUP(n); i++) \ if (t[i] != f[i]) v = 1 static int xxx, xbits; /* * Set/clear long term liveness for regs and temps. */ static void unionize(NODE *p, struct basicblock *bb, int suboff) { int o, ty; if ((o = p->n_op) == TEMP || VALIDREG(p)) { int b = regno(p); if (o == TEMP) b = b - suboff + MAXREGS; XCHECK(b); BITSET(bb->gen, b); } if (asgop(o)) { if (p->n_left->n_op == TEMP || VALIDREG(p)) { int b = regno(p->n_left); if (p->n_left->n_op == TEMP) b = b - suboff + MAXREGS; XCHECK(b); BITCLEAR(bb->gen, b); BITSET(bb->killed, b); unionize(p->n_right, bb, suboff); return; } } ty = optype(o); if (ty != LTYPE) unionize(p->n_left, bb, suboff); if (ty == BITYPE) unionize(p->n_right, bb, suboff); } /* * Found an extended assembler node, so growel out gen/killed nodes. */ static void xasmionize(NODE *p, void *arg) { struct basicblock *bb = arg; int cw, b; if (p->n_op == ICON && p->n_type == STRTY) return; /* dummy end marker */ cw = xasmcode(p->n_name); if (XASMVAL(cw) == 'n' || XASMVAL(cw) == 'm') return; /* no flow analysis */ p = p->n_left; if (XASMVAL(cw) == 'g' && p->n_op != TEMP && p->n_op != REG) return; /* no flow analysis */ b = regno(p); #if 0 if (XASMVAL(cw) == 'r' && p->n_op == TEMP) addnotspill(b); #endif #define MKTOFF(r) ((r) - xxx) if (XASMISOUT(cw)) { if (p->n_op == TEMP) { BITCLEAR(bb->gen, MKTOFF(b)); BITSET(bb->killed, MKTOFF(b)); } else if (p->n_op == REG) { BITCLEAR(bb->gen, b); BITSET(bb->killed, b); } else uerror("bad xasm node type %d", p->n_op); } if (XASMISINP(cw)) { if (p->n_op == TEMP) { BITSET(bb->gen, MKTOFF(b)); } else if (p->n_op == REG) { BITSET(bb->gen, b); } else if (optype(p->n_op) != LTYPE) { if (XASMVAL(cw) == 'r') uerror("couldn't find available register"); else uerror("bad xasm node type2"); } } } /* * Do variable liveness analysis. Only analyze the long-lived * variables, and save the live-on-exit temporaries in a bit-field * at the end of each basic block. This bit-field is later used * when doing short-range liveness analysis in Build(). */ void liveanal(struct p2env *p2e) { struct basicblock *bb; struct interpass *ip; bittype *saved; int i, mintemp, again; xbits = p2e->epp->ip_tmpnum - p2e->ipp->ip_tmpnum + MAXREGS; mintemp = p2e->ipp->ip_tmpnum; /* Just fetch space for the temporaries from heap */ DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { BITALLOC(bb->gen,tmpalloc,xbits); BITALLOC(bb->killed,tmpalloc,xbits); BITALLOC(bb->in,tmpalloc,xbits); BITALLOC(bb->out,tmpalloc,xbits); } BITALLOC(saved,tmpalloc,xbits); xxx = mintemp; /* * generate the gen-killed sets for all basic blocks. */ DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { for (ip = bb->last; ; ip = DLIST_PREV(ip, qelem)) { /* gen/killed is 'p', this node is 'n' */ if (ip->type == IP_NODE) { if (ip->ip_node->n_op == XASM) flist(ip->ip_node->n_left, xasmionize, bb); else unionize(ip->ip_node, bb, mintemp); } if (ip == bb->first) break; } memcpy(bb->in, bb->gen, BIT2BYTE(xbits)); #ifdef PCC_DEBUG #define PRTRG(x) printf("%d ", i < MAXREGS ? i : i + p2e->ipp->ip_tmpnum-MAXREGS) if (b2debug > 1) { printf("basic block %d\ngen: ", bb->bbnum); for (i = 0; i < xbits; i++) if (TESTBIT(bb->gen, i)) PRTRG(i); printf("\nkilled: "); for (i = 0; i < xbits; i++) if (TESTBIT(bb->killed, i)) PRTRG(i); printf("\n"); } #endif } /* do liveness analysis on basic block level */ do { struct cfgnode **cn; int j; again = 0; /* XXX - loop should be in reversed execution-order */ DLIST_FOREACH_REVERSE(bb, &p2e->bblocks, bbelem) { SETCOPY(saved, bb->out, j, xbits); FORCH(cn, bb->ch) { SETSET(bb->out, cn[0]->bblock->in, j, xbits); } SETCMP(again, saved, bb->out, j, xbits); SETCOPY(saved, bb->in, j, xbits); SETCOPY(bb->in, bb->out, j, xbits); SETCLEAR(bb->in, bb->killed, j, xbits); SETSET(bb->in, bb->gen, j, xbits); SETCMP(again, saved, bb->in, j, xbits); } } while (again); #ifdef PCC_DEBUG DLIST_FOREACH(bb, &p2e->bblocks, bbelem) { if (b2debug) { printf("all basic block %d\nin: ", bb->bbnum); for (i = 0; i < xbits; i++) if (TESTBIT(bb->in, i)) PRTRG(i); printf("\nout: "); for (i = 0; i < xbits; i++) if (TESTBIT(bb->out, i)) PRTRG(i); printf("\n"); } } #endif }