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 * 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 53 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 54 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 55 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 56 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 57 * THE POSSIBILITY OF SUCH DAMAGE. 58 */ 59 package jdk.internal.org.objectweb.asm.tree.analysis; 60 61 import java.util.ArrayList; 62 import java.util.HashMap; 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 164 // computes the subroutine for each instruction: 165 Subroutine main = new Subroutine(null, m.maxLocals, null); 166 List<AbstractInsnNode> subroutineCalls = new ArrayList<AbstractInsnNode>(); 167 Map<LabelNode, Subroutine> subroutineHeads = new HashMap<LabelNode, Subroutine>(); 168 findSubroutine(0, main, subroutineCalls); 169 while (!subroutineCalls.isEmpty()) { 170 JumpInsnNode jsr = (JumpInsnNode) subroutineCalls.remove(0); 171 Subroutine sub = subroutineHeads.get(jsr.label); 172 if (sub == null) { 173 sub = new Subroutine(jsr.label, m.maxLocals, jsr); 174 subroutineHeads.put(jsr.label, sub); 175 findSubroutine(insns.indexOf(jsr.label), sub, subroutineCalls); 176 } else { 177 sub.callers.add(jsr); 178 } 179 } 180 for (int i = 0; i < n; ++i) { 181 if (subroutines[i] != null && subroutines[i].start == null) { 182 subroutines[i] = null; 183 } 184 } 185 186 // initializes the data structures for the control flow analysis 187 Frame<V> current = newFrame(m.maxLocals, m.maxStack); 188 Frame<V> handler = newFrame(m.maxLocals, m.maxStack); 189 current.setReturn(interpreter.newValue(Type.getReturnType(m.desc))); 190 Type[] args = Type.getArgumentTypes(m.desc); 191 int local = 0; 192 if ((m.access & ACC_STATIC) == 0) { 193 Type ctype = Type.getObjectType(owner); 194 current.setLocal(local++, interpreter.newValue(ctype)); 195 } 196 for (int i = 0; i < args.length; ++i) { 197 current.setLocal(local++, interpreter.newValue(args[i])); 198 if (args[i].getSize() == 2) { 199 current.setLocal(local++, interpreter.newValue(null)); 200 } 201 } 202 while (local < m.maxLocals) { 203 current.setLocal(local++, interpreter.newValue(null)); 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) { 359 LabelNode l = tsnode.labels.get(i); 360 findSubroutine(insns.indexOf(l), sub, calls); 361 } 362 } else if (node instanceof LookupSwitchInsnNode) { 363 LookupSwitchInsnNode lsnode = (LookupSwitchInsnNode) node; 364 findSubroutine(insns.indexOf(lsnode.dflt), sub, calls); 365 for (int i = lsnode.labels.size() - 1; i >= 0; --i) { 366 LabelNode l = lsnode.labels.get(i); 367 findSubroutine(insns.indexOf(l), sub, calls); 368 } 369 } 370 371 // calls findSubroutine recursively on exception handler successors 372 List<TryCatchBlockNode> insnHandlers = handlers[insn]; 373 if (insnHandlers != null) { 374 for (int i = 0; i < insnHandlers.size(); ++i) { 375 TryCatchBlockNode tcb = insnHandlers.get(i); 376 findSubroutine(insns.indexOf(tcb.handler), sub, calls); 377 } 378 } 379 380 // if insn does not falls through to the next instruction, return. 381 switch (node.getOpcode()) { 382 case GOTO: 383 case RET: 384 case TABLESWITCH: 385 case LOOKUPSWITCH: 386 case IRETURN: 387 case LRETURN: 388 case FRETURN: 389 case DRETURN: 390 case ARETURN: 391 case RETURN: 392 case ATHROW: 393 return; 394 } 395 insn++; 396 } 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 } 577 } 578 }