diff options
Diffstat (limited to 'include/llvm/IR/Value.h')
| -rw-r--r-- | include/llvm/IR/Value.h | 306 |
1 files changed, 225 insertions, 81 deletions
diff --git a/include/llvm/IR/Value.h b/include/llvm/IR/Value.h index b5bbc96..67665be 100644 --- a/include/llvm/IR/Value.h +++ b/include/llvm/IR/Value.h @@ -53,6 +53,8 @@ typedef StringMapEntry<Value*> ValueName; // Value Class //===----------------------------------------------------------------------===// +/// \brief LLVM Value Representation +/// /// This is a very important LLVM class. It is the base class of all values /// computed by a program that may be used as operands to other values. Value is /// the super class of other important classes such as Instruction and Function. @@ -64,8 +66,6 @@ typedef StringMapEntry<Value*> ValueName; /// using this Value. A Value can also have an arbitrary number of ValueHandle /// objects that watch it and listen to RAUW and Destroy events. See /// llvm/IR/ValueHandle.h for details. -/// -/// @brief LLVM Value Representation class Value { Type *VTy; Use *UseList; @@ -77,18 +77,34 @@ class Value { const unsigned char SubclassID; // Subclass identifier (for isa/dyn_cast) unsigned char HasValueHandle : 1; // Has a ValueHandle pointing to this? protected: - /// SubclassOptionalData - This member is similar to SubclassData, however it - /// is for holding information which may be used to aid optimization, but - /// which may be cleared to zero without affecting conservative - /// interpretation. + /// \brief Hold subclass data that can be dropped. + /// + /// This member is similar to SubclassData, however it is for holding + /// information which may be used to aid optimization, but which may be + /// cleared to zero without affecting conservative interpretation. unsigned char SubclassOptionalData : 7; private: - /// SubclassData - This member is defined by this class, but is not used for - /// anything. Subclasses can use it to hold whatever state they find useful. - /// This field is initialized to zero by the ctor. + /// \brief Hold arbitrary subclass data. + /// + /// This member is defined by this class, but is not used for anything. + /// Subclasses can use it to hold whatever state they find useful. This + /// field is initialized to zero by the ctor. unsigned short SubclassData; +protected: + /// \brief The number of operands in the subclass. + /// + /// This member is defined by this class, but not used for anything. + /// Subclasses can use it to store their number of operands, if they have + /// any. + /// + /// This is stored here to save space in User on 64-bit hosts. Since most + /// instances of Value have operands, 32-bit hosts aren't significantly + /// affected. + unsigned NumOperands; + +private: template <typename UseT> // UseT == 'Use' or 'const Use' class use_iterator_impl : public std::iterator<std::forward_iterator_tag, UseT *, ptrdiff_t> { @@ -175,6 +191,7 @@ private: Use &getUse() const { return *UI; } /// \brief Return the operand # of this use in its User. + /// /// FIXME: Replace all callers with a direct call to Use::getOperandNo. unsigned getOperandNo() const { return UI->getOperandNo(); } }; @@ -187,15 +204,14 @@ protected: public: virtual ~Value(); - /// dump - Support for debugging, callable in GDB: V->dump() - // + /// \brief Support for debugging, callable in GDB: V->dump() void dump() const; - /// print - Implement operator<< on Value. - /// + /// \brief Implement operator<< on Value. void print(raw_ostream &O) const; /// \brief Print the name of this Value out to the specified raw_ostream. + /// /// This is useful when you just want to print 'int %reg126', not the /// instruction that generated it. If you specify a Module for context, then /// even constanst get pretty-printed; for example, the type of a null @@ -203,38 +219,43 @@ public: void printAsOperand(raw_ostream &O, bool PrintType = true, const Module *M = nullptr) const; - /// All values are typed, get the type of this value. - /// + /// \brief All values are typed, get the type of this value. Type *getType() const { return VTy; } - /// All values hold a context through their type. + /// \brief All values hold a context through their type. LLVMContext &getContext() const; - // All values can potentially be named. - bool hasName() const { return Name != nullptr && SubclassID != MDStringVal; } + // \brief All values can potentially be named. + bool hasName() const { return Name != nullptr; } ValueName *getValueName() const { return Name; } void setValueName(ValueName *VN) { Name = VN; } - /// getName() - Return a constant reference to the value's name. This is cheap - /// and guaranteed to return the same reference as long as the value is not - /// modified. + /// \brief Return a constant reference to the value's name. + /// + /// This is cheap and guaranteed to return the same reference as long as the + /// value is not modified. StringRef getName() const; - /// setName() - Change the name of the value, choosing a new unique name if - /// the provided name is taken. + /// \brief Change the name of the value. + /// + /// Choose a new unique name if the provided name is taken. /// /// \param Name The new name; or "" if the value's name should be removed. void setName(const Twine &Name); - /// takeName - transfer the name from V to this value, setting V's name to - /// empty. It is an error to call V->takeName(V). + /// \brief Transfer the name from V to this value. + /// + /// After taking V's name, sets V's name to empty. + /// + /// \note It is an error to call V->takeName(V). void takeName(Value *V); - /// replaceAllUsesWith - Go through the uses list for this definition and make - /// each use point to "V" instead of "this". After this completes, 'this's - /// use list is guaranteed to be empty. + /// \brief Change all uses of this to point to a new Value. /// + /// Go through the uses list for this definition and make each use point to + /// "V" instead of "this". After this completes, 'this's use list is + /// guaranteed to be empty. void replaceAllUsesWith(Value *V); //---------------------------------------------------------------------- @@ -270,36 +291,38 @@ public: return iterator_range<const_user_iterator>(user_begin(), user_end()); } - /// hasOneUse - Return true if there is exactly one user of this value. This - /// is specialized because it is a common request and does not require - /// traversing the whole use list. + /// \brief Return true if there is exactly one user of this value. /// + /// This is specialized because it is a common request and does not require + /// traversing the whole use list. bool hasOneUse() const { const_use_iterator I = use_begin(), E = use_end(); if (I == E) return false; return ++I == E; } - /// hasNUses - Return true if this Value has exactly N users. - /// + /// \brief Return true if this Value has exactly N users. bool hasNUses(unsigned N) const; - /// hasNUsesOrMore - Return true if this value has N users or more. This is - /// logically equivalent to getNumUses() >= N. + /// \brief Return true if this value has N users or more. /// + /// This is logically equivalent to getNumUses() >= N. bool hasNUsesOrMore(unsigned N) const; + /// \brief Check if this value is used in the specified basic block. bool isUsedInBasicBlock(const BasicBlock *BB) const; - /// getNumUses - This method computes the number of uses of this Value. This - /// is a linear time operation. Use hasOneUse, hasNUses, or hasNUsesOrMore - /// to check for specific values. + /// \brief This method computes the number of uses of this Value. + /// + /// This is a linear time operation. Use hasOneUse, hasNUses, or + /// hasNUsesOrMore to check for specific values. unsigned getNumUses() const; - /// addUse - This method should only be used by the Use class. - /// + /// \brief This method should only be used by the Use class. void addUse(Use &U) { U.addToList(&UseList); } + /// \brief Concrete subclass of this. + /// /// An enumeration for keeping track of the concrete subclass of Value that /// is actually instantiated. Values of this enumeration are kept in the /// Value classes SubclassID field. They are used for concrete type @@ -322,7 +345,8 @@ public: ConstantStructVal, // This is an instance of ConstantStruct ConstantVectorVal, // This is an instance of ConstantVector ConstantPointerNullVal, // This is an instance of ConstantPointerNull - MDNodeVal, // This is an instance of MDNode + GenericMDNodeVal, // This is an instance of GenericMDNode + MDNodeFwdDeclVal, // This is an instance of MDNodeFwdDecl MDStringVal, // This is an instance of MDString InlineAsmVal, // This is an instance of InlineAsm InstructionVal, // This is an instance of Instruction @@ -334,11 +358,12 @@ public: ConstantLastVal = ConstantPointerNullVal }; - /// getValueID - Return an ID for the concrete type of this object. This is - /// used to implement the classof checks. This should not be used for any - /// other purpose, as the values may change as LLVM evolves. Also, note that - /// for instructions, the Instruction's opcode is added to InstructionVal. So - /// this means three things: + /// \brief Return an ID for the concrete type of this object. + /// + /// This is used to implement the classof checks. This should not be used + /// for any other purpose, as the values may change as LLVM evolves. Also, + /// note that for instructions, the Instruction's opcode is added to + /// InstructionVal. So this means three things: /// # there is no value with code InstructionVal (no opcode==0). /// # there are more possible values for the value type than in ValueTy enum. /// # the InstructionVal enumerator must be the highest valued enumerator in @@ -347,64 +372,59 @@ public: return SubclassID; } - /// getRawSubclassOptionalData - Return the raw optional flags value - /// contained in this value. This should only be used when testing two - /// Values for equivalence. + /// \brief Return the raw optional flags value contained in this value. + /// + /// This should only be used when testing two Values for equivalence. unsigned getRawSubclassOptionalData() const { return SubclassOptionalData; } - /// clearSubclassOptionalData - Clear the optional flags contained in - /// this value. + /// \brief Clear the optional flags contained in this value. void clearSubclassOptionalData() { SubclassOptionalData = 0; } - /// hasSameSubclassOptionalData - Test whether the optional flags contained - /// in this value are equal to the optional flags in the given value. + /// \brief Check the optional flags for equality. bool hasSameSubclassOptionalData(const Value *V) const { return SubclassOptionalData == V->SubclassOptionalData; } - /// intersectOptionalDataWith - Clear any optional flags in this value - /// that are not also set in the given value. + /// \brief Clear any optional flags not set in the given Value. void intersectOptionalDataWith(const Value *V) { SubclassOptionalData &= V->SubclassOptionalData; } - /// hasValueHandle - Return true if there is a value handle associated with - /// this value. + /// \brief Return true if there is a value handle associated with this value. bool hasValueHandle() const { return HasValueHandle; } - /// \brief Strips off any unneeded pointer casts, all-zero GEPs and aliases - /// from the specified value, returning the original uncasted value. + /// \brief Strip off pointer casts, all-zero GEPs, and aliases. /// - /// If this is called on a non-pointer value, it returns 'this'. + /// Returns the original uncasted value. If this is called on a non-pointer + /// value, it returns 'this'. Value *stripPointerCasts(); const Value *stripPointerCasts() const { return const_cast<Value*>(this)->stripPointerCasts(); } - /// \brief Strips off any unneeded pointer casts and all-zero GEPs from the - /// specified value, returning the original uncasted value. + /// \brief Strip off pointer casts and all-zero GEPs. /// - /// If this is called on a non-pointer value, it returns 'this'. + /// Returns the original uncasted value. If this is called on a non-pointer + /// value, it returns 'this'. Value *stripPointerCastsNoFollowAliases(); const Value *stripPointerCastsNoFollowAliases() const { return const_cast<Value*>(this)->stripPointerCastsNoFollowAliases(); } - /// \brief Strips off unneeded pointer casts and all-constant GEPs from the - /// specified value, returning the original pointer value. + /// \brief Strip off pointer casts and all-constant inbounds GEPs. /// - /// If this is called on a non-pointer value, it returns 'this'. + /// Returns the original pointer value. If this is called on a non-pointer + /// value, it returns 'this'. Value *stripInBoundsConstantOffsets(); const Value *stripInBoundsConstantOffsets() const { return const_cast<Value*>(this)->stripInBoundsConstantOffsets(); } - /// \brief Strips like \c stripInBoundsConstantOffsets but also accumulates - /// the constant offset stripped. + /// \brief Accumulate offsets from \a stripInBoundsConstantOffsets(). /// /// Stores the resulting constant offset stripped into the APInt provided. /// The provided APInt will be extended or truncated as needed to be the @@ -419,23 +439,27 @@ public: ->stripAndAccumulateInBoundsConstantOffsets(DL, Offset); } - /// \brief Strips off unneeded pointer casts and any in-bounds offsets from - /// the specified value, returning the original pointer value. + /// \brief Strip off pointer casts and inbounds GEPs. /// - /// If this is called on a non-pointer value, it returns 'this'. + /// Returns the original pointer value. If this is called on a non-pointer + /// value, it returns 'this'. Value *stripInBoundsOffsets(); const Value *stripInBoundsOffsets() const { return const_cast<Value*>(this)->stripInBoundsOffsets(); } - /// isDereferenceablePointer - Test if this value is always a pointer to - /// allocated and suitably aligned memory for a simple load or store. + /// \brief Check if this is always a dereferenceable pointer. + /// + /// Test if this value is always a pointer to allocated and suitably aligned + /// memory for a simple load or store. bool isDereferenceablePointer(const DataLayout *DL = nullptr) const; - /// DoPHITranslation - If this value is a PHI node with CurBB as its parent, - /// return the value in the PHI node corresponding to PredBB. If not, return - /// ourself. This is useful if you want to know the value something has in a - /// predecessor block. + /// \brief Translate PHI node to its predecessor from the given basic block. + /// + /// If this value is a PHI node with CurBB as its parent, return the value in + /// the PHI node corresponding to PredBB. If not, return ourself. This is + /// useful if you want to know the value something has in a predecessor + /// block. Value *DoPHITranslation(const BasicBlock *CurBB, const BasicBlock *PredBB); const Value *DoPHITranslation(const BasicBlock *CurBB, @@ -443,11 +467,14 @@ public: return const_cast<Value*>(this)->DoPHITranslation(CurBB, PredBB); } - /// MaximumAlignment - This is the greatest alignment value supported by - /// load, store, and alloca instructions, and global values. + /// \brief The maximum alignment for instructions. + /// + /// This is the greatest alignment value supported by load, store, and alloca + /// instructions, and global values. static const unsigned MaximumAlignment = 1u << 29; - /// mutateType - Mutate the type of this Value to be of the specified type. + /// \brief Mutate the type of this Value to be of the specified type. + /// /// Note that this is an extremely dangerous operation which can create /// completely invalid IR very easily. It is strongly recommended that you /// recreate IR objects with the right types instead of mutating them in @@ -456,6 +483,37 @@ public: VTy = Ty; } + /// \brief Sort the use-list. + /// + /// Sorts the Value's use-list by Cmp using a stable mergesort. Cmp is + /// expected to compare two \a Use references. + template <class Compare> void sortUseList(Compare Cmp); + + /// \brief Reverse the use-list. + void reverseUseList(); + +private: + /// \brief Merge two lists together. + /// + /// Merges \c L and \c R using \c Cmp. To enable stable sorts, always pushes + /// "equal" items from L before items from R. + /// + /// \return the first element in the list. + /// + /// \note Completely ignores \a Use::Prev (doesn't read, doesn't update). + template <class Compare> + static Use *mergeUseLists(Use *L, Use *R, Compare Cmp) { + Use *Merged; + mergeUseListsImpl(L, R, &Merged, Cmp); + return Merged; + } + + /// \brief Tail-recursive helper for \a mergeUseLists(). + /// + /// \param[out] Next the first element in the list. + template <class Compare> + static void mergeUseListsImpl(Use *L, Use *R, Use **Next, Compare Cmp); + protected: unsigned short getSubclassDataFromValue() const { return SubclassData; } void setValueSubclassData(unsigned short D) { SubclassData = D; } @@ -472,6 +530,91 @@ void Use::set(Value *V) { if (V) V->addUse(*this); } +template <class Compare> void Value::sortUseList(Compare Cmp) { + if (!UseList || !UseList->Next) + // No need to sort 0 or 1 uses. + return; + + // Note: this function completely ignores Prev pointers until the end when + // they're fixed en masse. + + // Create a binomial vector of sorted lists, visiting uses one at a time and + // merging lists as necessary. + const unsigned MaxSlots = 32; + Use *Slots[MaxSlots]; + + // Collect the first use, turning it into a single-item list. + Use *Next = UseList->Next; + UseList->Next = nullptr; + unsigned NumSlots = 1; + Slots[0] = UseList; + + // Collect all but the last use. + while (Next->Next) { + Use *Current = Next; + Next = Current->Next; + + // Turn Current into a single-item list. + Current->Next = nullptr; + + // Save Current in the first available slot, merging on collisions. + unsigned I; + for (I = 0; I < NumSlots; ++I) { + if (!Slots[I]) + break; + + // Merge two lists, doubling the size of Current and emptying slot I. + // + // Since the uses in Slots[I] originally preceded those in Current, send + // Slots[I] in as the left parameter to maintain a stable sort. + Current = mergeUseLists(Slots[I], Current, Cmp); + Slots[I] = nullptr; + } + // Check if this is a new slot. + if (I == NumSlots) { + ++NumSlots; + assert(NumSlots <= MaxSlots && "Use list bigger than 2^32"); + } + + // Found an open slot. + Slots[I] = Current; + } + + // Merge all the lists together. + assert(Next && "Expected one more Use"); + assert(!Next->Next && "Expected only one Use"); + UseList = Next; + for (unsigned I = 0; I < NumSlots; ++I) + if (Slots[I]) + // Since the uses in Slots[I] originally preceded those in UseList, send + // Slots[I] in as the left parameter to maintain a stable sort. + UseList = mergeUseLists(Slots[I], UseList, Cmp); + + // Fix the Prev pointers. + for (Use *I = UseList, **Prev = &UseList; I; I = I->Next) { + I->setPrev(Prev); + Prev = &I->Next; + } +} + +template <class Compare> +void Value::mergeUseListsImpl(Use *L, Use *R, Use **Next, Compare Cmp) { + if (!L) { + *Next = R; + return; + } + if (!R) { + *Next = L; + return; + } + if (Cmp(*R, *L)) { + *Next = R; + mergeUseListsImpl(L, R->Next, &R->Next, Cmp); + return; + } + *Next = L; + mergeUseListsImpl(L->Next, R, &L->Next, Cmp); +} // isa - Provide some specializations of isa so that we don't have to include // the subtype header files to test to see if the value is a subclass... @@ -539,7 +682,8 @@ template <> struct isa_impl<GlobalObject, Value> { template <> struct isa_impl<MDNode, Value> { static inline bool doit(const Value &Val) { - return Val.getValueID() == Value::MDNodeVal; + return Val.getValueID() == Value::GenericMDNodeVal || + Val.getValueID() == Value::MDNodeFwdDeclVal; } }; |