* Copyright (c) 1980 Regents of the University of California.
* All rights reserved. The Berkeley software License Agreement
* specifies the terms and conditions for redistribution.
static char sccsid
[] = "@(#)optcse.c 5.1 (Berkeley) 6/7/85";
* Common subexpression elimination routines, F77 compiler pass 1.
* University of Utah CS Dept modification history:
* 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
* 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.
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 */
fprintf(diagfile
,"\n *** IDblocks ***\n");
for(idp
=current_BB
->headid
;idp
;idp
=idp
->next
)
"idp= %d idaddr= %d initval= %d assgnval= %d \n",
idp
, idp
->idaddr
, idp
->initval
, idp
->assgnval
);
fprintf(diagfile
,"nodes: ");
for (nl
=idp
->headnodelist
;nl
;nl
=nl
->next
) {
fprintf(diagfile
," %d ",nl
->nodep
);
fprintf(diagfile
,"\n *** VALUE NODES *** \n");
for(p
=current_BB
->headnode
;p
;p
=p
->next
) {
"\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
);
fprintf(diagfile
,"tag= %d ",p
->opp
->tag
);
fprintf(diagfile
,"opco= %d ",
p
->opp
->exprblock
.opcode
);
fprintf(diagfile
,"parent= %d dups: ",p
->parent
);
for(dl
=p
->headduplist
;dl
;dl
=dl
->next
) {
fprintf(diagfile
," %d ",dl
->parent
);
fprintf(diagfile
,"\ndeps IDs");
for(idl
=p
->headdeplist
;idl
;idl
=idl
->next
) {
fprintf(diagfile
," %d ",idl
->idp
);
LOCAL idlptr
mergedeps(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
;
lp
= lp1
= lp2
= head
= NULL
;
if(lnode
) lp1
= lnode
->headdeplist
;
if(rnode
) lp2
= rnode
->headdeplist
;
lp
->next
= ALLOC(IDlist
);
else lp
= head
= ALLOC(IDlist
);
else if (lp1
->idp
< lp2
->idp
) {
else if (lp1
->idp
> lp2
->idp
) {
/* Removes a value node from every IDblock on the node's list of identifiers.
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
)
/* 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.
for (nl1
= idp
->headnodelist
; nl1
; nl1
=nl2
)
/* 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
;
/* 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
if(idp
->idaddr
->addrblock
.vstg
== STGCOMMON
)
for(idp
=current_BB
->headid
;idp
;idp
=idp
->next
)
if(idp
->idaddr
->addrblock
.vstg
== STGCOMMON
)
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
)
/* 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.
for(idl
=nodep
->headdeplist
;idl
;idl
=idl
->next
)
if(idl
->idp
->idaddr
->tag
== TADDR
||
idl
->idp
->idaddr
->tag
== TTEMP
)
nl
->next
= idl
->idp
->headnodelist
;
idl
->idp
->headnodelist
= nl
;
LOCAL idlptr
addadep(idp
,nodep
)
/* Add an identifier to the dependents list of a value node. Dependents
** lists are ordered by increasing idp value
if(nodep
->headdeplist
== 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
) )
LOCAL valuen
newnode(expr
,left
,right
,rslt
)
/* Build a new value node
p
->headdeplist
= mergedeps(left
,right
);
if(current_BB
->headnode
== 0) current_BB
->headnode
=p
;
else if(current_BB
->tailnode
) current_BB
->tailnode
->next
=p
;
LOCAL
newid(idaddr
,addrof_idptr
)
/* Build a new IDblock and hook it on the current BB's ID list
/* 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
;
LOCAL
addadup(parent
,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.
dp
->next
= nodep
->headduplist
;
/* 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
) )
child
->headduplist
= dp
->next
;
if ( (child
= nodep
->rc
) && (child
->n_dups
) )
child
->headduplist
= dp
->next
;
if ( ep1
->tag
== ep2
->tag
)
if (ep1
->tempblock
.memalloc
== ep2
->tempblock
.memalloc
)
if (ep1
->addrblock
.vstg
== ep2
->addrblock
.vstg
) {
switch(ep1
->addrblock
.vstg
) {
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
) {
if (ep1
->addrblock
.memno
== ep2
->addrblock
.memno
) {
if( (ep1
->constblock
.vtype
) ==
(ep2
->constblock
.vtype
) )
ap
= &ep1
->constblock
.const;
bp
= &ep2
->constblock
.const;
switch(ep1
->constblock
.vtype
)
if(ap
->ci
== bp
->ci
) return(TRUE
);
if(ap
->cd
[0] == bp
->cd
[0]) return(TRUE
);
if(ap
->cd
[0] == bp
->cd
[0] &&
badtag ("samebase",ep2
->tag
);
LOCAL idptr
findid(idaddr
)
/* Find an identifier's IDblock given its idaddr. If the identifier has no
if(current_BB
->headid
== 0) newid(idaddr
,¤t_BB
->headid
);
if (samebase(idp
->idaddr
,idaddr
) ) break;
newid(idaddr
,&idp
->next
);
LOCAL valuen
findnode(ep
,leftc
,rightc
)
/* Look for a matching value node in the available computations stack
for ( p
=current_BB
->headnode
; p
; p
=p
->next
) {
( (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
)
LOCAL valuen
scanchain(listp
,p_parent
)
/* Make value nodes from the chain hanging off a LISTBLOCK
valuen lnode
,rnode
,new,scantree();
if (p
== NULL
) return(NULL
);
lnode
= scantree( &p
->datap
);
rnode
= scanchain(listp
, &p
->nextp
);
new = newnode(listp
,lnode
,rnode
,0);
LOCAL valuen
scantree(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;
if(p
== NULL
) return(NULL
);
return( findid(p
)->initval
);
if(idp
->assgnval
) return(idp
->assgnval
);
rnode
= scantree( &p
->tempblock
.memalloc
);
rsltnode
= findnode(p
,lnode
,rnode
);
new = newnode(p
,lnode
,rnode
,0);
if(idp
->assgnval
) return(idp
->assgnval
);
rnode
= scantree( &p
->addrblock
.memoffset
);
rsltnode
= findnode(p
,lnode
,rnode
);
* This code is broken until OPINDIRECT is implemented.
if(p
->addrblock
.memoffset
!= NULL
&&
p
->addrblock
.memoffset
->tag
== TEXPR
)
addadup(p_parent
,rsltnode
);
new = newnode(p
,lnode
,rnode
,0);
return(scanchain(p
->listblock
.listp
,&p
->listblock
.listp
));
badtag ("scantree",p
->tag
);
lnode
= scantree(&p
->exprblock
.leftp
);
rnode
= scantree(&p
->exprblock
.rightp
);
switch (p
->exprblock
.opcode
) {
ap
= (Addrp
) p
->exprblock
.leftp
;
if(rnode
->is_dead
)idp
->assgnval
=idp
->initval
;
else idp
->assgnval
= rnode
;
new = newnode(p
,idp
->initval
,NULL
,NULL
);
* Don't optimize these... they're a real hassle.
ap
= (Addrp
) p
->exprblock
.leftp
;
new = newnode(p
,lnode
,rnode
,NULL
);
/* 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
;
if (cp
->datap
->tag
== TADDR
||
cp
->datap
->tag
== TTEMP
){
new = newnode(p
,lnode
,rnode
,NULL
);
* For now, do not optimize LSHIFT until OPINDIRECT
new = newnode(p
,lnode
,rnode
,NULL
);
badop ("scantree",OPCOMMA
);
rsltnode
= findnode(p
,lnode
,rnode
);
addadup(p_parent
,rsltnode
);
new = newnode(p
,lnode
,rnode
,NULL
);
/* The only optcse.c routine that does any real work: go through the available
** computations stack and eliminate redundant subtrees.
expptr
*addr_tree1
= NULL
;
for(p
=current_BB
->headnode
;p
;p
=p
->next
)
if( addr_tree1
&& tree2
)
*addr_tree1
= fixtype(mkexpr(OPCOMMA
,tree2
,*addr_tree1
));
addr_tree1
= (expptr
*) p
->opp
;
if (p
->opp
->tag
== TTEMP
)
fprintf(diagfile
,"TTEMP in prunetrees - cbb\n");
if(p
->opp
->tag
== TADDR
) is_addrnode
= TRUE
;
else is_addrnode
= FALSE
;
tempv
= mktemp(TYADDR
,NULL
);
tempv
= mktemp(p
->opp
->exprblock
.vtype
,
p
->opp
->exprblock
.vleng
);
tree2
= fixtype(mkexpr(OPCOMMA
,tree2
,
fixtype(mkexpr(OPASSIGN
,cpexpr(tempv
),
(is_addrnode
? addrof(p
->opp
) : p
->opp
)
tree2
= fixtype(mkexpr(OPASSIGN
,cpexpr(tempv
),
(is_addrnode
? addrof(p
->opp
) : p
->opp
)
*(p
->parent
) = fixtype(mkexpr(OPINDIRECT
,cpexpr(tempv
), NULL
));
*(p
->parent
) = (expptr
) cpexpr(tempv
);
/* then replaces all future instances of the calculation by references to
for(dl
=p
->headduplist
;dl
->next
;dl
=dl
->next
) {
mkexpr(OPINDIRECT
,cpexpr(tempv
), NULL
));
*(dl
->parent
) = (expptr
) cpexpr(tempv
);
/* the last reference does not use a copy since the temporary can
*(dl
->parent
) = fixtype(mkexpr(OPINDIRECT
,tempv
, NULL
));
*(dl
->parent
) = (expptr
) tempv
;
*addr_tree1
= fixtype(mkexpr(OPCOMMA
,tree2
,*addr_tree1
));
/* loop trough all BB slots and scan candidate expr trees when found */
for (sp
= current_BB
->first
; ; sp
= sp
->next
)
newnode((expptr
) &sp
->expr
,NULL
,NULL
,NULL
);
if (sp
== current_BB
->last
) break;
/* use the information built up by scantree to prune reduntant subtrees */
* removes all instances of OPCOMMA from the given subexpression of
leftp
= p
->exprblock
.leftp
;
rightp
= p
->exprblock
.rightp
;
leftp
= rmcommaop (leftp
,sl
);
if (p
->exprblock
.opcode
== OPCOMMA
)
optinsert (SKEQ
,leftp
,0,0,sl
);
free ((charptr
) p
->exprblock
.vleng
);
p
= rmcommaop (rightp
,sl
);
p
->exprblock
.leftp
= leftp
;
p
->exprblock
.rightp
= rmcommaop (rightp
,sl
);
for (cp
= p
->listblock
.listp
; cp
; cp
= cp
->nextp
)
cp
->datap
= (tagptr
) rmcommaop (cp
->datap
,sl
);
p
->addrblock
.memoffset
= rmcommaop (p
->addrblock
.memoffset
,sl
);
* scans the code buffer, performing common subexpression elimination
for (sl
= firstslot
; sl
; sl
= sl
->next
)
sl
->expr
= rmcommaop (sl
->expr
,sl
);
for (bb
= firstblock
; bb
; bb
= bb
->next
)
"%d common subexpression use%s eliminated (%d definition%s)\n",
cse1count
, (cse1count
==1 ? "" : "s"),
cse2count
, (cse2count
==1 ? "" : "s"));