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