1 /*- 2 * %sccs.include.proprietary.c% 3 */ 4 5 #ifndef lint 6 static char sccsid[] = "@(#)2.dom.c 8.1 (Berkeley) 06/06/93"; 7 #endif /* not lint */ 8 9 #include <stdio.h> 10 # 11 /* 12 set dom[v] to immediate dominator of v, based on arcs as stored in inarcs 13 (i.e. pretending the graph is reducible if it isn't). 14 Algorithm is from Hecht and Ullman, Analysis of a simple algorithm for global 15 flow analysis problems, except bit vector operations replaced by search 16 through DOM to save quadratic blowup in space 17 */ 18 #include "def.h" 19 #include "2.def.h" 20 21 22 getdom(inarc,dom) 23 struct list **inarc; 24 VERT *dom; 25 { 26 VERT v; 27 int i; 28 struct list *ls; 29 for (v = 0; v < nodenum; ++v) 30 dom[v] = UNDEFINED; 31 for (i = 1; i < accessnum; ++i) 32 { 33 v = after[i]; 34 for (ls = inarc[v]; ls; ls = ls->nxtlist) 35 { 36 ASSERT(ntoaft[ls->elt] < i,getdom); 37 dom[v] = comdom(dom[v],ls->elt,dom); 38 } 39 40 } 41 } 42 43 44 comdom(u,v,dom) /* find closest common dominator of u,v */ 45 VERT u,v, *dom; 46 { 47 if (u == UNDEFINED) return(v); 48 if (v == UNDEFINED) return(u); 49 while(u != v) 50 { 51 ASSERT(u != UNDEFINED && v != UNDEFINED, comdom); 52 if (ntoaft[u] < ntoaft[v]) 53 v = dom[v]; 54 else 55 u = dom[u]; 56 } 57 return(u); 58 } 59