1: // Copyright (C) 1993-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 !DEMO && !SPP
14:
15: #include <stdio.h>
16: #include <stdlib.h>
17: #include <time.h>
18:
19: #if __sun&&__SVR4
20: #include <alloca.h>
21: #elif _MSC_VER
22: #include <malloc.h>
23: #endif
24:
25: #include "cc.h"
26: #include "global.h"
27: #include "el.h"
28: #include "go.h"
29: #include "type.h"
30: #include "oper.h"
31:
32: static char __file__[] = __FILE__; /* for tassert.h */
33: #include "tassert.h"
34:
35: typedef struct loc_t
36: {
37: elem *e;
38: int flags;
39: # define LFvolatile 1 // contains volatile refs or defs
40: # define LFambigref 2 // references ambiguous data
41: # define LFambigdef 4 // defines ambiguous data
42: # define LFsymref 8 // reference to symbol s
43: # define LFsymdef 0x10 // definition of symbol s
44: # define LFunambigref 0x20 // references unambiguous data other than s
45: # define LFunambigdef 0x40 // defines unambiguous data other than s
46: #if TX86
47: # define LFinp 0x80 // input from I/O port
48: # define LFoutp 0x100 // output to I/O port
49: #endif
50: # define LFfloat 0x200 // sets float flags and/or depends on
51: // floating point settings
52: } loc_t;
53:
54: static loc_t *loctab;
55: static unsigned locmax;
56: static unsigned loctop;
57:
58: STATIC void local_exp(elem *e,int goal);
59: STATIC int local_chkrem(elem *e,elem *eu);
60: STATIC void local_ins(elem *e);
61: STATIC void local_rem(unsigned u);
62: STATIC int local_getflags(elem *e,symbol *s);
63: STATIC void local_remove(int flags);
64: STATIC void local_ambigref(void);
65: STATIC void local_ambigdef(void);
66: STATIC void local_symref(symbol *s);
67: STATIC void local_symdef(symbol *s);
68:
69: #if !TX86
70: static bool fcall_seen = FALSE;
71: #endif
72:
73: ///////////////////////////////
74: // This optimization attempts to replace sequences like:
75: // x = func();
76: // y = 3;
77: // z = x + 5;
78: // with:
79: // y = 3;
80: // z = (x = func()) + 5;
81: // In other words, we attempt to localize expressions by moving them
82: // as near as we can to where they are used. This should minimize
83: // temporary generation and register usage.
84:
85: void localize()
86: { block *b;
87:
88: cmes("localize()\n");
89:
90: // Table should not get any larger than the symbol table
91: locmax = globsym.symmax;
92: loctab = (loc_t *) alloca(locmax * sizeof(*loctab));
warning C6255: _alloca indicates failure by raising a stack overflow exception. Consider using _malloca instead
93:
94: for (b = startblock; b; b = b->Bnext) /* for each block */
95: {
96: loctop = 0; // start over for each block
97: if (b->Belem &&
98: /* Overly broad way to account for the case:
99: * try
100: * { i++;
101: * foo(); // throws exception
102: * i++; // shouldn't combine previous i++ with this one
103: * }
104: */
105: !b->Btry)
106: {
107: local_exp(b->Belem,0);
108: }
109: }
110: }
111:
112: //////////////////////////////////////
113: // Input:
114: // goal !=0 if we want the result of the expression
115: //
116:
117: STATIC void local_exp(elem *e,int goal)
118: { symbol *s;
119: unsigned u;
120: elem *e1;
121: int op1;
122:
123: Loop:
124: elem_debug(e);
125: int op = e->Eoper;
126: switch (op)
127: { case OPcomma:
128: local_exp(e->E1,0);
129: e = e->E2;
130: goto Loop;
131:
132: case OPandand:
133: case OPoror:
134: local_exp(e->E1,1);
135: loctop = 0; // we can do better than this, fix later
136: break;
137:
138: case OPcolon:
139: case OPcolon2:
140: loctop = 0; // we can do better than this, fix later
141: break;
142:
143: case OPinfo:
144: if (e->E1->Eoper == OPmark)
145: { loctop = 0;
146: e = e->E2;
147: goto Loop;
148: }
149: goto case_bin;
150:
151: case OPdtor:
152: case OPctor:
153: case OPdctor:
154: loctop = 0; // don't move expressions across ctor/dtor
155: break; // boundaries, it would goof up EH cleanup
156:
157: case OPddtor:
158: loctop = 0; // don't move expressions across ctor/dtor
159: // boundaries, it would goof up EH cleanup
160: local_exp(e->E1,0);
161: loctop = 0;
162: break;
163:
164: case OPeq:
165: case OPstreq:
166: e1 = e->E1;
167: local_exp(e->E2,1);
168: if (e1->Eoper == OPvar)
169: { s = e1->EV.sp.Vsym;
170: if (s->Sflags & SFLunambig)
171: { local_symdef(s);
172: #if TX86
173: if (!goal)
174: #else
175: if (!(goal || fcall_seen))
176: // do not localize if there is a function call on the rhs
177: #endif
178: local_ins(e);
179: }
180: else
181: local_ambigdef();
182: }
183: else
184: {
185: assert(!OTleaf(e1->Eoper));
186: local_exp(e1->E1,1);
187: if (OTbinary(e1->Eoper))
188: local_exp(e1->E2,1);
189: local_ambigdef();
190: }
191: #if !TX86
192: e1->Nflags |= (e->E2->Nflags & NFLfcall);
193: #endif
194: break;
195:
196: case OPpostinc:
197: case OPpostdec:
198: case OPaddass:
199: case OPminass:
200: case OPmulass:
201: case OPdivass:
202: case OPmodass:
203: case OPashrass:
204: case OPshrass:
205: case OPshlass:
206: case OPandass:
207: case OPxorass:
208: case OPorass:
209: if (ERTOL(e))
210: { local_exp(e->E2,1);
211: case OPnegass:
212: e1 = e->E1;
213: op1 = e1->Eoper;
214: if (op1 != OPvar)
215: {
216: local_exp(e1->E1,1);
217: if (OTbinary(op1))
218: local_exp(e1->E2,1);
219: }
220: else if (loctop && (op == OPaddass || op == OPxorass))
221: { unsigned u;
warning C6246: Local declaration of 'u' hides declaration of the same name in outer scope. For additional information, see previous declaration at line '119' of 'c:\projects\extern\d\dmd\src\backend\glocal.c': Lines: 119
222:
223: s = e1->EV.sp.Vsym;
224: for (u = 0; u < loctop; u++)
225: { elem *em;
226:
227: em = loctab[u].e;
228: if (em->Eoper == op &&
229: em->E1->EV.sp.Vsym == s &&
230: tysize(em->Ety) == tysize(e1->Ety) &&
231: em->E1->EV.sp.Voffset == e1->EV.sp.Voffset &&
232: !el_sideeffect(em->E2)
233: )
234: { // Change (x += a),(x += b) to
235: // (x + a),(x += a + b)
236: changes++;
237: e->E2 = el_bin(opeqtoop(op),e->E2->Ety,em->E2,e->E2);
238: em->Eoper = opeqtoop(op);
239: em->E2 = el_copytree(em->E2);
240: local_rem(u);
241: #ifdef DEBUG
242: if (debugc)
243: { dbg_printf("Combined equation ");
244: WReqn(e);
245: dbg_printf(";\n");
246: e = doptelem(e,GOALvalue);
247: }
248: #endif
249:
250: break;
251: }
252: }
253: }
254: }
255: else
256: {
257: e1 = e->E1;
258: op1 = e1->Eoper;
259: if (op1 != OPvar)
260: {
261: local_exp(e1->E1,1);
262: if (OTbinary(op1))
263: local_exp(e1->E2,1);
264: }
265: if (loctop)
266: { if (op1 == OPvar &&
267: ((s = e1->EV.sp.Vsym)->Sflags & SFLunambig))
268: local_symref(s);
269: else
270: local_ambigref();
271: }
272: local_exp(e->E2,1);
273: }
274: if (op1 == OPvar &&
275: ((s = e1->EV.sp.Vsym)->Sflags & SFLunambig))
276: { local_symref(s);
277: local_symdef(s);
278: if (op == OPaddass || op == OPxorass)
279: local_ins(e);
280: }
281: else if (loctop)
282: {
283: local_remove(LFambigdef | LFambigref);
284: }
285: break;
286: #if TX86
287: case OPstrlen:
288: #endif
289: case OPind:
290: local_exp(e->E1,1);
291: local_ambigref();
292: break;
293:
294: case OPnewarray:
295: case OPmultinewarray:
296: local_exp(e->E1,1);
297: local_exp(e->E2,1);
298: goto Lrd;
299:
300: #if TX86
301: case OPstrcmp:
302: case OPmemcmp:
303: case OPbt:
304: case OParray:
305: case OPfield:
306: local_exp(e->E1,1);
307: local_exp(e->E2,1);
308: local_ambigref();
309: break;
310:
311: case OPstrcpy:
312: case OPmemcpy:
313: case OPstrcat:
314: case OPcall:
315: case OPcallns:
316: local_exp(e->E2,1);
317: case OPstrctor:
318: case OPucall:
319: case OPucallns:
320: local_exp(e->E1,1);
321: goto Lrd;
322:
323: case OPbtc:
324: case OPbtr:
325: case OPbts:
326: local_exp(e->E1,1);
327: local_exp(e->E2,1);
328: goto Lrd;
329: #else
330: case OPcall:
331: case OPcallns:
332: {
333: local_exp(e->E2,1);
334: }
335: case OPstrctor:
336: case OPucall:
337: case OPucallns:
338: fcall_seen = FALSE;
339: local_exp(e->E1,1);
340:
341: e->Nflags |= NFLfcall;
342: fcall_seen = TRUE;
343:
344: #endif
345: case OPasm:
346: Lrd:
347: local_remove(LFfloat | LFambigref | LFambigdef);
348: break;
349:
350: #if TX86
351: case OPmemset:
352: local_exp(e->E2,1);
353: if (e->E1->Eoper == OPvar)
354: {
355: /* Don't want to rearrange (p = get(); p memset 0;)
356: * as elemxxx() will rearrange it back.
357: */
358: s = e->E1->EV.sp.Vsym;
359: if (s->Sflags & SFLunambig)
360: local_symref(s);
361: else
362: local_ambigref(); // ambiguous reference
363: }
364: else
365: local_exp(e->E1,1);
366: local_ambigdef();
367: break;
368: #endif
369:
370: case OPvar:
371: s = e->EV.sp.Vsym;
372: if (loctop)
373: { unsigned u;
warning C6246: Local declaration of 'u' hides declaration of the same name in outer scope. For additional information, see previous declaration at line '119' of 'c:\projects\extern\d\dmd\src\backend\glocal.c': Lines: 119
374:
375: // If potential candidate for replacement
376: if (s->Sflags & SFLunambig)
377: {
378: for (u = 0; u < loctop; u++)
379: { elem *em;
380:
381: em = loctab[u].e;
382: if (em->E1->EV.sp.Vsym == s &&
383: (em->Eoper == OPeq || em->Eoper == OPstreq)
384: #if !TX86
385: && !(em->Nflags & NFLfcall)
386: #endif
387: )
388: {
389: if (tysize(em->Ety) == tysize(e->Ety) &&
390: em->E1->EV.sp.Voffset == e->EV.sp.Voffset &&
391: (tyfloating(em->Ety) != 0) == (tyfloating(e->Ety) != 0))
392: {
393: #ifdef DEBUG
394: if (debugc)
395: { dbg_printf("Moved equation ");
396: WReqn(em);
397: dbg_printf(";\n");
398: }
399: #endif
400: changes++;
401: em->Ety = e->Ety;
402: el_copy(e,em);
403: em->E1 = em->E2 = NULL;
404: em->Eoper = OPconst;
405: }
406: local_rem(u);
407: break;
408: }
409: }
410: local_symref(s);
411: }
412: else
413: local_ambigref(); // ambiguous reference
414: }
415: break;
416:
417: case OPremquo:
418: if (e->E1->Eoper != OPvar)
419: goto case_bin;
420: s = e->E1->EV.sp.Vsym;
421: if (loctop)
422: {
423: if (s->Sflags & SFLunambig)
424: local_symref(s);
425: else
426: local_ambigref(); // ambiguous reference
427: }
428: goal = 1;
429: e = e->E2;
430: goto Loop;
431:
432: default:
433: if (OTcommut(e->Eoper))
434: { // Since commutative operators may get their leaves
435: // swapped, we eliminate any that may be affected by that.
436:
437: for (u = 0; u < loctop;)
438: {
439: int f1,f2,f;
440: elem *eu;
441:
442: f = loctab[u].flags;
443: eu = loctab[u].e;
444: s = eu->E1->EV.sp.Vsym;
445: f1 = local_getflags(e->E1,s);
446: f2 = local_getflags(e->E2,s);
447: if (f1 & f2 & LFsymref || // if both reference or
448: (f1 | f2) & LFsymdef || // either define
449: f & LFambigref && (f1 | f2) & LFambigdef ||
450: f & LFambigdef && (f1 | f2) & (LFambigref | LFambigdef)
451: )
452: local_rem(u);
453: else if (f & LFunambigdef && local_chkrem(e,eu->E2))
454: local_rem(u);
455: else
456: u++;
457: }
458: }
459: if (EUNA(e))
460: { goal = 1;
461: e = e->E1;
462: goto Loop;
463: }
464: case_bin:
465: if (EBIN(e))
466: { local_exp(e->E1,1);
467: goal = 1;
468: e = e->E2;
469: goto Loop;
470: }
471: break;
472: } // end of switch (e->Eoper)
473:
474: #if !TX86
475: if (EUNA(e))
476: {
477: e->Nflags |= (e->E1->Nflags & NFLfcall);
478: }
479:
480: if (EBIN(e))
481: {
482: e->Nflags |= ((e->E1->Nflags | e->E2->Nflags) & NFLfcall);
483: }
484: #endif
485: }
486:
487: ///////////////////////////////////
488: // Examine expression tree eu to see if it defines any variables
489: // that e refs or defs.
490: // Note that e is a binary operator.
491: // Returns:
492: // !=0 if it does
493:
494: STATIC int local_chkrem(elem *e,elem *eu)
495: { int f1,f2;
496: int op;
497: symbol *s;
498: int result = 0;
499:
500: while (1)
501: { elem_debug(eu);
502: op = eu->Eoper;
503: if (OTassign(op) && eu->E1->Eoper == OPvar)
504: { s = eu->E1->EV.sp.Vsym;
505: f1 = local_getflags(e->E1,s);
506: f2 = local_getflags(e->E2,s);
507: if ((f1 | f2) & (LFsymref | LFsymdef)) // if either reference or define
508: { result = 1;
509: break;
510: }
511: }
512: if (OTbinary(op))
513: { if (local_chkrem(e,eu->E2))
514: { result = 1;
515: break;
516: }
517: }
518: else if (!OTunary(op))
519: break; // leaf node
520: eu = eu->E1;
521: }
522: return result;
523: }
524:
525: //////////////////////////////////////
526: // Add entry e to loctab[]
527:
528: STATIC void local_ins(elem *e)
529: {
530: elem_debug(e);
531: if (e->E1->Eoper == OPvar)
532: { symbol *s;
533:
534: s = e->E1->EV.sp.Vsym;
535: symbol_debug(s);
536: if (s->Sflags & SFLunambig) // if can only be referenced directly
537: { int flags;
538:
539: flags = local_getflags(e->E2,NULL);
540: #if TX86
541: if (!(flags & (LFvolatile | LFinp | LFoutp)) &&
542: #else
543: if (!(flags & LFvolatile) &&
544: #endif
545: !(e->E1->Ety & mTYvolatile))
546: {
547: // Add e to the candidate array
548: //dbg_printf("local_ins('%s'), loctop = %d, locmax = %d\n",s->Sident,loctop,locmax);
549: assert(loctop < locmax);
550: loctab[loctop].e = e;
551: loctab[loctop].flags = flags;
552: loctop++;
553: }
554: }
555: }
556: }
557:
558: //////////////////////////////////////
559: // Remove entry i from loctab[], and then compress the table.
560: //
561:
562: STATIC void local_rem(unsigned u)
563: {
564: //dbg_printf("local_rem(%u)\n",u);
565: assert(u < loctop);
566: if (u + 1 != loctop)
567: { assert(u < loctop);
568: loctab[u] = loctab[loctop - 1];
569: }
570: loctop--;
571: }
572:
573: //////////////////////////////////////
574: // Analyze and gather LFxxxx flags about expression e and symbol s.
575:
576: STATIC int local_getflags(elem *e,symbol *s)
577: { int flags;
578:
579: elem_debug(e);
580: if (s)
581: symbol_debug(s);
582: flags = 0;
warning C4390: ';' : empty controlled statement found; is this the intent?
583: while (1)
584: {
585: if (e->Ety & mTYvolatile)
586: flags |= LFvolatile;
587: switch (e->Eoper)
588: {
589: case OPeq:
590: case OPstreq:
591: if (e->E1->Eoper == OPvar)
592: { symbol *s1;
593:
594: s1 = e->E1->EV.sp.Vsym;
595: if (s1->Sflags & SFLunambig)
596: flags |= (s1 == s) ? LFsymdef : LFunambigdef;
597: else
598: flags |= LFambigdef;
599: }
600: else
601: flags |= LFambigdef;
602: goto L1;
603:
604: case OPpostinc:
605: case OPpostdec:
606: case OPaddass:
607: case OPminass:
608: case OPmulass:
609: case OPdivass:
610: case OPmodass:
611: case OPashrass:
612: case OPshrass:
613: case OPshlass:
614: case OPandass:
615: case OPxorass:
616: case OPorass:
617: if (e->E1->Eoper == OPvar)
618: { symbol *s1;
619:
620: s1 = e->E1->EV.sp.Vsym;
621: if (s1->Sflags & SFLunambig)
622: flags |= (s1 == s) ? LFsymdef | LFsymref
623: : LFunambigdef | LFunambigref;
624: else
625: flags |= LFambigdef | LFambigref;
626: }
627: else
628: flags |= LFambigdef | LFambigref;
629: L1:
630: flags |= local_getflags(e->E2,s);
631: e = e->E1;
632: break;
633:
634: case OPucall:
635: case OPucallns:
636: case OPcall:
637: case OPcallns:
638: case OPnewarray:
639: case OPmultinewarray:
640: #if TX86
641: case OPstrcat:
642: case OPstrcpy:
643: case OPmemcpy:
644: case OPbtc:
645: case OPbtr:
646: case OPbts:
647: #endif
648: case OPstrctor:
649: flags |= LFambigref | LFambigdef;
650: break;
651:
652: #if TX86
653: case OPmemset:
654: flags |= LFambigdef;
655: break;
656: #endif
657:
658: case OPvar:
659: if (e->EV.sp.Vsym == s)
660: flags |= LFsymref;
661: else if (!(e->EV.sp.Vsym->Sflags & SFLunambig))
662: flags |= LFambigref;
663: break;
664:
665: case OPind:
666: case OParray:
667: case OPfield:
668: #if TX86
669: case OPstrlen:
670: case OPstrcmp:
671: case OPmemcmp:
672: case OPbt:
673: #endif
674: flags |= LFambigref;
675: break;
676:
677: #if TX86
678: case OPinp:
679: flags |= LFinp;
680: break;
681:
682: case OPoutp:
683: flags |= LFoutp;
684: break;
685: #endif
686: }
687: if (EUNA(e))
688: {
689: if (tyfloating(e->Ety))
690: flags |= LFfloat;
691: e = e->E1;
692: }
693: else if (EBIN(e))
694: {
695: if (tyfloating(e->Ety))
696: flags |= LFfloat;
697: flags |= local_getflags(e->E2,s);
698: e = e->E1;
699: }
700: else
701: break;
702: }
703: return flags;
704: }
705:
706: //////////////////////////////////////
707: // Remove all entries with flags set.
708: //
709:
710: STATIC void local_remove(int flags)
711: { unsigned u;
712:
713: for (u = 0; u < loctop;)
714: {
715: if (loctab[u].flags & flags)
716: local_rem(u);
717: else
718: u++;
719: }
720: }
721:
722: //////////////////////////////////////
723: // Ambiguous reference. Remove all with ambiguous defs
724: //
725:
726: STATIC void local_ambigref()
727: { unsigned u;
728:
729: for (u = 0; u < loctop;)
730: {
731: if (loctab[u].flags & LFambigdef)
732: local_rem(u);
733: else
734: u++;
735: }
736: }
737:
738: //////////////////////////////////////
739: // Ambigous definition. Remove all with ambiguous refs.
740: //
741:
742: STATIC void local_ambigdef()
743: { unsigned u;
744:
745: for (u = 0; u < loctop;)
746: {
747: if (loctab[u].flags & (LFambigref | LFambigdef))
748: local_rem(u);
749: else
750: u++;
751: }
752: }
753:
754: //////////////////////////////////////
755: // Reference to symbol.
756: // Remove any that define that symbol.
757:
758: STATIC void local_symref(symbol *s)
759: { unsigned u;
760:
761: symbol_debug(s);
762: for (u = 0; u < loctop;)
763: {
764: if (local_getflags(loctab[u].e,s) & LFsymdef)
765: local_rem(u);
766: else
767: u++;
768: }
769: }
770:
771: //////////////////////////////////////
772: // Definition of symbol.
773: // Remove any that reference that symbol.
774:
775: STATIC void local_symdef(symbol *s)
776: { unsigned u;
777:
778: symbol_debug(s);
779: for (u = 0; u < loctop;)
780: {
781: if (local_getflags(loctab[u].e,s) & (LFsymref | LFsymdef))
782: local_rem(u);
783: else
784: u++;
785: }
786: }
787:
788: #endif
789: