1 /* 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 3 * 4 * This code is free software; you can redistribute it and/or modify it 5 * under the terms of the GNU General Public License version 2 only, as 6 * published by the Free Software Foundation. Oracle designates this 7 * particular file as subject to the "Classpath" exception as provided 8 * by Oracle in the LICENSE file that accompanied this code. 9 * 10 * This code is distributed in the hope that it will be useful, but WITHOUT 11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 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 54 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 55 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 56 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 57 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 58 * THE POSSIBILITY OF SUCH DAMAGE. 59 */ 60 package jdk.internal.org.objectweb.asm.tree.analysis; 61 62 import java.util.ArrayList; 63 import java.util.HashMap; 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 161 // computes the subroutine for each instruction: 162 Subroutine main = new Subroutine(null, m.maxLocals, null); 163 List<AbstractInsnNode> subroutineCalls = new ArrayList<AbstractInsnNode>(); 164 Map<LabelNode, Subroutine> subroutineHeads = new HashMap<LabelNode, Subroutine>(); 165 findSubroutine(0, main, subroutineCalls); 166 while (!subroutineCalls.isEmpty()) { 167 JumpInsnNode jsr = (JumpInsnNode) subroutineCalls.remove(0); 168 Subroutine sub = subroutineHeads.get(jsr.label); 169 if (sub == null) { 170 sub = new Subroutine(jsr.label, m.maxLocals, jsr); 171 subroutineHeads.put(jsr.label, sub); 172 findSubroutine(insns.indexOf(jsr.label), sub, subroutineCalls); 173 } else { 174 sub.callers.add(jsr); 175 } 176 } 177 for (int i = 0; i < n; ++i) { 178 if (subroutines[i] != null && subroutines[i].start == null) { 179 subroutines[i] = null; 180 } 181 } 182 183 // initializes the data structures for the control flow analysis 184 Frame<V> current = newFrame(m.maxLocals, m.maxStack); 185 Frame<V> handler = newFrame(m.maxLocals, m.maxStack); 186 current.setReturn(interpreter.newValue(Type.getReturnType(m.desc))); 187 Type[] args = Type.getArgumentTypes(m.desc); 188 int local = 0; 189 if ((m.access & ACC_STATIC) == 0) { 190 Type ctype = Type.getObjectType(owner); 191 current.setLocal(local++, interpreter.newValue(ctype)); 192 } 193 for (int i = 0; i < args.length; ++i) { 194 current.setLocal(local++, interpreter.newValue(args[i])); 195 if (args[i].getSize() == 2) { 196 current.setLocal(local++, interpreter.newValue(null)); 197 } 198 } 199 while (local < m.maxLocals) { 200 current.setLocal(local++, interpreter.newValue(null)); 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) { 362 LabelNode l = tsnode.labels.get(i); 363 findSubroutine(insns.indexOf(l), sub, calls); 364 } 365 } else if (node instanceof LookupSwitchInsnNode) { 366 LookupSwitchInsnNode lsnode = (LookupSwitchInsnNode) node; 367 findSubroutine(insns.indexOf(lsnode.dflt), sub, calls); 368 for (int i = lsnode.labels.size() - 1; i >= 0; --i) { 369 LabelNode l = lsnode.labels.get(i); 370 findSubroutine(insns.indexOf(l), sub, calls); 371 } 372 } 373 374 // calls findSubroutine recursively on exception handler successors 375 List<TryCatchBlockNode> insnHandlers = handlers[insn]; 376 if (insnHandlers != null) { 377 for (int i = 0; i < insnHandlers.size(); ++i) { 378 TryCatchBlockNode tcb = insnHandlers.get(i); 379 findSubroutine(insns.indexOf(tcb.handler), sub, calls); 380 } 381 } 382 383 // if insn does not falls through to the next instruction, return. 384 switch (node.getOpcode()) { 385 case GOTO: 386 case RET: 387 case TABLESWITCH: 388 case LOOKUPSWITCH: 389 case IRETURN: 390 case LRETURN: 391 case FRETURN: 392 case DRETURN: 393 case ARETURN: 394 case RETURN: 395 case ATHROW: 396 return; 397 } 398 insn++; 399 } 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 } 578 } 579 }