001// ASM: a very small and fast Java bytecode manipulation framework 002// Copyright (c) 2000-2011 INRIA, France Telecom 003// All rights reserved. 004// 005// Redistribution and use in source and binary forms, with or without 006// modification, are permitted provided that the following conditions 007// are met: 008// 1. Redistributions of source code must retain the above copyright 009// notice, this list of conditions and the following disclaimer. 010// 2. Redistributions in binary form must reproduce the above copyright 011// notice, this list of conditions and the following disclaimer in the 012// documentation and/or other materials provided with the distribution. 013// 3. Neither the name of the copyright holders nor the names of its 014// contributors may be used to endorse or promote products derived from 015// this software without specific prior written permission. 016// 017// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 018// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 019// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 020// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 021// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 022// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 023// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 024// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 025// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 026// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 027// THE POSSIBILITY OF SUCH DAMAGE. 028package org.springframework.asm; 029 030/** 031 * A position in the bytecode of a method. Labels are used for jump, goto, and switch instructions, 032 * and for try catch blocks. A label designates the <i>instruction</i> that is just after. Note 033 * however that there can be other elements between a label and the instruction it designates (such 034 * as other labels, stack map frames, line numbers, etc.). 035 * 036 * @author Eric Bruneton 037 */ 038public class Label { 039 040 /** 041 * A flag indicating that a label is only used for debug attributes. Such a label is not the start 042 * of a basic block, the target of a jump instruction, or an exception handler. It can be safely 043 * ignored in control flow graph analysis algorithms (for optimization purposes). 044 */ 045 static final int FLAG_DEBUG_ONLY = 1; 046 047 /** 048 * A flag indicating that a label is the target of a jump instruction, or the start of an 049 * exception handler. 050 */ 051 static final int FLAG_JUMP_TARGET = 2; 052 053 /** A flag indicating that the bytecode offset of a label is known. */ 054 static final int FLAG_RESOLVED = 4; 055 056 /** A flag indicating that a label corresponds to a reachable basic block. */ 057 static final int FLAG_REACHABLE = 8; 058 059 /** 060 * A flag indicating that the basic block corresponding to a label ends with a subroutine call. By 061 * construction in {@link MethodWriter#visitJumpInsn}, labels with this flag set have at least two 062 * outgoing edges: 063 * 064 * <ul> 065 * <li>the first one corresponds to the instruction that follows the jsr instruction in the 066 * bytecode, i.e. where execution continues when it returns from the jsr call. This is a 067 * virtual control flow edge, since execution never goes directly from the jsr to the next 068 * instruction. Instead, it goes to the subroutine and eventually returns to the instruction 069 * following the jsr. This virtual edge is used to compute the real outgoing edges of the 070 * basic blocks ending with a ret instruction, in {@link #addSubroutineRetSuccessors}. 071 * <li>the second one corresponds to the target of the jsr instruction, 072 * </ul> 073 */ 074 static final int FLAG_SUBROUTINE_CALLER = 16; 075 076 /** 077 * A flag indicating that the basic block corresponding to a label is the start of a subroutine. 078 */ 079 static final int FLAG_SUBROUTINE_START = 32; 080 081 /** A flag indicating that the basic block corresponding to a label is the end of a subroutine. */ 082 static final int FLAG_SUBROUTINE_END = 64; 083 084 /** 085 * The number of elements to add to the {@link #otherLineNumbers} array when it needs to be 086 * resized to store a new source line number. 087 */ 088 static final int LINE_NUMBERS_CAPACITY_INCREMENT = 4; 089 090 /** 091 * The number of elements to add to the {@link #forwardReferences} array when it needs to be 092 * resized to store a new forward reference. 093 */ 094 static final int FORWARD_REFERENCES_CAPACITY_INCREMENT = 6; 095 096 /** 097 * The bit mask to extract the type of a forward reference to this label. The extracted type is 098 * either {@link #FORWARD_REFERENCE_TYPE_SHORT} or {@link #FORWARD_REFERENCE_TYPE_WIDE}. 099 * 100 * @see #forwardReferences 101 */ 102 static final int FORWARD_REFERENCE_TYPE_MASK = 0xF0000000; 103 104 /** 105 * The type of forward references stored with two bytes in the bytecode. This is the case, for 106 * instance, of a forward reference from an ifnull instruction. 107 */ 108 static final int FORWARD_REFERENCE_TYPE_SHORT = 0x10000000; 109 110 /** 111 * The type of forward references stored in four bytes in the bytecode. This is the case, for 112 * instance, of a forward reference from a lookupswitch instruction. 113 */ 114 static final int FORWARD_REFERENCE_TYPE_WIDE = 0x20000000; 115 116 /** 117 * The bit mask to extract the 'handle' of a forward reference to this label. The extracted handle 118 * is the bytecode offset where the forward reference value is stored (using either 2 or 4 bytes, 119 * as indicated by the {@link #FORWARD_REFERENCE_TYPE_MASK}). 120 * 121 * @see #forwardReferences 122 */ 123 static final int FORWARD_REFERENCE_HANDLE_MASK = 0x0FFFFFFF; 124 125 /** 126 * A sentinel element used to indicate the end of a list of labels. 127 * 128 * @see #nextListElement 129 */ 130 static final Label EMPTY_LIST = new Label(); 131 132 /** 133 * A user managed state associated with this label. Warning: this field is used by the ASM tree 134 * package. In order to use it with the ASM tree package you must override the getLabelNode method 135 * in MethodNode. 136 */ 137 public Object info; 138 139 /** 140 * The type and status of this label or its corresponding basic block. Must be zero or more of 141 * {@link #FLAG_DEBUG_ONLY}, {@link #FLAG_JUMP_TARGET}, {@link #FLAG_RESOLVED}, {@link 142 * #FLAG_REACHABLE}, {@link #FLAG_SUBROUTINE_CALLER}, {@link #FLAG_SUBROUTINE_START}, {@link 143 * #FLAG_SUBROUTINE_END}. 144 */ 145 short flags; 146 147 /** 148 * The source line number corresponding to this label, or 0. If there are several source line 149 * numbers corresponding to this label, the first one is stored in this field, and the remaining 150 * ones are stored in {@link #otherLineNumbers}. 151 */ 152 private short lineNumber; 153 154 /** 155 * The source line numbers corresponding to this label, in addition to {@link #lineNumber}, or 156 * null. The first element of this array is the number n of source line numbers it contains, which 157 * are stored between indices 1 and n (inclusive). 158 */ 159 private int[] otherLineNumbers; 160 161 /** 162 * The offset of this label in the bytecode of its method, in bytes. This value is set if and only 163 * if the {@link #FLAG_RESOLVED} flag is set. 164 */ 165 int bytecodeOffset; 166 167 /** 168 * The forward references to this label. The first element is the number of forward references, 169 * times 2 (this corresponds to the index of the last element actually used in this array). Then, 170 * each forward reference is described with two consecutive integers noted 171 * 'sourceInsnBytecodeOffset' and 'reference': 172 * 173 * <ul> 174 * <li>'sourceInsnBytecodeOffset' is the bytecode offset of the instruction that contains the 175 * forward reference, 176 * <li>'reference' contains the type and the offset in the bytecode where the forward reference 177 * value must be stored, which can be extracted with {@link #FORWARD_REFERENCE_TYPE_MASK} 178 * and {@link #FORWARD_REFERENCE_HANDLE_MASK}. 179 * </ul> 180 * 181 * <p>For instance, for an ifnull instruction at bytecode offset x, 'sourceInsnBytecodeOffset' is 182 * equal to x, and 'reference' is of type {@link #FORWARD_REFERENCE_TYPE_SHORT} with value x + 1 183 * (because the ifnull instruction uses a 2 bytes bytecode offset operand stored one byte after 184 * the start of the instruction itself). For the default case of a lookupswitch instruction at 185 * bytecode offset x, 'sourceInsnBytecodeOffset' is equal to x, and 'reference' is of type {@link 186 * #FORWARD_REFERENCE_TYPE_WIDE} with value between x + 1 and x + 4 (because the lookupswitch 187 * instruction uses a 4 bytes bytecode offset operand stored one to four bytes after the start of 188 * the instruction itself). 189 */ 190 private int[] forwardReferences; 191 192 // ----------------------------------------------------------------------------------------------- 193 194 // Fields for the control flow and data flow graph analysis algorithms (used to compute the 195 // maximum stack size or the stack map frames). A control flow graph contains one node per "basic 196 // block", and one edge per "jump" from one basic block to another. Each node (i.e., each basic 197 // block) is represented with the Label object that corresponds to the first instruction of this 198 // basic block. Each node also stores the list of its successors in the graph, as a linked list of 199 // Edge objects. 200 // 201 // The control flow analysis algorithms used to compute the maximum stack size or the stack map 202 // frames are similar and use two steps. The first step, during the visit of each instruction, 203 // builds information about the state of the local variables and the operand stack at the end of 204 // each basic block, called the "output frame", <i>relatively</i> to the frame state at the 205 // beginning of the basic block, which is called the "input frame", and which is <i>unknown</i> 206 // during this step. The second step, in {@link MethodWriter#computeAllFrames} and {@link 207 // MethodWriter#computeMaxStackAndLocal}, is a fix point algorithm 208 // that computes information about the input frame of each basic block, from the input state of 209 // the first basic block (known from the method signature), and by the using the previously 210 // computed relative output frames. 211 // 212 // The algorithm used to compute the maximum stack size only computes the relative output and 213 // absolute input stack heights, while the algorithm used to compute stack map frames computes 214 // relative output frames and absolute input frames. 215 216 /** 217 * The number of elements in the input stack of the basic block corresponding to this label. This 218 * field is computed in {@link MethodWriter#computeMaxStackAndLocal}. 219 */ 220 short inputStackSize; 221 222 /** 223 * The number of elements in the output stack, at the end of the basic block corresponding to this 224 * label. This field is only computed for basic blocks that end with a RET instruction. 225 */ 226 short outputStackSize; 227 228 /** 229 * The maximum height reached by the output stack, relatively to the top of the input stack, in 230 * the basic block corresponding to this label. This maximum is always positive or {@literal 231 * null}. 232 */ 233 short outputStackMax; 234 235 /** 236 * The id of the subroutine to which this basic block belongs, or 0. If the basic block belongs to 237 * several subroutines, this is the id of the "oldest" subroutine that contains it (with the 238 * convention that a subroutine calling another one is "older" than the callee). This field is 239 * computed in {@link MethodWriter#computeMaxStackAndLocal}, if the method contains JSR 240 * instructions. 241 */ 242 short subroutineId; 243 244 /** 245 * The input and output stack map frames of the basic block corresponding to this label. This 246 * field is only used when the {@link MethodWriter#COMPUTE_ALL_FRAMES} or {@link 247 * MethodWriter#COMPUTE_INSERTED_FRAMES} option is used. 248 */ 249 Frame frame; 250 251 /** 252 * The successor of this label, in the order they are visited in {@link MethodVisitor#visitLabel}. 253 * This linked list does not include labels used for debug info only. If the {@link 254 * MethodWriter#COMPUTE_ALL_FRAMES} or {@link MethodWriter#COMPUTE_INSERTED_FRAMES} option is used 255 * then it does not contain either successive labels that denote the same bytecode offset (in this 256 * case only the first label appears in this list). 257 */ 258 Label nextBasicBlock; 259 260 /** 261 * The outgoing edges of the basic block corresponding to this label, in the control flow graph of 262 * its method. These edges are stored in a linked list of {@link Edge} objects, linked to each 263 * other by their {@link Edge#nextEdge} field. 264 */ 265 Edge outgoingEdges; 266 267 /** 268 * The next element in the list of labels to which this label belongs, or {@literal null} if it 269 * does not belong to any list. All lists of labels must end with the {@link #EMPTY_LIST} 270 * sentinel, in order to ensure that this field is null if and only if this label does not belong 271 * to a list of labels. Note that there can be several lists of labels at the same time, but that 272 * a label can belong to at most one list at a time (unless some lists share a common tail, but 273 * this is not used in practice). 274 * 275 * <p>List of labels are used in {@link MethodWriter#computeAllFrames} and {@link 276 * MethodWriter#computeMaxStackAndLocal} to compute stack map frames and the maximum stack size, 277 * respectively, as well as in {@link #markSubroutine} and {@link #addSubroutineRetSuccessors} to 278 * compute the basic blocks belonging to subroutines and their outgoing edges. Outside of these 279 * methods, this field should be null (this property is a precondition and a postcondition of 280 * these methods). 281 */ 282 Label nextListElement; 283 284 // ----------------------------------------------------------------------------------------------- 285 // Constructor and accessors 286 // ----------------------------------------------------------------------------------------------- 287 288 /** Constructs a new label. */ 289 public Label() { 290 // Nothing to do. 291 } 292 293 /** 294 * Returns the bytecode offset corresponding to this label. This offset is computed from the start 295 * of the method's bytecode. <i>This method is intended for {@link Attribute} sub classes, and is 296 * normally not needed by class generators or adapters.</i> 297 * 298 * @return the bytecode offset corresponding to this label. 299 * @throws IllegalStateException if this label is not resolved yet. 300 */ 301 public int getOffset() { 302 if ((flags & FLAG_RESOLVED) == 0) { 303 throw new IllegalStateException("Label offset position has not been resolved yet"); 304 } 305 return bytecodeOffset; 306 } 307 308 /** 309 * Returns the "canonical" {@link Label} instance corresponding to this label's bytecode offset, 310 * if known, otherwise the label itself. The canonical instance is the first label (in the order 311 * of their visit by {@link MethodVisitor#visitLabel}) corresponding to this bytecode offset. It 312 * cannot be known for labels which have not been visited yet. 313 * 314 * <p><i>This method should only be used when the {@link MethodWriter#COMPUTE_ALL_FRAMES} option 315 * is used.</i> 316 * 317 * @return the label itself if {@link #frame} is null, otherwise the Label's frame owner. This 318 * corresponds to the "canonical" label instance described above thanks to the way the label 319 * frame is set in {@link MethodWriter#visitLabel}. 320 */ 321 final Label getCanonicalInstance() { 322 return frame == null ? this : frame.owner; 323 } 324 325 // ----------------------------------------------------------------------------------------------- 326 // Methods to manage line numbers 327 // ----------------------------------------------------------------------------------------------- 328 329 /** 330 * Adds a source line number corresponding to this label. 331 * 332 * @param lineNumber a source line number (which should be strictly positive). 333 */ 334 final void addLineNumber(final int lineNumber) { 335 if (this.lineNumber == 0) { 336 this.lineNumber = (short) lineNumber; 337 } else { 338 if (otherLineNumbers == null) { 339 otherLineNumbers = new int[LINE_NUMBERS_CAPACITY_INCREMENT]; 340 } 341 int otherLineNumberIndex = ++otherLineNumbers[0]; 342 if (otherLineNumberIndex >= otherLineNumbers.length) { 343 int[] newLineNumbers = new int[otherLineNumbers.length + LINE_NUMBERS_CAPACITY_INCREMENT]; 344 System.arraycopy(otherLineNumbers, 0, newLineNumbers, 0, otherLineNumbers.length); 345 otherLineNumbers = newLineNumbers; 346 } 347 otherLineNumbers[otherLineNumberIndex] = lineNumber; 348 } 349 } 350 351 /** 352 * Makes the given visitor visit this label and its source line numbers, if applicable. 353 * 354 * @param methodVisitor a method visitor. 355 * @param visitLineNumbers whether to visit of the label's source line numbers, if any. 356 */ 357 final void accept(final MethodVisitor methodVisitor, final boolean visitLineNumbers) { 358 methodVisitor.visitLabel(this); 359 if (visitLineNumbers && lineNumber != 0) { 360 methodVisitor.visitLineNumber(lineNumber & 0xFFFF, this); 361 if (otherLineNumbers != null) { 362 for (int i = 1; i <= otherLineNumbers[0]; ++i) { 363 methodVisitor.visitLineNumber(otherLineNumbers[i], this); 364 } 365 } 366 } 367 } 368 369 // ----------------------------------------------------------------------------------------------- 370 // Methods to compute offsets and to manage forward references 371 // ----------------------------------------------------------------------------------------------- 372 373 /** 374 * Puts a reference to this label in the bytecode of a method. If the bytecode offset of the label 375 * is known, the relative bytecode offset between the label and the instruction referencing it is 376 * computed and written directly. Otherwise, a null relative offset is written and a new forward 377 * reference is declared for this label. 378 * 379 * @param code the bytecode of the method. This is where the reference is appended. 380 * @param sourceInsnBytecodeOffset the bytecode offset of the instruction that contains the 381 * reference to be appended. 382 * @param wideReference whether the reference must be stored in 4 bytes (instead of 2 bytes). 383 */ 384 final void put( 385 final ByteVector code, final int sourceInsnBytecodeOffset, final boolean wideReference) { 386 if ((flags & FLAG_RESOLVED) == 0) { 387 if (wideReference) { 388 addForwardReference(sourceInsnBytecodeOffset, FORWARD_REFERENCE_TYPE_WIDE, code.length); 389 code.putInt(-1); 390 } else { 391 addForwardReference(sourceInsnBytecodeOffset, FORWARD_REFERENCE_TYPE_SHORT, code.length); 392 code.putShort(-1); 393 } 394 } else { 395 if (wideReference) { 396 code.putInt(bytecodeOffset - sourceInsnBytecodeOffset); 397 } else { 398 code.putShort(bytecodeOffset - sourceInsnBytecodeOffset); 399 } 400 } 401 } 402 403 /** 404 * Adds a forward reference to this label. This method must be called only for a true forward 405 * reference, i.e. only if this label is not resolved yet. For backward references, the relative 406 * bytecode offset of the reference can be, and must be, computed and stored directly. 407 * 408 * @param sourceInsnBytecodeOffset the bytecode offset of the instruction that contains the 409 * reference stored at referenceHandle. 410 * @param referenceType either {@link #FORWARD_REFERENCE_TYPE_SHORT} or {@link 411 * #FORWARD_REFERENCE_TYPE_WIDE}. 412 * @param referenceHandle the offset in the bytecode where the forward reference value must be 413 * stored. 414 */ 415 private void addForwardReference( 416 final int sourceInsnBytecodeOffset, final int referenceType, final int referenceHandle) { 417 if (forwardReferences == null) { 418 forwardReferences = new int[FORWARD_REFERENCES_CAPACITY_INCREMENT]; 419 } 420 int lastElementIndex = forwardReferences[0]; 421 if (lastElementIndex + 2 >= forwardReferences.length) { 422 int[] newValues = new int[forwardReferences.length + FORWARD_REFERENCES_CAPACITY_INCREMENT]; 423 System.arraycopy(forwardReferences, 0, newValues, 0, forwardReferences.length); 424 forwardReferences = newValues; 425 } 426 forwardReferences[++lastElementIndex] = sourceInsnBytecodeOffset; 427 forwardReferences[++lastElementIndex] = referenceType | referenceHandle; 428 forwardReferences[0] = lastElementIndex; 429 } 430 431 /** 432 * Sets the bytecode offset of this label to the given value and resolves the forward references 433 * to this label, if any. This method must be called when this label is added to the bytecode of 434 * the method, i.e. when its bytecode offset becomes known. This method fills in the blanks that 435 * where left in the bytecode by each forward reference previously added to this label. 436 * 437 * @param code the bytecode of the method. 438 * @param bytecodeOffset the bytecode offset of this label. 439 * @return {@literal true} if a blank that was left for this label was too small to store the 440 * offset. In such a case the corresponding jump instruction is replaced with an equivalent 441 * ASM specific instruction using an unsigned two bytes offset. These ASM specific 442 * instructions are later replaced with standard bytecode instructions with wider offsets (4 443 * bytes instead of 2), in ClassReader. 444 */ 445 final boolean resolve(final byte[] code, final int bytecodeOffset) { 446 this.flags |= FLAG_RESOLVED; 447 this.bytecodeOffset = bytecodeOffset; 448 if (forwardReferences == null) { 449 return false; 450 } 451 boolean hasAsmInstructions = false; 452 for (int i = forwardReferences[0]; i > 0; i -= 2) { 453 final int sourceInsnBytecodeOffset = forwardReferences[i - 1]; 454 final int reference = forwardReferences[i]; 455 final int relativeOffset = bytecodeOffset - sourceInsnBytecodeOffset; 456 int handle = reference & FORWARD_REFERENCE_HANDLE_MASK; 457 if ((reference & FORWARD_REFERENCE_TYPE_MASK) == FORWARD_REFERENCE_TYPE_SHORT) { 458 if (relativeOffset < Short.MIN_VALUE || relativeOffset > Short.MAX_VALUE) { 459 // Change the opcode of the jump instruction, in order to be able to find it later in 460 // ClassReader. These ASM specific opcodes are similar to jump instruction opcodes, except 461 // that the 2 bytes offset is unsigned (and can therefore represent values from 0 to 462 // 65535, which is sufficient since the size of a method is limited to 65535 bytes). 463 int opcode = code[sourceInsnBytecodeOffset] & 0xFF; 464 if (opcode < Opcodes.IFNULL) { 465 // Change IFEQ ... JSR to ASM_IFEQ ... ASM_JSR. 466 code[sourceInsnBytecodeOffset] = (byte) (opcode + Constants.ASM_OPCODE_DELTA); 467 } else { 468 // Change IFNULL and IFNONNULL to ASM_IFNULL and ASM_IFNONNULL. 469 code[sourceInsnBytecodeOffset] = (byte) (opcode + Constants.ASM_IFNULL_OPCODE_DELTA); 470 } 471 hasAsmInstructions = true; 472 } 473 code[handle++] = (byte) (relativeOffset >>> 8); 474 code[handle] = (byte) relativeOffset; 475 } else { 476 code[handle++] = (byte) (relativeOffset >>> 24); 477 code[handle++] = (byte) (relativeOffset >>> 16); 478 code[handle++] = (byte) (relativeOffset >>> 8); 479 code[handle] = (byte) relativeOffset; 480 } 481 } 482 return hasAsmInstructions; 483 } 484 485 // ----------------------------------------------------------------------------------------------- 486 // Methods related to subroutines 487 // ----------------------------------------------------------------------------------------------- 488 489 /** 490 * Finds the basic blocks that belong to the subroutine starting with the basic block 491 * corresponding to this label, and marks these blocks as belonging to this subroutine. This 492 * method follows the control flow graph to find all the blocks that are reachable from the 493 * current basic block WITHOUT following any jsr target. 494 * 495 * <p>Note: a precondition and postcondition of this method is that all labels must have a null 496 * {@link #nextListElement}. 497 * 498 * @param subroutineId the id of the subroutine starting with the basic block corresponding to 499 * this label. 500 */ 501 final void markSubroutine(final short subroutineId) { 502 // Data flow algorithm: put this basic block in a list of blocks to process (which are blocks 503 // belonging to subroutine subroutineId) and, while there are blocks to process, remove one from 504 // the list, mark it as belonging to the subroutine, and add its successor basic blocks in the 505 // control flow graph to the list of blocks to process (if not already done). 506 Label listOfBlocksToProcess = this; 507 listOfBlocksToProcess.nextListElement = EMPTY_LIST; 508 while (listOfBlocksToProcess != EMPTY_LIST) { 509 // Remove a basic block from the list of blocks to process. 510 Label basicBlock = listOfBlocksToProcess; 511 listOfBlocksToProcess = listOfBlocksToProcess.nextListElement; 512 basicBlock.nextListElement = null; 513 514 // If it is not already marked as belonging to a subroutine, mark it as belonging to 515 // subroutineId and add its successors to the list of blocks to process (unless already done). 516 if (basicBlock.subroutineId == 0) { 517 basicBlock.subroutineId = subroutineId; 518 listOfBlocksToProcess = basicBlock.pushSuccessors(listOfBlocksToProcess); 519 } 520 } 521 } 522 523 /** 524 * Finds the basic blocks that end a subroutine starting with the basic block corresponding to 525 * this label and, for each one of them, adds an outgoing edge to the basic block following the 526 * given subroutine call. In other words, completes the control flow graph by adding the edges 527 * corresponding to the return from this subroutine, when called from the given caller basic 528 * block. 529 * 530 * <p>Note: a precondition and postcondition of this method is that all labels must have a null 531 * {@link #nextListElement}. 532 * 533 * @param subroutineCaller a basic block that ends with a jsr to the basic block corresponding to 534 * this label. This label is supposed to correspond to the start of a subroutine. 535 */ 536 final void addSubroutineRetSuccessors(final Label subroutineCaller) { 537 // Data flow algorithm: put this basic block in a list blocks to process (which are blocks 538 // belonging to a subroutine starting with this label) and, while there are blocks to process, 539 // remove one from the list, put it in a list of blocks that have been processed, add a return 540 // edge to the successor of subroutineCaller if applicable, and add its successor basic blocks 541 // in the control flow graph to the list of blocks to process (if not already done). 542 Label listOfProcessedBlocks = EMPTY_LIST; 543 Label listOfBlocksToProcess = this; 544 listOfBlocksToProcess.nextListElement = EMPTY_LIST; 545 while (listOfBlocksToProcess != EMPTY_LIST) { 546 // Move a basic block from the list of blocks to process to the list of processed blocks. 547 Label basicBlock = listOfBlocksToProcess; 548 listOfBlocksToProcess = basicBlock.nextListElement; 549 basicBlock.nextListElement = listOfProcessedBlocks; 550 listOfProcessedBlocks = basicBlock; 551 552 // Add an edge from this block to the successor of the caller basic block, if this block is 553 // the end of a subroutine and if this block and subroutineCaller do not belong to the same 554 // subroutine. 555 if ((basicBlock.flags & FLAG_SUBROUTINE_END) != 0 556 && basicBlock.subroutineId != subroutineCaller.subroutineId) { 557 basicBlock.outgoingEdges = 558 new Edge( 559 basicBlock.outputStackSize, 560 // By construction, the first outgoing edge of a basic block that ends with a jsr 561 // instruction leads to the jsr continuation block, i.e. where execution continues 562 // when ret is called (see {@link #FLAG_SUBROUTINE_CALLER}). 563 subroutineCaller.outgoingEdges.successor, 564 basicBlock.outgoingEdges); 565 } 566 // Add its successors to the list of blocks to process. Note that {@link #pushSuccessors} does 567 // not push basic blocks which are already in a list. Here this means either in the list of 568 // blocks to process, or in the list of already processed blocks. This second list is 569 // important to make sure we don't reprocess an already processed block. 570 listOfBlocksToProcess = basicBlock.pushSuccessors(listOfBlocksToProcess); 571 } 572 // Reset the {@link #nextListElement} of all the basic blocks that have been processed to null, 573 // so that this method can be called again with a different subroutine or subroutine caller. 574 while (listOfProcessedBlocks != EMPTY_LIST) { 575 Label newListOfProcessedBlocks = listOfProcessedBlocks.nextListElement; 576 listOfProcessedBlocks.nextListElement = null; 577 listOfProcessedBlocks = newListOfProcessedBlocks; 578 } 579 } 580 581 /** 582 * Adds the successors of this label in the method's control flow graph (except those 583 * corresponding to a jsr target, and those already in a list of labels) to the given list of 584 * blocks to process, and returns the new list. 585 * 586 * @param listOfLabelsToProcess a list of basic blocks to process, linked together with their 587 * {@link #nextListElement} field. 588 * @return the new list of blocks to process. 589 */ 590 private Label pushSuccessors(final Label listOfLabelsToProcess) { 591 Label newListOfLabelsToProcess = listOfLabelsToProcess; 592 Edge outgoingEdge = outgoingEdges; 593 while (outgoingEdge != null) { 594 // By construction, the second outgoing edge of a basic block that ends with a jsr instruction 595 // leads to the jsr target (see {@link #FLAG_SUBROUTINE_CALLER}). 596 boolean isJsrTarget = 597 (flags & Label.FLAG_SUBROUTINE_CALLER) != 0 && outgoingEdge == outgoingEdges.nextEdge; 598 if (!isJsrTarget && outgoingEdge.successor.nextListElement == null) { 599 // Add this successor to the list of blocks to process, if it does not already belong to a 600 // list of labels. 601 outgoingEdge.successor.nextListElement = newListOfLabelsToProcess; 602 newListOfLabelsToProcess = outgoingEdge.successor; 603 } 604 outgoingEdge = outgoingEdge.nextEdge; 605 } 606 return newListOfLabelsToProcess; 607 } 608 609 // ----------------------------------------------------------------------------------------------- 610 // Overridden Object methods 611 // ----------------------------------------------------------------------------------------------- 612 613 /** 614 * Returns a string representation of this label. 615 * 616 * @return a string representation of this label. 617 */ 618 @Override 619 public String toString() { 620 return "L" + System.identityHashCode(this); 621 } 622}