![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to optim.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv9 / jerq / sgs / optim|
Return to optim.c CVS log | Up to [Research Unix] / researchv9 / jerq / sgs / optim |
1.1 root 1: /* static char ID[] = "@(#) optim.c: 1.19 3/2/84"; */
2:
3: /* machine independent improvement routines */
4:
5: #include "optim.h"
6:
7: /* unit of allocatable space (in char *'s) */
8: #ifndef NSPACE
9: #define NSPACE 1024
10: #endif
11:
12: /* maximum number of labels referenced in a function */
13: #ifndef NUMLBLS
14: #define NUMLBLS 513
15: #endif
16: #define H_INCR 5
17: #define N_LBLS (NUMLBLS / H_INCR * H_INCR + 1)
18:
19: /* what to do if no input file specified */
20: #ifndef NOFILE
21: #define NOFILE() /* by default, use stdin */
22: #endif
23:
24: /* what to report if file-opening fails */
25: #ifndef FFILER
26: #define FFILER(S) "can't open %s\n"
27: #endif
28:
29: /* block of text */
30:
31: typedef struct block {
32: struct block *next; /* pointer to textually next block */
33: struct block *nextl; /* pointer to next executed block if no br */
34: struct block *nextr; /* pointer to next executed block if br */
35: struct block *ltest; /* for loop termination tests */
36: NODE *firstn; /* first text node of block */
37: NODE *lastn; /* last text node of block */
38: short index; /* block index for debugging purposes */
39: short length; /* number of instructions in block */
40: short indeg; /* number of text references */
41: short marked; /* marker for various things */
42: } BLOCK;
43:
44: /* symbol table entry */
45:
46: typedef struct {
47: char *cp; /* the symbol */
48: BLOCK *bl; /* the block it is defined in */
49: } LBL;
50:
51: /* data structures */
52:
53: NODE n0; /* header for text list */
54: NODE ntail = { NULL, NULL, TAIL }; /* trailer for text list */
55: REF r0; /* header for non-text reference list */
56: REF *lastref; /* pointer to last label reference */
57: static BLOCK b0; /* header for block list */
58: static BLOCK * Lastb = NULL; /* pointer to array of blocks previously
59: ** allocated for bldgr()
60: */
61: static LBL *Lbltbl; /* pointer to hash table of labels */
62: static int Numlbls; /* count of labels in hash table */
63: static BLOCK *Prevb; /* pointer to previous block during
64: traversal of list */
65: int fnum = 0; /* function counter */
66: int npass; /* pass-through-this-function counter */
67: static int idx; /* block index (for debugging) */
68:
69: /* space allocation control */
70:
71: static struct space_t { /* to manage space allocation */
72: struct space_t *next;
73: char *space[NSPACE - 1];
74: } *s0 = NULL, **Space;
75: static char *Lasta, *Lastx; /* pointers into allocatable space */
76: static long Maxu = 0, Maxm = 0, Maxa = 0;
77:
78: /* statistic counters */
79:
80: int ndisc = 0; /* instructions discarded */
81: int ninst = 0; /* total instructions */
82: static int nunr = 0; /* unreachable instructions */
83: int nmerge = 0; /* redundant instructions */
84: static int nsave = 0; /* branches saved */
85: static int nrot = 0; /* rotated loops */
86: static int noptim = 0; /* calls to optim */
87: #define PCASES 13
88: static int Pcase[PCASES + 1]; /* block types during reconstruction of text */
89: static struct added { /* to keep statistics on branches added */
90: struct added *next;
91: short fnum,
92: n_added;
93: } a0, *lastadd = &a0;
94:
95: /* debugging flags */
96:
97: static int bflag = 0; /* Blocks after initial construction */
98: int cflag = 0; /* do Conservative Comtail */
99: int dflag = 0; /* print live/Dead information if set */
100: static int eflag = 0; /* Execution trace */
101: int hflag = 0; /* peepHole disable if set */
102: static int lflag = 0; /* Labels deleted */
103: static int mflag = 0; /* Merged suffixes found */
104: static int pflag = 0; /* Path reconstruction trace */
105: int sflag = 0; /* Statistics (on stderr) */
106: static int uflag = 0; /* Unreachable code deleted */
107: static int wflag = 0; /* Window peephole trace */
108:
109: /* for readability */
110:
111: #ifdef MEMFCN /* replace strncpy when memset is available (5.0 and after) */
112: #define CLEAR(s, n) (void) memset((char *)(s), 0, (int)(n))
113: #else
114: #define CLEAR(s, n) (void) strncpy((char *)(s), "", (int)(n))
115: #endif
116: #define FATAL(S) fatal((S), (char *)NULL)
117: #define FLAG(L, LFLAG) case 'L': LFLAG = -1; continue;
118: #define ALLB(b, s) b = (s); b != NULL; b = b->next
119: #define PRCASE(N) if (pflag) { prcase(N, b); Pcase[N]++; }
120: #define TOPOFBLOCK(p) ((p) == NULL || islabel(p))
121: #define TRACE(F) if (eflag) PRINTF("%cStarting F[%d, %d]\n", \
122: CC, fnum, npass)
123: #define MPRINTF if (mflag) PRINTF
124: #define PRINDEX(P) (b->P == NULL ? 0 : b->P->index)
125: #define PSTAT(S, N) if ((N) > 0) FPRINTF(stderr, (S), (N))
126: #define FINDLBL(l) lblhash((l), (BLOCK *)NULL)
127: #define ADDLBL(l, b) (void) lblhash((l), (b))
128: #define ISUNCBL(b) ((b)->length == 1 && isuncbr((b)->lastn))
129: #define ISREMBL(b) (ISUNCBL(b) && !ishb((b)->lastn))
130: #define ISREMBR(p) (isbr(p) && !ishb(p))
131: #define RMBR(p) (ndisc++, nsave++, DELNODE(p))
132: /* TARGET follows branches until a non-branch is reached. However,
133: ** there is the danger that we will loop on ourselves if we encounter
134: ** an infinite loop. Solve the problem partially by preventing
135: ** self-loops.
136: */
137: #define TARGET(b) while (b->nextl != NULL && ISUNCBL(b->nextl) &&\
138: b->nextl != b) b = b->nextl
139: #define NEWBLK(n, type) ((type *) xalloc((n) * sizeof(type)))
140:
141: /* function declarations */
142:
143: extern char *label_left();
144: extern BLOCK *lblhash();
145: extern void bldgr(), putbr(), rmunrch(), modrefs(), indegree(), mkltbl();
146: #ifdef spflg
147: extern char * yysflgs();
148: #endif
149:
150: /************************************************************************/
151:
152: int
153: main(argc, argv) /* initialize, process parameters, control processing, etc. */
154: int argc; register char *argv[]; {
155:
156: extern void mustopen();
157: char usrflag[10];
158: int ufl = 0, i, fileseen = 0;
159:
160: /* process parameters on command line */
161:
162: while (--argc > 0) {
163: if (**++argv != '-') { /* alternate file(s) */
164: switch (fileseen) {
165: case 0: /* none yet, open input file */
166: mustopen(*argv, "r", stdin);
167: fileseen++;
168: continue;
169: case 1: /* input seen, open output file */
170: mustopen(*argv, "w", stdout);
171: fileseen++;
172: continue;
173: }
174: FATAL("too many filenames\n");
175: }
176: while ((i = *++*argv) != '\0') { /* debugging flags */
177: switch (tolower(i)) {
178: case 'i': /* alternate input file */
179: if (--argc <= 0)
180: FATAL("no argument for -I option\n");
181: mustopen(*++argv, "r", stdin);
182: break;
183: case 'o': /* alternate output file */
184: if (--argc <= 0)
185: FATAL("no argument for -O option\n");
186: mustopen(*++argv, "w", stdout);
187: break;
188: FLAG(b, bflag);
189: FLAG(c, cflag); /* kill comtail */
190: FLAG(d, dflag); /* display live/dead info */
191: FLAG(e, eflag);
192: FLAG(h, hflag); /* kill peephole optimizations */
193: FLAG(l, lflag);
194: FLAG(m, mflag);
195: FLAG(n, noptim); /* kill optimization */
196: FLAG(p, pflag);
197: FLAG(r, nrot); /* kill loop rotations */
198: FLAG(s, sflag);
199: FLAG(u, uflag);
200: FLAG(w, wflag);
201: default:
202: #ifdef spflg
203: if(spflg(i)) {
204: *argv = yysflgs(*argv);
205: }
206: else
207: #endif
208: usrflag[ufl++] = i;
209: continue;
210: }
211: break;
212: }
213: }
214: if (bflag | eflag | lflag | mflag | pflag | uflag | wflag)
215: setbuf(stdout, (char *)NULL); /* for easier debugging */
216: NOFILE(); /* if no input file specified */
217:
218: /* initialize everything */
219:
220: Lbltbl = NEWBLK(N_LBLS, LBL);
221: init();
222: usrflag[ufl] = '\0';
223: yyinit(usrflag);
224:
225: /* transfer to the machine dependent part */
226:
227: (void) yylex();
228: wrapup();
229:
230: /* print statistics if asked for */
231:
232: if (sflag) {
233: register struct added *a;
234:
235: for (a = a0.next; a != NULL; a = a->next)
236: FPRINTF(stderr, "%d branch(es) added to function %d\n",
237: a->n_added, a->fnum);
238: dstats(); /* machine dependent statistics */
239: PSTAT("%d unreachable instruction(s) deleted\n", nunr);
240: PSTAT("%d branch(es) saved\n", nsave);
241: PSTAT("%d instruction(s) merged\n", nmerge);
242: FPRINTF(stderr, "%d of %d total instructions discarded\n",
243: ndisc, ninst);
244: PSTAT("%d loop(s) rotated\n", nrot);
245: FPRINTF(stderr,
246: "%ld bytes used, %ld allocated\n%d function(s), %d optim(s)\n",
247: Maxm, Maxa, fnum - 1, noptim > 0 ? noptim : 0);
248: if (pflag && noptim > 0)
249: for (FPRINTF(stderr, "case\tnumber\n"),
250: i = 0; i <= PCASES; i++)
251: FPRINTF(stderr, "%2d\t%3d\n", i, Pcase[i]);
252: }
253: return (0);
254: }
255:
256: static void
257: mustopen(name, dir, file) char *name, *dir; FILE *file; {
258:
259: if (freopen(name, dir, file) == NULL)
260: fatal(FFILER(name), name);
261: }
262:
263: void
264: init() { /* reset pointers, counters, etc for next function */
265:
266: register struct space_t *p, *pp;
267: long maxa = N_LBLS * sizeof(LBL);
268:
269: if (Lastb != NULL) /* free bldgr's storage */
270: xfree((char *) Lastb);
271: Lastb = NULL; /* no memory now allocated */
272:
273: for (p = s0; p != NULL; p = pp) {
274: maxa += sizeof(struct space_t);
275: pp = p->next;
276: xfree((char *) p);
277: }
278: if ((Maxu += Numlbls * sizeof(LBL)) > Maxm)
279: Maxm = Maxu;
280: if (maxa > Maxa)
281: Maxa = maxa;
282: Maxu = 0;
283: Space = &s0;
284: s0 = NULL;
285: Lasta = Lastx = NULL;
286: n0.forw = &ntail;
287: ntail.back = &n0;
288: b0.firstn = b0.lastn = &n0;
289: r0.nextref = NULL;
290: lastref = &r0;
291: fnum++;
292: npass = 0;
293: }
294:
295: void
296: optim() { /* control improvement sequencing */
297:
298: if (noptim < 0)
299: return;
300: noptim++;
301: if (n0.forw != &ntail) {
302:
303: extern void rmlbls(), mrgbrs(), comtail(), reord(), rmbrs();
304: int onsave = nsave;
305:
306: rmlbls(); /* remove useless labels */
307: bldgr(true); /* build flow graph and call bboptim */
308: mrgbrs(); /* merge branches to branches */
309: rmunrch(false); /* remove unreachable code, don't preserve
310: ** block/node connectivity
311: */
312: comtail(); /* remove common tails */
313: reord(); /* reorder code */
314: rmbrs(); /* remove redundant branches */
315: rmlbls(); /* remove useless labels */
316: #ifdef LIVEDEAD
317: ldanal(); /* perform live/dead analysis */
318: #endif
319: if (sflag && onsave > nsave) {
320: register struct added *a = lastadd = lastadd->next =
321: NEWBLK(1, struct added);
322:
323: a->next = NULL;
324: a->fnum = fnum;
325: a->n_added = onsave - nsave;
326: }
327: }
328: npass++;
329: }
330:
331: static void
332: rmlbls() { /* remove unreferenced labels */
333:
334: register REF *r;
335: register NODE *p;
336: register char *s;
337:
338: TRACE(rmlbls);
339:
340: clrltbl();
341:
342: /* add references from data section */
343:
344: for (r = r0.nextref; r != NULL; r = r->nextref)
345: ADDLBL(r->lab, &b0);
346:
347: /* add references from branches in text section */
348:
349: for (ALLN(p))
350: if ((isbr(p) || ISLABREF(p)) && (s = getp(p)) != NULL)
351: ADDLBL(s, &b0);
352:
353: /* delete non-hard labels that are not now in the label table */
354:
355: for (ALLN(p))
356: if (islabel(p) && !ishl(p) && FINDLBL(p->ops[0]) == NULL) {
357: if (lflag)
358: PRINTF("%clabel %s removed\n", CC, p->ops[0]);
359: DELNODE(p);
360: }
361:
362: }
363:
364: /* This routine attempts to economize on space be allocating a hunk
365: ** of storage big enough for all program blocks. It deallocates that
366: ** hunk on the next call in hopes it can be reused.
367: */
368:
369: static void
370: bldgr(opt) boolean opt; { /* build flow graph of procedure */
371:
372: register BLOCK *b = &b0;
373: register NODE *p;
374:
375: TRACE(bldgr);
376:
377: if (Lastb != NULL) /* deallocate old array, if any */
378: xfree((char *)Lastb);
379:
380: /* Count number of blocks so we can allocate an array */
381:
382: idx = 0; /* use this to count blocks */
383: p = n0.forw; /* point at first node */
384: while (p != &ntail)
385: {
386: idx++; /* count one more block */
387: while (islabel(p)) /* skip leading labels */
388: p = p->forw;
389:
390: for ( ; p != &ntail && !islabel(p); p = p->forw) {
391: if (isbr(p)) {
392: p = p->forw;
393: break;
394: }
395: }
396: }
397:
398: /* idx is now the number of blocks. Allocate array. */
399:
400: Lastb = (BLOCK *) xalloc(idx * sizeof(BLOCK));
401:
402: /* now build the flow graph */
403:
404: idx = 0;
405: b = b0.next = Lastb; /* point at prospective first block */
406: for (p = n0.forw; p != &ntail; ) {
407:
408: register NODE *prevn = p->back;
409:
410: b->next = b + 1; /* "next" will be physically next */
411: b->index = ++idx;
412: b->length = b->indeg = 0;
413:
414: /* a block starts with 0 or more labels */
415:
416: while (islabel(p))
417: p = p->forw;
418:
419: /* followed by 0 or more non-branch instructions
420: terminated with a branch or before another label */
421:
422: for ( ; p != &ntail && !islabel(p); p = p->forw) {
423: b->length++;
424: if (isbr(p)) {
425: p = p->forw;
426: break;
427: }
428: }
429: if (opt) { /* do dependent basic-block optimization */
430:
431: int omit = bboptim(prevn->forw, p->back);
432: if (omit > b->length)
433: omit = b->length;
434: b->length -= omit;
435: ndisc += omit;
436: }
437: b->lastn = p->back;
438: if ((b->firstn = prevn->forw) != p) /* if non-empty block */
439: b++; /* we will next do next block */
440: }
441: b[-1].next = NULL; /* (assumes at least one block) next
442: ** pointer of last block we filled in
443: ** is NULL
444: */
445:
446: mkltbl(); /* make label table with only definitions */
447:
448: /* set branch pointers */
449:
450: for (ALLB(b, b0.next)) {
451: char *s;
452:
453: p = b->lastn;
454: b->nextl = b->next;
455: b->nextr = isbr(p) && (s = getp(p)) != NULL ?
456: FINDLBL(s) : NULL;
457: if (isuncbr(p)) {
458: b->nextl = b->nextr;
459: b->nextr = NULL;
460: }
461: if (bflag) {
462: PRINTF(
463: "%c\n%cblock %d (left: %d, right: %d, length: %d)\n%cfirst:\t",
464: CC, CC, b->index, PRINDEX(nextl), PRINDEX(nextr),
465: b->length, CC);
466: prinst(b->firstn);
467: PRINTF("%clast:\t", CC);
468: prinst(p);
469: }
470: }
471: }
472:
473: static void
474: mrgbrs() { /* merge branches to unconditional branches */
475:
476: register BLOCK *b, *bb;
477:
478: TRACE(mrgbrs);
479:
480: /* merge unconditional branches to their destinations */
481:
482: for (ALLB(b, b0.next))
483: if ((bb = b->nextl) == b->next) { /* fall-through */
484: if ((b = bb) == NULL)
485: break;
486: }
487: else if (bb != NULL && bb != b &&
488: islabel(b->firstn) && ISREMBL(b)) {
489: ndisc++;
490: nsave++;
491: modrefs(b->lastn->back, b, bb);
492: }
493:
494: /*
495: * It is assumed that "ret" is an unconditional branch;
496: * that getp on a "ret" returns NULL; that this can be
497: * placed on an unconditional branch ("jbr");
498: * that prinst() will convert "jbr NULL" back to "ret";
499: * but that the NULL
500: * cannot be placed on a conditional branch ("jne").
501: * (NULL is also returned by a multi-way branch (switch).)
502: */
503:
504: for (ALLB(b, b0.next)) {
505:
506: char *t;
507: register NODE *p = b->lastn;
508:
509: if (!isbr(p))
510: continue;
511: if (isuncbr(p))
512: while ((bb = b->nextl) != NULL && bb != bb->nextl &&
513: ISREMBL(bb)) {
514: register NODE *pp = bb->lastn;
515:
516: if ((t = getp(pp)) != NULL)
517: putp(p, t);
518: else { /* pp is a dead-end */
519: #ifdef MEMFCN
520: (void) memcpy((char *)p->ops,
521: (char *)pp->ops,
522: sizeof(pp->ops));
523: #else
524: register char **b_p = p->ops,
525: **bb_p = pp->ops;
526: register int i = MAXOPS + 1;
527:
528: while (--i >= 0)
529: *b_p++ = *bb_p++;
530: #endif
531: p->op = pp->op;
532: }
533: b->nextl = bb->nextl;
534: }
535: else
536: while ((bb = b->nextr) != NULL && bb != bb->nextl &&
537: ISREMBL(bb) && (t = getp(bb->lastn)) != NULL) {
538: putp(p, t);
539: b->nextr = bb->nextl;
540: }
541: }
542: }
543:
544: static void
545: comtail() { /* merge common tails from code blocks */
546:
547: boolean changed;
548:
549: TRACE(comtail);
550:
551: do {
552: extern boolean chktail();
553: register BLOCK *bi, *bj, *bi0, *bj0;
554:
555: changed = false;
556: if (cflag) /* for conservative analysis only */
557: indegree(); /* compute indegree (0 from bldgr()) */
558: for (ALLB(bi, b0.next)) { /* compute a key for each block */
559: bi->marked = 0;
560: if (bi->length == 1 && isbr(bi->lastn))
561: continue;
562: bi0 = bi;
563: if (isbr(bi->lastn) && !isuncbr(bi->lastn)) {
564: TARGET(bi0);
565: bi->marked += bi0->lastn->op;
566: }
567: bi->marked += bi0->nextl - &b0;
568: }
569: for (ALLB(bi, b0.next)) {
570: int cond_br;
571:
572: if (!bi->marked)
573: continue;
574: for (ALLB(bj, bi->next)) {
575: if (bi->marked != bj->marked)
576: continue; /* quick sieve on key */
577: if (bi->nextr != bj->nextr)
578: continue;
579: bi0 = bi; bj0 = bj;
580: /* if both blocks end in conditional branches,
581: * look ahead for left targets */
582: if (cond_br =
583: isbr(bj->lastn) && !isuncbr(bj->lastn)) {
584: if (bi->lastn->op != bj->lastn->op)
585: continue;
586: if(bi->nextr == NULL &&
587: !same(bi->lastn,bj->lastn))
588: continue;
589: TARGET(bi0);
590: TARGET(bj0);
591: }
592: /* blocks must fall through to same place */
593: if (bi0->nextl != bj0->nextl)
594: continue;
595: /* dead-end branches must have same text */
596: if (bi0->nextl == NULL &&
597: !same(bi0->lastn, bj0->lastn))
598: continue;
599: if (chktail(bi, bj, bi0->nextl) == true)
600: changed = true;
601: }
602: }
603: } while (changed == true);
604: }
605:
606: static boolean
607: chktail(bi, bj, bl) /* merge tails of bi-> and bj-> */
608: register BLOCK *bi, *bj; BLOCK *bl; {
609:
610: extern void rmtail();
611: register BLOCK *bn;
612: NODE *pi = bi->lastn, *pj = bj->lastn, *firstn, *lastn, *pb = NULL;
613: int length = 0, isbri = 0, isbrj = 0;
614:
615: /* pi and pj scan backwards through blocks bi and bj
616: until difference or no more code */
617:
618: if (isbr(pi)) { /* trailing branches have already been matched */
619: pb = pi;
620: pi = pi->back;
621: isbri++;
622: }
623: if (isbr(pj)) {
624: pb = pj;
625: pj = pj->back;
626: isbrj++;
627: }
628: for (firstn = lastn = pj; !TOPOFBLOCK(pi) && !TOPOFBLOCK(pj) &&
629: same(pi, pj) == true; length++) {
630: firstn = pj;
631: pi = (pi == bi->firstn) ? NULL : pi->back;
632: pj = (pj == bj->firstn) ? NULL : pj->back;
633: }
634: if (length == 0)
635: return (false);
636:
637: /* if blocks identical, change references to one to the other */
638:
639: if (TOPOFBLOCK(pi) && TOPOFBLOCK(pj)) {
640: isbri = 0;
641: modrefs(pj, bj, bn = bi);
642: MPRINTF("%cblock %d merged into block %d and deleted\n",
643: CC, bj->index, bi->index);
644: }
645:
646: /*
647: * Conservative common-tail merging avoids adding a branch to
648: * achieve a merge. It merges only blocks which join with no other
649: * blocks joining &at that point, so that the joining branch is merely
650: * raised above the common tail, and no new branch is added.
651: */
652:
653: else if (cflag && (bl == NULL || bl->indeg > 2))
654: return (false); /* conservative common tails */
655:
656: /* if one block is a tail of the other, remove the tail from the
657: larger block and make it reference the smaller */
658:
659: else if (TOPOFBLOCK(pi)) {
660: isbri = 0;
661: bj->lastn = pj;
662: bj->length -= length + isbrj;
663: bj->nextl = bn = bi;
664: rmtail(bj);
665: }
666: else if (TOPOFBLOCK(pj)) {
667: isbrj = 0;
668: bi->lastn = pi;
669: bi->length -= length + isbri;
670: bi->nextl = bn = bj;
671: rmtail(bi);
672: }
673:
674: /* otherwise make a new block, remove tails from common blocks and
675: make them reference the new block */
676:
677: else {
678: bi->lastn = pi;
679: bj->lastn = pj;
680: bi->length -= length + isbri;
681: bj->length -= length + isbrj;
682: bn = GETSTR(BLOCK);
683: *bn = *bj;
684: bn->firstn = firstn;
685: bn->lastn = lastn;
686: bn->length = length;
687: bn->index = ++idx;
688: bn->indeg = 2;
689: bi->nextl = bj->nextl = bj->next = bn;
690: bi->nextr = bj->nextr = NULL;
691: MPRINTF("%ctails of %d and %d merged into new block %d\n",
692: CC, bi->index, bj->index, idx);
693: }
694: if (pb != NULL && !isbr(bn->lastn)) { /* save final branch */
695: ndisc--;
696: nsave--;
697: bn->length++;
698: pb->back = bn->lastn;
699: bn->lastn = bn->lastn->forw = pb;
700: }
701:
702: #ifdef IDVAL
703: for (pb = bn->firstn; pb != NULL; pb = pb->forw) {
704: pb->uniqid = IDVAL;
705: if (pb == bn->lastn)
706: break;
707: }
708: #endif
709:
710: ndisc += length + isbri + isbrj;
711: nmerge += length;
712: nsave += isbri + isbrj; /* don't blame resequence for added branch */
713: MPRINTF("%c%d instruction(s) common to blocks %d and %d\n",
714: CC, length, bi->index, bj->index);
715: return (true);
716: }
717:
718: static void
719: rmtail(b) register BLOCK *b; { /* remove tail of b */
720:
721: b->nextr = NULL;
722: MPRINTF("%ctail of block %d deleted\n", CC, b->index);
723: }
724:
725: static void
726: modrefs(pi, bi, bj) /* change all refs from bi to bj */
727: register NODE *pi; register BLOCK *bi, *bj; {
728:
729: register BLOCK *b;
730:
731: if (pi != NULL) { /* transfer labels, if any, from bi to bj */
732: /* bi->firstn points to the first label to be transferred,
733: * pi points to the last. */
734: bj->firstn->back = pi;
735: pi->forw = bj->firstn;
736: bj->firstn = bi->firstn;
737: for ( ; ; pi = pi->back) { /* update the label table */
738: ADDLBL(pi->ops[0], bj);
739: if (pi == bi->firstn)
740: break;
741: }
742: }
743: for (ALLB(b, &b0)) { /* update the block structure */
744: if (b->next == bi)
745: b->next = bi->next;
746: if (b->nextl == bi)
747: b->nextl = bj;
748: if (b->nextr == bi)
749: b->nextr = bj;
750: }
751: }
752:
753: static void
754: reord() { /* reorder code */
755:
756: extern BLOCK *reord1();
757: extern void findlt();
758: register BLOCK *b;
759:
760: TRACE(reord);
761:
762: for (ALLB(b, b0.next)) {
763: b->ltest = NULL;
764: b->marked = 0; /* mark all blocks as unprocessed */
765: }
766: indegree(); /* compute indegree */
767:
768: if (nrot >= 0)
769: findlt(); /* find rotatable loops */
770:
771: /* tie blocks back together */
772:
773: if (pflag)
774: PRINTF("%cblock\tleft\tright\tcase\tlabels\n", CC);
775: Prevb = &b0;
776: for (b = b0.next; b != NULL; )
777: b = reord1(b);
778: if (Prevb->nextl != NULL)
779: putbr(Prevb);
780: Prevb->lastn->forw = &ntail;
781: ntail.back = Prevb->lastn; /* tack on tail node to text list */
782:
783: mkltbl(); /* make label table with only definitions */
784: rmunrch(true); /* remove unreachable code */
785: }
786:
787: static void
788: indegree() { /* compute indegree */
789:
790: register BLOCK *b, *bb;
791:
792: for (ALLB(b, b0.next))
793: b->indeg = 0;
794: for (ALLB(b, b0.next)) { /* compute indegree */
795: if ((bb = b->nextl) != NULL)
796: bb->indeg++;
797: if ((bb = b->nextr) != NULL)
798: bb->indeg++;
799: }
800: }
801:
802: static void
803: findlt() { /* find rotatable loops */
804:
805: /*
806: * To identify the top and termination-test of a rotatable loop:
807: * Look at the target of an unconditional backward branch.
808: * If it has only one reference, then it isn't the start of a loop.
809: * Then look at all intermediate blocks in lexical order
810: * to find a conditional jump past the backward branch.
811: * This is a very simplistic heuristic approach, because the loop
812: * test is actually never made.
813: * But it seems to give reasonable results rather rapidly.
814: * If there is more than one exit from the loop,
815: * rotate at the exit nearest to the bottom,
816: * in order to keep the elements of a compound test near each
817: * other (in case of window optimization)
818: * and near the bottom (in case of span-dependent branches).
819: */
820:
821: register BLOCK *b, *bl, *bb, *br;
822:
823: if (bflag)
824: PRINTF("%cltests are:", CC);
825: for (ALLB(b, b0.next)) {
826: if (b->nextr != NULL || (bl = b->nextl) == NULL ||
827: bl->indeg < 2 || bl->index > b->index || bl->ltest != NULL)
828: continue;
829: for (bb = bl; bb != NULL && bb->index < b->index; bb = bb->next)
830: if ((br = bb->nextr) != NULL && br->index > b->index)
831: bl->ltest = bb;
832: if (bflag && bl->ltest != NULL)
833: PRINTF(" %d/%d", bl->index, bl->ltest->index);
834: }
835: if (bflag)
836: PUTCHAR('\n');
837: }
838:
839: #define B_EXIT 2
840:
841: static BLOCK *
842: reord1(b) register BLOCK *b; {
843:
844: extern BLOCK *nextbr();
845: extern void prcase();
846: register BLOCK *bl, *br, *blt;
847:
848: /* top of rotatable loop */
849: /* don't rotate unless there already must be a branch to the entry */
850:
851: if (b->ltest != NULL && b != Prevb->nextl &&
852: (bl = b->ltest->nextl)->ltest == NULL && !bl->marked) {
853: b->ltest = NULL;
854: nrot++;
855: return (bl);
856: }
857:
858: /* mark block as processed and tie it in */
859:
860: b->marked++;
861: if (b != Prevb->nextl)
862: putbr(Prevb);
863: Prevb->lastn->forw = b->firstn;
864: b->firstn->back = Prevb->lastn;
865: Prevb = b;
866:
867: /* dead-end block */
868:
869: if ((bl = b->nextl) == NULL) {
870: PRCASE(0);
871: return (nextbr(b));
872: }
873:
874: bl->indeg--;
875: if ((br = b->nextr) != NULL)
876: br->indeg--;
877:
878: /* top of rotatable loop */
879:
880: if ((blt = bl->ltest) != NULL && blt->nextl->ltest == NULL &&
881: !blt->nextl->marked && !blt->nextr->marked && outdeg(bl) <= 1) {
882: PRCASE(1);
883: b = blt->nextl;
884: bl->ltest = NULL;
885: nrot++;
886: return (b);
887: }
888:
889: if (br == NULL) { /* unconditional branch or conditional to dead-end */
890:
891: if (!bl->marked) { /* to unprocessed block */
892:
893: if (bl->indeg <= 0) { /* with indeg 1 */
894: PRCASE(2);
895: return (bl);
896: }
897:
898: /* branch to block with indeg > 1
899: that originally followed this one */
900:
901: if (bl == b->next) {
902: PRCASE(3);
903: return (bl);
904: }
905:
906: /* branch to dead-end block */
907:
908: if (bl->nextl == NULL) {
909: PRCASE(4);
910: return (bl);
911: }
912:
913: }
914:
915: /* all other unconditional branches */
916:
917: PRCASE(5);
918: return (nextbr(b));
919: }
920:
921: /* conditional branch to processed block */
922:
923: if (br->marked && !bl->marked) {
924:
925: /* fall through to unprocessed block with indeg = 1 */
926:
927: if (bl->indeg <= 0) {
928: PRCASE(6);
929: return (bl);
930: }
931:
932: /* fall through to unprocessed block with indeg > 1
933: that originally followed this one */
934:
935: if (bl == b->next) {
936: PRCASE(7);
937: return (bl);
938: }
939: }
940:
941: /* reversible conditional branch to unprocessed block,
942: fall through to processed block */
943:
944: if (bl->marked && !br->marked && isrev(b->lastn)) {
945: revbr(b->lastn);
946: putp(b->lastn, label_left(b));
947: b->nextr = b->nextl;
948: b->nextl = br;
949: PRCASE(8);
950: return (br->indeg <= 0 ? br : nextbr(b));
951: }
952:
953: /* all other conditional branches that have one leg or the
954: other going to processed blocks */
955:
956: if (bl->marked || br->marked) {
957: PRCASE(9);
958: return (nextbr(b));
959: }
960:
961: /* fall through to block with indeg = 1
962: but not if it is an unlabeled unconditional transfer */
963:
964: if (bl->indeg <= 0 && !(isuncbr(bl->firstn) && isrev(b->lastn))) {
965: PRCASE(10);
966: return (bl);
967: }
968:
969: /* reversible branch to block with indeg = 1 */
970:
971: if (br->indeg <= 0 && isrev(b->lastn)) {
972: revbr(b->lastn);
973: putp(b->lastn, label_left(b));
974: b->nextr = b->nextl;
975: b->nextl = br;
976: PRCASE(11);
977: return (br);
978: }
979:
980: /* fall through to block with indeg > 1 that
981: originally followed this block */
982:
983: if (bl == b->next) {
984: PRCASE(12);
985: return (bl);
986: }
987:
988: /* everything else */
989:
990: PRCASE(13);
991: return (nextbr(b));
992: }
993:
994: /* Routine outdeg works in conjunction with loop rotation. It uses a
995: ** heuristic to determine how many of the loop exit target's remaining
996: ** incoming arcs are due to exits from the loop that is to be rotated.
997: ** Outdeg is called with a pointer to the top-of-loop block. It scans
998: ** lexically through the blocks that follow the top (much like findlt())
999: ** until
1000: ** 1) there is no next block
1001: ** 2) the "left" path points at the loop top, indicating the block
1002: ** is the loop end
1003: ** 3) the new block's index is at or past the loop target (since
1004: ** findlt calls something a loop exit when the block index
1005: ** of the "right" path is beyond the loop end)
1006: **
1007: ** As we scan through the blocks lexically, we decrement the effective
1008: ** indegree of the loop target whenever we find a "right" path that
1009: ** goes to the target from an unmarked block. (If the block was marked,
1010: ** its contribution to indegree has already been accounted for.)
1011: */
1012:
1013: static int
1014: outdeg(top)
1015: BLOCK * top; /* pointer to top of loop */
1016: {
1017: BLOCK * target = top->ltest->nextr; /* loop exit target */
1018: BLOCK * bp; /* scanning block pointer */
1019: int indegree = target->indeg; /* in-degree of target block */
1020:
1021: /* As a short-circuit, discontinue searching when the new indegree
1022: ** is <= 1
1023: */
1024:
1025: if (indegree <= 1)
1026: return(indegree);
1027:
1028: for (bp = top;
1029: bp != NULL /* have a block */
1030: && bp->nextl != top /* it doesn't close the loop */
1031: && bp->index < target->index ; /* it isn't past the target */
1032: bp = bp->next)
1033: {
1034: if (
1035: ! bp->marked /* the block is unmarked */
1036: && bp->nextr == target /* it branches cond. to target */
1037: && --indegree <= 1 /* time to quit */
1038: )
1039: break;
1040: }
1041:
1042: return(indegree); /* return effective indegree */
1043: }
1044:
1045:
1046: static void
1047: prcase(n, b) int n; register BLOCK *b; { /* print information during reord */
1048:
1049: register NODE *p;
1050:
1051: PRINTF("%c%d\t%d\t%d\t%d", CC, b->index,
1052: PRINDEX(nextl), PRINDEX(nextr), n);
1053: for (p = b->firstn; islabel(p); p = p->forw)
1054: PRINTF("\t%s", p->ops[0]);
1055: PRINTF("\n");
1056: }
1057:
1058: static BLOCK *
1059: nextbr(b) register BLOCK *b; { /* select next block to process */
1060:
1061: register BLOCK *bb;
1062:
1063: /* first look for orphan blocks (no more references) from the top */
1064:
1065: for (ALLB(bb, b0.next))
1066: if (!bb->marked && bb->indeg <= 0)
1067: return (bb);
1068:
1069: /* now look for unmarked block with live consequent (circularly) */
1070:
1071: for (bb = b->next; bb != b; bb = bb->next)
1072: if (bb == NULL) /* circular scan for next block */
1073: bb = &b0;
1074: else if (!bb->marked &&
1075: bb->nextl != NULL && !bb->nextl->marked)
1076: return (bb);
1077:
1078: /* now look for any unmarked block (circularly) */
1079:
1080: for (bb = b->next; bb != b; bb = bb->next)
1081: if (bb == NULL) /* circular scan for next block */
1082: bb = &b0;
1083: else if (!bb->marked)
1084: return (bb);
1085:
1086: return (NULL); /* no more blocks to process */
1087: }
1088:
1089: static void
1090: putbr(b) register BLOCK *b; { /* append a branch to b->nextl onto b */
1091:
1092: register NODE *p, *pl = b->lastn;
1093: char *s;
1094:
1095: if (b == &b0 || isuncbr(pl))
1096: return;
1097: ndisc--;
1098: nsave--;
1099: b->length++;
1100: p = Saveop(0, (char *)NULL, 0, GHOST); /* make node but don't link */
1101: b->lastn = pl->forw = p; /* link at end of this block */
1102: p->back = pl;
1103: s = label_left(b); /* get destination label, in 2 steps */
1104: setbr(p, s); /* in case setbr is a macro which double-evaluates */
1105: }
1106:
1107: static char *
1108: label_left(b) register BLOCK *b; { /* get label of b->nextl */
1109:
1110: register NODE *pf, *p;
1111: register BLOCK *bl;
1112:
1113: if ((bl = b->nextl) == NULL)
1114: FATAL("label of nonexistent block requested\n");
1115: for ( ; ISUNCBL(bl) && bl->nextl != bl; bl = bl->nextl)
1116: if (bl->nextl == NULL) {
1117:
1118: char *s = getp(bl->lastn);
1119:
1120: if (s == NULL) /* no target */
1121: break;
1122: b->nextl = NULL; /* dead-end */
1123: return (s);
1124: }
1125: b->nextl = bl; /* re-aim b at final target */
1126: pf = bl->firstn;
1127: if (islabel(pf) && !ishl(pf))
1128: return (pf->ops[0]);
1129: p = Saveop(0, newlab(), 0, GHOST); /* make node but don't link */
1130: p->forw = pf; /* link at beginning of this block */
1131: p->back = pf->back;
1132: if (bl->marked) /* this block already processed by reord */
1133: pf->back->forw = p;
1134: bl->firstn = pf->back = p;
1135: setlab(p);
1136: return (p->ops[0]);
1137: }
1138:
1139: static void
1140: rmunrch(preserve) boolean preserve; { /* remove unreachable code */
1141:
1142: extern void reach();
1143: register REF *r;
1144: register BLOCK *b, *prevb;
1145:
1146: TRACE(rmunrch);
1147:
1148: if (b0.next == NULL)
1149: return;
1150: for (ALLB(b, b0.next))
1151: b->marked = 0;
1152: reach(b0.next); /* mark all blocks reachable from initial block */
1153:
1154: /* mark all blocks reachable from hard-label blocks */
1155:
1156: for (ALLB(b, b0.next))
1157: if (!b->marked && ishlp(b->firstn))
1158: reach(b);
1159:
1160: /* mark all blocks reachable from non-text references */
1161:
1162: for (r = r0.nextref; r != NULL; r = r->nextref)
1163: if ((b = FINDLBL(r->lab)) != NULL && !b->marked)
1164: reach(b);
1165:
1166: for (ALLB(b, b0.next)) /* remove unmarked blocks */
1167: if (b->marked)
1168: prevb = b;
1169: else {
1170: ndisc += b->length;
1171: if (ISUNCBL(b) && islabel(b->firstn))
1172: nsave++;
1173: else {
1174: if (uflag)
1175: PRINTF("%cunreachable block %d removed\n",
1176: CC, b->index);
1177: nunr += b->length;
1178: }
1179: if (preserve) { /* node sequence must be preserved */
1180: b->firstn->back->forw = b->lastn->forw;
1181: b->lastn->forw->back = b->firstn->back;
1182: }
1183: prevb->next = b->next;
1184: }
1185: }
1186:
1187: static void
1188: reach(b) register BLOCK *b; { /* recursively mark reachable blocks */
1189:
1190: register BLOCK *bb;
1191:
1192: b->marked++;
1193:
1194: /*
1195: * Link around the second of successive removable branches with same
1196: * op-codes; multi-way branches (switches) must be identical in text.
1197: */
1198:
1199: while ((bb = b->nextl) != NULL && !bb->marked && bb->length == 1 &&
1200: bb->lastn->op == b->lastn->op && ISREMBR(bb->lastn)) {
1201: if(!(isuncbr(bb->lastn) ||
1202: bb->nextr != NULL || same(bb->lastn, b->lastn)))
1203: break;
1204: b->nextl = bb->nextl;
1205: }
1206: if (bb != NULL && !bb->marked)
1207: reach(bb);
1208: if ((bb = b->nextr) != NULL && !bb->marked)
1209: reach(bb);
1210: }
1211:
1212: static void
1213: rmbrs() { /* remove redundant branches */
1214:
1215: register BLOCK *b, *bl;
1216: register NODE *p;
1217:
1218: TRACE(rmbrs);
1219:
1220: for (ALLB(b, b0.next))
1221: if ((bl = b->nextl) != NULL &&
1222: (p = b->lastn)->forw == bl->firstn && ISREMBR(p)) {
1223:
1224: /* delete unconditional branch ahead of target */
1225:
1226: if (isuncbr(p)) {
1227: RMBR(p);
1228: continue;
1229: }
1230:
1231: /* delete conditional branch ahead of target
1232: or ahead of unconditional branch to same target */
1233:
1234: do {
1235: if (b->nextr == bl || b->nextr == NULL &&
1236: bl->nextl == NULL && ISUNCBL(bl) &&
1237: sameaddr(p, bl->lastn)) {
1238: RMBR(p);
1239: break;
1240: }
1241: } while ( ISUNCBL(bl)
1242: && bl != bl->nextl /* avoid self-loop */
1243: && (bl = bl->nextl) != NULL);
1244: }
1245: }
1246: /* ldanal -- perform live/dead analysis over flow graph
1247: **
1248: ** This routine calculates live/dead register information for the
1249: ** entire flow graph in these steps:
1250: **
1251: ** 1. Allocate temporary array to hold block-level live/dead info.
1252: ** Initialize it.
1253: ** 2. On a block-wise basis, determine registers set and used by
1254: ** each instruction. Determine registers used and set by the
1255: ** block.
1256: ** 3. Propagate register use/set information throughout the flow
1257: ** graph blocks.
1258: ** 4. Propagate final information back through each block to
1259: ** reflect correct live/dead information for each instruction.
1260: **
1261: ** We use the live/dead algorithm described in the Aho and Ullman
1262: ** "dragon book".
1263: */
1264:
1265: #ifdef LIVEDEAD
1266: void
1267: ldanal() { /* perform live-dead register analysis */
1268:
1269: typedef unsigned int LDREG;
1270: register BLOCK * b; /* pointer to current block */
1271: register NODE * p; /* pointer to current inst. node */
1272: struct ldinfo /* temporary block-level structure */
1273: {
1274: LDREG buses; /* registers used by block */
1275: LDREG bdef; /* registers defined (set) by block */
1276: LDREG bin; /* registers live coming into block */
1277: LDREG bout; /* registers live exiting block */
1278: };
1279: struct ldinfo * lddata; /* array of data for each block */
1280: register struct ldinfo * ldptr; /* pointer to one of the above */
1281: unsigned i;
1282: boolean changed;
1283:
1284: TRACE(ldanal);
1285:
1286: bldgr(false); /* update block structure but don't call bboptim */
1287: lddata = NEWBLK(idx + 1, struct ldinfo);
1288:
1289: /* Initialize: set the recently allocated array to zero. The idea, here,
1290: ** is that each entry in the array corresponds to one block in the flow
1291: ** graph. We assume that blocks have sequential index numbers and that
1292: ** idx is the last index number.
1293: */
1294:
1295: CLEAR(lddata, (idx + 1) * sizeof(struct ldinfo));
1296:
1297: /* Step 2. Calculate uses/def for each node and for the containing block. */
1298:
1299: for (ALLB(b,b0.next))
1300: {
1301: ldptr = lddata + b->index;
1302: for (p = b->lastn; !islabel(p); p = p->back)
1303: {
1304: p->nlive = uses(p) | LIVEREGS; /* what's used here, + always live */
1305: p->ndead = sets(p) & ~p->nlive; /* what's set, but not used, here */
1306: ldptr->buses = (p->nlive | (ldptr->buses & ~p->ndead)) & REGS;
1307: /* current live registers */
1308: ldptr->bdef = (p->ndead | (ldptr->bdef & ~p->nlive)) & REGS;
1309: /* current registers killed by block */
1310:
1311: if (p == b->firstn) /* stop if reached first node */
1312: break;
1313: }
1314:
1315: }
1316:
1317: /* Propagate live/dead data throughout the flow graph, using Aho and
1318: ** Ullman algorithm.
1319: */
1320:
1321: do
1322: {
1323: changed = false; /* will continue until no changes */
1324:
1325: for (ALLB(b,b0.next))
1326: {
1327: LDREG in, out;
1328:
1329: if (b->nextr == NULL && (b->nextl == NULL ||
1330: (isbr(b->lastn) && !isuncbr(b->lastn))))
1331: {
1332: /* This case represents a return, or an unconditional indexed
1333: ** jump, or a switch. If we had better connectivity in the
1334: ** flow graph, we could trace all successors correctly. As
1335: ** things are, we have to assume the worst about what registers
1336: ** are live going into the next block. For a return, this means
1337: ** those registers that can be used to return a value. For
1338: ** others, we mark all registers live.
1339: */
1340: out = isret(b->lastn) ? RETREG : REGS;
1341: }
1342: else
1343: {
1344: /* OUT = union (of successors) IN */
1345: out = 0; /* registers out of current block. */
1346: if (b->nextr != NULL)
1347: out |= lddata[b->nextr->index].bin;
1348: if (b->nextl != NULL)
1349: out |= lddata[b->nextl->index].bin;
1350: }
1351:
1352: ldptr = lddata + b->index; /* point at data for current block */
1353: /* IN = OUT - DEF u USE */
1354: in = (out & ~ldptr->bdef) | ldptr->buses;
1355:
1356: /* see what changed */
1357:
1358: if (in != ldptr->bin || out != ldptr->bout)
1359: {
1360: changed = true;
1361: ldptr->bin = in; /* set changed values */
1362: ldptr->bout = out;
1363: }
1364: } /* end for */
1365: } while (changed);
1366:
1367: /* Now set the final live/dead (really, just live) information in
1368: ** each node of each block.
1369: */
1370:
1371: for (ALLB(b,b0.next))
1372: {
1373: /* go backward again through each block */
1374: /* initial live is outgoing regs of block */
1375:
1376: LDREG live = lddata[b->index].bout;
1377: for (p = b->lastn; !islabel(p); p = p->back)
1378: {
1379: LDREG newlive = (p->nlive | (live & ~p->ndead)) & REGS;
1380: p->nlive = live; /* live for this node is what was
1381: ** live going into successor
1382: */
1383: live = newlive; /* live for next node is whatever
1384: ** else we used, but didn't kill
1385: */
1386: if (p == b->firstn)
1387: break; /* quit if first node in block */
1388: }
1389: }
1390:
1391: xfree((char *) lddata); /* free up temp. storage */
1392: }
1393:
1394: #endif /* def LIVEDEAD */
1395:
1396: #ifdef PEEPHOLE
1397: static NODE *pf; /* pointer to first window node */
1398: static NODE *opf; /* pointer to predecessor of first window node */
1399: static int wsize; /* window size for peephole trace */
1400:
1401: window(size, func) register int size; boolean (*func)(); { /* peephole scan */
1402:
1403: extern NODE *initw();
1404: register NODE *pl;
1405: register int i;
1406:
1407: TRACE(window);
1408:
1409: /* find first window */
1410:
1411: wsize = size;
1412: if ((pl = initw(n0.forw)) == NULL)
1413: return;
1414:
1415: /* move window through code */
1416:
1417: for (opf = pf->back; ; opf = pf->back) {
1418: if ((*func)(pf, pl) == true) {
1419: if (wflag)
1420: if (opf->forw == pl->forw)
1421: PRINTF("%cdeleted\n", CC);
1422: else {
1423: PRINTF("%cchanged to:\n", CC);
1424: prwindow(opf->forw, size);
1425: }
1426: if (size > 1) {
1427:
1428: /* move window back in case
1429: there is an overlapping improvement */
1430:
1431: for (i = 2; i <= size; i++)
1432: if ((opf = opf->back) == &n0) {
1433: opf = n0.forw;
1434: break;
1435: }
1436: if ((pl = initw(opf)) == NULL)
1437: return;
1438: continue;
1439: }
1440: }
1441:
1442: /* move window ahead */
1443:
1444: if ((pl = pl->forw) == &ntail)
1445: return;
1446: pf = pf->forw;
1447: if (islabel(pl) && (pl = initw(pl->forw)) == NULL)
1448: return;
1449: }
1450: }
1451:
1452: static NODE *
1453: initw(p) register NODE *p; { /* find first available window */
1454:
1455: register int i;
1456:
1457: if ((pf = p) == NULL)
1458: return (NULL);
1459:
1460: /* move p down until window is large enough */
1461:
1462: for (i = 1; i <= wsize; i++) {
1463: if (p == &ntail) /* no more windows */
1464: return (NULL);
1465: if (islabel(p)) { /* restart scan */
1466: pf = p->forw;
1467: i = 0;
1468: }
1469: p = p->forw;
1470: }
1471: return (p->back);
1472: }
1473:
1474: wchange() { /* print window before change */
1475:
1476: if (wflag) {
1477: PRINTF("%cwindow:\n", CC);
1478: prwindow(opf->forw, wsize);
1479: }
1480: }
1481:
1482: static
1483: prwindow(p, size) /* print "size" instructions starting at p */
1484: register NODE *p; register int size; {
1485:
1486: for ( ; --size >= 0 && p != &ntail && !islabel(p); p = p->forw) {
1487: PUTCHAR(CC);
1488: #ifdef LIVEDEAD
1489: PRINTF("(live: 0x%X)", p->nlive);
1490: #endif
1491: prinst(p);
1492: }
1493: }
1494: #endif
1495:
1496: static void
1497: mkltbl() { /* make label table with only definitions */
1498:
1499: register BLOCK *b;
1500: register NODE *p;
1501:
1502: clrltbl();
1503:
1504: /* add definitions from labels in text section */
1505:
1506: for (ALLB(b, b0.next))
1507: for (p = b->firstn; islabel(p); p = p->forw)
1508: ADDLBL(p->ops[0], b);
1509: }
1510:
1511: static
1512: clrltbl() { /* clear label table */
1513:
1514: CLEAR(Lbltbl, N_LBLS * sizeof(LBL));
1515: Numlbls = 0;
1516: }
1517:
1518: static BLOCK *
1519: lblhash(l, b) register char *l; BLOCK *b; { /* add or find label in label table */
1520:
1521: register LBL *p;
1522: register int lh = 0, c;
1523: register char *ll = l;
1524:
1525: while ((c = *ll++) != '\0')
1526: lh += c;
1527: /*
1528: * The precheck on the third character avoids many superfluous
1529: * calls to strcmp when the hash table is fairly full. The third
1530: * character is chosen because most compilers generate labels
1531: * with an invariant two-character prefix. In a later version,
1532: * perhaps labels should be converted at the machine-dependent
1533: * level into unique integers instead of being stored as strings.
1534: */
1535: for (p = Lbltbl + lh % N_LBLS; p->cp != NULL &&
1536: (l[2] != p->cp[2] && l[1] != '\0' || strcmp(p->cp, l)); )
1537: if ((p -= H_INCR) < Lbltbl)
1538: p += N_LBLS;
1539: if (b != NULL) { /* enter or overwrite the block entry */
1540: if (p->bl == NULL && ++Numlbls >= N_LBLS)
1541: FATAL("too many labels\n");
1542: p->cp = l;
1543: p->bl = b;
1544: }
1545: return (p->bl);
1546: }
1547:
1548: char *
1549: getspace(n) register unsigned n; { /* return a pointer to "n" bytes */
1550:
1551: register char *p = Lasta;
1552:
1553: /* round up so pointers are always word-aligned */
1554: /* int conversions are to avoid call to software remaindering */
1555:
1556: n += sizeof(char *) - ((int) n % (int) sizeof(char *));
1557: Maxu += n;
1558: while ((Lasta += n) >= Lastx) {
1559: *Space = NEWBLK(1, struct space_t);
1560: p = Lasta = (char *) &(*Space)->space[0];
1561: Lastx = (char *) &(*Space)->space[NSPACE - 1];
1562: (*Space)->next = NULL;
1563: Space = &(*Space)->next;
1564: }
1565: return (p);
1566: }
1567: /* Branch shortening
1568: **
1569: ** This code shortens span-dependent branches with assistance from
1570: ** machine dependent routines. The interface is as follows:
1571: **
1572: ** bspan(flag) is the entry point available to machine-
1573: ** dependent routines; the flag is true to print
1574: ** debugging information
1575: **
1576: ** BSHORTEN symbol, defined in "defs"; enables all this
1577: **
1578: ** int instsize(node)
1579: ** routine or macro; returns upper bound on size of
1580: ** instruction in node in arbitrary units
1581: ** void bshorten(node,dist)
1582: ** routine or macro; changes op at node to be
1583: ** shortened version of branch, based on (long)
1584: ** distance (dist) between branch and target
1585: **
1586: ** The algorithm proceeds in two passes over the blocks of the program.
1587: ** The first pass calculates the relative PC (program counter) value for
1588: ** the beginning of each block. (Remember, labels are always at the
1589: ** beginning of a block.) Since branches are always at the end of blocks,
1590: ** the assumption is that the machine's program counter register always
1591: ** points to the beginning of the block following the branch when the
1592: ** branch is executed. (This assumption for the purpose of calculating
1593: ** distances.) Branches are assumed to be shortenable both forward and
1594: ** backward.
1595: **
1596: ** The PC values for the blocks are kept in a dynamically allocated
1597: ** array. The array is size idx+2, where idx is the highest block
1598: ** number. The +2 accounts for not using array[0] (we index into
1599: ** the array by block index numbers which are non-zero) and for one
1600: ** additional entry at the end to contain the PC just after the
1601: ** last block.
1602: **
1603: ** Pass two calculates distances between branches and their targets
1604: ** and shortens branches which can be shortened.
1605: */
1606:
1607: #ifdef BSHORTEN
1608:
1609: void
1610: bspan(flag) /* shorten span-dependent branches */
1611: boolean flag; /* true to print debug info. */
1612: {
1613: long * bpc; /* point to array of PC's */
1614: register BLOCK * block; /* block pointer */
1615: register NODE * node; /* pointer for scanning block's nodes */
1616: BLOCK * target; /* branch target block */
1617: char * label; /* branch label string */
1618: long pc; /* current PC */
1619: long pcdiff; /* PC difference, branch to target */
1620: extern int instsize(); /* returns size of instruction */
1621:
1622: bldgr(false); /* build flow graph */
1623: /* allocate array for block start PC's */
1624:
1625: bpc = (long *) xalloc( sizeof(long) * (idx+2));
1626: pc = 0; /* current PC */
1627:
1628: /* make first pass to compute PC at start of each block */
1629:
1630: if (flag)
1631: PRINTF("%c Block starting PC:\n", CC);
1632:
1633: for ( ALLB(block, b0.next) )
1634: {
1635: if (flag)
1636: PRINTF("%c\t%d\t%d\n", CC, block->index, pc);
1637:
1638: bpc[block->index] = pc; /* current PC is block start PC */
1639: for (node = block->firstn ; ; node = node->forw)
1640: {
1641: pc += instsize(node); /* increase PC by instruction size */
1642: if (node == block->lastn)
1643: break; /* done this block at last inst. */
1644: }
1645: }
1646: bpc[idx+1] = pc; /* set PC of non-existent next block */
1647: if (flag)
1648: PRINTF("%c\t(last)\t%d\n", CC, pc);
1649: /* Pass 2. Try to shorten branches. */
1650:
1651: for ( ALLB(block, b0.next) )
1652: {
1653: if (isbr(block->lastn) && (label = getp(block->lastn)) != NULL)
1654: {
1655: /* Beware of non-existent target for branch */
1656:
1657: if((target = FINDLBL(label)) == NULL)
1658: pcdiff = ~((unsigned long) 0) >> 1; /* maximum offset */
1659: else
1660: pcdiff = bpc[target->index] /* target PC */
1661: - bpc[block->index + 1];
1662: /* branch PC (PC of next block */
1663:
1664: /* shorten branch if branch-to-target distance short enough */
1665:
1666: if (flag)
1667: {
1668: PRINTF("%c Difference: %d -- Shorten:\t", CC, pcdiff);
1669: prinst(block->lastn);
1670: }
1671: bshorten(block->lastn,pcdiff);
1672: }
1673: }
1674: xfree((char *) bpc); /* free up array */
1675: return;
1676: }
1677:
1678: #endif /* def BSHORTEN */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.