1 /*
   2  * Copyright (c) 2001, 2011, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 package sun.jvm.hotspot.oops;
  26 
  27 import java.io.*;
  28 import java.util.*;
  29 import sun.jvm.hotspot.interpreter.*;
  30 import sun.jvm.hotspot.runtime.*;
  31 import sun.jvm.hotspot.utilities.*;
  32 
  33 /** Minimal port of the VM's oop map generator for interpreted frames */
  34 
  35 public class GenerateOopMap {
  36   interface JumpClosure {
  37     public void process(GenerateOopMap c, int bcpDelta, int[] data);
  38   }
  39 
  40   // Used for debugging this code
  41   private static final boolean DEBUG = false;
  42 
  43   // These two should be removed. But requires som code to be cleaned up
  44   private static final int MAXARGSIZE     =   256;      // This should be enough
  45   private static final int MAX_LOCAL_VARS = 65536;      // 16-bit entry
  46   private static final boolean TraceMonitorMismatch = true;
  47   private static final boolean TraceOopMapRewrites = true;
  48 
  49   // Commonly used constants
  50   static CellTypeState[] epsilonCTS = { CellTypeState.bottom };
  51   static CellTypeState   refCTS     = CellTypeState.ref;
  52   static CellTypeState   valCTS     = CellTypeState.value;
  53   static CellTypeState[]    vCTS    = { CellTypeState.value, CellTypeState.bottom };
  54   static CellTypeState[]    rCTS    = { CellTypeState.ref,   CellTypeState.bottom };
  55   static CellTypeState[]   rrCTS    = { CellTypeState.ref,   CellTypeState.ref,   CellTypeState.bottom };
  56   static CellTypeState[]   vrCTS    = { CellTypeState.value, CellTypeState.ref,   CellTypeState.bottom };
  57   static CellTypeState[]   vvCTS    = { CellTypeState.value, CellTypeState.value, CellTypeState.bottom };
  58   static CellTypeState[]  rvrCTS    = { CellTypeState.ref,   CellTypeState.value, CellTypeState.ref,   CellTypeState.bottom };
  59   static CellTypeState[]  vvrCTS    = { CellTypeState.value, CellTypeState.value, CellTypeState.ref,   CellTypeState.bottom };
  60   static CellTypeState[]  vvvCTS    = { CellTypeState.value, CellTypeState.value, CellTypeState.value, CellTypeState.bottom };
  61   static CellTypeState[] vvvrCTS    = { CellTypeState.value, CellTypeState.value, CellTypeState.value, CellTypeState.ref,   CellTypeState.bottom };
  62   static CellTypeState[] vvvvCTS    = { CellTypeState.value, CellTypeState.value, CellTypeState.value, CellTypeState.value, CellTypeState.bottom };
  63 
  64   /** Specialization of SignatureIterator - compute the effects of a call */
  65   static class ComputeCallStack extends SignatureIterator {
  66     CellTypeStateList _effect;
  67     int _idx;
  68 
  69     void set(CellTypeState state)         { _effect.get(_idx++).set(state); }
  70     int  length()                         { return _idx; };
  71 
  72     public void doBool  ()              { set(CellTypeState.value); }
  73     public void doChar  ()              { set(CellTypeState.value); }
  74     public void doFloat ()              { set(CellTypeState.value); }
  75     public void doByte  ()              { set(CellTypeState.value); }
  76     public void doShort ()              { set(CellTypeState.value); }
  77     public void doInt   ()              { set(CellTypeState.value); }
  78     public void doVoid  ()              { set(CellTypeState.bottom);}
  79     public void doObject(int begin, int end) { set(CellTypeState.ref); }
  80     public void doArray (int begin, int end) { set(CellTypeState.ref); }
  81 
  82     public void doDouble()              { set(CellTypeState.value);
  83                                           set(CellTypeState.value); }
  84     public void doLong  ()              { set(CellTypeState.value);
  85                                           set(CellTypeState.value); }
  86 
  87     ComputeCallStack(Symbol signature) {
  88       super(signature);
  89     }
  90 
  91     // Compute methods
  92     int computeForParameters(boolean is_static, CellTypeStateList effect) {
  93       _idx    = 0;
  94       _effect = effect;
  95 
  96       if (!is_static) {
  97         effect.get(_idx++).set(CellTypeState.ref);
  98       }
  99 
 100       iterateParameters();
 101 
 102       return length();
 103     };
 104 
 105     int computeForReturntype(CellTypeStateList effect) {
 106       _idx    = 0;
 107       _effect = effect;
 108       iterateReturntype();
 109       set(CellTypeState.bottom);  // Always terminate with a bottom state, so ppush works
 110 
 111       return length();
 112     }
 113   }
 114 
 115   /** Specialization of SignatureIterator - in order to set up first stack frame */
 116   static class ComputeEntryStack extends SignatureIterator {
 117     CellTypeStateList _effect;
 118     int _idx;
 119 
 120     void set(CellTypeState state)         { _effect.get(_idx++).set(state); }
 121     int  length()                         { return _idx; };
 122 
 123     public void doBool  ()              { set(CellTypeState.value); }
 124     public void doChar  ()              { set(CellTypeState.value); }
 125     public void doFloat ()              { set(CellTypeState.value); }
 126     public void doByte  ()              { set(CellTypeState.value); }
 127     public void doShort ()              { set(CellTypeState.value); }
 128     public void doInt   ()              { set(CellTypeState.value); }
 129     public void doVoid  ()              { set(CellTypeState.bottom);}
 130     public void doObject(int begin, int end) { set(CellTypeState.makeSlotRef(_idx)); }
 131     public void doArray (int begin, int end) { set(CellTypeState.makeSlotRef(_idx)); }
 132 
 133     public void doDouble()              { set(CellTypeState.value);
 134                                           set(CellTypeState.value); }
 135     public void doLong  ()              { set(CellTypeState.value);
 136                                           set(CellTypeState.value); }
 137 
 138     ComputeEntryStack(Symbol signature) {
 139       super(signature);
 140     }
 141 
 142     // Compute methods
 143     int computeForParameters(boolean is_static, CellTypeStateList effect) {
 144       _idx    = 0;
 145       _effect = effect;
 146 
 147       if (!is_static) {
 148         effect.get(_idx++).set(CellTypeState.makeSlotRef(0));
 149       }
 150 
 151       iterateParameters();
 152 
 153       return length();
 154     };
 155 
 156     int computeForReturntype(CellTypeStateList effect) {
 157       _idx    = 0;
 158       _effect = effect;
 159       iterateReturntype();
 160       set(CellTypeState.bottom);  // Always terminate with a bottom state, so ppush works
 161 
 162       return length();
 163     }
 164   }
 165 
 166   /** Contains maping between jsr targets and there return addresses.
 167       One-to-many mapping. */
 168   static class RetTableEntry {
 169     private static int _init_nof_jsrs; // Default size of jsrs list
 170     private int _target_bci;           // Target PC address of jump (bytecode index)
 171     private List/*<int>*/ _jsrs;       // List of return addresses  (bytecode index)
 172     private RetTableEntry _next;       // Link to next entry
 173 
 174     RetTableEntry(int target, RetTableEntry next) {
 175       _target_bci = target;
 176       _jsrs = new ArrayList(_init_nof_jsrs);
 177       _next = next;
 178     }
 179 
 180     // Query
 181     int targetBci()  { return _target_bci; }
 182     int nofJsrs()    { return _jsrs.size(); }
 183     int jsrs(int i)  { return ((Integer) _jsrs.get(i)).intValue(); }
 184 
 185     // Update entry
 186     void addJsr  (int return_bci)     { _jsrs.add(new Integer(return_bci)); }
 187     void addDelta(int bci, int delta) {
 188       if (_target_bci > bci) {
 189         _target_bci += delta;
 190       }
 191 
 192       for (int k = 0; k < nofJsrs(); k++) {
 193         int jsr = jsrs(k);
 194         if (jsr > bci) {
 195           _jsrs.set(k, new Integer(jsr+delta));
 196         }
 197       }
 198     }
 199     RetTableEntry next()               { return _next; }
 200   }
 201 
 202   static class RetTable {
 203     private RetTableEntry _first;
 204     private static int _init_nof_entries;
 205 
 206     private void addJsr(int return_bci, int target_bci) {
 207       RetTableEntry entry = _first;
 208 
 209       // Scan table for entry
 210       for (;(entry != null) && (entry.targetBci() != target_bci); entry = entry.next());
 211 
 212       if (entry == null) {
 213         // Allocate new entry and put in list
 214         entry = new RetTableEntry(target_bci, _first);
 215         _first = entry;
 216       }
 217 
 218       // Now "entry" is set.  Make sure that the entry is initialized
 219       // and has room for the new jsr.
 220       entry.addJsr(return_bci);
 221     }
 222 
 223     RetTable() {}
 224     void computeRetTable(Method method) {
 225       BytecodeStream i = new BytecodeStream(method);
 226       int bytecode;
 227 
 228       while( (bytecode = i.next()) >= 0) {
 229         switch (bytecode) {
 230         case Bytecodes._jsr:
 231           addJsr(i.nextBCI(), i.dest());
 232           break;
 233         case Bytecodes._jsr_w:
 234           addJsr(i.nextBCI(), i.dest_w());
 235           break;
 236         }
 237       }
 238     }
 239     void updateRetTable(int bci, int delta) {
 240       RetTableEntry cur = _first;
 241       while(cur != null) {
 242         cur.addDelta(bci, delta);
 243         cur = cur.next();
 244       }
 245     }
 246     RetTableEntry findJsrsForTarget(int targBci) {
 247       RetTableEntry cur = _first;
 248 
 249       while(cur != null) {
 250         if (Assert.ASSERTS_ENABLED) {
 251           Assert.that(cur.targetBci() != -1, "sanity check");
 252         }
 253         if (cur.targetBci() == targBci) {
 254           return cur;
 255         }
 256         cur = cur.next();
 257       }
 258       throw new RuntimeException("Should not reach here");
 259     }
 260   }
 261 
 262   static class BasicBlock {
 263     private boolean _changed;              // Reached a fixpoint or not
 264     static final int _dead_basic_block = -2;
 265     // Alive but not yet reached by analysis
 266     static final int _unreached        = -1;
 267     // >=0: Alive and has a merged state
 268 
 269     int                     _bci;          // Start of basic block
 270     int                     _end_bci;      // Bci of last instruction in basicblock
 271     int                     _max_locals;   // Determines split between vars and stack
 272     int                     _max_stack;    // Determines split between stack and monitors
 273     CellTypeStateList       _state;        // State (vars, stack) at entry.
 274     int                     _stack_top;    // -1 indicates bottom stack value.
 275     int                     _monitor_top;  // -1 indicates bottom monitor stack value.
 276 
 277     CellTypeStateList       vars()  { return _state; }
 278     CellTypeStateList       stack() { return _state.subList(_max_locals, _state.size()); }
 279 
 280     boolean changed()               { return _changed; }
 281     void    setChanged(boolean s)   { _changed = s; }
 282 
 283     // Analysis has reached this basicblock
 284     boolean isReachable()           { return _stack_top >= 0; }
 285 
 286     // All basicblocks that are unreachable are going to have a _stack_top == _dead_basic_block.
 287     // This info. is setup in a pre-parse before the real abstract interpretation starts.
 288     boolean isDead()                { return _stack_top == _dead_basic_block; }
 289     boolean isAlive()               { return _stack_top != _dead_basic_block; }
 290     void    markAsAlive()           {
 291       if (Assert.ASSERTS_ENABLED) {
 292         Assert.that(isDead(), "must be dead");
 293         _stack_top = _unreached;
 294       }
 295     }
 296   }
 297 
 298   //----------------------------------------------------------------------
 299   // Protected routines for GenerateOopMap
 300   //
 301 
 302   // _monitor_top is set to this constant to indicate that a monitor matching
 303   // problem was encountered prior to this point in control flow.
 304   protected static final int bad_monitors = -1;
 305 
 306   // Main variables
 307   Method   _method;         // The method we are examining
 308   RetTable _rt;             // Contains the return address mappings
 309   int      _max_locals;     // Cached value of no. of locals
 310   int      _max_stack;      // Cached value of max. stack depth
 311   int      _max_monitors;   // Cached value of max. monitor stack depth
 312   boolean  _has_exceptions; // True, if exceptions exist for method
 313   boolean  _got_error;      // True, if an error occured during interpretation.
 314   String   _error_msg;      // Error message. Set if _got_error is true.
 315   //  bool     _did_rewriting;  // was bytecodes rewritten
 316   //  bool     _did_relocation; // was relocation neccessary
 317   boolean  _monitor_safe;   // The monitors in this method have been determined
 318                             // to be safe.
 319 
 320   // Working Cell type state
 321   int               _state_len;     // Size of states
 322   CellTypeStateList _state;         // list of states
 323   char[]            _state_vec_buf; // Buffer used to print a readable version of a state
 324   int               _stack_top;
 325   int               _monitor_top;
 326 
 327   // Timing and statistics
 328   //  static elapsedTimer _total_oopmap_time;   // Holds cumulative oopmap generation time
 329   //  static long         _total_byte_count;    // Holds cumulative number of bytes inspected
 330 
 331   // Monitor query logic
 332   int _report_for_exit_bci;
 333   int _matching_enter_bci;
 334 
 335   // Cell type methods
 336   void            initState() {
 337     _state_len = _max_locals + _max_stack + _max_monitors;
 338     _state     = new CellTypeStateList(_state_len);
 339     _state_vec_buf = new char[Math.max(_max_locals, Math.max(_max_stack, Math.max(_max_monitors, 1)))];
 340   }
 341   void            makeContextUninitialized () {
 342     CellTypeStateList vs = vars();
 343 
 344     for (int i = 0; i < _max_locals; i++)
 345       vs.get(i).set(CellTypeState.uninit);
 346 
 347     _stack_top = 0;
 348     _monitor_top = 0;
 349   }
 350 
 351   int             methodsigToEffect          (Symbol signature, boolean isStatic, CellTypeStateList effect) {
 352     ComputeEntryStack ces = new ComputeEntryStack(signature);
 353     return ces.computeForParameters(isStatic, effect);
 354   }
 355 
 356   boolean         mergeStateVectors          (CellTypeStateList cts, CellTypeStateList bbts) {
 357     int i;
 358     int len = _max_locals + _stack_top;
 359     boolean change = false;
 360 
 361     for (i = len - 1; i >= 0; i--) {
 362       CellTypeState v = cts.get(i).merge(bbts.get(i), i);
 363       change = change || !v.equal(bbts.get(i));
 364       bbts.get(i).set(v);
 365     }
 366 
 367     if (_max_monitors > 0 && _monitor_top != bad_monitors) {
 368       // If there are no monitors in the program, or there has been
 369       // a monitor matching error before this point in the program,
 370       // then we do not merge in the monitor state.
 371 
 372       int base = _max_locals + _max_stack;
 373       len = base + _monitor_top;
 374       for (i = len - 1; i >= base; i--) {
 375         CellTypeState v = cts.get(i).merge(bbts.get(i), i);
 376 
 377         // Can we prove that, when there has been a change, it will already
 378         // have been detected at this point?  That would make this equal
 379         // check here unnecessary.
 380         change = change || !v.equal(bbts.get(i));
 381         bbts.get(i).set(v);
 382       }
 383     }
 384 
 385     return change;
 386   }
 387 
 388   void            copyState                  (CellTypeStateList dst, CellTypeStateList src) {
 389     int len = _max_locals + _stack_top;
 390     for (int i = 0; i < len; i++) {
 391       if (src.get(i).isNonlockReference()) {
 392         dst.get(i).set(CellTypeState.makeSlotRef(i));
 393       } else {
 394         dst.get(i).set(src.get(i));
 395       }
 396     }
 397     if (_max_monitors > 0 && _monitor_top != bad_monitors) {
 398       int base = _max_locals + _max_stack;
 399       len = base + _monitor_top;
 400       for (int i = base; i < len; i++) {
 401         dst.get(i).set(src.get(i));
 402       }
 403     }
 404   }
 405 
 406   void            mergeStateIntoBB           (BasicBlock bb) {
 407     if (Assert.ASSERTS_ENABLED) {
 408       Assert.that(bb.isAlive(), "merging state into a dead basicblock");
 409     }
 410 
 411     if (_stack_top == bb._stack_top) {
 412       if (_monitor_top == bb._monitor_top) {
 413         if (mergeStateVectors(_state, bb._state)) {
 414           bb.setChanged(true);
 415         }
 416       } else {
 417         if (TraceMonitorMismatch) {
 418           reportMonitorMismatch("monitor stack height merge conflict");
 419         }
 420         // When the monitor stacks are not matched, we set _monitor_top to
 421         // bad_monitors.  This signals that, from here on, the monitor stack cannot
 422         // be trusted.  In particular, monitorexit bytecodes may throw
 423         // exceptions.  We mark this block as changed so that the change
 424         // propagates properly.
 425         bb._monitor_top = bad_monitors;
 426         bb.setChanged(true);
 427         _monitor_safe = false;
 428       }
 429     } else if (!bb.isReachable()) {
 430       // First time we look at this  BB
 431       copyState(bb._state, _state);
 432       bb._stack_top = _stack_top;
 433       bb._monitor_top = _monitor_top;
 434       bb.setChanged(true);
 435     } else {
 436       throw new RuntimeException("stack height conflict: " +
 437                                  _stack_top + " vs. " + bb._stack_top);
 438     }
 439   }
 440 
 441   void            mergeState                 (int bci, int[] data) {
 442     mergeStateIntoBB(getBasicBlockAt(bci));
 443   }
 444 
 445   void            setVar                     (int localNo, CellTypeState cts) {
 446     if (Assert.ASSERTS_ENABLED) {
 447       Assert.that(cts.isReference() || cts.isValue() || cts.isAddress(),
 448                   "wrong celltypestate");
 449     }
 450     if (localNo < 0 || localNo > _max_locals) {
 451       throw new RuntimeException("variable write error: r" + localNo);
 452     }
 453     vars().get(localNo).set(cts);
 454   }
 455 
 456   CellTypeState   getVar                     (int localNo) {
 457     if (Assert.ASSERTS_ENABLED) {
 458       Assert.that(localNo < _max_locals + _nof_refval_conflicts, "variable read error");
 459     }
 460     if (localNo < 0 || localNo > _max_locals) {
 461       throw new RuntimeException("variable read error: r" + localNo);
 462     }
 463     return vars().get(localNo).copy();
 464   }
 465 
 466   CellTypeState   pop                        () {
 467     if ( _stack_top <= 0) {
 468       throw new RuntimeException("stack underflow");
 469     }
 470     return  stack().get(--_stack_top).copy();
 471   }
 472 
 473   void            push                       (CellTypeState cts) {
 474     if ( _stack_top >= _max_stack) {
 475       if (DEBUG) {
 476         System.err.println("Method: " + method().getName().asString() + method().getSignature().asString() +
 477                            " _stack_top: " + _stack_top + " _max_stack: " + _max_stack);
 478       }
 479       throw new RuntimeException("stack overflow");
 480     }
 481     stack().get(_stack_top++).set(cts);
 482     if (DEBUG) {
 483       System.err.println("After push: _stack_top: " + _stack_top +
 484                          " _max_stack: " + _max_stack +
 485                          " just pushed: " + cts.toChar());
 486     }
 487   }
 488 
 489   CellTypeState   monitorPop                 () {
 490     if (Assert.ASSERTS_ENABLED) {
 491       Assert.that(_monitor_top != bad_monitors, "monitorPop called on error monitor stack");
 492     }
 493     if (_monitor_top == 0) {
 494       // We have detected a pop of an empty monitor stack.
 495       _monitor_safe = false;
 496       _monitor_top = bad_monitors;
 497 
 498       if (TraceMonitorMismatch) {
 499         reportMonitorMismatch("monitor stack underflow");
 500       }
 501       return CellTypeState.ref; // just to keep the analysis going.
 502     }
 503     return  monitors().get(--_monitor_top).copy();
 504   }
 505 
 506   void            monitorPush                (CellTypeState cts) {
 507     if (Assert.ASSERTS_ENABLED) {
 508       Assert.that(_monitor_top != bad_monitors, "monitorPush called on error monitor stack");
 509     }
 510     if (_monitor_top >= _max_monitors) {
 511       // Some monitorenter is being executed more than once.
 512       // This means that the monitor stack cannot be simulated.
 513       _monitor_safe = false;
 514       _monitor_top = bad_monitors;
 515 
 516       if (TraceMonitorMismatch) {
 517         reportMonitorMismatch("monitor stack overflow");
 518       }
 519       return;
 520     }
 521     monitors().get(_monitor_top++).set(cts);
 522   }
 523 
 524   CellTypeStateList vars    ()     { return _state; }
 525   CellTypeStateList stack   ()     { return _state.subList(_max_locals, _state.size()); }
 526   CellTypeStateList monitors()     { return _state.subList(_max_locals+_max_stack, _state.size()); }
 527 
 528   void            replaceAllCTSMatches       (CellTypeState match,
 529                                               CellTypeState replace) {
 530     int i;
 531     int len = _max_locals + _stack_top;
 532     boolean change = false;
 533 
 534     for (i = len - 1; i >= 0; i--) {
 535       if (match.equal(_state.get(i))) {
 536         _state.get(i).set(replace);
 537       }
 538     }
 539 
 540     if (_monitor_top > 0) {
 541       int base = _max_locals + _max_stack;
 542       len = base + _monitor_top;
 543       for (i = len - 1; i >= base; i--) {
 544         if (match.equal(_state.get(i))) {
 545           _state.get(i).set(replace);
 546         }
 547       }
 548     }
 549   }
 550 
 551   void            printStates                (PrintStream tty, CellTypeStateList vector, int num) {
 552     for (int i = 0; i < num; i++) {
 553       vector.get(i).print(tty);
 554     }
 555   }
 556 
 557   void            printCurrentState          (PrintStream tty,
 558                                               BytecodeStream currentBC,
 559                                               boolean        detailed) {
 560     if (detailed) {
 561       tty.print("     " + currentBC.bci() + " vars     = ");
 562       printStates(tty, vars(), _max_locals);
 563       tty.print("    " + Bytecodes.name(currentBC.code()));
 564       switch(currentBC.code()) {
 565       case Bytecodes._invokevirtual:
 566       case Bytecodes._invokespecial:
 567       case Bytecodes._invokestatic:
 568       case Bytecodes._invokeinterface:
 569       case Bytecodes._invokedynamic:
 570         // FIXME: print signature of referenced method (need more
 571         // accessors in ConstantPool and ConstantPoolCache)
 572         int idx = currentBC.hasIndexU4() ? currentBC.getIndexU4() : currentBC.getIndexU2();
 573         tty.print(" idx " + idx);
 574         /*
 575           int idx = currentBC.getIndexU2();
 576           ConstantPool cp       = method().getConstants();
 577           int nameAndTypeIdx    = cp.name_and_type_ref_index_at(idx);
 578           int signatureIdx      = cp.signature_ref_index_at(nameAndTypeIdx);
 579           Symbol* signature     = cp.symbol_at(signatureIdx);
 580           tty.print("%s", signature.as_C_string());
 581         */
 582       }
 583       tty.println();
 584       tty.print("          stack    = ");
 585       printStates(tty, stack(), _stack_top);
 586       tty.println();
 587       if (_monitor_top != bad_monitors) {
 588         tty.print("          monitors = ");
 589         printStates(tty, monitors(), _monitor_top);
 590       } else {
 591         tty.print("          [bad monitor stack]");
 592       }
 593       tty.println();
 594     } else {
 595       tty.print("    " + currentBC.bci() + "  vars = '" +
 596                 stateVecToString(vars(), _max_locals) + "' ");
 597       tty.print("     stack = '" + stateVecToString(stack(), _stack_top) + "' ");
 598       if (_monitor_top != bad_monitors) {
 599         tty.print("  monitors = '" + stateVecToString(monitors(), _monitor_top) + "'  \t" +
 600                   Bytecodes.name(currentBC.code()));
 601       } else {
 602         tty.print("  [bad monitor stack]");
 603       }
 604       switch(currentBC.code()) {
 605       case Bytecodes._invokevirtual:
 606       case Bytecodes._invokespecial:
 607       case Bytecodes._invokestatic:
 608       case Bytecodes._invokeinterface:
 609       case Bytecodes._invokedynamic:
 610         // FIXME: print signature of referenced method (need more
 611         // accessors in ConstantPool and ConstantPoolCache)
 612         int idx = currentBC.hasIndexU4() ? currentBC.getIndexU4() : currentBC.getIndexU2();
 613         tty.print(" idx " + idx);
 614         /*
 615           int idx = currentBC.getIndexU2();
 616           constantPoolOop cp    = method().constants();
 617           int nameAndTypeIdx    = cp.name_and_type_ref_index_at(idx);
 618           int signatureIdx      = cp.signature_ref_index_at(nameAndTypeIdx);
 619           Symbol* signature     = cp.symbol_at(signatureIdx);
 620           tty.print("%s", signature.as_C_string());
 621         */
 622       }
 623       tty.println();
 624     }
 625   }
 626 
 627   void            reportMonitorMismatch      (String msg) {
 628     if (Assert.ASSERTS_ENABLED) {
 629       System.err.print("    Monitor mismatch in method ");
 630       method().printValueOn(System.err);
 631       System.err.println(": " + msg);
 632     }
 633   }
 634 
 635   // Basicblock info
 636   BasicBlock[]    _basic_blocks;             // Array of basicblock info
 637   int             _gc_points;
 638   int             _bb_count;
 639   BitMap          _bb_hdr_bits;
 640 
 641   // Basicblocks methods
 642   void          initializeBB               () {
 643     _gc_points = 0;
 644     _bb_count  = 0;
 645     _bb_hdr_bits = new BitMap((int) _method.getCodeSize());
 646   }
 647 
 648   void          markBBHeadersAndCountGCPoints() {
 649     initializeBB();
 650 
 651     boolean fellThrough = false;  // False to get first BB marked.
 652 
 653     // First mark all exception handlers as start of a basic-block
 654     TypeArray excps = method().getExceptionTable();
 655     for(int i = 0; i < excps.getLength(); i += 4) {
 656       int handler_pc_idx = i+2;
 657       markBB(excps.getIntAt(handler_pc_idx), null);
 658     }
 659 
 660     // Then iterate through the code
 661     BytecodeStream bcs = new BytecodeStream(_method);
 662     int bytecode;
 663 
 664     while( (bytecode = bcs.next()) >= 0) {
 665       int bci = bcs.bci();
 666 
 667       if (!fellThrough)
 668         markBB(bci, null);
 669 
 670       fellThrough = jumpTargetsDo(bcs,
 671                                   new JumpClosure() {
 672                                       public void process(GenerateOopMap c, int bcpDelta, int[] data) {
 673                                         c.markBB(bcpDelta, data);
 674                                       }
 675                                     },
 676                                   null);
 677 
 678       /* We will also mark successors of jsr's as basic block headers. */
 679       switch (bytecode) {
 680       case Bytecodes._jsr:
 681         if (Assert.ASSERTS_ENABLED) {
 682           Assert.that(!fellThrough, "should not happen");
 683         }
 684         markBB(bci + Bytecodes.lengthFor(bytecode), null);
 685         break;
 686       case Bytecodes._jsr_w:
 687         if (Assert.ASSERTS_ENABLED) {
 688           Assert.that(!fellThrough, "should not happen");
 689         }
 690         markBB(bci + Bytecodes.lengthFor(bytecode), null);
 691         break;
 692       }
 693 
 694       if (possibleGCPoint(bcs))
 695         _gc_points++;
 696     }
 697   }
 698 
 699   boolean       isBBHeader                  (int bci) {
 700     return _bb_hdr_bits.at(bci);
 701   }
 702 
 703   int           gcPoints                    () {
 704     return _gc_points;
 705   }
 706 
 707   int           bbCount                     () {
 708     return _bb_count;
 709   }
 710 
 711   void          setBBMarkBit                (int bci) {
 712     _bb_hdr_bits.atPut(bci, true);
 713   }
 714 
 715   void          clear_bbmark_bit            (int bci) {
 716     _bb_hdr_bits.atPut(bci, false);
 717   }
 718 
 719   BasicBlock    getBasicBlockAt             (int bci) {
 720     BasicBlock bb = getBasicBlockContaining(bci);
 721     if (Assert.ASSERTS_ENABLED) {
 722       Assert.that(bb._bci == bci, "should have found BB");
 723     }
 724     return bb;
 725   }
 726 
 727   BasicBlock    getBasicBlockContaining     (int bci) {
 728     BasicBlock[] bbs = _basic_blocks;
 729     int lo = 0, hi = _bb_count - 1;
 730 
 731     while (lo <= hi) {
 732       int m = (lo + hi) / 2;
 733       int mbci = bbs[m]._bci;
 734       int nbci;
 735 
 736       if ( m == _bb_count-1) {
 737         if (Assert.ASSERTS_ENABLED) {
 738           Assert.that( bci >= mbci && bci < method().getCodeSize(), "sanity check failed");
 739         }
 740         return bbs[m];
 741       } else {
 742         nbci = bbs[m+1]._bci;
 743       }
 744 
 745       if ( mbci <= bci && bci < nbci) {
 746         return bbs[m];
 747       } else if (mbci < bci) {
 748         lo = m + 1;
 749       } else {
 750         if (Assert.ASSERTS_ENABLED) {
 751           Assert.that(mbci > bci, "sanity check");
 752         }
 753         hi = m - 1;
 754       }
 755     }
 756 
 757     throw new RuntimeException("should have found BB");
 758   }
 759 
 760   void          interpBB                    (BasicBlock bb) {
 761     // We do not want to do anything in case the basic-block has not been initialized. This
 762     // will happen in the case where there is dead-code hang around in a method.
 763     if (Assert.ASSERTS_ENABLED) {
 764       Assert.that(bb.isReachable(), "should be reachable or deadcode exist");
 765     }
 766     restoreState(bb);
 767 
 768     BytecodeStream itr = new BytecodeStream(_method);
 769 
 770     // Set iterator interval to be the current basicblock
 771     int lim_bci = nextBBStartPC(bb);
 772     itr.setInterval(bb._bci, lim_bci);
 773 
 774     if (DEBUG) {
 775       System.err.println("interpBB: method = " + method().getName().asString() +
 776                          method().getSignature().asString() +
 777                          ", BCI interval [" + bb._bci + ", " + lim_bci + ")");
 778       {
 779         System.err.print("Bytecodes:");
 780         for (int i = bb._bci; i < lim_bci; i++) {
 781           System.err.print(" 0x" + Long.toHexString(method().getBytecodeOrBPAt(i)));
 782         }
 783         System.err.println();
 784       }
 785     }
 786 
 787     if (Assert.ASSERTS_ENABLED) {
 788       Assert.that(lim_bci != bb._bci, "must be at least one instruction in a basicblock");
 789     }
 790     itr.next(); // read first instruction
 791 
 792     // Iterates through all bytecodes except the last in a basic block.
 793     // We handle the last one special, since there is controlflow change.
 794     while(itr.nextBCI() < lim_bci && !_got_error) {
 795       if (_has_exceptions || (_monitor_top != 0)) {
 796         // We do not need to interpret the results of exceptional
 797         // continuation from this instruction when the method has no
 798         // exception handlers and the monitor stack is currently
 799         // empty.
 800         doExceptionEdge(itr);
 801       }
 802       interp1(itr);
 803       itr.next();
 804     }
 805 
 806     // Handle last instruction.
 807     if (!_got_error) {
 808       if (Assert.ASSERTS_ENABLED) {
 809         Assert.that(itr.nextBCI() == lim_bci, "must point to end");
 810       }
 811       if (_has_exceptions || (_monitor_top != 0)) {
 812         doExceptionEdge(itr);
 813       }
 814       interp1(itr);
 815 
 816       boolean fall_through = jumpTargetsDo(itr, new JumpClosure() {
 817           public void process(GenerateOopMap c, int bcpDelta, int[] data) {
 818             c.mergeState(bcpDelta, data);
 819           }
 820         }, null);
 821       if (_got_error)  return;
 822 
 823       if (itr.code() == Bytecodes._ret) {
 824         if (Assert.ASSERTS_ENABLED) {
 825           Assert.that(!fall_through, "cannot be set if ret instruction");
 826         }
 827         // Automatically handles 'wide' ret indicies
 828         retJumpTargetsDo(itr, new JumpClosure() {
 829             public void process(GenerateOopMap c, int bcpDelta, int[] data) {
 830               c.mergeState(bcpDelta, data);
 831             }
 832           }, itr.getIndex(), null);
 833       } else if (fall_through) {
 834         // Hit end of BB, but the instr. was a fall-through instruction,
 835         // so perform transition as if the BB ended in a "jump".
 836         if (Assert.ASSERTS_ENABLED) {
 837           Assert.that(lim_bci == _basic_blocks[bbIndex(bb) + 1]._bci, "there must be another bb");
 838         }
 839         mergeStateIntoBB(_basic_blocks[bbIndex(bb) + 1]);
 840       }
 841     }
 842   }
 843 
 844   void          restoreState                (BasicBlock bb) {
 845     for (int i = 0; i < _state_len; i++) {
 846       _state.get(i).set(bb._state.get(i));
 847     }
 848     _stack_top   = bb._stack_top;
 849     _monitor_top = bb._monitor_top;
 850   }
 851 
 852   int           nextBBStartPC               (BasicBlock bb) {
 853     int bbNum = bbIndex(bb) + 1;
 854     if (bbNum == _bb_count)
 855       return (int) method().getCodeSize();
 856 
 857     return _basic_blocks[bbNum]._bci;
 858   }
 859 
 860   void          updateBasicBlocks           (int bci, int delta) {
 861     BitMap bbBits = new BitMap((int) (_method.getCodeSize() + delta));
 862     for(int k = 0; k < _bb_count; k++) {
 863       if (_basic_blocks[k]._bci > bci) {
 864         _basic_blocks[k]._bci     += delta;
 865         _basic_blocks[k]._end_bci += delta;
 866       }
 867       bbBits.atPut(_basic_blocks[k]._bci, true);
 868     }
 869     _bb_hdr_bits = bbBits;
 870   }
 871 
 872   void markBB(int bci, int[] data) {
 873     if (Assert.ASSERTS_ENABLED) {
 874       Assert.that(bci>= 0 && bci < method().getCodeSize(), "index out of bounds");
 875     }
 876     if (isBBHeader(bci))
 877       return;
 878 
 879     // FIXME: remove
 880     //    if (TraceNewOopMapGeneration) {
 881     //      tty.print_cr("Basicblock#%d begins at: %d", c._bb_count, bci);
 882     //    }
 883     setBBMarkBit(bci);
 884     _bb_count++;
 885   }
 886 
 887   // Dead code detection
 888   void          markReachableCode() {
 889     final int[] change = new int[1];
 890     change[0] = 1;
 891 
 892     // Mark entry basic block as alive and all exception handlers
 893     _basic_blocks[0].markAsAlive();
 894     TypeArray excps = method().getExceptionTable();
 895     for(int i = 0; i < excps.getLength(); i += 4) {
 896       int handler_pc_idx = i+2;
 897       BasicBlock bb = getBasicBlockAt(excps.getIntAt(handler_pc_idx));
 898       // If block is not already alive (due to multiple exception handlers to same bb), then
 899       // make it alive
 900       if (bb.isDead())
 901         bb.markAsAlive();
 902     }
 903 
 904     BytecodeStream bcs = new BytecodeStream(_method);
 905 
 906     // Iterate through all basic blocks until we reach a fixpoint
 907     while (change[0] != 0) {
 908       change[0] = 0;
 909 
 910       for (int i = 0; i < _bb_count; i++) {
 911         BasicBlock bb = _basic_blocks[i];
 912         if (bb.isAlive()) {
 913           // Position bytecodestream at last bytecode in basicblock
 914           bcs.setStart(bb._end_bci);
 915           bcs.next();
 916           int bytecode = bcs.code();
 917           int bci = bcs.bci();
 918           if (Assert.ASSERTS_ENABLED) {
 919             Assert.that(bci == bb._end_bci, "wrong bci");
 920           }
 921 
 922           boolean fell_through = jumpTargetsDo(bcs, new JumpClosure() {
 923               public void process(GenerateOopMap c, int bciDelta, int[] change) {
 924                 c.reachableBasicblock(bciDelta, change);
 925               }
 926             }, change);
 927 
 928           // We will also mark successors of jsr's as alive.
 929           switch (bytecode) {
 930           case Bytecodes._jsr:
 931           case Bytecodes._jsr_w:
 932             if (Assert.ASSERTS_ENABLED) {
 933               Assert.that(!fell_through, "should not happen");
 934             }
 935             reachableBasicblock(bci + Bytecodes.lengthFor(bytecode), change);
 936             break;
 937           }
 938           if (fell_through) {
 939             // Mark successor as alive
 940             if (_basic_blocks[i+1].isDead()) {
 941               _basic_blocks[i+1].markAsAlive();
 942               change[0] = 1;
 943             }
 944           }
 945         }
 946       }
 947     }
 948   }
 949 
 950   void  reachableBasicblock        (int bci, int[] data) {
 951     if (Assert.ASSERTS_ENABLED) {
 952       Assert.that(bci>= 0 && bci < method().getCodeSize(), "index out of bounds");
 953     }
 954     BasicBlock bb = getBasicBlockAt(bci);
 955     if (bb.isDead()) {
 956       bb.markAsAlive();
 957       data[0] = 1; // Mark basicblock as changed
 958     }
 959   }
 960 
 961   // Interpretation methods (primary)
 962   void  doInterpretation                    () {
 963     // "i" is just for debugging, so we can detect cases where this loop is
 964     // iterated more than once.
 965     int i = 0;
 966     do {
 967       // FIXME: remove
 968       //      if (TraceNewOopMapGeneration) {
 969       //        tty.print("\n\nIteration #%d of do_interpretation loop, method:\n", i);
 970       //        method().print_name(tty);
 971       //        tty.print("\n\n");
 972       //      }
 973       _conflict = false;
 974       _monitor_safe = true;
 975       // init_state is now called from init_basic_blocks.  The length of a
 976       // state vector cannot be determined until we have made a pass through
 977       // the bytecodes counting the possible monitor entries.
 978       if (!_got_error) initBasicBlocks();
 979       if (!_got_error) setupMethodEntryState();
 980       if (!_got_error) interpAll();
 981       if (!_got_error) rewriteRefvalConflicts();
 982       i++;
 983     } while (_conflict && !_got_error);
 984   }
 985 
 986   void  initBasicBlocks                     () {
 987     // Note: Could consider reserving only the needed space for each BB's state
 988     // (entry stack may not be of maximal height for every basic block).
 989     // But cumbersome since we don't know the stack heights yet.  (Nor the
 990     // monitor stack heights...)
 991 
 992     _basic_blocks = new BasicBlock[_bb_count];
 993     for (int i = 0; i < _bb_count; i++) {
 994       _basic_blocks[i] = new BasicBlock();
 995     }
 996 
 997     // Make a pass through the bytecodes.  Count the number of monitorenters.
 998     // This can be used an upper bound on the monitor stack depth in programs
 999     // which obey stack discipline with their monitor usage.  Initialize the
1000     // known information about basic blocks.
1001     BytecodeStream j = new BytecodeStream(_method);
1002     int bytecode;
1003 
1004     int bbNo = 0;
1005     int monitor_count = 0;
1006     int prev_bci = -1;
1007     while( (bytecode = j.next()) >= 0) {
1008       if (j.code() == Bytecodes._monitorenter) {
1009         monitor_count++;
1010       }
1011 
1012       int bci = j.bci();
1013       if (isBBHeader(bci)) {
1014         // Initialize the basicblock structure
1015         BasicBlock bb    = _basic_blocks[bbNo];
1016         bb._bci          = bci;
1017         bb._max_locals   = _max_locals;
1018         bb._max_stack    = _max_stack;
1019         bb.setChanged(false);
1020         bb._stack_top    = BasicBlock._dead_basic_block; // Initialize all basicblocks are dead.
1021         bb._monitor_top  = bad_monitors;
1022 
1023         if (bbNo > 0) {
1024           _basic_blocks[bbNo - 1]._end_bci = prev_bci;
1025         }
1026 
1027         bbNo++;
1028       }
1029       // Remember prevous bci.
1030       prev_bci = bci;
1031     }
1032     // Set
1033     _basic_blocks[bbNo-1]._end_bci = prev_bci;
1034 
1035     _max_monitors = monitor_count;
1036 
1037     // Now that we have a bound on the depth of the monitor stack, we can
1038     // initialize the CellTypeState-related information.
1039     initState();
1040 
1041     // We allocate space for all state-vectors for all basicblocks in one huge chuck.
1042     // Then in the next part of the code, we set a pointer in each _basic_block that
1043     // points to each piece.
1044     CellTypeStateList basicBlockState = new CellTypeStateList(bbNo * _state_len);
1045 
1046     // Make a pass over the basicblocks and assign their state vectors.
1047     for (int blockNum=0; blockNum < bbNo; blockNum++) {
1048       BasicBlock bb = _basic_blocks[blockNum];
1049       bb._state = basicBlockState.subList(blockNum * _state_len, (blockNum + 1) * _state_len);
1050 
1051       if (Assert.ASSERTS_ENABLED) {
1052         if (blockNum + 1 < bbNo) {
1053           int bc_len = Bytecodes.javaLengthAt(_method, bb._end_bci);
1054           Assert.that(bb._end_bci + bc_len == _basic_blocks[blockNum + 1]._bci,
1055                       "unmatched bci info in basicblock");
1056         }
1057       }
1058     }
1059     if (Assert.ASSERTS_ENABLED) {
1060       BasicBlock bb = _basic_blocks[bbNo-1];
1061       int bc_len = Bytecodes.javaLengthAt(_method, bb._end_bci);
1062       Assert.that(bb._end_bci + bc_len == _method.getCodeSize(), "wrong end bci");
1063     }
1064 
1065     // Check that the correct number of basicblocks was found
1066     if (bbNo !=_bb_count) {
1067       if (bbNo < _bb_count) {
1068         throw new RuntimeException("jump into the middle of instruction?");
1069       } else {
1070         throw new RuntimeException("extra basic blocks - should not happen?");
1071       }
1072     }
1073 
1074     // Mark all alive blocks
1075     markReachableCode();
1076   }
1077 
1078   void  setupMethodEntryState               () {
1079     // Initialize all locals to 'uninit' and set stack-height to 0
1080     makeContextUninitialized();
1081 
1082     // Initialize CellState type of arguments
1083     methodsigToEffect(method().getSignature(), method().isStatic(), vars());
1084 
1085     // If some references must be pre-assigned to null, then set that up
1086     initializeVars();
1087 
1088     // This is the start state
1089     mergeStateIntoBB(_basic_blocks[0]);
1090 
1091     if (Assert.ASSERTS_ENABLED) {
1092       Assert.that(_basic_blocks[0].changed(), "we are not getting off the ground");
1093     }
1094   }
1095 
1096   void  interpAll                           () {
1097     boolean change = true;
1098 
1099     while (change && !_got_error) {
1100       change = false;
1101       for (int i = 0; i < _bb_count && !_got_error; i++) {
1102         BasicBlock bb = _basic_blocks[i];
1103         if (bb.changed()) {
1104           if (_got_error) return;
1105           change = true;
1106           bb.setChanged(false);
1107           interpBB(bb);
1108         }
1109       }
1110     }
1111   }
1112 
1113   //
1114   // Interpretation methods (secondary)
1115   //
1116 
1117   /** Sets the current state to be the state after executing the
1118       current instruction, starting in the current state. */
1119   void  interp1                             (BytecodeStream itr) {
1120     if (DEBUG) {
1121       System.err.println(" - bci " + itr.bci() + " " + itr.code());
1122       printCurrentState(System.err, itr, false);
1123     }
1124 
1125     //    if (TraceNewOopMapGeneration) {
1126     //      print_current_state(tty, itr, TraceNewOopMapGenerationDetailed);
1127     //    }
1128 
1129     // Should we report the results? Result is reported *before* the
1130     // instruction at the current bci is executed.  However, not for
1131     // calls. For calls we do not want to include the arguments, so we
1132     // postpone the reporting until they have been popped (in method
1133     // ppl).
1134     if (_report_result == true) {
1135       switch(itr.code()) {
1136       case Bytecodes._invokevirtual:
1137       case Bytecodes._invokespecial:
1138       case Bytecodes._invokestatic:
1139       case Bytecodes._invokeinterface:
1140       case Bytecodes._invokedynamic:
1141         _itr_send = itr;
1142         _report_result_for_send = true;
1143         break;
1144       default:
1145         fillStackmapForOpcodes(itr, vars(), stack(), _stack_top);
1146         break;
1147       }
1148     }
1149 
1150     // abstract interpretation of current opcode
1151     switch(itr.code()) {
1152     case Bytecodes._nop:               break;
1153     case Bytecodes._goto:              break;
1154     case Bytecodes._goto_w:            break;
1155     case Bytecodes._iinc:              break;
1156     case Bytecodes._return:            doReturnMonitorCheck();
1157       break;
1158 
1159     case Bytecodes._aconst_null:
1160     case Bytecodes._new:               ppush1(CellTypeState.makeLineRef(itr.bci()));
1161       break;
1162 
1163     case Bytecodes._iconst_m1:
1164     case Bytecodes._iconst_0:
1165     case Bytecodes._iconst_1:
1166     case Bytecodes._iconst_2:
1167     case Bytecodes._iconst_3:
1168     case Bytecodes._iconst_4:
1169     case Bytecodes._iconst_5:
1170     case Bytecodes._fconst_0:
1171     case Bytecodes._fconst_1:
1172     case Bytecodes._fconst_2:
1173     case Bytecodes._bipush:
1174     case Bytecodes._sipush:            ppush1(valCTS);             break;
1175 
1176     case Bytecodes._lconst_0:
1177     case Bytecodes._lconst_1:
1178     case Bytecodes._dconst_0:
1179     case Bytecodes._dconst_1:          ppush(vvCTS);               break;
1180 
1181     case Bytecodes._ldc2_w:            ppush(vvCTS);               break;
1182 
1183     case Bytecodes._ldc:               doLdc(itr.bci());           break;
1184     case Bytecodes._ldc_w:             doLdc(itr.bci());           break;
1185 
1186     case Bytecodes._iload:
1187     case Bytecodes._fload:             ppload(vCTS, itr.getIndex()); break;
1188 
1189     case Bytecodes._lload:
1190     case Bytecodes._dload:             ppload(vvCTS,itr.getIndex()); break;
1191 
1192     case Bytecodes._aload:             ppload(rCTS, itr.getIndex()); break;
1193 
1194     case Bytecodes._iload_0:
1195     case Bytecodes._fload_0:           ppload(vCTS, 0);            break;
1196     case Bytecodes._iload_1:
1197     case Bytecodes._fload_1:           ppload(vCTS, 1);            break;
1198     case Bytecodes._iload_2:
1199     case Bytecodes._fload_2:           ppload(vCTS, 2);            break;
1200     case Bytecodes._iload_3:
1201     case Bytecodes._fload_3:           ppload(vCTS, 3);            break;
1202 
1203     case Bytecodes._lload_0:
1204     case Bytecodes._dload_0:           ppload(vvCTS, 0);           break;
1205     case Bytecodes._lload_1:
1206     case Bytecodes._dload_1:           ppload(vvCTS, 1);           break;
1207     case Bytecodes._lload_2:
1208     case Bytecodes._dload_2:           ppload(vvCTS, 2);           break;
1209     case Bytecodes._lload_3:
1210     case Bytecodes._dload_3:           ppload(vvCTS, 3);           break;
1211 
1212     case Bytecodes._aload_0:           ppload(rCTS, 0);            break;
1213     case Bytecodes._aload_1:           ppload(rCTS, 1);            break;
1214     case Bytecodes._aload_2:           ppload(rCTS, 2);            break;
1215     case Bytecodes._aload_3:           ppload(rCTS, 3);            break;
1216 
1217     case Bytecodes._iaload:
1218     case Bytecodes._faload:
1219     case Bytecodes._baload:
1220     case Bytecodes._caload:
1221     case Bytecodes._saload:            pp(vrCTS, vCTS); break;
1222 
1223     case Bytecodes._laload:            pp(vrCTS, vvCTS);  break;
1224     case Bytecodes._daload:            pp(vrCTS, vvCTS); break;
1225 
1226     case Bytecodes._aaload:            ppNewRef(vrCTS, itr.bci()); break;
1227 
1228     case Bytecodes._istore:
1229     case Bytecodes._fstore:            ppstore(vCTS, itr.getIndex()); break;
1230 
1231     case Bytecodes._lstore:
1232     case Bytecodes._dstore:            ppstore(vvCTS, itr.getIndex()); break;
1233 
1234     case Bytecodes._astore:            doAstore(itr.getIndex());     break;
1235 
1236     case Bytecodes._istore_0:
1237     case Bytecodes._fstore_0:          ppstore(vCTS, 0);           break;
1238     case Bytecodes._istore_1:
1239     case Bytecodes._fstore_1:          ppstore(vCTS, 1);           break;
1240     case Bytecodes._istore_2:
1241     case Bytecodes._fstore_2:          ppstore(vCTS, 2);           break;
1242     case Bytecodes._istore_3:
1243     case Bytecodes._fstore_3:          ppstore(vCTS, 3);           break;
1244 
1245     case Bytecodes._lstore_0:
1246     case Bytecodes._dstore_0:          ppstore(vvCTS, 0);          break;
1247     case Bytecodes._lstore_1:
1248     case Bytecodes._dstore_1:          ppstore(vvCTS, 1);          break;
1249     case Bytecodes._lstore_2:
1250     case Bytecodes._dstore_2:          ppstore(vvCTS, 2);          break;
1251     case Bytecodes._lstore_3:
1252     case Bytecodes._dstore_3:          ppstore(vvCTS, 3);          break;
1253 
1254     case Bytecodes._astore_0:          doAstore(0);                break;
1255     case Bytecodes._astore_1:          doAstore(1);                break;
1256     case Bytecodes._astore_2:          doAstore(2);                break;
1257     case Bytecodes._astore_3:          doAstore(3);                break;
1258 
1259     case Bytecodes._iastore:
1260     case Bytecodes._fastore:
1261     case Bytecodes._bastore:
1262     case Bytecodes._castore:
1263     case Bytecodes._sastore:           ppop(vvrCTS);               break;
1264     case Bytecodes._lastore:
1265     case Bytecodes._dastore:           ppop(vvvrCTS);              break;
1266     case Bytecodes._aastore:           ppop(rvrCTS);               break;
1267 
1268     case Bytecodes._pop:               ppopAny(1);                 break;
1269     case Bytecodes._pop2:              ppopAny(2);                 break;
1270 
1271     case Bytecodes._dup:               ppdupswap(1, "11");         break;
1272     case Bytecodes._dup_x1:            ppdupswap(2, "121");        break;
1273     case Bytecodes._dup_x2:            ppdupswap(3, "1321");       break;
1274     case Bytecodes._dup2:              ppdupswap(2, "2121");       break;
1275     case Bytecodes._dup2_x1:           ppdupswap(3, "21321");      break;
1276     case Bytecodes._dup2_x2:           ppdupswap(4, "214321");     break;
1277     case Bytecodes._swap:              ppdupswap(2, "12");         break;
1278 
1279     case Bytecodes._iadd:
1280     case Bytecodes._fadd:
1281     case Bytecodes._isub:
1282     case Bytecodes._fsub:
1283     case Bytecodes._imul:
1284     case Bytecodes._fmul:
1285     case Bytecodes._idiv:
1286     case Bytecodes._fdiv:
1287     case Bytecodes._irem:
1288     case Bytecodes._frem:
1289     case Bytecodes._ishl:
1290     case Bytecodes._ishr:
1291     case Bytecodes._iushr:
1292     case Bytecodes._iand:
1293     case Bytecodes._ior:
1294     case Bytecodes._ixor:
1295     case Bytecodes._l2f:
1296     case Bytecodes._l2i:
1297     case Bytecodes._d2f:
1298     case Bytecodes._d2i:
1299     case Bytecodes._fcmpl:
1300     case Bytecodes._fcmpg:             pp(vvCTS, vCTS); break;
1301 
1302     case Bytecodes._ladd:
1303     case Bytecodes._dadd:
1304     case Bytecodes._lsub:
1305     case Bytecodes._dsub:
1306     case Bytecodes._lmul:
1307     case Bytecodes._dmul:
1308     case Bytecodes._ldiv:
1309     case Bytecodes._ddiv:
1310     case Bytecodes._lrem:
1311     case Bytecodes._drem:
1312     case Bytecodes._land:
1313     case Bytecodes._lor:
1314     case Bytecodes._lxor:              pp(vvvvCTS, vvCTS); break;
1315 
1316     case Bytecodes._ineg:
1317     case Bytecodes._fneg:
1318     case Bytecodes._i2f:
1319     case Bytecodes._f2i:
1320     case Bytecodes._i2c:
1321     case Bytecodes._i2s:
1322     case Bytecodes._i2b:               pp(vCTS, vCTS); break;
1323 
1324     case Bytecodes._lneg:
1325     case Bytecodes._dneg:
1326     case Bytecodes._l2d:
1327     case Bytecodes._d2l:               pp(vvCTS, vvCTS); break;
1328 
1329     case Bytecodes._lshl:
1330     case Bytecodes._lshr:
1331     case Bytecodes._lushr:             pp(vvvCTS, vvCTS); break;
1332 
1333     case Bytecodes._i2l:
1334     case Bytecodes._i2d:
1335     case Bytecodes._f2l:
1336     case Bytecodes._f2d:               pp(vCTS, vvCTS); break;
1337 
1338     case Bytecodes._lcmp:              pp(vvvvCTS, vCTS); break;
1339     case Bytecodes._dcmpl:
1340     case Bytecodes._dcmpg:             pp(vvvvCTS, vCTS); break;
1341 
1342     case Bytecodes._ifeq:
1343     case Bytecodes._ifne:
1344     case Bytecodes._iflt:
1345     case Bytecodes._ifge:
1346     case Bytecodes._ifgt:
1347     case Bytecodes._ifle:
1348     case Bytecodes._tableswitch:       ppop1(valCTS);
1349       break;
1350     case Bytecodes._ireturn:
1351     case Bytecodes._freturn:           doReturnMonitorCheck();
1352       ppop1(valCTS);
1353       break;
1354     case Bytecodes._if_icmpeq:
1355     case Bytecodes._if_icmpne:
1356     case Bytecodes._if_icmplt:
1357     case Bytecodes._if_icmpge:
1358     case Bytecodes._if_icmpgt:
1359     case Bytecodes._if_icmple:         ppop(vvCTS);
1360       break;
1361 
1362     case Bytecodes._lreturn:           doReturnMonitorCheck();
1363       ppop(vvCTS);
1364       break;
1365 
1366     case Bytecodes._dreturn:           doReturnMonitorCheck();
1367       ppop(vvCTS);
1368       break;
1369 
1370     case Bytecodes._if_acmpeq:
1371     case Bytecodes._if_acmpne:         ppop(rrCTS);                 break;
1372 
1373     case Bytecodes._jsr:               doJsr(itr.dest());          break;
1374     case Bytecodes._jsr_w:             doJsr(itr.dest_w());        break;
1375 
1376     case Bytecodes._getstatic:         doField(true,  true,  itr.getIndexU2Cpcache(), itr.bci()); break;
1377     case Bytecodes._putstatic:         doField(false, true,  itr.getIndexU2Cpcache(), itr.bci()); break;
1378     case Bytecodes._getfield:          doField(true,  false, itr.getIndexU2Cpcache(), itr.bci()); break;
1379     case Bytecodes._putfield:          doField(false, false, itr.getIndexU2Cpcache(), itr.bci()); break;
1380 
1381     case Bytecodes._invokevirtual:
1382     case Bytecodes._invokespecial:     doMethod(false, false, itr.getIndexU2Cpcache(), itr.bci()); break;
1383     case Bytecodes._invokestatic:      doMethod(true,  false, itr.getIndexU2Cpcache(), itr.bci()); break;
1384     case Bytecodes._invokedynamic:     doMethod(true,  false, itr.getIndexU4(),        itr.bci()); break;
1385     case Bytecodes._invokeinterface:   doMethod(false,  true, itr.getIndexU2Cpcache(), itr.bci()); break;
1386     case Bytecodes._newarray:
1387     case Bytecodes._anewarray:         ppNewRef(vCTS, itr.bci()); break;
1388     case Bytecodes._checkcast:         doCheckcast(); break;
1389     case Bytecodes._arraylength:
1390     case Bytecodes._instanceof:        pp(rCTS, vCTS); break;
1391     case Bytecodes._monitorenter:      doMonitorenter(itr.bci()); break;
1392     case Bytecodes._monitorexit:       doMonitorexit(itr.bci()); break;
1393 
1394     case Bytecodes._athrow:            // handled by do_exception_edge() BUT ...
1395       // vlh(apple): doExceptionEdge() does not get
1396       // called if method has no exception handlers
1397       if ((!_has_exceptions) && (_monitor_top > 0)) {
1398         _monitor_safe = false;
1399       }
1400       break;
1401 
1402     case Bytecodes._areturn:           doReturnMonitorCheck();
1403       ppop1(refCTS);
1404       break;
1405     case Bytecodes._ifnull:
1406     case Bytecodes._ifnonnull:         ppop1(refCTS); break;
1407     case Bytecodes._multianewarray:    doMultianewarray(itr.codeAt(itr.bci() + 3), itr.bci()); break;
1408 
1409     case Bytecodes._wide:              throw new RuntimeException("Iterator should skip this bytecode");
1410     case Bytecodes._ret:                                           break;
1411 
1412       // Java opcodes
1413     case Bytecodes._fast_aaccess_0:     ppNewRef(rCTS, itr.bci()); break; // Pair bytecode for (aload_0, _fast_agetfield)
1414 
1415     case Bytecodes._fast_iaccess_0:     ppush1(valCTS);            break; // Pair bytecode for (aload_0, _fast_igetfield)
1416 
1417     case Bytecodes._fast_igetfield:     pp(rCTS, vCTS);            break;
1418 
1419     case Bytecodes._fast_agetfield:     ppNewRef(rCTS, itr.bci()); break;
1420 
1421     case Bytecodes._fast_aload_0:       ppload(rCTS,  0);          break;
1422 
1423     case Bytecodes._lookupswitch:
1424     case Bytecodes._fast_linearswitch:
1425     case Bytecodes._fast_binaryswitch:  ppop1(valCTS);             break;
1426 
1427     default:
1428       throw new RuntimeException("unexpected opcode: " + itr.code());
1429     }
1430   }
1431 
1432   void  doExceptionEdge                     (BytecodeStream itr) {
1433     // Only check exception edge, if bytecode can trap
1434     if (!Bytecodes.canTrap(itr.code())) return;
1435     switch (itr.code()) {
1436     case Bytecodes._aload_0:
1437     case Bytecodes._fast_aload_0:
1438       // These bytecodes can trap for rewriting.  We need to assume that
1439       // they do not throw exceptions to make the monitor analysis work.
1440       return;
1441 
1442     case Bytecodes._ireturn:
1443     case Bytecodes._lreturn:
1444     case Bytecodes._freturn:
1445     case Bytecodes._dreturn:
1446     case Bytecodes._areturn:
1447     case Bytecodes._return:
1448       // If the monitor stack height is not zero when we leave the method,
1449       // then we are either exiting with a non-empty stack or we have
1450       // found monitor trouble earlier in our analysis.  In either case,
1451       // assume an exception could be taken here.
1452       if (_monitor_top == 0) {
1453         return;
1454       }
1455       break;
1456 
1457     case Bytecodes._monitorexit:
1458       // If the monitor stack height is bad_monitors, then we have detected a
1459       // monitor matching problem earlier in the analysis.  If the
1460       // monitor stack height is 0, we are about to pop a monitor
1461       // off of an empty stack.  In either case, the bytecode
1462       // could throw an exception.
1463       if (_monitor_top != bad_monitors && _monitor_top != 0) {
1464         return;
1465       }
1466       break;
1467     }
1468 
1469     if (_has_exceptions) {
1470       int bci = itr.bci();
1471       TypeArray exct   = method().getExceptionTable();
1472       for(int i = 0; i< exct.getLength(); i+=4) {
1473         int start_pc   = exct.getIntAt(i);
1474         int end_pc     = exct.getIntAt(i+1);
1475         int handler_pc = exct.getIntAt(i+2);
1476         int catch_type = exct.getIntAt(i+3);
1477 
1478         if (start_pc <= bci && bci < end_pc) {
1479           BasicBlock excBB = getBasicBlockAt(handler_pc);
1480           CellTypeStateList excStk  = excBB.stack();
1481           CellTypeStateList cOpStck = stack();
1482           CellTypeState cOpStck_0 = cOpStck.get(0).copy();
1483           int cOpStackTop = _stack_top;
1484 
1485           // Exception stacks are always the same.
1486           if (Assert.ASSERTS_ENABLED) {
1487             Assert.that(method().getMaxStack() > 0, "sanity check");
1488           }
1489 
1490           // We remembered the size and first element of "cOpStck"
1491           // above; now we temporarily set them to the appropriate
1492           // values for an exception handler.
1493           cOpStck.get(0).set(CellTypeState.makeSlotRef(_max_locals));
1494           _stack_top = 1;
1495 
1496           mergeStateIntoBB(excBB);
1497 
1498           // Now undo the temporary change.
1499           cOpStck.get(0).set(cOpStck_0);
1500           _stack_top = cOpStackTop;
1501 
1502           // If this is a "catch all" handler, then we do not need to
1503           // consider any additional handlers.
1504           if (catch_type == 0) {
1505             return;
1506           }
1507         }
1508       }
1509     }
1510 
1511     // It is possible that none of the exception handlers would have caught
1512     // the exception.  In this case, we will exit the method.  We must
1513     // ensure that the monitor stack is empty in this case.
1514     if (_monitor_top == 0) {
1515       return;
1516     }
1517 
1518     // We pessimistically assume that this exception can escape the
1519     // method. (It is possible that it will always be caught, but
1520     // we don't care to analyse the types of the catch clauses.)
1521 
1522     // We don't set _monitor_top to bad_monitors because there are no successors
1523     // to this exceptional exit.
1524 
1525     if (TraceMonitorMismatch && _monitor_safe) {
1526       // We check _monitor_safe so that we only report the first mismatched
1527       // exceptional exit.
1528       reportMonitorMismatch("non-empty monitor stack at exceptional exit");
1529     }
1530     _monitor_safe = false;
1531   }
1532 
1533   void  checkType                           (CellTypeState expected, CellTypeState actual) {
1534     if (!expected.equalKind(actual)) {
1535       throw new RuntimeException("wrong type on stack (found: " +
1536                                  actual.toChar() + " expected: " +
1537                                  expected.toChar() + ")");
1538     }
1539   }
1540 
1541   void  ppstore                             (CellTypeState[] in,  int loc_no) {
1542     for (int i = 0; i < in.length && !in[i].equal(CellTypeState.bottom); i++) {
1543       CellTypeState expected = in[i];
1544       CellTypeState actual   = pop();
1545       checkType(expected, actual);
1546       if (Assert.ASSERTS_ENABLED) {
1547         Assert.that(loc_no >= 0, "sanity check");
1548       }
1549       setVar(loc_no++, actual);
1550     }
1551   }
1552 
1553   void  ppload                              (CellTypeState[] out, int loc_no) {
1554     for (int i = 0; i < out.length && !out[i].equal(CellTypeState.bottom); i++) {
1555       CellTypeState out1 = out[i];
1556       CellTypeState vcts = getVar(loc_no);
1557       if (Assert.ASSERTS_ENABLED) {
1558         Assert.that(out1.canBeReference() || out1.canBeValue(),
1559                     "can only load refs. and values.");
1560       }
1561       if (out1.isReference()) {
1562         if (Assert.ASSERTS_ENABLED) {
1563           Assert.that(loc_no>=0, "sanity check");
1564         }
1565         if (!vcts.isReference()) {
1566           // We were asked to push a reference, but the type of the
1567           // variable can be something else
1568           _conflict = true;
1569           if (vcts.canBeUninit()) {
1570             // It is a ref-uninit conflict (at least). If there are other
1571             // problems, we'll get them in the next round
1572             addToRefInitSet(loc_no);
1573             vcts = out1;
1574           } else {
1575             // It wasn't a ref-uninit conflict. So must be a
1576             // ref-val or ref-pc conflict. Split the variable.
1577             recordRefvalConflict(loc_no);
1578             vcts = out1;
1579           }
1580           push(out1); // recover...
1581         } else {
1582           push(vcts); // preserve reference.
1583         }
1584         // Otherwise it is a conflict, but one that verification would
1585         // have caught if illegal. In particular, it can't be a topCTS
1586         // resulting from mergeing two difference pcCTS's since the verifier
1587         // would have rejected any use of such a merge.
1588       } else {
1589         push(out1); // handle val/init conflict
1590       }
1591       loc_no++;
1592     }
1593   }
1594 
1595   void  ppush1                              (CellTypeState in) {
1596     if (Assert.ASSERTS_ENABLED) {
1597       Assert.that(in.isReference() | in.isValue(), "sanity check");
1598     }
1599     if (DEBUG) {
1600       System.err.println("   - pushing " + in.toChar());
1601     }
1602     push(in);
1603   }
1604 
1605   void  ppush                               (CellTypeState[] in) {
1606     for (int i = 0; i < in.length && !in[i].equal(CellTypeState.bottom); i++) {
1607       ppush1(in[i]);
1608     }
1609   }
1610 
1611   void  ppush                               (CellTypeStateList in) {
1612     for (int i = 0; i < in.size() && !in.get(i).equal(CellTypeState.bottom); i++) {
1613       ppush1(in.get(i));
1614     }
1615   }
1616 
1617   void  ppop1                               (CellTypeState out) {
1618     CellTypeState actual = pop();
1619     if (DEBUG) {
1620       System.err.println("   - popping " + actual.toChar() + ", expecting " + out.toChar());
1621     }
1622     checkType(out, actual);
1623   }
1624 
1625   void  ppop                                (CellTypeState[] out) {
1626     for (int i = 0; i < out.length && !out[i].equal(CellTypeState.bottom); i++) {
1627       ppop1(out[i]);
1628     }
1629   }
1630 
1631   void  ppopAny                             (int poplen) {
1632     if (_stack_top >= poplen) {
1633       _stack_top -= poplen;
1634     } else {
1635       throw new RuntimeException("stack underflow");
1636     }
1637   }
1638 
1639   void  pp                                  (CellTypeState[] in, CellTypeState[] out) {
1640     ppop(in);
1641     ppush(out);
1642   }
1643 
1644   void  ppNewRef                            (CellTypeState[] in, int bci) {
1645     ppop(in);
1646     ppush1(CellTypeState.makeLineRef(bci));
1647   }
1648 
1649   void  ppdupswap                           (int poplen, String out) {
1650     CellTypeState[] actual = new CellTypeState[5];
1651     Assert.that(poplen < 5, "this must be less than length of actual vector");
1652 
1653     // pop all arguments
1654     for(int i = 0; i < poplen; i++) actual[i] = pop();
1655 
1656     // put them back
1657     for (int i = 0; i < out.length(); i++) {
1658       char push_ch = out.charAt(i);
1659       int idx = push_ch - '1';
1660       if (Assert.ASSERTS_ENABLED) {
1661         Assert.that(idx >= 0 && idx < poplen, "wrong arguments");
1662       }
1663       push(actual[idx]);
1664     }
1665   }
1666 
1667   void  doLdc                               (int bci) {
1668     BytecodeLoadConstant ldc = BytecodeLoadConstant.at(_method, bci);
1669     ConstantPool  cp  = method().getConstants();
1670     BasicType     bt = ldc.resultType();
1671     CellTypeState cts = (bt == BasicType.T_OBJECT) ? CellTypeState.makeLineRef(bci) : valCTS;
1672     ppush1(cts);
1673   }
1674 
1675   void  doAstore                            (int idx) {
1676     CellTypeState r_or_p = pop();
1677     if (!r_or_p.isAddress() && !r_or_p.isReference()) {
1678       // We actually expected ref or pc, but we only report that we expected a ref. It does not
1679       // really matter (at least for now)
1680       throw new RuntimeException("wrong type on stack (found: " +
1681                                  r_or_p.toChar() + ", expected: {pr})");
1682     }
1683     setVar(idx, r_or_p);
1684   }
1685 
1686   void  doJsr                               (int targBCI) {
1687     push(CellTypeState.makeAddr(targBCI));
1688   }
1689 
1690   void  doField                             (boolean is_get, boolean is_static, int idx, int bci) {
1691     // Dig up signature for field in constant pool
1692     ConstantPool cp        = method().getConstants();
1693     int nameAndTypeIdx     = cp.getNameAndTypeRefIndexAt(idx);
1694     int signatureIdx       = cp.getSignatureRefIndexAt(nameAndTypeIdx);
1695     Symbol signature       = cp.getSymbolAt(signatureIdx);
1696 
1697     if (DEBUG) {
1698       System.err.println("doField: signature = " + signature.asString() + ", idx = " + idx +
1699                          ", nameAndTypeIdx = " + nameAndTypeIdx + ", signatureIdx = " + signatureIdx + ", bci = " + bci);
1700     }
1701 
1702     // Parse signature (espcially simple for fields)
1703     // The signature is UFT8 encoded, but the first char is always ASCII for signatures.
1704     char sigch = (char) signature.getByteAt(0);
1705     CellTypeState[] temp = new CellTypeState[4];
1706     CellTypeState[] eff  = sigcharToEffect(sigch, bci, temp);
1707 
1708     CellTypeState[] in = new CellTypeState[4];
1709     CellTypeState[] out;
1710     int i =  0;
1711 
1712     if (is_get) {
1713       out = eff;
1714     } else {
1715       out = epsilonCTS;
1716       i   = copyCTS(in, eff);
1717     }
1718     if (!is_static) in[i++] = CellTypeState.ref;
1719     in[i] = CellTypeState.bottom;
1720     if (Assert.ASSERTS_ENABLED) {
1721       Assert.that(i<=3, "sanity check");
1722     }
1723     pp(in, out);
1724   }
1725 
1726   void  doMethod                            (boolean is_static, boolean is_interface, int idx, int bci) {
1727     // Dig up signature for field in constant pool
1728     ConstantPool cp       = _method.getConstants();
1729     Symbol signature      = cp.getSignatureRefAt(idx);
1730 
1731     // Parse method signature
1732     CellTypeStateList out = new CellTypeStateList(4);
1733     CellTypeStateList in  = new CellTypeStateList(MAXARGSIZE+1);   // Includes result
1734     ComputeCallStack cse  = new ComputeCallStack(signature);
1735 
1736     // Compute return type
1737     int res_length = cse.computeForReturntype(out);
1738 
1739     // Temporary hack.
1740     if (out.get(0).equal(CellTypeState.ref) && out.get(1).equal(CellTypeState.bottom)) {
1741       out.get(0).set(CellTypeState.makeLineRef(bci));
1742     }
1743 
1744     if (Assert.ASSERTS_ENABLED) {
1745       Assert.that(res_length<=4, "max value should be vv");
1746     }
1747 
1748     // Compute arguments
1749     int arg_length = cse.computeForParameters(is_static, in);
1750     if (Assert.ASSERTS_ENABLED) {
1751       Assert.that(arg_length<=MAXARGSIZE, "too many locals");
1752     }
1753 
1754     // Pop arguments
1755     for (int i = arg_length - 1; i >= 0; i--) ppop1(in.get(i));// Do args in reverse order.
1756 
1757     // Report results
1758     if (_report_result_for_send == true) {
1759       fillStackmapForOpcodes(_itr_send, vars(), stack(), _stack_top);
1760       _report_result_for_send = false;
1761     }
1762 
1763     // Push return address
1764     ppush(out);
1765   }
1766 
1767   void  doMultianewarray                    (int dims, int bci) {
1768     if (Assert.ASSERTS_ENABLED) {
1769       Assert.that(dims >= 1, "sanity check");
1770     }
1771     for(int i = dims -1; i >=0; i--) {
1772       ppop1(valCTS);
1773     }
1774     ppush1(CellTypeState.makeLineRef(bci));
1775   }
1776 
1777   void  doMonitorenter                      (int bci) {
1778     CellTypeState actual = pop();
1779     if (_monitor_top == bad_monitors) {
1780       return;
1781     }
1782 
1783     // Bail out when we get repeated locks on an identical monitor.  This case
1784     // isn't too hard to handle and can be made to work if supporting nested
1785     // redundant synchronized statements becomes a priority.
1786     //
1787     // See also "Note" in do_monitorexit(), below.
1788     if (actual.isLockReference()) {
1789       _monitor_top = bad_monitors;
1790       _monitor_safe = false;
1791 
1792       if (TraceMonitorMismatch) {
1793         reportMonitorMismatch("nested redundant lock -- bailout...");
1794       }
1795       return;
1796     }
1797 
1798     CellTypeState lock = CellTypeState.makeLockRef(bci);
1799     checkType(refCTS, actual);
1800     if (!actual.isInfoTop()) {
1801       replaceAllCTSMatches(actual, lock);
1802       monitorPush(lock);
1803     }
1804   }
1805 
1806   void  doMonitorexit                       (int bci) {
1807     CellTypeState actual = pop();
1808     if (_monitor_top == bad_monitors) {
1809       return;
1810     }
1811     checkType(refCTS, actual);
1812     CellTypeState expected = monitorPop();
1813     if (!actual.isLockReference() || !expected.equal(actual)) {
1814       // The monitor we are exiting is not verifiably the one
1815       // on the top of our monitor stack.  This causes a monitor
1816       // mismatch.
1817       _monitor_top = bad_monitors;
1818       _monitor_safe = false;
1819 
1820       // We need to mark this basic block as changed so that
1821       // this monitorexit will be visited again.  We need to
1822       // do this to ensure that we have accounted for the
1823       // possibility that this bytecode will throw an
1824       // exception.
1825       BasicBlock bb = getBasicBlockContaining(bci);
1826       bb.setChanged(true);
1827       bb._monitor_top = bad_monitors;
1828 
1829       if (TraceMonitorMismatch) {
1830         reportMonitorMismatch("improper monitor pair");
1831       }
1832     } else {
1833       // This code is a fix for the case where we have repeated
1834       // locking of the same object in straightline code.  We clear
1835       // out the lock when it is popped from the monitor stack
1836       // and replace it with an unobtrusive reference value that can
1837       // be locked again.
1838       //
1839       // Note: when generateOopMap is fixed to properly handle repeated,
1840       //       nested, redundant locks on the same object, then this
1841       //       fix will need to be removed at that time.
1842       replaceAllCTSMatches(actual, CellTypeState.makeLineRef(bci));
1843     }
1844 
1845     if (_report_for_exit_bci == bci) {
1846       _matching_enter_bci = expected.getMonitorSource();
1847     }
1848   }
1849 
1850   void  doReturnMonitorCheck                () {
1851     if (_monitor_top > 0) {
1852       // The monitor stack must be empty when we leave the method
1853       // for the monitors to be properly matched.
1854       _monitor_safe = false;
1855 
1856       // Since there are no successors to the *return bytecode, it
1857       // isn't necessary to set _monitor_top to bad_monitors.
1858 
1859       if (TraceMonitorMismatch) {
1860         reportMonitorMismatch("non-empty monitor stack at return");
1861       }
1862     }
1863   }
1864 
1865   void  doCheckcast                         () {
1866     CellTypeState actual = pop();
1867     checkType(refCTS, actual);
1868     push(actual);
1869   }
1870 
1871   CellTypeState[] sigcharToEffect           (char sigch, int bci, CellTypeState[] out) {
1872     // Object and array
1873     if (sigch=='L' || sigch=='[') {
1874       out[0] = CellTypeState.makeLineRef(bci);
1875       out[1] = CellTypeState.bottom;
1876       return out;
1877     }
1878     if (sigch == 'J' || sigch == 'D' ) return vvCTS;  // Long and Double
1879     if (sigch == 'V' ) return epsilonCTS;             // Void
1880     return vCTS;                                      // Otherwise
1881   }
1882 
1883   // Copies (optionally bottom/zero terminated) CTS string from "src" into "dst".
1884   //   Does NOT terminate with a bottom. Returns the number of cells copied.
1885   int copyCTS                               (CellTypeState[] dst, CellTypeState[] src) {
1886     int idx = 0;
1887     for (; idx < src.length && !src[idx].isBottom(); idx++) {
1888       dst[idx] = src[idx];
1889     }
1890     return idx;
1891   }
1892 
1893   // Create result set
1894   boolean  _report_result;
1895   boolean  _report_result_for_send;         // Unfortunatly, stackmaps for sends are special, so we need some extra
1896   BytecodeStream _itr_send;                 // variables to handle them properly.
1897 
1898   void  reportResult                        () {
1899     //    if (TraceNewOopMapGeneration) tty.print_cr("Report result pass");
1900 
1901     // We now want to report the result of the parse
1902     _report_result = true;
1903 
1904     // Prolog code
1905     fillStackmapProlog(_gc_points);
1906 
1907     // Mark everything changed, then do one interpretation pass.
1908     for (int i = 0; i<_bb_count; i++) {
1909       if (_basic_blocks[i].isReachable()) {
1910         _basic_blocks[i].setChanged(true);
1911         interpBB(_basic_blocks[i]);
1912       }
1913     }
1914 
1915     // Note: Since we are skipping dead-code when we are reporting results, then
1916     // the no. of encountered gc-points might be fewer than the previously number
1917     // we have counted. (dead-code is a pain - it should be removed before we get here)
1918     fillStackmapEpilog();
1919 
1920     // Report initvars
1921     fillInitVars(_init_vars);
1922 
1923     _report_result = false;
1924   }
1925 
1926   // Initvars
1927   List/*<Integer>*/ _init_vars;
1928 
1929   void  initializeVars                      () {
1930     for (int k = 0; k < _init_vars.size(); k++)
1931       _state.get(((Integer) _init_vars.get(k)).intValue()).set(CellTypeState.makeSlotRef(k));
1932   }
1933 
1934   void  addToRefInitSet                     (int localNo) {
1935     //    if (TraceNewOopMapGeneration)
1936     //      tty.print_cr("Added init vars: %d", localNo);
1937 
1938     Integer local = new Integer(localNo);
1939 
1940     // Is it already in the set?
1941     if (_init_vars.contains(local))
1942       return;
1943 
1944     _init_vars.add(local);
1945   }
1946 
1947   // Conflicts rewrite logic
1948   boolean   _conflict;                      // True, if a conflict occured during interpretation
1949   int       _nof_refval_conflicts;          // No. of conflicts that require rewrites
1950   int[]     _new_var_map;
1951 
1952   void recordRefvalConflict                 (int varNo) {
1953     if (Assert.ASSERTS_ENABLED) {
1954       Assert.that(varNo>=0 && varNo< _max_locals, "index out of range");
1955     }
1956 
1957     if (TraceOopMapRewrites) {
1958       System.err.println("### Conflict detected (local no: " + varNo + ")");
1959     }
1960 
1961     if (_new_var_map == null) {
1962       _new_var_map = new int[_max_locals];
1963       for (int k = 0; k < _max_locals; k++)  _new_var_map[k] = k;
1964     }
1965 
1966     if ( _new_var_map[varNo] == varNo) {
1967       // Check if max. number of locals has been reached
1968       if (_max_locals + _nof_refval_conflicts >= MAX_LOCAL_VARS) {
1969         throw new RuntimeException("Rewriting exceeded local variable limit");
1970       }
1971       _new_var_map[varNo] = _max_locals + _nof_refval_conflicts;
1972       _nof_refval_conflicts++;
1973     }
1974   }
1975 
1976   void rewriteRefvalConflicts               () {
1977     if (_nof_refval_conflicts > 0) {
1978       if (VM.getVM().isDebugging()) {
1979         throw new RuntimeException("Should not reach here (method rewriting should have been done by the VM already)");
1980       } else {
1981         throw new RuntimeException("Method rewriting not yet implemented in Java");
1982       }
1983     }
1984   }
1985   // Rewriting-related routines are not needed here
1986   //  void rewrite_refval_conflict              (int from, int to);
1987   //  bool rewrite_refval_conflict_inst         (BytecodeStream *i, int from, int to);
1988   //  bool rewrite_load_or_store                (BytecodeStream *i, Bytecodes.Code bc, Bytecodes.Code bc0, unsigned int varNo);
1989 
1990   //  bool expand_current_instr                 (int bci, int ilen, int newIlen, u_char inst_buffer[]);
1991   //  bool is_astore                            (BytecodeStream *itr, int *index);
1992   //  bool is_aload                             (BytecodeStream *itr, int *index);
1993 
1994   // List of bci's where a return address is on top of the stack
1995   //  GrowableArray<intptr_t> *_ret_adr_tos;
1996 
1997   //  bool stack_top_holds_ret_addr             (int bci);
1998   //  void compute_ret_adr_at_TOS               ();
1999   //  void update_ret_adr_at_TOS                (int bci, int delta);
2000 
2001   String stateVecToString                   (CellTypeStateList vec, int len) {
2002     for (int i = 0; i < len; i++) {
2003       _state_vec_buf[i] = vec.get(i).toChar();
2004     }
2005     return new String(_state_vec_buf, 0, len);
2006   }
2007 
2008   // Helper method. Can be used in subclasses to fx. calculate gc_points. If the current instuction
2009   // is a control transfer, then calls the jmpFct all possible destinations.
2010   void  retJumpTargetsDo                    (BytecodeStream bcs, JumpClosure closure, int varNo, int[] data) {
2011     CellTypeState ra = vars().get(varNo);
2012     if (!ra.isGoodAddress()) {
2013       throw new RuntimeException("ret returns from two jsr subroutines?");
2014     }
2015     int target = ra.getInfo();
2016 
2017     RetTableEntry rtEnt = _rt.findJsrsForTarget(target);
2018     int bci = bcs.bci();
2019     for (int i = 0; i < rtEnt.nofJsrs(); i++) {
2020       int target_bci = rtEnt.jsrs(i);
2021       // Make sure a jrtRet does not set the changed bit for dead basicblock.
2022       BasicBlock jsr_bb    = getBasicBlockContaining(target_bci - 1);
2023       if (Assert.ASSERTS_ENABLED) {
2024         BasicBlock target_bb = _basic_blocks[1 + bbIndex(jsr_bb)];
2025         Assert.that(target_bb  == getBasicBlockAt(target_bci), "wrong calc. of successor basicblock");
2026       }
2027       boolean alive = jsr_bb.isAlive();
2028       //      if (TraceNewOopMapGeneration) {
2029       //        tty.print("pc = %d, ret . %d alive: %s\n", bci, target_bci, alive ? "true" : "false");
2030       //      }
2031       if (alive) {
2032         closure.process(this, target_bci, data);
2033       }
2034     }
2035   }
2036 
2037   /** If the current instruction in "c" has no effect on control flow,
2038       returns "true".  Otherwise, calls "closure.process()" one or
2039       more times, with "c", an appropriate "pcDelta", and "data" as
2040       arguments, then returns "false".  There is one exception: if the
2041       current instruction is a "ret", returns "false" without calling
2042       "jmpFct". Arrangements for tracking the control flow of a "ret"
2043       must be made externally. */
2044   boolean jumpTargetsDo                     (BytecodeStream bcs, JumpClosure closure, int[] data) {
2045     int bci = bcs.bci();
2046 
2047     switch (bcs.code()) {
2048     case Bytecodes._ifeq:
2049     case Bytecodes._ifne:
2050     case Bytecodes._iflt:
2051     case Bytecodes._ifge:
2052     case Bytecodes._ifgt:
2053     case Bytecodes._ifle:
2054     case Bytecodes._if_icmpeq:
2055     case Bytecodes._if_icmpne:
2056     case Bytecodes._if_icmplt:
2057     case Bytecodes._if_icmpge:
2058     case Bytecodes._if_icmpgt:
2059     case Bytecodes._if_icmple:
2060     case Bytecodes._if_acmpeq:
2061     case Bytecodes._if_acmpne:
2062     case Bytecodes._ifnull:
2063     case Bytecodes._ifnonnull:
2064       closure.process(this, bcs.dest(), data);
2065       closure.process(this, bci + 3, data);
2066       break;
2067 
2068     case Bytecodes._goto:
2069       closure.process(this, bcs.dest(), data);
2070       break;
2071     case Bytecodes._goto_w:
2072       closure.process(this, bcs.dest_w(), data);
2073       break;
2074     case Bytecodes._tableswitch:
2075       {
2076         BytecodeTableswitch tableswitch = BytecodeTableswitch.at(bcs);
2077         int len = tableswitch.length();
2078 
2079         closure.process(this, bci + tableswitch.defaultOffset(), data); /* Default. jump address */
2080         while (--len >= 0) {
2081           closure.process(this, bci + tableswitch.destOffsetAt(len), data);
2082         }
2083         break;
2084       }
2085 
2086     case Bytecodes._fast_linearswitch:     // Java opcodes
2087     case Bytecodes._fast_binaryswitch:     // get_int_table handles conversions
2088     case Bytecodes._lookupswitch:
2089       {
2090         BytecodeLookupswitch lookupswitch = BytecodeLookupswitch.at(bcs);
2091         int npairs = lookupswitch.numberOfPairs();
2092         closure.process(this, bci + lookupswitch.defaultOffset(), data); /* Default. */
2093         while(--npairs >= 0) {
2094           LookupswitchPair pair = lookupswitch.pairAt(npairs);
2095           closure.process(this, bci + pair.offset(), data);
2096         }
2097         break;
2098       }
2099     case Bytecodes._jsr:
2100       Assert.that(bcs.isWide()==false, "sanity check");
2101       closure.process(this, bcs.dest(), data);
2102       break;
2103     case Bytecodes._jsr_w:
2104       closure.process(this, bcs.dest_w(), data);
2105       break;
2106     case Bytecodes._wide:
2107       throw new RuntimeException("Should not reach here");
2108     case Bytecodes._athrow:
2109     case Bytecodes._ireturn:
2110     case Bytecodes._lreturn:
2111     case Bytecodes._freturn:
2112     case Bytecodes._dreturn:
2113     case Bytecodes._areturn:
2114     case Bytecodes._return:
2115     case Bytecodes._ret:
2116       break;
2117     default:
2118       return true;
2119     }
2120     return false;
2121   }
2122 
2123   // Monitor matching
2124   //  int fill_out_arrays                       (int *enter, int *exit, int max);
2125 
2126   //  friend class RelocCallback;
2127 
2128   //----------------------------------------------------------------------
2129   // Public routines for GenerateOopMap
2130   //
2131   public GenerateOopMap(Method method) {
2132     // We have to initialize all variables here, that can be queried direcly
2133     _method = method;
2134     _max_locals=0;
2135     _init_vars = null;
2136     _rt = new RetTable();
2137   }
2138 
2139 
2140   // Compute the map.
2141   public void computeMap() {
2142     if (DEBUG) {
2143       System.err.println("*** GenerateOopMap: computing for " +
2144                          method().getMethodHolder().getName().asString() + "." +
2145                          method().getName().asString() +
2146                          method().getSignature().asString());
2147     }
2148 
2149     // Initialize values
2150     _got_error      = false;
2151     _conflict       = false;
2152     _max_locals     = (int) method().getMaxLocals();
2153     _max_stack      = (int) method().getMaxStack();
2154     _has_exceptions = (method().getExceptionTable().getLength() > 0);
2155     _nof_refval_conflicts = 0;
2156     _init_vars      = new ArrayList(5);  // There are seldom more than 5 init_vars
2157     _report_result  = false;
2158     _report_result_for_send = false;
2159     _report_for_exit_bci = -1;
2160     _new_var_map    = null;
2161     //    _ret_adr_tos    = new GrowableArray<intptr_t>(5);  // 5 seems like a good number;
2162     //    _did_rewriting  = false;
2163     //    _did_relocation = false;
2164 
2165     // FIXME: remove
2166     /*
2167     if (TraceNewOopMapGeneration) {
2168       tty.print("Method name: %s\n", method().name().as_C_string());
2169       if (Verbose) {
2170         _method.print_codes();
2171         tty.print_cr("Exception table:");
2172         typeArrayOop excps = method().exception_table();
2173         for(int i = 0; i < excps.length(); i += 4) {
2174           tty.print_cr("[%d - %d] . %d", excps.int_at(i + 0), excps.int_at(i + 1), excps.int_at(i + 2));
2175         }
2176       }
2177     }
2178     */
2179 
2180     // if no code - do nothing
2181     // compiler needs info
2182     if (method().getCodeSize() == 0 || _max_locals + method().getMaxStack() == 0) {
2183       fillStackmapProlog(0);
2184       fillStackmapEpilog();
2185       return;
2186     }
2187     // Step 1: Compute all jump targets and their return value
2188     if (!_got_error)
2189       _rt.computeRetTable(_method);
2190 
2191     // Step 2: Find all basic blocks and count GC points
2192     if (!_got_error)
2193       markBBHeadersAndCountGCPoints();
2194 
2195     // Step 3: Calculate stack maps
2196     if (!_got_error)
2197       doInterpretation();
2198 
2199     // Step 4:Return results
2200     if (!_got_error && reportResults())
2201       reportResult();
2202 
2203     if (_got_error) {
2204       // We could expand this code to throw somekind of exception (e.g., VerifyException). However,
2205       // an exception thrown in this part of the code is likly to mean that we are executing some
2206       // illegal bytecodes (that the verifier should have caught if turned on), so we will just exit
2207       // with a fatal.
2208       throw new RuntimeException("Illegal bytecode sequence encountered while generating interpreter pointer maps - method should be rejected by verifier.");
2209     }
2210   }
2211 
2212   // Do a callback on fill_stackmap_for_opcodes for basicblock containing bci
2213   public void resultForBasicblock(int bci) {
2214     // FIXME: remove
2215     //    if (TraceNewOopMapGeneration) tty.print_cr("Report result pass for basicblock");
2216 
2217     // We now want to report the result of the parse
2218     _report_result = true;
2219 
2220     // Find basicblock and report results
2221     BasicBlock bb = getBasicBlockContaining(bci);
2222     if (Assert.ASSERTS_ENABLED) {
2223       Assert.that(bb.isReachable(), "getting result from unreachable basicblock");
2224     }
2225     bb.setChanged(true);
2226     interpBB(bb);
2227   }
2228 
2229   // Query
2230   public int maxLocals()                                  { return _max_locals; }
2231   public Method method()                                  { return _method; }
2232 
2233   //  bool did_rewriting()                             { return _did_rewriting; }
2234   //  bool did_relocation()                            { return _did_relocation; }
2235 
2236   //  static void print_time();
2237 
2238   // Monitor query
2239   public boolean monitorSafe()                            { return _monitor_safe; }
2240   // Takes as input the bci of a monitorexit bytecode.
2241   // Returns the bci of the corresponding monitorenter.
2242   // Can only be called safely after computeMap() is run.
2243   public int  getMonitorMatch(int bci) {
2244     if (Assert.ASSERTS_ENABLED) {
2245       Assert.that(_monitor_safe, "Attempt to match monitor in broken code.");
2246     }
2247 
2248     //    if (TraceNewOopMapGeneration)
2249     //      tty.print_cr("Report monitor match for bci : %d", bci);
2250 
2251     // We want to report the line number of the monitorenter.
2252     _report_for_exit_bci = bci;
2253     _matching_enter_bci = -1;
2254 
2255     // Find basicblock and report results
2256     BasicBlock bb = getBasicBlockContaining(bci);
2257     if (bb.isReachable()) {
2258       bb.setChanged(true);
2259       interpBB(bb);
2260       _report_for_exit_bci = -1;
2261       if (Assert.ASSERTS_ENABLED) {
2262         Assert.that(_matching_enter_bci != -1, "monitor matching invariant");
2263       }
2264     }
2265     return _matching_enter_bci;
2266   }
2267 
2268   // Returns a Arena allocated object that contains pairing info.
2269   //  MonitorPairs* get_pairing(Arena *arena);
2270 
2271   // copies monitor pairing info into area; area_count specifies maximum
2272   // possible number of monitor pairs
2273   //  int copy_pairing(int pair_count, MonitorPairs* pairs);
2274 
2275   private int bbIndex(BasicBlock bb) {
2276     for (int i = 0; i < _basic_blocks.length; i++) {
2277       if (_basic_blocks[i] == bb) {
2278         return i;
2279       }
2280     }
2281     throw new RuntimeException("Should have found block");
2282   }
2283 
2284   //----------------------------------------------------------------------
2285   // Specialization methods. Intended use:
2286   // - possibleGCPoint must return true for every bci for which the
2287   //   stackmaps must be returned
2288   // - fillStackmapProlog is called just before the result is
2289   //   reported. The arguments tells the estimated number of gc points
2290   // - fillStackmapForOpcodes is called once for each bytecode index
2291   //   in order (0...code_length-1)
2292   // - fillStackmapEpilog is called after all results has been
2293   //   reported. Note: Since the algorithm does not report stackmaps for
2294   //   deadcode, fewer gc_points might have been encounted than assumed
2295   //   during the epilog. It is the responsibility of the subclass to
2296   //   count the correct number.
2297   // - fillInitVars are called once with the result of the init_vars
2298   //   computation
2299   //
2300   // All these methods are used during a call to computeMap. Note:
2301   // None of the return results are valid after computeMap returns,
2302   // since all values are allocated as resource objects.
2303   //
2304   // All virtual method must be implemented in subclasses
2305   public boolean allowRewrites            ()                              { return false; }
2306   public boolean reportResults            ()                              { return true;  }
2307   public boolean reportInitVars           ()                              { return true;  }
2308   public boolean possibleGCPoint          (BytecodeStream bcs)            { throw new RuntimeException("ShouldNotReachHere"); }
2309   public void fillStackmapProlog          (int nofGCPoints)               { throw new RuntimeException("ShouldNotReachHere"); }
2310   public void fillStackmapEpilog          ()                              { throw new RuntimeException("ShouldNotReachHere"); }
2311   public void fillStackmapForOpcodes      (BytecodeStream bcs,
2312                                            CellTypeStateList vars,
2313                                            CellTypeStateList stack,
2314                                            int stackTop)                  { throw new RuntimeException("ShouldNotReachHere"); }
2315   public void fillInitVars                (List/*<Integer>*/ init_vars)   { throw new RuntimeException("ShouldNotReachHere"); }
2316 }