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