From bf145d6e2ba01f5099ccaa1b58ed3619406928a0 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Mon, 1 Dec 2008 01:15:42 +0000 Subject: Reimplement the non-local dependency data structure in terms of a sorted vector instead of a densemap. This shrinks the memory usage of this thing substantially (the high water mark) as well as making operations like scanning it faster. This speeds up memdep slightly, gvn goes from 3.9376 to 3.9118s on 403.gcc This also splits out the statistics for the cached non-local case to differentiate between the dirty and clean cached case. Here's the stats for 403.gcc: 6153 memdep - Number of dirty cached non-local responses 169336 memdep - Number of fully cached non-local responses 162428 memdep - Number of uncached non-local responses yay for caching :) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60313 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/MemoryDependenceAnalysis.h | 36 ++++++++++++++---------- 1 file changed, 21 insertions(+), 15 deletions(-) (limited to 'include/llvm') diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h index 4537405..c9a142e 100644 --- a/include/llvm/Analysis/MemoryDependenceAnalysis.h +++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h @@ -36,7 +36,7 @@ namespace llvm { /// Invalid - Clients of MemDep never see this. Invalid = 0, /// Normal - This is a normal instruction dependence. The pointer member - /// of the DepResultTy pair holds the instruction. + /// of the MemDepResult pair holds the instruction. Normal, /// NonLocal - This marker indicates that the query has no dependency in @@ -85,8 +85,10 @@ namespace llvm { /// is depended on. Otherwise, return null. Instruction *getInst() const { return Value.getPointer(); } - bool operator==(const MemDepResult &M) { return M.Value == Value; } - bool operator!=(const MemDepResult &M) { return M.Value != Value; } + bool operator==(const MemDepResult &M) const { return M.Value == Value; } + bool operator!=(const MemDepResult &M) const { return M.Value != Value; } + bool operator<(const MemDepResult &M) const { return M.Value < Value; } + bool operator>(const MemDepResult &M) const { return M.Value > Value; } private: friend class MemoryDependenceAnalysis; /// Dirty - Entries with this marker occur in a LocalDeps map or @@ -95,14 +97,14 @@ namespace llvm { /// 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 + /// In a default-constructed MemDepResult object, the type will be Dirty /// and the instruction pointer will be null. /// - + /// isDirty - Return true if this is a MemDepResult in its dirty/invalid. /// state. bool isDirty() const { return Value.getInt() == Invalid; } - + static MemDepResult getDirty(Instruction *Inst) { return MemDepResult(PairTy(Inst, Invalid)); } @@ -128,12 +130,15 @@ namespace llvm { typedef DenseMap LocalDepMapType; LocalDepMapType LocalDeps; - typedef DenseMap NonLocalDepInfo; + public: + typedef std::pair NonLocalDepEntry; + typedef std::vector NonLocalDepInfo; + private: /// PerInstNLInfo - This is the instruction we keep for each cached access /// that we have for an instruction. The pointer is an owning pointer and /// the bool indicates whether we have any dirty bits in the set. - typedef PointerIntPair PerInstNLInfo; + typedef std::pair PerInstNLInfo; // A map from instructions to their non-local dependencies. typedef DenseMap NonLocalDepMapType; @@ -162,9 +167,7 @@ namespace llvm { /// Clean up memory in between runs void releaseMemory() { LocalDeps.clear(); - for (NonLocalDepMapType::iterator I = NonLocalDeps.begin(), - E = NonLocalDeps.end(); I != E; ++I) - delete I->second.getPointer(); + NonLocalDeps.clear(); NonLocalDeps.clear(); ReverseLocalDeps.clear(); ReverseNonLocalDeps.clear(); @@ -194,11 +197,14 @@ namespace llvm { /// potentially live across. The returned set of results will include a /// "NonLocal" result for all blocks where the value is live across. /// - /// This method assumes the instruction returns a "nonlocal" dependency + /// This method assumes the instruction returns a "NonLocal" dependency /// within its own block. - void getNonLocalDependency(Instruction *QueryInst, - SmallVectorImpl > &Result); + /// + /// This returns a reference to an internal data structure that may be + /// invalidated on the next non-local query or when an instruction is + /// removed. Clients must copy this data if they want it around longer than + /// that. + const NonLocalDepInfo &getNonLocalDependency(Instruction *QueryInst); /// removeInstruction - Remove an instruction from the dependence analysis, /// updating the dependence of instructions that previously depended on it. -- cgit v1.1