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