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