1//===- PtrUseVisitor.h - InstVisitors over a pointers uses ------*- 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/// This file provides a collection of visitors which walk the (instruction)
11/// uses of a pointer. These visitors all provide the same essential behavior
12/// as an InstVisitor with similar template-based flexibility and
13/// implementation strategies.
14///
15/// These can be used, for example, to quickly analyze the uses of an alloca,
16/// global variable, or function argument.
17///
18/// FIXME: Provide a variant which doesn't track offsets and is cheaper.
19///
20//===----------------------------------------------------------------------===//
21
22#ifndef LLVM_ANALYSIS_PTRUSEVISITOR_H
23#define LLVM_ANALYSIS_PTRUSEVISITOR_H
24
25#include "llvm/ADT/APInt.h"
26#include "llvm/ADT/SmallPtrSet.h"
27#include "llvm/ADT/SmallVector.h"
28#include "llvm/IR/DataLayout.h"
29#include "llvm/IR/InstVisitor.h"
30#include "llvm/IR/IntrinsicInst.h"
31#include "llvm/Support/Compiler.h"
32
33namespace llvm {
34
35namespace detail {
36/// \brief Implementation of non-dependent functionality for \c PtrUseVisitor.
37///
38/// See \c PtrUseVisitor for the public interface and detailed comments about
39/// usage. This class is just a helper base class which is not templated and
40/// contains all common code to be shared between different instantiations of
41/// PtrUseVisitor.
42class PtrUseVisitorBase {
43public:
44  /// \brief This class provides information about the result of a visit.
45  ///
46  /// After walking all the users (recursively) of a pointer, the basic
47  /// infrastructure records some commonly useful information such as escape
48  /// analysis and whether the visit completed or aborted early.
49  class PtrInfo {
50  public:
51    PtrInfo() : AbortedInfo(nullptr, false), EscapedInfo(nullptr, false) {}
52
53    /// \brief Reset the pointer info, clearing all state.
54    void reset() {
55      AbortedInfo.setPointer(nullptr);
56      AbortedInfo.setInt(false);
57      EscapedInfo.setPointer(nullptr);
58      EscapedInfo.setInt(false);
59    }
60
61    /// \brief Did we abort the visit early?
62    bool isAborted() const { return AbortedInfo.getInt(); }
63
64    /// \brief Is the pointer escaped at some point?
65    bool isEscaped() const { return EscapedInfo.getInt(); }
66
67    /// \brief Get the instruction causing the visit to abort.
68    /// \returns a pointer to the instruction causing the abort if one is
69    /// available; otherwise returns null.
70    Instruction *getAbortingInst() const { return AbortedInfo.getPointer(); }
71
72    /// \brief Get the instruction causing the pointer to escape.
73    /// \returns a pointer to the instruction which escapes the pointer if one
74    /// is available; otherwise returns null.
75    Instruction *getEscapingInst() const { return EscapedInfo.getPointer(); }
76
77    /// \brief Mark the visit as aborted. Intended for use in a void return.
78    /// \param I The instruction which caused the visit to abort, if available.
79    void setAborted(Instruction *I = nullptr) {
80      AbortedInfo.setInt(true);
81      AbortedInfo.setPointer(I);
82    }
83
84    /// \brief Mark the pointer as escaped. Intended for use in a void return.
85    /// \param I The instruction which escapes the pointer, if available.
86    void setEscaped(Instruction *I = nullptr) {
87      EscapedInfo.setInt(true);
88      EscapedInfo.setPointer(I);
89    }
90
91    /// \brief Mark the pointer as escaped, and the visit as aborted. Intended
92    /// for use in a void return.
93    /// \param I The instruction which both escapes the pointer and aborts the
94    /// visit, if available.
95    void setEscapedAndAborted(Instruction *I = nullptr) {
96      setEscaped(I);
97      setAborted(I);
98    }
99
100  private:
101    PointerIntPair<Instruction *, 1, bool> AbortedInfo, EscapedInfo;
102  };
103
104protected:
105  const DataLayout &DL;
106
107  /// \name Visitation infrastructure
108  /// @{
109
110  /// \brief The info collected about the pointer being visited thus far.
111  PtrInfo PI;
112
113  /// \brief A struct of the data needed to visit a particular use.
114  ///
115  /// This is used to maintain a worklist fo to-visit uses. This is used to
116  /// make the visit be iterative rather than recursive.
117  struct UseToVisit {
118    typedef PointerIntPair<Use *, 1, bool> UseAndIsOffsetKnownPair;
119    UseAndIsOffsetKnownPair UseAndIsOffsetKnown;
120    APInt Offset;
121  };
122
123  /// \brief The worklist of to-visit uses.
124  SmallVector<UseToVisit, 8> Worklist;
125
126  /// \brief A set of visited uses to break cycles in unreachable code.
127  SmallPtrSet<Use *, 8> VisitedUses;
128
129  /// @}
130
131
132  /// \name Per-visit state
133  /// This state is reset for each instruction visited.
134  /// @{
135
136  /// \brief The use currently being visited.
137  Use *U;
138
139  /// \brief True if we have a known constant offset for the use currently
140  /// being visited.
141  bool IsOffsetKnown;
142
143  /// \brief The constant offset of the use if that is known.
144  APInt Offset;
145
146  /// @}
147
148
149  /// Note that the constructor is protected because this class must be a base
150  /// class, we can't create instances directly of this class.
151  PtrUseVisitorBase(const DataLayout &DL) : DL(DL) {}
152
153  /// \brief Enqueue the users of this instruction in the visit worklist.
154  ///
155  /// This will visit the users with the same offset of the current visit
156  /// (including an unknown offset if that is the current state).
157  void enqueueUsers(Instruction &I);
158
159  /// \brief Walk the operands of a GEP and adjust the offset as appropriate.
160  ///
161  /// This routine does the heavy lifting of the pointer walk by computing
162  /// offsets and looking through GEPs.
163  bool adjustOffsetForGEP(GetElementPtrInst &GEPI);
164};
165} // end namespace detail
166
167/// \brief A base class for visitors over the uses of a pointer value.
168///
169/// Once constructed, a user can call \c visit on a pointer value, and this
170/// will walk its uses and visit each instruction using an InstVisitor. It also
171/// provides visit methods which will recurse through any pointer-to-pointer
172/// transformations such as GEPs and bitcasts.
173///
174/// During the visit, the current Use* being visited is available to the
175/// subclass, as well as the current offset from the original base pointer if
176/// known.
177///
178/// The recursive visit of uses is accomplished with a worklist, so the only
179/// ordering guarantee is that an instruction is visited before any uses of it
180/// are visited. Note that this does *not* mean before any of its users are
181/// visited! This is because users can be visited multiple times due to
182/// multiple, different uses of pointers derived from the same base.
183///
184/// A particular Use will only be visited once, but a User may be visited
185/// multiple times, once per Use. This visits may notably have different
186/// offsets.
187///
188/// All visit methods on the underlying InstVisitor return a boolean. This
189/// return short-circuits the visit, stopping it immediately.
190///
191/// FIXME: Generalize this for all values rather than just instructions.
192template <typename DerivedT>
193class PtrUseVisitor : protected InstVisitor<DerivedT>,
194                      public detail::PtrUseVisitorBase {
195  friend class InstVisitor<DerivedT>;
196  typedef InstVisitor<DerivedT> Base;
197
198public:
199  PtrUseVisitor(const DataLayout &DL) : PtrUseVisitorBase(DL) {}
200
201  /// \brief Recursively visit the uses of the given pointer.
202  /// \returns An info struct about the pointer. See \c PtrInfo for details.
203  PtrInfo visitPtr(Instruction &I) {
204    // This must be a pointer type. Get an integer type suitable to hold
205    // offsets on this pointer.
206    // FIXME: Support a vector of pointers.
207    assert(I.getType()->isPointerTy());
208    IntegerType *IntPtrTy = cast<IntegerType>(DL.getIntPtrType(I.getType()));
209    IsOffsetKnown = true;
210    Offset = APInt(IntPtrTy->getBitWidth(), 0);
211    PI.reset();
212
213    // Enqueue the uses of this pointer.
214    enqueueUsers(I);
215
216    // Visit all the uses off the worklist until it is empty.
217    while (!Worklist.empty()) {
218      UseToVisit ToVisit = Worklist.pop_back_val();
219      U = ToVisit.UseAndIsOffsetKnown.getPointer();
220      IsOffsetKnown = ToVisit.UseAndIsOffsetKnown.getInt();
221      if (IsOffsetKnown)
222        Offset = std::move(ToVisit.Offset);
223
224      Instruction *I = cast<Instruction>(U->getUser());
225      static_cast<DerivedT*>(this)->visit(I);
226      if (PI.isAborted())
227        break;
228    }
229    return PI;
230  }
231
232protected:
233  void visitStoreInst(StoreInst &SI) {
234    if (SI.getValueOperand() == U->get())
235      PI.setEscaped(&SI);
236  }
237
238  void visitBitCastInst(BitCastInst &BC) {
239    enqueueUsers(BC);
240  }
241
242  void visitPtrToIntInst(PtrToIntInst &I) {
243    PI.setEscaped(&I);
244  }
245
246  void visitGetElementPtrInst(GetElementPtrInst &GEPI) {
247    if (GEPI.use_empty())
248      return;
249
250    // If we can't walk the GEP, clear the offset.
251    if (!adjustOffsetForGEP(GEPI)) {
252      IsOffsetKnown = false;
253      Offset = APInt();
254    }
255
256    // Enqueue the users now that the offset has been adjusted.
257    enqueueUsers(GEPI);
258  }
259
260  // No-op intrinsics which we know don't escape the pointer to to logic in
261  // some other function.
262  void visitDbgInfoIntrinsic(DbgInfoIntrinsic &I) {}
263  void visitMemIntrinsic(MemIntrinsic &I) {}
264  void visitIntrinsicInst(IntrinsicInst &II) {
265    switch (II.getIntrinsicID()) {
266    default:
267      return Base::visitIntrinsicInst(II);
268
269    case Intrinsic::lifetime_start:
270    case Intrinsic::lifetime_end:
271      return; // No-op intrinsics.
272    }
273  }
274
275  // Generically, arguments to calls and invokes escape the pointer to some
276  // other function. Mark that.
277  void visitCallSite(CallSite CS) {
278    PI.setEscaped(CS.getInstruction());
279    Base::visitCallSite(CS);
280  }
281};
282
283}
284
285#endif
286