001: /***
002: * ASM: a very small and fast Java bytecode manipulation framework
003: * Copyright (c) 2000-2005 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: */package com.tc.asm;
030:
031: /**
032: * A label represents a position in the bytecode of a method. Labels are used
033: * for jump, goto, and switch instructions, and for try catch blocks.
034: *
035: * @author Eric Bruneton
036: */
037: public class Label {
038:
039: /**
040: * Indicates if this label is only used for debug attributes. Such a label
041: * is not the start of a basic block, the target of a jump instruction, or
042: * an exception handler. It can be safely ignored in control flow graph
043: * analysis algorithms (for optimization purposes).
044: */
045: final static int DEBUG = 1;
046:
047: /**
048: * Indicates if the position of this label is known.
049: */
050: final static int RESOLVED = 2;
051:
052: /**
053: * Indicates if this label has been updated, after instruction resizing.
054: */
055: final static int RESIZED = 4;
056:
057: /**
058: * Indicates if this basic block has been pushed in the basic block stack.
059: * See {@link MethodWriter#visitMaxs visitMaxs}.
060: */
061: final static int PUSHED = 8;
062:
063: /**
064: * Indicates if this label is the target of a jump instruction, or the start
065: * of an exception handler.
066: */
067: final static int TARGET = 16;
068:
069: /**
070: * Indicates if a stack map frame must be stored for this label.
071: */
072: final static int STORE = 32;
073:
074: /**
075: * Indicates if this label corresponds to a reachable basic block.
076: */
077: final static int REACHABLE = 64;
078:
079: /**
080: * Indicates if this basic block ends with a JSR instruction.
081: */
082: final static int JSR = 128;
083:
084: /**
085: * Indicates if this basic block ends with a RET instruction.
086: */
087: final static int RET = 256;
088:
089: /**
090: * Field used to associate user information to a label.
091: */
092: public Object info;
093:
094: /**
095: * Flags that indicate the status of this label.
096: *
097: * @see #DEBUG
098: * @see #RESOLVED
099: * @see #RESIZED
100: * @see #PUSHED
101: * @see #TARGET
102: * @see #STORE
103: * @see #REACHABLE
104: * @see #JSR
105: * @see #RET
106: */
107: int status;
108:
109: /**
110: * The line number corresponding to this label, if known.
111: */
112: int line;
113:
114: /**
115: * The position of this label in the code, if known.
116: */
117: int position;
118:
119: /**
120: * Number of forward references to this label, times two.
121: */
122: private int referenceCount;
123:
124: /**
125: * Informations about forward references. Each forward reference is
126: * described by two consecutive integers in this array: the first one is the
127: * position of the first byte of the bytecode instruction that contains the
128: * forward reference, while the second is the position of the first byte of
129: * the forward reference itself. In fact the sign of the first integer
130: * indicates if this reference uses 2 or 4 bytes, and its absolute value
131: * gives the position of the bytecode instruction.
132: */
133: private int[] srcAndRefPositions;
134:
135: // ------------------------------------------------------------------------
136:
137: /*
138: * Fields for the control flow and data flow graph analysis algorithms (used
139: * to compute the maximum stack size or the stack map frames). A control
140: * flow graph contains one node per "basic block", and one edge per "jump"
141: * from one basic block to another. Each node (i.e., each basic block) is
142: * represented by the Label object that corresponds to the first instruction
143: * of this basic block. Each node also stores the list of its successors in
144: * the graph, as a linked list of Edge objects.
145: *
146: * The control flow analysis algorithms used to compute the maximum stack
147: * size or the stack map frames are similar and use two steps. The first
148: * step, during the visit of each instruction, builds information about the
149: * state of the local variables and the operand stack at the end of each
150: * basic block, called the "output frame", <i>relatively</i> to the frame
151: * state at the beginning of the basic block, which is called the "input
152: * frame", and which is <i>unknown</i> during this step. The second step,
153: * in {@link MethodWriter#visitMaxs}, is a fix point algorithm that
154: * computes information about the input frame of each basic block, from the
155: * input state of the first basic block (known from the method signature),
156: * and by the using the previously computed relative output frames.
157: *
158: * The algorithm used to compute the maximum stack size only computes the
159: * relative output and absolute input stack heights, while the algorithm
160: * used to compute stack map frames computes relative output frames and
161: * absolute input frames.
162: */
163:
164: /**
165: * Start of the output stack relatively to the input stack. The exact
166: * semantics of this field depends on the algorithm that is used.
167: *
168: * When only the maximum stack size is computed, this field is the number of
169: * elements in the input stack.
170: *
171: * When the stack map frames are completely computed, this field is the
172: * offset of the first output stack element relatively to the top of the
173: * input stack. This offset is always negative or null. A null offset means
174: * that the output stack must be appended to the input stack. A -n offset
175: * means that the first n output stack elements must replace the top n input
176: * stack elements, and that the other elements must be appended to the input
177: * stack.
178: */
179: int inputStackTop;
180:
181: /**
182: * Maximum height reached by the output stack, relatively to the top of the
183: * input stack. This maximum is always positive or null.
184: */
185: int outputStackMax;
186:
187: /**
188: * Information about the input and output stack map frames of this basic
189: * block. This field is only used when {@link ClassWriter#COMPUTE_FRAMES}
190: * option is used.
191: */
192: Frame frame;
193:
194: /**
195: * The successor of this label, in the order they are visited. This linked
196: * list does not include labels used for debug info only. If
197: * {@link ClassWriter#COMPUTE_FRAMES} option is used then, in addition, it
198: * does not contain successive labels that denote the same bytecode position
199: * (in this case only the first label appears in this list).
200: */
201: Label successor;
202:
203: /**
204: * The successors of this node in the control flow graph. These successors
205: * are stored in a linked list of {@link Edge Edge} objects, linked to each
206: * other by their {@link Edge#next} field.
207: */
208: Edge successors;
209:
210: /**
211: * The next basic block in the basic block stack. This stack is used in the
212: * main loop of the fix point algorithm used in the second step of the
213: * control flow analysis algorithms.
214: *
215: * @see MethodWriter#visitMaxs
216: */
217: Label next;
218:
219: // ------------------------------------------------------------------------
220: // Constructor
221: // ------------------------------------------------------------------------
222:
223: /**
224: * Constructs a new label.
225: */
226: public Label() {
227: }
228:
229: /**
230: * Constructs a new label.
231: *
232: * @param debug if this label is only used for debug attributes.
233: */
234: Label(final boolean debug) {
235: this .status = debug ? DEBUG : 0;
236: }
237:
238: // ------------------------------------------------------------------------
239: // Methods to compute offsets and to manage forward references
240: // ------------------------------------------------------------------------
241:
242: /**
243: * Returns the offset corresponding to this label. This offset is computed
244: * from the start of the method's bytecode. <i>This method is intended for
245: * {@link Attribute} sub classes, and is normally not needed by class
246: * generators or adapters.</i>
247: *
248: * @return the offset corresponding to this label.
249: * @throws IllegalStateException if this label is not resolved yet.
250: */
251: public int getOffset() {
252: if ((status & RESOLVED) == 0) {
253: throw new IllegalStateException(
254: "Label offset position has not been resolved yet");
255: }
256: return position;
257: }
258:
259: /**
260: * Puts a reference to this label in the bytecode of a method. If the
261: * position of the label is known, the offset is computed and written
262: * directly. Otherwise, a null offset is written and a new forward reference
263: * is declared for this label.
264: *
265: * @param owner the code writer that calls this method.
266: * @param out the bytecode of the method.
267: * @param source the position of first byte of the bytecode instruction that
268: * contains this label.
269: * @param wideOffset <tt>true</tt> if the reference must be stored in 4
270: * bytes, or <tt>false</tt> if it must be stored with 2 bytes.
271: * @throws IllegalArgumentException if this label has not been created by
272: * the given code writer.
273: */
274: void put(final MethodWriter owner, final ByteVector out,
275: final int source, final boolean wideOffset) {
276: if ((status & RESOLVED) != 0) {
277: if (wideOffset) {
278: out.putInt(position - source);
279: } else {
280: out.putShort(position - source);
281: }
282: } else {
283: if (wideOffset) {
284: addReference(-1 - source, out.length);
285: out.putInt(-1);
286: } else {
287: addReference(source, out.length);
288: out.putShort(-1);
289: }
290: }
291: }
292:
293: /**
294: * Adds a forward reference to this label. This method must be called only
295: * for a true forward reference, i.e. only if this label is not resolved
296: * yet. For backward references, the offset of the reference can be, and
297: * must be, computed and stored directly.
298: *
299: * @param sourcePosition the position of the referencing instruction. This
300: * position will be used to compute the offset of this forward
301: * reference.
302: * @param referencePosition the position where the offset for this forward
303: * reference must be stored.
304: */
305: private void addReference(final int sourcePosition,
306: final int referencePosition) {
307: if (srcAndRefPositions == null) {
308: srcAndRefPositions = new int[6];
309: }
310: if (referenceCount >= srcAndRefPositions.length) {
311: int[] a = new int[srcAndRefPositions.length + 6];
312: System.arraycopy(srcAndRefPositions, 0, a, 0,
313: srcAndRefPositions.length);
314: srcAndRefPositions = a;
315: }
316: srcAndRefPositions[referenceCount++] = sourcePosition;
317: srcAndRefPositions[referenceCount++] = referencePosition;
318: }
319:
320: /**
321: * Resolves all forward references to this label. This method must be called
322: * when this label is added to the bytecode of the method, i.e. when its
323: * position becomes known. This method fills in the blanks that where left
324: * in the bytecode by each forward reference previously added to this label.
325: *
326: * @param owner the code writer that calls this method.
327: * @param position the position of this label in the bytecode.
328: * @param data the bytecode of the method.
329: * @return <tt>true</tt> if a blank that was left for this label was to
330: * small to store the offset. In such a case the corresponding jump
331: * instruction is replaced with a pseudo instruction (using unused
332: * opcodes) using an unsigned two bytes offset. These pseudo
333: * instructions will need to be replaced with true instructions with
334: * wider offsets (4 bytes instead of 2). This is done in
335: * {@link MethodWriter#resizeInstructions}.
336: * @throws IllegalArgumentException if this label has already been resolved,
337: * or if it has not been created by the given code writer.
338: */
339: boolean resolve(final MethodWriter owner, final int position,
340: final byte[] data) {
341: boolean needUpdate = false;
342: this .status |= RESOLVED;
343: this .position = position;
344: int i = 0;
345: while (i < referenceCount) {
346: int source = srcAndRefPositions[i++];
347: int reference = srcAndRefPositions[i++];
348: int offset;
349: if (source >= 0) {
350: offset = position - source;
351: if (offset < Short.MIN_VALUE
352: || offset > Short.MAX_VALUE) {
353: /*
354: * changes the opcode of the jump instruction, in order to
355: * be able to find it later (see resizeInstructions in
356: * MethodWriter). These temporary opcodes are similar to
357: * jump instruction opcodes, except that the 2 bytes offset
358: * is unsigned (and can therefore represent values from 0 to
359: * 65535, which is sufficient since the size of a method is
360: * limited to 65535 bytes).
361: */
362: int opcode = data[reference - 1] & 0xFF;
363: if (opcode <= Opcodes.JSR) {
364: // changes IFEQ ... JSR to opcodes 202 to 217
365: data[reference - 1] = (byte) (opcode + 49);
366: } else {
367: // changes IFNULL and IFNONNULL to opcodes 218 and 219
368: data[reference - 1] = (byte) (opcode + 20);
369: }
370: needUpdate = true;
371: }
372: data[reference++] = (byte) (offset >>> 8);
373: data[reference] = (byte) offset;
374: } else {
375: offset = position + source + 1;
376: data[reference++] = (byte) (offset >>> 24);
377: data[reference++] = (byte) (offset >>> 16);
378: data[reference++] = (byte) (offset >>> 8);
379: data[reference] = (byte) offset;
380: }
381: }
382: return needUpdate;
383: }
384:
385: /**
386: * Returns the first label of the series to which this label belongs. For an
387: * isolated label or for the first label in a series of successive labels,
388: * this method returns the label itself. For other labels it returns the
389: * first label of the series.
390: *
391: * @return the first label of the series to which this label belongs.
392: */
393: Label getFirst() {
394: return frame == null ? this : frame.owner;
395: }
396:
397: // ------------------------------------------------------------------------
398: // Overriden Object methods
399: // ------------------------------------------------------------------------
400:
401: /**
402: * Returns a string representation of this label.
403: *
404: * @return a string representation of this label.
405: */
406: public String toString() {
407: return "L" + System.identityHashCode(this);
408: }
409: }
|