lib/VMCore/Constants.cpp

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