/*

 * Copyright (c) 2005, 2019, 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/shared/collectedHeap.inline.hpp"

#include "libadt/vectset.hpp"

#include "memory/universe.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"

#include "utilities/macros.hpp"

#if INCLUDE_G1GC

#include "gc/g1/g1ThreadLocalData.hpp"

#endif // INCLUDE_G1GC

#if INCLUDE_SHENANDOAHGC

#include "gc/shenandoah/c2/shenandoahBarrierSetC2.hpp"

#endif

//

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

    }

  }

}

void PhaseMacroExpand::eliminate_gc_barrier(Node* p2x) {

  BarrierSetC2 *bs = BarrierSet::barrier_set()->barrier_set_c2();

  bs->eliminate_gc_barrier(this, p2x);

}

// 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, Node* mem, 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()) {

    assert(ac->in(ArrayCopyNode::Src) != ac->in(ArrayCopyNode::Dest), "clone source equals destination");

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

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

  } 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* src_pos = ac->in(ArrayCopyNode::SrcPos);

      Node* dest_pos = ac->in(ArrayCopyNode::DestPos);

      const TypeInt* src_pos_t = _igvn.type(src_pos)->is_int();

      const TypeInt* dest_pos_t = _igvn.type(dest_pos)->is_int();

      Node* adr = NULL;

      const TypePtr* adr_type = NULL;

      if (src_pos_t->is_con() && dest_pos_t->is_con()) {

        intptr_t off = ((src_pos_t->get_con() - dest_pos_t->get_con()) << shift) + offset;

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

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

        adr_type = _igvn.type(base)->is_ptr()->add_offset(off);

        if (ac->in(ArrayCopyNode::Src) == ac->in(ArrayCopyNode::Dest)) {

          // Don't emit a new load from src if src == dst but try to get the value from memory instead

          return value_from_mem(ac->in(TypeFunc::Memory), ctl, ft, ftype, adr_type->isa_oopptr(), alloc);

        }

      } else {

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

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

        adr_type = _igvn.type(base)->is_ptr()->add_offset(Type::OffsetBot);

        if (ac->in(ArrayCopyNode::Src) == ac->in(ArrayCopyNode::Dest)) {

          // Non constant offset in the array: we can't statically

          // determine the value

          return NULL;

        }

      }

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

    }

  }

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

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

  }

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

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

  uint length = mem->req();

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

  // create a new Phi for the value

  PhiNode *phi = new PhiNode(mem->in(0), phi_type, NULL, mem->_idx, 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()) {

        Node* n = val->in(MemNode::ValueIn);

        BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();

        n = bs->step_over_gc_barrier(n);

        values.at_put(j, n);

      } 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() ||

               val->in(0)->Opcode() == Op_EncodeISOArray ||

               val->in(0)->Opcode() == Op_StrCompressedCopy, "sanity");

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

        return NULL;

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

        Node* res = make_arraycopy_load(val->as_ArrayCopy(), offset, val->in(0), val->in(TypeFunc::Memory), ft, phi_type, alloc);

        if (res == NULL) {

          return NULL;

        }

        values.at_put(j, res);

      } else {

#ifdef ASSERT

        val->dump();

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

#endif

        return NULL;  // unknown node on this path

      }