lib/VMCore/LLVMContextImpl.cpp

   1 //===--------------- LLVMContextImpl.cpp - 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 implements LLVMContextImpl, the opaque implementation
  11 //  of LLVMContext.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "LLVMContextImpl.h"
  16 #include "llvm/Constants.h"
  17 #include "llvm/DerivedTypes.h"
  18 #include "llvm/LLVMContext.h"
  19 #include "llvm/MDNode.h"
  20 using namespace llvm;
  21
  22 static char getValType(ConstantAggregateZero *CPZ) { return 0; }
  23
  24 namespace llvm {
  25 template<typename T, typename Alloc>
  26 struct VISIBILITY_HIDDEN ConstantTraits< std::vector<T, Alloc> > {
  27   static unsigned uses(const std::vector<T, Alloc>& v) {
  28     return v.size();
  29   }
  30 };
  31
  32 template<class ConstantClass, class TypeClass, class ValType>
  33 struct VISIBILITY_HIDDEN ConstantCreator {
  34   static ConstantClass *create(const TypeClass *Ty, const ValType &V) {
  35     return new(ConstantTraits<ValType>::uses(V)) ConstantClass(Ty, V);
  36   }
  37 };
  38
  39 template<class ConstantClass, class TypeClass>
  40 struct VISIBILITY_HIDDEN ConvertConstantType {
  41   static void convert(ConstantClass *OldC, const TypeClass *NewTy) {
  42     llvm_unreachable("This type cannot be converted!");
  43   }
  44 };
  45
  46 // ConstantAggregateZero does not take extra "value" argument...
  47 template<class ValType>
  48 struct ConstantCreator<ConstantAggregateZero, Type, ValType> {
  49   static ConstantAggregateZero *create(const Type *Ty, const ValType &V){
  50     return new ConstantAggregateZero(Ty);
  51   }
  52 };
  53
  54 template<>
  55 struct ConvertConstantType<ConstantAggregateZero, Type> {
  56   static void convert(ConstantAggregateZero *OldC, const Type *NewTy) {
  57     // Make everyone now use a constant of the new type...
  58     Constant *New = NewTy->getContext().getConstantAggregateZero(NewTy);
  59     assert(New != OldC && "Didn't replace constant??");
  60     OldC->uncheckedReplaceAllUsesWith(New);
  61     OldC->destroyConstant();     // This constant is now dead, destroy it.
  62   }
  63 };
  64 }
  65
  66 template<class ValType, class TypeClass, class ConstantClass,
  67          bool HasLargeKey  /*true for arrays and structs*/ >
  68 class VISIBILITY_HIDDEN ContextValueMap : public AbstractTypeUser {
  69 public:
  70   typedef std::pair<const Type*, ValType> MapKey;
  71   typedef std::map<MapKey, Constant *> MapTy;
  72   typedef std::map<Constant*, typename MapTy::iterator> InverseMapTy;
  73   typedef std::map<const Type*, typename MapTy::iterator> AbstractTypeMapTy;
  74 private:
  75   /// Map - This is the main map from the element descriptor to the Constants.
  76   /// This is the primary way we avoid creating two of the same shape
  77   /// constant.
  78   MapTy Map;
  79
  80   /// InverseMap - If "HasLargeKey" is true, this contains an inverse mapping
  81   /// from the constants to their element in Map.  This is important for
  82   /// removal of constants from the array, which would otherwise have to scan
  83   /// through the map with very large keys.
  84   InverseMapTy InverseMap;
  85
  86   /// AbstractTypeMap - Map for abstract type constants.
  87   ///
  88   AbstractTypeMapTy AbstractTypeMap;
  89
  90   /// ValueMapLock - Mutex for this map.
  91   sys::SmartMutex<true> ValueMapLock;
  92
  93 public:
  94   // NOTE: This function is not locked.  It is the caller's responsibility
  95   // to enforce proper synchronization.
  96   typename MapTy::iterator map_end() { return Map.end(); }
  97
  98   /// InsertOrGetItem - Return an iterator for the specified element.
  99   /// If the element exists in the map, the returned iterator points to the
 100   /// entry and Exists=true.  If not, the iterator points to the newly
 101   /// inserted entry and returns Exists=false.  Newly inserted entries have
 102   /// I->second == 0, and should be filled in.
 103   /// NOTE: This function is not locked.  It is the caller's responsibility
 104   // to enforce proper synchronization.
 105   typename MapTy::iterator InsertOrGetItem(std::pair<MapKey, Constant *>
 106                                  &InsertVal,
 107                                  bool &Exists) {
 108     std::pair<typename MapTy::iterator, bool> IP = Map.insert(InsertVal);
 109     Exists = !IP.second;
 110     return IP.first;
 111   }
 112
 113 private:
 114   typename MapTy::iterator FindExistingElement(ConstantClass *CP) {
 115     if (HasLargeKey) {
 116       typename InverseMapTy::iterator IMI = InverseMap.find(CP);
 117       assert(IMI != InverseMap.end() && IMI->second != Map.end() &&
 118              IMI->second->second == CP &&
 119              "InverseMap corrupt!");
 120       return IMI->second;
 121     }
 122
 123     typename MapTy::iterator I =
 124       Map.find(MapKey(static_cast<const TypeClass*>(CP->getRawType()),
 125                       getValType(CP)));
 126     if (I == Map.end() || I->second != CP) {
 127       // FIXME: This should not use a linear scan.  If this gets to be a
 128       // performance problem, someone should look at this.
 129       for (I = Map.begin(); I != Map.end() && I->second != CP; ++I)
 130         /* empty */;
 131     }
 132     return I;
 133   }
 134
 135   ConstantClass* Create(const TypeClass *Ty, const ValType &V,
 136                         typename MapTy::iterator I) {
 137     ConstantClass* Result =
 138       ConstantCreator<ConstantClass,TypeClass,ValType>::create(Ty, V);
 139
 140     assert(Result->getType() == Ty && "Type specified is not correct!");
 141     I = Map.insert(I, std::make_pair(MapKey(Ty, V), Result));
 142
 143     if (HasLargeKey)  // Remember the reverse mapping if needed.
 144       InverseMap.insert(std::make_pair(Result, I));
 145
 146     // If the type of the constant is abstract, make sure that an entry
 147     // exists for it in the AbstractTypeMap.
 148     if (Ty->isAbstract()) {
 149       typename AbstractTypeMapTy::iterator TI =
 150                                                AbstractTypeMap.find(Ty);
 151
 152       if (TI == AbstractTypeMap.end()) {
 153         // Add ourselves to the ATU list of the type.
 154         cast<DerivedType>(Ty)->addAbstractTypeUser(this);
 155
 156         AbstractTypeMap.insert(TI, std::make_pair(Ty, I));
 157       }
 158     }
 159
 160     return Result;
 161   }
 162 public:
 163
 164   /// getOrCreate - Return the specified constant from the map, creating it if
 165   /// necessary.
 166   ConstantClass *getOrCreate(const TypeClass *Ty, const ValType &V) {
 167     sys::SmartScopedLock<true> Lock(ValueMapLock);
 168     MapKey Lookup(Ty, V);
 169     ConstantClass* Result = 0;
 170
 171     typename MapTy::iterator I = Map.find(Lookup);
 172     // Is it in the map?
 173     if (I != Map.end())
 174       Result = static_cast<ConstantClass *>(I->second);
 175
 176     if (!Result) {
 177       // If no preexisting value, create one now...
 178       Result = Create(Ty, V, I);
 179     }
 180
 181     return Result;
 182   }
 183
 184   void remove(ConstantClass *CP) {
 185     sys::SmartScopedLock<true> Lock(ValueMapLock);
 186     typename MapTy::iterator I = FindExistingElement(CP);
 187     assert(I != Map.end() && "Constant not found in constant table!");
 188     assert(I->second == CP && "Didn't find correct element?");
 189
 190     if (HasLargeKey)  // Remember the reverse mapping if needed.
 191       InverseMap.erase(CP);
 192
 193     // Now that we found the entry, make sure this isn't the entry that
 194     // the AbstractTypeMap points to.
 195     const TypeClass *Ty = static_cast<const TypeClass *>(I->first.first);
 196     if (Ty->isAbstract()) {
 197       assert(AbstractTypeMap.count(Ty) &&
 198              "Abstract type not in AbstractTypeMap?");
 199       typename MapTy::iterator &ATMEntryIt = AbstractTypeMap[Ty];
 200       if (ATMEntryIt == I) {
 201         // Yes, we are removing the representative entry for this type.
 202         // See if there are any other entries of the same type.
 203         typename MapTy::iterator TmpIt = ATMEntryIt;
 204
 205         // First check the entry before this one...
 206         if (TmpIt != Map.begin()) {
 207           --TmpIt;
 208           if (TmpIt->first.first != Ty) // Not the same type, move back...
 209             ++TmpIt;
 210         }
 211
 212         // If we didn't find the same type, try to move forward...
 213         if (TmpIt == ATMEntryIt) {
 214           ++TmpIt;
 215           if (TmpIt == Map.end() || TmpIt->first.first != Ty)
 216             --TmpIt;   // No entry afterwards with the same type
 217         }
 218
 219         // If there is another entry in the map of the same abstract type,
 220         // update the AbstractTypeMap entry now.
 221         if (TmpIt != ATMEntryIt) {
 222           ATMEntryIt = TmpIt;
 223         } else {
 224           // Otherwise, we are removing the last instance of this type
 225           // from the table.  Remove from the ATM, and from user list.
 226           cast<DerivedType>(Ty)->removeAbstractTypeUser(this);
 227           AbstractTypeMap.erase(Ty);
 228         }
 229       }
 230     }
 231
 232     Map.erase(I);
 233   }
 234
 235
 236   /// MoveConstantToNewSlot - If we are about to change C to be the element
 237   /// specified by I, update our internal data structures to reflect this
 238   /// fact.
 239   /// NOTE: This function is not locked. It is the responsibility of the
 240   /// caller to enforce proper synchronization if using this method.
 241   void MoveConstantToNewSlot(ConstantClass *C, typename MapTy::iterator I) {
 242     // First, remove the old location of the specified constant in the map.
 243     typename MapTy::iterator OldI = FindExistingElement(C);
 244     assert(OldI != Map.end() && "Constant not found in constant table!");
 245     assert(OldI->second == C && "Didn't find correct element?");
 246
 247     // If this constant is the representative element for its abstract type,
 248     // update the AbstractTypeMap so that the representative element is I.
 249     if (C->getType()->isAbstract()) {
 250       typename AbstractTypeMapTy::iterator ATI =
 251           AbstractTypeMap.find(C->getType());
 252       assert(ATI != AbstractTypeMap.end() &&
 253              "Abstract type not in AbstractTypeMap?");
 254       if (ATI->second == OldI)
 255         ATI->second = I;
 256     }
 257
 258     // Remove the old entry from the map.
 259     Map.erase(OldI);
 260
 261     // Update the inverse map so that we know that this constant is now
 262     // located at descriptor I.
 263     if (HasLargeKey) {
 264       assert(I->second == C && "Bad inversemap entry!");
 265       InverseMap[C] = I;
 266     }
 267   }
 268
 269   void refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
 270     sys::SmartScopedLock<true> Lock(ValueMapLock);
 271     typename AbstractTypeMapTy::iterator I =
 272       AbstractTypeMap.find(cast<Type>(OldTy));
 273
 274     assert(I != AbstractTypeMap.end() &&
 275            "Abstract type not in AbstractTypeMap?");
 276
 277     // Convert a constant at a time until the last one is gone.  The last one
 278     // leaving will remove() itself, causing the AbstractTypeMapEntry to be
 279     // eliminated eventually.
 280     do {
 281       ConvertConstantType<ConstantClass,
 282                           TypeClass>::convert(
 283                               static_cast<ConstantClass *>(I->second->second),
 284                                               cast<TypeClass>(NewTy));
 285
 286       I = AbstractTypeMap.find(cast<Type>(OldTy));
 287     } while (I != AbstractTypeMap.end());
 288   }
 289
 290   // If the type became concrete without being refined to any other existing
 291   // type, we just remove ourselves from the ATU list.
 292   void typeBecameConcrete(const DerivedType *AbsTy) {
 293     AbsTy->removeAbstractTypeUser(this);
 294   }
 295
 296   void dump() const {
 297     DOUT << "Constant.cpp: ValueMap\n";
 298   }
 299 };
 300
 301 LLVMContextImpl::LLVMContextImpl(LLVMContext &C) :
 302     Context(C), TheTrueVal(0), TheFalseVal(0) {
 303   AggZeroConstants = new ContextValueMap<char, Type, ConstantAggregateZero>();
 304 }
 305
 306 LLVMContextImpl::~LLVMContextImpl() {
 307   delete AggZeroConstants;
 308 }
 309
 310 // Get a ConstantInt from an APInt. Note that the value stored in the DenseMap
 311 // as the key, is a DenseMapAPIntKeyInfo::KeyTy which has provided the
 312 // operator== and operator!= to ensure that the DenseMap doesn't attempt to
 313 // compare APInt's of different widths, which would violate an APInt class
 314 // invariant which generates an assertion.
 315 ConstantInt *LLVMContextImpl::getConstantInt(const APInt& V) {
 316   // Get the corresponding integer type for the bit width of the value.
 317   const IntegerType *ITy = Context.getIntegerType(V.getBitWidth());
 318   // get an existing value or the insertion position
 319   DenseMapAPIntKeyInfo::KeyTy Key(V, ITy);
 320
 321   ConstantsLock.reader_acquire();
 322   ConstantInt *&Slot = IntConstants[Key];
 323   ConstantsLock.reader_release();
 324
 325   if (!Slot) {
 326     sys::SmartScopedWriter<true> Writer(ConstantsLock);
 327     ConstantInt *&NewSlot = IntConstants[Key];
 328     if (!Slot) {
 329       NewSlot = new ConstantInt(ITy, V);
 330     }
 331
 332     return NewSlot;
 333   } else {
 334     return Slot;
 335   }
 336 }
 337
 338 ConstantFP *LLVMContextImpl::getConstantFP(const APFloat &V) {
 339   DenseMapAPFloatKeyInfo::KeyTy Key(V);
 340
 341   ConstantsLock.reader_acquire();
 342   ConstantFP *&Slot = FPConstants[Key];
 343   ConstantsLock.reader_release();
 344
 345   if (!Slot) {
 346     sys::SmartScopedWriter<true> Writer(ConstantsLock);
 347     ConstantFP *&NewSlot = FPConstants[Key];
 348     if (!NewSlot) {
 349       const Type *Ty;
 350       if (&V.getSemantics() == &APFloat::IEEEsingle)
 351         Ty = Type::FloatTy;
 352       else if (&V.getSemantics() == &APFloat::IEEEdouble)
 353         Ty = Type::DoubleTy;
 354       else if (&V.getSemantics() == &APFloat::x87DoubleExtended)
 355         Ty = Type::X86_FP80Ty;
 356       else if (&V.getSemantics() == &APFloat::IEEEquad)
 357         Ty = Type::FP128Ty;
 358       else {
 359         assert(&V.getSemantics() == &APFloat::PPCDoubleDouble &&
 360                "Unknown FP format");
 361         Ty = Type::PPC_FP128Ty;
 362       }
 363       NewSlot = new ConstantFP(Ty, V);
 364     }
 365
 366     return NewSlot;
 367   }
 368
 369   return Slot;
 370 }
 371
 372 MDString *LLVMContextImpl::getMDString(const char *StrBegin,
 373                                        const char *StrEnd) {
 374   sys::SmartScopedWriter<true> Writer(ConstantsLock);
 375   StringMapEntry<MDString *> &Entry = MDStringCache.GetOrCreateValue(
 376                                         StrBegin, StrEnd);
 377   MDString *&S = Entry.getValue();
 378   if (!S) S = new MDString(Entry.getKeyData(),
 379                            Entry.getKeyData() + Entry.getKeyLength());
 380
 381   return S;
 382 }
 383
 384 MDNode *LLVMContextImpl::getMDNode(Value*const* Vals, unsigned NumVals) {
 385   FoldingSetNodeID ID;
 386   for (unsigned i = 0; i != NumVals; ++i)
 387     ID.AddPointer(Vals[i]);
 388
 389   ConstantsLock.reader_acquire();
 390   void *InsertPoint;
 391   MDNode *N = MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint);
 392   ConstantsLock.reader_release();
 393
 394   if (!N) {
 395     sys::SmartScopedWriter<true> Writer(ConstantsLock);
 396     N = MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint);
 397     if (!N) {
 398       // InsertPoint will have been set by the FindNodeOrInsertPos call.
 399       N = new(0) MDNode(Vals, NumVals);
 400       MDNodeSet.InsertNode(N, InsertPoint);
 401     }
 402   }
 403
 404   return N;
 405 }
 406
 407 ConstantAggregateZero*
 408 LLVMContextImpl::getConstantAggregateZero(const Type *Ty) {
 409   assert((isa<StructType>(Ty) || isa<ArrayType>(Ty) || isa<VectorType>(Ty)) &&
 410          "Cannot create an aggregate zero of non-aggregate type!");
 411
 412   // Implicitly locked.
 413   return AggZeroConstants->getOrCreate(Ty, 0);
 414 }
 415
 416 // *** erase methods ***
 417
 418 void LLVMContextImpl::erase(MDString *M) {
 419   sys::SmartScopedWriter<true> Writer(ConstantsLock);
 420   MDStringCache.erase(MDStringCache.find(M->StrBegin, M->StrEnd));
 421 }
 422
 423 void LLVMContextImpl::erase(MDNode *M) {
 424   sys::SmartScopedWriter<true> Writer(ConstantsLock);
 425   MDNodeSet.RemoveNode(M);
 426 }
 427
 428 void LLVMContextImpl::erase(ConstantAggregateZero *Z) {
 429   AggZeroConstants->remove(Z);
 430 }