LLVM  16.0.0git
CaptureTracking.h
Go to the documentation of this file.
1 //===----- llvm/Analysis/CaptureTracking.h - Pointer capture ----*- 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 // This file contains routines that help determine which pointers are captured.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_ANALYSIS_CAPTURETRACKING_H
14 #define LLVM_ANALYSIS_CAPTURETRACKING_H
15 
16 #include "llvm/ADT/DenseMap.h"
18 
19 namespace llvm {
20 
21  class Value;
22  class Use;
23  class DataLayout;
24  class Instruction;
25  class DominatorTree;
26  class LoopInfo;
27  class Function;
28  template <typename T> class SmallPtrSetImpl;
29 
30  /// getDefaultMaxUsesToExploreForCaptureTracking - Return default value of
31  /// the maximal number of uses to explore before giving up. It is used by
32  /// PointerMayBeCaptured family analysis.
34 
35  /// PointerMayBeCaptured - Return true if this pointer value may be captured
36  /// by the enclosing function (which is required to exist). This routine can
37  /// be expensive, so consider caching the results. The boolean ReturnCaptures
38  /// specifies whether returning the value (or part of it) from the function
39  /// counts as capturing it or not. The boolean StoreCaptures specified
40  /// whether storing the value (or part of it) into memory anywhere
41  /// automatically counts as capturing it or not.
42  /// MaxUsesToExplore specifies how many uses the analysis should explore for
43  /// one value before giving up due too "too many uses". If MaxUsesToExplore
44  /// is zero, a default value is assumed.
45  bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures,
46  bool StoreCaptures, unsigned MaxUsesToExplore = 0);
47 
48  /// Variant of the above function which accepts a set of Values that are
49  /// ephemeral and cannot cause pointers to escape.
50  bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures,
51  bool StoreCaptures,
52  const SmallPtrSetImpl<const Value *> &EphValues,
53  unsigned MaxUsesToExplore = 0);
54 
55  /// PointerMayBeCapturedBefore - Return true if this pointer value may be
56  /// captured by the enclosing function (which is required to exist). If a
57  /// DominatorTree is provided, only captures which happen before the given
58  /// instruction are considered. This routine can be expensive, so consider
59  /// caching the results. The boolean ReturnCaptures specifies whether
60  /// returning the value (or part of it) from the function counts as capturing
61  /// it or not. The boolean StoreCaptures specified whether storing the value
62  /// (or part of it) into memory anywhere automatically counts as capturing it
63  /// or not. Captures by the provided instruction are considered if the
64  /// final parameter is true.
65  /// MaxUsesToExplore specifies how many uses the analysis should explore for
66  /// one value before giving up due too "too many uses". If MaxUsesToExplore
67  /// is zero, a default value is assumed.
68  bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures,
69  bool StoreCaptures, const Instruction *I,
70  const DominatorTree *DT,
71  bool IncludeI = false,
72  unsigned MaxUsesToExplore = 0,
73  const LoopInfo *LI = nullptr);
74 
75  // Returns the 'earliest' instruction that captures \p V in \F. An instruction
76  // A is considered earlier than instruction B, if A dominates B. If 2 escapes
77  // do not dominate each other, the terminator of the common dominator is
78  // chosen. If not all uses can be analyzed, the earliest escape is set to
79  // the first instruction in the function entry block. If \p V does not escape,
80  // nullptr is returned. Note that the caller of the function has to ensure
81  // that the instruction the result value is compared against is not in a
82  // cycle.
83  Instruction *
84  FindEarliestCapture(const Value *V, Function &F, bool ReturnCaptures,
85  bool StoreCaptures, const DominatorTree &DT,
86  const SmallPtrSetImpl<const Value *> &EphValues,
87  unsigned MaxUsesToExplore = 0);
88 
89  /// This callback is used in conjunction with PointerMayBeCaptured. In
90  /// addition to the interface here, you'll need to provide your own getters
91  /// to see whether anything was captured.
92  struct CaptureTracker {
93  virtual ~CaptureTracker();
94 
95  /// tooManyUses - The depth of traversal has breached a limit. There may be
96  /// capturing instructions that will not be passed into captured().
97  virtual void tooManyUses() = 0;
98 
99  /// shouldExplore - This is the use of a value derived from the pointer.
100  /// To prune the search (ie., assume that none of its users could possibly
101  /// capture) return false. To search it, return true.
102  ///
103  /// U->getUser() is always an Instruction.
104  virtual bool shouldExplore(const Use *U);
105 
106  /// captured - Information about the pointer was captured by the user of
107  /// use U. Return true to stop the traversal or false to continue looking
108  /// for more capturing instructions.
109  virtual bool captured(const Use *U) = 0;
110 
111  /// isDereferenceableOrNull - Overload to allow clients with additional
112  /// knowledge about pointer dereferenceability to provide it and thereby
113  /// avoid conservative responses when a pointer is compared to null.
114  virtual bool isDereferenceableOrNull(Value *O, const DataLayout &DL);
115  };
116 
117  /// Types of use capture kinds, see \p DetermineUseCaptureKind.
118  enum class UseCaptureKind {
119  NO_CAPTURE,
120  MAY_CAPTURE,
121  PASSTHROUGH,
122  };
123 
124  /// Determine what kind of capture behaviour \p U may exhibit.
125  ///
126  /// A use can be no-capture, a use can potentially capture, or a use can be
127  /// passthrough such that the uses of the user or \p U should be inspected.
128  /// The \p IsDereferenceableOrNull callback is used to rule out capturing for
129  /// certain comparisons.
131  DetermineUseCaptureKind(const Use &U,
132  llvm::function_ref<bool(Value *, const DataLayout &)>
133  IsDereferenceableOrNull);
134 
135  /// PointerMayBeCaptured - Visit the value and the values derived from it and
136  /// find values which appear to be capturing the pointer value. This feeds
137  /// results into and is controlled by the CaptureTracker object.
138  /// MaxUsesToExplore specifies how many uses the analysis should explore for
139  /// one value before giving up due too "too many uses". If MaxUsesToExplore
140  /// is zero, a default value is assumed.
141  void PointerMayBeCaptured(const Value *V, CaptureTracker *Tracker,
142  unsigned MaxUsesToExplore = 0);
143 
144  /// Returns true if the pointer is to a function-local object that never
145  /// escapes from the function.
147  const Value *V,
148  SmallDenseMap<const Value *, bool, 8> *IsCapturedCache = nullptr);
149 } // end namespace llvm
150 
151 #endif
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::getDefaultMaxUsesToExploreForCaptureTracking
unsigned getDefaultMaxUsesToExploreForCaptureTracking()
getDefaultMaxUsesToExploreForCaptureTracking - Return default value of the maximal number of uses to ...
Definition: CaptureTracking.cpp:52
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::isNonEscapingLocalObject
bool isNonEscapingLocalObject(const Value *V, SmallDenseMap< const Value *, bool, 8 > *IsCapturedCache=nullptr)
Returns true if the pointer is to a function-local object that never escapes from the function.
Definition: CaptureTracking.cpp:488
llvm::UseCaptureKind
UseCaptureKind
Types of use capture kinds, see DetermineUseCaptureKind.
Definition: CaptureTracking.h:118
llvm::CaptureTracker
This callback is used in conjunction with PointerMayBeCaptured.
Definition: CaptureTracking.h:92
llvm::CaptureTracker::captured
virtual bool captured(const Use *U)=0
captured - Information about the pointer was captured by the user of use U.
llvm::UseCaptureKind::MAY_CAPTURE
@ MAY_CAPTURE
DenseMap.h
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::CaptureTracker::~CaptureTracker
virtual ~CaptureTracker()
llvm::UseCaptureKind::NO_CAPTURE
@ NO_CAPTURE
llvm::CaptureTracker::shouldExplore
virtual bool shouldExplore(const Use *U)
shouldExplore - This is the use of a value derived from the pointer.
Definition: CaptureTracking.cpp:58
llvm::CaptureTracker::isDereferenceableOrNull
virtual bool isDereferenceableOrNull(Value *O, const DataLayout &DL)
isDereferenceableOrNull - Overload to allow clients with additional knowledge about pointer dereferen...
Definition: CaptureTracking.cpp:60
STLFunctionalExtras.h
llvm::UseCaptureKind::PASSTHROUGH
@ PASSTHROUGH
llvm::DetermineUseCaptureKind
UseCaptureKind DetermineUseCaptureKind(const Use &U, llvm::function_ref< bool(Value *, const DataLayout &)> IsDereferenceableOrNull)
Determine what kind of capture behaviour U may exhibit.
Definition: CaptureTracking.cpp:311
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::FindEarliestCapture
Instruction * FindEarliestCapture(const Value *V, Function &F, bool ReturnCaptures, bool StoreCaptures, const DominatorTree &DT, const SmallPtrSetImpl< const Value * > &EphValues, unsigned MaxUsesToExplore=0)
Definition: CaptureTracking.cpp:294
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:264
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::PointerMayBeCaptured
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
Definition: CaptureTracking.cpp:229
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::CaptureTracker::tooManyUses
virtual void tooManyUses()=0
tooManyUses - The depth of traversal has breached a limit.
llvm::PointerMayBeCapturedBefore
bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, bool StoreCaptures, const Instruction *I, const DominatorTree *DT, bool IncludeI=false, unsigned MaxUsesToExplore=0, const LoopInfo *LI=nullptr)
PointerMayBeCapturedBefore - Return true if this pointer value may be captured by the enclosing funct...
Definition: CaptureTracking.cpp:269
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43