lib/VMCore/ConstantsContext.h

   1 //===---------------- ConstantsContext.h - Implementation ------*- C++ -*--===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This file defines various helper methods and classes used by
  11 // LLVMContextImpl for creating and managing constants.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_CONSTANTSCONTEXT_H
  16 #define LLVM_CONSTANTSCONTEXT_H
  17
  18 #include "llvm/Instructions.h"
  19 #include "llvm/Operator.h"
  20 #include "llvm/Support/Debug.h"
  21 #include "llvm/Support/ErrorHandling.h"
  22 #include "llvm/System/Mutex.h"
  23 #include "llvm/System/RWMutex.h"
  24 #include <map>
  25
  26 namespace llvm {
  27 template<class ValType>
  28 struct ConstantTraits;
  29
  30 /// UnaryConstantExpr - This class is private to Constants.cpp, and is used
  31 /// behind the scenes to implement unary constant exprs.
  32 class UnaryConstantExpr : public ConstantExpr {
  33   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
  34 public:
  35   // allocate space for exactly one operand
  36   void *operator new(size_t s) {
  37     return User::operator new(s, 1);
  38   }
  39   UnaryConstantExpr(unsigned Opcode, Constant *C, const Type *Ty)
  40     : ConstantExpr(Ty, Opcode, &Op<0>(), 1) {
  41     Op<0>() = C;
  42   }
  43   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
  44 };
  45
  46 /// BinaryConstantExpr - This class is private to Constants.cpp, and is used
  47 /// behind the scenes to implement binary constant exprs.
  48 class BinaryConstantExpr : public ConstantExpr {
  49   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
  50 public:
  51   // allocate space for exactly two operands
  52   void *operator new(size_t s) {
  53     return User::operator new(s, 2);
  54   }
  55   BinaryConstantExpr(unsigned Opcode, Constant *C1, Constant *C2)
  56     : ConstantExpr(C1->getType(), Opcode, &Op<0>(), 2) {
  57     Op<0>() = C1;
  58     Op<1>() = C2;
  59   }
  60   /// Transparently provide more efficient getOperand methods.
  61   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
  62 };
  63
  64 /// SelectConstantExpr - This class is private to Constants.cpp, and is used
  65 /// behind the scenes to implement select constant exprs.
  66 class SelectConstantExpr : public ConstantExpr {
  67   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
  68 public:
  69   // allocate space for exactly three operands
  70   void *operator new(size_t s) {
  71     return User::operator new(s, 3);
  72   }
  73   SelectConstantExpr(Constant *C1, Constant *C2, Constant *C3)
  74     : ConstantExpr(C2->getType(), Instruction::Select, &Op<0>(), 3) {
  75     Op<0>() = C1;
  76     Op<1>() = C2;
  77     Op<2>() = C3;
  78   }
  79   /// Transparently provide more efficient getOperand methods.
  80   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
  81 };
  82
  83 /// ExtractElementConstantExpr - This class is private to
  84 /// Constants.cpp, and is used behind the scenes to implement
  85 /// extractelement constant exprs.
  86 class ExtractElementConstantExpr : public ConstantExpr {
  87   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
  88 public:
  89   // allocate space for exactly two operands
  90   void *operator new(size_t s) {
  91     return User::operator new(s, 2);
  92   }
  93   ExtractElementConstantExpr(Constant *C1, Constant *C2)
  94     : ConstantExpr(cast<VectorType>(C1->getType())->getElementType(),
  95                    Instruction::ExtractElement, &Op<0>(), 2) {
  96     Op<0>() = C1;
  97     Op<1>() = C2;
  98   }
  99   /// Transparently provide more efficient getOperand methods.
 100   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 101 };
 102
 103 /// InsertElementConstantExpr - This class is private to
 104 /// Constants.cpp, and is used behind the scenes to implement
 105 /// insertelement constant exprs.
 106 class InsertElementConstantExpr : public ConstantExpr {
 107   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
 108 public:
 109   // allocate space for exactly three operands
 110   void *operator new(size_t s) {
 111     return User::operator new(s, 3);
 112   }
 113   InsertElementConstantExpr(Constant *C1, Constant *C2, Constant *C3)
 114     : ConstantExpr(C1->getType(), Instruction::InsertElement,
 115                    &Op<0>(), 3) {
 116     Op<0>() = C1;
 117     Op<1>() = C2;
 118     Op<2>() = C3;
 119   }
 120   /// Transparently provide more efficient getOperand methods.
 121   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 122 };
 123
 124 /// ShuffleVectorConstantExpr - This class is private to
 125 /// Constants.cpp, and is used behind the scenes to implement
 126 /// shufflevector constant exprs.
 127 class ShuffleVectorConstantExpr : public ConstantExpr {
 128   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
 129 public:
 130   // allocate space for exactly three operands
 131   void *operator new(size_t s) {
 132     return User::operator new(s, 3);
 133   }
 134   ShuffleVectorConstantExpr(Constant *C1, Constant *C2, Constant *C3)
 135   : ConstantExpr(VectorType::get(
 136                    cast<VectorType>(C1->getType())->getElementType(),
 137                    cast<VectorType>(C3->getType())->getNumElements()),
 138                  Instruction::ShuffleVector,
 139                  &Op<0>(), 3) {
 140     Op<0>() = C1;
 141     Op<1>() = C2;
 142     Op<2>() = C3;
 143   }
 144   /// Transparently provide more efficient getOperand methods.
 145   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 146 };
 147
 148 /// ExtractValueConstantExpr - This class is private to
 149 /// Constants.cpp, and is used behind the scenes to implement
 150 /// extractvalue constant exprs.
 151 class ExtractValueConstantExpr : public ConstantExpr {
 152   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
 153 public:
 154   // allocate space for exactly one operand
 155   void *operator new(size_t s) {
 156     return User::operator new(s, 1);
 157   }
 158   ExtractValueConstantExpr(Constant *Agg,
 159                            const SmallVector<unsigned, 4> &IdxList,
 160                            const Type *DestTy)
 161     : ConstantExpr(DestTy, Instruction::ExtractValue, &Op<0>(), 1),
 162       Indices(IdxList) {
 163     Op<0>() = Agg;
 164   }
 165
 166   /// Indices - These identify which value to extract.
 167   const SmallVector<unsigned, 4> Indices;
 168
 169   /// Transparently provide more efficient getOperand methods.
 170   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 171 };
 172
 173 /// InsertValueConstantExpr - This class is private to
 174 /// Constants.cpp, and is used behind the scenes to implement
 175 /// insertvalue constant exprs.
 176 class InsertValueConstantExpr : public ConstantExpr {
 177   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
 178 public:
 179   // allocate space for exactly one operand
 180   void *operator new(size_t s) {
 181     return User::operator new(s, 2);
 182   }
 183   InsertValueConstantExpr(Constant *Agg, Constant *Val,
 184                           const SmallVector<unsigned, 4> &IdxList,
 185                           const Type *DestTy)
 186     : ConstantExpr(DestTy, Instruction::InsertValue, &Op<0>(), 2),
 187       Indices(IdxList) {
 188     Op<0>() = Agg;
 189     Op<1>() = Val;
 190   }
 191
 192   /// Indices - These identify the position for the insertion.
 193   const SmallVector<unsigned, 4> Indices;
 194
 195   /// Transparently provide more efficient getOperand methods.
 196   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 197 };
 198
 199
 200 /// GetElementPtrConstantExpr - This class is private to Constants.cpp, and is
 201 /// used behind the scenes to implement getelementpr constant exprs.
 202 class GetElementPtrConstantExpr : public ConstantExpr {
 203   GetElementPtrConstantExpr(Constant *C, const std::vector<Constant*> &IdxList,
 204                             const Type *DestTy);
 205 public:
 206   static GetElementPtrConstantExpr *Create(Constant *C,
 207                                            const std::vector<Constant*>&IdxList,
 208                                            const Type *DestTy) {
 209     return
 210       new(IdxList.size() + 1) GetElementPtrConstantExpr(C, IdxList, DestTy);
 211   }
 212   /// Transparently provide more efficient getOperand methods.
 213   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 214 };
 215
 216 // CompareConstantExpr - This class is private to Constants.cpp, and is used
 217 // behind the scenes to implement ICmp and FCmp constant expressions. This is
 218 // needed in order to store the predicate value for these instructions.
 219 struct CompareConstantExpr : public ConstantExpr {
 220   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
 221   // allocate space for exactly two operands
 222   void *operator new(size_t s) {
 223     return User::operator new(s, 2);
 224   }
 225   unsigned short predicate;
 226   CompareConstantExpr(const Type *ty, Instruction::OtherOps opc,
 227                       unsigned short pred,  Constant* LHS, Constant* RHS)
 228     : ConstantExpr(ty, opc, &Op<0>(), 2), predicate(pred) {
 229     Op<0>() = LHS;
 230     Op<1>() = RHS;
 231   }
 232   /// Transparently provide more efficient getOperand methods.
 233   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 234 };
 235
 236 template <>
 237 struct OperandTraits<UnaryConstantExpr> : FixedNumOperandTraits<1> {
 238 };
 239 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(UnaryConstantExpr, Value)
 240
 241 template <>
 242 struct OperandTraits<BinaryConstantExpr> : FixedNumOperandTraits<2> {
 243 };
 244 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(BinaryConstantExpr, Value)
 245
 246 template <>
 247 struct OperandTraits<SelectConstantExpr> : FixedNumOperandTraits<3> {
 248 };
 249 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(SelectConstantExpr, Value)
 250
 251 template <>
 252 struct OperandTraits<ExtractElementConstantExpr> : FixedNumOperandTraits<2> {
 253 };
 254 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ExtractElementConstantExpr, Value)
 255
 256 template <>
 257 struct OperandTraits<InsertElementConstantExpr> : FixedNumOperandTraits<3> {
 258 };
 259 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(InsertElementConstantExpr, Value)
 260
 261 template <>
 262 struct OperandTraits<ShuffleVectorConstantExpr> : FixedNumOperandTraits<3> {
 263 };
 264 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ShuffleVectorConstantExpr, Value)
 265
 266 template <>
 267 struct OperandTraits<ExtractValueConstantExpr> : FixedNumOperandTraits<1> {
 268 };
 269 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ExtractValueConstantExpr, Value)
 270
 271 template <>
 272 struct OperandTraits<InsertValueConstantExpr> : FixedNumOperandTraits<2> {
 273 };
 274 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(InsertValueConstantExpr, Value)
 275
 276 template <>
 277 struct OperandTraits<GetElementPtrConstantExpr> : VariadicOperandTraits<1> {
 278 };
 279
 280 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(GetElementPtrConstantExpr, Value)
 281
 282
 283 template <>
 284 struct OperandTraits<CompareConstantExpr> : FixedNumOperandTraits<2> {
 285 };
 286 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(CompareConstantExpr, Value)
 287
 288 struct ExprMapKeyType {
 289   typedef SmallVector<unsigned, 4> IndexList;
 290
 291   ExprMapKeyType(unsigned opc,
 292       const std::vector<Constant*> &ops,
 293       unsigned short pred = 0,
 294       const IndexList &inds = IndexList())
 295         : opcode(opc), predicate(pred), operands(ops), indices(inds) {}
 296   uint16_t opcode;
 297   uint16_t predicate;
 298   std::vector<Constant*> operands;
 299   IndexList indices;
 300   bool operator==(const ExprMapKeyType& that) const {
 301     return this->opcode == that.opcode &&
 302            this->predicate == that.predicate &&
 303            this->operands == that.operands &&
 304            this->indices == that.indices;
 305   }
 306   bool operator<(const ExprMapKeyType & that) const {
 307     return this->opcode < that.opcode ||
 308       (this->opcode == that.opcode && this->predicate < that.predicate) ||
 309       (this->opcode == that.opcode && this->predicate == that.predicate &&
 310        this->operands < that.operands) ||
 311       (this->opcode == that.opcode && this->predicate == that.predicate &&
 312        this->operands == that.operands && this->indices < that.indices);
 313   }
 314
 315   bool operator!=(const ExprMapKeyType& that) const {
 316     return !(*this == that);
 317   }
 318 };
 319
 320 // The number of operands for each ConstantCreator::create method is
 321 // determined by the ConstantTraits template.
 322 // ConstantCreator - A class that is used to create constants by
 323 // ValueMap*.  This class should be partially specialized if there is
 324 // something strange that needs to be done to interface to the ctor for the
 325 // constant.
 326 //
 327 template<typename T, typename Alloc>
 328 struct ConstantTraits< std::vector<T, Alloc> > {
 329   static unsigned uses(const std::vector<T, Alloc>& v) {
 330     return v.size();
 331   }
 332 };
 333
 334 template<class ConstantClass, class TypeClass, class ValType>
 335 struct ConstantCreator {
 336   static ConstantClass *create(const TypeClass *Ty, const ValType &V) {
 337     return new(ConstantTraits<ValType>::uses(V)) ConstantClass(Ty, V);
 338   }
 339 };
 340
 341 template<class ConstantClass, class TypeClass>
 342 struct ConvertConstantType {
 343   static void convert(ConstantClass *OldC, const TypeClass *NewTy) {
 344     llvm_unreachable("This type cannot be converted!");
 345   }
 346 };
 347
 348 template<>
 349 struct ConstantCreator<ConstantExpr, Type, ExprMapKeyType> {
 350   static ConstantExpr *create(const Type *Ty, const ExprMapKeyType &V,
 351       unsigned short pred = 0) {
 352     if (Instruction::isCast(V.opcode))
 353       return new UnaryConstantExpr(V.opcode, V.operands[0], Ty);
 354     if ((V.opcode >= Instruction::BinaryOpsBegin &&
 355          V.opcode < Instruction::BinaryOpsEnd))
 356       return new BinaryConstantExpr(V.opcode, V.operands[0], V.operands[1]);
 357     if (V.opcode == Instruction::Select)
 358       return new SelectConstantExpr(V.operands[0], V.operands[1],
 359                                     V.operands[2]);
 360     if (V.opcode == Instruction::ExtractElement)
 361       return new ExtractElementConstantExpr(V.operands[0], V.operands[1]);
 362     if (V.opcode == Instruction::InsertElement)
 363       return new InsertElementConstantExpr(V.operands[0], V.operands[1],
 364                                            V.operands[2]);
 365     if (V.opcode == Instruction::ShuffleVector)
 366       return new ShuffleVectorConstantExpr(V.operands[0], V.operands[1],
 367                                            V.operands[2]);
 368     if (V.opcode == Instruction::InsertValue)
 369       return new InsertValueConstantExpr(V.operands[0], V.operands[1],
 370                                          V.indices, Ty);
 371     if (V.opcode == Instruction::ExtractValue)
 372       return new ExtractValueConstantExpr(V.operands[0], V.indices, Ty);
 373     if (V.opcode == Instruction::GetElementPtr) {
 374       std::vector<Constant*> IdxList(V.operands.begin()+1, V.operands.end());
 375       return GetElementPtrConstantExpr::Create(V.operands[0], IdxList, Ty);
 376     }
 377
 378     // The compare instructions are weird. We have to encode the predicate
 379     // value and it is combined with the instruction opcode by multiplying
 380     // the opcode by one hundred. We must decode this to get the predicate.
 381     if (V.opcode == Instruction::ICmp)
 382       return new CompareConstantExpr(Ty, Instruction::ICmp, V.predicate,
 383                                      V.operands[0], V.operands[1]);
 384     if (V.opcode == Instruction::FCmp)
 385       return new CompareConstantExpr(Ty, Instruction::FCmp, V.predicate,
 386                                      V.operands[0], V.operands[1]);
 387     llvm_unreachable("Invalid ConstantExpr!");
 388     return 0;
 389   }
 390 };
 391
 392 template<>
 393 struct ConvertConstantType<ConstantExpr, Type> {
 394   static void convert(ConstantExpr *OldC, const Type *NewTy) {
 395     Constant *New;
 396     switch (OldC->getOpcode()) {
 397     case Instruction::Trunc:
 398     case Instruction::ZExt:
 399     case Instruction::SExt:
 400     case Instruction::FPTrunc:
 401     case Instruction::FPExt:
 402     case Instruction::UIToFP:
 403     case Instruction::SIToFP:
 404     case Instruction::FPToUI:
 405     case Instruction::FPToSI:
 406     case Instruction::PtrToInt:
 407     case Instruction::IntToPtr:
 408     case Instruction::BitCast:
 409       New = ConstantExpr::getCast(OldC->getOpcode(), OldC->getOperand(0),
 410                                   NewTy);
 411       break;
 412     case Instruction::Select:
 413       New = ConstantExpr::getSelectTy(NewTy, OldC->getOperand(0),
 414                                       OldC->getOperand(1),
 415                                       OldC->getOperand(2));
 416       break;
 417     default:
 418       assert(OldC->getOpcode() >= Instruction::BinaryOpsBegin &&
 419              OldC->getOpcode() <  Instruction::BinaryOpsEnd);
 420       New = ConstantExpr::getTy(NewTy, OldC->getOpcode(), OldC->getOperand(0),
 421                                 OldC->getOperand(1));
 422       break;
 423     case Instruction::GetElementPtr:
 424       // Make everyone now use a constant of the new type...
 425       std::vector<Value*> Idx(OldC->op_begin()+1, OldC->op_end());
 426       New = ConstantExpr::getGetElementPtrTy(NewTy, OldC->getOperand(0),
 427                                              &Idx[0], Idx.size());
 428       break;
 429     }
 430
 431     assert(New != OldC && "Didn't replace constant??");
 432     OldC->uncheckedReplaceAllUsesWith(New);
 433     OldC->destroyConstant();    // This constant is now dead, destroy it.
 434   }
 435 };
 436
 437 // ConstantAggregateZero does not take extra "value" argument...
 438 template<class ValType>
 439 struct ConstantCreator<ConstantAggregateZero, Type, ValType> {
 440   static ConstantAggregateZero *create(const Type *Ty, const ValType &V){
 441     return new ConstantAggregateZero(Ty);
 442   }
 443 };
 444
 445 template<>
 446 struct ConvertConstantType<ConstantVector, VectorType> {
 447   static void convert(ConstantVector *OldC, const VectorType *NewTy) {
 448     // Make everyone now use a constant of the new type...
 449     std::vector<Constant*> C;
 450     for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i)
 451       C.push_back(cast<Constant>(OldC->getOperand(i)));
 452     Constant *New = ConstantVector::get(NewTy, C);
 453     assert(New != OldC && "Didn't replace constant??");
 454     OldC->uncheckedReplaceAllUsesWith(New);
 455     OldC->destroyConstant();    // This constant is now dead, destroy it.
 456   }
 457 };
 458
 459 template<>
 460 struct ConvertConstantType<ConstantAggregateZero, Type> {
 461   static void convert(ConstantAggregateZero *OldC, const Type *NewTy) {
 462     // Make everyone now use a constant of the new type...
 463     Constant *New = ConstantAggregateZero::get(NewTy);
 464     assert(New != OldC && "Didn't replace constant??");
 465     OldC->uncheckedReplaceAllUsesWith(New);
 466     OldC->destroyConstant();     // This constant is now dead, destroy it.
 467   }
 468 };
 469
 470 template<>
 471 struct ConvertConstantType<ConstantArray, ArrayType> {
 472   static void convert(ConstantArray *OldC, const ArrayType *NewTy) {
 473     // Make everyone now use a constant of the new type...
 474     std::vector<Constant*> C;
 475     for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i)
 476       C.push_back(cast<Constant>(OldC->getOperand(i)));
 477     Constant *New = ConstantArray::get(NewTy, C);
 478     assert(New != OldC && "Didn't replace constant??");
 479     OldC->uncheckedReplaceAllUsesWith(New);
 480     OldC->destroyConstant();    // This constant is now dead, destroy it.
 481   }
 482 };
 483
 484 template<>
 485 struct ConvertConstantType<ConstantStruct, StructType> {
 486   static void convert(ConstantStruct *OldC, const StructType *NewTy) {
 487     // Make everyone now use a constant of the new type...
 488     std::vector<Constant*> C;
 489     for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i)
 490       C.push_back(cast<Constant>(OldC->getOperand(i)));
 491     Constant *New = ConstantStruct::get(NewTy, C);
 492     assert(New != OldC && "Didn't replace constant??");
 493
 494     OldC->uncheckedReplaceAllUsesWith(New);
 495     OldC->destroyConstant();    // This constant is now dead, destroy it.
 496   }
 497 };
 498
 499 // ConstantPointerNull does not take extra "value" argument...
 500 template<class ValType>
 501 struct ConstantCreator<ConstantPointerNull, PointerType, ValType> {
 502   static ConstantPointerNull *create(const PointerType *Ty, const ValType &V){
 503     return new ConstantPointerNull(Ty);
 504   }
 505 };
 506
 507 template<>
 508 struct ConvertConstantType<ConstantPointerNull, PointerType> {
 509   static void convert(ConstantPointerNull *OldC, const PointerType *NewTy) {
 510     // Make everyone now use a constant of the new type...
 511     Constant *New = ConstantPointerNull::get(NewTy);
 512     assert(New != OldC && "Didn't replace constant??");
 513     OldC->uncheckedReplaceAllUsesWith(New);
 514     OldC->destroyConstant();     // This constant is now dead, destroy it.
 515   }
 516 };
 517
 518 // UndefValue does not take extra "value" argument...
 519 template<class ValType>
 520 struct ConstantCreator<UndefValue, Type, ValType> {
 521   static UndefValue *create(const Type *Ty, const ValType &V) {
 522     return new UndefValue(Ty);
 523   }
 524 };
 525
 526 template<>
 527 struct ConvertConstantType<UndefValue, Type> {
 528   static void convert(UndefValue *OldC, const Type *NewTy) {
 529     // Make everyone now use a constant of the new type.
 530     Constant *New = UndefValue::get(NewTy);
 531     assert(New != OldC && "Didn't replace constant??");
 532     OldC->uncheckedReplaceAllUsesWith(New);
 533     OldC->destroyConstant();     // This constant is now dead, destroy it.
 534   }
 535 };
 536
 537 template<class ValType, class TypeClass, class ConstantClass,
 538          bool HasLargeKey = false /*true for arrays and structs*/ >
 539 class ValueMap : public AbstractTypeUser {
 540 public:
 541   typedef std::pair<const Type*, ValType> MapKey;
 542   typedef std::map<MapKey, Constant *> MapTy;
 543   typedef std::map<Constant*, typename MapTy::iterator> InverseMapTy;
 544   typedef std::map<const Type*, typename MapTy::iterator> AbstractTypeMapTy;
 545 private:
 546   /// Map - This is the main map from the element descriptor to the Constants.
 547   /// This is the primary way we avoid creating two of the same shape
 548   /// constant.
 549   MapTy Map;
 550
 551   /// InverseMap - If "HasLargeKey" is true, this contains an inverse mapping
 552   /// from the constants to their element in Map.  This is important for
 553   /// removal of constants from the array, which would otherwise have to scan
 554   /// through the map with very large keys.
 555   InverseMapTy InverseMap;
 556
 557   /// AbstractTypeMap - Map for abstract type constants.
 558   ///
 559   AbstractTypeMapTy AbstractTypeMap;
 560
 561   /// ValueMapLock - Mutex for this map.
 562   sys::SmartMutex<true> ValueMapLock;
 563
 564 public:
 565   // NOTE: This function is not locked.  It is the caller's responsibility
 566   // to enforce proper synchronization.
 567   typename MapTy::iterator map_end() { return Map.end(); }
 568
 569   /// InsertOrGetItem - Return an iterator for the specified element.
 570   /// If the element exists in the map, the returned iterator points to the
 571   /// entry and Exists=true.  If not, the iterator points to the newly
 572   /// inserted entry and returns Exists=false.  Newly inserted entries have
 573   /// I->second == 0, and should be filled in.
 574   /// NOTE: This function is not locked.  It is the caller's responsibility
 575   // to enforce proper synchronization.
 576   typename MapTy::iterator InsertOrGetItem(std::pair<MapKey, Constant *>
 577                                  &InsertVal,
 578                                  bool &Exists) {
 579     std::pair<typename MapTy::iterator, bool> IP = Map.insert(InsertVal);
 580     Exists = !IP.second;
 581     return IP.first;
 582   }
 583
 584 private:
 585   typename MapTy::iterator FindExistingElement(ConstantClass *CP) {
 586     if (HasLargeKey) {
 587       typename InverseMapTy::iterator IMI = InverseMap.find(CP);
 588       assert(IMI != InverseMap.end() && IMI->second != Map.end() &&
 589              IMI->second->second == CP &&
 590              "InverseMap corrupt!");
 591       return IMI->second;
 592     }
 593
 594     typename MapTy::iterator I =
 595       Map.find(MapKey(static_cast<const TypeClass*>(CP->getRawType()),
 596                       getValType(CP)));
 597     if (I == Map.end() || I->second != CP) {
 598       // FIXME: This should not use a linear scan.  If this gets to be a
 599       // performance problem, someone should look at this.
 600       for (I = Map.begin(); I != Map.end() && I->second != CP; ++I)
 601         /* empty */;
 602     }
 603     return I;
 604   }
 605
 606   ConstantClass* Create(const TypeClass *Ty, const ValType &V,
 607                         typename MapTy::iterator I) {
 608     ConstantClass* Result =
 609       ConstantCreator<ConstantClass,TypeClass,ValType>::create(Ty, V);
 610
 611     assert(Result->getType() == Ty && "Type specified is not correct!");
 612     I = Map.insert(I, std::make_pair(MapKey(Ty, V), Result));
 613
 614     if (HasLargeKey)  // Remember the reverse mapping if needed.
 615       InverseMap.insert(std::make_pair(Result, I));
 616
 617     // If the type of the constant is abstract, make sure that an entry
 618     // exists for it in the AbstractTypeMap.
 619     if (Ty->isAbstract()) {
 620       typename AbstractTypeMapTy::iterator TI =
 621                                                AbstractTypeMap.find(Ty);
 622
 623       if (TI == AbstractTypeMap.end()) {
 624         // Add ourselves to the ATU list of the type.
 625         cast<DerivedType>(Ty)->addAbstractTypeUser(this);
 626
 627         AbstractTypeMap.insert(TI, std::make_pair(Ty, I));
 628       }
 629     }
 630
 631     return Result;
 632   }
 633 public:
 634
 635   /// getOrCreate - Return the specified constant from the map, creating it if
 636   /// necessary.
 637   ConstantClass *getOrCreate(const TypeClass *Ty, const ValType &V) {
 638     sys::SmartScopedLock<true> Lock(ValueMapLock);
 639     MapKey Lookup(Ty, V);
 640     ConstantClass* Result = 0;
 641
 642     typename MapTy::iterator I = Map.find(Lookup);
 643     // Is it in the map?
 644     if (I != Map.end())
 645       Result = static_cast<ConstantClass *>(I->second);
 646
 647     if (!Result) {
 648       // If no preexisting value, create one now...
 649       Result = Create(Ty, V, I);
 650     }
 651
 652     return Result;
 653   }
 654
 655   void remove(ConstantClass *CP) {
 656     sys::SmartScopedLock<true> Lock(ValueMapLock);
 657     typename MapTy::iterator I = FindExistingElement(CP);
 658     assert(I != Map.end() && "Constant not found in constant table!");
 659     assert(I->second == CP && "Didn't find correct element?");
 660
 661     if (HasLargeKey)  // Remember the reverse mapping if needed.
 662       InverseMap.erase(CP);
 663
 664     // Now that we found the entry, make sure this isn't the entry that
 665     // the AbstractTypeMap points to.
 666     const TypeClass *Ty = static_cast<const TypeClass *>(I->first.first);
 667     if (Ty->isAbstract()) {
 668       assert(AbstractTypeMap.count(Ty) &&
 669              "Abstract type not in AbstractTypeMap?");
 670       typename MapTy::iterator &ATMEntryIt = AbstractTypeMap[Ty];
 671       if (ATMEntryIt == I) {
 672         // Yes, we are removing the representative entry for this type.
 673         // See if there are any other entries of the same type.
 674         typename MapTy::iterator TmpIt = ATMEntryIt;
 675
 676         // First check the entry before this one...
 677         if (TmpIt != Map.begin()) {
 678           --TmpIt;
 679           if (TmpIt->first.first != Ty) // Not the same type, move back...
 680             ++TmpIt;
 681         }
 682
 683         // If we didn't find the same type, try to move forward...
 684         if (TmpIt == ATMEntryIt) {
 685           ++TmpIt;
 686           if (TmpIt == Map.end() || TmpIt->first.first != Ty)
 687             --TmpIt;   // No entry afterwards with the same type
 688         }
 689
 690         // If there is another entry in the map of the same abstract type,
 691         // update the AbstractTypeMap entry now.
 692         if (TmpIt != ATMEntryIt) {
 693           ATMEntryIt = TmpIt;
 694         } else {
 695           // Otherwise, we are removing the last instance of this type
 696           // from the table.  Remove from the ATM, and from user list.
 697           cast<DerivedType>(Ty)->removeAbstractTypeUser(this);
 698           AbstractTypeMap.erase(Ty);
 699         }
 700       }
 701     }
 702
 703     Map.erase(I);
 704   }
 705
 706
 707   /// MoveConstantToNewSlot - If we are about to change C to be the element
 708   /// specified by I, update our internal data structures to reflect this
 709   /// fact.
 710   /// NOTE: This function is not locked. It is the responsibility of the
 711   /// caller to enforce proper synchronization if using this method.
 712   void MoveConstantToNewSlot(ConstantClass *C, typename MapTy::iterator I) {
 713     // First, remove the old location of the specified constant in the map.
 714     typename MapTy::iterator OldI = FindExistingElement(C);
 715     assert(OldI != Map.end() && "Constant not found in constant table!");
 716     assert(OldI->second == C && "Didn't find correct element?");
 717
 718     // If this constant is the representative element for its abstract type,
 719     // update the AbstractTypeMap so that the representative element is I.
 720     if (C->getType()->isAbstract()) {
 721       typename AbstractTypeMapTy::iterator ATI =
 722           AbstractTypeMap.find(C->getType());
 723       assert(ATI != AbstractTypeMap.end() &&
 724              "Abstract type not in AbstractTypeMap?");
 725       if (ATI->second == OldI)
 726         ATI->second = I;
 727     }
 728
 729     // Remove the old entry from the map.
 730     Map.erase(OldI);
 731
 732     // Update the inverse map so that we know that this constant is now
 733     // located at descriptor I.
 734     if (HasLargeKey) {
 735       assert(I->second == C && "Bad inversemap entry!");
 736       InverseMap[C] = I;
 737     }
 738   }
 739
 740   void refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
 741     sys::SmartScopedLock<true> Lock(ValueMapLock);
 742     typename AbstractTypeMapTy::iterator I =
 743       AbstractTypeMap.find(cast<Type>(OldTy));
 744
 745     assert(I != AbstractTypeMap.end() &&
 746            "Abstract type not in AbstractTypeMap?");
 747
 748     // Convert a constant at a time until the last one is gone.  The last one
 749     // leaving will remove() itself, causing the AbstractTypeMapEntry to be
 750     // eliminated eventually.
 751     do {
 752       ConvertConstantType<ConstantClass,
 753                           TypeClass>::convert(
 754                               static_cast<ConstantClass *>(I->second->second),
 755                                               cast<TypeClass>(NewTy));
 756
 757       I = AbstractTypeMap.find(cast<Type>(OldTy));
 758     } while (I != AbstractTypeMap.end());
 759   }
 760
 761   // If the type became concrete without being refined to any other existing
 762   // type, we just remove ourselves from the ATU list.
 763   void typeBecameConcrete(const DerivedType *AbsTy) {
 764     AbsTy->removeAbstractTypeUser(this);
 765   }
 766
 767   void dump() const {
 768     DOUT << "Constant.cpp: ValueMap\n";
 769   }
 770 };
 771
 772 }
 773
 774 #endif