Frame


1   /***
2    * ASM: a very small and fast Java bytecode manipulation framework
3    * Copyright (c) 2000-2005 INRIA, France Telecom
4    * All rights reserved.
5    *
6    * Redistribution and use in source and binary forms, with or without
7    * modification, are permitted provided that the following conditions
8    * are met:
9    * 1. Redistributions of source code must retain the above copyright
10   *    notice, this list of conditions and the following disclaimer.
11   * 2. Redistributions in binary form must reproduce the above copyright
12   *    notice, this list of conditions and the following disclaimer in the
13   *    documentation and/or other materials provided with the distribution.
14   * 3. Neither the name of the copyright holders nor the names of its
15   *    contributors may be used to endorse or promote products derived from
16   *    this software without specific prior written permission.
17   *
18   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19   * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21   * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
22   * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23   * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24   * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25   * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26   * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27   * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
28   * THE POSSIBILITY OF SUCH DAMAGE.
29   */
30  package org.objectweb.asm;
31  
32  /**
33   * Information about the input and output stack map frames of a basic block.
34   * 
35   * @author Eric Bruneton
36   */
37  final class Frame {
38  
39      /*
40       * Frames are computed in a two steps process: during the visit of each
41       * instruction, the state of the frame at the end of current basic block is
42       * updated by simulating the action of the instruction on the previous state
43       * of this so called "output frame". In visitMaxs, a fix point algorithm is
44       * used to compute the "input frame" of each basic block, i.e. the stack map
45       * frame at the begining of the basic block, starting from the input frame
46       * of the first basic block (which is computed from the method descriptor),
47       * and by using the previously computed output frames to compute the input
48       * state of the other blocks.
49       * 
50       * All output and input frames are stored as arrays of integers. Reference
51       * and array types are represented by an index into a type table (which is
52       * not the same as the constant pool of the class, in order to avoid adding
53       * unnecessary constants in the pool - not all computed frames will end up
54       * being stored in the stack map table). This allows very fast type
55       * comparisons.
56       * 
57       * Output stack map frames are computed relatively to the input frame of the
58       * basic block, which is not yet known when output frames are computed. It
59       * is therefore necessary to be able to represent abstract types such as
60       * "the type at position x in the input frame locals" or "the type at
61       * position x from the top of the input frame stack" or even "the type at
62       * position x in the input frame, with y more (or less) array dimensions".
63       * This explains the rather complicated type format used in output frames.
64       * 
65       * This format is the following: DIM KIND VALUE (4, 4 and 24 bits). DIM is a
66       * signed number of array dimensions (from -8 to 7). KIND is either BASE,
67       * LOCAL or STACK. BASE is used for types that are not relative to the input
68       * frame. LOCAL is used for types that are relative to the input local
69       * variable types. STACK is used for types that are relative to the input
70       * stack types. VALUE depends on KIND. For LOCAL types, it is an index in
71       * the input local variable types. For STACK types, it is a position
72       * relatively to the top of input frame stack. For BASE types, it is either
73       * one of the constants defined in FrameVisitor, or for OBJECT and
74       * UNINITIALIZED types, a tag and an index in the type table.
75       * 
76       * Output frames can contain types of any kind and with a positive or
77       * negative dimension (and even unassigned types, represented by 0 - which
78       * does not correspond to any valid type value). Input frames can only
79       * contain BASE types of positive or null dimension. In all cases the type
80       * table contains only internal type names (array type descriptors are
81       * forbidden - dimensions must be represented through the DIM field).
82       * 
83       * The LONG and DOUBLE types are always represented by using two slots (LONG +
84       * TOP or DOUBLE + TOP), for local variable types as well as in the operand
85       * stack. This is necessary to be able to simulate DUPx_y instructions,
86       * whose effect would be dependent on the actual type values if types were
87       * always represented by a single slot in the stack (and this is not
88       * possible, since actual type values are not always known - cf LOCAL and
89       * STACK type kinds).
90       */
91  
92      /**
93       * Mask to get the dimension of a frame type. This dimension is a signed
94       * integer between -8 and 7.
95       */
96      final static int DIM = 0xF0000000;
97  
98      /**
99       * Constant to be added to a type to get a type with one more dimension.
100      */
101     final static int ARRAY_OF = 0x10000000;
102 
103     /**
104      * Constant to be added to a type to get a type with one less dimension.
105      */
106     final static int ELEMENT_OF = 0xF0000000;
107 
108     /**
109      * Mask to get the kind of a frame type.
110      * 
111      * @see #BASE
112      * @see #LOCAL
113      * @see #STACK
114      */
115     final static int KIND = 0xF000000;
116 
117     /**
118      * Mask to get the value of a frame type.
119      */
120     final static int VALUE = 0xFFFFFF;
121 
122     /**
123      * Mask to get the kind of base types.
124      */
125     final static int BASE_KIND = 0xFF00000;
126 
127     /**
128      * Mask to get the value of base types.
129      */
130     final static int BASE_VALUE = 0xFFFFF;
131 
132     /**
133      * Kind of the types that are not relative to an input stack map frame.
134      */
135     final static int BASE = 0x1000000;
136 
137     /**
138      * Base kind of the base reference types. The BASE_VALUE of such types is an
139      * index into the type table.
140      */
141     final static int OBJECT = BASE | 0x700000;
142 
143     /**
144      * Base kind of the uninitialized base types. The BASE_VALUE of such types
145      * in an index into the type table (the Item at that index contains both an
146      * instruction offset and an internal class name).
147      */
148     final static int UNINITIALIZED = BASE | 0x800000;
149 
150     /**
151      * Kind of the types that are relative to the local variable types of an
152      * input stack map frame. The value of such types is a local variable index.
153      */
154     private final static int LOCAL = 0x2000000;
155 
156     /**
157      * Kind of the the types that are relative to the stack of an input stack
158      * map frame. The value of such types is a position relatively to the top of
159      * this stack.
160      */
161     private final static int STACK = 0x3000000;
162 
163     /**
164      * The TOP type. This is a BASE type.
165      */
166     final static int TOP = BASE | 0;
167 
168     /**
169      * The BOOLEAN type. This is a BASE type mainly used for array types.
170      */
171     final static int BOOLEAN = BASE | 9;
172 
173     /**
174      * The BYTE type. This is a BASE type mainly used for array types.
175      */
176     final static int BYTE = BASE | 10;
177 
178     /**
179      * The CHAR type. This is a BASE type mainly used for array types.
180      */
181     final static int CHAR = BASE | 11;
182 
183     /**
184      * The SHORT type. This is a BASE type mainly used for array types.
185      */
186     final static int SHORT = BASE | 12;
187 
188     /**
189      * The INTEGER type. This is a BASE type.
190      */
191     final static int INTEGER = BASE | 1;
192 
193     /**
194      * The FLOAT type. This is a BASE type.
195      */
196     final static int FLOAT = BASE | 2;
197 
198     /**
199      * The DOUBLE type. This is a BASE type.
200      */
201     final static int DOUBLE = BASE | 3;
202 
203     /**
204      * The LONG type. This is a BASE type.
205      */
206     final static int LONG = BASE | 4;
207 
208     /**
209      * The NULL type. This is a BASE type.
210      */
211     final static int NULL = BASE | 5;
212 
213     /**
214      * The UNINITIALIZED_THIS type. This is a BASE type.
215      */
216     final static int UNINITIALIZED_THIS = BASE | 6;
217 
218     /**
219      * The stack size variation corresponding to each JVM instruction. This
220      * stack variation is equal to the size of the values produced by an
221      * instruction, minus the size of the values consumed by this instruction.
222      */
223     final static int[] SIZE;
224 
225     /**
226      * Computes the stack size variation corresponding to each JVM instruction.
227      */
228     static {
229         int i;
230         int[] b = new int[202];
231         String   s = "EFFFFFFFFGGFFFGGFFFEEFGFGFEEEEEEEEEEEEEEEEEEEEDEDEDDDDD"
232                 + "CDCDEEEEEEEEEEEEEEEEEEEEBABABBBBDCFFFGGGEDCDCDCDCDCDCDCDCD"
233                 + "CDCEEEEDDDDDDDCDCDCEFEFDDEEFFDEDEEEBDDBBDDDDDDCCCCCCCCEFED"
234                 + "DDCDCDEEEEEEEEEEFEEEEEEDDEEDDEE";
235         for (i = 0; i < b.length; ++i) {
236             b[i] = s.charAt(i) - 'E';
237         }
238         SIZE = b;
239 
240         // code to generate the above string
241         //
242         // int NA = 0; // not applicable (unused opcode or variable size opcode)
243         //
244         // b = new int[] {
245         // 0, //NOP, // visitInsn
246         // 1, //ACONST_NULL, // -
247         // 1, //ICONST_M1, // -
248         // 1, //ICONST_0, // -
249         // 1, //ICONST_1, // -
250         // 1, //ICONST_2, // -
251         // 1, //ICONST_3, // -
252         // 1, //ICONST_4, // -
253         // 1, //ICONST_5, // -
254         // 2, //LCONST_0, // -
255         // 2, //LCONST_1, // -
256         // 1, //FCONST_0, // -
257         // 1, //FCONST_1, // -
258         // 1, //FCONST_2, // -
259         // 2, //DCONST_0, // -
260         // 2, //DCONST_1, // -
261         // 1, //BIPUSH, // visitIntInsn
262         // 1, //SIPUSH, // -
263         // 1, //LDC, // visitLdcInsn
264         // NA, //LDC_W, // -
265         // NA, //LDC2_W, // -
266         // 1, //ILOAD, // visitVarInsn
267         // 2, //LLOAD, // -
268         // 1, //FLOAD, // -
269         // 2, //DLOAD, // -
270         // 1, //ALOAD, // -
271         // NA, //ILOAD_0, // -
272         // NA, //ILOAD_1, // -
273         // NA, //ILOAD_2, // -
274         // NA, //ILOAD_3, // -
275         // NA, //LLOAD_0, // -
276         // NA, //LLOAD_1, // -
277         // NA, //LLOAD_2, // -
278         // NA, //LLOAD_3, // -
279         // NA, //FLOAD_0, // -
280         // NA, //FLOAD_1, // -
281         // NA, //FLOAD_2, // -
282         // NA, //FLOAD_3, // -
283         // NA, //DLOAD_0, // -
284         // NA, //DLOAD_1, // -
285         // NA, //DLOAD_2, // -
286         // NA, //DLOAD_3, // -
287         // NA, //ALOAD_0, // -
288         // NA, //ALOAD_1, // -
289         // NA, //ALOAD_2, // -
290         // NA, //ALOAD_3, // -
291         // -1, //IALOAD, // visitInsn
292         // 0, //LALOAD, // -
293         // -1, //FALOAD, // -
294         // 0, //DALOAD, // -
295         // -1, //AALOAD, // -
296         // -1, //BALOAD, // -
297         // -1, //CALOAD, // -
298         // -1, //SALOAD, // -
299         // -1, //ISTORE, // visitVarInsn
300         // -2, //LSTORE, // -
301         // -1, //FSTORE, // -
302         // -2, //DSTORE, // -
303         // -1, //ASTORE, // -
304         // NA, //ISTORE_0, // -
305         // NA, //ISTORE_1, // -
306         // NA, //ISTORE_2, // -
307         // NA, //ISTORE_3, // -
308         // NA, //LSTORE_0, // -
309         // NA, //LSTORE_1, // -
310         // NA, //LSTORE_2, // -
311         // NA, //LSTORE_3, // -
312         // NA, //FSTORE_0, // -
313         // NA, //FSTORE_1, // -
314         // NA, //FSTORE_2, // -
315         // NA, //FSTORE_3, // -
316         // NA, //DSTORE_0, // -
317         // NA, //DSTORE_1, // -
318         // NA, //DSTORE_2, // -
319         // NA, //DSTORE_3, // -
320         // NA, //ASTORE_0, // -
321         // NA, //ASTORE_1, // -
322         // NA, //ASTORE_2, // -
323         // NA, //ASTORE_3, // -
324         // -3, //IASTORE, // visitInsn
325         // -4, //LASTORE, // -
326         // -3, //FASTORE, // -
327         // -4, //DASTORE, // -
328         // -3, //AASTORE, // -
329         // -3, //BASTORE, // -
330         // -3, //CASTORE, // -
331         // -3, //SASTORE, // -
332         // -1, //POP, // -
333         // -2, //POP2, // -
334         // 1, //DUP, // -
335         // 1, //DUP_X1, // -
336         // 1, //DUP_X2, // -
337         // 2, //DUP2, // -
338         // 2, //DUP2_X1, // -
339         // 2, //DUP2_X2, // -
340         // 0, //SWAP, // -
341         // -1, //IADD, // -
342         // -2, //LADD, // -
343         // -1, //FADD, // -
344         // -2, //DADD, // -
345         // -1, //ISUB, // -
346         // -2, //LSUB, // -
347         // -1, //FSUB, // -
348         // -2, //DSUB, // -
349         // -1, //IMUL, // -
350         // -2, //LMUL, // -
351         // -1, //FMUL, // -
352         // -2, //DMUL, // -
353         // -1, //IDIV, // -
354         // -2, //LDIV, // -
355         // -1, //FDIV, // -
356         // -2, //DDIV, // -
357         // -1, //IREM, // -
358         // -2, //LREM, // -
359         // -1, //FREM, // -
360         // -2, //DREM, // -
361         // 0, //INEG, // -
362         // 0, //LNEG, // -
363         // 0, //FNEG, // -
364         // 0, //DNEG, // -
365         // -1, //ISHL, // -
366         // -1, //LSHL, // -
367         // -1, //ISHR, // -
368         // -1, //LSHR, // -
369         // -1, //IUSHR, // -
370         // -1, //LUSHR, // -
371         // -1, //IAND, // -
372         // -2, //LAND, // -
373         // -1, //IOR, // -
374         // -2, //LOR, // -
375         // -1, //IXOR, // -
376         // -2, //LXOR, // -
377         // 0, //IINC, // visitIincInsn
378         // 1, //I2L, // visitInsn
379         // 0, //I2F, // -
380         // 1, //I2D, // -
381         // -1, //L2I, // -
382         // -1, //L2F, // -
383         // 0, //L2D, // -
384         // 0, //F2I, // -
385         // 1, //F2L, // -
386         // 1, //F2D, // -
387         // -1, //D2I, // -
388         // 0, //D2L, // -
389         // -1, //D2F, // -
390         // 0, //I2B, // -
391         // 0, //I2C, // -
392         // 0, //I2S, // -
393         // -3, //LCMP, // -
394         // -1, //FCMPL, // -
395         // -1, //FCMPG, // -
396         // -3, //DCMPL, // -
397         // -3, //DCMPG, // -
398         // -1, //IFEQ, // visitJumpInsn
399         // -1, //IFNE, // -
400         // -1, //IFLT, // -
401         // -1, //IFGE, // -
402         // -1, //IFGT, // -
403         // -1, //IFLE, // -
404         // -2, //IF_ICMPEQ, // -
405         // -2, //IF_ICMPNE, // -
406         // -2, //IF_ICMPLT, // -
407         // -2, //IF_ICMPGE, // -
408         // -2, //IF_ICMPGT, // -
409         // -2, //IF_ICMPLE, // -
410         // -2, //IF_ACMPEQ, // -
411         // -2, //IF_ACMPNE, // -
412         // 0, //GOTO, // -
413         // 1, //JSR, // -
414         // 0, //RET, // visitVarInsn
415         // -1, //TABLESWITCH, // visiTableSwitchInsn
416         // -1, //LOOKUPSWITCH, // visitLookupSwitch
417         // -1, //IRETURN, // visitInsn
418         // -2, //LRETURN, // -
419         // -1, //FRETURN, // -
420         // -2, //DRETURN, // -
421         // -1, //ARETURN, // -
422         // 0, //RETURN, // -
423         // NA, //GETSTATIC, // visitFieldInsn
424         // NA, //PUTSTATIC, // -
425         // NA, //GETFIELD, // -
426         // NA, //PUTFIELD, // -
427         // NA, //INVOKEVIRTUAL, // visitMethodInsn
428         // NA, //INVOKESPECIAL, // -
429         // NA, //INVOKESTATIC, // -
430         // NA, //INVOKEINTERFACE, // -
431         // NA, //UNUSED, // NOT VISITED
432         // 1, //NEW, // visitTypeInsn
433         // 0, //NEWARRAY, // visitIntInsn
434         // 0, //ANEWARRAY, // visitTypeInsn
435         // 0, //ARRAYLENGTH, // visitInsn
436         // NA, //ATHROW, // -
437         // 0, //CHECKCAST, // visitTypeInsn
438         // 0, //INSTANCEOF, // -
439         // -1, //MONITORENTER, // visitInsn
440         // -1, //MONITOREXIT, // -
441         // NA, //WIDE, // NOT VISITED
442         // NA, //MULTIANEWARRAY, // visitMultiANewArrayInsn
443         // -1, //IFNULL, // visitJumpInsn
444         // -1, //IFNONNULL, // -
445         // NA, //GOTO_W, // -
446         // NA, //JSR_W, // -
447         // };
448         // for (i = 0; i < b.length; ++i) {
449         // System.err.print((char)('E' + b[i]));
450         // }
451         // System.err.println();
452     }
453 
454     /**
455      * The label (i.e. basic block) to which these input and output stack map
456      * frames correspond.
457      */
458     Label owner;
459 
460     /**
461      * The input stack map frame locals.
462      */
463     int[] inputLocals;
464 
465     /**
466      * The input stack map frame stack.
467      */
468     int[] inputStack;
469 
470     /**
471      * The output stack map frame locals.
472      */
473     private int[] outputLocals;
474 
475     /**
476      * The output stack map frame stack.
477      */
478     private int[] outputStack;
479 
480     /**
481      * Relative size of the output stack. The exact semantics of this field
482      * depends on the algorithm that is used.
483      * 
484      * When only the maximum stack size is computed, this field is the size of
485      * the output stack relatively to the top of the input stack.
486      * 
487      * When the stack map frames are completely computed, this field is the
488      * actual number of types in {@link #outputStack}.
489      */
490     private int outputStackTop;
491 
492     /**
493      * Number of types that are initialized in the basic block.
494      * 
495      * @see #initializations
496      */
497     private int initializationCount;
498 
499     /**
500      * The types that are initialized in the basic block. A constructor
501      * invocation on an UNINITIALIZED or UNINITIALIZED_THIS type must replace
502      * <i>every occurence</i> of this type in the local variables and in the
503      * operand stack. This cannot be done during the first phase of the
504      * algorithm since, during this phase, the local variables and the operand
505      * stack are not completely computed. It is therefore necessary to store the
506      * types on which constructors are invoked in the basic block, in order to
507      * do this replacement during the second phase of the algorithm, where the
508      * frames are fully computed. Note that this array can contain types that
509      * are relative to input locals or to the input stack (see below for the
510      * description of the algorithm).
511      */
512     private int[] initializations;
513 
514     /**
515      * Returns the output frame local variable type at the given index.
516      * 
517      * @param local the index of the local that must be returned.
518      * @return the output frame local variable type at the given index.
519      */
520     private int get(final int local) {
521         if (outputLocals == null || local >= outputLocals.length) {
522             // this local has never been assigned in this basic block,
523             // so it is still equal to its value in the input frame
524             return LOCAL | local;
525         } else {
526             int type = outputLocals[local];
527             if (type == 0) {
528                 // this local has never been assigned in this basic block,
529                 // so it is still equal to its value in the input frame
530                 type = outputLocals[local] = LOCAL | local;
531             }
532             return type;
533         }
534     }
535 
536     /**
537      * Sets the output frame local variable type at the given index.
538      * 
539      * @param local the index of the local that must be set.
540      * @param type the value of the local that must be set.
541      */
542     private void set(final int local, final int type) {
543         // creates and/or resizes the output local variables array if necessary
544         if (outputLocals == null) {
545             outputLocals = new int[10];
546         }
547         int n = outputLocals.length;
548         if (local >= n) {
549             int[] t = new int[Math.max(local + 1, 2 * n)];
550             System.arraycopy(outputLocals, 0, t, 0, n);
551             outputLocals = t;
552         }
553         // sets the local variable
554         outputLocals[local] = type;
555     }
556 
557     /**
558      * Pushes a new type onto the output frame stack.
559      * 
560      * @param type the type that must be pushed.
561      */
562     private void push(final int type) {
563         // creates and/or resizes the output stack array if necessary
564         if (outputStack == null) {
565             outputStack = new int[10];
566         }
567         int n = outputStack.length;
568         if (outputStackTop >= n) {
569             int[] t = new int[Math.max(outputStackTop + 1, 2 * n)];
570             System.arraycopy(outputStack, 0, t, 0, n);
571             outputStack = t;
572         }
573         // pushes the type on the output stack
574         outputStack[outputStackTop++] = type;
575         // updates the maximun height reached by the output stack, if needed
576         int top = owner.inputStackTop + outputStackTop;
577         if (top > owner.outputStackMax) {
578             owner.outputStackMax = top;
579         }
580     }
581 
582     /**
583      * Pushes a new type onto the output frame stack.
584      * 
585      * @param cw the ClassWriter to which this label belongs.
586      * @param desc the descriptor of the type to be pushed. Can also be a method
587      *        descriptor (in this case this method pushes its return type onto
588      *        the output frame stack).
589      */
590     private void push(final ClassWriter cw, final String   desc) {
591         int type = type(cw, desc);
592         if (type != 0) {
593             push(type);
594             if (type == LONG || type == DOUBLE) {
595                 push(TOP);
596             }
597         }
598     }
599 
600     /**
601      * Returns the int encoding of the given type.
602      * 
603      * @param cw the ClassWriter to which this label belongs.
604      * @param desc a type descriptor.
605      * @return the int encoding of the given type.
606      */
607     private int type(final ClassWriter cw, final String   desc) {
608         String   t;
609         int index = desc.charAt(0) == '(' ? desc.indexOf(')') + 1 : 0;
610         switch (desc.charAt(index)) {
611             case 'V':
612                 return 0;
613             case 'Z':
614             case 'C':
615             case 'B':
616             case 'S':
617             case 'I':
618                 return INTEGER;
619             case 'F':
620                 return FLOAT;
621             case 'J':
622                 return LONG;
623             case 'D':
624                 return DOUBLE;
625             case 'L':
626                 // stores the internal name, not the descriptor!
627                 t = desc.substring(index + 1, desc.length() - 1);
628                 return OBJECT | cw.addType(t);
629                 // case '[':
630             default:
631                 // extracts the dimensions and the element type
632                 int data;
633                 int dims = index + 1;
634                 while (desc.charAt(dims) == '[') {
635                     ++dims;
636                 }
637                 switch (desc.charAt(dims)) {
638                     case 'Z':
639                         data = BOOLEAN;
640                         break;
641                     case 'C':
642                         data = CHAR;
643                         break;
644                     case 'B':
645                         data = BYTE;
646                         break;
647                     case 'S':
648                         data = SHORT;
649                         break;
650                     case 'I':
651                         data = INTEGER;
652                         break;
653                     case 'F':
654                         data = FLOAT;
655                         break;
656                     case 'J':
657                         data = LONG;
658                         break;
659                     case 'D':
660                         data = DOUBLE;
661                         break;
662                     // case 'L':
663                     default:
664                         // stores the internal name, not the descriptor
665                         t = desc.substring(dims + 1, desc.length() - 1);
666                         data = OBJECT | cw.addType(t);
667                 }
668                 return (dims - index) << 28 | data;
669         }
670     }
671 
672     /**
673      * Pops a type from the output frame stack and returns its value.
674      * 
675      * @return the type that has been popped from the output frame stack.
676      */
677     private int pop() {
678         if (outputStackTop > 0) {
679             return outputStack[--outputStackTop];
680         } else {
681             // if the output frame stack is empty, pops from the input stack
682             return STACK | -(--owner.inputStackTop);
683         }
684     }
685 
686     /**
687      * Pops the given number of types from the output frame stack.
688      * 
689      * @param elements the number of types that must be popped.
690      */
691     private void pop(final int elements) {
692         if (outputStackTop >= elements) {
693             outputStackTop -= elements;
694         } else {
695             // if the number of elements to be popped is greater than the number
696             // of elements in the output stack, clear it, and pops the remaining
697             // elements from the input stack.
698             owner.inputStackTop -= elements - outputStackTop;
699             outputStackTop = 0;
700         }
701     }
702 
703     /**
704      * Pops a type from the output frame stack.
705      * 
706      * @param desc the descriptor of the type to be popped. Can also be a method
707      *        descriptor (in this case this method pops the types corresponding
708      *        to the method arguments).
709      */
710     private void pop(final String   desc) {
711         char c = desc.charAt(0);
712         if (c == '(') {
713             pop((MethodWriter.getArgumentsAndReturnSizes(desc) >> 2) - 1);
714         } else if (c == 'J' || c == 'D') {
715             pop(2);
716         } else {
717             pop(1);
718         }
719     }
720 
721     /**
722      * Adds a new type to the list of types on which a constructor is invoked in
723      * the basic block.
724      * 
725      * @param var a type on a which a constructor is invoked.
726      */
727     private void init(final int var) {
728         // creates and/or resizes the initializations array if necessary
729         if (initializations == null) {
730             initializations = new int[2];
731         }
732         int n = initializations.length;
733         if (initializationCount >= n) {
734             int[] t = new int[Math.max(initializationCount + 1, 2 * n)];
735             System.arraycopy(initializations, 0, t, 0, n);
736             initializations = t;
737         }
738         // stores the type to be initialized
739         initializations[initializationCount++] = var;
740     }
741 
742     /**
743      * Replaces the given type with the appropriate type if it is one of the
744      * types on which a constructor is invoked in the basic block.
745      * 
746      * @param cw the ClassWriter to which this label belongs.
747      * @param t a type
748      * @return t or, if t is one of the types on which a constructor is invoked
749      *         in the basic block, the type corresponding to this constructor.
750      */
751     private int init(final ClassWriter cw, final int t) {
752         int s;
753         if (t == UNINITIALIZED_THIS) {
754             s = OBJECT | cw.addType(cw.thisName);
755         } else if ((t & (DIM | BASE_KIND)) == UNINITIALIZED) {
756             String   type = cw.typeTable[t & BASE_VALUE].strVal1;
757             s = OBJECT | cw.addType(type);
758         } else {
759             return t;
760         }
761         for (int j = 0; j < initializationCount; ++j) {
762             int u = initializations[j];
763             int dim = u & DIM;
764             int kind = u & KIND;
765             if (kind == LOCAL) {
766                 u = dim + inputLocals[u & VALUE];
767             } else if (kind == STACK) {
768                 u = dim + inputStack[inputStack.length - (u & VALUE)];
769             }
770             if (t == u) {
771                 return s;
772             }
773         }
774         return t;
775     }
776 
777     /**
778      * Initializes the input frame of the first basic block from the method
779      * descriptor.
780      * 
781      * @param cw the ClassWriter to which this label belongs.
782      * @param access the access flags of the method to which this label belongs.
783      * @param args the formal parameter types of this method.
784      * @param maxLocals the maximum number of local variables of this method.
785      */
786     void initInputFrame(
787         final ClassWriter cw,
788         final int access,
789         final Type[] args,
790         final int maxLocals)
791     {
792         inputLocals = new int[maxLocals];
793         inputStack = new int[0];
794         int i = 0;
795         if ((access & Opcodes.ACC_STATIC) == 0) {
796             if ((access & MethodWriter.ACC_CONSTRUCTOR) == 0) {
797                 inputLocals[i++] = OBJECT | cw.addType(cw.thisName);
798             } else {
799                 inputLocals[i++] = UNINITIALIZED_THIS;
800             }
801         }
802         for (int j = 0; j < args.length; ++j) {
803             int t = type(cw, args[j].getDescriptor());
804             inputLocals[i++] = t;
805             if (t == LONG || t == DOUBLE) {
806                 inputLocals[i++] = TOP;
807             }
808         }
809         while (i < maxLocals) {
810             inputLocals[i++] = TOP;
811         }
812     }
813 
814     /**
815      * Simulates the action of the given instruction on the output stack frame.
816      * 
817      * @param opcode the opcode of the instruction.
818      * @param arg the operand of the instruction, if any.
819      * @param cw the class writer to which this label belongs.
820      * @param item the operand of the instructions, if any.
821      */
822     void execute(
823         final int opcode,
824         final int arg,
825         final ClassWriter cw,
826         final Item item)
827     {
828         int t1, t2, t3, t4;
829         switch (opcode) {
830             case Opcodes.NOP:
831             case Opcodes.INEG:
832             case Opcodes.LNEG:
833             case Opcodes.FNEG:
834             case Opcodes.DNEG:
835             case Opcodes.I2B:
836             case Opcodes.I2C:
837             case Opcodes.I2S:
838             case Opcodes.GOTO:
839             case Opcodes.RETURN:
840                 break;
841             case Opcodes.ACONST_NULL:
842                 push(NULL);
843                 break;
844             case Opcodes.ICONST_M1:
845             case Opcodes.ICONST_0:
846             case Opcodes.ICONST_1:
847             case Opcodes.ICONST_2:
848             case Opcodes.ICONST_3:
849             case Opcodes.ICONST_4:
850             case Opcodes.ICONST_5:
851             case Opcodes.BIPUSH:
852             case Opcodes.SIPUSH:
853             case Opcodes.ILOAD:
854                 push(INTEGER);
855                 break;
856             case Opcodes.LCONST_0:
857             case Opcodes.LCONST_1:
858             case Opcodes.LLOAD:
859                 push(LONG);
860                 push(TOP);
861                 break;
862             case Opcodes.FCONST_0:
863             case Opcodes.FCONST_1:
864             case Opcodes.FCONST_2:
865             case Opcodes.FLOAD:
866                 push(FLOAT);
867                 break;
868             case Opcodes.DCONST_0:
869             case Opcodes.DCONST_1:
870             case Opcodes.DLOAD:
871                 push(DOUBLE);
872                 push(TOP);
873                 break;
874             case Opcodes.LDC:
875                 switch (item.type) {
876                     case ClassWriter.INT:
877                         push(INTEGER);
878                         break;
879                     case ClassWriter.LONG:
880                         push(LONG);
881                         push(TOP);
882                         break;
883                     case ClassWriter.FLOAT:
884                         push(FLOAT);
885                         break;
886                     case ClassWriter.DOUBLE:
887                         push(DOUBLE);
888                         push(TOP);
889                         break;
890                     case ClassWriter.CLASS:
891                         push(OBJECT | cw.addType("java/lang/Class"));
892                         break;
893                     // case ClassWriter.STR:
894                     default:
895                         push(OBJECT | cw.addType("java/lang/String"));
896                 }
897                 break;
898             case Opcodes.ALOAD:
899                 push(get(arg));
900                 break;
901             case Opcodes.IALOAD:
902             case Opcodes.BALOAD:
903             case Opcodes.CALOAD:
904             case Opcodes.SALOAD:
905                 pop(2);
906                 push(INTEGER);
907                 break;
908             case Opcodes.LALOAD:
909             case Opcodes.D2L:
910                 pop(2);
911                 push(LONG);
912                 push(TOP);
913                 break;
914             case Opcodes.FALOAD:
915                 pop(2);
916                 push(FLOAT);
917                 break;
918             case Opcodes.DALOAD:
919             case Opcodes.L2D:
920                 pop(2);
921                 push(DOUBLE);
922                 push(TOP);
923                 break;
924             case Opcodes.AALOAD:
925                 pop(1);
926                 t1 = pop();
927                 push(ELEMENT_OF + t1);
928                 break;
929             case Opcodes.ISTORE:
930             case Opcodes.FSTORE:
931             case Opcodes.ASTORE:
932                 t1 = pop();
933                 set(arg, t1);
934                 if (arg > 0) {
935                     t2 = get(arg - 1);
936                     // if t2 is of kind STACK or LOCAL we cannot know its size!
937                     if (t2 == LONG || t2 == DOUBLE) {
938                         set(arg - 1, TOP);
939                     }
940                 }
941                 break;
942             case Opcodes.LSTORE:
943             case Opcodes.DSTORE:
944                 pop(1);
945                 t1 = pop();
946                 set(arg, t1);
947                 set(arg + 1, TOP);
948                 if (arg > 0) {
949                     t2 = get(arg - 1);
950                     // if t2 is of kind STACK or LOCAL we cannot know its size!
951                     if (t2 == LONG || t2 == DOUBLE) {
952                         set(arg - 1, TOP);
953                     }
954                 }
955                 break;
956             case Opcodes.IASTORE:
957             case Opcodes.BASTORE:
958             case Opcodes.CASTORE:
959             case Opcodes.SASTORE:
960             case Opcodes.FASTORE:
961             case Opcodes.AASTORE:
962                 pop(3);
963                 break;
964             case Opcodes.LASTORE:
965             case Opcodes.DASTORE:
966                 pop(4);
967                 break;
968             case Opcodes.POP:
969             case Opcodes.IFEQ:
970             case Opcodes.IFNE:
971             case Opcodes.IFLT:
972             case Opcodes.IFGE:
973             case Opcodes.IFGT:
974             case Opcodes.IFLE:
975             case Opcodes.IRETURN:
976             case Opcodes.FRETURN:
977             case Opcodes.ARETURN:
978             case Opcodes.TABLESWITCH:
979             case Opcodes.LOOKUPSWITCH:
980             case Opcodes.ATHROW:
981             case Opcodes.MONITORENTER:
982             case Opcodes.MONITOREXIT:
983             case Opcodes.IFNULL:
984             case Opcodes.IFNONNULL:
985                 pop(1);
986                 break;
987             case Opcodes.POP2:
988             case Opcodes.IF_ICMPEQ:
989             case Opcodes.IF_ICMPNE:
990             case Opcodes.IF_ICMPLT:
991             case Opcodes.IF_ICMPGE:
992             case Opcodes.IF_ICMPGT:
993             case Opcodes.IF_ICMPLE:
994             case Opcodes.IF_ACMPEQ:
995             case Opcodes.IF_ACMPNE:
996             case Opcodes.LRETURN:
997             case Opcodes.DRETURN:
998                 pop(2);
999                 break;
1000            case Opcodes.DUP:
1001                t1 = pop();
1002                push(t1);
1003                push(t1);
1004                break;
1005            case Opcodes.DUP_X1:
1006                t1 = pop();
1007                t2 = pop();
1008                push(t1);
1009                push(t2);
1010                push(t1);
1011                break;
1012            case Opcodes.DUP_X2:
1013                t1 = pop();
1014                t2 = pop();
1015                t3 = pop();
1016                push(t1);
1017                push(t3);
1018                push(t2);
1019                push(t1);
1020                break;
1021            case Opcodes.DUP2:
1022                t1 = pop();
1023                t2 = pop();
1024                push(t2);
1025                push(t1);
1026                push(t2);
1027                push(t1);
1028                break;
1029            case Opcodes.DUP2_X1:
1030                t1 = pop();
1031                t2 = pop();
1032                t3 = pop();
1033                push(t2);
1034                push(t1);
1035                push(t3);
1036                push(t2);
1037                push(t1);
1038                break;
1039            case Opcodes.DUP2_X2:
1040                t1 = pop();
1041                t2 = pop();
1042                t3 = pop();
1043                t4 = pop();
1044                push(t2);
1045                push(t1);
1046                push(t4);
1047                push(t3);
1048                push(t2);
1049                push(t1);
1050                break;
1051            case Opcodes.SWAP:
1052                t1 = pop();
1053                t2 = pop();
1054                push(t1);
1055                push(t2);
1056                break;
1057            case Opcodes.IADD:
1058            case Opcodes.ISUB:
1059            case Opcodes.IMUL:
1060            case Opcodes.IDIV:
1061            case Opcodes.IREM:
1062            case Opcodes.IAND:
1063            case Opcodes.IOR:
1064            case Opcodes.IXOR:
1065            case Opcodes.ISHL:
1066            case Opcodes.ISHR:
1067            case Opcodes.IUSHR:
1068            case Opcodes.L2I:
1069            case Opcodes.D2I:
1070            case Opcodes.FCMPL:
1071            case Opcodes.FCMPG:
1072                pop(2);
1073                push(INTEGER);
1074                break;
1075            case Opcodes.LADD:
1076            case Opcodes.LSUB:
1077            case Opcodes.LMUL:
1078            case Opcodes.LDIV:
1079            case Opcodes.LREM:
1080            case Opcodes.LAND:
1081            case Opcodes.LOR:
1082            case Opcodes.LXOR:
1083                pop(4);
1084                push(LONG);
1085                push(TOP);
1086                break;
1087            case Opcodes.FADD:
1088            case Opcodes.FSUB:
1089            case Opcodes.FMUL:
1090            case Opcodes.FDIV:
1091            case Opcodes.FREM:
1092            case Opcodes.L2F:
1093            case Opcodes.D2F:
1094                pop(2);
1095                push(FLOAT);
1096                break;
1097            case Opcodes.DADD:
1098            case Opcodes.DSUB:
1099            case Opcodes.DMUL:
1100            case Opcodes.DDIV:
1101            case Opcodes.DREM:
1102                pop(4);
1103                push(DOUBLE);
1104                push(TOP);
1105                break;
1106            case Opcodes.LSHL:
1107            case Opcodes.LSHR:
1108            case Opcodes.LUSHR:
1109                pop(3);
1110                push(LONG);
1111                push(TOP);
1112                break;
1113            case Opcodes.IINC:
1114                set(arg, INTEGER);
1115                break;
1116            case Opcodes.I2L:
1117            case Opcodes.F2L:
1118                pop(1);
1119                push(LONG);
1120                push(TOP);
1121                break;
1122            case Opcodes.I2F:
1123                pop(1);
1124                push(FLOAT);
1125                break;
1126            case Opcodes.I2D:
1127            case Opcodes.F2D:
1128                pop(1);
1129                push(DOUBLE);
1130                push(TOP);
1131                break;
1132            case Opcodes.F2I:
1133            case Opcodes.ARRAYLENGTH:
1134            case Opcodes.INSTANCEOF:
1135                pop(1);
1136                push(INTEGER);
1137                break;
1138            case Opcodes.LCMP:
1139            case Opcodes.DCMPL:
1140            case Opcodes.DCMPG:
1141                pop(4);
1142                push(INTEGER);
1143                break;
1144            case Opcodes.JSR:
1145            case Opcodes.RET:
1146                throw new RuntimeException  ("JSR/RET are not supported with computeFrames option");
1147            case Opcodes.GETSTATIC:
1148                push(cw, item.strVal3);
1149                break;
1150            case Opcodes.PUTSTATIC:
1151                pop(item.strVal3);
1152                break;
1153            case Opcodes.GETFIELD:
1154                pop(1);
1155                push(cw, item.strVal3);
1156                break;
1157            case Opcodes.PUTFIELD:
1158                pop(item.strVal3);
1159                pop();
1160                break;
1161            case Opcodes.INVOKEVIRTUAL:
1162            case Opcodes.INVOKESPECIAL:
1163            case Opcodes.INVOKESTATIC:
1164            case Opcodes.INVOKEINTERFACE:
1165                pop(item.strVal3);
1166                if (opcode != Opcodes.INVOKESTATIC) {
1167                    t1 = pop();
1168                    if (opcode == Opcodes.INVOKESPECIAL
1169                            && item.strVal2.charAt(0) == '<')
1170                    {
1171                        init(t1);
1172                    }
1173                }
1174                push(cw, item.strVal3);
1175                break;
1176            case Opcodes.NEW:
1177                push(UNINITIALIZED | cw.addUninitializedType(item.strVal1, arg));
1178                break;
1179            case Opcodes.NEWARRAY:
1180                pop();
1181                switch (arg) {
1182                    case Opcodes.T_BOOLEAN:
1183                        push(ARRAY_OF | BOOLEAN);
1184                        break;
1185                    case Opcodes.T_CHAR:
1186                        push(ARRAY_OF | CHAR);
1187                        break;
1188                    case Opcodes.T_BYTE:
1189                        push(ARRAY_OF | BYTE);
1190                        break;
1191                    case Opcodes.T_SHORT:
1192                        push(ARRAY_OF | SHORT);
1193                        break;
1194                    case Opcodes.T_INT:
1195                        push(ARRAY_OF | INTEGER);
1196                        break;
1197                    case Opcodes.T_FLOAT:
1198                        push(ARRAY_OF | FLOAT);
1199                        break;
1200                    case Opcodes.T_DOUBLE:
1201                        push(ARRAY_OF | DOUBLE);
1202                        break;
1203                    // case Opcodes.T_LONG:
1204                    default:
1205                        push(ARRAY_OF | LONG);
1206                        break;
1207                }
1208                break;
1209            case Opcodes.ANEWARRAY:
1210                String   s = item.strVal1;
1211                pop();
1212                if (s.charAt(0) == '[') {
1213                    push(cw, "[" + s);
1214                } else {
1215                    push(ARRAY_OF | OBJECT | cw.addType(s));
1216                }
1217                break;
1218            case Opcodes.CHECKCAST:
1219                s = item.strVal1;
1220                pop();
1221                if (s.charAt(0) == '[') {
1222                    push(cw, s);
1223                } else {
1224                    push(OBJECT | cw.addType(s));
1225                }
1226                break;
1227            // case Opcodes.MULTIANEWARRAY:
1228            default:
1229                pop(arg);
1230                push(cw, item.strVal1);
1231                break;
1232        }
1233    }
1234
1235    /**
1236     * Merges the input frame of the given basic block with the input and output
1237     * frames of this basic block. Returns <tt>true</tt> if the input frame of
1238     * the given label has been changed by this operation.
1239     * 
1240     * @param cw the ClassWriter to which this label belongs.
1241     * @param frame the basic block whose input frame must be updated.
1242     * @param edge the kind of the {@link Edge} between this label and 'label'.
1243     *        See {@link Edge#info}.
1244     * @return <tt>true</tt> if the input frame of the given label has been
1245     *         changed by this operation.
1246     */
1247    boolean merge(final ClassWriter cw, final Frame frame, final int edge) {
1248        boolean changed = false;
1249        int i, s, dim, kind, t;
1250
1251        int nLocal = inputLocals.length;
1252        int nStack = inputStack.length;
1253        if (frame.inputLocals == null) {
1254            frame.inputLocals = new int[nLocal];
1255            changed = true;
1256        }
1257
1258        for (i = 0; i < nLocal; ++i) {
1259            if (outputLocals != null && i < outputLocals.length) {
1260                s = outputLocals[i];
1261                if (s == 0) {
1262                    t = inputLocals[i];
1263                } else {
1264                    dim = s & DIM;
1265                    kind = s & KIND;
1266                    if (kind == LOCAL) {
1267                        t = dim + inputLocals[s & VALUE];
1268                    } else if (kind == STACK) {
1269                        t = dim + inputStack[nStack - (s & VALUE)];
1270                    } else {
1271                        t = s;
1272                    }
1273                }
1274            } else {
1275                t = inputLocals[i];
1276            }
1277            if (initializations != null) {
1278                t = init(cw, t);
1279            }
1280            changed |= merge(cw, t, frame.inputLocals, i);
1281        }
1282
1283        if (edge > 0) {
1284            for (i = 0; i < nLocal; ++i) {
1285                t = inputLocals[i];
1286                changed |= merge(cw, t, frame.inputLocals, i);
1287            }
1288            if (frame.inputStack == null) {
1289                frame.inputStack = new int[1];
1290                changed = true;
1291            }
1292            changed |= merge(cw, edge, frame.inputStack, 0);
1293            return changed;
1294        }
1295
1296        int nInputStack = inputStack.length + owner.inputStackTop;
1297        if (frame.inputStack == null) {
1298            frame.inputStack = new int[nInputStack + outputStackTop];
1299            changed = true;
1300        }
1301
1302        for (i = 0; i < nInputStack; ++i) {
1303            t = inputStack[i];
1304            if (initializations != null) {
1305                t = init(cw, t);
1306            }
1307            changed |= merge(cw, t, frame.inputStack, i);
1308        }
1309        for (i = 0; i < outputStackTop; ++i) {
1310            s = outputStack[i];
1311            dim = s & DIM;
1312            kind = s & KIND;
1313            if (kind == LOCAL) {
1314                t = dim + inputLocals[s & VALUE];
1315            } else if (kind == STACK) {
1316                t = dim + inputStack[nStack - (s & VALUE)];
1317            } else {
1318                t = s;
1319            }
1320            if (initializations != null) {
1321                t = init(cw, t);
1322            }
1323            changed |= merge(cw, t, frame.inputStack, nInputStack + i);
1324        }
1325        return changed;
1326    }
1327
1328    /**
1329     * Merges the type at the given index in the given type array with the given
1330     * type. Returns <tt>true</tt> if the type array has been modified by this
1331     * operation.
1332     * 
1333     * @param cw the ClassWriter to which this label belongs.
1334     * @param t the type with which the type array element must be merged.
1335     * @param types an array of types.
1336     * @param index the index of the type that must be merged in 'types'.
1337     * @return <tt>true</tt> if the type array has been modified by this
1338     *         operation.
1339     */
1340    private boolean merge(
1341        final ClassWriter cw,
1342        int t,
1343        final int[] types,
1344        final int index)
1345    {
1346        int u = types[index];
1347        if (u == t) {
1348            // if the types are equal, merge(u,t)=u, so there is no change
1349            return false;
1350        }
1351        if ((t & ~DIM) == NULL) {
1352            if (u == NULL) {
1353                return false;
1354            }
1355            t = NULL;
1356        }
1357        if (u == 0) {
1358            // if types[index] has never been assigned, merge(u,t)=t
1359            types[index] = t;
1360            return true;
1361        }
1362        int v;
1363        if ((u & BASE_KIND) == OBJECT || (u & DIM) != 0) {
1364            // if u is a reference type of any dimension
1365            if (t == NULL) {
1366                // if t is the NULL type, merge(u,t)=u, so there is no change
1367                return false;
1368            } else if ((t & (DIM | BASE_KIND)) == (u & (DIM | BASE_KIND))) {
1369                if ((u & BASE_KIND) == OBJECT) {
1370                    // if t is also a reference type, and if u and t have the
1371                    // same dimension merge(u,t) = dim(t) | common parent of the
1372                    // element types of u and t
1373                    v = (t & DIM) | OBJECT
1374                            | cw.getMergedType(t & BASE_VALUE, u & BASE_VALUE);
1375                } else {
1376                    // if u and t are array types, but not with the same element
1377                    // type, merge(u,t)=java/lang/Object
1378                    v = OBJECT | cw.addType("java/lang/Object");
1379                }
1380            } else if ((t & BASE_KIND) == OBJECT || (t & DIM) != 0) {
1381                // if t is any other reference or array type,
1382                // merge(u,t)=java/lang/Object
1383                v = OBJECT | cw.addType("java/lang/Object");
1384            } else {
1385                // if t is any other type, merge(u,t)=TOP
1386                v = TOP;
1387            }
1388        } else if (u == NULL) {
1389            // if u is the NULL type, merge(u,t)=t,
1390            // or TOP if t is not a reference type
1391            v = (t & BASE_KIND) == OBJECT || (t & DIM) != 0 ? t : TOP;
1392        } else {
1393            // if u is any other type, merge(u,t)=TOP whatever t
1394            v = TOP;
1395        }
1396        if (u != v) {
1397            types[index] = v;
1398            return true;
1399        }
1400        return false;
1401    }
1402}
1403
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags