Teach Function::hasAddressTaken that BlockAddress doesn't really take
[oota-llvm.git] / lib / VMCore / Constants.cpp
index 0fcce0940841a3993531650e954d265868cfcfb1..6dbc1449f245e14b808909387461177414c79888 100644 (file)
@@ -78,6 +78,11 @@ bool Constant::isAllOnesValue() const {
     if (Constant *Splat = CV->getSplatValue())
       return Splat->isAllOnesValue();
 
+  // Check for constant vectors which are splats of -1 values.
+  if (const ConstantDataVector *CV = dyn_cast<ConstantDataVector>(this))
+    if (Constant *Splat = CV->getSplatValue())
+      return Splat->isAllOnesValue();
+
   return false;
 }
 
@@ -112,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!");
   }
 }
 
@@ -129,7 +133,7 @@ Constant *Constant::getIntegerValue(Type *Ty, const APInt &V) {
 
   // Broadcast a scalar to a vector, if necessary.
   if (VectorType *VTy = dyn_cast<VectorType>(Ty))
-    C = ConstantVector::get(std::vector<Constant *>(VTy->getNumElements(), C));
+    C = ConstantVector::getSplat(VTy->getNumElements(), C);
 
   return C;
 }
@@ -145,13 +149,44 @@ Constant *Constant::getAllOnesValue(Type *Ty) {
     return ConstantFP::get(Ty->getContext(), FL);
   }
 
-  SmallVector<Constant*, 16> Elts;
   VectorType *VTy = cast<VectorType>(Ty);
-  Elts.resize(VTy->getNumElements(), getAllOnesValue(VTy->getElementType()));
-  assert(Elts[0] && "Invalid AllOnes value!");
-  return cast<ConstantVector>(ConstantVector::get(Elts));
+  return ConstantVector::getSplat(VTy->getNumElements(),
+                                  getAllOnesValue(VTy->getElementType()));
+}
+
+/// getAggregateElement - For aggregates (struct/array/vector) return the
+/// constant that corresponds to the specified element if possible, or null if
+/// not.  This can return null if the element index is a ConstantExpr, or if
+/// 'this' is a constant expr.
+Constant *Constant::getAggregateElement(unsigned Elt) const {
+  if (const ConstantStruct *CS = dyn_cast<ConstantStruct>(this))
+    return Elt < CS->getNumOperands() ? CS->getOperand(Elt) : 0;
+  
+  if (const ConstantArray *CA = dyn_cast<ConstantArray>(this))
+    return Elt < CA->getNumOperands() ? CA->getOperand(Elt) : 0;
+  
+  if (const ConstantVector *CV = dyn_cast<ConstantVector>(this))
+    return Elt < CV->getNumOperands() ? CV->getOperand(Elt) : 0;
+  
+  if (const ConstantAggregateZero *CAZ =dyn_cast<ConstantAggregateZero>(this))
+    return CAZ->getElementValue(Elt);
+  
+  if (const UndefValue *UV = dyn_cast<UndefValue>(this))
+    return UV->getElementValue(Elt);
+  
+  if (const ConstantDataSequential *CDS =dyn_cast<ConstantDataSequential>(this))
+    return Elt < CDS->getNumElements() ? CDS->getElementAsConstant(Elt) : 0;
+  return 0;
 }
 
+Constant *Constant::getAggregateElement(Constant *Elt) const {
+  assert(isa<IntegerType>(Elt->getType()) && "Index must be an integer");
+  if (ConstantInt *CI = dyn_cast<ConstantInt>(Elt))
+    return getAggregateElement(CI->getZExtValue());
+  return 0;
+}
+
+
 void Constant::destroyConstantImpl() {
   // When a Constant is destroyed, there may be lingering
   // references to the constant by other constants in the constant pool.  These
@@ -170,8 +205,7 @@ void Constant::destroyConstantImpl() {
     }
 #endif
     assert(isa<Constant>(V) && "References remain to Constant being destroyed");
-    Constant *CV = cast<Constant>(V);
-    CV->destroyConstant();
+    cast<Constant>(V)->destroyConstant();
 
     // The constant should remove itself from our use list...
     assert((use_empty() || use_back() != V) && "Constant not removed!");
@@ -277,36 +311,6 @@ Constant::PossibleRelocationsTy Constant::getRelocationInfo() const {
   return Result;
 }
 
-
-/// getVectorElements - This method, which is only valid on constant of vector
-/// type, returns the elements of the vector in the specified smallvector.
-/// This handles breaking down a vector undef into undef elements, etc.  For
-/// constant exprs and other cases we can't handle, we return an empty vector.
-void Constant::getVectorElements(SmallVectorImpl<Constant*> &Elts) const {
-  assert(getType()->isVectorTy() && "Not a vector constant!");
-  
-  if (const ConstantVector *CV = dyn_cast<ConstantVector>(this)) {
-    for (unsigned i = 0, e = CV->getNumOperands(); i != e; ++i)
-      Elts.push_back(CV->getOperand(i));
-    return;
-  }
-  
-  VectorType *VT = cast<VectorType>(getType());
-  if (isa<ConstantAggregateZero>(this)) {
-    Elts.assign(VT->getNumElements(), 
-                Constant::getNullValue(VT->getElementType()));
-    return;
-  }
-  
-  if (isa<UndefValue>(this)) {
-    Elts.assign(VT->getNumElements(), UndefValue::get(VT->getElementType()));
-    return;
-  }
-  
-  // Unknown type, must be constant expr etc.
-}
-
-
 /// removeDeadUsersOfConstant - If the specified constantexpr is dead, remove
 /// it.  This involves recursively eliminating any dead users of the
 /// constantexpr.
@@ -394,9 +398,8 @@ Constant *ConstantInt::getTrue(Type *Ty) {
   }
   assert(VTy->getElementType()->isIntegerTy(1) &&
          "True must be vector of i1 or i1.");
-  SmallVector<Constant*, 16> Splat(VTy->getNumElements(),
-                                   ConstantInt::getTrue(Ty->getContext()));
-  return ConstantVector::get(Splat);
+  return ConstantVector::getSplat(VTy->getNumElements(),
+                                  ConstantInt::getTrue(Ty->getContext()));
 }
 
 Constant *ConstantInt::getFalse(Type *Ty) {
@@ -407,9 +410,8 @@ Constant *ConstantInt::getFalse(Type *Ty) {
   }
   assert(VTy->getElementType()->isIntegerTy(1) &&
          "False must be vector of i1 or i1.");
-  SmallVector<Constant*, 16> Splat(VTy->getNumElements(),
-                                   ConstantInt::getFalse(Ty->getContext()));
-  return ConstantVector::get(Splat);
+  return ConstantVector::getSplat(VTy->getNumElements(),
+                                  ConstantInt::getFalse(Ty->getContext()));
 }
 
 
@@ -433,18 +435,17 @@ Constant *ConstantInt::get(Type *Ty, uint64_t V, bool isSigned) {
 
   // For vectors, broadcast the value.
   if (VectorType *VTy = dyn_cast<VectorType>(Ty))
-    return ConstantVector::get(SmallVector<Constant*,
-                                           16>(VTy->getNumElements(), C));
+    return ConstantVector::getSplat(VTy->getNumElements(), C);
 
   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);
 }
 
@@ -452,20 +453,19 @@ Constant *ConstantInt::getSigned(Type *Ty, int64_t V) {
   return get(Ty, V, true);
 }
 
-Constant *ConstantInt::get(TypeTy, 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!");
 
   // For vectors, broadcast the value.
   if (VectorType *VTy = dyn_cast<VectorType>(Ty))
-    return ConstantVector::get(
-      SmallVector<Constant *, 16>(VTy->getNumElements(), C));
+    return ConstantVector::getSplat(VTy->getNumElements(), C);
 
   return C;
 }
 
-ConstantIntConstantInt::get(IntegerType* Ty, StringRef Str,
+ConstantInt *ConstantInt::get(IntegerType* Ty, StringRef Str,
                               uint8_t radix) {
   return get(Ty->getContext(), APInt(Ty->getBitWidth(), Str, radix));
 }
@@ -495,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(TypeTy, double V) {
+Constant *ConstantFP::get(Type *Ty, double V) {
   LLVMContext &Context = Ty->getContext();
   
   APFloat FV(V);
@@ -506,14 +506,13 @@ Constant *ConstantFP::get(Type* Ty, double V) {
 
   // For vectors, broadcast the value.
   if (VectorType *VTy = dyn_cast<VectorType>(Ty))
-    return ConstantVector::get(
-      SmallVector<Constant *, 16>(VTy->getNumElements(), C));
+    return ConstantVector::getSplat(VTy->getNumElements(), C);
 
   return C;
 }
 
 
-Constant *ConstantFP::get(TypeTy, StringRef Str) {
+Constant *ConstantFP::get(Type *Ty, StringRef Str) {
   LLVMContext &Context = Ty->getContext();
 
   APFloat FV(*TypeToFloatSemantics(Ty->getScalarType()), Str);
@@ -521,31 +520,28 @@ Constant *ConstantFP::get(Type* Ty, StringRef Str) {
 
   // For vectors, broadcast the value.
   if (VectorType *VTy = dyn_cast<VectorType>(Ty))
-    return ConstantVector::get(
-      SmallVector<Constant *, 16>(VTy->getNumElements(), C));
+    return ConstantVector::getSplat(VTy->getNumElements(), C);
 
   return C; 
 }
 
 
-ConstantFP* ConstantFP::getNegativeZero(Type* Ty) {
+ConstantFP *ConstantFP::getNegativeZero(Type *Ty) {
   LLVMContext &Context = Ty->getContext();
-  APFloat apf = cast <ConstantFP>(Constant::getNullValue(Ty))->getValueAPF();
+  APFloat apf = cast<ConstantFP>(Constant::getNullValue(Ty))->getValueAPF();
   apf.changeSign();
   return get(Context, apf);
 }
 
 
-Constant *ConstantFP::getZeroValueForNegation(Type* Ty) {
-  if (VectorType *PTy = dyn_cast<VectorType>(Ty))
-    if (PTy->getElementType()->isFloatingPointTy()) {
-      SmallVector<Constant*, 16> zeros(PTy->getNumElements(),
-                           getNegativeZero(PTy->getElementType()));
-      return ConstantVector::get(zeros);
-    }
-
-  if (Ty->isFloatingPointTy()) 
-    return getNegativeZero(Ty);
+Constant *ConstantFP::getZeroValueForNegation(Type *Ty) {
+  Type *ScalarTy = Ty->getScalarType();
+  if (ScalarTy->isFloatingPointTy()) {
+    Constant *C = getNegativeZero(ScalarTy);
+    if (VectorType *VTy = dyn_cast<VectorType>(Ty))
+      return ConstantVector::getSplat(VTy->getNumElements(), C);
+    return C;
+  }
 
   return Constant::getNullValue(Ty);
 }
@@ -604,21 +600,19 @@ bool ConstantFP::isExactlyValue(const APFloat &V) const {
 
 /// getSequentialElement - If this CAZ has array or vector type, return a zero
 /// with the right element type.
-Constant *ConstantAggregateZero::getSequentialElement() {
-  return Constant::getNullValue(
-                            cast<SequentialType>(getType())->getElementType());
+Constant *ConstantAggregateZero::getSequentialElement() const {
+  return Constant::getNullValue(getType()->getSequentialElementType());
 }
 
 /// getStructElement - If this CAZ has struct type, return a zero with the
 /// right element type for the specified element.
-Constant *ConstantAggregateZero::getStructElement(unsigned Elt) {
-  return Constant::getNullValue(
-                              cast<StructType>(getType())->getElementType(Elt));
+Constant *ConstantAggregateZero::getStructElement(unsigned Elt) const {
+  return Constant::getNullValue(getType()->getStructElementType(Elt));
 }
 
 /// getElementValue - Return a zero of the right value for the specified GEP
 /// index if we can, otherwise return null (e.g. if C is a ConstantExpr).
-Constant *ConstantAggregateZero::getElementValue(Constant *C) {
+Constant *ConstantAggregateZero::getElementValue(Constant *C) const {
   if (isa<SequentialType>(getType()))
     return getSequentialElement();
   return getStructElement(cast<ConstantInt>(C)->getZExtValue());
@@ -626,7 +620,7 @@ Constant *ConstantAggregateZero::getElementValue(Constant *C) {
 
 /// getElementValue - Return a zero of the right value for the specified GEP
 /// index.
-Constant *ConstantAggregateZero::getElementValue(unsigned Idx) {
+Constant *ConstantAggregateZero::getElementValue(unsigned Idx) const {
   if (isa<SequentialType>(getType()))
     return getSequentialElement();
   return getStructElement(Idx);
@@ -639,19 +633,19 @@ Constant *ConstantAggregateZero::getElementValue(unsigned Idx) {
 
 /// getSequentialElement - If this undef has array or vector type, return an
 /// undef with the right element type.
-UndefValue *UndefValue::getSequentialElement() {
-  return UndefValue::get(cast<SequentialType>(getType())->getElementType());
+UndefValue *UndefValue::getSequentialElement() const {
+  return UndefValue::get(getType()->getSequentialElementType());
 }
 
 /// getStructElement - If this undef has struct type, return a zero with the
 /// right element type for the specified element.
-UndefValue *UndefValue::getStructElement(unsigned Elt) {
-  return UndefValue::get(cast<StructType>(getType())->getElementType(Elt));
+UndefValue *UndefValue::getStructElement(unsigned Elt) const {
+  return UndefValue::get(getType()->getStructElementType(Elt));
 }
 
 /// getElementValue - Return an undef of the right value for the specified GEP
 /// index if we can, otherwise return null (e.g. if C is a ConstantExpr).
-UndefValue *UndefValue::getElementValue(Constant *C) {
+UndefValue *UndefValue::getElementValue(Constant *C) const {
   if (isa<SequentialType>(getType()))
     return getSequentialElement();
   return getStructElement(cast<ConstantInt>(C)->getZExtValue());
@@ -659,7 +653,7 @@ UndefValue *UndefValue::getElementValue(Constant *C) {
 
 /// getElementValue - Return an undef of the right value for the specified GEP
 /// index.
-UndefValue *UndefValue::getElementValue(unsigned Idx) {
+UndefValue *UndefValue::getElementValue(unsigned Idx) const {
   if (isa<SequentialType>(getType()))
     return getSequentialElement();
   return getStructElement(Idx);
@@ -671,6 +665,13 @@ UndefValue *UndefValue::getElementValue(unsigned Idx) {
 //                            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,
@@ -685,44 +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
-  if (!V.empty()) {
-    Constant *C = V[0];
-    if (!C->isNullValue())
-      return pImpl->ArrayConstants.getOrCreate(Ty, V);
-    
-    for (unsigned i = 1, e = V.size(); i != e; ++i)
-      if (V[i] != C)
-        return pImpl->ArrayConstants.getOrCreate(Ty, V);
-  }
   
-  return ConstantAggregateZero::get(Ty);
-}
+  // 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);
 
-/// 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
@@ -730,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);
 }
@@ -760,14 +815,31 @@ ConstantStruct::ConstantStruct(StructType *T, ArrayRef<Constant *> V)
 
 // ConstantStruct accessors.
 Constant *ConstantStruct::get(StructType *ST, ArrayRef<Constant*> V) {
-  // Create a ConstantAggregateZero value if all elements are zeros.
-  for (unsigned i = 0, e = V.size(); i != e; ++i)
-    if (!V[i]->isNullValue())
-      return ST->getContext().pImpl->StructConstants.getOrCreate(ST, V);
-
   assert((ST->isOpaque() || ST->getNumElements() == V.size()) &&
          "Incorrect # elements specified to ConstantStruct::get");
-  return ConstantAggregateZero::get(ST);
+
+  // Create a ConstantAggregateZero value if all elements are zeros.
+  bool isZero = true;
+  bool isUndef = false;
+  
+  if (!V.empty()) {
+    isUndef = isa<UndefValue>(V[0]);
+    isZero = V[0]->isNullValue();
+    if (isUndef || isZero) {
+      for (unsigned i = 0, e = V.size(); i != e; ++i) {
+        if (!V[i]->isNullValue())
+          isZero = false;
+        if (!isa<UndefValue>(V[i]))
+          isUndef = false;
+      }
+    }
+  }  
+  if (isZero)
+    return ConstantAggregateZero::get(ST);
+  if (isUndef)
+    return UndefValue::get(ST);
+    
+  return ST->getContext().pImpl->StructConstants.getOrCreate(ST, V);
 }
 
 Constant *ConstantStruct::get(StructType *T, ...) {
@@ -814,10 +886,93 @@ 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);
+}
+
+
 // Utility function for determining if a ConstantExpr is a CastOp or not. This
 // can't be inline because we don't want to #include Instruction.h into
 // Constant.h
@@ -876,66 +1031,16 @@ unsigned ConstantExpr::getPredicate() const {
 /// one, but with the specified operand set to the specified value.
 Constant *
 ConstantExpr::getWithOperandReplaced(unsigned OpNo, Constant *Op) const {
-  assert(OpNo < getNumOperands() && "Operand num is out of range!");
   assert(Op->getType() == getOperand(OpNo)->getType() &&
          "Replacing operand with value of different type!");
   if (getOperand(OpNo) == Op)
     return const_cast<ConstantExpr*>(this);
+
+  SmallVector<Constant*, 8> NewOps;
+  for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
+    NewOps.push_back(i == OpNo ? Op : getOperand(i));
   
-  Constant *Op0, *Op1, *Op2;
-  switch (getOpcode()) {
-  case Instruction::Trunc:
-  case Instruction::ZExt:
-  case Instruction::SExt:
-  case Instruction::FPTrunc:
-  case Instruction::FPExt:
-  case Instruction::UIToFP:
-  case Instruction::SIToFP:
-  case Instruction::FPToUI:
-  case Instruction::FPToSI:
-  case Instruction::PtrToInt:
-  case Instruction::IntToPtr:
-  case Instruction::BitCast:
-    return ConstantExpr::getCast(getOpcode(), Op, getType());
-  case Instruction::Select:
-    Op0 = (OpNo == 0) ? Op : getOperand(0);
-    Op1 = (OpNo == 1) ? Op : getOperand(1);
-    Op2 = (OpNo == 2) ? Op : getOperand(2);
-    return ConstantExpr::getSelect(Op0, Op1, Op2);
-  case Instruction::InsertElement:
-    Op0 = (OpNo == 0) ? Op : getOperand(0);
-    Op1 = (OpNo == 1) ? Op : getOperand(1);
-    Op2 = (OpNo == 2) ? Op : getOperand(2);
-    return ConstantExpr::getInsertElement(Op0, Op1, Op2);
-  case Instruction::ExtractElement:
-    Op0 = (OpNo == 0) ? Op : getOperand(0);
-    Op1 = (OpNo == 1) ? Op : getOperand(1);
-    return ConstantExpr::getExtractElement(Op0, Op1);
-  case Instruction::ShuffleVector:
-    Op0 = (OpNo == 0) ? Op : getOperand(0);
-    Op1 = (OpNo == 1) ? Op : getOperand(1);
-    Op2 = (OpNo == 2) ? Op : getOperand(2);
-    return ConstantExpr::getShuffleVector(Op0, Op1, Op2);
-  case Instruction::GetElementPtr: {
-    SmallVector<Constant*, 8> Ops;
-    Ops.resize(getNumOperands()-1);
-    for (unsigned i = 1, e = getNumOperands(); i != e; ++i)
-      Ops[i-1] = getOperand(i);
-    if (OpNo == 0)
-      return
-        ConstantExpr::getGetElementPtr(Op, Ops,
-                                       cast<GEPOperator>(this)->isInBounds());
-    Ops[OpNo-1] = Op;
-    return
-      ConstantExpr::getGetElementPtr(getOperand(0), Ops,
-                                     cast<GEPOperator>(this)->isInBounds());
-  }
-  default:
-    assert(getNumOperands() == 2 && "Must be binary operator?");
-    Op0 = (OpNo == 0) ? Op : getOperand(0);
-    Op1 = (OpNo == 1) ? Op : getOperand(1);
-    return ConstantExpr::get(getOpcode(), Op0, Op1, SubclassOptionalData);
-  }
+  return getWithOperands(NewOps);
 }
 
 /// getWithOperands - This returns the current constant expression with the
@@ -971,12 +1076,15 @@ getWithOperands(ArrayRef<Constant*> Ops, Type *Ty) const {
     return ConstantExpr::getInsertElement(Ops[0], Ops[1], Ops[2]);
   case Instruction::ExtractElement:
     return ConstantExpr::getExtractElement(Ops[0], Ops[1]);
+  case Instruction::InsertValue:
+    return ConstantExpr::getInsertValue(Ops[0], Ops[1], getIndices());
+  case Instruction::ExtractValue:
+    return ConstantExpr::getExtractValue(Ops[0], getIndices());
   case Instruction::ShuffleVector:
     return ConstantExpr::getShuffleVector(Ops[0], Ops[1], Ops[2]);
   case Instruction::GetElementPtr:
-    return
-      ConstantExpr::getGetElementPtr(Ops[0], Ops.slice(1),
-                                     cast<GEPOperator>(this)->isInBounds());
+    return ConstantExpr::getGetElementPtr(Ops[0], Ops.slice(1),
+                                      cast<GEPOperator>(this)->isInBounds());
   case Instruction::ICmp:
   case Instruction::FCmp:
     return ConstantExpr::getCompare(getPredicate(), Ops[0], Ops[1]);
@@ -991,8 +1099,8 @@ getWithOperands(ArrayRef<Constant*> Ops, Type *Ty) const {
 //                      isValueValidForType implementations
 
 bool ConstantInt::isValueValidForType(Type *Ty, uint64_t Val) {
-  unsigned NumBits = cast<IntegerType>(Ty)->getBitWidth(); // assert okay
-  if (Ty == Type::getInt1Ty(Ty->getContext()))
+  unsigned NumBits = Ty->getIntegerBitWidth(); // assert okay
+  if (Ty->isIntegerTy(1))
     return Val == 0 || Val == 1;
   if (NumBits >= 64)
     return true; // always true, has to fit in largest type
@@ -1001,8 +1109,8 @@ bool ConstantInt::isValueValidForType(Type *Ty, uint64_t Val) {
 }
 
 bool ConstantInt::isValueValidForType(Type *Ty, int64_t Val) {
-  unsigned NumBits = cast<IntegerType>(Ty)->getBitWidth(); // assert okay
-  if (Ty == Type::getInt1Ty(Ty->getContext()))
+  unsigned NumBits = Ty->getIntegerBitWidth();
+  if (Ty->isIntegerTy(1))
     return Val == 0 || Val == 1 || Val == -1;
   if (NumBits >= 64)
     return true; // always true, has to fit in largest type
@@ -1087,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...
 //
@@ -1506,8 +1551,8 @@ Constant *ConstantExpr::getPtrToInt(Constant *C, Type *DstTy) {
   assert(DstTy->getScalarType()->isIntegerTy() && 
          "PtrToInt destination must be integer or integer vector");
   assert(isa<VectorType>(C->getType()) == isa<VectorType>(DstTy));
-  if (VectorType *VT = dyn_cast<VectorType>(C->getType()))
-    assert(VT->getNumElements() == cast<VectorType>(DstTy)->getNumElements() &&
+  if (isa<VectorType>(C->getType()))
+    assert(C->getType()->getVectorNumElements()==DstTy->getVectorNumElements()&&
            "Invalid cast between a different number of vector elements");
   return getFoldedCast(Instruction::PtrToInt, C, DstTy);
 }
@@ -1518,8 +1563,8 @@ Constant *ConstantExpr::getIntToPtr(Constant *C, Type *DstTy) {
   assert(DstTy->getScalarType()->isPointerTy() &&
          "IntToPtr destination must be a pointer or pointer vector");
   assert(isa<VectorType>(C->getType()) == isa<VectorType>(DstTy));
-  if (VectorType *VT = dyn_cast<VectorType>(C->getType()))
-    assert(VT->getNumElements() == cast<VectorType>(DstTy)->getNumElements() &&
+  if (isa<VectorType>(C->getType()))
+    assert(C->getType()->getVectorNumElements()==DstTy->getVectorNumElements()&&
            "Invalid cast between a different number of vector elements");
   return getFoldedCast(Instruction::IntToPtr, C, DstTy);
 }
@@ -1700,7 +1745,7 @@ Constant *ConstantExpr::getGetElementPtr(Constant *C, ArrayRef<Value *> Idxs,
   // Get the result type of the getelementptr!
   Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), Idxs);
   assert(Ty && "GEP indices invalid!");
-  unsigned AS = cast<PointerType>(C->getType())->getAddressSpace();
+  unsigned AS = C->getType()->getPointerAddressSpace();
   Type *ReqTy = Ty->getPointerTo(AS);
   
   assert(C->getType()->isPointerTy() &&
@@ -1780,7 +1825,7 @@ Constant *ConstantExpr::getExtractElement(Constant *Val, Constant *Idx) {
   const ExprMapKeyType Key(Instruction::ExtractElement,ArgVec);
   
   LLVMContextImpl *pImpl = Val->getContext().pImpl;
-  Type *ReqTy = cast<VectorType>(Val->getType())->getElementType();
+  Type *ReqTy = Val->getType()->getVectorElementType();
   return pImpl->ExprConstants.getOrCreate(ReqTy, Key);
 }
 
@@ -1788,8 +1833,8 @@ Constant *ConstantExpr::getInsertElement(Constant *Val, Constant *Elt,
                                          Constant *Idx) {
   assert(Val->getType()->isVectorTy() &&
          "Tried to create insertelement operation on non-vector type!");
-  assert(Elt->getType() == cast<VectorType>(Val->getType())->getElementType()
-         && "Insertelement types must match!");
+  assert(Elt->getType() == Val->getType()->getVectorElementType() &&
+         "Insertelement types must match!");
   assert(Idx->getType()->isIntegerTy(32) &&
          "Insertelement index must be i32 type!");
 
@@ -1813,8 +1858,8 @@ Constant *ConstantExpr::getShuffleVector(Constant *V1, Constant *V2,
   if (Constant *FC = ConstantFoldShuffleVectorInstruction(V1, V2, Mask))
     return FC;          // Fold a few common cases.
 
-  unsigned NElts = cast<VectorType>(Mask->getType())->getNumElements();
-  Type *EltTy = cast<VectorType>(V1->getType())->getElementType();
+  unsigned NElts = Mask->getType()->getVectorNumElements();
+  Type *EltTy = V1->getType()->getVectorElementType();
   Type *ShufTy = VectorType::get(EltTy, NElts);
 
   // Look up the constant in the table first to ensure uniqueness
@@ -1976,7 +2021,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)
@@ -2024,7 +2069,7 @@ bool ConstantDataSequential::isElementTypeCompatible(const Type *Ty) {
 unsigned ConstantDataSequential::getNumElements() const {
   if (ArrayType *AT = dyn_cast<ArrayType>(getType()))
     return AT->getNumElements();
-  return cast<VectorType>(getType())->getNumElements();
+  return getType()->getVectorNumElements();
 }
 
 
@@ -2050,10 +2095,10 @@ 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(cast<SequentialType>(Ty)->getElementType()));
+  assert(isElementTypeCompatible(Ty->getSequentialElementType()));
   // If the elements are all zero or there are no elements, return a CAZ, which
   // is more dense and canonical.
   if (isAllZeros(Elements))
@@ -2194,6 +2239,42 @@ Constant *ConstantDataVector::get(LLVMContext &Context, ArrayRef<double> Elts) {
   return getImpl(StringRef((char*)Elts.data(), Elts.size()*8), Ty);
 }
 
+Constant *ConstantDataVector::getSplat(unsigned NumElts, Constant *V) {
+  assert(isElementTypeCompatible(V->getType()) &&
+         "Element type not compatible with ConstantData");
+  if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
+    if (CI->getType()->isIntegerTy(8)) {
+      SmallVector<uint8_t, 16> Elts(NumElts, CI->getZExtValue());
+      return get(V->getContext(), Elts);
+    }
+    if (CI->getType()->isIntegerTy(16)) {
+      SmallVector<uint16_t, 16> Elts(NumElts, CI->getZExtValue());
+      return get(V->getContext(), Elts);
+    }
+    if (CI->getType()->isIntegerTy(32)) {
+      SmallVector<uint32_t, 16> Elts(NumElts, CI->getZExtValue());
+      return get(V->getContext(), Elts);
+    }
+    assert(CI->getType()->isIntegerTy(64) && "Unsupported ConstantData type");
+    SmallVector<uint64_t, 16> Elts(NumElts, CI->getZExtValue());
+    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);
+    }
+  }
+  return ConstantVector::getSplat(NumElts, V);
+}
+
+
 /// getElementAsInteger - If this is a sequential container of integers (of
 /// any size), return the specified element in the low bits of a uint64_t.
 uint64_t ConstantDataSequential::getElementAsInteger(unsigned Elt) const {
@@ -2203,8 +2284,8 @@ 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 (cast<IntegerType>(getElementType())->getBitWidth()) {
-  default: assert(0 && "Invalid bitwidth for CDS");
+  switch (getElementType()->getIntegerBitWidth()) {
+  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;
@@ -2218,7 +2299,8 @@ APFloat ConstantDataSequential::getElementAsAPFloat(unsigned Elt) const {
   const char *EltPtr = getElementPointer(Elt);
 
   switch (getElementType()->getTypeID()) {
-  default: assert("Accessor can only be used when element is float/double!");
+  default:
+    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);
   }
@@ -2270,6 +2352,20 @@ bool ConstantDataSequential::isCString() const {
   return Str.drop_back().find(0) == StringRef::npos;
 }
 
+/// getSplatValue - If this is a splat constant, meaning that all of the
+/// elements have the same value, return that value. Otherwise return NULL.
+Constant *ConstantDataVector::getSplatValue() const {
+  const char *Base = getRawDataValues().data();
+  
+  // Compare elements 1+ to the 0'th element.
+  unsigned EltSize = getElementByteSize();
+  for (unsigned i = 1, e = getNumElements(); i != e; ++i)
+    if (memcmp(Base, Base+i*EltSize, EltSize))
+      return 0;
+  
+  // If they're all the same, return the 0th one as a representative.
+  return getElementAsConstant(0);
+}
 
 //===----------------------------------------------------------------------===//
 //                replaceUsesOfWithOnConstant implementations
@@ -2292,56 +2388,46 @@ 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, 
   // compute whether this turns into an all-zeros array.
-  bool isAllZeros = false;
   unsigned NumUpdated = 0;
-  if (!ToC->isNullValue()) {
-    for (Use *O = OperandList, *E = OperandList+getNumOperands(); O != E; ++O) {
-      Constant *Val = cast<Constant>(O->get());
-      if (Val == From) {
-        Val = ToC;
-        ++NumUpdated;
-      }
-      Values.push_back(Val);
-    }
-  } else {
-    isAllZeros = true;
-    for (Use *O = OperandList, *E = OperandList+getNumOperands();O != E; ++O) {
-      Constant *Val = cast<Constant>(O->get());
-      if (Val == From) {
-        Val = ToC;
-        ++NumUpdated;
-      }
-      Values.push_back(Val);
-      if (isAllZeros) isAllZeros = Val->isNullValue();
+  
+  // Keep track of whether all the values in the array are "ToC".
+  bool AllSame = true;
+  for (Use *O = OperandList, *E = OperandList+getNumOperands(); O != E; ++O) {
+    Constant *Val = cast<Constant>(O->get());
+    if (Val == From) {
+      Val = ToC;
+      ++NumUpdated;
     }
+    Values.push_back(Val);
+    AllSame &= Val == ToC;
   }
   
   Constant *Replacement = 0;
-  if (isAllZeros) {
+  if (AllSame && ToC->isNullValue()) {
     Replacement = ConstantAggregateZero::get(getType());
+  } else if (AllSame && isa<UndefValue>(ToC)) {
+    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.
@@ -2355,6 +2441,7 @@ void ConstantArray::replaceUsesOfWithOnConstant(Value *From, Value *To,
           if (getOperand(i) == From)
             setOperand(i, ToC);
       }
+      pImpl->ArrayConstants.insert(this);
       return;
     }
   }
@@ -2377,26 +2464,32 @@ 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;
-  if (!ToC->isNullValue()) {
-    for (Use *O = OperandList, *E = OperandList + getNumOperands(); O != E; ++O)
-      Values.push_back(cast<Constant>(O->get()));
-  } else {
+  bool isAllUndef = false;
+  if (ToC->isNullValue()) {
     isAllZeros = true;
     for (Use *O = OperandList, *E = OperandList+getNumOperands(); O != E; ++O) {
       Constant *Val = cast<Constant>(O->get());
       Values.push_back(Val);
       if (isAllZeros) isAllZeros = Val->isNullValue();
     }
+  } else if (isa<UndefValue>(ToC)) {
+    isAllUndef = true;
+    for (Use *O = OperandList, *E = OperandList+getNumOperands(); O != E; ++O) {
+      Constant *Val = cast<Constant>(O->get());
+      Values.push_back(Val);
+      if (isAllUndef) isAllUndef = isa<UndefValue>(Val);
+    }
+  } else {
+    for (Use *O = OperandList, *E = OperandList + getNumOperands(); O != E; ++O)
+      Values.push_back(cast<Constant>(O->get()));
   }
   Values[OperandToUpdate] = ToC;
   
@@ -2405,23 +2498,26 @@ void ConstantStruct::replaceUsesOfWithOnConstant(Value *From, Value *To,
   Constant *Replacement = 0;
   if (isAllZeros) {
     Replacement = ConstantAggregateZero::get(getType());
+  } else if (isAllUndef) {
+    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;
     }
   }
@@ -2439,7 +2535,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);
@@ -2462,88 +2558,13 @@ void ConstantExpr::replaceUsesOfWithOnConstant(Value *From, Value *ToV,
   assert(isa<Constant>(ToV) && "Cannot make Constant refer to non-constant!");
   Constant *To = cast<Constant>(ToV);
   
-  Constant *Replacement = 0;
-  if (getOpcode() == Instruction::GetElementPtr) {
-    SmallVector<Constant*, 8> Indices;
-    Constant *Pointer = getOperand(0);
-    Indices.reserve(getNumOperands()-1);
-    if (Pointer == From) Pointer = To;
-    
-    for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
-      Constant *Val = getOperand(i);
-      if (Val == From) Val = To;
-      Indices.push_back(Val);
-    }
-    Replacement = ConstantExpr::getGetElementPtr(Pointer, Indices,
-                                         cast<GEPOperator>(this)->isInBounds());
-  } else if (getOpcode() == Instruction::ExtractValue) {
-    Constant *Agg = getOperand(0);
-    if (Agg == From) Agg = To;
-    
-    ArrayRef<unsigned> Indices = getIndices();
-    Replacement = ConstantExpr::getExtractValue(Agg, Indices);
-  } else if (getOpcode() == Instruction::InsertValue) {
-    Constant *Agg = getOperand(0);
-    Constant *Val = getOperand(1);
-    if (Agg == From) Agg = To;
-    if (Val == From) Val = To;
-    
-    ArrayRef<unsigned> Indices = getIndices();
-    Replacement = ConstantExpr::getInsertValue(Agg, Val, Indices);
-  } else if (isCast()) {
-    assert(getOperand(0) == From && "Cast only has one use!");
-    Replacement = ConstantExpr::getCast(getOpcode(), To, getType());
-  } else if (getOpcode() == Instruction::Select) {
-    Constant *C1 = getOperand(0);
-    Constant *C2 = getOperand(1);
-    Constant *C3 = getOperand(2);
-    if (C1 == From) C1 = To;
-    if (C2 == From) C2 = To;
-    if (C3 == From) C3 = To;
-    Replacement = ConstantExpr::getSelect(C1, C2, C3);
-  } else if (getOpcode() == Instruction::ExtractElement) {
-    Constant *C1 = getOperand(0);
-    Constant *C2 = getOperand(1);
-    if (C1 == From) C1 = To;
-    if (C2 == From) C2 = To;
-    Replacement = ConstantExpr::getExtractElement(C1, C2);
-  } else if (getOpcode() == Instruction::InsertElement) {
-    Constant *C1 = getOperand(0);
-    Constant *C2 = getOperand(1);
-    Constant *C3 = getOperand(1);
-    if (C1 == From) C1 = To;
-    if (C2 == From) C2 = To;
-    if (C3 == From) C3 = To;
-    Replacement = ConstantExpr::getInsertElement(C1, C2, C3);
-  } else if (getOpcode() == Instruction::ShuffleVector) {
-    Constant *C1 = getOperand(0);
-    Constant *C2 = getOperand(1);
-    Constant *C3 = getOperand(2);
-    if (C1 == From) C1 = To;
-    if (C2 == From) C2 = To;
-    if (C3 == From) C3 = To;
-    Replacement = ConstantExpr::getShuffleVector(C1, C2, C3);
-  } else if (isCompare()) {
-    Constant *C1 = getOperand(0);
-    Constant *C2 = getOperand(1);
-    if (C1 == From) C1 = To;
-    if (C2 == From) C2 = To;
-    if (getOpcode() == Instruction::ICmp)
-      Replacement = ConstantExpr::getICmp(getPredicate(), C1, C2);
-    else {
-      assert(getOpcode() == Instruction::FCmp);
-      Replacement = ConstantExpr::getFCmp(getPredicate(), C1, C2);
-    }
-  } else if (getNumOperands() == 2) {
-    Constant *C1 = getOperand(0);
-    Constant *C2 = getOperand(1);
-    if (C1 == From) C1 = To;
-    if (C2 == From) C2 = To;
-    Replacement = ConstantExpr::get(getOpcode(), C1, C2, SubclassOptionalData);
-  } else {
-    llvm_unreachable("Unknown ConstantExpr type!");
+  SmallVector<Constant*, 8> NewOps;
+  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
+    Constant *Op = getOperand(i);
+    NewOps.push_back(Op == From ? To : Op);
   }
   
+  Constant *Replacement = getWithOperands(NewOps);
   assert(Replacement != this && "I didn't contain From!");
   
   // Everyone using this now uses the replacement.