/*

 * Copyright (c) 1997, 2013, 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.

 *

 */

#ifndef SHARE_VM_OPTO_TYPE_HPP

#define SHARE_VM_OPTO_TYPE_HPP

#include "opto/adlcVMDeps.hpp"

#include "runtime/handles.hpp"

// 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   TypeNarrowPtr;

class     TypeNarrowOop;

class     TypeNarrowKlass;

class   TypeAry;

class   TypeTuple;

class   TypeVect;

class     TypeVectS;

class     TypeVectD;

class     TypeVectX;

class     TypeVectY;

class   TypePtr;

class     TypeRawPtr;

class     TypeOopPtr;

class       TypeInstPtr;

class       TypeAryPtr;

class     TypeKlassPtr;

class     TypeMetadataPtr;

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

  friend class VMStructs;

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

    NarrowKlass,                // Compressed klass pointer

    Tuple,                      // Method signature or object layout

    Array,                      // Array types

    VectorS,                    //  32bit Vector types

    VectorD,                    //  64bit Vector types

    VectorX,                    // 128bit Vector types

    VectorY,                    // 256bit Vector 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

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

    MetadataPtr,                // Generic metadata

    KlassPtr,                   // Klass pointers

    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:

  typedef struct {

    const TYPES                dual_type;

    const BasicType            basic_type;

    const char*                msg;

    const bool                 isa_oop;

    const int                  ideal_reg;

    const relocInfo::relocType reloc;

  } TypeInfo;

  // Dictionary of types shared among compilations.

  static Dict* _shared_type_dict;

  static TypeInfo _type_info[];

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

#ifdef ASSERT

  // One type is interface, the other is oop

  virtual bool interface_vs_oop_helper(const Type *t) const;

#endif

  const Type *meet_helper(const Type *t, bool include_speculative) const;

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

  virtual const Type *filter_helper(const Type *kills, bool include_speculative) const;

  const Type *join_helper(const Type *t, bool include_speculative) const {

    return dual()->meet_helper(t->dual(), include_speculative)->dual();

  }

public:

  inline void* operator new( size_t x ) throw() {

    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

  // Variant that drops the speculative part of the types

  int higher_equal(const Type *t) const {

    return !cmp(meet(t),t->remove_speculative());

  }

  // Variant that keeps the speculative part of the types

  int higher_equal_speculative(const Type *t) const {

    return !cmp(meet_speculative(t),t);

  }

  // MEET operation; lower in lattice.

  // Variant that drops the speculative part of the types

  const Type *meet(const Type *t) const {

    return meet_helper(t, false);

  }

  // Variant that keeps the speculative part of the types

  const Type *meet_speculative(const Type *t) const {

    return meet_helper(t, true)->cleanup_speculative();

  }

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

  virtual const Type *widen( const Type *old, const Type* limit ) 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.

  // Variant that drops the speculative part of the types

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

    return join_helper(t, false);

  }

  // Variant that keeps the speculative part of the types

  const Type *join_speculative(const Type *t) const {

    return join_helper(t, true)->cleanup_speculative();

  }

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

  // Variant that drops the speculative part of the types

  const Type *filter(const Type *kills) const {

    return filter_helper(kills, false);

  }

  // Variant that keeps the speculative part of the types

  const Type *filter_speculative(const Type *kills) const {

    return filter_helper(kills, true)->cleanup_speculative();

  }

#ifdef ASSERT

  // One type is interface, the other is oop

  virtual bool interface_vs_oop(const Type *t) const;

#endif

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

  // compressed oop references.

  bool is_ptr_to_narrowoop() const;

  bool is_ptr_to_narrowklass() const;

  bool is_ptr_to_boxing_obj() 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      *isa_double() const;          // Returns NULL if not a Double{Top,Con,Bot}

  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      *isa_float() const;           // Returns NULL if not a Float{Top,Con,Bot}

  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 TypeVect   *is_vect() const;             // Vector

  const TypeVect   *isa_vect() const;            // Returns NULL if not a Vector

  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 TypeNarrowKlass *is_narrowklass() const; // compressed klass pointer

  const TypeNarrowKlass *isa_narrowklass() 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 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

  const TypeMetadataPtr   *isa_metadataptr() const;   // Returns NULL if not oop ptr type

  const TypeMetadataPtr   *is_metadataptr() 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

  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 oopptr type or the equivalent oopptr type for this compressed pointer.

  // Asserts if the underlying type is not an oopptr or narrowoop.

  const TypeOopPtr* make_oopptr() const;

  // Returns this compressed pointer or the equivalent compressed version

  // of this pointer type.

  const TypeNarrowOop* make_narrowoop() const;

  // Returns this compressed klass pointer or the equivalent

  // compressed version of this pointer type.

  const TypeNarrowKlass* make_narrowklass() 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;

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

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

#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 _type_info[_base].basic_type; }

  int ideal_reg() const              { return _type_info[_base].ideal_reg; }

  const char* msg() const            { return _type_info[_base].msg; }

  bool isa_oop_ptr() const           { return _type_info[_base].isa_oop; }

  relocInfo::relocType reloc() const { return _type_info[_base].reloc; }

  // Mapping from CI type system to compiler type:

  static const Type* get_typeflow_type(ciType* type);

  static const Type* make_from_constant(ciConstant constant,

                                        bool require_constant = false,

                                        bool is_autobox_cache = false);

  // Speculative type helper methods. See TypePtr.

  virtual const TypePtr* speculative() const                                  { return NULL; }

  virtual ciKlass* speculative_type() const                                   { return NULL; }

  virtual ciKlass* speculative_type_not_null() const                          { return NULL; }

  virtual bool speculative_maybe_null() const                                 { return true; }

  virtual const Type* remove_speculative() const                              { return this; }

  virtual const Type* cleanup_speculative() const                             { return this; }

  virtual bool would_improve_type(ciKlass* exact_kls, int inline_depth) const { return exact_kls != NULL; }

  virtual bool would_improve_ptr(bool maybe_null) const                       { return !maybe_null; }

  const Type* maybe_remove_speculative(bool include_speculative) const;

  virtual bool maybe_null() const { return true; }

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

protected:

  virtual const Type *filter_helper(const Type *kills, bool include_speculative) const;

public:

  typedef jint NativeType;

  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

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