optcse.c

来自「<B>Digital的Unix操作系统VAX 4.2源码</B>」· C语言 代码 · 共 947 行 · 第 1/2 页

#ifndef lint
static	char	*sccsid = "@(#)optcse.c	4.1	(ULTRIX)	7/17/90";
#endif lint

/************************************************************************
 *									*
 *			Copyright (c) 1984 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.	*
 *									*
 ************************************************************************/
/*
 * optcse.c
 *
 * Common subexpression elimination routines, F77 compiler pass 1.
 *
 * University of Utah CS Dept modification history:
 *
 * $Log:	optcse.c,v $
 * Revision 2.4  84/10/29  04:40:48  donn
 * Problem with conversions -- two expressions headed by a conversion may be
 * identical in structure but different in type, thus type must be checked in
 * findnode().  This was causing a subscript to become REAL*8 type...
 * 
 * Revision 2.3  84/08/04  20:38:53  donn
 * Added fix from Jerry Berkman for an earlier fix from Alastair Fyfe --
 * samebase() should treat EQUIVALENCEd variables just as daintily as
 * COMMON variables.
 * 
 * Revision 2.2  84/08/01  16:04:33  donn
 * Changed rmcommaop so that it does subscripts too.
 * 
 * Revision 2.1  84/07/19  12:03:44  donn
 * Changed comment headers for UofU.
 * 
 * Revision 1.5  84/07/09  14:43:05  donn
 * Added changes to make OPPLUSEQ and OPSTAREQ expressions ineligible for
 * CSE, since I can't think of a simple way to handle them and they are broken
 * in the previous version, where they were treated like OPASSIGN -- this
 * fails because CSE would think that the value of the lhs and rhs were equal.
 * 
 * Revision 1.4  84/06/08  11:43:35  donn
 * Yet another way of handling the bug with COMMON -- this one is from Alastair
 * Fyfe at Sun.  I backed out the old fix.
 * 
 * Revision 1.3  84/03/07  19:25:14  donn
 * Changed method of handling COMMON bug -- COMMON variables are now treated
 * like array elements and hence are ineligible for CSE.
 * 
 * Revision 1.2  84/02/26  03:30:47  donn
 * Fixed bug in evaluation graph construction that caused two variables in
 * common to be considered identical if they were merely in the same common,
 * rather than in the same common at the same offset.
 * 
 */

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

#define FALSE	0
#define TRUE	1

LOCAL Bblockp	current_BB;
LOCAL int	cse1count;	/* count of number of cse uses eliminated */
LOCAL int	cse2count;	/* count of number of cse def's eliminated */




LOCAL dumpstacks()
{
	duplptr dl;
	valuen p;
	idlptr idl;
	idptr idp;
	nodelptr nl;
	int i;

	fprintf(diagfile,"\n *** IDblocks ***\n");
	for(idp=current_BB->headid;idp;idp=idp->next) 
	{ 
		fprintf(diagfile,
			"idp= %d idaddr= %d initval= %d assgnval= %d \n",
			idp, idp->idaddr, idp->initval, idp->assgnval);
		fprintf(diagfile,"nodes: ");
		i=0;
		for (nl=idp->headnodelist;nl;nl=nl->next) {
			if(++i>20){
				fprintf(diagfile,"\n");
				i=0;
			}
			fprintf(diagfile," %d ",nl->nodep);
		}
		fprintf(diagfile,"\n");
	}

	fprintf(diagfile,"\n *** VALUE NODES *** \n");
	for(p=current_BB->headnode;p;p=p->next) {
		fprintf(diagfile,
		   "\np= %d opp= %d lc= %d rc= %d rs= %d is_dead= %d n_dups %d",
		   p, p->opp,p->lc,p->rc, p->rs, p->is_dead, p->n_dups);
		if (p->rs){ 
			fprintf(diagfile,"tag= %d ",p->opp->tag);
			if(p->opp->tag==TEXPR)
				fprintf(diagfile,"opco= %d ",
				    p->opp->exprblock.opcode);
		}
		fprintf(diagfile,"\n");
		fprintf(diagfile,"parent= %d dups:  ",p->parent);
		i=0;
		for(dl=p->headduplist;dl;dl=dl->next) {
			if(++i>20){
				fprintf(diagfile,"\n");
				i=0;
			}
			fprintf(diagfile," %d ",dl->parent);
		}

		fprintf(diagfile,"\ndeps IDs");
		i=0;
		for(idl=p->headdeplist;idl;idl=idl->next) {
			if(++i>20){
				fprintf(diagfile,"\n");
				i=0;
			}
			fprintf(diagfile," %d ",idl->idp);
		}
	}
}



LOCAL idlptr mergedeps(lnode,rnode)
valuen lnode,rnode;
/* Given two value nodes, merge the lists of identifiers on which they
** depend to produce a new list incorporating both dependencies. Lists
** are assumed to be ordered by increasing idp address. No duplicate identifiers
** are generated in the output list.
*/
{
	register idlptr lp,lp1,lp2;
	idlptr head;

	lp = lp1 = lp2 = head = NULL;
	if(lnode) lp1 = lnode->headdeplist;
	if(rnode) lp2 = rnode->headdeplist;

	while (lp1 || lp2) {
		if (lp) { 
			lp->next = ALLOC(IDlist); 
			lp = lp->next; 
		}
		else lp = head = ALLOC(IDlist);
		lp->next = 0;
		if (lp1 == 0) {
			lp->idp = lp2->idp;
			lp2 = lp2->next;
		}
		else if (lp2 == 0) {
			lp->idp = lp1->idp;
			lp1 = lp1->next; 
		}
		else if (lp1->idp < lp2->idp) {
			lp->idp = lp1->idp;
			lp1 = lp1->next; 
		}
		else if (lp1->idp > lp2->idp) {
			lp->idp = lp2->idp;
			lp2 = lp2->next; 
		}
		else {
			lp->idp = lp1->idp;
			lp1 = lp1->next;
			lp2 = lp2->next;
		}
	}
	return(head);
}



LOCAL removenode(nodep)
valuen nodep;
/*  Removes a value node from every IDblock on the node's list of identifiers.
*/
{
	register idlptr idl;
	register nodelptr nl;
	register nodelptr *addrnl;

	if(nodep == NULL) return ;

	/* loop through all identifiers */
	for(idl=nodep->headdeplist;idl;idl=idl->next)
	{
		addrnl = &(idl->idp->headnodelist);
		/* for each identifier loop through all nodes until match is found */
		for(nl = *addrnl; nl; nl = *addrnl)
		{
			if(nl->nodep == nodep) {
				*addrnl = nl->next;
				free ( (charptr) nl );
				break;
			}
			addrnl = &nl->next;
		}
	}
	nodep->is_dead = TRUE;
}



LOCAL killid(idp)
idptr idp;
/* Kill all nodes on one identifier's list of dependent nodes, i.e. remove
** all calculations that depend on this identifier from the available 
** values stack.  Free the list of records pointing at the dependent nodes.
*/
{
	nodelptr nl1,nl2;

	for (nl1 = idp->headnodelist; nl1; nl1=nl2) 
	{
		nl2 = nl1->next;
		removenode(nl1->nodep);
	}
	/* the above call frees the node list record pointed at by nl1 since it frees
	** all the node list records that reference the value node being killed
	*/
	idp->headnodelist = NULL;

}



LOCAL killdepnodes(idp)
idptr idp;
/* Kill all value nodes that represent calculations which depend on
** this identifier. If the identifier is in COMMON or EQUIVALENCE storage,
** kill all values that depend on identifiers in COMMON or EQUIVALENCE
*/
{
	int thismemno;

	if(idp->idaddr->addrblock.vstg == STGCOMMON) 
	{
		for(idp=current_BB->headid;idp;idp=idp->next)
			if(idp->idaddr->addrblock.vstg == STGCOMMON)
				killid(idp);
	}
	else if(idp->idaddr->addrblock.vstg == STGEQUIV) 
	{           
		thismemno=idp->idaddr->addrblock.memno;
		for(idp=current_BB->headid;idp;idp=idp->next)
			if(idp->idaddr->addrblock.vstg == STGEQUIV
			    && idp->idaddr->addrblock.memno == thismemno)
				killid(idp);
	}
	else killid(idp);

}



LOCAL appendnode(nodep)
valuen nodep;
/* Append a value node to all the IDblocks on that node's list of
** dependent identifiers i.e., since this computation depends on
** all the identifiers on its list then each of those identifiers should
** include this node in their list of dependent nodes.
*/
{
	register idlptr idl;
	register nodelptr nl;

	for(idl=nodep->headdeplist;idl;idl=idl->next)
		if(idl->idp->idaddr->tag == TADDR ||
		   idl->idp->idaddr->tag == TTEMP)
			{
			nl=ALLOC(NODElist);
			nl->nodep = nodep;
			nl->next = idl->idp->headnodelist;
			idl->idp->headnodelist = nl;
			}
}



LOCAL idlptr addadep(idp,nodep) 
idptr idp;
valuen nodep;
/* Add an identifier to the dependents list of a value node.  Dependents
** lists are ordered by increasing idp value
*/
{
	register idlptr lp1,lp2; 

	lp2 = ALLOC(IDlist);
	lp2->idp = idp;
	if(nodep->headdeplist == 0) {
		lp2->next = 0;
		nodep->headdeplist = lp2;
	}
	else if(idp <= nodep->headdeplist->idp) {
		lp2->next = nodep->headdeplist;
		nodep->headdeplist = lp2;
	}
	else for(lp1 = nodep->headdeplist; lp1; lp1 = lp1->next)
		if( (lp1->next == 0) || (idp <= lp1->next->idp) )
		{
			lp2->next = lp1->next;
			lp1->next = lp2;
			break;
		}
	return(lp2);
}



LOCAL valuen newnode(expr,left,right,rslt) 
expptr expr;
valuen left,right,rslt;
/* Build a new value node            
*/
{
	register valuen p;

	p= ALLOC(VALUEnode);
	p->opp = expr ; 
	p->parent = NULL ;
	p->lc = left;
	p->rc = right;
	p->rs = rslt;
	p->n_dups = 0;
	p->is_dead = FALSE;
	p->next=NULL;
	p->headdeplist = mergedeps(left,right);
	p->headduplist=NULL;
	if(current_BB->headnode == 0) current_BB->headnode=p;
	else if(current_BB->tailnode) current_BB->tailnode->next=p;
	current_BB->tailnode=p;

	return(p);
}



LOCAL newid(idaddr,addrof_idptr)
expptr idaddr; 
idptr *addrof_idptr;
/* Build a new IDblock and hook it on the current BB's ID list
*/
{
	register idptr p;

	p= ALLOC(IDblock);

/* build a leaf value node for the identifier and put the ID on the leaf node's
** list of dependent identifiers
*/
	p->initval =  newnode(idaddr,NULL,NULL,NULL);
	p->initval->rs = p->initval;
	addadep(p,p->initval); 

	p->idaddr = idaddr;
	*addrof_idptr = p;
	p->headnodelist=NULL;
	p->next=NULL;

}



LOCAL addadup(parent,nodep)
expptr *parent;
valuen nodep;

/* A subtree has been found that duplicates the calculation represented
** by the value node referenced by nodep : add the root of the reduntant
** tree to the value node's list of duplicates.
*/

{
	register duplptr dp;
	valuen child;

	dp = ALLOC(DUPlist);
	dp->parent = parent;
	dp->next = nodep->headduplist;
	nodep->headduplist = dp;
	++nodep->n_dups;

/* Check whether either of nodep's children is also a duplicate calculation
** and if so peel off it's most recent dup record
*/

	if ( (child = nodep->lc) && (child->n_dups) )
	{
		dp = child->headduplist;
		child->headduplist = dp->next;
		free ( (charptr) dp );
		--child->n_dups;
	}
	if ( (child = nodep->rc) && (child->n_dups) )
	{
		dp = child->headduplist;
		child->headduplist = dp->next;
		free ( (charptr) dp );
		--child->n_dups;
	}

}



LOCAL samebase(ep1,ep2)
expptr ep1,ep2;
{
    if ( ep1->tag == ep2->tag  )       
	switch (ep2->tag) {
	    case TTEMP :
		if (ep1->tempblock.memalloc == ep2->tempblock.memalloc)
			return (TRUE);
		break;
	    case TADDR :  
		if (ep1->addrblock.vstg == ep2->addrblock.vstg) {
		    switch(ep1->addrblock.vstg) {
			case STGEQUIV:
			case STGCOMMON:
			    if (ep1->addrblock.memno == ep2->addrblock.memno &&
				ISCONST(ep1->addrblock.memoffset) &&
				ISCONST(ep2->addrblock.memoffset) &&
				ep1->addrblock.memoffset->constblock.const.ci ==
				ep2->addrblock.memoffset->constblock.const.ci ) {
				    return(TRUE); 
			    }
			    break;

			default:
			    if (ep1->addrblock.memno == ep2->addrblock.memno ) {
				return(TRUE); 
			    }
		    }
		}
		break;
	    case TCONST :
		if( (ep1->constblock.vtype) ==
		    (ep2->constblock.vtype)  ) 
		{
			union Constant *ap,*bp;
			ap= &ep1->constblock.const;
			bp= &ep2->constblock.const;
			switch(ep1->constblock.vtype)