lib/IR/ConstantsContext.h

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