![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to branch.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv9 / cmd / sun / c2|
Return to branch.c CVS log | Up to [Research Unix] / researchv9 / cmd / sun / c2 |
1.1 root 1: #ifndef lint
2: static char sccsid[] = "@(#)branch.c 1.1 86/02/03 Copyr 1985 Sun Micro";
3: #endif
4:
5: /*
6: * Copyright (c) 1985 by Sun Microsystems, Inc.
7: */
8:
9: #include "as.h"
10: #include "c2.h"
11:
12: char *unbranch[] = {
13: "jne", "jeq", "jgt", "jlt", "jge", "jle",
14: "jhi", "jls", "jpl", "jmi", "jf",
15: "jcc", "jcs", "jvc", "jvs", "jra",
16: "jfneq", "jfeq", "jfnlt", "jflt",
17: "jfnle", "jfle", "jfngt", "jfgt",
18: "jfnge", "jfge",
19: "fjneq", "fjeq", "fjngt", "fjgt", "fjnge", "fjge",
20: "fjnlt", "fjlt", "fjnle", "fjle", "fjngl", "fjgl",
21: "fjngle", "fjgle", "fjule", "fjogt", "fjult", "fjoge",
22: "fjuge", "fjolt", "fjugt", "fjole", "fjueq", "fjogl",
23: "fjun", "fjor", "fjst", "fjsf", "fjsneq", "fjseq"
24: };
25: extern NODE *deletenode();
26:
27: NODE *
28: insert_label( p )
29: register NODE *p;
30: {
31: static int newlabno = 0;
32: register NODE *l;
33: register struct sym_bkt *s;
34: char labname[20];
35:
36: l = new();
37: l->op = OP_LABEL;
38: l->nref = 0;
39: sprintf( labname, "LY%05d", newlabno++ );
40: l->name = s = lookup(labname);
41: s->attr_s |= S_DEF|S_DEC;
42: s->csect_s = C_TEXT;
43: s->where_s = l;
44: l->forw = p;
45: l->back = p->back;
46: l->back->forw = l;
47: p->back = l;
48: l->ruse = l->rset = regmask0;
49: l->rlive = l->forw->rlive;
50: return l;
51: }
52:
53: NODE *
54: merge_labels( to, from )
55: register NODE * to, *from ;
56: {
57: /*
58: * there are two kinds of labels:
59: * those all of whose references we can find, and
60: * the others.
61: * In the latter case, we will want to move the label,
62: * and let someone smarter than us drop the equate.
63: */
64: register refs = 0;
65: register NODE *luse;
66: if (from->luse!=NULL){
67: for ( luse=from->luse; ; luse=luse->lnext ){
68: luse->luse = to;
69: refs++;
70: if (luse->lnext==NULL) break;
71: }
72: luse->lnext=to->luse;
73: to->luse =from->luse;
74: }
75: if (refs == from->nref){
76: from = deletenode( from )->forw;
77: meter.nrlab++;
78: } else {
79: /*
80: * at this point there are not references on our list, but
81: * still references to this label somewhere out there
82: * move the damn thing
83: * and null out the use list
84: */
85: NODE *temp;
86: from->nref -= refs;
87: from->luse = NULL;
88: temp = from->forw;
89: from->back->forw = from->forw;
90: from->forw->back = from->back;
91: from->forw = to->forw;
92: from->forw->back = from;
93: from->back = to;
94: to->forw = from;
95: from = temp;
96: }
97: to->nref += refs;
98: return from;
99: }
100:
101: int
102: fallthrough( t )
103: register NODE *t;
104: {
105: /*
106: * return 0 if t is a node that cannot "fall through" to the
107: * next instruction, such as an unconditional jump or code-
108: * emitting pseudo-instruction
109: * return 1 if this is not the case.
110: */
111: if (ISDIRECTIVE(t->op) ) return 1;
112: else if (ISPSEUDO(t->op) ) return 0;
113: else switch (t->op){
114: case OP_CSWITCH:
115: case OP_FIRST:
116: case OP_EXIT:
117: return 0;
118: case OP_BRANCH:
119: case OP_JUMP:
120: return t->subop!=JALL;
121: default:
122: return 1;
123: }
124: /* NOTREACHED */
125: }
126:
127:
128: # define nexti( t ) while( t->op==OP_LABEL ) t=t->forw
129: tangle()
130: {
131: /*
132: * remove:
133: * trivial jumps
134: * jumps to jumps
135: * jumps around jumps
136: */
137:
138: int changed = 1;
139: int niter=0;
140: register NODE *p, *t, *u;
141: NODE *j, *jdest, *savelabel;
142:
143: while (changed){
144: changed=0;
145: for (p=first.forw; p!=&first; p=p->forw){
146: if ((p->op==OP_JUMP&&p->subop!=JIND)||p->op==OP_CSWITCH){
147: t = p->luse;
148: nexti( t );
149: if (t==p){
150: /* selfloop */
151: if (p->luse->nref==1 && !fallthrough(p->back)){
152: /* unreachable */
153: unreference( p->luse, p);
154: p = deletenode( p );
155: meter.nbrbr++;
156: changed++;
157: }
158: continue;
159: }
160: if (t->op==p->op && (t->subop==JALL || t->subop==p->subop)){
161: /* jump-to-jump -- remove the middle reference */
162: if (p->luse==t->luse){
163: /* jump into selfloop */
164: continue;
165: }
166: unreference( p->luse, p);
167: newreference( t->luse, p);
168: t = p->luse;
169: nexti( t );
170: meter.nbrbr++;
171: changed++;
172: }
173: if (p->op==OP_CSWITCH ) continue;
174: if (p->luse==p->forw){
175: /* trivial jump */
176: unreference( p->luse, p);
177: p = deletenode( p );
178: changed++;
179: meter.njp1++;
180: continue;
181: }
182: if (p->subop == JALL){
183: u = (t=p->luse)->back;
184: /* find the non-pseudo-op before the destination */
185: while (ISDIRECTIVE(u->op))
186: u = u->back;
187: if ( t->nref==1 && ( u->op==OP_FIRST ||
188: ((u->op==OP_JUMP&&u->subop==JALL)|| u->op==OP_EXIT))){
189: /*
190: * this piece of code is reachable from p but not by
191: * fall through. move it to after p and delete
192: * the jump. stop moving after a cswitch
193: * or unconditional goto or return.
194: */
195: jdest = u->luse;
196: savelabel = 0;
197: u = t;
198: while ((u=u->forw)->op!= OP_FIRST){
199: if (u->op==OP_LABEL ){
200: if ( u->back->op==OP_CSWITCH )
201: break;
202: else if (savelabel != jdest
203: && !(u->forw->op==OP_CSWITCH ) )
204: savelabel = u;
205: }else if ((u->op==OP_JUMP && u->subop==JALL)
206: || u->op==OP_EXIT ){
207: u = u->forw;
208: break;
209: }
210: }
211: /* t points to the first node to move, and */
212: /* u points to the first node not to move. */
213: j = u->back;
214: if (j==p){
215: /*
216: * oh, my... a loop. It may be without any
217: * way in, but I'm too 'fraid to try deleteing
218: * it. Lets try pivoting around an appropriate
219: * label in the loop.
220: */
221: if (savelabel){
222: u = savelabel;
223: j = u->back;
224: } else
225: continue;
226: }
227: if (j->op != OP_CSWITCH
228: && !(j->op==OP_JUMP && j->subop==JALL)
229: && j->op != OP_EXIT
230: && u->op==OP_LABEL){
231: /* add unconditional branch here */
232: j->forw = new();
233: j->forw->back = j;
234: j = j->forw;
235: cannibalize( j, "jra" );
236: j->op = OP_JUMP; /* rather than OP_BRANCH */
237: newreference( u, j);
238: }
239: u->back = t->back;
240: t->back->forw = u;
241: t->back = p;
242: j->forw = p->forw;
243: p->forw->back = j;
244: p->forw = t;
245: /* the details will take care of themselves */
246: p = p->back;
247: changed++;
248: meter.ncmot++;
249: continue;
250: }
251: /* delete dead code after unconditional branch */
252: /* should do after exits, too */
253: u = p->forw;
254: while ((t=u)->op!=OP_LABEL && t->op!=OP_FIRST
255: && t->op != OP_EXIT){
256: u = t->forw;
257: if (ISPSEUDO( t->op ))
258: continue; /* don't delete pseudoops */
259: if (ISBRANCH(t->op))
260: unreference( t->luse, t);
261: (void)deletenode( t );
262: meter.iaftbr++;
263: changed++;
264: }
265: } else {
266: /* here for conditional branches */
267: u = p->forw;
268: /* may be no intervening branches here */
269: if (u->op==p->op && (u->subop==JALL || u->subop==p->subop)){
270: j = u;
271: u = u->forw;
272: nexti( u );
273: if (u==t){
274: /* jump-around-jump -- reverse condition, go directly */
275: cannibalize( j, unbranch[(int)(p->subop)-(int)JEQ] );
276: j->op = OP_JUMP; /* cannibalize makes an OP_BRANCH*/
277: unreference( p->luse, p );
278: p = deletenode( p );
279: meter.nrevbr++;
280: changed++;
281: }
282: } else if ( (int)p->subop <= (int)JNONE && u->op==OP_DJMP && u->subop==JNONE){
283: /*
284: * jXX Y
285: * dbra dZ,W
286: * should be changed to:
287: * dbXX dZ,W
288: * jXX Y
289: * because its faster. If label Y directly follows
290: * the dbra, the jump can be deleted entirely!
291: */
292: static char dbname[5] = {'d', 'b', '\0', '\0', '\0'};
293: /*
294: * since we cannot search for the correct instruction
295: * indexed by op and subop, we need to synthesize the
296: * new name and call cannibalize.
297: * jump instruction is of form [jb]CC[ls].
298: */
299: dbname[2] = p->instr->text_i[1];
300: dbname[3] = p->instr->text_i[2];
301: cannibalize( u, dbname );
302: u->op = OP_DJMP;
303:
304: /*
305: * unhook p from the list, reinsert it later
306: */
307: u = u->forw;
308: nexti( u );
309: if (u==t){
310: unreference( p->luse, p );
311: deletenode(p);
312: meter.nskip++;
313: } else {
314: p->back->forw = p->forw;
315: p->forw->back = p->back;
316: p->forw = p->back = 0;
317: insert( p, u->back );
318: meter.ndbrarev++;
319: }
320: p = u->back;
321: changed++;
322: }
323: }
324: }
325: }
326: if (++niter > 1000) sys_error("Tangled control-flow logic");
327: }
328: return niter-1;
329: }
330:
331: zipper()
332: {
333: /*
334: * For each label: look at all the jumps to that label:
335: * for those that are unconditional:
336: * compare the instructions preceeding to the
337: * instructions preceeding the label. The unconditional
338: * jump could jump to an earlier point in the "fall through"
339: * flow.
340: */
341:
342: register NODE *l, *u, *prec, *uprec, *luse;
343: NODE *pr, *upr;
344: int refs;
345: int nchange=0, didchange;
346:
347: for (l=first.forw; l!= &first; l=l->forw){
348: if (l->op!=OP_LABEL) continue;
349: prec = l->back;
350: /* skip over stabs */
351: while (ISDIRECTIVE(prec->op) )
352: prec=prec->back;
353: if (!ISINSTRUC(prec->op))
354: continue;
355: if (prec->op==OP_CSWITCH ) continue;
356: if ((prec->op==OP_BRANCH || prec->op==OP_JUMP) && prec->subop==JALL)
357: continue;
358: pr = prec;
359: for (u = l->luse; u!=NULL; u=upr, prec=pr){
360: upr = u->lnext;
361: uprec = u->back;
362: didchange=0;
363: if (u->op!=OP_JUMP || u->subop!=JALL) continue;
364: while (ISDIRECTIVE(uprec->op) )
365: uprec=uprec->back;
366: if (uprec->op==OP_FIRST) continue;
367: while(1){
368: if (uprec->op != prec->op ){
369: if (prec->op==OP_LABEL){
370: /* skip it */
371: prec=prec->back;
372: continue;
373: }else
374: break;
375: }
376: if (prec==uprec || prec==u || uprec==upr) break;
377: if (prec->op == OP_LABEL ){
378: uprec = merge_labels( prec, uprec );
379: didchange++;
380: } else{
381: if (ISPSEUDO( prec->op )) goto endzip;
382: if (!sameins( prec, uprec) ) goto endzip;
383: if (ISBRANCH(prec->op))
384: if (prec->luse != uprec->luse)
385: goto endzip;
386: else
387: unreference( uprec->luse, uprec);
388: uprec = deletenode( uprec )->forw;
389: didchange++;
390: }
391: prec=prec->back;
392: uprec=uprec->back;
393: }
394: endzip:
395: if (didchange){
396: /*
397: * we may have done something here.
398: * uprec addresses the first NON-common node we found.
399: * put the jump after it.
400: */
401: if ( uprec->forw != u ){
402: uprec->forw->back = u;
403: u->back->forw = u->forw;
404: u->forw->back = u->back;
405: u->forw = uprec->forw;
406: uprec->forw = u;
407: u->back = uprec;
408: }
409: if (prec->op!=OP_LABEL)
410: prec = insert_label( prec->forw );
411: unreference( u->luse, u);
412: newreference( prec, u);
413: u->rlive = u->luse->rlive;
414: nchange++;
415: }
416: }
417: }
418: meter.ncomj += nchange;
419: return nchange;
420: }
421:
422: int
423: tmerge()
424: {
425: /*
426: * For each label, z, in the program, try to find commonality
427: * amoung the pieces of code that end up at that label.
428: * We are very cautious.
429: * We are looking for the forms:
430: * jra elsewhere
431: * L: X
432: * X
433: * jra z
434: * and
435: * jYY L
436: * X
437: * X
438: * jra z
439: * L:
440: * which we can combine for smaller and no-slower code.
441: */
442:
443: NODE *z;
444: register NODE *a, *b;
445: NODE *ajmp;
446: NODE *bnext, *anext, *t;
447: NODE *bforw, *aforw;
448: int nchanged = 0;
449:
450: for (z=first.forw; z!=&first; z=z->forw){
451: if (z->op != OP_LABEL) continue;
452: for (ajmp=z->luse; ajmp!=NULL; ajmp=anext){
453: anext=ajmp->lnext;
454: if (ajmp->op != OP_JUMP || ajmp->subop != JALL) continue;
455: for (b=ajmp->lnext; b!=NULL; b=bnext){
456: bnext=b->lnext;
457: if (b->op != OP_JUMP || b->subop != JALL) continue;
458: bforw = b->forw;
459: a = ajmp;
460: aforw = a->forw;
461: /*
462: * compare backwards until:
463: * -- we hit a non-equality, or
464: * -- we hit a label, or
465: * -- we hit a jump
466: */
467: for ( a=a->back, b=b->back;
468: a->op!=OP_FIRST && b->op!=OP_FIRST;
469: a=a->back, b=b->back){
470:
471: while (ISDIRECTIVE( a->op ))
472: a=a->back;
473: while (ISDIRECTIVE( b->op ))
474: b=b->back;
475: switch (a->op){
476: default: /* | */
477: if ( ISPSEUDO(a->op) || !sameins( a, b ) ) break;
478: continue;
479: case OP_JUMP:
480: case OP_LABEL:
481: case OP_CSWITCH:
482: break; /* to outer break */
483: }/* +--------------------+ */
484: /* v */
485: break; /* out of for loop */
486: }/* +---------------------+ */
487: /* v
488: * we have now compared just a little too far:
489: * either *a != *b , or they are both pseudo-ops,
490: * jumps, labels, or something else unspeakable.
491: */
492: a = a->forw;
493: b = b->forw;
494: if (a == ajmp)
495: /* no equal sequences */
496: continue;
497: /* look for preceeding label, preceeded by unconditional jump */
498: if (b->back->op == OP_LABEL && (fallthrough(b->back->back)
499: || (a->back->op == OP_JUMP && a->back->luse == aforw)) ){
500: /* want to merge into "b" -- exchange */
501: t = b; b = a; a = t;
502: t = bforw; bforw = aforw; aforw = t;
503: /* and fall through into "a" test, which will succeed */
504: }
505: if (a->back->op == OP_LABEL){
506: if ( (t=b->back)->op == OP_LABEL && !fallthrough(t->back)){
507: /* merge into "a" */
508: (void)merge_labels( a->back, t);
509: /* cream junk trailing merged-out code */
510: if (anext == bforw->back)
511: anext = NULL;
512: while ( b!=bforw ){
513: if (ISBRANCH(b->op))
514: unreference( b->luse, b );
515: b = deletenode( b )->forw;
516: }
517: nchanged++;
518: break;
519: } else if (t->op == OP_JUMP && t->luse == bforw ){
520: a = a->back; /* "a" now addresses label */
521: cond_jumparound:
522: /*
523: * delete "b" code, complement branch condition,
524: * change branch target to "a"
525: */
526: if (anext == bforw->back)
527: anext = NULL;
528: while ( b!=bforw ){
529: if (ISBRANCH(b->op))
530: unreference( b->luse, b );
531: b = deletenode( b )->forw;
532: }
533: unreference( t->luse, t);
534: newreference( a, t);
535: cannibalize( t, unbranch[(int)(t->subop)-(int)JEQ] );
536: t->op = OP_JUMP; /* not BRANCH */
537: nchanged++;
538: break;
539: } else if (!fallthrough( a->back->back) ){
540: /*
541: * we can just move label "a" to before "b"
542: * and delete the rest of the "a" code
543: */
544: while (a != aforw ){
545: if (ISBRANCH(a->op))
546: unreference( a->luse, a );
547: a = deletenode( a )->forw;
548: }
549: a->back->back->forw = a;
550: a->back->forw = b;
551: t->forw = a->back;
552: a->back = a->back->back;
553: t->forw->back = t;
554: b->back = t->forw;
555: nchanged++;
556: break;
557: }
558: /* else out of luck */
559: } else if (a->back->op == OP_JUMP && a->back->luse == aforw
560: && b->back->op == OP_JUMP && b->back->luse == bforw ){
561: /*
562: * must insert new label, then treat like one of
563: * the labelled cases above.
564: */
565: a = insert_label( a );
566: t = b->back;
567: goto cond_jumparound;
568: }
569: }
570: }
571: }
572: meter.ncomj += nchanged;
573: return nchanged;
574: }
575:
576: /*
577: * assign a sequential node number to each node.
578: * Sequence is used to detect backwards edges.
579: */
580: order_nodes()
581: {
582: register NODE *n;
583: register nodenumber;
584:
585: nodenumber = 0;
586: for (n = first.forw; n != &first; n = n->forw) {
587: n->lineno = nodenumber++;
588: }
589: }
590:
591: /*
592: * change test-at-the-top loops to test-at-the-bottom
593: * with a jump to the test at the front.
594: * In order that we not get confused and loop forever moving the test
595: * back and forth, we will recompute the node ordering every time a
596: * loop is inverted.
597: */
598: int
599: invloop()
600: {
601: int nchanged;
602: register NODE *n;
603: register nodenumber;
604: register NODE *headlabel, *taillabel;
605: NODE *jump, *newlabel;
606:
607: nchanged = 0;
608: order_nodes();
609: for (n = first.forw; n != &first; n = n->forw){
610: /*
611: * look for this configuaration:
612: * headlabel -> Lx:
613: * <some instructions ( the test )>
614: * n -> conditional jump to Ly
615: * <some more instructions ( the loop body )>
616: * jump -> jra Lx
617: * taillabel -> Ly:
618: * If there are many conditional jumps (as in the case of
619: * while( xx && yy)) then we can key off of any of the jumps,
620: * but the first one makes the most sense, since it will be
621: * executed the most frequently.
622: */
623: if (n->op == OP_JUMP && n->subop != JALL &&
624: (taillabel = n->luse)->lineno > n->lineno){
625: jump = taillabel->back;
626: if (jump->op == OP_JUMP && jump->subop == JALL &&
627: (headlabel = jump->luse)->lineno < n->lineno){
628: /*
629: * Got it: now reorganize as:
630: * Lx:
631: * jmp Lnew2
632: * Lnew1:
633: * < some instructions ( the loop body ) >
634: * Lnew2:
635: * < some more instructions ( the test ) >
636: * conditional jump to Lnew1 ( reversed conditions )
637: * Ly:
638: * in the simple cases, Lx and Ly will become unused at this
639: * point.
640: */
641: /* move test & jmp code to after the jump */
642: unreference( headlabel, jump );
643: jump->forw = headlabel->forw;
644: headlabel->forw = n->forw;
645: n->forw->back = headlabel;
646: n->forw = taillabel;
647: taillabel->back = n;
648: jump->forw->back = jump;
649: /* delete the jump, replace by a label */
650: newlabel = insert_label( deletenode( jump )->forw );
651: /* insert new jump to new label at head of loop */
652: jump = new();
653: jump->forw = headlabel->forw;
654: headlabel->forw = jump;
655: jump->back = headlabel;
656: jump->forw->back = jump;
657: cannibalize( jump, "jra" );
658: jump->op = OP_JUMP; /* rather than OP_BRANCH */
659: newreference( newlabel, jump );
660: /* add another new label after the new jump */
661: newlabel = insert_label( jump->forw );
662: /* flip condition on conditional, point it at the new label */
663: cannibalize( n, unbranch[(int)(n->subop)-(int)JEQ] );
664: n->op = OP_JUMP; /* rather than OP_BRANCH */
665: unreference( taillabel, n );
666: newreference( newlabel, n );
667: order_nodes();
668: n = taillabel->back;
669: /* if either of the old labels is superfluous, delete it */
670: if (headlabel->nref == 0 ) (void)deletenode(headlabel);
671: if (taillabel->nref == 0 ) (void)deletenode(taillabel);
672: nchanged++;
673: meter.loopiv++;
674: }
675: }
676: }
677: return nchanged;
678: }
679:
680: chase(n,tail)
681: register NODE *n, *tail;
682: {
683: register NODE *p;
684: if (n == tail)
685: return;
686: for (p = n->forw; p != n; p = p->forw) {
687: if (p == tail)
688: return;
689: }
690: printf("lost track of node %s\n", tail);
691: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.