LLVM API Documentation

LoopDependenceAnalysis.h

Go to the documentation of this file.
00001 //===- llvm/Analysis/LoopDependenceAnalysis.h --------------- -*- C++ -*---===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // LoopDependenceAnalysis is an LLVM pass that analyses dependences in memory
00011 // accesses in loops.
00012 //
00013 // Please note that this is work in progress and the interface is subject to
00014 // change.
00015 //
00016 // TODO: adapt as interface progresses
00017 //
00018 //===----------------------------------------------------------------------===//
00019 
00020 #ifndef LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H
00021 #define LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H
00022 
00023 #include "llvm/ADT/DenseSet.h"
00024 #include "llvm/ADT/FoldingSet.h"
00025 #include "llvm/ADT/SmallVector.h"
00026 #include "llvm/Analysis/LoopPass.h"
00027 #include "llvm/Support/Allocator.h"
00028 #include <iosfwd>
00029 
00030 namespace llvm {
00031 
00032 class AliasAnalysis;
00033 class AnalysisUsage;
00034 class ScalarEvolution;
00035 class SCEV;
00036 class Value;
00037 class raw_ostream;
00038 
00039 class LoopDependenceAnalysis : public LoopPass {
00040   AliasAnalysis *AA;
00041   ScalarEvolution *SE;
00042 
00043   /// L - The loop we are currently analysing.
00044   Loop *L;
00045 
00046   /// TODO: doc
00047   enum DependenceResult { Independent = 0, Dependent = 1, Unknown = 2 };
00048 
00049   /// TODO: doc
00050   struct Subscript {
00051     /// TODO: Add distance, direction, breaking conditions, ...
00052   };
00053 
00054   /// DependencePair - Represents a data dependence relation between to memory
00055   /// reference instructions.
00056   struct DependencePair : public FastFoldingSetNode {
00057     Value *A;
00058     Value *B;
00059     DependenceResult Result;
00060     SmallVector<Subscript, 4> Subscripts;
00061 
00062     DependencePair(const FoldingSetNodeID &ID, Value *a, Value *b) :
00063         FastFoldingSetNode(ID), A(a), B(b), Result(Unknown), Subscripts() {}
00064   };
00065 
00066   /// findOrInsertDependencePair - Return true if a DependencePair for the
00067   /// given Values already exists, false if a new DependencePair had to be
00068   /// created. The third argument is set to the pair found or created.
00069   bool findOrInsertDependencePair(Value*, Value*, DependencePair*&);
00070 
00071   /// getLoops - Collect all loops of the loop-nest L a given SCEV is variant
00072   /// in.
00073   void getLoops(const SCEV*, DenseSet<const Loop*>*) const;
00074 
00075   /// isLoopInvariant - True if a given SCEV is invariant in all loops of the
00076   /// loop-nest starting at the innermost loop L.
00077   bool isLoopInvariant(const SCEV*) const;
00078 
00079   /// isAffine - An SCEV is affine with respect to the loop-nest starting at
00080   /// the innermost loop L if it is of the form A+B*X where A, B are invariant
00081   /// in the loop-nest and X is a induction variable in the loop-nest.
00082   bool isAffine(const SCEV*) const;
00083 
00084   /// TODO: doc
00085   bool isZIVPair(const SCEV*, const SCEV*) const;
00086   bool isSIVPair(const SCEV*, const SCEV*) const;
00087   DependenceResult analyseZIV(const SCEV*, const SCEV*, Subscript*) const;
00088   DependenceResult analyseSIV(const SCEV*, const SCEV*, Subscript*) const;
00089   DependenceResult analyseMIV(const SCEV*, const SCEV*, Subscript*) const;
00090   DependenceResult analyseSubscript(const SCEV*, const SCEV*, Subscript*) const;
00091   DependenceResult analysePair(DependencePair*) const;
00092 
00093 public:
00094   static char ID; // Class identification, replacement for typeinfo
00095   LoopDependenceAnalysis() : LoopPass(&ID) {}
00096 
00097   /// isDependencePair - Check wether two values can possibly give rise to a
00098   /// data dependence: that is the case if both are instructions accessing
00099   /// memory and at least one of those accesses is a write.
00100   bool isDependencePair(const Value*, const Value*) const;
00101 
00102   /// depends - Return a boolean indicating if there is a data dependence
00103   /// between two instructions.
00104   bool depends(Value*, Value*);
00105 
00106   bool runOnLoop(Loop*, LPPassManager&);
00107   virtual void releaseMemory();
00108   virtual void getAnalysisUsage(AnalysisUsage&) const;
00109   void print(raw_ostream&, const Module* = 0) const;
00110   virtual void print(std::ostream&, const Module* = 0) const;
00111 
00112 private:
00113   FoldingSet<DependencePair> Pairs;
00114   BumpPtrAllocator PairAllocator;
00115 }; // class LoopDependenceAnalysis
00116 
00117 // createLoopDependenceAnalysisPass - This creates an instance of the
00118 // LoopDependenceAnalysis pass.
00119 //
00120 LoopPass *createLoopDependenceAnalysisPass();
00121 
00122 } // namespace llvm
00123 
00124 #endif /* LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H */