1 /*- 2 * %sccs.include.proprietary.c% 3 */ 4 5 #ifndef lint 6 static char sccsid[] = "@(#)2.tree.c 8.1 (Berkeley) 06/06/93"; 7 #endif /* not lint */ 8 9 #include <stdio.h> 10 # 11 /* use inarc, dom, and head to build tree representing structure of program. 12 Each node v has CHILDNUM(v) children denoted by 13 LCHILD(v,0), LCHILD(v,1),... 14 RSIB((v) is right sibling of v or UNDEFINED; 15 RSIB(v) represents code following v at the same level of nesting, 16 while LCHILD(v,i) represents code nested within v 17 */ 18 #include "def.h" 19 #include "2.def.h" 20 21 gettree(inarc,dom,head) /* build tree */ 22 struct list **inarc; 23 VERT *dom, *head; 24 { 25 VERT v,u,from; 26 int i; 27 for ( v = 0; v < nodenum; ++v) 28 { 29 RSIB(v) = UNDEFINED; 30 for (i = 0; i < CHILDNUM(v); ++i) 31 LCHILD(v,i) = UNDEFINED; 32 } 33 for (i = accessnum-1; i > 0; --i) 34 { 35 v = after[i]; 36 from = oneelt(inarc[v]); /* the unique elt of inarc[v] or UNDEFINED */ 37 if (DEFINED(from)) 38 if (NTYPE(from) == IFVX && (head[v] == head[from] || asoc(v,exitsize) != -1) ) 39 /* place in clause of IFVX if in smallest loop containing it 40 or if size of code for v is <= exitsize */ 41 if (ARC(from,THEN) == v) 42 { 43 LCHILD(from,THEN) = v; 44 continue; 45 } 46 else 47 { 48 ASSERT(ARC(from,ELSE) == v,gettree); 49 LCHILD(from,ELSE) = v; 50 continue; 51 } 52 else if (NTYPE(v) == ITERVX || NTYPE(from) == ITERVX ) 53 /* LOOPVX -> ITERVX ->vert always in same loop*/ 54 { 55 LCHILD(from,0) = v; 56 continue; 57 } 58 else if (NTYPE(from) == SWCHVX) 59 { 60 ASSERT(0 < ARCNUM(v),gettree); 61 if (ARC(from,0) == v) 62 LCHILD(from,0) = v; 63 else 64 { 65 int j; 66 for (j = 1; j < ARCNUM(from); ++j) 67 if (ARC(from,j) == v) 68 {insib(ARC(from,j-1),v); 69 break; 70 } 71 } 72 continue; 73 } 74 else if (NTYPE(from) == ICASVX && (head[v] == head[from] || asoc(v,exitsize) != -1)) 75 { 76 LCHILD(from,0) = v; 77 continue; 78 } 79 else if (NTYPE(from) == DUMVX && ARC(from,0) == v) 80 { 81 LCHILD(from,0) = v; 82 continue; 83 } 84 if (loomem(v,head[dom[v]],head)) 85 /* v is in smallest loop containing dom[v] */ 86 insib(dom[v],v); 87 else 88 { 89 /* make v follow LOOPVX heading largest loop 90 containing DOM[v] but not v */ 91 ASSERT(DEFINED(head[dom[v]]),gettree); 92 for (u = head[dom[v]]; head[u] != head[v]; u = head[u]) 93 ASSERT(DEFINED(head[u]),gettree); 94 ASSERT(NTYPE(u) == ITERVX,gettree); 95 insib(FATH(u),v); 96 } 97 } 98 } 99 100 101 102 103 insib(w,v) /* make RSIB(w) = v, and make RSIB(rightmost sib of v) = old RSIB(w) */ 104 VERT w,v; 105 { 106 VERT u, temp; 107 temp = RSIB(w); 108 RSIB(w) = v; 109 for (u = v; DEFINED(RSIB(u)); u = RSIB(u)) 110 ; 111 RSIB(u) = temp; 112 } 113 114 115 asoc(v,n) /* return # of nodes associated with v if <= n, -1 otherwise */ 116 VERT v; 117 int n; 118 { 119 int count,i,temp; 120 VERT w; 121 count = (NTYPE(v) == STLNVX) ? CODELINES(v) : 1; 122 for (i = 0; i < CHILDNUM(v); ++i) 123 { 124 w = LCHILD(v,i); 125 if (!DEFINED(w)) continue; 126 temp = asoc(w,n-count); 127 if (temp == -1) return(-1); 128 count += temp; 129 if (count > n) return(-1); 130 } 131 if (DEFINED(RSIB(v))) 132 { 133 temp = asoc(RSIB(v),n-count); 134 if (temp == -1) return(-1); 135 count += temp; 136 } 137 if (count > n) return(-1); 138 else return(count); 139 } 140