1 //===-- llvm/Use.h - Definition of the Use class ----------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// This defines the Use class. The Use class represents the operand of an
12 /// instruction or some other User instance which refers to a Value. The Use
13 /// class keeps the "use list" of the referenced value up to date.
15 /// Pointer tagging is used to efficiently find the User corresponding to a Use
16 /// without having to store a User pointer in every Use. A User is preceded in
17 /// memory by all the Uses corresponding to its operands, and the low bits of
18 /// one of the fields (Prev) of the Use class are used to encode offsets to be
19 /// able to find that User given a pointer to any Use. For details, see:
21 /// http://www.llvm.org/docs/ProgrammersManual.html#UserLayout
23 //===----------------------------------------------------------------------===//
28 #include "llvm/ADT/PointerIntPair.h"
29 #include "llvm/Support/CBindingWrapping.h"
30 #include "llvm/Support/Compiler.h"
39 template <typename> struct simplify_type;
41 // Use** is only 4-byte aligned.
42 template <> class PointerLikeTypeTraits<Use **> {
44 static inline void *getAsVoidPointer(Use **P) { return P; }
45 static inline Use **getFromVoidPointer(void *P) {
46 return static_cast<Use **>(P);
48 enum { NumLowBitsAvailable = 2 };
51 /// \brief A Use represents the edge between a Value definition and its users.
53 /// This is notionally a two-dimensional linked list. It supports traversing
54 /// all of the uses for a particular value definition. It also supports jumping
55 /// directly to the used value when we arrive from the User's operands, and
56 /// jumping directly to the User when we arrive from the Value's uses.
58 /// The pointer to the used Value is explicit, and the pointer to the User is
59 /// implicit. The implicit pointer is found via a waymarking algorithm
60 /// described in the programmer's manual:
62 /// http://www.llvm.org/docs/ProgrammersManual.html#the-waymarking-algorithm
64 /// This is essentially the single most memory intensive object in LLVM because
65 /// of the number of uses in the system. At the same time, the constant time
66 /// operations it allows are essential to many optimizations having reasonable
70 /// \brief Provide a fast substitute to std::swap<Use>
71 /// that also works with less standard-compliant compilers
74 // A type for the word following an array of hung-off Uses in memory, which is
75 // a pointer back to their User with the bottom bit set.
76 typedef PointerIntPair<User *, 1, unsigned> UserRef;
79 Use(const Use &U) = delete;
81 /// Destructor - Only for zap()
87 enum PrevPtrTag { zeroDigitTag, oneDigitTag, stopTag, fullStopTag };
90 Use(PrevPtrTag tag) : Val(nullptr) { Prev.setInt(tag); }
93 operator Value *() const { return Val; }
94 Value *get() const { return Val; }
96 /// \brief Returns the User that contains this Use.
98 /// For an instruction operand, for example, this will return the
100 User *getUser() const;
102 inline void set(Value *Val);
104 Value *operator=(Value *RHS) {
108 const Use &operator=(const Use &RHS) {
113 Value *operator->() { return Val; }
114 const Value *operator->() const { return Val; }
116 Use *getNext() const { return Next; }
118 /// \brief Return the operand # of this use in its User.
119 unsigned getOperandNo() const;
121 /// \brief Initializes the waymarking tags on an array of Uses.
123 /// This sets up the array of Uses such that getUser() can find the User from
124 /// any of those Uses.
125 static Use *initTags(Use *Start, Use *Stop);
127 /// \brief Destroys Use operands when the number of operands of
129 static void zap(Use *Start, const Use *Stop, bool del = false);
132 const Use *getImpliedUser() const;
136 PointerIntPair<Use **, 2, PrevPtrTag> Prev;
138 void setPrev(Use **NewPrev) { Prev.setPointer(NewPrev); }
139 void addToList(Use **List) {
142 Next->setPrev(&Next);
146 void removeFromList() {
147 Use **StrippedPrev = Prev.getPointer();
148 *StrippedPrev = Next;
150 Next->setPrev(StrippedPrev);
156 /// \brief Allow clients to treat uses just like values when using
157 /// casting operators.
158 template <> struct simplify_type<Use> {
159 typedef Value *SimpleType;
160 static SimpleType getSimplifiedValue(Use &Val) { return Val.get(); }
162 template <> struct simplify_type<const Use> {
163 typedef /*const*/ Value *SimpleType;
164 static SimpleType getSimplifiedValue(const Use &Val) { return Val.get(); }
167 // Create wrappers for C Binding types (see CBindingWrapping.h).
168 DEFINE_SIMPLE_CONVERSION_FUNCTIONS(Use, LLVMUseRef)