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