#ifndef lintstatic 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]);