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" 17 #include "llvm/ADT/STLFunctionalExtras.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. 33 unsigned getDefaultMaxUsesToExploreForCaptureTracking(); 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. 130 UseCaptureKind 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. 146 bool isNonEscapingLocalObject( 147 const Value *V, 148 SmallDenseMap<const Value *, bool, 8> *IsCapturedCache = nullptr); 149 } // end namespace llvm 150 151 #endif 152