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