LLVM API Documentation
00001 //===- llvm/Analysis/LoopDependenceAnalysis.h --------------- -*- C++ -*---===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // LoopDependenceAnalysis is an LLVM pass that analyses dependences in memory 00011 // accesses in loops. 00012 // 00013 // Please note that this is work in progress and the interface is subject to 00014 // change. 00015 // 00016 // TODO: adapt as interface progresses 00017 // 00018 //===----------------------------------------------------------------------===// 00019 00020 #ifndef LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H 00021 #define LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H 00022 00023 #include "llvm/ADT/DenseSet.h" 00024 #include "llvm/ADT/FoldingSet.h" 00025 #include "llvm/ADT/SmallVector.h" 00026 #include "llvm/Analysis/LoopPass.h" 00027 #include "llvm/Support/Allocator.h" 00028 #include <iosfwd> 00029 00030 namespace llvm { 00031 00032 class AliasAnalysis; 00033 class AnalysisUsage; 00034 class ScalarEvolution; 00035 class SCEV; 00036 class Value; 00037 class raw_ostream; 00038 00039 class LoopDependenceAnalysis : public LoopPass { 00040 AliasAnalysis *AA; 00041 ScalarEvolution *SE; 00042 00043 /// L - The loop we are currently analysing. 00044 Loop *L; 00045 00046 /// TODO: doc 00047 enum DependenceResult { Independent = 0, Dependent = 1, Unknown = 2 }; 00048 00049 /// TODO: doc 00050 struct Subscript { 00051 /// TODO: Add distance, direction, breaking conditions, ... 00052 }; 00053 00054 /// DependencePair - Represents a data dependence relation between to memory 00055 /// reference instructions. 00056 struct DependencePair : public FastFoldingSetNode { 00057 Value *A; 00058 Value *B; 00059 DependenceResult Result; 00060 SmallVector<Subscript, 4> Subscripts; 00061 00062 DependencePair(const FoldingSetNodeID &ID, Value *a, Value *b) : 00063 FastFoldingSetNode(ID), A(a), B(b), Result(Unknown), Subscripts() {} 00064 }; 00065 00066 /// findOrInsertDependencePair - Return true if a DependencePair for the 00067 /// given Values already exists, false if a new DependencePair had to be 00068 /// created. The third argument is set to the pair found or created. 00069 bool findOrInsertDependencePair(Value*, Value*, DependencePair*&); 00070 00071 /// getLoops - Collect all loops of the loop-nest L a given SCEV is variant 00072 /// in. 00073 void getLoops(const SCEV*, DenseSet<const Loop*>*) const; 00074 00075 /// isLoopInvariant - True if a given SCEV is invariant in all loops of the 00076 /// loop-nest starting at the innermost loop L. 00077 bool isLoopInvariant(const SCEV*) const; 00078 00079 /// isAffine - An SCEV is affine with respect to the loop-nest starting at 00080 /// the innermost loop L if it is of the form A+B*X where A, B are invariant 00081 /// in the loop-nest and X is a induction variable in the loop-nest. 00082 bool isAffine(const SCEV*) const; 00083 00084 /// TODO: doc 00085 bool isZIVPair(const SCEV*, const SCEV*) const; 00086 bool isSIVPair(const SCEV*, const SCEV*) const; 00087 DependenceResult analyseZIV(const SCEV*, const SCEV*, Subscript*) const; 00088 DependenceResult analyseSIV(const SCEV*, const SCEV*, Subscript*) const; 00089 DependenceResult analyseMIV(const SCEV*, const SCEV*, Subscript*) const; 00090 DependenceResult analyseSubscript(const SCEV*, const SCEV*, Subscript*) const; 00091 DependenceResult analysePair(DependencePair*) const; 00092 00093 public: 00094 static char ID; // Class identification, replacement for typeinfo 00095 LoopDependenceAnalysis() : LoopPass(&ID) {} 00096 00097 /// isDependencePair - Check wether two values can possibly give rise to a 00098 /// data dependence: that is the case if both are instructions accessing 00099 /// memory and at least one of those accesses is a write. 00100 bool isDependencePair(const Value*, const Value*) const; 00101 00102 /// depends - Return a boolean indicating if there is a data dependence 00103 /// between two instructions. 00104 bool depends(Value*, Value*); 00105 00106 bool runOnLoop(Loop*, LPPassManager&); 00107 virtual void releaseMemory(); 00108 virtual void getAnalysisUsage(AnalysisUsage&) const; 00109 void print(raw_ostream&, const Module* = 0) const; 00110 virtual void print(std::ostream&, const Module* = 0) const; 00111 00112 private: 00113 FoldingSet<DependencePair> Pairs; 00114 BumpPtrAllocator PairAllocator; 00115 }; // class LoopDependenceAnalysis 00116 00117 // createLoopDependenceAnalysisPass - This creates an instance of the 00118 // LoopDependenceAnalysis pass. 00119 // 00120 LoopPass *createLoopDependenceAnalysisPass(); 00121 00122 } // namespace llvm 00123 00124 #endif /* LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H */