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