1 //===- llvm/Value.h - Definition of the Value class -------------*- 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 declares the Value class. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_IR_VALUE_H 14 #define LLVM_IR_VALUE_H 15 16 #include "llvm-c/Types.h" 17 #include "llvm/ADT/STLExtras.h" 18 #include "llvm/ADT/iterator_range.h" 19 #include "llvm/IR/Use.h" 20 #include "llvm/Support/Alignment.h" 21 #include "llvm/Support/CBindingWrapping.h" 22 #include "llvm/Support/Casting.h" 23 #include <cassert> 24 #include <iterator> 25 #include <memory> 26 27 namespace llvm { 28 29 class APInt; 30 class Argument; 31 class BasicBlock; 32 class Constant; 33 class ConstantData; 34 class ConstantAggregate; 35 class DataLayout; 36 class Function; 37 class GlobalAlias; 38 class GlobalIFunc; 39 class GlobalIndirectSymbol; 40 class GlobalObject; 41 class GlobalValue; 42 class GlobalVariable; 43 class InlineAsm; 44 class Instruction; 45 class LLVMContext; 46 class Module; 47 class ModuleSlotTracker; 48 class raw_ostream; 49 template<typename ValueTy> class StringMapEntry; 50 class StringRef; 51 class Twine; 52 class Type; 53 class User; 54 55 using ValueName = StringMapEntry<Value *>; 56 57 //===----------------------------------------------------------------------===// 58 // Value Class 59 //===----------------------------------------------------------------------===// 60 61 /// LLVM Value Representation 62 /// 63 /// This is a very important LLVM class. It is the base class of all values 64 /// computed by a program that may be used as operands to other values. Value is 65 /// the super class of other important classes such as Instruction and Function. 66 /// All Values have a Type. Type is not a subclass of Value. Some values can 67 /// have a name and they belong to some Module. Setting the name on the Value 68 /// automatically updates the module's symbol table. 69 /// 70 /// Every value has a "use list" that keeps track of which other Values are 71 /// using this Value. A Value can also have an arbitrary number of ValueHandle 72 /// objects that watch it and listen to RAUW and Destroy events. See 73 /// llvm/IR/ValueHandle.h for details. 74 class Value { 75 // The least-significant bit of the first word of Value *must* be zero: 76 // http://www.llvm.org/docs/ProgrammersManual.html#the-waymarking-algorithm 77 Type *VTy; 78 Use *UseList; 79 80 friend class ValueAsMetadata; // Allow access to IsUsedByMD. 81 friend class ValueHandleBase; 82 83 const unsigned char SubclassID; // Subclass identifier (for isa/dyn_cast) 84 unsigned char HasValueHandle : 1; // Has a ValueHandle pointing to this? 85 86 protected: 87 /// Hold subclass data that can be dropped. 88 /// 89 /// This member is similar to SubclassData, however it is for holding 90 /// information which may be used to aid optimization, but which may be 91 /// cleared to zero without affecting conservative interpretation. 92 unsigned char SubclassOptionalData : 7; 93 94 private: 95 /// Hold arbitrary subclass data. 96 /// 97 /// This member is defined by this class, but is not used for anything. 98 /// Subclasses can use it to hold whatever state they find useful. This 99 /// field is initialized to zero by the ctor. 100 unsigned short SubclassData; 101 102 protected: 103 /// The number of operands in the subclass. 104 /// 105 /// This member is defined by this class, but not used for anything. 106 /// Subclasses can use it to store their number of operands, if they have 107 /// any. 108 /// 109 /// This is stored here to save space in User on 64-bit hosts. Since most 110 /// instances of Value have operands, 32-bit hosts aren't significantly 111 /// affected. 112 /// 113 /// Note, this should *NOT* be used directly by any class other than User. 114 /// User uses this value to find the Use list. 115 enum : unsigned { NumUserOperandsBits = 28 }; 116 unsigned NumUserOperands : NumUserOperandsBits; 117 118 // Use the same type as the bitfield above so that MSVC will pack them. 119 unsigned IsUsedByMD : 1; 120 unsigned HasName : 1; 121 unsigned HasHungOffUses : 1; 122 unsigned HasDescriptor : 1; 123 124 private: 125 template <typename UseT> // UseT == 'Use' or 'const Use' 126 class use_iterator_impl 127 : public std::iterator<std::forward_iterator_tag, UseT *> { 128 friend class Value; 129 130 UseT *U; 131 132 explicit use_iterator_impl(UseT *u) : U(u) {} 133 134 public: 135 use_iterator_impl() : U() {} 136 137 bool operator==(const use_iterator_impl &x) const { return U == x.U; } 138 bool operator!=(const use_iterator_impl &x) const { return !operator==(x); } 139 140 use_iterator_impl &operator++() { // Preincrement 141 assert(U && "Cannot increment end iterator!"); 142 U = U->getNext(); 143 return *this; 144 } 145 146 use_iterator_impl operator++(int) { // Postincrement 147 auto tmp = *this; 148 ++*this; 149 return tmp; 150 } 151 152 UseT &operator*() const { 153 assert(U && "Cannot dereference end iterator!"); 154 return *U; 155 } 156 157 UseT *operator->() const { return &operator*(); } 158 159 operator use_iterator_impl<const UseT>() const { 160 return use_iterator_impl<const UseT>(U); 161 } 162 }; 163 164 template <typename UserTy> // UserTy == 'User' or 'const User' 165 class user_iterator_impl 166 : public std::iterator<std::forward_iterator_tag, UserTy *> { 167 use_iterator_impl<Use> UI; 168 explicit user_iterator_impl(Use *U) : UI(U) {} 169 friend class Value; 170 171 public: 172 user_iterator_impl() = default; 173 174 bool operator==(const user_iterator_impl &x) const { return UI == x.UI; } 175 bool operator!=(const user_iterator_impl &x) const { return !operator==(x); } 176 177 /// Returns true if this iterator is equal to user_end() on the value. 178 bool atEnd() const { return *this == user_iterator_impl(); } 179 180 user_iterator_impl &operator++() { // Preincrement 181 ++UI; 182 return *this; 183 } 184 185 user_iterator_impl operator++(int) { // Postincrement 186 auto tmp = *this; 187 ++*this; 188 return tmp; 189 } 190 191 // Retrieve a pointer to the current User. 192 UserTy *operator*() const { 193 return UI->getUser(); 194 } 195 196 UserTy *operator->() const { return operator*(); } 197 198 operator user_iterator_impl<const UserTy>() const { 199 return user_iterator_impl<const UserTy>(*UI); 200 } 201 202 Use &getUse() const { return *UI; } 203 }; 204 205 protected: 206 Value(Type *Ty, unsigned scid); 207 208 /// Value's destructor should be virtual by design, but that would require 209 /// that Value and all of its subclasses have a vtable that effectively 210 /// duplicates the information in the value ID. As a size optimization, the 211 /// destructor has been protected, and the caller should manually call 212 /// deleteValue. 213 ~Value(); // Use deleteValue() to delete a generic Value. 214 215 public: 216 Value(const Value &) = delete; 217 Value &operator=(const Value &) = delete; 218 219 /// Delete a pointer to a generic Value. 220 void deleteValue(); 221 222 /// Support for debugging, callable in GDB: V->dump() 223 void dump() const; 224 225 /// Implement operator<< on Value. 226 /// @{ 227 void print(raw_ostream &O, bool IsForDebug = false) const; 228 void print(raw_ostream &O, ModuleSlotTracker &MST, 229 bool IsForDebug = false) const; 230 /// @} 231 232 /// Print the name of this Value out to the specified raw_ostream. 233 /// 234 /// This is useful when you just want to print 'int %reg126', not the 235 /// instruction that generated it. If you specify a Module for context, then 236 /// even constanst get pretty-printed; for example, the type of a null 237 /// pointer is printed symbolically. 238 /// @{ 239 void printAsOperand(raw_ostream &O, bool PrintType = true, 240 const Module *M = nullptr) const; 241 void printAsOperand(raw_ostream &O, bool PrintType, 242 ModuleSlotTracker &MST) const; 243 /// @} 244 245 /// All values are typed, get the type of this value. 246 Type *getType() const { return VTy; } 247 248 /// All values hold a context through their type. 249 LLVMContext &getContext() const; 250 251 // All values can potentially be named. 252 bool hasName() const { return HasName; } 253 ValueName *getValueName() const; 254 void setValueName(ValueName *VN); 255 256 private: 257 void destroyValueName(); 258 enum class ReplaceMetadataUses { No, Yes }; 259 void doRAUW(Value *New, ReplaceMetadataUses); 260 void setNameImpl(const Twine &Name); 261 262 public: 263 /// Return a constant reference to the value's name. 264 /// 265 /// This guaranteed to return the same reference as long as the value is not 266 /// modified. If the value has a name, this does a hashtable lookup, so it's 267 /// not free. 268 StringRef getName() const; 269 270 /// Change the name of the value. 271 /// 272 /// Choose a new unique name if the provided name is taken. 273 /// 274 /// \param Name The new name; or "" if the value's name should be removed. 275 void setName(const Twine &Name); 276 277 /// Transfer the name from V to this value. 278 /// 279 /// After taking V's name, sets V's name to empty. 280 /// 281 /// \note It is an error to call V->takeName(V). 282 void takeName(Value *V); 283 284 /// Change all uses of this to point to a new Value. 285 /// 286 /// Go through the uses list for this definition and make each use point to 287 /// "V" instead of "this". After this completes, 'this's use list is 288 /// guaranteed to be empty. 289 void replaceAllUsesWith(Value *V); 290 291 /// Change non-metadata uses of this to point to a new Value. 292 /// 293 /// Go through the uses list for this definition and make each use point to 294 /// "V" instead of "this". This function skips metadata entries in the list. 295 void replaceNonMetadataUsesWith(Value *V); 296 297 /// Go through the uses list for this definition and make each use point 298 /// to "V" if the callback ShouldReplace returns true for the given Use. 299 /// Unlike replaceAllUsesWith() this function does not support basic block 300 /// values or constant users. 301 void replaceUsesWithIf(Value *New, 302 llvm::function_ref<bool(Use &U)> ShouldReplace) { 303 assert(New && "Value::replaceUsesWithIf(<null>) is invalid!"); 304 assert(New->getType() == getType() && 305 "replaceUses of value with new value of different type!"); 306 307 for (use_iterator UI = use_begin(), E = use_end(); UI != E;) { 308 Use &U = *UI; 309 ++UI; 310 if (!ShouldReplace(U)) 311 continue; 312 U.set(New); 313 } 314 } 315 316 /// replaceUsesOutsideBlock - Go through the uses list for this definition and 317 /// make each use point to "V" instead of "this" when the use is outside the 318 /// block. 'This's use list is expected to have at least one element. 319 /// Unlike replaceAllUsesWith() this function does not support basic block 320 /// values or constant users. 321 void replaceUsesOutsideBlock(Value *V, BasicBlock *BB); 322 323 //---------------------------------------------------------------------- 324 // Methods for handling the chain of uses of this Value. 325 // 326 // Materializing a function can introduce new uses, so these methods come in 327 // two variants: 328 // The methods that start with materialized_ check the uses that are 329 // currently known given which functions are materialized. Be very careful 330 // when using them since you might not get all uses. 331 // The methods that don't start with materialized_ assert that modules is 332 // fully materialized. 333 void assertModuleIsMaterializedImpl() const; 334 // This indirection exists so we can keep assertModuleIsMaterializedImpl() 335 // around in release builds of Value.cpp to be linked with other code built 336 // in debug mode. But this avoids calling it in any of the release built code. 337 void assertModuleIsMaterialized() const { 338 #ifndef NDEBUG 339 assertModuleIsMaterializedImpl(); 340 #endif 341 } 342 343 bool use_empty() const { 344 assertModuleIsMaterialized(); 345 return UseList == nullptr; 346 } 347 348 bool materialized_use_empty() const { 349 return UseList == nullptr; 350 } 351 352 using use_iterator = use_iterator_impl<Use>; 353 using const_use_iterator = use_iterator_impl<const Use>; 354 355 use_iterator materialized_use_begin() { return use_iterator(UseList); } 356 const_use_iterator materialized_use_begin() const { 357 return const_use_iterator(UseList); 358 } 359 use_iterator use_begin() { 360 assertModuleIsMaterialized(); 361 return materialized_use_begin(); 362 } 363 const_use_iterator use_begin() const { 364 assertModuleIsMaterialized(); 365 return materialized_use_begin(); 366 } 367 use_iterator use_end() { return use_iterator(); } 368 const_use_iterator use_end() const { return const_use_iterator(); } 369 iterator_range<use_iterator> materialized_uses() { 370 return make_range(materialized_use_begin(), use_end()); 371 } 372 iterator_range<const_use_iterator> materialized_uses() const { 373 return make_range(materialized_use_begin(), use_end()); 374 } 375 iterator_range<use_iterator> uses() { 376 assertModuleIsMaterialized(); 377 return materialized_uses(); 378 } 379 iterator_range<const_use_iterator> uses() const { 380 assertModuleIsMaterialized(); 381 return materialized_uses(); 382 } 383 384 bool user_empty() const { 385 assertModuleIsMaterialized(); 386 return UseList == nullptr; 387 } 388 389 using user_iterator = user_iterator_impl<User>; 390 using const_user_iterator = user_iterator_impl<const User>; 391 392 user_iterator materialized_user_begin() { return user_iterator(UseList); } 393 const_user_iterator materialized_user_begin() const { 394 return const_user_iterator(UseList); 395 } 396 user_iterator user_begin() { 397 assertModuleIsMaterialized(); 398 return materialized_user_begin(); 399 } 400 const_user_iterator user_begin() const { 401 assertModuleIsMaterialized(); 402 return materialized_user_begin(); 403 } 404 user_iterator user_end() { return user_iterator(); } 405 const_user_iterator user_end() const { return const_user_iterator(); } 406 User *user_back() { 407 assertModuleIsMaterialized(); 408 return *materialized_user_begin(); 409 } 410 const User *user_back() const { 411 assertModuleIsMaterialized(); 412 return *materialized_user_begin(); 413 } 414 iterator_range<user_iterator> materialized_users() { 415 return make_range(materialized_user_begin(), user_end()); 416 } 417 iterator_range<const_user_iterator> materialized_users() const { 418 return make_range(materialized_user_begin(), user_end()); 419 } 420 iterator_range<user_iterator> users() { 421 assertModuleIsMaterialized(); 422 return materialized_users(); 423 } 424 iterator_range<const_user_iterator> users() const { 425 assertModuleIsMaterialized(); 426 return materialized_users(); 427 } 428 429 /// Return true if there is exactly one user of this value. 430 /// 431 /// This is specialized because it is a common request and does not require 432 /// traversing the whole use list. 433 bool hasOneUse() const { 434 const_use_iterator I = use_begin(), E = use_end(); 435 if (I == E) return false; 436 return ++I == E; 437 } 438 439 /// Return true if this Value has exactly N users. 440 bool hasNUses(unsigned N) const; 441 442 /// Return true if this value has N users or more. 443 /// 444 /// This is logically equivalent to getNumUses() >= N. 445 bool hasNUsesOrMore(unsigned N) const; 446 447 /// Check if this value is used in the specified basic block. 448 bool isUsedInBasicBlock(const BasicBlock *BB) const; 449 450 /// This method computes the number of uses of this Value. 451 /// 452 /// This is a linear time operation. Use hasOneUse, hasNUses, or 453 /// hasNUsesOrMore to check for specific values. 454 unsigned getNumUses() const; 455 456 /// This method should only be used by the Use class. 457 void addUse(Use &U) { U.addToList(&UseList); } 458 459 /// Concrete subclass of this. 460 /// 461 /// An enumeration for keeping track of the concrete subclass of Value that 462 /// is actually instantiated. Values of this enumeration are kept in the 463 /// Value classes SubclassID field. They are used for concrete type 464 /// identification. 465 enum ValueTy { 466 #define HANDLE_VALUE(Name) Name##Val, 467 #include "llvm/IR/Value.def" 468 469 // Markers: 470 #define HANDLE_CONSTANT_MARKER(Marker, Constant) Marker = Constant##Val, 471 #include "llvm/IR/Value.def" 472 }; 473 474 /// Return an ID for the concrete type of this object. 475 /// 476 /// This is used to implement the classof checks. This should not be used 477 /// for any other purpose, as the values may change as LLVM evolves. Also, 478 /// note that for instructions, the Instruction's opcode is added to 479 /// InstructionVal. So this means three things: 480 /// # there is no value with code InstructionVal (no opcode==0). 481 /// # there are more possible values for the value type than in ValueTy enum. 482 /// # the InstructionVal enumerator must be the highest valued enumerator in 483 /// the ValueTy enum. 484 unsigned getValueID() const { 485 return SubclassID; 486 } 487 488 /// Return the raw optional flags value contained in this value. 489 /// 490 /// This should only be used when testing two Values for equivalence. 491 unsigned getRawSubclassOptionalData() const { 492 return SubclassOptionalData; 493 } 494 495 /// Clear the optional flags contained in this value. 496 void clearSubclassOptionalData() { 497 SubclassOptionalData = 0; 498 } 499 500 /// Check the optional flags for equality. 501 bool hasSameSubclassOptionalData(const Value *V) const { 502 return SubclassOptionalData == V->SubclassOptionalData; 503 } 504 505 /// Return true if there is a value handle associated with this value. 506 bool hasValueHandle() const { return HasValueHandle; } 507 508 /// Return true if there is metadata referencing this value. 509 bool isUsedByMetadata() const { return IsUsedByMD; } 510 511 /// Return true if this value is a swifterror value. 512 /// 513 /// swifterror values can be either a function argument or an alloca with a 514 /// swifterror attribute. 515 bool isSwiftError() const; 516 517 /// Strip off pointer casts, all-zero GEPs and address space casts. 518 /// 519 /// Returns the original uncasted value. If this is called on a non-pointer 520 /// value, it returns 'this'. 521 const Value *stripPointerCasts() const; 522 Value *stripPointerCasts() { 523 return const_cast<Value *>( 524 static_cast<const Value *>(this)->stripPointerCasts()); 525 } 526 527 /// Strip off pointer casts, all-zero GEPs, address space casts, and aliases. 528 /// 529 /// Returns the original uncasted value. If this is called on a non-pointer 530 /// value, it returns 'this'. 531 const Value *stripPointerCastsAndAliases() const; 532 Value *stripPointerCastsAndAliases() { 533 return const_cast<Value *>( 534 static_cast<const Value *>(this)->stripPointerCastsAndAliases()); 535 } 536 537 /// Strip off pointer casts, all-zero GEPs and address space casts 538 /// but ensures the representation of the result stays the same. 539 /// 540 /// Returns the original uncasted value with the same representation. If this 541 /// is called on a non-pointer value, it returns 'this'. 542 const Value *stripPointerCastsSameRepresentation() const; 543 Value *stripPointerCastsSameRepresentation() { 544 return const_cast<Value *>(static_cast<const Value *>(this) 545 ->stripPointerCastsSameRepresentation()); 546 } 547 548 /// Strip off pointer casts, all-zero GEPs and invariant group info. 549 /// 550 /// Returns the original uncasted value. If this is called on a non-pointer 551 /// value, it returns 'this'. This function should be used only in 552 /// Alias analysis. 553 const Value *stripPointerCastsAndInvariantGroups() const; 554 Value *stripPointerCastsAndInvariantGroups() { 555 return const_cast<Value *>(static_cast<const Value *>(this) 556 ->stripPointerCastsAndInvariantGroups()); 557 } 558 559 /// Strip off pointer casts and all-constant inbounds GEPs. 560 /// 561 /// Returns the original pointer value. If this is called on a non-pointer 562 /// value, it returns 'this'. 563 const Value *stripInBoundsConstantOffsets() const; 564 Value *stripInBoundsConstantOffsets() { 565 return const_cast<Value *>( 566 static_cast<const Value *>(this)->stripInBoundsConstantOffsets()); 567 } 568 569 /// Accumulate the constant offset this value has compared to a base pointer. 570 /// Only 'getelementptr' instructions (GEPs) with constant indices are 571 /// accumulated but other instructions, e.g., casts, are stripped away as 572 /// well. The accumulated constant offset is added to \p Offset and the base 573 /// pointer is returned. 574 /// 575 /// The APInt \p Offset has to have a bit-width equal to the IntPtr type for 576 /// the address space of 'this' pointer value, e.g., use 577 /// DataLayout::getIndexTypeSizeInBits(Ty). 578 /// 579 /// If \p AllowNonInbounds is true, constant offsets in GEPs are stripped and 580 /// accumulated even if the GEP is not "inbounds". 581 /// 582 /// If this is called on a non-pointer value, it returns 'this' and the 583 /// \p Offset is not modified. 584 /// 585 /// Note that this function will never return a nullptr. It will also never 586 /// manipulate the \p Offset in a way that would not match the difference 587 /// between the underlying value and the returned one. Thus, if no constant 588 /// offset was found, the returned value is the underlying one and \p Offset 589 /// is unchanged. 590 const Value *stripAndAccumulateConstantOffsets(const DataLayout &DL, 591 APInt &Offset, 592 bool AllowNonInbounds) const; 593 Value *stripAndAccumulateConstantOffsets(const DataLayout &DL, APInt &Offset, 594 bool AllowNonInbounds) { 595 return const_cast<Value *>( 596 static_cast<const Value *>(this)->stripAndAccumulateConstantOffsets( 597 DL, Offset, AllowNonInbounds)); 598 } 599 600 /// This is a wrapper around stripAndAccumulateConstantOffsets with the 601 /// in-bounds requirement set to false. 602 const Value *stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL, 603 APInt &Offset) const { 604 return stripAndAccumulateConstantOffsets(DL, Offset, 605 /* AllowNonInbounds */ false); 606 } 607 Value *stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL, 608 APInt &Offset) { 609 return stripAndAccumulateConstantOffsets(DL, Offset, 610 /* AllowNonInbounds */ false); 611 } 612 613 /// Strip off pointer casts and inbounds GEPs. 614 /// 615 /// Returns the original pointer value. If this is called on a non-pointer 616 /// value, it returns 'this'. 617 const Value *stripInBoundsOffsets() const; 618 Value *stripInBoundsOffsets() { 619 return const_cast<Value *>( 620 static_cast<const Value *>(this)->stripInBoundsOffsets()); 621 } 622 623 /// Returns the number of bytes known to be dereferenceable for the 624 /// pointer value. 625 /// 626 /// If CanBeNull is set by this function the pointer can either be null or be 627 /// dereferenceable up to the returned number of bytes. 628 uint64_t getPointerDereferenceableBytes(const DataLayout &DL, 629 bool &CanBeNull) const; 630 631 /// Returns an alignment of the pointer value. 632 /// 633 /// Returns an alignment which is either specified explicitly, e.g. via 634 /// align attribute of a function argument, or guaranteed by DataLayout. 635 MaybeAlign getPointerAlignment(const DataLayout &DL) const; 636 637 /// Translate PHI node to its predecessor from the given basic block. 638 /// 639 /// If this value is a PHI node with CurBB as its parent, return the value in 640 /// the PHI node corresponding to PredBB. If not, return ourself. This is 641 /// useful if you want to know the value something has in a predecessor 642 /// block. 643 const Value *DoPHITranslation(const BasicBlock *CurBB, 644 const BasicBlock *PredBB) const; 645 Value *DoPHITranslation(const BasicBlock *CurBB, const BasicBlock *PredBB) { 646 return const_cast<Value *>( 647 static_cast<const Value *>(this)->DoPHITranslation(CurBB, PredBB)); 648 } 649 650 /// The maximum alignment for instructions. 651 /// 652 /// This is the greatest alignment value supported by load, store, and alloca 653 /// instructions, and global values. 654 static const unsigned MaxAlignmentExponent = 29; 655 static const unsigned MaximumAlignment = 1u << MaxAlignmentExponent; 656 657 /// Mutate the type of this Value to be of the specified type. 658 /// 659 /// Note that this is an extremely dangerous operation which can create 660 /// completely invalid IR very easily. It is strongly recommended that you 661 /// recreate IR objects with the right types instead of mutating them in 662 /// place. 663 void mutateType(Type *Ty) { 664 VTy = Ty; 665 } 666 667 /// Sort the use-list. 668 /// 669 /// Sorts the Value's use-list by Cmp using a stable mergesort. Cmp is 670 /// expected to compare two \a Use references. 671 template <class Compare> void sortUseList(Compare Cmp); 672 673 /// Reverse the use-list. 674 void reverseUseList(); 675 676 private: 677 /// Merge two lists together. 678 /// 679 /// Merges \c L and \c R using \c Cmp. To enable stable sorts, always pushes 680 /// "equal" items from L before items from R. 681 /// 682 /// \return the first element in the list. 683 /// 684 /// \note Completely ignores \a Use::Prev (doesn't read, doesn't update). 685 template <class Compare> 686 static Use *mergeUseLists(Use *L, Use *R, Compare Cmp) { 687 Use *Merged; 688 Use **Next = &Merged; 689 690 while (true) { 691 if (!L) { 692 *Next = R; 693 break; 694 } 695 if (!R) { 696 *Next = L; 697 break; 698 } 699 if (Cmp(*R, *L)) { 700 *Next = R; 701 Next = &R->Next; 702 R = R->Next; 703 } else { 704 *Next = L; 705 Next = &L->Next; 706 L = L->Next; 707 } 708 } 709 710 return Merged; 711 } 712 713 protected: 714 unsigned short getSubclassDataFromValue() const { return SubclassData; } 715 void setValueSubclassData(unsigned short D) { SubclassData = D; } 716 }; 717 718 struct ValueDeleter { void operator()(Value *V) { V->deleteValue(); } }; 719 720 /// Use this instead of std::unique_ptr<Value> or std::unique_ptr<Instruction>. 721 /// Those don't work because Value and Instruction's destructors are protected, 722 /// aren't virtual, and won't destroy the complete object. 723 using unique_value = std::unique_ptr<Value, ValueDeleter>; 724 725 inline raw_ostream &operator<<(raw_ostream &OS, const Value &V) { 726 V.print(OS); 727 return OS; 728 } 729 730 void Use::set(Value *V) { 731 if (Val) removeFromList(); 732 Val = V; 733 if (V) V->addUse(*this); 734 } 735 736 Value *Use::operator=(Value *RHS) { 737 set(RHS); 738 return RHS; 739 } 740 741 const Use &Use::operator=(const Use &RHS) { 742 set(RHS.Val); 743 return *this; 744 } 745 746 template <class Compare> void Value::sortUseList(Compare Cmp) { 747 if (!UseList || !UseList->Next) 748 // No need to sort 0 or 1 uses. 749 return; 750 751 // Note: this function completely ignores Prev pointers until the end when 752 // they're fixed en masse. 753 754 // Create a binomial vector of sorted lists, visiting uses one at a time and 755 // merging lists as necessary. 756 const unsigned MaxSlots = 32; 757 Use *Slots[MaxSlots]; 758 759 // Collect the first use, turning it into a single-item list. 760 Use *Next = UseList->Next; 761 UseList->Next = nullptr; 762 unsigned NumSlots = 1; 763 Slots[0] = UseList; 764 765 // Collect all but the last use. 766 while (Next->Next) { 767 Use *Current = Next; 768 Next = Current->Next; 769 770 // Turn Current into a single-item list. 771 Current->Next = nullptr; 772 773 // Save Current in the first available slot, merging on collisions. 774 unsigned I; 775 for (I = 0; I < NumSlots; ++I) { 776 if (!Slots[I]) 777 break; 778 779 // Merge two lists, doubling the size of Current and emptying slot I. 780 // 781 // Since the uses in Slots[I] originally preceded those in Current, send 782 // Slots[I] in as the left parameter to maintain a stable sort. 783 Current = mergeUseLists(Slots[I], Current, Cmp); 784 Slots[I] = nullptr; 785 } 786 // Check if this is a new slot. 787 if (I == NumSlots) { 788 ++NumSlots; 789 assert(NumSlots <= MaxSlots && "Use list bigger than 2^32"); 790 } 791 792 // Found an open slot. 793 Slots[I] = Current; 794 } 795 796 // Merge all the lists together. 797 assert(Next && "Expected one more Use"); 798 assert(!Next->Next && "Expected only one Use"); 799 UseList = Next; 800 for (unsigned I = 0; I < NumSlots; ++I) 801 if (Slots[I]) 802 // Since the uses in Slots[I] originally preceded those in UseList, send 803 // Slots[I] in as the left parameter to maintain a stable sort. 804 UseList = mergeUseLists(Slots[I], UseList, Cmp); 805 806 // Fix the Prev pointers. 807 for (Use *I = UseList, **Prev = &UseList; I; I = I->Next) { 808 I->setPrev(Prev); 809 Prev = &I->Next; 810 } 811 } 812 813 // isa - Provide some specializations of isa so that we don't have to include 814 // the subtype header files to test to see if the value is a subclass... 815 // 816 template <> struct isa_impl<Constant, Value> { 817 static inline bool doit(const Value &Val) { 818 static_assert(Value::ConstantFirstVal == 0, "Val.getValueID() >= Value::ConstantFirstVal"); 819 return Val.getValueID() <= Value::ConstantLastVal; 820 } 821 }; 822 823 template <> struct isa_impl<ConstantData, Value> { 824 static inline bool doit(const Value &Val) { 825 return Val.getValueID() >= Value::ConstantDataFirstVal && 826 Val.getValueID() <= Value::ConstantDataLastVal; 827 } 828 }; 829 830 template <> struct isa_impl<ConstantAggregate, Value> { 831 static inline bool doit(const Value &Val) { 832 return Val.getValueID() >= Value::ConstantAggregateFirstVal && 833 Val.getValueID() <= Value::ConstantAggregateLastVal; 834 } 835 }; 836 837 template <> struct isa_impl<Argument, Value> { 838 static inline bool doit (const Value &Val) { 839 return Val.getValueID() == Value::ArgumentVal; 840 } 841 }; 842 843 template <> struct isa_impl<InlineAsm, Value> { 844 static inline bool doit(const Value &Val) { 845 return Val.getValueID() == Value::InlineAsmVal; 846 } 847 }; 848 849 template <> struct isa_impl<Instruction, Value> { 850 static inline bool doit(const Value &Val) { 851 return Val.getValueID() >= Value::InstructionVal; 852 } 853 }; 854 855 template <> struct isa_impl<BasicBlock, Value> { 856 static inline bool doit(const Value &Val) { 857 return Val.getValueID() == Value::BasicBlockVal; 858 } 859 }; 860 861 template <> struct isa_impl<Function, Value> { 862 static inline bool doit(const Value &Val) { 863 return Val.getValueID() == Value::FunctionVal; 864 } 865 }; 866 867 template <> struct isa_impl<GlobalVariable, Value> { 868 static inline bool doit(const Value &Val) { 869 return Val.getValueID() == Value::GlobalVariableVal; 870 } 871 }; 872 873 template <> struct isa_impl<GlobalAlias, Value> { 874 static inline bool doit(const Value &Val) { 875 return Val.getValueID() == Value::GlobalAliasVal; 876 } 877 }; 878 879 template <> struct isa_impl<GlobalIFunc, Value> { 880 static inline bool doit(const Value &Val) { 881 return Val.getValueID() == Value::GlobalIFuncVal; 882 } 883 }; 884 885 template <> struct isa_impl<GlobalIndirectSymbol, Value> { 886 static inline bool doit(const Value &Val) { 887 return isa<GlobalAlias>(Val) || isa<GlobalIFunc>(Val); 888 } 889 }; 890 891 template <> struct isa_impl<GlobalValue, Value> { 892 static inline bool doit(const Value &Val) { 893 return isa<GlobalObject>(Val) || isa<GlobalIndirectSymbol>(Val); 894 } 895 }; 896 897 template <> struct isa_impl<GlobalObject, Value> { 898 static inline bool doit(const Value &Val) { 899 return isa<GlobalVariable>(Val) || isa<Function>(Val); 900 } 901 }; 902 903 // Create wrappers for C Binding types (see CBindingWrapping.h). 904 DEFINE_ISA_CONVERSION_FUNCTIONS(Value, LLVMValueRef) 905 906 // Specialized opaque value conversions. 907 inline Value **unwrap(LLVMValueRef *Vals) { 908 return reinterpret_cast<Value**>(Vals); 909 } 910 911 template<typename T> 912 inline T **unwrap(LLVMValueRef *Vals, unsigned Length) { 913 #ifndef NDEBUG 914 for (LLVMValueRef *I = Vals, *E = Vals + Length; I != E; ++I) 915 unwrap<T>(*I); // For side effect of calling assert on invalid usage. 916 #endif 917 (void)Length; 918 return reinterpret_cast<T**>(Vals); 919 } 920 921 inline LLVMValueRef *wrap(const Value **Vals) { 922 return reinterpret_cast<LLVMValueRef*>(const_cast<Value**>(Vals)); 923 } 924 925 } // end namespace llvm 926 927 #endif // LLVM_IR_VALUE_H 928