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, all-zero GEPs, aliases and barriers.
 486   ///
 487   /// Returns the original uncasted value.  If this is called on a non-pointer
 488   /// value, it returns 'this'. This function should be used only in
 489   /// Alias analysis.
 490   const Value *stripPointerCastsAndBarriers() const;
 491   Value *stripPointerCastsAndBarriers() {
 492     return const_cast<Value *>(
 493         static_cast<const Value *>(this)->stripPointerCastsAndBarriers());
 494   }
 495
 496   /// \brief Strip off pointer casts and all-zero GEPs.
 497   ///
 498   /// Returns the original uncasted value.  If this is called on a non-pointer
 499   /// value, it returns 'this'.
 500   const Value *stripPointerCastsNoFollowAliases() const;
 501   Value *stripPointerCastsNoFollowAliases() {
 502     return const_cast<Value *>(
 503           static_cast<const Value *>(this)->stripPointerCastsNoFollowAliases());
 504   }
 505
 506   /// \brief Strip off pointer casts and all-constant inbounds GEPs.
 507   ///
 508   /// Returns the original pointer value.  If this is called on a non-pointer
 509   /// value, it returns 'this'.
 510   const Value *stripInBoundsConstantOffsets() const;
 511   Value *stripInBoundsConstantOffsets() {
 512     return const_cast<Value *>(
 513               static_cast<const Value *>(this)->stripInBoundsConstantOffsets());
 514   }
 515
 516   /// \brief Accumulate offsets from \a stripInBoundsConstantOffsets().
 517   ///
 518   /// Stores the resulting constant offset stripped into the APInt provided.
 519   /// The provided APInt will be extended or truncated as needed to be the
 520   /// correct bitwidth for an offset of this pointer type.
 521   ///
 522   /// If this is called on a non-pointer value, it returns 'this'.
 523   const Value *stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL,
 524                                                          APInt &Offset) const;
 525   Value *stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL,
 526                                                    APInt &Offset) {
 527     return const_cast<Value *>(static_cast<const Value *>(this)
 528         ->stripAndAccumulateInBoundsConstantOffsets(DL, Offset));
 529   }
 530
 531   /// \brief Strip off pointer casts and inbounds GEPs.
 532   ///
 533   /// Returns the original pointer value.  If this is called on a non-pointer
 534   /// value, it returns 'this'.
 535   const Value *stripInBoundsOffsets() const;
 536   Value *stripInBoundsOffsets() {
 537     return const_cast<Value *>(
 538                       static_cast<const Value *>(this)->stripInBoundsOffsets());
 539   }
 540
 541   /// \brief Returns the number of bytes known to be dereferenceable for the
 542   /// pointer value.
 543   ///
 544   /// If CanBeNull is set by this function the pointer can either be null or be
 545   /// dereferenceable up to the returned number of bytes.
 546   unsigned getPointerDereferenceableBytes(const DataLayout &DL,
 547                                           bool &CanBeNull) const;
 548
 549   /// \brief Returns an alignment of the pointer value.
 550   ///
 551   /// Returns an alignment which is either specified explicitly, e.g. via
 552   /// align attribute of a function argument, or guaranteed by DataLayout.
 553   unsigned getPointerAlignment(const DataLayout &DL) const;
 554
 555   /// \brief Translate PHI node to its predecessor from the given basic block.
 556   ///
 557   /// If this value is a PHI node with CurBB as its parent, return the value in
 558   /// the PHI node corresponding to PredBB.  If not, return ourself.  This is
 559   /// useful if you want to know the value something has in a predecessor
 560   /// block.
 561   const Value *DoPHITranslation(const BasicBlock *CurBB,
 562                                 const BasicBlock *PredBB) const;
 563
 564   Value *DoPHITranslation(const BasicBlock *CurBB, const BasicBlock *PredBB) {
 565     return const_cast<Value *>(
 566              static_cast<const Value *>(this)->DoPHITranslation(CurBB, PredBB));
 567   }
 568
 569   /// \brief The maximum alignment for instructions.
 570   ///
 571   /// This is the greatest alignment value supported by load, store, and alloca
 572   /// instructions, and global values.
 573   static const unsigned MaxAlignmentExponent = 29;
 574   static const unsigned MaximumAlignment = 1u << MaxAlignmentExponent;
 575
 576   /// \brief Mutate the type of this Value to be of the specified type.
 577   ///
 578   /// Note that this is an extremely dangerous operation which can create
 579   /// completely invalid IR very easily.  It is strongly recommended that you
 580   /// recreate IR objects with the right types instead of mutating them in
 581   /// place.
 582   void mutateType(Type *Ty) {
 583     VTy = Ty;
 584   }
 585
 586   /// \brief Sort the use-list.
 587   ///
 588   /// Sorts the Value's use-list by Cmp using a stable mergesort.  Cmp is
 589   /// expected to compare two \a Use references.
 590   template <class Compare> void sortUseList(Compare Cmp);
 591
 592   /// \brief Reverse the use-list.
 593   void reverseUseList();
 594
 595 private:
 596   /// \brief Merge two lists together.
 597   ///
 598   /// Merges \c L and \c R using \c Cmp.  To enable stable sorts, always pushes
 599   /// "equal" items from L before items from R.
 600   ///
 601   /// \return the first element in the list.
 602   ///
 603   /// \note Completely ignores \a Use::Prev (doesn't read, doesn't update).
 604   template <class Compare>
 605   static Use *mergeUseLists(Use *L, Use *R, Compare Cmp) {
 606     Use *Merged;
 607     Use **Next = &Merged;
 608
 609     for (;;) {
 610       if (!L) {
 611         *Next = R;
 612         break;
 613       }
 614       if (!R) {
 615         *Next = L;
 616         break;
 617       }
 618       if (Cmp(*R, *L)) {
 619         *Next = R;
 620         Next = &R->Next;
 621         R = R->Next;
 622       } else {
 623         *Next = L;
 624         Next = &L->Next;
 625         L = L->Next;
 626       }
 627     }
 628
 629     return Merged;
 630   }
 631
 632   /// \brief Tail-recursive helper for \a mergeUseLists().
 633   ///
 634   /// \param[out] Next the first element in the list.
 635   template <class Compare>
 636   static void mergeUseListsImpl(Use *L, Use *R, Use **Next, Compare Cmp);
 637
 638 protected:
 639   unsigned short getSubclassDataFromValue() const { return SubclassData; }
 640   void setValueSubclassData(unsigned short D) { SubclassData = D; }
 641 };
 642
 643 inline raw_ostream &operator<<(raw_ostream &OS, const Value &V) {
 644   V.print(OS);
 645   return OS;
 646 }
 647
 648 void Use::set(Value *V) {
 649   if (Val) removeFromList();
 650   Val = V;
 651   if (V) V->addUse(*this);
 652 }
 653
 654 Value *Use::operator=(Value *RHS) {
 655   set(RHS);
 656   return RHS;
 657 }
 658
 659 const Use &Use::operator=(const Use &RHS) {
 660   set(RHS.Val);
 661   return *this;
 662 }
 663
 664 template <class Compare> void Value::sortUseList(Compare Cmp) {
 665   if (!UseList || !UseList->Next)
 666     // No need to sort 0 or 1 uses.
 667     return;
 668
 669   // Note: this function completely ignores Prev pointers until the end when
 670   // they're fixed en masse.
 671
 672   // Create a binomial vector of sorted lists, visiting uses one at a time and
 673   // merging lists as necessary.
 674   const unsigned MaxSlots = 32;
 675   Use *Slots[MaxSlots];
 676
 677   // Collect the first use, turning it into a single-item list.
 678   Use *Next = UseList->Next;
 679   UseList->Next = nullptr;
 680   unsigned NumSlots = 1;
 681   Slots[0] = UseList;
 682
 683   // Collect all but the last use.
 684   while (Next->Next) {
 685     Use *Current = Next;
 686     Next = Current->Next;
 687
 688     // Turn Current into a single-item list.
 689     Current->Next = nullptr;
 690
 691     // Save Current in the first available slot, merging on collisions.
 692     unsigned I;
 693     for (I = 0; I < NumSlots; ++I) {
 694       if (!Slots[I])
 695         break;
 696
 697       // Merge two lists, doubling the size of Current and emptying slot I.
 698       //
 699       // Since the uses in Slots[I] originally preceded those in Current, send
 700       // Slots[I] in as the left parameter to maintain a stable sort.
 701       Current = mergeUseLists(Slots[I], Current, Cmp);
 702       Slots[I] = nullptr;
 703     }
 704     // Check if this is a new slot.
 705     if (I == NumSlots) {
 706       ++NumSlots;
 707       assert(NumSlots <= MaxSlots && "Use list bigger than 2^32");
 708     }
 709
 710     // Found an open slot.
 711     Slots[I] = Current;
 712   }
 713
 714   // Merge all the lists together.
 715   assert(Next && "Expected one more Use");
 716   assert(!Next->Next && "Expected only one Use");
 717   UseList = Next;
 718   for (unsigned I = 0; I < NumSlots; ++I)
 719     if (Slots[I])
 720       // Since the uses in Slots[I] originally preceded those in UseList, send
 721       // Slots[I] in as the left parameter to maintain a stable sort.
 722       UseList = mergeUseLists(Slots[I], UseList, Cmp);
 723
 724   // Fix the Prev pointers.
 725   for (Use *I = UseList, **Prev = &UseList; I; I = I->Next) {
 726     I->setPrev(Prev);
 727     Prev = &I->Next;
 728   }
 729 }
 730
 731 // isa - Provide some specializations of isa so that we don't have to include
 732 // the subtype header files to test to see if the value is a subclass...
 733 //
 734 template <> struct isa_impl<Constant, Value> {
 735   static inline bool doit(const Value &Val) {
 736     return Val.getValueID() >= Value::ConstantFirstVal &&
 737       Val.getValueID() <= Value::ConstantLastVal;
 738   }
 739 };
 740
 741 template <> struct isa_impl<ConstantData, Value> {
 742   static inline bool doit(const Value &Val) {
 743     return Val.getValueID() >= Value::ConstantDataFirstVal &&
 744            Val.getValueID() <= Value::ConstantDataLastVal;
 745   }
 746 };
 747
 748 template <> struct isa_impl<ConstantAggregate, Value> {
 749   static inline bool doit(const Value &Val) {
 750     return Val.getValueID() >= Value::ConstantAggregateFirstVal &&
 751            Val.getValueID() <= Value::ConstantAggregateLastVal;
 752   }
 753 };
 754
 755 template <> struct isa_impl<Argument, Value> {
 756   static inline bool doit (const Value &Val) {
 757     return Val.getValueID() == Value::ArgumentVal;
 758   }
 759 };
 760
 761 template <> struct isa_impl<InlineAsm, Value> {
 762   static inline bool doit(const Value &Val) {
 763     return Val.getValueID() == Value::InlineAsmVal;
 764   }
 765 };
 766
 767 template <> struct isa_impl<Instruction, Value> {
 768   static inline bool doit(const Value &Val) {
 769     return Val.getValueID() >= Value::InstructionVal;
 770   }
 771 };
 772
 773 template <> struct isa_impl<BasicBlock, Value> {
 774   static inline bool doit(const Value &Val) {
 775     return Val.getValueID() == Value::BasicBlockVal;
 776   }
 777 };
 778
 779 template <> struct isa_impl<Function, Value> {
 780   static inline bool doit(const Value &Val) {
 781     return Val.getValueID() == Value::FunctionVal;
 782   }
 783 };
 784
 785 template <> struct isa_impl<GlobalVariable, Value> {
 786   static inline bool doit(const Value &Val) {
 787     return Val.getValueID() == Value::GlobalVariableVal;
 788   }
 789 };
 790
 791 template <> struct isa_impl<GlobalAlias, Value> {
 792   static inline bool doit(const Value &Val) {
 793     return Val.getValueID() == Value::GlobalAliasVal;
 794   }
 795 };
 796
 797 template <> struct isa_impl<GlobalIFunc, Value> {
 798   static inline bool doit(const Value &Val) {
 799     return Val.getValueID() == Value::GlobalIFuncVal;
 800   }
 801 };
 802
 803 template <> struct isa_impl<GlobalIndirectSymbol, Value> {
 804   static inline bool doit(const Value &Val) {
 805     return isa<GlobalAlias>(Val) || isa<GlobalIFunc>(Val);
 806   }
 807 };
 808
 809 template <> struct isa_impl<GlobalValue, Value> {
 810   static inline bool doit(const Value &Val) {
 811     return isa<GlobalObject>(Val) || isa<GlobalIndirectSymbol>(Val);
 812   }
 813 };
 814
 815 template <> struct isa_impl<GlobalObject, Value> {
 816   static inline bool doit(const Value &Val) {
 817     return isa<GlobalVariable>(Val) || isa<Function>(Val);
 818   }
 819 };
 820
 821 // Create wrappers for C Binding types (see CBindingWrapping.h).
 822 DEFINE_ISA_CONVERSION_FUNCTIONS(Value, LLVMValueRef)
 823
 824 // Specialized opaque value conversions.
 825 inline Value **unwrap(LLVMValueRef *Vals) {
 826   return reinterpret_cast<Value**>(Vals);
 827 }
 828
 829 template<typename T>
 830 inline T **unwrap(LLVMValueRef *Vals, unsigned Length) {
 831 #ifndef NDEBUG
 832   for (LLVMValueRef *I = Vals, *E = Vals + Length; I != E; ++I)
 833     unwrap<T>(*I); // For side effect of calling assert on invalid usage.
 834 #endif
 835   (void)Length;
 836   return reinterpret_cast<T**>(Vals);
 837 }
 838
 839 inline LLVMValueRef *wrap(const Value **Vals) {
 840   return reinterpret_cast<LLVMValueRef*>(const_cast<Value**>(Vals));
 841 }
 842
 843 } // end namespace llvm
 844
 845 #endif // LLVM_IR_VALUE_H