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