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