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