Don't populate TryAgainList when coalescing only physical registers with virtual...
[oota-llvm.git] / include / llvm / Type.h
1 //===-- llvm/Type.h - Classes for handling data types -----------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10
11 #ifndef LLVM_TYPE_H
12 #define LLVM_TYPE_H
13
14 #include "llvm/AbstractTypeUser.h"
15 #include "llvm/Support/Casting.h"
16 #include "llvm/Support/DataTypes.h"
17 #include "llvm/Support/Streams.h"
18 #include "llvm/ADT/GraphTraits.h"
19 #include "llvm/ADT/iterator"
20 #include <string>
21 #include <vector>
22
23 namespace llvm {
24
25 class DerivedType;
26 class PointerType;
27 class IntegerType;
28 class TypeMapBase;
29
30 /// This file contains the declaration of the Type class.  For more "Type" type
31 /// stuff, look in DerivedTypes.h.
32 ///
33 /// The instances of the Type class are immutable: once they are created,
34 /// they are never changed.  Also note that only one instance of a particular
35 /// type is ever created.  Thus seeing if two types are equal is a matter of
36 /// doing a trivial pointer comparison. To enforce that no two equal instances
37 /// are created, Type instances can only be created via static factory methods 
38 /// in class Type and in derived classes.
39 /// 
40 /// Once allocated, Types are never free'd, unless they are an abstract type
41 /// that is resolved to a more concrete type.
42 /// 
43 /// Types themself don't have a name, and can be named either by:
44 /// - using SymbolTable instance, typically from some Module,
45 /// - using convenience methods in the Module class (which uses module's 
46 ///    SymbolTable too).
47 ///
48 /// Opaque types are simple derived types with no state.  There may be many
49 /// different Opaque type objects floating around, but two are only considered
50 /// identical if they are pointer equals of each other.  This allows us to have
51 /// two opaque types that end up resolving to different concrete types later.
52 ///
53 /// Opaque types are also kinda weird and scary and different because they have
54 /// to keep a list of uses of the type.  When, through linking, parsing, or
55 /// bytecode reading, they become resolved, they need to find and update all
56 /// users of the unknown type, causing them to reference a new, more concrete
57 /// type.  Opaque types are deleted when their use list dwindles to zero users.
58 ///
59 /// @brief Root of type hierarchy
60 class Type : public AbstractTypeUser {
61 public:
62   //===-------------------------------------------------------------------===//
63   /// Definitions of all of the base types for the Type system.  Based on this
64   /// value, you can cast to a "DerivedType" subclass (see DerivedTypes.h)
65   /// Note: If you add an element to this, you need to add an element to the
66   /// Type::getPrimitiveType function, or else things will break!
67   ///
68   enum TypeID {
69     // PrimitiveTypes .. make sure LastPrimitiveTyID stays up to date
70     VoidTyID = 0,    ///<  0: type with no size
71     FloatTyID,       ///<  1: 32 bit floating point type
72     DoubleTyID,      ///<  2: 64 bit floating point type
73     LabelTyID,       ///<  3: Labels
74
75     // Derived types... see DerivedTypes.h file...
76     // Make sure FirstDerivedTyID stays up to date!!!
77     IntegerTyID,     ///<  4: Arbitrary bit width integers
78     FunctionTyID,    ///<  5: Functions
79     StructTyID,      ///<  6: Structures
80     PackedStructTyID,///<  7: Packed Structure. This is for bytecode only
81     ArrayTyID,       ///<  8: Arrays
82     PointerTyID,     ///<  9: Pointers
83     OpaqueTyID,      ///< 10: Opaque: type with unknown structure
84     VectorTyID,      ///< 11: SIMD 'packed' format, or other vector type
85
86     NumTypeIDs,                         // Must remain as last defined ID
87     LastPrimitiveTyID = LabelTyID,
88     FirstDerivedTyID = IntegerTyID
89   };
90
91 private:
92   TypeID   ID : 8;    // The current base type of this type.
93   bool     Abstract : 1;  // True if type contains an OpaqueType
94   unsigned SubclassData : 23; //Space for subclasses to store data
95
96   /// RefCount - This counts the number of PATypeHolders that are pointing to
97   /// this type.  When this number falls to zero, if the type is abstract and
98   /// has no AbstractTypeUsers, the type is deleted.  This is only sensical for
99   /// derived types.
100   ///
101   mutable unsigned RefCount;
102
103   const Type *getForwardedTypeInternal() const;
104
105   // Some Type instances are allocated as arrays, some aren't. So we provide
106   // this method to get the right kind of destruction for the type of Type.
107   void destroy() const; // const is a lie, this does "delete this"!
108
109 protected:
110   Type(const char *Name, TypeID id);
111   explicit Type(TypeID id) : ID(id), Abstract(false), SubclassData(0),
112                              RefCount(0), ForwardType(0), NumContainedTys(0),
113                              ContainedTys(0) {}
114   virtual ~Type() {
115     assert(AbstractTypeUsers.empty() && "Abstract types remain");
116   }
117
118   /// Types can become nonabstract later, if they are refined.
119   ///
120   inline void setAbstract(bool Val) { Abstract = Val; }
121
122   unsigned getRefCount() const { return RefCount; }
123
124   unsigned getSubclassData() const { return SubclassData; }
125   void setSubclassData(unsigned val) { SubclassData = val; }
126
127   /// ForwardType - This field is used to implement the union find scheme for
128   /// abstract types.  When types are refined to other types, this field is set
129   /// to the more refined type.  Only abstract types can be forwarded.
130   mutable const Type *ForwardType;
131
132
133   /// AbstractTypeUsers - Implement a list of the users that need to be notified
134   /// if I am a type, and I get resolved into a more concrete type.
135   ///
136   mutable std::vector<AbstractTypeUser *> AbstractTypeUsers;
137
138   /// NumContainedTys - Keeps track of how many PATypeHandle instances there
139   /// are at the end of this type instance for the list of contained types. It
140   /// is the subclasses responsibility to set this up. Set to 0 if there are no
141   /// contained types in this type.
142   unsigned NumContainedTys;
143
144   /// ContainedTys - A pointer to the array of Types (PATypeHandle) contained 
145   /// by this Type.  For example, this includes the arguments of a function 
146   /// type, the elements of a structure, the pointee of a pointer, the element
147   /// type of an array, etc.  This pointer may be 0 for types that don't 
148   /// contain other types (Integer, Double, Float).  In general, the subclass 
149   /// should arrange for space for the PATypeHandles to be included in the 
150   /// allocation of the type object and set this pointer to the address of the 
151   /// first element. This allows the Type class to manipulate the ContainedTys 
152   /// without understanding the subclass's placement for this array.  keeping 
153   /// it here also allows the subtype_* members to be implemented MUCH more 
154   /// efficiently, and dynamically very few types do not contain any elements.
155   PATypeHandle *ContainedTys;
156
157 public:
158   void print(std::ostream &O) const;
159   void print(std::ostream *O) const { if (O) print(*O); }
160
161   /// @brief Debugging support: print to stderr
162   void dump() const;
163
164   //===--------------------------------------------------------------------===//
165   // Property accessors for dealing with types... Some of these virtual methods
166   // are defined in private classes defined in Type.cpp for primitive types.
167   //
168
169   /// getTypeID - Return the type id for the type.  This will return one
170   /// of the TypeID enum elements defined above.
171   ///
172   inline TypeID getTypeID() const { return ID; }
173
174   /// getDescription - Return the string representation of the type...
175   const std::string &getDescription() const;
176
177   /// isInteger - True if this is an instance of IntegerType.
178   ///
179   bool isInteger() const { return ID == IntegerTyID; } 
180
181   /// isFloatingPoint - Return true if this is one of the two floating point
182   /// types
183   bool isFloatingPoint() const { return ID == FloatTyID || ID == DoubleTyID; }
184
185   /// isFPOrFPVector - Return true if this is a FP type or a vector of FP types.
186   ///
187   bool isFPOrFPVector() const;
188   
189   /// isAbstract - True if the type is either an Opaque type, or is a derived
190   /// type that includes an opaque type somewhere in it.
191   ///
192   inline bool isAbstract() const { return Abstract; }
193
194   /// canLosslesslyBitCastTo - Return true if this type could be converted 
195   /// with a lossless BitCast to type 'Ty'. For example, uint to int. BitCasts 
196   /// are valid for types of the same size only where no re-interpretation of 
197   /// the bits is done.
198   /// @brief Determine if this type could be losslessly bitcast to Ty
199   bool canLosslesslyBitCastTo(const Type *Ty) const;
200
201
202   /// Here are some useful little methods to query what type derived types are
203   /// Note that all other types can just compare to see if this == Type::xxxTy;
204   ///
205   inline bool isPrimitiveType() const { return ID <= LastPrimitiveTyID; }
206   inline bool isDerivedType()   const { return ID >= FirstDerivedTyID; }
207
208   /// isFirstClassType - Return true if the value is holdable in a register.
209   ///
210   inline bool isFirstClassType() const {
211     return (ID != VoidTyID && ID <= LastPrimitiveTyID) ||
212             ID == IntegerTyID || ID == PointerTyID || ID == VectorTyID;
213   }
214
215   /// isSized - Return true if it makes sense to take the size of this type.  To
216   /// get the actual size for a particular target, it is reasonable to use the
217   /// TargetData subsystem to do this.
218   ///
219   bool isSized() const {
220     // If it's a primitive, it is always sized.
221     if (ID == IntegerTyID || isFloatingPoint() || ID == PointerTyID)
222       return true;
223     // If it is not something that can have a size (e.g. a function or label),
224     // it doesn't have a size.
225     if (ID != StructTyID && ID != ArrayTyID && ID != VectorTyID &&
226         ID != PackedStructTyID)
227       return false;
228     // If it is something that can have a size and it's concrete, it definitely
229     // has a size, otherwise we have to try harder to decide.
230     return !isAbstract() || isSizedDerivedType();
231   }
232
233   /// getPrimitiveSize - Return the basic size of this type if it is a primitive
234   /// type.  These are fixed by LLVM and are not target dependent.  This will
235   /// return zero if the type does not have a size or is not a primitive type.
236   ///
237   unsigned getPrimitiveSizeInBits() const;
238
239   /// getForwaredType - Return the type that this type has been resolved to if
240   /// it has been resolved to anything.  This is used to implement the
241   /// union-find algorithm for type resolution, and shouldn't be used by general
242   /// purpose clients.
243   const Type *getForwardedType() const {
244     if (!ForwardType) return 0;
245     return getForwardedTypeInternal();
246   }
247
248   /// getVAArgsPromotedType - Return the type an argument of this type
249   /// will be promoted to if passed through a variable argument
250   /// function.
251   const Type *getVAArgsPromotedType() const; 
252
253   //===--------------------------------------------------------------------===//
254   // Type Iteration support
255   //
256   typedef PATypeHandle *subtype_iterator;
257   subtype_iterator subtype_begin() const { return ContainedTys; }
258   subtype_iterator subtype_end() const { return &ContainedTys[NumContainedTys];}
259
260   /// getContainedType - This method is used to implement the type iterator
261   /// (defined a the end of the file).  For derived types, this returns the
262   /// types 'contained' in the derived type.
263   ///
264   const Type *getContainedType(unsigned i) const {
265     assert(i < NumContainedTys && "Index out of range!");
266     return ContainedTys[i].get();
267   }
268
269   /// getNumContainedTypes - Return the number of types in the derived type.
270   ///
271   unsigned getNumContainedTypes() const { return NumContainedTys; }
272
273   //===--------------------------------------------------------------------===//
274   // Static members exported by the Type class itself.  Useful for getting
275   // instances of Type.
276   //
277
278   /// getPrimitiveType - Return a type based on an identifier.
279   static const Type *getPrimitiveType(TypeID IDNumber);
280
281   //===--------------------------------------------------------------------===//
282   // These are the builtin types that are always available...
283   //
284   static const Type *VoidTy, *LabelTy, *FloatTy, *DoubleTy;
285   static const IntegerType *Int1Ty, *Int8Ty, *Int16Ty, *Int32Ty, *Int64Ty;
286
287   /// Methods for support type inquiry through isa, cast, and dyn_cast:
288   static inline bool classof(const Type *T) { return true; }
289
290   void addRef() const {
291     assert(isAbstract() && "Cannot add a reference to a non-abstract type!");
292     ++RefCount;
293   }
294
295   void dropRef() const {
296     assert(isAbstract() && "Cannot drop a reference to a non-abstract type!");
297     assert(RefCount && "No objects are currently referencing this object!");
298
299     // If this is the last PATypeHolder using this object, and there are no
300     // PATypeHandles using it, the type is dead, delete it now.
301     if (--RefCount == 0 && AbstractTypeUsers.empty())
302       this->destroy();
303   }
304   
305   /// addAbstractTypeUser - Notify an abstract type that there is a new user of
306   /// it.  This function is called primarily by the PATypeHandle class.
307   ///
308   void addAbstractTypeUser(AbstractTypeUser *U) const {
309     assert(isAbstract() && "addAbstractTypeUser: Current type not abstract!");
310     AbstractTypeUsers.push_back(U);
311   }
312   
313   /// removeAbstractTypeUser - Notify an abstract type that a user of the class
314   /// no longer has a handle to the type.  This function is called primarily by
315   /// the PATypeHandle class.  When there are no users of the abstract type, it
316   /// is annihilated, because there is no way to get a reference to it ever
317   /// again.
318   ///
319   void removeAbstractTypeUser(AbstractTypeUser *U) const;
320
321 private:
322   /// isSizedDerivedType - Derived types like structures and arrays are sized
323   /// iff all of the members of the type are sized as well.  Since asking for
324   /// their size is relatively uncommon, move this operation out of line.
325   bool isSizedDerivedType() const;
326
327   virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy);
328   virtual void typeBecameConcrete(const DerivedType *AbsTy);
329
330 protected:
331   // PromoteAbstractToConcrete - This is an internal method used to calculate
332   // change "Abstract" from true to false when types are refined.
333   void PromoteAbstractToConcrete();
334   friend class TypeMapBase;
335 };
336
337 //===----------------------------------------------------------------------===//
338 // Define some inline methods for the AbstractTypeUser.h:PATypeHandle class.
339 // These are defined here because they MUST be inlined, yet are dependent on
340 // the definition of the Type class.
341 //
342 inline void PATypeHandle::addUser() {
343   assert(Ty && "Type Handle has a null type!");
344   if (Ty->isAbstract())
345     Ty->addAbstractTypeUser(User);
346 }
347 inline void PATypeHandle::removeUser() {
348   if (Ty->isAbstract())
349     Ty->removeAbstractTypeUser(User);
350 }
351
352 // Define inline methods for PATypeHolder...
353
354 inline void PATypeHolder::addRef() {
355   if (Ty->isAbstract())
356     Ty->addRef();
357 }
358
359 inline void PATypeHolder::dropRef() {
360   if (Ty->isAbstract())
361     Ty->dropRef();
362 }
363
364
365 //===----------------------------------------------------------------------===//
366 // Provide specializations of GraphTraits to be able to treat a type as a
367 // graph of sub types...
368
369 template <> struct GraphTraits<Type*> {
370   typedef Type NodeType;
371   typedef Type::subtype_iterator ChildIteratorType;
372
373   static inline NodeType *getEntryNode(Type *T) { return T; }
374   static inline ChildIteratorType child_begin(NodeType *N) {
375     return N->subtype_begin();
376   }
377   static inline ChildIteratorType child_end(NodeType *N) {
378     return N->subtype_end();
379   }
380 };
381
382 template <> struct GraphTraits<const Type*> {
383   typedef const Type NodeType;
384   typedef Type::subtype_iterator ChildIteratorType;
385
386   static inline NodeType *getEntryNode(const Type *T) { return T; }
387   static inline ChildIteratorType child_begin(NodeType *N) {
388     return N->subtype_begin();
389   }
390   static inline ChildIteratorType child_end(NodeType *N) {
391     return N->subtype_end();
392   }
393 };
394
395 template <> inline bool isa_impl<PointerType, Type>(const Type &Ty) {
396   return Ty.getTypeID() == Type::PointerTyID;
397 }
398
399 std::ostream &operator<<(std::ostream &OS, const Type &T);
400
401 } // End llvm namespace
402
403 #endif