/*

 * Copyright (c) 1997, 2014, 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 "classfile/systemDictionary.hpp"

#include "compiler/compileLog.hpp"

#include "memory/allocation.inline.hpp"

#include "oops/objArrayKlass.hpp"

#include "opto/addnode.hpp"

#include "opto/cfgnode.hpp"

#include "opto/compile.hpp"

#include "opto/connode.hpp"

#include "opto/convertnode.hpp"

#include "opto/loopnode.hpp"

#include "opto/machnode.hpp"

#include "opto/matcher.hpp"

#include "opto/memnode.hpp"

#include "opto/mulnode.hpp"

#include "opto/narrowptrnode.hpp"

#include "opto/phaseX.hpp"

#include "opto/regmask.hpp"

// Portions of code courtesy of Clifford Click

// Optimization - Graph Style

static Node *step_through_mergemem(PhaseGVN *phase, MergeMemNode *mmem,  const TypePtr *tp, const TypePtr *adr_check, outputStream *st);

//=============================================================================

uint MemNode::size_of() const { return sizeof(*this); }

const TypePtr *MemNode::adr_type() const {

  Node* adr = in(Address);

  if (adr == NULL)  return NULL; // node is dead

  const TypePtr* cross_check = NULL;

  DEBUG_ONLY(cross_check = _adr_type);

  return calculate_adr_type(adr->bottom_type(), cross_check);

}

#ifndef PRODUCT

void MemNode::dump_spec(outputStream *st) const {

  if (in(Address) == NULL)  return; // node is dead

#ifndef ASSERT

  // fake the missing field

  const TypePtr* _adr_type = NULL;

  if (in(Address) != NULL)

    _adr_type = in(Address)->bottom_type()->isa_ptr();

#endif

  dump_adr_type(this, _adr_type, st);

  Compile* C = Compile::current();

  if( C->alias_type(_adr_type)->is_volatile() )

    st->print(" Volatile!");

}

void MemNode::dump_adr_type(const Node* mem, const TypePtr* adr_type, outputStream *st) {

  st->print(" @");

  if (adr_type == NULL) {

    st->print("NULL");

  } else {

    adr_type->dump_on(st);

    Compile* C = Compile::current();

    Compile::AliasType* atp = NULL;

    if (C->have_alias_type(adr_type))  atp = C->alias_type(adr_type);

    if (atp == NULL)

      st->print(", idx=?\?;");

    else if (atp->index() == Compile::AliasIdxBot)

      st->print(", idx=Bot;");

    else if (atp->index() == Compile::AliasIdxTop)

      st->print(", idx=Top;");

    else if (atp->index() == Compile::AliasIdxRaw)

      st->print(", idx=Raw;");

    else {

      ciField* field = atp->field();

      if (field) {

        st->print(", name=");

        field->print_name_on(st);

      }

      st->print(", idx=%d;", atp->index());

    }

  }

}

extern void print_alias_types();

#endif

Node *MemNode::optimize_simple_memory_chain(Node *mchain, const TypeOopPtr *t_oop, Node *load, PhaseGVN *phase) {

  assert((t_oop != NULL), "sanity");

  bool is_instance = t_oop->is_known_instance_field();

  bool is_boxed_value_load = t_oop->is_ptr_to_boxed_value() &&

                             (load != NULL) && load->is_Load() &&

                             (phase->is_IterGVN() != NULL);

  if (!(is_instance || is_boxed_value_load))

    return mchain;  // don't try to optimize non-instance types

  uint instance_id = t_oop->instance_id();

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

  Node *prev = NULL;

  Node *result = mchain;

  while (prev != result) {

    prev = result;

    if (result == start_mem)

      break;  // hit one of our sentinels

    // skip over a call which does not affect this memory slice

    if (result->is_Proj() && result->as_Proj()->_con == TypeFunc::Memory) {

      Node *proj_in = result->in(0);

      if (proj_in->is_Allocate() && proj_in->_idx == instance_id) {

        break;  // hit one of our sentinels

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

        CallNode *call = proj_in->as_Call();

        if (!call->may_modify(t_oop, phase)) { // returns false for instances

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

        }

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

        AllocateNode* alloc = proj_in->as_Initialize()->allocation();

        // Stop if this is the initialization for the object instance which

        // which contains this memory slice, otherwise skip over it.

        if ((alloc == NULL) || (alloc->_idx == instance_id)) {

          break;

        }

        if (is_instance) {

          result = proj_in->in(TypeFunc::Memory);

        } else if (is_boxed_value_load) {

          Node* klass = alloc->in(AllocateNode::KlassNode);

          const TypeKlassPtr* tklass = phase->type(klass)->is_klassptr();

          if (tklass->klass_is_exact() && !tklass->klass()->equals(t_oop->klass())) {

            result = proj_in->in(TypeFunc::Memory); // not related allocation

          }

        }

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

        result = proj_in->in(TypeFunc::Memory);

      } else {

        assert(false, "unexpected projection");

      }

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

      if (!is_instance || !ClearArrayNode::step_through(&result, instance_id, phase)) {

        // Can not bypass initialization of the instance

        // we are looking for.

        break;

      }

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

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

      result = step_through_mergemem(phase, result->as_MergeMem(), t_oop, NULL, tty);

    }

  }

  return result;

}

Node *MemNode::optimize_memory_chain(Node *mchain, const TypePtr *t_adr, Node *load, PhaseGVN *phase) {

  const TypeOopPtr* t_oop = t_adr->isa_oopptr();

  if (t_oop == NULL)

    return mchain;  // don't try to optimize non-oop types

  Node* result = optimize_simple_memory_chain(mchain, t_oop, load, phase);

  bool is_instance = t_oop->is_known_instance_field();

  PhaseIterGVN *igvn = phase->is_IterGVN();

  if (is_instance && igvn != NULL  && result->is_Phi()) {

    PhiNode *mphi = result->as_Phi();

    assert(mphi->bottom_type() == Type::MEMORY, "memory phi required");

    const TypePtr *t = mphi->adr_type();

    if (t == TypePtr::BOTTOM || t == TypeRawPtr::BOTTOM ||

        t->isa_oopptr() && !t->is_oopptr()->is_known_instance() &&

        t->is_oopptr()->cast_to_exactness(true)

         ->is_oopptr()->cast_to_ptr_type(t_oop->ptr())

         ->is_oopptr()->cast_to_instance_id(t_oop->instance_id()) == t_oop) {

      // clone the Phi with our address type

      result = mphi->split_out_instance(t_adr, igvn);

    } else {

      assert(phase->C->get_alias_index(t) == phase->C->get_alias_index(t_adr), "correct memory chain");

    }

  }

  return result;

}

static Node *step_through_mergemem(PhaseGVN *phase, MergeMemNode *mmem,  const TypePtr *tp, const TypePtr *adr_check, outputStream *st) {

  uint alias_idx = phase->C->get_alias_index(tp);

  Node *mem = mmem;

#ifdef ASSERT

  {

    // Check that current type is consistent with the alias index used during graph construction

    assert(alias_idx >= Compile::AliasIdxRaw, "must not be a bad alias_idx");

    bool consistent =  adr_check == NULL || adr_check->empty() ||

                       phase->C->must_alias(adr_check, alias_idx );

    // Sometimes dead array references collapse to a[-1], a[-2], or a[-3]

    if( !consistent && adr_check != NULL && !adr_check->empty() &&

               tp->isa_aryptr() &&        tp->offset() == Type::OffsetBot &&

        adr_check->isa_aryptr() && adr_check->offset() != Type::OffsetBot &&

        ( adr_check->offset() == arrayOopDesc::length_offset_in_bytes() ||

          adr_check->offset() == oopDesc::klass_offset_in_bytes() ||

          adr_check->offset() == oopDesc::mark_offset_in_bytes() ) ) {

      // don't assert if it is dead code.

      consistent = true;

    }

    if( !consistent ) {

      st->print("alias_idx==%d, adr_check==", alias_idx);

      if( adr_check == NULL ) {

        st->print("NULL");

      } else {

        adr_check->dump();

      }

      st->cr();

      print_alias_types();

      assert(consistent, "adr_check must match alias idx");

    }

  }

#endif

  // TypeOopPtr::NOTNULL+any is an OOP with unknown offset - generally

  // means an array I have not precisely typed yet.  Do not do any

  // alias stuff with it any time soon.

  const TypeOopPtr *toop = tp->isa_oopptr();

  if( tp->base() != Type::AnyPtr &&

      !(toop &&

        toop->klass() != NULL &&

        toop->klass()->is_java_lang_Object() &&

        toop->offset() == Type::OffsetBot) ) {

    // compress paths and change unreachable cycles to TOP

    // If not, we can update the input infinitely along a MergeMem cycle

    // Equivalent code in PhiNode::Ideal

    Node* m  = phase->transform(mmem);

    // If transformed to a MergeMem, get the desired slice

    // Otherwise the returned node represents memory for every slice

    mem = (m->is_MergeMem())? m->as_MergeMem()->memory_at(alias_idx) : m;

    // Update input if it is progress over what we have now

  }

  return mem;

}

//--------------------------Ideal_common---------------------------------------

// Look for degenerate control and memory inputs.  Bypass MergeMem inputs.

// Unhook non-raw memories from complete (macro-expanded) initializations.

Node *MemNode::Ideal_common(PhaseGVN *phase, bool can_reshape) {

  // If our control input is a dead region, kill all below the region

  Node *ctl = in(MemNode::Control);

  if (ctl && remove_dead_region(phase, can_reshape))

    return this;

  ctl = in(MemNode::Control);

  // Don't bother trying to transform a dead node

  if (ctl && ctl->is_top())  return NodeSentinel;

  PhaseIterGVN *igvn = phase->is_IterGVN();

  // Wait if control on the worklist.

  if (ctl && can_reshape && igvn != NULL) {

    Node* bol = NULL;

    Node* cmp = NULL;

    if (ctl->in(0)->is_If()) {

      assert(ctl->is_IfTrue() || ctl->is_IfFalse(), "sanity");

      bol = ctl->in(0)->in(1);

      if (bol->is_Bool())

        cmp = ctl->in(0)->in(1)->in(1);

    }

    if (igvn->_worklist.member(ctl) ||

        (bol != NULL && igvn->_worklist.member(bol)) ||

        (cmp != NULL && igvn->_worklist.member(cmp)) ) {

      // This control path may be dead.

      // Delay this memory node transformation until the control is processed.

      phase->is_IterGVN()->_worklist.push(this);

      return NodeSentinel; // caller will return NULL

    }

  }

  // Ignore if memory is dead, or self-loop

  Node *mem = in(MemNode::Memory);

  if (phase->type( mem ) == Type::TOP) return NodeSentinel; // caller will return NULL

  assert(mem != this, "dead loop in MemNode::Ideal");

  if (can_reshape && igvn != NULL && igvn->_worklist.member(mem)) {

    // This memory slice may be dead.

    // Delay this mem node transformation until the memory is processed.

    phase->is_IterGVN()->_worklist.push(this);

    return NodeSentinel; // caller will return NULL

  }

  Node *address = in(MemNode::Address);

  const Type *t_adr = phase->type(address);

  if (t_adr == Type::TOP)              return NodeSentinel; // caller will return NULL

  if (can_reshape && igvn != NULL &&

      (igvn->_worklist.member(address) ||

       igvn->_worklist.size() > 0 && (t_adr != adr_type())) ) {

    // The address's base and type may change when the address is processed.

    // Delay this mem node transformation until the address is processed.

    phase->is_IterGVN()->_worklist.push(this);

    return NodeSentinel; // caller will return NULL

  }

  // Do NOT remove or optimize the next lines: ensure a new alias index

  // is allocated for an oop pointer type before Escape Analysis.

  // Note: C++ will not remove it since the call has side effect.

  if (t_adr->isa_oopptr()) {

    int alias_idx = phase->C->get_alias_index(t_adr->is_ptr());

  }

  Node* base = NULL;

  if (address->is_AddP()) {

    base = address->in(AddPNode::Base);

  }

  if (base != NULL && phase->type(base)->higher_equal(TypePtr::NULL_PTR) &&

      !t_adr->isa_rawptr()) {

    // Note: raw address has TOP base and top->higher_equal(TypePtr::NULL_PTR) is true.

    // Skip this node optimization if its address has TOP base.

    return NodeSentinel; // caller will return NULL

  }

  // Avoid independent memory operations

  Node* old_mem = mem;

  // The code which unhooks non-raw memories from complete (macro-expanded)

  // initializations was removed. After macro-expansion all stores catched

  // by Initialize node became raw stores and there is no information

  // which memory slices they modify. So it is unsafe to move any memory

  // operation above these stores. Also in most cases hooked non-raw memories

  // were already unhooked by using information from detect_ptr_independence()

  // and find_previous_store().

  if (mem->is_MergeMem()) {

    MergeMemNode* mmem = mem->as_MergeMem();

    const TypePtr *tp = t_adr->is_ptr();

    mem = step_through_mergemem(phase, mmem, tp, adr_type(), tty);

  }

  if (mem != old_mem) {

    set_req(MemNode::Memory, mem);

    if (can_reshape && old_mem->outcnt() == 0) {

        igvn->_worklist.push(old_mem);

    }

    if (phase->type( mem ) == Type::TOP) return NodeSentinel;

    return this;

  }

  // let the subclass continue analyzing...

  return NULL;

}

// Helper function for proving some simple control dominations.

// Attempt to prove that all control inputs of 'dom' dominate 'sub'.

// Already assumes that 'dom' is available at 'sub', and that 'sub'

// is not a constant (dominated by the method's StartNode).

// Used by MemNode::find_previous_store to prove that the

// control input of a memory operation predates (dominates)

// an allocation it wants to look past.

bool MemNode::all_controls_dominate(Node* dom, Node* sub) {

  if (dom == NULL || dom->is_top() || sub == NULL || sub->is_top())

    return false; // Conservative answer for dead code

  // Check 'dom'. Skip Proj and CatchProj nodes.

  dom = dom->find_exact_control(dom);

  if (dom == NULL || dom->is_top())

    return false; // Conservative answer for dead code

  if (dom == sub) {

    // For the case when, for example, 'sub' is Initialize and the original

    // 'dom' is Proj node of the 'sub'.

    return false;

  }

  if (dom->is_Con() || dom->is_Start() || dom->is_Root() || dom == sub)

    return true;

  // 'dom' dominates 'sub' if its control edge and control edges

  // of all its inputs dominate or equal to sub's control edge.

  // Currently 'sub' is either Allocate, Initialize or Start nodes.

  // Or Region for the check in LoadNode::Ideal();

  // 'sub' should have sub->in(0) != NULL.

  assert(sub->is_Allocate() || sub->is_Initialize() || sub->is_Start() ||

         sub->is_Region() || sub->is_Call(), "expecting only these nodes");

  // Get control edge of 'sub'.

  Node* orig_sub = sub;

  sub = sub->find_exact_control(sub->in(0));

  if (sub == NULL || sub->is_top())

    return false; // Conservative answer for dead code

  assert(sub->is_CFG(), "expecting control");

  if (sub == dom)

    return true;

  if (sub->is_Start() || sub->is_Root())

    return false;

  {

    // Check all control edges of 'dom'.

    ResourceMark rm;

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

    Node_List nlist(arena);

    Unique_Node_List dom_list(arena);

    dom_list.push(dom);

    bool only_dominating_controls = false;

    for (uint next = 0; next < dom_list.size(); next++) {

      Node* n = dom_list.at(next);

      if (n == orig_sub)

        return false; // One of dom's inputs dominated by sub.

      if (!n->is_CFG() && n->pinned()) {

        // Check only own control edge for pinned non-control nodes.

        n = n->find_exact_control(n->in(0));

        if (n == NULL || n->is_top())

          return false; // Conservative answer for dead code

        assert(n->is_CFG(), "expecting control");

        dom_list.push(n);

      } else if (n->is_Con() || n->is_Start() || n->is_Root()) {

        only_dominating_controls = true;

      } else if (n->is_CFG()) {

        if (n->dominates(sub, nlist))

          only_dominating_controls = true;

        else

          return false;

      } else {

        // First, own control edge.

        Node* m = n->find_exact_control(n->in(0));

        if (m != NULL) {

          if (m->is_top())

            return false; // Conservative answer for dead code

          dom_list.push(m);

        }

        // Now, the rest of edges.

        uint cnt = n->req();

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

          m = n->find_exact_control(n->in(i));

          if (m == NULL || m->is_top())

            continue;

          dom_list.push(m);

        }

      }

    }

    return only_dominating_controls;

  }

}

//---------------------detect_ptr_independence---------------------------------

// Used by MemNode::find_previous_store to prove that two base

// pointers are never equal.

// The pointers are accompanied by their associated allocations,

// if any, which have been previously discovered by the caller.

bool MemNode::detect_ptr_independence(Node* p1, AllocateNode* a1,

                                      Node* p2, AllocateNode* a2,

                                      PhaseTransform* phase) {

  // Attempt to prove that these two pointers cannot be aliased.

  // They may both manifestly be allocations, and they should differ.

  // Or, if they are not both allocations, they can be distinct constants.

  // Otherwise, one is an allocation and the other a pre-existing value.

  if (a1 == NULL && a2 == NULL) {           // neither an allocation

    return (p1 != p2) && p1->is_Con() && p2->is_Con();

  } else if (a1 != NULL && a2 != NULL) {    // both allocations

    return (a1 != a2);

  } else if (a1 != NULL) {                  // one allocation a1

    // (Note:  p2->is_Con implies p2->in(0)->is_Root, which dominates.)

    return all_controls_dominate(p2, a1);

  } else { //(a2 != NULL)                   // one allocation a2

    return all_controls_dominate(p1, a2);

  }

  return false;

}

// The logic for reordering loads and stores uses four steps:

// (a) Walk carefully past stores and initializations which we

//     can prove are independent of this load.

// (b) Observe that the next memory state makes an exact match

//     with self (load or store), and locate the relevant store.

// (c) Ensure that, if we were to wire self directly to the store,

//     the optimizer would fold it up somehow.

// (d) Do the rewiring, and return, depending on some other part of

//     the optimizer to fold up the load.

// This routine handles steps (a) and (b).  Steps (c) and (d) are

// specific to loads and stores, so they are handled by the callers.

// (Currently, only LoadNode::Ideal has steps (c), (d).  More later.)

//

Node* MemNode::find_previous_store(PhaseTransform* phase) {

  Node*         ctrl   = in(MemNode::Control);

  Node*         adr    = in(MemNode::Address);

  intptr_t      offset = 0;

  Node*         base   = AddPNode::Ideal_base_and_offset(adr, phase, offset);

  AllocateNode* alloc  = AllocateNode::Ideal_allocation(base, phase);

  if (offset == Type::OffsetBot)