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