/*

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

#include "opto/callnode.hpp"

#include "opto/castnode.hpp"

#include "opto/cfgnode.hpp"

#include "opto/compile.hpp"

#include "opto/convertnode.hpp"

#include "opto/graphKit.hpp"

#include "opto/locknode.hpp"

#include "opto/loopnode.hpp"

#include "opto/macro.hpp"

#include "opto/memnode.hpp"

#include "opto/narrowptrnode.hpp"

#include "opto/node.hpp"

#include "opto/opaquenode.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");

  // SafePointScalarObject node could be referenced several times in debug info.

  // Use Dict to record cloned nodes.

  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(sosn_map);

      if (old_unique != C->unique()) { // New node?

        new_in->set_req(0, C->root()); // reset control edge

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

      }

      old_in = new_in;

    }

    newcall->add_req(old_in);

  }

  // JVMS may be shared so clone it before we modify it

  newcall->set_jvms(oldcall->jvms() != NULL ? oldcall->jvms()->clone_deep(C) : NULL);

  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 AndXNode(word, MakeConX(mask)));

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

  } else {

    cmp = word;

  }

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

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

  transform_later(iff);

  // Fast path taken.

  Node *fast_taken = transform_later(new IfFalseNode(iff));

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

  Node *slow_taken = transform_later(new 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, Node* parm2) {

  // Slow-path call

 CallNode *call = leaf_name

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

   : (CallNode*)new 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);

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

  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 1 or 2 users: Xor and URShift nodes");

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

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

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

    // An other case of only one user (Xor) is when the value check for NULL

    // in G1 post barrier is folded after CCP so the code which used URShift

    // is removed.

    // Take Region node before eliminating post barrier since it also

    // eliminates CastP2X node when it has only one user.

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

    assert(this_region != NULL, "");

    // 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 = p2x->find_out_with(Op_XorX);

    if (xorx != NULL) {

      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".

      // 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() +

                                                SATBMarkQueue::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));

            }

          }

        }

      }

    } else {

      assert(!GraphKit::use_ReduceInitialCardMarks(), "can only happen with card marking");

      // This is a G1 post barrier emitted by the Object.clone() intrinsic.

      // Search for the CastP2X->URShiftX->AddP->LoadB->Cmp path which checks if the card

      // is marked as young_gen and replace the Cmp with 0 (false) to collapse the barrier.

      Node* shift = p2x->find_out_with(Op_URShiftX);

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

      Node* addp = shift->unique_out();

      Node* load = addp->find_out_with(Op_LoadB);

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

      Node* cmpx = load->unique_out();

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

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

             "missing card value check in G1 post barrier");

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

      // There is no G1 pre barrier in this case

    }

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

    // which currently still alive until igvn optimize it.

    assert(p2x->outcnt() == 0 || 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)) {

          assert(call->is_ArrayCopy(), "ArrayCopy is the only call node that doesn't make allocation escape");

          if (call->as_ArrayCopy()->modifies(offset, offset, phase, false)) {

            return in;

          }

        }

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

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

        ArrayCopyNode* ac = NULL;

        if (ArrayCopyNode::may_modify(tinst, in->as_MemBar(), phase, ac)) {

          assert(ac != NULL && ac->is_clonebasic(), "Only basic clone is a non escaping clone");

          return ac;

        }

        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 = phase->C->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) {

      mem = mem->in(0);

      Node* adr = NULL;

      if (mem->is_LoadStore()) {

        adr = mem->in(MemNode::Address);

      } else {

        assert(mem->Opcode() == Op_EncodeISOArray ||

               mem->Opcode() == Op_StrCompressedCopy, "sanity");

        adr = mem->in(3); // Destination array

      }

      const TypePtr* atype = adr->bottom_type()->is_ptr();

      int adr_idx = phase->C->get_alias_index(atype);

      if (adr_idx == alias_idx) {

        DEBUG_ONLY(mem->dump();)

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

        return NULL;

      }

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

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

      Node* adr = mem->in(3); // Destination array

      const TypePtr* atype = adr->bottom_type()->is_ptr();

      int adr_idx = phase->C->get_alias_index(atype);

      if (adr_idx == alias_idx) {

        DEBUG_ONLY(mem->dump();)

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

        return NULL;

      }

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

    } else {

      return mem;

    }

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

  }

}

// Generate loads from source of the arraycopy for fields of

// destination needed at a deoptimization point

Node* PhaseMacroExpand::make_arraycopy_load(ArrayCopyNode* ac, intptr_t offset, Node* ctl, BasicType ft, const Type *ftype, AllocateNode *alloc) {

  BasicType bt = ft;

  const Type *type = ftype;

  if (ft == T_NARROWOOP) {

    bt = T_OBJECT;

    type = ftype->make_oopptr();

  }

  Node* res = NULL;

  if (ac->is_clonebasic()) {

    Node* base = ac->in(ArrayCopyNode::Src)->in(AddPNode::Base);

    Node* adr = _igvn.transform(new AddPNode(base, base, MakeConX(offset)));

    const TypePtr* adr_type = _igvn.type(base)->is_ptr()->add_offset(offset);

    Node* m = ac->in(TypeFunc::Memory);

    res = LoadNode::make(_igvn, ctl, m, adr, adr_type, type, bt, MemNode::unordered, LoadNode::Pinned);

  } else {

    if (ac->modifies(offset, offset, &_igvn, true)) {

      assert(ac->in(ArrayCopyNode::Dest) == alloc->result_cast(), "arraycopy destination should be allocation's result");

      uint shift  = exact_log2(type2aelembytes(bt));

      Node* diff = _igvn.transform(new SubINode(ac->in(ArrayCopyNode::SrcPos), ac->in(ArrayCopyNode::DestPos)));

#ifdef _LP64

      diff = _igvn.transform(new ConvI2LNode(diff));

#endif

      diff = _igvn.transform(new LShiftXNode(diff, intcon(shift)));

      Node* off = _igvn.transform(new AddXNode(MakeConX(offset), diff));

      Node* base = ac->in(ArrayCopyNode::Src);

      Node* adr = _igvn.transform(new AddPNode(base, base, off));

      const TypePtr* adr_type = _igvn.type(base)->is_ptr()->add_offset(offset);

      Node* m = ac->in(TypeFunc::Memory);

      res = LoadNode::make(_igvn, ctl, m, adr, adr_type, type, bt, MemNode::unordered, LoadNode::Pinned);

    }

  }

  if (res != NULL) {

    res = _igvn.transform(res);

    if (ftype->isa_narrowoop()) {

      // PhaseMacroExpand::scalar_replacement adds DecodeN nodes

      res = _igvn.transform(new EncodePNode(res, ftype));

    }

    return res;

  }

  return NULL;

}

//

// 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 limited 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, AllocateNode *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, (int)mem->_idx, instance_id, alias_idx, offset)) {

      return phi;

    }

  }

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

  Node* new_phi = value_phis->find(mem->_idx);

  if (new_phi != NULL)

    return new_phi;

  if (level <= 0) {