aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorBob Wilson <bob.wilson@apple.com>2010-02-16 19:51:59 +0000
committerBob Wilson <bob.wilson@apple.com>2010-02-16 19:51:59 +0000
commit484d4a30c055eef3101d01a7a468db3413dd20d3 (patch)
treed3dbf1f999ddbf0f8516c6387d767c4c323f6f75
parentadb6f226714dcfae363f51b453c4590b0f42da5e (diff)
downloadexternal_llvm-484d4a30c055eef3101d01a7a468db3413dd20d3.zip
external_llvm-484d4a30c055eef3101d01a7a468db3413dd20d3.tar.gz
external_llvm-484d4a30c055eef3101d01a7a468db3413dd20d3.tar.bz2
Split critical edges as needed for load PRE.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@96378 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r--include/llvm/Analysis/MemoryDependenceAnalysis.h7
-rw-r--r--lib/Analysis/MemoryDependenceAnalysis.cpp7
-rw-r--r--lib/Transforms/Scalar/GVN.cpp38
3 files changed, 43 insertions, 9 deletions
diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h
index f83cc4f..f6aab03 100644
--- a/include/llvm/Analysis/MemoryDependenceAnalysis.h
+++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h
@@ -249,7 +249,7 @@ namespace llvm {
SmallPtrSet<Instruction*, 4> > ReverseDepMapType;
ReverseDepMapType ReverseLocalDeps;
- // A reverse mapping form dependencies to the non-local dependees.
+ // A reverse mapping from dependencies to the non-local dependees.
ReverseDepMapType ReverseNonLocalDeps;
/// Current AA implementation, just a cache.
@@ -312,6 +312,11 @@ namespace llvm {
/// value and replaces the other value with ptr. This can make Ptr available
/// in more places that cached info does not necessarily keep.
void invalidateCachedPointerInfo(Value *Ptr);
+
+ /// invalidateCachedPredecessors - Clear the PredIteratorCache info.
+ /// This needs to be done when the CFG changes, e.g., due to splitting
+ /// critical edges.
+ void invalidateCachedPredecessors();
private:
MemDepResult getPointerDependencyFrom(Value *Pointer, uint64_t MemSize,
diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp
index 183edf4..04641e8 100644
--- a/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -1016,6 +1016,13 @@ void MemoryDependenceAnalysis::invalidateCachedPointerInfo(Value *Ptr) {
RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, true));
}
+/// invalidateCachedPredecessors - Clear the PredIteratorCache info.
+/// This needs to be done when the CFG changes, e.g., due to splitting
+/// critical edges.
+void MemoryDependenceAnalysis::invalidateCachedPredecessors() {
+ PredCache->clear();
+}
+
/// removeInstruction - Remove an instruction from the dependence analysis,
/// updating the dependence of instructions that previously depended on it.
/// This method attempts to keep the cache coherent using the reverse map.
diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index b3a8687..c144e16 100644
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -674,6 +674,9 @@ namespace {
ValueTable VN;
DenseMap<BasicBlock*, ValueNumberScope*> localAvail;
+ // List of critical edges to be split between iterations.
+ SmallVector<std::pair<TerminatorInst*, unsigned>, 4> toSplit;
+
// This transformation requires dominator postdominator info
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<DominatorTree>();
@@ -701,6 +704,7 @@ namespace {
Value *lookupNumber(BasicBlock *BB, uint32_t num);
void cleanupGlobalSets();
void verifyRemoved(const Instruction *I) const;
+ bool splitCriticalEdges();
};
char GVN::ID = 0;
@@ -1583,10 +1587,15 @@ bool GVN::processNonLocalLoad(LoadInst *LI,
continue;
}
PredLoads[Pred] = 0;
- // We don't currently handle critical edges :(
+
if (Pred->getTerminator()->getNumSuccessors() != 1) {
- DEBUG(dbgs() << "COULD NOT PRE LOAD BECAUSE OF CRITICAL EDGE '"
- << Pred->getName() << "': " << *LI << '\n');
+ if (isa<IndirectBrInst>(Pred->getTerminator())) {
+ DEBUG(dbgs() << "COULD NOT PRE LOAD BECAUSE OF INDBR CRITICAL EDGE '"
+ << Pred->getName() << "': " << *LI << '\n');
+ return false;
+ }
+ unsigned SuccNum = SuccessorNumber(Pred, LoadBB);
+ toSplit.push_back(std::make_pair(Pred->getTerminator(), SuccNum));
return false;
}
}
@@ -2004,6 +2013,8 @@ bool GVN::runOnFunction(Function& F) {
while (ShouldContinue) {
DEBUG(dbgs() << "GVN iteration: " << Iteration << "\n");
ShouldContinue = iterateOnFunction(F);
+ if (splitCriticalEdges())
+ ShouldContinue = true;
Changed |= ShouldContinue;
++Iteration;
}
@@ -2070,7 +2081,6 @@ bool GVN::processBlock(BasicBlock *BB) {
/// control flow patterns and attempts to perform simple PRE at the join point.
bool GVN::performPRE(Function &F) {
bool Changed = false;
- SmallVector<std::pair<TerminatorInst*, unsigned>, 4> toSplit;
DenseMap<BasicBlock*, Value*> predMap;
for (df_iterator<BasicBlock*> DI = df_begin(&F.getEntryBlock()),
DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) {
@@ -2209,11 +2219,23 @@ bool GVN::performPRE(Function &F) {
}
}
- for (SmallVector<std::pair<TerminatorInst*, unsigned>, 4>::iterator
- I = toSplit.begin(), E = toSplit.end(); I != E; ++I)
- SplitCriticalEdge(I->first, I->second, this);
+ if (splitCriticalEdges())
+ Changed = true;
+
+ return Changed;
+}
- return Changed || toSplit.size();
+/// splitCriticalEdges - Split critical edges found during the previous
+/// iteration that may enable further optimization.
+bool GVN::splitCriticalEdges() {
+ if (toSplit.empty())
+ return false;
+ do {
+ std::pair<TerminatorInst*, unsigned> Edge = toSplit.pop_back_val();
+ SplitCriticalEdge(Edge.first, Edge.second, this);
+ } while (!toSplit.empty());
+ MD->invalidateCachedPredecessors();
+ return true;
}
/// iterateOnFunction - Executes one iteration of GVN