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<ConstantAggregateZero, Type> {
  75   static void convert(ConstantAggregateZero *OldC, const Type *NewTy) {
  76     // Make everyone now use a constant of the new type...
  77     Constant *New = ConstantAggregateZero::get(NewTy);
  78     assert(New != OldC && "Didn't replace constant??");
  79     OldC->uncheckedReplaceAllUsesWith(New);
  80     OldC->destroyConstant();     // This constant is now dead, destroy it.
  81   }
  82 };
  83
  84 template<>
  85 struct ConvertConstantType<ConstantArray, ArrayType> {
  86   static void convert(ConstantArray *OldC, const ArrayType *NewTy) {
  87     // Make everyone now use a constant of the new type...
  88     std::vector<Constant*> C;
  89     for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i)
  90       C.push_back(cast<Constant>(OldC->getOperand(i)));
  91     Constant *New = ConstantArray::get(NewTy, C);
  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<ConstantStruct, StructType> {
 100   static void convert(ConstantStruct *OldC, const StructType *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 = ConstantStruct::get(NewTy, C);
 106     assert(New != OldC && "Didn't replace constant??");
 107
 108     OldC->uncheckedReplaceAllUsesWith(New);
 109     OldC->destroyConstant();    // This constant is now dead, destroy it.
 110   }
 111 };
 112
 113 template<>
 114 struct ConvertConstantType<ConstantVector, VectorType> {
 115   static void convert(ConstantVector *OldC, const VectorType *NewTy) {
 116     // Make everyone now use a constant of the new type...
 117     std::vector<Constant*> C;
 118     for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i)
 119       C.push_back(cast<Constant>(OldC->getOperand(i)));
 120     Constant *New = ConstantVector::get(NewTy, C);
 121     assert(New != OldC && "Didn't replace constant??");
 122     OldC->uncheckedReplaceAllUsesWith(New);
 123     OldC->destroyConstant();    // This constant is now dead, destroy it.
 124   }
 125 };
 126
 127 template<class ValType, class TypeClass, class ConstantClass,
 128          bool HasLargeKey = false /*true for arrays and structs*/ >
 129 class ValueMap : public AbstractTypeUser {
 130 public:
 131   typedef std::pair<const Type*, ValType> MapKey;
 132   typedef std::map<MapKey, Constant *> MapTy;
 133   typedef std::map<Constant*, typename MapTy::iterator> InverseMapTy;
 134   typedef std::map<const Type*, typename MapTy::iterator> AbstractTypeMapTy;
 135 private:
 136   /// Map - This is the main map from the element descriptor to the Constants.
 137   /// This is the primary way we avoid creating two of the same shape
 138   /// constant.
 139   MapTy Map;
 140
 141   /// InverseMap - If "HasLargeKey" is true, this contains an inverse mapping
 142   /// from the constants to their element in Map.  This is important for
 143   /// removal of constants from the array, which would otherwise have to scan
 144   /// through the map with very large keys.
 145   InverseMapTy InverseMap;
 146
 147   /// AbstractTypeMap - Map for abstract type constants.
 148   ///
 149   AbstractTypeMapTy AbstractTypeMap;
 150
 151   /// ValueMapLock - Mutex for this map.
 152   sys::SmartMutex<true> ValueMapLock;
 153
 154 public:
 155   // NOTE: This function is not locked.  It is the caller's responsibility
 156   // to enforce proper synchronization.
 157   typename MapTy::iterator map_end() { return Map.end(); }
 158
 159   /// InsertOrGetItem - Return an iterator for the specified element.
 160   /// If the element exists in the map, the returned iterator points to the
 161   /// entry and Exists=true.  If not, the iterator points to the newly
 162   /// inserted entry and returns Exists=false.  Newly inserted entries have
 163   /// I->second == 0, and should be filled in.
 164   /// NOTE: This function is not locked.  It is the caller's responsibility
 165   // to enforce proper synchronization.
 166   typename MapTy::iterator InsertOrGetItem(std::pair<MapKey, Constant *>
 167                                  &InsertVal,
 168                                  bool &Exists) {
 169     std::pair<typename MapTy::iterator, bool> IP = Map.insert(InsertVal);
 170     Exists = !IP.second;
 171     return IP.first;
 172   }
 173
 174 private:
 175   typename MapTy::iterator FindExistingElement(ConstantClass *CP) {
 176     if (HasLargeKey) {
 177       typename InverseMapTy::iterator IMI = InverseMap.find(CP);
 178       assert(IMI != InverseMap.end() && IMI->second != Map.end() &&
 179              IMI->second->second == CP &&
 180              "InverseMap corrupt!");
 181       return IMI->second;
 182     }
 183
 184     typename MapTy::iterator I =
 185       Map.find(MapKey(static_cast<const TypeClass*>(CP->getRawType()),
 186                       getValType(CP)));
 187     if (I == Map.end() || I->second != CP) {
 188       // FIXME: This should not use a linear scan.  If this gets to be a
 189       // performance problem, someone should look at this.
 190       for (I = Map.begin(); I != Map.end() && I->second != CP; ++I)
 191         /* empty */;
 192     }
 193     return I;
 194   }
 195
 196   ConstantClass* Create(const TypeClass *Ty, const ValType &V,
 197                         typename MapTy::iterator I) {
 198     ConstantClass* Result =
 199       ConstantCreator<ConstantClass,TypeClass,ValType>::create(Ty, V);
 200
 201     assert(Result->getType() == Ty && "Type specified is not correct!");
 202     I = Map.insert(I, std::make_pair(MapKey(Ty, V), Result));
 203
 204     if (HasLargeKey)  // Remember the reverse mapping if needed.
 205       InverseMap.insert(std::make_pair(Result, I));
 206
 207     // If the type of the constant is abstract, make sure that an entry
 208     // exists for it in the AbstractTypeMap.
 209     if (Ty->isAbstract()) {
 210       typename AbstractTypeMapTy::iterator TI =
 211                                                AbstractTypeMap.find(Ty);
 212
 213       if (TI == AbstractTypeMap.end()) {
 214         // Add ourselves to the ATU list of the type.
 215         cast<DerivedType>(Ty)->addAbstractTypeUser(this);
 216
 217         AbstractTypeMap.insert(TI, std::make_pair(Ty, I));
 218       }
 219     }
 220
 221     return Result;
 222   }
 223 public:
 224
 225   /// getOrCreate - Return the specified constant from the map, creating it if
 226   /// necessary.
 227   ConstantClass *getOrCreate(const TypeClass *Ty, const ValType &V) {
 228     sys::SmartScopedLock<true> Lock(ValueMapLock);
 229     MapKey Lookup(Ty, V);
 230     ConstantClass* Result = 0;
 231
 232     typename MapTy::iterator I = Map.find(Lookup);
 233     // Is it in the map?
 234     if (I != Map.end())
 235       Result = static_cast<ConstantClass *>(I->second);
 236
 237     if (!Result) {
 238       // If no preexisting value, create one now...
 239       Result = Create(Ty, V, I);
 240     }
 241
 242     return Result;
 243   }
 244
 245   void remove(ConstantClass *CP) {
 246     sys::SmartScopedLock<true> Lock(ValueMapLock);
 247     typename MapTy::iterator I = FindExistingElement(CP);
 248     assert(I != Map.end() && "Constant not found in constant table!");
 249     assert(I->second == CP && "Didn't find correct element?");
 250
 251     if (HasLargeKey)  // Remember the reverse mapping if needed.
 252       InverseMap.erase(CP);
 253
 254     // Now that we found the entry, make sure this isn't the entry that
 255     // the AbstractTypeMap points to.
 256     const TypeClass *Ty = static_cast<const TypeClass *>(I->first.first);
 257     if (Ty->isAbstract()) {
 258       assert(AbstractTypeMap.count(Ty) &&
 259              "Abstract type not in AbstractTypeMap?");
 260       typename MapTy::iterator &ATMEntryIt = AbstractTypeMap[Ty];
 261       if (ATMEntryIt == I) {
 262         // Yes, we are removing the representative entry for this type.
 263         // See if there are any other entries of the same type.
 264         typename MapTy::iterator TmpIt = ATMEntryIt;
 265
 266         // First check the entry before this one...
 267         if (TmpIt != Map.begin()) {
 268           --TmpIt;
 269           if (TmpIt->first.first != Ty) // Not the same type, move back...
 270             ++TmpIt;
 271         }
 272
 273         // If we didn't find the same type, try to move forward...
 274         if (TmpIt == ATMEntryIt) {
 275           ++TmpIt;
 276           if (TmpIt == Map.end() || TmpIt->first.first != Ty)
 277             --TmpIt;   // No entry afterwards with the same type
 278         }
 279
 280         // If there is another entry in the map of the same abstract type,
 281         // update the AbstractTypeMap entry now.
 282         if (TmpIt != ATMEntryIt) {
 283           ATMEntryIt = TmpIt;
 284         } else {
 285           // Otherwise, we are removing the last instance of this type
 286           // from the table.  Remove from the ATM, and from user list.
 287           cast<DerivedType>(Ty)->removeAbstractTypeUser(this);
 288           AbstractTypeMap.erase(Ty);
 289         }
 290       }
 291     }
 292
 293     Map.erase(I);
 294   }
 295
 296
 297   /// MoveConstantToNewSlot - If we are about to change C to be the element
 298   /// specified by I, update our internal data structures to reflect this
 299   /// fact.
 300   /// NOTE: This function is not locked. It is the responsibility of the
 301   /// caller to enforce proper synchronization if using this method.
 302   void MoveConstantToNewSlot(ConstantClass *C, typename MapTy::iterator I) {
 303     // First, remove the old location of the specified constant in the map.
 304     typename MapTy::iterator OldI = FindExistingElement(C);
 305     assert(OldI != Map.end() && "Constant not found in constant table!");
 306     assert(OldI->second == C && "Didn't find correct element?");
 307
 308     // If this constant is the representative element for its abstract type,
 309     // update the AbstractTypeMap so that the representative element is I.
 310     if (C->getType()->isAbstract()) {
 311       typename AbstractTypeMapTy::iterator ATI =
 312           AbstractTypeMap.find(C->getType());
 313       assert(ATI != AbstractTypeMap.end() &&
 314              "Abstract type not in AbstractTypeMap?");
 315       if (ATI->second == OldI)
 316         ATI->second = I;
 317     }
 318
 319     // Remove the old entry from the map.
 320     Map.erase(OldI);
 321
 322     // Update the inverse map so that we know that this constant is now
 323     // located at descriptor I.
 324     if (HasLargeKey) {
 325       assert(I->second == C && "Bad inversemap entry!");
 326       InverseMap[C] = I;
 327     }
 328   }
 329
 330   void refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
 331     sys::SmartScopedLock<true> Lock(ValueMapLock);
 332     typename AbstractTypeMapTy::iterator I =
 333       AbstractTypeMap.find(cast<Type>(OldTy));
 334
 335     assert(I != AbstractTypeMap.end() &&
 336            "Abstract type not in AbstractTypeMap?");
 337
 338     // Convert a constant at a time until the last one is gone.  The last one
 339     // leaving will remove() itself, causing the AbstractTypeMapEntry to be
 340     // eliminated eventually.
 341     do {
 342       ConvertConstantType<ConstantClass,
 343                           TypeClass>::convert(
 344                               static_cast<ConstantClass *>(I->second->second),
 345                                               cast<TypeClass>(NewTy));
 346
 347       I = AbstractTypeMap.find(cast<Type>(OldTy));
 348     } while (I != AbstractTypeMap.end());
 349   }
 350
 351   // If the type became concrete without being refined to any other existing
 352   // type, we just remove ourselves from the ATU list.
 353   void typeBecameConcrete(const DerivedType *AbsTy) {
 354     AbsTy->removeAbstractTypeUser(this);
 355   }
 356
 357   void dump() const {
 358     DOUT << "Constant.cpp: ValueMap\n";
 359   }
 360 };
 361
 362
 363 class ConstantInt;
 364 class ConstantFP;
 365 class MDString;
 366 class MDNode;
 367 class LLVMContext;
 368 class Type;
 369 class Value;
 370
 371 struct DenseMapAPIntKeyInfo {
 372   struct KeyTy {
 373     APInt val;
 374     const Type* type;
 375     KeyTy(const APInt& V, const Type* Ty) : val(V), type(Ty) {}
 376     KeyTy(const KeyTy& that) : val(that.val), type(that.type) {}
 377     bool operator==(const KeyTy& that) const {
 378       return type == that.type && this->val == that.val;
 379     }
 380     bool operator!=(const KeyTy& that) const {
 381       return !this->operator==(that);
 382     }
 383   };
 384   static inline KeyTy getEmptyKey() { return KeyTy(APInt(1,0), 0); }
 385   static inline KeyTy getTombstoneKey() { return KeyTy(APInt(1,1), 0); }
 386   static unsigned getHashValue(const KeyTy &Key) {
 387     return DenseMapInfo<void*>::getHashValue(Key.type) ^
 388       Key.val.getHashValue();
 389   }
 390   static bool isEqual(const KeyTy &LHS, const KeyTy &RHS) {
 391     return LHS == RHS;
 392   }
 393   static bool isPod() { return false; }
 394 };
 395
 396 struct DenseMapAPFloatKeyInfo {
 397   struct KeyTy {
 398     APFloat val;
 399     KeyTy(const APFloat& V) : val(V){}
 400     KeyTy(const KeyTy& that) : val(that.val) {}
 401     bool operator==(const KeyTy& that) const {
 402       return this->val.bitwiseIsEqual(that.val);
 403     }
 404     bool operator!=(const KeyTy& that) const {
 405       return !this->operator==(that);
 406     }
 407   };
 408   static inline KeyTy getEmptyKey() {
 409     return KeyTy(APFloat(APFloat::Bogus,1));
 410   }
 411   static inline KeyTy getTombstoneKey() {
 412     return KeyTy(APFloat(APFloat::Bogus,2));
 413   }
 414   static unsigned getHashValue(const KeyTy &Key) {
 415     return Key.val.getHashValue();
 416   }
 417   static bool isEqual(const KeyTy &LHS, const KeyTy &RHS) {
 418     return LHS == RHS;
 419   }
 420   static bool isPod() { return false; }
 421 };
 422
 423 class LLVMContextImpl {
 424   sys::SmartRWMutex<true> ConstantsLock;
 425
 426   typedef DenseMap<DenseMapAPIntKeyInfo::KeyTy, ConstantInt*,
 427                    DenseMapAPIntKeyInfo> IntMapTy;
 428   IntMapTy IntConstants;
 429
 430   typedef DenseMap<DenseMapAPFloatKeyInfo::KeyTy, ConstantFP*,
 431                    DenseMapAPFloatKeyInfo> FPMapTy;
 432   FPMapTy FPConstants;
 433
 434   StringMap<MDString*> MDStringCache;
 435
 436   FoldingSet<MDNode> MDNodeSet;
 437
 438   ValueMap<char, Type, ConstantAggregateZero> AggZeroConstants;
 439
 440   typedef ValueMap<std::vector<Constant*>, ArrayType,
 441     ConstantArray, true /*largekey*/> ArrayConstantsTy;
 442   ArrayConstantsTy ArrayConstants;
 443
 444   typedef ValueMap<std::vector<Constant*>, StructType,
 445                    ConstantStruct, true /*largekey*/> StructConstantsTy;
 446   StructConstantsTy StructConstants;
 447
 448   typedef ValueMap<std::vector<Constant*>, VectorType,
 449                    ConstantVector> VectorConstantsTy;
 450   VectorConstantsTy VectorConstants;
 451
 452   LLVMContext &Context;
 453   ConstantInt *TheTrueVal;
 454   ConstantInt *TheFalseVal;
 455
 456   LLVMContextImpl();
 457   LLVMContextImpl(const LLVMContextImpl&);
 458
 459   friend class ConstantInt;
 460   friend class ConstantFP;
 461   friend class ConstantStruct;
 462   friend class ConstantArray;
 463   friend class ConstantVector;
 464   friend class ConstantAggregateZero;
 465 public:
 466   LLVMContextImpl(LLVMContext &C);
 467
 468   MDString *getMDString(const char *StrBegin, unsigned StrLength);
 469
 470   MDNode *getMDNode(Value*const* Vals, unsigned NumVals);
 471
 472   void erase(MDString *M);
 473   void erase(MDNode *M);
 474 };
 475
 476 }
 477
 478 #endif