/*

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

 *

 */

#include "precompiled.hpp"

#include "ci/ciMethodData.hpp"

#include "ci/ciTypeFlow.hpp"

#include "classfile/symbolTable.hpp"

#include "classfile/systemDictionary.hpp"

#include "compiler/compileLog.hpp"

#include "gc/shared/gcLocker.hpp"

#include "libadt/dict.hpp"

#include "memory/oopFactory.hpp"

#include "memory/resourceArea.hpp"

#include "oops/instanceKlass.hpp"

#include "oops/instanceMirrorKlass.hpp"

#include "oops/objArrayKlass.hpp"

#include "oops/typeArrayKlass.hpp"

#include "opto/matcher.hpp"

#include "opto/node.hpp"

#include "opto/opcodes.hpp"

#include "opto/type.hpp"

// Portions of code courtesy of Clifford Click

// Optimization - Graph Style

// Dictionary of types shared among compilations.

Dict* Type::_shared_type_dict = NULL;

// Array which maps compiler types to Basic Types

Type::TypeInfo Type::_type_info[Type::lastype] = {

  { Bad,             T_ILLEGAL,    "bad",           false, Node::NotAMachineReg, relocInfo::none          },  // Bad

  { Control,         T_ILLEGAL,    "control",       false, 0,                    relocInfo::none          },  // Control

  { Bottom,          T_VOID,       "top",           false, 0,                    relocInfo::none          },  // Top

  { Bad,             T_INT,        "int:",          false, Op_RegI,              relocInfo::none          },  // Int

  { Bad,             T_LONG,       "long:",         false, Op_RegL,              relocInfo::none          },  // Long

  { Half,            T_VOID,       "half",          false, 0,                    relocInfo::none          },  // Half

  { Bad,             T_NARROWOOP,  "narrowoop:",    false, Op_RegN,              relocInfo::none          },  // NarrowOop

  { Bad,             T_NARROWKLASS,"narrowklass:",  false, Op_RegN,              relocInfo::none          },  // NarrowKlass

  { Bad,             T_ILLEGAL,    "tuple:",        false, Node::NotAMachineReg, relocInfo::none          },  // Tuple

  { Bad,             T_ARRAY,      "array:",        false, Node::NotAMachineReg, relocInfo::none          },  // Array

#ifdef SPARC

  { Bad,             T_ILLEGAL,    "vectors:",      false, 0,                    relocInfo::none          },  // VectorS

  { Bad,             T_ILLEGAL,    "vectord:",      false, Op_RegD,              relocInfo::none          },  // VectorD

  { Bad,             T_ILLEGAL,    "vectorx:",      false, 0,                    relocInfo::none          },  // VectorX

  { Bad,             T_ILLEGAL,    "vectory:",      false, 0,                    relocInfo::none          },  // VectorY

  { Bad,             T_ILLEGAL,    "vectorz:",      false, 0,                    relocInfo::none          },  // VectorZ

#elif defined(PPC64)

  { Bad,             T_ILLEGAL,    "vectors:",      false, 0,                    relocInfo::none          },  // VectorS

  { Bad,             T_ILLEGAL,    "vectord:",      false, Op_RegL,              relocInfo::none          },  // VectorD

  { Bad,             T_ILLEGAL,    "vectorx:",      false, 0,                    relocInfo::none          },  // VectorX

  { Bad,             T_ILLEGAL,    "vectory:",      false, 0,                    relocInfo::none          },  // VectorY

  { Bad,             T_ILLEGAL,    "vectorz:",      false, 0,                    relocInfo::none          },  // VectorZ

#else // all other

  { Bad,             T_ILLEGAL,    "vectors:",      false, Op_VecS,              relocInfo::none          },  // VectorS

  { Bad,             T_ILLEGAL,    "vectord:",      false, Op_VecD,              relocInfo::none          },  // VectorD

  { Bad,             T_ILLEGAL,    "vectorx:",      false, Op_VecX,              relocInfo::none          },  // VectorX

  { Bad,             T_ILLEGAL,    "vectory:",      false, Op_VecY,              relocInfo::none          },  // VectorY

  { Bad,             T_ILLEGAL,    "vectorz:",      false, Op_VecZ,              relocInfo::none          },  // VectorZ

#endif

  { Bad,             T_ADDRESS,    "anyptr:",       false, Op_RegP,              relocInfo::none          },  // AnyPtr

  { Bad,             T_ADDRESS,    "rawptr:",       false, Op_RegP,              relocInfo::none          },  // RawPtr

  { Bad,             T_OBJECT,     "oop:",          true,  Op_RegP,              relocInfo::oop_type      },  // OopPtr

  { Bad,             T_OBJECT,     "inst:",         true,  Op_RegP,              relocInfo::oop_type      },  // InstPtr

  { Bad,             T_OBJECT,     "ary:",          true,  Op_RegP,              relocInfo::oop_type      },  // AryPtr

  { Bad,             T_METADATA,   "metadata:",     false, Op_RegP,              relocInfo::metadata_type },  // MetadataPtr

  { Bad,             T_METADATA,   "klass:",        false, Op_RegP,              relocInfo::metadata_type },  // KlassPtr

  { Bad,             T_OBJECT,     "func",          false, 0,                    relocInfo::none          },  // Function

  { Abio,            T_ILLEGAL,    "abIO",          false, 0,                    relocInfo::none          },  // Abio

  { Return_Address,  T_ADDRESS,    "return_address",false, Op_RegP,              relocInfo::none          },  // Return_Address

  { Memory,          T_ILLEGAL,    "memory",        false, 0,                    relocInfo::none          },  // Memory

  { FloatBot,        T_FLOAT,      "float_top",     false, Op_RegF,              relocInfo::none          },  // FloatTop

  { FloatCon,        T_FLOAT,      "ftcon:",        false, Op_RegF,              relocInfo::none          },  // FloatCon

  { FloatTop,        T_FLOAT,      "float",         false, Op_RegF,              relocInfo::none          },  // FloatBot

  { DoubleBot,       T_DOUBLE,     "double_top",    false, Op_RegD,              relocInfo::none          },  // DoubleTop

  { DoubleCon,       T_DOUBLE,     "dblcon:",       false, Op_RegD,              relocInfo::none          },  // DoubleCon

  { DoubleTop,       T_DOUBLE,     "double",        false, Op_RegD,              relocInfo::none          },  // DoubleBot

  { Top,             T_ILLEGAL,    "bottom",        false, 0,                    relocInfo::none          }   // Bottom

};

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

const Type *Type::mreg2type[_last_machine_leaf];

// Map basic types to canonical Type* pointers.

const Type* Type::     _const_basic_type[T_CONFLICT+1];

// Map basic types to constant-zero Types.

const Type* Type::            _zero_type[T_CONFLICT+1];

// Map basic types to array-body alias types.

const TypeAryPtr* TypeAryPtr::_array_body_type[T_CONFLICT+1];

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

// Convenience common pre-built types.

const Type *Type::ABIO;         // State-of-machine only

const Type *Type::BOTTOM;       // All values

const Type *Type::CONTROL;      // Control only

const Type *Type::DOUBLE;       // All doubles

const Type *Type::FLOAT;        // All floats

const Type *Type::HALF;         // Placeholder half of doublewide type

const Type *Type::MEMORY;       // Abstract store only

const Type *Type::RETURN_ADDRESS;

const Type *Type::TOP;          // No values in set

//------------------------------get_const_type---------------------------

const Type* Type::get_const_type(ciType* type) {

  if (type == NULL) {

    return NULL;

  } else if (type->is_primitive_type()) {

    return get_const_basic_type(type->basic_type());

  } else {

    return TypeOopPtr::make_from_klass(type->as_klass());

  }

}

//---------------------------array_element_basic_type---------------------------------

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

BasicType Type::array_element_basic_type() const {

  BasicType bt = basic_type();

  if (bt == T_INT) {

    if (this == TypeInt::INT)   return T_INT;

    if (this == TypeInt::CHAR)  return T_CHAR;

    if (this == TypeInt::BYTE)  return T_BYTE;

    if (this == TypeInt::BOOL)  return T_BOOLEAN;

    if (this == TypeInt::SHORT) return T_SHORT;

    return T_VOID;

  }

  return bt;

}

// For two instance arrays of same dimension, return the base element types.

// Otherwise or if the arrays have different dimensions, return NULL.

void Type::get_arrays_base_elements(const Type *a1, const Type *a2,

                                    const TypeInstPtr **e1, const TypeInstPtr **e2) {

  if (e1) *e1 = NULL;

  if (e2) *e2 = NULL;

  const TypeAryPtr* a1tap = (a1 == NULL) ? NULL : a1->isa_aryptr();

  const TypeAryPtr* a2tap = (a2 == NULL) ? NULL : a2->isa_aryptr();

  if (a1tap != NULL && a2tap != NULL) {

    // Handle multidimensional arrays

    const TypePtr* a1tp = a1tap->elem()->make_ptr();

    const TypePtr* a2tp = a2tap->elem()->make_ptr();

    while (a1tp && a1tp->isa_aryptr() && a2tp && a2tp->isa_aryptr()) {

      a1tap = a1tp->is_aryptr();

      a2tap = a2tp->is_aryptr();

      a1tp = a1tap->elem()->make_ptr();

      a2tp = a2tap->elem()->make_ptr();

    }

    if (a1tp && a1tp->isa_instptr() && a2tp && a2tp->isa_instptr()) {

      if (e1) *e1 = a1tp->is_instptr();

      if (e2) *e2 = a2tp->is_instptr();

    }

  }

}

//---------------------------get_typeflow_type---------------------------------

// Import a type produced by ciTypeFlow.

const Type* Type::get_typeflow_type(ciType* type) {

  switch (type->basic_type()) {

  case ciTypeFlow::StateVector::T_BOTTOM:

    assert(type == ciTypeFlow::StateVector::bottom_type(), "");

    return Type::BOTTOM;

  case ciTypeFlow::StateVector::T_TOP:

    assert(type == ciTypeFlow::StateVector::top_type(), "");

    return Type::TOP;

  case ciTypeFlow::StateVector::T_NULL:

    assert(type == ciTypeFlow::StateVector::null_type(), "");

    return TypePtr::NULL_PTR;

  case ciTypeFlow::StateVector::T_LONG2:

    // The ciTypeFlow pass pushes a long, then the half.

    // We do the same.

    assert(type == ciTypeFlow::StateVector::long2_type(), "");

    return TypeInt::TOP;

  case ciTypeFlow::StateVector::T_DOUBLE2:

    // The ciTypeFlow pass pushes double, then the half.

    // Our convention is the same.

    assert(type == ciTypeFlow::StateVector::double2_type(), "");

    return Type::TOP;

  case T_ADDRESS:

    assert(type->is_return_address(), "");

    return TypeRawPtr::make((address)(intptr_t)type->as_return_address()->bci());

  default:

    // make sure we did not mix up the cases:

    assert(type != ciTypeFlow::StateVector::bottom_type(), "");

    assert(type != ciTypeFlow::StateVector::top_type(), "");

    assert(type != ciTypeFlow::StateVector::null_type(), "");

    assert(type != ciTypeFlow::StateVector::long2_type(), "");

    assert(type != ciTypeFlow::StateVector::double2_type(), "");

    assert(!type->is_return_address(), "");

    return Type::get_const_type(type);

  }

}

//-----------------------make_from_constant------------------------------------

  switch (constant.basic_type()) {

      }

  }

  // Fall through to failure

  return NULL;

}

  if (field->is_static()) {

    // final static field

    // final or stable non-static field

    // Treat final non-static fields of trusted classes (classes in

    // java.lang.invoke and sun.invoke packages and subpackages) as

    // compile time constants.

  }

    }

  }

  return con_type;

}

//------------------------------make-------------------------------------------

// Create a simple Type, with default empty symbol sets.  Then hashcons it

// and look for an existing copy in the type dictionary.

const Type *Type::make( enum TYPES t ) {

  return (new Type(t))->hashcons();

}

//------------------------------cmp--------------------------------------------

int Type::cmp( const Type *const t1, const Type *const t2 ) {

  if( t1->_base != t2->_base )

    return 1;                   // Missed badly

  assert(t1 != t2 || t1->eq(t2), "eq must be reflexive");

  return !t1->eq(t2);           // Return ZERO if equal

}

const Type* Type::maybe_remove_speculative(bool include_speculative) const {

  if (!include_speculative) {

    return remove_speculative();

  }

  return this;

}

//------------------------------hash-------------------------------------------

int Type::uhash( const Type *const t ) {

  return t->hash();

}

#define SMALLINT ((juint)3)  // a value too insignificant to consider widening

//--------------------------Initialize_shared----------------------------------

void Type::Initialize_shared(Compile* current) {

  // This method does not need to be locked because the first system

  // compilations (stub compilations) occur serially.  If they are

  // changed to proceed in parallel, then this section will need

  // locking.

  Arena* save = current->type_arena();

  Arena* shared_type_arena = new (mtCompiler)Arena(mtCompiler);

  current->set_type_arena(shared_type_arena);

  _shared_type_dict =

    new (shared_type_arena) Dict( (CmpKey)Type::cmp, (Hash)Type::uhash,

                                  shared_type_arena, 128 );

  current->set_type_dict(_shared_type_dict);

  // Make shared pre-built types.

  CONTROL = make(Control);      // Control only

  TOP     = make(Top);          // No values in set

  MEMORY  = make(Memory);       // Abstract store only

  ABIO    = make(Abio);         // State-of-machine only

  RETURN_ADDRESS=make(Return_Address);

  FLOAT   = make(FloatBot);     // All floats

  DOUBLE  = make(DoubleBot);    // All doubles

  BOTTOM  = make(Bottom);       // Everything

  HALF    = make(Half);         // Placeholder half of doublewide type

  TypeF::ZERO = TypeF::make(0.0); // Float 0 (positive zero)

  TypeF::ONE  = TypeF::make(1.0); // Float 1

  TypeD::ZERO = TypeD::make(0.0); // Double 0 (positive zero)

  TypeD::ONE  = TypeD::make(1.0); // Double 1

  TypeInt::MINUS_1 = TypeInt::make(-1);  // -1

  TypeInt::ZERO    = TypeInt::make( 0);  //  0

  TypeInt::ONE     = TypeInt::make( 1);  //  1

  TypeInt::BOOL    = TypeInt::make(0,1,   WidenMin);  // 0 or 1, FALSE or TRUE.

  TypeInt::CC      = TypeInt::make(-1, 1, WidenMin);  // -1, 0 or 1, condition codes

  TypeInt::CC_LT   = TypeInt::make(-1,-1, WidenMin);  // == TypeInt::MINUS_1

  TypeInt::CC_GT   = TypeInt::make( 1, 1, WidenMin);  // == TypeInt::ONE

  TypeInt::CC_EQ   = TypeInt::make( 0, 0, WidenMin);  // == TypeInt::ZERO

  TypeInt::CC_LE   = TypeInt::make(-1, 0, WidenMin);

  TypeInt::CC_GE   = TypeInt::make( 0, 1, WidenMin);  // == TypeInt::BOOL

  TypeInt::BYTE    = TypeInt::make(-128,127,     WidenMin); // Bytes

  TypeInt::UBYTE   = TypeInt::make(0, 255,       WidenMin); // Unsigned Bytes

  TypeInt::CHAR    = TypeInt::make(0,65535,      WidenMin); // Java chars

  TypeInt::SHORT   = TypeInt::make(-32768,32767, WidenMin); // Java shorts

  TypeInt::POS     = TypeInt::make(0,max_jint,   WidenMin); // Non-neg values

  TypeInt::POS1    = TypeInt::make(1,max_jint,   WidenMin); // Positive values

  TypeInt::INT     = TypeInt::make(min_jint,max_jint, WidenMax); // 32-bit integers

  TypeInt::SYMINT  = TypeInt::make(-max_jint,max_jint,WidenMin); // symmetric range

  TypeInt::TYPE_DOMAIN  = TypeInt::INT;

  // CmpL is overloaded both as the bytecode computation returning

  // a trinary (-1,0,+1) integer result AND as an efficient long

  // compare returning optimizer ideal-type flags.

  assert( TypeInt::CC_LT == TypeInt::MINUS_1, "types must match for CmpL to work" );

  assert( TypeInt::CC_GT == TypeInt::ONE,     "types must match for CmpL to work" );

  assert( TypeInt::CC_EQ == TypeInt::ZERO,    "types must match for CmpL to work" );

  assert( TypeInt::CC_GE == TypeInt::BOOL,    "types must match for CmpL to work" );

  assert( (juint)(TypeInt::CC->_hi - TypeInt::CC->_lo) <= SMALLINT, "CC is truly small");

  TypeLong::MINUS_1 = TypeLong::make(-1);        // -1

  TypeLong::ZERO    = TypeLong::make( 0);        //  0

  TypeLong::ONE     = TypeLong::make( 1);        //  1

  TypeLong::POS     = TypeLong::make(0,max_jlong, WidenMin); // Non-neg values

  TypeLong::LONG    = TypeLong::make(min_jlong,max_jlong,WidenMax); // 64-bit integers

  TypeLong::INT     = TypeLong::make((jlong)min_jint,(jlong)max_jint,WidenMin);

  TypeLong::UINT    = TypeLong::make(0,(jlong)max_juint,WidenMin);

  TypeLong::TYPE_DOMAIN  = TypeLong::LONG;

  const Type **fboth =(const Type**)shared_type_arena->Amalloc_4(2*sizeof(Type*));

  fboth[0] = Type::CONTROL;

  fboth[1] = Type::CONTROL;

  TypeTuple::IFBOTH = TypeTuple::make( 2, fboth );

  const Type **ffalse =(const Type**)shared_type_arena->Amalloc_4(2*sizeof(Type*));

  ffalse[0] = Type::CONTROL;

  ffalse[1] = Type::TOP;

  TypeTuple::IFFALSE = TypeTuple::make( 2, ffalse );

  const Type **fneither =(const Type**)shared_type_arena->Amalloc_4(2*sizeof(Type*));

  fneither[0] = Type::TOP;

  fneither[1] = Type::TOP;

  TypeTuple::IFNEITHER = TypeTuple::make( 2, fneither );

  const Type **ftrue =(const Type**)shared_type_arena->Amalloc_4(2*sizeof(Type*));

  ftrue[0] = Type::TOP;

  ftrue[1] = Type::CONTROL;

  TypeTuple::IFTRUE = TypeTuple::make( 2, ftrue );

  const Type **floop =(const Type**)shared_type_arena->Amalloc_4(2*sizeof(Type*));

  floop[0] = Type::CONTROL;

  floop[1] = TypeInt::INT;

  TypeTuple::LOOPBODY = TypeTuple::make( 2, floop );