lib/VMCore/Constants.cpp

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