lib/VMCore/LLVMContextImpl.h

   1 //===----------------- LLVMContextImpl.h - Implementation ------*- C++ -*--===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This file declares LLVMContextImpl, the opaque implementation
  11 //  of LLVMContext.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_LLVMCONTEXT_IMPL_H
  16 #define LLVM_LLVMCONTEXT_IMPL_H
  17
  18 #include "llvm/LLVMContext.h"
  19 #include "llvm/Constants.h"
  20 #include "llvm/DerivedTypes.h"
  21 #include "llvm/Support/Debug.h"
  22 #include "llvm/Support/ErrorHandling.h"
  23 #include "llvm/System/Mutex.h"
  24 #include "llvm/System/RWMutex.h"
  25 #include "llvm/ADT/APFloat.h"
  26 #include "llvm/ADT/APInt.h"
  27 #include "llvm/ADT/DenseMap.h"
  28 #include "llvm/ADT/FoldingSet.h"
  29 #include "llvm/ADT/StringMap.h"
  30 #include <map>
  31 #include <vector>
  32
  33 namespace llvm {
  34 template<class ValType>
  35 struct ConstantTraits;
  36
  37 // The number of operands for each ConstantCreator::create method is
  38 // determined by the ConstantTraits template.
  39 // ConstantCreator - A class that is used to create constants by
  40 // ValueMap*.  This class should be partially specialized if there is
  41 // something strange that needs to be done to interface to the ctor for the
  42 // constant.
  43 //
  44 template<typename T, typename Alloc>
  45 struct VISIBILITY_HIDDEN ConstantTraits< std::vector<T, Alloc> > {
  46   static unsigned uses(const std::vector<T, Alloc>& v) {
  47     return v.size();
  48   }
  49 };
  50
  51 template<class ConstantClass, class TypeClass, class ValType>
  52 struct VISIBILITY_HIDDEN ConstantCreator {
  53   static ConstantClass *create(const TypeClass *Ty, const ValType &V) {
  54     return new(ConstantTraits<ValType>::uses(V)) ConstantClass(Ty, V);
  55   }
  56 };
  57
  58 template<class ConstantClass, class TypeClass>
  59 struct VISIBILITY_HIDDEN ConvertConstantType {
  60   static void convert(ConstantClass *OldC, const TypeClass *NewTy) {
  61     llvm_unreachable("This type cannot be converted!");
  62   }
  63 };
  64
  65 // ConstantAggregateZero does not take extra "value" argument...
  66 template<class ValType>
  67 struct ConstantCreator<ConstantAggregateZero, Type, ValType> {
  68   static ConstantAggregateZero *create(const Type *Ty, const ValType &V){
  69     return new ConstantAggregateZero(Ty);
  70   }
  71 };
  72
  73 template<>
  74 struct ConvertConstantType<ConstantVector, VectorType> {
  75   static void convert(ConstantVector *OldC, const VectorType *NewTy) {
  76     // Make everyone now use a constant of the new type...
  77     std::vector<Constant*> C;
  78     for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i)
  79       C.push_back(cast<Constant>(OldC->getOperand(i)));
  80     Constant *New = ConstantVector::get(NewTy, C);
  81     assert(New != OldC && "Didn't replace constant??");
  82     OldC->uncheckedReplaceAllUsesWith(New);
  83     OldC->destroyConstant();    // This constant is now dead, destroy it.
  84   }
  85 };
  86
  87 template<>
  88 struct ConvertConstantType<ConstantAggregateZero, Type> {
  89   static void convert(ConstantAggregateZero *OldC, const Type *NewTy) {
  90     // Make everyone now use a constant of the new type...
  91     Constant *New = ConstantAggregateZero::get(NewTy);
  92     assert(New != OldC && "Didn't replace constant??");
  93     OldC->uncheckedReplaceAllUsesWith(New);
  94     OldC->destroyConstant();     // This constant is now dead, destroy it.
  95   }
  96 };
  97
  98 template<>
  99 struct ConvertConstantType<ConstantArray, ArrayType> {
 100   static void convert(ConstantArray *OldC, const ArrayType *NewTy) {
 101     // Make everyone now use a constant of the new type...
 102     std::vector<Constant*> C;
 103     for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i)
 104       C.push_back(cast<Constant>(OldC->getOperand(i)));
 105     Constant *New = ConstantArray::get(NewTy, C);
 106     assert(New != OldC && "Didn't replace constant??");
 107     OldC->uncheckedReplaceAllUsesWith(New);
 108     OldC->destroyConstant();    // This constant is now dead, destroy it.
 109   }
 110 };
 111
 112 template<>
 113 struct ConvertConstantType<ConstantStruct, StructType> {
 114   static void convert(ConstantStruct *OldC, const StructType *NewTy) {
 115     // Make everyone now use a constant of the new type...
 116     std::vector<Constant*> C;
 117     for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i)
 118       C.push_back(cast<Constant>(OldC->getOperand(i)));
 119     Constant *New = ConstantStruct::get(NewTy, C);
 120     assert(New != OldC && "Didn't replace constant??");
 121
 122     OldC->uncheckedReplaceAllUsesWith(New);
 123     OldC->destroyConstant();    // This constant is now dead, destroy it.
 124   }
 125 };
 126
 127 // ConstantPointerNull does not take extra "value" argument...
 128 template<class ValType>
 129 struct ConstantCreator<ConstantPointerNull, PointerType, ValType> {
 130   static ConstantPointerNull *create(const PointerType *Ty, const ValType &V){
 131     return new ConstantPointerNull(Ty);
 132   }
 133 };
 134
 135 template<>
 136 struct ConvertConstantType<ConstantPointerNull, PointerType> {
 137   static void convert(ConstantPointerNull *OldC, const PointerType *NewTy) {
 138     // Make everyone now use a constant of the new type...
 139     Constant *New = ConstantPointerNull::get(NewTy);
 140     assert(New != OldC && "Didn't replace constant??");
 141     OldC->uncheckedReplaceAllUsesWith(New);
 142     OldC->destroyConstant();     // This constant is now dead, destroy it.
 143   }
 144 };
 145
 146 // UndefValue does not take extra "value" argument...
 147 template<class ValType>
 148 struct ConstantCreator<UndefValue, Type, ValType> {
 149   static UndefValue *create(const Type *Ty, const ValType &V) {
 150     return new UndefValue(Ty);
 151   }
 152 };
 153
 154 template<>
 155 struct ConvertConstantType<UndefValue, Type> {
 156   static void convert(UndefValue *OldC, const Type *NewTy) {
 157     // Make everyone now use a constant of the new type.
 158     Constant *New = UndefValue::get(NewTy);
 159     assert(New != OldC && "Didn't replace constant??");
 160     OldC->uncheckedReplaceAllUsesWith(New);
 161     OldC->destroyConstant();     // This constant is now dead, destroy it.
 162   }
 163 };
 164
 165 template<class ValType, class TypeClass, class ConstantClass,
 166          bool HasLargeKey = false /*true for arrays and structs*/ >
 167 class ValueMap : public AbstractTypeUser {
 168 public:
 169   typedef std::pair<const Type*, ValType> MapKey;
 170   typedef std::map<MapKey, Constant *> MapTy;
 171   typedef std::map<Constant*, typename MapTy::iterator> InverseMapTy;
 172   typedef std::map<const Type*, typename MapTy::iterator> AbstractTypeMapTy;
 173 private:
 174   /// Map - This is the main map from the element descriptor to the Constants.
 175   /// This is the primary way we avoid creating two of the same shape
 176   /// constant.
 177   MapTy Map;
 178
 179   /// InverseMap - If "HasLargeKey" is true, this contains an inverse mapping
 180   /// from the constants to their element in Map.  This is important for
 181   /// removal of constants from the array, which would otherwise have to scan
 182   /// through the map with very large keys.
 183   InverseMapTy InverseMap;
 184
 185   /// AbstractTypeMap - Map for abstract type constants.
 186   ///
 187   AbstractTypeMapTy AbstractTypeMap;
 188
 189   /// ValueMapLock - Mutex for this map.
 190   sys::SmartMutex<true> ValueMapLock;
 191
 192 public:
 193   // NOTE: This function is not locked.  It is the caller's responsibility
 194   // to enforce proper synchronization.
 195   typename MapTy::iterator map_end() { return Map.end(); }
 196
 197   /// InsertOrGetItem - Return an iterator for the specified element.
 198   /// If the element exists in the map, the returned iterator points to the
 199   /// entry and Exists=true.  If not, the iterator points to the newly
 200   /// inserted entry and returns Exists=false.  Newly inserted entries have
 201   /// I->second == 0, and should be filled in.
 202   /// NOTE: This function is not locked.  It is the caller's responsibility
 203   // to enforce proper synchronization.
 204   typename MapTy::iterator InsertOrGetItem(std::pair<MapKey, Constant *>
 205                                  &InsertVal,
 206                                  bool &Exists) {
 207     std::pair<typename MapTy::iterator, bool> IP = Map.insert(InsertVal);
 208     Exists = !IP.second;
 209     return IP.first;
 210   }
 211
 212 private:
 213   typename MapTy::iterator FindExistingElement(ConstantClass *CP) {
 214     if (HasLargeKey) {
 215       typename InverseMapTy::iterator IMI = InverseMap.find(CP);
 216       assert(IMI != InverseMap.end() && IMI->second != Map.end() &&
 217              IMI->second->second == CP &&
 218              "InverseMap corrupt!");
 219       return IMI->second;
 220     }
 221
 222     typename MapTy::iterator I =
 223       Map.find(MapKey(static_cast<const TypeClass*>(CP->getRawType()),
 224                       getValType(CP)));
 225     if (I == Map.end() || I->second != CP) {
 226       // FIXME: This should not use a linear scan.  If this gets to be a
 227       // performance problem, someone should look at this.
 228       for (I = Map.begin(); I != Map.end() && I->second != CP; ++I)
 229         /* empty */;
 230     }
 231     return I;
 232   }
 233
 234   ConstantClass* Create(const TypeClass *Ty, const ValType &V,
 235                         typename MapTy::iterator I) {
 236     ConstantClass* Result =
 237       ConstantCreator<ConstantClass,TypeClass,ValType>::create(Ty, V);
 238
 239     assert(Result->getType() == Ty && "Type specified is not correct!");
 240     I = Map.insert(I, std::make_pair(MapKey(Ty, V), Result));
 241
 242     if (HasLargeKey)  // Remember the reverse mapping if needed.
 243       InverseMap.insert(std::make_pair(Result, I));
 244
 245     // If the type of the constant is abstract, make sure that an entry
 246     // exists for it in the AbstractTypeMap.
 247     if (Ty->isAbstract()) {
 248       typename AbstractTypeMapTy::iterator TI =
 249                                                AbstractTypeMap.find(Ty);
 250
 251       if (TI == AbstractTypeMap.end()) {
 252         // Add ourselves to the ATU list of the type.
 253         cast<DerivedType>(Ty)->addAbstractTypeUser(this);
 254
 255         AbstractTypeMap.insert(TI, std::make_pair(Ty, I));
 256       }
 257     }
 258
 259     return Result;
 260   }
 261 public:
 262
 263   /// getOrCreate - Return the specified constant from the map, creating it if
 264   /// necessary.
 265   ConstantClass *getOrCreate(const TypeClass *Ty, const ValType &V) {
 266     sys::SmartScopedLock<true> Lock(ValueMapLock);
 267     MapKey Lookup(Ty, V);
 268     ConstantClass* Result = 0;
 269
 270     typename MapTy::iterator I = Map.find(Lookup);
 271     // Is it in the map?
 272     if (I != Map.end())
 273       Result = static_cast<ConstantClass *>(I->second);
 274
 275     if (!Result) {
 276       // If no preexisting value, create one now...
 277       Result = Create(Ty, V, I);
 278     }
 279
 280     return Result;
 281   }
 282
 283   void remove(ConstantClass *CP) {
 284     sys::SmartScopedLock<true> Lock(ValueMapLock);
 285     typename MapTy::iterator I = FindExistingElement(CP);
 286     assert(I != Map.end() && "Constant not found in constant table!");
 287     assert(I->second == CP && "Didn't find correct element?");
 288
 289     if (HasLargeKey)  // Remember the reverse mapping if needed.
 290       InverseMap.erase(CP);
 291
 292     // Now that we found the entry, make sure this isn't the entry that
 293     // the AbstractTypeMap points to.
 294     const TypeClass *Ty = static_cast<const TypeClass *>(I->first.first);
 295     if (Ty->isAbstract()) {
 296       assert(AbstractTypeMap.count(Ty) &&
 297              "Abstract type not in AbstractTypeMap?");
 298       typename MapTy::iterator &ATMEntryIt = AbstractTypeMap[Ty];
 299       if (ATMEntryIt == I) {
 300         // Yes, we are removing the representative entry for this type.
 301         // See if there are any other entries of the same type.
 302         typename MapTy::iterator TmpIt = ATMEntryIt;
 303
 304         // First check the entry before this one...
 305         if (TmpIt != Map.begin()) {
 306           --TmpIt;
 307           if (TmpIt->first.first != Ty) // Not the same type, move back...
 308             ++TmpIt;
 309         }
 310
 311         // If we didn't find the same type, try to move forward...
 312         if (TmpIt == ATMEntryIt) {
 313           ++TmpIt;
 314           if (TmpIt == Map.end() || TmpIt->first.first != Ty)
 315             --TmpIt;   // No entry afterwards with the same type
 316         }
 317
 318         // If there is another entry in the map of the same abstract type,
 319         // update the AbstractTypeMap entry now.
 320         if (TmpIt != ATMEntryIt) {
 321           ATMEntryIt = TmpIt;
 322         } else {
 323           // Otherwise, we are removing the last instance of this type
 324           // from the table.  Remove from the ATM, and from user list.
 325           cast<DerivedType>(Ty)->removeAbstractTypeUser(this);
 326           AbstractTypeMap.erase(Ty);
 327         }
 328       }
 329     }
 330
 331     Map.erase(I);
 332   }
 333
 334
 335   /// MoveConstantToNewSlot - If we are about to change C to be the element
 336   /// specified by I, update our internal data structures to reflect this
 337   /// fact.
 338   /// NOTE: This function is not locked. It is the responsibility of the
 339   /// caller to enforce proper synchronization if using this method.
 340   void MoveConstantToNewSlot(ConstantClass *C, typename MapTy::iterator I) {
 341     // First, remove the old location of the specified constant in the map.
 342     typename MapTy::iterator OldI = FindExistingElement(C);
 343     assert(OldI != Map.end() && "Constant not found in constant table!");
 344     assert(OldI->second == C && "Didn't find correct element?");
 345
 346     // If this constant is the representative element for its abstract type,
 347     // update the AbstractTypeMap so that the representative element is I.
 348     if (C->getType()->isAbstract()) {
 349       typename AbstractTypeMapTy::iterator ATI =
 350           AbstractTypeMap.find(C->getType());
 351       assert(ATI != AbstractTypeMap.end() &&
 352              "Abstract type not in AbstractTypeMap?");
 353       if (ATI->second == OldI)
 354         ATI->second = I;
 355     }
 356
 357     // Remove the old entry from the map.
 358     Map.erase(OldI);
 359
 360     // Update the inverse map so that we know that this constant is now
 361     // located at descriptor I.
 362     if (HasLargeKey) {
 363       assert(I->second == C && "Bad inversemap entry!");
 364       InverseMap[C] = I;
 365     }
 366   }
 367
 368   void refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
 369     sys::SmartScopedLock<true> Lock(ValueMapLock);
 370     typename AbstractTypeMapTy::iterator I =
 371       AbstractTypeMap.find(cast<Type>(OldTy));
 372
 373     assert(I != AbstractTypeMap.end() &&
 374            "Abstract type not in AbstractTypeMap?");
 375
 376     // Convert a constant at a time until the last one is gone.  The last one
 377     // leaving will remove() itself, causing the AbstractTypeMapEntry to be
 378     // eliminated eventually.
 379     do {
 380       ConvertConstantType<ConstantClass,
 381                           TypeClass>::convert(
 382                               static_cast<ConstantClass *>(I->second->second),
 383                                               cast<TypeClass>(NewTy));
 384
 385       I = AbstractTypeMap.find(cast<Type>(OldTy));
 386     } while (I != AbstractTypeMap.end());
 387   }
 388
 389   // If the type became concrete without being refined to any other existing
 390   // type, we just remove ourselves from the ATU list.
 391   void typeBecameConcrete(const DerivedType *AbsTy) {
 392     AbsTy->removeAbstractTypeUser(this);
 393   }
 394
 395   void dump() const {
 396     DOUT << "Constant.cpp: ValueMap\n";
 397   }
 398 };
 399
 400
 401 class ConstantInt;
 402 class ConstantFP;
 403 class MDString;
 404 class MDNode;
 405 class LLVMContext;
 406 class Type;
 407 class Value;
 408
 409 struct DenseMapAPIntKeyInfo {
 410   struct KeyTy {
 411     APInt val;
 412     const Type* type;
 413     KeyTy(const APInt& V, const Type* Ty) : val(V), type(Ty) {}
 414     KeyTy(const KeyTy& that) : val(that.val), type(that.type) {}
 415     bool operator==(const KeyTy& that) const {
 416       return type == that.type && this->val == that.val;
 417     }
 418     bool operator!=(const KeyTy& that) const {
 419       return !this->operator==(that);
 420     }
 421   };
 422   static inline KeyTy getEmptyKey() { return KeyTy(APInt(1,0), 0); }
 423   static inline KeyTy getTombstoneKey() { return KeyTy(APInt(1,1), 0); }
 424   static unsigned getHashValue(const KeyTy &Key) {
 425     return DenseMapInfo<void*>::getHashValue(Key.type) ^
 426       Key.val.getHashValue();
 427   }
 428   static bool isEqual(const KeyTy &LHS, const KeyTy &RHS) {
 429     return LHS == RHS;
 430   }
 431   static bool isPod() { return false; }
 432 };
 433
 434 struct DenseMapAPFloatKeyInfo {
 435   struct KeyTy {
 436     APFloat val;
 437     KeyTy(const APFloat& V) : val(V){}
 438     KeyTy(const KeyTy& that) : val(that.val) {}
 439     bool operator==(const KeyTy& that) const {
 440       return this->val.bitwiseIsEqual(that.val);
 441     }
 442     bool operator!=(const KeyTy& that) const {
 443       return !this->operator==(that);
 444     }
 445   };
 446   static inline KeyTy getEmptyKey() {
 447     return KeyTy(APFloat(APFloat::Bogus,1));
 448   }
 449   static inline KeyTy getTombstoneKey() {
 450     return KeyTy(APFloat(APFloat::Bogus,2));
 451   }
 452   static unsigned getHashValue(const KeyTy &Key) {
 453     return Key.val.getHashValue();
 454   }
 455   static bool isEqual(const KeyTy &LHS, const KeyTy &RHS) {
 456     return LHS == RHS;
 457   }
 458   static bool isPod() { return false; }
 459 };
 460
 461 class LLVMContextImpl {
 462   sys::SmartRWMutex<true> ConstantsLock;
 463
 464   typedef DenseMap<DenseMapAPIntKeyInfo::KeyTy, ConstantInt*,
 465                    DenseMapAPIntKeyInfo> IntMapTy;
 466   IntMapTy IntConstants;
 467
 468   typedef DenseMap<DenseMapAPFloatKeyInfo::KeyTy, ConstantFP*,
 469                    DenseMapAPFloatKeyInfo> FPMapTy;
 470   FPMapTy FPConstants;
 471
 472   StringMap<MDString*> MDStringCache;
 473
 474   FoldingSet<MDNode> MDNodeSet;
 475
 476   ValueMap<char, Type, ConstantAggregateZero> AggZeroConstants;
 477
 478   typedef ValueMap<std::vector<Constant*>, ArrayType,
 479     ConstantArray, true /*largekey*/> ArrayConstantsTy;
 480   ArrayConstantsTy ArrayConstants;
 481
 482   typedef ValueMap<std::vector<Constant*>, StructType,
 483                    ConstantStruct, true /*largekey*/> StructConstantsTy;
 484   StructConstantsTy StructConstants;
 485
 486   typedef ValueMap<std::vector<Constant*>, VectorType,
 487                    ConstantVector> VectorConstantsTy;
 488   VectorConstantsTy VectorConstants;
 489
 490   ValueMap<char, PointerType, ConstantPointerNull> NullPtrConstants;
 491
 492   ValueMap<char, Type, UndefValue> UndefValueConstants;
 493
 494   LLVMContext &Context;
 495   ConstantInt *TheTrueVal;
 496   ConstantInt *TheFalseVal;
 497
 498   LLVMContextImpl();
 499   LLVMContextImpl(const LLVMContextImpl&);
 500
 501   friend class ConstantInt;
 502   friend class ConstantFP;
 503   friend class ConstantStruct;
 504   friend class ConstantArray;
 505   friend class ConstantVector;
 506   friend class ConstantAggregateZero;
 507   friend class MDNode;
 508   friend class MDString;
 509   friend class ConstantPointerNull;
 510   friend class UndefValue;
 511 public:
 512   LLVMContextImpl(LLVMContext &C);
 513 };
 514
 515 }
 516
 517 #endif