LLVM 17.0.0git
DependenceAnalysis.h
Go to the documentation of this file.
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
44#include "llvm/IR/PassManager.h"
45#include "llvm/Pass.h"
46
47namespace 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;
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.
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:
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 ///
294 public:
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,
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:
982
983 private:
984 static AnalysisKey Key;
986 }; // class DependenceAnalysis
987
988 /// Printer pass to dump DA results.
990 : public PassInfoMixin<DependenceAnalysisPrinterPass> {
992 bool NormalizeResults = false)
993 : OS(OS), NormalizeResults(NormalizeResults) {}
994
996
997 private:
998 raw_ostream &OS;
999 bool NormalizeResults;
1000 }; // class DependenceAnalysisPrinterPass
1001
1002 /// Legacy pass manager pass to access dependence information
1004 public:
1005 static char ID; // Class identification, replacement for typeinfo
1007
1008 bool runOnFunction(Function &F) override;
1009 void releaseMemory() override;
1010 void getAnalysisUsage(AnalysisUsage &) const override;
1011 void print(raw_ostream &, const Module * = nullptr) const override;
1012 DependenceInfo &getDI() const;
1013
1014 private:
1015 std::unique_ptr<DependenceInfo> info;
1016 }; // class DependenceAnalysisWrapperPass
1017
1018 /// createDependenceAnalysisPass - This creates an instance of the
1019 /// DependenceAnalysis wrapper pass.
1021
1022} // namespace llvm
1023
1024#endif
basic Basic Alias true
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
uint64_t Size
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
hexagon gen pred
Hexagon Hardware Loops
Loop::LoopBounds::Direction Direction
Definition: LoopInfo.cpp:230
#define F(x, y, z)
Definition: MD5.cpp:55
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
FunctionAnalysisManager FAM
This header defines various interfaces for pass management in LLVM.
This file implements the SmallBitVector class.
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:661
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
Represent the analysis usage information of a pass.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:718
Legacy pass manager pass to access dependence information.
void getAnalysisUsage(AnalysisUsage &) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void print(raw_ostream &, const Module *=nullptr) const override
print - Print out the internal state of the pass.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
AnalysisPass to compute dependence information in a function.
Result run(Function &F, FunctionAnalysisManager &FAM)
DependenceInfo - This class is the main dependence-analysis driver.
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle transitive invalidation when the cached analysis results go away.
const SCEV * getSplitIteration(const Dependence &Dep, unsigned Level)
getSplitIteration - Give a dependence that's splittable at some particular level, return the iteratio...
Function * getFunction() const
std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool PossiblyLoopIndependent)
depends - Tests for a dependence between the Src and Dst instructions.
DependenceInfo(Function *F, AAResults *AA, ScalarEvolution *SE, LoopInfo *LI)
Dependence - This class represents a dependence between two memory memory references in a function.
virtual unsigned getDirection(unsigned Level) const
getDirection - Returns the direction associated with a particular level.
virtual bool isPeelFirst(unsigned Level) const
isPeelFirst - Returns true if peeling the first iteration from this loop will break this dependence.
Instruction * getDst() const
getDst - Returns the destination instruction for this dependence.
Dependence & operator=(Dependence &&)=default
bool isOrdered() const
isOrdered - Returns true if dependence is Output, Flow, or Anti
void setNextSuccessor(const Dependence *succ)
setNextSuccessor - Sets the value of the NextSuccessor field.
Dependence(Dependence &&)=default
bool isUnordered() const
isUnordered - Returns true if dependence is Input
virtual bool isConfused() const
isConfused - Returns true if this dependence is confused (the compiler understands nothing and makes ...
virtual bool isSplitable(unsigned Level) const
isSplitable - Returns true if splitting this loop will break the dependence.
virtual const SCEV * getDistance(unsigned Level) const
getDistance - Returns the distance (or NULL) associated with a particular level.
virtual bool isScalar(unsigned Level) const
isScalar - Returns true if a particular level is scalar; that is, if no subscript in the source or de...
virtual bool isConsistent() const
isConsistent - Returns true if this dependence is consistent (occurs every time the source and destin...
virtual bool isPeelLast(unsigned Level) const
isPeelLast - Returns true if peeling the last iteration from this loop will break this dependence.
virtual unsigned getLevels() const
getLevels - Returns the number of common loops surrounding the source and destination of the dependen...
const Dependence * getNextPredecessor() const
getNextPredecessor - Returns the value of the NextPredecessor field.
bool isFlow() const
isFlow - Returns true if this is a flow (aka true) dependence.
Dependence(Instruction *Source, Instruction *Destination)
virtual ~Dependence()=default
bool isInput() const
isInput - Returns true if this is an input dependence.
virtual bool normalize(ScalarEvolution *SE)
If the direction vector is negative, normalize the direction vector to make it non-negative.
bool isAnti() const
isAnti - Returns true if this is an anti dependence.
const Dependence * getNextSuccessor() const
getNextSuccessor - Returns the value of the NextSuccessor field.
virtual bool isDirectionNegative() const
Check if the direction vector is negative.
Instruction * getSrc() const
getSrc - Returns the source instruction for this dependence.
virtual bool isLoopIndependent() const
isLoopIndependent - Returns true if this is a loop-independent dependence.
bool isOutput() const
isOutput - Returns true if this is an output dependence.
void setNextPredecessor(const Dependence *pred)
setNextPredecessor - Sets the value of the NextPredecessor field.
void dump(raw_ostream &OS) const
dump - For debugging purposes, dumps a dependence to OS.
FullDependence - This class represents a dependence between two memory references in a function.
unsigned getDirection(unsigned Level) const override
getDirection - Returns the direction associated with a particular level.
const SCEV * getDistance(unsigned Level) const override
getDistance - Returns the distance (or NULL) associated with a particular level.
bool isConfused() const override
isConfused - Returns true if this dependence is confused (the compiler understands nothing and makes ...
bool isDirectionNegative() const override
Check if the direction vector is negative.
bool isSplitable(unsigned Level) const override
isSplitable - Returns true if splitting the loop will break the dependence.
bool isLoopIndependent() const override
isLoopIndependent - Returns true if this is a loop-independent dependence.
bool isScalar(unsigned Level) const override
isScalar - Returns true if a particular level is scalar; that is, if no subscript in the source or de...
bool isPeelLast(unsigned Level) const override
isPeelLast - Returns true if peeling the last iteration from this loop will break this dependence.
unsigned getLevels() const override
getLevels - Returns the number of common loops surrounding the source and destination of the dependen...
bool isPeelFirst(unsigned Level) const override
isPeelFirst - Returns true if peeling the first iteration from this loop will break this dependence.
bool isConsistent() const override
isConsistent - Returns true if this dependence is consistent (occurs every time the source and destin...
bool normalize(ScalarEvolution *SE) override
If the direction vector is negative, normalize the direction vector to make it non-negative.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
This class represents an analyzed expression in the program.
The main scalar evolution driver.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
@ Lower
The operation itself must be expressed in terms of simpler actions on this target.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
ArrayRef(const T &OneElt) -> ArrayRef< T >
FunctionPass * createDependenceAnalysisWrapperPass()
createDependenceAnalysisPass - This creates an instance of the DependenceAnalysis wrapper pass.
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
Printer pass to dump DA results.
DependenceAnalysisPrinterPass(raw_ostream &OS, bool NormalizeResults=false)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Dependence::DVEntry - Each level in the distance/direction vector has a direction (or perhaps a union...
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371