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) {
184 }
else if (EarliestCapture->getParent() ==
I->getParent()) {
185 if (
I->comesBefore(EarliestCapture))
190 if (DT.dominates(EarliestBB, CurrentBB)) {
192 }
else if (DT.dominates(CurrentBB, EarliestBB)) {
196 auto *NearestCommonDom =
197 DT.findNearestCommonDominator(CurrentBB, EarliestBB);
198 EarliestCapture = NearestCommonDom->getTerminator();
216 bool Captured =
false;
230 bool StoreCaptures,
unsigned MaxUsesToExplore) {
241 unsigned MaxUsesToExplore) {
242 assert(!isa<GlobalValue>(V) &&
243 "It doesn't make sense to ask whether a global is captured.");
251 SimpleCaptureTracker SCT(EphValues, ReturnCaptures);
272 unsigned MaxUsesToExplore,
274 assert(!isa<GlobalValue>(V) &&
275 "It doesn't make sense to ask whether a global is captured.");
284 CapturesBefore CB(ReturnCaptures,
I, DT, IncludeI, LI);
289 ++NumNotCapturedBefore;
298 unsigned MaxUsesToExplore) {
299 assert(!isa<GlobalValue>(V) &&
300 "It doesn't make sense to ask whether a global is captured.");
302 EarliestCaptures CB(ReturnCaptures,
F, DT, EphValues);
307 ++NumNotCapturedBefore;
308 return CB.EarliestCapture;
316 switch (
I->getOpcode()) {
318 case Instruction::Invoke: {
319 auto *Call = cast<CallBase>(
I);
323 if (Call->onlyReadsMemory() && Call->doesNotThrow() &&
324 Call->getType()->isVoidTy())
337 if (
auto *
MI = dyn_cast<MemIntrinsic>(Call))
338 if (
MI->isVolatile())
347 if (Call->isCallee(&U))
351 if (Call->isDataOperand(&U) &&
352 !Call->doesNotCapture(Call->getDataOperandNo(&U))) {
360 if (cast<LoadInst>(
I)->isVolatile())
363 case Instruction::VAArg:
369 if (U.
getOperandNo() == 0 || cast<StoreInst>(
I)->isVolatile())
372 case Instruction::AtomicRMW: {
378 auto *ARMWI = cast<AtomicRMWInst>(
I);
383 case Instruction::AtomicCmpXchg: {
389 auto *ACXI = cast<AtomicCmpXchgInst>(
I);
394 case Instruction::BitCast:
395 case Instruction::GetElementPtr:
396 case Instruction::PHI:
398 case Instruction::AddrSpaceCast:
401 case Instruction::ICmp: {
403 unsigned OtherIdx = 1 - Idx;
404 if (
auto *CPN = dyn_cast<ConstantPointerNull>(
I->getOperand(OtherIdx))) {
408 if (CPN->getType()->getAddressSpace() == 0)
411 if (!
I->getFunction()->nullPointerIsDefined()) {
412 auto *
O =
I->getOperand(Idx)->stripPointerCastsSameRepresentation();
417 if (IsDereferenceableOrNull && IsDereferenceableOrNull(
O,
DL))
424 auto *LI = dyn_cast<LoadInst>(
I->getOperand(OtherIdx));
425 if (LI && isa<GlobalVariable>(LI->getPointerOperand()))
438 unsigned MaxUsesToExplore) {
440 if (MaxUsesToExplore == 0)
447 auto AddUses = [&](
const Value *V) {
449 for (
const Use &U : V->
uses()) {
452 if (Count++ >= MaxUsesToExplore) {
456 if (!Visited.
insert(&U).second)
460 Worklist.push_back(&U);
470 while (!Worklist.empty()) {
480 if (!AddUses(U->getUser()))
492 if (IsCapturedCache) {
494 std::tie(CacheIt, Inserted) = IsCapturedCache->
insert({V,
false});
497 return CacheIt->second;
509 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.
const Function * getParent() const
Return the enclosing method, or null if none.
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.
LLVM_NODISCARD T pop_back_val()
virtual ~CaptureTracker()
LLVM Basic Block Representation.
bool isIdentifiedFunctionLocal(const Value *V)
Return true if V is umabigously identified at the function-level.
static cl::opt< unsigned > DefaultMaxUsesToExplore("capture-tracking-max-uses-to-explore", cl::Hidden, cl::desc("Maximal number of uses to explore."), cl::init(20))
The default value for MaxUsesToExplore argument.
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)
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
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
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.
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.