Coverage Report

Created: 2019-03-24 22:13

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