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 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 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 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 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 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 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 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