Commit | Line | Data |
---|---|---|
0fc6e47b KB |
1 | /*- |
2 | * %sccs.include.proprietary.c% | |
3 | */ | |
4 | ||
3c3dae4d | 5 | #ifndef lint |
0fc6e47b KB |
6 | static char sccsid[] = "@(#)2.tree.c 4.2 (Berkeley) %G%"; |
7 | #endif /* not lint */ | |
3c3dae4d RH |
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 | } |