/*

 * Copyright (c) 1997, 2014, 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 "ci/bcEscapeAnalyzer.hpp"

#include "compiler/oopMap.hpp"

#include "opto/callGenerator.hpp"

#include "opto/callnode.hpp"

#include "opto/castnode.hpp"

#include "opto/escape.hpp"

#include "opto/locknode.hpp"

#include "opto/machnode.hpp"

#include "opto/matcher.hpp"

#include "opto/parse.hpp"

#include "opto/regalloc.hpp"

#include "opto/regmask.hpp"

#include "opto/rootnode.hpp"

#include "opto/runtime.hpp"

// Portions of code courtesy of Clifford Click

// Optimization - Graph Style

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

uint StartNode::size_of() const { return sizeof(*this); }

uint StartNode::cmp( const Node &n ) const

{ return _domain == ((StartNode&)n)._domain; }

const Type *StartNode::bottom_type() const { return _domain; }

const Type *StartNode::Value(PhaseTransform *phase) const { return _domain; }

#ifndef PRODUCT

void StartNode::dump_spec(outputStream *st) const { st->print(" #"); _domain->dump_on(st);}

#endif

//------------------------------Ideal------------------------------------------

Node *StartNode::Ideal(PhaseGVN *phase, bool can_reshape){

  return remove_dead_region(phase, can_reshape) ? this : NULL;

}

//------------------------------calling_convention-----------------------------

void StartNode::calling_convention( BasicType* sig_bt, VMRegPair *parm_regs, uint argcnt ) const {

  Matcher::calling_convention( sig_bt, parm_regs, argcnt, false );

}

//------------------------------Registers--------------------------------------

const RegMask &StartNode::in_RegMask(uint) const {

  return RegMask::Empty;

}

//------------------------------match------------------------------------------

// Construct projections for incoming parameters, and their RegMask info

Node *StartNode::match( const ProjNode *proj, const Matcher *match ) {

  switch (proj->_con) {

  case TypeFunc::Control:

  case TypeFunc::I_O:

  case TypeFunc::Memory:

    return new MachProjNode(this,proj->_con,RegMask::Empty,MachProjNode::unmatched_proj);

  case TypeFunc::FramePtr:

    return new MachProjNode(this,proj->_con,Matcher::c_frame_ptr_mask, Op_RegP);

  case TypeFunc::ReturnAdr:

    return new MachProjNode(this,proj->_con,match->_return_addr_mask,Op_RegP);

  case TypeFunc::Parms:

  default: {

      uint parm_num = proj->_con - TypeFunc::Parms;

      const Type *t = _domain->field_at(proj->_con);

      if (t->base() == Type::Half)  // 2nd half of Longs and Doubles

        return new ConNode(Type::TOP);

      uint ideal_reg = t->ideal_reg();

      RegMask &rm = match->_calling_convention_mask[parm_num];

      return new MachProjNode(this,proj->_con,rm,ideal_reg);

    }

  }

  return NULL;

}

//------------------------------StartOSRNode----------------------------------

// The method start node for an on stack replacement adapter

//------------------------------osr_domain-----------------------------

const TypeTuple *StartOSRNode::osr_domain() {

  const Type **fields = TypeTuple::fields(2);

  fields[TypeFunc::Parms+0] = TypeRawPtr::BOTTOM;  // address of osr buffer

  return TypeTuple::make(TypeFunc::Parms+1, fields);

}

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

const char * const ParmNode::names[TypeFunc::Parms+1] = {

  "Control", "I_O", "Memory", "FramePtr", "ReturnAdr", "Parms"

};

#ifndef PRODUCT

void ParmNode::dump_spec(outputStream *st) const {

  if( _con < TypeFunc::Parms ) {

    st->print("%s", names[_con]);

  } else {

    st->print("Parm%d: ",_con-TypeFunc::Parms);

    // Verbose and WizardMode dump bottom_type for all nodes

    if( !Verbose && !WizardMode )   bottom_type()->dump_on(st);

  }

}

#endif

uint ParmNode::ideal_reg() const {

  switch( _con ) {

  case TypeFunc::Control  : // fall through

  case TypeFunc::I_O      : // fall through

  case TypeFunc::Memory   : return 0;

  case TypeFunc::FramePtr : // fall through

  case TypeFunc::ReturnAdr: return Op_RegP;

  default                 : assert( _con > TypeFunc::Parms, "" );

    // fall through

  case TypeFunc::Parms    : {

    // Type of argument being passed

    const Type *t = in(0)->as_Start()->_domain->field_at(_con);

    return t->ideal_reg();

  }

  }

  ShouldNotReachHere();

  return 0;

}

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

ReturnNode::ReturnNode(uint edges, Node *cntrl, Node *i_o, Node *memory, Node *frameptr, Node *retadr ) : Node(edges) {

  init_req(TypeFunc::Control,cntrl);

  init_req(TypeFunc::I_O,i_o);

  init_req(TypeFunc::Memory,memory);

  init_req(TypeFunc::FramePtr,frameptr);

  init_req(TypeFunc::ReturnAdr,retadr);

}

Node *ReturnNode::Ideal(PhaseGVN *phase, bool can_reshape){

  return remove_dead_region(phase, can_reshape) ? this : NULL;

}

const Type *ReturnNode::Value( PhaseTransform *phase ) const {

  return ( phase->type(in(TypeFunc::Control)) == Type::TOP)

    ? Type::TOP

    : Type::BOTTOM;

}

// Do we Match on this edge index or not?  No edges on return nodes

uint ReturnNode::match_edge(uint idx) const {

  return 0;

}

#ifndef PRODUCT

void ReturnNode::dump_req(outputStream *st) const {

  // Dump the required inputs, enclosed in '(' and ')'

  uint i;                       // Exit value of loop

  for (i = 0; i < req(); i++) {    // For all required inputs

    if (i == TypeFunc::Parms) st->print("returns");

    if (in(i)) st->print("%c%d ", Compile::current()->node_arena()->contains(in(i)) ? ' ' : 'o', in(i)->_idx);

    else st->print("_ ");

  }

}

#endif

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

RethrowNode::RethrowNode(

  Node* cntrl,

  Node* i_o,

  Node* memory,

  Node* frameptr,

  Node* ret_adr,

  Node* exception

) : Node(TypeFunc::Parms + 1) {

  init_req(TypeFunc::Control  , cntrl    );

  init_req(TypeFunc::I_O      , i_o      );

  init_req(TypeFunc::Memory   , memory   );

  init_req(TypeFunc::FramePtr , frameptr );

  init_req(TypeFunc::ReturnAdr, ret_adr);

  init_req(TypeFunc::Parms    , exception);

}

Node *RethrowNode::Ideal(PhaseGVN *phase, bool can_reshape){

  return remove_dead_region(phase, can_reshape) ? this : NULL;

}

const Type *RethrowNode::Value( PhaseTransform *phase ) const {

  return (phase->type(in(TypeFunc::Control)) == Type::TOP)

    ? Type::TOP

    : Type::BOTTOM;

}

uint RethrowNode::match_edge(uint idx) const {

  return 0;

}

#ifndef PRODUCT

void RethrowNode::dump_req(outputStream *st) const {

  // Dump the required inputs, enclosed in '(' and ')'

  uint i;                       // Exit value of loop

  for (i = 0; i < req(); i++) {    // For all required inputs

    if (i == TypeFunc::Parms) st->print("exception");

    if (in(i)) st->print("%c%d ", Compile::current()->node_arena()->contains(in(i)) ? ' ' : 'o', in(i)->_idx);

    else st->print("_ ");

  }

}

#endif

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

// Do we Match on this edge index or not?  Match only target address & method

uint TailCallNode::match_edge(uint idx) const {

  return TypeFunc::Parms <= idx  &&  idx <= TypeFunc::Parms+1;

}

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

// Do we Match on this edge index or not?  Match only target address & oop

uint TailJumpNode::match_edge(uint idx) const {

  return TypeFunc::Parms <= idx  &&  idx <= TypeFunc::Parms+1;

}

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

JVMState::JVMState(ciMethod* method, JVMState* caller) :

  _method(method) {

  assert(method != NULL, "must be valid call site");

  _reexecute = Reexecute_Undefined;

  debug_only(_bci = -99);  // random garbage value

  debug_only(_map = (SafePointNode*)-1);

  _caller = caller;

  _depth  = 1 + (caller == NULL ? 0 : caller->depth());

  _locoff = TypeFunc::Parms;

  _stkoff = _locoff + _method->max_locals();

  _monoff = _stkoff + _method->max_stack();

  _scloff = _monoff;

  _endoff = _monoff;

  _sp = 0;

}

JVMState::JVMState(int stack_size) :

  _method(NULL) {

  _bci = InvocationEntryBci;

  _reexecute = Reexecute_Undefined;

  debug_only(_map = (SafePointNode*)-1);

  _caller = NULL;

  _depth  = 1;

  _locoff = TypeFunc::Parms;

  _stkoff = _locoff;

  _monoff = _stkoff + stack_size;

  _scloff = _monoff;

  _endoff = _monoff;

  _sp = 0;

}

//--------------------------------of_depth-------------------------------------

JVMState* JVMState::of_depth(int d) const {

  const JVMState* jvmp = this;

  assert(0 < d && (uint)d <= depth(), "oob");

  for (int skip = depth() - d; skip > 0; skip--) {

    jvmp = jvmp->caller();

  }

  assert(jvmp->depth() == (uint)d, "found the right one");

  return (JVMState*)jvmp;

}

//-----------------------------same_calls_as-----------------------------------

bool JVMState::same_calls_as(const JVMState* that) const {

  if (this == that)                    return true;

  if (this->depth() != that->depth())  return false;

  const JVMState* p = this;

  const JVMState* q = that;

  for (;;) {

    if (p->_method != q->_method)    return false;

    if (p->_method == NULL)          return true;   // bci is irrelevant

    if (p->_bci    != q->_bci)       return false;

    if (p->_reexecute != q->_reexecute)  return false;

    p = p->caller();

    q = q->caller();

    if (p == q)                      return true;

    assert(p != NULL && q != NULL, "depth check ensures we don't run off end");

  }

}

//------------------------------debug_start------------------------------------

uint JVMState::debug_start()  const {

  debug_only(JVMState* jvmroot = of_depth(1));

  assert(jvmroot->locoff() <= this->locoff(), "youngest JVMState must be last");

  return of_depth(1)->locoff();

}

//-------------------------------debug_end-------------------------------------

uint JVMState::debug_end() const {

  debug_only(JVMState* jvmroot = of_depth(1));

  assert(jvmroot->endoff() <= this->endoff(), "youngest JVMState must be last");

  return endoff();

}

//------------------------------debug_depth------------------------------------

uint JVMState::debug_depth() const {

  uint total = 0;

  for (const JVMState* jvmp = this; jvmp != NULL; jvmp = jvmp->caller()) {

    total += jvmp->debug_size();

  }

  return total;

}

#ifndef PRODUCT

//------------------------------format_helper----------------------------------

// Given an allocation (a Chaitin object) and a Node decide if the Node carries

// any defined value or not.  If it does, print out the register or constant.

static void format_helper( PhaseRegAlloc *regalloc, outputStream* st, Node *n, const char *msg, uint i, GrowableArray<SafePointScalarObjectNode*> *scobjs ) {

  if (n == NULL) { st->print(" NULL"); return; }

  if (n->is_SafePointScalarObject()) {

    // Scalar replacement.

    SafePointScalarObjectNode* spobj = n->as_SafePointScalarObject();

    scobjs->append_if_missing(spobj);

    int sco_n = scobjs->find(spobj);

    assert(sco_n >= 0, "");

    st->print(" %s%d]=#ScObj" INT32_FORMAT, msg, i, sco_n);

    return;

  }

  if (regalloc->node_regs_max_index() > 0 &&

      OptoReg::is_valid(regalloc->get_reg_first(n))) { // Check for undefined

    char buf[50];

    regalloc->dump_register(n,buf);

    st->print(" %s%d]=%s",msg,i,buf);

  } else {                      // No register, but might be constant

    const Type *t = n->bottom_type();

    switch (t->base()) {

    case Type::Int:

      st->print(" %s%d]=#"INT32_FORMAT,msg,i,t->is_int()->get_con());

      break;

    case Type::AnyPtr:

      assert( t == TypePtr::NULL_PTR || n->in_dump(), "" );

      st->print(" %s%d]=#NULL",msg,i);

      break;

    case Type::AryPtr:

    case Type::InstPtr:

      st->print(" %s%d]=#Ptr" INTPTR_FORMAT,msg,i,p2i(t->isa_oopptr()->const_oop()));

      break;

    case Type::KlassPtr:

      st->print(" %s%d]=#Ptr" INTPTR_FORMAT,msg,i,p2i(t->make_ptr()->isa_klassptr()->klass()));

      break;

    case Type::MetadataPtr:

      st->print(" %s%d]=#Ptr" INTPTR_FORMAT,msg,i,p2i(t->make_ptr()->isa_metadataptr()->metadata()));

      break;

    case Type::NarrowOop:

      st->print(" %s%d]=#Ptr" INTPTR_FORMAT,msg,i,p2i(t->make_ptr()->isa_oopptr()->const_oop()));

      break;

    case Type::RawPtr:

      st->print(" %s%d]=#Raw" INTPTR_FORMAT,msg,i,p2i(t->is_rawptr()));

      break;

    case Type::DoubleCon:

      st->print(" %s%d]=#%fD",msg,i,t->is_double_constant()->_d);

      break;

    case Type::FloatCon:

      st->print(" %s%d]=#%fF",msg,i,t->is_float_constant()->_f);

      break;

    case Type::Long:

      st->print(" %s%d]=#"INT64_FORMAT,msg,i,(int64_t)(t->is_long()->get_con()));

      break;

    case Type::Half:

    case Type::Top:

      st->print(" %s%d]=_",msg,i);

      break;

    default: ShouldNotReachHere();

    }

  }

}

//------------------------------format-----------------------------------------

void JVMState::format(PhaseRegAlloc *regalloc, const Node *n, outputStream* st) const {

  st->print("        #");

  if (_method) {

    _method->print_short_name(st);

    st->print(" @ bci:%d ",_bci);

  } else {

    st->print_cr(" runtime stub ");

    return;

  }

  if (n->is_MachSafePoint()) {

    GrowableArray<SafePointScalarObjectNode*> scobjs;

    MachSafePointNode *mcall = n->as_MachSafePoint();

    uint i;

    // Print locals

    for (i = 0; i < (uint)loc_size(); i++)

      format_helper(regalloc, st, mcall->local(this, i), "L[", i, &scobjs);

    // Print stack

    for (i = 0; i < (uint)stk_size(); i++) {

      if ((uint)(_stkoff + i) >= mcall->len())

        st->print(" oob ");

      else

       format_helper(regalloc, st, mcall->stack(this, i), "STK[", i, &scobjs);

    }

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

      Node *box = mcall->monitor_box(this, i);

      Node *obj = mcall->monitor_obj(this, i);

      if (regalloc->node_regs_max_index() > 0 &&

          OptoReg::is_valid(regalloc->get_reg_first(box))) {

        box = BoxLockNode::box_node(box);

        format_helper(regalloc, st, box, "MON-BOX[", i, &scobjs);

      } else {

        OptoReg::Name box_reg = BoxLockNode::reg(box);

        st->print(" MON-BOX%d=%s+%d",

                   i,

                   OptoReg::regname(OptoReg::c_frame_pointer),

                   regalloc->reg2offset(box_reg));

      }

      const char* obj_msg = "MON-OBJ[";

      if (EliminateLocks) {

        if (BoxLockNode::box_node(box)->is_eliminated())

          obj_msg = "MON-OBJ(LOCK ELIMINATED)[";

      }

      format_helper(regalloc, st, obj, obj_msg, i, &scobjs);

    }

    for (i = 0; i < (uint)scobjs.length(); i++) {

      // Scalar replaced objects.

      st->cr();

      st->print("        # ScObj" INT32_FORMAT " ", i);

      SafePointScalarObjectNode* spobj = scobjs.at(i);

      ciKlass* cik = spobj->bottom_type()->is_oopptr()->klass();

      assert(cik->is_instance_klass() ||

             cik->is_array_klass(), "Not supported allocation.");

      ciInstanceKlass *iklass = NULL;

      if (cik->is_instance_klass()) {

        cik->print_name_on(st);

        iklass = cik->as_instance_klass();

      } else if (cik->is_type_array_klass()) {

        cik->as_array_klass()->base_element_type()->print_name_on(st);

        st->print("[%d]", spobj->n_fields());

      } else if (cik->is_obj_array_klass()) {

        ciKlass* cie = cik->as_obj_array_klass()->base_element_klass();

        if (cie->is_instance_klass()) {

          cie->print_name_on(st);

        } else if (cie->is_type_array_klass()) {

          cie->as_array_klass()->base_element_type()->print_name_on(st);

        } else {

          ShouldNotReachHere();

        }

        st->print("[%d]", spobj->n_fields());

        int ndim = cik->as_array_klass()->dimension() - 1;

        while (ndim-- > 0) {

          st->print("[]");

        }

      }

      st->print("={");

      uint nf = spobj->n_fields();

      if (nf > 0) {

        uint first_ind = spobj->first_index(mcall->jvms());

        Node* fld_node = mcall->in(first_ind);

        ciField* cifield;

        if (iklass != NULL) {

          st->print(" [");

          cifield = iklass->nonstatic_field_at(0);

          cifield->print_name_on(st);

          format_helper(regalloc, st, fld_node, ":", 0, &scobjs);

        } else {

          format_helper(regalloc, st, fld_node, "[", 0, &scobjs);

        }

        for (uint j = 1; j < nf; j++) {

          fld_node = mcall->in(first_ind+j);

          if (iklass != NULL) {

            st->print(", [");

            cifield = iklass->nonstatic_field_at(j);

            cifield->print_name_on(st);

            format_helper(regalloc, st, fld_node, ":", j, &scobjs);

          } else {

            format_helper(regalloc, st, fld_node, ", [", j, &scobjs);

          }

        }

      }

      st->print(" }");

    }

  }

  st->cr();

  if (caller() != NULL) caller()->format(regalloc, n, st);

}

void JVMState::dump_spec(outputStream *st) const {

  if (_method != NULL) {

    bool printed = false;

    if (!Verbose) {

      // The JVMS dumps make really, really long lines.

      // Take out the most boring parts, which are the package prefixes.

      char buf[500];

      stringStream namest(buf, sizeof(buf));

      _method->print_short_name(&namest);

      if (namest.count() < sizeof(buf)) {

        const char* name = namest.base();

        if (name[0] == ' ')  ++name;

        const char* endcn = strchr(name, ':');  // end of class name

        if (endcn == NULL)  endcn = strchr(name, '(');

        if (endcn == NULL)  endcn = name + strlen(name);

        while (endcn > name && endcn[-1] != '.' && endcn[-1] != '/')

          --endcn;