contrib/llvm/include/llvm/IR/Value.h

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