regalloc.c

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

#ifndef lint
static char	*sccsid = " @(#)regalloc.c	1.3	(ULTRIX)	1/15/86";
#endif lint

/************************************************************************
 *									*
 *			Copyright (c) 1986 by				*
 *		Digital Equipment Corporation, Maynard, MA		*
 *			All rights reserved.				*
 *									*
 *   This software is furnished under a license and may be used and	*
 *   copied  only  in accordance with the terms of such license and	*
 *   with the  inclusion  of  the  above  copyright  notice.   This	*
 *   software  or  any  other copies thereof may not be provided or	*
 *   otherwise made available to any other person.  No title to and	*
 *   ownership of the software is hereby transferred.			*
 *									*
 *   This software is  derived  from  software  received  from  the	*
 *   University    of   California,   Berkeley,   and   from   Bell	*
 *   Laboratories.  Use, duplication, or disclosure is  subject  to	*
 *   restrictions  under  license  agreements  with  University  of	*
 *   California and with AT&T.						*
 *									*
 *   The information in this software is subject to change  without	*
 *   notice  and should not be construed as a commitment by Digital	*
 *   Equipment Corporation.						*
 *									*
 *   Digital assumes no responsibility for the use  or  reliability	*
 *   of its software on equipment which is not supplied by Digital.	*
 *									*
 ************************************************************************/

/************************************************************************
*
*			Modification History
*
*	Sid Maxwell		29-Sep-88
*
* 002	Modified alreg to write COMMON register values before an inner
*	DO loop head.
*
*	David Metsky		14-Jan-86
*
* 001	Replaced old version with BSD 4.3 version as part of upgrade.
*
*	Based on:	regalloc.c	5.1		6/7/85
*
*************************************************************************/

/*
 * regalloc.c
 *
 * Register optimization routines for f77 compiler, pass 1
 *
 * University of Utah CS Dept modification history:
 *
 * $History$
 * $Log:	regalloc.c,v $
 * Revision 2.9  85/03/18  21:35:05  donn
 * Bob Corbett's hack to prevent conflicts between subroutine side effects
 * and register assignment.  Makes the code a lot worse...
 * 
 * Revision 2.8  85/02/22  02:14:08  donn
 * In code like 'x = foo(x)', alreg() would copy the memory version of the
 * variable 'x' into the register version after the assignment, clobbering
 * the result.  A small change to regwrite() seems to prevent this.
 * 
 * Revision 2.7  85/02/16  03:32:45  donn
 * Fixed a bug where the loop test and increment were having register
 * substitution performed twice, once in the environment of the current
 * loop and once in the environment of the containing loop.  If the
 * containing loop puts (say) the inner loop's index variable in register
 * but the inner loop does not, havoc results.
 * 
 * Revision 2.6  85/02/14  23:21:45  donn
 * Don't permit variable references of the form 'a(i)' to be put in register
 * if array 'a' is in common.  This is because there is no good way to
 * identify instances of this sort without getting confused with other
 * variables in the same common block which are in register.  Sigh.
 * 
 * Revision 2.5  85/01/11  21:08:00  donn
 * Made changes so that we pay attention to SAVE statements.  Added a new
 * gensetreturn() function to implement this.
 * 
 * Revision 2.4  84/09/03  22:37:28  donn
 * Changed the treatment of SKRETURN in alreg() so that all variables in
 * register, not just COMMON variables, get written out to memory before a
 * RETURN.  This was causing the return value of a function to get lost when
 * a RETURN was done from inside a loop (among other problems).
 * 
 * Revision 2.3  84/08/04  20:52:42  donn
 * Added fixes for EXTERNAL parameters from Jerry Berkman.
 * 
 * Revision 2.2  84/08/04  20:34:29  donn
 * Fixed a stupidity pointed out by Jerry Berkman -- the 'floats in register'
 * stuff applies if the TARGET is a VAX, not if the local machine is a VAX.
 * 
 * Revision 2.1  84/07/19  12:04:47  donn
 * Changed comment headers for UofU.
 * 
 * Revision 1.5  83/11/27  19:25:41  donn
 * Added REAL to the list of types which may appear in registers (VAXen only).
 * 
 * Revision 1.4  83/11/13  02:38:39  donn
 * Bug fixed in alreg()'s handling of computed goto's.  A '<=' in place of a
 * '<' led to core dumps when we walked off the end of the list of labels...
 * 
 * Revision 1.3  83/11/12  01:25:57  donn
 * Bug in redundant register assignment code, mistakenly carried over some old
 * code that sometimes rewound a slot pointer even when a redundant slot wasn't
 * deleted; this caused an infinite loop...  Seems to work now.
 * 
 * Revision 1.2  83/11/09  14:58:12  donn
 * Took out broken code dealing with redundant register initializations.
 * Couldn't see what to do about redundantly initializing a DO variable but
 * I did fix things so that an assignment from a register into the same
 * register is always deleted.
 * 
 */

#include "defs.h"
#include "optim.h"

#define LABTABSIZE 101
#define VARTABSIZE 1009
#define TABLELIMIT 12

#if TARGET==VAX
#define MSKREGTYPES M(TYLOGICAL) | M(TYADDR) | M(TYSHORT) | M(TYLONG) | M(TYREAL)
#else
#define MSKREGTYPES M(TYLOGICAL) | M(TYADDR) | M(TYSHORT) | M(TYLONG)
#endif

#define ISREGTYPE(x) ONEOF(x, MSKREGTYPES)

#define MSKVARS M(STGAUTO) | M(STGBSS) | M(STGINIT) | M(STGCONST) |\
		M(STGEQUIV) | M(STGARG) | M(STGCOMMON)

#define ISVAR(x) ((((expptr) x)->headblock.vclass == CLVAR || \
			((expptr) x)->headblock.vclass == CLUNKNOWN) \
                  && ONEOF(((expptr) x)->headblock.vstg, MSKVARS))


typedef
  struct regdata
    {
      field vstg;
      field vtype;
      int memno;
      int memoffset;
      int refs;
      Addrp stgp;
      unsigned isarrayarg : 1;
      unsigned istemp : 1;
      unsigned isset : 1;
      unsigned setfirst : 1;
    } REGDATA;


typedef
  struct labelnode
    {
      struct labelnode *link;
      int labelno;
    } LABELNODE;



typedef
  struct varnode
    {
      struct varnode *link;
      int memoffset;
      unsigned isset : 1;
      unsigned isused : 1;
      unsigned setfirst : 1;
      unsigned unusable : 1;
      int refs;
      Addrp stgp;
    } VARNODE;


typedef
  struct addrnode
    {
      struct addrnode *link;
      field vtype;
      field vstg;
      int memno;
      unsigned istemp : 1;
      unsigned isset : 1;
      unsigned freeuse : 1;
      unsigned mixedtype : 1;
      unsigned fixed : 1;
      int refs;
      struct addrnode *commonlink;
      VARNODE *varlist;
    } ADDRNODE;


typedef
  struct setnode
    {
      struct setnode *link;
      field vstg;
      int memno;
      int memoffset;
    } SETNODE;


typedef
  struct doqueue
    {
      struct doqueue *up, *down;
      Slotp dohead, doend;
      int nregvars;
      REGNODE *reg[MAXREGVAR];
    }  DOQUEUE;

LOCAL DOQUEUE *dqptr, *dqtop, *dqbottom;


LOCAL Slotp dohead;
LOCAL Slotp doend;
LOCAL Slotp newcode;



LOCAL LABELNODE *labeltable[LABTABSIZE];
LOCAL ADDRNODE *vartable[VARTABSIZE];
LOCAL ADDRNODE *commonvars;
LOCAL SETNODE *setlist;
LOCAL int topregvar;
LOCAL int toplcv;
LOCAL int allset;
LOCAL ADDRNODE *currentaddr;
LOCAL int loopcost;
LOCAL REGDATA *regtab[MAXREGVAR];
LOCAL REGDATA *rt[TABLELIMIT];
LOCAL int tabletop;
LOCAL int linearcode;
LOCAL int globalbranch;
LOCAL int commonunusable;
LOCAL int regdefined[MAXREGVAR];
LOCAL int memdefined[MAXREGVAR];
LOCAL int regaltered[MAXREGVAR];



LOCAL insertlabel(l)
int l;

{
  int key;
  LABELNODE *p;

  key = l % LABTABSIZE;
  for (p = labeltable[key]; p; p = p->link)
    if (p->labelno == l) return;
  p = labeltable[key];
  labeltable[key] = ALLOC(labelnode);
  labeltable[key]->link = p;
  labeltable[key]->labelno = l;
  return;
}



LOCAL int locallabel(l)
int l;

{
  int key;
  LABELNODE *p;

  key = l % LABTABSIZE;
  for (p = labeltable[key]; p; p = p->link)
    if (p->labelno == l) return YES;

  return NO;
}



LOCAL freelabtab()

{
  int i;
  LABELNODE *p, *q;

  for (i = 0; i < LABTABSIZE; i++)
    if (labeltable[i])
      {
	p = labeltable[i];
	labeltable[i] = NULL;
	while (p)
	  {
	    q = p->link;
	    free(p);
	    p = q;
	  }
      }
  return;
}



LOCAL ADDRNODE *getaddr(ap)
Addrp ap;

{
  int key;
  field vstg;
  int memno;
  register ADDRNODE *q;
  ADDRNODE *q1;

  if (!ISVAR(ap))
    fatal("regalloc: bad data sent to getaddr");
  vstg = ap->vstg;
  memno = ap->memno;
  key = (256*vstg + memno) % VARTABSIZE;

  for (q = vartable[key]; q; q = q->link)
    if ((q->vstg == vstg) && (q->memno == memno)) 
      {
	if (ap->istemp) q->istemp = YES;
	if (ap->vtype != q->vtype)
	  q->mixedtype = YES;
	if (!fixedaddress(ap))
	  q->fixed = NO;
	return q;
      }

  q1 = vartable[key];
  vartable[key] = q = ALLOC(addrnode);
  q->link = q1;
  q->vstg = vstg;
  q->memno = memno;
  if (ap->istemp) q->istemp = YES;
  if (fixedaddress(ap)) q->fixed = YES;
  q->vtype = ap->vtype;
  q->varlist = NULL;
  if (vstg == STGCOMMON)
    {
      q->commonlink = commonvars;
      commonvars = q;
    }
  return q;
}



LOCAL VARNODE *getvar(ainfo, ap)
ADDRNODE *ainfo;
Addrp ap;

{
  register VARNODE *q;
  VARNODE *q1;
  int memoffset;

  if (!ISVAR(ap))
    fatal("regalloc:  bad data sent to getvar");

  memoffset = ap->memoffset->constblock.const.ci;

  for (q = ainfo->varlist; q; q = q->link)
    if (q->memoffset == memoffset)
      return q;

  q1 = ainfo->varlist;
  ainfo->varlist = q = ALLOC(varnode);
  q->link = q1;
  q->memoffset = memoffset;
  q->stgp = (Addrp) cpexpr(ap);
  return q;
}


LOCAL ADDRNODE *lookupaddr(vstg, memno)
field vstg;
int memno;

{
  int key;
  register ADDRNODE *q;

  key = (256*vstg + memno) % VARTABSIZE;

  for (q = vartable[key]; q; q = q->link)
    if ((q->vstg == vstg) && (q->memno == memno))
      return q;

  fatal("regalloc:  lookupaddr");
}


LOCAL VARNODE *lookupvar(ainfo, memoffset)
ADDRNODE *ainfo;
int memoffset;

{
  register VARNODE *q;

  for (q = ainfo->varlist; q; q = q->link)
    if (q->memoffset == memoffset)
      return q;

  fatal("regalloc:  lookupvar");
}



LOCAL int invartable(p)
REGNODE *p;

{
  field vstg;
  int memno;
  int key;
  register ADDRNODE *q;

  vstg = p->vstg;
  memno = p->memno;
  key = (256*vstg + memno) % VARTABSIZE;

  for (q = vartable[key]; q; q = q->link)
    if ((q->vstg == vstg) && (q->memno == memno))
      return YES;

  return NO;
}



LOCAL freevartab()

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

  for (i = 0; i < VARTABSIZE; i++)
    if (vartable[i])
      {
	p = vartable[i];
	vartable[i] = NULL;

	while (p)
	  {
	    for (q = p->varlist; q; q = q1)
	      {
		q1 = q->link;
		frexpr(q->stgp);
		free ((char *) q);
	      }
	    p1 = p->link;
	    free((char *) p);
	    p = p1;
	  }
      }
}



LOCAL insertset(vstg, memno, memoffset)
field vstg;
int memno;
int memoffset;

{
  register SETNODE *p;
  SETNODE *q;

  if (allset) return;
  for (p = setlist; p; p = p->link)
    if((p->vstg == vstg) && (p->memno == memno) && (p->memoffset == memoffset))
      return;

  q = p;
  setlist = p = ALLOC(setnode);
  p->link = q;
  p->vstg = vstg;
  p->memno = memno;
  p->memoffset = memoffset;
  return;
}



LOCAL int insetlist(vstg, memno, memoffset)
field vstg;
int memno;
int memoffset;

{
  register SETNODE *p;

  if (allset) return YES;
  for (p = setlist; p; p = p->link)
    if((p->vstg == vstg) && (p->memno == memno) && (p->memoffset == memoffset))
      return YES;

  return NO;
}



LOCAL clearsets()

{
  register SETNODE *p, *q;

  allset = NO;

  p = setlist;
  while (p)
    {
      q = p->link;
      free ((char *) p);
      p = q;
    }
  setlist = NULL;
  return;
}



LOCAL alreg()

{
  register Slotp sp;
  register int i;
  register ADDRNODE *p;
  register VARNODE *q;
  Slotp sp1, sp2;
  ADDRNODE *addrinfo;
  VARNODE *varinfo;
  int docount;
  struct Labelblock **lp;
  int toptrack;
  int track[MAXREGVAR];
  Addrp ap, ap1;
  DOQUEUE *dqp;
  REGDATA *rp;
  REGNODE *regp;

  if (nregvar >= maxregvar) return;

  commonvars = NULL;

  for (sp = dohead; sp != doend->next; sp = sp->next)
    switch (sp->type)
      {
      case SKLABEL:
	insertlabel(sp->label);
	break;

      case SKARIF:
      case SKASGOTO:
      case SKCALL:
      case SKCMGOTO:
      case SKEQ:
      case SKIFN:
      case SKIOIFN:
      case SKSTOP:
      case SKPAUSE:
      case SKRETURN:
	scanvars(sp->expr);
	break;

      case SKNULL:
      case SKGOTO:
      case SKDOHEAD:
      case SKENDDO:
      case SKASSIGN:
	break;

      default:
	badthing ("SKtype", "alreg-1", sp->type);
      }

  loopcost = 0;
  docount = 1;
  commonunusable = NO;
  if (! dohead->nullslot) fatal ("missing dohead->nullslot -cbb");
  for (sp = dohead->next, globalbranch = NO;
       docount;
       sp = sp->next, clearsets(), globalbranch = NO)
    if (docount > 1)
      switch (sp->type)
	{
	case SKDOHEAD:
	  docount++;
	  break;

	case SKENDDO:
	  docount--;

	default:
	  break;
	}
    else
      switch (sp->type)
	{
	case SKARIF:
#define LM   ((struct Labelblock * *)sp->ctlinfo)[0]->labelno 
#define LZ   ((struct Labelblock * *)sp->ctlinfo)[1]->labelno 
#define LP   ((struct Labelblock * *)sp->ctlinfo)[2]->labelno 

	  if (!locallabel(LM) || !locallabel(LZ) || !locallabel(LP))
	    {
	      setall();
	      globalbranch = YES;
	    }
	  countrefs(sp->expr);
	  break;

	case SKASGOTO:
	  setall();
	  globalbranch = YES;
	  countrefs(sp->expr);
	  break;

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

	case SKDOHEAD:
	  globalbranch = YES;
	  loopcost = 2;
	  docount++;
	  break;

	case SKENDDO:
	  docount = 0;
	  break;

	case SKGOTO:
	  if (!locallabel(sp->label))
	    {
	      setall();
	      globalbranch = YES;
	    }
	  break;

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

	case SKEQ:
	case SKCALL:
	case SKSTOP:
	case SKPAUSE:
	  linearcode = YES;
	  countrefs(sp->expr);
	  linearcode = NO;
	  break;
	}

  topregvar = toplcv = nregvar - 1;

  for (i = 0; i < nregvar; i++)
    {
      ap = memversion(regnamep[i]);
      regtab[i] = rp = ALLOC(regdata);
      rp->vstg = ap->vstg;
      rp->vtype = ap->vtype;
      rp->memno = ap->memno;
      rp->memoffset = ap->memoffset->constblock.const.ci;
      rp->isarrayarg = NO;
      rp->stgp = ap;
    }

  for (i = 0; i < MAXREGVAR; i++)
    track[i] = YES;

  for (dqp = dqptr->down; dqp; dqp = dqp->down)
    {
      if (dqp->nregvars - 1 > topregvar)
	topregvar = dqp->nregvars -1;
      for (i = toplcv + 1; i < dqp->nregvars; i++)
	if (track[i])
	  if (regp = dqp->reg[i])
	    if (rp = regtab[i])
	      {
		if (!samevar(rp, regp))
		  track[i] = NO;
	      }
	    else if (invartable(regp))
	      {
		regtab[i] = rp = ALLOC(regdata);
		rp->vstg = regp->vstg;
		rp->vtype = regp->vtype;
		rp->memno = regp->memno;
		rp->memoffset = regp->memoffset;
		addrinfo = lookupaddr(rp->vstg, rp->memno);
		if (regp->isarrayarg)
		  {
		    rp->isarrayarg = YES;
		    rp->refs = addrinfo->refs;
		  }
		else
		  {
		    varinfo = lookupvar(addrinfo, regp->memoffset);
		    rp->refs = varinfo->refs;
		    rp->stgp = (Addrp) cpexpr(varinfo->stgp);
		    rp->istemp = addrinfo->istemp;
		    rp->isset = varinfo->isset;
		    rp->setfirst = varinfo->setfirst;
		  }
	      }
	    else
              track[i] = NO;
	  else
	    track[i] = NO;
    }

  toptrack = topregvar;

  for (i = toplcv + 1; i <= topregvar; i++)
    if (regtab[i])
      if ((track[i] == NO) || (regtab[i]->refs <= 0))
        {
	  free((char *) regtab[i]);