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 !SPP
14:
15: #include <stdio.h>
16: #include <time.h>
17:
18: #include "cc.h"
19: #include "oper.h"
20: #include "global.h"
21: #include "code.h"
22: #include "type.h"
23:
24: static char __file__[] = __FILE__; /* for tassert.h */
25: #include "tassert.h"
26:
27: /*********************************
28: * Struct for each elem:
29: * Helem pointer to elem
30: * Hhash hash value for the elem
31: */
32:
33: typedef struct HCS
34: { elem *Helem;
35: unsigned Hhash;
36: } hcs;
37:
38: static hcs *hcstab = NULL; /* array of hcs's */
39: static unsigned hcsmax = 0; /* max index into hcstab[] */
40: static unsigned hcstop; /* # of entries in hcstab[] */
41: static unsigned touchstari;
42: static unsigned touchfunci[2];
43:
44: // Use a bit vector for quick check if expression is possibly in hcstab[].
45: // This results in much faster compiles when hcstab[] gets big.
46: static vec_t csvec; // vector of used entries
47: #define CSVECDIM 16001 //8009 //3001 // dimension of csvec (should be prime)
48:
49: STATIC void ecom(elem **);
50: STATIC unsigned cs_comphash(elem *);
51: STATIC void addhcstab(elem *,int);
52: STATIC void touchlvalue(elem *);
53: STATIC void touchfunc(int);
54: STATIC void touchstar(void);
55: STATIC void touchaccess(elem *);
56:
57: /*******************************
58: * Eliminate common subexpressions across extended basic blocks.
59: * String together as many blocks as we can.
60: */
61:
62: void comsubs()
63: { register block *bl,*blc,*bln;
64: register int n; /* # of blocks to treat as one */
65:
66: //static int xx;
67: //printf("comsubs() %d\n", ++xx);
68: //debugx = (xx == 37);
69:
70: #ifdef DEBUG
71: if (debugx) dbg_printf("comsubs(%p)\n",startblock);
72: #endif
73:
74: // No longer do we just compute Bcount. We now eliminate unreachable
75: // blocks.
76: block_compbcount(); // eliminate unreachable blocks
77: #if SCPP
78: if (errcnt)
79: return;
80: #endif
81:
82: if (!csvec)
83: {
84: csvec = vec_calloc(CSVECDIM);
85: }
86:
87: for (bl = startblock; bl; bl = bln)
88: {
89: bln = bl->Bnext;
90: if (!bl->Belem)
91: continue; /* if no expression or no parents */
92:
93: // Count up n, the number of blocks in this extended basic block (EBB)
94: n = 1; // always at least one block in EBB
95: blc = bl;
96: while (bln && list_nitems(bln->Bpred) == 1 &&
97: ((blc->BC == BCiftrue &&
98: list_block(list_next(blc->Bsucc)) == bln) ||
99: (blc->BC == BCgoto && list_block(blc->Bsucc) == bln)
100: ) &&
101: bln->BC != BCasm // no CSE's extending across ASM blocks
102: )
103: {
104: n++; // add block to EBB
105: blc = bln;
106: bln = blc->Bnext;
107: }
108: vec_clear(csvec);
109: hcstop = 0;
110: touchstari = 0;
111: touchfunci[0] = 0;
112: touchfunci[1] = 0;
113: bln = bl;
114: while (n--) // while more blocks in EBB
115: {
116: #ifdef DEBUG
117: if (debugx)
118: dbg_printf("cses for block %p\n",bln);
119: #endif
120: if (bln->Belem)
121: ecom(&bln->Belem); // do the tree
122: bln = bln->Bnext;
123: }
124: }
125:
126: #ifdef DEBUG
127: if (debugx)
128: dbg_printf("done with comsubs()\n");
129: #endif
130: }
131:
132: /*******************************
133: */
134:
135: void cgcs_term()
136: {
137: vec_free(csvec);
138: csvec = NULL;
139: #ifdef DEBUG
140: debugw && dbg_printf("freeing hcstab\n");
141: #endif
142: #if TX86
143: util_free(hcstab);
144: #else
145: MEM_PARF_FREE(hcstab);
146: #endif
147: hcstab = NULL;
148: hcsmax = 0;
149: }
150:
151: /*************************
152: * Eliminate common subexpressions for an element.
153: */
154:
155: STATIC void ecom(elem **pe)
156: { int i,op,hcstopsave;
157: unsigned hash;
158: elem *e,*ehash;
159: tym_t tym;
160:
161: e = *pe;
162: assert(e);
163: elem_debug(e);
164: #ifdef DEBUG
165: assert(e->Ecount == 0);
166: //assert(e->Ecomsub == 0);
167: #endif
168: tym = tybasic(e->Ety);
169: op = e->Eoper;
170: switch (op)
171: {
172: case OPconst:
173: case OPvar:
174: case OPrelconst:
175: break;
176: case OPstreq:
177: case OPpostinc:
178: case OPpostdec:
179: case OPeq:
180: case OPaddass:
181: case OPminass:
182: case OPmulass:
183: case OPdivass:
184: case OPmodass:
185: case OPshrass:
186: case OPashrass:
187: case OPshlass:
188: case OPandass:
189: case OPxorass:
190: case OPorass:
191: #if TX86
192: /* Reverse order of evaluation for double op=. This is so that */
193: /* the pushing of the address of the second operand is easier. */
194: /* However, with the 8087 we don't need the kludge. */
195: if (op != OPeq && tym == TYdouble && !config.inline8087)
196: { if (EOP(e->E1))
197: ecom(&e->E1->E1);
198: ecom(&e->E2);
199: }
200: else
201: #endif
202: {
203: /* Don't mark the increment of an i++ or i-- as a CSE, if it */
204: /* can be done with an INC or DEC instruction. */
205: if (!(OTpost(op) && elemisone(e->E2)))
206: ecom(&e->E2); /* evaluate 2nd operand first */
207: case OPnegass:
208: if (EOP(e->E1)) /* if lvalue is an operator */
209: {
210: #ifdef DEBUG
211: if (e->E1->Eoper != OPind)
212: elem_print(e);
213: #endif
214: assert(e->E1->Eoper == OPind);
215: ecom(&(e->E1->E1));
216: }
217: }
218: touchlvalue(e->E1);
219: if (!OTpost(op)) /* lvalue of i++ or i-- is not a cse*/
220: {
221: hash = cs_comphash(e->E1);
222: vec_setbit(hash % CSVECDIM,csvec);
223: addhcstab(e->E1,hash); // add lvalue to hcstab[]
224: }
225: return;
226:
227: case OPbtc:
228: case OPbts:
229: case OPbtr:
230: ecom(&e->E1);
231: ecom(&e->E2);
232: touchfunc(0); // indirect assignment
233: return;
234:
235: case OPandand:
236: case OPoror:
237: ecom(&e->E1);
238: hcstopsave = hcstop;
239: ecom(&e->E2);
240: hcstop = hcstopsave; /* no common subs by E2 */
241: return; /* if comsub then logexp() will */
242: /* break */
243: case OPcond:
244: ecom(&e->E1);
245: hcstopsave = hcstop;
246: ecom(&e->E2->E1); /* left condition */
247: hcstop = hcstopsave; /* no common subs by E2 */
248: ecom(&e->E2->E2); /* right condition */
249: hcstop = hcstopsave; /* no common subs by E2 */
250: return; /* can't be a common sub */
251: case OPcall:
252: case OPcallns:
253: ecom(&e->E2); /* eval right first */
254: /* FALL-THROUGH */
255: case OPucall:
256: case OPucallns:
257: ecom(&e->E1);
258: touchfunc(1);
259: return;
260: case OPstrpar: /* so we don't break logexp() */
261: #if TX86
262: case OPinp: /* never CSE the I/O instruction itself */
263: #endif
264: case OPdctor:
265: ecom(&e->E1);
266: /* FALL-THROUGH */
267: case OPasm:
268: case OPstrthis: // don't CSE these
269: case OPframeptr:
270: case OPgot:
271: case OPctor:
272: case OPdtor:
273: case OPmark:
274: return;
275:
276: case OPddtor:
277: return;
278:
279: case OPparam:
280: #if TX86
281: case OPoutp:
282: #endif
283: ecom(&e->E1);
284: case OPinfo:
285: ecom(&e->E2);
286: return;
287: case OPcomma:
288: case OPremquo:
289: ecom(&e->E1);
290: ecom(&e->E2);
291: break;
292: case OPvptrfptr:
293: case OPcvptrfptr:
294: ecom(&e->E1);
295: touchaccess(e);
296: break;
297: case OPind:
298: ecom(&e->E1);
299: /* Generally, CSEing a *(double *) results in worse code */
300: if (tyfloating(tym))
301: return;
302: break;
303: #if TX86
304: case OPstrcpy:
305: case OPstrcat:
306: case OPmemcpy:
307: case OPmemset:
308: ecom(&e->E2);
309: case OPsetjmp:
310: ecom(&e->E1);
311: touchfunc(0);
312: return;
313: #endif
314: default: /* other operators */
315: #if TX86
316: #ifdef DEBUG
317: if (!EBIN(e)) WROP(e->Eoper);
318: #endif
319: assert(EBIN(e));
320: case OPadd:
321: case OPmin:
322: case OPmul:
323: case OPdiv:
324: case OPor:
325: case OPxor:
326: case OPand:
327: case OPeqeq:
328: case OPne:
329: case OPscale:
330: case OPyl2x:
331: case OPyl2xp1:
332: ecom(&e->E1);
333: ecom(&e->E2);
334: break;
335: #else
336: #ifdef DEBUG
337: if (!EOP(e)) WROP(e->Eoper);
338: #endif
339: assert(EOP(e));
340: ecom(&e->E1);
341: if (EBIN(e))
342: ecom(&e->E2); /* eval left first */
343: break;
344: #endif
345: case OPstring:
346: case OPaddr:
347: case OPbit:
348: #ifdef DEBUG
349: WROP(e->Eoper);
350: elem_print(e);
351: #endif
352: assert(0); /* optelem() should have removed these */
353: /* NOTREACHED */
354:
355: #if TX86
356: // Explicitly list all the unary ops for speed
357: case OPnot: case OPcom: case OPneg: case OPuadd:
358: case OPabs: case OPsqrt: case OPrndtol: case OPsin: case OPcos: case OPrint:
359: case OPpreinc: case OPpredec:
360: case OPbool: case OPstrlen: case OPs16_32: case OPu16_32:
361: case OPd_s32: case OPd_u32: case OPoffset:
362: case OPs32_d: case OPu32_d: case OPdblint: case OPs16_d: case OPlngsht:
363: case OPd_f: case OPf_d:
364: case OPd_ld: case OPld_d:
365: case OPc_r: case OPc_i:
366: case OPu8int: case OPs8int: case OPint8:
367: case OPu32_64: case OPlngllng: case OP64_32: case OPmsw:
368: case OPu64_128: case OPs64_128: case OP128_64:
369: case OPd_s64: case OPs64_d: case OPd_u64: case OPu64_d:
370: case OPstrctor: case OPu16_d: case OPdbluns:
371: case OPptrlptr: case OPtofar16: case OPfromfar16: case OParrow:
372: case OPvoid: case OPnullcheck:
373: case OPbsf: case OPbsr: case OPbswap:
374: case OPld_u64:
375: ecom(&e->E1);
376: break;
377: #endif
378: case OPhalt:
379: return;
380: }
381:
382: /* don't CSE structures or unions or volatile stuff */
383: if (tym == TYstruct ||
384: tym == TYvoid ||
385: e->Ety & mTYvolatile
386: #if TX86
387: // don't CSE doubles if inline 8087 code (code generator can't handle it)
388: || (tyfloating(tym) && config.inline8087)
389: #endif
390: )
391: return;
392:
393: hash = cs_comphash(e); /* must be AFTER leaves are done */
394:
395: /* Search for a match in hcstab[].
396: * Search backwards, as most likely matches will be towards the end
397: * of the list.
398: */
399:
400: #ifdef DEBUG
401: if (debugx) dbg_printf("elem: %p hash: %6d\n",e,hash);
402: #endif
403: int csveci = hash % CSVECDIM;
404: if (vec_testbit(csveci,csvec))
405: {
406: for (i = hcstop; i--;)
407: {
408: #ifdef DEBUG
409: if (debugx)
410: dbg_printf("i: %2d Hhash: %6d Helem: %p\n",
411: i,hcstab[i].Hhash,hcstab[i].Helem);
412: #endif
413: if (hash == hcstab[i].Hhash && (ehash = hcstab[i].Helem) != NULL)
414: {
415: /* if elems are the same and we still have room for more */
416: if (el_match(e,ehash) && ehash->Ecount < 0xFF)
417: {
418: /* Make sure leaves are also common subexpressions
419: * to avoid false matches.
420: */
421: if (!OTleaf(op))
422: {
423: if (!e->E1->Ecount)
424: continue;
425: if (OTbinary(op) && !e->E2->Ecount)
426: continue;
427: }
428: ehash->Ecount++;
429: *pe = ehash;
430: #ifdef DEBUG
431: if (debugx)
432: dbg_printf("**MATCH** %p with %p\n",e,*pe);
433: #endif
434: el_free(e);
435: return;
436: }
437: }
438: }
439: }
440: else
441: vec_setbit(csveci,csvec);
442: addhcstab(e,hash); // add this elem to hcstab[]
443: }
444:
445: /**************************
446: * Compute hash function for elem e.
447: */
448:
449: STATIC unsigned cs_comphash(elem *e)
450: { register int hash;
451: unsigned op;
452:
453: elem_debug(e);
454: op = e->Eoper;
455: #if TX86
456: hash = (e->Ety & (mTYbasic | mTYconst | mTYvolatile)) + (op << 8);
457: #else
458: hash = e->Ety + op;
459: #endif
460: if (!OTleaf(op))
461: { hash += (size_t) e->E1;
462: if (OTbinary(op))
463: hash += (size_t) e->E2;
464: }
465: else
466: { hash += e->EV.Vint;
467: if (op == OPvar || op == OPrelconst)
468: hash += (size_t) e->EV.sp.Vsym;
469: }
470: return hash;
471: }
472:
473: /****************************
474: * Add an elem to the common subexpression table.
475: * Recompute hash if it is 0.
476: */
477:
478: STATIC void addhcstab(elem *e,int hash)
479: { unsigned h = hcstop;
480:
481: if (h >= hcsmax) /* need to reallocate table */
482: {
483: assert(h == hcsmax);
484: // With 32 bit compiles, we've got memory to burn
485: hcsmax += (__INTSIZE == 4) ? (hcsmax + 128) : 100;
warning C6326: Potential comparison of a constant with another constant
486: assert(h < hcsmax);
487: #if TX86
488: hcstab = (hcs *) util_realloc(hcstab,hcsmax,sizeof(hcs));
489: #else
490: hcstab = (hcs *) MEM_PARF_REALLOC(hcstab,hcsmax*sizeof(hcs));
491: #endif
492: //printf("hcstab = %p; hcstop = %d, hcsmax = %d\n",hcstab,hcstop,hcsmax);
493: }
494: hcstab[h].Helem = e;
495: hcstab[h].Hhash = hash;
496: hcstop++;
497: }
498:
499: /***************************
500: * "touch" the elem.
501: * If it is a pointer, "touch" all the suspects
502: * who could be pointed to.
503: * Eliminate common subs that are indirect loads.
504: */
505:
506: STATIC void touchlvalue(elem *e)
507: { register int i;
508:
509: if (e->Eoper == OPind) /* if indirect store */
510: {
511: /* NOTE: Some types of array assignments do not need
512: * to touch all variables. (Like a[5], where a is an
513: * array instead of a pointer.)
514: */
515:
516: touchfunc(0);
517: return;
518: }
519:
520: for (i = hcstop; --i >= 0;)
521: { if (hcstab[i].Helem &&
522: hcstab[i].Helem->EV.sp.Vsym == e->EV.sp.Vsym)
523: hcstab[i].Helem = NULL;
524: }
525:
526: assert(e->Eoper == OPvar || e->Eoper == OPrelconst);
527: switch (e->EV.sp.Vsym->Sclass)
528: {
529: case SCregpar:
530: case SCregister:
531: case SCtmp:
532: case SCpseudo:
533: break;
534: case SCauto:
535: case SCparameter:
536: #if TX86
537: case SCfastpar:
538: case SCbprel:
539: #endif
540: if (e->EV.sp.Vsym->Sflags & SFLunambig)
541: break;
542: /* FALL-THROUGH */
543: case SCstatic:
544: case SCextern:
545: case SCglobal:
546: case SClocstat:
547: case SCcomdat:
548: case SCinline:
549: case SCsinline:
550: case SCeinline:
551: #if TX86
552: case SCcomdef:
553: #endif
554: touchstar();
555: break;
556: default:
557: #ifdef DEBUG
558: elem_print(e);
559: symbol_print(e->EV.sp.Vsym);
560: #endif
561: assert(0);
562: }
563: }
564:
565: /**************************
566: * "touch" variables that could be changed by a function call or
567: * an indirect assignment.
568: * Eliminate any subexpressions that are "starred" (they need to
569: * be recomputed).
570: * Input:
571: * flag If !=0, then this is a function call.
572: * If 0, then this is an indirect assignment.
573: */
574:
575: STATIC void touchfunc(int flag)
576: { register hcs *pe,*petop;
577: register elem *he;
578:
579: //printf("touchfunc(%d)\n", flag);
580: petop = &hcstab[hcstop];
581: //pe = &hcstab[0]; printf("pe = %p, petop = %p\n",pe,petop);
582: for (pe = &hcstab[0]; pe < petop; pe++)
583: //for (pe = &hcstab[touchfunci[flag]]; pe < petop; pe++)
584: { he = pe->Helem;
585: if (!he)
586: continue;
587: switch (he->Eoper)
588: {
589: case OPvar:
590: switch (he->EV.sp.Vsym->Sclass)
591: {
592: case SCregpar:
593: case SCregister:
594: case SCtmp:
595: break;
596: case SCauto:
597: case SCparameter:
598: #if TX86
599: case SCfastpar:
600: case SCbprel:
601: #endif
602: //printf("he = '%s'\n", he->EV.sp.Vsym->Sident);
603: if (he->EV.sp.Vsym->Sflags & SFLunambig)
604: break;
605: /* FALL-THROUGH */
606: case SCstatic:
607: case SCextern:
608: #if TX86
609: case SCcomdef:
610: #endif
611: case SCglobal:
612: case SClocstat:
613: case SCcomdat:
614: case SCpseudo:
615: case SCinline:
616: case SCsinline:
617: case SCeinline:
618: if (!(he->EV.sp.Vsym->ty() & mTYconst))
619: goto L1;
620: break;
621: default:
622: debug(WRclass((enum SC)he->EV.sp.Vsym->Sclass));
623: assert(0);
624: }
625: break;
626: case OPind:
627: #if TX86
628: case OPstrlen:
629: case OPstrcmp:
630: case OPmemcmp:
631: case OPbt:
632: #endif
633: goto L1;
634: case OPvptrfptr:
635: case OPcvptrfptr:
636: if (flag == 0) /* function calls destroy vptrfptr's, */
637: break; /* not indirect assignments */
638: L1:
639: pe->Helem = NULL;
640: break;
641: }
642: }
643: touchfunci[flag] = hcstop;
warning C6386: Buffer overrun: accessing 'touchfunci', the writable size is '8' bytes, but '12' bytes might be written: Lines: 576, 577, 580, 582, 584, 585, 582, 584, 585, 582, 584, 585, 587, 634, 635, 636, 638, 639, 582, 643
644: }
645:
646:
647: /*******************************
648: * Eliminate all common subexpressions that
649: * do any indirection ("starred" elems).
650: */
651:
652: STATIC void touchstar()
653: { register int i;
654: register elem *e;
655:
656: for (i = touchstari; i < hcstop; i++)
warning C4018: '<' : signed/unsigned mismatch
657: { e = hcstab[i].Helem;
658: if (e && (e->Eoper == OPind || e->Eoper == OPbt) /*&& !(e->Ety & mTYconst)*/)
659: hcstab[i].Helem = NULL;
660: }
661: touchstari = hcstop;
662: }
663:
664: /*****************************************
665: * Eliminate any common subexpressions that could be modified
666: * if a handle pointer access occurs.
667: */
668:
669: STATIC void touchaccess(elem *ev)
670: { register int i;
671: register elem *e;
672:
673: ev = ev->E1;
674: for (i = 0; i < hcstop; i++)
warning C4018: '<' : signed/unsigned mismatch
675: { e = hcstab[i].Helem;
676: /* Invalidate any previous handle pointer accesses that */
677: /* are not accesses of ev. */
678: if (e && (e->Eoper == OPvptrfptr || e->Eoper == OPcvptrfptr) &&
679: e->E1 != ev)
680: hcstab[i].Helem = NULL;
681: }
682: }
683:
684: #endif // !SPP
685: