1 /*
2  * Copyright (c) 1980 Regents of the University of California.
3  * All rights reserved.  The Berkeley software License Agreement
4  * specifies the terms and conditions for redistribution.
5  */
6 
7 #ifndef lint
8 static char sccsid[] = "@(#)optcse.c	5.1 (Berkeley) 6/7/85";
9 #endif not lint
10 
11 /*
12  * optcse.c
13  *
14  * Common subexpression elimination routines, F77 compiler pass 1.
15  *
16  * University of Utah CS Dept modification history:
17  *
18  * $Log:	optcse.c,v $
19  * Revision 2.4  84/10/29  04:40:48  donn
20  * Problem with conversions -- two expressions headed by a conversion may be
21  * identical in structure but different in type, thus type must be checked in
22  * findnode().  This was causing a subscript to become REAL*8 type...
23  *
24  * Revision 2.3  84/08/04  20:38:53  donn
25  * Added fix from Jerry Berkman for an earlier fix from Alastair Fyfe --
26  * samebase() should treat EQUIVALENCEd variables just as daintily as
27  * COMMON variables.
28  *
29  * Revision 2.2  84/08/01  16:04:33  donn
30  * Changed rmcommaop so that it does subscripts too.
31  *
32  * Revision 2.1  84/07/19  12:03:44  donn
33  * Changed comment headers for UofU.
34  *
35  * Revision 1.5  84/07/09  14:43:05  donn
36  * Added changes to make OPPLUSEQ and OPSTAREQ expressions ineligible for
37  * CSE, since I can't think of a simple way to handle them and they are broken
38  * in the previous version, where they were treated like OPASSIGN -- this
39  * fails because CSE would think that the value of the lhs and rhs were equal.
40  *
41  * Revision 1.4  84/06/08  11:43:35  donn
42  * Yet another way of handling the bug with COMMON -- this one is from Alastair
43  * Fyfe at Sun.  I backed out the old fix.
44  *
45  * Revision 1.3  84/03/07  19:25:14  donn
46  * Changed method of handling COMMON bug -- COMMON variables are now treated
47  * like array elements and hence are ineligible for CSE.
48  *
49  * Revision 1.2  84/02/26  03:30:47  donn
50  * Fixed bug in evaluation graph construction that caused two variables in
51  * common to be considered identical if they were merely in the same common,
52  * rather than in the same common at the same offset.
53  *
54  */
55 
56 #include "defs.h"
57 #include "optim.h"
58 
59 #define FALSE	0
60 #define TRUE	1
61 
62 LOCAL Bblockp	current_BB;
63 LOCAL int	cse1count;	/* count of number of cse uses eliminated */
64 LOCAL int	cse2count;	/* count of number of cse def's eliminated */
65 
66 
67 
68 
69 LOCAL dumpstacks()
70 {
71 	duplptr dl;
72 	valuen p;
73 	idlptr idl;
74 	idptr idp;
75 	nodelptr nl;
76 	int i;
77 
78 	fprintf(diagfile,"\n *** IDblocks ***\n");
79 	for(idp=current_BB->headid;idp;idp=idp->next)
80 	{
81 		fprintf(diagfile,
82 			"idp= %d idaddr= %d initval= %d assgnval= %d \n",
83 			idp, idp->idaddr, idp->initval, idp->assgnval);
84 		fprintf(diagfile,"nodes: ");
85 		i=0;
86 		for (nl=idp->headnodelist;nl;nl=nl->next) {
87 			if(++i>20){
88 				fprintf(diagfile,"\n");
89 				i=0;
90 			}
91 			fprintf(diagfile," %d ",nl->nodep);
92 		}
93 		fprintf(diagfile,"\n");
94 	}
95 
96 	fprintf(diagfile,"\n *** VALUE NODES *** \n");
97 	for(p=current_BB->headnode;p;p=p->next) {
98 		fprintf(diagfile,
99 		   "\np= %d opp= %d lc= %d rc= %d rs= %d is_dead= %d n_dups %d",
100 		   p, p->opp,p->lc,p->rc, p->rs, p->is_dead, p->n_dups);
101 		if (p->rs){
102 			fprintf(diagfile,"tag= %d ",p->opp->tag);
103 			if(p->opp->tag==TEXPR)
104 				fprintf(diagfile,"opco= %d ",
105 				    p->opp->exprblock.opcode);
106 		}
107 		fprintf(diagfile,"\n");
108 		fprintf(diagfile,"parent= %d dups:  ",p->parent);
109 		i=0;
110 		for(dl=p->headduplist;dl;dl=dl->next) {
111 			if(++i>20){
112 				fprintf(diagfile,"\n");
113 				i=0;
114 			}
115 			fprintf(diagfile," %d ",dl->parent);
116 		}
117 
118 		fprintf(diagfile,"\ndeps IDs");
119 		i=0;
120 		for(idl=p->headdeplist;idl;idl=idl->next) {
121 			if(++i>20){
122 				fprintf(diagfile,"\n");
123 				i=0;
124 			}
125 			fprintf(diagfile," %d ",idl->idp);
126 		}
127 	}
128 }
129 
130 
131 
132 LOCAL idlptr mergedeps(lnode,rnode)
133 valuen lnode,rnode;
134 /* Given two value nodes, merge the lists of identifiers on which they
135 ** depend to produce a new list incorporating both dependencies. Lists
136 ** are assumed to be ordered by increasing idp address. No duplicate identifiers
137 ** are generated in the output list.
138 */
139 {
140 	register idlptr lp,lp1,lp2;
141 	idlptr head;
142 
143 	lp = lp1 = lp2 = head = NULL;
144 	if(lnode) lp1 = lnode->headdeplist;
145 	if(rnode) lp2 = rnode->headdeplist;
146 
147 	while (lp1 || lp2) {
148 		if (lp) {
149 			lp->next = ALLOC(IDlist);
150 			lp = lp->next;
151 		}
152 		else lp = head = ALLOC(IDlist);
153 		lp->next = 0;
154 		if (lp1 == 0) {
155 			lp->idp = lp2->idp;
156 			lp2 = lp2->next;
157 		}
158 		else if (lp2 == 0) {
159 			lp->idp = lp1->idp;
160 			lp1 = lp1->next;
161 		}
162 		else if (lp1->idp < lp2->idp) {
163 			lp->idp = lp1->idp;
164 			lp1 = lp1->next;
165 		}
166 		else if (lp1->idp > lp2->idp) {
167 			lp->idp = lp2->idp;
168 			lp2 = lp2->next;
169 		}
170 		else {
171 			lp->idp = lp1->idp;
172 			lp1 = lp1->next;
173 			lp2 = lp2->next;
174 		}
175 	}
176 	return(head);
177 }
178 
179 
180 
181 LOCAL removenode(nodep)
182 valuen nodep;
183 /*  Removes a value node from every IDblock on the node's list of identifiers.
184 */
185 {
186 	register idlptr idl;
187 	register nodelptr nl;
188 	register nodelptr *addrnl;
189 
190 	if(nodep == NULL) return ;
191 
192 	/* loop through all identifiers */
193 	for(idl=nodep->headdeplist;idl;idl=idl->next)
194 	{
195 		addrnl = &(idl->idp->headnodelist);
196 		/* for each identifier loop through all nodes until match is found */
197 		for(nl = *addrnl; nl; nl = *addrnl)
198 		{
199 			if(nl->nodep == nodep) {
200 				*addrnl = nl->next;
201 				free ( (charptr) nl );
202 				break;
203 			}
204 			addrnl = &nl->next;
205 		}
206 	}
207 	nodep->is_dead = TRUE;
208 }
209 
210 
211 
212 LOCAL killid(idp)
213 idptr idp;
214 /* Kill all nodes on one identifier's list of dependent nodes, i.e. remove
215 ** all calculations that depend on this identifier from the available
216 ** values stack.  Free the list of records pointing at the dependent nodes.
217 */
218 {
219 	nodelptr nl1,nl2;
220 
221 	for (nl1 = idp->headnodelist; nl1; nl1=nl2)
222 	{
223 		nl2 = nl1->next;
224 		removenode(nl1->nodep);
225 	}
226 	/* the above call frees the node list record pointed at by nl1 since it frees
227 	** all the node list records that reference the value node being killed
228 	*/
229 	idp->headnodelist = NULL;
230 
231 }
232 
233 
234 
235 LOCAL killdepnodes(idp)
236 idptr idp;
237 /* Kill all value nodes that represent calculations which depend on
238 ** this identifier. If the identifier is in COMMON or EQUIVALENCE storage,
239 ** kill all values that depend on identifiers in COMMON or EQUIVALENCE
240 */
241 {
242 	int thismemno;
243 
244 	if(idp->idaddr->addrblock.vstg == STGCOMMON)
245 	{
246 		for(idp=current_BB->headid;idp;idp=idp->next)
247 			if(idp->idaddr->addrblock.vstg == STGCOMMON)
248 				killid(idp);
249 	}
250 	else if(idp->idaddr->addrblock.vstg == STGEQUIV)
251 	{
252 		thismemno=idp->idaddr->addrblock.memno;
253 		for(idp=current_BB->headid;idp;idp=idp->next)
254 			if(idp->idaddr->addrblock.vstg == STGEQUIV
255 			    && idp->idaddr->addrblock.memno == thismemno)
256 				killid(idp);
257 	}
258 	else killid(idp);
259 
260 }
261 
262 
263 
264 LOCAL appendnode(nodep)
265 valuen nodep;
266 /* Append a value node to all the IDblocks on that node's list of
267 ** dependent identifiers i.e., since this computation depends on
268 ** all the identifiers on its list then each of those identifiers should
269 ** include this node in their list of dependent nodes.
270 */
271 {
272 	register idlptr idl;
273 	register nodelptr nl;
274 
275 	for(idl=nodep->headdeplist;idl;idl=idl->next)
276 		if(idl->idp->idaddr->tag == TADDR ||
277 		   idl->idp->idaddr->tag == TTEMP)
278 			{
279 			nl=ALLOC(NODElist);
280 			nl->nodep = nodep;
281 			nl->next = idl->idp->headnodelist;
282 			idl->idp->headnodelist = nl;
283 			}
284 }
285 
286 
287 
288 LOCAL idlptr addadep(idp,nodep)
289 idptr idp;
290 valuen nodep;
291 /* Add an identifier to the dependents list of a value node.  Dependents
292 ** lists are ordered by increasing idp value
293 */
294 {
295 	register idlptr lp1,lp2;
296 
297 	lp2 = ALLOC(IDlist);
298 	lp2->idp = idp;
299 	if(nodep->headdeplist == 0) {
300 		lp2->next = 0;
301 		nodep->headdeplist = lp2;
302 	}
303 	else if(idp <= nodep->headdeplist->idp) {
304 		lp2->next = nodep->headdeplist;
305 		nodep->headdeplist = lp2;
306 	}
307 	else for(lp1 = nodep->headdeplist; lp1; lp1 = lp1->next)
308 		if( (lp1->next == 0) || (idp <= lp1->next->idp) )
309 		{
310 			lp2->next = lp1->next;
311 			lp1->next = lp2;
312 			break;
313 		}
314 	return(lp2);
315 }
316 
317 
318 
319 LOCAL valuen newnode(expr,left,right,rslt)
320 expptr expr;
321 valuen left,right,rslt;
322 /* Build a new value node
323 */
324 {
325 	register valuen p;
326 
327 	p= ALLOC(VALUEnode);
328 	p->opp = expr ;
329 	p->parent = NULL ;
330 	p->lc = left;
331 	p->rc = right;
332 	p->rs = rslt;
333 	p->n_dups = 0;
334 	p->is_dead = FALSE;
335 	p->next=NULL;
336 	p->headdeplist = mergedeps(left,right);
337 	p->headduplist=NULL;
338 	if(current_BB->headnode == 0) current_BB->headnode=p;
339 	else if(current_BB->tailnode) current_BB->tailnode->next=p;
340 	current_BB->tailnode=p;
341 
342 	return(p);
343 }
344 
345 
346 
347 LOCAL newid(idaddr,addrof_idptr)
348 expptr idaddr;
349 idptr *addrof_idptr;
350 /* Build a new IDblock and hook it on the current BB's ID list
351 */
352 {
353 	register idptr p;
354 
355 	p= ALLOC(IDblock);
356 
357 /* build a leaf value node for the identifier and put the ID on the leaf node's
358 ** list of dependent identifiers
359 */
360 	p->initval =  newnode(idaddr,NULL,NULL,NULL);
361 	p->initval->rs = p->initval;
362 	addadep(p,p->initval);
363 
364 	p->idaddr = idaddr;
365 	*addrof_idptr = p;
366 	p->headnodelist=NULL;
367 	p->next=NULL;
368 
369 }
370 
371 
372 
373 LOCAL addadup(parent,nodep)
374 expptr *parent;
375 valuen nodep;
376 
377 /* A subtree has been found that duplicates the calculation represented
378 ** by the value node referenced by nodep : add the root of the reduntant
379 ** tree to the value node's list of duplicates.
380 */
381 
382 {
383 	register duplptr dp;
384 	valuen child;
385 
386 	dp = ALLOC(DUPlist);
387 	dp->parent = parent;
388 	dp->next = nodep->headduplist;
389 	nodep->headduplist = dp;
390 	++nodep->n_dups;
391 
392 /* Check whether either of nodep's children is also a duplicate calculation
393 ** and if so peel off it's most recent dup record
394 */
395 
396 	if ( (child = nodep->lc) && (child->n_dups) )
397 	{
398 		dp = child->headduplist;
399 		child->headduplist = dp->next;
400 		free ( (charptr) dp );
401 		--child->n_dups;
402 	}
403 	if ( (child = nodep->rc) && (child->n_dups) )
404 	{
405 		dp = child->headduplist;
406 		child->headduplist = dp->next;
407 		free ( (charptr) dp );
408 		--child->n_dups;
409 	}
410 
411 }
412 
413 
414 
415 LOCAL samebase(ep1,ep2)
416 expptr ep1,ep2;
417 {
418     if ( ep1->tag == ep2->tag  )
419 	switch (ep2->tag) {
420 	    case TTEMP :
421 		if (ep1->tempblock.memalloc == ep2->tempblock.memalloc)
422 			return (TRUE);
423 		break;
424 	    case TADDR :
425 		if (ep1->addrblock.vstg == ep2->addrblock.vstg) {
426 		    switch(ep1->addrblock.vstg) {
427 			case STGEQUIV:
428 			case STGCOMMON:
429 			    if (ep1->addrblock.memno == ep2->addrblock.memno &&
430 				ISCONST(ep1->addrblock.memoffset) &&
431 				ISCONST(ep2->addrblock.memoffset) &&
432 				ep1->addrblock.memoffset->constblock.const.ci ==
433 				ep2->addrblock.memoffset->constblock.const.ci ) {
434 				    return(TRUE);
435 			    }
436 			    break;
437 
438 			default:
439 			    if (ep1->addrblock.memno == ep2->addrblock.memno ) {
440 				return(TRUE);
441 			    }
442 		    }
443 		}
444 		break;
445 	    case TCONST :
446 		if( (ep1->constblock.vtype) ==
447 		    (ep2->constblock.vtype)  )
448 		{
449 			union Constant *ap,*bp;
450 			ap= &ep1->constblock.const;
451 			bp= &ep2->constblock.const;
452 			switch(ep1->constblock.vtype)
453 
454 			{
455 			case TYSHORT:
456 			case TYLONG:
457 				if(ap->ci == bp->ci) return(TRUE);
458 				break;
459 			case TYREAL:
460 			case TYDREAL:
461 				if(ap->cd[0] == bp->cd[0]) return(TRUE);
462 				break;
463 			case TYCOMPLEX:
464 			case TYDCOMPLEX:
465 				if(ap->cd[0] == bp->cd[0] &&
466 				    ap->cd[1] == bp->cd[1] )
467 					return(TRUE);
468 				break;
469 			}
470 		}
471 		break;
472 
473 	    default :
474 		badtag ("samebase",ep2->tag);
475 	}
476     return(FALSE);
477 }
478 
479 
480 
481 LOCAL idptr findid(idaddr)
482 expptr idaddr;
483 
484 /* Find an identifier's IDblock given its idaddr. If the identifier has no
485 ** IBblock build one
486 */
487 
488 {
489 	register idptr idp;
490 	if(current_BB->headid == 0) newid(idaddr,&current_BB->headid);
491 	idp=current_BB->headid;
492 
493 	do {
494 		if (samebase(idp->idaddr,idaddr) )  break;
495 		if (idp->next == 0) {
496 			newid(idaddr,&idp->next);
497 			idp = idp->next;
498 			break;
499 		}
500 		idp = idp->next;
501 	}
502 	while(TRUE);
503 
504 	return(idp);
505 }
506 
507 
508 
509 LOCAL valuen findnode(ep,leftc,rightc)
510 expptr ep;
511 valuen leftc,rightc;
512 {
513 	/* Look for a matching value node in the available computations stack
514 	*/
515 	register valuen p;
516 
517 	for ( p=current_BB->headnode; p ; p=p->next)  {
518 		if( ( ! p->is_dead)   &&
519 		    (p->lc == leftc)  &&
520 		    (p->rc == rightc) &&
521 		    ( (ep->tag == TEXPR && p->opp->tag == TEXPR
522 		      && p->opp->exprblock.opcode == ep->exprblock.opcode
523 		      && p->opp->exprblock.vtype == ep->exprblock.vtype
524 		      )
525 		    || (ep->tag == TADDR) || (ep->tag == TTEMP)
526 		    )
527 		  )
528 			return(p);
529 	}
530 	return(NULL);
531 }
532 
533 
534 
535 LOCAL valuen scanchain(listp,p_parent)
536 expptr listp;
537 chainp *p_parent;
538 
539 /* Make value nodes from the chain hanging off a LISTBLOCK
540 */
541 
542 {
543 	valuen lnode,rnode,new,scantree();
544 	chainp p;
545 
546 	p= *p_parent;
547 	if (p == NULL) return(NULL);
548 	lnode = scantree( &p->datap);
549 	rnode = scanchain(listp, &p->nextp);
550 	new = newnode(listp,lnode,rnode,0);
551 	new->rs = new;
552 	return(new->rs);
553 }
554 
555 
556 
557 LOCAL valuen scantree(p_parent)
558 expptr *p_parent;
559 
560 /* build a value node and return its address. p must point to an
561 ** exprblock an addrblock a listblock  or a constblock.
562 */
563 
564 {
565 valuen lnode, rnode,rsltnode,new;
566 expptr opp,p;
567 Exprp ep1,ep2;
568 idptr idp;
569 
570 p = *p_parent;
571 if(p == NULL) return(NULL);
572 
573 switch (p->tag) {
574 	case TCONST :
575 		return( findid(p)->initval );
576 
577 	case TTEMP :
578 		idp = findid(p);
579 		if(idp->assgnval) return(idp->assgnval);
580 
581 		lnode = idp->initval;
582 		rnode = scantree( &p->tempblock.memalloc);
583 
584 		rsltnode = findnode(p,lnode,rnode);
585 		if(rsltnode)
586 			return(rsltnode);
587 		else {
588 			new = newnode(p,lnode,rnode,0);
589 			new->rs = new;
590 			new->parent = p_parent;
591 			return(new->rs);
592 		}
593 
594 	case TADDR :
595 		idp = findid(p);
596 		if(idp->assgnval) return(idp->assgnval);
597 
598 		lnode = idp->initval;
599 		rnode = scantree( &p->addrblock.memoffset);
600 
601 		rsltnode = findnode(p,lnode,rnode);
602 		if(rsltnode) {
603 #ifdef	notdef
604 			/*
605 			 * This code is broken until OPINDIRECT is implemented.
606 			 */
607 			if(p->addrblock.memoffset != NULL &&
608 			    p->addrblock.memoffset->tag == TEXPR)
609 				addadup(p_parent,rsltnode);
610 #endif	notdef
611 			return(rsltnode);
612 		}
613 		else {
614 			new = newnode(p,lnode,rnode,0);
615 			new->rs = new;
616 			new->parent = p_parent;
617 			return(new->rs);
618 		}
619 
620 	case TLIST :
621 		return(scanchain(p->listblock.listp,&p->listblock.listp));
622 
623 	default :
624 		badtag ("scantree",p->tag);
625 
626 	case TEXPR  :
627 		lnode = scantree(&p->exprblock.leftp);
628 		rnode = scantree(&p->exprblock.rightp);
629 
630 		switch (p->exprblock.opcode) {
631 			case OPASSIGN :
632 				{
633 				Addrp ap;
634 
635 				ap = (Addrp) p->exprblock.leftp;
636 				idp = findid(ap);
637 				killdepnodes(idp);
638 				if( ! ap->isarray ) {
639 					if(rnode->is_dead)idp->assgnval=idp->initval;
640 					else idp->assgnval = rnode;
641 				}
642 				new = newnode(p,idp->initval,NULL,NULL);
643 				appendnode(new);
644 				new->rs = new;
645 				return(new->rs);
646 				}
647 
648 			/*
649 			 * Don't optimize these...  they're a real hassle.
650 			 */
651 			case OPPLUSEQ :
652 			case OPSTAREQ :
653 				{
654 				Addrp ap;
655 
656 				ap = (Addrp) p->exprblock.leftp;
657 				idp = findid(ap);
658 				killdepnodes(idp);
659 				idp->assgnval = NULL;
660 				new = newnode(p,lnode,rnode,NULL);
661 				new->rs = new;
662 				return(new->rs);
663 				}
664 
665 			case OPCALL :
666 				{
667 				chainp cp;
668 
669 				if(p->exprblock.rightp)
670 
671 	/* pretend that all variables on the arglist have just
672 	** been assigned to i.e. kill of calculations that
673 	** depend on them. Not necessary for CCALL(by value)
674 	*/
675 
676 				for(cp=p->exprblock.rightp->listblock.listp;
677                                 cp;cp=cp->nextp)
678 					if (cp->datap->tag == TADDR ||
679 					    cp->datap->tag == TTEMP){
680 						idp = findid(cp->datap);
681 						killdepnodes(idp);
682 						idp->assgnval = NULL;
683 				}
684 
685 				new = newnode(p,lnode,rnode,NULL);
686 				new->rs = new;
687 				return(new->rs);
688 				}
689 
690 			case OPCONCAT:
691 			case OPADDR:
692 			case OPCOLON:
693 			case OPINDIRECT:
694 		/*
695 		 * For now, do not optimize LSHIFT until OPINDIRECT
696 		 * implemented.
697 		 */
698 			case OPLSHIFT:
699 				new = newnode(p,lnode,rnode,NULL);
700 				new->rs = new;
701 				return(new->rs);
702 
703 			case OPCOMMA:
704 				badop ("scantree",OPCOMMA);
705 				break;
706 
707 			default :
708 				rsltnode = findnode(p,lnode,rnode);
709 				if (rsltnode) {
710 					addadup(p_parent,rsltnode);
711 					return(rsltnode);
712 				}
713 				else {
714 					new = newnode(p,lnode,rnode,NULL);
715 					new->rs = new;
716 					new->parent = p_parent;
717 					appendnode(new);
718 					return(new->rs);
719 				}
720 			}
721 	}
722 }
723 
724 
725 
726 LOCAL prunetrees()
727 
728 /* The only optcse.c routine that does any real work: go through the available
729 ** computations stack and eliminate redundant subtrees.
730 */
731 
732 {
733 Addrp tempv;
734 register duplptr dl;
735 register valuen p;
736 expptr t;
737 int is_addrnode;
738 expptr *addr_tree1 = NULL ;
739 expptr tree2 = NULL ;
740 
741 for(p=current_BB->headnode;p;p=p->next)
742 {
743 	if(p->rs == NULL) {
744 		if( addr_tree1 && tree2 )
745 		     *addr_tree1 = fixtype(mkexpr(OPCOMMA,tree2,*addr_tree1));
746 		addr_tree1 = (expptr*) p->opp;
747 		tree2 = NULL;
748 	}
749 	if (p->n_dups ) {
750 
751 		if (p->opp->tag == TTEMP)
752 			fprintf(diagfile,"TTEMP in prunetrees - cbb\n");
753 		if(p->opp->tag == TADDR) is_addrnode = TRUE;
754 		else is_addrnode = FALSE;
755 
756 		if (is_addrnode)
757 			tempv = mktemp(TYADDR,NULL);
758 		else
759 			tempv = mktemp(p->opp->exprblock.vtype,
760 			    p->opp->exprblock.vleng);
761 		cse2count++;
762 
763 		if(tree2)
764 			tree2 = fixtype(mkexpr(OPCOMMA,tree2,
765 				fixtype(mkexpr(OPASSIGN,cpexpr(tempv),
766 				(is_addrnode ? addrof(p->opp) :  p->opp)
767 				))));
768 		else
769 			tree2 = fixtype(mkexpr(OPASSIGN,cpexpr(tempv),
770 				(is_addrnode ? addrof(p->opp) :  p->opp)
771 				));
772 
773 		if(is_addrnode)
774 			*(p->parent) = fixtype(mkexpr(OPINDIRECT,cpexpr(tempv), NULL));
775 		else
776 			*(p->parent) = (expptr) cpexpr(tempv);
777 
778 /* then replaces all future instances of the calculation by references to
779    the temporary */
780 
781 		for(dl=p->headduplist;dl->next;dl=dl->next) {
782 			cse1count++;
783 			frexpr(*dl->parent);
784 			if(is_addrnode)
785 				*(dl->parent) = fixtype(
786 					mkexpr(OPINDIRECT,cpexpr(tempv), NULL));
787 			else
788 				*(dl->parent) = (expptr) cpexpr(tempv);
789 		}
790 
791 /* the last reference does not use a copy since the temporary can
792    now be freed */
793 
794 		cse1count++;
795 		frexpr(*dl->parent);
796 		if(is_addrnode)
797 			*(dl->parent) = fixtype(mkexpr(OPINDIRECT,tempv, NULL));
798 		else
799 			*(dl->parent) = (expptr) tempv;
800 
801 		frtemp (tempv);
802 	}
803 }
804 if(addr_tree1 && tree2)
805 	*addr_tree1 = fixtype(mkexpr(OPCOMMA,tree2,*addr_tree1));
806 }
807 
808 
809 
810 LOCAL rewritebb (bb)
811 Bblockp bb;
812 {
813 	Slotp sp;
814 	expptr p;
815 
816 	if (bb == NULL)
817 		return;
818 	else
819 		current_BB = bb;
820 	sp = current_BB->first;
821 
822 	/* loop trough all BB slots and scan candidate expr trees when found */
823 
824 	for (sp = current_BB->first; ; sp = sp->next)
825 		{
826 		switch (sp->type)
827 		    {
828 		    case SKEQ :
829 		    case SKIFN :
830 		    case SKCMGOTO :
831 		    case SKCALL :
832 			newnode((expptr) &sp->expr,NULL,NULL,NULL);
833 			scantree(&sp->expr);
834 			break;
835 
836 		    default  :
837 			break;
838 		    }
839 		if (sp == current_BB->last) break;
840 		}
841 
842 /* use the information built up by scantree to prune reduntant subtrees */
843 	prunetrees();
844 
845 	current_BB = NULL;
846 }
847 
848 
849 
850 /*
851  *  removes all instances of OPCOMMA from the given subexpression of
852  *  the given buffer slot
853  */
854 
855 expptr rmcommaop (p,sl)
856 expptr	p;
857 Slotp	sl;
858 
859 {
860 expptr	leftp,rightp;
861 chainp	cp;
862 
863 if (!p)
864 	return (ENULL);
865 switch (p->tag)
866 	{
867 	case TEXPR:
868 		leftp = p->exprblock.leftp;
869 		rightp = p->exprblock.rightp;
870 		leftp = rmcommaop (leftp,sl);
871 		if (p->exprblock.opcode == OPCOMMA)
872 			{
873 			optinsert (SKEQ,leftp,0,0,sl);
874 			if (p->exprblock.vleng)
875 				free ((charptr) p->exprblock.vleng);
876 			free ((charptr) p);
877 			p = rmcommaop (rightp,sl);
878 			return (p);
879 			}
880 		p->exprblock.leftp = leftp;
881 		p->exprblock.rightp = rmcommaop (rightp,sl);
882 		return (p);
883 
884 	case TLIST:
885 		for (cp = p->listblock.listp; cp; cp = cp->nextp)
886 			cp->datap = (tagptr) rmcommaop (cp->datap,sl);
887 		return (p);
888 
889 	case TADDR:
890 		p->addrblock.memoffset = rmcommaop (p->addrblock.memoffset,sl);
891 		return (p);
892 
893 	default:
894 		return (p);
895 	}
896 }
897 
898 
899 
900 /*
901  *  scans the code buffer, performing common subexpression elimination
902  */
903 
904 optcse ()
905 
906 {
907 Slotp	sl;
908 Bblockp	bb;
909 
910 if (debugflag[13])
911 	return;
912 
913 cse1count = 0;
914 cse2count = 0;
915 for (sl = firstslot; sl; sl = sl->next)
916 	sl->expr = rmcommaop (sl->expr,sl);
917 for (bb = firstblock; bb; bb = bb->next)
918 	rewritebb (bb);
919 
920 if (debugflag[0])
921 	fprintf (diagfile,
922 		"%d common subexpression use%s eliminated (%d definition%s)\n",
923 		cse1count, (cse1count==1 ? "" : "s"),
924 		cse2count, (cse2count==1 ? "" : "s"));
925 }
926