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