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 */ 59package jdk.internal.org.objectweb.asm.tree.analysis; 60 61import java.util.ArrayList; 62import java.util.HashMap; 63import java.util.List; 64import java.util.Map; 65 66import jdk.internal.org.objectweb.asm.Opcodes; 67import jdk.internal.org.objectweb.asm.Type; 68import jdk.internal.org.objectweb.asm.tree.AbstractInsnNode; 69import jdk.internal.org.objectweb.asm.tree.IincInsnNode; 70import jdk.internal.org.objectweb.asm.tree.InsnList; 71import jdk.internal.org.objectweb.asm.tree.JumpInsnNode; 72import jdk.internal.org.objectweb.asm.tree.LabelNode; 73import jdk.internal.org.objectweb.asm.tree.LookupSwitchInsnNode; 74import jdk.internal.org.objectweb.asm.tree.MethodNode; 75import jdk.internal.org.objectweb.asm.tree.TableSwitchInsnNode; 76import jdk.internal.org.objectweb.asm.tree.TryCatchBlockNode; 77import 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 */ 88public 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 @SuppressWarnings("unchecked") 135 public Frame<V>[] analyze(final String owner, final MethodNode m) 136 throws AnalyzerException { 137 if ((m.access & (ACC_ABSTRACT | ACC_NATIVE)) != 0) { 138 frames = (Frame<V>[]) new Frame<?>[0]; 139 return frames; 140 } 141 n = m.instructions.size(); 142 insns = m.instructions; 143 handlers = (List<TryCatchBlockNode>[]) new List<?>[n]; 144 frames = (Frame<V>[]) new Frame<?>[n]; 145 subroutines = new Subroutine[n]; 146 queued = new boolean[n]; 147 queue = new int[n]; 148 top = 0; 149 150 // computes exception handlers for each instruction 151 for (int i = 0; i < m.tryCatchBlocks.size(); ++i) { 152 TryCatchBlockNode tcb = m.tryCatchBlocks.get(i); 153 int begin = insns.indexOf(tcb.start); 154 int end = insns.indexOf(tcb.end); 155 for (int j = begin; j < end; ++j) { 156 List<TryCatchBlockNode> insnHandlers = handlers[j]; 157 if (insnHandlers == null) { 158 insnHandlers = new ArrayList<TryCatchBlockNode>(); 159 handlers[j] = insnHandlers; 160 } 161 insnHandlers.add(tcb); 162 } 163 } 164 165 // computes the subroutine for each instruction: 166 Subroutine main = new Subroutine(null, m.maxLocals, null); 167 List<AbstractInsnNode> subroutineCalls = new ArrayList<AbstractInsnNode>(); 168 Map<LabelNode, Subroutine> subroutineHeads = new HashMap<LabelNode, Subroutine>(); 169 findSubroutine(0, main, subroutineCalls); 170 while (!subroutineCalls.isEmpty()) { 171 JumpInsnNode jsr = (JumpInsnNode) subroutineCalls.remove(0); 172 Subroutine sub = subroutineHeads.get(jsr.label); 173 if (sub == null) { 174 sub = new Subroutine(jsr.label, m.maxLocals, jsr); 175 subroutineHeads.put(jsr.label, sub); 176 findSubroutine(insns.indexOf(jsr.label), sub, subroutineCalls); 177 } else { 178 sub.callers.add(jsr); 179 } 180 } 181 for (int i = 0; i < n; ++i) { 182 if (subroutines[i] != null && subroutines[i].start == null) { 183 subroutines[i] = null; 184 } 185 } 186 187 // initializes the data structures for the control flow analysis 188 Frame<V> current = newFrame(m.maxLocals, m.maxStack); 189 Frame<V> handler = newFrame(m.maxLocals, m.maxStack); 190 current.setReturn(interpreter.newValue(Type.getReturnType(m.desc))); 191 Type[] args = Type.getArgumentTypes(m.desc); 192 int local = 0; 193 if ((m.access & ACC_STATIC) == 0) { 194 Type ctype = Type.getObjectType(owner); 195 current.setLocal(local++, interpreter.newValue(ctype)); 196 } 197 for (int i = 0; i < args.length; ++i) { 198 current.setLocal(local++, interpreter.newValue(args[i])); 199 if (args[i].getSize() == 2) { 200 current.setLocal(local++, interpreter.newValue(null)); 201 } 202 } 203 while (local < m.maxLocals) { 204 current.setLocal(local++, interpreter.newValue(null)); 205 } 206 merge(0, current, null); 207 208 init(owner, m); 209 210 // control flow analysis 211 while (top > 0) { 212 int insn = queue[--top]; 213 Frame<V> f = frames[insn]; 214 Subroutine subroutine = subroutines[insn]; 215 queued[insn] = false; 216 217 AbstractInsnNode insnNode = null; 218 try { 219 insnNode = m.instructions.get(insn); 220 int insnOpcode = insnNode.getOpcode(); 221 int insnType = insnNode.getType(); 222 223 if (insnType == AbstractInsnNode.LABEL 224 || insnType == AbstractInsnNode.LINE 225 || insnType == AbstractInsnNode.FRAME) { 226 merge(insn + 1, f, subroutine); 227 newControlFlowEdge(insn, insn + 1); 228 } else { 229 current.init(f).execute(insnNode, interpreter); 230 subroutine = subroutine == null ? null : subroutine.copy(); 231 232 if (insnNode instanceof JumpInsnNode) { 233 JumpInsnNode j = (JumpInsnNode) insnNode; 234 if (insnOpcode != GOTO && insnOpcode != JSR) { 235 merge(insn + 1, current, subroutine); 236 newControlFlowEdge(insn, insn + 1); 237 } 238 int jump = insns.indexOf(j.label); 239 if (insnOpcode == JSR) { 240 merge(jump, current, new Subroutine(j.label, 241 m.maxLocals, j)); 242 } else { 243 merge(jump, current, subroutine); 244 } 245 newControlFlowEdge(insn, jump); 246 } else if (insnNode instanceof LookupSwitchInsnNode) { 247 LookupSwitchInsnNode lsi = (LookupSwitchInsnNode) insnNode; 248 int jump = insns.indexOf(lsi.dflt); 249 merge(jump, current, subroutine); 250 newControlFlowEdge(insn, jump); 251 for (int j = 0; j < lsi.labels.size(); ++j) { 252 LabelNode label = lsi.labels.get(j); 253 jump = insns.indexOf(label); 254 merge(jump, current, subroutine); 255 newControlFlowEdge(insn, jump); 256 } 257 } else if (insnNode instanceof TableSwitchInsnNode) { 258 TableSwitchInsnNode tsi = (TableSwitchInsnNode) insnNode; 259 int jump = insns.indexOf(tsi.dflt); 260 merge(jump, current, subroutine); 261 newControlFlowEdge(insn, jump); 262 for (int j = 0; j < tsi.labels.size(); ++j) { 263 LabelNode label = tsi.labels.get(j); 264 jump = insns.indexOf(label); 265 merge(jump, current, subroutine); 266 newControlFlowEdge(insn, jump); 267 } 268 } else if (insnOpcode == RET) { 269 if (subroutine == null) { 270 throw new AnalyzerException(insnNode, 271 "RET instruction outside of a sub routine"); 272 } 273 for (int i = 0; i < subroutine.callers.size(); ++i) { 274 JumpInsnNode caller = subroutine.callers.get(i); 275 int call = insns.indexOf(caller); 276 if (frames[call] != null) { 277 merge(call + 1, frames[call], current, 278 subroutines[call], subroutine.access); 279 newControlFlowEdge(insn, call + 1); 280 } 281 } 282 } else if (insnOpcode != ATHROW 283 && (insnOpcode < IRETURN || insnOpcode > RETURN)) { 284 if (subroutine != null) { 285 if (insnNode instanceof VarInsnNode) { 286 int var = ((VarInsnNode) insnNode).var; 287 subroutine.access[var] = true; 288 if (insnOpcode == LLOAD || insnOpcode == DLOAD 289 || insnOpcode == LSTORE 290 || insnOpcode == DSTORE) { 291 subroutine.access[var + 1] = true; 292 } 293 } else if (insnNode instanceof IincInsnNode) { 294 int var = ((IincInsnNode) insnNode).var; 295 subroutine.access[var] = true; 296 } 297 } 298 merge(insn + 1, current, subroutine); 299 newControlFlowEdge(insn, insn + 1); 300 } 301 } 302 303 List<TryCatchBlockNode> insnHandlers = handlers[insn]; 304 if (insnHandlers != null) { 305 for (int i = 0; i < insnHandlers.size(); ++i) { 306 TryCatchBlockNode tcb = insnHandlers.get(i); 307 Type type; 308 if (tcb.type == null) { 309 type = Type.getObjectType("java/lang/Throwable"); 310 } else { 311 type = Type.getObjectType(tcb.type); 312 } 313 int jump = insns.indexOf(tcb.handler); 314 if (newControlFlowExceptionEdge(insn, tcb)) { 315 handler.init(f); 316 handler.clearStack(); 317 handler.push(interpreter.newValue(type)); 318 merge(jump, handler, subroutine); 319 } 320 } 321 } 322 } catch (AnalyzerException e) { 323 throw new AnalyzerException(e.node, "Error at instruction " 324 + insn + ": " + e.getMessage(), e); 325 } catch (Exception e) { 326 throw new AnalyzerException(insnNode, "Error at instruction " 327 + insn + ": " + e.getMessage(), e); 328 } 329 } 330 331 return frames; 332 } 333 334 private void findSubroutine(int insn, final Subroutine sub, 335 final List<AbstractInsnNode> calls) throws AnalyzerException { 336 while (true) { 337 if (insn < 0 || insn >= n) { 338 throw new AnalyzerException(null, 339 "Execution can fall off end of the code"); 340 } 341 if (subroutines[insn] != null) { 342 return; 343 } 344 subroutines[insn] = sub.copy(); 345 AbstractInsnNode node = insns.get(insn); 346 347 // calls findSubroutine recursively on normal successors 348 if (node instanceof JumpInsnNode) { 349 if (node.getOpcode() == JSR) { 350 // do not follow a JSR, it leads to another subroutine! 351 calls.add(node); 352 } else { 353 JumpInsnNode jnode = (JumpInsnNode) node; 354 findSubroutine(insns.indexOf(jnode.label), sub, calls); 355 } 356 } else if (node instanceof TableSwitchInsnNode) { 357 TableSwitchInsnNode tsnode = (TableSwitchInsnNode) node; 358 findSubroutine(insns.indexOf(tsnode.dflt), sub, calls); 359 for (int i = tsnode.labels.size() - 1; i >= 0; --i) { 360 LabelNode l = tsnode.labels.get(i); 361 findSubroutine(insns.indexOf(l), sub, calls); 362 } 363 } else if (node instanceof LookupSwitchInsnNode) { 364 LookupSwitchInsnNode lsnode = (LookupSwitchInsnNode) node; 365 findSubroutine(insns.indexOf(lsnode.dflt), sub, calls); 366 for (int i = lsnode.labels.size() - 1; i >= 0; --i) { 367 LabelNode l = lsnode.labels.get(i); 368 findSubroutine(insns.indexOf(l), sub, calls); 369 } 370 } 371 372 // calls findSubroutine recursively on exception handler successors 373 List<TryCatchBlockNode> insnHandlers = handlers[insn]; 374 if (insnHandlers != null) { 375 for (int i = 0; i < insnHandlers.size(); ++i) { 376 TryCatchBlockNode tcb = insnHandlers.get(i); 377 findSubroutine(insns.indexOf(tcb.handler), sub, calls); 378 } 379 } 380 381 // if insn does not falls through to the next instruction, return. 382 switch (node.getOpcode()) { 383 case GOTO: 384 case RET: 385 case TABLESWITCH: 386 case LOOKUPSWITCH: 387 case IRETURN: 388 case LRETURN: 389 case FRETURN: 390 case DRETURN: 391 case ARETURN: 392 case RETURN: 393 case ATHROW: 394 return; 395 } 396 insn++; 397 } 398 } 399 400 /** 401 * Returns the symbolic stack frame for each instruction of the last 402 * recently analyzed method. 403 * 404 * @return the symbolic state of the execution stack frame at each bytecode 405 * instruction of the method. The size of the returned array is 406 * equal to the number of instructions (and labels) of the method. A 407 * given frame is <tt>null</tt> if the corresponding instruction 408 * cannot be reached, or if an error occured during the analysis of 409 * the method. 410 */ 411 public Frame<V>[] getFrames() { 412 return frames; 413 } 414 415 /** 416 * Returns the exception handlers for the given instruction. 417 * 418 * @param insn 419 * the index of an instruction of the last recently analyzed 420 * method. 421 * @return a list of {@link TryCatchBlockNode} objects. 422 */ 423 public List<TryCatchBlockNode> getHandlers(final int insn) { 424 return handlers[insn]; 425 } 426 427 /** 428 * Initializes this analyzer. This method is called just before the 429 * execution of control flow analysis loop in #analyze. The default 430 * implementation of this method does nothing. 431 * 432 * @param owner 433 * the internal name of the class to which the method belongs. 434 * @param m 435 * the method to be analyzed. 436 * @throws AnalyzerException 437 * if a problem occurs. 438 */ 439 protected void init(String owner, MethodNode m) throws AnalyzerException { 440 } 441 442 /** 443 * Constructs a new frame with the given size. 444 * 445 * @param nLocals 446 * the maximum number of local variables of the frame. 447 * @param nStack 448 * the maximum stack size of the frame. 449 * @return the created frame. 450 */ 451 protected Frame<V> newFrame(final int nLocals, final int nStack) { 452 return new Frame<V>(nLocals, nStack); 453 } 454 455 /** 456 * Constructs a new frame that is identical to the given frame. 457 * 458 * @param src 459 * a frame. 460 * @return the created frame. 461 */ 462 protected Frame<V> newFrame(final Frame<? extends V> src) { 463 return new Frame<V>(src); 464 } 465 466 /** 467 * Creates a control flow graph edge. The default implementation of this 468 * method does nothing. It can be overriden in order to construct the 469 * control flow graph of a method (this method is called by the 470 * {@link #analyze analyze} method during its visit of the method's code). 471 * 472 * @param insn 473 * an instruction index. 474 * @param successor 475 * index of a successor instruction. 476 */ 477 protected void newControlFlowEdge(final int insn, final int successor) { 478 } 479 480 /** 481 * Creates a control flow graph edge corresponding to an exception handler. 482 * The default implementation of this method does nothing. It can be 483 * overridden in order to construct the control flow graph of a method (this 484 * method is called by the {@link #analyze analyze} method during its visit 485 * of the method's code). 486 * 487 * @param insn 488 * an instruction index. 489 * @param successor 490 * index of a successor instruction. 491 * @return true if this edge must be considered in the data flow analysis 492 * performed by this analyzer, or false otherwise. The default 493 * implementation of this method always returns true. 494 */ 495 protected boolean newControlFlowExceptionEdge(final int insn, 496 final int successor) { 497 return true; 498 } 499 500 /** 501 * Creates a control flow graph edge corresponding to an exception handler. 502 * The default implementation of this method delegates to 503 * {@link #newControlFlowExceptionEdge(int, int) 504 * newControlFlowExceptionEdge(int, int)}. It can be overridden in order to 505 * construct the control flow graph of a method (this method is called by 506 * the {@link #analyze analyze} method during its visit of the method's 507 * code). 508 * 509 * @param insn 510 * an instruction index. 511 * @param tcb 512 * TryCatchBlockNode corresponding to this edge. 513 * @return true if this edge must be considered in the data flow analysis 514 * performed by this analyzer, or false otherwise. The default 515 * implementation of this method delegates to 516 * {@link #newControlFlowExceptionEdge(int, int) 517 * newControlFlowExceptionEdge(int, int)}. 518 */ 519 protected boolean newControlFlowExceptionEdge(final int insn, 520 final TryCatchBlockNode tcb) { 521 return newControlFlowExceptionEdge(insn, insns.indexOf(tcb.handler)); 522 } 523 524 // ------------------------------------------------------------------------- 525 526 private void merge(final int insn, final Frame<V> frame, 527 final Subroutine subroutine) throws AnalyzerException { 528 Frame<V> oldFrame = frames[insn]; 529 Subroutine oldSubroutine = subroutines[insn]; 530 boolean changes; 531 532 if (oldFrame == null) { 533 frames[insn] = newFrame(frame); 534 changes = true; 535 } else { 536 changes = oldFrame.merge(frame, interpreter); 537 } 538 539 if (oldSubroutine == null) { 540 if (subroutine != null) { 541 subroutines[insn] = subroutine.copy(); 542 changes = true; 543 } 544 } else { 545 if (subroutine != null) { 546 changes |= oldSubroutine.merge(subroutine); 547 } 548 } 549 if (changes && !queued[insn]) { 550 queued[insn] = true; 551 queue[top++] = insn; 552 } 553 } 554 555 private void merge(final int insn, final Frame<V> beforeJSR, 556 final Frame<V> afterRET, final Subroutine subroutineBeforeJSR, 557 final boolean[] access) throws AnalyzerException { 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} 580