![[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 [MW Coherent from dump] / coherent / d / bin / cc / c / n2|
Return to optim.c CVS log | Up to [MW Coherent from dump] / coherent / d / bin / cc / c / n2 |
1.1 root 1: /*
2: * C compiler.
3: * Jump and shape optimization.
4: * Jump to jump, etc.
5: * Common sequences.
6: * Cross jumping.
7: */
8: #ifdef vax
9: #include "INC$LIB:cc2.h"
10: #else
11: #include "cc2.h"
12: #endif
13:
14: #define NLHASH 64
15: #define LHMASK 077
16:
17: static INS *labhash[NLHASH];
18:
19: /*
20: * Shuffle segments,
21: * Move all non 'SHRI' segments to the front,
22: * then squash any extra switches out of the stream.
23: * This is necessary to make code that is together in
24: * memory together in the 'ins' lists.
25: */
26: shuffle()
27: {
28: register INS *fp, *ip;
29: register INS *niloc;
30: INS *bep, *bfp;
31: register int curseg;
32:
33: niloc = &ins;
34: for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) {
35: if (ip->i_type != ENTER)
36: continue;
37: bfp = ip;
38: do {
39: ip = ip->i_fp;
40: } while (ip->i_type != ENTER);
41: if (bfp != ins.i_fp) {
42: bep = ip;
43: ip = bfp->i_bp;
44: bfp->i_bp->i_fp = bep->i_fp;
45: bep->i_fp->i_bp = bfp->i_bp;
46: niloc->i_fp->i_bp = bep;
47: bfp->i_bp = niloc;
48: bep->i_fp = niloc->i_fp;
49: niloc->i_fp = bfp;
50: niloc = bep;
51: }
52: }
53: curseg = dotseg;
54: for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) {
55: if (ip->i_type != ENTER)
56: continue;
57: while ((fp=ip->i_fp)!=&ins && fp->i_type==ENTER)
58: ip = deleteins(ip, ip->i_fp)->i_fp;
59: if (ip->i_seg == curseg) {
60: ip = deleteins(ip, ip->i_fp);
61: continue;
62: }
63: curseg = ip->i_seg;
64: }
65: }
66:
67: /*
68: * Delete node ip.
69: * Return a pointer to the previous node.
70: * Merge any line number references onto ip1.
71: */
72: INS *
73: deleteins(ip, ip1)
74: register INS *ip;
75: INS *ip1;
76: {
77: register INS *bp, *fp;
78:
79: mrgdbgt(ip, ip1);
80: if ((ip->i_type==JUMP || ip->i_type==LLLINK) && ((fp=ip->i_ip)!=NULL))
81: decrefc(fp);
82: bp = ip->i_bp;
83: fp = ip->i_fp;
84: bp->i_fp = fp;
85: fp->i_bp = bp;
86: free((char *) ip);
87: return (bp);
88: }
89:
90: /*
91: * Decrement the reference count on a label.
92: * Delete it if the label is now unreferenced.
93: * It is a fatal error to hand this routine a non label.
94: */
95: decrefc(ip)
96: register INS *ip;
97: {
98: if (ip->i_type != LLABEL)
99: cbotch("decrefc passed non label");
100: if (--ip->i_refc == 0)
101: deleteins(ip, ip->i_fp);
102: }
103:
104: /*
105: * Set up label reference counts and delete any unused labels.
106: */
107: labels()
108: {
109: register INS *fp, *ip, *lp;
110: INS *findlab();
111: register int curseg, i;
112:
113: for (i=0; i<NLHASH; ++i)
114: labhash[i] = NULL;
115: curseg = dotseg;
116: for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) {
117: if (ip->i_type == ENTER)
118: curseg = ip->i_seg;
119: else if (ip->i_type == LLABEL) {
120: ip->i_refc = 0;
121: /*
122: * Hack the reference count on the
123: * label if it is the label on a switch
124: * table to prevent it from being deleted
125: * by the next bit of code. Kludgy.
126: */
127: if (curseg != SCODE)
128: ++ip->i_refc;
129: else if ((fp=ip->i_fp) != &ins) {
130: if (fp->i_type == LLLINK)
131: ++ip->i_refc;
132: else if (fp->i_type == CODE
133: && fp->i_op >= ZBYTE
134: && fp->i_op <= ZGPTR)
135: ++ip->i_refc;
136: }
137: labhash[ip->i_labno&LHMASK] = ip;
138: }
139: }
140: for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) {
141: if (ip->i_type!=JUMP && ip->i_type!=LLLINK)
142: continue;
143: if ((lp=findlab(ip->i_labno)) != NULL) {
144: while ((fp=lp->i_fp)!=&ins && fp->i_type==LLABEL)
145: lp = fp;
146: ip->i_labno = lp->i_labno;
147: ++lp->i_refc;
148: }
149: ip->i_ip = lp;
150: }
151: for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) {
152: if (ip->i_type!=LLABEL || ip->i_refc!=0)
153: continue;
154: ip = deleteins(ip, ip->i_fp);
155: ++nlabdel;
156: }
157: }
158:
159: /*
160: * Find label.
161: * Quick test using hashtable.
162: * Long linear search if that fails.
163: */
164: INS *
165: findlab(n)
166: register int n;
167: {
168: register INS *lp;
169:
170: if ((lp=labhash[n&LHMASK])!=NULL && lp->i_labno==n)
171: return (lp);
172: for (lp=ins.i_fp; lp!=&ins; lp=lp->i_fp)
173: if (lp->i_type==LLABEL && lp->i_labno==n)
174: return (lp);
175: return (NULL);
176: }
177:
178: /*
179: * Delete dead code.
180: * Dead code begins after an unconditional jump and continues
181: * until the next label, segment change or the EPILOG.
182: */
183: deadcode()
184: {
185: register INS *fp, *ip;
186: register int t;
187:
188: for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) {
189: t = ip->i_type;
190: if (t == LLLINK) { /* Switch table */
191: while ((fp=ip->i_fp) != &ins && (fp->i_type == LLLINK
192: || (fp->i_type == CODE && opinfo[fp->i_op].op_style
193: == OF_WORD)))
194: ip = fp;
195: } else if (t != JUMP || ip->i_rel != UNCON)
196: continue;
197: fp = ip->i_fp;
198: while (fp != &ins) {
199: t = fp->i_type;
200: if (t==LLABEL || t==EPILOG || t==ENTER)
201: break;
202: fp = deleteins(fp, fp->i_fp)->i_fp;
203: ++ndead;
204: ++changes;
205: }
206: }
207: }
208:
209: /*
210: * Fix some of the more common funny things
211: * associated with jump instructions and labels.
212: * There are more things that could be done.
213: * These five things should get most of the common things.
214: */
215: fixbr()
216: {
217: register INS *ip, *ip1, *ip2;
218: INS *ip3, *ip4;
219: int t;
220:
221: again:
222: for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) {
223: t = ip->i_type;
224: /* Jump to jump. */
225: if ((t==JUMP && ischnrel(ip->i_rel)) || t==LLLINK) {
226: ip1 = ip->i_ip;
227: if (ip1 != NULL) {
228: ip2 = ip1;
229: for (;;) {
230: while (ip2->i_type == LLABEL)
231: ip2 = ip2->i_fp;
232: if (ip2->i_type!=JUMP
233: || ip2->i_rel!=UNCON)
234: break;
235: ip3 = ip2->i_ip;
236: if (ip3==NULL
237: || ip3==ip1
238: || ip3==ip2->i_bp)
239: break;
240: ip2 = ip3;
241: }
242: ip2 = ip2->i_bp;
243: if (ip1 != ip2) {
244: decrefc(ip1);
245: increfc(ip2);
246: ip->i_labno = ip2->i_labno;
247: ip->i_ip = ip2;
248: ++nbrbr;
249: ++changes;
250: }
251: }
252: }
253: /* Reversible jump over unconditional jump. */
254: if (t==JUMP && isrevrel(ip->i_rel)) {
255: ip1 = ip->i_fp;
256: if (ip1->i_type==JUMP && ip1->i_rel==UNCON) {
257: ip2 = ip1->i_fp;
258: if (ip2->i_type==LLABEL && ip->i_ip==ip2) {
259: ip1->i_rel = revrel(ip->i_rel);
260: deleteins(ip, ip1);
261: ++ncbrbr;
262: ++changes;
263: goto again;
264: }
265: }
266: }
267: /* Jump to next instruction. */
268: if (t==JUMP && ip->i_ip==ip->i_fp) {
269: deleteins(ip, ip->i_fp);
270: ++nbrnext;
271: ++changes;
272: goto again;
273: }
274: /*
275: * The preceding optimizations do not change the code order,
276: * so they can be executed even if VNOOPT.
277: * The following optimizations do change the code order,
278: * so they are suppressed if VNOOPT.
279: */
280: if (isvariant(VNOOPT))
281: continue;
282: /*
283: * [ip]JUMP L1; [ip1]L2:...; [ip2]L1:...; [ip3]JUMP L2; ...
284: * becomes [ip2]L1:...; [ip1]L2:...; [ip]JUMP L1; ...
285: * Saves a jump in every for loop.
286: */
287: if (t==JUMP && ip->i_rel==UNCON) {
288: ip1 = ip->i_fp;
289: if (ip1!=&ins && ip1->i_type==LLABEL) {
290: ip2 = NULL;
291: for (ip3=ip1->i_fp; ip3!=&ins; ip3=ip3->i_fp) {
292: if (ip3->i_type==LLABEL
293: && ip->i_ip==ip3)
294: ip2 = ip3;
295: else if (ip2!=NULL
296: && ip3->i_type==JUMP
297: && ip3->i_rel==UNCON
298: && ip3->i_ip==ip1) {
299: ip4 = ip2->i_bp;
300: ip->i_bp->i_fp = ip2;
301: ip3->i_bp->i_fp = ip1;
302: ip4->i_fp = ip;
303: ip->i_fp = ip3;
304: ip2->i_bp = ip->i_bp;
305: ip1->i_bp = ip3->i_bp;
306: ip->i_bp = ip4;
307: ip3->i_bp = ip;
308: deleteins(ip3, ip1);
309: ++nexbr;
310: ++changes;
311: goto again;
312: }
313: }
314: }
315: }
316: /*
317: * [ip] JUMP L1; <code1>; [ip2] JUMP L2; [ip1] L1: <code2>; [ip3] L2:
318: * becomes [ip1] L1: <code2>; [ip] JUMP L2; <code1>; [ip3] L2:
319: * Saves a jump in every switch and restores natural code order.
320: * <code2> often ends in JUMP or LLLINK, in which case JUMP L2
321: * gets optimized out later.
322: */
323: if (t==JUMP && ip->i_rel==UNCON && precedes(ip, ip->i_ip)) {
324: ip1 = ip->i_ip;
325: ip2 = ip1->i_bp;
326: if (ip2->i_type==JUMP && ip2->i_rel==UNCON
327: && precedes(ip1, ip2->i_ip)) {
328: ip3 = ip2->i_ip;
329: /* Rearrange the code. */
330: ip->i_bp->i_fp = ip1;
331: ip3->i_bp->i_fp = ip;
332: ip2->i_fp = ip3;
333: ip1->i_bp = ip->i_bp;
334: ip->i_bp = ip3->i_bp;
335: ip3->i_bp = ip2;
336: /* Change JUMP L1 at ip into JUMP L2. */
337: ip->i_ip = ip3;
338: ip->i_labno = ip3->i_labno;
339: increfc(ip3);
340: decrefc(ip1);
341: /* Delete the now extraneous JUMP. */
342: deleteins(ip2, ip3);
343: ++nexbr;
344: ++changes;
345: goto again;
346: }
347: }
348: }
349: }
350:
351: /*
352: * Return true iff ip1 precedes ip2 in the INS node chain.
353: */
354: static
355: precedes(ip1, ip2)
356: register INS *ip1, *ip2;
357: {
358: while ((ip1 = ip1->i_fp) != &ins)
359: if (ip1 == ip2)
360: return(1);
361: return(0);
362: }
363:
364: /*
365: * Increment the reference count on a label.
366: * It is a fatal error to hand this routine a non label.
367: */
368: increfc(ip)
369: register INS *ip;
370: {
371: if (ip->i_type != LLABEL)
372: cbotch("increfc passed non label");
373: ++ip->i_refc;
374: }
375:
376: /*
377: * Insert a label.
378: * It has been 'increfc'ed.
379: * Return pointer to the new label.
380: */
381: INS *
382: inslab(ip)
383: register INS *ip;
384: {
385: register INS *lp, *bp;
386:
387: if (ip->i_type == LLABEL) {
388: increfc(ip);
389: return (ip);
390: }
391: lp = (INS *) malloc(sizeof(INS));
392: if (lp != NULL) {
393: lp->i_type = LLABEL;
394: lp->i_labno = newlab();
395: lp->i_sp = NULL;
396: lp->i_refc = 1;
397: bp = ip->i_bp;
398: bp->i_fp = lp;
399: lp->i_fp = ip;
400: ip->i_bp = lp;
401: lp->i_bp = bp;
402: }
403: return (lp);
404: }
405:
406: /*
407: * Cross jumps.
408: * If the same code precedes an unconditional jump and
409: * the label to which it jumps, replace the former with
410: * a jump to a new local label.
411: */
412: xjumps()
413: {
414: register INS *ip, *lp;
415:
416: for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) {
417: if (ip->i_type!=JUMP || ip->i_rel!=UNCON
418: || (lp = ip->i_ip)==NULL)
419: continue;
420: if (!docomseq(lp, ip, &nxjump))
421: return;
422: }
423: }
424:
425: /*
426: * Compare two nodes.
427: * True return if the same.
428: * Never called on strange stuff
429: * or labels.
430: */
431: xeq(ip1, ip2)
432: register INS *ip1, *ip2;
433: {
434: register int t;
435:
436: if ((t=ip1->i_type) != ip2->i_type)
437: return (0);
438: if (t==JUMP || t==LLLINK) {
439: if (ip1->i_labno != ip2->i_labno)
440: return (0);
441: if (t==JUMP && ip1->i_rel!=ip2->i_rel)
442: return (0);
443: return (1);
444: }
445: if (t != CODE)
446: cbotch("xeq");
447: if (ip1->i_op != ip2->i_op)
448: return (0);
449: if (ip1->i_naddr != ip2->i_naddr)
450: return (0);
451: return (cmpfield(ip1, ip2));
452: }
453:
454: /*
455: * Detect common sequences before jumps.
456: * When found, replace the later with a jump to a new
457: * local label preceding the former.
458: */
459: comseq()
460: {
461: register INS *ip, *xp, *yp;
462:
463: for (xp=ins.i_fp; xp!=&ins; xp=xp->i_fp) {
464: if (xp->i_type!=JUMP || xp->i_rel!=UNCON)
465: continue;
466: ip = xp->i_ip;
467: if (ip==NULL || ip->i_type != LLABEL)
468: continue;
469: for (yp=xp->i_fp; yp!=&ins; yp=yp->i_fp) {
470: if (yp->i_type==JUMP && yp->i_rel==UNCON
471: && yp->i_ip==ip) {
472: if (!docomseq(xp, yp, &ncomseq))
473: return;
474: }
475: }
476: }
477: }
478:
479:
480: /*
481: * Back up through the code looking for valid cross jumps.
482: * When found, insert a new local label before the first
483: * and change the second into an unconditional jump to it.
484: * Called from xjumps and comseq.
485: * Returns 0 if the new node allocation fails.
486: */
487: docomseq(xp, yp, countp)
488: register INS *xp, *yp;
489: int *countp;
490: {
491: for (;;) {
492: xp = xp->i_bp;
493: if (xp==&ins || xp->i_type==LLABEL || xp->i_type==LLLINK)
494: break;
495: yp = yp->i_bp;
496: if (yp==&ins || yp->i_type==LLABEL || yp->i_type==LLLINK
497: || xeq(xp, yp)==0)
498: break;
499: xp = inslab(xp);
500: if (xp == NULL)
501: return (0);
502: mrgdbgt(yp, xp->i_fp);
503: if ((yp->i_type==JUMP || yp->i_type==LLLINK) && yp->i_ip!=NULL)
504: decrefc(yp->i_ip);
505: yp->i_type = JUMP;
506: yp->i_labno = xp->i_labno;
507: yp->i_sp = NULL;
508: yp->i_ip = xp;
509: yp->i_rel = UNCON;
510: yp->i_long = 0;
511: ++*countp;
512: ++changes;
513: }
514: return(1);
515: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.