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