lib/VMCore/ConstantsContext.h

   1 //===-- ConstantsContext.h - Constants-related Context Interals -----------===//
   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/ADT/DenseMap.h"
  19 #include "llvm/InlineAsm.h"
  20 #include "llvm/Instructions.h"
  21 #include "llvm/Operator.h"
  22 #include "llvm/Support/Debug.h"
  23 #include "llvm/Support/ErrorHandling.h"
  24 #include "llvm/Support/raw_ostream.h"
  25 #include <map>
  26
  27 namespace llvm {
  28 template<class ValType>
  29 struct ConstantTraits;
  30
  31 /// UnaryConstantExpr - This class is private to Constants.cpp, and is used
  32 /// behind the scenes to implement unary constant exprs.
  33 class UnaryConstantExpr : public ConstantExpr {
  34   virtual void anchor();
  35   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
  36 public:
  37   // allocate space for exactly one operand
  38   void *operator new(size_t s) {
  39     return User::operator new(s, 1);
  40   }
  41   UnaryConstantExpr(unsigned Opcode, Constant *C, Type *Ty)
  42     : ConstantExpr(Ty, Opcode, &Op<0>(), 1) {
  43     Op<0>() = C;
  44   }
  45   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
  46 };
  47
  48 /// BinaryConstantExpr - This class is private to Constants.cpp, and is used
  49 /// behind the scenes to implement binary constant exprs.
  50 class BinaryConstantExpr : public ConstantExpr {
  51   virtual void anchor();
  52   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
  53 public:
  54   // allocate space for exactly two operands
  55   void *operator new(size_t s) {
  56     return User::operator new(s, 2);
  57   }
  58   BinaryConstantExpr(unsigned Opcode, Constant *C1, Constant *C2,
  59                      unsigned Flags)
  60     : ConstantExpr(C1->getType(), Opcode, &Op<0>(), 2) {
  61     Op<0>() = C1;
  62     Op<1>() = C2;
  63     SubclassOptionalData = Flags;
  64   }
  65   /// Transparently provide more efficient getOperand methods.
  66   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
  67 };
  68
  69 /// SelectConstantExpr - This class is private to Constants.cpp, and is used
  70 /// behind the scenes to implement select constant exprs.
  71 class SelectConstantExpr : public ConstantExpr {
  72   virtual void anchor();
  73   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
  74 public:
  75   // allocate space for exactly three operands
  76   void *operator new(size_t s) {
  77     return User::operator new(s, 3);
  78   }
  79   SelectConstantExpr(Constant *C1, Constant *C2, Constant *C3)
  80     : ConstantExpr(C2->getType(), Instruction::Select, &Op<0>(), 3) {
  81     Op<0>() = C1;
  82     Op<1>() = C2;
  83     Op<2>() = C3;
  84   }
  85   /// Transparently provide more efficient getOperand methods.
  86   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
  87 };
  88
  89 /// ExtractElementConstantExpr - This class is private to
  90 /// Constants.cpp, and is used behind the scenes to implement
  91 /// extractelement constant exprs.
  92 class ExtractElementConstantExpr : public ConstantExpr {
  93   virtual void anchor();
  94   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
  95 public:
  96   // allocate space for exactly two operands
  97   void *operator new(size_t s) {
  98     return User::operator new(s, 2);
  99   }
 100   ExtractElementConstantExpr(Constant *C1, Constant *C2)
 101     : ConstantExpr(cast<VectorType>(C1->getType())->getElementType(),
 102                    Instruction::ExtractElement, &Op<0>(), 2) {
 103     Op<0>() = C1;
 104     Op<1>() = C2;
 105   }
 106   /// Transparently provide more efficient getOperand methods.
 107   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 108 };
 109
 110 /// InsertElementConstantExpr - This class is private to
 111 /// Constants.cpp, and is used behind the scenes to implement
 112 /// insertelement constant exprs.
 113 class InsertElementConstantExpr : public ConstantExpr {
 114   virtual void anchor();
 115   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
 116 public:
 117   // allocate space for exactly three operands
 118   void *operator new(size_t s) {
 119     return User::operator new(s, 3);
 120   }
 121   InsertElementConstantExpr(Constant *C1, Constant *C2, Constant *C3)
 122     : ConstantExpr(C1->getType(), Instruction::InsertElement,
 123                    &Op<0>(), 3) {
 124     Op<0>() = C1;
 125     Op<1>() = C2;
 126     Op<2>() = C3;
 127   }
 128   /// Transparently provide more efficient getOperand methods.
 129   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 130 };
 131
 132 /// ShuffleVectorConstantExpr - This class is private to
 133 /// Constants.cpp, and is used behind the scenes to implement
 134 /// shufflevector constant exprs.
 135 class ShuffleVectorConstantExpr : public ConstantExpr {
 136   virtual void anchor();
 137   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
 138 public:
 139   // allocate space for exactly three operands
 140   void *operator new(size_t s) {
 141     return User::operator new(s, 3);
 142   }
 143   ShuffleVectorConstantExpr(Constant *C1, Constant *C2, Constant *C3)
 144   : ConstantExpr(VectorType::get(
 145                    cast<VectorType>(C1->getType())->getElementType(),
 146                    cast<VectorType>(C3->getType())->getNumElements()),
 147                  Instruction::ShuffleVector,
 148                  &Op<0>(), 3) {
 149     Op<0>() = C1;
 150     Op<1>() = C2;
 151     Op<2>() = C3;
 152   }
 153   /// Transparently provide more efficient getOperand methods.
 154   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 155 };
 156
 157 /// ExtractValueConstantExpr - This class is private to
 158 /// Constants.cpp, and is used behind the scenes to implement
 159 /// extractvalue constant exprs.
 160 class ExtractValueConstantExpr : public ConstantExpr {
 161   virtual void anchor();
 162   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
 163 public:
 164   // allocate space for exactly one operand
 165   void *operator new(size_t s) {
 166     return User::operator new(s, 1);
 167   }
 168   ExtractValueConstantExpr(Constant *Agg,
 169                            const SmallVector<unsigned, 4> &IdxList,
 170                            Type *DestTy)
 171     : ConstantExpr(DestTy, Instruction::ExtractValue, &Op<0>(), 1),
 172       Indices(IdxList) {
 173     Op<0>() = Agg;
 174   }
 175
 176   /// Indices - These identify which value to extract.
 177   const SmallVector<unsigned, 4> Indices;
 178
 179   /// Transparently provide more efficient getOperand methods.
 180   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 181 };
 182
 183 /// InsertValueConstantExpr - This class is private to
 184 /// Constants.cpp, and is used behind the scenes to implement
 185 /// insertvalue constant exprs.
 186 class InsertValueConstantExpr : public ConstantExpr {
 187   virtual void anchor();
 188   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
 189 public:
 190   // allocate space for exactly one operand
 191   void *operator new(size_t s) {
 192     return User::operator new(s, 2);
 193   }
 194   InsertValueConstantExpr(Constant *Agg, Constant *Val,
 195                           const SmallVector<unsigned, 4> &IdxList,
 196                           Type *DestTy)
 197     : ConstantExpr(DestTy, Instruction::InsertValue, &Op<0>(), 2),
 198       Indices(IdxList) {
 199     Op<0>() = Agg;
 200     Op<1>() = Val;
 201   }
 202
 203   /// Indices - These identify the position for the insertion.
 204   const SmallVector<unsigned, 4> Indices;
 205
 206   /// Transparently provide more efficient getOperand methods.
 207   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 208 };
 209
 210
 211 /// GetElementPtrConstantExpr - This class is private to Constants.cpp, and is
 212 /// used behind the scenes to implement getelementpr constant exprs.
 213 class GetElementPtrConstantExpr : public ConstantExpr {
 214   virtual void anchor();
 215   GetElementPtrConstantExpr(Constant *C, ArrayRef<Constant*> IdxList,
 216                             Type *DestTy);
 217 public:
 218   static GetElementPtrConstantExpr *Create(Constant *C,
 219                                            ArrayRef<Constant*> IdxList,
 220                                            Type *DestTy,
 221                                            unsigned Flags) {
 222     GetElementPtrConstantExpr *Result =
 223       new(IdxList.size() + 1) GetElementPtrConstantExpr(C, IdxList, DestTy);
 224     Result->SubclassOptionalData = Flags;
 225     return Result;
 226   }
 227   /// Transparently provide more efficient getOperand methods.
 228   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 229 };
 230
 231 // CompareConstantExpr - This class is private to Constants.cpp, and is used
 232 // behind the scenes to implement ICmp and FCmp constant expressions. This is
 233 // needed in order to store the predicate value for these instructions.
 234 class CompareConstantExpr : public ConstantExpr {
 235   virtual void anchor();
 236   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
 237 public:
 238   // allocate space for exactly two operands
 239   void *operator new(size_t s) {
 240     return User::operator new(s, 2);
 241   }
 242   unsigned short predicate;
 243   CompareConstantExpr(Type *ty, Instruction::OtherOps opc,
 244                       unsigned short pred,  Constant* LHS, Constant* RHS)
 245     : ConstantExpr(ty, opc, &Op<0>(), 2), predicate(pred) {
 246     Op<0>() = LHS;
 247     Op<1>() = RHS;
 248   }
 249   /// Transparently provide more efficient getOperand methods.
 250   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 251 };
 252
 253 template <>
 254 struct OperandTraits<UnaryConstantExpr> :
 255   public FixedNumOperandTraits<UnaryConstantExpr, 1> {
 256 };
 257 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(UnaryConstantExpr, Value)
 258
 259 template <>
 260 struct OperandTraits<BinaryConstantExpr> :
 261   public FixedNumOperandTraits<BinaryConstantExpr, 2> {
 262 };
 263 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(BinaryConstantExpr, Value)
 264
 265 template <>
 266 struct OperandTraits<SelectConstantExpr> :
 267   public FixedNumOperandTraits<SelectConstantExpr, 3> {
 268 };
 269 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(SelectConstantExpr, Value)
 270
 271 template <>
 272 struct OperandTraits<ExtractElementConstantExpr> :
 273   public FixedNumOperandTraits<ExtractElementConstantExpr, 2> {
 274 };
 275 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ExtractElementConstantExpr, Value)
 276
 277 template <>
 278 struct OperandTraits<InsertElementConstantExpr> :
 279   public FixedNumOperandTraits<InsertElementConstantExpr, 3> {
 280 };
 281 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(InsertElementConstantExpr, Value)
 282
 283 template <>
 284 struct OperandTraits<ShuffleVectorConstantExpr> :
 285     public FixedNumOperandTraits<ShuffleVectorConstantExpr, 3> {
 286 };
 287 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ShuffleVectorConstantExpr, Value)
 288
 289 template <>
 290 struct OperandTraits<ExtractValueConstantExpr> :
 291   public FixedNumOperandTraits<ExtractValueConstantExpr, 1> {
 292 };
 293 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ExtractValueConstantExpr, Value)
 294
 295 template <>
 296 struct OperandTraits<InsertValueConstantExpr> :
 297   public FixedNumOperandTraits<InsertValueConstantExpr, 2> {
 298 };
 299 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(InsertValueConstantExpr, Value)
 300
 301 template <>
 302 struct OperandTraits<GetElementPtrConstantExpr> :
 303   public VariadicOperandTraits<GetElementPtrConstantExpr, 1> {
 304 };
 305
 306 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(GetElementPtrConstantExpr, Value)
 307
 308
 309 template <>
 310 struct OperandTraits<CompareConstantExpr> :
 311   public FixedNumOperandTraits<CompareConstantExpr, 2> {
 312 };
 313 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(CompareConstantExpr, Value)
 314
 315 struct ExprMapKeyType {
 316   ExprMapKeyType(unsigned opc,
 317       ArrayRef<Constant*> ops,
 318       unsigned short flags = 0,
 319       unsigned short optionalflags = 0,
 320       ArrayRef<unsigned> inds = ArrayRef<unsigned>())
 321         : opcode(opc), subclassoptionaldata(optionalflags), subclassdata(flags),
 322         operands(ops.begin(), ops.end()), indices(inds.begin(), inds.end()) {}
 323   uint8_t opcode;
 324   uint8_t subclassoptionaldata;
 325   uint16_t subclassdata;
 326   std::vector<Constant*> operands;
 327   SmallVector<unsigned, 4> indices;
 328   bool operator==(const ExprMapKeyType& that) const {
 329     return this->opcode == that.opcode &&
 330            this->subclassdata == that.subclassdata &&
 331            this->subclassoptionaldata == that.subclassoptionaldata &&
 332            this->operands == that.operands &&
 333            this->indices == that.indices;
 334   }
 335   bool operator<(const ExprMapKeyType & that) const {
 336     if (this->opcode != that.opcode) return this->opcode < that.opcode;
 337     if (this->operands != that.operands) return this->operands < that.operands;
 338     if (this->subclassdata != that.subclassdata)
 339       return this->subclassdata < that.subclassdata;
 340     if (this->subclassoptionaldata != that.subclassoptionaldata)
 341       return this->subclassoptionaldata < that.subclassoptionaldata;
 342     if (this->indices != that.indices) return this->indices < that.indices;
 343     return false;
 344   }
 345
 346   bool operator!=(const ExprMapKeyType& that) const {
 347     return !(*this == that);
 348   }
 349 };
 350
 351 struct InlineAsmKeyType {
 352   InlineAsmKeyType(StringRef AsmString,
 353                    StringRef Constraints, bool hasSideEffects,
 354                    bool isAlignStack)
 355     : asm_string(AsmString), constraints(Constraints),
 356       has_side_effects(hasSideEffects), is_align_stack(isAlignStack) {}
 357   std::string asm_string;
 358   std::string constraints;
 359   bool has_side_effects;
 360   bool is_align_stack;
 361   bool operator==(const InlineAsmKeyType& that) const {
 362     return this->asm_string == that.asm_string &&
 363            this->constraints == that.constraints &&
 364            this->has_side_effects == that.has_side_effects &&
 365            this->is_align_stack == that.is_align_stack;
 366   }
 367   bool operator<(const InlineAsmKeyType& that) const {
 368     if (this->asm_string != that.asm_string)
 369       return this->asm_string < that.asm_string;
 370     if (this->constraints != that.constraints)
 371       return this->constraints < that.constraints;
 372     if (this->has_side_effects != that.has_side_effects)
 373       return this->has_side_effects < that.has_side_effects;
 374     if (this->is_align_stack != that.is_align_stack)
 375       return this->is_align_stack < that.is_align_stack;
 376     return false;
 377   }
 378
 379   bool operator!=(const InlineAsmKeyType& that) const {
 380     return !(*this == that);
 381   }
 382 };
 383
 384 // The number of operands for each ConstantCreator::create method is
 385 // determined by the ConstantTraits template.
 386 // ConstantCreator - A class that is used to create constants by
 387 // ConstantUniqueMap*.  This class should be partially specialized if there is
 388 // something strange that needs to be done to interface to the ctor for the
 389 // constant.
 390 //
 391 template<typename T, typename Alloc>
 392 struct ConstantTraits< std::vector<T, Alloc> > {
 393   static unsigned uses(const std::vector<T, Alloc>& v) {
 394     return v.size();
 395   }
 396 };
 397
 398 template<>
 399 struct ConstantTraits<Constant *> {
 400   static unsigned uses(Constant * const & v) {
 401     return 1;
 402   }
 403 };
 404
 405 template<class ConstantClass, class TypeClass, class ValType>
 406 struct ConstantCreator {
 407   static ConstantClass *create(TypeClass *Ty, const ValType &V) {
 408     return new(ConstantTraits<ValType>::uses(V)) ConstantClass(Ty, V);
 409   }
 410 };
 411
 412 template<class ConstantClass, class TypeClass>
 413 struct ConstantArrayCreator {
 414   static ConstantClass *create(TypeClass *Ty, ArrayRef<Constant*> V) {
 415     return new(V.size()) ConstantClass(Ty, V);
 416   }
 417 };
 418
 419 template<class ConstantClass>
 420 struct ConstantKeyData {
 421   typedef void ValType;
 422   static ValType getValType(ConstantClass *C) {
 423     llvm_unreachable("Unknown Constant type!");
 424   }
 425 };
 426
 427 template<>
 428 struct ConstantCreator<ConstantExpr, Type, ExprMapKeyType> {
 429   static ConstantExpr *create(Type *Ty, const ExprMapKeyType &V,
 430       unsigned short pred = 0) {
 431     if (Instruction::isCast(V.opcode))
 432       return new UnaryConstantExpr(V.opcode, V.operands[0], Ty);
 433     if ((V.opcode >= Instruction::BinaryOpsBegin &&
 434          V.opcode < Instruction::BinaryOpsEnd))
 435       return new BinaryConstantExpr(V.opcode, V.operands[0], V.operands[1],
 436                                     V.subclassoptionaldata);
 437     if (V.opcode == Instruction::Select)
 438       return new SelectConstantExpr(V.operands[0], V.operands[1],
 439                                     V.operands[2]);
 440     if (V.opcode == Instruction::ExtractElement)
 441       return new ExtractElementConstantExpr(V.operands[0], V.operands[1]);
 442     if (V.opcode == Instruction::InsertElement)
 443       return new InsertElementConstantExpr(V.operands[0], V.operands[1],
 444                                            V.operands[2]);
 445     if (V.opcode == Instruction::ShuffleVector)
 446       return new ShuffleVectorConstantExpr(V.operands[0], V.operands[1],
 447                                            V.operands[2]);
 448     if (V.opcode == Instruction::InsertValue)
 449       return new InsertValueConstantExpr(V.operands[0], V.operands[1],
 450                                          V.indices, Ty);
 451     if (V.opcode == Instruction::ExtractValue)
 452       return new ExtractValueConstantExpr(V.operands[0], V.indices, Ty);
 453     if (V.opcode == Instruction::GetElementPtr) {
 454       std::vector<Constant*> IdxList(V.operands.begin()+1, V.operands.end());
 455       return GetElementPtrConstantExpr::Create(V.operands[0], IdxList, Ty,
 456                                                V.subclassoptionaldata);
 457     }
 458
 459     // The compare instructions are weird. We have to encode the predicate
 460     // value and it is combined with the instruction opcode by multiplying
 461     // the opcode by one hundred. We must decode this to get the predicate.
 462     if (V.opcode == Instruction::ICmp)
 463       return new CompareConstantExpr(Ty, Instruction::ICmp, V.subclassdata,
 464                                      V.operands[0], V.operands[1]);
 465     if (V.opcode == Instruction::FCmp)
 466       return new CompareConstantExpr(Ty, Instruction::FCmp, V.subclassdata,
 467                                      V.operands[0], V.operands[1]);
 468     llvm_unreachable("Invalid ConstantExpr!");
 469   }
 470 };
 471
 472 template<>
 473 struct ConstantKeyData<ConstantExpr> {
 474   typedef ExprMapKeyType ValType;
 475   static ValType getValType(ConstantExpr *CE) {
 476     std::vector<Constant*> Operands;
 477     Operands.reserve(CE->getNumOperands());
 478     for (unsigned i = 0, e = CE->getNumOperands(); i != e; ++i)
 479       Operands.push_back(cast<Constant>(CE->getOperand(i)));
 480     return ExprMapKeyType(CE->getOpcode(), Operands,
 481         CE->isCompare() ? CE->getPredicate() : 0,
 482         CE->getRawSubclassOptionalData(),
 483         CE->hasIndices() ?
 484           CE->getIndices() : ArrayRef<unsigned>());
 485   }
 486 };
 487
 488 template<>
 489 struct ConstantCreator<InlineAsm, PointerType, InlineAsmKeyType> {
 490   static InlineAsm *create(PointerType *Ty, const InlineAsmKeyType &Key) {
 491     return new InlineAsm(Ty, Key.asm_string, Key.constraints,
 492                          Key.has_side_effects, Key.is_align_stack);
 493   }
 494 };
 495
 496 template<>
 497 struct ConstantKeyData<InlineAsm> {
 498   typedef InlineAsmKeyType ValType;
 499   static ValType getValType(InlineAsm *Asm) {
 500     return InlineAsmKeyType(Asm->getAsmString(), Asm->getConstraintString(),
 501                             Asm->hasSideEffects(), Asm->isAlignStack());
 502   }
 503 };
 504
 505 template<class ValType, class ValRefType, class TypeClass, class ConstantClass,
 506          bool HasLargeKey = false /*true for arrays and structs*/ >
 507 class ConstantUniqueMap {
 508 public:
 509   typedef std::pair<TypeClass*, ValType> MapKey;
 510   typedef std::map<MapKey, ConstantClass *> MapTy;
 511   typedef std::map<ConstantClass *, typename MapTy::iterator> InverseMapTy;
 512 private:
 513   /// Map - This is the main map from the element descriptor to the Constants.
 514   /// This is the primary way we avoid creating two of the same shape
 515   /// constant.
 516   MapTy Map;
 517
 518   /// InverseMap - If "HasLargeKey" is true, this contains an inverse mapping
 519   /// from the constants to their element in Map.  This is important for
 520   /// removal of constants from the array, which would otherwise have to scan
 521   /// through the map with very large keys.
 522   InverseMapTy InverseMap;
 523
 524 public:
 525   typename MapTy::iterator map_begin() { return Map.begin(); }
 526   typename MapTy::iterator map_end() { return Map.end(); }
 527
 528   void freeConstants() {
 529     for (typename MapTy::iterator I=Map.begin(), E=Map.end();
 530          I != E; ++I) {
 531       // Asserts that use_empty().
 532       delete I->second;
 533     }
 534   }
 535
 536   /// InsertOrGetItem - Return an iterator for the specified element.
 537   /// If the element exists in the map, the returned iterator points to the
 538   /// entry and Exists=true.  If not, the iterator points to the newly
 539   /// inserted entry and returns Exists=false.  Newly inserted entries have
 540   /// I->second == 0, and should be filled in.
 541   typename MapTy::iterator InsertOrGetItem(std::pair<MapKey, ConstantClass *>
 542                                  &InsertVal,
 543                                  bool &Exists) {
 544     std::pair<typename MapTy::iterator, bool> IP = Map.insert(InsertVal);
 545     Exists = !IP.second;
 546     return IP.first;
 547   }
 548
 549 private:
 550   typename MapTy::iterator FindExistingElement(ConstantClass *CP) {
 551     if (HasLargeKey) {
 552       typename InverseMapTy::iterator IMI = InverseMap.find(CP);
 553       assert(IMI != InverseMap.end() && IMI->second != Map.end() &&
 554              IMI->second->second == CP &&
 555              "InverseMap corrupt!");
 556       return IMI->second;
 557     }
 558
 559     typename MapTy::iterator I =
 560       Map.find(MapKey(static_cast<TypeClass*>(CP->getType()),
 561                       ConstantKeyData<ConstantClass>::getValType(CP)));
 562     if (I == Map.end() || I->second != CP) {
 563       // FIXME: This should not use a linear scan.  If this gets to be a
 564       // performance problem, someone should look at this.
 565       for (I = Map.begin(); I != Map.end() && I->second != CP; ++I)
 566         /* empty */;
 567     }
 568     return I;
 569   }
 570
 571   ConstantClass *Create(TypeClass *Ty, ValRefType V,
 572                         typename MapTy::iterator I) {
 573     ConstantClass* Result =
 574       ConstantCreator<ConstantClass,TypeClass,ValType>::create(Ty, V);
 575
 576     assert(Result->getType() == Ty && "Type specified is not correct!");
 577     I = Map.insert(I, std::make_pair(MapKey(Ty, V), Result));
 578
 579     if (HasLargeKey)  // Remember the reverse mapping if needed.
 580       InverseMap.insert(std::make_pair(Result, I));
 581
 582     return Result;
 583   }
 584 public:
 585
 586   /// getOrCreate - Return the specified constant from the map, creating it if
 587   /// necessary.
 588   ConstantClass *getOrCreate(TypeClass *Ty, ValRefType V) {
 589     MapKey Lookup(Ty, V);
 590     ConstantClass* Result = 0;
 591
 592     typename MapTy::iterator I = Map.find(Lookup);
 593     // Is it in the map?
 594     if (I != Map.end())
 595       Result = I->second;
 596
 597     if (!Result) {
 598       // If no preexisting value, create one now...
 599       Result = Create(Ty, V, I);
 600     }
 601
 602     return Result;
 603   }
 604
 605   void remove(ConstantClass *CP) {
 606     typename MapTy::iterator I = FindExistingElement(CP);
 607     assert(I != Map.end() && "Constant not found in constant table!");
 608     assert(I->second == CP && "Didn't find correct element?");
 609
 610     if (HasLargeKey)  // Remember the reverse mapping if needed.
 611       InverseMap.erase(CP);
 612
 613     Map.erase(I);
 614   }
 615
 616   /// MoveConstantToNewSlot - If we are about to change C to be the element
 617   /// specified by I, update our internal data structures to reflect this
 618   /// fact.
 619   void MoveConstantToNewSlot(ConstantClass *C, typename MapTy::iterator I) {
 620     // First, remove the old location of the specified constant in the map.
 621     typename MapTy::iterator OldI = FindExistingElement(C);
 622     assert(OldI != Map.end() && "Constant not found in constant table!");
 623     assert(OldI->second == C && "Didn't find correct element?");
 624
 625      // Remove the old entry from the map.
 626     Map.erase(OldI);
 627
 628     // Update the inverse map so that we know that this constant is now
 629     // located at descriptor I.
 630     if (HasLargeKey) {
 631       assert(I->second == C && "Bad inversemap entry!");
 632       InverseMap[C] = I;
 633     }
 634   }
 635
 636   void dump() const {
 637     DEBUG(dbgs() << "Constant.cpp: ConstantUniqueMap\n");
 638   }
 639 };
 640
 641 // Unique map for aggregate constants
 642 template<class TypeClass, class ConstantClass>
 643 class ConstantAggrUniqueMap {
 644 public:
 645   typedef ArrayRef<Constant*> Operands;
 646   typedef std::pair<TypeClass*, Operands> LookupKey;
 647 private:
 648   struct MapInfo {
 649     typedef DenseMapInfo<ConstantClass*> ConstantClassInfo;
 650     typedef DenseMapInfo<Constant*> ConstantInfo;
 651     typedef DenseMapInfo<TypeClass*> TypeClassInfo;
 652     static inline ConstantClass* getEmptyKey() {
 653       return ConstantClassInfo::getEmptyKey();
 654     }
 655     static inline ConstantClass* getTombstoneKey() {
 656       return ConstantClassInfo::getTombstoneKey();
 657     }
 658     static unsigned getHashValue(const ConstantClass *CP) {
 659       // This is adapted from SuperFastHash by Paul Hsieh.
 660       unsigned Hash = TypeClassInfo::getHashValue(CP->getType());
 661       for (unsigned I = 0, E = CP->getNumOperands(); I < E; ++I) {
 662         unsigned Data = ConstantInfo::getHashValue(CP->getOperand(I));
 663         Hash         += Data & 0xFFFF;
 664         unsigned Tmp  = ((Data >> 16) << 11) ^ Hash;
 665         Hash          = (Hash << 16) ^ Tmp;
 666         Hash         += Hash >> 11;
 667       }
 668
 669       // Force "avalanching" of final 127 bits.
 670       Hash ^= Hash << 3;
 671       Hash += Hash >> 5;
 672       Hash ^= Hash << 4;
 673       Hash += Hash >> 17;
 674       Hash ^= Hash << 25;
 675       Hash += Hash >> 6;
 676       return Hash;
 677     }
 678     static bool isEqual(const ConstantClass *LHS, const ConstantClass *RHS) {
 679       return LHS == RHS;
 680     }
 681     static unsigned getHashValue(const LookupKey &Val) {
 682       // This is adapted from SuperFastHash by Paul Hsieh.
 683       unsigned Hash = TypeClassInfo::getHashValue(Val.first);
 684       for (Operands::const_iterator
 685         I = Val.second.begin(), E = Val.second.end(); I != E; ++I) {
 686         unsigned Data = ConstantInfo::getHashValue(*I);
 687         Hash         += Data & 0xFFFF;
 688         unsigned Tmp  = ((Data >> 16) << 11) ^ Hash;
 689         Hash          = (Hash << 16) ^ Tmp;
 690         Hash         += Hash >> 11;
 691       }
 692
 693       // Force "avalanching" of final 127 bits.
 694       Hash ^= Hash << 3;
 695       Hash += Hash >> 5;
 696       Hash ^= Hash << 4;
 697       Hash += Hash >> 17;
 698       Hash ^= Hash << 25;
 699       Hash += Hash >> 6;
 700       return Hash;
 701     }
 702     static bool isEqual(const LookupKey &LHS, const ConstantClass *RHS) {
 703       if (RHS == getEmptyKey() || RHS == getTombstoneKey())
 704         return false;
 705       if (LHS.first != RHS->getType()
 706           || LHS.second.size() != RHS->getNumOperands())
 707         return false;
 708       for (unsigned I = 0, E = RHS->getNumOperands(); I < E; ++I) {
 709         if (LHS.second[I] != RHS->getOperand(I))
 710           return false;
 711       }
 712       return true;
 713     }
 714   };
 715 public:
 716   typedef DenseMap<ConstantClass *, char, MapInfo> MapTy;
 717
 718 private:
 719   /// Map - This is the main map from the element descriptor to the Constants.
 720   /// This is the primary way we avoid creating two of the same shape
 721   /// constant.
 722   MapTy Map;
 723
 724 public:
 725   typename MapTy::iterator map_begin() { return Map.begin(); }
 726   typename MapTy::iterator map_end() { return Map.end(); }
 727
 728   void freeConstants() {
 729     for (typename MapTy::iterator I=Map.begin(), E=Map.end();
 730          I != E; ++I) {
 731       // Asserts that use_empty().
 732       delete I->first;
 733     }
 734   }
 735
 736 private:
 737   typename MapTy::iterator findExistingElement(ConstantClass *CP) {
 738     return Map.find(CP);
 739   }
 740
 741   ConstantClass *Create(TypeClass *Ty, Operands V, typename MapTy::iterator I) {
 742     ConstantClass* Result =
 743       ConstantArrayCreator<ConstantClass,TypeClass>::create(Ty, V);
 744
 745     assert(Result->getType() == Ty && "Type specified is not correct!");
 746     Map[Result] = '\0';
 747
 748     return Result;
 749   }
 750 public:
 751
 752   /// getOrCreate - Return the specified constant from the map, creating it if
 753   /// necessary.
 754   ConstantClass *getOrCreate(TypeClass *Ty, Operands V) {
 755     LookupKey Lookup(Ty, V);
 756     ConstantClass* Result = 0;
 757
 758     typename MapTy::iterator I = Map.find_as(Lookup);
 759     // Is it in the map?
 760     if (I != Map.end())
 761       Result = I->first;
 762
 763     if (!Result) {
 764       // If no preexisting value, create one now...
 765       Result = Create(Ty, V, I);
 766     }
 767
 768     return Result;
 769   }
 770
 771   /// Find the constant by lookup key.
 772   typename MapTy::iterator find(LookupKey Lookup) {
 773     return Map.find_as(Lookup);
 774   }
 775
 776   /// Insert the constant into its proper slot.
 777   void insert(ConstantClass *CP) {
 778     Map[CP] = '\0';
 779   }
 780
 781   /// Remove this constant from the map
 782   void remove(ConstantClass *CP) {
 783     typename MapTy::iterator I = findExistingElement(CP);
 784     assert(I != Map.end() && "Constant not found in constant table!");
 785     assert(I->first == CP && "Didn't find correct element?");
 786     Map.erase(I);
 787   }
 788
 789   void dump() const {
 790     DEBUG(dbgs() << "Constant.cpp: ConstantUniqueMap\n");
 791   }
 792 };
 793
 794 }
 795
 796 #endif