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