1 //===- llvm/Analysis/LoopDependenceAnalysis.h --------------- -*- C++ -*---===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // LoopDependenceAnalysis is an LLVM pass that analyses dependences in memory
13 // Please note that this is work in progress and the interface is subject to
16 // TODO: adapt as interface progresses
18 //===----------------------------------------------------------------------===//
20 #ifndef LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H
21 #define LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H
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"
33 class ScalarEvolution;
38 class LoopDependenceAnalysis : public LoopPass {
42 /// L - The loop we are currently analysing.
46 enum DependenceResult { Independent = 0, Dependent = 1, Unknown = 2 };
50 /// TODO: Add distance, direction, breaking conditions, ...
53 /// DependencePair - Represents a data dependence relation between to memory
54 /// reference instructions.
55 struct DependencePair : public FastFoldingSetNode {
58 DependenceResult Result;
59 SmallVector<Subscript, 4> Subscripts;
61 DependencePair(const FoldingSetNodeID &ID, Value *a, Value *b) :
62 FastFoldingSetNode(ID), A(a), B(b), Result(Unknown), Subscripts() {}
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*&);
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;
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;
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;
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;
93 static char ID; // Class identification, replacement for typeinfo
94 LoopDependenceAnalysis() : LoopPass(ID) {
95 initializeLoopDependenceAnalysisPass(*PassRegistry::getPassRegistry());
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;
103 /// depends - Return a boolean indicating if there is a data dependence
104 /// between two instructions.
105 bool depends(Value*, Value*);
107 bool runOnLoop(Loop*, LPPassManager&);
108 virtual void releaseMemory();
109 virtual void getAnalysisUsage(AnalysisUsage&) const;
110 void print(raw_ostream&, const Module* = 0) const;
113 FoldingSet<DependencePair> Pairs;
114 BumpPtrAllocator PairAllocator;
115 }; // class LoopDependenceAnalysis
117 // createLoopDependenceAnalysisPass - This creates an instance of the
118 // LoopDependenceAnalysis pass.
120 LoopPass *createLoopDependenceAnalysisPass();
124 #endif /* LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H */