CaptureTracking.cpp Source File (original) (raw)

30using namespace llvm;

32#define DEBUG_TYPE "capture-tracking"

34 STATISTIC(NumCaptured, "Number of pointers maybe captured");

35 STATISTIC(NumNotCaptured, "Number of pointers not captured");

36 STATISTIC(NumCapturedBefore, "Number of pointers maybe captured before");

37 STATISTIC(NumNotCapturedBefore, "Number of pointers not captured before");

47 cl::desc("Maximal number of uses to explore."),

58namespace {

60 explicit SimpleCaptureTracker(bool ReturnCaptures, CaptureComponents Mask,

62 : ReturnCaptures(ReturnCaptures), Mask(Mask), StopFn(StopFn) {}

64 void tooManyUses() override {

65 LLVM_DEBUG(dbgs() << "Captured due to too many uses\n");

66 CC = Mask;

67 }

69 Action captured(const Use *U, UseCaptureInfo CI) override {

71 return ContinueIgnoringReturn;

76 LLVM_DEBUG(dbgs() << "Captured by: " << *U->getUser() << "\n");

78 return StopFn(CC) ? Stop : Continue;

79 }

81 bool ReturnCaptures;

86};

94 CapturesBefore(bool ReturnCaptures, const Instruction *I,

95 const DominatorTree *DT, bool IncludeI, const LoopInfo *LI,

98 : BeforeHere(I), DT(DT), ReturnCaptures(ReturnCaptures),

99 IncludeI(IncludeI), LI(LI), Mask(Mask), StopFn(StopFn) {}

100

101 void tooManyUses() override { CC = Mask; }

102

103 bool isSafeToPrune(Instruction *I) {

104 if (BeforeHere == I)

105 return !IncludeI;

106

107

108

110 return true;

111

112

114 }

115

116 Action captured(const Use *U, UseCaptureInfo CI) override {

119 return ContinueIgnoringReturn;

120

121

122

123

124 if (isSafeToPrune(I))

125

126 return ContinueIgnoringReturn;

127

130

132 return StopFn(CC) ? Stop : Continue;

133 }

134

136 const DominatorTree *DT;

137

138 bool ReturnCaptures;

139 bool IncludeI;

140

142

143 const LoopInfo *LI;

146};

147

148

149

150

151

152

153

154

155

157

158 EarliestCaptures(bool ReturnCaptures, Function &F, const DominatorTree &DT,

160 : DT(DT), ReturnCaptures(ReturnCaptures), F(F), Mask(Mask) {}

161

162 void tooManyUses() override {

164 EarliestCapture = &*F.getEntryBlock().begin();

165 }

166

167 Action captured(const Use *U, UseCaptureInfo CI) override {

170 return ContinueIgnoringReturn;

171

173 if (!EarliestCapture)

174 EarliestCapture = I;

175 else

178 }

179

180

182 }

183

184 const DominatorTree &DT;

185 bool ReturnCaptures;

188

191};

192}

193

198 "It doesn't make sense to ask whether a global is captured.");

199

201

202 SimpleCaptureTracker SCT(ReturnCaptures, Mask, StopFn);

205 ++NumCaptured;

206 else {

207 ++NumNotCaptured;

209 }

210 return SCT.CC;

211}

212

214 unsigned MaxUsesToExplore) {

218}

219

224 unsigned MaxUsesToExplore) {

226 "It doesn't make sense to ask whether a global is captured.");

227

228 if (!DT)

230 MaxUsesToExplore);

231

232 CapturesBefore CB(ReturnCaptures, I, DT, IncludeI, LI, Mask, StopFn);

235 ++NumCapturedBefore;

236 else

237 ++NumNotCapturedBefore;

238 return CB.CC;

239}

240

244 unsigned MaxUsesToExplore,

249}

250

251std::pair<Instruction *, CaptureComponents>

254 unsigned MaxUsesToExplore) {

256 "It doesn't make sense to ask whether a global is captured.");

257

258 EarliestCaptures CB(ReturnCaptures, F, DT, Mask);

261 ++NumCapturedBefore;

262 else

263 ++NumNotCapturedBefore;

264 return {CB.EarliestCapture, CB.CC};

265}

266

269

270

271 if ()

273

274 switch (I->getOpcode()) {

275 case Instruction::Call:

276 case Instruction::Invoke: {

278

279

280

281

282

285

286

287

289 if (MI->isVolatile())

291

292

293

294

295

296

297

298 if (Call->isCallee(&U))

300

301 assert(Call->isDataOperand(&U) && "Non-callee must be data operand");

303

304

305

307 if (Call->onlyReadsMemory() && Call->getType()->isVoidTy())

309

312 }

313 case Instruction::Load:

314

318 case Instruction::VAArg:

319

321 case Instruction::Store:

322

323 if (U.getOperandNo() == 0)

325 I->getMetadata(LLVMContext::MD_captures));

326

327

331 case Instruction::AtomicRMW: {

332

333

334

335

336

338 if (U.getOperandNo() == 1 || ARMWI->isVolatile())

341 }

342 case Instruction::AtomicCmpXchg: {

343

344

345

346

347

349 if (U.getOperandNo() == 1 || U.getOperandNo() == 2 || ACXI->isVolatile())

352 }

353 case Instruction::GetElementPtr:

354

355

356 if (I->getType()->isVectorTy())

359 case Instruction::BitCast:

360 case Instruction::PHI:

361 case Instruction::Select:

362 case Instruction::AddrSpaceCast:

363

365 case Instruction::PtrToAddr:

366

367

368

369

371 case Instruction::ICmp: {

372 unsigned Idx = U.getOperandNo();

373 unsigned OtherIdx = 1 - Idx;

376

377

378

379

380

381

382 if (U->getType()->getPointerAddressSpace() == 0)

385

386

387

388 if (U.get() == Base)

390 }

391

392

393

394

396 }

397 default:

398

400 }

401}

402

404 unsigned MaxUsesToExplore) {

405 assert(V->getType()->isPointerTy() && "Capture is for pointers only!");

406 if (MaxUsesToExplore == 0)

408

412

413 auto AddUses = [&](const Value *V) {

414 for (const Use &U : V->uses()) {

415

416

417 if (Visited.size() >= MaxUsesToExplore) {

419 return false;

420 }

421 if (!Visited.insert(&U).second)

422 continue;

424 continue;

426 }

427 return true;

428 };

429 if (!AddUses(V))

430 return;

431

432 while (!Worklist.empty()) {

436 switch (Tracker->captured(U, CI)) {

438 return;

440 continue;

442

443

444

445

447 continue;

448 break;

449 }

450 }

451

453 return;

454 }

455

456

457}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

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...

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)

Represents which components of the pointer may be captured in which location.

CaptureComponents getOtherComponents() const

Get components potentially captured through locations other than the return value.

CaptureComponents getRetComponents() const

Get components potentially captured by the return value.

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

LLVM_ABI bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

LLVM_ABI Instruction * findNearestCommonDominator(Instruction *I1, Instruction *I2) const

Find the nearest instruction I that dominates both I1 and I2, in the sense that a result produced bef...

static LLVM_ABI CaptureComponents toCaptureComponents(const MDNode *MD)

Convert !captures metadata to CaptureComponents. MD may be nullptr.

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

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.

iterator_range< use_iterator > uses()

An efficient, type-erasing, non-owning reference to a callable.

constexpr std::underlying_type_t< E > Mask()

Get a bitmask with 1s in all places up to the high-order bit of E's largest value.

initializer< Ty > init(const Ty &Val)

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

LLVM_ABI std::pair< Instruction *, CaptureComponents > FindEarliestCapture(const Value *V, Function &F, bool ReturnCaptures, const DominatorTree &DT, CaptureComponents Mask, unsigned MaxUsesToExplore=0)

Definition CaptureTracking.cpp:252

LLVM_ABI bool isNoAliasCall(const Value *V)

Return true if this pointer is returned by a noalias function.

LLVM_ABI unsigned getDefaultMaxUsesToExploreForCaptureTracking()

getDefaultMaxUsesToExploreForCaptureTracking - Return default value of the maximal number of uses to ...

Definition CaptureTracking.cpp:50

LLVM_ABI bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, 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...

Definition CaptureTracking.cpp:241

LLVM_ABI bool isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(const CallBase *Call, bool MustPreserveNullness)

{launder,strip}.invariant.group returns pointer that aliases its argument, and it only captures point...

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

CaptureComponents

Components of the pointer that may be captured.

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

LLVM_ABI bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, unsigned MaxUsesToExplore=0)

PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...

Definition CaptureTracking.cpp:213

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

bool capturesAnything(CaptureComponents CC)

LLVM_ABI UseCaptureInfo DetermineUseCaptureKind(const Use &U, const Value *Base)

Determine what kind of capture behaviour U may exhibit.

Definition CaptureTracking.cpp:267

bool capturesNothing(CaptureComponents CC)

LLVM_ABI 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.

Definition CaptureTracking.cpp:56

@ ContinueIgnoringReturn

Continue traversal, but do not follow the return value of the user, even if it has additional capture...

@ Continue

Continue traversal, and also follow the return value of the user if it has additional capture compone...

@ Stop

Stop the traversal.

virtual Action captured(const Use *U, UseCaptureInfo CI)=0

Use U directly captures CI.UseCC and additionally CI.ResultCC through the return value of the user of...

virtual void tooManyUses()=0

tooManyUses - The depth of traversal has breached a limit.

virtual ~CaptureTracker()

Capture information for a specific Use.

CaptureComponents UseCC

Components captured by this use.

CaptureComponents ResultCC

Components captured by the return value of the user of this Use.

static UseCaptureInfo passthrough()