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)));
32 static std::vector<Constant*> getValType(ConstantStruct *CS) {
33 std::vector<Constant*> Elements;
34 Elements.reserve(CS->getNumOperands());
35 for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i)
36 Elements.push_back(cast<Constant>(CS->getOperand(i)));
41 template<typename T, typename Alloc>
42 struct VISIBILITY_HIDDEN ConstantTraits< std::vector<T, Alloc> > {
43 static unsigned uses(const std::vector<T, Alloc>& v) {
48 template<class ConstantClass, class TypeClass, class ValType>
49 struct VISIBILITY_HIDDEN ConstantCreator {
50 static ConstantClass *create(const TypeClass *Ty, const ValType &V) {
51 return new(ConstantTraits<ValType>::uses(V)) ConstantClass(Ty, V);
55 template<class ConstantClass, class TypeClass>
56 struct VISIBILITY_HIDDEN ConvertConstantType {
57 static void convert(ConstantClass *OldC, const TypeClass *NewTy) {
58 llvm_unreachable("This type cannot be converted!");
62 // ConstantAggregateZero does not take extra "value" argument...
63 template<class ValType>
64 struct ConstantCreator<ConstantAggregateZero, Type, ValType> {
65 static ConstantAggregateZero *create(const Type *Ty, const ValType &V){
66 return new ConstantAggregateZero(Ty);
71 struct ConvertConstantType<ConstantAggregateZero, Type> {
72 static void convert(ConstantAggregateZero *OldC, const Type *NewTy) {
73 // Make everyone now use a constant of the new type...
74 Constant *New = NewTy->getContext().getConstantAggregateZero(NewTy);
75 assert(New != OldC && "Didn't replace constant??");
76 OldC->uncheckedReplaceAllUsesWith(New);
77 OldC->destroyConstant(); // This constant is now dead, destroy it.
82 struct ConvertConstantType<ConstantArray, ArrayType> {
83 static void convert(ConstantArray *OldC, const ArrayType *NewTy) {
84 // Make everyone now use a constant of the new type...
85 std::vector<Constant*> C;
86 for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i)
87 C.push_back(cast<Constant>(OldC->getOperand(i)));
88 Constant *New = NewTy->getContext().getConstantArray(NewTy, C);
89 assert(New != OldC && "Didn't replace constant??");
90 OldC->uncheckedReplaceAllUsesWith(New);
91 OldC->destroyConstant(); // This constant is now dead, destroy it.
96 struct ConvertConstantType<ConstantStruct, StructType> {
97 static void convert(ConstantStruct *OldC, const StructType *NewTy) {
98 // Make everyone now use a constant of the new type...
99 std::vector<Constant*> C;
100 for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i)
101 C.push_back(cast<Constant>(OldC->getOperand(i)));
102 Constant *New = NewTy->getContext().getConstantStruct(NewTy, C);
103 assert(New != OldC && "Didn't replace constant??");
105 OldC->uncheckedReplaceAllUsesWith(New);
106 OldC->destroyConstant(); // This constant is now dead, destroy it.
111 template<class ValType, class TypeClass, class ConstantClass,
112 bool HasLargeKey /*true for arrays and structs*/ >
113 class VISIBILITY_HIDDEN ValueMap : public AbstractTypeUser {
115 typedef std::pair<const Type*, ValType> MapKey;
116 typedef std::map<MapKey, Constant *> MapTy;
117 typedef std::map<Constant*, typename MapTy::iterator> InverseMapTy;
118 typedef std::map<const Type*, typename MapTy::iterator> AbstractTypeMapTy;
120 /// Map - This is the main map from the element descriptor to the Constants.
121 /// This is the primary way we avoid creating two of the same shape
125 /// InverseMap - If "HasLargeKey" is true, this contains an inverse mapping
126 /// from the constants to their element in Map. This is important for
127 /// removal of constants from the array, which would otherwise have to scan
128 /// through the map with very large keys.
129 InverseMapTy InverseMap;
131 /// AbstractTypeMap - Map for abstract type constants.
133 AbstractTypeMapTy AbstractTypeMap;
135 /// ValueMapLock - Mutex for this map.
136 sys::SmartMutex<true> ValueMapLock;
139 // NOTE: This function is not locked. It is the caller's responsibility
140 // to enforce proper synchronization.
141 typename MapTy::iterator map_end() { return Map.end(); }
143 /// InsertOrGetItem - Return an iterator for the specified element.
144 /// If the element exists in the map, the returned iterator points to the
145 /// entry and Exists=true. If not, the iterator points to the newly
146 /// inserted entry and returns Exists=false. Newly inserted entries have
147 /// I->second == 0, and should be filled in.
148 /// NOTE: This function is not locked. It is the caller's responsibility
149 // to enforce proper synchronization.
150 typename MapTy::iterator InsertOrGetItem(std::pair<MapKey, Constant *>
153 std::pair<typename MapTy::iterator, bool> IP = Map.insert(InsertVal);
159 typename MapTy::iterator FindExistingElement(ConstantClass *CP) {
161 typename InverseMapTy::iterator IMI = InverseMap.find(CP);
162 assert(IMI != InverseMap.end() && IMI->second != Map.end() &&
163 IMI->second->second == CP &&
164 "InverseMap corrupt!");
168 typename MapTy::iterator I =
169 Map.find(MapKey(static_cast<const TypeClass*>(CP->getRawType()),
171 if (I == Map.end() || I->second != CP) {
172 // FIXME: This should not use a linear scan. If this gets to be a
173 // performance problem, someone should look at this.
174 for (I = Map.begin(); I != Map.end() && I->second != CP; ++I)
180 ConstantClass* Create(const TypeClass *Ty, const ValType &V,
181 typename MapTy::iterator I) {
182 ConstantClass* Result =
183 ConstantCreator<ConstantClass,TypeClass,ValType>::create(Ty, V);
185 assert(Result->getType() == Ty && "Type specified is not correct!");
186 I = Map.insert(I, std::make_pair(MapKey(Ty, V), Result));
188 if (HasLargeKey) // Remember the reverse mapping if needed.
189 InverseMap.insert(std::make_pair(Result, I));
191 // If the type of the constant is abstract, make sure that an entry
192 // exists for it in the AbstractTypeMap.
193 if (Ty->isAbstract()) {
194 typename AbstractTypeMapTy::iterator TI =
195 AbstractTypeMap.find(Ty);
197 if (TI == AbstractTypeMap.end()) {
198 // Add ourselves to the ATU list of the type.
199 cast<DerivedType>(Ty)->addAbstractTypeUser(this);
201 AbstractTypeMap.insert(TI, std::make_pair(Ty, I));
209 /// getOrCreate - Return the specified constant from the map, creating it if
211 ConstantClass *getOrCreate(const TypeClass *Ty, const ValType &V) {
212 sys::SmartScopedLock<true> Lock(ValueMapLock);
213 MapKey Lookup(Ty, V);
214 ConstantClass* Result = 0;
216 typename MapTy::iterator I = Map.find(Lookup);
219 Result = static_cast<ConstantClass *>(I->second);
222 // If no preexisting value, create one now...
223 Result = Create(Ty, V, I);
229 void remove(ConstantClass *CP) {
230 sys::SmartScopedLock<true> Lock(ValueMapLock);
231 typename MapTy::iterator I = FindExistingElement(CP);
232 assert(I != Map.end() && "Constant not found in constant table!");
233 assert(I->second == CP && "Didn't find correct element?");
235 if (HasLargeKey) // Remember the reverse mapping if needed.
236 InverseMap.erase(CP);
238 // Now that we found the entry, make sure this isn't the entry that
239 // the AbstractTypeMap points to.
240 const TypeClass *Ty = static_cast<const TypeClass *>(I->first.first);
241 if (Ty->isAbstract()) {
242 assert(AbstractTypeMap.count(Ty) &&
243 "Abstract type not in AbstractTypeMap?");
244 typename MapTy::iterator &ATMEntryIt = AbstractTypeMap[Ty];
245 if (ATMEntryIt == I) {
246 // Yes, we are removing the representative entry for this type.
247 // See if there are any other entries of the same type.
248 typename MapTy::iterator TmpIt = ATMEntryIt;
250 // First check the entry before this one...
251 if (TmpIt != Map.begin()) {
253 if (TmpIt->first.first != Ty) // Not the same type, move back...
257 // If we didn't find the same type, try to move forward...
258 if (TmpIt == ATMEntryIt) {
260 if (TmpIt == Map.end() || TmpIt->first.first != Ty)
261 --TmpIt; // No entry afterwards with the same type
264 // If there is another entry in the map of the same abstract type,
265 // update the AbstractTypeMap entry now.
266 if (TmpIt != ATMEntryIt) {
269 // Otherwise, we are removing the last instance of this type
270 // from the table. Remove from the ATM, and from user list.
271 cast<DerivedType>(Ty)->removeAbstractTypeUser(this);
272 AbstractTypeMap.erase(Ty);
281 /// MoveConstantToNewSlot - If we are about to change C to be the element
282 /// specified by I, update our internal data structures to reflect this
284 /// NOTE: This function is not locked. It is the responsibility of the
285 /// caller to enforce proper synchronization if using this method.
286 void MoveConstantToNewSlot(ConstantClass *C, typename MapTy::iterator I) {
287 // First, remove the old location of the specified constant in the map.
288 typename MapTy::iterator OldI = FindExistingElement(C);
289 assert(OldI != Map.end() && "Constant not found in constant table!");
290 assert(OldI->second == C && "Didn't find correct element?");
292 // If this constant is the representative element for its abstract type,
293 // update the AbstractTypeMap so that the representative element is I.
294 if (C->getType()->isAbstract()) {
295 typename AbstractTypeMapTy::iterator ATI =
296 AbstractTypeMap.find(C->getType());
297 assert(ATI != AbstractTypeMap.end() &&
298 "Abstract type not in AbstractTypeMap?");
299 if (ATI->second == OldI)
303 // Remove the old entry from the map.
306 // Update the inverse map so that we know that this constant is now
307 // located at descriptor I.
309 assert(I->second == C && "Bad inversemap entry!");
314 void refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
315 sys::SmartScopedLock<true> Lock(ValueMapLock);
316 typename AbstractTypeMapTy::iterator I =
317 AbstractTypeMap.find(cast<Type>(OldTy));
319 assert(I != AbstractTypeMap.end() &&
320 "Abstract type not in AbstractTypeMap?");
322 // Convert a constant at a time until the last one is gone. The last one
323 // leaving will remove() itself, causing the AbstractTypeMapEntry to be
324 // eliminated eventually.
326 ConvertConstantType<ConstantClass,
328 static_cast<ConstantClass *>(I->second->second),
329 cast<TypeClass>(NewTy));
331 I = AbstractTypeMap.find(cast<Type>(OldTy));
332 } while (I != AbstractTypeMap.end());
335 // If the type became concrete without being refined to any other existing
336 // type, we just remove ourselves from the ATU list.
337 void typeBecameConcrete(const DerivedType *AbsTy) {
338 AbsTy->removeAbstractTypeUser(this);
342 DOUT << "Constant.cpp: ValueMap\n";
346 LLVMContextImpl::LLVMContextImpl(LLVMContext &C) :
347 Context(C), TheTrueVal(0), TheFalseVal(0) {
348 AggZeroConstants = new ValueMap<char, Type, ConstantAggregateZero>();
349 ArrayConstants = new ArrayConstantsTy();
350 StructConstants = new StructConstantsTy();
353 LLVMContextImpl::~LLVMContextImpl() {
354 delete AggZeroConstants;
355 delete ArrayConstants;
356 delete StructConstants;
359 // Get a ConstantInt from an APInt. Note that the value stored in the DenseMap
360 // as the key, is a DenseMapAPIntKeyInfo::KeyTy which has provided the
361 // operator== and operator!= to ensure that the DenseMap doesn't attempt to
362 // compare APInt's of different widths, which would violate an APInt class
363 // invariant which generates an assertion.
364 ConstantInt *LLVMContextImpl::getConstantInt(const APInt& V) {
365 // Get the corresponding integer type for the bit width of the value.
366 const IntegerType *ITy = Context.getIntegerType(V.getBitWidth());
367 // get an existing value or the insertion position
368 DenseMapAPIntKeyInfo::KeyTy Key(V, ITy);
370 ConstantsLock.reader_acquire();
371 ConstantInt *&Slot = IntConstants[Key];
372 ConstantsLock.reader_release();
375 sys::SmartScopedWriter<true> Writer(ConstantsLock);
376 ConstantInt *&NewSlot = IntConstants[Key];
378 NewSlot = new ConstantInt(ITy, V);
387 ConstantFP *LLVMContextImpl::getConstantFP(const APFloat &V) {
388 DenseMapAPFloatKeyInfo::KeyTy Key(V);
390 ConstantsLock.reader_acquire();
391 ConstantFP *&Slot = FPConstants[Key];
392 ConstantsLock.reader_release();
395 sys::SmartScopedWriter<true> Writer(ConstantsLock);
396 ConstantFP *&NewSlot = FPConstants[Key];
399 if (&V.getSemantics() == &APFloat::IEEEsingle)
401 else if (&V.getSemantics() == &APFloat::IEEEdouble)
403 else if (&V.getSemantics() == &APFloat::x87DoubleExtended)
404 Ty = Type::X86_FP80Ty;
405 else if (&V.getSemantics() == &APFloat::IEEEquad)
408 assert(&V.getSemantics() == &APFloat::PPCDoubleDouble &&
409 "Unknown FP format");
410 Ty = Type::PPC_FP128Ty;
412 NewSlot = new ConstantFP(Ty, V);
421 MDString *LLVMContextImpl::getMDString(const char *StrBegin,
422 unsigned StrLength) {
423 sys::SmartScopedWriter<true> Writer(ConstantsLock);
424 StringMapEntry<MDString *> &Entry =
425 MDStringCache.GetOrCreateValue(StringRef(StrBegin, StrLength));
426 MDString *&S = Entry.getValue();
427 if (!S) S = new MDString(Entry.getKeyData(),
428 Entry.getKeyLength());
433 MDNode *LLVMContextImpl::getMDNode(Value*const* Vals, unsigned NumVals) {
435 for (unsigned i = 0; i != NumVals; ++i)
436 ID.AddPointer(Vals[i]);
438 ConstantsLock.reader_acquire();
440 MDNode *N = MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint);
441 ConstantsLock.reader_release();
444 sys::SmartScopedWriter<true> Writer(ConstantsLock);
445 N = MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint);
447 // InsertPoint will have been set by the FindNodeOrInsertPos call.
448 N = new MDNode(Vals, NumVals);
449 MDNodeSet.InsertNode(N, InsertPoint);
456 ConstantAggregateZero*
457 LLVMContextImpl::getConstantAggregateZero(const Type *Ty) {
458 assert((isa<StructType>(Ty) || isa<ArrayType>(Ty) || isa<VectorType>(Ty)) &&
459 "Cannot create an aggregate zero of non-aggregate type!");
461 // Implicitly locked.
462 return AggZeroConstants->getOrCreate(Ty, 0);
465 Constant *LLVMContextImpl::getConstantArray(const ArrayType *Ty,
466 const std::vector<Constant*> &V) {
467 // If this is an all-zero array, return a ConstantAggregateZero object
470 if (!C->isNullValue()) {
471 // Implicitly locked.
472 return ArrayConstants->getOrCreate(Ty, V);
474 for (unsigned i = 1, e = V.size(); i != e; ++i)
476 // Implicitly locked.
477 return ArrayConstants->getOrCreate(Ty, V);
481 return Context.getConstantAggregateZero(Ty);
484 Constant *LLVMContextImpl::getConstantStruct(const StructType *Ty,
485 const std::vector<Constant*> &V) {
486 // Create a ConstantAggregateZero value if all elements are zeros...
487 for (unsigned i = 0, e = V.size(); i != e; ++i)
488 if (!V[i]->isNullValue())
489 // Implicitly locked.
490 return StructConstants->getOrCreate(Ty, V);
492 return Context.getConstantAggregateZero(Ty);
495 // *** erase methods ***
497 void LLVMContextImpl::erase(MDString *M) {
498 sys::SmartScopedWriter<true> Writer(ConstantsLock);
499 MDStringCache.erase(MDStringCache.find(StringRef(M->StrBegin,
503 void LLVMContextImpl::erase(MDNode *M) {
504 sys::SmartScopedWriter<true> Writer(ConstantsLock);
505 MDNodeSet.RemoveNode(M);
508 void LLVMContextImpl::erase(ConstantAggregateZero *Z) {
509 AggZeroConstants->remove(Z);
512 void LLVMContextImpl::erase(ConstantArray *C) {
513 ArrayConstants->remove(C);
516 void LLVMContextImpl::erase(ConstantStruct *S) {
517 StructConstants->remove(S);
520 // *** RAUW helpers ***
522 Constant *LLVMContextImpl::replaceUsesOfWithOnConstant(ConstantArray *CA,
523 Value *From, Value *To, Use *U) {
524 assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
525 Constant *ToC = cast<Constant>(To);
527 std::pair<ArrayConstantsTy::MapKey, Constant*> Lookup;
528 Lookup.first.first = CA->getType();
531 std::vector<Constant*> &Values = Lookup.first.second;
532 Values.reserve(CA->getNumOperands()); // Build replacement array.
534 // Fill values with the modified operands of the constant array. Also,
535 // compute whether this turns into an all-zeros array.
536 bool isAllZeros = false;
537 unsigned NumUpdated = 0;
538 if (!ToC->isNullValue()) {
539 for (Use *O = CA->OperandList, *E = CA->OperandList + CA->getNumOperands();
541 Constant *Val = cast<Constant>(O->get());
546 Values.push_back(Val);
550 for (Use *O = CA->OperandList, *E = CA->OperandList + CA->getNumOperands();
552 Constant *Val = cast<Constant>(O->get());
557 Values.push_back(Val);
558 if (isAllZeros) isAllZeros = Val->isNullValue();
562 Constant *Replacement = 0;
564 Replacement = Context.getConstantAggregateZero(CA->getType());
566 // Check to see if we have this array type already.
567 sys::SmartScopedWriter<true> Writer(ConstantsLock);
569 ArrayConstantsTy::MapTy::iterator I =
570 ArrayConstants->InsertOrGetItem(Lookup, Exists);
573 Replacement = I->second;
575 // Okay, the new shape doesn't exist in the system yet. Instead of
576 // creating a new constant array, inserting it, replaceallusesof'ing the
577 // old with the new, then deleting the old... just update the current one
579 ArrayConstants->MoveConstantToNewSlot(CA, I);
581 // Update to the new value. Optimize for the case when we have a single
582 // operand that we're changing, but handle bulk updates efficiently.
583 if (NumUpdated == 1) {
584 unsigned OperandToUpdate = U - CA->OperandList;
585 assert(CA->getOperand(OperandToUpdate) == From &&
586 "ReplaceAllUsesWith broken!");
587 CA->setOperand(OperandToUpdate, ToC);
589 for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i)
590 if (CA->getOperand(i) == From)
591 CA->setOperand(i, ToC);
600 Constant *LLVMContextImpl::replaceUsesOfWithOnConstant(ConstantStruct *CS,
601 Value *From, Value *To, Use *U) {
602 assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
603 Constant *ToC = cast<Constant>(To);
605 unsigned OperandToUpdate = U - CS->OperandList;
606 assert(CS->getOperand(OperandToUpdate) == From &&
607 "ReplaceAllUsesWith broken!");
609 std::pair<StructConstantsTy::MapKey, Constant*> Lookup;
610 Lookup.first.first = CS->getType();
612 std::vector<Constant*> &Values = Lookup.first.second;
613 Values.reserve(CS->getNumOperands()); // Build replacement struct.
616 // Fill values with the modified operands of the constant struct. Also,
617 // compute whether this turns into an all-zeros struct.
618 bool isAllZeros = false;
619 if (!ToC->isNullValue()) {
620 for (Use *O = CS->OperandList, *E = CS->OperandList + CS->getNumOperands();
622 Values.push_back(cast<Constant>(O->get()));
625 for (Use *O = CS->OperandList, *E = CS->OperandList + CS->getNumOperands();
627 Constant *Val = cast<Constant>(O->get());
628 Values.push_back(Val);
629 if (isAllZeros) isAllZeros = Val->isNullValue();
632 Values[OperandToUpdate] = ToC;
634 Constant *Replacement = 0;
636 Replacement = Context.getConstantAggregateZero(CS->getType());
638 // Check to see if we have this array type already.
639 sys::SmartScopedWriter<true> Writer(ConstantsLock);
641 StructConstantsTy::MapTy::iterator I =
642 StructConstants->InsertOrGetItem(Lookup, Exists);
645 Replacement = I->second;
647 // Okay, the new shape doesn't exist in the system yet. Instead of
648 // creating a new constant struct, inserting it, replaceallusesof'ing the
649 // old with the new, then deleting the old... just update the current one
651 StructConstants->MoveConstantToNewSlot(CS, I);
653 // Update to the new value.
654 CS->setOperand(OperandToUpdate, ToC);
659 assert(Replacement != CS && "I didn't contain From!");