lib/VMCore/Constants.cpp

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