1 /*
   2  * Copyright (c) 1997, 2016, 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 #include "precompiled.hpp"
  26 #include "interpreter/bytecodeStream.hpp"
  27 #include "oops/generateOopMap.hpp"
  28 #include "oops/oop.inline.hpp"
  29 #include "oops/symbol.hpp"
  30 #include "runtime/handles.inline.hpp"
  31 #include "runtime/java.hpp"
  32 #include "runtime/relocator.hpp"
  33 #include "utilities/bitMap.inline.hpp"
  34 #include "prims/methodHandles.hpp"
  35 
  36 //
  37 //
  38 // Compute stack layouts for each instruction in method.
  39 //
  40 //  Problems:
  41 //  - What to do about jsr with different types of local vars?
  42 //  Need maps that are conditional on jsr path?
  43 //  - Jsr and exceptions should be done more efficiently (the retAddr stuff)
  44 //
  45 //  Alternative:
  46 //  - Could extend verifier to provide this information.
  47 //    For: one fewer abstract interpreter to maintain. Against: the verifier
  48 //    solves a bigger problem so slower (undesirable to force verification of
  49 //    everything?).
  50 //
  51 //  Algorithm:
  52 //    Partition bytecodes into basic blocks
  53 //    For each basic block: store entry state (vars, stack). For instructions
  54 //    inside basic blocks we do not store any state (instead we recompute it
  55 //    from state produced by previous instruction).
  56 //
  57 //    Perform abstract interpretation of bytecodes over this lattice:
  58 //
  59 //                _--'#'--_
  60 //               /  /  \   \
  61 //             /   /     \   \
  62 //            /    |     |     \
  63 //          'r'   'v'   'p'   ' '
  64 //           \     |     |     /
  65 //            \    \     /    /
  66 //              \   \   /    /
  67 //                -- '@' --
  68 //
  69 //    '#'  top, result of conflict merge
  70 //    'r'  reference type
  71 //    'v'  value type
  72 //    'p'  pc type for jsr/ret
  73 //    ' '  uninitialized; never occurs on operand stack in Java
  74 //    '@'  bottom/unexecuted; initial state each bytecode.
  75 //
  76 //    Basic block headers are the only merge points. We use this iteration to
  77 //    compute the information:
  78 //
  79 //    find basic blocks;
  80 //    initialize them with uninitialized state;
  81 //    initialize first BB according to method signature;
  82 //    mark first BB changed
  83 //    while (some BB is changed) do {
  84 //      perform abstract interpration of all bytecodes in BB;
  85 //      merge exit state of BB into entry state of all successor BBs,
  86 //      noting if any of these change;
  87 //    }
  88 //
  89 //  One additional complication is necessary. The jsr instruction pushes
  90 //  a return PC on the stack (a 'p' type in the abstract interpretation).
  91 //  To be able to process "ret" bytecodes, we keep track of these return
  92 //  PC's in a 'retAddrs' structure in abstract interpreter context (when
  93 //  processing a "ret" bytecodes, it is not sufficient to know that it gets
  94 //  an argument of the right type 'p'; we need to know which address it
  95 //  returns to).
  96 //
  97 // (Note this comment is borrowed form the original author of the algorithm)
  98 
  99 // ComputeCallStack
 100 //
 101 // Specialization of SignatureIterator - compute the effects of a call
 102 //
 103 class ComputeCallStack : public SignatureIterator {
 104   CellTypeState *_effect;
 105   int _idx;
 106 
 107   void setup();
 108   void set(CellTypeState state)         { _effect[_idx++] = state; }
 109   int  length()                         { return _idx; };
 110 
 111   virtual void do_bool  ()              { set(CellTypeState::value); };
 112   virtual void do_char  ()              { set(CellTypeState::value); };
 113   virtual void do_float ()              { set(CellTypeState::value); };
 114   virtual void do_byte  ()              { set(CellTypeState::value); };
 115   virtual void do_short ()              { set(CellTypeState::value); };
 116   virtual void do_int   ()              { set(CellTypeState::value); };
 117   virtual void do_void  ()              { set(CellTypeState::bottom);};
 118   virtual void do_object(int begin, int end)  { set(CellTypeState::ref); };
 119   virtual void do_valuetype (int begin, int end)  { set(CellTypeState::valuetype); };
 120   virtual void do_array (int begin, int end)  { set(CellTypeState::ref); };
 121 
 122   void do_double()                      { set(CellTypeState::value);
 123                                           set(CellTypeState::value); }
 124   void do_long  ()                      { set(CellTypeState::value);
 125                                            set(CellTypeState::value); }
 126 
 127 public:
 128   ComputeCallStack(Symbol* signature) : SignatureIterator(signature) {};
 129 
 130   // Compute methods
 131   int compute_for_parameters(bool is_static, bool is_direct, CellTypeState *effect) {
 132     _idx    = 0;
 133     _effect = effect;
 134 
 135     if (is_direct) {
 136       effect[_idx++] = CellTypeState::valuetype;
 137     }
 138     else if (!is_static) {
 139       effect[_idx++] = CellTypeState::ref;
 140     }
 141     iterate_parameters();
 142 
 143     return length();
 144   };
 145 
 146   int compute_for_returntype(CellTypeState *effect) {
 147     _idx    = 0;
 148     _effect = effect;
 149     iterate_returntype();
 150     set(CellTypeState::bottom);  // Always terminate with a bottom state, so ppush works
 151 
 152     return length();
 153   }
 154 };
 155 
 156 //=========================================================================================
 157 // ComputeEntryStack
 158 //
 159 // Specialization of SignatureIterator - in order to set up first stack frame
 160 //
 161 class ComputeEntryStack : public SignatureIterator {
 162   CellTypeState *_effect;
 163   int _idx;
 164 
 165   void setup();
 166   void set(CellTypeState state)         { _effect[_idx++] = state; }
 167   int  length()                         { return _idx; };
 168 
 169   virtual void do_bool  ()              { set(CellTypeState::value); };
 170   virtual void do_char  ()              { set(CellTypeState::value); };
 171   virtual void do_float ()              { set(CellTypeState::value); };
 172   virtual void do_byte  ()              { set(CellTypeState::value); };
 173   virtual void do_short ()              { set(CellTypeState::value); };
 174   virtual void do_int   ()              { set(CellTypeState::value); };
 175   virtual void do_void  ()              { set(CellTypeState::bottom);};
 176   virtual void do_object(int begin, int end)  { set(CellTypeState::make_slot_ref(_idx)); }
 177   virtual void do_array (int begin, int end)  { set(CellTypeState::make_slot_ref(_idx)); }
 178   virtual void do_valuetype(int begin, int end)  { set(CellTypeState::make_slot_valuetype(_idx)); }
 179 
 180 
 181   void do_double()                      { set(CellTypeState::value);
 182                                           set(CellTypeState::value); }
 183   void do_long  ()                      { set(CellTypeState::value);
 184                                           set(CellTypeState::value); }
 185 
 186 public:
 187   ComputeEntryStack(Symbol* signature) : SignatureIterator(signature) {};
 188 
 189   // Compute methods
 190   int compute_for_parameters(bool is_static, CellTypeState *effect) {
 191     _idx    = 0;
 192     _effect = effect;
 193 
 194     if (!is_static)
 195       effect[_idx++] = CellTypeState::make_slot_ref(0);
 196 
 197     iterate_parameters();
 198 
 199     return length();
 200   };
 201 
 202   int compute_for_returntype(CellTypeState *effect) {
 203     _idx    = 0;
 204     _effect = effect;
 205     iterate_returntype();
 206     set(CellTypeState::bottom);  // Always terminate with a bottom state, so ppush works
 207 
 208     return length();
 209   }
 210 };
 211 
 212 //=====================================================================================
 213 //
 214 // Implementation of RetTable/RetTableEntry
 215 //
 216 // Contains function to itereate through all bytecodes
 217 // and find all return entry points
 218 //
 219 int RetTable::_init_nof_entries = 10;
 220 int RetTableEntry::_init_nof_jsrs = 5;
 221 
 222 void RetTableEntry::add_delta(int bci, int delta) {
 223   if (_target_bci > bci) _target_bci += delta;
 224 
 225   for (int k = 0; k < _jsrs->length(); k++) {
 226     int jsr = _jsrs->at(k);
 227     if (jsr > bci) _jsrs->at_put(k, jsr+delta);
 228   }
 229 }
 230 
 231 void RetTable::compute_ret_table(const methodHandle& method) {
 232   BytecodeStream i(method);
 233   Bytecodes::Code bytecode;
 234 
 235   while( (bytecode = i.next()) >= 0) {
 236     switch (bytecode) {
 237       case Bytecodes::_jsr:
 238         add_jsr(i.next_bci(), i.dest());
 239         break;
 240       case Bytecodes::_jsr_w:
 241         add_jsr(i.next_bci(), i.dest_w());
 242         break;
 243     }
 244   }
 245 }
 246 
 247 void RetTable::add_jsr(int return_bci, int target_bci) {
 248   RetTableEntry* entry = _first;
 249 
 250   // Scan table for entry
 251   for (;entry && entry->target_bci() != target_bci; entry = entry->next());
 252 
 253   if (!entry) {
 254     // Allocate new entry and put in list
 255     entry = new RetTableEntry(target_bci, _first);
 256     _first = entry;
 257   }
 258 
 259   // Now "entry" is set.  Make sure that the entry is initialized
 260   // and has room for the new jsr.
 261   entry->add_jsr(return_bci);
 262 }
 263 
 264 RetTableEntry* RetTable::find_jsrs_for_target(int targBci) {
 265   RetTableEntry *cur = _first;
 266 
 267   while(cur) {
 268     assert(cur->target_bci() != -1, "sanity check");
 269     if (cur->target_bci() == targBci)  return cur;
 270     cur = cur->next();
 271   }
 272   ShouldNotReachHere();
 273   return NULL;
 274 }
 275 
 276 // The instruction at bci is changing size by "delta".  Update the return map.
 277 void RetTable::update_ret_table(int bci, int delta) {
 278   RetTableEntry *cur = _first;
 279   while(cur) {
 280     cur->add_delta(bci, delta);
 281     cur = cur->next();
 282   }
 283 }
 284 
 285 //
 286 // Celltype state
 287 //
 288 
 289 CellTypeState CellTypeState::bottom      = CellTypeState::make_bottom();
 290 CellTypeState CellTypeState::uninit      = CellTypeState::make_any(uninit_value);
 291 CellTypeState CellTypeState::ref         = CellTypeState::make_any(ref_conflict);
 292 CellTypeState CellTypeState::value       = CellTypeState::make_any(val_value);
 293 CellTypeState CellTypeState::valuetype   = CellTypeState::make_any(valuetype_conflict);
 294 CellTypeState CellTypeState::refUninit   = CellTypeState::make_any(ref_conflict | uninit_value);
 295 CellTypeState CellTypeState::top         = CellTypeState::make_top();
 296 CellTypeState CellTypeState::addr        = CellTypeState::make_any(addr_conflict);
 297 
 298 // Commonly used constants
 299 static CellTypeState epsilonCTS[1] = { CellTypeState::bottom };
 300 static CellTypeState   refCTS   = CellTypeState::ref;
 301 static CellTypeState   valCTS   = CellTypeState::value;
 302 static CellTypeState valuetypeCTS = CellTypeState::valuetype;
 303 static CellTypeState    vCTS[2] = { CellTypeState::value, CellTypeState::bottom };
 304 static CellTypeState    rCTS[2] = { CellTypeState::ref,   CellTypeState::bottom };
 305 static CellTypeState    qCTS[2] = { CellTypeState::valuetype, CellTypeState::bottom };
 306 static CellTypeState   rrCTS[3] = { CellTypeState::ref,   CellTypeState::ref,   CellTypeState::bottom };
 307 static CellTypeState   vrCTS[3] = { CellTypeState::value, CellTypeState::ref,   CellTypeState::bottom };
 308 static CellTypeState   vvCTS[3] = { CellTypeState::value, CellTypeState::value, CellTypeState::bottom };
 309 static CellTypeState  rvrCTS[4] = { CellTypeState::ref,   CellTypeState::value, CellTypeState::ref,   CellTypeState::bottom };
 310 static CellTypeState  qvrCTS[4] = { CellTypeState::valuetype, CellTypeState::value, CellTypeState::ref, CellTypeState::bottom };
 311 static CellTypeState  vvrCTS[4] = { CellTypeState::value, CellTypeState::value, CellTypeState::ref,   CellTypeState::bottom };
 312 static CellTypeState  vvvCTS[4] = { CellTypeState::value, CellTypeState::value, CellTypeState::value, CellTypeState::bottom };
 313 static CellTypeState vvvrCTS[5] = { CellTypeState::value, CellTypeState::value, CellTypeState::value, CellTypeState::ref,   CellTypeState::bottom };
 314 static CellTypeState vvvvCTS[5] = { CellTypeState::value, CellTypeState::value, CellTypeState::value, CellTypeState::value, CellTypeState::bottom };
 315 
 316 char CellTypeState::to_char() const {
 317   if (can_be_reference()) {
 318     if (can_be_value() || can_be_address() || can_be_valuetype())
 319       return '#';    // Conflict that needs to be rewritten
 320     else
 321       return 'r';
 322   } else if (can_be_valuetype()) {
 323     if (can_be_value() || can_be_address())
 324       return '#';    // Conflict that needs to be rewritten
 325     else
 326       return 'q';
 327   } else if (can_be_value())
 328     return 'v';
 329   else if (can_be_address())
 330     return 'p';
 331   else if (can_be_uninit())
 332     return ' ';
 333   else
 334     return '@';
 335 }
 336 
 337 
 338 // Print a detailed CellTypeState.  Indicate all bits that are set.  If
 339 // the CellTypeState represents an address or a reference, print the
 340 // value of the additional information.
 341 void CellTypeState::print(outputStream *os) {
 342   if (can_be_address()) {
 343     os->print("(p");
 344   } else {
 345     os->print("( ");
 346   }
 347   if (can_be_reference()) {
 348     os->print("r");
 349   } else {
 350     os->print(" ");
 351   }
 352   if (can_be_value()) {
 353     os->print("v");
 354   } else {
 355     os->print(" ");
 356   }
 357   if (can_be_valuetype()) {
 358     os->print("q");
 359   } else {
 360     os->print(" ");
 361   }
 362   if (can_be_uninit()) {
 363     os->print("u|");
 364   } else {
 365     os->print(" |");
 366   }
 367   if (is_info_top()) {
 368     os->print("Top)");
 369   } else if (is_info_bottom()) {
 370     os->print("Bot)");
 371   } else {
 372     if (is_reference()) {
 373       int info = get_info();
 374       int data = info & ~(ref_not_lock_bit | ref_slot_bit);
 375       if (info & ref_not_lock_bit) {
 376         // Not a monitor lock reference.
 377         if (info & ref_slot_bit) {
 378           // slot
 379           os->print("slot%d)", data);
 380         } else {
 381           // line
 382           os->print("line%d)", data);
 383         }
 384       } else {
 385         // lock
 386         os->print("lock%d)", data);
 387       }
 388     } else {
 389       os->print("%d)", get_info());
 390     }
 391   }
 392 }
 393 
 394 //
 395 // Basicblock handling methods
 396 //
 397 
 398 void GenerateOopMap ::initialize_bb() {
 399   _gc_points = 0;
 400   _bb_count  = 0;
 401   _bb_hdr_bits.clear();
 402   _bb_hdr_bits.resize(method()->code_size());
 403 }
 404 
 405 void GenerateOopMap::bb_mark_fct(GenerateOopMap *c, int bci, int *data) {
 406   assert(bci>= 0 && bci < c->method()->code_size(), "index out of bounds");
 407   if (c->is_bb_header(bci))
 408      return;
 409 
 410   if (TraceNewOopMapGeneration) {
 411      tty->print_cr("Basicblock#%d begins at: %d", c->_bb_count, bci);
 412   }
 413   c->set_bbmark_bit(bci);
 414   c->_bb_count++;
 415 }
 416 
 417 
 418 void GenerateOopMap::mark_bbheaders_and_count_gc_points() {
 419   initialize_bb();
 420 
 421   bool fellThrough = false;  // False to get first BB marked.
 422 
 423   // First mark all exception handlers as start of a basic-block
 424   ExceptionTable excps(method());
 425   for(int i = 0; i < excps.length(); i ++) {
 426     bb_mark_fct(this, excps.handler_pc(i), NULL);
 427   }
 428 
 429   // Then iterate through the code
 430   BytecodeStream bcs(_method);
 431   Bytecodes::Code bytecode;
 432 
 433   while( (bytecode = bcs.next()) >= 0) {
 434     int bci = bcs.bci();
 435 
 436     if (!fellThrough)
 437         bb_mark_fct(this, bci, NULL);
 438 
 439     fellThrough = jump_targets_do(&bcs, &GenerateOopMap::bb_mark_fct, NULL);
 440 
 441      /* We will also mark successors of jsr's as basic block headers. */
 442     switch (bytecode) {
 443       case Bytecodes::_jsr:
 444         assert(!fellThrough, "should not happen");
 445         bb_mark_fct(this, bci + Bytecodes::length_for(bytecode), NULL);
 446         break;
 447       case Bytecodes::_jsr_w:
 448         assert(!fellThrough, "should not happen");
 449         bb_mark_fct(this, bci + Bytecodes::length_for(bytecode), NULL);
 450         break;
 451     }
 452 
 453     if (possible_gc_point(&bcs))
 454       _gc_points++;
 455   }
 456 }
 457 
 458 void GenerateOopMap::reachable_basicblock(GenerateOopMap *c, int bci, int *data) {
 459   assert(bci>= 0 && bci < c->method()->code_size(), "index out of bounds");
 460   BasicBlock* bb = c->get_basic_block_at(bci);
 461   if (bb->is_dead()) {
 462     bb->mark_as_alive();
 463     *data = 1; // Mark basicblock as changed
 464   }
 465 }
 466 
 467 
 468 void GenerateOopMap::mark_reachable_code() {
 469   int change = 1; // int to get function pointers to work
 470 
 471   // Mark entry basic block as alive and all exception handlers
 472   _basic_blocks[0].mark_as_alive();
 473   ExceptionTable excps(method());
 474   for(int i = 0; i < excps.length(); i++) {
 475     BasicBlock *bb = get_basic_block_at(excps.handler_pc(i));
 476     // If block is not already alive (due to multiple exception handlers to same bb), then
 477     // make it alive
 478     if (bb->is_dead()) bb->mark_as_alive();
 479   }
 480 
 481   BytecodeStream bcs(_method);
 482 
 483   // Iterate through all basic blocks until we reach a fixpoint
 484   while (change) {
 485     change = 0;
 486 
 487     for (int i = 0; i < _bb_count; i++) {
 488       BasicBlock *bb = &_basic_blocks[i];
 489       if (bb->is_alive()) {
 490         // Position bytecodestream at last bytecode in basicblock
 491         bcs.set_start(bb->_end_bci);
 492         bcs.next();
 493         Bytecodes::Code bytecode = bcs.code();
 494         int bci = bcs.bci();
 495         assert(bci == bb->_end_bci, "wrong bci");
 496 
 497         bool fell_through = jump_targets_do(&bcs, &GenerateOopMap::reachable_basicblock, &change);
 498 
 499         // We will also mark successors of jsr's as alive.
 500         switch (bytecode) {
 501           case Bytecodes::_jsr:
 502           case Bytecodes::_jsr_w:
 503             assert(!fell_through, "should not happen");
 504             reachable_basicblock(this, bci + Bytecodes::length_for(bytecode), &change);
 505             break;
 506         }
 507         if (fell_through) {
 508           // Mark successor as alive
 509           if (bb[1].is_dead()) {
 510             bb[1].mark_as_alive();
 511             change = 1;
 512           }
 513         }
 514       }
 515     }
 516   }
 517 }
 518 
 519 /* If the current instruction in "c" has no effect on control flow,
 520    returns "true".  Otherwise, calls "jmpFct" one or more times, with
 521    "c", an appropriate "pcDelta", and "data" as arguments, then
 522    returns "false".  There is one exception: if the current
 523    instruction is a "ret", returns "false" without calling "jmpFct".
 524    Arrangements for tracking the control flow of a "ret" must be made
 525    externally. */
 526 bool GenerateOopMap::jump_targets_do(BytecodeStream *bcs, jmpFct_t jmpFct, int *data) {
 527   int bci = bcs->bci();
 528 
 529   switch (bcs->code()) {
 530     case Bytecodes::_ifeq:
 531     case Bytecodes::_ifne:
 532     case Bytecodes::_iflt:
 533     case Bytecodes::_ifge:
 534     case Bytecodes::_ifgt:
 535     case Bytecodes::_ifle:
 536     case Bytecodes::_if_icmpeq:
 537     case Bytecodes::_if_icmpne:
 538     case Bytecodes::_if_icmplt:
 539     case Bytecodes::_if_icmpge:
 540     case Bytecodes::_if_icmpgt:
 541     case Bytecodes::_if_icmple:
 542     case Bytecodes::_if_acmpeq:
 543     case Bytecodes::_if_acmpne:
 544     case Bytecodes::_ifnull:
 545     case Bytecodes::_ifnonnull:
 546       (*jmpFct)(this, bcs->dest(), data);
 547       (*jmpFct)(this, bci + 3, data);
 548       break;
 549 
 550     case Bytecodes::_goto:
 551       (*jmpFct)(this, bcs->dest(), data);
 552       break;
 553     case Bytecodes::_goto_w:
 554       (*jmpFct)(this, bcs->dest_w(), data);
 555       break;
 556     case Bytecodes::_tableswitch:
 557       { Bytecode_tableswitch tableswitch(method(), bcs->bcp());
 558         int len = tableswitch.length();
 559 
 560         (*jmpFct)(this, bci + tableswitch.default_offset(), data); /* Default. jump address */
 561         while (--len >= 0) {
 562           (*jmpFct)(this, bci + tableswitch.dest_offset_at(len), data);
 563         }
 564         break;
 565       }
 566 
 567     case Bytecodes::_lookupswitch:
 568       { Bytecode_lookupswitch lookupswitch(method(), bcs->bcp());
 569         int npairs = lookupswitch.number_of_pairs();
 570         (*jmpFct)(this, bci + lookupswitch.default_offset(), data); /* Default. */
 571         while(--npairs >= 0) {
 572           LookupswitchPair pair = lookupswitch.pair_at(npairs);
 573           (*jmpFct)(this, bci + pair.offset(), data);
 574         }
 575         break;
 576       }
 577     case Bytecodes::_jsr:
 578       assert(bcs->is_wide()==false, "sanity check");
 579       (*jmpFct)(this, bcs->dest(), data);
 580 
 581 
 582 
 583       break;
 584     case Bytecodes::_jsr_w:
 585       (*jmpFct)(this, bcs->dest_w(), data);
 586       break;
 587     case Bytecodes::_wide:
 588       ShouldNotReachHere();
 589       return true;
 590       break;
 591     case Bytecodes::_athrow:
 592     case Bytecodes::_ireturn:
 593     case Bytecodes::_lreturn:
 594     case Bytecodes::_freturn:
 595     case Bytecodes::_dreturn:
 596     case Bytecodes::_areturn:
 597     case Bytecodes::_vreturn:
 598     case Bytecodes::_return:
 599     case Bytecodes::_ret:
 600       break;
 601     default:
 602       return true;
 603   }
 604   return false;
 605 }
 606 
 607 /* Requires "pc" to be the head of a basic block; returns that basic
 608    block. */
 609 BasicBlock *GenerateOopMap::get_basic_block_at(int bci) const {
 610   BasicBlock* bb = get_basic_block_containing(bci);
 611   assert(bb->_bci == bci, "should have found BB");
 612   return bb;
 613 }
 614 
 615 // Requires "pc" to be the start of an instruction; returns the basic
 616 //   block containing that instruction. */
 617 BasicBlock  *GenerateOopMap::get_basic_block_containing(int bci) const {
 618   BasicBlock *bbs = _basic_blocks;
 619   int lo = 0, hi = _bb_count - 1;
 620 
 621   while (lo <= hi) {
 622     int m = (lo + hi) / 2;
 623     int mbci = bbs[m]._bci;
 624     int nbci;
 625 
 626     if ( m == _bb_count-1) {
 627       assert( bci >= mbci && bci < method()->code_size(), "sanity check failed");
 628       return bbs+m;
 629     } else {
 630       nbci = bbs[m+1]._bci;
 631     }
 632 
 633     if ( mbci <= bci && bci < nbci) {
 634       return bbs+m;
 635     } else if (mbci < bci) {
 636       lo = m + 1;
 637     } else {
 638       assert(mbci > bci, "sanity check");
 639       hi = m - 1;
 640     }
 641   }
 642 
 643   fatal("should have found BB");
 644   return NULL;
 645 }
 646 
 647 void GenerateOopMap::restore_state(BasicBlock *bb)
 648 {
 649   memcpy(_state, bb->_state, _state_len*sizeof(CellTypeState));
 650   _stack_top = bb->_stack_top;
 651   _monitor_top = bb->_monitor_top;
 652 }
 653 
 654 int GenerateOopMap::next_bb_start_pc(BasicBlock *bb) {
 655  int bbNum = bb - _basic_blocks + 1;
 656  if (bbNum == _bb_count)
 657     return method()->code_size();
 658 
 659  return _basic_blocks[bbNum]._bci;
 660 }
 661 
 662 //
 663 // CellType handling methods
 664 //
 665 
 666 // Allocate memory and throw LinkageError if failure.
 667 #define ALLOC_RESOURCE_ARRAY(var, type, count) \
 668   var = NEW_RESOURCE_ARRAY_RETURN_NULL(type, count);              \
 669   if (var == NULL) {                                              \
 670     report_error("Cannot reserve enough memory to analyze this method"); \
 671     return;                                                       \
 672   }
 673 
 674 
 675 void GenerateOopMap::init_state() {
 676   _state_len     = _max_locals + _max_stack + _max_monitors;
 677   ALLOC_RESOURCE_ARRAY(_state, CellTypeState, _state_len);
 678   memset(_state, 0, _state_len * sizeof(CellTypeState));
 679   int count = MAX3(_max_locals, _max_stack, _max_monitors) + 1/*for null terminator char */;
 680   ALLOC_RESOURCE_ARRAY(_state_vec_buf, char, count);
 681 }
 682 
 683 void GenerateOopMap::make_context_uninitialized() {
 684   CellTypeState* vs = vars();
 685 
 686   for (int i = 0; i < _max_locals; i++)
 687       vs[i] = CellTypeState::uninit;
 688 
 689   _stack_top = 0;
 690   _monitor_top = 0;
 691 }
 692 
 693 int GenerateOopMap::methodsig_to_effect(Symbol* signature, bool is_static, CellTypeState* effect) {
 694   ComputeEntryStack ces(signature);
 695   return ces.compute_for_parameters(is_static, effect);
 696 }
 697 
 698 // Return result of merging cts1 and cts2.
 699 CellTypeState CellTypeState::merge(CellTypeState cts, int slot) const {
 700   CellTypeState result;
 701 
 702   assert(!is_bottom() && !cts.is_bottom(),
 703          "merge of bottom values is handled elsewhere");
 704 
 705   result._state = _state | cts._state;
 706 
 707   // If the top bit is set, we don't need to do any more work.
 708   if (!result.is_info_top()) {
 709     assert((result.can_be_address() || result.can_be_reference() || result.can_be_valuetype()),
 710            "only addresses and references have non-top info");
 711 
 712     if (!equal(cts)) {
 713       // The two values being merged are different.  Raise to top.
 714       if (result.is_reference()) {
 715         result = CellTypeState::make_slot_ref(slot);
 716       } else if (result.is_valuetype()) {
 717         result = CellTypeState::make_slot_valuetype(slot);
 718       } else {
 719         result._state |= info_conflict;
 720       }
 721     }
 722   }
 723   assert(result.is_valid_state(), "checking that CTS merge maintains legal state");
 724 
 725   return result;
 726 }
 727 
 728 // Merge the variable state for locals and stack from cts into bbts.
 729 bool GenerateOopMap::merge_local_state_vectors(CellTypeState* cts,
 730                                                CellTypeState* bbts) {
 731   int i;
 732   int len = _max_locals + _stack_top;
 733   bool change = false;
 734 
 735   for (i = len - 1; i >= 0; i--) {
 736     CellTypeState v = cts[i].merge(bbts[i], i);
 737     change = change || !v.equal(bbts[i]);
 738     bbts[i] = v;
 739   }
 740 
 741   return change;
 742 }
 743 
 744 // Merge the monitor stack state from cts into bbts.
 745 bool GenerateOopMap::merge_monitor_state_vectors(CellTypeState* cts,
 746                                                  CellTypeState* bbts) {
 747   bool change = false;
 748   if (_max_monitors > 0 && _monitor_top != bad_monitors) {
 749     // If there are no monitors in the program, or there has been
 750     // a monitor matching error before this point in the program,
 751     // then we do not merge in the monitor state.
 752 
 753     int base = _max_locals + _max_stack;
 754     int len = base + _monitor_top;
 755     for (int i = len - 1; i >= base; i--) {
 756       CellTypeState v = cts[i].merge(bbts[i], i);
 757 
 758       // Can we prove that, when there has been a change, it will already
 759       // have been detected at this point?  That would make this equal
 760       // check here unnecessary.
 761       change = change || !v.equal(bbts[i]);
 762       bbts[i] = v;
 763     }
 764   }
 765 
 766   return change;
 767 }
 768 
 769 void GenerateOopMap::copy_state(CellTypeState *dst, CellTypeState *src) {
 770   int len = _max_locals + _stack_top;
 771   for (int i = 0; i < len; i++) {
 772     if (src[i].is_nonlock_reference()) {
 773       dst[i] = CellTypeState::make_slot_ref(i);
 774     } else {
 775       dst[i] = src[i];
 776     }
 777   }
 778   if (_max_monitors > 0 && _monitor_top != bad_monitors) {
 779     int base = _max_locals + _max_stack;
 780     len = base + _monitor_top;
 781     for (int i = base; i < len; i++) {
 782       dst[i] = src[i];
 783     }
 784   }
 785 }
 786 
 787 
 788 // Merge the states for the current block and the next.  As long as a
 789 // block is reachable the locals and stack must be merged.  If the
 790 // stack heights don't match then this is a verification error and
 791 // it's impossible to interpret the code.  Simultaneously monitor
 792 // states are being check to see if they nest statically.  If monitor
 793 // depths match up then their states are merged.  Otherwise the
 794 // mismatch is simply recorded and interpretation continues since
 795 // monitor matching is purely informational and doesn't say anything
 796 // about the correctness of the code.
 797 void GenerateOopMap::merge_state_into_bb(BasicBlock *bb) {
 798   guarantee(bb != NULL, "null basicblock");
 799   assert(bb->is_alive(), "merging state into a dead basicblock");
 800 
 801   if (_stack_top == bb->_stack_top) {
 802     // always merge local state even if monitors don't match.
 803     if (merge_local_state_vectors(_state, bb->_state)) {
 804       bb->set_changed(true);
 805     }
 806     if (_monitor_top == bb->_monitor_top) {
 807       // monitors still match so continue merging monitor states.
 808       if (merge_monitor_state_vectors(_state, bb->_state)) {
 809         bb->set_changed(true);
 810       }
 811     } else {
 812       if (TraceMonitorMismatch) {
 813         report_monitor_mismatch("monitor stack height merge conflict");
 814       }
 815       // When the monitor stacks are not matched, we set _monitor_top to
 816       // bad_monitors.  This signals that, from here on, the monitor stack cannot
 817       // be trusted.  In particular, monitorexit bytecodes may throw
 818       // exceptions.  We mark this block as changed so that the change
 819       // propagates properly.
 820       bb->_monitor_top = bad_monitors;
 821       bb->set_changed(true);
 822       _monitor_safe = false;
 823     }
 824   } else if (!bb->is_reachable()) {
 825     // First time we look at this  BB
 826     copy_state(bb->_state, _state);
 827     bb->_stack_top = _stack_top;
 828     bb->_monitor_top = _monitor_top;
 829     bb->set_changed(true);
 830   } else {
 831     verify_error("stack height conflict: %d vs. %d",  _stack_top, bb->_stack_top);
 832   }
 833 }
 834 
 835 void GenerateOopMap::merge_state(GenerateOopMap *gom, int bci, int* data) {
 836    gom->merge_state_into_bb(gom->get_basic_block_at(bci));
 837 }
 838 
 839 void GenerateOopMap::set_var(int localNo, CellTypeState cts) {
 840   assert(cts.is_reference() || cts.is_value() || cts.is_address() || cts.is_valuetype(),
 841          "wrong celltypestate");
 842   if (localNo < 0 || localNo > _max_locals) {
 843     verify_error("variable write error: r%d", localNo);
 844     return;
 845   }
 846   vars()[localNo] = cts;
 847 }
 848 
 849 CellTypeState GenerateOopMap::get_var(int localNo) {
 850   assert(localNo < _max_locals + _nof_refval_conflicts, "variable read error");
 851   if (localNo < 0 || localNo > _max_locals) {
 852     verify_error("variable read error: r%d", localNo);
 853     return valCTS; // just to pick something;
 854   }
 855   return vars()[localNo];
 856 }
 857 
 858 CellTypeState GenerateOopMap::pop() {
 859   if ( _stack_top <= 0) {
 860     verify_error("stack underflow");
 861     return valCTS; // just to pick something
 862   }
 863   return  stack()[--_stack_top];
 864 }
 865 
 866 void GenerateOopMap::push(CellTypeState cts) {
 867   if ( _stack_top >= _max_stack) {
 868     verify_error("stack overflow");
 869     return;
 870   }
 871   stack()[_stack_top++] = cts;
 872 }
 873 
 874 CellTypeState GenerateOopMap::monitor_pop() {
 875   assert(_monitor_top != bad_monitors, "monitor_pop called on error monitor stack");
 876   if (_monitor_top == 0) {
 877     // We have detected a pop of an empty monitor stack.
 878     _monitor_safe = false;
 879      _monitor_top = bad_monitors;
 880 
 881     if (TraceMonitorMismatch) {
 882       report_monitor_mismatch("monitor stack underflow");
 883     }
 884     return CellTypeState::ref; // just to keep the analysis going.
 885   }
 886   return  monitors()[--_monitor_top];
 887 }
 888 
 889 void GenerateOopMap::monitor_push(CellTypeState cts) {
 890   assert(_monitor_top != bad_monitors, "monitor_push called on error monitor stack");
 891   if (_monitor_top >= _max_monitors) {
 892     // Some monitorenter is being executed more than once.
 893     // This means that the monitor stack cannot be simulated.
 894     _monitor_safe = false;
 895     _monitor_top = bad_monitors;
 896 
 897     if (TraceMonitorMismatch) {
 898       report_monitor_mismatch("monitor stack overflow");
 899     }
 900     return;
 901   }
 902   monitors()[_monitor_top++] = cts;
 903 }
 904 
 905 //
 906 // Interpretation handling methods
 907 //
 908 
 909 void GenerateOopMap::do_interpretation()
 910 {
 911   // "i" is just for debugging, so we can detect cases where this loop is
 912   // iterated more than once.
 913   int i = 0;
 914   do {
 915 #ifndef PRODUCT
 916     if (TraceNewOopMapGeneration) {
 917       tty->print("\n\nIteration #%d of do_interpretation loop, method:\n", i);
 918       method()->print_name(tty);
 919       tty->print("\n\n");
 920     }
 921 #endif
 922     _conflict = false;
 923     _monitor_safe = true;
 924     // init_state is now called from init_basic_blocks.  The length of a
 925     // state vector cannot be determined until we have made a pass through
 926     // the bytecodes counting the possible monitor entries.
 927     if (!_got_error) init_basic_blocks();
 928     if (!_got_error) setup_method_entry_state();
 929     if (!_got_error) interp_all();
 930     if (!_got_error) rewrite_refval_conflicts();
 931     i++;
 932   } while (_conflict && !_got_error);
 933 }
 934 
 935 void GenerateOopMap::init_basic_blocks() {
 936   // Note: Could consider reserving only the needed space for each BB's state
 937   // (entry stack may not be of maximal height for every basic block).
 938   // But cumbersome since we don't know the stack heights yet.  (Nor the
 939   // monitor stack heights...)
 940 
 941   ALLOC_RESOURCE_ARRAY(_basic_blocks, BasicBlock, _bb_count);
 942 
 943   // Make a pass through the bytecodes.  Count the number of monitorenters.
 944   // This can be used an upper bound on the monitor stack depth in programs
 945   // which obey stack discipline with their monitor usage.  Initialize the
 946   // known information about basic blocks.
 947   BytecodeStream j(_method);
 948   Bytecodes::Code bytecode;
 949 
 950   int bbNo = 0;
 951   int monitor_count = 0;
 952   int prev_bci = -1;
 953   while( (bytecode = j.next()) >= 0) {
 954     if (j.code() == Bytecodes::_monitorenter) {
 955       monitor_count++;
 956     }
 957 
 958     int bci = j.bci();
 959     if (is_bb_header(bci)) {
 960       // Initialize the basicblock structure
 961       BasicBlock *bb   = _basic_blocks + bbNo;
 962       bb->_bci         = bci;
 963       bb->_max_locals  = _max_locals;
 964       bb->_max_stack   = _max_stack;
 965       bb->set_changed(false);
 966       bb->_stack_top   = BasicBlock::_dead_basic_block; // Initialize all basicblocks are dead.
 967       bb->_monitor_top = bad_monitors;
 968 
 969       if (bbNo > 0) {
 970         _basic_blocks[bbNo - 1]._end_bci = prev_bci;
 971       }
 972 
 973       bbNo++;
 974     }
 975     // Remember prevous bci.
 976     prev_bci = bci;
 977   }
 978   // Set
 979   _basic_blocks[bbNo-1]._end_bci = prev_bci;
 980 
 981 
 982   // Check that the correct number of basicblocks was found
 983   if (bbNo !=_bb_count) {
 984     if (bbNo < _bb_count) {
 985       verify_error("jump into the middle of instruction?");
 986       return;
 987     } else {
 988       verify_error("extra basic blocks - should not happen?");
 989       return;
 990     }
 991   }
 992 
 993   _max_monitors = monitor_count;
 994 
 995   // Now that we have a bound on the depth of the monitor stack, we can
 996   // initialize the CellTypeState-related information.
 997   init_state();
 998 
 999   // We allocate space for all state-vectors for all basicblocks in one huge
1000   // chunk.  Then in the next part of the code, we set a pointer in each
1001   // _basic_block that points to each piece.
1002 
1003   // The product of bbNo and _state_len can get large if there are lots of
1004   // basic blocks and stack/locals/monitors.  Need to check to make sure
1005   // we don't overflow the capacity of a pointer.
1006   if ((unsigned)bbNo > UINTPTR_MAX / sizeof(CellTypeState) / _state_len) {
1007     report_error("The amount of memory required to analyze this method "
1008                  "exceeds addressable range");
1009     return;
1010   }
1011 
1012   CellTypeState *basicBlockState;
1013   ALLOC_RESOURCE_ARRAY(basicBlockState, CellTypeState, bbNo * _state_len);
1014   memset(basicBlockState, 0, bbNo * _state_len * sizeof(CellTypeState));
1015 
1016   // Make a pass over the basicblocks and assign their state vectors.
1017   for (int blockNum=0; blockNum < bbNo; blockNum++) {
1018     BasicBlock *bb = _basic_blocks + blockNum;
1019     bb->_state = basicBlockState + blockNum * _state_len;
1020 
1021 #ifdef ASSERT
1022     if (blockNum + 1 < bbNo) {
1023       address bcp = _method->bcp_from(bb->_end_bci);
1024       int bc_len = Bytecodes::java_length_at(_method(), bcp);
1025       assert(bb->_end_bci + bc_len == bb[1]._bci, "unmatched bci info in basicblock");
1026     }
1027 #endif
1028   }
1029 #ifdef ASSERT
1030   { BasicBlock *bb = &_basic_blocks[bbNo-1];
1031     address bcp = _method->bcp_from(bb->_end_bci);
1032     int bc_len = Bytecodes::java_length_at(_method(), bcp);
1033     assert(bb->_end_bci + bc_len == _method->code_size(), "wrong end bci");
1034   }
1035 #endif
1036 
1037   // Mark all alive blocks
1038   mark_reachable_code();
1039 }
1040 
1041 void GenerateOopMap::setup_method_entry_state() {
1042 
1043     // Initialize all locals to 'uninit' and set stack-height to 0
1044     make_context_uninitialized();
1045 
1046     // Initialize CellState type of arguments
1047     methodsig_to_effect(method()->signature(), method()->is_static(), vars());
1048 
1049     // If some references must be pre-assigned to null, then set that up
1050     initialize_vars();
1051 
1052     // This is the start state
1053     merge_state_into_bb(&_basic_blocks[0]);
1054 
1055     assert(_basic_blocks[0].changed(), "we are not getting off the ground");
1056 }
1057 
1058 // The instruction at bci is changing size by "delta".  Update the basic blocks.
1059 void GenerateOopMap::update_basic_blocks(int bci, int delta,
1060                                          int new_method_size) {
1061   assert(new_method_size >= method()->code_size() + delta,
1062          "new method size is too small");
1063 
1064   BitMap::bm_word_t* new_bb_hdr_bits =
1065     NEW_RESOURCE_ARRAY(BitMap::bm_word_t,
1066                        BitMap::word_align_up(new_method_size));
1067   _bb_hdr_bits.set_map(new_bb_hdr_bits);
1068   _bb_hdr_bits.set_size(new_method_size);
1069   _bb_hdr_bits.clear();
1070 
1071 
1072   for(int k = 0; k < _bb_count; k++) {
1073     if (_basic_blocks[k]._bci > bci) {
1074       _basic_blocks[k]._bci     += delta;
1075       _basic_blocks[k]._end_bci += delta;
1076     }
1077     _bb_hdr_bits.at_put(_basic_blocks[k]._bci, true);
1078   }
1079 }
1080 
1081 //
1082 // Initvars handling
1083 //
1084 
1085 void GenerateOopMap::initialize_vars() {
1086   for (int k = 0; k < _init_vars->length(); k++)
1087     _state[_init_vars->at(k)] = CellTypeState::make_slot_ref(k);
1088 }
1089 
1090 void GenerateOopMap::add_to_ref_init_set(int localNo) {
1091 
1092   if (TraceNewOopMapGeneration)
1093     tty->print_cr("Added init vars: %d", localNo);
1094 
1095   // Is it already in the set?
1096   if (_init_vars->contains(localNo) )
1097     return;
1098 
1099    _init_vars->append(localNo);
1100 }
1101 
1102 //
1103 // Interpreration code
1104 //
1105 
1106 void GenerateOopMap::interp_all() {
1107   bool change = true;
1108 
1109   while (change && !_got_error) {
1110     change = false;
1111     for (int i = 0; i < _bb_count && !_got_error; i++) {
1112       BasicBlock *bb = &_basic_blocks[i];
1113       if (bb->changed()) {
1114          if (_got_error) return;
1115          change = true;
1116          bb->set_changed(false);
1117          interp_bb(bb);
1118       }
1119     }
1120   }
1121 }
1122 
1123 void GenerateOopMap::interp_bb(BasicBlock *bb) {
1124 
1125   // We do not want to do anything in case the basic-block has not been initialized. This
1126   // will happen in the case where there is dead-code hang around in a method.
1127   assert(bb->is_reachable(), "should be reachable or deadcode exist");
1128   restore_state(bb);
1129 
1130   BytecodeStream itr(_method);
1131 
1132   // Set iterator interval to be the current basicblock
1133   int lim_bci = next_bb_start_pc(bb);
1134   itr.set_interval(bb->_bci, lim_bci);
1135   assert(lim_bci != bb->_bci, "must be at least one instruction in a basicblock");
1136   itr.next(); // read first instruction
1137 
1138   // Iterates through all bytecodes except the last in a basic block.
1139   // We handle the last one special, since there is controlflow change.
1140   while(itr.next_bci() < lim_bci && !_got_error) {
1141     if (_has_exceptions || _monitor_top != 0) {
1142       // We do not need to interpret the results of exceptional
1143       // continuation from this instruction when the method has no
1144       // exception handlers and the monitor stack is currently
1145       // empty.
1146       do_exception_edge(&itr);
1147     }
1148     interp1(&itr);
1149     itr.next();
1150   }
1151 
1152   // Handle last instruction.
1153   if (!_got_error) {
1154     assert(itr.next_bci() == lim_bci, "must point to end");
1155     if (_has_exceptions || _monitor_top != 0) {
1156       do_exception_edge(&itr);
1157     }
1158     interp1(&itr);
1159 
1160     bool fall_through = jump_targets_do(&itr, GenerateOopMap::merge_state, NULL);
1161     if (_got_error)  return;
1162 
1163     if (itr.code() == Bytecodes::_ret) {
1164       assert(!fall_through, "cannot be set if ret instruction");
1165       // Automatically handles 'wide' ret indicies
1166       ret_jump_targets_do(&itr, GenerateOopMap::merge_state, itr.get_index(), NULL);
1167     } else if (fall_through) {
1168      // Hit end of BB, but the instr. was a fall-through instruction,
1169      // so perform transition as if the BB ended in a "jump".
1170      if (lim_bci != bb[1]._bci) {
1171        verify_error("bytecodes fell through last instruction");
1172        return;
1173      }
1174      merge_state_into_bb(bb + 1);
1175     }
1176   }
1177 }
1178 
1179 void GenerateOopMap::do_exception_edge(BytecodeStream* itr) {
1180   // Only check exception edge, if bytecode can trap
1181   if (!Bytecodes::can_trap(itr->code())) return;
1182   switch (itr->code()) {
1183     case Bytecodes::_aload_0:
1184       // These bytecodes can trap for rewriting.  We need to assume that
1185       // they do not throw exceptions to make the monitor analysis work.
1186       return;
1187 
1188     case Bytecodes::_ireturn:
1189     case Bytecodes::_lreturn:
1190     case Bytecodes::_freturn:
1191     case Bytecodes::_dreturn:
1192     case Bytecodes::_areturn:
1193     case Bytecodes::_return:
1194       // If the monitor stack height is not zero when we leave the method,
1195       // then we are either exiting with a non-empty stack or we have
1196       // found monitor trouble earlier in our analysis.  In either case,
1197       // assume an exception could be taken here.
1198       if (_monitor_top == 0) {
1199         return;
1200       }
1201       break;
1202 
1203     case Bytecodes::_monitorexit:
1204       // If the monitor stack height is bad_monitors, then we have detected a
1205       // monitor matching problem earlier in the analysis.  If the
1206       // monitor stack height is 0, we are about to pop a monitor
1207       // off of an empty stack.  In either case, the bytecode
1208       // could throw an exception.
1209       if (_monitor_top != bad_monitors && _monitor_top != 0) {
1210         return;
1211       }
1212       break;
1213   }
1214 
1215   if (_has_exceptions) {
1216     int bci = itr->bci();
1217     ExceptionTable exct(method());
1218     for(int i = 0; i< exct.length(); i++) {
1219       int start_pc   = exct.start_pc(i);
1220       int end_pc     = exct.end_pc(i);
1221       int handler_pc = exct.handler_pc(i);
1222       int catch_type = exct.catch_type_index(i);
1223 
1224       if (start_pc <= bci && bci < end_pc) {
1225         BasicBlock *excBB = get_basic_block_at(handler_pc);
1226         guarantee(excBB != NULL, "no basic block for exception");
1227         CellTypeState *excStk = excBB->stack();
1228         CellTypeState *cOpStck = stack();
1229         CellTypeState cOpStck_0 = cOpStck[0];
1230         int cOpStackTop = _stack_top;
1231 
1232         // Exception stacks are always the same.
1233         assert(method()->max_stack() > 0, "sanity check");
1234 
1235         // We remembered the size and first element of "cOpStck"
1236         // above; now we temporarily set them to the appropriate
1237         // values for an exception handler. */
1238         cOpStck[0] = CellTypeState::make_slot_ref(_max_locals);
1239         _stack_top = 1;
1240 
1241         merge_state_into_bb(excBB);
1242 
1243         // Now undo the temporary change.
1244         cOpStck[0] = cOpStck_0;
1245         _stack_top = cOpStackTop;
1246 
1247         // If this is a "catch all" handler, then we do not need to
1248         // consider any additional handlers.
1249         if (catch_type == 0) {
1250           return;
1251         }
1252       }
1253     }
1254   }
1255 
1256   // It is possible that none of the exception handlers would have caught
1257   // the exception.  In this case, we will exit the method.  We must
1258   // ensure that the monitor stack is empty in this case.
1259   if (_monitor_top == 0) {
1260     return;
1261   }
1262 
1263   // We pessimistically assume that this exception can escape the
1264   // method. (It is possible that it will always be caught, but
1265   // we don't care to analyse the types of the catch clauses.)
1266 
1267   // We don't set _monitor_top to bad_monitors because there are no successors
1268   // to this exceptional exit.
1269 
1270   if (TraceMonitorMismatch && _monitor_safe) {
1271     // We check _monitor_safe so that we only report the first mismatched
1272     // exceptional exit.
1273     report_monitor_mismatch("non-empty monitor stack at exceptional exit");
1274   }
1275   _monitor_safe = false;
1276 
1277 }
1278 
1279 void GenerateOopMap::report_monitor_mismatch(const char *msg) {
1280 #ifndef PRODUCT
1281   tty->print("    Monitor mismatch in method ");
1282   method()->print_short_name(tty);
1283   tty->print_cr(": %s", msg);
1284 #endif
1285 }
1286 
1287 void GenerateOopMap::print_states(outputStream *os,
1288                                   CellTypeState* vec, int num) {
1289   for (int i = 0; i < num; i++) {
1290     vec[i].print(tty);
1291   }
1292 }
1293 
1294 // Print the state values at the current bytecode.
1295 void GenerateOopMap::print_current_state(outputStream   *os,
1296                                          BytecodeStream *currentBC,
1297                                          bool            detailed) {
1298 
1299   if (detailed) {
1300     os->print("     %4d vars     = ", currentBC->bci());
1301     print_states(os, vars(), _max_locals);
1302     os->print("    %s", Bytecodes::name(currentBC->code()));
1303     switch(currentBC->code()) {
1304       case Bytecodes::_invokevirtual:
1305       case Bytecodes::_invokedirect:
1306       case Bytecodes::_invokespecial:
1307       case Bytecodes::_invokestatic:
1308       case Bytecodes::_invokedynamic:
1309       case Bytecodes::_invokeinterface:
1310         int idx = currentBC->has_index_u4() ? currentBC->get_index_u4() : currentBC->get_index_u2_cpcache();
1311         ConstantPool* cp      = method()->constants();
1312         int nameAndTypeIdx    = cp->name_and_type_ref_index_at(idx);
1313         int signatureIdx      = cp->signature_ref_index_at(nameAndTypeIdx);
1314         Symbol* signature     = cp->symbol_at(signatureIdx);
1315         os->print("%s", signature->as_C_string());
1316     }
1317     os->cr();
1318     os->print("          stack    = ");
1319     print_states(os, stack(), _stack_top);
1320     os->cr();
1321     if (_monitor_top != bad_monitors) {
1322       os->print("          monitors = ");
1323       print_states(os, monitors(), _monitor_top);
1324     } else {
1325       os->print("          [bad monitor stack]");
1326     }
1327     os->cr();
1328   } else {
1329     os->print("    %4d  vars = '%s' ", currentBC->bci(),  state_vec_to_string(vars(), _max_locals));
1330     os->print("     stack = '%s' ", state_vec_to_string(stack(), _stack_top));
1331     if (_monitor_top != bad_monitors) {
1332       os->print("  monitors = '%s'  \t%s", state_vec_to_string(monitors(), _monitor_top), Bytecodes::name(currentBC->code()));
1333     } else {
1334       os->print("  [bad monitor stack]");
1335     }
1336     switch(currentBC->code()) {
1337       case Bytecodes::_invokevirtual:
1338       case Bytecodes::_invokedirect:
1339       case Bytecodes::_invokespecial:
1340       case Bytecodes::_invokestatic:
1341       case Bytecodes::_invokedynamic:
1342       case Bytecodes::_invokeinterface:
1343         int idx = currentBC->has_index_u4() ? currentBC->get_index_u4() : currentBC->get_index_u2_cpcache();
1344         ConstantPool* cp      = method()->constants();
1345         int nameAndTypeIdx    = cp->name_and_type_ref_index_at(idx);
1346         int signatureIdx      = cp->signature_ref_index_at(nameAndTypeIdx);
1347         Symbol* signature     = cp->symbol_at(signatureIdx);
1348         os->print("%s", signature->as_C_string());
1349     }
1350     os->cr();
1351   }
1352 }
1353 
1354 // Sets the current state to be the state after executing the
1355 // current instruction, starting in the current state.
1356 void GenerateOopMap::interp1(BytecodeStream *itr) {
1357   if (TraceNewOopMapGeneration) {
1358     print_current_state(tty, itr, TraceNewOopMapGenerationDetailed);
1359   }
1360 
1361   // Should we report the results? Result is reported *before* the instruction at the current bci is executed.
1362   // However, not for calls. For calls we do not want to include the arguments, so we postpone the reporting until
1363   // they have been popped (in method ppl).
1364   if (_report_result == true) {
1365     switch(itr->code()) {
1366       case Bytecodes::_invokevirtual:
1367       case Bytecodes::_invokedirect:
1368       case Bytecodes::_invokespecial:
1369       case Bytecodes::_invokestatic:
1370       case Bytecodes::_invokedynamic:
1371       case Bytecodes::_invokeinterface:
1372         _itr_send = itr;
1373         _report_result_for_send = true;
1374         break;
1375       default:
1376        fill_stackmap_for_opcodes(itr, vars(), stack(), _stack_top);
1377        break;
1378     }
1379   }
1380 
1381   // abstract interpretation of current opcode
1382   switch(itr->code()) {
1383     case Bytecodes::_nop:                                           break;
1384     case Bytecodes::_goto:                                          break;
1385     case Bytecodes::_goto_w:                                        break;
1386     case Bytecodes::_iinc:                                          break;
1387     case Bytecodes::_return:            do_return_monitor_check();
1388                                         break;
1389 
1390     case Bytecodes::_aconst_null:
1391     case Bytecodes::_new:               ppush1(CellTypeState::make_line_ref(itr->bci()));
1392                                         break;
1393 
1394     case Bytecodes::_vnew:
1395     case Bytecodes::_vdefault:
1396     case Bytecodes::_vwithfield:        ppush1(CellTypeState::make_line_valuetype(itr->bci()));
1397                                         break;
1398 
1399     case Bytecodes::_iconst_m1:
1400     case Bytecodes::_iconst_0:
1401     case Bytecodes::_iconst_1:
1402     case Bytecodes::_iconst_2:
1403     case Bytecodes::_iconst_3:
1404     case Bytecodes::_iconst_4:
1405     case Bytecodes::_iconst_5:
1406     case Bytecodes::_fconst_0:
1407     case Bytecodes::_fconst_1:
1408     case Bytecodes::_fconst_2:
1409     case Bytecodes::_bipush:
1410     case Bytecodes::_sipush:            ppush1(valCTS);             break;
1411 
1412     case Bytecodes::_lconst_0:
1413     case Bytecodes::_lconst_1:
1414     case Bytecodes::_dconst_0:
1415     case Bytecodes::_dconst_1:          ppush(vvCTS);               break;
1416 
1417     case Bytecodes::_ldc2_w:            ppush(vvCTS);               break;
1418 
1419     case Bytecodes::_ldc:               // fall through:
1420     case Bytecodes::_ldc_w:             do_ldc(itr->bci());         break;
1421 
1422     case Bytecodes::_iload:
1423     case Bytecodes::_fload:             ppload(vCTS, itr->get_index()); break;
1424 
1425     case Bytecodes::_lload:
1426     case Bytecodes::_dload:             ppload(vvCTS,itr->get_index()); break;
1427 
1428     case Bytecodes::_aload:             ppload(rCTS, itr->get_index()); break;
1429 
1430     case Bytecodes::_vload:             ppload(qCTS, itr->get_index()); break;
1431 
1432     case Bytecodes::_iload_0:
1433     case Bytecodes::_fload_0:           ppload(vCTS, 0);            break;
1434     case Bytecodes::_iload_1:
1435     case Bytecodes::_fload_1:           ppload(vCTS, 1);            break;
1436     case Bytecodes::_iload_2:
1437     case Bytecodes::_fload_2:           ppload(vCTS, 2);            break;
1438     case Bytecodes::_iload_3:
1439     case Bytecodes::_fload_3:           ppload(vCTS, 3);            break;
1440 
1441     case Bytecodes::_lload_0:
1442     case Bytecodes::_dload_0:           ppload(vvCTS, 0);           break;
1443     case Bytecodes::_lload_1:
1444     case Bytecodes::_dload_1:           ppload(vvCTS, 1);           break;
1445     case Bytecodes::_lload_2:
1446     case Bytecodes::_dload_2:           ppload(vvCTS, 2);           break;
1447     case Bytecodes::_lload_3:
1448     case Bytecodes::_dload_3:           ppload(vvCTS, 3);           break;
1449 
1450     case Bytecodes::_aload_0:           ppload(rCTS, 0);            break;
1451     case Bytecodes::_aload_1:           ppload(rCTS, 1);            break;
1452     case Bytecodes::_aload_2:           ppload(rCTS, 2);            break;
1453     case Bytecodes::_aload_3:           ppload(rCTS, 3);            break;
1454 
1455     case Bytecodes::_iaload:
1456     case Bytecodes::_faload:
1457     case Bytecodes::_baload:
1458     case Bytecodes::_caload:
1459     case Bytecodes::_saload:            pp(vrCTS, vCTS); break;
1460 
1461     case Bytecodes::_laload:            pp(vrCTS, vvCTS);  break;
1462     case Bytecodes::_daload:            pp(vrCTS, vvCTS); break;
1463 
1464     case Bytecodes::_aaload:            pp_new_ref(vrCTS, itr->bci()); break;
1465     case Bytecodes::_vaload:            pp_new_valuetype(vrCTS, itr->bci()); break;
1466 
1467     case Bytecodes::_istore:
1468     case Bytecodes::_fstore:            ppstore(vCTS, itr->get_index()); break;
1469 
1470     case Bytecodes::_lstore:
1471     case Bytecodes::_dstore:            ppstore(vvCTS, itr->get_index()); break;
1472 
1473     case Bytecodes::_astore:            do_astore(itr->get_index());     break;
1474     case Bytecodes::_vstore:            do_vstore(itr->get_index()); break;
1475 
1476     case Bytecodes::_istore_0:
1477     case Bytecodes::_fstore_0:          ppstore(vCTS, 0);           break;
1478     case Bytecodes::_istore_1:
1479     case Bytecodes::_fstore_1:          ppstore(vCTS, 1);           break;
1480     case Bytecodes::_istore_2:
1481     case Bytecodes::_fstore_2:          ppstore(vCTS, 2);           break;
1482     case Bytecodes::_istore_3:
1483     case Bytecodes::_fstore_3:          ppstore(vCTS, 3);           break;
1484 
1485     case Bytecodes::_lstore_0:
1486     case Bytecodes::_dstore_0:          ppstore(vvCTS, 0);          break;
1487     case Bytecodes::_lstore_1:
1488     case Bytecodes::_dstore_1:          ppstore(vvCTS, 1);          break;
1489     case Bytecodes::_lstore_2:
1490     case Bytecodes::_dstore_2:          ppstore(vvCTS, 2);          break;
1491     case Bytecodes::_lstore_3:
1492     case Bytecodes::_dstore_3:          ppstore(vvCTS, 3);          break;
1493 
1494     case Bytecodes::_astore_0:          do_astore(0);               break;
1495     case Bytecodes::_astore_1:          do_astore(1);               break;
1496     case Bytecodes::_astore_2:          do_astore(2);               break;
1497     case Bytecodes::_astore_3:          do_astore(3);               break;
1498 
1499     case Bytecodes::_iastore:
1500     case Bytecodes::_fastore:
1501     case Bytecodes::_bastore:
1502     case Bytecodes::_castore:
1503     case Bytecodes::_sastore:           ppop(vvrCTS);               break;
1504     case Bytecodes::_lastore:
1505     case Bytecodes::_dastore:           ppop(vvvrCTS);              break;
1506     case Bytecodes::_aastore:           ppop(rvrCTS);               break;
1507     case Bytecodes::_vastore:           ppop(qvrCTS);               break;
1508 
1509     case Bytecodes::_pop:               ppop_any(1);                break;
1510     case Bytecodes::_pop2:              ppop_any(2);                break;
1511 
1512     case Bytecodes::_dup:               ppdupswap(1, "11");         break;
1513     case Bytecodes::_dup_x1:            ppdupswap(2, "121");        break;
1514     case Bytecodes::_dup_x2:            ppdupswap(3, "1321");       break;
1515     case Bytecodes::_dup2:              ppdupswap(2, "2121");       break;
1516     case Bytecodes::_dup2_x1:           ppdupswap(3, "21321");      break;
1517     case Bytecodes::_dup2_x2:           ppdupswap(4, "214321");     break;
1518     case Bytecodes::_swap:              ppdupswap(2, "12");         break;
1519 
1520     case Bytecodes::_iadd:
1521     case Bytecodes::_fadd:
1522     case Bytecodes::_isub:
1523     case Bytecodes::_fsub:
1524     case Bytecodes::_imul:
1525     case Bytecodes::_fmul:
1526     case Bytecodes::_idiv:
1527     case Bytecodes::_fdiv:
1528     case Bytecodes::_irem:
1529     case Bytecodes::_frem:
1530     case Bytecodes::_ishl:
1531     case Bytecodes::_ishr:
1532     case Bytecodes::_iushr:
1533     case Bytecodes::_iand:
1534     case Bytecodes::_ior:
1535     case Bytecodes::_ixor:
1536     case Bytecodes::_l2f:
1537     case Bytecodes::_l2i:
1538     case Bytecodes::_d2f:
1539     case Bytecodes::_d2i:
1540     case Bytecodes::_fcmpl:
1541     case Bytecodes::_fcmpg:             pp(vvCTS, vCTS); break;
1542 
1543     case Bytecodes::_ladd:
1544     case Bytecodes::_dadd:
1545     case Bytecodes::_lsub:
1546     case Bytecodes::_dsub:
1547     case Bytecodes::_lmul:
1548     case Bytecodes::_dmul:
1549     case Bytecodes::_ldiv:
1550     case Bytecodes::_ddiv:
1551     case Bytecodes::_lrem:
1552     case Bytecodes::_drem:
1553     case Bytecodes::_land:
1554     case Bytecodes::_lor:
1555     case Bytecodes::_lxor:              pp(vvvvCTS, vvCTS); break;
1556 
1557     case Bytecodes::_ineg:
1558     case Bytecodes::_fneg:
1559     case Bytecodes::_i2f:
1560     case Bytecodes::_f2i:
1561     case Bytecodes::_i2c:
1562     case Bytecodes::_i2s:
1563     case Bytecodes::_i2b:               pp(vCTS, vCTS); break;
1564 
1565     case Bytecodes::_lneg:
1566     case Bytecodes::_dneg:
1567     case Bytecodes::_l2d:
1568     case Bytecodes::_d2l:               pp(vvCTS, vvCTS); break;
1569 
1570     case Bytecodes::_lshl:
1571     case Bytecodes::_lshr:
1572     case Bytecodes::_lushr:             pp(vvvCTS, vvCTS); break;
1573 
1574     case Bytecodes::_i2l:
1575     case Bytecodes::_i2d:
1576     case Bytecodes::_f2l:
1577     case Bytecodes::_f2d:               pp(vCTS, vvCTS); break;
1578 
1579     case Bytecodes::_lcmp:              pp(vvvvCTS, vCTS); break;
1580     case Bytecodes::_dcmpl:
1581     case Bytecodes::_dcmpg:             pp(vvvvCTS, vCTS); break;
1582 
1583     case Bytecodes::_ifeq:
1584     case Bytecodes::_ifne:
1585     case Bytecodes::_iflt:
1586     case Bytecodes::_ifge:
1587     case Bytecodes::_ifgt:
1588     case Bytecodes::_ifle:
1589     case Bytecodes::_tableswitch:       ppop1(valCTS);
1590                                         break;
1591     case Bytecodes::_ireturn:
1592     case Bytecodes::_freturn:           do_return_monitor_check();
1593                                         ppop1(valCTS);
1594                                         break;
1595     case Bytecodes::_if_icmpeq:
1596     case Bytecodes::_if_icmpne:
1597     case Bytecodes::_if_icmplt:
1598     case Bytecodes::_if_icmpge:
1599     case Bytecodes::_if_icmpgt:
1600     case Bytecodes::_if_icmple:         ppop(vvCTS);
1601                                         break;
1602 
1603     case Bytecodes::_lreturn:           do_return_monitor_check();
1604                                         ppop(vvCTS);
1605                                         break;
1606 
1607     case Bytecodes::_dreturn:           do_return_monitor_check();
1608                                         ppop(vvCTS);
1609                                         break;
1610 
1611     case Bytecodes::_if_acmpeq:
1612     case Bytecodes::_if_acmpne:         ppop(rrCTS);                 break;
1613 
1614     case Bytecodes::_jsr:               do_jsr(itr->dest());         break;
1615     case Bytecodes::_jsr_w:             do_jsr(itr->dest_w());       break;
1616 
1617     case Bytecodes::_getstatic:         do_field(true,  true, false,  itr->get_index_u2_cpcache(), itr->bci()); break;
1618     case Bytecodes::_putstatic:         do_field(false, true, false,  itr->get_index_u2_cpcache(), itr->bci()); break;
1619     case Bytecodes::_getfield:          do_field(true,  false, false, itr->get_index_u2_cpcache(), itr->bci()); break;
1620     case Bytecodes::_putfield:          do_field(false, false, false, itr->get_index_u2_cpcache(), itr->bci()); break;
1621     case Bytecodes::_vgetfield:         do_field(true,  false, true , itr->get_index_u2_cpcache(), itr->bci()); break;
1622 
1623     case Bytecodes::_invokeinterface:
1624     case Bytecodes::_invokevirtual:
1625     case Bytecodes::_invokespecial:     do_method(false, false, itr->get_index_u2_cpcache(), itr->bci()); break;
1626     case Bytecodes::_invokedirect:      do_method(false, true , itr->get_index_u2_cpcache(), itr->bci()); break;
1627     case Bytecodes::_invokestatic:      do_method(true,  false, itr->get_index_u2_cpcache(), itr->bci()); break;
1628     case Bytecodes::_invokedynamic:     do_method(true,  false, itr->get_index_u4(),         itr->bci()); break;
1629     case Bytecodes::_newarray:
1630     case Bytecodes::_anewarray:         pp_new_ref(vCTS, itr->bci()); break;
1631     case Bytecodes::_checkcast:         do_checkcast(); break;
1632     case Bytecodes::_arraylength:
1633     case Bytecodes::_instanceof:        pp(rCTS, vCTS); break;
1634     case Bytecodes::_monitorenter:      do_monitorenter(itr->bci()); break;
1635     case Bytecodes::_monitorexit:       do_monitorexit(itr->bci()); break;
1636 
1637     case Bytecodes::_athrow:            // handled by do_exception_edge() BUT ...
1638                                         // vlh(apple): do_exception_edge() does not get
1639                                         // called if method has no exception handlers
1640                                         if ((!_has_exceptions) && (_monitor_top > 0)) {
1641                                           _monitor_safe = false;
1642                                         }
1643                                         break;
1644 
1645     case Bytecodes::_areturn:           do_return_monitor_check();
1646                                         ppop1(refCTS);
1647                                         break;
1648 
1649     case Bytecodes::_vreturn:           do_return_monitor_check();
1650                                         ppop1(valuetypeCTS);
1651                                         break;
1652 
1653     case Bytecodes::_ifnull:
1654     case Bytecodes::_ifnonnull:         ppop1(refCTS); break;
1655     case Bytecodes::_multianewarray:    do_multianewarray(*(itr->bcp()+3), itr->bci()); break;
1656 
1657     case Bytecodes::_vbox:              pp_new_ref(qCTS, itr->bci());       break;
1658     case Bytecodes::_vunbox:            pp_new_valuetype(rCTS, itr->bci()); break;
1659 
1660     case Bytecodes::_wide:              fatal("Iterator should skip this bytecode"); break;
1661     case Bytecodes::_ret:                                           break;
1662 
1663     // Java opcodes
1664     case Bytecodes::_lookupswitch:      ppop1(valCTS);             break;
1665 
1666     default:
1667          tty->print("unexpected opcode: %d\n", itr->code());
1668          ShouldNotReachHere();
1669     break;
1670   }
1671 }
1672 
1673 void GenerateOopMap::check_type(CellTypeState expected, CellTypeState actual) {
1674   if (!expected.equal_kind(actual)) {
1675     verify_error("wrong type on stack (found: %c expected: %c)", actual.to_char(), expected.to_char());
1676   }
1677 }
1678 
1679 void GenerateOopMap::ppstore(CellTypeState *in, int loc_no) {
1680   while(!(*in).is_bottom()) {
1681     CellTypeState expected =*in++;
1682     CellTypeState actual   = pop();
1683     check_type(expected, actual);
1684     assert(loc_no >= 0, "sanity check");
1685     set_var(loc_no++, actual);
1686   }
1687 }
1688 
1689 void GenerateOopMap::ppload(CellTypeState *out, int loc_no) {
1690   while(!(*out).is_bottom()) {
1691     CellTypeState out1 = *out++;
1692     CellTypeState vcts = get_var(loc_no);
1693     assert(out1.can_be_reference() || out1.can_be_value() || out1.can_be_valuetype(),
1694            "can only load refs. and values.");
1695     if (out1.is_reference()) {
1696       assert(loc_no>=0, "sanity check");
1697       if (!vcts.is_reference()) {
1698         // We were asked to push a reference, but the type of the
1699         // variable can be something else
1700         _conflict = true;
1701         if (vcts.can_be_uninit()) {
1702           // It is a ref-uninit conflict (at least). If there are other
1703           // problems, we'll get them in the next round
1704           add_to_ref_init_set(loc_no);
1705           vcts = out1;
1706         } else {
1707           // It wasn't a ref-uninit conflict. So must be a
1708           // ref-val or ref-pc conflict. Split the variable.
1709           record_refval_conflict(loc_no);
1710           vcts = out1;
1711         }
1712         push(out1); // recover...
1713       } else {
1714         push(vcts); // preserve reference.
1715       }
1716       // Otherwise it is a conflict, but one that verification would
1717       // have caught if illegal. In particular, it can't be a topCTS
1718       // resulting from mergeing two difference pcCTS's since the verifier
1719       // would have rejected any use of such a merge.
1720     } else {
1721       push(out1); // handle val/init conflict
1722     }
1723     loc_no++;
1724   }
1725 }
1726 
1727 void GenerateOopMap::ppdupswap(int poplen, const char *out) {
1728   CellTypeState actual[5];
1729   assert(poplen < 5, "this must be less than length of actual vector");
1730 
1731   // pop all arguments
1732   for(int i = 0; i < poplen; i++) actual[i] = pop();
1733 
1734   // put them back
1735   char push_ch = *out++;
1736   while (push_ch != '\0') {
1737     int idx = push_ch - '1';
1738     assert(idx >= 0 && idx < poplen, "wrong arguments");
1739     push(actual[idx]);
1740     push_ch = *out++;
1741   }
1742 }
1743 
1744 void GenerateOopMap::ppop1(CellTypeState out) {
1745   CellTypeState actual = pop();
1746   check_type(out, actual);
1747 }
1748 
1749 void GenerateOopMap::ppop(CellTypeState *out) {
1750   while (!(*out).is_bottom()) {
1751     ppop1(*out++);
1752   }
1753 }
1754 
1755 void GenerateOopMap::ppush1(CellTypeState in) {
1756   assert(in.is_reference() || in.is_value() || in.is_valuetype(), "sanity check");
1757   push(in);
1758 }
1759 
1760 void GenerateOopMap::ppush(CellTypeState *in) {
1761   while (!(*in).is_bottom()) {
1762     ppush1(*in++);
1763   }
1764 }
1765 
1766 void GenerateOopMap::pp(CellTypeState *in, CellTypeState *out) {
1767   ppop(in);
1768   ppush(out);
1769 }
1770 
1771 void GenerateOopMap::pp_new_ref(CellTypeState *in, int bci) {
1772   ppop(in);
1773   ppush1(CellTypeState::make_line_ref(bci));
1774 }
1775 
1776 void GenerateOopMap::pp_new_valuetype(CellTypeState *in, int bci) {
1777   ppop(in);
1778   ppush1(CellTypeState::make_line_valuetype(bci));
1779 }
1780 
1781 void GenerateOopMap::ppop_any(int poplen) {
1782   if (_stack_top >= poplen) {
1783     _stack_top -= poplen;
1784   } else {
1785     verify_error("stack underflow");
1786   }
1787 }
1788 
1789 // Replace all occurences of the state 'match' with the state 'replace'
1790 // in our current state vector.
1791 void GenerateOopMap::replace_all_CTS_matches(CellTypeState match,
1792                                              CellTypeState replace) {
1793   int i;
1794   int len = _max_locals + _stack_top;
1795   bool change = false;
1796 
1797   for (i = len - 1; i >= 0; i--) {
1798     if (match.equal(_state[i])) {
1799       _state[i] = replace;
1800     }
1801   }
1802 
1803   if (_monitor_top > 0) {
1804     int base = _max_locals + _max_stack;
1805     len = base + _monitor_top;
1806     for (i = len - 1; i >= base; i--) {
1807       if (match.equal(_state[i])) {
1808         _state[i] = replace;
1809       }
1810     }
1811   }
1812 }
1813 
1814 void GenerateOopMap::do_checkcast() {
1815   CellTypeState actual = pop();
1816   check_type(refCTS, actual);
1817   push(actual);
1818 }
1819 
1820 void GenerateOopMap::do_monitorenter(int bci) {
1821   CellTypeState actual = pop();
1822   if (_monitor_top == bad_monitors) {
1823     return;
1824   }
1825 
1826   // Bail out when we get repeated locks on an identical monitor.  This case
1827   // isn't too hard to handle and can be made to work if supporting nested
1828   // redundant synchronized statements becomes a priority.
1829   //
1830   // See also "Note" in do_monitorexit(), below.
1831   if (actual.is_lock_reference()) {
1832     _monitor_top = bad_monitors;
1833     _monitor_safe = false;
1834 
1835     if (TraceMonitorMismatch) {
1836       report_monitor_mismatch("nested redundant lock -- bailout...");
1837     }
1838     return;
1839   }
1840 
1841   CellTypeState lock = CellTypeState::make_lock_ref(bci);
1842   check_type(refCTS, actual);
1843   if (!actual.is_info_top()) {
1844     replace_all_CTS_matches(actual, lock);
1845     monitor_push(lock);
1846   }
1847 }
1848 
1849 void GenerateOopMap::do_monitorexit(int bci) {
1850   CellTypeState actual = pop();
1851   if (_monitor_top == bad_monitors) {
1852     return;
1853   }
1854   check_type(refCTS, actual);
1855   CellTypeState expected = monitor_pop();
1856   if (!actual.is_lock_reference() || !expected.equal(actual)) {
1857     // The monitor we are exiting is not verifiably the one
1858     // on the top of our monitor stack.  This causes a monitor
1859     // mismatch.
1860     _monitor_top = bad_monitors;
1861     _monitor_safe = false;
1862 
1863     // We need to mark this basic block as changed so that
1864     // this monitorexit will be visited again.  We need to
1865     // do this to ensure that we have accounted for the
1866     // possibility that this bytecode will throw an
1867     // exception.
1868     BasicBlock* bb = get_basic_block_containing(bci);
1869     guarantee(bb != NULL, "no basic block for bci");
1870     bb->set_changed(true);
1871     bb->_monitor_top = bad_monitors;
1872 
1873     if (TraceMonitorMismatch) {
1874       report_monitor_mismatch("improper monitor pair");
1875     }
1876   } else {
1877     // This code is a fix for the case where we have repeated
1878     // locking of the same object in straightline code.  We clear
1879     // out the lock when it is popped from the monitor stack
1880     // and replace it with an unobtrusive reference value that can
1881     // be locked again.
1882     //
1883     // Note: when generateOopMap is fixed to properly handle repeated,
1884     //       nested, redundant locks on the same object, then this
1885     //       fix will need to be removed at that time.
1886     replace_all_CTS_matches(actual, CellTypeState::make_line_ref(bci));
1887   }
1888 }
1889 
1890 void GenerateOopMap::do_return_monitor_check() {
1891   if (_monitor_top > 0) {
1892     // The monitor stack must be empty when we leave the method
1893     // for the monitors to be properly matched.
1894     _monitor_safe = false;
1895 
1896     // Since there are no successors to the *return bytecode, it
1897     // isn't necessary to set _monitor_top to bad_monitors.
1898 
1899     if (TraceMonitorMismatch) {
1900       report_monitor_mismatch("non-empty monitor stack at return");
1901     }
1902   }
1903 }
1904 
1905 void GenerateOopMap::do_jsr(int targ_bci) {
1906   push(CellTypeState::make_addr(targ_bci));
1907 }
1908 
1909 
1910 
1911 void GenerateOopMap::do_ldc(int bci) {
1912   Bytecode_loadconstant ldc(method(), bci);
1913   ConstantPool* cp  = method()->constants();
1914   constantTag tag = cp->tag_at(ldc.pool_index()); // idx is index in resolved_references
1915   BasicType       bt  = ldc.result_type();
1916   CellTypeState   cts;
1917   if (tag.basic_type() == T_OBJECT) {
1918     assert(!tag.is_string_index() && !tag.is_klass_index(), "Unexpected index tag");
1919     assert(bt == T_OBJECT, "Guard is incorrect");
1920     cts = CellTypeState::make_line_ref(bci);
1921   } else {
1922     assert(bt != T_OBJECT, "Guard is incorrect");
1923     cts = valCTS;
1924   }
1925   ppush1(cts);
1926 }
1927 
1928 void GenerateOopMap::do_multianewarray(int dims, int bci) {
1929   assert(dims >= 1, "sanity check");
1930   for(int i = dims -1; i >=0; i--) {
1931     ppop1(valCTS);
1932   }
1933   ppush1(CellTypeState::make_line_ref(bci));
1934 }
1935 
1936 void GenerateOopMap::do_astore(int idx) {
1937   CellTypeState r_or_p = pop();
1938   if (!r_or_p.is_address() && !r_or_p.is_reference()) {
1939     // We actually expected ref or pc, but we only report that we expected a ref. It does not
1940     // really matter (at least for now)
1941     verify_error("wrong type on stack (found: %c, expected: {pr})", r_or_p.to_char());
1942     return;
1943   }
1944   set_var(idx, r_or_p);
1945 }
1946 
1947 void GenerateOopMap::do_vstore(int idx) {
1948   CellTypeState q = pop();
1949   if (!q.is_valuetype()) {
1950     verify_error("wrong type on stack (found: %c, expected: {q})", q.to_char());
1951     return;
1952   }
1953   set_var(idx, q);
1954 }
1955 
1956 // Copies bottom/zero terminated CTS string from "src" into "dst".
1957 //   Does NOT terminate with a bottom. Returns the number of cells copied.
1958 int GenerateOopMap::copy_cts(CellTypeState *dst, CellTypeState *src) {
1959   int idx = 0;
1960   while (!src[idx].is_bottom()) {
1961     dst[idx] = src[idx];
1962     idx++;
1963   }
1964   return idx;
1965 }
1966 
1967 void GenerateOopMap::do_field(int is_get, int is_static, int is_valuetype, int idx, int bci) {
1968   assert(!(!is_get && is_valuetype), "Invalid configuration: vputfield doesn't exist");
1969   // Dig up signature for field in constant pool
1970   ConstantPool* cp     = method()->constants();
1971   int nameAndTypeIdx     = cp->name_and_type_ref_index_at(idx);
1972   int signatureIdx       = cp->signature_ref_index_at(nameAndTypeIdx);
1973   Symbol* signature      = cp->symbol_at(signatureIdx);
1974 
1975   // Parse signature (espcially simple for fields)
1976   assert(signature->utf8_length() > 0, "field signatures cannot have zero length");
1977   // The signature is UFT8 encoded, but the first char is always ASCII for signatures.
1978   char sigch = (char)*(signature->base());
1979   CellTypeState temp[4];
1980   CellTypeState *eff  = sigchar_to_effect(sigch, bci, temp);
1981 
1982   CellTypeState in[4];
1983   CellTypeState *out;
1984   int i =  0;
1985 
1986   if (is_get) {
1987     out = eff;
1988   } else {
1989     out = epsilonCTS;
1990     i   = copy_cts(in, eff);
1991   }
1992   if (!is_static) {
1993     if (is_valuetype) {
1994       in[i++] = CellTypeState::valuetype;
1995     } else {
1996       in[i++] = CellTypeState::ref;
1997     }
1998   }
1999   in[i] = CellTypeState::bottom;
2000   assert(i<=3, "sanity check");
2001   pp(in, out);
2002 }
2003 
2004 void GenerateOopMap::do_method(int is_static, int is_direct, int idx, int bci) {
2005  // Dig up signature for field in constant pool
2006   ConstantPool* cp  = _method->constants();
2007   Symbol* signature   = cp->signature_ref_at(idx);
2008 
2009   // Parse method signature
2010   CellTypeState out[4];
2011   CellTypeState in[MAXARGSIZE+1];   // Includes result
2012   ComputeCallStack cse(signature);
2013 
2014   // Compute return type
2015   int res_length=  cse.compute_for_returntype(out);
2016 
2017   // Temporary hack.
2018   if (out[0].equal(CellTypeState::ref) && out[1].equal(CellTypeState::bottom)) {
2019     out[0] = CellTypeState::make_line_ref(bci);
2020   }
2021 
2022   assert(res_length<=4, "max value should be vv");
2023 
2024   // Compute arguments
2025   int arg_length = cse.compute_for_parameters(is_static != 0, is_direct != 0, in);
2026   assert(arg_length<=MAXARGSIZE, "too many locals");
2027 
2028   // Pop arguments
2029   for (int i = arg_length - 1; i >= 0; i--) ppop1(in[i]);// Do args in reverse order.
2030 
2031   // Report results
2032   if (_report_result_for_send == true) {
2033      fill_stackmap_for_opcodes(_itr_send, vars(), stack(), _stack_top);
2034      _report_result_for_send = false;
2035   }
2036 
2037   // Push return address
2038   ppush(out);
2039 }
2040 
2041 // This is used to parse the signature for fields, since they are very simple...
2042 CellTypeState *GenerateOopMap::sigchar_to_effect(char sigch, int bci, CellTypeState *out) {
2043   // Object and array
2044   if (sigch=='L' || sigch=='[') {
2045     out[0] = CellTypeState::make_line_ref(bci);
2046     out[1] = CellTypeState::bottom;
2047     return out;
2048   }
2049   if (sigch == 'Q') {
2050     out[0] = CellTypeState::make_line_valuetype(bci);
2051     out[1] = CellTypeState::bottom;
2052     return out;
2053   }
2054   if (sigch == 'J' || sigch == 'D' ) return vvCTS;  // Long and Double
2055   if (sigch == 'V' ) return epsilonCTS;             // Void
2056   return vCTS;                                      // Otherwise
2057 }
2058 
2059 long GenerateOopMap::_total_byte_count = 0;
2060 elapsedTimer GenerateOopMap::_total_oopmap_time;
2061 
2062 // This function assumes "bcs" is at a "ret" instruction and that the vars
2063 // state is valid for that instruction. Furthermore, the ret instruction
2064 // must be the last instruction in "bb" (we store information about the
2065 // "ret" in "bb").
2066 void GenerateOopMap::ret_jump_targets_do(BytecodeStream *bcs, jmpFct_t jmpFct, int varNo, int *data) {
2067   CellTypeState ra = vars()[varNo];
2068   if (!ra.is_good_address()) {
2069     verify_error("ret returns from two jsr subroutines?");
2070     return;
2071   }
2072   int target = ra.get_info();
2073 
2074   RetTableEntry* rtEnt = _rt.find_jsrs_for_target(target);
2075   int bci = bcs->bci();
2076   for (int i = 0; i < rtEnt->nof_jsrs(); i++) {
2077     int target_bci = rtEnt->jsrs(i);
2078     // Make sure a jrtRet does not set the changed bit for dead basicblock.
2079     BasicBlock* jsr_bb    = get_basic_block_containing(target_bci - 1);
2080     debug_only(BasicBlock* target_bb = &jsr_bb[1];)
2081     assert(target_bb  == get_basic_block_at(target_bci), "wrong calc. of successor basicblock");
2082     bool alive = jsr_bb->is_alive();
2083     if (TraceNewOopMapGeneration) {
2084       tty->print("pc = %d, ret -> %d alive: %s\n", bci, target_bci, alive ? "true" : "false");
2085     }
2086     if (alive) jmpFct(this, target_bci, data);
2087   }
2088 }
2089 
2090 //
2091 // Debug method
2092 //
2093 char* GenerateOopMap::state_vec_to_string(CellTypeState* vec, int len) {
2094 #ifdef ASSERT
2095   int checklen = MAX3(_max_locals, _max_stack, _max_monitors) + 1;
2096   assert(len < checklen, "state_vec_buf overflow");
2097 #endif
2098   for (int i = 0; i < len; i++) _state_vec_buf[i] = vec[i].to_char();
2099   _state_vec_buf[len] = 0;
2100   return _state_vec_buf;
2101 }
2102 
2103 void GenerateOopMap::print_time() {
2104   tty->print_cr ("Accumulated oopmap times:");
2105   tty->print_cr ("---------------------------");
2106   tty->print_cr ("  Total : %3.3f sec.", GenerateOopMap::_total_oopmap_time.seconds());
2107   tty->print_cr ("  (%3.0f bytecodes per sec) ",
2108   GenerateOopMap::_total_byte_count / GenerateOopMap::_total_oopmap_time.seconds());
2109 }
2110 
2111 //
2112 //  ============ Main Entry Point ===========
2113 //
2114 GenerateOopMap::GenerateOopMap(const methodHandle& method) {
2115   // We have to initialize all variables here, that can be queried directly
2116   _method = method;
2117   _max_locals=0;
2118   _init_vars = NULL;
2119 
2120 #ifndef PRODUCT
2121   // If we are doing a detailed trace, include the regular trace information.
2122   if (TraceNewOopMapGenerationDetailed) {
2123     TraceNewOopMapGeneration = true;
2124   }
2125 #endif
2126 }
2127 
2128 void GenerateOopMap::compute_map(TRAPS) {
2129 #ifndef PRODUCT
2130   if (TimeOopMap2) {
2131     method()->print_short_name(tty);
2132     tty->print("  ");
2133   }
2134   if (TimeOopMap) {
2135     _total_byte_count += method()->code_size();
2136   }
2137 #endif
2138   TraceTime t_single("oopmap time", TimeOopMap2);
2139   TraceTime t_all(NULL, &_total_oopmap_time, TimeOopMap);
2140 
2141   // Initialize values
2142   _got_error      = false;
2143   _conflict       = false;
2144   _max_locals     = method()->max_locals();
2145   _max_stack      = method()->max_stack();
2146   _has_exceptions = (method()->has_exception_handler());
2147   _nof_refval_conflicts = 0;
2148   _init_vars      = new GrowableArray<intptr_t>(5);  // There are seldom more than 5 init_vars
2149   _report_result  = false;
2150   _report_result_for_send = false;
2151   _new_var_map    = NULL;
2152   _ret_adr_tos    = new GrowableArray<intptr_t>(5);  // 5 seems like a good number;
2153   _did_rewriting  = false;
2154   _did_relocation = false;
2155 
2156   if (TraceNewOopMapGeneration) {
2157     tty->print("Method name: %s\n", method()->name()->as_C_string());
2158     if (Verbose) {
2159       _method->print_codes();
2160       tty->print_cr("Exception table:");
2161       ExceptionTable excps(method());
2162       for(int i = 0; i < excps.length(); i ++) {
2163         tty->print_cr("[%d - %d] -> %d",
2164                       excps.start_pc(i), excps.end_pc(i), excps.handler_pc(i));
2165       }
2166     }
2167   }
2168 
2169   // if no code - do nothing
2170   // compiler needs info
2171   if (method()->code_size() == 0 || _max_locals + method()->max_stack() == 0) {
2172     fill_stackmap_prolog(0);
2173     fill_stackmap_epilog();
2174     return;
2175   }
2176   // Step 1: Compute all jump targets and their return value
2177   if (!_got_error)
2178     _rt.compute_ret_table(_method);
2179 
2180   // Step 2: Find all basic blocks and count GC points
2181   if (!_got_error)
2182     mark_bbheaders_and_count_gc_points();
2183 
2184   // Step 3: Calculate stack maps
2185   if (!_got_error)
2186     do_interpretation();
2187 
2188   // Step 4:Return results
2189   if (!_got_error && report_results())
2190      report_result();
2191 
2192   if (_got_error) {
2193     THROW_HANDLE(_exception);
2194   }
2195 }
2196 
2197 // Error handling methods
2198 // These methods create an exception for the current thread which is thrown
2199 // at the bottom of the call stack, when it returns to compute_map().  The
2200 // _got_error flag controls execution.  NOT TODO: The VM exception propagation
2201 // mechanism using TRAPS/CHECKs could be used here instead but it would need
2202 // to be added as a parameter to every function and checked for every call.
2203 // The tons of extra code it would generate didn't seem worth the change.
2204 //
2205 void GenerateOopMap::error_work(const char *format, va_list ap) {
2206   _got_error = true;
2207   char msg_buffer[512];
2208   vsnprintf(msg_buffer, sizeof(msg_buffer), format, ap);
2209   // Append method name
2210   char msg_buffer2[512];
2211   jio_snprintf(msg_buffer2, sizeof(msg_buffer2), "%s in method %s", msg_buffer, method()->name()->as_C_string());
2212   _exception = Exceptions::new_exception(Thread::current(),
2213                 vmSymbols::java_lang_LinkageError(), msg_buffer2);
2214 }
2215 
2216 void GenerateOopMap::report_error(const char *format, ...) {
2217   va_list ap;
2218   va_start(ap, format);
2219   error_work(format, ap);
2220 }
2221 
2222 void GenerateOopMap::verify_error(const char *format, ...) {
2223   // We do not distinguish between different types of errors for verification
2224   // errors.  Let the verifier give a better message.
2225   const char *msg = "Illegal class file encountered. Try running with -Xverify:all";
2226   _got_error = true;
2227   // Append method name
2228   char msg_buffer2[512];
2229   jio_snprintf(msg_buffer2, sizeof(msg_buffer2), "%s in method %s", msg,
2230                method()->name()->as_C_string());
2231   _exception = Exceptions::new_exception(Thread::current(),
2232                 vmSymbols::java_lang_LinkageError(), msg_buffer2);
2233 }
2234 
2235 //
2236 // Report result opcodes
2237 //
2238 void GenerateOopMap::report_result() {
2239 
2240   if (TraceNewOopMapGeneration) tty->print_cr("Report result pass");
2241 
2242   // We now want to report the result of the parse
2243   _report_result = true;
2244 
2245   // Prolog code
2246   fill_stackmap_prolog(_gc_points);
2247 
2248    // Mark everything changed, then do one interpretation pass.
2249   for (int i = 0; i<_bb_count; i++) {
2250     if (_basic_blocks[i].is_reachable()) {
2251       _basic_blocks[i].set_changed(true);
2252       interp_bb(&_basic_blocks[i]);
2253     }
2254   }
2255 
2256   // Note: Since we are skipping dead-code when we are reporting results, then
2257   // the no. of encountered gc-points might be fewer than the previously number
2258   // we have counted. (dead-code is a pain - it should be removed before we get here)
2259   fill_stackmap_epilog();
2260 
2261   // Report initvars
2262   fill_init_vars(_init_vars);
2263 
2264   _report_result = false;
2265 }
2266 
2267 void GenerateOopMap::result_for_basicblock(int bci) {
2268  if (TraceNewOopMapGeneration) tty->print_cr("Report result pass for basicblock");
2269 
2270   // We now want to report the result of the parse
2271   _report_result = true;
2272 
2273   // Find basicblock and report results
2274   BasicBlock* bb = get_basic_block_containing(bci);
2275   guarantee(bb != NULL, "no basic block for bci");
2276   assert(bb->is_reachable(), "getting result from unreachable basicblock");
2277   bb->set_changed(true);
2278   interp_bb(bb);
2279 }
2280 
2281 //
2282 // Conflict handling code
2283 //
2284 
2285 void GenerateOopMap::record_refval_conflict(int varNo) {
2286   assert(varNo>=0 && varNo< _max_locals, "index out of range");
2287 
2288   if (TraceOopMapRewrites) {
2289      tty->print("### Conflict detected (local no: %d)\n", varNo);
2290   }
2291 
2292   if (!_new_var_map) {
2293     _new_var_map = NEW_RESOURCE_ARRAY(int, _max_locals);
2294     for (int k = 0; k < _max_locals; k++)  _new_var_map[k] = k;
2295   }
2296 
2297   if ( _new_var_map[varNo] == varNo) {
2298     // Check if max. number of locals has been reached
2299     if (_max_locals + _nof_refval_conflicts >= MAX_LOCAL_VARS) {
2300       report_error("Rewriting exceeded local variable limit");
2301       return;
2302     }
2303     _new_var_map[varNo] = _max_locals + _nof_refval_conflicts;
2304     _nof_refval_conflicts++;
2305   }
2306 }
2307 
2308 void GenerateOopMap::rewrite_refval_conflicts()
2309 {
2310   // We can get here two ways: Either a rewrite conflict was detected, or
2311   // an uninitialize reference was detected. In the second case, we do not
2312   // do any rewriting, we just want to recompute the reference set with the
2313   // new information
2314 
2315   int nof_conflicts = 0;              // Used for debugging only
2316 
2317   if ( _nof_refval_conflicts == 0 )
2318      return;
2319 
2320   // Check if rewrites are allowed in this parse.
2321   if (!allow_rewrites() && !IgnoreRewrites) {
2322     fatal("Rewriting method not allowed at this stage");
2323   }
2324 
2325 
2326   // This following flag is to tempoary supress rewrites. The locals that might conflict will
2327   // all be set to contain values. This is UNSAFE - however, until the rewriting has been completely
2328   // tested it is nice to have.
2329   if (IgnoreRewrites) {
2330     if (Verbose) {
2331        tty->print("rewrites suppressed for local no. ");
2332        for (int l = 0; l < _max_locals; l++) {
2333          if (_new_var_map[l] != l) {
2334            tty->print("%d ", l);
2335            vars()[l] = CellTypeState::value;
2336          }
2337        }
2338        tty->cr();
2339     }
2340 
2341     // That was that...
2342     _new_var_map = NULL;
2343     _nof_refval_conflicts = 0;
2344     _conflict = false;
2345 
2346     return;
2347   }
2348 
2349   // Tracing flag
2350   _did_rewriting = true;
2351 
2352   if (TraceOopMapRewrites) {
2353     tty->print_cr("ref/value conflict for method %s - bytecodes are getting rewritten", method()->name()->as_C_string());
2354     method()->print();
2355     method()->print_codes();
2356   }
2357 
2358   assert(_new_var_map!=NULL, "nothing to rewrite");
2359   assert(_conflict==true, "We should not be here");
2360 
2361   compute_ret_adr_at_TOS();
2362   if (!_got_error) {
2363     for (int k = 0; k < _max_locals && !_got_error; k++) {
2364       if (_new_var_map[k] != k) {
2365         if (TraceOopMapRewrites) {
2366           tty->print_cr("Rewriting: %d -> %d", k, _new_var_map[k]);
2367         }
2368         rewrite_refval_conflict(k, _new_var_map[k]);
2369         if (_got_error) return;
2370         nof_conflicts++;
2371       }
2372     }
2373   }
2374 
2375   assert(nof_conflicts == _nof_refval_conflicts, "sanity check");
2376 
2377   // Adjust the number of locals
2378   method()->set_max_locals(_max_locals+_nof_refval_conflicts);
2379   _max_locals += _nof_refval_conflicts;
2380 
2381   // That was that...
2382   _new_var_map = NULL;
2383   _nof_refval_conflicts = 0;
2384 }
2385 
2386 void GenerateOopMap::rewrite_refval_conflict(int from, int to) {
2387   bool startOver;
2388   do {
2389     // Make sure that the BytecodeStream is constructed in the loop, since
2390     // during rewriting a new method oop is going to be used, and the next time
2391     // around we want to use that.
2392     BytecodeStream bcs(_method);
2393     startOver = false;
2394 
2395     while( !startOver && !_got_error &&
2396            // test bcs in case method changed and it became invalid
2397            bcs.next() >=0) {
2398       startOver = rewrite_refval_conflict_inst(&bcs, from, to);
2399     }
2400   } while (startOver && !_got_error);
2401 }
2402 
2403 /* If the current instruction is one that uses local variable "from"
2404    in a ref way, change it to use "to". There's a subtle reason why we
2405    renumber the ref uses and not the non-ref uses: non-ref uses may be
2406    2 slots wide (double, long) which would necessitate keeping track of
2407    whether we should add one or two variables to the method. If the change
2408    affected the width of some instruction, returns "TRUE"; otherwise, returns "FALSE".
2409    Another reason for moving ref's value is for solving (addr, ref) conflicts, which
2410    both uses aload/astore methods.
2411 */
2412 bool GenerateOopMap::rewrite_refval_conflict_inst(BytecodeStream *itr, int from, int to) {
2413   Bytecodes::Code bc = itr->code();
2414   int index;
2415   int bci = itr->bci();
2416 
2417   if (is_aload(itr, &index) && index == from) {
2418     if (TraceOopMapRewrites) {
2419       tty->print_cr("Rewriting aload at bci: %d", bci);
2420     }
2421     return rewrite_load_or_store(itr, Bytecodes::_aload, Bytecodes::_aload_0, to);
2422   }
2423 
2424   if (is_astore(itr, &index) && index == from) {
2425     if (!stack_top_holds_ret_addr(bci)) {
2426       if (TraceOopMapRewrites) {
2427         tty->print_cr("Rewriting astore at bci: %d", bci);
2428       }
2429       return rewrite_load_or_store(itr, Bytecodes::_astore, Bytecodes::_astore_0, to);
2430     } else {
2431       if (TraceOopMapRewrites) {
2432         tty->print_cr("Supress rewriting of astore at bci: %d", bci);
2433       }
2434     }
2435   }
2436 
2437   return false;
2438 }
2439 
2440 // The argument to this method is:
2441 // bc : Current bytecode
2442 // bcN : either _aload or _astore
2443 // bc0 : either _aload_0 or _astore_0
2444 bool GenerateOopMap::rewrite_load_or_store(BytecodeStream *bcs, Bytecodes::Code bcN, Bytecodes::Code bc0, unsigned int varNo) {
2445   assert(bcN == Bytecodes::_astore   || bcN == Bytecodes::_aload,   "wrong argument (bcN)");
2446   assert(bc0 == Bytecodes::_astore_0 || bc0 == Bytecodes::_aload_0, "wrong argument (bc0)");
2447   int ilen = Bytecodes::length_at(_method(), bcs->bcp());
2448   int newIlen;
2449 
2450   if (ilen == 4) {
2451     // Original instruction was wide; keep it wide for simplicity
2452     newIlen = 4;
2453   } else if (varNo < 4)
2454      newIlen = 1;
2455   else if (varNo >= 256)
2456      newIlen = 4;
2457   else
2458      newIlen = 2;
2459 
2460   // If we need to relocate in order to patch the byte, we
2461   // do the patching in a temp. buffer, that is passed to the reloc.
2462   // The patching of the bytecode stream is then done by the Relocator.
2463   // This is neccesary, since relocating the instruction at a certain bci, might
2464   // also relocate that instruction, e.g., if a _goto before it gets widen to a _goto_w.
2465   // Hence, we do not know which bci to patch after relocation.
2466 
2467   assert(newIlen <= 4, "sanity check");
2468   u_char inst_buffer[4]; // Max. instruction size is 4.
2469   address bcp;
2470 
2471   if (newIlen != ilen) {
2472     // Relocation needed do patching in temp. buffer
2473     bcp = (address)inst_buffer;
2474   } else {
2475     bcp = _method->bcp_from(bcs->bci());
2476   }
2477 
2478   // Patch either directly in Method* or in temp. buffer
2479   if (newIlen == 1) {
2480     assert(varNo < 4, "varNo too large");
2481     *bcp = bc0 + varNo;
2482   } else if (newIlen == 2) {
2483     assert(varNo < 256, "2-byte index needed!");
2484     *(bcp + 0) = bcN;
2485     *(bcp + 1) = varNo;
2486   } else {
2487     assert(newIlen == 4, "Wrong instruction length");
2488     *(bcp + 0) = Bytecodes::_wide;
2489     *(bcp + 1) = bcN;
2490     Bytes::put_Java_u2(bcp+2, varNo);
2491   }
2492 
2493   if (newIlen != ilen) {
2494     expand_current_instr(bcs->bci(), ilen, newIlen, inst_buffer);
2495   }
2496 
2497 
2498   return (newIlen != ilen);
2499 }
2500 
2501 class RelocCallback : public RelocatorListener {
2502  private:
2503   GenerateOopMap* _gom;
2504  public:
2505    RelocCallback(GenerateOopMap* gom) { _gom = gom; };
2506 
2507   // Callback method
2508   virtual void relocated(int bci, int delta, int new_code_length) {
2509     _gom->update_basic_blocks  (bci, delta, new_code_length);
2510     _gom->update_ret_adr_at_TOS(bci, delta);
2511     _gom->_rt.update_ret_table (bci, delta);
2512   }
2513 };
2514 
2515 // Returns true if expanding was succesful. Otherwise, reports an error and
2516 // returns false.
2517 void GenerateOopMap::expand_current_instr(int bci, int ilen, int newIlen, u_char inst_buffer[]) {
2518   Thread *THREAD = Thread::current();  // Could really have TRAPS argument.
2519   RelocCallback rcb(this);
2520   Relocator rc(_method, &rcb);
2521   methodHandle m= rc.insert_space_at(bci, newIlen, inst_buffer, THREAD);
2522   if (m.is_null() || HAS_PENDING_EXCEPTION) {
2523     report_error("could not rewrite method - exception occurred or bytecode buffer overflow");
2524     return;
2525   }
2526 
2527   // Relocator returns a new method oop.
2528   _did_relocation = true;
2529   _method = m;
2530 }
2531 
2532 
2533 bool GenerateOopMap::is_astore(BytecodeStream *itr, int *index) {
2534   Bytecodes::Code bc = itr->code();
2535   switch(bc) {
2536     case Bytecodes::_astore_0:
2537     case Bytecodes::_astore_1:
2538     case Bytecodes::_astore_2:
2539     case Bytecodes::_astore_3:
2540       *index = bc - Bytecodes::_astore_0;
2541       return true;
2542     case Bytecodes::_astore:
2543       *index = itr->get_index();
2544       return true;
2545   }
2546   return false;
2547 }
2548 
2549 bool GenerateOopMap::is_aload(BytecodeStream *itr, int *index) {
2550   Bytecodes::Code bc = itr->code();
2551   switch(bc) {
2552     case Bytecodes::_aload_0:
2553     case Bytecodes::_aload_1:
2554     case Bytecodes::_aload_2:
2555     case Bytecodes::_aload_3:
2556       *index = bc - Bytecodes::_aload_0;
2557       return true;
2558 
2559     case Bytecodes::_aload:
2560       *index = itr->get_index();
2561       return true;
2562   }
2563   return false;
2564 }
2565 
2566 
2567 // Return true iff the top of the operand stack holds a return address at
2568 // the current instruction
2569 bool GenerateOopMap::stack_top_holds_ret_addr(int bci) {
2570   for(int i = 0; i < _ret_adr_tos->length(); i++) {
2571     if (_ret_adr_tos->at(i) == bci)
2572       return true;
2573   }
2574 
2575   return false;
2576 }
2577 
2578 void GenerateOopMap::compute_ret_adr_at_TOS() {
2579   assert(_ret_adr_tos != NULL, "must be initialized");
2580   _ret_adr_tos->clear();
2581 
2582   for (int i = 0; i < bb_count(); i++) {
2583     BasicBlock* bb = &_basic_blocks[i];
2584 
2585     // Make sure to only check basicblocks that are reachable
2586     if (bb->is_reachable()) {
2587 
2588       // For each Basic block we check all instructions
2589       BytecodeStream bcs(_method);
2590       bcs.set_interval(bb->_bci, next_bb_start_pc(bb));
2591 
2592       restore_state(bb);
2593 
2594       while (bcs.next()>=0 && !_got_error) {
2595         // TDT: should this be is_good_address() ?
2596         if (_stack_top > 0 && stack()[_stack_top-1].is_address()) {
2597           _ret_adr_tos->append(bcs.bci());
2598           if (TraceNewOopMapGeneration) {
2599             tty->print_cr("Ret_adr TOS at bci: %d", bcs.bci());
2600           }
2601         }
2602         interp1(&bcs);
2603       }
2604     }
2605   }
2606 }
2607 
2608 void GenerateOopMap::update_ret_adr_at_TOS(int bci, int delta) {
2609   for(int i = 0; i < _ret_adr_tos->length(); i++) {
2610     int v = _ret_adr_tos->at(i);
2611     if (v > bci)  _ret_adr_tos->at_put(i, v + delta);
2612   }
2613 }
2614 
2615 // ===================================================================
2616 
2617 #ifndef PRODUCT
2618 int ResolveOopMapConflicts::_nof_invocations  = 0;
2619 int ResolveOopMapConflicts::_nof_rewrites     = 0;
2620 int ResolveOopMapConflicts::_nof_relocations  = 0;
2621 #endif
2622 
2623 methodHandle ResolveOopMapConflicts::do_potential_rewrite(TRAPS) {
2624   compute_map(CHECK_(methodHandle()));
2625 
2626 #ifndef PRODUCT
2627   // Tracking and statistics
2628   if (PrintRewrites) {
2629     _nof_invocations++;
2630     if (did_rewriting()) {
2631       _nof_rewrites++;
2632       if (did_relocation()) _nof_relocations++;
2633       tty->print("Method was rewritten %s: ", (did_relocation()) ? "and relocated" : "");
2634       method()->print_value(); tty->cr();
2635       tty->print_cr("Cand.: %d rewrts: %d (%d%%) reloc.: %d (%d%%)",
2636           _nof_invocations,
2637           _nof_rewrites,    (_nof_rewrites    * 100) / _nof_invocations,
2638           _nof_relocations, (_nof_relocations * 100) / _nof_invocations);
2639     }
2640   }
2641 #endif
2642   return methodHandle(THREAD, method());
2643 }