optcse.c

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

			{
			case TYSHORT:
			case TYLONG:
				if(ap->ci == bp->ci) return(TRUE);
				break;
			case TYREAL:
			case TYDREAL:
				if(ap->cd[0] == bp->cd[0]) return(TRUE);
				break;
			case TYCOMPLEX:
			case TYDCOMPLEX:
				if(ap->cd[0] == bp->cd[0] &&
				    ap->cd[1] == bp->cd[1] )
					return(TRUE);
				break;
			}
		}
		break;

	    default : 
		badtag ("samebase",ep2->tag);
	}
    return(FALSE);
}



LOCAL idptr findid(idaddr)
expptr idaddr;

/* Find an identifier's IDblock given its idaddr. If the identifier has no
** IBblock build one
*/

{
	register idptr idp;
	if(current_BB->headid == 0) newid(idaddr,&current_BB->headid);
	idp=current_BB->headid;

	do {
		if (samebase(idp->idaddr,idaddr) )  break;
		if (idp->next == 0) {
			newid(idaddr,&idp->next);
			idp = idp->next;
			break;
		}
		idp = idp->next;
	}
	while(TRUE);

	return(idp);
}



LOCAL valuen findnode(ep,leftc,rightc)
expptr ep;
valuen leftc,rightc;
{
	/* Look for a matching value node in the available computations stack
	*/  
	register valuen p;

	for ( p=current_BB->headnode; p ; p=p->next)  {
		if( ( ! p->is_dead)   &&
		    (p->lc == leftc)  &&
		    (p->rc == rightc) &&
		    ( (ep->tag == TEXPR && p->opp->tag == TEXPR 
		      && p->opp->exprblock.opcode == ep->exprblock.opcode
		      && p->opp->exprblock.vtype == ep->exprblock.vtype
		      )
		    || (ep->tag == TADDR) || (ep->tag == TTEMP)
		    )
		  ) 
			return(p);
	}
	return(NULL);
}



LOCAL valuen scanchain(listp,p_parent)
expptr listp;
chainp *p_parent;

/* Make value nodes from the chain hanging off a LISTBLOCK
*/

{
	valuen lnode,rnode,new,scantree();
	chainp p;

	p= *p_parent;
	if (p == NULL) return(NULL);
	lnode = scantree( &p->datap);
	rnode = scanchain(listp, &p->nextp);
	new = newnode(listp,lnode,rnode,0);    
	new->rs = new;
	return(new->rs);
}



LOCAL valuen scantree(p_parent)
expptr *p_parent;

/* build a value node and return its address. p must point to an
** exprblock an addrblock a listblock  or a constblock.
*/

{
valuen lnode, rnode,rsltnode,new;
expptr opp,p;
Exprp ep1,ep2;
idptr idp;

p = *p_parent;
if(p == NULL) return(NULL);

switch (p->tag) {
	case TCONST :
		return( findid(p)->initval );
	
	case TTEMP :
		idp = findid(p);
		if(idp->assgnval) return(idp->assgnval);
	
		lnode = idp->initval;
		rnode = scantree( &p->tempblock.memalloc);
	
		rsltnode = findnode(p,lnode,rnode);
		if(rsltnode)
			return(rsltnode);
		else { 
			new = newnode(p,lnode,rnode,0);
			new->rs = new;
			new->parent = p_parent;
			return(new->rs);
		}

	case TADDR :    
		idp = findid(p);
		if(idp->assgnval) return(idp->assgnval);
	
		lnode = idp->initval;
		rnode = scantree( &p->addrblock.memoffset);
	
		rsltnode = findnode(p,lnode,rnode);
		if(rsltnode) {
#ifdef	notdef
			/*
			 * This code is broken until OPINDIRECT is implemented.
			 */
			if(p->addrblock.memoffset != NULL &&
			    p->addrblock.memoffset->tag == TEXPR)
				addadup(p_parent,rsltnode);
#endif	notdef
			return(rsltnode);
		} 
		else { 
			new = newnode(p,lnode,rnode,0);
			new->rs = new;
			new->parent = p_parent;
			return(new->rs);
		}
	
	case TLIST :
		return(scanchain(p->listblock.listp,&p->listblock.listp));
	
	default :    
		badtag ("scantree",p->tag);
	
	case TEXPR  :    
		lnode = scantree(&p->exprblock.leftp);
		rnode = scantree(&p->exprblock.rightp);
	
		switch (p->exprblock.opcode) {
			case OPASSIGN :
				{
				Addrp ap;

				ap = (Addrp) p->exprblock.leftp;
				idp = findid(ap);
				killdepnodes(idp);
				if( ! ap->isarray ) {
					if(rnode->is_dead)idp->assgnval=idp->initval;
					else idp->assgnval = rnode;
				}
				new = newnode(p,idp->initval,NULL,NULL);
				appendnode(new);
				new->rs = new;
				return(new->rs);
				}

			/*
			 * Don't optimize these...  they're a real hassle.
			 */
			case OPPLUSEQ :
			case OPSTAREQ :
				{
				Addrp ap;

				ap = (Addrp) p->exprblock.leftp;
				idp = findid(ap);
				killdepnodes(idp);
				idp->assgnval = NULL;
				new = newnode(p,lnode,rnode,NULL);
				new->rs = new;
				return(new->rs);
				}

			case OPCALL :                    
				{
				chainp cp;

				if(p->exprblock.rightp)

	/* pretend that all variables on the arglist have just
	** been assigned to i.e. kill of calculations that 
	** depend on them. Not necessary for CCALL(by value)
	*/

				for(cp=p->exprblock.rightp->listblock.listp;
                                cp;cp=cp->nextp) 
					if (cp->datap->tag == TADDR ||
					    cp->datap->tag == TTEMP){
						idp = findid(cp->datap);
						killdepnodes(idp);
						idp->assgnval = NULL;
				}

				new = newnode(p,lnode,rnode,NULL);
				new->rs = new;
				return(new->rs);
				}

			case OPCONCAT:
			case OPADDR:
			case OPCOLON:
			case OPINDIRECT:
		/*
		 * For now, do not optimize LSHIFT until OPINDIRECT
		 * implemented.
		 */
			case OPLSHIFT:
				new = newnode(p,lnode,rnode,NULL);
				new->rs = new;
				return(new->rs);

			case OPCOMMA:
				badop ("scantree",OPCOMMA);
				break;

			default : 
				rsltnode = findnode(p,lnode,rnode);
				if (rsltnode) {
					addadup(p_parent,rsltnode);
					return(rsltnode);
				}
				else {
					new = newnode(p,lnode,rnode,NULL);
					new->rs = new;             
					new->parent = p_parent;
					appendnode(new);
					return(new->rs);
				}
			}
	}
}



LOCAL prunetrees()

/* The only optcse.c routine that does any real work: go through the available
** computations stack and eliminate redundant subtrees.
*/

{
Addrp tempv;
register duplptr dl;
register valuen p;
expptr t;
int is_addrnode;
expptr *addr_tree1 = NULL ;
expptr tree2 = NULL ;

for(p=current_BB->headnode;p;p=p->next) 
{
	if(p->rs == NULL) { 
		if( addr_tree1 && tree2 ) 
		     *addr_tree1 = fixtype(mkexpr(OPCOMMA,tree2,*addr_tree1));
		addr_tree1 = (expptr*) p->opp;
		tree2 = NULL;
	}
	if (p->n_dups ) {

		if (p->opp->tag == TTEMP)
			fprintf(diagfile,"TTEMP in prunetrees - cbb\n");
		if(p->opp->tag == TADDR) is_addrnode = TRUE;
		else is_addrnode = FALSE;

		if (is_addrnode)
			tempv = mktemp(TYADDR,NULL);
		else
			tempv = mktemp(p->opp->exprblock.vtype,
			    p->opp->exprblock.vleng);
		cse2count++;

		if(tree2)
			tree2 = fixtype(mkexpr(OPCOMMA,tree2,
				fixtype(mkexpr(OPASSIGN,cpexpr(tempv),
				(is_addrnode ? addrof(p->opp) :  p->opp)
				))));
		else
			tree2 = fixtype(mkexpr(OPASSIGN,cpexpr(tempv),
				(is_addrnode ? addrof(p->opp) :  p->opp)
				));

		if(is_addrnode)
			*(p->parent) = fixtype(mkexpr(OPINDIRECT,cpexpr(tempv), NULL));
		else
			*(p->parent) = (expptr) cpexpr(tempv);

/* then replaces all future instances of the calculation by references to
   the temporary */

		for(dl=p->headduplist;dl->next;dl=dl->next) {
			cse1count++;
			frexpr(*dl->parent);
			if(is_addrnode)
				*(dl->parent) = fixtype(
					mkexpr(OPINDIRECT,cpexpr(tempv), NULL));
			else
				*(dl->parent) = (expptr) cpexpr(tempv);
		}

/* the last reference does not use a copy since the temporary can
   now be freed */

		cse1count++;
		frexpr(*dl->parent);
		if(is_addrnode)
			*(dl->parent) = fixtype(mkexpr(OPINDIRECT,tempv, NULL));
		else
			*(dl->parent) = (expptr) tempv;

		frtemp (tempv);
	}                  
}
if(addr_tree1 && tree2)
	*addr_tree1 = fixtype(mkexpr(OPCOMMA,tree2,*addr_tree1));
}



LOCAL rewritebb (bb)
Bblockp bb;
{
	Slotp sp; 
	expptr p;

	if (bb == NULL)
		return;
	else
		current_BB = bb;
	sp = current_BB->first;

	/* loop trough all BB slots and scan candidate expr trees when found */

	for (sp = current_BB->first; ; sp = sp->next)
		{
		switch (sp->type)
		    {
		    case SKEQ : 
		    case SKIFN : 
		    case SKCMGOTO :
		    case SKCALL :
			newnode((expptr) &sp->expr,NULL,NULL,NULL);
			scantree(&sp->expr); 
			break;

		    default  : 
			break;
		    }
		if (sp == current_BB->last) break;
		}

/* use the information built up by scantree to prune reduntant subtrees */
	prunetrees();

	current_BB = NULL;
}



/*
 *  removes all instances of OPCOMMA from the given subexpression of
 *  the given buffer slot
 */

expptr rmcommaop (p,sl)
expptr	p;
Slotp	sl;

{
expptr	leftp,rightp;
chainp	cp;

if (!p)
	return (ENULL);
switch (p->tag)
	{
	case TEXPR:
		leftp = p->exprblock.leftp;
		rightp = p->exprblock.rightp;
		leftp = rmcommaop (leftp,sl);
		if (p->exprblock.opcode == OPCOMMA)
			{
			optinsert (SKEQ,leftp,0,0,sl);
			if (p->exprblock.vleng)
				free ((charptr) p->exprblock.vleng);
			free ((charptr) p);
			p = rmcommaop (rightp,sl);
			return (p);
			}
		p->exprblock.leftp = leftp;
		p->exprblock.rightp = rmcommaop (rightp,sl);
		return (p);

	case TLIST:
		for (cp = p->listblock.listp; cp; cp = cp->nextp)
			cp->datap = (tagptr) rmcommaop (cp->datap,sl);
		return (p);

	case TADDR:
		p->addrblock.memoffset = rmcommaop (p->addrblock.memoffset,sl);
		return (p);

	default:
		return (p);
	}
}



/*
 *  scans the code buffer, performing common subexpression elimination
 */

optcse ()

{
Slotp	sl;
Bblockp	bb;

if (debugflag[13])
	return;

cse1count = 0;
cse2count = 0;
for (sl = firstslot; sl; sl = sl->next)
	sl->expr = rmcommaop (sl->expr,sl);
for (bb = firstblock; bb; bb = bb->next)
	rewritebb (bb);

if (debugflag[0])
	fprintf (diagfile,
		"%d common subexpression use%s eliminated (%d definition%s)\n",
		cse1count, (cse1count==1 ? "" : "s"),
		cse2count, (cse2count==1 ? "" : "s"));
}