lib/VMCore/Constants.cpp

   1 //===-- Constants.cpp - Implement Constant nodes --------------------------===//
   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 the Constant* classes...
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Constants.h"
  15 #include "ConstantFold.h"
  16 #include "llvm/DerivedTypes.h"
  17 #include "llvm/GlobalValue.h"
  18 #include "llvm/Instructions.h"
  19 #include "llvm/MDNode.h"
  20 #include "llvm/Module.h"
  21 #include "llvm/ADT/FoldingSet.h"
  22 #include "llvm/ADT/StringExtras.h"
  23 #include "llvm/ADT/StringMap.h"
  24 #include "llvm/Support/Compiler.h"
  25 #include "llvm/Support/Debug.h"
  26 #include "llvm/Support/ErrorHandling.h"
  27 #include "llvm/Support/ManagedStatic.h"
  28 #include "llvm/Support/MathExtras.h"
  29 #include "llvm/System/Mutex.h"
  30 #include "llvm/System/RWMutex.h"
  31 #include "llvm/System/Threading.h"
  32 #include "llvm/ADT/DenseMap.h"
  33 #include "llvm/ADT/SmallVector.h"
  34 #include <algorithm>
  35 #include <map>
  36 using namespace llvm;
  37
  38 //===----------------------------------------------------------------------===//
  39 //                              Constant Class
  40 //===----------------------------------------------------------------------===//
  41
  42 // Becomes a no-op when multithreading is disabled.
  43 ManagedStatic<sys::SmartRWMutex<true> > ConstantsLock;
  44
  45 void Constant::destroyConstantImpl() {
  46   // When a Constant is destroyed, there may be lingering
  47   // references to the constant by other constants in the constant pool.  These
  48   // constants are implicitly dependent on the module that is being deleted,
  49   // but they don't know that.  Because we only find out when the CPV is
  50   // deleted, we must now notify all of our users (that should only be
  51   // Constants) that they are, in fact, invalid now and should be deleted.
  52   //
  53   while (!use_empty()) {
  54     Value *V = use_back();
  55 #ifndef NDEBUG      // Only in -g mode...
  56     if (!isa<Constant>(V))
  57       DOUT << "While deleting: " << *this
  58            << "\n\nUse still stuck around after Def is destroyed: "
  59            << *V << "\n\n";
  60 #endif
  61     assert(isa<Constant>(V) && "References remain to Constant being destroyed");
  62     Constant *CV = cast<Constant>(V);
  63     CV->destroyConstant();
  64
  65     // The constant should remove itself from our use list...
  66     assert((use_empty() || use_back() != V) && "Constant not removed!");
  67   }
  68
  69   // Value has no outstanding references it is safe to delete it now...
  70   delete this;
  71 }
  72
  73 /// canTrap - Return true if evaluation of this constant could trap.  This is
  74 /// true for things like constant expressions that could divide by zero.
  75 bool Constant::canTrap() const {
  76   assert(getType()->isFirstClassType() && "Cannot evaluate aggregate vals!");
  77   // The only thing that could possibly trap are constant exprs.
  78   const ConstantExpr *CE = dyn_cast<ConstantExpr>(this);
  79   if (!CE) return false;
  80
  81   // ConstantExpr traps if any operands can trap.
  82   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
  83     if (getOperand(i)->canTrap())
  84       return true;
  85
  86   // Otherwise, only specific operations can trap.
  87   switch (CE->getOpcode()) {
  88   default:
  89     return false;
  90   case Instruction::UDiv:
  91   case Instruction::SDiv:
  92   case Instruction::FDiv:
  93   case Instruction::URem:
  94   case Instruction::SRem:
  95   case Instruction::FRem:
  96     // Div and rem can trap if the RHS is not known to be non-zero.
  97     if (!isa<ConstantInt>(getOperand(1)) || getOperand(1)->isNullValue())
  98       return true;
  99     return false;
 100   }
 101 }
 102
 103 /// ContainsRelocations - Return true if the constant value contains relocations
 104 /// which cannot be resolved at compile time. Kind argument is used to filter
 105 /// only 'interesting' sorts of relocations.
 106 bool Constant::ContainsRelocations(unsigned Kind) const {
 107   if (const GlobalValue* GV = dyn_cast<GlobalValue>(this)) {
 108     bool isLocal = GV->hasLocalLinkage();
 109     if ((Kind & Reloc::Local) && isLocal) {
 110       // Global has local linkage and 'local' kind of relocations are
 111       // requested
 112       return true;
 113     }
 114
 115     if ((Kind & Reloc::Global) && !isLocal) {
 116       // Global has non-local linkage and 'global' kind of relocations are
 117       // requested
 118       return true;
 119     }
 120
 121     return false;
 122   }
 123
 124   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
 125     if (getOperand(i)->ContainsRelocations(Kind))
 126       return true;
 127
 128   return false;
 129 }
 130
 131 Constant *Constant::getAllOnesValue(const Type *Ty) {
 132   if (const IntegerType* ITy = dyn_cast<IntegerType>(Ty))
 133     return ConstantInt::get(APInt::getAllOnesValue(ITy->getBitWidth()));
 134   return ConstantVector::getAllOnesValue(cast<VectorType>(Ty));
 135 }
 136
 137 // Static constructor to create an integral constant with all bits set
 138 ConstantInt *ConstantInt::getAllOnesValue(const Type *Ty) {
 139   if (const IntegerType* ITy = dyn_cast<IntegerType>(Ty))
 140     return ConstantInt::get(APInt::getAllOnesValue(ITy->getBitWidth()));
 141   return 0;
 142 }
 143
 144 /// @returns the value for a vector integer constant of the given type that
 145 /// has all its bits set to true.
 146 /// @brief Get the all ones value
 147 ConstantVector *ConstantVector::getAllOnesValue(const VectorType *Ty) {
 148   std::vector<Constant*> Elts;
 149   Elts.resize(Ty->getNumElements(),
 150               ConstantInt::getAllOnesValue(Ty->getElementType()));
 151   assert(Elts[0] && "Not a vector integer type!");
 152   return cast<ConstantVector>(ConstantVector::get(Elts));
 153 }
 154
 155
 156 /// getVectorElements - This method, which is only valid on constant of vector
 157 /// type, returns the elements of the vector in the specified smallvector.
 158 /// This handles breaking down a vector undef into undef elements, etc.  For
 159 /// constant exprs and other cases we can't handle, we return an empty vector.
 160 void Constant::getVectorElements(LLVMContext &Context,
 161                                  SmallVectorImpl<Constant*> &Elts) const {
 162   assert(isa<VectorType>(getType()) && "Not a vector constant!");
 163
 164   if (const ConstantVector *CV = dyn_cast<ConstantVector>(this)) {
 165     for (unsigned i = 0, e = CV->getNumOperands(); i != e; ++i)
 166       Elts.push_back(CV->getOperand(i));
 167     return;
 168   }
 169
 170   const VectorType *VT = cast<VectorType>(getType());
 171   if (isa<ConstantAggregateZero>(this)) {
 172     Elts.assign(VT->getNumElements(),
 173                 Context.getNullValue(VT->getElementType()));
 174     return;
 175   }
 176
 177   if (isa<UndefValue>(this)) {
 178     Elts.assign(VT->getNumElements(), Context.getUndef(VT->getElementType()));
 179     return;
 180   }
 181
 182   // Unknown type, must be constant expr etc.
 183 }
 184
 185
 186
 187 //===----------------------------------------------------------------------===//
 188 //                                ConstantInt
 189 //===----------------------------------------------------------------------===//
 190
 191 ConstantInt::ConstantInt(const IntegerType *Ty, const APInt& V)
 192   : Constant(Ty, ConstantIntVal, 0, 0), Val(V) {
 193   assert(V.getBitWidth() == Ty->getBitWidth() && "Invalid constant for type");
 194 }
 195
 196 ConstantInt *ConstantInt::TheTrueVal = 0;
 197 ConstantInt *ConstantInt::TheFalseVal = 0;
 198
 199 namespace llvm {
 200   void CleanupTrueFalse(void *) {
 201     ConstantInt::ResetTrueFalse();
 202   }
 203 }
 204
 205 static ManagedCleanup<llvm::CleanupTrueFalse> TrueFalseCleanup;
 206
 207 ConstantInt *ConstantInt::CreateTrueFalseVals(bool WhichOne) {
 208   assert(TheTrueVal == 0 && TheFalseVal == 0);
 209   TheTrueVal  = get(Type::Int1Ty, 1);
 210   TheFalseVal = get(Type::Int1Ty, 0);
 211
 212   // Ensure that llvm_shutdown nulls out TheTrueVal/TheFalseVal.
 213   TrueFalseCleanup.Register();
 214
 215   return WhichOne ? TheTrueVal : TheFalseVal;
 216 }
 217
 218
 219 namespace {
 220   struct DenseMapAPIntKeyInfo {
 221     struct KeyTy {
 222       APInt val;
 223       const Type* type;
 224       KeyTy(const APInt& V, const Type* Ty) : val(V), type(Ty) {}
 225       KeyTy(const KeyTy& that) : val(that.val), type(that.type) {}
 226       bool operator==(const KeyTy& that) const {
 227         return type == that.type && this->val == that.val;
 228       }
 229       bool operator!=(const KeyTy& that) const {
 230         return !this->operator==(that);
 231       }
 232     };
 233     static inline KeyTy getEmptyKey() { return KeyTy(APInt(1,0), 0); }
 234     static inline KeyTy getTombstoneKey() { return KeyTy(APInt(1,1), 0); }
 235     static unsigned getHashValue(const KeyTy &Key) {
 236       return DenseMapInfo<void*>::getHashValue(Key.type) ^
 237         Key.val.getHashValue();
 238     }
 239     static bool isEqual(const KeyTy &LHS, const KeyTy &RHS) {
 240       return LHS == RHS;
 241     }
 242     static bool isPod() { return false; }
 243   };
 244 }
 245
 246
 247 typedef DenseMap<DenseMapAPIntKeyInfo::KeyTy, ConstantInt*,
 248                  DenseMapAPIntKeyInfo> IntMapTy;
 249 static ManagedStatic<IntMapTy> IntConstants;
 250
 251 ConstantInt *ConstantInt::get(const IntegerType *Ty,
 252                               uint64_t V, bool isSigned) {
 253   return get(APInt(Ty->getBitWidth(), V, isSigned));
 254 }
 255
 256 Constant *ConstantInt::get(const Type *Ty, uint64_t V, bool isSigned) {
 257   Constant *C = get(cast<IntegerType>(Ty->getScalarType()), V, isSigned);
 258
 259   // For vectors, broadcast the value.
 260   if (const VectorType *VTy = dyn_cast<VectorType>(Ty))
 261     return
 262       ConstantVector::get(std::vector<Constant *>(VTy->getNumElements(), C));
 263
 264   return C;
 265 }
 266
 267 // Get a ConstantInt from an APInt. Note that the value stored in the DenseMap
 268 // as the key, is a DenseMapAPIntKeyInfo::KeyTy which has provided the
 269 // operator== and operator!= to ensure that the DenseMap doesn't attempt to
 270 // compare APInt's of different widths, which would violate an APInt class
 271 // invariant which generates an assertion.
 272 ConstantInt *ConstantInt::get(const APInt& V) {
 273   // Get the corresponding integer type for the bit width of the value.
 274   const IntegerType *ITy = IntegerType::get(V.getBitWidth());
 275   // get an existing value or the insertion position
 276   DenseMapAPIntKeyInfo::KeyTy Key(V, ITy);
 277
 278   ConstantsLock->reader_acquire();
 279   ConstantInt *&Slot = (*IntConstants)[Key];
 280   ConstantsLock->reader_release();
 281
 282   if (!Slot) {
 283     sys::SmartScopedWriter<true> Writer(*ConstantsLock);
 284     ConstantInt *&NewSlot = (*IntConstants)[Key];
 285     if (!Slot) {
 286       NewSlot = new ConstantInt(ITy, V);
 287     }
 288
 289     return NewSlot;
 290   } else {
 291     return Slot;
 292   }
 293 }
 294
 295 Constant *ConstantInt::get(const Type *Ty, const APInt &V) {
 296   ConstantInt *C = ConstantInt::get(V);
 297   assert(C->getType() == Ty->getScalarType() &&
 298          "ConstantInt type doesn't match the type implied by its value!");
 299
 300   // For vectors, broadcast the value.
 301   if (const VectorType *VTy = dyn_cast<VectorType>(Ty))
 302     return
 303       ConstantVector::get(std::vector<Constant *>(VTy->getNumElements(), C));
 304
 305   return C;
 306 }
 307
 308 //===----------------------------------------------------------------------===//
 309 //                                ConstantFP
 310 //===----------------------------------------------------------------------===//
 311
 312 static const fltSemantics *TypeToFloatSemantics(const Type *Ty) {
 313   if (Ty == Type::FloatTy)
 314     return &APFloat::IEEEsingle;
 315   if (Ty == Type::DoubleTy)
 316     return &APFloat::IEEEdouble;
 317   if (Ty == Type::X86_FP80Ty)
 318     return &APFloat::x87DoubleExtended;
 319   else if (Ty == Type::FP128Ty)
 320     return &APFloat::IEEEquad;
 321
 322   assert(Ty == Type::PPC_FP128Ty && "Unknown FP format");
 323   return &APFloat::PPCDoubleDouble;
 324 }
 325
 326 ConstantFP::ConstantFP(const Type *Ty, const APFloat& V)
 327   : Constant(Ty, ConstantFPVal, 0, 0), Val(V) {
 328   assert(&V.getSemantics() == TypeToFloatSemantics(Ty) &&
 329          "FP type Mismatch");
 330 }
 331
 332 bool ConstantFP::isNullValue() const {
 333   return Val.isZero() && !Val.isNegative();
 334 }
 335
 336 bool ConstantFP::isExactlyValue(const APFloat& V) const {
 337   return Val.bitwiseIsEqual(V);
 338 }
 339
 340 namespace {
 341   struct DenseMapAPFloatKeyInfo {
 342     struct KeyTy {
 343       APFloat val;
 344       KeyTy(const APFloat& V) : val(V){}
 345       KeyTy(const KeyTy& that) : val(that.val) {}
 346       bool operator==(const KeyTy& that) const {
 347         return this->val.bitwiseIsEqual(that.val);
 348       }
 349       bool operator!=(const KeyTy& that) const {
 350         return !this->operator==(that);
 351       }
 352     };
 353     static inline KeyTy getEmptyKey() {
 354       return KeyTy(APFloat(APFloat::Bogus,1));
 355     }
 356     static inline KeyTy getTombstoneKey() {
 357       return KeyTy(APFloat(APFloat::Bogus,2));
 358     }
 359     static unsigned getHashValue(const KeyTy &Key) {
 360       return Key.val.getHashValue();
 361     }
 362     static bool isEqual(const KeyTy &LHS, const KeyTy &RHS) {
 363       return LHS == RHS;
 364     }
 365     static bool isPod() { return false; }
 366   };
 367 }
 368
 369 //---- ConstantFP::get() implementation...
 370 //
 371 typedef DenseMap<DenseMapAPFloatKeyInfo::KeyTy, ConstantFP*,
 372                  DenseMapAPFloatKeyInfo> FPMapTy;
 373
 374 static ManagedStatic<FPMapTy> FPConstants;
 375
 376 ConstantFP *ConstantFP::get(const APFloat &V) {
 377   DenseMapAPFloatKeyInfo::KeyTy Key(V);
 378
 379   ConstantsLock->reader_acquire();
 380   ConstantFP *&Slot = (*FPConstants)[Key];
 381   ConstantsLock->reader_release();
 382
 383   if (!Slot) {
 384     sys::SmartScopedWriter<true> Writer(*ConstantsLock);
 385     ConstantFP *&NewSlot = (*FPConstants)[Key];
 386     if (!NewSlot) {
 387       const Type *Ty;
 388       if (&V.getSemantics() == &APFloat::IEEEsingle)
 389         Ty = Type::FloatTy;
 390       else if (&V.getSemantics() == &APFloat::IEEEdouble)
 391         Ty = Type::DoubleTy;
 392       else if (&V.getSemantics() == &APFloat::x87DoubleExtended)
 393         Ty = Type::X86_FP80Ty;
 394       else if (&V.getSemantics() == &APFloat::IEEEquad)
 395         Ty = Type::FP128Ty;
 396       else {
 397         assert(&V.getSemantics() == &APFloat::PPCDoubleDouble &&
 398                "Unknown FP format");
 399         Ty = Type::PPC_FP128Ty;
 400       }
 401       NewSlot = new ConstantFP(Ty, V);
 402     }
 403
 404     return NewSlot;
 405   }
 406
 407   return Slot;
 408 }
 409
 410 /// get() - This returns a constant fp for the specified value in the
 411 /// specified type.  This should only be used for simple constant values like
 412 /// 2.0/1.0 etc, that are known-valid both as double and as the target format.
 413 Constant *ConstantFP::get(const Type *Ty, double V) {
 414   APFloat FV(V);
 415   bool ignored;
 416   FV.convert(*TypeToFloatSemantics(Ty->getScalarType()),
 417              APFloat::rmNearestTiesToEven, &ignored);
 418   Constant *C = get(FV);
 419
 420   // For vectors, broadcast the value.
 421   if (const VectorType *VTy = dyn_cast<VectorType>(Ty))
 422     return
 423       ConstantVector::get(std::vector<Constant *>(VTy->getNumElements(), C));
 424
 425   return C;
 426 }
 427
 428 //===----------------------------------------------------------------------===//
 429 //                            ConstantXXX Classes
 430 //===----------------------------------------------------------------------===//
 431
 432
 433 ConstantArray::ConstantArray(const ArrayType *T,
 434                              const std::vector<Constant*> &V)
 435   : Constant(T, ConstantArrayVal,
 436              OperandTraits<ConstantArray>::op_end(this) - V.size(),
 437              V.size()) {
 438   assert(V.size() == T->getNumElements() &&
 439          "Invalid initializer vector for constant array");
 440   Use *OL = OperandList;
 441   for (std::vector<Constant*>::const_iterator I = V.begin(), E = V.end();
 442        I != E; ++I, ++OL) {
 443     Constant *C = *I;
 444     assert((C->getType() == T->getElementType() ||
 445             (T->isAbstract() &&
 446              C->getType()->getTypeID() == T->getElementType()->getTypeID())) &&
 447            "Initializer for array element doesn't match array element type!");
 448     *OL = C;
 449   }
 450 }
 451
 452
 453 ConstantStruct::ConstantStruct(const StructType *T,
 454                                const std::vector<Constant*> &V)
 455   : Constant(T, ConstantStructVal,
 456              OperandTraits<ConstantStruct>::op_end(this) - V.size(),
 457              V.size()) {
 458   assert(V.size() == T->getNumElements() &&
 459          "Invalid initializer vector for constant structure");
 460   Use *OL = OperandList;
 461   for (std::vector<Constant*>::const_iterator I = V.begin(), E = V.end();
 462        I != E; ++I, ++OL) {
 463     Constant *C = *I;
 464     assert((C->getType() == T->getElementType(I-V.begin()) ||
 465             ((T->getElementType(I-V.begin())->isAbstract() ||
 466               C->getType()->isAbstract()) &&
 467              T->getElementType(I-V.begin())->getTypeID() ==
 468                    C->getType()->getTypeID())) &&
 469            "Initializer for struct element doesn't match struct element type!");
 470     *OL = C;
 471   }
 472 }
 473
 474
 475 ConstantVector::ConstantVector(const VectorType *T,
 476                                const std::vector<Constant*> &V)
 477   : Constant(T, ConstantVectorVal,
 478              OperandTraits<ConstantVector>::op_end(this) - V.size(),
 479              V.size()) {
 480   Use *OL = OperandList;
 481     for (std::vector<Constant*>::const_iterator I = V.begin(), E = V.end();
 482          I != E; ++I, ++OL) {
 483       Constant *C = *I;
 484       assert((C->getType() == T->getElementType() ||
 485             (T->isAbstract() &&
 486              C->getType()->getTypeID() == T->getElementType()->getTypeID())) &&
 487            "Initializer for vector element doesn't match vector element type!");
 488     *OL = C;
 489   }
 490 }
 491
 492
 493 namespace llvm {
 494 // We declare several classes private to this file, so use an anonymous
 495 // namespace
 496 namespace {
 497
 498 /// UnaryConstantExpr - This class is private to Constants.cpp, and is used
 499 /// behind the scenes to implement unary constant exprs.
 500 class VISIBILITY_HIDDEN UnaryConstantExpr : public ConstantExpr {
 501   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
 502 public:
 503   // allocate space for exactly one operand
 504   void *operator new(size_t s) {
 505     return User::operator new(s, 1);
 506   }
 507   UnaryConstantExpr(unsigned Opcode, Constant *C, const Type *Ty)
 508     : ConstantExpr(Ty, Opcode, &Op<0>(), 1) {
 509     Op<0>() = C;
 510   }
 511   /// Transparently provide more efficient getOperand methods.
 512   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 513 };
 514
 515 /// BinaryConstantExpr - This class is private to Constants.cpp, and is used
 516 /// behind the scenes to implement binary constant exprs.
 517 class VISIBILITY_HIDDEN BinaryConstantExpr : public ConstantExpr {
 518   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
 519 public:
 520   // allocate space for exactly two operands
 521   void *operator new(size_t s) {
 522     return User::operator new(s, 2);
 523   }
 524   BinaryConstantExpr(unsigned Opcode, Constant *C1, Constant *C2)
 525     : ConstantExpr(C1->getType(), Opcode, &Op<0>(), 2) {
 526     Op<0>() = C1;
 527     Op<1>() = C2;
 528   }
 529   /// Transparently provide more efficient getOperand methods.
 530   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 531 };
 532
 533 /// SelectConstantExpr - This class is private to Constants.cpp, and is used
 534 /// behind the scenes to implement select constant exprs.
 535 class VISIBILITY_HIDDEN SelectConstantExpr : public ConstantExpr {
 536   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
 537 public:
 538   // allocate space for exactly three operands
 539   void *operator new(size_t s) {
 540     return User::operator new(s, 3);
 541   }
 542   SelectConstantExpr(Constant *C1, Constant *C2, Constant *C3)
 543     : ConstantExpr(C2->getType(), Instruction::Select, &Op<0>(), 3) {
 544     Op<0>() = C1;
 545     Op<1>() = C2;
 546     Op<2>() = C3;
 547   }
 548   /// Transparently provide more efficient getOperand methods.
 549   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 550 };
 551
 552 /// ExtractElementConstantExpr - This class is private to
 553 /// Constants.cpp, and is used behind the scenes to implement
 554 /// extractelement constant exprs.
 555 class VISIBILITY_HIDDEN ExtractElementConstantExpr : public ConstantExpr {
 556   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
 557 public:
 558   // allocate space for exactly two operands
 559   void *operator new(size_t s) {
 560     return User::operator new(s, 2);
 561   }
 562   ExtractElementConstantExpr(Constant *C1, Constant *C2)
 563     : ConstantExpr(cast<VectorType>(C1->getType())->getElementType(),
 564                    Instruction::ExtractElement, &Op<0>(), 2) {
 565     Op<0>() = C1;
 566     Op<1>() = C2;
 567   }
 568   /// Transparently provide more efficient getOperand methods.
 569   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 570 };
 571
 572 /// InsertElementConstantExpr - This class is private to
 573 /// Constants.cpp, and is used behind the scenes to implement
 574 /// insertelement constant exprs.
 575 class VISIBILITY_HIDDEN InsertElementConstantExpr : public ConstantExpr {
 576   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
 577 public:
 578   // allocate space for exactly three operands
 579   void *operator new(size_t s) {
 580     return User::operator new(s, 3);
 581   }
 582   InsertElementConstantExpr(Constant *C1, Constant *C2, Constant *C3)
 583     : ConstantExpr(C1->getType(), Instruction::InsertElement,
 584                    &Op<0>(), 3) {
 585     Op<0>() = C1;
 586     Op<1>() = C2;
 587     Op<2>() = C3;
 588   }
 589   /// Transparently provide more efficient getOperand methods.
 590   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 591 };
 592
 593 /// ShuffleVectorConstantExpr - This class is private to
 594 /// Constants.cpp, and is used behind the scenes to implement
 595 /// shufflevector constant exprs.
 596 class VISIBILITY_HIDDEN ShuffleVectorConstantExpr : public ConstantExpr {
 597   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
 598 public:
 599   // allocate space for exactly three operands
 600   void *operator new(size_t s) {
 601     return User::operator new(s, 3);
 602   }
 603   ShuffleVectorConstantExpr(Constant *C1, Constant *C2, Constant *C3)
 604   : ConstantExpr(VectorType::get(
 605                    cast<VectorType>(C1->getType())->getElementType(),
 606                    cast<VectorType>(C3->getType())->getNumElements()),
 607                  Instruction::ShuffleVector,
 608                  &Op<0>(), 3) {
 609     Op<0>() = C1;
 610     Op<1>() = C2;
 611     Op<2>() = C3;
 612   }
 613   /// Transparently provide more efficient getOperand methods.
 614   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 615 };
 616
 617 /// ExtractValueConstantExpr - This class is private to
 618 /// Constants.cpp, and is used behind the scenes to implement
 619 /// extractvalue constant exprs.
 620 class VISIBILITY_HIDDEN ExtractValueConstantExpr : public ConstantExpr {
 621   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
 622 public:
 623   // allocate space for exactly one operand
 624   void *operator new(size_t s) {
 625     return User::operator new(s, 1);
 626   }
 627   ExtractValueConstantExpr(Constant *Agg,
 628                            const SmallVector<unsigned, 4> &IdxList,
 629                            const Type *DestTy)
 630     : ConstantExpr(DestTy, Instruction::ExtractValue, &Op<0>(), 1),
 631       Indices(IdxList) {
 632     Op<0>() = Agg;
 633   }
 634
 635   /// Indices - These identify which value to extract.
 636   const SmallVector<unsigned, 4> Indices;
 637
 638   /// Transparently provide more efficient getOperand methods.
 639   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 640 };
 641
 642 /// InsertValueConstantExpr - This class is private to
 643 /// Constants.cpp, and is used behind the scenes to implement
 644 /// insertvalue constant exprs.
 645 class VISIBILITY_HIDDEN InsertValueConstantExpr : public ConstantExpr {
 646   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
 647 public:
 648   // allocate space for exactly one operand
 649   void *operator new(size_t s) {
 650     return User::operator new(s, 2);
 651   }
 652   InsertValueConstantExpr(Constant *Agg, Constant *Val,
 653                           const SmallVector<unsigned, 4> &IdxList,
 654                           const Type *DestTy)
 655     : ConstantExpr(DestTy, Instruction::InsertValue, &Op<0>(), 2),
 656       Indices(IdxList) {
 657     Op<0>() = Agg;
 658     Op<1>() = Val;
 659   }
 660
 661   /// Indices - These identify the position for the insertion.
 662   const SmallVector<unsigned, 4> Indices;
 663
 664   /// Transparently provide more efficient getOperand methods.
 665   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 666 };
 667
 668
 669 /// GetElementPtrConstantExpr - This class is private to Constants.cpp, and is
 670 /// used behind the scenes to implement getelementpr constant exprs.
 671 class VISIBILITY_HIDDEN GetElementPtrConstantExpr : public ConstantExpr {
 672   GetElementPtrConstantExpr(Constant *C, const std::vector<Constant*> &IdxList,
 673                             const Type *DestTy);
 674 public:
 675   static GetElementPtrConstantExpr *Create(Constant *C,
 676                                            const std::vector<Constant*>&IdxList,
 677                                            const Type *DestTy) {
 678     return new(IdxList.size() + 1)
 679       GetElementPtrConstantExpr(C, IdxList, DestTy);
 680   }
 681   /// Transparently provide more efficient getOperand methods.
 682   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 683 };
 684
 685 // CompareConstantExpr - This class is private to Constants.cpp, and is used
 686 // behind the scenes to implement ICmp and FCmp constant expressions. This is
 687 // needed in order to store the predicate value for these instructions.
 688 struct VISIBILITY_HIDDEN CompareConstantExpr : public ConstantExpr {
 689   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
 690   // allocate space for exactly two operands
 691   void *operator new(size_t s) {
 692     return User::operator new(s, 2);
 693   }
 694   unsigned short predicate;
 695   CompareConstantExpr(const Type *ty, Instruction::OtherOps opc,
 696                       unsigned short pred,  Constant* LHS, Constant* RHS)
 697     : ConstantExpr(ty, opc, &Op<0>(), 2), predicate(pred) {
 698     Op<0>() = LHS;
 699     Op<1>() = RHS;
 700   }
 701   /// Transparently provide more efficient getOperand methods.
 702   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 703 };
 704
 705 } // end anonymous namespace
 706
 707 template <>
 708 struct OperandTraits<UnaryConstantExpr> : FixedNumOperandTraits<1> {
 709 };
 710 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(UnaryConstantExpr, Value)
 711
 712 template <>
 713 struct OperandTraits<BinaryConstantExpr> : FixedNumOperandTraits<2> {
 714 };
 715 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(BinaryConstantExpr, Value)
 716
 717 template <>
 718 struct OperandTraits<SelectConstantExpr> : FixedNumOperandTraits<3> {
 719 };
 720 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(SelectConstantExpr, Value)
 721
 722 template <>
 723 struct OperandTraits<ExtractElementConstantExpr> : FixedNumOperandTraits<2> {
 724 };
 725 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ExtractElementConstantExpr, Value)
 726
 727 template <>
 728 struct OperandTraits<InsertElementConstantExpr> : FixedNumOperandTraits<3> {
 729 };
 730 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(InsertElementConstantExpr, Value)
 731
 732 template <>
 733 struct OperandTraits<ShuffleVectorConstantExpr> : FixedNumOperandTraits<3> {
 734 };
 735 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ShuffleVectorConstantExpr, Value)
 736
 737 template <>
 738 struct OperandTraits<ExtractValueConstantExpr> : FixedNumOperandTraits<1> {
 739 };
 740 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ExtractValueConstantExpr, Value)
 741
 742 template <>
 743 struct OperandTraits<InsertValueConstantExpr> : FixedNumOperandTraits<2> {
 744 };
 745 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(InsertValueConstantExpr, Value)
 746
 747 template <>
 748 struct OperandTraits<GetElementPtrConstantExpr> : VariadicOperandTraits<1> {
 749 };
 750
 751 GetElementPtrConstantExpr::GetElementPtrConstantExpr
 752   (Constant *C,
 753    const std::vector<Constant*> &IdxList,
 754    const Type *DestTy)
 755     : ConstantExpr(DestTy, Instruction::GetElementPtr,
 756                    OperandTraits<GetElementPtrConstantExpr>::op_end(this)
 757                    - (IdxList.size()+1),
 758                    IdxList.size()+1) {
 759   OperandList[0] = C;
 760   for (unsigned i = 0, E = IdxList.size(); i != E; ++i)
 761     OperandList[i+1] = IdxList[i];
 762 }
 763
 764 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(GetElementPtrConstantExpr, Value)
 765
 766
 767 template <>
 768 struct OperandTraits<CompareConstantExpr> : FixedNumOperandTraits<2> {
 769 };
 770 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(CompareConstantExpr, Value)
 771
 772
 773 } // End llvm namespace
 774
 775
 776 // Utility function for determining if a ConstantExpr is a CastOp or not. This
 777 // can't be inline because we don't want to #include Instruction.h into
 778 // Constant.h
 779 bool ConstantExpr::isCast() const {
 780   return Instruction::isCast(getOpcode());
 781 }
 782
 783 bool ConstantExpr::isCompare() const {
 784   return getOpcode() == Instruction::ICmp || getOpcode() == Instruction::FCmp;
 785 }
 786
 787 bool ConstantExpr::hasIndices() const {
 788   return getOpcode() == Instruction::ExtractValue ||
 789          getOpcode() == Instruction::InsertValue;
 790 }
 791
 792 const SmallVector<unsigned, 4> &ConstantExpr::getIndices() const {
 793   if (const ExtractValueConstantExpr *EVCE =
 794         dyn_cast<ExtractValueConstantExpr>(this))
 795     return EVCE->Indices;
 796
 797   return cast<InsertValueConstantExpr>(this)->Indices;
 798 }
 799
 800 Constant *ConstantExpr::getNot(Constant *C) {
 801   assert(C->getType()->isIntOrIntVector() &&
 802          "Cannot NOT a nonintegral value!");
 803   return get(Instruction::Xor, C,
 804              Constant::getAllOnesValue(C->getType()));
 805 }
 806 Constant *ConstantExpr::getAdd(Constant *C1, Constant *C2) {
 807   return get(Instruction::Add, C1, C2);
 808 }
 809 Constant *ConstantExpr::getFAdd(Constant *C1, Constant *C2) {
 810   return get(Instruction::FAdd, C1, C2);
 811 }
 812 Constant *ConstantExpr::getSub(Constant *C1, Constant *C2) {
 813   return get(Instruction::Sub, C1, C2);
 814 }
 815 Constant *ConstantExpr::getFSub(Constant *C1, Constant *C2) {
 816   return get(Instruction::FSub, C1, C2);
 817 }
 818 Constant *ConstantExpr::getMul(Constant *C1, Constant *C2) {
 819   return get(Instruction::Mul, C1, C2);
 820 }
 821 Constant *ConstantExpr::getFMul(Constant *C1, Constant *C2) {
 822   return get(Instruction::FMul, C1, C2);
 823 }
 824 Constant *ConstantExpr::getUDiv(Constant *C1, Constant *C2) {
 825   return get(Instruction::UDiv, C1, C2);
 826 }
 827 Constant *ConstantExpr::getSDiv(Constant *C1, Constant *C2) {
 828   return get(Instruction::SDiv, C1, C2);
 829 }
 830 Constant *ConstantExpr::getFDiv(Constant *C1, Constant *C2) {
 831   return get(Instruction::FDiv, C1, C2);
 832 }
 833 Constant *ConstantExpr::getURem(Constant *C1, Constant *C2) {
 834   return get(Instruction::URem, C1, C2);
 835 }
 836 Constant *ConstantExpr::getSRem(Constant *C1, Constant *C2) {
 837   return get(Instruction::SRem, C1, C2);
 838 }
 839 Constant *ConstantExpr::getFRem(Constant *C1, Constant *C2) {
 840   return get(Instruction::FRem, C1, C2);
 841 }
 842 Constant *ConstantExpr::getAnd(Constant *C1, Constant *C2) {
 843   return get(Instruction::And, C1, C2);
 844 }
 845 Constant *ConstantExpr::getOr(Constant *C1, Constant *C2) {
 846   return get(Instruction::Or, C1, C2);
 847 }
 848 Constant *ConstantExpr::getXor(Constant *C1, Constant *C2) {
 849   return get(Instruction::Xor, C1, C2);
 850 }
 851 unsigned ConstantExpr::getPredicate() const {
 852   assert(getOpcode() == Instruction::FCmp ||
 853          getOpcode() == Instruction::ICmp);
 854   return ((const CompareConstantExpr*)this)->predicate;
 855 }
 856 Constant *ConstantExpr::getShl(Constant *C1, Constant *C2) {
 857   return get(Instruction::Shl, C1, C2);
 858 }
 859 Constant *ConstantExpr::getLShr(Constant *C1, Constant *C2) {
 860   return get(Instruction::LShr, C1, C2);
 861 }
 862 Constant *ConstantExpr::getAShr(Constant *C1, Constant *C2) {
 863   return get(Instruction::AShr, C1, C2);
 864 }
 865
 866 /// getWithOperandReplaced - Return a constant expression identical to this
 867 /// one, but with the specified operand set to the specified value.
 868 Constant *
 869 ConstantExpr::getWithOperandReplaced(unsigned OpNo, Constant *Op) const {
 870   assert(OpNo < getNumOperands() && "Operand num is out of range!");
 871   assert(Op->getType() == getOperand(OpNo)->getType() &&
 872          "Replacing operand with value of different type!");
 873   if (getOperand(OpNo) == Op)
 874     return const_cast<ConstantExpr*>(this);
 875
 876   Constant *Op0, *Op1, *Op2;
 877   switch (getOpcode()) {
 878   case Instruction::Trunc:
 879   case Instruction::ZExt:
 880   case Instruction::SExt:
 881   case Instruction::FPTrunc:
 882   case Instruction::FPExt:
 883   case Instruction::UIToFP:
 884   case Instruction::SIToFP:
 885   case Instruction::FPToUI:
 886   case Instruction::FPToSI:
 887   case Instruction::PtrToInt:
 888   case Instruction::IntToPtr:
 889   case Instruction::BitCast:
 890     return ConstantExpr::getCast(getOpcode(), Op, getType());
 891   case Instruction::Select:
 892     Op0 = (OpNo == 0) ? Op : getOperand(0);
 893     Op1 = (OpNo == 1) ? Op : getOperand(1);
 894     Op2 = (OpNo == 2) ? Op : getOperand(2);
 895     return ConstantExpr::getSelect(Op0, Op1, Op2);
 896   case Instruction::InsertElement:
 897     Op0 = (OpNo == 0) ? Op : getOperand(0);
 898     Op1 = (OpNo == 1) ? Op : getOperand(1);
 899     Op2 = (OpNo == 2) ? Op : getOperand(2);
 900     return ConstantExpr::getInsertElement(Op0, Op1, Op2);
 901   case Instruction::ExtractElement:
 902     Op0 = (OpNo == 0) ? Op : getOperand(0);
 903     Op1 = (OpNo == 1) ? Op : getOperand(1);
 904     return ConstantExpr::getExtractElement(Op0, Op1);
 905   case Instruction::ShuffleVector:
 906     Op0 = (OpNo == 0) ? Op : getOperand(0);
 907     Op1 = (OpNo == 1) ? Op : getOperand(1);
 908     Op2 = (OpNo == 2) ? Op : getOperand(2);
 909     return ConstantExpr::getShuffleVector(Op0, Op1, Op2);
 910   case Instruction::GetElementPtr: {
 911     SmallVector<Constant*, 8> Ops;
 912     Ops.resize(getNumOperands()-1);
 913     for (unsigned i = 1, e = getNumOperands(); i != e; ++i)
 914       Ops[i-1] = getOperand(i);
 915     if (OpNo == 0)
 916       return ConstantExpr::getGetElementPtr(Op, &Ops[0], Ops.size());
 917     Ops[OpNo-1] = Op;
 918     return ConstantExpr::getGetElementPtr(getOperand(0), &Ops[0], Ops.size());
 919   }
 920   default:
 921     assert(getNumOperands() == 2 && "Must be binary operator?");
 922     Op0 = (OpNo == 0) ? Op : getOperand(0);
 923     Op1 = (OpNo == 1) ? Op : getOperand(1);
 924     return ConstantExpr::get(getOpcode(), Op0, Op1);
 925   }
 926 }
 927
 928 /// getWithOperands - This returns the current constant expression with the
 929 /// operands replaced with the specified values.  The specified operands must
 930 /// match count and type with the existing ones.
 931 Constant *ConstantExpr::
 932 getWithOperands(Constant* const *Ops, unsigned NumOps) const {
 933   assert(NumOps == getNumOperands() && "Operand count mismatch!");
 934   bool AnyChange = false;
 935   for (unsigned i = 0; i != NumOps; ++i) {
 936     assert(Ops[i]->getType() == getOperand(i)->getType() &&
 937            "Operand type mismatch!");
 938     AnyChange |= Ops[i] != getOperand(i);
 939   }
 940   if (!AnyChange)  // No operands changed, return self.
 941     return const_cast<ConstantExpr*>(this);
 942
 943   switch (getOpcode()) {
 944   case Instruction::Trunc:
 945   case Instruction::ZExt:
 946   case Instruction::SExt:
 947   case Instruction::FPTrunc:
 948   case Instruction::FPExt:
 949   case Instruction::UIToFP:
 950   case Instruction::SIToFP:
 951   case Instruction::FPToUI:
 952   case Instruction::FPToSI:
 953   case Instruction::PtrToInt:
 954   case Instruction::IntToPtr:
 955   case Instruction::BitCast:
 956     return ConstantExpr::getCast(getOpcode(), Ops[0], getType());
 957   case Instruction::Select:
 958     return ConstantExpr::getSelect(Ops[0], Ops[1], Ops[2]);
 959   case Instruction::InsertElement:
 960     return ConstantExpr::getInsertElement(Ops[0], Ops[1], Ops[2]);
 961   case Instruction::ExtractElement:
 962     return ConstantExpr::getExtractElement(Ops[0], Ops[1]);
 963   case Instruction::ShuffleVector:
 964     return ConstantExpr::getShuffleVector(Ops[0], Ops[1], Ops[2]);
 965   case Instruction::GetElementPtr:
 966     return ConstantExpr::getGetElementPtr(Ops[0], &Ops[1], NumOps-1);
 967   case Instruction::ICmp:
 968   case Instruction::FCmp:
 969     return ConstantExpr::getCompare(getPredicate(), Ops[0], Ops[1]);
 970   default:
 971     assert(getNumOperands() == 2 && "Must be binary operator?");
 972     return ConstantExpr::get(getOpcode(), Ops[0], Ops[1]);
 973   }
 974 }
 975
 976
 977 //===----------------------------------------------------------------------===//
 978 //                      isValueValidForType implementations
 979
 980 bool ConstantInt::isValueValidForType(const Type *Ty, uint64_t Val) {
 981   unsigned NumBits = cast<IntegerType>(Ty)->getBitWidth(); // assert okay
 982   if (Ty == Type::Int1Ty)
 983     return Val == 0 || Val == 1;
 984   if (NumBits >= 64)
 985     return true; // always true, has to fit in largest type
 986   uint64_t Max = (1ll << NumBits) - 1;
 987   return Val <= Max;
 988 }
 989
 990 bool ConstantInt::isValueValidForType(const Type *Ty, int64_t Val) {
 991   unsigned NumBits = cast<IntegerType>(Ty)->getBitWidth(); // assert okay
 992   if (Ty == Type::Int1Ty)
 993     return Val == 0 || Val == 1 || Val == -1;
 994   if (NumBits >= 64)
 995     return true; // always true, has to fit in largest type
 996   int64_t Min = -(1ll << (NumBits-1));
 997   int64_t Max = (1ll << (NumBits-1)) - 1;
 998   return (Val >= Min && Val <= Max);
 999 }
1000
1001 bool ConstantFP::isValueValidForType(const Type *Ty, const APFloat& Val) {
1002   // convert modifies in place, so make a copy.
1003   APFloat Val2 = APFloat(Val);
1004   bool losesInfo;
1005   switch (Ty->getTypeID()) {
1006   default:
1007     return false;         // These can't be represented as floating point!
1008
1009   // FIXME rounding mode needs to be more flexible
1010   case Type::FloatTyID: {
1011     if (&Val2.getSemantics() == &APFloat::IEEEsingle)
1012       return true;
1013     Val2.convert(APFloat::IEEEsingle, APFloat::rmNearestTiesToEven, &losesInfo);
1014     return !losesInfo;
1015   }
1016   case Type::DoubleTyID: {
1017     if (&Val2.getSemantics() == &APFloat::IEEEsingle ||
1018         &Val2.getSemantics() == &APFloat::IEEEdouble)
1019       return true;
1020     Val2.convert(APFloat::IEEEdouble, APFloat::rmNearestTiesToEven, &losesInfo);
1021     return !losesInfo;
1022   }
1023   case Type::X86_FP80TyID:
1024     return &Val2.getSemantics() == &APFloat::IEEEsingle ||
1025            &Val2.getSemantics() == &APFloat::IEEEdouble ||
1026            &Val2.getSemantics() == &APFloat::x87DoubleExtended;
1027   case Type::FP128TyID:
1028     return &Val2.getSemantics() == &APFloat::IEEEsingle ||
1029            &Val2.getSemantics() == &APFloat::IEEEdouble ||
1030            &Val2.getSemantics() == &APFloat::IEEEquad;
1031   case Type::PPC_FP128TyID:
1032     return &Val2.getSemantics() == &APFloat::IEEEsingle ||
1033            &Val2.getSemantics() == &APFloat::IEEEdouble ||
1034            &Val2.getSemantics() == &APFloat::PPCDoubleDouble;
1035   }
1036 }
1037
1038 //===----------------------------------------------------------------------===//
1039 //                      Factory Function Implementation
1040
1041
1042 // The number of operands for each ConstantCreator::create method is
1043 // determined by the ConstantTraits template.
1044 // ConstantCreator - A class that is used to create constants by
1045 // ValueMap*.  This class should be partially specialized if there is
1046 // something strange that needs to be done to interface to the ctor for the
1047 // constant.
1048 //
1049 namespace llvm {
1050   template<class ValType>
1051   struct ConstantTraits;
1052
1053   template<typename T, typename Alloc>
1054   struct VISIBILITY_HIDDEN ConstantTraits< std::vector<T, Alloc> > {
1055     static unsigned uses(const std::vector<T, Alloc>& v) {
1056       return v.size();
1057     }
1058   };
1059
1060   template<class ConstantClass, class TypeClass, class ValType>
1061   struct VISIBILITY_HIDDEN ConstantCreator {
1062     static ConstantClass *create(const TypeClass *Ty, const ValType &V) {
1063       return new(ConstantTraits<ValType>::uses(V)) ConstantClass(Ty, V);
1064     }
1065   };
1066
1067   template<class ConstantClass, class TypeClass>
1068   struct VISIBILITY_HIDDEN ConvertConstantType {
1069     static void convert(ConstantClass *OldC, const TypeClass *NewTy) {
1070       LLVM_UNREACHABLE("This type cannot be converted!");
1071     }
1072   };
1073
1074   template<class ValType, class TypeClass, class ConstantClass,
1075            bool HasLargeKey = false  /*true for arrays and structs*/ >
1076   class VISIBILITY_HIDDEN ValueMap : public AbstractTypeUser {
1077   public:
1078     typedef std::pair<const Type*, ValType> MapKey;
1079     typedef std::map<MapKey, Constant *> MapTy;
1080     typedef std::map<Constant*, typename MapTy::iterator> InverseMapTy;
1081     typedef std::map<const Type*, typename MapTy::iterator> AbstractTypeMapTy;
1082   private:
1083     /// Map - This is the main map from the element descriptor to the Constants.
1084     /// This is the primary way we avoid creating two of the same shape
1085     /// constant.
1086     MapTy Map;
1087
1088     /// InverseMap - If "HasLargeKey" is true, this contains an inverse mapping
1089     /// from the constants to their element in Map.  This is important for
1090     /// removal of constants from the array, which would otherwise have to scan
1091     /// through the map with very large keys.
1092     InverseMapTy InverseMap;
1093
1094     /// AbstractTypeMap - Map for abstract type constants.
1095     ///
1096     AbstractTypeMapTy AbstractTypeMap;
1097
1098     /// ValueMapLock - Mutex for this map.
1099     sys::SmartMutex<true> ValueMapLock;
1100
1101   public:
1102     // NOTE: This function is not locked.  It is the caller's responsibility
1103     // to enforce proper synchronization.
1104     typename MapTy::iterator map_end() { return Map.end(); }
1105
1106     /// InsertOrGetItem - Return an iterator for the specified element.
1107     /// If the element exists in the map, the returned iterator points to the
1108     /// entry and Exists=true.  If not, the iterator points to the newly
1109     /// inserted entry and returns Exists=false.  Newly inserted entries have
1110     /// I->second == 0, and should be filled in.
1111     /// NOTE: This function is not locked.  It is the caller's responsibility
1112     // to enforce proper synchronization.
1113     typename MapTy::iterator InsertOrGetItem(std::pair<MapKey, Constant *>
1114                                    &InsertVal,
1115                                    bool &Exists) {
1116       std::pair<typename MapTy::iterator, bool> IP = Map.insert(InsertVal);
1117       Exists = !IP.second;
1118       return IP.first;
1119     }
1120
1121 private:
1122     typename MapTy::iterator FindExistingElement(ConstantClass *CP) {
1123       if (HasLargeKey) {
1124         typename InverseMapTy::iterator IMI = InverseMap.find(CP);
1125         assert(IMI != InverseMap.end() && IMI->second != Map.end() &&
1126                IMI->second->second == CP &&
1127                "InverseMap corrupt!");
1128         return IMI->second;
1129       }
1130
1131       typename MapTy::iterator I =
1132         Map.find(MapKey(static_cast<const TypeClass*>(CP->getRawType()),
1133                         getValType(CP)));
1134       if (I == Map.end() || I->second != CP) {
1135         // FIXME: This should not use a linear scan.  If this gets to be a
1136         // performance problem, someone should look at this.
1137         for (I = Map.begin(); I != Map.end() && I->second != CP; ++I)
1138           /* empty */;
1139       }
1140       return I;
1141     }
1142
1143     ConstantClass* Create(const TypeClass *Ty, const ValType &V,
1144                           typename MapTy::iterator I) {
1145       ConstantClass* Result =
1146         ConstantCreator<ConstantClass,TypeClass,ValType>::create(Ty, V);
1147
1148       assert(Result->getType() == Ty && "Type specified is not correct!");
1149       I = Map.insert(I, std::make_pair(MapKey(Ty, V), Result));
1150
1151       if (HasLargeKey)  // Remember the reverse mapping if needed.
1152         InverseMap.insert(std::make_pair(Result, I));
1153
1154       // If the type of the constant is abstract, make sure that an entry
1155       // exists for it in the AbstractTypeMap.
1156       if (Ty->isAbstract()) {
1157         typename AbstractTypeMapTy::iterator TI =
1158                                                  AbstractTypeMap.find(Ty);
1159
1160         if (TI == AbstractTypeMap.end()) {
1161           // Add ourselves to the ATU list of the type.
1162           cast<DerivedType>(Ty)->addAbstractTypeUser(this);
1163
1164           AbstractTypeMap.insert(TI, std::make_pair(Ty, I));
1165         }
1166       }
1167
1168       return Result;
1169     }
1170 public:
1171
1172     /// getOrCreate - Return the specified constant from the map, creating it if
1173     /// necessary.
1174     ConstantClass *getOrCreate(const TypeClass *Ty, const ValType &V) {
1175       sys::SmartScopedLock<true> Lock(ValueMapLock);
1176       MapKey Lookup(Ty, V);
1177       ConstantClass* Result = 0;
1178
1179       typename MapTy::iterator I = Map.find(Lookup);
1180       // Is it in the map?
1181       if (I != Map.end())
1182         Result = static_cast<ConstantClass *>(I->second);
1183
1184       if (!Result) {
1185         // If no preexisting value, create one now...
1186         Result = Create(Ty, V, I);
1187       }
1188
1189       return Result;
1190     }
1191
1192     void remove(ConstantClass *CP) {
1193       sys::SmartScopedLock<true> Lock(ValueMapLock);
1194       typename MapTy::iterator I = FindExistingElement(CP);
1195       assert(I != Map.end() && "Constant not found in constant table!");
1196       assert(I->second == CP && "Didn't find correct element?");
1197
1198       if (HasLargeKey)  // Remember the reverse mapping if needed.
1199         InverseMap.erase(CP);
1200
1201       // Now that we found the entry, make sure this isn't the entry that
1202       // the AbstractTypeMap points to.
1203       const TypeClass *Ty = static_cast<const TypeClass *>(I->first.first);
1204       if (Ty->isAbstract()) {
1205         assert(AbstractTypeMap.count(Ty) &&
1206                "Abstract type not in AbstractTypeMap?");
1207         typename MapTy::iterator &ATMEntryIt = AbstractTypeMap[Ty];
1208         if (ATMEntryIt == I) {
1209           // Yes, we are removing the representative entry for this type.
1210           // See if there are any other entries of the same type.
1211           typename MapTy::iterator TmpIt = ATMEntryIt;
1212
1213           // First check the entry before this one...
1214           if (TmpIt != Map.begin()) {
1215             --TmpIt;
1216             if (TmpIt->first.first != Ty) // Not the same type, move back...
1217               ++TmpIt;
1218           }
1219
1220           // If we didn't find the same type, try to move forward...
1221           if (TmpIt == ATMEntryIt) {
1222             ++TmpIt;
1223             if (TmpIt == Map.end() || TmpIt->first.first != Ty)
1224               --TmpIt;   // No entry afterwards with the same type
1225           }
1226
1227           // If there is another entry in the map of the same abstract type,
1228           // update the AbstractTypeMap entry now.
1229           if (TmpIt != ATMEntryIt) {
1230             ATMEntryIt = TmpIt;
1231           } else {
1232             // Otherwise, we are removing the last instance of this type
1233             // from the table.  Remove from the ATM, and from user list.
1234             cast<DerivedType>(Ty)->removeAbstractTypeUser(this);
1235             AbstractTypeMap.erase(Ty);
1236           }
1237         }
1238       }
1239
1240       Map.erase(I);
1241     }
1242
1243
1244     /// MoveConstantToNewSlot - If we are about to change C to be the element
1245     /// specified by I, update our internal data structures to reflect this
1246     /// fact.
1247     /// NOTE: This function is not locked. It is the responsibility of the
1248     /// caller to enforce proper synchronization if using this method.
1249     void MoveConstantToNewSlot(ConstantClass *C, typename MapTy::iterator I) {
1250       // First, remove the old location of the specified constant in the map.
1251       typename MapTy::iterator OldI = FindExistingElement(C);
1252       assert(OldI != Map.end() && "Constant not found in constant table!");
1253       assert(OldI->second == C && "Didn't find correct element?");
1254
1255       // If this constant is the representative element for its abstract type,
1256       // update the AbstractTypeMap so that the representative element is I.
1257       if (C->getType()->isAbstract()) {
1258         typename AbstractTypeMapTy::iterator ATI =
1259             AbstractTypeMap.find(C->getType());
1260         assert(ATI != AbstractTypeMap.end() &&
1261                "Abstract type not in AbstractTypeMap?");
1262         if (ATI->second == OldI)
1263           ATI->second = I;
1264       }
1265
1266       // Remove the old entry from the map.
1267       Map.erase(OldI);
1268
1269       // Update the inverse map so that we know that this constant is now
1270       // located at descriptor I.
1271       if (HasLargeKey) {
1272         assert(I->second == C && "Bad inversemap entry!");
1273         InverseMap[C] = I;
1274       }
1275     }
1276
1277     void refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
1278       sys::SmartScopedLock<true> Lock(ValueMapLock);
1279       typename AbstractTypeMapTy::iterator I =
1280         AbstractTypeMap.find(cast<Type>(OldTy));
1281
1282       assert(I != AbstractTypeMap.end() &&
1283              "Abstract type not in AbstractTypeMap?");
1284
1285       // Convert a constant at a time until the last one is gone.  The last one
1286       // leaving will remove() itself, causing the AbstractTypeMapEntry to be
1287       // eliminated eventually.
1288       do {
1289         ConvertConstantType<ConstantClass,
1290                             TypeClass>::convert(
1291                                 static_cast<ConstantClass *>(I->second->second),
1292                                                 cast<TypeClass>(NewTy));
1293
1294         I = AbstractTypeMap.find(cast<Type>(OldTy));
1295       } while (I != AbstractTypeMap.end());
1296     }
1297
1298     // If the type became concrete without being refined to any other existing
1299     // type, we just remove ourselves from the ATU list.
1300     void typeBecameConcrete(const DerivedType *AbsTy) {
1301       AbsTy->removeAbstractTypeUser(this);
1302     }
1303
1304     void dump() const {
1305       DOUT << "Constant.cpp: ValueMap\n";
1306     }
1307   };
1308 }
1309
1310
1311
1312 //---- ConstantAggregateZero::get() implementation...
1313 //
1314 namespace llvm {
1315   // ConstantAggregateZero does not take extra "value" argument...
1316   template<class ValType>
1317   struct ConstantCreator<ConstantAggregateZero, Type, ValType> {
1318     static ConstantAggregateZero *create(const Type *Ty, const ValType &V){
1319       return new ConstantAggregateZero(Ty);
1320     }
1321   };
1322
1323   template<>
1324   struct ConvertConstantType<ConstantAggregateZero, Type> {
1325     static void convert(ConstantAggregateZero *OldC, const Type *NewTy) {
1326       // Make everyone now use a constant of the new type...
1327       Constant *New = ConstantAggregateZero::get(NewTy);
1328       assert(New != OldC && "Didn't replace constant??");
1329       OldC->uncheckedReplaceAllUsesWith(New);
1330       OldC->destroyConstant();     // This constant is now dead, destroy it.
1331     }
1332   };
1333 }
1334
1335 static ManagedStatic<ValueMap<char, Type,
1336                               ConstantAggregateZero> > AggZeroConstants;
1337
1338 static char getValType(ConstantAggregateZero *CPZ) { return 0; }
1339
1340 ConstantAggregateZero *ConstantAggregateZero::get(const Type *Ty) {
1341   assert((isa<StructType>(Ty) || isa<ArrayType>(Ty) || isa<VectorType>(Ty)) &&
1342          "Cannot create an aggregate zero of non-aggregate type!");
1343
1344   // Implicitly locked.
1345   return AggZeroConstants->getOrCreate(Ty, 0);
1346 }
1347
1348 /// destroyConstant - Remove the constant from the constant table...
1349 ///
1350 void ConstantAggregateZero::destroyConstant() {
1351   // Implicitly locked.
1352   AggZeroConstants->remove(this);
1353   destroyConstantImpl();
1354 }
1355
1356 //---- ConstantArray::get() implementation...
1357 //
1358 namespace llvm {
1359   template<>
1360   struct ConvertConstantType<ConstantArray, ArrayType> {
1361     static void convert(ConstantArray *OldC, const ArrayType *NewTy) {
1362       // Make everyone now use a constant of the new type...
1363       std::vector<Constant*> C;
1364       for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i)
1365         C.push_back(cast<Constant>(OldC->getOperand(i)));
1366       Constant *New = ConstantArray::get(NewTy, C);
1367       assert(New != OldC && "Didn't replace constant??");
1368       OldC->uncheckedReplaceAllUsesWith(New);
1369       OldC->destroyConstant();    // This constant is now dead, destroy it.
1370     }
1371   };
1372 }
1373
1374 static std::vector<Constant*> getValType(ConstantArray *CA) {
1375   std::vector<Constant*> Elements;
1376   Elements.reserve(CA->getNumOperands());
1377   for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i)
1378     Elements.push_back(cast<Constant>(CA->getOperand(i)));
1379   return Elements;
1380 }
1381
1382 typedef ValueMap<std::vector<Constant*>, ArrayType,
1383                  ConstantArray, true /*largekey*/> ArrayConstantsTy;
1384 static ManagedStatic<ArrayConstantsTy> ArrayConstants;
1385
1386 Constant *ConstantArray::get(const ArrayType *Ty,
1387                              const std::vector<Constant*> &V) {
1388   // If this is an all-zero array, return a ConstantAggregateZero object
1389   if (!V.empty()) {
1390     Constant *C = V[0];
1391     if (!C->isNullValue()) {
1392       // Implicitly locked.
1393       return ArrayConstants->getOrCreate(Ty, V);
1394     }
1395     for (unsigned i = 1, e = V.size(); i != e; ++i)
1396       if (V[i] != C) {
1397         // Implicitly locked.
1398         return ArrayConstants->getOrCreate(Ty, V);
1399       }
1400   }
1401
1402   return ConstantAggregateZero::get(Ty);
1403 }
1404
1405 /// destroyConstant - Remove the constant from the constant table...
1406 ///
1407 void ConstantArray::destroyConstant() {
1408   // Implicitly locked.
1409   ArrayConstants->remove(this);
1410   destroyConstantImpl();
1411 }
1412
1413 /// ConstantArray::get(const string&) - Return an array that is initialized to
1414 /// contain the specified string.  If length is zero then a null terminator is
1415 /// added to the specified string so that it may be used in a natural way.
1416 /// Otherwise, the length parameter specifies how much of the string to use
1417 /// and it won't be null terminated.
1418 ///
1419 Constant *ConstantArray::get(const std::string &Str, bool AddNull) {
1420   std::vector<Constant*> ElementVals;
1421   for (unsigned i = 0; i < Str.length(); ++i)
1422     ElementVals.push_back(ConstantInt::get(Type::Int8Ty, Str[i]));
1423
1424   // Add a null terminator to the string...
1425   if (AddNull) {
1426     ElementVals.push_back(ConstantInt::get(Type::Int8Ty, 0));
1427   }
1428
1429   ArrayType *ATy = ArrayType::get(Type::Int8Ty, ElementVals.size());
1430   return ConstantArray::get(ATy, ElementVals);
1431 }
1432
1433 /// isString - This method returns true if the array is an array of i8, and
1434 /// if the elements of the array are all ConstantInt's.
1435 bool ConstantArray::isString() const {
1436   // Check the element type for i8...
1437   if (getType()->getElementType() != Type::Int8Ty)
1438     return false;
1439   // Check the elements to make sure they are all integers, not constant
1440   // expressions.
1441   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
1442     if (!isa<ConstantInt>(getOperand(i)))
1443       return false;
1444   return true;
1445 }
1446
1447 /// isCString - This method returns true if the array is a string (see
1448 /// isString) and it ends in a null byte \\0 and does not contains any other
1449 /// null bytes except its terminator.
1450 bool ConstantArray::isCString(LLVMContext &Context) const {
1451   // Check the element type for i8...
1452   if (getType()->getElementType() != Type::Int8Ty)
1453     return false;
1454   Constant *Zero = Context.getNullValue(getOperand(0)->getType());
1455   // Last element must be a null.
1456   if (getOperand(getNumOperands()-1) != Zero)
1457     return false;
1458   // Other elements must be non-null integers.
1459   for (unsigned i = 0, e = getNumOperands()-1; i != e; ++i) {
1460     if (!isa<ConstantInt>(getOperand(i)))
1461       return false;
1462     if (getOperand(i) == Zero)
1463       return false;
1464   }
1465   return true;
1466 }
1467
1468
1469 /// getAsString - If the sub-element type of this array is i8
1470 /// then this method converts the array to an std::string and returns it.
1471 /// Otherwise, it asserts out.
1472 ///
1473 std::string ConstantArray::getAsString() const {
1474   assert(isString() && "Not a string!");
1475   std::string Result;
1476   Result.reserve(getNumOperands());
1477   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
1478     Result.push_back((char)cast<ConstantInt>(getOperand(i))->getZExtValue());
1479   return Result;
1480 }
1481
1482
1483 //---- ConstantStruct::get() implementation...
1484 //
1485
1486 namespace llvm {
1487   template<>
1488   struct ConvertConstantType<ConstantStruct, StructType> {
1489     static void convert(ConstantStruct *OldC, const StructType *NewTy) {
1490       // Make everyone now use a constant of the new type...
1491       std::vector<Constant*> C;
1492       for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i)
1493         C.push_back(cast<Constant>(OldC->getOperand(i)));
1494       Constant *New = ConstantStruct::get(NewTy, C);
1495       assert(New != OldC && "Didn't replace constant??");
1496
1497       OldC->uncheckedReplaceAllUsesWith(New);
1498       OldC->destroyConstant();    // This constant is now dead, destroy it.
1499     }
1500   };
1501 }
1502
1503 typedef ValueMap<std::vector<Constant*>, StructType,
1504                  ConstantStruct, true /*largekey*/> StructConstantsTy;
1505 static ManagedStatic<StructConstantsTy> StructConstants;
1506
1507 static std::vector<Constant*> getValType(ConstantStruct *CS) {
1508   std::vector<Constant*> Elements;
1509   Elements.reserve(CS->getNumOperands());
1510   for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i)
1511     Elements.push_back(cast<Constant>(CS->getOperand(i)));
1512   return Elements;
1513 }
1514
1515 Constant *ConstantStruct::get(const StructType *Ty,
1516                               const std::vector<Constant*> &V) {
1517   // Create a ConstantAggregateZero value if all elements are zeros...
1518   for (unsigned i = 0, e = V.size(); i != e; ++i)
1519     if (!V[i]->isNullValue())
1520       // Implicitly locked.
1521       return StructConstants->getOrCreate(Ty, V);
1522
1523   return ConstantAggregateZero::get(Ty);
1524 }
1525
1526 Constant *ConstantStruct::get(const std::vector<Constant*> &V, bool packed) {
1527   std::vector<const Type*> StructEls;
1528   StructEls.reserve(V.size());
1529   for (unsigned i = 0, e = V.size(); i != e; ++i)
1530     StructEls.push_back(V[i]->getType());
1531   return get(StructType::get(StructEls, packed), V);
1532 }
1533
1534 // destroyConstant - Remove the constant from the constant table...
1535 //
1536 void ConstantStruct::destroyConstant() {
1537   // Implicitly locked.
1538   StructConstants->remove(this);
1539   destroyConstantImpl();
1540 }
1541
1542 //---- ConstantVector::get() implementation...
1543 //
1544 namespace llvm {
1545   template<>
1546   struct ConvertConstantType<ConstantVector, VectorType> {
1547     static void convert(ConstantVector *OldC, const VectorType *NewTy) {
1548       // Make everyone now use a constant of the new type...
1549       std::vector<Constant*> C;
1550       for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i)
1551         C.push_back(cast<Constant>(OldC->getOperand(i)));
1552       Constant *New = ConstantVector::get(NewTy, C);
1553       assert(New != OldC && "Didn't replace constant??");
1554       OldC->uncheckedReplaceAllUsesWith(New);
1555       OldC->destroyConstant();    // This constant is now dead, destroy it.
1556     }
1557   };
1558 }
1559
1560 static std::vector<Constant*> getValType(ConstantVector *CP) {
1561   std::vector<Constant*> Elements;
1562   Elements.reserve(CP->getNumOperands());
1563   for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i)
1564     Elements.push_back(CP->getOperand(i));
1565   return Elements;
1566 }
1567
1568 static ManagedStatic<ValueMap<std::vector<Constant*>, VectorType,
1569                               ConstantVector> > VectorConstants;
1570
1571 Constant *ConstantVector::get(const VectorType *Ty,
1572                               const std::vector<Constant*> &V) {
1573   assert(!V.empty() && "Vectors can't be empty");
1574   // If this is an all-undef or alll-zero vector, return a
1575   // ConstantAggregateZero or UndefValue.
1576   Constant *C = V[0];
1577   bool isZero = C->isNullValue();
1578   bool isUndef = isa<UndefValue>(C);
1579
1580   if (isZero || isUndef) {
1581     for (unsigned i = 1, e = V.size(); i != e; ++i)
1582       if (V[i] != C) {
1583         isZero = isUndef = false;
1584         break;
1585       }
1586   }
1587
1588   if (isZero)
1589     return ConstantAggregateZero::get(Ty);
1590   if (isUndef)
1591     return UndefValue::get(Ty);
1592
1593   // Implicitly locked.
1594   return VectorConstants->getOrCreate(Ty, V);
1595 }
1596
1597 Constant *ConstantVector::get(const std::vector<Constant*> &V) {
1598   assert(!V.empty() && "Cannot infer type if V is empty");
1599   return get(VectorType::get(V.front()->getType(),V.size()), V);
1600 }
1601
1602 // destroyConstant - Remove the constant from the constant table...
1603 //
1604 void ConstantVector::destroyConstant() {
1605   // Implicitly locked.
1606   VectorConstants->remove(this);
1607   destroyConstantImpl();
1608 }
1609
1610 /// This function will return true iff every element in this vector constant
1611 /// is set to all ones.
1612 /// @returns true iff this constant's emements are all set to all ones.
1613 /// @brief Determine if the value is all ones.
1614 bool ConstantVector::isAllOnesValue() const {
1615   // Check out first element.
1616   const Constant *Elt = getOperand(0);
1617   const ConstantInt *CI = dyn_cast<ConstantInt>(Elt);
1618   if (!CI || !CI->isAllOnesValue()) return false;
1619   // Then make sure all remaining elements point to the same value.
1620   for (unsigned I = 1, E = getNumOperands(); I < E; ++I) {
1621     if (getOperand(I) != Elt) return false;
1622   }
1623   return true;
1624 }
1625
1626 /// getSplatValue - If this is a splat constant, where all of the
1627 /// elements have the same value, return that value. Otherwise return null.
1628 Constant *ConstantVector::getSplatValue() {
1629   // Check out first element.
1630   Constant *Elt = getOperand(0);
1631   // Then make sure all remaining elements point to the same value.
1632   for (unsigned I = 1, E = getNumOperands(); I < E; ++I)
1633     if (getOperand(I) != Elt) return 0;
1634   return Elt;
1635 }
1636
1637 //---- ConstantPointerNull::get() implementation...
1638 //
1639
1640 namespace llvm {
1641   // ConstantPointerNull does not take extra "value" argument...
1642   template<class ValType>
1643   struct ConstantCreator<ConstantPointerNull, PointerType, ValType> {
1644     static ConstantPointerNull *create(const PointerType *Ty, const ValType &V){
1645       return new ConstantPointerNull(Ty);
1646     }
1647   };
1648
1649   template<>
1650   struct ConvertConstantType<ConstantPointerNull, PointerType> {
1651     static void convert(ConstantPointerNull *OldC, const PointerType *NewTy) {
1652       // Make everyone now use a constant of the new type...
1653       Constant *New = ConstantPointerNull::get(NewTy);
1654       assert(New != OldC && "Didn't replace constant??");
1655       OldC->uncheckedReplaceAllUsesWith(New);
1656       OldC->destroyConstant();     // This constant is now dead, destroy it.
1657     }
1658   };
1659 }
1660
1661 static ManagedStatic<ValueMap<char, PointerType,
1662                               ConstantPointerNull> > NullPtrConstants;
1663
1664 static char getValType(ConstantPointerNull *) {
1665   return 0;
1666 }
1667
1668
1669 ConstantPointerNull *ConstantPointerNull::get(const PointerType *Ty) {
1670   // Implicitly locked.
1671   return NullPtrConstants->getOrCreate(Ty, 0);
1672 }
1673
1674 // destroyConstant - Remove the constant from the constant table...
1675 //
1676 void ConstantPointerNull::destroyConstant() {
1677   // Implicitly locked.
1678   NullPtrConstants->remove(this);
1679   destroyConstantImpl();
1680 }
1681
1682
1683 //---- UndefValue::get() implementation...
1684 //
1685
1686 namespace llvm {
1687   // UndefValue does not take extra "value" argument...
1688   template<class ValType>
1689   struct ConstantCreator<UndefValue, Type, ValType> {
1690     static UndefValue *create(const Type *Ty, const ValType &V) {
1691       return new UndefValue(Ty);
1692     }
1693   };
1694
1695   template<>
1696   struct ConvertConstantType<UndefValue, Type> {
1697     static void convert(UndefValue *OldC, const Type *NewTy) {
1698       // Make everyone now use a constant of the new type.
1699       Constant *New = UndefValue::get(NewTy);
1700       assert(New != OldC && "Didn't replace constant??");
1701       OldC->uncheckedReplaceAllUsesWith(New);
1702       OldC->destroyConstant();     // This constant is now dead, destroy it.
1703     }
1704   };
1705 }
1706
1707 static ManagedStatic<ValueMap<char, Type, UndefValue> > UndefValueConstants;
1708
1709 static char getValType(UndefValue *) {
1710   return 0;
1711 }
1712
1713
1714 UndefValue *UndefValue::get(const Type *Ty) {
1715   // Implicitly locked.
1716   return UndefValueConstants->getOrCreate(Ty, 0);
1717 }
1718
1719 // destroyConstant - Remove the constant from the constant table.
1720 //
1721 void UndefValue::destroyConstant() {
1722   // Implicitly locked.
1723   UndefValueConstants->remove(this);
1724   destroyConstantImpl();
1725 }
1726
1727 //---- MDString::get() implementation
1728 //
1729
1730 MDString::MDString(const char *begin, const char *end)
1731   : Constant(Type::MetadataTy, MDStringVal, 0, 0),
1732     StrBegin(begin), StrEnd(end) {}
1733
1734 static ManagedStatic<StringMap<MDString*> > MDStringCache;
1735
1736 MDString *MDString::get(const char *StrBegin, const char *StrEnd) {
1737   sys::SmartScopedWriter<true> Writer(*ConstantsLock);
1738   StringMapEntry<MDString *> &Entry = MDStringCache->GetOrCreateValue(
1739                                         StrBegin, StrEnd);
1740   MDString *&S = Entry.getValue();
1741   if (!S) S = new MDString(Entry.getKeyData(),
1742                            Entry.getKeyData() + Entry.getKeyLength());
1743
1744   return S;
1745 }
1746
1747 MDString *MDString::get(const std::string &Str) {
1748   sys::SmartScopedWriter<true> Writer(*ConstantsLock);
1749   StringMapEntry<MDString *> &Entry = MDStringCache->GetOrCreateValue(
1750                                         Str.data(), Str.data() + Str.size());
1751   MDString *&S = Entry.getValue();
1752   if (!S) S = new MDString(Entry.getKeyData(),
1753                            Entry.getKeyData() + Entry.getKeyLength());
1754
1755   return S;
1756 }
1757
1758 void MDString::destroyConstant() {
1759   sys::SmartScopedWriter<true> Writer(*ConstantsLock);
1760   MDStringCache->erase(MDStringCache->find(StrBegin, StrEnd));
1761   destroyConstantImpl();
1762 }
1763
1764 //---- MDNode::get() implementation
1765 //
1766
1767 static ManagedStatic<FoldingSet<MDNode> > MDNodeSet;
1768
1769 MDNode::MDNode(Value*const* Vals, unsigned NumVals)
1770   : Constant(Type::MetadataTy, MDNodeVal, 0, 0) {
1771   for (unsigned i = 0; i != NumVals; ++i)
1772     Node.push_back(ElementVH(Vals[i], this));
1773 }
1774
1775 void MDNode::Profile(FoldingSetNodeID &ID) const {
1776   for (const_elem_iterator I = elem_begin(), E = elem_end(); I != E; ++I)
1777     ID.AddPointer(*I);
1778 }
1779
1780 MDNode *MDNode::get(Value*const* Vals, unsigned NumVals) {
1781   FoldingSetNodeID ID;
1782   for (unsigned i = 0; i != NumVals; ++i)
1783     ID.AddPointer(Vals[i]);
1784
1785   ConstantsLock->reader_acquire();
1786   void *InsertPoint;
1787   MDNode *N = MDNodeSet->FindNodeOrInsertPos(ID, InsertPoint);
1788   ConstantsLock->reader_release();
1789
1790   if (!N) {
1791     sys::SmartScopedWriter<true> Writer(*ConstantsLock);
1792     N = MDNodeSet->FindNodeOrInsertPos(ID, InsertPoint);
1793     if (!N) {
1794       // InsertPoint will have been set by the FindNodeOrInsertPos call.
1795       N = new(0) MDNode(Vals, NumVals);
1796       MDNodeSet->InsertNode(N, InsertPoint);
1797     }
1798   }
1799   return N;
1800 }
1801
1802 void MDNode::destroyConstant() {
1803   sys::SmartScopedWriter<true> Writer(*ConstantsLock);
1804   MDNodeSet->RemoveNode(this);
1805
1806   destroyConstantImpl();
1807 }
1808
1809 //---- ConstantExpr::get() implementations...
1810 //
1811
1812 namespace {
1813
1814 struct ExprMapKeyType {
1815   typedef SmallVector<unsigned, 4> IndexList;
1816
1817   ExprMapKeyType(unsigned opc,
1818       const std::vector<Constant*> &ops,
1819       unsigned short pred = 0,
1820       const IndexList &inds = IndexList())
1821         : opcode(opc), predicate(pred), operands(ops), indices(inds) {}
1822   uint16_t opcode;
1823   uint16_t predicate;
1824   std::vector<Constant*> operands;
1825   IndexList indices;
1826   bool operator==(const ExprMapKeyType& that) const {
1827     return this->opcode == that.opcode &&
1828            this->predicate == that.predicate &&
1829            this->operands == that.operands &&
1830            this->indices == that.indices;
1831   }
1832   bool operator<(const ExprMapKeyType & that) const {
1833     return this->opcode < that.opcode ||
1834       (this->opcode == that.opcode && this->predicate < that.predicate) ||
1835       (this->opcode == that.opcode && this->predicate == that.predicate &&
1836        this->operands < that.operands) ||
1837       (this->opcode == that.opcode && this->predicate == that.predicate &&
1838        this->operands == that.operands && this->indices < that.indices);
1839   }
1840
1841   bool operator!=(const ExprMapKeyType& that) const {
1842     return !(*this == that);
1843   }
1844 };
1845
1846 }
1847
1848 namespace llvm {
1849   template<>
1850   struct ConstantCreator<ConstantExpr, Type, ExprMapKeyType> {
1851     static ConstantExpr *create(const Type *Ty, const ExprMapKeyType &V,
1852         unsigned short pred = 0) {
1853       if (Instruction::isCast(V.opcode))
1854         return new UnaryConstantExpr(V.opcode, V.operands[0], Ty);
1855       if ((V.opcode >= Instruction::BinaryOpsBegin &&
1856            V.opcode < Instruction::BinaryOpsEnd))
1857         return new BinaryConstantExpr(V.opcode, V.operands[0], V.operands[1]);
1858       if (V.opcode == Instruction::Select)
1859         return new SelectConstantExpr(V.operands[0], V.operands[1],
1860                                       V.operands[2]);
1861       if (V.opcode == Instruction::ExtractElement)
1862         return new ExtractElementConstantExpr(V.operands[0], V.operands[1]);
1863       if (V.opcode == Instruction::InsertElement)
1864         return new InsertElementConstantExpr(V.operands[0], V.operands[1],
1865                                              V.operands[2]);
1866       if (V.opcode == Instruction::ShuffleVector)
1867         return new ShuffleVectorConstantExpr(V.operands[0], V.operands[1],
1868                                              V.operands[2]);
1869       if (V.opcode == Instruction::InsertValue)
1870         return new InsertValueConstantExpr(V.operands[0], V.operands[1],
1871                                            V.indices, Ty);
1872       if (V.opcode == Instruction::ExtractValue)
1873         return new ExtractValueConstantExpr(V.operands[0], V.indices, Ty);
1874       if (V.opcode == Instruction::GetElementPtr) {
1875         std::vector<Constant*> IdxList(V.operands.begin()+1, V.operands.end());
1876         return GetElementPtrConstantExpr::Create(V.operands[0], IdxList, Ty);
1877       }
1878
1879       // The compare instructions are weird. We have to encode the predicate
1880       // value and it is combined with the instruction opcode by multiplying
1881       // the opcode by one hundred. We must decode this to get the predicate.
1882       if (V.opcode == Instruction::ICmp)
1883         return new CompareConstantExpr(Ty, Instruction::ICmp, V.predicate,
1884                                        V.operands[0], V.operands[1]);
1885       if (V.opcode == Instruction::FCmp)
1886         return new CompareConstantExpr(Ty, Instruction::FCmp, V.predicate,
1887                                        V.operands[0], V.operands[1]);
1888       LLVM_UNREACHABLE("Invalid ConstantExpr!");
1889       return 0;
1890     }
1891   };
1892
1893   template<>
1894   struct ConvertConstantType<ConstantExpr, Type> {
1895     static void convert(ConstantExpr *OldC, const Type *NewTy) {
1896       Constant *New;
1897       switch (OldC->getOpcode()) {
1898       case Instruction::Trunc:
1899       case Instruction::ZExt:
1900       case Instruction::SExt:
1901       case Instruction::FPTrunc:
1902       case Instruction::FPExt:
1903       case Instruction::UIToFP:
1904       case Instruction::SIToFP:
1905       case Instruction::FPToUI:
1906       case Instruction::FPToSI:
1907       case Instruction::PtrToInt:
1908       case Instruction::IntToPtr:
1909       case Instruction::BitCast:
1910         New = ConstantExpr::getCast(OldC->getOpcode(), OldC->getOperand(0),
1911                                     NewTy);
1912         break;
1913       case Instruction::Select:
1914         New = ConstantExpr::getSelectTy(NewTy, OldC->getOperand(0),
1915                                         OldC->getOperand(1),
1916                                         OldC->getOperand(2));
1917         break;
1918       default:
1919         assert(OldC->getOpcode() >= Instruction::BinaryOpsBegin &&
1920                OldC->getOpcode() <  Instruction::BinaryOpsEnd);
1921         New = ConstantExpr::getTy(NewTy, OldC->getOpcode(), OldC->getOperand(0),
1922                                   OldC->getOperand(1));
1923         break;
1924       case Instruction::GetElementPtr:
1925         // Make everyone now use a constant of the new type...
1926         std::vector<Value*> Idx(OldC->op_begin()+1, OldC->op_end());
1927         New = ConstantExpr::getGetElementPtrTy(NewTy, OldC->getOperand(0),
1928                                                &Idx[0], Idx.size());
1929         break;
1930       }
1931
1932       assert(New != OldC && "Didn't replace constant??");
1933       OldC->uncheckedReplaceAllUsesWith(New);
1934       OldC->destroyConstant();    // This constant is now dead, destroy it.
1935     }
1936   };
1937 } // end namespace llvm
1938
1939
1940 static ExprMapKeyType getValType(ConstantExpr *CE) {
1941   std::vector<Constant*> Operands;
1942   Operands.reserve(CE->getNumOperands());
1943   for (unsigned i = 0, e = CE->getNumOperands(); i != e; ++i)
1944     Operands.push_back(cast<Constant>(CE->getOperand(i)));
1945   return ExprMapKeyType(CE->getOpcode(), Operands,
1946       CE->isCompare() ? CE->getPredicate() : 0,
1947       CE->hasIndices() ?
1948         CE->getIndices() : SmallVector<unsigned, 4>());
1949 }
1950
1951 static ManagedStatic<ValueMap<ExprMapKeyType, Type,
1952                               ConstantExpr> > ExprConstants;
1953
1954 /// This is a utility function to handle folding of casts and lookup of the
1955 /// cast in the ExprConstants map. It is used by the various get* methods below.
1956 static inline Constant *getFoldedCast(
1957   Instruction::CastOps opc, Constant *C, const Type *Ty) {
1958   assert(Ty->isFirstClassType() && "Cannot cast to an aggregate type!");
1959   // Fold a few common cases
1960   if (Constant *FC =
1961                     ConstantFoldCastInstruction(getGlobalContext(), opc, C, Ty))
1962     return FC;
1963
1964   // Look up the constant in the table first to ensure uniqueness
1965   std::vector<Constant*> argVec(1, C);
1966   ExprMapKeyType Key(opc, argVec);
1967
1968   // Implicitly locked.
1969   return ExprConstants->getOrCreate(Ty, Key);
1970 }
1971
1972 Constant *ConstantExpr::getCast(unsigned oc, Constant *C, const Type *Ty) {
1973   Instruction::CastOps opc = Instruction::CastOps(oc);
1974   assert(Instruction::isCast(opc) && "opcode out of range");
1975   assert(C && Ty && "Null arguments to getCast");
1976   assert(Ty->isFirstClassType() && "Cannot cast to an aggregate type!");
1977
1978   switch (opc) {
1979     default:
1980       LLVM_UNREACHABLE("Invalid cast opcode");
1981       break;
1982     case Instruction::Trunc:    return getTrunc(C, Ty);
1983     case Instruction::ZExt:     return getZExt(C, Ty);
1984     case Instruction::SExt:     return getSExt(C, Ty);
1985     case Instruction::FPTrunc:  return getFPTrunc(C, Ty);
1986     case Instruction::FPExt:    return getFPExtend(C, Ty);
1987     case Instruction::UIToFP:   return getUIToFP(C, Ty);
1988     case Instruction::SIToFP:   return getSIToFP(C, Ty);
1989     case Instruction::FPToUI:   return getFPToUI(C, Ty);
1990     case Instruction::FPToSI:   return getFPToSI(C, Ty);
1991     case Instruction::PtrToInt: return getPtrToInt(C, Ty);
1992     case Instruction::IntToPtr: return getIntToPtr(C, Ty);
1993     case Instruction::BitCast:  return getBitCast(C, Ty);
1994   }
1995   return 0;
1996 }
1997
1998 Constant *ConstantExpr::getZExtOrBitCast(Constant *C, const Type *Ty) {
1999   if (C->getType()->getScalarSizeInBits() == Ty->getScalarSizeInBits())
2000     return getCast(Instruction::BitCast, C, Ty);
2001   return getCast(Instruction::ZExt, C, Ty);
2002 }
2003
2004 Constant *ConstantExpr::getSExtOrBitCast(Constant *C, const Type *Ty) {
2005   if (C->getType()->getScalarSizeInBits() == Ty->getScalarSizeInBits())
2006     return getCast(Instruction::BitCast, C, Ty);
2007   return getCast(Instruction::SExt, C, Ty);
2008 }
2009
2010 Constant *ConstantExpr::getTruncOrBitCast(Constant *C, const Type *Ty) {
2011   if (C->getType()->getScalarSizeInBits() == Ty->getScalarSizeInBits())
2012     return getCast(Instruction::BitCast, C, Ty);
2013   return getCast(Instruction::Trunc, C, Ty);
2014 }
2015
2016 Constant *ConstantExpr::getPointerCast(Constant *S, const Type *Ty) {
2017   assert(isa<PointerType>(S->getType()) && "Invalid cast");
2018   assert((Ty->isInteger() || isa<PointerType>(Ty)) && "Invalid cast");
2019
2020   if (Ty->isInteger())
2021     return getCast(Instruction::PtrToInt, S, Ty);
2022   return getCast(Instruction::BitCast, S, Ty);
2023 }
2024
2025 Constant *ConstantExpr::getIntegerCast(Constant *C, const Type *Ty,
2026                                        bool isSigned) {
2027   assert(C->getType()->isIntOrIntVector() &&
2028          Ty->isIntOrIntVector() && "Invalid cast");
2029   unsigned SrcBits = C->getType()->getScalarSizeInBits();
2030   unsigned DstBits = Ty->getScalarSizeInBits();
2031   Instruction::CastOps opcode =
2032     (SrcBits == DstBits ? Instruction::BitCast :
2033      (SrcBits > DstBits ? Instruction::Trunc :
2034       (isSigned ? Instruction::SExt : Instruction::ZExt)));
2035   return getCast(opcode, C, Ty);
2036 }
2037
2038 Constant *ConstantExpr::getFPCast(Constant *C, const Type *Ty) {
2039   assert(C->getType()->isFPOrFPVector() && Ty->isFPOrFPVector() &&
2040          "Invalid cast");
2041   unsigned SrcBits = C->getType()->getScalarSizeInBits();
2042   unsigned DstBits = Ty->getScalarSizeInBits();
2043   if (SrcBits == DstBits)
2044     return C; // Avoid a useless cast
2045   Instruction::CastOps opcode =
2046      (SrcBits > DstBits ? Instruction::FPTrunc : Instruction::FPExt);
2047   return getCast(opcode, C, Ty);
2048 }
2049
2050 Constant *ConstantExpr::getTrunc(Constant *C, const Type *Ty) {
2051 #ifndef NDEBUG
2052   bool fromVec = C->getType()->getTypeID() == Type::VectorTyID;
2053   bool toVec = Ty->getTypeID() == Type::VectorTyID;
2054 #endif
2055   assert((fromVec == toVec) && "Cannot convert from scalar to/from vector");
2056   assert(C->getType()->isIntOrIntVector() && "Trunc operand must be integer");
2057   assert(Ty->isIntOrIntVector() && "Trunc produces only integral");
2058   assert(C->getType()->getScalarSizeInBits() > Ty->getScalarSizeInBits()&&
2059          "SrcTy must be larger than DestTy for Trunc!");
2060
2061   return getFoldedCast(Instruction::Trunc, C, Ty);
2062 }
2063
2064 Constant *ConstantExpr::getSExt(Constant *C, const Type *Ty) {
2065 #ifndef NDEBUG
2066   bool fromVec = C->getType()->getTypeID() == Type::VectorTyID;
2067   bool toVec = Ty->getTypeID() == Type::VectorTyID;
2068 #endif
2069   assert((fromVec == toVec) && "Cannot convert from scalar to/from vector");
2070   assert(C->getType()->isIntOrIntVector() && "SExt operand must be integral");
2071   assert(Ty->isIntOrIntVector() && "SExt produces only integer");
2072   assert(C->getType()->getScalarSizeInBits() < Ty->getScalarSizeInBits()&&
2073          "SrcTy must be smaller than DestTy for SExt!");
2074
2075   return getFoldedCast(Instruction::SExt, C, Ty);
2076 }
2077
2078 Constant *ConstantExpr::getZExt(Constant *C, const Type *Ty) {
2079 #ifndef NDEBUG
2080   bool fromVec = C->getType()->getTypeID() == Type::VectorTyID;
2081   bool toVec = Ty->getTypeID() == Type::VectorTyID;
2082 #endif
2083   assert((fromVec == toVec) && "Cannot convert from scalar to/from vector");
2084   assert(C->getType()->isIntOrIntVector() && "ZEXt operand must be integral");
2085   assert(Ty->isIntOrIntVector() && "ZExt produces only integer");
2086   assert(C->getType()->getScalarSizeInBits() < Ty->getScalarSizeInBits()&&
2087          "SrcTy must be smaller than DestTy for ZExt!");
2088
2089   return getFoldedCast(Instruction::ZExt, C, Ty);
2090 }
2091
2092 Constant *ConstantExpr::getFPTrunc(Constant *C, const Type *Ty) {
2093 #ifndef NDEBUG
2094   bool fromVec = C->getType()->getTypeID() == Type::VectorTyID;
2095   bool toVec = Ty->getTypeID() == Type::VectorTyID;
2096 #endif
2097   assert((fromVec == toVec) && "Cannot convert from scalar to/from vector");
2098   assert(C->getType()->isFPOrFPVector() && Ty->isFPOrFPVector() &&
2099          C->getType()->getScalarSizeInBits() > Ty->getScalarSizeInBits()&&
2100          "This is an illegal floating point truncation!");
2101   return getFoldedCast(Instruction::FPTrunc, C, Ty);
2102 }
2103
2104 Constant *ConstantExpr::getFPExtend(Constant *C, const Type *Ty) {
2105 #ifndef NDEBUG
2106   bool fromVec = C->getType()->getTypeID() == Type::VectorTyID;
2107   bool toVec = Ty->getTypeID() == Type::VectorTyID;
2108 #endif
2109   assert((fromVec == toVec) && "Cannot convert from scalar to/from vector");
2110   assert(C->getType()->isFPOrFPVector() && Ty->isFPOrFPVector() &&
2111          C->getType()->getScalarSizeInBits() < Ty->getScalarSizeInBits()&&
2112          "This is an illegal floating point extension!");
2113   return getFoldedCast(Instruction::FPExt, C, Ty);
2114 }
2115
2116 Constant *ConstantExpr::getUIToFP(Constant *C, const Type *Ty) {
2117 #ifndef NDEBUG
2118   bool fromVec = C->getType()->getTypeID() == Type::VectorTyID;
2119   bool toVec = Ty->getTypeID() == Type::VectorTyID;
2120 #endif
2121   assert((fromVec == toVec) && "Cannot convert from scalar to/from vector");
2122   assert(C->getType()->isIntOrIntVector() && Ty->isFPOrFPVector() &&
2123          "This is an illegal uint to floating point cast!");
2124   return getFoldedCast(Instruction::UIToFP, C, Ty);
2125 }
2126
2127 Constant *ConstantExpr::getSIToFP(Constant *C, const Type *Ty) {
2128 #ifndef NDEBUG
2129   bool fromVec = C->getType()->getTypeID() == Type::VectorTyID;
2130   bool toVec = Ty->getTypeID() == Type::VectorTyID;
2131 #endif
2132   assert((fromVec == toVec) && "Cannot convert from scalar to/from vector");
2133   assert(C->getType()->isIntOrIntVector() && Ty->isFPOrFPVector() &&
2134          "This is an illegal sint to floating point cast!");
2135   return getFoldedCast(Instruction::SIToFP, C, Ty);
2136 }
2137
2138 Constant *ConstantExpr::getFPToUI(Constant *C, const Type *Ty) {
2139 #ifndef NDEBUG
2140   bool fromVec = C->getType()->getTypeID() == Type::VectorTyID;
2141   bool toVec = Ty->getTypeID() == Type::VectorTyID;
2142 #endif
2143   assert((fromVec == toVec) && "Cannot convert from scalar to/from vector");
2144   assert(C->getType()->isFPOrFPVector() && Ty->isIntOrIntVector() &&
2145          "This is an illegal floating point to uint cast!");
2146   return getFoldedCast(Instruction::FPToUI, C, Ty);
2147 }
2148
2149 Constant *ConstantExpr::getFPToSI(Constant *C, const Type *Ty) {
2150 #ifndef NDEBUG
2151   bool fromVec = C->getType()->getTypeID() == Type::VectorTyID;
2152   bool toVec = Ty->getTypeID() == Type::VectorTyID;
2153 #endif
2154   assert((fromVec == toVec) && "Cannot convert from scalar to/from vector");
2155   assert(C->getType()->isFPOrFPVector() && Ty->isIntOrIntVector() &&
2156          "This is an illegal floating point to sint cast!");
2157   return getFoldedCast(Instruction::FPToSI, C, Ty);
2158 }
2159
2160 Constant *ConstantExpr::getPtrToInt(Constant *C, const Type *DstTy) {
2161   assert(isa<PointerType>(C->getType()) && "PtrToInt source must be pointer");
2162   assert(DstTy->isInteger() && "PtrToInt destination must be integral");
2163   return getFoldedCast(Instruction::PtrToInt, C, DstTy);
2164 }
2165
2166 Constant *ConstantExpr::getIntToPtr(Constant *C, const Type *DstTy) {
2167   assert(C->getType()->isInteger() && "IntToPtr source must be integral");
2168   assert(isa<PointerType>(DstTy) && "IntToPtr destination must be a pointer");
2169   return getFoldedCast(Instruction::IntToPtr, C, DstTy);
2170 }
2171
2172 Constant *ConstantExpr::getBitCast(Constant *C, const Type *DstTy) {
2173   // BitCast implies a no-op cast of type only. No bits change.  However, you
2174   // can't cast pointers to anything but pointers.
2175 #ifndef NDEBUG
2176   const Type *SrcTy = C->getType();
2177   assert((isa<PointerType>(SrcTy) == isa<PointerType>(DstTy)) &&
2178          "BitCast cannot cast pointer to non-pointer and vice versa");
2179
2180   // Now we know we're not dealing with mismatched pointer casts (ptr->nonptr
2181   // or nonptr->ptr). For all the other types, the cast is okay if source and
2182   // destination bit widths are identical.
2183   unsigned SrcBitSize = SrcTy->getPrimitiveSizeInBits();
2184   unsigned DstBitSize = DstTy->getPrimitiveSizeInBits();
2185 #endif
2186   assert(SrcBitSize == DstBitSize && "BitCast requires types of same width");
2187
2188   // It is common to ask for a bitcast of a value to its own type, handle this
2189   // speedily.
2190   if (C->getType() == DstTy) return C;
2191
2192   return getFoldedCast(Instruction::BitCast, C, DstTy);
2193 }
2194
2195 Constant *ConstantExpr::getTy(const Type *ReqTy, unsigned Opcode,
2196                               Constant *C1, Constant *C2) {
2197   // Check the operands for consistency first
2198   assert(Opcode >= Instruction::BinaryOpsBegin &&
2199          Opcode <  Instruction::BinaryOpsEnd   &&
2200          "Invalid opcode in binary constant expression");
2201   assert(C1->getType() == C2->getType() &&
2202          "Operand types in binary constant expression should match");
2203
2204   if (ReqTy == C1->getType() || ReqTy == Type::Int1Ty)
2205     if (Constant *FC = ConstantFoldBinaryInstruction(
2206                                             getGlobalContext(), Opcode, C1, C2))
2207       return FC;          // Fold a few common cases...
2208
2209   std::vector<Constant*> argVec(1, C1); argVec.push_back(C2);
2210   ExprMapKeyType Key(Opcode, argVec);
2211
2212   // Implicitly locked.
2213   return ExprConstants->getOrCreate(ReqTy, Key);
2214 }
2215
2216 Constant *ConstantExpr::getCompareTy(unsigned short predicate,
2217                                      Constant *C1, Constant *C2) {
2218   switch (predicate) {
2219     default: LLVM_UNREACHABLE("Invalid CmpInst predicate");
2220     case CmpInst::FCMP_FALSE: case CmpInst::FCMP_OEQ: case CmpInst::FCMP_OGT:
2221     case CmpInst::FCMP_OGE:   case CmpInst::FCMP_OLT: case CmpInst::FCMP_OLE:
2222     case CmpInst::FCMP_ONE:   case CmpInst::FCMP_ORD: case CmpInst::FCMP_UNO:
2223     case CmpInst::FCMP_UEQ:   case CmpInst::FCMP_UGT: case CmpInst::FCMP_UGE:
2224     case CmpInst::FCMP_ULT:   case CmpInst::FCMP_ULE: case CmpInst::FCMP_UNE:
2225     case CmpInst::FCMP_TRUE:
2226       return getFCmp(predicate, C1, C2);
2227
2228     case CmpInst::ICMP_EQ:  case CmpInst::ICMP_NE:  case CmpInst::ICMP_UGT:
2229     case CmpInst::ICMP_UGE: case CmpInst::ICMP_ULT: case CmpInst::ICMP_ULE:
2230     case CmpInst::ICMP_SGT: case CmpInst::ICMP_SGE: case CmpInst::ICMP_SLT:
2231     case CmpInst::ICMP_SLE:
2232       return getICmp(predicate, C1, C2);
2233   }
2234 }
2235
2236 Constant *ConstantExpr::get(unsigned Opcode, Constant *C1, Constant *C2) {
2237   // API compatibility: Adjust integer opcodes to floating-point opcodes.
2238   if (C1->getType()->isFPOrFPVector()) {
2239     if (Opcode == Instruction::Add) Opcode = Instruction::FAdd;
2240     else if (Opcode == Instruction::Sub) Opcode = Instruction::FSub;
2241     else if (Opcode == Instruction::Mul) Opcode = Instruction::FMul;
2242   }
2243 #ifndef NDEBUG
2244   switch (Opcode) {
2245   case Instruction::Add:
2246   case Instruction::Sub:
2247   case Instruction::Mul:
2248     assert(C1->getType() == C2->getType() && "Op types should be identical!");
2249     assert(C1->getType()->isIntOrIntVector() &&
2250            "Tried to create an integer operation on a non-integer type!");
2251     break;
2252   case Instruction::FAdd:
2253   case Instruction::FSub:
2254   case Instruction::FMul:
2255     assert(C1->getType() == C2->getType() && "Op types should be identical!");
2256     assert(C1->getType()->isFPOrFPVector() &&
2257            "Tried to create a floating-point operation on a "
2258            "non-floating-point type!");
2259     break;
2260   case Instruction::UDiv:
2261   case Instruction::SDiv:
2262     assert(C1->getType() == C2->getType() && "Op types should be identical!");
2263     assert(C1->getType()->isIntOrIntVector() &&
2264            "Tried to create an arithmetic operation on a non-arithmetic type!");
2265     break;
2266   case Instruction::FDiv:
2267     assert(C1->getType() == C2->getType() && "Op types should be identical!");
2268     assert(C1->getType()->isFPOrFPVector() &&
2269            "Tried to create an arithmetic operation on a non-arithmetic type!");
2270     break;
2271   case Instruction::URem:
2272   case Instruction::SRem:
2273     assert(C1->getType() == C2->getType() && "Op types should be identical!");
2274     assert(C1->getType()->isIntOrIntVector() &&
2275            "Tried to create an arithmetic operation on a non-arithmetic type!");
2276     break;
2277   case Instruction::FRem:
2278     assert(C1->getType() == C2->getType() && "Op types should be identical!");
2279     assert(C1->getType()->isFPOrFPVector() &&
2280            "Tried to create an arithmetic operation on a non-arithmetic type!");
2281     break;
2282   case Instruction::And:
2283   case Instruction::Or:
2284   case Instruction::Xor:
2285     assert(C1->getType() == C2->getType() && "Op types should be identical!");
2286     assert(C1->getType()->isIntOrIntVector() &&
2287            "Tried to create a logical operation on a non-integral type!");
2288     break;
2289   case Instruction::Shl:
2290   case Instruction::LShr:
2291   case Instruction::AShr:
2292     assert(C1->getType() == C2->getType() && "Op types should be identical!");
2293     assert(C1->getType()->isIntOrIntVector() &&
2294            "Tried to create a shift operation on a non-integer type!");
2295     break;
2296   default:
2297     break;
2298   }
2299 #endif
2300
2301   return getTy(C1->getType(), Opcode, C1, C2);
2302 }
2303
2304 Constant *ConstantExpr::getCompare(unsigned short pred,
2305                             Constant *C1, Constant *C2) {
2306   assert(C1->getType() == C2->getType() && "Op types should be identical!");
2307   return getCompareTy(pred, C1, C2);
2308 }
2309
2310 Constant *ConstantExpr::getSelectTy(const Type *ReqTy, Constant *C,
2311                                     Constant *V1, Constant *V2) {
2312   assert(!SelectInst::areInvalidOperands(C, V1, V2)&&"Invalid select operands");
2313
2314   if (ReqTy == V1->getType())
2315     if (Constant *SC = ConstantFoldSelectInstruction(
2316                                                 getGlobalContext(), C, V1, V2))
2317       return SC;        // Fold common cases
2318
2319   std::vector<Constant*> argVec(3, C);
2320   argVec[1] = V1;
2321   argVec[2] = V2;
2322   ExprMapKeyType Key(Instruction::Select, argVec);
2323
2324   // Implicitly locked.
2325   return ExprConstants->getOrCreate(ReqTy, Key);
2326 }
2327
2328 Constant *ConstantExpr::getGetElementPtrTy(const Type *ReqTy, Constant *C,
2329                                            Value* const *Idxs,
2330                                            unsigned NumIdx) {
2331   assert(GetElementPtrInst::getIndexedType(C->getType(), Idxs,
2332                                            Idxs+NumIdx) ==
2333          cast<PointerType>(ReqTy)->getElementType() &&
2334          "GEP indices invalid!");
2335
2336   if (Constant *FC = ConstantFoldGetElementPtr(
2337                                getGlobalContext(), C, (Constant**)Idxs, NumIdx))
2338     return FC;          // Fold a few common cases...
2339
2340   assert(isa<PointerType>(C->getType()) &&
2341          "Non-pointer type for constant GetElementPtr expression");
2342   // Look up the constant in the table first to ensure uniqueness
2343   std::vector<Constant*> ArgVec;
2344   ArgVec.reserve(NumIdx+1);
2345   ArgVec.push_back(C);
2346   for (unsigned i = 0; i != NumIdx; ++i)
2347     ArgVec.push_back(cast<Constant>(Idxs[i]));
2348   const ExprMapKeyType Key(Instruction::GetElementPtr, ArgVec);
2349
2350   // Implicitly locked.
2351   return ExprConstants->getOrCreate(ReqTy, Key);
2352 }
2353
2354 Constant *ConstantExpr::getGetElementPtr(Constant *C, Value* const *Idxs,
2355                                          unsigned NumIdx) {
2356   // Get the result type of the getelementptr!
2357   const Type *Ty =
2358     GetElementPtrInst::getIndexedType(C->getType(), Idxs, Idxs+NumIdx);
2359   assert(Ty && "GEP indices invalid!");
2360   unsigned As = cast<PointerType>(C->getType())->getAddressSpace();
2361   return getGetElementPtrTy(PointerType::get(Ty, As), C, Idxs, NumIdx);
2362 }
2363
2364 Constant *ConstantExpr::getGetElementPtr(Constant *C, Constant* const *Idxs,
2365                                          unsigned NumIdx) {
2366   return getGetElementPtr(C, (Value* const *)Idxs, NumIdx);
2367 }
2368
2369
2370 Constant *
2371 ConstantExpr::getICmp(unsigned short pred, Constant* LHS, Constant* RHS) {
2372   assert(LHS->getType() == RHS->getType());
2373   assert(pred >= ICmpInst::FIRST_ICMP_PREDICATE &&
2374          pred <= ICmpInst::LAST_ICMP_PREDICATE && "Invalid ICmp Predicate");
2375
2376   if (Constant *FC = ConstantFoldCompareInstruction(
2377                                              getGlobalContext(),pred, LHS, RHS))
2378     return FC;          // Fold a few common cases...
2379
2380   // Look up the constant in the table first to ensure uniqueness
2381   std::vector<Constant*> ArgVec;
2382   ArgVec.push_back(LHS);
2383   ArgVec.push_back(RHS);
2384   // Get the key type with both the opcode and predicate
2385   const ExprMapKeyType Key(Instruction::ICmp, ArgVec, pred);
2386
2387   // Implicitly locked.
2388   return ExprConstants->getOrCreate(Type::Int1Ty, Key);
2389 }
2390
2391 Constant *
2392 ConstantExpr::getFCmp(unsigned short pred, Constant* LHS, Constant* RHS) {
2393   assert(LHS->getType() == RHS->getType());
2394   assert(pred <= FCmpInst::LAST_FCMP_PREDICATE && "Invalid FCmp Predicate");
2395
2396   if (Constant *FC = ConstantFoldCompareInstruction(
2397                                             getGlobalContext(), pred, LHS, RHS))
2398     return FC;          // Fold a few common cases...
2399
2400   // Look up the constant in the table first to ensure uniqueness
2401   std::vector<Constant*> ArgVec;
2402   ArgVec.push_back(LHS);
2403   ArgVec.push_back(RHS);
2404   // Get the key type with both the opcode and predicate
2405   const ExprMapKeyType Key(Instruction::FCmp, ArgVec, pred);
2406
2407   // Implicitly locked.
2408   return ExprConstants->getOrCreate(Type::Int1Ty, Key);
2409 }
2410
2411 Constant *ConstantExpr::getExtractElementTy(const Type *ReqTy, Constant *Val,
2412                                             Constant *Idx) {
2413   if (Constant *FC = ConstantFoldExtractElementInstruction(
2414                                                   getGlobalContext(), Val, Idx))
2415     return FC;          // Fold a few common cases...
2416   // Look up the constant in the table first to ensure uniqueness
2417   std::vector<Constant*> ArgVec(1, Val);
2418   ArgVec.push_back(Idx);
2419   const ExprMapKeyType Key(Instruction::ExtractElement,ArgVec);
2420
2421   // Implicitly locked.
2422   return ExprConstants->getOrCreate(ReqTy, Key);
2423 }
2424
2425 Constant *ConstantExpr::getExtractElement(Constant *Val, Constant *Idx) {
2426   assert(isa<VectorType>(Val->getType()) &&
2427          "Tried to create extractelement operation on non-vector type!");
2428   assert(Idx->getType() == Type::Int32Ty &&
2429          "Extractelement index must be i32 type!");
2430   return getExtractElementTy(cast<VectorType>(Val->getType())->getElementType(),
2431                              Val, Idx);
2432 }
2433
2434 Constant *ConstantExpr::getInsertElementTy(const Type *ReqTy, Constant *Val,
2435                                            Constant *Elt, Constant *Idx) {
2436   if (Constant *FC = ConstantFoldInsertElementInstruction(
2437                                             getGlobalContext(), Val, Elt, Idx))
2438     return FC;          // Fold a few common cases...
2439   // Look up the constant in the table first to ensure uniqueness
2440   std::vector<Constant*> ArgVec(1, Val);
2441   ArgVec.push_back(Elt);
2442   ArgVec.push_back(Idx);
2443   const ExprMapKeyType Key(Instruction::InsertElement,ArgVec);
2444
2445   // Implicitly locked.
2446   return ExprConstants->getOrCreate(ReqTy, Key);
2447 }
2448
2449 Constant *ConstantExpr::getInsertElement(Constant *Val, Constant *Elt,
2450                                          Constant *Idx) {
2451   assert(isa<VectorType>(Val->getType()) &&
2452          "Tried to create insertelement operation on non-vector type!");
2453   assert(Elt->getType() == cast<VectorType>(Val->getType())->getElementType()
2454          && "Insertelement types must match!");
2455   assert(Idx->getType() == Type::Int32Ty &&
2456          "Insertelement index must be i32 type!");
2457   return getInsertElementTy(Val->getType(), Val, Elt, Idx);
2458 }
2459
2460 Constant *ConstantExpr::getShuffleVectorTy(const Type *ReqTy, Constant *V1,
2461                                            Constant *V2, Constant *Mask) {
2462   if (Constant *FC = ConstantFoldShuffleVectorInstruction(
2463                                               getGlobalContext(), V1, V2, Mask))
2464     return FC;          // Fold a few common cases...
2465   // Look up the constant in the table first to ensure uniqueness
2466   std::vector<Constant*> ArgVec(1, V1);
2467   ArgVec.push_back(V2);
2468   ArgVec.push_back(Mask);
2469   const ExprMapKeyType Key(Instruction::ShuffleVector,ArgVec);
2470
2471   // Implicitly locked.
2472   return ExprConstants->getOrCreate(ReqTy, Key);
2473 }
2474
2475 Constant *ConstantExpr::getShuffleVector(Constant *V1, Constant *V2,
2476                                          Constant *Mask) {
2477   assert(ShuffleVectorInst::isValidOperands(V1, V2, Mask) &&
2478          "Invalid shuffle vector constant expr operands!");
2479
2480   unsigned NElts = cast<VectorType>(Mask->getType())->getNumElements();
2481   const Type *EltTy = cast<VectorType>(V1->getType())->getElementType();
2482   const Type *ShufTy = VectorType::get(EltTy, NElts);
2483   return getShuffleVectorTy(ShufTy, V1, V2, Mask);
2484 }
2485
2486 Constant *ConstantExpr::getInsertValueTy(const Type *ReqTy, Constant *Agg,
2487                                          Constant *Val,
2488                                         const unsigned *Idxs, unsigned NumIdx) {
2489   assert(ExtractValueInst::getIndexedType(Agg->getType(), Idxs,
2490                                           Idxs+NumIdx) == Val->getType() &&
2491          "insertvalue indices invalid!");
2492   assert(Agg->getType() == ReqTy &&
2493          "insertvalue type invalid!");
2494   assert(Agg->getType()->isFirstClassType() &&
2495          "Non-first-class type for constant InsertValue expression");
2496   Constant *FC = ConstantFoldInsertValueInstruction(
2497                                     getGlobalContext(), Agg, Val, Idxs, NumIdx);
2498   assert(FC && "InsertValue constant expr couldn't be folded!");
2499   return FC;
2500 }
2501
2502 Constant *ConstantExpr::getInsertValue(Constant *Agg, Constant *Val,
2503                                      const unsigned *IdxList, unsigned NumIdx) {
2504   assert(Agg->getType()->isFirstClassType() &&
2505          "Tried to create insertelement operation on non-first-class type!");
2506
2507   const Type *ReqTy = Agg->getType();
2508 #ifndef NDEBUG
2509   const Type *ValTy =
2510     ExtractValueInst::getIndexedType(Agg->getType(), IdxList, IdxList+NumIdx);
2511 #endif
2512   assert(ValTy == Val->getType() && "insertvalue indices invalid!");
2513   return getInsertValueTy(ReqTy, Agg, Val, IdxList, NumIdx);
2514 }
2515
2516 Constant *ConstantExpr::getExtractValueTy(const Type *ReqTy, Constant *Agg,
2517                                         const unsigned *Idxs, unsigned NumIdx) {
2518   assert(ExtractValueInst::getIndexedType(Agg->getType(), Idxs,
2519                                           Idxs+NumIdx) == ReqTy &&
2520          "extractvalue indices invalid!");
2521   assert(Agg->getType()->isFirstClassType() &&
2522          "Non-first-class type for constant extractvalue expression");
2523   Constant *FC = ConstantFoldExtractValueInstruction(
2524                                          getGlobalContext(), Agg, Idxs, NumIdx);
2525   assert(FC && "ExtractValue constant expr couldn't be folded!");
2526   return FC;
2527 }
2528
2529 Constant *ConstantExpr::getExtractValue(Constant *Agg,
2530                                      const unsigned *IdxList, unsigned NumIdx) {
2531   assert(Agg->getType()->isFirstClassType() &&
2532          "Tried to create extractelement operation on non-first-class type!");
2533
2534   const Type *ReqTy =
2535     ExtractValueInst::getIndexedType(Agg->getType(), IdxList, IdxList+NumIdx);
2536   assert(ReqTy && "extractvalue indices invalid!");
2537   return getExtractValueTy(ReqTy, Agg, IdxList, NumIdx);
2538 }
2539
2540 // destroyConstant - Remove the constant from the constant table...
2541 //
2542 void ConstantExpr::destroyConstant() {
2543   // Implicitly locked.
2544   ExprConstants->remove(this);
2545   destroyConstantImpl();
2546 }
2547
2548 const char *ConstantExpr::getOpcodeName() const {
2549   return Instruction::getOpcodeName(getOpcode());
2550 }
2551
2552 //===----------------------------------------------------------------------===//
2553 //                replaceUsesOfWithOnConstant implementations
2554
2555 /// replaceUsesOfWithOnConstant - Update this constant array to change uses of
2556 /// 'From' to be uses of 'To'.  This must update the uniquing data structures
2557 /// etc.
2558 ///
2559 /// Note that we intentionally replace all uses of From with To here.  Consider
2560 /// a large array that uses 'From' 1000 times.  By handling this case all here,
2561 /// ConstantArray::replaceUsesOfWithOnConstant is only invoked once, and that
2562 /// single invocation handles all 1000 uses.  Handling them one at a time would
2563 /// work, but would be really slow because it would have to unique each updated
2564 /// array instance.
2565 void ConstantArray::replaceUsesOfWithOnConstant(Value *From, Value *To,
2566                                                 Use *U) {
2567   assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
2568   Constant *ToC = cast<Constant>(To);
2569
2570   std::pair<ArrayConstantsTy::MapKey, Constant*> Lookup;
2571   Lookup.first.first = getType();
2572   Lookup.second = this;
2573
2574   std::vector<Constant*> &Values = Lookup.first.second;
2575   Values.reserve(getNumOperands());  // Build replacement array.
2576
2577   // Fill values with the modified operands of the constant array.  Also,
2578   // compute whether this turns into an all-zeros array.
2579   bool isAllZeros = false;
2580   unsigned NumUpdated = 0;
2581   if (!ToC->isNullValue()) {
2582     for (Use *O = OperandList, *E = OperandList+getNumOperands(); O != E; ++O) {
2583       Constant *Val = cast<Constant>(O->get());
2584       if (Val == From) {
2585         Val = ToC;
2586         ++NumUpdated;
2587       }
2588       Values.push_back(Val);
2589     }
2590   } else {
2591     isAllZeros = true;
2592     for (Use *O = OperandList, *E = OperandList+getNumOperands(); O != E; ++O) {
2593       Constant *Val = cast<Constant>(O->get());
2594       if (Val == From) {
2595         Val = ToC;
2596         ++NumUpdated;
2597       }
2598       Values.push_back(Val);
2599       if (isAllZeros) isAllZeros = Val->isNullValue();
2600     }
2601   }
2602
2603   Constant *Replacement = 0;
2604   if (isAllZeros) {
2605     Replacement = ConstantAggregateZero::get(getType());
2606   } else {
2607     // Check to see if we have this array type already.
2608     sys::SmartScopedWriter<true> Writer(*ConstantsLock);
2609     bool Exists;
2610     ArrayConstantsTy::MapTy::iterator I =
2611       ArrayConstants->InsertOrGetItem(Lookup, Exists);
2612
2613     if (Exists) {
2614       Replacement = I->second;
2615     } else {
2616       // Okay, the new shape doesn't exist in the system yet.  Instead of
2617       // creating a new constant array, inserting it, replaceallusesof'ing the
2618       // old with the new, then deleting the old... just update the current one
2619       // in place!
2620       ArrayConstants->MoveConstantToNewSlot(this, I);
2621
2622       // Update to the new value.  Optimize for the case when we have a single
2623       // operand that we're changing, but handle bulk updates efficiently.
2624       if (NumUpdated == 1) {
2625         unsigned OperandToUpdate = U-OperandList;
2626         assert(getOperand(OperandToUpdate) == From &&
2627                "ReplaceAllUsesWith broken!");
2628         setOperand(OperandToUpdate, ToC);
2629       } else {
2630         for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
2631           if (getOperand(i) == From)
2632             setOperand(i, ToC);
2633       }
2634       return;
2635     }
2636   }
2637
2638   // Otherwise, I do need to replace this with an existing value.
2639   assert(Replacement != this && "I didn't contain From!");
2640
2641   // Everyone using this now uses the replacement.
2642   uncheckedReplaceAllUsesWith(Replacement);
2643
2644   // Delete the old constant!
2645   destroyConstant();
2646 }
2647
2648 void ConstantStruct::replaceUsesOfWithOnConstant(Value *From, Value *To,
2649                                                  Use *U) {
2650   assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
2651   Constant *ToC = cast<Constant>(To);
2652
2653   unsigned OperandToUpdate = U-OperandList;
2654   assert(getOperand(OperandToUpdate) == From && "ReplaceAllUsesWith broken!");
2655
2656   std::pair<StructConstantsTy::MapKey, Constant*> Lookup;
2657   Lookup.first.first = getType();
2658   Lookup.second = this;
2659   std::vector<Constant*> &Values = Lookup.first.second;
2660   Values.reserve(getNumOperands());  // Build replacement struct.
2661
2662
2663   // Fill values with the modified operands of the constant struct.  Also,
2664   // compute whether this turns into an all-zeros struct.
2665   bool isAllZeros = false;
2666   if (!ToC->isNullValue()) {
2667     for (Use *O = OperandList, *E = OperandList+getNumOperands(); O != E; ++O)
2668       Values.push_back(cast<Constant>(O->get()));
2669   } else {
2670     isAllZeros = true;
2671     for (Use *O = OperandList, *E = OperandList+getNumOperands(); O != E; ++O) {
2672       Constant *Val = cast<Constant>(O->get());
2673       Values.push_back(Val);
2674       if (isAllZeros) isAllZeros = Val->isNullValue();
2675     }
2676   }
2677   Values[OperandToUpdate] = ToC;
2678
2679   Constant *Replacement = 0;
2680   if (isAllZeros) {
2681     Replacement = ConstantAggregateZero::get(getType());
2682   } else {
2683     // Check to see if we have this array type already.
2684     sys::SmartScopedWriter<true> Writer(*ConstantsLock);
2685     bool Exists;
2686     StructConstantsTy::MapTy::iterator I =
2687       StructConstants->InsertOrGetItem(Lookup, Exists);
2688
2689     if (Exists) {
2690       Replacement = I->second;
2691     } else {
2692       // Okay, the new shape doesn't exist in the system yet.  Instead of
2693       // creating a new constant struct, inserting it, replaceallusesof'ing the
2694       // old with the new, then deleting the old... just update the current one
2695       // in place!
2696       StructConstants->MoveConstantToNewSlot(this, I);
2697
2698       // Update to the new value.
2699       setOperand(OperandToUpdate, ToC);
2700       return;
2701     }
2702   }
2703
2704   assert(Replacement != this && "I didn't contain From!");
2705
2706   // Everyone using this now uses the replacement.
2707   uncheckedReplaceAllUsesWith(Replacement);
2708
2709   // Delete the old constant!
2710   destroyConstant();
2711 }
2712
2713 void ConstantVector::replaceUsesOfWithOnConstant(Value *From, Value *To,
2714                                                  Use *U) {
2715   assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
2716
2717   std::vector<Constant*> Values;
2718   Values.reserve(getNumOperands());  // Build replacement array...
2719   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
2720     Constant *Val = getOperand(i);
2721     if (Val == From) Val = cast<Constant>(To);
2722     Values.push_back(Val);
2723   }
2724
2725   Constant *Replacement = ConstantVector::get(getType(), Values);
2726   assert(Replacement != this && "I didn't contain From!");
2727
2728   // Everyone using this now uses the replacement.
2729   uncheckedReplaceAllUsesWith(Replacement);
2730
2731   // Delete the old constant!
2732   destroyConstant();
2733 }
2734
2735 void ConstantExpr::replaceUsesOfWithOnConstant(Value *From, Value *ToV,
2736                                                Use *U) {
2737   assert(isa<Constant>(ToV) && "Cannot make Constant refer to non-constant!");
2738   Constant *To = cast<Constant>(ToV);
2739
2740   Constant *Replacement = 0;
2741   if (getOpcode() == Instruction::GetElementPtr) {
2742     SmallVector<Constant*, 8> Indices;
2743     Constant *Pointer = getOperand(0);
2744     Indices.reserve(getNumOperands()-1);
2745     if (Pointer == From) Pointer = To;
2746
2747     for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
2748       Constant *Val = getOperand(i);
2749       if (Val == From) Val = To;
2750       Indices.push_back(Val);
2751     }
2752     Replacement = ConstantExpr::getGetElementPtr(Pointer,
2753                                                  &Indices[0], Indices.size());
2754   } else if (getOpcode() == Instruction::ExtractValue) {
2755     Constant *Agg = getOperand(0);
2756     if (Agg == From) Agg = To;
2757
2758     const SmallVector<unsigned, 4> &Indices = getIndices();
2759     Replacement = ConstantExpr::getExtractValue(Agg,
2760                                                 &Indices[0], Indices.size());
2761   } else if (getOpcode() == Instruction::InsertValue) {
2762     Constant *Agg = getOperand(0);
2763     Constant *Val = getOperand(1);
2764     if (Agg == From) Agg = To;
2765     if (Val == From) Val = To;
2766
2767     const SmallVector<unsigned, 4> &Indices = getIndices();
2768     Replacement = ConstantExpr::getInsertValue(Agg, Val,
2769                                                &Indices[0], Indices.size());
2770   } else if (isCast()) {
2771     assert(getOperand(0) == From && "Cast only has one use!");
2772     Replacement = ConstantExpr::getCast(getOpcode(), To, getType());
2773   } else if (getOpcode() == Instruction::Select) {
2774     Constant *C1 = getOperand(0);
2775     Constant *C2 = getOperand(1);
2776     Constant *C3 = getOperand(2);
2777     if (C1 == From) C1 = To;
2778     if (C2 == From) C2 = To;
2779     if (C3 == From) C3 = To;
2780     Replacement = ConstantExpr::getSelect(C1, C2, C3);
2781   } else if (getOpcode() == Instruction::ExtractElement) {
2782     Constant *C1 = getOperand(0);
2783     Constant *C2 = getOperand(1);
2784     if (C1 == From) C1 = To;
2785     if (C2 == From) C2 = To;
2786     Replacement = ConstantExpr::getExtractElement(C1, C2);
2787   } else if (getOpcode() == Instruction::InsertElement) {
2788     Constant *C1 = getOperand(0);
2789     Constant *C2 = getOperand(1);
2790     Constant *C3 = getOperand(1);
2791     if (C1 == From) C1 = To;
2792     if (C2 == From) C2 = To;
2793     if (C3 == From) C3 = To;
2794     Replacement = ConstantExpr::getInsertElement(C1, C2, C3);
2795   } else if (getOpcode() == Instruction::ShuffleVector) {
2796     Constant *C1 = getOperand(0);
2797     Constant *C2 = getOperand(1);
2798     Constant *C3 = getOperand(2);
2799     if (C1 == From) C1 = To;
2800     if (C2 == From) C2 = To;
2801     if (C3 == From) C3 = To;
2802     Replacement = ConstantExpr::getShuffleVector(C1, C2, C3);
2803   } else if (isCompare()) {
2804     Constant *C1 = getOperand(0);
2805     Constant *C2 = getOperand(1);
2806     if (C1 == From) C1 = To;
2807     if (C2 == From) C2 = To;
2808     if (getOpcode() == Instruction::ICmp)
2809       Replacement = ConstantExpr::getICmp(getPredicate(), C1, C2);
2810     else {
2811       assert(getOpcode() == Instruction::FCmp);
2812       Replacement = ConstantExpr::getFCmp(getPredicate(), C1, C2);
2813     }
2814   } else if (getNumOperands() == 2) {
2815     Constant *C1 = getOperand(0);
2816     Constant *C2 = getOperand(1);
2817     if (C1 == From) C1 = To;
2818     if (C2 == From) C2 = To;
2819     Replacement = ConstantExpr::get(getOpcode(), C1, C2);
2820   } else {
2821     LLVM_UNREACHABLE("Unknown ConstantExpr type!");
2822     return;
2823   }
2824
2825   assert(Replacement != this && "I didn't contain From!");
2826
2827   // Everyone using this now uses the replacement.
2828   uncheckedReplaceAllUsesWith(Replacement);
2829
2830   // Delete the old constant!
2831   destroyConstant();
2832 }
2833
2834 void MDNode::replaceElement(Value *From, Value *To) {
2835   SmallVector<Value*, 4> Values;
2836   Values.reserve(getNumElements());  // Build replacement array...
2837   for (unsigned i = 0, e = getNumElements(); i != e; ++i) {
2838     Value *Val = getElement(i);
2839     if (Val == From) Val = To;
2840     Values.push_back(Val);
2841   }
2842
2843   MDNode *Replacement = MDNode::get(&Values[0], Values.size());
2844   assert(Replacement != this && "I didn't contain From!");
2845
2846   uncheckedReplaceAllUsesWith(Replacement);
2847
2848   destroyConstant();
2849 }