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