001/*** 002 * ASM: a very small and fast Java bytecode manipulation framework 003 * Copyright (c) 2000-2011 INRIA, France Telecom 004 * All rights reserved. 005 * 006 * Redistribution and use in source and binary forms, with or without 007 * modification, are permitted provided that the following conditions 008 * are met: 009 * 1. Redistributions of source code must retain the above copyright 010 * notice, this list of conditions and the following disclaimer. 011 * 2. Redistributions in binary form must reproduce the above copyright 012 * notice, this list of conditions and the following disclaimer in the 013 * documentation and/or other materials provided with the distribution. 014 * 3. Neither the name of the copyright holders nor the names of its 015 * contributors may be used to endorse or promote products derived from 016 * this software without specific prior written permission. 017 * 018 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 019 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 020 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 021 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 022 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 023 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 024 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 025 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 026 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 027 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 028 * THE POSSIBILITY OF SUCH DAMAGE. 029 */ 030package org.springframework.asm; 031 032/** 033 * A label represents a position in the bytecode of a method. Labels are used 034 * for jump, goto, and switch instructions, and for try catch blocks. A label 035 * designates the <i>instruction</i> that is just after. Note however that there 036 * can be other elements between a label and the instruction it designates (such 037 * as other labels, stack map frames, line numbers, etc.). 038 * 039 * @author Eric Bruneton 040 */ 041public class Label { 042 043 /** 044 * Indicates if this label is only used for debug attributes. Such a label 045 * is not the start of a basic block, the target of a jump instruction, or 046 * an exception handler. It can be safely ignored in control flow graph 047 * analysis algorithms (for optimization purposes). 048 */ 049 static final int DEBUG = 1; 050 051 /** 052 * Indicates if the position of this label is known. 053 */ 054 static final int RESOLVED = 2; 055 056 /** 057 * Indicates if this label has been updated, after instruction resizing. 058 */ 059 static final int RESIZED = 4; 060 061 /** 062 * Indicates if this basic block has been pushed in the basic block stack. 063 * See {@link MethodWriter#visitMaxs visitMaxs}. 064 */ 065 static final int PUSHED = 8; 066 067 /** 068 * Indicates if this label is the target of a jump instruction, or the start 069 * of an exception handler. 070 */ 071 static final int TARGET = 16; 072 073 /** 074 * Indicates if a stack map frame must be stored for this label. 075 */ 076 static final int STORE = 32; 077 078 /** 079 * Indicates if this label corresponds to a reachable basic block. 080 */ 081 static final int REACHABLE = 64; 082 083 /** 084 * Indicates if this basic block ends with a JSR instruction. 085 */ 086 static final int JSR = 128; 087 088 /** 089 * Indicates if this basic block ends with a RET instruction. 090 */ 091 static final int RET = 256; 092 093 /** 094 * Indicates if this basic block is the start of a subroutine. 095 */ 096 static final int SUBROUTINE = 512; 097 098 /** 099 * Indicates if this subroutine basic block has been visited by a 100 * visitSubroutine(null, ...) call. 101 */ 102 static final int VISITED = 1024; 103 104 /** 105 * Indicates if this subroutine basic block has been visited by a 106 * visitSubroutine(!null, ...) call. 107 */ 108 static final int VISITED2 = 2048; 109 110 /** 111 * Field used to associate user information to a label. Warning: this field 112 * is used by the ASM tree package. In order to use it with the ASM tree 113 * package you must override the 114 * {@code org.objectweb.asm.tree.MethodNode#getLabelNode} method. 115 */ 116 public Object info; 117 118 /** 119 * Flags that indicate the status of this label. 120 * 121 * @see #DEBUG 122 * @see #RESOLVED 123 * @see #RESIZED 124 * @see #PUSHED 125 * @see #TARGET 126 * @see #STORE 127 * @see #REACHABLE 128 * @see #JSR 129 * @see #RET 130 */ 131 int status; 132 133 /** 134 * The line number corresponding to this label, if known. If there are 135 * several lines, each line is stored in a separate label, all linked via 136 * their next field (these links are created in ClassReader and removed just 137 * before visitLabel is called, so that this does not impact the rest of the 138 * code). 139 */ 140 int line; 141 142 /** 143 * The position of this label in the code, if known. 144 */ 145 int position; 146 147 /** 148 * Number of forward references to this label, times two. 149 */ 150 private int referenceCount; 151 152 /** 153 * Informations about forward references. Each forward reference is 154 * described by two consecutive integers in this array: the first one is the 155 * position of the first byte of the bytecode instruction that contains the 156 * forward reference, while the second is the position of the first byte of 157 * the forward reference itself. In fact the sign of the first integer 158 * indicates if this reference uses 2 or 4 bytes, and its absolute value 159 * gives the position of the bytecode instruction. This array is also used 160 * as a bitset to store the subroutines to which a basic block belongs. This 161 * information is needed in {@link MethodWriter#visitMaxs}, after all 162 * forward references have been resolved. Hence the same array can be used 163 * for both purposes without problems. 164 */ 165 private int[] srcAndRefPositions; 166 167 // ------------------------------------------------------------------------ 168 169 /* 170 * Fields for the control flow and data flow graph analysis algorithms (used 171 * to compute the maximum stack size or the stack map frames). A control 172 * flow graph contains one node per "basic block", and one edge per "jump" 173 * from one basic block to another. Each node (i.e., each basic block) is 174 * represented by the Label object that corresponds to the first instruction 175 * of this basic block. Each node also stores the list of its successors in 176 * the graph, as a linked list of Edge objects. 177 * 178 * The control flow analysis algorithms used to compute the maximum stack 179 * size or the stack map frames are similar and use two steps. The first 180 * step, during the visit of each instruction, builds information about the 181 * state of the local variables and the operand stack at the end of each 182 * basic block, called the "output frame", <i>relatively</i> to the frame 183 * state at the beginning of the basic block, which is called the "input 184 * frame", and which is <i>unknown</i> during this step. The second step, in 185 * {@link MethodWriter#visitMaxs}, is a fix point algorithm that computes 186 * information about the input frame of each basic block, from the input 187 * state of the first basic block (known from the method signature), and by 188 * the using the previously computed relative output frames. 189 * 190 * The algorithm used to compute the maximum stack size only computes the 191 * relative output and absolute input stack heights, while the algorithm 192 * used to compute stack map frames computes relative output frames and 193 * absolute input frames. 194 */ 195 196 /** 197 * Start of the output stack relatively to the input stack. The exact 198 * semantics of this field depends on the algorithm that is used. 199 * 200 * When only the maximum stack size is computed, this field is the number of 201 * elements in the input stack. 202 * 203 * When the stack map frames are completely computed, this field is the 204 * offset of the first output stack element relatively to the top of the 205 * input stack. This offset is always negative or null. A null offset means 206 * that the output stack must be appended to the input stack. A -n offset 207 * means that the first n output stack elements must replace the top n input 208 * stack elements, and that the other elements must be appended to the input 209 * stack. 210 */ 211 int inputStackTop; 212 213 /** 214 * Maximum height reached by the output stack, relatively to the top of the 215 * input stack. This maximum is always positive or null. 216 */ 217 int outputStackMax; 218 219 /** 220 * Information about the input and output stack map frames of this basic 221 * block. This field is only used when {@link ClassWriter#COMPUTE_FRAMES} 222 * option is used. 223 */ 224 Frame frame; 225 226 /** 227 * The successor of this label, in the order they are visited. This linked 228 * list does not include labels used for debug info only. If 229 * {@link ClassWriter#COMPUTE_FRAMES} option is used then, in addition, it 230 * does not contain successive labels that denote the same bytecode position 231 * (in this case only the first label appears in this list). 232 */ 233 Label successor; 234 235 /** 236 * The successors of this node in the control flow graph. These successors 237 * are stored in a linked list of {@link Edge Edge} objects, linked to each 238 * other by their {@link Edge#next} field. 239 */ 240 Edge successors; 241 242 /** 243 * The next basic block in the basic block stack. This stack is used in the 244 * main loop of the fix point algorithm used in the second step of the 245 * control flow analysis algorithms. It is also used in 246 * {@link #visitSubroutine} to avoid using a recursive method, and in 247 * ClassReader to temporarily store multiple source lines for a label. 248 * 249 * @see MethodWriter#visitMaxs 250 */ 251 Label next; 252 253 // ------------------------------------------------------------------------ 254 // Constructor 255 // ------------------------------------------------------------------------ 256 257 /** 258 * Constructs a new label. 259 */ 260 public Label() { 261 } 262 263 // ------------------------------------------------------------------------ 264 // Methods to compute offsets and to manage forward references 265 // ------------------------------------------------------------------------ 266 267 /** 268 * Returns the offset corresponding to this label. This offset is computed 269 * from the start of the method's bytecode. <i>This method is intended for 270 * {@link Attribute} sub classes, and is normally not needed by class 271 * generators or adapters.</i> 272 * 273 * @return the offset corresponding to this label. 274 * @throws IllegalStateException 275 * if this label is not resolved yet. 276 */ 277 public int getOffset() { 278 if ((status & RESOLVED) == 0) { 279 throw new IllegalStateException( 280 "Label offset position has not been resolved yet"); 281 } 282 return position; 283 } 284 285 /** 286 * Puts a reference to this label in the bytecode of a method. If the 287 * position of the label is known, the offset is computed and written 288 * directly. Otherwise, a null offset is written and a new forward reference 289 * is declared for this label. 290 * 291 * @param owner 292 * the code writer that calls this method. 293 * @param out 294 * the bytecode of the method. 295 * @param source 296 * the position of first byte of the bytecode instruction that 297 * contains this label. 298 * @param wideOffset 299 * <tt>true</tt> if the reference must be stored in 4 bytes, or 300 * <tt>false</tt> if it must be stored with 2 bytes. 301 * @throws IllegalArgumentException 302 * if this label has not been created by the given code writer. 303 */ 304 void put(final MethodWriter owner, final ByteVector out, final int source, 305 final boolean wideOffset) { 306 if ((status & RESOLVED) == 0) { 307 if (wideOffset) { 308 addReference(-1 - source, out.length); 309 out.putInt(-1); 310 } else { 311 addReference(source, out.length); 312 out.putShort(-1); 313 } 314 } else { 315 if (wideOffset) { 316 out.putInt(position - source); 317 } else { 318 out.putShort(position - source); 319 } 320 } 321 } 322 323 /** 324 * Adds a forward reference to this label. This method must be called only 325 * for a true forward reference, i.e. only if this label is not resolved 326 * yet. For backward references, the offset of the reference can be, and 327 * must be, computed and stored directly. 328 * 329 * @param sourcePosition 330 * the position of the referencing instruction. This position 331 * will be used to compute the offset of this forward reference. 332 * @param referencePosition 333 * the position where the offset for this forward reference must 334 * be stored. 335 */ 336 private void addReference(final int sourcePosition, 337 final int referencePosition) { 338 if (srcAndRefPositions == null) { 339 srcAndRefPositions = new int[6]; 340 } 341 if (referenceCount >= srcAndRefPositions.length) { 342 int[] a = new int[srcAndRefPositions.length + 6]; 343 System.arraycopy(srcAndRefPositions, 0, a, 0, 344 srcAndRefPositions.length); 345 srcAndRefPositions = a; 346 } 347 srcAndRefPositions[referenceCount++] = sourcePosition; 348 srcAndRefPositions[referenceCount++] = referencePosition; 349 } 350 351 /** 352 * Resolves all forward references to this label. This method must be called 353 * when this label is added to the bytecode of the method, i.e. when its 354 * position becomes known. This method fills in the blanks that where left 355 * in the bytecode by each forward reference previously added to this label. 356 * 357 * @param owner 358 * the code writer that calls this method. 359 * @param position 360 * the position of this label in the bytecode. 361 * @param data 362 * the bytecode of the method. 363 * @return <tt>true</tt> if a blank that was left for this label was to 364 * small to store the offset. In such a case the corresponding jump 365 * instruction is replaced with a pseudo instruction (using unused 366 * opcodes) using an unsigned two bytes offset. These pseudo 367 * instructions will be replaced with standard bytecode instructions 368 * with wider offsets (4 bytes instead of 2), in ClassReader. 369 * @throws IllegalArgumentException 370 * if this label has already been resolved, or if it has not 371 * been created by the given code writer. 372 */ 373 boolean resolve(final MethodWriter owner, final int position, 374 final byte[] data) { 375 boolean needUpdate = false; 376 this.status |= RESOLVED; 377 this.position = position; 378 int i = 0; 379 while (i < referenceCount) { 380 int source = srcAndRefPositions[i++]; 381 int reference = srcAndRefPositions[i++]; 382 int offset; 383 if (source >= 0) { 384 offset = position - source; 385 if (offset < Short.MIN_VALUE || offset > Short.MAX_VALUE) { 386 /* 387 * changes the opcode of the jump instruction, in order to 388 * be able to find it later (see resizeInstructions in 389 * MethodWriter). These temporary opcodes are similar to 390 * jump instruction opcodes, except that the 2 bytes offset 391 * is unsigned (and can therefore represent values from 0 to 392 * 65535, which is sufficient since the size of a method is 393 * limited to 65535 bytes). 394 */ 395 int opcode = data[reference - 1] & 0xFF; 396 if (opcode <= Opcodes.JSR) { 397 // changes IFEQ ... JSR to opcodes 202 to 217 398 data[reference - 1] = (byte) (opcode + 49); 399 } else { 400 // changes IFNULL and IFNONNULL to opcodes 218 and 219 401 data[reference - 1] = (byte) (opcode + 20); 402 } 403 needUpdate = true; 404 } 405 data[reference++] = (byte) (offset >>> 8); 406 data[reference] = (byte) offset; 407 } else { 408 offset = position + source + 1; 409 data[reference++] = (byte) (offset >>> 24); 410 data[reference++] = (byte) (offset >>> 16); 411 data[reference++] = (byte) (offset >>> 8); 412 data[reference] = (byte) offset; 413 } 414 } 415 return needUpdate; 416 } 417 418 /** 419 * Returns the first label of the series to which this label belongs. For an 420 * isolated label or for the first label in a series of successive labels, 421 * this method returns the label itself. For other labels it returns the 422 * first label of the series. 423 * 424 * @return the first label of the series to which this label belongs. 425 */ 426 Label getFirst() { 427 return !ClassReader.FRAMES || frame == null ? this : frame.owner; 428 } 429 430 // ------------------------------------------------------------------------ 431 // Methods related to subroutines 432 // ------------------------------------------------------------------------ 433 434 /** 435 * Returns true is this basic block belongs to the given subroutine. 436 * 437 * @param id 438 * a subroutine id. 439 * @return true is this basic block belongs to the given subroutine. 440 */ 441 boolean inSubroutine(final long id) { 442 if ((status & Label.VISITED) != 0) { 443 return (srcAndRefPositions[(int) (id >>> 32)] & (int) id) != 0; 444 } 445 return false; 446 } 447 448 /** 449 * Returns true if this basic block and the given one belong to a common 450 * subroutine. 451 * 452 * @param block 453 * another basic block. 454 * @return true if this basic block and the given one belong to a common 455 * subroutine. 456 */ 457 boolean inSameSubroutine(final Label block) { 458 if ((status & VISITED) == 0 || (block.status & VISITED) == 0) { 459 return false; 460 } 461 for (int i = 0; i < srcAndRefPositions.length; ++i) { 462 if ((srcAndRefPositions[i] & block.srcAndRefPositions[i]) != 0) { 463 return true; 464 } 465 } 466 return false; 467 } 468 469 /** 470 * Marks this basic block as belonging to the given subroutine. 471 * 472 * @param id 473 * a subroutine id. 474 * @param nbSubroutines 475 * the total number of subroutines in the method. 476 */ 477 void addToSubroutine(final long id, final int nbSubroutines) { 478 if ((status & VISITED) == 0) { 479 status |= VISITED; 480 srcAndRefPositions = new int[nbSubroutines / 32 + 1]; 481 } 482 srcAndRefPositions[(int) (id >>> 32)] |= (int) id; 483 } 484 485 /** 486 * Finds the basic blocks that belong to a given subroutine, and marks these 487 * blocks as belonging to this subroutine. This method follows the control 488 * flow graph to find all the blocks that are reachable from the current 489 * block WITHOUT following any JSR target. 490 * 491 * @param JSR 492 * a JSR block that jumps to this subroutine. If this JSR is not 493 * null it is added to the successor of the RET blocks found in 494 * the subroutine. 495 * @param id 496 * the id of this subroutine. 497 * @param nbSubroutines 498 * the total number of subroutines in the method. 499 */ 500 void visitSubroutine(final Label JSR, final long id, final int nbSubroutines) { 501 // user managed stack of labels, to avoid using a recursive method 502 // (recursivity can lead to stack overflow with very large methods) 503 Label stack = this; 504 while (stack != null) { 505 // removes a label l from the stack 506 Label l = stack; 507 stack = l.next; 508 l.next = null; 509 510 if (JSR != null) { 511 if ((l.status & VISITED2) != 0) { 512 continue; 513 } 514 l.status |= VISITED2; 515 // adds JSR to the successors of l, if it is a RET block 516 if ((l.status & RET) != 0) { 517 if (!l.inSameSubroutine(JSR)) { 518 Edge e = new Edge(); 519 e.info = l.inputStackTop; 520 e.successor = JSR.successors.successor; 521 e.next = l.successors; 522 l.successors = e; 523 } 524 } 525 } else { 526 // if the l block already belongs to subroutine 'id', continue 527 if (l.inSubroutine(id)) { 528 continue; 529 } 530 // marks the l block as belonging to subroutine 'id' 531 l.addToSubroutine(id, nbSubroutines); 532 } 533 // pushes each successor of l on the stack, except JSR targets 534 Edge e = l.successors; 535 while (e != null) { 536 // if the l block is a JSR block, then 'l.successors.next' leads 537 // to the JSR target (see {@link #visitJumpInsn}) and must 538 // therefore not be followed 539 if ((l.status & Label.JSR) == 0 || e != l.successors.next) { 540 // pushes e.successor on the stack if it not already added 541 if (e.successor.next == null) { 542 e.successor.next = stack; 543 stack = e.successor; 544 } 545 } 546 e = e.next; 547 } 548 } 549 } 550 551 // ------------------------------------------------------------------------ 552 // Overriden Object methods 553 // ------------------------------------------------------------------------ 554 555 /** 556 * Returns a string representation of this label. 557 * 558 * @return a string representation of this label. 559 */ 560 @Override 561 public String toString() { 562 return "L" + System.identityHashCode(this); 563 } 564}