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/DenseSet.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 
     27 #define DEBUG_TYPE "ir"
     28 
     29 namespace llvm {
     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   void anchor() override;
     35   void *operator new(size_t, unsigned) = delete;
     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   void anchor() override;
     52   void *operator new(size_t, unsigned) = delete;
     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   void anchor() override;
     73   void *operator new(size_t, unsigned) = delete;
     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   void anchor() override;
     94   void *operator new(size_t, unsigned) = delete;
     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   void anchor() override;
    115   void *operator new(size_t, unsigned) = delete;
    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   void anchor() override;
    137   void *operator new(size_t, unsigned) = delete;
    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   void anchor() override;
    162   void *operator new(size_t, unsigned) = delete;
    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, ArrayRef<unsigned> IdxList,
    169                            Type *DestTy)
    170       : ConstantExpr(DestTy, Instruction::ExtractValue, &Op<0>(), 1),
    171         Indices(IdxList.begin(), IdxList.end()) {
    172     Op<0>() = Agg;
    173   }
    174 
    175   /// Indices - These identify which value to extract.
    176   const SmallVector<unsigned, 4> Indices;
    177 
    178   /// Transparently provide more efficient getOperand methods.
    179   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
    180 
    181   static bool classof(const ConstantExpr *CE) {
    182     return CE->getOpcode() == Instruction::ExtractValue;
    183   }
    184   static bool classof(const Value *V) {
    185     return isa<ConstantExpr>(V) && classof(cast<ConstantExpr>(V));
    186   }
    187 };
    188 
    189 /// InsertValueConstantExpr - This class is private to
    190 /// Constants.cpp, and is used behind the scenes to implement
    191 /// insertvalue constant exprs.
    192 class InsertValueConstantExpr : public ConstantExpr {
    193   void anchor() override;
    194   void *operator new(size_t, unsigned) = delete;
    195 public:
    196   // allocate space for exactly one operand
    197   void *operator new(size_t s) {
    198     return User::operator new(s, 2);
    199   }
    200   InsertValueConstantExpr(Constant *Agg, Constant *Val,
    201                           ArrayRef<unsigned> IdxList, Type *DestTy)
    202       : ConstantExpr(DestTy, Instruction::InsertValue, &Op<0>(), 2),
    203         Indices(IdxList.begin(), IdxList.end()) {
    204     Op<0>() = Agg;
    205     Op<1>() = Val;
    206   }
    207 
    208   /// Indices - These identify the position for the insertion.
    209   const SmallVector<unsigned, 4> Indices;
    210 
    211   /// Transparently provide more efficient getOperand methods.
    212   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
    213 
    214   static bool classof(const ConstantExpr *CE) {
    215     return CE->getOpcode() == Instruction::InsertValue;
    216   }
    217   static bool classof(const Value *V) {
    218     return isa<ConstantExpr>(V) && classof(cast<ConstantExpr>(V));
    219   }
    220 };
    221 
    222 /// GetElementPtrConstantExpr - This class is private to Constants.cpp, and is
    223 /// used behind the scenes to implement getelementpr constant exprs.
    224 class GetElementPtrConstantExpr : public ConstantExpr {
    225   Type *SrcElementTy;
    226   Type *ResElementTy;
    227   void anchor() override;
    228   GetElementPtrConstantExpr(Type *SrcElementTy, Constant *C,
    229                             ArrayRef<Constant *> IdxList, Type *DestTy);
    230 
    231 public:
    232   static GetElementPtrConstantExpr *Create(Type *SrcElementTy, Constant *C,
    233                                            ArrayRef<Constant *> IdxList,
    234                                            Type *DestTy, unsigned Flags) {
    235     GetElementPtrConstantExpr *Result = new (IdxList.size() + 1)
    236         GetElementPtrConstantExpr(SrcElementTy, C, IdxList, DestTy);
    237     Result->SubclassOptionalData = Flags;
    238     return Result;
    239   }
    240   Type *getSourceElementType() const;
    241   Type *getResultElementType() const;
    242   /// Transparently provide more efficient getOperand methods.
    243   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
    244 
    245   static bool classof(const ConstantExpr *CE) {
    246     return CE->getOpcode() == Instruction::GetElementPtr;
    247   }
    248   static bool classof(const Value *V) {
    249     return isa<ConstantExpr>(V) && classof(cast<ConstantExpr>(V));
    250   }
    251 };
    252 
    253 // CompareConstantExpr - This class is private to Constants.cpp, and is used
    254 // behind the scenes to implement ICmp and FCmp constant expressions. This is
    255 // needed in order to store the predicate value for these instructions.
    256 class CompareConstantExpr : public ConstantExpr {
    257   void anchor() override;
    258   void *operator new(size_t, unsigned) = delete;
    259 public:
    260   // allocate space for exactly two operands
    261   void *operator new(size_t s) {
    262     return User::operator new(s, 2);
    263   }
    264   unsigned short predicate;
    265   CompareConstantExpr(Type *ty, Instruction::OtherOps opc,
    266                       unsigned short pred,  Constant* LHS, Constant* RHS)
    267     : ConstantExpr(ty, opc, &Op<0>(), 2), predicate(pred) {
    268     Op<0>() = LHS;
    269     Op<1>() = RHS;
    270   }
    271   /// Transparently provide more efficient getOperand methods.
    272   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
    273 
    274   static bool classof(const ConstantExpr *CE) {
    275     return CE->getOpcode() == Instruction::ICmp ||
    276            CE->getOpcode() == Instruction::FCmp;
    277   }
    278   static bool classof(const Value *V) {
    279     return isa<ConstantExpr>(V) && classof(cast<ConstantExpr>(V));
    280   }
    281 };
    282 
    283 template <>
    284 struct OperandTraits<UnaryConstantExpr>
    285     : public FixedNumOperandTraits<UnaryConstantExpr, 1> {};
    286 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(UnaryConstantExpr, Value)
    287 
    288 template <>
    289 struct OperandTraits<BinaryConstantExpr>
    290     : public FixedNumOperandTraits<BinaryConstantExpr, 2> {};
    291 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(BinaryConstantExpr, Value)
    292 
    293 template <>
    294 struct OperandTraits<SelectConstantExpr>
    295     : public FixedNumOperandTraits<SelectConstantExpr, 3> {};
    296 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(SelectConstantExpr, Value)
    297 
    298 template <>
    299 struct OperandTraits<ExtractElementConstantExpr>
    300     : public FixedNumOperandTraits<ExtractElementConstantExpr, 2> {};
    301 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ExtractElementConstantExpr, Value)
    302 
    303 template <>
    304 struct OperandTraits<InsertElementConstantExpr>
    305     : public FixedNumOperandTraits<InsertElementConstantExpr, 3> {};
    306 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(InsertElementConstantExpr, Value)
    307 
    308 template <>
    309 struct OperandTraits<ShuffleVectorConstantExpr>
    310     : public FixedNumOperandTraits<ShuffleVectorConstantExpr, 3> {};
    311 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ShuffleVectorConstantExpr, Value)
    312 
    313 template <>
    314 struct OperandTraits<ExtractValueConstantExpr>
    315     : public FixedNumOperandTraits<ExtractValueConstantExpr, 1> {};
    316 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ExtractValueConstantExpr, Value)
    317 
    318 template <>
    319 struct OperandTraits<InsertValueConstantExpr>
    320     : public FixedNumOperandTraits<InsertValueConstantExpr, 2> {};
    321 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(InsertValueConstantExpr, Value)
    322 
    323 template <>
    324 struct OperandTraits<GetElementPtrConstantExpr>
    325     : public VariadicOperandTraits<GetElementPtrConstantExpr, 1> {};
    326 
    327 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(GetElementPtrConstantExpr, Value)
    328 
    329 template <>
    330 struct OperandTraits<CompareConstantExpr>
    331     : public FixedNumOperandTraits<CompareConstantExpr, 2> {};
    332 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(CompareConstantExpr, Value)
    333 
    334 template <class ConstantClass> struct ConstantAggrKeyType;
    335 struct InlineAsmKeyType;
    336 struct ConstantExprKeyType;
    337 
    338 template <class ConstantClass> struct ConstantInfo;
    339 template <> struct ConstantInfo<ConstantExpr> {
    340   typedef ConstantExprKeyType ValType;
    341   typedef Type TypeClass;
    342 };
    343 template <> struct ConstantInfo<InlineAsm> {
    344   typedef InlineAsmKeyType ValType;
    345   typedef PointerType TypeClass;
    346 };
    347 template <> struct ConstantInfo<ConstantArray> {
    348   typedef ConstantAggrKeyType<ConstantArray> ValType;
    349   typedef ArrayType TypeClass;
    350 };
    351 template <> struct ConstantInfo<ConstantStruct> {
    352   typedef ConstantAggrKeyType<ConstantStruct> ValType;
    353   typedef StructType TypeClass;
    354 };
    355 template <> struct ConstantInfo<ConstantVector> {
    356   typedef ConstantAggrKeyType<ConstantVector> ValType;
    357   typedef VectorType TypeClass;
    358 };
    359 
    360 template <class ConstantClass> struct ConstantAggrKeyType {
    361   ArrayRef<Constant *> Operands;
    362   ConstantAggrKeyType(ArrayRef<Constant *> Operands) : Operands(Operands) {}
    363   ConstantAggrKeyType(ArrayRef<Constant *> Operands, const ConstantClass *)
    364       : Operands(Operands) {}
    365   ConstantAggrKeyType(const ConstantClass *C,
    366                       SmallVectorImpl<Constant *> &Storage) {
    367     assert(Storage.empty() && "Expected empty storage");
    368     for (unsigned I = 0, E = C->getNumOperands(); I != E; ++I)
    369       Storage.push_back(C->getOperand(I));
    370     Operands = Storage;
    371   }
    372 
    373   bool operator==(const ConstantAggrKeyType &X) const {
    374     return Operands == X.Operands;
    375   }
    376   bool operator==(const ConstantClass *C) const {
    377     if (Operands.size() != C->getNumOperands())
    378       return false;
    379     for (unsigned I = 0, E = Operands.size(); I != E; ++I)
    380       if (Operands[I] != C->getOperand(I))
    381         return false;
    382     return true;
    383   }
    384   unsigned getHash() const {
    385     return hash_combine_range(Operands.begin(), Operands.end());
    386   }
    387 
    388   typedef typename ConstantInfo<ConstantClass>::TypeClass TypeClass;
    389   ConstantClass *create(TypeClass *Ty) const {
    390     return new (Operands.size()) ConstantClass(Ty, Operands);
    391   }
    392 };
    393 
    394 struct InlineAsmKeyType {
    395   StringRef AsmString;
    396   StringRef Constraints;
    397   FunctionType *FTy;
    398   bool HasSideEffects;
    399   bool IsAlignStack;
    400   InlineAsm::AsmDialect AsmDialect;
    401 
    402   InlineAsmKeyType(StringRef AsmString, StringRef Constraints,
    403                    FunctionType *FTy, bool HasSideEffects, bool IsAlignStack,
    404                    InlineAsm::AsmDialect AsmDialect)
    405       : AsmString(AsmString), Constraints(Constraints), FTy(FTy),
    406         HasSideEffects(HasSideEffects), IsAlignStack(IsAlignStack),
    407         AsmDialect(AsmDialect) {}
    408   InlineAsmKeyType(const InlineAsm *Asm, SmallVectorImpl<Constant *> &)
    409       : AsmString(Asm->getAsmString()), Constraints(Asm->getConstraintString()),
    410         FTy(Asm->getFunctionType()), HasSideEffects(Asm->hasSideEffects()),
    411         IsAlignStack(Asm->isAlignStack()), AsmDialect(Asm->getDialect()) {}
    412 
    413   bool operator==(const InlineAsmKeyType &X) const {
    414     return HasSideEffects == X.HasSideEffects &&
    415            IsAlignStack == X.IsAlignStack && AsmDialect == X.AsmDialect &&
    416            AsmString == X.AsmString && Constraints == X.Constraints &&
    417            FTy == X.FTy;
    418   }
    419   bool operator==(const InlineAsm *Asm) const {
    420     return HasSideEffects == Asm->hasSideEffects() &&
    421            IsAlignStack == Asm->isAlignStack() &&
    422            AsmDialect == Asm->getDialect() &&
    423            AsmString == Asm->getAsmString() &&
    424            Constraints == Asm->getConstraintString() &&
    425            FTy == Asm->getFunctionType();
    426   }
    427   unsigned getHash() const {
    428     return hash_combine(AsmString, Constraints, HasSideEffects, IsAlignStack,
    429                         AsmDialect, FTy);
    430   }
    431 
    432   typedef ConstantInfo<InlineAsm>::TypeClass TypeClass;
    433   InlineAsm *create(TypeClass *Ty) const {
    434     assert(PointerType::getUnqual(FTy) == Ty);
    435     return new InlineAsm(FTy, AsmString, Constraints, HasSideEffects,
    436                          IsAlignStack, AsmDialect);
    437   }
    438 };
    439 
    440 struct ConstantExprKeyType {
    441   uint8_t Opcode;
    442   uint8_t SubclassOptionalData;
    443   uint16_t SubclassData;
    444   ArrayRef<Constant *> Ops;
    445   ArrayRef<unsigned> Indexes;
    446   Type *ExplicitTy;
    447 
    448   ConstantExprKeyType(unsigned Opcode, ArrayRef<Constant *> Ops,
    449                       unsigned short SubclassData = 0,
    450                       unsigned short SubclassOptionalData = 0,
    451                       ArrayRef<unsigned> Indexes = None,
    452                       Type *ExplicitTy = nullptr)
    453       : Opcode(Opcode), SubclassOptionalData(SubclassOptionalData),
    454         SubclassData(SubclassData), Ops(Ops), Indexes(Indexes),
    455         ExplicitTy(ExplicitTy) {}
    456   ConstantExprKeyType(ArrayRef<Constant *> Operands, const ConstantExpr *CE)
    457       : Opcode(CE->getOpcode()),
    458         SubclassOptionalData(CE->getRawSubclassOptionalData()),
    459         SubclassData(CE->isCompare() ? CE->getPredicate() : 0), Ops(Operands),
    460         Indexes(CE->hasIndices() ? CE->getIndices() : ArrayRef<unsigned>()) {}
    461   ConstantExprKeyType(const ConstantExpr *CE,
    462                       SmallVectorImpl<Constant *> &Storage)
    463       : Opcode(CE->getOpcode()),
    464         SubclassOptionalData(CE->getRawSubclassOptionalData()),
    465         SubclassData(CE->isCompare() ? CE->getPredicate() : 0),
    466         Indexes(CE->hasIndices() ? CE->getIndices() : ArrayRef<unsigned>()) {
    467     assert(Storage.empty() && "Expected empty storage");
    468     for (unsigned I = 0, E = CE->getNumOperands(); I != E; ++I)
    469       Storage.push_back(CE->getOperand(I));
    470     Ops = Storage;
    471   }
    472 
    473   bool operator==(const ConstantExprKeyType &X) const {
    474     return Opcode == X.Opcode && SubclassData == X.SubclassData &&
    475            SubclassOptionalData == X.SubclassOptionalData && Ops == X.Ops &&
    476            Indexes == X.Indexes;
    477   }
    478 
    479   bool operator==(const ConstantExpr *CE) const {
    480     if (Opcode != CE->getOpcode())
    481       return false;
    482     if (SubclassOptionalData != CE->getRawSubclassOptionalData())
    483       return false;
    484     if (Ops.size() != CE->getNumOperands())
    485       return false;
    486     if (SubclassData != (CE->isCompare() ? CE->getPredicate() : 0))
    487       return false;
    488     for (unsigned I = 0, E = Ops.size(); I != E; ++I)
    489       if (Ops[I] != CE->getOperand(I))
    490         return false;
    491     if (Indexes != (CE->hasIndices() ? CE->getIndices() : ArrayRef<unsigned>()))
    492       return false;
    493     return true;
    494   }
    495 
    496   unsigned getHash() const {
    497     return hash_combine(Opcode, SubclassOptionalData, SubclassData,
    498                         hash_combine_range(Ops.begin(), Ops.end()),
    499                         hash_combine_range(Indexes.begin(), Indexes.end()));
    500   }
    501 
    502   typedef ConstantInfo<ConstantExpr>::TypeClass TypeClass;
    503   ConstantExpr *create(TypeClass *Ty) const {
    504     switch (Opcode) {
    505     default:
    506       if (Instruction::isCast(Opcode))
    507         return new UnaryConstantExpr(Opcode, Ops[0], Ty);
    508       if ((Opcode >= Instruction::BinaryOpsBegin &&
    509            Opcode < Instruction::BinaryOpsEnd))
    510         return new BinaryConstantExpr(Opcode, Ops[0], Ops[1],
    511                                       SubclassOptionalData);
    512       llvm_unreachable("Invalid ConstantExpr!");
    513     case Instruction::Select:
    514       return new SelectConstantExpr(Ops[0], Ops[1], Ops[2]);
    515     case Instruction::ExtractElement:
    516       return new ExtractElementConstantExpr(Ops[0], Ops[1]);
    517     case Instruction::InsertElement:
    518       return new InsertElementConstantExpr(Ops[0], Ops[1], Ops[2]);
    519     case Instruction::ShuffleVector:
    520       return new ShuffleVectorConstantExpr(Ops[0], Ops[1], Ops[2]);
    521     case Instruction::InsertValue:
    522       return new InsertValueConstantExpr(Ops[0], Ops[1], Indexes, Ty);
    523     case Instruction::ExtractValue:
    524       return new ExtractValueConstantExpr(Ops[0], Indexes, Ty);
    525     case Instruction::GetElementPtr:
    526       return GetElementPtrConstantExpr::Create(
    527           ExplicitTy ? ExplicitTy
    528                      : cast<PointerType>(Ops[0]->getType()->getScalarType())
    529                            ->getElementType(),
    530           Ops[0], Ops.slice(1), Ty, SubclassOptionalData);
    531     case Instruction::ICmp:
    532       return new CompareConstantExpr(Ty, Instruction::ICmp, SubclassData,
    533                                      Ops[0], Ops[1]);
    534     case Instruction::FCmp:
    535       return new CompareConstantExpr(Ty, Instruction::FCmp, SubclassData,
    536                                      Ops[0], Ops[1]);
    537     }
    538   }
    539 };
    540 
    541 template <class ConstantClass> class ConstantUniqueMap {
    542 public:
    543   typedef typename ConstantInfo<ConstantClass>::ValType ValType;
    544   typedef typename ConstantInfo<ConstantClass>::TypeClass TypeClass;
    545   typedef std::pair<TypeClass *, ValType> LookupKey;
    546 
    547   /// Key and hash together, so that we compute the hash only once and reuse it.
    548   typedef std::pair<unsigned, LookupKey> LookupKeyHashed;
    549 
    550 private:
    551   struct MapInfo {
    552     typedef DenseMapInfo<ConstantClass *> ConstantClassInfo;
    553     static inline ConstantClass *getEmptyKey() {
    554       return ConstantClassInfo::getEmptyKey();
    555     }
    556     static inline ConstantClass *getTombstoneKey() {
    557       return ConstantClassInfo::getTombstoneKey();
    558     }
    559     static unsigned getHashValue(const ConstantClass *CP) {
    560       SmallVector<Constant *, 32> Storage;
    561       return getHashValue(LookupKey(CP->getType(), ValType(CP, Storage)));
    562     }
    563     static bool isEqual(const ConstantClass *LHS, const ConstantClass *RHS) {
    564       return LHS == RHS;
    565     }
    566     static unsigned getHashValue(const LookupKey &Val) {
    567       return hash_combine(Val.first, Val.second.getHash());
    568     }
    569     static unsigned getHashValue(const LookupKeyHashed &Val) {
    570       return Val.first;
    571     }
    572     static bool isEqual(const LookupKey &LHS, const ConstantClass *RHS) {
    573       if (RHS == getEmptyKey() || RHS == getTombstoneKey())
    574         return false;
    575       if (LHS.first != RHS->getType())
    576         return false;
    577       return LHS.second == RHS;
    578     }
    579     static bool isEqual(const LookupKeyHashed &LHS, const ConstantClass *RHS) {
    580       return isEqual(LHS.second, RHS);
    581     }
    582   };
    583 
    584 public:
    585   typedef DenseSet<ConstantClass *, MapInfo> MapTy;
    586 
    587 private:
    588   MapTy Map;
    589 
    590 public:
    591   typename MapTy::iterator begin() { return Map.begin(); }
    592   typename MapTy::iterator end() { return Map.end(); }
    593 
    594   void freeConstants() {
    595     for (auto &I : Map)
    596       delete I; // Asserts that use_empty().
    597   }
    598 private:
    599   ConstantClass *create(TypeClass *Ty, ValType V, LookupKeyHashed &HashKey) {
    600     ConstantClass *Result = V.create(Ty);
    601 
    602     assert(Result->getType() == Ty && "Type specified is not correct!");
    603     Map.insert_as(Result, HashKey);
    604 
    605     return Result;
    606   }
    607 
    608 public:
    609   /// Return the specified constant from the map, creating it if necessary.
    610   ConstantClass *getOrCreate(TypeClass *Ty, ValType V) {
    611     LookupKey Key(Ty, V);
    612     /// Hash once, and reuse it for the lookup and the insertion if needed.
    613     LookupKeyHashed Lookup(MapInfo::getHashValue(Key), Key);
    614 
    615     ConstantClass *Result = nullptr;
    616 
    617     auto I = Map.find_as(Lookup);
    618     if (I == Map.end())
    619       Result = create(Ty, V, Lookup);
    620     else
    621       Result = *I;
    622     assert(Result && "Unexpected nullptr");
    623 
    624     return Result;
    625   }
    626 
    627   /// Remove this constant from the map
    628   void remove(ConstantClass *CP) {
    629     typename MapTy::iterator I = Map.find(CP);
    630     assert(I != Map.end() && "Constant not found in constant table!");
    631     assert(*I == CP && "Didn't find correct element?");
    632     Map.erase(I);
    633   }
    634 
    635   ConstantClass *replaceOperandsInPlace(ArrayRef<Constant *> Operands,
    636                                         ConstantClass *CP, Value *From,
    637                                         Constant *To, unsigned NumUpdated = 0,
    638                                         unsigned OperandNo = ~0u) {
    639     LookupKey Key(CP->getType(), ValType(Operands, CP));
    640     /// Hash once, and reuse it for the lookup and the insertion if needed.
    641     LookupKeyHashed Lookup(MapInfo::getHashValue(Key), Key);
    642 
    643     auto I = Map.find_as(Lookup);
    644     if (I != Map.end())
    645       return *I;
    646 
    647     // Update to the new value.  Optimize for the case when we have a single
    648     // operand that we're changing, but handle bulk updates efficiently.
    649     remove(CP);
    650     if (NumUpdated == 1) {
    651       assert(OperandNo < CP->getNumOperands() && "Invalid index");
    652       assert(CP->getOperand(OperandNo) != To && "I didn't contain From!");
    653       CP->setOperand(OperandNo, To);
    654     } else {
    655       for (unsigned I = 0, E = CP->getNumOperands(); I != E; ++I)
    656         if (CP->getOperand(I) == From)
    657           CP->setOperand(I, To);
    658     }
    659     Map.insert_as(CP, Lookup);
    660     return nullptr;
    661   }
    662 
    663   void dump() const { DEBUG(dbgs() << "Constant.cpp: ConstantUniqueMap\n"); }
    664 };
    665 
    666 } // end namespace llvm
    667 
    668 #endif
    669