From c8cd3f69598dfb0db97de4a9337534e52b32dd2d Mon Sep 17 00:00:00 2001 From: Andreas Bolka Date: Thu, 23 Jul 2009 14:32:46 +0000 Subject: [PATCH] Cache dependence computation using FoldingSet. This introduces an LDA-internal DependencePair class. The intention is, that this is a place where dependence testers can store various results such as SCEVs describing conflicting iterations, breaking conditions, distance/direction vectors, etc. llvm-svn: 76877 --- .../include/llvm/Analysis/LoopDependenceAnalysis.h | 44 ++++++++++- llvm/lib/Analysis/LoopDependenceAnalysis.cpp | 88 ++++++++++++++++------ 2 files changed, 105 insertions(+), 27 deletions(-) diff --git a/llvm/include/llvm/Analysis/LoopDependenceAnalysis.h b/llvm/include/llvm/Analysis/LoopDependenceAnalysis.h index 42e434e..17bbf8b 100644 --- a/llvm/include/llvm/Analysis/LoopDependenceAnalysis.h +++ b/llvm/include/llvm/Analysis/LoopDependenceAnalysis.h @@ -20,7 +20,9 @@ #ifndef LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H #define LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H +#include "llvm/ADT/FoldingSet.h" #include "llvm/Analysis/LoopPass.h" +#include "llvm/Support/Allocator.h" #include "llvm/Support/raw_ostream.h" #include @@ -32,24 +34,58 @@ class ScalarEvolution; class Value; class LoopDependenceAnalysis : public LoopPass { - Loop *L; AliasAnalysis *AA; ScalarEvolution *SE; + /// L - The loop we are currently analysing. + Loop *L; + + /// TODO: doc + enum DependenceResult { Independent = 0, Dependent = 1, Unknown = 2 }; + + /// DependencePair - Represents a data dependence relation between to memory + /// reference instructions. + /// + /// TODO: add subscripts vector + struct DependencePair : public FastFoldingSetNode { + Value *A; + Value *B; + DependenceResult Result; + + DependencePair(const FoldingSetNodeID &ID, Value *a, Value *b) : + FastFoldingSetNode(ID), A(a), B(b), Result(Unknown) {} + }; + + /// findOrInsertDependencePair - Return true if a DependencePair for the + /// given Values already exists, false if a new DependencePair had to be + /// created. The third argument is set to the pair found or created. + bool findOrInsertDependencePair(Value*, Value*, DependencePair*&); + + /// TODO: doc + void analysePair(DependencePair *P) const; + public: static char ID; // Class identification, replacement for typeinfo LoopDependenceAnalysis() : LoopPass(&ID) {} - /// TODO: docs + /// isDependencePair - Check wether two values can possibly give rise to a + /// data dependence: that is the case if both are instructions accessing + /// memory and at least one of those accesses is a write. bool isDependencePair(const Value*, const Value*) const; + + /// depends - Return a boolean indicating if there is a data dependence + /// between two instructions. bool depends(Value*, Value*); bool runOnLoop(Loop*, LPPassManager&); - + virtual void releaseMemory(); virtual void getAnalysisUsage(AnalysisUsage&) const; - void print(raw_ostream&, const Module* = 0) const; virtual void print(std::ostream&, const Module* = 0) const; + +private: + FoldingSet Pairs; + BumpPtrAllocator PairAllocator; }; // class LoopDependenceAnalysis diff --git a/llvm/lib/Analysis/LoopDependenceAnalysis.cpp b/llvm/lib/Analysis/LoopDependenceAnalysis.cpp index cef11e1..13d449f 100644 --- a/llvm/lib/Analysis/LoopDependenceAnalysis.cpp +++ b/llvm/lib/Analysis/LoopDependenceAnalysis.cpp @@ -81,36 +81,73 @@ bool LoopDependenceAnalysis::isDependencePair(const Value *A, cast(B)->mayWriteToMemory()); } -bool LoopDependenceAnalysis::depends(Value *Src, Value *Dst) { - assert(isDependencePair(Src, Dst) && "Values form no dependence pair!"); - DOUT << "== LDA test ==\n" << *Src << *Dst; - - // We only analyse loads and stores; for possible memory accesses by e.g. - // free, call, or invoke instructions we conservatively assume dependence. - if (!IsLoadOrStoreInst(Src) || !IsLoadOrStoreInst(Dst)) - return true; - - Value *srcPtr = GetPointerOperand(Src); - Value *dstPtr = GetPointerOperand(Dst); - const Value *srcObj = srcPtr->getUnderlyingObject(); - const Value *dstObj = dstPtr->getUnderlyingObject(); +bool LoopDependenceAnalysis::findOrInsertDependencePair(Value *X, + Value *Y, + DependencePair *&P) { + void *insertPos = 0; + FoldingSetNodeID id; + id.AddPointer(X); + id.AddPointer(Y); + + P = Pairs.FindNodeOrInsertPos(id, insertPos); + if (P) return true; + + P = PairAllocator.Allocate(); + new (P) DependencePair(id, X, Y); + Pairs.InsertNode(P, insertPos); + return false; +} + +void LoopDependenceAnalysis::analysePair(DependencePair *P) const { + DOUT << "Analysing:\n" << *P->A << "\n" << *P->B << "\n"; + + // Our default answer: we don't know anything, i.e. we failed to analyse this + // pair to get a more specific answer (dependent, independent). + P->Result = Unknown; + + // We only analyse loads and stores but no possible memory accesses by e.g. + // free, call, or invoke instructions. + if (!IsLoadOrStoreInst(P->A) || !IsLoadOrStoreInst(P->B)) { + DOUT << "--> [?] no load/store\n"; + return; + } + + Value *aptr = GetPointerOperand(P->A); + Value *bptr = GetPointerOperand(P->B); + const Value *aobj = aptr->getUnderlyingObject(); + const Value *bobj = bptr->getUnderlyingObject(); AliasAnalysis::AliasResult alias = AA->alias( - srcObj, AA->getTargetData().getTypeStoreSize(srcObj->getType()), - dstObj, AA->getTargetData().getTypeStoreSize(dstObj->getType())); + aobj, AA->getTargetData().getTypeStoreSize(aobj->getType()), + bobj, AA->getTargetData().getTypeStoreSize(bobj->getType())); - // If we don't know whether or not the two objects alias, assume dependence. - if (alias == AliasAnalysis::MayAlias) - return true; + // We can not analyse objects if we do not know about their aliasing. + if (alias == AliasAnalysis::MayAlias) { + DOUT << "---> [?] may alias\n"; + return; + } // If the objects noalias, they are distinct, accesses are independent. - if (alias == AliasAnalysis::NoAlias) - return false; + if (alias == AliasAnalysis::NoAlias) { + DOUT << "---> [I] no alias\n"; + P->Result = Independent; + return; + } // TODO: the underlying objects MustAlias, test for dependence - // We couldn't establish a more precise result, so we have to conservatively - // assume full dependence. - return true; + DOUT << "---> [?] cannot analyse\n"; + return; +} + +bool LoopDependenceAnalysis::depends(Value *A, Value *B) { + assert(isDependencePair(A, B) && "Values form no dependence pair!"); + + DependencePair *p; + if (!findOrInsertDependencePair(A, B, p)) { + // The pair is not cached, so analyse it. + analysePair(p); + } + return p->Result != Independent; } //===----------------------------------------------------------------------===// @@ -124,6 +161,11 @@ bool LoopDependenceAnalysis::runOnLoop(Loop *L, LPPassManager &) { return false; } +void LoopDependenceAnalysis::releaseMemory() { + Pairs.clear(); + PairAllocator.Reset(); +} + void LoopDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); AU.addRequiredTransitive(); -- 2.7.4