annotate src/clojure/asm/Label.java @ 10:ef7dbbd6452c

added clojure source goodness
author Robert McIntyre <rlm@mit.edu>
date Sat, 21 Aug 2010 06:25:44 -0400
parents
children
rev   line source
rlm@10 1 /***
rlm@10 2 * ASM: a very small and fast Java bytecode manipulation framework
rlm@10 3 * Copyright (c) 2000-2005 INRIA, France Telecom
rlm@10 4 * All rights reserved.
rlm@10 5 *
rlm@10 6 * Redistribution and use in source and binary forms, with or without
rlm@10 7 * modification, are permitted provided that the following conditions
rlm@10 8 * are met:
rlm@10 9 * 1. Redistributions of source code must retain the above copyright
rlm@10 10 * notice, this list of conditions and the following disclaimer.
rlm@10 11 * 2. Redistributions in binary form must reproduce the above copyright
rlm@10 12 * notice, this list of conditions and the following disclaimer in the
rlm@10 13 * documentation and/or other materials provided with the distribution.
rlm@10 14 * 3. Neither the name of the copyright holders nor the names of its
rlm@10 15 * contributors may be used to endorse or promote products derived from
rlm@10 16 * this software without specific prior written permission.
rlm@10 17 *
rlm@10 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
rlm@10 19 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
rlm@10 20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
rlm@10 21 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
rlm@10 22 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
rlm@10 23 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
rlm@10 24 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
rlm@10 25 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
rlm@10 26 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
rlm@10 27 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
rlm@10 28 * THE POSSIBILITY OF SUCH DAMAGE.
rlm@10 29 */
rlm@10 30 package clojure.asm;
rlm@10 31
rlm@10 32 /**
rlm@10 33 * A label represents a position in the bytecode of a method. Labels are used
rlm@10 34 * for jump, goto, and switch instructions, and for try catch blocks.
rlm@10 35 *
rlm@10 36 * @author Eric Bruneton
rlm@10 37 */
rlm@10 38 public class Label{
rlm@10 39
rlm@10 40 /**
rlm@10 41 * Indicates if this label is only used for debug attributes. Such a label
rlm@10 42 * is not the start of a basic block, the target of a jump instruction, or
rlm@10 43 * an exception handler. It can be safely ignored in control flow graph
rlm@10 44 * analysis algorithms (for optimization purposes).
rlm@10 45 */
rlm@10 46 final static int DEBUG = 1;
rlm@10 47
rlm@10 48 /**
rlm@10 49 * Indicates if the position of this label is known.
rlm@10 50 */
rlm@10 51 final static int RESOLVED = 2;
rlm@10 52
rlm@10 53 /**
rlm@10 54 * Indicates if this label has been updated, after instruction resizing.
rlm@10 55 */
rlm@10 56 final static int RESIZED = 4;
rlm@10 57
rlm@10 58 /**
rlm@10 59 * Indicates if this basic block has been pushed in the basic block stack.
rlm@10 60 * See {@link MethodWriter#visitMaxs visitMaxs}.
rlm@10 61 */
rlm@10 62 final static int PUSHED = 8;
rlm@10 63
rlm@10 64 /**
rlm@10 65 * Indicates if this label is the target of a jump instruction, or the start
rlm@10 66 * of an exception handler.
rlm@10 67 */
rlm@10 68 final static int TARGET = 16;
rlm@10 69
rlm@10 70 /**
rlm@10 71 * Indicates if a stack map frame must be stored for this label.
rlm@10 72 */
rlm@10 73 final static int STORE = 32;
rlm@10 74
rlm@10 75 /**
rlm@10 76 * Indicates if this label corresponds to a reachable basic block.
rlm@10 77 */
rlm@10 78 final static int REACHABLE = 64;
rlm@10 79
rlm@10 80 /**
rlm@10 81 * Indicates if this basic block ends with a JSR instruction.
rlm@10 82 */
rlm@10 83 final static int JSR = 128;
rlm@10 84
rlm@10 85 /**
rlm@10 86 * Indicates if this basic block ends with a RET instruction.
rlm@10 87 */
rlm@10 88 final static int RET = 256;
rlm@10 89
rlm@10 90 /**
rlm@10 91 * Field used to associate user information to a label.
rlm@10 92 */
rlm@10 93 public Object info;
rlm@10 94
rlm@10 95 /**
rlm@10 96 * Flags that indicate the status of this label.
rlm@10 97 *
rlm@10 98 * @see #DEBUG
rlm@10 99 * @see #RESOLVED
rlm@10 100 * @see #RESIZED
rlm@10 101 * @see #PUSHED
rlm@10 102 * @see #TARGET
rlm@10 103 * @see #STORE
rlm@10 104 * @see #REACHABLE
rlm@10 105 * @see #JSR
rlm@10 106 * @see #RET
rlm@10 107 */
rlm@10 108 int status;
rlm@10 109
rlm@10 110 /**
rlm@10 111 * The line number corresponding to this label, if known.
rlm@10 112 */
rlm@10 113 int line;
rlm@10 114
rlm@10 115 /**
rlm@10 116 * The position of this label in the code, if known.
rlm@10 117 */
rlm@10 118 int position;
rlm@10 119
rlm@10 120 /**
rlm@10 121 * Number of forward references to this label, times two.
rlm@10 122 */
rlm@10 123 private int referenceCount;
rlm@10 124
rlm@10 125 /**
rlm@10 126 * Informations about forward references. Each forward reference is
rlm@10 127 * described by two consecutive integers in this array: the first one is the
rlm@10 128 * position of the first byte of the bytecode instruction that contains the
rlm@10 129 * forward reference, while the second is the position of the first byte of
rlm@10 130 * the forward reference itself. In fact the sign of the first integer
rlm@10 131 * indicates if this reference uses 2 or 4 bytes, and its absolute value
rlm@10 132 * gives the position of the bytecode instruction.
rlm@10 133 */
rlm@10 134 private int[] srcAndRefPositions;
rlm@10 135
rlm@10 136 // ------------------------------------------------------------------------
rlm@10 137
rlm@10 138 /*
rlm@10 139 * Fields for the control flow and data flow graph analysis algorithms (used
rlm@10 140 * to compute the maximum stack size or the stack map frames). A control
rlm@10 141 * flow graph contains one node per "basic block", and one edge per "jump"
rlm@10 142 * from one basic block to another. Each node (i.e., each basic block) is
rlm@10 143 * represented by the Label object that corresponds to the first instruction
rlm@10 144 * of this basic block. Each node also stores the list of its successors in
rlm@10 145 * the graph, as a linked list of Edge objects.
rlm@10 146 *
rlm@10 147 * The control flow analysis algorithms used to compute the maximum stack
rlm@10 148 * size or the stack map frames are similar and use two steps. The first
rlm@10 149 * step, during the visit of each instruction, builds information about the
rlm@10 150 * state of the local variables and the operand stack at the end of each
rlm@10 151 * basic block, called the "output frame", <i>relatively</i> to the frame
rlm@10 152 * state at the beginning of the basic block, which is called the "input
rlm@10 153 * frame", and which is <i>unknown</i> during this step. The second step,
rlm@10 154 * in {@link MethodWriter#visitMaxs}, is a fix point algorithm that
rlm@10 155 * computes information about the input frame of each basic block, from the
rlm@10 156 * input state of the first basic block (known from the method signature),
rlm@10 157 * and by the using the previously computed relative output frames.
rlm@10 158 *
rlm@10 159 * The algorithm used to compute the maximum stack size only computes the
rlm@10 160 * relative output and absolute input stack heights, while the algorithm
rlm@10 161 * used to compute stack map frames computes relative output frames and
rlm@10 162 * absolute input frames.
rlm@10 163 */
rlm@10 164
rlm@10 165 /**
rlm@10 166 * Start of the output stack relatively to the input stack. The exact
rlm@10 167 * semantics of this field depends on the algorithm that is used.
rlm@10 168 * <p/>
rlm@10 169 * When only the maximum stack size is computed, this field is the number of
rlm@10 170 * elements in the input stack.
rlm@10 171 * <p/>
rlm@10 172 * When the stack map frames are completely computed, this field is the
rlm@10 173 * offset of the first output stack element relatively to the top of the
rlm@10 174 * input stack. This offset is always negative or null. A null offset means
rlm@10 175 * that the output stack must be appended to the input stack. A -n offset
rlm@10 176 * means that the first n output stack elements must replace the top n input
rlm@10 177 * stack elements, and that the other elements must be appended to the input
rlm@10 178 * stack.
rlm@10 179 */
rlm@10 180 int inputStackTop;
rlm@10 181
rlm@10 182 /**
rlm@10 183 * Maximum height reached by the output stack, relatively to the top of the
rlm@10 184 * input stack. This maximum is always positive or null.
rlm@10 185 */
rlm@10 186 int outputStackMax;
rlm@10 187
rlm@10 188 /**
rlm@10 189 * Information about the input and output stack map frames of this basic
rlm@10 190 * block. This field is only used when {@link ClassWriter#COMPUTE_FRAMES}
rlm@10 191 * option is used.
rlm@10 192 */
rlm@10 193 Frame frame;
rlm@10 194
rlm@10 195 /**
rlm@10 196 * The successor of this label, in the order they are visited. This linked
rlm@10 197 * list does not include labels used for debug info only. If
rlm@10 198 * {@link ClassWriter#COMPUTE_FRAMES} option is used then, in addition, it
rlm@10 199 * does not contain successive labels that denote the same bytecode position
rlm@10 200 * (in this case only the first label appears in this list).
rlm@10 201 */
rlm@10 202 Label successor;
rlm@10 203
rlm@10 204 /**
rlm@10 205 * The successors of this node in the control flow graph. These successors
rlm@10 206 * are stored in a linked list of {@link Edge Edge} objects, linked to each
rlm@10 207 * other by their {@link Edge#next} field.
rlm@10 208 */
rlm@10 209 Edge successors;
rlm@10 210
rlm@10 211 /**
rlm@10 212 * The next basic block in the basic block stack. This stack is used in the
rlm@10 213 * main loop of the fix point algorithm used in the second step of the
rlm@10 214 * control flow analysis algorithms.
rlm@10 215 *
rlm@10 216 * @see MethodWriter#visitMaxs
rlm@10 217 */
rlm@10 218 Label next;
rlm@10 219
rlm@10 220 // ------------------------------------------------------------------------
rlm@10 221 // Constructor
rlm@10 222 // ------------------------------------------------------------------------
rlm@10 223
rlm@10 224 /**
rlm@10 225 * Constructs a new label.
rlm@10 226 */
rlm@10 227 public Label(){
rlm@10 228 }
rlm@10 229
rlm@10 230 /**
rlm@10 231 * Constructs a new label.
rlm@10 232 *
rlm@10 233 * @param debug if this label is only used for debug attributes.
rlm@10 234 */
rlm@10 235 Label(final boolean debug){
rlm@10 236 this.status = debug ? DEBUG : 0;
rlm@10 237 }
rlm@10 238
rlm@10 239 // ------------------------------------------------------------------------
rlm@10 240 // Methods to compute offsets and to manage forward references
rlm@10 241 // ------------------------------------------------------------------------
rlm@10 242
rlm@10 243 /**
rlm@10 244 * Returns the offset corresponding to this label. This offset is computed
rlm@10 245 * from the start of the method's bytecode. <i>This method is intended for
rlm@10 246 * {@link Attribute} sub classes, and is normally not needed by class
rlm@10 247 * generators or adapters.</i>
rlm@10 248 *
rlm@10 249 * @return the offset corresponding to this label.
rlm@10 250 * @throws IllegalStateException if this label is not resolved yet.
rlm@10 251 */
rlm@10 252 public int getOffset(){
rlm@10 253 if((status & RESOLVED) == 0)
rlm@10 254 {
rlm@10 255 throw new IllegalStateException("Label offset position has not been resolved yet");
rlm@10 256 }
rlm@10 257 return position;
rlm@10 258 }
rlm@10 259
rlm@10 260 /**
rlm@10 261 * Puts a reference to this label in the bytecode of a method. If the
rlm@10 262 * position of the label is known, the offset is computed and written
rlm@10 263 * directly. Otherwise, a null offset is written and a new forward reference
rlm@10 264 * is declared for this label.
rlm@10 265 *
rlm@10 266 * @param owner the code writer that calls this method.
rlm@10 267 * @param out the bytecode of the method.
rlm@10 268 * @param source the position of first byte of the bytecode instruction that
rlm@10 269 * contains this label.
rlm@10 270 * @param wideOffset <tt>true</tt> if the reference must be stored in 4
rlm@10 271 * bytes, or <tt>false</tt> if it must be stored with 2 bytes.
rlm@10 272 * @throws IllegalArgumentException if this label has not been created by
rlm@10 273 * the given code writer.
rlm@10 274 */
rlm@10 275 void put(
rlm@10 276 final MethodWriter owner,
rlm@10 277 final ByteVector out,
rlm@10 278 final int source,
rlm@10 279 final boolean wideOffset){
rlm@10 280 if((status & RESOLVED) != 0)
rlm@10 281 {
rlm@10 282 if(wideOffset)
rlm@10 283 {
rlm@10 284 out.putInt(position - source);
rlm@10 285 }
rlm@10 286 else
rlm@10 287 {
rlm@10 288 out.putShort(position - source);
rlm@10 289 }
rlm@10 290 }
rlm@10 291 else
rlm@10 292 {
rlm@10 293 if(wideOffset)
rlm@10 294 {
rlm@10 295 addReference(-1 - source, out.length);
rlm@10 296 out.putInt(-1);
rlm@10 297 }
rlm@10 298 else
rlm@10 299 {
rlm@10 300 addReference(source, out.length);
rlm@10 301 out.putShort(-1);
rlm@10 302 }
rlm@10 303 }
rlm@10 304 }
rlm@10 305
rlm@10 306 /**
rlm@10 307 * Adds a forward reference to this label. This method must be called only
rlm@10 308 * for a true forward reference, i.e. only if this label is not resolved
rlm@10 309 * yet. For backward references, the offset of the reference can be, and
rlm@10 310 * must be, computed and stored directly.
rlm@10 311 *
rlm@10 312 * @param sourcePosition the position of the referencing instruction. This
rlm@10 313 * position will be used to compute the offset of this forward
rlm@10 314 * reference.
rlm@10 315 * @param referencePosition the position where the offset for this forward
rlm@10 316 * reference must be stored.
rlm@10 317 */
rlm@10 318 private void addReference(
rlm@10 319 final int sourcePosition,
rlm@10 320 final int referencePosition){
rlm@10 321 if(srcAndRefPositions == null)
rlm@10 322 {
rlm@10 323 srcAndRefPositions = new int[6];
rlm@10 324 }
rlm@10 325 if(referenceCount >= srcAndRefPositions.length)
rlm@10 326 {
rlm@10 327 int[] a = new int[srcAndRefPositions.length + 6];
rlm@10 328 System.arraycopy(srcAndRefPositions,
rlm@10 329 0,
rlm@10 330 a,
rlm@10 331 0,
rlm@10 332 srcAndRefPositions.length);
rlm@10 333 srcAndRefPositions = a;
rlm@10 334 }
rlm@10 335 srcAndRefPositions[referenceCount++] = sourcePosition;
rlm@10 336 srcAndRefPositions[referenceCount++] = referencePosition;
rlm@10 337 }
rlm@10 338
rlm@10 339 /**
rlm@10 340 * Resolves all forward references to this label. This method must be called
rlm@10 341 * when this label is added to the bytecode of the method, i.e. when its
rlm@10 342 * position becomes known. This method fills in the blanks that where left
rlm@10 343 * in the bytecode by each forward reference previously added to this label.
rlm@10 344 *
rlm@10 345 * @param owner the code writer that calls this method.
rlm@10 346 * @param position the position of this label in the bytecode.
rlm@10 347 * @param data the bytecode of the method.
rlm@10 348 * @return <tt>true</tt> if a blank that was left for this label was to
rlm@10 349 * small to store the offset. In such a case the corresponding jump
rlm@10 350 * instruction is replaced with a pseudo instruction (using unused
rlm@10 351 * opcodes) using an unsigned two bytes offset. These pseudo
rlm@10 352 * instructions will need to be replaced with true instructions with
rlm@10 353 * wider offsets (4 bytes instead of 2). This is done in
rlm@10 354 * {@link MethodWriter#resizeInstructions}.
rlm@10 355 * @throws IllegalArgumentException if this label has already been resolved,
rlm@10 356 * or if it has not been created by the given code writer.
rlm@10 357 */
rlm@10 358 boolean resolve(
rlm@10 359 final MethodWriter owner,
rlm@10 360 final int position,
rlm@10 361 final byte[] data){
rlm@10 362 boolean needUpdate = false;
rlm@10 363 this.status |= RESOLVED;
rlm@10 364 this.position = position;
rlm@10 365 int i = 0;
rlm@10 366 while(i < referenceCount)
rlm@10 367 {
rlm@10 368 int source = srcAndRefPositions[i++];
rlm@10 369 int reference = srcAndRefPositions[i++];
rlm@10 370 int offset;
rlm@10 371 if(source >= 0)
rlm@10 372 {
rlm@10 373 offset = position - source;
rlm@10 374 if(offset < Short.MIN_VALUE || offset > Short.MAX_VALUE)
rlm@10 375 {
rlm@10 376 /*
rlm@10 377 * changes the opcode of the jump instruction, in order to
rlm@10 378 * be able to find it later (see resizeInstructions in
rlm@10 379 * MethodWriter). These temporary opcodes are similar to
rlm@10 380 * jump instruction opcodes, except that the 2 bytes offset
rlm@10 381 * is unsigned (and can therefore represent values from 0 to
rlm@10 382 * 65535, which is sufficient since the size of a method is
rlm@10 383 * limited to 65535 bytes).
rlm@10 384 */
rlm@10 385 int opcode = data[reference - 1] & 0xFF;
rlm@10 386 if(opcode <= Opcodes.JSR)
rlm@10 387 {
rlm@10 388 // changes IFEQ ... JSR to opcodes 202 to 217
rlm@10 389 data[reference - 1] = (byte) (opcode + 49);
rlm@10 390 }
rlm@10 391 else
rlm@10 392 {
rlm@10 393 // changes IFNULL and IFNONNULL to opcodes 218 and 219
rlm@10 394 data[reference - 1] = (byte) (opcode + 20);
rlm@10 395 }
rlm@10 396 needUpdate = true;
rlm@10 397 }
rlm@10 398 data[reference++] = (byte) (offset >>> 8);
rlm@10 399 data[reference] = (byte) offset;
rlm@10 400 }
rlm@10 401 else
rlm@10 402 {
rlm@10 403 offset = position + source + 1;
rlm@10 404 data[reference++] = (byte) (offset >>> 24);
rlm@10 405 data[reference++] = (byte) (offset >>> 16);
rlm@10 406 data[reference++] = (byte) (offset >>> 8);
rlm@10 407 data[reference] = (byte) offset;
rlm@10 408 }
rlm@10 409 }
rlm@10 410 return needUpdate;
rlm@10 411 }
rlm@10 412
rlm@10 413 /**
rlm@10 414 * Returns the first label of the series to which this label belongs. For an
rlm@10 415 * isolated label or for the first label in a series of successive labels,
rlm@10 416 * this method returns the label itself. For other labels it returns the
rlm@10 417 * first label of the series.
rlm@10 418 *
rlm@10 419 * @return the first label of the series to which this label belongs.
rlm@10 420 */
rlm@10 421 Label getFirst(){
rlm@10 422 return frame == null ? this : frame.owner;
rlm@10 423 }
rlm@10 424
rlm@10 425 // ------------------------------------------------------------------------
rlm@10 426 // Overriden Object methods
rlm@10 427 // ------------------------------------------------------------------------
rlm@10 428
rlm@10 429 /**
rlm@10 430 * Returns a string representation of this label.
rlm@10 431 *
rlm@10 432 * @return a string representation of this label.
rlm@10 433 */
rlm@10 434 public String toString(){
rlm@10 435 return "L" + System.identityHashCode(this);
rlm@10 436 }
rlm@10 437 }