/*

 * Copyright 1997-2007 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"

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

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

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 control input 'dom' dominates (or equals) '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::detect_dominating_control(Node* dom, Node* sub) {

  if (dom == NULL)      return false;

  if (dom->is_Proj())   dom = dom->in(0);

  if (dom->is_Start())  return true; // anything inside the method

  if (dom->is_Root())   return true; // dom 'controls' a constant

  int cnt = 20;                      // detect cycle or too much effort

  while (sub != NULL) {              // walk 'sub' up the chain to 'dom'

    if (--cnt < 0)   return false;   // in a cycle or too complex

    if (sub == dom)  return true;

    if (sub->is_Start())  return false;

    if (sub->is_Root())   return false;

    Node* up = sub->in(0);

    if (sub == up && sub->is_Region()) {

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

        Node* in = sub->in(i);

        if (in != NULL && !in->is_top() && in != sub) {

          up = in; break;            // take any path on the way up to 'dom'

        }

      }

    }

    if (sub == up)  return false;    // some kind of tight cycle

    sub = up;

  }

  return false;

}

//---------------------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 detect_dominating_control(p2->in(0), a1->in(0));

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

    return detect_dominating_control(p1->in(0), a2->in(0));

  }

  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

  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 (ctrl != NULL &&

               detect_dominating_control(ctrl, st_alloc->in(0)))

        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)

      }

    }

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

// Also, asserts a cross-check of the type against the expected address type.

const TypePtr* MemNode::calculate_adr_type(const Type* t, const TypePtr* cross_check) {

  if (t == Type::TOP)  return NULL; // does not touch memory any more?

  #ifdef PRODUCT

  cross_check = NULL;

  #else

  if (!VerifyAliases || is_error_reported() || Node::in_dump())  cross_check = NULL;

  #endif

  const TypePtr* tp = t->isa_ptr();

  if (tp == NULL) {

    assert(cross_check == NULL || cross_check == TypePtr::BOTTOM, "expected memory type must be wide");

    return TypePtr::BOTTOM;           // touches lots of memory

  } else {

    #ifdef ASSERT

    // %%%% [phh] We don't check the alias index if cross_check is

    //            TypeRawPtr::BOTTOM.  Needs to be investigated.

    if (cross_check != NULL &&

        cross_check != TypePtr::BOTTOM &&

        cross_check != TypeRawPtr::BOTTOM) {

      // Recheck the alias index, to see if it has changed (due to a bug).

      Compile* C = Compile::current();

      assert(C->get_alias_index(cross_check) == C->get_alias_index(tp),

             "must stay in the original alias category");

      // The type of the address must be contained in the adr_type,

      // disregarding "null"-ness.

      // (We make an exception for TypeRawPtr::BOTTOM, which is a bit bucket.)

      const TypePtr* tp_notnull = tp->join(TypePtr::NOTNULL)->is_ptr();

      assert(cross_check->meet(tp_notnull) == cross_check,

             "real address must not escape from expected memory type");

    }

    #endif

    return tp;

  }

}

//------------------------adr_phi_is_loop_invariant----------------------------

// A helper function for Ideal_DU_postCCP to check if a Phi in a counted

// loop is loop invariant. Make a quick traversal of Phi and associated

// CastPP nodes, looking to see if they are a closed group within the loop.

bool MemNode::adr_phi_is_loop_invariant(Node* adr_phi, Node* cast) {

  // The idea is that the phi-nest must boil down to only CastPP nodes

  // with the same data. This implies that any path into the loop already

  // includes such a CastPP, and so the original cast, whatever its input,

  // must be covered by an equivalent cast, with an earlier control input.

  ResourceMark rm;

  // The loop entry input of the phi should be the unique dominating

  // node for every Phi/CastPP in the loop.

  Unique_Node_List closure;

  closure.push(adr_phi->in(LoopNode::EntryControl));

  // Add the phi node and the cast to the worklist.

  Unique_Node_List worklist;

  worklist.push(adr_phi);

  if( cast != NULL ){

    if( !cast->is_ConstraintCast() ) return false;

    worklist.push(cast);

  }

  // Begin recursive walk of phi nodes.

  while( worklist.size() ){

    // Take a node off the worklist

    Node *n = worklist.pop();

    if( !closure.member(n) ){

      // Add it to the closure.

      closure.push(n);

      // Make a sanity check to ensure we don't waste too much time here.

      if( closure.size() > 20) return false;

      // This node is OK if:

      //  - it is a cast of an identical value

      //  - or it is a phi node (then we add its inputs to the worklist)

      // Otherwise, the node is not OK, and we presume the cast is not invariant

      if( n->is_ConstraintCast() ){

        worklist.push(n->in(1));

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

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

          worklist.push(n->in(i));

        }

      } else {

        return false;

      }

    }

  }

  // Quit when the worklist is empty, and we've found no offending nodes.

  return true;

}

//------------------------------Ideal_DU_postCCP-------------------------------

// Find any cast-away of null-ness and keep its control.  Null cast-aways are

// going away in this pass and we need to make this memory op depend on the

// gating null check.

// I tried to leave the CastPP's in.  This makes the graph more accurate in

// some sense; we get to keep around the knowledge that an oop is not-null

// after some test.  Alas, the CastPP's interfere with GVN (some values are

// the regular oop, some are the CastPP of the oop, all merge at Phi's which

// cannot collapse, etc).  This cost us 10% on SpecJVM, even when I removed

// some of the more trivial cases in the optimizer.  Removing more useless

// Phi's started allowing Loads to illegally float above null checks.  I gave

// up on this approach.  CNC 10/20/2000

Node *MemNode::Ideal_DU_postCCP( PhaseCCP *ccp ) {

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

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

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

  Node *skipped_cast = NULL;

  // Need a null check?  Regular static accesses do not because they are

  // from constant addresses.  Array ops are gated by the range check (which

  // always includes a NULL check).  Just check field ops.

  if( !ctr ) {

    // Scan upwards for the highest location we can place this memory op.

    while( true ) {

      switch( adr->Opcode() ) {

      case Op_AddP:             // No change to NULL-ness, so peek thru AddP's

        adr = adr->in(AddPNode::Base);

        continue;

      case Op_CastPP:

        // If the CastPP is useless, just peek on through it.

        if( ccp->type(adr) == ccp->type(adr->in(1)) ) {

          // Remember the cast that we've peeked though. If we peek

          // through more than one, then we end up remembering the highest

          // one, that is, if in a loop, the one closest to the top.

          skipped_cast = adr;

          adr = adr->in(1);

          continue;

        }

        // CastPP is going away in this pass!  We need this memory op to be

        // control-dependent on the test that is guarding the CastPP.

        ccp->hash_delete(this);

        set_req(MemNode::Control, adr->in(0));

        ccp->hash_insert(this);

        return this;

      case Op_Phi:

        // Attempt to float above a Phi to some dominating point.

        if (adr->in(0) != NULL && adr->in(0)->is_CountedLoop()) {

          // If we've already peeked through a Cast (which could have set the

          // control), we can't float above a Phi, because the skipped Cast

          // may not be loop invariant.

          if (adr_phi_is_loop_invariant(adr, skipped_cast)) {

            adr = adr->in(1);

            continue;

          }

        }

        // Intentional fallthrough!

        // No obvious dominating point.  The mem op is pinned below the Phi

        // by the Phi itself.  If the Phi goes away (no true value is merged)

        // then the mem op can float, but not indefinitely.  It must be pinned

        // behind the controls leading to the Phi.

      case Op_CheckCastPP:

        // These usually stick around to change address type, however a

        // useless one can be elided and we still need to pick up a control edge

        if (adr->in(0) == NULL) {

          // This CheckCastPP node has NO control and is likely useless. But we

          // need check further up the ancestor chain for a control input to keep

          // the node in place. 4959717.

          skipped_cast = adr;

          adr = adr->in(1);

          continue;

        }

        ccp->hash_delete(this);