From 0ec48ddef20deaa061152d86645972122beef605 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Sat, 29 Nov 2008 22:02:15 +0000 Subject: [PATCH] implement some fixme's: when deleting an instruction with an entry in the nonlocal deps map, don't reset entries referencing that instruction to [dirty, null], instead, set them to [dirty,next] where next is the instruction after the deleted one. Use this information in the non-local deps code to avoid rescanning entire blocks. This speeds up GVN slightly by avoiding pointless work. On 403.gcc this makes GVN 1.5% faster. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60256 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/MemoryDependenceAnalysis.h | 14 ++--- lib/Analysis/MemoryDependenceAnalysis.cpp | 76 +++++++++++++++++++----- 2 files changed, 67 insertions(+), 23 deletions(-) diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h index 10aeb290c84..5bd6a82d013 100644 --- a/include/llvm/Analysis/MemoryDependenceAnalysis.h +++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h @@ -84,19 +84,15 @@ namespace llvm { /// DepType - This enum is used to indicate what flavor of dependence this /// is. If the type is Normal, there is an associated instruction pointer. enum DepType { - /// Dirty - Entries with this marker may come in two forms, depending on - /// whether they are in a LocalDeps map or NonLocalDeps map. In either - /// case, this marker indicates that the cached value has been invalidated - /// by a removeInstruction call. - /// - /// If in the LocalDeps map, the Instruction field will indicate the place - /// in the current block to start scanning. If in the non-localdeps map, - /// the instruction will be null. + /// Dirty - Entries with this marker occur in a LocalDeps map or + /// NonLocalDeps map when the instruction they previously referenced was + /// removed from MemDep. In either case, the entry may include an + /// instruction pointer. If so, the pointer is an instruction in the + /// block where scanning can start from, saving some work. /// /// In a default-constructed DepResultTy object, the type will be Dirty /// and the instruction pointer will be null. /// - /// FIXME: Why not add a scanning point for the non-local deps map??? Dirty = 0, /// Normal - This is a normal instruction dependence. The pointer member diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp index 099d43492cd..56128e68966 100644 --- a/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -28,8 +28,8 @@ #include "llvm/Target/TargetData.h" using namespace llvm; -STATISTIC(NumCacheNonlocal, "Number of cached non-local responses"); -STATISTIC(NumUncacheNonlocal, "Number of uncached non-local responses"); +STATISTIC(NumCacheNonLocal, "Number of cached non-local responses"); +STATISTIC(NumUncacheNonLocal, "Number of uncached non-local responses"); char MemoryDependenceAnalysis::ID = 0; @@ -112,8 +112,10 @@ getNonLocalDependency(Instruction *QueryInst, "getNonLocalDependency should only be used on insts with non-local deps!"); DenseMap &Cache = NonLocalDeps[QueryInst]; - /// DirtyBlocks - This is the set of blocks that need to be recomputed. This - /// can happen due to instructions being deleted etc. + /// DirtyBlocks - This is the set of blocks that need to be recomputed. In + /// the cached case, this can happen due to instructions being deleted etc. In + /// the uncached case, this starts out as the set of predecessors we care + /// about. SmallVector DirtyBlocks; if (!Cache.empty()) { @@ -126,12 +128,15 @@ getNonLocalDependency(Instruction *QueryInst, if (I->second.getInt() == Dirty) DirtyBlocks.push_back(I->first); - NumCacheNonlocal++; + NumCacheNonLocal++; + + //cerr << "CACHED CASE: " << DirtyBlocks.size() << " dirty: " + // << Cache.size() << " cached: " << *QueryInst; } else { // Seed DirtyBlocks with each of the preds of QueryInst's block. BasicBlock *QueryBB = QueryInst->getParent(); DirtyBlocks.append(pred_begin(QueryBB), pred_end(QueryBB)); - NumUncacheNonlocal++; + NumUncacheNonLocal++; } // Iterate while we still have blocks to update. @@ -149,7 +154,14 @@ getNonLocalDependency(Instruction *QueryInst, // Find out if this block has a local dependency for QueryInst. // FIXME: If the dirty entry has an instruction pointer, scan from it! // FIXME: Don't convert back and forth for MemDepResult <-> DepResultTy. - DirtyBBEntry = ConvFromResult(getDependencyFrom(QueryInst, DirtyBB->end(), + + // If the dirty entry has a pointer, start scanning from it so we don't have + // to rescan the entire block. + BasicBlock::iterator ScanPos = DirtyBB->end(); + if (Instruction *Inst = DirtyBBEntry.getPointer()) + ScanPos = Inst; + + DirtyBBEntry = ConvFromResult(getDependencyFrom(QueryInst, ScanPos, DirtyBB)); // If the block has a dependency (i.e. it isn't completely transparent to @@ -289,7 +301,8 @@ MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { // Check for a cached result DepResultTy &LocalCache = LocalDeps[QueryInst]; - // If the cached entry is non-dirty, just return it. + // If the cached entry is non-dirty, just return it. Note that this depends + // on DepResultTy's default constructing to 'dirty'. if (LocalCache.getInt() != Dirty) return ConvToResult(LocalCache); @@ -337,6 +350,8 @@ void MemoryDependenceAnalysis::dropInstruction(Instruction* drop) { ReverseNonLocalDeps[Inst].erase(drop); if (ReverseNonLocalDeps.count(drop)) { + SmallVector, 8> ReverseDepsToAdd; + SmallPtrSet& set = ReverseNonLocalDeps[drop]; for (SmallPtrSet::iterator I = set.begin(), E = set.end(); @@ -344,9 +359,24 @@ void MemoryDependenceAnalysis::dropInstruction(Instruction* drop) { for (DenseMap::iterator DI = NonLocalDeps[*I].begin(), DE = NonLocalDeps[*I].end(); DI != DE; ++DI) - if (DI->second == DepResultTy(drop, Normal)) - // FIXME: Why not remember the old insertion point?? - DI->second = DepResultTy(0, Dirty); + if (DI->second.getPointer() == drop) { + // Convert to a dirty entry for the subsequent instruction. + DI->second.setInt(Dirty); + if (drop->isTerminator()) + DI->second.setPointer(0); + else { + Instruction *NextI = next(BasicBlock::iterator(drop)); + DI->second.setPointer(NextI); + ReverseDepsToAdd.push_back(std::make_pair(NextI, *I)); + } + } + + // Add new reverse deps after scanning the set, to avoid invalidating 'Set' + while (!ReverseDepsToAdd.empty()) { + ReverseNonLocalDeps[ReverseDepsToAdd.back().first] + .insert(ReverseDepsToAdd.back().second); + ReverseDepsToAdd.pop_back(); + } } ReverseNonLocalDeps.erase(drop); @@ -433,15 +463,33 @@ void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) { ReverseDepIt = ReverseNonLocalDeps.find(RemInst); if (ReverseDepIt != ReverseNonLocalDeps.end()) { + SmallVector, 8> ReverseDepsToAdd; + SmallPtrSet& set = ReverseDepIt->second; for (SmallPtrSet::iterator I = set.begin(), E = set.end(); I != E; ++I) for (DenseMap::iterator DI = NonLocalDeps[*I].begin(), DE = NonLocalDeps[*I].end(); DI != DE; ++DI) - if (DI->second == DepResultTy(RemInst, Normal)) - // FIXME: Why not remember the old insertion point?? - DI->second = DepResultTy(0, Dirty); + if (DI->second.getPointer() == RemInst) { + // Convert to a dirty entry for the subsequent instruction. + DI->second.setInt(Dirty); + if (RemInst->isTerminator()) + DI->second.setPointer(0); + else { + Instruction *NextI = next(BasicBlock::iterator(RemInst)); + DI->second.setPointer(NextI); + ReverseDepsToAdd.push_back(std::make_pair(NextI, *I)); + } + } + + // Add new reverse deps after scanning the set, to avoid invalidating 'Set' + while (!ReverseDepsToAdd.empty()) { + ReverseNonLocalDeps[ReverseDepsToAdd.back().first] + .insert(ReverseDepsToAdd.back().second); + ReverseDepsToAdd.pop_back(); + } + ReverseNonLocalDeps.erase(ReverseDepIt); } -- 2.11.0