ConstantsContext.h revision dce4a407a24b04eebc6a376f8e62b41aaa7b071f 
1//===-- ConstantsContext.h - Constants-related Context Interals -----------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10//  This file defines various helper methods and classes used by
11// LLVMContextImpl for creating and managing constants.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_CONSTANTSCONTEXT_H
16#define LLVM_CONSTANTSCONTEXT_H
17
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/Hashing.h"
20#include "llvm/IR/InlineAsm.h"
21#include "llvm/IR/Instructions.h"
22#include "llvm/IR/Operator.h"
23#include "llvm/Support/Debug.h"
24#include "llvm/Support/ErrorHandling.h"
25#include "llvm/Support/raw_ostream.h"
26#include <map>
27#include <tuple>
28
29#define DEBUG_TYPE "ir"
30
31namespace llvm {
32template<class ValType>
33struct ConstantTraits;
34
35/// UnaryConstantExpr - This class is private to Constants.cpp, and is used
36/// behind the scenes to implement unary constant exprs.
37class UnaryConstantExpr : public ConstantExpr {
38  void anchor() override;
39  void *operator new(size_t, unsigned) LLVM_DELETED_FUNCTION;
40public:
41  // allocate space for exactly one operand
42  void *operator new(size_t s) {
43    return User::operator new(s, 1);
44  }
45  UnaryConstantExpr(unsigned Opcode, Constant *C, Type *Ty)
46    : ConstantExpr(Ty, Opcode, &Op<0>(), 1) {
47    Op<0>() = C;
48  }
49  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
50};
51
52/// BinaryConstantExpr - This class is private to Constants.cpp, and is used
53/// behind the scenes to implement binary constant exprs.
54class BinaryConstantExpr : public ConstantExpr {
55  void anchor() override;
56  void *operator new(size_t, unsigned) LLVM_DELETED_FUNCTION;
57public:
58  // allocate space for exactly two operands
59  void *operator new(size_t s) {
60    return User::operator new(s, 2);
61  }
62  BinaryConstantExpr(unsigned Opcode, Constant *C1, Constant *C2,
63                     unsigned Flags)
64    : ConstantExpr(C1->getType(), Opcode, &Op<0>(), 2) {
65    Op<0>() = C1;
66    Op<1>() = C2;
67    SubclassOptionalData = Flags;
68  }
69  /// Transparently provide more efficient getOperand methods.
70  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
71};
72
73/// SelectConstantExpr - This class is private to Constants.cpp, and is used
74/// behind the scenes to implement select constant exprs.
75class SelectConstantExpr : public ConstantExpr {
76  void anchor() override;
77  void *operator new(size_t, unsigned) LLVM_DELETED_FUNCTION;
78public:
79  // allocate space for exactly three operands
80  void *operator new(size_t s) {
81    return User::operator new(s, 3);
82  }
83  SelectConstantExpr(Constant *C1, Constant *C2, Constant *C3)
84    : ConstantExpr(C2->getType(), Instruction::Select, &Op<0>(), 3) {
85    Op<0>() = C1;
86    Op<1>() = C2;
87    Op<2>() = C3;
88  }
89  /// Transparently provide more efficient getOperand methods.
90  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
91};
92
93/// ExtractElementConstantExpr - This class is private to
94/// Constants.cpp, and is used behind the scenes to implement
95/// extractelement constant exprs.
96class ExtractElementConstantExpr : public ConstantExpr {
97  void anchor() override;
98  void *operator new(size_t, unsigned) LLVM_DELETED_FUNCTION;
99public:
100  // allocate space for exactly two operands
101  void *operator new(size_t s) {
102    return User::operator new(s, 2);
103  }
104  ExtractElementConstantExpr(Constant *C1, Constant *C2)
105    : ConstantExpr(cast<VectorType>(C1->getType())->getElementType(),
106                   Instruction::ExtractElement, &Op<0>(), 2) {
107    Op<0>() = C1;
108    Op<1>() = C2;
109  }
110  /// Transparently provide more efficient getOperand methods.
111  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
112};
113
114/// InsertElementConstantExpr - This class is private to
115/// Constants.cpp, and is used behind the scenes to implement
116/// insertelement constant exprs.
117class InsertElementConstantExpr : public ConstantExpr {
118  void anchor() override;
119  void *operator new(size_t, unsigned) LLVM_DELETED_FUNCTION;
120public:
121  // allocate space for exactly three operands
122  void *operator new(size_t s) {
123    return User::operator new(s, 3);
124  }
125  InsertElementConstantExpr(Constant *C1, Constant *C2, Constant *C3)
126    : ConstantExpr(C1->getType(), Instruction::InsertElement,
127                   &Op<0>(), 3) {
128    Op<0>() = C1;
129    Op<1>() = C2;
130    Op<2>() = C3;
131  }
132  /// Transparently provide more efficient getOperand methods.
133  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
134};
135
136/// ShuffleVectorConstantExpr - This class is private to
137/// Constants.cpp, and is used behind the scenes to implement
138/// shufflevector constant exprs.
139class ShuffleVectorConstantExpr : public ConstantExpr {
140  void anchor() override;
141  void *operator new(size_t, unsigned) LLVM_DELETED_FUNCTION;
142public:
143  // allocate space for exactly three operands
144  void *operator new(size_t s) {
145    return User::operator new(s, 3);
146  }
147  ShuffleVectorConstantExpr(Constant *C1, Constant *C2, Constant *C3)
148  : ConstantExpr(VectorType::get(
149                   cast<VectorType>(C1->getType())->getElementType(),
150                   cast<VectorType>(C3->getType())->getNumElements()),
151                 Instruction::ShuffleVector,
152                 &Op<0>(), 3) {
153    Op<0>() = C1;
154    Op<1>() = C2;
155    Op<2>() = C3;
156  }
157  /// Transparently provide more efficient getOperand methods.
158  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
159};
160
161/// ExtractValueConstantExpr - This class is private to
162/// Constants.cpp, and is used behind the scenes to implement
163/// extractvalue constant exprs.
164class ExtractValueConstantExpr : public ConstantExpr {
165  void anchor() override;
166  void *operator new(size_t, unsigned) LLVM_DELETED_FUNCTION;
167public:
168  // allocate space for exactly one operand
169  void *operator new(size_t s) {
170    return User::operator new(s, 1);
171  }
172  ExtractValueConstantExpr(Constant *Agg,
173                           const SmallVector<unsigned, 4> &IdxList,
174                           Type *DestTy)
175    : ConstantExpr(DestTy, Instruction::ExtractValue, &Op<0>(), 1),
176      Indices(IdxList) {
177    Op<0>() = Agg;
178  }
179
180  /// Indices - These identify which value to extract.
181  const SmallVector<unsigned, 4> Indices;
182
183  /// Transparently provide more efficient getOperand methods.
184  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
185};
186
187/// InsertValueConstantExpr - This class is private to
188/// Constants.cpp, and is used behind the scenes to implement
189/// insertvalue constant exprs.
190class InsertValueConstantExpr : public ConstantExpr {
191  void anchor() override;
192  void *operator new(size_t, unsigned) LLVM_DELETED_FUNCTION;
193public:
194  // allocate space for exactly one operand
195  void *operator new(size_t s) {
196    return User::operator new(s, 2);
197  }
198  InsertValueConstantExpr(Constant *Agg, Constant *Val,
199                          const SmallVector<unsigned, 4> &IdxList,
200                          Type *DestTy)
201    : ConstantExpr(DestTy, Instruction::InsertValue, &Op<0>(), 2),
202      Indices(IdxList) {
203    Op<0>() = Agg;
204    Op<1>() = Val;
205  }
206
207  /// Indices - These identify the position for the insertion.
208  const SmallVector<unsigned, 4> Indices;
209
210  /// Transparently provide more efficient getOperand methods.
211  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
212};
213
214
215/// GetElementPtrConstantExpr - This class is private to Constants.cpp, and is
216/// used behind the scenes to implement getelementpr constant exprs.
217class GetElementPtrConstantExpr : public ConstantExpr {
218  void anchor() override;
219  GetElementPtrConstantExpr(Constant *C, ArrayRef<Constant*> IdxList,
220                            Type *DestTy);
221public:
222  static GetElementPtrConstantExpr *Create(Constant *C,
223                                           ArrayRef<Constant*> IdxList,
224                                           Type *DestTy,
225                                           unsigned Flags) {
226    GetElementPtrConstantExpr *Result =
227      new(IdxList.size() + 1) GetElementPtrConstantExpr(C, IdxList, DestTy);
228    Result->SubclassOptionalData = Flags;
229    return Result;
230  }
231  /// Transparently provide more efficient getOperand methods.
232  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
233};
234
235// CompareConstantExpr - This class is private to Constants.cpp, and is used
236// behind the scenes to implement ICmp and FCmp constant expressions. This is
237// needed in order to store the predicate value for these instructions.
238class CompareConstantExpr : public ConstantExpr {
239  void anchor() override;
240  void *operator new(size_t, unsigned) LLVM_DELETED_FUNCTION;
241public:
242  // allocate space for exactly two operands
243  void *operator new(size_t s) {
244    return User::operator new(s, 2);
245  }
246  unsigned short predicate;
247  CompareConstantExpr(Type *ty, Instruction::OtherOps opc,
248                      unsigned short pred,  Constant* LHS, Constant* RHS)
249    : ConstantExpr(ty, opc, &Op<0>(), 2), predicate(pred) {
250    Op<0>() = LHS;
251    Op<1>() = RHS;
252  }
253  /// Transparently provide more efficient getOperand methods.
254  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
255};
256
257template <>
258struct OperandTraits<UnaryConstantExpr> :
259  public FixedNumOperandTraits<UnaryConstantExpr, 1> {
260};
261DEFINE_TRANSPARENT_OPERAND_ACCESSORS(UnaryConstantExpr, Value)
262
263template <>
264struct OperandTraits<BinaryConstantExpr> :
265  public FixedNumOperandTraits<BinaryConstantExpr, 2> {
266};
267DEFINE_TRANSPARENT_OPERAND_ACCESSORS(BinaryConstantExpr, Value)
268
269template <>
270struct OperandTraits<SelectConstantExpr> :
271  public FixedNumOperandTraits<SelectConstantExpr, 3> {
272};
273DEFINE_TRANSPARENT_OPERAND_ACCESSORS(SelectConstantExpr, Value)
274
275template <>
276struct OperandTraits<ExtractElementConstantExpr> :
277  public FixedNumOperandTraits<ExtractElementConstantExpr, 2> {
278};
279DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ExtractElementConstantExpr, Value)
280
281template <>
282struct OperandTraits<InsertElementConstantExpr> :
283  public FixedNumOperandTraits<InsertElementConstantExpr, 3> {
284};
285DEFINE_TRANSPARENT_OPERAND_ACCESSORS(InsertElementConstantExpr, Value)
286
287template <>
288struct OperandTraits<ShuffleVectorConstantExpr> :
289    public FixedNumOperandTraits<ShuffleVectorConstantExpr, 3> {
290};
291DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ShuffleVectorConstantExpr, Value)
292
293template <>
294struct OperandTraits<ExtractValueConstantExpr> :
295  public FixedNumOperandTraits<ExtractValueConstantExpr, 1> {
296};
297DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ExtractValueConstantExpr, Value)
298
299template <>
300struct OperandTraits<InsertValueConstantExpr> :
301  public FixedNumOperandTraits<InsertValueConstantExpr, 2> {
302};
303DEFINE_TRANSPARENT_OPERAND_ACCESSORS(InsertValueConstantExpr, Value)
304
305template <>
306struct OperandTraits<GetElementPtrConstantExpr> :
307  public VariadicOperandTraits<GetElementPtrConstantExpr, 1> {
308};
309
310DEFINE_TRANSPARENT_OPERAND_ACCESSORS(GetElementPtrConstantExpr, Value)
311
312
313template <>
314struct OperandTraits<CompareConstantExpr> :
315  public FixedNumOperandTraits<CompareConstantExpr, 2> {
316};
317DEFINE_TRANSPARENT_OPERAND_ACCESSORS(CompareConstantExpr, Value)
318
319struct ExprMapKeyType {
320  ExprMapKeyType(unsigned opc,
321      ArrayRef<Constant*> ops,
322      unsigned short flags = 0,
323      unsigned short optionalflags = 0,
324      ArrayRef<unsigned> inds = None)
325        : opcode(opc), subclassoptionaldata(optionalflags), subclassdata(flags),
326        operands(ops.begin(), ops.end()), indices(inds.begin(), inds.end()) {}
327  uint8_t opcode;
328  uint8_t subclassoptionaldata;
329  uint16_t subclassdata;
330  std::vector<Constant*> operands;
331  SmallVector<unsigned, 4> indices;
332  bool operator==(const ExprMapKeyType& that) const {
333    return this->opcode == that.opcode &&
334           this->subclassdata == that.subclassdata &&
335           this->subclassoptionaldata == that.subclassoptionaldata &&
336           this->operands == that.operands &&
337           this->indices == that.indices;
338  }
339  bool operator<(const ExprMapKeyType & that) const {
340    return std::tie(opcode, operands, subclassdata, subclassoptionaldata,
341                    indices) <
342           std::tie(that.opcode, that.operands, that.subclassdata,
343                    that.subclassoptionaldata, that.indices);
344  }
345
346  bool operator!=(const ExprMapKeyType& that) const {
347    return !(*this == that);
348  }
349};
350
351struct InlineAsmKeyType {
352  InlineAsmKeyType(StringRef AsmString,
353                   StringRef Constraints, bool hasSideEffects,
354                   bool isAlignStack, InlineAsm::AsmDialect asmDialect)
355    : asm_string(AsmString), constraints(Constraints),
356      has_side_effects(hasSideEffects), is_align_stack(isAlignStack),
357      asm_dialect(asmDialect) {}
358  std::string asm_string;
359  std::string constraints;
360  bool has_side_effects;
361  bool is_align_stack;
362  InlineAsm::AsmDialect asm_dialect;
363  bool operator==(const InlineAsmKeyType& that) const {
364    return this->asm_string == that.asm_string &&
365           this->constraints == that.constraints &&
366           this->has_side_effects == that.has_side_effects &&
367           this->is_align_stack == that.is_align_stack &&
368           this->asm_dialect == that.asm_dialect;
369  }
370  bool operator<(const InlineAsmKeyType& that) const {
371    return std::tie(asm_string, constraints, has_side_effects, is_align_stack,
372                    asm_dialect) <
373           std::tie(that.asm_string, that.constraints, that.has_side_effects,
374                    that.is_align_stack, that.asm_dialect);
375  }
376
377  bool operator!=(const InlineAsmKeyType& that) const {
378    return !(*this == that);
379  }
380};
381
382// The number of operands for each ConstantCreator::create method is
383// determined by the ConstantTraits template.
384// ConstantCreator - A class that is used to create constants by
385// ConstantUniqueMap*.  This class should be partially specialized if there is
386// something strange that needs to be done to interface to the ctor for the
387// constant.
388//
389template<typename T, typename Alloc>
390struct ConstantTraits< std::vector<T, Alloc> > {
391  static unsigned uses(const std::vector<T, Alloc>& v) {
392    return v.size();
393  }
394};
395
396template<>
397struct ConstantTraits<Constant *> {
398  static unsigned uses(Constant * const & v) {
399    return 1;
400  }
401};
402
403template<class ConstantClass, class TypeClass, class ValType>
404struct ConstantCreator {
405  static ConstantClass *create(TypeClass *Ty, const ValType &V) {
406    return new(ConstantTraits<ValType>::uses(V)) ConstantClass(Ty, V);
407  }
408};
409
410template<class ConstantClass, class TypeClass>
411struct ConstantArrayCreator {
412  static ConstantClass *create(TypeClass *Ty, ArrayRef<Constant*> V) {
413    return new(V.size()) ConstantClass(Ty, V);
414  }
415};
416
417template<class ConstantClass>
418struct ConstantKeyData {
419  typedef void ValType;
420  static ValType getValType(ConstantClass *C) {
421    llvm_unreachable("Unknown Constant type!");
422  }
423};
424
425template<>
426struct ConstantCreator<ConstantExpr, Type, ExprMapKeyType> {
427  static ConstantExpr *create(Type *Ty, const ExprMapKeyType &V,
428      unsigned short pred = 0) {
429    if (Instruction::isCast(V.opcode))
430      return new UnaryConstantExpr(V.opcode, V.operands[0], Ty);
431    if ((V.opcode >= Instruction::BinaryOpsBegin &&
432         V.opcode < Instruction::BinaryOpsEnd))
433      return new BinaryConstantExpr(V.opcode, V.operands[0], V.operands[1],
434                                    V.subclassoptionaldata);
435    if (V.opcode == Instruction::Select)
436      return new SelectConstantExpr(V.operands[0], V.operands[1],
437                                    V.operands[2]);
438    if (V.opcode == Instruction::ExtractElement)
439      return new ExtractElementConstantExpr(V.operands[0], V.operands[1]);
440    if (V.opcode == Instruction::InsertElement)
441      return new InsertElementConstantExpr(V.operands[0], V.operands[1],
442                                           V.operands[2]);
443    if (V.opcode == Instruction::ShuffleVector)
444      return new ShuffleVectorConstantExpr(V.operands[0], V.operands[1],
445                                           V.operands[2]);
446    if (V.opcode == Instruction::InsertValue)
447      return new InsertValueConstantExpr(V.operands[0], V.operands[1],
448                                         V.indices, Ty);
449    if (V.opcode == Instruction::ExtractValue)
450      return new ExtractValueConstantExpr(V.operands[0], V.indices, Ty);
451    if (V.opcode == Instruction::GetElementPtr) {
452      std::vector<Constant*> IdxList(V.operands.begin()+1, V.operands.end());
453      return GetElementPtrConstantExpr::Create(V.operands[0], IdxList, Ty,
454                                               V.subclassoptionaldata);
455    }
456
457    // The compare instructions are weird. We have to encode the predicate
458    // value and it is combined with the instruction opcode by multiplying
459    // the opcode by one hundred. We must decode this to get the predicate.
460    if (V.opcode == Instruction::ICmp)
461      return new CompareConstantExpr(Ty, Instruction::ICmp, V.subclassdata,
462                                     V.operands[0], V.operands[1]);
463    if (V.opcode == Instruction::FCmp)
464      return new CompareConstantExpr(Ty, Instruction::FCmp, V.subclassdata,
465                                     V.operands[0], V.operands[1]);
466    llvm_unreachable("Invalid ConstantExpr!");
467  }
468};
469
470template<>
471struct ConstantKeyData<ConstantExpr> {
472  typedef ExprMapKeyType ValType;
473  static ValType getValType(ConstantExpr *CE) {
474    std::vector<Constant*> Operands;
475    Operands.reserve(CE->getNumOperands());
476    for (unsigned i = 0, e = CE->getNumOperands(); i != e; ++i)
477      Operands.push_back(cast<Constant>(CE->getOperand(i)));
478    return ExprMapKeyType(CE->getOpcode(), Operands,
479        CE->isCompare() ? CE->getPredicate() : 0,
480        CE->getRawSubclassOptionalData(),
481        CE->hasIndices() ?
482          CE->getIndices() : ArrayRef<unsigned>());
483  }
484};
485
486template<>
487struct ConstantCreator<InlineAsm, PointerType, InlineAsmKeyType> {
488  static InlineAsm *create(PointerType *Ty, const InlineAsmKeyType &Key) {
489    return new InlineAsm(Ty, Key.asm_string, Key.constraints,
490                         Key.has_side_effects, Key.is_align_stack,
491                         Key.asm_dialect);
492  }
493};
494
495template<>
496struct ConstantKeyData<InlineAsm> {
497  typedef InlineAsmKeyType ValType;
498  static ValType getValType(InlineAsm *Asm) {
499    return InlineAsmKeyType(Asm->getAsmString(), Asm->getConstraintString(),
500                            Asm->hasSideEffects(), Asm->isAlignStack(),
501                            Asm->getDialect());
502  }
503};
504
505template<class ValType, class ValRefType, class TypeClass, class ConstantClass,
506         bool HasLargeKey = false /*true for arrays and structs*/ >
507class ConstantUniqueMap {
508public:
509  typedef std::pair<TypeClass*, ValType> MapKey;
510  typedef std::map<MapKey, ConstantClass *> MapTy;
511  typedef std::map<ConstantClass *, typename MapTy::iterator> InverseMapTy;
512private:
513  /// Map - This is the main map from the element descriptor to the Constants.
514  /// This is the primary way we avoid creating two of the same shape
515  /// constant.
516  MapTy Map;
517
518  /// InverseMap - If "HasLargeKey" is true, this contains an inverse mapping
519  /// from the constants to their element in Map.  This is important for
520  /// removal of constants from the array, which would otherwise have to scan
521  /// through the map with very large keys.
522  InverseMapTy InverseMap;
523
524public:
525  typename MapTy::iterator map_begin() { return Map.begin(); }
526  typename MapTy::iterator map_end() { return Map.end(); }
527
528  void freeConstants() {
529    for (typename MapTy::iterator I=Map.begin(), E=Map.end();
530         I != E; ++I) {
531      // Asserts that use_empty().
532      delete I->second;
533    }
534  }
535
536  /// InsertOrGetItem - Return an iterator for the specified element.
537  /// If the element exists in the map, the returned iterator points to the
538  /// entry and Exists=true.  If not, the iterator points to the newly
539  /// inserted entry and returns Exists=false.  Newly inserted entries have
540  /// I->second == 0, and should be filled in.
541  typename MapTy::iterator InsertOrGetItem(std::pair<MapKey, ConstantClass *>
542                                 &InsertVal,
543                                 bool &Exists) {
544    std::pair<typename MapTy::iterator, bool> IP = Map.insert(InsertVal);
545    Exists = !IP.second;
546    return IP.first;
547  }
548
549private:
550  typename MapTy::iterator FindExistingElement(ConstantClass *CP) {
551    if (HasLargeKey) {
552      typename InverseMapTy::iterator IMI = InverseMap.find(CP);
553      assert(IMI != InverseMap.end() && IMI->second != Map.end() &&
554             IMI->second->second == CP &&
555             "InverseMap corrupt!");
556      return IMI->second;
557    }
558
559    typename MapTy::iterator I =
560      Map.find(MapKey(static_cast<TypeClass*>(CP->getType()),
561                      ConstantKeyData<ConstantClass>::getValType(CP)));
562    if (I == Map.end() || I->second != CP) {
563      // FIXME: This should not use a linear scan.  If this gets to be a
564      // performance problem, someone should look at this.
565      for (I = Map.begin(); I != Map.end() && I->second != CP; ++I)
566        /* empty */;
567    }
568    return I;
569  }
570
571  ConstantClass *Create(TypeClass *Ty, ValRefType V,
572                        typename MapTy::iterator I) {
573    ConstantClass* Result =
574      ConstantCreator<ConstantClass,TypeClass,ValType>::create(Ty, V);
575
576    assert(Result->getType() == Ty && "Type specified is not correct!");
577    I = Map.insert(I, std::make_pair(MapKey(Ty, V), Result));
578
579    if (HasLargeKey)  // Remember the reverse mapping if needed.
580      InverseMap.insert(std::make_pair(Result, I));
581
582    return Result;
583  }
584public:
585
586  /// getOrCreate - Return the specified constant from the map, creating it if
587  /// necessary.
588  ConstantClass *getOrCreate(TypeClass *Ty, ValRefType V) {
589    MapKey Lookup(Ty, V);
590    ConstantClass* Result = nullptr;
591
592    typename MapTy::iterator I = Map.find(Lookup);
593    // Is it in the map?
594    if (I != Map.end())
595      Result = I->second;
596
597    if (!Result) {
598      // If no preexisting value, create one now...
599      Result = Create(Ty, V, I);
600    }
601
602    return Result;
603  }
604
605  void remove(ConstantClass *CP) {
606    typename MapTy::iterator I = FindExistingElement(CP);
607    assert(I != Map.end() && "Constant not found in constant table!");
608    assert(I->second == CP && "Didn't find correct element?");
609
610    if (HasLargeKey)  // Remember the reverse mapping if needed.
611      InverseMap.erase(CP);
612
613    Map.erase(I);
614  }
615
616  /// MoveConstantToNewSlot - If we are about to change C to be the element
617  /// specified by I, update our internal data structures to reflect this
618  /// fact.
619  void MoveConstantToNewSlot(ConstantClass *C, typename MapTy::iterator I) {
620    // First, remove the old location of the specified constant in the map.
621    typename MapTy::iterator OldI = FindExistingElement(C);
622    assert(OldI != Map.end() && "Constant not found in constant table!");
623    assert(OldI->second == C && "Didn't find correct element?");
624
625     // Remove the old entry from the map.
626    Map.erase(OldI);
627
628    // Update the inverse map so that we know that this constant is now
629    // located at descriptor I.
630    if (HasLargeKey) {
631      assert(I->second == C && "Bad inversemap entry!");
632      InverseMap[C] = I;
633    }
634  }
635
636  void dump() const {
637    DEBUG(dbgs() << "Constant.cpp: ConstantUniqueMap\n");
638  }
639};
640
641// Unique map for aggregate constants
642template<class TypeClass, class ConstantClass>
643class ConstantAggrUniqueMap {
644public:
645  typedef ArrayRef<Constant*> Operands;
646  typedef std::pair<TypeClass*, Operands> LookupKey;
647private:
648  struct MapInfo {
649    typedef DenseMapInfo<ConstantClass*> ConstantClassInfo;
650    typedef DenseMapInfo<Constant*> ConstantInfo;
651    typedef DenseMapInfo<TypeClass*> TypeClassInfo;
652    static inline ConstantClass* getEmptyKey() {
653      return ConstantClassInfo::getEmptyKey();
654    }
655    static inline ConstantClass* getTombstoneKey() {
656      return ConstantClassInfo::getTombstoneKey();
657    }
658    static unsigned getHashValue(const ConstantClass *CP) {
659      SmallVector<Constant*, 8> CPOperands;
660      CPOperands.reserve(CP->getNumOperands());
661      for (unsigned I = 0, E = CP->getNumOperands(); I < E; ++I)
662        CPOperands.push_back(CP->getOperand(I));
663      return getHashValue(LookupKey(CP->getType(), CPOperands));
664    }
665    static bool isEqual(const ConstantClass *LHS, const ConstantClass *RHS) {
666      return LHS == RHS;
667    }
668    static unsigned getHashValue(const LookupKey &Val) {
669      return hash_combine(Val.first, hash_combine_range(Val.second.begin(),
670                                                        Val.second.end()));
671    }
672    static bool isEqual(const LookupKey &LHS, const ConstantClass *RHS) {
673      if (RHS == getEmptyKey() || RHS == getTombstoneKey())
674        return false;
675      if (LHS.first != RHS->getType()
676          || LHS.second.size() != RHS->getNumOperands())
677        return false;
678      for (unsigned I = 0, E = RHS->getNumOperands(); I < E; ++I) {
679        if (LHS.second[I] != RHS->getOperand(I))
680          return false;
681      }
682      return true;
683    }
684  };
685public:
686  typedef DenseMap<ConstantClass *, char, MapInfo> MapTy;
687
688private:
689  /// Map - This is the main map from the element descriptor to the Constants.
690  /// This is the primary way we avoid creating two of the same shape
691  /// constant.
692  MapTy Map;
693
694public:
695  typename MapTy::iterator map_begin() { return Map.begin(); }
696  typename MapTy::iterator map_end() { return Map.end(); }
697
698  void freeConstants() {
699    for (typename MapTy::iterator I=Map.begin(), E=Map.end();
700         I != E; ++I) {
701      // Asserts that use_empty().
702      delete I->first;
703    }
704  }
705
706private:
707  typename MapTy::iterator findExistingElement(ConstantClass *CP) {
708    return Map.find(CP);
709  }
710
711  ConstantClass *Create(TypeClass *Ty, Operands V, typename MapTy::iterator I) {
712    ConstantClass* Result =
713      ConstantArrayCreator<ConstantClass,TypeClass>::create(Ty, V);
714
715    assert(Result->getType() == Ty && "Type specified is not correct!");
716    Map[Result] = '\0';
717
718    return Result;
719  }
720public:
721
722  /// getOrCreate - Return the specified constant from the map, creating it if
723  /// necessary.
724  ConstantClass *getOrCreate(TypeClass *Ty, Operands V) {
725    LookupKey Lookup(Ty, V);
726    ConstantClass* Result = nullptr;
727
728    typename MapTy::iterator I = Map.find_as(Lookup);
729    // Is it in the map?
730    if (I != Map.end())
731      Result = I->first;
732
733    if (!Result) {
734      // If no preexisting value, create one now...
735      Result = Create(Ty, V, I);
736    }
737
738    return Result;
739  }
740
741  /// Find the constant by lookup key.
742  typename MapTy::iterator find(LookupKey Lookup) {
743    return Map.find_as(Lookup);
744  }
745
746  /// Insert the constant into its proper slot.
747  void insert(ConstantClass *CP) {
748    Map[CP] = '\0';
749  }
750
751  /// Remove this constant from the map
752  void remove(ConstantClass *CP) {
753    typename MapTy::iterator I = findExistingElement(CP);
754    assert(I != Map.end() && "Constant not found in constant table!");
755    assert(I->first == CP && "Didn't find correct element?");
756    Map.erase(I);
757  }
758
759  void dump() const {
760    DEBUG(dbgs() << "Constant.cpp: ConstantUniqueMap\n");
761  }
762};
763
764}
765
766#endif
767