1: // Copyright (C) 1985-1998 by Symantec
2: // Copyright (C) 2000-2009 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 "type.h"
23: #include "oper.h"
24: #include "vec.h"
25:
26: static char __file__[] = __FILE__; /* for tassert.h */
27: #include "tassert.h"
28:
29: /* Since many routines are nearly identical, we can combine them with */
30: /* this flag: */
31:
32: #define AE 1
33: #define CP 2
34: #define VBE 3
35:
36: static int flowxx; /* one of the above values */
37:
38: static vec_t ambigsym = NULL;
39:
40: STATIC void rdgenkill(void);
41: STATIC void numdefelems(elem *n);
42: STATIC void asgdefelems(block *b , elem *n);
43: STATIC void aecpgenkill(void);
44: STATIC int numaeelems(elem *n);
45: STATIC void numcpelems(elem *n);
46: STATIC void asgexpelems(elem *n);
47: STATIC void defstarkill(void);
48: STATIC void rdelem(vec_t *pgen , vec_t *pkill , elem *n);
49: STATIC void aecpelem(vec_t *pgen , vec_t *pkill , elem *n);
50: STATIC void accumaecp(vec_t GEN , vec_t KILL , elem *n);
51: STATIC void accumaecpx(elem *n);
52: STATIC void lvgenkill(void);
53: STATIC void lvelem(vec_t *pgen , vec_t *pkill , elem *n);
54: STATIC void accumlv(vec_t GEN , vec_t KILL , elem *n);
55: STATIC void accumvbe(vec_t GEN , vec_t KILL , elem *n);
56: STATIC void accumrd(vec_t GEN , vec_t KILL , elem *n);
57: STATIC void flowaecp(void);
58:
59: /***************** REACHING DEFINITIONS *********************/
60:
61: /************************************
62: * Compute reaching definitions (RDs).
63: * That is, for each block B and each program variable X
64: * find all elems that could be the last elem that defines
65: * X along some path to B.
66: * Binrd = the set of defs reaching the beginning of B.
67: * Boutrd = the set of defs reaching the end of B.
68: * Bkillrd = set of defs that are killed by some def in B.
69: * Bgenrd = set of defs in B that reach the end of B.
70: */
71:
72: void flowrd()
73: { register vec_t tmp;
74: register unsigned i;
75: register bool anychng;
76:
77: rdgenkill(); /* Compute Bgen and Bkill for RDs */
78: if (deftop == 0) /* if no definition elems */
79: return; /* no analysis to be done */
80:
81: /* The transfer equation is: */
82: /* Bin = union of Bouts of all predecessors of B. */
83: /* Bout = (Bin - Bkill) | Bgen */
84: /* Using Ullman's algorithm: */
85:
86: for (i = 0; i < dfotop; i++)
87: vec_copy(dfo[i]->Boutrd,dfo[i]->Bgen);
88:
89: tmp = vec_calloc(deftop);
90: do
91: { anychng = FALSE;
92: for (i = 0; i < dfotop; i++) /* for each block */
93: { register block *b;
94: register list_t bp;
95:
96: b = dfo[i];
97:
98: /* Binrd = union of Boutrds of all predecessors of b */
99: vec_clear(b->Binrd);
100: if (b->BC != BCcatch /*&& b->BC != BCjcatch*/)
101: {
102: /* Set Binrd to 0 to account for:
103: * i = 0;
104: * try { i = 1; throw; } catch () { x = i; }
105: */
106: for (bp = b->Bpred; bp; bp = list_next(bp))
107: vec_orass(b->Binrd,list_block(bp)->Boutrd);
108: }
109: /* Bout = (Bin - Bkill) | Bgen */
110: vec_sub(tmp,b->Binrd,b->Bkill);
111: vec_orass(tmp,b->Bgen);
112: if (!anychng)
113: anychng = !vec_equal(tmp,b->Boutrd);
114: vec_copy(b->Boutrd,tmp);
115: }
116: } while (anychng); /* while any changes to Boutrd */
117: vec_free(tmp);
118:
119: #if 0
120: dbg_printf("Reaching definitions\n");
121: for (i = 0; i < dfotop; i++)
122: { register block *b = dfo[i];
123:
124: assert(vec_numbits(b->Binrd) == deftop);
125: dbg_printf("B%d Bin ",i); vec_println(b->Binrd);
126: dbg_printf(" Bgen "); vec_println(b->Bgen);
127: dbg_printf(" Bkill "); vec_println(b->Bkill);
128: dbg_printf(" Bout "); vec_println(b->Boutrd);
129: }
130: #endif
131: }
132:
133: /***************************
134: * Compute Bgen and Bkill for RDs.
135: */
136:
137: STATIC void rdgenkill()
138: { register unsigned i,deftopsave;
139:
140: #if TX86
141: util_free(defnod); /* free existing junk */
142: #else /* might be from previous memory pool */
143: MEM_BEF_FREE(defnod); /* free existing junk */
144: #endif
145: defnod = NULL;
146:
147: /* Compute number of definition elems. */
148: deftop = 0;
149: for (i = 0; i < dfotop; i++)
150: if (dfo[i]->Belem)
151: {
152: numdefelems(dfo[i]->Belem);
153: }
154: if (deftop == 0)
155: return;
156:
157: /* Allocate array of pointers to all definition elems */
158: /* The elems are in dfo order. */
159: /* defnod[]s consist of a elem pointer and a pointer */
160: /* to the enclosing block. */
161: #if TX86
162: defnod = (dn *) util_calloc(sizeof(dn),deftop);
163: #else
164: defnod = (dn *)MEM_BEF_CALLOC(sizeof(dn) * deftop);
165: #endif
166: deftopsave = deftop;
167: deftop = 0;
168: for (i = 0; i < dfotop; i++)
169: if (dfo[i]->Belem)
170: asgdefelems(dfo[i],dfo[i]->Belem);
171: assert(deftop == deftopsave);
172:
173: for (i = 0; i < dfotop; i++) /* for each block */
174: { register block *b = dfo[i];
175:
176: /* dump any existing vectors */
177: vec_free(b->Bgen);
178: vec_free(b->Bkill);
179: vec_free(b->Binrd);
180: vec_free(b->Boutrd);
181:
182: /* calculate and create new vectors */
183: rdelem(&(b->Bgen),&(b->Bkill),b->Belem);
184: if (b->BC == BCasm)
185: { vec_clear(b->Bkill); // KILL nothing
186: vec_set(b->Bgen); // GEN everything
187: }
188: b->Binrd = vec_calloc(deftop);
189: b->Boutrd = vec_calloc(deftop);
190: }
191: }
192:
193: /**********************
194: * Compute # of definition elems (deftop).
195: */
196:
197: STATIC void numdefelems(register elem *n)
198: {
199: while (1)
200: { assert(n);
201: if (OTdef(n->Eoper))
202: deftop++;
203: if (OTbinary(n->Eoper))
204: {
205: numdefelems(n->E1);
206: n = n->E2;
207: }
208: else if (OTunary(n->Eoper))
209: {
210: n = n->E1;
211: }
212: else
213: break;
214: }
215: }
216:
217: /**************************
218: * Load defnod[] array.
219: * Loaded in order of execution of the elems. Not sure if this is
220: * necessary.
221: */
222:
223: STATIC void asgdefelems(block *b,register elem *n)
224: { register unsigned op;
225:
226: assert(b && n);
227: op = n->Eoper;
228: if (ERTOL(n))
229: { asgdefelems(b,n->E2);
230: asgdefelems(b,n->E1);
231: }
232: else if (OTbinary(op))
233: { asgdefelems(b,n->E1);
234: asgdefelems(b,n->E2);
235: }
236: else if (OTunary(op))
237: asgdefelems(b,n->E1);
238: if (OTdef(op))
239: { assert(defnod);
240: defnod[deftop].DNblock = b;
241: defnod[deftop].DNelem = n;
242: deftop++;
243: }
244: }
245:
246: /*************************************
247: * Allocate and compute rd GEN and KILL.
248: */
249:
250: STATIC void rdelem(vec_t *pgen,vec_t *pkill, /* where to put result */
251: elem *n ) /* tree to evaluate for GEN and KILL */
252: {
253: *pgen = vec_calloc(deftop);
254: *pkill = vec_calloc(deftop);
255: if (n)
256: accumrd(*pgen,*pkill,n);
257: }
258:
259: /**************************************
260: * Accumulate GEN and KILL vectors for this elem.
261: */
262:
263: STATIC void accumrd(vec_t GEN,vec_t KILL,elem *n)
264: { vec_t Gl,Kl,Gr,Kr;
265: unsigned op;
266:
267: assert(GEN && KILL && n);
268: op = n->Eoper;
269: if (OTunary(op))
270: accumrd(GEN,KILL,n->E1);
271: else if (OTbinary(op))
272: {
273: if (op == OPcolon || op == OPcolon2)
274: {
275: rdelem(&Gl,&Kl,n->E1);
276: rdelem(&Gr,&Kr,n->E2);
277:
278: /* GEN = (GEN - Kl) | Gl | */
279: /* (GEN - Kr) | Gr */
280: /* KILL |= Kl & Kr */
281:
282: vec_orass(Gl,Gr);
283: vec_sub(Gr,GEN,Kl);
284: vec_orass(Gl,Gr);
285: vec_sub(Gr,GEN,Kr);
286: vec_or(GEN,Gl,Gr);
287:
288: vec_andass(Kl,Kr);
289: vec_orass(KILL,Kl);
290:
291: vec_free(Gl);
292: vec_free(Kl);
293: vec_free(Gr);
294: vec_free(Kr);
295: }
296: else if (op == OPandand || op == OPoror)
297: {
298: accumrd(GEN,KILL,n->E1);
299: rdelem(&Gr,&Kr,n->E2);
300: vec_orass(GEN,Gr); /* GEN |= Gr */
301:
302: vec_free(Gr);
303: vec_free(Kr);
304: }
305: else if (OTrtol(op) && ERTOL(n))
306: { accumrd(GEN,KILL,n->E2);
307: accumrd(GEN,KILL,n->E1);
308: }
309: else
310: { accumrd(GEN,KILL,n->E1);
311: accumrd(GEN,KILL,n->E2);
312: }
313: }
314:
315: if (OTdef(op)) /* if definition elem */
316: updaterd(n,GEN,KILL);
317: }
318:
319: /******************** AVAILABLE EXPRESSIONS ***********************/
320:
321: /************************************
322: * Compute available expressions (AEs).
323: * That is, expressions whose result is still current.
324: * Bin = the set of AEs reaching the beginning of B.
325: * Bout = the set of AEs reaching the end of B.
326: */
327:
328: void flowae()
329: {
330: flowxx = AE;
331: flowaecp();
332: }
333:
334: /**************************** COPY PROPAGATION ************************/
335:
336: /***************************************
337: * Compute copy propagation info (CPs).
338: * Very similar to AEs (the same code is used).
339: * Using RDs for copy propagation is WRONG!
340: * That is, set of copy statements still valid.
341: * Bin = the set of CPs reaching the beginning of B.
342: * Bout = the set of CPs reaching the end of B.
343: */
344:
345: void flowcp()
346: {
347: flowxx = CP;
348: flowaecp();
349: }
350:
351: /*****************************************
352: * Common flow analysis routines for Available Expressions and
353: * Copy Propagation.
354: * Input:
355: * flowxx
356: */
357:
358: STATIC void flowaecp()
359: { vec_t tmp;
360: register unsigned i;
361: bool anychng;
362:
363: aecpgenkill(); /* Compute Bgen and Bkill for AEs or CPs */
364: if (exptop <= 1) /* if no expressions */
365: return;
366:
367: /* The transfer equation is: */
368: /* Bin = & Bout(all predecessors P of B) */
369: /* Bout = (Bin - Bkill) | Bgen */
370: /* Using Ullman's algorithm: */
371:
372: vec_clear(startblock->Bin);
373: vec_copy(startblock->Bout,startblock->Bgen); /* these never change */
374: if (startblock->BC == BCiftrue)
375: vec_copy(startblock->Bout2,startblock->Bgen2); // these never change
376:
377: /* For all blocks except startblock */
378: for (i = 1; i < dfotop; i++)
379: { register block *b = dfo[i];
380:
381: vec_set(b->Bin); /* Bin = all expressions */
382:
383: /* Bout = (Bin - Bkill) | Bgen */
384: vec_sub(b->Bout,b->Bin,b->Bkill);
385: vec_orass(b->Bout,b->Bgen);
386: if (b->BC == BCiftrue)
387: { vec_sub(b->Bout2,b->Bin,b->Bkill2);
388: vec_orass(b->Bout2,b->Bgen2);
389: }
390: }
391:
392: tmp = vec_calloc(exptop);
393: do
394: { anychng = FALSE;
395:
396: // For all blocks except startblock
397: for (i = 1; i < dfotop; i++)
398: { block *b = dfo[i];
399: list_t bl = b->Bpred;
400: block *bp;
401:
402: // Bin = & of Bout of all predecessors
403: // Bout = (Bin - Bkill) | Bgen
404:
405: assert(bl); // it must have predecessors
406: bp = list_block(bl);
407: if (bp->BC == BCiftrue && list_block(bp->Bsucc) != b)
408: vec_copy(b->Bin,bp->Bout2);
409: else
410: vec_copy(b->Bin,bp->Bout);
411: while (TRUE)
412: { bl = list_next(bl);
413: if (!bl)
414: break;
415: bp = list_block(bl);
416: if (bp->BC == BCiftrue && list_block(bp->Bsucc) != b)
417: vec_andass(b->Bin,bp->Bout2);
418: else
419: vec_andass(b->Bin,bp->Bout);
420: }
421:
422: if (anychng)
423: { vec_sub(b->Bout,b->Bin,b->Bkill);
424: vec_orass(b->Bout,b->Bgen);
425: }
426: else
427: { vec_sub(tmp,b->Bin,b->Bkill);
428: vec_orass(tmp,b->Bgen);
429: if (!vec_equal(tmp,b->Bout))
430: { // Swap Bout and tmp instead of
431: // copying tmp over Bout
432: vec_t v;
433:
434: v = tmp;
435: tmp = b->Bout;
436: b->Bout = v;
437: anychng = TRUE;
438: }
439: }
440:
441: if (b->BC == BCiftrue)
442: { // Bout2 = (Bin - Bkill2) | Bgen2
443: if (anychng)
444: { vec_sub(b->Bout2,b->Bin,b->Bkill2);
445: vec_orass(b->Bout2,b->Bgen2);
446: }
447: else
448: { vec_sub(tmp,b->Bin,b->Bkill2);
449: vec_orass(tmp,b->Bgen2);
450: if (!vec_equal(tmp,b->Bout2))
451: { // Swap Bout and tmp instead of
452: // copying tmp over Bout2
453: vec_t v;
454:
455: v = tmp;
456: tmp = b->Bout2;
457: b->Bout2 = v;
458: anychng = TRUE;
459: }
460: }
461: }
462: }
463: } while (anychng);
464: vec_free(tmp);
465: }
466:
467: /******************************
468: * A variable to avoid parameter overhead to asgexpelems().
469: */
470:
471: static block *this_block;
472:
473: /***********************************
474: * Compute Bgen and Bkill for AEs, CPs, and VBEs.
475: */
476:
477: STATIC void aecpgenkill()
478: { register unsigned i;
479: unsigned exptopsave;
480:
481: #if TX86
482: util_free(expnod); /* dump any existing one */
483: #else /* might be from previous memory pool */
484: MEM_BEF_FREE(expnod); /* dump any existing one */
485: #endif
486: expnod = NULL;
487:
488: /* Compute number of expressions */
489: exptop = 1; /* start at 1 */
490: for (i = 0; i < dfotop; i++)
491: if (dfo[i]->Belem)
492: { if (flowxx == CP)
493: numcpelems(dfo[i]->Belem);
494: else // AE || VBE
495: numaeelems(dfo[i]->Belem);
496: }
497: if (exptop <= 1) /* if no expressions */
498: return;
499:
500: /* Allocate array of pointers to all expression elems. */
501: /* (The elems are in order. Also, these expressions must not */
502: /* have any side effects, and possibly should not be machine */
503: /* dependent primitive addressing modes.) */
504: #if TX86
505: expnod = (elem **) util_calloc(sizeof(elem *),exptop);
506: util_free(expblk);
507: expblk = (flowxx == VBE)
508: ? (block **) util_calloc(sizeof(block *),exptop) : NULL;
509: #else
510: expnod = (elem **) MEM_BEF_CALLOC(sizeof(elem *) * exptop);
511: MEM_BEF_FREE(expblk);
512: expblk = (flowxx == VBE)
513: ? (block **) MEM_BEF_CALLOC(sizeof(block *) * exptop) : NULL;
514: #endif
515:
516: exptopsave = exptop;
517: exptop = 1;
518: for (i = 0; i < dfotop; i++)
519: { this_block = dfo[i]; /* so asgexpelems knows about this */
520: if (this_block->Belem)
521: asgexpelems(this_block->Belem);
522: }
523: assert(exptop == exptopsave);
524:
525: defstarkill(); /* compute defkill and starkill */
526:
527: #if 0
528: assert(vec_numbits(defkill) == exptop);
529: assert(vec_numbits(starkill) == exptop);
530: assert(vec_numbits(vptrkill) == exptop);
531: dbg_printf("defkill "); vec_println(defkill);
532: if (starkill)
533: { dbg_printf("starkill "); vec_println(starkill);}
534: if (vptrkill)
535: { dbg_printf("vptrkill "); vec_println(vptrkill); }
536: #endif
537:
538: for (i = 0; i < dfotop; i++) /* for each block */
539: { register block *b = dfo[i];
540: elem *e;
541:
542: /* dump any existing vectors */
543: vec_free(b->Bin);
544: vec_free(b->Bout);
545: vec_free(b->Bgen);
546: vec_free(b->Bkill);
547: b->Bgen = vec_calloc(exptop);
548: b->Bkill = vec_calloc(exptop);
549: switch (b->BC)
550: {
551: case BCiftrue:
552: vec_free(b->Bout2);
553: vec_free(b->Bgen2);
554: vec_free(b->Bkill2);
555: for (e = b->Belem; e->Eoper == OPcomma; e = e->E2)
556: accumaecp(b->Bgen,b->Bkill,e);
557: if (e->Eoper == OPandand || e->Eoper == OPoror)
558: { vec_t Kr,Gr;
559:
560: accumaecp(b->Bgen,b->Bkill,e->E1);
561: Kr = vec_calloc(exptop);
562: Gr = vec_calloc(exptop);
563: accumaecp(Gr,Kr,e->E2);
564:
565: // We might or might not have executed E2
566: // KILL1 = KILL | Kr
567: // GEN1 = GEN & ((GEN - Kr) | Gr)
568:
569: // We definitely executed E2
570: // KILL2 = (KILL - Gr) | Kr
571: // GEN2 = (GEN - Kr) | Gr
572:
573: unsigned j,dim;
574: dim = vec_dim(Kr);
575: vec_t KILL = b->Bkill;
576: vec_t GEN = b->Bgen;
577:
578: for (j = 0; j < dim; j++)
579: { vec_base_t KILL1,KILL2,GEN1,GEN2;
580:
581: KILL1 = KILL[j] | Kr[j];
582: GEN1 = GEN[j] & ((GEN[j] & ~Kr[j]) | Gr[j]);
583:
584: KILL2 = (KILL[j] & ~Gr[j]) | Kr[j];
585: GEN2 = (GEN[j] & ~Kr[j]) | Gr[j];
586:
587: KILL[j] = KILL1;
588: GEN[j] = GEN1;
589: Kr[j] = KILL2;
590: Gr[j] = GEN2;
591: }
592:
593: if (e->Eoper == OPandand)
594: { b->Bkill = Kr;
595: b->Bgen = Gr;
596: b->Bkill2 = KILL;
597: b->Bgen2 = GEN;
598: }
599: else
600: { b->Bkill = KILL;
601: b->Bgen = GEN;
602: b->Bkill2 = Kr;
603: b->Bgen2 = Gr;
604: }
605: }
606: else
607: {
608: accumaecp(b->Bgen,b->Bkill,e);
609: b->Bgen2 = vec_clone(b->Bgen);
610: b->Bkill2 = vec_clone(b->Bkill);
611: }
612: b->Bout2 = vec_calloc(exptop);
613: break;
614:
615: case BCasm:
616: vec_set(b->Bkill); // KILL everything
617: vec_clear(b->Bgen); // GEN nothing
618: break;
619:
620: default:
621: // calculate GEN & KILL vectors
622: if (b->Belem)
623: accumaecp(b->Bgen,b->Bkill,b->Belem);
624: break;
625: }
626: #if 0
627: dbg_printf("block %d Bgen ",i); vec_println(b->Bgen);
628: dbg_printf(" Bkill "); vec_println(b->Bkill);
629: #endif
630: b->Bin = vec_calloc(exptop);
631: b->Bout = vec_calloc(exptop);
632: }
633: }
634:
635: /*****************************
636: * Accumulate number of expressions in exptop.
637: * Set NFLaecp as a flag indicating an AE elem.
638: * Returns:
639: * TRUE if this elem is a possible AE elem.
640: */
641:
642: STATIC int numaeelems(register elem *n)
643: { register unsigned op;
644: unsigned ae;
645:
646: assert(n);
647: op = n->Eoper;
648: if (OTunary(op))
649: { ae = numaeelems(n->E1);
650: // Disallow starred references to avoid problems with VBE's
651: // being hoisted before tests of an invalid pointer.
652: if (flowxx == VBE && op == OPind)
653: goto L1;
654: }
655: else if (OTbinary(op))
656: ae = numaeelems(n->E1) & numaeelems(n->E2);
657: else
658: ae = TRUE;
659:
660: if (ae && OTae(op) && !(n->Ety & mTYvolatile) &&
661: // Disallow struct AEs, because we can't handle CSEs that are structs
662: tybasic(n->Ety) != TYstruct)
663: { n->Nflags |= NFLaecp; /* remember for asgexpelems() */
664: exptop++;
665: }
666: else
667: L1:
668: n->Nflags &= ~NFLaecp;
669: return n->Nflags & NFLaecp;
670: }
671:
672:
673: /****************************
674: * Compute number of cp elems into exptop.
675: * Mark cp elems by setting NFLaecp flag.
676: */
677:
678: STATIC void numcpelems(elem *n)
679: { unsigned op;
680:
681: op = n->Eoper;
682: if (OTunary(op))
683: numcpelems(n->E1);
684: else if (OTbinary(op))
685: { numcpelems(n->E1);
686: numcpelems(n->E2);
687:
688: /* look for elem of the form OPvar=OPvar, where they aren't the */
689: /* same variable. */
690: if (op == OPeq &&
691: n->E1->Eoper == OPvar &&
692: n->E2->Eoper == OPvar &&
693: !((n->E1->Ety | n->E2->Ety) & mTYvolatile) &&
694: n->E1->EV.sp.Vsym != n->E2->EV.sp.Vsym)
695: { exptop++;
696: n->Nflags |= NFLaecp;
697: return;
698: }
699: }
700: n->Nflags &= ~NFLaecp;
701: }
702:
703: /********************************
704: * Assign ae (or cp) elems to expnod[] (in order of evaluation).
705: */
706:
707: STATIC void asgexpelems(elem *n)
708: {
709: assert(n);
710: if (OTunary(n->Eoper))
711: asgexpelems(n->E1);
712: else if (ERTOL(n))
713: { asgexpelems(n->E2);
714: asgexpelems(n->E1);
715: }
716: else if (OTbinary(n->Eoper))
717: { asgexpelems(n->E1);
718: asgexpelems(n->E2);
719: }
720:
721: if (n->Nflags & NFLaecp) /* if an ae, cp or vbe elem */
722: { n->Eexp = exptop; /* remember index into expnod[] */
723: expnod[exptop] = n;
724: if (expblk)
725: expblk[exptop] = this_block;
726: exptop++;
727: }
728: else
729: n->Eexp = 0;
730: }
731:
732: /********************************
733: * Compute defkill, starkill and vptrkill vectors.
734: * starkill: set of expressions killed when a variable is
735: * changed that somebody could be pointing to.
736: * (not needed for cp)
737: * starkill is a subset of defkill.
738: * defkill: set of expressions killed by an ambiguous
739: * definition.
740: * vptrkill: set of expressions killed by an access to a vptr.
741: */
742:
743: STATIC void defstarkill()
744: { register unsigned i,op;
745: register elem *n;
746:
747: vec_free(vptrkill);
748: vec_free(defkill);
749: vec_free(starkill); /* dump any existing ones */
750: defkill = vec_calloc(exptop);
751: if (flowxx != CP)
752: { starkill = vec_calloc(exptop); /* and create new ones */
753: vptrkill = vec_calloc(exptop); /* and create new ones */
754: }
755: else /* CP */
756: { starkill = NULL;
757: vptrkill = NULL;
758: }
759:
760: if (flowxx == CP)
761: {
762: for (i = 1; i < exptop; i++)
763: { n = expnod[i];
764: op = n->Eoper;
765: assert(op == OPeq);
766: assert(n->E1->Eoper==OPvar && n->E2->Eoper==OPvar);
767:
768: // Set bit in defkill if either the left or the
769: // right variable is killed by an ambiguous def.
770:
771: Symbol *s1 = n->E1->EV.sp.Vsym;
772: if (!(s1->Sflags & SFLunambig) ||
773: !(n->E2->EV.sp.Vsym->Sflags & SFLunambig))
774: {
775: vec_setbit(i,defkill);
776: }
777: }
778: }
779: else
780: {
781: for (i = 1; i < exptop; i++)
782: { n = expnod[i];
783: op = n->Eoper;
784: switch (op)
785: {
786: case OPvar:
787: if (!(n->EV.sp.Vsym->Sflags & SFLunambig))
788: vec_setbit(i,defkill);
789: break;
790:
791: case OPind: // if a 'starred' ref
792:
793: #if 1
794: /* The following program fails for this:
795: import std.c.stdio;
796:
797: class Foo
798: {
799: string foo = "abc";
800: size_t i = 0;
801:
802: void bar()
803: {
804: printf("%c\n", foo[i]);
805: i++;
806: printf("%c\n", foo[i]);
807: }
808: }
809:
810: void main()
811: {
812: auto f = new Foo();
813: f.bar();
814: }
815: */
816: // For C/C++, casting to 'const' doesn't mean it
817: // actually is const,
818: // but immutable really doesn't change
819: if ((n->Ety & (mTYimmutable | mTYvolatile)) == mTYimmutable &&
820: n->E1->Eoper == OPvar &&
821: n->E1->EV.sp.Vsym->Sflags & SFLunambig
822: )
823: break;
824: #endif
825: #if TX86
826: case OPstrlen:
827: case OPstrcmp:
828: case OPmemcmp:
829: case OPbt: // OPbt is like OPind
830: #endif
831: vec_setbit(i,defkill);
832: vec_setbit(i,starkill);
833: break;
834:
835:
836: case OPvptrfptr:
837: case OPcvptrfptr:
838: vec_setbit(i,vptrkill);
839: goto Lunary;
840:
841: default:
842: if (OTunary(op))
warning C6385: Invalid data: accessing 'unsigned char const * const optab1', the readable size is '183' bytes, but '1145' bytes might be read: Lines: 744, 745, 747, 748, 749, 750, 751, 752, 753, 760, 781, 782, 783, 784, 841, 842
843: {
844: Lunary:
845: if (vec_testbit(n->E1->Eexp,defkill))
846: vec_setbit(i,defkill);
847: if (vec_testbit(n->E1->Eexp,starkill))
848: vec_setbit(i,starkill);
849: }
850: else if (OTbinary(op))
851: {
852: if (vec_testbit(n->E1->Eexp,defkill) ||
853: vec_testbit(n->E2->Eexp,defkill))
854: vec_setbit(i,defkill);
855: if (vec_testbit(n->E1->Eexp,starkill) ||
856: vec_testbit(n->E2->Eexp,starkill))
857: vec_setbit(i,starkill);
858: }
859: break;
860: }
861: }
862: }
863: }
864:
865: /********************************
866: * Compute GEN and KILL vectors only for AEs.
867: * defkill and starkill are assumed to be already set up correctly.
868: * expnod[] is assumed to be set up correctly.
869: */
870:
871: void genkillae()
872: { register unsigned i;
873:
874: flowxx = AE;
875: assert(exptop > 1);
876: for (i = 0; i < dfotop; i++)
877: { register block *b = dfo[i];
878:
879: assert(b);
880: vec_clear(b->Bgen);
881: vec_clear(b->Bkill);
882: if (b->Belem)
883: accumaecp(b->Bgen,b->Bkill,b->Belem);
884: else if (b->BC == BCasm)
885: { vec_set(b->Bkill); // KILL everything
886: vec_clear(b->Bgen); // GEN nothing
887: }
888: }
889: }
890:
891: /************************************
892: * Allocate and compute KILL and GEN vectors for a elem.
893: */
894:
895: STATIC void aecpelem(vec_t *pgen,vec_t *pkill, elem *n)
896: { *pgen = vec_calloc(exptop);
897: *pkill = vec_calloc(exptop);
898: if (n)
899: { if (flowxx == VBE)
900: accumvbe(*pgen,*pkill,n);
901: else
902: accumaecp(*pgen,*pkill,n);
903: }
904: }
905:
906: /*************************************
907: * Accumulate GEN and KILL sets for AEs and CPs for this elem.
908: */
909:
910: static vec_t GEN; // use static copies to save on parameter passing
911: static vec_t KILL;
912:
913: STATIC void accumaecp(vec_t g,vec_t k,elem *n)
914: { vec_t GENsave,KILLsave;
915:
916: assert(g && k);
917: GENsave = GEN;
918: KILLsave = KILL;
919: GEN = g;
920: KILL = k;
921: accumaecpx(n);
922: GEN = GENsave;
923: KILL = KILLsave;
924: }
925:
926: STATIC void accumaecpx(elem *n)
927: { unsigned i,op;
928: elem *t;
929:
930: assert(n);
931: elem_debug(n);
932: op = n->Eoper;
933:
934: switch (op)
935: {
936: case OPvar:
937: case OPconst:
938: case OPrelconst:
939: if ((flowxx == AE) && n->Eexp)
940: { unsigned b;
941: #ifdef DEBUG
942: assert(expnod[n->Eexp] == n);
943: #endif
944: b = n->Eexp;
945: vec_setclear(b,GEN,KILL);
946: }
947: return;
948: case OPcolon:
949: case OPcolon2:
950: { vec_t Gl,Kl,Gr,Kr;
951:
952: aecpelem(&Gl,&Kl,n->E1);
953: aecpelem(&Gr,&Kr,n->E2);
954:
955: /* KILL |= Kl | Kr */
956: /* GEN =((GEN - Kl) | Gl) & */
957: /* ((GEN - Kr) | Gr) */
958:
959: vec_orass(KILL,Kl);
960: vec_orass(KILL,Kr);
961:
962: vec_sub(Kl,GEN,Kl);
963: vec_sub(Kr,GEN,Kr);
964: vec_orass(Kl,Gl);
965: vec_orass(Kr,Gr);
966: vec_and(GEN,Kl,Kr);
967:
968: vec_free(Gl);
969: vec_free(Gr);
970: vec_free(Kl);
971: vec_free(Kr);
972: break;
973: }
974: case OPandand:
975: case OPoror:
976: { vec_t Gr,Kr;
977:
978: accumaecpx(n->E1);
979: aecpelem(&Gr,&Kr,n->E2);
980:
981: if (!el_noreturn(n->E2))
982: {
983: // KILL |= Kr
984: // GEN &= (GEN - Kr) | Gr
985:
986: vec_orass(KILL,Kr);
987: vec_sub(Kr,GEN,Kr);
988: vec_orass(Kr,Gr);
989: vec_andass(GEN,Kr);
990: }
991:
992: vec_free(Gr);
993: vec_free(Kr);
994: break;
995: }
996: case OPasm:
997: assert(!n->Eexp); // no ASM available expressions
998: vec_set(KILL); // KILL everything
999: vec_clear(GEN); // GEN nothing
1000: return;
1001:
1002: #if TX86
1003: case OPeq:
1004: case OPstreq:
1005: accumaecpx(n->E2);
1006: case OPnegass:
1007: accumaecpx(n->E1);
1008: t = Elvalue(n);
1009: break;
1010: #endif
1011:
1012: case OPvptrfptr:
1013: case OPcvptrfptr: // if vptr access
1014: if ((flowxx == AE) && n->Eexp)
1015: vec_orass(KILL,vptrkill); // kill all other vptr accesses
1016: break;
1017:
1018: default:
1019: if (OTunary(op))
warning C6385: Invalid data: accessing 'unsigned char const * const optab1', the readable size is '183' bytes, but '1145' bytes might be read: Lines: 927, 928, 930, 932, 934, 1018, 1019
1020: {
1021: #if TX86
1022: case OPind: // most common unary operator
1023: accumaecpx(n->E1);
1024: #ifdef DEBUG
1025: assert(!OTassign(op));
1026: #endif
1027: #else
1028: accumaecpx(n->E1);
1029: if (OTassign(op)) // if assignment operator
1030: t = Elvalue(n);
1031: #endif
1032: }
1033: else if (OTbinary(op))
1034: {
1035: if (OTrtol(op) && ERTOL(n))
1036: { accumaecpx(n->E2);
1037: accumaecpx(n->E1);
1038: }
1039: else
1040: { accumaecpx(n->E1);
1041: accumaecpx(n->E2);
1042: }
1043: if (OTassign(op)) // if assignment operator
1044: t = Elvalue(n);
1045: }
1046: break;
1047: }
1048:
1049:
1050: /* Do copy propagation stuff first */
1051:
1052: if (flowxx == CP)
1053: {
1054: if (!OTdef(op)) /* if not def elem */
1055: return;
1056: if (!Eunambig(n)) /* if ambiguous def elem */
1057: { vec_orass(KILL,defkill);
1058: vec_subass(GEN,defkill);
1059: }
1060: else /* unambiguous def elem */
1061: { symbol *s;
1062:
1063: assert(t->Eoper == OPvar);
1064: s = t->EV.sp.Vsym; // ptr to var being def'd
1065: for (i = 1; i < exptop; i++) /* for each ae elem */
1066: { register elem *e = expnod[i];
1067:
1068: /* If it could be changed by the definition, */
1069: /* set bit in KILL. */
1070:
1071: if (e->E1->EV.sp.Vsym == s || e->E2->EV.sp.Vsym == s)
1072: vec_setclear(i,KILL,GEN);
1073: }
1074: }
1075:
1076: /* GEN CP elems */
1077: if (n->Eexp)
1078: { unsigned b = n->Eexp;
1079:
1080: vec_setclear(b,GEN,KILL);
1081: }
1082:
1083: return;
1084: }
1085:
1086: /* Else Available Expression stuff */
1087:
1088: if (n->Eexp)
1089: { unsigned b = n->Eexp; // add elem to GEN
1090:
1091: assert(expnod[b] == n);
1092: vec_setclear(b,GEN,KILL);
1093: }
1094: else if (OTdef(op)) /* else if definition elem */
warning C6385: Invalid data: accessing 'unsigned char const * const optab2', the readable size is '183' bytes, but '1145' bytes might be read: Lines: 927, 928, 930, 932, 934, 1018, 1019, 1022, 1023, 1052, 1088, 1094
1095: {
1096: if (!Eunambig(n)) /* if ambiguous def elem */
1097: { vec_orass(KILL,defkill);
1098: vec_subass(GEN,defkill);
1099: if (OTcalldef(op))
1100: { vec_orass(KILL,vptrkill);
1101: vec_subass(GEN,vptrkill);
1102: }
1103: }
1104: else /* unambiguous def elem */
1105: { symbol *s;
1106:
1107: assert(t->Eoper == OPvar);
1108: s = t->EV.sp.Vsym; /* idx of var being def'd */
1109: if (!(s->Sflags & SFLunambig))
1110: { vec_orass(KILL,starkill); /* kill all 'starred' refs */
1111: vec_subass(GEN,starkill);
1112: }
1113: for (i = 1; i < exptop; i++) /* for each ae elem */
1114: { elem *e = expnod[i];
1115: int eop = e->Eoper;
1116:
1117: /* If it could be changed by the definition, */
1118: /* set bit in KILL. */
1119: if (eop == OPvar)
1120: { if (e->EV.sp.Vsym != s)
1121: continue;
1122: }
1123: else if (OTunary(eop))
1124: { if (!vec_testbit(e->E1->Eexp,KILL))
1125: continue;
1126: }
1127: else if (OTbinary(eop))
1128: { if (!vec_testbit(e->E1->Eexp,KILL) &&
1129: !vec_testbit(e->E2->Eexp,KILL))
1130: continue;
1131: }
1132: else
1133: continue;
1134:
1135: vec_setclear(i,KILL,GEN);
1136: }
1137: }
1138:
1139: /* GEN the lvalue of an assignment operator */
1140: if (OTassign(op) && !OTpost(op) && t->Eexp)
warning C6001: Using uninitialized memory 't': Lines: 927, 928, 930, 932, 934, 948, 949, 950, 952, 953, 959, 960, 962, 963, 964, 965, 966, 968, 969, 970, 971, 1052, 1088, 1094, 1096, 1097, 1098, 1099, 1140
1141: { unsigned b = t->Eexp;
1142:
1143: vec_setclear(b,GEN,KILL);
1144: }
1145: }
1146: }
1147:
1148: /************************* LIVE VARIABLES **********************/
1149:
1150: /*********************************
1151: * Do live variable analysis (LVs).
1152: * A variable is 'live' at some point if there is a
1153: * subsequent use of it before a redefinition.
1154: * Binlv = the set of variables live at the beginning of B.
1155: * Boutlv = the set of variables live at the end of B.
1156: * Bgen = set of variables used before any definition in B.
1157: * Bkill = set of variables unambiguously defined before
1158: * any use in B.
1159: * Note that Bgen & Bkill = 0.
1160: */
1161:
1162: void flowlv()
1163: { vec_t tmp,livexit;
1164: register unsigned i;
1165: bool anychng;
1166: unsigned cnt;
1167:
1168: lvgenkill(); /* compute Bgen and Bkill for LVs. */
1169: //assert(globsym.top); /* should be at least some symbols */
1170:
1171: /* Create a vector of all the variables that are live on exit */
1172: /* from the function. */
1173:
1174: livexit = vec_calloc(globsym.top);
1175: for (i = 0; i < globsym.top; i++)
warning C4018: '<' : signed/unsigned mismatch
1176: { if (globsym.tab[i]->Sflags & SFLlivexit)
1177: vec_setbit(i,livexit);
1178: }
1179:
1180: /* The transfer equation is: */
1181: /* Bin = (Bout - Bkill) | Bgen */
1182: /* Bout = union of Bin of all successors to B. */
1183: /* Using Ullman's algorithm: */
1184:
1185: for (i = 0; i < dfotop; i++) /* for each block B */
1186: {
1187: vec_copy(dfo[i]->Binlv,dfo[i]->Bgen); /* Binlv = Bgen */
1188: }
1189:
1190: tmp = vec_calloc(globsym.top);
1191: cnt = 0;
1192: do
1193: { anychng = FALSE;
1194:
1195: /* For each block B in reverse DFO order */
1196: for (i = dfotop; i--;)
1197: { register block *b = dfo[i];
1198: register list_t bl = b->Bsucc;
1199:
1200: /* Bout = union of Bins of all successors to B. */
1201: if (bl)
1202: { vec_copy(b->Boutlv,list_block(bl)->Binlv);
1203: while ((bl = list_next(bl)) != NULL)
1204: { vec_orass(b->Boutlv,list_block(bl)->Binlv);
1205: }
1206: }
1207: else /* no successors, Boutlv = livexit */
1208: { //assert(b->BC==BCret||b->BC==BCretexp||b->BC==BCexit);
1209: vec_copy(b->Boutlv,livexit);
1210: }
1211:
1212: /* Bin = (Bout - Bkill) | Bgen */
1213: vec_sub(tmp,b->Boutlv,b->Bkill);
1214: vec_orass(tmp,b->Bgen);
1215: if (!anychng)
1216: anychng = !vec_equal(tmp,b->Binlv);
1217: vec_copy(b->Binlv,tmp);
1218: }
1219: cnt++;
1220: assert(cnt < 50);
1221: } while (anychng);
1222: vec_free(tmp);
1223: vec_free(livexit);
1224: #if 0
1225: dbg_printf("Live variables\n");
1226: for (i = 0; i < dfotop; i++)
1227: { dbg_printf("B%d IN\t",i);
1228: vec_println(dfo[i]->Binlv);
1229: dbg_printf("B%d GEN\t",i);
1230: vec_println(dfo[i]->Bgen);
1231: dbg_printf(" KILL\t");
1232: vec_println(dfo[i]->Bkill);
1233: dbg_printf(" OUT\t");
1234: vec_println(dfo[i]->Boutlv);
1235: }
1236: #endif
1237: }
1238:
1239: /***********************************
1240: * Compute Bgen and Bkill for LVs.
1241: * Allocate Binlv and Boutlv vectors.
1242: */
1243:
1244: STATIC void lvgenkill()
1245: { unsigned i;
1246:
1247: /* Compute ambigsym, a vector of all variables that could be */
1248: /* referenced by a *e or a call. */
1249:
1250: assert(ambigsym == NULL);
1251: ambigsym = vec_calloc(globsym.top);
1252: for (i = 0; i < globsym.top; i++)
warning C4018: '<' : signed/unsigned mismatch
1253: if (!(globsym.tab[i]->Sflags & SFLunambig))
1254: vec_setbit(i,ambigsym);
1255:
1256: for (i = 0; i < dfotop; i++)
1257: { block *b = dfo[i];
1258:
1259: vec_free(b->Bgen);
1260: vec_free(b->Bkill);
1261: lvelem(&(b->Bgen),&(b->Bkill),b->Belem);
1262: if (b->BC == BCasm)
1263: { vec_set(b->Bgen);
1264: vec_clear(b->Bkill);
1265: }
1266:
1267: vec_free(b->Binlv);
1268: vec_free(b->Boutlv);
1269: b->Binlv = vec_calloc(globsym.top);
1270: b->Boutlv = vec_calloc(globsym.top);
1271: }
1272:
1273: vec_free(ambigsym); /* dump any existing one */
1274: ambigsym = NULL;
1275: }
1276:
1277: /*****************************
1278: * Allocate and compute KILL and GEN for live variables.
1279: */
1280:
1281: STATIC void lvelem(vec_t *pgen,vec_t *pkill,elem *n)
1282: {
1283: *pgen = vec_calloc(globsym.top);
1284: *pkill = vec_calloc(globsym.top);
1285: if (n && globsym.top)
1286: accumlv(*pgen,*pkill,n);
1287: }
1288:
1289: /**********************************************
1290: * Accumulate GEN and KILL sets for LVs for this elem.
1291: */
1292:
1293: STATIC void accumlv(vec_t GEN,vec_t KILL,elem *n)
warning C6244: Local declaration of 'GEN' hides previous declaration at line '910' of 'c:\projects\extern\d\dmd\src\backend\gflow.c'
warning C6244: Local declaration of 'KILL' hides previous declaration at line '911' of 'c:\projects\extern\d\dmd\src\backend\gflow.c'
1294: { vec_t Gl,Kl,Gr,Kr;
1295: register unsigned op;
1296: elem *t;
1297:
1298: assert(GEN && KILL && n);
1299:
1300: while (1)
1301: { elem_debug(n);
1302: op = n->Eoper;
1303: switch (op)
1304: {
1305: case OPvar:
1306: if (symbol_isintab(n->EV.sp.Vsym))
1307: { SYMIDX si = n->EV.sp.Vsym->Ssymnum;
1308:
1309: assert((unsigned)si < globsym.top);
warning C4018: '<' : signed/unsigned mismatch
1310: if (!vec_testbit(si,KILL)) // if not in KILL
1311: vec_setbit(si,GEN); // put in GEN
1312: }
1313: break;
1314:
1315: case OPcolon:
1316: case OPcolon2:
1317: lvelem(&Gl,&Kl,n->E1);
1318: lvelem(&Gr,&Kr,n->E2);
1319:
1320: /* GEN |= (Gl | Gr) - KILL */
1321: /* KILL |= (Kl & Kr) - GEN */
1322:
1323: vec_orass(Gl,Gr);
1324: vec_subass(Gl,KILL);
1325: vec_orass(GEN,Gl);
1326: vec_andass(Kl,Kr);
1327: vec_subass(Kl,GEN);
1328: vec_orass(KILL,Kl);
1329:
1330: vec_free(Gl);
1331: vec_free(Gr);
1332: vec_free(Kl);
1333: vec_free(Kr);
1334: break;
1335:
1336: case OPandand:
1337: case OPoror:
1338: accumlv(GEN,KILL,n->E1);
1339: lvelem(&Gr,&Kr,n->E2);
1340:
1341: /* GEN |= Gr - KILL */
1342: /* KILL |= 0 */
1343:
1344: vec_subass(Gr,KILL);
1345: vec_orass(GEN,Gr);
1346:
1347: vec_free(Gr);
1348: vec_free(Kr);
1349: break;
1350:
1351: case OPasm:
1352: vec_set(GEN); /* GEN everything not already KILLed */
1353: vec_subass(GEN,KILL);
1354: break;
1355:
1356: case OPnewarray:
1357: case OPmultinewarray:
1358: accumlv(GEN,KILL,n->E1);
1359: accumlv(GEN,KILL,n->E2);
1360: goto L1;
1361:
1362: case OPcall:
1363: case OPcallns:
1364: #if TX86
1365: case OPstrcpy:
1366: case OPmemcpy:
1367: case OPmemset:
1368: #endif
1369: #ifdef DEBUG
1370: assert(OTrtol(op));
1371: #endif
1372: accumlv(GEN,KILL,n->E2);
1373: accumlv(GEN,KILL,n->E1);
1374: goto L1;
1375:
1376: #if TX86
1377: case OPstrcat:
1378: #ifdef DEBUG
1379: assert(!OTrtol(op));
1380: #endif
1381: accumlv(GEN,KILL,n->E1);
1382: accumlv(GEN,KILL,n->E2);
1383: #endif
1384: L1:
1385: vec_orass(GEN,ambigsym);
1386: vec_subass(GEN,KILL);
1387: break;
1388:
1389: case OPeq:
1390: /* Avoid GENing the lvalue of an = */
1391: accumlv(GEN,KILL,n->E2);
1392: t = Elvalue(n);
1393: if (t->Eoper != OPvar)
1394: accumlv(GEN,KILL,t->E1);
1395: else /* unambiguous assignment */
1396: { symbol *s;
1397:
1398: s = t->EV.sp.Vsym;
1399: symbol_debug(s);
1400:
1401: /* if not GENed already, KILL it */
1402: if (symbol_isintab(s) &&
1403: !vec_testbit(s->Ssymnum,GEN) &&
1404: /* assignments to aggregates are */
1405: /* not unambiguous */
1406: !tyaggregate(s->ty()) &&
1407: t->EV.sp.Voffset == 0 &&
1408: tysize(t->Ety) == tysize(s->ty())
1409: )
1410: { assert((unsigned)s->Ssymnum < globsym.top);
warning C4018: '<' : signed/unsigned mismatch
1411: vec_setbit(s->Ssymnum,KILL);
1412: }
1413: }
1414: break;
1415:
1416: case OPind:
1417: case OPucall:
1418: case OPucallns:
1419: case OPstrlen:
1420: accumlv(GEN,KILL,n->E1);
1421:
1422: /* If it was a *p elem, set bits in GEN for all symbols */
1423: /* it could have referenced, but only if bits in KILL */
1424: /* are not already set. */
1425:
1426: vec_orass(GEN,ambigsym);
1427: vec_subass(GEN,KILL);
1428: break;
1429:
1430: default:
1431: if (OTunary(op))
1432: { n = n->E1;
1433: continue;
1434: }
1435: else if (OTrtol(op) && ERTOL(n))
1436: {
1437: accumlv(GEN,KILL,n->E2);
1438:
1439: /* Note that lvalues of op=,i++,i-- elems */
1440: /* are GENed. */
1441: n = n->E1;
1442: continue;
1443: }
1444: else if (OTbinary(op))
1445: {
1446: accumlv(GEN,KILL,n->E1);
1447: n = n->E2;
1448: continue;
1449: }
1450: break;
1451: }
1452: break;
1453: }
1454: }
1455:
1456: /********************* VERY BUSY EXPRESSIONS ********************/
1457:
1458: /**********************************************
1459: * Compute very busy expressions(VBEs).
1460: * That is,expressions that are evaluated along
1461: * separate paths.
1462: * Bin = the set of VBEs at the beginning of B.
1463: * Bout = the set of VBEs at the end of B.
1464: * Bgen = set of expressions X+Y such that X+Y is
1465: * evaluated before any def of X or Y.
1466: * Bkill = set of expressions X+Y such that X or Y could
1467: * be defined before X+Y is computed.
1468: * Note that gen and kill are mutually exclusive.
1469: */
1470:
1471: void flowvbe()
1472: { vec_t tmp;
1473: unsigned i;
1474: bool anychng;
1475:
1476: flowxx = VBE;
1477: aecpgenkill(); /* compute Bgen and Bkill for VBEs */
1478: if (exptop <= 1) /* if no candidates for VBEs */
1479: return;
1480:
1481: /*for (i = 0; i < exptop; i++)
1482: dbg_printf("expnod[%d] = 0x%x\n",i,expnod[i]);*/
1483:
1484: /* The transfer equation is: */
1485: /* Bout = & Bin(all successors S of B) */
1486: /* Bin =(Bout - Bkill) | Bgen */
1487: /* Using Ullman's algorithm: */
1488:
1489: /*dbg_printf("defkill = "); vec_println(defkill);
1490: dbg_printf("starkill = "); vec_println(starkill);*/
1491:
1492: for (i = 0; i < dfotop; i++)
1493: { block *b = dfo[i];
1494:
1495: /*dbg_printf("block 0x%x\n",b);
1496: dbg_printf("Bgen = "); vec_println(b->Bgen);
1497: dbg_printf("Bkill = "); vec_println(b->Bkill);*/
1498:
1499: if (b->BC == BCret || b->BC == BCretexp || b->BC == BCexit)
1500: vec_clear(b->Bout);
1501: else
1502: vec_set(b->Bout);
1503:
1504: /* Bin = (Bout - Bkill) | Bgen */
1505: vec_sub(b->Bin,b->Bout,b->Bkill);
1506: vec_orass(b->Bin,b->Bgen);
1507: }
1508:
1509: tmp = vec_calloc(exptop);
1510: do
1511: { anychng = FALSE;
1512:
1513: /* for all blocks except return blocks in reverse dfo order */
1514: for (i = dfotop; i--;)
1515: { block *b = dfo[i];
1516: list_t bl;
1517:
1518: if (b->BC == BCret || b->BC == BCretexp || b->BC == BCexit)
1519: continue;
1520:
1521: /* Bout = & of Bin of all successors */
1522: bl = b->Bsucc;
1523: assert(bl); /* must have successors */
1524: vec_copy(b->Bout,list_block(bl)->Bin);
1525: while (TRUE)
1526: { bl = list_next(bl);
1527: if (!bl)
1528: break;
1529: vec_andass(b->Bout,list_block(bl)->Bin);
1530: }
1531:
1532: /* Bin = (Bout - Bkill) | Bgen */
1533: vec_sub(tmp,b->Bout,b->Bkill);
1534: vec_orass(tmp,b->Bgen);
1535: if (!anychng)
1536: anychng = !vec_equal(tmp,b->Bin);
1537: vec_copy(b->Bin,tmp);
1538: }
1539: } while (anychng); /* while any changes occurred to any Bin */
1540: vec_free(tmp);
1541: }
1542:
1543: /*************************************
1544: * Accumulate GEN and KILL sets for VBEs for this elem.
1545: */
1546:
1547: STATIC void accumvbe(vec_t GEN,vec_t KILL,elem *n)
warning C6244: Local declaration of 'GEN' hides previous declaration at line '910' of 'c:\projects\extern\d\dmd\src\backend\gflow.c'
warning C6244: Local declaration of 'KILL' hides previous declaration at line '911' of 'c:\projects\extern\d\dmd\src\backend\gflow.c'
1548: { register unsigned op,i;
1549: register elem *t;
1550:
1551: assert(GEN && KILL && n);
1552: op = n->Eoper;
1553:
1554: switch (op)
1555: {
1556: case OPcolon:
1557: case OPcolon2:
1558: { vec_t Gl,Gr,Kl,Kr;
1559:
1560: aecpelem(&Gl,&Kl,n->E1);
1561: aecpelem(&Gr,&Kr,n->E2);
1562:
1563: /* GEN |=((Gr - Kl) | (Gl - Kr)) - KILL */
1564: vec_subass(Gr,Kl);
1565: vec_subass(Gl,Kr);
1566: vec_orass(Gr,Gl);
1567: vec_subass(Gr,KILL);
1568: vec_orass(GEN,Gr);
1569:
1570: /* KILL |=(Kl | Kr) - GEN */
1571: vec_orass(Kl,Kr);
1572: vec_subass(Kl,GEN);
1573: vec_orass(KILL,Kl);
1574:
1575: vec_free(Gl);
1576: vec_free(Kl);
1577: vec_free(Gr);
1578: vec_free(Kr);
1579: break;
1580: }
1581:
1582: case OPandand:
1583: case OPoror:
1584: accumvbe(GEN,KILL,n->E1);
1585: /* WARNING: just so happens that it works this way. */
1586: /* Be careful about (b+c)||(b+c) being VBEs, only the */
1587: /* first should be GENed. Doing things this way instead */
1588: /* of (GEN |= Gr - KILL) and (KILL |= Kr - GEN) will */
1589: /* ensure this. */
1590: accumvbe(GEN,KILL,n->E2);
1591: break;
1592:
1593: case OPnegass:
1594: t = n->E1;
1595: if (t->Eoper != OPvar)
1596: { accumvbe(GEN,KILL,t->E1);
1597: if (OTbinary(t->Eoper))
1598: accumvbe(GEN,KILL,t->E2);
1599: }
1600: break;
1601:
1602: case OPnewarray:
1603: case OPmultinewarray:
1604: accumvbe(GEN,KILL,n->E1);
1605: accumvbe(GEN,KILL,n->E2);
1606: break;
1607:
1608: case OPcall:
1609: case OPcallns:
1610: accumvbe(GEN,KILL,n->E2);
1611: case OPucall:
1612: case OPucallns:
1613: t = n->E1;
1614: // Do not VBE indirect function calls
1615: if (t->Eoper == OPind)
1616: t = t->E1;
1617: accumvbe(GEN,KILL,t);
1618: break;
1619:
1620: case OPasm: // if the dreaded OPasm elem
1621: vec_set(KILL); // KILL everything
1622: vec_subass(KILL,GEN); // except for GENed stuff
1623: return;
1624:
1625: default:
1626: if (OTunary(op))
1627: {
1628: t = n->E1;
1629: accumvbe(GEN,KILL,t);
1630: }
1631: else if (ERTOL(n))
1632: { accumvbe(GEN,KILL,n->E2);
1633: t = n->E1;
1634: // do not GEN the lvalue of an assignment op
1635: if (OTassign(op))
1636: { t = Elvalue(n);
1637: if (t->Eoper != OPvar)
1638: { accumvbe(GEN,KILL,t->E1);
1639: if (OTbinary(t->Eoper))
1640: accumvbe(GEN,KILL,t->E2);
1641: }
1642: }
1643: else
1644: accumvbe(GEN,KILL,t);
1645: }
1646: else if (OTbinary(op))
1647: {
1648: /* do not GEN the lvalue of an assignment op */
1649: if (OTassign(op))
1650: { t = Elvalue(n);
1651: if (t->Eoper != OPvar)
1652: { accumvbe(GEN,KILL,t->E1);
1653: if (OTbinary(t->Eoper))
1654: accumvbe(GEN,KILL,t->E2);
1655: }
1656: }
1657: else
1658: accumvbe(GEN,KILL,n->E1);
1659: accumvbe(GEN,KILL,n->E2);
1660: }
1661: break;
1662: }
1663:
1664: if (n->Eexp) /* if a vbe elem */
1665: { int ne = n->Eexp;
1666:
1667: assert(expnod[ne] == n);
1668: if (!vec_testbit(ne,KILL)) /* if not already KILLed */
1669: {
1670: /* GEN this expression only if it hasn't */
1671: /* already been GENed in this block. */
1672: /* (Don't GEN common subexpressions.) */
1673: if (vec_testbit(ne,GEN))
1674: vec_clearbit(ne,GEN);
1675: else
1676: { vec_setbit(ne,GEN); /* GEN this expression */
1677: /* GEN all identical expressions */
1678: /* (operators only, as there is no point */
1679: /* to hoisting out variables and constants) */
1680: if (!OTleaf(op))
1681: { for (i = 1; i < exptop; i++)
1682: { if (op == expnod[i]->Eoper &&
1683: i != ne &&
1684: el_match(n,expnod[i]))
1685: { vec_setbit(i,GEN);
1686: assert(!vec_testbit(i,KILL));
1687: }
1688: }
1689: }
1690: }
1691: }
1692: if (op == OPvptrfptr || op == OPcvptrfptr)
1693: {
1694: vec_orass(KILL,vptrkill); /* KILL all vptr accesses */
1695: vec_subass(KILL,GEN); /* except for GENed stuff */
1696: }
1697: }
1698: else if (OTdef(op)) /* if definition elem */
1699: {
1700: if (!Eunambig(n)) /* if ambiguous definition */
1701: { vec_orass(KILL,defkill);
1702: if (OTcalldef(op))
1703: vec_orass(KILL,vptrkill);
1704: }
1705: else /* unambiguous definition */
1706: { symbol *s;
1707:
1708: assert(t->Eoper == OPvar);
1709: s = t->EV.sp.Vsym; // ptr to var being def'd
1710: if (!(s->Sflags & SFLunambig))
1711: vec_orass(KILL,starkill);/* kill all 'starred' refs */
1712: for (i = 1; i < exptop; i++) /* for each vbe elem */
1713: { elem *e = expnod[i];
1714: unsigned eop = e->Eoper;
1715:
1716: /* If it could be changed by the definition, */
1717: /* set bit in KILL. */
1718: if (eop == OPvar)
1719: { if (e->EV.sp.Vsym != s)
1720: continue;
1721: }
1722: else if (OTbinary(eop))
1723: { if (!vec_testbit(e->E1->Eexp,KILL) &&
1724: !vec_testbit(e->E2->Eexp,KILL))
1725: continue;
1726: }
1727: else if (OTunary(eop))
1728: { if (!vec_testbit(e->E1->Eexp,KILL))
1729: continue;
1730: }
1731: else /* OPconst or OPrelconst or OPstring or OPhstring */
1732: continue;
1733:
1734: vec_setbit(i,KILL); // KILL it
1735: } /* for */
1736: } /* if */
1737: vec_subass(KILL,GEN);
1738: } /* if */
1739: }
1740:
1741: #endif
1742: