bb.c

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

#ifndef lint
static	char	*sccsid = "@(#)bb.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.	*
 *									*
 ************************************************************************/
/*
 * bb.c
 *
 * Basic block optimizations.
 *
 * University of Utah CS Dept modification history:
 *
 * $Log:	bb.c,v $
 * Revision 2.1  84/07/19  12:01:20  donn
 * Changed comment headers for UofU.
 * 
 * Revision 1.2  84/04/02  14:22:49  donn
 * Bug in copy propagation missed places where temporaries are assigned to
 * by OPSTAREQ or OPPLUSEQ, e.g. exponentiation with an integer constant
 * power, expanded inline.
 * 
 */

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

/*
 *  This file contains code for determination of basic blocks,
 *  as well as some other optimization supporting routines
 *  [including the main routine 'optimize()'].
 *
 *  The compiler's general debugging flag ['debugflag'] has been
 *  extended to provide the capability of having multiple flags
 *  which are contained in an array.  If the option -d is used,
 *  then the flag debugflag[0] is set.  If a sequence of one or more
 *  numbers are given (e.g, -d3,7,12), then the flags debugflag[3],
 *  debugflag[7], and debugflag[12] are set.  The maximum number of
 *  flags available is specified in the defines.h file.
 */


Bblockp	firstblock = NULL;		/* first block in buffer */
Bblockp	lastblock = NULL;		/* last block in buffer */

expptr	tempalloc();


optimize ()

{
Bblockp bb;
Slotp	sl,nextsl;

if (debugflag[2]) showbuffer ();

optloops ();

if (debugflag[3]) showbuffer ();

formbblock ();
optcse ();

if (debugflag[4]) showbuffer ();

if (! debugflag[7])
	copyprop ();

if (debugflag[9]) showbuffer ();

for (sl = firstslot; sl; sl = nextsl)
	{
	nextsl = sl->next;
	if (sl->type == SKFRTEMP)
		{
		templist = mkchain (sl->expr,templist);
		sl->expr = NULL;
		delslot (sl);
		}
	else
		sl->expr = tempalloc (sl->expr);
	}

if (! debugflag[10])
	regalloc ();

flushopt ();
}



/*
 *  creates a new basic block record
 */

LOCAL Bblockp newblock (sl)
Slotp	sl;

{
register Bblockp bb;

bb = ALLOC( bblock );
bb->next = NULL ;
if (lastblock)
	{
	bb->prev = lastblock;
	lastblock->next = bb;
	lastblock = bb;
	}
else
	{
	firstblock = lastblock = bb;
	bb->prev = NULL;
	}

bb->first = sl;
return (bb);
}



/*
 *  scans slot buffer, creating basic block records
 */

formbblock ()

{
Slotp	sl;
field	type;
Bblockp	newbb;

newbb = NULL;
for (sl = firstslot; sl; sl = sl->next)
	{
	type = sl->type;
	switch (type)
		{
		case SKEQ:
			if (!newbb)
				newbb = newblock(sl);
			if (containscall(sl->expr))
				{
				newbb->last = sl;
				newbb = NULL;
				}
			break;
		case SKNULL:
		case SKASSIGN:
		case SKFRTEMP:
			if (!newbb)
				newbb = newblock(sl);
			break;
		case SKPAUSE:
		case SKSTOP:
		case SKIFN:
		case SKGOTO:
		case SKCMGOTO:
		case SKARIF:
		case SKASGOTO:
		case SKIOIFN:
		case SKCALL:
		case SKRETURN:
			if (!newbb)
				newbb = newblock(sl);
			newbb->last = sl;
			newbb = NULL;
			break;
		case SKLABEL:
			if (newbb)
				newbb->last = sl->prev;
			newbb = newblock(sl);
			break;
		case SKDOHEAD:
		case SKENDDO:
			if (!newbb)
				newbb = newblock(sl);
			break;
		default:
			badthing("SKtype", "formbblock", type);
			break;
		}
	}
if (newbb)
	newbb->last = lastslot;
}



/*
 *  frees all basic block records
 *  as well as the id and value node chains hanging off the bb and their
 *  respective cross link chains (IDlist, DUPlist and NODElist structs) 
 */

clearbb ()
{
Bblockp	bb,next;

for (bb = firstblock; bb; bb = next)
	{
	next = bb->next;
	   { 
	     idptr idp,next;
	     for(idp = bb->headid; idp; idp = next) 
		{ 
		 next = idp->next;
		      {
		      nodelptr nodelp, next;
	              for(nodelp = idp->headnodelist; nodelp; nodelp = next)
			 {
			    next = nodelp->next;
		            free( (charptr) nodelp);
		         }	
		      }
                 free( (charptr) idp);
	        }	
           }
	   { 
	     valuen vp,next;
	     for(vp = bb->headnode; vp; vp = next) 
		{ 
		 next = vp->next;
		      {
		      idlptr idlp, next;
	              for(idlp = vp->headdeplist; idlp; idlp = next)
			 {
			    next = idlp->next;
		            free( (charptr) idlp);
		         }	
		      }
		      {
		      duplptr duplp, next;
	              for(duplp = vp->headduplist; duplp; duplp = next)
			 {
			    next = duplp->next;
		            free( (charptr) duplp);
		         }	
		      }
                 free( (charptr) vp);
	        }	
           }
	free ( (charptr) bb);
	}
firstblock = lastblock = NULL;
}


/* structure for maintaining records on copy statements */

typedef struct Subrec {
	Addrp	lmem;
	Addrp	rmem;
	int	sets;
} *Subrecp;


LOCAL chainp sublist;	/* list of copy statements */
LOCAL int prop1count;	/* count of number of temporaries eliminated */
LOCAL int prop2count;	/* count of number of uses of temporaries replaced */

expptr rmcommaop();
Addrp subfor();



/*
 *  eliminates copy statements of the form T1 = T2 from the intermediate
 *  code, where T1 and T2 are temporary variables which are each
 *  set only once;  eliminates the copy statement and replaces each
 *  use of T1 by T2 (T1 is therefore totally eliminated).
 */

LOCAL copyprop ()

{
Slotp	sl,nextsl;
expptr	expr;
Tempp	lp,rp;

for (sl = firstslot; sl; sl = sl->next)
	sl->expr = rmcommaop (sl->expr,sl);

prop1count = prop2count = 0;
findcopies ();

for (sl = firstslot; sl; sl = nextsl)
	{
	nextsl = sl->next;
	expr = sl->expr;

	if ((sl->type == SKFRTEMP) && subfor (expr))
		{
		delslot (sl);
		expr = ENULL;
		}
	else if (expr && expr->tag == TEXPR &&
			expr->exprblock.opcode == OPASSIGN)
		{
		lp = (Tempp) expr->exprblock.leftp;
		rp = (Tempp) expr->exprblock.rightp;
		if (lp->tag == TTEMP && rp->tag == TTEMP)
			if (subfor(lp->memalloc) == rp->memalloc
					&& !subfor (rp->memalloc))
				{
				frexpr (expr);
				expr = sl->expr = ENULL;
				prop1count++;
				}
		}

	propagate (expr);
	}

if (debugflag[0])
	fprintf (diagfile,
	    "%d temporarie%s replaced by copy propagation (%d use%s)\n",
		prop1count,(prop1count==1 ? "" : "s"),
		prop2count,(prop2count==1 ? "" : "s") );
}



/*
 *  finds copy statements and enters information in table
 */

LOCAL findcopies ()

{
Slotp	sl;
expptr	expr;
chainp	cp;

for (sl = firstslot; sl; sl = sl->next)
	{
	expr = sl->expr;
	if (expr) switch (expr->tag)
	    {
	    case TEXPR:
		ckexpr (expr);
		break;

	    case TLIST:
		for (cp = expr->listblock.listp; cp; cp = cp->nextp)
			{
			expr = (expptr) cp->datap;
			ckexpr (expr);
			}
		break;

	    default:
		break;
	    }
	}
}



/*
 *  checks an individual expression
 */

ckexpr (expr)
expptr	expr;

{
Tempp	lp,rp;
int	oc = expr->exprblock.opcode;

if (oc == OPASSIGN || oc == OPPLUSEQ || oc == OPSTAREQ)
	{
	lp = (Tempp) expr->exprblock.leftp;
	rp = (Tempp) expr->exprblock.rightp;
	if (lp->tag == TTEMP)
		if (rp->tag == TTEMP && oc == OPASSIGN)
			enter (lp->memalloc, rp->memalloc);
		else
			enter (lp->memalloc, ENULL);
	}
}



/*
 *  Enters the given memalloc values in the table (or update if they
 *  are already there), for the assignment statement m1 = m2.
 *  If m2 is NULL, this indicates that the assignment is not a copy
 *  statement.
 */

LOCAL enter (m1,m2)
Addrp	m1,m2;

{
chainp	cp;
Subrecp old,new;

for (cp = sublist; cp; cp = cp->nextp)
	{
	old = (Subrecp) cp->datap;
	if (old->lmem == m1)
		{
		old->sets++;