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