1 //===-- ConstantsContext.h - Constants-related Context Interals -*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines various helper methods and classes used by 10 // LLVMContextImpl for creating and managing constants. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_LIB_IR_CONSTANTSCONTEXT_H 15 #define LLVM_LIB_IR_CONSTANTSCONTEXT_H 16 17 #include "llvm/ADT/ArrayRef.h" 18 #include "llvm/ADT/DenseMapInfo.h" 19 #include "llvm/ADT/DenseSet.h" 20 #include "llvm/ADT/Hashing.h" 21 #include "llvm/ADT/None.h" 22 #include "llvm/ADT/SmallVector.h" 23 #include "llvm/ADT/StringRef.h" 24 #include "llvm/IR/Constant.h" 25 #include "llvm/IR/Constants.h" 26 #include "llvm/IR/DerivedTypes.h" 27 #include "llvm/IR/InlineAsm.h" 28 #include "llvm/IR/Instruction.h" 29 #include "llvm/IR/Instructions.h" 30 #include "llvm/IR/OperandTraits.h" 31 #include "llvm/Support/Casting.h" 32 #include "llvm/Support/Debug.h" 33 #include "llvm/Support/ErrorHandling.h" 34 #include "llvm/Support/raw_ostream.h" 35 #include <cassert> 36 #include <cstddef> 37 #include <cstdint> 38 #include <utility> 39 40 #define DEBUG_TYPE "ir" 41 42 namespace llvm { 43 44 /// UnaryConstantExpr - This class is private to Constants.cpp, and is used 45 /// behind the scenes to implement unary constant exprs. 46 class UnaryConstantExpr final : public ConstantExpr { 47 public: UnaryConstantExpr(unsigned Opcode,Constant * C,Type * Ty)48 UnaryConstantExpr(unsigned Opcode, Constant *C, Type *Ty) 49 : ConstantExpr(Ty, Opcode, &Op<0>(), 1) { 50 Op<0>() = C; 51 } 52 53 // allocate space for exactly one operand new(size_t s)54 void *operator new(size_t s) { 55 return User::operator new(s, 1); 56 } 57 58 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); 59 classof(const ConstantExpr * CE)60 static bool classof(const ConstantExpr *CE) { 61 return Instruction::isCast(CE->getOpcode()) || 62 Instruction::isUnaryOp(CE->getOpcode()); 63 } classof(const Value * V)64 static bool classof(const Value *V) { 65 return isa<ConstantExpr>(V) && classof(cast<ConstantExpr>(V)); 66 } 67 }; 68 69 /// BinaryConstantExpr - This class is private to Constants.cpp, and is used 70 /// behind the scenes to implement binary constant exprs. 71 class BinaryConstantExpr final : public ConstantExpr { 72 public: BinaryConstantExpr(unsigned Opcode,Constant * C1,Constant * C2,unsigned Flags)73 BinaryConstantExpr(unsigned Opcode, Constant *C1, Constant *C2, 74 unsigned Flags) 75 : ConstantExpr(C1->getType(), Opcode, &Op<0>(), 2) { 76 Op<0>() = C1; 77 Op<1>() = C2; 78 SubclassOptionalData = Flags; 79 } 80 81 // allocate space for exactly two operands new(size_t s)82 void *operator new(size_t s) { 83 return User::operator new(s, 2); 84 } 85 86 /// Transparently provide more efficient getOperand methods. 87 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); 88 classof(const ConstantExpr * CE)89 static bool classof(const ConstantExpr *CE) { 90 return Instruction::isBinaryOp(CE->getOpcode()); 91 } classof(const Value * V)92 static bool classof(const Value *V) { 93 return isa<ConstantExpr>(V) && classof(cast<ConstantExpr>(V)); 94 } 95 }; 96 97 /// SelectConstantExpr - This class is private to Constants.cpp, and is used 98 /// behind the scenes to implement select constant exprs. 99 class SelectConstantExpr final : public ConstantExpr { 100 public: SelectConstantExpr(Constant * C1,Constant * C2,Constant * C3)101 SelectConstantExpr(Constant *C1, Constant *C2, Constant *C3) 102 : ConstantExpr(C2->getType(), Instruction::Select, &Op<0>(), 3) { 103 Op<0>() = C1; 104 Op<1>() = C2; 105 Op<2>() = C3; 106 } 107 108 // allocate space for exactly three operands new(size_t s)109 void *operator new(size_t s) { 110 return User::operator new(s, 3); 111 } 112 113 /// Transparently provide more efficient getOperand methods. 114 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); 115 classof(const ConstantExpr * CE)116 static bool classof(const ConstantExpr *CE) { 117 return CE->getOpcode() == Instruction::Select; 118 } classof(const Value * V)119 static bool classof(const Value *V) { 120 return isa<ConstantExpr>(V) && classof(cast<ConstantExpr>(V)); 121 } 122 }; 123 124 /// ExtractElementConstantExpr - This class is private to 125 /// Constants.cpp, and is used behind the scenes to implement 126 /// extractelement constant exprs. 127 class ExtractElementConstantExpr final : public ConstantExpr { 128 public: ExtractElementConstantExpr(Constant * C1,Constant * C2)129 ExtractElementConstantExpr(Constant *C1, Constant *C2) 130 : ConstantExpr(cast<VectorType>(C1->getType())->getElementType(), 131 Instruction::ExtractElement, &Op<0>(), 2) { 132 Op<0>() = C1; 133 Op<1>() = C2; 134 } 135 136 // allocate space for exactly two operands new(size_t s)137 void *operator new(size_t s) { 138 return User::operator new(s, 2); 139 } 140 141 /// Transparently provide more efficient getOperand methods. 142 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); 143 classof(const ConstantExpr * CE)144 static bool classof(const ConstantExpr *CE) { 145 return CE->getOpcode() == Instruction::ExtractElement; 146 } classof(const Value * V)147 static bool classof(const Value *V) { 148 return isa<ConstantExpr>(V) && classof(cast<ConstantExpr>(V)); 149 } 150 }; 151 152 /// InsertElementConstantExpr - This class is private to 153 /// Constants.cpp, and is used behind the scenes to implement 154 /// insertelement constant exprs. 155 class InsertElementConstantExpr final : public ConstantExpr { 156 public: InsertElementConstantExpr(Constant * C1,Constant * C2,Constant * C3)157 InsertElementConstantExpr(Constant *C1, Constant *C2, Constant *C3) 158 : ConstantExpr(C1->getType(), Instruction::InsertElement, 159 &Op<0>(), 3) { 160 Op<0>() = C1; 161 Op<1>() = C2; 162 Op<2>() = C3; 163 } 164 165 // allocate space for exactly three operands new(size_t s)166 void *operator new(size_t s) { 167 return User::operator new(s, 3); 168 } 169 170 /// Transparently provide more efficient getOperand methods. 171 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); 172 classof(const ConstantExpr * CE)173 static bool classof(const ConstantExpr *CE) { 174 return CE->getOpcode() == Instruction::InsertElement; 175 } classof(const Value * V)176 static bool classof(const Value *V) { 177 return isa<ConstantExpr>(V) && classof(cast<ConstantExpr>(V)); 178 } 179 }; 180 181 /// ShuffleVectorConstantExpr - This class is private to 182 /// Constants.cpp, and is used behind the scenes to implement 183 /// shufflevector constant exprs. 184 class ShuffleVectorConstantExpr final : public ConstantExpr { 185 public: ShuffleVectorConstantExpr(Constant * C1,Constant * C2,ArrayRef<int> Mask)186 ShuffleVectorConstantExpr(Constant *C1, Constant *C2, ArrayRef<int> Mask) 187 : ConstantExpr(VectorType::get( 188 cast<VectorType>(C1->getType())->getElementType(), 189 Mask.size(), isa<ScalableVectorType>(C1->getType())), 190 Instruction::ShuffleVector, &Op<0>(), 2) { 191 assert(ShuffleVectorInst::isValidOperands(C1, C2, Mask) && 192 "Invalid shuffle vector instruction operands!"); 193 Op<0>() = C1; 194 Op<1>() = C2; 195 ShuffleMask.assign(Mask.begin(), Mask.end()); 196 ShuffleMaskForBitcode = 197 ShuffleVectorInst::convertShuffleMaskForBitcode(Mask, getType()); 198 } 199 200 SmallVector<int, 4> ShuffleMask; 201 Constant *ShuffleMaskForBitcode; 202 new(size_t s)203 void *operator new(size_t s) { return User::operator new(s, 2); } 204 205 /// Transparently provide more efficient getOperand methods. 206 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); 207 classof(const ConstantExpr * CE)208 static bool classof(const ConstantExpr *CE) { 209 return CE->getOpcode() == Instruction::ShuffleVector; 210 } classof(const Value * V)211 static bool classof(const Value *V) { 212 return isa<ConstantExpr>(V) && classof(cast<ConstantExpr>(V)); 213 } 214 }; 215 216 /// ExtractValueConstantExpr - This class is private to 217 /// Constants.cpp, and is used behind the scenes to implement 218 /// extractvalue constant exprs. 219 class ExtractValueConstantExpr final : public ConstantExpr { 220 public: ExtractValueConstantExpr(Constant * Agg,ArrayRef<unsigned> IdxList,Type * DestTy)221 ExtractValueConstantExpr(Constant *Agg, ArrayRef<unsigned> IdxList, 222 Type *DestTy) 223 : ConstantExpr(DestTy, Instruction::ExtractValue, &Op<0>(), 1), 224 Indices(IdxList.begin(), IdxList.end()) { 225 Op<0>() = Agg; 226 } 227 228 // allocate space for exactly one operand new(size_t s)229 void *operator new(size_t s) { 230 return User::operator new(s, 1); 231 } 232 233 /// Indices - These identify which value to extract. 234 const SmallVector<unsigned, 4> Indices; 235 236 /// Transparently provide more efficient getOperand methods. 237 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); 238 classof(const ConstantExpr * CE)239 static bool classof(const ConstantExpr *CE) { 240 return CE->getOpcode() == Instruction::ExtractValue; 241 } classof(const Value * V)242 static bool classof(const Value *V) { 243 return isa<ConstantExpr>(V) && classof(cast<ConstantExpr>(V)); 244 } 245 }; 246 247 /// InsertValueConstantExpr - This class is private to 248 /// Constants.cpp, and is used behind the scenes to implement 249 /// insertvalue constant exprs. 250 class InsertValueConstantExpr final : public ConstantExpr { 251 public: InsertValueConstantExpr(Constant * Agg,Constant * Val,ArrayRef<unsigned> IdxList,Type * DestTy)252 InsertValueConstantExpr(Constant *Agg, Constant *Val, 253 ArrayRef<unsigned> IdxList, Type *DestTy) 254 : ConstantExpr(DestTy, Instruction::InsertValue, &Op<0>(), 2), 255 Indices(IdxList.begin(), IdxList.end()) { 256 Op<0>() = Agg; 257 Op<1>() = Val; 258 } 259 260 // allocate space for exactly one operand new(size_t s)261 void *operator new(size_t s) { 262 return User::operator new(s, 2); 263 } 264 265 /// Indices - These identify the position for the insertion. 266 const SmallVector<unsigned, 4> Indices; 267 268 /// Transparently provide more efficient getOperand methods. 269 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); 270 classof(const ConstantExpr * CE)271 static bool classof(const ConstantExpr *CE) { 272 return CE->getOpcode() == Instruction::InsertValue; 273 } classof(const Value * V)274 static bool classof(const Value *V) { 275 return isa<ConstantExpr>(V) && classof(cast<ConstantExpr>(V)); 276 } 277 }; 278 279 /// GetElementPtrConstantExpr - This class is private to Constants.cpp, and is 280 /// used behind the scenes to implement getelementpr constant exprs. 281 class GetElementPtrConstantExpr final : public ConstantExpr { 282 Type *SrcElementTy; 283 Type *ResElementTy; 284 285 GetElementPtrConstantExpr(Type *SrcElementTy, Constant *C, 286 ArrayRef<Constant *> IdxList, Type *DestTy); 287 288 public: Create(Type * SrcElementTy,Constant * C,ArrayRef<Constant * > IdxList,Type * DestTy,unsigned Flags)289 static GetElementPtrConstantExpr *Create(Type *SrcElementTy, Constant *C, 290 ArrayRef<Constant *> IdxList, 291 Type *DestTy, unsigned Flags) { 292 GetElementPtrConstantExpr *Result = new (IdxList.size() + 1) 293 GetElementPtrConstantExpr(SrcElementTy, C, IdxList, DestTy); 294 Result->SubclassOptionalData = Flags; 295 return Result; 296 } 297 298 Type *getSourceElementType() const; 299 Type *getResultElementType() const; 300 301 /// Transparently provide more efficient getOperand methods. 302 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); 303 classof(const ConstantExpr * CE)304 static bool classof(const ConstantExpr *CE) { 305 return CE->getOpcode() == Instruction::GetElementPtr; 306 } classof(const Value * V)307 static bool classof(const Value *V) { 308 return isa<ConstantExpr>(V) && classof(cast<ConstantExpr>(V)); 309 } 310 }; 311 312 // CompareConstantExpr - This class is private to Constants.cpp, and is used 313 // behind the scenes to implement ICmp and FCmp constant expressions. This is 314 // needed in order to store the predicate value for these instructions. 315 class CompareConstantExpr final : public ConstantExpr { 316 public: 317 unsigned short predicate; CompareConstantExpr(Type * ty,Instruction::OtherOps opc,unsigned short pred,Constant * LHS,Constant * RHS)318 CompareConstantExpr(Type *ty, Instruction::OtherOps opc, 319 unsigned short pred, Constant* LHS, Constant* RHS) 320 : ConstantExpr(ty, opc, &Op<0>(), 2), predicate(pred) { 321 Op<0>() = LHS; 322 Op<1>() = RHS; 323 } 324 325 // allocate space for exactly two operands new(size_t s)326 void *operator new(size_t s) { 327 return User::operator new(s, 2); 328 } 329 330 /// Transparently provide more efficient getOperand methods. 331 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); 332 classof(const ConstantExpr * CE)333 static bool classof(const ConstantExpr *CE) { 334 return CE->getOpcode() == Instruction::ICmp || 335 CE->getOpcode() == Instruction::FCmp; 336 } classof(const Value * V)337 static bool classof(const Value *V) { 338 return isa<ConstantExpr>(V) && classof(cast<ConstantExpr>(V)); 339 } 340 }; 341 342 template <> 343 struct OperandTraits<UnaryConstantExpr> 344 : public FixedNumOperandTraits<UnaryConstantExpr, 1> {}; 345 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(UnaryConstantExpr, Value) 346 347 template <> 348 struct OperandTraits<BinaryConstantExpr> 349 : public FixedNumOperandTraits<BinaryConstantExpr, 2> {}; 350 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(BinaryConstantExpr, Value) 351 352 template <> 353 struct OperandTraits<SelectConstantExpr> 354 : public FixedNumOperandTraits<SelectConstantExpr, 3> {}; 355 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(SelectConstantExpr, Value) 356 357 template <> 358 struct OperandTraits<ExtractElementConstantExpr> 359 : public FixedNumOperandTraits<ExtractElementConstantExpr, 2> {}; 360 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ExtractElementConstantExpr, Value) 361 362 template <> 363 struct OperandTraits<InsertElementConstantExpr> 364 : public FixedNumOperandTraits<InsertElementConstantExpr, 3> {}; 365 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(InsertElementConstantExpr, Value) 366 367 template <> 368 struct OperandTraits<ShuffleVectorConstantExpr> 369 : public FixedNumOperandTraits<ShuffleVectorConstantExpr, 2> {}; 370 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ShuffleVectorConstantExpr, Value) 371 372 template <> 373 struct OperandTraits<ExtractValueConstantExpr> 374 : public FixedNumOperandTraits<ExtractValueConstantExpr, 1> {}; 375 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ExtractValueConstantExpr, Value) 376 377 template <> 378 struct OperandTraits<InsertValueConstantExpr> 379 : public FixedNumOperandTraits<InsertValueConstantExpr, 2> {}; 380 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(InsertValueConstantExpr, Value) 381 382 template <> 383 struct OperandTraits<GetElementPtrConstantExpr> 384 : public VariadicOperandTraits<GetElementPtrConstantExpr, 1> {}; 385 386 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(GetElementPtrConstantExpr, Value) 387 388 template <> 389 struct OperandTraits<CompareConstantExpr> 390 : public FixedNumOperandTraits<CompareConstantExpr, 2> {}; 391 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(CompareConstantExpr, Value) 392 393 template <class ConstantClass> struct ConstantAggrKeyType; 394 struct InlineAsmKeyType; 395 struct ConstantExprKeyType; 396 397 template <class ConstantClass> struct ConstantInfo; 398 template <> struct ConstantInfo<ConstantExpr> { 399 using ValType = ConstantExprKeyType; 400 using TypeClass = Type; 401 }; 402 template <> struct ConstantInfo<InlineAsm> { 403 using ValType = InlineAsmKeyType; 404 using TypeClass = PointerType; 405 }; 406 template <> struct ConstantInfo<ConstantArray> { 407 using ValType = ConstantAggrKeyType<ConstantArray>; 408 using TypeClass = ArrayType; 409 }; 410 template <> struct ConstantInfo<ConstantStruct> { 411 using ValType = ConstantAggrKeyType<ConstantStruct>; 412 using TypeClass = StructType; 413 }; 414 template <> struct ConstantInfo<ConstantVector> { 415 using ValType = ConstantAggrKeyType<ConstantVector>; 416 using TypeClass = VectorType; 417 }; 418 419 template <class ConstantClass> struct ConstantAggrKeyType { 420 ArrayRef<Constant *> Operands; 421 422 ConstantAggrKeyType(ArrayRef<Constant *> Operands) : Operands(Operands) {} 423 424 ConstantAggrKeyType(ArrayRef<Constant *> Operands, const ConstantClass *) 425 : Operands(Operands) {} 426 427 ConstantAggrKeyType(const ConstantClass *C, 428 SmallVectorImpl<Constant *> &Storage) { 429 assert(Storage.empty() && "Expected empty storage"); 430 for (unsigned I = 0, E = C->getNumOperands(); I != E; ++I) 431 Storage.push_back(C->getOperand(I)); 432 Operands = Storage; 433 } 434 435 bool operator==(const ConstantAggrKeyType &X) const { 436 return Operands == X.Operands; 437 } 438 439 bool operator==(const ConstantClass *C) const { 440 if (Operands.size() != C->getNumOperands()) 441 return false; 442 for (unsigned I = 0, E = Operands.size(); I != E; ++I) 443 if (Operands[I] != C->getOperand(I)) 444 return false; 445 return true; 446 } 447 448 unsigned getHash() const { 449 return hash_combine_range(Operands.begin(), Operands.end()); 450 } 451 452 using TypeClass = typename ConstantInfo<ConstantClass>::TypeClass; 453 454 ConstantClass *create(TypeClass *Ty) const { 455 return new (Operands.size()) ConstantClass(Ty, Operands); 456 } 457 }; 458 459 struct InlineAsmKeyType { 460 StringRef AsmString; 461 StringRef Constraints; 462 FunctionType *FTy; 463 bool HasSideEffects; 464 bool IsAlignStack; 465 InlineAsm::AsmDialect AsmDialect; 466 bool CanThrow; 467 468 InlineAsmKeyType(StringRef AsmString, StringRef Constraints, 469 FunctionType *FTy, bool HasSideEffects, bool IsAlignStack, 470 InlineAsm::AsmDialect AsmDialect, bool canThrow) 471 : AsmString(AsmString), Constraints(Constraints), FTy(FTy), 472 HasSideEffects(HasSideEffects), IsAlignStack(IsAlignStack), 473 AsmDialect(AsmDialect), CanThrow(canThrow) {} 474 475 InlineAsmKeyType(const InlineAsm *Asm, SmallVectorImpl<Constant *> &) 476 : AsmString(Asm->getAsmString()), Constraints(Asm->getConstraintString()), 477 FTy(Asm->getFunctionType()), HasSideEffects(Asm->hasSideEffects()), 478 IsAlignStack(Asm->isAlignStack()), AsmDialect(Asm->getDialect()), 479 CanThrow(Asm->canThrow()) {} 480 481 bool operator==(const InlineAsmKeyType &X) const { 482 return HasSideEffects == X.HasSideEffects && 483 IsAlignStack == X.IsAlignStack && AsmDialect == X.AsmDialect && 484 AsmString == X.AsmString && Constraints == X.Constraints && 485 FTy == X.FTy && CanThrow == X.CanThrow; 486 } 487 488 bool operator==(const InlineAsm *Asm) const { 489 return HasSideEffects == Asm->hasSideEffects() && 490 IsAlignStack == Asm->isAlignStack() && 491 AsmDialect == Asm->getDialect() && 492 AsmString == Asm->getAsmString() && 493 Constraints == Asm->getConstraintString() && 494 FTy == Asm->getFunctionType() && CanThrow == Asm->canThrow(); 495 } 496 497 unsigned getHash() const { 498 return hash_combine(AsmString, Constraints, HasSideEffects, IsAlignStack, 499 AsmDialect, FTy, CanThrow); 500 } 501 502 using TypeClass = ConstantInfo<InlineAsm>::TypeClass; 503 504 InlineAsm *create(TypeClass *Ty) const { 505 assert(PointerType::getUnqual(FTy) == Ty); 506 return new InlineAsm(FTy, std::string(AsmString), std::string(Constraints), 507 HasSideEffects, IsAlignStack, AsmDialect, CanThrow); 508 } 509 }; 510 511 struct ConstantExprKeyType { 512 private: 513 uint8_t Opcode; 514 uint8_t SubclassOptionalData; 515 uint16_t SubclassData; 516 ArrayRef<Constant *> Ops; 517 ArrayRef<unsigned> Indexes; 518 ArrayRef<int> ShuffleMask; 519 Type *ExplicitTy; 520 521 static ArrayRef<int> getShuffleMaskIfValid(const ConstantExpr *CE) { 522 if (CE->getOpcode() == Instruction::ShuffleVector) 523 return CE->getShuffleMask(); 524 return None; 525 } 526 527 static ArrayRef<unsigned> getIndicesIfValid(const ConstantExpr *CE) { 528 if (CE->hasIndices()) 529 return CE->getIndices(); 530 return None; 531 } 532 533 static Type *getSourceElementTypeIfValid(const ConstantExpr *CE) { 534 if (auto *GEPCE = dyn_cast<GetElementPtrConstantExpr>(CE)) 535 return GEPCE->getSourceElementType(); 536 return nullptr; 537 } 538 539 public: 540 ConstantExprKeyType(unsigned Opcode, ArrayRef<Constant *> Ops, 541 unsigned short SubclassData = 0, 542 unsigned short SubclassOptionalData = 0, 543 ArrayRef<unsigned> Indexes = None, 544 ArrayRef<int> ShuffleMask = None, 545 Type *ExplicitTy = nullptr) 546 : Opcode(Opcode), SubclassOptionalData(SubclassOptionalData), 547 SubclassData(SubclassData), Ops(Ops), Indexes(Indexes), 548 ShuffleMask(ShuffleMask), ExplicitTy(ExplicitTy) {} 549 550 ConstantExprKeyType(ArrayRef<Constant *> Operands, const ConstantExpr *CE) 551 : Opcode(CE->getOpcode()), 552 SubclassOptionalData(CE->getRawSubclassOptionalData()), 553 SubclassData(CE->isCompare() ? CE->getPredicate() : 0), Ops(Operands), 554 Indexes(getIndicesIfValid(CE)), ShuffleMask(getShuffleMaskIfValid(CE)), 555 ExplicitTy(getSourceElementTypeIfValid(CE)) {} 556 557 ConstantExprKeyType(const ConstantExpr *CE, 558 SmallVectorImpl<Constant *> &Storage) 559 : Opcode(CE->getOpcode()), 560 SubclassOptionalData(CE->getRawSubclassOptionalData()), 561 SubclassData(CE->isCompare() ? CE->getPredicate() : 0), 562 Indexes(getIndicesIfValid(CE)), ShuffleMask(getShuffleMaskIfValid(CE)), 563 ExplicitTy(getSourceElementTypeIfValid(CE)) { 564 assert(Storage.empty() && "Expected empty storage"); 565 for (unsigned I = 0, E = CE->getNumOperands(); I != E; ++I) 566 Storage.push_back(CE->getOperand(I)); 567 Ops = Storage; 568 } 569 570 bool operator==(const ConstantExprKeyType &X) const { 571 return Opcode == X.Opcode && SubclassData == X.SubclassData && 572 SubclassOptionalData == X.SubclassOptionalData && Ops == X.Ops && 573 Indexes == X.Indexes && ShuffleMask == X.ShuffleMask && 574 ExplicitTy == X.ExplicitTy; 575 } 576 577 bool operator==(const ConstantExpr *CE) const { 578 if (Opcode != CE->getOpcode()) 579 return false; 580 if (SubclassOptionalData != CE->getRawSubclassOptionalData()) 581 return false; 582 if (Ops.size() != CE->getNumOperands()) 583 return false; 584 if (SubclassData != (CE->isCompare() ? CE->getPredicate() : 0)) 585 return false; 586 for (unsigned I = 0, E = Ops.size(); I != E; ++I) 587 if (Ops[I] != CE->getOperand(I)) 588 return false; 589 if (Indexes != getIndicesIfValid(CE)) 590 return false; 591 if (ShuffleMask != getShuffleMaskIfValid(CE)) 592 return false; 593 if (ExplicitTy != getSourceElementTypeIfValid(CE)) 594 return false; 595 return true; 596 } 597 598 unsigned getHash() const { 599 return hash_combine( 600 Opcode, SubclassOptionalData, SubclassData, 601 hash_combine_range(Ops.begin(), Ops.end()), 602 hash_combine_range(Indexes.begin(), Indexes.end()), 603 hash_combine_range(ShuffleMask.begin(), ShuffleMask.end()), ExplicitTy); 604 } 605 606 using TypeClass = ConstantInfo<ConstantExpr>::TypeClass; 607 608 ConstantExpr *create(TypeClass *Ty) const { 609 switch (Opcode) { 610 default: 611 if (Instruction::isCast(Opcode) || 612 (Opcode >= Instruction::UnaryOpsBegin && 613 Opcode < Instruction::UnaryOpsEnd)) 614 return new UnaryConstantExpr(Opcode, Ops[0], Ty); 615 if ((Opcode >= Instruction::BinaryOpsBegin && 616 Opcode < Instruction::BinaryOpsEnd)) 617 return new BinaryConstantExpr(Opcode, Ops[0], Ops[1], 618 SubclassOptionalData); 619 llvm_unreachable("Invalid ConstantExpr!"); 620 case Instruction::Select: 621 return new SelectConstantExpr(Ops[0], Ops[1], Ops[2]); 622 case Instruction::ExtractElement: 623 return new ExtractElementConstantExpr(Ops[0], Ops[1]); 624 case Instruction::InsertElement: 625 return new InsertElementConstantExpr(Ops[0], Ops[1], Ops[2]); 626 case Instruction::ShuffleVector: 627 return new ShuffleVectorConstantExpr(Ops[0], Ops[1], ShuffleMask); 628 case Instruction::InsertValue: 629 return new InsertValueConstantExpr(Ops[0], Ops[1], Indexes, Ty); 630 case Instruction::ExtractValue: 631 return new ExtractValueConstantExpr(Ops[0], Indexes, Ty); 632 case Instruction::GetElementPtr: 633 return GetElementPtrConstantExpr::Create(ExplicitTy, Ops[0], Ops.slice(1), 634 Ty, SubclassOptionalData); 635 case Instruction::ICmp: 636 return new CompareConstantExpr(Ty, Instruction::ICmp, SubclassData, 637 Ops[0], Ops[1]); 638 case Instruction::FCmp: 639 return new CompareConstantExpr(Ty, Instruction::FCmp, SubclassData, 640 Ops[0], Ops[1]); 641 } 642 } 643 }; 644 645 // Free memory for a given constant. Assumes the constant has already been 646 // removed from all relevant maps. 647 void deleteConstant(Constant *C); 648 649 template <class ConstantClass> class ConstantUniqueMap { 650 public: 651 using ValType = typename ConstantInfo<ConstantClass>::ValType; 652 using TypeClass = typename ConstantInfo<ConstantClass>::TypeClass; 653 using LookupKey = std::pair<TypeClass *, ValType>; 654 655 /// Key and hash together, so that we compute the hash only once and reuse it. 656 using LookupKeyHashed = std::pair<unsigned, LookupKey>; 657 658 private: 659 struct MapInfo { 660 using ConstantClassInfo = DenseMapInfo<ConstantClass *>; 661 662 static inline ConstantClass *getEmptyKey() { 663 return ConstantClassInfo::getEmptyKey(); 664 } 665 666 static inline ConstantClass *getTombstoneKey() { 667 return ConstantClassInfo::getTombstoneKey(); 668 } 669 670 static unsigned getHashValue(const ConstantClass *CP) { 671 SmallVector<Constant *, 32> Storage; 672 return getHashValue(LookupKey(CP->getType(), ValType(CP, Storage))); 673 } 674 675 static bool isEqual(const ConstantClass *LHS, const ConstantClass *RHS) { 676 return LHS == RHS; 677 } 678 679 static unsigned getHashValue(const LookupKey &Val) { 680 return hash_combine(Val.first, Val.second.getHash()); 681 } 682 683 static unsigned getHashValue(const LookupKeyHashed &Val) { 684 return Val.first; 685 } 686 687 static bool isEqual(const LookupKey &LHS, const ConstantClass *RHS) { 688 if (RHS == getEmptyKey() || RHS == getTombstoneKey()) 689 return false; 690 if (LHS.first != RHS->getType()) 691 return false; 692 return LHS.second == RHS; 693 } 694 695 static bool isEqual(const LookupKeyHashed &LHS, const ConstantClass *RHS) { 696 return isEqual(LHS.second, RHS); 697 } 698 }; 699 700 public: 701 using MapTy = DenseSet<ConstantClass *, MapInfo>; 702 703 private: 704 MapTy Map; 705 706 public: 707 typename MapTy::iterator begin() { return Map.begin(); } 708 typename MapTy::iterator end() { return Map.end(); } 709 710 void freeConstants() { 711 for (auto &I : Map) 712 deleteConstant(I); 713 } 714 715 private: 716 ConstantClass *create(TypeClass *Ty, ValType V, LookupKeyHashed &HashKey) { 717 ConstantClass *Result = V.create(Ty); 718 719 assert(Result->getType() == Ty && "Type specified is not correct!"); 720 Map.insert_as(Result, HashKey); 721 722 return Result; 723 } 724 725 public: 726 /// Return the specified constant from the map, creating it if necessary. 727 ConstantClass *getOrCreate(TypeClass *Ty, ValType V) { 728 LookupKey Key(Ty, V); 729 /// Hash once, and reuse it for the lookup and the insertion if needed. 730 LookupKeyHashed Lookup(MapInfo::getHashValue(Key), Key); 731 732 ConstantClass *Result = nullptr; 733 734 auto I = Map.find_as(Lookup); 735 if (I == Map.end()) 736 Result = create(Ty, V, Lookup); 737 else 738 Result = *I; 739 assert(Result && "Unexpected nullptr"); 740 741 return Result; 742 } 743 744 /// Remove this constant from the map 745 void remove(ConstantClass *CP) { 746 typename MapTy::iterator I = Map.find(CP); 747 assert(I != Map.end() && "Constant not found in constant table!"); 748 assert(*I == CP && "Didn't find correct element?"); 749 Map.erase(I); 750 } 751 752 ConstantClass *replaceOperandsInPlace(ArrayRef<Constant *> Operands, 753 ConstantClass *CP, Value *From, 754 Constant *To, unsigned NumUpdated = 0, 755 unsigned OperandNo = ~0u) { 756 LookupKey Key(CP->getType(), ValType(Operands, CP)); 757 /// Hash once, and reuse it for the lookup and the insertion if needed. 758 LookupKeyHashed Lookup(MapInfo::getHashValue(Key), Key); 759 760 auto ItMap = Map.find_as(Lookup); 761 if (ItMap != Map.end()) 762 return *ItMap; 763 764 // Update to the new value. Optimize for the case when we have a single 765 // operand that we're changing, but handle bulk updates efficiently. 766 remove(CP); 767 if (NumUpdated == 1) { 768 assert(OperandNo < CP->getNumOperands() && "Invalid index"); 769 assert(CP->getOperand(OperandNo) != To && "I didn't contain From!"); 770 CP->setOperand(OperandNo, To); 771 } else { 772 for (unsigned I = 0, E = CP->getNumOperands(); I != E; ++I) 773 if (CP->getOperand(I) == From) 774 CP->setOperand(I, To); 775 } 776 Map.insert_as(CP, Lookup); 777 return nullptr; 778 } 779 780 void dump() const { 781 LLVM_DEBUG(dbgs() << "Constant.cpp: ConstantUniqueMap\n"); 782 } 783 }; 784 785 template <> inline void ConstantUniqueMap<InlineAsm>::freeConstants() { 786 for (auto &I : Map) 787 delete I; 788 } 789 790 } // end namespace llvm 791 792 #endif // LLVM_LIB_IR_CONSTANTSCONTEXT_H 793