lib/IR/ConstantsContext.h

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