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
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) LLVM_DELETED_FUNCTION;
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) LLVM_DELETED_FUNCTION;
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) LLVM_DELETED_FUNCTION;
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) LLVM_DELETED_FUNCTION;
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) LLVM_DELETED_FUNCTION;
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) LLVM_DELETED_FUNCTION;
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) LLVM_DELETED_FUNCTION;
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) LLVM_DELETED_FUNCTION;
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) LLVM_DELETED_FUNCTION;
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 = None)
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, InlineAsm::AsmDialect asmDialect)
356    : asm_string(AsmString), constraints(Constraints),
357      has_side_effects(hasSideEffects), is_align_stack(isAlignStack),
358      asm_dialect(asmDialect) {}
359  std::string asm_string;
360  std::string constraints;
361  bool has_side_effects;
362  bool is_align_stack;
363  InlineAsm::AsmDialect asm_dialect;
364  bool operator==(const InlineAsmKeyType& that) const {
365    return this->asm_string == that.asm_string &&
366           this->constraints == that.constraints &&
367           this->has_side_effects == that.has_side_effects &&
368           this->is_align_stack == that.is_align_stack &&
369           this->asm_dialect == that.asm_dialect;
370  }
371  bool operator<(const InlineAsmKeyType& that) const {
372    if (this->asm_string != that.asm_string)
373      return this->asm_string < that.asm_string;
374    if (this->constraints != that.constraints)
375      return this->constraints < that.constraints;
376    if (this->has_side_effects != that.has_side_effects)
377      return this->has_side_effects < that.has_side_effects;
378    if (this->is_align_stack != that.is_align_stack)
379      return this->is_align_stack < that.is_align_stack;
380    if (this->asm_dialect != that.asm_dialect)
381      return this->asm_dialect < that.asm_dialect;
382    return false;
383  }
384
385  bool operator!=(const InlineAsmKeyType& that) const {
386    return !(*this == that);
387  }
388};
389
390// The number of operands for each ConstantCreator::create method is
391// determined by the ConstantTraits template.
392// ConstantCreator - A class that is used to create constants by
393// ConstantUniqueMap*.  This class should be partially specialized if there is
394// something strange that needs to be done to interface to the ctor for the
395// constant.
396//
397template<typename T, typename Alloc>
398struct ConstantTraits< std::vector<T, Alloc> > {
399  static unsigned uses(const std::vector<T, Alloc>& v) {
400    return v.size();
401  }
402};
403
404template<>
405struct ConstantTraits<Constant *> {
406  static unsigned uses(Constant * const & v) {
407    return 1;
408  }
409};
410
411template<class ConstantClass, class TypeClass, class ValType>
412struct ConstantCreator {
413  static ConstantClass *create(TypeClass *Ty, const ValType &V) {
414    return new(ConstantTraits<ValType>::uses(V)) ConstantClass(Ty, V);
415  }
416};
417
418template<class ConstantClass, class TypeClass>
419struct ConstantArrayCreator {
420  static ConstantClass *create(TypeClass *Ty, ArrayRef<Constant*> V) {
421    return new(V.size()) ConstantClass(Ty, V);
422  }
423};
424
425template<class ConstantClass>
426struct ConstantKeyData {
427  typedef void ValType;
428  static ValType getValType(ConstantClass *C) {
429    llvm_unreachable("Unknown Constant type!");
430  }
431};
432
433template<>
434struct ConstantCreator<ConstantExpr, Type, ExprMapKeyType> {
435  static ConstantExpr *create(Type *Ty, const ExprMapKeyType &V,
436      unsigned short pred = 0) {
437    if (Instruction::isCast(V.opcode))
438      return new UnaryConstantExpr(V.opcode, V.operands[0], Ty);
439    if ((V.opcode >= Instruction::BinaryOpsBegin &&
440         V.opcode < Instruction::BinaryOpsEnd))
441      return new BinaryConstantExpr(V.opcode, V.operands[0], V.operands[1],
442                                    V.subclassoptionaldata);
443    if (V.opcode == Instruction::Select)
444      return new SelectConstantExpr(V.operands[0], V.operands[1],
445                                    V.operands[2]);
446    if (V.opcode == Instruction::ExtractElement)
447      return new ExtractElementConstantExpr(V.operands[0], V.operands[1]);
448    if (V.opcode == Instruction::InsertElement)
449      return new InsertElementConstantExpr(V.operands[0], V.operands[1],
450                                           V.operands[2]);
451    if (V.opcode == Instruction::ShuffleVector)
452      return new ShuffleVectorConstantExpr(V.operands[0], V.operands[1],
453                                           V.operands[2]);
454    if (V.opcode == Instruction::InsertValue)
455      return new InsertValueConstantExpr(V.operands[0], V.operands[1],
456                                         V.indices, Ty);
457    if (V.opcode == Instruction::ExtractValue)
458      return new ExtractValueConstantExpr(V.operands[0], V.indices, Ty);
459    if (V.opcode == Instruction::GetElementPtr) {
460      std::vector<Constant*> IdxList(V.operands.begin()+1, V.operands.end());
461      return GetElementPtrConstantExpr::Create(V.operands[0], IdxList, Ty,
462                                               V.subclassoptionaldata);
463    }
464
465    // The compare instructions are weird. We have to encode the predicate
466    // value and it is combined with the instruction opcode by multiplying
467    // the opcode by one hundred. We must decode this to get the predicate.
468    if (V.opcode == Instruction::ICmp)
469      return new CompareConstantExpr(Ty, Instruction::ICmp, V.subclassdata,
470                                     V.operands[0], V.operands[1]);
471    if (V.opcode == Instruction::FCmp)
472      return new CompareConstantExpr(Ty, Instruction::FCmp, V.subclassdata,
473                                     V.operands[0], V.operands[1]);
474    llvm_unreachable("Invalid ConstantExpr!");
475  }
476};
477
478template<>
479struct ConstantKeyData<ConstantExpr> {
480  typedef ExprMapKeyType ValType;
481  static ValType getValType(ConstantExpr *CE) {
482    std::vector<Constant*> Operands;
483    Operands.reserve(CE->getNumOperands());
484    for (unsigned i = 0, e = CE->getNumOperands(); i != e; ++i)
485      Operands.push_back(cast<Constant>(CE->getOperand(i)));
486    return ExprMapKeyType(CE->getOpcode(), Operands,
487        CE->isCompare() ? CE->getPredicate() : 0,
488        CE->getRawSubclassOptionalData(),
489        CE->hasIndices() ?
490          CE->getIndices() : ArrayRef<unsigned>());
491  }
492};
493
494template<>
495struct ConstantCreator<InlineAsm, PointerType, InlineAsmKeyType> {
496  static InlineAsm *create(PointerType *Ty, const InlineAsmKeyType &Key) {
497    return new InlineAsm(Ty, Key.asm_string, Key.constraints,
498                         Key.has_side_effects, Key.is_align_stack,
499                         Key.asm_dialect);
500  }
501};
502
503template<>
504struct ConstantKeyData<InlineAsm> {
505  typedef InlineAsmKeyType ValType;
506  static ValType getValType(InlineAsm *Asm) {
507    return InlineAsmKeyType(Asm->getAsmString(), Asm->getConstraintString(),
508                            Asm->hasSideEffects(), Asm->isAlignStack(),
509                            Asm->getDialect());
510  }
511};
512
513template<class ValType, class ValRefType, class TypeClass, class ConstantClass,
514         bool HasLargeKey = false /*true for arrays and structs*/ >
515class ConstantUniqueMap {
516public:
517  typedef std::pair<TypeClass*, ValType> MapKey;
518  typedef std::map<MapKey, ConstantClass *> MapTy;
519  typedef std::map<ConstantClass *, typename MapTy::iterator> InverseMapTy;
520private:
521  /// Map - This is the main map from the element descriptor to the Constants.
522  /// This is the primary way we avoid creating two of the same shape
523  /// constant.
524  MapTy Map;
525
526  /// InverseMap - If "HasLargeKey" is true, this contains an inverse mapping
527  /// from the constants to their element in Map.  This is important for
528  /// removal of constants from the array, which would otherwise have to scan
529  /// through the map with very large keys.
530  InverseMapTy InverseMap;
531
532public:
533  typename MapTy::iterator map_begin() { return Map.begin(); }
534  typename MapTy::iterator map_end() { return Map.end(); }
535
536  void freeConstants() {
537    for (typename MapTy::iterator I=Map.begin(), E=Map.end();
538         I != E; ++I) {
539      // Asserts that use_empty().
540      delete I->second;
541    }
542  }
543
544  /// InsertOrGetItem - Return an iterator for the specified element.
545  /// If the element exists in the map, the returned iterator points to the
546  /// entry and Exists=true.  If not, the iterator points to the newly
547  /// inserted entry and returns Exists=false.  Newly inserted entries have
548  /// I->second == 0, and should be filled in.
549  typename MapTy::iterator InsertOrGetItem(std::pair<MapKey, ConstantClass *>
550                                 &InsertVal,
551                                 bool &Exists) {
552    std::pair<typename MapTy::iterator, bool> IP = Map.insert(InsertVal);
553    Exists = !IP.second;
554    return IP.first;
555  }
556
557private:
558  typename MapTy::iterator FindExistingElement(ConstantClass *CP) {
559    if (HasLargeKey) {
560      typename InverseMapTy::iterator IMI = InverseMap.find(CP);
561      assert(IMI != InverseMap.end() && IMI->second != Map.end() &&
562             IMI->second->second == CP &&
563             "InverseMap corrupt!");
564      return IMI->second;
565    }
566
567    typename MapTy::iterator I =
568      Map.find(MapKey(static_cast<TypeClass*>(CP->getType()),
569                      ConstantKeyData<ConstantClass>::getValType(CP)));
570    if (I == Map.end() || I->second != CP) {
571      // FIXME: This should not use a linear scan.  If this gets to be a
572      // performance problem, someone should look at this.
573      for (I = Map.begin(); I != Map.end() && I->second != CP; ++I)
574        /* empty */;
575    }
576    return I;
577  }
578
579  ConstantClass *Create(TypeClass *Ty, ValRefType V,
580                        typename MapTy::iterator I) {
581    ConstantClass* Result =
582      ConstantCreator<ConstantClass,TypeClass,ValType>::create(Ty, V);
583
584    assert(Result->getType() == Ty && "Type specified is not correct!");
585    I = Map.insert(I, std::make_pair(MapKey(Ty, V), Result));
586
587    if (HasLargeKey)  // Remember the reverse mapping if needed.
588      InverseMap.insert(std::make_pair(Result, I));
589
590    return Result;
591  }
592public:
593
594  /// getOrCreate - Return the specified constant from the map, creating it if
595  /// necessary.
596  ConstantClass *getOrCreate(TypeClass *Ty, ValRefType V) {
597    MapKey Lookup(Ty, V);
598    ConstantClass* Result = 0;
599
600    typename MapTy::iterator I = Map.find(Lookup);
601    // Is it in the map?
602    if (I != Map.end())
603      Result = I->second;
604
605    if (!Result) {
606      // If no preexisting value, create one now...
607      Result = Create(Ty, V, I);
608    }
609
610    return Result;
611  }
612
613  void remove(ConstantClass *CP) {
614    typename MapTy::iterator I = FindExistingElement(CP);
615    assert(I != Map.end() && "Constant not found in constant table!");
616    assert(I->second == CP && "Didn't find correct element?");
617
618    if (HasLargeKey)  // Remember the reverse mapping if needed.
619      InverseMap.erase(CP);
620
621    Map.erase(I);
622  }
623
624  /// MoveConstantToNewSlot - If we are about to change C to be the element
625  /// specified by I, update our internal data structures to reflect this
626  /// fact.
627  void MoveConstantToNewSlot(ConstantClass *C, typename MapTy::iterator I) {
628    // First, remove the old location of the specified constant in the map.
629    typename MapTy::iterator OldI = FindExistingElement(C);
630    assert(OldI != Map.end() && "Constant not found in constant table!");
631    assert(OldI->second == C && "Didn't find correct element?");
632
633     // Remove the old entry from the map.
634    Map.erase(OldI);
635
636    // Update the inverse map so that we know that this constant is now
637    // located at descriptor I.
638    if (HasLargeKey) {
639      assert(I->second == C && "Bad inversemap entry!");
640      InverseMap[C] = I;
641    }
642  }
643
644  void dump() const {
645    DEBUG(dbgs() << "Constant.cpp: ConstantUniqueMap\n");
646  }
647};
648
649// Unique map for aggregate constants
650template<class TypeClass, class ConstantClass>
651class ConstantAggrUniqueMap {
652public:
653  typedef ArrayRef<Constant*> Operands;
654  typedef std::pair<TypeClass*, Operands> LookupKey;
655private:
656  struct MapInfo {
657    typedef DenseMapInfo<ConstantClass*> ConstantClassInfo;
658    typedef DenseMapInfo<Constant*> ConstantInfo;
659    typedef DenseMapInfo<TypeClass*> TypeClassInfo;
660    static inline ConstantClass* getEmptyKey() {
661      return ConstantClassInfo::getEmptyKey();
662    }
663    static inline ConstantClass* getTombstoneKey() {
664      return ConstantClassInfo::getTombstoneKey();
665    }
666    static unsigned getHashValue(const ConstantClass *CP) {
667      SmallVector<Constant*, 8> CPOperands;
668      CPOperands.reserve(CP->getNumOperands());
669      for (unsigned I = 0, E = CP->getNumOperands(); I < E; ++I)
670        CPOperands.push_back(CP->getOperand(I));
671      return getHashValue(LookupKey(CP->getType(), CPOperands));
672    }
673    static bool isEqual(const ConstantClass *LHS, const ConstantClass *RHS) {
674      return LHS == RHS;
675    }
676    static unsigned getHashValue(const LookupKey &Val) {
677      return hash_combine(Val.first, hash_combine_range(Val.second.begin(),
678                                                        Val.second.end()));
679    }
680    static bool isEqual(const LookupKey &LHS, const ConstantClass *RHS) {
681      if (RHS == getEmptyKey() || RHS == getTombstoneKey())
682        return false;
683      if (LHS.first != RHS->getType()
684          || LHS.second.size() != RHS->getNumOperands())
685        return false;
686      for (unsigned I = 0, E = RHS->getNumOperands(); I < E; ++I) {
687        if (LHS.second[I] != RHS->getOperand(I))
688          return false;
689      }
690      return true;
691    }
692  };
693public:
694  typedef DenseMap<ConstantClass *, char, MapInfo> MapTy;
695
696private:
697  /// Map - This is the main map from the element descriptor to the Constants.
698  /// This is the primary way we avoid creating two of the same shape
699  /// constant.
700  MapTy Map;
701
702public:
703  typename MapTy::iterator map_begin() { return Map.begin(); }
704  typename MapTy::iterator map_end() { return Map.end(); }
705
706  void freeConstants() {
707    for (typename MapTy::iterator I=Map.begin(), E=Map.end();
708         I != E; ++I) {
709      // Asserts that use_empty().
710      delete I->first;
711    }
712  }
713
714private:
715  typename MapTy::iterator findExistingElement(ConstantClass *CP) {
716    return Map.find(CP);
717  }
718
719  ConstantClass *Create(TypeClass *Ty, Operands V, typename MapTy::iterator I) {
720    ConstantClass* Result =
721      ConstantArrayCreator<ConstantClass,TypeClass>::create(Ty, V);
722
723    assert(Result->getType() == Ty && "Type specified is not correct!");
724    Map[Result] = '\0';
725
726    return Result;
727  }
728public:
729
730  /// getOrCreate - Return the specified constant from the map, creating it if
731  /// necessary.
732  ConstantClass *getOrCreate(TypeClass *Ty, Operands V) {
733    LookupKey Lookup(Ty, V);
734    ConstantClass* Result = 0;
735
736    typename MapTy::iterator I = Map.find_as(Lookup);
737    // Is it in the map?
738    if (I != Map.end())
739      Result = I->first;
740
741    if (!Result) {
742      // If no preexisting value, create one now...
743      Result = Create(Ty, V, I);
744    }
745
746    return Result;
747  }
748
749  /// Find the constant by lookup key.
750  typename MapTy::iterator find(LookupKey Lookup) {
751    return Map.find_as(Lookup);
752  }
753
754  /// Insert the constant into its proper slot.
755  void insert(ConstantClass *CP) {
756    Map[CP] = '\0';
757  }
758
759  /// Remove this constant from the map
760  void remove(ConstantClass *CP) {
761    typename MapTy::iterator I = findExistingElement(CP);
762    assert(I != Map.end() && "Constant not found in constant table!");
763    assert(I->first == CP && "Didn't find correct element?");
764    Map.erase(I);
765  }
766
767  void dump() const {
768    DEBUG(dbgs() << "Constant.cpp: ConstantUniqueMap\n");
769  }
770};
771
772}
773
774#endif
775