Commit | Line | Data |
---|---|---|
aaa7ced1 BJ |
1 | #include <stdio.h> |
2 | # | |
3 | /* depth-first search used to identify back edges, unreachable nodes; | |
4 | each node v entered by back edge replaced by | |
5 | LOOPVX ->ITERVX -> v, | |
6 | so that back edges entering v now enter the ITERVX, | |
7 | and other edges entering v now enter the LOOPVX. | |
8 | Nodes are numbered according to depth-first search: | |
9 | before numbering- ntobef[v] = i => node numbered v is i'th | |
10 | node in order of first visit during the search; | |
11 | after numbering- ntoaft[v] = i => node numbered v is i'th | |
12 | node visited in order of last visit during the search. | |
13 | Also, in this case after[i] = v. | |
14 | */ | |
15 | ||
16 | #include "def.h" | |
17 | #include "2.def.h" | |
18 | ||
19 | #define MAXINS 3 /* spacing needed between numbers generated during depth first search */ | |
20 | ||
21 | int *status; | |
22 | int befcount, aftcount; | |
23 | /* following defines used to mark back edges and nodes entered by back edges */ | |
24 | #define UNPROCESSED 0 | |
25 | #define STACKED 1 | |
26 | #define FINISHED 2 | |
27 | #define MARK(v) {REACH(v) = 1; } /* mark node v */ | |
28 | #define UNMARK(v) {REACH(v) = 0; } | |
29 | #define MARKED(v) (REACH(v)) | |
30 | #define MKEDGE(e) {if (e >= -1) e = -(e+3); } /* mark edge e */ | |
31 | #define UNMKEDGE(e) {if (e < -1) e = -(e+3); } | |
32 | #define BACKEDGE(e) (e < -1) | |
33 | ||
34 | ||
35 | dfs(v) /* depth first search */ | |
36 | VERT v; | |
37 | { | |
38 | int i; VERT w; | |
39 | accessnum = 0; | |
40 | status = challoc(sizeof(*status) * nodenum); | |
41 | for (w = 0; w < nodenum; ++w) | |
42 | { | |
43 | status[w] = UNPROCESSED; | |
44 | UNMARK(w); | |
45 | } | |
46 | search(v); | |
47 | chreach(); | |
48 | chfree(status, sizeof(*status) * nodenum); | |
49 | addloop(); | |
50 | after = challoc(sizeof(*after) * accessnum); | |
51 | for (i = 0; i < accessnum; ++i) | |
52 | after[i] = UNDEFINED; | |
53 | ntoaft = challoc(sizeof(*ntoaft) * nodenum); | |
54 | ntobef = challoc(sizeof(*ntobef) * nodenum); | |
55 | for (w = 0; w < nodenum; ++w) | |
56 | ntobef[w] = ntoaft[w] = UNDEFINED; | |
57 | befcount = 0; | |
58 | aftcount = 0; | |
59 | repsearch(v); | |
60 | } | |
61 | ||
62 | ||
63 | search(v) | |
64 | /* using depth first search, mark back edges using MKEDGE, and nodes entered by back | |
65 | edges using MARK */ | |
66 | VERT v; | |
67 | { | |
68 | VERT adj; int i; | |
69 | status[v] = STACKED; | |
70 | for(i = 0; i < ARCNUM(v); ++i) | |
71 | { | |
72 | adj = ARC(v,i); | |
73 | if (!DEFINED(adj)) continue; | |
74 | else if (status[adj] == UNPROCESSED) | |
75 | search(adj); | |
76 | else if (status[adj] == STACKED) | |
77 | { | |
78 | MARK(adj); /* mark adj as entered by back edge */ | |
79 | MKEDGE(ARC(v,i)); /* mark edge ARC(v,i) as being back edge */ | |
80 | } | |
81 | } | |
82 | status[v] = FINISHED; | |
83 | ++accessnum; | |
84 | } | |
85 | ||
86 | chreach() /* look for unreachable nodes */ | |
87 | { | |
88 | VERT v; | |
89 | LOGICAL unreach; | |
90 | unreach = FALSE; | |
91 | for (v = 0; v < nodenum; ++v) | |
92 | if (status[v] == UNPROCESSED && NTYPE(v) != FMTVX | |
93 | && NTYPE(v) != STOPVX && NTYPE(v) != RETVX) | |
94 | { | |
95 | unreach = TRUE; | |
96 | if (debug) | |
97 | fprintf(stderr,"node %d unreachable\n",v); | |
98 | } | |
99 | if (unreach) | |
100 | error(": unreachable statements - ","will be ignored",""); | |
101 | } | |
102 | ||
103 | ||
104 | addloop() /* add LOOPVX, ITERVX at nodes entered by back edges, and adjust edges */ | |
105 | { | |
106 | VERT v, adj; | |
107 | int j, oldnum; | |
108 | for (v = 0, oldnum = nodenum; v < oldnum; ++v) /* insloop increases nodenum */ | |
109 | if (MARKED(v)) | |
110 | { | |
111 | UNMARK(v); /* remove mark indicating v entered by back edge */ | |
112 | if (NTYPE(v) != ITERVX) /* DO loops already have ITERVX */ | |
113 | insloop(v); /* add LOOPVX, ITERVX since v entered by back edge*/ | |
114 | } | |
115 | /* arcs which used to enter v now enter LOOPVX; must make back edges enter ITERVX */ | |
116 | for (v = 0; v < nodenum; ++v) | |
117 | for (j = 0; j < ARCNUM(v); ++j) | |
118 | { | |
119 | if (BACKEDGE(ARC(v,j))) | |
120 | { | |
121 | UNMKEDGE(ARC(v,j)); /* return edge to normal value */ | |
122 | adj = ARC(v,j); | |
123 | if (NTYPE(adj) == ITERVX) continue; | |
124 | ASSERT(NTYPE(adj) == LOOPVX,addloop); | |
125 | ARC(v,j) = ARC(adj,0); /* change arc to point to ITERVX */ | |
126 | ASSERT(NTYPE(ARC(v,j)) == ITERVX,addloop); | |
127 | } | |
128 | } | |
129 | } | |
130 | ||
131 | insloop(v) /* insert LOOPVX, ITERVX at node number v */ | |
132 | VERT v; | |
133 | { | |
134 | VERT loo, iter; | |
135 | loo = create(LOOPVX, 1); | |
136 | iter = create(ITERVX,1); | |
137 | accessnum += 2; | |
138 | /* want LOOPVX to take on node number v, so that arcs other than back arcs | |
139 | entering v will enter the LOOPVX automatically */ | |
140 | exchange(&graph[v], &graph[loo]); | |
141 | exchange(&v, &loo); | |
142 | ARC(loo,0) = iter; | |
143 | ARC(iter,0) = v; | |
144 | FATH(iter) = UNDEFINED; /* will be defined later along with FATH for DOVX */ | |
145 | } | |
146 | ||
147 | exchange(p1,p2) /* exchange values of p1,p2 */ | |
148 | int *p1,*p2; | |
149 | { | |
150 | int temp; | |
151 | temp = *p1; | |
152 | *p1 = *p2; | |
153 | *p2 = temp; | |
154 | } | |
155 | ||
156 | ||
157 | repsearch(v) /* repeat df search in order to fill in after, ntoaft, ntobef tables */ | |
158 | VERT v; | |
159 | { | |
160 | VERT adj; int i,temp; | |
161 | ntobef[v] = befcount; | |
162 | ++befcount; | |
163 | for(i = 0; i < ARCNUM(v); ++i) | |
164 | { | |
165 | adj = ARC(v,i); | |
166 | if (DEFINED(adj) && ntobef[adj] == UNDEFINED) | |
167 | repsearch(adj); | |
168 | } | |
169 | ++aftcount; | |
170 | temp = accessnum - aftcount; | |
171 | after[temp] = v; | |
172 | ntoaft[v] = temp; | |
173 | } |