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 static std::vector<Constant*> getValType(ConstantArray *CA) {
  25   std::vector<Constant*> Elements;
  26   Elements.reserve(CA->getNumOperands());
  27   for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i)
  28     Elements.push_back(cast<Constant>(CA->getOperand(i)));
  29   return Elements;
  30 }
  31
  32 namespace llvm {
  33 template<typename T, typename Alloc>
  34 struct VISIBILITY_HIDDEN ConstantTraits< std::vector<T, Alloc> > {
  35   static unsigned uses(const std::vector<T, Alloc>& v) {
  36     return v.size();
  37   }
  38 };
  39
  40 template<class ConstantClass, class TypeClass, class ValType>
  41 struct VISIBILITY_HIDDEN ConstantCreator {
  42   static ConstantClass *create(const TypeClass *Ty, const ValType &V) {
  43     return new(ConstantTraits<ValType>::uses(V)) ConstantClass(Ty, V);
  44   }
  45 };
  46
  47 template<class ConstantClass, class TypeClass>
  48 struct VISIBILITY_HIDDEN ConvertConstantType {
  49   static void convert(ConstantClass *OldC, const TypeClass *NewTy) {
  50     llvm_unreachable("This type cannot be converted!");
  51   }
  52 };
  53
  54 // ConstantAggregateZero does not take extra "value" argument...
  55 template<class ValType>
  56 struct ConstantCreator<ConstantAggregateZero, Type, ValType> {
  57   static ConstantAggregateZero *create(const Type *Ty, const ValType &V){
  58     return new ConstantAggregateZero(Ty);
  59   }
  60 };
  61
  62 template<>
  63 struct ConvertConstantType<ConstantAggregateZero, Type> {
  64   static void convert(ConstantAggregateZero *OldC, const Type *NewTy) {
  65     // Make everyone now use a constant of the new type...
  66     Constant *New = NewTy->getContext().getConstantAggregateZero(NewTy);
  67     assert(New != OldC && "Didn't replace constant??");
  68     OldC->uncheckedReplaceAllUsesWith(New);
  69     OldC->destroyConstant();     // This constant is now dead, destroy it.
  70   }
  71 };
  72
  73 template<>
  74 struct ConvertConstantType<ConstantArray, ArrayType> {
  75   static void convert(ConstantArray *OldC, const ArrayType *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 = NewTy->getContext().getConstantArray(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
  88 template<class ValType, class TypeClass, class ConstantClass,
  89          bool HasLargeKey  /*true for arrays and structs*/ >
  90 class VISIBILITY_HIDDEN ValueMap : public AbstractTypeUser {
  91 public:
  92   typedef std::pair<const Type*, ValType> MapKey;
  93   typedef std::map<MapKey, Constant *> MapTy;
  94   typedef std::map<Constant*, typename MapTy::iterator> InverseMapTy;
  95   typedef std::map<const Type*, typename MapTy::iterator> AbstractTypeMapTy;
  96 private:
  97   /// Map - This is the main map from the element descriptor to the Constants.
  98   /// This is the primary way we avoid creating two of the same shape
  99   /// constant.
 100   MapTy Map;
 101
 102   /// InverseMap - If "HasLargeKey" is true, this contains an inverse mapping
 103   /// from the constants to their element in Map.  This is important for
 104   /// removal of constants from the array, which would otherwise have to scan
 105   /// through the map with very large keys.
 106   InverseMapTy InverseMap;
 107
 108   /// AbstractTypeMap - Map for abstract type constants.
 109   ///
 110   AbstractTypeMapTy AbstractTypeMap;
 111
 112   /// ValueMapLock - Mutex for this map.
 113   sys::SmartMutex<true> ValueMapLock;
 114
 115 public:
 116   // NOTE: This function is not locked.  It is the caller's responsibility
 117   // to enforce proper synchronization.
 118   typename MapTy::iterator map_end() { return Map.end(); }
 119
 120   /// InsertOrGetItem - Return an iterator for the specified element.
 121   /// If the element exists in the map, the returned iterator points to the
 122   /// entry and Exists=true.  If not, the iterator points to the newly
 123   /// inserted entry and returns Exists=false.  Newly inserted entries have
 124   /// I->second == 0, and should be filled in.
 125   /// NOTE: This function is not locked.  It is the caller's responsibility
 126   // to enforce proper synchronization.
 127   typename MapTy::iterator InsertOrGetItem(std::pair<MapKey, Constant *>
 128                                  &InsertVal,
 129                                  bool &Exists) {
 130     std::pair<typename MapTy::iterator, bool> IP = Map.insert(InsertVal);
 131     Exists = !IP.second;
 132     return IP.first;
 133   }
 134
 135 private:
 136   typename MapTy::iterator FindExistingElement(ConstantClass *CP) {
 137     if (HasLargeKey) {
 138       typename InverseMapTy::iterator IMI = InverseMap.find(CP);
 139       assert(IMI != InverseMap.end() && IMI->second != Map.end() &&
 140              IMI->second->second == CP &&
 141              "InverseMap corrupt!");
 142       return IMI->second;
 143     }
 144
 145     typename MapTy::iterator I =
 146       Map.find(MapKey(static_cast<const TypeClass*>(CP->getRawType()),
 147                       getValType(CP)));
 148     if (I == Map.end() || I->second != CP) {
 149       // FIXME: This should not use a linear scan.  If this gets to be a
 150       // performance problem, someone should look at this.
 151       for (I = Map.begin(); I != Map.end() && I->second != CP; ++I)
 152         /* empty */;
 153     }
 154     return I;
 155   }
 156
 157   ConstantClass* Create(const TypeClass *Ty, const ValType &V,
 158                         typename MapTy::iterator I) {
 159     ConstantClass* Result =
 160       ConstantCreator<ConstantClass,TypeClass,ValType>::create(Ty, V);
 161
 162     assert(Result->getType() == Ty && "Type specified is not correct!");
 163     I = Map.insert(I, std::make_pair(MapKey(Ty, V), Result));
 164
 165     if (HasLargeKey)  // Remember the reverse mapping if needed.
 166       InverseMap.insert(std::make_pair(Result, I));
 167
 168     // If the type of the constant is abstract, make sure that an entry
 169     // exists for it in the AbstractTypeMap.
 170     if (Ty->isAbstract()) {
 171       typename AbstractTypeMapTy::iterator TI =
 172                                                AbstractTypeMap.find(Ty);
 173
 174       if (TI == AbstractTypeMap.end()) {
 175         // Add ourselves to the ATU list of the type.
 176         cast<DerivedType>(Ty)->addAbstractTypeUser(this);
 177
 178         AbstractTypeMap.insert(TI, std::make_pair(Ty, I));
 179       }
 180     }
 181
 182     return Result;
 183   }
 184 public:
 185
 186   /// getOrCreate - Return the specified constant from the map, creating it if
 187   /// necessary.
 188   ConstantClass *getOrCreate(const TypeClass *Ty, const ValType &V) {
 189     sys::SmartScopedLock<true> Lock(ValueMapLock);
 190     MapKey Lookup(Ty, V);
 191     ConstantClass* Result = 0;
 192
 193     typename MapTy::iterator I = Map.find(Lookup);
 194     // Is it in the map?
 195     if (I != Map.end())
 196       Result = static_cast<ConstantClass *>(I->second);
 197
 198     if (!Result) {
 199       // If no preexisting value, create one now...
 200       Result = Create(Ty, V, I);
 201     }
 202
 203     return Result;
 204   }
 205
 206   void remove(ConstantClass *CP) {
 207     sys::SmartScopedLock<true> Lock(ValueMapLock);
 208     typename MapTy::iterator I = FindExistingElement(CP);
 209     assert(I != Map.end() && "Constant not found in constant table!");
 210     assert(I->second == CP && "Didn't find correct element?");
 211
 212     if (HasLargeKey)  // Remember the reverse mapping if needed.
 213       InverseMap.erase(CP);
 214
 215     // Now that we found the entry, make sure this isn't the entry that
 216     // the AbstractTypeMap points to.
 217     const TypeClass *Ty = static_cast<const TypeClass *>(I->first.first);
 218     if (Ty->isAbstract()) {
 219       assert(AbstractTypeMap.count(Ty) &&
 220              "Abstract type not in AbstractTypeMap?");
 221       typename MapTy::iterator &ATMEntryIt = AbstractTypeMap[Ty];
 222       if (ATMEntryIt == I) {
 223         // Yes, we are removing the representative entry for this type.
 224         // See if there are any other entries of the same type.
 225         typename MapTy::iterator TmpIt = ATMEntryIt;
 226
 227         // First check the entry before this one...
 228         if (TmpIt != Map.begin()) {
 229           --TmpIt;
 230           if (TmpIt->first.first != Ty) // Not the same type, move back...
 231             ++TmpIt;
 232         }
 233
 234         // If we didn't find the same type, try to move forward...
 235         if (TmpIt == ATMEntryIt) {
 236           ++TmpIt;
 237           if (TmpIt == Map.end() || TmpIt->first.first != Ty)
 238             --TmpIt;   // No entry afterwards with the same type
 239         }
 240
 241         // If there is another entry in the map of the same abstract type,
 242         // update the AbstractTypeMap entry now.
 243         if (TmpIt != ATMEntryIt) {
 244           ATMEntryIt = TmpIt;
 245         } else {
 246           // Otherwise, we are removing the last instance of this type
 247           // from the table.  Remove from the ATM, and from user list.
 248           cast<DerivedType>(Ty)->removeAbstractTypeUser(this);
 249           AbstractTypeMap.erase(Ty);
 250         }
 251       }
 252     }
 253
 254     Map.erase(I);
 255   }
 256
 257
 258   /// MoveConstantToNewSlot - If we are about to change C to be the element
 259   /// specified by I, update our internal data structures to reflect this
 260   /// fact.
 261   /// NOTE: This function is not locked. It is the responsibility of the
 262   /// caller to enforce proper synchronization if using this method.
 263   void MoveConstantToNewSlot(ConstantClass *C, typename MapTy::iterator I) {
 264     // First, remove the old location of the specified constant in the map.
 265     typename MapTy::iterator OldI = FindExistingElement(C);
 266     assert(OldI != Map.end() && "Constant not found in constant table!");
 267     assert(OldI->second == C && "Didn't find correct element?");
 268
 269     // If this constant is the representative element for its abstract type,
 270     // update the AbstractTypeMap so that the representative element is I.
 271     if (C->getType()->isAbstract()) {
 272       typename AbstractTypeMapTy::iterator ATI =
 273           AbstractTypeMap.find(C->getType());
 274       assert(ATI != AbstractTypeMap.end() &&
 275              "Abstract type not in AbstractTypeMap?");
 276       if (ATI->second == OldI)
 277         ATI->second = I;
 278     }
 279
 280     // Remove the old entry from the map.
 281     Map.erase(OldI);
 282
 283     // Update the inverse map so that we know that this constant is now
 284     // located at descriptor I.
 285     if (HasLargeKey) {
 286       assert(I->second == C && "Bad inversemap entry!");
 287       InverseMap[C] = I;
 288     }
 289   }
 290
 291   void refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
 292     sys::SmartScopedLock<true> Lock(ValueMapLock);
 293     typename AbstractTypeMapTy::iterator I =
 294       AbstractTypeMap.find(cast<Type>(OldTy));
 295
 296     assert(I != AbstractTypeMap.end() &&
 297            "Abstract type not in AbstractTypeMap?");
 298
 299     // Convert a constant at a time until the last one is gone.  The last one
 300     // leaving will remove() itself, causing the AbstractTypeMapEntry to be
 301     // eliminated eventually.
 302     do {
 303       ConvertConstantType<ConstantClass,
 304                           TypeClass>::convert(
 305                               static_cast<ConstantClass *>(I->second->second),
 306                                               cast<TypeClass>(NewTy));
 307
 308       I = AbstractTypeMap.find(cast<Type>(OldTy));
 309     } while (I != AbstractTypeMap.end());
 310   }
 311
 312   // If the type became concrete without being refined to any other existing
 313   // type, we just remove ourselves from the ATU list.
 314   void typeBecameConcrete(const DerivedType *AbsTy) {
 315     AbsTy->removeAbstractTypeUser(this);
 316   }
 317
 318   void dump() const {
 319     DOUT << "Constant.cpp: ValueMap\n";
 320   }
 321 };
 322
 323 LLVMContextImpl::LLVMContextImpl(LLVMContext &C) :
 324     Context(C), TheTrueVal(0), TheFalseVal(0) {
 325   AggZeroConstants = new ValueMap<char, Type, ConstantAggregateZero>();
 326   ArrayConstants = new ArrayConstantsTy();
 327 }
 328
 329 LLVMContextImpl::~LLVMContextImpl() {
 330   delete AggZeroConstants;
 331   delete ArrayConstants;
 332 }
 333
 334 // Get a ConstantInt from an APInt. Note that the value stored in the DenseMap
 335 // as the key, is a DenseMapAPIntKeyInfo::KeyTy which has provided the
 336 // operator== and operator!= to ensure that the DenseMap doesn't attempt to
 337 // compare APInt's of different widths, which would violate an APInt class
 338 // invariant which generates an assertion.
 339 ConstantInt *LLVMContextImpl::getConstantInt(const APInt& V) {
 340   // Get the corresponding integer type for the bit width of the value.
 341   const IntegerType *ITy = Context.getIntegerType(V.getBitWidth());
 342   // get an existing value or the insertion position
 343   DenseMapAPIntKeyInfo::KeyTy Key(V, ITy);
 344
 345   ConstantsLock.reader_acquire();
 346   ConstantInt *&Slot = IntConstants[Key];
 347   ConstantsLock.reader_release();
 348
 349   if (!Slot) {
 350     sys::SmartScopedWriter<true> Writer(ConstantsLock);
 351     ConstantInt *&NewSlot = IntConstants[Key];
 352     if (!Slot) {
 353       NewSlot = new ConstantInt(ITy, V);
 354     }
 355
 356     return NewSlot;
 357   } else {
 358     return Slot;
 359   }
 360 }
 361
 362 ConstantFP *LLVMContextImpl::getConstantFP(const APFloat &V) {
 363   DenseMapAPFloatKeyInfo::KeyTy Key(V);
 364
 365   ConstantsLock.reader_acquire();
 366   ConstantFP *&Slot = FPConstants[Key];
 367   ConstantsLock.reader_release();
 368
 369   if (!Slot) {
 370     sys::SmartScopedWriter<true> Writer(ConstantsLock);
 371     ConstantFP *&NewSlot = FPConstants[Key];
 372     if (!NewSlot) {
 373       const Type *Ty;
 374       if (&V.getSemantics() == &APFloat::IEEEsingle)
 375         Ty = Type::FloatTy;
 376       else if (&V.getSemantics() == &APFloat::IEEEdouble)
 377         Ty = Type::DoubleTy;
 378       else if (&V.getSemantics() == &APFloat::x87DoubleExtended)
 379         Ty = Type::X86_FP80Ty;
 380       else if (&V.getSemantics() == &APFloat::IEEEquad)
 381         Ty = Type::FP128Ty;
 382       else {
 383         assert(&V.getSemantics() == &APFloat::PPCDoubleDouble &&
 384                "Unknown FP format");
 385         Ty = Type::PPC_FP128Ty;
 386       }
 387       NewSlot = new ConstantFP(Ty, V);
 388     }
 389
 390     return NewSlot;
 391   }
 392
 393   return Slot;
 394 }
 395
 396 MDString *LLVMContextImpl::getMDString(const char *StrBegin,
 397                                        const char *StrEnd) {
 398   sys::SmartScopedWriter<true> Writer(ConstantsLock);
 399   StringMapEntry<MDString *> &Entry = MDStringCache.GetOrCreateValue(
 400                                         StrBegin, StrEnd);
 401   MDString *&S = Entry.getValue();
 402   if (!S) S = new MDString(Entry.getKeyData(),
 403                            Entry.getKeyData() + Entry.getKeyLength());
 404
 405   return S;
 406 }
 407
 408 MDNode *LLVMContextImpl::getMDNode(Value*const* Vals, unsigned NumVals) {
 409   FoldingSetNodeID ID;
 410   for (unsigned i = 0; i != NumVals; ++i)
 411     ID.AddPointer(Vals[i]);
 412
 413   ConstantsLock.reader_acquire();
 414   void *InsertPoint;
 415   MDNode *N = MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint);
 416   ConstantsLock.reader_release();
 417
 418   if (!N) {
 419     sys::SmartScopedWriter<true> Writer(ConstantsLock);
 420     N = MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint);
 421     if (!N) {
 422       // InsertPoint will have been set by the FindNodeOrInsertPos call.
 423       N = new MDNode(Vals, NumVals);
 424       MDNodeSet.InsertNode(N, InsertPoint);
 425     }
 426   }
 427
 428   return N;
 429 }
 430
 431 ConstantAggregateZero*
 432 LLVMContextImpl::getConstantAggregateZero(const Type *Ty) {
 433   assert((isa<StructType>(Ty) || isa<ArrayType>(Ty) || isa<VectorType>(Ty)) &&
 434          "Cannot create an aggregate zero of non-aggregate type!");
 435
 436   // Implicitly locked.
 437   return AggZeroConstants->getOrCreate(Ty, 0);
 438 }
 439
 440 Constant *LLVMContextImpl::getConstantArray(const ArrayType *Ty,
 441                              const std::vector<Constant*> &V) {
 442   // If this is an all-zero array, return a ConstantAggregateZero object
 443   if (!V.empty()) {
 444     Constant *C = V[0];
 445     if (!C->isNullValue()) {
 446       // Implicitly locked.
 447       return ArrayConstants->getOrCreate(Ty, V);
 448     }
 449     for (unsigned i = 1, e = V.size(); i != e; ++i)
 450       if (V[i] != C) {
 451         // Implicitly locked.
 452         return ArrayConstants->getOrCreate(Ty, V);
 453       }
 454   }
 455
 456   return Context.getConstantAggregateZero(Ty);
 457 }
 458
 459 // *** erase methods ***
 460
 461 void LLVMContextImpl::erase(MDString *M) {
 462   sys::SmartScopedWriter<true> Writer(ConstantsLock);
 463   MDStringCache.erase(MDStringCache.find(M->StrBegin, M->StrEnd));
 464 }
 465
 466 void LLVMContextImpl::erase(MDNode *M) {
 467   sys::SmartScopedWriter<true> Writer(ConstantsLock);
 468   MDNodeSet.RemoveNode(M);
 469 }
 470
 471 void LLVMContextImpl::erase(ConstantAggregateZero *Z) {
 472   AggZeroConstants->remove(Z);
 473 }
 474
 475 void LLVMContextImpl::erase(ConstantArray *C) {
 476   ArrayConstants->remove(C);
 477 }
 478
 479 // *** RAUW helpers ***
 480 Constant *LLVMContextImpl::replaceUsesOfWithOnConstant(ConstantArray *CA,
 481                                                Value *From, Value *To, Use *U) {
 482   assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
 483   Constant *ToC = cast<Constant>(To);
 484
 485   std::pair<ArrayConstantsTy::MapKey, Constant*> Lookup;
 486   Lookup.first.first = CA->getType();
 487   Lookup.second = CA;
 488
 489   std::vector<Constant*> &Values = Lookup.first.second;
 490   Values.reserve(CA->getNumOperands());  // Build replacement array.
 491
 492   // Fill values with the modified operands of the constant array.  Also,
 493   // compute whether this turns into an all-zeros array.
 494   bool isAllZeros = false;
 495   unsigned NumUpdated = 0;
 496   if (!ToC->isNullValue()) {
 497     for (Use *O = CA->OperandList, *E = CA->OperandList + CA->getNumOperands();
 498          O != E; ++O) {
 499       Constant *Val = cast<Constant>(O->get());
 500       if (Val == From) {
 501         Val = ToC;
 502         ++NumUpdated;
 503       }
 504       Values.push_back(Val);
 505     }
 506   } else {
 507     isAllZeros = true;
 508     for (Use *O = CA->OperandList, *E = CA->OperandList + CA->getNumOperands();
 509          O != E; ++O) {
 510       Constant *Val = cast<Constant>(O->get());
 511       if (Val == From) {
 512         Val = ToC;
 513         ++NumUpdated;
 514       }
 515       Values.push_back(Val);
 516       if (isAllZeros) isAllZeros = Val->isNullValue();
 517     }
 518   }
 519
 520   Constant *Replacement = 0;
 521   if (isAllZeros) {
 522     Replacement = Context.getConstantAggregateZero(CA->getType());
 523   } else {
 524     // Check to see if we have this array type already.
 525     sys::SmartScopedWriter<true> Writer(ConstantsLock);
 526     bool Exists;
 527     ArrayConstantsTy::MapTy::iterator I =
 528       ArrayConstants->InsertOrGetItem(Lookup, Exists);
 529
 530     if (Exists) {
 531       Replacement = I->second;
 532     } else {
 533       // Okay, the new shape doesn't exist in the system yet.  Instead of
 534       // creating a new constant array, inserting it, replaceallusesof'ing the
 535       // old with the new, then deleting the old... just update the current one
 536       // in place!
 537       ArrayConstants->MoveConstantToNewSlot(CA, I);
 538
 539       // Update to the new value.  Optimize for the case when we have a single
 540       // operand that we're changing, but handle bulk updates efficiently.
 541       if (NumUpdated == 1) {
 542         unsigned OperandToUpdate = U - CA->OperandList;
 543         assert(CA->getOperand(OperandToUpdate) == From &&
 544                "ReplaceAllUsesWith broken!");
 545         CA->setOperand(OperandToUpdate, ToC);
 546       } else {
 547         for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i)
 548           if (CA->getOperand(i) == From)
 549             CA->setOperand(i, ToC);
 550       }
 551       return 0;
 552     }
 553   }
 554
 555   return Replacement;
 556 }
 557