/*

 * Copyright 2005-2008 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.

 *

 */

#include "incls/_precompiled.incl"

#include "incls/_macro.cpp.incl"

//

// 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->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 = 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_iff(Node* region, Node* iff) {

  IfNode *opt_iff = transform_later(iff)->as_If();

  // Fast path taken; set region slot 2

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

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

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

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

  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.hash_delete(oldcall);

  _igvn.subsume_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");

  Node *shift = p2x->unique_out();

  Node *addp = shift->unique_out();

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

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

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

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

  }

}

// 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 sentinals

    } 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 {

      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 {

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

        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;

      }

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

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

      assert(atype != NULL, "address type must be oopptr");

      assert(C->get_alias_index(atype) == alias_idx &&

             atype->is_known_instance_field() && atype->offset() == offset &&

             atype->instance_id() == instance_id, "store is correct memory slice");

      done = true;

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

      // try to find a phi's unique input

      Node *unique_input = NULL;

      Node *top = C->top();

      for (uint i = 1; i < mem->req(); i++) {

        Node *n = scan_mem_chain(mem->in(i), alias_idx, offset, start_mem, alloc, &_igvn);

        if (n == NULL || n == top || n == mem) {

          continue;

        } else if (unique_input == NULL) {

          unique_input = n;

        } else if (unique_input != n) {

          unique_input = top;

          break;

        }

      }

      if (unique_input != NULL && unique_input != top) {

        mem = unique_input;

      } else {

        done = true;

      }

    } else {

      assert(false, "unexpected node");

    }

  }

  if (mem != NULL) {

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

      // hit a sentinel, return appropriate 0 value

      return _igvn.zerocon(ft);

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

      return mem->in(MemNode::ValueIn);

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

      // attempt to produce a Phi reflecting the values on the input paths of the Phi

      Node_Stack value_phis(a, 8);

      Node * phi = value_from_mem_phi(mem, ft, ftype, adr_t, alloc, &value_phis, ValueSearchLimit);

      if (phi != NULL) {

        return phi;

      } else {

        // Kill all new Phis

        while(value_phis.is_nonempty()) {

          Node* n = value_phis.node();

          _igvn.hash_delete(n);

          _igvn.subsume_node(n, C->top());

          value_phis.pop();

        }

      }

    }

  }

  // Something go wrong.

  return NULL;

}

// Check the possibility of scalar replacement.

bool PhaseMacroExpand::can_eliminate_allocation(AllocateNode *alloc, GrowableArray <SafePointNode *>& safepoints) {

  //  Scan the uses of the allocation to check for anything that would

  //  prevent us from eliminating it.

  NOT_PRODUCT( const char* fail_eliminate = NULL; )

  DEBUG_ONLY( Node* disq_node = NULL; )

  bool  can_eliminate = true;

  Node* res = alloc->result_cast();

  const TypeOopPtr* res_type = NULL;

  if (res == NULL) {

    // All users were eliminated.

  } else if (!res->is_CheckCastPP()) {

    alloc->_is_scalar_replaceable = false;  // don't try again

    NOT_PRODUCT(fail_eliminate = "Allocation does not have unique CheckCastPP";)

    can_eliminate = false;

  } else {

    res_type = _igvn.type(res)->isa_oopptr();

    if (res_type == NULL) {

      NOT_PRODUCT(fail_eliminate = "Neither instance or array allocation";)

      can_eliminate = false;

    } else if (res_type->isa_aryptr()) {

      int length = alloc->in(AllocateNode::ALength)->find_int_con(-1);

      if (length < 0) {

        NOT_PRODUCT(fail_eliminate = "Array's size is not constant";)

        can_eliminate = false;

      }

    }

  }

  if (can_eliminate && res != NULL) {

    for (DUIterator_Fast jmax, j = res->fast_outs(jmax);

                               j < jmax && can_eliminate; j++) {

      Node* use = res->fast_out(j);

      if (use->is_AddP()) {

        const TypePtr* addp_type = _igvn.type(use)->is_ptr();

        int offset = addp_type->offset();

        if (offset == Type::OffsetTop || offset == Type::OffsetBot) {

          NOT_PRODUCT(fail_eliminate = "Undefined field referrence";)

          can_eliminate = false;

          break;

        }

        for (DUIterator_Fast kmax, k = use->fast_outs(kmax);

                                   k < kmax && can_eliminate; k++) {

          Node* n = use->fast_out(k);

          if (!n->is_Store() && n->Opcode() != Op_CastP2X) {

            DEBUG_ONLY(disq_node = n;)

            if (n->is_Load() || n->is_LoadStore()) {

              NOT_PRODUCT(fail_eliminate = "Field load";)

            } else {

              NOT_PRODUCT(fail_eliminate = "Not store field referrence";)

            }

            can_eliminate = false;

          }

        }

      } else if (use->is_SafePoint()) {

        SafePointNode* sfpt = use->as_SafePoint();

        if (sfpt->is_Call() && sfpt->as_Call()->has_non_debug_use(res)) {

          // Object is passed as argument.

          DEBUG_ONLY(disq_node = use;)

          NOT_PRODUCT(fail_eliminate = "Object is passed as argument";)

          can_eliminate = false;

        }

        Node* sfptMem = sfpt->memory();

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

          DEBUG_ONLY(disq_node = use;)

          NOT_PRODUCT(fail_eliminate = "NULL or TOP memory";)

          can_eliminate = false;

        } else {

          safepoints.append_if_missing(sfpt);

        }

      } else if (use->Opcode() != Op_CastP2X) { // CastP2X is used by card mark

        if (use->is_Phi()) {

          if (use->outcnt() == 1 && use->unique_out()->Opcode() == Op_Return) {

            NOT_PRODUCT(fail_eliminate = "Object is return value";)

          } else {