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-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 /// 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   /// 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   /// 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   /// 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     /// 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   /// Support for debugging, callable in GDB: V->dump()
 222   void dump() const;
 223
 224   /// 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   /// 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   /// All values are typed, get the type of this value.
 245   Type *getType() const { return VTy; }
 246
 247   /// All values hold a context through their type.
 248   LLVMContext &getContext() const;
 249
 250   // 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   /// 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   /// 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   /// 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   /// 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   /// Change non-metadata uses of this to point to a new Value.
 290   ///
 291   /// Go through the uses list for this definition and make each use point to
 292   /// "V" instead of "this". This function skips metadata entries in the list.
 293   void replaceNonMetadataUsesWith(Value *V);
 294
 295   /// replaceUsesOutsideBlock - Go through the uses list for this definition and
 296   /// make each use point to "V" instead of "this" when the use is outside the
 297   /// block. 'This's use list is expected to have at least one element.
 298   /// Unlike replaceAllUsesWith this function does not support basic block
 299   /// values or constant users.
 300   void replaceUsesOutsideBlock(Value *V, BasicBlock *BB);
 301
 302   //----------------------------------------------------------------------
 303   // Methods for handling the chain of uses of this Value.
 304   //
 305   // Materializing a function can introduce new uses, so these methods come in
 306   // two variants:
 307   // The methods that start with materialized_ check the uses that are
 308   // currently known given which functions are materialized. Be very careful
 309   // when using them since you might not get all uses.
 310   // The methods that don't start with materialized_ assert that modules is
 311   // fully materialized.
 312   void assertModuleIsMaterializedImpl() const;
 313   // This indirection exists so we can keep assertModuleIsMaterializedImpl()
 314   // around in release builds of Value.cpp to be linked with other code built
 315   // in debug mode. But this avoids calling it in any of the release built code.
 316   void assertModuleIsMaterialized() const {
 317 #ifndef NDEBUG
 318     assertModuleIsMaterializedImpl();
 319 #endif
 320   }
 321
 322   bool use_empty() const {
 323     assertModuleIsMaterialized();
 324     return UseList == nullptr;
 325   }
 326
 327   bool materialized_use_empty() const {
 328     return UseList == nullptr;
 329   }
 330
 331   using use_iterator = use_iterator_impl<Use>;
 332   using const_use_iterator = use_iterator_impl<const Use>;
 333
 334   use_iterator materialized_use_begin() { return use_iterator(UseList); }
 335   const_use_iterator materialized_use_begin() const {
 336     return const_use_iterator(UseList);
 337   }
 338   use_iterator use_begin() {
 339     assertModuleIsMaterialized();
 340     return materialized_use_begin();
 341   }
 342   const_use_iterator use_begin() const {
 343     assertModuleIsMaterialized();
 344     return materialized_use_begin();
 345   }
 346   use_iterator use_end() { return use_iterator(); }
 347   const_use_iterator use_end() const { return const_use_iterator(); }
 348   iterator_range<use_iterator> materialized_uses() {
 349     return make_range(materialized_use_begin(), use_end());
 350   }
 351   iterator_range<const_use_iterator> materialized_uses() const {
 352     return make_range(materialized_use_begin(), use_end());
 353   }
 354   iterator_range<use_iterator> uses() {
 355     assertModuleIsMaterialized();
 356     return materialized_uses();
 357   }
 358   iterator_range<const_use_iterator> uses() const {
 359     assertModuleIsMaterialized();
 360     return materialized_uses();
 361   }
 362
 363   bool user_empty() const {
 364     assertModuleIsMaterialized();
 365     return UseList == nullptr;
 366   }
 367
 368   using user_iterator = user_iterator_impl<User>;
 369   using const_user_iterator = user_iterator_impl<const User>;
 370
 371   user_iterator materialized_user_begin() { return user_iterator(UseList); }
 372   const_user_iterator materialized_user_begin() const {
 373     return const_user_iterator(UseList);
 374   }
 375   user_iterator user_begin() {
 376     assertModuleIsMaterialized();
 377     return materialized_user_begin();
 378   }
 379   const_user_iterator user_begin() const {
 380     assertModuleIsMaterialized();
 381     return materialized_user_begin();
 382   }
 383   user_iterator user_end() { return user_iterator(); }
 384   const_user_iterator user_end() const { return const_user_iterator(); }
 385   User *user_back() {
 386     assertModuleIsMaterialized();
 387     return *materialized_user_begin();
 388   }
 389   const User *user_back() const {
 390     assertModuleIsMaterialized();
 391     return *materialized_user_begin();
 392   }
 393   iterator_range<user_iterator> materialized_users() {
 394     return make_range(materialized_user_begin(), user_end());
 395   }
 396   iterator_range<const_user_iterator> materialized_users() const {
 397     return make_range(materialized_user_begin(), user_end());
 398   }
 399   iterator_range<user_iterator> users() {
 400     assertModuleIsMaterialized();
 401     return materialized_users();
 402   }
 403   iterator_range<const_user_iterator> users() const {
 404     assertModuleIsMaterialized();
 405     return materialized_users();
 406   }
 407
 408   /// Return true if there is exactly one user of this value.
 409   ///
 410   /// This is specialized because it is a common request and does not require
 411   /// traversing the whole use list.
 412   bool hasOneUse() const {
 413     const_use_iterator I = use_begin(), E = use_end();
 414     if (I == E) return false;
 415     return ++I == E;
 416   }
 417
 418   /// Return true if this Value has exactly N users.
 419   bool hasNUses(unsigned N) const;
 420
 421   /// Return true if this value has N users or more.
 422   ///
 423   /// This is logically equivalent to getNumUses() >= N.
 424   bool hasNUsesOrMore(unsigned N) const;
 425
 426   /// Check if this value is used in the specified basic block.
 427   bool isUsedInBasicBlock(const BasicBlock *BB) const;
 428
 429   /// This method computes the number of uses of this Value.
 430   ///
 431   /// This is a linear time operation.  Use hasOneUse, hasNUses, or
 432   /// hasNUsesOrMore to check for specific values.
 433   unsigned getNumUses() const;
 434
 435   /// This method should only be used by the Use class.
 436   void addUse(Use &U) { U.addToList(&UseList); }
 437
 438   /// Concrete subclass of this.
 439   ///
 440   /// An enumeration for keeping track of the concrete subclass of Value that
 441   /// is actually instantiated. Values of this enumeration are kept in the
 442   /// Value classes SubclassID field. They are used for concrete type
 443   /// identification.
 444   enum ValueTy {
 445 #define HANDLE_VALUE(Name) Name##Val,
 446 #include "llvm/IR/Value.def"
 447
 448     // Markers:
 449 #define HANDLE_CONSTANT_MARKER(Marker, Constant) Marker = Constant##Val,
 450 #include "llvm/IR/Value.def"
 451   };
 452
 453   /// Return an ID for the concrete type of this object.
 454   ///
 455   /// This is used to implement the classof checks.  This should not be used
 456   /// for any other purpose, as the values may change as LLVM evolves.  Also,
 457   /// note that for instructions, the Instruction's opcode is added to
 458   /// InstructionVal. So this means three things:
 459   /// # there is no value with code InstructionVal (no opcode==0).
 460   /// # there are more possible values for the value type than in ValueTy enum.
 461   /// # the InstructionVal enumerator must be the highest valued enumerator in
 462   ///   the ValueTy enum.
 463   unsigned getValueID() const {
 464     return SubclassID;
 465   }
 466
 467   /// Return the raw optional flags value contained in this value.
 468   ///
 469   /// This should only be used when testing two Values for equivalence.
 470   unsigned getRawSubclassOptionalData() const {
 471     return SubclassOptionalData;
 472   }
 473
 474   /// Clear the optional flags contained in this value.
 475   void clearSubclassOptionalData() {
 476     SubclassOptionalData = 0;
 477   }
 478
 479   /// Check the optional flags for equality.
 480   bool hasSameSubclassOptionalData(const Value *V) const {
 481     return SubclassOptionalData == V->SubclassOptionalData;
 482   }
 483
 484   /// Return true if there is a value handle associated with this value.
 485   bool hasValueHandle() const { return HasValueHandle; }
 486
 487   /// Return true if there is metadata referencing this value.
 488   bool isUsedByMetadata() const { return IsUsedByMD; }
 489
 490   /// Return true if this value is a swifterror value.
 491   ///
 492   /// swifterror values can be either a function argument or an alloca with a
 493   /// swifterror attribute.
 494   bool isSwiftError() const;
 495
 496   /// Strip off pointer casts, all-zero GEPs, and aliases.
 497   ///
 498   /// Returns the original uncasted value.  If this is called on a non-pointer
 499   /// value, it returns 'this'.
 500   const Value *stripPointerCasts() const;
 501   Value *stripPointerCasts() {
 502     return const_cast<Value *>(
 503                          static_cast<const Value *>(this)->stripPointerCasts());
 504   }
 505
 506   /// Strip off pointer casts, all-zero GEPs, aliases and invariant group
 507   /// info.
 508   ///
 509   /// Returns the original uncasted value.  If this is called on a non-pointer
 510   /// value, it returns 'this'. This function should be used only in
 511   /// Alias analysis.
 512   const Value *stripPointerCastsAndInvariantGroups() const;
 513   Value *stripPointerCastsAndInvariantGroups() {
 514     return const_cast<Value *>(
 515         static_cast<const Value *>(this)->stripPointerCastsAndInvariantGroups());
 516   }
 517
 518   /// Strip off pointer casts and all-zero GEPs.
 519   ///
 520   /// Returns the original uncasted value.  If this is called on a non-pointer
 521   /// value, it returns 'this'.
 522   const Value *stripPointerCastsNoFollowAliases() const;
 523   Value *stripPointerCastsNoFollowAliases() {
 524     return const_cast<Value *>(
 525           static_cast<const Value *>(this)->stripPointerCastsNoFollowAliases());
 526   }
 527
 528   /// Strip off pointer casts and all-constant inbounds GEPs.
 529   ///
 530   /// Returns the original pointer value.  If this is called on a non-pointer
 531   /// value, it returns 'this'.
 532   const Value *stripInBoundsConstantOffsets() const;
 533   Value *stripInBoundsConstantOffsets() {
 534     return const_cast<Value *>(
 535               static_cast<const Value *>(this)->stripInBoundsConstantOffsets());
 536   }
 537
 538   /// Accumulate offsets from \a stripInBoundsConstantOffsets().
 539   ///
 540   /// Stores the resulting constant offset stripped into the APInt provided.
 541   /// The provided APInt will be extended or truncated as needed to be the
 542   /// correct bitwidth for an offset of this pointer type.
 543   ///
 544   /// If this is called on a non-pointer value, it returns 'this'.
 545   const Value *stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL,
 546                                                          APInt &Offset) const;
 547   Value *stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL,
 548                                                    APInt &Offset) {
 549     return const_cast<Value *>(static_cast<const Value *>(this)
 550         ->stripAndAccumulateInBoundsConstantOffsets(DL, Offset));
 551   }
 552
 553   /// Strip off pointer casts and inbounds GEPs.
 554   ///
 555   /// Returns the original pointer value.  If this is called on a non-pointer
 556   /// value, it returns 'this'.
 557   const Value *stripInBoundsOffsets() const;
 558   Value *stripInBoundsOffsets() {
 559     return const_cast<Value *>(
 560                       static_cast<const Value *>(this)->stripInBoundsOffsets());
 561   }
 562
 563   /// Returns the number of bytes known to be dereferenceable for the
 564   /// pointer value.
 565   ///
 566   /// If CanBeNull is set by this function the pointer can either be null or be
 567   /// dereferenceable up to the returned number of bytes.
 568   uint64_t getPointerDereferenceableBytes(const DataLayout &DL,
 569                                           bool &CanBeNull) const;
 570
 571   /// Returns an alignment of the pointer value.
 572   ///
 573   /// Returns an alignment which is either specified explicitly, e.g. via
 574   /// align attribute of a function argument, or guaranteed by DataLayout.
 575   unsigned getPointerAlignment(const DataLayout &DL) const;
 576
 577   /// Translate PHI node to its predecessor from the given basic block.
 578   ///
 579   /// If this value is a PHI node with CurBB as its parent, return the value in
 580   /// the PHI node corresponding to PredBB.  If not, return ourself.  This is
 581   /// useful if you want to know the value something has in a predecessor
 582   /// block.
 583   const Value *DoPHITranslation(const BasicBlock *CurBB,
 584                                 const BasicBlock *PredBB) const;
 585   Value *DoPHITranslation(const BasicBlock *CurBB, const BasicBlock *PredBB) {
 586     return const_cast<Value *>(
 587              static_cast<const Value *>(this)->DoPHITranslation(CurBB, PredBB));
 588   }
 589
 590   /// The maximum alignment for instructions.
 591   ///
 592   /// This is the greatest alignment value supported by load, store, and alloca
 593   /// instructions, and global values.
 594   static const unsigned MaxAlignmentExponent = 29;
 595   static const unsigned MaximumAlignment = 1u << MaxAlignmentExponent;
 596
 597   /// Mutate the type of this Value to be of the specified type.
 598   ///
 599   /// Note that this is an extremely dangerous operation which can create
 600   /// completely invalid IR very easily.  It is strongly recommended that you
 601   /// recreate IR objects with the right types instead of mutating them in
 602   /// place.
 603   void mutateType(Type *Ty) {
 604     VTy = Ty;
 605   }
 606
 607   /// Sort the use-list.
 608   ///
 609   /// Sorts the Value's use-list by Cmp using a stable mergesort.  Cmp is
 610   /// expected to compare two \a Use references.
 611   template <class Compare> void sortUseList(Compare Cmp);
 612
 613   /// Reverse the use-list.
 614   void reverseUseList();
 615
 616 private:
 617   /// Merge two lists together.
 618   ///
 619   /// Merges \c L and \c R using \c Cmp.  To enable stable sorts, always pushes
 620   /// "equal" items from L before items from R.
 621   ///
 622   /// \return the first element in the list.
 623   ///
 624   /// \note Completely ignores \a Use::Prev (doesn't read, doesn't update).
 625   template <class Compare>
 626   static Use *mergeUseLists(Use *L, Use *R, Compare Cmp) {
 627     Use *Merged;
 628     Use **Next = &Merged;
 629
 630     while (true) {
 631       if (!L) {
 632         *Next = R;
 633         break;
 634       }
 635       if (!R) {
 636         *Next = L;
 637         break;
 638       }
 639       if (Cmp(*R, *L)) {
 640         *Next = R;
 641         Next = &R->Next;
 642         R = R->Next;
 643       } else {
 644         *Next = L;
 645         Next = &L->Next;
 646         L = L->Next;
 647       }
 648     }
 649
 650     return Merged;
 651   }
 652
 653 protected:
 654   unsigned short getSubclassDataFromValue() const { return SubclassData; }
 655   void setValueSubclassData(unsigned short D) { SubclassData = D; }
 656 };
 657
 658 struct ValueDeleter { void operator()(Value *V) { V->deleteValue(); } };
 659
 660 /// Use this instead of std::unique_ptr<Value> or std::unique_ptr<Instruction>.
 661 /// Those don't work because Value and Instruction's destructors are protected,
 662 /// aren't virtual, and won't destroy the complete object.
 663 using unique_value = std::unique_ptr<Value, ValueDeleter>;
 664
 665 inline raw_ostream &operator<<(raw_ostream &OS, const Value &V) {
 666   V.print(OS);
 667   return OS;
 668 }
 669
 670 void Use::set(Value *V) {
 671   if (Val) removeFromList();
 672   Val = V;
 673   if (V) V->addUse(*this);
 674 }
 675
 676 Value *Use::operator=(Value *RHS) {
 677   set(RHS);
 678   return RHS;
 679 }
 680
 681 const Use &Use::operator=(const Use &RHS) {
 682   set(RHS.Val);
 683   return *this;
 684 }
 685
 686 template <class Compare> void Value::sortUseList(Compare Cmp) {
 687   if (!UseList || !UseList->Next)
 688     // No need to sort 0 or 1 uses.
 689     return;
 690
 691   // Note: this function completely ignores Prev pointers until the end when
 692   // they're fixed en masse.
 693
 694   // Create a binomial vector of sorted lists, visiting uses one at a time and
 695   // merging lists as necessary.
 696   const unsigned MaxSlots = 32;
 697   Use *Slots[MaxSlots];
 698
 699   // Collect the first use, turning it into a single-item list.
 700   Use *Next = UseList->Next;
 701   UseList->Next = nullptr;
 702   unsigned NumSlots = 1;
 703   Slots[0] = UseList;
 704
 705   // Collect all but the last use.
 706   while (Next->Next) {
 707     Use *Current = Next;
 708     Next = Current->Next;
 709
 710     // Turn Current into a single-item list.
 711     Current->Next = nullptr;
 712
 713     // Save Current in the first available slot, merging on collisions.
 714     unsigned I;
 715     for (I = 0; I < NumSlots; ++I) {
 716       if (!Slots[I])
 717         break;
 718
 719       // Merge two lists, doubling the size of Current and emptying slot I.
 720       //
 721       // Since the uses in Slots[I] originally preceded those in Current, send
 722       // Slots[I] in as the left parameter to maintain a stable sort.
 723       Current = mergeUseLists(Slots[I], Current, Cmp);
 724       Slots[I] = nullptr;
 725     }
 726     // Check if this is a new slot.
 727     if (I == NumSlots) {
 728       ++NumSlots;
 729       assert(NumSlots <= MaxSlots && "Use list bigger than 2^32");
 730     }
 731
 732     // Found an open slot.
 733     Slots[I] = Current;
 734   }
 735
 736   // Merge all the lists together.
 737   assert(Next && "Expected one more Use");
 738   assert(!Next->Next && "Expected only one Use");
 739   UseList = Next;
 740   for (unsigned I = 0; I < NumSlots; ++I)
 741     if (Slots[I])
 742       // Since the uses in Slots[I] originally preceded those in UseList, send
 743       // Slots[I] in as the left parameter to maintain a stable sort.
 744       UseList = mergeUseLists(Slots[I], UseList, Cmp);
 745
 746   // Fix the Prev pointers.
 747   for (Use *I = UseList, **Prev = &UseList; I; I = I->Next) {
 748     I->setPrev(Prev);
 749     Prev = &I->Next;
 750   }
 751 }
 752
 753 // isa - Provide some specializations of isa so that we don't have to include
 754 // the subtype header files to test to see if the value is a subclass...
 755 //
 756 template <> struct isa_impl<Constant, Value> {
 757   static inline bool doit(const Value &Val) {
 758     static_assert(Value::ConstantFirstVal == 0, "Val.getValueID() >= Value::ConstantFirstVal");
 759     return Val.getValueID() <= Value::ConstantLastVal;
 760   }
 761 };
 762
 763 template <> struct isa_impl<ConstantData, Value> {
 764   static inline bool doit(const Value &Val) {
 765     return Val.getValueID() >= Value::ConstantDataFirstVal &&
 766            Val.getValueID() <= Value::ConstantDataLastVal;
 767   }
 768 };
 769
 770 template <> struct isa_impl<ConstantAggregate, Value> {
 771   static inline bool doit(const Value &Val) {
 772     return Val.getValueID() >= Value::ConstantAggregateFirstVal &&
 773            Val.getValueID() <= Value::ConstantAggregateLastVal;
 774   }
 775 };
 776
 777 template <> struct isa_impl<Argument, Value> {
 778   static inline bool doit (const Value &Val) {
 779     return Val.getValueID() == Value::ArgumentVal;
 780   }
 781 };
 782
 783 template <> struct isa_impl<InlineAsm, Value> {
 784   static inline bool doit(const Value &Val) {
 785     return Val.getValueID() == Value::InlineAsmVal;
 786   }
 787 };
 788
 789 template <> struct isa_impl<Instruction, Value> {
 790   static inline bool doit(const Value &Val) {
 791     return Val.getValueID() >= Value::InstructionVal;
 792   }
 793 };
 794
 795 template <> struct isa_impl<BasicBlock, Value> {
 796   static inline bool doit(const Value &Val) {
 797     return Val.getValueID() == Value::BasicBlockVal;
 798   }
 799 };
 800
 801 template <> struct isa_impl<Function, Value> {
 802   static inline bool doit(const Value &Val) {
 803     return Val.getValueID() == Value::FunctionVal;
 804   }
 805 };
 806
 807 template <> struct isa_impl<GlobalVariable, Value> {
 808   static inline bool doit(const Value &Val) {
 809     return Val.getValueID() == Value::GlobalVariableVal;
 810   }
 811 };
 812
 813 template <> struct isa_impl<GlobalAlias, Value> {
 814   static inline bool doit(const Value &Val) {
 815     return Val.getValueID() == Value::GlobalAliasVal;
 816   }
 817 };
 818
 819 template <> struct isa_impl<GlobalIFunc, Value> {
 820   static inline bool doit(const Value &Val) {
 821     return Val.getValueID() == Value::GlobalIFuncVal;
 822   }
 823 };
 824
 825 template <> struct isa_impl<GlobalIndirectSymbol, Value> {
 826   static inline bool doit(const Value &Val) {
 827     return isa<GlobalAlias>(Val) || isa<GlobalIFunc>(Val);
 828   }
 829 };
 830
 831 template <> struct isa_impl<GlobalValue, Value> {
 832   static inline bool doit(const Value &Val) {
 833     return isa<GlobalObject>(Val) || isa<GlobalIndirectSymbol>(Val);
 834   }
 835 };
 836
 837 template <> struct isa_impl<GlobalObject, Value> {
 838   static inline bool doit(const Value &Val) {
 839     return isa<GlobalVariable>(Val) || isa<Function>(Val);
 840   }
 841 };
 842
 843 // Create wrappers for C Binding types (see CBindingWrapping.h).
 844 DEFINE_ISA_CONVERSION_FUNCTIONS(Value, LLVMValueRef)
 845
 846 // Specialized opaque value conversions.
 847 inline Value **unwrap(LLVMValueRef *Vals) {
 848   return reinterpret_cast<Value**>(Vals);
 849 }
 850
 851 template<typename T>
 852 inline T **unwrap(LLVMValueRef *Vals, unsigned Length) {
 853 #ifndef NDEBUG
 854   for (LLVMValueRef *I = Vals, *E = Vals + Length; I != E; ++I)
 855     unwrap<T>(*I); // For side effect of calling assert on invalid usage.
 856 #endif
 857   (void)Length;
 858   return reinterpret_cast<T**>(Vals);
 859 }
 860
 861 inline LLVMValueRef *wrap(const Value **Vals) {
 862   return reinterpret_cast<LLVMValueRef*>(const_cast<Value**>(Vals));
 863 }
 864
 865 } // end namespace llvm
 866
 867 #endif // LLVM_IR_VALUE_H