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