1 //===-- Type.cpp - Implement the Type class -------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the Type class for the VMCore library.
12 //===----------------------------------------------------------------------===//
14 #include "LLVMContextImpl.h"
15 #include "llvm/DerivedTypes.h"
16 #include "llvm/Constants.h"
17 #include "llvm/Assembly/Writer.h"
18 #include "llvm/LLVMContext.h"
19 #include "llvm/Metadata.h"
20 #include "llvm/ADT/DepthFirstIterator.h"
21 #include "llvm/ADT/StringExtras.h"
22 #include "llvm/ADT/SCCIterator.h"
23 #include "llvm/ADT/STLExtras.h"
24 #include "llvm/Support/Compiler.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Support/ErrorHandling.h"
27 #include "llvm/Support/ManagedStatic.h"
28 #include "llvm/Support/MathExtras.h"
29 #include "llvm/Support/raw_ostream.h"
30 #include "llvm/System/Mutex.h"
31 #include "llvm/System/RWMutex.h"
32 #include "llvm/System/Threading.h"
37 // DEBUG_MERGE_TYPES - Enable this #define to see how and when derived types are
38 // created and later destroyed, all in an effort to make sure that there is only
39 // a single canonical version of a type.
41 // #define DEBUG_MERGE_TYPES 1
43 AbstractTypeUser::~AbstractTypeUser() {}
46 //===----------------------------------------------------------------------===//
47 // Type Class Implementation
48 //===----------------------------------------------------------------------===//
50 /// Because of the way Type subclasses are allocated, this function is necessary
51 /// to use the correct kind of "delete" operator to deallocate the Type object.
52 /// Some type objects (FunctionTy, StructTy) allocate additional space after
53 /// the space for their derived type to hold the contained types array of
54 /// PATypeHandles. Using this allocation scheme means all the PATypeHandles are
55 /// allocated with the type object, decreasing allocations and eliminating the
56 /// need for a std::vector to be used in the Type class itself.
57 /// @brief Type destruction function
58 void Type::destroy() const {
60 // Structures and Functions allocate their contained types past the end of
61 // the type object itself. These need to be destroyed differently than the
63 if (isa
<FunctionType
>(this) || isa
<StructType
>(this)) {
64 // First, make sure we destruct any PATypeHandles allocated by these
65 // subclasses. They must be manually destructed.
66 for (unsigned i
= 0; i
< NumContainedTys
; ++i
)
67 ContainedTys
[i
].PATypeHandle::~PATypeHandle();
69 // Now call the destructor for the subclass directly because we're going
70 // to delete this as an array of char.
71 if (isa
<FunctionType
>(this))
72 static_cast<const FunctionType
*>(this)->FunctionType::~FunctionType();
74 static_cast<const StructType
*>(this)->StructType::~StructType();
76 // Finally, remove the memory as an array deallocation of the chars it was
78 operator delete(const_cast<Type
*>(this));
83 // For all the other type subclasses, there is either no contained types or
84 // just one (all Sequentials). For Sequentials, the PATypeHandle is not
85 // allocated past the type object, its included directly in the SequentialType
86 // class. This means we can safely just do "normal" delete of this object and
87 // all the destructors that need to run will be run.
91 const Type
*Type::getPrimitiveType(LLVMContext
&C
, TypeID IDNumber
) {
93 case VoidTyID
: return getVoidTy(C
);
94 case FloatTyID
: return getFloatTy(C
);
95 case DoubleTyID
: return getDoubleTy(C
);
96 case X86_FP80TyID
: return getX86_FP80Ty(C
);
97 case FP128TyID
: return getFP128Ty(C
);
98 case PPC_FP128TyID
: return getPPC_FP128Ty(C
);
99 case LabelTyID
: return getLabelTy(C
);
100 case MetadataTyID
: return getMetadataTy(C
);
106 const Type
*Type::getVAArgsPromotedType(LLVMContext
&C
) const {
107 if (ID
== IntegerTyID
&& getSubclassData() < 32)
108 return Type::getInt32Ty(C
);
109 else if (ID
== FloatTyID
)
110 return Type::getDoubleTy(C
);
115 /// getScalarType - If this is a vector type, return the element type,
116 /// otherwise return this.
117 const Type
*Type::getScalarType() const {
118 if (const VectorType
*VTy
= dyn_cast
<VectorType
>(this))
119 return VTy
->getElementType();
123 /// isIntOrIntVector - Return true if this is an integer type or a vector of
126 bool Type::isIntOrIntVector() const {
129 if (ID
!= Type::VectorTyID
) return false;
131 return cast
<VectorType
>(this)->getElementType()->isInteger();
134 /// isFPOrFPVector - Return true if this is a FP type or a vector of FP types.
136 bool Type::isFPOrFPVector() const {
137 if (ID
== Type::FloatTyID
|| ID
== Type::DoubleTyID
||
138 ID
== Type::FP128TyID
|| ID
== Type::X86_FP80TyID
||
139 ID
== Type::PPC_FP128TyID
)
141 if (ID
!= Type::VectorTyID
) return false;
143 return cast
<VectorType
>(this)->getElementType()->isFloatingPoint();
146 // canLosslesslyBitCastTo - Return true if this type can be converted to
147 // 'Ty' without any reinterpretation of bits. For example, i8* to i32*.
149 bool Type::canLosslesslyBitCastTo(const Type
*Ty
) const {
150 // Identity cast means no change so return true
154 // They are not convertible unless they are at least first class types
155 if (!this->isFirstClassType() || !Ty
->isFirstClassType())
158 // Vector -> Vector conversions are always lossless if the two vector types
159 // have the same size, otherwise not.
160 if (const VectorType
*thisPTy
= dyn_cast
<VectorType
>(this))
161 if (const VectorType
*thatPTy
= dyn_cast
<VectorType
>(Ty
))
162 return thisPTy
->getBitWidth() == thatPTy
->getBitWidth();
164 // At this point we have only various mismatches of the first class types
165 // remaining and ptr->ptr. Just select the lossless conversions. Everything
166 // else is not lossless.
167 if (isa
<PointerType
>(this))
168 return isa
<PointerType
>(Ty
);
169 return false; // Other types have no identity values
172 unsigned Type::getPrimitiveSizeInBits() const {
173 switch (getTypeID()) {
174 case Type::FloatTyID
: return 32;
175 case Type::DoubleTyID
: return 64;
176 case Type::X86_FP80TyID
: return 80;
177 case Type::FP128TyID
: return 128;
178 case Type::PPC_FP128TyID
: return 128;
179 case Type::IntegerTyID
: return cast
<IntegerType
>(this)->getBitWidth();
180 case Type::VectorTyID
: return cast
<VectorType
>(this)->getBitWidth();
185 /// getScalarSizeInBits - If this is a vector type, return the
186 /// getPrimitiveSizeInBits value for the element type. Otherwise return the
187 /// getPrimitiveSizeInBits value for this type.
188 unsigned Type::getScalarSizeInBits() const {
189 return getScalarType()->getPrimitiveSizeInBits();
192 /// getFPMantissaWidth - Return the width of the mantissa of this type. This
193 /// is only valid on floating point types. If the FP type does not
194 /// have a stable mantissa (e.g. ppc long double), this method returns -1.
195 int Type::getFPMantissaWidth() const {
196 if (const VectorType
*VTy
= dyn_cast
<VectorType
>(this))
197 return VTy
->getElementType()->getFPMantissaWidth();
198 assert(isFloatingPoint() && "Not a floating point type!");
199 if (ID
== FloatTyID
) return 24;
200 if (ID
== DoubleTyID
) return 53;
201 if (ID
== X86_FP80TyID
) return 64;
202 if (ID
== FP128TyID
) return 113;
203 assert(ID
== PPC_FP128TyID
&& "unknown fp type");
207 /// isSizedDerivedType - Derived types like structures and arrays are sized
208 /// iff all of the members of the type are sized as well. Since asking for
209 /// their size is relatively uncommon, move this operation out of line.
210 bool Type::isSizedDerivedType() const {
211 if (isa
<IntegerType
>(this))
214 if (const ArrayType
*ATy
= dyn_cast
<ArrayType
>(this))
215 return ATy
->getElementType()->isSized();
217 if (const VectorType
*PTy
= dyn_cast
<VectorType
>(this))
218 return PTy
->getElementType()->isSized();
220 if (!isa
<StructType
>(this))
223 // Okay, our struct is sized if all of the elements are...
224 for (subtype_iterator I
= subtype_begin(), E
= subtype_end(); I
!= E
; ++I
)
225 if (!(*I
)->isSized())
231 /// getForwardedTypeInternal - This method is used to implement the union-find
232 /// algorithm for when a type is being forwarded to another type.
233 const Type
*Type::getForwardedTypeInternal() const {
234 assert(ForwardType
&& "This type is not being forwarded to another type!");
236 // Check to see if the forwarded type has been forwarded on. If so, collapse
237 // the forwarding links.
238 const Type
*RealForwardedType
= ForwardType
->getForwardedType();
239 if (!RealForwardedType
)
240 return ForwardType
; // No it's not forwarded again
242 // Yes, it is forwarded again. First thing, add the reference to the new
244 if (RealForwardedType
->isAbstract())
245 cast
<DerivedType
>(RealForwardedType
)->addRef();
247 // Now drop the old reference. This could cause ForwardType to get deleted.
248 cast
<DerivedType
>(ForwardType
)->dropRef();
250 // Return the updated type.
251 ForwardType
= RealForwardedType
;
255 void Type::refineAbstractType(const DerivedType
*OldTy
, const Type
*NewTy
) {
256 llvm_unreachable("Attempting to refine a derived type!");
258 void Type::typeBecameConcrete(const DerivedType
*AbsTy
) {
259 llvm_unreachable("DerivedType is already a concrete type!");
263 std::string
Type::getDescription() const {
264 LLVMContextImpl
*pImpl
= getContext().pImpl
;
267 pImpl
->AbstractTypeDescriptions
:
268 pImpl
->ConcreteTypeDescriptions
;
271 raw_string_ostream
DescOS(DescStr
);
272 Map
.print(this, DescOS
);
277 bool StructType::indexValid(const Value
*V
) const {
278 // Structure indexes require 32-bit integer constants.
279 if (V
->getType() == Type::getInt32Ty(V
->getContext()))
280 if (const ConstantInt
*CU
= dyn_cast
<ConstantInt
>(V
))
281 return indexValid(CU
->getZExtValue());
285 bool StructType::indexValid(unsigned V
) const {
286 return V
< NumContainedTys
;
289 // getTypeAtIndex - Given an index value into the type, return the type of the
290 // element. For a structure type, this must be a constant value...
292 const Type
*StructType::getTypeAtIndex(const Value
*V
) const {
293 unsigned Idx
= (unsigned)cast
<ConstantInt
>(V
)->getZExtValue();
294 return getTypeAtIndex(Idx
);
297 const Type
*StructType::getTypeAtIndex(unsigned Idx
) const {
298 assert(indexValid(Idx
) && "Invalid structure index!");
299 return ContainedTys
[Idx
];
302 //===----------------------------------------------------------------------===//
303 // Primitive 'Type' data
304 //===----------------------------------------------------------------------===//
306 const Type
*Type::getVoidTy(LLVMContext
&C
) {
307 return &C
.pImpl
->VoidTy
;
310 const Type
*Type::getLabelTy(LLVMContext
&C
) {
311 return &C
.pImpl
->LabelTy
;
314 const Type
*Type::getFloatTy(LLVMContext
&C
) {
315 return &C
.pImpl
->FloatTy
;
318 const Type
*Type::getDoubleTy(LLVMContext
&C
) {
319 return &C
.pImpl
->DoubleTy
;
322 const Type
*Type::getMetadataTy(LLVMContext
&C
) {
323 return &C
.pImpl
->MetadataTy
;
326 const Type
*Type::getX86_FP80Ty(LLVMContext
&C
) {
327 return &C
.pImpl
->X86_FP80Ty
;
330 const Type
*Type::getFP128Ty(LLVMContext
&C
) {
331 return &C
.pImpl
->FP128Ty
;
334 const Type
*Type::getPPC_FP128Ty(LLVMContext
&C
) {
335 return &C
.pImpl
->PPC_FP128Ty
;
338 const IntegerType
*Type::getInt1Ty(LLVMContext
&C
) {
339 return &C
.pImpl
->Int1Ty
;
342 const IntegerType
*Type::getInt8Ty(LLVMContext
&C
) {
343 return &C
.pImpl
->Int8Ty
;
346 const IntegerType
*Type::getInt16Ty(LLVMContext
&C
) {
347 return &C
.pImpl
->Int16Ty
;
350 const IntegerType
*Type::getInt32Ty(LLVMContext
&C
) {
351 return &C
.pImpl
->Int32Ty
;
354 const IntegerType
*Type::getInt64Ty(LLVMContext
&C
) {
355 return &C
.pImpl
->Int64Ty
;
358 //===----------------------------------------------------------------------===//
359 // Derived Type Constructors
360 //===----------------------------------------------------------------------===//
362 /// isValidReturnType - Return true if the specified type is valid as a return
364 bool FunctionType::isValidReturnType(const Type
*RetTy
) {
365 if (RetTy
->isFirstClassType()) {
366 if (const PointerType
*PTy
= dyn_cast
<PointerType
>(RetTy
))
367 return PTy
->getElementType()->getTypeID() != MetadataTyID
;
370 if (RetTy
->getTypeID() == VoidTyID
|| RetTy
->getTypeID() == MetadataTyID
||
371 isa
<OpaqueType
>(RetTy
))
374 // If this is a multiple return case, verify that each return is a first class
375 // value and that there is at least one value.
376 const StructType
*SRetTy
= dyn_cast
<StructType
>(RetTy
);
377 if (SRetTy
== 0 || SRetTy
->getNumElements() == 0)
380 for (unsigned i
= 0, e
= SRetTy
->getNumElements(); i
!= e
; ++i
)
381 if (!SRetTy
->getElementType(i
)->isFirstClassType())
386 /// isValidArgumentType - Return true if the specified type is valid as an
388 bool FunctionType::isValidArgumentType(const Type
*ArgTy
) {
389 if ((!ArgTy
->isFirstClassType() && !isa
<OpaqueType
>(ArgTy
)) ||
390 (isa
<PointerType
>(ArgTy
) &&
391 cast
<PointerType
>(ArgTy
)->getElementType()->getTypeID() == MetadataTyID
))
397 FunctionType::FunctionType(const Type
*Result
,
398 const std::vector
<const Type
*> &Params
,
400 : DerivedType(Result
->getContext(), FunctionTyID
), isVarArgs(IsVarArgs
) {
401 ContainedTys
= reinterpret_cast<PATypeHandle
*>(this+1);
402 NumContainedTys
= Params
.size() + 1; // + 1 for result type
403 assert(isValidReturnType(Result
) && "invalid return type for function");
406 bool isAbstract
= Result
->isAbstract();
407 new (&ContainedTys
[0]) PATypeHandle(Result
, this);
409 for (unsigned i
= 0; i
!= Params
.size(); ++i
) {
410 assert(isValidArgumentType(Params
[i
]) &&
411 "Not a valid type for function argument!");
412 new (&ContainedTys
[i
+1]) PATypeHandle(Params
[i
], this);
413 isAbstract
|= Params
[i
]->isAbstract();
416 // Calculate whether or not this type is abstract
417 setAbstract(isAbstract
);
420 StructType::StructType(LLVMContext
&C
,
421 const std::vector
<const Type
*> &Types
, bool isPacked
)
422 : CompositeType(C
, StructTyID
) {
423 ContainedTys
= reinterpret_cast<PATypeHandle
*>(this + 1);
424 NumContainedTys
= Types
.size();
425 setSubclassData(isPacked
);
426 bool isAbstract
= false;
427 for (unsigned i
= 0; i
< Types
.size(); ++i
) {
428 assert(Types
[i
] && "<null> type for structure field!");
429 assert(isValidElementType(Types
[i
]) &&
430 "Invalid type for structure element!");
431 new (&ContainedTys
[i
]) PATypeHandle(Types
[i
], this);
432 isAbstract
|= Types
[i
]->isAbstract();
435 // Calculate whether or not this type is abstract
436 setAbstract(isAbstract
);
439 ArrayType::ArrayType(const Type
*ElType
, uint64_t NumEl
)
440 : SequentialType(ArrayTyID
, ElType
) {
443 // Calculate whether or not this type is abstract
444 setAbstract(ElType
->isAbstract());
447 VectorType::VectorType(const Type
*ElType
, unsigned NumEl
)
448 : SequentialType(VectorTyID
, ElType
) {
450 setAbstract(ElType
->isAbstract());
451 assert(NumEl
> 0 && "NumEl of a VectorType must be greater than 0");
452 assert(isValidElementType(ElType
) &&
453 "Elements of a VectorType must be a primitive type");
458 PointerType::PointerType(const Type
*E
, unsigned AddrSpace
)
459 : SequentialType(PointerTyID
, E
) {
460 AddressSpace
= AddrSpace
;
461 // Calculate whether or not this type is abstract
462 setAbstract(E
->isAbstract());
465 OpaqueType::OpaqueType(LLVMContext
&C
) : DerivedType(C
, OpaqueTyID
) {
467 #ifdef DEBUG_MERGE_TYPES
468 DEBUG(errs() << "Derived new type: " << *this << "\n");
472 void PATypeHolder::destroy() {
476 // dropAllTypeUses - When this (abstract) type is resolved to be equal to
477 // another (more concrete) type, we must eliminate all references to other
478 // types, to avoid some circular reference problems.
479 void DerivedType::dropAllTypeUses() {
480 if (NumContainedTys
!= 0) {
481 // The type must stay abstract. To do this, we insert a pointer to a type
482 // that will never get resolved, thus will always be abstract.
483 static Type
*AlwaysOpaqueTy
= 0;
484 static PATypeHolder
* Holder
= 0;
485 Type
*tmp
= AlwaysOpaqueTy
;
486 if (llvm_is_multithreaded()) {
489 llvm_acquire_global_lock();
490 tmp
= AlwaysOpaqueTy
;
492 tmp
= OpaqueType::get(getContext());
493 PATypeHolder
* tmp2
= new PATypeHolder(tmp
);
495 AlwaysOpaqueTy
= tmp
;
499 llvm_release_global_lock();
501 } else if (!AlwaysOpaqueTy
) {
502 AlwaysOpaqueTy
= OpaqueType::get(getContext());
503 Holder
= new PATypeHolder(AlwaysOpaqueTy
);
506 ContainedTys
[0] = AlwaysOpaqueTy
;
508 // Change the rest of the types to be Int32Ty's. It doesn't matter what we
509 // pick so long as it doesn't point back to this type. We choose something
510 // concrete to avoid overhead for adding to AbstractTypeUser lists and
512 for (unsigned i
= 1, e
= NumContainedTys
; i
!= e
; ++i
)
513 ContainedTys
[i
] = Type::getInt32Ty(getContext());
520 /// TypePromotionGraph and graph traits - this is designed to allow us to do
521 /// efficient SCC processing of type graphs. This is the exact same as
522 /// GraphTraits<Type*>, except that we pretend that concrete types have no
523 /// children to avoid processing them.
524 struct TypePromotionGraph
{
526 TypePromotionGraph(Type
*T
) : Ty(T
) {}
532 template <> struct GraphTraits
<TypePromotionGraph
> {
533 typedef Type NodeType
;
534 typedef Type::subtype_iterator ChildIteratorType
;
536 static inline NodeType
*getEntryNode(TypePromotionGraph G
) { return G
.Ty
; }
537 static inline ChildIteratorType
child_begin(NodeType
*N
) {
539 return N
->subtype_begin();
540 else // No need to process children of concrete types.
541 return N
->subtype_end();
543 static inline ChildIteratorType
child_end(NodeType
*N
) {
544 return N
->subtype_end();
550 // PromoteAbstractToConcrete - This is a recursive function that walks a type
551 // graph calculating whether or not a type is abstract.
553 void Type::PromoteAbstractToConcrete() {
554 if (!isAbstract()) return;
556 scc_iterator
<TypePromotionGraph
> SI
= scc_begin(TypePromotionGraph(this));
557 scc_iterator
<TypePromotionGraph
> SE
= scc_end (TypePromotionGraph(this));
559 for (; SI
!= SE
; ++SI
) {
560 std::vector
<Type
*> &SCC
= *SI
;
562 // Concrete types are leaves in the tree. Since an SCC will either be all
563 // abstract or all concrete, we only need to check one type.
564 if (SCC
[0]->isAbstract()) {
565 if (isa
<OpaqueType
>(SCC
[0]))
566 return; // Not going to be concrete, sorry.
568 // If all of the children of all of the types in this SCC are concrete,
569 // then this SCC is now concrete as well. If not, neither this SCC, nor
570 // any parent SCCs will be concrete, so we might as well just exit.
571 for (unsigned i
= 0, e
= SCC
.size(); i
!= e
; ++i
)
572 for (Type::subtype_iterator CI
= SCC
[i
]->subtype_begin(),
573 E
= SCC
[i
]->subtype_end(); CI
!= E
; ++CI
)
574 if ((*CI
)->isAbstract())
575 // If the child type is in our SCC, it doesn't make the entire SCC
576 // abstract unless there is a non-SCC abstract type.
577 if (std::find(SCC
.begin(), SCC
.end(), *CI
) == SCC
.end())
578 return; // Not going to be concrete, sorry.
580 // Okay, we just discovered this whole SCC is now concrete, mark it as
582 for (unsigned i
= 0, e
= SCC
.size(); i
!= e
; ++i
) {
583 assert(SCC
[i
]->isAbstract() && "Why are we processing concrete types?");
585 SCC
[i
]->setAbstract(false);
588 for (unsigned i
= 0, e
= SCC
.size(); i
!= e
; ++i
) {
589 assert(!SCC
[i
]->isAbstract() && "Concrete type became abstract?");
590 // The type just became concrete, notify all users!
591 cast
<DerivedType
>(SCC
[i
])->notifyUsesThatTypeBecameConcrete();
598 //===----------------------------------------------------------------------===//
599 // Type Structural Equality Testing
600 //===----------------------------------------------------------------------===//
602 // TypesEqual - Two types are considered structurally equal if they have the
603 // same "shape": Every level and element of the types have identical primitive
604 // ID's, and the graphs have the same edges/nodes in them. Nodes do not have to
605 // be pointer equals to be equivalent though. This uses an optimistic algorithm
606 // that assumes that two graphs are the same until proven otherwise.
608 static bool TypesEqual(const Type
*Ty
, const Type
*Ty2
,
609 std::map
<const Type
*, const Type
*> &EqTypes
) {
610 if (Ty
== Ty2
) return true;
611 if (Ty
->getTypeID() != Ty2
->getTypeID()) return false;
612 if (isa
<OpaqueType
>(Ty
))
613 return false; // Two unequal opaque types are never equal
615 std::map
<const Type
*, const Type
*>::iterator It
= EqTypes
.find(Ty
);
616 if (It
!= EqTypes
.end())
617 return It
->second
== Ty2
; // Looping back on a type, check for equality
619 // Otherwise, add the mapping to the table to make sure we don't get
620 // recursion on the types...
621 EqTypes
.insert(It
, std::make_pair(Ty
, Ty2
));
623 // Two really annoying special cases that breaks an otherwise nice simple
624 // algorithm is the fact that arraytypes have sizes that differentiates types,
625 // and that function types can be varargs or not. Consider this now.
627 if (const IntegerType
*ITy
= dyn_cast
<IntegerType
>(Ty
)) {
628 const IntegerType
*ITy2
= cast
<IntegerType
>(Ty2
);
629 return ITy
->getBitWidth() == ITy2
->getBitWidth();
630 } else if (const PointerType
*PTy
= dyn_cast
<PointerType
>(Ty
)) {
631 const PointerType
*PTy2
= cast
<PointerType
>(Ty2
);
632 return PTy
->getAddressSpace() == PTy2
->getAddressSpace() &&
633 TypesEqual(PTy
->getElementType(), PTy2
->getElementType(), EqTypes
);
634 } else if (const StructType
*STy
= dyn_cast
<StructType
>(Ty
)) {
635 const StructType
*STy2
= cast
<StructType
>(Ty2
);
636 if (STy
->getNumElements() != STy2
->getNumElements()) return false;
637 if (STy
->isPacked() != STy2
->isPacked()) return false;
638 for (unsigned i
= 0, e
= STy2
->getNumElements(); i
!= e
; ++i
)
639 if (!TypesEqual(STy
->getElementType(i
), STy2
->getElementType(i
), EqTypes
))
642 } else if (const ArrayType
*ATy
= dyn_cast
<ArrayType
>(Ty
)) {
643 const ArrayType
*ATy2
= cast
<ArrayType
>(Ty2
);
644 return ATy
->getNumElements() == ATy2
->getNumElements() &&
645 TypesEqual(ATy
->getElementType(), ATy2
->getElementType(), EqTypes
);
646 } else if (const VectorType
*PTy
= dyn_cast
<VectorType
>(Ty
)) {
647 const VectorType
*PTy2
= cast
<VectorType
>(Ty2
);
648 return PTy
->getNumElements() == PTy2
->getNumElements() &&
649 TypesEqual(PTy
->getElementType(), PTy2
->getElementType(), EqTypes
);
650 } else if (const FunctionType
*FTy
= dyn_cast
<FunctionType
>(Ty
)) {
651 const FunctionType
*FTy2
= cast
<FunctionType
>(Ty2
);
652 if (FTy
->isVarArg() != FTy2
->isVarArg() ||
653 FTy
->getNumParams() != FTy2
->getNumParams() ||
654 !TypesEqual(FTy
->getReturnType(), FTy2
->getReturnType(), EqTypes
))
656 for (unsigned i
= 0, e
= FTy2
->getNumParams(); i
!= e
; ++i
) {
657 if (!TypesEqual(FTy
->getParamType(i
), FTy2
->getParamType(i
), EqTypes
))
662 llvm_unreachable("Unknown derived type!");
667 static bool TypesEqual(const Type
*Ty
, const Type
*Ty2
) {
668 std::map
<const Type
*, const Type
*> EqTypes
;
669 return TypesEqual(Ty
, Ty2
, EqTypes
);
672 // AbstractTypeHasCycleThrough - Return true there is a path from CurTy to
673 // TargetTy in the type graph. We know that Ty is an abstract type, so if we
674 // ever reach a non-abstract type, we know that we don't need to search the
676 static bool AbstractTypeHasCycleThrough(const Type
*TargetTy
, const Type
*CurTy
,
677 SmallPtrSet
<const Type
*, 128> &VisitedTypes
) {
678 if (TargetTy
== CurTy
) return true;
679 if (!CurTy
->isAbstract()) return false;
681 if (!VisitedTypes
.insert(CurTy
))
682 return false; // Already been here.
684 for (Type::subtype_iterator I
= CurTy
->subtype_begin(),
685 E
= CurTy
->subtype_end(); I
!= E
; ++I
)
686 if (AbstractTypeHasCycleThrough(TargetTy
, *I
, VisitedTypes
))
691 static bool ConcreteTypeHasCycleThrough(const Type
*TargetTy
, const Type
*CurTy
,
692 SmallPtrSet
<const Type
*, 128> &VisitedTypes
) {
693 if (TargetTy
== CurTy
) return true;
695 if (!VisitedTypes
.insert(CurTy
))
696 return false; // Already been here.
698 for (Type::subtype_iterator I
= CurTy
->subtype_begin(),
699 E
= CurTy
->subtype_end(); I
!= E
; ++I
)
700 if (ConcreteTypeHasCycleThrough(TargetTy
, *I
, VisitedTypes
))
705 /// TypeHasCycleThroughItself - Return true if the specified type has a cycle
707 static bool TypeHasCycleThroughItself(const Type
*Ty
) {
708 SmallPtrSet
<const Type
*, 128> VisitedTypes
;
710 if (Ty
->isAbstract()) { // Optimized case for abstract types.
711 for (Type::subtype_iterator I
= Ty
->subtype_begin(), E
= Ty
->subtype_end();
713 if (AbstractTypeHasCycleThrough(Ty
, *I
, VisitedTypes
))
716 for (Type::subtype_iterator I
= Ty
->subtype_begin(), E
= Ty
->subtype_end();
718 if (ConcreteTypeHasCycleThrough(Ty
, *I
, VisitedTypes
))
724 //===----------------------------------------------------------------------===//
725 // Function Type Factory and Value Class...
727 const IntegerType
*IntegerType::get(LLVMContext
&C
, unsigned NumBits
) {
728 assert(NumBits
>= MIN_INT_BITS
&& "bitwidth too small");
729 assert(NumBits
<= MAX_INT_BITS
&& "bitwidth too large");
731 // Check for the built-in integer types
733 case 1: return cast
<IntegerType
>(Type::getInt1Ty(C
));
734 case 8: return cast
<IntegerType
>(Type::getInt8Ty(C
));
735 case 16: return cast
<IntegerType
>(Type::getInt16Ty(C
));
736 case 32: return cast
<IntegerType
>(Type::getInt32Ty(C
));
737 case 64: return cast
<IntegerType
>(Type::getInt64Ty(C
));
742 LLVMContextImpl
*pImpl
= C
.pImpl
;
744 IntegerValType
IVT(NumBits
);
745 IntegerType
*ITy
= 0;
747 // First, see if the type is already in the table, for which
748 // a reader lock suffices.
749 sys::SmartScopedLock
<true> L(pImpl
->TypeMapLock
);
750 ITy
= pImpl
->IntegerTypes
.get(IVT
);
753 // Value not found. Derive a new type!
754 ITy
= new IntegerType(C
, NumBits
);
755 pImpl
->IntegerTypes
.add(IVT
, ITy
);
757 #ifdef DEBUG_MERGE_TYPES
758 DEBUG(errs() << "Derived new type: " << *ITy
<< "\n");
763 bool IntegerType::isPowerOf2ByteWidth() const {
764 unsigned BitWidth
= getBitWidth();
765 return (BitWidth
> 7) && isPowerOf2_32(BitWidth
);
768 APInt
IntegerType::getMask() const {
769 return APInt::getAllOnesValue(getBitWidth());
772 FunctionValType
FunctionValType::get(const FunctionType
*FT
) {
773 // Build up a FunctionValType
774 std::vector
<const Type
*> ParamTypes
;
775 ParamTypes
.reserve(FT
->getNumParams());
776 for (unsigned i
= 0, e
= FT
->getNumParams(); i
!= e
; ++i
)
777 ParamTypes
.push_back(FT
->getParamType(i
));
778 return FunctionValType(FT
->getReturnType(), ParamTypes
, FT
->isVarArg());
782 // FunctionType::get - The factory function for the FunctionType class...
783 FunctionType
*FunctionType::get(const Type
*ReturnType
,
784 const std::vector
<const Type
*> &Params
,
786 FunctionValType
VT(ReturnType
, Params
, isVarArg
);
787 FunctionType
*FT
= 0;
789 LLVMContextImpl
*pImpl
= ReturnType
->getContext().pImpl
;
791 sys::SmartScopedLock
<true> L(pImpl
->TypeMapLock
);
792 FT
= pImpl
->FunctionTypes
.get(VT
);
795 FT
= (FunctionType
*) operator new(sizeof(FunctionType
) +
796 sizeof(PATypeHandle
)*(Params
.size()+1));
797 new (FT
) FunctionType(ReturnType
, Params
, isVarArg
);
798 pImpl
->FunctionTypes
.add(VT
, FT
);
801 #ifdef DEBUG_MERGE_TYPES
802 DEBUG(errs() << "Derived new type: " << FT
<< "\n");
807 ArrayType
*ArrayType::get(const Type
*ElementType
, uint64_t NumElements
) {
808 assert(ElementType
&& "Can't get array of <null> types!");
809 assert(isValidElementType(ElementType
) && "Invalid type for array element!");
811 ArrayValType
AVT(ElementType
, NumElements
);
814 LLVMContextImpl
*pImpl
= ElementType
->getContext().pImpl
;
816 sys::SmartScopedLock
<true> L(pImpl
->TypeMapLock
);
817 AT
= pImpl
->ArrayTypes
.get(AVT
);
820 // Value not found. Derive a new type!
821 pImpl
->ArrayTypes
.add(AVT
, AT
= new ArrayType(ElementType
, NumElements
));
823 #ifdef DEBUG_MERGE_TYPES
824 DEBUG(errs() << "Derived new type: " << *AT
<< "\n");
829 bool ArrayType::isValidElementType(const Type
*ElemTy
) {
830 if (ElemTy
->getTypeID() == VoidTyID
|| ElemTy
->getTypeID() == LabelTyID
||
831 ElemTy
->getTypeID() == MetadataTyID
|| isa
<FunctionType
>(ElemTy
))
834 if (const PointerType
*PTy
= dyn_cast
<PointerType
>(ElemTy
))
835 if (PTy
->getElementType()->getTypeID() == MetadataTyID
)
841 VectorType
*VectorType::get(const Type
*ElementType
, unsigned NumElements
) {
842 assert(ElementType
&& "Can't get vector of <null> types!");
844 VectorValType
PVT(ElementType
, NumElements
);
847 LLVMContextImpl
*pImpl
= ElementType
->getContext().pImpl
;
849 sys::SmartScopedLock
<true> L(pImpl
->TypeMapLock
);
850 PT
= pImpl
->VectorTypes
.get(PVT
);
853 pImpl
->VectorTypes
.add(PVT
, PT
= new VectorType(ElementType
, NumElements
));
855 #ifdef DEBUG_MERGE_TYPES
856 DEBUG(errs() << "Derived new type: " << *PT
<< "\n");
861 bool VectorType::isValidElementType(const Type
*ElemTy
) {
862 if (ElemTy
->isInteger() || ElemTy
->isFloatingPoint() ||
863 isa
<OpaqueType
>(ElemTy
))
869 //===----------------------------------------------------------------------===//
870 // Struct Type Factory...
873 StructType
*StructType::get(LLVMContext
&Context
,
874 const std::vector
<const Type
*> &ETypes
,
876 StructValType
STV(ETypes
, isPacked
);
879 LLVMContextImpl
*pImpl
= Context
.pImpl
;
881 sys::SmartScopedLock
<true> L(pImpl
->TypeMapLock
);
882 ST
= pImpl
->StructTypes
.get(STV
);
885 // Value not found. Derive a new type!
886 ST
= (StructType
*) operator new(sizeof(StructType
) +
887 sizeof(PATypeHandle
) * ETypes
.size());
888 new (ST
) StructType(Context
, ETypes
, isPacked
);
889 pImpl
->StructTypes
.add(STV
, ST
);
891 #ifdef DEBUG_MERGE_TYPES
892 DEBUG(errs() << "Derived new type: " << *ST
<< "\n");
897 StructType
*StructType::get(LLVMContext
&Context
, const Type
*type
, ...) {
899 std::vector
<const llvm::Type
*> StructFields
;
902 StructFields
.push_back(type
);
903 type
= va_arg(ap
, llvm::Type
*);
905 return llvm::StructType::get(Context
, StructFields
);
908 bool StructType::isValidElementType(const Type
*ElemTy
) {
909 if (ElemTy
->getTypeID() == VoidTyID
|| ElemTy
->getTypeID() == LabelTyID
||
910 ElemTy
->getTypeID() == MetadataTyID
|| isa
<FunctionType
>(ElemTy
))
913 if (const PointerType
*PTy
= dyn_cast
<PointerType
>(ElemTy
))
914 if (PTy
->getElementType()->getTypeID() == MetadataTyID
)
921 //===----------------------------------------------------------------------===//
922 // Pointer Type Factory...
925 PointerType
*PointerType::get(const Type
*ValueType
, unsigned AddressSpace
) {
926 assert(ValueType
&& "Can't get a pointer to <null> type!");
927 assert(ValueType
->getTypeID() != VoidTyID
&&
928 "Pointer to void is not valid, use i8* instead!");
929 assert(isValidElementType(ValueType
) && "Invalid type for pointer element!");
930 PointerValType
PVT(ValueType
, AddressSpace
);
934 LLVMContextImpl
*pImpl
= ValueType
->getContext().pImpl
;
936 sys::SmartScopedLock
<true> L(pImpl
->TypeMapLock
);
937 PT
= pImpl
->PointerTypes
.get(PVT
);
940 // Value not found. Derive a new type!
941 pImpl
->PointerTypes
.add(PVT
, PT
= new PointerType(ValueType
, AddressSpace
));
943 #ifdef DEBUG_MERGE_TYPES
944 DEBUG(errs() << "Derived new type: " << *PT
<< "\n");
949 PointerType
*Type::getPointerTo(unsigned addrs
) const {
950 return PointerType::get(this, addrs
);
953 bool PointerType::isValidElementType(const Type
*ElemTy
) {
954 if (ElemTy
->getTypeID() == VoidTyID
||
955 ElemTy
->getTypeID() == LabelTyID
)
958 if (const PointerType
*PTy
= dyn_cast
<PointerType
>(ElemTy
))
959 if (PTy
->getElementType()->getTypeID() == MetadataTyID
)
966 //===----------------------------------------------------------------------===//
967 // Derived Type Refinement Functions
968 //===----------------------------------------------------------------------===//
970 // addAbstractTypeUser - Notify an abstract type that there is a new user of
971 // it. This function is called primarily by the PATypeHandle class.
972 void Type::addAbstractTypeUser(AbstractTypeUser
*U
) const {
973 assert(isAbstract() && "addAbstractTypeUser: Current type not abstract!");
974 LLVMContextImpl
*pImpl
= getContext().pImpl
;
975 pImpl
->AbstractTypeUsersLock
.acquire();
976 AbstractTypeUsers
.push_back(U
);
977 pImpl
->AbstractTypeUsersLock
.release();
981 // removeAbstractTypeUser - Notify an abstract type that a user of the class
982 // no longer has a handle to the type. This function is called primarily by
983 // the PATypeHandle class. When there are no users of the abstract type, it
984 // is annihilated, because there is no way to get a reference to it ever again.
986 void Type::removeAbstractTypeUser(AbstractTypeUser
*U
) const {
987 LLVMContextImpl
*pImpl
= getContext().pImpl
;
988 pImpl
->AbstractTypeUsersLock
.acquire();
990 // Search from back to front because we will notify users from back to
991 // front. Also, it is likely that there will be a stack like behavior to
992 // users that register and unregister users.
995 for (i
= AbstractTypeUsers
.size(); AbstractTypeUsers
[i
-1] != U
; --i
)
996 assert(i
!= 0 && "AbstractTypeUser not in user list!");
998 --i
; // Convert to be in range 0 <= i < size()
999 assert(i
< AbstractTypeUsers
.size() && "Index out of range!"); // Wraparound?
1001 AbstractTypeUsers
.erase(AbstractTypeUsers
.begin()+i
);
1003 #ifdef DEBUG_MERGE_TYPES
1004 DEBUG(errs() << " remAbstractTypeUser[" << (void*)this << ", "
1005 << *this << "][" << i
<< "] User = " << U
<< "\n");
1008 if (AbstractTypeUsers
.empty() && getRefCount() == 0 && isAbstract()) {
1009 #ifdef DEBUG_MERGE_TYPES
1010 DEBUG(errs() << "DELETEing unused abstract type: <" << *this
1011 << ">[" << (void*)this << "]" << "\n");
1017 pImpl
->AbstractTypeUsersLock
.release();
1020 // unlockedRefineAbstractTypeTo - This function is used when it is discovered
1021 // that the 'this' abstract type is actually equivalent to the NewType
1022 // specified. This causes all users of 'this' to switch to reference the more
1023 // concrete type NewType and for 'this' to be deleted. Only used for internal
1026 void DerivedType::unlockedRefineAbstractTypeTo(const Type
*NewType
) {
1027 assert(isAbstract() && "refineAbstractTypeTo: Current type is not abstract!");
1028 assert(this != NewType
&& "Can't refine to myself!");
1029 assert(ForwardType
== 0 && "This type has already been refined!");
1031 LLVMContextImpl
*pImpl
= getContext().pImpl
;
1033 // The descriptions may be out of date. Conservatively clear them all!
1034 pImpl
->AbstractTypeDescriptions
.clear();
1036 #ifdef DEBUG_MERGE_TYPES
1037 DEBUG(errs() << "REFINING abstract type [" << (void*)this << " "
1038 << *this << "] to [" << (void*)NewType
<< " "
1039 << *NewType
<< "]!\n");
1042 // Make sure to put the type to be refined to into a holder so that if IT gets
1043 // refined, that we will not continue using a dead reference...
1045 PATypeHolder
NewTy(NewType
);
1046 // Any PATypeHolders referring to this type will now automatically forward to
1047 // the type we are resolved to.
1048 ForwardType
= NewType
;
1049 if (NewType
->isAbstract())
1050 cast
<DerivedType
>(NewType
)->addRef();
1052 // Add a self use of the current type so that we don't delete ourself until
1053 // after the function exits.
1055 PATypeHolder
CurrentTy(this);
1057 // To make the situation simpler, we ask the subclass to remove this type from
1058 // the type map, and to replace any type uses with uses of non-abstract types.
1059 // This dramatically limits the amount of recursive type trouble we can find
1063 // Iterate over all of the uses of this type, invoking callback. Each user
1064 // should remove itself from our use list automatically. We have to check to
1065 // make sure that NewTy doesn't _become_ 'this'. If it does, resolving types
1066 // will not cause users to drop off of the use list. If we resolve to ourself
1069 pImpl
->AbstractTypeUsersLock
.acquire();
1070 while (!AbstractTypeUsers
.empty() && NewTy
!= this) {
1071 AbstractTypeUser
*User
= AbstractTypeUsers
.back();
1073 unsigned OldSize
= AbstractTypeUsers
.size(); OldSize
=OldSize
;
1074 #ifdef DEBUG_MERGE_TYPES
1075 DEBUG(errs() << " REFINING user " << OldSize
-1 << "[" << (void*)User
1076 << "] of abstract type [" << (void*)this << " "
1077 << *this << "] to [" << (void*)NewTy
.get() << " "
1078 << *NewTy
<< "]!\n");
1080 User
->refineAbstractType(this, NewTy
);
1082 assert(AbstractTypeUsers
.size() != OldSize
&&
1083 "AbsTyUser did not remove self from user list!");
1085 pImpl
->AbstractTypeUsersLock
.release();
1087 // If we were successful removing all users from the type, 'this' will be
1088 // deleted when the last PATypeHolder is destroyed or updated from this type.
1089 // This may occur on exit of this function, as the CurrentTy object is
1093 // refineAbstractTypeTo - This function is used by external callers to notify
1094 // us that this abstract type is equivalent to another type.
1096 void DerivedType::refineAbstractTypeTo(const Type
*NewType
) {
1097 // All recursive calls will go through unlockedRefineAbstractTypeTo,
1098 // to avoid deadlock problems.
1099 sys::SmartScopedLock
<true> L(NewType
->getContext().pImpl
->TypeMapLock
);
1100 unlockedRefineAbstractTypeTo(NewType
);
1103 // notifyUsesThatTypeBecameConcrete - Notify AbstractTypeUsers of this type that
1104 // the current type has transitioned from being abstract to being concrete.
1106 void DerivedType::notifyUsesThatTypeBecameConcrete() {
1107 #ifdef DEBUG_MERGE_TYPES
1108 DEBUG(errs() << "typeIsREFINED type: " << (void*)this << " " << *this <<"\n");
1111 LLVMContextImpl
*pImpl
= getContext().pImpl
;
1113 pImpl
->AbstractTypeUsersLock
.acquire();
1114 unsigned OldSize
= AbstractTypeUsers
.size(); OldSize
=OldSize
;
1115 while (!AbstractTypeUsers
.empty()) {
1116 AbstractTypeUser
*ATU
= AbstractTypeUsers
.back();
1117 ATU
->typeBecameConcrete(this);
1119 assert(AbstractTypeUsers
.size() < OldSize
-- &&
1120 "AbstractTypeUser did not remove itself from the use list!");
1122 pImpl
->AbstractTypeUsersLock
.release();
1125 // refineAbstractType - Called when a contained type is found to be more
1126 // concrete - this could potentially change us from an abstract type to a
1129 void FunctionType::refineAbstractType(const DerivedType
*OldType
,
1130 const Type
*NewType
) {
1131 LLVMContextImpl
*pImpl
= OldType
->getContext().pImpl
;
1132 pImpl
->FunctionTypes
.RefineAbstractType(this, OldType
, NewType
);
1135 void FunctionType::typeBecameConcrete(const DerivedType
*AbsTy
) {
1136 LLVMContextImpl
*pImpl
= AbsTy
->getContext().pImpl
;
1137 pImpl
->FunctionTypes
.TypeBecameConcrete(this, AbsTy
);
1141 // refineAbstractType - Called when a contained type is found to be more
1142 // concrete - this could potentially change us from an abstract type to a
1145 void ArrayType::refineAbstractType(const DerivedType
*OldType
,
1146 const Type
*NewType
) {
1147 LLVMContextImpl
*pImpl
= OldType
->getContext().pImpl
;
1148 pImpl
->ArrayTypes
.RefineAbstractType(this, OldType
, NewType
);
1151 void ArrayType::typeBecameConcrete(const DerivedType
*AbsTy
) {
1152 LLVMContextImpl
*pImpl
= AbsTy
->getContext().pImpl
;
1153 pImpl
->ArrayTypes
.TypeBecameConcrete(this, AbsTy
);
1156 // refineAbstractType - Called when a contained type is found to be more
1157 // concrete - this could potentially change us from an abstract type to a
1160 void VectorType::refineAbstractType(const DerivedType
*OldType
,
1161 const Type
*NewType
) {
1162 LLVMContextImpl
*pImpl
= OldType
->getContext().pImpl
;
1163 pImpl
->VectorTypes
.RefineAbstractType(this, OldType
, NewType
);
1166 void VectorType::typeBecameConcrete(const DerivedType
*AbsTy
) {
1167 LLVMContextImpl
*pImpl
= AbsTy
->getContext().pImpl
;
1168 pImpl
->VectorTypes
.TypeBecameConcrete(this, AbsTy
);
1171 // refineAbstractType - Called when a contained type is found to be more
1172 // concrete - this could potentially change us from an abstract type to a
1175 void StructType::refineAbstractType(const DerivedType
*OldType
,
1176 const Type
*NewType
) {
1177 LLVMContextImpl
*pImpl
= OldType
->getContext().pImpl
;
1178 pImpl
->StructTypes
.RefineAbstractType(this, OldType
, NewType
);
1181 void StructType::typeBecameConcrete(const DerivedType
*AbsTy
) {
1182 LLVMContextImpl
*pImpl
= AbsTy
->getContext().pImpl
;
1183 pImpl
->StructTypes
.TypeBecameConcrete(this, AbsTy
);
1186 // refineAbstractType - Called when a contained type is found to be more
1187 // concrete - this could potentially change us from an abstract type to a
1190 void PointerType::refineAbstractType(const DerivedType
*OldType
,
1191 const Type
*NewType
) {
1192 LLVMContextImpl
*pImpl
= OldType
->getContext().pImpl
;
1193 pImpl
->PointerTypes
.RefineAbstractType(this, OldType
, NewType
);
1196 void PointerType::typeBecameConcrete(const DerivedType
*AbsTy
) {
1197 LLVMContextImpl
*pImpl
= AbsTy
->getContext().pImpl
;
1198 pImpl
->PointerTypes
.TypeBecameConcrete(this, AbsTy
);
1201 bool SequentialType::indexValid(const Value
*V
) const {
1202 if (isa
<IntegerType
>(V
->getType()))
1208 raw_ostream
&operator<<(raw_ostream
&OS
, const Type
&T
) {