Lines Matching refs:Dependence
13 // Practical Dependence Testing
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.
22 // passes because there's a useful separation of concerns. A dependence exists
35 // Return a set of more precise dependences instead of just one dependence
56 /// Dependence - This class represents a dependence between two memory
59 /// determine anything beyond the existence of a dependence; that is, it
60 /// represents a confused dependence (see also FullDependence). In most
61 /// cases (for output, flow, and anti dependences), the dependence implies
65 /// When a dependence graph is built, each Dependence will be a member of
68 /// as singly-linked lists, with the "next" fields stored in the dependence
70 class Dependence {
72 Dependence(Instruction *Source,
78 virtual ~Dependence() {}
80 /// Dependence::DVEntry - Each level in the distance/direction vector
94 bool PeelFirst : 1; // Peeling the first iteration will break dependence.
95 bool PeelLast : 1; // Peeling the last iteration will break the dependence.
96 bool Splitable : 1; // Splitting the loop will break dependence.
102 /// getSrc - Returns the source instruction for this dependence.
106 /// getDst - Returns the destination instruction for this dependence.
110 /// isInput - Returns true if this is an input dependence.
114 /// isOutput - Returns true if this is an output dependence.
118 /// isFlow - Returns true if this is a flow (aka true) dependence.
122 /// isAnti - Returns true if this is an anti dependence.
126 /// isOrdered - Returns true if dependence is Output, Flow, or Anti
130 /// isUnordered - Returns true if dependence is Input
135 /// dependence.
138 /// isConfused - Returns true if this dependence is confused
143 /// isConsistent - Returns true if this dependence is consistent
148 /// source and destination of the dependence.
160 /// this loop will break this dependence.
164 /// this loop will break this dependence.
168 /// the dependence.
178 const Dependence *getNextPredecessor() const {
184 const Dependence *getNextSuccessor() const {
190 void setNextPredecessor(const Dependence *pred) {
196 void setNextSuccessor(const Dependence *succ) {
200 /// dump - For debugging purposes, dumps a dependence to OS.
205 const Dependence *NextPredecessor, *NextSuccessor;
210 /// FullDependence - This class represents a dependence between two memory
212 /// dependence (direction vectors, etc.) and is used when the compiler is
214 /// it is not a confused dependence (see Dependence). In most cases
215 /// (for output, flow, and anti dependences), the dependence implies an
218 class FullDependence : public Dependence {
229 /// dependence.
232 /// isConfused - Returns true if this dependence is confused
237 /// isConsistent - Returns true if this dependence is consistent
242 /// source and destination of the dependence.
254 /// this loop will break this dependence.
258 /// this loop will break this dependence.
262 /// the dependence.
278 /// DependenceAnalysis - This class is the main dependence-analysis driver.
284 /// depends - Tests for a dependence between the Src and Dst instructions.
285 /// Returns NULL if no dependence; otherwise, returns a Dependence (or a
290 Dependence *depends(Instruction *Src,
294 /// getSplitIteration - Give a dependence that's splittable at some
298 /// Generally, the dependence analyzer will be used to build
299 /// a dependence graph for a function (basically a map from instructions
319 /// There's a loop-carried flow dependence from the store to the load,
320 /// found by the weak-crossing SIV test. The dependence will have a flag,
321 /// indicating that the dependence can be broken by splitting the loop.
323 /// Splitting the loop breaks the dependence, like so:
332 /// breaks the dependence and allows us to vectorize/parallelize
334 const SCEV *getSplitIteration(const Dependence *Dep, unsigned Level);
372 /// Practical Dependence Testing
377 /// 1) Any - indicates no constraint, any dependence is possible.
379 /// representing the dependence equation.
380 /// 3) Distance - The value d of the dependence distance;
381 /// 4) Point - A point <x, y> representing the dependence from
383 /// 5) Empty - No dependence is possible.
497 /// If we're looking at the possibility of a dependence between the store
579 /// testZIV - Tests the ZIV subscript pair (Src and Dst) for dependence.
580 /// Returns true if any possible dependence is disproved.
581 /// If there might be a dependence, returns false.
582 /// If the dependence isn't proven to exist,
588 /// testSIV - Tests the SIV subscript pair (Src and Dst) for dependence.
592 /// Returns true if any possible dependence is disproved.
593 /// If there might be a dependence, returns false.
596 /// If the dependence isn't proven to exist,
605 /// testRDIV - Tests the RDIV subscript pair (Src and Dst) for dependence.
611 /// Returns true if any possible dependence is disproved.
612 /// If there might be a dependence, returns false.
618 /// testMIV - Tests the MIV subscript pair (Src and Dst) for dependence.
619 /// Returns true if dependence disproved.
627 /// for dependence.
631 /// Returns true if any possible dependence is disproved.
632 /// If there might be a dependence, returns false.
643 /// (Src and Dst) for dependence.
647 /// Returns true if any possible dependence is disproved.
648 /// If there might be a dependence, returns false.
651 /// Marks the dependence as splitable.
662 /// (Src and Dst) for dependence.
666 /// Returns true if any possible dependence is disproved.
667 /// If there might be a dependence, returns false.
680 /// (Src and Dst) for dependence.
684 /// Returns true if any possible dependence is disproved.
685 /// If there might be a dependence, returns false.
688 /// If loop peeling will break the dependence, mark appropriately.
698 /// (Src and Dst) for dependence.
702 /// Returns true if any possible dependence is disproved.
703 /// If there might be a dependence, returns false.
706 /// If loop peeling will break the dependence, mark appropriately.
715 /// exactRDIVtest - Tests the RDIV subscript pair for dependence.
719 /// Returns true if any possible dependence is disproved.
731 /// symbolicRDIVtest - Tests the RDIV subscript pair for dependence.
735 /// Returns true if any possible dependence is disproved.
747 /// gcdMIVtest - Tests an MIV subscript pair for dependence.
748 /// Returns true if any possible dependence is disproved.
757 /// banerjeeMIVtest - Tests an MIV subscript pair for dependence.
758 /// Returns true if any possible dependence is disproved.
794 /// dependences discovered. If the dependence is disproved,
848 /// in terms of dependence), set consistent to false.
859 /// in terms of dependence), set consistent to false.
876 /// in terms of dependence), set consistent to false.
909 void updateDirection(Dependence::DVEntry &Level,
