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