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