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