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