diff options
author | Owen Anderson <resistor@mac.com> | 2007-07-24 21:52:37 +0000 |
---|---|---|
committer | Owen Anderson <resistor@mac.com> | 2007-07-24 21:52:37 +0000 |
commit | 4beedbd0063a8ba6f97db02c3c94707d8ab45b50 (patch) | |
tree | 0b7c0cd04ba66a17d589f10abe8693e4b6c990c2 /lib/Analysis/MemoryDependenceAnalysis.cpp | |
parent | bf31b85ea2a3bf17f3934b7e139b7475a84429fa (diff) | |
download | external_llvm-4beedbd0063a8ba6f97db02c3c94707d8ab45b50.zip external_llvm-4beedbd0063a8ba6f97db02c3c94707d8ab45b50.tar.gz external_llvm-4beedbd0063a8ba6f97db02c3c94707d8ab45b50.tar.bz2 |
Add initial support for non-local memory dependence analysis.
NOTE: This has only been cursorily tested. Expected improvements soon.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40476 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Analysis/MemoryDependenceAnalysis.cpp')
-rw-r--r-- | lib/Analysis/MemoryDependenceAnalysis.cpp | 59 |
1 files changed, 53 insertions, 6 deletions
diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp index 3ec733f..34c4348 100644 --- a/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -19,6 +19,7 @@ #include "llvm/Instructions.h" #include "llvm/Function.h" #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Support/CFG.h" #include "llvm/Target/TargetData.h" using namespace llvm; @@ -26,7 +27,7 @@ using namespace llvm; char MemoryDependenceAnalysis::ID = 0; Instruction* MemoryDependenceAnalysis::NonLocal = (Instruction*)0; -Instruction* MemoryDependenceAnalysis::None = (Instruction*)~0; +Instruction* MemoryDependenceAnalysis::None = (Instruction*)(~0 - 1); // Register this pass... static RegisterPass<MemoryDependenceAnalysis> X("memdep", @@ -100,15 +101,60 @@ Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C, Instruc return NonLocal; } +SmallPtrSet<Instruction*, 4> MemoryDependenceAnalysis::nonLocalHelper(Instruction* query, + BasicBlock* block) { + SmallPtrSet<Instruction*, 4> ret; + + Instruction* localDep = getDependency(query, block->end(), block); + if (localDep != NonLocal) { + ret.insert(localDep); + return ret; + } + + for (pred_iterator PI = pred_begin(block), PE = pred_end(block); + PI != PE; ++PI) { + SmallPtrSet<Instruction*, 4> pred_deps = nonLocalHelper(query, *PI); + for (SmallPtrSet<Instruction*, 4>::iterator I = pred_deps.begin(), + E = pred_deps.end(); I != E; ++I) + ret.insert(*I); + } + + if (ret.empty()) + ret.insert(None); + + return ret; +} + +SmallPtrSet<Instruction*, 4> MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query) { + SmallPtrSet<Instruction*, 4> ret; + + Instruction* localDep = getDependency(query); + if (localDep != NonLocal) { + ret.insert(localDep); + return ret; + } + + BasicBlock* parent = query->getParent(); + for (pred_iterator PI = pred_begin(parent), PE = pred_end(parent); + PI != PE; ++PI) { + SmallPtrSet<Instruction*, 4> pred_deps = nonLocalHelper(query, *PI); + for (SmallPtrSet<Instruction*, 4>::iterator I = pred_deps.begin(), + E = pred_deps.end(); I != E; ++I) + ret.insert(*I); + } + + if (ret.empty()) + ret.insert(None); + + return ret; +} + /// getDependency - Return the instruction on which a memory operation /// depends. The local paramter indicates if the query should only /// evaluate dependencies within the same basic block. Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query, Instruction* start, - bool local) { - if (!local) - assert(0 && "Non-local memory dependence is not yet supported."); - + BasicBlock* block) { // Start looking for dependencies with the queried inst BasicBlock::iterator QI = query; @@ -154,7 +200,8 @@ Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query, else return None; - BasicBlock::iterator blockBegin = query->getParent()->begin(); + BasicBlock::iterator blockBegin = block ? block->begin() + : query->getParent()->begin(); while (QI != blockBegin) { --QI; |