X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FConstants.cpp;h=400b2741cdf71d1c1c618870264e16da187a0a79;hb=6de8ffbbc91bd750fa7212d3cbc4211341ef817e;hp=4d332fe255aee48104e516b2d247fd41075657e5;hpb=1a8def6ad6b7b114abd31524d73ad8062a82fbc8;p=oota-llvm.git

diff --git a/lib/VMCore/Constants.cpp b/lib/VMCore/Constants.cpp
index 4d332fe255a..400b2741cdf 100644
--- a/lib/VMCore/Constants.cpp
+++ b/lib/VMCore/Constants.cpp
@@ -117,8 +117,7 @@ Constant *Constant::getNullValue(Type *Ty) {
     return ConstantAggregateZero::get(Ty);
   default:
     // Function, Label, or Opaque type?
-    assert(0 && "Cannot create a null constant of that type!");
-    return 0;
+    llvm_unreachable("Cannot create a null constant of that type!");
   }
 }
 
@@ -176,7 +175,7 @@ Constant *Constant::getAggregateElement(unsigned Elt) const {
     return UV->getElementValue(Elt);
   
   if (const ConstantDataSequential *CDS =dyn_cast<ConstantDataSequential>(this))
-    return CDS->getElementAsConstant(Elt);
+    return Elt < CDS->getNumElements() ? CDS->getElementAsConstant(Elt) : 0;
   return 0;
 }
 
@@ -441,12 +440,12 @@ Constant *ConstantInt::get(Type *Ty, uint64_t V, bool isSigned) {
   return C;
 }
 
-ConstantInt* ConstantInt::get(IntegerType* Ty, uint64_t V, 
+ConstantInt *ConstantInt::get(IntegerType *Ty, uint64_t V, 
                               bool isSigned) {
   return get(Ty->getContext(), APInt(Ty->getBitWidth(), V, isSigned));
 }
 
-ConstantInt* ConstantInt::getSigned(IntegerType* Ty, int64_t V) {
+ConstantInt *ConstantInt::getSigned(IntegerType *Ty, int64_t V) {
   return get(Ty, V, true);
 }
 
@@ -454,7 +453,7 @@ Constant *ConstantInt::getSigned(Type *Ty, int64_t V) {
   return get(Ty, V, true);
 }
 
-Constant *ConstantInt::get(Type* Ty, const APInt& V) {
+Constant *ConstantInt::get(Type *Ty, const APInt& V) {
   ConstantInt *C = get(Ty->getContext(), V);
   assert(C->getType() == Ty->getScalarType() &&
          "ConstantInt type doesn't match the type implied by its value!");
@@ -466,7 +465,7 @@ Constant *ConstantInt::get(Type* Ty, const APInt& V) {
   return C;
 }
 
-ConstantInt* ConstantInt::get(IntegerType* Ty, StringRef Str,
+ConstantInt *ConstantInt::get(IntegerType* Ty, StringRef Str,
                               uint8_t radix) {
   return get(Ty->getContext(), APInt(Ty->getBitWidth(), Str, radix));
 }
@@ -496,7 +495,7 @@ void ConstantFP::anchor() { }
 /// get() - This returns a constant fp for the specified value in the
 /// specified type.  This should only be used for simple constant values like
 /// 2.0/1.0 etc, that are known-valid both as double and as the target format.
-Constant *ConstantFP::get(Type* Ty, double V) {
+Constant *ConstantFP::get(Type *Ty, double V) {
   LLVMContext &Context = Ty->getContext();
   
   APFloat FV(V);
@@ -513,7 +512,7 @@ Constant *ConstantFP::get(Type* Ty, double V) {
 }
 
 
-Constant *ConstantFP::get(Type* Ty, StringRef Str) {
+Constant *ConstantFP::get(Type *Ty, StringRef Str) {
   LLVMContext &Context = Ty->getContext();
 
   APFloat FV(*TypeToFloatSemantics(Ty->getScalarType()), Str);
@@ -666,6 +665,13 @@ UndefValue *UndefValue::getElementValue(unsigned Idx) const {
 //                            ConstantXXX Classes
 //===----------------------------------------------------------------------===//
 
+template <typename ItTy, typename EltTy>
+static bool rangeOnlyContains(ItTy Start, ItTy End, EltTy Elt) {
+  for (; Start != End; ++Start)
+    if (*Start != Elt)
+      return false;
+  return true;
+}
 
 ConstantArray::ConstantArray(ArrayType *T, ArrayRef<Constant *> V)
   : Constant(T, ConstantArrayVal,
@@ -680,54 +686,97 @@ ConstantArray::ConstantArray(ArrayType *T, ArrayRef<Constant *> V)
 }
 
 Constant *ConstantArray::get(ArrayType *Ty, ArrayRef<Constant*> V) {
+  // Empty arrays are canonicalized to ConstantAggregateZero.
+  if (V.empty())
+    return ConstantAggregateZero::get(Ty);
+
   for (unsigned i = 0, e = V.size(); i != e; ++i) {
     assert(V[i]->getType() == Ty->getElementType() &&
            "Wrong type in array element initializer");
   }
   LLVMContextImpl *pImpl = Ty->getContext().pImpl;
-  // If this is an all-zero array, return a ConstantAggregateZero object
-  bool isAllZero = true;
-  bool isUndef = false;
-  if (!V.empty()) {
-    Constant *C = V[0];
-    isAllZero = C->isNullValue();
-    isUndef = isa<UndefValue>(C);
-
-    if (isAllZero || isUndef)
-      for (unsigned i = 1, e = V.size(); i != e; ++i)
-        if (V[i] != C) {
-          isAllZero = false;
-          isUndef = false;
-          break;
-        }
-  }
-
-  if (isAllZero)
-    return ConstantAggregateZero::get(Ty);
-  if (isUndef)
+  
+  // If this is an all-zero array, return a ConstantAggregateZero object.  If
+  // all undef, return an UndefValue, if "all simple", then return a
+  // ConstantDataArray.
+  Constant *C = V[0];
+  if (isa<UndefValue>(C) && rangeOnlyContains(V.begin(), V.end(), C))
     return UndefValue::get(Ty);
-  return pImpl->ArrayConstants.getOrCreate(Ty, V);
-}
 
-/// ConstantArray::get(const string&) - Return an array that is initialized to
-/// contain the specified string.  If length is zero then a null terminator is 
-/// added to the specified string so that it may be used in a natural way. 
-/// Otherwise, the length parameter specifies how much of the string to use 
-/// and it won't be null terminated.
-///
-Constant *ConstantArray::get(LLVMContext &Context, StringRef Str,
-                             bool AddNull) {
-  std::vector<Constant*> ElementVals;
-  ElementVals.reserve(Str.size() + size_t(AddNull));
-  for (unsigned i = 0; i < Str.size(); ++i)
-    ElementVals.push_back(ConstantInt::get(Type::getInt8Ty(Context), Str[i]));
+  if (C->isNullValue() && rangeOnlyContains(V.begin(), V.end(), C))
+    return ConstantAggregateZero::get(Ty);
 
-  // Add a null terminator to the string...
-  if (AddNull)
-    ElementVals.push_back(ConstantInt::get(Type::getInt8Ty(Context), 0));
+  // Check to see if all of the elements are ConstantFP or ConstantInt and if
+  // the element type is compatible with ConstantDataVector.  If so, use it.
+  if (ConstantDataSequential::isElementTypeCompatible(C->getType())) {
+    // We speculatively build the elements here even if it turns out that there
+    // is a constantexpr or something else weird in the array, since it is so
+    // uncommon for that to happen.
+    if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) {
+      if (CI->getType()->isIntegerTy(8)) {
+        SmallVector<uint8_t, 16> Elts;
+        for (unsigned i = 0, e = V.size(); i != e; ++i)
+          if (ConstantInt *CI = dyn_cast<ConstantInt>(V[i]))
+            Elts.push_back(CI->getZExtValue());
+          else
+            break;
+        if (Elts.size() == V.size())
+          return ConstantDataArray::get(C->getContext(), Elts);
+      } else if (CI->getType()->isIntegerTy(16)) {
+        SmallVector<uint16_t, 16> Elts;
+        for (unsigned i = 0, e = V.size(); i != e; ++i)
+          if (ConstantInt *CI = dyn_cast<ConstantInt>(V[i]))
+            Elts.push_back(CI->getZExtValue());
+          else
+            break;
+        if (Elts.size() == V.size())
+          return ConstantDataArray::get(C->getContext(), Elts);
+      } else if (CI->getType()->isIntegerTy(32)) {
+        SmallVector<uint32_t, 16> Elts;
+        for (unsigned i = 0, e = V.size(); i != e; ++i)
+          if (ConstantInt *CI = dyn_cast<ConstantInt>(V[i]))
+            Elts.push_back(CI->getZExtValue());
+          else
+            break;
+        if (Elts.size() == V.size())
+          return ConstantDataArray::get(C->getContext(), Elts);
+      } else if (CI->getType()->isIntegerTy(64)) {
+        SmallVector<uint64_t, 16> Elts;
+        for (unsigned i = 0, e = V.size(); i != e; ++i)
+          if (ConstantInt *CI = dyn_cast<ConstantInt>(V[i]))
+            Elts.push_back(CI->getZExtValue());
+          else
+            break;
+        if (Elts.size() == V.size())
+          return ConstantDataArray::get(C->getContext(), Elts);
+      }
+    }
+    
+    if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
+      if (CFP->getType()->isFloatTy()) {
+        SmallVector<float, 16> Elts;
+        for (unsigned i = 0, e = V.size(); i != e; ++i)
+          if (ConstantFP *CFP = dyn_cast<ConstantFP>(V[i]))
+            Elts.push_back(CFP->getValueAPF().convertToFloat());
+          else
+            break;
+        if (Elts.size() == V.size())
+          return ConstantDataArray::get(C->getContext(), Elts);
+      } else if (CFP->getType()->isDoubleTy()) {
+        SmallVector<double, 16> Elts;
+        for (unsigned i = 0, e = V.size(); i != e; ++i)
+          if (ConstantFP *CFP = dyn_cast<ConstantFP>(V[i]))
+            Elts.push_back(CFP->getValueAPF().convertToDouble());
+          else
+            break;
+        if (Elts.size() == V.size())
+          return ConstantDataArray::get(C->getContext(), Elts);
+      }
+    }
+  }
 
-  ArrayType *ATy = ArrayType::get(Type::getInt8Ty(Context), ElementVals.size());
-  return get(ATy, ElementVals);
+  // Otherwise, we really do want to create a ConstantArray.
+  return pImpl->ArrayConstants.getOrCreate(Ty, V);
 }
 
 /// getTypeForElements - Return an anonymous struct type to use for a constant
@@ -735,9 +784,10 @@ Constant *ConstantArray::get(LLVMContext &Context, StringRef Str,
 StructType *ConstantStruct::getTypeForElements(LLVMContext &Context,
                                                ArrayRef<Constant*> V,
                                                bool Packed) {
-  SmallVector<Type*, 16> EltTypes;
-  for (unsigned i = 0, e = V.size(); i != e; ++i)
-    EltTypes.push_back(V[i]->getType());
+  unsigned VecSize = V.size();
+  SmallVector<Type*, 16> EltTypes(VecSize);
+  for (unsigned i = 0; i != VecSize; ++i)
+    EltTypes[i] = V[i]->getType();
   
   return StructType::get(Context, EltTypes, Packed);
 }
@@ -836,11 +886,88 @@ Constant *ConstantVector::get(ArrayRef<Constant*> V) {
     return ConstantAggregateZero::get(T);
   if (isUndef)
     return UndefValue::get(T);
+   
+  // Check to see if all of the elements are ConstantFP or ConstantInt and if
+  // the element type is compatible with ConstantDataVector.  If so, use it.
+  if (ConstantDataSequential::isElementTypeCompatible(C->getType())) {
+    // We speculatively build the elements here even if it turns out that there
+    // is a constantexpr or something else weird in the array, since it is so
+    // uncommon for that to happen.
+    if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) {
+      if (CI->getType()->isIntegerTy(8)) {
+        SmallVector<uint8_t, 16> Elts;
+        for (unsigned i = 0, e = V.size(); i != e; ++i)
+          if (ConstantInt *CI = dyn_cast<ConstantInt>(V[i]))
+            Elts.push_back(CI->getZExtValue());
+          else
+            break;
+        if (Elts.size() == V.size())
+          return ConstantDataVector::get(C->getContext(), Elts);
+      } else if (CI->getType()->isIntegerTy(16)) {
+        SmallVector<uint16_t, 16> Elts;
+        for (unsigned i = 0, e = V.size(); i != e; ++i)
+          if (ConstantInt *CI = dyn_cast<ConstantInt>(V[i]))
+            Elts.push_back(CI->getZExtValue());
+          else
+            break;
+        if (Elts.size() == V.size())
+          return ConstantDataVector::get(C->getContext(), Elts);
+      } else if (CI->getType()->isIntegerTy(32)) {
+        SmallVector<uint32_t, 16> Elts;
+        for (unsigned i = 0, e = V.size(); i != e; ++i)
+          if (ConstantInt *CI = dyn_cast<ConstantInt>(V[i]))
+            Elts.push_back(CI->getZExtValue());
+          else
+            break;
+        if (Elts.size() == V.size())
+          return ConstantDataVector::get(C->getContext(), Elts);
+      } else if (CI->getType()->isIntegerTy(64)) {
+        SmallVector<uint64_t, 16> Elts;
+        for (unsigned i = 0, e = V.size(); i != e; ++i)
+          if (ConstantInt *CI = dyn_cast<ConstantInt>(V[i]))
+            Elts.push_back(CI->getZExtValue());
+          else
+            break;
+        if (Elts.size() == V.size())
+          return ConstantDataVector::get(C->getContext(), Elts);
+      }
+    }
     
+    if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
+      if (CFP->getType()->isFloatTy()) {
+        SmallVector<float, 16> Elts;
+        for (unsigned i = 0, e = V.size(); i != e; ++i)
+          if (ConstantFP *CFP = dyn_cast<ConstantFP>(V[i]))
+            Elts.push_back(CFP->getValueAPF().convertToFloat());
+          else
+            break;
+        if (Elts.size() == V.size())
+          return ConstantDataVector::get(C->getContext(), Elts);
+      } else if (CFP->getType()->isDoubleTy()) {
+        SmallVector<double, 16> Elts;
+        for (unsigned i = 0, e = V.size(); i != e; ++i)
+          if (ConstantFP *CFP = dyn_cast<ConstantFP>(V[i]))
+            Elts.push_back(CFP->getValueAPF().convertToDouble());
+          else
+            break;
+        if (Elts.size() == V.size())
+          return ConstantDataVector::get(C->getContext(), Elts);
+      }
+    }
+  }
+  
+  // Otherwise, the element type isn't compatible with ConstantDataVector, or
+  // the operand list constants a ConstantExpr or something else strange.
   return pImpl->VectorConstants.getOrCreate(T, V);
 }
 
 Constant *ConstantVector::getSplat(unsigned NumElts, Constant *V) {
+  // If this splat is compatible with ConstantDataVector, use it instead of
+  // ConstantVector.
+  if ((isa<ConstantFP>(V) || isa<ConstantInt>(V)) &&
+      ConstantDataSequential::isElementTypeCompatible(V->getType()))
+    return ConstantDataVector::getSplat(NumElts, V);
+  
   SmallVector<Constant*, 32> Elts(NumElts, V);
   return get(Elts);
 }
@@ -1068,69 +1195,6 @@ void ConstantArray::destroyConstant() {
   destroyConstantImpl();
 }
 
-/// isString - This method returns true if the array is an array of i8, and 
-/// if the elements of the array are all ConstantInt's.
-bool ConstantArray::isString() const {
-  // Check the element type for i8...
-  if (!getType()->getElementType()->isIntegerTy(8))
-    return false;
-  // Check the elements to make sure they are all integers, not constant
-  // expressions.
-  for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
-    if (!isa<ConstantInt>(getOperand(i)))
-      return false;
-  return true;
-}
-
-/// isCString - This method returns true if the array is a string (see
-/// isString) and it ends in a null byte \\0 and does not contains any other
-/// null bytes except its terminator.
-bool ConstantArray::isCString() const {
-  // Check the element type for i8...
-  if (!getType()->getElementType()->isIntegerTy(8))
-    return false;
-
-  // Last element must be a null.
-  if (!getOperand(getNumOperands()-1)->isNullValue())
-    return false;
-  // Other elements must be non-null integers.
-  for (unsigned i = 0, e = getNumOperands()-1; i != e; ++i) {
-    if (!isa<ConstantInt>(getOperand(i)))
-      return false;
-    if (getOperand(i)->isNullValue())
-      return false;
-  }
-  return true;
-}
-
-
-/// convertToString - Helper function for getAsString() and getAsCString().
-static std::string convertToString(const User *U, unsigned len) {
-  std::string Result;
-  Result.reserve(len);
-  for (unsigned i = 0; i != len; ++i)
-    Result.push_back((char)cast<ConstantInt>(U->getOperand(i))->getZExtValue());
-  return Result;
-}
-
-/// getAsString - If this array is isString(), then this method converts the
-/// array to an std::string and returns it.  Otherwise, it asserts out.
-///
-std::string ConstantArray::getAsString() const {
-  assert(isString() && "Not a string!");
-  return convertToString(this, getNumOperands());
-}
-
-
-/// getAsCString - If this array is isCString(), then this method converts the
-/// array (without the trailing null byte) to an std::string and returns it.
-/// Otherwise, it asserts out.
-///
-std::string ConstantArray::getAsCString() const {
-  assert(isCString() && "Not a string!");
-  return convertToString(this, getNumOperands() - 1);
-}
-
 
 //---- ConstantStruct::get() implementation...
 //
@@ -1943,6 +2007,47 @@ Constant *ConstantExpr::getAShr(Constant *C1, Constant *C2, bool isExact) {
              isExact ? PossiblyExactOperator::IsExact : 0);
 }
 
+/// getBinOpIdentity - Return the identity for the given binary operation,
+/// i.e. a constant C such that X op C = X and C op X = X for every X.  It
+/// returns null if the operator doesn't have an identity.
+Constant *ConstantExpr::getBinOpIdentity(unsigned Opcode, Type *Ty) {
+  switch (Opcode) {
+  default:
+    // Doesn't have an identity.
+    return 0;
+
+  case Instruction::Add:
+  case Instruction::Or:
+  case Instruction::Xor:
+    return Constant::getNullValue(Ty);
+
+  case Instruction::Mul:
+    return ConstantInt::get(Ty, 1);
+
+  case Instruction::And:
+    return Constant::getAllOnesValue(Ty);
+  }
+}
+
+/// getBinOpAbsorber - Return the absorbing element for the given binary
+/// operation, i.e. a constant C such that X op C = C and C op X = C for
+/// every X.  For example, this returns zero for integer multiplication.
+/// It returns null if the operator doesn't have an absorbing element.
+Constant *ConstantExpr::getBinOpAbsorber(unsigned Opcode, Type *Ty) {
+  switch (Opcode) {
+  default:
+    // Doesn't have an absorber.
+    return 0;
+
+  case Instruction::Or:
+    return Constant::getAllOnesValue(Ty);
+
+  case Instruction::And:
+  case Instruction::Mul:
+    return Constant::getNullValue(Ty);
+  }
+}
+
 // destroyConstant - Remove the constant from the constant table...
 //
 void ConstantExpr::destroyConstant() {
@@ -1957,7 +2062,7 @@ const char *ConstantExpr::getOpcodeName() const {
 
 
 GetElementPtrConstantExpr::
-GetElementPtrConstantExpr(Constant *C, const std::vector<Constant*> &IdxList,
+GetElementPtrConstantExpr(Constant *C, ArrayRef<Constant*> IdxList,
                           Type *DestTy)
   : ConstantExpr(DestTy, Instruction::GetElementPtr,
                  OperandTraits<GetElementPtrConstantExpr>::op_end(this)
@@ -2031,7 +2136,7 @@ static bool isAllZeros(StringRef Arr) {
 
 /// getImpl - This is the underlying implementation of all of the
 /// ConstantDataSequential::get methods.  They all thunk down to here, providing
-/// the correct element type.  We take the bytes in as an StringRef because
+/// the correct element type.  We take the bytes in as a StringRef because
 /// we *want* an underlying "char*" to avoid TBAA type punning violations.
 Constant *ConstantDataSequential::getImpl(StringRef Elements, Type *Ty) {
   assert(isElementTypeCompatible(Ty->getSequentialElementType()));
@@ -2196,14 +2301,18 @@ Constant *ConstantDataVector::getSplat(unsigned NumElts, Constant *V) {
     return get(V->getContext(), Elts);
   }
 
-  ConstantFP *CFP = cast<ConstantFP>(V);
-  if (CFP->getType()->isFloatTy()) {
-    SmallVector<float, 16> Elts(NumElts, CFP->getValueAPF().convertToFloat());
-    return get(V->getContext(), Elts);
+  if (ConstantFP *CFP = dyn_cast<ConstantFP>(V)) {
+    if (CFP->getType()->isFloatTy()) {
+      SmallVector<float, 16> Elts(NumElts, CFP->getValueAPF().convertToFloat());
+      return get(V->getContext(), Elts);
+    }
+    if (CFP->getType()->isDoubleTy()) {
+      SmallVector<double, 16> Elts(NumElts,
+                                   CFP->getValueAPF().convertToDouble());
+      return get(V->getContext(), Elts);
+    }
   }
-  assert(CFP->getType()->isDoubleTy() && "Unsupported ConstantData type");
-  SmallVector<double, 16> Elts(NumElts, CFP->getValueAPF().convertToDouble());
-  return get(V->getContext(), Elts);
+  return ConstantVector::getSplat(NumElts, V);
 }
 
 
@@ -2217,7 +2326,7 @@ uint64_t ConstantDataSequential::getElementAsInteger(unsigned Elt) const {
   // The data is stored in host byte order, make sure to cast back to the right
   // type to load with the right endianness.
   switch (getElementType()->getIntegerBitWidth()) {
-  default: assert(0 && "Invalid bitwidth for CDS");
+  default: llvm_unreachable("Invalid bitwidth for CDS");
   case 8:  return *(uint8_t*)EltPtr;
   case 16: return *(uint16_t*)EltPtr;
   case 32: return *(uint32_t*)EltPtr;
@@ -2232,7 +2341,7 @@ APFloat ConstantDataSequential::getElementAsAPFloat(unsigned Elt) const {
 
   switch (getElementType()->getTypeID()) {
   default:
-    assert(0 && "Accessor can only be used when element is float/double!");
+    llvm_unreachable("Accessor can only be used when element is float/double!");
   case Type::FloatTyID: return APFloat(*(float*)EltPtr);
   case Type::DoubleTyID: return APFloat(*(double*)EltPtr);
   }
@@ -2320,11 +2429,9 @@ void ConstantArray::replaceUsesOfWithOnConstant(Value *From, Value *To,
 
   LLVMContextImpl *pImpl = getType()->getContext().pImpl;
 
-  std::pair<LLVMContextImpl::ArrayConstantsTy::MapKey, ConstantArray*> Lookup;
-  Lookup.first.first = cast<ArrayType>(getType());
-  Lookup.second = this;
-
-  std::vector<Constant*> &Values = Lookup.first.second;
+  SmallVector<Constant*, 8> Values;
+  LLVMContextImpl::ArrayConstantsTy::LookupKey Lookup;
+  Lookup.first = cast<ArrayType>(getType());
   Values.reserve(getNumOperands());  // Build replacement array.
 
   // Fill values with the modified operands of the constant array.  Also, 
@@ -2340,7 +2447,7 @@ void ConstantArray::replaceUsesOfWithOnConstant(Value *From, Value *To,
       ++NumUpdated;
     }
     Values.push_back(Val);
-    AllSame = Val == ToC;
+    AllSame &= Val == ToC;
   }
   
   Constant *Replacement = 0;
@@ -2350,18 +2457,18 @@ void ConstantArray::replaceUsesOfWithOnConstant(Value *From, Value *To,
     Replacement = UndefValue::get(getType());
   } else {
     // Check to see if we have this array type already.
-    bool Exists;
+    Lookup.second = makeArrayRef(Values);
     LLVMContextImpl::ArrayConstantsTy::MapTy::iterator I =
-      pImpl->ArrayConstants.InsertOrGetItem(Lookup, Exists);
+      pImpl->ArrayConstants.find(Lookup);
     
-    if (Exists) {
-      Replacement = I->second;
+    if (I != pImpl->ArrayConstants.map_end()) {
+      Replacement = I->first;
     } else {
       // Okay, the new shape doesn't exist in the system yet.  Instead of
       // creating a new constant array, inserting it, replaceallusesof'ing the
       // old with the new, then deleting the old... just update the current one
       // in place!
-      pImpl->ArrayConstants.MoveConstantToNewSlot(this, I);
+      pImpl->ArrayConstants.remove(this);
       
       // Update to the new value.  Optimize for the case when we have a single
       // operand that we're changing, but handle bulk updates efficiently.
@@ -2375,6 +2482,7 @@ void ConstantArray::replaceUsesOfWithOnConstant(Value *From, Value *To,
           if (getOperand(i) == From)
             setOperand(i, ToC);
       }
+      pImpl->ArrayConstants.insert(this);
       return;
     }
   }
@@ -2397,13 +2505,11 @@ void ConstantStruct::replaceUsesOfWithOnConstant(Value *From, Value *To,
   unsigned OperandToUpdate = U-OperandList;
   assert(getOperand(OperandToUpdate) == From && "ReplaceAllUsesWith broken!");
 
-  std::pair<LLVMContextImpl::StructConstantsTy::MapKey, ConstantStruct*> Lookup;
-  Lookup.first.first = cast<StructType>(getType());
-  Lookup.second = this;
-  std::vector<Constant*> &Values = Lookup.first.second;
+  SmallVector<Constant*, 8> Values;
+  LLVMContextImpl::StructConstantsTy::LookupKey Lookup;
+  Lookup.first = cast<StructType>(getType());
   Values.reserve(getNumOperands());  // Build replacement struct.
   
-  
   // Fill values with the modified operands of the constant struct.  Also, 
   // compute whether this turns into an all-zeros struct.
   bool isAllZeros = false;
@@ -2437,21 +2543,22 @@ void ConstantStruct::replaceUsesOfWithOnConstant(Value *From, Value *To,
     Replacement = UndefValue::get(getType());
   } else {
     // Check to see if we have this struct type already.
-    bool Exists;
+    Lookup.second = makeArrayRef(Values);
     LLVMContextImpl::StructConstantsTy::MapTy::iterator I =
-      pImpl->StructConstants.InsertOrGetItem(Lookup, Exists);
+      pImpl->StructConstants.find(Lookup);
     
-    if (Exists) {
-      Replacement = I->second;
+    if (I != pImpl->StructConstants.map_end()) {
+      Replacement = I->first;
     } else {
       // Okay, the new shape doesn't exist in the system yet.  Instead of
       // creating a new constant struct, inserting it, replaceallusesof'ing the
       // old with the new, then deleting the old... just update the current one
       // in place!
-      pImpl->StructConstants.MoveConstantToNewSlot(this, I);
+      pImpl->StructConstants.remove(this);
       
       // Update to the new value.
       setOperand(OperandToUpdate, ToC);
+      pImpl->StructConstants.insert(this);
       return;
     }
   }
@@ -2469,7 +2576,7 @@ void ConstantVector::replaceUsesOfWithOnConstant(Value *From, Value *To,
                                                  Use *U) {
   assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
   
-  std::vector<Constant*> Values;
+  SmallVector<Constant*, 8> Values;
   Values.reserve(getNumOperands());  // Build replacement array...
   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
     Constant *Val = getOperand(i);