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 /// ExtractValueConstantExpr - This class is private to
213 /// Constants.cpp, and is used behind the scenes to implement
214 /// extractvalue constant exprs.
215 class ExtractValueConstantExpr final : public ConstantExpr {
216 public:
217   ExtractValueConstantExpr(Constant *Agg, ArrayRef<unsigned> IdxList,
218                            Type *DestTy)
219       : ConstantExpr(DestTy, Instruction::ExtractValue, &Op<0>(), 1),
220         Indices(IdxList.begin(), IdxList.end()) {
221     Op<0>() = Agg;
222   }
223 
224   // allocate space for exactly one operand
225   void *operator new(size_t S) { return User::operator new(S, 1); }
226   void operator delete(void *Ptr) { User::operator delete(Ptr); }
227 
228   /// Indices - These identify which value to extract.
229   const SmallVector<unsigned, 4> Indices;
230 
231   /// Transparently provide more efficient getOperand methods.
232   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
233 
234   static bool classof(const ConstantExpr *CE) {
235     return CE->getOpcode() == Instruction::ExtractValue;
236   }
237   static bool classof(const Value *V) {
238     return isa<ConstantExpr>(V) && classof(cast<ConstantExpr>(V));
239   }
240 };
241 
242 /// InsertValueConstantExpr - This class is private to
243 /// Constants.cpp, and is used behind the scenes to implement
244 /// insertvalue constant exprs.
245 class InsertValueConstantExpr final : public ConstantExpr {
246 public:
247   InsertValueConstantExpr(Constant *Agg, Constant *Val,
248                           ArrayRef<unsigned> IdxList, Type *DestTy)
249       : ConstantExpr(DestTy, Instruction::InsertValue, &Op<0>(), 2),
250         Indices(IdxList.begin(), IdxList.end()) {
251     Op<0>() = Agg;
252     Op<1>() = Val;
253   }
254 
255   // allocate space for exactly one operand
256   void *operator new(size_t S) { return User::operator new(S, 2); }
257   void operator delete(void *Ptr) { User::operator delete(Ptr); }
258 
259   /// Indices - These identify the position for the insertion.
260   const SmallVector<unsigned, 4> Indices;
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::InsertValue;
267   }
268   static bool classof(const Value *V) {
269     return isa<ConstantExpr>(V) && classof(cast<ConstantExpr>(V));
270   }
271 };
272 
273 /// GetElementPtrConstantExpr - This class is private to Constants.cpp, and is
274 /// used behind the scenes to implement getelementpr constant exprs.
275 class GetElementPtrConstantExpr final : public ConstantExpr {
276   Type *SrcElementTy;
277   Type *ResElementTy;
278 
279   GetElementPtrConstantExpr(Type *SrcElementTy, Constant *C,
280                             ArrayRef<Constant *> IdxList, Type *DestTy);
281 
282 public:
283   static GetElementPtrConstantExpr *Create(Type *SrcElementTy, Constant *C,
284                                            ArrayRef<Constant *> IdxList,
285                                            Type *DestTy, unsigned Flags) {
286     GetElementPtrConstantExpr *Result = new (IdxList.size() + 1)
287         GetElementPtrConstantExpr(SrcElementTy, C, IdxList, DestTy);
288     Result->SubclassOptionalData = Flags;
289     return Result;
290   }
291 
292   Type *getSourceElementType() const;
293   Type *getResultElementType() const;
294 
295   /// Transparently provide more efficient getOperand methods.
296   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
297 
298   static bool classof(const ConstantExpr *CE) {
299     return CE->getOpcode() == Instruction::GetElementPtr;
300   }
301   static bool classof(const Value *V) {
302     return isa<ConstantExpr>(V) && classof(cast<ConstantExpr>(V));
303   }
304 };
305 
306 // CompareConstantExpr - This class is private to Constants.cpp, and is used
307 // behind the scenes to implement ICmp and FCmp constant expressions. This is
308 // needed in order to store the predicate value for these instructions.
309 class CompareConstantExpr final : public ConstantExpr {
310 public:
311   unsigned short predicate;
312   CompareConstantExpr(Type *ty, Instruction::OtherOps opc,
313                       unsigned short pred,  Constant* LHS, Constant* RHS)
314     : ConstantExpr(ty, opc, &Op<0>(), 2), predicate(pred) {
315     Op<0>() = LHS;
316     Op<1>() = RHS;
317   }
318 
319   // allocate space for exactly two operands
320   void *operator new(size_t S) { return User::operator new(S, 2); }
321   void operator delete(void *Ptr) { return User::operator delete(Ptr); }
322 
323   /// Transparently provide more efficient getOperand methods.
324   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
325 
326   static bool classof(const ConstantExpr *CE) {
327     return CE->getOpcode() == Instruction::ICmp ||
328            CE->getOpcode() == Instruction::FCmp;
329   }
330   static bool classof(const Value *V) {
331     return isa<ConstantExpr>(V) && classof(cast<ConstantExpr>(V));
332   }
333 };
334 
335 template <>
336 struct OperandTraits<UnaryConstantExpr>
337     : public FixedNumOperandTraits<UnaryConstantExpr, 1> {};
338 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(UnaryConstantExpr, Value)
339 
340 template <>
341 struct OperandTraits<BinaryConstantExpr>
342     : public FixedNumOperandTraits<BinaryConstantExpr, 2> {};
343 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(BinaryConstantExpr, Value)
344 
345 template <>
346 struct OperandTraits<SelectConstantExpr>
347     : public FixedNumOperandTraits<SelectConstantExpr, 3> {};
348 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(SelectConstantExpr, Value)
349 
350 template <>
351 struct OperandTraits<ExtractElementConstantExpr>
352     : public FixedNumOperandTraits<ExtractElementConstantExpr, 2> {};
353 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ExtractElementConstantExpr, Value)
354 
355 template <>
356 struct OperandTraits<InsertElementConstantExpr>
357     : public FixedNumOperandTraits<InsertElementConstantExpr, 3> {};
358 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(InsertElementConstantExpr, Value)
359 
360 template <>
361 struct OperandTraits<ShuffleVectorConstantExpr>
362     : public FixedNumOperandTraits<ShuffleVectorConstantExpr, 2> {};
363 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ShuffleVectorConstantExpr, Value)
364 
365 template <>
366 struct OperandTraits<ExtractValueConstantExpr>
367     : public FixedNumOperandTraits<ExtractValueConstantExpr, 1> {};
368 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ExtractValueConstantExpr, Value)
369 
370 template <>
371 struct OperandTraits<InsertValueConstantExpr>
372     : public FixedNumOperandTraits<InsertValueConstantExpr, 2> {};
373 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(InsertValueConstantExpr, Value)
374 
375 template <>
376 struct OperandTraits<GetElementPtrConstantExpr>
377     : public VariadicOperandTraits<GetElementPtrConstantExpr, 1> {};
378 
379 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(GetElementPtrConstantExpr, Value)
380 
381 template <>
382 struct OperandTraits<CompareConstantExpr>
383     : public FixedNumOperandTraits<CompareConstantExpr, 2> {};
384 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(CompareConstantExpr, Value)
385 
386 template <class ConstantClass> struct ConstantAggrKeyType;
387 struct InlineAsmKeyType;
388 struct ConstantExprKeyType;
389 
390 template <class ConstantClass> struct ConstantInfo;
391 template <> struct ConstantInfo<ConstantExpr> {
392   using ValType = ConstantExprKeyType;
393   using TypeClass = Type;
394 };
395 template <> struct ConstantInfo<InlineAsm> {
396   using ValType = InlineAsmKeyType;
397   using TypeClass = PointerType;
398 };
399 template <> struct ConstantInfo<ConstantArray> {
400   using ValType = ConstantAggrKeyType<ConstantArray>;
401   using TypeClass = ArrayType;
402 };
403 template <> struct ConstantInfo<ConstantStruct> {
404   using ValType = ConstantAggrKeyType<ConstantStruct>;
405   using TypeClass = StructType;
406 };
407 template <> struct ConstantInfo<ConstantVector> {
408   using ValType = ConstantAggrKeyType<ConstantVector>;
409   using TypeClass = VectorType;
410 };
411 
412 template <class ConstantClass> struct ConstantAggrKeyType {
413   ArrayRef<Constant *> Operands;
414 
415   ConstantAggrKeyType(ArrayRef<Constant *> Operands) : Operands(Operands) {}
416 
417   ConstantAggrKeyType(ArrayRef<Constant *> Operands, const ConstantClass *)
418       : Operands(Operands) {}
419 
420   ConstantAggrKeyType(const ConstantClass *C,
421                       SmallVectorImpl<Constant *> &Storage) {
422     assert(Storage.empty() && "Expected empty storage");
423     for (unsigned I = 0, E = C->getNumOperands(); I != E; ++I)
424       Storage.push_back(C->getOperand(I));
425     Operands = Storage;
426   }
427 
428   bool operator==(const ConstantAggrKeyType &X) const {
429     return Operands == X.Operands;
430   }
431 
432   bool operator==(const ConstantClass *C) const {
433     if (Operands.size() != C->getNumOperands())
434       return false;
435     for (unsigned I = 0, E = Operands.size(); I != E; ++I)
436       if (Operands[I] != C->getOperand(I))
437         return false;
438     return true;
439   }
440 
441   unsigned getHash() const {
442     return hash_combine_range(Operands.begin(), Operands.end());
443   }
444 
445   using TypeClass = typename ConstantInfo<ConstantClass>::TypeClass;
446 
447   ConstantClass *create(TypeClass *Ty) const {
448     return new (Operands.size()) ConstantClass(Ty, Operands);
449   }
450 };
451 
452 struct InlineAsmKeyType {
453   StringRef AsmString;
454   StringRef Constraints;
455   FunctionType *FTy;
456   bool HasSideEffects;
457   bool IsAlignStack;
458   InlineAsm::AsmDialect AsmDialect;
459   bool CanThrow;
460 
461   InlineAsmKeyType(StringRef AsmString, StringRef Constraints,
462                    FunctionType *FTy, bool HasSideEffects, bool IsAlignStack,
463                    InlineAsm::AsmDialect AsmDialect, bool canThrow)
464       : AsmString(AsmString), Constraints(Constraints), FTy(FTy),
465         HasSideEffects(HasSideEffects), IsAlignStack(IsAlignStack),
466         AsmDialect(AsmDialect), CanThrow(canThrow) {}
467 
468   InlineAsmKeyType(const InlineAsm *Asm, SmallVectorImpl<Constant *> &)
469       : AsmString(Asm->getAsmString()), Constraints(Asm->getConstraintString()),
470         FTy(Asm->getFunctionType()), HasSideEffects(Asm->hasSideEffects()),
471         IsAlignStack(Asm->isAlignStack()), AsmDialect(Asm->getDialect()),
472         CanThrow(Asm->canThrow()) {}
473 
474   bool operator==(const InlineAsmKeyType &X) const {
475     return HasSideEffects == X.HasSideEffects &&
476            IsAlignStack == X.IsAlignStack && AsmDialect == X.AsmDialect &&
477            AsmString == X.AsmString && Constraints == X.Constraints &&
478            FTy == X.FTy && CanThrow == X.CanThrow;
479   }
480 
481   bool operator==(const InlineAsm *Asm) const {
482     return HasSideEffects == Asm->hasSideEffects() &&
483            IsAlignStack == Asm->isAlignStack() &&
484            AsmDialect == Asm->getDialect() &&
485            AsmString == Asm->getAsmString() &&
486            Constraints == Asm->getConstraintString() &&
487            FTy == Asm->getFunctionType() && CanThrow == Asm->canThrow();
488   }
489 
490   unsigned getHash() const {
491     return hash_combine(AsmString, Constraints, HasSideEffects, IsAlignStack,
492                         AsmDialect, FTy, CanThrow);
493   }
494 
495   using TypeClass = ConstantInfo<InlineAsm>::TypeClass;
496 
497   InlineAsm *create(TypeClass *Ty) const {
498     assert(PointerType::getUnqual(FTy) == Ty);
499     return new InlineAsm(FTy, std::string(AsmString), std::string(Constraints),
500                          HasSideEffects, IsAlignStack, AsmDialect, CanThrow);
501   }
502 };
503 
504 struct ConstantExprKeyType {
505 private:
506   uint8_t Opcode;
507   uint8_t SubclassOptionalData;
508   uint16_t SubclassData;
509   ArrayRef<Constant *> Ops;
510   ArrayRef<unsigned> Indexes;
511   ArrayRef<int> ShuffleMask;
512   Type *ExplicitTy;
513 
514   static ArrayRef<int> getShuffleMaskIfValid(const ConstantExpr *CE) {
515     if (CE->getOpcode() == Instruction::ShuffleVector)
516       return CE->getShuffleMask();
517     return None;
518   }
519 
520   static ArrayRef<unsigned> getIndicesIfValid(const ConstantExpr *CE) {
521     if (CE->hasIndices())
522       return CE->getIndices();
523     return None;
524   }
525 
526   static Type *getSourceElementTypeIfValid(const ConstantExpr *CE) {
527     if (auto *GEPCE = dyn_cast<GetElementPtrConstantExpr>(CE))
528       return GEPCE->getSourceElementType();
529     return nullptr;
530   }
531 
532 public:
533   ConstantExprKeyType(unsigned Opcode, ArrayRef<Constant *> Ops,
534                       unsigned short SubclassData = 0,
535                       unsigned short SubclassOptionalData = 0,
536                       ArrayRef<unsigned> Indexes = None,
537                       ArrayRef<int> ShuffleMask = None,
538                       Type *ExplicitTy = nullptr)
539       : Opcode(Opcode), SubclassOptionalData(SubclassOptionalData),
540         SubclassData(SubclassData), Ops(Ops), Indexes(Indexes),
541         ShuffleMask(ShuffleMask), ExplicitTy(ExplicitTy) {}
542 
543   ConstantExprKeyType(ArrayRef<Constant *> Operands, const ConstantExpr *CE)
544       : Opcode(CE->getOpcode()),
545         SubclassOptionalData(CE->getRawSubclassOptionalData()),
546         SubclassData(CE->isCompare() ? CE->getPredicate() : 0), Ops(Operands),
547         Indexes(getIndicesIfValid(CE)), ShuffleMask(getShuffleMaskIfValid(CE)),
548         ExplicitTy(getSourceElementTypeIfValid(CE)) {}
549 
550   ConstantExprKeyType(const ConstantExpr *CE,
551                       SmallVectorImpl<Constant *> &Storage)
552       : Opcode(CE->getOpcode()),
553         SubclassOptionalData(CE->getRawSubclassOptionalData()),
554         SubclassData(CE->isCompare() ? CE->getPredicate() : 0),
555         Indexes(getIndicesIfValid(CE)), ShuffleMask(getShuffleMaskIfValid(CE)),
556         ExplicitTy(getSourceElementTypeIfValid(CE)) {
557     assert(Storage.empty() && "Expected empty storage");
558     for (unsigned I = 0, E = CE->getNumOperands(); I != E; ++I)
559       Storage.push_back(CE->getOperand(I));
560     Ops = Storage;
561   }
562 
563   bool operator==(const ConstantExprKeyType &X) const {
564     return Opcode == X.Opcode && SubclassData == X.SubclassData &&
565            SubclassOptionalData == X.SubclassOptionalData && Ops == X.Ops &&
566            Indexes == X.Indexes && ShuffleMask == X.ShuffleMask &&
567            ExplicitTy == X.ExplicitTy;
568   }
569 
570   bool operator==(const ConstantExpr *CE) const {
571     if (Opcode != CE->getOpcode())
572       return false;
573     if (SubclassOptionalData != CE->getRawSubclassOptionalData())
574       return false;
575     if (Ops.size() != CE->getNumOperands())
576       return false;
577     if (SubclassData != (CE->isCompare() ? CE->getPredicate() : 0))
578       return false;
579     for (unsigned I = 0, E = Ops.size(); I != E; ++I)
580       if (Ops[I] != CE->getOperand(I))
581         return false;
582     if (Indexes != getIndicesIfValid(CE))
583       return false;
584     if (ShuffleMask != getShuffleMaskIfValid(CE))
585       return false;
586     if (ExplicitTy != getSourceElementTypeIfValid(CE))
587       return false;
588     return true;
589   }
590 
591   unsigned getHash() const {
592     return hash_combine(
593         Opcode, SubclassOptionalData, SubclassData,
594         hash_combine_range(Ops.begin(), Ops.end()),
595         hash_combine_range(Indexes.begin(), Indexes.end()),
596         hash_combine_range(ShuffleMask.begin(), ShuffleMask.end()), ExplicitTy);
597   }
598 
599   using TypeClass = ConstantInfo<ConstantExpr>::TypeClass;
600 
601   ConstantExpr *create(TypeClass *Ty) const {
602     switch (Opcode) {
603     default:
604       if (Instruction::isCast(Opcode) ||
605           (Opcode >= Instruction::UnaryOpsBegin &&
606            Opcode < Instruction::UnaryOpsEnd))
607         return new UnaryConstantExpr(Opcode, Ops[0], Ty);
608       if ((Opcode >= Instruction::BinaryOpsBegin &&
609            Opcode < Instruction::BinaryOpsEnd))
610         return new BinaryConstantExpr(Opcode, Ops[0], Ops[1],
611                                       SubclassOptionalData);
612       llvm_unreachable("Invalid ConstantExpr!");
613     case Instruction::Select:
614       return new SelectConstantExpr(Ops[0], Ops[1], Ops[2]);
615     case Instruction::ExtractElement:
616       return new ExtractElementConstantExpr(Ops[0], Ops[1]);
617     case Instruction::InsertElement:
618       return new InsertElementConstantExpr(Ops[0], Ops[1], Ops[2]);
619     case Instruction::ShuffleVector:
620       return new ShuffleVectorConstantExpr(Ops[0], Ops[1], ShuffleMask);
621     case Instruction::InsertValue:
622       return new InsertValueConstantExpr(Ops[0], Ops[1], Indexes, Ty);
623     case Instruction::ExtractValue:
624       return new ExtractValueConstantExpr(Ops[0], Indexes, Ty);
625     case Instruction::GetElementPtr:
626       return GetElementPtrConstantExpr::Create(ExplicitTy, Ops[0], Ops.slice(1),
627                                                Ty, SubclassOptionalData);
628     case Instruction::ICmp:
629       return new CompareConstantExpr(Ty, Instruction::ICmp, SubclassData,
630                                      Ops[0], Ops[1]);
631     case Instruction::FCmp:
632       return new CompareConstantExpr(Ty, Instruction::FCmp, SubclassData,
633                                      Ops[0], Ops[1]);
634     }
635   }
636 };
637 
638 // Free memory for a given constant.  Assumes the constant has already been
639 // removed from all relevant maps.
640 void deleteConstant(Constant *C);
641 
642 template <class ConstantClass> class ConstantUniqueMap {
643 public:
644   using ValType = typename ConstantInfo<ConstantClass>::ValType;
645   using TypeClass = typename ConstantInfo<ConstantClass>::TypeClass;
646   using LookupKey = std::pair<TypeClass *, ValType>;
647 
648   /// Key and hash together, so that we compute the hash only once and reuse it.
649   using LookupKeyHashed = std::pair<unsigned, LookupKey>;
650 
651 private:
652   struct MapInfo {
653     using ConstantClassInfo = DenseMapInfo<ConstantClass *>;
654 
655     static inline ConstantClass *getEmptyKey() {
656       return ConstantClassInfo::getEmptyKey();
657     }
658 
659     static inline ConstantClass *getTombstoneKey() {
660       return ConstantClassInfo::getTombstoneKey();
661     }
662 
663     static unsigned getHashValue(const ConstantClass *CP) {
664       SmallVector<Constant *, 32> Storage;
665       return getHashValue(LookupKey(CP->getType(), ValType(CP, Storage)));
666     }
667 
668     static bool isEqual(const ConstantClass *LHS, const ConstantClass *RHS) {
669       return LHS == RHS;
670     }
671 
672     static unsigned getHashValue(const LookupKey &Val) {
673       return hash_combine(Val.first, Val.second.getHash());
674     }
675 
676     static unsigned getHashValue(const LookupKeyHashed &Val) {
677       return Val.first;
678     }
679 
680     static bool isEqual(const LookupKey &LHS, const ConstantClass *RHS) {
681       if (RHS == getEmptyKey() || RHS == getTombstoneKey())
682         return false;
683       if (LHS.first != RHS->getType())
684         return false;
685       return LHS.second == RHS;
686     }
687 
688     static bool isEqual(const LookupKeyHashed &LHS, const ConstantClass *RHS) {
689       return isEqual(LHS.second, RHS);
690     }
691   };
692 
693 public:
694   using MapTy = DenseSet<ConstantClass *, MapInfo>;
695 
696 private:
697   MapTy Map;
698 
699 public:
700   typename MapTy::iterator begin() { return Map.begin(); }
701   typename MapTy::iterator end() { return Map.end(); }
702 
703   void freeConstants() {
704     for (auto &I : Map)
705       deleteConstant(I);
706   }
707 
708 private:
709   ConstantClass *create(TypeClass *Ty, ValType V, LookupKeyHashed &HashKey) {
710     ConstantClass *Result = V.create(Ty);
711 
712     assert(Result->getType() == Ty && "Type specified is not correct!");
713     Map.insert_as(Result, HashKey);
714 
715     return Result;
716   }
717 
718 public:
719   /// Return the specified constant from the map, creating it if necessary.
720   ConstantClass *getOrCreate(TypeClass *Ty, ValType V) {
721     LookupKey Key(Ty, V);
722     /// Hash once, and reuse it for the lookup and the insertion if needed.
723     LookupKeyHashed Lookup(MapInfo::getHashValue(Key), Key);
724 
725     ConstantClass *Result = nullptr;
726 
727     auto I = Map.find_as(Lookup);
728     if (I == Map.end())
729       Result = create(Ty, V, Lookup);
730     else
731       Result = *I;
732     assert(Result && "Unexpected nullptr");
733 
734     return Result;
735   }
736 
737   /// Remove this constant from the map
738   void remove(ConstantClass *CP) {
739     typename MapTy::iterator I = Map.find(CP);
740     assert(I != Map.end() && "Constant not found in constant table!");
741     assert(*I == CP && "Didn't find correct element?");
742     Map.erase(I);
743   }
744 
745   ConstantClass *replaceOperandsInPlace(ArrayRef<Constant *> Operands,
746                                         ConstantClass *CP, Value *From,
747                                         Constant *To, unsigned NumUpdated = 0,
748                                         unsigned OperandNo = ~0u) {
749     LookupKey Key(CP->getType(), ValType(Operands, CP));
750     /// Hash once, and reuse it for the lookup and the insertion if needed.
751     LookupKeyHashed Lookup(MapInfo::getHashValue(Key), Key);
752 
753     auto ItMap = Map.find_as(Lookup);
754     if (ItMap != Map.end())
755       return *ItMap;
756 
757     // Update to the new value.  Optimize for the case when we have a single
758     // operand that we're changing, but handle bulk updates efficiently.
759     remove(CP);
760     if (NumUpdated == 1) {
761       assert(OperandNo < CP->getNumOperands() && "Invalid index");
762       assert(CP->getOperand(OperandNo) != To && "I didn't contain From!");
763       CP->setOperand(OperandNo, To);
764     } else {
765       for (unsigned I = 0, E = CP->getNumOperands(); I != E; ++I)
766         if (CP->getOperand(I) == From)
767           CP->setOperand(I, To);
768     }
769     Map.insert_as(CP, Lookup);
770     return nullptr;
771   }
772 
773   void dump() const {
774     LLVM_DEBUG(dbgs() << "Constant.cpp: ConstantUniqueMap\n");
775   }
776 };
777 
778 template <> inline void ConstantUniqueMap<InlineAsm>::freeConstants() {
779   for (auto &I : Map)
780     delete I;
781 }
782 
783 } // end namespace llvm
784 
785 #endif // LLVM_LIB_IR_CONSTANTSCONTEXT_H
786