Commit | Line | Data |
---|---|---|
ba350979 KB |
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,¤t_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 | } |