Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 1 | //===-- Type.cpp - Implement the Type class -------------------------------===// |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame^] | 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 | //===----------------------------------------------------------------------===// |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 9 | // |
| 10 | // This file implements the Type class for the VMCore library. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #include "llvm/DerivedTypes.h" |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 15 | #include "llvm/SymbolTable.h" |
Chris Lattner | 31bcdb8 | 2002-04-28 19:55:58 +0000 | [diff] [blame] | 16 | #include "llvm/Constants.h" |
Chris Lattner | cee8f9a | 2001-11-27 00:03:19 +0000 | [diff] [blame] | 17 | #include "Support/StringExtras.h" |
| 18 | #include "Support/STLExtras.h" |
Chris Lattner | 417081c | 2002-04-07 06:14:56 +0000 | [diff] [blame] | 19 | #include <algorithm> |
Chris Lattner | 697954c | 2002-01-20 22:54:45 +0000 | [diff] [blame] | 20 | |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 21 | // DEBUG_MERGE_TYPES - Enable this #define to see how and when derived types are |
| 22 | // created and later destroyed, all in an effort to make sure that there is only |
Chris Lattner | 065a616 | 2003-09-10 05:29:43 +0000 | [diff] [blame] | 23 | // a single canonical version of a type. |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 24 | // |
| 25 | //#define DEBUG_MERGE_TYPES 1 |
| 26 | |
| 27 | |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 28 | //===----------------------------------------------------------------------===// |
| 29 | // Type Class Implementation |
| 30 | //===----------------------------------------------------------------------===// |
| 31 | |
| 32 | static unsigned CurUID = 0; |
Chris Lattner | 47697a1 | 2003-05-22 21:21:43 +0000 | [diff] [blame] | 33 | static std::vector<const Type *> UIDMappings; |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 34 | |
Chris Lattner | dd4b421 | 2003-09-02 16:35:17 +0000 | [diff] [blame] | 35 | // Concrete/Abstract TypeDescriptions - We lazily calculate type descriptions |
| 36 | // for types as they are needed. Because resolution of types must invalidate |
| 37 | // all of the abstract type descriptions, we keep them in a seperate map to make |
| 38 | // this easy. |
| 39 | static std::map<const Type*, std::string> ConcreteTypeDescriptions; |
| 40 | static std::map<const Type*, std::string> AbstractTypeDescriptions; |
| 41 | |
Chris Lattner | 47697a1 | 2003-05-22 21:21:43 +0000 | [diff] [blame] | 42 | Type::Type(const std::string &name, PrimitiveID id) |
Chris Lattner | 1c5164e | 2003-10-02 23:35:57 +0000 | [diff] [blame] | 43 | : Value(Type::TypeTy, Value::TypeVal), ForwardType(0) { |
Chris Lattner | d8d6c76 | 2003-09-02 22:50:02 +0000 | [diff] [blame] | 44 | if (!name.empty()) |
| 45 | ConcreteTypeDescriptions[this] = name; |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 46 | ID = id; |
Chris Lattner | 87ca5fa | 2003-09-02 21:41:05 +0000 | [diff] [blame] | 47 | Abstract = false; |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 48 | UID = CurUID++; // Assign types UID's as they are created |
| 49 | UIDMappings.push_back(this); |
| 50 | } |
| 51 | |
Chris Lattner | 47697a1 | 2003-05-22 21:21:43 +0000 | [diff] [blame] | 52 | void Type::setName(const std::string &Name, SymbolTable *ST) { |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 53 | assert(ST && "Type::setName - Must provide symbol table argument!"); |
| 54 | |
| 55 | if (Name.size()) ST->insert(Name, this); |
| 56 | } |
| 57 | |
| 58 | |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 59 | const Type *Type::getUniqueIDType(unsigned UID) { |
| 60 | assert(UID < UIDMappings.size() && |
| 61 | "Type::getPrimitiveType: UID out of range!"); |
| 62 | return UIDMappings[UID]; |
| 63 | } |
| 64 | |
| 65 | const Type *Type::getPrimitiveType(PrimitiveID IDNumber) { |
| 66 | switch (IDNumber) { |
| 67 | case VoidTyID : return VoidTy; |
| 68 | case BoolTyID : return BoolTy; |
| 69 | case UByteTyID : return UByteTy; |
| 70 | case SByteTyID : return SByteTy; |
| 71 | case UShortTyID: return UShortTy; |
| 72 | case ShortTyID : return ShortTy; |
| 73 | case UIntTyID : return UIntTy; |
| 74 | case IntTyID : return IntTy; |
| 75 | case ULongTyID : return ULongTy; |
| 76 | case LongTyID : return LongTy; |
| 77 | case FloatTyID : return FloatTy; |
| 78 | case DoubleTyID: return DoubleTy; |
| 79 | case TypeTyID : return TypeTy; |
| 80 | case LabelTyID : return LabelTy; |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 81 | default: |
| 82 | return 0; |
| 83 | } |
| 84 | } |
| 85 | |
Misha Brukman | f117cc9 | 2003-05-20 18:45:36 +0000 | [diff] [blame] | 86 | // isLosslesslyConvertibleTo - Return true if this type can be converted to |
Chris Lattner | 58716b9 | 2001-11-26 17:01:47 +0000 | [diff] [blame] | 87 | // 'Ty' without any reinterpretation of bits. For example, uint to int. |
| 88 | // |
Misha Brukman | f117cc9 | 2003-05-20 18:45:36 +0000 | [diff] [blame] | 89 | bool Type::isLosslesslyConvertibleTo(const Type *Ty) const { |
Chris Lattner | 58716b9 | 2001-11-26 17:01:47 +0000 | [diff] [blame] | 90 | if (this == Ty) return true; |
Chris Lattner | d44023e | 2002-05-06 16:14:39 +0000 | [diff] [blame] | 91 | if ((!isPrimitiveType() && !isa<PointerType>(this)) || |
| 92 | (!isa<PointerType>(Ty) && !Ty->isPrimitiveType())) return false; |
Chris Lattner | 58716b9 | 2001-11-26 17:01:47 +0000 | [diff] [blame] | 93 | |
| 94 | if (getPrimitiveID() == Ty->getPrimitiveID()) |
| 95 | return true; // Handles identity cast, and cast of differing pointer types |
| 96 | |
| 97 | // Now we know that they are two differing primitive or pointer types |
| 98 | switch (getPrimitiveID()) { |
| 99 | case Type::UByteTyID: return Ty == Type::SByteTy; |
| 100 | case Type::SByteTyID: return Ty == Type::UByteTy; |
| 101 | case Type::UShortTyID: return Ty == Type::ShortTy; |
| 102 | case Type::ShortTyID: return Ty == Type::UShortTy; |
| 103 | case Type::UIntTyID: return Ty == Type::IntTy; |
| 104 | case Type::IntTyID: return Ty == Type::UIntTy; |
| 105 | case Type::ULongTyID: |
| 106 | case Type::LongTyID: |
| 107 | case Type::PointerTyID: |
Chris Lattner | c72114c | 2002-04-27 02:26:03 +0000 | [diff] [blame] | 108 | return Ty == Type::ULongTy || Ty == Type::LongTy || isa<PointerType>(Ty); |
Chris Lattner | 58716b9 | 2001-11-26 17:01:47 +0000 | [diff] [blame] | 109 | default: |
| 110 | return false; // Other types have no identity values |
| 111 | } |
| 112 | } |
| 113 | |
Misha Brukman | 6b63452 | 2003-10-10 17:54:14 +0000 | [diff] [blame] | 114 | // getPrimitiveSize - Return the basic size of this type if it is a primitive |
Misha Brukman | ef6a6a6 | 2003-08-21 22:14:26 +0000 | [diff] [blame] | 115 | // type. These are fixed by LLVM and are not target dependent. This will |
Chris Lattner | d44023e | 2002-05-06 16:14:39 +0000 | [diff] [blame] | 116 | // return zero if the type does not have a size or is not a primitive type. |
| 117 | // |
| 118 | unsigned Type::getPrimitiveSize() const { |
| 119 | switch (getPrimitiveID()) { |
| 120 | #define HANDLE_PRIM_TYPE(TY,SIZE) case TY##TyID: return SIZE; |
| 121 | #include "llvm/Type.def" |
| 122 | default: return 0; |
| 123 | } |
| 124 | } |
| 125 | |
Chris Lattner | 58716b9 | 2001-11-26 17:01:47 +0000 | [diff] [blame] | 126 | |
Chris Lattner | 1c5164e | 2003-10-02 23:35:57 +0000 | [diff] [blame] | 127 | /// getForwardedTypeInternal - This method is used to implement the union-find |
| 128 | /// algorithm for when a type is being forwarded to another type. |
| 129 | const Type *Type::getForwardedTypeInternal() const { |
| 130 | assert(ForwardType && "This type is not being forwarded to another type!"); |
| 131 | |
| 132 | // Check to see if the forwarded type has been forwarded on. If so, collapse |
| 133 | // the forwarding links. |
| 134 | const Type *RealForwardedType = ForwardType->getForwardedType(); |
| 135 | if (!RealForwardedType) |
| 136 | return ForwardType; // No it's not forwarded again |
| 137 | |
| 138 | // Yes, it is forwarded again. First thing, add the reference to the new |
| 139 | // forward type. |
| 140 | if (RealForwardedType->isAbstract()) |
| 141 | cast<DerivedType>(RealForwardedType)->addRef(); |
| 142 | |
| 143 | // Now drop the old reference. This could cause ForwardType to get deleted. |
| 144 | cast<DerivedType>(ForwardType)->dropRef(); |
| 145 | |
| 146 | // Return the updated type. |
| 147 | ForwardType = RealForwardedType; |
| 148 | return ForwardType; |
| 149 | } |
| 150 | |
Chris Lattner | dd4b421 | 2003-09-02 16:35:17 +0000 | [diff] [blame] | 151 | // getTypeDescription - This is a recursive function that walks a type hierarchy |
| 152 | // calculating the description for a type. |
| 153 | // |
| 154 | static std::string getTypeDescription(const Type *Ty, |
| 155 | std::vector<const Type *> &TypeStack) { |
| 156 | if (isa<OpaqueType>(Ty)) { // Base case for the recursion |
| 157 | std::map<const Type*, std::string>::iterator I = |
| 158 | AbstractTypeDescriptions.lower_bound(Ty); |
| 159 | if (I != AbstractTypeDescriptions.end() && I->first == Ty) |
| 160 | return I->second; |
| 161 | std::string Desc = "opaque"+utostr(Ty->getUniqueID()); |
| 162 | AbstractTypeDescriptions.insert(std::make_pair(Ty, Desc)); |
| 163 | return Desc; |
| 164 | } |
| 165 | |
Chris Lattner | 87ca5fa | 2003-09-02 21:41:05 +0000 | [diff] [blame] | 166 | if (!Ty->isAbstract()) { // Base case for the recursion |
Chris Lattner | dd4b421 | 2003-09-02 16:35:17 +0000 | [diff] [blame] | 167 | std::map<const Type*, std::string>::iterator I = |
| 168 | ConcreteTypeDescriptions.find(Ty); |
| 169 | if (I != ConcreteTypeDescriptions.end()) return I->second; |
| 170 | } |
| 171 | |
| 172 | // Check to see if the Type is already on the stack... |
| 173 | unsigned Slot = 0, CurSize = TypeStack.size(); |
| 174 | while (Slot < CurSize && TypeStack[Slot] != Ty) ++Slot; // Scan for type |
| 175 | |
| 176 | // This is another base case for the recursion. In this case, we know |
| 177 | // that we have looped back to a type that we have previously visited. |
| 178 | // Generate the appropriate upreference to handle this. |
| 179 | // |
| 180 | if (Slot < CurSize) |
| 181 | return "\\" + utostr(CurSize-Slot); // Here's the upreference |
| 182 | |
| 183 | // Recursive case: derived types... |
| 184 | std::string Result; |
| 185 | TypeStack.push_back(Ty); // Add us to the stack.. |
| 186 | |
| 187 | switch (Ty->getPrimitiveID()) { |
| 188 | case Type::FunctionTyID: { |
| 189 | const FunctionType *FTy = cast<FunctionType>(Ty); |
| 190 | Result = getTypeDescription(FTy->getReturnType(), TypeStack) + " ("; |
| 191 | for (FunctionType::ParamTypes::const_iterator |
| 192 | I = FTy->getParamTypes().begin(), |
| 193 | E = FTy->getParamTypes().end(); I != E; ++I) { |
| 194 | if (I != FTy->getParamTypes().begin()) |
| 195 | Result += ", "; |
| 196 | Result += getTypeDescription(*I, TypeStack); |
| 197 | } |
| 198 | if (FTy->isVarArg()) { |
| 199 | if (!FTy->getParamTypes().empty()) Result += ", "; |
| 200 | Result += "..."; |
| 201 | } |
| 202 | Result += ")"; |
| 203 | break; |
| 204 | } |
| 205 | case Type::StructTyID: { |
| 206 | const StructType *STy = cast<StructType>(Ty); |
| 207 | Result = "{ "; |
| 208 | for (StructType::ElementTypes::const_iterator |
| 209 | I = STy->getElementTypes().begin(), |
| 210 | E = STy->getElementTypes().end(); I != E; ++I) { |
| 211 | if (I != STy->getElementTypes().begin()) |
| 212 | Result += ", "; |
| 213 | Result += getTypeDescription(*I, TypeStack); |
| 214 | } |
| 215 | Result += " }"; |
| 216 | break; |
| 217 | } |
| 218 | case Type::PointerTyID: { |
| 219 | const PointerType *PTy = cast<PointerType>(Ty); |
| 220 | Result = getTypeDescription(PTy->getElementType(), TypeStack) + " *"; |
| 221 | break; |
| 222 | } |
| 223 | case Type::ArrayTyID: { |
| 224 | const ArrayType *ATy = cast<ArrayType>(Ty); |
| 225 | unsigned NumElements = ATy->getNumElements(); |
| 226 | Result = "["; |
| 227 | Result += utostr(NumElements) + " x "; |
| 228 | Result += getTypeDescription(ATy->getElementType(), TypeStack) + "]"; |
| 229 | break; |
| 230 | } |
| 231 | default: |
Chris Lattner | dd4b421 | 2003-09-02 16:35:17 +0000 | [diff] [blame] | 232 | Result = "<error>"; |
Chris Lattner | d8d6c76 | 2003-09-02 22:50:02 +0000 | [diff] [blame] | 233 | assert(0 && "Unhandled type in getTypeDescription!"); |
Chris Lattner | dd4b421 | 2003-09-02 16:35:17 +0000 | [diff] [blame] | 234 | } |
| 235 | |
| 236 | TypeStack.pop_back(); // Remove self from stack... |
| 237 | |
Chris Lattner | a3057e8 | 2003-09-04 23:41:03 +0000 | [diff] [blame] | 238 | return Result; |
Chris Lattner | dd4b421 | 2003-09-02 16:35:17 +0000 | [diff] [blame] | 239 | } |
| 240 | |
| 241 | |
| 242 | |
| 243 | static const std::string &getOrCreateDesc(std::map<const Type*,std::string>&Map, |
| 244 | const Type *Ty) { |
| 245 | std::map<const Type*, std::string>::iterator I = Map.find(Ty); |
| 246 | if (I != Map.end()) return I->second; |
| 247 | |
| 248 | std::vector<const Type *> TypeStack; |
Chris Lattner | a3057e8 | 2003-09-04 23:41:03 +0000 | [diff] [blame] | 249 | return Map[Ty] = getTypeDescription(Ty, TypeStack); |
Chris Lattner | dd4b421 | 2003-09-02 16:35:17 +0000 | [diff] [blame] | 250 | } |
| 251 | |
| 252 | |
| 253 | const std::string &Type::getDescription() const { |
| 254 | if (isAbstract()) |
| 255 | return getOrCreateDesc(AbstractTypeDescriptions, this); |
| 256 | else |
| 257 | return getOrCreateDesc(ConcreteTypeDescriptions, this); |
| 258 | } |
| 259 | |
| 260 | |
Chris Lattner | 58716b9 | 2001-11-26 17:01:47 +0000 | [diff] [blame] | 261 | bool StructType::indexValid(const Value *V) const { |
Chris Lattner | e9bb2df | 2001-12-03 22:26:30 +0000 | [diff] [blame] | 262 | if (!isa<Constant>(V)) return false; |
Chris Lattner | 58716b9 | 2001-11-26 17:01:47 +0000 | [diff] [blame] | 263 | if (V->getType() != Type::UByteTy) return false; |
Chris Lattner | e9bb2df | 2001-12-03 22:26:30 +0000 | [diff] [blame] | 264 | unsigned Idx = cast<ConstantUInt>(V)->getValue(); |
Chris Lattner | 58716b9 | 2001-11-26 17:01:47 +0000 | [diff] [blame] | 265 | return Idx < ETypes.size(); |
| 266 | } |
| 267 | |
| 268 | // getTypeAtIndex - Given an index value into the type, return the type of the |
| 269 | // element. For a structure type, this must be a constant value... |
| 270 | // |
| 271 | const Type *StructType::getTypeAtIndex(const Value *V) const { |
Chris Lattner | e9bb2df | 2001-12-03 22:26:30 +0000 | [diff] [blame] | 272 | assert(isa<Constant>(V) && "Structure index must be a constant!!"); |
Chris Lattner | 58716b9 | 2001-11-26 17:01:47 +0000 | [diff] [blame] | 273 | assert(V->getType() == Type::UByteTy && "Structure index must be ubyte!"); |
Chris Lattner | e9bb2df | 2001-12-03 22:26:30 +0000 | [diff] [blame] | 274 | unsigned Idx = cast<ConstantUInt>(V)->getValue(); |
Chris Lattner | 58716b9 | 2001-11-26 17:01:47 +0000 | [diff] [blame] | 275 | assert(Idx < ETypes.size() && "Structure index out of range!"); |
| 276 | assert(indexValid(V) && "Invalid structure index!"); // Duplicate check |
| 277 | |
| 278 | return ETypes[Idx]; |
| 279 | } |
| 280 | |
| 281 | |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 282 | //===----------------------------------------------------------------------===// |
Misha Brukman | 6b63452 | 2003-10-10 17:54:14 +0000 | [diff] [blame] | 283 | // Auxiliary classes |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 284 | //===----------------------------------------------------------------------===// |
| 285 | // |
| 286 | // These classes are used to implement specialized behavior for each different |
| 287 | // type. |
| 288 | // |
Chris Lattner | 0c4e886 | 2002-09-03 01:08:28 +0000 | [diff] [blame] | 289 | struct SignedIntType : public Type { |
Chris Lattner | 47697a1 | 2003-05-22 21:21:43 +0000 | [diff] [blame] | 290 | SignedIntType(const std::string &Name, PrimitiveID id) : Type(Name, id) {} |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 291 | |
| 292 | // isSigned - Return whether a numeric type is signed. |
| 293 | virtual bool isSigned() const { return 1; } |
Chris Lattner | 1a2cefc | 2001-07-21 19:15:26 +0000 | [diff] [blame] | 294 | |
Chris Lattner | 0c4e886 | 2002-09-03 01:08:28 +0000 | [diff] [blame] | 295 | // isInteger - Equivalent to isSigned() || isUnsigned, but with only a single |
Chris Lattner | 1a2cefc | 2001-07-21 19:15:26 +0000 | [diff] [blame] | 296 | // virtual function invocation. |
| 297 | // |
Chris Lattner | 0c4e886 | 2002-09-03 01:08:28 +0000 | [diff] [blame] | 298 | virtual bool isInteger() const { return 1; } |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 299 | }; |
| 300 | |
Chris Lattner | 0c4e886 | 2002-09-03 01:08:28 +0000 | [diff] [blame] | 301 | struct UnsignedIntType : public Type { |
Chris Lattner | 47697a1 | 2003-05-22 21:21:43 +0000 | [diff] [blame] | 302 | UnsignedIntType(const std::string &N, PrimitiveID id) : Type(N, id) {} |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 303 | |
| 304 | // isUnsigned - Return whether a numeric type is signed. |
| 305 | virtual bool isUnsigned() const { return 1; } |
Chris Lattner | 1a2cefc | 2001-07-21 19:15:26 +0000 | [diff] [blame] | 306 | |
Chris Lattner | 0c4e886 | 2002-09-03 01:08:28 +0000 | [diff] [blame] | 307 | // isInteger - Equivalent to isSigned() || isUnsigned, but with only a single |
Chris Lattner | 1a2cefc | 2001-07-21 19:15:26 +0000 | [diff] [blame] | 308 | // virtual function invocation. |
| 309 | // |
Chris Lattner | 0c4e886 | 2002-09-03 01:08:28 +0000 | [diff] [blame] | 310 | virtual bool isInteger() const { return 1; } |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 311 | }; |
| 312 | |
Chris Lattner | 950273b | 2003-05-22 21:31:52 +0000 | [diff] [blame] | 313 | struct OtherType : public Type { |
| 314 | OtherType(const std::string &N, PrimitiveID id) : Type(N, id) {} |
| 315 | }; |
| 316 | |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 317 | static struct TypeType : public Type { |
| 318 | TypeType() : Type("type", TypeTyID) {} |
Chris Lattner | 950273b | 2003-05-22 21:31:52 +0000 | [diff] [blame] | 319 | } TheTypeTy; // Implement the type that is global. |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 320 | |
| 321 | |
| 322 | //===----------------------------------------------------------------------===// |
| 323 | // Static 'Type' data |
| 324 | //===----------------------------------------------------------------------===// |
| 325 | |
Chris Lattner | 950273b | 2003-05-22 21:31:52 +0000 | [diff] [blame] | 326 | static OtherType TheVoidTy ("void" , Type::VoidTyID); |
| 327 | static OtherType TheBoolTy ("bool" , Type::BoolTyID); |
| 328 | static SignedIntType TheSByteTy ("sbyte" , Type::SByteTyID); |
| 329 | static UnsignedIntType TheUByteTy ("ubyte" , Type::UByteTyID); |
| 330 | static SignedIntType TheShortTy ("short" , Type::ShortTyID); |
| 331 | static UnsignedIntType TheUShortTy("ushort", Type::UShortTyID); |
| 332 | static SignedIntType TheIntTy ("int" , Type::IntTyID); |
| 333 | static UnsignedIntType TheUIntTy ("uint" , Type::UIntTyID); |
| 334 | static SignedIntType TheLongTy ("long" , Type::LongTyID); |
| 335 | static UnsignedIntType TheULongTy ("ulong" , Type::ULongTyID); |
| 336 | static OtherType TheFloatTy ("float" , Type::FloatTyID); |
| 337 | static OtherType TheDoubleTy("double", Type::DoubleTyID); |
| 338 | static OtherType TheLabelTy ("label" , Type::LabelTyID); |
| 339 | |
| 340 | Type *Type::VoidTy = &TheVoidTy; |
| 341 | Type *Type::BoolTy = &TheBoolTy; |
| 342 | Type *Type::SByteTy = &TheSByteTy; |
| 343 | Type *Type::UByteTy = &TheUByteTy; |
| 344 | Type *Type::ShortTy = &TheShortTy; |
| 345 | Type *Type::UShortTy = &TheUShortTy; |
| 346 | Type *Type::IntTy = &TheIntTy; |
| 347 | Type *Type::UIntTy = &TheUIntTy; |
| 348 | Type *Type::LongTy = &TheLongTy; |
| 349 | Type *Type::ULongTy = &TheULongTy; |
| 350 | Type *Type::FloatTy = &TheFloatTy; |
| 351 | Type *Type::DoubleTy = &TheDoubleTy; |
| 352 | Type *Type::TypeTy = &TheTypeTy; |
| 353 | Type *Type::LabelTy = &TheLabelTy; |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 354 | |
| 355 | |
| 356 | //===----------------------------------------------------------------------===// |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 357 | // Derived Type Constructors |
| 358 | //===----------------------------------------------------------------------===// |
| 359 | |
Chris Lattner | 6bfd6a5 | 2002-03-29 03:44:36 +0000 | [diff] [blame] | 360 | FunctionType::FunctionType(const Type *Result, |
Chris Lattner | 47697a1 | 2003-05-22 21:21:43 +0000 | [diff] [blame] | 361 | const std::vector<const Type*> &Params, |
Chris Lattner | 6bfd6a5 | 2002-03-29 03:44:36 +0000 | [diff] [blame] | 362 | bool IsVarArgs) : DerivedType(FunctionTyID), |
Chris Lattner | 893f025 | 2003-06-18 19:22:36 +0000 | [diff] [blame] | 363 | ResultType(PATypeHandle(Result, this)), |
Chris Lattner | e5a57ee | 2001-07-25 22:47:55 +0000 | [diff] [blame] | 364 | isVarArgs(IsVarArgs) { |
Chris Lattner | a3ad5b2 | 2003-09-03 14:44:53 +0000 | [diff] [blame] | 365 | bool isAbstract = Result->isAbstract(); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 366 | ParamTys.reserve(Params.size()); |
Chris Lattner | a3ad5b2 | 2003-09-03 14:44:53 +0000 | [diff] [blame] | 367 | for (unsigned i = 0; i < Params.size(); ++i) { |
Chris Lattner | 893f025 | 2003-06-18 19:22:36 +0000 | [diff] [blame] | 368 | ParamTys.push_back(PATypeHandle(Params[i], this)); |
Chris Lattner | a3ad5b2 | 2003-09-03 14:44:53 +0000 | [diff] [blame] | 369 | isAbstract |= Params[i]->isAbstract(); |
| 370 | } |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 371 | |
Chris Lattner | a3ad5b2 | 2003-09-03 14:44:53 +0000 | [diff] [blame] | 372 | // Calculate whether or not this type is abstract |
| 373 | setAbstract(isAbstract); |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 374 | } |
| 375 | |
Chris Lattner | 47697a1 | 2003-05-22 21:21:43 +0000 | [diff] [blame] | 376 | StructType::StructType(const std::vector<const Type*> &Types) |
Chris Lattner | 6c42c31 | 2001-12-14 16:41:56 +0000 | [diff] [blame] | 377 | : CompositeType(StructTyID) { |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 378 | ETypes.reserve(Types.size()); |
Chris Lattner | a3ad5b2 | 2003-09-03 14:44:53 +0000 | [diff] [blame] | 379 | bool isAbstract = false; |
Chris Lattner | 56c5acb | 2001-10-13 07:01:33 +0000 | [diff] [blame] | 380 | for (unsigned i = 0; i < Types.size(); ++i) { |
| 381 | assert(Types[i] != Type::VoidTy && "Void type in method prototype!!"); |
Chris Lattner | 893f025 | 2003-06-18 19:22:36 +0000 | [diff] [blame] | 382 | ETypes.push_back(PATypeHandle(Types[i], this)); |
Chris Lattner | a3ad5b2 | 2003-09-03 14:44:53 +0000 | [diff] [blame] | 383 | isAbstract |= Types[i]->isAbstract(); |
Chris Lattner | 56c5acb | 2001-10-13 07:01:33 +0000 | [diff] [blame] | 384 | } |
Chris Lattner | a3ad5b2 | 2003-09-03 14:44:53 +0000 | [diff] [blame] | 385 | |
| 386 | // Calculate whether or not this type is abstract |
| 387 | setAbstract(isAbstract); |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 388 | } |
| 389 | |
Chris Lattner | 6c42c31 | 2001-12-14 16:41:56 +0000 | [diff] [blame] | 390 | ArrayType::ArrayType(const Type *ElType, unsigned NumEl) |
| 391 | : SequentialType(ArrayTyID, ElType) { |
| 392 | NumElements = NumEl; |
Chris Lattner | a3ad5b2 | 2003-09-03 14:44:53 +0000 | [diff] [blame] | 393 | |
| 394 | // Calculate whether or not this type is abstract |
| 395 | setAbstract(ElType->isAbstract()); |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 396 | } |
| 397 | |
Chris Lattner | 6c42c31 | 2001-12-14 16:41:56 +0000 | [diff] [blame] | 398 | PointerType::PointerType(const Type *E) : SequentialType(PointerTyID, E) { |
Chris Lattner | a3ad5b2 | 2003-09-03 14:44:53 +0000 | [diff] [blame] | 399 | // Calculate whether or not this type is abstract |
| 400 | setAbstract(E->isAbstract()); |
Chris Lattner | 6c42c31 | 2001-12-14 16:41:56 +0000 | [diff] [blame] | 401 | } |
| 402 | |
| 403 | OpaqueType::OpaqueType() : DerivedType(OpaqueTyID) { |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 404 | setAbstract(true); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 405 | #ifdef DEBUG_MERGE_TYPES |
Chris Lattner | a5112c7 | 2003-09-04 23:46:03 +0000 | [diff] [blame] | 406 | std::cerr << "Derived new type: " << *this << "\n"; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 407 | #endif |
| 408 | } |
| 409 | |
| 410 | |
Chris Lattner | 1825009 | 2003-10-13 14:03:36 +0000 | [diff] [blame] | 411 | // getAlwaysOpaqueTy - This function returns an opaque type. It doesn't matter |
| 412 | // _which_ opaque type it is, but the opaque type must never get resolved. |
| 413 | // |
| 414 | static Type *getAlwaysOpaqueTy() { |
| 415 | static Type *AlwaysOpaqueTy = OpaqueType::get(); |
| 416 | static PATypeHolder Holder(AlwaysOpaqueTy); |
| 417 | return AlwaysOpaqueTy; |
| 418 | } |
| 419 | |
| 420 | |
| 421 | //===----------------------------------------------------------------------===// |
| 422 | // dropAllTypeUses methods - These methods eliminate any possibly recursive type |
| 423 | // references from a derived type. The type must remain abstract, so we make |
| 424 | // sure to use an always opaque type as an argument. |
| 425 | // |
| 426 | |
| 427 | void FunctionType::dropAllTypeUses() { |
| 428 | ResultType = getAlwaysOpaqueTy(); |
| 429 | ParamTys.clear(); |
| 430 | } |
| 431 | |
| 432 | void ArrayType::dropAllTypeUses() { |
| 433 | ElementType = getAlwaysOpaqueTy(); |
| 434 | } |
| 435 | |
| 436 | void StructType::dropAllTypeUses() { |
| 437 | ETypes.clear(); |
| 438 | ETypes.push_back(PATypeHandle(getAlwaysOpaqueTy(), this)); |
| 439 | } |
| 440 | |
| 441 | void PointerType::dropAllTypeUses() { |
| 442 | ElementType = getAlwaysOpaqueTy(); |
| 443 | } |
| 444 | |
| 445 | |
| 446 | |
| 447 | |
Chris Lattner | bc4846d | 2003-09-02 21:56:34 +0000 | [diff] [blame] | 448 | // isTypeAbstract - This is a recursive function that walks a type hierarchy |
| 449 | // calculating whether or not a type is abstract. Worst case it will have to do |
| 450 | // a lot of traversing if you have some whacko opaque types, but in most cases, |
| 451 | // it will do some simple stuff when it hits non-abstract types that aren't |
| 452 | // recursive. |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 453 | // |
Chris Lattner | bc4846d | 2003-09-02 21:56:34 +0000 | [diff] [blame] | 454 | bool Type::isTypeAbstract() { |
| 455 | if (!isAbstract()) // Base case for the recursion |
| 456 | return false; // Primitive = leaf type |
Chris Lattner | dd4b421 | 2003-09-02 16:35:17 +0000 | [diff] [blame] | 457 | |
Chris Lattner | bc4846d | 2003-09-02 21:56:34 +0000 | [diff] [blame] | 458 | if (isa<OpaqueType>(this)) // Base case for the recursion |
| 459 | return true; // This whole type is abstract! |
Chris Lattner | dd4b421 | 2003-09-02 16:35:17 +0000 | [diff] [blame] | 460 | |
Chris Lattner | bc4846d | 2003-09-02 21:56:34 +0000 | [diff] [blame] | 461 | // We have to guard against recursion. To do this, we temporarily mark this |
| 462 | // type as concrete, so that if we get back to here recursively we will think |
| 463 | // it's not abstract, and thus not scan it again. |
| 464 | setAbstract(false); |
Chris Lattner | dd4b421 | 2003-09-02 16:35:17 +0000 | [diff] [blame] | 465 | |
Chris Lattner | bc4846d | 2003-09-02 21:56:34 +0000 | [diff] [blame] | 466 | // Scan all of the sub-types. If any of them are abstract, than so is this |
| 467 | // one! |
| 468 | for (Type::subtype_iterator I = subtype_begin(), E = subtype_end(); |
| 469 | I != E; ++I) |
| 470 | if (const_cast<Type*>(*I)->isTypeAbstract()) { |
Chris Lattner | 1bb6263 | 2003-09-02 22:15:15 +0000 | [diff] [blame] | 471 | setAbstract(true); // Restore the abstract bit. |
| 472 | return true; // This type is abstract if subtype is abstract! |
Chris Lattner | bc4846d | 2003-09-02 21:56:34 +0000 | [diff] [blame] | 473 | } |
| 474 | |
| 475 | // Restore the abstract bit. |
| 476 | setAbstract(true); |
Chris Lattner | dd4b421 | 2003-09-02 16:35:17 +0000 | [diff] [blame] | 477 | |
Chris Lattner | bc4846d | 2003-09-02 21:56:34 +0000 | [diff] [blame] | 478 | // Nothing looks abstract here... |
| 479 | return false; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 480 | } |
| 481 | |
| 482 | |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 483 | //===----------------------------------------------------------------------===// |
| 484 | // Type Structural Equality Testing |
| 485 | //===----------------------------------------------------------------------===// |
| 486 | |
| 487 | // TypesEqual - Two types are considered structurally equal if they have the |
| 488 | // same "shape": Every level and element of the types have identical primitive |
| 489 | // ID's, and the graphs have the same edges/nodes in them. Nodes do not have to |
| 490 | // be pointer equals to be equivalent though. This uses an optimistic algorithm |
| 491 | // that assumes that two graphs are the same until proven otherwise. |
| 492 | // |
| 493 | static bool TypesEqual(const Type *Ty, const Type *Ty2, |
Chris Lattner | 47697a1 | 2003-05-22 21:21:43 +0000 | [diff] [blame] | 494 | std::map<const Type *, const Type *> &EqTypes) { |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 495 | if (Ty == Ty2) return true; |
| 496 | if (Ty->getPrimitiveID() != Ty2->getPrimitiveID()) return false; |
| 497 | if (Ty->isPrimitiveType()) return true; |
Chris Lattner | 008f906 | 2001-10-24 05:12:04 +0000 | [diff] [blame] | 498 | if (isa<OpaqueType>(Ty)) |
Misha Brukman | 6b63452 | 2003-10-10 17:54:14 +0000 | [diff] [blame] | 499 | return false; // Two unequal opaque types are never equal |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 500 | |
Chris Lattner | 5af4197 | 2003-10-13 14:55:56 +0000 | [diff] [blame] | 501 | std::map<const Type*, const Type*>::iterator It = EqTypes.lower_bound(Ty); |
| 502 | if (It != EqTypes.end() && It->first == Ty) |
Chris Lattner | 3b1e3f4 | 2001-11-02 07:51:31 +0000 | [diff] [blame] | 503 | return It->second == Ty2; // Looping back on a type, check for equality |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 504 | |
Chris Lattner | 3b1e3f4 | 2001-11-02 07:51:31 +0000 | [diff] [blame] | 505 | // Otherwise, add the mapping to the table to make sure we don't get |
| 506 | // recursion on the types... |
Chris Lattner | 5af4197 | 2003-10-13 14:55:56 +0000 | [diff] [blame] | 507 | EqTypes.insert(It, std::make_pair(Ty, Ty2)); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 508 | |
Chris Lattner | 56c5acb | 2001-10-13 07:01:33 +0000 | [diff] [blame] | 509 | // Two really annoying special cases that breaks an otherwise nice simple |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 510 | // algorithm is the fact that arraytypes have sizes that differentiates types, |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 511 | // and that function types can be varargs or not. Consider this now. |
Chris Lattner | 5af4197 | 2003-10-13 14:55:56 +0000 | [diff] [blame] | 512 | // |
| 513 | if (const PointerType *PTy = dyn_cast<PointerType>(Ty)) { |
| 514 | return TypesEqual(PTy->getElementType(), |
| 515 | cast<PointerType>(Ty2)->getElementType(), EqTypes); |
| 516 | } else if (const StructType *STy = dyn_cast<StructType>(Ty)) { |
| 517 | const StructType::ElementTypes &STyE = STy->getElementTypes(); |
| 518 | const StructType::ElementTypes &STyE2 = |
| 519 | cast<StructType>(Ty2)->getElementTypes(); |
| 520 | if (STyE.size() != STyE2.size()) return false; |
| 521 | for (unsigned i = 0, e = STyE.size(); i != e; ++i) |
| 522 | if (!TypesEqual(STyE[i], STyE2[i], EqTypes)) |
| 523 | return false; |
| 524 | return true; |
| 525 | } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { |
| 526 | const ArrayType *ATy2 = cast<ArrayType>(Ty2); |
| 527 | return ATy->getNumElements() == ATy2->getNumElements() && |
| 528 | TypesEqual(ATy->getElementType(), ATy2->getElementType(), EqTypes); |
Chris Lattner | dd4b421 | 2003-09-02 16:35:17 +0000 | [diff] [blame] | 529 | } else if (const FunctionType *FTy = dyn_cast<FunctionType>(Ty)) { |
Chris Lattner | 5af4197 | 2003-10-13 14:55:56 +0000 | [diff] [blame] | 530 | const FunctionType *FTy2 = cast<FunctionType>(Ty2); |
| 531 | if (FTy->isVarArg() != FTy2->isVarArg() || |
| 532 | FTy->getParamTypes().size() != FTy2->getParamTypes().size() || |
| 533 | !TypesEqual(FTy->getReturnType(), FTy2->getReturnType(), EqTypes)) |
Chris Lattner | 56c5acb | 2001-10-13 07:01:33 +0000 | [diff] [blame] | 534 | return false; |
Chris Lattner | 5af4197 | 2003-10-13 14:55:56 +0000 | [diff] [blame] | 535 | const FunctionType::ParamTypes &FTyP = FTy->getParamTypes(); |
| 536 | const FunctionType::ParamTypes &FTy2P = FTy2->getParamTypes(); |
| 537 | for (unsigned i = 0, e = FTyP.size(); i != e; ++i) |
| 538 | if (!TypesEqual(FTyP[i], FTy2P[i], EqTypes)) |
| 539 | return false; |
| 540 | return true; |
| 541 | } else { |
| 542 | assert(0 && "Unknown derived type!"); |
| 543 | return false; |
Chris Lattner | 56c5acb | 2001-10-13 07:01:33 +0000 | [diff] [blame] | 544 | } |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 545 | } |
| 546 | |
| 547 | static bool TypesEqual(const Type *Ty, const Type *Ty2) { |
Chris Lattner | 47697a1 | 2003-05-22 21:21:43 +0000 | [diff] [blame] | 548 | std::map<const Type *, const Type *> EqTypes; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 549 | return TypesEqual(Ty, Ty2, EqTypes); |
| 550 | } |
| 551 | |
| 552 | |
| 553 | |
| 554 | //===----------------------------------------------------------------------===// |
| 555 | // Derived Type Factory Functions |
| 556 | //===----------------------------------------------------------------------===// |
| 557 | |
| 558 | // TypeMap - Make sure that only one instance of a particular type may be |
| 559 | // created on any given run of the compiler... note that this involves updating |
| 560 | // our map if an abstract type gets refined somehow... |
| 561 | // |
| 562 | template<class ValType, class TypeClass> |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 563 | class TypeMap { |
| 564 | typedef std::map<ValType, TypeClass *> MapTy; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 565 | MapTy Map; |
| 566 | public: |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 567 | typedef typename MapTy::iterator iterator; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 568 | ~TypeMap() { print("ON EXIT"); } |
| 569 | |
| 570 | inline TypeClass *get(const ValType &V) { |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 571 | iterator I = Map.find(V); |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 572 | return I != Map.end() ? I->second : 0; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 573 | } |
| 574 | |
| 575 | inline void add(const ValType &V, TypeClass *T) { |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 576 | Map.insert(std::make_pair(V, T)); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 577 | print("add"); |
| 578 | } |
| 579 | |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 580 | iterator getEntryForType(TypeClass *Ty) { |
| 581 | iterator I = Map.find(ValType::get(Ty)); |
| 582 | if (I == Map.end()) print("ERROR!"); |
| 583 | assert(I != Map.end() && "Didn't find type entry!"); |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 584 | assert(I->second == Ty && "Type entry wrong?"); |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 585 | return I; |
| 586 | } |
| 587 | |
Chris Lattner | 266caa2 | 2003-09-05 02:30:47 +0000 | [diff] [blame] | 588 | |
Chris Lattner | af6f93c | 2003-10-03 18:57:54 +0000 | [diff] [blame] | 589 | void finishRefinement(iterator TyIt) { |
| 590 | TypeClass *Ty = TyIt->second; |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 591 | |
| 592 | // The old record is now out-of-date, because one of the children has been |
| 593 | // updated. Remove the obsolete entry from the map. |
| 594 | Map.erase(TyIt); |
| 595 | |
| 596 | // Now we check to see if there is an existing entry in the table which is |
| 597 | // structurally identical to the newly refined type. If so, this type gets |
| 598 | // refined to the pre-existing type. |
| 599 | // |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 600 | for (iterator I = Map.begin(), E = Map.end(); I != E; ++I) |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 601 | if (TypesEqual(Ty, I->second)) { |
Chris Lattner | c9b24a3 | 2003-09-05 05:10:04 +0000 | [diff] [blame] | 602 | assert(Ty->isAbstract() && "Replacing a non-abstract type?"); |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 603 | TypeClass *NewTy = I->second; |
| 604 | |
Chris Lattner | 8df956c | 2003-09-05 02:39:52 +0000 | [diff] [blame] | 605 | // Refined to a different type altogether? |
Chris Lattner | af6f93c | 2003-10-03 18:57:54 +0000 | [diff] [blame] | 606 | Ty->refineAbstractTypeTo(NewTy); |
Chris Lattner | 8df956c | 2003-09-05 02:39:52 +0000 | [diff] [blame] | 607 | return; |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 608 | } |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 609 | |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 610 | // If there is no existing type of the same structure, we reinsert an |
| 611 | // updated record into the map. |
| 612 | Map.insert(std::make_pair(ValType::get(Ty), Ty)); |
| 613 | |
Chris Lattner | 8df956c | 2003-09-05 02:39:52 +0000 | [diff] [blame] | 614 | // If the type is currently thought to be abstract, rescan all of our |
| 615 | // subtypes to see if the type has just become concrete! |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 616 | if (Ty->isAbstract()) { |
Chris Lattner | c9b24a3 | 2003-09-05 05:10:04 +0000 | [diff] [blame] | 617 | Ty->setAbstract(Ty->isTypeAbstract()); |
| 618 | |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 619 | // If the type just became concrete, notify all users! |
| 620 | if (!Ty->isAbstract()) |
| 621 | Ty->notifyUsesThatTypeBecameConcrete(); |
| 622 | } |
Chris Lattner | 266caa2 | 2003-09-05 02:30:47 +0000 | [diff] [blame] | 623 | } |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 624 | |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 625 | void remove(const ValType &OldVal) { |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 626 | iterator I = Map.find(OldVal); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 627 | assert(I != Map.end() && "TypeMap::remove, element not found!"); |
| 628 | Map.erase(I); |
| 629 | } |
| 630 | |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 631 | void remove(iterator I) { |
| 632 | assert(I != Map.end() && "Cannot remove invalid iterator pointer!"); |
| 633 | Map.erase(I); |
| 634 | } |
| 635 | |
Chris Lattner | aa06d2c | 2002-04-04 19:26:02 +0000 | [diff] [blame] | 636 | void print(const char *Arg) const { |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 637 | #ifdef DEBUG_MERGE_TYPES |
Chris Lattner | 47697a1 | 2003-05-22 21:21:43 +0000 | [diff] [blame] | 638 | std::cerr << "TypeMap<>::" << Arg << " table contents:\n"; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 639 | unsigned i = 0; |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 640 | for (typename MapTy::const_iterator I = Map.begin(), E = Map.end(); |
| 641 | I != E; ++I) |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 642 | std::cerr << " " << (++i) << ". " << (void*)I->second << " " |
| 643 | << *I->second << "\n"; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 644 | #endif |
| 645 | } |
Chris Lattner | aa06d2c | 2002-04-04 19:26:02 +0000 | [diff] [blame] | 646 | |
| 647 | void dump() const { print("dump output"); } |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 648 | }; |
| 649 | |
| 650 | |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 651 | |
| 652 | //===----------------------------------------------------------------------===// |
Chris Lattner | 6bfd6a5 | 2002-03-29 03:44:36 +0000 | [diff] [blame] | 653 | // Function Type Factory and Value Class... |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 654 | // |
| 655 | |
Chris Lattner | 6bfd6a5 | 2002-03-29 03:44:36 +0000 | [diff] [blame] | 656 | // FunctionValType - Define a class to hold the key that goes into the TypeMap |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 657 | // |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 658 | class FunctionValType { |
| 659 | const Type *RetTy; |
| 660 | std::vector<const Type*> ArgTypes; |
Chris Lattner | 56c5acb | 2001-10-13 07:01:33 +0000 | [diff] [blame] | 661 | bool isVarArg; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 662 | public: |
Chris Lattner | 47697a1 | 2003-05-22 21:21:43 +0000 | [diff] [blame] | 663 | FunctionValType(const Type *ret, const std::vector<const Type*> &args, |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 664 | bool IVA) : RetTy(ret), isVarArg(IVA) { |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 665 | for (unsigned i = 0; i < args.size(); ++i) |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 666 | ArgTypes.push_back(args[i]); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 667 | } |
| 668 | |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 669 | static FunctionValType get(const FunctionType *FT); |
| 670 | |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 671 | // Subclass should override this... to update self as usual |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 672 | void doRefinement(const DerivedType *OldType, const Type *NewType) { |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 673 | if (RetTy == OldType) RetTy = NewType; |
Chris Lattner | 417081c | 2002-04-07 06:14:56 +0000 | [diff] [blame] | 674 | for (unsigned i = 0, e = ArgTypes.size(); i != e; ++i) |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 675 | if (ArgTypes[i] == OldType) ArgTypes[i] = NewType; |
| 676 | } |
| 677 | |
Chris Lattner | 6bfd6a5 | 2002-03-29 03:44:36 +0000 | [diff] [blame] | 678 | inline bool operator<(const FunctionValType &MTV) const { |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 679 | if (RetTy < MTV.RetTy) return true; |
| 680 | if (RetTy > MTV.RetTy) return false; |
Chris Lattner | 56c5acb | 2001-10-13 07:01:33 +0000 | [diff] [blame] | 681 | |
| 682 | if (ArgTypes < MTV.ArgTypes) return true; |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 683 | return ArgTypes == MTV.ArgTypes && isVarArg < MTV.isVarArg; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 684 | } |
| 685 | }; |
| 686 | |
| 687 | // Define the actual map itself now... |
Chris Lattner | 6bfd6a5 | 2002-03-29 03:44:36 +0000 | [diff] [blame] | 688 | static TypeMap<FunctionValType, FunctionType> FunctionTypes; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 689 | |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 690 | FunctionValType FunctionValType::get(const FunctionType *FT) { |
| 691 | // Build up a FunctionValType |
| 692 | std::vector<const Type *> ParamTypes; |
| 693 | ParamTypes.reserve(FT->getParamTypes().size()); |
| 694 | for (unsigned i = 0, e = FT->getParamTypes().size(); i != e; ++i) |
| 695 | ParamTypes.push_back(FT->getParamType(i)); |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 696 | return FunctionValType(FT->getReturnType(), ParamTypes, FT->isVarArg()); |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 697 | } |
| 698 | |
| 699 | |
Chris Lattner | 6bfd6a5 | 2002-03-29 03:44:36 +0000 | [diff] [blame] | 700 | // FunctionType::get - The factory function for the FunctionType class... |
| 701 | FunctionType *FunctionType::get(const Type *ReturnType, |
Chris Lattner | 47697a1 | 2003-05-22 21:21:43 +0000 | [diff] [blame] | 702 | const std::vector<const Type*> &Params, |
Chris Lattner | 6bfd6a5 | 2002-03-29 03:44:36 +0000 | [diff] [blame] | 703 | bool isVarArg) { |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 704 | FunctionValType VT(ReturnType, Params, isVarArg); |
Chris Lattner | 6bfd6a5 | 2002-03-29 03:44:36 +0000 | [diff] [blame] | 705 | FunctionType *MT = FunctionTypes.get(VT); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 706 | if (MT) return MT; |
Chris Lattner | e5a57ee | 2001-07-25 22:47:55 +0000 | [diff] [blame] | 707 | |
Chris Lattner | 6bfd6a5 | 2002-03-29 03:44:36 +0000 | [diff] [blame] | 708 | FunctionTypes.add(VT, MT = new FunctionType(ReturnType, Params, isVarArg)); |
Chris Lattner | e5a57ee | 2001-07-25 22:47:55 +0000 | [diff] [blame] | 709 | |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 710 | #ifdef DEBUG_MERGE_TYPES |
Chris Lattner | 47697a1 | 2003-05-22 21:21:43 +0000 | [diff] [blame] | 711 | std::cerr << "Derived new type: " << MT << "\n"; |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 712 | #endif |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 713 | return MT; |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 714 | } |
| 715 | |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 716 | //===----------------------------------------------------------------------===// |
| 717 | // Array Type Factory... |
| 718 | // |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 719 | class ArrayValType { |
| 720 | const Type *ValTy; |
Chris Lattner | 6c42c31 | 2001-12-14 16:41:56 +0000 | [diff] [blame] | 721 | unsigned Size; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 722 | public: |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 723 | ArrayValType(const Type *val, int sz) : ValTy(val), Size(sz) {} |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 724 | |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 725 | static ArrayValType get(const ArrayType *AT) { |
| 726 | return ArrayValType(AT->getElementType(), AT->getNumElements()); |
| 727 | } |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 728 | |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 729 | // Subclass should override this... to update self as usual |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 730 | void doRefinement(const DerivedType *OldType, const Type *NewType) { |
Chris Lattner | 417081c | 2002-04-07 06:14:56 +0000 | [diff] [blame] | 731 | assert(ValTy == OldType); |
| 732 | ValTy = NewType; |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 733 | } |
| 734 | |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 735 | inline bool operator<(const ArrayValType &MTV) const { |
| 736 | if (Size < MTV.Size) return true; |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 737 | return Size == MTV.Size && ValTy < MTV.ValTy; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 738 | } |
| 739 | }; |
| 740 | |
| 741 | static TypeMap<ArrayValType, ArrayType> ArrayTypes; |
| 742 | |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 743 | |
Chris Lattner | 6c42c31 | 2001-12-14 16:41:56 +0000 | [diff] [blame] | 744 | ArrayType *ArrayType::get(const Type *ElementType, unsigned NumElements) { |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 745 | assert(ElementType && "Can't get array of null types!"); |
| 746 | |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 747 | ArrayValType AVT(ElementType, NumElements); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 748 | ArrayType *AT = ArrayTypes.get(AVT); |
| 749 | if (AT) return AT; // Found a match, return it! |
| 750 | |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 751 | // Value not found. Derive a new type! |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 752 | ArrayTypes.add(AVT, AT = new ArrayType(ElementType, NumElements)); |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 753 | |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 754 | #ifdef DEBUG_MERGE_TYPES |
Chris Lattner | a5112c7 | 2003-09-04 23:46:03 +0000 | [diff] [blame] | 755 | std::cerr << "Derived new type: " << *AT << "\n"; |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 756 | #endif |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 757 | return AT; |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 758 | } |
| 759 | |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 760 | //===----------------------------------------------------------------------===// |
| 761 | // Struct Type Factory... |
| 762 | // |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 763 | |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 764 | // StructValType - Define a class to hold the key that goes into the TypeMap |
| 765 | // |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 766 | class StructValType { |
| 767 | std::vector<const Type*> ElTypes; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 768 | public: |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 769 | StructValType(const std::vector<const Type*> &args) : ElTypes(args) {} |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 770 | |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 771 | static StructValType get(const StructType *ST) { |
| 772 | std::vector<const Type *> ElTypes; |
| 773 | ElTypes.reserve(ST->getElementTypes().size()); |
| 774 | for (unsigned i = 0, e = ST->getElementTypes().size(); i != e; ++i) |
| 775 | ElTypes.push_back(ST->getElementTypes()[i]); |
| 776 | |
| 777 | return StructValType(ElTypes); |
| 778 | } |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 779 | |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 780 | // Subclass should override this... to update self as usual |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 781 | void doRefinement(const DerivedType *OldType, const Type *NewType) { |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 782 | for (unsigned i = 0; i < ElTypes.size(); ++i) |
| 783 | if (ElTypes[i] == OldType) ElTypes[i] = NewType; |
| 784 | } |
| 785 | |
| 786 | inline bool operator<(const StructValType &STV) const { |
| 787 | return ElTypes < STV.ElTypes; |
| 788 | } |
| 789 | }; |
| 790 | |
| 791 | static TypeMap<StructValType, StructType> StructTypes; |
| 792 | |
Chris Lattner | 47697a1 | 2003-05-22 21:21:43 +0000 | [diff] [blame] | 793 | StructType *StructType::get(const std::vector<const Type*> &ETypes) { |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 794 | StructValType STV(ETypes); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 795 | StructType *ST = StructTypes.get(STV); |
| 796 | if (ST) return ST; |
| 797 | |
| 798 | // Value not found. Derive a new type! |
| 799 | StructTypes.add(STV, ST = new StructType(ETypes)); |
| 800 | |
| 801 | #ifdef DEBUG_MERGE_TYPES |
Chris Lattner | a5112c7 | 2003-09-04 23:46:03 +0000 | [diff] [blame] | 802 | std::cerr << "Derived new type: " << *ST << "\n"; |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 803 | #endif |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 804 | return ST; |
| 805 | } |
| 806 | |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 807 | |
| 808 | |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 809 | //===----------------------------------------------------------------------===// |
| 810 | // Pointer Type Factory... |
| 811 | // |
| 812 | |
| 813 | // PointerValType - Define a class to hold the key that goes into the TypeMap |
| 814 | // |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 815 | class PointerValType { |
| 816 | const Type *ValTy; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 817 | public: |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 818 | PointerValType(const Type *val) : ValTy(val) {} |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 819 | |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 820 | static PointerValType get(const PointerType *PT) { |
| 821 | return PointerValType(PT->getElementType()); |
| 822 | } |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 823 | |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 824 | // Subclass should override this... to update self as usual |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 825 | void doRefinement(const DerivedType *OldType, const Type *NewType) { |
Chris Lattner | 417081c | 2002-04-07 06:14:56 +0000 | [diff] [blame] | 826 | assert(ValTy == OldType); |
| 827 | ValTy = NewType; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 828 | } |
| 829 | |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 830 | bool operator<(const PointerValType &MTV) const { |
| 831 | return ValTy < MTV.ValTy; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 832 | } |
| 833 | }; |
| 834 | |
| 835 | static TypeMap<PointerValType, PointerType> PointerTypes; |
| 836 | |
| 837 | PointerType *PointerType::get(const Type *ValueType) { |
| 838 | assert(ValueType && "Can't get a pointer to <null> type!"); |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 839 | PointerValType PVT(ValueType); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 840 | |
| 841 | PointerType *PT = PointerTypes.get(PVT); |
| 842 | if (PT) return PT; |
| 843 | |
| 844 | // Value not found. Derive a new type! |
| 845 | PointerTypes.add(PVT, PT = new PointerType(ValueType)); |
| 846 | |
| 847 | #ifdef DEBUG_MERGE_TYPES |
Chris Lattner | a5112c7 | 2003-09-04 23:46:03 +0000 | [diff] [blame] | 848 | std::cerr << "Derived new type: " << *PT << "\n"; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 849 | #endif |
| 850 | return PT; |
| 851 | } |
| 852 | |
Chris Lattner | 339ba45 | 2002-04-06 00:21:11 +0000 | [diff] [blame] | 853 | void debug_type_tables() { |
| 854 | FunctionTypes.dump(); |
| 855 | ArrayTypes.dump(); |
| 856 | StructTypes.dump(); |
| 857 | PointerTypes.dump(); |
| 858 | } |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 859 | |
| 860 | |
| 861 | //===----------------------------------------------------------------------===// |
| 862 | // Derived Type Refinement Functions |
| 863 | //===----------------------------------------------------------------------===// |
| 864 | |
| 865 | // removeAbstractTypeUser - Notify an abstract type that a user of the class |
| 866 | // no longer has a handle to the type. This function is called primarily by |
| 867 | // the PATypeHandle class. When there are no users of the abstract type, it |
Misha Brukman | 6b63452 | 2003-10-10 17:54:14 +0000 | [diff] [blame] | 868 | // is annihilated, because there is no way to get a reference to it ever again. |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 869 | // |
| 870 | void DerivedType::removeAbstractTypeUser(AbstractTypeUser *U) const { |
| 871 | // Search from back to front because we will notify users from back to |
| 872 | // front. Also, it is likely that there will be a stack like behavior to |
| 873 | // users that register and unregister users. |
| 874 | // |
Chris Lattner | 3f59b7e | 2002-04-05 19:44:07 +0000 | [diff] [blame] | 875 | unsigned i; |
| 876 | for (i = AbstractTypeUsers.size(); AbstractTypeUsers[i-1] != U; --i) |
| 877 | assert(i != 0 && "AbstractTypeUser not in user list!"); |
| 878 | |
| 879 | --i; // Convert to be in range 0 <= i < size() |
| 880 | assert(i < AbstractTypeUsers.size() && "Index out of range!"); // Wraparound? |
| 881 | |
| 882 | AbstractTypeUsers.erase(AbstractTypeUsers.begin()+i); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 883 | |
| 884 | #ifdef DEBUG_MERGE_TYPES |
Chris Lattner | 47697a1 | 2003-05-22 21:21:43 +0000 | [diff] [blame] | 885 | std::cerr << " remAbstractTypeUser[" << (void*)this << ", " |
Chris Lattner | a5112c7 | 2003-09-04 23:46:03 +0000 | [diff] [blame] | 886 | << *this << "][" << i << "] User = " << U << "\n"; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 887 | #endif |
Chris Lattner | 3f59b7e | 2002-04-05 19:44:07 +0000 | [diff] [blame] | 888 | |
Chris Lattner | 1c5164e | 2003-10-02 23:35:57 +0000 | [diff] [blame] | 889 | if (AbstractTypeUsers.empty() && RefCount == 0 && isAbstract()) { |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 890 | #ifdef DEBUG_MERGE_TYPES |
Chris Lattner | a5112c7 | 2003-09-04 23:46:03 +0000 | [diff] [blame] | 891 | std::cerr << "DELETEing unused abstract type: <" << *this |
Chris Lattner | 47697a1 | 2003-05-22 21:21:43 +0000 | [diff] [blame] | 892 | << ">[" << (void*)this << "]" << "\n"; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 893 | #endif |
Chris Lattner | 3f59b7e | 2002-04-05 19:44:07 +0000 | [diff] [blame] | 894 | delete this; // No users of this abstract type! |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 895 | } |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 896 | } |
| 897 | |
| 898 | |
Chris Lattner | af6f93c | 2003-10-03 18:57:54 +0000 | [diff] [blame] | 899 | // refineAbstractTypeTo - This function is used to when it is discovered that |
| 900 | // the 'this' abstract type is actually equivalent to the NewType specified. |
| 901 | // This causes all users of 'this' to switch to reference the more concrete type |
| 902 | // NewType and for 'this' to be deleted. |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 903 | // |
Chris Lattner | af6f93c | 2003-10-03 18:57:54 +0000 | [diff] [blame] | 904 | void DerivedType::refineAbstractTypeTo(const Type *NewType) { |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 905 | assert(isAbstract() && "refineAbstractTypeTo: Current type is not abstract!"); |
| 906 | assert(this != NewType && "Can't refine to myself!"); |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 907 | assert(ForwardType == 0 && "This type has already been refined!"); |
| 908 | |
Chris Lattner | dd4b421 | 2003-09-02 16:35:17 +0000 | [diff] [blame] | 909 | // The descriptions may be out of date. Conservatively clear them all! |
| 910 | AbstractTypeDescriptions.clear(); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 911 | |
| 912 | #ifdef DEBUG_MERGE_TYPES |
Chris Lattner | 47697a1 | 2003-05-22 21:21:43 +0000 | [diff] [blame] | 913 | std::cerr << "REFINING abstract type [" << (void*)this << " " |
Chris Lattner | a5112c7 | 2003-09-04 23:46:03 +0000 | [diff] [blame] | 914 | << *this << "] to [" << (void*)NewType << " " |
| 915 | << *NewType << "]!\n"; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 916 | #endif |
| 917 | |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 918 | // Make sure to put the type to be refined to into a holder so that if IT gets |
| 919 | // refined, that we will not continue using a dead reference... |
| 920 | // |
Chris Lattner | aa06d2c | 2002-04-04 19:26:02 +0000 | [diff] [blame] | 921 | PATypeHolder NewTy(NewType); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 922 | |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 923 | // Any PATypeHolders referring to this type will now automatically forward to |
| 924 | // the type we are resolved to. |
Chris Lattner | 1c5164e | 2003-10-02 23:35:57 +0000 | [diff] [blame] | 925 | ForwardType = NewType; |
| 926 | if (NewType->isAbstract()) |
| 927 | cast<DerivedType>(NewType)->addRef(); |
| 928 | |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 929 | // Add a self use of the current type so that we don't delete ourself until |
Chris Lattner | 8ef852f | 2003-10-03 04:48:21 +0000 | [diff] [blame] | 930 | // after the function exits. |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 931 | // |
Chris Lattner | 8ef852f | 2003-10-03 04:48:21 +0000 | [diff] [blame] | 932 | PATypeHolder CurrentTy(this); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 933 | |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 934 | // To make the situation simpler, we ask the subclass to remove this type from |
| 935 | // the type map, and to replace any type uses with uses of non-abstract types. |
| 936 | // This dramatically limits the amount of recursive type trouble we can find |
| 937 | // ourselves in. |
Chris Lattner | af6f93c | 2003-10-03 18:57:54 +0000 | [diff] [blame] | 938 | dropAllTypeUses(); |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 939 | |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 940 | // Iterate over all of the uses of this type, invoking callback. Each user |
Chris Lattner | 3f59b7e | 2002-04-05 19:44:07 +0000 | [diff] [blame] | 941 | // should remove itself from our use list automatically. We have to check to |
| 942 | // make sure that NewTy doesn't _become_ 'this'. If it does, resolving types |
| 943 | // will not cause users to drop off of the use list. If we resolve to ourself |
| 944 | // we succeed! |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 945 | // |
Chris Lattner | 8ef852f | 2003-10-03 04:48:21 +0000 | [diff] [blame] | 946 | while (!AbstractTypeUsers.empty() && NewTy != this) { |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 947 | AbstractTypeUser *User = AbstractTypeUsers.back(); |
| 948 | |
Chris Lattner | 8ef852f | 2003-10-03 04:48:21 +0000 | [diff] [blame] | 949 | unsigned OldSize = AbstractTypeUsers.size(); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 950 | #ifdef DEBUG_MERGE_TYPES |
Chris Lattner | 8ef852f | 2003-10-03 04:48:21 +0000 | [diff] [blame] | 951 | std::cerr << " REFINING user " << OldSize-1 << "[" << (void*)User |
| 952 | << "] of abstract type [" << (void*)this << " " |
| 953 | << *this << "] to [" << (void*)NewTy.get() << " " |
| 954 | << *NewTy << "]!\n"; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 955 | #endif |
Chris Lattner | 8ef852f | 2003-10-03 04:48:21 +0000 | [diff] [blame] | 956 | User->refineAbstractType(this, NewTy); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 957 | |
Chris Lattner | 8ef852f | 2003-10-03 04:48:21 +0000 | [diff] [blame] | 958 | assert(AbstractTypeUsers.size() != OldSize && |
| 959 | "AbsTyUser did not remove self from user list!"); |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 960 | } |
| 961 | |
Chris Lattner | 8ef852f | 2003-10-03 04:48:21 +0000 | [diff] [blame] | 962 | // If we were successful removing all users from the type, 'this' will be |
| 963 | // deleted when the last PATypeHolder is destroyed or updated from this type. |
| 964 | // This may occur on exit of this function, as the CurrentTy object is |
| 965 | // destroyed. |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 966 | } |
| 967 | |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 968 | // notifyUsesThatTypeBecameConcrete - Notify AbstractTypeUsers of this type that |
| 969 | // the current type has transitioned from being abstract to being concrete. |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 970 | // |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 971 | void DerivedType::notifyUsesThatTypeBecameConcrete() { |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 972 | #ifdef DEBUG_MERGE_TYPES |
Chris Lattner | a5112c7 | 2003-09-04 23:46:03 +0000 | [diff] [blame] | 973 | std::cerr << "typeIsREFINED type: " << (void*)this << " " << *this << "\n"; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 974 | #endif |
Chris Lattner | 417081c | 2002-04-07 06:14:56 +0000 | [diff] [blame] | 975 | |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 976 | unsigned OldSize = AbstractTypeUsers.size(); |
| 977 | while (!AbstractTypeUsers.empty()) { |
| 978 | AbstractTypeUser *ATU = AbstractTypeUsers.back(); |
| 979 | ATU->typeBecameConcrete(this); |
Chris Lattner | 417081c | 2002-04-07 06:14:56 +0000 | [diff] [blame] | 980 | |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 981 | assert(AbstractTypeUsers.size() < OldSize-- && |
| 982 | "AbstractTypeUser did not remove itself from the use list!"); |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 983 | } |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 984 | } |
| 985 | |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 986 | |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 987 | |
| 988 | |
| 989 | // refineAbstractType - Called when a contained type is found to be more |
| 990 | // concrete - this could potentially change us from an abstract type to a |
| 991 | // concrete type. |
| 992 | // |
Chris Lattner | 6bfd6a5 | 2002-03-29 03:44:36 +0000 | [diff] [blame] | 993 | void FunctionType::refineAbstractType(const DerivedType *OldType, |
| 994 | const Type *NewType) { |
Chris Lattner | c9b24a3 | 2003-09-05 05:10:04 +0000 | [diff] [blame] | 995 | assert((isAbstract() || !OldType->isAbstract()) && |
| 996 | "Refining a non-abstract type!"); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 997 | #ifdef DEBUG_MERGE_TYPES |
Chris Lattner | 47697a1 | 2003-05-22 21:21:43 +0000 | [diff] [blame] | 998 | std::cerr << "FunctionTy::refineAbstractTy(" << (void*)OldType << "[" |
Chris Lattner | a5112c7 | 2003-09-04 23:46:03 +0000 | [diff] [blame] | 999 | << *OldType << "], " << (void*)NewType << " [" |
| 1000 | << *NewType << "])\n"; |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 1001 | #endif |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 1002 | |
| 1003 | // Look up our current type map entry.. |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 1004 | TypeMap<FunctionValType, FunctionType>::iterator TMI = |
| 1005 | FunctionTypes.getEntryForType(this); |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 1006 | |
Chris Lattner | 3855f2f | 2002-04-05 22:25:26 +0000 | [diff] [blame] | 1007 | // Find the type element we are refining... |
Chris Lattner | 417081c | 2002-04-07 06:14:56 +0000 | [diff] [blame] | 1008 | if (ResultType == OldType) { |
| 1009 | ResultType.removeUserFromConcrete(); |
| 1010 | ResultType = NewType; |
Chris Lattner | e244a25 | 2001-11-03 03:27:53 +0000 | [diff] [blame] | 1011 | } |
Chris Lattner | 417081c | 2002-04-07 06:14:56 +0000 | [diff] [blame] | 1012 | for (unsigned i = 0, e = ParamTys.size(); i != e; ++i) |
| 1013 | if (ParamTys[i] == OldType) { |
| 1014 | ParamTys[i].removeUserFromConcrete(); |
| 1015 | ParamTys[i] = NewType; |
| 1016 | } |
Chris Lattner | e244a25 | 2001-11-03 03:27:53 +0000 | [diff] [blame] | 1017 | |
Chris Lattner | af6f93c | 2003-10-03 18:57:54 +0000 | [diff] [blame] | 1018 | FunctionTypes.finishRefinement(TMI); |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 1019 | } |
| 1020 | |
| 1021 | void FunctionType::typeBecameConcrete(const DerivedType *AbsTy) { |
| 1022 | refineAbstractType(AbsTy, AbsTy); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 1023 | } |
| 1024 | |
| 1025 | |
| 1026 | // refineAbstractType - Called when a contained type is found to be more |
| 1027 | // concrete - this could potentially change us from an abstract type to a |
| 1028 | // concrete type. |
| 1029 | // |
| 1030 | void ArrayType::refineAbstractType(const DerivedType *OldType, |
| 1031 | const Type *NewType) { |
Chris Lattner | c9b24a3 | 2003-09-05 05:10:04 +0000 | [diff] [blame] | 1032 | assert((isAbstract() || !OldType->isAbstract()) && |
| 1033 | "Refining a non-abstract type!"); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 1034 | #ifdef DEBUG_MERGE_TYPES |
Chris Lattner | 47697a1 | 2003-05-22 21:21:43 +0000 | [diff] [blame] | 1035 | std::cerr << "ArrayTy::refineAbstractTy(" << (void*)OldType << "[" |
Chris Lattner | a5112c7 | 2003-09-04 23:46:03 +0000 | [diff] [blame] | 1036 | << *OldType << "], " << (void*)NewType << " [" |
| 1037 | << *NewType << "])\n"; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 1038 | #endif |
Chris Lattner | 3b1e3f4 | 2001-11-02 07:51:31 +0000 | [diff] [blame] | 1039 | |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 1040 | // Look up our current type map entry.. |
| 1041 | TypeMap<ArrayValType, ArrayType>::iterator TMI = |
| 1042 | ArrayTypes.getEntryForType(this); |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 1043 | |
Chris Lattner | 417081c | 2002-04-07 06:14:56 +0000 | [diff] [blame] | 1044 | assert(getElementType() == OldType); |
| 1045 | ElementType.removeUserFromConcrete(); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 1046 | ElementType = NewType; |
Chris Lattner | 417081c | 2002-04-07 06:14:56 +0000 | [diff] [blame] | 1047 | |
Chris Lattner | af6f93c | 2003-10-03 18:57:54 +0000 | [diff] [blame] | 1048 | ArrayTypes.finishRefinement(TMI); |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 1049 | } |
| 1050 | |
| 1051 | void ArrayType::typeBecameConcrete(const DerivedType *AbsTy) { |
| 1052 | refineAbstractType(AbsTy, AbsTy); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 1053 | } |
| 1054 | |
| 1055 | |
| 1056 | // refineAbstractType - Called when a contained type is found to be more |
| 1057 | // concrete - this could potentially change us from an abstract type to a |
| 1058 | // concrete type. |
| 1059 | // |
| 1060 | void StructType::refineAbstractType(const DerivedType *OldType, |
| 1061 | const Type *NewType) { |
Chris Lattner | c9b24a3 | 2003-09-05 05:10:04 +0000 | [diff] [blame] | 1062 | assert((isAbstract() || !OldType->isAbstract()) && |
| 1063 | "Refining a non-abstract type!"); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 1064 | #ifdef DEBUG_MERGE_TYPES |
Chris Lattner | 47697a1 | 2003-05-22 21:21:43 +0000 | [diff] [blame] | 1065 | std::cerr << "StructTy::refineAbstractTy(" << (void*)OldType << "[" |
Chris Lattner | a5112c7 | 2003-09-04 23:46:03 +0000 | [diff] [blame] | 1066 | << *OldType << "], " << (void*)NewType << " [" |
| 1067 | << *NewType << "])\n"; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 1068 | #endif |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 1069 | |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 1070 | // Look up our current type map entry.. |
| 1071 | TypeMap<StructValType, StructType>::iterator TMI = |
| 1072 | StructTypes.getEntryForType(this); |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 1073 | |
Chris Lattner | 6a490ce | 2003-01-14 19:42:39 +0000 | [diff] [blame] | 1074 | for (int i = ETypes.size()-1; i >= 0; --i) |
Chris Lattner | 417081c | 2002-04-07 06:14:56 +0000 | [diff] [blame] | 1075 | if (ETypes[i] == OldType) { |
| 1076 | ETypes[i].removeUserFromConcrete(); |
Chris Lattner | e244a25 | 2001-11-03 03:27:53 +0000 | [diff] [blame] | 1077 | |
Chris Lattner | 417081c | 2002-04-07 06:14:56 +0000 | [diff] [blame] | 1078 | // Update old type to new type in the array... |
| 1079 | ETypes[i] = NewType; |
| 1080 | } |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 1081 | |
Chris Lattner | af6f93c | 2003-10-03 18:57:54 +0000 | [diff] [blame] | 1082 | StructTypes.finishRefinement(TMI); |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 1083 | } |
| 1084 | |
| 1085 | void StructType::typeBecameConcrete(const DerivedType *AbsTy) { |
| 1086 | refineAbstractType(AbsTy, AbsTy); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 1087 | } |
| 1088 | |
| 1089 | // refineAbstractType - Called when a contained type is found to be more |
| 1090 | // concrete - this could potentially change us from an abstract type to a |
| 1091 | // concrete type. |
| 1092 | // |
| 1093 | void PointerType::refineAbstractType(const DerivedType *OldType, |
| 1094 | const Type *NewType) { |
Chris Lattner | c9b24a3 | 2003-09-05 05:10:04 +0000 | [diff] [blame] | 1095 | assert((isAbstract() || !OldType->isAbstract()) && |
| 1096 | "Refining a non-abstract type!"); |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 1097 | #ifdef DEBUG_MERGE_TYPES |
Chris Lattner | 47697a1 | 2003-05-22 21:21:43 +0000 | [diff] [blame] | 1098 | std::cerr << "PointerTy::refineAbstractTy(" << (void*)OldType << "[" |
Chris Lattner | a5112c7 | 2003-09-04 23:46:03 +0000 | [diff] [blame] | 1099 | << *OldType << "], " << (void*)NewType << " [" |
| 1100 | << *NewType << "])\n"; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 1101 | #endif |
Chris Lattner | 3b1e3f4 | 2001-11-02 07:51:31 +0000 | [diff] [blame] | 1102 | |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 1103 | // Look up our current type map entry.. |
| 1104 | TypeMap<PointerValType, PointerType>::iterator TMI = |
| 1105 | PointerTypes.getEntryForType(this); |
Chris Lattner | 169726b | 2003-09-05 02:21:39 +0000 | [diff] [blame] | 1106 | |
Chris Lattner | 417081c | 2002-04-07 06:14:56 +0000 | [diff] [blame] | 1107 | assert(ElementType == OldType); |
| 1108 | ElementType.removeUserFromConcrete(); |
Chris Lattner | 6c42c31 | 2001-12-14 16:41:56 +0000 | [diff] [blame] | 1109 | ElementType = NewType; |
Chris Lattner | c038a2f | 2001-09-07 16:56:42 +0000 | [diff] [blame] | 1110 | |
Chris Lattner | af6f93c | 2003-10-03 18:57:54 +0000 | [diff] [blame] | 1111 | PointerTypes.finishRefinement(TMI); |
Chris Lattner | 7685ac8 | 2003-10-03 18:46:24 +0000 | [diff] [blame] | 1112 | } |
| 1113 | |
| 1114 | void PointerType::typeBecameConcrete(const DerivedType *AbsTy) { |
| 1115 | refineAbstractType(AbsTy, AbsTy); |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 1116 | } |
| 1117 | |