include/llvm/Analysis/LoopDependenceAnalysis.h

   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
  61     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
  94   LoopDependenceAnalysis() : LoopPass(ID) {}
  95
  96   /// isDependencePair - Check whether two values can possibly give rise to
  97   /// a data dependence: that is the case if both are instructions accessing
  98   /// memory and at least one of those accesses is a write.
  99   bool isDependencePair(const Value*, const Value*) const;
 100
 101   /// depends - Return a boolean indicating if there is a data dependence
 102   /// between two instructions.
 103   bool depends(Value*, Value*);
 104
 105   bool runOnLoop(Loop*, LPPassManager&);
 106   virtual void releaseMemory();
 107   virtual void getAnalysisUsage(AnalysisUsage&) const;
 108   void print(raw_ostream&, const Module* = 0) const;
 109
 110 private:
 111   FoldingSet<DependencePair> Pairs;
 112   BumpPtrAllocator PairAllocator;
 113 }; // class LoopDependenceAnalysis
 114
 115 // createLoopDependenceAnalysisPass - This creates an instance of the
 116 // LoopDependenceAnalysis pass.
 117 //
 118 LoopPass *createLoopDependenceAnalysisPass();
 119
 120 } // namespace llvm
 121
 122 #endif /* LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H */