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 "LLVMContextImpl.h"
  16 #include "ConstantFold.h"
  17 #include "llvm/DerivedTypes.h"
  18 #include "llvm/GlobalValue.h"
  19 #include "llvm/Instructions.h"
  20 #include "llvm/Module.h"
  21 #include "llvm/Operator.h"
  22 #include "llvm/ADT/FoldingSet.h"
  23 #include "llvm/ADT/StringExtras.h"
  24 #include "llvm/ADT/StringMap.h"
  25 #include "llvm/Support/Compiler.h"
  26 #include "llvm/Support/Debug.h"
  27 #include "llvm/Support/ErrorHandling.h"
  28 #include "llvm/Support/ManagedStatic.h"
  29 #include "llvm/Support/MathExtras.h"
  30 #include "llvm/Support/raw_ostream.h"
  31 #include "llvm/Support/GetElementPtrTypeIterator.h"
  32 #include "llvm/ADT/DenseMap.h"
  33 #include "llvm/ADT/SmallVector.h"
  34 #include "llvm/ADT/STLExtras.h"
  35 #include <algorithm>
  36 #include <cstdarg>
  37 using namespace llvm;
  38
  39 //===----------------------------------------------------------------------===//
  40 //                              Constant Class
  41 //===----------------------------------------------------------------------===//
  42
  43 void Constant::anchor() { }
  44
  45 bool Constant::isNegativeZeroValue() const {
  46   // Floating point values have an explicit -0.0 value.
  47   if (const ConstantFP *CFP = dyn_cast<ConstantFP>(this))
  48     return CFP->isZero() && CFP->isNegative();
  49
  50   // Otherwise, just use +0.0.
  51   return isNullValue();
  52 }
  53
  54 bool Constant::isNullValue() const {
  55   // 0 is null.
  56   if (const ConstantInt *CI = dyn_cast<ConstantInt>(this))
  57     return CI->isZero();
  58
  59   // +0.0 is null.
  60   if (const ConstantFP *CFP = dyn_cast<ConstantFP>(this))
  61     return CFP->isZero() && !CFP->isNegative();
  62
  63   // constant zero is zero for aggregates and cpnull is null for pointers.
  64   return isa<ConstantAggregateZero>(this) || isa<ConstantPointerNull>(this);
  65 }
  66
  67 bool Constant::isAllOnesValue() const {
  68   // Check for -1 integers
  69   if (const ConstantInt *CI = dyn_cast<ConstantInt>(this))
  70     return CI->isMinusOne();
  71
  72   // Check for FP which are bitcasted from -1 integers
  73   if (const ConstantFP *CFP = dyn_cast<ConstantFP>(this))
  74     return CFP->getValueAPF().bitcastToAPInt().isAllOnesValue();
  75
  76   // Check for constant vectors which are splats of -1 values.
  77   if (const ConstantVector *CV = dyn_cast<ConstantVector>(this))
  78     if (Constant *Splat = CV->getSplatValue())
  79       return Splat->isAllOnesValue();
  80
  81   return false;
  82 }
  83
  84 // Constructor to create a '0' constant of arbitrary type...
  85 Constant *Constant::getNullValue(Type *Ty) {
  86   switch (Ty->getTypeID()) {
  87   case Type::IntegerTyID:
  88     return ConstantInt::get(Ty, 0);
  89   case Type::HalfTyID:
  90     return ConstantFP::get(Ty->getContext(),
  91                            APFloat::getZero(APFloat::IEEEhalf));
  92   case Type::FloatTyID:
  93     return ConstantFP::get(Ty->getContext(),
  94                            APFloat::getZero(APFloat::IEEEsingle));
  95   case Type::DoubleTyID:
  96     return ConstantFP::get(Ty->getContext(),
  97                            APFloat::getZero(APFloat::IEEEdouble));
  98   case Type::X86_FP80TyID:
  99     return ConstantFP::get(Ty->getContext(),
 100                            APFloat::getZero(APFloat::x87DoubleExtended));
 101   case Type::FP128TyID:
 102     return ConstantFP::get(Ty->getContext(),
 103                            APFloat::getZero(APFloat::IEEEquad));
 104   case Type::PPC_FP128TyID:
 105     return ConstantFP::get(Ty->getContext(),
 106                            APFloat(APInt::getNullValue(128)));
 107   case Type::PointerTyID:
 108     return ConstantPointerNull::get(cast<PointerType>(Ty));
 109   case Type::StructTyID:
 110   case Type::ArrayTyID:
 111   case Type::VectorTyID:
 112     return ConstantAggregateZero::get(Ty);
 113   default:
 114     // Function, Label, or Opaque type?
 115     assert(0 && "Cannot create a null constant of that type!");
 116     return 0;
 117   }
 118 }
 119
 120 Constant *Constant::getIntegerValue(Type *Ty, const APInt &V) {
 121   Type *ScalarTy = Ty->getScalarType();
 122
 123   // Create the base integer constant.
 124   Constant *C = ConstantInt::get(Ty->getContext(), V);
 125
 126   // Convert an integer to a pointer, if necessary.
 127   if (PointerType *PTy = dyn_cast<PointerType>(ScalarTy))
 128     C = ConstantExpr::getIntToPtr(C, PTy);
 129
 130   // Broadcast a scalar to a vector, if necessary.
 131   if (VectorType *VTy = dyn_cast<VectorType>(Ty))
 132     C = ConstantVector::get(std::vector<Constant *>(VTy->getNumElements(), C));
 133
 134   return C;
 135 }
 136
 137 Constant *Constant::getAllOnesValue(Type *Ty) {
 138   if (IntegerType *ITy = dyn_cast<IntegerType>(Ty))
 139     return ConstantInt::get(Ty->getContext(),
 140                             APInt::getAllOnesValue(ITy->getBitWidth()));
 141
 142   if (Ty->isFloatingPointTy()) {
 143     APFloat FL = APFloat::getAllOnesValue(Ty->getPrimitiveSizeInBits(),
 144                                           !Ty->isPPC_FP128Ty());
 145     return ConstantFP::get(Ty->getContext(), FL);
 146   }
 147
 148   SmallVector<Constant*, 16> Elts;
 149   VectorType *VTy = cast<VectorType>(Ty);
 150   Elts.resize(VTy->getNumElements(), getAllOnesValue(VTy->getElementType()));
 151   assert(Elts[0] && "Invalid AllOnes value!");
 152   return cast<ConstantVector>(ConstantVector::get(Elts));
 153 }
 154
 155 void Constant::destroyConstantImpl() {
 156   // When a Constant is destroyed, there may be lingering
 157   // references to the constant by other constants in the constant pool.  These
 158   // constants are implicitly dependent on the module that is being deleted,
 159   // but they don't know that.  Because we only find out when the CPV is
 160   // deleted, we must now notify all of our users (that should only be
 161   // Constants) that they are, in fact, invalid now and should be deleted.
 162   //
 163   while (!use_empty()) {
 164     Value *V = use_back();
 165 #ifndef NDEBUG      // Only in -g mode...
 166     if (!isa<Constant>(V)) {
 167       dbgs() << "While deleting: " << *this
 168              << "\n\nUse still stuck around after Def is destroyed: "
 169              << *V << "\n\n";
 170     }
 171 #endif
 172     assert(isa<Constant>(V) && "References remain to Constant being destroyed");
 173     Constant *CV = cast<Constant>(V);
 174     CV->destroyConstant();
 175
 176     // The constant should remove itself from our use list...
 177     assert((use_empty() || use_back() != V) && "Constant not removed!");
 178   }
 179
 180   // Value has no outstanding references it is safe to delete it now...
 181   delete this;
 182 }
 183
 184 /// canTrap - Return true if evaluation of this constant could trap.  This is
 185 /// true for things like constant expressions that could divide by zero.
 186 bool Constant::canTrap() const {
 187   assert(getType()->isFirstClassType() && "Cannot evaluate aggregate vals!");
 188   // The only thing that could possibly trap are constant exprs.
 189   const ConstantExpr *CE = dyn_cast<ConstantExpr>(this);
 190   if (!CE) return false;
 191
 192   // ConstantExpr traps if any operands can trap.
 193   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
 194     if (CE->getOperand(i)->canTrap())
 195       return true;
 196
 197   // Otherwise, only specific operations can trap.
 198   switch (CE->getOpcode()) {
 199   default:
 200     return false;
 201   case Instruction::UDiv:
 202   case Instruction::SDiv:
 203   case Instruction::FDiv:
 204   case Instruction::URem:
 205   case Instruction::SRem:
 206   case Instruction::FRem:
 207     // Div and rem can trap if the RHS is not known to be non-zero.
 208     if (!isa<ConstantInt>(CE->getOperand(1)) ||CE->getOperand(1)->isNullValue())
 209       return true;
 210     return false;
 211   }
 212 }
 213
 214 /// isConstantUsed - Return true if the constant has users other than constant
 215 /// exprs and other dangling things.
 216 bool Constant::isConstantUsed() const {
 217   for (const_use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
 218     const Constant *UC = dyn_cast<Constant>(*UI);
 219     if (UC == 0 || isa<GlobalValue>(UC))
 220       return true;
 221
 222     if (UC->isConstantUsed())
 223       return true;
 224   }
 225   return false;
 226 }
 227
 228
 229
 230 /// getRelocationInfo - This method classifies the entry according to
 231 /// whether or not it may generate a relocation entry.  This must be
 232 /// conservative, so if it might codegen to a relocatable entry, it should say
 233 /// so.  The return values are:
 234 ///
 235 ///  NoRelocation: This constant pool entry is guaranteed to never have a
 236 ///     relocation applied to it (because it holds a simple constant like
 237 ///     '4').
 238 ///  LocalRelocation: This entry has relocations, but the entries are
 239 ///     guaranteed to be resolvable by the static linker, so the dynamic
 240 ///     linker will never see them.
 241 ///  GlobalRelocations: This entry may have arbitrary relocations.
 242 ///
 243 /// FIXME: This really should not be in VMCore.
 244 Constant::PossibleRelocationsTy Constant::getRelocationInfo() const {
 245   if (const GlobalValue *GV = dyn_cast<GlobalValue>(this)) {
 246     if (GV->hasLocalLinkage() || GV->hasHiddenVisibility())
 247       return LocalRelocation;  // Local to this file/library.
 248     return GlobalRelocations;    // Global reference.
 249   }
 250
 251   if (const BlockAddress *BA = dyn_cast<BlockAddress>(this))
 252     return BA->getFunction()->getRelocationInfo();
 253
 254   // While raw uses of blockaddress need to be relocated, differences between
 255   // two of them don't when they are for labels in the same function.  This is a
 256   // common idiom when creating a table for the indirect goto extension, so we
 257   // handle it efficiently here.
 258   if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(this))
 259     if (CE->getOpcode() == Instruction::Sub) {
 260       ConstantExpr *LHS = dyn_cast<ConstantExpr>(CE->getOperand(0));
 261       ConstantExpr *RHS = dyn_cast<ConstantExpr>(CE->getOperand(1));
 262       if (LHS && RHS &&
 263           LHS->getOpcode() == Instruction::PtrToInt &&
 264           RHS->getOpcode() == Instruction::PtrToInt &&
 265           isa<BlockAddress>(LHS->getOperand(0)) &&
 266           isa<BlockAddress>(RHS->getOperand(0)) &&
 267           cast<BlockAddress>(LHS->getOperand(0))->getFunction() ==
 268             cast<BlockAddress>(RHS->getOperand(0))->getFunction())
 269         return NoRelocation;
 270     }
 271
 272   PossibleRelocationsTy Result = NoRelocation;
 273   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
 274     Result = std::max(Result,
 275                       cast<Constant>(getOperand(i))->getRelocationInfo());
 276
 277   return Result;
 278 }
 279
 280
 281 /// getVectorElements - This method, which is only valid on constant of vector
 282 /// type, returns the elements of the vector in the specified smallvector.
 283 /// This handles breaking down a vector undef into undef elements, etc.  For
 284 /// constant exprs and other cases we can't handle, we return an empty vector.
 285 void Constant::getVectorElements(SmallVectorImpl<Constant*> &Elts) const {
 286   assert(getType()->isVectorTy() && "Not a vector constant!");
 287
 288   if (const ConstantVector *CV = dyn_cast<ConstantVector>(this)) {
 289     for (unsigned i = 0, e = CV->getNumOperands(); i != e; ++i)
 290       Elts.push_back(CV->getOperand(i));
 291     return;
 292   }
 293
 294   VectorType *VT = cast<VectorType>(getType());
 295   if (isa<ConstantAggregateZero>(this)) {
 296     Elts.assign(VT->getNumElements(),
 297                 Constant::getNullValue(VT->getElementType()));
 298     return;
 299   }
 300
 301   if (isa<UndefValue>(this)) {
 302     Elts.assign(VT->getNumElements(), UndefValue::get(VT->getElementType()));
 303     return;
 304   }
 305
 306   // Unknown type, must be constant expr etc.
 307 }
 308
 309
 310 /// removeDeadUsersOfConstant - If the specified constantexpr is dead, remove
 311 /// it.  This involves recursively eliminating any dead users of the
 312 /// constantexpr.
 313 static bool removeDeadUsersOfConstant(const Constant *C) {
 314   if (isa<GlobalValue>(C)) return false; // Cannot remove this
 315
 316   while (!C->use_empty()) {
 317     const Constant *User = dyn_cast<Constant>(C->use_back());
 318     if (!User) return false; // Non-constant usage;
 319     if (!removeDeadUsersOfConstant(User))
 320       return false; // Constant wasn't dead
 321   }
 322
 323   const_cast<Constant*>(C)->destroyConstant();
 324   return true;
 325 }
 326
 327
 328 /// removeDeadConstantUsers - If there are any dead constant users dangling
 329 /// off of this constant, remove them.  This method is useful for clients
 330 /// that want to check to see if a global is unused, but don't want to deal
 331 /// with potentially dead constants hanging off of the globals.
 332 void Constant::removeDeadConstantUsers() const {
 333   Value::const_use_iterator I = use_begin(), E = use_end();
 334   Value::const_use_iterator LastNonDeadUser = E;
 335   while (I != E) {
 336     const Constant *User = dyn_cast<Constant>(*I);
 337     if (User == 0) {
 338       LastNonDeadUser = I;
 339       ++I;
 340       continue;
 341     }
 342
 343     if (!removeDeadUsersOfConstant(User)) {
 344       // If the constant wasn't dead, remember that this was the last live use
 345       // and move on to the next constant.
 346       LastNonDeadUser = I;
 347       ++I;
 348       continue;
 349     }
 350
 351     // If the constant was dead, then the iterator is invalidated.
 352     if (LastNonDeadUser == E) {
 353       I = use_begin();
 354       if (I == E) break;
 355     } else {
 356       I = LastNonDeadUser;
 357       ++I;
 358     }
 359   }
 360 }
 361
 362
 363
 364 //===----------------------------------------------------------------------===//
 365 //                                ConstantInt
 366 //===----------------------------------------------------------------------===//
 367
 368 void ConstantInt::anchor() { }
 369
 370 ConstantInt::ConstantInt(IntegerType *Ty, const APInt& V)
 371   : Constant(Ty, ConstantIntVal, 0, 0), Val(V) {
 372   assert(V.getBitWidth() == Ty->getBitWidth() && "Invalid constant for type");
 373 }
 374
 375 ConstantInt *ConstantInt::getTrue(LLVMContext &Context) {
 376   LLVMContextImpl *pImpl = Context.pImpl;
 377   if (!pImpl->TheTrueVal)
 378     pImpl->TheTrueVal = ConstantInt::get(Type::getInt1Ty(Context), 1);
 379   return pImpl->TheTrueVal;
 380 }
 381
 382 ConstantInt *ConstantInt::getFalse(LLVMContext &Context) {
 383   LLVMContextImpl *pImpl = Context.pImpl;
 384   if (!pImpl->TheFalseVal)
 385     pImpl->TheFalseVal = ConstantInt::get(Type::getInt1Ty(Context), 0);
 386   return pImpl->TheFalseVal;
 387 }
 388
 389 Constant *ConstantInt::getTrue(Type *Ty) {
 390   VectorType *VTy = dyn_cast<VectorType>(Ty);
 391   if (!VTy) {
 392     assert(Ty->isIntegerTy(1) && "True must be i1 or vector of i1.");
 393     return ConstantInt::getTrue(Ty->getContext());
 394   }
 395   assert(VTy->getElementType()->isIntegerTy(1) &&
 396          "True must be vector of i1 or i1.");
 397   SmallVector<Constant*, 16> Splat(VTy->getNumElements(),
 398                                    ConstantInt::getTrue(Ty->getContext()));
 399   return ConstantVector::get(Splat);
 400 }
 401
 402 Constant *ConstantInt::getFalse(Type *Ty) {
 403   VectorType *VTy = dyn_cast<VectorType>(Ty);
 404   if (!VTy) {
 405     assert(Ty->isIntegerTy(1) && "False must be i1 or vector of i1.");
 406     return ConstantInt::getFalse(Ty->getContext());
 407   }
 408   assert(VTy->getElementType()->isIntegerTy(1) &&
 409          "False must be vector of i1 or i1.");
 410   SmallVector<Constant*, 16> Splat(VTy->getNumElements(),
 411                                    ConstantInt::getFalse(Ty->getContext()));
 412   return ConstantVector::get(Splat);
 413 }
 414
 415
 416 // Get a ConstantInt from an APInt. Note that the value stored in the DenseMap
 417 // as the key, is a DenseMapAPIntKeyInfo::KeyTy which has provided the
 418 // operator== and operator!= to ensure that the DenseMap doesn't attempt to
 419 // compare APInt's of different widths, which would violate an APInt class
 420 // invariant which generates an assertion.
 421 ConstantInt *ConstantInt::get(LLVMContext &Context, const APInt &V) {
 422   // Get the corresponding integer type for the bit width of the value.
 423   IntegerType *ITy = IntegerType::get(Context, V.getBitWidth());
 424   // get an existing value or the insertion position
 425   DenseMapAPIntKeyInfo::KeyTy Key(V, ITy);
 426   ConstantInt *&Slot = Context.pImpl->IntConstants[Key];
 427   if (!Slot) Slot = new ConstantInt(ITy, V);
 428   return Slot;
 429 }
 430
 431 Constant *ConstantInt::get(Type *Ty, uint64_t V, bool isSigned) {
 432   Constant *C = get(cast<IntegerType>(Ty->getScalarType()), V, isSigned);
 433
 434   // For vectors, broadcast the value.
 435   if (VectorType *VTy = dyn_cast<VectorType>(Ty))
 436     return ConstantVector::get(SmallVector<Constant*,
 437                                            16>(VTy->getNumElements(), C));
 438
 439   return C;
 440 }
 441
 442 ConstantInt* ConstantInt::get(IntegerType* Ty, uint64_t V,
 443                               bool isSigned) {
 444   return get(Ty->getContext(), APInt(Ty->getBitWidth(), V, isSigned));
 445 }
 446
 447 ConstantInt* ConstantInt::getSigned(IntegerType* Ty, int64_t V) {
 448   return get(Ty, V, true);
 449 }
 450
 451 Constant *ConstantInt::getSigned(Type *Ty, int64_t V) {
 452   return get(Ty, V, true);
 453 }
 454
 455 Constant *ConstantInt::get(Type* Ty, const APInt& V) {
 456   ConstantInt *C = get(Ty->getContext(), V);
 457   assert(C->getType() == Ty->getScalarType() &&
 458          "ConstantInt type doesn't match the type implied by its value!");
 459
 460   // For vectors, broadcast the value.
 461   if (VectorType *VTy = dyn_cast<VectorType>(Ty))
 462     return ConstantVector::get(
 463       SmallVector<Constant *, 16>(VTy->getNumElements(), C));
 464
 465   return C;
 466 }
 467
 468 ConstantInt* ConstantInt::get(IntegerType* Ty, StringRef Str,
 469                               uint8_t radix) {
 470   return get(Ty->getContext(), APInt(Ty->getBitWidth(), Str, radix));
 471 }
 472
 473 //===----------------------------------------------------------------------===//
 474 //                                ConstantFP
 475 //===----------------------------------------------------------------------===//
 476
 477 static const fltSemantics *TypeToFloatSemantics(Type *Ty) {
 478   if (Ty->isHalfTy())
 479     return &APFloat::IEEEhalf;
 480   if (Ty->isFloatTy())
 481     return &APFloat::IEEEsingle;
 482   if (Ty->isDoubleTy())
 483     return &APFloat::IEEEdouble;
 484   if (Ty->isX86_FP80Ty())
 485     return &APFloat::x87DoubleExtended;
 486   else if (Ty->isFP128Ty())
 487     return &APFloat::IEEEquad;
 488
 489   assert(Ty->isPPC_FP128Ty() && "Unknown FP format");
 490   return &APFloat::PPCDoubleDouble;
 491 }
 492
 493 void ConstantFP::anchor() { }
 494
 495 /// get() - This returns a constant fp for the specified value in the
 496 /// specified type.  This should only be used for simple constant values like
 497 /// 2.0/1.0 etc, that are known-valid both as double and as the target format.
 498 Constant *ConstantFP::get(Type* Ty, double V) {
 499   LLVMContext &Context = Ty->getContext();
 500
 501   APFloat FV(V);
 502   bool ignored;
 503   FV.convert(*TypeToFloatSemantics(Ty->getScalarType()),
 504              APFloat::rmNearestTiesToEven, &ignored);
 505   Constant *C = get(Context, FV);
 506
 507   // For vectors, broadcast the value.
 508   if (VectorType *VTy = dyn_cast<VectorType>(Ty))
 509     return ConstantVector::get(
 510       SmallVector<Constant *, 16>(VTy->getNumElements(), C));
 511
 512   return C;
 513 }
 514
 515
 516 Constant *ConstantFP::get(Type* Ty, StringRef Str) {
 517   LLVMContext &Context = Ty->getContext();
 518
 519   APFloat FV(*TypeToFloatSemantics(Ty->getScalarType()), Str);
 520   Constant *C = get(Context, FV);
 521
 522   // For vectors, broadcast the value.
 523   if (VectorType *VTy = dyn_cast<VectorType>(Ty))
 524     return ConstantVector::get(
 525       SmallVector<Constant *, 16>(VTy->getNumElements(), C));
 526
 527   return C;
 528 }
 529
 530
 531 ConstantFP* ConstantFP::getNegativeZero(Type* Ty) {
 532   LLVMContext &Context = Ty->getContext();
 533   APFloat apf = cast <ConstantFP>(Constant::getNullValue(Ty))->getValueAPF();
 534   apf.changeSign();
 535   return get(Context, apf);
 536 }
 537
 538
 539 Constant *ConstantFP::getZeroValueForNegation(Type* Ty) {
 540   if (VectorType *PTy = dyn_cast<VectorType>(Ty))
 541     if (PTy->getElementType()->isFloatingPointTy()) {
 542       SmallVector<Constant*, 16> zeros(PTy->getNumElements(),
 543                            getNegativeZero(PTy->getElementType()));
 544       return ConstantVector::get(zeros);
 545     }
 546
 547   if (Ty->isFloatingPointTy())
 548     return getNegativeZero(Ty);
 549
 550   return Constant::getNullValue(Ty);
 551 }
 552
 553
 554 // ConstantFP accessors.
 555 ConstantFP* ConstantFP::get(LLVMContext &Context, const APFloat& V) {
 556   DenseMapAPFloatKeyInfo::KeyTy Key(V);
 557
 558   LLVMContextImpl* pImpl = Context.pImpl;
 559
 560   ConstantFP *&Slot = pImpl->FPConstants[Key];
 561
 562   if (!Slot) {
 563     Type *Ty;
 564     if (&V.getSemantics() == &APFloat::IEEEhalf)
 565       Ty = Type::getHalfTy(Context);
 566     else if (&V.getSemantics() == &APFloat::IEEEsingle)
 567       Ty = Type::getFloatTy(Context);
 568     else if (&V.getSemantics() == &APFloat::IEEEdouble)
 569       Ty = Type::getDoubleTy(Context);
 570     else if (&V.getSemantics() == &APFloat::x87DoubleExtended)
 571       Ty = Type::getX86_FP80Ty(Context);
 572     else if (&V.getSemantics() == &APFloat::IEEEquad)
 573       Ty = Type::getFP128Ty(Context);
 574     else {
 575       assert(&V.getSemantics() == &APFloat::PPCDoubleDouble &&
 576              "Unknown FP format");
 577       Ty = Type::getPPC_FP128Ty(Context);
 578     }
 579     Slot = new ConstantFP(Ty, V);
 580   }
 581
 582   return Slot;
 583 }
 584
 585 ConstantFP *ConstantFP::getInfinity(Type *Ty, bool Negative) {
 586   const fltSemantics &Semantics = *TypeToFloatSemantics(Ty);
 587   return ConstantFP::get(Ty->getContext(),
 588                          APFloat::getInf(Semantics, Negative));
 589 }
 590
 591 ConstantFP::ConstantFP(Type *Ty, const APFloat& V)
 592   : Constant(Ty, ConstantFPVal, 0, 0), Val(V) {
 593   assert(&V.getSemantics() == TypeToFloatSemantics(Ty) &&
 594          "FP type Mismatch");
 595 }
 596
 597 bool ConstantFP::isExactlyValue(const APFloat &V) const {
 598   return Val.bitwiseIsEqual(V);
 599 }
 600
 601 //===----------------------------------------------------------------------===//
 602 //                   ConstantAggregateZero Implementation
 603 //===----------------------------------------------------------------------===//
 604
 605 /// getSequentialElement - If this CAZ has array or vector type, return a zero
 606 /// with the right element type.
 607 Constant *ConstantAggregateZero::getSequentialElement() {
 608   return Constant::getNullValue(
 609                             cast<SequentialType>(getType())->getElementType());
 610 }
 611
 612 /// getStructElement - If this CAZ has struct type, return a zero with the
 613 /// right element type for the specified element.
 614 Constant *ConstantAggregateZero::getStructElement(unsigned Elt) {
 615   return Constant::getNullValue(
 616                               cast<StructType>(getType())->getElementType(Elt));
 617 }
 618
 619 /// getElementValue - Return a zero of the right value for the specified GEP
 620 /// index if we can, otherwise return null (e.g. if C is a ConstantExpr).
 621 Constant *ConstantAggregateZero::getElementValue(Constant *C) {
 622   if (isa<SequentialType>(getType()))
 623     return getSequentialElement();
 624   return getStructElement(cast<ConstantInt>(C)->getZExtValue());
 625 }
 626
 627 /// getElementValue - Return a zero of the right value for the specified GEP
 628 /// index.
 629 Constant *ConstantAggregateZero::getElementValue(unsigned Idx) {
 630   if (isa<SequentialType>(getType()))
 631     return getSequentialElement();
 632   return getStructElement(Idx);
 633 }
 634
 635
 636 //===----------------------------------------------------------------------===//
 637 //                         UndefValue Implementation
 638 //===----------------------------------------------------------------------===//
 639
 640 /// getSequentialElement - If this undef has array or vector type, return an
 641 /// undef with the right element type.
 642 UndefValue *UndefValue::getSequentialElement() {
 643   return UndefValue::get(cast<SequentialType>(getType())->getElementType());
 644 }
 645
 646 /// getStructElement - If this undef has struct type, return a zero with the
 647 /// right element type for the specified element.
 648 UndefValue *UndefValue::getStructElement(unsigned Elt) {
 649   return UndefValue::get(cast<StructType>(getType())->getElementType(Elt));
 650 }
 651
 652 /// getElementValue - Return an undef of the right value for the specified GEP
 653 /// index if we can, otherwise return null (e.g. if C is a ConstantExpr).
 654 UndefValue *UndefValue::getElementValue(Constant *C) {
 655   if (isa<SequentialType>(getType()))
 656     return getSequentialElement();
 657   return getStructElement(cast<ConstantInt>(C)->getZExtValue());
 658 }
 659
 660 /// getElementValue - Return an undef of the right value for the specified GEP
 661 /// index.
 662 UndefValue *UndefValue::getElementValue(unsigned Idx) {
 663   if (isa<SequentialType>(getType()))
 664     return getSequentialElement();
 665   return getStructElement(Idx);
 666 }
 667
 668
 669
 670 //===----------------------------------------------------------------------===//
 671 //                            ConstantXXX Classes
 672 //===----------------------------------------------------------------------===//
 673
 674
 675 ConstantArray::ConstantArray(ArrayType *T, ArrayRef<Constant *> V)
 676   : Constant(T, ConstantArrayVal,
 677              OperandTraits<ConstantArray>::op_end(this) - V.size(),
 678              V.size()) {
 679   assert(V.size() == T->getNumElements() &&
 680          "Invalid initializer vector for constant array");
 681   for (unsigned i = 0, e = V.size(); i != e; ++i)
 682     assert(V[i]->getType() == T->getElementType() &&
 683            "Initializer for array element doesn't match array element type!");
 684   std::copy(V.begin(), V.end(), op_begin());
 685 }
 686
 687 Constant *ConstantArray::get(ArrayType *Ty, ArrayRef<Constant*> V) {
 688   for (unsigned i = 0, e = V.size(); i != e; ++i) {
 689     assert(V[i]->getType() == Ty->getElementType() &&
 690            "Wrong type in array element initializer");
 691   }
 692   LLVMContextImpl *pImpl = Ty->getContext().pImpl;
 693   // If this is an all-zero array, return a ConstantAggregateZero object
 694   if (!V.empty()) {
 695     Constant *C = V[0];
 696     if (!C->isNullValue())
 697       return pImpl->ArrayConstants.getOrCreate(Ty, V);
 698
 699     for (unsigned i = 1, e = V.size(); i != e; ++i)
 700       if (V[i] != C)
 701         return pImpl->ArrayConstants.getOrCreate(Ty, V);
 702   }
 703
 704   return ConstantAggregateZero::get(Ty);
 705 }
 706
 707 /// ConstantArray::get(const string&) - Return an array that is initialized to
 708 /// contain the specified string.  If length is zero then a null terminator is
 709 /// added to the specified string so that it may be used in a natural way.
 710 /// Otherwise, the length parameter specifies how much of the string to use
 711 /// and it won't be null terminated.
 712 ///
 713 Constant *ConstantArray::get(LLVMContext &Context, StringRef Str,
 714                              bool AddNull) {
 715   std::vector<Constant*> ElementVals;
 716   ElementVals.reserve(Str.size() + size_t(AddNull));
 717   for (unsigned i = 0; i < Str.size(); ++i)
 718     ElementVals.push_back(ConstantInt::get(Type::getInt8Ty(Context), Str[i]));
 719
 720   // Add a null terminator to the string...
 721   if (AddNull)
 722     ElementVals.push_back(ConstantInt::get(Type::getInt8Ty(Context), 0));
 723
 724   ArrayType *ATy = ArrayType::get(Type::getInt8Ty(Context), ElementVals.size());
 725   return get(ATy, ElementVals);
 726 }
 727
 728 /// getTypeForElements - Return an anonymous struct type to use for a constant
 729 /// with the specified set of elements.  The list must not be empty.
 730 StructType *ConstantStruct::getTypeForElements(LLVMContext &Context,
 731                                                ArrayRef<Constant*> V,
 732                                                bool Packed) {
 733   SmallVector<Type*, 16> EltTypes;
 734   for (unsigned i = 0, e = V.size(); i != e; ++i)
 735     EltTypes.push_back(V[i]->getType());
 736
 737   return StructType::get(Context, EltTypes, Packed);
 738 }
 739
 740
 741 StructType *ConstantStruct::getTypeForElements(ArrayRef<Constant*> V,
 742                                                bool Packed) {
 743   assert(!V.empty() &&
 744          "ConstantStruct::getTypeForElements cannot be called on empty list");
 745   return getTypeForElements(V[0]->getContext(), V, Packed);
 746 }
 747
 748
 749 ConstantStruct::ConstantStruct(StructType *T, ArrayRef<Constant *> V)
 750   : Constant(T, ConstantStructVal,
 751              OperandTraits<ConstantStruct>::op_end(this) - V.size(),
 752              V.size()) {
 753   assert(V.size() == T->getNumElements() &&
 754          "Invalid initializer vector for constant structure");
 755   for (unsigned i = 0, e = V.size(); i != e; ++i)
 756     assert((T->isOpaque() || V[i]->getType() == T->getElementType(i)) &&
 757            "Initializer for struct element doesn't match struct element type!");
 758   std::copy(V.begin(), V.end(), op_begin());
 759 }
 760
 761 // ConstantStruct accessors.
 762 Constant *ConstantStruct::get(StructType *ST, ArrayRef<Constant*> V) {
 763   // Create a ConstantAggregateZero value if all elements are zeros.
 764   for (unsigned i = 0, e = V.size(); i != e; ++i)
 765     if (!V[i]->isNullValue())
 766       return ST->getContext().pImpl->StructConstants.getOrCreate(ST, V);
 767
 768   assert((ST->isOpaque() || ST->getNumElements() == V.size()) &&
 769          "Incorrect # elements specified to ConstantStruct::get");
 770   return ConstantAggregateZero::get(ST);
 771 }
 772
 773 Constant *ConstantStruct::get(StructType *T, ...) {
 774   va_list ap;
 775   SmallVector<Constant*, 8> Values;
 776   va_start(ap, T);
 777   while (Constant *Val = va_arg(ap, llvm::Constant*))
 778     Values.push_back(Val);
 779   va_end(ap);
 780   return get(T, Values);
 781 }
 782
 783 ConstantVector::ConstantVector(VectorType *T, ArrayRef<Constant *> V)
 784   : Constant(T, ConstantVectorVal,
 785              OperandTraits<ConstantVector>::op_end(this) - V.size(),
 786              V.size()) {
 787   for (size_t i = 0, e = V.size(); i != e; i++)
 788     assert(V[i]->getType() == T->getElementType() &&
 789            "Initializer for vector element doesn't match vector element type!");
 790   std::copy(V.begin(), V.end(), op_begin());
 791 }
 792
 793 // ConstantVector accessors.
 794 Constant *ConstantVector::get(ArrayRef<Constant*> V) {
 795   assert(!V.empty() && "Vectors can't be empty");
 796   VectorType *T = VectorType::get(V.front()->getType(), V.size());
 797   LLVMContextImpl *pImpl = T->getContext().pImpl;
 798
 799   // If this is an all-undef or all-zero vector, return a
 800   // ConstantAggregateZero or UndefValue.
 801   Constant *C = V[0];
 802   bool isZero = C->isNullValue();
 803   bool isUndef = isa<UndefValue>(C);
 804
 805   if (isZero || isUndef) {
 806     for (unsigned i = 1, e = V.size(); i != e; ++i)
 807       if (V[i] != C) {
 808         isZero = isUndef = false;
 809         break;
 810       }
 811   }
 812
 813   if (isZero)
 814     return ConstantAggregateZero::get(T);
 815   if (isUndef)
 816     return UndefValue::get(T);
 817
 818   return pImpl->VectorConstants.getOrCreate(T, V);
 819 }
 820
 821 // Utility function for determining if a ConstantExpr is a CastOp or not. This
 822 // can't be inline because we don't want to #include Instruction.h into
 823 // Constant.h
 824 bool ConstantExpr::isCast() const {
 825   return Instruction::isCast(getOpcode());
 826 }
 827
 828 bool ConstantExpr::isCompare() const {
 829   return getOpcode() == Instruction::ICmp || getOpcode() == Instruction::FCmp;
 830 }
 831
 832 bool ConstantExpr::isGEPWithNoNotionalOverIndexing() const {
 833   if (getOpcode() != Instruction::GetElementPtr) return false;
 834
 835   gep_type_iterator GEPI = gep_type_begin(this), E = gep_type_end(this);
 836   User::const_op_iterator OI = llvm::next(this->op_begin());
 837
 838   // Skip the first index, as it has no static limit.
 839   ++GEPI;
 840   ++OI;
 841
 842   // The remaining indices must be compile-time known integers within the
 843   // bounds of the corresponding notional static array types.
 844   for (; GEPI != E; ++GEPI, ++OI) {
 845     ConstantInt *CI = dyn_cast<ConstantInt>(*OI);
 846     if (!CI) return false;
 847     if (ArrayType *ATy = dyn_cast<ArrayType>(*GEPI))
 848       if (CI->getValue().getActiveBits() > 64 ||
 849           CI->getZExtValue() >= ATy->getNumElements())
 850         return false;
 851   }
 852
 853   // All the indices checked out.
 854   return true;
 855 }
 856
 857 bool ConstantExpr::hasIndices() const {
 858   return getOpcode() == Instruction::ExtractValue ||
 859          getOpcode() == Instruction::InsertValue;
 860 }
 861
 862 ArrayRef<unsigned> ConstantExpr::getIndices() const {
 863   if (const ExtractValueConstantExpr *EVCE =
 864         dyn_cast<ExtractValueConstantExpr>(this))
 865     return EVCE->Indices;
 866
 867   return cast<InsertValueConstantExpr>(this)->Indices;
 868 }
 869
 870 unsigned ConstantExpr::getPredicate() const {
 871   assert(isCompare());
 872   return ((const CompareConstantExpr*)this)->predicate;
 873 }
 874
 875 /// getWithOperandReplaced - Return a constant expression identical to this
 876 /// one, but with the specified operand set to the specified value.
 877 Constant *
 878 ConstantExpr::getWithOperandReplaced(unsigned OpNo, Constant *Op) const {
 879   assert(OpNo < getNumOperands() && "Operand num is out of range!");
 880   assert(Op->getType() == getOperand(OpNo)->getType() &&
 881          "Replacing operand with value of different type!");
 882   if (getOperand(OpNo) == Op)
 883     return const_cast<ConstantExpr*>(this);
 884
 885   Constant *Op0, *Op1, *Op2;
 886   switch (getOpcode()) {
 887   case Instruction::Trunc:
 888   case Instruction::ZExt:
 889   case Instruction::SExt:
 890   case Instruction::FPTrunc:
 891   case Instruction::FPExt:
 892   case Instruction::UIToFP:
 893   case Instruction::SIToFP:
 894   case Instruction::FPToUI:
 895   case Instruction::FPToSI:
 896   case Instruction::PtrToInt:
 897   case Instruction::IntToPtr:
 898   case Instruction::BitCast:
 899     return ConstantExpr::getCast(getOpcode(), Op, getType());
 900   case Instruction::Select:
 901     Op0 = (OpNo == 0) ? Op : getOperand(0);
 902     Op1 = (OpNo == 1) ? Op : getOperand(1);
 903     Op2 = (OpNo == 2) ? Op : getOperand(2);
 904     return ConstantExpr::getSelect(Op0, Op1, Op2);
 905   case Instruction::InsertElement:
 906     Op0 = (OpNo == 0) ? Op : getOperand(0);
 907     Op1 = (OpNo == 1) ? Op : getOperand(1);
 908     Op2 = (OpNo == 2) ? Op : getOperand(2);
 909     return ConstantExpr::getInsertElement(Op0, Op1, Op2);
 910   case Instruction::ExtractElement:
 911     Op0 = (OpNo == 0) ? Op : getOperand(0);
 912     Op1 = (OpNo == 1) ? Op : getOperand(1);
 913     return ConstantExpr::getExtractElement(Op0, Op1);
 914   case Instruction::ShuffleVector:
 915     Op0 = (OpNo == 0) ? Op : getOperand(0);
 916     Op1 = (OpNo == 1) ? Op : getOperand(1);
 917     Op2 = (OpNo == 2) ? Op : getOperand(2);
 918     return ConstantExpr::getShuffleVector(Op0, Op1, Op2);
 919   case Instruction::GetElementPtr: {
 920     SmallVector<Constant*, 8> Ops;
 921     Ops.resize(getNumOperands()-1);
 922     for (unsigned i = 1, e = getNumOperands(); i != e; ++i)
 923       Ops[i-1] = getOperand(i);
 924     if (OpNo == 0)
 925       return
 926         ConstantExpr::getGetElementPtr(Op, Ops,
 927                                        cast<GEPOperator>(this)->isInBounds());
 928     Ops[OpNo-1] = Op;
 929     return
 930       ConstantExpr::getGetElementPtr(getOperand(0), Ops,
 931                                      cast<GEPOperator>(this)->isInBounds());
 932   }
 933   default:
 934     assert(getNumOperands() == 2 && "Must be binary operator?");
 935     Op0 = (OpNo == 0) ? Op : getOperand(0);
 936     Op1 = (OpNo == 1) ? Op : getOperand(1);
 937     return ConstantExpr::get(getOpcode(), Op0, Op1, SubclassOptionalData);
 938   }
 939 }
 940
 941 /// getWithOperands - This returns the current constant expression with the
 942 /// operands replaced with the specified values.  The specified array must
 943 /// have the same number of operands as our current one.
 944 Constant *ConstantExpr::
 945 getWithOperands(ArrayRef<Constant*> Ops, Type *Ty) const {
 946   assert(Ops.size() == getNumOperands() && "Operand count mismatch!");
 947   bool AnyChange = Ty != getType();
 948   for (unsigned i = 0; i != Ops.size(); ++i)
 949     AnyChange |= Ops[i] != getOperand(i);
 950
 951   if (!AnyChange)  // No operands changed, return self.
 952     return const_cast<ConstantExpr*>(this);
 953
 954   switch (getOpcode()) {
 955   case Instruction::Trunc:
 956   case Instruction::ZExt:
 957   case Instruction::SExt:
 958   case Instruction::FPTrunc:
 959   case Instruction::FPExt:
 960   case Instruction::UIToFP:
 961   case Instruction::SIToFP:
 962   case Instruction::FPToUI:
 963   case Instruction::FPToSI:
 964   case Instruction::PtrToInt:
 965   case Instruction::IntToPtr:
 966   case Instruction::BitCast:
 967     return ConstantExpr::getCast(getOpcode(), Ops[0], Ty);
 968   case Instruction::Select:
 969     return ConstantExpr::getSelect(Ops[0], Ops[1], Ops[2]);
 970   case Instruction::InsertElement:
 971     return ConstantExpr::getInsertElement(Ops[0], Ops[1], Ops[2]);
 972   case Instruction::ExtractElement:
 973     return ConstantExpr::getExtractElement(Ops[0], Ops[1]);
 974   case Instruction::ShuffleVector:
 975     return ConstantExpr::getShuffleVector(Ops[0], Ops[1], Ops[2]);
 976   case Instruction::GetElementPtr:
 977     return
 978       ConstantExpr::getGetElementPtr(Ops[0], Ops.slice(1),
 979                                      cast<GEPOperator>(this)->isInBounds());
 980   case Instruction::ICmp:
 981   case Instruction::FCmp:
 982     return ConstantExpr::getCompare(getPredicate(), Ops[0], Ops[1]);
 983   default:
 984     assert(getNumOperands() == 2 && "Must be binary operator?");
 985     return ConstantExpr::get(getOpcode(), Ops[0], Ops[1], SubclassOptionalData);
 986   }
 987 }
 988
 989
 990 //===----------------------------------------------------------------------===//
 991 //                      isValueValidForType implementations
 992
 993 bool ConstantInt::isValueValidForType(Type *Ty, uint64_t Val) {
 994   unsigned NumBits = cast<IntegerType>(Ty)->getBitWidth(); // assert okay
 995   if (Ty == Type::getInt1Ty(Ty->getContext()))
 996     return Val == 0 || Val == 1;
 997   if (NumBits >= 64)
 998     return true; // always true, has to fit in largest type
 999   uint64_t Max = (1ll << NumBits) - 1;
1000   return Val <= Max;
1001 }
1002
1003 bool ConstantInt::isValueValidForType(Type *Ty, int64_t Val) {
1004   unsigned NumBits = cast<IntegerType>(Ty)->getBitWidth(); // assert okay
1005   if (Ty == Type::getInt1Ty(Ty->getContext()))
1006     return Val == 0 || Val == 1 || Val == -1;
1007   if (NumBits >= 64)
1008     return true; // always true, has to fit in largest type
1009   int64_t Min = -(1ll << (NumBits-1));
1010   int64_t Max = (1ll << (NumBits-1)) - 1;
1011   return (Val >= Min && Val <= Max);
1012 }
1013
1014 bool ConstantFP::isValueValidForType(Type *Ty, const APFloat& Val) {
1015   // convert modifies in place, so make a copy.
1016   APFloat Val2 = APFloat(Val);
1017   bool losesInfo;
1018   switch (Ty->getTypeID()) {
1019   default:
1020     return false;         // These can't be represented as floating point!
1021
1022   // FIXME rounding mode needs to be more flexible
1023   case Type::HalfTyID: {
1024     if (&Val2.getSemantics() == &APFloat::IEEEhalf)
1025       return true;
1026     Val2.convert(APFloat::IEEEhalf, APFloat::rmNearestTiesToEven, &losesInfo);
1027     return !losesInfo;
1028   }
1029   case Type::FloatTyID: {
1030     if (&Val2.getSemantics() == &APFloat::IEEEsingle)
1031       return true;
1032     Val2.convert(APFloat::IEEEsingle, APFloat::rmNearestTiesToEven, &losesInfo);
1033     return !losesInfo;
1034   }
1035   case Type::DoubleTyID: {
1036     if (&Val2.getSemantics() == &APFloat::IEEEhalf ||
1037         &Val2.getSemantics() == &APFloat::IEEEsingle ||
1038         &Val2.getSemantics() == &APFloat::IEEEdouble)
1039       return true;
1040     Val2.convert(APFloat::IEEEdouble, APFloat::rmNearestTiesToEven, &losesInfo);
1041     return !losesInfo;
1042   }
1043   case Type::X86_FP80TyID:
1044     return &Val2.getSemantics() == &APFloat::IEEEhalf ||
1045            &Val2.getSemantics() == &APFloat::IEEEsingle ||
1046            &Val2.getSemantics() == &APFloat::IEEEdouble ||
1047            &Val2.getSemantics() == &APFloat::x87DoubleExtended;
1048   case Type::FP128TyID:
1049     return &Val2.getSemantics() == &APFloat::IEEEhalf ||
1050            &Val2.getSemantics() == &APFloat::IEEEsingle ||
1051            &Val2.getSemantics() == &APFloat::IEEEdouble ||
1052            &Val2.getSemantics() == &APFloat::IEEEquad;
1053   case Type::PPC_FP128TyID:
1054     return &Val2.getSemantics() == &APFloat::IEEEhalf ||
1055            &Val2.getSemantics() == &APFloat::IEEEsingle ||
1056            &Val2.getSemantics() == &APFloat::IEEEdouble ||
1057            &Val2.getSemantics() == &APFloat::PPCDoubleDouble;
1058   }
1059 }
1060
1061
1062 //===----------------------------------------------------------------------===//
1063 //                      Factory Function Implementation
1064
1065 ConstantAggregateZero *ConstantAggregateZero::get(Type *Ty) {
1066   assert((Ty->isStructTy() || Ty->isArrayTy() || Ty->isVectorTy()) &&
1067          "Cannot create an aggregate zero of non-aggregate type!");
1068
1069   ConstantAggregateZero *&Entry = Ty->getContext().pImpl->CAZConstants[Ty];
1070   if (Entry == 0)
1071     Entry = new ConstantAggregateZero(Ty);
1072
1073   return Entry;
1074 }
1075
1076 /// destroyConstant - Remove the constant from the constant table.
1077 ///
1078 void ConstantAggregateZero::destroyConstant() {
1079   getContext().pImpl->CAZConstants.erase(getType());
1080   destroyConstantImpl();
1081 }
1082
1083 /// destroyConstant - Remove the constant from the constant table...
1084 ///
1085 void ConstantArray::destroyConstant() {
1086   getType()->getContext().pImpl->ArrayConstants.remove(this);
1087   destroyConstantImpl();
1088 }
1089
1090 /// isString - This method returns true if the array is an array of i8, and
1091 /// if the elements of the array are all ConstantInt's.
1092 bool ConstantArray::isString() const {
1093   // Check the element type for i8...
1094   if (!getType()->getElementType()->isIntegerTy(8))
1095     return false;
1096   // Check the elements to make sure they are all integers, not constant
1097   // expressions.
1098   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
1099     if (!isa<ConstantInt>(getOperand(i)))
1100       return false;
1101   return true;
1102 }
1103
1104 /// isCString - This method returns true if the array is a string (see
1105 /// isString) and it ends in a null byte \\0 and does not contains any other
1106 /// null bytes except its terminator.
1107 bool ConstantArray::isCString() const {
1108   // Check the element type for i8...
1109   if (!getType()->getElementType()->isIntegerTy(8))
1110     return false;
1111
1112   // Last element must be a null.
1113   if (!getOperand(getNumOperands()-1)->isNullValue())
1114     return false;
1115   // Other elements must be non-null integers.
1116   for (unsigned i = 0, e = getNumOperands()-1; i != e; ++i) {
1117     if (!isa<ConstantInt>(getOperand(i)))
1118       return false;
1119     if (getOperand(i)->isNullValue())
1120       return false;
1121   }
1122   return true;
1123 }
1124
1125
1126 /// convertToString - Helper function for getAsString() and getAsCString().
1127 static std::string convertToString(const User *U, unsigned len) {
1128   std::string Result;
1129   Result.reserve(len);
1130   for (unsigned i = 0; i != len; ++i)
1131     Result.push_back((char)cast<ConstantInt>(U->getOperand(i))->getZExtValue());
1132   return Result;
1133 }
1134
1135 /// getAsString - If this array is isString(), then this method converts the
1136 /// array to an std::string and returns it.  Otherwise, it asserts out.
1137 ///
1138 std::string ConstantArray::getAsString() const {
1139   assert(isString() && "Not a string!");
1140   return convertToString(this, getNumOperands());
1141 }
1142
1143
1144 /// getAsCString - If this array is isCString(), then this method converts the
1145 /// array (without the trailing null byte) to an std::string and returns it.
1146 /// Otherwise, it asserts out.
1147 ///
1148 std::string ConstantArray::getAsCString() const {
1149   assert(isCString() && "Not a string!");
1150   return convertToString(this, getNumOperands() - 1);
1151 }
1152
1153
1154 //---- ConstantStruct::get() implementation...
1155 //
1156
1157 // destroyConstant - Remove the constant from the constant table...
1158 //
1159 void ConstantStruct::destroyConstant() {
1160   getType()->getContext().pImpl->StructConstants.remove(this);
1161   destroyConstantImpl();
1162 }
1163
1164 // destroyConstant - Remove the constant from the constant table...
1165 //
1166 void ConstantVector::destroyConstant() {
1167   getType()->getContext().pImpl->VectorConstants.remove(this);
1168   destroyConstantImpl();
1169 }
1170
1171 /// getSplatValue - If this is a splat constant, where all of the
1172 /// elements have the same value, return that value. Otherwise return null.
1173 Constant *ConstantVector::getSplatValue() const {
1174   // Check out first element.
1175   Constant *Elt = getOperand(0);
1176   // Then make sure all remaining elements point to the same value.
1177   for (unsigned I = 1, E = getNumOperands(); I < E; ++I)
1178     if (getOperand(I) != Elt)
1179       return 0;
1180   return Elt;
1181 }
1182
1183 //---- ConstantPointerNull::get() implementation.
1184 //
1185
1186 ConstantPointerNull *ConstantPointerNull::get(PointerType *Ty) {
1187   ConstantPointerNull *&Entry = Ty->getContext().pImpl->CPNConstants[Ty];
1188   if (Entry == 0)
1189     Entry = new ConstantPointerNull(Ty);
1190
1191   return Entry;
1192 }
1193
1194 // destroyConstant - Remove the constant from the constant table...
1195 //
1196 void ConstantPointerNull::destroyConstant() {
1197   getContext().pImpl->CPNConstants.erase(getType());
1198   // Free the constant and any dangling references to it.
1199   destroyConstantImpl();
1200 }
1201
1202
1203 //---- UndefValue::get() implementation.
1204 //
1205
1206 UndefValue *UndefValue::get(Type *Ty) {
1207   UndefValue *&Entry = Ty->getContext().pImpl->UVConstants[Ty];
1208   if (Entry == 0)
1209     Entry = new UndefValue(Ty);
1210
1211   return Entry;
1212 }
1213
1214 // destroyConstant - Remove the constant from the constant table.
1215 //
1216 void UndefValue::destroyConstant() {
1217   // Free the constant and any dangling references to it.
1218   getContext().pImpl->UVConstants.erase(getType());
1219   destroyConstantImpl();
1220 }
1221
1222 //---- BlockAddress::get() implementation.
1223 //
1224
1225 BlockAddress *BlockAddress::get(BasicBlock *BB) {
1226   assert(BB->getParent() != 0 && "Block must have a parent");
1227   return get(BB->getParent(), BB);
1228 }
1229
1230 BlockAddress *BlockAddress::get(Function *F, BasicBlock *BB) {
1231   BlockAddress *&BA =
1232     F->getContext().pImpl->BlockAddresses[std::make_pair(F, BB)];
1233   if (BA == 0)
1234     BA = new BlockAddress(F, BB);
1235
1236   assert(BA->getFunction() == F && "Basic block moved between functions");
1237   return BA;
1238 }
1239
1240 BlockAddress::BlockAddress(Function *F, BasicBlock *BB)
1241 : Constant(Type::getInt8PtrTy(F->getContext()), Value::BlockAddressVal,
1242            &Op<0>(), 2) {
1243   setOperand(0, F);
1244   setOperand(1, BB);
1245   BB->AdjustBlockAddressRefCount(1);
1246 }
1247
1248
1249 // destroyConstant - Remove the constant from the constant table.
1250 //
1251 void BlockAddress::destroyConstant() {
1252   getFunction()->getType()->getContext().pImpl
1253     ->BlockAddresses.erase(std::make_pair(getFunction(), getBasicBlock()));
1254   getBasicBlock()->AdjustBlockAddressRefCount(-1);
1255   destroyConstantImpl();
1256 }
1257
1258 void BlockAddress::replaceUsesOfWithOnConstant(Value *From, Value *To, Use *U) {
1259   // This could be replacing either the Basic Block or the Function.  In either
1260   // case, we have to remove the map entry.
1261   Function *NewF = getFunction();
1262   BasicBlock *NewBB = getBasicBlock();
1263
1264   if (U == &Op<0>())
1265     NewF = cast<Function>(To);
1266   else
1267     NewBB = cast<BasicBlock>(To);
1268
1269   // See if the 'new' entry already exists, if not, just update this in place
1270   // and return early.
1271   BlockAddress *&NewBA =
1272     getContext().pImpl->BlockAddresses[std::make_pair(NewF, NewBB)];
1273   if (NewBA == 0) {
1274     getBasicBlock()->AdjustBlockAddressRefCount(-1);
1275
1276     // Remove the old entry, this can't cause the map to rehash (just a
1277     // tombstone will get added).
1278     getContext().pImpl->BlockAddresses.erase(std::make_pair(getFunction(),
1279                                                             getBasicBlock()));
1280     NewBA = this;
1281     setOperand(0, NewF);
1282     setOperand(1, NewBB);
1283     getBasicBlock()->AdjustBlockAddressRefCount(1);
1284     return;
1285   }
1286
1287   // Otherwise, I do need to replace this with an existing value.
1288   assert(NewBA != this && "I didn't contain From!");
1289
1290   // Everyone using this now uses the replacement.
1291   replaceAllUsesWith(NewBA);
1292
1293   destroyConstant();
1294 }
1295
1296 //---- ConstantExpr::get() implementations.
1297 //
1298
1299 /// This is a utility function to handle folding of casts and lookup of the
1300 /// cast in the ExprConstants map. It is used by the various get* methods below.
1301 static inline Constant *getFoldedCast(
1302   Instruction::CastOps opc, Constant *C, Type *Ty) {
1303   assert(Ty->isFirstClassType() && "Cannot cast to an aggregate type!");
1304   // Fold a few common cases
1305   if (Constant *FC = ConstantFoldCastInstruction(opc, C, Ty))
1306     return FC;
1307
1308   LLVMContextImpl *pImpl = Ty->getContext().pImpl;
1309
1310   // Look up the constant in the table first to ensure uniqueness
1311   std::vector<Constant*> argVec(1, C);
1312   ExprMapKeyType Key(opc, argVec);
1313
1314   return pImpl->ExprConstants.getOrCreate(Ty, Key);
1315 }
1316
1317 Constant *ConstantExpr::getCast(unsigned oc, Constant *C, Type *Ty) {
1318   Instruction::CastOps opc = Instruction::CastOps(oc);
1319   assert(Instruction::isCast(opc) && "opcode out of range");
1320   assert(C && Ty && "Null arguments to getCast");
1321   assert(CastInst::castIsValid(opc, C, Ty) && "Invalid constantexpr cast!");
1322
1323   switch (opc) {
1324   default:
1325     llvm_unreachable("Invalid cast opcode");
1326   case Instruction::Trunc:    return getTrunc(C, Ty);
1327   case Instruction::ZExt:     return getZExt(C, Ty);
1328   case Instruction::SExt:     return getSExt(C, Ty);
1329   case Instruction::FPTrunc:  return getFPTrunc(C, Ty);
1330   case Instruction::FPExt:    return getFPExtend(C, Ty);
1331   case Instruction::UIToFP:   return getUIToFP(C, Ty);
1332   case Instruction::SIToFP:   return getSIToFP(C, Ty);
1333   case Instruction::FPToUI:   return getFPToUI(C, Ty);
1334   case Instruction::FPToSI:   return getFPToSI(C, Ty);
1335   case Instruction::PtrToInt: return getPtrToInt(C, Ty);
1336   case Instruction::IntToPtr: return getIntToPtr(C, Ty);
1337   case Instruction::BitCast:  return getBitCast(C, Ty);
1338   }
1339 }
1340
1341 Constant *ConstantExpr::getZExtOrBitCast(Constant *C, Type *Ty) {
1342   if (C->getType()->getScalarSizeInBits() == Ty->getScalarSizeInBits())
1343     return getBitCast(C, Ty);
1344   return getZExt(C, Ty);
1345 }
1346
1347 Constant *ConstantExpr::getSExtOrBitCast(Constant *C, Type *Ty) {
1348   if (C->getType()->getScalarSizeInBits() == Ty->getScalarSizeInBits())
1349     return getBitCast(C, Ty);
1350   return getSExt(C, Ty);
1351 }
1352
1353 Constant *ConstantExpr::getTruncOrBitCast(Constant *C, Type *Ty) {
1354   if (C->getType()->getScalarSizeInBits() == Ty->getScalarSizeInBits())
1355     return getBitCast(C, Ty);
1356   return getTrunc(C, Ty);
1357 }
1358
1359 Constant *ConstantExpr::getPointerCast(Constant *S, Type *Ty) {
1360   assert(S->getType()->isPointerTy() && "Invalid cast");
1361   assert((Ty->isIntegerTy() || Ty->isPointerTy()) && "Invalid cast");
1362
1363   if (Ty->isIntegerTy())
1364     return getPtrToInt(S, Ty);
1365   return getBitCast(S, Ty);
1366 }
1367
1368 Constant *ConstantExpr::getIntegerCast(Constant *C, Type *Ty,
1369                                        bool isSigned) {
1370   assert(C->getType()->isIntOrIntVectorTy() &&
1371          Ty->isIntOrIntVectorTy() && "Invalid cast");
1372   unsigned SrcBits = C->getType()->getScalarSizeInBits();
1373   unsigned DstBits = Ty->getScalarSizeInBits();
1374   Instruction::CastOps opcode =
1375     (SrcBits == DstBits ? Instruction::BitCast :
1376      (SrcBits > DstBits ? Instruction::Trunc :
1377       (isSigned ? Instruction::SExt : Instruction::ZExt)));
1378   return getCast(opcode, C, Ty);
1379 }
1380
1381 Constant *ConstantExpr::getFPCast(Constant *C, Type *Ty) {
1382   assert(C->getType()->isFPOrFPVectorTy() && Ty->isFPOrFPVectorTy() &&
1383          "Invalid cast");
1384   unsigned SrcBits = C->getType()->getScalarSizeInBits();
1385   unsigned DstBits = Ty->getScalarSizeInBits();
1386   if (SrcBits == DstBits)
1387     return C; // Avoid a useless cast
1388   Instruction::CastOps opcode =
1389     (SrcBits > DstBits ? Instruction::FPTrunc : Instruction::FPExt);
1390   return getCast(opcode, C, Ty);
1391 }
1392
1393 Constant *ConstantExpr::getTrunc(Constant *C, Type *Ty) {
1394 #ifndef NDEBUG
1395   bool fromVec = C->getType()->getTypeID() == Type::VectorTyID;
1396   bool toVec = Ty->getTypeID() == Type::VectorTyID;
1397 #endif
1398   assert((fromVec == toVec) && "Cannot convert from scalar to/from vector");
1399   assert(C->getType()->isIntOrIntVectorTy() && "Trunc operand must be integer");
1400   assert(Ty->isIntOrIntVectorTy() && "Trunc produces only integral");
1401   assert(C->getType()->getScalarSizeInBits() > Ty->getScalarSizeInBits()&&
1402          "SrcTy must be larger than DestTy for Trunc!");
1403
1404   return getFoldedCast(Instruction::Trunc, C, Ty);
1405 }
1406
1407 Constant *ConstantExpr::getSExt(Constant *C, Type *Ty) {
1408 #ifndef NDEBUG
1409   bool fromVec = C->getType()->getTypeID() == Type::VectorTyID;
1410   bool toVec = Ty->getTypeID() == Type::VectorTyID;
1411 #endif
1412   assert((fromVec == toVec) && "Cannot convert from scalar to/from vector");
1413   assert(C->getType()->isIntOrIntVectorTy() && "SExt operand must be integral");
1414   assert(Ty->isIntOrIntVectorTy() && "SExt produces only integer");
1415   assert(C->getType()->getScalarSizeInBits() < Ty->getScalarSizeInBits()&&
1416          "SrcTy must be smaller than DestTy for SExt!");
1417
1418   return getFoldedCast(Instruction::SExt, C, Ty);
1419 }
1420
1421 Constant *ConstantExpr::getZExt(Constant *C, Type *Ty) {
1422 #ifndef NDEBUG
1423   bool fromVec = C->getType()->getTypeID() == Type::VectorTyID;
1424   bool toVec = Ty->getTypeID() == Type::VectorTyID;
1425 #endif
1426   assert((fromVec == toVec) && "Cannot convert from scalar to/from vector");
1427   assert(C->getType()->isIntOrIntVectorTy() && "ZEXt operand must be integral");
1428   assert(Ty->isIntOrIntVectorTy() && "ZExt produces only integer");
1429   assert(C->getType()->getScalarSizeInBits() < Ty->getScalarSizeInBits()&&
1430          "SrcTy must be smaller than DestTy for ZExt!");
1431
1432   return getFoldedCast(Instruction::ZExt, C, Ty);
1433 }
1434
1435 Constant *ConstantExpr::getFPTrunc(Constant *C, Type *Ty) {
1436 #ifndef NDEBUG
1437   bool fromVec = C->getType()->getTypeID() == Type::VectorTyID;
1438   bool toVec = Ty->getTypeID() == Type::VectorTyID;
1439 #endif
1440   assert((fromVec == toVec) && "Cannot convert from scalar to/from vector");
1441   assert(C->getType()->isFPOrFPVectorTy() && Ty->isFPOrFPVectorTy() &&
1442          C->getType()->getScalarSizeInBits() > Ty->getScalarSizeInBits()&&
1443          "This is an illegal floating point truncation!");
1444   return getFoldedCast(Instruction::FPTrunc, C, Ty);
1445 }
1446
1447 Constant *ConstantExpr::getFPExtend(Constant *C, Type *Ty) {
1448 #ifndef NDEBUG
1449   bool fromVec = C->getType()->getTypeID() == Type::VectorTyID;
1450   bool toVec = Ty->getTypeID() == Type::VectorTyID;
1451 #endif
1452   assert((fromVec == toVec) && "Cannot convert from scalar to/from vector");
1453   assert(C->getType()->isFPOrFPVectorTy() && Ty->isFPOrFPVectorTy() &&
1454          C->getType()->getScalarSizeInBits() < Ty->getScalarSizeInBits()&&
1455          "This is an illegal floating point extension!");
1456   return getFoldedCast(Instruction::FPExt, C, Ty);
1457 }
1458
1459 Constant *ConstantExpr::getUIToFP(Constant *C, Type *Ty) {
1460 #ifndef NDEBUG
1461   bool fromVec = C->getType()->getTypeID() == Type::VectorTyID;
1462   bool toVec = Ty->getTypeID() == Type::VectorTyID;
1463 #endif
1464   assert((fromVec == toVec) && "Cannot convert from scalar to/from vector");
1465   assert(C->getType()->isIntOrIntVectorTy() && Ty->isFPOrFPVectorTy() &&
1466          "This is an illegal uint to floating point cast!");
1467   return getFoldedCast(Instruction::UIToFP, C, Ty);
1468 }
1469
1470 Constant *ConstantExpr::getSIToFP(Constant *C, Type *Ty) {
1471 #ifndef NDEBUG
1472   bool fromVec = C->getType()->getTypeID() == Type::VectorTyID;
1473   bool toVec = Ty->getTypeID() == Type::VectorTyID;
1474 #endif
1475   assert((fromVec == toVec) && "Cannot convert from scalar to/from vector");
1476   assert(C->getType()->isIntOrIntVectorTy() && Ty->isFPOrFPVectorTy() &&
1477          "This is an illegal sint to floating point cast!");
1478   return getFoldedCast(Instruction::SIToFP, C, Ty);
1479 }
1480
1481 Constant *ConstantExpr::getFPToUI(Constant *C, Type *Ty) {
1482 #ifndef NDEBUG
1483   bool fromVec = C->getType()->getTypeID() == Type::VectorTyID;
1484   bool toVec = Ty->getTypeID() == Type::VectorTyID;
1485 #endif
1486   assert((fromVec == toVec) && "Cannot convert from scalar to/from vector");
1487   assert(C->getType()->isFPOrFPVectorTy() && Ty->isIntOrIntVectorTy() &&
1488          "This is an illegal floating point to uint cast!");
1489   return getFoldedCast(Instruction::FPToUI, C, Ty);
1490 }
1491
1492 Constant *ConstantExpr::getFPToSI(Constant *C, Type *Ty) {
1493 #ifndef NDEBUG
1494   bool fromVec = C->getType()->getTypeID() == Type::VectorTyID;
1495   bool toVec = Ty->getTypeID() == Type::VectorTyID;
1496 #endif
1497   assert((fromVec == toVec) && "Cannot convert from scalar to/from vector");
1498   assert(C->getType()->isFPOrFPVectorTy() && Ty->isIntOrIntVectorTy() &&
1499          "This is an illegal floating point to sint cast!");
1500   return getFoldedCast(Instruction::FPToSI, C, Ty);
1501 }
1502
1503 Constant *ConstantExpr::getPtrToInt(Constant *C, Type *DstTy) {
1504   assert(C->getType()->getScalarType()->isPointerTy() &&
1505          "PtrToInt source must be pointer or pointer vector");
1506   assert(DstTy->getScalarType()->isIntegerTy() &&
1507          "PtrToInt destination must be integer or integer vector");
1508   assert(isa<VectorType>(C->getType()) == isa<VectorType>(DstTy));
1509   if (isa<VectorType>(C->getType()))
1510     assert(cast<VectorType>(C->getType())->getNumElements() ==
1511            cast<VectorType>(DstTy)->getNumElements() &&
1512            "Invalid cast between a different number of vector elements");
1513   return getFoldedCast(Instruction::PtrToInt, C, DstTy);
1514 }
1515
1516 Constant *ConstantExpr::getIntToPtr(Constant *C, Type *DstTy) {
1517   assert(C->getType()->getScalarType()->isIntegerTy() &&
1518          "IntToPtr source must be integer or integer vector");
1519   assert(DstTy->getScalarType()->isPointerTy() &&
1520          "IntToPtr destination must be a pointer or pointer vector");
1521   assert(isa<VectorType>(C->getType()) == isa<VectorType>(DstTy));
1522   if (isa<VectorType>(C->getType()))
1523     assert(cast<VectorType>(C->getType())->getNumElements() ==
1524            cast<VectorType>(DstTy)->getNumElements() &&
1525            "Invalid cast between a different number of vector elements");
1526   return getFoldedCast(Instruction::IntToPtr, C, DstTy);
1527 }
1528
1529 Constant *ConstantExpr::getBitCast(Constant *C, Type *DstTy) {
1530   assert(CastInst::castIsValid(Instruction::BitCast, C, DstTy) &&
1531          "Invalid constantexpr bitcast!");
1532
1533   // It is common to ask for a bitcast of a value to its own type, handle this
1534   // speedily.
1535   if (C->getType() == DstTy) return C;
1536
1537   return getFoldedCast(Instruction::BitCast, C, DstTy);
1538 }
1539
1540 Constant *ConstantExpr::get(unsigned Opcode, Constant *C1, Constant *C2,
1541                             unsigned Flags) {
1542   // Check the operands for consistency first.
1543   assert(Opcode >= Instruction::BinaryOpsBegin &&
1544          Opcode <  Instruction::BinaryOpsEnd   &&
1545          "Invalid opcode in binary constant expression");
1546   assert(C1->getType() == C2->getType() &&
1547          "Operand types in binary constant expression should match");
1548
1549 #ifndef NDEBUG
1550   switch (Opcode) {
1551   case Instruction::Add:
1552   case Instruction::Sub:
1553   case Instruction::Mul:
1554     assert(C1->getType() == C2->getType() && "Op types should be identical!");
1555     assert(C1->getType()->isIntOrIntVectorTy() &&
1556            "Tried to create an integer operation on a non-integer type!");
1557     break;
1558   case Instruction::FAdd:
1559   case Instruction::FSub:
1560   case Instruction::FMul:
1561     assert(C1->getType() == C2->getType() && "Op types should be identical!");
1562     assert(C1->getType()->isFPOrFPVectorTy() &&
1563            "Tried to create a floating-point operation on a "
1564            "non-floating-point type!");
1565     break;
1566   case Instruction::UDiv:
1567   case Instruction::SDiv:
1568     assert(C1->getType() == C2->getType() && "Op types should be identical!");
1569     assert(C1->getType()->isIntOrIntVectorTy() &&
1570            "Tried to create an arithmetic operation on a non-arithmetic type!");
1571     break;
1572   case Instruction::FDiv:
1573     assert(C1->getType() == C2->getType() && "Op types should be identical!");
1574     assert(C1->getType()->isFPOrFPVectorTy() &&
1575            "Tried to create an arithmetic operation on a non-arithmetic type!");
1576     break;
1577   case Instruction::URem:
1578   case Instruction::SRem:
1579     assert(C1->getType() == C2->getType() && "Op types should be identical!");
1580     assert(C1->getType()->isIntOrIntVectorTy() &&
1581            "Tried to create an arithmetic operation on a non-arithmetic type!");
1582     break;
1583   case Instruction::FRem:
1584     assert(C1->getType() == C2->getType() && "Op types should be identical!");
1585     assert(C1->getType()->isFPOrFPVectorTy() &&
1586            "Tried to create an arithmetic operation on a non-arithmetic type!");
1587     break;
1588   case Instruction::And:
1589   case Instruction::Or:
1590   case Instruction::Xor:
1591     assert(C1->getType() == C2->getType() && "Op types should be identical!");
1592     assert(C1->getType()->isIntOrIntVectorTy() &&
1593            "Tried to create a logical operation on a non-integral type!");
1594     break;
1595   case Instruction::Shl:
1596   case Instruction::LShr:
1597   case Instruction::AShr:
1598     assert(C1->getType() == C2->getType() && "Op types should be identical!");
1599     assert(C1->getType()->isIntOrIntVectorTy() &&
1600            "Tried to create a shift operation on a non-integer type!");
1601     break;
1602   default:
1603     break;
1604   }
1605 #endif
1606
1607   if (Constant *FC = ConstantFoldBinaryInstruction(Opcode, C1, C2))
1608     return FC;          // Fold a few common cases.
1609
1610   std::vector<Constant*> argVec(1, C1);
1611   argVec.push_back(C2);
1612   ExprMapKeyType Key(Opcode, argVec, 0, Flags);
1613
1614   LLVMContextImpl *pImpl = C1->getContext().pImpl;
1615   return pImpl->ExprConstants.getOrCreate(C1->getType(), Key);
1616 }
1617
1618 Constant *ConstantExpr::getSizeOf(Type* Ty) {
1619   // sizeof is implemented as: (i64) gep (Ty*)null, 1
1620   // Note that a non-inbounds gep is used, as null isn't within any object.
1621   Constant *GEPIdx = ConstantInt::get(Type::getInt32Ty(Ty->getContext()), 1);
1622   Constant *GEP = getGetElementPtr(
1623                  Constant::getNullValue(PointerType::getUnqual(Ty)), GEPIdx);
1624   return getPtrToInt(GEP,
1625                      Type::getInt64Ty(Ty->getContext()));
1626 }
1627
1628 Constant *ConstantExpr::getAlignOf(Type* Ty) {
1629   // alignof is implemented as: (i64) gep ({i1,Ty}*)null, 0, 1
1630   // Note that a non-inbounds gep is used, as null isn't within any object.
1631   Type *AligningTy =
1632     StructType::get(Type::getInt1Ty(Ty->getContext()), Ty, NULL);
1633   Constant *NullPtr = Constant::getNullValue(AligningTy->getPointerTo());
1634   Constant *Zero = ConstantInt::get(Type::getInt64Ty(Ty->getContext()), 0);
1635   Constant *One = ConstantInt::get(Type::getInt32Ty(Ty->getContext()), 1);
1636   Constant *Indices[2] = { Zero, One };
1637   Constant *GEP = getGetElementPtr(NullPtr, Indices);
1638   return getPtrToInt(GEP,
1639                      Type::getInt64Ty(Ty->getContext()));
1640 }
1641
1642 Constant *ConstantExpr::getOffsetOf(StructType* STy, unsigned FieldNo) {
1643   return getOffsetOf(STy, ConstantInt::get(Type::getInt32Ty(STy->getContext()),
1644                                            FieldNo));
1645 }
1646
1647 Constant *ConstantExpr::getOffsetOf(Type* Ty, Constant *FieldNo) {
1648   // offsetof is implemented as: (i64) gep (Ty*)null, 0, FieldNo
1649   // Note that a non-inbounds gep is used, as null isn't within any object.
1650   Constant *GEPIdx[] = {
1651     ConstantInt::get(Type::getInt64Ty(Ty->getContext()), 0),
1652     FieldNo
1653   };
1654   Constant *GEP = getGetElementPtr(
1655                 Constant::getNullValue(PointerType::getUnqual(Ty)), GEPIdx);
1656   return getPtrToInt(GEP,
1657                      Type::getInt64Ty(Ty->getContext()));
1658 }
1659
1660 Constant *ConstantExpr::getCompare(unsigned short Predicate,
1661                                    Constant *C1, Constant *C2) {
1662   assert(C1->getType() == C2->getType() && "Op types should be identical!");
1663
1664   switch (Predicate) {
1665   default: llvm_unreachable("Invalid CmpInst predicate");
1666   case CmpInst::FCMP_FALSE: case CmpInst::FCMP_OEQ: case CmpInst::FCMP_OGT:
1667   case CmpInst::FCMP_OGE:   case CmpInst::FCMP_OLT: case CmpInst::FCMP_OLE:
1668   case CmpInst::FCMP_ONE:   case CmpInst::FCMP_ORD: case CmpInst::FCMP_UNO:
1669   case CmpInst::FCMP_UEQ:   case CmpInst::FCMP_UGT: case CmpInst::FCMP_UGE:
1670   case CmpInst::FCMP_ULT:   case CmpInst::FCMP_ULE: case CmpInst::FCMP_UNE:
1671   case CmpInst::FCMP_TRUE:
1672     return getFCmp(Predicate, C1, C2);
1673
1674   case CmpInst::ICMP_EQ:  case CmpInst::ICMP_NE:  case CmpInst::ICMP_UGT:
1675   case CmpInst::ICMP_UGE: case CmpInst::ICMP_ULT: case CmpInst::ICMP_ULE:
1676   case CmpInst::ICMP_SGT: case CmpInst::ICMP_SGE: case CmpInst::ICMP_SLT:
1677   case CmpInst::ICMP_SLE:
1678     return getICmp(Predicate, C1, C2);
1679   }
1680 }
1681
1682 Constant *ConstantExpr::getSelect(Constant *C, Constant *V1, Constant *V2) {
1683   assert(!SelectInst::areInvalidOperands(C, V1, V2)&&"Invalid select operands");
1684
1685   if (Constant *SC = ConstantFoldSelectInstruction(C, V1, V2))
1686     return SC;        // Fold common cases
1687
1688   std::vector<Constant*> argVec(3, C);
1689   argVec[1] = V1;
1690   argVec[2] = V2;
1691   ExprMapKeyType Key(Instruction::Select, argVec);
1692
1693   LLVMContextImpl *pImpl = C->getContext().pImpl;
1694   return pImpl->ExprConstants.getOrCreate(V1->getType(), Key);
1695 }
1696
1697 Constant *ConstantExpr::getGetElementPtr(Constant *C, ArrayRef<Value *> Idxs,
1698                                          bool InBounds) {
1699   if (Constant *FC = ConstantFoldGetElementPtr(C, InBounds, Idxs))
1700     return FC;          // Fold a few common cases.
1701
1702   // Get the result type of the getelementptr!
1703   Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), Idxs);
1704   assert(Ty && "GEP indices invalid!");
1705   unsigned AS = cast<PointerType>(C->getType())->getAddressSpace();
1706   Type *ReqTy = Ty->getPointerTo(AS);
1707
1708   assert(C->getType()->isPointerTy() &&
1709          "Non-pointer type for constant GetElementPtr expression");
1710   // Look up the constant in the table first to ensure uniqueness
1711   std::vector<Constant*> ArgVec;
1712   ArgVec.reserve(1 + Idxs.size());
1713   ArgVec.push_back(C);
1714   for (unsigned i = 0, e = Idxs.size(); i != e; ++i)
1715     ArgVec.push_back(cast<Constant>(Idxs[i]));
1716   const ExprMapKeyType Key(Instruction::GetElementPtr, ArgVec, 0,
1717                            InBounds ? GEPOperator::IsInBounds : 0);
1718
1719   LLVMContextImpl *pImpl = C->getContext().pImpl;
1720   return pImpl->ExprConstants.getOrCreate(ReqTy, Key);
1721 }
1722
1723 Constant *
1724 ConstantExpr::getICmp(unsigned short pred, Constant *LHS, Constant *RHS) {
1725   assert(LHS->getType() == RHS->getType());
1726   assert(pred >= ICmpInst::FIRST_ICMP_PREDICATE &&
1727          pred <= ICmpInst::LAST_ICMP_PREDICATE && "Invalid ICmp Predicate");
1728
1729   if (Constant *FC = ConstantFoldCompareInstruction(pred, LHS, RHS))
1730     return FC;          // Fold a few common cases...
1731
1732   // Look up the constant in the table first to ensure uniqueness
1733   std::vector<Constant*> ArgVec;
1734   ArgVec.push_back(LHS);
1735   ArgVec.push_back(RHS);
1736   // Get the key type with both the opcode and predicate
1737   const ExprMapKeyType Key(Instruction::ICmp, ArgVec, pred);
1738
1739   Type *ResultTy = Type::getInt1Ty(LHS->getContext());
1740   if (VectorType *VT = dyn_cast<VectorType>(LHS->getType()))
1741     ResultTy = VectorType::get(ResultTy, VT->getNumElements());
1742
1743   LLVMContextImpl *pImpl = LHS->getType()->getContext().pImpl;
1744   return pImpl->ExprConstants.getOrCreate(ResultTy, Key);
1745 }
1746
1747 Constant *
1748 ConstantExpr::getFCmp(unsigned short pred, Constant *LHS, Constant *RHS) {
1749   assert(LHS->getType() == RHS->getType());
1750   assert(pred <= FCmpInst::LAST_FCMP_PREDICATE && "Invalid FCmp Predicate");
1751
1752   if (Constant *FC = ConstantFoldCompareInstruction(pred, LHS, RHS))
1753     return FC;          // Fold a few common cases...
1754
1755   // Look up the constant in the table first to ensure uniqueness
1756   std::vector<Constant*> ArgVec;
1757   ArgVec.push_back(LHS);
1758   ArgVec.push_back(RHS);
1759   // Get the key type with both the opcode and predicate
1760   const ExprMapKeyType Key(Instruction::FCmp, ArgVec, pred);
1761
1762   Type *ResultTy = Type::getInt1Ty(LHS->getContext());
1763   if (VectorType *VT = dyn_cast<VectorType>(LHS->getType()))
1764     ResultTy = VectorType::get(ResultTy, VT->getNumElements());
1765
1766   LLVMContextImpl *pImpl = LHS->getType()->getContext().pImpl;
1767   return pImpl->ExprConstants.getOrCreate(ResultTy, Key);
1768 }
1769
1770 Constant *ConstantExpr::getExtractElement(Constant *Val, Constant *Idx) {
1771   assert(Val->getType()->isVectorTy() &&
1772          "Tried to create extractelement operation on non-vector type!");
1773   assert(Idx->getType()->isIntegerTy(32) &&
1774          "Extractelement index must be i32 type!");
1775
1776   if (Constant *FC = ConstantFoldExtractElementInstruction(Val, Idx))
1777     return FC;          // Fold a few common cases.
1778
1779   // Look up the constant in the table first to ensure uniqueness
1780   std::vector<Constant*> ArgVec(1, Val);
1781   ArgVec.push_back(Idx);
1782   const ExprMapKeyType Key(Instruction::ExtractElement,ArgVec);
1783
1784   LLVMContextImpl *pImpl = Val->getContext().pImpl;
1785   Type *ReqTy = cast<VectorType>(Val->getType())->getElementType();
1786   return pImpl->ExprConstants.getOrCreate(ReqTy, Key);
1787 }
1788
1789 Constant *ConstantExpr::getInsertElement(Constant *Val, Constant *Elt,
1790                                          Constant *Idx) {
1791   assert(Val->getType()->isVectorTy() &&
1792          "Tried to create insertelement operation on non-vector type!");
1793   assert(Elt->getType() == cast<VectorType>(Val->getType())->getElementType()
1794          && "Insertelement types must match!");
1795   assert(Idx->getType()->isIntegerTy(32) &&
1796          "Insertelement index must be i32 type!");
1797
1798   if (Constant *FC = ConstantFoldInsertElementInstruction(Val, Elt, Idx))
1799     return FC;          // Fold a few common cases.
1800   // Look up the constant in the table first to ensure uniqueness
1801   std::vector<Constant*> ArgVec(1, Val);
1802   ArgVec.push_back(Elt);
1803   ArgVec.push_back(Idx);
1804   const ExprMapKeyType Key(Instruction::InsertElement,ArgVec);
1805
1806   LLVMContextImpl *pImpl = Val->getContext().pImpl;
1807   return pImpl->ExprConstants.getOrCreate(Val->getType(), Key);
1808 }
1809
1810 Constant *ConstantExpr::getShuffleVector(Constant *V1, Constant *V2,
1811                                          Constant *Mask) {
1812   assert(ShuffleVectorInst::isValidOperands(V1, V2, Mask) &&
1813          "Invalid shuffle vector constant expr operands!");
1814
1815   if (Constant *FC = ConstantFoldShuffleVectorInstruction(V1, V2, Mask))
1816     return FC;          // Fold a few common cases.
1817
1818   unsigned NElts = cast<VectorType>(Mask->getType())->getNumElements();
1819   Type *EltTy = cast<VectorType>(V1->getType())->getElementType();
1820   Type *ShufTy = VectorType::get(EltTy, NElts);
1821
1822   // Look up the constant in the table first to ensure uniqueness
1823   std::vector<Constant*> ArgVec(1, V1);
1824   ArgVec.push_back(V2);
1825   ArgVec.push_back(Mask);
1826   const ExprMapKeyType Key(Instruction::ShuffleVector,ArgVec);
1827
1828   LLVMContextImpl *pImpl = ShufTy->getContext().pImpl;
1829   return pImpl->ExprConstants.getOrCreate(ShufTy, Key);
1830 }
1831
1832 Constant *ConstantExpr::getInsertValue(Constant *Agg, Constant *Val,
1833                                        ArrayRef<unsigned> Idxs) {
1834   assert(ExtractValueInst::getIndexedType(Agg->getType(),
1835                                           Idxs) == Val->getType() &&
1836          "insertvalue indices invalid!");
1837   assert(Agg->getType()->isFirstClassType() &&
1838          "Non-first-class type for constant insertvalue expression");
1839   Constant *FC = ConstantFoldInsertValueInstruction(Agg, Val, Idxs);
1840   assert(FC && "insertvalue constant expr couldn't be folded!");
1841   return FC;
1842 }
1843
1844 Constant *ConstantExpr::getExtractValue(Constant *Agg,
1845                                         ArrayRef<unsigned> Idxs) {
1846   assert(Agg->getType()->isFirstClassType() &&
1847          "Tried to create extractelement operation on non-first-class type!");
1848
1849   Type *ReqTy = ExtractValueInst::getIndexedType(Agg->getType(), Idxs);
1850   (void)ReqTy;
1851   assert(ReqTy && "extractvalue indices invalid!");
1852
1853   assert(Agg->getType()->isFirstClassType() &&
1854          "Non-first-class type for constant extractvalue expression");
1855   Constant *FC = ConstantFoldExtractValueInstruction(Agg, Idxs);
1856   assert(FC && "ExtractValue constant expr couldn't be folded!");
1857   return FC;
1858 }
1859
1860 Constant *ConstantExpr::getNeg(Constant *C, bool HasNUW, bool HasNSW) {
1861   assert(C->getType()->isIntOrIntVectorTy() &&
1862          "Cannot NEG a nonintegral value!");
1863   return getSub(ConstantFP::getZeroValueForNegation(C->getType()),
1864                 C, HasNUW, HasNSW);
1865 }
1866
1867 Constant *ConstantExpr::getFNeg(Constant *C) {
1868   assert(C->getType()->isFPOrFPVectorTy() &&
1869          "Cannot FNEG a non-floating-point value!");
1870   return getFSub(ConstantFP::getZeroValueForNegation(C->getType()), C);
1871 }
1872
1873 Constant *ConstantExpr::getNot(Constant *C) {
1874   assert(C->getType()->isIntOrIntVectorTy() &&
1875          "Cannot NOT a nonintegral value!");
1876   return get(Instruction::Xor, C, Constant::getAllOnesValue(C->getType()));
1877 }
1878
1879 Constant *ConstantExpr::getAdd(Constant *C1, Constant *C2,
1880                                bool HasNUW, bool HasNSW) {
1881   unsigned Flags = (HasNUW ? OverflowingBinaryOperator::NoUnsignedWrap : 0) |
1882                    (HasNSW ? OverflowingBinaryOperator::NoSignedWrap   : 0);
1883   return get(Instruction::Add, C1, C2, Flags);
1884 }
1885
1886 Constant *ConstantExpr::getFAdd(Constant *C1, Constant *C2) {
1887   return get(Instruction::FAdd, C1, C2);
1888 }
1889
1890 Constant *ConstantExpr::getSub(Constant *C1, Constant *C2,
1891                                bool HasNUW, bool HasNSW) {
1892   unsigned Flags = (HasNUW ? OverflowingBinaryOperator::NoUnsignedWrap : 0) |
1893                    (HasNSW ? OverflowingBinaryOperator::NoSignedWrap   : 0);
1894   return get(Instruction::Sub, C1, C2, Flags);
1895 }
1896
1897 Constant *ConstantExpr::getFSub(Constant *C1, Constant *C2) {
1898   return get(Instruction::FSub, C1, C2);
1899 }
1900
1901 Constant *ConstantExpr::getMul(Constant *C1, Constant *C2,
1902                                bool HasNUW, bool HasNSW) {
1903   unsigned Flags = (HasNUW ? OverflowingBinaryOperator::NoUnsignedWrap : 0) |
1904                    (HasNSW ? OverflowingBinaryOperator::NoSignedWrap   : 0);
1905   return get(Instruction::Mul, C1, C2, Flags);
1906 }
1907
1908 Constant *ConstantExpr::getFMul(Constant *C1, Constant *C2) {
1909   return get(Instruction::FMul, C1, C2);
1910 }
1911
1912 Constant *ConstantExpr::getUDiv(Constant *C1, Constant *C2, bool isExact) {
1913   return get(Instruction::UDiv, C1, C2,
1914              isExact ? PossiblyExactOperator::IsExact : 0);
1915 }
1916
1917 Constant *ConstantExpr::getSDiv(Constant *C1, Constant *C2, bool isExact) {
1918   return get(Instruction::SDiv, C1, C2,
1919              isExact ? PossiblyExactOperator::IsExact : 0);
1920 }
1921
1922 Constant *ConstantExpr::getFDiv(Constant *C1, Constant *C2) {
1923   return get(Instruction::FDiv, C1, C2);
1924 }
1925
1926 Constant *ConstantExpr::getURem(Constant *C1, Constant *C2) {
1927   return get(Instruction::URem, C1, C2);
1928 }
1929
1930 Constant *ConstantExpr::getSRem(Constant *C1, Constant *C2) {
1931   return get(Instruction::SRem, C1, C2);
1932 }
1933
1934 Constant *ConstantExpr::getFRem(Constant *C1, Constant *C2) {
1935   return get(Instruction::FRem, C1, C2);
1936 }
1937
1938 Constant *ConstantExpr::getAnd(Constant *C1, Constant *C2) {
1939   return get(Instruction::And, C1, C2);
1940 }
1941
1942 Constant *ConstantExpr::getOr(Constant *C1, Constant *C2) {
1943   return get(Instruction::Or, C1, C2);
1944 }
1945
1946 Constant *ConstantExpr::getXor(Constant *C1, Constant *C2) {
1947   return get(Instruction::Xor, C1, C2);
1948 }
1949
1950 Constant *ConstantExpr::getShl(Constant *C1, Constant *C2,
1951                                bool HasNUW, bool HasNSW) {
1952   unsigned Flags = (HasNUW ? OverflowingBinaryOperator::NoUnsignedWrap : 0) |
1953                    (HasNSW ? OverflowingBinaryOperator::NoSignedWrap   : 0);
1954   return get(Instruction::Shl, C1, C2, Flags);
1955 }
1956
1957 Constant *ConstantExpr::getLShr(Constant *C1, Constant *C2, bool isExact) {
1958   return get(Instruction::LShr, C1, C2,
1959              isExact ? PossiblyExactOperator::IsExact : 0);
1960 }
1961
1962 Constant *ConstantExpr::getAShr(Constant *C1, Constant *C2, bool isExact) {
1963   return get(Instruction::AShr, C1, C2,
1964              isExact ? PossiblyExactOperator::IsExact : 0);
1965 }
1966
1967 // destroyConstant - Remove the constant from the constant table...
1968 //
1969 void ConstantExpr::destroyConstant() {
1970   getType()->getContext().pImpl->ExprConstants.remove(this);
1971   destroyConstantImpl();
1972 }
1973
1974 const char *ConstantExpr::getOpcodeName() const {
1975   return Instruction::getOpcodeName(getOpcode());
1976 }
1977
1978
1979
1980 GetElementPtrConstantExpr::
1981 GetElementPtrConstantExpr(Constant *C, const std::vector<Constant*> &IdxList,
1982                           Type *DestTy)
1983   : ConstantExpr(DestTy, Instruction::GetElementPtr,
1984                  OperandTraits<GetElementPtrConstantExpr>::op_end(this)
1985                  - (IdxList.size()+1), IdxList.size()+1) {
1986   OperandList[0] = C;
1987   for (unsigned i = 0, E = IdxList.size(); i != E; ++i)
1988     OperandList[i+1] = IdxList[i];
1989 }
1990
1991 //===----------------------------------------------------------------------===//
1992 //                       ConstantData* implementations
1993
1994 void ConstantDataArray::anchor() {}
1995 void ConstantDataVector::anchor() {}
1996
1997 /// getElementType - Return the element type of the array/vector.
1998 Type *ConstantDataSequential::getElementType() const {
1999   return getType()->getElementType();
2000 }
2001
2002 StringRef ConstantDataSequential::getRawDataValues() const {
2003   return StringRef(DataElements, getNumElements()*getElementByteSize());
2004 }
2005
2006 /// isElementTypeCompatible - Return true if a ConstantDataSequential can be
2007 /// formed with a vector or array of the specified element type.
2008 /// ConstantDataArray only works with normal float and int types that are
2009 /// stored densely in memory, not with things like i42 or x86_f80.
2010 bool ConstantDataSequential::isElementTypeCompatible(const Type *Ty) {
2011   if (Ty->isFloatTy() || Ty->isDoubleTy()) return true;
2012   if (const IntegerType *IT = dyn_cast<IntegerType>(Ty)) {
2013     switch (IT->getBitWidth()) {
2014     case 8:
2015     case 16:
2016     case 32:
2017     case 64:
2018       return true;
2019     default: break;
2020     }
2021   }
2022   return false;
2023 }
2024
2025 /// getNumElements - Return the number of elements in the array or vector.
2026 unsigned ConstantDataSequential::getNumElements() const {
2027   if (ArrayType *AT = dyn_cast<ArrayType>(getType()))
2028     return AT->getNumElements();
2029   return cast<VectorType>(getType())->getNumElements();
2030 }
2031
2032
2033 /// getElementByteSize - Return the size in bytes of the elements in the data.
2034 uint64_t ConstantDataSequential::getElementByteSize() const {
2035   return getElementType()->getPrimitiveSizeInBits()/8;
2036 }
2037
2038 /// getElementPointer - Return the start of the specified element.
2039 const char *ConstantDataSequential::getElementPointer(unsigned Elt) const {
2040   assert(Elt < getNumElements() && "Invalid Elt");
2041   return DataElements+Elt*getElementByteSize();
2042 }
2043
2044
2045 /// isAllZeros - return true if the array is empty or all zeros.
2046 static bool isAllZeros(StringRef Arr) {
2047   for (StringRef::iterator I = Arr.begin(), E = Arr.end(); I != E; ++I)
2048     if (*I != 0)
2049       return false;
2050   return true;
2051 }
2052
2053 /// getImpl - This is the underlying implementation of all of the
2054 /// ConstantDataSequential::get methods.  They all thunk down to here, providing
2055 /// the correct element type.  We take the bytes in as an StringRef because
2056 /// we *want* an underlying "char*" to avoid TBAA type punning violations.
2057 Constant *ConstantDataSequential::getImpl(StringRef Elements, Type *Ty) {
2058   assert(isElementTypeCompatible(cast<SequentialType>(Ty)->getElementType()));
2059   // If the elements are all zero or there are no elements, return a CAZ, which
2060   // is more dense and canonical.
2061   if (isAllZeros(Elements))
2062     return ConstantAggregateZero::get(Ty);
2063
2064   // Do a lookup to see if we have already formed one of these.
2065   StringMap<ConstantDataSequential*>::MapEntryTy &Slot =
2066     Ty->getContext().pImpl->CDSConstants.GetOrCreateValue(Elements);
2067
2068   // The bucket can point to a linked list of different CDS's that have the same
2069   // body but different types.  For example, 0,0,0,1 could be a 4 element array
2070   // of i8, or a 1-element array of i32.  They'll both end up in the same
2071   /// StringMap bucket, linked up by their Next pointers.  Walk the list.
2072   ConstantDataSequential **Entry = &Slot.getValue();
2073   for (ConstantDataSequential *Node = *Entry; Node != 0;
2074        Entry = &Node->Next, Node = *Entry)
2075     if (Node->getType() == Ty)
2076       return Node;
2077
2078   // Okay, we didn't get a hit.  Create a node of the right class, link it in,
2079   // and return it.
2080   if (isa<ArrayType>(Ty))
2081     return *Entry = new ConstantDataArray(Ty, Slot.getKeyData());
2082
2083   assert(isa<VectorType>(Ty));
2084   return *Entry = new ConstantDataVector(Ty, Slot.getKeyData());
2085 }
2086
2087 void ConstantDataSequential::destroyConstant() {
2088   // Remove the constant from the StringMap.
2089   StringMap<ConstantDataSequential*> &CDSConstants =
2090     getType()->getContext().pImpl->CDSConstants;
2091
2092   StringMap<ConstantDataSequential*>::iterator Slot =
2093     CDSConstants.find(getRawDataValues());
2094
2095   assert(Slot != CDSConstants.end() && "CDS not found in uniquing table");
2096
2097   ConstantDataSequential **Entry = &Slot->getValue();
2098
2099   // Remove the entry from the hash table.
2100   if ((*Entry)->Next == 0) {
2101     // If there is only one value in the bucket (common case) it must be this
2102     // entry, and removing the entry should remove the bucket completely.
2103     assert((*Entry) == this && "Hash mismatch in ConstantDataSequential");
2104     getContext().pImpl->CDSConstants.erase(Slot);
2105   } else {
2106     // Otherwise, there are multiple entries linked off the bucket, unlink the
2107     // node we care about but keep the bucket around.
2108     for (ConstantDataSequential *Node = *Entry; ;
2109          Entry = &Node->Next, Node = *Entry) {
2110       assert(Node && "Didn't find entry in its uniquing hash table!");
2111       // If we found our entry, unlink it from the list and we're done.
2112       if (Node == this) {
2113         *Entry = Node->Next;
2114         break;
2115       }
2116     }
2117   }
2118
2119   // If we were part of a list, make sure that we don't delete the list that is
2120   // still owned by the uniquing map.
2121   Next = 0;
2122
2123   // Finally, actually delete it.
2124   destroyConstantImpl();
2125 }
2126
2127 /// get() constructors - Return a constant with array type with an element
2128 /// count and element type matching the ArrayRef passed in.  Note that this
2129 /// can return a ConstantAggregateZero object.
2130 Constant *ConstantDataArray::get(LLVMContext &Context, ArrayRef<uint8_t> Elts) {
2131   Type *Ty = ArrayType::get(Type::getInt8Ty(Context), Elts.size());
2132   return getImpl(StringRef((char*)Elts.data(), Elts.size()*1), Ty);
2133 }
2134 Constant *ConstantDataArray::get(LLVMContext &Context, ArrayRef<uint16_t> Elts){
2135   Type *Ty = ArrayType::get(Type::getInt16Ty(Context), Elts.size());
2136   return getImpl(StringRef((char*)Elts.data(), Elts.size()*2), Ty);
2137 }
2138 Constant *ConstantDataArray::get(LLVMContext &Context, ArrayRef<uint32_t> Elts){
2139   Type *Ty = ArrayType::get(Type::getInt32Ty(Context), Elts.size());
2140   return getImpl(StringRef((char*)Elts.data(), Elts.size()*4), Ty);
2141 }
2142 Constant *ConstantDataArray::get(LLVMContext &Context, ArrayRef<uint64_t> Elts){
2143   Type *Ty = ArrayType::get(Type::getInt64Ty(Context), Elts.size());
2144   return getImpl(StringRef((char*)Elts.data(), Elts.size()*8), Ty);
2145 }
2146 Constant *ConstantDataArray::get(LLVMContext &Context, ArrayRef<float> Elts) {
2147   Type *Ty = ArrayType::get(Type::getFloatTy(Context), Elts.size());
2148   return getImpl(StringRef((char*)Elts.data(), Elts.size()*4), Ty);
2149 }
2150 Constant *ConstantDataArray::get(LLVMContext &Context, ArrayRef<double> Elts) {
2151   Type *Ty = ArrayType::get(Type::getDoubleTy(Context), Elts.size());
2152   return getImpl(StringRef((char*)Elts.data(), Elts.size()*8), Ty);
2153 }
2154
2155 /// getString - This method constructs a CDS and initializes it with a text
2156 /// string. The default behavior (AddNull==true) causes a null terminator to
2157 /// be placed at the end of the array (increasing the length of the string by
2158 /// one more than the StringRef would normally indicate.  Pass AddNull=false
2159 /// to disable this behavior.
2160 Constant *ConstantDataArray::getString(LLVMContext &Context,
2161                                        StringRef Str, bool AddNull) {
2162   if (!AddNull)
2163     return get(Context, ArrayRef<uint8_t>((uint8_t*)Str.data(), Str.size()));
2164
2165   SmallVector<uint8_t, 64> ElementVals;
2166   ElementVals.append(Str.begin(), Str.end());
2167   ElementVals.push_back(0);
2168   return get(Context, ElementVals);
2169 }
2170
2171 /// get() constructors - Return a constant with vector type with an element
2172 /// count and element type matching the ArrayRef passed in.  Note that this
2173 /// can return a ConstantAggregateZero object.
2174 Constant *ConstantDataVector::get(LLVMContext &Context, ArrayRef<uint8_t> Elts){
2175   Type *Ty = VectorType::get(Type::getInt8Ty(Context), Elts.size());
2176   return getImpl(StringRef((char*)Elts.data(), Elts.size()*1), Ty);
2177 }
2178 Constant *ConstantDataVector::get(LLVMContext &Context, ArrayRef<uint16_t> Elts){
2179   Type *Ty = VectorType::get(Type::getInt16Ty(Context), Elts.size());
2180   return getImpl(StringRef((char*)Elts.data(), Elts.size()*2), Ty);
2181 }
2182 Constant *ConstantDataVector::get(LLVMContext &Context, ArrayRef<uint32_t> Elts){
2183   Type *Ty = VectorType::get(Type::getInt32Ty(Context), Elts.size());
2184   return getImpl(StringRef((char*)Elts.data(), Elts.size()*4), Ty);
2185 }
2186 Constant *ConstantDataVector::get(LLVMContext &Context, ArrayRef<uint64_t> Elts){
2187   Type *Ty = VectorType::get(Type::getInt64Ty(Context), Elts.size());
2188   return getImpl(StringRef((char*)Elts.data(), Elts.size()*8), Ty);
2189 }
2190 Constant *ConstantDataVector::get(LLVMContext &Context, ArrayRef<float> Elts) {
2191   Type *Ty = VectorType::get(Type::getFloatTy(Context), Elts.size());
2192   return getImpl(StringRef((char*)Elts.data(), Elts.size()*4), Ty);
2193 }
2194 Constant *ConstantDataVector::get(LLVMContext &Context, ArrayRef<double> Elts) {
2195   Type *Ty = VectorType::get(Type::getDoubleTy(Context), Elts.size());
2196   return getImpl(StringRef((char*)Elts.data(), Elts.size()*8), Ty);
2197 }
2198
2199 /// getElementAsInteger - If this is a sequential container of integers (of
2200 /// any size), return the specified element in the low bits of a uint64_t.
2201 uint64_t ConstantDataSequential::getElementAsInteger(unsigned Elt) const {
2202   assert(isa<IntegerType>(getElementType()) &&
2203          "Accessor can only be used when element is an integer");
2204   const char *EltPtr = getElementPointer(Elt);
2205
2206   // The data is stored in host byte order, make sure to cast back to the right
2207   // type to load with the right endianness.
2208   switch (cast<IntegerType>(getElementType())->getBitWidth()) {
2209   default: assert(0 && "Invalid bitwidth for CDS");
2210   case 8:  return *(uint8_t*)EltPtr;
2211   case 16: return *(uint16_t*)EltPtr;
2212   case 32: return *(uint32_t*)EltPtr;
2213   case 64: return *(uint64_t*)EltPtr;
2214   }
2215 }
2216
2217 /// getElementAsAPFloat - If this is a sequential container of floating point
2218 /// type, return the specified element as an APFloat.
2219 APFloat ConstantDataSequential::getElementAsAPFloat(unsigned Elt) const {
2220   const char *EltPtr = getElementPointer(Elt);
2221
2222   switch (getElementType()->getTypeID()) {
2223   default:
2224     assert(0 && "Accessor can only be used when element is float/double!");
2225   case Type::FloatTyID: return APFloat(*(float*)EltPtr);
2226   case Type::DoubleTyID: return APFloat(*(double*)EltPtr);
2227   }
2228 }
2229
2230 /// getElementAsFloat - If this is an sequential container of floats, return
2231 /// the specified element as a float.
2232 float ConstantDataSequential::getElementAsFloat(unsigned Elt) const {
2233   assert(getElementType()->isFloatTy() &&
2234          "Accessor can only be used when element is a 'float'");
2235   return *(float*)getElementPointer(Elt);
2236 }
2237
2238 /// getElementAsDouble - If this is an sequential container of doubles, return
2239 /// the specified element as a float.
2240 double ConstantDataSequential::getElementAsDouble(unsigned Elt) const {
2241   assert(getElementType()->isDoubleTy() &&
2242          "Accessor can only be used when element is a 'float'");
2243   return *(double*)getElementPointer(Elt);
2244 }
2245
2246 /// getElementAsConstant - Return a Constant for a specified index's element.
2247 /// Note that this has to compute a new constant to return, so it isn't as
2248 /// efficient as getElementAsInteger/Float/Double.
2249 Constant *ConstantDataSequential::getElementAsConstant(unsigned Elt) const {
2250   if (getElementType()->isFloatTy() || getElementType()->isDoubleTy())
2251     return ConstantFP::get(getContext(), getElementAsAPFloat(Elt));
2252
2253   return ConstantInt::get(getElementType(), getElementAsInteger(Elt));
2254 }
2255
2256 /// isString - This method returns true if this is an array of i8.
2257 bool ConstantDataSequential::isString() const {
2258   return isa<ArrayType>(getType()) && getElementType()->isIntegerTy(8);
2259 }
2260
2261 /// isCString - This method returns true if the array "isString", ends with a
2262 /// nul byte, and does not contains any other nul bytes.
2263 bool ConstantDataSequential::isCString() const {
2264   if (!isString())
2265     return false;
2266
2267   StringRef Str = getAsString();
2268
2269   // The last value must be nul.
2270   if (Str.back() != 0) return false;
2271
2272   // Other elements must be non-nul.
2273   return Str.drop_back().find(0) == StringRef::npos;
2274 }
2275
2276
2277 //===----------------------------------------------------------------------===//
2278 //                replaceUsesOfWithOnConstant implementations
2279
2280 /// replaceUsesOfWithOnConstant - Update this constant array to change uses of
2281 /// 'From' to be uses of 'To'.  This must update the uniquing data structures
2282 /// etc.
2283 ///
2284 /// Note that we intentionally replace all uses of From with To here.  Consider
2285 /// a large array that uses 'From' 1000 times.  By handling this case all here,
2286 /// ConstantArray::replaceUsesOfWithOnConstant is only invoked once, and that
2287 /// single invocation handles all 1000 uses.  Handling them one at a time would
2288 /// work, but would be really slow because it would have to unique each updated
2289 /// array instance.
2290 ///
2291 void ConstantArray::replaceUsesOfWithOnConstant(Value *From, Value *To,
2292                                                 Use *U) {
2293   assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
2294   Constant *ToC = cast<Constant>(To);
2295
2296   LLVMContextImpl *pImpl = getType()->getContext().pImpl;
2297
2298   std::pair<LLVMContextImpl::ArrayConstantsTy::MapKey, ConstantArray*> Lookup;
2299   Lookup.first.first = cast<ArrayType>(getType());
2300   Lookup.second = this;
2301
2302   std::vector<Constant*> &Values = Lookup.first.second;
2303   Values.reserve(getNumOperands());  // Build replacement array.
2304
2305   // Fill values with the modified operands of the constant array.  Also,
2306   // compute whether this turns into an all-zeros array.
2307   bool isAllZeros = false;
2308   unsigned NumUpdated = 0;
2309   if (!ToC->isNullValue()) {
2310     for (Use *O = OperandList, *E = OperandList+getNumOperands(); O != E; ++O) {
2311       Constant *Val = cast<Constant>(O->get());
2312       if (Val == From) {
2313         Val = ToC;
2314         ++NumUpdated;
2315       }
2316       Values.push_back(Val);
2317     }
2318   } else {
2319     isAllZeros = true;
2320     for (Use *O = OperandList, *E = OperandList+getNumOperands();O != E; ++O) {
2321       Constant *Val = cast<Constant>(O->get());
2322       if (Val == From) {
2323         Val = ToC;
2324         ++NumUpdated;
2325       }
2326       Values.push_back(Val);
2327       if (isAllZeros) isAllZeros = Val->isNullValue();
2328     }
2329   }
2330
2331   Constant *Replacement = 0;
2332   if (isAllZeros) {
2333     Replacement = ConstantAggregateZero::get(getType());
2334   } else {
2335     // Check to see if we have this array type already.
2336     bool Exists;
2337     LLVMContextImpl::ArrayConstantsTy::MapTy::iterator I =
2338       pImpl->ArrayConstants.InsertOrGetItem(Lookup, Exists);
2339
2340     if (Exists) {
2341       Replacement = I->second;
2342     } else {
2343       // Okay, the new shape doesn't exist in the system yet.  Instead of
2344       // creating a new constant array, inserting it, replaceallusesof'ing the
2345       // old with the new, then deleting the old... just update the current one
2346       // in place!
2347       pImpl->ArrayConstants.MoveConstantToNewSlot(this, I);
2348
2349       // Update to the new value.  Optimize for the case when we have a single
2350       // operand that we're changing, but handle bulk updates efficiently.
2351       if (NumUpdated == 1) {
2352         unsigned OperandToUpdate = U - OperandList;
2353         assert(getOperand(OperandToUpdate) == From &&
2354                "ReplaceAllUsesWith broken!");
2355         setOperand(OperandToUpdate, ToC);
2356       } else {
2357         for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
2358           if (getOperand(i) == From)
2359             setOperand(i, ToC);
2360       }
2361       return;
2362     }
2363   }
2364
2365   // Otherwise, I do need to replace this with an existing value.
2366   assert(Replacement != this && "I didn't contain From!");
2367
2368   // Everyone using this now uses the replacement.
2369   replaceAllUsesWith(Replacement);
2370
2371   // Delete the old constant!
2372   destroyConstant();
2373 }
2374
2375 void ConstantStruct::replaceUsesOfWithOnConstant(Value *From, Value *To,
2376                                                  Use *U) {
2377   assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
2378   Constant *ToC = cast<Constant>(To);
2379
2380   unsigned OperandToUpdate = U-OperandList;
2381   assert(getOperand(OperandToUpdate) == From && "ReplaceAllUsesWith broken!");
2382
2383   std::pair<LLVMContextImpl::StructConstantsTy::MapKey, ConstantStruct*> Lookup;
2384   Lookup.first.first = cast<StructType>(getType());
2385   Lookup.second = this;
2386   std::vector<Constant*> &Values = Lookup.first.second;
2387   Values.reserve(getNumOperands());  // Build replacement struct.
2388
2389
2390   // Fill values with the modified operands of the constant struct.  Also,
2391   // compute whether this turns into an all-zeros struct.
2392   bool isAllZeros = false;
2393   if (!ToC->isNullValue()) {
2394     for (Use *O = OperandList, *E = OperandList + getNumOperands(); O != E; ++O)
2395       Values.push_back(cast<Constant>(O->get()));
2396   } else {
2397     isAllZeros = true;
2398     for (Use *O = OperandList, *E = OperandList+getNumOperands(); O != E; ++O) {
2399       Constant *Val = cast<Constant>(O->get());
2400       Values.push_back(Val);
2401       if (isAllZeros) isAllZeros = Val->isNullValue();
2402     }
2403   }
2404   Values[OperandToUpdate] = ToC;
2405
2406   LLVMContextImpl *pImpl = getContext().pImpl;
2407
2408   Constant *Replacement = 0;
2409   if (isAllZeros) {
2410     Replacement = ConstantAggregateZero::get(getType());
2411   } else {
2412     // Check to see if we have this struct type already.
2413     bool Exists;
2414     LLVMContextImpl::StructConstantsTy::MapTy::iterator I =
2415       pImpl->StructConstants.InsertOrGetItem(Lookup, Exists);
2416
2417     if (Exists) {
2418       Replacement = I->second;
2419     } else {
2420       // Okay, the new shape doesn't exist in the system yet.  Instead of
2421       // creating a new constant struct, inserting it, replaceallusesof'ing the
2422       // old with the new, then deleting the old... just update the current one
2423       // in place!
2424       pImpl->StructConstants.MoveConstantToNewSlot(this, I);
2425
2426       // Update to the new value.
2427       setOperand(OperandToUpdate, ToC);
2428       return;
2429     }
2430   }
2431
2432   assert(Replacement != this && "I didn't contain From!");
2433
2434   // Everyone using this now uses the replacement.
2435   replaceAllUsesWith(Replacement);
2436
2437   // Delete the old constant!
2438   destroyConstant();
2439 }
2440
2441 void ConstantVector::replaceUsesOfWithOnConstant(Value *From, Value *To,
2442                                                  Use *U) {
2443   assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
2444
2445   std::vector<Constant*> Values;
2446   Values.reserve(getNumOperands());  // Build replacement array...
2447   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
2448     Constant *Val = getOperand(i);
2449     if (Val == From) Val = cast<Constant>(To);
2450     Values.push_back(Val);
2451   }
2452
2453   Constant *Replacement = get(Values);
2454   assert(Replacement != this && "I didn't contain From!");
2455
2456   // Everyone using this now uses the replacement.
2457   replaceAllUsesWith(Replacement);
2458
2459   // Delete the old constant!
2460   destroyConstant();
2461 }
2462
2463 void ConstantExpr::replaceUsesOfWithOnConstant(Value *From, Value *ToV,
2464                                                Use *U) {
2465   assert(isa<Constant>(ToV) && "Cannot make Constant refer to non-constant!");
2466   Constant *To = cast<Constant>(ToV);
2467
2468   Constant *Replacement = 0;
2469   if (getOpcode() == Instruction::GetElementPtr) {
2470     SmallVector<Constant*, 8> Indices;
2471     Constant *Pointer = getOperand(0);
2472     Indices.reserve(getNumOperands()-1);
2473     if (Pointer == From) Pointer = To;
2474
2475     for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
2476       Constant *Val = getOperand(i);
2477       if (Val == From) Val = To;
2478       Indices.push_back(Val);
2479     }
2480     Replacement = ConstantExpr::getGetElementPtr(Pointer, Indices,
2481                                          cast<GEPOperator>(this)->isInBounds());
2482   } else if (getOpcode() == Instruction::ExtractValue) {
2483     Constant *Agg = getOperand(0);
2484     if (Agg == From) Agg = To;
2485
2486     ArrayRef<unsigned> Indices = getIndices();
2487     Replacement = ConstantExpr::getExtractValue(Agg, Indices);
2488   } else if (getOpcode() == Instruction::InsertValue) {
2489     Constant *Agg = getOperand(0);
2490     Constant *Val = getOperand(1);
2491     if (Agg == From) Agg = To;
2492     if (Val == From) Val = To;
2493
2494     ArrayRef<unsigned> Indices = getIndices();
2495     Replacement = ConstantExpr::getInsertValue(Agg, Val, Indices);
2496   } else if (isCast()) {
2497     assert(getOperand(0) == From && "Cast only has one use!");
2498     Replacement = ConstantExpr::getCast(getOpcode(), To, getType());
2499   } else if (getOpcode() == Instruction::Select) {
2500     Constant *C1 = getOperand(0);
2501     Constant *C2 = getOperand(1);
2502     Constant *C3 = getOperand(2);
2503     if (C1 == From) C1 = To;
2504     if (C2 == From) C2 = To;
2505     if (C3 == From) C3 = To;
2506     Replacement = ConstantExpr::getSelect(C1, C2, C3);
2507   } else if (getOpcode() == Instruction::ExtractElement) {
2508     Constant *C1 = getOperand(0);
2509     Constant *C2 = getOperand(1);
2510     if (C1 == From) C1 = To;
2511     if (C2 == From) C2 = To;
2512     Replacement = ConstantExpr::getExtractElement(C1, C2);
2513   } else if (getOpcode() == Instruction::InsertElement) {
2514     Constant *C1 = getOperand(0);
2515     Constant *C2 = getOperand(1);
2516     Constant *C3 = getOperand(1);
2517     if (C1 == From) C1 = To;
2518     if (C2 == From) C2 = To;
2519     if (C3 == From) C3 = To;
2520     Replacement = ConstantExpr::getInsertElement(C1, C2, C3);
2521   } else if (getOpcode() == Instruction::ShuffleVector) {
2522     Constant *C1 = getOperand(0);
2523     Constant *C2 = getOperand(1);
2524     Constant *C3 = getOperand(2);
2525     if (C1 == From) C1 = To;
2526     if (C2 == From) C2 = To;
2527     if (C3 == From) C3 = To;
2528     Replacement = ConstantExpr::getShuffleVector(C1, C2, C3);
2529   } else if (isCompare()) {
2530     Constant *C1 = getOperand(0);
2531     Constant *C2 = getOperand(1);
2532     if (C1 == From) C1 = To;
2533     if (C2 == From) C2 = To;
2534     if (getOpcode() == Instruction::ICmp)
2535       Replacement = ConstantExpr::getICmp(getPredicate(), C1, C2);
2536     else {
2537       assert(getOpcode() == Instruction::FCmp);
2538       Replacement = ConstantExpr::getFCmp(getPredicate(), C1, C2);
2539     }
2540   } else if (getNumOperands() == 2) {
2541     Constant *C1 = getOperand(0);
2542     Constant *C2 = getOperand(1);
2543     if (C1 == From) C1 = To;
2544     if (C2 == From) C2 = To;
2545     Replacement = ConstantExpr::get(getOpcode(), C1, C2, SubclassOptionalData);
2546   } else {
2547     llvm_unreachable("Unknown ConstantExpr type!");
2548   }
2549
2550   assert(Replacement != this && "I didn't contain From!");
2551
2552   // Everyone using this now uses the replacement.
2553   replaceAllUsesWith(Replacement);
2554
2555   // Delete the old constant!
2556   destroyConstant();
2557 }