regalloc.c

<B>Digital的Unix操作系统VAX 4.2源码</B>

	  regtab[i] = NULL;
        }

  tabletop = -1;
  if (topregvar < maxregvar - 1)
    for (i = 0; i < VARTABSIZE; i++)
      for (p = vartable[i]; p; p = p->link)
	{
	  entableaddr(p);
	  if ((!p->mixedtype) &&
	      (p->vstg != STGARG) &&
	      !((p->vstg == STGCOMMON) && ((!p->fixed) || commonunusable)))
	    for (q = p->varlist; q; q = q->link)
	      entablevar(q);
	}

  for (i = 0; (i <= tabletop) && (topregvar + 1 < maxregvar); i++)
    {
      if (inregtab(rt[i]) || (loopcost && rt[i]->isset))
	continue;
      topregvar++;
      regtab[topregvar] = rp = ALLOC(regdata);
      rp->vstg = rt[i]->vstg;
      rp->vtype = rt[i]->vtype;
      rp->memno = rt[i]->memno;
      rp->memoffset = rt[i]->memoffset;
      rp->refs = rt[i]->refs;
      rp->stgp = (Addrp) cpexpr(rt[i]->stgp);
      rp->isarrayarg = rt[i]->isarrayarg;
      rp->istemp = rt[i]->istemp;
      rp->isset = rt[i]->isset;
      rp->setfirst = rt[i]->setfirst;
    }

  for (i = toplcv + 1; i <= topregvar; i++)
    {
      if (rp = regtab[i])
	if (rp->isarrayarg)
	  {
	    ap = ALLOC(Addrblock);
	    ap->tag = TADDR;
	    ap->vstg = STGREG;
	    ap->vtype = TYADDR;
	    ap->vclass = CLVAR;
	    ap->memno = regnum[i];
	    ap->memoffset = ICON(0);

	    ap1 = ALLOC(Addrblock);
	    ap1->tag = TADDR;
	    ap1->vstg = rp->vstg;
	    ap1->vtype = rp->vtype;
	    ap1->vclass = CLVAR;
	    ap1->memno = rp->memno;
	    ap1->memoffset = ICON(0);

	    insertassign(dohead, ap, addrof(ap1));
	  }
        else if (!(rp->setfirst && rp->istemp))
	  {
	    if (rp->istemp)
	      for (sp = newcode; sp && sp != dohead; sp = sp->next)
	        if (sp->type == SKEQ)
		  {
		    ap = (Addrp) sp->expr->exprblock.leftp;
		    if ((ap->vstg == rp->vstg) && (ap->memno == rp->memno) &&
			fixedaddress(ap) &&
			(ap->memoffset->constblock.const.ci == rp->memoffset))
		      {
			changetoreg(ap, i);
			goto L1;
		      }
		  }
	    ap = (Addrp) cpexpr(rp->stgp);
	    changetoreg(ap, i);
	    insertassign(dohead, ap, cpexpr(rp->stgp));
	  }
L1:;
    }

  for (i = toplcv + 1; i <= topregvar; i++)
    if (rp = regtab[i])
      if (rp->isset && !(rp->istemp || rp->isarrayarg))
	{
	  ap = (Addrp) cpexpr(rp->stgp);
	  changetoreg(ap, i);
	  appendassign(doend, cpexpr(rp->stgp), ap);
	}

  docount = 1;
  clearmems();
  setregs();
  sp = dohead->next;
  if (loopcost)
    for (i = toptrack + 1; i <= topregvar; i++)
      if ((rp = regtab[i]) && !rp->isarrayarg)
	{
	  ap = (Addrp) cpexpr(rp->stgp);
	  changetoreg(ap, i);
	  insertassign(sp, cpexpr(rp->stgp), ap);
	}

  for ( sp = dohead->next;
	docount || sp->type != SKNULL;
	sp = sp->next)
    if (docount > 1)
      switch (sp->type)
	{
	case SKDOHEAD:
	  docount++;
	  break;

	case SKENDDO:
	  if (--docount == 1)
	    {
	      /*
	       * Remove redundant stores to memory.
	       */
	      sp1 = sp->nullslot->next;
	      while (sp1)
		{
		  if (regtomem(sp1))
		    {
		      ap = (Addrp) sp1->expr->exprblock.rightp;
		      sp2 = sp1->next;
		      for (i = toplcv + 2; i <= toptrack; i++)
			if (regtab[i] && (regnum[i] == ap->memno))
			  {
			    deleteslot(sp1);
			    break;
			  }
		      sp1 = sp2;
		    }
		  else
		    sp1 = NULL;
		}

	      /*
	       * Restore register variables (complement to DOHEAD code).
	       */
	      sp1 = sp->nullslot->next;
	      for (i = toplcv + 1; i <= topregvar; i++)
		if (rp = regtab[i])
		  if (!regdefined[i])
		    if (i >= dqp->nregvars || !samevar(rp, dqp->reg[i]))
		      {
			ap = (Addrp) cpexpr(rp->stgp);
			changetoreg(ap, i);
			insertassign(sp1, ap, cpexpr(rp->stgp));
			regdefined[i] = YES;
		      }

	      clearmems();
	      if (toplcv + 1 < maxregvar)
		memdefined[toplcv + 1] = YES;
	      sp = sp1->prev;
	    }
	  break;
	}
      else
	{
	  setregs();
	  for (i = 0; i <= MAXREGVAR; i++)
	    regaltered[i] = NO;
	  globalbranch = NO;

	  switch (sp->type)
	    {
	    case SKLABEL:
	      clearmems();
	      break;

	    case SKGOTO:
	      if (!locallabel(sp->label))
		gensetall(sp);
	      break;

	    case SKENDDO:
	      docount = 0;
	      break;

	    case SKRETURN:
	      gensetreturn(sp);
	      linearcode = YES;
	      regwrite(sp, sp->expr);
	      linearcode = NO;
	      break;

	    case SKDOHEAD:
	      /*
	       * If one of the current loop's register variables is not in
	       * register in an inner loop, we must save it.  It's a pity
	       * we don't save enough info to optimize this properly...
	       */
	      for (dqp = dqptr->down; dqp; dqp = dqp->down)
		if (dqp->dohead == sp)
		  break;
	      if (dqp == NULL)
		fatal("confused in alreg loop analysis");
	      for (i = toplcv + 1; i <= topregvar; i++)
		if (rp = regtab[i])
		  if (!memdefined[i])
		    if (i >= dqp->nregvars || !samevar(rp, dqp->reg[i]) ||
			(rp->vstg == STGCOMMON)
		       )
		      {
			ap = (Addrp) cpexpr(rp->stgp);
			changetoreg(ap, i);
			insertassign(sp, cpexpr(rp->stgp), ap);
			memdefined[i] = YES;
			regdefined[i] = NO;
		      }

	      docount++;
	      globalbranch = YES;
	      break;

	    case SKEQ:
	    case SKCALL:
	    case SKSTOP:
	    case SKPAUSE:
	      linearcode = YES;
	      regwrite(sp, sp->expr);
	      for (i = toplcv + 1; i <= topregvar; i++)
		if (!regdefined[i] && ((rp = regtab[i]) && rp->isset))
		  {
		    ap = (Addrp) cpexpr(rp->stgp);
		    changetoreg(ap, i);
		    appendassign(sp, ap, cpexpr(rp->stgp));
		    sp = sp->next;
		    regdefined[i] = YES;
		  }
	      linearcode = NO;

	      /*
	       * Eliminate redundant register moves.
	       */
	      if (regtoreg(sp))
		{
		  ap = (Addrp) sp->expr->exprblock.leftp;
	          sp1 = sp->prev;
		  for (i = toplcv + 1; i <= toptrack; i++)
		    if (regtab[i] && (regnum[i] == ap->memno))
		      {
			deleteslot(sp);
			sp = sp1;
			break;
		      }
		}
	      break;

	    case SKARIF:
	      if (!locallabel(LM) || !locallabel(LZ) || !locallabel(LP))
		{
		  gensetall(sp);
		  globalbranch = YES;
		}
	      regwrite(sp, sp->expr);
	      break;

	    case SKASGOTO:
	      gensetall(sp);
	      globalbranch = YES;
	      regwrite(sp, sp->expr);
	      break;

	    case SKCMGOTO:
	      lp = (struct Labelblock **) sp->ctlinfo;
	      for (i = 0; i < sp->label; i++, lp++)
		if (!locallabel((*lp)->labelno))
		  {
		    gensetall(sp);
		    globalbranch = YES;
		    break;
		  }
	      regwrite(sp, sp->expr);
	      break;

	    case SKIFN:
	    case SKIOIFN:
	      if (!locallabel(sp->label))
		{
		  gensetall(sp);
		  globalbranch = YES;
		}
	      regwrite(sp, sp->expr);
	      break;

	    case SKNULL:
	    case SKASSIGN:
	      break;

	    default:
	      badthing ("SKtype","alreg-3",sp->type);
	    }
	  
	  for (i = toplcv + 1; i <= topregvar; i++)
	    if (regaltered[i])
	      memdefined[i] = NO;
	}

  if (topregvar + 1 > highregvar)
    highregvar = topregvar + 1;
  dqptr->nregvars = topregvar + 1;
  for (i = 0; i <= topregvar; i++)
    if (rp = regtab[i])
      {
	dqptr->reg[i] = regp = ALLOC(regnode);
	regp->vstg = rp->vstg;
	regp->vtype = rp->vtype;
	regp->memno = rp->memno;
	regp->memoffset = rp->memoffset;
	regp->isarrayarg = rp->isarrayarg;
	frexpr(rp->stgp);
	free((char *) rp);
	regtab[i] = NULL;
      }

  while (tabletop >= 0)
    free((char *) rt[tabletop--]);
  freelabtab();
  freevartab();
  return;
}



LOCAL scanvars(p)
expptr p;

{
  Addrp ap;
  ADDRNODE *addrinfo;
  VARNODE *varinfo;
  chainp args;
  VARNODE *q;

  if (p == NULL) return;

  switch (p->tag)
    {
    case TCONST:
      return;

    case TEXPR:
      switch (p->exprblock.opcode)
	{
	case OPASSIGN:
	  scanassign(p);
	  return;

	case OPPLUSEQ:
	case OPSTAREQ:
	  scanopeq(p);
	  return;

	case OPCALL:
	  scancall(p);
	  return;

	default:
	  scanvars(p->exprblock.vleng);
	  scanvars(p->exprblock.leftp);
	  scanvars(p->exprblock.rightp);
	  return;
	}

    case TADDR:
      ap = (Addrp) p;
      scanvars(ap->vleng);
      scanvars(ap->memoffset);
      if (!ISVAR(ap)) return;

      addrinfo = getaddr(ap);
      if (fixedaddress(ap))
	{
	  if (ISREGTYPE(ap->vtype))
	    {
	      varinfo = getvar(addrinfo, ap);
	      varinfo->isused = YES;
	    }
	}
      else
	{
	  addrinfo->freeuse = YES;
	  for (q = addrinfo->varlist; q; q = q->link)
	    q->isused = YES;
	}
      return;

    case TLIST:
      for (args = p->listblock.listp; args; args = args->nextp)
	scanvars(args->datap);
      return;

    default:
      badtag ("regalloc:scanvars", p->tag);
    }
}



LOCAL scanassign(ep)
Exprp ep;

{
  Addrp lhs;
  VARNODE *varinfo;
  ADDRNODE *addrinfo;

  scanvars(ep->rightp);
  if (ep->leftp->tag == TADDR)
    {
      lhs = (Addrp) ep->leftp;
      scanvars(lhs->vleng);
      scanvars(lhs->memoffset);
      if ((lhs->vstg == STGREG) || (lhs->vstg == STGPREG))
	return;
      if (ISVAR(lhs))
	{
          addrinfo = getaddr(lhs);
          addrinfo->isset = YES;
          if (fixedaddress(lhs) && ISREGTYPE(lhs->vtype))
	    {
	      varinfo = getvar(addrinfo, lhs);
	      if (addrinfo->freeuse) varinfo->isused = YES;
	      varinfo->isset = YES;
	      if (!addrinfo->freeuse && !varinfo->isused)
	        varinfo->setfirst = YES;
	    }
        }
    }
  else
    badtag ("regalloc:scanassign", ep->leftp->tag);
}



LOCAL scanopeq(ep)
Exprp ep;

{
  Addrp lhs;
  ADDRNODE *addrinfo;
  VARNODE *varinfo;

  scanvars(ep->rightp);
  if (ep->leftp->tag == TADDR)
    {
      lhs = (Addrp) ep->leftp;
      scanvars(lhs->vleng);
      scanvars(lhs->memoffset);
      if ((lhs->vstg == STGREG) || (lhs->vstg == STGPREG))
	return;
      if (ISVAR(lhs))
	{
          addrinfo = getaddr(lhs);
          addrinfo->isset = YES;
          if (fixedaddress(lhs))
	    {
	      if (ISREGTYPE(lhs->vtype))
	        {
	          varinfo = getvar(addrinfo, lhs);
	          varinfo->isused = YES;
	          varinfo->isset = YES;
	        }
	    }
        }
      else
	addrinfo->freeuse = YES;
    }
  else
    badtag ("regalloc:scanopeq", ep->leftp->tag);
}



LOCAL scancall(ep)
Exprp ep;

{
  Addrp lhs;
  chainp args;
  Addrp ap;
  VARNODE *varinfo;
  ADDRNODE *addrinfo;

  lhs = (Addrp) ep->leftp;
  scanvars(lhs->vleng);
  scanvars(lhs->memoffset);

  if (ep->rightp == NULL) return;

  if (lhs->vstg != STGINTR)
    {
      args = ep->rightp->listblock.listp;
      for (; args; args = args->nextp)
	{
	  if (args->datap->tag == TADDR)
	    {
	      ap = (Addrp) args->datap;
	      scanvars(ap->vleng);
	      scanvars(ap->memoffset);
	      if (!ISVAR(ap)) continue;

	      addrinfo = getaddr(ap);
	      addrinfo->isset = YES;
	      if (fixedaddress(ap))
		{
		  varinfo = getvar(addrinfo, ap);
		  if (ap->vstg != STGCONST)
		    varinfo->isset = YES;
		  varinfo->isused = YES;
		}
	      else
		addrinfo->freeuse = YES;
	    }
	  else
	    scanvars(args->datap);
	}
    }
  else
    scanvars(ep->rightp);

  return;
}



LOCAL int fixedaddress(ap)
Addrp ap;

{
  if (!ap->memoffset)
    return NO;
  return (ISCONST(ap->memoffset) && ISINT(ap->memoffset->headblock.vtype));
}



LOCAL countrefs(p)
expptr p;

{
  Addrp ap;
  ADDRNODE *addrinfo;
  VARNODE *varinfo;
  VARNODE *vp;
  chainp args;

  if (p == NULL) return;

  switch (p->tag)
    {
    case TCONST:
      return;

    case TEXPR:
      switch (p->exprblock.opcode)
	{
	case OPCALL:
	  if (p->exprblock.leftp->tag != TADDR)
	    badtag ("regalloc:countrefs", p->exprblock.leftp->tag);
	  countrefs(p->exprblock.leftp->addrblock.vleng);
	  countrefs(p->exprblock.leftp->addrblock.memoffset);

	  if (p->exprblock.leftp->addrblock.vstg != STGINTR)
	    {
	      if (!commonunusable)
		if (linearcode)
		  setcommon();
	        else
		  commonunusable = YES;
	      if (p->exprblock.rightp == NULL) return;
	      args = p->exprblock.rightp->listblock.listp;
	      for (; args; args = args->nextp)
		if (args->datap->tag == TADDR)
		  {
		    ap = (Addrp) args->datap;
		    countrefs(ap->vleng);
		    countrefs(ap->memoffset);
		    if (!ISVAR(ap) || ap->vstg == STGCONST) continue;
		    addrinfo = lookupaddr(ap->vstg, ap->memno);
		    if (ap->vstg == STGARG)
		      addrinfo->refs++;
		    for (vp = addrinfo->varlist; vp; vp = vp->link)
		      if (linearcode)
		        if (!insetlist(ap->vstg, ap->memno, vp->memoffset))
			  if (addrinfo->istemp)
			    vp->refs--;
			  else
			    {
			      vp->refs -= 2;
			      insertset(ap->vstg, ap->memno, vp->memoffset);
			    }
		        else
			  vp->refs--;
		      else
			{
			  if (!addrinfo->istemp)
			    vp->unusable = YES;
			}
		  }
		else
		  countrefs(args->datap);
            }
	  else
	    {
	      if (p->exprblock.rightp == NULL) return;
	      args = p->exprblock.rightp->listblock.listp;
	      for (; args; args = args->nextp)
		if (args->datap->tag == TADDR)
		  {
		    ap = (Addrp) args->datap;
		    countrefs(ap->vleng);
		    countrefs(ap->memoffset);
		    if (!ISVAR(ap) || ap->vstg == STGCONST) continue;
		    addrinfo = lookupaddr(ap->vstg, ap->memno);
		    addrinfo->refs++;
		    for (vp = addrinfo->varlist; vp; vp = vp->link)
		      if (!insetlist(ap->vstg, ap->memno, vp->memoffset))
			{
			  vp->refs--;
			  insertset(ap->vstg, ap->memno, vp->memoffset);
			}
		  }
		else
		  countrefs(args->datap);
	    }
	  return;

	case OPASSIGN:
	case OPPLUSEQ:
	case OPSTAREQ:
	  countrefs(p->exprblock.vleng);
	  countrefs(p->exprblock.rightp);
	  ap = (Addrp) p->exprblock.leftp;
	  if (fixedaddress(ap))
	    if (globalbranch)
	      {
		countrefs(ap->vleng);
		countrefs(ap->memoffset);
	      }
	    else
	      countrefs(ap);
	  else if (linearcode)
	    {
	      countrefs(ap);
	      for (vp = lookupaddr(ap->vstg, ap->memno)->varlist;
		   vp;
		   vp = vp->link)
		vp->refs--;
	    }
	  else
	    {
	      countrefs(ap);
	      for (vp = lookupaddr(ap->vstg, ap->memno)->varlist;
		   vp;
		   vp = vp->link)
		vp->unusable = YES;
	    }
	  return;

	default:
	  countrefs(p->exprblock.vleng);
	  countrefs(p->exprblock.leftp);
	  countrefs(p->exprblock.rightp);
	  return;
	}

    case TADDR:
      ap = (Addrp) p;
      countrefs(ap->vleng);
      countrefs(ap->memoffset);
      if (!ISVAR(ap)) return;

      addrinfo = lookupaddr(ap->vstg, ap->memno);
      if (ap->vstg == STGARG)
	addrinfo->refs++;

      if (fixedaddress(ap))
	{
	  if (ISREGTYPE(ap->vtype))
	    {
	      varinfo = lookupvar(addrinfo, ap->memoffset->constblock.const.ci);
	      varinfo->refs++;
	    }
	}
      else
	for (vp = addrinfo->varlist; vp; vp = vp->link)
	  if (!insetlist(ap->vstg, ap->memno, vp->memoffset))
	    {
	      vp->refs--;
	      insertset(ap->vstg, ap->memno, vp->memoffset);
	    }
      return;

    case TLIST:
      args = p->listblock.listp;
      for (; args; args = args->nextp)
	countrefs(args->datap);
      return;

    default:
      badtag ("regalloc:countrefs", p->tag);
    }
}



LOCAL regwrite(sp, p)
Slotp sp;
expptr p;

{
  register int i;
  REGDATA *rp;
  chainp args;
  Addrp ap, ap1;
  int memoffset;

  if (p == NULL) return;

  switch (p->tag)
    {
    case TCONST:
      return;

    case TEXPR:
      switch (p->exprblock.opcode)
	{
	case OPCALL:
	  ap = (Addrp) p->exprblock.leftp;
	  regwrite(sp, ap->vleng);
	  regwrite(sp, ap->memoffset);
	  if (ap->vstg != STGINTR)
	    {
	      if (linearcode)
		{
		  gensetcommon(sp);
		  for (i = toplcv + 1; i <= topregvar; i++)
		    if ((rp = regtab[i]) && (rp->vstg == STGCOMMON))
		      regdefined[i] = NO;