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