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