1: // Copyright (C) 1986-1997 by Symantec
2: // Copyright (C) 2000-2010 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:
14: /****************************************************************
15: * Handle basic blocks.
16: */
17:
18: #if !SPP
19:
20: #include <stdio.h>
21: #include <string.h>
22: #include <time.h>
23: #include <stdlib.h>
24:
25: #include "cc.h"
26: #include "oper.h"
27: #include "el.h"
28: #include "type.h"
29: #include "global.h"
30: #include "go.h"
31: #include "code.h"
32: #if SCPP
33: #include "parser.h"
34: #include "iasm.h"
35: #endif
36:
37: static char __file__[] = __FILE__; /* for tassert.h */
38: #include "tassert.h"
39:
40: STATIC void bropt(void);
41: STATIC void brrear(void);
42: STATIC void search(block *b);
43: STATIC void elimblks(void);
44: STATIC int mergeblks(void);
45: STATIC void blident(void);
46: STATIC void blreturn(void);
47: STATIC void brmin(void);
48: STATIC void bltailmerge(void);
49: STATIC void block_check();
50: STATIC void brtailrecursion();
51: STATIC elem * assignparams(elem **pe,int *psi,elem **pe2);
52: STATIC void emptyloops();
53: int el_anyframeptr(elem *e);
54:
55: unsigned numblks; // number of basic blocks in current function
56: block *startblock; /* beginning block of function */
57: /* (can have no predecessors) */
58:
59: block **dfo = NULL; /* array of depth first order */
60: unsigned dfotop; /* # of items in dfo[] */
61:
62: block *curblock; /* current block being read in */
63: block *block_last; // last block read in
64:
65: static block * block_freelist;
66:
67: ////////////////////////////
68: // Storage allocator.
69:
70: static block blkzero;
71:
72: __inline block *block_calloc_i()
73: { block *b;
74:
75: if (block_freelist)
76: { b = block_freelist;
77: block_freelist = b->Bnext;
78: *b = blkzero;
79: }
80: else
81: b = (block *) mem_fcalloc(sizeof(block));
82: return b;
83: }
84:
85: block *block_calloc()
86: {
87: return block_calloc_i();
88: }
89:
90: //////////////////////////////////
91: //
92:
93: unsigned bc_goal[BCMAX];
94:
95: void block_init()
96: { int i;
97:
98: for (i = 0; i < BCMAX; i++)
99: bc_goal[i] = GOALvalue;
100: bc_goal[BCgoto] = GOALnone;
101: bc_goal[BCret ] = GOALnone;
102: bc_goal[BCexit] = GOALnone;
103: }
104:
105: //////////////////////////////////
106: //
107:
108: void block_term()
109: {
110: #if TERMCODE
111: block *b;
112:
113: while (block_freelist)
114: { b = block_freelist->Bnext;
115: mem_ffree(block_freelist);
116: block_freelist = b;
117: }
118:
119: #endif
120: }
121:
122: /**************************
123: * Finish up this block and start the next one.
124: */
125:
126: #if MARS
127: void block_next(Blockx *bctx,enum BC bc,block *bn)
128: {
129: bctx->curblock->BC = bc;
130: block_last = bctx->curblock;
131: if (!bn)
132: bn = block_calloc_i();
133: bctx->curblock->Bnext = bn; // next block
134: bctx->curblock = bctx->curblock->Bnext; // new current block
135: #if NTEXCEPTIONS
136: bctx->curblock->Btry = bctx->tryblock;
137: #endif
138: bctx->curblock->Bflags |= bctx->flags;
139: }
140: #else
141: void block_next(enum BC bc,block *bn)
142: {
143: curblock->BC = bc;
144: curblock->Bsymend = globsym.top;
145: block_last = curblock;
146: if (!bn)
147: bn = block_calloc_i();
148: curblock->Bnext = bn; // next block
149: curblock = curblock->Bnext; // new current block
150: curblock->Bsymstart = globsym.top;
151: curblock->Btry = pstate.STbtry;
152: }
153:
154: void block_next()
155: {
156: block_next((enum BC)curblock->BC,NULL);
157: }
158: #endif
159:
160: /**************************
161: * Finish up this block and start the next one.
162: */
163:
164: #if MARS
165:
166: block *block_goto(Blockx *bx,enum BC bc,block *bn)
167: { block *b;
168:
169: b = bx->curblock;
170: block_next(bx,bc,bn);
171: list_append(&b->Bsucc,bx->curblock);
172: return bx->curblock;
173: }
174:
175: #endif
176:
177: /****************************
178: * Goto a block named gotolbl.
179: * Start a new block that is labelled by newlbl.
180: */
181:
182: #if SCPP
183:
184: void block_goto()
185: {
186: block_goto(block_calloc());
187: }
188:
189: void block_goto(block *bn)
190: {
191: block_goto(bn,bn);
192: }
193:
194: void block_goto(block *bgoto,block *bnew)
195: {
196: enum BC bc;
197:
198: assert(bgoto);
199: list_append(&(curblock->Bsucc),bgoto);
200: if (curblock->Bcode) // If there is already code in the block
201: // then this is an ASM block
202: bc = BCasm;
203: else
204: bc = BCgoto; // fall thru to next block
205: block_next(bc,bnew);
206: }
207:
208: #endif
209:
210: /**********************************
211: * Replace block numbers with block pointers.
212: * Also compute numblks and maxblks.
213: */
214:
215: void block_ptr()
216: { block *b;
217:
218: /* dbg_printf("block_ptr()\n");*/
219:
220: numblks = 0;
221: for (b = startblock; b; b = b->Bnext) /* for each block */
222: {
223: #if SCPP
224: b->Bblknum = numblks;
225: #endif
226: numblks++;
227: }
228: maxblks = 3 * numblks; /* allow for increase in # of blocks */
229: }
230:
231: /*******************************
232: * Build predecessor list (Bpred) for each block.
233: */
234:
235: void block_pred()
236: { block *b;
237:
238: //dbg_printf("block_pred()\n");
239: for (b = startblock; b; b = b->Bnext) /* for each block */
240: list_free(&b->Bpred,FPNULL);
241:
242: for (b = startblock; b; b = b->Bnext) /* for each block */
243: { register list_t bp;
244:
245: //printf("b = %p, BC = ",b); WRBC(b->BC); printf("\n");
246: for (bp = b->Bsucc; bp; bp = list_next(bp))
247: { /* for each successor to b */
248: //printf("\tbs = %p\n",list_block(bp));
249: assert(list_block(bp));
250: list_prepend(&(list_block(bp)->Bpred),b);
251: }
252: }
253: assert(startblock->Bpred == NULL); /* startblock has no preds */
warning C6011: Dereferencing NULL pointer 'struct block * startblock': Lines: 236, 239, 242, 253
254: }
255:
256: /********************************************
257: * Clear visit.
258: */
259:
260: void block_clearvisit()
261: { block *b;
262:
263: for (b = startblock; b; b = b->Bnext) // for each block
264: b->Bflags &= ~BFLvisited; // mark as unvisited
265: }
266:
267: /********************************************
268: * Visit block and each of its predecessors.
269: */
270:
271: void block_visit(block *b)
272: { list_t l;
273:
274: b->Bflags |= BFLvisited;
275: for (l = b->Bsucc; l; l = list_next(l)) // for each successor
276: { block *bs = list_block(l);
277: assert(bs);
278: if ((bs->Bflags & BFLvisited) == 0) // if not visited
279: block_visit(bs);
280: }
281: }
282:
283: /*****************************
284: * Compute number of parents (Bcount) of each basic block.
285: */
286:
287: void block_compbcount()
288: {
289: block_clearvisit();
290: block_visit(startblock); // visit all reachable blocks
291: elimblks(); // eliminate unvisited blocks
292: }
293:
294: /*******************************
295: * Free list of blocks.
296: */
297:
298: void blocklist_free(block **pb)
299: { block *b,*bn;
300:
301: for (b = *pb; b; b = bn)
302: { bn = b->Bnext;
303: block_free(b);
304: }
305: *pb = NULL;
306: }
307:
308: /********************************
309: * Free optimizer gathered data.
310: */
311:
312: void block_optimizer_free(block *b)
313: {
314: vec_free(b->Bdom);
315: vec_free(b->Binrd);
316: vec_free(b->Boutrd);
317: vec_free(b->Binlv);
318: vec_free(b->Boutlv);
319: vec_free(b->Bin);
320: vec_free(b->Bout);
321: vec_free(b->Bgen);
322: vec_free(b->Bkill);
323: vec_free(b->Bout2);
324: vec_free(b->Bgen2);
325: vec_free(b->Bkill2);
326:
327: memset(&b->_BLU,0,sizeof(b->_BLU));
328: }
329:
330: /****************************
331: * Free a block.
332: */
333:
334: void block_free(block *b)
335: {
336: assert(b);
337: if (b->Belem)
338: el_free(b->Belem);
339: list_free(&b->Bsucc,FPNULL);
340: list_free(&b->Bpred,FPNULL);
341: if (OPTIMIZER)
342: block_optimizer_free(b);
343: switch (b->BC)
344: { case BCswitch:
345: case BCifthen:
346: case BCjmptab:
347: #if MARS
348: free(b->BS.Bswitch);
349: #else
350: MEM_PH_FREE(b->BS.Bswitch);
351: #endif
352: break;
353: #if SCPP
354: case BCcatch:
355: type_free(b->Bcatchtype);
356: break;
357: #endif
358: case BCasm:
359: code_free(b->Bcode);
360: break;
361: }
362: b->Bnext = block_freelist;
363: block_freelist = b;
364: }
365:
366: /****************************
367: * Hydrate/dehydrate a list of blocks.
368: */
369:
370: #if HYDRATE
371: void blocklist_hydrate(block **pb)
372: { block *b;
373:
374: while (isdehydrated(*pb))
375: {
376: /*dbg_printf("blocklist_hydrate(*pb = %p) =",*pb);*/
377: b = (block *)ph_hydrate(pb);
378: /*dbg_printf(" %p\n",b);*/
379: el_hydrate(&b->Belem);
380: list_hydrate(&b->Bsucc,FPNULL);
381: list_hydrate(&b->Bpred,FPNULL);
382: (void) ph_hydrate(&b->Btry);
383: #if SCPP
384: (void) ph_hydrate(&b->Bendscope);
385: symbol_hydrate(&b->Binitvar);
386: #endif
387: switch (b->BC)
388: {
389: #if SCPP
390: case BCtry:
391: symbol_hydrate(&b->catchvar);
392: break;
393: case BCcatch:
394: type_hydrate(&b->Bcatchtype);
395: break;
396: #endif
397: case BCswitch:
398: (void) ph_hydrate(&b->BS.Bswitch);
399: break;
400:
401: case BC_finally:
402: //(void) ph_hydrate(&b->B_ret);
403: break;
404:
405: case BCasm:
406: code_hydrate(&b->Bcode);
407: break;
408: }
409: #if TX86
410: filename_translate(&b->Bsrcpos);
411: srcpos_hydrate(&b->Bsrcpos);
412: #endif
413: pb = &b->Bnext;
414: }
415: }
416: #endif
417:
418: #if DEHYDRATE
419: void blocklist_dehydrate(block **pb)
420: { block *b;
421:
422: while ((b = *pb) != NULL && !isdehydrated(b))
423: {
424: #if DEBUG_XSYMGEN
425: if (xsym_gen && ph_in_head(b))
426: return;
427: #endif
428: /*dbg_printf("blocklist_dehydrate(*pb = %p) =",b);*/
429: ph_dehydrate(pb);
430: /*dbg_printf(" %p\n",*pb);*/
431: el_dehydrate(&b->Belem);
432: list_dehydrate(&b->Bsucc,FPNULL);
433: list_dehydrate(&b->Bpred,FPNULL);
434: ph_dehydrate(&b->Btry);
435: #if SCPP
436: ph_dehydrate(&b->Bendscope);
437: symbol_dehydrate(&b->Binitvar);
438: #endif
439: switch (b->BC)
440: {
441: #if SCPP
442: case BCtry:
443: symbol_dehydrate(&b->catchvar);
444: break;
445: case BCcatch:
446: type_dehydrate(&b->Bcatchtype);
447: break;
448: #endif
449: case BCswitch:
450: ph_dehydrate(&b->BS.Bswitch);
451: break;
452:
453: case BC_finally:
454: //ph_dehydrate(&b->B_ret);
455: break;
456:
457: case BCasm:
458: code_dehydrate(&b->Bcode);
459: break;
460: }
461: #if TX86
462: srcpos_dehydrate(&b->Bsrcpos);
463: #endif
464: pb = &b->Bnext;
465: }
466: }
467: #endif
468:
469: /****************************
470: * Append elem to the elems comprising the current block.
471: * Read in an expression and put it in curblock->Belem.
472: * If there is one already there, create a tree like:
473: * ,
474: * / \
475: * old e
476: */
477:
478: void block_appendexp(block *b,elem *e)
479: { elem *ec;
480: elem **pe;
481:
482: assert(MARS || PARSER);
483: if (e)
484: {
485: assert(b);
486: elem_debug(e);
487: pe = &b->Belem;
488: ec = *pe;
489: if (ec != NULL)
490: {
491: type *t = e->ET;
492:
493: if (t)
494: type_debug(t);
495: elem_debug(e);
warning C4390: ';' : empty controlled statement found; is this the intent?
496: #if MARS
497: tym_t ty = e->Ety;
498:
499: elem_debug(e);
500: /* Build tree such that (a,b) => (a,(b,e)) */
501: while (ec->Eoper == OPcomma)
502: {
503: ec->Ety = ty;
504: ec->ET = t;
505: pe = &(ec->E2);
506: ec = *pe;
507: }
508: e = el_bin(OPcomma,ty,ec,e);
509: e->ET = t;
510: #else
511: /* Build tree such that (a,b) => (a,(b,e)) */
512: while (ec->Eoper == OPcomma)
513: {
514: el_settype(ec,t);
515: pe = &(ec->E2);
516: ec = *pe;
517: }
518: e = el_bint(OPcomma,t,ec,e);
519: #endif
520: }
521: *pe = e;
522: }
523: }
524:
525: /************************
526: * Mark curblock as initializing symbol s.
527: */
528:
529: #if SCPP
530:
531: #undef block_initvar
532:
533: void block_initvar(symbol *s)
534: {
535: #ifdef DEBUG
536: assert(curblock);
537: #endif
538: symbol_debug(s);
539: curblock->Binitvar = s;
540: }
541:
542: #endif
543:
544: /*******************
545: * Mark end of function.
546: * flag:
547: * 0 do a "return"
548: * 1 do a "return 0"
549: */
550:
551: void block_endfunc(int flag)
552: {
553: #if SCPP
554: curblock->Bsymend = globsym.top;
555: curblock->Bendscope = curblock;
556: #endif
557: if (flag)
558: { elem *e;
559:
560: e = el_longt(tsint, 0);
561: block_appendexp(curblock, e);
562: curblock->BC = BCretexp; // put a return at the end
563: }
564: else
565: curblock->BC = BCret; // put a return at the end
566: curblock = NULL; // undefined from now on
567: block_last = NULL;
568: }
569:
570: /******************************
571: * Perform branch optimization on basic blocks.
572: */
573:
574: void blockopt(int iter)
575: { block *b;
576: int count;
577:
578: if (OPTIMIZER)
579: {
580: int iterationLimit = 200;
581: if (iterationLimit < numblks)
warning C4018: '<' : signed/unsigned mismatch
582: iterationLimit = numblks;
583: count = 0;
584: do
585: {
586: //printf("changes = %d, count = %d, dfotop = %d\n",changes,count,dfotop);
587: #if MARS
588: util_progress();
589: #else
590: if (controlc_saw)
591: util_exit(EXIT_BREAK);
592: #endif
593: changes = 0;
594: bropt(); // branch optimization
595: brrear(); // branch rearrangement
596: blident(); // combine identical blocks
597: blreturn(); // split out return blocks
598: bltailmerge(); // do tail merging
599: brtailrecursion(); // do tail recursion
600: brcombine(); // convert graph to expressions
601: if (iter >= 2)
602: brmin(); // minimize branching
603: do
604: {
605: compdfo(); /* compute depth first order (DFO) */
606: elimblks(); /* remove blocks not in DFO */
607: assert(count < iterationLimit);
608: count++;
609: } while (mergeblks()); /* merge together blocks */
610: } while (changes);
611: #ifdef DEBUG
612: if (debugw)
613: for (b = startblock; b; b = b->Bnext)
614: WRblock(b);
615: #endif
616: }
617: else
618: {
619: /* canonicalize the trees */
620: for (b = startblock; b; b = b->Bnext)
621: {
622: #ifdef DEBUG
623: if (debugb)
624: WRblock(b);
625: #endif
626: if (b->Belem)
627: { b->Belem = doptelem(b->Belem,bc_goal[b->BC] | GOALstruct);
628: if (b->Belem)
629: b->Belem = el_convert(b->Belem);
630: }
631: #ifdef DEBUG
632: if (debugb)
633: { dbg_printf("after optelem():\n");
634: WRblock(b);
635: }
636: #endif
637: }
638: if (localgot)
639: { // Initialize with:
640: // localgot = OPgot;
641: elem *e = el_long(TYnptr, 0);
642: e->Eoper = OPgot;
643: e = el_bin(OPeq, TYnptr, el_var(localgot), e);
644: startblock->Belem = el_combine(e, startblock->Belem);
warning C6011: Dereferencing NULL pointer 'struct block * startblock': Lines: 575, 576, 578, 620, 638, 641, 642, 643, 644
645: }
646:
647: bropt(); /* branch optimization */
648: brrear(); /* branch rearrangement */
649: comsubs(); /* eliminate common subexpressions */
650: #ifdef DEBUG
651: if (debugb)
652: for (b = startblock; b; b = b->Bnext)
653: WRblock(b);
654: #endif
655: }
656: }
657:
658: /***********************************
659: * Try to remove control structure.
660: * That is, try to resolve if-else, goto and return statements
661: * into &&, || and ?: combinations.
662: */
663:
664: void brcombine()
665: { block *b;
666: block *b2,*b3;
667: int op;
668: int anychanges;
669:
670: cmes("brcombine()\n");
671: //for (b = startblock; b; b = b->Bnext)
672: //WRblock(b);
673:
674: if (funcsym_p->Sfunc->Fflags3 & (Fcppeh | Fnteh))
675: { // Don't mess up extra EH info by eliminating blocks
676: return;
677: }
678:
679: do
680: {
681: anychanges = 0;
682: for (b = startblock; b; b = b->Bnext) /* for each block */
683: { unsigned char bc;
684:
685: /* Look for [e1 IFFALSE L3,L2] L2: [e2 GOTO L3] L3: [e3] */
686: /* Replace with [(e1 && e2),e3] */
687: bc = b->BC;
688: if (bc == BCiftrue)
689: { unsigned char bc2;
690:
691: b2 = list_block(b->Bsucc);
692: b3 = list_block(list_next(b->Bsucc));
693:
694: if (list_next(b2->Bpred)) // if more than one predecessor
695: continue;
696: if (b2 == b3)
697: continue;
698: if (b2 == startblock)
699: continue;
700: if (!PARSER && b2->Belem && EOP(b2->Belem))
701: continue;
702:
703: bc2 = b2->BC;
704: if (bc2 == BCgoto &&
705: b3 == list_block(b2->Bsucc))
706: {
707: b->BC = BCgoto;
708: if (b2->Belem)
709: {
710: op = OPandand;
711: b->Belem = PARSER ? el_bint(op,tsint,b->Belem,b2->Belem)
712: : el_bin(op,TYint,b->Belem,b2->Belem);
713: b2->Belem = NULL;
714: }
715: list_subtract(&(b->Bsucc),b2);
716: list_subtract(&(b2->Bpred),b);
717: cmes("brcombine(): if !e1 then e2 => e1 || e2\n");
718: anychanges++;
719: }
720: else if (list_next(b3->Bpred) || b3 == startblock)
721: continue;
722: else if ((bc2 == BCretexp && b3->BC == BCretexp)
723: //|| (bc2 == BCret && b3->BC == BCret)
724: )
725: { elem *e;
726:
727: if (PARSER)
728: {
729: type *t = (bc2 == BCretexp) ? b2->Belem->ET : tsvoid;
730: e = el_bint(OPcolon2,t,b2->Belem,b3->Belem);
731: b->Belem = el_bint(OPcond,t,b->Belem,e);
732: }
733: else
734: {
735: if (EOP(b3->Belem))
736: continue;
737: tym_t ty = (bc2 == BCretexp) ? b2->Belem->Ety : TYvoid;
738: e = el_bin(OPcolon2,ty,b2->Belem,b3->Belem);
739: b->Belem = el_bin(OPcond,ty,b->Belem,e);
740: }
741: b->BC = bc2;
742: b->Belem->ET = b2->Belem->ET;
743: b2->Belem = NULL;
744: b3->Belem = NULL;
745: list_free(&b->Bsucc,FPNULL);
746: list_subtract(&(b2->Bpred),b);
747: list_subtract(&(b3->Bpred),b);
748: cmes("brcombine(): if e1 return e2 else return e3 => ret e1?e2:e3\n");
749: anychanges++;
750: }
751: else if (bc2 == BCgoto &&
752: b3->BC == BCgoto &&
753: list_block(b2->Bsucc) == list_block(b3->Bsucc))
754: { elem *e;
755: block *bsucc;
756:
757: bsucc = list_block(b2->Bsucc);
758: if (b2->Belem)
759: {
760: if (PARSER)
761: {
762: if (b3->Belem)
763: {
764: e = el_bint(OPcolon2,b2->Belem->ET,
765: b2->Belem,b3->Belem);
766: e = el_bint(OPcond,e->ET,b->Belem,e);
767: }
768: else
769: {
770: op = OPandand;
771: e = el_bint(op,tsint,b->Belem,b2->Belem);
772: }
773: }
774: else
775: {
776: if (b3->Belem)
777: {
778: if (EOP(b3->Belem))
779: continue;
780: e = el_bin(OPcolon2,b2->Belem->Ety,
781: b2->Belem,b3->Belem);
782: e = el_bin(OPcond,e->Ety,b->Belem,e);
783: e->ET = b2->Belem->ET;
784: }
785: else
786: {
787: op = OPandand;
788: e = el_bin(op,TYint,b->Belem,b2->Belem);
789: }
790: }
791: b2->Belem = NULL;
792: b->Belem = e;
793: }
794: else if (b3->Belem)
795: {
796: op = OPoror;
797: b->Belem = PARSER ? el_bint(op,tsint,b->Belem,b3->Belem)
798: : el_bin(op,TYint,b->Belem,b3->Belem);
799: }
800: b->BC = BCgoto;
801: b3->Belem = NULL;
802: list_free(&b->Bsucc,FPNULL);
803:
804: list_append(&b->Bsucc,bsucc);
805: list_append(&bsucc->Bpred,b);
806:
807: list_free(&(b2->Bpred),FPNULL);
808: list_free(&(b2->Bsucc),FPNULL);
809: list_free(&(b3->Bpred),FPNULL);
810: list_free(&(b3->Bsucc),FPNULL);
811: b2->BC = BCret;
812: b3->BC = BCret;
813: list_subtract(&(bsucc->Bpred),b2);
814: list_subtract(&(bsucc->Bpred),b3);
815: cmes("brcombine(): if e1 goto e2 else goto e3 => ret e1?e2:e3\n");
816: anychanges++;
817: }
818: }
819: else if (bc == BCgoto && PARSER)
820: {
821: b2 = list_block(b->Bsucc);
822: if (!list_next(b2->Bpred) && b2->BC != BCasm // if b is only parent
823: && b2 != startblock
824: #if SCPP
825: && b2->BC != BCtry
826: #endif
827: && b2->BC != BC_try
828: && b->Btry == b2->Btry
829: )
830: { list_t bl;
831:
832: if (b2->Belem)
833: {
834: if (PARSER)
835: {
836: block_appendexp(b,b2->Belem);
837: }
838: else if (b->Belem)
839: b->Belem = el_bin(OPcomma,b2->Belem->Ety,b->Belem,b2->Belem);
840: else
841: b->Belem = b2->Belem;
842: b2->Belem = NULL;
843: }
844: list_subtract(&b->Bsucc,b2);
845: list_subtract(&b2->Bpred,b);
846:
847: /* change predecessor of successors of b2 from b2 to b */
848: for (bl = b2->Bsucc; bl; bl = list_next(bl))
849: { list_t bp;
850:
851: for (bp = list_block(bl)->Bpred; bp; bp = list_next(bp))
852: {
853: if (list_block(bp) == b2)
854: list_ptr(bp) = (void *)b;
855: }
856: }
857:
858: b->BC = b2->BC;
859: b->BS = b2->BS;
860: b->Bsucc = b2->Bsucc;
861: b2->Bsucc = NULL;
862: b2->BC = BCret; /* a harmless one */
863: cmes3("brcombine(): %p goto %p eliminated\n",b,b2);
864: anychanges++;
865: }
866: }
867: }
868: if (anychanges)
869: { changes++;
870: continue;
871: }
872: } while (0);
873: }
874:
875: /***********************
876: * Branch optimization.
877: */
878:
879: STATIC void bropt()
880: { block *b,*db;
881: elem *n,**pn;
882:
883: cmes("bropt()\n");
884: assert(!PARSER);
885: for (b = startblock; b; b = b->Bnext) /* for each block */
886: {
887: pn = &(b->Belem);
888: if (OPTIMIZER && *pn)
889: while ((*pn)->Eoper == OPcomma)
890: pn = &((*pn)->E2);
891:
892: n = *pn;
893: if (b->BC == BCiftrue)
894: {
895: assert(n);
896: /* Replace IF (!e) GOTO ... with */
897: /* IF OPnot (e) GOTO ... */
898: if (n->Eoper == OPnot)
899: {
900: tym_t tym;
901:
902: tym = n->E1->Ety;
903: *pn = el_selecte1(n);
904: (*pn)->Ety = tym;
905: for (n = b->Belem; n->Eoper == OPcomma; n = n->E2)
906: n->Ety = tym;
907: b->Bsucc = list_reverse(b->Bsucc);
908: cmes("CHANGE: if (!e)\n");
909: changes++;
910: }
911:
912: /* Take care of IF (constant) */
913: if (iftrue(n)) /* if elem is TRUE */
914: {
915: // select first succ
916: db = list_block(list_next(b->Bsucc));
917: goto L1;
918: }
919: else if (iffalse(n))
920: {
921: // select second succ
922: db = list_block(b->Bsucc);
923:
924: L1: list_subtract(&(b->Bsucc),db);
925: list_subtract(&(db->Bpred),b);
926: b->BC = BCgoto;
927: /* delete elem if it has no side effects */
928: b->Belem = doptelem(b->Belem,GOALnone | GOALagain);
929: cmes("CHANGE: if (const)\n");
930: changes++;
931: }
932:
933: /* Look for both destinations being the same */
934: else if (list_block(b->Bsucc) ==
935: list_block(list_next(b->Bsucc)))
936: { b->BC = BCgoto;
937: db = list_block(b->Bsucc);
938: list_subtract(&(b->Bsucc),db);
939: list_subtract(&(db->Bpred),b);
940: cmes("CHANGE: if (e) goto L1; else goto L1;\n");
941: changes++;
942: }
943: }
944: else if (b->BC == BCswitch)
945: { /* see we can evaluate this switch now */
946: register unsigned i,ncases;
947: targ_llong *p,value;
948: register list_t bl;
949:
950: while (n->Eoper == OPcomma)
951: n = n->E2;
952: if (n->Eoper != OPconst)
953: continue;
954: assert(tyintegral(n->Ety));
955: value = el_tolong(n);
956: p = b->BS.Bswitch; /* ptr to switch data */
957: assert(p);
958: ncases = *p++; /* # of cases */
warning C4244: '=' : conversion from 'targ_llong' to 'unsigned int', possible loss of data
959: i = 1; /* first case */
960: while (1)
961: {
962: if (i > ncases)
963: { i = 0; /* select default */
964: break;
965: }
966: if (*p++ == value)
967: break; /* found it */
968: i++; /* next case */
969: }
970: /* the ith entry in Bsucc is the one we want */
971: db = list_block(list_nth(b->Bsucc,i));
972: /* delete predecessors of successors (!) */
973: for (bl = b->Bsucc; bl; bl = list_next(bl))
974: if (i--) // if not ith successor
975: { void *p;
warning C6246: Local declaration of 'p' hides declaration of the same name in outer scope. For additional information, see previous declaration at line '947' of 'c:\projects\extern\d\dmd\src\backend\blockopt.c': Lines: 947
976: p = list_subtract(
977: &(list_block(bl)->Bpred),b);
978: assert(p == b);
979: }
980:
981: /* dump old successor list and create a new one */
982: list_free(&b->Bsucc,FPNULL);
983: list_append(&b->Bsucc,db);
984: b->BC = BCgoto;
985: b->Belem = doptelem(b->Belem,GOALnone | GOALagain);
986: cmes("CHANGE: switch (const)\n");
987: changes++;
988: }
989: }
990: }
991:
992: /*********************************
993: * Do branch rearrangement.
994: */
995:
996: STATIC void brrear()
997: { register block *b;
998:
999: cmes("brrear()\n");
1000: for (b = startblock; b; b = b->Bnext) /* for each block */
1001: { register list_t bl;
1002:
1003: for (bl = b->Bsucc; bl; bl = list_next(bl))
1004: { /* For each transfer of control block pointer */
1005: block *bt;
1006: int iter = 0;
1007:
1008: bt = list_block(bl);
1009:
1010: /* If it is a transfer to a block that consists */
1011: /* of nothing but an unconditional transfer, */
1012: /* Replace transfer address with that */
1013: /* transfer address. */
1014: /* Note: There are certain kinds of infinite */
1015: /* loops which we avoid by putting a lid on */
1016: /* the number of iterations. */
1017:
1018: while (bt->BC == BCgoto && !bt->Belem &&
1019: #if SCPP || NTEXCEPTIONS
1020: b->Btry == bt->Btry &&
1021: #endif
1022: #if NTEXCEPTIONS
1023: bt->Btry == list_block(bt->Bsucc)->Btry &&
1024: #endif
1025:
1026: ++iter < 10)
1027: {
1028: list_ptr(bl) = list_ptr(bt->Bsucc);
1029: if (bt->Bsrcpos.Slinnum && !b->Bsrcpos.Slinnum)
1030: b->Bsrcpos = bt->Bsrcpos;
1031: b->Bflags |= bt->Bflags;
1032: list_append(&(list_block(bl)->Bpred),b);
1033: list_subtract(&(bt->Bpred),b);
1034: cmes("goto->goto\n");
1035: bt = list_block(bl);
1036: }
1037:
1038: // Bsucc after the first are the targets of
1039: // jumps, calls and loops, and as such to do this right
1040: // we need to traverse the Bcode list and fix up
1041: // the IEV2.Vblock pointers.
1042: if (b->BC == BCasm)
1043: break;
1044: }
1045: #if 0
1046: /* Replace cases of */
1047: /* IF (e) GOTO L1 ELSE L2 */
1048: /* L1: */
1049: /* with */
1050: /* IF OPnot (e) GOTO L2 ELSE L1 */
1051: /* L1: */
1052:
1053: if (b->BC == BCiftrue || b->BC == BCiffalse)
1054: { register block *bif,*belse;
1055:
1056: bif = list_block(b->Bsucc);
1057: belse = list_block(list_next(b->Bsucc));
1058:
1059: if (bif == b->Bnext)
1060: { b->BC ^= BCiffalse ^ BCiftrue; /* toggle */
1061: list_ptr(b->Bsucc) = belse;
1062: list_ptr(list_next(b->Bsucc)) = bif;
1063: b->Bflags |= bif->Bflags & BFLvisited;
1064: cmes("if (e) L1 else L2\n");
1065: }
1066: }
1067: #endif
1068: } /* for */
1069: }
1070:
1071: /*************************
1072: * Compute depth first order (DFO).
1073: * Equivalent to Aho & Ullman Fig. 13.8.
1074: * Blocks not in dfo[] are unreachable.
1075: */
1076:
1077: void compdfo()
1078: {
1079: register int i;
1080:
1081: cmes("compdfo()\n");
1082: assert(OPTIMIZER);
1083: block_clearvisit();
1084: #ifdef DEBUG
1085: if (maxblks == 0 || maxblks < numblks)
1086: dbg_printf("maxblks = %d, numblks = %d\n",maxblks,numblks);
1087: #endif
1088: assert(maxblks && maxblks >= numblks);
1089: debug_assert(!PARSER);
1090: if (!dfo)
1091: #if TX86
1092: dfo = (block **) util_calloc(sizeof(block *),maxblks);
1093: #else
1094: dfo = (block **) MEM_PARF_CALLOC(sizeof(block *) * maxblks);
1095: #endif
1096: dfotop = numblks; /* assign numbers backwards */
1097: search(startblock);
1098: assert(dfotop <= numblks);
1099: /* Ripple data to the bottom of the array */
1100: if (dfotop) /* if not at bottom */
1101: { for (i = 0; i < numblks - dfotop; i++)
warning C4018: '<' : signed/unsigned mismatch
1102: { dfo[i] = dfo[i + dfotop];
1103: dfo[i]->Bdfoidx = i;
1104: }
1105: }
1106: dfotop = numblks - dfotop;
1107: #if 0
1108: for (i = 0; i < dfotop; i++)
1109: dbg_printf("dfo[%d] = 0x%x\n",i,dfo[i]);
1110: #endif
1111: }
1112:
1113: /******************************
1114: * Add block to dfo[], then its successors.
1115: */
1116:
1117: STATIC void search(block *b)
1118: { list_t l;
1119:
1120: assert(b);
1121: b->Bflags |= BFLvisited; // executed at least once
1122: for (l = b->Bsucc; l; l = list_next(l)) // for each successor
1123: { block *bs = list_block(l);
1124:
1125: assert(bs);
1126: if ((bs->Bflags & BFLvisited) == 0) // if not visited
1127: search(bs); // search it
1128: }
1129: dfo[--dfotop] = b; // add to dfo[]
1130: b->Bdfoidx = dfotop; // link back
1131: }
1132:
1133: /*************************
1134: * Remove blocks not marked as visited (they aren't in dfo[]).
1135: * A block is not in dfo[] if not visited.
1136: */
1137:
1138: STATIC void elimblks()
1139: { block **pb,*b;
1140: list_t s;
1141: block *bf;
1142:
1143: #ifdef DEBUG
1144: if (OPTIMIZER)
1145: { int n;
1146:
1147: n = 0;
1148: for (b = startblock; b; b = b->Bnext)
1149: n++;
1150: //dbg_printf("1 n = %d, numblks = %d, dfotop = %d\n",n,numblks,dfotop);
1151: assert(numblks == n);
1152: }
1153: #endif
1154:
1155: cmes("elimblks()\n");
1156: bf = NULL;
1157: for (pb = &startblock; (b = *pb) != NULL;)
1158: {
1159: if (((b->Bflags & BFLvisited) == 0) /* if block is not visited */
1160: && ((b->Bflags & BFLlabel) == 0) /* need label offset */
1161: )
1162: {
1163: /* for each marked successor S to b */
1164: /* remove b from S.Bpred. */
1165: /* Presumably all predecessors to b are unmarked also. */
1166: for (s = b->Bsucc; s; s = list_next(s))
1167: { assert(list_block(s));
1168: if (list_block(s)->Bflags & BFLvisited) /* if it is marked */
1169: list_subtract(&(list_block(s)->Bpred),b);
1170: }
1171: if (b->Balign && b->Bnext && b->Balign > b->Bnext->Balign)
1172: b->Bnext->Balign = b->Balign;
1173: *pb = b->Bnext; /* remove from linked list */
1174:
1175: b->Bnext = bf;
1176: bf = b; /* prepend to deferred list to free */
1177: cmes2("CHANGE: block %p deleted\n",b);
1178: changes++;
1179: }
1180: else
1181: pb = &((*pb)->Bnext);
1182: }
1183:
1184: // Do deferred free's of the blocks
1185: for ( ; bf; bf = b)
1186: { b = bf->Bnext;
1187: block_free(bf);
1188: numblks--;
1189: }
1190:
1191: cmes("elimblks done\n");
1192: assert(!OPTIMIZER || numblks == dfotop);
1193: }
1194:
1195: /**********************************
1196: * Merge together blocks where the first block is a goto to the next
1197: * block and the next block has only the first block as a predecessor.
1198: * Example:
1199: * e1; GOTO L2;
1200: * L2: return e2;
1201: * becomes:
1202: * L2: return (e1 , e2);
1203: * Returns:
1204: * # of merged blocks
1205: */
1206:
1207: STATIC int mergeblks()
1208: { int merge = 0,i;
1209:
1210: assert(OPTIMIZER);
1211: cmes("mergeblks()\n");
1212: for (i = 0; i < dfotop; i++)
warning C4018: '<' : signed/unsigned mismatch
1213: { block *b;
1214:
1215: b = dfo[i];
1216: if (b->BC == BCgoto)
1217: { block *bL2 = list_block(b->Bsucc);
1218:
1219: if (b == bL2)
1220: {
1221: Lcontinue:
warning C4102: 'Lcontinue' : unreferenced label
1222: continue;
1223: }
1224: assert(bL2->Bpred);
1225: if (!list_next(bL2->Bpred) && bL2 != startblock)
1226: { list_t bl;
1227: elem *e;
1228:
1229: if (b == bL2 || bL2->BC == BCasm)
1230: continue;
1231:
1232: if (
1233: #if SCPP
1234: bL2->BC == BCtry ||
1235: #endif
1236: bL2->BC == BC_try ||
1237: b->Btry != bL2->Btry)
1238: continue;
1239: #if SCPP
1240: // If any predecessors of b are BCasm, don't merge.
1241: for (bl = b->Bpred; bl; bl = list_next(bl))
1242: {
1243: if (list_block(bl)->BC == BCasm)
1244: goto Lcontinue;
1245: }
1246: #endif
1247:
1248: /* JOIN the elems */
1249: e = el_combine(b->Belem,bL2->Belem);
1250: if (b->Belem && bL2->Belem)
1251: e = doptelem(e,bc_goal[bL2->BC] | GOALagain);
1252: bL2->Belem = e;
1253: b->Belem = NULL;
1254:
1255: /* Remove b from predecessors of bL2 */
1256: list_free(&(bL2->Bpred),FPNULL);
1257: bL2->Bpred = b->Bpred;
1258: b->Bpred = NULL;
1259: /* Remove bL2 from successors of b */
1260: list_free(&b->Bsucc,FPNULL);
1261:
1262: /* fix up successor list of predecessors */
1263: for (bl = bL2->Bpred; bl; bl = list_next(bl))
1264: { register list_t bs;
1265:
1266: for (bs=list_block(bl)->Bsucc; bs; bs=list_next(bs))
1267: if (list_block(bs) == b)
1268: list_ptr(bs) = (void *)bL2;
1269: }
1270:
1271: merge++;
1272: cmes3("block %p merged with %p\n",b,bL2);
1273:
1274: if (b == startblock)
1275: { /* bL2 is the new startblock */
1276: block **pb;
1277:
1278: cmes("bL2 is new startblock\n");
1279: /* Remove bL2 from list of blocks */
1280: for (pb = &startblock; 1; pb = &(*pb)->Bnext)
1281: { assert(*pb);
1282: if (*pb == bL2)
1283: { *pb = bL2->Bnext;
1284: break;
1285: }
1286: }
1287:
1288: /* And relink bL2 at the start */
1289: bL2->Bnext = startblock->Bnext;
1290: startblock = bL2; /* new start */
1291:
1292: block_free(b);
1293: numblks--;
1294: break; /* dfo[] is now invalid */
1295: }
1296: }
1297: }
1298: }
1299: return merge;
1300: }
1301:
1302: /*******************************
1303: * Combine together blocks that are identical.
1304: */
1305:
1306: STATIC void blident()
1307: { block *bn;
1308: block *bnext;
1309:
1310: cmes("blident()\n");
1311: assert(startblock);
1312:
1313: #if SCPP
1314: // Determine if any asm blocks
1315: int anyasm = 0;
1316: for (bn = startblock; bn; bn = bn->Bnext)
1317: { if (bn->BC == BCasm)
1318: { anyasm = 1;
1319: break;
1320: }
1321: }
1322: #endif
1323:
1324: for (bn = startblock; bn; bn = bnext)
1325: { block *b;
1326:
1327: bnext = bn->Bnext;
1328: if (bn->Bflags & BFLnomerg)
1329: continue;
1330:
1331: for (b = bnext; b; b = b->Bnext)
1332: {
1333: /* Blocks are identical if: */
1334: /* BC match */
1335: /* not optimized for time or it's a return */
1336: /* (otherwise looprotate() is undone) */
1337: /* successors match */
1338: /* elems match */
1339: if (b->BC == bn->BC &&
1340: //(!OPTIMIZER || !(mfoptim & MFtime) || !b->Bsucc) &&
1341: (!OPTIMIZER || !(b->Bflags & BFLnomerg) || !b->Bsucc) &&
1342: list_equal(b->Bsucc,bn->Bsucc) &&
1343: #if SCPP || NTEXCEPTIONS
1344: b->Btry == bn->Btry &&
1345: #endif
1346: el_match(b->Belem,bn->Belem)
1347: )
1348: { /* Eliminate block bn */
1349: list_t bl;
1350:
1351: switch (b->BC)
1352: {
1353: case BCswitch:
1354: if (memcmp(b->BS.Bswitch,bn->BS.Bswitch,list_nitems(bn->Bsucc) * sizeof(*bn->BS.Bswitch)))
1355: continue;
1356: break;
1357:
1358: #if SCPP
1359: case BCtry:
1360: case BCcatch:
1361: #endif
1362: #if MARS
1363: case BCjcatch:
1364: #endif
1365: case BC_try:
1366: case BC_finally:
1367: case BCasm:
1368: Lcontinue:
1369: continue;
1370: }
1371: assert(!b->Bcode);
1372:
1373: for (bl = bn->Bpred; bl; bl = list_next(bl))
1374: { block *bp;
1375:
1376: bp = list_block(bl);
1377: if (bp->BC == BCasm)
1378: // Can't do this because of jmp's and loop's
1379: goto Lcontinue;
1380: }
1381:
1382: #if 0 && SCPP
1383: // Predecessors must all be at the same btry level.
1384: if (bn->Bpred)
1385: { block *bp;
1386:
1387: bp = list_block(bn->Bpred);
1388: btry = bp->Btry;
1389: if (bp->BC == BCtry)
1390: btry = bp;
1391: }
1392: else
1393: btry = NULL;
1394:
1395: for (bl = b->Bpred; bl; bl = list_next(bl))
1396: { block *bp;
1397:
1398: bp = list_block(bl);
1399: if (bp->BC != BCtry)
1400: bp = bp->Btry;
1401: if (btry != bp)
1402: goto Lcontinue;
1403: }
1404: #endif
1405:
1406: // if bn is startblock, eliminate b instead of bn
1407: if (bn == startblock)
1408: {
1409: goto Lcontinue; // can't handle predecessors to startblock
1410: bn = b;
1411: b = startblock; /* swap b and bn */
1412: }
1413:
1414: #if SCPP
1415: // Don't do it if any predecessors are ASM blocks, since
1416: // we'd have to walk the code list to fix up any jmps.
1417: if (anyasm)
1418: {
1419: for (bl = bn->Bpred; bl; bl = list_next(bl))
1420: { list_t bls;
1421: block *bp;
1422:
1423: bp = list_block(bl);
1424: if (bp->BC == BCasm)
1425: goto Lcontinue;
1426: for (bls=bp->Bsucc; bls; bls=list_next(bls))
1427: if (list_block(bls) == bn &&
1428: list_block(bls)->BC == BCasm)
1429: goto Lcontinue;
1430: }
1431: }
1432: #endif
1433:
1434: /* Change successors to predecessors of bn to point to */
1435: /* b instead of bn */
1436: for (bl = bn->Bpred; bl; bl = list_next(bl))
1437: { list_t bls;
1438: block *bp;
1439:
1440: bp = list_block(bl);
1441: for (bls=bp->Bsucc; bls; bls=list_next(bls))
1442: if (list_block(bls) == bn)
1443: { list_ptr(bls) = (void *)b;
1444: list_prepend(&b->Bpred,bp);
1445: }
1446: }
1447:
1448: /* Entirely remove predecessor list from bn. */
1449: /* elimblks() will delete bn entirely. */
1450: list_free(&(bn->Bpred),FPNULL);
1451:
1452: #ifdef DEBUG
1453: assert(bn->BC != BCcatch);
1454: if (debugc)
1455: dbg_printf("block B%d (%p) removed, it was same as B%d (%p)\n",
1456: bn->Bdfoidx,bn,b->Bdfoidx,b);
1457: #endif
1458: changes++;
1459: break;
1460: }
1461: }
1462: }
1463: }
1464:
1465: /**********************************
1466: * Split out return blocks so the returns can be combined into a
1467: * single block by blident().
1468: */
1469:
1470: STATIC void blreturn()
1471: {
1472: if (!(mfoptim & MFtime)) /* if optimized for space */
1473: {
1474: int retcount; /* number of return counts */
1475: block *b;
1476:
1477: retcount = 0;
1478:
1479: /* Find last return block */
1480: for (b = startblock; b; b = b->Bnext)
1481: { if (b->BC == BCret)
1482: retcount++;
1483: if (b->BC == BCasm)
1484: return; // mucks up blident()
1485: }
1486:
1487: if (retcount < 2) /* quit if nothing to combine */
1488: return;
1489:
1490: /* Split return blocks */
1491: for (b = startblock; b; b = b->Bnext)
1492: { if (b->BC != BCret)
1493: continue;
1494: #if SCPP || NTEXCEPTIONS
1495: // If no other blocks with the same Btry, don't split
1496: #if SCPP
1497: if (config.flags3 & CFG3eh)
1498: #endif
1499: {
1500: for (block *b2 = startblock; b2; b2 = b2->Bnext)
1501: {
1502: if (b2->BC == BCret && b != b2 && b->Btry == b2->Btry)
1503: goto L1;
1504: }
1505: continue;
1506: }
1507: L1: ;
1508: #endif
1509: if (b->Belem)
1510: { /* Split b into a goto and a b */
1511: block *bn;
1512:
1513: #ifdef DEBUG
1514: if (debugc)
1515: dbg_printf("blreturn: splitting block B%d\n",b->Bdfoidx);
1516: #endif
1517: numblks++;
1518: bn = block_calloc();
1519: bn->BC = BCret;
1520: bn->Bnext = b->Bnext;
1521: #if SCPP || NTEXCEPTIONS
1522: bn->Btry = b->Btry;
1523: #endif
1524: b->BC = BCgoto;
1525: b->Bnext = bn;
1526: list_append(&b->Bsucc,bn);
1527: list_append(&bn->Bpred,b);
1528:
1529: b = bn;
1530: }
1531: }
1532:
1533: blident(); /* combine return blocks */
1534: }
1535: }
1536:
1537: /*****************************************
1538: * Convert expression into a list.
1539: * Construct the list in reverse, that is, so that the right-most
1540: * expression occurs first in the list.
1541: */
1542:
1543: STATIC list_t bl_enlist(elem *e)
1544: { list_t el = NULL;
1545:
1546: if (e)
1547: {
1548: elem_debug(e);
1549: if (e->Eoper == OPcomma)
1550: { list_t el2;
1551: list_t pl;
1552:
1553: el2 = bl_enlist(e->E1);
1554: el = bl_enlist(e->E2);
1555: e->E1 = e->E2 = NULL;
1556: el_free(e);
1557:
1558: /* Append el2 list to el */
1559: assert(el);
1560: for (pl = el; list_next(pl); pl = list_next(pl))
1561: ;
1562: list_next(pl) = el2;
1563: }
1564: else
1565: list_prepend(&el,e);
1566: }
1567: return el;
1568: }
1569:
1570: /*****************************************
1571: * Take a list of expressions and convert it back into an expression tree.
1572: */
1573:
1574: STATIC elem * bl_delist(list_t el)
1575: { elem *e;
1576: list_t elstart = el;
1577:
1578: for (e = NULL; el; el = list_next(el))
1579: e = el_combine(list_elem(el),e);
1580: list_free(&elstart,FPNULL);
1581: return e;
1582: }
1583:
1584: /*****************************************
1585: * Do tail merging.
1586: */
1587:
1588: STATIC void bltailmerge()
1589: {
1590: cmes("bltailmerge()\n");
1591: assert(!PARSER && OPTIMIZER);
1592: if (!(mfoptim & MFtime)) /* if optimized for space */
1593: {
1594: block *b;
1595: block *bn;
1596: list_t bl;
1597: elem *e;
1598: elem *en;
1599:
1600: /* Split each block into a reversed linked list of elems */
1601: for (b = startblock; b; b = b->Bnext)
1602: b->Blist = bl_enlist(b->Belem);
1603:
1604: /* Search for two blocks that have the same successor list.
1605: If the first expressions both lists are the same, split
1606: off a new block with that expression in it.
1607: */
1608: for (b = startblock; b; b = b->Bnext)
1609: {
1610: if (!b->Blist)
1611: continue;
1612: e = list_elem(b->Blist);
1613: elem_debug(e);
1614: for (bn = b->Bnext; bn; bn = bn->Bnext)
1615: {
1616: if (b->BC == bn->BC &&
1617: list_equal(b->Bsucc,bn->Bsucc) &&
1618: bn->Blist &&
1619: el_match(e,(en = list_elem(bn->Blist)))
1620: #if SCPP || NTEXCEPTIONS
1621: && b->Btry == bn->Btry
1622: #endif
1623: )
1624: {
1625: switch (b->BC)
1626: {
1627: case BCswitch:
1628: if (memcmp(b->BS.Bswitch,bn->BS.Bswitch,list_nitems(bn->Bsucc) * sizeof(*bn->BS.Bswitch)))
1629: continue;
1630: break;
1631:
1632: #if SCPP
1633: case BCtry:
1634: case BCcatch:
1635: #endif
1636: #if MARS
1637: case BCjcatch:
1638: #endif
1639: case BC_try:
1640: case BC_finally:
1641: case BCasm:
1642: continue;
1643: }
1644:
1645: /* We've got a match */
1646: block *bnew;
1647:
1648: /* Create a new block, bnew, which will be the
1649: merged block. Physically locate it just after bn.
1650: */
1651: #ifdef DEBUG
1652: if (debugc)
1653: dbg_printf("tail merging: %p and %p\n", b, bn);
1654: #endif
1655: numblks++;
1656: bnew = block_calloc();
1657: bnew->Bnext = bn->Bnext;
1658: bnew->BC = b->BC;
1659: #if SCPP || NTEXCEPTIONS
1660: bnew->Btry = b->Btry;
1661: #endif
1662: if (bnew->BC == BCswitch)
1663: {
1664: bnew->BS.Bswitch = b->BS.Bswitch;
1665: b->BS.Bswitch = NULL;
1666: bn->BS.Bswitch = NULL;
1667: }
1668: bn->Bnext = bnew;
1669:
1670: /* The successor list to bnew is the same as b's was */
1671: bnew->Bsucc = b->Bsucc;
1672: b->Bsucc = NULL;
1673: list_free(&bn->Bsucc,FPNULL);
1674:
1675: /* Update the predecessor list of the successor list
1676: of bnew, from b to bnew, and removing bn
1677: */
1678: for (bl = bnew->Bsucc; bl; bl = list_next(bl))
1679: {
1680: list_subtract(&list_block(bl)->Bpred,b);
1681: list_subtract(&list_block(bl)->Bpred,bn);
1682: list_append(&list_block(bl)->Bpred,bnew);
1683: }
1684:
1685: /* The predecessors to bnew are b and bn */
1686: list_append(&bnew->Bpred,b);
1687: list_append(&bnew->Bpred,bn);
1688:
1689: /* The successors to b and bn are bnew */
1690: b->BC = BCgoto;
1691: bn->BC = BCgoto;
1692: list_append(&b->Bsucc,bnew);
1693: list_append(&bn->Bsucc,bnew);
1694:
1695: changes++;
1696:
1697: /* Find all the expressions we can merge */
1698: do
1699: {
1700: list_append(&bnew->Blist,e);
1701: el_free(en);
1702: list_pop(&b->Blist);
1703: list_pop(&bn->Blist);
1704: if (!b->Blist)
1705: goto nextb;
1706: e = list_elem(b->Blist);
1707: if (!bn->Blist)
1708: break;
1709: en = list_elem(bn->Blist);
1710: } while (el_match(e,en));
1711: }
1712: }
1713: nextb: ;
1714: }
1715:
1716: /* Recombine elem lists into expression trees */
1717: for (b = startblock; b; b = b->Bnext)
1718: b->Belem = bl_delist(b->Blist);
1719: }
1720: }
1721:
1722: /**********************************
1723: * Rearrange blocks to minimize jmp's.
1724: */
1725:
1726: STATIC void brmin()
1727: { block *b;
1728: block *bnext;
1729: list_t bl,blp;
1730:
1731: #if SCPP
1732: // Dunno how this may mess up generating EH tables.
1733: if (config.flags3 & CFG3eh) // if EH turned on
1734: return;
1735: #endif
1736:
1737: cmes("brmin()\n");
1738: debug_assert(startblock);
1739: for (b = startblock->Bnext; b; b = b->Bnext)
1740: {
1741: bnext = b->Bnext;
1742: if (!bnext)
1743: break;
1744: for (bl = b->Bsucc; bl; bl = list_next(bl))
1745: { block *bs;
1746:
1747: bs = list_block(bl);
1748: if (bs == bnext)
1749: goto L1;
1750: }
1751:
1752: // b is a block which does not have bnext as a successor.
1753: // Look for a successor of b for which everyone must jmp to.
1754:
1755: for (bl = b->Bsucc; bl; bl = list_next(bl))
1756: { block *bs;
1757: block *bn;
1758:
1759: bs = list_block(bl);
1760: for (blp = bs->Bpred; blp; blp = list_next(blp))
1761: { block *bsp;
1762:
1763: bsp = list_block(blp);
1764: if (bsp->Bnext == bs)
1765: goto L2;
1766: }
1767:
1768: // Move bs so it is the Bnext of b
1769: for (bn = bnext; 1; bn = bn->Bnext)
1770: {
1771: if (!bn)
1772: goto L2;
1773: if (bn->Bnext == bs)
1774: break;
1775: }
1776: #if 1
1777: bn->Bnext = NULL;
1778: b->Bnext = bs;
1779: for (bn = bs; bn->Bnext; bn = bn->Bnext)
1780: ;
1781: bn->Bnext = bnext;
1782: #else
1783: bn->Bnext = bs->Bnext;
1784: bs->Bnext = bnext;
1785: b->Bnext = bs;
1786: #endif
1787: cmes3("Moving block %p to appear after %p\n",bs,b);
1788: changes++;
1789: break;
1790:
1791: L2: ;
1792: }
1793:
1794:
1795: L1: ;
1796: }
1797: }
1798:
1799: /********************************
1800: * Check integrity of blocks.
1801: */
1802:
1803: #if 0
1804:
1805: STATIC void block_check()
1806: { block *b;
1807: list_t bl;
1808:
1809: for (b = startblock; b; b = b->Bnext)
1810: { int nsucc;
1811: int npred;
1812:
1813: nsucc = list_nitems(b->Bsucc);
1814: npred = list_nitems(b->Bpred);
1815: switch (b->BC)
1816: {
1817: case BCgoto:
1818: assert(nsucc == 1);
1819: break;
1820: case BCiftrue:
1821: assert(nsucc == 2);
1822: break;
1823: }
1824:
1825: for (bl = b->Bsucc; bl; bl = list_next(bl))
1826: { block *bs = list_block(bl);
1827: list_t bls;
1828:
1829: for (bls = bs->Bpred; 1; bls = list_next(bls))
1830: {
1831: assert(bls);
1832: if (list_block(bls) == b)
1833: break;
1834: }
1835: }
1836: }
1837: }
1838:
1839: #endif
1840:
1841: /***************************************
1842: * Do tail recursion.
1843: */
1844:
1845: STATIC void brtailrecursion()
1846: { block *b;
1847: block *bs;
1848: elem **pe;
1849:
1850: #if SCPP
1851: // if (tyvariadic(funcsym_p->Stype))
1852: return;
1853: return; // haven't dealt with struct params, and ctors/dtors
1854: #endif
1855: if (funcsym_p->Sfunc->Fflags3 & Fnotailrecursion)
1856: return;
1857: if (localgot)
1858: { /* On OSX, tail recursion will result in two OPgot's:
1859: int status5;
1860: struct MyStruct5 { }
1861: void rec5(int i, MyStruct5 s)
1862: {
1863: if( i > 0 )
1864: { status5++;
1865: rec5(i-1, s);
1866: }
1867: }
1868: */
1869:
1870: return;
1871: }
1872: for (b = startblock; b; b = b->Bnext)
1873: {
1874: if (b->BC == BC_try)
1875: return;
1876: pe = &b->Belem;
1877: block *bn = NULL;
1878: if (*pe &&
1879: (b->BC == BCret ||
1880: b->BC == BCretexp ||
1881: (b->BC == BCgoto && (bn = list_block(b->Bsucc))->Belem == NULL &&
1882: bn->BC == BCret)
1883: )
1884: )
1885: { elem *e;
1886:
1887: if (el_anyframeptr(*pe))
1888: return;
1889: while ((*pe)->Eoper == OPcomma)
1890: pe = &(*pe)->E2;
1891: e = *pe;
1892: if (OTcall(e->Eoper) &&
1893: e->E1->Eoper == OPvar &&
1894: e->E1->EV.sp.Vsym == funcsym_p)
1895: {
1896: //printf("before:\n");
1897: //elem_print(*pe);
1898: if (OTunary(e->Eoper))
1899: { *pe = el_long(TYint,0);
1900: }
1901: else
1902: { int si = 0;
1903: elem *e2 = NULL;
1904: *pe = assignparams(&e->E2,&si,&e2);
1905: *pe = el_combine(*pe,e2);
1906: }
1907: el_free(e);
1908: //printf("after:\n");
1909: //elem_print(*pe);
1910:
1911: if (b->BC == BCgoto)
1912: { list_subtract(&b->Bsucc,bn);
1913: list_subtract(&bn->Bpred,b);
1914: }
1915: b->BC = BCgoto;
1916: list_append(&b->Bsucc,startblock);
1917: list_append(&startblock->Bpred,b);
1918:
1919: // Create a new startblock, bs, because startblock cannot
1920: // have predecessors.
1921: numblks++;
1922: bs = block_calloc();
1923: bs->BC = BCgoto;
1924: bs->Bnext = startblock;
1925: list_append(&bs->Bsucc,startblock);
1926: list_append(&startblock->Bpred,bs);
1927: startblock = bs;
1928:
1929: cmes("tail recursion\n");
1930: changes++;
1931: return;
1932: }
1933: }
1934: }
1935: }
1936:
1937: /*****************************************
1938: * Convert parameter expression to assignment statements.
1939: */
1940:
1941: STATIC elem * assignparams(elem **pe,int *psi,elem **pe2)
1942: {
1943: elem *e = *pe;
1944:
1945: if (e->Eoper == OPparam)
1946: { elem *ea = NULL;
1947: elem *eb = NULL;
1948: elem *e2 = assignparams(&e->E2,psi,&eb);
1949: elem *e1 = assignparams(&e->E1,psi,&ea);
1950: e->E1 = NULL;
1951: e->E2 = NULL;
1952: e = el_combine(e1,e2);
1953: *pe2 = el_combine(eb,ea);
1954: }
1955: else
1956: { int si = *psi;
1957: Symbol *sp;
1958: Symbol *s;
1959: int op;
1960: elem *es;
1961: type *t;
1962:
1963: assert(si < globsym.top);
1964: sp = globsym.tab[si];
1965: s = symbol_genauto(sp->Stype);
1966: s->Sfl = FLauto;
1967: op = OPeq;
1968: if (e->Eoper == OPstrpar)
1969: {
1970: op = OPstreq;
1971: t = e->ET;
1972: elem *ex = e;
1973: e = e->E1;
1974: ex->E1 = NULL;
1975: el_free(ex);
1976: }
1977: es = el_var(s);
1978: es->Ety = e->Ety;
1979: e = el_bin(op,TYvoid,es,e);
1980: if (op == OPstreq)
1981: e->ET = t;
1982: *pe2 = el_bin(op,TYvoid,el_var(sp),el_copytree(es));
1983: (*pe2)->E1->Ety = es->Ety;
1984: if (op == OPstreq)
1985: (*pe2)->ET = t;
1986: *psi = ++si;
1987: *pe = NULL;
1988: }
1989: return e;
1990: }
1991:
1992: /****************************************************
1993: * Eliminate empty loops.
1994: */
1995:
1996: STATIC void emptyloops()
1997: {
1998: block *b;
1999:
2000: cmes("emptyloops()\n");
2001: for (b = startblock; b; b = b->Bnext)
2002: {
2003: if (b->BC == BCiftrue &&
2004: list_block(b->Bsucc) == b &&
2005: list_nitems(b->Bpred) == 2)
2006: { block *bpred;
2007: elem *einit;
2008: elem *erel;
2009: elem *einc;
2010:
2011: // Find predecessor to b
2012: bpred = list_block(b->Bpred);
2013: if (bpred == b)
2014: bpred = list_block(list_next(b->Bpred));
2015: if (!bpred->Belem)
2016: continue;
2017:
2018: // Find einit
2019: for (einit = bpred->Belem; einit->Eoper == OPcomma; einit = einit->E2)
2020: ;
2021: if (einit->Eoper != OPeq ||
2022: einit->E2->Eoper != OPconst ||
2023: einit->E1->Eoper != OPvar)
2024: continue;
2025:
2026: #if 1
2027: // Look for ((i += 1) < limit)
2028: erel = b->Belem;
2029: if (erel->Eoper != OPlt ||
2030: erel->E2->Eoper != OPconst ||
2031: erel->E1->Eoper != OPaddass)
2032: continue;
2033:
2034: einc = erel->E1;
2035: if (einc->E2->Eoper != OPconst ||
2036: einc->E1->Eoper != OPvar ||
2037: !el_match(einc->E1,einit->E1))
2038: continue;
2039:
2040: if (!tyintegral(einit->E1->Ety) ||
2041: el_tolong(einc->E2) != 1 ||
2042: el_tolong(einit->E2) >= el_tolong(erel->E2)
2043: )
2044: continue;
2045:
2046: {
2047: erel->Eoper = OPeq;
2048: erel->Ety = erel->E1->Ety;
2049: erel->E1 = el_selecte1(erel->E1);
2050: b->BC = BCgoto;
2051: list_subtract(&b->Bsucc,b);
2052: list_subtract(&b->Bpred,b);
2053: #ifdef DEBUG
2054: if (debugc)
2055: { WReqn(erel);
2056: dbg_printf(" eliminated loop\n");
2057: }
2058: #endif
2059: changes++;
2060: }
2061: #else
2062: // Find einc and erel
2063: if (b->Belem->Eoper != OPcomma)
2064: continue;
2065: einc = b->Belem->E1;
2066: erel = b->Belem->E2;
2067: if (einc->Eoper != OPaddass ||
2068: einc->E1->Eoper != OPvar ||
2069: einc->E2->Eoper != OPconst ||
2070: erel->Eoper != OPlt ||
2071: erel->E1->Eoper != OPvar ||
2072: erel->E2->Eoper != OPconst ||
2073: !el_match(einit->E1,einc->E1) ||
2074: !el_match(einit->E1,erel->E1)
2075: )
2076: continue;
2077:
2078: if (!tyintegral(einit->E1->Ety) ||
2079: el_tolong(einc->E2) != 1 ||
2080: el_tolong(einit->E2) >= el_tolong(erel->E2)
2081: )
2082: continue;
2083:
2084: {
2085: erel->Eoper = OPeq;
2086: erel->Ety = erel->E1->Ety;
2087: b->BC = BCgoto;
2088: list_subtract(&b->Bsucc,b);
2089: list_subtract(&b->Bpred,b);
2090: #ifdef DEBUG
2091: if (debugc)
2092: { WReqn(erel);
2093: dbg_printf(" eliminated loop\n");
2094: }
2095: #endif
2096: changes++;
2097: }
2098: #endif
2099: }
2100: }
2101: }
2102:
2103: /******************************************
2104: * Determine if function has any side effects.
2105: * This means, determine if all the function does is return a value;
2106: * no extraneous definitions or effects or exceptions.
2107: * A function with no side effects can be CSE'd. It does not reference
2108: * statics or indirect references.
2109: */
2110:
2111: STATIC int funcsideeffect_walk(elem *e);
2112:
2113: void funcsideeffects()
2114: {
2115: #if MARS
2116: block *b;
2117:
2118: //printf("funcsideeffects('%s')\n",funcsym_p->Sident);
2119: for (b = startblock; b; b = b->Bnext)
2120: {
2121: if (b->Belem && funcsideeffect_walk(b->Belem))
2122: goto Lside;
2123: }
2124:
2125: Lnoside:
warning C4102: 'Lnoside' : unreferenced label
2126: funcsym_p->Sfunc->Fflags3 |= Fnosideeff;
2127: //printf(" function '%s' has no side effects\n",funcsym_p->Sident);
2128: //return;
2129:
2130: Lside:
2131: //printf(" function '%s' has side effects\n",funcsym_p->Sident);
2132: ;
2133: #endif
2134: }
2135:
2136: #if MARS
2137:
2138: STATIC int funcsideeffect_walk(elem *e)
2139: { int op;
2140: Symbol *s;
2141:
2142: assert(e);
2143: elem_debug(e);
2144: if (typemask(e) & mTYvolatile)
2145: goto Lside;
2146: op = e->Eoper;
2147: switch (op)
2148: {
2149: case OPcall:
2150: case OPucall:
2151: if (e->E1->Eoper == OPvar &&
2152: tyfunc((s = e->E1->EV.sp.Vsym)->Stype->Tty) &&
2153: ((s->Sfunc && s->Sfunc->Fflags3 & Fnosideeff) || s == funcsym_p)
2154: )
2155: break;
2156: goto Lside;
2157:
2158: case OParray:
2159: case OPfield:
2160: goto Lside; // these can throw exceptions
2161:
2162: // Note: we should allow assignments to local variables as
2163: // not being a 'side effect'.
2164:
2165: default:
2166: assert(op < OPMAX);
2167: return OTsideff(op) ||
2168: (OTunary(op) && funcsideeffect_walk(e->E1)) ||
2169: (OTbinary(op) && (funcsideeffect_walk(e->E1) ||
2170: funcsideeffect_walk(e->E2)));
2171: }
2172: return 0;
2173:
2174: Lside:
2175: return 1;
2176: }
2177:
2178: #endif
2179:
2180: /*******************************
2181: * Determine if there are any OPframeptr's in the tree.
2182: */
2183:
2184: int el_anyframeptr(elem *e)
2185: {
2186: while (1)
2187: {
2188: if (OTunary(e->Eoper))
2189: e = e->E1;
2190: else if (OTbinary(e->Eoper))
2191: { if (el_anyframeptr(e->E2))
2192: return 1;
2193: e = e->E1;
2194: }
2195: else if (e->Eoper == OPframeptr)
2196: return 1;
2197: else
2198: break;
2199: }
2200: return 0;
2201: }
2202:
2203:
2204: #endif //!SPP
2205: