+CaptureTracker::~CaptureTracker() {}
+
+bool CaptureTracker::shouldExplore(const Use *U) { return true; }
+
+namespace {
+ struct SimpleCaptureTracker : public CaptureTracker {
+ explicit SimpleCaptureTracker(bool ReturnCaptures)
+ : ReturnCaptures(ReturnCaptures), Captured(false) {}
+
+ void tooManyUses() override { Captured = true; }
+
+ bool captured(const Use *U) override {
+ if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures)
+ return false;
+
+ Captured = true;
+ return true;
+ }
+
+ bool ReturnCaptures;
+
+ bool Captured;
+ };
+
+ /// Only find pointer captures which happen before the given instruction. Uses
+ /// the dominator tree to determine whether one instruction is before another.
+ /// Only support the case where the Value is defined in the same basic block
+ /// as the given instruction and the use.
+ struct CapturesBefore : public CaptureTracker {
+
+ CapturesBefore(bool ReturnCaptures, const Instruction *I, DominatorTree *DT,
+ bool IncludeI, OrderedBasicBlock *IC)
+ : OrderedBB(IC), BeforeHere(I), DT(DT),
+ ReturnCaptures(ReturnCaptures), IncludeI(IncludeI), Captured(false) {}
+
+ void tooManyUses() override { Captured = true; }
+
+ bool isSafeToPrune(Instruction *I) {
+ BasicBlock *BB = I->getParent();
+ // We explore this usage only if the usage can reach "BeforeHere".
+ // If use is not reachable from entry, there is no need to explore.
+ if (BeforeHere != I && !DT->isReachableFromEntry(BB))
+ return true;
+
+ // Compute the case where both instructions are inside the same basic
+ // block. Since instructions in the same BB as BeforeHere are numbered in
+ // 'OrderedBB', avoid using 'dominates' and 'isPotentiallyReachable'
+ // which are very expensive for large basic blocks.
+ if (BB == BeforeHere->getParent()) {
+ // 'I' dominates 'BeforeHere' => not safe to prune.
+ //
+ // The value defined by an invoke dominates an instruction only
+ // if it dominates every instruction in UseBB. A PHI is dominated only
+ // if the instruction dominates every possible use in the UseBB. Since
+ // UseBB == BB, avoid pruning.
+ if (isa<InvokeInst>(BeforeHere) || isa<PHINode>(I) || I == BeforeHere)
+ return false;
+ if (!OrderedBB->dominates(BeforeHere, I))
+ return false;
+
+ // 'BeforeHere' comes before 'I', it's safe to prune if we also
+ // guarantee that 'I' never reaches 'BeforeHere' through a back-edge or
+ // by its successors, i.e, prune if:
+ //
+ // (1) BB is an entry block or have no sucessors.
+ // (2) There's no path coming back through BB sucessors.
+ if (BB == &BB->getParent()->getEntryBlock() ||
+ !BB->getTerminator()->getNumSuccessors())
+ return true;
+
+ SmallVector<BasicBlock*, 32> Worklist;
+ Worklist.append(succ_begin(BB), succ_end(BB));
+ return !isPotentiallyReachableFromMany(Worklist, BB, DT);
+ }
+
+ // If the value is defined in the same basic block as use and BeforeHere,
+ // there is no need to explore the use if BeforeHere dominates use.
+ // Check whether there is a path from I to BeforeHere.
+ if (BeforeHere != I && DT->dominates(BeforeHere, I) &&
+ !isPotentiallyReachable(I, BeforeHere, DT))
+ return true;
+
+ return false;
+ }
+
+ bool shouldExplore(const Use *U) override {
+ Instruction *I = cast<Instruction>(U->getUser());
+
+ if (BeforeHere == I && !IncludeI)
+ return false;
+
+ if (isSafeToPrune(I))
+ return false;
+
+ return true;
+ }
+
+ bool captured(const Use *U) override {
+ if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures)
+ return false;
+
+ if (!shouldExplore(U))
+ return false;
+
+ Captured = true;
+ return true;
+ }
+
+ OrderedBasicBlock *OrderedBB;
+ const Instruction *BeforeHere;
+ DominatorTree *DT;
+
+ bool ReturnCaptures;
+ bool IncludeI;
+
+ bool Captured;
+ };
+}
+