Coverage Report

Created: 2018-09-25 00:18

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