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