1 cananian 1.1 // DomTree.java, created Mon Sep 14 17:38:43 1998 by cananian
2 cananian 1.8 // Copyright (C) 1998 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.8 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1 package harpoon.Analysis;
5 cananian 1.1
6 cananian 1.8.2.2 import harpoon.ClassFile.HCode;
7 cananian 1.8.2.2 import harpoon.ClassFile.HCodeEdge;
8 cananian 1.8.2.2 import harpoon.ClassFile.HCodeElement;
9 cananian 1.8.2.6 import harpoon.IR.Properties.CFGrapher;
10 cananian 1.8.2.1 import harpoon.Util.ArrayFactory;
11 cananian 1.8.2.7 import harpoon.Util.ArrayIterator;
12 cananian 1.12 import net.cscott.jutil.AggregateSetFactory;
13 cananian 1.12 import net.cscott.jutil.GenericMultiMap;
14 cananian 1.12 import net.cscott.jutil.MultiMap;
15 cananian 1.8.2.4 import harpoon.Util.Util;
16 cananian 1.12 import net.cscott.jutil.Default;
17 cananian 1.1
18 cananian 1.8.2.8 import java.util.Collection;
19 cananian 1.8.2.8 import java.util.HashMap;
20 cananian 1.1 import java.util.Hashtable;
21 cananian 1.8.2.7 import java.util.Iterator;
22 cananian 1.8.2.8 import java.util.Map;
23 cananian 1.1 import java.util.Vector;
24 pnkfelix 1.8.2.9 import java.util.List;
25 pnkfelix 1.8.2.9 import java.util.Stack;
26 pnkfelix 1.8.2.9
27 cananian 1.1 /**
28 cananian 1.1 * <code>DomTree</code> computes the dominator tree of a flowgraph-structured
29 cananian 1.8.2.7 * IR. The <code>HCode</code> must have a valid
30 cananian 1.8.2.7 * <code>CFGrapher</code>.
31 cananian 1.1 *
32 cananian 1.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
33 cananian 1.12 * @version $Id: DomTree.java,v 1.12 2004/02/08 01:49:03 cananian Exp $
34 cananian 1.1 */
35 cananian 1.1
36 cananian 1.10.2.2 public class DomTree<HCE extends HCodeElement> /*implements Graph*/ {
37 cananian 1.8.2.7 /** <code>HCode</code> this <code>DomTree</code> corresponds to. */
38 cananian 1.10.2.2 final HCode<HCE> hcode; // included only for DomFrontier's use.
39 cananian 1.8.2.7 /** <code>CFGrapher</code> used to construct this <code>DomTree</code>.*/
40 cananian 1.10.2.2 final CFGrapher<HCE> grapher; // included only for DomFrontier's use.
41 cananian 1.1 /** Mapping of HCodeElements to their immediate dominators. */
42 cananian 1.10.2.2 Map<HCE,HCE> idom = new HashMap<HCE,HCE>();
43 cananian 1.1 /** Reverse mapping: mapping of an HCodeElement to the elements which
44 cananian 1.1 * have this element as their immediate dominator. */
45 cananian 1.10.2.2 final SetHTable<HCE> children;
46 cananian 1.8.2.7
47 cananian 1.8.2.7 /** Creates a new <code>DomTree</code> with the dominator
48 cananian 1.8.2.7 * tree for the given <code>HCode</code>; if <code>isPost</code> is
49 cananian 1.8.2.6 * true, creates a postdominator tree instead. Uses the default
50 cananian 1.8.2.6 * <code>CFGrapher</code>, which means the elements of the
51 cananian 1.8.2.6 * <code>HCode</code> must implement <code>CFGraphable</code>. */
52 cananian 1.10.2.2 public DomTree(HCode<HCE> hcode, boolean isPost) {
53 cananian 1.12 this(hcode, (CFGrapher<HCE>) CFGrapher.DEFAULT, isPost);
54 cananian 1.8.2.6 }
55 cananian 1.8.2.7 /** Creates a new <code>DomTree</code> with the dominator
56 cananian 1.8.2.7 * tree for the given <code>HCode</code>; if <code>isPost</code> is
57 cananian 1.8.2.7 * true, creates a postdominator tree instead. Uses the specified
58 cananian 1.8.2.7 * <code>CFGrapher</code> to construct the control flow graph of
59 cananian 1.8.2.7 * the <code>HCode</code>. */
60 cananian 1.10.2.2 public DomTree(HCode<HCE> hcode, CFGrapher<HCE> grapher, boolean isPost) {
61 cananian 1.8.2.7 this(hcode, isPost?grapher.edgeReversed():grapher);
62 cananian 1.8.2.7 }
63 cananian 1.8.2.7 /** Common constructor. Not for external use: we want people to be aware
64 cananian 1.8.2.7 * whether they're requesting a dominator or post-dominator tree. */
65 cananian 1.10.2.2 private DomTree(HCode<HCE> hcode, CFGrapher<HCE> grapher) {
66 cananian 1.8.2.7 this.hcode = hcode;
67 cananian 1.8.2.6 this.grapher = grapher;
68 cananian 1.10.2.2 this.children = new SetHTable<HCE>(hcode.elementArrayFactory());
69 cananian 1.8.2.7 analyze(hcode, grapher);
70 cananian 1.8.2.7
71 cananian 1.1 }
72 cananian 1.1
73 cananian 1.8.2.7 /** Return the roots of the (post-)dominator tree (forest). */
74 cananian 1.10.2.2 public HCE[] roots() {
75 cananian 1.8.2.7 return grapher.getFirstElements(hcode);
76 cananian 1.8.2.7 }
77 cananian 1.8.2.7
78 cananian 1.8.2.7 /** Return the immediate (post)dominator of an <code>HCodeElement</code>.
79 cananian 1.8.2.7 * @return the immediate (post)dominator of <code>n</code>, or
80 cananian 1.8.2.7 * <code>null</code> if <code>n</code> is the root (a leaf)
81 cananian 1.1 * of the flow graph. */
82 cananian 1.10.2.2 public HCE idom(HCE n) {
83 cananian 1.10.2.2 return idom.get(n);
84 cananian 1.1 }
85 cananian 1.3 /** Return the children of an <code>HCodeElement</code> in the immediate
86 cananian 1.8.2.7 * (post)dominator tree.
87 cananian 1.1 * @return an array with all the children of <code>n</code> in the
88 cananian 1.1 * immediate dominator tree, or a zero-length array if
89 cananian 1.1 * <code>n</code> is a tree leaf. */
90 cananian 1.10.2.2 public HCE[] children(HCE n) {
91 cananian 1.8.2.7 return children.getSet(n);
92 cananian 1.1 }
93 cananian 1.1
94 cananian 1.8.2.6 /** Analyze an <code>HCode</code>. */
95 cananian 1.10.2.3 private void analyze(final HCode<HCE> hc, final CFGrapher<HCE> grapher) {
96 cananian 1.1 // Setup lists and tables.
97 cananian 1.10.2.2 final IntHTable<HCE> dfnum = new IntHTable<HCE>();
98 cananian 1.10.2.2 final Map<HCE,HCE> semi = new HashMap<HCE,HCE>();
99 cananian 1.10.2.2 final Map<HCE,HCE> ancestor = new HashMap<HCE,HCE>();
100 cananian 1.10.2.2 final Map<HCE,HCE> parent = new HashMap<HCE,HCE>();
101 cananian 1.10.2.2 final Map<HCE,HCE> best = new HashMap<HCE,HCE>();
102 cananian 1.1
103 cananian 1.10.2.2 SetHTable<HCE> bucket = new SetHTable<HCE>(hc.elementArrayFactory());
104 cananian 1.10.2.2 Map<HCE,HCE> samedom = new HashMap<HCE,HCE>();
105 cananian 1.1
106 cananian 1.10.2.2 final Vector<HCE> vertex = new Vector<HCE>();
107 cananian 1.1
108 cananian 1.1 /** Utility class wraps analysis subroutines. */
109 cananian 1.1 class Utility {
110 pnkfelix 1.8.2.9 /** Number nodes of depth-first spanning tree
111 pnkfelix 1.8.2.9 @requires: n_orig != null. (note p_orig may be null)
112 pnkfelix 1.8.2.9 */
113 cananian 1.10.2.2 void DFS(HCE p_orig, HCE n_orig) {
114 pnkfelix 1.8.2.9 // Does an depth first iteration by keeping partially
115 pnkfelix 1.8.2.9 // traversed iterators on the stack.
116 cananian 1.10.2.2 Stack<Pair<HCE,Iterator<HCE>>> stk =
117 cananian 1.10.2.2 new Stack<Pair<HCE,Iterator<HCE>>>();
118 cananian 1.10.2.2 stk.push( cons(p_orig, Default.singletonIterator(n_orig)) );
119 pnkfelix 1.8.2.9 while( ! stk.isEmpty() ){
120 cananian 1.10.2.2 Pair<HCE,Iterator<HCE>> pair = stk.peek();
121 cananian 1.10.2.2 HCE p = pair.left;
122 cananian 1.10.2.2 Iterator<HCE> niter = pair.right;
123 pnkfelix 1.8.2.9 if (niter.hasNext()){
124 cananian 1.10.2.2 HCE n = niter.next();
125 pnkfelix 1.8.2.9 if (dfnum.getInt(n)==0) {
126 pnkfelix 1.8.2.9 int N = vertex.size()+1;
127 pnkfelix 1.8.2.9 dfnum.putInt(n, N);
128 pnkfelix 1.8.2.9 if (p!=null)
129 pnkfelix 1.8.2.9 parent.put(n, p);
130 pnkfelix 1.8.2.9 vertex.addElement(n);
131 cananian 1.10.2.2 Iterator<HCE> succIter = grapher.succElemC(n).iterator();
132 cananian 1.10.2.2 stk.push( cons(n, succIter) );
133 pnkfelix 1.8.2.9 }
134 pnkfelix 1.8.2.9 continue;
135 cananian 1.2 } else {
136 pnkfelix 1.8.2.9 stk.pop();
137 cananian 1.2 }
138 cananian 1.1 }
139 cananian 1.1 }
140 pnkfelix 1.8.2.9
141 cananian 1.1 /** Add edge p->n to spanning forest. */
142 cananian 1.10.2.2 void Link(HCE p, HCE n) {
143 cananian 1.1 ancestor.put(n, p);
144 cananian 1.1 best.put(n, n);
145 cananian 1.1 }
146 cananian 1.1 /** In the forest, find nonroot ancestor of n that has
147 cananian 1.1 * lowest-numbered semidominator. */
148 cananian 1.10.2.2 HCE Eval(HCE vOrig) {
149 cananian 1.10.2.2 HCE v, a, b;
150 cananian 1.10.2.2 Stack<Pair<HCE,HCE>> stk = new Stack<Pair<HCE,HCE>>();
151 pnkfelix 1.8.2.9 v = vOrig;
152 cananian 1.10.2.2 a = ancestor.get(v);
153 pnkfelix 1.8.2.9 while( ancestor.get(a) != null ){
154 cananian 1.10.2.2 stk.push( cons(v, a) );
155 cananian 1.10.2.2 v = a; a = ancestor.get(a);
156 pnkfelix 1.8.2.9 }
157 cananian 1.10.2.2 b = best.get(v); // base case return
158 pnkfelix 1.8.2.9 while( ! stk.isEmpty() ){
159 cananian 1.10.2.2 Pair<HCE,HCE> pair = stk.pop();
160 cananian 1.10.2.2 v = pair.left;
161 cananian 1.10.2.2 a = pair.right;
162 cananian 1.1 ancestor.put(v, ancestor.get(a));
163 pnkfelix 1.8.2.9 if (dfnum.getInt(semi.get(b)) <
164 pnkfelix 1.8.2.9 dfnum.getInt(semi.get(best.get(v)))){
165 cananian 1.1 best.put(v, b);
166 pnkfelix 1.8.2.9 }
167 cananian 1.10.2.2 b = best.get(v); // recursive return
168 cananian 1.1 }
169 cananian 1.10.2.1 assert v == vOrig;
170 cananian 1.10.2.1 assert b == best.get(v);
171 pnkfelix 1.8.2.9 return b;
172 cananian 1.1 }
173 cananian 1.1 }
174 cananian 1.1 Utility u = new Utility();
175 cananian 1.1
176 cananian 1.1 // Dominators algorithm:
177 cananian 1.10.2.3 for (Iterator<HCE> it = new ArrayIterator<HCE>
178 cananian 1.10.2.3 (grapher.getFirstElements(hc)); it.hasNext(); )
179 cananian 1.10.2.2 u.DFS(null, it.next());
180 cananian 1.2
181 cananian 1.2 for (int i=vertex.size()-1; i>=0; i--) {
182 cananian 1.1 // calculate the semidominator of vertex[i]
183 cananian 1.10.2.2 HCE n = vertex.elementAt(i);
184 cananian 1.10.2.2 HCE p = parent.get(n);
185 cananian 1.10.2.2 HCE s = p;
186 cananian 1.10.2.2 HCE sprime;
187 cananian 1.1
188 cananian 1.2 if (p == null) continue; // skip root(s).
189 cananian 1.2
190 cananian 1.1 // (for each predecessor v of n)
191 cananian 1.10.2.2 for (Iterator<HCodeEdge<HCE>> it=grapher.predC(n).iterator(); it.hasNext(); ) {
192 cananian 1.10.2.2 HCE v = it.next().from();
193 cananian 1.1 // ignore unreachable nodes.
194 cananian 1.1 if (!dfnum.containsKey(v)) continue;
195 cananian 1.7 if (dfnum.getInt(v) <= dfnum.getInt(n))
196 cananian 1.1 sprime = v;
197 cananian 1.1 else
198 cananian 1.10.2.2 sprime = semi.get(u.Eval(v));
199 cananian 1.1 if (dfnum.getInt(sprime) < dfnum.getInt(s))
200 cananian 1.1 s = sprime;
201 cananian 1.1 }
202 cananian 1.1 semi.put(n, s);
203 cananian 1.1
204 cananian 1.1 // Calculation of n's dominator is deferred until the path
205 cananian 1.1 // from s to n has been linked into the forest.
206 cananian 1.1 bucket.unionSet(s, n);
207 cananian 1.1 u.Link(p, n);
208 cananian 1.1
209 cananian 1.1 // Now that the path from p to n has been linked into the
210 cananian 1.1 // spanning forest, calculate the dominator of v (or else defer
211 cananian 1.1 // the calculation).
212 cananian 1.1 // (for each v in bucket[p])
213 cananian 1.10.2.2 HCE[] hcel = bucket.getSet(p);
214 cananian 1.1 for (int j=0; j<hcel.length; j++) {
215 cananian 1.10.2.2 HCE v = hcel[j];
216 cananian 1.10.2.2 HCE y = u.Eval(v);
217 cananian 1.1 if (semi.get(y) == semi.get(v))
218 cananian 1.1 idom.put(v, p);
219 cananian 1.1 else
220 cananian 1.1 samedom.put(v, y);
221 cananian 1.1 }
222 cananian 1.1 bucket.clearSet(p);
223 cananian 1.1 }
224 cananian 1.1 // Now all the deferred dominator calculations are performed.
225 cananian 1.2 for (int i=0; i<vertex.size(); i++) {
226 cananian 1.10.2.2 HCE n = vertex.elementAt(i);
227 cananian 1.2 if (parent.get(n)==null) continue; // skip root(s).
228 cananian 1.1 if (samedom.get(n)!=null)
229 cananian 1.1 idom.put(n, idom.get(samedom.get(n)));
230 cananian 1.1 }
231 cananian 1.1 // done. Make inverse mapping.
232 cananian 1.2 for (int i=0; i<vertex.size(); i++) {
233 cananian 1.10.2.2 HCE n = vertex.elementAt(i);
234 cananian 1.10.2.2 HCE id = idom.get(n);
235 cananian 1.2 if (parent.get(n)==null) continue; // skip root(s).
236 cananian 1.1 children.unionSet(id, n);
237 cananian 1.1 }
238 cananian 1.1 }
239 cananian 1.1
240 cananian 1.10.2.2 // utility class.
241 cananian 1.10.2.2 static class Pair<A,B> {
242 cananian 1.10.2.2 public final A left;
243 cananian 1.10.2.2 public final B right;
244 cananian 1.10.2.2 Pair(A a, B b) { this.left = a; this.right = b; }
245 cananian 1.10.2.2 }
246 cananian 1.10.2.2 private static <A,B> Pair<A,B> cons(A a, B b) { return new Pair(a, b); }
247 cananian 1.1
248 cananian 1.1 // Useful Hashtable extensions.
249 cananian 1.10.2.2 static class IntHTable<V> {
250 cananian 1.10.2.2 private Map<V,Integer> m = new HashMap<V,Integer>();
251 cananian 1.10.2.2 void putInt(V o, int n) {
252 cananian 1.8.2.8 m.put(o, new Integer(n));
253 cananian 1.1 }
254 cananian 1.10.2.2 int getInt(V o) {
255 cananian 1.8.2.8 if (!m.containsKey(o)) return 0;
256 cananian 1.10.2.2 return m.get(o).intValue();
257 cananian 1.8.2.8 }
258 cananian 1.8.2.8 boolean containsKey(Object o) {
259 cananian 1.8.2.8 return m.containsKey(o);
260 cananian 1.1 }
261 cananian 1.1 }
262 cananian 1.10.2.2 static class SetHTable<HCE extends HCodeElement> {
263 cananian 1.10.2.2 ArrayFactory<HCE> af;
264 cananian 1.10.2.2 MultiMap<HCE,HCE> mm =
265 cananian 1.10.2.2 new GenericMultiMap<HCE,HCE>(new AggregateSetFactory<HCE>());
266 cananian 1.10.2.2 SetHTable(ArrayFactory<HCE> af) { super(); this.af = af; }
267 cananian 1.10.2.2 void clearSet(HCE hce) {
268 cananian 1.8.2.8 mm.remove(hce);
269 cananian 1.1 }
270 cananian 1.10.2.2 HCE[] getSet(HCE hce) {
271 cananian 1.10.2.2 Collection<HCE> c = mm.getValues(hce);
272 cananian 1.10.2.2 return c.toArray(af.newArray(c.size()));
273 cananian 1.1 }
274 cananian 1.10.2.2 void unionSet(HCE hce, HCE newEl) {
275 cananian 1.8.2.8 mm.add(hce, newEl);
276 cananian 1.1 }
277 cananian 1.1 }
278 cananian 1.1 }