Home | History | Annotate | Download | only in IR 
      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 
     33 /// UnaryConstantExpr - This class is private to Constants.cpp, and is used
     34 /// behind the scenes to implement unary constant exprs.
     35 class UnaryConstantExpr : public ConstantExpr {
     36   void anchor() override;
     37   void *operator new(size_t, unsigned) = delete;
     38 public:
     39   // allocate space for exactly one operand
     40   void *operator new(size_t s) {
     41     return User::operator new(s, 1);
     42   }
     43   UnaryConstantExpr(unsigned Opcode, Constant *C, Type *Ty)
     44     : ConstantExpr(Ty, Opcode, &Op<0>(), 1) {
     45     Op<0>() = C;
     46   }
     47   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
     48 };
     49 
     50 /// BinaryConstantExpr - This class is private to Constants.cpp, and is used
     51 /// behind the scenes to implement binary constant exprs.
     52 class BinaryConstantExpr : public ConstantExpr {
     53   void anchor() override;
     54   void *operator new(size_t, unsigned) = delete;
     55 public:
     56   // allocate space for exactly two operands
     57   void *operator new(size_t s) {
     58     return User::operator new(s, 2);
     59   }
     60   BinaryConstantExpr(unsigned Opcode, Constant *C1, Constant *C2,
     61                      unsigned Flags)
     62     : ConstantExpr(C1->getType(), Opcode, &Op<0>(), 2) {
     63     Op<0>() = C1;
     64     Op<1>() = C2;
     65     SubclassOptionalData = Flags;
     66   }
     67   /// Transparently provide more efficient getOperand methods.
     68   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
     69 };
     70 
     71 /// SelectConstantExpr - This class is private to Constants.cpp, and is used
     72 /// behind the scenes to implement select constant exprs.
     73 class SelectConstantExpr : public ConstantExpr {
     74   void anchor() override;
     75   void *operator new(size_t, unsigned) = delete;
     76 public:
     77   // allocate space for exactly three operands
     78   void *operator new(size_t s) {
     79     return User::operator new(s, 3);
     80   }
     81   SelectConstantExpr(Constant *C1, Constant *C2, Constant *C3)
     82     : ConstantExpr(C2->getType(), Instruction::Select, &Op<0>(), 3) {
     83     Op<0>() = C1;
     84     Op<1>() = C2;
     85     Op<2>() = C3;
     86   }
     87   /// Transparently provide more efficient getOperand methods.
     88   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
     89 };
     90 
     91 /// ExtractElementConstantExpr - This class is private to
     92 /// Constants.cpp, and is used behind the scenes to implement
     93 /// extractelement constant exprs.
     94 class ExtractElementConstantExpr : public ConstantExpr {
     95   void anchor() override;
     96   void *operator new(size_t, unsigned) = delete;
     97 public:
     98   // allocate space for exactly two operands
     99   void *operator new(size_t s) {
    100     return User::operator new(s, 2);
    101   }
    102   ExtractElementConstantExpr(Constant *C1, Constant *C2)
    103     : ConstantExpr(cast<VectorType>(C1->getType())->getElementType(),
    104                    Instruction::ExtractElement, &Op<0>(), 2) {
    105     Op<0>() = C1;
    106     Op<1>() = C2;
    107   }
    108   /// Transparently provide more efficient getOperand methods.
    109   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
    110 };
    111 
    112 /// InsertElementConstantExpr - This class is private to
    113 /// Constants.cpp, and is used behind the scenes to implement
    114 /// insertelement constant exprs.
    115 class InsertElementConstantExpr : public ConstantExpr {
    116   void anchor() override;
    117   void *operator new(size_t, unsigned) = delete;
    118 public:
    119   // allocate space for exactly three operands
    120   void *operator new(size_t s) {
    121     return User::operator new(s, 3);
    122   }
    123   InsertElementConstantExpr(Constant *C1, Constant *C2, Constant *C3)
    124     : ConstantExpr(C1->getType(), Instruction::InsertElement,
    125                    &Op<0>(), 3) {
    126     Op<0>() = C1;
    127     Op<1>() = C2;
    128     Op<2>() = C3;
    129   }
    130   /// Transparently provide more efficient getOperand methods.
    131   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
    132 };
    133 
    134 /// ShuffleVectorConstantExpr - This class is private to
    135 /// Constants.cpp, and is used behind the scenes to implement
    136 /// shufflevector constant exprs.
    137 class ShuffleVectorConstantExpr : public ConstantExpr {
    138   void anchor() override;
    139   void *operator new(size_t, unsigned) = delete;
    140 public:
    141   // allocate space for exactly three operands
    142   void *operator new(size_t s) {
    143     return User::operator new(s, 3);
    144   }
    145   ShuffleVectorConstantExpr(Constant *C1, Constant *C2, Constant *C3)
    146   : ConstantExpr(VectorType::get(
    147                    cast<VectorType>(C1->getType())->getElementType(),
    148                    cast<VectorType>(C3->getType())->getNumElements()),
    149                  Instruction::ShuffleVector,
    150                  &Op<0>(), 3) {
    151     Op<0>() = C1;
    152     Op<1>() = C2;
    153     Op<2>() = C3;
    154   }
    155   /// Transparently provide more efficient getOperand methods.
    156   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
    157 };
    158 
    159 /// ExtractValueConstantExpr - This class is private to
    160 /// Constants.cpp, and is used behind the scenes to implement
    161 /// extractvalue constant exprs.
    162 class ExtractValueConstantExpr : public ConstantExpr {
    163   void anchor() override;
    164   void *operator new(size_t, unsigned) = delete;
    165 public:
    166   // allocate space for exactly one operand
    167   void *operator new(size_t s) {
    168     return User::operator new(s, 1);
    169   }
    170   ExtractValueConstantExpr(Constant *Agg, ArrayRef<unsigned> IdxList,
    171                            Type *DestTy)
    172       : ConstantExpr(DestTy, Instruction::ExtractValue, &Op<0>(), 1),
    173         Indices(IdxList.begin(), IdxList.end()) {
    174     Op<0>() = Agg;
    175   }
    176 
    177   /// Indices - These identify which value to extract.
    178   const SmallVector<unsigned, 4> Indices;
    179 
    180   /// Transparently provide more efficient getOperand methods.
    181   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
    182 };
    183 
    184 /// InsertValueConstantExpr - This class is private to
    185 /// Constants.cpp, and is used behind the scenes to implement
    186 /// insertvalue constant exprs.
    187 class InsertValueConstantExpr : public ConstantExpr {
    188   void anchor() override;
    189   void *operator new(size_t, unsigned) = delete;
    190 public:
    191   // allocate space for exactly one operand
    192   void *operator new(size_t s) {
    193     return User::operator new(s, 2);
    194   }
    195   InsertValueConstantExpr(Constant *Agg, Constant *Val,
    196                           ArrayRef<unsigned> IdxList, Type *DestTy)
    197       : ConstantExpr(DestTy, Instruction::InsertValue, &Op<0>(), 2),
    198         Indices(IdxList.begin(), IdxList.end()) {
    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   void anchor() override;
    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   void anchor() override;
    236   void *operator new(size_t, unsigned) = delete;
    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 template <class ConstantClass> struct ConstantAggrKeyType;
    316 struct InlineAsmKeyType;
    317 struct ConstantExprKeyType;
    318 
    319 template <class ConstantClass> struct ConstantInfo;
    320 template <> struct ConstantInfo<ConstantExpr> {
    321   typedef ConstantExprKeyType ValType;
    322   typedef Type TypeClass;
    323 };
    324 template <> struct ConstantInfo<InlineAsm> {
    325   typedef InlineAsmKeyType ValType;
    326   typedef PointerType TypeClass;
    327 };
    328 template <> struct ConstantInfo<ConstantArray> {
    329   typedef ConstantAggrKeyType<ConstantArray> ValType;
    330   typedef ArrayType TypeClass;
    331 };
    332 template <> struct ConstantInfo<ConstantStruct> {
    333   typedef ConstantAggrKeyType<ConstantStruct> ValType;
    334   typedef StructType TypeClass;
    335 };
    336 template <> struct ConstantInfo<ConstantVector> {
    337   typedef ConstantAggrKeyType<ConstantVector> ValType;
    338   typedef VectorType TypeClass;
    339 };
    340 
    341 template <class ConstantClass> struct ConstantAggrKeyType {
    342   ArrayRef<Constant *> Operands;
    343   ConstantAggrKeyType(ArrayRef<Constant *> Operands) : Operands(Operands) {}
    344   ConstantAggrKeyType(ArrayRef<Constant *> Operands, const ConstantClass *)
    345       : Operands(Operands) {}
    346   ConstantAggrKeyType(const ConstantClass *C,
    347                       SmallVectorImpl<Constant *> &Storage) {
    348     assert(Storage.empty() && "Expected empty storage");
    349     for (unsigned I = 0, E = C->getNumOperands(); I != E; ++I)
    350       Storage.push_back(C->getOperand(I));
    351     Operands = Storage;
    352   }
    353 
    354   bool operator==(const ConstantAggrKeyType &X) const {
    355     return Operands == X.Operands;
    356   }
    357   bool operator==(const ConstantClass *C) const {
    358     if (Operands.size() != C->getNumOperands())
    359       return false;
    360     for (unsigned I = 0, E = Operands.size(); I != E; ++I)
    361       if (Operands[I] != C->getOperand(I))
    362         return false;
    363     return true;
    364   }
    365   unsigned getHash() const {
    366     return hash_combine_range(Operands.begin(), Operands.end());
    367   }
    368 
    369   typedef typename ConstantInfo<ConstantClass>::TypeClass TypeClass;
    370   ConstantClass *create(TypeClass *Ty) const {
    371     return new (Operands.size()) ConstantClass(Ty, Operands);
    372   }
    373 };
    374 
    375 struct InlineAsmKeyType {
    376   StringRef AsmString;
    377   StringRef Constraints;
    378   bool HasSideEffects;
    379   bool IsAlignStack;
    380   InlineAsm::AsmDialect AsmDialect;
    381 
    382   InlineAsmKeyType(StringRef AsmString, StringRef Constraints,
    383                    bool HasSideEffects, bool IsAlignStack,
    384                    InlineAsm::AsmDialect AsmDialect)
    385       : AsmString(AsmString), Constraints(Constraints),
    386         HasSideEffects(HasSideEffects), IsAlignStack(IsAlignStack),
    387         AsmDialect(AsmDialect) {}
    388   InlineAsmKeyType(const InlineAsm *Asm, SmallVectorImpl<Constant *> &)
    389       : AsmString(Asm->getAsmString()), Constraints(Asm->getConstraintString()),
    390         HasSideEffects(Asm->hasSideEffects()),
    391         IsAlignStack(Asm->isAlignStack()), AsmDialect(Asm->getDialect()) {}
    392 
    393   bool operator==(const InlineAsmKeyType &X) const {
    394     return HasSideEffects == X.HasSideEffects &&
    395            IsAlignStack == X.IsAlignStack && AsmDialect == X.AsmDialect &&
    396            AsmString == X.AsmString && Constraints == X.Constraints;
    397   }
    398   bool operator==(const InlineAsm *Asm) const {
    399     return HasSideEffects == Asm->hasSideEffects() &&
    400            IsAlignStack == Asm->isAlignStack() &&
    401            AsmDialect == Asm->getDialect() &&
    402            AsmString == Asm->getAsmString() &&
    403            Constraints == Asm->getConstraintString();
    404   }
    405   unsigned getHash() const {
    406     return hash_combine(AsmString, Constraints, HasSideEffects, IsAlignStack,
    407                         AsmDialect);
    408   }
    409 
    410   typedef ConstantInfo<InlineAsm>::TypeClass TypeClass;
    411   InlineAsm *create(TypeClass *Ty) const {
    412     return new InlineAsm(Ty, AsmString, Constraints, HasSideEffects,
    413                          IsAlignStack, AsmDialect);
    414   }
    415 };
    416 
    417 struct ConstantExprKeyType {
    418   uint8_t Opcode;
    419   uint8_t SubclassOptionalData;
    420   uint16_t SubclassData;
    421   ArrayRef<Constant *> Ops;
    422   ArrayRef<unsigned> Indexes;
    423 
    424   ConstantExprKeyType(unsigned Opcode, ArrayRef<Constant *> Ops,
    425                       unsigned short SubclassData = 0,
    426                       unsigned short SubclassOptionalData = 0,
    427                       ArrayRef<unsigned> Indexes = None)
    428       : Opcode(Opcode), SubclassOptionalData(SubclassOptionalData),
    429         SubclassData(SubclassData), Ops(Ops), Indexes(Indexes) {}
    430   ConstantExprKeyType(ArrayRef<Constant *> Operands, const ConstantExpr *CE)
    431       : Opcode(CE->getOpcode()),
    432         SubclassOptionalData(CE->getRawSubclassOptionalData()),
    433         SubclassData(CE->isCompare() ? CE->getPredicate() : 0), Ops(Operands),
    434         Indexes(CE->hasIndices() ? CE->getIndices() : ArrayRef<unsigned>()) {}
    435   ConstantExprKeyType(const ConstantExpr *CE,
    436                       SmallVectorImpl<Constant *> &Storage)
    437       : Opcode(CE->getOpcode()),
    438         SubclassOptionalData(CE->getRawSubclassOptionalData()),
    439         SubclassData(CE->isCompare() ? CE->getPredicate() : 0),
    440         Indexes(CE->hasIndices() ? CE->getIndices() : ArrayRef<unsigned>()) {
    441     assert(Storage.empty() && "Expected empty storage");
    442     for (unsigned I = 0, E = CE->getNumOperands(); I != E; ++I)
    443       Storage.push_back(CE->getOperand(I));
    444     Ops = Storage;
    445   }
    446 
    447   bool operator==(const ConstantExprKeyType &X) const {
    448     return Opcode == X.Opcode && SubclassData == X.SubclassData &&
    449            SubclassOptionalData == X.SubclassOptionalData && Ops == X.Ops &&
    450            Indexes == X.Indexes;
    451   }
    452 
    453   bool operator==(const ConstantExpr *CE) const {
    454     if (Opcode != CE->getOpcode())
    455       return false;
    456     if (SubclassOptionalData != CE->getRawSubclassOptionalData())
    457       return false;
    458     if (Ops.size() != CE->getNumOperands())
    459       return false;
    460     if (SubclassData != (CE->isCompare() ? CE->getPredicate() : 0))
    461       return false;
    462     for (unsigned I = 0, E = Ops.size(); I != E; ++I)
    463       if (Ops[I] != CE->getOperand(I))
    464         return false;
    465     if (Indexes != (CE->hasIndices() ? CE->getIndices() : ArrayRef<unsigned>()))
    466       return false;
    467     return true;
    468   }
    469 
    470   unsigned getHash() const {
    471     return hash_combine(Opcode, SubclassOptionalData, SubclassData,
    472                         hash_combine_range(Ops.begin(), Ops.end()),
    473                         hash_combine_range(Indexes.begin(), Indexes.end()));
    474   }
    475 
    476   typedef ConstantInfo<ConstantExpr>::TypeClass TypeClass;
    477   ConstantExpr *create(TypeClass *Ty) const {
    478     switch (Opcode) {
    479     default:
    480       if (Instruction::isCast(Opcode))
    481         return new UnaryConstantExpr(Opcode, Ops[0], Ty);
    482       if ((Opcode >= Instruction::BinaryOpsBegin &&
    483            Opcode < Instruction::BinaryOpsEnd))
    484         return new BinaryConstantExpr(Opcode, Ops[0], Ops[1],
    485                                       SubclassOptionalData);
    486       llvm_unreachable("Invalid ConstantExpr!");
    487     case Instruction::Select:
    488       return new SelectConstantExpr(Ops[0], Ops[1], Ops[2]);
    489     case Instruction::ExtractElement:
    490       return new ExtractElementConstantExpr(Ops[0], Ops[1]);
    491     case Instruction::InsertElement:
    492       return new InsertElementConstantExpr(Ops[0], Ops[1], Ops[2]);
    493     case Instruction::ShuffleVector:
    494       return new ShuffleVectorConstantExpr(Ops[0], Ops[1], Ops[2]);
    495     case Instruction::InsertValue:
    496       return new InsertValueConstantExpr(Ops[0], Ops[1], Indexes, Ty);
    497     case Instruction::ExtractValue:
    498       return new ExtractValueConstantExpr(Ops[0], Indexes, Ty);
    499     case Instruction::GetElementPtr:
    500       return GetElementPtrConstantExpr::Create(Ops[0], Ops.slice(1), Ty,
    501                                                SubclassOptionalData);
    502     case Instruction::ICmp:
    503       return new CompareConstantExpr(Ty, Instruction::ICmp, SubclassData,
    504                                      Ops[0], Ops[1]);
    505     case Instruction::FCmp:
    506       return new CompareConstantExpr(Ty, Instruction::FCmp, SubclassData,
    507                                      Ops[0], Ops[1]);
    508     }
    509   }
    510 };
    511 
    512 template <class ConstantClass> class ConstantUniqueMap {
    513 public:
    514   typedef typename ConstantInfo<ConstantClass>::ValType ValType;
    515   typedef typename ConstantInfo<ConstantClass>::TypeClass TypeClass;
    516   typedef std::pair<TypeClass *, ValType> LookupKey;
    517 
    518 private:
    519   struct MapInfo {
    520     typedef DenseMapInfo<ConstantClass *> ConstantClassInfo;
    521     static inline ConstantClass *getEmptyKey() {
    522       return ConstantClassInfo::getEmptyKey();
    523     }
    524     static inline ConstantClass *getTombstoneKey() {
    525       return ConstantClassInfo::getTombstoneKey();
    526     }
    527     static unsigned getHashValue(const ConstantClass *CP) {
    528       SmallVector<Constant *, 8> Storage;
    529       return getHashValue(LookupKey(CP->getType(), ValType(CP, Storage)));
    530     }
    531     static bool isEqual(const ConstantClass *LHS, const ConstantClass *RHS) {
    532       return LHS == RHS;
    533     }
    534     static unsigned getHashValue(const LookupKey &Val) {
    535       return hash_combine(Val.first, Val.second.getHash());
    536     }
    537     static bool isEqual(const LookupKey &LHS, const ConstantClass *RHS) {
    538       if (RHS == getEmptyKey() || RHS == getTombstoneKey())
    539         return false;
    540       if (LHS.first != RHS->getType())
    541         return false;
    542       return LHS.second == RHS;
    543     }
    544   };
    545 
    546 public:
    547   typedef DenseMap<ConstantClass *, char, MapInfo> MapTy;
    548 
    549 private:
    550   MapTy Map;
    551 
    552 public:
    553   typename MapTy::iterator map_begin() { return Map.begin(); }
    554   typename MapTy::iterator map_end() { return Map.end(); }
    555 
    556   void freeConstants() {
    557     for (auto &I : Map)
    558       // Asserts that use_empty().
    559       delete I.first;
    560   }
    561 
    562 private:
    563   ConstantClass *create(TypeClass *Ty, ValType V) {
    564     ConstantClass *Result = V.create(Ty);
    565 
    566     assert(Result->getType() == Ty && "Type specified is not correct!");
    567     insert(Result);
    568 
    569     return Result;
    570   }
    571 
    572 public:
    573   /// Return the specified constant from the map, creating it if necessary.
    574   ConstantClass *getOrCreate(TypeClass *Ty, ValType V) {
    575     LookupKey Lookup(Ty, V);
    576     ConstantClass *Result = nullptr;
    577 
    578     auto I = find(Lookup);
    579     if (I == Map.end())
    580       Result = create(Ty, V);
    581     else
    582       Result = I->first;
    583     assert(Result && "Unexpected nullptr");
    584 
    585     return Result;
    586   }
    587 
    588   /// Find the constant by lookup key.
    589   typename MapTy::iterator find(LookupKey Lookup) {
    590     return Map.find_as(Lookup);
    591   }
    592 
    593   /// Insert the constant into its proper slot.
    594   void insert(ConstantClass *CP) { Map[CP] = '\0'; }
    595 
    596   /// Remove this constant from the map
    597   void remove(ConstantClass *CP) {
    598     typename MapTy::iterator I = Map.find(CP);
    599     assert(I != Map.end() && "Constant not found in constant table!");
    600     assert(I->first == CP && "Didn't find correct element?");
    601     Map.erase(I);
    602   }
    603 
    604   ConstantClass *replaceOperandsInPlace(ArrayRef<Constant *> Operands,
    605                                         ConstantClass *CP, Value *From,
    606                                         Constant *To, unsigned NumUpdated = 0,
    607                                         unsigned OperandNo = ~0u) {
    608     LookupKey Lookup(CP->getType(), ValType(Operands, CP));
    609     auto I = find(Lookup);
    610     if (I != Map.end())
    611       return I->first;
    612 
    613     // Update to the new value.  Optimize for the case when we have a single
    614     // operand that we're changing, but handle bulk updates efficiently.
    615     remove(CP);
    616     if (NumUpdated == 1) {
    617       assert(OperandNo < CP->getNumOperands() && "Invalid index");
    618       assert(CP->getOperand(OperandNo) != To && "I didn't contain From!");
    619       CP->setOperand(OperandNo, To);
    620     } else {
    621       for (unsigned I = 0, E = CP->getNumOperands(); I != E; ++I)
    622         if (CP->getOperand(I) == From)
    623           CP->setOperand(I, To);
    624     }
    625     insert(CP);
    626     return nullptr;
    627   }
    628 
    629   void dump() const { DEBUG(dbgs() << "Constant.cpp: ConstantUniqueMap\n"); }
    630 };
    631 
    632 } // end namespace llvm
    633 
    634 #endif
    635