LLVM 24.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
46#include "llvm/IR/PassManager.h"
47#include "llvm/Pass.h"
49
50namespace llvm {
51class AAResults;
52struct AnalysisOptions;
53template <typename T> class ArrayRef;
54class Loop;
55class LoopInfo;
56class MDNode;
57class SCEVConstant;
58class raw_ostream;
59
60/// Dependence - This class represents a dependence between two memory
61/// memory references in a function. It contains minimal information and
62/// is used in the very common situation where the compiler is unable to
63/// determine anything beyond the existence of a dependence; that is, it
64/// represents a confused dependence (see also FullDependence). In most
65/// cases (for output, flow, and anti dependences), the dependence implies
66/// an ordering, where the source must precede the destination; in contrast,
67/// input dependences are unordered.
68///
69/// When a dependence graph is built, each Dependence will be a member of
70/// the set of predecessor edges for its destination instruction and a set
71/// if successor edges for its source instruction. These sets are represented
72/// as singly-linked lists, with the "next" fields stored in the dependence
73/// itelf.
75protected:
76 Dependence(Dependence &&) = default;
78
79public:
80 Dependence(Instruction *Source, Instruction *Destination,
81 const SCEVUnionPredicate &A)
82 : Src(Source), Dst(Destination), Assumptions(A) {}
83 virtual ~Dependence() = default;
84
85 /// Dependence::DVEntry - Each level in the distance/direction vector
86 /// has a direction (or perhaps a union of several directions), and
87 /// perhaps a distance.
88 /// The dependency information could be across a single loop level or across
89 /// two separate levels that have the same trip count and nesting depth,
90 /// which helps to provide information for loop fusion candidation.
91 /// For example, loops b and c have the same iteration count and depth:
92 /// for (a = ...) {
93 /// for (b = 0; b < 10; b++) {
94 /// }
95 /// for (c = 0; c < 10; c++) {
96 /// }
97 /// }
98 struct DVEntry {
99 enum : unsigned char {
100 NONE = 0,
101 LT = 1,
102 EQ = 2,
103 LE = 3,
104 GT = 4,
105 NE = 5,
106 GE = 6,
107 ALL = 7
108 };
109 unsigned char Direction : 3; // Init to ALL, then refine.
110 bool Scalar : 1; // Init to true.
111 const SCEV *Distance = nullptr; // NULL implies no distance available.
113 };
114
115 /// getSrc - Returns the source instruction for this dependence.
116 Instruction *getSrc() const { return Src; }
117
118 /// getDst - Returns the destination instruction for this dependence.
119 Instruction *getDst() const { return Dst; }
120
121 /// isInput - Returns true if this is an input dependence.
122 bool isInput() const;
123
124 /// isOutput - Returns true if this is an output dependence.
125 bool isOutput() const;
126
127 /// isFlow - Returns true if this is a flow (aka true) dependence.
128 bool isFlow() const;
129
130 /// isAnti - Returns true if this is an anti dependence.
131 bool isAnti() const;
132
133 /// isOrdered - Returns true if dependence is Output, Flow, or Anti
134 bool isOrdered() const { return isOutput() || isFlow() || isAnti(); }
135
136 /// isUnordered - Returns true if dependence is Input
137 bool isUnordered() const { return isInput(); }
138
139 /// isLoopIndependent - Returns true if this is a loop-independent
140 /// dependence.
141 virtual bool isLoopIndependent() const { return true; }
142
143 /// isConfused - Returns true if this dependence is confused
144 /// (the compiler understands nothing and makes worst-case assumptions).
145 virtual bool isConfused() const { return true; }
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 /// getSameSDLevels - Returns the number of separate SameSD loops surrounding
152 /// the source and destination of the dependence.
153 virtual unsigned getSameSDLevels() const { return 0; }
154
155 /// getDirection - Returns the direction associated with a particular
156 /// common or SameSD level.
157 virtual unsigned getDirection(unsigned Level, bool SameSD = false) const {
158 return DVEntry::ALL;
159 }
160
161 /// getDistance - Returns the distance (or NULL) associated with a
162 /// particular common or SameSD level.
163 virtual const SCEV *getDistance(unsigned Level, bool SameSD = false) const {
164 return nullptr;
165 }
166
167 /// Check if the direction vector is negative. A negative direction
168 /// vector means Src and Dst are reversed in the actual program.
169 virtual bool isDirectionNegative() const { return false; }
170
171 /// Negate the dependence by swapping the source and destination, and
172 /// reversing the direction and distance information.
173 virtual void negate(ScalarEvolution &SE) {}
174
175 /// If the direction vector is negative, normalize the direction
176 /// vector to make it non-negative. Normalization is done by reversing
177 /// Src and Dst, plus reversing the dependence directions and distances
178 /// in the vector.
179 virtual bool normalize(ScalarEvolution *SE) { return false; }
180
181 /// inSameSDLoops - Returns true if this level is an SameSD level, i.e.,
182 /// performed across two separate loop nests that have the Same Iteration and
183 /// Depth.
184 virtual bool inSameSDLoops(unsigned Level) const { return false; }
185
186 /// isScalar - Returns true if a particular regular or SameSD level is
187 /// scalar; that is, if no subscript in the source or destination mention
188 /// the induction variable associated with the loop at this level.
189 virtual bool isScalar(unsigned Level, bool SameSD = false) const;
190
191 /// getNextPredecessor - Returns the value of the NextPredecessor field.
192 const Dependence *getNextPredecessor() const { return NextPredecessor; }
193
194 /// getNextSuccessor - Returns the value of the NextSuccessor field.
195 const Dependence *getNextSuccessor() const { return NextSuccessor; }
196
197 /// setNextPredecessor - Sets the value of the NextPredecessor
198 /// field.
199 void setNextPredecessor(const Dependence *pred) { NextPredecessor = pred; }
200
201 /// setNextSuccessor - Sets the value of the NextSuccessor field.
202 void setNextSuccessor(const Dependence *succ) { NextSuccessor = succ; }
203
204 /// getRuntimeAssumptions - Returns the runtime assumptions under which this
205 /// Dependence relation is valid.
206 SCEVUnionPredicate getRuntimeAssumptions() const { return Assumptions; }
207
208 /// dump - For debugging purposes, dumps a dependence to OS.
209 void dump(raw_ostream &OS) const;
210
211 /// dumpImp - For debugging purposes. Dumps a dependence to OS with or
212 /// without considering the SameSD levels.
213 void dumpImp(raw_ostream &OS, bool IsSameSD = false) const;
214
215protected:
217
218private:
219 SCEVUnionPredicate Assumptions;
220 const Dependence *NextPredecessor = nullptr, *NextSuccessor = nullptr;
221 friend class DependenceInfo;
222};
223
224/// FullDependence - This class represents a dependence between two memory
225/// references in a function. It contains detailed information about the
226/// dependence (direction vectors, etc.) and is used when the compiler is
227/// able to accurately analyze the interaction of the references; that is,
228/// it is not a confused dependence (see Dependence). In most cases
229/// (for output, flow, and anti dependences), the dependence implies an
230/// ordering, where the source must precede the destination; in contrast,
231/// input dependences are unordered.
232class LLVM_ABI FullDependence final : public Dependence {
233public:
234 FullDependence(Instruction *Source, Instruction *Destination,
235 const SCEVUnionPredicate &Assumes,
236 bool PossiblyLoopIndependent, unsigned Levels);
237
238 /// isLoopIndependent - Returns true if this is a loop-independent
239 /// dependence.
240 bool isLoopIndependent() const override { return LoopIndependent; }
241
242 /// isConfused - Returns true if this dependence is confused
243 /// (the compiler understands nothing and makes worst-case
244 /// assumptions).
245 bool isConfused() const override { return false; }
246
247 /// getLevels - Returns the number of common loops surrounding the
248 /// source and destination of the dependence.
249 unsigned getLevels() const override { return Levels; }
250
251 /// getSameSDLevels - Returns the number of separate SameSD loops surrounding
252 /// the source and destination of the dependence.
253 unsigned getSameSDLevels() const override { return SameSDLevels; }
254
255 /// getDVEntry - Returns the DV entry associated with a regular or a
256 /// SameSD level.
257 DVEntry getDVEntry(unsigned Level, bool IsSameSD) const {
258 if (!IsSameSD) {
259 assert(0 < Level && Level <= Levels && "Level out of range");
260 return DV[Level - 1];
261 } else {
262 assert(Levels < Level &&
263 Level <= static_cast<unsigned>(Levels) + SameSDLevels &&
264 "isSameSD level out of range");
265 return DVSameSD[Level - Levels - 1];
266 }
267 }
268
269 /// getDirection - Returns the direction associated with a particular
270 /// common or SameSD level.
271 unsigned getDirection(unsigned Level, bool SameSD = false) const override;
272
273 /// getDistance - Returns the distance (or NULL) associated with a
274 /// particular common or SameSD level.
275 const SCEV *getDistance(unsigned Level, bool SameSD = false) const override;
276
277 /// Check if the direction vector is negative. A negative direction
278 /// vector means Src and Dst are reversed in the actual program.
279 bool isDirectionNegative() const override;
280
281 void negate(ScalarEvolution &SE) override;
282
283 /// If the direction vector is negative, normalize the direction
284 /// vector to make it non-negative. Normalization is done by reversing
285 /// Src and Dst, plus reversing the dependence directions and distances
286 /// in the vector.
287 bool normalize(ScalarEvolution *SE) override;
288
289 /// inSameSDLoops - Returns true if this level is an SameSD level, i.e.,
290 /// performed across two separate loop nests that have the Same Iteration and
291 /// Depth.
292 bool inSameSDLoops(unsigned Level) const override;
293
294 /// isScalar - Returns true if a particular regular or SameSD level is
295 /// scalar; that is, if no subscript in the source or destination mention
296 /// the induction variable associated with the loop at this level.
297 bool isScalar(unsigned Level, bool SameSD = false) const override;
298
299private:
300 unsigned short Levels;
301 unsigned short SameSDLevels;
302 bool LoopIndependent;
303 std::unique_ptr<DVEntry[]> DV;
304 std::unique_ptr<DVEntry[]> DVSameSD; // DV entries on SameSD levels
305 friend class DependenceInfo;
306};
307
308/// DependenceInfo - This class is the main dependence-analysis driver.
310public:
312 LoopInfo *LI);
313
314 /// Handle transitive invalidation when the cached analysis results go away.
316 FunctionAnalysisManager::Invalidator &Inv);
317
318 /// depends - Tests for a dependence between the Src and Dst instructions.
319 /// Returns NULL if no dependence; otherwise, returns a Dependence (or a
320 /// FullDependence) with as much information as can be gleaned. By default,
321 /// the dependence test collects a set of runtime assumptions that cannot be
322 /// solved at compilation time. By default UnderRuntimeAssumptions is false
323 /// for a safe approximation of the dependence relation that does not
324 /// require runtime checks.
325 LLVM_ABI std::unique_ptr<Dependence>
327 bool UnderRuntimeAssumptions = false);
328
329 Function *getFunction() const { return F; }
330
331private:
332 const AnalysisOptions &Opts;
333 AAResults *AA;
334 ScalarEvolution *SE;
335 LoopInfo *LI;
336 Function *F;
337
338 SmallPtrSet<const MDNode *, 4> LoopAliasScopes;
339 SmallPtrSet<const Loop *, 8> AlreadyCheckedLoops;
340
341 void updateLoopAliasScopes(const Loop *L);
342
343 /// Subscript - This private struct represents a pair of subscripts from
344 /// a pair of potentially multi-dimensional array references. We use a
345 /// vector of them to guide subscript partitioning.
346 struct Subscript {
347 const SCEV *Src;
348 const SCEV *Dst;
349 enum ClassificationKind { ZIV, SIV, RDIV, MIV, NonLinear } Classification;
350 SmallBitVector Loops;
351 };
352
353 struct CoefficientInfo {
354 const SCEV *SrcCoeff;
355 const SCEV *DstCoeff;
356 const SCEV *MaxIterIndex;
357 };
358
359 struct BoundInfo {
360 const SCEV *Upper[8];
361 const SCEV *Lower[8];
362 unsigned char Direction;
363 unsigned char DirSet;
364 };
365
366 /// Returns true if two loops have the Same iteration Space and Depth. To be
367 /// more specific, two loops have SameSD if they are in the same nesting
368 /// depth and have the same backedge count. SameSD stands for Same iteration
369 /// Space and Depth.
370 bool haveSameSD(const Loop *SrcLoop, const Loop *DstLoop) const;
371
372 /// establishNestingLevels - Examines the loop nesting of the Src and Dst
373 /// instructions and establishes their shared loops. Sets the variables
374 /// CommonLevels, SrcLevels, and MaxLevels.
375 /// The source and destination instructions needn't be contained in the same
376 /// loop. The routine establishNestingLevels finds the level of most deeply
377 /// nested loop that contains them both, CommonLevels. An instruction that's
378 /// not contained in a loop is at level = 0. MaxLevels is equal to the level
379 /// of the source plus the level of the destination, minus CommonLevels.
380 /// This lets us allocate vectors MaxLevels in length, with room for every
381 /// distinct loop referenced in both the source and destination subscripts.
382 /// The variable SrcLevels is the nesting depth of the source instruction.
383 /// It's used to help calculate distinct loops referenced by the destination.
384 /// Here's the map from loops to levels:
385 /// 0 - unused
386 /// 1 - outermost common loop
387 /// ... - other common loops
388 /// CommonLevels - innermost common loop
389 /// ... - loops containing Src but not Dst
390 /// SrcLevels - innermost loop containing Src but not Dst
391 /// ... - loops containing Dst but not Src
392 /// MaxLevels - innermost loop containing Dst but not Src
393 /// Consider the follow code fragment:
394 /// for (a = ...) {
395 /// for (b = ...) {
396 /// for (c = ...) {
397 /// for (d = ...) {
398 /// A[] = ...;
399 /// }
400 /// }
401 /// for (e = ...) {
402 /// for (f = ...) {
403 /// for (g = ...) {
404 /// ... = A[];
405 /// }
406 /// }
407 /// }
408 /// }
409 /// }
410 /// If we're looking at the possibility of a dependence between the store
411 /// to A (the Src) and the load from A (the Dst), we'll note that they
412 /// have 2 loops in common, so CommonLevels will equal 2 and the direction
413 /// vector for Result will have 2 entries. SrcLevels = 4 and MaxLevels = 7.
414 /// A map from loop names to level indices would look like
415 /// a - 1
416 /// b - 2 = CommonLevels
417 /// c - 3
418 /// d - 4 = SrcLevels
419 /// e - 5
420 /// f - 6
421 /// g - 7 = MaxLevels
422 /// SameSDLevels counts the number of levels after common levels that are
423 /// not common but have the same iteration space and depth. Internally this
424 /// is checked using haveSameSD. Assume that in this code fragment, levels c
425 /// and e have the same iteration space and depth, but levels d and f does
426 /// not. Then SameSDLevels is set to 1. In that case the level numbers for the
427 /// previous code look like
428 /// a - 1
429 /// b - 2
430 /// c,e - 3 = CommonLevels
431 /// d - 4 = SrcLevels
432 /// f - 5
433 /// g - 6 = MaxLevels
434 void establishNestingLevels(const Instruction *Src, const Instruction *Dst);
435
436 unsigned CommonLevels, SrcLevels, MaxLevels, SameSDLevels;
437
438 /// mapSrcLoop - Given one of the loops containing the source, return
439 /// its level index in our numbering scheme.
440 unsigned mapSrcLoop(const Loop *SrcLoop) const;
441
442 /// mapDstLoop - Given one of the loops containing the destination,
443 /// return its level index in our numbering scheme.
444 unsigned mapDstLoop(const Loop *DstLoop) const;
445
446 /// isLoopInvariant - Returns true if Expression is loop invariant
447 /// in LoopNest.
448 bool isLoopInvariant(const SCEV *Expression, const Loop *LoopNest) const;
449
450 /// collectCommonLoops - Finds the set of loops from the LoopNest that
451 /// have a level <= CommonLevels and are referred to by the SCEV Expression.
452 void collectCommonLoops(const SCEV *Expression, const Loop *LoopNest,
453 SmallBitVector &Loops) const;
454
455 /// checkSrcSubscript - Examines the SCEV Src, returning true iff it's
456 /// linear. Collect the set of loops mentioned by Src.
457 bool checkSrcSubscript(const SCEV *Src, const Loop *LoopNest,
458 SmallBitVector &Loops);
459
460 /// checkDstSubscript - Examines the SCEV Dst, returning true iff it's
461 /// linear. Collect the set of loops mentioned by Dst.
462 bool checkDstSubscript(const SCEV *Dst, const Loop *LoopNest,
463 SmallBitVector &Loops);
464
465 /// collectUpperBound - All subscripts are the same type (on my machine,
466 /// an i64). The loop bound may be a smaller type. collectUpperBound
467 /// find the bound, if available, and zero extends it to the Type T.
468 /// (I zero extend since the bound should always be >= 0.)
469 /// If no upper bound is available, return NULL.
470 const SCEV *collectUpperBound(const Loop *l, Type *T) const;
471
472 /// collectNonNegativeConstantUpperBound - Calls collectUpperBound(), then
473 /// attempts to cast it to APInt. If the cast fails, or the value is negative,
474 /// returns std::nullopt.
475 std::optional<APInt> collectNonNegativeConstantUpperBound(const Loop *L,
476 Type *T) const;
477
478 /// classifyPair - Examines the subscript pair (the Src and Dst SCEVs)
479 /// and classifies it as either ZIV, SIV, RDIV, MIV, or Nonlinear.
480 /// Collects the associated loops in a set.
481 Subscript::ClassificationKind
482 classifyPair(const SCEV *Src, const Loop *SrcLoopNest, const SCEV *Dst,
483 const Loop *DstLoopNest, SmallBitVector &Loops);
484
485 /// testZIV - Tests the ZIV subscript pair (Src and Dst) for dependence.
486 /// Returns true if any possible dependence is disproved.
487 /// If there might be a dependence, returns false.
488 /// If the dependence isn't proven to exist,
489 bool testZIV(const SCEV *Src, const SCEV *Dst, FullDependence &Result) const;
490
491 /// testSIV - Tests the SIV subscript pair (Src and Dst) for dependence.
492 /// Things of the form [c1 + a1*i] and [c2 + a2*j], where
493 /// i and j are induction variables, c1 and c2 are loop invariant,
494 /// and a1 and a2 are constant.
495 /// Returns true if any possible dependence is disproved.
496 /// If there might be a dependence, returns false.
497 /// Sets appropriate direction vector entry and, when possible,
498 /// the distance vector entry.
499 /// If the dependence isn't proven to exist,
500 bool testSIV(const SCEV *Src, const SCEV *Dst, unsigned &Level,
501 FullDependence &Result, bool UnderRuntimeAssumptions);
502
503 /// testRDIV - Tests the RDIV subscript pair (Src and Dst) for dependence.
504 /// Things of the form [c1 + a1*i] and [c2 + a2*j]
505 /// where i and j are induction variables, c1 and c2 are loop invariant,
506 /// and a1 and a2 are constant.
507 /// With minor algebra, this test can also be used for things like
508 /// [c1 + a1*i + a2*j][c2].
509 /// Returns true if any possible dependence is disproved.
510 /// If there might be a dependence, returns false.
511 bool testRDIV(const SCEV *Src, const SCEV *Dst, FullDependence &Result) const;
512
513 /// testMIV - Tests the MIV subscript pair (Src and Dst) for dependence.
514 /// Returns true if dependence disproved.
515 /// Can sometimes refine direction vectors.
516 bool testMIV(const SCEV *Src, const SCEV *Dst, const SmallBitVector &Loops,
517 FullDependence &Result) const;
518
519 /// strongSIVtest - Tests the strong SIV subscript pair (\p Src and \p Dst)
520 /// for dependence.
521 /// Things of the form [c1 + a*i] and [c2 + a*i],
522 /// where i is an induction variable, c1 and c2 are loop invariant,
523 /// and a is a constant
524 /// Returns true if any possible dependence is disproved.
525 /// If there might be a dependence, returns false.
526 /// Sets appropriate direction and distance.
527 bool strongSIVtest(const SCEVAddRecExpr *Src, const SCEVAddRecExpr *Dst,
528 unsigned Level, FullDependence &Result,
529 bool UnderRuntimeAssumptions);
530
531 /// weakCrossingSIVtest - Tests the weak-crossing SIV subscript pair
532 /// (Src and Dst) for dependence.
533 /// Things of the form [c1 + a*i] and [c2 - a*i],
534 /// where i is an induction variable, c1 and c2 are loop invariant,
535 /// and a is a constant.
536 /// Returns true if any possible dependence is disproved.
537 /// If there might be a dependence, returns false.
538 /// Sets appropriate direction entry.
539 bool weakCrossingSIVtest(const SCEVAddRecExpr *Src, const SCEVAddRecExpr *Dst,
540 unsigned Level, FullDependence &Result) const;
541
542 /// ExactSIVtest - Tests the SIV subscript pair
543 /// (Src and Dst) for dependence.
544 /// Things of the form [c1 + a1*i] and [c2 + a2*i],
545 /// where i is an induction variable, c1 and c2 are loop invariant,
546 /// and a1 and a2 are constant.
547 /// Returns true if any possible dependence is disproved.
548 /// If there might be a dependence, returns false.
549 /// Sets appropriate direction entry.
550 bool exactSIVtest(const SCEVAddRecExpr *Src, const SCEVAddRecExpr *Dst,
551 unsigned Level, FullDependence &Result) const;
552
553 /// weakZeroSIVtestImpl - Core implementation for weakZeroSrcSIVtest and
554 /// weakZeroDstSIVtest.
555 bool weakZeroSIVtestImpl(const SCEVAddRecExpr *AR, const SCEV *Const,
556 unsigned Level, FullDependence &Result) const;
557
558 /// weakZeroSrcSIVtest - Tests the weak-zero SIV subscript pair
559 /// (Src and Dst) for dependence.
560 /// Things of the form [c1] and [c2 + a*i],
561 /// where i is an induction variable, c1 and c2 are loop invariant,
562 /// and a is a constant. See also weakZeroDstSIVtest.
563 /// Returns true if any possible dependence is disproved.
564 /// If there might be a dependence, returns false.
565 /// Sets appropriate direction entry.
566 bool weakZeroSrcSIVtest(const SCEV *SrcConst, const SCEVAddRecExpr *Dst,
567 unsigned Level, FullDependence &Result) const;
568
569 /// weakZeroDstSIVtest - Tests the weak-zero SIV subscript pair
570 /// (Src and Dst) for dependence.
571 /// Things of the form [c1 + a*i] and [c2],
572 /// where i is an induction variable, c1 and c2 are loop invariant,
573 /// and a is a constant. See also weakZeroSrcSIVtest.
574 /// Returns true if any possible dependence is disproved.
575 /// If there might be a dependence, returns false.
576 /// Sets appropriate direction entry.
577 bool weakZeroDstSIVtest(const SCEVAddRecExpr *Src, const SCEV *DstConst,
578 unsigned Level, FullDependence &Result) const;
579
580 /// exactRDIVtest - Tests the RDIV subscript pair for dependence.
581 /// Things of the form [c1 + a*i] and [c2 + b*j],
582 /// where i and j are induction variable, c1 and c2 are loop invariant,
583 /// and a and b are constants.
584 /// Returns true if any possible dependence is disproved.
585 /// Works in some cases that symbolicRDIVtest doesn't,
586 /// and vice versa.
587 bool exactRDIVtest(const SCEVAddRecExpr *Src, const SCEVAddRecExpr *Dst,
588 FullDependence &Result) const;
589
590 /// exactTestImpl - Core implementation shared by the Exact SIV test and the
591 /// Exact RDIV test. Returns true if any possible dependence is disproved. If
592 /// \p Level is provided, this function will also attempt to explore
593 /// directions and refine \p Result for the given level.
594 bool exactTestImpl(const SCEVAddRecExpr *Src, const SCEVAddRecExpr *Dst,
595 FullDependence &Result,
596 std::optional<unsigned> Level) const;
597
598 /// gcdMIVtest - Tests an MIV subscript pair for dependence.
599 /// Returns true if any possible dependence is disproved.
600 /// Can sometimes disprove the equal direction for 1 or more loops.
601 // Can handle some symbolics that even the SIV tests don't get,
602 /// so we use it as a backup for everything.
603 bool gcdMIVtest(const SCEV *Src, const SCEV *Dst,
604 FullDependence &Result) const;
605
606 /// banerjeeMIVtest - Tests an MIV subscript pair for dependence.
607 /// Returns true if any possible dependence is disproved.
608 /// Computes directions.
609 bool banerjeeMIVtest(const SCEV *Src, const SCEV *Dst,
610 const SmallBitVector &Loops,
611 FullDependence &Result) const;
612
613 /// collectCoeffInfo - Walks through the subscript, collecting each
614 /// coefficient and the associated maximum iteration index in the
615 /// widened analysis type. Returns the widened constant term.
616 const SCEV *collectCoeffInfo(const SCEV *Subscript, bool SrcFlag,
617 Type *WideType,
619
620 /// Given \p Expr of the form
621 ///
622 /// c_0*X_0*i_0 + c_1*X_1*i_1 + ...c_n*X_n*i_n + C
623 ///
624 /// compute
625 ///
626 /// RunningGCD = gcd(RunningGCD, c_0, c_1, ..., c_n)
627 ///
628 /// where c_0, c_1, ..., and c_n are the constant values. The result is stored
629 /// in \p RunningGCD. Also, the initial value of \p RunningGCD affects the
630 /// result. If we find a term like (c_k * X_k * i_k), where i_k is the
631 /// induction variable of \p CurLoop, c_k is stored in \p CurLoopCoeff and not
632 /// included in the GCD computation. Returns nullptr if we fail to find a
633 /// constant coefficient for some loop, e.g., when a term like (X+Y)*i is
634 /// present. Otherwise returns the remaining constant term C.
635 const SCEV *accumulateCoefficientsGCD(const SCEV *Expr, const Loop *CurLoop,
636 const SCEV *&CurLoopCoeff,
637 APInt &RunningGCD) const;
638
639 /// getLowerBound - Looks through all the bounds info and
640 /// computes the lower bound given the current direction settings
641 /// at each level.
642 const SCEV *getLowerBound(ArrayRef<BoundInfo> Bound) const;
643
644 /// getUpperBound - Looks through all the bounds info and
645 /// computes the upper bound given the current direction settings
646 /// at each level.
647 const SCEV *getUpperBound(ArrayRef<BoundInfo> Bound) const;
648
649 /// exploreDirections - Hierarchically expands the direction vector
650 /// search space, combining the directions of discovered dependences
651 /// in the DirSet field of Bound. Returns the number of distinct
652 /// dependences discovered. If the dependence is disproved,
653 /// it will return 0.
654 unsigned exploreDirections(unsigned Level, MutableArrayRef<BoundInfo> Bound,
655 const SmallBitVector &Loops, const SCEV *Delta,
656 const FullDependence &Result) const;
657
658 /// testBounds - Returns true when the current bounds may be feasible
659 /// or their feasibility is unknown.
660 bool testBounds(unsigned char DirKind, unsigned Level,
661 MutableArrayRef<BoundInfo> Bound, const SCEV *Delta) const;
662
663 /// findBoundsALL - Computes the upper and lower bounds for level K
664 /// using the * direction. Records them in Bound.
665 void findBoundsALL(ArrayRef<CoefficientInfo> CI,
666 MutableArrayRef<BoundInfo> Bound, unsigned K) const;
667
668 /// findBoundsLT - Computes the upper and lower bounds for level K
669 /// using the < direction. Records them in Bound.
670 void findBoundsLT(ArrayRef<CoefficientInfo> CI,
671 MutableArrayRef<BoundInfo> Bound, unsigned K) const;
672
673 /// findBoundsGT - Computes the upper and lower bounds for level K
674 /// using the > direction. Records them in Bound.
675 void findBoundsGT(ArrayRef<CoefficientInfo> CI,
676 MutableArrayRef<BoundInfo> Bound, unsigned K) const;
677
678 /// findBoundsEQ - Computes the upper and lower bounds for level K
679 /// using the = direction. Records them in Bound.
680 void findBoundsEQ(ArrayRef<CoefficientInfo> CI,
681 MutableArrayRef<BoundInfo> Bound, unsigned K) const;
682
683 /// Given a linear access function, tries to recover subscripts
684 /// for each dimension of the array element access.
685 bool tryDelinearize(Instruction *Src, Instruction *Dst,
686 SmallVectorImpl<Subscript> &Pair);
687
688 /// Tries to delinearize \p Src and \p Dst access functions for a fixed size
689 /// multi-dimensional array. Calls delinearizeFixedSizeArray() to delinearize
690 /// \p Src and \p Dst separately,
691 bool tryDelinearizeFixedSize(Instruction *Src, Instruction *Dst,
692 const SCEV *SrcAccessFn, const SCEV *DstAccessFn,
693 SmallVectorImpl<const SCEV *> &SrcSubscripts,
694 SmallVectorImpl<const SCEV *> &DstSubscripts);
695
696 /// Tries to delinearize access function for a multi-dimensional array with
697 /// symbolic runtime sizes.
698 /// Returns true upon success and false otherwise.
699 bool
700 tryDelinearizeParametricSize(Instruction *Src, Instruction *Dst,
701 const SCEV *SrcAccessFn, const SCEV *DstAccessFn,
702 SmallVectorImpl<const SCEV *> &SrcSubscripts,
703 SmallVectorImpl<const SCEV *> &DstSubscripts);
704
705 /// checkSubscript - Helper function for checkSrcSubscript and
706 /// checkDstSubscript to avoid duplicate code
707 bool checkSubscript(const SCEV *Expr, const Loop *LoopNest,
708 SmallBitVector &Loops, bool IsSrc);
709}; // class DependenceInfo
710
711/// AnalysisPass to compute dependence information in a function
712class DependenceAnalysis : public AnalysisInfoMixin<DependenceAnalysis> {
713public:
716
717private:
720}; // class DependenceAnalysis
721
722/// Printer pass to dump DA results.
724 : public RequiredPassInfoMixin<DependenceAnalysisPrinterPass> {
725 DependenceAnalysisPrinterPass(raw_ostream &OS, bool NormalizeResults = false)
726 : OS(OS), NormalizeResults(NormalizeResults) {}
727
729
730private:
731 raw_ostream &OS;
732 bool NormalizeResults;
733}; // class DependenceAnalysisPrinterPass
734
735/// Legacy pass manager pass to access dependence information
737public:
738 static char ID; // Class identification, replacement for typeinfo
740
741 bool runOnFunction(Function &F) override;
742 void releaseMemory() override;
743 void getAnalysisUsage(AnalysisUsage &) const override;
744 void print(raw_ostream &, const Module * = nullptr) const override;
745 DependenceInfo &getDI() const;
746
747private:
748 std::unique_ptr<DependenceInfo> info;
749}; // class DependenceAnalysisWrapperPass
750
751/// createDependenceAnalysisPass - This creates an instance of the
752/// DependenceAnalysis wrapper pass.
754
755} // namespace llvm
756
757#endif
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define LLVM_ABI
Definition Compiler.h:211
static bool runOnFunction(Function &F, bool PostInlining)
Hexagon Hardware Loops
This header defines various interfaces for pass management in LLVM.
#define F(x, y, z)
Definition MD5.cpp:54
#define T
static bool isInput(const ArrayRef< StringRef > &Prefixes, StringRef Arg)
Definition OptTable.cpp:143
FunctionAnalysisManager FAM
This file implements the SmallBitVector class.
This file defines the SmallPtrSet class.
Represent the analysis usage information of a pass.
Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:40
void getAnalysisUsage(AnalysisUsage &) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
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.
LLVM_ABI Result run(Function &F, FunctionAnalysisManager &FAM)
DependenceInfo - This class is the main dependence-analysis driver.
LLVM_ABI bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle transitive invalidation when the cached analysis results go away.
Function * getFunction() const
LLVM_ABI DependenceInfo(Function *F, AAResults *AA, ScalarEvolution *SE, LoopInfo *LI)
LLVM_ABI std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool UnderRuntimeAssumptions=false)
depends - Tests for a dependence between the Src and Dst instructions.
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.
friend class DependenceInfo
Dependence(Instruction *Source, Instruction *Destination, const SCEVUnionPredicate &A)
Dependence(Dependence &&)=default
bool isUnordered() const
isUnordered - Returns true if dependence is Input
SCEVUnionPredicate getRuntimeAssumptions() const
getRuntimeAssumptions - Returns the runtime assumptions under which this Dependence relation is valid...
virtual bool isConfused() const
isConfused - Returns true if this dependence is confused (the compiler understands nothing and makes ...
virtual unsigned getSameSDLevels() const
getSameSDLevels - Returns the number of separate SameSD loops surrounding the source and destination ...
virtual const SCEV * getDistance(unsigned Level, bool SameSD=false) const
getDistance - Returns the distance (or NULL) associated with a particular common or SameSD level.
virtual void negate(ScalarEvolution &SE)
Negate the dependence by swapping the source and destination, and reversing the direction and distanc...
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.
virtual unsigned getDirection(unsigned Level, bool SameSD=false) const
getDirection - Returns the direction associated with a particular common or SameSD level.
bool isFlow() const
isFlow - Returns true if this is a flow (aka true) dependence.
virtual ~Dependence()=default
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.
virtual bool inSameSDLoops(unsigned Level) const
inSameSDLoops - Returns true if this level is an SameSD level, i.e., performed across two separate lo...
FullDependence(Instruction *Source, Instruction *Destination, const SCEVUnionPredicate &Assumes, bool PossiblyLoopIndependent, unsigned Levels)
bool isConfused() const override
isConfused - Returns true if this dependence is confused (the compiler understands nothing and makes ...
DVEntry getDVEntry(unsigned Level, bool IsSameSD) const
getDVEntry - Returns the DV entry associated with a regular or a SameSD level.
bool isLoopIndependent() const override
isLoopIndependent - Returns true if this is a loop-independent dependence.
unsigned getSameSDLevels() const override
getSameSDLevels - Returns the number of separate SameSD loops surrounding the source and destination ...
unsigned getLevels() const override
getLevels - Returns the number of common loops surrounding the source and destination of the dependen...
FunctionPass class - This class is used to implement most global optimizations.
Definition Pass.h:312
FunctionPass(char &pid)
Definition Pass.h:314
Represents a single loop in the control flow graph.
Definition LoopInfo.h:40
Metadata node.
Definition Metadata.h:1081
A Module instance is used to store all the information related to an LLVM module.
Definition Module.h:68
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
This class represents a constant integer value.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
This class represents an analyzed expression in the program.
The main scalar evolution driver.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
Abstract Attribute helper functions.
Definition Attributor.h:166
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
MutableArrayRef(T &OneElt) -> MutableArrayRef< T >
ArrayRef(const T &OneElt) -> ArrayRef< T >
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI FunctionPass * createDependenceAnalysisWrapperPass()
createDependenceAnalysisPass - This creates an instance of the DependenceAnalysis wrapper pass.
A CRTP mix-in that provides informational APIs needed for analysis passes.
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition Analysis.h:29
DependenceAnalysisPrinterPass(raw_ostream &OS, bool NormalizeResults=false)
LLVM_ABI 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 for passes that should not be skipped.