summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Analysis')
-rw-r--r--llvm/lib/Analysis/BasicAliasAnalysis.cpp2
-rw-r--r--llvm/lib/Analysis/CFG.cpp73
-rw-r--r--llvm/lib/Analysis/CaptureTracking.cpp4
3 files changed, 54 insertions, 25 deletions
diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
index 232132958f7..3721c99883b 100644
--- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
@@ -1906,7 +1906,7 @@ bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,
// the Values cannot come from different iterations of a potential cycle the
// phi nodes could be involved in.
for (auto *P : VisitedPhiBBs)
- if (isPotentiallyReachable(&P->front(), Inst, DT, LI))
+ if (isPotentiallyReachable(&P->front(), Inst, nullptr, DT, LI))
return false;
return true;
diff --git a/llvm/lib/Analysis/CFG.cpp b/llvm/lib/Analysis/CFG.cpp
index 6ef36dcad57..44191f094e2 100644
--- a/llvm/lib/Analysis/CFG.cpp
+++ b/llvm/lib/Analysis/CFG.cpp
@@ -12,6 +12,7 @@
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/CFG.h"
+#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/IR/Dominators.h"
@@ -119,22 +120,33 @@ static const Loop *getOutermostLoop(const LoopInfo *LI, const BasicBlock *BB) {
return L;
}
-// True if there is a loop which contains both BB1 and BB2.
-static bool loopContainsBoth(const LoopInfo *LI,
- const BasicBlock *BB1, const BasicBlock *BB2) {
- const Loop *L1 = getOutermostLoop(LI, BB1);
- const Loop *L2 = getOutermostLoop(LI, BB2);
- return L1 != nullptr && L1 == L2;
-}
-
bool llvm::isPotentiallyReachableFromMany(
SmallVectorImpl<BasicBlock *> &Worklist, BasicBlock *StopBB,
- const DominatorTree *DT, const LoopInfo *LI) {
+ const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, 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))
DT = nullptr;
+ // We can't skip directly from a block that dominates the stop block if the
+ // exclusion block is potentially in between.
+ if (ExclusionSet && !ExclusionSet->empty())
+ DT = nullptr;
+
+ // Normally any block in a loop is reachable from any other block in a loop,
+ // however excluded blocks might partition the body of a loop to make that
+ // untrue.
+ SmallPtrSet<const Loop *, 8> LoopsWithHoles;
+ if (LI && ExclusionSet) {
+ for (auto BB : *ExclusionSet) {
+ if (const Loop *L = getOutermostLoop(LI, BB))
+ LoopsWithHoles.insert(L);
+ }
+ }
+
+ const Loop *StopLoop = LI ? getOutermostLoop(LI, StopBB) : nullptr;
+
// Limit the number of blocks we visit. The goal is to avoid run-away compile
// times on large CFGs without hampering sensible code. Arbitrarily chosen.
unsigned Limit = 32;
@@ -145,10 +157,23 @@ bool llvm::isPotentiallyReachableFromMany(
continue;
if (BB == StopBB)
return true;
+ if (ExclusionSet && ExclusionSet->count(BB))
+ continue;
if (DT && DT->dominates(BB, StopBB))
return true;
- if (LI && loopContainsBoth(LI, BB, StopBB))
- return true;
+
+ const Loop *Outer = nullptr;
+ if (LI) {
+ Outer = getOutermostLoop(LI, BB);
+ // If we're in a loop with a hole, not all blocks in the loop are
+ // reachable from all other blocks. That implies we can't simply jump to
+ // the loop's exit blocks, as that exit might need to pass through an
+ // excluded block. Clear Outer so we process BB's successors.
+ if (LoopsWithHoles.count(Outer))
+ Outer = nullptr;
+ if (StopLoop && Outer == StopLoop)
+ return true;
+ }
if (!--Limit) {
// We haven't been able to prove it one way or the other. Conservatively
@@ -156,7 +181,7 @@ bool llvm::isPotentiallyReachableFromMany(
return true;
}
- if (const Loop *Outer = LI ? getOutermostLoop(LI, BB) : nullptr) {
+ if (Outer) {
// All blocks in a single loop are reachable from all other blocks. From
// any of these blocks, we can skip directly to the exits of the loop,
// ignoring any other blocks inside the loop body.
@@ -180,11 +205,13 @@ bool llvm::isPotentiallyReachable(const BasicBlock *A, const BasicBlock *B,
Worklist.push_back(const_cast<BasicBlock*>(A));
return isPotentiallyReachableFromMany(Worklist, const_cast<BasicBlock *>(B),
- DT, LI);
+ nullptr, DT, LI);
}
-bool llvm::isPotentiallyReachable(const Instruction *A, const Instruction *B,
- const DominatorTree *DT, const LoopInfo *LI) {
+bool llvm::isPotentiallyReachable(
+ const Instruction *A, const Instruction *B,
+ const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
+ const LoopInfo *LI) {
assert(A->getParent()->getParent() == B->getParent()->getParent() &&
"This analysis is function-local!");
@@ -230,14 +257,16 @@ bool llvm::isPotentiallyReachable(const Instruction *A, const Instruction *B,
if (DT->isReachableFromEntry(A->getParent()) !=
DT->isReachableFromEntry(B->getParent()))
return false;
- if (A->getParent() == &A->getParent()->getParent()->getEntryBlock() &&
- DT->isReachableFromEntry(B->getParent()))
- return true;
- if (B->getParent() == &A->getParent()->getParent()->getEntryBlock() &&
- DT->isReachableFromEntry(A->getParent()))
- return false;
+ if (!ExclusionSet || ExclusionSet->empty()) {
+ if (A->getParent() == &A->getParent()->getParent()->getEntryBlock() &&
+ DT->isReachableFromEntry(B->getParent()))
+ return true;
+ if (B->getParent() == &A->getParent()->getParent()->getEntryBlock() &&
+ DT->isReachableFromEntry(A->getParent()))
+ return false;
+ }
}
return isPotentiallyReachableFromMany(
- Worklist, const_cast<BasicBlock *>(B->getParent()), DT, LI);
+ Worklist, const_cast<BasicBlock *>(B->getParent()), ExclusionSet, DT, LI);
}
diff --git a/llvm/lib/Analysis/CaptureTracking.cpp b/llvm/lib/Analysis/CaptureTracking.cpp
index d3bd556f8bc..d2a0920413c 100644
--- a/llvm/lib/Analysis/CaptureTracking.cpp
+++ b/llvm/lib/Analysis/CaptureTracking.cpp
@@ -101,14 +101,14 @@ namespace {
SmallVector<BasicBlock*, 32> Worklist;
Worklist.append(succ_begin(BB), succ_end(BB));
- return !isPotentiallyReachableFromMany(Worklist, BB, DT);
+ return !isPotentiallyReachableFromMany(Worklist, BB, nullptr, 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))
+ !isPotentiallyReachable(I, BeforeHere, nullptr, DT))
return true;
return false;
OpenPOWER on IntegriCloud