diff options
author | Owen Anderson <resistor@mac.com> | 2007-08-01 22:01:54 +0000 |
---|---|---|
committer | Owen Anderson <resistor@mac.com> | 2007-08-01 22:01:54 +0000 |
commit | 9066020993695a690c1f979f9cac4e14d325e237 (patch) | |
tree | 96d88a34a49128b109c6423bbc6de462bb738a52 /lib/Analysis/MemoryDependenceAnalysis.cpp | |
parent | c5dd54154acfd222a39cbdc01e4d5202a78f268b (diff) | |
download | external_llvm-9066020993695a690c1f979f9cac4e14d325e237.zip external_llvm-9066020993695a690c1f979f9cac4e14d325e237.tar.gz external_llvm-9066020993695a690c1f979f9cac4e14d325e237.tar.bz2 |
Make non-local memdep not be recursive, and fix a bug on 403.gcc that this exposed.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40692 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Analysis/MemoryDependenceAnalysis.cpp')
-rw-r--r-- | lib/Analysis/MemoryDependenceAnalysis.cpp | 91 |
1 files changed, 45 insertions, 46 deletions
diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp index 5a8cb7b..a280fff 100644 --- a/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -101,63 +101,62 @@ Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C, Instruc return NonLocal; } -bool MemoryDependenceAnalysis::nonLocalHelper(Instruction* query, +void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query, BasicBlock* block, - DenseMap<BasicBlock*, Value*>& resp, - SmallPtrSet<BasicBlock*, 4>& visited) { - if (resp.count(block)) - return resp[block] != None; + DenseMap<BasicBlock*, Value*>& resp) { + SmallPtrSet<BasicBlock*, 4> visited; + SmallVector<BasicBlock*, 4> stack; + stack.push_back(block); - Instruction* localDep = getDependency(query, 0, block); - if (localDep != NonLocal) { - resp.insert(std::make_pair(block, localDep)); - return true; + while (!stack.empty()) { + BasicBlock* BB = stack.back(); + + visited.insert(BB); + + if (resp.count(BB)) { + stack.pop_back(); + continue; + } + + if (BB != block) { + Instruction* localDep = getDependency(query, 0, BB); + if (localDep != NonLocal) { + resp.insert(std::make_pair(BB, localDep)); + continue; + } + } + + bool predOnStack = false; + bool inserted = false; + for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); + PI != PE; ++PI) + if (!visited.count(*PI)) { + stack.push_back(*PI); + inserted = true; + } else + predOnStack = true; + + if (inserted) + continue; + else if (!inserted && !predOnStack) { + resp.insert(std::make_pair(BB, None)); + } else if (!inserted && predOnStack){ + resp.insert(std::make_pair(BB, NonLocal)); + } + + stack.pop_back(); } - - visited.insert(block); - - bool inserted = false; - bool predOnStack = false; - for (pred_iterator PI = pred_begin(block), PE = pred_end(block); - PI != PE; ++PI) - if (!visited.count(*PI)) - inserted |= nonLocalHelper(query, *PI, resp, visited); - else - predOnStack = true; - - visited.erase(block); - - if (!inserted && !predOnStack) - resp.insert(std::make_pair(block, None)); - else if (inserted && predOnStack) - resp.insert(std::make_pair(block, NonLocal)); - - return inserted; } -bool MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query, +void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query, DenseMap<BasicBlock*, Value*>& resp) { Instruction* localDep = getDependency(query); if (localDep != NonLocal) { resp.insert(std::make_pair(query->getParent(), localDep)); - return true; - } - - bool inserted = false; - SmallPtrSet<BasicBlock*, 4> visited; - visited.insert(query->getParent()); - - BasicBlock* parent = query->getParent(); - for (pred_iterator PI = pred_begin(parent), PE = pred_end(parent); - PI != PE; ++PI) { - if (!visited.count(*PI)) - inserted |= nonLocalHelper(query, *PI, resp, visited); + return; } - if (!inserted) - resp.insert(std::make_pair(query->getParent(), None)); - - return inserted; + nonLocalHelper(query, query->getParent(), resp); } /// getDependency - Return the instruction on which a memory operation |