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