/*

 * Copyright (c) 2001, 2015, 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 "compiler/compileLog.hpp"

#include "gc_implementation/g1/g1SATBCardTableModRefBS.hpp"

#include "gc_implementation/g1/heapRegion.hpp"

#include "gc_interface/collectedHeap.hpp"

#include "memory/barrierSet.hpp"

#include "memory/cardTableModRefBS.hpp"

#include "opto/addnode.hpp"

#include "opto/castnode.hpp"

#include "opto/convertnode.hpp"

#include "opto/graphKit.hpp"

#include "opto/idealKit.hpp"

#include "opto/intrinsicnode.hpp"

#include "opto/locknode.hpp"

#include "opto/machnode.hpp"

#include "opto/opaquenode.hpp"

#include "opto/parse.hpp"

#include "opto/rootnode.hpp"

#include "opto/runtime.hpp"

#include "runtime/deoptimization.hpp"

#include "runtime/sharedRuntime.hpp"

//----------------------------GraphKit-----------------------------------------

// Main utility constructor.

GraphKit::GraphKit(JVMState* jvms)

  : Phase(Phase::Parser),

    _env(C->env()),

    _gvn(*C->initial_gvn())

{

  _exceptions = jvms->map()->next_exception();

  if (_exceptions != NULL)  jvms->map()->set_next_exception(NULL);

  set_jvms(jvms);

}

// Private constructor for parser.

GraphKit::GraphKit()

  : Phase(Phase::Parser),

    _env(C->env()),

    _gvn(*C->initial_gvn())

{

  _exceptions = NULL;

  set_map(NULL);

  debug_only(_sp = -99);

  debug_only(set_bci(-99));

}

//---------------------------clean_stack---------------------------------------

// Clear away rubbish from the stack area of the JVM state.

// This destroys any arguments that may be waiting on the stack.

void GraphKit::clean_stack(int from_sp) {

  SafePointNode* map      = this->map();

  JVMState*      jvms     = this->jvms();

  int            stk_size = jvms->stk_size();

  int            stkoff   = jvms->stkoff();

  Node*          top      = this->top();

  for (int i = from_sp; i < stk_size; i++) {

    if (map->in(stkoff + i) != top) {

      map->set_req(stkoff + i, top);

    }

  }

}

//--------------------------------sync_jvms-----------------------------------

// Make sure our current jvms agrees with our parse state.

JVMState* GraphKit::sync_jvms() const {

  JVMState* jvms = this->jvms();

  jvms->set_bci(bci());       // Record the new bci in the JVMState

  jvms->set_sp(sp());         // Record the new sp in the JVMState

  assert(jvms_in_sync(), "jvms is now in sync");

  return jvms;

}

//--------------------------------sync_jvms_for_reexecute---------------------

// Make sure our current jvms agrees with our parse state.  This version

// uses the reexecute_sp for reexecuting bytecodes.

JVMState* GraphKit::sync_jvms_for_reexecute() {

  JVMState* jvms = this->jvms();

  jvms->set_bci(bci());          // Record the new bci in the JVMState

  jvms->set_sp(reexecute_sp());  // Record the new sp in the JVMState

  return jvms;

}

#ifdef ASSERT

bool GraphKit::jvms_in_sync() const {

  Parse* parse = is_Parse();

  if (parse == NULL) {

    if (bci() !=      jvms()->bci())          return false;

    if (sp()  != (int)jvms()->sp())           return false;

    return true;

  }

  if (jvms()->method() != parse->method())    return false;

  if (jvms()->bci()    != parse->bci())       return false;

  int jvms_sp = jvms()->sp();

  if (jvms_sp          != parse->sp())        return false;

  int jvms_depth = jvms()->depth();

  if (jvms_depth       != parse->depth())     return false;

  return true;

}

// Local helper checks for special internal merge points

// used to accumulate and merge exception states.

// They are marked by the region's in(0) edge being the map itself.

// Such merge points must never "escape" into the parser at large,

// until they have been handed to gvn.transform.

static bool is_hidden_merge(Node* reg) {

  if (reg == NULL)  return false;

  if (reg->is_Phi()) {

    reg = reg->in(0);

    if (reg == NULL)  return false;

  }

  return reg->is_Region() && reg->in(0) != NULL && reg->in(0)->is_Root();

}

void GraphKit::verify_map() const {

  if (map() == NULL)  return;  // null map is OK

  assert(map()->req() <= jvms()->endoff(), "no extra garbage on map");

  assert(!map()->has_exceptions(),    "call add_exception_states_from 1st");

  assert(!is_hidden_merge(control()), "call use_exception_state, not set_map");

}

void GraphKit::verify_exception_state(SafePointNode* ex_map) {

  assert(ex_map->next_exception() == NULL, "not already part of a chain");

  assert(has_saved_ex_oop(ex_map), "every exception state has an ex_oop");

}

#endif

//---------------------------stop_and_kill_map---------------------------------

// Set _map to NULL, signalling a stop to further bytecode execution.

// First smash the current map's control to a constant, to mark it dead.

void GraphKit::stop_and_kill_map() {

  SafePointNode* dead_map = stop();

  if (dead_map != NULL) {

    dead_map->disconnect_inputs(NULL, C); // Mark the map as killed.

    assert(dead_map->is_killed(), "must be so marked");

  }

}

//--------------------------------stopped--------------------------------------

// Tell if _map is NULL, or control is top.

bool GraphKit::stopped() {

  if (map() == NULL)           return true;

  else if (control() == top()) return true;

  else                         return false;

}

//-----------------------------has_ex_handler----------------------------------

// Tell if this method or any caller method has exception handlers.

bool GraphKit::has_ex_handler() {

  for (JVMState* jvmsp = jvms(); jvmsp != NULL; jvmsp = jvmsp->caller()) {

    if (jvmsp->has_method() && jvmsp->method()->has_exception_handlers()) {

      return true;

    }

  }

  return false;

}

//------------------------------save_ex_oop------------------------------------

// Save an exception without blowing stack contents or other JVM state.

void GraphKit::set_saved_ex_oop(SafePointNode* ex_map, Node* ex_oop) {

  assert(!has_saved_ex_oop(ex_map), "clear ex-oop before setting again");

  ex_map->add_req(ex_oop);

  debug_only(verify_exception_state(ex_map));

}

inline static Node* common_saved_ex_oop(SafePointNode* ex_map, bool clear_it) {

  assert(GraphKit::has_saved_ex_oop(ex_map), "ex_oop must be there");

  Node* ex_oop = ex_map->in(ex_map->req()-1);

  if (clear_it)  ex_map->del_req(ex_map->req()-1);

  return ex_oop;

}

//-----------------------------saved_ex_oop------------------------------------

// Recover a saved exception from its map.

Node* GraphKit::saved_ex_oop(SafePointNode* ex_map) {

  return common_saved_ex_oop(ex_map, false);

}

//--------------------------clear_saved_ex_oop---------------------------------

// Erase a previously saved exception from its map.

Node* GraphKit::clear_saved_ex_oop(SafePointNode* ex_map) {

  return common_saved_ex_oop(ex_map, true);

}

#ifdef ASSERT

//---------------------------has_saved_ex_oop----------------------------------

// Erase a previously saved exception from its map.

bool GraphKit::has_saved_ex_oop(SafePointNode* ex_map) {

  return ex_map->req() == ex_map->jvms()->endoff()+1;

}

#endif

//-------------------------make_exception_state--------------------------------

// Turn the current JVM state into an exception state, appending the ex_oop.

SafePointNode* GraphKit::make_exception_state(Node* ex_oop) {

  sync_jvms();

  SafePointNode* ex_map = stop();  // do not manipulate this map any more

  set_saved_ex_oop(ex_map, ex_oop);

  return ex_map;

}

//--------------------------add_exception_state--------------------------------

// Add an exception to my list of exceptions.

void GraphKit::add_exception_state(SafePointNode* ex_map) {

  if (ex_map == NULL || ex_map->control() == top()) {

    return;

  }

#ifdef ASSERT

  verify_exception_state(ex_map);

  if (has_exceptions()) {

    assert(ex_map->jvms()->same_calls_as(_exceptions->jvms()), "all collected exceptions must come from the same place");

  }

#endif

  // If there is already an exception of exactly this type, merge with it.

  // In particular, null-checks and other low-level exceptions common up here.

  Node*       ex_oop  = saved_ex_oop(ex_map);

  const Type* ex_type = _gvn.type(ex_oop);

  if (ex_oop == top()) {

    // No action needed.

    return;

  }

  assert(ex_type->isa_instptr(), "exception must be an instance");

  for (SafePointNode* e2 = _exceptions; e2 != NULL; e2 = e2->next_exception()) {

    const Type* ex_type2 = _gvn.type(saved_ex_oop(e2));

    // We check sp also because call bytecodes can generate exceptions

    // both before and after arguments are popped!

    if (ex_type2 == ex_type

        && e2->_jvms->sp() == ex_map->_jvms->sp()) {

      combine_exception_states(ex_map, e2);

      return;

    }

  }

  // No pre-existing exception of the same type.  Chain it on the list.

  push_exception_state(ex_map);

}

//-----------------------add_exception_states_from-----------------------------

void GraphKit::add_exception_states_from(JVMState* jvms) {

  SafePointNode* ex_map = jvms->map()->next_exception();

  if (ex_map != NULL) {

    jvms->map()->set_next_exception(NULL);

    for (SafePointNode* next_map; ex_map != NULL; ex_map = next_map) {

      next_map = ex_map->next_exception();

      ex_map->set_next_exception(NULL);

      add_exception_state(ex_map);

    }

  }

}

//-----------------------transfer_exceptions_into_jvms-------------------------

JVMState* GraphKit::transfer_exceptions_into_jvms() {

  if (map() == NULL) {

    // We need a JVMS to carry the exceptions, but the map has gone away.

    // Create a scratch JVMS, cloned from any of the exception states...

    if (has_exceptions()) {

      _map = _exceptions;

      _map = clone_map();

      _map->set_next_exception(NULL);

      clear_saved_ex_oop(_map);

      debug_only(verify_map());

    } else {

      // ...or created from scratch

      JVMState* jvms = new (C) JVMState(_method, NULL);

      jvms->set_bci(_bci);

      jvms->set_sp(_sp);

      jvms->set_map(new SafePointNode(TypeFunc::Parms, jvms));

      set_jvms(jvms);

      for (uint i = 0; i < map()->req(); i++)  map()->init_req(i, top());

      set_all_memory(top());

      while (map()->req() < jvms->endoff())  map()->add_req(top());

    }

    // (This is a kludge, in case you didn't notice.)

    set_control(top());

  }

  JVMState* jvms = sync_jvms();

  assert(!jvms->map()->has_exceptions(), "no exceptions on this map yet");

  jvms->map()->set_next_exception(_exceptions);

  _exceptions = NULL;   // done with this set of exceptions

  return jvms;

}

static inline void add_n_reqs(Node* dstphi, Node* srcphi) {

  assert(is_hidden_merge(dstphi), "must be a special merge node");

  assert(is_hidden_merge(srcphi), "must be a special merge node");

  uint limit = srcphi->req();

  for (uint i = PhiNode::Input; i < limit; i++) {

    dstphi->add_req(srcphi->in(i));

  }

}

static inline void add_one_req(Node* dstphi, Node* src) {

  assert(is_hidden_merge(dstphi), "must be a special merge node");

  assert(!is_hidden_merge(src), "must not be a special merge node");

  dstphi->add_req(src);

}

//-----------------------combine_exception_states------------------------------

// This helper function combines exception states by building phis on a

// specially marked state-merging region.  These regions and phis are

// untransformed, and can build up gradually.  The region is marked by

// having a control input of its exception map, rather than NULL.  Such

// regions do not appear except in this function, and in use_exception_state.

void GraphKit::combine_exception_states(SafePointNode* ex_map, SafePointNode* phi_map) {

  if (failing())  return;  // dying anyway...

  JVMState* ex_jvms = ex_map->_jvms;

  assert(ex_jvms->same_calls_as(phi_map->_jvms), "consistent call chains");

  assert(ex_jvms->stkoff() == phi_map->_jvms->stkoff(), "matching locals");

  assert(ex_jvms->sp() == phi_map->_jvms->sp(), "matching stack sizes");

  assert(ex_jvms->monoff() == phi_map->_jvms->monoff(), "matching JVMS");

  assert(ex_jvms->scloff() == phi_map->_jvms->scloff(), "matching scalar replaced objects");

  assert(ex_map->req() == phi_map->req(), "matching maps");

  uint tos = ex_jvms->stkoff() + ex_jvms->sp();

  Node*         hidden_merge_mark = root();

  Node*         region  = phi_map->control();

  MergeMemNode* phi_mem = phi_map->merged_memory();

  MergeMemNode* ex_mem  = ex_map->merged_memory();

  if (region->in(0) != hidden_merge_mark) {

    // The control input is not (yet) a specially-marked region in phi_map.

    // Make it so, and build some phis.

    region = new RegionNode(2);

    _gvn.set_type(region, Type::CONTROL);

    region->set_req(0, hidden_merge_mark);  // marks an internal ex-state

    region->init_req(1, phi_map->control());

    phi_map->set_control(region);

    Node* io_phi = PhiNode::make(region, phi_map->i_o(), Type::ABIO);

    record_for_igvn(io_phi);

    _gvn.set_type(io_phi, Type::ABIO);

    phi_map->set_i_o(io_phi);

    for (MergeMemStream mms(phi_mem); mms.next_non_empty(); ) {

      Node* m = mms.memory();

      Node* m_phi = PhiNode::make(region, m, Type::MEMORY, mms.adr_type(C));

      record_for_igvn(m_phi);

      _gvn.set_type(m_phi, Type::MEMORY);

      mms.set_memory(m_phi);

    }

  }

  // Either or both of phi_map and ex_map might already be converted into phis.

  Node* ex_control = ex_map->control();

  // if there is special marking on ex_map also, we add multiple edges from src

  bool add_multiple = (ex_control->in(0) == hidden_merge_mark);

  // how wide was the destination phi_map, originally?

  uint orig_width = region->req();

  if (add_multiple) {

    add_n_reqs(region, ex_control);

    add_n_reqs(phi_map->i_o(), ex_map->i_o());

  } else {

    // ex_map has no merges, so we just add single edges everywhere

    add_one_req(region, ex_control);

    add_one_req(phi_map->i_o(), ex_map->i_o());

  }

  for (MergeMemStream mms(phi_mem, ex_mem); mms.next_non_empty2(); ) {

    if (mms.is_empty()) {

      // get a copy of the base memory, and patch some inputs into it

      const TypePtr* adr_type = mms.adr_type(C);

      Node* phi = mms.force_memory()->as_Phi()->slice_memory(adr_type);

      assert(phi->as_Phi()->region() == mms.base_memory()->in(0), "");

      mms.set_memory(phi);

      // Prepare to append interesting stuff onto the newly sliced phi:

      while (phi->req() > orig_width)  phi->del_req(phi->req()-1);

    }

    // Append stuff from ex_map:

    if (add_multiple) {

      add_n_reqs(mms.memory(), mms.memory2());

    } else {

      add_one_req(mms.memory(), mms.memory2());

    }

  }

  uint limit = ex_map->req();

  for (uint i = TypeFunc::Parms; i < limit; i++) {

    // Skip everything in the JVMS after tos.  (The ex_oop follows.)

    if (i == tos)  i = ex_jvms->monoff();

    Node* src = ex_map->in(i);

    Node* dst = phi_map->in(i);

    if (src != dst) {

      PhiNode* phi;

      if (dst->in(0) != region) {

        dst = phi = PhiNode::make(region, dst, _gvn.type(dst));

        record_for_igvn(phi);

        _gvn.set_type(phi, phi->type());

        phi_map->set_req(i, dst);

        // Prepare to append interesting stuff onto the new phi:

        while (dst->req() > orig_width)  dst->del_req(dst->req()-1);

      } else {

        assert(dst->is_Phi(), "nobody else uses a hidden region");

        phi = dst->as_Phi();

      }

      if (add_multiple && src->in(0) == ex_control) {

        // Both are phis.

        add_n_reqs(dst, src);

      } else {

        while (dst->req() < region->req())  add_one_req(dst, src);

      }

      const Type* srctype = _gvn.type(src);

      if (phi->type() != srctype) {

        const Type* dsttype = phi->type()->meet_speculative(srctype);

        if (phi->type() != dsttype) {

          phi->set_type(dsttype);

          _gvn.set_type(phi, dsttype);

        }

      }

    }

  }

  phi_map->merge_replaced_nodes_with(ex_map);

}

//--------------------------use_exception_state--------------------------------

Node* GraphKit::use_exception_state(SafePointNode* phi_map) {

  if (failing()) { stop(); return top(); }

  Node* region = phi_map->control();

  Node* hidden_merge_mark = root();

  assert(phi_map->jvms()->map() == phi_map, "sanity: 1-1 relation");

  Node* ex_oop = clear_saved_ex_oop(phi_map);

  if (region->in(0) == hidden_merge_mark) {

    // Special marking for internal ex-states.  Process the phis now.

    region->set_req(0, region);  // now it's an ordinary region

    set_jvms(phi_map->jvms());   // ...so now we can use it as a map

    // Note: Setting the jvms also sets the bci and sp.

    set_control(_gvn.transform(region));

    uint tos = jvms()->stkoff() + sp();

    for (uint i = 1; i < tos; i++) {

      Node* x = phi_map->in(i);

      if (x->in(0) == region) {

        assert(x->is_Phi(), "expected a special phi");

        phi_map->set_req(i, _gvn.transform(x));

      }

    }

    for (MergeMemStream mms(merged_memory()); mms.next_non_empty(); ) {

      Node* x = mms.memory();

      if (x->in(0) == region) {

        assert(x->is_Phi(), "nobody else uses a hidden region");

        mms.set_memory(_gvn.transform(x));

      }

    }

    if (ex_oop->in(0) == region) {

      assert(ex_oop->is_Phi(), "expected a special phi");

      ex_oop = _gvn.transform(ex_oop);

    }

  } else {

    set_jvms(phi_map->jvms());

  }

  assert(!is_hidden_merge(phi_map->control()), "hidden ex. states cleared");

  assert(!is_hidden_merge(phi_map->i_o()), "hidden ex. states cleared");

  return ex_oop;

}

//---------------------------------java_bc-------------------------------------

Bytecodes::Code GraphKit::java_bc() const {

  ciMethod* method = this->method();

  int       bci    = this->bci();

  if (method != NULL && bci != InvocationEntryBci)

    return method->java_code_at_bci(bci);

  else

    return Bytecodes::_illegal;

}

void GraphKit::uncommon_trap_if_should_post_on_exceptions(Deoptimization::DeoptReason reason,

                                                          bool must_throw) {

    // if the exception capability is set, then we will generate code

    // to check the JavaThread.should_post_on_exceptions flag to see

    // if we actually need to report exception events (for this

    // thread).  If we don't need to report exception events, we will

    // take the normal fast path provided by add_exception_events.  If

    // exception event reporting is enabled for this thread, we will

    // take the uncommon_trap in the BuildCutout below.

    // first must access the should_post_on_exceptions_flag in this thread's JavaThread

    Node* jthread = _gvn.transform(new ThreadLocalNode());

    Node* adr = basic_plus_adr(top(), jthread, in_bytes(JavaThread::should_post_on_exceptions_flag_offset()));

    Node* should_post_flag = make_load(control(), adr, TypeInt::INT, T_INT, Compile::AliasIdxRaw, MemNode::unordered);

    // Test the should_post_on_exceptions_flag vs. 0

    Node* chk = _gvn.transform( new CmpINode(should_post_flag, intcon(0)) );

    Node* tst = _gvn.transform( new BoolNode(chk, BoolTest::eq) );

    // Branch to slow_path if should_post_on_exceptions_flag was true

    { BuildCutout unless(this, tst, PROB_MAX);

      // Do not try anything fancy if we're notifying the VM on every throw.

      // Cf. case Bytecodes::_athrow in parse2.cpp.

      uncommon_trap(reason, Deoptimization::Action_none,

                    (ciKlass*)NULL, (char*)NULL, must_throw);

    }

}

//------------------------------builtin_throw----------------------------------

void GraphKit::builtin_throw(Deoptimization::DeoptReason reason, Node* arg) {

  bool must_throw = true;