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 29 /// getDefaultMaxUsesToExploreForCaptureTracking - Return default value of 30 /// the maximal number of uses to explore before giving up. It is used by 31 /// PointerMayBeCaptured family analysis. 32 unsigned getDefaultMaxUsesToExploreForCaptureTracking(); 33 34 /// PointerMayBeCaptured - Return true if this pointer value may be captured 35 /// by the enclosing function (which is required to exist). This routine can 36 /// be expensive, so consider caching the results. The boolean ReturnCaptures 37 /// specifies whether returning the value (or part of it) from the function 38 /// counts as capturing it or not. The boolean StoreCaptures specified 39 /// whether storing the value (or part of it) into memory anywhere 40 /// automatically counts as capturing it or not. 41 /// MaxUsesToExplore specifies how many uses the analysis should explore for 42 /// one value before giving up due too "too many uses". If MaxUsesToExplore 43 /// is zero, a default value is assumed. 44 bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, 45 bool StoreCaptures, unsigned MaxUsesToExplore = 0); 46 47 /// PointerMayBeCapturedBefore - Return true if this pointer value may be 48 /// captured by the enclosing function (which is required to exist). If a 49 /// DominatorTree is provided, only captures which happen before the given 50 /// instruction are considered. This routine can be expensive, so consider 51 /// caching the results. The boolean ReturnCaptures specifies whether 52 /// returning the value (or part of it) from the function counts as capturing 53 /// it or not. The boolean StoreCaptures specified whether storing the value 54 /// (or part of it) into memory anywhere automatically counts as capturing it 55 /// or not. Captures by the provided instruction are considered if the 56 /// final parameter is true. 57 /// MaxUsesToExplore specifies how many uses the analysis should explore for 58 /// one value before giving up due too "too many uses". If MaxUsesToExplore 59 /// is zero, a default value is assumed. 60 bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, 61 bool StoreCaptures, const Instruction *I, 62 const DominatorTree *DT, 63 bool IncludeI = false, 64 unsigned MaxUsesToExplore = 0, 65 const LoopInfo *LI = nullptr); 66 67 // Returns the 'earliest' instruction that captures \p V in \F. An instruction 68 // A is considered earlier than instruction B, if A dominates B. If 2 escapes 69 // do not dominate each other, the terminator of the common dominator is 70 // chosen. If not all uses can be analyzed, the earliest escape is set to 71 // the first instruction in the function entry block. If \p V does not escape, 72 // nullptr is returned. Note that the caller of the function has to ensure 73 // that the instruction the result value is compared against is not in a 74 // cycle. 75 Instruction *FindEarliestCapture(const Value *V, Function &F, 76 bool ReturnCaptures, bool StoreCaptures, 77 const DominatorTree &DT, 78 unsigned MaxUsesToExplore = 0); 79 80 /// This callback is used in conjunction with PointerMayBeCaptured. In 81 /// addition to the interface here, you'll need to provide your own getters 82 /// to see whether anything was captured. 83 struct CaptureTracker { 84 virtual ~CaptureTracker(); 85 86 /// tooManyUses - The depth of traversal has breached a limit. There may be 87 /// capturing instructions that will not be passed into captured(). 88 virtual void tooManyUses() = 0; 89 90 /// shouldExplore - This is the use of a value derived from the pointer. 91 /// To prune the search (ie., assume that none of its users could possibly 92 /// capture) return false. To search it, return true. 93 /// 94 /// U->getUser() is always an Instruction. 95 virtual bool shouldExplore(const Use *U); 96 97 /// captured - Information about the pointer was captured by the user of 98 /// use U. Return true to stop the traversal or false to continue looking 99 /// for more capturing instructions. 100 virtual bool captured(const Use *U) = 0; 101 102 /// isDereferenceableOrNull - Overload to allow clients with additional 103 /// knowledge about pointer dereferenceability to provide it and thereby 104 /// avoid conservative responses when a pointer is compared to null. 105 virtual bool isDereferenceableOrNull(Value *O, const DataLayout &DL); 106 }; 107 108 /// Types of use capture kinds, see \p DetermineUseCaptureKind. 109 enum class UseCaptureKind { 110 NO_CAPTURE, 111 MAY_CAPTURE, 112 PASSTHROUGH, 113 }; 114 115 /// Determine what kind of capture behaviour \p U may exhibit. 116 /// 117 /// A use can be no-capture, a use can potentially capture, or a use can be 118 /// passthrough such that the uses of the user or \p U should be inspected. 119 /// The \p IsDereferenceableOrNull callback is used to rule out capturing for 120 /// certain comparisons. 121 UseCaptureKind 122 DetermineUseCaptureKind(const Use &U, 123 llvm::function_ref<bool(Value *, const DataLayout &)> 124 IsDereferenceableOrNull); 125 126 /// PointerMayBeCaptured - Visit the value and the values derived from it and 127 /// find values which appear to be capturing the pointer value. This feeds 128 /// results into and is controlled by the CaptureTracker object. 129 /// MaxUsesToExplore specifies how many uses the analysis should explore for 130 /// one value before giving up due too "too many uses". If MaxUsesToExplore 131 /// is zero, a default value is assumed. 132 void PointerMayBeCaptured(const Value *V, CaptureTracker *Tracker, 133 unsigned MaxUsesToExplore = 0); 134 135 /// Returns true if the pointer is to a function-local object that never 136 /// escapes from the function. 137 bool isNonEscapingLocalObject( 138 const Value *V, 139 SmallDenseMap<const Value *, bool, 8> *IsCapturedCache = nullptr); 140 } // end namespace llvm 141 142 #endif 143