lib/VMCore/Constants.cpp

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