1
2
3
4 package joeq.Compiler.Quad;
5 import java.util.ArrayList;
6 import java.util.Collection;
7 import java.util.Collections;
8 import java.util.Iterator;
9 import joeq.Class.jq_Method;
10 import joeq.Class.jq_MethodVisitor;
11 import joeq.Util.Templates.List;
12 import joeq.Util.Templates.ListIterator;
13 import jwutil.graphs.Navigator;
14 import jwutil.graphs.Traversals;
15 import jwutil.math.BitString;
16 import jwutil.math.BitString.BitStringIterator;
17
18 /***
19 *
20 * @author John Whaley <jwhaley@alum.mit.edu>
21 * @version $Id: Dominators.java 2465 2006-06-07 23:03:17Z joewhaley $
22 */
23 public class Dominators extends jq_MethodVisitor.EmptyVisitor implements BasicBlockVisitor {
24
25 /*** true = normal dominators.
26 * false = post dominators.
27 */
28 public Dominators(boolean direction) {
29 this.direction = direction;
30 }
31 public Dominators() {
32 this(false);
33 }
34
35 public static final boolean TRACE = false;
36
37 public final boolean direction;
38 public BitString[] dominators;
39 protected boolean change;
40 protected ControlFlowGraph cfg;
41 protected BasicBlock[] bbs;
42 private BitString temp;
43
44 public void visitMethod(jq_Method m) {
45 if (m.getBytecode() == null) return;
46 cfg = joeq.Compiler.Quad.CodeCache.getCode(m);
47 bbs = new BasicBlock[cfg.getNumberOfBasicBlocks()];
48 dominators = new BitString[cfg.getNumberOfBasicBlocks()];
49 temp = new BitString(dominators.length);
50 int offset = direction?1:0;
51 dominators[offset] = new BitString(dominators.length);
52 dominators[offset].setAll();
53 dominators[1-offset] = new BitString(dominators.length);
54 dominators[1-offset].set(1-offset);
55 for (int i=2; i<dominators.length; ++i) {
56 dominators[i] = new BitString(dominators.length);
57 dominators[i].setAll();
58 }
59 List.BasicBlock rpo;
60 if (direction)
61 rpo = cfg.reversePostOrder(cfg.entry());
62 else
63 rpo = cfg.reversePostOrderOnReverseGraph(cfg.exit());
64 for (;;) {
65 if (TRACE) System.out.println("Iterating over "+rpo);
66 change = false;
67 ListIterator.BasicBlock rpo_i = rpo.basicBlockIterator();
68 BasicBlock first = rpo_i.nextBasicBlock();
69 bbs[first.getID()] = first;
70 while (rpo_i.hasNext()) {
71 BasicBlock bb = rpo_i.nextBasicBlock();
72 this.visitBasicBlock(bb);
73 }
74 if (!change) break;
75 }
76
77
78
79
80
81 }
82
83 public void visitBasicBlock(BasicBlock bb) {
84 if (TRACE) System.out.println("Visiting: "+bb);
85 bbs[bb.getID()] = bb;
86 temp.setAll();
87 ListIterator.BasicBlock preds = direction?bb.getPredecessors().basicBlockIterator():
88 bb.getSuccessors().basicBlockIterator();
89 while (preds.hasNext()) {
90 BasicBlock pred = preds.nextBasicBlock();
91 if (TRACE) System.out.println("Visiting pred: "+pred);
92 temp.and(dominators[pred.getID()]);
93 }
94 if (direction) {
95 if (bb.isExceptionHandlerEntry()) {
96 Iterator it = cfg.getExceptionHandlersMatchingEntry(bb);
97 while (it.hasNext()) {
98 ExceptionHandler eh = (ExceptionHandler)it.next();
99 preds = eh.getHandledBasicBlocks().basicBlockIterator();
100 while (preds.hasNext()) {
101 BasicBlock pred = preds.nextBasicBlock();
102 if (TRACE) System.out.println("Visiting ex pred: "+pred);
103 temp.and(dominators[pred.getID()]);
104 }
105 }
106 }
107 } else {
108 ListIterator.ExceptionHandler it = bb.getExceptionHandlers().exceptionHandlerIterator();
109 while (it.hasNext()) {
110 ExceptionHandler eh = (ExceptionHandler)it.next();
111 BasicBlock pred = eh.getEntry();
112 if (TRACE) System.out.println("Visiting ex pred: "+pred);
113 temp.and(dominators[pred.getID()]);
114 }
115 }
116 temp.set(bb.getID());
117 if (!temp.equals(dominators[bb.getID()])) {
118 if (TRACE) System.out.println("Changed!");
119
120 dominators[bb.getID()].copyBits(temp);
121 change = true;
122 }
123
124
125 }
126
127 DominatorNode[] dominatorNodes;
128
129 public DominatorNode getDominatorNode(BasicBlock bb) {
130 return dominatorNodes[bb.getID()];
131 }
132
133 public BasicBlock getImmediateDominator(BasicBlock bb) {
134 DominatorNode n = getDominatorNode(bb);
135 return n.parent.getBasicBlock();
136 }
137
138 public DominatorNode computeTree() {
139
140 dominatorNodes = new DominatorNode[dominators.length];
141 ArrayList list = new ArrayList();
142 list.add(new ArrayList());
143 for (int depth = 1; ; ++depth) {
144 if (TRACE) System.out.println("depth: "+depth);
145 ArrayList list2 = new ArrayList();
146 boolean found = false;
147 for (int i=0; i<dominators.length; ++i) {
148 if (dominators[i].numberOfOnes() == depth) {
149 if (TRACE) System.out.println("bb"+i+" matches: "+dominators[i]);
150 found = true;
151 temp.copyBits(dominators[i]);
152 temp.clear(i);
153 DominatorNode parent = null;
154 Iterator it = ((ArrayList)list.get(depth-1)).iterator();
155 while (it.hasNext()) {
156 DominatorNode n = (DominatorNode)it.next();
157 if (temp.equals(dominators[n.getBasicBlock().getID()])) {
158 parent = n; break;
159 }
160 }
161 DominatorNode n0 = new DominatorNode(bbs[i], parent);
162 if (parent != null)
163 parent.addChild(n0);
164 dominatorNodes[i] = n0;
165 list2.add(n0);
166 }
167 }
168 list.add(list2);
169 if (!found) break;
170 }
171 DominatorNode root = (DominatorNode)((ArrayList)list.get(1)).get(0);
172 return root;
173 }
174
175 public static class DominatorNode {
176 public final BasicBlock bb;
177 public final DominatorNode parent;
178 public final ArrayList children;
179 public BitString dominance_frontier;
180
181 public DominatorNode(BasicBlock bb, DominatorNode parent) {
182 this.bb = bb; this.parent = parent; this.children = new ArrayList();
183 }
184
185 public BasicBlock getBasicBlock() { return bb; }
186 public DominatorNode getParent() { return parent; }
187 public int getNumberOfChildren() { return children.size(); }
188 public DominatorNode getChild(int i) { return (DominatorNode)children.get(i); }
189 public java.util.List getChildren() { return children; }
190 public void addChild(DominatorNode n) { children.add(n); }
191 public String toString() { return bb.toString(); }
192 public void dumpTree() {
193 System.out.println("Node: "+toString());
194 System.out.println("Children of :"+toString());
195 Iterator i = children.iterator();
196 while (i.hasNext()) {
197 ((DominatorNode)i.next()).dumpTree();
198 }
199 System.out.println("End of children of :"+toString());
200 }
201 }
202
203 public static final Navigator dom_nav = new Navigator() {
204
205 public Collection next(Object node) {
206 DominatorNode dn = (DominatorNode) node;
207 return dn.children;
208 }
209
210 public Collection prev(Object node) {
211 DominatorNode dn = (DominatorNode) node;
212 if (dn.parent == null) return Collections.EMPTY_LIST;
213 return Collections.singleton(dn.parent);
214 }
215
216 };
217
218 public void calculateDominanceFrontier(DominatorNode tree) {
219
220 for (Iterator x = Traversals.postOrder(dom_nav, tree).iterator(); x.hasNext();) {
221 DominatorNode v = (DominatorNode) x.next();
222 BasicBlock X = v.getBasicBlock();
223 BitString DF = new BitString(dominatorNodes.length);
224 v.dominance_frontier = DF;
225
226 for (Iterator y = X.getSuccessors().iterator(); y.hasNext();) {
227 BasicBlock Y = (BasicBlock) y.next();
228
229 if (Y.isExit())
230 continue;
231
232 if (getImmediateDominator(Y) != X)
233 DF.set(Y.getID());
234 }
235
236 for (Iterator z = getDominatorNode(X).getChildren().iterator(); z.hasNext();) {
237 DominatorNode zVertex = (DominatorNode) z.next();
238
239
240 for (BitStringIterator y = zVertex.dominance_frontier
241 .iterator(); y.hasNext();) {
242 int I = y.nextIndex();
243 BasicBlock Y = bbs[I];
244
245 if (getImmediateDominator(Y) != X)
246 DF.set(Y.getID());
247 }
248 }
249 }
250 }
251
252 public boolean dominates(int b, BitString b2) {
253 BitString b1 = (BitString) this.dominators[b].clone();
254 b1.minus(b2);
255 return b1.isZero();
256 }
257
258 public BitString getDominanceFrontier(BitString bits) {
259 BitString result = new BitString(dominatorNodes.length);
260 for (BitStringIterator y = bits.iterator(); y.hasNext();) {
261 int I = y.nextIndex();
262 DominatorNode dn = dominatorNodes[I];
263 result.or(dn.dominance_frontier);
264 }
265 return result;
266 }
267 public BitString getIteratedDominanceFrontier(BitString S) {
268 BitString DFi = getDominanceFrontier(S);
269 for (;;) {
270 BitString DFiplus1 = getDominanceFrontier(DFi);
271 DFiplus1.or(DFi);
272 if (DFi.equals(DFiplus1))
273 break;
274 DFi = DFiplus1;
275 }
276 return DFi;
277 }
278
279 public static void main(String[] args) {
280 joeq.Main.HostedVM.initialize();
281
282 joeq.Class.jq_Class c = (joeq.Class.jq_Class) joeq.Class.jq_Type.parseType(args[0]);
283 c.load();
284 Dominators dom = new Dominators();
285 jq_Method[] ms = c.getDeclaredStaticMethods();
286 for (int i=0; i<ms.length; ++i) {
287 dom.visitMethod(ms[i]);
288 DominatorNode n = dom.computeTree();
289 n.dumpTree();
290 }
291 }
292
293 }