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 "llvm/Support/MathExtras.h"
  23 #include "llvm/Support/Visibility.h"
  24 #include <algorithm>
  25 #include <iostream>
  26 using namespace llvm;
  27
  28 ConstantBool *ConstantBool::True  = new ConstantBool(true);
  29 ConstantBool *ConstantBool::False = new ConstantBool(false);
  30
  31
  32 //===----------------------------------------------------------------------===//
  33 //                              Constant Class
  34 //===----------------------------------------------------------------------===//
  35
  36 void Constant::destroyConstantImpl() {
  37   // When a Constant is destroyed, there may be lingering
  38   // references to the constant by other constants in the constant pool.  These
  39   // constants are implicitly dependent on the module that is being deleted,
  40   // but they don't know that.  Because we only find out when the CPV is
  41   // deleted, we must now notify all of our users (that should only be
  42   // Constants) that they are, in fact, invalid now and should be deleted.
  43   //
  44   while (!use_empty()) {
  45     Value *V = use_back();
  46 #ifndef NDEBUG      // Only in -g mode...
  47     if (!isa<Constant>(V))
  48       std::cerr << "While deleting: " << *this
  49                 << "\n\nUse still stuck around after Def is destroyed: "
  50                 << *V << "\n\n";
  51 #endif
  52     assert(isa<Constant>(V) && "References remain to Constant being destroyed");
  53     Constant *CV = cast<Constant>(V);
  54     CV->destroyConstant();
  55
  56     // The constant should remove itself from our use list...
  57     assert((use_empty() || use_back() != V) && "Constant not removed!");
  58   }
  59
  60   // Value has no outstanding references it is safe to delete it now...
  61   delete this;
  62 }
  63
  64 // Static constructor to create a '0' constant of arbitrary type...
  65 Constant *Constant::getNullValue(const Type *Ty) {
  66   switch (Ty->getTypeID()) {
  67   case Type::BoolTyID: {
  68     static Constant *NullBool = ConstantBool::get(false);
  69     return NullBool;
  70   }
  71   case Type::SByteTyID: {
  72     static Constant *NullSByte = ConstantSInt::get(Type::SByteTy, 0);
  73     return NullSByte;
  74   }
  75   case Type::UByteTyID: {
  76     static Constant *NullUByte = ConstantUInt::get(Type::UByteTy, 0);
  77     return NullUByte;
  78   }
  79   case Type::ShortTyID: {
  80     static Constant *NullShort = ConstantSInt::get(Type::ShortTy, 0);
  81     return NullShort;
  82   }
  83   case Type::UShortTyID: {
  84     static Constant *NullUShort = ConstantUInt::get(Type::UShortTy, 0);
  85     return NullUShort;
  86   }
  87   case Type::IntTyID: {
  88     static Constant *NullInt = ConstantSInt::get(Type::IntTy, 0);
  89     return NullInt;
  90   }
  91   case Type::UIntTyID: {
  92     static Constant *NullUInt = ConstantUInt::get(Type::UIntTy, 0);
  93     return NullUInt;
  94   }
  95   case Type::LongTyID: {
  96     static Constant *NullLong = ConstantSInt::get(Type::LongTy, 0);
  97     return NullLong;
  98   }
  99   case Type::ULongTyID: {
 100     static Constant *NullULong = ConstantUInt::get(Type::ULongTy, 0);
 101     return NullULong;
 102   }
 103
 104   case Type::FloatTyID: {
 105     static Constant *NullFloat = ConstantFP::get(Type::FloatTy, 0);
 106     return NullFloat;
 107   }
 108   case Type::DoubleTyID: {
 109     static Constant *NullDouble = ConstantFP::get(Type::DoubleTy, 0);
 110     return NullDouble;
 111   }
 112
 113   case Type::PointerTyID:
 114     return ConstantPointerNull::get(cast<PointerType>(Ty));
 115
 116   case Type::StructTyID:
 117   case Type::ArrayTyID:
 118   case Type::PackedTyID:
 119     return ConstantAggregateZero::get(Ty);
 120   default:
 121     // Function, Label, or Opaque type?
 122     assert(!"Cannot create a null constant of that type!");
 123     return 0;
 124   }
 125 }
 126
 127 // Static constructor to create the maximum constant of an integral type...
 128 ConstantIntegral *ConstantIntegral::getMaxValue(const Type *Ty) {
 129   switch (Ty->getTypeID()) {
 130   case Type::BoolTyID:   return ConstantBool::True;
 131   case Type::SByteTyID:
 132   case Type::ShortTyID:
 133   case Type::IntTyID:
 134   case Type::LongTyID: {
 135     // Calculate 011111111111111...
 136     unsigned TypeBits = Ty->getPrimitiveSize()*8;
 137     int64_t Val = INT64_MAX;             // All ones
 138     Val >>= 64-TypeBits;                 // Shift out unwanted 1 bits...
 139     return ConstantSInt::get(Ty, Val);
 140   }
 141
 142   case Type::UByteTyID:
 143   case Type::UShortTyID:
 144   case Type::UIntTyID:
 145   case Type::ULongTyID:  return getAllOnesValue(Ty);
 146
 147   default: return 0;
 148   }
 149 }
 150
 151 // Static constructor to create the minimum constant for an integral type...
 152 ConstantIntegral *ConstantIntegral::getMinValue(const Type *Ty) {
 153   switch (Ty->getTypeID()) {
 154   case Type::BoolTyID:   return ConstantBool::False;
 155   case Type::SByteTyID:
 156   case Type::ShortTyID:
 157   case Type::IntTyID:
 158   case Type::LongTyID: {
 159      // Calculate 1111111111000000000000
 160      unsigned TypeBits = Ty->getPrimitiveSize()*8;
 161      int64_t Val = -1;                    // All ones
 162      Val <<= TypeBits-1;                  // Shift over to the right spot
 163      return ConstantSInt::get(Ty, Val);
 164   }
 165
 166   case Type::UByteTyID:
 167   case Type::UShortTyID:
 168   case Type::UIntTyID:
 169   case Type::ULongTyID:  return ConstantUInt::get(Ty, 0);
 170
 171   default: return 0;
 172   }
 173 }
 174
 175 // Static constructor to create an integral constant with all bits set
 176 ConstantIntegral *ConstantIntegral::getAllOnesValue(const Type *Ty) {
 177   switch (Ty->getTypeID()) {
 178   case Type::BoolTyID:   return ConstantBool::True;
 179   case Type::SByteTyID:
 180   case Type::ShortTyID:
 181   case Type::IntTyID:
 182   case Type::LongTyID:   return ConstantSInt::get(Ty, -1);
 183
 184   case Type::UByteTyID:
 185   case Type::UShortTyID:
 186   case Type::UIntTyID:
 187   case Type::ULongTyID: {
 188     // Calculate ~0 of the right type...
 189     unsigned TypeBits = Ty->getPrimitiveSize()*8;
 190     uint64_t Val = ~0ULL;                // All ones
 191     Val >>= 64-TypeBits;                 // Shift out unwanted 1 bits...
 192     return ConstantUInt::get(Ty, Val);
 193   }
 194   default: return 0;
 195   }
 196 }
 197
 198 bool ConstantUInt::isAllOnesValue() const {
 199   unsigned TypeBits = getType()->getPrimitiveSize()*8;
 200   uint64_t Val = ~0ULL;                // All ones
 201   Val >>= 64-TypeBits;                 // Shift out inappropriate bits
 202   return getValue() == Val;
 203 }
 204
 205
 206 //===----------------------------------------------------------------------===//
 207 //                            ConstantXXX Classes
 208 //===----------------------------------------------------------------------===//
 209
 210 //===----------------------------------------------------------------------===//
 211 //                             Normal Constructors
 212
 213 ConstantIntegral::ConstantIntegral(const Type *Ty, ValueTy VT, uint64_t V)
 214   : Constant(Ty, VT, 0, 0) {
 215     Val.Unsigned = V;
 216 }
 217
 218 ConstantBool::ConstantBool(bool V)
 219   : ConstantIntegral(Type::BoolTy, ConstantBoolVal, V) {
 220 }
 221
 222 ConstantInt::ConstantInt(const Type *Ty, ValueTy VT, uint64_t V)
 223   : ConstantIntegral(Ty, VT, V) {
 224 }
 225
 226 ConstantSInt::ConstantSInt(const Type *Ty, int64_t V)
 227   : ConstantInt(Ty, ConstantSIntVal, V) {
 228   assert(Ty->isInteger() && Ty->isSigned() &&
 229          "Illegal type for signed integer constant!");
 230   assert(isValueValidForType(Ty, V) && "Value too large for type!");
 231 }
 232
 233 ConstantUInt::ConstantUInt(const Type *Ty, uint64_t V)
 234   : ConstantInt(Ty, ConstantUIntVal, V) {
 235   assert(Ty->isInteger() && Ty->isUnsigned() &&
 236          "Illegal type for unsigned integer constant!");
 237   assert(isValueValidForType(Ty, V) && "Value too large for type!");
 238 }
 239
 240 ConstantFP::ConstantFP(const Type *Ty, double V)
 241   : Constant(Ty, ConstantFPVal, 0, 0) {
 242   assert(isValueValidForType(Ty, V) && "Value too large for type!");
 243   Val = V;
 244 }
 245
 246 ConstantArray::ConstantArray(const ArrayType *T,
 247                              const std::vector<Constant*> &V)
 248   : Constant(T, ConstantArrayVal, new Use[V.size()], V.size()) {
 249   assert(V.size() == T->getNumElements() &&
 250          "Invalid initializer vector for constant array");
 251   Use *OL = OperandList;
 252   for (std::vector<Constant*>::const_iterator I = V.begin(), E = V.end();
 253        I != E; ++I, ++OL) {
 254     Constant *C = *I;
 255     assert((C->getType() == T->getElementType() ||
 256             (T->isAbstract() &&
 257              C->getType()->getTypeID() == T->getElementType()->getTypeID())) &&
 258            "Initializer for array element doesn't match array element type!");
 259     OL->init(C, this);
 260   }
 261 }
 262
 263 ConstantArray::~ConstantArray() {
 264   delete [] OperandList;
 265 }
 266
 267 ConstantStruct::ConstantStruct(const StructType *T,
 268                                const std::vector<Constant*> &V)
 269   : Constant(T, ConstantStructVal, new Use[V.size()], V.size()) {
 270   assert(V.size() == T->getNumElements() &&
 271          "Invalid initializer vector for constant structure");
 272   Use *OL = OperandList;
 273   for (std::vector<Constant*>::const_iterator I = V.begin(), E = V.end();
 274        I != E; ++I, ++OL) {
 275     Constant *C = *I;
 276     assert((C->getType() == T->getElementType(I-V.begin()) ||
 277             ((T->getElementType(I-V.begin())->isAbstract() ||
 278               C->getType()->isAbstract()) &&
 279              T->getElementType(I-V.begin())->getTypeID() ==
 280                    C->getType()->getTypeID())) &&
 281            "Initializer for struct element doesn't match struct element type!");
 282     OL->init(C, this);
 283   }
 284 }
 285
 286 ConstantStruct::~ConstantStruct() {
 287   delete [] OperandList;
 288 }
 289
 290
 291 ConstantPacked::ConstantPacked(const PackedType *T,
 292                                const std::vector<Constant*> &V)
 293   : Constant(T, ConstantPackedVal, new Use[V.size()], V.size()) {
 294   Use *OL = OperandList;
 295     for (std::vector<Constant*>::const_iterator I = V.begin(), E = V.end();
 296          I != E; ++I, ++OL) {
 297       Constant *C = *I;
 298       assert((C->getType() == T->getElementType() ||
 299             (T->isAbstract() &&
 300              C->getType()->getTypeID() == T->getElementType()->getTypeID())) &&
 301            "Initializer for packed element doesn't match packed element type!");
 302     OL->init(C, this);
 303   }
 304 }
 305
 306 ConstantPacked::~ConstantPacked() {
 307   delete [] OperandList;
 308 }
 309
 310 /// UnaryConstantExpr - This class is private to Constants.cpp, and is used
 311 /// behind the scenes to implement unary constant exprs.
 312 namespace {
 313 class VISIBILITY_HIDDEN UnaryConstantExpr : public ConstantExpr {
 314   Use Op;
 315 public:
 316   UnaryConstantExpr(unsigned Opcode, Constant *C, const Type *Ty)
 317     : ConstantExpr(Ty, Opcode, &Op, 1), Op(C, this) {}
 318 };
 319 }
 320
 321 static bool isSetCC(unsigned Opcode) {
 322   return Opcode == Instruction::SetEQ || Opcode == Instruction::SetNE ||
 323          Opcode == Instruction::SetLT || Opcode == Instruction::SetGT ||
 324          Opcode == Instruction::SetLE || Opcode == Instruction::SetGE;
 325 }
 326
 327 /// BinaryConstantExpr - This class is private to Constants.cpp, and is used
 328 /// behind the scenes to implement binary constant exprs.
 329 namespace {
 330 class VISIBILITY_HIDDEN BinaryConstantExpr : public ConstantExpr {
 331   Use Ops[2];
 332 public:
 333   BinaryConstantExpr(unsigned Opcode, Constant *C1, Constant *C2)
 334     : ConstantExpr(isSetCC(Opcode) ? Type::BoolTy : C1->getType(),
 335                    Opcode, Ops, 2) {
 336     Ops[0].init(C1, this);
 337     Ops[1].init(C2, this);
 338   }
 339 };
 340 }
 341
 342 /// SelectConstantExpr - This class is private to Constants.cpp, and is used
 343 /// behind the scenes to implement select constant exprs.
 344 namespace {
 345 class VISIBILITY_HIDDEN SelectConstantExpr : public ConstantExpr {
 346   Use Ops[3];
 347 public:
 348   SelectConstantExpr(Constant *C1, Constant *C2, Constant *C3)
 349     : ConstantExpr(C2->getType(), Instruction::Select, Ops, 3) {
 350     Ops[0].init(C1, this);
 351     Ops[1].init(C2, this);
 352     Ops[2].init(C3, this);
 353   }
 354 };
 355 }
 356
 357 /// ExtractElementConstantExpr - This class is private to
 358 /// Constants.cpp, and is used behind the scenes to implement
 359 /// extractelement constant exprs.
 360 namespace {
 361 class VISIBILITY_HIDDEN ExtractElementConstantExpr : public ConstantExpr {
 362   Use Ops[2];
 363 public:
 364   ExtractElementConstantExpr(Constant *C1, Constant *C2)
 365     : ConstantExpr(cast<PackedType>(C1->getType())->getElementType(),
 366                    Instruction::ExtractElement, Ops, 2) {
 367     Ops[0].init(C1, this);
 368     Ops[1].init(C2, this);
 369   }
 370 };
 371 }
 372
 373 /// InsertElementConstantExpr - This class is private to
 374 /// Constants.cpp, and is used behind the scenes to implement
 375 /// insertelement constant exprs.
 376 namespace {
 377 class VISIBILITY_HIDDEN InsertElementConstantExpr : public ConstantExpr {
 378   Use Ops[3];
 379 public:
 380   InsertElementConstantExpr(Constant *C1, Constant *C2, Constant *C3)
 381     : ConstantExpr(C1->getType(), Instruction::InsertElement,
 382                    Ops, 3) {
 383     Ops[0].init(C1, this);
 384     Ops[1].init(C2, this);
 385     Ops[2].init(C3, this);
 386   }
 387 };
 388 }
 389
 390 /// ShuffleVectorConstantExpr - This class is private to
 391 /// Constants.cpp, and is used behind the scenes to implement
 392 /// shufflevector constant exprs.
 393 namespace {
 394 class VISIBILITY_HIDDEN ShuffleVectorConstantExpr : public ConstantExpr {
 395   Use Ops[3];
 396 public:
 397   ShuffleVectorConstantExpr(Constant *C1, Constant *C2, Constant *C3)
 398   : ConstantExpr(C1->getType(), Instruction::ShuffleVector,
 399                  Ops, 3) {
 400     Ops[0].init(C1, this);
 401     Ops[1].init(C2, this);
 402     Ops[2].init(C3, this);
 403   }
 404 };
 405 }
 406
 407 /// GetElementPtrConstantExpr - This class is private to Constants.cpp, and is
 408 /// used behind the scenes to implement getelementpr constant exprs.
 409 namespace {
 410 struct VISIBILITY_HIDDEN GetElementPtrConstantExpr : public ConstantExpr {
 411   GetElementPtrConstantExpr(Constant *C, const std::vector<Constant*> &IdxList,
 412                             const Type *DestTy)
 413     : ConstantExpr(DestTy, Instruction::GetElementPtr,
 414                    new Use[IdxList.size()+1], IdxList.size()+1) {
 415     OperandList[0].init(C, this);
 416     for (unsigned i = 0, E = IdxList.size(); i != E; ++i)
 417       OperandList[i+1].init(IdxList[i], this);
 418   }
 419   ~GetElementPtrConstantExpr() {
 420     delete [] OperandList;
 421   }
 422 };
 423 }
 424
 425 /// ConstantExpr::get* - Return some common constants without having to
 426 /// specify the full Instruction::OPCODE identifier.
 427 ///
 428 Constant *ConstantExpr::getNeg(Constant *C) {
 429   if (!C->getType()->isFloatingPoint())
 430     return get(Instruction::Sub, getNullValue(C->getType()), C);
 431   else
 432     return get(Instruction::Sub, ConstantFP::get(C->getType(), -0.0), C);
 433 }
 434 Constant *ConstantExpr::getNot(Constant *C) {
 435   assert(isa<ConstantIntegral>(C) && "Cannot NOT a nonintegral type!");
 436   return get(Instruction::Xor, C,
 437              ConstantIntegral::getAllOnesValue(C->getType()));
 438 }
 439 Constant *ConstantExpr::getAdd(Constant *C1, Constant *C2) {
 440   return get(Instruction::Add, C1, C2);
 441 }
 442 Constant *ConstantExpr::getSub(Constant *C1, Constant *C2) {
 443   return get(Instruction::Sub, C1, C2);
 444 }
 445 Constant *ConstantExpr::getMul(Constant *C1, Constant *C2) {
 446   return get(Instruction::Mul, C1, C2);
 447 }
 448 Constant *ConstantExpr::getDiv(Constant *C1, Constant *C2) {
 449   return get(Instruction::Div, C1, C2);
 450 }
 451 Constant *ConstantExpr::getRem(Constant *C1, Constant *C2) {
 452   return get(Instruction::Rem, C1, C2);
 453 }
 454 Constant *ConstantExpr::getAnd(Constant *C1, Constant *C2) {
 455   return get(Instruction::And, C1, C2);
 456 }
 457 Constant *ConstantExpr::getOr(Constant *C1, Constant *C2) {
 458   return get(Instruction::Or, C1, C2);
 459 }
 460 Constant *ConstantExpr::getXor(Constant *C1, Constant *C2) {
 461   return get(Instruction::Xor, C1, C2);
 462 }
 463 Constant *ConstantExpr::getSetEQ(Constant *C1, Constant *C2) {
 464   return get(Instruction::SetEQ, C1, C2);
 465 }
 466 Constant *ConstantExpr::getSetNE(Constant *C1, Constant *C2) {
 467   return get(Instruction::SetNE, C1, C2);
 468 }
 469 Constant *ConstantExpr::getSetLT(Constant *C1, Constant *C2) {
 470   return get(Instruction::SetLT, C1, C2);
 471 }
 472 Constant *ConstantExpr::getSetGT(Constant *C1, Constant *C2) {
 473   return get(Instruction::SetGT, C1, C2);
 474 }
 475 Constant *ConstantExpr::getSetLE(Constant *C1, Constant *C2) {
 476   return get(Instruction::SetLE, C1, C2);
 477 }
 478 Constant *ConstantExpr::getSetGE(Constant *C1, Constant *C2) {
 479   return get(Instruction::SetGE, C1, C2);
 480 }
 481 Constant *ConstantExpr::getShl(Constant *C1, Constant *C2) {
 482   return get(Instruction::Shl, C1, C2);
 483 }
 484 Constant *ConstantExpr::getShr(Constant *C1, Constant *C2) {
 485   return get(Instruction::Shr, C1, C2);
 486 }
 487
 488 Constant *ConstantExpr::getUShr(Constant *C1, Constant *C2) {
 489   if (C1->getType()->isUnsigned()) return getShr(C1, C2);
 490   return getCast(getShr(getCast(C1,
 491                     C1->getType()->getUnsignedVersion()), C2), C1->getType());
 492 }
 493
 494 Constant *ConstantExpr::getSShr(Constant *C1, Constant *C2) {
 495   if (C1->getType()->isSigned()) return getShr(C1, C2);
 496   return getCast(getShr(getCast(C1,
 497                         C1->getType()->getSignedVersion()), C2), C1->getType());
 498 }
 499
 500
 501 //===----------------------------------------------------------------------===//
 502 //                      isValueValidForType implementations
 503
 504 bool ConstantSInt::isValueValidForType(const Type *Ty, int64_t Val) {
 505   switch (Ty->getTypeID()) {
 506   default:
 507     return false;         // These can't be represented as integers!!!
 508     // Signed types...
 509   case Type::SByteTyID:
 510     return (Val <= INT8_MAX && Val >= INT8_MIN);
 511   case Type::ShortTyID:
 512     return (Val <= INT16_MAX && Val >= INT16_MIN);
 513   case Type::IntTyID:
 514     return (Val <= int(INT32_MAX) && Val >= int(INT32_MIN));
 515   case Type::LongTyID:
 516     return true;          // This is the largest type...
 517   }
 518 }
 519
 520 bool ConstantUInt::isValueValidForType(const Type *Ty, uint64_t Val) {
 521   switch (Ty->getTypeID()) {
 522   default:
 523     return false;         // These can't be represented as integers!!!
 524
 525     // Unsigned types...
 526   case Type::UByteTyID:
 527     return (Val <= UINT8_MAX);
 528   case Type::UShortTyID:
 529     return (Val <= UINT16_MAX);
 530   case Type::UIntTyID:
 531     return (Val <= UINT32_MAX);
 532   case Type::ULongTyID:
 533     return true;          // This is the largest type...
 534   }
 535 }
 536
 537 bool ConstantFP::isValueValidForType(const Type *Ty, double Val) {
 538   switch (Ty->getTypeID()) {
 539   default:
 540     return false;         // These can't be represented as floating point!
 541
 542     // TODO: Figure out how to test if a double can be cast to a float!
 543   case Type::FloatTyID:
 544   case Type::DoubleTyID:
 545     return true;          // This is the largest type...
 546   }
 547 }
 548
 549 //===----------------------------------------------------------------------===//
 550 //                      Factory Function Implementation
 551
 552 // ConstantCreator - A class that is used to create constants by
 553 // ValueMap*.  This class should be partially specialized if there is
 554 // something strange that needs to be done to interface to the ctor for the
 555 // constant.
 556 //
 557 namespace llvm {
 558   template<class ConstantClass, class TypeClass, class ValType>
 559   struct VISIBILITY_HIDDEN ConstantCreator {
 560     static ConstantClass *create(const TypeClass *Ty, const ValType &V) {
 561       return new ConstantClass(Ty, V);
 562     }
 563   };
 564
 565   template<class ConstantClass, class TypeClass>
 566   struct VISIBILITY_HIDDEN ConvertConstantType {
 567     static void convert(ConstantClass *OldC, const TypeClass *NewTy) {
 568       assert(0 && "This type cannot be converted!\n");
 569       abort();
 570     }
 571   };
 572 }
 573
 574 namespace {
 575   template<class ValType, class TypeClass, class ConstantClass,
 576            bool HasLargeKey = false  /*true for arrays and structs*/ >
 577   class VISIBILITY_HIDDEN ValueMap : public AbstractTypeUser {
 578   public:
 579     typedef std::pair<const TypeClass*, ValType> MapKey;
 580     typedef std::map<MapKey, ConstantClass *> MapTy;
 581     typedef typename MapTy::iterator MapIterator;
 582   private:
 583     /// Map - This is the main map from the element descriptor to the Constants.
 584     /// This is the primary way we avoid creating two of the same shape
 585     /// constant.
 586     MapTy Map;
 587
 588     /// InverseMap - If "HasLargeKey" is true, this contains an inverse mapping
 589     /// from the constants to their element in Map.  This is important for
 590     /// removal of constants from the array, which would otherwise have to scan
 591     /// through the map with very large keys.
 592     std::map<ConstantClass*, MapIterator> InverseMap;
 593
 594     typedef std::map<const TypeClass*, MapIterator> AbstractTypeMapTy;
 595     AbstractTypeMapTy AbstractTypeMap;
 596
 597     friend void Constant::clearAllValueMaps();
 598   private:
 599     void clear(std::vector<Constant *> &Constants) {
 600       for(MapIterator I = Map.begin(); I != Map.end(); ++I)
 601         Constants.push_back(I->second);
 602       Map.clear();
 603       AbstractTypeMap.clear();
 604       InverseMap.clear();
 605     }
 606
 607   public:
 608     MapIterator map_end() { return Map.end(); }
 609
 610     /// InsertOrGetItem - Return an iterator for the specified element.
 611     /// If the element exists in the map, the returned iterator points to the
 612     /// entry and Exists=true.  If not, the iterator points to the newly
 613     /// inserted entry and returns Exists=false.  Newly inserted entries have
 614     /// I->second == 0, and should be filled in.
 615     MapIterator InsertOrGetItem(std::pair<MapKey, ConstantClass *> &InsertVal,
 616                                    bool &Exists) {
 617       std::pair<MapIterator, bool> IP = Map.insert(InsertVal);
 618       Exists = !IP.second;
 619       return IP.first;
 620     }
 621
 622 private:
 623     MapIterator FindExistingElement(ConstantClass *CP) {
 624       if (HasLargeKey) {
 625         typename std::map<ConstantClass*, MapIterator>::iterator
 626             IMI = InverseMap.find(CP);
 627         assert(IMI != InverseMap.end() && IMI->second != Map.end() &&
 628                IMI->second->second == CP &&
 629                "InverseMap corrupt!");
 630         return IMI->second;
 631       }
 632
 633       MapIterator I =
 634         Map.find(MapKey((TypeClass*)CP->getRawType(), getValType(CP)));
 635       if (I == Map.end() || I->second != CP) {
 636         // FIXME: This should not use a linear scan.  If this gets to be a
 637         // performance problem, someone should look at this.
 638         for (I = Map.begin(); I != Map.end() && I->second != CP; ++I)
 639           /* empty */;
 640       }
 641       return I;
 642     }
 643 public:
 644
 645     /// getOrCreate - Return the specified constant from the map, creating it if
 646     /// necessary.
 647     ConstantClass *getOrCreate(const TypeClass *Ty, const ValType &V) {
 648       MapKey Lookup(Ty, V);
 649       MapIterator I = Map.lower_bound(Lookup);
 650       if (I != Map.end() && I->first == Lookup)
 651         return I->second;  // Is it in the map?
 652
 653       // If no preexisting value, create one now...
 654       ConstantClass *Result =
 655         ConstantCreator<ConstantClass,TypeClass,ValType>::create(Ty, V);
 656
 657       /// FIXME: why does this assert fail when loading 176.gcc?
 658       //assert(Result->getType() == Ty && "Type specified is not correct!");
 659       I = Map.insert(I, std::make_pair(MapKey(Ty, V), Result));
 660
 661       if (HasLargeKey)  // Remember the reverse mapping if needed.
 662         InverseMap.insert(std::make_pair(Result, I));
 663
 664       // If the type of the constant is abstract, make sure that an entry exists
 665       // for it in the AbstractTypeMap.
 666       if (Ty->isAbstract()) {
 667         typename AbstractTypeMapTy::iterator TI =
 668           AbstractTypeMap.lower_bound(Ty);
 669
 670         if (TI == AbstractTypeMap.end() || TI->first != Ty) {
 671           // Add ourselves to the ATU list of the type.
 672           cast<DerivedType>(Ty)->addAbstractTypeUser(this);
 673
 674           AbstractTypeMap.insert(TI, std::make_pair(Ty, I));
 675         }
 676       }
 677       return Result;
 678     }
 679
 680     void remove(ConstantClass *CP) {
 681       MapIterator I = FindExistingElement(CP);
 682       assert(I != Map.end() && "Constant not found in constant table!");
 683       assert(I->second == CP && "Didn't find correct element?");
 684
 685       if (HasLargeKey)  // Remember the reverse mapping if needed.
 686         InverseMap.erase(CP);
 687
 688       // Now that we found the entry, make sure this isn't the entry that
 689       // the AbstractTypeMap points to.
 690       const TypeClass *Ty = I->first.first;
 691       if (Ty->isAbstract()) {
 692         assert(AbstractTypeMap.count(Ty) &&
 693                "Abstract type not in AbstractTypeMap?");
 694         MapIterator &ATMEntryIt = AbstractTypeMap[Ty];
 695         if (ATMEntryIt == I) {
 696           // Yes, we are removing the representative entry for this type.
 697           // See if there are any other entries of the same type.
 698           MapIterator TmpIt = ATMEntryIt;
 699
 700           // First check the entry before this one...
 701           if (TmpIt != Map.begin()) {
 702             --TmpIt;
 703             if (TmpIt->first.first != Ty) // Not the same type, move back...
 704               ++TmpIt;
 705           }
 706
 707           // If we didn't find the same type, try to move forward...
 708           if (TmpIt == ATMEntryIt) {
 709             ++TmpIt;
 710             if (TmpIt == Map.end() || TmpIt->first.first != Ty)
 711               --TmpIt;   // No entry afterwards with the same type
 712           }
 713
 714           // If there is another entry in the map of the same abstract type,
 715           // update the AbstractTypeMap entry now.
 716           if (TmpIt != ATMEntryIt) {
 717             ATMEntryIt = TmpIt;
 718           } else {
 719             // Otherwise, we are removing the last instance of this type
 720             // from the table.  Remove from the ATM, and from user list.
 721             cast<DerivedType>(Ty)->removeAbstractTypeUser(this);
 722             AbstractTypeMap.erase(Ty);
 723           }
 724         }
 725       }
 726
 727       Map.erase(I);
 728     }
 729
 730
 731     /// MoveConstantToNewSlot - If we are about to change C to be the element
 732     /// specified by I, update our internal data structures to reflect this
 733     /// fact.
 734     void MoveConstantToNewSlot(ConstantClass *C, MapIterator I) {
 735       // First, remove the old location of the specified constant in the map.
 736       MapIterator OldI = FindExistingElement(C);
 737       assert(OldI != Map.end() && "Constant not found in constant table!");
 738       assert(OldI->second == C && "Didn't find correct element?");
 739
 740       // If this constant is the representative element for its abstract type,
 741       // update the AbstractTypeMap so that the representative element is I.
 742       if (C->getType()->isAbstract()) {
 743         typename AbstractTypeMapTy::iterator ATI =
 744             AbstractTypeMap.find(C->getType());
 745         assert(ATI != AbstractTypeMap.end() &&
 746                "Abstract type not in AbstractTypeMap?");
 747         if (ATI->second == OldI)
 748           ATI->second = I;
 749       }
 750
 751       // Remove the old entry from the map.
 752       Map.erase(OldI);
 753
 754       // Update the inverse map so that we know that this constant is now
 755       // located at descriptor I.
 756       if (HasLargeKey) {
 757         assert(I->second == C && "Bad inversemap entry!");
 758         InverseMap[C] = I;
 759       }
 760     }
 761
 762     void refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
 763       typename AbstractTypeMapTy::iterator I =
 764         AbstractTypeMap.find(cast<TypeClass>(OldTy));
 765
 766       assert(I != AbstractTypeMap.end() &&
 767              "Abstract type not in AbstractTypeMap?");
 768
 769       // Convert a constant at a time until the last one is gone.  The last one
 770       // leaving will remove() itself, causing the AbstractTypeMapEntry to be
 771       // eliminated eventually.
 772       do {
 773         ConvertConstantType<ConstantClass,
 774                             TypeClass>::convert(I->second->second,
 775                                                 cast<TypeClass>(NewTy));
 776
 777         I = AbstractTypeMap.find(cast<TypeClass>(OldTy));
 778       } while (I != AbstractTypeMap.end());
 779     }
 780
 781     // If the type became concrete without being refined to any other existing
 782     // type, we just remove ourselves from the ATU list.
 783     void typeBecameConcrete(const DerivedType *AbsTy) {
 784       AbsTy->removeAbstractTypeUser(this);
 785     }
 786
 787     void dump() const {
 788       std::cerr << "Constant.cpp: ValueMap\n";
 789     }
 790   };
 791 }
 792
 793 //---- ConstantUInt::get() and ConstantSInt::get() implementations...
 794 //
 795 static ValueMap< int64_t, Type, ConstantSInt> SIntConstants;
 796 static ValueMap<uint64_t, Type, ConstantUInt> UIntConstants;
 797
 798 ConstantSInt *ConstantSInt::get(const Type *Ty, int64_t V) {
 799   return SIntConstants.getOrCreate(Ty, V);
 800 }
 801
 802 ConstantUInt *ConstantUInt::get(const Type *Ty, uint64_t V) {
 803   return UIntConstants.getOrCreate(Ty, V);
 804 }
 805
 806 ConstantInt *ConstantInt::get(const Type *Ty, unsigned char V) {
 807   assert(V <= 127 && "Can only be used with very small positive constants!");
 808   if (Ty->isSigned()) return ConstantSInt::get(Ty, V);
 809   return ConstantUInt::get(Ty, V);
 810 }
 811
 812 //---- ConstantFP::get() implementation...
 813 //
 814 namespace llvm {
 815   template<>
 816   struct ConstantCreator<ConstantFP, Type, uint64_t> {
 817     static ConstantFP *create(const Type *Ty, uint64_t V) {
 818       assert(Ty == Type::DoubleTy);
 819       return new ConstantFP(Ty, BitsToDouble(V));
 820     }
 821   };
 822   template<>
 823   struct ConstantCreator<ConstantFP, Type, uint32_t> {
 824     static ConstantFP *create(const Type *Ty, uint32_t V) {
 825       assert(Ty == Type::FloatTy);
 826       return new ConstantFP(Ty, BitsToFloat(V));
 827     }
 828   };
 829 }
 830
 831 static ValueMap<uint64_t, Type, ConstantFP> DoubleConstants;
 832 static ValueMap<uint32_t, Type, ConstantFP> FloatConstants;
 833
 834 bool ConstantFP::isNullValue() const {
 835   return DoubleToBits(Val) == 0;
 836 }
 837
 838 bool ConstantFP::isExactlyValue(double V) const {
 839   return DoubleToBits(V) == DoubleToBits(Val);
 840 }
 841
 842
 843 ConstantFP *ConstantFP::get(const Type *Ty, double V) {
 844   if (Ty == Type::FloatTy) {
 845     // Force the value through memory to normalize it.
 846     return FloatConstants.getOrCreate(Ty, FloatToBits(V));
 847   } else {
 848     assert(Ty == Type::DoubleTy);
 849     return DoubleConstants.getOrCreate(Ty, DoubleToBits(V));
 850   }
 851 }
 852
 853 //---- ConstantAggregateZero::get() implementation...
 854 //
 855 namespace llvm {
 856   // ConstantAggregateZero does not take extra "value" argument...
 857   template<class ValType>
 858   struct ConstantCreator<ConstantAggregateZero, Type, ValType> {
 859     static ConstantAggregateZero *create(const Type *Ty, const ValType &V){
 860       return new ConstantAggregateZero(Ty);
 861     }
 862   };
 863
 864   template<>
 865   struct ConvertConstantType<ConstantAggregateZero, Type> {
 866     static void convert(ConstantAggregateZero *OldC, const Type *NewTy) {
 867       // Make everyone now use a constant of the new type...
 868       Constant *New = ConstantAggregateZero::get(NewTy);
 869       assert(New != OldC && "Didn't replace constant??");
 870       OldC->uncheckedReplaceAllUsesWith(New);
 871       OldC->destroyConstant();     // This constant is now dead, destroy it.
 872     }
 873   };
 874 }
 875
 876 static ValueMap<char, Type, ConstantAggregateZero> AggZeroConstants;
 877
 878 static char getValType(ConstantAggregateZero *CPZ) { return 0; }
 879
 880 Constant *ConstantAggregateZero::get(const Type *Ty) {
 881   assert((isa<StructType>(Ty) || isa<ArrayType>(Ty) || isa<PackedType>(Ty)) &&
 882          "Cannot create an aggregate zero of non-aggregate type!");
 883   return AggZeroConstants.getOrCreate(Ty, 0);
 884 }
 885
 886 // destroyConstant - Remove the constant from the constant table...
 887 //
 888 void ConstantAggregateZero::destroyConstant() {
 889   AggZeroConstants.remove(this);
 890   destroyConstantImpl();
 891 }
 892
 893 //---- ConstantArray::get() implementation...
 894 //
 895 namespace llvm {
 896   template<>
 897   struct ConvertConstantType<ConstantArray, ArrayType> {
 898     static void convert(ConstantArray *OldC, const ArrayType *NewTy) {
 899       // Make everyone now use a constant of the new type...
 900       std::vector<Constant*> C;
 901       for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i)
 902         C.push_back(cast<Constant>(OldC->getOperand(i)));
 903       Constant *New = ConstantArray::get(NewTy, C);
 904       assert(New != OldC && "Didn't replace constant??");
 905       OldC->uncheckedReplaceAllUsesWith(New);
 906       OldC->destroyConstant();    // This constant is now dead, destroy it.
 907     }
 908   };
 909 }
 910
 911 static std::vector<Constant*> getValType(ConstantArray *CA) {
 912   std::vector<Constant*> Elements;
 913   Elements.reserve(CA->getNumOperands());
 914   for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i)
 915     Elements.push_back(cast<Constant>(CA->getOperand(i)));
 916   return Elements;
 917 }
 918
 919 typedef ValueMap<std::vector<Constant*>, ArrayType,
 920                  ConstantArray, true /*largekey*/> ArrayConstantsTy;
 921 static ArrayConstantsTy ArrayConstants;
 922
 923 Constant *ConstantArray::get(const ArrayType *Ty,
 924                              const std::vector<Constant*> &V) {
 925   // If this is an all-zero array, return a ConstantAggregateZero object
 926   if (!V.empty()) {
 927     Constant *C = V[0];
 928     if (!C->isNullValue())
 929       return ArrayConstants.getOrCreate(Ty, V);
 930     for (unsigned i = 1, e = V.size(); i != e; ++i)
 931       if (V[i] != C)
 932         return ArrayConstants.getOrCreate(Ty, V);
 933   }
 934   return ConstantAggregateZero::get(Ty);
 935 }
 936
 937 // destroyConstant - Remove the constant from the constant table...
 938 //
 939 void ConstantArray::destroyConstant() {
 940   ArrayConstants.remove(this);
 941   destroyConstantImpl();
 942 }
 943
 944 /// ConstantArray::get(const string&) - Return an array that is initialized to
 945 /// contain the specified string.  If length is zero then a null terminator is
 946 /// added to the specified string so that it may be used in a natural way.
 947 /// Otherwise, the length parameter specifies how much of the string to use
 948 /// and it won't be null terminated.
 949 ///
 950 Constant *ConstantArray::get(const std::string &Str, bool AddNull) {
 951   std::vector<Constant*> ElementVals;
 952   for (unsigned i = 0; i < Str.length(); ++i)
 953     ElementVals.push_back(ConstantSInt::get(Type::SByteTy, Str[i]));
 954
 955   // Add a null terminator to the string...
 956   if (AddNull) {
 957     ElementVals.push_back(ConstantSInt::get(Type::SByteTy, 0));
 958   }
 959
 960   ArrayType *ATy = ArrayType::get(Type::SByteTy, ElementVals.size());
 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 typedef ValueMap<std::vector<Constant*>, StructType,
1013                  ConstantStruct, true /*largekey*/> StructConstantsTy;
1014 static StructConstantsTy StructConstants;
1015
1016 static std::vector<Constant*> getValType(ConstantStruct *CS) {
1017   std::vector<Constant*> Elements;
1018   Elements.reserve(CS->getNumOperands());
1019   for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i)
1020     Elements.push_back(cast<Constant>(CS->getOperand(i)));
1021   return Elements;
1022 }
1023
1024 Constant *ConstantStruct::get(const StructType *Ty,
1025                               const std::vector<Constant*> &V) {
1026   // Create a ConstantAggregateZero value if all elements are zeros...
1027   for (unsigned i = 0, e = V.size(); i != e; ++i)
1028     if (!V[i]->isNullValue())
1029       return StructConstants.getOrCreate(Ty, V);
1030
1031   return ConstantAggregateZero::get(Ty);
1032 }
1033
1034 Constant *ConstantStruct::get(const std::vector<Constant*> &V) {
1035   std::vector<const Type*> StructEls;
1036   StructEls.reserve(V.size());
1037   for (unsigned i = 0, e = V.size(); i != e; ++i)
1038     StructEls.push_back(V[i]->getType());
1039   return get(StructType::get(StructEls), V);
1040 }
1041
1042 // destroyConstant - Remove the constant from the constant table...
1043 //
1044 void ConstantStruct::destroyConstant() {
1045   StructConstants.remove(this);
1046   destroyConstantImpl();
1047 }
1048
1049 //---- ConstantPacked::get() implementation...
1050 //
1051 namespace llvm {
1052   template<>
1053   struct ConvertConstantType<ConstantPacked, PackedType> {
1054     static void convert(ConstantPacked *OldC, const PackedType *NewTy) {
1055       // Make everyone now use a constant of the new type...
1056       std::vector<Constant*> C;
1057       for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i)
1058         C.push_back(cast<Constant>(OldC->getOperand(i)));
1059       Constant *New = ConstantPacked::get(NewTy, C);
1060       assert(New != OldC && "Didn't replace constant??");
1061       OldC->uncheckedReplaceAllUsesWith(New);
1062       OldC->destroyConstant();    // This constant is now dead, destroy it.
1063     }
1064   };
1065 }
1066
1067 static std::vector<Constant*> getValType(ConstantPacked *CP) {
1068   std::vector<Constant*> Elements;
1069   Elements.reserve(CP->getNumOperands());
1070   for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i)
1071     Elements.push_back(CP->getOperand(i));
1072   return Elements;
1073 }
1074
1075 static ValueMap<std::vector<Constant*>, PackedType,
1076                 ConstantPacked> PackedConstants;
1077
1078 Constant *ConstantPacked::get(const PackedType *Ty,
1079                               const std::vector<Constant*> &V) {
1080   // If this is an all-zero packed, return a ConstantAggregateZero object
1081   if (!V.empty()) {
1082     Constant *C = V[0];
1083     if (!C->isNullValue())
1084       return PackedConstants.getOrCreate(Ty, V);
1085     for (unsigned i = 1, e = V.size(); i != e; ++i)
1086       if (V[i] != C)
1087         return PackedConstants.getOrCreate(Ty, V);
1088   }
1089   return ConstantAggregateZero::get(Ty);
1090 }
1091
1092 Constant *ConstantPacked::get(const std::vector<Constant*> &V) {
1093   assert(!V.empty() && "Cannot infer type if V is empty");
1094   return get(PackedType::get(V.front()->getType(),V.size()), V);
1095 }
1096
1097 // destroyConstant - Remove the constant from the constant table...
1098 //
1099 void ConstantPacked::destroyConstant() {
1100   PackedConstants.remove(this);
1101   destroyConstantImpl();
1102 }
1103
1104 //---- ConstantPointerNull::get() implementation...
1105 //
1106
1107 namespace llvm {
1108   // ConstantPointerNull does not take extra "value" argument...
1109   template<class ValType>
1110   struct ConstantCreator<ConstantPointerNull, PointerType, ValType> {
1111     static ConstantPointerNull *create(const PointerType *Ty, const ValType &V){
1112       return new ConstantPointerNull(Ty);
1113     }
1114   };
1115
1116   template<>
1117   struct ConvertConstantType<ConstantPointerNull, PointerType> {
1118     static void convert(ConstantPointerNull *OldC, const PointerType *NewTy) {
1119       // Make everyone now use a constant of the new type...
1120       Constant *New = ConstantPointerNull::get(NewTy);
1121       assert(New != OldC && "Didn't replace constant??");
1122       OldC->uncheckedReplaceAllUsesWith(New);
1123       OldC->destroyConstant();     // This constant is now dead, destroy it.
1124     }
1125   };
1126 }
1127
1128 static ValueMap<char, PointerType, ConstantPointerNull> NullPtrConstants;
1129
1130 static char getValType(ConstantPointerNull *) {
1131   return 0;
1132 }
1133
1134
1135 ConstantPointerNull *ConstantPointerNull::get(const PointerType *Ty) {
1136   return NullPtrConstants.getOrCreate(Ty, 0);
1137 }
1138
1139 // destroyConstant - Remove the constant from the constant table...
1140 //
1141 void ConstantPointerNull::destroyConstant() {
1142   NullPtrConstants.remove(this);
1143   destroyConstantImpl();
1144 }
1145
1146
1147 //---- UndefValue::get() implementation...
1148 //
1149
1150 namespace llvm {
1151   // UndefValue does not take extra "value" argument...
1152   template<class ValType>
1153   struct ConstantCreator<UndefValue, Type, ValType> {
1154     static UndefValue *create(const Type *Ty, const ValType &V) {
1155       return new UndefValue(Ty);
1156     }
1157   };
1158
1159   template<>
1160   struct ConvertConstantType<UndefValue, Type> {
1161     static void convert(UndefValue *OldC, const Type *NewTy) {
1162       // Make everyone now use a constant of the new type.
1163       Constant *New = UndefValue::get(NewTy);
1164       assert(New != OldC && "Didn't replace constant??");
1165       OldC->uncheckedReplaceAllUsesWith(New);
1166       OldC->destroyConstant();     // This constant is now dead, destroy it.
1167     }
1168   };
1169 }
1170
1171 static ValueMap<char, Type, UndefValue> UndefValueConstants;
1172
1173 static char getValType(UndefValue *) {
1174   return 0;
1175 }
1176
1177
1178 UndefValue *UndefValue::get(const Type *Ty) {
1179   return UndefValueConstants.getOrCreate(Ty, 0);
1180 }
1181
1182 // destroyConstant - Remove the constant from the constant table.
1183 //
1184 void UndefValue::destroyConstant() {
1185   UndefValueConstants.remove(this);
1186   destroyConstantImpl();
1187 }
1188
1189
1190
1191
1192 //---- ConstantExpr::get() implementations...
1193 //
1194 typedef std::pair<unsigned, std::vector<Constant*> > ExprMapKeyType;
1195
1196 namespace llvm {
1197   template<>
1198   struct ConstantCreator<ConstantExpr, Type, ExprMapKeyType> {
1199     static ConstantExpr *create(const Type *Ty, const ExprMapKeyType &V) {
1200       if (V.first == Instruction::Cast)
1201         return new UnaryConstantExpr(Instruction::Cast, V.second[0], Ty);
1202       if ((V.first >= Instruction::BinaryOpsBegin &&
1203            V.first < Instruction::BinaryOpsEnd) ||
1204           V.first == Instruction::Shl || V.first == Instruction::Shr)
1205         return new BinaryConstantExpr(V.first, V.second[0], V.second[1]);
1206       if (V.first == Instruction::Select)
1207         return new SelectConstantExpr(V.second[0], V.second[1], V.second[2]);
1208       if (V.first == Instruction::ExtractElement)
1209         return new ExtractElementConstantExpr(V.second[0], V.second[1]);
1210       if (V.first == Instruction::InsertElement)
1211         return new InsertElementConstantExpr(V.second[0], V.second[1],
1212                                              V.second[2]);
1213       if (V.first == Instruction::ShuffleVector)
1214         return new ShuffleVectorConstantExpr(V.second[0], V.second[1],
1215                                              V.second[2]);
1216
1217       assert(V.first == Instruction::GetElementPtr && "Invalid ConstantExpr!");
1218
1219       std::vector<Constant*> IdxList(V.second.begin()+1, V.second.end());
1220       return new GetElementPtrConstantExpr(V.second[0], IdxList, Ty);
1221     }
1222   };
1223
1224   template<>
1225   struct ConvertConstantType<ConstantExpr, Type> {
1226     static void convert(ConstantExpr *OldC, const Type *NewTy) {
1227       Constant *New;
1228       switch (OldC->getOpcode()) {
1229       case Instruction::Cast:
1230         New = ConstantExpr::getCast(OldC->getOperand(0), NewTy);
1231         break;
1232       case Instruction::Select:
1233         New = ConstantExpr::getSelectTy(NewTy, OldC->getOperand(0),
1234                                         OldC->getOperand(1),
1235                                         OldC->getOperand(2));
1236         break;
1237       case Instruction::Shl:
1238       case Instruction::Shr:
1239         New = ConstantExpr::getShiftTy(NewTy, OldC->getOpcode(),
1240                                      OldC->getOperand(0), OldC->getOperand(1));
1241         break;
1242       default:
1243         assert(OldC->getOpcode() >= Instruction::BinaryOpsBegin &&
1244                OldC->getOpcode() < Instruction::BinaryOpsEnd);
1245         New = ConstantExpr::getTy(NewTy, OldC->getOpcode(), OldC->getOperand(0),
1246                                   OldC->getOperand(1));
1247         break;
1248       case Instruction::GetElementPtr:
1249         // Make everyone now use a constant of the new type...
1250         std::vector<Value*> Idx(OldC->op_begin()+1, OldC->op_end());
1251         New = ConstantExpr::getGetElementPtrTy(NewTy, OldC->getOperand(0), Idx);
1252         break;
1253       }
1254
1255       assert(New != OldC && "Didn't replace constant??");
1256       OldC->uncheckedReplaceAllUsesWith(New);
1257       OldC->destroyConstant();    // This constant is now dead, destroy it.
1258     }
1259   };
1260 } // end namespace llvm
1261
1262
1263 static ExprMapKeyType getValType(ConstantExpr *CE) {
1264   std::vector<Constant*> Operands;
1265   Operands.reserve(CE->getNumOperands());
1266   for (unsigned i = 0, e = CE->getNumOperands(); i != e; ++i)
1267     Operands.push_back(cast<Constant>(CE->getOperand(i)));
1268   return ExprMapKeyType(CE->getOpcode(), Operands);
1269 }
1270
1271 static ValueMap<ExprMapKeyType, Type, ConstantExpr> ExprConstants;
1272
1273 Constant *ConstantExpr::getCast(Constant *C, const Type *Ty) {
1274   assert(Ty->isFirstClassType() && "Cannot cast to an aggregate type!");
1275
1276   if (Constant *FC = ConstantFoldCastInstruction(C, Ty))
1277     return FC;          // Fold a few common cases...
1278
1279   // Look up the constant in the table first to ensure uniqueness
1280   std::vector<Constant*> argVec(1, C);
1281   ExprMapKeyType Key = std::make_pair(Instruction::Cast, argVec);
1282   return ExprConstants.getOrCreate(Ty, Key);
1283 }
1284
1285 Constant *ConstantExpr::getSignExtend(Constant *C, const Type *Ty) {
1286   assert(C->getType()->isIntegral() && Ty->isIntegral() &&
1287          C->getType()->getPrimitiveSize() <= Ty->getPrimitiveSize() &&
1288          "This is an illegal sign extension!");
1289   if (C->getType() != Type::BoolTy) {
1290     C = ConstantExpr::getCast(C, C->getType()->getSignedVersion());
1291     return ConstantExpr::getCast(C, Ty);
1292   } else {
1293     if (C == ConstantBool::True)
1294       return ConstantIntegral::getAllOnesValue(Ty);
1295     else
1296       return ConstantIntegral::getNullValue(Ty);
1297   }
1298 }
1299
1300 Constant *ConstantExpr::getZeroExtend(Constant *C, const Type *Ty) {
1301   assert(C->getType()->isIntegral() && Ty->isIntegral() &&
1302          C->getType()->getPrimitiveSize() <= Ty->getPrimitiveSize() &&
1303          "This is an illegal zero extension!");
1304   if (C->getType() != Type::BoolTy)
1305     C = ConstantExpr::getCast(C, C->getType()->getUnsignedVersion());
1306   return ConstantExpr::getCast(C, Ty);
1307 }
1308
1309 Constant *ConstantExpr::getSizeOf(const Type *Ty) {
1310   // sizeof is implemented as: (ulong) gep (Ty*)null, 1
1311   return getCast(
1312     getGetElementPtr(getNullValue(PointerType::get(Ty)),
1313                  std::vector<Constant*>(1, ConstantInt::get(Type::UIntTy, 1))),
1314     Type::ULongTy);
1315 }
1316
1317 Constant *ConstantExpr::getPtrPtrFromArrayPtr(Constant *C) {
1318   // pointer from array is implemented as: getelementptr arr ptr, 0, 0
1319   static std::vector<Constant*> Indices(2, ConstantUInt::get(Type::UIntTy, 0));
1320
1321   return ConstantExpr::getGetElementPtr(C, Indices);
1322 }
1323
1324 Constant *ConstantExpr::getTy(const Type *ReqTy, unsigned Opcode,
1325                               Constant *C1, Constant *C2) {
1326   if (Opcode == Instruction::Shl || Opcode == Instruction::Shr)
1327     return getShiftTy(ReqTy, Opcode, C1, C2);
1328   // Check the operands for consistency first
1329   assert((Opcode >= Instruction::BinaryOpsBegin &&
1330           Opcode < Instruction::BinaryOpsEnd) &&
1331          "Invalid opcode in binary constant expression");
1332   assert(C1->getType() == C2->getType() &&
1333          "Operand types in binary constant expression should match");
1334
1335   if (ReqTy == C1->getType() || (Instruction::isRelational(Opcode) &&
1336                                  ReqTy == Type::BoolTy))
1337     if (Constant *FC = ConstantFoldBinaryInstruction(Opcode, C1, C2))
1338       return FC;          // Fold a few common cases...
1339
1340   std::vector<Constant*> argVec(1, C1); argVec.push_back(C2);
1341   ExprMapKeyType Key = std::make_pair(Opcode, argVec);
1342   return ExprConstants.getOrCreate(ReqTy, Key);
1343 }
1344
1345 Constant *ConstantExpr::get(unsigned Opcode, Constant *C1, Constant *C2) {
1346 #ifndef NDEBUG
1347   switch (Opcode) {
1348   case Instruction::Add: case Instruction::Sub:
1349   case Instruction::Mul: case Instruction::Div:
1350   case Instruction::Rem:
1351     assert(C1->getType() == C2->getType() && "Op types should be identical!");
1352     assert((C1->getType()->isInteger() || C1->getType()->isFloatingPoint() ||
1353             isa<PackedType>(C1->getType())) &&
1354            "Tried to create an arithmetic operation on a non-arithmetic type!");
1355     break;
1356   case Instruction::And:
1357   case Instruction::Or:
1358   case Instruction::Xor:
1359     assert(C1->getType() == C2->getType() && "Op types should be identical!");
1360     assert((C1->getType()->isIntegral() || isa<PackedType>(C1->getType())) &&
1361            "Tried to create a logical operation on a non-integral type!");
1362     break;
1363   case Instruction::SetLT: case Instruction::SetGT: case Instruction::SetLE:
1364   case Instruction::SetGE: case Instruction::SetEQ: case Instruction::SetNE:
1365     assert(C1->getType() == C2->getType() && "Op types should be identical!");
1366     break;
1367   case Instruction::Shl:
1368   case Instruction::Shr:
1369     assert(C2->getType() == Type::UByteTy && "Shift should be by ubyte!");
1370     assert((C1->getType()->isInteger() || isa<PackedType>(C1->getType())) &&
1371            "Tried to create a shift operation on a non-integer type!");
1372     break;
1373   default:
1374     break;
1375   }
1376 #endif
1377
1378   if (Instruction::isRelational(Opcode))
1379     return getTy(Type::BoolTy, Opcode, C1, C2);
1380   else
1381     return getTy(C1->getType(), Opcode, C1, C2);
1382 }
1383
1384 Constant *ConstantExpr::getSelectTy(const Type *ReqTy, Constant *C,
1385                                     Constant *V1, Constant *V2) {
1386   assert(C->getType() == Type::BoolTy && "Select condition must be bool!");
1387   assert(V1->getType() == V2->getType() && "Select value types must match!");
1388   assert(V1->getType()->isFirstClassType() && "Cannot select aggregate type!");
1389
1390   if (ReqTy == V1->getType())
1391     if (Constant *SC = ConstantFoldSelectInstruction(C, V1, V2))
1392       return SC;        // Fold common cases
1393
1394   std::vector<Constant*> argVec(3, C);
1395   argVec[1] = V1;
1396   argVec[2] = V2;
1397   ExprMapKeyType Key = std::make_pair(Instruction::Select, argVec);
1398   return ExprConstants.getOrCreate(ReqTy, Key);
1399 }
1400
1401 /// getShiftTy - Return a shift left or shift right constant expr
1402 Constant *ConstantExpr::getShiftTy(const Type *ReqTy, unsigned Opcode,
1403                                    Constant *C1, Constant *C2) {
1404   // Check the operands for consistency first
1405   assert((Opcode == Instruction::Shl ||
1406           Opcode == Instruction::Shr) &&
1407          "Invalid opcode in binary constant expression");
1408   assert(C1->getType()->isIntegral() && C2->getType() == Type::UByteTy &&
1409          "Invalid operand types for Shift constant expr!");
1410
1411   if (Constant *FC = ConstantFoldBinaryInstruction(Opcode, C1, C2))
1412     return FC;          // Fold a few common cases...
1413
1414   // Look up the constant in the table first to ensure uniqueness
1415   std::vector<Constant*> argVec(1, C1); argVec.push_back(C2);
1416   ExprMapKeyType Key = std::make_pair(Opcode, argVec);
1417   return ExprConstants.getOrCreate(ReqTy, Key);
1418 }
1419
1420
1421 Constant *ConstantExpr::getGetElementPtrTy(const Type *ReqTy, Constant *C,
1422                                            const std::vector<Value*> &IdxList) {
1423   assert(GetElementPtrInst::getIndexedType(C->getType(), IdxList, true) &&
1424          "GEP indices invalid!");
1425
1426   if (Constant *FC = ConstantFoldGetElementPtr(C, IdxList))
1427     return FC;          // Fold a few common cases...
1428
1429   assert(isa<PointerType>(C->getType()) &&
1430          "Non-pointer type for constant GetElementPtr expression");
1431   // Look up the constant in the table first to ensure uniqueness
1432   std::vector<Constant*> ArgVec;
1433   ArgVec.reserve(IdxList.size()+1);
1434   ArgVec.push_back(C);
1435   for (unsigned i = 0, e = IdxList.size(); i != e; ++i)
1436     ArgVec.push_back(cast<Constant>(IdxList[i]));
1437   const ExprMapKeyType &Key = std::make_pair(Instruction::GetElementPtr,ArgVec);
1438   return ExprConstants.getOrCreate(ReqTy, Key);
1439 }
1440
1441 Constant *ConstantExpr::getGetElementPtr(Constant *C,
1442                                          const std::vector<Constant*> &IdxList){
1443   // Get the result type of the getelementptr!
1444   std::vector<Value*> VIdxList(IdxList.begin(), IdxList.end());
1445
1446   const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), VIdxList,
1447                                                      true);
1448   assert(Ty && "GEP indices invalid!");
1449   return getGetElementPtrTy(PointerType::get(Ty), C, VIdxList);
1450 }
1451
1452 Constant *ConstantExpr::getGetElementPtr(Constant *C,
1453                                          const std::vector<Value*> &IdxList) {
1454   // Get the result type of the getelementptr!
1455   const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), IdxList,
1456                                                      true);
1457   assert(Ty && "GEP indices invalid!");
1458   return getGetElementPtrTy(PointerType::get(Ty), C, IdxList);
1459 }
1460
1461 Constant *ConstantExpr::getExtractElementTy(const Type *ReqTy, Constant *Val,
1462                                             Constant *Idx) {
1463   if (Constant *FC = ConstantFoldExtractElementInstruction(Val, Idx))
1464     return FC;          // Fold a few common cases...
1465   // Look up the constant in the table first to ensure uniqueness
1466   std::vector<Constant*> ArgVec(1, Val);
1467   ArgVec.push_back(Idx);
1468   const ExprMapKeyType &Key = std::make_pair(Instruction::ExtractElement,ArgVec);
1469   return ExprConstants.getOrCreate(ReqTy, Key);
1470 }
1471
1472 Constant *ConstantExpr::getExtractElement(Constant *Val, Constant *Idx) {
1473   assert(isa<PackedType>(Val->getType()) &&
1474          "Tried to create extractelement operation on non-packed type!");
1475   assert(Idx->getType() == Type::UIntTy &&
1476          "Extractelement index must be uint type!");
1477   return getExtractElementTy(cast<PackedType>(Val->getType())->getElementType(),
1478                              Val, Idx);
1479 }
1480
1481 Constant *ConstantExpr::getInsertElementTy(const Type *ReqTy, Constant *Val,
1482                                            Constant *Elt, Constant *Idx) {
1483   if (Constant *FC = ConstantFoldInsertElementInstruction(Val, Elt, Idx))
1484     return FC;          // Fold a few common cases...
1485   // Look up the constant in the table first to ensure uniqueness
1486   std::vector<Constant*> ArgVec(1, Val);
1487   ArgVec.push_back(Elt);
1488   ArgVec.push_back(Idx);
1489   const ExprMapKeyType &Key = std::make_pair(Instruction::InsertElement,ArgVec);
1490   return ExprConstants.getOrCreate(ReqTy, Key);
1491 }
1492
1493 Constant *ConstantExpr::getInsertElement(Constant *Val, Constant *Elt,
1494                                          Constant *Idx) {
1495   assert(isa<PackedType>(Val->getType()) &&
1496          "Tried to create insertelement operation on non-packed type!");
1497   assert(Elt->getType() == cast<PackedType>(Val->getType())->getElementType()
1498          && "Insertelement types must match!");
1499   assert(Idx->getType() == Type::UIntTy &&
1500          "Insertelement index must be uint type!");
1501   return getInsertElementTy(cast<PackedType>(Val->getType())->getElementType(),
1502                             Val, Elt, Idx);
1503 }
1504
1505 Constant *ConstantExpr::getShuffleVectorTy(const Type *ReqTy, Constant *V1,
1506                                            Constant *V2, Constant *Mask) {
1507   if (Constant *FC = ConstantFoldShuffleVectorInstruction(V1, V2, Mask))
1508     return FC;          // Fold a few common cases...
1509   // Look up the constant in the table first to ensure uniqueness
1510   std::vector<Constant*> ArgVec(1, V1);
1511   ArgVec.push_back(V2);
1512   ArgVec.push_back(Mask);
1513   const ExprMapKeyType &Key = std::make_pair(Instruction::ShuffleVector,ArgVec);
1514   return ExprConstants.getOrCreate(ReqTy, Key);
1515 }
1516
1517 Constant *ConstantExpr::getShuffleVector(Constant *V1, Constant *V2,
1518                                          Constant *Mask) {
1519   assert(ShuffleVectorInst::isValidOperands(V1, V2, Mask) &&
1520          "Invalid shuffle vector constant expr operands!");
1521   return getShuffleVectorTy(V1->getType(), V1, V2, Mask);
1522 }
1523
1524
1525 // destroyConstant - Remove the constant from the constant table...
1526 //
1527 void ConstantExpr::destroyConstant() {
1528   ExprConstants.remove(this);
1529   destroyConstantImpl();
1530 }
1531
1532 const char *ConstantExpr::getOpcodeName() const {
1533   return Instruction::getOpcodeName(getOpcode());
1534 }
1535
1536 //===----------------------------------------------------------------------===//
1537 //                replaceUsesOfWithOnConstant implementations
1538
1539 void ConstantArray::replaceUsesOfWithOnConstant(Value *From, Value *To,
1540                                                 Use *U) {
1541   assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
1542   Constant *ToC = cast<Constant>(To);
1543
1544   unsigned OperandToUpdate = U-OperandList;
1545   assert(getOperand(OperandToUpdate) == From && "ReplaceAllUsesWith broken!");
1546
1547   std::pair<ArrayConstantsTy::MapKey, ConstantArray*> Lookup;
1548   Lookup.first.first = getType();
1549   Lookup.second = this;
1550
1551   std::vector<Constant*> &Values = Lookup.first.second;
1552   Values.reserve(getNumOperands());  // Build replacement array.
1553
1554   // Fill values with the modified operands of the constant array.  Also,
1555   // compute whether this turns into an all-zeros array.
1556   bool isAllZeros = false;
1557   if (!ToC->isNullValue()) {
1558     for (Use *O = OperandList, *E = OperandList+getNumOperands(); O != E; ++O)
1559       Values.push_back(cast<Constant>(O->get()));
1560   } else {
1561     isAllZeros = true;
1562     for (Use *O = OperandList, *E = OperandList+getNumOperands(); O != E; ++O) {
1563       Constant *Val = cast<Constant>(O->get());
1564       Values.push_back(Val);
1565       if (isAllZeros) isAllZeros = Val->isNullValue();
1566     }
1567   }
1568   Values[OperandToUpdate] = ToC;
1569
1570   Constant *Replacement = 0;
1571   if (isAllZeros) {
1572     Replacement = ConstantAggregateZero::get(getType());
1573   } else {
1574     // Check to see if we have this array type already.
1575     bool Exists;
1576     ArrayConstantsTy::MapIterator I =
1577       ArrayConstants.InsertOrGetItem(Lookup, Exists);
1578
1579     if (Exists) {
1580       Replacement = I->second;
1581     } else {
1582       // Okay, the new shape doesn't exist in the system yet.  Instead of
1583       // creating a new constant array, inserting it, replaceallusesof'ing the
1584       // old with the new, then deleting the old... just update the current one
1585       // in place!
1586       ArrayConstants.MoveConstantToNewSlot(this, I);
1587
1588       // Update to the new value.
1589       setOperand(OperandToUpdate, ToC);
1590       return;
1591     }
1592   }
1593
1594   // Otherwise, I do need to replace this with an existing value.
1595   assert(Replacement != this && "I didn't contain From!");
1596
1597   // Everyone using this now uses the replacement.
1598   uncheckedReplaceAllUsesWith(Replacement);
1599
1600   // Delete the old constant!
1601   destroyConstant();
1602 }
1603
1604 void ConstantStruct::replaceUsesOfWithOnConstant(Value *From, Value *To,
1605                                                  Use *U) {
1606   assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
1607   Constant *ToC = cast<Constant>(To);
1608
1609   unsigned OperandToUpdate = U-OperandList;
1610   assert(getOperand(OperandToUpdate) == From && "ReplaceAllUsesWith broken!");
1611
1612   std::pair<StructConstantsTy::MapKey, ConstantStruct*> Lookup;
1613   Lookup.first.first = getType();
1614   Lookup.second = this;
1615   std::vector<Constant*> &Values = Lookup.first.second;
1616   Values.reserve(getNumOperands());  // Build replacement struct.
1617
1618
1619   // Fill values with the modified operands of the constant struct.  Also,
1620   // compute whether this turns into an all-zeros struct.
1621   bool isAllZeros = false;
1622   if (!ToC->isNullValue()) {
1623     for (Use *O = OperandList, *E = OperandList+getNumOperands(); O != E; ++O)
1624       Values.push_back(cast<Constant>(O->get()));
1625   } else {
1626     isAllZeros = true;
1627     for (Use *O = OperandList, *E = OperandList+getNumOperands(); O != E; ++O) {
1628       Constant *Val = cast<Constant>(O->get());
1629       Values.push_back(Val);
1630       if (isAllZeros) isAllZeros = Val->isNullValue();
1631     }
1632   }
1633   Values[OperandToUpdate] = ToC;
1634
1635   Constant *Replacement = 0;
1636   if (isAllZeros) {
1637     Replacement = ConstantAggregateZero::get(getType());
1638   } else {
1639     // Check to see if we have this array type already.
1640     bool Exists;
1641     StructConstantsTy::MapIterator I =
1642       StructConstants.InsertOrGetItem(Lookup, Exists);
1643
1644     if (Exists) {
1645       Replacement = I->second;
1646     } else {
1647       // Okay, the new shape doesn't exist in the system yet.  Instead of
1648       // creating a new constant struct, inserting it, replaceallusesof'ing the
1649       // old with the new, then deleting the old... just update the current one
1650       // in place!
1651       StructConstants.MoveConstantToNewSlot(this, I);
1652
1653       // Update to the new value.
1654       setOperand(OperandToUpdate, ToC);
1655       return;
1656     }
1657   }
1658
1659   assert(Replacement != this && "I didn't contain From!");
1660
1661   // Everyone using this now uses the replacement.
1662   uncheckedReplaceAllUsesWith(Replacement);
1663
1664   // Delete the old constant!
1665   destroyConstant();
1666 }
1667
1668 void ConstantPacked::replaceUsesOfWithOnConstant(Value *From, Value *To,
1669                                                  Use *U) {
1670   assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
1671
1672   std::vector<Constant*> Values;
1673   Values.reserve(getNumOperands());  // Build replacement array...
1674   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
1675     Constant *Val = getOperand(i);
1676     if (Val == From) Val = cast<Constant>(To);
1677     Values.push_back(Val);
1678   }
1679
1680   Constant *Replacement = ConstantPacked::get(getType(), Values);
1681   assert(Replacement != this && "I didn't contain From!");
1682
1683   // Everyone using this now uses the replacement.
1684   uncheckedReplaceAllUsesWith(Replacement);
1685
1686   // Delete the old constant!
1687   destroyConstant();
1688 }
1689
1690 void ConstantExpr::replaceUsesOfWithOnConstant(Value *From, Value *ToV,
1691                                                Use *U) {
1692   assert(isa<Constant>(ToV) && "Cannot make Constant refer to non-constant!");
1693   Constant *To = cast<Constant>(ToV);
1694
1695   Constant *Replacement = 0;
1696   if (getOpcode() == Instruction::GetElementPtr) {
1697     std::vector<Constant*> Indices;
1698     Constant *Pointer = getOperand(0);
1699     Indices.reserve(getNumOperands()-1);
1700     if (Pointer == From) Pointer = To;
1701
1702     for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
1703       Constant *Val = getOperand(i);
1704       if (Val == From) Val = To;
1705       Indices.push_back(Val);
1706     }
1707     Replacement = ConstantExpr::getGetElementPtr(Pointer, Indices);
1708   } else if (getOpcode() == Instruction::Cast) {
1709     assert(getOperand(0) == From && "Cast only has one use!");
1710     Replacement = ConstantExpr::getCast(To, getType());
1711   } else if (getOpcode() == Instruction::Select) {
1712     Constant *C1 = getOperand(0);
1713     Constant *C2 = getOperand(1);
1714     Constant *C3 = getOperand(2);
1715     if (C1 == From) C1 = To;
1716     if (C2 == From) C2 = To;
1717     if (C3 == From) C3 = To;
1718     Replacement = ConstantExpr::getSelect(C1, C2, C3);
1719   } else if (getOpcode() == Instruction::ExtractElement) {
1720     Constant *C1 = getOperand(0);
1721     Constant *C2 = getOperand(1);
1722     if (C1 == From) C1 = To;
1723     if (C2 == From) C2 = To;
1724     Replacement = ConstantExpr::getExtractElement(C1, C2);
1725   } else if (getOpcode() == Instruction::InsertElement) {
1726     Constant *C1 = getOperand(0);
1727     Constant *C2 = getOperand(1);
1728     Constant *C3 = getOperand(1);
1729     if (C1 == From) C1 = To;
1730     if (C2 == From) C2 = To;
1731     if (C3 == From) C3 = To;
1732     Replacement = ConstantExpr::getInsertElement(C1, C2, C3);
1733   } else if (getOpcode() == Instruction::ShuffleVector) {
1734     Constant *C1 = getOperand(0);
1735     Constant *C2 = getOperand(1);
1736     Constant *C3 = getOperand(2);
1737     if (C1 == From) C1 = To;
1738     if (C2 == From) C2 = To;
1739     if (C3 == From) C3 = To;
1740     Replacement = ConstantExpr::getShuffleVector(C1, C2, C3);
1741   } else if (getNumOperands() == 2) {
1742     Constant *C1 = getOperand(0);
1743     Constant *C2 = getOperand(1);
1744     if (C1 == From) C1 = To;
1745     if (C2 == From) C2 = To;
1746     Replacement = ConstantExpr::get(getOpcode(), C1, C2);
1747   } else {
1748     assert(0 && "Unknown ConstantExpr type!");
1749     return;
1750   }
1751
1752   assert(Replacement != this && "I didn't contain From!");
1753
1754   // Everyone using this now uses the replacement.
1755   uncheckedReplaceAllUsesWith(Replacement);
1756
1757   // Delete the old constant!
1758   destroyConstant();
1759 }
1760
1761
1762
1763 /// clearAllValueMaps - This method frees all internal memory used by the
1764 /// constant subsystem, which can be used in environments where this memory
1765 /// is otherwise reported as a leak.
1766 void Constant::clearAllValueMaps() {
1767   std::vector<Constant *> Constants;
1768
1769   DoubleConstants.clear(Constants);
1770   FloatConstants.clear(Constants);
1771   SIntConstants.clear(Constants);
1772   UIntConstants.clear(Constants);
1773   AggZeroConstants.clear(Constants);
1774   ArrayConstants.clear(Constants);
1775   StructConstants.clear(Constants);
1776   PackedConstants.clear(Constants);
1777   NullPtrConstants.clear(Constants);
1778   UndefValueConstants.clear(Constants);
1779   ExprConstants.clear(Constants);
1780
1781   for (std::vector<Constant *>::iterator I = Constants.begin(),
1782        E = Constants.end(); I != E; ++I)
1783     (*I)->dropAllReferences();
1784   for (std::vector<Constant *>::iterator I = Constants.begin(),
1785        E = Constants.end(); I != E; ++I)
1786     (*I)->destroyConstantImpl();
1787   Constants.clear();
1788 }
1789
1790 /// getStringValue - Turn an LLVM constant pointer that eventually points to a
1791 /// global into a string value.  Return an empty string if we can't do it.
1792 /// Parameter Chop determines if the result is chopped at the first null
1793 /// terminator.
1794 ///
1795 std::string Constant::getStringValue(bool Chop, unsigned Offset) {
1796   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(this)) {
1797     if (GV->hasInitializer() && isa<ConstantArray>(GV->getInitializer())) {
1798       ConstantArray *Init = cast<ConstantArray>(GV->getInitializer());
1799       if (Init->isString()) {
1800         std::string Result = Init->getAsString();
1801         if (Offset < Result.size()) {
1802           // If we are pointing INTO The string, erase the beginning...
1803           Result.erase(Result.begin(), Result.begin()+Offset);
1804
1805           // Take off the null terminator, and any string fragments after it.
1806           if (Chop) {
1807             std::string::size_type NullPos = Result.find_first_of((char)0);
1808             if (NullPos != std::string::npos)
1809               Result.erase(Result.begin()+NullPos, Result.end());
1810           }
1811           return Result;
1812         }
1813       }
1814     }
1815   } else if (Constant *C = dyn_cast<Constant>(this)) {
1816     if (GlobalValue *GV = dyn_cast<GlobalValue>(C))
1817       return GV->getStringValue(Chop, Offset);
1818     else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
1819       if (CE->getOpcode() == Instruction::GetElementPtr) {
1820         // Turn a gep into the specified offset.
1821         if (CE->getNumOperands() == 3 &&
1822             cast<Constant>(CE->getOperand(1))->isNullValue() &&
1823             isa<ConstantInt>(CE->getOperand(2))) {
1824           Offset += cast<ConstantInt>(CE->getOperand(2))->getRawValue();
1825           return CE->getOperand(0)->getStringValue(Chop, Offset);
1826         }
1827       }
1828     }
1829   }
1830   return "";
1831 }
1832