/*

 * 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

class MultiNode;

class PhaseCCP;

class PhaseTransform;

//------------------------------MemNode----------------------------------------

// Load or Store, possibly throwing a NULL pointer exception

class MemNode : public Node {

protected:

#ifdef ASSERT

  const TypePtr* _adr_type;     // What kind of memory is being addressed?

#endif

  virtual uint size_of() const; // Size is bigger (ASSERT only)

public:

  enum { Control,               // When is it safe to do this load?

         Memory,                // Chunk of memory is being loaded from

         Address,               // Actually address, derived from base

         ValueIn,               // Value to store

         OopStore               // Preceeding oop store, only in StoreCM

  };

protected:

  MemNode( Node *c0, Node *c1, Node *c2, const TypePtr* at )

    : Node(c0,c1,c2   ) {

    init_class_id(Class_Mem);

    debug_only(_adr_type=at; adr_type();)

  }

  MemNode( Node *c0, Node *c1, Node *c2, const TypePtr* at, Node *c3 )

    : Node(c0,c1,c2,c3) {

    init_class_id(Class_Mem);

    debug_only(_adr_type=at; adr_type();)

  }

  MemNode( Node *c0, Node *c1, Node *c2, const TypePtr* at, Node *c3, Node *c4)

    : Node(c0,c1,c2,c3,c4) {

    init_class_id(Class_Mem);

    debug_only(_adr_type=at; adr_type();)

  }

public:

  // Helpers for the optimizer.  Documented in memnode.cpp.

  static bool detect_ptr_independence(Node* p1, AllocateNode* a1,

                                      Node* p2, AllocateNode* a2,

                                      PhaseTransform* phase);

  static bool adr_phi_is_loop_invariant(Node* adr_phi, Node* cast);

  static Node *optimize_simple_memory_chain(Node *mchain, const TypePtr *t_adr, PhaseGVN *phase);

  static Node *optimize_memory_chain(Node *mchain, const TypePtr *t_adr, PhaseGVN *phase);

  // This one should probably be a phase-specific function:

  static bool all_controls_dominate(Node* dom, Node* sub);

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

  static  Node *Ideal_common_DU_postCCP( PhaseCCP *ccp, Node* n, Node* adr );

  virtual Node *Ideal_DU_postCCP( PhaseCCP *ccp );

  virtual const class TypePtr *adr_type() const;  // returns bottom_type of address

  // Shared code for Ideal methods:

  Node *Ideal_common(PhaseGVN *phase, bool can_reshape);  // Return -1 for short-circuit NULL.

  // Helper function for adr_type() implementations.

  static const TypePtr* calculate_adr_type(const Type* t, const TypePtr* cross_check = NULL);

  // Raw access function, to allow copying of adr_type efficiently in

  // product builds and retain the debug info for debug builds.

  const TypePtr *raw_adr_type() const {

#ifdef ASSERT

    return _adr_type;

#else

    return 0;

#endif

  }

  // Map a load or store opcode to its corresponding store opcode.

  // (Return -1 if unknown.)

  virtual int store_Opcode() const { return -1; }

  // What is the type of the value in memory?  (T_VOID mean "unspecified".)

  virtual BasicType memory_type() const = 0;

  virtual int memory_size() const {

#ifdef ASSERT

    return type2aelembytes(memory_type(), true);

#else

    return type2aelembytes(memory_type());

#endif

  }

  // Search through memory states which precede this node (load or store).

  // Look for an exact match for the address, with no intervening

  // aliased stores.

  Node* find_previous_store(PhaseTransform* phase);

  // Can this node (load or store) accurately see a stored value in

  // the given memory state?  (The state may or may not be in(Memory).)

  Node* can_see_stored_value(Node* st, PhaseTransform* phase) const;

#ifndef PRODUCT

  static void dump_adr_type(const Node* mem, const TypePtr* adr_type, outputStream *st);

  virtual void dump_spec(outputStream *st) const;

#endif

};

//------------------------------LoadNode---------------------------------------

// Load value; requires Memory and Address

class LoadNode : public MemNode {

protected:

  virtual uint cmp( const Node &n ) const;

  virtual uint size_of() const; // Size is bigger

  const Type* const _type;      // What kind of value is loaded?

public:

  LoadNode( Node *c, Node *mem, Node *adr, const TypePtr* at, const Type *rt )

    : MemNode(c,mem,adr,at), _type(rt) {

    init_class_id(Class_Load);

  }

  // Polymorphic factory method:

  static Node* make( PhaseGVN& gvn, Node *c, Node *mem, Node *adr,

                     const TypePtr* at, const Type *rt, BasicType bt );

  virtual uint hash()   const;  // Check the type

  // Handle algebraic identities here.  If we have an identity, return the Node

  // we are equivalent to.  We look for Load of a Store.

  virtual Node *Identity( PhaseTransform *phase );

  // If the load is from Field memory and the pointer is non-null, we can

  // zero out the control input.

  virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);

  // Split instance field load through Phi.

  Node* split_through_phi(PhaseGVN *phase);

  // Recover original value from boxed values

  Node *eliminate_autobox(PhaseGVN *phase);

  // Compute a new Type for this node.  Basically we just do the pre-check,

  // then call the virtual add() to set the type.

  virtual const Type *Value( PhaseTransform *phase ) const;

  // Common methods for LoadKlass and LoadNKlass nodes.

  const Type *klass_value_common( PhaseTransform *phase ) const;

  Node *klass_identity_common( PhaseTransform *phase );

  virtual uint ideal_reg() const;

  virtual const Type *bottom_type() const;

  // Following method is copied from TypeNode:

  void set_type(const Type* t) {

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

    debug_only(uint check_hash = (VerifyHashTableKeys && _hash_lock) ? hash() : NO_HASH);

    *(const Type**)&_type = t;   // cast away const-ness

    // If this node is in the hash table, make sure it doesn't need a rehash.

    assert(check_hash == NO_HASH || check_hash == hash(), "type change must preserve hash code");

  }

  const Type* type() const { assert(_type != NULL, "sanity"); return _type; };

  // Do not match memory edge

  virtual uint match_edge(uint idx) const;

  // Map a load opcode to its corresponding store opcode.

  virtual int store_Opcode() const = 0;

  // Check if the load's memory input is a Phi node with the same control.

  bool is_instance_field_load_with_local_phi(Node* ctrl);

#ifndef PRODUCT

  virtual void dump_spec(outputStream *st) const;

#endif

protected:

  const Type* load_array_final_field(const TypeKlassPtr *tkls,

                                     ciKlass* klass) const;

};

//------------------------------LoadBNode--------------------------------------

// Load a byte (8bits signed) from memory

class LoadBNode : public LoadNode {

public:

  LoadBNode( Node *c, Node *mem, Node *adr, const TypePtr* at, const TypeInt *ti = TypeInt::BYTE )

    : LoadNode(c,mem,adr,at,ti) {}

  virtual int Opcode() const;

  virtual uint ideal_reg() const { return Op_RegI; }

  virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);

  virtual int store_Opcode() const { return Op_StoreB; }

  virtual BasicType memory_type() const { return T_BYTE; }

};

//------------------------------LoadCNode--------------------------------------

// Load a char (16bits unsigned) from memory

class LoadCNode : public LoadNode {

public:

  LoadCNode( Node *c, Node *mem, Node *adr, const TypePtr* at, const TypeInt *ti = TypeInt::CHAR )

    : LoadNode(c,mem,adr,at,ti) {}

  virtual int Opcode() const;

  virtual uint ideal_reg() const { return Op_RegI; }

  virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);

  virtual int store_Opcode() const { return Op_StoreC; }

  virtual BasicType memory_type() const { return T_CHAR; }

};

//------------------------------LoadINode--------------------------------------

// Load an integer from memory

class LoadINode : public LoadNode {

public:

  LoadINode( Node *c, Node *mem, Node *adr, const TypePtr* at, const TypeInt *ti = TypeInt::INT )

    : LoadNode(c,mem,adr,at,ti) {}

  virtual int Opcode() const;

  virtual uint ideal_reg() const { return Op_RegI; }

  virtual int store_Opcode() const { return Op_StoreI; }

  virtual BasicType memory_type() const { return T_INT; }

};

//------------------------------LoadRangeNode----------------------------------

// Load an array length from the array

class LoadRangeNode : public LoadINode {

public:

  LoadRangeNode( Node *c, Node *mem, Node *adr, const TypeInt *ti = TypeInt::POS )

    : LoadINode(c,mem,adr,TypeAryPtr::RANGE,ti) {}

  virtual int Opcode() const;

  virtual const Type *Value( PhaseTransform *phase ) const;

  virtual Node *Identity( PhaseTransform *phase );

  virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);

};

//------------------------------LoadLNode--------------------------------------

// Load a long from memory

class LoadLNode : public LoadNode {

  virtual uint hash() const { return LoadNode::hash() + _require_atomic_access; }

  virtual uint cmp( const Node &n ) const {

    return _require_atomic_access == ((LoadLNode&)n)._require_atomic_access

      && LoadNode::cmp(n);

  }

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

  const bool _require_atomic_access;  // is piecewise load forbidden?

public:

  LoadLNode( Node *c, Node *mem, Node *adr, const TypePtr* at,

             const TypeLong *tl = TypeLong::LONG,

             bool require_atomic_access = false )

    : LoadNode(c,mem,adr,at,tl)

    , _require_atomic_access(require_atomic_access)

  {}

  virtual int Opcode() const;

  virtual uint ideal_reg() const { return Op_RegL; }

  virtual int store_Opcode() const { return Op_StoreL; }

  virtual BasicType memory_type() const { return T_LONG; }

  bool require_atomic_access() { return _require_atomic_access; }

  static LoadLNode* make_atomic(Compile *C, Node* ctl, Node* mem, Node* adr, const TypePtr* adr_type, const Type* rt);

#ifndef PRODUCT

  virtual void dump_spec(outputStream *st) const {

    LoadNode::dump_spec(st);

    if (_require_atomic_access)  st->print(" Atomic!");

  }

#endif

};

//------------------------------LoadL_unalignedNode----------------------------

// Load a long from unaligned memory

class LoadL_unalignedNode : public LoadLNode {

public:

  LoadL_unalignedNode( Node *c, Node *mem, Node *adr, const TypePtr* at )

    : LoadLNode(c,mem,adr,at) {}

  virtual int Opcode() const;

};

//------------------------------LoadFNode--------------------------------------

// Load a float (64 bits) from memory

class LoadFNode : public LoadNode {

public:

  LoadFNode( Node *c, Node *mem, Node *adr, const TypePtr* at, const Type *t = Type::FLOAT )

    : LoadNode(c,mem,adr,at,t) {}

  virtual int Opcode() const;

  virtual uint ideal_reg() const { return Op_RegF; }

  virtual int store_Opcode() const { return Op_StoreF; }

  virtual BasicType memory_type() const { return T_FLOAT; }

};

//------------------------------LoadDNode--------------------------------------

// Load a double (64 bits) from memory

class LoadDNode : public LoadNode {

public:

  LoadDNode( Node *c, Node *mem, Node *adr, const TypePtr* at, const Type *t = Type::DOUBLE )

    : LoadNode(c,mem,adr,at,t) {}

  virtual int Opcode() const;

  virtual uint ideal_reg() const { return Op_RegD; }

  virtual int store_Opcode() const { return Op_StoreD; }

  virtual BasicType memory_type() const { return T_DOUBLE; }

};

//------------------------------LoadD_unalignedNode----------------------------

// Load a double from unaligned memory

class LoadD_unalignedNode : public LoadDNode {

public:

  LoadD_unalignedNode( Node *c, Node *mem, Node *adr, const TypePtr* at )

    : LoadDNode(c,mem,adr,at) {}

  virtual int Opcode() const;

};

//------------------------------LoadPNode--------------------------------------

// Load a pointer from memory (either object or array)

class LoadPNode : public LoadNode {

public:

  LoadPNode( Node *c, Node *mem, Node *adr, const TypePtr *at, const TypePtr* t )

    : LoadNode(c,mem,adr,at,t) {}

  virtual int Opcode() const;

  virtual uint ideal_reg() const { return Op_RegP; }

  virtual int store_Opcode() const { return Op_StoreP; }

  virtual BasicType memory_type() const { return T_ADDRESS; }

  // depends_only_on_test is almost always true, and needs to be almost always

  // true to enable key hoisting & commoning optimizations.  However, for the

  // special case of RawPtr loads from TLS top & end, the control edge carries

  // the dependence preventing hoisting past a Safepoint instead of the memory

  // edge.  (An unfortunate consequence of having Safepoints not set Raw

  // Memory; itself an unfortunate consequence of having Nodes which produce

  // results (new raw memory state) inside of loops preventing all manner of

  // other optimizations).  Basically, it's ugly but so is the alternative.

  // See comment in macro.cpp, around line 125 expand_allocate_common().

  virtual bool depends_only_on_test() const { return adr_type() != TypeRawPtr::BOTTOM; }

};

//------------------------------LoadNNode--------------------------------------

// Load a narrow oop from memory (either object or array)

class LoadNNode : public LoadNode {

public:

  LoadNNode( Node *c, Node *mem, Node *adr, const TypePtr *at, const Type* t )

    : LoadNode(c,mem,adr,at,t) {}

  virtual int Opcode() const;

  virtual uint ideal_reg() const { return Op_RegN; }

  virtual int store_Opcode() const { return Op_StoreN; }

  virtual BasicType memory_type() const { return T_NARROWOOP; }

  // depends_only_on_test is almost always true, and needs to be almost always

  // true to enable key hoisting & commoning optimizations.  However, for the

  // special case of RawPtr loads from TLS top & end, the control edge carries

  // the dependence preventing hoisting past a Safepoint instead of the memory

  // edge.  (An unfortunate consequence of having Safepoints not set Raw

  // Memory; itself an unfortunate consequence of having Nodes which produce

  // results (new raw memory state) inside of loops preventing all manner of

  // other optimizations).  Basically, it's ugly but so is the alternative.

  // See comment in macro.cpp, around line 125 expand_allocate_common().

  virtual bool depends_only_on_test() const { return adr_type() != TypeRawPtr::BOTTOM; }

};

//------------------------------LoadKlassNode----------------------------------

// Load a Klass from an object

class LoadKlassNode : public LoadPNode {

public:

  LoadKlassNode( Node *c, Node *mem, Node *adr, const TypePtr *at, const TypeKlassPtr *tk )

    : LoadPNode(c,mem,adr,at,tk) {}

  virtual int Opcode() const;

  virtual const Type *Value( PhaseTransform *phase ) const;

  virtual Node *Identity( PhaseTransform *phase );

  virtual bool depends_only_on_test() const { return true; }

  // Polymorphic factory method:

  static Node* make( PhaseGVN& gvn, Node *mem, Node *adr, const TypePtr* at,

                     const TypeKlassPtr *tk = TypeKlassPtr::OBJECT );

};

//------------------------------LoadNKlassNode---------------------------------

// Load a narrow Klass from an object.

class LoadNKlassNode : public LoadNNode {

public:

  LoadNKlassNode( Node *c, Node *mem, Node *adr, const TypePtr *at, const TypeNarrowOop *tk )

    : LoadNNode(c,mem,adr,at,tk) {}

  virtual int Opcode() const;

  virtual uint ideal_reg() const { return Op_RegN; }

  virtual int store_Opcode() const { return Op_StoreN; }

  virtual BasicType memory_type() const { return T_NARROWOOP; }

  virtual const Type *Value( PhaseTransform *phase ) const;

  virtual Node *Identity( PhaseTransform *phase );

  virtual bool depends_only_on_test() const { return true; }

};

//------------------------------LoadSNode--------------------------------------

// Load a short (16bits signed) from memory

class LoadSNode : public LoadNode {

public:

  LoadSNode( Node *c, Node *mem, Node *adr, const TypePtr* at, const TypeInt *ti = TypeInt::SHORT )

    : LoadNode(c,mem,adr,at,ti) {}

  virtual int Opcode() const;

  virtual uint ideal_reg() const { return Op_RegI; }

  virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);

  virtual int store_Opcode() const { return Op_StoreC; }

  virtual BasicType memory_type() const { return T_SHORT; }

};

//------------------------------StoreNode--------------------------------------

// Store value; requires Store, Address and Value

class StoreNode : public MemNode {

protected:

  virtual uint cmp( const Node &n ) const;

  virtual bool depends_only_on_test() const { return false; }

  Node *Ideal_masked_input       (PhaseGVN *phase, uint mask);

  Node *Ideal_sign_extended_input(PhaseGVN *phase, int  num_bits);

public:

  StoreNode( Node *c, Node *mem, Node *adr, const TypePtr* at, Node *val )

    : MemNode(c,mem,adr,at,val) {

    init_class_id(Class_Store);

  }

  StoreNode( Node *c, Node *mem, Node *adr, const TypePtr* at, Node *val, Node *oop_store )

    : MemNode(c,mem,adr,at,val,oop_store) {

    init_class_id(Class_Store);

  }

  // Polymorphic factory method:

  static StoreNode* make( PhaseGVN& gvn, Node *c, Node *mem, Node *adr,

                          const TypePtr* at, Node *val, BasicType bt );

  virtual uint hash() const;    // Check the type

  // If the store is to Field memory and the pointer is non-null, we can

  // zero out the control input.

  virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);

  // Compute a new Type for this node.  Basically we just do the pre-check,

  // then call the virtual add() to set the type.

  virtual const Type *Value( PhaseTransform *phase ) const;

  // Check for identity function on memory (Load then Store at same address)

  virtual Node *Identity( PhaseTransform *phase );

  // Do not match memory edge

  virtual uint match_edge(uint idx) const;

  virtual const Type *bottom_type() const;  // returns Type::MEMORY

  // Map a store opcode to its corresponding own opcode, trivially.

  virtual int store_Opcode() const { return Opcode(); }

  // have all possible loads of the value stored been optimized away?

  bool value_never_loaded(PhaseTransform *phase) const;

};

//------------------------------StoreBNode-------------------------------------

// Store byte to memory

class StoreBNode : public StoreNode {

public:

  StoreBNode( Node *c, Node *mem, Node *adr, const TypePtr* at, Node *val ) : StoreNode(c,mem,adr,at,val) {}

  virtual int Opcode() const;

  virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);

  virtual BasicType memory_type() const { return T_BYTE; }

};

//------------------------------StoreCNode-------------------------------------

// Store char/short to memory

class StoreCNode : public StoreNode {

public:

  StoreCNode( Node *c, Node *mem, Node *adr, const TypePtr* at, Node *val ) : StoreNode(c,mem,adr,at,val) {}

  virtual int Opcode() const;

  virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);

  virtual BasicType memory_type() const { return T_CHAR; }

};

//------------------------------StoreINode-------------------------------------

// Store int to memory

class StoreINode : public StoreNode {

public:

  StoreINode( Node *c, Node *mem, Node *adr, const TypePtr* at, Node *val ) : StoreNode(c,mem,adr,at,val) {}

  virtual int Opcode() const;

  virtual BasicType memory_type() const { return T_INT; }

};

//------------------------------StoreLNode-------------------------------------

// Store long to memory

class StoreLNode : public StoreNode {

  virtual uint hash() const { return StoreNode::hash() + _require_atomic_access; }

  virtual uint cmp( const Node &n ) const {

    return _require_atomic_access == ((StoreLNode&)n)._require_atomic_access

      && StoreNode::cmp(n);

  }

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

  const bool _require_atomic_access;  // is piecewise store forbidden?

public:

  StoreLNode( Node *c, Node *mem, Node *adr, const TypePtr* at, Node *val,

              bool require_atomic_access = false )

    : StoreNode(c,mem,adr,at,val)

    , _require_atomic_access(require_atomic_access)

  {}

  virtual int Opcode() const;

  virtual BasicType memory_type() const { return T_LONG; }

  bool require_atomic_access() { return _require_atomic_access; }

  static StoreLNode* make_atomic(Compile *C, Node* ctl, Node* mem, Node* adr, const TypePtr* adr_type, Node* val);

#ifndef PRODUCT

  virtual void dump_spec(outputStream *st) const {

    StoreNode::dump_spec(st);

    if (_require_atomic_access)  st->print(" Atomic!");

  }

#endif

};

//------------------------------StoreFNode-------------------------------------

// Store float to memory

class StoreFNode : public StoreNode {