Add mipsel-* to the list of targets recognized by configure script.
[oota-llvm.git] / lib / VMCore / ConstantsContext.h
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
28 namespace llvm {
29 template<class ValType>
30 struct ConstantTraits;
31
32 /// UnaryConstantExpr - This class is private to Constants.cpp, and is used
33 /// behind the scenes to implement unary constant exprs.
34 class UnaryConstantExpr : public ConstantExpr {
35   virtual void anchor();
36   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
37 public:
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.
51 class BinaryConstantExpr : public ConstantExpr {
52   virtual void anchor();
53   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
54 public:
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.
72 class SelectConstantExpr : public ConstantExpr {
73   virtual void anchor();
74   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
75 public:
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.
93 class ExtractElementConstantExpr : public ConstantExpr {
94   virtual void anchor();
95   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
96 public:
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.
114 class InsertElementConstantExpr : public ConstantExpr {
115   virtual void anchor();
116   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
117 public:
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.
136 class ShuffleVectorConstantExpr : public ConstantExpr {
137   virtual void anchor();
138   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
139 public:
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.
161 class ExtractValueConstantExpr : public ConstantExpr {
162   virtual void anchor();
163   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
164 public:
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.
187 class InsertValueConstantExpr : public ConstantExpr {
188   virtual void anchor();
189   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
190 public:
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.
214 class GetElementPtrConstantExpr : public ConstantExpr {
215   virtual void anchor();
216   GetElementPtrConstantExpr(Constant *C, ArrayRef<Constant*> IdxList,
217                             Type *DestTy);
218 public:
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.
235 class CompareConstantExpr : public ConstantExpr {
236   virtual void anchor();
237   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
238 public:
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
254 template <>
255 struct OperandTraits<UnaryConstantExpr> :
256   public FixedNumOperandTraits<UnaryConstantExpr, 1> {
257 };
258 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(UnaryConstantExpr, Value)
259
260 template <>
261 struct OperandTraits<BinaryConstantExpr> :
262   public FixedNumOperandTraits<BinaryConstantExpr, 2> {
263 };
264 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(BinaryConstantExpr, Value)
265
266 template <>
267 struct OperandTraits<SelectConstantExpr> :
268   public FixedNumOperandTraits<SelectConstantExpr, 3> {
269 };
270 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(SelectConstantExpr, Value)
271
272 template <>
273 struct OperandTraits<ExtractElementConstantExpr> :
274   public FixedNumOperandTraits<ExtractElementConstantExpr, 2> {
275 };
276 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ExtractElementConstantExpr, Value)
277
278 template <>
279 struct OperandTraits<InsertElementConstantExpr> :
280   public FixedNumOperandTraits<InsertElementConstantExpr, 3> {
281 };
282 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(InsertElementConstantExpr, Value)
283
284 template <>
285 struct OperandTraits<ShuffleVectorConstantExpr> :
286     public FixedNumOperandTraits<ShuffleVectorConstantExpr, 3> {
287 };
288 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ShuffleVectorConstantExpr, Value)
289
290 template <>
291 struct OperandTraits<ExtractValueConstantExpr> :
292   public FixedNumOperandTraits<ExtractValueConstantExpr, 1> {
293 };
294 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ExtractValueConstantExpr, Value)
295
296 template <>
297 struct OperandTraits<InsertValueConstantExpr> :
298   public FixedNumOperandTraits<InsertValueConstantExpr, 2> {
299 };
300 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(InsertValueConstantExpr, Value)
301
302 template <>
303 struct OperandTraits<GetElementPtrConstantExpr> :
304   public VariadicOperandTraits<GetElementPtrConstantExpr, 1> {
305 };
306
307 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(GetElementPtrConstantExpr, Value)
308
309
310 template <>
311 struct OperandTraits<CompareConstantExpr> :
312   public FixedNumOperandTraits<CompareConstantExpr, 2> {
313 };
314 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(CompareConstantExpr, Value)
315
316 struct 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
352 struct 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 //
392 template<typename T, typename Alloc>
393 struct ConstantTraits< std::vector<T, Alloc> > {
394   static unsigned uses(const std::vector<T, Alloc>& v) {
395     return v.size();
396   }
397 };
398
399 template<>
400 struct ConstantTraits<Constant *> {
401   static unsigned uses(Constant * const & v) {
402     return 1;
403   }
404 };
405
406 template<class ConstantClass, class TypeClass, class ValType>
407 struct ConstantCreator {
408   static ConstantClass *create(TypeClass *Ty, const ValType &V) {
409     return new(ConstantTraits<ValType>::uses(V)) ConstantClass(Ty, V);
410   }
411 };
412
413 template<class ConstantClass, class TypeClass>
414 struct ConstantArrayCreator {
415   static ConstantClass *create(TypeClass *Ty, ArrayRef<Constant*> V) {
416     return new(V.size()) ConstantClass(Ty, V);
417   }
418 };
419
420 template<class ConstantClass>
421 struct ConstantKeyData {
422   typedef void ValType;
423   static ValType getValType(ConstantClass *C) {
424     llvm_unreachable("Unknown Constant type!");
425   }
426 };
427
428 template<>
429 struct 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
473 template<>
474 struct 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
489 template<>
490 struct 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
497 template<>
498 struct 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
506 template<class ValType, class ValRefType, class TypeClass, class ConstantClass,
507          bool HasLargeKey = false /*true for arrays and structs*/ >
508 class ConstantUniqueMap {
509 public:
510   typedef std::pair<TypeClass*, ValType> MapKey;
511   typedef std::map<MapKey, ConstantClass *> MapTy;
512   typedef std::map<ConstantClass *, typename MapTy::iterator> InverseMapTy;
513 private:
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
525 public:
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     
550 private:
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   }
585 public:
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
643 template<class TypeClass, class ConstantClass>
644 class ConstantAggrUniqueMap {
645 public:
646   typedef ArrayRef<Constant*> Operands;
647   typedef std::pair<TypeClass*, Operands> LookupKey;
648 private:
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   };
686 public:
687   typedef DenseMap<ConstantClass *, char, MapInfo> MapTy;
688
689 private:
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
695 public:
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
707 private:
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   }
721 public:
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