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