1 //===- llvm/Use.h - Definition of the Use class -----------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 /// \file
9 ///
10 /// This defines the Use class.  The Use class represents the operand of an
11 /// instruction or some other User instance which refers to a Value.  The Use
12 /// class keeps the "use list" of the referenced value up to date.
13 ///
14 /// Pointer tagging is used to efficiently find the User corresponding to a Use
15 /// without having to store a User pointer in every Use. A User is preceded in
16 /// memory by all the Uses corresponding to its operands, and the low bits of
17 /// one of the fields (Prev) of the Use class are used to encode offsets to be
18 /// able to find that User given a pointer to any Use. For details, see:
19 ///
20 ///   http://www.llvm.org/docs/ProgrammersManual.html#UserLayout
21 ///
22 //===----------------------------------------------------------------------===//
23 
24 #ifndef LLVM_IR_USE_H
25 #define LLVM_IR_USE_H
26 
27 #include "llvm-c/Types.h"
28 #include "llvm/ADT/PointerIntPair.h"
29 #include "llvm/Support/CBindingWrapping.h"
30 #include "llvm/Support/Compiler.h"
31 
32 namespace llvm {
33 
34 template <typename> struct simplify_type;
35 class User;
36 class Value;
37 
38 /// A Use represents the edge between a Value definition and its users.
39 ///
40 /// This is notionally a two-dimensional linked list. It supports traversing
41 /// all of the uses for a particular value definition. It also supports jumping
42 /// directly to the used value when we arrive from the User's operands, and
43 /// jumping directly to the User when we arrive from the Value's uses.
44 ///
45 /// The pointer to the used Value is explicit, and the pointer to the User is
46 /// implicit. The implicit pointer is found via a waymarking algorithm
47 /// described in the programmer's manual:
48 ///
49 ///   http://www.llvm.org/docs/ProgrammersManual.html#the-waymarking-algorithm
50 ///
51 /// This is essentially the single most memory intensive object in LLVM because
52 /// of the number of uses in the system. At the same time, the constant time
53 /// operations it allows are essential to many optimizations having reasonable
54 /// time complexity.
55 class Use {
56 public:
57   Use(const Use &U) = delete;
58 
59   /// Provide a fast substitute to std::swap<Use>
60   /// that also works with less standard-compliant compilers
61   void swap(Use &RHS);
62 
63   /// Pointer traits for the UserRef PointerIntPair. This ensures we always
64   /// use the LSB regardless of pointer alignment on different targets.
65   struct UserRefPointerTraits {
66     static inline void *getAsVoidPointer(User *P) { return P; }
67 
68     static inline User *getFromVoidPointer(void *P) {
69       return (User *)P;
70     }
71 
72     enum { NumLowBitsAvailable = 1 };
73   };
74 
75   // A type for the word following an array of hung-off Uses in memory, which is
76   // a pointer back to their User with the bottom bit set.
77   using UserRef = PointerIntPair<User *, 1, unsigned, UserRefPointerTraits>;
78 
79   /// Pointer traits for the Prev PointerIntPair. This ensures we always use
80   /// the two LSBs regardless of pointer alignment on different targets.
81   struct PrevPointerTraits {
82     static inline void *getAsVoidPointer(Use **P) { return P; }
83 
84     static inline Use **getFromVoidPointer(void *P) {
85       return (Use **)P;
86     }
87 
88     enum { NumLowBitsAvailable = 2 };
89   };
90 
91 private:
92   /// Destructor - Only for zap()
93   ~Use() {
94     if (Val)
95       removeFromList();
96   }
97 
98   enum PrevPtrTag { zeroDigitTag, oneDigitTag, stopTag, fullStopTag };
99 
100   /// Constructor
101   Use(PrevPtrTag tag) { Prev.setInt(tag); }
102 
103 public:
104   friend class Value;
105 
106   operator Value *() const { return Val; }
107   Value *get() const { return Val; }
108 
109   /// Returns the User that contains this Use.
110   ///
111   /// For an instruction operand, for example, this will return the
112   /// instruction.
113   User *getUser() const LLVM_READONLY;
114 
115   inline void set(Value *Val);
116 
117   inline Value *operator=(Value *RHS);
118   inline const Use &operator=(const Use &RHS);
119 
120   Value *operator->() { return Val; }
121   const Value *operator->() const { return Val; }
122 
123   Use *getNext() const { return Next; }
124 
125   /// Return the operand # of this use in its User.
126   unsigned getOperandNo() const;
127 
128   /// Initializes the waymarking tags on an array of Uses.
129   ///
130   /// This sets up the array of Uses such that getUser() can find the User from
131   /// any of those Uses.
132   static Use *initTags(Use *Start, Use *Stop);
133 
134   /// Destroys Use operands when the number of operands of
135   /// a User changes.
136   static void zap(Use *Start, const Use *Stop, bool del = false);
137 
138 private:
139   const Use *getImpliedUser() const LLVM_READONLY;
140 
141   Value *Val = nullptr;
142   Use *Next = nullptr;
143   PointerIntPair<Use **, 2, PrevPtrTag, PrevPointerTraits> Prev;
144 
145   void setPrev(Use **NewPrev) { Prev.setPointer(NewPrev); }
146 
147   void addToList(Use **List) {
148     Next = *List;
149     if (Next)
150       Next->setPrev(&Next);
151     setPrev(List);
152     *List = this;
153   }
154 
155   void removeFromList() {
156     Use **StrippedPrev = Prev.getPointer();
157     *StrippedPrev = Next;
158     if (Next)
159       Next->setPrev(StrippedPrev);
160   }
161 };
162 
163 /// Allow clients to treat uses just like values when using
164 /// casting operators.
165 template <> struct simplify_type<Use> {
166   using SimpleType = Value *;
167 
168   static SimpleType getSimplifiedValue(Use &Val) { return Val.get(); }
169 };
170 template <> struct simplify_type<const Use> {
171   using SimpleType = /*const*/ Value *;
172 
173   static SimpleType getSimplifiedValue(const Use &Val) { return Val.get(); }
174 };
175 
176 // Create wrappers for C Binding types (see CBindingWrapping.h).
177 DEFINE_SIMPLE_CONVERSION_FUNCTIONS(Use, LLVMUseRef)
178 
179 } // end namespace llvm
180 
181 #endif // LLVM_IR_USE_H
182