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