/*

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

// This class defines a Type lattice.  The lattice is used in the constant

// propagation algorithms, and for some type-checking of the iloc code.

// Basic types include RSD's (lower bound, upper bound, stride for integers),

// float & double precision constants, sets of data-labels and code-labels.

// The complete lattice is described below.  Subtypes have no relationship to

// up or down in the lattice; that is entirely determined by the behavior of

// the MEET/JOIN functions.

class Dict;

class Type;

class   TypeD;

class   TypeF;

class   TypeInt;

class   TypeLong;

class   TypeNarrowOop;

class   TypeAry;

class   TypeTuple;

class   TypePtr;

class     TypeRawPtr;

class     TypeOopPtr;

class       TypeInstPtr;

class       TypeAryPtr;

class       TypeKlassPtr;

//------------------------------Type-------------------------------------------

// Basic Type object, represents a set of primitive Values.

// Types are hash-cons'd into a private class dictionary, so only one of each

// different kind of Type exists.  Types are never modified after creation, so

// all their interesting fields are constant.

class Type {

public:

  enum TYPES {

    Bad=0,                      // Type check

    Control,                    // Control of code (not in lattice)

    Top,                        // Top of the lattice

    Int,                        // Integer range (lo-hi)

    Long,                       // Long integer range (lo-hi)

    Half,                       // Placeholder half of doubleword

    NarrowOop,                  // Compressed oop pointer

    Tuple,                      // Method signature or object layout

    Array,                      // Array types

    AnyPtr,                     // Any old raw, klass, inst, or array pointer

    RawPtr,                     // Raw (non-oop) pointers

    OopPtr,                     // Any and all Java heap entities

    InstPtr,                    // Instance pointers (non-array objects)

    AryPtr,                     // Array pointers

    KlassPtr,                   // Klass pointers

    // (Ptr order matters:  See is_ptr, isa_ptr, is_oopptr, isa_oopptr.)

    Function,                   // Function signature

    Abio,                       // Abstract I/O

    Return_Address,             // Subroutine return address

    Memory,                     // Abstract store

    FloatTop,                   // No float value

    FloatCon,                   // Floating point constant

    FloatBot,                   // Any float value

    DoubleTop,                  // No double value

    DoubleCon,                  // Double precision constant

    DoubleBot,                  // Any double value

    Bottom,                     // Bottom of lattice

    lastype                     // Bogus ending type (not in lattice)

  };

  // Signal values for offsets from a base pointer

  enum OFFSET_SIGNALS {

    OffsetTop = -2000000000,    // undefined offset

    OffsetBot = -2000000001     // any possible offset

  };

  // Min and max WIDEN values.

  enum WIDEN {

    WidenMin = 0,

    WidenMax = 3

  };

private:

  // Dictionary of types shared among compilations.

  static Dict* _shared_type_dict;

  static int uhash( const Type *const t );

  // Structural equality check.  Assumes that cmp() has already compared

  // the _base types and thus knows it can cast 't' appropriately.

  virtual bool eq( const Type *t ) const;

  // Top-level hash-table of types

  static Dict *type_dict() {

    return Compile::current()->type_dict();

  }

  // DUAL operation: reflect around lattice centerline.  Used instead of

  // join to ensure my lattice is symmetric up and down.  Dual is computed

  // lazily, on demand, and cached in _dual.

  const Type *_dual;            // Cached dual value

  // Table for efficient dualing of base types

  static const TYPES dual_type[lastype];

protected:

  // Each class of type is also identified by its base.

  const TYPES _base;            // Enum of Types type

  Type( TYPES t ) : _dual(NULL),  _base(t) {} // Simple types

  // ~Type();                   // Use fast deallocation

  const Type *hashcons();       // Hash-cons the type

public:

  inline void* operator new( size_t x ) {

    Compile* compile = Compile::current();

    compile->set_type_last_size(x);

    void *temp = compile->type_arena()->Amalloc_D(x);

    compile->set_type_hwm(temp);

    return temp;

  }

  inline void operator delete( void* ptr ) {

    Compile* compile = Compile::current();

    compile->type_arena()->Afree(ptr,compile->type_last_size());

  }

  // Initialize the type system for a particular compilation.

  static void Initialize(Compile* compile);

  // Initialize the types shared by all compilations.

  static void Initialize_shared(Compile* compile);

  TYPES base() const {

    assert(_base > Bad && _base < lastype, "sanity");

    return _base;

  }

  // Create a new hash-consd type

  static const Type *make(enum TYPES);

  // Test for equivalence of types

  static int cmp( const Type *const t1, const Type *const t2 );

  // Test for higher or equal in lattice

  int higher_equal( const Type *t ) const { return !cmp(meet(t),t); }

  // MEET operation; lower in lattice.

  const Type *meet( const Type *t ) const;

  // WIDEN: 'widens' for Ints and other range types

  virtual const Type *widen( const Type *old ) const { return this; }

  // NARROW: complement for widen, used by pessimistic phases

  virtual const Type *narrow( const Type *old ) const { return this; }

  // DUAL operation: reflect around lattice centerline.  Used instead of

  // join to ensure my lattice is symmetric up and down.

  const Type *dual() const { return _dual; }

  // Compute meet dependent on base type

  virtual const Type *xmeet( const Type *t ) const;

  virtual const Type *xdual() const;    // Compute dual right now.

  // JOIN operation; higher in lattice.  Done by finding the dual of the

  // meet of the dual of the 2 inputs.

  const Type *join( const Type *t ) const {

    return dual()->meet(t->dual())->dual(); }

  // Modified version of JOIN adapted to the needs Node::Value.

  // Normalizes all empty values to TOP.  Does not kill _widen bits.

  // Currently, it also works around limitations involving interface types.

  virtual const Type *filter( const Type *kills ) const;

  // Returns true if this pointer points at memory which contains a

  // compressed oop references.

  bool is_ptr_to_narrowoop() const;

  // Convenience access

  float getf() const;

  double getd() const;

  const TypeInt    *is_int() const;

  const TypeInt    *isa_int() const;             // Returns NULL if not an Int

  const TypeLong   *is_long() const;

  const TypeLong   *isa_long() const;            // Returns NULL if not a Long

  const TypeD      *is_double_constant() const;  // Asserts it is a DoubleCon

  const TypeD      *isa_double_constant() const; // Returns NULL if not a DoubleCon

  const TypeF      *is_float_constant() const;   // Asserts it is a FloatCon

  const TypeF      *isa_float_constant() const;  // Returns NULL if not a FloatCon

  const TypeTuple  *is_tuple() const;            // Collection of fields, NOT a pointer

  const TypeAry    *is_ary() const;              // Array, NOT array pointer

  const TypePtr    *is_ptr() const;              // Asserts it is a ptr type

  const TypePtr    *isa_ptr() const;             // Returns NULL if not ptr type

  const TypeRawPtr *isa_rawptr() const;          // NOT Java oop

  const TypeRawPtr *is_rawptr() const;           // Asserts is rawptr

  const TypeNarrowOop  *is_narrowoop() const;    // Java-style GC'd pointer

  const TypeNarrowOop  *isa_narrowoop() const;   // Returns NULL if not oop ptr type

  const TypeOopPtr   *isa_oopptr() const;        // Returns NULL if not oop ptr type

  const TypeOopPtr   *is_oopptr() const;         // Java-style GC'd pointer

  const TypeKlassPtr *isa_klassptr() const;      // Returns NULL if not KlassPtr

  const TypeKlassPtr *is_klassptr() const;       // assert if not KlassPtr

  const TypeInstPtr  *isa_instptr() const;       // Returns NULL if not InstPtr

  const TypeInstPtr  *is_instptr() const;        // Instance

  const TypeAryPtr   *isa_aryptr() const;        // Returns NULL if not AryPtr

  const TypeAryPtr   *is_aryptr() const;         // Array oop

  virtual bool      is_finite() const;           // Has a finite value

  virtual bool      is_nan()    const;           // Is not a number (NaN)

  // Returns this ptr type or the equivalent ptr type for this compressed pointer.

  const TypePtr* make_ptr() const;

  // Returns this compressed pointer or the equivalent compressed version

  // of this pointer type.

  const TypeNarrowOop* make_narrowoop() const;

  // Special test for register pressure heuristic

  bool is_floatingpoint() const;        // True if Float or Double base type

  // Do you have memory, directly or through a tuple?

  bool has_memory( ) const;

  // Are you a pointer type or not?

  bool isa_oop_ptr() const;

  // TRUE if type is a singleton

  virtual bool singleton(void) const;

  // TRUE if type is above the lattice centerline, and is therefore vacuous

  virtual bool empty(void) const;

  // Return a hash for this type.  The hash function is public so ConNode

  // (constants) can hash on their constant, which is represented by a Type.

  virtual int hash() const;

  // Map ideal registers (machine types) to ideal types

  static const Type *mreg2type[];

  // Printing, statistics

  static const char * const msg[lastype]; // Printable strings

#ifndef PRODUCT

  void         dump_on(outputStream *st) const;

  void         dump() const {

    dump_on(tty);

  }

  virtual void dump2( Dict &d, uint depth, outputStream *st ) const;

  static  void dump_stats();

  static  void verify_lastype();          // Check that arrays match type enum

#endif

  void typerr(const Type *t) const; // Mixing types error

  // Create basic type

  static const Type* get_const_basic_type(BasicType type) {

    assert((uint)type <= T_CONFLICT && _const_basic_type[type] != NULL, "bad type");

    return _const_basic_type[type];

  }

  // Mapping to the array element's basic type.

  BasicType array_element_basic_type() const;

  // Create standard type for a ciType:

  static const Type* get_const_type(ciType* type);

  // Create standard zero value:

  static const Type* get_zero_type(BasicType type) {

    assert((uint)type <= T_CONFLICT && _zero_type[type] != NULL, "bad type");

    return _zero_type[type];

  }

  // Report if this is a zero value (not top).

  bool is_zero_type() const {

    BasicType type = basic_type();

    if (type == T_VOID || type >= T_CONFLICT)

      return false;

    else

      return (this == _zero_type[type]);

  }

  // Convenience common pre-built types.

  static const Type *ABIO;

  static const Type *BOTTOM;

  static const Type *CONTROL;

  static const Type *DOUBLE;

  static const Type *FLOAT;

  static const Type *HALF;

  static const Type *MEMORY;

  static const Type *MULTI;

  static const Type *RETURN_ADDRESS;

  static const Type *TOP;

  // Mapping from compiler type to VM BasicType

  BasicType basic_type() const { return _basic_type[_base]; }

  // Mapping from CI type system to compiler type:

  static const Type* get_typeflow_type(ciType* type);

private:

  // support arrays

  static const BasicType _basic_type[];

  static const Type*        _zero_type[T_CONFLICT+1];

  static const Type* _const_basic_type[T_CONFLICT+1];

};

//------------------------------TypeF------------------------------------------

// Class of Float-Constant Types.

class TypeF : public Type {

  TypeF( float f ) : Type(FloatCon), _f(f) {};

public:

  virtual bool eq( const Type *t ) const;

  virtual int  hash() const;             // Type specific hashing

  virtual bool singleton(void) const;    // TRUE if type is a singleton

  virtual bool empty(void) const;        // TRUE if type is vacuous

public:

  const float _f;               // Float constant

  static const TypeF *make(float f);

  virtual bool        is_finite() const;  // Has a finite value

  virtual bool        is_nan()    const;  // Is not a number (NaN)

  virtual const Type *xmeet( const Type *t ) const;

  virtual const Type *xdual() const;    // Compute dual right now.

  // Convenience common pre-built types.

  static const TypeF *ZERO; // positive zero only

  static const TypeF *ONE;

#ifndef PRODUCT

  virtual void dump2( Dict &d, uint depth, outputStream *st ) const;

#endif

};

//------------------------------TypeD------------------------------------------

// Class of Double-Constant Types.

class TypeD : public Type {

  TypeD( double d ) : Type(DoubleCon), _d(d) {};

public:

  virtual bool eq( const Type *t ) const;

  virtual int  hash() const;             // Type specific hashing

  virtual bool singleton(void) const;    // TRUE if type is a singleton

  virtual bool empty(void) const;        // TRUE if type is vacuous

public:

  const double _d;              // Double constant

  static const TypeD *make(double d);

  virtual bool        is_finite() const;  // Has a finite value

  virtual bool        is_nan()    const;  // Is not a number (NaN)

  virtual const Type *xmeet( const Type *t ) const;

  virtual const Type *xdual() const;    // Compute dual right now.

  // Convenience common pre-built types.

  static const TypeD *ZERO; // positive zero only

  static const TypeD *ONE;

#ifndef PRODUCT

  virtual void dump2( Dict &d, uint depth, outputStream *st ) const;

#endif

};

//------------------------------TypeInt----------------------------------------

// Class of integer ranges, the set of integers between a lower bound and an

// upper bound, inclusive.

class TypeInt : public Type {

  TypeInt( jint lo, jint hi, int w );

public:

  virtual bool eq( const Type *t ) const;

  virtual int  hash() const;             // Type specific hashing

  virtual bool singleton(void) const;    // TRUE if type is a singleton

  virtual bool empty(void) const;        // TRUE if type is vacuous

public:

  const jint _lo, _hi;          // Lower bound, upper bound

  const short _widen;           // Limit on times we widen this sucker

  static const TypeInt *make(jint lo);

  // must always specify w

  static const TypeInt *make(jint lo, jint hi, int w);

  // Check for single integer

  int is_con() const { return _lo==_hi; }

  bool is_con(int i) const { return is_con() && _lo == i; }

  jint get_con() const { assert( is_con(), "" );  return _lo; }

  virtual bool        is_finite() const;  // Has a finite value

  virtual const Type *xmeet( const Type *t ) const;

  virtual const Type *xdual() const;    // Compute dual right now.

  virtual const Type *widen( const Type *t ) const;

  virtual const Type *narrow( const Type *t ) const;

  // Do not kill _widen bits.

  virtual const Type *filter( const Type *kills ) const;

  // Convenience common pre-built types.

  static const TypeInt *MINUS_1;

  static const TypeInt *ZERO;

  static const TypeInt *ONE;

  static const TypeInt *BOOL;

  static const TypeInt *CC;

  static const TypeInt *CC_LT;  // [-1]  == MINUS_1

  static const TypeInt *CC_GT;  // [1]   == ONE

  static const TypeInt *CC_EQ;  // [0]   == ZERO

  static const TypeInt *CC_LE;  // [-1,0]

  static const TypeInt *CC_GE;  // [0,1] == BOOL (!)

  static const TypeInt *BYTE;

  static const TypeInt *UBYTE;

  static const TypeInt *CHAR;

  static const TypeInt *SHORT;

  static const TypeInt *POS;

  static const TypeInt *POS1;

  static const TypeInt *INT;

  static const TypeInt *SYMINT; // symmetric range [-max_jint..max_jint]

#ifndef PRODUCT

  virtual void dump2( Dict &d, uint depth, outputStream *st ) const;

#endif

};

//------------------------------TypeLong---------------------------------------

// Class of long integer ranges, the set of integers between a lower bound and

// an upper bound, inclusive.

class TypeLong : public Type {

  TypeLong( jlong lo, jlong hi, int w );

public:

  virtual bool eq( const Type *t ) const;

  virtual int  hash() const;             // Type specific hashing

  virtual bool singleton(void) const;    // TRUE if type is a singleton

  virtual bool empty(void) const;        // TRUE if type is vacuous

public:

  const jlong _lo, _hi;         // Lower bound, upper bound

  const short _widen;           // Limit on times we widen this sucker

  static const TypeLong *make(jlong lo);

  // must always specify w

  static const TypeLong *make(jlong lo, jlong hi, int w);

  // Check for single integer

  int is_con() const { return _lo==_hi; }

  bool is_con(int i) const { return is_con() && _lo == i; }

  jlong get_con() const { assert( is_con(), "" ); return _lo; }

  virtual bool        is_finite() const;  // Has a finite value

  virtual const Type *xmeet( const Type *t ) const;

  virtual const Type *xdual() const;    // Compute dual right now.

  virtual const Type *widen( const Type *t ) const;

  virtual const Type *narrow( const Type *t ) const;

  // Do not kill _widen bits.

  virtual const Type *filter( const Type *kills ) const;

  // Convenience common pre-built types.

  static const TypeLong *MINUS_1;

  static const TypeLong *ZERO;

  static const TypeLong *ONE;

  static const TypeLong *POS;

  static const TypeLong *LONG;

  static const TypeLong *INT;    // 32-bit subrange [min_jint..max_jint]

  static const TypeLong *UINT;   // 32-bit unsigned [0..max_juint]

#ifndef PRODUCT

  virtual void dump2( Dict &d, uint, outputStream *st  ) const;// Specialized per-Type dumping

#endif

};

//------------------------------TypeTuple--------------------------------------

// Class of Tuple Types, essentially type collections for function signatures

// and class layouts.  It happens to also be a fast cache for the HotSpot

// signature types.

class TypeTuple : public Type {

  TypeTuple( uint cnt, const Type **fields ) : Type(Tuple), _cnt(cnt), _fields(fields) { }

public:

  virtual bool eq( const Type *t ) const;

  virtual int  hash() const;             // Type specific hashing

  virtual bool singleton(void) const;    // TRUE if type is a singleton

  virtual bool empty(void) const;        // TRUE if type is vacuous

public:

  const uint          _cnt;              // Count of fields

  const Type ** const _fields;           // Array of field types

  // Accessors:

  uint cnt() const { return _cnt; }

  const Type* field_at(uint i) const {

    assert(i < _cnt, "oob");

    return _fields[i];

  }

  void set_field_at(uint i, const Type* t) {

    assert(i < _cnt, "oob");

    _fields[i] = t;

  }

  static const TypeTuple *make( uint cnt, const Type **fields );

  static const TypeTuple *make_range(ciSignature *sig);

  static const TypeTuple *make_domain(ciInstanceKlass* recv, ciSignature *sig);

  // Subroutine call type with space allocated for argument types

  static const Type **fields( uint arg_cnt );

  virtual const Type *xmeet( const Type *t ) const;

  virtual const Type *xdual() const;    // Compute dual right now.

  // Convenience common pre-built types.

  static const TypeTuple *IFBOTH;

  static const TypeTuple *IFFALSE;

  static const TypeTuple *IFTRUE;

  static const TypeTuple *IFNEITHER;

  static const TypeTuple *LOOPBODY;

  static const TypeTuple *MEMBAR;

  static const TypeTuple *STORECONDITIONAL;

  static const TypeTuple *START_I2C;

  static const TypeTuple *INT_PAIR;