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