• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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
new(size_t s)38   void *operator new(size_t s) {
39     return User::operator new(s, 1);
40   }
UnaryConstantExpr(unsigned Opcode,Constant * C,Type * Ty)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
new(size_t s)55   void *operator new(size_t s) {
56     return User::operator new(s, 2);
57   }
BinaryConstantExpr(unsigned Opcode,Constant * C1,Constant * C2,unsigned Flags)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
new(size_t s)76   void *operator new(size_t s) {
77     return User::operator new(s, 3);
78   }
SelectConstantExpr(Constant * C1,Constant * C2,Constant * C3)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
new(size_t s)97   void *operator new(size_t s) {
98     return User::operator new(s, 2);
99   }
ExtractElementConstantExpr(Constant * C1,Constant * C2)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
new(size_t s)118   void *operator new(size_t s) {
119     return User::operator new(s, 3);
120   }
InsertElementConstantExpr(Constant * C1,Constant * C2,Constant * C3)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
new(size_t s)140   void *operator new(size_t s) {
141     return User::operator new(s, 3);
142   }
ShuffleVectorConstantExpr(Constant * C1,Constant * C2,Constant * C3)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
new(size_t s)165   void *operator new(size_t s) {
166     return User::operator new(s, 1);
167   }
ExtractValueConstantExpr(Constant * Agg,ArrayRef<unsigned> IdxList,Type * DestTy)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 
classof(const ConstantExpr * CE)181   static bool classof(const ConstantExpr *CE) {
182     return CE->getOpcode() == Instruction::ExtractValue;
183   }
classof(const Value * V)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
new(size_t s)197   void *operator new(size_t s) {
198     return User::operator new(s, 2);
199   }
InsertValueConstantExpr(Constant * Agg,Constant * Val,ArrayRef<unsigned> IdxList,Type * DestTy)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 
classof(const ConstantExpr * CE)214   static bool classof(const ConstantExpr *CE) {
215     return CE->getOpcode() == Instruction::InsertValue;
216   }
classof(const Value * V)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:
Create(Type * SrcElementTy,Constant * C,ArrayRef<Constant * > IdxList,Type * DestTy,unsigned Flags)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 
classof(const ConstantExpr * CE)245   static bool classof(const ConstantExpr *CE) {
246     return CE->getOpcode() == Instruction::GetElementPtr;
247   }
classof(const Value * V)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
new(size_t s)261   void *operator new(size_t s) {
262     return User::operator new(s, 2);
263   }
264   unsigned short predicate;
CompareConstantExpr(Type * ty,Instruction::OtherOps opc,unsigned short pred,Constant * LHS,Constant * RHS)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 
classof(const ConstantExpr * CE)274   static bool classof(const ConstantExpr *CE) {
275     return CE->getOpcode() == Instruction::ICmp ||
276            CE->getOpcode() == Instruction::FCmp;
277   }
classof(const Value * V)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
669