View Javadoc
1   /*
2    * Copyright (c) 2005, 2009, Oracle and/or its affiliates. All rights reserved.
3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4    *
5    * This code is free software; you can redistribute it and/or modify it
6    * under the terms of the GNU General Public License version 2 only, as
7    * published by the Free Software Foundation.  Oracle designates this
8    * particular file as subject to the "Classpath" exception as provided
9    * by Oracle in the LICENSE file that accompanied this code.
10   *
11   * This code is distributed in the hope that it will be useful, but WITHOUT
12   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14   * version 2 for more details (a copy is included in the LICENSE file that
15   * accompanied this code).
16   *
17   * You should have received a copy of the GNU General Public License version
18   * 2 along with this work; if not, write to the Free Software Foundation,
19   * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20   *
21   * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22   * or visit www.oracle.com if you need additional information or have any
23   * questions.
24   */
25  
26  /*
27   * This file is available under and governed by the GNU General Public
28   * License version 2 only, as published by the Free Software Foundation.
29   * However, the following notice accompanied the original version of this
30   * file:
31   *
32   * ASM: a very small and fast Java bytecode manipulation framework
33   * Copyright (c) 2000-2007 INRIA, France Telecom
34   * All rights reserved.
35   *
36   * Redistribution and use in source and binary forms, with or without
37   * modification, are permitted provided that the following conditions
38   * are met:
39   * 1. Redistributions of source code must retain the above copyright
40   *    notice, this list of conditions and the following disclaimer.
41   * 2. Redistributions in binary form must reproduce the above copyright
42   *    notice, this list of conditions and the following disclaimer in the
43   *    documentation and/or other materials provided with the distribution.
44   * 3. Neither the name of the copyright holders nor the names of its
45   *    contributors may be used to endorse or promote products derived from
46   *    this software without specific prior written permission.
47   *
48   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
49   * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
50   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
51   * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
52   * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
53   * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
54   * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
55   * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
56   * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
57   * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
58   * THE POSSIBILITY OF SUCH DAMAGE.
59   */
60  package com.sun.xml.internal.ws.org.objectweb.asm;
61  
62  /**
63   * A label represents a position in the bytecode of a method. Labels are used
64   * for jump, goto, and switch instructions, and for try catch blocks.
65   *
66   * @author Eric Bruneton
67   */
68  public class Label {
69  
70      /**
71       * Indicates if this label is only used for debug attributes. Such a label
72       * is not the start of a basic block, the target of a jump instruction, or
73       * an exception handler. It can be safely ignored in control flow graph
74       * analysis algorithms (for optimization purposes).
75       */
76      static final int DEBUG = 1;
77  
78      /**
79       * Indicates if the position of this label is known.
80       */
81      static final int RESOLVED = 2;
82  
83      /**
84       * Indicates if this label has been updated, after instruction resizing.
85       */
86      static final int RESIZED = 4;
87  
88      /**
89       * Indicates if this basic block has been pushed in the basic block stack.
90       * See {@link MethodWriter#visitMaxs visitMaxs}.
91       */
92      static final int PUSHED = 8;
93  
94      /**
95       * Indicates if this label is the target of a jump instruction, or the start
96       * of an exception handler.
97       */
98      static final int TARGET = 16;
99  
100     /**
101      * Indicates if a stack map frame must be stored for this label.
102      */
103     static final int STORE = 32;
104 
105     /**
106      * Indicates if this label corresponds to a reachable basic block.
107      */
108     static final int REACHABLE = 64;
109 
110     /**
111      * Indicates if this basic block ends with a JSR instruction.
112      */
113     static final int JSR = 128;
114 
115     /**
116      * Indicates if this basic block ends with a RET instruction.
117      */
118     static final int RET = 256;
119 
120     /**
121      * Indicates if this basic block is the start of a subroutine.
122      */
123     static final int SUBROUTINE = 512;
124 
125     /**
126      * Indicates if this subroutine basic block has been visited.
127      */
128     static final int VISITED = 1024;
129 
130     /**
131      * Field used to associate user information to a label. Warning: this field
132      * is used by the ASM tree package. In order to use it with the ASM tree
133      * package you must override the {@link
134      * com.sun.xml.internal.ws.org.objectweb.asm.tree.MethodNode#getLabelNode} method.
135      */
136     public Object info;
137 
138     /**
139      * Flags that indicate the status of this label.
140      *
141      * @see #DEBUG
142      * @see #RESOLVED
143      * @see #RESIZED
144      * @see #PUSHED
145      * @see #TARGET
146      * @see #STORE
147      * @see #REACHABLE
148      * @see #JSR
149      * @see #RET
150      */
151     int status;
152 
153     /**
154      * The line number corresponding to this label, if known.
155      */
156     int line;
157 
158     /**
159      * The position of this label in the code, if known.
160      */
161     int position;
162 
163     /**
164      * Number of forward references to this label, times two.
165      */
166     private int referenceCount;
167 
168     /**
169      * Informations about forward references. Each forward reference is
170      * described by two consecutive integers in this array: the first one is the
171      * position of the first byte of the bytecode instruction that contains the
172      * forward reference, while the second is the position of the first byte of
173      * the forward reference itself. In fact the sign of the first integer
174      * indicates if this reference uses 2 or 4 bytes, and its absolute value
175      * gives the position of the bytecode instruction. This array is also used
176      * as a bitset to store the subroutines to which a basic block belongs. This
177      * information is needed in {@linked  MethodWriter#visitMaxs}, after all
178      * forward references have been resolved. Hence the same array can be used
179      * for both purposes without problems.
180      */
181     private int[] srcAndRefPositions;
182 
183     // ------------------------------------------------------------------------
184 
185     /*
186      * Fields for the control flow and data flow graph analysis algorithms (used
187      * to compute the maximum stack size or the stack map frames). A control
188      * flow graph contains one node per "basic block", and one edge per "jump"
189      * from one basic block to another. Each node (i.e., each basic block) is
190      * represented by the Label object that corresponds to the first instruction
191      * of this basic block. Each node also stores the list of its successors in
192      * the graph, as a linked list of Edge objects.
193      *
194      * The control flow analysis algorithms used to compute the maximum stack
195      * size or the stack map frames are similar and use two steps. The first
196      * step, during the visit of each instruction, builds information about the
197      * state of the local variables and the operand stack at the end of each
198      * basic block, called the "output frame", <i>relatively</i> to the frame
199      * state at the beginning of the basic block, which is called the "input
200      * frame", and which is <i>unknown</i> during this step. The second step,
201      * in {@link MethodWriter#visitMaxs}, is a fix point algorithm that
202      * computes information about the input frame of each basic block, from the
203      * input state of the first basic block (known from the method signature),
204      * and by the using the previously computed relative output frames.
205      *
206      * The algorithm used to compute the maximum stack size only computes the
207      * relative output and absolute input stack heights, while the algorithm
208      * used to compute stack map frames computes relative output frames and
209      * absolute input frames.
210      */
211 
212     /**
213      * Start of the output stack relatively to the input stack. The exact
214      * semantics of this field depends on the algorithm that is used.
215      *
216      * When only the maximum stack size is computed, this field is the number of
217      * elements in the input stack.
218      *
219      * When the stack map frames are completely computed, this field is the
220      * offset of the first output stack element relatively to the top of the
221      * input stack. This offset is always negative or null. A null offset means
222      * that the output stack must be appended to the input stack. A -n offset
223      * means that the first n output stack elements must replace the top n input
224      * stack elements, and that the other elements must be appended to the input
225      * stack.
226      */
227     int inputStackTop;
228 
229     /**
230      * Maximum height reached by the output stack, relatively to the top of the
231      * input stack. This maximum is always positive or null.
232      */
233     int outputStackMax;
234 
235     /**
236      * Information about the input and output stack map frames of this basic
237      * block. This field is only used when {@link ClassWriter#COMPUTE_FRAMES}
238      * option is used.
239      */
240     Frame frame;
241 
242     /**
243      * The successor of this label, in the order they are visited. This linked
244      * list does not include labels used for debug info only. If
245      * {@link ClassWriter#COMPUTE_FRAMES} option is used then, in addition, it
246      * does not contain successive labels that denote the same bytecode position
247      * (in this case only the first label appears in this list).
248      */
249     Label successor;
250 
251     /**
252      * The successors of this node in the control flow graph. These successors
253      * are stored in a linked list of {@link Edge Edge} objects, linked to each
254      * other by their {@link Edge#next} field.
255      */
256     Edge successors;
257 
258     /**
259      * The next basic block in the basic block stack. This stack is used in the
260      * main loop of the fix point algorithm used in the second step of the
261      * control flow analysis algorithms.
262      *
263      * @see MethodWriter#visitMaxs
264      */
265     Label next;
266 
267     // ------------------------------------------------------------------------
268     // Constructor
269     // ------------------------------------------------------------------------
270 
271     /**
272      * Constructs a new label.
273      */
274     public Label() {
275     }
276 
277     // ------------------------------------------------------------------------
278     // Methods to compute offsets and to manage forward references
279     // ------------------------------------------------------------------------
280 
281     /**
282      * Returns the offset corresponding to this label. This offset is computed
283      * from the start of the method's bytecode. <i>This method is intended for
284      * {@link Attribute} sub classes, and is normally not needed by class
285      * generators or adapters.</i>
286      *
287      * @return the offset corresponding to this label.
288      * @throws IllegalStateException if this label is not resolved yet.
289      */
290     public int getOffset() {
291         if ((status & RESOLVED) == 0) {
292             throw new IllegalStateException("Label offset position has not been resolved yet");
293         }
294         return position;
295     }
296 
297     /**
298      * Puts a reference to this label in the bytecode of a method. If the
299      * position of the label is known, the offset is computed and written
300      * directly. Otherwise, a null offset is written and a new forward reference
301      * is declared for this label.
302      *
303      * @param owner the code writer that calls this method.
304      * @param out the bytecode of the method.
305      * @param source the position of first byte of the bytecode instruction that
306      *        contains this label.
307      * @param wideOffset <tt>true</tt> if the reference must be stored in 4
308      *        bytes, or <tt>false</tt> if it must be stored with 2 bytes.
309      * @throws IllegalArgumentException if this label has not been created by
310      *         the given code writer.
311      */
312     void put(
313         final MethodWriter owner,
314         final ByteVector out,
315         final int source,
316         final boolean wideOffset)
317     {
318         if ((status & RESOLVED) == 0) {
319             if (wideOffset) {
320                 addReference(-1 - source, out.length);
321                 out.putInt(-1);
322             } else {
323                 addReference(source, out.length);
324                 out.putShort(-1);
325             }
326         } else {
327             if (wideOffset) {
328                 out.putInt(position - source);
329             } else {
330                 out.putShort(position - source);
331             }
332         }
333     }
334 
335     /**
336      * Adds a forward reference to this label. This method must be called only
337      * for a true forward reference, i.e. only if this label is not resolved
338      * yet. For backward references, the offset of the reference can be, and
339      * must be, computed and stored directly.
340      *
341      * @param sourcePosition the position of the referencing instruction. This
342      *        position will be used to compute the offset of this forward
343      *        reference.
344      * @param referencePosition the position where the offset for this forward
345      *        reference must be stored.
346      */
347     private void addReference(
348         final int sourcePosition,
349         final int referencePosition)
350     {
351         if (srcAndRefPositions == null) {
352             srcAndRefPositions = new int[6];
353         }
354         if (referenceCount >= srcAndRefPositions.length) {
355             int[] a = new int[srcAndRefPositions.length + 6];
356             System.arraycopy(srcAndRefPositions,
357                     0,
358                     a,
359                     0,
360                     srcAndRefPositions.length);
361             srcAndRefPositions = a;
362         }
363         srcAndRefPositions[referenceCount++] = sourcePosition;
364         srcAndRefPositions[referenceCount++] = referencePosition;
365     }
366 
367     /**
368      * Resolves all forward references to this label. This method must be called
369      * when this label is added to the bytecode of the method, i.e. when its
370      * position becomes known. This method fills in the blanks that where left
371      * in the bytecode by each forward reference previously added to this label.
372      *
373      * @param owner the code writer that calls this method.
374      * @param position the position of this label in the bytecode.
375      * @param data the bytecode of the method.
376      * @return <tt>true</tt> if a blank that was left for this label was to
377      *         small to store the offset. In such a case the corresponding jump
378      *         instruction is replaced with a pseudo instruction (using unused
379      *         opcodes) using an unsigned two bytes offset. These pseudo
380      *         instructions will need to be replaced with true instructions with
381      *         wider offsets (4 bytes instead of 2). This is done in
382      *         {@link MethodWriter#resizeInstructions}.
383      * @throws IllegalArgumentException if this label has already been resolved,
384      *         or if it has not been created by the given code writer.
385      */
386     boolean resolve(
387         final MethodWriter owner,
388         final int position,
389         final byte[] data)
390     {
391         boolean needUpdate = false;
392         this.status |= RESOLVED;
393         this.position = position;
394         int i = 0;
395         while (i < referenceCount) {
396             int source = srcAndRefPositions[i++];
397             int reference = srcAndRefPositions[i++];
398             int offset;
399             if (source >= 0) {
400                 offset = position - source;
401                 if (offset < Short.MIN_VALUE || offset > Short.MAX_VALUE) {
402                     /*
403                      * changes the opcode of the jump instruction, in order to
404                      * be able to find it later (see resizeInstructions in
405                      * MethodWriter). These temporary opcodes are similar to
406                      * jump instruction opcodes, except that the 2 bytes offset
407                      * is unsigned (and can therefore represent values from 0 to
408                      * 65535, which is sufficient since the size of a method is
409                      * limited to 65535 bytes).
410                      */
411                     int opcode = data[reference - 1] & 0xFF;
412                     if (opcode <= Opcodes.JSR) {
413                         // changes IFEQ ... JSR to opcodes 202 to 217
414                         data[reference - 1] = (byte) (opcode + 49);
415                     } else {
416                         // changes IFNULL and IFNONNULL to opcodes 218 and 219
417                         data[reference - 1] = (byte) (opcode + 20);
418                     }
419                     needUpdate = true;
420                 }
421                 data[reference++] = (byte) (offset >>> 8);
422                 data[reference] = (byte) offset;
423             } else {
424                 offset = position + source + 1;
425                 data[reference++] = (byte) (offset >>> 24);
426                 data[reference++] = (byte) (offset >>> 16);
427                 data[reference++] = (byte) (offset >>> 8);
428                 data[reference] = (byte) offset;
429             }
430         }
431         return needUpdate;
432     }
433 
434     /**
435      * Returns the first label of the series to which this label belongs. For an
436      * isolated label or for the first label in a series of successive labels,
437      * this method returns the label itself. For other labels it returns the
438      * first label of the series.
439      *
440      * @return the first label of the series to which this label belongs.
441      */
442     Label getFirst() {
443         return !ClassReader.FRAMES || frame == null ? this : frame.owner;
444     }
445 
446     // ------------------------------------------------------------------------
447     // Methods related to subroutines
448     // ------------------------------------------------------------------------
449 
450     /**
451      * Returns true is this basic block belongs to the given subroutine.
452      *
453      * @param id a subroutine id.
454      * @return true is this basic block belongs to the given subroutine.
455      */
456     boolean inSubroutine(final long id) {
457         if ((status & Label.VISITED) != 0) {
458             return (srcAndRefPositions[(int) (id >>> 32)] & (int) id) != 0;
459         }
460         return false;
461     }
462 
463     /**
464      * Returns true if this basic block and the given one belong to a common
465      * subroutine.
466      *
467      * @param block another basic block.
468      * @return true if this basic block and the given one belong to a common
469      *         subroutine.
470      */
471     boolean inSameSubroutine(final Label block) {
472         for (int i = 0; i < srcAndRefPositions.length; ++i) {
473             if ((srcAndRefPositions[i] & block.srcAndRefPositions[i]) != 0) {
474                 return true;
475             }
476         }
477         return false;
478     }
479 
480     /**
481      * Marks this basic block as belonging to the given subroutine.
482      *
483      * @param id a subroutine id.
484      * @param nbSubroutines the total number of subroutines in the method.
485      */
486     void addToSubroutine(final long id, final int nbSubroutines) {
487         if ((status & VISITED) == 0) {
488             status |= VISITED;
489             srcAndRefPositions = new int[(nbSubroutines - 1) / 32 + 1];
490         }
491         srcAndRefPositions[(int) (id >>> 32)] |= (int) id;
492     }
493 
494     /**
495      * Finds the basic blocks that belong to a given subroutine, and marks these
496      * blocks as belonging to this subroutine. This recursive method follows the
497      * control flow graph to find all the blocks that are reachable from the
498      * current block WITHOUT following any JSR target.
499      *
500      * @param JSR a JSR block that jumps to this subroutine. If this JSR is not
501      *        null it is added to the successor of the RET blocks found in the
502      *        subroutine.
503      * @param id the id of this subroutine.
504      * @param nbSubroutines the total number of subroutines in the method.
505      */
506     void visitSubroutine(final Label JSR, final long id, final int nbSubroutines)
507     {
508         if (JSR != null) {
509             if ((status & VISITED) != 0) {
510                 return;
511             }
512             status |= VISITED;
513             // adds JSR to the successors of this block, if it is a RET block
514             if ((status & RET) != 0) {
515                 if (!inSameSubroutine(JSR)) {
516                     Edge e = new Edge();
517                     e.info = inputStackTop;
518                     e.successor = JSR.successors.successor;
519                     e.next = successors;
520                     successors = e;
521                 }
522             }
523         } else {
524             // if this block already belongs to subroutine 'id', returns
525             if (inSubroutine(id)) {
526                 return;
527             }
528             // marks this block as belonging to subroutine 'id'
529             addToSubroutine(id, nbSubroutines);
530         }
531         // calls this method recursively on each successor, except JSR targets
532         Edge e = successors;
533         while (e != null) {
534             // if this block is a JSR block, then 'successors.next' leads
535             // to the JSR target (see {@link #visitJumpInsn}) and must therefore
536             // not be followed
537             if ((status & Label.JSR) == 0 || e != successors.next) {
538                 e.successor.visitSubroutine(JSR, id, nbSubroutines);
539             }
540             e = e.next;
541         }
542     }
543 
544     // ------------------------------------------------------------------------
545     // Overriden Object methods
546     // ------------------------------------------------------------------------
547 
548     /**
549      * Returns a string representation of this label.
550      *
551      * @return a string representation of this label.
552      */
553     public String toString() {
554         return "L" + System.identityHashCode(this);
555     }
556 }