LLVM API Documentation
00001 //===---------------- ConstantsContext.h - Implementation ------*- C++ -*--===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines various helper methods and classes used by 00011 // LLVMContextImpl for creating and managing constants. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #ifndef LLVM_CONSTANTSCONTEXT_H 00016 #define LLVM_CONSTANTSCONTEXT_H 00017 00018 #include "llvm/Instructions.h" 00019 #include "llvm/Metadata.h" 00020 #include "llvm/Operator.h" 00021 #include "llvm/Support/Debug.h" 00022 #include "llvm/Support/ErrorHandling.h" 00023 #include "llvm/System/Mutex.h" 00024 #include "llvm/System/RWMutex.h" 00025 #include <map> 00026 00027 namespace llvm { 00028 template<class ValType> 00029 struct ConstantTraits; 00030 00031 /// UnaryConstantExpr - This class is private to Constants.cpp, and is used 00032 /// behind the scenes to implement unary constant exprs. 00033 class UnaryConstantExpr : public ConstantExpr { 00034 void *operator new(size_t, unsigned); // DO NOT IMPLEMENT 00035 public: 00036 // allocate space for exactly one operand 00037 void *operator new(size_t s) { 00038 return User::operator new(s, 1); 00039 } 00040 UnaryConstantExpr(unsigned Opcode, Constant *C, const Type *Ty) 00041 : ConstantExpr(Ty, Opcode, &Op<0>(), 1) { 00042 Op<0>() = C; 00043 } 00044 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); 00045 }; 00046 00047 /// BinaryConstantExpr - This class is private to Constants.cpp, and is used 00048 /// behind the scenes to implement binary constant exprs. 00049 class BinaryConstantExpr : public ConstantExpr { 00050 void *operator new(size_t, unsigned); // DO NOT IMPLEMENT 00051 public: 00052 // allocate space for exactly two operands 00053 void *operator new(size_t s) { 00054 return User::operator new(s, 2); 00055 } 00056 BinaryConstantExpr(unsigned Opcode, Constant *C1, Constant *C2) 00057 : ConstantExpr(C1->getType(), Opcode, &Op<0>(), 2) { 00058 Op<0>() = C1; 00059 Op<1>() = C2; 00060 } 00061 /// Transparently provide more efficient getOperand methods. 00062 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); 00063 }; 00064 00065 /// SelectConstantExpr - This class is private to Constants.cpp, and is used 00066 /// behind the scenes to implement select constant exprs. 00067 class SelectConstantExpr : public ConstantExpr { 00068 void *operator new(size_t, unsigned); // DO NOT IMPLEMENT 00069 public: 00070 // allocate space for exactly three operands 00071 void *operator new(size_t s) { 00072 return User::operator new(s, 3); 00073 } 00074 SelectConstantExpr(Constant *C1, Constant *C2, Constant *C3) 00075 : ConstantExpr(C2->getType(), Instruction::Select, &Op<0>(), 3) { 00076 Op<0>() = C1; 00077 Op<1>() = C2; 00078 Op<2>() = C3; 00079 } 00080 /// Transparently provide more efficient getOperand methods. 00081 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); 00082 }; 00083 00084 /// ExtractElementConstantExpr - This class is private to 00085 /// Constants.cpp, and is used behind the scenes to implement 00086 /// extractelement constant exprs. 00087 class ExtractElementConstantExpr : public ConstantExpr { 00088 void *operator new(size_t, unsigned); // DO NOT IMPLEMENT 00089 public: 00090 // allocate space for exactly two operands 00091 void *operator new(size_t s) { 00092 return User::operator new(s, 2); 00093 } 00094 ExtractElementConstantExpr(Constant *C1, Constant *C2) 00095 : ConstantExpr(cast<VectorType>(C1->getType())->getElementType(), 00096 Instruction::ExtractElement, &Op<0>(), 2) { 00097 Op<0>() = C1; 00098 Op<1>() = C2; 00099 } 00100 /// Transparently provide more efficient getOperand methods. 00101 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); 00102 }; 00103 00104 /// InsertElementConstantExpr - This class is private to 00105 /// Constants.cpp, and is used behind the scenes to implement 00106 /// insertelement constant exprs. 00107 class InsertElementConstantExpr : public ConstantExpr { 00108 void *operator new(size_t, unsigned); // DO NOT IMPLEMENT 00109 public: 00110 // allocate space for exactly three operands 00111 void *operator new(size_t s) { 00112 return User::operator new(s, 3); 00113 } 00114 InsertElementConstantExpr(Constant *C1, Constant *C2, Constant *C3) 00115 : ConstantExpr(C1->getType(), Instruction::InsertElement, 00116 &Op<0>(), 3) { 00117 Op<0>() = C1; 00118 Op<1>() = C2; 00119 Op<2>() = C3; 00120 } 00121 /// Transparently provide more efficient getOperand methods. 00122 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); 00123 }; 00124 00125 /// ShuffleVectorConstantExpr - This class is private to 00126 /// Constants.cpp, and is used behind the scenes to implement 00127 /// shufflevector constant exprs. 00128 class ShuffleVectorConstantExpr : public ConstantExpr { 00129 void *operator new(size_t, unsigned); // DO NOT IMPLEMENT 00130 public: 00131 // allocate space for exactly three operands 00132 void *operator new(size_t s) { 00133 return User::operator new(s, 3); 00134 } 00135 ShuffleVectorConstantExpr(Constant *C1, Constant *C2, Constant *C3) 00136 : ConstantExpr(VectorType::get( 00137 cast<VectorType>(C1->getType())->getElementType(), 00138 cast<VectorType>(C3->getType())->getNumElements()), 00139 Instruction::ShuffleVector, 00140 &Op<0>(), 3) { 00141 Op<0>() = C1; 00142 Op<1>() = C2; 00143 Op<2>() = C3; 00144 } 00145 /// Transparently provide more efficient getOperand methods. 00146 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); 00147 }; 00148 00149 /// ExtractValueConstantExpr - This class is private to 00150 /// Constants.cpp, and is used behind the scenes to implement 00151 /// extractvalue constant exprs. 00152 class ExtractValueConstantExpr : public ConstantExpr { 00153 void *operator new(size_t, unsigned); // DO NOT IMPLEMENT 00154 public: 00155 // allocate space for exactly one operand 00156 void *operator new(size_t s) { 00157 return User::operator new(s, 1); 00158 } 00159 ExtractValueConstantExpr(Constant *Agg, 00160 const SmallVector<unsigned, 4> &IdxList, 00161 const Type *DestTy) 00162 : ConstantExpr(DestTy, Instruction::ExtractValue, &Op<0>(), 1), 00163 Indices(IdxList) { 00164 Op<0>() = Agg; 00165 } 00166 00167 /// Indices - These identify which value to extract. 00168 const SmallVector<unsigned, 4> Indices; 00169 00170 /// Transparently provide more efficient getOperand methods. 00171 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); 00172 }; 00173 00174 /// InsertValueConstantExpr - This class is private to 00175 /// Constants.cpp, and is used behind the scenes to implement 00176 /// insertvalue constant exprs. 00177 class InsertValueConstantExpr : public ConstantExpr { 00178 void *operator new(size_t, unsigned); // DO NOT IMPLEMENT 00179 public: 00180 // allocate space for exactly one operand 00181 void *operator new(size_t s) { 00182 return User::operator new(s, 2); 00183 } 00184 InsertValueConstantExpr(Constant *Agg, Constant *Val, 00185 const SmallVector<unsigned, 4> &IdxList, 00186 const Type *DestTy) 00187 : ConstantExpr(DestTy, Instruction::InsertValue, &Op<0>(), 2), 00188 Indices(IdxList) { 00189 Op<0>() = Agg; 00190 Op<1>() = Val; 00191 } 00192 00193 /// Indices - These identify the position for the insertion. 00194 const SmallVector<unsigned, 4> Indices; 00195 00196 /// Transparently provide more efficient getOperand methods. 00197 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); 00198 }; 00199 00200 00201 /// GetElementPtrConstantExpr - This class is private to Constants.cpp, and is 00202 /// used behind the scenes to implement getelementpr constant exprs. 00203 class GetElementPtrConstantExpr : public ConstantExpr { 00204 GetElementPtrConstantExpr(Constant *C, const std::vector<Constant*> &IdxList, 00205 const Type *DestTy); 00206 public: 00207 static GetElementPtrConstantExpr *Create(Constant *C, 00208 const std::vector<Constant*>&IdxList, 00209 const Type *DestTy) { 00210 return 00211 new(IdxList.size() + 1) GetElementPtrConstantExpr(C, IdxList, DestTy); 00212 } 00213 /// Transparently provide more efficient getOperand methods. 00214 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); 00215 }; 00216 00217 // CompareConstantExpr - This class is private to Constants.cpp, and is used 00218 // behind the scenes to implement ICmp and FCmp constant expressions. This is 00219 // needed in order to store the predicate value for these instructions. 00220 struct CompareConstantExpr : public ConstantExpr { 00221 void *operator new(size_t, unsigned); // DO NOT IMPLEMENT 00222 // allocate space for exactly two operands 00223 void *operator new(size_t s) { 00224 return User::operator new(s, 2); 00225 } 00226 unsigned short predicate; 00227 CompareConstantExpr(const Type *ty, Instruction::OtherOps opc, 00228 unsigned short pred, Constant* LHS, Constant* RHS) 00229 : ConstantExpr(ty, opc, &Op<0>(), 2), predicate(pred) { 00230 Op<0>() = LHS; 00231 Op<1>() = RHS; 00232 } 00233 /// Transparently provide more efficient getOperand methods. 00234 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); 00235 }; 00236 00237 template <> 00238 struct OperandTraits<UnaryConstantExpr> : FixedNumOperandTraits<1> { 00239 }; 00240 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(UnaryConstantExpr, Value) 00241 00242 template <> 00243 struct OperandTraits<BinaryConstantExpr> : FixedNumOperandTraits<2> { 00244 }; 00245 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(BinaryConstantExpr, Value) 00246 00247 template <> 00248 struct OperandTraits<SelectConstantExpr> : FixedNumOperandTraits<3> { 00249 }; 00250 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(SelectConstantExpr, Value) 00251 00252 template <> 00253 struct OperandTraits<ExtractElementConstantExpr> : FixedNumOperandTraits<2> { 00254 }; 00255 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ExtractElementConstantExpr, Value) 00256 00257 template <> 00258 struct OperandTraits<InsertElementConstantExpr> : FixedNumOperandTraits<3> { 00259 }; 00260 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(InsertElementConstantExpr, Value) 00261 00262 template <> 00263 struct OperandTraits<ShuffleVectorConstantExpr> : FixedNumOperandTraits<3> { 00264 }; 00265 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ShuffleVectorConstantExpr, Value) 00266 00267 template <> 00268 struct OperandTraits<ExtractValueConstantExpr> : FixedNumOperandTraits<1> { 00269 }; 00270 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ExtractValueConstantExpr, Value) 00271 00272 template <> 00273 struct OperandTraits<InsertValueConstantExpr> : FixedNumOperandTraits<2> { 00274 }; 00275 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(InsertValueConstantExpr, Value) 00276 00277 template <> 00278 struct OperandTraits<GetElementPtrConstantExpr> : VariadicOperandTraits<1> { 00279 }; 00280 00281 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(GetElementPtrConstantExpr, Value) 00282 00283 00284 template <> 00285 struct OperandTraits<CompareConstantExpr> : FixedNumOperandTraits<2> { 00286 }; 00287 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(CompareConstantExpr, Value) 00288 00289 struct ExprMapKeyType { 00290 typedef SmallVector<unsigned, 4> IndexList; 00291 00292 ExprMapKeyType(unsigned opc, 00293 const std::vector<Constant*> &ops, 00294 unsigned short pred = 0, 00295 const IndexList &inds = IndexList()) 00296 : opcode(opc), predicate(pred), operands(ops), indices(inds) {} 00297 uint16_t opcode; 00298 uint16_t predicate; 00299 std::vector<Constant*> operands; 00300 IndexList indices; 00301 bool operator==(const ExprMapKeyType& that) const { 00302 return this->opcode == that.opcode && 00303 this->predicate == that.predicate && 00304 this->operands == that.operands && 00305 this->indices == that.indices; 00306 } 00307 bool operator<(const ExprMapKeyType & that) const { 00308 return this->opcode < that.opcode || 00309 (this->opcode == that.opcode && this->predicate < that.predicate) || 00310 (this->opcode == that.opcode && this->predicate == that.predicate && 00311 this->operands < that.operands) || 00312 (this->opcode == that.opcode && this->predicate == that.predicate && 00313 this->operands == that.operands && this->indices < that.indices); 00314 } 00315 00316 bool operator!=(const ExprMapKeyType& that) const { 00317 return !(*this == that); 00318 } 00319 }; 00320 00321 // The number of operands for each ConstantCreator::create method is 00322 // determined by the ConstantTraits template. 00323 // ConstantCreator - A class that is used to create constants by 00324 // ValueMap*. This class should be partially specialized if there is 00325 // something strange that needs to be done to interface to the ctor for the 00326 // constant. 00327 // 00328 template<typename T, typename Alloc> 00329 struct ConstantTraits< std::vector<T, Alloc> > { 00330 static unsigned uses(const std::vector<T, Alloc>& v) { 00331 return v.size(); 00332 } 00333 }; 00334 00335 template<class ConstantClass, class TypeClass, class ValType> 00336 struct ConstantCreator { 00337 static ConstantClass *create(const TypeClass *Ty, const ValType &V) { 00338 return new(ConstantTraits<ValType>::uses(V)) ConstantClass(Ty, V); 00339 } 00340 }; 00341 00342 template<class ConstantClass, class TypeClass> 00343 struct ConvertConstant { 00344 static void convert(ConstantClass *OldC, const TypeClass *NewTy) { 00345 llvm_unreachable("This type cannot be converted!"); 00346 } 00347 }; 00348 00349 template<> 00350 struct ConstantCreator<ConstantExpr, Type, ExprMapKeyType> { 00351 static ConstantExpr *create(const Type *Ty, const ExprMapKeyType &V, 00352 unsigned short pred = 0) { 00353 if (Instruction::isCast(V.opcode)) 00354 return new UnaryConstantExpr(V.opcode, V.operands[0], Ty); 00355 if ((V.opcode >= Instruction::BinaryOpsBegin && 00356 V.opcode < Instruction::BinaryOpsEnd)) 00357 return new BinaryConstantExpr(V.opcode, V.operands[0], V.operands[1]); 00358 if (V.opcode == Instruction::Select) 00359 return new SelectConstantExpr(V.operands[0], V.operands[1], 00360 V.operands[2]); 00361 if (V.opcode == Instruction::ExtractElement) 00362 return new ExtractElementConstantExpr(V.operands[0], V.operands[1]); 00363 if (V.opcode == Instruction::InsertElement) 00364 return new InsertElementConstantExpr(V.operands[0], V.operands[1], 00365 V.operands[2]); 00366 if (V.opcode == Instruction::ShuffleVector) 00367 return new ShuffleVectorConstantExpr(V.operands[0], V.operands[1], 00368 V.operands[2]); 00369 if (V.opcode == Instruction::InsertValue) 00370 return new InsertValueConstantExpr(V.operands[0], V.operands[1], 00371 V.indices, Ty); 00372 if (V.opcode == Instruction::ExtractValue) 00373 return new ExtractValueConstantExpr(V.operands[0], V.indices, Ty); 00374 if (V.opcode == Instruction::GetElementPtr) { 00375 std::vector<Constant*> IdxList(V.operands.begin()+1, V.operands.end()); 00376 return GetElementPtrConstantExpr::Create(V.operands[0], IdxList, Ty); 00377 } 00378 00379 // The compare instructions are weird. We have to encode the predicate 00380 // value and it is combined with the instruction opcode by multiplying 00381 // the opcode by one hundred. We must decode this to get the predicate. 00382 if (V.opcode == Instruction::ICmp) 00383 return new CompareConstantExpr(Ty, Instruction::ICmp, V.predicate, 00384 V.operands[0], V.operands[1]); 00385 if (V.opcode == Instruction::FCmp) 00386 return new CompareConstantExpr(Ty, Instruction::FCmp, V.predicate, 00387 V.operands[0], V.operands[1]); 00388 llvm_unreachable("Invalid ConstantExpr!"); 00389 return 0; 00390 } 00391 }; 00392 00393 template<> 00394 struct ConvertConstant<ConstantExpr, Type> { 00395 static void convert(ConstantExpr *OldC, const Type *NewTy) { 00396 Constant *New; 00397 switch (OldC->getOpcode()) { 00398 case Instruction::Trunc: 00399 case Instruction::ZExt: 00400 case Instruction::SExt: 00401 case Instruction::FPTrunc: 00402 case Instruction::FPExt: 00403 case Instruction::UIToFP: 00404 case Instruction::SIToFP: 00405 case Instruction::FPToUI: 00406 case Instruction::FPToSI: 00407 case Instruction::PtrToInt: 00408 case Instruction::IntToPtr: 00409 case Instruction::BitCast: 00410 New = ConstantExpr::getCast(OldC->getOpcode(), OldC->getOperand(0), 00411 NewTy); 00412 break; 00413 case Instruction::Select: 00414 New = ConstantExpr::getSelectTy(NewTy, OldC->getOperand(0), 00415 OldC->getOperand(1), 00416 OldC->getOperand(2)); 00417 break; 00418 default: 00419 assert(OldC->getOpcode() >= Instruction::BinaryOpsBegin && 00420 OldC->getOpcode() < Instruction::BinaryOpsEnd); 00421 New = ConstantExpr::getTy(NewTy, OldC->getOpcode(), OldC->getOperand(0), 00422 OldC->getOperand(1)); 00423 break; 00424 case Instruction::GetElementPtr: 00425 // Make everyone now use a constant of the new type... 00426 std::vector<Value*> Idx(OldC->op_begin()+1, OldC->op_end()); 00427 New = ConstantExpr::getGetElementPtrTy(NewTy, OldC->getOperand(0), 00428 &Idx[0], Idx.size()); 00429 break; 00430 } 00431 00432 assert(New != OldC && "Didn't replace constant??"); 00433 OldC->uncheckedReplaceAllUsesWith(New); 00434 OldC->destroyConstant(); // This constant is now dead, destroy it. 00435 } 00436 }; 00437 00438 // ConstantAggregateZero does not take extra "value" argument... 00439 template<class ValType> 00440 struct ConstantCreator<ConstantAggregateZero, Type, ValType> { 00441 static ConstantAggregateZero *create(const Type *Ty, const ValType &V){ 00442 return new ConstantAggregateZero(Ty); 00443 } 00444 }; 00445 00446 template<> 00447 struct ConstantCreator<MDNode, Type, std::vector<Value*> > { 00448 static MDNode *create(const Type* Ty, const std::vector<Value*> &V) { 00449 return new MDNode(Ty->getContext(), &V[0], V.size()); 00450 } 00451 }; 00452 00453 template<> 00454 struct ConvertConstant<ConstantVector, VectorType> { 00455 static void convert(ConstantVector *OldC, const VectorType *NewTy) { 00456 // Make everyone now use a constant of the new type... 00457 std::vector<Constant*> C; 00458 for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i) 00459 C.push_back(cast<Constant>(OldC->getOperand(i))); 00460 Constant *New = ConstantVector::get(NewTy, C); 00461 assert(New != OldC && "Didn't replace constant??"); 00462 OldC->uncheckedReplaceAllUsesWith(New); 00463 OldC->destroyConstant(); // This constant is now dead, destroy it. 00464 } 00465 }; 00466 00467 template<> 00468 struct ConvertConstant<ConstantAggregateZero, Type> { 00469 static void convert(ConstantAggregateZero *OldC, const Type *NewTy) { 00470 // Make everyone now use a constant of the new type... 00471 Constant *New = ConstantAggregateZero::get(NewTy); 00472 assert(New != OldC && "Didn't replace constant??"); 00473 OldC->uncheckedReplaceAllUsesWith(New); 00474 OldC->destroyConstant(); // This constant is now dead, destroy it. 00475 } 00476 }; 00477 00478 template<> 00479 struct ConvertConstant<ConstantArray, ArrayType> { 00480 static void convert(ConstantArray *OldC, const ArrayType *NewTy) { 00481 // Make everyone now use a constant of the new type... 00482 std::vector<Constant*> C; 00483 for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i) 00484 C.push_back(cast<Constant>(OldC->getOperand(i))); 00485 Constant *New = ConstantArray::get(NewTy, C); 00486 assert(New != OldC && "Didn't replace constant??"); 00487 OldC->uncheckedReplaceAllUsesWith(New); 00488 OldC->destroyConstant(); // This constant is now dead, destroy it. 00489 } 00490 }; 00491 00492 template<> 00493 struct ConvertConstant<ConstantStruct, StructType> { 00494 static void convert(ConstantStruct *OldC, const StructType *NewTy) { 00495 // Make everyone now use a constant of the new type... 00496 std::vector<Constant*> C; 00497 for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i) 00498 C.push_back(cast<Constant>(OldC->getOperand(i))); 00499 Constant *New = ConstantStruct::get(NewTy, C); 00500 assert(New != OldC && "Didn't replace constant??"); 00501 00502 OldC->uncheckedReplaceAllUsesWith(New); 00503 OldC->destroyConstant(); // This constant is now dead, destroy it. 00504 } 00505 }; 00506 00507 // ConstantPointerNull does not take extra "value" argument... 00508 template<class ValType> 00509 struct ConstantCreator<ConstantPointerNull, PointerType, ValType> { 00510 static ConstantPointerNull *create(const PointerType *Ty, const ValType &V){ 00511 return new ConstantPointerNull(Ty); 00512 } 00513 }; 00514 00515 template<> 00516 struct ConvertConstant<ConstantPointerNull, PointerType> { 00517 static void convert(ConstantPointerNull *OldC, const PointerType *NewTy) { 00518 // Make everyone now use a constant of the new type... 00519 Constant *New = ConstantPointerNull::get(NewTy); 00520 assert(New != OldC && "Didn't replace constant??"); 00521 OldC->uncheckedReplaceAllUsesWith(New); 00522 OldC->destroyConstant(); // This constant is now dead, destroy it. 00523 } 00524 }; 00525 00526 // UndefValue does not take extra "value" argument... 00527 template<class ValType> 00528 struct ConstantCreator<UndefValue, Type, ValType> { 00529 static UndefValue *create(const Type *Ty, const ValType &V) { 00530 return new UndefValue(Ty); 00531 } 00532 }; 00533 00534 template<> 00535 struct ConvertConstant<UndefValue, Type> { 00536 static void convert(UndefValue *OldC, const Type *NewTy) { 00537 // Make everyone now use a constant of the new type. 00538 Constant *New = UndefValue::get(NewTy); 00539 assert(New != OldC && "Didn't replace constant??"); 00540 OldC->uncheckedReplaceAllUsesWith(New); 00541 OldC->destroyConstant(); // This constant is now dead, destroy it. 00542 } 00543 }; 00544 00545 template<class ValType, class TypeClass, class ConstantClass, 00546 bool HasLargeKey = false /*true for arrays and structs*/ > 00547 class ValueMap : public AbstractTypeUser { 00548 public: 00549 typedef std::pair<const Type*, ValType> MapKey; 00550 typedef std::map<MapKey, Value *> MapTy; 00551 typedef std::map<Value*, typename MapTy::iterator> InverseMapTy; 00552 typedef std::map<const Type*, typename MapTy::iterator> AbstractTypeMapTy; 00553 private: 00554 /// Map - This is the main map from the element descriptor to the Constants. 00555 /// This is the primary way we avoid creating two of the same shape 00556 /// constant. 00557 MapTy Map; 00558 00559 /// InverseMap - If "HasLargeKey" is true, this contains an inverse mapping 00560 /// from the constants to their element in Map. This is important for 00561 /// removal of constants from the array, which would otherwise have to scan 00562 /// through the map with very large keys. 00563 InverseMapTy InverseMap; 00564 00565 /// AbstractTypeMap - Map for abstract type constants. 00566 /// 00567 AbstractTypeMapTy AbstractTypeMap; 00568 00569 /// ValueMapLock - Mutex for this map. 00570 sys::SmartMutex<true> ValueMapLock; 00571 00572 public: 00573 // NOTE: This function is not locked. It is the caller's responsibility 00574 // to enforce proper synchronization. 00575 typename MapTy::iterator map_begin() { return Map.begin(); } 00576 typename MapTy::iterator map_end() { return Map.end(); } 00577 00578 /// InsertOrGetItem - Return an iterator for the specified element. 00579 /// If the element exists in the map, the returned iterator points to the 00580 /// entry and Exists=true. If not, the iterator points to the newly 00581 /// inserted entry and returns Exists=false. Newly inserted entries have 00582 /// I->second == 0, and should be filled in. 00583 /// NOTE: This function is not locked. It is the caller's responsibility 00584 // to enforce proper synchronization. 00585 typename MapTy::iterator InsertOrGetItem(std::pair<MapKey, Constant *> 00586 &InsertVal, 00587 bool &Exists) { 00588 std::pair<typename MapTy::iterator, bool> IP = Map.insert(InsertVal); 00589 Exists = !IP.second; 00590 return IP.first; 00591 } 00592 00593 private: 00594 typename MapTy::iterator FindExistingElement(ConstantClass *CP) { 00595 if (HasLargeKey) { 00596 typename InverseMapTy::iterator IMI = InverseMap.find(CP); 00597 assert(IMI != InverseMap.end() && IMI->second != Map.end() && 00598 IMI->second->second == CP && 00599 "InverseMap corrupt!"); 00600 return IMI->second; 00601 } 00602 00603 typename MapTy::iterator I = 00604 Map.find(MapKey(static_cast<const TypeClass*>(CP->getRawType()), 00605 getValType(CP))); 00606 if (I == Map.end() || I->second != CP) { 00607 // FIXME: This should not use a linear scan. If this gets to be a 00608 // performance problem, someone should look at this. 00609 for (I = Map.begin(); I != Map.end() && I->second != CP; ++I) 00610 /* empty */; 00611 } 00612 return I; 00613 } 00614 00615 ConstantClass* Create(const TypeClass *Ty, const ValType &V, 00616 typename MapTy::iterator I) { 00617 ConstantClass* Result = 00618 ConstantCreator<ConstantClass,TypeClass,ValType>::create(Ty, V); 00619 00620 assert(Result->getType() == Ty && "Type specified is not correct!"); 00621 I = Map.insert(I, std::make_pair(MapKey(Ty, V), Result)); 00622 00623 if (HasLargeKey) // Remember the reverse mapping if needed. 00624 InverseMap.insert(std::make_pair(Result, I)); 00625 00626 // If the type of the constant is abstract, make sure that an entry 00627 // exists for it in the AbstractTypeMap. 00628 if (Ty->isAbstract()) { 00629 typename AbstractTypeMapTy::iterator TI = 00630 AbstractTypeMap.find(Ty); 00631 00632 if (TI == AbstractTypeMap.end()) { 00633 // Add ourselves to the ATU list of the type. 00634 cast<DerivedType>(Ty)->addAbstractTypeUser(this); 00635 00636 AbstractTypeMap.insert(TI, std::make_pair(Ty, I)); 00637 } 00638 } 00639 00640 return Result; 00641 } 00642 public: 00643 00644 /// getOrCreate - Return the specified constant from the map, creating it if 00645 /// necessary. 00646 ConstantClass *getOrCreate(const TypeClass *Ty, const ValType &V) { 00647 sys::SmartScopedLock<true> Lock(ValueMapLock); 00648 MapKey Lookup(Ty, V); 00649 ConstantClass* Result = 0; 00650 00651 typename MapTy::iterator I = Map.find(Lookup); 00652 // Is it in the map? 00653 if (I != Map.end()) 00654 Result = static_cast<ConstantClass *>(I->second); 00655 00656 if (!Result) { 00657 // If no preexisting value, create one now... 00658 Result = Create(Ty, V, I); 00659 } 00660 00661 return Result; 00662 } 00663 00664 void remove(ConstantClass *CP) { 00665 sys::SmartScopedLock<true> Lock(ValueMapLock); 00666 typename MapTy::iterator I = FindExistingElement(CP); 00667 assert(I != Map.end() && "Constant not found in constant table!"); 00668 assert(I->second == CP && "Didn't find correct element?"); 00669 00670 if (HasLargeKey) // Remember the reverse mapping if needed. 00671 InverseMap.erase(CP); 00672 00673 // Now that we found the entry, make sure this isn't the entry that 00674 // the AbstractTypeMap points to. 00675 const TypeClass *Ty = static_cast<const TypeClass *>(I->first.first); 00676 if (Ty->isAbstract()) { 00677 assert(AbstractTypeMap.count(Ty) && 00678 "Abstract type not in AbstractTypeMap?"); 00679 typename MapTy::iterator &ATMEntryIt = AbstractTypeMap[Ty]; 00680 if (ATMEntryIt == I) { 00681 // Yes, we are removing the representative entry for this type. 00682 // See if there are any other entries of the same type. 00683 typename MapTy::iterator TmpIt = ATMEntryIt; 00684 00685 // First check the entry before this one... 00686 if (TmpIt != Map.begin()) { 00687 --TmpIt; 00688 if (TmpIt->first.first != Ty) // Not the same type, move back... 00689 ++TmpIt; 00690 } 00691 00692 // If we didn't find the same type, try to move forward... 00693 if (TmpIt == ATMEntryIt) { 00694 ++TmpIt; 00695 if (TmpIt == Map.end() || TmpIt->first.first != Ty) 00696 --TmpIt; // No entry afterwards with the same type 00697 } 00698 00699 // If there is another entry in the map of the same abstract type, 00700 // update the AbstractTypeMap entry now. 00701 if (TmpIt != ATMEntryIt) { 00702 ATMEntryIt = TmpIt; 00703 } else { 00704 // Otherwise, we are removing the last instance of this type 00705 // from the table. Remove from the ATM, and from user list. 00706 cast<DerivedType>(Ty)->removeAbstractTypeUser(this); 00707 AbstractTypeMap.erase(Ty); 00708 } 00709 } 00710 } 00711 00712 Map.erase(I); 00713 } 00714 00715 00716 /// MoveConstantToNewSlot - If we are about to change C to be the element 00717 /// specified by I, update our internal data structures to reflect this 00718 /// fact. 00719 /// NOTE: This function is not locked. It is the responsibility of the 00720 /// caller to enforce proper synchronization if using this method. 00721 void MoveConstantToNewSlot(ConstantClass *C, typename MapTy::iterator I) { 00722 // First, remove the old location of the specified constant in the map. 00723 typename MapTy::iterator OldI = FindExistingElement(C); 00724 assert(OldI != Map.end() && "Constant not found in constant table!"); 00725 assert(OldI->second == C && "Didn't find correct element?"); 00726 00727 // If this constant is the representative element for its abstract type, 00728 // update the AbstractTypeMap so that the representative element is I. 00729 if (C->getType()->isAbstract()) { 00730 typename AbstractTypeMapTy::iterator ATI = 00731 AbstractTypeMap.find(C->getType()); 00732 assert(ATI != AbstractTypeMap.end() && 00733 "Abstract type not in AbstractTypeMap?"); 00734 if (ATI->second == OldI) 00735 ATI->second = I; 00736 } 00737 00738 // Remove the old entry from the map. 00739 Map.erase(OldI); 00740 00741 // Update the inverse map so that we know that this constant is now 00742 // located at descriptor I. 00743 if (HasLargeKey) { 00744 assert(I->second == C && "Bad inversemap entry!"); 00745 InverseMap[C] = I; 00746 } 00747 } 00748 00749 void refineAbstractType(const DerivedType *OldTy, const Type *NewTy) { 00750 sys::SmartScopedLock<true> Lock(ValueMapLock); 00751 typename AbstractTypeMapTy::iterator I = 00752 AbstractTypeMap.find(cast<Type>(OldTy)); 00753 00754 assert(I != AbstractTypeMap.end() && 00755 "Abstract type not in AbstractTypeMap?"); 00756 00757 // Convert a constant at a time until the last one is gone. The last one 00758 // leaving will remove() itself, causing the AbstractTypeMapEntry to be 00759 // eliminated eventually. 00760 do { 00761 ConvertConstant<ConstantClass, TypeClass>::convert( 00762 static_cast<ConstantClass *>(I->second->second), 00763 cast<TypeClass>(NewTy)); 00764 00765 I = AbstractTypeMap.find(cast<Type>(OldTy)); 00766 } while (I != AbstractTypeMap.end()); 00767 } 00768 00769 // If the type became concrete without being refined to any other existing 00770 // type, we just remove ourselves from the ATU list. 00771 void typeBecameConcrete(const DerivedType *AbsTy) { 00772 AbsTy->removeAbstractTypeUser(this); 00773 } 00774 00775 void dump() const { 00776 DOUT << "Constant.cpp: ValueMap\n"; 00777 } 00778 }; 00779 00780 } 00781 00782 #endif