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 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)));
  37   return Elements;
  38 }
  39
  40 namespace llvm {
  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) {
  44     return v.size();
  45   }
  46 };
  47
  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);
  52   }
  53 };
  54
  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!");
  59   }
  60 };
  61
  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);
  67   }
  68 };
  69
  70 template<>
  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.
  78   }
  79 };
  80
  81 template<>
  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.
  92   }
  93 };
  94
  95 template<>
  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??");
 104
 105     OldC->uncheckedReplaceAllUsesWith(New);
 106     OldC->destroyConstant();    // This constant is now dead, destroy it.
 107   }
 108 };
 109 }
 110
 111 template<class ValType, class TypeClass, class ConstantClass,
 112          bool HasLargeKey  /*true for arrays and structs*/ >
 113 class VISIBILITY_HIDDEN ValueMap : public AbstractTypeUser {
 114 public:
 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;
 119 private:
 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
 122   /// constant.
 123   MapTy Map;
 124
 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;
 130
 131   /// AbstractTypeMap - Map for abstract type constants.
 132   ///
 133   AbstractTypeMapTy AbstractTypeMap;
 134
 135   /// ValueMapLock - Mutex for this map.
 136   sys::SmartMutex<true> ValueMapLock;
 137
 138 public:
 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(); }
 142
 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 *>
 151                                  &InsertVal,
 152                                  bool &Exists) {
 153     std::pair<typename MapTy::iterator, bool> IP = Map.insert(InsertVal);
 154     Exists = !IP.second;
 155     return IP.first;
 156   }
 157
 158 private:
 159   typename MapTy::iterator FindExistingElement(ConstantClass *CP) {
 160     if (HasLargeKey) {
 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!");
 165       return IMI->second;
 166     }
 167
 168     typename MapTy::iterator I =
 169       Map.find(MapKey(static_cast<const TypeClass*>(CP->getRawType()),
 170                       getValType(CP)));
 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)
 175         /* empty */;
 176     }
 177     return I;
 178   }
 179
 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);
 184
 185     assert(Result->getType() == Ty && "Type specified is not correct!");
 186     I = Map.insert(I, std::make_pair(MapKey(Ty, V), Result));
 187
 188     if (HasLargeKey)  // Remember the reverse mapping if needed.
 189       InverseMap.insert(std::make_pair(Result, I));
 190
 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);
 196
 197       if (TI == AbstractTypeMap.end()) {
 198         // Add ourselves to the ATU list of the type.
 199         cast<DerivedType>(Ty)->addAbstractTypeUser(this);
 200
 201         AbstractTypeMap.insert(TI, std::make_pair(Ty, I));
 202       }
 203     }
 204
 205     return Result;
 206   }
 207 public:
 208
 209   /// getOrCreate - Return the specified constant from the map, creating it if
 210   /// necessary.
 211   ConstantClass *getOrCreate(const TypeClass *Ty, const ValType &V) {
 212     sys::SmartScopedLock<true> Lock(ValueMapLock);
 213     MapKey Lookup(Ty, V);
 214     ConstantClass* Result = 0;
 215
 216     typename MapTy::iterator I = Map.find(Lookup);
 217     // Is it in the map?
 218     if (I != Map.end())
 219       Result = static_cast<ConstantClass *>(I->second);
 220
 221     if (!Result) {
 222       // If no preexisting value, create one now...
 223       Result = Create(Ty, V, I);
 224     }
 225
 226     return Result;
 227   }
 228
 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?");
 234
 235     if (HasLargeKey)  // Remember the reverse mapping if needed.
 236       InverseMap.erase(CP);
 237
 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;
 249
 250         // First check the entry before this one...
 251         if (TmpIt != Map.begin()) {
 252           --TmpIt;
 253           if (TmpIt->first.first != Ty) // Not the same type, move back...
 254             ++TmpIt;
 255         }
 256
 257         // If we didn't find the same type, try to move forward...
 258         if (TmpIt == ATMEntryIt) {
 259           ++TmpIt;
 260           if (TmpIt == Map.end() || TmpIt->first.first != Ty)
 261             --TmpIt;   // No entry afterwards with the same type
 262         }
 263
 264         // If there is another entry in the map of the same abstract type,
 265         // update the AbstractTypeMap entry now.
 266         if (TmpIt != ATMEntryIt) {
 267           ATMEntryIt = TmpIt;
 268         } else {
 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);
 273         }
 274       }
 275     }
 276
 277     Map.erase(I);
 278   }
 279
 280
 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
 283   /// fact.
 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?");
 291
 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)
 300         ATI->second = I;
 301     }
 302
 303     // Remove the old entry from the map.
 304     Map.erase(OldI);
 305
 306     // Update the inverse map so that we know that this constant is now
 307     // located at descriptor I.
 308     if (HasLargeKey) {
 309       assert(I->second == C && "Bad inversemap entry!");
 310       InverseMap[C] = I;
 311     }
 312   }
 313
 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));
 318
 319     assert(I != AbstractTypeMap.end() &&
 320            "Abstract type not in AbstractTypeMap?");
 321
 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.
 325     do {
 326       ConvertConstantType<ConstantClass,
 327                           TypeClass>::convert(
 328                               static_cast<ConstantClass *>(I->second->second),
 329                                               cast<TypeClass>(NewTy));
 330
 331       I = AbstractTypeMap.find(cast<Type>(OldTy));
 332     } while (I != AbstractTypeMap.end());
 333   }
 334
 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);
 339   }
 340
 341   void dump() const {
 342     DOUT << "Constant.cpp: ValueMap\n";
 343   }
 344 };
 345
 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();
 351 }
 352
 353 LLVMContextImpl::~LLVMContextImpl() {
 354   delete AggZeroConstants;
 355   delete ArrayConstants;
 356   delete StructConstants;
 357 }
 358
 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);
 369
 370   ConstantsLock.reader_acquire();
 371   ConstantInt *&Slot = IntConstants[Key];
 372   ConstantsLock.reader_release();
 373
 374   if (!Slot) {
 375     sys::SmartScopedWriter<true> Writer(ConstantsLock);
 376     ConstantInt *&NewSlot = IntConstants[Key];
 377     if (!Slot) {
 378       NewSlot = new ConstantInt(ITy, V);
 379     }
 380
 381     return NewSlot;
 382   } else {
 383     return Slot;
 384   }
 385 }
 386
 387 ConstantFP *LLVMContextImpl::getConstantFP(const APFloat &V) {
 388   DenseMapAPFloatKeyInfo::KeyTy Key(V);
 389
 390   ConstantsLock.reader_acquire();
 391   ConstantFP *&Slot = FPConstants[Key];
 392   ConstantsLock.reader_release();
 393
 394   if (!Slot) {
 395     sys::SmartScopedWriter<true> Writer(ConstantsLock);
 396     ConstantFP *&NewSlot = FPConstants[Key];
 397     if (!NewSlot) {
 398       const Type *Ty;
 399       if (&V.getSemantics() == &APFloat::IEEEsingle)
 400         Ty = Type::FloatTy;
 401       else if (&V.getSemantics() == &APFloat::IEEEdouble)
 402         Ty = Type::DoubleTy;
 403       else if (&V.getSemantics() == &APFloat::x87DoubleExtended)
 404         Ty = Type::X86_FP80Ty;
 405       else if (&V.getSemantics() == &APFloat::IEEEquad)
 406         Ty = Type::FP128Ty;
 407       else {
 408         assert(&V.getSemantics() == &APFloat::PPCDoubleDouble &&
 409                "Unknown FP format");
 410         Ty = Type::PPC_FP128Ty;
 411       }
 412       NewSlot = new ConstantFP(Ty, V);
 413     }
 414
 415     return NewSlot;
 416   }
 417
 418   return Slot;
 419 }
 420
 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());
 429
 430   return S;
 431 }
 432
 433 MDNode *LLVMContextImpl::getMDNode(Value*const* Vals, unsigned NumVals) {
 434   FoldingSetNodeID ID;
 435   for (unsigned i = 0; i != NumVals; ++i)
 436     ID.AddPointer(Vals[i]);
 437
 438   ConstantsLock.reader_acquire();
 439   void *InsertPoint;
 440   MDNode *N = MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint);
 441   ConstantsLock.reader_release();
 442
 443   if (!N) {
 444     sys::SmartScopedWriter<true> Writer(ConstantsLock);
 445     N = MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint);
 446     if (!N) {
 447       // InsertPoint will have been set by the FindNodeOrInsertPos call.
 448       N = new MDNode(Vals, NumVals);
 449       MDNodeSet.InsertNode(N, InsertPoint);
 450     }
 451   }
 452
 453   return N;
 454 }
 455
 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!");
 460
 461   // Implicitly locked.
 462   return AggZeroConstants->getOrCreate(Ty, 0);
 463 }
 464
 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
 468   if (!V.empty()) {
 469     Constant *C = V[0];
 470     if (!C->isNullValue()) {
 471       // Implicitly locked.
 472       return ArrayConstants->getOrCreate(Ty, V);
 473     }
 474     for (unsigned i = 1, e = V.size(); i != e; ++i)
 475       if (V[i] != C) {
 476         // Implicitly locked.
 477         return ArrayConstants->getOrCreate(Ty, V);
 478       }
 479   }
 480
 481   return Context.getConstantAggregateZero(Ty);
 482 }
 483
 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);
 491
 492   return Context.getConstantAggregateZero(Ty);
 493 }
 494
 495 // *** erase methods ***
 496
 497 void LLVMContextImpl::erase(MDString *M) {
 498   sys::SmartScopedWriter<true> Writer(ConstantsLock);
 499   MDStringCache.erase(MDStringCache.find(StringRef(M->StrBegin,
 500                                                    M->length())));
 501 }
 502
 503 void LLVMContextImpl::erase(MDNode *M) {
 504   sys::SmartScopedWriter<true> Writer(ConstantsLock);
 505   MDNodeSet.RemoveNode(M);
 506 }
 507
 508 void LLVMContextImpl::erase(ConstantAggregateZero *Z) {
 509   AggZeroConstants->remove(Z);
 510 }
 511
 512 void LLVMContextImpl::erase(ConstantArray *C) {
 513   ArrayConstants->remove(C);
 514 }
 515
 516 void LLVMContextImpl::erase(ConstantStruct *S) {
 517   StructConstants->remove(S);
 518 }
 519
 520 // *** RAUW helpers ***
 521
 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);
 526
 527   std::pair<ArrayConstantsTy::MapKey, Constant*> Lookup;
 528   Lookup.first.first = CA->getType();
 529   Lookup.second = CA;
 530
 531   std::vector<Constant*> &Values = Lookup.first.second;
 532   Values.reserve(CA->getNumOperands());  // Build replacement array.
 533
 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();
 540          O != E; ++O) {
 541       Constant *Val = cast<Constant>(O->get());
 542       if (Val == From) {
 543         Val = ToC;
 544         ++NumUpdated;
 545       }
 546       Values.push_back(Val);
 547     }
 548   } else {
 549     isAllZeros = true;
 550     for (Use *O = CA->OperandList, *E = CA->OperandList + CA->getNumOperands();
 551          O != E; ++O) {
 552       Constant *Val = cast<Constant>(O->get());
 553       if (Val == From) {
 554         Val = ToC;
 555         ++NumUpdated;
 556       }
 557       Values.push_back(Val);
 558       if (isAllZeros) isAllZeros = Val->isNullValue();
 559     }
 560   }
 561
 562   Constant *Replacement = 0;
 563   if (isAllZeros) {
 564     Replacement = Context.getConstantAggregateZero(CA->getType());
 565   } else {
 566     // Check to see if we have this array type already.
 567     sys::SmartScopedWriter<true> Writer(ConstantsLock);
 568     bool Exists;
 569     ArrayConstantsTy::MapTy::iterator I =
 570       ArrayConstants->InsertOrGetItem(Lookup, Exists);
 571
 572     if (Exists) {
 573       Replacement = I->second;
 574     } else {
 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
 578       // in place!
 579       ArrayConstants->MoveConstantToNewSlot(CA, I);
 580
 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);
 588       } else {
 589         for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i)
 590           if (CA->getOperand(i) == From)
 591             CA->setOperand(i, ToC);
 592       }
 593       return 0;
 594     }
 595   }
 596
 597   return Replacement;
 598 }
 599
 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);
 604
 605   unsigned OperandToUpdate = U - CS->OperandList;
 606   assert(CS->getOperand(OperandToUpdate) == From &&
 607          "ReplaceAllUsesWith broken!");
 608
 609   std::pair<StructConstantsTy::MapKey, Constant*> Lookup;
 610   Lookup.first.first = CS->getType();
 611   Lookup.second = CS;
 612   std::vector<Constant*> &Values = Lookup.first.second;
 613   Values.reserve(CS->getNumOperands());  // Build replacement struct.
 614
 615
 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();
 621          O != E; ++O)
 622       Values.push_back(cast<Constant>(O->get()));
 623   } else {
 624     isAllZeros = true;
 625     for (Use *O = CS->OperandList, *E = CS->OperandList + CS->getNumOperands();
 626          O != E; ++O) {
 627       Constant *Val = cast<Constant>(O->get());
 628       Values.push_back(Val);
 629       if (isAllZeros) isAllZeros = Val->isNullValue();
 630     }
 631   }
 632   Values[OperandToUpdate] = ToC;
 633
 634   Constant *Replacement = 0;
 635   if (isAllZeros) {
 636     Replacement = Context.getConstantAggregateZero(CS->getType());
 637   } else {
 638     // Check to see if we have this array type already.
 639     sys::SmartScopedWriter<true> Writer(ConstantsLock);
 640     bool Exists;
 641     StructConstantsTy::MapTy::iterator I =
 642       StructConstants->InsertOrGetItem(Lookup, Exists);
 643
 644     if (Exists) {
 645       Replacement = I->second;
 646     } else {
 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
 650       // in place!
 651       StructConstants->MoveConstantToNewSlot(CS, I);
 652
 653       // Update to the new value.
 654       CS->setOperand(OperandToUpdate, ToC);
 655       return 0;
 656     }
 657   }
 658
 659   assert(Replacement != CS && "I didn't contain From!");
 660
 661   return Replacement;
 662 }