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