1 //===- llvm/Analysis/LoopDependenceAnalysis.h --------------- -*- C++ -*---===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // LoopDependenceAnalysis is an LLVM pass that analyses dependences in memory 11 // accesses in loops. 12 // 13 // Please note that this is work in progress and the interface is subject to 14 // change. 15 // 16 // TODO: adapt as interface progresses 17 // 18 //===----------------------------------------------------------------------===// 19 20 #ifndef LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H 21 #define LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H 22 23 #include "llvm/ADT/DenseSet.h" 24 #include "llvm/ADT/FoldingSet.h" 25 #include "llvm/ADT/SmallVector.h" 26 #include "llvm/Analysis/LoopPass.h" 27 #include "llvm/Support/Allocator.h" 28 29 namespace llvm { 30 31 class AliasAnalysis; 32 class AnalysisUsage; 33 class ScalarEvolution; 34 class SCEV; 35 class Value; 36 class raw_ostream; 37 38 class LoopDependenceAnalysis : public LoopPass { 39 AliasAnalysis *AA; 40 ScalarEvolution *SE; 41 42 /// L - The loop we are currently analysing. 43 Loop *L; 44 45 /// TODO: doc 46 enum DependenceResult { Independent = 0, Dependent = 1, Unknown = 2 }; 47 48 /// TODO: doc 49 struct Subscript { 50 /// TODO: Add distance, direction, breaking conditions, ... 51 }; 52 53 /// DependencePair - Represents a data dependence relation between to memory 54 /// reference instructions. 55 struct DependencePair : public FastFoldingSetNode { 56 Value *A; 57 Value *B; 58 DependenceResult Result; 59 SmallVector<Subscript, 4> Subscripts; 60 DependencePairDependencePair61 DependencePair(const FoldingSetNodeID &ID, Value *a, Value *b) : 62 FastFoldingSetNode(ID), A(a), B(b), Result(Unknown), Subscripts() {} 63 }; 64 65 /// findOrInsertDependencePair - Return true if a DependencePair for the 66 /// given Values already exists, false if a new DependencePair had to be 67 /// created. The third argument is set to the pair found or created. 68 bool findOrInsertDependencePair(Value*, Value*, DependencePair*&); 69 70 /// getLoops - Collect all loops of the loop nest L in which 71 /// a given SCEV is variant. 72 void getLoops(const SCEV*, DenseSet<const Loop*>*) const; 73 74 /// isLoopInvariant - True if a given SCEV is invariant in all loops of the 75 /// loop nest starting at the innermost loop L. 76 bool isLoopInvariant(const SCEV*) const; 77 78 /// isAffine - An SCEV is affine with respect to the loop nest starting at 79 /// the innermost loop L if it is of the form A+B*X where A, B are invariant 80 /// in the loop nest and X is a induction variable in the loop nest. 81 bool isAffine(const SCEV*) const; 82 83 /// TODO: doc 84 bool isZIVPair(const SCEV*, const SCEV*) const; 85 bool isSIVPair(const SCEV*, const SCEV*) const; 86 DependenceResult analyseZIV(const SCEV*, const SCEV*, Subscript*) const; 87 DependenceResult analyseSIV(const SCEV*, const SCEV*, Subscript*) const; 88 DependenceResult analyseMIV(const SCEV*, const SCEV*, Subscript*) const; 89 DependenceResult analyseSubscript(const SCEV*, const SCEV*, Subscript*) const; 90 DependenceResult analysePair(DependencePair*) const; 91 92 public: 93 static char ID; // Class identification, replacement for typeinfo LoopDependenceAnalysis()94 LoopDependenceAnalysis() : LoopPass(ID) { 95 initializeLoopDependenceAnalysisPass(*PassRegistry::getPassRegistry()); 96 } 97 98 /// isDependencePair - Check whether two values can possibly give rise to 99 /// a data dependence: that is the case if both are instructions accessing 100 /// memory and at least one of those accesses is a write. 101 bool isDependencePair(const Value*, const Value*) const; 102 103 /// depends - Return a boolean indicating if there is a data dependence 104 /// between two instructions. 105 bool depends(Value*, Value*); 106 107 bool runOnLoop(Loop*, LPPassManager&); 108 virtual void releaseMemory(); 109 virtual void getAnalysisUsage(AnalysisUsage&) const; 110 void print(raw_ostream&, const Module* = 0) const; 111 112 private: 113 FoldingSet<DependencePair> Pairs; 114 BumpPtrAllocator PairAllocator; 115 }; // class LoopDependenceAnalysis 116 117 // createLoopDependenceAnalysisPass - This creates an instance of the 118 // LoopDependenceAnalysis pass. 119 // 120 LoopPass *createLoopDependenceAnalysisPass(); 121 122 } // namespace llvm 123 124 #endif /* LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H */ 125