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