//===----- llvm/Analysis/CaptureTracking.h - Pointer capture ----*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file contains routines that help determine which pointers are captured.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ANALYSIS_CAPTURETRACKING_H
#define LLVM_ANALYSIS_CAPTURETRACKING_H
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLFunctionalExtras.h"
namespace llvm {
class Value;
class Use;
class DataLayout;
class Instruction;
class DominatorTree;
class LoopInfo;
class Function;
template <typename T> class SmallPtrSetImpl;
/// getDefaultMaxUsesToExploreForCaptureTracking - Return default value of
/// the maximal number of uses to explore before giving up. It is used by
/// PointerMayBeCaptured family analysis.
unsigned getDefaultMaxUsesToExploreForCaptureTracking();
/// PointerMayBeCaptured - Return true if this pointer value may be captured
/// by the enclosing function (which is required to exist). This routine can
/// be expensive, so consider caching the results. The boolean ReturnCaptures
/// specifies whether returning the value (or part of it) from the function
/// counts as capturing it or not. The boolean StoreCaptures specified
/// whether storing the value (or part of it) into memory anywhere
/// automatically counts as capturing it or not.
/// MaxUsesToExplore specifies how many uses the analysis should explore for
/// one value before giving up due too "too many uses". If MaxUsesToExplore
/// is zero, a default value is assumed.
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures,
bool StoreCaptures, unsigned MaxUsesToExplore = 0);
/// Variant of the above function which accepts a set of Values that are
/// ephemeral and cannot cause pointers to escape.
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures,
bool StoreCaptures,
const SmallPtrSetImpl<const Value *> &EphValues,
unsigned MaxUsesToExplore = 0);
/// PointerMayBeCapturedBefore - Return true if this pointer value may be
/// captured by the enclosing function (which is required to exist). If a
/// DominatorTree is provided, only captures which happen before the given
/// instruction are considered. This routine can be expensive, so consider
/// caching the results. The boolean ReturnCaptures specifies whether
/// returning the value (or part of it) from the function counts as capturing
/// it or not. The boolean StoreCaptures specified whether storing the value
/// (or part of it) into memory anywhere automatically counts as capturing it
/// or not. Captures by the provided instruction are considered if the
/// final parameter is true.
/// MaxUsesToExplore specifies how many uses the analysis should explore for
/// one value before giving up due too "too many uses". If MaxUsesToExplore
/// is zero, a default value is assumed.
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);
// Returns the 'earliest' instruction that captures \p V in \F. An instruction
// A is considered earlier than instruction B, if A dominates B. If 2 escapes
// do not dominate each other, the terminator of the common dominator is
// chosen. If not all uses can be analyzed, the earliest escape is set to
// the first instruction in the function entry block. If \p V does not escape,
// nullptr is returned. Note that the caller of the function has to ensure
// that the instruction the result value is compared against is not in a
// cycle.
Instruction *
FindEarliestCapture(const Value *V, Function &F, bool ReturnCaptures,
bool StoreCaptures, const DominatorTree &DT,
const SmallPtrSetImpl<const Value *> &EphValues,
unsigned MaxUsesToExplore = 0);
/// This callback is used in conjunction with PointerMayBeCaptured. In
/// addition to the interface here, you'll need to provide your own getters
/// to see whether anything was captured.
struct CaptureTracker {
virtual ~CaptureTracker();
/// tooManyUses - The depth of traversal has breached a limit. There may be
/// capturing instructions that will not be passed into captured().
virtual void tooManyUses() = 0;
/// shouldExplore - This is the use of a value derived from the pointer.
/// To prune the search (ie., assume that none of its users could possibly
/// capture) return false. To search it, return true.
///
/// U->getUser() is always an Instruction.
virtual bool shouldExplore(const Use *U);
/// captured - Information about the pointer was captured by the user of
/// use U. Return true to stop the traversal or false to continue looking
/// for more capturing instructions.
virtual bool captured(const Use *U) = 0;
/// isDereferenceableOrNull - Overload to allow clients with additional
/// knowledge about pointer dereferenceability to provide it and thereby
/// avoid conservative responses when a pointer is compared to null.
virtual bool isDereferenceableOrNull(Value *O, const DataLayout &DL);
};
/// Types of use capture kinds, see \p DetermineUseCaptureKind.
enum class UseCaptureKind {
NO_CAPTURE,
MAY_CAPTURE,
PASSTHROUGH,
};
/// Determine what kind of capture behaviour \p U may exhibit.
///
/// A use can be no-capture, a use can potentially capture, or a use can be
/// passthrough such that the uses of the user or \p U should be inspected.
/// The \p IsDereferenceableOrNull callback is used to rule out capturing for
/// certain comparisons.
UseCaptureKind
DetermineUseCaptureKind(const Use &U,
llvm::function_ref<bool(Value *, const DataLayout &)>
IsDereferenceableOrNull);
/// PointerMayBeCaptured - Visit the value and the values derived from it and
/// find values which appear to be capturing the pointer value. This feeds
/// results into and is controlled by the CaptureTracker object.
/// MaxUsesToExplore specifies how many uses the analysis should explore for
/// one value before giving up due too "too many uses". If MaxUsesToExplore
/// is zero, a default value is assumed.
void PointerMayBeCaptured(const Value *V, CaptureTracker *Tracker,
unsigned MaxUsesToExplore = 0);
/// Returns true if the pointer is to a function-local object that never
/// escapes from the function.
bool isNonEscapingLocalObject(
const Value *V,
SmallDenseMap<const Value *, bool, 8> *IsCapturedCache = nullptr);
} // end namespace llvm
#endif