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/FoldingSet.h"
  24 #include "llvm/Analysis/LoopPass.h"
  25 #include "llvm/Support/Allocator.h"
  26 #include <iosfwd>
  27
  28 namespace llvm {
  29
  30 class AliasAnalysis;
  31 class AnalysisUsage;
  32 class ScalarEvolution;
  33 class Value;
  34 class raw_ostream;
  35
  36 class LoopDependenceAnalysis : public LoopPass {
  37   AliasAnalysis *AA;
  38   ScalarEvolution *SE;
  39
  40   /// L - The loop we are currently analysing.
  41   Loop *L;
  42
  43   /// TODO: doc
  44   enum DependenceResult { Independent = 0, Dependent = 1, Unknown = 2 };
  45
  46   /// DependencePair - Represents a data dependence relation between to memory
  47   /// reference instructions.
  48   ///
  49   /// TODO: add subscripts vector
  50   struct DependencePair : public FastFoldingSetNode {
  51     Value *A;
  52     Value *B;
  53     DependenceResult Result;
  54
  55     DependencePair(const FoldingSetNodeID &ID, Value *a, Value *b) :
  56         FastFoldingSetNode(ID), A(a), B(b), Result(Unknown) {}
  57   };
  58
  59   /// findOrInsertDependencePair - Return true if a DependencePair for the
  60   /// given Values already exists, false if a new DependencePair had to be
  61   /// created. The third argument is set to the pair found or created.
  62   bool findOrInsertDependencePair(Value*, Value*, DependencePair*&);
  63
  64   /// TODO: doc
  65   DependenceResult analysePair(DependencePair *P) const;
  66
  67 public:
  68   static char ID; // Class identification, replacement for typeinfo
  69   LoopDependenceAnalysis() : LoopPass(&ID) {}
  70
  71   /// isDependencePair - Check wether two values can possibly give rise to a
  72   /// data dependence: that is the case if both are instructions accessing
  73   /// memory and at least one of those accesses is a write.
  74   bool isDependencePair(const Value*, const Value*) const;
  75
  76   /// depends - Return a boolean indicating if there is a data dependence
  77   /// between two instructions.
  78   bool depends(Value*, Value*);
  79
  80   bool runOnLoop(Loop*, LPPassManager&);
  81   virtual void releaseMemory();
  82   virtual void getAnalysisUsage(AnalysisUsage&) const;
  83   void print(raw_ostream&, const Module* = 0) const;
  84   virtual void print(std::ostream&, const Module* = 0) const;
  85
  86 private:
  87   FoldingSet<DependencePair> Pairs;
  88   BumpPtrAllocator PairAllocator;
  89 }; // class LoopDependenceAnalysis
  90
  91
  92 // createLoopDependenceAnalysisPass - This creates an instance of the
  93 // LoopDependenceAnalysis pass.
  94 //
  95 LoopPass *createLoopDependenceAnalysisPass();
  96
  97 } // namespace llvm
  98
  99 #endif /* LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H */