/*

 * 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/ciTypeFlow.hpp"

#include "classfile/symbolTable.hpp"

#include "classfile/systemDictionary.hpp"

#include "compiler/compileLog.hpp"

#include "libadt/dict.hpp"

#include "memory/gcLocker.hpp"

#include "memory/oopFactory.hpp"

#include "memory/resourceArea.hpp"

#include "oops/instanceKlass.hpp"

#include "oops/instanceMirrorKlass.hpp"

#include "oops/klassKlass.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

const BasicType Type::_basic_type[Type::lastype] = {

  T_ILLEGAL,    // Bad

  T_ILLEGAL,    // Control

  T_VOID,       // Top

  T_INT,        // Int

  T_LONG,       // Long

  T_VOID,       // Half

  T_NARROWOOP,  // NarrowOop

  T_ILLEGAL,    // Tuple

  T_ARRAY,      // Array

  T_ADDRESS,    // AnyPtr   // shows up in factory methods for NULL_PTR

  T_ADDRESS,    // RawPtr

  T_OBJECT,     // OopPtr

  T_OBJECT,     // InstPtr

  T_OBJECT,     // AryPtr

  T_OBJECT,     // KlassPtr

  T_OBJECT,     // Function

  T_ILLEGAL,    // Abio

  T_ADDRESS,    // Return_Address

  T_ILLEGAL,    // Memory

  T_FLOAT,      // FloatTop

  T_FLOAT,      // FloatCon

  T_FLOAT,      // FloatBot

  T_DOUBLE,     // DoubleTop

  T_DOUBLE,     // DoubleCon

  T_DOUBLE,     // DoubleBot

  T_ILLEGAL,    // 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;

}

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

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

}

//------------------------------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 Arena();

  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

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

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

  TypePtr::NULL_PTR= TypePtr::make( AnyPtr, TypePtr::Null, 0 );

  TypePtr::NOTNULL = TypePtr::make( AnyPtr, TypePtr::NotNull, OffsetBot );

  TypePtr::BOTTOM  = TypePtr::make( AnyPtr, TypePtr::BotPTR, OffsetBot );

  TypeRawPtr::BOTTOM = TypeRawPtr::make( TypePtr::BotPTR );

  TypeRawPtr::NOTNULL= TypeRawPtr::make( TypePtr::NotNull );

  const Type **fmembar = TypeTuple::fields(0);

  TypeTuple::MEMBAR = TypeTuple::make(TypeFunc::Parms+0, fmembar);

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

  fsc[0] = TypeInt::CC;

  fsc[1] = Type::MEMORY;

  TypeTuple::STORECONDITIONAL = TypeTuple::make(2, fsc);

  TypeInstPtr::NOTNULL = TypeInstPtr::make(TypePtr::NotNull, current->env()->Object_klass());

  TypeInstPtr::BOTTOM  = TypeInstPtr::make(TypePtr::BotPTR,  current->env()->Object_klass());

  TypeInstPtr::MIRROR  = TypeInstPtr::make(TypePtr::NotNull, current->env()->Class_klass());

  TypeInstPtr::MARK    = TypeInstPtr::make(TypePtr::BotPTR,  current->env()->Object_klass(),

                                           false, 0, oopDesc::mark_offset_in_bytes());

  TypeInstPtr::KLASS   = TypeInstPtr::make(TypePtr::BotPTR,  current->env()->Object_klass(),

                                           false, 0, oopDesc::klass_offset_in_bytes());

  TypeOopPtr::BOTTOM  = TypeOopPtr::make(TypePtr::BotPTR, OffsetBot, TypeOopPtr::InstanceBot);

  TypeNarrowOop::NULL_PTR = TypeNarrowOop::make( TypePtr::NULL_PTR );

  TypeNarrowOop::BOTTOM   = TypeNarrowOop::make( TypeInstPtr::BOTTOM );

  mreg2type[Op_Node] = Type::BOTTOM;

  mreg2type[Op_Set ] = 0;

  mreg2type[Op_RegN] = TypeNarrowOop::BOTTOM;

  mreg2type[Op_RegI] = TypeInt::INT;

  mreg2type[Op_RegP] = TypePtr::BOTTOM;

  mreg2type[Op_RegF] = Type::FLOAT;

  mreg2type[Op_RegD] = Type::DOUBLE;

  mreg2type[Op_RegL] = TypeLong::LONG;

  mreg2type[Op_RegFlags] = TypeInt::CC;

  TypeAryPtr::RANGE   = TypeAryPtr::make( TypePtr::BotPTR, TypeAry::make(Type::BOTTOM,TypeInt::POS), NULL /* current->env()->Object_klass() */, false, arrayOopDesc::length_offset_in_bytes());

  TypeAryPtr::NARROWOOPS = TypeAryPtr::make(TypePtr::BotPTR, TypeAry::make(TypeNarrowOop::BOTTOM, TypeInt::POS), NULL /*ciArrayKlass::make(o)*/,  false,  Type::OffsetBot);

#ifdef _LP64

  if (UseCompressedOops) {

    TypeAryPtr::OOPS  = TypeAryPtr::NARROWOOPS;

  } else

#endif

  {

    // There is no shared klass for Object[].  See note in TypeAryPtr::klass().

    TypeAryPtr::OOPS  = TypeAryPtr::make(TypePtr::BotPTR, TypeAry::make(TypeInstPtr::BOTTOM,TypeInt::POS), NULL /*ciArrayKlass::make(o)*/,  false,  Type::OffsetBot);

  }

  TypeAryPtr::BYTES   = TypeAryPtr::make(TypePtr::BotPTR, TypeAry::make(TypeInt::BYTE      ,TypeInt::POS), ciTypeArrayKlass::make(T_BYTE),   true,  Type::OffsetBot);

  TypeAryPtr::SHORTS  = TypeAryPtr::make(TypePtr::BotPTR, TypeAry::make(TypeInt::SHORT     ,TypeInt::POS), ciTypeArrayKlass::make(T_SHORT),  true,  Type::OffsetBot);

  TypeAryPtr::CHARS   = TypeAryPtr::make(TypePtr::BotPTR, TypeAry::make(TypeInt::CHAR      ,TypeInt::POS), ciTypeArrayKlass::make(T_CHAR),   true,  Type::OffsetBot);

  TypeAryPtr::INTS    = TypeAryPtr::make(TypePtr::BotPTR, TypeAry::make(TypeInt::INT       ,TypeInt::POS), ciTypeArrayKlass::make(T_INT),    true,  Type::OffsetBot);

  TypeAryPtr::LONGS   = TypeAryPtr::make(TypePtr::BotPTR, TypeAry::make(TypeLong::LONG     ,TypeInt::POS), ciTypeArrayKlass::make(T_LONG),   true,  Type::OffsetBot);

  TypeAryPtr::FLOATS  = TypeAryPtr::make(TypePtr::BotPTR, TypeAry::make(Type::FLOAT        ,TypeInt::POS), ciTypeArrayKlass::make(T_FLOAT),  true,  Type::OffsetBot);

  TypeAryPtr::DOUBLES = TypeAryPtr::make(TypePtr::BotPTR, TypeAry::make(Type::DOUBLE       ,TypeInt::POS), ciTypeArrayKlass::make(T_DOUBLE), true,  Type::OffsetBot);

  // Nobody should ask _array_body_type[T_NARROWOOP]. Use NULL as assert.

  TypeAryPtr::_array_body_type[T_NARROWOOP] = NULL;

  TypeAryPtr::_array_body_type[T_OBJECT]  = TypeAryPtr::OOPS;

  TypeAryPtr::_array_body_type[T_ARRAY]   = TypeAryPtr::OOPS; // arrays are stored in oop arrays

  TypeAryPtr::_array_body_type[T_BYTE]    = TypeAryPtr::BYTES;

  TypeAryPtr::_array_body_type[T_BOOLEAN] = TypeAryPtr::BYTES;  // boolean[] is a byte array

  TypeAryPtr::_array_body_type[T_SHORT]   = TypeAryPtr::SHORTS;

  TypeAryPtr::_array_body_type[T_CHAR]    = TypeAryPtr::CHARS;

  TypeAryPtr::_array_body_type[T_INT]     = TypeAryPtr::INTS;

  TypeAryPtr::_array_body_type[T_LONG]    = TypeAryPtr::LONGS;

  TypeAryPtr::_array_body_type[T_FLOAT]   = TypeAryPtr::FLOATS;

  TypeAryPtr::_array_body_type[T_DOUBLE]  = TypeAryPtr::DOUBLES;

  TypeKlassPtr::OBJECT = TypeKlassPtr::make( TypePtr::NotNull, current->env()->Object_klass(), 0 );

  TypeKlassPtr::OBJECT_OR_NULL = TypeKlassPtr::make( TypePtr::BotPTR, current->env()->Object_klass(), 0 );

  const Type **fi2c = TypeTuple::fields(2);

  fi2c[TypeFunc::Parms+0] = TypeInstPtr::BOTTOM; // methodOop

  fi2c[TypeFunc::Parms+1] = TypeRawPtr::BOTTOM; // argument pointer

  TypeTuple::START_I2C = TypeTuple::make(TypeFunc::Parms+2, fi2c);

  const Type **intpair = TypeTuple::fields(2);

  intpair[0] = TypeInt::INT;

  intpair[1] = TypeInt::INT;

  TypeTuple::INT_PAIR = TypeTuple::make(2, intpair);

  const Type **longpair = TypeTuple::fields(2);

  longpair[0] = TypeLong::LONG;

  longpair[1] = TypeLong::LONG;

  TypeTuple::LONG_PAIR = TypeTuple::make(2, longpair);

  _const_basic_type[T_NARROWOOP] = TypeNarrowOop::BOTTOM;

  _const_basic_type[T_BOOLEAN] = TypeInt::BOOL;

  _const_basic_type[T_CHAR]    = TypeInt::CHAR;

  _const_basic_type[T_BYTE]    = TypeInt::BYTE;

  _const_basic_type[T_SHORT]   = TypeInt::SHORT;

  _const_basic_type[T_INT]     = TypeInt::INT;

  _const_basic_type[T_LONG]    = TypeLong::LONG;

  _const_basic_type[T_FLOAT]   = Type::FLOAT;

  _const_basic_type[T_DOUBLE]  = Type::DOUBLE;

  _const_basic_type[T_OBJECT]  = TypeInstPtr::BOTTOM;

  _const_basic_type[T_ARRAY]   = TypeInstPtr::BOTTOM; // there is no separate bottom for arrays

  _const_basic_type[T_VOID]    = TypePtr::NULL_PTR;   // reflection represents void this way

  _const_basic_type[T_ADDRESS] = TypeRawPtr::BOTTOM;  // both interpreter return addresses & random raw ptrs

  _const_basic_type[T_CONFLICT]= Type::BOTTOM;        // why not?

  _zero_type[T_NARROWOOP] = TypeNarrowOop::NULL_PTR;

  _zero_type[T_BOOLEAN] = TypeInt::ZERO;     // false == 0

  _zero_type[T_CHAR]    = TypeInt::ZERO;     // '\0' == 0

  _zero_type[T_BYTE]    = TypeInt::ZERO;     // 0x00 == 0

  _zero_type[T_SHORT]   = TypeInt::ZERO;     // 0x0000 == 0

  _zero_type[T_INT]     = TypeInt::ZERO;

  _zero_type[T_LONG]    = TypeLong::ZERO;

  _zero_type[T_FLOAT]   = TypeF::ZERO;

  _zero_type[T_DOUBLE]  = TypeD::ZERO;

  _zero_type[T_OBJECT]  = TypePtr::NULL_PTR;

  _zero_type[T_ARRAY]   = TypePtr::NULL_PTR; // null array is null oop

  _zero_type[T_ADDRESS] = TypePtr::NULL_PTR; // raw pointers use the same null

  _zero_type[T_VOID]    = Type::TOP;         // the only void value is no value at all

  // get_zero_type() should not happen for T_CONFLICT

  _zero_type[T_CONFLICT]= NULL;

  // Restore working type arena.

  current->set_type_arena(save);

  current->set_type_dict(NULL);

}

//------------------------------Initialize-------------------------------------

void Type::Initialize(Compile* current) {

  assert(current->type_arena() != NULL, "must have created type arena");

  if (_shared_type_dict == NULL) {

    Initialize_shared(current);

  }

  Arena* type_arena = current->type_arena();

  // Create the hash-cons'ing dictionary with top-level storage allocation

  Dict *tdic = new (type_arena) Dict( (CmpKey)Type::cmp,(Hash)Type::uhash, type_arena, 128 );

  current->set_type_dict(tdic);

  // Transfer the shared types.

  DictI i(_shared_type_dict);

  for( ; i.test(); ++i ) {

    Type* t = (Type*)i._value;

    tdic->Insert(t,t);  // New Type, insert into Type table

  }

#ifdef ASSERT

  verify_lastype();

#endif

}

//------------------------------hashcons---------------------------------------

// Do the hash-cons trick.  If the Type already exists in the type table,

// delete the current Type and return the existing Type.  Otherwise stick the

// current Type in the Type table.

const Type *Type::hashcons(void) {

  debug_only(base());           // Check the assertion in Type::base().

  // Look up the Type in the Type dictionary

  Dict *tdic = type_dict();

  Type* old = (Type*)(tdic->Insert(this, this, false));

  if( old ) {                   // Pre-existing Type?

    if( old != this )           // Yes, this guy is not the pre-existing?

      delete this;              // Yes, Nuke this guy

    assert( old->_dual, "" );

    return old;                 // Return pre-existing

  }

  // Every type has a dual (to make my lattice symmetric).

  // Since we just discovered a new Type, compute its dual right now.

  assert( !_dual, "" );         // No dual yet

  _dual = xdual();              // Compute the dual

  if( cmp(this,_dual)==0 ) {    // Handle self-symmetric

    _dual = this;

    return this;

  }

  assert( !_dual->_dual, "" );  // No reverse dual yet

  assert( !(*tdic)[_dual], "" ); // Dual not in type system either

  // New Type, insert into Type table

  tdic->Insert((void*)_dual,(void*)_dual);

  ((Type*)_dual)->_dual = this; // Finish up being symmetric

#ifdef ASSERT

  Type *dual_dual = (Type*)_dual->xdual();

  assert( eq(dual_dual), "xdual(xdual()) should be identity" );

  delete dual_dual;

#endif

  return this;                  // Return new Type

}

//------------------------------eq---------------------------------------------

// Structural equality check for Type representations

bool Type::eq( const Type * ) const {

  return true;                  // Nothing else can go wrong

}

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

// Type-specific hashing function.

int Type::hash(void) const {

  return _base;

}

//------------------------------is_finite--------------------------------------

// Has a finite value