Logo Search packages:      
Sourcecode: pcc version File versions  Download package

optim2.c

/*    $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 <string.h>
#include <stdlib.h>

#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
00252 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;i<defsites.size;i++)
            SLIST_INIT(&defsites.stack[i]);     
      
      /* Find all defsites */
      DLIST_FOREACH(bb, &p2e->bblocks, 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 ;
}

01769 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
}

Generated by  Doxygen 1.6.0   Back to index