summaryrefslogtreecommitdiffstats
path: root/lib/Analysis
diff options
context:
space:
mode:
authorManman Ren <mren@apple.com>2013-01-04 19:19:47 +0000
committerManman Ren <mren@apple.com>2013-01-04 19:19:47 +0000
commitc55bd47105ef8e362cfb2a2c97ee3e23145aca4d (patch)
treedcfd58c47215cc7c814d162ce379239be6b1e587 /lib/Analysis
parent63723e5bf8bc1e5b699733cb79992b720b20f0d5 (diff)
downloadexternal_llvm-c55bd47105ef8e362cfb2a2c97ee3e23145aca4d.zip
external_llvm-c55bd47105ef8e362cfb2a2c97ee3e23145aca4d.tar.gz
external_llvm-c55bd47105ef8e362cfb2a2c97ee3e23145aca4d.tar.bz2
Memory Dependence Analysis: fix a miscompile that uses DT to approxmiate the
reachablity. We conservatively approximate the reachability analysis by saying it is not reachable if there is a single path starting from "From" and the path does not reach "To". rdar://12801584 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171512 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Analysis')
-rw-r--r--lib/Analysis/AliasAnalysis.cpp38
1 files changed, 34 insertions, 4 deletions
diff --git a/lib/Analysis/AliasAnalysis.cpp b/lib/Analysis/AliasAnalysis.cpp
index 7b2e60d..f32bd70 100644
--- a/lib/Analysis/AliasAnalysis.cpp
+++ b/lib/Analysis/AliasAnalysis.cpp
@@ -361,8 +361,28 @@ AliasAnalysis::getModRefInfo(const AtomicRMWInst *RMW, const Location &Loc) {
}
namespace {
+ // Conservatively return true. Return false, if there is a single path
+ // starting from "From" and the path does not reach "To".
+ static bool hasPath(const BasicBlock *From, const BasicBlock *To) {
+ const unsigned MaxCheck = 5;
+ const BasicBlock *Current = From;
+ for (unsigned I = 0; I < MaxCheck; I++) {
+ unsigned NumSuccs = Current->getTerminator()->getNumSuccessors();
+ if (NumSuccs > 1)
+ return true;
+ if (NumSuccs == 0)
+ return false;
+ Current = Current->getTerminator()->getSuccessor(0);
+ if (Current == To)
+ return true;
+ }
+ return true;
+ }
+
/// 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(const Instruction *I, DominatorTree *DT)
: BeforeHere(I), DT(DT), Captured(false) {}
@@ -372,8 +392,15 @@ namespace {
bool shouldExplore(Use *U) {
Instruction *I = cast<Instruction>(U->getUser());
BasicBlock *BB = I->getParent();
- if (BeforeHere != I &&
- (!DT->isReachableFromEntry(BB) || DT->dominates(BeforeHere, I)))
+ // 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 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) &&
+ !hasPath(BB, BeforeHere->getParent()))
return false;
return true;
}
@@ -381,8 +408,11 @@ namespace {
bool captured(Use *U) {
Instruction *I = cast<Instruction>(U->getUser());
BasicBlock *BB = I->getParent();
- if (BeforeHere != I &&
- (!DT->isReachableFromEntry(BB) || DT->dominates(BeforeHere, I)))
+ // Same logic as in shouldExplore.
+ if (BeforeHere != I && !DT->isReachableFromEntry(BB))
+ return false;
+ if (BeforeHere != I && DT->dominates(BeforeHere, I) &&
+ !hasPath(BB, BeforeHere->getParent()))
return false;
Captured = true;
return true;