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