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."),
71 bool CanBeNull, CanBeFreed;
72 return O->getPointerDereferenceableBytes(
DL, CanBeNull, CanBeFreed);
77 explicit SimpleCaptureTracker(
80 : EphValues(EphValues), ReturnCaptures(ReturnCaptures) {}
82 void tooManyUses()
override {
87 bool captured(
const Use *U)
override {
88 if (isa<ReturnInst>(
U->getUser()) && !ReturnCaptures)
91 if (EphValues.contains(
U->getUser()))
104 bool Captured =
false;
113 CapturesBefore(
bool ReturnCaptures,
const Instruction *
I,
115 : BeforeHere(
I), DT(DT), ReturnCaptures(ReturnCaptures),
116 IncludeI(IncludeI), LI(LI) {}
118 void tooManyUses()
override { Captured =
true; }
126 if (!DT->isReachableFromEntry(
I->getParent()))
133 bool captured(
const Use *U)
override {
135 if (isa<ReturnInst>(
I) && !ReturnCaptures)
141 if (isSafeToPrune(
I))
154 bool Captured =
false;
171 : EphValues(EphValues), DT(DT), ReturnCaptures(ReturnCaptures),
F(
F) {}
173 void tooManyUses()
override {
175 EarliestCapture = &*
F.getEntryBlock().begin();
178 bool captured(
const Use *U)
override {
180 if (isa<ReturnInst>(
I) && !ReturnCaptures)
183 if (EphValues.contains(
I))
186 if (!EarliestCapture)
189 EarliestCapture = DT.findNearestCommonDominator(EarliestCapture,
I);
205 bool Captured =
false;
219 bool StoreCaptures,
unsigned MaxUsesToExplore) {
230 unsigned MaxUsesToExplore) {
231 assert(!isa<GlobalValue>(V) &&
232 "It doesn't make sense to ask whether a global is captured.");
242 SimpleCaptureTracker SCT(EphValues, ReturnCaptures);
265 unsigned MaxUsesToExplore,
267 assert(!isa<GlobalValue>(V) &&
268 "It doesn't make sense to ask whether a global is captured.");
277 CapturesBefore CB(ReturnCaptures,
I, DT, IncludeI, LI);
282 ++NumNotCapturedBefore;
291 unsigned MaxUsesToExplore) {
292 assert(!isa<GlobalValue>(V) &&
293 "It doesn't make sense to ask whether a global is captured.");
295 EarliestCaptures CB(ReturnCaptures,
F, DT, EphValues);
300 ++NumNotCapturedBefore;
301 return CB.EarliestCapture;
313 switch (
I->getOpcode()) {
314 case Instruction::Call:
315 case Instruction::Invoke: {
316 auto *Call = cast<CallBase>(
I);
320 if (Call->onlyReadsMemory() && Call->doesNotThrow() &&
321 Call->getType()->isVoidTy())
334 if (
auto *
MI = dyn_cast<MemIntrinsic>(Call))
335 if (
MI->isVolatile())
344 if (Call->isCallee(&U))
348 if (Call->isDataOperand(&U) &&
349 !Call->doesNotCapture(Call->getDataOperandNo(&U))) {
355 case Instruction::Load:
357 if (cast<LoadInst>(
I)->isVolatile())
360 case Instruction::VAArg:
363 case Instruction::Store:
366 if (U.getOperandNo() == 0 || cast<StoreInst>(
I)->isVolatile())
369 case Instruction::AtomicRMW: {
375 auto *ARMWI = cast<AtomicRMWInst>(
I);
376 if (U.getOperandNo() == 1 || ARMWI->isVolatile())
380 case Instruction::AtomicCmpXchg: {
386 auto *ACXI = cast<AtomicCmpXchgInst>(
I);
387 if (U.getOperandNo() == 1 || U.getOperandNo() == 2 || ACXI->isVolatile())
391 case Instruction::BitCast:
392 case Instruction::GetElementPtr:
393 case Instruction::PHI:
394 case Instruction::Select:
395 case Instruction::AddrSpaceCast:
398 case Instruction::ICmp: {
399 unsigned Idx = U.getOperandNo();
400 unsigned OtherIdx = 1 -
Idx;
401 if (
auto *CPN = dyn_cast<ConstantPointerNull>(
I->getOperand(OtherIdx))) {
405 if (CPN->getType()->getAddressSpace() == 0)
408 if (!
I->getFunction()->nullPointerIsDefined()) {
409 auto *O =
I->getOperand(
Idx)->stripPointerCastsSameRepresentation();
414 if (IsDereferenceableOrNull && IsDereferenceableOrNull(O,
DL))
430 unsigned MaxUsesToExplore) {
431 assert(V->getType()->isPointerTy() &&
"Capture is for pointers only!");
432 if (MaxUsesToExplore == 0)
439 auto AddUses = [&](
const Value *V) {
440 for (
const Use &U : V->uses()) {
443 if (Visited.
size() >= MaxUsesToExplore) {
447 if (!Visited.
insert(&U).second)
461 while (!Worklist.
empty()) {
471 if (!AddUses(U->getUser()))
483 if (IsCapturedCache) {
485 std::tie(CacheIt, Inserted) = IsCapturedCache->
insert({V,
false});
488 return CacheIt->second;
500 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.