Home | History | Annotate | Download | only in Analysis 
      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     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