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