regalloc.c

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

		}
	      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;
		    regwrite(sp, ap->vleng);
		    regwrite(sp, ap->memoffset);
		    for (i = toplcv + 1; i <= topregvar; i++)
		      if ((rp = regtab[i]) &&
			  !rp->isarrayarg &&
			  !rp->istemp &&
			  (rp->vstg == ap->vstg) &&
			  (rp->memno == ap->memno))
			{
			  regdefined[i] = NO;
			  if (!memdefined[i])
			    {
			      ap1 = (Addrp) cpexpr(rp->stgp);
			      changetoreg(ap1, i);
			      insertassign(sp, cpexpr(rp->stgp), ap1);
			      memdefined[i] = YES;
			    }
			}
		      else if (rp->isarrayarg &&
			       (ap->vstg == STGARG) &&
			       (ap->memno == rp->memno))
			{
			  ap->vstg = STGPREG;
			  ap->memno = regnum[i];
			}
		  }
		else
		  regwrite(sp, 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;
		    regwrite(sp, ap->vleng);
		    regwrite(sp, ap->memoffset);
		    for (i = toplcv + 1; i <= topregvar; i++)
		      if ((rp = regtab[i]) &&
			  !rp->isarrayarg &&
			  !rp->istemp &&
			  (rp->vstg == ap->vstg) &&
			  (rp->memno == ap->memno) &&
			  !memdefined[i])
			{
			  ap1 = (Addrp) cpexpr(rp->stgp);
			  changetoreg(ap1, i);
			  insertassign(sp, cpexpr(rp->stgp), ap1);
			  memdefined[i] = YES;
			}
		      else if (rp->isarrayarg &&
			       (ap->vstg == STGARG) &&
			       (rp->memno == ap->memno))
			{
			  ap->vstg = STGPREG;
			  ap->memno = regnum[i];
			}
		  }
		else
		  {
		    regwrite(sp, args->datap);
		  }
	    }
	  return;

	case OPASSIGN:
	case OPPLUSEQ:
	case OPSTAREQ:
	  regwrite(sp, p->exprblock.vleng);
	  regwrite(sp, p->exprblock.rightp);
	  ap = (Addrp) p->exprblock.leftp;
	  regwrite(sp, ap->vleng);
	  regwrite(sp, ap->memoffset);

	  if (ap->vstg == STGARG)
	    for (i = toplcv + 1; i<=topregvar; i++)
	      if ((rp = regtab[i]) &&
		  rp->isarrayarg &&
		  (rp->memno == ap->memno))
		{
		  ap->vstg = STGPREG;
		  ap->memno = regnum[i];
		  return;
		}

	  if (fixedaddress(ap))
	    {
	      memoffset = ap->memoffset->constblock.const.ci;
	      for (i = toplcv + 1; i <= topregvar; i++)
		if ((rp = regtab[i]) &&
		    !rp->isarrayarg &&
		    (rp->vstg == ap->vstg) &&
		    (rp->memno == ap->memno) &&
		    (rp->memoffset == memoffset))
		  {
		    changetoreg(ap, i);
		    if (globalbranch)
		      {
			p->exprblock.rightp = (expptr) cpexpr(p);
			p->exprblock.leftp = (expptr) cpexpr(rp->stgp);
			p->exprblock.opcode = OPASSIGN;
			memdefined[i] = YES;
		      }
		    else
		      {
			regaltered[i] = YES;
			regdefined[i] = YES;
		      }
		  }
	      return;
	    }

	  if (linearcode)
	    for (i = toplcv + 1; i <= topregvar; i++)
	      if ((rp = regtab[i]) &&
		  !rp->isarrayarg &&
		  (rp->vstg == ap->vstg) &&
		  (rp->memno == ap->memno))
		regdefined[i] = NO;
	  return;

	default:
	  regwrite(sp, p->exprblock.vleng);
	  regwrite(sp, p->exprblock.leftp);
	  regwrite(sp, p->exprblock.rightp);
	  return;
	}

    case TADDR:
      ap = (Addrp) p;
      regwrite(sp, ap->vleng);
      regwrite(sp, ap->memoffset);

      if (ap->vstg == STGARG)
	for (i = toplcv + 1; i <= topregvar; i++)
	  if ((rp = regtab[i]) &&
	      rp->isarrayarg &&
	      (rp->memno == ap->memno))
	    {
	      ap->vstg = STGPREG;
	      ap->memno = regnum[i];
	      return;
	    }

      if (fixedaddress(ap))
	{
          memoffset = ap->memoffset->constblock.const.ci;
	  for (i = toplcv + 1; i <= topregvar; i++)
	    if ((rp = regtab[i]) &&
		!rp->isarrayarg &&
		(rp->vstg == ap->vstg) &&
		(rp->memno == ap->memno) &&
		(rp->memoffset == memoffset))
	      {
		changetoreg(ap, i);
		return;
	      }
	}
      else
	{
	  for (i = toplcv + 1; i <= topregvar; i++)
	    if ((rp = regtab[i]) &&
		!rp->isarrayarg &&
		(rp->vstg == ap->vstg) &&
		(rp->memno == ap->memno) &&
		!memdefined[i])
	      {
		ap1 = (Addrp) cpexpr(rp->stgp);
		changetoreg(ap1, i);
		insertassign(sp, cpexpr(rp->stgp), ap1);
		memdefined[i] = YES;
	      }
	}
      return;

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

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



LOCAL setcommon()

{
  ADDRNODE *ap;
  VARNODE *vp;

  for (ap = commonvars; ap; ap = ap->commonlink)
    for (vp = ap->varlist; vp; vp = vp->link)
      if (!insetlist(ap->vstg, ap->memno, vp->memoffset))
	{
	  vp->refs -= 2;
	  insertset(ap->vstg, ap->memno, vp->memoffset);
	}
      else
	vp->refs--;

  return;
}

 

LOCAL setall()

{
  register int i;
  register ADDRNODE *p;
  register VARNODE *q;

  for (i = 0; i < VARTABSIZE; i++)
    for (p = vartable[i]; p; p = p->link)
      if (p->istemp || !p->isset)
	break;
      else
	for (q = p->varlist; q; q = q->link)
	  if (q->isset && !insetlist(p->vstg, p->memno, q->memoffset))
	    q->refs--;

  allset = YES;
  return;
}



LOCAL int samevar(r1, r2)
register REGDATA *r1;
register REGNODE *r2;

{
  if ((r1->vstg != r2->vstg) ||
      (r1->memno != r2->memno) ||
      (r1->isarrayarg != r2->isarrayarg))
    return NO;
  if (r1->isarrayarg)
    return YES;
  return (r1->memoffset == r2->memoffset);
}



LOCAL entableaddr(p)
ADDRNODE *p;

{
  int refs;
  Addrp ap;
  register int i;

  if (p->vstg != STGARG)
    {
      currentaddr = p;
      return;
    }

  refs = p->refs;
  if (refs <= 0) return;

  if (tabletop < 0)
    tabletop = i = 0;
  else if (refs > rt[tabletop]->refs)
    {
      if (tabletop + 1 < TABLELIMIT)
	tabletop++;
      else
	{
	  frexpr(rt[tabletop]->stgp);
	  free((char *) rt[tabletop]);
	}

      for (i = tabletop; i > 0; i--)
	if (refs > rt[i - 1]->refs)
	  rt[i] = rt[i - 1];
	else
	  break;
    }
  else if (tabletop + 1 < TABLELIMIT)
    i = ++tabletop;
  else
    return;

  rt[i] = ALLOC(regdata);
  rt[i]->vstg = p->vstg;
  rt[i]->vtype = p->vtype;
  rt[i]->memno = p->memno;
  rt[i]->refs = refs;
  rt[i]->isarrayarg = YES;

  return;
}




LOCAL entablevar(p)
VARNODE *p;

{
  int refs;
  register int i;

  if (p->unusable) return;
  refs = p->refs - loopcost;
  if (refs <= 0) return;

  if (tabletop < 0)
    tabletop = i = 0;
  else if (refs > rt[tabletop]->refs)
    {
      if (tabletop + 1 < TABLELIMIT)
        tabletop++;
      else
	{
	  frexpr(rt[tabletop]->stgp);
          free((char *) rt[tabletop]);
	}

      for (i = tabletop; i > 0; i--)
        if (refs > rt[i - 1]->refs)
          rt[i] = rt[i - 1];
        else
          break;
    }
  else if (tabletop + 1 < TABLELIMIT)
    i = ++tabletop;
  else
    return;

  rt[i] = ALLOC(regdata);
  rt[i]->vstg = currentaddr->vstg;
  rt[i]->vtype = currentaddr->vtype;
  rt[i]->memno = currentaddr->memno;
  rt[i]->memoffset = p->memoffset;
  rt[i]->refs = refs;
  rt[i]->stgp = (Addrp) cpexpr(p->stgp);
  rt[i]->isarrayarg = NO;
  rt[i]->istemp = currentaddr->istemp;
  rt[i]->isset = p->isset;
  rt[i]->setfirst = p->setfirst;

  return;
}



LOCAL int inregtab(p)
register REGDATA *p;

{
  register REGDATA *rp;
  register int i;

  for (i = 0; i <= topregvar; i++)
    if (rp = regtab[i])
      if ((rp->vstg == p->vstg) &&
	  (rp->memno == p->memno) &&
	  (rp->isarrayarg == p->isarrayarg))
	if (rp->isarrayarg)
          return YES;
        else if (rp->memoffset == p->memoffset)
          return YES;

  return NO;
}



LOCAL changetoreg(ap, i)
register Addrp ap;
int i;

{
  ap->vstg = STGREG;
  ap->memno = regnum[i];
  frexpr(ap->memoffset);
  ap->memoffset = ICON(0);
  ap->istemp = NO;
  return;
}



LOCAL insertassign(sp, dest, src)
Slotp sp;
Addrp dest;
expptr src;

{
  Slotp newslot;
  expptr p;

  p = mkexpr(OPASSIGN, dest, src);
  newslot = optinsert (SKEQ,p,0,0,sp);

  if (sp == dohead)
    if (!newcode)
      newcode = newslot;

  return;
}


LOCAL appendassign(sp, dest, src)
Slotp sp;
Addrp dest;
expptr src;

{
  Slotp newslot;
  expptr p;

  if (!sp)
    fatal ("regalloc:appendassign");

  p = mkexpr(OPASSIGN, dest, src);
  newslot = optinsert (SKEQ,p,0,0,sp->next);

  return;
}



LOCAL int regtomem(sp)
Slotp sp;

{
  expptr p, l, r;
  int i;

  if (sp->type != SKEQ) return NO;

  p = sp->expr;
  if ((p->tag != TEXPR) || (p->exprblock.opcode != OPASSIGN))
    return NO;

  r = p->exprblock.rightp;
  if ((r->tag != TADDR) || (r->addrblock.vstg != STGREG))
    return NO;

  l = p->exprblock.leftp;
  if (l->tag != TADDR)
    return NO;
  i = r->addrblock.memno;
  if (regtab[i] &&
      (l->addrblock.vstg == regtab[i]->vstg) &&
      (l->addrblock.memno == regtab[i]->memno) &&
      fixedaddress(l) &&
      (l->addrblock.memoffset->constblock.const.ci == regtab[i]->memoffset))
    return YES;

  return NO;
}



LOCAL int regtoreg(sp)
Slotp sp;

{
  expptr p, l, r;

  if (sp->type != SKEQ) return NO;

  p = sp->expr;
  if ((p->tag != TEXPR) || (p->exprblock.opcode != OPASSIGN))
    return NO;

  l = p->exprblock.leftp;
  if ((l->tag != TADDR) || (l->addrblock.vstg != STGREG))
    return NO;

  r = p->exprblock.rightp;
  if ((r->tag == TADDR) &&
      (r->addrblock.vstg == STGREG) &&
      (r->addrblock.memno == l->addrblock.memno))
    return YES;

  return NO;
}



LOCAL deleteslot(sp)
Slotp sp;

{
  if (newcode == sp)
    {
      newcode = sp->next;
      if (newcode == dohead)
	newcode = NULL;
    }

  delslot (sp);
  return;
}



LOCAL gensetall(sp)
Slotp sp;

{
  register int i;
  register REGDATA *rp;
  register Addrp ap;

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

  return;
}


LOCAL gensetcommon(sp)
Slotp sp;

{
  register int i;
  register REGDATA *rp;
  register Addrp ap;

  for (i = toplcv + 1; i <= topregvar; i++)
    if (rp = regtab[i])
      if ((rp->vstg == STGCOMMON) && !rp->isarrayarg)
	if (!memdefined[i])
	  {
	    ap = (Addrp) cpexpr(rp->stgp);
	    changetoreg(ap, i);
	    insertassign(sp, cpexpr(rp->stgp), ap);
	    memdefined[i] = YES;
	  }

  return;
}


LOCAL gensetreturn(sp)
Slotp sp;

{
  register int i;
  register REGDATA *rp;
  register Addrp ap;

  for (i = toplcv + 1; i <= topregvar; i++)
    if (rp = regtab[i])
      if (((rp->vstg == STGCOMMON) && !rp->isarrayarg)
      || (rp->isset && (saveall || rp->stgp->issaved) && !(rp->istemp || rp->isarrayarg)))
	if (!memdefined[i])
	  {
	    ap = (Addrp) cpexpr(rp->stgp);
	    changetoreg(ap, i);
	    insertassign(sp, cpexpr(rp->stgp), ap);
	    memdefined[i] = YES;
	  }

  return;
}



LOCAL clearmems()

{
  REGDATA *rp;
  register int i;

  for (i = 0; i <= toplcv; i++)
    memdefined[i] = YES;
  for (; i <= topregvar; i++)
    if ((rp = regtab[i]) && rp->isset)
      memdefined[i] = NO;
    else
      memdefined[i] = YES;
  return;
}


LOCAL setregs()

{
  register int i;

  for (i = 0; i <= topregvar; i++)
    regdefined[i] = YES;
  return;
}



regalloc()

{
int	match;
Slotp	nextslot;
Slotp	sl1,sl2;
Slotp	lastlabslot;

if (! optimflag) return;

lastlabslot = NULL;
for (sl1 = firstslot; sl1; sl1 = nextslot)
	{
	nextslot = sl1->next;
	switch (sl1->type)
	    {

/* temporarily commented out -----
	    case SKLABEL:
		lastlabslot = sl1;
		break;

	    case SKGOTO:
		if (lastlabslot && sl1->label == lastlabslot->label)
			{
			dohead = lastlabslot;
			doend = sl1;
			alreg ();
			}
		break;
----- */

	    case SKDOHEAD:
		pushq (sl1);
		break;

	    case SKENDDO:
		match = 0;
		for (sl2 = sl1; sl2; sl2 = sl2->prev)
			{
			if (sl2->type == SKDOHEAD) match++;
			else if (sl2->type == SKENDDO) match--;
			if (match == 0) break;
			}
		if (sl2)
			dohead = sl2;
		else
			fatal ("unmatched enddo in code buffer");
		if (sl2->type != SKDOHEAD)
			fatal ("internal error in regalloc");

		for (dqptr = dqbottom; dqptr; dqptr = dqptr->up)
			{
			if (dqptr->dohead == dohead)
				break;
			}

		if (!dqptr)
			fatal ("garbled doqueue in regalloc");

		/*  sl1 now points to the SKENDDO slot; the SKNULL slot
		 *  is reached through sl1->nullslot
		 */
		doend = (Slotp) sl1->nullslot;

		alreg ();
		break;

	    default:
		break;
	    }
	}

while (dqtop)
	popq (dqtop->dohead);

return;
}



LOCAL pushq(sp)
Slotp sp;

{
  DOQUEUE *t;

  if (sp->type != SKDOHEAD)
    fatal("regalloc:pushq:  DO statement expected");

  if (dqbottom)
    {
      t = ALLOC(doqueue);
      t->up = dqbottom;
      dqbottom->down = t;
      dqbottom = t;
    }
  else
    dqtop = dqbottom = ALLOC(doqueue);

  dqbottom->dohead = sp;
}


LOCAL popq(sp)
Slotp sp;

{
  DOQUEUE *t;
  register int i;

  if (!dqtop)
    fatal("regalloc:popq:  empty DO queue");
  if (dqtop->dohead != sp)
    fatal("regalloc:popq:  garbled DO queue");

  t = dqtop;
  
  dqtop = t->down;
  if (dqtop)
    dqtop->up = NULL;
  else
    dqbottom = NULL;
  for (i = 0; i < MAXREGVAR; i++)
    if (t->reg[i])
      free((char *) t->reg[i]);
  free(t);
}