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