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