Fix DFS number calculation for postdominators

[oota-llvm.git] / include / llvm / Analysis / LoopDependenceAnalysis.h

diff --git a/include/llvm/Analysis/LoopDependenceAnalysis.h b/include/llvm/Analysis/LoopDependenceAnalysis.h
index 67da2e7fbc1b1d3a9dbafba12125897f7de6945c..a1a563796f5a0ad8f91248acab31f603f90c5f7a 100644 (file)
--- a/include/llvm/Analysis/LoopDependenceAnalysis.h
+++ b/include/llvm/Analysis/LoopDependenceAnalysis.h
@@ -20,43 +20,102 @@
 #ifndef LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H
 #define LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H
 
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/FoldingSet.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/LoopPass.h"
-#include "llvm/Support/raw_ostream.h"
-#include <iosfwd>
+#include "llvm/Support/Allocator.h"
 
 namespace llvm {
 
-  class AliasAnalysis;
-  class AnalysisUsage;
-  class ScalarEvolution;
-  class Value;
+class AliasAnalysis;
+class AnalysisUsage;
+class ScalarEvolution;
+class SCEV;
+class Value;
+class raw_ostream;
 
-  class LoopDependenceAnalysis : public LoopPass {
-    Loop *L;
-    AliasAnalysis *AA;
-    ScalarEvolution *SE;
+class LoopDependenceAnalysis : public LoopPass {
+  AliasAnalysis *AA;
+  ScalarEvolution *SE;
 
-  public:
-    static char ID; // Class identification, replacement for typeinfo
-    LoopDependenceAnalysis() : LoopPass(&ID) {}
+  /// L - The loop we are currently analysing.
+  Loop *L;
 
-    /// TODO: docs
-    bool isDependencePair(const Value*, const Value*) const;
-    bool depends(Value*, Value*);
+  /// TODO: doc
+  enum DependenceResult { Independent = 0, Dependent = 1, Unknown = 2 };
 
-    bool runOnLoop(Loop*, LPPassManager&);
+  /// TODO: doc
+  struct Subscript {
+    /// TODO: Add distance, direction, breaking conditions, ...
+  };
 
-    virtual void getAnalysisUsage(AnalysisUsage&) const;
+  /// DependencePair - Represents a data dependence relation between to memory
+  /// reference instructions.
+  struct DependencePair : public FastFoldingSetNode {
+    Value *A;
+    Value *B;
+    DependenceResult Result;
+    SmallVector<Subscript, 4> Subscripts;
 
-    void print(raw_ostream&, const Module* = 0) const;
-    virtual void print(std::ostream&, const Module* = 0) const;
-  }; // class LoopDependenceAnalysis
+    DependencePair(const FoldingSetNodeID &ID, Value *a, Value *b) :
+        FastFoldingSetNode(ID), A(a), B(b), Result(Unknown), Subscripts() {}
+  };
 
+  /// 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*&);
 
-  // createLoopDependenceAnalysisPass - This creates an instance of the
-  // LoopDependenceAnalysis pass.
-  //
-  LoopPass *createLoopDependenceAnalysisPass();
+  /// getLoops - Collect all loops of the loop nest L in which
+  /// a given SCEV is variant.
+  void getLoops(const SCEV*, DenseSet<const Loop*>*) const;
+
+  /// isLoopInvariant - True if a given SCEV is invariant in all loops of the
+  /// loop nest starting at the innermost loop L.
+  bool isLoopInvariant(const SCEV*) const;
+
+  /// isAffine - An SCEV is affine with respect to the loop nest starting at
+  /// the innermost loop L if it is of the form A+B*X where A, B are invariant
+  /// in the loop nest and X is a induction variable in the loop nest.
+  bool isAffine(const SCEV*) const;
+
+  /// TODO: doc
+  bool isZIVPair(const SCEV*, const SCEV*) const;
+  bool isSIVPair(const SCEV*, const SCEV*) const;
+  DependenceResult analyseZIV(const SCEV*, const SCEV*, Subscript*) const;
+  DependenceResult analyseSIV(const SCEV*, const SCEV*, Subscript*) const;
+  DependenceResult analyseMIV(const SCEV*, const SCEV*, Subscript*) const;
+  DependenceResult analyseSubscript(const SCEV*, const SCEV*, Subscript*) const;
+  DependenceResult analysePair(DependencePair*) const;
+
+public:
+  static char ID; // Class identification, replacement for typeinfo
+  LoopDependenceAnalysis() : LoopPass(&ID) {}
+
+  /// isDependencePair - Check whether 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;
+
+private:
+  FoldingSet<DependencePair> Pairs;
+  BumpPtrAllocator PairAllocator;
+}; // class LoopDependenceAnalysis
+
+// createLoopDependenceAnalysisPass - This creates an instance of the
+// LoopDependenceAnalysis pass.
+//
+LoopPass *createLoopDependenceAnalysisPass();
 
 } // namespace llvm