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