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