summaryrefslogtreecommitdiffstats
path: root/llvm
diff options
context:
space:
mode:
Diffstat (limited to 'llvm')
-rw-r--r--llvm/include/llvm/Analysis/CFG.h11
-rw-r--r--llvm/lib/Analysis/CFG.cpp16
-rw-r--r--llvm/lib/Analysis/CaptureTracking.cpp127
3 files changed, 129 insertions, 25 deletions
diff --git a/llvm/include/llvm/Analysis/CFG.h b/llvm/include/llvm/Analysis/CFG.h
index 7f92eda8cb2..7c4df780198 100644
--- a/llvm/include/llvm/Analysis/CFG.h
+++ b/llvm/include/llvm/Analysis/CFG.h
@@ -78,6 +78,17 @@ bool isPotentiallyReachable(const BasicBlock *From, const BasicBlock *To,
const DominatorTree *DT = nullptr,
const LoopInfo *LI = nullptr);
+/// \brief Determine whether there is at least one path from a block in
+/// 'Worklist' to 'StopBB', returning true if uncertain.
+///
+/// Determine whether there is a path from at least one block in Worklist to
+/// StopBB within a single function. Returns false only if we can prove that
+/// once any block in 'Worklist' has been reached then 'StopBB' can not be
+/// executed. Conservatively returns true.
+bool isPotentiallyReachableFromMany(SmallVectorImpl<BasicBlock *> &Worklist,
+ BasicBlock *StopBB,
+ const DominatorTree *DT = nullptr,
+ const LoopInfo *LI = nullptr);
} // End llvm namespace
#endif
diff --git a/llvm/lib/Analysis/CFG.cpp b/llvm/lib/Analysis/CFG.cpp
index 8ecd70b5d71..e15109bd270 100644
--- a/llvm/lib/Analysis/CFG.cpp
+++ b/llvm/lib/Analysis/CFG.cpp
@@ -126,10 +126,9 @@ static bool loopContainsBoth(const LoopInfo *LI,
return L1 != nullptr && L1 == L2;
}
-static bool isPotentiallyReachableInner(SmallVectorImpl<BasicBlock *> &Worklist,
- BasicBlock *StopBB,
- const DominatorTree *DT,
- const LoopInfo *LI) {
+bool llvm::isPotentiallyReachableFromMany(
+ SmallVectorImpl<BasicBlock *> &Worklist, BasicBlock *StopBB,
+ const DominatorTree *DT, const LoopInfo *LI) {
// When the stop block is unreachable, it's dominated from everywhere,
// regardless of whether there's a path between the two blocks.
if (DT && !DT->isReachableFromEntry(StopBB))
@@ -179,8 +178,8 @@ bool llvm::isPotentiallyReachable(const BasicBlock *A, const BasicBlock *B,
SmallVector<BasicBlock*, 32> Worklist;
Worklist.push_back(const_cast<BasicBlock*>(A));
- return isPotentiallyReachableInner(Worklist, const_cast<BasicBlock*>(B),
- DT, LI);
+ return isPotentiallyReachableFromMany(Worklist, const_cast<BasicBlock *>(B),
+ DT, LI);
}
bool llvm::isPotentiallyReachable(const Instruction *A, const Instruction *B,
@@ -230,7 +229,6 @@ bool llvm::isPotentiallyReachable(const Instruction *A, const Instruction *B,
if (B->getParent() == &A->getParent()->getParent()->getEntryBlock())
return false;
- return isPotentiallyReachableInner(Worklist,
- const_cast<BasicBlock*>(B->getParent()),
- DT, LI);
+ return isPotentiallyReachableFromMany(
+ Worklist, const_cast<BasicBlock *>(B->getParent()), DT, LI);
}
diff --git a/llvm/lib/Analysis/CaptureTracking.cpp b/llvm/lib/Analysis/CaptureTracking.cpp
index 5a547541795..52ef807aeb5 100644
--- a/llvm/lib/Analysis/CaptureTracking.cpp
+++ b/llvm/lib/Analysis/CaptureTracking.cpp
@@ -52,34 +52,136 @@ namespace {
bool Captured;
};
+ struct NumberedInstCache {
+ SmallDenseMap<const Instruction *, unsigned, 32> NumberedInsts;
+ BasicBlock::const_iterator LastInstFound;
+ unsigned LastInstPos;
+ const BasicBlock *BB;
+
+ NumberedInstCache(const BasicBlock *BasicB) : LastInstPos(0), BB(BasicB) {
+ LastInstFound = BB->end();
+ }
+
+ /// \brief Find the first instruction 'A' or 'B' in 'BB'. Number out
+ /// instruction while walking 'BB'.
+ const Instruction *find(const Instruction *A, const Instruction *B) {
+ const Instruction *Inst = nullptr;
+ assert(!(LastInstFound == BB->end() && LastInstPos != 0) &&
+ "Instruction supposed to be in NumberedInsts");
+
+ // Start the search with the instruction found in the last lookup round.
+ auto II = BB->begin();
+ auto IE = BB->end();
+ if (LastInstFound != IE)
+ II = std::next(LastInstFound);
+
+ // Number all instructions up to the point where we find 'A' or 'B'.
+ for (++LastInstPos; II != IE; ++II, ++LastInstPos) {
+ Inst = cast<Instruction>(II);
+ NumberedInsts[Inst] = LastInstPos;
+ if (Inst == A || Inst == B)
+ break;
+ }
+
+ assert(II != IE && "Instruction not found?");
+ LastInstFound = II;
+ return Inst;
+ }
+
+ /// \brief Find out whether 'A' dominates 'B', meaning whether 'A'
+ /// comes before 'B' in 'BB'. This is a simplification that considers
+ /// cached instruction positions and ignores other basic blocks, being
+ /// only relevant to compare relative instructions positions inside 'BB'.
+ bool dominates(const Instruction *A, const Instruction *B) {
+ assert(A->getParent() == B->getParent() &&
+ "Instructions must be in the same basic block!");
+
+ unsigned NA = NumberedInsts.lookup(A);
+ unsigned NB = NumberedInsts.lookup(B);
+ if (NA && NB)
+ return NA < NB;
+ if (NA)
+ return true;
+ if (NB)
+ return false;
+
+ return A == find(A, B);
+ }
+ };
+
/// 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)
- : BeforeHere(I), DT(DT), ReturnCaptures(ReturnCaptures),
- IncludeI(IncludeI), Captured(false) {}
+ : LocalInstCache(I->getParent()), BeforeHere(I), DT(DT),
+ ReturnCaptures(ReturnCaptures), IncludeI(IncludeI), Captured(false) {}
void tooManyUses() override { Captured = true; }
- bool shouldExplore(const Use *U) override {
- Instruction *I = cast<Instruction>(U->getUser());
- if (BeforeHere == I && !IncludeI)
- return false;
-
+ 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
+ // 'LocalInstCache', 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 (!LocalInstCache.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));
+ if (!isPotentiallyReachableFromMany(Worklist, BB, DT))
+ return true;
+
return false;
+ }
+
// 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;
}
@@ -87,21 +189,14 @@ namespace {
if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures)
return false;
- Instruction *I = cast<Instruction>(U->getUser());
- if (BeforeHere == I && !IncludeI)
+ if (!shouldExplore(U))
return false;
- BasicBlock *BB = I->getParent();
- // Same logic as in shouldExplore.
- if (BeforeHere != I && !DT->isReachableFromEntry(BB))
- return false;
- if (BeforeHere != I && DT->dominates(BeforeHere, I) &&
- !isPotentiallyReachable(I, BeforeHere, DT))
- return false;
Captured = true;
return true;
}
+ NumberedInstCache LocalInstCache;
const Instruction *BeforeHere;
DominatorTree *DT;
OpenPOWER on IntegriCloud