Commit | Line | Data |
---|---|---|
42d6e430 BJ |
1 | #include <stdio.h> |
2 | # | |
3 | /* find forward in-arcs for each node, pretending that arcs which jump into a loop | |
4 | jump to the head of the largest such loop instead, based on the | |
5 | depth first search tree */ | |
6 | #include "def.h" | |
7 | #include "2.def.h" | |
8 | ||
9 | getinarc(inarc,head) /* construct array "inarc" containing in arcs for each node */ | |
10 | struct list **inarc; | |
11 | VERT *head; | |
12 | { | |
13 | VERT v,adj,x; | |
14 | int i, j; | |
15 | ||
16 | for (v=0; v < nodenum; ++v) inarc[v] = 0; | |
17 | ||
18 | /* fill in inarc nodes */ | |
19 | ||
20 | for (i = 0; i < accessnum; ++i) | |
21 | { | |
22 | v = after[i]; | |
23 | for (j = 0; j < ARCNUM(v); ++j) | |
24 | { | |
25 | adj = ARC(v,j); | |
26 | if (!DEFINED(adj)) | |
27 | continue; | |
28 | if (ntoaft[adj] > ntoaft[v]) /* not a back edge */ | |
29 | /* if edge jumps into loop, pretend jumps to head of | |
30 | largest loop jumped into */ | |
31 | { | |
32 | x = maxentry(v,adj,head); | |
33 | if (!DEFINED(x)) x = adj; | |
34 | else x = FATH(x); | |
35 | ||
36 | inarc[x] = consls(v,inarc[x]); /* insert v in list inarc[x] */ | |
37 | } | |
38 | } | |
39 | } | |
40 | } | |
41 | ||
42 | ||
43 | ||
44 | maxentry(x,y,head) /* return z if z is ITERVX of largest loop containing y but not x, UNDEFINED otherwise */ | |
45 | VERT x,y, *head; | |
46 | { | |
47 | if (head[y] == UNDEFINED) return(UNDEFINED); | |
48 | if (loomem(x,head[y], head)) return (UNDEFINED); | |
49 | y = head[y]; | |
50 | while (head[y] != UNDEFINED) | |
51 | { | |
52 | if (loomem(x,head[y],head)) return(y); | |
53 | y = head[y]; | |
54 | } | |
55 | return(y); | |
56 | } | |
57 | ||
58 | ||
59 | ||
60 | loomem(x,y,head) /* return TRUE if x is in loop headed by y, FALSE otherwise */ | |
61 | VERT x,y, *head; | |
62 | { | |
63 | VERT w; | |
64 | if (!DEFINED(y)) return(TRUE); | |
65 | ASSERT(NTYPE(y) == ITERVX, loomem); | |
66 | for (w = (NTYPE(x) == ITERVX) ? x : head[x]; DEFINED(w); w = head[w]) | |
67 | if (w == y) return (TRUE); | |
68 | return(FALSE); | |
69 | } |