/*

 * Copyright 1997-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.

 *

 */

// Portions of code courtesy of Clifford Click

// Optimization - Graph Style

#include "incls/_precompiled.incl"

#include "incls/_memnode.cpp.incl"

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

  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 TypePtr *t_adr, PhaseGVN *phase) {

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

  if (tinst == NULL || !tinst->is_known_instance_field())

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

  uint instance_id = tinst->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 sentinals

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

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

        CallNode *call = proj_in->as_Call();

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

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

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

        }

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

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

      } else {

        assert(false, "unexpected projection");

      }

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

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

    }

  }

  return result;

}

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

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

  bool is_instance = (t_oop != NULL) && t_oop->is_known_instance_field();

  PhaseIterGVN *igvn = phase->is_IterGVN();

  Node *result = mchain;

  result = optimize_simple_memory_chain(result, t_adr, phase);

  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

  // TypeInstPtr::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 *tinst = tp->isa_oopptr();

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

      !(tinst &&

        tinst->klass()->is_java_lang_Object() &&

        tinst->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 tranformed 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;

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

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

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

  if( t_adr == Type::TOP )              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);

    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(), "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)

    return NULL;            // cannot unalias unless there are precise offsets

  const TypeOopPtr *addr_t = adr->bottom_type()->isa_oopptr();

  intptr_t size_in_bytes = memory_size();

  Node* mem = in(MemNode::Memory);   // start searching here...

  int cnt = 50;             // Cycle limiter

  for (;;) {                // While we can dance past unrelated stores...

    if (--cnt < 0)  break;  // Caught in cycle or a complicated dance?

    if (mem->is_Store()) {

      Node* st_adr = mem->in(MemNode::Address);

      intptr_t st_offset = 0;

      Node* st_base = AddPNode::Ideal_base_and_offset(st_adr, phase, st_offset);

      if (st_base == NULL)

        break;              // inscrutable pointer

      if (st_offset != offset && st_offset != Type::OffsetBot) {

        const int MAX_STORE = BytesPerLong;

        if (st_offset >= offset + size_in_bytes ||

            st_offset <= offset - MAX_STORE ||

            st_offset <= offset - mem->as_Store()->memory_size()) {

          // Success:  The offsets are provably independent.

          // (You may ask, why not just test st_offset != offset and be done?

          // The answer is that stores of different sizes can co-exist

          // in the same sequence of RawMem effects.  We sometimes initialize

          // a whole 'tile' of array elements with a single jint or jlong.)

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

          continue;           // (a) advance through independent store memory

        }

      }

      if (st_base != base &&

          detect_ptr_independence(base, alloc,

                                  st_base,

                                  AllocateNode::Ideal_allocation(st_base, phase),

                                  phase)) {

        // Success:  The bases are provably independent.

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

        continue;           // (a) advance through independent store memory

      }

      // (b) At this point, if the bases or offsets do not agree, we lose,

      // since we have not managed to prove 'this' and 'mem' independent.

      if (st_base == base && st_offset == offset) {

        return mem;         // let caller handle steps (c), (d)

      }

    } else if (mem->is_Proj() && mem->in(0)->is_Initialize()) {

      InitializeNode* st_init = mem->in(0)->as_Initialize();

      AllocateNode*  st_alloc = st_init->allocation();

      if (st_alloc == NULL)

        break;              // something degenerated

      bool known_identical = false;

      bool known_independent = false;

      if (alloc == st_alloc)

        known_identical = true;

      else if (alloc != NULL)

        known_independent = true;

      else if (all_controls_dominate(this, st_alloc))

        known_independent = true;

      if (known_independent) {

        // The bases are provably independent: Either they are

        // manifestly distinct allocations, or else the control

        // of this load dominates the store's allocation.

        int alias_idx = phase->C->get_alias_index(adr_type());

        if (alias_idx == Compile::AliasIdxRaw) {

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

        } else {

          mem = st_init->memory(alias_idx);

        }

        continue;           // (a) advance through independent store memory

      }

      // (b) at this point, if we are not looking at a store initializing

      // the same allocation we are loading from, we lose.

      if (known_identical) {

        // From caller, can_see_stored_value will consult find_captured_store.

        return mem;         // let caller handle steps (c), (d)

      }

    } else if (addr_t != NULL && addr_t->is_known_instance_field()) {

      // Can't use optimize_simple_memory_chain() since it needs PhaseGVN.

      if (mem->is_Proj() && mem->in(0)->is_Call()) {

        CallNode *call = mem->in(0)->as_Call();

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

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

          continue;         // (a) advance through independent call memory

        }

      } else if (mem->is_Proj() && mem->in(0)->is_MemBar()) {

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

        continue;           // (a) advance through independent MemBar memory

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

        int alias_idx = phase->C->get_alias_index(adr_type());

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

        continue;           // (a) advance through independent MergeMem memory

      }

    }

    // Unless there is an explicit 'continue', we must bail out here,

    // because 'mem' is an inscrutable memory state (e.g., a call).

    break;

  }

  return NULL;              // bail out

}

//----------------------calculate_adr_type-------------------------------------

// Helper function.  Notices when the given type of address hits top or bottom.