include/llvm/Analysis/DependenceAnalysis.h

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