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