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