1: // Copyright (C) 1986-1998 by Symantec
2: // Copyright (C) 2000-2011 by Digital Mars
3: // All Rights Reserved
4: // http://www.digitalmars.com
5: // Written by Walter Bright
6: /*
7: * This source file is made available for personal use
8: * only. The license is in /dmd/src/dmd/backendlicense.txt
9: * or /dm/src/dmd/backendlicense.txt
10: * For any other uses, please contact Digital Mars.
11: */
12:
13: #if (SCPP || MARS) && !HTOD
14:
15: #include <stdio.h>
16: #include <time.h>
17:
18: #include "cc.h"
19: #include "global.h"
20: #include "el.h"
21: #include "go.h"
22: #include "oper.h"
23: #include "list.h"
24: #include "type.h"
25:
26: #if SCPP
27: #include "parser.h"
28: #endif
29:
30: static char __file__[] = __FILE__; /* for tassert.h */
31: #include "tassert.h"
32:
33: extern void error(const char *filename, unsigned linnum, const char *format, ...);
34:
35: STATIC void rd_free_elem(elem *e);
36: STATIC void rd_compute();
37: STATIC void conpropwalk(elem *n , vec_t IN);
38: STATIC void chkrd(elem *n , list_t rdlist);
39: STATIC elem * chkprop(elem *n , list_t rdlist);
40: STATIC void arrayboundsrds(void);
41: STATIC void eqeqranges(void);
42: STATIC void intranges(void);
43: STATIC int loopcheck(block *start , block *inc , block *rel);
44: STATIC void cpwalk(elem *n , vec_t IN);
45: STATIC unsigned numasg(elem *e);
46: STATIC void accumda(elem *n , vec_t DEAD , vec_t POSS);
47: STATIC void dvwalk(elem *n , unsigned i);
48: STATIC int killed(unsigned j , block *bp , block *b);
49: STATIC int ispath(unsigned j , block *bp , block *b);
50:
51: /**********************************************************************/
52:
53: // Lists to help identify ranges of variables
54: struct Elemdata
55: { Elemdata *next; // linked list
56: elem *pelem; // the elem in question
57: block *pblock; // which block it's in
58: list_t rdlist; // list of definition elems for *pelem
59:
60: static Elemdata *ctor(elem *e,block *b,list_t rd);
61: };
62:
63: Elemdata *Elemdata::ctor(elem *e,block *b,list_t rd)
64: { Elemdata *ed;
65:
66: ed = (Elemdata *) MEM_BEF_CALLOC(sizeof(Elemdata));
67: ed->pelem = e;
68: ed->pblock = b;
69: ed->rdlist = rd;
70: return ed;
71: }
72:
73:
74: /*****************
75: * Free list of Elemdata's.
76: */
77:
78: STATIC void elemdatafree(Elemdata **plist)
79: { Elemdata *el;
80: Elemdata *eln;
81:
82: for (el = *plist; el; el = eln)
83: { eln = el->next;
84: list_free(&el->rdlist);
85: MEM_BEF_FREE(el);
86: }
87: *plist = NULL;
88: }
89:
90: static Elemdata *arraylist = NULL; // list of Elemdata's of OParray elems
91: static Elemdata *eqeqlist = NULL; // list of Elemdata's of OPeqeq & OPne elems
92: static Elemdata *rellist = NULL; // list of Elemdata's of relop elems
93: static Elemdata *inclist = NULL; // list of Elemdata's of increment elems
94:
95: enum Rdtype { RDarraybounds, RDconstprop };
96: static Rdtype rdtype;
97:
98: /*************************** Constant Propagation ***************************/
99:
100:
101: /**************************
102: * Constant propagation.
103: * Also detects use of variable before any possible def.
104: */
105:
106: void constprop()
107: {
108: rdtype = RDconstprop;
109: rd_compute();
110: intranges(); // compute integer ranges
111: #if 0
112: eqeqranges(); // see if we can eliminate some relationals
113: #endif
114: elemdatafree(&eqeqlist);
115: elemdatafree(&rellist);
116: elemdatafree(&inclist);
117: }
118:
119: /************************************
120: * Compute reaching definitions.
121: * Note: RD vectors are destroyed by this.
122: */
123:
124: static block *thisblock;
125:
126: STATIC void rd_compute()
127: { register unsigned i;
128:
129: cmes("constprop()\n");
130: assert(dfo);
131: flowrd(); /* compute reaching definitions (rd) */
132: if (deftop == 0) /* if no reaching defs */
133: return;
134: #if TX86
135: assert(rellist == NULL && inclist == NULL && eqeqlist == NULL && arraylist == NULL);
136: #else
137: rellist = inclist = eqeqlist = arraylist = NULL;
138: #endif
139: block_clearvisit();
140: for (i = 0; i < dfotop; i++) /* for each block */
141: { block *b = dfo[i];
142:
143: switch (b->BC)
144: {
145: #if MARS
146: case BCjcatch:
147: #endif
148: case BC_finally:
149: case BCasm:
150: case BCcatch:
151: block_visit(b);
152: break;
153: }
154: }
155:
156: for (i = 0; i < dfotop; i++) /* for each block */
157: { register block *b;
158:
159: b = dfo[i];
160: thisblock = b;
161: #if 0
162: dbg_printf("block %d Bin ",i); vec_println(b->Binrd);
163: dbg_printf(" Bout "); vec_println(b->Boutrd);
164: #endif
165: if (b->Bflags & BFLvisited)
166: continue; // not reliable for this block
167: if (b->Belem)
168: {
169: conpropwalk(b->Belem,b->Binrd);
170: #ifdef DEBUG
171: if (!(vec_equal(b->Binrd,b->Boutrd)))
172: { int j;
173:
174: dbg_printf("block %d Binrd ",i); vec_println(b->Binrd);
175: dbg_printf(" Boutrd "); vec_println(b->Boutrd);
176: WReqn(b->Belem);
177: dbg_printf("\n");
178: vec_xorass(b->Binrd,b->Boutrd);
179: j = vec_index(0,b->Binrd);
180: WReqn(defnod[j].DNelem);
181: dbg_printf("\n");
182: }
183: #endif
184: assert(vec_equal(b->Binrd,b->Boutrd));
185: }
186: }
187: }
188:
189: /***************************
190: * Support routine for constprop().
191: * Visit each elem in order
192: * If elem is a reference to a variable, and
193: * all the reaching defs of that variable are
194: * defining it to be a specific constant,
195: * Replace reference with that constant.
196: * Generate warning if no reaching defs for a
197: * variable, and the variable is on the stack
198: * or in a register.
199: * If elem is an assignment or function call or OPasm
200: * Modify vector of reaching defs.
201: */
202:
203: STATIC void conpropwalk(elem *n,vec_t IN)
204: { register unsigned op;
205: Elemdata *pdata;
206: vec_t L,R;
207: elem *t;
208:
209: assert(n && IN);
210: /*chkvecdim(deftop,0);*/
211: //printf("conpropwalk()\n"),elem_print(n);
212: op = n->Eoper;
213: if (op == OPcolon || op == OPcolon2)
214: { L = vec_clone(IN);
215: conpropwalk(n->E1,L);
216: conpropwalk(n->E2,IN);
217: vec_orass(IN,L); /* IN = L | R */
218: vec_free(L);
219: }
220: else if (op == OPandand || op == OPoror)
221: { conpropwalk(n->E1,IN);
222: R = vec_clone(IN);
223: conpropwalk(n->E2,R);
224: vec_orass(IN,R); /* IN |= R */
225: vec_free(R);
226: }
227: else if (OTunary(op))
228: goto L3;
229: else if (ERTOL(n))
230: { conpropwalk(n->E2,IN);
231: L3:
232: t = n->E1;
233: if (OTassign(op))
234: {
235: if (t->Eoper == OPvar)
236: {
237: // Note that the following ignores OPnegass
238: if (rdtype == RDconstprop &&
239: OTopeq(op) && sytab[t->EV.sp.Vsym->Sclass] & SCRD)
240: { elem *e;
241: list_t rdl;
242:
243: rdl = listrds(IN,t,NULL);
244: if (!(config.flags & CFGnowarning)) // if warnings are enabled
245: chkrd(t,rdl);
246: e = chkprop(t,rdl);
247: if (e)
248: { // Replace (t op= exp) with (t = e op exp)
249:
250: e = el_copytree(e);
251: e->Ety = t->Ety;
252: n->E2 = el_bin(opeqtoop(op),n->Ety,e,n->E2);
253: n->Eoper = OPeq;
254: }
255: list_free(&rdl);
256: }
257: }
258: else
259: conpropwalk(t,IN);
260: }
261: else
262: conpropwalk(t,IN);
263: }
264: else if (OTbinary(op))
265: {
266: if (OTassign(op))
267: { t = Elvalue(n);
268: if (t->Eoper != OPvar)
269: conpropwalk(t,IN);
270: }
271: else
272: conpropwalk(n->E1,IN);
273: conpropwalk(n->E2,IN);
274: }
275:
276: // Collect data for subsequent optimizations
277: if (OTbinary(op) && n->E1->Eoper == OPvar && n->E2->Eoper == OPconst)
278: {
279: switch (op)
280: {
281: case OPlt:
282: case OPgt:
283: case OPle:
284: case OPge:
285: // Collect compare elems and their rd's in the rellist list
286: if (rdtype == RDconstprop &&
287: tyintegral(n->E1->Ety) &&
288: tyintegral(n->E2->Ety)
289: )
290: {
291: //dbg_printf("appending to rellist\n"); elem_print(n);
292: pdata = Elemdata::ctor(n,thisblock,listrds(IN,n->E1,NULL));
293: pdata->next = rellist;
294: rellist = pdata;
295: }
296: break;
297:
298: case OPaddass:
299: case OPminass:
300: case OPpostinc:
301: case OPpostdec:
302: // Collect increment elems and their rd's in the inclist list
303: if (rdtype == RDconstprop &&
304: tyintegral(n->E1->Ety))
305: {
306: //dbg_printf("appending to inclist\n"); elem_print(n);
307: pdata = Elemdata::ctor(n,thisblock,listrds(IN,n->E1,NULL));
308: pdata->next = inclist;
309: inclist = pdata;
310: }
311: break;
312:
313: case OPne:
314: case OPeqeq:
315: // Collect compare elems and their rd's in the rellist list
316: if (rdtype == RDconstprop &&
317: tyintegral(n->E1->Ety))
318: { //dbg_printf("appending to eqeqlist\n"); elem_print(n);
319: pdata = Elemdata::ctor(n,thisblock,listrds(IN,n->E1,NULL));
320: pdata->next = eqeqlist;
321: eqeqlist = pdata;
322: }
323: break;
324: }
325: }
326:
327:
328: if (OTdef(op)) /* if definition elem */
329: updaterd(n,IN,NULL); /* then update IN vector */
330:
331: /* now we get to the part that checks to see if we can */
332: /* propagate a constant. */
333: if (op == OPvar && sytab[n->EV.sp.Vsym->Sclass] & SCRD)
334: { list_t rdl;
335:
336: //printf("const prop: %s\n", n->EV.sp.Vsym->Sident);
337: rdl = listrds(IN,n,NULL);
338: if (rdtype == RDconstprop)
339: { elem *e;
340:
341: if (!(config.flags & CFGnowarning)) // if warnings are enabled
342: chkrd(n,rdl);
343: e = chkprop(n,rdl);
344: if (e)
345: { tym_t nty;
346:
347: nty = n->Ety;
348: el_copy(n,e);
349: n->Ety = nty; // retain original type
350: }
351: list_free(&rdl);
352: }
353: }
354: }
355:
356: /******************************
357: * Give error if there are no reaching defs for variable v.
358: */
359:
360: STATIC void chkrd(elem *n,list_t rdlist)
361: { unsigned i;
362: symbol *sv;
363: int unambig;
364:
365: sv = n->EV.sp.Vsym;
366: assert(sytab[sv->Sclass] & SCRD);
367: if (sv->Sflags & SFLnord) // if already printed a warning
368: return;
369: #if TX86
370: if (sv->ty() & mTYvolatile)
371: return;
372: #endif
373: unambig = sv->Sflags & SFLunambig;
374: for (list_t l = rdlist; l; l = list_next(l))
375: { elem *d = (elem *) list_ptr(l);
376:
377: elem_debug(d);
378: if (d->Eoper == OPasm) /* OPasm elems ruin everything */
379: return;
380: if (OTassign(d->Eoper))
381: {
382: if (d->E1->Eoper == OPvar)
383: { if (d->E1->EV.sp.Vsym == sv)
384: return;
385: }
386: else if (!unambig)
387: return;
388: }
389: else
390: { if (!unambig)
391: return;
392: }
393: }
394:
395: // If there are any asm blocks, don't print the message
396: for (i = 0; i < dfotop; i++)
397: if (dfo[i]->BC == BCasm)
398: return;
399:
400: // If variable contains bit fields, don't print message (because if
401: // bit field is the first set, then we get a spurious warning).
402: // STL uses 0 sized structs to transmit type information, so
403: // don't complain about them being used before set.
404: if (type_struct(sv->Stype))
405: {
406: if (sv->Stype->Ttag->Sstruct->Sflags & (STRbitfields | STR0size))
407: return;
408: }
409: #if SCPP
410: { Outbuffer buf;
411: char *p2;
412:
413: type_tostring(&buf, sv->Stype);
414: buf.writeByte(' ');
415: buf.write(sv->Sident);
416: p2 = buf.toString();
417: warerr(WM_used_b4_set, p2); // variable used before set
418: }
419: #endif
420: #if 1 && MARS
421: /* Watch out for:
422: void test()
423: {
424: void[0] x;
425: auto y = x;
426: }
427: */
428: error(n->Esrcpos.Sfilename, n->Esrcpos.Slinnum, "variable %s used before set", sv->Sident);
429: #endif
430:
431: sv->Sflags |= SFLnord; // no redundant messages
432: #ifdef DEBUG
433: //elem_print(n);
434: #endif
435: }
436:
437: /**********************************
438: * Look through the vector of reaching defs (IN) to see
439: * if all defs of n are of the same constant. If so, replace
440: * n with that constant.
441: * Bit fields are gross, so don't propagate anything with assignments
442: * to a bit field.
443: * Note the flaw in the reaching def vector. There is currently no way
444: * to detect RDs from when the function is invoked, i.e. RDs for parameters,
445: * statics and globals. This could be fixed by adding dummy defs for
446: * them before startblock, but we just kludge it and don't propagate
447: * stuff for them.
448: * Returns:
449: * NULL do not propagate constant
450: * e constant elem that we should replace n with
451: */
452:
453: STATIC elem * chkprop(elem *n,list_t rdlist)
454: {
455: elem *foundelem = NULL;
456: int unambig;
457: symbol *sv;
458: tym_t nty;
459: unsigned nsize;
460: targ_size_t noff;
461: list_t l;
462:
463: //printf("checkprop: "); WReqn(n); printf("\n");
464: assert(n && n->Eoper == OPvar);
465: elem_debug(n);
466: sv = n->EV.sp.Vsym;
467: assert(sytab[sv->Sclass] & SCRD);
468: nty = n->Ety;
469: if (!tyscalar(nty))
470: goto noprop;
471: nsize = size(nty);
472: noff = n->EV.sp.Voffset;
473: unambig = sv->Sflags & SFLunambig;
474: for (l = rdlist; l; l = list_next(l))
475: { elem *d = (elem *) list_ptr(l);
476:
477: elem_debug(d);
478:
479: //printf("\trd: "); WReqn(d); printf("\n");
480: if (d->Eoper == OPasm) /* OPasm elems ruin everything */
481: goto noprop;
482: #if 0
483: // Runs afoul of Buzilla 4506
484: if (OTassign(d->Eoper) && EBIN(d)) // if assignment elem
485: #else
486: if (OTassign(d->Eoper)) // if assignment elem
487: #endif
488: { elem *t = Elvalue(d);
489:
490: if (t->Eoper == OPvar)
491: { assert(t->EV.sp.Vsym == sv);
492:
493: if (d->Eoper == OPstreq ||
494: !tyscalar(t->Ety))
495: goto noprop; // not worth bothering with these cases
496:
497: if (d->Eoper == OPnegass)
498: goto noprop; // don't bother with this case, either
499:
500: /* Everything must match or we must skip this variable */
501: /* (in case of assigning to overlapping unions, etc.) */
502: if (t->EV.sp.Voffset != noff ||
503: /* If sizes match, we are ok */
504: size(t->Ety) != nsize &&
505: !(d->E2->Eoper == OPconst && size(t->Ety) > nsize && !tyfloating(d->E2->Ety)))
506: goto noprop;
507: }
508: else
509: { if (unambig) /* unambiguous assignments only */
510: continue;
511: goto noprop;
512: }
513: if (d->Eoper != OPeq)
514: goto noprop;
515: }
516: else /* must be a call elem */
517: {
518: if (unambig)
519: continue;
520: else
521: goto noprop; /* could be affected */
522: }
523:
524: if (d->E2->Eoper == OPconst || d->E2->Eoper == OPrelconst)
525: {
526: if (foundelem) /* already found one */
527: { /* then they must be the same */
528: if (!el_match(foundelem,d->E2))
529: goto noprop;
530: }
531: else /* else this is it */
532: foundelem = d->E2;
533: }
534: else
535: goto noprop;
536: }
537:
538: if (foundelem) /* if we got one */
539: { /* replace n with foundelem */
540: #ifdef DEBUG
541: if (debugc)
542: { dbg_printf("const prop (");
543: WReqn(n);
544: dbg_printf(" replaced by ");
545: WReqn(foundelem);
546: dbg_printf("), %p to %p\n",foundelem,n);
547: }
548: #endif
549: changes++;
550: return foundelem;
551: }
552: noprop:
553: return NULL;
554: }
555:
556: /***********************************
557: * Find all the reaching defs of OPvar e.
558: * Put into a linked list, or just set the RD bits in a vector.
559: *
560: */
561:
562: list_t listrds(vec_t IN,elem *e,vec_t f)
563: { list_t rdlist;
564: unsigned i;
565: unsigned unambig;
566: Symbol *s;
567: unsigned nsize;
568: targ_size_t noff;
569: tym_t ty;
570:
571: //printf("listrds: "); WReqn(e); printf("\n");
572: assert(IN);
573: rdlist = NULL;
574: assert(e->Eoper == OPvar);
575: s = e->EV.sp.Vsym;
576: ty = e->Ety;
577: if (tyscalar(ty))
578: nsize = size(ty);
579: noff = e->EV.sp.Voffset;
580: unambig = s->Sflags & SFLunambig;
581: if (f)
582: vec_clear(f);
583: foreach (i, deftop, IN)
584: { elem *d;
585: unsigned op;
586:
587: d = defnod[i].DNelem;
588: //dbg_printf("\tlooking at "); WReqn(d); dbg_printf("\n");
589: op = d->Eoper;
590: if (op == OPasm) // assume ASM elems define everything
591: goto listit;
592: if (OTassign(op))
593: { elem *t = Elvalue(d);
594:
595: if (t->Eoper == OPvar && t->EV.sp.Vsym == s)
596: { if (op == OPstreq)
597: goto listit;
598: if (!tyscalar(ty) || !tyscalar(t->Ety))
599: goto listit;
600: // If t does not overlap e, then it doesn't affect things
601: if (noff + nsize > t->EV.sp.Voffset &&
602: t->EV.sp.Voffset + size(t->Ety) > noff)
603: goto listit; // it's an assignment to s
604: }
605: else if (t->Eoper != OPvar && !unambig)
606: goto listit; /* assignment through pointer */
607: }
608: else if (!unambig)
609: goto listit; /* probably a function call */
610: continue;
611:
612: listit:
613: //dbg_printf("\tlisting "); WReqn(d); dbg_printf("\n");
614: if (f)
615: vec_setbit(i,f);
616: else
617: list_append(&rdlist,d); // add the definition node
618: }
619: return rdlist;
620: }
621:
622: /********************************************
623: * Look at reaching defs for expressions of the form (v == c) and (v != c).
624: * If all definitions of v are c or are not c, then we can replace the
625: * expression with 1 or 0.
626: */
627:
628: STATIC void eqeqranges()
629: { Elemdata *rel;
630: list_t rdl;
631: Symbol *v;
632: int sz;
633: elem *e;
634: targ_llong c;
635: int result;
636:
637: for (rel = eqeqlist; rel; rel = rel->next)
638: {
639: e = rel->pelem;
640: v = e->E1->EV.sp.Vsym;
641: if (!(sytab[v->Sclass] & SCRD))
642: continue;
643: sz = tysize(e->E1->Ety);
644: c = el_tolong(e->E2);
645:
646: result = -1; // result not known yet
647: for (rdl = rel->rdlist; rdl; rdl = list_next(rdl))
648: { elem *erd = (elem *) list_ptr(rdl);
649: elem *erd1;
650: int szrd;
651: int tmp;
652:
653: elem_debug(erd);
654: if (erd->Eoper != OPeq ||
655: (erd1 = erd->E1)->Eoper != OPvar ||
656: erd->E2->Eoper != OPconst
657: )
658: goto L1;
659: szrd = tysize(erd1->Ety);
660: if (erd1->EV.sp.Voffset + szrd <= e->E1->EV.sp.Voffset ||
661: e->E1->EV.sp.Voffset + sz <= erd1->EV.sp.Voffset)
662: continue; // doesn't affect us, skip it
663: if (szrd != sz || e->E1->EV.sp.Voffset != erd1->EV.sp.Voffset)
664: goto L1; // overlapping - forget it
665:
666: tmp = (c == el_tolong(erd->E2));
667: if (result == -1)
668: result = tmp;
669: else if (result != tmp)
670: goto L1;
671: }
672: if (result >= 0)
673: {
674: //printf("replacing with %d\n",result);
675: el_free(e->E1);
676: el_free(e->E2);
677: e->EV.Vint = (e->Eoper == OPeqeq) ? result : result ^ 1;
678: e->Eoper = OPconst;
679: }
680: L1: ;
681: }
682: }
683:
684: /******************************
685: * Examine rellist and inclist to determine if any of the signed compare
686: * elems in rellist can be replace by unsigned compares.
687: * rellist is list of relationals in function.
688: * inclist is list of increment elems in function.
689: */
690:
691: STATIC void intranges()
692: { Elemdata *rel,*iel;
693: block *rb,*ib;
694: symbol *v;
695: elem *rdeq,*rdinc;
696: unsigned incop,relatop;
697: targ_int initial,increment,final;
698:
699: cmes("intranges()\n");
700: for (rel = rellist; rel; rel = rel->next)
701: {
702: rb = rel->pblock;
703: //dbg_printf("rel->pelem: "); WReqn(rel->pelem); dbg_printf("\n");
704: assert(rel->pelem->E1->Eoper == OPvar);
705: v = rel->pelem->E1->EV.sp.Vsym;
706:
707: // RD info is only reliable for registers and autos
708: if (!(sytab[v->Sclass] & SCRD))
709: continue;
710:
711: /* Look for two rd's: an = and an increment */
712: if (list_nitems(rel->rdlist) != 2)
713: continue;
714: rdeq = list_elem(list_next(rel->rdlist));
715: if (rdeq->Eoper != OPeq)
716: { rdinc = rdeq;
717: rdeq = list_elem(rel->rdlist);
718: if (rdeq->Eoper != OPeq)
719: continue;
720: }
721: else
722: rdinc = list_elem(rel->rdlist);
723: #if 0
724: printf("\neq: "); WReqn(rdeq); printf("\n");
725: printf("rel: "); WReqn(rel->pelem); printf("\n");
726: printf("inc: "); WReqn(rdinc); printf("\n");
727: #endif
728: incop = rdinc->Eoper;
729: if (!OTpost(incop) && incop != OPaddass && incop != OPminass)
730: continue;
731:
732: /* lvalues should be unambiguous defs */
733: if (rdeq->E1->Eoper != OPvar || rdinc->E1->Eoper != OPvar)
734: continue;
735: /* rvalues should be constants */
736: if (rdeq->E2->Eoper != OPconst || rdinc->E2->Eoper != OPconst)
737: continue;
738:
739: /* Ensure that the only defs reaching the increment elem (rdinc) */
740: /* are rdeq and rdinc. */
741: for (iel = inclist; TRUE; iel = iel->next)
742: { elem *rd1,*rd2;
743:
744: if (!iel)
745: goto nextrel;
746: ib = iel->pblock;
747: if (iel->pelem != rdinc)
748: continue; /* not our increment elem */
749: if (list_nitems(iel->rdlist) != 2)
750: { //printf("!= 2\n");
751: goto nextrel;
752: }
753: rd1 = list_elem(iel->rdlist);
754: rd2 = list_elem(list_next(iel->rdlist));
755: /* The rd's for the relational elem (rdeq,rdinc) must be */
756: /* the same as the rd's for tne increment elem (rd1,rd2). */
757: if (rd1 == rdeq && rd2 == rdinc || rd1 == rdinc && rd2 == rdeq)
758: break;
759: }
760:
761: // Check that all paths from rdinc to rdinc must pass through rdrel
762: { int i;
763:
764: // ib: block of increment
765: // rb: block of relational
766: i = loopcheck(ib,ib,rb);
767: block_clearvisit();
768: if (i)
769: continue;
770: }
771:
772: /* Gather initial, increment, and final values for loop */
773: initial = el_tolong(rdeq->E2);
warning C4244: '=' : conversion from 'targ_llong' to 'targ_int', possible loss of data
774: increment = el_tolong(rdinc->E2);
warning C4244: '=' : conversion from 'targ_llong' to 'targ_int', possible loss of data
775: if (incop == OPpostdec || incop == OPminass)
776: increment = -increment;
777: relatop = rel->pelem->Eoper;
778: final = el_tolong(rel->pelem->E2);
warning C4244: '=' : conversion from 'targ_llong' to 'targ_int', possible loss of data
779: // dbg_printf("initial = %d, increment = %d, final = %d\n",
780: // initial,increment,final);
781:
782: /* Determine if we can make the relational an unsigned */
783: if (initial >= 0)
784: { if (final >= initial)
785: { if (increment > 0 && ((final - initial) % increment) == 0)
786: goto makeuns;
787: }
788: else if (final >= 0)
789: { /* 0 <= final < initial */
790: if (increment < 0 && ((final - initial) % increment) == 0 &&
791: !(final + increment < 0 &&
792: (relatop == OPge || relatop == OPlt)
793: )
794: )
795: {
796: makeuns:
797: if (!tyuns(rel->pelem->E2->Ety))
798: {
799: rel->pelem->E2->Ety = touns(rel->pelem->E2->Ety);
800: rel->pelem->Nflags |= NFLtouns;
801: #ifdef DEBUG
802: if (debugc)
803: { WReqn(rel->pelem);
804: dbg_printf(" made unsigned, initial = %ld, increment = %ld,\
805: final = %ld\n",initial,increment,final);
806: }
807: #endif
808: changes++;
809: }
810: #if 0
811: // Eliminate loop if it is empty
812: if (relatop == OPlt &&
813: rb->BC == BCiftrue &&
814: list_block(rb->Bsucc) == rb &&
815: rb->Belem->Eoper == OPcomma &&
816: rb->Belem->E1 == rdinc &&
817: rb->Belem->E2 == rel->pelem
818: )
819: {
820: rel->pelem->Eoper = OPeq;
821: rel->pelem->Ety = rel->pelem->E1->Ety;
822: rb->BC = BCgoto;
823: list_subtract(&rb->Bsucc,rb);
824: list_subtract(&rb->Bpred,rb);
825: #ifdef DEBUG
826: if (debugc)
827: { WReqn(rel->pelem);
828: dbg_printf(" eliminated loop\n");
829: }
830: #endif
831: changes++;
832: }
833: #endif
834: }
835: }
836: }
837:
838: nextrel:
839: ;
840: }
841: }
842:
843: /***********************
844: * Return TRUE if there is a path from start to inc without
845: * passing through rel.
846: */
847:
848: STATIC int loopcheck(block *start,block *inc,block *rel)
849: { list_t list;
850: block *b;
851:
852: #if __ZTC__
853: _chkstack(); /* always check stack on recursive routines */
854: #endif
855: if (!(start->Bflags & BFLvisited))
856: { start->Bflags |= BFLvisited; /* guarantee eventual termination */
857: for (list = start->Bsucc; list; list = list_next(list))
858: { b = (block *) list_ptr(list);
859: if (b != rel && (b == inc || loopcheck(b,inc,rel)))
860: return TRUE;
861: }
862: }
863: return FALSE;
864: }
865:
866: /****************************
867: * Do copy propagation.
868: * Copy propagation elems are of the form OPvar=OPvar, and they are
869: * in expnod[].
870: */
871:
872: static int recalc;
873:
874: void copyprop()
875: { register unsigned i;
876:
877: out_regcand(&globsym);
878: cmes("copyprop()\n");
879: assert(dfo);
880: Lagain:
881: flowcp(); /* compute available copy statements */
882: if (exptop <= 1)
883: return; /* none available */
884: #if 0
885: for (i = 1; i < exptop; i++)
886: { dbg_printf("expnod[%d] = (",i);
887: WReqn(expnod[i]);
888: dbg_printf(");\n");
889: }
890: #endif
891: recalc = 0;
892: for (i = 0; i < dfotop; i++) /* for each block */
893: { register block *b;
894:
895: b = dfo[i];
896: if (b->Belem)
897: {
898: #if 0
899: dbg_printf("B%d, elem (",i);
900: WReqn(b->Belem); dbg_printf(")\nBin ");
901: vec_println(b->Bin);
902: cpwalk(b->Belem,b->Bin);
903: dbg_printf("Bino ");
904: vec_println(b->Bin);
905: dbg_printf("Bout ");
906: vec_println(b->Bout);
907: #else
908: cpwalk(b->Belem,b->Bin);
909: #endif
910: /*assert(vec_equal(b->Bin,b->Bout)); */
911: /* The previous assert() is correct except */
912: /* for the following case: */
913: /* a=b; d=a; a=b; */
914: /* The vectors don't match because the */
915: /* equations changed to: */
916: /* a=b; d=b; a=b; */
917: /* and the d=b copy elem now reaches the end */
918: /* of the block (the d=a elem didn't). */
919: }
920: if (recalc)
921: goto Lagain;
922: }
923: }
924:
925: /*****************************
926: * Walk tree n, doing copy propagation as we go.
927: * Keep IN up to date.
928: */
929:
930: STATIC void cpwalk(register elem *n,vec_t IN)
931: { register unsigned op,i;
932: register elem *t;
933: vec_t L;
934:
935: static int nocp;
936:
937: assert(n && IN);
938: /*chkvecdim(exptop,0);*/
939: if (recalc)
940: return;
941: op = n->Eoper;
942: if (op == OPcolon || op == OPcolon2)
943: {
944: L = vec_clone(IN);
945: cpwalk(n->E1,L);
946: cpwalk(n->E2,IN);
947: vec_andass(IN,L); // IN = L & R
948: vec_free(L);
949: }
950: else if (op == OPandand || op == OPoror)
951: { cpwalk(n->E1,IN);
952: L = vec_clone(IN);
953: cpwalk(n->E2,L);
954: vec_andass(IN,L); // IN = L & R
955: vec_free(L);
956: }
957: else if (OTunary(op))
958: {
959: t = n->E1;
960: if (OTassign(op))
961: { if (t->Eoper == OPind)
962: cpwalk(t->E1,IN);
963: }
964: else if (op == OPctor || op == OPdtor)
965: {
966: /* This kludge is necessary because in except_pop()
967: * an el_match is done on the lvalue. If copy propagation
968: * changes the OPctor but not the corresponding OPdtor,
969: * then the match won't happen and except_pop()
970: * will fail.
971: */
972: nocp++;
973: cpwalk(t,IN);
974: nocp--;
975: }
976: else
977: cpwalk(t,IN);
978: }
979: else if (OTassign(op))
980: { cpwalk(n->E2,IN);
981: t = Elvalue(n);
982: if (t->Eoper == OPind)
983: cpwalk(t,IN);
984: else
985: {
986: #ifdef DEBUG
987: if (t->Eoper != OPvar) elem_print(n);
988: #endif
989: assert(t->Eoper == OPvar);
990: }
991: }
992: else if (ERTOL(n))
993: { cpwalk(n->E2,IN);
994: cpwalk(n->E1,IN);
995: }
996: else if (OTbinary(op))
997: {
998: cpwalk(n->E1,IN);
999: cpwalk(n->E2,IN);
1000: }
1001:
1002: if (OTdef(op)) // if definition elem
1003: { int ambig; /* TRUE if ambiguous def */
1004:
1005: ambig = !OTassign(op) || t->Eoper == OPind;
1006: foreach (i,exptop,IN) /* for each active copy elem */
1007: { symbol *v;
1008:
1009: if (op == OPasm)
1010: goto clr;
1011:
1012: /* If this elem could kill the lvalue or the rvalue, */
1013: /* Clear bit in IN. */
1014: v = expnod[i]->E1->EV.sp.Vsym;
1015: if (ambig)
1016: { if (!(v->Sflags & SFLunambig))
1017: goto clr;
1018: }
1019: else
1020: { if (v == t->EV.sp.Vsym)
1021: goto clr;
1022: }
1023: v = expnod[i]->E2->EV.sp.Vsym;
1024: if (ambig)
1025: { if (!(v->Sflags & SFLunambig))
1026: goto clr;
1027: }
1028: else
1029: { if (v == t->EV.sp.Vsym)
1030: goto clr;
1031: }
1032: continue;
1033:
1034: clr: /* this copy elem is not available */
1035: vec_clearbit(i,IN); /* so remove it from the vector */
1036: } /* foreach */
1037:
1038: /* If this is a copy elem in expnod[] */
1039: /* Set bit in IN. */
1040: if (op == OPeq && n->E1->Eoper == OPvar &&
1041: n->E2->Eoper == OPvar && n->Eexp)
1042: vec_setbit(n->Eexp,IN);
1043: }
1044: else if (op == OPvar && !nocp) // if reference to variable v
1045: { symbol *v = n->EV.sp.Vsym;
1046: symbol *f;
1047: elem *foundelem = NULL;
1048: unsigned sz;
1049: tym_t ty;
1050:
1051: //dbg_printf("Checking copyprop for '%s', ty=x%x\n",v->Sident,n->Ety);
1052: symbol_debug(v);
1053: ty = n->Ety;
1054: sz = tysize(n->Ety);
1055: foreach(i,exptop,IN) /* for all active copy elems */
1056: { elem *c;
1057:
1058: c = expnod[i];
1059: assert(c);
1060:
1061: //dbg_printf("looking at: ("); WReqn(c); dbg_printf("), ty=x%x\n",c->E1->Ety);
1062: /* Not only must symbol numbers match, but */
1063: /* offsets too (in case of arrays) and sizes */
1064: /* (in case of unions). */
1065: if (v == c->E1->EV.sp.Vsym &&
1066: n->EV.sp.Voffset == c->E1->EV.sp.Voffset &&
1067: sz <= tysize(c->E1->Ety))
warning C4018: '<=' : signed/unsigned mismatch
1068: { if (foundelem)
1069: { if (c->E2->EV.sp.Vsym != f)
1070: goto noprop;
1071: }
1072: else
1073: { foundelem = c;
1074: f = foundelem->E2->EV.sp.Vsym;
1075: }
1076: }
1077: }
1078: if (foundelem) /* if we can do the copy prop */
1079: {
1080: cmes3("Copyprop, from '%s' to '%s'\n",
1081: (v->Sident) ? (char *)v->Sident : "temp",
1082: (f->Sident) ? (char *)f->Sident : "temp");
1083: el_copy(n,foundelem->E2);
1084: n->Ety = ty; // retain original type
1085: changes++;
1086:
1087: // Mark ones we can no longer use
1088: foreach(i,exptop,IN)
1089: {
1090: if (f == expnod[i]->E2->EV.sp.Vsym)
1091: { recalc++;
1092: break;
1093: }
1094: }
1095: }
1096: //else dbg_printf("not found\n");
1097: noprop:
1098: ;
1099: }
1100: }
1101:
1102: /********************************
1103: * Remove dead assignments. Those are assignments to a variable v
1104: * for which there are no subsequent uses of v.
1105: */
1106:
1107: static unsigned asstop, /* # of assignment elems in assnod[] */
1108: assmax = 0, /* size of assnod[] */
1109: assnum; /* current position in assnod[] */
1110: static elem **assnod = NULL; /* array of pointers to asg elems */
1111: static vec_t ambigref; /* vector of assignment elems that */
1112: /* are referenced when an ambiguous */
1113: /* reference is done (as in *p or call) */
1114:
1115: void rmdeadass()
1116: { register unsigned i,j;
1117: vec_t DEAD,POSS;
1118:
1119: cmes("rmdeadass()\n");
1120: flowlv(); /* compute live variables */
1121: for (i = 0; i < dfotop; i++) /* for each block b */
1122: { register block *b = dfo[i];
1123:
1124: if (!b->Belem) /* if no elems at all */
1125: continue;
1126: if (b->Btry) // if in try-block guarded body
1127: continue;
1128: asstop = numasg(b->Belem); /* # of assignment elems */
1129: if (asstop == 0) /* if no assignment elems */
1130: continue;
1131: if (asstop > assmax) /* if we need to reallocate */
1132: { assnod = (elem **)
1133: #if TX86
1134: util_realloc(assnod,sizeof(elem *),asstop);
1135: #else
1136: MEM_BEF_REALLOC(assnod,sizeof(elem *)*asstop);
1137: #endif
1138: assmax = asstop;
1139: }
1140: /*setvecdim(asstop);*/
1141: DEAD = vec_calloc(asstop);
1142: POSS = vec_calloc(asstop);
1143: ambigref = vec_calloc(asstop);
1144: assnum = 0;
1145: accumda(b->Belem,DEAD,POSS); /* compute DEAD and POSS */
1146: assert(assnum == asstop);
1147: vec_free(ambigref);
1148: vec_orass(POSS,DEAD); /* POSS |= DEAD */
1149: foreach (j,asstop,POSS) /* for each possible dead asg. */
1150: { symbol *v; /* v = target of assignment */
1151: register elem *n,*nv;
1152:
1153: n = assnod[j];
1154: nv = Elvalue(n);
1155: v = nv->EV.sp.Vsym;
1156: if (!symbol_isintab(v)) // not considered
1157: continue;
1158: //printf("assnod[%d]: ",j); WReqn(n); printf("\n");
1159: //printf("\tPOSS\n");
1160: /* If not positively dead but v is live on a */
1161: /* successor to b, then v is live. */
1162: //printf("\tDEAD=%d, live=%d\n",vec_testbit(j,DEAD),vec_testbit(v->Ssymnum,b->Boutlv));
1163: if (!vec_testbit(j,DEAD) && vec_testbit(v->Ssymnum,b->Boutlv))
1164: continue;
1165: /* volatile variables are not dead */
1166: if ((v->ty() | nv->Ety) & mTYvolatile)
1167: continue;
1168: #ifdef DEBUG
1169: if (debugc)
1170: { dbg_printf("dead assignment (");
1171: WReqn(n);
1172: if (vec_testbit(j,DEAD))
1173: dbg_printf(") DEAD\n");
1174: else
1175: dbg_printf(") Boutlv\n");
1176: }
1177: #endif
1178: elimass(n);
1179: changes++;
1180: } /* foreach */
1181: vec_free(DEAD);
1182: vec_free(POSS);
1183: } /* for */
1184: #if TX86
1185: util_free(assnod);
1186: #else
1187: MEM_BEF_FREE(assnod);
1188: #endif
1189: assnod = NULL;
1190: assmax = 0;
1191: }
1192:
1193: /***************************
1194: * Remove side effect of assignment elem.
1195: */
1196:
1197: void elimass(elem *n)
1198: { elem *e1;
1199:
1200: switch (n->Eoper)
1201: { case OPeq:
1202: case OPstreq:
1203: /* (V=e) => (random constant,e) */
1204: /* Watch out for (a=b=c) stuff! */
1205: /* Don't screw up assnod[]. */
1206: n->Eoper = OPcomma;
1207: n->Ety |= n->E2->Ety & (mTYconst | mTYvolatile | mTYimmutable | mTYshared
1208: #if !TARGET_FLAT
1209: | mTYfar
1210: #endif
1211: );
1212: n->E1->Eoper = OPconst;
1213: break;
1214: /* Convert (V op= e) to (V op e) */
1215: case OPaddass:
1216: case OPminass:
1217: case OPmulass:
1218: case OPdivass:
1219: case OPorass:
1220: case OPandass:
1221: case OPxorass:
1222: case OPmodass:
1223: case OPshlass:
1224: case OPshrass:
1225: case OPashrass:
1226: n->Eoper = opeqtoop(n->Eoper);
1227: break;
1228: case OPpostinc: /* (V i++ c) => V */
1229: case OPpostdec: /* (V i-- c) => V */
1230: e1 = n->E1;
1231: el_free(n->E2);
1232: el_copy(n,e1);
1233: el_free(e1);
1234: break;
1235: case OPnegass:
1236: n->Eoper = OPneg;
1237: break;
1238: case OPbtc:
1239: case OPbtr:
1240: case OPbts:
1241: n->Eoper = OPbt;
1242: break;
1243: default:
1244: assert(0);
1245: }
1246: }
1247:
1248: /************************
1249: * Compute number of =,op=,i++,i--,--i,++i elems.
1250: * (Unambiguous assignments only. Ambiguous ones would always be live.)
1251: * Some compilers generate better code for ?: than if-then-else.
1252: */
1253:
1254: STATIC unsigned numasg(elem *e)
1255: {
1256: assert(e);
1257: if (OTassign(e->Eoper) && e->E1->Eoper == OPvar)
1258: { e->Nflags |= NFLassign;
1259: return 1 + numasg(e->E1) + (OTbinary(e->Eoper) ? numasg(e->E2) : 0);
1260: }
1261: e->Nflags &= ~NFLassign;
1262: return OTunary(e->Eoper) ? numasg(e->E1) :
1263: OTbinary(e->Eoper) ? numasg(e->E1) + numasg(e->E2) : 0;
1264: }
1265:
1266: /******************************
1267: * Tree walk routine for rmdeadass().
1268: * DEAD = assignments which are dead
1269: * POSS = assignments which are possibly dead
1270: * The algorithm is basically:
1271: * if we have an assignment to v,
1272: * for all defs of v in POSS
1273: * set corresponding bits in DEAD
1274: * set bit for this def in POSS
1275: * if we have a reference to v,
1276: * clear all bits in POSS that are refs of v
1277: */
1278:
1279: STATIC void accumda(elem *n,vec_t DEAD, vec_t POSS)
1280: { vec_t Pl,Pr,Dl,Dr;
1281: register unsigned i,op,vecdim;
1282:
1283: /*chkvecdim(asstop,0);*/
1284: assert(n && DEAD && POSS);
1285: op = n->Eoper;
1286: switch (op)
1287: { case OPcolon:
1288: case OPcolon2:
1289: Pl = vec_clone(POSS);
1290: Pr = vec_clone(POSS);
1291: Dl = vec_calloc(asstop);
1292: Dr = vec_calloc(asstop);
1293: accumda(n->E1,Dl,Pl);
1294: accumda(n->E2,Dr,Pr);
1295:
1296: /* D |= P & (Dl & Dr) | ~P & (Dl | Dr) */
1297: /* P = P & (Pl & Pr) | ~P & (Pl | Pr) */
1298: /* = Pl & Pr | ~P & (Pl | Pr) */
1299: vecdim = vec_dim(DEAD);
1300: for (i = 0; i < vecdim; i++)
1301: #if MPW
1302: {
1303: unsigned tmp1,tmp2;
1304: tmp1 = POSS[i] & Dl[i] & Dr[i] ;
1305: tmp2 = ~POSS[i] & (Dl[i] | Dr[i]);
1306: DEAD[i] |= tmp1 | tmp2;
1307: tmp1 = Pl[i] & Pr[i];
1308: tmp2 = ~POSS[i] & (Pl[i] | Pr[i]);
1309: POSS[i] = tmp1 | tmp2;
1310: }
1311: #else
1312: { DEAD[i] |= POSS[i] & Dl[i] & Dr[i] |
1313: ~POSS[i] & (Dl[i] | Dr[i]);
1314: POSS[i] = Pl[i] & Pr[i] | ~POSS[i] & (Pl[i] | Pr[i]);
1315: }
1316: #endif
1317: vec_free(Pl); vec_free(Pr); vec_free(Dl); vec_free(Dr);
1318: break;
1319:
1320: case OPandand:
1321: case OPoror:
1322: accumda(n->E1,DEAD,POSS);
1323: // Substituting into the above equations Pl=P and Dl=0:
1324: // D |= Dr - P
1325: // P = Pr
1326: Pr = vec_clone(POSS);
1327: Dr = vec_calloc(asstop);
1328: accumda(n->E2,Dr,Pr);
1329: vec_subass(Dr,POSS);
1330: vec_orass(DEAD,Dr);
1331: vec_copy(POSS,Pr);
1332: vec_free(Pr); vec_free(Dr);
1333: break;
1334:
1335: case OPvar:
1336: { symbol *v = n->EV.sp.Vsym;
1337: targ_size_t voff = n->EV.sp.Voffset;
1338: unsigned vsize = tysize(n->Ety);
1339:
1340: // We have a reference. Clear all bits in POSS that
1341: // could be referenced.
1342:
1343: for (i = 0; i < assnum; i++)
1344: { register elem *ti;
1345:
1346: ti = Elvalue(assnod[i]);
1347: if (v == ti->EV.sp.Vsym &&
1348: // If symbol references overlap
1349: voff + vsize > ti->EV.sp.Voffset &&
1350: ti->EV.sp.Voffset + tysize(ti->Ety) > voff
1351: )
1352: vec_clearbit(i,POSS);
1353: }
1354: break;
1355: }
1356:
1357: case OPasm: // reference everything
1358: for (i = 0; i < assnum; i++)
1359: vec_clearbit(i,POSS);
1360: break;
1361:
1362: case OPind:
1363: case OPucall:
1364: case OPucallns:
1365: #if !TX86
1366: case OPvptrfptr:
1367: #endif
1368: accumda(n->E1,DEAD,POSS);
1369: vec_subass(POSS,ambigref); // remove possibly refed
1370: // assignments from list
1371: // of possibly dead ones
1372: break;
1373:
1374: case OPconst:
1375: break;
1376:
1377: case OPcall:
1378: case OPcallns:
1379: case OPmemcpy:
1380: case OPstrcpy:
1381: case OPmemset:
1382: accumda(n->E2,DEAD,POSS);
1383: case OPstrlen:
1384: accumda(n->E1,DEAD,POSS);
1385: vec_subass(POSS,ambigref); // remove possibly refed
1386: // assignments from list
1387: // of possibly dead ones
1388: break;
1389:
1390: case OPnewarray:
1391: case OPmultinewarray:
1392: case OParray:
1393: case OPfield:
1394: case OPstrcat:
1395: case OPstrcmp:
1396: case OPmemcmp:
1397: accumda(n->E1,DEAD,POSS);
1398: accumda(n->E2,DEAD,POSS);
1399: vec_subass(POSS,ambigref); // remove possibly refed
1400: // assignments from list
1401: // of possibly dead ones
1402: break;
1403:
1404: default:
1405: if (OTassign(op))
1406: { elem *t;
1407:
1408: if (ERTOL(n))
1409: accumda(n->E2,DEAD,POSS);
1410: t = Elvalue(n);
1411: // if not (v = expression) then gen refs of left tree
1412: if (op != OPeq)
1413: accumda(n->E1,DEAD,POSS);
1414: else if (OTunary(t->Eoper)) // if (*e = expression)
1415: accumda(t->E1,DEAD,POSS);
1416: else if (OTbinary(t->Eoper))
1417: { accumda(t->E1,DEAD,POSS);
1418: accumda(t->E2,DEAD,POSS);
1419: }
1420: if (!ERTOL(n) && op != OPnegass)
1421: accumda(n->E2,DEAD,POSS);
1422:
1423: // if unambiguous assignment, post all possibilities
1424: // to DEAD
1425: if (op == OPeq && t->Eoper == OPvar)
1426: {
1427: for (i = 0; i < assnum; i++)
1428: { register elem *ti;
1429:
1430: ti = Elvalue(assnod[i]);
1431: // There may be some problem with this next
1432: // statement with unions.
1433: if (ti->EV.sp.Vsym == t->EV.sp.Vsym &&
1434: ti->EV.sp.Voffset == t->EV.sp.Voffset &&
1435: tysize(ti->Ety) == tysize(t->Ety) &&
1436: !(t->Ety & mTYvolatile) &&
1437: //t->EV.sp.Vsym->Sflags & SFLunambig &&
1438: vec_testbit(i,POSS))
1439: vec_setbit(i,DEAD);
1440: }
1441: }
1442:
1443: // if assignment operator, post this def to POSS
1444: if (n->Nflags & NFLassign)
1445: { assnod[assnum] = n;
1446: vec_setbit(assnum,POSS);
1447:
1448: // if variable could be referenced by a pointer
1449: // or a function call, mark the assignment in
1450: // ambigref
1451: if (!(t->EV.sp.Vsym->Sflags & SFLunambig))
1452: { vec_setbit(assnum,ambigref);
1453: #if DEBUG
1454: if (debugc)
1455: { dbg_printf("ambiguous lvalue: ");
1456: WReqn(n);
1457: dbg_printf("\n");
1458: }
1459: #endif
1460: }
1461:
1462: assnum++;
1463: }
1464: }
1465: else if (OTrtol(op))
1466: { accumda(n->E2,DEAD,POSS);
1467: accumda(n->E1,DEAD,POSS);
1468: }
1469: else if (OTbinary(op))
1470: { accumda(n->E1,DEAD,POSS);
1471: accumda(n->E2,DEAD,POSS);
1472: }
1473: else if (OTunary(op))
1474: accumda(n->E1,DEAD,POSS);
1475: break;
1476: }
1477: }
1478:
1479: /***************************
1480: * Mark all dead variables. Only worry about register candidates.
1481: * Compute live ranges for register candidates.
1482: * Be careful not to compute live ranges for members of structures (CLMOS).
1483: */
1484:
1485: void deadvar()
1486: { SYMIDX i;
1487:
1488: assert(dfo);
1489:
1490: /* First, mark each candidate as dead. */
1491: /* Initialize vectors for live ranges. */
1492: /*setvecdim(dfotop);*/
1493: for (i = 0; i < globsym.top; i++)
1494: { symbol *s = globsym.tab[i];
1495:
1496: if (s->Sflags & SFLunambig)
1497: {
1498: s->Sflags |= SFLdead;
1499: if (s->Sflags & GTregcand)
1500: { if (s->Srange)
1501: vec_clear(s->Srange);
1502: else
1503: s->Srange = vec_calloc(maxblks);
1504: }
1505: }
1506: }
1507:
1508: /* Go through trees and "liven" each one we see. */
1509: for (i = 0; i < dfotop; i++)
warning C4018: '<' : signed/unsigned mismatch
1510: if (dfo[i]->Belem)
1511: dvwalk(dfo[i]->Belem,i);
1512:
1513: /* Compute live variables. Set bit for block in live range */
1514: /* if variable is in the IN set for that block. */
1515: flowlv(); /* compute live variables */
1516: for (i = 0; i < globsym.top; i++)
1517: { register unsigned j;
1518:
1519: if (globsym.tab[i]->Srange /*&& globsym.tab[i]->Sclass != CLMOS*/)
1520: for (j = 0; j < dfotop; j++)
1521: if (vec_testbit(i,dfo[j]->Binlv))
1522: vec_setbit(j,globsym.tab[i]->Srange);
1523: }
1524:
1525: /* Print results */
1526: for (i = 0; i < globsym.top; i++)
1527: { register char *p;
warning C4101: 'p' : unreferenced local variable
1528: symbol *s = globsym.tab[i];
1529:
1530: if (s->Sflags & SFLdead && s->Sclass != SCparameter && s->Sclass != SCregpar)
1531: s->Sflags &= ~GTregcand; // do not put dead variables in registers
1532: #ifdef DEBUG
1533: p = (char *) s->Sident ;
1534: if (s->Sflags & SFLdead)
1535: cmes3("Symbol %d '%s' is dead\n",i,p);
1536: if (debugc && s->Srange /*&& s->Sclass != CLMOS*/)
1537: { dbg_printf("Live range for %d '%s': ",i,p);
1538: vec_println(s->Srange);
1539: }
1540: #endif
1541: }
1542: }
1543:
1544: /*****************************
1545: * Tree walk support routine for deadvar().
1546: * Input:
1547: * n = elem to look at
1548: * i = block index
1549: */
1550:
1551: STATIC void dvwalk(register elem *n,register unsigned i)
1552: {
1553: for (; TRUE; n = n->E1)
1554: { assert(n);
1555: if (n->Eoper == OPvar || n->Eoper == OPrelconst)
1556: { register symbol *s = n->EV.sp.Vsym;
1557:
1558: s->Sflags &= ~SFLdead;
1559: if (s->Srange)
1560: vec_setbit(i,s->Srange);
1561: }
1562: else if (!OTleaf(n->Eoper))
1563: { if (OTbinary(n->Eoper))
1564: dvwalk(n->E2,i);
1565: continue;
1566: }
1567: break;
1568: }
1569: }
1570:
1571: /*********************************
1572: * Optimize very busy expressions (VBEs).
1573: */
1574:
1575: static vec_t blockseen; /* which blocks we have visited */
1576:
1577: void verybusyexp()
1578: { elem **pn;
1579: register int i;
1580: register unsigned j,k,l;
1581:
1582: cmes("verybusyexp()\n");
1583: flowvbe(); /* compute VBEs */
1584: if (exptop <= 1) return; /* if no VBEs */
1585: assert(expblk);
1586: if (blockinit())
1587: return; // can't handle ASM blocks
1588: compdom(); /* compute dominators */
1589: /*setvecdim(exptop);*/
1590: genkillae(); /* compute Bgen and Bkill for */
1591: /* AEs */
1592: /*chkvecdim(exptop,0);*/
1593: blockseen = vec_calloc(dfotop);
1594:
1595: /* Go backwards through dfo so that VBEs are evaluated as */
1596: /* close as possible to where they are used. */
1597: for (i = dfotop; --i >= 0;) /* for each block */
1598: { register block *b = dfo[i];
1599: register int done;
1600:
1601: /* Do not hoist things to blocks that do not */
1602: /* divide the flow of control. */
1603:
1604: switch (b->BC)
1605: { case BCiftrue:
1606: case BCswitch:
1607: break;
1608: default:
1609: continue;
1610: }
1611:
1612: /* Find pointer to last statement in current elem */
1613: pn = &(b->Belem);
1614: if (*pn)
1615: { while ((*pn)->Eoper == OPcomma)
1616: pn = &((*pn)->E2);
1617: /* If last statement has side effects, */
1618: /* don't do these VBEs. Potentially we */
1619: /* could by assigning the result to */
1620: /* a temporary, and rewriting the tree */
1621: /* from (n) to (T=n,T) and installing */
1622: /* the VBE as (T=n,VBE,T). This */
1623: /* may not buy us very much, so we will */
1624: /* just skip it for now. */
1625: /*if (sideeffect(*pn))*/
1626: if (!(*pn)->Eexp)
1627: continue;
1628: }
1629:
1630: /* Eliminate all elems that have already been */
1631: /* hoisted (indicated by expnod[] == 0). */
1632: /* Constants are not useful as VBEs. */
1633: /* Eliminate all elems from Bout that are not in blocks */
1634: /* that are dominated by b. */
1635: #if 0
1636: dbg_printf("block %d Bout = ",i);
1637: vec_println(b->Bout);
1638: #endif
1639: done = TRUE;
1640: foreach (j,exptop,b->Bout)
1641: { if (expnod[j] == 0 ||
1642: !!OTleaf(expnod[j]->Eoper) ||
1643: !dom(b,expblk[j]))
1644: vec_clearbit(j,b->Bout);
1645: else
1646: done = FALSE;
1647: }
1648: if (done) continue;
1649:
1650: /* Eliminate from Bout all elems that are killed by */
1651: /* a block between b and that elem. */
1652: #if 0
1653: dbg_printf("block %d Bout = ",i);
1654: vec_println(b->Bout);
1655: #endif
1656:
1657: foreach (j,exptop,b->Bout)
1658: { register list_t bl;
1659:
1660: vec_clear(blockseen);
1661: for (bl = expblk[j]->Bpred; bl; bl = list_next(bl))
1662: { if (killed(j,list_block(bl),b))
1663: { vec_clearbit(j,b->Bout);
1664: break;
1665: }
1666: }
1667: }
1668:
1669: /* For each elem still left, make sure that there */
1670: /* exists a path from b to j along which there is */
1671: /* no other use of j (else it would be a CSE, and */
1672: /* it would be a waste of time to hoist it). */
1673: #if 0
1674: dbg_printf("block %d Bout = ",i);
1675: vec_println(b->Bout);
1676: #endif
1677:
1678: foreach (j,exptop,b->Bout)
1679: { register list_t bl;
1680:
1681: vec_clear(blockseen);
1682: for (bl = expblk[j]->Bpred; bl; bl = list_next(bl))
1683: { if (ispath(j,list_block(bl),b))
1684: goto L2;
1685: }
1686: vec_clearbit(j,b->Bout); /* thar ain't no path */
1687: L2: ;
1688: }
1689:
1690:
1691: /* For each elem that appears more than once in Bout */
1692: /* We have a VBE. */
1693: #if 0
1694: dbg_printf("block %d Bout = ",i);
1695: vec_println(b->Bout);
1696: #endif
1697:
1698: foreach (j,exptop,b->Bout)
1699: {
1700: for (k = j + 1; k < exptop; k++)
1701: { if (vec_testbit(k,b->Bout) &&
1702: el_match(expnod[j],expnod[k]))
1703: goto foundvbe;
1704: }
1705: continue; /* no VBE here */
1706:
1707: foundvbe: /* we got one */
1708: #ifdef DEBUG
1709: if (debugc)
1710: { dbg_printf("VBE %d,%d, block %d (",j,k,i);
1711: WReqn(expnod[j]);
1712: dbg_printf(");\n");
1713: }
1714: #endif
1715: *pn = el_bin(OPcomma,(*pn)->Ety,
1716: el_copytree(expnod[j]),*pn);
1717:
1718: /* Mark all the vbe elems found but one (the */
1719: /* expnod[j] one) so that the expression will */
1720: /* only be hoisted again if other occurrances */
1721: /* of the expression are found later. This */
1722: /* will substitute for the fact that the */
1723: /* el_copytree() expression does not appear in expnod[]. */
1724: l = k;
1725: do
1726: { if ( k == l || (vec_testbit(k,b->Bout) &&
1727: el_match(expnod[j],expnod[k])))
1728: {
1729: /* Fix so nobody else will */
1730: /* vbe this elem */
1731: expnod[k] = NULL;
1732: vec_clearbit(k,b->Bout);
1733: }
1734: } while (++k < exptop);
1735: changes++;
1736: } /* foreach */
1737: } /* for */
1738: vec_free(blockseen);
1739: }
1740:
1741: /****************************
1742: * Return TRUE if elem j is killed somewhere
1743: * between b and bp.
1744: */
1745:
1746: STATIC int killed(register unsigned j,register block *bp,block *b)
1747: { register list_t bl;
1748:
1749: if (bp == b || vec_testbit(bp->Bdfoidx,blockseen))
1750: return FALSE;
1751: if (vec_testbit(j,bp->Bkill))
1752: return TRUE;
1753: vec_setbit(bp->Bdfoidx,blockseen); /* mark as visited */
1754: for (bl = bp->Bpred; bl; bl = list_next(bl))
1755: if (killed(j,list_block(bl),b))
1756: return TRUE;
1757: return FALSE;
1758: }
1759:
1760: /***************************
1761: * Return TRUE if there is a path from b to bp along which
1762: * elem j is not used.
1763: * Input:
1764: * b -> block where we want to put the VBE
1765: * bp -> block somewhere between b and block containing j
1766: * j = VBE expression elem candidate (index into expnod[])
1767: */
1768:
1769: STATIC int ispath(register unsigned j,register block *bp,block *b)
1770: { register list_t bl;
1771: register unsigned i;
1772:
1773: /*chkvecdim(exptop,0);*/
1774: if (bp == b) return TRUE; /* the trivial case */
1775: if (vec_testbit(bp->Bdfoidx,blockseen))
1776: return FALSE; /* already seen this block */
1777: vec_setbit(bp->Bdfoidx,blockseen); /* we've visited this block */
1778:
1779: /* FALSE if elem j is used in block bp (and reaches the end */
1780: /* of bp, indicated by it being an AE in Bgen) */
1781: foreach (i,exptop,bp->Bgen) /* look thru used expressions */
1782: { if (i != j && expnod[i] && el_match(expnod[i],expnod[j]))
1783: return FALSE;
1784: }
1785:
1786: /* Not used in bp, see if there is a path through a predecessor */
1787: /* of bp */
1788: for (bl = bp->Bpred; bl; bl = list_next(bl))
1789: if (ispath(j,list_block(bl),b))
1790: return TRUE;
1791:
1792: return FALSE; /* j is used along all paths */
1793: }
1794:
1795: #endif
1796: