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. |
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. |
70 |
class Dependence { |
71 |
public: |
72 |
Dependence(Instruction *Source, |
73 |
Instruction *Destination) : |
74 |
Src(Source), |
75 |
Dst(Destination), |
76 |
NextPredecessor(NULL), |
77 |
NextSuccessor(NULL) {} |
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), |
99 |
PeelLast(false), Splitable(false), Distance(NULL) { } |
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. |
157 |
virtual const SCEV *getDistance(unsigned Level) const { return NULL; } |
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 |
|
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 |
|
200 |
/// dump - For debugging purposes, dumps a dependence to OS. |
201 |
/// |
202 |
void dump(raw_ostream &OS) const; |
203 |
private: |
204 |
Instruction *Src, *Dst; |
205 |
const Dependence *NextPredecessor, *NextSuccessor; |
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. |
230 |
bool isLoopIndependent() const { return LoopIndependent; } |
231 |
|
232 |
/// isConfused - Returns true if this dependence is confused |
233 |
/// (the compiler understands nothing and makes worst-case |
234 |
/// assumptions). |
235 |
bool isConfused() const { return false; } |
236 |
|
237 |
/// isConsistent - Returns true if this dependence is consistent |
238 |
/// (occurs every time the source and destination are executed). |
239 |
bool isConsistent() const { return Consistent; } |
240 |
|
241 |
/// getLevels - Returns the number of common loops surrounding the |
242 |
/// source and destination of the dependence. |
243 |
unsigned getLevels() const { return Levels; } |
244 |
|
245 |
/// getDirection - Returns the direction associated with a particular |
246 |
/// level. |
247 |
unsigned getDirection(unsigned Level) const; |
248 |
|
249 |
/// getDistance - Returns the distance (or NULL) associated with a |
250 |
/// particular level. |
251 |
const SCEV *getDistance(unsigned Level) const; |
252 |
|
253 |
/// isPeelFirst - Returns true if peeling the first iteration from |
254 |
/// this loop will break this dependence. |
255 |
bool isPeelFirst(unsigned Level) const; |
256 |
|
257 |
/// isPeelLast - Returns true if peeling the last iteration from |
258 |
/// this loop will break this dependence. |
259 |
bool isPeelLast(unsigned Level) const; |
260 |
|
261 |
/// isSplitable - Returns true if splitting the loop will break |
262 |
/// the dependence. |
263 |
bool isSplitable(unsigned Level) const; |
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. |
268 |
bool isScalar(unsigned Level) const; |
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. |
290 |
Dependence *depends(Instruction *Src, |
291 |
Instruction *Dst, |
292 |
bool PossiblyLoopIndependent); |
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. |
334 |
const SCEV *getSplitIteration(const Dependence *Dep, unsigned Level); |
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 |
|
526 |
/// removeMatchingExtensions - Examines a subscript pair. |
527 |
/// If the source and destination are identically sign (or zero) |
528 |
/// extended, it strips off the extension in an effort to |
529 |
/// simplify the actual analysis. |
530 |
void removeMatchingExtensions(Subscript *Pair); |
531 |
|
532 |
/// collectCommonLoops - Finds the set of loops from the LoopNest that |
533 |
/// have a level <= CommonLevels and are referred to by the SCEV Expression. |
534 |
void collectCommonLoops(const SCEV *Expression, |
535 |
const Loop *LoopNest, |
536 |
SmallBitVector &Loops) const; |
537 |
|
538 |
/// checkSrcSubscript - Examines the SCEV Src, returning true iff it's |
539 |
/// linear. Collect the set of loops mentioned by Src. |
540 |
bool checkSrcSubscript(const SCEV *Src, |
541 |
const Loop *LoopNest, |
542 |
SmallBitVector &Loops); |
543 |
|
544 |
/// checkDstSubscript - Examines the SCEV Dst, returning true iff it's |
545 |
/// linear. Collect the set of loops mentioned by Dst. |
546 |
bool checkDstSubscript(const SCEV *Dst, |
547 |
const Loop *LoopNest, |
548 |
SmallBitVector &Loops); |
549 |
|
550 |
/// isKnownPredicate - Compare X and Y using the predicate Pred. |
551 |
/// Basically a wrapper for SCEV::isKnownPredicate, |
552 |
/// but tries harder, especially in the presence of sign and zero |
553 |
/// extensions and symbolics. |
554 |
bool isKnownPredicate(ICmpInst::Predicate Pred, |
555 |
const SCEV *X, |
556 |
const SCEV *Y) const; |
557 |
|
558 |
/// collectUpperBound - All subscripts are the same type (on my machine, |
559 |
/// an i64). The loop bound may be a smaller type. collectUpperBound |
560 |
/// find the bound, if available, and zero extends it to the Type T. |
561 |
/// (I zero extend since the bound should always be >= 0.) |
562 |
/// If no upper bound is available, return NULL. |
563 |
const SCEV *collectUpperBound(const Loop *l, Type *T) const; |
564 |
|
565 |
/// collectConstantUpperBound - Calls collectUpperBound(), then |
566 |
/// attempts to cast it to SCEVConstant. If the cast fails, |
567 |
/// returns NULL. |
568 |
const SCEVConstant *collectConstantUpperBound(const Loop *l, Type *T) const; |
569 |
|
570 |
/// classifyPair - Examines the subscript pair (the Src and Dst SCEVs) |
571 |
/// and classifies it as either ZIV, SIV, RDIV, MIV, or Nonlinear. |
572 |
/// Collects the associated loops in a set. |
573 |
Subscript::ClassificationKind classifyPair(const SCEV *Src, |
574 |
const Loop *SrcLoopNest, |
575 |
const SCEV *Dst, |
576 |
const Loop *DstLoopNest, |
577 |
SmallBitVector &Loops); |
578 |
|
579 |
/// testZIV - Tests the ZIV subscript pair (Src and Dst) for dependence. |
580 |
/// Returns true if any possible dependence is disproved. |
581 |
/// If there might be a dependence, returns false. |
582 |
/// If the dependence isn't proven to exist, |
583 |
/// marks the Result as inconsistent. |
584 |
bool testZIV(const SCEV *Src, |
585 |
const SCEV *Dst, |
586 |
FullDependence &Result) const; |
587 |
|
588 |
/// testSIV - Tests the SIV subscript pair (Src and Dst) for dependence. |
589 |
/// Things of the form [c1 + a1*i] and [c2 + a2*j], where |
590 |
/// i and j are induction variables, c1 and c2 are loop invariant, |
591 |
/// and a1 and a2 are constant. |
592 |
/// Returns true if any possible dependence is disproved. |
593 |
/// If there might be a dependence, returns false. |
594 |
/// Sets appropriate direction vector entry and, when possible, |
595 |
/// the distance vector entry. |
596 |
/// If the dependence isn't proven to exist, |
597 |
/// marks the Result as inconsistent. |
598 |
bool testSIV(const SCEV *Src, |
599 |
const SCEV *Dst, |
600 |
unsigned &Level, |
601 |
FullDependence &Result, |
602 |
Constraint &NewConstraint, |
603 |
const SCEV *&SplitIter) const; |
604 |
|
605 |
/// testRDIV - Tests the RDIV subscript pair (Src and Dst) for dependence. |
606 |
/// Things of the form [c1 + a1*i] and [c2 + a2*j] |
607 |
/// where i and j are induction variables, c1 and c2 are loop invariant, |
608 |
/// and a1 and a2 are constant. |
609 |
/// With minor algebra, this test can also be used for things like |
610 |
/// [c1 + a1*i + a2*j][c2]. |
611 |
/// Returns true if any possible dependence is disproved. |
612 |
/// If there might be a dependence, returns false. |
613 |
/// Marks the Result as inconsistent. |
614 |
bool testRDIV(const SCEV *Src, |
615 |
const SCEV *Dst, |
616 |
FullDependence &Result) const; |
617 |
|
618 |
/// testMIV - Tests the MIV subscript pair (Src and Dst) for dependence. |
619 |
/// Returns true if dependence disproved. |
620 |
/// Can sometimes refine direction vectors. |
621 |
bool testMIV(const SCEV *Src, |
622 |
const SCEV *Dst, |
623 |
const SmallBitVector &Loops, |
624 |
FullDependence &Result) const; |
625 |
|
626 |
/// strongSIVtest - Tests the strong SIV subscript pair (Src and Dst) |
627 |
/// for dependence. |
628 |
/// Things of the form [c1 + a*i] and [c2 + a*i], |
629 |
/// where i is an induction variable, c1 and c2 are loop invariant, |
630 |
/// and a is a constant |
631 |
/// Returns true if any possible dependence is disproved. |
632 |
/// If there might be a dependence, returns false. |
633 |
/// Sets appropriate direction and distance. |
634 |
bool strongSIVtest(const SCEV *Coeff, |
635 |
const SCEV *SrcConst, |
636 |
const SCEV *DstConst, |
637 |
const Loop *CurrentLoop, |
638 |
unsigned Level, |
639 |
FullDependence &Result, |
640 |
Constraint &NewConstraint) const; |
641 |
|
642 |
/// weakCrossingSIVtest - Tests the weak-crossing SIV subscript pair |
643 |
/// (Src and Dst) for dependence. |
644 |
/// Things of the form [c1 + a*i] and [c2 - a*i], |
645 |
/// where i is an induction variable, c1 and c2 are loop invariant, |
646 |
/// and a is a constant. |
647 |
/// Returns true if any possible dependence is disproved. |
648 |
/// If there might be a dependence, returns false. |
649 |
/// Sets appropriate direction entry. |
650 |
/// Set consistent to false. |
651 |
/// Marks the dependence as splitable. |
652 |
bool weakCrossingSIVtest(const SCEV *SrcCoeff, |
653 |
const SCEV *SrcConst, |
654 |
const SCEV *DstConst, |
655 |
const Loop *CurrentLoop, |
656 |
unsigned Level, |
657 |
FullDependence &Result, |
658 |
Constraint &NewConstraint, |
659 |
const SCEV *&SplitIter) const; |
660 |
|
661 |
/// ExactSIVtest - Tests the SIV subscript pair |
662 |
/// (Src and Dst) for dependence. |
663 |
/// Things of the form [c1 + a1*i] and [c2 + a2*i], |
664 |
/// where i is an induction variable, c1 and c2 are loop invariant, |
665 |
/// and a1 and a2 are constant. |
666 |
/// Returns true if any possible dependence is disproved. |
667 |
/// If there might be a dependence, returns false. |
668 |
/// Sets appropriate direction entry. |
669 |
/// Set consistent to false. |
670 |
bool exactSIVtest(const SCEV *SrcCoeff, |
671 |
const SCEV *DstCoeff, |
672 |
const SCEV *SrcConst, |
673 |
const SCEV *DstConst, |
674 |
const Loop *CurrentLoop, |
675 |
unsigned Level, |
676 |
FullDependence &Result, |
677 |
Constraint &NewConstraint) const; |
678 |
|
679 |
/// weakZeroSrcSIVtest - Tests the weak-zero SIV subscript pair |
680 |
/// (Src and Dst) for dependence. |
681 |
/// Things of the form [c1] and [c2 + a*i], |
682 |
/// where i is an induction variable, c1 and c2 are loop invariant, |
683 |
/// and a is a constant. See also weakZeroDstSIVtest. |
684 |
/// Returns true if any possible dependence is disproved. |
685 |
/// If there might be a dependence, returns false. |
686 |
/// Sets appropriate direction entry. |
687 |
/// Set consistent to false. |
688 |
/// If loop peeling will break the dependence, mark appropriately. |
689 |
bool weakZeroSrcSIVtest(const SCEV *DstCoeff, |
690 |
const SCEV *SrcConst, |
691 |
const SCEV *DstConst, |
692 |
const Loop *CurrentLoop, |
693 |
unsigned Level, |
694 |
FullDependence &Result, |
695 |
Constraint &NewConstraint) const; |
696 |
|
697 |
/// weakZeroDstSIVtest - Tests the weak-zero SIV subscript pair |
698 |
/// (Src and Dst) for dependence. |
699 |
/// Things of the form [c1 + a*i] and [c2], |
700 |
/// where i is an induction variable, c1 and c2 are loop invariant, |
701 |
/// and a is a constant. See also weakZeroSrcSIVtest. |
702 |
/// Returns true if any possible dependence is disproved. |
703 |
/// If there might be a dependence, returns false. |
704 |
/// Sets appropriate direction entry. |
705 |
/// Set consistent to false. |
706 |
/// If loop peeling will break the dependence, mark appropriately. |
707 |
bool weakZeroDstSIVtest(const SCEV *SrcCoeff, |
708 |
const SCEV *SrcConst, |
709 |
const SCEV *DstConst, |
710 |
const Loop *CurrentLoop, |
711 |
unsigned Level, |
712 |
FullDependence &Result, |
713 |
Constraint &NewConstraint) const; |
714 |
|
715 |
/// exactRDIVtest - Tests the RDIV subscript pair for dependence. |
716 |
/// Things of the form [c1 + a*i] and [c2 + b*j], |
717 |
/// where i and j are induction variable, c1 and c2 are loop invariant, |
718 |
/// and a and b are constants. |
719 |
/// Returns true if any possible dependence is disproved. |
720 |
/// Marks the result as inconsistent. |
721 |
/// Works in some cases that symbolicRDIVtest doesn't, |
722 |
/// and vice versa. |
723 |
bool exactRDIVtest(const SCEV *SrcCoeff, |
724 |
const SCEV *DstCoeff, |
725 |
const SCEV *SrcConst, |
726 |
const SCEV *DstConst, |
727 |
const Loop *SrcLoop, |
728 |
const Loop *DstLoop, |
729 |
FullDependence &Result) const; |
730 |
|
731 |
/// symbolicRDIVtest - Tests the RDIV subscript pair for dependence. |
732 |
/// Things of the form [c1 + a*i] and [c2 + b*j], |
733 |
/// where i and j are induction variable, c1 and c2 are loop invariant, |
734 |
/// and a and b are constants. |
735 |
/// Returns true if any possible dependence is disproved. |
736 |
/// Marks the result as inconsistent. |
737 |
/// Works in some cases that exactRDIVtest doesn't, |
738 |
/// and vice versa. Can also be used as a backup for |
739 |
/// ordinary SIV tests. |
740 |
bool symbolicRDIVtest(const SCEV *SrcCoeff, |
741 |
const SCEV *DstCoeff, |
742 |
const SCEV *SrcConst, |
743 |
const SCEV *DstConst, |
744 |
const Loop *SrcLoop, |
745 |
const Loop *DstLoop) const; |
746 |
|
747 |
/// gcdMIVtest - Tests an MIV subscript pair for dependence. |
748 |
/// Returns true if any possible dependence is disproved. |
749 |
/// Marks the result as inconsistent. |
750 |
/// Can sometimes disprove the equal direction for 1 or more loops. |
751 |
// Can handle some symbolics that even the SIV tests don't get, |
752 |
/// so we use it as a backup for everything. |
753 |
bool gcdMIVtest(const SCEV *Src, |
754 |
const SCEV *Dst, |
755 |
FullDependence &Result) const; |
756 |
|
757 |
/// banerjeeMIVtest - Tests an MIV subscript pair for dependence. |
758 |
/// Returns true if any possible dependence is disproved. |
759 |
/// Marks the result as inconsistent. |
760 |
/// Computes directions. |
761 |
bool banerjeeMIVtest(const SCEV *Src, |
762 |
const SCEV *Dst, |
763 |
const SmallBitVector &Loops, |
764 |
FullDependence &Result) const; |
765 |
|
766 |
/// collectCoefficientInfo - Walks through the subscript, |
767 |
/// collecting each coefficient, the associated loop bounds, |
768 |
/// and recording its positive and negative parts for later use. |
769 |
CoefficientInfo *collectCoeffInfo(const SCEV *Subscript, |
770 |
bool SrcFlag, |
771 |
const SCEV *&Constant) const; |
772 |
|
773 |
/// getPositivePart - X^+ = max(X, 0). |
774 |
/// |
775 |
const SCEV *getPositivePart(const SCEV *X) const; |
776 |
|
777 |
/// getNegativePart - X^- = min(X, 0). |
778 |
/// |
779 |
const SCEV *getNegativePart(const SCEV *X) const; |
780 |
|
781 |
/// getLowerBound - Looks through all the bounds info and |
782 |
/// computes the lower bound given the current direction settings |
783 |
/// at each level. |
784 |
const SCEV *getLowerBound(BoundInfo *Bound) const; |
785 |
|
786 |
/// getUpperBound - Looks through all the bounds info and |
787 |
/// computes the upper bound given the current direction settings |
788 |
/// at each level. |
789 |
const SCEV *getUpperBound(BoundInfo *Bound) const; |
790 |
|
791 |
/// exploreDirections - Hierarchically expands the direction vector |
792 |
/// search space, combining the directions of discovered dependences |
793 |
/// in the DirSet field of Bound. Returns the number of distinct |
794 |
/// dependences discovered. If the dependence is disproved, |
795 |
/// it will return 0. |
796 |
unsigned exploreDirections(unsigned Level, |
797 |
CoefficientInfo *A, |
798 |
CoefficientInfo *B, |
799 |
BoundInfo *Bound, |
800 |
const SmallBitVector &Loops, |
801 |
unsigned &DepthExpanded, |
802 |
const SCEV *Delta) const; |
803 |
|
804 |
/// testBounds - Returns true iff the current bounds are plausible. |
805 |
/// |
806 |
bool testBounds(unsigned char DirKind, |
807 |
unsigned Level, |
808 |
BoundInfo *Bound, |
809 |
const SCEV *Delta) const; |
810 |
|
811 |
/// findBoundsALL - Computes the upper and lower bounds for level K |
812 |
/// using the * direction. Records them in Bound. |
813 |
void findBoundsALL(CoefficientInfo *A, |
814 |
CoefficientInfo *B, |
815 |
BoundInfo *Bound, |
816 |
unsigned K) const; |
817 |
|
818 |
/// findBoundsLT - Computes the upper and lower bounds for level K |
819 |
/// using the < direction. Records them in Bound. |
820 |
void findBoundsLT(CoefficientInfo *A, |
821 |
CoefficientInfo *B, |
822 |
BoundInfo *Bound, |
823 |
unsigned K) const; |
824 |
|
825 |
/// findBoundsGT - Computes the upper and lower bounds for level K |
826 |
/// using the > direction. Records them in Bound. |
827 |
void findBoundsGT(CoefficientInfo *A, |
828 |
CoefficientInfo *B, |
829 |
BoundInfo *Bound, |
830 |
unsigned K) const; |
831 |
|
832 |
/// findBoundsEQ - Computes the upper and lower bounds for level K |
833 |
/// using the = direction. Records them in Bound. |
834 |
void findBoundsEQ(CoefficientInfo *A, |
835 |
CoefficientInfo *B, |
836 |
BoundInfo *Bound, |
837 |
unsigned K) const; |
838 |
|
839 |
/// intersectConstraints - Updates X with the intersection |
840 |
/// of the Constraints X and Y. Returns true if X has changed. |
841 |
bool intersectConstraints(Constraint *X, |
842 |
const Constraint *Y); |
843 |
|
844 |
/// propagate - Review the constraints, looking for opportunities |
845 |
/// to simplify a subscript pair (Src and Dst). |
846 |
/// Return true if some simplification occurs. |
847 |
/// If the simplification isn't exact (that is, if it is conservative |
848 |
/// in terms of dependence), set consistent to false. |
849 |
bool propagate(const SCEV *&Src, |
850 |
const SCEV *&Dst, |
851 |
SmallBitVector &Loops, |
852 |
SmallVectorImpl<Constraint> &Constraints, |
853 |
bool &Consistent); |
854 |
|
855 |
/// propagateDistance - Attempt to propagate a distance |
856 |
/// constraint into a subscript pair (Src and Dst). |
857 |
/// Return true if some simplification occurs. |
858 |
/// If the simplification isn't exact (that is, if it is conservative |
859 |
/// in terms of dependence), set consistent to false. |
860 |
bool propagateDistance(const SCEV *&Src, |
861 |
const SCEV *&Dst, |
862 |
Constraint &CurConstraint, |
863 |
bool &Consistent); |
864 |
|
865 |
/// propagatePoint - Attempt to propagate a point |
866 |
/// constraint into a subscript pair (Src and Dst). |
867 |
/// Return true if some simplification occurs. |
868 |
bool propagatePoint(const SCEV *&Src, |
869 |
const SCEV *&Dst, |
870 |
Constraint &CurConstraint); |
871 |
|
872 |
/// propagateLine - Attempt to propagate a line |
873 |
/// constraint into a subscript pair (Src and Dst). |
874 |
/// Return true if some simplification occurs. |
875 |
/// If the simplification isn't exact (that is, if it is conservative |
876 |
/// in terms of dependence), set consistent to false. |
877 |
bool propagateLine(const SCEV *&Src, |
878 |
const SCEV *&Dst, |
879 |
Constraint &CurConstraint, |
880 |
bool &Consistent); |
881 |
|
882 |
/// findCoefficient - Given a linear SCEV, |
883 |
/// return the coefficient corresponding to specified loop. |
884 |
/// If there isn't one, return the SCEV constant 0. |
885 |
/// For example, given a*i + b*j + c*k, returning the coefficient |
886 |
/// corresponding to the j loop would yield b. |
887 |
const SCEV *findCoefficient(const SCEV *Expr, |
888 |
const Loop *TargetLoop) const; |
889 |
|
890 |
/// zeroCoefficient - Given a linear SCEV, |
891 |
/// return the SCEV given by zeroing out the coefficient |
892 |
/// corresponding to the specified loop. |
893 |
/// For example, given a*i + b*j + c*k, zeroing the coefficient |
894 |
/// corresponding to the j loop would yield a*i + c*k. |
895 |
const SCEV *zeroCoefficient(const SCEV *Expr, |
896 |
const Loop *TargetLoop) const; |
897 |
|
898 |
/// addToCoefficient - Given a linear SCEV Expr, |
899 |
/// return the SCEV given by adding some Value to the |
900 |
/// coefficient corresponding to the specified TargetLoop. |
901 |
/// For example, given a*i + b*j + c*k, adding 1 to the coefficient |
902 |
/// corresponding to the j loop would yield a*i + (b+1)*j + c*k. |
903 |
const SCEV *addToCoefficient(const SCEV *Expr, |
904 |
const Loop *TargetLoop, |
905 |
const SCEV *Value) const; |
906 |
|
907 |
/// updateDirection - Update direction vector entry |
908 |
/// based on the current constraint. |
909 |
void updateDirection(Dependence::DVEntry &Level, |
910 |
const Constraint &CurConstraint) const; |
911 |
|
912 |
bool tryDelinearize(const SCEV *SrcSCEV, const SCEV *DstSCEV, |
913 |
SmallVectorImpl<Subscript> &Pair) const; |
914 |
|
915 |
public: |
916 |
static char ID; // Class identification, replacement for typeinfo |
917 |
DependenceAnalysis() : FunctionPass(ID) { |
918 |
initializeDependenceAnalysisPass(*PassRegistry::getPassRegistry()); |
919 |
} |
920 |
|
921 |
bool runOnFunction(Function &F); |
922 |
void releaseMemory(); |
923 |
void getAnalysisUsage(AnalysisUsage &) const; |
924 |
void print(raw_ostream &, const Module * = 0) const; |
925 |
}; // class DependenceAnalysis |
926 |
|
927 |
/// createDependenceAnalysisPass - This creates an instance of the |
928 |
/// DependenceAnalysis pass. |
929 |
FunctionPass *createDependenceAnalysisPass(); |
930 |
|
931 |
} // namespace llvm |
932 |
|
933 |
#endif |