001/*
002 *  This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 *  This file is licensed to You under the Eclipse Public License (EPL);
005 *  You may not use this file except in compliance with the License. You
006 *  may obtain a copy of the License at
007 *
008 *      http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 *  See the COPYRIGHT.txt file distributed with this work for information
011 *  regarding copyright ownership.
012 */
013package org.jikesrvm.osr;
014
015import static org.jikesrvm.classloader.BytecodeConstants.*;
016import static org.jikesrvm.classloader.ClassLoaderConstants.ArrayTypeCode;
017import static org.jikesrvm.classloader.ClassLoaderConstants.CP_CLASS;
018import static org.jikesrvm.classloader.ClassLoaderConstants.CP_DOUBLE;
019import static org.jikesrvm.classloader.ClassLoaderConstants.CP_FLOAT;
020import static org.jikesrvm.classloader.ClassLoaderConstants.CP_INT;
021import static org.jikesrvm.classloader.ClassLoaderConstants.CP_LONG;
022import static org.jikesrvm.classloader.ClassLoaderConstants.CP_STRING;
023import static org.jikesrvm.classloader.ClassLoaderConstants.ClassTypeCode;
024import static org.jikesrvm.classloader.ClassLoaderConstants.DoubleTypeCode;
025import static org.jikesrvm.classloader.ClassLoaderConstants.FloatTypeCode;
026import static org.jikesrvm.classloader.ClassLoaderConstants.IntTypeCode;
027import static org.jikesrvm.classloader.ClassLoaderConstants.LongTypeCode;
028import static org.jikesrvm.classloader.ClassLoaderConstants.VoidTypeCode;
029import static org.jikesrvm.osr.OSRConstants.PSEUDO_InvokeCompiledMethod;
030import static org.jikesrvm.osr.OSRConstants.PSEUDO_InvokeStatic;
031import static org.jikesrvm.osr.OSRConstants.PSEUDO_LoadDoubleConst;
032import static org.jikesrvm.osr.OSRConstants.PSEUDO_LoadFloatConst;
033import static org.jikesrvm.osr.OSRConstants.PSEUDO_LoadIntConst;
034import static org.jikesrvm.osr.OSRConstants.PSEUDO_LoadLongConst;
035import static org.jikesrvm.osr.OSRConstants.PSEUDO_LoadRetAddrConst;
036import static org.jikesrvm.osr.OSRConstants.PSEUDO_LoadWordConst;
037import static org.jikesrvm.osr.OSRConstants.PSEUDO_ParamInitEnd;
038import static org.jikesrvm.osr.OSRConstants.ReturnAddressTypeCode;
039import static org.jikesrvm.osr.OSRConstants.WordTypeCode;
040
041import org.jikesrvm.VM;
042import org.jikesrvm.classloader.BytecodeStream;
043import org.jikesrvm.classloader.ExceptionHandlerMap;
044import org.jikesrvm.classloader.FieldReference;
045import org.jikesrvm.classloader.MethodReference;
046import org.jikesrvm.classloader.NormalMethod;
047import org.jikesrvm.classloader.RVMClass;
048import org.jikesrvm.classloader.RVMMethod;
049import org.jikesrvm.classloader.TypeReference;
050import org.jikesrvm.compilers.common.CompiledMethods;
051import org.jikesrvm.osr.bytecodes.InvokeStatic;
052
053/**
054 * BytecodeTraverser does depth first search on a bytecode
055 * array, determines the type information of locals and stacks at
056 * Interesting point.
057 * <p>
058 * This class only intends to provide type information for on-stack
059 * replacement, which needs to know the type of a value.  This class
060 * can only tells basic type information such as : REFERENCE, LONG,
061 * DOUBLE, FLOAT, INT, and ReturnAddress.  Not like GCMap which tells
062 * GC a value is REFERENCE or NON-REFERENCE we also want to know it
063 * is INT or DOUBLE, and takes two words value or one word.
064 * <p>
065 * The produced type information has to be adjusted by consulting
066 * GC maps because two different types may merge at one program point
067 * (REF and non-REF types). Bytecode verifier will make the type info
068 * undefined in that case. But this class won't know. So the caller
069 * should check the GC map to validate a REF type variable.
070 * <p>
071 * More or less, this class needs to do the same work as a bytecode
072 * verifier, which tells the type and size of each locals and stacks.
073 * The JSR/RET instructions pose the difficulty to our case. However,
074 * we can assume the bytecode is verified. We use following assumptions:
075 * <ol>
076 *   <li> After JSR, the stack was not changed, only local variable
077 *      type needs to merge with FINALLY clause.
078 *   <li> We need program-point specific stack type, but only need
079 *      the summary of local types. Thus, after analysis, local
080 *      types are same for all PCs.
081 * </ol>
082 */
083public class BytecodeTraverser {
084
085  /////// COMMON
086  /* to handle ret address which is not produced by JSR, we need a
087   * separate array to track that.
088   */
089  private int[] retaddr;
090  private int addr;
091
092  private byte[] visitedpc;
093  private final boolean TRACE = false;
094
095  // when computing infor for partial bytecodes
096  // donot following bytecodes out of range
097  private boolean ignoreGotos = false;
098  private BytecodeStream bytecodes;
099
100  /////// COMPUTING_TYPE_INFO
101  /* type information of local variables and stack slots */
102  private byte[] ltypes;
103  private byte[] stypes;
104
105  ///////////////////////////
106  // COMPUTE TYPE INFORMATION
107  //////////////////////////
108  /**
109   * Computes types of local variable and stack slots at an interesting point
110   * for future querying. Computing type info and retrieval should not be
111   * reentered. The type info of local variable is not accurate about reference
112   * types, see JVM SPEC (2nd edition) p 146.  The caller can consult GC map
113   * to verify if a local is a reference or not.
114   *
115   * @param method whose bytecode to be queried
116   * @param bcpoint the bytecode index which is the interesting point
117   *               at the mean time, we only support one PC.
118   * @return whether the pc is a valid program point of the method
119   */
120  public boolean computeLocalStackTypes(NormalMethod method, int bcpoint) {
121    if (VM.TraceOnStackReplacement) {
122      VM.sysWrite("computing local and stack types of " + method + "\n");
123    }
124
125    int localsize = method.getLocalWords();
126    ltypes = new byte[localsize];
127
128    if (VM.TraceOnStackReplacement) {
129      VM.sysWrite("local size : ");
130      VM.sysWrite(localsize);
131      VM.sysWrite("\n");
132    }
133
134    retaddr = new int[localsize];
135    for (int i = 0; i < localsize; i++) {
136      retaddr[i] = -1;
137    }
138    addr = -1;
139
140    int stacksize = method.getOperandWords();
141    stypes = new byte[stacksize];
142
143    /* set marks for each byte code. */
144    // always operate on original method
145    this.bytecodes = method.getBytecodes();
146
147    visitedpc = new byte[bytecodes.length()];
148
149    /* then we initialize all stack and local type as void. */
150    for (int i = 0, n = ltypes.length; i < n; i++) {
151      ltypes[i] = VoidTypeCode;
152    }
153
154    TypeStack simstacks = new TypeStack(stacksize, VoidTypeCode);
155
156    /* initialize local types from method signature.*/
157    {
158      TypeReference[] ptypes = method.getParameterTypes();
159      int lidx = 0;
160      if (!method.isStatic()) {
161        ltypes[lidx++] = ClassTypeCode;
162      }
163      for (int i = 0, n = ptypes.length; i < n; i++) {
164        byte tcode = ptypes[i].getName().parseForTypeCode();
165        ltypes[lidx++] = tcode;
166        if ((tcode == LongTypeCode) || (tcode == DoubleTypeCode)) {
167          ltypes[lidx++] = VoidTypeCode;
168        }
169      }
170    }
171
172    /* scan start from method entry */
173    boolean found = scanBlocks(method, bytecodes, true, bcpoint, ltypes, stypes, 0, simstacks, null);
174    /* scan for exception handler. */
175    if (!found) {
176      ExceptionHandlerMap ehmap = method.getExceptionHandlerMap();
177      if (ehmap != null) {
178        int[] handlerPCs = ehmap.getHandlerPC();
179        for (int i = 0, n = handlerPCs.length; i < n; i++) {
180          simstacks.clear();
181          simstacks.push(ClassTypeCode);
182          int startpc = handlerPCs[i];
183          found = scanBlocks(method, bytecodes, true, bcpoint, ltypes, stypes, startpc, simstacks, null);
184          if (found) {
185            break;
186          }
187        }
188      }
189    }
190    visitedpc = null;
191
192    return true;
193  }
194
195  /**
196   * Returns an array of type information of locals at the registered
197   * program point. The size of array is fixed by MAX_LOCALS, the type
198   * descriptor can be found in "ClassLoadConstants.java".
199   *
200   * @return an array of type information, or null
201   */
202  public byte[] getLocalTypes() {
203    return ltypes;
204  }
205
206  /**
207   * Returns an array of type information of stacks at a program
208   * point.  The size of array is fixed by MAX_STACKS, the type
209   * descriptor can be found in "ClassLoadConstants.java".
210   *
211   * @return an array of type information, or null
212   */
213  public byte[] getStackTypes() {
214    return stypes;
215  }
216
217  //////////////////////////
218  // COMPUTE STACK HEIGHTS
219  //////////////////////////
220  public void computeStackHeights(NormalMethod method, BytecodeStream bcodes, int[] stackHeights,
221                                  boolean adjustExptable) {
222    if (VM.TraceOnStackReplacement) {
223      VM.sysWriteln("computing stack heights of method " + method.toString());
224    }
225
226    /* set marks for each byte code. */
227    // this may be the specialized method
228    bytecodes = bcodes;
229    visitedpc = new byte[bytecodes.length()];
230
231    int localsize = method.getLocalWords();
232    retaddr = new int[localsize];
233    for (int i = 0; i < localsize; i++) {
234      retaddr[i] = -1;
235    }
236    addr = -1;
237
238    int stacksize = method.getOperandWords();
239    TypeStack simstacks = new TypeStack(stacksize, VoidTypeCode);
240
241    /* scan start from method entry */
242    {
243      int startpc = 0;
244      scanBlocks(method, bytecodes, false, -1, null, null, startpc, simstacks, stackHeights);
245    }
246    /* scan for exception handler. */
247    {
248      ExceptionHandlerMap ehmap = method.getExceptionHandlerMap();
249      if (ehmap != null) {
250        int[] handlerPCs = ehmap.getHandlerPC();
251
252        for (int i = 0, n = handlerPCs.length; i < n; i++) {
253          int startpc = handlerPCs[i];
254
255          /* for baseline compilation, the SpecialCompiler
256           * didnot adjust exception table, we has to adjust it
257           * here.
258           */
259          if (adjustExptable && method.isForOsrSpecialization()) {
260            startpc += method.getOsrPrologueLength();
261          }
262
263          simstacks.clear();
264          simstacks.push(ClassTypeCode);
265          scanBlocks(method, bytecodes, false, -1, null, null, startpc, simstacks, stackHeights);
266        }
267      }
268    }
269    visitedpc = null;
270  }
271
272  /**
273   * Compute stack heights of bytecode stream (used for osr prologue)
274   *
275   * @param method the method that's subject to OSR
276   * @param bcodes the bytecode stream for the OSR prologue
277   * @param stackHeights the original stack heights computed by the baseline
278   *  compiler
279   */
280  public void prologueStackHeights(NormalMethod method, BytecodeStream bcodes, int[] stackHeights) {
281    if (VM.TraceOnStackReplacement) {
282      VM.sysWriteln("computing stack heights of method " + method.toString());
283    }
284
285    /* set marks for each byte code. */
286    // this may be the specialized method
287    bytecodes = bcodes;
288    visitedpc = new byte[bytecodes.length()];
289
290    ignoreGotos = true;
291
292    int localsize = method.getLocalWords();
293    retaddr = new int[localsize];
294    for (int i = 0; i < localsize; i++) {
295      retaddr[i] = -1;
296    }
297    addr = -1;
298
299    int stacksize = method.getOperandWords();
300    TypeStack simstacks = new TypeStack(stacksize, VoidTypeCode);
301
302    /* scan start from method entry */
303    {
304      int startpc = 0;
305      scanBlocks(method, bytecodes, false, -1, null, null, startpc, simstacks, stackHeights);
306    }
307    visitedpc = null;
308  }
309
310  /* returns type code of the return type from the signature.
311  * SEE also : Atom.parseForReturnType
312  */
313  @SuppressWarnings("unused")
314  private byte getReturnCodeFromSignature(String sig) {
315    byte[] val = sig.getBytes();
316
317    int i = 0;
318    while (val[i++] != ')') ;
319    return (val[i]);
320  }
321
322  ////////////////////////////
323  // IMPLEMENTATION
324  ///////////////////////////
325
326  /* return true --> hit the bytecode pointed by PC */
327
328  private boolean scanBlocks(NormalMethod method,    // which method
329                             BytecodeStream bytecodes,         // the bytecodes
330                             boolean doDFS,       // do a DFS or one-pass scan
331                             int pcs,             // the target pcs, if doDFS
332                             byte[] ltypes,       // the local types if doDFS
333                             byte[] stypes,       // the stack types if doDFS
334                             int startpc,         // start pc
335                             TypeStack S,     // stack
336                             int[] stackHeights) { // the stack height if not doDFS
337
338    int localsize = method.getLocalWords() - 1;
339    RVMClass declaringClass = method.getDeclaringClass();
340    bytecodes.reset(startpc);
341
342    boolean found = false;
343
344    while (bytecodes.hasMoreBytecodes()) {
345      int pc = bytecodes.index(); // get current pc
346      if (visitedpc[pc] == 1) {
347        return false;
348      } else {
349        visitedpc[pc] = 1;
350      }
351
352      if (doDFS && (pc == pcs)) {
353        /* make a copy of stack frame and put into stypes. */
354        byte[] stack = S.snapshot();
355        System.arraycopy(stack, 0, stypes, 0, stack.length);
356        return true;
357      }
358
359      if (!doDFS) {
360        // record stack heights
361        stackHeights[pc] = localsize + S.depth();
362      }
363
364      /* let's continue */
365      int bcode = bytecodes.nextInstruction();
366
367      if (TRACE) {
368        if (bcode <= JBC_jsr_w) {
369          VM.sysWriteln(pc + " : " + S.depth() + " : " + JBC_name(bcode));
370        } else {
371          VM.sysWriteln(pc + " : " + S.depth() + " : impdep1");
372        }
373      }
374
375      switch (bcode) {
376        case JBC_nop:
377          break;
378        case JBC_aconst_null:
379          S.push(ClassTypeCode);
380          break;
381        case JBC_iconst_m1:
382        case JBC_iconst_0:
383        case JBC_iconst_1:
384        case JBC_iconst_2:
385        case JBC_iconst_3:
386        case JBC_iconst_4:
387        case JBC_iconst_5:
388          S.push(IntTypeCode);
389          break;
390        case JBC_lconst_0:
391        case JBC_lconst_1:
392          /* we should do the save order as opt compiler */
393          S.push(VoidTypeCode);
394          S.push(LongTypeCode);
395          break;
396        case JBC_fconst_0:
397        case JBC_fconst_1:
398        case JBC_fconst_2:
399          S.push(FloatTypeCode);
400          break;
401        case JBC_dconst_0:
402        case JBC_dconst_1:
403          S.push(VoidTypeCode);
404          S.push(DoubleTypeCode);
405          break;
406        case JBC_bipush:
407          bytecodes.getByteValue();
408          S.push(IntTypeCode);
409          break;
410        case JBC_sipush:
411          bytecodes.getShortValue();
412          S.push(IntTypeCode);
413          break;
414        case JBC_ldc:
415        case JBC_ldc_w: {
416          int cpoolidx = (bcode == JBC_ldc) ? bytecodes.getConstantIndex() : bytecodes.getWideConstantIndex();
417          byte tdesc = declaringClass.getLiteralDescription(cpoolidx);
418          switch (tdesc) {
419            case CP_INT:
420              S.push(IntTypeCode);
421              break;
422            case CP_FLOAT:
423              S.push(FloatTypeCode);
424              break;
425            case CP_STRING:
426              S.push(ClassTypeCode);
427              break;
428            case CP_CLASS:
429              S.push(ClassTypeCode);
430              break;
431            default:
432              if (VM.TraceOnStackReplacement) VM.sysWriteln("ldc unknown type " + tdesc);
433              if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED);
434              break;
435          }  // end of switch
436        }
437        break;
438        case JBC_ldc2_w: {
439          int cpoolidx = bytecodes.getWideConstantIndex();
440          byte tdesc = declaringClass.getLiteralDescription(cpoolidx);
441          S.push(VoidTypeCode);
442          switch (tdesc) {
443            case CP_LONG:
444              S.push(LongTypeCode);
445              break;
446            case CP_DOUBLE:
447              S.push(DoubleTypeCode);
448              break;
449            default:
450              if (VM.TraceOnStackReplacement) VM.sysWriteln("ldc2_w unknown type " + tdesc);
451              if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED);
452              break;
453          }  // end of switch
454        }
455        break;
456        case JBC_iload:
457          bytecodes.getLocalNumber(); // skip local
458          S.push(IntTypeCode);
459          break;
460        case JBC_lload:
461          bytecodes.getLocalNumber(); // skip local
462          S.push(VoidTypeCode);
463          S.push(LongTypeCode);
464          break;
465        case JBC_fload:
466          bytecodes.getLocalNumber(); // skip local
467          S.push(FloatTypeCode);
468          break;
469        case JBC_dload:
470          bytecodes.getLocalNumber();
471          S.push(VoidTypeCode);
472          S.push(DoubleTypeCode);
473          break;
474        case JBC_aload:
475          bytecodes.getLocalNumber();
476          S.push(ClassTypeCode);
477          break;
478        case JBC_iload_0:
479        case JBC_iload_1:
480        case JBC_iload_2:
481        case JBC_iload_3:
482          S.push(IntTypeCode);
483          break;
484        case JBC_lload_0:
485        case JBC_lload_1:
486        case JBC_lload_2:
487        case JBC_lload_3:
488          S.push(VoidTypeCode);
489          S.push(LongTypeCode);
490          break;
491        case JBC_fload_0:
492        case JBC_fload_1:
493        case JBC_fload_2:
494        case JBC_fload_3:
495          S.push(FloatTypeCode);
496          break;
497        case JBC_dload_0:
498        case JBC_dload_1:
499        case JBC_dload_2:
500        case JBC_dload_3:
501          S.push(VoidTypeCode);
502          S.push(DoubleTypeCode);
503          break;
504        case JBC_aload_0:
505        case JBC_aload_1:
506        case JBC_aload_2:
507        case JBC_aload_3:
508          S.push(ClassTypeCode);
509          break;
510        case JBC_iaload:
511        case JBC_baload:
512        case JBC_caload:
513        case JBC_saload:
514          S.pop();
515          S.pop();
516          S.push(IntTypeCode);
517          break;
518        case JBC_laload:
519          S.pop();
520          S.pop();
521          S.push(VoidTypeCode);
522          S.push(LongTypeCode);
523          break;
524        case JBC_faload:
525          S.pop();
526          S.pop();
527          S.push(FloatTypeCode);
528          break;
529        case JBC_daload:
530          S.pop();
531          S.pop();
532          S.push(VoidTypeCode);
533          S.push(DoubleTypeCode);
534          break;
535        case JBC_aaload:
536          S.pop();
537          S.pop();
538          S.push(ClassTypeCode);
539          break;
540        case JBC_istore: {
541          S.pop();
542          int index = bytecodes.getLocalNumber();
543          if (doDFS) ltypes[index] = IntTypeCode;
544        }
545        break;
546        case JBC_istore_0:
547        case JBC_istore_1:
548        case JBC_istore_2:
549        case JBC_istore_3: {
550          S.pop();
551          int index = bcode - JBC_istore_0;
552          if (doDFS) ltypes[index] = IntTypeCode;
553        }
554        break;
555        case JBC_lstore: {
556          S.pop();
557          S.pop();
558          int index = bytecodes.getLocalNumber();
559          if (doDFS) {
560            ltypes[index] = LongTypeCode;
561            ltypes[index + 1] = VoidTypeCode;
562          }
563        }
564        break;
565        case JBC_lstore_0:
566        case JBC_lstore_1:
567        case JBC_lstore_2:
568        case JBC_lstore_3: {
569          S.pop();
570          S.pop();
571          int index = bcode - JBC_lstore_0;
572          if (doDFS) {
573            ltypes[index] = LongTypeCode;
574            ltypes[index + 1] = VoidTypeCode;
575          }
576        }
577        break;
578        case JBC_fstore: {
579          S.pop();
580          int index = bytecodes.getLocalNumber();
581          if (doDFS) ltypes[index] = FloatTypeCode;
582        }
583        break;
584        case JBC_fstore_0:
585        case JBC_fstore_1:
586        case JBC_fstore_2:
587        case JBC_fstore_3: {
588          S.pop();
589          int index = bcode - JBC_fstore_0;
590          if (doDFS) ltypes[index] = FloatTypeCode;
591        }
592        break;
593        case JBC_dstore: {
594          S.pop();
595          S.pop();
596          int index = bytecodes.getLocalNumber();
597          if (doDFS) {
598            ltypes[index] = DoubleTypeCode;
599            ltypes[index + 1] = VoidTypeCode;
600          }
601        }
602        break;
603        case JBC_dstore_0:
604        case JBC_dstore_1:
605        case JBC_dstore_2:
606        case JBC_dstore_3: {
607          S.pop();
608          S.pop();
609          int index = bcode - JBC_dstore_0;
610          if (doDFS) {
611            ltypes[index] = DoubleTypeCode;
612            ltypes[index + 1] = VoidTypeCode;
613          }
614        }
615        break;
616        case JBC_astore: {
617          // caution: astore may save return address type
618          int index = bytecodes.getLocalNumber();
619          byte tcode = S.pop();
620
621          if (doDFS) ltypes[index] = tcode;
622
623          // for ret address.
624          if (tcode == ReturnAddressTypeCode) {
625            retaddr[index] = addr;
626            addr = -1;
627          }
628        }
629        break;
630        case JBC_astore_0:
631        case JBC_astore_1:
632        case JBC_astore_2:
633        case JBC_astore_3: {
634          // caution: astore may save return address type
635          int index = bcode - JBC_astore_0;
636          byte tcode = S.pop();
637
638          if (doDFS) ltypes[index] = tcode;
639
640          // for ret address.
641          if (tcode == ReturnAddressTypeCode) {
642            retaddr[index] = addr;
643            addr = -1;
644          }
645        }
646        break;
647        case JBC_iastore:
648        case JBC_bastore:
649        case JBC_castore:
650        case JBC_sastore:
651          S.pop(3);
652          break;
653        case JBC_lastore:
654          S.pop(4);
655          break;
656        case JBC_fastore:
657          S.pop(3);
658          break;
659        case JBC_dastore:
660          S.pop(4);
661          break;
662        case JBC_aastore:
663          S.pop(3);
664          break;
665        case JBC_pop:
666          S.pop();
667          break;
668        case JBC_pop2:
669          S.pop(2);
670          break;
671        case JBC_dup: {
672          byte v1 = S.peek();
673          S.push(v1);
674        }
675        break;
676        case JBC_dup_x1: {
677          byte v1 = S.peek();
678          S.pop();
679          byte v2 = S.peek();
680          S.pop();
681          S.push(v1);
682          S.push(v2);
683          S.push(v1);
684        }
685        break;
686        case JBC_dup_x2: {
687          byte v1 = S.peek();
688          S.pop();
689          byte v2 = S.peek();
690          S.pop();
691          byte v3 = S.peek();
692          S.pop();
693          S.push(v1);
694          S.push(v3);
695          S.push(v2);
696          S.push(v1);
697        }
698        break;
699        case JBC_dup2: {
700          byte v1 = S.peek();
701          S.pop();
702          byte v2 = S.peek();
703          S.push(v1);
704          S.push(v2);
705          S.push(v1);
706        }
707        break;
708        case JBC_dup2_x1: {
709          byte v1 = S.peek();
710          S.pop();
711          byte v2 = S.peek();
712          S.pop();
713          byte v3 = S.peek();
714          S.pop();
715          S.push(v2);
716          S.push(v1);
717          S.push(v3);
718          S.push(v2);
719          S.push(v1);
720        }
721        break;
722        case JBC_dup2_x2: {
723          byte v1 = S.peek();
724          S.pop();
725          byte v2 = S.peek();
726          S.pop();
727          byte v3 = S.peek();
728          S.pop();
729          byte v4 = S.peek();
730          S.pop();
731          S.push(v2);
732          S.push(v1);
733          S.push(v4);
734          S.push(v3);
735          S.push(v2);
736          S.push(v1);
737        }
738        break;
739        case JBC_swap: {
740          byte v1 = S.peek();
741          S.pop();
742          byte v2 = S.peek();
743          S.pop();
744          S.push(v1);
745          S.push(v2);
746        }
747        break;
748        case JBC_iadd:
749        case JBC_isub:
750        case JBC_imul:
751        case JBC_idiv:
752        case JBC_irem:
753        case JBC_iand:
754        case JBC_ior:
755        case JBC_ixor:
756        case JBC_ishl:
757        case JBC_ishr:
758        case JBC_iushr:
759          S.pop();
760          break;
761        case JBC_ladd:
762        case JBC_lsub:
763        case JBC_lmul:
764        case JBC_ldiv:
765        case JBC_lrem:
766        case JBC_land:
767        case JBC_lor:
768        case JBC_lxor:
769          S.pop(2);
770          break;
771        case JBC_lshl:
772        case JBC_lshr:
773        case JBC_lushr:
774          S.pop();
775          break;
776        case JBC_fadd:
777        case JBC_fsub:
778        case JBC_fmul:
779        case JBC_fdiv:
780        case JBC_frem:
781          S.pop();
782          break;
783        case JBC_dadd:
784        case JBC_dsub:
785        case JBC_dmul:
786        case JBC_ddiv:
787        case JBC_drem:
788          S.pop(2);
789          break;
790        case JBC_ineg:
791        case JBC_lneg:
792        case JBC_fneg:
793        case JBC_dneg:
794          break;
795        case JBC_iinc: {
796          int index = bytecodes.getLocalNumber();
797          /* int value = */
798          bytecodes.getIncrement();
799          if (doDFS) ltypes[index] = IntTypeCode;
800        }
801        break;
802        case JBC_i2l:
803          S.pop();
804          S.push(VoidTypeCode);
805          S.push(LongTypeCode);
806          break;
807        case JBC_i2f:
808          S.pop();
809          S.push(FloatTypeCode);
810          break;
811        case JBC_i2d:
812          S.pop();
813          S.push(VoidTypeCode);
814          S.push(DoubleTypeCode);
815          break;
816        case JBC_l2i:
817          S.pop(2);
818          S.push(IntTypeCode);
819          break;
820        case JBC_l2f:
821          S.pop(2);
822          S.push(FloatTypeCode);
823          break;
824        case JBC_l2d:
825          S.pop(2);
826          S.push(VoidTypeCode);
827          S.push(DoubleTypeCode);
828          break;
829        case JBC_f2i:
830          S.pop();
831          S.push(IntTypeCode);
832          break;
833        case JBC_f2l:
834          S.pop();
835          S.push(VoidTypeCode);
836          S.push(LongTypeCode);
837          break;
838        case JBC_f2d:
839          S.pop();
840          S.push(VoidTypeCode);
841          S.push(DoubleTypeCode);
842          break;
843        case JBC_d2i:
844          S.pop(2);
845          S.push(IntTypeCode);
846          break;
847        case JBC_d2l:
848          S.pop(2);
849          S.push(VoidTypeCode);
850          S.push(LongTypeCode);
851          break;
852        case JBC_d2f:
853          S.pop(2);
854          S.push(FloatTypeCode);
855          break;
856        case JBC_int2byte:
857        case JBC_int2char:
858        case JBC_int2short:
859          break;
860        case JBC_lcmp:
861          S.pop(4);
862          S.push(IntTypeCode);
863          break;
864        case JBC_fcmpl:
865        case JBC_fcmpg:
866          S.pop(2);
867          S.push(IntTypeCode);
868          break;
869        case JBC_dcmpl:
870        case JBC_dcmpg:
871          S.pop(4);
872          S.push(IntTypeCode);
873          break;
874        case JBC_ifeq:
875        case JBC_ifne:
876        case JBC_iflt:
877        case JBC_ifge:
878        case JBC_ifgt:
879        case JBC_ifle:
880        case JBC_ifnull:
881        case JBC_ifnonnull: {
882          S.pop();
883
884          // flowthrough first
885          int nextpc = pc + 3;
886          int target = pc + bytecodes.getBranchOffset();
887          if (doDFS) {
888            // make a copy of ltypes, stypes to pass in
889            byte[] newltypes = new byte[ltypes.length];
890            byte[] newstypes = new byte[stypes.length];
891            System.arraycopy(ltypes, 0, newltypes, 0, ltypes.length);
892            System.arraycopy(stypes, 0, newstypes, 0, stypes.length);
893            found = scanBlocks(method, bytecodes, true, pcs, newltypes, newstypes, nextpc, new TypeStack(S), null);
894            if (found) {
895              // copy back the ltypes and stypes
896              System.arraycopy(newltypes, 0, ltypes, 0, ltypes.length);
897              System.arraycopy(newstypes, 0, stypes, 0, stypes.length);
898
899              return true;
900            }
901          } else {
902            found = scanBlocks(method, bytecodes, false, -1, null, null, nextpc, new TypeStack(S), stackHeights);
903          }
904          bytecodes.reset(target);
905        }
906        break;
907        case JBC_if_icmpeq:
908        case JBC_if_icmpne:
909        case JBC_if_icmplt:
910        case JBC_if_icmpge:
911        case JBC_if_icmpgt:
912        case JBC_if_icmple:
913        case JBC_if_acmpeq:
914        case JBC_if_acmpne: {
915          S.pop(2);
916
917          // flowthrough first
918          int nextpc = pc + 3;
919          int target = pc + bytecodes.getBranchOffset();
920
921          if (doDFS) {
922            // make a copy of ltypes, stypes to pass in
923            byte[] newltypes = new byte[ltypes.length];
924            byte[] newstypes = new byte[stypes.length];
925            System.arraycopy(ltypes, 0, newltypes, 0, ltypes.length);
926            System.arraycopy(stypes, 0, newstypes, 0, stypes.length);
927            found = scanBlocks(method, bytecodes, true, pcs, newltypes, newstypes, nextpc, new TypeStack(S), null);
928            if (found) {
929              // copy back the ltypes and stypes
930              System.arraycopy(newltypes, 0, ltypes, 0, ltypes.length);
931              System.arraycopy(newstypes, 0, stypes, 0, stypes.length);
932
933              return true;
934            }
935          } else {
936            found = scanBlocks(method, bytecodes, false, -1, null, null, nextpc, new TypeStack(S), stackHeights);
937          }
938
939          bytecodes.reset(target);
940        }
941        break;
942        case JBC_goto: {
943          int offset = bytecodes.getBranchOffset();
944          if (!ignoreGotos) {
945            bytecodes.reset(pc + offset);
946          }
947        }
948        break;
949        case JBC_goto_w: {
950          int offset = bytecodes.getWideBranchOffset();
951          if (!ignoreGotos) {
952            bytecodes.reset(pc + offset);
953          }
954        }
955        break;
956        case JBC_jsr:
957        case JBC_jsr_w: {
958          // flow through firs
959          int nextpc = pc + ((bcode == JBC_jsr) ? 3 : 5);
960          int target = pc + ((bcode == JBC_jsr) ? bytecodes.getBranchOffset() : bytecodes.getWideBranchOffset());
961
962          if (doDFS) {
963            // make a copy of ltypes, stypes to pass in
964            byte[] newltypes = new byte[ltypes.length];
965            byte[] newstypes = new byte[stypes.length];
966            System.arraycopy(ltypes, 0, newltypes, 0, ltypes.length);
967            System.arraycopy(stypes, 0, newstypes, 0, stypes.length);
968            found = scanBlocks(method, bytecodes, true, pcs, newltypes, newstypes, nextpc, new TypeStack(S), null);
969            if (found) {
970              // copy back the ltypes and stypes
971              System.arraycopy(newltypes, 0, ltypes, 0, ltypes.length);
972              System.arraycopy(newstypes, 0, stypes, 0, stypes.length);
973
974              return true;
975            }
976          } else {
977            found = scanBlocks(method, bytecodes, false, -1, null, null, nextpc, new TypeStack(S), stackHeights);
978          }
979
980          // branch to jsr subroutine
981          // remember return address for ret.
982          addr = pc + ((bcode == JBC_jsr) ? 3 : 5);
983          S.push(ReturnAddressTypeCode);
984          bytecodes.reset(target);
985        }
986        break;
987        case JBC_ret: {
988          // the OPT compiler set local to null after _ret instruction,
989          // then we should clean it here also, otherwise it will
990          // throw a null pointer exception.
991          // HOWEVER, it is not part of JVM spec.
992          int index = bytecodes.getLocalNumber();
993
994          if (doDFS) ltypes[index] = VoidTypeCode;
995
996          /* the ret address may be saved by a PSEUDO_LoadRetAddrConstant
997          */
998          if (retaddr[index] != -1) {
999            bytecodes.reset(retaddr[index]);
1000            retaddr[index] = -1;
1001          } else {
1002            // now we hit ret, return out
1003            return false;
1004          }
1005        }
1006        break;
1007        case JBC_tableswitch: {
1008          S.pop();
1009          bytecodes.alignSwitch();
1010          int defaultval = bytecodes.getDefaultSwitchOffset();
1011          int low = bytecodes.getLowSwitchValue();
1012          int high = bytecodes.getHighSwitchValue();
1013
1014          // write down a list of targets
1015          int npairs = high - low + 1;
1016          int[] offsets = new int[npairs];
1017          for (int i = 0; i < npairs; i++) {
1018            offsets[i] = bytecodes.getTableSwitchOffset(i);
1019          }
1020
1021          for (int i = 0; i < npairs; i++) {
1022            int tgtpc = pc + offsets[i];
1023
1024            if (doDFS) {
1025              // make a copy of ltypes, stypes to pass in
1026              byte[] newltypes = new byte[ltypes.length];
1027              byte[] newstypes = new byte[stypes.length];
1028
1029              System.arraycopy(ltypes, 0, newltypes, 0, ltypes.length);
1030              System.arraycopy(stypes, 0, newstypes, 0, stypes.length);
1031              found = scanBlocks(method, bytecodes, true, pcs, newltypes, newstypes, tgtpc, new TypeStack(S), null);
1032              if (found) {
1033                // copy back the ltypes and stypes
1034                System.arraycopy(newltypes, 0, ltypes, 0, ltypes.length);
1035                System.arraycopy(newstypes, 0, stypes, 0, stypes.length);
1036
1037                return true;
1038              }
1039            } else {
1040              found = scanBlocks(method, bytecodes, false, -1, null, null, tgtpc, new TypeStack(S), stackHeights);
1041            }
1042          }
1043
1044          // default
1045          {
1046            int tgtpc = pc + defaultval;
1047
1048            if (doDFS) {
1049              // make a copy of ltypes, stypes to pass in
1050              byte[] newltypes = new byte[ltypes.length];
1051              byte[] newstypes = new byte[stypes.length];
1052              System.arraycopy(ltypes, 0, newltypes, 0, ltypes.length);
1053              System.arraycopy(stypes, 0, newstypes, 0, stypes.length);
1054              found = scanBlocks(method, bytecodes, true, pcs, newltypes, newstypes, tgtpc, new TypeStack(S), null);
1055              if (found) {
1056                // copy back the ltypes and stypes
1057                System.arraycopy(newltypes, 0, ltypes, 0, ltypes.length);
1058                System.arraycopy(newstypes, 0, stypes, 0, stypes.length);
1059              }
1060            } else {
1061              found = scanBlocks(method, bytecodes, false, -1, null, null, tgtpc, new TypeStack(S), stackHeights);
1062            }
1063            return found;
1064          }
1065        }
1066        case JBC_lookupswitch: {
1067          S.pop(); // pop the key
1068          bytecodes.alignSwitch();
1069          int defaultval = bytecodes.getDefaultSwitchOffset();
1070          int npairs = bytecodes.getSwitchLength();
1071
1072          int[] matches = new int[npairs];
1073          int[] offsets = new int[npairs];
1074          for (int i = 0; i < npairs; i++) {
1075            matches[i] = bytecodes.getLookupSwitchValue(i);
1076            offsets[i] = bytecodes.getLookupSwitchOffset(i);
1077          }
1078
1079          for (int i = 0; i < npairs; i++) {
1080            //int match = matches[i];
1081            int offset = offsets[i];
1082
1083            int tgtpc = pc + offset;
1084
1085            if (doDFS) {
1086              // make a copy of ltypes, stypes to pass in
1087              byte[] newltypes = new byte[ltypes.length];
1088              byte[] newstypes = new byte[stypes.length];
1089
1090              System.arraycopy(ltypes, 0, newltypes, 0, ltypes.length);
1091              System.arraycopy(stypes, 0, newstypes, 0, stypes.length);
1092              found = scanBlocks(method, bytecodes, true, pcs, newltypes, newstypes, tgtpc, new TypeStack(S), null);
1093              if (found) {
1094                // copy back the ltypes and stypes
1095                System.arraycopy(newltypes, 0, ltypes, 0, ltypes.length);
1096                System.arraycopy(newstypes, 0, stypes, 0, stypes.length);
1097
1098                return true;
1099              }
1100            } else {
1101              found = scanBlocks(method, bytecodes, false, -1, null, null, tgtpc, new TypeStack(S), stackHeights);
1102            }
1103          }
1104
1105          // default
1106          {
1107            int tgtpc = pc + defaultval;
1108
1109            if (doDFS) {
1110              // make a copy of ltypes, stypes to pass in
1111              byte[] newltypes = new byte[ltypes.length];
1112              byte[] newstypes = new byte[stypes.length];
1113
1114              System.arraycopy(ltypes, 0, newltypes, 0, ltypes.length);
1115              System.arraycopy(stypes, 0, newstypes, 0, stypes.length);
1116              found = scanBlocks(method, bytecodes, true, pcs, newltypes, newstypes, tgtpc, new TypeStack(S), null);
1117              if (found) {
1118                // copy back the ltypes and stypes
1119                System.arraycopy(newltypes, 0, ltypes, 0, ltypes.length);
1120                System.arraycopy(newstypes, 0, stypes, 0, stypes.length);
1121              }
1122            } else {
1123              found = scanBlocks(method, bytecodes, false, -1, null, null, tgtpc, new TypeStack(S), stackHeights);
1124            }
1125          }
1126        }
1127        return found;
1128        case JBC_ireturn:
1129          S.pop();
1130          return false;
1131        case JBC_lreturn:
1132          S.pop(2);
1133          return false;
1134        case JBC_freturn:
1135          S.pop();
1136          return false;
1137        case JBC_dreturn:
1138          S.pop(2);
1139          return false;
1140        case JBC_areturn:
1141          S.pop();
1142          return false;
1143        case JBC_return:
1144          return false;
1145        case JBC_getfield:
1146          S.pop();
1147        case JBC_getstatic: {
1148          FieldReference fieldRef = bytecodes.getFieldReference();
1149          TypeReference ftype = fieldRef.getFieldContentsType();
1150          byte tcode = ftype.getName().parseForTypeCode();
1151          if ((tcode == LongTypeCode) || (tcode == DoubleTypeCode)) {
1152            S.push(VoidTypeCode);
1153          }
1154          S.push(tcode);
1155        }
1156        break;
1157        case JBC_putstatic: {
1158          FieldReference fieldRef = bytecodes.getFieldReference();
1159          TypeReference ftype = fieldRef.getFieldContentsType();
1160          byte tcode = ftype.getName().parseForTypeCode();
1161          if ((tcode == LongTypeCode) || (tcode == DoubleTypeCode)) {
1162            S.pop(2);
1163          } else {
1164            S.pop();
1165          }
1166        }
1167        break;
1168        case JBC_putfield: {
1169          FieldReference fieldRef = bytecodes.getFieldReference();
1170          TypeReference ftype = fieldRef.getFieldContentsType();
1171          byte tcode = ftype.getName().parseForTypeCode();
1172          if ((tcode == LongTypeCode) || (tcode == DoubleTypeCode)) {
1173            S.pop(2);
1174          } else {
1175            S.pop();
1176          }
1177        }
1178        S.pop();
1179        break;
1180        case JBC_invokevirtual:
1181        case JBC_invokespecial:
1182        case JBC_invokestatic:
1183        case JBC_invokeinterface: {
1184          MethodReference callee = bytecodes.getMethodReference();
1185
1186          int psize = callee.getParameterWords();
1187
1188          S.pop(psize);
1189
1190          if (bcode != JBC_invokestatic) {
1191            S.pop();     // pop the object reference
1192          }
1193
1194          TypeReference rtype = callee.getReturnType();
1195          byte tcode = rtype.getName().parseForTypeCode();
1196
1197          if (tcode == VoidTypeCode) {
1198            // nothing to do with void return type
1199          } else {
1200            if ((tcode == LongTypeCode) || (tcode == DoubleTypeCode)) {
1201              S.push(VoidTypeCode);
1202            }
1203            S.push(tcode);
1204          }
1205
1206          if (bcode == JBC_invokeinterface) {
1207            bytecodes.alignInvokeInterface();
1208          }
1209        }
1210        break;
1211        case JBC_invokedynamic:
1212          break;
1213
1214        case JBC_new:
1215          bytecodes.getTypeReference(); // skip cpi of type
1216          S.push(ClassTypeCode);
1217          break;
1218        case JBC_newarray:
1219          S.pop();
1220          S.push(ArrayTypeCode);
1221          bytecodes.getArrayElementType(); // skip cpi of element type
1222          break;
1223        case JBC_anewarray:
1224          S.pop();
1225          S.push(ArrayTypeCode);
1226          bytecodes.getTypeReference(); // skip cpi of reference type
1227          break;
1228        case JBC_arraylength:
1229          S.pop();
1230          S.push(IntTypeCode);
1231          break;
1232        case JBC_athrow:
1233          S.clear();
1234          S.push(ClassTypeCode);
1235          return false;
1236        case JBC_checkcast:
1237          bytecodes.getTypeReference(); // skip cpi of reference type
1238          break;
1239        case JBC_instanceof:
1240          S.pop();
1241          S.push(IntTypeCode);
1242          bytecodes.getTypeReference(); // skip cpi of reference type
1243          break;
1244        case JBC_monitorenter:
1245        case JBC_monitorexit:
1246          S.pop();
1247          break;
1248        case JBC_wide: {
1249          int widecode = bytecodes.getWideOpcode();
1250          int index = bytecodes.getWideLocalNumber();
1251          switch (widecode) {
1252            case JBC_iload:
1253              S.push(IntTypeCode);
1254              break;
1255            case JBC_lload:
1256              S.push(LongTypeCode);
1257              break;
1258            case JBC_fload:
1259              S.push(FloatTypeCode);
1260              break;
1261            case JBC_dload:
1262              S.push(DoubleTypeCode);
1263              break;
1264            case JBC_aload:
1265              S.push(ClassTypeCode);
1266              break;
1267            case JBC_istore:
1268              S.pop();
1269              if (doDFS) ltypes[index] = IntTypeCode;
1270              break;
1271            case JBC_lstore:
1272              S.pop();
1273              if (doDFS) ltypes[index] = LongTypeCode;
1274              break;
1275            case JBC_fstore:
1276              S.pop();
1277              if (doDFS) ltypes[index] = FloatTypeCode;
1278              break;
1279            case JBC_dstore:
1280              S.pop();
1281              if (doDFS) ltypes[index] = DoubleTypeCode;
1282              break;
1283            case JBC_astore: {
1284              byte tcode = S.pop();
1285              if (doDFS) ltypes[index] = tcode;
1286
1287              // for ret address.
1288              if (tcode == ReturnAddressTypeCode) {
1289                retaddr[index] = addr;
1290                addr = -1;
1291              }
1292            }
1293            break;
1294            case JBC_iinc: {
1295              bytecodes.getWideIncrement(); // skip increment
1296              if (doDFS) ltypes[index] = IntTypeCode;
1297            }
1298            break;
1299            case JBC_ret:
1300              if (doDFS) ltypes[index] = VoidTypeCode;
1301
1302              if (retaddr[index] != -1) {
1303                bytecodes.reset(retaddr[index]);
1304                retaddr[index] = -1;
1305              } else {
1306                // now we hit ret, return out
1307                return false;
1308              }
1309              break;
1310            default:
1311              if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED);
1312              break;
1313          }
1314          break;
1315        }
1316        case JBC_multianewarray: {
1317          bytecodes.getTypeReference(); // skip type reference
1318          int dims = bytecodes.getArrayDimension();
1319          S.pop(dims);
1320          S.push(ArrayTypeCode);
1321        }
1322        break;
1323        case JBC_impdep1: {
1324          int pseudo_opcode = bytecodes.nextPseudoInstruction();
1325          switch (pseudo_opcode) {
1326            case PSEUDO_LoadIntConst:
1327              bytecodes.readIntConst(); // skip value
1328              S.push(IntTypeCode);
1329              break;
1330            case PSEUDO_LoadLongConst:
1331              bytecodes.readLongConst(); // skip value
1332              S.push(VoidTypeCode);
1333              S.push(LongTypeCode);
1334              break;
1335            case PSEUDO_LoadWordConst:
1336              if (VM.BuildFor32Addr) {
1337                bytecodes.readIntConst();
1338              } else {
1339                bytecodes.readLongConst(); // skip value
1340              }
1341              S.push(WordTypeCode);
1342              break;
1343            case PSEUDO_LoadFloatConst:
1344              bytecodes.readIntConst(); // skip value
1345              S.push(FloatTypeCode);
1346              break;
1347            case PSEUDO_LoadDoubleConst:
1348              bytecodes.readLongConst(); // skip value
1349              S.push(VoidTypeCode);
1350              S.push(DoubleTypeCode);
1351              break;
1352            case PSEUDO_LoadRetAddrConst:
1353              // remember the address for ret.
1354              addr = bytecodes.readIntConst(); // get address
1355              S.push(ReturnAddressTypeCode);
1356              break;
1357            case PSEUDO_InvokeStatic: {
1358              int mid = bytecodes.readIntConst(); // get METHIDX
1359              RVMMethod callee = InvokeStatic.targetMethod(mid);
1360
1361              int psize = callee.getParameterWords();
1362              S.pop(psize);
1363
1364              TypeReference rtype = callee.getReturnType();
1365              byte tcode = rtype.getName().parseForTypeCode();
1366
1367              if (tcode == VoidTypeCode) {
1368                // nothing to do with void return type
1369              } else {
1370                if ((tcode == LongTypeCode) || (tcode == DoubleTypeCode)) {
1371                  S.push(VoidTypeCode);
1372                }
1373                S.push(tcode);
1374              }
1375              break;
1376            }
1377/*
1378        case PSEUDO_CheckCast:
1379          bytecodes.readIntConst(); // skip type id
1380          break;
1381*/
1382            case PSEUDO_InvokeCompiledMethod:
1383              int cmid = bytecodes.readIntConst(); // cmid
1384              bytecodes.readIntConst(); // skip bcindex
1385
1386              RVMMethod callee = CompiledMethods.getCompiledMethod(cmid).getMethod();
1387              int psize = callee.getParameterWords();
1388
1389              S.pop(psize);
1390
1391              if (!callee.isStatic()) {
1392                S.pop();   // pop receiver
1393              }
1394
1395              TypeReference rtype = callee.getReturnType();
1396              byte tcode = rtype.getName().parseForTypeCode();
1397
1398              if (tcode == VoidTypeCode) {
1399                // nothing to do with void return type
1400              } else {
1401                if ((tcode == LongTypeCode) || (tcode == DoubleTypeCode)) {
1402                  S.push(VoidTypeCode);
1403                }
1404                S.push(tcode);
1405              }
1406              break;
1407            case PSEUDO_ParamInitEnd:
1408              break;
1409            default:
1410              if (VM.VerifyAssertions) {
1411                VM.sysWrite(" Error, no such pseudo code : " + pseudo_opcode + "\n");
1412                VM._assert(VM.NOT_REACHED);
1413              }
1414              return false;
1415          }
1416          break;
1417        }
1418        default:
1419          VM.sysWrite("Unknown bytecode : " + bcode + "\n");
1420          return false;
1421      }
1422    }
1423
1424    /* did not found the PC. */
1425    return false;
1426  }
1427}
1428