/*

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

#include "libadt/vectset.hpp"

#include "opto/addnode.hpp"

#include "opto/callnode.hpp"

#include "opto/cfgnode.hpp"

#include "opto/compile.hpp"

#include "opto/connode.hpp"

#include "opto/locknode.hpp"

#include "opto/loopnode.hpp"

#include "opto/macro.hpp"

#include "opto/memnode.hpp"

#include "opto/node.hpp"

#include "opto/phaseX.hpp"

#include "opto/rootnode.hpp"

#include "opto/runtime.hpp"

#include "opto/subnode.hpp"

#include "opto/type.hpp"

#include "runtime/sharedRuntime.hpp"

//

// Replace any references to "oldref" in inputs to "use" with "newref".

// Returns the number of replacements made.

//

int PhaseMacroExpand::replace_input(Node *use, Node *oldref, Node *newref) {

  int nreplacements = 0;

  uint req = use->req();

  for (uint j = 0; j < use->len(); j++) {

    Node *uin = use->in(j);

    if (uin == oldref) {

      if (j < req)

        use->set_req(j, newref);

      else

        use->set_prec(j, newref);

      nreplacements++;

    } else if (j >= req && uin == NULL) {

      break;

    }

  }

  return nreplacements;

}

void PhaseMacroExpand::copy_call_debug_info(CallNode *oldcall, CallNode * newcall) {

  // Copy debug information and adjust JVMState information

  uint old_dbg_start = oldcall->tf()->domain()->cnt();

  uint new_dbg_start = newcall->tf()->domain()->cnt();

  int jvms_adj  = new_dbg_start - old_dbg_start;

  assert (new_dbg_start == newcall->req(), "argument count mismatch");

  Dict* sosn_map = new Dict(cmpkey,hashkey);

  for (uint i = old_dbg_start; i < oldcall->req(); i++) {

    Node* old_in = oldcall->in(i);

    // Clone old SafePointScalarObjectNodes, adjusting their field contents.

    if (old_in != NULL && old_in->is_SafePointScalarObject()) {

      SafePointScalarObjectNode* old_sosn = old_in->as_SafePointScalarObject();

      uint old_unique = C->unique();

      Node* new_in = old_sosn->clone(jvms_adj, sosn_map);

      if (old_unique != C->unique()) {

        new_in->set_req(0, newcall->in(0)); // reset control edge

        new_in = transform_later(new_in); // Register new node.

      }

      old_in = new_in;

    }

    newcall->add_req(old_in);

  }

  newcall->set_jvms(oldcall->jvms());

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

    jvms->set_map(newcall);

    jvms->set_locoff(jvms->locoff()+jvms_adj);

    jvms->set_stkoff(jvms->stkoff()+jvms_adj);

    jvms->set_monoff(jvms->monoff()+jvms_adj);

    jvms->set_scloff(jvms->scloff()+jvms_adj);

    jvms->set_endoff(jvms->endoff()+jvms_adj);

  }

}

Node* PhaseMacroExpand::opt_bits_test(Node* ctrl, Node* region, int edge, Node* word, int mask, int bits, bool return_fast_path) {

  Node* cmp;

  if (mask != 0) {

    Node* and_node = transform_later(new (C, 3) AndXNode(word, MakeConX(mask)));

    cmp = transform_later(new (C, 3) CmpXNode(and_node, MakeConX(bits)));

  } else {

    cmp = word;

  }

  Node* bol = transform_later(new (C, 2) BoolNode(cmp, BoolTest::ne));

  IfNode* iff = new (C, 2) IfNode( ctrl, bol, PROB_MIN, COUNT_UNKNOWN );

  transform_later(iff);

  // Fast path taken.

  Node *fast_taken = transform_later( new (C, 1) IfFalseNode(iff) );

  // Fast path not-taken, i.e. slow path

  Node *slow_taken = transform_later( new (C, 1) IfTrueNode(iff) );

  if (return_fast_path) {

    region->init_req(edge, slow_taken); // Capture slow-control

    return fast_taken;

  } else {

    region->init_req(edge, fast_taken); // Capture fast-control

    return slow_taken;

  }

}

//--------------------copy_predefined_input_for_runtime_call--------------------

void PhaseMacroExpand::copy_predefined_input_for_runtime_call(Node * ctrl, CallNode* oldcall, CallNode* call) {

  // Set fixed predefined input arguments

  call->init_req( TypeFunc::Control, ctrl );

  call->init_req( TypeFunc::I_O    , oldcall->in( TypeFunc::I_O) );

  call->init_req( TypeFunc::Memory , oldcall->in( TypeFunc::Memory ) ); // ?????

  call->init_req( TypeFunc::ReturnAdr, oldcall->in( TypeFunc::ReturnAdr ) );

  call->init_req( TypeFunc::FramePtr, oldcall->in( TypeFunc::FramePtr ) );

}

//------------------------------make_slow_call---------------------------------

CallNode* PhaseMacroExpand::make_slow_call(CallNode *oldcall, const TypeFunc* slow_call_type, address slow_call, const char* leaf_name, Node* slow_path, Node* parm0, Node* parm1) {

  // Slow-path call

  int size = slow_call_type->domain()->cnt();

 CallNode *call = leaf_name

   ? (CallNode*)new (C, size) CallLeafNode      ( slow_call_type, slow_call, leaf_name, TypeRawPtr::BOTTOM )

   : (CallNode*)new (C, size) CallStaticJavaNode( slow_call_type, slow_call, OptoRuntime::stub_name(slow_call), oldcall->jvms()->bci(), TypeRawPtr::BOTTOM );

  // Slow path call has no side-effects, uses few values

  copy_predefined_input_for_runtime_call(slow_path, oldcall, call );

  if (parm0 != NULL)  call->init_req(TypeFunc::Parms+0, parm0);

  if (parm1 != NULL)  call->init_req(TypeFunc::Parms+1, parm1);

  copy_call_debug_info(oldcall, call);

  call->set_cnt(PROB_UNLIKELY_MAG(4));  // Same effect as RC_UNCOMMON.

  _igvn.replace_node(oldcall, call);

  transform_later(call);

  return call;

}

void PhaseMacroExpand::extract_call_projections(CallNode *call) {

  _fallthroughproj = NULL;

  _fallthroughcatchproj = NULL;

  _ioproj_fallthrough = NULL;

  _ioproj_catchall = NULL;

  _catchallcatchproj = NULL;

  _memproj_fallthrough = NULL;

  _memproj_catchall = NULL;

  _resproj = NULL;

  for (DUIterator_Fast imax, i = call->fast_outs(imax); i < imax; i++) {

    ProjNode *pn = call->fast_out(i)->as_Proj();

    switch (pn->_con) {

      case TypeFunc::Control:

      {

        // For Control (fallthrough) and I_O (catch_all_index) we have CatchProj -> Catch -> Proj

        _fallthroughproj = pn;

        DUIterator_Fast jmax, j = pn->fast_outs(jmax);

        const Node *cn = pn->fast_out(j);

        if (cn->is_Catch()) {

          ProjNode *cpn = NULL;

          for (DUIterator_Fast kmax, k = cn->fast_outs(kmax); k < kmax; k++) {

            cpn = cn->fast_out(k)->as_Proj();

            assert(cpn->is_CatchProj(), "must be a CatchProjNode");

            if (cpn->_con == CatchProjNode::fall_through_index)

              _fallthroughcatchproj = cpn;

            else {

              assert(cpn->_con == CatchProjNode::catch_all_index, "must be correct index.");

              _catchallcatchproj = cpn;

            }

          }

        }

        break;

      }

      case TypeFunc::I_O:

        if (pn->_is_io_use)

          _ioproj_catchall = pn;

        else

          _ioproj_fallthrough = pn;

        break;

      case TypeFunc::Memory:

        if (pn->_is_io_use)

          _memproj_catchall = pn;

        else

          _memproj_fallthrough = pn;

        break;

      case TypeFunc::Parms:

        _resproj = pn;

        break;

      default:

        assert(false, "unexpected projection from allocation node.");

    }

  }

}

// Eliminate a card mark sequence.  p2x is a ConvP2XNode

void PhaseMacroExpand::eliminate_card_mark(Node* p2x) {

  assert(p2x->Opcode() == Op_CastP2X, "ConvP2XNode required");

  if (!UseG1GC) {

    // vanilla/CMS post barrier

    Node *shift = p2x->unique_out();

    Node *addp = shift->unique_out();

    for (DUIterator_Last jmin, j = addp->last_outs(jmin); j >= jmin; --j) {

      Node *mem = addp->last_out(j);

      if (UseCondCardMark && mem->is_Load()) {

        assert(mem->Opcode() == Op_LoadB, "unexpected code shape");

        // The load is checking if the card has been written so

        // replace it with zero to fold the test.

        _igvn.replace_node(mem, intcon(0));

        continue;

      }

      assert(mem->is_Store(), "store required");

      _igvn.replace_node(mem, mem->in(MemNode::Memory));

    }

  } else {

    // G1 pre/post barriers

    assert(p2x->outcnt() == 2, "expects 2 users: Xor and URShift nodes");

    // It could be only one user, URShift node, in Object.clone() instrinsic

    // but the new allocation is passed to arraycopy stub and it could not

    // be scalar replaced. So we don't check the case.

    // Remove G1 post barrier.

    // Search for CastP2X->Xor->URShift->Cmp path which

    // checks if the store done to a different from the value's region.

    // And replace Cmp with #0 (false) to collapse G1 post barrier.

    Node* xorx = NULL;

    for (DUIterator_Fast imax, i = p2x->fast_outs(imax); i < imax; i++) {

      Node* u = p2x->fast_out(i);

      if (u->Opcode() == Op_XorX) {

        xorx = u;

        break;

      }

    }

    assert(xorx != NULL, "missing G1 post barrier");

    Node* shift = xorx->unique_out();

    Node* cmpx = shift->unique_out();

    assert(cmpx->is_Cmp() && cmpx->unique_out()->is_Bool() &&

    cmpx->unique_out()->as_Bool()->_test._test == BoolTest::ne,

    "missing region check in G1 post barrier");

    _igvn.replace_node(cmpx, makecon(TypeInt::CC_EQ));

    // Remove G1 pre barrier.

    // Search "if (marking != 0)" check and set it to "false".

    Node* this_region = p2x->in(0);

    assert(this_region != NULL, "");

    // There is no G1 pre barrier if previous stored value is NULL

    // (for example, after initialization).

    if (this_region->is_Region() && this_region->req() == 3) {

      int ind = 1;

      if (!this_region->in(ind)->is_IfFalse()) {

        ind = 2;

      }

      if (this_region->in(ind)->is_IfFalse()) {

        Node* bol = this_region->in(ind)->in(0)->in(1);

        assert(bol->is_Bool(), "");

        cmpx = bol->in(1);

        if (bol->as_Bool()->_test._test == BoolTest::ne &&

            cmpx->is_Cmp() && cmpx->in(2) == intcon(0) &&

            cmpx->in(1)->is_Load()) {

          Node* adr = cmpx->in(1)->as_Load()->in(MemNode::Address);

          const int marking_offset = in_bytes(JavaThread::satb_mark_queue_offset() +

                                              PtrQueue::byte_offset_of_active());

          if (adr->is_AddP() && adr->in(AddPNode::Base) == top() &&

              adr->in(AddPNode::Address)->Opcode() == Op_ThreadLocal &&

              adr->in(AddPNode::Offset) == MakeConX(marking_offset)) {

            _igvn.replace_node(cmpx, makecon(TypeInt::CC_EQ));

          }

        }

      }

    }

    // Now CastP2X can be removed since it is used only on dead path

    // which currently still alive until igvn optimize it.

    assert(p2x->unique_out()->Opcode() == Op_URShiftX, "");

    _igvn.replace_node(p2x, top());

  }

}

// Search for a memory operation for the specified memory slice.

static Node *scan_mem_chain(Node *mem, int alias_idx, int offset, Node *start_mem, Node *alloc, PhaseGVN *phase) {

  Node *orig_mem = mem;

  Node *alloc_mem = alloc->in(TypeFunc::Memory);

  const TypeOopPtr *tinst = phase->C->get_adr_type(alias_idx)->isa_oopptr();

  while (true) {

    if (mem == alloc_mem || mem == start_mem ) {

      return mem;  // hit one of our sentinels

    } else if (mem->is_MergeMem()) {

      mem = mem->as_MergeMem()->memory_at(alias_idx);

    } else if (mem->is_Proj() && mem->as_Proj()->_con == TypeFunc::Memory) {

      Node *in = mem->in(0);

      // we can safely skip over safepoints, calls, locks and membars because we

      // already know that the object is safe to eliminate.

      if (in->is_Initialize() && in->as_Initialize()->allocation() == alloc) {

        return in;

      } else if (in->is_Call()) {

        CallNode *call = in->as_Call();

        if (!call->may_modify(tinst, phase)) {

          mem = call->in(TypeFunc::Memory);

        }

        mem = in->in(TypeFunc::Memory);

      } else if (in->is_MemBar()) {

        mem = in->in(TypeFunc::Memory);

      } else {

        assert(false, "unexpected projection");

      }

    } else if (mem->is_Store()) {

      const TypePtr* atype = mem->as_Store()->adr_type();

      int adr_idx = Compile::current()->get_alias_index(atype);

      if (adr_idx == alias_idx) {

        assert(atype->isa_oopptr(), "address type must be oopptr");

        int adr_offset = atype->offset();

        uint adr_iid = atype->is_oopptr()->instance_id();

        // Array elements references have the same alias_idx

        // but different offset and different instance_id.

        if (adr_offset == offset && adr_iid == alloc->_idx)

          return mem;

      } else {

        assert(adr_idx == Compile::AliasIdxRaw, "address must match or be raw");

      }

      mem = mem->in(MemNode::Memory);

    } else if (mem->is_ClearArray()) {

      if (!ClearArrayNode::step_through(&mem, alloc->_idx, phase)) {

        // Can not bypass initialization of the instance

        // we are looking.

        debug_only(intptr_t offset;)

        assert(alloc == AllocateNode::Ideal_allocation(mem->in(3), phase, offset), "sanity");

        InitializeNode* init = alloc->as_Allocate()->initialization();

        // We are looking for stored value, return Initialize node

        // or memory edge from Allocate node.

        if (init != NULL)

          return init;

        else

          return alloc->in(TypeFunc::Memory); // It will produce zero value (see callers).

      }

      // Otherwise skip it (the call updated 'mem' value).

    } else if (mem->Opcode() == Op_SCMemProj) {

      assert(mem->in(0)->is_LoadStore(), "sanity");

      const TypePtr* atype = mem->in(0)->in(MemNode::Address)->bottom_type()->is_ptr();

      int adr_idx = Compile::current()->get_alias_index(atype);

      if (adr_idx == alias_idx) {

        assert(false, "Object is not scalar replaceable if a LoadStore node access its field");

        return NULL;

      }

      mem = mem->in(0)->in(MemNode::Memory);

    } else {

      return mem;

    }

    assert(mem != orig_mem, "dead memory loop");

  }

}

//

// Given a Memory Phi, compute a value Phi containing the values from stores

// on the input paths.

// Note: this function is recursive, its depth is limied by the "level" argument

// Returns the computed Phi, or NULL if it cannot compute it.

Node *PhaseMacroExpand::value_from_mem_phi(Node *mem, BasicType ft, const Type *phi_type, const TypeOopPtr *adr_t, Node *alloc, Node_Stack *value_phis, int level) {

  assert(mem->is_Phi(), "sanity");

  int alias_idx = C->get_alias_index(adr_t);

  int offset = adr_t->offset();

  int instance_id = adr_t->instance_id();

  // Check if an appropriate value phi already exists.

  Node* region = mem->in(0);

  for (DUIterator_Fast kmax, k = region->fast_outs(kmax); k < kmax; k++) {

    Node* phi = region->fast_out(k);

    if (phi->is_Phi() && phi != mem &&

        phi->as_Phi()->is_same_inst_field(phi_type, instance_id, alias_idx, offset)) {

      return phi;

    }

  }

  // Check if an appropriate new value phi already exists.

  Node* new_phi = NULL;

  uint size = value_phis->size();

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

    if ( mem->_idx == value_phis->index_at(i) ) {

      return value_phis->node_at(i);

    }

  }

  if (level <= 0) {

    return NULL; // Give up: phi tree too deep

  }

  Node *start_mem = C->start()->proj_out(TypeFunc::Memory);

  Node *alloc_mem = alloc->in(TypeFunc::Memory);

  uint length = mem->req();

  GrowableArray <Node *> values(length, length, NULL);

  // create a new Phi for the value

  PhiNode *phi = new (C, length) PhiNode(mem->in(0), phi_type, NULL, instance_id, alias_idx, offset);

  transform_later(phi);

  value_phis->push(phi, mem->_idx);

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

    Node *in = mem->in(j);

    if (in == NULL || in->is_top()) {

      values.at_put(j, in);

    } else  {

      Node *val = scan_mem_chain(in, alias_idx, offset, start_mem, alloc, &_igvn);

      if (val == start_mem || val == alloc_mem) {

        // hit a sentinel, return appropriate 0 value

        values.at_put(j, _igvn.zerocon(ft));

        continue;

      }

      if (val->is_Initialize()) {

        val = val->as_Initialize()->find_captured_store(offset, type2aelembytes(ft), &_igvn);

      }

      if (val == NULL) {

        return NULL;  // can't find a value on this path

      }

      if (val == mem) {

        values.at_put(j, mem);

      } else if (val->is_Store()) {

        values.at_put(j, val->in(MemNode::ValueIn));

      } else if(val->is_Proj() && val->in(0) == alloc) {

        values.at_put(j, _igvn.zerocon(ft));

      } else if (val->is_Phi()) {

        val = value_from_mem_phi(val, ft, phi_type, adr_t, alloc, value_phis, level-1);

        if (val == NULL) {

          return NULL;

        }

        values.at_put(j, val);

      } else if (val->Opcode() == Op_SCMemProj) {

        assert(val->in(0)->is_LoadStore(), "sanity");

        assert(false, "Object is not scalar replaceable if a LoadStore node access its field");

        return NULL;

      } else {

#ifdef ASSERT

        val->dump();

        assert(false, "unknown node on this path");

#endif

        return NULL;  // unknown node on this path

      }

    }

  }

  // Set Phi's inputs

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

    if (values.at(j) == mem) {

      phi->init_req(j, phi);

    } else {

      phi->init_req(j, values.at(j));

    }

  }

  return phi;

}

// Search the last value stored into the object's field.

Node *PhaseMacroExpand::value_from_mem(Node *sfpt_mem, BasicType ft, const Type *ftype, const TypeOopPtr *adr_t, Node *alloc) {

  assert(adr_t->is_known_instance_field(), "instance required");

  int instance_id = adr_t->instance_id();

  assert((uint)instance_id == alloc->_idx, "wrong allocation");

  int alias_idx = C->get_alias_index(adr_t);

  int offset = adr_t->offset();

  Node *start_mem = C->start()->proj_out(TypeFunc::Memory);

  Node *alloc_ctrl = alloc->in(TypeFunc::Control);

  Node *alloc_mem = alloc->in(TypeFunc::Memory);

  Arena *a = Thread::current()->resource_area();

  VectorSet visited(a);

  bool done = sfpt_mem == alloc_mem;

  Node *mem = sfpt_mem;

  while (!done) {

    if (visited.test_set(mem->_idx)) {

      return NULL;  // found a loop, give up

    }

    mem = scan_mem_chain(mem, alias_idx, offset, start_mem, alloc, &_igvn);

    if (mem == start_mem || mem == alloc_mem) {

      done = true;  // hit a sentinel, return appropriate 0 value

    } else if (mem->is_Initialize()) {

      mem = mem->as_Initialize()->find_captured_store(offset, type2aelembytes(ft), &_igvn);

      if (mem == NULL) {

        done = true; // Something go wrong.

      } else if (mem->is_Store()) {

        const TypePtr* atype = mem->as_Store()->adr_type();

        assert(C->get_alias_index(atype) == Compile::AliasIdxRaw, "store is correct memory slice");

        done = true;