1 /*
   2  * Copyright (c) 1998, 2014, 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 "ci/ciMethod.hpp"
  27 #include "ci/ciMethodBlocks.hpp"
  28 #include "ci/ciStreams.hpp"
  29 #include "compiler/methodLiveness.hpp"
  30 #include "interpreter/bytecode.hpp"
  31 #include "interpreter/bytecodes.hpp"
  32 #include "memory/allocation.inline.hpp"
  33 #include "utilities/bitMap.inline.hpp"
  34 
  35 // The MethodLiveness class performs a simple liveness analysis on a method
  36 // in order to decide which locals are live (that is, will be used again) at
  37 // a particular bytecode index (bci).
  38 //
  39 // The algorithm goes:
  40 //
  41 // 1. Break the method into a set of basic blocks.  For each basic block we
  42 //    also keep track of its set of predecessors through normal control flow
  43 //    and predecessors through exceptional control flow.
  44 //
  45 // 2. For each basic block, compute two sets, gen (the set of values used before
  46 //    they are defined) and kill (the set of values defined before they are used)
  47 //    in the basic block.  A basic block "needs" the locals in its gen set to
  48 //    perform its computation.  A basic block "provides" values for the locals in
  49 //    its kill set, allowing a need from a successor to be ignored.
  50 //
  51 // 3. Liveness information (the set of locals which are needed) is pushed backwards through
  52 //    the program, from blocks to their predecessors.  We compute and store liveness
  53 //    information for the normal/exceptional exit paths for each basic block.  When
  54 //    this process reaches a fixed point, we are done.
  55 //
  56 // 4. When we are asked about the liveness at a particular bci with a basic block, we
  57 //    compute gen/kill sets which represent execution from that bci to the exit of
  58 //    its blocks.  We then compose this range gen/kill information with the normal
  59 //    and exceptional exit information for the block to produce liveness information
  60 //    at that bci.
  61 //
  62 // The algorithm is approximate in many respects.  Notably:
  63 //
  64 // 1. We do not do the analysis necessary to match jsr's with the appropriate ret.
  65 //    Instead we make the conservative assumption that any ret can return to any
  66 //    jsr return site.
  67 // 2. Instead of computing the effects of exceptions at every instruction, we
  68 //    summarize the effects of all exceptional continuations from the block as
  69 //    a single set (_exception_exit), losing some information but simplifying the
  70 //    analysis.
  71 
  72 
  73 //--------------------------------------------------------------------------
  74 // The BitCounter class is used for counting the number of bits set in
  75 // some BitMap.  It is only used when collecting liveness statistics.
  76 
  77 #ifndef PRODUCT
  78 
  79 class BitCounter: public BitMapClosure {
  80  private:
  81   int _count;
  82  public:
  83   BitCounter() : _count(0) {}
  84 
  85   // Callback when bit in map is set
  86   virtual bool do_bit(size_t offset) {
  87     _count++;
  88     return true;
  89   }
  90 
  91   int count() {
  92     return _count;
  93   }
  94 };
  95 
  96 
  97 //--------------------------------------------------------------------------
  98 
  99 
 100 // Counts
 101 long MethodLiveness::_total_bytes = 0;
 102 int  MethodLiveness::_total_methods = 0;
 103 
 104 long MethodLiveness::_total_blocks = 0;
 105 int  MethodLiveness::_max_method_blocks = 0;
 106 
 107 long MethodLiveness::_total_edges = 0;
 108 int  MethodLiveness::_max_block_edges = 0;
 109 
 110 long MethodLiveness::_total_exc_edges = 0;
 111 int  MethodLiveness::_max_block_exc_edges = 0;
 112 
 113 long MethodLiveness::_total_method_locals = 0;
 114 int  MethodLiveness::_max_method_locals = 0;
 115 
 116 long MethodLiveness::_total_locals_queried = 0;
 117 long MethodLiveness::_total_live_locals_queried = 0;
 118 
 119 long MethodLiveness::_total_visits = 0;
 120 
 121 #endif
 122 
 123 // Timers
 124 elapsedTimer MethodLiveness::_time_build_graph;
 125 elapsedTimer MethodLiveness::_time_gen_kill;
 126 elapsedTimer MethodLiveness::_time_flow;
 127 elapsedTimer MethodLiveness::_time_query;
 128 elapsedTimer MethodLiveness::_time_total;
 129 
 130 MethodLiveness::MethodLiveness(Arena* arena, ciMethod* method)
 131 #ifdef COMPILER1
 132   : _bci_block_start((uintptr_t*)arena->Amalloc((method->code_size() >> LogBitsPerByte) + 1), method->code_size())
 133 #endif
 134 {
 135   _arena = arena;
 136   _method = method;
 137   _bit_map_size_bits = method->max_locals();
 138   _bit_map_size_words = (_bit_map_size_bits / sizeof(unsigned int)) + 1;
 139 
 140 #ifdef COMPILER1
 141   _bci_block_start.clear();
 142 #endif
 143 }
 144 
 145 void MethodLiveness::compute_liveness() {
 146 #ifndef PRODUCT
 147   if (TraceLivenessGen) {
 148     tty->print_cr("################################################################");
 149     tty->print("# Computing liveness information for ");
 150     method()->print_short_name();
 151   }
 152 
 153   if (TimeLivenessAnalysis) _time_total.start();
 154 #endif
 155 
 156   {
 157     TraceTime buildGraph(NULL, &_time_build_graph, TimeLivenessAnalysis);
 158     init_basic_blocks();
 159   }
 160   {
 161     TraceTime genKill(NULL, &_time_gen_kill, TimeLivenessAnalysis);
 162     init_gen_kill();
 163   }
 164   {
 165     TraceTime flow(NULL, &_time_flow, TimeLivenessAnalysis);
 166     propagate_liveness();
 167   }
 168 
 169 #ifndef PRODUCT
 170   if (TimeLivenessAnalysis) _time_total.stop();
 171 
 172   if (TimeLivenessAnalysis) {
 173     // Collect statistics
 174     _total_bytes += method()->code_size();
 175     _total_methods++;
 176 
 177     int num_blocks = _block_count;
 178     _total_blocks += num_blocks;
 179     _max_method_blocks = MAX2(num_blocks,_max_method_blocks);
 180 
 181     for (int i=0; i<num_blocks; i++) {
 182       BasicBlock *block = _block_list[i];
 183 
 184       int numEdges = block->_normal_predecessors->length();
 185       int numExcEdges = block->_exception_predecessors->length();
 186 
 187       _total_edges += numEdges;
 188       _total_exc_edges += numExcEdges;
 189       _max_block_edges = MAX2(numEdges,_max_block_edges);
 190       _max_block_exc_edges = MAX2(numExcEdges,_max_block_exc_edges);
 191     }
 192 
 193     int numLocals = _bit_map_size_bits;
 194     _total_method_locals += numLocals;
 195     _max_method_locals = MAX2(numLocals,_max_method_locals);
 196   }
 197 #endif
 198 }
 199 
 200 
 201 void MethodLiveness::init_basic_blocks() {
 202   bool bailout = false;
 203 
 204   int method_len = method()->code_size();
 205   ciMethodBlocks *mblocks = method()->get_method_blocks();
 206 
 207   // Create an array to store the bci->BasicBlock mapping.
 208   _block_map = new (arena()) GrowableArray<BasicBlock*>(arena(), method_len, method_len, NULL);
 209 
 210   _block_count = mblocks->num_blocks();
 211   _block_list = (BasicBlock **) arena()->Amalloc(sizeof(BasicBlock *) * _block_count);
 212 
 213   // Used for patching up jsr/ret control flow.
 214   GrowableArray<BasicBlock*>* jsr_exit_list = new GrowableArray<BasicBlock*>(5);
 215   GrowableArray<BasicBlock*>* ret_list = new GrowableArray<BasicBlock*>(5);
 216 
 217   // generate our block list from ciMethodBlocks
 218   for (int blk = 0; blk < _block_count; blk++) {
 219     ciBlock *cib = mblocks->block(blk);
 220      int start_bci = cib->start_bci();
 221     _block_list[blk] = new (arena()) BasicBlock(this, start_bci, cib->limit_bci());
 222     _block_map->at_put(start_bci, _block_list[blk]);
 223 #ifdef COMPILER1
 224     // mark all bcis where a new basic block starts
 225     _bci_block_start.set_bit(start_bci);
 226 #endif // COMPILER1
 227   }
 228   // fill in the predecessors of blocks
 229   ciBytecodeStream bytes(method());
 230 
 231   for (int blk = 0; blk < _block_count; blk++) {
 232     BasicBlock *current_block = _block_list[blk];
 233     int bci =  mblocks->block(blk)->control_bci();
 234 
 235     if (bci == ciBlock::fall_through_bci) {
 236       int limit = current_block->limit_bci();
 237       if (limit < method_len) {
 238         BasicBlock *next = _block_map->at(limit);
 239         assert( next != NULL, "must be a block immediately following this one.");
 240         next->add_normal_predecessor(current_block);
 241       }
 242       continue;
 243     }
 244     bytes.reset_to_bci(bci);
 245     Bytecodes::Code code = bytes.next();
 246     BasicBlock *dest;
 247 
 248     // Now we need to interpret the instruction's effect
 249     // on control flow.
 250     assert (current_block != NULL, "we must have a current block");
 251     switch (code) {
 252       case Bytecodes::_ifeq:
 253       case Bytecodes::_ifne:
 254       case Bytecodes::_iflt:
 255       case Bytecodes::_ifge:
 256       case Bytecodes::_ifgt:
 257       case Bytecodes::_ifle:
 258       case Bytecodes::_if_icmpeq:
 259       case Bytecodes::_if_icmpne:
 260       case Bytecodes::_if_icmplt:
 261       case Bytecodes::_if_icmpge:
 262       case Bytecodes::_if_icmpgt:
 263       case Bytecodes::_if_icmple:
 264       case Bytecodes::_if_acmpeq:
 265       case Bytecodes::_if_acmpne:
 266       case Bytecodes::_ifnull:
 267       case Bytecodes::_ifnonnull:
 268         // Two way branch.  Set predecessors at each destination.
 269         dest = _block_map->at(bytes.next_bci());
 270         assert(dest != NULL, "must be a block immediately following this one.");
 271         dest->add_normal_predecessor(current_block);
 272 
 273         dest = _block_map->at(bytes.get_dest());
 274         assert(dest != NULL, "branch desination must start a block.");
 275         dest->add_normal_predecessor(current_block);
 276         break;
 277       case Bytecodes::_goto:
 278         dest = _block_map->at(bytes.get_dest());
 279         assert(dest != NULL, "branch desination must start a block.");
 280         dest->add_normal_predecessor(current_block);
 281         break;
 282       case Bytecodes::_goto_w:
 283         dest = _block_map->at(bytes.get_far_dest());
 284         assert(dest != NULL, "branch desination must start a block.");
 285         dest->add_normal_predecessor(current_block);
 286         break;
 287       case Bytecodes::_tableswitch:
 288         {
 289           Bytecode_tableswitch tableswitch(&bytes);
 290 
 291           int len = tableswitch.length();
 292 
 293           dest = _block_map->at(bci + tableswitch.default_offset());
 294           assert(dest != NULL, "branch desination must start a block.");
 295           dest->add_normal_predecessor(current_block);
 296           while (--len >= 0) {
 297             dest = _block_map->at(bci + tableswitch.dest_offset_at(len));
 298             assert(dest != NULL, "branch desination must start a block.");
 299             dest->add_normal_predecessor(current_block);
 300           }
 301           break;
 302         }
 303 
 304       case Bytecodes::_lookupswitch:
 305         {
 306           Bytecode_lookupswitch lookupswitch(&bytes);
 307 
 308           int npairs = lookupswitch.number_of_pairs();
 309 
 310           dest = _block_map->at(bci + lookupswitch.default_offset());
 311           assert(dest != NULL, "branch desination must start a block.");
 312           dest->add_normal_predecessor(current_block);
 313           while(--npairs >= 0) {
 314             LookupswitchPair pair = lookupswitch.pair_at(npairs);
 315             dest = _block_map->at( bci + pair.offset());
 316             assert(dest != NULL, "branch desination must start a block.");
 317             dest->add_normal_predecessor(current_block);
 318           }
 319           break;
 320         }
 321 
 322       case Bytecodes::_jsr:
 323         {
 324           assert(bytes.is_wide()==false, "sanity check");
 325           dest = _block_map->at(bytes.get_dest());
 326           assert(dest != NULL, "branch desination must start a block.");
 327           dest->add_normal_predecessor(current_block);
 328           BasicBlock *jsrExit = _block_map->at(current_block->limit_bci());
 329           assert(jsrExit != NULL, "jsr return bci must start a block.");
 330           jsr_exit_list->append(jsrExit);
 331           break;
 332         }
 333       case Bytecodes::_jsr_w:
 334         {
 335           dest = _block_map->at(bytes.get_far_dest());
 336           assert(dest != NULL, "branch desination must start a block.");
 337           dest->add_normal_predecessor(current_block);
 338           BasicBlock *jsrExit = _block_map->at(current_block->limit_bci());
 339           assert(jsrExit != NULL, "jsr return bci must start a block.");
 340           jsr_exit_list->append(jsrExit);
 341           break;
 342         }
 343 
 344       case Bytecodes::_wide:
 345         assert(false, "wide opcodes should not be seen here");
 346         break;
 347       case Bytecodes::_athrow:
 348       case Bytecodes::_ireturn:
 349       case Bytecodes::_lreturn:
 350       case Bytecodes::_freturn:
 351       case Bytecodes::_dreturn:
 352       case Bytecodes::_areturn:
 353       case Bytecodes::_vreturn:
 354       case Bytecodes::_return:
 355         // These opcodes are  not the normal predecessors of any other opcodes.
 356         break;
 357       case Bytecodes::_ret:
 358         // We will patch up jsr/rets in a subsequent pass.
 359         ret_list->append(current_block);
 360         break;
 361       case Bytecodes::_breakpoint:
 362         // Bail out of there are breakpoints in here.
 363         bailout = true;
 364         break;
 365       default:
 366         // Do nothing.
 367         break;
 368     }
 369   }
 370   // Patch up the jsr/ret's.  We conservatively assume that any ret
 371   // can return to any jsr site.
 372   int ret_list_len = ret_list->length();
 373   int jsr_exit_list_len = jsr_exit_list->length();
 374   if (ret_list_len > 0 && jsr_exit_list_len > 0) {
 375     for (int i = jsr_exit_list_len - 1; i >= 0; i--) {
 376       BasicBlock *jsrExit = jsr_exit_list->at(i);
 377       for (int i = ret_list_len - 1; i >= 0; i--) {
 378         jsrExit->add_normal_predecessor(ret_list->at(i));
 379       }
 380     }
 381   }
 382 
 383   // Compute exception edges.
 384   for (int b=_block_count-1; b >= 0; b--) {
 385     BasicBlock *block = _block_list[b];
 386     int block_start = block->start_bci();
 387     int block_limit = block->limit_bci();
 388     ciExceptionHandlerStream handlers(method());
 389     for (; !handlers.is_done(); handlers.next()) {
 390       ciExceptionHandler* handler = handlers.handler();
 391       int start       = handler->start();
 392       int limit       = handler->limit();
 393       int handler_bci = handler->handler_bci();
 394 
 395       int intersect_start = MAX2(block_start, start);
 396       int intersect_limit = MIN2(block_limit, limit);
 397       if (intersect_start < intersect_limit) {
 398         // The catch range has a nonempty intersection with this
 399         // basic block.  That means this basic block can be an
 400         // exceptional predecessor.
 401         _block_map->at(handler_bci)->add_exception_predecessor(block);
 402 
 403         if (handler->is_catch_all()) {
 404           // This is a catch-all block.
 405           if (intersect_start == block_start && intersect_limit == block_limit) {
 406             // The basic block is entirely contained in this catch-all block.
 407             // Skip the rest of the exception handlers -- they can never be
 408             // reached in execution.
 409             break;
 410           }
 411         }
 412       }
 413     }
 414   }
 415 }
 416 
 417 void MethodLiveness::init_gen_kill() {
 418   for (int i=_block_count-1; i >= 0; i--) {
 419     _block_list[i]->compute_gen_kill(method());
 420   }
 421 }
 422 
 423 void MethodLiveness::propagate_liveness() {
 424   int num_blocks = _block_count;
 425   BasicBlock *block;
 426 
 427   // We start our work list off with all blocks in it.
 428   // Alternately, we could start off the work list with the list of all
 429   // blocks which could exit the method directly, along with one block
 430   // from any infinite loop.  If this matters, it can be changed.  It
 431   // may not be clear from looking at the code, but the order of the
 432   // workList will be the opposite of the creation order of the basic
 433   // blocks, which should be decent for quick convergence (with the
 434   // possible exception of exception handlers, which are all created
 435   // early).
 436   _work_list = NULL;
 437   for (int i = 0; i < num_blocks; i++) {
 438     block = _block_list[i];
 439     block->set_next(_work_list);
 440     block->set_on_work_list(true);
 441     _work_list = block;
 442   }
 443 
 444 
 445   while ((block = work_list_get()) != NULL) {
 446     block->propagate(this);
 447     NOT_PRODUCT(_total_visits++;)
 448   }
 449 }
 450 
 451 void MethodLiveness::work_list_add(BasicBlock *block) {
 452   if (!block->on_work_list()) {
 453     block->set_next(_work_list);
 454     block->set_on_work_list(true);
 455     _work_list = block;
 456   }
 457 }
 458 
 459 MethodLiveness::BasicBlock *MethodLiveness::work_list_get() {
 460   BasicBlock *block = _work_list;
 461   if (block != NULL) {
 462     block->set_on_work_list(false);
 463     _work_list = block->next();
 464   }
 465   return block;
 466 }
 467 
 468 
 469 MethodLivenessResult MethodLiveness::get_liveness_at(int entry_bci) {
 470   int bci = entry_bci;
 471   bool is_entry = false;
 472   if (entry_bci == InvocationEntryBci) {
 473     is_entry = true;
 474     bci = 0;
 475   }
 476 
 477   MethodLivenessResult answer((BitMap::bm_word_t*)NULL,0);
 478 
 479   if (_block_count > 0) {
 480     if (TimeLivenessAnalysis) _time_total.start();
 481     if (TimeLivenessAnalysis) _time_query.start();
 482 
 483     assert( 0 <= bci && bci < method()->code_size(), "bci out of range" );
 484     BasicBlock *block = _block_map->at(bci);
 485     // We may not be at the block start, so search backwards to find the block
 486     // containing bci.
 487     int t = bci;
 488     while (block == NULL && t > 0) {
 489      block = _block_map->at(--t);
 490     }
 491     assert( block != NULL, "invalid bytecode index; must be instruction index" );
 492     assert(bci >= block->start_bci() && bci < block->limit_bci(), "block must contain bci.");
 493 
 494     answer = block->get_liveness_at(method(), bci);
 495 
 496     if (is_entry && method()->is_synchronized() && !method()->is_static()) {
 497       // Synchronized methods use the receiver once on entry.
 498       answer.at_put(0, true);
 499     }
 500 
 501 #ifndef PRODUCT
 502     if (TraceLivenessQuery) {
 503       tty->print("Liveness query of ");
 504       method()->print_short_name();
 505       tty->print(" @ %d : result is ", bci);
 506       answer.print_on(tty);
 507     }
 508 
 509     if (TimeLivenessAnalysis) _time_query.stop();
 510     if (TimeLivenessAnalysis) _time_total.stop();
 511 #endif
 512   }
 513 
 514 #ifndef PRODUCT
 515   if (TimeLivenessAnalysis) {
 516     // Collect statistics.
 517     _total_locals_queried += _bit_map_size_bits;
 518     BitCounter counter;
 519     answer.iterate(&counter);
 520     _total_live_locals_queried += counter.count();
 521   }
 522 #endif
 523 
 524   return answer;
 525 }
 526 
 527 
 528 #ifndef PRODUCT
 529 
 530 void MethodLiveness::print_times() {
 531   tty->print_cr ("Accumulated liveness analysis times/statistics:");
 532   tty->print_cr ("-----------------------------------------------");
 533   tty->print_cr ("  Total         : %3.3f sec.", _time_total.seconds());
 534   tty->print_cr ("    Build graph : %3.3f sec. (%2.2f%%)", _time_build_graph.seconds(),
 535                  _time_build_graph.seconds() * 100 / _time_total.seconds());
 536   tty->print_cr ("    Gen / Kill  : %3.3f sec. (%2.2f%%)", _time_gen_kill.seconds(),
 537                  _time_gen_kill.seconds() * 100 / _time_total.seconds());
 538   tty->print_cr ("    Dataflow    : %3.3f sec. (%2.2f%%)", _time_flow.seconds(),
 539                  _time_flow.seconds() * 100 / _time_total.seconds());
 540   tty->print_cr ("    Query       : %3.3f sec. (%2.2f%%)", _time_query.seconds(),
 541                  _time_query.seconds() * 100 / _time_total.seconds());
 542   tty->print_cr ("  #bytes   : %8ld (%3.0f bytes per sec)",
 543                  _total_bytes,
 544                  _total_bytes / _time_total.seconds());
 545   tty->print_cr ("  #methods : %8d (%3.0f methods per sec)",
 546                  _total_methods,
 547                  _total_methods / _time_total.seconds());
 548   tty->print_cr ("    avg locals : %3.3f    max locals : %3d",
 549                  (float)_total_method_locals / _total_methods,
 550                  _max_method_locals);
 551   tty->print_cr ("    avg blocks : %3.3f    max blocks : %3d",
 552                  (float)_total_blocks / _total_methods,
 553                  _max_method_blocks);
 554   tty->print_cr ("    avg bytes  : %3.3f",
 555                  (float)_total_bytes / _total_methods);
 556   tty->print_cr ("  #blocks  : %8ld",
 557                  _total_blocks);
 558   tty->print_cr ("    avg normal predecessors    : %3.3f  max normal predecessors    : %3d",
 559                  (float)_total_edges / _total_blocks,
 560                  _max_block_edges);
 561   tty->print_cr ("    avg exception predecessors : %3.3f  max exception predecessors : %3d",
 562                  (float)_total_exc_edges / _total_blocks,
 563                  _max_block_exc_edges);
 564   tty->print_cr ("    avg visits                 : %3.3f",
 565                  (float)_total_visits / _total_blocks);
 566   tty->print_cr ("  #locals queried : %8ld    #live : %8ld   %%live : %2.2f%%",
 567                  _total_locals_queried,
 568                  _total_live_locals_queried,
 569                  100.0 * _total_live_locals_queried / _total_locals_queried);
 570 }
 571 
 572 #endif
 573 
 574 
 575 MethodLiveness::BasicBlock::BasicBlock(MethodLiveness *analyzer, int start, int limit) :
 576          _gen((uintptr_t*)analyzer->arena()->Amalloc(BytesPerWord * analyzer->bit_map_size_words()),
 577                          analyzer->bit_map_size_bits()),
 578          _kill((uintptr_t*)analyzer->arena()->Amalloc(BytesPerWord * analyzer->bit_map_size_words()),
 579                          analyzer->bit_map_size_bits()),
 580          _entry((uintptr_t*)analyzer->arena()->Amalloc(BytesPerWord * analyzer->bit_map_size_words()),
 581                          analyzer->bit_map_size_bits()),
 582          _normal_exit((uintptr_t*)analyzer->arena()->Amalloc(BytesPerWord * analyzer->bit_map_size_words()),
 583                          analyzer->bit_map_size_bits()),
 584          _exception_exit((uintptr_t*)analyzer->arena()->Amalloc(BytesPerWord * analyzer->bit_map_size_words()),
 585                          analyzer->bit_map_size_bits()),
 586          _last_bci(-1) {
 587   _analyzer = analyzer;
 588   _start_bci = start;
 589   _limit_bci = limit;
 590   _normal_predecessors =
 591     new (analyzer->arena()) GrowableArray<MethodLiveness::BasicBlock*>(analyzer->arena(), 5, 0, NULL);
 592   _exception_predecessors =
 593     new (analyzer->arena()) GrowableArray<MethodLiveness::BasicBlock*>(analyzer->arena(), 5, 0, NULL);
 594   _normal_exit.clear();
 595   _exception_exit.clear();
 596   _entry.clear();
 597 
 598   // this initialization is not strictly necessary.
 599   // _gen and _kill are cleared at the beginning of compute_gen_kill_range()
 600   _gen.clear();
 601   _kill.clear();
 602 }
 603 
 604 
 605 
 606 MethodLiveness::BasicBlock *MethodLiveness::BasicBlock::split(int split_bci) {
 607   int start = _start_bci;
 608   int limit = _limit_bci;
 609 
 610   if (TraceLivenessGen) {
 611     tty->print_cr(" ** Splitting block (%d,%d) at %d", start, limit, split_bci);
 612   }
 613 
 614   GrowableArray<BasicBlock*>* save_predecessors = _normal_predecessors;
 615 
 616   assert (start < split_bci && split_bci < limit, "improper split");
 617 
 618   // Make a new block to cover the first half of the range.
 619   BasicBlock *first_half = new (_analyzer->arena()) BasicBlock(_analyzer, start, split_bci);
 620 
 621   // Assign correct values to the second half (this)
 622   _normal_predecessors = first_half->_normal_predecessors;
 623   _start_bci = split_bci;
 624   add_normal_predecessor(first_half);
 625 
 626   // Assign correct predecessors to the new first half
 627   first_half->_normal_predecessors = save_predecessors;
 628 
 629   return first_half;
 630 }
 631 
 632 void MethodLiveness::BasicBlock::compute_gen_kill(ciMethod* method) {
 633   ciBytecodeStream bytes(method);
 634   bytes.reset_to_bci(start_bci());
 635   bytes.set_max_bci(limit_bci());
 636   compute_gen_kill_range(&bytes);
 637 
 638 }
 639 
 640 void MethodLiveness::BasicBlock::compute_gen_kill_range(ciBytecodeStream *bytes) {
 641   _gen.clear();
 642   _kill.clear();
 643 
 644   while (bytes->next() != ciBytecodeStream::EOBC()) {
 645     compute_gen_kill_single(bytes);
 646   }
 647 }
 648 
 649 void MethodLiveness::BasicBlock::compute_gen_kill_single(ciBytecodeStream *instruction) {
 650   int localNum;
 651 
 652   // We prohibit _gen and _kill from having locals in common.  If we
 653   // know that one is definitely going to be applied before the other,
 654   // we could save some computation time by relaxing this prohibition.
 655 
 656   switch (instruction->cur_bc()) {
 657     case Bytecodes::_nop:
 658     case Bytecodes::_goto:
 659     case Bytecodes::_goto_w:
 660     case Bytecodes::_aconst_null:
 661     case Bytecodes::_new:
 662     case Bytecodes::_vnew:
 663     case Bytecodes::_iconst_m1:
 664     case Bytecodes::_iconst_0:
 665     case Bytecodes::_iconst_1:
 666     case Bytecodes::_iconst_2:
 667     case Bytecodes::_iconst_3:
 668     case Bytecodes::_iconst_4:
 669     case Bytecodes::_iconst_5:
 670     case Bytecodes::_fconst_0:
 671     case Bytecodes::_fconst_1:
 672     case Bytecodes::_fconst_2:
 673     case Bytecodes::_bipush:
 674     case Bytecodes::_sipush:
 675     case Bytecodes::_lconst_0:
 676     case Bytecodes::_lconst_1:
 677     case Bytecodes::_dconst_0:
 678     case Bytecodes::_dconst_1:
 679     case Bytecodes::_ldc2_w:
 680     case Bytecodes::_ldc:
 681     case Bytecodes::_ldc_w:
 682     case Bytecodes::_iaload:
 683     case Bytecodes::_faload:
 684     case Bytecodes::_baload:
 685     case Bytecodes::_caload:
 686     case Bytecodes::_saload:
 687     case Bytecodes::_laload:
 688     case Bytecodes::_daload:
 689     case Bytecodes::_aaload:
 690     case Bytecodes::_iastore:
 691     case Bytecodes::_fastore:
 692     case Bytecodes::_bastore:
 693     case Bytecodes::_castore:
 694     case Bytecodes::_sastore:
 695     case Bytecodes::_lastore:
 696     case Bytecodes::_dastore:
 697     case Bytecodes::_aastore:
 698     case Bytecodes::_pop:
 699     case Bytecodes::_pop2:
 700     case Bytecodes::_dup:
 701     case Bytecodes::_dup_x1:
 702     case Bytecodes::_dup_x2:
 703     case Bytecodes::_dup2:
 704     case Bytecodes::_dup2_x1:
 705     case Bytecodes::_dup2_x2:
 706     case Bytecodes::_swap:
 707     case Bytecodes::_iadd:
 708     case Bytecodes::_fadd:
 709     case Bytecodes::_isub:
 710     case Bytecodes::_fsub:
 711     case Bytecodes::_imul:
 712     case Bytecodes::_fmul:
 713     case Bytecodes::_idiv:
 714     case Bytecodes::_fdiv:
 715     case Bytecodes::_irem:
 716     case Bytecodes::_frem:
 717     case Bytecodes::_ishl:
 718     case Bytecodes::_ishr:
 719     case Bytecodes::_iushr:
 720     case Bytecodes::_iand:
 721     case Bytecodes::_ior:
 722     case Bytecodes::_ixor:
 723     case Bytecodes::_l2f:
 724     case Bytecodes::_l2i:
 725     case Bytecodes::_d2f:
 726     case Bytecodes::_d2i:
 727     case Bytecodes::_fcmpl:
 728     case Bytecodes::_fcmpg:
 729     case Bytecodes::_ladd:
 730     case Bytecodes::_dadd:
 731     case Bytecodes::_lsub:
 732     case Bytecodes::_dsub:
 733     case Bytecodes::_lmul:
 734     case Bytecodes::_dmul:
 735     case Bytecodes::_ldiv:
 736     case Bytecodes::_ddiv:
 737     case Bytecodes::_lrem:
 738     case Bytecodes::_drem:
 739     case Bytecodes::_land:
 740     case Bytecodes::_lor:
 741     case Bytecodes::_lxor:
 742     case Bytecodes::_ineg:
 743     case Bytecodes::_fneg:
 744     case Bytecodes::_i2f:
 745     case Bytecodes::_f2i:
 746     case Bytecodes::_i2c:
 747     case Bytecodes::_i2s:
 748     case Bytecodes::_i2b:
 749     case Bytecodes::_lneg:
 750     case Bytecodes::_dneg:
 751     case Bytecodes::_l2d:
 752     case Bytecodes::_d2l:
 753     case Bytecodes::_lshl:
 754     case Bytecodes::_lshr:
 755     case Bytecodes::_lushr:
 756     case Bytecodes::_i2l:
 757     case Bytecodes::_i2d:
 758     case Bytecodes::_f2l:
 759     case Bytecodes::_f2d:
 760     case Bytecodes::_lcmp:
 761     case Bytecodes::_dcmpl:
 762     case Bytecodes::_dcmpg:
 763     case Bytecodes::_ifeq:
 764     case Bytecodes::_ifne:
 765     case Bytecodes::_iflt:
 766     case Bytecodes::_ifge:
 767     case Bytecodes::_ifgt:
 768     case Bytecodes::_ifle:
 769     case Bytecodes::_tableswitch:
 770     case Bytecodes::_ireturn:
 771     case Bytecodes::_freturn:
 772     case Bytecodes::_if_icmpeq:
 773     case Bytecodes::_if_icmpne:
 774     case Bytecodes::_if_icmplt:
 775     case Bytecodes::_if_icmpge:
 776     case Bytecodes::_if_icmpgt:
 777     case Bytecodes::_if_icmple:
 778     case Bytecodes::_lreturn:
 779     case Bytecodes::_dreturn:
 780     case Bytecodes::_if_acmpeq:
 781     case Bytecodes::_if_acmpne:
 782     case Bytecodes::_jsr:
 783     case Bytecodes::_jsr_w:
 784     case Bytecodes::_getstatic:
 785     case Bytecodes::_putstatic:
 786     case Bytecodes::_getfield:
 787     case Bytecodes::_vgetfield:
 788     case Bytecodes::_putfield:
 789     case Bytecodes::_invokevirtual:
 790     case Bytecodes::_invokedirect:
 791     case Bytecodes::_invokespecial:
 792     case Bytecodes::_invokestatic:
 793     case Bytecodes::_invokeinterface:
 794     case Bytecodes::_invokedynamic:
 795     case Bytecodes::_newarray:
 796     case Bytecodes::_anewarray:
 797     case Bytecodes::_checkcast:
 798     case Bytecodes::_arraylength:
 799     case Bytecodes::_instanceof:
 800     case Bytecodes::_athrow:
 801     case Bytecodes::_areturn:
 802     case Bytecodes::_vreturn:
 803     case Bytecodes::_monitorenter:
 804     case Bytecodes::_monitorexit:
 805     case Bytecodes::_ifnull:
 806     case Bytecodes::_ifnonnull:
 807     case Bytecodes::_multianewarray:
 808     case Bytecodes::_lookupswitch:
 809     case Bytecodes::_vbox:
 810     case Bytecodes::_vunbox:
 811       // These bytecodes have no effect on the method's locals.
 812       break;
 813 
 814     case Bytecodes::_return:
 815       if (instruction->method()->intrinsic_id() == vmIntrinsics::_Object_init) {
 816         // return from Object.init implicitly registers a finalizer
 817         // for the receiver if needed, so keep it alive.
 818         load_one(0);
 819       }
 820       break;
 821 
 822 
 823     case Bytecodes::_lload:
 824     case Bytecodes::_dload:
 825       load_two(instruction->get_index());
 826       break;
 827 
 828     case Bytecodes::_lload_0:
 829     case Bytecodes::_dload_0:
 830       load_two(0);
 831       break;
 832 
 833     case Bytecodes::_lload_1:
 834     case Bytecodes::_dload_1:
 835       load_two(1);
 836       break;
 837 
 838     case Bytecodes::_lload_2:
 839     case Bytecodes::_dload_2:
 840       load_two(2);
 841       break;
 842 
 843     case Bytecodes::_lload_3:
 844     case Bytecodes::_dload_3:
 845       load_two(3);
 846       break;
 847 
 848     case Bytecodes::_iload:
 849     case Bytecodes::_iinc:
 850     case Bytecodes::_fload:
 851     case Bytecodes::_aload:
 852     case Bytecodes::_vload:
 853     case Bytecodes::_ret:
 854       load_one(instruction->get_index());
 855       break;
 856 
 857     case Bytecodes::_iload_0:
 858     case Bytecodes::_fload_0:
 859     case Bytecodes::_aload_0:
 860       load_one(0);
 861       break;
 862 
 863     case Bytecodes::_iload_1:
 864     case Bytecodes::_fload_1:
 865     case Bytecodes::_aload_1:
 866       load_one(1);
 867       break;
 868 
 869     case Bytecodes::_iload_2:
 870     case Bytecodes::_fload_2:
 871     case Bytecodes::_aload_2:
 872       load_one(2);
 873       break;
 874 
 875     case Bytecodes::_iload_3:
 876     case Bytecodes::_fload_3:
 877     case Bytecodes::_aload_3:
 878       load_one(3);
 879       break;
 880 
 881     case Bytecodes::_lstore:
 882     case Bytecodes::_dstore:
 883       store_two(localNum = instruction->get_index());
 884       break;
 885 
 886     case Bytecodes::_lstore_0:
 887     case Bytecodes::_dstore_0:
 888       store_two(0);
 889       break;
 890 
 891     case Bytecodes::_lstore_1:
 892     case Bytecodes::_dstore_1:
 893       store_two(1);
 894       break;
 895 
 896     case Bytecodes::_lstore_2:
 897     case Bytecodes::_dstore_2:
 898       store_two(2);
 899       break;
 900 
 901     case Bytecodes::_lstore_3:
 902     case Bytecodes::_dstore_3:
 903       store_two(3);
 904       break;
 905 
 906     case Bytecodes::_istore:
 907     case Bytecodes::_fstore:
 908     case Bytecodes::_astore:
 909     case Bytecodes::_vstore:
 910       store_one(instruction->get_index());
 911       break;
 912 
 913     case Bytecodes::_istore_0:
 914     case Bytecodes::_fstore_0:
 915     case Bytecodes::_astore_0:
 916       store_one(0);
 917       break;
 918 
 919     case Bytecodes::_istore_1:
 920     case Bytecodes::_fstore_1:
 921     case Bytecodes::_astore_1:
 922       store_one(1);
 923       break;
 924 
 925     case Bytecodes::_istore_2:
 926     case Bytecodes::_fstore_2:
 927     case Bytecodes::_astore_2:
 928       store_one(2);
 929       break;
 930 
 931     case Bytecodes::_istore_3:
 932     case Bytecodes::_fstore_3:
 933     case Bytecodes::_astore_3:
 934       store_one(3);
 935       break;
 936 
 937     case Bytecodes::_wide:
 938       fatal("Iterator should skip this bytecode");
 939       break;
 940 
 941     default:
 942       tty->print("unexpected opcode: %d\n", instruction->cur_bc());
 943       ShouldNotReachHere();
 944       break;
 945   }
 946 }
 947 
 948 void MethodLiveness::BasicBlock::load_two(int local) {
 949   load_one(local);
 950   load_one(local+1);
 951 }
 952 
 953 void MethodLiveness::BasicBlock::load_one(int local) {
 954   if (!_kill.at(local)) {
 955     _gen.at_put(local, true);
 956   }
 957 }
 958 
 959 void MethodLiveness::BasicBlock::store_two(int local) {
 960   store_one(local);
 961   store_one(local+1);
 962 }
 963 
 964 void MethodLiveness::BasicBlock::store_one(int local) {
 965   if (!_gen.at(local)) {
 966     _kill.at_put(local, true);
 967   }
 968 }
 969 
 970 void MethodLiveness::BasicBlock::propagate(MethodLiveness *ml) {
 971   // These set operations could be combined for efficiency if the
 972   // performance of this analysis becomes an issue.
 973   _entry.set_union(_normal_exit);
 974   _entry.set_difference(_kill);
 975   _entry.set_union(_gen);
 976 
 977   // Note that we merge information from our exceptional successors
 978   // just once, rather than at individual bytecodes.
 979   _entry.set_union(_exception_exit);
 980 
 981   if (TraceLivenessGen) {
 982     tty->print_cr(" ** Visiting block at %d **", start_bci());
 983     print_on(tty);
 984   }
 985 
 986   int i;
 987   for (i=_normal_predecessors->length()-1; i>=0; i--) {
 988     BasicBlock *block = _normal_predecessors->at(i);
 989     if (block->merge_normal(_entry)) {
 990       ml->work_list_add(block);
 991     }
 992   }
 993   for (i=_exception_predecessors->length()-1; i>=0; i--) {
 994     BasicBlock *block = _exception_predecessors->at(i);
 995     if (block->merge_exception(_entry)) {
 996       ml->work_list_add(block);
 997     }
 998   }
 999 }
1000 
1001 bool MethodLiveness::BasicBlock::merge_normal(BitMap other) {
1002   return _normal_exit.set_union_with_result(other);
1003 }
1004 
1005 bool MethodLiveness::BasicBlock::merge_exception(BitMap other) {
1006   return _exception_exit.set_union_with_result(other);
1007 }
1008 
1009 MethodLivenessResult MethodLiveness::BasicBlock::get_liveness_at(ciMethod* method, int bci) {
1010   MethodLivenessResult answer(NEW_RESOURCE_ARRAY(BitMap::bm_word_t, _analyzer->bit_map_size_words()),
1011                 _analyzer->bit_map_size_bits());
1012   answer.set_is_valid();
1013 
1014 #ifndef ASSERT
1015   if (bci == start_bci()) {
1016     answer.set_from(_entry);
1017     return answer;
1018   }
1019 #endif
1020 
1021 #ifdef ASSERT
1022   ResourceMark rm;
1023   BitMap g(_gen.size()); g.set_from(_gen);
1024   BitMap k(_kill.size()); k.set_from(_kill);
1025 #endif
1026   if (_last_bci != bci || trueInDebug) {
1027     ciBytecodeStream bytes(method);
1028     bytes.reset_to_bci(bci);
1029     bytes.set_max_bci(limit_bci());
1030     compute_gen_kill_range(&bytes);
1031     assert(_last_bci != bci ||
1032            (g.is_same(_gen) && k.is_same(_kill)), "cached computation is incorrect");
1033     _last_bci = bci;
1034   }
1035 
1036   answer.clear();
1037   answer.set_union(_normal_exit);
1038   answer.set_difference(_kill);
1039   answer.set_union(_gen);
1040   answer.set_union(_exception_exit);
1041 
1042 #ifdef ASSERT
1043   if (bci == start_bci()) {
1044     assert(answer.is_same(_entry), "optimized answer must be accurate");
1045   }
1046 #endif
1047 
1048   return answer;
1049 }
1050 
1051 #ifndef PRODUCT
1052 
1053 void MethodLiveness::BasicBlock::print_on(outputStream *os) const {
1054   os->print_cr("===================================================================");
1055   os->print_cr("    Block start: %4d, limit: %4d", _start_bci, _limit_bci);
1056   os->print   ("    Normal predecessors (%2d)      @", _normal_predecessors->length());
1057   int i;
1058   for (i=0; i < _normal_predecessors->length(); i++) {
1059     os->print(" %4d", _normal_predecessors->at(i)->start_bci());
1060   }
1061   os->cr();
1062   os->print   ("    Exceptional predecessors (%2d) @", _exception_predecessors->length());
1063   for (i=0; i < _exception_predecessors->length(); i++) {
1064     os->print(" %4d", _exception_predecessors->at(i)->start_bci());
1065   }
1066   os->cr();
1067   os->print ("    Normal Exit   : ");
1068   _normal_exit.print_on(os);
1069   os->print ("    Gen           : ");
1070   _gen.print_on(os);
1071   os->print ("    Kill          : ");
1072   _kill.print_on(os);
1073   os->print ("    Exception Exit: ");
1074   _exception_exit.print_on(os);
1075   os->print ("    Entry         : ");
1076   _entry.print_on(os);
1077 }
1078 
1079 #endif // PRODUCT