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