LLVM  6.0.0svn
Use.h
Go to the documentation of this file.
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"
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 /// \brief 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  /// \brief 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.
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.
79 
80  /// Pointer traits for the Prev PointerIntPair. This ensures we always use
81  /// the two LSBs regardless of pointer alignment on different targets.
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  ~Use() {
95  if (Val)
96  removeFromList();
97  }
98 
99  enum PrevPtrTag { zeroDigitTag, oneDigitTag, stopTag, fullStopTag };
100 
101  /// Constructor
102  Use(PrevPtrTag tag) { Prev.setInt(tag); }
103 
104 public:
105  friend class Value;
106 
107  operator Value *() const { return Val; }
108  Value *get() const { return Val; }
109 
110  /// \brief 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  Value *operator->() { return Val; }
122  const Value *operator->() const { return Val; }
123 
124  Use *getNext() const { return Next; }
125 
126  /// \brief Return the operand # of this use in its User.
127  unsigned getOperandNo() const;
128 
129  /// \brief 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  /// \brief 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;
145 
146  void setPrev(Use **NewPrev) { Prev.setPointer(NewPrev); }
147 
148  void addToList(Use **List) {
149  Next = *List;
150  if (Next)
151  Next->setPrev(&Next);
152  setPrev(List);
153  *List = this;
154  }
155 
156  void removeFromList() {
157  Use **StrippedPrev = Prev.getPointer();
158  *StrippedPrev = Next;
159  if (Next)
160  Next->setPrev(StrippedPrev);
161  }
162 };
163 
164 /// \brief 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  static SimpleType getSimplifiedValue(Use &Val) { return Val.get(); }
170 };
171 template <> struct simplify_type<const Use> {
172  using SimpleType = /*const*/ Value *;
173 
174  static SimpleType getSimplifiedValue(const Use &Val) { return Val.get(); }
175 };
176 
177 // Create wrappers for C Binding types (see CBindingWrapping.h).
179 
180 } // end namespace llvm
181 
182 #endif // LLVM_IR_USE_H
Use(const Use &U)=delete
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
PointerTy getPointer() const
static void * getAsVoidPointer(User *P)
Definition: Use.h:67
static void * getAsVoidPointer(Use **P)
Definition: Use.h:83
Value * get() const
Definition: Use.h:108
void setPointer(PointerTy PtrVal)
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
User * getUser() const LLVM_READONLY
Returns the User that contains this Use.
Definition: Use.cpp:41
static Use ** getFromVoidPointer(void *P)
Definition: Use.h:85
struct LLVMOpaqueUse * LLVMUseRef
Used to get the users and usees of a Value.
Definition: Types.h:123
unsigned getOperandNo() const
Return the operand # of this use in its User.
Definition: Use.cpp:48
const Value * operator->() const
Definition: Use.h:122
Pointer traits for the Prev PointerIntPair.
Definition: Use.h:82
static User * getFromVoidPointer(void *P)
Definition: Use.h:69
#define P(N)
PointerIntPair - This class implements a pair of a pointer and small integer.
static Use * initTags(Use *Start, Use *Stop)
Initializes the waymarking tags on an array of Uses.
Definition: Use.cpp:57
void swap(Use &RHS)
Provide a fast substitute to std::swap<Use> that also works with less standard-compliant compilers...
Definition: Use.cpp:17
Value * operator->()
Definition: Use.h:121
DEFINE_SIMPLE_CONVERSION_FUNCTIONS(std::shared_ptr< Module >, LLVMSharedModuleRef) namespace detail
static SimpleType getSimplifiedValue(const Use &Val)
Definition: Use.h:174
could "use" a pointer
const NodeList & List
Definition: RDFGraph.cpp:210
#define LLVM_READONLY
Definition: Compiler.h:168
aarch64 promote const
LLVM Value Representation.
Definition: Value.h:73
static SimpleType getSimplifiedValue(Use &Val)
Definition: Use.h:169
Use * getNext() const
Definition: Use.h:124
Pointer traits for the UserRef PointerIntPair.
Definition: Use.h:66
Value * operator=(Value *RHS)
Definition: Value.h:683
static void zap(Use *Start, const Use *Stop, bool del=false)
Destroys Use operands when the number of operands of a User changes.
Definition: Use.cpp:87