1 //===--------------- LLVMContextImpl.cpp - Implementation ------*- C++ -*--===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements LLVMContextImpl, the opaque implementation
13 //===----------------------------------------------------------------------===//
15 #include "LLVMContextImpl.h"
16 #include "llvm/Constants.h"
17 #include "llvm/DerivedTypes.h"
18 #include "llvm/LLVMContext.h"
19 #include "llvm/MDNode.h"
22 static char getValType(ConstantAggregateZero *CPZ) { return 0; }
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)));
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) {
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);
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!");
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);
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.
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.
88 template<class ValType, class TypeClass, class ConstantClass,
89 bool HasLargeKey /*true for arrays and structs*/ >
90 class VISIBILITY_HIDDEN ValueMap : public AbstractTypeUser {
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;
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
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;
108 /// AbstractTypeMap - Map for abstract type constants.
110 AbstractTypeMapTy AbstractTypeMap;
112 /// ValueMapLock - Mutex for this map.
113 sys::SmartMutex<true> ValueMapLock;
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(); }
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 *>
130 std::pair<typename MapTy::iterator, bool> IP = Map.insert(InsertVal);
136 typename MapTy::iterator FindExistingElement(ConstantClass *CP) {
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!");
145 typename MapTy::iterator I =
146 Map.find(MapKey(static_cast<const TypeClass*>(CP->getRawType()),
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)
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);
162 assert(Result->getType() == Ty && "Type specified is not correct!");
163 I = Map.insert(I, std::make_pair(MapKey(Ty, V), Result));
165 if (HasLargeKey) // Remember the reverse mapping if needed.
166 InverseMap.insert(std::make_pair(Result, I));
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);
174 if (TI == AbstractTypeMap.end()) {
175 // Add ourselves to the ATU list of the type.
176 cast<DerivedType>(Ty)->addAbstractTypeUser(this);
178 AbstractTypeMap.insert(TI, std::make_pair(Ty, I));
186 /// getOrCreate - Return the specified constant from the map, creating it if
188 ConstantClass *getOrCreate(const TypeClass *Ty, const ValType &V) {
189 sys::SmartScopedLock<true> Lock(ValueMapLock);
190 MapKey Lookup(Ty, V);
191 ConstantClass* Result = 0;
193 typename MapTy::iterator I = Map.find(Lookup);
196 Result = static_cast<ConstantClass *>(I->second);
199 // If no preexisting value, create one now...
200 Result = Create(Ty, V, I);
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?");
212 if (HasLargeKey) // Remember the reverse mapping if needed.
213 InverseMap.erase(CP);
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;
227 // First check the entry before this one...
228 if (TmpIt != Map.begin()) {
230 if (TmpIt->first.first != Ty) // Not the same type, move back...
234 // If we didn't find the same type, try to move forward...
235 if (TmpIt == ATMEntryIt) {
237 if (TmpIt == Map.end() || TmpIt->first.first != Ty)
238 --TmpIt; // No entry afterwards with the same type
241 // If there is another entry in the map of the same abstract type,
242 // update the AbstractTypeMap entry now.
243 if (TmpIt != ATMEntryIt) {
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);
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
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?");
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)
280 // Remove the old entry from the map.
283 // Update the inverse map so that we know that this constant is now
284 // located at descriptor I.
286 assert(I->second == C && "Bad inversemap entry!");
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));
296 assert(I != AbstractTypeMap.end() &&
297 "Abstract type not in AbstractTypeMap?");
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.
303 ConvertConstantType<ConstantClass,
305 static_cast<ConstantClass *>(I->second->second),
306 cast<TypeClass>(NewTy));
308 I = AbstractTypeMap.find(cast<Type>(OldTy));
309 } while (I != AbstractTypeMap.end());
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);
319 DOUT << "Constant.cpp: ValueMap\n";
323 LLVMContextImpl::LLVMContextImpl(LLVMContext &C) :
324 Context(C), TheTrueVal(0), TheFalseVal(0) {
325 AggZeroConstants = new ValueMap<char, Type, ConstantAggregateZero>();
326 ArrayConstants = new ArrayConstantsTy();
329 LLVMContextImpl::~LLVMContextImpl() {
330 delete AggZeroConstants;
331 delete ArrayConstants;
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);
345 ConstantsLock.reader_acquire();
346 ConstantInt *&Slot = IntConstants[Key];
347 ConstantsLock.reader_release();
350 sys::SmartScopedWriter<true> Writer(ConstantsLock);
351 ConstantInt *&NewSlot = IntConstants[Key];
353 NewSlot = new ConstantInt(ITy, V);
362 ConstantFP *LLVMContextImpl::getConstantFP(const APFloat &V) {
363 DenseMapAPFloatKeyInfo::KeyTy Key(V);
365 ConstantsLock.reader_acquire();
366 ConstantFP *&Slot = FPConstants[Key];
367 ConstantsLock.reader_release();
370 sys::SmartScopedWriter<true> Writer(ConstantsLock);
371 ConstantFP *&NewSlot = FPConstants[Key];
374 if (&V.getSemantics() == &APFloat::IEEEsingle)
376 else if (&V.getSemantics() == &APFloat::IEEEdouble)
378 else if (&V.getSemantics() == &APFloat::x87DoubleExtended)
379 Ty = Type::X86_FP80Ty;
380 else if (&V.getSemantics() == &APFloat::IEEEquad)
383 assert(&V.getSemantics() == &APFloat::PPCDoubleDouble &&
384 "Unknown FP format");
385 Ty = Type::PPC_FP128Ty;
387 NewSlot = new ConstantFP(Ty, V);
396 MDString *LLVMContextImpl::getMDString(const char *StrBegin,
397 unsigned StrLength) {
398 sys::SmartScopedWriter<true> Writer(ConstantsLock);
399 StringMapEntry<MDString *> &Entry =
400 MDStringCache.GetOrCreateValue(StringRef(StrBegin, StrLength));
401 MDString *&S = Entry.getValue();
402 if (!S) S = new MDString(Entry.getKeyData(),
403 Entry.getKeyLength());
408 MDNode *LLVMContextImpl::getMDNode(Value*const* Vals, unsigned NumVals) {
410 for (unsigned i = 0; i != NumVals; ++i)
411 ID.AddPointer(Vals[i]);
413 ConstantsLock.reader_acquire();
415 MDNode *N = MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint);
416 ConstantsLock.reader_release();
419 sys::SmartScopedWriter<true> Writer(ConstantsLock);
420 N = MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint);
422 // InsertPoint will have been set by the FindNodeOrInsertPos call.
423 N = new MDNode(Vals, NumVals);
424 MDNodeSet.InsertNode(N, InsertPoint);
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!");
436 // Implicitly locked.
437 return AggZeroConstants->getOrCreate(Ty, 0);
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
445 if (!C->isNullValue()) {
446 // Implicitly locked.
447 return ArrayConstants->getOrCreate(Ty, V);
449 for (unsigned i = 1, e = V.size(); i != e; ++i)
451 // Implicitly locked.
452 return ArrayConstants->getOrCreate(Ty, V);
456 return Context.getConstantAggregateZero(Ty);
459 // *** erase methods ***
461 void LLVMContextImpl::erase(MDString *M) {
462 sys::SmartScopedWriter<true> Writer(ConstantsLock);
463 MDStringCache.erase(MDStringCache.find(StringRef(M->StrBegin,
467 void LLVMContextImpl::erase(MDNode *M) {
468 sys::SmartScopedWriter<true> Writer(ConstantsLock);
469 MDNodeSet.RemoveNode(M);
472 void LLVMContextImpl::erase(ConstantAggregateZero *Z) {
473 AggZeroConstants->remove(Z);
476 void LLVMContextImpl::erase(ConstantArray *C) {
477 ArrayConstants->remove(C);
480 // *** RAUW helpers ***
481 Constant *LLVMContextImpl::replaceUsesOfWithOnConstant(ConstantArray *CA,
482 Value *From, Value *To, Use *U) {
483 assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
484 Constant *ToC = cast<Constant>(To);
486 std::pair<ArrayConstantsTy::MapKey, Constant*> Lookup;
487 Lookup.first.first = CA->getType();
490 std::vector<Constant*> &Values = Lookup.first.second;
491 Values.reserve(CA->getNumOperands()); // Build replacement array.
493 // Fill values with the modified operands of the constant array. Also,
494 // compute whether this turns into an all-zeros array.
495 bool isAllZeros = false;
496 unsigned NumUpdated = 0;
497 if (!ToC->isNullValue()) {
498 for (Use *O = CA->OperandList, *E = CA->OperandList + CA->getNumOperands();
500 Constant *Val = cast<Constant>(O->get());
505 Values.push_back(Val);
509 for (Use *O = CA->OperandList, *E = CA->OperandList + CA->getNumOperands();
511 Constant *Val = cast<Constant>(O->get());
516 Values.push_back(Val);
517 if (isAllZeros) isAllZeros = Val->isNullValue();
521 Constant *Replacement = 0;
523 Replacement = Context.getConstantAggregateZero(CA->getType());
525 // Check to see if we have this array type already.
526 sys::SmartScopedWriter<true> Writer(ConstantsLock);
528 ArrayConstantsTy::MapTy::iterator I =
529 ArrayConstants->InsertOrGetItem(Lookup, Exists);
532 Replacement = I->second;
534 // Okay, the new shape doesn't exist in the system yet. Instead of
535 // creating a new constant array, inserting it, replaceallusesof'ing the
536 // old with the new, then deleting the old... just update the current one
538 ArrayConstants->MoveConstantToNewSlot(CA, I);
540 // Update to the new value. Optimize for the case when we have a single
541 // operand that we're changing, but handle bulk updates efficiently.
542 if (NumUpdated == 1) {
543 unsigned OperandToUpdate = U - CA->OperandList;
544 assert(CA->getOperand(OperandToUpdate) == From &&
545 "ReplaceAllUsesWith broken!");
546 CA->setOperand(OperandToUpdate, ToC);
548 for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i)
549 if (CA->getOperand(i) == From)
550 CA->setOperand(i, ToC);