Source code: Compil3r/Quad/ControlFlowGraph.java
1 // ControlFlowGraph.java, created Fri Jan 11 16:42:38 2002 by joewhaley
2 // Copyright (C) 2001-3 John Whaley <jwhaley@alum.mit.edu>
3 // Licensed under the terms of the GNU LGPL; see COPYING for details.
4 package Compil3r.Quad;
5
6 import java.util.Collection;
7 import java.util.Collections;
8 import java.util.HashMap;
9 import java.util.Map;
10
11 import Bootstrap.PrimordialClassLoader;
12 import Clazz.jq_Method;
13 import Clazz.jq_Primitive;
14 import Clazz.jq_Type;
15 import Compil3r.Quad.Operand.BasicBlockTableOperand;
16 import Compil3r.Quad.Operand.ParamListOperand;
17 import Compil3r.Quad.Operand.RegisterOperand;
18 import Compil3r.Quad.Operand.TargetOperand;
19 import Compil3r.Quad.RegisterFactory.Register;
20 import Util.Assert;
21 import Util.Strings;
22 import Util.Collections.FilterIterator;
23 import Util.Graphs.Graph;
24 import Util.Graphs.Navigator;
25 import Util.Templates.List;
26 import Util.Templates.ListIterator;
27 import Util.Templates.ListWrapper;
28 import Util.Templates.UnmodifiableList;
29
30 /**
31 * Control flow graph for the Quad format.
32 * The control flow graph is a fundamental part of the quad intermediate representation.
33 * The control flow graph organizes the basic blocks for a method.
34 *
35 * Control flow graphs always include an entry basic block and an exit basic block.
36 * These basic blocks are always empty and have id numbers 0 and 1, respectively.
37 *
38 * A control flow graph includes references to the entry and exit nodes, and the
39 * set of exception handlers for the method.
40 *
41 * @author John Whaley <jwhaley@alum.mit.edu>
42 * @version $Id: ControlFlowGraph.java,v 1.20 2003/06/17 02:12:27 joewhaley Exp $
43 */
44
45 public class ControlFlowGraph implements Graph {
46
47 /* Method that this control flow graph represents. May be null for synthetic methods. */
48 private final jq_Method method;
49 /* Reference to the start node of this control flow graph. */
50 private final BasicBlock start_node;
51 /* Reference to the end node of this control flow graph. */
52 private final BasicBlock end_node;
53 /* List of exception handlers for this control flow graph. */
54 private final java.util.List/*<ExceptionHandler>*/ exception_handlers;
55
56 /* Register factory that we use on this control flow graph. */
57 private final RegisterFactory rf;
58
59 /* Current number of basic blocks, used to generate unique id's. */
60 private int bb_counter;
61 /* Current number of quads, used to generate unique id's. */
62 private int quad_counter;
63
64 /** Creates a new ControlFlowGraph.
65 * @param numOfExits the expected number of branches to the exit node.
66 * @param numOfExceptionHandlers the expected number of exception handlers. */
67 public ControlFlowGraph(jq_Method method, int numOfExits, int numOfExceptionHandlers, RegisterFactory rf) {
68 this.method = method;
69 start_node = BasicBlock.createStartNode();
70 end_node = BasicBlock.createEndNode(numOfExits);
71 exception_handlers = new java.util.ArrayList(numOfExceptionHandlers);
72 this.rf = rf;
73 bb_counter = 1; quad_counter = 0;
74 }
75
76 /** Returns the entry node.
77 * @return the entry node. */
78 public BasicBlock entry() { return start_node; }
79 /** Returns the exit node.
80 * @return the exit node. */
81 public BasicBlock exit() { return end_node; }
82
83 /** Returns the method this control flow graph represents.
84 * May be null for synthetic methods.
85 * @return method this control flow graph represents, or null for synthetic. */
86 public jq_Method getMethod() { return method; }
87
88 /** Returns the register factory used by this control flow graph.
89 * @return the register factory used by this control flow graph. */
90 public RegisterFactory getRegisterFactory() { return rf; }
91
92 /** Create a new basic block in this control flow graph. The new basic block
93 * is given a new, unique id number.
94 * @param numOfPredecessors number of predecessor basic blocks that this
95 basic block is expected to have.
96 * @param numOfSuccessors number of successor basic blocks that this
97 basic block is expected to have.
98 * @param numOfInstructions number of instructions that this basic block
99 is expected to have.
100 * @param ehs set of exception handlers for this basic block.
101 * @return the newly created basic block. */
102 public BasicBlock createBasicBlock(int numOfPredecessors, int numOfSuccessors, int numOfInstructions,
103 ExceptionHandlerList ehs) {
104 return BasicBlock.createBasicBlock(++bb_counter, numOfPredecessors, numOfSuccessors, numOfInstructions, ehs);
105 }
106 /** Use with care after renumbering basic blocks. */
107 void updateBBcounter(int value) { bb_counter = value-1; }
108 /** Returns a maximum on the number of basic blocks in this control flow graph.
109 * @return a maximum on the number of basic blocks in this control flow graph. */
110 public int getNumberOfBasicBlocks() { return bb_counter+1; }
111
112 public int getNumberOfQuads() {
113 int total = 0;
114 ListIterator.BasicBlock i = reversePostOrderIterator();
115 while (i.hasNext()) {
116 BasicBlock bb = i.nextBasicBlock();
117 total += bb.size();
118 }
119 return total;
120 }
121
122 /** Returns a new id number for a quad. */
123 public int getNewQuadID() { return ++quad_counter; }
124
125 /** Returns the maximum id number for a quad. */
126 public int getMaxQuadID() { return quad_counter; }
127
128 Map jsr_map;
129
130 public void addJSRInfo(JSRInfo info) {
131 if (jsr_map == null) jsr_map = new HashMap();
132 jsr_map.put(info.entry_block, info);
133 jsr_map.put(info.exit_block, info);
134 }
135
136 public JSRInfo getJSRInfo(BasicBlock bb) {
137 return (JSRInfo) jsr_map.get(bb);
138 }
139
140 /** Returns an iteration of the basic blocks in this graph in reverse post order.
141 * @return an iteration of the basic blocks in this graph in reverse post order. */
142 public ListIterator.BasicBlock reversePostOrderIterator() {
143 return reversePostOrderIterator(start_node);
144 }
145
146 /** Returns an iteration of the basic blocks in the reversed graph in reverse post order.
147 * The reversed graph is the graph where all edges are reversed.
148 * @return an iteration of the basic blocks in the reversed graph in reverse post order. */
149 public ListIterator.BasicBlock reversePostOrderOnReverseGraphIterator() {
150 return reversePostOrderOnReverseGraph(end_node).basicBlockIterator();
151 }
152
153 /** Returns an iteration of the basic blocks in the reversed graph in post order.
154 * The reversed graph is the graph where all edges are reversed.
155 * @return an iteration of the basic blocks in the reversed graph in post order. */
156 public ListIterator.BasicBlock postOrderOnReverseGraphIterator() {
157 return postOrderOnReverseGraph(end_node).basicBlockIterator();
158 }
159
160 /** Returns an iteration of the basic blocks in this graph reachable from the given
161 * basic block in reverse post order, starting from the given basic block.
162 * @param start_bb basic block to start reverse post order from.
163 * @return an iteration of the basic blocks in this graph reachable from the given basic block in reverse post order. */
164 public ListIterator.BasicBlock reversePostOrderIterator(BasicBlock start_bb) {
165 return reversePostOrder(start_bb).basicBlockIterator();
166 }
167
168 /** Visits all of the basic blocks in this graph with the given visitor.
169 * @param bbv visitor to visit each basic block with. */
170 public void visitBasicBlocks(BasicBlockVisitor bbv) {
171 for (ListIterator.BasicBlock i=reversePostOrderIterator(); i.hasNext(); ) {
172 BasicBlock bb = i.nextBasicBlock();
173 bbv.visitBasicBlock(bb);
174 }
175 }
176
177 /** Returns a list of basic blocks in reverse post order, starting at the given basic block.
178 * @param start_bb basic block to start from.
179 * @return a list of basic blocks in reverse post order, starting at the given basic block. */
180 public List.BasicBlock reversePostOrder(BasicBlock start_bb) {
181 java.util.LinkedList/*<BasicBlock>*/ result = new java.util.LinkedList();
182 boolean[] visited = new boolean[bb_counter+1];
183 reversePostOrder_helper(start_bb, visited, result, true);
184 BasicBlock[] bb = new BasicBlock[result.size()];
185 bb = (BasicBlock[])result.toArray(bb);
186 return new UnmodifiableList.BasicBlock(bb);
187 }
188
189 /** Returns a list of basic blocks of the reversed graph in reverse post order, starting at the given basic block.
190 * @param start_bb basic block to start from.
191 * @return a list of basic blocks of the reversed graph in reverse post order, starting at the given basic block. */
192 public List.BasicBlock reversePostOrderOnReverseGraph(BasicBlock start_bb) {
193 java.util.LinkedList/*<BasicBlock>*/ result = new java.util.LinkedList();
194 boolean[] visited = new boolean[bb_counter+1];
195 reversePostOrder_helper(start_bb, visited, result, false);
196 BasicBlock[] bb = new BasicBlock[result.size()];
197 bb = (BasicBlock[])result.toArray(bb);
198 return new UnmodifiableList.BasicBlock(bb);
199 }
200
201 /** Returns a list of basic blocks of the reversed graph in post order, starting at the given basic block.
202 * @param start_bb basic block to start from.
203 * @return a list of basic blocks of the reversed graph in post order, starting at the given basic block. */
204 public List.BasicBlock postOrderOnReverseGraph(BasicBlock start_bb) {
205 java.util.LinkedList/*<BasicBlock>*/ result = new java.util.LinkedList();
206 boolean[] visited = new boolean[bb_counter+1];
207 reversePostOrder_helper(start_bb, visited, result, false);
208 java.util.Collections.reverse(result);
209 BasicBlock[] bb = new BasicBlock[result.size()];
210 bb = (BasicBlock[])result.toArray(bb);
211 return new UnmodifiableList.BasicBlock(bb);
212 }
213
214 /** Helper function to compute reverse post order. */
215 private void reversePostOrder_helper(BasicBlock b, boolean[] visited, java.util.LinkedList result, boolean direction) {
216 if (visited[b.getID()]) return;
217 visited[b.getID()] = true;
218 List.BasicBlock bbs = direction ? b.getSuccessors() : b.getPredecessors();
219 ListIterator.BasicBlock bbi = bbs.basicBlockIterator();
220 while (bbi.hasNext()) {
221 BasicBlock b2 = bbi.nextBasicBlock();
222 reversePostOrder_helper(b2, visited, result, direction);
223 }
224 if (direction) {
225 ListIterator.ExceptionHandler ehi = b.getExceptionHandlers().exceptionHandlerIterator();
226 while (ehi.hasNext()) {
227 ExceptionHandler eh = ehi.nextExceptionHandler();
228 BasicBlock b2 = eh.getEntry();
229 reversePostOrder_helper(b2, visited, result, direction);
230 }
231 } else {
232 if (b.isExceptionHandlerEntry()) {
233 java.util.Iterator ex_handlers = getExceptionHandlersMatchingEntry(b);
234 while (ex_handlers.hasNext()) {
235 ExceptionHandler eh = (ExceptionHandler)ex_handlers.next();
236 ListIterator.BasicBlock handled = eh.getHandledBasicBlocks().basicBlockIterator();
237 while (handled.hasNext()) {
238 BasicBlock bb = handled.nextBasicBlock();
239 reversePostOrder_helper(bb, visited, result, direction);
240 }
241 }
242 }
243 }
244 result.addFirst(b);
245 }
246
247 void addExceptionHandler(ExceptionHandler eh) {
248 exception_handlers.add(eh);
249 }
250
251 /** Return the list of exception handlers in this control flow graph.
252 */
253 public List.ExceptionHandler getExceptionHandlers() {
254 return new ListWrapper.ExceptionHandler(exception_handlers);
255 }
256
257 /** Return an iterator of the exception handlers with the given entry point.
258 * @param b basic block to check exception handlers against.
259 * @return an iterator of the exception handlers with the given entry point. */
260 public java.util.Iterator getExceptionHandlersMatchingEntry(BasicBlock b) {
261 final BasicBlock bb = b;
262 return new FilterIterator(exception_handlers.iterator(),
263 new FilterIterator.Filter() {
264 public boolean isElement(Object o) {
265 ExceptionHandler eh = (ExceptionHandler)o;
266 return eh.getEntry() == bb;
267 }
268 });
269 }
270
271 /** Returns a verbose string of every basic block in this control flow graph.
272 * @return a verbose string of every basic block in this control flow graph. */
273 public String fullDump() {
274 StringBuffer sb = new StringBuffer();
275 sb.append("Control flow graph for "+method+":"+Strings.lineSep);
276 ListIterator.BasicBlock i = reversePostOrderIterator();
277 while (i.hasNext()) {
278 BasicBlock bb = i.nextBasicBlock();
279 sb.append(bb.fullDump());
280 }
281 sb.append("Exception handlers: "+exception_handlers);
282 sb.append(Strings.lineSep+"Register factory: "+rf);
283 return sb.toString();
284 }
285
286 private ExceptionHandler copier(HashMap map, ExceptionHandler this_eh) {
287 ExceptionHandler that_eh = (ExceptionHandler)map.get(this_eh);
288 if (that_eh != null) return that_eh;
289 map.put(this_eh, that_eh = new ExceptionHandler(this_eh.getExceptionType()));
290 that_eh.setEntry(copier(map, this_eh.getEntry()));
291 for (ListIterator.BasicBlock li =
292 this_eh.getHandledBasicBlocks().basicBlockIterator();
293 li.hasNext(); ) {
294 that_eh.addHandledBasicBlock(copier(map, li.nextBasicBlock()));
295 }
296 return that_eh;
297 }
298
299 private ExceptionHandlerList copier(HashMap map, ExceptionHandlerList this_ehl) {
300 if (this_ehl == null || this_ehl.size() == 0) return null;
301 ExceptionHandlerList that_ehl = (ExceptionHandlerList)map.get(this_ehl);
302 if (that_ehl != null) return that_ehl;
303 map.put(this_ehl, that_ehl = new ExceptionHandlerList());
304 that_ehl.setHandler(copier(map, this_ehl.getHandler()));
305 that_ehl.setParent(copier(map, this_ehl.getParent()));
306 return that_ehl;
307 }
308
309 private void updateOperand(HashMap map, Operand op) {
310 if (op == null) return;
311 if (op instanceof TargetOperand) {
312 ((TargetOperand)op).setTarget(copier(map, ((TargetOperand)op).getTarget()));
313 } else if (op instanceof BasicBlockTableOperand) {
314 BasicBlockTableOperand bt = (BasicBlockTableOperand)op;
315 for (int i=0; i<bt.size(); ++i) {
316 bt.set(i, copier(map, bt.get(i)));
317 }
318 } else if (op instanceof RegisterOperand) {
319 RegisterOperand rop = (RegisterOperand)op;
320 Register r = (Register)map.get(rop.getRegister());
321 if (r == null) {
322 if (rop.getRegister().getNumber() == -1) {
323 r = RegisterFactory.makeGuardReg().getRegister();
324 map.put(rop.getRegister(), r);
325 } else {
326 Assert.UNREACHABLE(rop.toString());
327 }
328 } else {
329 rop.setRegister(r);
330 }
331 } else if (op instanceof ParamListOperand) {
332 ParamListOperand plo = (ParamListOperand)op;
333 for (int i=0; i<plo.length(); ++i) {
334 updateOperand(map, plo.get(i));
335 }
336 }
337 }
338
339 private Quad copier(HashMap map, Quad this_q) {
340 Quad that_q = (Quad)map.get(this_q);
341 if (that_q != null) return that_q;
342 map.put(this_q, that_q = this_q.copy(++quad_counter));
343 updateOperand(map, that_q.getOp1());
344 updateOperand(map, that_q.getOp2());
345 updateOperand(map, that_q.getOp3());
346 updateOperand(map, that_q.getOp4());
347 return that_q;
348 }
349
350 private BasicBlock copier(HashMap map, BasicBlock this_bb) {
351 BasicBlock that_bb = (BasicBlock)map.get(this_bb);
352 if (that_bb != null) return that_bb;
353 that_bb = BasicBlock.createBasicBlock(++this.bb_counter,
354 this_bb.getNumberOfPredecessors(),
355 this_bb.getNumberOfSuccessors(),
356 this_bb.size());
357 map.put(this_bb, that_bb);
358 ExceptionHandlerList that_ehl = copier(map, this_bb.getExceptionHandlers());
359 that_bb.setExceptionHandlerList(that_ehl);
360 for (ListIterator.BasicBlock bbs = this_bb.getSuccessors().basicBlockIterator();
361 bbs.hasNext(); ) {
362 that_bb.addSuccessor(copier(map, bbs.nextBasicBlock()));
363 }
364 for (ListIterator.BasicBlock bbs = this_bb.getPredecessors().basicBlockIterator();
365 bbs.hasNext(); ) {
366 that_bb.addPredecessor(copier(map, bbs.nextBasicBlock()));
367 }
368 for (ListIterator.Quad qs = this_bb.iterator();
369 qs.hasNext(); ) {
370 that_bb.appendQuad(copier(map, qs.nextQuad()));
371 }
372 return that_bb;
373 }
374
375 static void addRegistersToMap(HashMap map, RegisterFactory from,
376 RegisterFactory to, jq_Type type) {
377 int n = from.getLocalSize(type);
378 Assert._assert(n == to.getLocalSize(type), n+" != "+to.getLocalSize(type));
379 for (int i=0; i<n; ++i) {
380 map.put(from.getLocal(i, type), to.getLocal(i, type));
381 }
382 n = from.getStackSize(type);
383 Assert._assert(n == to.getStackSize(type));
384 for (int i=0; i<n; ++i) {
385 map.put(from.getStack(i, type), to.getStack(i, type));
386 }
387 }
388
389 static void addRegistersToMap(HashMap map, RegisterFactory from,
390 RegisterFactory to) {
391 addRegistersToMap(map, from, to, jq_Primitive.INT);
392 addRegistersToMap(map, from, to, jq_Primitive.FLOAT);
393 addRegistersToMap(map, from, to, jq_Primitive.LONG);
394 addRegistersToMap(map, from, to, jq_Primitive.DOUBLE);
395 addRegistersToMap(map, from, to, PrimordialClassLoader.getJavaLangObject());
396 }
397
398 /** Merges the given control flow graph into this control flow graph.
399 * Doesn't modify the given control flow graph. A copy of the
400 * given control flow graph (with appropriate renumberings) is
401 * returned.
402 */
403 public ControlFlowGraph merge(ControlFlowGraph from) {
404 RegisterFactory that_rf = this.rf.merge(from.rf);
405 ControlFlowGraph that = new ControlFlowGraph(from.getMethod(),
406 from.exit().getNumberOfPredecessors(), from.exception_handlers.size(), that_rf);
407 HashMap map = new HashMap();
408 map.put(from.entry(), that.entry());
409 map.put(from.exit(), that.exit());
410
411 addRegistersToMap(map, from.getRegisterFactory(), that_rf);
412
413 for (ListIterator.ExceptionHandler exs = from.getExceptionHandlers().exceptionHandlerIterator();
414 exs.hasNext(); ) {
415 that.addExceptionHandler(copier(map, exs.nextExceptionHandler()));
416 }
417
418 that.entry().addSuccessor(copier(map, from.entry().getFallthroughSuccessor()));
419 for (ListIterator.BasicBlock bbs = from.exit().getPredecessors().basicBlockIterator();
420 bbs.hasNext(); ) {
421 that.exit().addPredecessor(copier(map, bbs.nextBasicBlock()));
422 }
423
424 that.bb_counter = this.bb_counter;
425 that.quad_counter = this.quad_counter;
426
427 return that;
428 }
429
430 public void appendExceptionHandlers(ExceptionHandlerList ehl) {
431 if (ehl == null || ehl.size() == 0) return;
432 ListIterator.BasicBlock l = reversePostOrderIterator();
433 while (l.hasNext()) {
434 BasicBlock bb = l.nextBasicBlock();
435 if (bb.isEntry() || bb.isExit()) continue;
436 bb.appendExceptionHandlerList(ehl);
437 }
438 }
439
440 /* (non-Javadoc)
441 * @see Util.Graphs.Graph#getRoots()
442 */
443 public Collection getRoots() {
444 return Collections.singleton(start_node);
445 }
446
447 /* (non-Javadoc)
448 * @see Util.Graphs.Graph#getNavigator()
449 */
450 public Navigator getNavigator() {
451 return new ControlFlowGraphNavigator(this);
452 }
453
454 }