aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/libs/llvm14/include/llvm/Analysis/PtrUseVisitor.h
blob: 47f3d84a62371555998a5c18135ba3a121e68feb (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
#pragma once

#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-parameter"
#endif

//===- PtrUseVisitor.h - InstVisitors over a pointers uses ------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
/// \file
/// This file provides a collection of visitors which walk the (instruction)
/// uses of a pointer. These visitors all provide the same essential behavior
/// as an InstVisitor with similar template-based flexibility and
/// implementation strategies.
///
/// These can be used, for example, to quickly analyze the uses of an alloca,
/// global variable, or function argument.
///
/// FIXME: Provide a variant which doesn't track offsets and is cheaper.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_PTRUSEVISITOR_H
#define LLVM_ANALYSIS_PTRUSEVISITOR_H

#include "llvm/ADT/APInt.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/InstVisitor.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/Support/Casting.h"
#include <algorithm>
#include <cassert>
#include <type_traits>

namespace llvm {

namespace detail {

/// Implementation of non-dependent functionality for \c PtrUseVisitor.
///
/// See \c PtrUseVisitor for the public interface and detailed comments about
/// usage. This class is just a helper base class which is not templated and
/// contains all common code to be shared between different instantiations of
/// PtrUseVisitor.
class PtrUseVisitorBase {
public:
  /// This class provides information about the result of a visit.
  ///
  /// After walking all the users (recursively) of a pointer, the basic
  /// infrastructure records some commonly useful information such as escape
  /// analysis and whether the visit completed or aborted early.
  class PtrInfo {
  public:
    PtrInfo() : AbortedInfo(nullptr, false), EscapedInfo(nullptr, false) {}

    /// Reset the pointer info, clearing all state.
    void reset() {
      AbortedInfo.setPointer(nullptr);
      AbortedInfo.setInt(false);
      EscapedInfo.setPointer(nullptr);
      EscapedInfo.setInt(false);
    }

    /// Did we abort the visit early?
    bool isAborted() const { return AbortedInfo.getInt(); }

    /// Is the pointer escaped at some point?
    bool isEscaped() const { return EscapedInfo.getInt(); }

    /// Get the instruction causing the visit to abort.
    /// \returns a pointer to the instruction causing the abort if one is
    /// available; otherwise returns null.
    Instruction *getAbortingInst() const { return AbortedInfo.getPointer(); }

    /// Get the instruction causing the pointer to escape.
    /// \returns a pointer to the instruction which escapes the pointer if one
    /// is available; otherwise returns null.
    Instruction *getEscapingInst() const { return EscapedInfo.getPointer(); }

    /// Mark the visit as aborted. Intended for use in a void return.
    /// \param I The instruction which caused the visit to abort, if available.
    void setAborted(Instruction *I = nullptr) {
      AbortedInfo.setInt(true);
      AbortedInfo.setPointer(I);
    }

    /// Mark the pointer as escaped. Intended for use in a void return.
    /// \param I The instruction which escapes the pointer, if available.
    void setEscaped(Instruction *I = nullptr) {
      EscapedInfo.setInt(true);
      EscapedInfo.setPointer(I);
    }

    /// Mark the pointer as escaped, and the visit as aborted. Intended
    /// for use in a void return.
    /// \param I The instruction which both escapes the pointer and aborts the
    /// visit, if available.
    void setEscapedAndAborted(Instruction *I = nullptr) {
      setEscaped(I);
      setAborted(I);
    }

  private:
    PointerIntPair<Instruction *, 1, bool> AbortedInfo, EscapedInfo;
  };

protected:
  const DataLayout &DL;

  /// \name Visitation infrastructure
  /// @{

  /// The info collected about the pointer being visited thus far.
  PtrInfo PI;

  /// A struct of the data needed to visit a particular use.
  ///
  /// This is used to maintain a worklist fo to-visit uses. This is used to
  /// make the visit be iterative rather than recursive.
  struct UseToVisit {
    using UseAndIsOffsetKnownPair = PointerIntPair<Use *, 1, bool>;

    UseAndIsOffsetKnownPair UseAndIsOffsetKnown;
    APInt Offset;
  };

  /// The worklist of to-visit uses.
  SmallVector<UseToVisit, 8> Worklist;

  /// A set of visited uses to break cycles in unreachable code.
  SmallPtrSet<Use *, 8> VisitedUses;

  /// @}

  /// \name Per-visit state
  /// This state is reset for each instruction visited.
  /// @{

  /// The use currently being visited.
  Use *U;

  /// True if we have a known constant offset for the use currently
  /// being visited.
  bool IsOffsetKnown;

  /// The constant offset of the use if that is known.
  APInt Offset;

  /// @}

  /// Note that the constructor is protected because this class must be a base
  /// class, we can't create instances directly of this class.
  PtrUseVisitorBase(const DataLayout &DL) : DL(DL) {}

  /// Enqueue the users of this instruction in the visit worklist.
  ///
  /// This will visit the users with the same offset of the current visit
  /// (including an unknown offset if that is the current state).
  void enqueueUsers(Instruction &I);

  /// Walk the operands of a GEP and adjust the offset as appropriate.
  ///
  /// This routine does the heavy lifting of the pointer walk by computing
  /// offsets and looking through GEPs.
  bool adjustOffsetForGEP(GetElementPtrInst &GEPI);
};

} // end namespace detail

/// A base class for visitors over the uses of a pointer value.
///
/// Once constructed, a user can call \c visit on a pointer value, and this
/// will walk its uses and visit each instruction using an InstVisitor. It also
/// provides visit methods which will recurse through any pointer-to-pointer
/// transformations such as GEPs and bitcasts.
///
/// During the visit, the current Use* being visited is available to the
/// subclass, as well as the current offset from the original base pointer if
/// known.
///
/// The recursive visit of uses is accomplished with a worklist, so the only
/// ordering guarantee is that an instruction is visited before any uses of it
/// are visited. Note that this does *not* mean before any of its users are
/// visited! This is because users can be visited multiple times due to
/// multiple, different uses of pointers derived from the same base.
///
/// A particular Use will only be visited once, but a User may be visited
/// multiple times, once per Use. This visits may notably have different
/// offsets.
///
/// All visit methods on the underlying InstVisitor return a boolean. This
/// return short-circuits the visit, stopping it immediately.
///
/// FIXME: Generalize this for all values rather than just instructions.
template <typename DerivedT>
class PtrUseVisitor : protected InstVisitor<DerivedT>,
                      public detail::PtrUseVisitorBase {
  friend class InstVisitor<DerivedT>;

  using Base = InstVisitor<DerivedT>;

public:
  PtrUseVisitor(const DataLayout &DL) : PtrUseVisitorBase(DL) {
    static_assert(std::is_base_of<PtrUseVisitor, DerivedT>::value,
                  "Must pass the derived type to this template!");
  }

  /// Recursively visit the uses of the given pointer.
  /// \returns An info struct about the pointer. See \c PtrInfo for details.
  PtrInfo visitPtr(Instruction &I) {
    // This must be a pointer type. Get an integer type suitable to hold
    // offsets on this pointer.
    // FIXME: Support a vector of pointers.
    assert(I.getType()->isPointerTy());
    IntegerType *IntIdxTy = cast<IntegerType>(DL.getIndexType(I.getType()));
    IsOffsetKnown = true;
    Offset = APInt(IntIdxTy->getBitWidth(), 0);
    PI.reset();

    // Enqueue the uses of this pointer.
    enqueueUsers(I);

    // Visit all the uses off the worklist until it is empty.
    while (!Worklist.empty()) {
      UseToVisit ToVisit = Worklist.pop_back_val();
      U = ToVisit.UseAndIsOffsetKnown.getPointer();
      IsOffsetKnown = ToVisit.UseAndIsOffsetKnown.getInt();
      if (IsOffsetKnown)
        Offset = std::move(ToVisit.Offset);

      Instruction *I = cast<Instruction>(U->getUser());
      static_cast<DerivedT*>(this)->visit(I);
      if (PI.isAborted())
        break;
    }
    return PI;
  }

protected:
  void visitStoreInst(StoreInst &SI) {
    if (SI.getValueOperand() == U->get())
      PI.setEscaped(&SI);
  }

  void visitBitCastInst(BitCastInst &BC) {
    enqueueUsers(BC);
  }

  void visitAddrSpaceCastInst(AddrSpaceCastInst &ASC) {
    enqueueUsers(ASC);
  }

  void visitPtrToIntInst(PtrToIntInst &I) {
    PI.setEscaped(&I);
  }

  void visitGetElementPtrInst(GetElementPtrInst &GEPI) {
    if (GEPI.use_empty())
      return;

    // If we can't walk the GEP, clear the offset.
    if (!adjustOffsetForGEP(GEPI)) {
      IsOffsetKnown = false;
      Offset = APInt();
    }

    // Enqueue the users now that the offset has been adjusted.
    enqueueUsers(GEPI);
  }

  // No-op intrinsics which we know don't escape the pointer to logic in
  // some other function.
  void visitDbgInfoIntrinsic(DbgInfoIntrinsic &I) {}
  void visitMemIntrinsic(MemIntrinsic &I) {}
  void visitIntrinsicInst(IntrinsicInst &II) {
    switch (II.getIntrinsicID()) {
    default:
      return Base::visitIntrinsicInst(II);

    case Intrinsic::lifetime_start:
    case Intrinsic::lifetime_end:
      return; // No-op intrinsics.
    }
  }

  // Generically, arguments to calls and invokes escape the pointer to some
  // other function. Mark that.
  void visitCallBase(CallBase &CB) {
    PI.setEscaped(&CB);
    Base::visitCallBase(CB);
  }
};

} // end namespace llvm

#endif // LLVM_ANALYSIS_PTRUSEVISITOR_H

#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif