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