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