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