Add an optional list of blocks to avoid when looking for a path in isPotentiallyReachable.
The leads to some ambiguous overloads, so update three callers.
Differential Revision: https://reviews.llvm.org/D60085
llvm-svn: 357447
diff --git a/llvm/lib/Analysis/CFG.cpp b/llvm/lib/Analysis/CFG.cpp
index 6ef36dc..44191f0 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 @@
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 @@
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 @@
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 @@
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 @@
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);
}