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