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