13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *
20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 * or visit www.oracle.com if you need additional information or have any
22 * questions.
23 */
24
25 /*
26 * This file is available under and governed by the GNU General Public
27 * License version 2 only, as published by the Free Software Foundation.
28 * However, the following notice accompanied the original version of this
29 * file:
30 *
31 * ASM: a very small and fast Java bytecode manipulation framework
32 * Copyright (c) 2000-2011 INRIA, France Telecom
33 * Copyright (c) 2011 Google
34 * All rights reserved.
35 *
36 * Redistribution and use in source and binary forms, with or without
37 * modification, are permitted provided that the following conditions
38 * are met:
39 * 1. Redistributions of source code must retain the above copyright
40 * notice, this list of conditions and the following disclaimer.
41 * 2. Redistributions in binary form must reproduce the above copyright
42 * notice, this list of conditions and the following disclaimer in the
43 * documentation and/or other materials provided with the distribution.
44 * 3. Neither the name of the copyright holders nor the names of its
45 * contributors may be used to endorse or promote products derived from
46 * this software without specific prior written permission.
47 *
48 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
49 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
50 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
51 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
52 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
53 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
64 import java.util.List;
65 import java.util.Map;
66
67 import jdk.internal.org.objectweb.asm.Opcodes;
68 import jdk.internal.org.objectweb.asm.Type;
69 import jdk.internal.org.objectweb.asm.tree.AbstractInsnNode;
70 import jdk.internal.org.objectweb.asm.tree.IincInsnNode;
71 import jdk.internal.org.objectweb.asm.tree.InsnList;
72 import jdk.internal.org.objectweb.asm.tree.JumpInsnNode;
73 import jdk.internal.org.objectweb.asm.tree.LabelNode;
74 import jdk.internal.org.objectweb.asm.tree.LookupSwitchInsnNode;
75 import jdk.internal.org.objectweb.asm.tree.MethodNode;
76 import jdk.internal.org.objectweb.asm.tree.TableSwitchInsnNode;
77 import jdk.internal.org.objectweb.asm.tree.TryCatchBlockNode;
78 import jdk.internal.org.objectweb.asm.tree.VarInsnNode;
79
80 /**
81 * A semantic bytecode analyzer. <i>This class does not fully check that JSR and
82 * RET instructions are valid.</i>
83 *
84 * @param <V> type of the Value used for the analysis.
85 *
86 * @author Eric Bruneton
87 */
88 public class Analyzer<V extends Value> implements Opcodes {
89
90 private final Interpreter<V> interpreter;
91
92 private int n;
93
94 private InsnList insns;
95
96 private List<TryCatchBlockNode>[] handlers;
97
98 private Frame<V>[] frames;
99
100 private Subroutine[] subroutines;
101
102 private boolean[] queued;
103
104 private int[] queue;
105
106 private int top;
107
108 /**
109 * Constructs a new {@link Analyzer}.
110 *
111 * @param interpreter the interpreter to be used to symbolically interpret
112 * the bytecode instructions.
113 */
114 public Analyzer(final Interpreter<V> interpreter) {
115 this.interpreter = interpreter;
116 }
117
118 /**
119 * Analyzes the given method.
120 *
121 * @param owner the internal name of the class to which the method belongs.
122 * @param m the method to be analyzed.
123 * @return the symbolic state of the execution stack frame at each bytecode
124 * instruction of the method. The size of the returned array is
125 * equal to the number of instructions (and labels) of the method. A
126 * given frame is <tt>null</tt> if and only if the corresponding
127 * instruction cannot be reached (dead code).
128 * @throws AnalyzerException if a problem occurs during the analysis.
129 */
130 public Frame<V>[] analyze(final String owner, final MethodNode m)
131 throws AnalyzerException
132 {
133 if ((m.access & (ACC_ABSTRACT | ACC_NATIVE)) != 0) {
134 frames = (Frame<V>[])new Frame<?>[0];
135 return frames;
136 }
137 n = m.instructions.size();
138 insns = m.instructions;
139 handlers = (List<TryCatchBlockNode>[])new List<?>[n];
140 frames = (Frame<V>[])new Frame<?>[n];
141 subroutines = new Subroutine[n];
142 queued = new boolean[n];
143 queue = new int[n];
144 top = 0;
145
146 // computes exception handlers for each instruction
147 for (int i = 0; i < m.tryCatchBlocks.size(); ++i) {
148 TryCatchBlockNode tcb = m.tryCatchBlocks.get(i);
149 int begin = insns.indexOf(tcb.start);
150 int end = insns.indexOf(tcb.end);
151 for (int j = begin; j < end; ++j) {
152 List<TryCatchBlockNode> insnHandlers = handlers[j];
153 if (insnHandlers == null) {
154 insnHandlers = new ArrayList<TryCatchBlockNode>();
155 handlers[j] = insnHandlers;
156 }
157 insnHandlers.add(tcb);
158 }
159 }
160
201 }
202 merge(0, current, null);
203
204 init(owner, m);
205
206 // control flow analysis
207 while (top > 0) {
208 int insn = queue[--top];
209 Frame<V> f = frames[insn];
210 Subroutine subroutine = subroutines[insn];
211 queued[insn] = false;
212
213 AbstractInsnNode insnNode = null;
214 try {
215 insnNode = m.instructions.get(insn);
216 int insnOpcode = insnNode.getOpcode();
217 int insnType = insnNode.getType();
218
219 if (insnType == AbstractInsnNode.LABEL
220 || insnType == AbstractInsnNode.LINE
221 || insnType == AbstractInsnNode.FRAME)
222 {
223 merge(insn + 1, f, subroutine);
224 newControlFlowEdge(insn, insn + 1);
225 } else {
226 current.init(f).execute(insnNode, interpreter);
227 subroutine = subroutine == null ? null : subroutine.copy();
228
229 if (insnNode instanceof JumpInsnNode) {
230 JumpInsnNode j = (JumpInsnNode) insnNode;
231 if (insnOpcode != GOTO && insnOpcode != JSR) {
232 merge(insn + 1, current, subroutine);
233 newControlFlowEdge(insn, insn + 1);
234 }
235 int jump = insns.indexOf(j.label);
236 if (insnOpcode == JSR) {
237 merge(jump, current, new Subroutine(j.label,
238 m.maxLocals,
239 j));
240 } else {
241 merge(jump, current, subroutine);
242 }
243 newControlFlowEdge(insn, jump);
244 } else if (insnNode instanceof LookupSwitchInsnNode) {
245 LookupSwitchInsnNode lsi = (LookupSwitchInsnNode) insnNode;
246 int jump = insns.indexOf(lsi.dflt);
247 merge(jump, current, subroutine);
248 newControlFlowEdge(insn, jump);
249 for (int j = 0; j < lsi.labels.size(); ++j) {
250 LabelNode label = lsi.labels.get(j);
251 jump = insns.indexOf(label);
252 merge(jump, current, subroutine);
253 newControlFlowEdge(insn, jump);
254 }
255 } else if (insnNode instanceof TableSwitchInsnNode) {
256 TableSwitchInsnNode tsi = (TableSwitchInsnNode) insnNode;
257 int jump = insns.indexOf(tsi.dflt);
258 merge(jump, current, subroutine);
259 newControlFlowEdge(insn, jump);
260 for (int j = 0; j < tsi.labels.size(); ++j) {
261 LabelNode label = tsi.labels.get(j);
262 jump = insns.indexOf(label);
263 merge(jump, current, subroutine);
264 newControlFlowEdge(insn, jump);
265 }
266 } else if (insnOpcode == RET) {
267 if (subroutine == null) {
268 throw new AnalyzerException(insnNode, "RET instruction outside of a sub routine");
269 }
270 for (int i = 0; i < subroutine.callers.size(); ++i) {
271 JumpInsnNode caller = subroutine.callers.get(i);
272 int call = insns.indexOf(caller);
273 if (frames[call] != null) {
274 merge(call + 1,
275 frames[call],
276 current,
277 subroutines[call],
278 subroutine.access);
279 newControlFlowEdge(insn, call + 1);
280 }
281 }
282 } else if (insnOpcode != ATHROW
283 && (insnOpcode < IRETURN || insnOpcode > RETURN))
284 {
285 if (subroutine != null) {
286 if (insnNode instanceof VarInsnNode) {
287 int var = ((VarInsnNode) insnNode).var;
288 subroutine.access[var] = true;
289 if (insnOpcode == LLOAD || insnOpcode == DLOAD
290 || insnOpcode == LSTORE
291 || insnOpcode == DSTORE)
292 {
293 subroutine.access[var + 1] = true;
294 }
295 } else if (insnNode instanceof IincInsnNode) {
296 int var = ((IincInsnNode) insnNode).var;
297 subroutine.access[var] = true;
298 }
299 }
300 merge(insn + 1, current, subroutine);
301 newControlFlowEdge(insn, insn + 1);
302 }
303 }
304
305 List<TryCatchBlockNode> insnHandlers = handlers[insn];
306 if (insnHandlers != null) {
307 for (int i = 0; i < insnHandlers.size(); ++i) {
308 TryCatchBlockNode tcb = insnHandlers.get(i);
309 Type type;
310 if (tcb.type == null) {
311 type = Type.getObjectType("java/lang/Throwable");
312 } else {
313 type = Type.getObjectType(tcb.type);
314 }
315 int jump = insns.indexOf(tcb.handler);
316 if (newControlFlowExceptionEdge(insn, tcb)) {
317 handler.init(f);
318 handler.clearStack();
319 handler.push(interpreter.newValue(type));
320 merge(jump, handler, subroutine);
321 }
322 }
323 }
324 } catch (AnalyzerException e) {
325 throw new AnalyzerException(e.node, "Error at instruction " + insn
326 + ": " + e.getMessage(), e);
327 } catch (Exception e) {
328 throw new AnalyzerException(insnNode, "Error at instruction " + insn
329 + ": " + e.getMessage(), e);
330 }
331 }
332
333 return frames;
334 }
335
336 private void findSubroutine(int insn, final Subroutine sub, final List<AbstractInsnNode> calls)
337 throws AnalyzerException
338 {
339 while (true) {
340 if (insn < 0 || insn >= n) {
341 throw new AnalyzerException(null, "Execution can fall off end of the code");
342 }
343 if (subroutines[insn] != null) {
344 return;
345 }
346 subroutines[insn] = sub.copy();
347 AbstractInsnNode node = insns.get(insn);
348
349 // calls findSubroutine recursively on normal successors
350 if (node instanceof JumpInsnNode) {
351 if (node.getOpcode() == JSR) {
352 // do not follow a JSR, it leads to another subroutine!
353 calls.add(node);
354 } else {
355 JumpInsnNode jnode = (JumpInsnNode) node;
356 findSubroutine(insns.indexOf(jnode.label), sub, calls);
357 }
358 } else if (node instanceof TableSwitchInsnNode) {
359 TableSwitchInsnNode tsnode = (TableSwitchInsnNode) node;
360 findSubroutine(insns.indexOf(tsnode.dflt), sub, calls);
361 for (int i = tsnode.labels.size() - 1; i >= 0; --i) {
400 }
401
402 /**
403 * Returns the symbolic stack frame for each instruction of the last
404 * recently analyzed method.
405 *
406 * @return the symbolic state of the execution stack frame at each bytecode
407 * instruction of the method. The size of the returned array is
408 * equal to the number of instructions (and labels) of the method. A
409 * given frame is <tt>null</tt> if the corresponding instruction
410 * cannot be reached, or if an error occured during the analysis of
411 * the method.
412 */
413 public Frame<V>[] getFrames() {
414 return frames;
415 }
416
417 /**
418 * Returns the exception handlers for the given instruction.
419 *
420 * @param insn the index of an instruction of the last recently analyzed
421 * method.
422 * @return a list of {@link TryCatchBlockNode} objects.
423 */
424 public List<TryCatchBlockNode> getHandlers(final int insn) {
425 return handlers[insn];
426 }
427
428 /**
429 * Initializes this analyzer. This method is called just before the
430 * execution of control flow analysis loop in #analyze. The default
431 * implementation of this method does nothing.
432 *
433 * @param owner the internal name of the class to which the method belongs.
434 * @param m the method to be analyzed.
435 * @throws AnalyzerException if a problem occurs.
436 */
437 protected void init(String owner, MethodNode m) throws AnalyzerException {
438 }
439
440 /**
441 * Constructs a new frame with the given size.
442 *
443 * @param nLocals the maximum number of local variables of the frame.
444 * @param nStack the maximum stack size of the frame.
445 * @return the created frame.
446 */
447 protected Frame<V> newFrame(final int nLocals, final int nStack) {
448 return new Frame<V>(nLocals, nStack);
449 }
450
451 /**
452 * Constructs a new frame that is identical to the given frame.
453 *
454 * @param src a frame.
455 * @return the created frame.
456 */
457 protected Frame<V> newFrame(final Frame<? extends V> src) {
458 return new Frame<V>(src);
459 }
460
461 /**
462 * Creates a control flow graph edge. The default implementation of this
463 * method does nothing. It can be overriden in order to construct the
464 * control flow graph of a method (this method is called by the
465 * {@link #analyze analyze} method during its visit of the method's code).
466 *
467 * @param insn an instruction index.
468 * @param successor index of a successor instruction.
469 */
470 protected void newControlFlowEdge(final int insn, final int successor) {
471 }
472
473 /**
474 * Creates a control flow graph edge corresponding to an exception handler.
475 * The default implementation of this method does nothing. It can be
476 * overridden in order to construct the control flow graph of a method (this
477 * method is called by the {@link #analyze analyze} method during its visit
478 * of the method's code).
479 *
480 * @param insn an instruction index.
481 * @param successor index of a successor instruction.
482 * @return true if this edge must be considered in the data flow analysis
483 * performed by this analyzer, or false otherwise. The default
484 * implementation of this method always returns true.
485 */
486 protected boolean newControlFlowExceptionEdge(
487 final int insn,
488 final int successor)
489 {
490 return true;
491 }
492
493 /**
494 * Creates a control flow graph edge corresponding to an exception handler.
495 * The default implementation of this method delegates to
496 * {@link #newControlFlowExceptionEdge(int, int)
497 * newControlFlowExceptionEdge(int, int)}. It can be overridden in order to
498 * construct the control flow graph of a method (this method is called by
499 * the {@link #analyze analyze} method during its visit of the method's
500 * code).
501 *
502 * @param insn an instruction index.
503 * @param tcb TryCatchBlockNode corresponding to this edge.
504 * @return true if this edge must be considered in the data flow analysis
505 * performed by this analyzer, or false otherwise. The default
506 * implementation of this method delegates to
507 * {@link #newControlFlowExceptionEdge(int, int)
508 * newControlFlowExceptionEdge(int, int)}.
509 */
510 protected boolean newControlFlowExceptionEdge(
511 final int insn,
512 final TryCatchBlockNode tcb)
513 {
514 return newControlFlowExceptionEdge(insn, insns.indexOf(tcb.handler));
515 }
516
517 // -------------------------------------------------------------------------
518
519 private void merge(
520 final int insn,
521 final Frame<V> frame,
522 final Subroutine subroutine) throws AnalyzerException
523 {
524 Frame<V> oldFrame = frames[insn];
525 Subroutine oldSubroutine = subroutines[insn];
526 boolean changes;
527
528 if (oldFrame == null) {
529 frames[insn] = newFrame(frame);
530 changes = true;
531 } else {
532 changes = oldFrame.merge(frame, interpreter);
533 }
534
535 if (oldSubroutine == null) {
536 if (subroutine != null) {
537 subroutines[insn] = subroutine.copy();
538 changes = true;
539 }
540 } else {
541 if (subroutine != null) {
542 changes |= oldSubroutine.merge(subroutine);
543 }
544 }
545 if (changes && !queued[insn]) {
546 queued[insn] = true;
547 queue[top++] = insn;
548 }
549 }
550
551 private void merge(
552 final int insn,
553 final Frame<V> beforeJSR,
554 final Frame<V> afterRET,
555 final Subroutine subroutineBeforeJSR,
556 final boolean[] access) throws AnalyzerException
557 {
558 Frame<V> oldFrame = frames[insn];
559 Subroutine oldSubroutine = subroutines[insn];
560 boolean changes;
561
562 afterRET.merge(beforeJSR, access);
563
564 if (oldFrame == null) {
565 frames[insn] = newFrame(afterRET);
566 changes = true;
567 } else {
568 changes = oldFrame.merge(afterRET, interpreter);
569 }
570
571 if (oldSubroutine != null && subroutineBeforeJSR != null) {
572 changes |= oldSubroutine.merge(subroutineBeforeJSR);
573 }
574 if (changes && !queued[insn]) {
575 queued[insn] = true;
576 queue[top++] = insn;
577 }
|
13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *
20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 * or visit www.oracle.com if you need additional information or have any
22 * questions.
23 */
24
25 /*
26 * This file is available under and governed by the GNU General Public
27 * License version 2 only, as published by the Free Software Foundation.
28 * However, the following notice accompanied the original version of this
29 * file:
30 *
31 * ASM: a very small and fast Java bytecode manipulation framework
32 * Copyright (c) 2000-2011 INRIA, France Telecom
33 * All rights reserved.
34 *
35 * Redistribution and use in source and binary forms, with or without
36 * modification, are permitted provided that the following conditions
37 * are met:
38 * 1. Redistributions of source code must retain the above copyright
39 * notice, this list of conditions and the following disclaimer.
40 * 2. Redistributions in binary form must reproduce the above copyright
41 * notice, this list of conditions and the following disclaimer in the
42 * documentation and/or other materials provided with the distribution.
43 * 3. Neither the name of the copyright holders nor the names of its
44 * contributors may be used to endorse or promote products derived from
45 * this software without specific prior written permission.
46 *
47 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
48 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
49 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
50 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
51 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
52 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
63 import java.util.List;
64 import java.util.Map;
65
66 import jdk.internal.org.objectweb.asm.Opcodes;
67 import jdk.internal.org.objectweb.asm.Type;
68 import jdk.internal.org.objectweb.asm.tree.AbstractInsnNode;
69 import jdk.internal.org.objectweb.asm.tree.IincInsnNode;
70 import jdk.internal.org.objectweb.asm.tree.InsnList;
71 import jdk.internal.org.objectweb.asm.tree.JumpInsnNode;
72 import jdk.internal.org.objectweb.asm.tree.LabelNode;
73 import jdk.internal.org.objectweb.asm.tree.LookupSwitchInsnNode;
74 import jdk.internal.org.objectweb.asm.tree.MethodNode;
75 import jdk.internal.org.objectweb.asm.tree.TableSwitchInsnNode;
76 import jdk.internal.org.objectweb.asm.tree.TryCatchBlockNode;
77 import jdk.internal.org.objectweb.asm.tree.VarInsnNode;
78
79 /**
80 * A semantic bytecode analyzer. <i>This class does not fully check that JSR and
81 * RET instructions are valid.</i>
82 *
83 * @param <V>
84 * type of the Value used for the analysis.
85 *
86 * @author Eric Bruneton
87 */
88 public class Analyzer<V extends Value> implements Opcodes {
89
90 private final Interpreter<V> interpreter;
91
92 private int n;
93
94 private InsnList insns;
95
96 private List<TryCatchBlockNode>[] handlers;
97
98 private Frame<V>[] frames;
99
100 private Subroutine[] subroutines;
101
102 private boolean[] queued;
103
104 private int[] queue;
105
106 private int top;
107
108 /**
109 * Constructs a new {@link Analyzer}.
110 *
111 * @param interpreter
112 * the interpreter to be used to symbolically interpret the
113 * bytecode instructions.
114 */
115 public Analyzer(final Interpreter<V> interpreter) {
116 this.interpreter = interpreter;
117 }
118
119 /**
120 * Analyzes the given method.
121 *
122 * @param owner
123 * the internal name of the class to which the method belongs.
124 * @param m
125 * the method to be analyzed.
126 * @return the symbolic state of the execution stack frame at each bytecode
127 * instruction of the method. The size of the returned array is
128 * equal to the number of instructions (and labels) of the method. A
129 * given frame is <tt>null</tt> if and only if the corresponding
130 * instruction cannot be reached (dead code).
131 * @throws AnalyzerException
132 * if a problem occurs during the analysis.
133 */
134 public Frame<V>[] analyze(final String owner, final MethodNode m)
135 throws AnalyzerException {
136 if ((m.access & (ACC_ABSTRACT | ACC_NATIVE)) != 0) {
137 frames = (Frame<V>[]) new Frame<?>[0];
138 return frames;
139 }
140 n = m.instructions.size();
141 insns = m.instructions;
142 handlers = (List<TryCatchBlockNode>[]) new List<?>[n];
143 frames = (Frame<V>[]) new Frame<?>[n];
144 subroutines = new Subroutine[n];
145 queued = new boolean[n];
146 queue = new int[n];
147 top = 0;
148
149 // computes exception handlers for each instruction
150 for (int i = 0; i < m.tryCatchBlocks.size(); ++i) {
151 TryCatchBlockNode tcb = m.tryCatchBlocks.get(i);
152 int begin = insns.indexOf(tcb.start);
153 int end = insns.indexOf(tcb.end);
154 for (int j = begin; j < end; ++j) {
155 List<TryCatchBlockNode> insnHandlers = handlers[j];
156 if (insnHandlers == null) {
157 insnHandlers = new ArrayList<TryCatchBlockNode>();
158 handlers[j] = insnHandlers;
159 }
160 insnHandlers.add(tcb);
161 }
162 }
163
204 }
205 merge(0, current, null);
206
207 init(owner, m);
208
209 // control flow analysis
210 while (top > 0) {
211 int insn = queue[--top];
212 Frame<V> f = frames[insn];
213 Subroutine subroutine = subroutines[insn];
214 queued[insn] = false;
215
216 AbstractInsnNode insnNode = null;
217 try {
218 insnNode = m.instructions.get(insn);
219 int insnOpcode = insnNode.getOpcode();
220 int insnType = insnNode.getType();
221
222 if (insnType == AbstractInsnNode.LABEL
223 || insnType == AbstractInsnNode.LINE
224 || insnType == AbstractInsnNode.FRAME) {
225 merge(insn + 1, f, subroutine);
226 newControlFlowEdge(insn, insn + 1);
227 } else {
228 current.init(f).execute(insnNode, interpreter);
229 subroutine = subroutine == null ? null : subroutine.copy();
230
231 if (insnNode instanceof JumpInsnNode) {
232 JumpInsnNode j = (JumpInsnNode) insnNode;
233 if (insnOpcode != GOTO && insnOpcode != JSR) {
234 merge(insn + 1, current, subroutine);
235 newControlFlowEdge(insn, insn + 1);
236 }
237 int jump = insns.indexOf(j.label);
238 if (insnOpcode == JSR) {
239 merge(jump, current, new Subroutine(j.label,
240 m.maxLocals, j));
241 } else {
242 merge(jump, current, subroutine);
243 }
244 newControlFlowEdge(insn, jump);
245 } else if (insnNode instanceof LookupSwitchInsnNode) {
246 LookupSwitchInsnNode lsi = (LookupSwitchInsnNode) insnNode;
247 int jump = insns.indexOf(lsi.dflt);
248 merge(jump, current, subroutine);
249 newControlFlowEdge(insn, jump);
250 for (int j = 0; j < lsi.labels.size(); ++j) {
251 LabelNode label = lsi.labels.get(j);
252 jump = insns.indexOf(label);
253 merge(jump, current, subroutine);
254 newControlFlowEdge(insn, jump);
255 }
256 } else if (insnNode instanceof TableSwitchInsnNode) {
257 TableSwitchInsnNode tsi = (TableSwitchInsnNode) insnNode;
258 int jump = insns.indexOf(tsi.dflt);
259 merge(jump, current, subroutine);
260 newControlFlowEdge(insn, jump);
261 for (int j = 0; j < tsi.labels.size(); ++j) {
262 LabelNode label = tsi.labels.get(j);
263 jump = insns.indexOf(label);
264 merge(jump, current, subroutine);
265 newControlFlowEdge(insn, jump);
266 }
267 } else if (insnOpcode == RET) {
268 if (subroutine == null) {
269 throw new AnalyzerException(insnNode,
270 "RET instruction outside of a sub routine");
271 }
272 for (int i = 0; i < subroutine.callers.size(); ++i) {
273 JumpInsnNode caller = subroutine.callers.get(i);
274 int call = insns.indexOf(caller);
275 if (frames[call] != null) {
276 merge(call + 1, frames[call], current,
277 subroutines[call], subroutine.access);
278 newControlFlowEdge(insn, call + 1);
279 }
280 }
281 } else if (insnOpcode != ATHROW
282 && (insnOpcode < IRETURN || insnOpcode > RETURN)) {
283 if (subroutine != null) {
284 if (insnNode instanceof VarInsnNode) {
285 int var = ((VarInsnNode) insnNode).var;
286 subroutine.access[var] = true;
287 if (insnOpcode == LLOAD || insnOpcode == DLOAD
288 || insnOpcode == LSTORE
289 || insnOpcode == DSTORE) {
290 subroutine.access[var + 1] = true;
291 }
292 } else if (insnNode instanceof IincInsnNode) {
293 int var = ((IincInsnNode) insnNode).var;
294 subroutine.access[var] = true;
295 }
296 }
297 merge(insn + 1, current, subroutine);
298 newControlFlowEdge(insn, insn + 1);
299 }
300 }
301
302 List<TryCatchBlockNode> insnHandlers = handlers[insn];
303 if (insnHandlers != null) {
304 for (int i = 0; i < insnHandlers.size(); ++i) {
305 TryCatchBlockNode tcb = insnHandlers.get(i);
306 Type type;
307 if (tcb.type == null) {
308 type = Type.getObjectType("java/lang/Throwable");
309 } else {
310 type = Type.getObjectType(tcb.type);
311 }
312 int jump = insns.indexOf(tcb.handler);
313 if (newControlFlowExceptionEdge(insn, tcb)) {
314 handler.init(f);
315 handler.clearStack();
316 handler.push(interpreter.newValue(type));
317 merge(jump, handler, subroutine);
318 }
319 }
320 }
321 } catch (AnalyzerException e) {
322 throw new AnalyzerException(e.node, "Error at instruction "
323 + insn + ": " + e.getMessage(), e);
324 } catch (Exception e) {
325 throw new AnalyzerException(insnNode, "Error at instruction "
326 + insn + ": " + e.getMessage(), e);
327 }
328 }
329
330 return frames;
331 }
332
333 private void findSubroutine(int insn, final Subroutine sub,
334 final List<AbstractInsnNode> calls) throws AnalyzerException {
335 while (true) {
336 if (insn < 0 || insn >= n) {
337 throw new AnalyzerException(null,
338 "Execution can fall off end of the code");
339 }
340 if (subroutines[insn] != null) {
341 return;
342 }
343 subroutines[insn] = sub.copy();
344 AbstractInsnNode node = insns.get(insn);
345
346 // calls findSubroutine recursively on normal successors
347 if (node instanceof JumpInsnNode) {
348 if (node.getOpcode() == JSR) {
349 // do not follow a JSR, it leads to another subroutine!
350 calls.add(node);
351 } else {
352 JumpInsnNode jnode = (JumpInsnNode) node;
353 findSubroutine(insns.indexOf(jnode.label), sub, calls);
354 }
355 } else if (node instanceof TableSwitchInsnNode) {
356 TableSwitchInsnNode tsnode = (TableSwitchInsnNode) node;
357 findSubroutine(insns.indexOf(tsnode.dflt), sub, calls);
358 for (int i = tsnode.labels.size() - 1; i >= 0; --i) {
397 }
398
399 /**
400 * Returns the symbolic stack frame for each instruction of the last
401 * recently analyzed method.
402 *
403 * @return the symbolic state of the execution stack frame at each bytecode
404 * instruction of the method. The size of the returned array is
405 * equal to the number of instructions (and labels) of the method. A
406 * given frame is <tt>null</tt> if the corresponding instruction
407 * cannot be reached, or if an error occured during the analysis of
408 * the method.
409 */
410 public Frame<V>[] getFrames() {
411 return frames;
412 }
413
414 /**
415 * Returns the exception handlers for the given instruction.
416 *
417 * @param insn
418 * the index of an instruction of the last recently analyzed
419 * method.
420 * @return a list of {@link TryCatchBlockNode} objects.
421 */
422 public List<TryCatchBlockNode> getHandlers(final int insn) {
423 return handlers[insn];
424 }
425
426 /**
427 * Initializes this analyzer. This method is called just before the
428 * execution of control flow analysis loop in #analyze. The default
429 * implementation of this method does nothing.
430 *
431 * @param owner
432 * the internal name of the class to which the method belongs.
433 * @param m
434 * the method to be analyzed.
435 * @throws AnalyzerException
436 * if a problem occurs.
437 */
438 protected void init(String owner, MethodNode m) throws AnalyzerException {
439 }
440
441 /**
442 * Constructs a new frame with the given size.
443 *
444 * @param nLocals
445 * the maximum number of local variables of the frame.
446 * @param nStack
447 * the maximum stack size of the frame.
448 * @return the created frame.
449 */
450 protected Frame<V> newFrame(final int nLocals, final int nStack) {
451 return new Frame<V>(nLocals, nStack);
452 }
453
454 /**
455 * Constructs a new frame that is identical to the given frame.
456 *
457 * @param src
458 * a frame.
459 * @return the created frame.
460 */
461 protected Frame<V> newFrame(final Frame<? extends V> src) {
462 return new Frame<V>(src);
463 }
464
465 /**
466 * Creates a control flow graph edge. The default implementation of this
467 * method does nothing. It can be overriden in order to construct the
468 * control flow graph of a method (this method is called by the
469 * {@link #analyze analyze} method during its visit of the method's code).
470 *
471 * @param insn
472 * an instruction index.
473 * @param successor
474 * index of a successor instruction.
475 */
476 protected void newControlFlowEdge(final int insn, final int successor) {
477 }
478
479 /**
480 * Creates a control flow graph edge corresponding to an exception handler.
481 * The default implementation of this method does nothing. It can be
482 * overridden in order to construct the control flow graph of a method (this
483 * method is called by the {@link #analyze analyze} method during its visit
484 * of the method's code).
485 *
486 * @param insn
487 * an instruction index.
488 * @param successor
489 * index of a successor instruction.
490 * @return true if this edge must be considered in the data flow analysis
491 * performed by this analyzer, or false otherwise. The default
492 * implementation of this method always returns true.
493 */
494 protected boolean newControlFlowExceptionEdge(final int insn,
495 final int successor) {
496 return true;
497 }
498
499 /**
500 * Creates a control flow graph edge corresponding to an exception handler.
501 * The default implementation of this method delegates to
502 * {@link #newControlFlowExceptionEdge(int, int)
503 * newControlFlowExceptionEdge(int, int)}. It can be overridden in order to
504 * construct the control flow graph of a method (this method is called by
505 * the {@link #analyze analyze} method during its visit of the method's
506 * code).
507 *
508 * @param insn
509 * an instruction index.
510 * @param tcb
511 * TryCatchBlockNode corresponding to this edge.
512 * @return true if this edge must be considered in the data flow analysis
513 * performed by this analyzer, or false otherwise. The default
514 * implementation of this method delegates to
515 * {@link #newControlFlowExceptionEdge(int, int)
516 * newControlFlowExceptionEdge(int, int)}.
517 */
518 protected boolean newControlFlowExceptionEdge(final int insn,
519 final TryCatchBlockNode tcb) {
520 return newControlFlowExceptionEdge(insn, insns.indexOf(tcb.handler));
521 }
522
523 // -------------------------------------------------------------------------
524
525 private void merge(final int insn, final Frame<V> frame,
526 final Subroutine subroutine) throws AnalyzerException {
527 Frame<V> oldFrame = frames[insn];
528 Subroutine oldSubroutine = subroutines[insn];
529 boolean changes;
530
531 if (oldFrame == null) {
532 frames[insn] = newFrame(frame);
533 changes = true;
534 } else {
535 changes = oldFrame.merge(frame, interpreter);
536 }
537
538 if (oldSubroutine == null) {
539 if (subroutine != null) {
540 subroutines[insn] = subroutine.copy();
541 changes = true;
542 }
543 } else {
544 if (subroutine != null) {
545 changes |= oldSubroutine.merge(subroutine);
546 }
547 }
548 if (changes && !queued[insn]) {
549 queued[insn] = true;
550 queue[top++] = insn;
551 }
552 }
553
554 private void merge(final int insn, final Frame<V> beforeJSR,
555 final Frame<V> afterRET, final Subroutine subroutineBeforeJSR,
556 final boolean[] access) throws AnalyzerException {
557 Frame<V> oldFrame = frames[insn];
558 Subroutine oldSubroutine = subroutines[insn];
559 boolean changes;
560
561 afterRET.merge(beforeJSR, access);
562
563 if (oldFrame == null) {
564 frames[insn] = newFrame(afterRET);
565 changes = true;
566 } else {
567 changes = oldFrame.merge(afterRET, interpreter);
568 }
569
570 if (oldSubroutine != null && subroutineBeforeJSR != null) {
571 changes |= oldSubroutine.merge(subroutineBeforeJSR);
572 }
573 if (changes && !queued[insn]) {
574 queued[insn] = true;
575 queue[top++] = insn;
576 }
|