Go to the documentation of this file.
34 #define DEBUG_TYPE "capture-tracking"
36 STATISTIC(NumCaptured,
"Number of pointers maybe captured");
37 STATISTIC(NumNotCaptured,
"Number of pointers not captured");
38 STATISTIC(NumCapturedBefore,
"Number of pointers maybe captured before");
39 STATISTIC(NumNotCapturedBefore,
"Number of pointers not captured before");
49 cl::desc(
"Maximal number of uses to explore."),
69 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(
O))
70 if (
GEP->isInBounds())
72 bool CanBeNull, CanBeFreed;
73 return O->getPointerDereferenceableBytes(
DL, CanBeNull, CanBeFreed);
78 explicit SimpleCaptureTracker(
81 : EphValues(EphValues), ReturnCaptures(ReturnCaptures) {}
83 void tooManyUses()
override { Captured =
true; }
85 bool captured(
const Use *U)
override {
86 if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures)
89 if (EphValues.contains(U->getUser()))
100 bool Captured =
false;
109 CapturesBefore(
bool ReturnCaptures,
const Instruction *
I,
111 : BeforeHere(
I), DT(DT), ReturnCaptures(ReturnCaptures),
112 IncludeI(IncludeI), LI(LI) {}
114 void tooManyUses()
override { Captured =
true; }
122 if (!DT->isReachableFromEntry(
I->getParent()))
129 bool captured(
const Use *U)
override {
131 if (isa<ReturnInst>(
I) && !ReturnCaptures)
137 if (isSafeToPrune(
I))
150 bool Captured =
false;
167 : EphValues(EphValues), DT(DT), ReturnCaptures(ReturnCaptures),
F(
F) {}
169 void tooManyUses()
override {
171 EarliestCapture = &*
F.getEntryBlock().begin();
174 bool captured(
const Use *U)
override {
176 if (isa<ReturnInst>(
I) && !ReturnCaptures)
179 if (EphValues.contains(
I))
182 if (!EarliestCapture)
185 EarliestCapture = DT.findNearestCommonDominator(EarliestCapture,
I);
201 bool Captured =
false;
215 bool StoreCaptures,
unsigned MaxUsesToExplore) {
226 unsigned MaxUsesToExplore) {
227 assert(!isa<GlobalValue>(V) &&
228 "It doesn't make sense to ask whether a global is captured.");
236 SimpleCaptureTracker SCT(EphValues, ReturnCaptures);
257 unsigned MaxUsesToExplore,
259 assert(!isa<GlobalValue>(V) &&
260 "It doesn't make sense to ask whether a global is captured.");
269 CapturesBefore CB(ReturnCaptures,
I, DT, IncludeI, LI);
274 ++NumNotCapturedBefore;
283 unsigned MaxUsesToExplore) {
284 assert(!isa<GlobalValue>(V) &&
285 "It doesn't make sense to ask whether a global is captured.");
287 EarliestCaptures CB(ReturnCaptures,
F, DT, EphValues);
292 ++NumNotCapturedBefore;
293 return CB.EarliestCapture;
301 switch (
I->getOpcode()) {
303 case Instruction::Invoke: {
304 auto *Call = cast<CallBase>(
I);
308 if (Call->onlyReadsMemory() && Call->doesNotThrow() &&
309 Call->getType()->isVoidTy())
322 if (
auto *
MI = dyn_cast<MemIntrinsic>(Call))
323 if (
MI->isVolatile())
332 if (Call->isCallee(&U))
336 if (Call->isDataOperand(&U) &&
337 !Call->doesNotCapture(Call->getDataOperandNo(&U))) {
345 if (cast<LoadInst>(
I)->isVolatile())
348 case Instruction::VAArg:
354 if (U.
getOperandNo() == 0 || cast<StoreInst>(
I)->isVolatile())
357 case Instruction::AtomicRMW: {
363 auto *ARMWI = cast<AtomicRMWInst>(
I);
368 case Instruction::AtomicCmpXchg: {
374 auto *ACXI = cast<AtomicCmpXchgInst>(
I);
379 case Instruction::BitCast:
380 case Instruction::GetElementPtr:
383 case Instruction::AddrSpaceCast:
386 case Instruction::ICmp: {
388 unsigned OtherIdx = 1 - Idx;
389 if (
auto *CPN = dyn_cast<ConstantPointerNull>(
I->getOperand(OtherIdx))) {
393 if (CPN->getType()->getAddressSpace() == 0)
396 if (!
I->getFunction()->nullPointerIsDefined()) {
397 auto *
O =
I->getOperand(Idx)->stripPointerCastsSameRepresentation();
402 if (IsDereferenceableOrNull && IsDereferenceableOrNull(
O,
DL))
409 auto *LI = dyn_cast<LoadInst>(
I->getOperand(OtherIdx));
410 if (LI && isa<GlobalVariable>(LI->getPointerOperand()))
423 unsigned MaxUsesToExplore) {
425 if (MaxUsesToExplore == 0)
432 auto AddUses = [&](
const Value *V) {
433 for (
const Use &U : V->
uses()) {
436 if (Visited.
size() >= MaxUsesToExplore) {
440 if (!Visited.
insert(&U).second)
444 Worklist.push_back(&U);
454 while (!Worklist.empty()) {
464 if (!AddUses(U->getUser()))
476 if (IsCapturedCache) {
478 std::tie(CacheIt, Inserted) = IsCapturedCache->
insert({V,
false});
481 return CacheIt->second;
493 CacheIt->second =
Ret;
This is an optimization pass for GlobalISel generic memory operations.
unsigned getDefaultMaxUsesToExploreForCaptureTracking()
getDefaultMaxUsesToExploreForCaptureTracking - Return default value of the maximal number of uses to ...
A parsed version of the target data layout string in and methods for querying it.
bool isPointerTy() const
True if this is an instance of PointerType.
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.
UseCaptureKind
Types of use capture kinds, see DetermineUseCaptureKind.
This callback is used in conjunction with PointerMayBeCaptured.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
virtual bool captured(const Use *U)=0
captured - Information about the pointer was captured by the user of use U.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
unsigned getOperandNo() const
Return the operand # of this use in its User.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
virtual ~CaptureTracker()
bool isIdentifiedFunctionLocal(const Value *V)
Return true if V is umabigously identified at the function-level.
bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
virtual bool shouldExplore(const Use *U)
shouldExplore - This is the use of a value derived from the pointer.
iterator_range< use_iterator > uses()
bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction 'To' is reachable from 'From', without passing through any blocks in Ex...
STATISTIC(NumFunctions, "Total number of functions")
virtual bool isDereferenceableOrNull(Value *O, const DataLayout &DL)
isDereferenceableOrNull - Overload to allow clients with additional knowledge about pointer dereferen...
User * getUser() const
Returns the User that contains this Use.
UseCaptureKind DetermineUseCaptureKind(const Use &U, llvm::function_ref< bool(Value *, const DataLayout &)> IsDereferenceableOrNull)
Determine what kind of capture behaviour U may exhibit.
An efficient, type-erasing, non-owning reference to a callable.
Instruction * FindEarliestCapture(const Value *V, Function &F, bool ReturnCaptures, bool StoreCaptures, const DominatorTree &DT, const SmallPtrSetImpl< const Value * > &EphValues, unsigned MaxUsesToExplore=0)
static cl::opt< unsigned > DefaultMaxUsesToExplore("capture-tracking-max-uses-to-explore", cl::Hidden, cl::desc("Maximal number of uses to explore."), cl::init(100))
The default value for MaxUsesToExplore argument.
initializer< Ty > init(const Ty &Val)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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...
Type * getType() const
All values are typed, get the type of this value.
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::insert std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
virtual void tooManyUses()=0
tooManyUses - The depth of traversal has breached a limit.
void reserve(size_type N)
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...
LLVM Value Representation.
bool isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(const CallBase *Call, bool MustPreserveNullness)
{launder,strip}.invariant.group returns pointer that aliases its argument, and it only captures point...
A Use represents the edge between a Value definition and its users.