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