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/SymbolTable.h"
  20 #include "llvm/Module.h"
  21 #include "llvm/ADT/StringExtras.h"
  22 #include <algorithm>
  23 #include <iostream>
  24 using namespace llvm;
  25
  26 ConstantBool *ConstantBool::True  = new ConstantBool(true);
  27 ConstantBool *ConstantBool::False = new ConstantBool(false);
  28
  29
  30 //===----------------------------------------------------------------------===//
  31 //                              Constant Class
  32 //===----------------------------------------------------------------------===//
  33
  34 // Specialize setName to take care of symbol table majik
  35 void Constant::setName(const std::string &Name, SymbolTable *ST) {
  36   assert(ST && "Type::setName - Must provide symbol table argument!");
  37
  38   if (Name.size()) ST->insert(Name, this);
  39 }
  40
  41 void Constant::destroyConstantImpl() {
  42   // When a Constant is destroyed, there may be lingering
  43   // references to the constant by other constants in the constant pool.  These
  44   // constants are implicitly dependent on the module that is being deleted,
  45   // but they don't know that.  Because we only find out when the CPV is
  46   // deleted, we must now notify all of our users (that should only be
  47   // Constants) that they are, in fact, invalid now and should be deleted.
  48   //
  49   while (!use_empty()) {
  50     Value *V = use_back();
  51 #ifndef NDEBUG      // Only in -g mode...
  52     if (!isa<Constant>(V))
  53       std::cerr << "While deleting: " << *this
  54                 << "\n\nUse still stuck around after Def is destroyed: "
  55                 << *V << "\n\n";
  56 #endif
  57     assert(isa<Constant>(V) && "References remain to Constant being destroyed");
  58     Constant *CV = cast<Constant>(V);
  59     CV->destroyConstant();
  60
  61     // The constant should remove itself from our use list...
  62     assert((use_empty() || use_back() != V) && "Constant not removed!");
  63   }
  64
  65   // Value has no outstanding references it is safe to delete it now...
  66   delete this;
  67 }
  68
  69 // Static constructor to create a '0' constant of arbitrary type...
  70 Constant *Constant::getNullValue(const Type *Ty) {
  71   switch (Ty->getTypeID()) {
  72   case Type::BoolTyID: {
  73     static Constant *NullBool = ConstantBool::get(false);
  74     return NullBool;
  75   }
  76   case Type::SByteTyID: {
  77     static Constant *NullSByte = ConstantSInt::get(Type::SByteTy, 0);
  78     return NullSByte;
  79   }
  80   case Type::UByteTyID: {
  81     static Constant *NullUByte = ConstantUInt::get(Type::UByteTy, 0);
  82     return NullUByte;
  83   }
  84   case Type::ShortTyID: {
  85     static Constant *NullShort = ConstantSInt::get(Type::ShortTy, 0);
  86     return NullShort;
  87   }
  88   case Type::UShortTyID: {
  89     static Constant *NullUShort = ConstantUInt::get(Type::UShortTy, 0);
  90     return NullUShort;
  91   }
  92   case Type::IntTyID: {
  93     static Constant *NullInt = ConstantSInt::get(Type::IntTy, 0);
  94     return NullInt;
  95   }
  96   case Type::UIntTyID: {
  97     static Constant *NullUInt = ConstantUInt::get(Type::UIntTy, 0);
  98     return NullUInt;
  99   }
 100   case Type::LongTyID: {
 101     static Constant *NullLong = ConstantSInt::get(Type::LongTy, 0);
 102     return NullLong;
 103   }
 104   case Type::ULongTyID: {
 105     static Constant *NullULong = ConstantUInt::get(Type::ULongTy, 0);
 106     return NullULong;
 107   }
 108
 109   case Type::FloatTyID: {
 110     static Constant *NullFloat = ConstantFP::get(Type::FloatTy, 0);
 111     return NullFloat;
 112   }
 113   case Type::DoubleTyID: {
 114     static Constant *NullDouble = ConstantFP::get(Type::DoubleTy, 0);
 115     return NullDouble;
 116   }
 117
 118   case Type::PointerTyID:
 119     return ConstantPointerNull::get(cast<PointerType>(Ty));
 120
 121   case Type::StructTyID:
 122   case Type::ArrayTyID:
 123   case Type::PackedTyID:
 124     return ConstantAggregateZero::get(Ty);
 125   default:
 126     // Function, Label, or Opaque type?
 127     assert(!"Cannot create a null constant of that type!");
 128     return 0;
 129   }
 130 }
 131
 132 // Static constructor to create the maximum constant of an integral type...
 133 ConstantIntegral *ConstantIntegral::getMaxValue(const Type *Ty) {
 134   switch (Ty->getTypeID()) {
 135   case Type::BoolTyID:   return ConstantBool::True;
 136   case Type::SByteTyID:
 137   case Type::ShortTyID:
 138   case Type::IntTyID:
 139   case Type::LongTyID: {
 140     // Calculate 011111111111111...
 141     unsigned TypeBits = Ty->getPrimitiveSize()*8;
 142     int64_t Val = INT64_MAX;             // All ones
 143     Val >>= 64-TypeBits;                 // Shift out unwanted 1 bits...
 144     return ConstantSInt::get(Ty, Val);
 145   }
 146
 147   case Type::UByteTyID:
 148   case Type::UShortTyID:
 149   case Type::UIntTyID:
 150   case Type::ULongTyID:  return getAllOnesValue(Ty);
 151
 152   default: return 0;
 153   }
 154 }
 155
 156 // Static constructor to create the minimum constant for an integral type...
 157 ConstantIntegral *ConstantIntegral::getMinValue(const Type *Ty) {
 158   switch (Ty->getTypeID()) {
 159   case Type::BoolTyID:   return ConstantBool::False;
 160   case Type::SByteTyID:
 161   case Type::ShortTyID:
 162   case Type::IntTyID:
 163   case Type::LongTyID: {
 164      // Calculate 1111111111000000000000
 165      unsigned TypeBits = Ty->getPrimitiveSize()*8;
 166      int64_t Val = -1;                    // All ones
 167      Val <<= TypeBits-1;                  // Shift over to the right spot
 168      return ConstantSInt::get(Ty, Val);
 169   }
 170
 171   case Type::UByteTyID:
 172   case Type::UShortTyID:
 173   case Type::UIntTyID:
 174   case Type::ULongTyID:  return ConstantUInt::get(Ty, 0);
 175
 176   default: return 0;
 177   }
 178 }
 179
 180 // Static constructor to create an integral constant with all bits set
 181 ConstantIntegral *ConstantIntegral::getAllOnesValue(const Type *Ty) {
 182   switch (Ty->getTypeID()) {
 183   case Type::BoolTyID:   return ConstantBool::True;
 184   case Type::SByteTyID:
 185   case Type::ShortTyID:
 186   case Type::IntTyID:
 187   case Type::LongTyID:   return ConstantSInt::get(Ty, -1);
 188
 189   case Type::UByteTyID:
 190   case Type::UShortTyID:
 191   case Type::UIntTyID:
 192   case Type::ULongTyID: {
 193     // Calculate ~0 of the right type...
 194     unsigned TypeBits = Ty->getPrimitiveSize()*8;
 195     uint64_t Val = ~0ULL;                // All ones
 196     Val >>= 64-TypeBits;                 // Shift out unwanted 1 bits...
 197     return ConstantUInt::get(Ty, Val);
 198   }
 199   default: return 0;
 200   }
 201 }
 202
 203 bool ConstantUInt::isAllOnesValue() const {
 204   unsigned TypeBits = getType()->getPrimitiveSize()*8;
 205   uint64_t Val = ~0ULL;                // All ones
 206   Val >>= 64-TypeBits;                 // Shift out inappropriate bits
 207   return getValue() == Val;
 208 }
 209
 210
 211 //===----------------------------------------------------------------------===//
 212 //                            ConstantXXX Classes
 213 //===----------------------------------------------------------------------===//
 214
 215 //===----------------------------------------------------------------------===//
 216 //                             Normal Constructors
 217
 218 ConstantIntegral::ConstantIntegral(const Type *Ty, uint64_t V)
 219   : Constant(Ty, SimpleConstantVal, 0, 0) {
 220     Val.Unsigned = V;
 221 }
 222
 223 ConstantBool::ConstantBool(bool V) : ConstantIntegral(Type::BoolTy, V) {
 224 }
 225
 226 ConstantInt::ConstantInt(const Type *Ty, uint64_t V) : ConstantIntegral(Ty, V) {
 227 }
 228
 229 ConstantSInt::ConstantSInt(const Type *Ty, int64_t V) : ConstantInt(Ty, V) {
 230   assert(Ty->isInteger() && Ty->isSigned() &&
 231          "Illegal type for unsigned integer constant!");
 232   assert(isValueValidForType(Ty, V) && "Value too large for type!");
 233 }
 234
 235 ConstantUInt::ConstantUInt(const Type *Ty, uint64_t V) : ConstantInt(Ty, V) {
 236   assert(Ty->isInteger() && Ty->isUnsigned() &&
 237          "Illegal type for unsigned integer constant!");
 238   assert(isValueValidForType(Ty, V) && "Value too large for type!");
 239 }
 240
 241 ConstantFP::ConstantFP(const Type *Ty, double V)
 242   : Constant(Ty, SimpleConstantVal, 0, 0) {
 243   assert(isValueValidForType(Ty, V) && "Value too large for type!");
 244   Val = V;
 245 }
 246
 247 ConstantArray::ConstantArray(const ArrayType *T,
 248                              const std::vector<Constant*> &V)
 249   : Constant(T, SimpleConstantVal, new Use[V.size()], V.size()) {
 250   assert(V.size() == T->getNumElements() &&
 251          "Invalid initializer vector for constant array");
 252   Use *OL = OperandList;
 253   for (unsigned i = 0, e = V.size(); i != e; ++i) {
 254     assert((V[i]->getType() == T->getElementType() ||
 255             (T->isAbstract() &&
 256              V[i]->getType()->getTypeID()==T->getElementType()->getTypeID())) &&
 257            "Initializer for array element doesn't match array element type!");
 258     OL[i].init(V[i], this);
 259   }
 260 }
 261
 262 ConstantArray::~ConstantArray() {
 263   delete [] OperandList;
 264 }
 265
 266 ConstantStruct::ConstantStruct(const StructType *T,
 267                                const std::vector<Constant*> &V)
 268   : Constant(T, SimpleConstantVal, new Use[V.size()], V.size()) {
 269   assert(V.size() == T->getNumElements() &&
 270          "Invalid initializer vector for constant structure");
 271   Use *OL = OperandList;
 272   for (unsigned i = 0, e = V.size(); i != e; ++i) {
 273     assert((V[i]->getType() == T->getElementType(i) ||
 274             ((T->getElementType(i)->isAbstract() ||
 275               V[i]->getType()->isAbstract()) &&
 276              T->getElementType(i)->getTypeID()==V[i]->getType()->getTypeID()))&&
 277            "Initializer for struct element doesn't match struct element type!");
 278     OL[i].init(V[i], this);
 279   }
 280 }
 281
 282 ConstantStruct::~ConstantStruct() {
 283   delete [] OperandList;
 284 }
 285
 286
 287 ConstantPacked::ConstantPacked(const PackedType *T,
 288                                const std::vector<Constant*> &V)
 289   : Constant(T, SimpleConstantVal, new Use[V.size()], V.size()) {
 290   Use *OL = OperandList;
 291   for (unsigned i = 0, e = V.size(); i != e; ++i) {
 292     assert((V[i]->getType() == T->getElementType() ||
 293             (T->isAbstract() &&
 294              V[i]->getType()->getTypeID()==T->getElementType()->getTypeID())) &&
 295            "Initializer for packed element doesn't match packed element type!");
 296     OL[i].init(V[i], this);
 297   }
 298 }
 299
 300 ConstantPacked::~ConstantPacked() {
 301   delete [] OperandList;
 302 }
 303
 304 /// UnaryConstantExpr - This class is private to Constants.cpp, and is used
 305 /// behind the scenes to implement unary constant exprs.
 306 class UnaryConstantExpr : public ConstantExpr {
 307   Use Op;
 308 public:
 309   UnaryConstantExpr(unsigned Opcode, Constant *C, const Type *Ty)
 310     : ConstantExpr(Ty, Opcode, &Op, 1), Op(C, this) {}
 311 };
 312
 313 static bool isSetCC(unsigned Opcode) {
 314   return Opcode == Instruction::SetEQ || Opcode == Instruction::SetNE ||
 315          Opcode == Instruction::SetLT || Opcode == Instruction::SetGT ||
 316          Opcode == Instruction::SetLE || Opcode == Instruction::SetGE;
 317 }
 318
 319 /// BinaryConstantExpr - This class is private to Constants.cpp, and is used
 320 /// behind the scenes to implement binary constant exprs.
 321 class BinaryConstantExpr : public ConstantExpr {
 322   Use Ops[2];
 323 public:
 324   BinaryConstantExpr(unsigned Opcode, Constant *C1, Constant *C2)
 325     : ConstantExpr(isSetCC(Opcode) ? Type::BoolTy : C1->getType(),
 326                    Opcode, Ops, 2) {
 327     Ops[0].init(C1, this);
 328     Ops[1].init(C2, this);
 329   }
 330 };
 331
 332 /// SelectConstantExpr - This class is private to Constants.cpp, and is used
 333 /// behind the scenes to implement select constant exprs.
 334 class SelectConstantExpr : public ConstantExpr {
 335   Use Ops[3];
 336 public:
 337   SelectConstantExpr(Constant *C1, Constant *C2, Constant *C3)
 338     : ConstantExpr(C2->getType(), Instruction::Select, Ops, 3) {
 339     Ops[0].init(C1, this);
 340     Ops[1].init(C2, this);
 341     Ops[2].init(C3, this);
 342   }
 343 };
 344
 345 /// GetElementPtrConstantExpr - This class is private to Constants.cpp, and is
 346 /// used behind the scenes to implement getelementpr constant exprs.
 347 struct GetElementPtrConstantExpr : public ConstantExpr {
 348   GetElementPtrConstantExpr(Constant *C, const std::vector<Constant*> &IdxList,
 349                             const Type *DestTy)
 350     : ConstantExpr(DestTy, Instruction::GetElementPtr,
 351                    new Use[IdxList.size()+1], IdxList.size()+1) {
 352     OperandList[0].init(C, this);
 353     for (unsigned i = 0, E = IdxList.size(); i != E; ++i)
 354       OperandList[i+1].init(IdxList[i], this);
 355   }
 356   ~GetElementPtrConstantExpr() {
 357     delete [] OperandList;
 358   }
 359 };
 360
 361 /// ConstantExpr::get* - Return some common constants without having to
 362 /// specify the full Instruction::OPCODE identifier.
 363 ///
 364 Constant *ConstantExpr::getNeg(Constant *C) {
 365   if (!C->getType()->isFloatingPoint())
 366     return get(Instruction::Sub, getNullValue(C->getType()), C);
 367   else
 368     return get(Instruction::Sub, ConstantFP::get(C->getType(), -0.0), C);
 369 }
 370 Constant *ConstantExpr::getNot(Constant *C) {
 371   assert(isa<ConstantIntegral>(C) && "Cannot NOT a nonintegral type!");
 372   return get(Instruction::Xor, C,
 373              ConstantIntegral::getAllOnesValue(C->getType()));
 374 }
 375 Constant *ConstantExpr::getAdd(Constant *C1, Constant *C2) {
 376   return get(Instruction::Add, C1, C2);
 377 }
 378 Constant *ConstantExpr::getSub(Constant *C1, Constant *C2) {
 379   return get(Instruction::Sub, C1, C2);
 380 }
 381 Constant *ConstantExpr::getMul(Constant *C1, Constant *C2) {
 382   return get(Instruction::Mul, C1, C2);
 383 }
 384 Constant *ConstantExpr::getDiv(Constant *C1, Constant *C2) {
 385   return get(Instruction::Div, C1, C2);
 386 }
 387 Constant *ConstantExpr::getRem(Constant *C1, Constant *C2) {
 388   return get(Instruction::Rem, C1, C2);
 389 }
 390 Constant *ConstantExpr::getAnd(Constant *C1, Constant *C2) {
 391   return get(Instruction::And, C1, C2);
 392 }
 393 Constant *ConstantExpr::getOr(Constant *C1, Constant *C2) {
 394   return get(Instruction::Or, C1, C2);
 395 }
 396 Constant *ConstantExpr::getXor(Constant *C1, Constant *C2) {
 397   return get(Instruction::Xor, C1, C2);
 398 }
 399 Constant *ConstantExpr::getSetEQ(Constant *C1, Constant *C2) {
 400   return get(Instruction::SetEQ, C1, C2);
 401 }
 402 Constant *ConstantExpr::getSetNE(Constant *C1, Constant *C2) {
 403   return get(Instruction::SetNE, C1, C2);
 404 }
 405 Constant *ConstantExpr::getSetLT(Constant *C1, Constant *C2) {
 406   return get(Instruction::SetLT, C1, C2);
 407 }
 408 Constant *ConstantExpr::getSetGT(Constant *C1, Constant *C2) {
 409   return get(Instruction::SetGT, C1, C2);
 410 }
 411 Constant *ConstantExpr::getSetLE(Constant *C1, Constant *C2) {
 412   return get(Instruction::SetLE, C1, C2);
 413 }
 414 Constant *ConstantExpr::getSetGE(Constant *C1, Constant *C2) {
 415   return get(Instruction::SetGE, C1, C2);
 416 }
 417 Constant *ConstantExpr::getShl(Constant *C1, Constant *C2) {
 418   return get(Instruction::Shl, C1, C2);
 419 }
 420 Constant *ConstantExpr::getShr(Constant *C1, Constant *C2) {
 421   return get(Instruction::Shr, C1, C2);
 422 }
 423
 424 Constant *ConstantExpr::getUShr(Constant *C1, Constant *C2) {
 425   if (C1->getType()->isUnsigned()) return getShr(C1, C2);
 426   return getCast(getShr(getCast(C1,
 427                     C1->getType()->getUnsignedVersion()), C2), C1->getType());
 428 }
 429
 430 Constant *ConstantExpr::getSShr(Constant *C1, Constant *C2) {
 431   if (C1->getType()->isSigned()) return getShr(C1, C2);
 432   return getCast(getShr(getCast(C1,
 433                         C1->getType()->getSignedVersion()), C2), C1->getType());
 434 }
 435
 436
 437 //===----------------------------------------------------------------------===//
 438 //                      isValueValidForType implementations
 439
 440 bool ConstantSInt::isValueValidForType(const Type *Ty, int64_t Val) {
 441   switch (Ty->getTypeID()) {
 442   default:
 443     return false;         // These can't be represented as integers!!!
 444     // Signed types...
 445   case Type::SByteTyID:
 446     return (Val <= INT8_MAX && Val >= INT8_MIN);
 447   case Type::ShortTyID:
 448     return (Val <= INT16_MAX && Val >= INT16_MIN);
 449   case Type::IntTyID:
 450     return (Val <= int(INT32_MAX) && Val >= int(INT32_MIN));
 451   case Type::LongTyID:
 452     return true;          // This is the largest type...
 453   }
 454 }
 455
 456 bool ConstantUInt::isValueValidForType(const Type *Ty, uint64_t Val) {
 457   switch (Ty->getTypeID()) {
 458   default:
 459     return false;         // These can't be represented as integers!!!
 460
 461     // Unsigned types...
 462   case Type::UByteTyID:
 463     return (Val <= UINT8_MAX);
 464   case Type::UShortTyID:
 465     return (Val <= UINT16_MAX);
 466   case Type::UIntTyID:
 467     return (Val <= UINT32_MAX);
 468   case Type::ULongTyID:
 469     return true;          // This is the largest type...
 470   }
 471 }
 472
 473 bool ConstantFP::isValueValidForType(const Type *Ty, double Val) {
 474   switch (Ty->getTypeID()) {
 475   default:
 476     return false;         // These can't be represented as floating point!
 477
 478     // TODO: Figure out how to test if a double can be cast to a float!
 479   case Type::FloatTyID:
 480   case Type::DoubleTyID:
 481     return true;          // This is the largest type...
 482   }
 483 };
 484
 485 //===----------------------------------------------------------------------===//
 486 //                replaceUsesOfWithOnConstant implementations
 487
 488 void ConstantArray::replaceUsesOfWithOnConstant(Value *From, Value *To,
 489                                                 bool DisableChecking) {
 490   assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
 491
 492   std::vector<Constant*> Values;
 493   Values.reserve(getNumOperands());  // Build replacement array...
 494   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
 495     Constant *Val = getOperand(i);
 496     if (Val == From) Val = cast<Constant>(To);
 497     Values.push_back(Val);
 498   }
 499
 500   Constant *Replacement = ConstantArray::get(getType(), Values);
 501   assert(Replacement != this && "I didn't contain From!");
 502
 503   // Everyone using this now uses the replacement...
 504   if (DisableChecking)
 505     uncheckedReplaceAllUsesWith(Replacement);
 506   else
 507     replaceAllUsesWith(Replacement);
 508
 509   // Delete the old constant!
 510   destroyConstant();
 511 }
 512
 513 void ConstantStruct::replaceUsesOfWithOnConstant(Value *From, Value *To,
 514                                                  bool DisableChecking) {
 515   assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
 516
 517   std::vector<Constant*> Values;
 518   Values.reserve(getNumOperands());  // Build replacement array...
 519   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
 520     Constant *Val = getOperand(i);
 521     if (Val == From) Val = cast<Constant>(To);
 522     Values.push_back(Val);
 523   }
 524
 525   Constant *Replacement = ConstantStruct::get(getType(), Values);
 526   assert(Replacement != this && "I didn't contain From!");
 527
 528   // Everyone using this now uses the replacement...
 529   if (DisableChecking)
 530     uncheckedReplaceAllUsesWith(Replacement);
 531   else
 532     replaceAllUsesWith(Replacement);
 533
 534   // Delete the old constant!
 535   destroyConstant();
 536 }
 537
 538 void ConstantPacked::replaceUsesOfWithOnConstant(Value *From, Value *To,
 539                                                  bool DisableChecking) {
 540   assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
 541
 542   std::vector<Constant*> Values;
 543   Values.reserve(getNumOperands());  // Build replacement array...
 544   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
 545     Constant *Val = getOperand(i);
 546     if (Val == From) Val = cast<Constant>(To);
 547     Values.push_back(Val);
 548   }
 549
 550   Constant *Replacement = ConstantPacked::get(getType(), Values);
 551   assert(Replacement != this && "I didn't contain From!");
 552
 553   // Everyone using this now uses the replacement...
 554   if (DisableChecking)
 555     uncheckedReplaceAllUsesWith(Replacement);
 556   else
 557     replaceAllUsesWith(Replacement);
 558
 559   // Delete the old constant!
 560   destroyConstant();
 561 }
 562
 563 void ConstantExpr::replaceUsesOfWithOnConstant(Value *From, Value *ToV,
 564                                                bool DisableChecking) {
 565   assert(isa<Constant>(ToV) && "Cannot make Constant refer to non-constant!");
 566   Constant *To = cast<Constant>(ToV);
 567
 568   Constant *Replacement = 0;
 569   if (getOpcode() == Instruction::GetElementPtr) {
 570     std::vector<Constant*> Indices;
 571     Constant *Pointer = getOperand(0);
 572     Indices.reserve(getNumOperands()-1);
 573     if (Pointer == From) Pointer = To;
 574
 575     for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
 576       Constant *Val = getOperand(i);
 577       if (Val == From) Val = To;
 578       Indices.push_back(Val);
 579     }
 580     Replacement = ConstantExpr::getGetElementPtr(Pointer, Indices);
 581   } else if (getOpcode() == Instruction::Cast) {
 582     assert(getOperand(0) == From && "Cast only has one use!");
 583     Replacement = ConstantExpr::getCast(To, getType());
 584   } else if (getOpcode() == Instruction::Select) {
 585     Constant *C1 = getOperand(0);
 586     Constant *C2 = getOperand(1);
 587     Constant *C3 = getOperand(2);
 588     if (C1 == From) C1 = To;
 589     if (C2 == From) C2 = To;
 590     if (C3 == From) C3 = To;
 591     Replacement = ConstantExpr::getSelect(C1, C2, C3);
 592   } else if (getNumOperands() == 2) {
 593     Constant *C1 = getOperand(0);
 594     Constant *C2 = getOperand(1);
 595     if (C1 == From) C1 = To;
 596     if (C2 == From) C2 = To;
 597     Replacement = ConstantExpr::get(getOpcode(), C1, C2);
 598   } else {
 599     assert(0 && "Unknown ConstantExpr type!");
 600     return;
 601   }
 602
 603   assert(Replacement != this && "I didn't contain From!");
 604
 605   // Everyone using this now uses the replacement...
 606   if (DisableChecking)
 607     uncheckedReplaceAllUsesWith(Replacement);
 608   else
 609     replaceAllUsesWith(Replacement);
 610
 611   // Delete the old constant!
 612   destroyConstant();
 613 }
 614
 615 //===----------------------------------------------------------------------===//
 616 //                      Factory Function Implementation
 617
 618 // ConstantCreator - A class that is used to create constants by
 619 // ValueMap*.  This class should be partially specialized if there is
 620 // something strange that needs to be done to interface to the ctor for the
 621 // constant.
 622 //
 623 namespace llvm {
 624   template<class ConstantClass, class TypeClass, class ValType>
 625   struct ConstantCreator {
 626     static ConstantClass *create(const TypeClass *Ty, const ValType &V) {
 627       return new ConstantClass(Ty, V);
 628     }
 629   };
 630
 631   template<class ConstantClass, class TypeClass>
 632   struct ConvertConstantType {
 633     static void convert(ConstantClass *OldC, const TypeClass *NewTy) {
 634       assert(0 && "This type cannot be converted!\n");
 635       abort();
 636     }
 637   };
 638 }
 639
 640 namespace {
 641   template<class ValType, class TypeClass, class ConstantClass>
 642   class ValueMap : public AbstractTypeUser {
 643     typedef std::pair<const TypeClass*, ValType> MapKey;
 644     typedef std::map<MapKey, ConstantClass *> MapTy;
 645     typedef typename MapTy::iterator MapIterator;
 646     MapTy Map;
 647
 648     typedef std::map<const TypeClass*, MapIterator> AbstractTypeMapTy;
 649     AbstractTypeMapTy AbstractTypeMap;
 650
 651     friend void Constant::clearAllValueMaps();
 652   private:
 653     void clear(std::vector<Constant *> &Constants) {
 654       for(MapIterator I = Map.begin(); I != Map.end(); ++I)
 655         Constants.push_back(I->second);
 656       Map.clear();
 657       AbstractTypeMap.clear();
 658     }
 659
 660   public:
 661     // getOrCreate - Return the specified constant from the map, creating it if
 662     // necessary.
 663     ConstantClass *getOrCreate(const TypeClass *Ty, const ValType &V) {
 664       MapKey Lookup(Ty, V);
 665       MapIterator I = Map.lower_bound(Lookup);
 666       if (I != Map.end() && I->first == Lookup)
 667         return I->second;  // Is it in the map?
 668
 669       // If no preexisting value, create one now...
 670       ConstantClass *Result =
 671         ConstantCreator<ConstantClass,TypeClass,ValType>::create(Ty, V);
 672
 673
 674       /// FIXME: why does this assert fail when loading 176.gcc?
 675       //assert(Result->getType() == Ty && "Type specified is not correct!");
 676       I = Map.insert(I, std::make_pair(MapKey(Ty, V), Result));
 677
 678       // If the type of the constant is abstract, make sure that an entry exists
 679       // for it in the AbstractTypeMap.
 680       if (Ty->isAbstract()) {
 681         typename AbstractTypeMapTy::iterator TI =
 682           AbstractTypeMap.lower_bound(Ty);
 683
 684         if (TI == AbstractTypeMap.end() || TI->first != Ty) {
 685           // Add ourselves to the ATU list of the type.
 686           cast<DerivedType>(Ty)->addAbstractTypeUser(this);
 687
 688           AbstractTypeMap.insert(TI, std::make_pair(Ty, I));
 689         }
 690       }
 691       return Result;
 692     }
 693
 694     void remove(ConstantClass *CP) {
 695       MapIterator I = Map.find(MapKey((TypeClass*)CP->getRawType(),
 696                                       getValType(CP)));
 697       if (I == Map.end() || I->second != CP) {
 698         // FIXME: This should not use a linear scan.  If this gets to be a
 699         // performance problem, someone should look at this.
 700         for (I = Map.begin(); I != Map.end() && I->second != CP; ++I)
 701           /* empty */;
 702       }
 703
 704       assert(I != Map.end() && "Constant not found in constant table!");
 705       assert(I->second == CP && "Didn't find correct element?");
 706
 707       // Now that we found the entry, make sure this isn't the entry that
 708       // the AbstractTypeMap points to.
 709       const TypeClass *Ty = I->first.first;
 710       if (Ty->isAbstract()) {
 711         assert(AbstractTypeMap.count(Ty) &&
 712                "Abstract type not in AbstractTypeMap?");
 713         MapIterator &ATMEntryIt = AbstractTypeMap[Ty];
 714         if (ATMEntryIt == I) {
 715           // Yes, we are removing the representative entry for this type.
 716           // See if there are any other entries of the same type.
 717           MapIterator TmpIt = ATMEntryIt;
 718
 719           // First check the entry before this one...
 720           if (TmpIt != Map.begin()) {
 721             --TmpIt;
 722             if (TmpIt->first.first != Ty) // Not the same type, move back...
 723               ++TmpIt;
 724           }
 725
 726           // If we didn't find the same type, try to move forward...
 727           if (TmpIt == ATMEntryIt) {
 728             ++TmpIt;
 729             if (TmpIt == Map.end() || TmpIt->first.first != Ty)
 730               --TmpIt;   // No entry afterwards with the same type
 731           }
 732
 733           // If there is another entry in the map of the same abstract type,
 734           // update the AbstractTypeMap entry now.
 735           if (TmpIt != ATMEntryIt) {
 736             ATMEntryIt = TmpIt;
 737           } else {
 738             // Otherwise, we are removing the last instance of this type
 739             // from the table.  Remove from the ATM, and from user list.
 740             cast<DerivedType>(Ty)->removeAbstractTypeUser(this);
 741             AbstractTypeMap.erase(Ty);
 742           }
 743         }
 744       }
 745
 746       Map.erase(I);
 747     }
 748
 749     void refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
 750       typename AbstractTypeMapTy::iterator I =
 751         AbstractTypeMap.find(cast<TypeClass>(OldTy));
 752
 753       assert(I != AbstractTypeMap.end() &&
 754              "Abstract type not in AbstractTypeMap?");
 755
 756       // Convert a constant at a time until the last one is gone.  The last one
 757       // leaving will remove() itself, causing the AbstractTypeMapEntry to be
 758       // eliminated eventually.
 759       do {
 760         ConvertConstantType<ConstantClass,
 761                             TypeClass>::convert(I->second->second,
 762                                                 cast<TypeClass>(NewTy));
 763
 764         I = AbstractTypeMap.find(cast<TypeClass>(OldTy));
 765       } while (I != AbstractTypeMap.end());
 766     }
 767
 768     // If the type became concrete without being refined to any other existing
 769     // type, we just remove ourselves from the ATU list.
 770     void typeBecameConcrete(const DerivedType *AbsTy) {
 771       AbsTy->removeAbstractTypeUser(this);
 772     }
 773
 774     void dump() const {
 775       std::cerr << "Constant.cpp: ValueMap\n";
 776     }
 777   };
 778 }
 779
 780 //---- ConstantUInt::get() and ConstantSInt::get() implementations...
 781 //
 782 static ValueMap< int64_t, Type, ConstantSInt> SIntConstants;
 783 static ValueMap<uint64_t, Type, ConstantUInt> UIntConstants;
 784
 785 ConstantSInt *ConstantSInt::get(const Type *Ty, int64_t V) {
 786   return SIntConstants.getOrCreate(Ty, V);
 787 }
 788
 789 ConstantUInt *ConstantUInt::get(const Type *Ty, uint64_t V) {
 790   return UIntConstants.getOrCreate(Ty, V);
 791 }
 792
 793 ConstantInt *ConstantInt::get(const Type *Ty, unsigned char V) {
 794   assert(V <= 127 && "Can only be used with very small positive constants!");
 795   if (Ty->isSigned()) return ConstantSInt::get(Ty, V);
 796   return ConstantUInt::get(Ty, V);
 797 }
 798
 799 //---- ConstantFP::get() implementation...
 800 //
 801 namespace llvm {
 802   template<>
 803   struct ConstantCreator<ConstantFP, Type, uint64_t> {
 804     static ConstantFP *create(const Type *Ty, uint64_t V) {
 805       assert(Ty == Type::DoubleTy);
 806       union {
 807         double F;
 808         uint64_t I;
 809       } T;
 810       T.I = V;
 811       return new ConstantFP(Ty, T.F);
 812     }
 813   };
 814   template<>
 815   struct ConstantCreator<ConstantFP, Type, uint32_t> {
 816     static ConstantFP *create(const Type *Ty, uint32_t V) {
 817       assert(Ty == Type::FloatTy);
 818       union {
 819         float F;
 820         uint32_t I;
 821       } T;
 822       T.I = V;
 823       return new ConstantFP(Ty, T.F);
 824     }
 825   };
 826 }
 827
 828 static ValueMap<uint64_t, Type, ConstantFP> DoubleConstants;
 829 static ValueMap<uint32_t, Type, ConstantFP> FloatConstants;
 830
 831 ConstantFP *ConstantFP::get(const Type *Ty, double V) {
 832   if (Ty == Type::FloatTy) {
 833     // Force the value through memory to normalize it.
 834     union {
 835       float F;
 836       uint32_t I;
 837     } T;
 838     T.F = (float)V;
 839     return FloatConstants.getOrCreate(Ty, T.I);
 840   } else {
 841     assert(Ty == Type::DoubleTy);
 842     union {
 843       double F;
 844       uint64_t I;
 845     } T;
 846     T.F = V;
 847     return DoubleConstants.getOrCreate(Ty, T.I);
 848   }
 849 }
 850
 851 //---- ConstantAggregateZero::get() implementation...
 852 //
 853 namespace llvm {
 854   // ConstantAggregateZero does not take extra "value" argument...
 855   template<class ValType>
 856   struct ConstantCreator<ConstantAggregateZero, Type, ValType> {
 857     static ConstantAggregateZero *create(const Type *Ty, const ValType &V){
 858       return new ConstantAggregateZero(Ty);
 859     }
 860   };
 861
 862   template<>
 863   struct ConvertConstantType<ConstantAggregateZero, Type> {
 864     static void convert(ConstantAggregateZero *OldC, const Type *NewTy) {
 865       // Make everyone now use a constant of the new type...
 866       Constant *New = ConstantAggregateZero::get(NewTy);
 867       assert(New != OldC && "Didn't replace constant??");
 868       OldC->uncheckedReplaceAllUsesWith(New);
 869       OldC->destroyConstant();     // This constant is now dead, destroy it.
 870     }
 871   };
 872 }
 873
 874 static ValueMap<char, Type, ConstantAggregateZero> AggZeroConstants;
 875
 876 static char getValType(ConstantAggregateZero *CPZ) { return 0; }
 877
 878 Constant *ConstantAggregateZero::get(const Type *Ty) {
 879   return AggZeroConstants.getOrCreate(Ty, 0);
 880 }
 881
 882 // destroyConstant - Remove the constant from the constant table...
 883 //
 884 void ConstantAggregateZero::destroyConstant() {
 885   AggZeroConstants.remove(this);
 886   destroyConstantImpl();
 887 }
 888
 889 void ConstantAggregateZero::replaceUsesOfWithOnConstant(Value *From, Value *To,
 890                                                         bool DisableChecking) {
 891   assert(0 && "No uses!");
 892   abort();
 893 }
 894
 895
 896
 897 //---- ConstantArray::get() implementation...
 898 //
 899 namespace llvm {
 900   template<>
 901   struct ConvertConstantType<ConstantArray, ArrayType> {
 902     static void convert(ConstantArray *OldC, const ArrayType *NewTy) {
 903       // Make everyone now use a constant of the new type...
 904       std::vector<Constant*> C;
 905       for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i)
 906         C.push_back(cast<Constant>(OldC->getOperand(i)));
 907       Constant *New = ConstantArray::get(NewTy, C);
 908       assert(New != OldC && "Didn't replace constant??");
 909       OldC->uncheckedReplaceAllUsesWith(New);
 910       OldC->destroyConstant();    // This constant is now dead, destroy it.
 911     }
 912   };
 913 }
 914
 915 static std::vector<Constant*> getValType(ConstantArray *CA) {
 916   std::vector<Constant*> Elements;
 917   Elements.reserve(CA->getNumOperands());
 918   for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i)
 919     Elements.push_back(cast<Constant>(CA->getOperand(i)));
 920   return Elements;
 921 }
 922
 923 static ValueMap<std::vector<Constant*>, ArrayType,
 924                 ConstantArray> ArrayConstants;
 925
 926 Constant *ConstantArray::get(const ArrayType *Ty,
 927                              const std::vector<Constant*> &V) {
 928   // If this is an all-zero array, return a ConstantAggregateZero object
 929   if (!V.empty()) {
 930     Constant *C = V[0];
 931     if (!C->isNullValue())
 932       return ArrayConstants.getOrCreate(Ty, V);
 933     for (unsigned i = 1, e = V.size(); i != e; ++i)
 934       if (V[i] != C)
 935         return ArrayConstants.getOrCreate(Ty, V);
 936   }
 937   return ConstantAggregateZero::get(Ty);
 938 }
 939
 940 // destroyConstant - Remove the constant from the constant table...
 941 //
 942 void ConstantArray::destroyConstant() {
 943   ArrayConstants.remove(this);
 944   destroyConstantImpl();
 945 }
 946
 947 // ConstantArray::get(const string&) - Return an array that is initialized to
 948 // contain the specified string.  A null terminator is added to the specified
 949 // string so that it may be used in a natural way...
 950 //
 951 Constant *ConstantArray::get(const std::string &Str) {
 952   std::vector<Constant*> ElementVals;
 953
 954   for (unsigned i = 0; i < Str.length(); ++i)
 955     ElementVals.push_back(ConstantSInt::get(Type::SByteTy, Str[i]));
 956
 957   // Add a null terminator to the string...
 958   ElementVals.push_back(ConstantSInt::get(Type::SByteTy, 0));
 959
 960   ArrayType *ATy = ArrayType::get(Type::SByteTy, Str.length()+1);
 961   return ConstantArray::get(ATy, ElementVals);
 962 }
 963
 964 /// isString - This method returns true if the array is an array of sbyte or
 965 /// ubyte, and if the elements of the array are all ConstantInt's.
 966 bool ConstantArray::isString() const {
 967   // Check the element type for sbyte or ubyte...
 968   if (getType()->getElementType() != Type::UByteTy &&
 969       getType()->getElementType() != Type::SByteTy)
 970     return false;
 971   // Check the elements to make sure they are all integers, not constant
 972   // expressions.
 973   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
 974     if (!isa<ConstantInt>(getOperand(i)))
 975       return false;
 976   return true;
 977 }
 978
 979 // getAsString - If the sub-element type of this array is either sbyte or ubyte,
 980 // then this method converts the array to an std::string and returns it.
 981 // Otherwise, it asserts out.
 982 //
 983 std::string ConstantArray::getAsString() const {
 984   assert(isString() && "Not a string!");
 985   std::string Result;
 986   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
 987     Result += (char)cast<ConstantInt>(getOperand(i))->getRawValue();
 988   return Result;
 989 }
 990
 991
 992 //---- ConstantStruct::get() implementation...
 993 //
 994
 995 namespace llvm {
 996   template<>
 997   struct ConvertConstantType<ConstantStruct, StructType> {
 998     static void convert(ConstantStruct *OldC, const StructType *NewTy) {
 999       // Make everyone now use a constant of the new type...
1000       std::vector<Constant*> C;
1001       for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i)
1002         C.push_back(cast<Constant>(OldC->getOperand(i)));
1003       Constant *New = ConstantStruct::get(NewTy, C);
1004       assert(New != OldC && "Didn't replace constant??");
1005
1006       OldC->uncheckedReplaceAllUsesWith(New);
1007       OldC->destroyConstant();    // This constant is now dead, destroy it.
1008     }
1009   };
1010 }
1011
1012 static ValueMap<std::vector<Constant*>, StructType,
1013                 ConstantStruct> StructConstants;
1014
1015 static std::vector<Constant*> getValType(ConstantStruct *CS) {
1016   std::vector<Constant*> Elements;
1017   Elements.reserve(CS->getNumOperands());
1018   for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i)
1019     Elements.push_back(cast<Constant>(CS->getOperand(i)));
1020   return Elements;
1021 }
1022
1023 Constant *ConstantStruct::get(const StructType *Ty,
1024                               const std::vector<Constant*> &V) {
1025   // Create a ConstantAggregateZero value if all elements are zeros...
1026   for (unsigned i = 0, e = V.size(); i != e; ++i)
1027     if (!V[i]->isNullValue())
1028       return StructConstants.getOrCreate(Ty, V);
1029
1030   return ConstantAggregateZero::get(Ty);
1031 }
1032
1033 Constant *ConstantStruct::get(const std::vector<Constant*> &V) {
1034   std::vector<const Type*> StructEls;
1035   StructEls.reserve(V.size());
1036   for (unsigned i = 0, e = V.size(); i != e; ++i)
1037     StructEls.push_back(V[i]->getType());
1038   return get(StructType::get(StructEls), V);
1039 }
1040
1041 // destroyConstant - Remove the constant from the constant table...
1042 //
1043 void ConstantStruct::destroyConstant() {
1044   StructConstants.remove(this);
1045   destroyConstantImpl();
1046 }
1047
1048 //---- ConstantPacked::get() implementation...
1049 //
1050 namespace llvm {
1051   template<>
1052   struct ConvertConstantType<ConstantPacked, PackedType> {
1053     static void convert(ConstantPacked *OldC, const PackedType *NewTy) {
1054       // Make everyone now use a constant of the new type...
1055       std::vector<Constant*> C;
1056       for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i)
1057         C.push_back(cast<Constant>(OldC->getOperand(i)));
1058       Constant *New = ConstantPacked::get(NewTy, C);
1059       assert(New != OldC && "Didn't replace constant??");
1060       OldC->uncheckedReplaceAllUsesWith(New);
1061       OldC->destroyConstant();    // This constant is now dead, destroy it.
1062     }
1063   };
1064 }
1065
1066 static std::vector<Constant*> getValType(ConstantPacked *CP) {
1067   std::vector<Constant*> Elements;
1068   Elements.reserve(CP->getNumOperands());
1069   for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i)
1070     Elements.push_back(CP->getOperand(i));
1071   return Elements;
1072 }
1073
1074 static ValueMap<std::vector<Constant*>, PackedType,
1075                 ConstantPacked> PackedConstants;
1076
1077 Constant *ConstantPacked::get(const PackedType *Ty,
1078                               const std::vector<Constant*> &V) {
1079   // If this is an all-zero packed, return a ConstantAggregateZero object
1080   if (!V.empty()) {
1081     Constant *C = V[0];
1082     if (!C->isNullValue())
1083       return PackedConstants.getOrCreate(Ty, V);
1084     for (unsigned i = 1, e = V.size(); i != e; ++i)
1085       if (V[i] != C)
1086         return PackedConstants.getOrCreate(Ty, V);
1087   }
1088   return ConstantAggregateZero::get(Ty);
1089 }
1090
1091 Constant *ConstantPacked::get(const std::vector<Constant*> &V) {
1092   assert(!V.empty() && "Cannot infer type if V is empty");
1093   return get(PackedType::get(V.front()->getType(),V.size()), V);
1094 }
1095
1096 // destroyConstant - Remove the constant from the constant table...
1097 //
1098 void ConstantPacked::destroyConstant() {
1099   PackedConstants.remove(this);
1100   destroyConstantImpl();
1101 }
1102
1103 //---- ConstantPointerNull::get() implementation...
1104 //
1105
1106 namespace llvm {
1107   // ConstantPointerNull does not take extra "value" argument...
1108   template<class ValType>
1109   struct ConstantCreator<ConstantPointerNull, PointerType, ValType> {
1110     static ConstantPointerNull *create(const PointerType *Ty, const ValType &V){
1111       return new ConstantPointerNull(Ty);
1112     }
1113   };
1114
1115   template<>
1116   struct ConvertConstantType<ConstantPointerNull, PointerType> {
1117     static void convert(ConstantPointerNull *OldC, const PointerType *NewTy) {
1118       // Make everyone now use a constant of the new type...
1119       Constant *New = ConstantPointerNull::get(NewTy);
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 ValueMap<char, PointerType, ConstantPointerNull> NullPtrConstants;
1128
1129 static char getValType(ConstantPointerNull *) {
1130   return 0;
1131 }
1132
1133
1134 ConstantPointerNull *ConstantPointerNull::get(const PointerType *Ty) {
1135   return NullPtrConstants.getOrCreate(Ty, 0);
1136 }
1137
1138 // destroyConstant - Remove the constant from the constant table...
1139 //
1140 void ConstantPointerNull::destroyConstant() {
1141   NullPtrConstants.remove(this);
1142   destroyConstantImpl();
1143 }
1144
1145
1146 //---- UndefValue::get() implementation...
1147 //
1148
1149 namespace llvm {
1150   // UndefValue does not take extra "value" argument...
1151   template<class ValType>
1152   struct ConstantCreator<UndefValue, Type, ValType> {
1153     static UndefValue *create(const Type *Ty, const ValType &V) {
1154       return new UndefValue(Ty);
1155     }
1156   };
1157
1158   template<>
1159   struct ConvertConstantType<UndefValue, Type> {
1160     static void convert(UndefValue *OldC, const Type *NewTy) {
1161       // Make everyone now use a constant of the new type.
1162       Constant *New = UndefValue::get(NewTy);
1163       assert(New != OldC && "Didn't replace constant??");
1164       OldC->uncheckedReplaceAllUsesWith(New);
1165       OldC->destroyConstant();     // This constant is now dead, destroy it.
1166     }
1167   };
1168 }
1169
1170 static ValueMap<char, Type, UndefValue> UndefValueConstants;
1171
1172 static char getValType(UndefValue *) {
1173   return 0;
1174 }
1175
1176
1177 UndefValue *UndefValue::get(const Type *Ty) {
1178   return UndefValueConstants.getOrCreate(Ty, 0);
1179 }
1180
1181 // destroyConstant - Remove the constant from the constant table.
1182 //
1183 void UndefValue::destroyConstant() {
1184   UndefValueConstants.remove(this);
1185   destroyConstantImpl();
1186 }
1187
1188
1189
1190
1191 //---- ConstantExpr::get() implementations...
1192 //
1193 typedef std::pair<unsigned, std::vector<Constant*> > ExprMapKeyType;
1194
1195 namespace llvm {
1196   template<>
1197   struct ConstantCreator<ConstantExpr, Type, ExprMapKeyType> {
1198     static ConstantExpr *create(const Type *Ty, const ExprMapKeyType &V) {
1199       if (V.first == Instruction::Cast)
1200         return new UnaryConstantExpr(Instruction::Cast, V.second[0], Ty);
1201       if ((V.first >= Instruction::BinaryOpsBegin &&
1202            V.first < Instruction::BinaryOpsEnd) ||
1203           V.first == Instruction::Shl || V.first == Instruction::Shr)
1204         return new BinaryConstantExpr(V.first, V.second[0], V.second[1]);
1205       if (V.first == Instruction::Select)
1206         return new SelectConstantExpr(V.second[0], V.second[1], V.second[2]);
1207
1208       assert(V.first == Instruction::GetElementPtr && "Invalid ConstantExpr!");
1209
1210       std::vector<Constant*> IdxList(V.second.begin()+1, V.second.end());
1211       return new GetElementPtrConstantExpr(V.second[0], IdxList, Ty);
1212     }
1213   };
1214
1215   template<>
1216   struct ConvertConstantType<ConstantExpr, Type> {
1217     static void convert(ConstantExpr *OldC, const Type *NewTy) {
1218       Constant *New;
1219       switch (OldC->getOpcode()) {
1220       case Instruction::Cast:
1221         New = ConstantExpr::getCast(OldC->getOperand(0), NewTy);
1222         break;
1223       case Instruction::Select:
1224         New = ConstantExpr::getSelectTy(NewTy, OldC->getOperand(0),
1225                                         OldC->getOperand(1),
1226                                         OldC->getOperand(2));
1227         break;
1228       case Instruction::Shl:
1229       case Instruction::Shr:
1230         New = ConstantExpr::getShiftTy(NewTy, OldC->getOpcode(),
1231                                      OldC->getOperand(0), OldC->getOperand(1));
1232         break;
1233       default:
1234         assert(OldC->getOpcode() >= Instruction::BinaryOpsBegin &&
1235                OldC->getOpcode() < Instruction::BinaryOpsEnd);
1236         New = ConstantExpr::getTy(NewTy, OldC->getOpcode(), OldC->getOperand(0),
1237                                   OldC->getOperand(1));
1238         break;
1239       case Instruction::GetElementPtr:
1240         // Make everyone now use a constant of the new type...
1241         std::vector<Value*> Idx(OldC->op_begin()+1, OldC->op_end());
1242         New = ConstantExpr::getGetElementPtrTy(NewTy, OldC->getOperand(0), Idx);
1243         break;
1244       }
1245
1246       assert(New != OldC && "Didn't replace constant??");
1247       OldC->uncheckedReplaceAllUsesWith(New);
1248       OldC->destroyConstant();    // This constant is now dead, destroy it.
1249     }
1250   };
1251 } // end namespace llvm
1252
1253
1254 static ExprMapKeyType getValType(ConstantExpr *CE) {
1255   std::vector<Constant*> Operands;
1256   Operands.reserve(CE->getNumOperands());
1257   for (unsigned i = 0, e = CE->getNumOperands(); i != e; ++i)
1258     Operands.push_back(cast<Constant>(CE->getOperand(i)));
1259   return ExprMapKeyType(CE->getOpcode(), Operands);
1260 }
1261
1262 static ValueMap<ExprMapKeyType, Type, ConstantExpr> ExprConstants;
1263
1264 Constant *ConstantExpr::getCast(Constant *C, const Type *Ty) {
1265   assert(Ty->isFirstClassType() && "Cannot cast to an aggregate type!");
1266
1267   if (Constant *FC = ConstantFoldCastInstruction(C, Ty))
1268     return FC;          // Fold a few common cases...
1269
1270   // Look up the constant in the table first to ensure uniqueness
1271   std::vector<Constant*> argVec(1, C);
1272   ExprMapKeyType Key = std::make_pair(Instruction::Cast, argVec);
1273   return ExprConstants.getOrCreate(Ty, Key);
1274 }
1275
1276 Constant *ConstantExpr::getSignExtend(Constant *C, const Type *Ty) {
1277   assert(C->getType()->isIntegral() && Ty->isIntegral() &&
1278          C->getType()->getPrimitiveSize() <= Ty->getPrimitiveSize() &&
1279          "This is an illegal sign extension!");
1280   if (C->getType() != Type::BoolTy) {
1281     C = ConstantExpr::getCast(C, C->getType()->getSignedVersion());
1282     return ConstantExpr::getCast(C, Ty);
1283   } else {
1284     if (C == ConstantBool::True)
1285       return ConstantIntegral::getAllOnesValue(Ty);
1286     else
1287       return ConstantIntegral::getNullValue(Ty);
1288   }
1289 }
1290
1291 Constant *ConstantExpr::getZeroExtend(Constant *C, const Type *Ty) {
1292   assert(C->getType()->isIntegral() && Ty->isIntegral() &&
1293          C->getType()->getPrimitiveSize() <= Ty->getPrimitiveSize() &&
1294          "This is an illegal zero extension!");
1295   if (C->getType() != Type::BoolTy)
1296     C = ConstantExpr::getCast(C, C->getType()->getUnsignedVersion());
1297   return ConstantExpr::getCast(C, Ty);
1298 }
1299
1300 Constant *ConstantExpr::getSizeOf(const Type *Ty) {
1301   // sizeof is implemented as: (ulong) gep (Ty*)null, 1
1302   return getCast(
1303     getGetElementPtr(getNullValue(PointerType::get(Ty)),
1304                  std::vector<Constant*>(1, ConstantInt::get(Type::UIntTy, 1))),
1305     Type::ULongTy);
1306 }
1307
1308 Constant *ConstantExpr::getTy(const Type *ReqTy, unsigned Opcode,
1309                               Constant *C1, Constant *C2) {
1310   if (Opcode == Instruction::Shl || Opcode == Instruction::Shr)
1311     return getShiftTy(ReqTy, Opcode, C1, C2);
1312   // Check the operands for consistency first
1313   assert((Opcode >= Instruction::BinaryOpsBegin &&
1314           Opcode < Instruction::BinaryOpsEnd) &&
1315          "Invalid opcode in binary constant expression");
1316   assert(C1->getType() == C2->getType() &&
1317          "Operand types in binary constant expression should match");
1318
1319   if (ReqTy == C1->getType() || (Instruction::isRelational(Opcode) &&
1320                                  ReqTy == Type::BoolTy))
1321     if (Constant *FC = ConstantFoldBinaryInstruction(Opcode, C1, C2))
1322       return FC;          // Fold a few common cases...
1323
1324   std::vector<Constant*> argVec(1, C1); argVec.push_back(C2);
1325   ExprMapKeyType Key = std::make_pair(Opcode, argVec);
1326   return ExprConstants.getOrCreate(ReqTy, Key);
1327 }
1328
1329 Constant *ConstantExpr::get(unsigned Opcode, Constant *C1, Constant *C2) {
1330 #ifndef NDEBUG
1331   switch (Opcode) {
1332   case Instruction::Add: case Instruction::Sub:
1333   case Instruction::Mul: case Instruction::Div:
1334   case Instruction::Rem:
1335     assert(C1->getType() == C2->getType() && "Op types should be identical!");
1336     assert((C1->getType()->isInteger() || C1->getType()->isFloatingPoint()) &&
1337            "Tried to create an arithmetic operation on a non-arithmetic type!");
1338     break;
1339   case Instruction::And:
1340   case Instruction::Or:
1341   case Instruction::Xor:
1342     assert(C1->getType() == C2->getType() && "Op types should be identical!");
1343     assert(C1->getType()->isIntegral() &&
1344            "Tried to create a logical operation on a non-integral type!");
1345     break;
1346   case Instruction::SetLT: case Instruction::SetGT: case Instruction::SetLE:
1347   case Instruction::SetGE: case Instruction::SetEQ: case Instruction::SetNE:
1348     assert(C1->getType() == C2->getType() && "Op types should be identical!");
1349     break;
1350   case Instruction::Shl:
1351   case Instruction::Shr:
1352     assert(C2->getType() == Type::UByteTy && "Shift should be by ubyte!");
1353     assert(C1->getType()->isInteger() &&
1354            "Tried to create a shift operation on a non-integer type!");
1355     break;
1356   default:
1357     break;
1358   }
1359 #endif
1360
1361   if (Instruction::isRelational(Opcode))
1362     return getTy(Type::BoolTy, Opcode, C1, C2);
1363   else
1364     return getTy(C1->getType(), Opcode, C1, C2);
1365 }
1366
1367 Constant *ConstantExpr::getSelectTy(const Type *ReqTy, Constant *C,
1368                                     Constant *V1, Constant *V2) {
1369   assert(C->getType() == Type::BoolTy && "Select condition must be bool!");
1370   assert(V1->getType() == V2->getType() && "Select value types must match!");
1371   assert(V1->getType()->isFirstClassType() && "Cannot select aggregate type!");
1372
1373   if (ReqTy == V1->getType())
1374     if (Constant *SC = ConstantFoldSelectInstruction(C, V1, V2))
1375       return SC;        // Fold common cases
1376
1377   std::vector<Constant*> argVec(3, C);
1378   argVec[1] = V1;
1379   argVec[2] = V2;
1380   ExprMapKeyType Key = std::make_pair(Instruction::Select, argVec);
1381   return ExprConstants.getOrCreate(ReqTy, Key);
1382 }
1383
1384 /// getShiftTy - Return a shift left or shift right constant expr
1385 Constant *ConstantExpr::getShiftTy(const Type *ReqTy, unsigned Opcode,
1386                                    Constant *C1, Constant *C2) {
1387   // Check the operands for consistency first
1388   assert((Opcode == Instruction::Shl ||
1389           Opcode == Instruction::Shr) &&
1390          "Invalid opcode in binary constant expression");
1391   assert(C1->getType()->isIntegral() && C2->getType() == Type::UByteTy &&
1392          "Invalid operand types for Shift constant expr!");
1393
1394   if (Constant *FC = ConstantFoldBinaryInstruction(Opcode, C1, C2))
1395     return FC;          // Fold a few common cases...
1396
1397   // Look up the constant in the table first to ensure uniqueness
1398   std::vector<Constant*> argVec(1, C1); argVec.push_back(C2);
1399   ExprMapKeyType Key = std::make_pair(Opcode, argVec);
1400   return ExprConstants.getOrCreate(ReqTy, Key);
1401 }
1402
1403
1404 Constant *ConstantExpr::getGetElementPtrTy(const Type *ReqTy, Constant *C,
1405                                            const std::vector<Value*> &IdxList) {
1406   assert(GetElementPtrInst::getIndexedType(C->getType(), IdxList, true) &&
1407          "GEP indices invalid!");
1408
1409   if (Constant *FC = ConstantFoldGetElementPtr(C, IdxList))
1410     return FC;          // Fold a few common cases...
1411
1412   assert(isa<PointerType>(C->getType()) &&
1413          "Non-pointer type for constant GetElementPtr expression");
1414   // Look up the constant in the table first to ensure uniqueness
1415   std::vector<Constant*> ArgVec;
1416   ArgVec.reserve(IdxList.size()+1);
1417   ArgVec.push_back(C);
1418   for (unsigned i = 0, e = IdxList.size(); i != e; ++i)
1419     ArgVec.push_back(cast<Constant>(IdxList[i]));
1420   const ExprMapKeyType &Key = std::make_pair(Instruction::GetElementPtr,ArgVec);
1421   return ExprConstants.getOrCreate(ReqTy, Key);
1422 }
1423
1424 Constant *ConstantExpr::getGetElementPtr(Constant *C,
1425                                          const std::vector<Constant*> &IdxList){
1426   // Get the result type of the getelementptr!
1427   std::vector<Value*> VIdxList(IdxList.begin(), IdxList.end());
1428
1429   const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), VIdxList,
1430                                                      true);
1431   assert(Ty && "GEP indices invalid!");
1432   return getGetElementPtrTy(PointerType::get(Ty), C, VIdxList);
1433 }
1434
1435 Constant *ConstantExpr::getGetElementPtr(Constant *C,
1436                                          const std::vector<Value*> &IdxList) {
1437   // Get the result type of the getelementptr!
1438   const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), IdxList,
1439                                                      true);
1440   assert(Ty && "GEP indices invalid!");
1441   return getGetElementPtrTy(PointerType::get(Ty), C, IdxList);
1442 }
1443
1444
1445 // destroyConstant - Remove the constant from the constant table...
1446 //
1447 void ConstantExpr::destroyConstant() {
1448   ExprConstants.remove(this);
1449   destroyConstantImpl();
1450 }
1451
1452 const char *ConstantExpr::getOpcodeName() const {
1453   return Instruction::getOpcodeName(getOpcode());
1454 }
1455
1456 /// clearAllValueMaps - This method frees all internal memory used by the
1457 /// constant subsystem, which can be used in environments where this memory
1458 /// is otherwise reported as a leak.
1459 void Constant::clearAllValueMaps() {
1460   std::vector<Constant *> Constants;
1461
1462   DoubleConstants.clear(Constants);
1463   FloatConstants.clear(Constants);
1464   SIntConstants.clear(Constants);
1465   UIntConstants.clear(Constants);
1466   AggZeroConstants.clear(Constants);
1467   ArrayConstants.clear(Constants);
1468   StructConstants.clear(Constants);
1469   PackedConstants.clear(Constants);
1470   NullPtrConstants.clear(Constants);
1471   UndefValueConstants.clear(Constants);
1472   ExprConstants.clear(Constants);
1473
1474   for (std::vector<Constant *>::iterator I = Constants.begin(),
1475        E = Constants.end(); I != E; ++I)
1476     (*I)->dropAllReferences();
1477   for (std::vector<Constant *>::iterator I = Constants.begin(),
1478        E = Constants.end(); I != E; ++I)
1479     (*I)->destroyConstantImpl();
1480   Constants.clear();
1481 }