1
2
3
4 package joeq.Compiler.BytecodeAnalysis;
5
6 import java.util.HashMap;
7 import java.util.ListIterator;
8 import java.util.Map;
9 import joeq.Class.jq_Method;
10 import joeq.Class.jq_TryCatchBC;
11 import jwutil.math.BitString;
12 import jwutil.math.BitString.BitStringIterator;
13 import jwutil.util.Assert;
14
15 /***
16 * Control flow graph for a bytecode stream. The data structure is immutable
17 * and corresponds exactly to the underlying bytecodes.
18 *
19 * @author John Whaley <jwhaley@alum.mit.edu>
20 * @version $Id: ControlFlowGraph.java 2465 2006-06-07 23:03:17Z joewhaley $
21 */
22 public class ControlFlowGraph {
23
24 public static final boolean TRACE = false;
25
26 /*** Array of basic blocks, ordered by their appearance in the bytecode. */
27 private final BasicBlock[] basic_blocks;
28 /*** Map from basic blocks to their JSR info.
29 * There is JSR info associated with the entry and exit blocks of each
30 * JSR subroutine. */
31 private Map
32
33 /*** Creates new ControlFlowGraph */
34 private ControlFlowGraph(int n_bb, int n_handlers) {
35 basic_blocks = new BasicBlock[n_bb];
36 }
37
38 /*** Returns the entry basic block. */
39 public BasicBlock getEntry() { return basic_blocks[0]; }
40 /*** Returns the exit basic block. */
41 public BasicBlock getExit() { return basic_blocks[1]; }
42 /*** Returns the number of basic blocks. */
43 public int getNumberOfBasicBlocks() { return basic_blocks.length; }
44 /*** Returns the basic block with the given number. */
45 public BasicBlock getBasicBlock(int index) { return basic_blocks[index]; }
46
47 /*** Add info about a JSR subroutine. The JSR subroutine has the given
48 * entry and exit blocks and modifies the given locals. This info is
49 * associated with the entry and exit blocks.
50 *
51 * @param entry entry block
52 * @param exit exit block
53 * @param locals which locals are modified
54 */
55 public void addJSRInfo(BasicBlock entry, BasicBlock exit, boolean[] locals) {
56 if (jsr_info == null) jsr_info = new HashMap();
57 JSRInfo nfo = new JSRInfo(entry, exit, locals);
58 jsr_info.put(entry, nfo);
59 jsr_info.put(exit, nfo);
60 }
61
62 /*** Returns the JSR info about the JSR subroutine with the given entry/exit
63 * block, or null if there are none.
64 */
65 public JSRInfo getJSRInfo(BasicBlock b) {
66 return jsr_info != null ? (JSRInfo)jsr_info.get(b) : null;
67 }
68
69 /*** Returns the basic block that contains the given bytecode index.
70 */
71 public BasicBlock getBasicBlockByBytecodeIndex(int index) {
72
73 int lo, hi, mid;
74 lo = 2; hi = basic_blocks.length-1;
75 for (;;) {
76 mid = (lo + hi) >> 1;
77 if (lo > hi) break;
78 int mid_index = basic_blocks[mid].start;
79 if (index < mid_index) {
80 hi = mid-1;
81 } else {
82 lo = mid+1;
83 }
84 }
85 BasicBlock bb = basic_blocks[mid];
86 Assert._assert(bb.start == index);
87 return bb;
88 }
89
90 /*** Returns the basic blocks in reverse post-order.
91 */
92 public RPOBasicBlockIterator reversePostOrderIterator() {
93 return new RPOBasicBlockIterator(basic_blocks, basic_blocks[0]);
94 }
95
96 /*** Returns the basic blocks in reverse post-order starting from the given
97 * block.
98 */
99 public RPOBasicBlockIterator reversePostOrderIterator(BasicBlock start_bb) {
100 return new RPOBasicBlockIterator(basic_blocks, start_bb);
101 }
102
103 public interface BasicBlockIterator extends ListIterator {
104 BasicBlock nextBB();
105 BasicBlock previousBB();
106 }
107
108 public static class RPOBasicBlockIterator implements BasicBlockIterator {
109 private BasicBlock[] rpo;
110 private int index;
111
112 RPOBasicBlockIterator(BasicBlock[] bbs, BasicBlock start_bb) {
113 index = bbs.length;
114 rpo = new BasicBlock[index];
115 boolean[] visited = new boolean[index];
116 visit(visited, start_bb);
117 --index;
118 }
119
120 private void visit(boolean[] visited, BasicBlock b) {
121 int n = b.getNumberOfSuccessors();
122 for (int i=0; i<n; ++i) {
123 BasicBlock b2 = b.getSuccessor(i);
124 if (!visited[b2.id]) {
125 visited[b2.id] = true;
126 visit(visited, b2);
127 }
128 }
129 ExceptionHandlerIterator ehi = b.getExceptionHandlers();
130 while (ehi.hasNext()) {
131 ExceptionHandler eh = ehi.nextEH();
132 BasicBlock b2 = eh.getEntry();
133 if (!visited[b2.id]) {
134 visited[b2.id] = true;
135 visit(visited, b2);
136 }
137 }
138 rpo[--index] = b;
139 }
140
141 public boolean hasNext() { return index < rpo.length-1; }
142 public BasicBlock nextBB() { return rpo[++index]; }
143 public Object next() { return nextBB(); }
144 public int nextIndex() { return index+1; }
145 public boolean hasPrevious() { return index >= 0 && rpo[index] != null; }
146 public BasicBlock previousBB() { return rpo[index--]; }
147 public Object previous() { return previousBB(); }
148 public int previousIndex() { return index; }
149 public void remove() { throw new UnsupportedOperationException(); }
150 public void add(Object o) { throw new UnsupportedOperationException(); }
151 public void set(Object o) { throw new UnsupportedOperationException(); }
152 public void jumpToEnd() { index = rpo.length-1; }
153 public String toString() {
154 StringBuffer sb = new StringBuffer();
155 for (int i=0; i<rpo.length; ++i) {
156 sb.append(rpo[i]);
157 if (i == index) sb.append(" * ");
158 else sb.append(" ");
159 }
160 return sb.toString();
161 }
162 }
163
164 /*** Compute and return the control flow graph for the given method. */
165 public static ControlFlowGraph computeCFG(jq_Method method) {
166
167 InitialPass pass = new InitialPass(method);
168 pass.forwardTraversal();
169
170 byte[] bc = method.getBytecode();
171
172 BitString basic_block_start = pass.getBasicBlockStart();
173 BitString branch_locations = pass.getBranchLocations();
174
175 if (!basic_block_start.get(bc.length)) {
176
177 basic_block_start.set(bc.length);
178 }
179
180
181 jq_TryCatchBC[] exs = method.getExceptionTable();
182 for (int i=0; i<exs.length; ++i) {
183 jq_TryCatchBC ex = exs[i];
184 basic_block_start.set(ex.getStartPC());
185 basic_block_start.set(ex.getEndPC());
186 basic_block_start.set(ex.getHandlerPC());
187 }
188
189 if (TRACE) System.out.println("Number of bb: "+basic_block_start.numberOfOnes());
190 if (TRACE) System.out.println("Basic block start: "+basic_block_start);
191 if (TRACE) System.out.println("Branch locations : "+branch_locations);
192
193 int n_bb = basic_block_start.numberOfOnes();
194 n_bb += 1;
195 int[] n_pred = new int[n_bb];
196 ControlFlowGraph cfg = new ControlFlowGraph(n_bb, exs.length);
197 cfg.basic_blocks[0] = new BasicBlock(0, -1);
198 cfg.basic_blocks[1] = new BasicBlock(1, -1);
199 int bb_i = 2; BasicBlock bb = null;
200 cfg.basic_blocks[2] = bb = new BasicBlock(2, 0);
201 if (TRACE) System.out.println("Created "+bb+" at bytecode 0");
202 BitStringIterator it = basic_block_start.iterator();
203 Assert._assert(it.hasNext());
204 for (;;) {
205 Assert._assert(it.hasNext());
206 int bc_i = it.nextIndex();
207 cfg.basic_blocks[bb_i-1].end = bc_i-1;
208 if (TRACE) System.out.println("Ending basic block #"+(bb_i-1)+" at bytecode "+(bc_i-1));
209 if (bc_i == bc.length) break;
210 if (TRACE) System.out.println("Creating basic block #"+bb_i+" at bytecode "+bc_i);
211 bb = cfg.basic_blocks[bb_i] = new BasicBlock(bb_i, bc_i);
212 ++bb_i;
213 }
214 Assert._assert(!it.hasNext());
215 Assert._assert(bb_i == n_bb);
216 cfg.basic_blocks[0].end = -1;
217 cfg.basic_blocks[0].successors = new BasicBlock[1];
218 cfg.basic_blocks[0].successors[0] = cfg.basic_blocks[2];
219 cfg.basic_blocks[0].predecessors = cfg.basic_blocks[1].successors = new BasicBlock[0];
220
221 bb.end = bc.length-1;
222
223 n_pred[2] = 1;
224 it = branch_locations.iterator();
225 bb_i = 2;
226 BranchVisitor bv = new BranchVisitor(method, cfg, n_pred);
227 while (it.hasNext()) {
228 int bc_i = it.nextIndex();
229 bb = cfg.basic_blocks[bb_i];
230 if (TRACE) System.out.println("Next branch: bc "+bc_i);
231 while (bc_i > bb.end) {
232
233 bb.successors = new BasicBlock[1];
234 BasicBlock next_bb = bb.successors[0] = cfg.basic_blocks[bb_i+1];
235 ++n_pred[++bb_i];
236 if (TRACE) System.out.println("Fallthrough "+bb+" to "+next_bb);
237 bb = next_bb;
238 }
239
240 if (TRACE) System.out.println("Visiting branch at bc "+bc_i+" in "+bb);
241 bv.bb = bb;
242 bv.setLocation(bc_i);
243 bv.visitBytecode();
244 ++bb_i;
245 }
246 if (bb_i != n_bb) {
247
248 Assert._assert(bb_i == n_bb-1);
249 if (TRACE) System.out.println("Code falls off end!");
250 cfg.basic_blocks[bb_i].successors = new BasicBlock[0];
251 }
252
253 for (bb_i = 1; bb_i < n_bb; ++bb_i) {
254 bb = cfg.basic_blocks[bb_i];
255 bb.predecessors = new BasicBlock[n_pred[bb_i]];
256 if (TRACE) System.out.println(bb+" has "+n_pred[bb_i]+" predecessors");
257 Assert._assert(bb.successors != null);
258 n_pred[bb_i] = -1;
259 }
260
261 for (bb_i = 0; bb_i < n_bb; ++bb_i) {
262 bb = cfg.basic_blocks[bb_i];
263 for (int ct = 0; ct < bb.successors.length; ++ct) {
264 BasicBlock bb2 = bb.successors[ct];
265 bb2.predecessors[++n_pred[bb2.id]] = bb;
266 }
267 }
268
269 for (int i=exs.length-1; i>=0; --i) {
270 jq_TryCatchBC ex = exs[i];
271 bb = cfg.getBasicBlockByBytecodeIndex(ex.getStartPC());
272 if (bb.start >= ex.getEndPC())
273 throw new VerifyError("Exception handler "+i+" "+ex+": start ("+(int)bb.start+") comes after end ("+(int)ex.getEndPC()+")");
274 int numOfProtectedBlocks = (ex.getEndPC()==bc.length?n_bb:cfg.getBasicBlockByBytecodeIndex(ex.getEndPC()).id) - bb.id;
275 BasicBlock handler_bb = cfg.getBasicBlockByBytecodeIndex(ex.getHandlerPC());
276 ExceptionHandler eh = new ExceptionHandler(ex.getExceptionType(),
277 numOfProtectedBlocks,
278 handler_bb);
279 ExceptionHandlerList ehs = new ExceptionHandlerList(eh, null);
280 bb.addExceptionHandler_first(ehs);
281 int start_id = bb.id;
282 while (bb.getStart() < ex.getEndPC()) {
283 eh.handledBlocks[bb.id - start_id] = bb;
284 ehs = bb.addExceptionHandler(ehs);
285 bb = cfg.basic_blocks[bb.id+1];
286 }
287 }
288
289 if (pass.nJsrs > 0) {
290
291 LiveRefAnalysis lra = new LiveRefAnalysis(method);
292 lra.compute(cfg);
293 }
294 return cfg;
295 }
296
297 /*** Visitor to perform the initial pass over the bytecode. */
298 public static class InitialPass extends BytecodeVisitor {
299
300 private BitString basic_block_start;
301 private BitString branch_locations;
302 private int nJsrs, nRets, nExits;
303
304 InitialPass(jq_Method method) {
305 super(method);
306 this.basic_block_start = new BitString(bcs.length+1);
307 this.branch_locations = new BitString(bcs.length);
308 this.basic_block_start.set(0);
309
310 }
311
312 public String toString() {
313 return "CFG1/"+method.getName();
314 }
315
316 public BitString getBasicBlockStart() {
317 return this.basic_block_start;
318 }
319 public BitString getBranchLocations() {
320 return this.branch_locations;
321 }
322 public int getNumberOfExits() { return nExits; }
323
324 private void addBranch(int target) {
325 basic_block_start.set(target);
326 endBB();
327 }
328 private void endBB() {
329 branch_locations.set(i_start);
330 basic_block_start.set(i_end+1);
331 }
332
333 public void visitJSR(int target) {
334 super.visitJSR(target);
335 ++nJsrs; addBranch(target);
336 }
337 public void visitGOTO(int target) {
338 super.visitGOTO(target);
339 addBranch(target);
340 }
341 public void visitIRETURN() {
342 super.visitIRETURN();
343 ++nExits;
344 endBB();
345 }
346 public void visitLRETURN() {
347 super.visitLRETURN();
348 ++nExits;
349 endBB();
350 }
351 public void visitFRETURN() {
352 super.visitFRETURN();
353 ++nExits;
354 endBB();
355 }
356 public void visitDRETURN() {
357 super.visitDRETURN();
358 ++nExits;
359 endBB();
360 }
361 public void visitARETURN() {
362 super.visitARETURN();
363 ++nExits;
364 endBB();
365 }
366 public void visitVRETURN() {
367 super.visitVRETURN();
368 ++nExits;
369 endBB();
370 }
371 public void visitATHROW() {
372 super.visitATHROW();
373 ++nExits;
374 endBB();
375 }
376 public void visitRET(int i) {
377 super.visitRET(i);
378 ++nRets;
379 endBB();
380 }
381 public void visitIF(byte op, int target) {
382 super.visitIF(op, target);
383 addBranch(target);
384 }
385 public void visitIFREF(byte op, int target) {
386 super.visitIFREF(op, target);
387 addBranch(target);
388 }
389 public void visitIFCMP(byte op, int target) {
390 super.visitIFCMP(op, target);
391 addBranch(target);
392 }
393 public void visitIFREFCMP(byte op, int target) {
394 super.visitIFREFCMP(op, target);
395 addBranch(target);
396 }
397 public void visitTABLESWITCH(int default_target, int low, int high, int[] targets) {
398 super.visitTABLESWITCH(default_target, low, high, targets);
399 for (int i=0; i<targets.length; ++i) {
400 basic_block_start.set(targets[i]);
401 }
402 addBranch(default_target);
403 }
404 public void visitLOOKUPSWITCH(int default_target, int[] values, int[] targets) {
405 super.visitLOOKUPSWITCH(default_target, values, targets);
406 for (int i=0; i<targets.length; ++i) {
407 basic_block_start.set(targets[i]);
408 }
409 addBranch(default_target);
410 }
411 }
412
413 /*** Visitor to link up each of the branches in the code. */
414 static class BranchVisitor extends BytecodeVisitor {
415
416 private final ControlFlowGraph cfg;
417 private final int[] n_pred;
418 BasicBlock bb;
419
420 BranchVisitor(jq_Method m, ControlFlowGraph cfg, int[] n_pred) {
421 super(m);
422 this.cfg = cfg; this.n_pred = n_pred;
423
424 }
425
426 void setLocation(int index) {
427 i_start = index; i_end = index-1;
428 }
429
430 public void visitJSR(int target) {
431 super.visitJSR(target);
432 BasicBlock target_bb = cfg.getBasicBlockByBytecodeIndex(target);
433 ++n_pred[target_bb.id];
434 bb.successors = new BasicBlock[1];
435 bb.successors[0] = target_bb;
436 }
437 public void visitRET(int i) {
438 super.visitRET(i);
439
440 bb.successors = new BasicBlock[0];
441 }
442 public void visitGOTO(int target) {
443 super.visitGOTO(target);
444 BasicBlock target_bb = cfg.getBasicBlockByBytecodeIndex(target);
445 ++n_pred[target_bb.id];
446 bb.successors = new BasicBlock[1];
447 bb.successors[0] = target_bb;
448 }
449 private void RETURNhelper() {
450 BasicBlock target_bb = cfg.basic_blocks[1];
451 ++n_pred[target_bb.id];
452 bb.successors = new BasicBlock[1];
453 bb.successors[0] = target_bb;
454 }
455 public void visitIRETURN() {
456 super.visitIRETURN();
457 RETURNhelper();
458 }
459 public void visitLRETURN() {
460 super.visitLRETURN();
461 RETURNhelper();
462 }
463 public void visitFRETURN() {
464 super.visitFRETURN();
465 RETURNhelper();
466 }
467 public void visitDRETURN() {
468 super.visitDRETURN();
469 RETURNhelper();
470 }
471 public void visitARETURN() {
472 super.visitARETURN();
473 RETURNhelper();
474 }
475 public void visitVRETURN() {
476 super.visitVRETURN();
477 RETURNhelper();
478 }
479 public void visitATHROW() {
480 super.visitATHROW();
481 RETURNhelper();
482 }
483 private void CONDBRANCHhelper(int target) {
484 int bb_i = bb.id;
485 BasicBlock next_bb = cfg.basic_blocks[bb_i+1];
486 ++n_pred[next_bb.id];
487 BasicBlock target_bb = cfg.getBasicBlockByBytecodeIndex(target);
488 ++n_pred[target_bb.id];
489 bb.successors = new BasicBlock[2];
490 bb.successors[0] = next_bb;
491 bb.successors[1] = target_bb;
492 }
493 public void visitIF(byte op, int target) {
494 super.visitIF(op, target);
495 CONDBRANCHhelper(target);
496 }
497 public void visitIFREF(byte op, int target) {
498 super.visitIFREF(op, target);
499 CONDBRANCHhelper(target);
500 }
501 public void visitIFCMP(byte op, int target) {
502 super.visitIFCMP(op, target);
503 CONDBRANCHhelper(target);
504 }
505 public void visitIFREFCMP(byte op, int target) {
506 super.visitIFREFCMP(op, target);
507 CONDBRANCHhelper(target);
508 }
509 public void visitTABLESWITCH(int default_target, int low, int high, int[] targets) {
510 super.visitTABLESWITCH(default_target, low, high, targets);
511 BasicBlock target_bb = cfg.getBasicBlockByBytecodeIndex(default_target);
512 ++n_pred[target_bb.id];
513 bb.successors = new BasicBlock[targets.length+1];
514 bb.successors[0] = target_bb;
515 for (int i=0; i<targets.length; ++i) {
516 target_bb = cfg.getBasicBlockByBytecodeIndex(targets[i]);
517 ++n_pred[target_bb.id];
518 bb.successors[i+1] = target_bb;
519 }
520 }
521 public void visitLOOKUPSWITCH(int default_target, int[] values, int[] targets) {
522 super.visitLOOKUPSWITCH(default_target, values, targets);
523 BasicBlock target_bb = cfg.getBasicBlockByBytecodeIndex(default_target);
524 ++n_pred[target_bb.id];
525 bb.successors = new BasicBlock[targets.length+1];
526 bb.successors[0] = target_bb;
527 for (int i=0; i<targets.length; ++i) {
528 target_bb = cfg.getBasicBlockByBytecodeIndex(targets[i]);
529 ++n_pred[target_bb.id];
530 bb.successors[i+1] = target_bb;
531 }
532 }
533 }
534
535 }