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