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