/*

 * Copyright (c) 1997, 2011, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 *

 */

#include "precompiled.hpp"

#include "interpreter/bytecodeStream.hpp"

#include "oops/generateOopMap.hpp"

#include "oops/oop.inline.hpp"

#include "oops/symbol.hpp"

#include "runtime/handles.inline.hpp"

#include "runtime/java.hpp"

#include "runtime/relocator.hpp"

#include "utilities/bitMap.inline.hpp"

//

//

// Compute stack layouts for each instruction in method.

//

//  Problems:

//  - What to do about jsr with different types of local vars?

//  Need maps that are conditional on jsr path?

//  - Jsr and exceptions should be done more efficiently (the retAddr stuff)

//

//  Alternative:

//  - Could extend verifier to provide this information.

//    For: one fewer abstract interpreter to maintain. Against: the verifier

//    solves a bigger problem so slower (undesirable to force verification of

//    everything?).

//

//  Algorithm:

//    Partition bytecodes into basic blocks

//    For each basic block: store entry state (vars, stack). For instructions

//    inside basic blocks we do not store any state (instead we recompute it

//    from state produced by previous instruction).

//

//    Perform abstract interpretation of bytecodes over this lattice:

//

//                _--'#'--_

//               /  /  \   \

//             /   /     \   \

//            /    |     |     \

//          'r'   'v'   'p'   ' '

//           \     |     |     /

//            \    \     /    /

//              \   \   /    /

//                -- '@' --

//

//    '#'  top, result of conflict merge

//    'r'  reference type

//    'v'  value type

//    'p'  pc type for jsr/ret

//    ' '  uninitialized; never occurs on operand stack in Java

//    '@'  bottom/unexecuted; initial state each bytecode.

//

//    Basic block headers are the only merge points. We use this iteration to

//    compute the information:

//

//    find basic blocks;

//    initialize them with uninitialized state;

//    initialize first BB according to method signature;

//    mark first BB changed

//    while (some BB is changed) do {

//      perform abstract interpration of all bytecodes in BB;

//      merge exit state of BB into entry state of all successor BBs,

//      noting if any of these change;

//    }

//

//  One additional complication is necessary. The jsr instruction pushes

//  a return PC on the stack (a 'p' type in the abstract interpretation).

//  To be able to process "ret" bytecodes, we keep track of these return

//  PC's in a 'retAddrs' structure in abstract interpreter context (when

//  processing a "ret" bytecodes, it is not sufficient to know that it gets

//  an argument of the right type 'p'; we need to know which address it

//  returns to).

//

// (Note this comment is borrowed form the original author of the algorithm)

// ComputeCallStack

//

// Specialization of SignatureIterator - compute the effects of a call

//

class ComputeCallStack : public SignatureIterator {

  CellTypeState *_effect;

  int _idx;

  void setup();

  void set(CellTypeState state)         { _effect[_idx++] = state; }

  int  length()                         { return _idx; };

  virtual void do_bool  ()              { set(CellTypeState::value); };

  virtual void do_char  ()              { set(CellTypeState::value); };

  virtual void do_float ()              { set(CellTypeState::value); };

  virtual void do_byte  ()              { set(CellTypeState::value); };

  virtual void do_short ()              { set(CellTypeState::value); };

  virtual void do_int   ()              { set(CellTypeState::value); };

  virtual void do_void  ()              { set(CellTypeState::bottom);};

  virtual void do_object(int begin, int end)  { set(CellTypeState::ref); };

  virtual void do_array (int begin, int end)  { set(CellTypeState::ref); };

  void do_double()                      { set(CellTypeState::value);

                                          set(CellTypeState::value); }

  void do_long  ()                      { set(CellTypeState::value);

                                           set(CellTypeState::value); }

public:

  ComputeCallStack(Symbol* signature) : SignatureIterator(signature) {};

  // Compute methods

  int compute_for_parameters(bool is_static, CellTypeState *effect) {

    _idx    = 0;

    _effect = effect;

    if (!is_static)

      effect[_idx++] = CellTypeState::ref;

    iterate_parameters();

    return length();

  };

  int compute_for_returntype(CellTypeState *effect) {

    _idx    = 0;

    _effect = effect;

    iterate_returntype();

    set(CellTypeState::bottom);  // Always terminate with a bottom state, so ppush works

    return length();

  }

};

//=========================================================================================

// ComputeEntryStack

//

// Specialization of SignatureIterator - in order to set up first stack frame

//

class ComputeEntryStack : public SignatureIterator {

  CellTypeState *_effect;

  int _idx;

  void setup();

  void set(CellTypeState state)         { _effect[_idx++] = state; }

  int  length()                         { return _idx; };

  virtual void do_bool  ()              { set(CellTypeState::value); };

  virtual void do_char  ()              { set(CellTypeState::value); };

  virtual void do_float ()              { set(CellTypeState::value); };

  virtual void do_byte  ()              { set(CellTypeState::value); };

  virtual void do_short ()              { set(CellTypeState::value); };

  virtual void do_int   ()              { set(CellTypeState::value); };

  virtual void do_void  ()              { set(CellTypeState::bottom);};

  virtual void do_object(int begin, int end)  { set(CellTypeState::make_slot_ref(_idx)); }

  virtual void do_array (int begin, int end)  { set(CellTypeState::make_slot_ref(_idx)); }

  void do_double()                      { set(CellTypeState::value);

                                          set(CellTypeState::value); }

  void do_long  ()                      { set(CellTypeState::value);

                                          set(CellTypeState::value); }

public:

  ComputeEntryStack(Symbol* signature) : SignatureIterator(signature) {};

  // Compute methods

  int compute_for_parameters(bool is_static, CellTypeState *effect) {

    _idx    = 0;

    _effect = effect;

    if (!is_static)

      effect[_idx++] = CellTypeState::make_slot_ref(0);

    iterate_parameters();

    return length();

  };

  int compute_for_returntype(CellTypeState *effect) {

    _idx    = 0;

    _effect = effect;

    iterate_returntype();

    set(CellTypeState::bottom);  // Always terminate with a bottom state, so ppush works

    return length();

  }

};

//=====================================================================================

//

// Implementation of RetTable/RetTableEntry

//

// Contains function to itereate through all bytecodes

// and find all return entry points

//

int RetTable::_init_nof_entries = 10;

int RetTableEntry::_init_nof_jsrs = 5;

void RetTableEntry::add_delta(int bci, int delta) {

  if (_target_bci > bci) _target_bci += delta;

  for (int k = 0; k < _jsrs->length(); k++) {

    int jsr = _jsrs->at(k);

    if (jsr > bci) _jsrs->at_put(k, jsr+delta);

  }

}

void RetTable::compute_ret_table(methodHandle method) {

  BytecodeStream i(method);

  Bytecodes::Code bytecode;

  while( (bytecode = i.next()) >= 0) {

    switch (bytecode) {

      case Bytecodes::_jsr:

        add_jsr(i.next_bci(), i.dest());

        break;

      case Bytecodes::_jsr_w:

        add_jsr(i.next_bci(), i.dest_w());

        break;

    }

  }

}

void RetTable::add_jsr(int return_bci, int target_bci) {

  RetTableEntry* entry = _first;

  // Scan table for entry

  for (;entry && entry->target_bci() != target_bci; entry = entry->next());

  if (!entry) {

    // Allocate new entry and put in list

    entry = new RetTableEntry(target_bci, _first);

    _first = entry;

  }

  // Now "entry" is set.  Make sure that the entry is initialized

  // and has room for the new jsr.

  entry->add_jsr(return_bci);

}

RetTableEntry* RetTable::find_jsrs_for_target(int targBci) {

  RetTableEntry *cur = _first;

  while(cur) {

    assert(cur->target_bci() != -1, "sanity check");

    if (cur->target_bci() == targBci)  return cur;

    cur = cur->next();

  }

  ShouldNotReachHere();

  return NULL;

}

// The instruction at bci is changing size by "delta".  Update the return map.

void RetTable::update_ret_table(int bci, int delta) {

  RetTableEntry *cur = _first;

  while(cur) {

    cur->add_delta(bci, delta);

    cur = cur->next();

  }

}

//

// Celltype state

//

CellTypeState CellTypeState::bottom      = CellTypeState::make_bottom();

CellTypeState CellTypeState::uninit      = CellTypeState::make_any(uninit_value);

CellTypeState CellTypeState::ref         = CellTypeState::make_any(ref_conflict);

CellTypeState CellTypeState::value       = CellTypeState::make_any(val_value);

CellTypeState CellTypeState::refUninit   = CellTypeState::make_any(ref_conflict | uninit_value);

CellTypeState CellTypeState::top         = CellTypeState::make_top();

CellTypeState CellTypeState::addr        = CellTypeState::make_any(addr_conflict);

// Commonly used constants

static CellTypeState epsilonCTS[1] = { CellTypeState::bottom };

static CellTypeState   refCTS   = CellTypeState::ref;

static CellTypeState   valCTS   = CellTypeState::value;

static CellTypeState    vCTS[2] = { CellTypeState::value, CellTypeState::bottom };

static CellTypeState    rCTS[2] = { CellTypeState::ref,   CellTypeState::bottom };

static CellTypeState   rrCTS[3] = { CellTypeState::ref,   CellTypeState::ref,   CellTypeState::bottom };

static CellTypeState   vrCTS[3] = { CellTypeState::value, CellTypeState::ref,   CellTypeState::bottom };

static CellTypeState   vvCTS[3] = { CellTypeState::value, CellTypeState::value, CellTypeState::bottom };

static CellTypeState  rvrCTS[4] = { CellTypeState::ref,   CellTypeState::value, CellTypeState::ref,   CellTypeState::bottom };

static CellTypeState  vvrCTS[4] = { CellTypeState::value, CellTypeState::value, CellTypeState::ref,   CellTypeState::bottom };

static CellTypeState  vvvCTS[4] = { CellTypeState::value, CellTypeState::value, CellTypeState::value, CellTypeState::bottom };

static CellTypeState vvvrCTS[5] = { CellTypeState::value, CellTypeState::value, CellTypeState::value, CellTypeState::ref,   CellTypeState::bottom };

static CellTypeState vvvvCTS[5] = { CellTypeState::value, CellTypeState::value, CellTypeState::value, CellTypeState::value, CellTypeState::bottom };

char CellTypeState::to_char() const {

  if (can_be_reference()) {

    if (can_be_value() || can_be_address())

      return '#';    // Conflict that needs to be rewritten

    else

      return 'r';

  } else if (can_be_value())

    return 'v';

  else if (can_be_address())

    return 'p';

  else if (can_be_uninit())

    return ' ';

  else

    return '@';

}

// Print a detailed CellTypeState.  Indicate all bits that are set.  If

// the CellTypeState represents an address or a reference, print the

// value of the additional information.

void CellTypeState::print(outputStream *os) {

  if (can_be_address()) {

    os->print("(p");

  } else {

    os->print("( ");

  }

  if (can_be_reference()) {

    os->print("r");

  } else {

    os->print(" ");

  }

  if (can_be_value()) {

    os->print("v");

  } else {

    os->print(" ");

  }

  if (can_be_uninit()) {

    os->print("u|");

  } else {

    os->print(" |");

  }

  if (is_info_top()) {

    os->print("Top)");

  } else if (is_info_bottom()) {

    os->print("Bot)");

  } else {

    if (is_reference()) {

      int info = get_info();

      int data = info & ~(ref_not_lock_bit | ref_slot_bit);

      if (info & ref_not_lock_bit) {

        // Not a monitor lock reference.

        if (info & ref_slot_bit) {

          // slot

          os->print("slot%d)", data);

        } else {

          // line

          os->print("line%d)", data);

        }

      } else {

        // lock

        os->print("lock%d)", data);

      }

    } else {

      os->print("%d)", get_info());

    }

  }

}

//

// Basicblock handling methods

//

void GenerateOopMap ::initialize_bb() {

  _gc_points = 0;

  _bb_count  = 0;

  _bb_hdr_bits.clear();

  _bb_hdr_bits.resize(method()->code_size());

}

void GenerateOopMap::bb_mark_fct(GenerateOopMap *c, int bci, int *data) {

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

  if (c->is_bb_header(bci))

     return;

  if (TraceNewOopMapGeneration) {

     tty->print_cr("Basicblock#%d begins at: %d", c->_bb_count, bci);

  }

  c->set_bbmark_bit(bci);

  c->_bb_count++;

}

void GenerateOopMap::mark_bbheaders_and_count_gc_points() {

  initialize_bb();

  bool fellThrough = false;  // False to get first BB marked.

  // First mark all exception handlers as start of a basic-block

  typeArrayOop excps = method()->exception_table();

  for(int i = 0; i < excps->length(); i += 4) {

    int handler_pc_idx = i+2;

    bb_mark_fct(this, excps->int_at(handler_pc_idx), NULL);

  }

  // Then iterate through the code

  BytecodeStream bcs(_method);

  Bytecodes::Code bytecode;

  while( (bytecode = bcs.next()) >= 0) {

    int bci = bcs.bci();

    if (!fellThrough)

        bb_mark_fct(this, bci, NULL);

    fellThrough = jump_targets_do(&bcs, &GenerateOopMap::bb_mark_fct, NULL);

     /* We will also mark successors of jsr's as basic block headers. */

    switch (bytecode) {

      case Bytecodes::_jsr:

        assert(!fellThrough, "should not happen");

        bb_mark_fct(this, bci + Bytecodes::length_for(bytecode), NULL);

        break;

      case Bytecodes::_jsr_w:

        assert(!fellThrough, "should not happen");

        bb_mark_fct(this, bci + Bytecodes::length_for(bytecode), NULL);

        break;

    }

    if (possible_gc_point(&bcs))

      _gc_points++;

  }

}

void GenerateOopMap::reachable_basicblock(GenerateOopMap *c, int bci, int *data) {

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

  BasicBlock* bb = c->get_basic_block_at(bci);

  if (bb->is_dead()) {

    bb->mark_as_alive();

    *data = 1; // Mark basicblock as changed

  }

}

void GenerateOopMap::mark_reachable_code() {

  int change = 1; // int to get function pointers to work

  // Mark entry basic block as alive and all exception handlers

  _basic_blocks[0].mark_as_alive();

  typeArrayOop excps = method()->exception_table();

  for(int i = 0; i < excps->length(); i += 4) {

    int handler_pc_idx = i+2;

    BasicBlock *bb = get_basic_block_at(excps->int_at(handler_pc_idx));

    // If block is not already alive (due to multiple exception handlers to same bb), then

    // make it alive

    if (bb->is_dead()) bb->mark_as_alive();

  }

  BytecodeStream bcs(_method);

  // Iterate through all basic blocks until we reach a fixpoint

  while (change) {

    change = 0;

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

      BasicBlock *bb = &_basic_blocks[i];

      if (bb->is_alive()) {

        // Position bytecodestream at last bytecode in basicblock

        bcs.set_start(bb->_end_bci);

        bcs.next();

        Bytecodes::Code bytecode = bcs.code();

        int bci = bcs.bci();

        assert(bci == bb->_end_bci, "wrong bci");

        bool fell_through = jump_targets_do(&bcs, &GenerateOopMap::reachable_basicblock, &change);

        // We will also mark successors of jsr's as alive.

        switch (bytecode) {

          case Bytecodes::_jsr:

          case Bytecodes::_jsr_w:

            assert(!fell_through, "should not happen");

            reachable_basicblock(this, bci + Bytecodes::length_for(bytecode), &change);

            break;

        }

        if (fell_through) {

          // Mark successor as alive

          if (bb[1].is_dead()) {

            bb[1].mark_as_alive();

            change = 1;

          }

        }

      }

    }

  }

}

/* If the current instruction in "c" has no effect on control flow,

   returns "true".  Otherwise, calls "jmpFct" one or more times, with

   "c", an appropriate "pcDelta", and "data" as arguments, then

   returns "false".  There is one exception: if the current

   instruction is a "ret", returns "false" without calling "jmpFct".

   Arrangements for tracking the control flow of a "ret" must be made

   externally. */

bool GenerateOopMap::jump_targets_do(BytecodeStream *bcs, jmpFct_t jmpFct, int *data) {

  int bci = bcs->bci();

  switch (bcs->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: