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