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