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
comdom(u,v,dom)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