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