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