contrib/llvm/lib/IR/ConstantsContext.h

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