LCOV - code coverage report
Current view: top level - include/llvm/Analysis - DependenceAnalysis.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 21 28 75.0 %
Date: 2017-09-14 15:23:50 Functions: 13 22 59.1 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===-- llvm/Analysis/DependenceAnalysis.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             : // DependenceAnalysis is an LLVM pass that analyses dependences between memory
      11             : // accesses. Currently, it is an implementation of the approach described in
      12             : //
      13             : //            Practical Dependence Testing
      14             : //            Goff, Kennedy, Tseng
      15             : //            PLDI 1991
      16             : //
      17             : // There's a single entry point that analyzes the dependence between a pair
      18             : // of memory references in a function, returning either NULL, for no dependence,
      19             : // or a more-or-less detailed description of the dependence between them.
      20             : //
      21             : // This pass exists to support the DependenceGraph pass. There are two separate
      22             : // passes because there's a useful separation of concerns. A dependence exists
      23             : // if two conditions are met:
      24             : //
      25             : //    1) Two instructions reference the same memory location, and
      26             : //    2) There is a flow of control leading from one instruction to the other.
      27             : //
      28             : // DependenceAnalysis attacks the first condition; DependenceGraph will attack
      29             : // the second (it's not yet ready).
      30             : //
      31             : // Please note that this is work in progress and the interface is subject to
      32             : // change.
      33             : //
      34             : // Plausible changes:
      35             : //    Return a set of more precise dependences instead of just one dependence
      36             : //    summarizing all.
      37             : //
      38             : //===----------------------------------------------------------------------===//
      39             : 
      40             : #ifndef LLVM_ANALYSIS_DEPENDENCEANALYSIS_H
      41             : #define LLVM_ANALYSIS_DEPENDENCEANALYSIS_H
      42             : 
      43             : #include "llvm/ADT/SmallBitVector.h"
      44             : #include "llvm/Analysis/AliasAnalysis.h"
      45             : #include "llvm/IR/Instructions.h"
      46             : #include "llvm/Pass.h"
      47             : 
      48             : namespace llvm {
      49             : template <typename T> class ArrayRef;
      50             :   class Loop;
      51             :   class LoopInfo;
      52             :   class ScalarEvolution;
      53             :   class SCEV;
      54             :   class SCEVConstant;
      55             :   class raw_ostream;
      56             : 
      57             :   /// Dependence - This class represents a dependence between two memory
      58             :   /// memory references in a function. It contains minimal information and
      59             :   /// is used in the very common situation where the compiler is unable to
      60             :   /// determine anything beyond the existence of a dependence; that is, it
      61             :   /// represents a confused dependence (see also FullDependence). In most
      62             :   /// cases (for output, flow, and anti dependences), the dependence implies
      63             :   /// an ordering, where the source must precede the destination; in contrast,
      64             :   /// input dependences are unordered.
      65             :   ///
      66             :   /// When a dependence graph is built, each Dependence will be a member of
      67             :   /// the set of predecessor edges for its destination instruction and a set
      68             :   /// if successor edges for its source instruction. These sets are represented
      69             :   /// as singly-linked lists, with the "next" fields stored in the dependence
      70             :   /// itelf.
      71             :   class Dependence {
      72             :   protected:
      73         405 :     Dependence(Dependence &&) = default;
      74             :     Dependence &operator=(Dependence &&) = default;
      75             : 
      76             :   public:
      77             :     Dependence(Instruction *Source,
      78        1461 :                Instruction *Destination) :
      79             :       Src(Source),
      80             :       Dst(Destination),
      81             :       NextPredecessor(nullptr),
      82        1461 :       NextSuccessor(nullptr) {}
      83         546 :     virtual ~Dependence() {}
      84             : 
      85             :     /// Dependence::DVEntry - Each level in the distance/direction vector
      86             :     /// has a direction (or perhaps a union of several directions), and
      87             :     /// perhaps a distance.
      88             :     struct DVEntry {
      89             :       enum { NONE = 0,
      90             :              LT = 1,
      91             :              EQ = 2,
      92             :              LE = 3,
      93             :              GT = 4,
      94             :              NE = 5,
      95             :              GE = 6,
      96             :              ALL = 7 };
      97             :       unsigned char Direction : 3; // Init to ALL, then refine.
      98             :       bool Scalar    : 1; // Init to true.
      99             :       bool PeelFirst : 1; // Peeling the first iteration will break dependence.
     100             :       bool PeelLast  : 1; // Peeling the last iteration will break the dependence.
     101             :       bool Splitable : 1; // Splitting the loop will break dependence.
     102             :       const SCEV *Distance; // NULL implies no distance available.
     103        1413 :       DVEntry() : Direction(ALL), Scalar(true), PeelFirst(false),
     104        1413 :                   PeelLast(false), Splitable(false), Distance(nullptr) { }
     105             :     };
     106             : 
     107             :     /// getSrc - Returns the source instruction for this dependence.
     108             :     ///
     109             :     Instruction *getSrc() const { return Src; }
     110             : 
     111             :     /// getDst - Returns the destination instruction for this dependence.
     112             :     ///
     113             :     Instruction *getDst() const { return Dst; }
     114             : 
     115             :     /// isInput - Returns true if this is an input dependence.
     116             :     ///
     117             :     bool isInput() const;
     118             : 
     119             :     /// isOutput - Returns true if this is an output dependence.
     120             :     ///
     121             :     bool isOutput() const;
     122             : 
     123             :     /// isFlow - Returns true if this is a flow (aka true) dependence.
     124             :     ///
     125             :     bool isFlow() const;
     126             : 
     127             :     /// isAnti - Returns true if this is an anti dependence.
     128             :     ///
     129             :     bool isAnti() const;
     130             : 
     131             :     /// isOrdered - Returns true if dependence is Output, Flow, or Anti
     132             :     ///
     133             :     bool isOrdered() const { return isOutput() || isFlow() || isAnti(); }
     134             : 
     135             :     /// isUnordered - Returns true if dependence is Input
     136             :     ///
     137             :     bool isUnordered() const { return isInput(); }
     138             : 
     139             :     /// isLoopIndependent - Returns true if this is a loop-independent
     140             :     /// dependence.
     141           0 :     virtual bool isLoopIndependent() const { return true; }
     142             : 
     143             :     /// isConfused - Returns true if this dependence is confused
     144             :     /// (the compiler understands nothing and makes worst-case
     145             :     /// assumptions).
     146         546 :     virtual bool isConfused() const { return true; }
     147             : 
     148             :     /// isConsistent - Returns true if this dependence is consistent
     149             :     /// (occurs every time the source and destination are executed).
     150           0 :     virtual bool isConsistent() const { return false; }
     151             : 
     152             :     /// getLevels - Returns the number of common loops surrounding the
     153             :     /// source and destination of the dependence.
     154         546 :     virtual unsigned getLevels() const { return 0; }
     155             : 
     156             :     /// getDirection - Returns the direction associated with a particular
     157             :     /// level.
     158           0 :     virtual unsigned getDirection(unsigned Level) const { return DVEntry::ALL; }
     159             : 
     160             :     /// getDistance - Returns the distance (or NULL) associated with a
     161             :     /// particular level.
     162           0 :     virtual const SCEV *getDistance(unsigned Level) const { return nullptr; }
     163             : 
     164             :     /// isPeelFirst - Returns true if peeling the first iteration from
     165             :     /// this loop will break this dependence.
     166           0 :     virtual bool isPeelFirst(unsigned Level) const { return false; }
     167             : 
     168             :     /// isPeelLast - Returns true if peeling the last iteration from
     169             :     /// this loop will break this dependence.
     170           0 :     virtual bool isPeelLast(unsigned Level) const { return false; }
     171             : 
     172             :     /// isSplitable - Returns true if splitting this loop will break
     173             :     /// the dependence.
     174           0 :     virtual bool isSplitable(unsigned Level) const { return false; }
     175             : 
     176             :     /// isScalar - Returns true if a particular level is scalar; that is,
     177             :     /// if no subscript in the source or destination mention the induction
     178             :     /// variable associated with the loop at this level.
     179             :     virtual bool isScalar(unsigned Level) const;
     180             : 
     181             :     /// getNextPredecessor - Returns the value of the NextPredecessor
     182             :     /// field.
     183             :     const Dependence *getNextPredecessor() const { return NextPredecessor; }
     184             : 
     185             :     /// getNextSuccessor - Returns the value of the NextSuccessor
     186             :     /// field.
     187             :     const Dependence *getNextSuccessor() const { return NextSuccessor; }
     188             : 
     189             :     /// setNextPredecessor - Sets the value of the NextPredecessor
     190             :     /// field.
     191             :     void setNextPredecessor(const Dependence *pred) { NextPredecessor = pred; }
     192             : 
     193             :     /// setNextSuccessor - Sets the value of the NextSuccessor
     194             :     /// field.
     195             :     void setNextSuccessor(const Dependence *succ) { NextSuccessor = succ; }
     196             : 
     197             :     /// dump - For debugging purposes, dumps a dependence to OS.
     198             :     ///
     199             :     void dump(raw_ostream &OS) const;
     200             : 
     201             :   private:
     202             :     Instruction *Src, *Dst;
     203             :     const Dependence *NextPredecessor, *NextSuccessor;
     204             :     friend class DependenceInfo;
     205             :   };
     206             : 
     207             :   /// FullDependence - This class represents a dependence between two memory
     208             :   /// references in a function. It contains detailed information about the
     209             :   /// dependence (direction vectors, etc.) and is used when the compiler is
     210             :   /// able to accurately analyze the interaction of the references; that is,
     211             :   /// it is not a confused dependence (see Dependence). In most cases
     212             :   /// (for output, flow, and anti dependences), the dependence implies an
     213             :   /// ordering, where the source must precede the destination; in contrast,
     214             :   /// input dependences are unordered.
     215        3855 :   class FullDependence final : public Dependence {
     216             :   public:
     217             :     FullDependence(Instruction *Src, Instruction *Dst, bool LoopIndependent,
     218             :                    unsigned Levels);
     219             : 
     220             :     /// isLoopIndependent - Returns true if this is a loop-independent
     221             :     /// dependence.
     222         376 :     bool isLoopIndependent() const override { return LoopIndependent; }
     223             : 
     224             :     /// isConfused - Returns true if this dependence is confused
     225             :     /// (the compiler understands nothing and makes worst-case
     226             :     /// assumptions).
     227         376 :     bool isConfused() const override { return false; }
     228             : 
     229             :     /// isConsistent - Returns true if this dependence is consistent
     230             :     /// (occurs every time the source and destination are executed).
     231         376 :     bool isConsistent() const override { return Consistent; }
     232             : 
     233             :     /// getLevels - Returns the number of common loops surrounding the
     234             :     /// source and destination of the dependence.
     235        1495 :     unsigned getLevels() const override { return Levels; }
     236             : 
     237             :     /// getDirection - Returns the direction associated with a particular
     238             :     /// level.
     239             :     unsigned getDirection(unsigned Level) const override;
     240             : 
     241             :     /// getDistance - Returns the distance (or NULL) associated with a
     242             :     /// particular level.
     243             :     const SCEV *getDistance(unsigned Level) const override;
     244             : 
     245             :     /// isPeelFirst - Returns true if peeling the first iteration from
     246             :     /// this loop will break this dependence.
     247             :     bool isPeelFirst(unsigned Level) const override;
     248             : 
     249             :     /// isPeelLast - Returns true if peeling the last iteration from
     250             :     /// this loop will break this dependence.
     251             :     bool isPeelLast(unsigned Level) const override;
     252             : 
     253             :     /// isSplitable - Returns true if splitting the loop will break
     254             :     /// the dependence.
     255             :     bool isSplitable(unsigned Level) const override;
     256             : 
     257             :     /// isScalar - Returns true if a particular level is scalar; that is,
     258             :     /// if no subscript in the source or destination mention the induction
     259             :     /// variable associated with the loop at this level.
     260             :     bool isScalar(unsigned Level) const override;
     261             : 
     262             :   private:
     263             :     unsigned short Levels;
     264             :     bool LoopIndependent;
     265             :     bool Consistent; // Init to true, then refine.
     266             :     std::unique_ptr<DVEntry[]> DV;
     267             :     friend class DependenceInfo;
     268             :   };
     269             : 
     270             :   /// DependenceInfo - This class is the main dependence-analysis driver.
     271             :   ///
     272             :   class DependenceInfo {
     273             :   public:
     274             :     DependenceInfo(Function *F, AliasAnalysis *AA, ScalarEvolution *SE,
     275             :                    LoopInfo *LI)
     276         208 :         : AA(AA), SE(SE), LI(LI), F(F) {}
     277             : 
     278             :     /// depends - Tests for a dependence between the Src and Dst instructions.
     279             :     /// Returns NULL if no dependence; otherwise, returns a Dependence (or a
     280             :     /// FullDependence) with as much information as can be gleaned.
     281             :     /// The flag PossiblyLoopIndependent should be set by the caller
     282             :     /// if it appears that control flow can reach from Src to Dst
     283             :     /// without traversing a loop back edge.
     284             :     std::unique_ptr<Dependence> depends(Instruction *Src,
     285             :                                         Instruction *Dst,
     286             :                                         bool PossiblyLoopIndependent);
     287             : 
     288             :     /// getSplitIteration - Give a dependence that's splittable at some
     289             :     /// particular level, return the iteration that should be used to split
     290             :     /// the loop.
     291             :     ///
     292             :     /// Generally, the dependence analyzer will be used to build
     293             :     /// a dependence graph for a function (basically a map from instructions
     294             :     /// to dependences). Looking for cycles in the graph shows us loops
     295             :     /// that cannot be trivially vectorized/parallelized.
     296             :     ///
     297             :     /// We can try to improve the situation by examining all the dependences
     298             :     /// that make up the cycle, looking for ones we can break.
     299             :     /// Sometimes, peeling the first or last iteration of a loop will break
     300             :     /// dependences, and there are flags for those possibilities.
     301             :     /// Sometimes, splitting a loop at some other iteration will do the trick,
     302             :     /// and we've got a flag for that case. Rather than waste the space to
     303             :     /// record the exact iteration (since we rarely know), we provide
     304             :     /// a method that calculates the iteration. It's a drag that it must work
     305             :     /// from scratch, but wonderful in that it's possible.
     306             :     ///
     307             :     /// Here's an example:
     308             :     ///
     309             :     ///    for (i = 0; i < 10; i++)
     310             :     ///        A[i] = ...
     311             :     ///        ... = A[11 - i]
     312             :     ///
     313             :     /// There's a loop-carried flow dependence from the store to the load,
     314             :     /// found by the weak-crossing SIV test. The dependence will have a flag,
     315             :     /// indicating that the dependence can be broken by splitting the loop.
     316             :     /// Calling getSplitIteration will return 5.
     317             :     /// Splitting the loop breaks the dependence, like so:
     318             :     ///
     319             :     ///    for (i = 0; i <= 5; i++)
     320             :     ///        A[i] = ...
     321             :     ///        ... = A[11 - i]
     322             :     ///    for (i = 6; i < 10; i++)
     323             :     ///        A[i] = ...
     324             :     ///        ... = A[11 - i]
     325             :     ///
     326             :     /// breaks the dependence and allows us to vectorize/parallelize
     327             :     /// both loops.
     328             :     const SCEV *getSplitIteration(const Dependence &Dep, unsigned Level);
     329             : 
     330             :     Function *getFunction() const { return F; }
     331             : 
     332             :   private:
     333             :     AliasAnalysis *AA;
     334             :     ScalarEvolution *SE;
     335             :     LoopInfo *LI;
     336             :     Function *F;
     337             : 
     338             :     /// Subscript - This private struct represents a pair of subscripts from
     339             :     /// a pair of potentially multi-dimensional array references. We use a
     340             :     /// vector of them to guide subscript partitioning.
     341        7044 :     struct Subscript {
     342             :       const SCEV *Src;
     343             :       const SCEV *Dst;
     344             :       enum ClassificationKind { ZIV, SIV, RDIV, MIV, NonLinear } Classification;
     345             :       SmallBitVector Loops;
     346             :       SmallBitVector GroupLoops;
     347             :       SmallBitVector Group;
     348             :     };
     349             : 
     350             :     struct CoefficientInfo {
     351             :       const SCEV *Coeff;
     352             :       const SCEV *PosPart;
     353             :       const SCEV *NegPart;
     354             :       const SCEV *Iterations;
     355             :     };
     356             : 
     357             :     struct BoundInfo {
     358             :       const SCEV *Iterations;
     359             :       const SCEV *Upper[8];
     360             :       const SCEV *Lower[8];
     361             :       unsigned char Direction;
     362             :       unsigned char DirSet;
     363             :     };
     364             : 
     365             :     /// Constraint - This private class represents a constraint, as defined
     366             :     /// in the paper
     367             :     ///
     368             :     ///           Practical Dependence Testing
     369             :     ///           Goff, Kennedy, Tseng
     370             :     ///           PLDI 1991
     371             :     ///
     372             :     /// There are 5 kinds of constraint, in a hierarchy.
     373             :     ///   1) Any - indicates no constraint, any dependence is possible.
     374             :     ///   2) Line - A line ax + by = c, where a, b, and c are parameters,
     375             :     ///             representing the dependence equation.
     376             :     ///   3) Distance - The value d of the dependence distance;
     377             :     ///   4) Point - A point <x, y> representing the dependence from
     378             :     ///              iteration x to iteration y.
     379             :     ///   5) Empty - No dependence is possible.
     380             :     class Constraint {
     381             :     private:
     382             :       enum ConstraintKind { Empty, Point, Distance, Line, Any } Kind;
     383             :       ScalarEvolution *SE;
     384             :       const SCEV *A;
     385             :       const SCEV *B;
     386             :       const SCEV *C;
     387             :       const Loop *AssociatedLoop;
     388             : 
     389             :     public:
     390             :       /// isEmpty - Return true if the constraint is of kind Empty.
     391             :       bool isEmpty() const { return Kind == Empty; }
     392             : 
     393             :       /// isPoint - Return true if the constraint is of kind Point.
     394             :       bool isPoint() const { return Kind == Point; }
     395             : 
     396             :       /// isDistance - Return true if the constraint is of kind Distance.
     397             :       bool isDistance() const { return Kind == Distance; }
     398             : 
     399             :       /// isLine - Return true if the constraint is of kind Line.
     400             :       /// Since Distance's can also be represented as Lines, we also return
     401             :       /// true if the constraint is of kind Distance.
     402         153 :       bool isLine() const { return Kind == Line || Kind == Distance; }
     403             : 
     404             :       /// isAny - Return true if the constraint is of kind Any;
     405             :       bool isAny() const { return Kind == Any; }
     406             : 
     407             :       /// getX - If constraint is a point <X, Y>, returns X.
     408             :       /// Otherwise assert.
     409             :       const SCEV *getX() const;
     410             : 
     411             :       /// getY - If constraint is a point <X, Y>, returns Y.
     412             :       /// Otherwise assert.
     413             :       const SCEV *getY() const;
     414             : 
     415             :       /// getA - If constraint is a line AX + BY = C, returns A.
     416             :       /// Otherwise assert.
     417             :       const SCEV *getA() const;
     418             : 
     419             :       /// getB - If constraint is a line AX + BY = C, returns B.
     420             :       /// Otherwise assert.
     421             :       const SCEV *getB() const;
     422             : 
     423             :       /// getC - If constraint is a line AX + BY = C, returns C.
     424             :       /// Otherwise assert.
     425             :       const SCEV *getC() const;
     426             : 
     427             :       /// getD - If constraint is a distance, returns D.
     428             :       /// Otherwise assert.
     429             :       const SCEV *getD() const;
     430             : 
     431             :       /// getAssociatedLoop - Returns the loop associated with this constraint.
     432             :       const Loop *getAssociatedLoop() const;
     433             : 
     434             :       /// setPoint - Change a constraint to Point.
     435             :       void setPoint(const SCEV *X, const SCEV *Y, const Loop *CurrentLoop);
     436             : 
     437             :       /// setLine - Change a constraint to Line.
     438             :       void setLine(const SCEV *A, const SCEV *B,
     439             :                    const SCEV *C, const Loop *CurrentLoop);
     440             : 
     441             :       /// setDistance - Change a constraint to Distance.
     442             :       void setDistance(const SCEV *D, const Loop *CurrentLoop);
     443             : 
     444             :       /// setEmpty - Change a constraint to Empty.
     445             :       void setEmpty();
     446             : 
     447             :       /// setAny - Change a constraint to Any.
     448             :       void setAny(ScalarEvolution *SE);
     449             : 
     450             :       /// dump - For debugging purposes. Dumps the constraint
     451             :       /// out to OS.
     452             :       void dump(raw_ostream &OS) const;
     453             :     };
     454             : 
     455             :     /// establishNestingLevels - Examines the loop nesting of the Src and Dst
     456             :     /// instructions and establishes their shared loops. Sets the variables
     457             :     /// CommonLevels, SrcLevels, and MaxLevels.
     458             :     /// The source and destination instructions needn't be contained in the same
     459             :     /// loop. The routine establishNestingLevels finds the level of most deeply
     460             :     /// nested loop that contains them both, CommonLevels. An instruction that's
     461             :     /// not contained in a loop is at level = 0. MaxLevels is equal to the level
     462             :     /// of the source plus the level of the destination, minus CommonLevels.
     463             :     /// This lets us allocate vectors MaxLevels in length, with room for every
     464             :     /// distinct loop referenced in both the source and destination subscripts.
     465             :     /// The variable SrcLevels is the nesting depth of the source instruction.
     466             :     /// It's used to help calculate distinct loops referenced by the destination.
     467             :     /// Here's the map from loops to levels:
     468             :     ///            0 - unused
     469             :     ///            1 - outermost common loop
     470             :     ///          ... - other common loops
     471             :     /// CommonLevels - innermost common loop
     472             :     ///          ... - loops containing Src but not Dst
     473             :     ///    SrcLevels - innermost loop containing Src but not Dst
     474             :     ///          ... - loops containing Dst but not Src
     475             :     ///    MaxLevels - innermost loop containing Dst but not Src
     476             :     /// Consider the follow code fragment:
     477             :     ///    for (a = ...) {
     478             :     ///      for (b = ...) {
     479             :     ///        for (c = ...) {
     480             :     ///          for (d = ...) {
     481             :     ///            A[] = ...;
     482             :     ///          }
     483             :     ///        }
     484             :     ///        for (e = ...) {
     485             :     ///          for (f = ...) {
     486             :     ///            for (g = ...) {
     487             :     ///              ... = A[];
     488             :     ///            }
     489             :     ///          }
     490             :     ///        }
     491             :     ///      }
     492             :     ///    }
     493             :     /// If we're looking at the possibility of a dependence between the store
     494             :     /// to A (the Src) and the load from A (the Dst), we'll note that they
     495             :     /// have 2 loops in common, so CommonLevels will equal 2 and the direction
     496             :     /// vector for Result will have 2 entries. SrcLevels = 4 and MaxLevels = 7.
     497             :     /// A map from loop names to level indices would look like
     498             :     ///     a - 1
     499             :     ///     b - 2 = CommonLevels
     500             :     ///     c - 3
     501             :     ///     d - 4 = SrcLevels
     502             :     ///     e - 5
     503             :     ///     f - 6
     504             :     ///     g - 7 = MaxLevels
     505             :     void establishNestingLevels(const Instruction *Src,
     506             :                                 const Instruction *Dst);
     507             : 
     508             :     unsigned CommonLevels, SrcLevels, MaxLevels;
     509             : 
     510             :     /// mapSrcLoop - Given one of the loops containing the source, return
     511             :     /// its level index in our numbering scheme.
     512             :     unsigned mapSrcLoop(const Loop *SrcLoop) const;
     513             : 
     514             :     /// mapDstLoop - Given one of the loops containing the destination,
     515             :     /// return its level index in our numbering scheme.
     516             :     unsigned mapDstLoop(const Loop *DstLoop) const;
     517             : 
     518             :     /// isLoopInvariant - Returns true if Expression is loop invariant
     519             :     /// in LoopNest.
     520             :     bool isLoopInvariant(const SCEV *Expression, const Loop *LoopNest) const;
     521             : 
     522             :     /// Makes sure all subscript pairs share the same integer type by
     523             :     /// sign-extending as necessary.
     524             :     /// Sign-extending a subscript is safe because getelementptr assumes the
     525             :     /// array subscripts are signed.
     526             :     void unifySubscriptType(ArrayRef<Subscript *> Pairs);
     527             : 
     528             :     /// removeMatchingExtensions - Examines a subscript pair.
     529             :     /// If the source and destination are identically sign (or zero)
     530             :     /// extended, it strips off the extension in an effort to
     531             :     /// simplify the actual analysis.
     532             :     void removeMatchingExtensions(Subscript *Pair);
     533             : 
     534             :     /// collectCommonLoops - Finds the set of loops from the LoopNest that
     535             :     /// have a level <= CommonLevels and are referred to by the SCEV Expression.
     536             :     void collectCommonLoops(const SCEV *Expression,
     537             :                             const Loop *LoopNest,
     538             :                             SmallBitVector &Loops) const;
     539             : 
     540             :     /// checkSrcSubscript - Examines the SCEV Src, returning true iff it's
     541             :     /// linear. Collect the set of loops mentioned by Src.
     542             :     bool checkSrcSubscript(const SCEV *Src,
     543             :                            const Loop *LoopNest,
     544             :                            SmallBitVector &Loops);
     545             : 
     546             :     /// checkDstSubscript - Examines the SCEV Dst, returning true iff it's
     547             :     /// linear. Collect the set of loops mentioned by Dst.
     548             :     bool checkDstSubscript(const SCEV *Dst,
     549             :                            const Loop *LoopNest,
     550             :                            SmallBitVector &Loops);
     551             : 
     552             :     /// isKnownPredicate - Compare X and Y using the predicate Pred.
     553             :     /// Basically a wrapper for SCEV::isKnownPredicate,
     554             :     /// but tries harder, especially in the presence of sign and zero
     555             :     /// extensions and symbolics.
     556             :     bool isKnownPredicate(ICmpInst::Predicate Pred,
     557             :                           const SCEV *X,
     558             :                           const SCEV *Y) const;
     559             : 
     560             :     /// collectUpperBound - All subscripts are the same type (on my machine,
     561             :     /// an i64). The loop bound may be a smaller type. collectUpperBound
     562             :     /// find the bound, if available, and zero extends it to the Type T.
     563             :     /// (I zero extend since the bound should always be >= 0.)
     564             :     /// If no upper bound is available, return NULL.
     565             :     const SCEV *collectUpperBound(const Loop *l, Type *T) const;
     566             : 
     567             :     /// collectConstantUpperBound - Calls collectUpperBound(), then
     568             :     /// attempts to cast it to SCEVConstant. If the cast fails,
     569             :     /// returns NULL.
     570             :     const SCEVConstant *collectConstantUpperBound(const Loop *l, Type *T) const;
     571             : 
     572             :     /// classifyPair - Examines the subscript pair (the Src and Dst SCEVs)
     573             :     /// and classifies it as either ZIV, SIV, RDIV, MIV, or Nonlinear.
     574             :     /// Collects the associated loops in a set.
     575             :     Subscript::ClassificationKind classifyPair(const SCEV *Src,
     576             :                                            const Loop *SrcLoopNest,
     577             :                                            const SCEV *Dst,
     578             :                                            const Loop *DstLoopNest,
     579             :                                            SmallBitVector &Loops);
     580             : 
     581             :     /// testZIV - Tests the ZIV subscript pair (Src and Dst) for dependence.
     582             :     /// Returns true if any possible dependence is disproved.
     583             :     /// If there might be a dependence, returns false.
     584             :     /// If the dependence isn't proven to exist,
     585             :     /// marks the Result as inconsistent.
     586             :     bool testZIV(const SCEV *Src,
     587             :                  const SCEV *Dst,
     588             :                  FullDependence &Result) const;
     589             : 
     590             :     /// testSIV - Tests the SIV subscript pair (Src and Dst) for dependence.
     591             :     /// Things of the form [c1 + a1*i] and [c2 + a2*j], where
     592             :     /// i and j are induction variables, c1 and c2 are loop invariant,
     593             :     /// and a1 and a2 are constant.
     594             :     /// Returns true if any possible dependence is disproved.
     595             :     /// If there might be a dependence, returns false.
     596             :     /// Sets appropriate direction vector entry and, when possible,
     597             :     /// the distance vector entry.
     598             :     /// If the dependence isn't proven to exist,
     599             :     /// marks the Result as inconsistent.
     600             :     bool testSIV(const SCEV *Src,
     601             :                  const SCEV *Dst,
     602             :                  unsigned &Level,
     603             :                  FullDependence &Result,
     604             :                  Constraint &NewConstraint,
     605             :                  const SCEV *&SplitIter) const;
     606             : 
     607             :     /// testRDIV - Tests the RDIV subscript pair (Src and Dst) for dependence.
     608             :     /// Things of the form [c1 + a1*i] and [c2 + a2*j]
     609             :     /// where i and j are induction variables, c1 and c2 are loop invariant,
     610             :     /// and a1 and a2 are constant.
     611             :     /// With minor algebra, this test can also be used for things like
     612             :     /// [c1 + a1*i + a2*j][c2].
     613             :     /// Returns true if any possible dependence is disproved.
     614             :     /// If there might be a dependence, returns false.
     615             :     /// Marks the Result as inconsistent.
     616             :     bool testRDIV(const SCEV *Src,
     617             :                   const SCEV *Dst,
     618             :                   FullDependence &Result) const;
     619             : 
     620             :     /// testMIV - Tests the MIV subscript pair (Src and Dst) for dependence.
     621             :     /// Returns true if dependence disproved.
     622             :     /// Can sometimes refine direction vectors.
     623             :     bool testMIV(const SCEV *Src,
     624             :                  const SCEV *Dst,
     625             :                  const SmallBitVector &Loops,
     626             :                  FullDependence &Result) const;
     627             : 
     628             :     /// strongSIVtest - Tests the strong SIV subscript pair (Src and Dst)
     629             :     /// for dependence.
     630             :     /// Things of the form [c1 + a*i] and [c2 + a*i],
     631             :     /// where i is an induction variable, c1 and c2 are loop invariant,
     632             :     /// and a is a constant
     633             :     /// Returns true if any possible dependence is disproved.
     634             :     /// If there might be a dependence, returns false.
     635             :     /// Sets appropriate direction and distance.
     636             :     bool strongSIVtest(const SCEV *Coeff,
     637             :                        const SCEV *SrcConst,
     638             :                        const SCEV *DstConst,
     639             :                        const Loop *CurrentLoop,
     640             :                        unsigned Level,
     641             :                        FullDependence &Result,
     642             :                        Constraint &NewConstraint) const;
     643             : 
     644             :     /// weakCrossingSIVtest - Tests the weak-crossing SIV subscript pair
     645             :     /// (Src and Dst) for dependence.
     646             :     /// Things of the form [c1 + a*i] and [c2 - a*i],
     647             :     /// where i is an induction variable, c1 and c2 are loop invariant,
     648             :     /// and a is a constant.
     649             :     /// Returns true if any possible dependence is disproved.
     650             :     /// If there might be a dependence, returns false.
     651             :     /// Sets appropriate direction entry.
     652             :     /// Set consistent to false.
     653             :     /// Marks the dependence as splitable.
     654             :     bool weakCrossingSIVtest(const SCEV *SrcCoeff,
     655             :                              const SCEV *SrcConst,
     656             :                              const SCEV *DstConst,
     657             :                              const Loop *CurrentLoop,
     658             :                              unsigned Level,
     659             :                              FullDependence &Result,
     660             :                              Constraint &NewConstraint,
     661             :                              const SCEV *&SplitIter) const;
     662             : 
     663             :     /// ExactSIVtest - Tests the SIV subscript pair
     664             :     /// (Src and Dst) for dependence.
     665             :     /// Things of the form [c1 + a1*i] and [c2 + a2*i],
     666             :     /// where i is an induction variable, c1 and c2 are loop invariant,
     667             :     /// and a1 and a2 are constant.
     668             :     /// Returns true if any possible dependence is disproved.
     669             :     /// If there might be a dependence, returns false.
     670             :     /// Sets appropriate direction entry.
     671             :     /// Set consistent to false.
     672             :     bool exactSIVtest(const SCEV *SrcCoeff,
     673             :                       const SCEV *DstCoeff,
     674             :                       const SCEV *SrcConst,
     675             :                       const SCEV *DstConst,
     676             :                       const Loop *CurrentLoop,
     677             :                       unsigned Level,
     678             :                       FullDependence &Result,
     679             :                       Constraint &NewConstraint) const;
     680             : 
     681             :     /// weakZeroSrcSIVtest - Tests the weak-zero SIV subscript pair
     682             :     /// (Src and Dst) for dependence.
     683             :     /// Things of the form [c1] and [c2 + a*i],
     684             :     /// where i is an induction variable, c1 and c2 are loop invariant,
     685             :     /// and a is a constant. See also weakZeroDstSIVtest.
     686             :     /// Returns true if any possible dependence is disproved.
     687             :     /// If there might be a dependence, returns false.
     688             :     /// Sets appropriate direction entry.
     689             :     /// Set consistent to false.
     690             :     /// If loop peeling will break the dependence, mark appropriately.
     691             :     bool weakZeroSrcSIVtest(const SCEV *DstCoeff,
     692             :                             const SCEV *SrcConst,
     693             :                             const SCEV *DstConst,
     694             :                             const Loop *CurrentLoop,
     695             :                             unsigned Level,
     696             :                             FullDependence &Result,
     697             :                             Constraint &NewConstraint) const;
     698             : 
     699             :     /// weakZeroDstSIVtest - Tests the weak-zero SIV subscript pair
     700             :     /// (Src and Dst) for dependence.
     701             :     /// Things of the form [c1 + a*i] and [c2],
     702             :     /// where i is an induction variable, c1 and c2 are loop invariant,
     703             :     /// and a is a constant. See also weakZeroSrcSIVtest.
     704             :     /// Returns true if any possible dependence is disproved.
     705             :     /// If there might be a dependence, returns false.
     706             :     /// Sets appropriate direction entry.
     707             :     /// Set consistent to false.
     708             :     /// If loop peeling will break the dependence, mark appropriately.
     709             :     bool weakZeroDstSIVtest(const SCEV *SrcCoeff,
     710             :                             const SCEV *SrcConst,
     711             :                             const SCEV *DstConst,
     712             :                             const Loop *CurrentLoop,
     713             :                             unsigned Level,
     714             :                             FullDependence &Result,
     715             :                             Constraint &NewConstraint) const;
     716             : 
     717             :     /// exactRDIVtest - Tests the RDIV subscript pair for dependence.
     718             :     /// Things of the form [c1 + a*i] and [c2 + b*j],
     719             :     /// where i and j are induction variable, c1 and c2 are loop invariant,
     720             :     /// and a and b are constants.
     721             :     /// Returns true if any possible dependence is disproved.
     722             :     /// Marks the result as inconsistent.
     723             :     /// Works in some cases that symbolicRDIVtest doesn't,
     724             :     /// and vice versa.
     725             :     bool exactRDIVtest(const SCEV *SrcCoeff,
     726             :                        const SCEV *DstCoeff,
     727             :                        const SCEV *SrcConst,
     728             :                        const SCEV *DstConst,
     729             :                        const Loop *SrcLoop,
     730             :                        const Loop *DstLoop,
     731             :                        FullDependence &Result) const;
     732             : 
     733             :     /// symbolicRDIVtest - Tests the RDIV subscript pair for dependence.
     734             :     /// Things of the form [c1 + a*i] and [c2 + b*j],
     735             :     /// where i and j are induction variable, c1 and c2 are loop invariant,
     736             :     /// and a and b are constants.
     737             :     /// Returns true if any possible dependence is disproved.
     738             :     /// Marks the result as inconsistent.
     739             :     /// Works in some cases that exactRDIVtest doesn't,
     740             :     /// and vice versa. Can also be used as a backup for
     741             :     /// ordinary SIV tests.
     742             :     bool symbolicRDIVtest(const SCEV *SrcCoeff,
     743             :                           const SCEV *DstCoeff,
     744             :                           const SCEV *SrcConst,
     745             :                           const SCEV *DstConst,
     746             :                           const Loop *SrcLoop,
     747             :                           const Loop *DstLoop) const;
     748             : 
     749             :     /// gcdMIVtest - Tests an MIV subscript pair for dependence.
     750             :     /// Returns true if any possible dependence is disproved.
     751             :     /// Marks the result as inconsistent.
     752             :     /// Can sometimes disprove the equal direction for 1 or more loops.
     753             :     //  Can handle some symbolics that even the SIV tests don't get,
     754             :     /// so we use it as a backup for everything.
     755             :     bool gcdMIVtest(const SCEV *Src,
     756             :                     const SCEV *Dst,
     757             :                     FullDependence &Result) const;
     758             : 
     759             :     /// banerjeeMIVtest - Tests an MIV subscript pair for dependence.
     760             :     /// Returns true if any possible dependence is disproved.
     761             :     /// Marks the result as inconsistent.
     762             :     /// Computes directions.
     763             :     bool banerjeeMIVtest(const SCEV *Src,
     764             :                          const SCEV *Dst,
     765             :                          const SmallBitVector &Loops,
     766             :                          FullDependence &Result) const;
     767             : 
     768             :     /// collectCoefficientInfo - Walks through the subscript,
     769             :     /// collecting each coefficient, the associated loop bounds,
     770             :     /// and recording its positive and negative parts for later use.
     771             :     CoefficientInfo *collectCoeffInfo(const SCEV *Subscript,
     772             :                                       bool SrcFlag,
     773             :                                       const SCEV *&Constant) const;
     774             : 
     775             :     /// getPositivePart - X^+ = max(X, 0).
     776             :     ///
     777             :     const SCEV *getPositivePart(const SCEV *X) const;
     778             : 
     779             :     /// getNegativePart - X^- = min(X, 0).
     780             :     ///
     781             :     const SCEV *getNegativePart(const SCEV *X) const;
     782             : 
     783             :     /// getLowerBound - Looks through all the bounds info and
     784             :     /// computes the lower bound given the current direction settings
     785             :     /// at each level.
     786             :     const SCEV *getLowerBound(BoundInfo *Bound) const;
     787             : 
     788             :     /// getUpperBound - Looks through all the bounds info and
     789             :     /// computes the upper bound given the current direction settings
     790             :     /// at each level.
     791             :     const SCEV *getUpperBound(BoundInfo *Bound) const;
     792             : 
     793             :     /// exploreDirections - Hierarchically expands the direction vector
     794             :     /// search space, combining the directions of discovered dependences
     795             :     /// in the DirSet field of Bound. Returns the number of distinct
     796             :     /// dependences discovered. If the dependence is disproved,
     797             :     /// it will return 0.
     798             :     unsigned exploreDirections(unsigned Level,
     799             :                                CoefficientInfo *A,
     800             :                                CoefficientInfo *B,
     801             :                                BoundInfo *Bound,
     802             :                                const SmallBitVector &Loops,
     803             :                                unsigned &DepthExpanded,
     804             :                                const SCEV *Delta) const;
     805             : 
     806             :     /// testBounds - Returns true iff the current bounds are plausible.
     807             :     bool testBounds(unsigned char DirKind,
     808             :                     unsigned Level,
     809             :                     BoundInfo *Bound,
     810             :                     const SCEV *Delta) const;
     811             : 
     812             :     /// findBoundsALL - Computes the upper and lower bounds for level K
     813             :     /// using the * direction. Records them in Bound.
     814             :     void findBoundsALL(CoefficientInfo *A,
     815             :                        CoefficientInfo *B,
     816             :                        BoundInfo *Bound,
     817             :                        unsigned K) const;
     818             : 
     819             :     /// findBoundsLT - Computes the upper and lower bounds for level K
     820             :     /// using the < direction. Records them in Bound.
     821             :     void findBoundsLT(CoefficientInfo *A,
     822             :                       CoefficientInfo *B,
     823             :                       BoundInfo *Bound,
     824             :                       unsigned K) const;
     825             : 
     826             :     /// findBoundsGT - Computes the upper and lower bounds for level K
     827             :     /// using the > direction. Records them in Bound.
     828             :     void findBoundsGT(CoefficientInfo *A,
     829             :                       CoefficientInfo *B,
     830             :                       BoundInfo *Bound,
     831             :                       unsigned K) const;
     832             : 
     833             :     /// findBoundsEQ - Computes the upper and lower bounds for level K
     834             :     /// using the = direction. Records them in Bound.
     835             :     void findBoundsEQ(CoefficientInfo *A,
     836             :                       CoefficientInfo *B,
     837             :                       BoundInfo *Bound,
     838             :                       unsigned K) const;
     839             : 
     840             :     /// intersectConstraints - Updates X with the intersection
     841             :     /// of the Constraints X and Y. Returns true if X has changed.
     842             :     bool intersectConstraints(Constraint *X,
     843             :                               const Constraint *Y);
     844             : 
     845             :     /// propagate - Review the constraints, looking for opportunities
     846             :     /// to simplify a subscript pair (Src and Dst).
     847             :     /// Return true if some simplification occurs.
     848             :     /// If the simplification isn't exact (that is, if it is conservative
     849             :     /// in terms of dependence), set consistent to false.
     850             :     bool propagate(const SCEV *&Src,
     851             :                    const SCEV *&Dst,
     852             :                    SmallBitVector &Loops,
     853             :                    SmallVectorImpl<Constraint> &Constraints,
     854             :                    bool &Consistent);
     855             : 
     856             :     /// propagateDistance - Attempt to propagate a distance
     857             :     /// constraint into a subscript pair (Src and Dst).
     858             :     /// Return true if some simplification occurs.
     859             :     /// If the simplification isn't exact (that is, if it is conservative
     860             :     /// in terms of dependence), set consistent to false.
     861             :     bool propagateDistance(const SCEV *&Src,
     862             :                            const SCEV *&Dst,
     863             :                            Constraint &CurConstraint,
     864             :                            bool &Consistent);
     865             : 
     866             :     /// propagatePoint - Attempt to propagate a point
     867             :     /// constraint into a subscript pair (Src and Dst).
     868             :     /// Return true if some simplification occurs.
     869             :     bool propagatePoint(const SCEV *&Src,
     870             :                         const SCEV *&Dst,
     871             :                         Constraint &CurConstraint);
     872             : 
     873             :     /// propagateLine - Attempt to propagate a line
     874             :     /// constraint into a subscript pair (Src and Dst).
     875             :     /// Return true if some simplification occurs.
     876             :     /// If the simplification isn't exact (that is, if it is conservative
     877             :     /// in terms of dependence), set consistent to false.
     878             :     bool propagateLine(const SCEV *&Src,
     879             :                        const SCEV *&Dst,
     880             :                        Constraint &CurConstraint,
     881             :                        bool &Consistent);
     882             : 
     883             :     /// findCoefficient - Given a linear SCEV,
     884             :     /// return the coefficient corresponding to specified loop.
     885             :     /// If there isn't one, return the SCEV constant 0.
     886             :     /// For example, given a*i + b*j + c*k, returning the coefficient
     887             :     /// corresponding to the j loop would yield b.
     888             :     const SCEV *findCoefficient(const SCEV *Expr,
     889             :                                 const Loop *TargetLoop) const;
     890             : 
     891             :     /// zeroCoefficient - Given a linear SCEV,
     892             :     /// return the SCEV given by zeroing out the coefficient
     893             :     /// corresponding to the specified loop.
     894             :     /// For example, given a*i + b*j + c*k, zeroing the coefficient
     895             :     /// corresponding to the j loop would yield a*i + c*k.
     896             :     const SCEV *zeroCoefficient(const SCEV *Expr,
     897             :                                 const Loop *TargetLoop) const;
     898             : 
     899             :     /// addToCoefficient - Given a linear SCEV Expr,
     900             :     /// return the SCEV given by adding some Value to the
     901             :     /// coefficient corresponding to the specified TargetLoop.
     902             :     /// For example, given a*i + b*j + c*k, adding 1 to the coefficient
     903             :     /// corresponding to the j loop would yield a*i + (b+1)*j + c*k.
     904             :     const SCEV *addToCoefficient(const SCEV *Expr,
     905             :                                  const Loop *TargetLoop,
     906             :                                  const SCEV *Value)  const;
     907             : 
     908             :     /// updateDirection - Update direction vector entry
     909             :     /// based on the current constraint.
     910             :     void updateDirection(Dependence::DVEntry &Level,
     911             :                          const Constraint &CurConstraint) const;
     912             : 
     913             :     bool tryDelinearize(Instruction *Src, Instruction *Dst,
     914             :                         SmallVectorImpl<Subscript> &Pair);
     915             :   }; // class DependenceInfo
     916             : 
     917             :   /// \brief AnalysisPass to compute dependence information in a function
     918             :   class DependenceAnalysis : public AnalysisInfoMixin<DependenceAnalysis> {
     919             :   public:
     920             :     typedef DependenceInfo Result;
     921             :     Result run(Function &F, FunctionAnalysisManager &FAM);
     922             : 
     923             :   private:
     924             :     static AnalysisKey Key;
     925             :     friend struct AnalysisInfoMixin<DependenceAnalysis>;
     926             :   }; // class DependenceAnalysis
     927             : 
     928             :   /// \brief Legacy pass manager pass to access dependence information
     929         172 :   class DependenceAnalysisWrapperPass : public FunctionPass {
     930             :   public:
     931             :     static char ID; // Class identification, replacement for typeinfo
     932         129 :     DependenceAnalysisWrapperPass() : FunctionPass(ID) {
     933          43 :       initializeDependenceAnalysisWrapperPassPass(
     934          43 :           *PassRegistry::getPassRegistry());
     935          43 :     }
     936             : 
     937             :     bool runOnFunction(Function &F) override;
     938             :     void releaseMemory() override;
     939             :     void getAnalysisUsage(AnalysisUsage &) const override;
     940             :     void print(raw_ostream &, const Module * = nullptr) const override;
     941             :     DependenceInfo &getDI() const;
     942             : 
     943             :   private:
     944             :     std::unique_ptr<DependenceInfo> info;
     945             :   }; // class DependenceAnalysisWrapperPass
     946             : 
     947             :   /// createDependenceAnalysisPass - This creates an instance of the
     948             :   /// DependenceAnalysis wrapper pass.
     949             :   FunctionPass *createDependenceAnalysisWrapperPass();
     950             : 
     951             : } // namespace llvm
     952             : 
     953             : #endif

Generated by: LCOV version 1.13