34#define DEBUG_TYPE "capture-tracking"
36STATISTIC(NumCaptured,
"Number of pointers maybe captured");
37STATISTIC(NumNotCaptured,
"Number of pointers not captured");
38STATISTIC(NumCapturedBefore,
"Number of pointers maybe captured before");
39STATISTIC(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 {
88 bool captured(
const Use *U)
override {
89 if (isa<ReturnInst>(
U->getUser()) && !ReturnCaptures)
92 if (EphValues.contains(
U->getUser()))
105 bool Captured =
false;
114 CapturesBefore(
bool ReturnCaptures,
const Instruction *
I,
116 : BeforeHere(
I), DT(DT), ReturnCaptures(ReturnCaptures),
117 IncludeI(IncludeI), LI(LI) {}
119 void tooManyUses()
override { Captured =
true; }
127 if (!DT->isReachableFromEntry(
I->getParent()))
134 bool captured(
const Use *U)
override {
136 if (isa<ReturnInst>(
I) && !ReturnCaptures)
142 if (isSafeToPrune(
I))
155 bool Captured =
false;
172 : EphValues(EphValues), DT(DT), ReturnCaptures(ReturnCaptures),
F(
F) {}
174 void tooManyUses()
override {
176 EarliestCapture = &*
F.getEntryBlock().begin();
179 bool captured(
const Use *U)
override {
181 if (isa<ReturnInst>(
I) && !ReturnCaptures)
184 if (EphValues.contains(
I))
187 if (!EarliestCapture)
190 EarliestCapture = DT.findNearestCommonDominator(EarliestCapture,
I);
206 bool Captured =
false;
220 bool StoreCaptures,
unsigned MaxUsesToExplore) {
231 unsigned MaxUsesToExplore) {
232 assert(!isa<GlobalValue>(V) &&
233 "It doesn't make sense to ask whether a global is captured.");
243 SimpleCaptureTracker SCT(EphValues, ReturnCaptures);
266 unsigned MaxUsesToExplore,
268 assert(!isa<GlobalValue>(V) &&
269 "It doesn't make sense to ask whether a global is captured.");
278 CapturesBefore CB(ReturnCaptures,
I, DT, IncludeI, LI);
283 ++NumNotCapturedBefore;
292 unsigned MaxUsesToExplore) {
293 assert(!isa<GlobalValue>(V) &&
294 "It doesn't make sense to ask whether a global is captured.");
296 EarliestCaptures CB(ReturnCaptures,
F, DT, EphValues);
301 ++NumNotCapturedBefore;
302 return CB.EarliestCapture;
310 switch (
I->getOpcode()) {
311 case Instruction::Call:
312 case Instruction::Invoke: {
313 auto *Call = cast<CallBase>(
I);
317 if (Call->onlyReadsMemory() && Call->doesNotThrow() &&
318 Call->getType()->isVoidTy())
331 if (
auto *
MI = dyn_cast<MemIntrinsic>(Call))
332 if (
MI->isVolatile())
341 if (Call->isCallee(&U))
345 if (Call->isDataOperand(&U) &&
346 !Call->doesNotCapture(Call->getDataOperandNo(&U))) {
352 case Instruction::Load:
354 if (cast<LoadInst>(
I)->isVolatile())
357 case Instruction::VAArg:
360 case Instruction::Store:
363 if (U.getOperandNo() == 0 || cast<StoreInst>(
I)->isVolatile())
366 case Instruction::AtomicRMW: {
372 auto *ARMWI = cast<AtomicRMWInst>(
I);
373 if (U.getOperandNo() == 1 || ARMWI->isVolatile())
377 case Instruction::AtomicCmpXchg: {
383 auto *ACXI = cast<AtomicCmpXchgInst>(
I);
384 if (U.getOperandNo() == 1 || U.getOperandNo() == 2 || ACXI->isVolatile())
388 case Instruction::BitCast:
389 case Instruction::GetElementPtr:
390 case Instruction::PHI:
391 case Instruction::Select:
392 case Instruction::AddrSpaceCast:
395 case Instruction::ICmp: {
396 unsigned Idx = U.getOperandNo();
397 unsigned OtherIdx = 1 -
Idx;
398 if (
auto *CPN = dyn_cast<ConstantPointerNull>(
I->getOperand(OtherIdx))) {
402 if (CPN->getType()->getAddressSpace() == 0)
405 if (!
I->getFunction()->nullPointerIsDefined()) {
406 auto *O =
I->getOperand(
Idx)->stripPointerCastsSameRepresentation();
411 if (IsDereferenceableOrNull && IsDereferenceableOrNull(O,
DL))
427 unsigned MaxUsesToExplore) {
428 assert(V->getType()->isPointerTy() &&
"Capture is for pointers only!");
429 if (MaxUsesToExplore == 0)
436 auto AddUses = [&](
const Value *V) {
437 for (
const Use &U : V->uses()) {
440 if (Visited.
size() >= MaxUsesToExplore) {
444 if (!Visited.
insert(&U).second)
458 while (!Worklist.
empty()) {
468 if (!AddUses(U->getUser()))
480 if (IsCapturedCache) {
482 std::tie(CacheIt, Inserted) = IsCapturedCache->
insert({V,
false});
485 return CacheIt->second;
497 CacheIt->second = Ret;
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
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.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
A parsed version of the target data layout string in and methods for querying it.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
void reserve(size_type N)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
An efficient, type-erasing, non-owning reference to a callable.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
UseCaptureKind DetermineUseCaptureKind(const Use &U, llvm::function_ref< bool(Value *, const DataLayout &)> IsDereferenceableOrNull)
Determine what kind of capture behaviour U may exhibit.
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...
Instruction * FindEarliestCapture(const Value *V, Function &F, bool ReturnCaptures, bool StoreCaptures, const DominatorTree &DT, const SmallPtrSetImpl< const Value * > &EphValues, unsigned MaxUsesToExplore=0)
bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
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.
unsigned getDefaultMaxUsesToExploreForCaptureTracking()
getDefaultMaxUsesToExploreForCaptureTracking - Return default value of the maximal number of uses to ...
bool isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(const CallBase *Call, bool MustPreserveNullness)
{launder,strip}.invariant.group returns pointer that aliases its argument, and it only captures point...
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...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isIdentifiedFunctionLocal(const Value *V)
Return true if V is umabigously identified at the function-level.
UseCaptureKind
Types of use capture kinds, see DetermineUseCaptureKind.
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...
This callback is used in conjunction with PointerMayBeCaptured.
virtual bool shouldExplore(const Use *U)
shouldExplore - This is the use of a value derived from the pointer.
virtual bool isDereferenceableOrNull(Value *O, const DataLayout &DL)
isDereferenceableOrNull - Overload to allow clients with additional knowledge about pointer dereferen...
virtual void tooManyUses()=0
tooManyUses - The depth of traversal has breached a limit.
virtual ~CaptureTracker()
virtual bool captured(const Use *U)=0
captured - Information about the pointer was captured by the user of use U.