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/Support/Compiler.h" 18 #include "llvm/Support/ModRef.h" 19 20 namespace llvm { 21 22 class Value; 23 class Use; 24 class CaptureInfo; 25 class DataLayout; 26 class Instruction; 27 class DominatorTree; 28 class LoopInfo; 29 class Function; 30 template <typename Fn> class function_ref; 31 32 /// getDefaultMaxUsesToExploreForCaptureTracking - Return default value of 33 /// the maximal number of uses to explore before giving up. It is used by 34 /// PointerMayBeCaptured family analysis. 35 LLVM_ABI unsigned getDefaultMaxUsesToExploreForCaptureTracking(); 36 37 /// PointerMayBeCaptured - Return true if this pointer value may be captured 38 /// by the enclosing function (which is required to exist). This routine can 39 /// be expensive, so consider caching the results. The boolean ReturnCaptures 40 /// specifies whether returning the value (or part of it) from the function 41 /// 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 /// This function only considers captures of the passed value via its def-use 46 /// chain, without considering captures of values it may be based on, or 47 /// implicit captures such as for external globals. 48 LLVM_ABI bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, 49 unsigned MaxUsesToExplore = 0); 50 51 /// Return which components of the pointer may be captured. Only consider 52 /// components that are part of \p Mask. Once \p StopFn on the accumulated 53 /// components returns true, the traversal is aborted early. By default, this 54 /// happens when *any* of the components in \p Mask are captured. 55 /// This function only considers captures of the passed value via its def-use 56 /// chain, without considering captures of values it may be based on, or 57 /// implicit captures such as for external globals. 58 LLVM_ABI CaptureComponents PointerMayBeCaptured( 59 const Value *V, bool ReturnCaptures, CaptureComponents Mask, 60 function_ref<bool(CaptureComponents)> StopFn = capturesAnything, 61 unsigned MaxUsesToExplore = 0); 62 63 /// PointerMayBeCapturedBefore - Return true if this pointer value may be 64 /// captured by the enclosing function (which is required to exist). If a 65 /// DominatorTree is provided, only captures which happen before the given 66 /// instruction are considered. This routine can be expensive, so consider 67 /// caching the results. The boolean ReturnCaptures specifies whether 68 /// returning the value (or part of it) from the function counts as capturing 69 /// it or not. Captures by the provided instruction are considered if the 70 /// final parameter is true. 71 /// MaxUsesToExplore specifies how many uses the analysis should explore for 72 /// one value before giving up due too "too many uses". If MaxUsesToExplore 73 /// is zero, a default value is assumed. 74 /// This function only considers captures of the passed value via its def-use 75 /// chain, without considering captures of values it may be based on, or 76 /// implicit captures such as for external globals. 77 LLVM_ABI bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, 78 const Instruction *I, 79 const DominatorTree *DT, 80 bool IncludeI = false, 81 unsigned MaxUsesToExplore = 0, 82 const LoopInfo *LI = nullptr); 83 84 /// Return which components of the pointer may be captured on the path to 85 /// \p I. Only consider components that are part of \p Mask. Once \p StopFn 86 /// on the accumulated components returns true, the traversal is aborted 87 /// early. By default, this happens when *any* of the components in \p Mask 88 /// are captured. 89 /// This function only considers captures of the passed value via its def-use 90 /// chain, without considering captures of values it may be based on, or 91 /// implicit captures such as for external globals. 92 LLVM_ABI CaptureComponents PointerMayBeCapturedBefore( 93 const Value *V, bool ReturnCaptures, const Instruction *I, 94 const DominatorTree *DT, bool IncludeI, CaptureComponents Mask, 95 function_ref<bool(CaptureComponents)> StopFn = capturesAnything, 96 const LoopInfo *LI = nullptr, unsigned MaxUsesToExplore = 0); 97 98 // Returns the 'earliest' instruction that captures \p V in \F, and which 99 // components may be captured (by any use, not necessarily the earliest one). 100 // An instruction A is considered earlier than instruction B, if A dominates 101 // B. If 2 escapes do not dominate each other, the terminator of the common 102 // dominator is chosen. If not all uses can be analyzed, the earliest escape 103 // is set to the first instruction in the function entry block. If \p V does 104 // not escape, nullptr is returned. Note that the caller of the function has 105 // to ensure that the instruction the result value is compared against is 106 // not in a cycle. 107 // 108 // Only consider components that are part of \p Mask. 109 LLVM_ABI std::pair<Instruction *, CaptureComponents> 110 FindEarliestCapture(const Value *V, Function &F, bool ReturnCaptures, 111 const DominatorTree &DT, CaptureComponents Mask, 112 unsigned MaxUsesToExplore = 0); 113 114 /// Capture information for a specific Use. 115 struct UseCaptureInfo { 116 /// Components captured by this use. 117 CaptureComponents UseCC; 118 /// Components captured by the return value of the user of this Use. 119 CaptureComponents ResultCC; 120 121 UseCaptureInfo(CaptureComponents UseCC, 122 CaptureComponents ResultCC = CaptureComponents::None) UseCCUseCaptureInfo123 : UseCC(UseCC), ResultCC(ResultCC) {} 124 passthroughUseCaptureInfo125 static UseCaptureInfo passthrough() { 126 return UseCaptureInfo(CaptureComponents::None, CaptureComponents::All); 127 } 128 isPassthroughUseCaptureInfo129 bool isPassthrough() const { 130 return capturesNothing(UseCC) && capturesAnything(ResultCC); 131 } 132 CaptureComponentsUseCaptureInfo133 operator CaptureComponents() const { return UseCC | ResultCC; } 134 }; 135 136 /// This callback is used in conjunction with PointerMayBeCaptured. In 137 /// addition to the interface here, you'll need to provide your own getters 138 /// to see whether anything was captured. 139 struct LLVM_ABI CaptureTracker { 140 /// Action returned from captures(). 141 enum Action { 142 /// Stop the traversal. 143 Stop, 144 /// Continue traversal, and also follow the return value of the user if 145 /// it has additional capture components (that is, if it has capture 146 /// components in Ret that are not part of Other). 147 Continue, 148 /// Continue traversal, but do not follow the return value of the user, 149 /// even if it has additional capture components. Should only be used if 150 /// captures() has already taken the potential return captures into 151 /// account. 152 ContinueIgnoringReturn, 153 }; 154 155 virtual ~CaptureTracker(); 156 157 /// tooManyUses - The depth of traversal has breached a limit. There may be 158 /// capturing instructions that will not be passed into captured(). 159 virtual void tooManyUses() = 0; 160 161 /// shouldExplore - This is the use of a value derived from the pointer. 162 /// To prune the search (ie., assume that none of its users could possibly 163 /// capture) return false. To search it, return true. 164 /// 165 /// U->getUser() is always an Instruction. 166 virtual bool shouldExplore(const Use *U); 167 168 /// Use U directly captures CI.UseCC and additionally CI.ResultCC 169 /// through the return value of the user of U. 170 /// 171 /// Return one of Stop, Continue or ContinueIgnoringReturn to control 172 /// further traversal. 173 virtual Action captured(const Use *U, UseCaptureInfo CI) = 0; 174 }; 175 176 /// Determine what kind of capture behaviour \p U may exhibit. 177 /// 178 /// The returned UseCaptureInfo contains the components captured directly 179 /// by the use (UseCC) and the components captured through the return value 180 /// of the user (ResultCC). 181 /// 182 /// \p Base is the starting value of the capture analysis, which is 183 /// relevant for address_is_null captures. 184 LLVM_ABI UseCaptureInfo DetermineUseCaptureKind(const Use &U, 185 const Value *Base); 186 187 /// PointerMayBeCaptured - Visit the value and the values derived from it and 188 /// find values which appear to be capturing the pointer value. This feeds 189 /// results into and is controlled by the CaptureTracker object. 190 /// MaxUsesToExplore specifies how many uses the analysis should explore for 191 /// one value before giving up due too "too many uses". If MaxUsesToExplore 192 /// is zero, a default value is assumed. 193 /// This function only considers captures of the passed value via its def-use 194 /// chain, without considering captures of values it may be based on, or 195 /// implicit captures such as for external globals. 196 LLVM_ABI void PointerMayBeCaptured(const Value *V, CaptureTracker *Tracker, 197 unsigned MaxUsesToExplore = 0); 198 } // end namespace llvm 199 200 #endif 201