X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FDependenceAnalysis.h;h=5290552b41dc989c720d078a4c6b8a395bbc694a;hp=b4327eeb0b1e673bef616105228c965f7d83bb51;hb=74e437e7b1e30e86d453fb2317800b418d0290fd;hpb=e803d05bd87d1181c971fb719fef5638dd44ce99 diff --git a/include/llvm/Analysis/DependenceAnalysis.h b/include/llvm/Analysis/DependenceAnalysis.h index b4327eeb0b1..5290552b41d 100644 --- a/include/llvm/Analysis/DependenceAnalysis.h +++ b/include/llvm/Analysis/DependenceAnalysis.h @@ -18,6 +18,16 @@ // of memory references in a function, returning either NULL, for no dependence, // or a more-or-less detailed description of the dependence between them. // +// This pass exists to support the DependenceGraph pass. There are two separate +// passes because there's a useful separation of concerns. A dependence exists +// if two conditions are met: +// +// 1) Two instructions reference the same memory location, and +// 2) There is a flow of control leading from one instruction to the other. +// +// DependenceAnalysis attacks the first condition; DependenceGraph will attack +// the second (it's not yet ready). +// // Please note that this is work in progress and the interface is subject to // change. // @@ -30,12 +40,13 @@ #ifndef LLVM_ANALYSIS_DEPENDENCEANALYSIS_H #define LLVM_ANALYSIS_DEPENDENCEANALYSIS_H -#include "llvm/Instructions.h" -#include "llvm/Pass.h" #include "llvm/ADT/SmallBitVector.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/IR/Instructions.h" +#include "llvm/Pass.h" namespace llvm { - class AliasAnalysis; class Loop; class LoopInfo; class ScalarEvolution; @@ -51,11 +62,29 @@ namespace llvm { /// cases (for output, flow, and anti dependences), the dependence implies /// an ordering, where the source must precede the destination; in contrast, /// input dependences are unordered. + /// + /// When a dependence graph is built, each Dependence will be a member of + /// the set of predecessor edges for its destination instruction and a set + /// if successor edges for its source instruction. These sets are represented + /// as singly-linked lists, with the "next" fields stored in the dependence + /// itelf. class Dependence { + protected: + Dependence(const Dependence &) = default; + + // FIXME: When we move to MSVC 2015 as the base compiler for Visual Studio + // support, uncomment this line to allow a defaulted move constructor for + // Dependence. Currently, FullDependence relies on the copy constructor, but + // that is acceptable given the triviality of the class. + // Dependence(Dependence &&) = default; + public: - Dependence(const Instruction *Source, - const Instruction *Destination) : - Src(Source), Dst(Destination) {} + Dependence(Instruction *Source, + Instruction *Destination) : + Src(Source), + Dst(Destination), + NextPredecessor(nullptr), + NextSuccessor(nullptr) {} virtual ~Dependence() {} /// Dependence::DVEntry - Each level in the distance/direction vector @@ -77,16 +106,16 @@ namespace llvm { bool Splitable : 1; // Splitting the loop will break dependence. const SCEV *Distance; // NULL implies no distance available. DVEntry() : Direction(ALL), Scalar(true), PeelFirst(false), - PeelLast(false), Splitable(false), Distance(NULL) { } + PeelLast(false), Splitable(false), Distance(nullptr) { } }; /// getSrc - Returns the source instruction for this dependence. /// - const Instruction *getSrc() const { return Src; } + Instruction *getSrc() const { return Src; } /// getDst - Returns the destination instruction for this dependence. /// - const Instruction *getDst() const { return Dst; } + Instruction *getDst() const { return Dst; } /// isInput - Returns true if this is an input dependence. /// @@ -135,7 +164,7 @@ namespace llvm { /// getDistance - Returns the distance (or NULL) associated with a /// particular level. - virtual const SCEV *getDistance(unsigned Level) const { return NULL; } + virtual const SCEV *getDistance(unsigned Level) const { return nullptr; } /// isPeelFirst - Returns true if peeling the first iteration from /// this loop will break this dependence. @@ -154,88 +183,106 @@ namespace llvm { /// variable associated with the loop at this level. virtual bool isScalar(unsigned Level) const; + /// getNextPredecessor - Returns the value of the NextPredecessor + /// field. + const Dependence *getNextPredecessor() const { return NextPredecessor; } + + /// getNextSuccessor - Returns the value of the NextSuccessor + /// field. + const Dependence *getNextSuccessor() const { return NextSuccessor; } + + /// setNextPredecessor - Sets the value of the NextPredecessor + /// field. + void setNextPredecessor(const Dependence *pred) { NextPredecessor = pred; } + + /// setNextSuccessor - Sets the value of the NextSuccessor + /// field. + void setNextSuccessor(const Dependence *succ) { NextSuccessor = succ; } + /// dump - For debugging purposes, dumps a dependence to OS. /// void dump(raw_ostream &OS) const; + private: - const Instruction *Src, *Dst; + Instruction *Src, *Dst; + const Dependence *NextPredecessor, *NextSuccessor; friend class DependenceAnalysis; }; - /// FullDependence - This class represents a dependence between two memory /// references in a function. It contains detailed information about the - /// dependence (direction vectors, etc) and is used when the compiler is + /// dependence (direction vectors, etc.) and is used when the compiler is /// able to accurately analyze the interaction of the references; that is, /// it is not a confused dependence (see Dependence). In most cases /// (for output, flow, and anti dependences), the dependence implies an /// ordering, where the source must precede the destination; in contrast, /// input dependences are unordered. - class FullDependence : public Dependence { + class FullDependence final : public Dependence { public: - FullDependence(const Instruction *Src, - const Instruction *Dst, - bool LoopIndependent, + FullDependence(Instruction *Src, Instruction *Dst, bool LoopIndependent, unsigned Levels); - ~FullDependence() { - delete DV; - } + + FullDependence(FullDependence &&RHS) + : Dependence(std::move(RHS)), Levels(RHS.Levels), + LoopIndependent(RHS.LoopIndependent), Consistent(RHS.Consistent), + DV(std::move(RHS.DV)) {} /// isLoopIndependent - Returns true if this is a loop-independent /// dependence. - bool isLoopIndependent() const { return LoopIndependent; } + bool isLoopIndependent() const override { return LoopIndependent; } /// isConfused - Returns true if this dependence is confused /// (the compiler understands nothing and makes worst-case /// assumptions). - bool isConfused() const { return false; } + bool isConfused() const override { return false; } /// isConsistent - Returns true if this dependence is consistent /// (occurs every time the source and destination are executed). - bool isConsistent() const { return Consistent; } + bool isConsistent() const override { return Consistent; } /// getLevels - Returns the number of common loops surrounding the /// source and destination of the dependence. - unsigned getLevels() const { return Levels; } + unsigned getLevels() const override { return Levels; } /// getDirection - Returns the direction associated with a particular /// level. - unsigned getDirection(unsigned Level) const; + unsigned getDirection(unsigned Level) const override; /// getDistance - Returns the distance (or NULL) associated with a /// particular level. - const SCEV *getDistance(unsigned Level) const; + const SCEV *getDistance(unsigned Level) const override; /// isPeelFirst - Returns true if peeling the first iteration from /// this loop will break this dependence. - bool isPeelFirst(unsigned Level) const; + bool isPeelFirst(unsigned Level) const override; /// isPeelLast - Returns true if peeling the last iteration from /// this loop will break this dependence. - bool isPeelLast(unsigned Level) const; + bool isPeelLast(unsigned Level) const override; /// isSplitable - Returns true if splitting the loop will break /// the dependence. - bool isSplitable(unsigned Level) const; + bool isSplitable(unsigned Level) const override; /// isScalar - Returns true if a particular level is scalar; that is, /// if no subscript in the source or destination mention the induction /// variable associated with the loop at this level. - bool isScalar(unsigned Level) const; + bool isScalar(unsigned Level) const override; + private: unsigned short Levels; bool LoopIndependent; bool Consistent; // Init to true, then refine. - DVEntry *DV; + std::unique_ptr DV; friend class DependenceAnalysis; }; - /// DependenceAnalysis - This class is the main dependence-analysis driver. /// class DependenceAnalysis : public FunctionPass { - void operator=(const DependenceAnalysis &); // do not implement - DependenceAnalysis(const DependenceAnalysis &); // do not implement + void operator=(const DependenceAnalysis &) = delete; + DependenceAnalysis(const DependenceAnalysis &) = delete; + public: /// depends - Tests for a dependence between the Src and Dst instructions. /// Returns NULL if no dependence; otherwise, returns a Dependence (or a @@ -243,11 +290,11 @@ namespace llvm { /// The flag PossiblyLoopIndependent should be set by the caller /// if it appears that control flow can reach from Src to Dst /// without traversing a loop back edge. - Dependence *depends(const Instruction *Src, - const Instruction *Dst, - bool PossiblyLoopIndependent); + std::unique_ptr depends(Instruction *Src, + Instruction *Dst, + bool PossiblyLoopIndependent); - /// getSplitIteration - Give a dependence that's splitable at some + /// getSplitIteration - Give a dependence that's splittable at some /// particular level, return the iteration that should be used to split /// the loop. /// @@ -287,7 +334,7 @@ namespace llvm { /// /// breaks the dependence and allows us to vectorize/parallelize /// both loops. - const SCEV *getSplitIteration(const Dependence *Dep, unsigned Level); + const SCEV *getSplitIteration(const Dependence &Dep, unsigned Level); private: AliasAnalysis *AA; @@ -345,6 +392,7 @@ namespace llvm { const SCEV *B; const SCEV *C; const Loop *AssociatedLoop; + public: /// isEmpty - Return true if the constraint is of kind Empty. bool isEmpty() const { return Kind == Empty; } @@ -411,7 +459,6 @@ namespace llvm { void dump(raw_ostream &OS) const; }; - /// establishNestingLevels - Examines the loop nesting of the Src and Dst /// instructions and establishes their shared loops. Sets the variables /// CommonLevels, SrcLevels, and MaxLevels. @@ -479,6 +526,12 @@ namespace llvm { /// in LoopNest. bool isLoopInvariant(const SCEV *Expression, const Loop *LoopNest) const; + /// Makes sure all subscript pairs share the same integer type by + /// sign-extending as necessary. + /// Sign-extending a subscript is safe because getelementptr assumes the + /// array subscripts are signed. + void unifySubscriptType(ArrayRef Pairs); + /// removeMatchingExtensions - Examines a subscript pair. /// If the source and destination are identically sign (or zero) /// extended, it strips off the extension in an effort to @@ -758,7 +811,6 @@ namespace llvm { const SCEV *Delta) const; /// testBounds - Returns true iff the current bounds are plausible. - /// bool testBounds(unsigned char DirKind, unsigned Level, BoundInfo *Bound, @@ -805,7 +857,7 @@ namespace llvm { bool propagate(const SCEV *&Src, const SCEV *&Dst, SmallBitVector &Loops, - SmallVector &Constraints, + SmallVectorImpl &Constraints, bool &Consistent); /// propagateDistance - Attempt to propagate a distance @@ -864,16 +916,20 @@ namespace llvm { /// based on the current constraint. void updateDirection(Dependence::DVEntry &Level, const Constraint &CurConstraint) const; + + bool tryDelinearize(Instruction *Src, Instruction *Dst, + SmallVectorImpl &Pair); + public: static char ID; // Class identification, replacement for typeinfo DependenceAnalysis() : FunctionPass(ID) { initializeDependenceAnalysisPass(*PassRegistry::getPassRegistry()); } - bool runOnFunction(Function &F); - void releaseMemory(); - void getAnalysisUsage(AnalysisUsage &) const; - void print(raw_ostream &, const Module * = 0) const; + bool runOnFunction(Function &F) override; + void releaseMemory() override; + void getAnalysisUsage(AnalysisUsage &) const override; + void print(raw_ostream &, const Module * = nullptr) const override; }; // class DependenceAnalysis /// createDependenceAnalysisPass - This creates an instance of the