/*

 * Copyright 1998-2006 Sun Microsystems, Inc.  All Rights Reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 *

 */

// The MethodLiveness class performs a simple liveness analysis on a method

// in order to decide which locals are live (that is, will be used again) at

// a particular bytecode index (bci).

//

// The algorithm goes:

//

// 1. Break the method into a set of basic blocks.  For each basic block we

//    also keep track of its set of predecessors through normal control flow

//    and predecessors through exceptional control flow.

//

// 2. For each basic block, compute two sets, gen (the set of values used before

//    they are defined) and kill (the set of values defined before they are used)

//    in the basic block.  A basic block "needs" the locals in its gen set to

//    perform its computation.  A basic block "provides" values for the locals in

//    its kill set, allowing a need from a successor to be ignored.

//

// 3. Liveness information (the set of locals which are needed) is pushed backwards through

//    the program, from blocks to their predecessors.  We compute and store liveness

//    information for the normal/exceptional exit paths for each basic block.  When

//    this process reaches a fixed point, we are done.

//

// 4. When we are asked about the liveness at a particular bci with a basic block, we

//    compute gen/kill sets which represent execution from that bci to the exit of

//    its blocks.  We then compose this range gen/kill information with the normal

//    and exceptional exit information for the block to produce liveness information

//    at that bci.

//

// The algorithm is approximate in many respects.  Notably:

//

// 1. We do not do the analysis necessary to match jsr's with the appropriate ret.

//    Instead we make the conservative assumption that any ret can return to any

//    jsr return site.

// 2. Instead of computing the effects of exceptions at every instruction, we

//    summarize the effects of all exceptional continuations from the block as

//    a single set (_exception_exit), losing some information but simplifying the

//    analysis.

# include "incls/_precompiled.incl"

# include "incls/_methodLiveness.cpp.incl"

//--------------------------------------------------------------------------

// The BitCounter class is used for counting the number of bits set in

// some BitMap.  It is only used when collecting liveness statistics.

#ifndef PRODUCT

class BitCounter: public BitMapClosure {

 private:

  int _count;

 public:

  BitCounter() : _count(0) {}

  // Callback when bit in map is set

  virtual void do_bit(size_t offset) {

    _count++;

  }

  int count() {

    return _count;

  }

};

//--------------------------------------------------------------------------

// Counts

long MethodLiveness::_total_bytes = 0;

int  MethodLiveness::_total_methods = 0;

long MethodLiveness::_total_blocks = 0;

int  MethodLiveness::_max_method_blocks = 0;

long MethodLiveness::_total_edges = 0;

int  MethodLiveness::_max_block_edges = 0;

long MethodLiveness::_total_exc_edges = 0;

int  MethodLiveness::_max_block_exc_edges = 0;

long MethodLiveness::_total_method_locals = 0;

int  MethodLiveness::_max_method_locals = 0;

long MethodLiveness::_total_locals_queried = 0;

long MethodLiveness::_total_live_locals_queried = 0;

long MethodLiveness::_total_visits = 0;

#endif

// Timers

elapsedTimer MethodLiveness::_time_build_graph;

elapsedTimer MethodLiveness::_time_gen_kill;

elapsedTimer MethodLiveness::_time_flow;

elapsedTimer MethodLiveness::_time_query;

elapsedTimer MethodLiveness::_time_total;

MethodLiveness::MethodLiveness(Arena* arena, ciMethod* method)

#ifdef COMPILER1

  : _bci_block_start((uintptr_t*)arena->Amalloc((method->code_size() >> LogBitsPerByte) + 1), method->code_size())

#endif

{

  _arena = arena;

  _method = method;

  _bit_map_size_bits = method->max_locals();

  _bit_map_size_words = (_bit_map_size_bits / sizeof(unsigned int)) + 1;

#ifdef COMPILER1

  _bci_block_start.clear();

#endif

}

void MethodLiveness::compute_liveness() {

#ifndef PRODUCT

  if (TraceLivenessGen) {

    tty->print_cr("################################################################");

    tty->print("# Computing liveness information for ");

    method()->print_short_name();

  }

  if (TimeLivenessAnalysis) _time_total.start();

#endif

  {

    TraceTime buildGraph(NULL, &_time_build_graph, TimeLivenessAnalysis);

    init_basic_blocks();

  }

  {

    TraceTime genKill(NULL, &_time_gen_kill, TimeLivenessAnalysis);

    init_gen_kill();

  }

  {

    TraceTime flow(NULL, &_time_flow, TimeLivenessAnalysis);

    propagate_liveness();

  }

#ifndef PRODUCT

  if (TimeLivenessAnalysis) _time_total.stop();

  if (TimeLivenessAnalysis) {

    // Collect statistics

    _total_bytes += method()->code_size();

    _total_methods++;

    int num_blocks = _block_count;

    _total_blocks += num_blocks;

    _max_method_blocks = MAX2(num_blocks,_max_method_blocks);

    for (int i=0; i<num_blocks; i++) {

      BasicBlock *block = _block_list[i];

      int numEdges = block->_normal_predecessors->length();

      int numExcEdges = block->_exception_predecessors->length();

      _total_edges += numEdges;

      _total_exc_edges += numExcEdges;

      _max_block_edges = MAX2(numEdges,_max_block_edges);

      _max_block_exc_edges = MAX2(numExcEdges,_max_block_exc_edges);

    }

    int numLocals = _bit_map_size_bits;

    _total_method_locals += numLocals;

    _max_method_locals = MAX2(numLocals,_max_method_locals);

  }

#endif

}

void MethodLiveness::init_basic_blocks() {

  bool bailout = false;

  int method_len = method()->code_size();

  ciMethodBlocks *mblocks = method()->get_method_blocks();

  // Create an array to store the bci->BasicBlock mapping.

  _block_map = new (arena()) GrowableArray<BasicBlock*>(arena(), method_len, method_len, NULL);

  _block_count = mblocks->num_blocks();

  _block_list = (BasicBlock **) arena()->Amalloc(sizeof(BasicBlock *) * _block_count);

  // Used for patching up jsr/ret control flow.

  GrowableArray<BasicBlock*>* jsr_exit_list = new GrowableArray<BasicBlock*>(5);

  GrowableArray<BasicBlock*>* ret_list = new GrowableArray<BasicBlock*>(5);

  // generate our block list from ciMethodBlocks

  for (int blk = 0; blk < _block_count; blk++) {

    ciBlock *cib = mblocks->block(blk);

     int start_bci = cib->start_bci();

    _block_list[blk] = new (arena()) BasicBlock(this, start_bci, cib->limit_bci());

    _block_map->at_put(start_bci, _block_list[blk]);

#ifdef COMPILER1

    // mark all bcis where a new basic block starts

    _bci_block_start.set_bit(start_bci);

#endif // COMPILER1

  }

  // fill in the predecessors of blocks

  ciBytecodeStream bytes(method());

  for (int blk = 0; blk < _block_count; blk++) {

    BasicBlock *current_block = _block_list[blk];

    int bci =  mblocks->block(blk)->control_bci();

    if (bci == ciBlock::fall_through_bci) {

      int limit = current_block->limit_bci();

      if (limit < method_len) {

        BasicBlock *next = _block_map->at(limit);

        assert( next != NULL, "must be a block immediately following this one.");

        next->add_normal_predecessor(current_block);

      }

      continue;

    }

    bytes.reset_to_bci(bci);

    Bytecodes::Code code = bytes.next();

    BasicBlock *dest;

    // Now we need to interpret the instruction's effect

    // on control flow.

    assert (current_block != NULL, "we must have a current block");

    switch (code) {

      case Bytecodes::_ifeq:

      case Bytecodes::_ifne:

      case Bytecodes::_iflt:

      case Bytecodes::_ifge:

      case Bytecodes::_ifgt:

      case Bytecodes::_ifle:

      case Bytecodes::_if_icmpeq:

      case Bytecodes::_if_icmpne:

      case Bytecodes::_if_icmplt:

      case Bytecodes::_if_icmpge:

      case Bytecodes::_if_icmpgt:

      case Bytecodes::_if_icmple:

      case Bytecodes::_if_acmpeq:

      case Bytecodes::_if_acmpne:

      case Bytecodes::_ifnull:

      case Bytecodes::_ifnonnull:

        // Two way branch.  Set predecessors at each destination.

        dest = _block_map->at(bytes.next_bci());

        assert(dest != NULL, "must be a block immediately following this one.");

        dest->add_normal_predecessor(current_block);

        dest = _block_map->at(bytes.get_dest());

        assert(dest != NULL, "branch desination must start a block.");

        dest->add_normal_predecessor(current_block);

        break;

      case Bytecodes::_goto:

        dest = _block_map->at(bytes.get_dest());

        assert(dest != NULL, "branch desination must start a block.");

        dest->add_normal_predecessor(current_block);

        break;

      case Bytecodes::_goto_w:

        dest = _block_map->at(bytes.get_far_dest());

        assert(dest != NULL, "branch desination must start a block.");

        dest->add_normal_predecessor(current_block);

        break;

      case Bytecodes::_tableswitch:

        {

          Bytecode_tableswitch *tableswitch =

            Bytecode_tableswitch_at(bytes.cur_bcp());

          int len = tableswitch->length();

          dest = _block_map->at(bci + tableswitch->default_offset());

          assert(dest != NULL, "branch desination must start a block.");

          dest->add_normal_predecessor(current_block);

          while (--len >= 0) {

            dest = _block_map->at(bci + tableswitch->dest_offset_at(len));

            assert(dest != NULL, "branch desination must start a block.");

            dest->add_normal_predecessor(current_block);

          }

          break;

        }

      case Bytecodes::_lookupswitch:

        {

          Bytecode_lookupswitch *lookupswitch =

            Bytecode_lookupswitch_at(bytes.cur_bcp());

          int npairs = lookupswitch->number_of_pairs();

          dest = _block_map->at(bci + lookupswitch->default_offset());

          assert(dest != NULL, "branch desination must start a block.");

          dest->add_normal_predecessor(current_block);

          while(--npairs >= 0) {

            LookupswitchPair *pair = lookupswitch->pair_at(npairs);

            dest = _block_map->at( bci + pair->offset());

            assert(dest != NULL, "branch desination must start a block.");

            dest->add_normal_predecessor(current_block);

          }

          break;

        }

      case Bytecodes::_jsr:

        {

          assert(bytes.is_wide()==false, "sanity check");

          dest = _block_map->at(bytes.get_dest());

          assert(dest != NULL, "branch desination must start a block.");

          dest->add_normal_predecessor(current_block);

          BasicBlock *jsrExit = _block_map->at(current_block->limit_bci());

          assert(jsrExit != NULL, "jsr return bci must start a block.");

          jsr_exit_list->append(jsrExit);

          break;

        }

      case Bytecodes::_jsr_w:

        {

          dest = _block_map->at(bytes.get_far_dest());

          assert(dest != NULL, "branch desination must start a block.");

          dest->add_normal_predecessor(current_block);

          BasicBlock *jsrExit = _block_map->at(current_block->limit_bci());

          assert(jsrExit != NULL, "jsr return bci must start a block.");

          jsr_exit_list->append(jsrExit);

          break;

        }

      case Bytecodes::_wide:

        assert(false, "wide opcodes should not be seen here");

        break;

      case Bytecodes::_athrow:

      case Bytecodes::_ireturn:

      case Bytecodes::_lreturn:

      case Bytecodes::_freturn:

      case Bytecodes::_dreturn:

      case Bytecodes::_areturn:

      case Bytecodes::_return:

        // These opcodes are  not the normal predecessors of any other opcodes.

        break;

      case Bytecodes::_ret:

        // We will patch up jsr/rets in a subsequent pass.

        ret_list->append(current_block);

        break;

      case Bytecodes::_breakpoint:

        // Bail out of there are breakpoints in here.

        bailout = true;

        break;

      default:

        // Do nothing.

        break;

    }

  }

  // Patch up the jsr/ret's.  We conservatively assume that any ret

  // can return to any jsr site.

  int ret_list_len = ret_list->length();

  int jsr_exit_list_len = jsr_exit_list->length();

  if (ret_list_len > 0 && jsr_exit_list_len > 0) {

    for (int i = jsr_exit_list_len - 1; i >= 0; i--) {

      BasicBlock *jsrExit = jsr_exit_list->at(i);

      for (int i = ret_list_len - 1; i >= 0; i--) {

        jsrExit->add_normal_predecessor(ret_list->at(i));

      }

    }

  }

  // Compute exception edges.

  for (int b=_block_count-1; b >= 0; b--) {

    BasicBlock *block = _block_list[b];

    int block_start = block->start_bci();

    int block_limit = block->limit_bci();

    ciExceptionHandlerStream handlers(method());

    for (; !handlers.is_done(); handlers.next()) {

      ciExceptionHandler* handler = handlers.handler();

      int start       = handler->start();

      int limit       = handler->limit();

      int handler_bci = handler->handler_bci();

      int intersect_start = MAX2(block_start, start);

      int intersect_limit = MIN2(block_limit, limit);

      if (intersect_start < intersect_limit) {

        // The catch range has a nonempty intersection with this

        // basic block.  That means this basic block can be an

        // exceptional predecessor.

        _block_map->at(handler_bci)->add_exception_predecessor(block);

        if (handler->is_catch_all()) {

          // This is a catch-all block.

          if (intersect_start == block_start && intersect_limit == block_limit) {

            // The basic block is entirely contained in this catch-all block.

            // Skip the rest of the exception handlers -- they can never be

            // reached in execution.

            break;

          }

        }

      }

    }

  }

}

void MethodLiveness::init_gen_kill() {

  for (int i=_block_count-1; i >= 0; i--) {

    _block_list[i]->compute_gen_kill(method());

  }

}

void MethodLiveness::propagate_liveness() {

  int num_blocks = _block_count;

  BasicBlock *block;

  // We start our work list off with all blocks in it.

  // Alternately, we could start off the work list with the list of all

  // blocks which could exit the method directly, along with one block

  // from any infinite loop.  If this matters, it can be changed.  It

  // may not be clear from looking at the code, but the order of the

  // workList will be the opposite of the creation order of the basic

  // blocks, which should be decent for quick convergence (with the

  // possible exception of exception handlers, which are all created

  // early).

  _work_list = NULL;

  for (int i = 0; i < num_blocks; i++) {

    block = _block_list[i];

    block->set_next(_work_list);

    block->set_on_work_list(true);

    _work_list = block;

  }

  while ((block = work_list_get()) != NULL) {

    block->propagate(this);

    NOT_PRODUCT(_total_visits++;)

  }

}

void MethodLiveness::work_list_add(BasicBlock *block) {

  if (!block->on_work_list()) {

    block->set_next(_work_list);

    block->set_on_work_list(true);

    _work_list = block;

  }

}

MethodLiveness::BasicBlock *MethodLiveness::work_list_get() {

  BasicBlock *block = _work_list;

  if (block != NULL) {

    block->set_on_work_list(false);

    _work_list = block->next();

  }

  return block;

}

MethodLivenessResult MethodLiveness::get_liveness_at(int entry_bci) {

  int bci = entry_bci;

  bool is_entry = false;

  if (entry_bci == InvocationEntryBci) {

    is_entry = true;

    bci = 0;

  }

  MethodLivenessResult answer(NULL,0);

  if (_block_count > 0) {

    if (TimeLivenessAnalysis) _time_total.start();

    if (TimeLivenessAnalysis) _time_query.start();

    assert( 0 <= bci && bci < method()->code_size(), "bci out of range" );

    BasicBlock *block = _block_map->at(bci);

    // We may not be at the block start, so search backwards to find the block

    // containing bci.

    int t = bci;

    while (block == NULL && t > 0) {

     block = _block_map->at(--t);

    }

    assert( block != NULL, "invalid bytecode index; must be instruction index" );

    assert(bci >= block->start_bci() && bci < block->limit_bci(), "block must contain bci.");

    answer = block->get_liveness_at(method(), bci);

    if (is_entry && method()->is_synchronized() && !method()->is_static()) {

      // Synchronized methods use the receiver once on entry.

      answer.at_put(0, true);

    }

#ifndef PRODUCT

    if (TraceLivenessQuery) {

      tty->print("Liveness query of ");

      method()->print_short_name();

      tty->print(" @ %d : result is ", bci);

      answer.print_on(tty);

    }

    if (TimeLivenessAnalysis) _time_query.stop();

    if (TimeLivenessAnalysis) _time_total.stop();

#endif

  }

#ifndef PRODUCT

  if (TimeLivenessAnalysis) {

    // Collect statistics.

    _total_locals_queried += _bit_map_size_bits;

    BitCounter counter;

    answer.iterate(&counter);

    _total_live_locals_queried += counter.count();

  }

#endif

  return answer;

}

#ifndef PRODUCT

void MethodLiveness::print_times() {

  tty->print_cr ("Accumulated liveness analysis times/statistics:");

  tty->print_cr ("-----------------------------------------------");

  tty->print_cr ("  Total         : %3.3f sec.", _time_total.seconds());

  tty->print_cr ("    Build graph : %3.3f sec. (%2.2f%%)", _time_build_graph.seconds(),

                 _time_build_graph.seconds() * 100 / _time_total.seconds());

  tty->print_cr ("    Gen / Kill  : %3.3f sec. (%2.2f%%)", _time_gen_kill.seconds(),