LLVM 22.0.0git
DependenceAnalysis.cpp
Go to the documentation of this file.
1//===-- DependenceAnalysis.cpp - DA Implementation --------------*- 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 (incomplete) implementation of the approach
11// 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// Currently, the implementation cannot propagate constraints between
22// coupled RDIV subscripts and lacks a multi-subscript MIV test.
23// Both of these are conservative weaknesses;
24// that is, not a source of correctness problems.
25//
26// Since Clang linearizes some array subscripts, the dependence
27// analysis is using SCEV->delinearize to recover the representation of multiple
28// subscripts, and thus avoid the more expensive and less precise MIV tests. The
29// delinearization is controlled by the flag -da-delinearize.
30//
31// We should pay some careful attention to the possibility of integer overflow
32// in the implementation of the various tests. This could happen with Add,
33// Subtract, or Multiply, with both APInt's and SCEV's.
34//
35// Some non-linear subscript pairs can be handled by the GCD test
36// (and perhaps other tests).
37// Should explore how often these things occur.
38//
39// Finally, it seems like certain test cases expose weaknesses in the SCEV
40// simplification, especially in the handling of sign and zero extensions.
41// It could be useful to spend time exploring these.
42//
43// Please note that this is work in progress and the interface is subject to
44// change.
45//
46//===----------------------------------------------------------------------===//
47// //
48// In memory of Ken Kennedy, 1945 - 2007 //
49// //
50//===----------------------------------------------------------------------===//
51
53#include "llvm/ADT/Statistic.h"
61#include "llvm/IR/Module.h"
64#include "llvm/Support/Debug.h"
67
68using namespace llvm;
69
70#define DEBUG_TYPE "da"
71
72//===----------------------------------------------------------------------===//
73// statistics
74
75STATISTIC(TotalArrayPairs, "Array pairs tested");
76STATISTIC(SeparableSubscriptPairs, "Separable subscript pairs");
77STATISTIC(CoupledSubscriptPairs, "Coupled subscript pairs");
78STATISTIC(NonlinearSubscriptPairs, "Nonlinear subscript pairs");
79STATISTIC(ZIVapplications, "ZIV applications");
80STATISTIC(ZIVindependence, "ZIV independence");
81STATISTIC(StrongSIVapplications, "Strong SIV applications");
82STATISTIC(StrongSIVsuccesses, "Strong SIV successes");
83STATISTIC(StrongSIVindependence, "Strong SIV independence");
84STATISTIC(WeakCrossingSIVapplications, "Weak-Crossing SIV applications");
85STATISTIC(WeakCrossingSIVsuccesses, "Weak-Crossing SIV successes");
86STATISTIC(WeakCrossingSIVindependence, "Weak-Crossing SIV independence");
87STATISTIC(ExactSIVapplications, "Exact SIV applications");
88STATISTIC(ExactSIVsuccesses, "Exact SIV successes");
89STATISTIC(ExactSIVindependence, "Exact SIV independence");
90STATISTIC(WeakZeroSIVapplications, "Weak-Zero SIV applications");
91STATISTIC(WeakZeroSIVsuccesses, "Weak-Zero SIV successes");
92STATISTIC(WeakZeroSIVindependence, "Weak-Zero SIV independence");
93STATISTIC(ExactRDIVapplications, "Exact RDIV applications");
94STATISTIC(ExactRDIVindependence, "Exact RDIV independence");
95STATISTIC(SymbolicRDIVapplications, "Symbolic RDIV applications");
96STATISTIC(SymbolicRDIVindependence, "Symbolic RDIV independence");
97STATISTIC(DeltaApplications, "Delta applications");
98STATISTIC(DeltaSuccesses, "Delta successes");
99STATISTIC(DeltaIndependence, "Delta independence");
100STATISTIC(DeltaPropagations, "Delta propagations");
101STATISTIC(GCDapplications, "GCD applications");
102STATISTIC(GCDsuccesses, "GCD successes");
103STATISTIC(GCDindependence, "GCD independence");
104STATISTIC(BanerjeeApplications, "Banerjee applications");
105STATISTIC(BanerjeeIndependence, "Banerjee independence");
106STATISTIC(BanerjeeSuccesses, "Banerjee successes");
107STATISTIC(SameSDLoopsCount, "Loops with Same iteration Space and Depth");
108
109static cl::opt<bool>
110 Delinearize("da-delinearize", cl::init(true), cl::Hidden,
111 cl::desc("Try to delinearize array references."));
113 "da-disable-delinearization-checks", cl::Hidden,
114 cl::desc(
115 "Disable checks that try to statically verify validity of "
116 "delinearized subscripts. Enabling this option may result in incorrect "
117 "dependence vectors for languages that allow the subscript of one "
118 "dimension to underflow or overflow into another dimension."));
119
121 "da-miv-max-level-threshold", cl::init(7), cl::Hidden,
122 cl::desc("Maximum depth allowed for the recursive algorithm used to "
123 "explore MIV direction vectors."));
124
125namespace {
126
127/// Types of dependence test routines.
128enum class DependenceTestType {
129 All,
130 StrongSIV,
131 WeakCrossingSIV,
132 ExactSIV,
133 WeakZeroSIV,
134 ExactRDIV,
135 SymbolicRDIV,
136 GCDMIV,
137 BanerjeeMIV,
138};
139
140} // anonymous namespace
141
143 "da-enable-dependence-test", cl::init(DependenceTestType::All),
145 cl::desc("Run only specified dependence test routine and disable others. "
146 "The purpose is mainly to exclude the influence of other "
147 "dependence test routines in regression tests. If set to All, all "
148 "dependence test routines are enabled."),
149 cl::values(clEnumValN(DependenceTestType::All, "all",
150 "Enable all dependence test routines."),
151 clEnumValN(DependenceTestType::StrongSIV, "strong-siv",
152 "Enable only Strong SIV test."),
153 clEnumValN(DependenceTestType::WeakCrossingSIV,
154 "weak-crossing-siv",
155 "Enable only Weak-Crossing SIV test."),
156 clEnumValN(DependenceTestType::ExactSIV, "exact-siv",
157 "Enable only Exact SIV test."),
158 clEnumValN(DependenceTestType::WeakZeroSIV, "weak-zero-siv",
159 "Enable only Weak-Zero SIV test."),
160 clEnumValN(DependenceTestType::ExactRDIV, "exact-rdiv",
161 "Enable only Exact RDIV test."),
162 clEnumValN(DependenceTestType::SymbolicRDIV, "symbolic-rdiv",
163 "Enable only Symbolic RDIV test."),
164 clEnumValN(DependenceTestType::GCDMIV, "gcd-miv",
165 "Enable only GCD MIV test."),
166 clEnumValN(DependenceTestType::BanerjeeMIV, "banerjee-miv",
167 "Enable only Banerjee MIV test.")));
168
169// TODO: This flag is disabled by default because it is still under development.
170// Enable it or delete this flag when the feature is ready.
172 "da-enable-monotonicity-check", cl::init(false), cl::Hidden,
173 cl::desc("Check if the subscripts are monotonic. If it's not, dependence "
174 "is reported as unknown."));
175
177 "da-dump-monotonicity-report", cl::init(false), cl::Hidden,
178 cl::desc(
179 "When printing analysis, dump the results of monotonicity checks."));
180
181//===----------------------------------------------------------------------===//
182// basics
183
186 auto &AA = FAM.getResult<AAManager>(F);
187 auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);
188 auto &LI = FAM.getResult<LoopAnalysis>(F);
189 return DependenceInfo(&F, &AA, &SE, &LI);
190}
191
192AnalysisKey DependenceAnalysis::Key;
193
195 "Dependence Analysis", true, true)
201
203
206
210
212 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
213 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
214 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
215 info.reset(new DependenceInfo(&F, &AA, &SE, &LI));
216 return false;
217}
218
220
222
229
230namespace {
231
232/// The property of monotonicity of a SCEV. To define the monotonicity, assume
233/// a SCEV defined within N-nested loops. Let i_k denote the iteration number
234/// of the k-th loop. Then we can regard the SCEV as an N-ary function:
235///
236/// F(i_1, i_2, ..., i_N)
237///
238/// The domain of i_k is the closed range [0, BTC_k], where BTC_k is the
239/// backedge-taken count of the k-th loop.
240///
241/// A function F is said to be "monotonically increasing with respect to the
242/// k-th loop" if x <= y implies the following condition:
243///
244/// F(i_1, ..., i_{k-1}, x, i_{k+1}, ..., i_N) <=
245/// F(i_1, ..., i_{k-1}, y, i_{k+1}, ..., i_N)
246///
247/// where i_1, ..., i_{k-1}, i_{k+1}, ..., i_N, x, and y are elements of their
248/// respective domains.
249///
250/// Likewise F is "monotonically decreasing with respect to the k-th loop"
251/// if x <= y implies
252///
253/// F(i_1, ..., i_{k-1}, x, i_{k+1}, ..., i_N) >=
254/// F(i_1, ..., i_{k-1}, y, i_{k+1}, ..., i_N)
255///
256/// A function F that is monotonically increasing or decreasing with respect to
257/// the k-th loop is simply called "monotonic with respect to k-th loop".
258///
259/// A function F is said to be "multivariate monotonic" when it is monotonic
260/// with respect to all of the N loops.
261///
262/// Since integer comparison can be either signed or unsigned, we need to
263/// distinguish monotonicity in the signed sense from that in the unsigned
264/// sense. Note that the inequality "x <= y" merely indicates loop progression
265/// and is not affected by the difference between signed and unsigned order.
266///
267/// Currently we only consider monotonicity in a signed sense.
268enum class SCEVMonotonicityType {
269 /// We don't know anything about the monotonicity of the SCEV.
270 Unknown,
271
272 /// The SCEV is loop-invariant with respect to the outermost loop. In other
273 /// words, the function F corresponding to the SCEV is a constant function.
274 Invariant,
275
276 /// The function F corresponding to the SCEV is multivariate monotonic in a
277 /// signed sense. Note that the multivariate monotonic function may also be a
278 /// constant function. The order employed in the definition of monotonicity
279 /// is not strict order.
280 MultivariateSignedMonotonic,
281};
282
283struct SCEVMonotonicity {
284 SCEVMonotonicity(SCEVMonotonicityType Type,
285 const SCEV *FailurePoint = nullptr);
286
287 SCEVMonotonicityType getType() const { return Type; }
288
289 const SCEV *getFailurePoint() const { return FailurePoint; }
290
291 bool isUnknown() const { return Type == SCEVMonotonicityType::Unknown; }
292
293 void print(raw_ostream &OS, unsigned Depth) const;
294
295private:
296 SCEVMonotonicityType Type;
297
298 /// The subexpression that caused Unknown. Mainly for debugging purpose.
299 const SCEV *FailurePoint;
300};
301
302/// Check the monotonicity of a SCEV. Since dependence tests (SIV, MIV, etc.)
303/// assume that subscript expressions are (multivariate) monotonic, we need to
304/// verify this property before applying those tests. Violating this assumption
305/// may cause them to produce incorrect results.
306struct SCEVMonotonicityChecker
307 : public SCEVVisitor<SCEVMonotonicityChecker, SCEVMonotonicity> {
308
309 SCEVMonotonicityChecker(ScalarEvolution *SE) : SE(SE) {}
310
311 /// Check the monotonicity of \p Expr. \p Expr must be integer type. If \p
312 /// OutermostLoop is not null, \p Expr must be defined in \p OutermostLoop or
313 /// one of its nested loops.
314 SCEVMonotonicity checkMonotonicity(const SCEV *Expr,
315 const Loop *OutermostLoop);
316
317private:
318 ScalarEvolution *SE;
319
320 /// The outermost loop that DA is analyzing.
321 const Loop *OutermostLoop;
322
323 /// A helper to classify \p Expr as either Invariant or Unknown.
324 SCEVMonotonicity invariantOrUnknown(const SCEV *Expr);
325
326 /// Return true if \p Expr is loop-invariant with respect to the outermost
327 /// loop.
328 bool isLoopInvariant(const SCEV *Expr) const;
329
330 /// A helper to create an Unknown SCEVMonotonicity.
331 SCEVMonotonicity createUnknown(const SCEV *FailurePoint) {
332 return SCEVMonotonicity(SCEVMonotonicityType::Unknown, FailurePoint);
333 }
334
335 SCEVMonotonicity visitAddRecExpr(const SCEVAddRecExpr *Expr);
336
337 SCEVMonotonicity visitConstant(const SCEVConstant *) {
338 return SCEVMonotonicity(SCEVMonotonicityType::Invariant);
339 }
340 SCEVMonotonicity visitVScale(const SCEVVScale *) {
341 return SCEVMonotonicity(SCEVMonotonicityType::Invariant);
342 }
343
344 // TODO: Handle more cases.
345 SCEVMonotonicity visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
346 return invariantOrUnknown(Expr);
347 }
348 SCEVMonotonicity visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
349 return invariantOrUnknown(Expr);
350 }
351 SCEVMonotonicity visitAddExpr(const SCEVAddExpr *Expr) {
352 return invariantOrUnknown(Expr);
353 }
354 SCEVMonotonicity visitMulExpr(const SCEVMulExpr *Expr) {
355 return invariantOrUnknown(Expr);
356 }
357 SCEVMonotonicity visitPtrToIntExpr(const SCEVPtrToIntExpr *Expr) {
358 return invariantOrUnknown(Expr);
359 }
360 SCEVMonotonicity visitTruncateExpr(const SCEVTruncateExpr *Expr) {
361 return invariantOrUnknown(Expr);
362 }
363 SCEVMonotonicity visitUDivExpr(const SCEVUDivExpr *Expr) {
364 return invariantOrUnknown(Expr);
365 }
366 SCEVMonotonicity visitSMaxExpr(const SCEVSMaxExpr *Expr) {
367 return invariantOrUnknown(Expr);
368 }
369 SCEVMonotonicity visitUMaxExpr(const SCEVUMaxExpr *Expr) {
370 return invariantOrUnknown(Expr);
371 }
372 SCEVMonotonicity visitSMinExpr(const SCEVSMinExpr *Expr) {
373 return invariantOrUnknown(Expr);
374 }
375 SCEVMonotonicity visitUMinExpr(const SCEVUMinExpr *Expr) {
376 return invariantOrUnknown(Expr);
377 }
378 SCEVMonotonicity visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Expr) {
379 return invariantOrUnknown(Expr);
380 }
381 SCEVMonotonicity visitUnknown(const SCEVUnknown *Expr) {
382 return invariantOrUnknown(Expr);
383 }
384 SCEVMonotonicity visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {
385 return invariantOrUnknown(Expr);
386 }
387
388 friend struct SCEVVisitor<SCEVMonotonicityChecker, SCEVMonotonicity>;
389};
390
391} // anonymous namespace
392
393// Used to test the dependence analyzer.
394// Looks through the function, noting instructions that may access memory.
395// Calls depends() on every possible pair and prints out the result.
396// Ignores all other instructions.
398 ScalarEvolution &SE, LoopInfo &LI,
399 bool NormalizeResults) {
400 auto *F = DA->getFunction();
401
403 SCEVMonotonicityChecker Checker(&SE);
404 OS << "Monotonicity check:\n";
405 for (Instruction &Inst : instructions(F)) {
406 if (!isa<LoadInst>(Inst) && !isa<StoreInst>(Inst))
407 continue;
409 const Loop *L = LI.getLoopFor(Inst.getParent());
410 const SCEV *PtrSCEV = SE.getSCEVAtScope(Ptr, L);
411 const SCEV *AccessFn = SE.removePointerBase(PtrSCEV);
412 SCEVMonotonicity Mon = Checker.checkMonotonicity(AccessFn, L);
413 OS.indent(2) << "Inst: " << Inst << "\n";
414 OS.indent(4) << "Expr: " << *AccessFn << "\n";
415 Mon.print(OS, 4);
416 }
417 OS << "\n";
418 }
419
420 for (inst_iterator SrcI = inst_begin(F), SrcE = inst_end(F); SrcI != SrcE;
421 ++SrcI) {
422 if (SrcI->mayReadOrWriteMemory()) {
423 for (inst_iterator DstI = SrcI, DstE = inst_end(F); DstI != DstE;
424 ++DstI) {
425 if (DstI->mayReadOrWriteMemory()) {
426 OS << "Src:" << *SrcI << " --> Dst:" << *DstI << "\n";
427 OS << " da analyze - ";
428 if (auto D = DA->depends(&*SrcI, &*DstI,
429 /*UnderRuntimeAssumptions=*/true)) {
430
431#ifndef NDEBUG
432 // Verify that the distance being zero is equivalent to the
433 // direction being EQ.
434 for (unsigned Level = 1; Level <= D->getLevels(); Level++) {
435 const SCEV *Distance = D->getDistance(Level);
436 bool IsDistanceZero = Distance && Distance->isZero();
437 bool IsDirectionEQ =
438 D->getDirection(Level) == Dependence::DVEntry::EQ;
439 assert(IsDistanceZero == IsDirectionEQ &&
440 "Inconsistent distance and direction.");
441 }
442#endif
443
444 // Normalize negative direction vectors if required by clients.
445 if (NormalizeResults && D->normalize(&SE))
446 OS << "normalized - ";
447 D->dump(OS);
448 for (unsigned Level = 1; Level <= D->getLevels(); Level++) {
449 if (D->isSplitable(Level)) {
450 OS << " da analyze - split level = " << Level;
451 OS << ", iteration = " << *DA->getSplitIteration(*D, Level);
452 OS << "!\n";
453 }
454 }
455 } else
456 OS << "none!\n";
457 }
458 }
459 }
460 }
461 SCEVUnionPredicate Assumptions = DA->getRuntimeAssumptions();
462 if (!Assumptions.isAlwaysTrue()) {
463 OS << "Runtime Assumptions:\n";
464 Assumptions.print(OS, 0);
465 }
466}
467
469 const Module *) const {
471 OS, info.get(), getAnalysis<ScalarEvolutionWrapperPass>().getSE(),
472 getAnalysis<LoopInfoWrapperPass>().getLoopInfo(), false);
473}
474
477 OS << "Printing analysis 'Dependence Analysis' for function '" << F.getName()
478 << "':\n";
480 FAM.getResult<ScalarEvolutionAnalysis>(F),
481 FAM.getResult<LoopAnalysis>(F), NormalizeResults);
482 return PreservedAnalyses::all();
483}
484
485//===----------------------------------------------------------------------===//
486// Dependence methods
487
488// Returns true if this is an input dependence.
490 return Src->mayReadFromMemory() && Dst->mayReadFromMemory();
491}
492
493// Returns true if this is an output dependence.
495 return Src->mayWriteToMemory() && Dst->mayWriteToMemory();
496}
497
498// Returns true if this is an flow (aka true) dependence.
499bool Dependence::isFlow() const {
500 return Src->mayWriteToMemory() && Dst->mayReadFromMemory();
501}
502
503// Returns true if this is an anti dependence.
504bool Dependence::isAnti() const {
505 return Src->mayReadFromMemory() && Dst->mayWriteToMemory();
506}
507
508// Returns true if a particular level is scalar; that is,
509// if no subscript in the source or destination mention the induction
510// variable associated with the loop at this level.
511// Leave this out of line, so it will serve as a virtual method anchor
512bool Dependence::isScalar(unsigned level, bool IsSameSD) const { return false; }
513
514//===----------------------------------------------------------------------===//
515// FullDependence methods
516
518 const SCEVUnionPredicate &Assumes,
519 bool PossiblyLoopIndependent,
520 unsigned CommonLevels)
521 : Dependence(Source, Destination, Assumes), Levels(CommonLevels),
522 LoopIndependent(PossiblyLoopIndependent) {
523 Consistent = true;
524 SameSDLevels = 0;
525 if (CommonLevels)
526 DV = std::make_unique<DVEntry[]>(CommonLevels);
527}
528
529// FIXME: in some cases the meaning of a negative direction vector
530// may not be straightforward, e.g.,
531// for (int i = 0; i < 32; ++i) {
532// Src: A[i] = ...;
533// Dst: use(A[31 - i]);
534// }
535// The dependency is
536// flow { Src[i] -> Dst[31 - i] : when i >= 16 } and
537// anti { Dst[i] -> Src[31 - i] : when i < 16 },
538// -- hence a [<>].
539// As long as a dependence result contains '>' ('<>', '<=>', "*"), it
540// means that a reversed/normalized dependence needs to be considered
541// as well. Nevertheless, current isDirectionNegative() only returns
542// true with a '>' or '>=' dependency for ease of canonicalizing the
543// dependency vector, since the reverse of '<>', '<=>' and "*" is itself.
545 for (unsigned Level = 1; Level <= Levels; ++Level) {
546 unsigned char Direction = DV[Level - 1].Direction;
547 if (Direction == Dependence::DVEntry::EQ)
548 continue;
549 if (Direction == Dependence::DVEntry::GT ||
550 Direction == Dependence::DVEntry::GE)
551 return true;
552 return false;
553 }
554 return false;
555}
556
558 if (!isDirectionNegative())
559 return false;
560
561 LLVM_DEBUG(dbgs() << "Before normalizing negative direction vectors:\n";
562 dump(dbgs()););
563 std::swap(Src, Dst);
564 for (unsigned Level = 1; Level <= Levels; ++Level) {
565 unsigned char Direction = DV[Level - 1].Direction;
566 // Reverse the direction vector, this means LT becomes GT
567 // and GT becomes LT.
568 unsigned char RevDirection = Direction & Dependence::DVEntry::EQ;
569 if (Direction & Dependence::DVEntry::LT)
570 RevDirection |= Dependence::DVEntry::GT;
571 if (Direction & Dependence::DVEntry::GT)
572 RevDirection |= Dependence::DVEntry::LT;
573 DV[Level - 1].Direction = RevDirection;
574 // Reverse the dependence distance as well.
575 if (DV[Level - 1].Distance != nullptr)
576 DV[Level - 1].Distance = SE->getNegativeSCEV(DV[Level - 1].Distance);
577 }
578
579 LLVM_DEBUG(dbgs() << "After normalizing negative direction vectors:\n";
580 dump(dbgs()););
581 return true;
582}
583
584// The rest are simple getters that hide the implementation.
585
586// getDirection - Returns the direction associated with a particular common or
587// SameSD level.
588unsigned FullDependence::getDirection(unsigned Level, bool IsSameSD) const {
589 return getDVEntry(Level, IsSameSD).Direction;
590}
591
592// Returns the distance (or NULL) associated with a particular common or
593// SameSD level.
594const SCEV *FullDependence::getDistance(unsigned Level, bool IsSameSD) const {
595 return getDVEntry(Level, IsSameSD).Distance;
596}
597
598// Returns true if a particular regular or SameSD level is scalar; that is,
599// if no subscript in the source or destination mention the induction variable
600// associated with the loop at this level.
601bool FullDependence::isScalar(unsigned Level, bool IsSameSD) const {
602 return getDVEntry(Level, IsSameSD).Scalar;
603}
604
605// Returns true if peeling the first iteration from this regular or SameSD
606// loop level will break this dependence.
607bool FullDependence::isPeelFirst(unsigned Level, bool IsSameSD) const {
608 return getDVEntry(Level, IsSameSD).PeelFirst;
609}
610
611// Returns true if peeling the last iteration from this regular or SameSD
612// loop level will break this dependence.
613bool FullDependence::isPeelLast(unsigned Level, bool IsSameSD) const {
614 return getDVEntry(Level, IsSameSD).PeelLast;
615}
616
617// Returns true if splitting loop will break the dependence.
618bool FullDependence::isSplitable(unsigned Level, bool IsSameSD) const {
619 return getDVEntry(Level, IsSameSD).Splitable;
620}
621
622// inSameSDLoops - Returns true if this level is an SameSD level, i.e.,
623// performed across two separate loop nests that have the Same iteration space
624// and Depth.
625bool FullDependence::inSameSDLoops(unsigned Level) const {
626 assert(0 < Level && Level <= static_cast<unsigned>(Levels) + SameSDLevels &&
627 "Level out of range");
628 return Level > Levels;
629}
630
631//===----------------------------------------------------------------------===//
632// DependenceInfo::Constraint methods
633
634// If constraint is a point <X, Y>, returns X.
635// Otherwise assert.
636const SCEV *DependenceInfo::Constraint::getX() const {
637 assert(Kind == Point && "Kind should be Point");
638 return A;
639}
640
641// If constraint is a point <X, Y>, returns Y.
642// Otherwise assert.
643const SCEV *DependenceInfo::Constraint::getY() const {
644 assert(Kind == Point && "Kind should be Point");
645 return B;
646}
647
648// If constraint is a line AX + BY = C, returns A.
649// Otherwise assert.
650const SCEV *DependenceInfo::Constraint::getA() const {
651 assert((Kind == Line || Kind == Distance) &&
652 "Kind should be Line (or Distance)");
653 return A;
654}
655
656// If constraint is a line AX + BY = C, returns B.
657// Otherwise assert.
658const SCEV *DependenceInfo::Constraint::getB() const {
659 assert((Kind == Line || Kind == Distance) &&
660 "Kind should be Line (or Distance)");
661 return B;
662}
663
664// If constraint is a line AX + BY = C, returns C.
665// Otherwise assert.
666const SCEV *DependenceInfo::Constraint::getC() const {
667 assert((Kind == Line || Kind == Distance) &&
668 "Kind should be Line (or Distance)");
669 return C;
670}
671
672// If constraint is a distance, returns D.
673// Otherwise assert.
674const SCEV *DependenceInfo::Constraint::getD() const {
675 assert(Kind == Distance && "Kind should be Distance");
676 return SE->getNegativeSCEV(C);
677}
678
679// Returns the source loop associated with this constraint.
680const Loop *DependenceInfo::Constraint::getAssociatedSrcLoop() const {
681 assert((Kind == Distance || Kind == Line || Kind == Point) &&
682 "Kind should be Distance, Line, or Point");
683 return AssociatedSrcLoop;
684}
685
686// Returns the destination loop associated with this constraint.
687const Loop *DependenceInfo::Constraint::getAssociatedDstLoop() const {
688 assert((Kind == Distance || Kind == Line || Kind == Point) &&
689 "Kind should be Distance, Line, or Point");
690 return AssociatedDstLoop;
691}
692
693void DependenceInfo::Constraint::setPoint(const SCEV *X, const SCEV *Y,
694 const Loop *CurSrcLoop,
695 const Loop *CurDstLoop) {
696 Kind = Point;
697 A = X;
698 B = Y;
699 AssociatedSrcLoop = CurSrcLoop;
700 AssociatedDstLoop = CurDstLoop;
701}
702
703void DependenceInfo::Constraint::setLine(const SCEV *AA, const SCEV *BB,
704 const SCEV *CC, const Loop *CurSrcLoop,
705 const Loop *CurDstLoop) {
706 Kind = Line;
707 A = AA;
708 B = BB;
709 C = CC;
710 AssociatedSrcLoop = CurSrcLoop;
711 AssociatedDstLoop = CurDstLoop;
712}
713
714void DependenceInfo::Constraint::setDistance(const SCEV *D,
715 const Loop *CurSrcLoop,
716 const Loop *CurDstLoop) {
717 Kind = Distance;
718 A = SE->getOne(D->getType());
719 B = SE->getNegativeSCEV(A);
720 C = SE->getNegativeSCEV(D);
721 AssociatedSrcLoop = CurSrcLoop;
722 AssociatedDstLoop = CurDstLoop;
723}
724
725void DependenceInfo::Constraint::setEmpty() { Kind = Empty; }
726
727void DependenceInfo::Constraint::setAny(ScalarEvolution *NewSE) {
728 SE = NewSE;
729 Kind = Any;
730}
731
732#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
733// For debugging purposes. Dumps the constraint out to OS.
734LLVM_DUMP_METHOD void DependenceInfo::Constraint::dump(raw_ostream &OS) const {
735 if (isEmpty())
736 OS << " Empty\n";
737 else if (isAny())
738 OS << " Any\n";
739 else if (isPoint())
740 OS << " Point is <" << *getX() << ", " << *getY() << ">\n";
741 else if (isDistance())
742 OS << " Distance is " << *getD() << " (" << *getA() << "*X + " << *getB()
743 << "*Y = " << *getC() << ")\n";
744 else if (isLine())
745 OS << " Line is " << *getA() << "*X + " << *getB() << "*Y = " << *getC()
746 << "\n";
747 else
748 llvm_unreachable("unknown constraint type in Constraint::dump");
749}
750#endif
751
752// Updates X with the intersection
753// of the Constraints X and Y. Returns true if X has changed.
754// Corresponds to Figure 4 from the paper
755//
756// Practical Dependence Testing
757// Goff, Kennedy, Tseng
758// PLDI 1991
759bool DependenceInfo::intersectConstraints(Constraint *X, const Constraint *Y) {
760 ++DeltaApplications;
761 LLVM_DEBUG(dbgs() << "\tintersect constraints\n");
762 LLVM_DEBUG(dbgs() << "\t X ="; X->dump(dbgs()));
763 LLVM_DEBUG(dbgs() << "\t Y ="; Y->dump(dbgs()));
764 assert(!Y->isPoint() && "Y must not be a Point");
765 if (X->isAny()) {
766 if (Y->isAny())
767 return false;
768 *X = *Y;
769 return true;
770 }
771 if (X->isEmpty())
772 return false;
773 if (Y->isEmpty()) {
774 X->setEmpty();
775 return true;
776 }
777
778 if (X->isDistance() && Y->isDistance()) {
779 LLVM_DEBUG(dbgs() << "\t intersect 2 distances\n");
780 if (isKnownPredicate(CmpInst::ICMP_EQ, X->getD(), Y->getD()))
781 return false;
782 if (isKnownPredicate(CmpInst::ICMP_NE, X->getD(), Y->getD())) {
783 X->setEmpty();
784 ++DeltaSuccesses;
785 return true;
786 }
787 // Hmmm, interesting situation.
788 // I guess if either is constant, keep it and ignore the other.
789 if (isa<SCEVConstant>(Y->getD())) {
790 *X = *Y;
791 return true;
792 }
793 return false;
794 }
795
796 // At this point, the pseudo-code in Figure 4 of the paper
797 // checks if (X->isPoint() && Y->isPoint()).
798 // This case can't occur in our implementation,
799 // since a Point can only arise as the result of intersecting
800 // two Line constraints, and the right-hand value, Y, is never
801 // the result of an intersection.
802 assert(!(X->isPoint() && Y->isPoint()) &&
803 "We shouldn't ever see X->isPoint() && Y->isPoint()");
804
805 if (X->isLine() && Y->isLine()) {
806 LLVM_DEBUG(dbgs() << "\t intersect 2 lines\n");
807 const SCEV *Prod1 = SE->getMulExpr(X->getA(), Y->getB());
808 const SCEV *Prod2 = SE->getMulExpr(X->getB(), Y->getA());
809 if (isKnownPredicate(CmpInst::ICMP_EQ, Prod1, Prod2)) {
810 // slopes are equal, so lines are parallel
811 LLVM_DEBUG(dbgs() << "\t\tsame slope\n");
812 Prod1 = SE->getMulExpr(X->getC(), Y->getB());
813 Prod2 = SE->getMulExpr(X->getB(), Y->getC());
814 if (isKnownPredicate(CmpInst::ICMP_EQ, Prod1, Prod2))
815 return false;
816 if (isKnownPredicate(CmpInst::ICMP_NE, Prod1, Prod2)) {
817 X->setEmpty();
818 ++DeltaSuccesses;
819 return true;
820 }
821 return false;
822 }
823 if (isKnownPredicate(CmpInst::ICMP_NE, Prod1, Prod2)) {
824 // slopes differ, so lines intersect
825 LLVM_DEBUG(dbgs() << "\t\tdifferent slopes\n");
826 const SCEV *C1B2 = SE->getMulExpr(X->getC(), Y->getB());
827 const SCEV *C1A2 = SE->getMulExpr(X->getC(), Y->getA());
828 const SCEV *C2B1 = SE->getMulExpr(Y->getC(), X->getB());
829 const SCEV *C2A1 = SE->getMulExpr(Y->getC(), X->getA());
830 const SCEV *A1B2 = SE->getMulExpr(X->getA(), Y->getB());
831 const SCEV *A2B1 = SE->getMulExpr(Y->getA(), X->getB());
832 const SCEVConstant *C1A2_C2A1 =
833 dyn_cast<SCEVConstant>(SE->getMinusSCEV(C1A2, C2A1));
834 const SCEVConstant *C1B2_C2B1 =
835 dyn_cast<SCEVConstant>(SE->getMinusSCEV(C1B2, C2B1));
836 const SCEVConstant *A1B2_A2B1 =
837 dyn_cast<SCEVConstant>(SE->getMinusSCEV(A1B2, A2B1));
838 const SCEVConstant *A2B1_A1B2 =
839 dyn_cast<SCEVConstant>(SE->getMinusSCEV(A2B1, A1B2));
840 if (!C1B2_C2B1 || !C1A2_C2A1 || !A1B2_A2B1 || !A2B1_A1B2)
841 return false;
842 APInt Xtop = C1B2_C2B1->getAPInt();
843 APInt Xbot = A1B2_A2B1->getAPInt();
844 APInt Ytop = C1A2_C2A1->getAPInt();
845 APInt Ybot = A2B1_A1B2->getAPInt();
846 LLVM_DEBUG(dbgs() << "\t\tXtop = " << Xtop << "\n");
847 LLVM_DEBUG(dbgs() << "\t\tXbot = " << Xbot << "\n");
848 LLVM_DEBUG(dbgs() << "\t\tYtop = " << Ytop << "\n");
849 LLVM_DEBUG(dbgs() << "\t\tYbot = " << Ybot << "\n");
850 APInt Xq = Xtop; // these need to be initialized, even
851 APInt Xr = Xtop; // though they're just going to be overwritten
852 APInt::sdivrem(Xtop, Xbot, Xq, Xr);
853 APInt Yq = Ytop;
854 APInt Yr = Ytop;
855 APInt::sdivrem(Ytop, Ybot, Yq, Yr);
856 if (Xr != 0 || Yr != 0) {
857 X->setEmpty();
858 ++DeltaSuccesses;
859 return true;
860 }
861 LLVM_DEBUG(dbgs() << "\t\tX = " << Xq << ", Y = " << Yq << "\n");
862 if (Xq.slt(0) || Yq.slt(0)) {
863 X->setEmpty();
864 ++DeltaSuccesses;
865 return true;
866 }
867 if (const SCEVConstant *CUB = collectConstantUpperBound(
868 X->getAssociatedSrcLoop(), Prod1->getType())) {
869 const APInt &UpperBound = CUB->getAPInt();
870 LLVM_DEBUG(dbgs() << "\t\tupper bound = " << UpperBound << "\n");
871 if (Xq.sgt(UpperBound) || Yq.sgt(UpperBound)) {
872 X->setEmpty();
873 ++DeltaSuccesses;
874 return true;
875 }
876 }
877 X->setPoint(SE->getConstant(Xq), SE->getConstant(Yq),
878 X->getAssociatedSrcLoop(), X->getAssociatedDstLoop());
879 ++DeltaSuccesses;
880 return true;
881 }
882 return false;
883 }
884
885 // if (X->isLine() && Y->isPoint()) This case can't occur.
886 assert(!(X->isLine() && Y->isPoint()) && "This case should never occur");
887
888 if (X->isPoint() && Y->isLine()) {
889 LLVM_DEBUG(dbgs() << "\t intersect Point and Line\n");
890 const SCEV *A1X1 = SE->getMulExpr(Y->getA(), X->getX());
891 const SCEV *B1Y1 = SE->getMulExpr(Y->getB(), X->getY());
892 const SCEV *Sum = SE->getAddExpr(A1X1, B1Y1);
893 if (isKnownPredicate(CmpInst::ICMP_EQ, Sum, Y->getC()))
894 return false;
895 if (isKnownPredicate(CmpInst::ICMP_NE, Sum, Y->getC())) {
896 X->setEmpty();
897 ++DeltaSuccesses;
898 return true;
899 }
900 return false;
901 }
902
903 llvm_unreachable("shouldn't reach the end of Constraint intersection");
904 return false;
905}
906
907//===----------------------------------------------------------------------===//
908// SCEVMonotonicity
909
910SCEVMonotonicity::SCEVMonotonicity(SCEVMonotonicityType Type,
911 const SCEV *FailurePoint)
912 : Type(Type), FailurePoint(FailurePoint) {
913 assert(
914 ((Type == SCEVMonotonicityType::Unknown) == (FailurePoint != nullptr)) &&
915 "FailurePoint must be provided iff Type is Unknown");
916}
917
918void SCEVMonotonicity::print(raw_ostream &OS, unsigned Depth) const {
919 OS.indent(Depth) << "Monotonicity: ";
920 switch (Type) {
921 case SCEVMonotonicityType::Unknown:
922 assert(FailurePoint && "FailurePoint must be provided for Unknown");
923 OS << "Unknown\n";
924 OS.indent(Depth) << "Reason: " << *FailurePoint << "\n";
925 break;
926 case SCEVMonotonicityType::Invariant:
927 OS << "Invariant\n";
928 break;
929 case SCEVMonotonicityType::MultivariateSignedMonotonic:
930 OS << "MultivariateSignedMonotonic\n";
931 break;
932 }
933}
934
935bool SCEVMonotonicityChecker::isLoopInvariant(const SCEV *Expr) const {
936 return !OutermostLoop || SE->isLoopInvariant(Expr, OutermostLoop);
937}
938
939SCEVMonotonicity SCEVMonotonicityChecker::invariantOrUnknown(const SCEV *Expr) {
940 if (isLoopInvariant(Expr))
941 return SCEVMonotonicity(SCEVMonotonicityType::Invariant);
942 return createUnknown(Expr);
943}
944
945SCEVMonotonicity
946SCEVMonotonicityChecker::checkMonotonicity(const SCEV *Expr,
947 const Loop *OutermostLoop) {
948 assert(Expr->getType()->isIntegerTy() && "Expr must be integer type");
949 this->OutermostLoop = OutermostLoop;
950 return visit(Expr);
951}
952
953/// We only care about an affine AddRec at the moment. For an affine AddRec,
954/// the monotonicity can be inferred from its nowrap property. For example, let
955/// X and Y be loop-invariant, and assume Y is non-negative. An AddRec
956/// {X,+.Y}<nsw> implies:
957///
958/// X <=s (X + Y) <=s ((X + Y) + Y) <=s ...
959///
960/// Thus, we can conclude that the AddRec is monotonically increasing with
961/// respect to the associated loop in a signed sense. The similar reasoning
962/// applies when Y is non-positive, leading to a monotonically decreasing
963/// AddRec.
964SCEVMonotonicity
965SCEVMonotonicityChecker::visitAddRecExpr(const SCEVAddRecExpr *Expr) {
966 if (!Expr->isAffine() || !Expr->hasNoSignedWrap())
967 return createUnknown(Expr);
968
969 const SCEV *Start = Expr->getStart();
970 const SCEV *Step = Expr->getStepRecurrence(*SE);
971
972 SCEVMonotonicity StartMon = visit(Start);
973 if (StartMon.isUnknown())
974 return StartMon;
975
976 if (!isLoopInvariant(Step))
977 return createUnknown(Expr);
978
979 return SCEVMonotonicity(SCEVMonotonicityType::MultivariateSignedMonotonic);
980}
981
982//===----------------------------------------------------------------------===//
983// DependenceInfo methods
984
985// For debugging purposes. Dumps a dependence to OS.
987 if (isConfused())
988 OS << "confused";
989 else {
990 if (isConsistent())
991 OS << "consistent ";
992 if (isFlow())
993 OS << "flow";
994 else if (isOutput())
995 OS << "output";
996 else if (isAnti())
997 OS << "anti";
998 else if (isInput())
999 OS << "input";
1000 dumpImp(OS);
1001 unsigned SameSDLevels = getSameSDLevels();
1002 if (SameSDLevels > 0) {
1003 OS << " / assuming " << SameSDLevels << " loop level(s) fused: ";
1004 dumpImp(OS, true);
1005 }
1006 }
1007 OS << "!\n";
1008
1010 if (!Assumptions.isAlwaysTrue()) {
1011 OS << " Runtime Assumptions:\n";
1012 Assumptions.print(OS, 2);
1013 }
1014}
1015
1016// For debugging purposes. Dumps a dependence to OS with or without considering
1017// the SameSD levels.
1018void Dependence::dumpImp(raw_ostream &OS, bool IsSameSD) const {
1019 bool Splitable = false;
1020 unsigned Levels = getLevels();
1021 unsigned SameSDLevels = getSameSDLevels();
1022 bool OnSameSD = false;
1023 unsigned LevelNum = Levels;
1024 if (IsSameSD)
1025 LevelNum += SameSDLevels;
1026 OS << " [";
1027 for (unsigned II = 1; II <= LevelNum; ++II) {
1028 if (!OnSameSD && inSameSDLoops(II))
1029 OnSameSD = true;
1030 if (isSplitable(II, OnSameSD))
1031 Splitable = true;
1032 if (isPeelFirst(II, OnSameSD))
1033 OS << 'p';
1034 const SCEV *Distance = getDistance(II, OnSameSD);
1035 if (Distance)
1036 OS << *Distance;
1037 else if (isScalar(II, OnSameSD))
1038 OS << "S";
1039 else {
1040 unsigned Direction = getDirection(II, OnSameSD);
1041 if (Direction == DVEntry::ALL)
1042 OS << "*";
1043 else {
1044 if (Direction & DVEntry::LT)
1045 OS << "<";
1046 if (Direction & DVEntry::EQ)
1047 OS << "=";
1048 if (Direction & DVEntry::GT)
1049 OS << ">";
1050 }
1051 }
1052 if (isPeelLast(II, OnSameSD))
1053 OS << 'p';
1054 if (II < LevelNum)
1055 OS << " ";
1056 }
1057 if (isLoopIndependent())
1058 OS << "|<";
1059 OS << "]";
1060 if (Splitable)
1061 OS << " splitable";
1062}
1063
1064// Returns NoAlias/MayAliass/MustAlias for two memory locations based upon their
1065// underlaying objects. If LocA and LocB are known to not alias (for any reason:
1066// tbaa, non-overlapping regions etc), then it is known there is no dependecy.
1067// Otherwise the underlying objects are checked to see if they point to
1068// different identifiable objects.
1070 const MemoryLocation &LocA,
1071 const MemoryLocation &LocB) {
1072 // Check the original locations (minus size) for noalias, which can happen for
1073 // tbaa, incompatible underlying object locations, etc.
1074 MemoryLocation LocAS =
1076 MemoryLocation LocBS =
1078 BatchAAResults BAA(*AA);
1080
1081 if (BAA.isNoAlias(LocAS, LocBS))
1082 return AliasResult::NoAlias;
1083
1084 // Check the underlying objects are the same
1085 const Value *AObj = getUnderlyingObject(LocA.Ptr);
1086 const Value *BObj = getUnderlyingObject(LocB.Ptr);
1087
1088 // If the underlying objects are the same, they must alias
1089 if (AObj == BObj)
1091
1092 // We may have hit the recursion limit for underlying objects, or have
1093 // underlying objects where we don't know they will alias.
1094 if (!isIdentifiedObject(AObj) || !isIdentifiedObject(BObj))
1095 return AliasResult::MayAlias;
1096
1097 // Otherwise we know the objects are different and both identified objects so
1098 // must not alias.
1099 return AliasResult::NoAlias;
1100}
1101
1102// Returns true if the load or store can be analyzed. Atomic and volatile
1103// operations have properties which this analysis does not understand.
1104static bool isLoadOrStore(const Instruction *I) {
1105 if (const LoadInst *LI = dyn_cast<LoadInst>(I))
1106 return LI->isUnordered();
1107 else if (const StoreInst *SI = dyn_cast<StoreInst>(I))
1108 return SI->isUnordered();
1109 return false;
1110}
1111
1112// Returns true if two loops have the Same iteration Space and Depth. To be
1113// more specific, two loops have SameSD if they are in the same nesting
1114// depth and have the same backedge count. SameSD stands for Same iteration
1115// Space and Depth.
1116bool DependenceInfo::haveSameSD(const Loop *SrcLoop,
1117 const Loop *DstLoop) const {
1118 if (SrcLoop == DstLoop)
1119 return true;
1120
1121 if (SrcLoop->getLoopDepth() != DstLoop->getLoopDepth())
1122 return false;
1123
1124 if (!SrcLoop || !SrcLoop->getLoopLatch() || !DstLoop ||
1125 !DstLoop->getLoopLatch())
1126 return false;
1127
1128 const SCEV *SrcUB = nullptr, *DstUP = nullptr;
1129 if (SE->hasLoopInvariantBackedgeTakenCount(SrcLoop))
1130 SrcUB = SE->getBackedgeTakenCount(SrcLoop);
1131 if (SE->hasLoopInvariantBackedgeTakenCount(DstLoop))
1132 DstUP = SE->getBackedgeTakenCount(DstLoop);
1133
1134 if (SrcUB != nullptr && DstUP != nullptr &&
1135 SE->isKnownPredicate(ICmpInst::ICMP_EQ, SrcUB, DstUP))
1136 return true;
1137
1138 return false;
1139}
1140
1141// Examines the loop nesting of the Src and Dst
1142// instructions and establishes their shared loops. Sets the variables
1143// CommonLevels, SrcLevels, and MaxLevels.
1144// The source and destination instructions needn't be contained in the same
1145// loop. The routine establishNestingLevels finds the level of most deeply
1146// nested loop that contains them both, CommonLevels. An instruction that's
1147// not contained in a loop is at level = 0. MaxLevels is equal to the level
1148// of the source plus the level of the destination, minus CommonLevels.
1149// This lets us allocate vectors MaxLevels in length, with room for every
1150// distinct loop referenced in both the source and destination subscripts.
1151// The variable SrcLevels is the nesting depth of the source instruction.
1152// It's used to help calculate distinct loops referenced by the destination.
1153// Here's the map from loops to levels:
1154// 0 - unused
1155// 1 - outermost common loop
1156// ... - other common loops
1157// CommonLevels - innermost common loop
1158// ... - loops containing Src but not Dst
1159// SrcLevels - innermost loop containing Src but not Dst
1160// ... - loops containing Dst but not Src
1161// MaxLevels - innermost loops containing Dst but not Src
1162// Consider the follow code fragment:
1163// for (a = ...) {
1164// for (b = ...) {
1165// for (c = ...) {
1166// for (d = ...) {
1167// A[] = ...;
1168// }
1169// }
1170// for (e = ...) {
1171// for (f = ...) {
1172// for (g = ...) {
1173// ... = A[];
1174// }
1175// }
1176// }
1177// }
1178// }
1179// If we're looking at the possibility of a dependence between the store
1180// to A (the Src) and the load from A (the Dst), we'll note that they
1181// have 2 loops in common, so CommonLevels will equal 2 and the direction
1182// vector for Result will have 2 entries. SrcLevels = 4 and MaxLevels = 7.
1183// A map from loop names to loop numbers would look like
1184// a - 1
1185// b - 2 = CommonLevels
1186// c - 3
1187// d - 4 = SrcLevels
1188// e - 5
1189// f - 6
1190// g - 7 = MaxLevels
1191// SameSDLevels counts the number of levels after common levels that are
1192// not common but have the same iteration space and depth. Internally this
1193// is checked using haveSameSD. Assume that in this code fragment, levels c and
1194// e have the same iteration space and depth, but levels d and f does not. Then
1195// SameSDLevels is set to 1. In that case the level numbers for the previous
1196// code look like
1197// a - 1
1198// b - 2
1199// c,e - 3 = CommonLevels
1200// d - 4 = SrcLevels
1201// f - 5
1202// g - 6 = MaxLevels
1203void DependenceInfo::establishNestingLevels(const Instruction *Src,
1204 const Instruction *Dst) {
1205 const BasicBlock *SrcBlock = Src->getParent();
1206 const BasicBlock *DstBlock = Dst->getParent();
1207 unsigned SrcLevel = LI->getLoopDepth(SrcBlock);
1208 unsigned DstLevel = LI->getLoopDepth(DstBlock);
1209 const Loop *SrcLoop = LI->getLoopFor(SrcBlock);
1210 const Loop *DstLoop = LI->getLoopFor(DstBlock);
1211 SrcLevels = SrcLevel;
1212 MaxLevels = SrcLevel + DstLevel;
1213 SameSDLevels = 0;
1214 while (SrcLevel > DstLevel) {
1215 SrcLoop = SrcLoop->getParentLoop();
1216 SrcLevel--;
1217 }
1218 while (DstLevel > SrcLevel) {
1219 DstLoop = DstLoop->getParentLoop();
1220 DstLevel--;
1221 }
1222
1223 // find the first common level and count the SameSD levels leading to it
1224 while (SrcLoop != DstLoop) {
1225 SameSDLevels++;
1226 if (!haveSameSD(SrcLoop, DstLoop))
1227 SameSDLevels = 0;
1228 SrcLoop = SrcLoop->getParentLoop();
1229 DstLoop = DstLoop->getParentLoop();
1230 SrcLevel--;
1231 }
1232 CommonLevels = SrcLevel;
1233 MaxLevels -= CommonLevels;
1234}
1235
1236// Given one of the loops containing the source, return
1237// its level index in our numbering scheme.
1238unsigned DependenceInfo::mapSrcLoop(const Loop *SrcLoop) const {
1239 return SrcLoop->getLoopDepth();
1240}
1241
1242// Given one of the loops containing the destination,
1243// return its level index in our numbering scheme.
1244unsigned DependenceInfo::mapDstLoop(const Loop *DstLoop) const {
1245 unsigned D = DstLoop->getLoopDepth();
1246 if (D > CommonLevels)
1247 // This tries to make sure that we assign unique numbers to src and dst when
1248 // the memory accesses reside in different loops that have the same depth.
1249 return D - CommonLevels + SrcLevels;
1250 else
1251 return D;
1252}
1253
1254// Returns true if Expression is loop invariant in LoopNest.
1255bool DependenceInfo::isLoopInvariant(const SCEV *Expression,
1256 const Loop *LoopNest) const {
1257 // Unlike ScalarEvolution::isLoopInvariant() we consider an access outside of
1258 // any loop as invariant, because we only consier expression evaluation at a
1259 // specific position (where the array access takes place), and not across the
1260 // entire function.
1261 if (!LoopNest)
1262 return true;
1263
1264 // If the expression is invariant in the outermost loop of the loop nest, it
1265 // is invariant anywhere in the loop nest.
1266 return SE->isLoopInvariant(Expression, LoopNest->getOutermostLoop());
1267}
1268
1269// Finds the set of loops from the LoopNest that
1270// have a level <= CommonLevels and are referred to by the SCEV Expression.
1271void DependenceInfo::collectCommonLoops(const SCEV *Expression,
1272 const Loop *LoopNest,
1273 SmallBitVector &Loops) const {
1274 while (LoopNest) {
1275 unsigned Level = LoopNest->getLoopDepth();
1276 if (Level <= CommonLevels && !SE->isLoopInvariant(Expression, LoopNest))
1277 Loops.set(Level);
1278 LoopNest = LoopNest->getParentLoop();
1279 }
1280}
1281
1282void DependenceInfo::unifySubscriptType(ArrayRef<Subscript *> Pairs) {
1283
1284 unsigned widestWidthSeen = 0;
1285 Type *widestType;
1286
1287 // Go through each pair and find the widest bit to which we need
1288 // to extend all of them.
1289 for (Subscript *Pair : Pairs) {
1290 const SCEV *Src = Pair->Src;
1291 const SCEV *Dst = Pair->Dst;
1292 IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType());
1293 IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType());
1294 if (SrcTy == nullptr || DstTy == nullptr) {
1295 assert(SrcTy == DstTy &&
1296 "This function only unify integer types and "
1297 "expect Src and Dst share the same type otherwise.");
1298 continue;
1299 }
1300 if (SrcTy->getBitWidth() > widestWidthSeen) {
1301 widestWidthSeen = SrcTy->getBitWidth();
1302 widestType = SrcTy;
1303 }
1304 if (DstTy->getBitWidth() > widestWidthSeen) {
1305 widestWidthSeen = DstTy->getBitWidth();
1306 widestType = DstTy;
1307 }
1308 }
1309
1310 assert(widestWidthSeen > 0);
1311
1312 // Now extend each pair to the widest seen.
1313 for (Subscript *Pair : Pairs) {
1314 const SCEV *Src = Pair->Src;
1315 const SCEV *Dst = Pair->Dst;
1316 IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType());
1317 IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType());
1318 if (SrcTy == nullptr || DstTy == nullptr) {
1319 assert(SrcTy == DstTy &&
1320 "This function only unify integer types and "
1321 "expect Src and Dst share the same type otherwise.");
1322 continue;
1323 }
1324 if (SrcTy->getBitWidth() < widestWidthSeen)
1325 // Sign-extend Src to widestType
1326 Pair->Src = SE->getSignExtendExpr(Src, widestType);
1327 if (DstTy->getBitWidth() < widestWidthSeen) {
1328 // Sign-extend Dst to widestType
1329 Pair->Dst = SE->getSignExtendExpr(Dst, widestType);
1330 }
1331 }
1332}
1333
1334// removeMatchingExtensions - Examines a subscript pair.
1335// If the source and destination are identically sign (or zero)
1336// extended, it strips off the extension in an effect to simplify
1337// the actual analysis.
1338void DependenceInfo::removeMatchingExtensions(Subscript *Pair) {
1339 const SCEV *Src = Pair->Src;
1340 const SCEV *Dst = Pair->Dst;
1343 const SCEVIntegralCastExpr *SrcCast = cast<SCEVIntegralCastExpr>(Src);
1344 const SCEVIntegralCastExpr *DstCast = cast<SCEVIntegralCastExpr>(Dst);
1345 const SCEV *SrcCastOp = SrcCast->getOperand();
1346 const SCEV *DstCastOp = DstCast->getOperand();
1347 if (SrcCastOp->getType() == DstCastOp->getType()) {
1348 Pair->Src = SrcCastOp;
1349 Pair->Dst = DstCastOp;
1350 }
1351 }
1352}
1353
1354// Examine the scev and return true iff it's affine.
1355// Collect any loops mentioned in the set of "Loops".
1356bool DependenceInfo::checkSubscript(const SCEV *Expr, const Loop *LoopNest,
1357 SmallBitVector &Loops, bool IsSrc) {
1358 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
1359 if (!AddRec)
1360 return isLoopInvariant(Expr, LoopNest);
1361
1362 // The AddRec must depend on one of the containing loops. Otherwise,
1363 // mapSrcLoop and mapDstLoop return indices outside the intended range. This
1364 // can happen when a subscript in one loop references an IV from a sibling
1365 // loop that could not be replaced with a concrete exit value by
1366 // getSCEVAtScope.
1367 const Loop *L = LoopNest;
1368 while (L && AddRec->getLoop() != L)
1369 L = L->getParentLoop();
1370 if (!L)
1371 return false;
1372
1373 const SCEV *Start = AddRec->getStart();
1374 const SCEV *Step = AddRec->getStepRecurrence(*SE);
1375 if (!isLoopInvariant(Step, LoopNest))
1376 return false;
1377 if (IsSrc)
1378 Loops.set(mapSrcLoop(AddRec->getLoop()));
1379 else
1380 Loops.set(mapDstLoop(AddRec->getLoop()));
1381 return checkSubscript(Start, LoopNest, Loops, IsSrc);
1382}
1383
1384// Examine the scev and return true iff it's linear.
1385// Collect any loops mentioned in the set of "Loops".
1386bool DependenceInfo::checkSrcSubscript(const SCEV *Src, const Loop *LoopNest,
1388 return checkSubscript(Src, LoopNest, Loops, true);
1389}
1390
1391// Examine the scev and return true iff it's linear.
1392// Collect any loops mentioned in the set of "Loops".
1393bool DependenceInfo::checkDstSubscript(const SCEV *Dst, const Loop *LoopNest,
1395 return checkSubscript(Dst, LoopNest, Loops, false);
1396}
1397
1398// Examines the subscript pair (the Src and Dst SCEVs)
1399// and classifies it as either ZIV, SIV, RDIV, MIV, or Nonlinear.
1400// Collects the associated loops in a set.
1401DependenceInfo::Subscript::ClassificationKind
1402DependenceInfo::classifyPair(const SCEV *Src, const Loop *SrcLoopNest,
1403 const SCEV *Dst, const Loop *DstLoopNest,
1405 SmallBitVector SrcLoops(MaxLevels + 1);
1406 SmallBitVector DstLoops(MaxLevels + 1);
1407 if (!checkSrcSubscript(Src, SrcLoopNest, SrcLoops))
1408 return Subscript::NonLinear;
1409 if (!checkDstSubscript(Dst, DstLoopNest, DstLoops))
1410 return Subscript::NonLinear;
1411 Loops = SrcLoops;
1412 Loops |= DstLoops;
1413 unsigned N = Loops.count();
1414 if (N == 0)
1415 return Subscript::ZIV;
1416 if (N == 1)
1417 return Subscript::SIV;
1418 if (N == 2 && (SrcLoops.count() == 0 || DstLoops.count() == 0 ||
1419 (SrcLoops.count() == 1 && DstLoops.count() == 1)))
1420 return Subscript::RDIV;
1421 return Subscript::MIV;
1422}
1423
1424// A wrapper around SCEV::isKnownPredicate.
1425// Looks for cases where we're interested in comparing for equality.
1426// If both X and Y have been identically sign or zero extended,
1427// it strips off the (confusing) extensions before invoking
1428// SCEV::isKnownPredicate. Perhaps, someday, the ScalarEvolution package
1429// will be similarly updated.
1430//
1431// If SCEV::isKnownPredicate can't prove the predicate,
1432// we try simple subtraction, which seems to help in some cases
1433// involving symbolics.
1434bool DependenceInfo::isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *X,
1435 const SCEV *Y) const {
1436 if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE) {
1439 const SCEVIntegralCastExpr *CX = cast<SCEVIntegralCastExpr>(X);
1440 const SCEVIntegralCastExpr *CY = cast<SCEVIntegralCastExpr>(Y);
1441 const SCEV *Xop = CX->getOperand();
1442 const SCEV *Yop = CY->getOperand();
1443 if (Xop->getType() == Yop->getType()) {
1444 X = Xop;
1445 Y = Yop;
1446 }
1447 }
1448 }
1449 if (SE->isKnownPredicate(Pred, X, Y))
1450 return true;
1451 // If SE->isKnownPredicate can't prove the condition,
1452 // we try the brute-force approach of subtracting
1453 // and testing the difference.
1454 // By testing with SE->isKnownPredicate first, we avoid
1455 // the possibility of overflow when the arguments are constants.
1456 const SCEV *Delta = SE->getMinusSCEV(X, Y);
1457 switch (Pred) {
1458 case CmpInst::ICMP_EQ:
1459 return Delta->isZero();
1460 case CmpInst::ICMP_NE:
1461 return SE->isKnownNonZero(Delta);
1462 case CmpInst::ICMP_SGE:
1463 return SE->isKnownNonNegative(Delta);
1464 case CmpInst::ICMP_SLE:
1465 return SE->isKnownNonPositive(Delta);
1466 case CmpInst::ICMP_SGT:
1467 return SE->isKnownPositive(Delta);
1468 case CmpInst::ICMP_SLT:
1469 return SE->isKnownNegative(Delta);
1470 default:
1471 llvm_unreachable("unexpected predicate in isKnownPredicate");
1472 }
1473}
1474
1475/// Compare to see if S is less than Size, using
1476///
1477/// isKnownNegative(S - Size)
1478///
1479/// with some extra checking if S is an AddRec and we can prove less-than using
1480/// the loop bounds.
1481bool DependenceInfo::isKnownLessThan(const SCEV *S, const SCEV *Size) const {
1482 // First unify to the same type
1483 auto *SType = dyn_cast<IntegerType>(S->getType());
1484 auto *SizeType = dyn_cast<IntegerType>(Size->getType());
1485 if (!SType || !SizeType)
1486 return false;
1487 Type *MaxType =
1488 (SType->getBitWidth() >= SizeType->getBitWidth()) ? SType : SizeType;
1489 S = SE->getTruncateOrZeroExtend(S, MaxType);
1490 Size = SE->getTruncateOrZeroExtend(Size, MaxType);
1491
1492 auto CheckAddRecBECount = [&]() {
1493 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S);
1494 if (!AddRec || !AddRec->isAffine() || !AddRec->hasNoSignedWrap())
1495 return false;
1496 const SCEV *BECount = collectUpperBound(AddRec->getLoop(), MaxType);
1497 // If the BTC cannot be computed, check the base case for S.
1498 if (!BECount || isa<SCEVCouldNotCompute>(BECount))
1499 return false;
1500 const SCEV *Start = AddRec->getStart();
1501 const SCEV *Step = AddRec->getStepRecurrence(*SE);
1502 const SCEV *End = AddRec->evaluateAtIteration(BECount, *SE);
1503 const SCEV *Diff0 = SE->getMinusSCEV(Start, Size);
1504 const SCEV *Diff1 = SE->getMinusSCEV(End, Size);
1505
1506 // If the value of Step is non-negative and the AddRec is non-wrap, it
1507 // reaches its maximum at the last iteration. So it's enouth to check
1508 // whether End - Size is negative.
1509 if (SE->isKnownNonNegative(Step) && SE->isKnownNegative(Diff1))
1510 return true;
1511
1512 // If the value of Step is non-positive and the AddRec is non-wrap, the
1513 // initial value is its maximum.
1514 if (SE->isKnownNonPositive(Step) && SE->isKnownNegative(Diff0))
1515 return true;
1516
1517 // Even if we don't know the sign of Step, either Start or End must be
1518 // the maximum value of the AddRec since it is non-wrap.
1519 if (SE->isKnownNegative(Diff0) && SE->isKnownNegative(Diff1))
1520 return true;
1521
1522 return false;
1523 };
1524
1525 if (CheckAddRecBECount())
1526 return true;
1527
1528 // Check using normal isKnownNegative
1529 const SCEV *LimitedBound = SE->getMinusSCEV(S, Size);
1530 return SE->isKnownNegative(LimitedBound);
1531}
1532
1533bool DependenceInfo::isKnownNonNegative(const SCEV *S, const Value *Ptr) const {
1534 bool Inbounds = false;
1535 if (auto *SrcGEP = dyn_cast<GetElementPtrInst>(Ptr))
1536 Inbounds = SrcGEP->isInBounds();
1537 if (Inbounds) {
1538 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
1539 if (AddRec->isAffine()) {
1540 // We know S is for Ptr, the operand on a load/store, so doesn't wrap.
1541 // If both parts are NonNegative, the end result will be NonNegative
1542 if (SE->isKnownNonNegative(AddRec->getStart()) &&
1543 SE->isKnownNonNegative(AddRec->getOperand(1)))
1544 return true;
1545 }
1546 }
1547 }
1548
1549 return SE->isKnownNonNegative(S);
1550}
1551
1552// All subscripts are all the same type.
1553// Loop bound may be smaller (e.g., a char).
1554// Should zero extend loop bound, since it's always >= 0.
1555// This routine collects upper bound and extends or truncates if needed.
1556// Truncating is safe when subscripts are known not to wrap. Cases without
1557// nowrap flags should have been rejected earlier.
1558// Return null if no bound available.
1559const SCEV *DependenceInfo::collectUpperBound(const Loop *L, Type *T) const {
1560 if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
1561 const SCEV *UB = SE->getBackedgeTakenCount(L);
1562 return SE->getTruncateOrZeroExtend(UB, T);
1563 }
1564 return nullptr;
1565}
1566
1567// Calls collectUpperBound(), then attempts to cast it to SCEVConstant.
1568// If the cast fails, returns NULL.
1569const SCEVConstant *DependenceInfo::collectConstantUpperBound(const Loop *L,
1570 Type *T) const {
1571 if (const SCEV *UB = collectUpperBound(L, T))
1572 return dyn_cast<SCEVConstant>(UB);
1573 return nullptr;
1574}
1575
1576/// Returns \p A - \p B if it guaranteed not to signed wrap. Otherwise returns
1577/// nullptr. \p A and \p B must have the same integer type.
1578static const SCEV *minusSCEVNoSignedOverflow(const SCEV *A, const SCEV *B,
1579 ScalarEvolution &SE) {
1580 if (SE.willNotOverflow(Instruction::Sub, /*Signed=*/true, A, B))
1581 return SE.getMinusSCEV(A, B);
1582 return nullptr;
1583}
1584
1585/// Returns true iff \p Test is enabled.
1586static bool isDependenceTestEnabled(DependenceTestType Test) {
1587 if (EnableDependenceTest == DependenceTestType::All)
1588 return true;
1589 return EnableDependenceTest == Test;
1590}
1591
1592// testZIV -
1593// When we have a pair of subscripts of the form [c1] and [c2],
1594// where c1 and c2 are both loop invariant, we attack it using
1595// the ZIV test. Basically, we test by comparing the two values,
1596// but there are actually three possible results:
1597// 1) the values are equal, so there's a dependence
1598// 2) the values are different, so there's no dependence
1599// 3) the values might be equal, so we have to assume a dependence.
1600//
1601// Return true if dependence disproved.
1602bool DependenceInfo::testZIV(const SCEV *Src, const SCEV *Dst,
1603 FullDependence &Result) const {
1604 LLVM_DEBUG(dbgs() << " src = " << *Src << "\n");
1605 LLVM_DEBUG(dbgs() << " dst = " << *Dst << "\n");
1606 ++ZIVapplications;
1607 if (isKnownPredicate(CmpInst::ICMP_EQ, Src, Dst)) {
1608 LLVM_DEBUG(dbgs() << " provably dependent\n");
1609 return false; // provably dependent
1610 }
1611 if (isKnownPredicate(CmpInst::ICMP_NE, Src, Dst)) {
1612 LLVM_DEBUG(dbgs() << " provably independent\n");
1613 ++ZIVindependence;
1614 return true; // provably independent
1615 }
1616 LLVM_DEBUG(dbgs() << " possibly dependent\n");
1617 Result.Consistent = false;
1618 return false; // possibly dependent
1619}
1620
1621// strongSIVtest -
1622// From the paper, Practical Dependence Testing, Section 4.2.1
1623//
1624// When we have a pair of subscripts of the form [c1 + a*i] and [c2 + a*i],
1625// where i is an induction variable, c1 and c2 are loop invariant,
1626// and a is a constant, we can solve it exactly using the Strong SIV test.
1627//
1628// Can prove independence. Failing that, can compute distance (and direction).
1629// In the presence of symbolic terms, we can sometimes make progress.
1630//
1631// If there's a dependence,
1632//
1633// c1 + a*i = c2 + a*i'
1634//
1635// The dependence distance is
1636//
1637// d = i' - i = (c1 - c2)/a
1638//
1639// A dependence only exists if d is an integer and abs(d) <= U, where U is the
1640// loop's upper bound. If a dependence exists, the dependence direction is
1641// defined as
1642//
1643// { < if d > 0
1644// direction = { = if d = 0
1645// { > if d < 0
1646//
1647// Return true if dependence disproved.
1648bool DependenceInfo::strongSIVtest(const SCEV *Coeff, const SCEV *SrcConst,
1649 const SCEV *DstConst, const Loop *CurSrcLoop,
1650 const Loop *CurDstLoop, unsigned Level,
1651 FullDependence &Result,
1652 Constraint &NewConstraint) const {
1653 if (!isDependenceTestEnabled(DependenceTestType::StrongSIV))
1654 return false;
1655
1656 LLVM_DEBUG(dbgs() << "\tStrong SIV test\n");
1657 LLVM_DEBUG(dbgs() << "\t Coeff = " << *Coeff);
1658 LLVM_DEBUG(dbgs() << ", " << *Coeff->getType() << "\n");
1659 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst);
1660 LLVM_DEBUG(dbgs() << ", " << *SrcConst->getType() << "\n");
1661 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst);
1662 LLVM_DEBUG(dbgs() << ", " << *DstConst->getType() << "\n");
1663 ++StrongSIVapplications;
1664 assert(0 < Level && Level <= CommonLevels && "level out of range");
1665 Level--;
1666
1667 const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst);
1668 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta);
1669 LLVM_DEBUG(dbgs() << ", " << *Delta->getType() << "\n");
1670
1671 // check that |Delta| < iteration count
1672 if (const SCEV *UpperBound =
1673 collectUpperBound(CurSrcLoop, Delta->getType())) {
1674 LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound);
1675 LLVM_DEBUG(dbgs() << ", " << *UpperBound->getType() << "\n");
1676 const SCEV *AbsDelta =
1677 SE->isKnownNonNegative(Delta) ? Delta : SE->getNegativeSCEV(Delta);
1678 const SCEV *AbsCoeff =
1679 SE->isKnownNonNegative(Coeff) ? Coeff : SE->getNegativeSCEV(Coeff);
1680 const SCEV *Product = SE->getMulExpr(UpperBound, AbsCoeff);
1681 if (isKnownPredicate(CmpInst::ICMP_SGT, AbsDelta, Product)) {
1682 // Distance greater than trip count - no dependence
1683 ++StrongSIVindependence;
1684 ++StrongSIVsuccesses;
1685 return true;
1686 }
1687 }
1688
1689 // Can we compute distance?
1690 if (isa<SCEVConstant>(Delta) && isa<SCEVConstant>(Coeff)) {
1691 APInt ConstDelta = cast<SCEVConstant>(Delta)->getAPInt();
1692 APInt ConstCoeff = cast<SCEVConstant>(Coeff)->getAPInt();
1693 APInt Distance = ConstDelta; // these need to be initialized
1694 APInt Remainder = ConstDelta;
1695 APInt::sdivrem(ConstDelta, ConstCoeff, Distance, Remainder);
1696 LLVM_DEBUG(dbgs() << "\t Distance = " << Distance << "\n");
1697 LLVM_DEBUG(dbgs() << "\t Remainder = " << Remainder << "\n");
1698 // Make sure Coeff divides Delta exactly
1699 if (Remainder != 0) {
1700 // Coeff doesn't divide Distance, no dependence
1701 ++StrongSIVindependence;
1702 ++StrongSIVsuccesses;
1703 return true;
1704 }
1705 Result.DV[Level].Distance = SE->getConstant(Distance);
1706 NewConstraint.setDistance(SE->getConstant(Distance), CurSrcLoop,
1707 CurDstLoop);
1708 if (Distance.sgt(0))
1709 Result.DV[Level].Direction &= Dependence::DVEntry::LT;
1710 else if (Distance.slt(0))
1711 Result.DV[Level].Direction &= Dependence::DVEntry::GT;
1712 else
1713 Result.DV[Level].Direction &= Dependence::DVEntry::EQ;
1714 ++StrongSIVsuccesses;
1715 } else if (Delta->isZero()) {
1716 // since 0/X == 0
1717 Result.DV[Level].Distance = Delta;
1718 NewConstraint.setDistance(Delta, CurSrcLoop, CurDstLoop);
1719 Result.DV[Level].Direction &= Dependence::DVEntry::EQ;
1720 ++StrongSIVsuccesses;
1721 } else {
1722 if (Coeff->isOne()) {
1723 LLVM_DEBUG(dbgs() << "\t Distance = " << *Delta << "\n");
1724 Result.DV[Level].Distance = Delta; // since X/1 == X
1725 NewConstraint.setDistance(Delta, CurSrcLoop, CurDstLoop);
1726 } else {
1727 Result.Consistent = false;
1728 NewConstraint.setLine(Coeff, SE->getNegativeSCEV(Coeff),
1729 SE->getNegativeSCEV(Delta), CurSrcLoop, CurDstLoop);
1730 }
1731
1732 // maybe we can get a useful direction
1733 bool DeltaMaybeZero = !SE->isKnownNonZero(Delta);
1734 bool DeltaMaybePositive = !SE->isKnownNonPositive(Delta);
1735 bool DeltaMaybeNegative = !SE->isKnownNonNegative(Delta);
1736 bool CoeffMaybePositive = !SE->isKnownNonPositive(Coeff);
1737 bool CoeffMaybeNegative = !SE->isKnownNonNegative(Coeff);
1738 // The double negatives above are confusing.
1739 // It helps to read !SE->isKnownNonZero(Delta)
1740 // as "Delta might be Zero"
1741 unsigned NewDirection = Dependence::DVEntry::NONE;
1742 if ((DeltaMaybePositive && CoeffMaybePositive) ||
1743 (DeltaMaybeNegative && CoeffMaybeNegative))
1744 NewDirection = Dependence::DVEntry::LT;
1745 if (DeltaMaybeZero)
1746 NewDirection |= Dependence::DVEntry::EQ;
1747 if ((DeltaMaybeNegative && CoeffMaybePositive) ||
1748 (DeltaMaybePositive && CoeffMaybeNegative))
1749 NewDirection |= Dependence::DVEntry::GT;
1750 if (NewDirection < Result.DV[Level].Direction)
1751 ++StrongSIVsuccesses;
1752 Result.DV[Level].Direction &= NewDirection;
1753 }
1754 return false;
1755}
1756
1757// weakCrossingSIVtest -
1758// From the paper, Practical Dependence Testing, Section 4.2.2
1759//
1760// When we have a pair of subscripts of the form [c1 + a*i] and [c2 - a*i],
1761// where i is an induction variable, c1 and c2 are loop invariant,
1762// and a is a constant, we can solve it exactly using the
1763// Weak-Crossing SIV test.
1764//
1765// Given c1 + a*i = c2 - a*i', we can look for the intersection of
1766// the two lines, where i = i', yielding
1767//
1768// c1 + a*i = c2 - a*i
1769// 2a*i = c2 - c1
1770// i = (c2 - c1)/2a
1771//
1772// If i < 0, there is no dependence.
1773// If i > upperbound, there is no dependence.
1774// If i = 0 (i.e., if c1 = c2), there's a dependence with distance = 0.
1775// If i = upperbound, there's a dependence with distance = 0.
1776// If i is integral, there's a dependence (all directions).
1777// If the non-integer part = 1/2, there's a dependence (<> directions).
1778// Otherwise, there's no dependence.
1779//
1780// Can prove independence. Failing that,
1781// can sometimes refine the directions.
1782// Can determine iteration for splitting.
1783//
1784// Return true if dependence disproved.
1785bool DependenceInfo::weakCrossingSIVtest(
1786 const SCEV *Coeff, const SCEV *SrcConst, const SCEV *DstConst,
1787 const Loop *CurSrcLoop, const Loop *CurDstLoop, unsigned Level,
1788 FullDependence &Result, Constraint &NewConstraint,
1789 const SCEV *&SplitIter) const {
1790 if (!isDependenceTestEnabled(DependenceTestType::WeakCrossingSIV))
1791 return false;
1792
1793 LLVM_DEBUG(dbgs() << "\tWeak-Crossing SIV test\n");
1794 LLVM_DEBUG(dbgs() << "\t Coeff = " << *Coeff << "\n");
1795 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n");
1796 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n");
1797 ++WeakCrossingSIVapplications;
1798 assert(0 < Level && Level <= CommonLevels && "Level out of range");
1799 Level--;
1800 Result.Consistent = false;
1801 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
1802 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n");
1803 NewConstraint.setLine(Coeff, Coeff, Delta, CurSrcLoop, CurDstLoop);
1804 if (Delta->isZero()) {
1805 Result.DV[Level].Direction &= ~Dependence::DVEntry::LT;
1806 Result.DV[Level].Direction &= ~Dependence::DVEntry::GT;
1807 ++WeakCrossingSIVsuccesses;
1808 if (!Result.DV[Level].Direction) {
1809 ++WeakCrossingSIVindependence;
1810 return true;
1811 }
1812 Result.DV[Level].Distance = Delta; // = 0
1813 return false;
1814 }
1815 const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(Coeff);
1816 if (!ConstCoeff)
1817 return false;
1818
1819 Result.DV[Level].Splitable = true;
1820 if (SE->isKnownNegative(ConstCoeff)) {
1821 ConstCoeff = dyn_cast<SCEVConstant>(SE->getNegativeSCEV(ConstCoeff));
1822 assert(ConstCoeff &&
1823 "dynamic cast of negative of ConstCoeff should yield constant");
1824 Delta = SE->getNegativeSCEV(Delta);
1825 }
1826 assert(SE->isKnownPositive(ConstCoeff) && "ConstCoeff should be positive");
1827
1828 // compute SplitIter for use by DependenceInfo::getSplitIteration()
1829 SplitIter = SE->getUDivExpr(
1830 SE->getSMaxExpr(SE->getZero(Delta->getType()), Delta),
1831 SE->getMulExpr(SE->getConstant(Delta->getType(), 2), ConstCoeff));
1832 LLVM_DEBUG(dbgs() << "\t Split iter = " << *SplitIter << "\n");
1833
1834 const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
1835 if (!ConstDelta)
1836 return false;
1837
1838 // We're certain that ConstCoeff > 0; therefore,
1839 // if Delta < 0, then no dependence.
1840 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n");
1841 LLVM_DEBUG(dbgs() << "\t ConstCoeff = " << *ConstCoeff << "\n");
1842 if (SE->isKnownNegative(Delta)) {
1843 // No dependence, Delta < 0
1844 ++WeakCrossingSIVindependence;
1845 ++WeakCrossingSIVsuccesses;
1846 return true;
1847 }
1848
1849 // We're certain that Delta > 0 and ConstCoeff > 0.
1850 // Check Delta/(2*ConstCoeff) against upper loop bound
1851 if (const SCEV *UpperBound =
1852 collectUpperBound(CurSrcLoop, Delta->getType())) {
1853 LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound << "\n");
1854 const SCEV *ConstantTwo = SE->getConstant(UpperBound->getType(), 2);
1855 const SCEV *ML =
1856 SE->getMulExpr(SE->getMulExpr(ConstCoeff, UpperBound), ConstantTwo);
1857 LLVM_DEBUG(dbgs() << "\t ML = " << *ML << "\n");
1858 if (isKnownPredicate(CmpInst::ICMP_SGT, Delta, ML)) {
1859 // Delta too big, no dependence
1860 ++WeakCrossingSIVindependence;
1861 ++WeakCrossingSIVsuccesses;
1862 return true;
1863 }
1864 if (isKnownPredicate(CmpInst::ICMP_EQ, Delta, ML)) {
1865 // i = i' = UB
1866 Result.DV[Level].Direction &= ~Dependence::DVEntry::LT;
1867 Result.DV[Level].Direction &= ~Dependence::DVEntry::GT;
1868 ++WeakCrossingSIVsuccesses;
1869 if (!Result.DV[Level].Direction) {
1870 ++WeakCrossingSIVindependence;
1871 return true;
1872 }
1873 Result.DV[Level].Splitable = false;
1874 Result.DV[Level].Distance = SE->getZero(Delta->getType());
1875 return false;
1876 }
1877 }
1878
1879 // check that Coeff divides Delta
1880 APInt APDelta = ConstDelta->getAPInt();
1881 APInt APCoeff = ConstCoeff->getAPInt();
1882 APInt Distance = APDelta; // these need to be initialzed
1883 APInt Remainder = APDelta;
1884 APInt::sdivrem(APDelta, APCoeff, Distance, Remainder);
1885 LLVM_DEBUG(dbgs() << "\t Remainder = " << Remainder << "\n");
1886 if (Remainder != 0) {
1887 // Coeff doesn't divide Delta, no dependence
1888 ++WeakCrossingSIVindependence;
1889 ++WeakCrossingSIVsuccesses;
1890 return true;
1891 }
1892 LLVM_DEBUG(dbgs() << "\t Distance = " << Distance << "\n");
1893
1894 // if 2*Coeff doesn't divide Delta, then the equal direction isn't possible
1895 APInt Two = APInt(Distance.getBitWidth(), 2, true);
1896 Remainder = Distance.srem(Two);
1897 LLVM_DEBUG(dbgs() << "\t Remainder = " << Remainder << "\n");
1898 if (Remainder != 0) {
1899 // Equal direction isn't possible
1900 Result.DV[Level].Direction &= ~Dependence::DVEntry::EQ;
1901 ++WeakCrossingSIVsuccesses;
1902 }
1903 return false;
1904}
1905
1906// Kirch's algorithm, from
1907//
1908// Optimizing Supercompilers for Supercomputers
1909// Michael Wolfe
1910// MIT Press, 1989
1911//
1912// Program 2.1, page 29.
1913// Computes the GCD of AM and BM.
1914// Also finds a solution to the equation ax - by = gcd(a, b).
1915// Returns true if dependence disproved; i.e., gcd does not divide Delta.
1916static bool findGCD(unsigned Bits, const APInt &AM, const APInt &BM,
1917 const APInt &Delta, APInt &G, APInt &X, APInt &Y) {
1918 APInt A0(Bits, 1, true), A1(Bits, 0, true);
1919 APInt B0(Bits, 0, true), B1(Bits, 1, true);
1920 APInt G0 = AM.abs();
1921 APInt G1 = BM.abs();
1922 APInt Q = G0; // these need to be initialized
1923 APInt R = G0;
1924 APInt::sdivrem(G0, G1, Q, R);
1925 while (R != 0) {
1926 // clang-format off
1927 APInt A2 = A0 - Q*A1; A0 = A1; A1 = A2;
1928 APInt B2 = B0 - Q*B1; B0 = B1; B1 = B2;
1929 G0 = G1; G1 = R;
1930 // clang-format on
1931 APInt::sdivrem(G0, G1, Q, R);
1932 }
1933 G = G1;
1934 LLVM_DEBUG(dbgs() << "\t GCD = " << G << "\n");
1935 X = AM.slt(0) ? -A1 : A1;
1936 Y = BM.slt(0) ? B1 : -B1;
1937
1938 // make sure gcd divides Delta
1939 R = Delta.srem(G);
1940 if (R != 0)
1941 return true; // gcd doesn't divide Delta, no dependence
1942 Q = Delta.sdiv(G);
1943 return false;
1944}
1945
1946static APInt floorOfQuotient(const APInt &A, const APInt &B) {
1947 APInt Q = A; // these need to be initialized
1948 APInt R = A;
1949 APInt::sdivrem(A, B, Q, R);
1950 if (R == 0)
1951 return Q;
1952 if ((A.sgt(0) && B.sgt(0)) || (A.slt(0) && B.slt(0)))
1953 return Q;
1954 else
1955 return Q - 1;
1956}
1957
1958static APInt ceilingOfQuotient(const APInt &A, const APInt &B) {
1959 APInt Q = A; // these need to be initialized
1960 APInt R = A;
1961 APInt::sdivrem(A, B, Q, R);
1962 if (R == 0)
1963 return Q;
1964 if ((A.sgt(0) && B.sgt(0)) || (A.slt(0) && B.slt(0)))
1965 return Q + 1;
1966 else
1967 return Q;
1968}
1969
1970/// Given an affine expression of the form A*k + B, where k is an arbitrary
1971/// integer, infer the possible range of k based on the known range of the
1972/// affine expression. If we know A*k + B is non-negative, i.e.,
1973///
1974/// A*k + B >= 0
1975///
1976/// we can derive the following inequalities for k when A is positive:
1977///
1978/// k >= -B / A
1979///
1980/// Since k is an integer, it means k is greater than or equal to the
1981/// ceil(-B / A).
1982///
1983/// If the upper bound of the affine expression \p UB is passed, the following
1984/// inequality can be derived as well:
1985///
1986/// A*k + B <= UB
1987///
1988/// which leads to:
1989///
1990/// k <= (UB - B) / A
1991///
1992/// Again, as k is an integer, it means k is less than or equal to the
1993/// floor((UB - B) / A).
1994///
1995/// The similar logic applies when A is negative, but the inequalities sign flip
1996/// while working with them.
1997///
1998/// Preconditions: \p A is non-zero, and we know A*k + B is non-negative.
1999static std::pair<std::optional<APInt>, std::optional<APInt>>
2001 const std::optional<APInt> &UB) {
2002 assert(A != 0 && "A must be non-zero");
2003 std::optional<APInt> TL, TU;
2004 if (A.sgt(0)) {
2005 TL = ceilingOfQuotient(-B, A);
2006 LLVM_DEBUG(dbgs() << "\t Possible TL = " << *TL << "\n");
2007 // New bound check - modification to Banerjee's e3 check
2008 if (UB) {
2009 // TODO?: Overflow check for UB - B
2010 TU = floorOfQuotient(*UB - B, A);
2011 LLVM_DEBUG(dbgs() << "\t Possible TU = " << *TU << "\n");
2012 }
2013 } else {
2014 TU = floorOfQuotient(-B, A);
2015 LLVM_DEBUG(dbgs() << "\t Possible TU = " << *TU << "\n");
2016 // New bound check - modification to Banerjee's e3 check
2017 if (UB) {
2018 // TODO?: Overflow check for UB - B
2019 TL = ceilingOfQuotient(*UB - B, A);
2020 LLVM_DEBUG(dbgs() << "\t Possible TL = " << *TL << "\n");
2021 }
2022 }
2023 return std::make_pair(TL, TU);
2024}
2025
2026// exactSIVtest -
2027// When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*i],
2028// where i is an induction variable, c1 and c2 are loop invariant, and a1
2029// and a2 are constant, we can solve it exactly using an algorithm developed
2030// by Banerjee and Wolfe. See Algorithm 6.2.1 (case 2.5) in:
2031//
2032// Dependence Analysis for Supercomputing
2033// Utpal Banerjee
2034// Kluwer Academic Publishers, 1988
2035//
2036// It's slower than the specialized tests (strong SIV, weak-zero SIV, etc),
2037// so use them if possible. They're also a bit better with symbolics and,
2038// in the case of the strong SIV test, can compute Distances.
2039//
2040// Return true if dependence disproved.
2041//
2042// This is a modified version of the original Banerjee algorithm. The original
2043// only tested whether Dst depends on Src. This algorithm extends that and
2044// returns all the dependencies that exist between Dst and Src.
2045bool DependenceInfo::exactSIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff,
2046 const SCEV *SrcConst, const SCEV *DstConst,
2047 const Loop *CurSrcLoop,
2048 const Loop *CurDstLoop, unsigned Level,
2049 FullDependence &Result,
2050 Constraint &NewConstraint) const {
2051 if (!isDependenceTestEnabled(DependenceTestType::ExactSIV))
2052 return false;
2053
2054 LLVM_DEBUG(dbgs() << "\tExact SIV test\n");
2055 LLVM_DEBUG(dbgs() << "\t SrcCoeff = " << *SrcCoeff << " = AM\n");
2056 LLVM_DEBUG(dbgs() << "\t DstCoeff = " << *DstCoeff << " = BM\n");
2057 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n");
2058 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n");
2059 ++ExactSIVapplications;
2060 assert(0 < Level && Level <= CommonLevels && "Level out of range");
2061 Level--;
2062 Result.Consistent = false;
2063 const SCEV *Delta = minusSCEVNoSignedOverflow(DstConst, SrcConst, *SE);
2064 if (!Delta)
2065 return false;
2066 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n");
2067 NewConstraint.setLine(SrcCoeff, SE->getNegativeSCEV(DstCoeff), Delta,
2068 CurSrcLoop, CurDstLoop);
2069 const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
2070 const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
2071 const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
2072 if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
2073 return false;
2074
2075 // find gcd
2076 APInt G, X, Y;
2077 APInt AM = ConstSrcCoeff->getAPInt();
2078 APInt BM = ConstDstCoeff->getAPInt();
2079 APInt CM = ConstDelta->getAPInt();
2080 unsigned Bits = AM.getBitWidth();
2081 if (findGCD(Bits, AM, BM, CM, G, X, Y)) {
2082 // gcd doesn't divide Delta, no dependence
2083 ++ExactSIVindependence;
2084 ++ExactSIVsuccesses;
2085 return true;
2086 }
2087
2088 LLVM_DEBUG(dbgs() << "\t X = " << X << ", Y = " << Y << "\n");
2089
2090 // since SCEV construction normalizes, LM = 0
2091 std::optional<APInt> UM;
2092 // UM is perhaps unavailable, let's check
2093 if (const SCEVConstant *CUB =
2094 collectConstantUpperBound(CurSrcLoop, Delta->getType())) {
2095 UM = CUB->getAPInt();
2096 LLVM_DEBUG(dbgs() << "\t UM = " << *UM << "\n");
2097 }
2098
2099 APInt TU(APInt::getSignedMaxValue(Bits));
2100 APInt TL(APInt::getSignedMinValue(Bits));
2101 APInt TC = CM.sdiv(G);
2102 APInt TX = X * TC;
2103 APInt TY = Y * TC;
2104 LLVM_DEBUG(dbgs() << "\t TC = " << TC << "\n");
2105 LLVM_DEBUG(dbgs() << "\t TX = " << TX << "\n");
2106 LLVM_DEBUG(dbgs() << "\t TY = " << TY << "\n");
2107
2108 APInt TB = BM.sdiv(G);
2109 APInt TA = AM.sdiv(G);
2110
2111 // At this point, we have the following equations:
2112 //
2113 // TA*i0 - TB*i1 = TC
2114 //
2115 // Also, we know that the all pairs of (i0, i1) can be expressed as:
2116 //
2117 // (TX + k*TB, TY + k*TA)
2118 //
2119 // where k is an arbitrary integer.
2120 auto [TL0, TU0] = inferDomainOfAffine(TB, TX, UM);
2121 auto [TL1, TU1] = inferDomainOfAffine(TA, TY, UM);
2122
2123 auto CreateVec = [](const std::optional<APInt> &V0,
2124 const std::optional<APInt> &V1) {
2126 if (V0)
2127 Vec.push_back(*V0);
2128 if (V1)
2129 Vec.push_back(*V1);
2130 return Vec;
2131 };
2132
2133 SmallVector<APInt, 2> TLVec = CreateVec(TL0, TL1);
2134 SmallVector<APInt, 2> TUVec = CreateVec(TU0, TU1);
2135
2136 LLVM_DEBUG(dbgs() << "\t TA = " << TA << "\n");
2137 LLVM_DEBUG(dbgs() << "\t TB = " << TB << "\n");
2138
2139 if (TLVec.empty() || TUVec.empty())
2140 return false;
2141 TL = APIntOps::smax(TLVec.front(), TLVec.back());
2142 TU = APIntOps::smin(TUVec.front(), TUVec.back());
2143 LLVM_DEBUG(dbgs() << "\t TL = " << TL << "\n");
2144 LLVM_DEBUG(dbgs() << "\t TU = " << TU << "\n");
2145
2146 if (TL.sgt(TU)) {
2147 ++ExactSIVindependence;
2148 ++ExactSIVsuccesses;
2149 return true;
2150 }
2151
2152 // explore directions
2153 unsigned NewDirection = Dependence::DVEntry::NONE;
2154 APInt LowerDistance, UpperDistance;
2155 // TODO: Overflow check may be needed.
2156 if (TA.sgt(TB)) {
2157 LowerDistance = (TY - TX) + (TA - TB) * TL;
2158 UpperDistance = (TY - TX) + (TA - TB) * TU;
2159 } else {
2160 LowerDistance = (TY - TX) + (TA - TB) * TU;
2161 UpperDistance = (TY - TX) + (TA - TB) * TL;
2162 }
2163
2164 LLVM_DEBUG(dbgs() << "\t LowerDistance = " << LowerDistance << "\n");
2165 LLVM_DEBUG(dbgs() << "\t UpperDistance = " << UpperDistance << "\n");
2166
2167 APInt Zero(Bits, 0, true);
2168 if (LowerDistance.sle(Zero) && UpperDistance.sge(Zero)) {
2169 NewDirection |= Dependence::DVEntry::EQ;
2170 ++ExactSIVsuccesses;
2171 }
2172 if (LowerDistance.slt(0)) {
2173 NewDirection |= Dependence::DVEntry::GT;
2174 ++ExactSIVsuccesses;
2175 }
2176 if (UpperDistance.sgt(0)) {
2177 NewDirection |= Dependence::DVEntry::LT;
2178 ++ExactSIVsuccesses;
2179 }
2180
2181 // finished
2182 Result.DV[Level].Direction &= NewDirection;
2183 if (Result.DV[Level].Direction == Dependence::DVEntry::NONE)
2184 ++ExactSIVindependence;
2185 LLVM_DEBUG(dbgs() << "\t Result = ");
2186 LLVM_DEBUG(Result.dump(dbgs()));
2187 return Result.DV[Level].Direction == Dependence::DVEntry::NONE;
2188}
2189
2190// Return true if the divisor evenly divides the dividend.
2191static bool isRemainderZero(const SCEVConstant *Dividend,
2192 const SCEVConstant *Divisor) {
2193 const APInt &ConstDividend = Dividend->getAPInt();
2194 const APInt &ConstDivisor = Divisor->getAPInt();
2195 return ConstDividend.srem(ConstDivisor) == 0;
2196}
2197
2198// weakZeroSrcSIVtest -
2199// From the paper, Practical Dependence Testing, Section 4.2.2
2200//
2201// When we have a pair of subscripts of the form [c1] and [c2 + a*i],
2202// where i is an induction variable, c1 and c2 are loop invariant,
2203// and a is a constant, we can solve it exactly using the
2204// Weak-Zero SIV test.
2205//
2206// Given
2207//
2208// c1 = c2 + a*i
2209//
2210// we get
2211//
2212// (c1 - c2)/a = i
2213//
2214// If i is not an integer, there's no dependence.
2215// If i < 0 or > UB, there's no dependence.
2216// If i = 0, the direction is >= and peeling the
2217// 1st iteration will break the dependence.
2218// If i = UB, the direction is <= and peeling the
2219// last iteration will break the dependence.
2220// Otherwise, the direction is *.
2221//
2222// Can prove independence. Failing that, we can sometimes refine
2223// the directions. Can sometimes show that first or last
2224// iteration carries all the dependences (so worth peeling).
2225//
2226// (see also weakZeroDstSIVtest)
2227//
2228// Return true if dependence disproved.
2229bool DependenceInfo::weakZeroSrcSIVtest(
2230 const SCEV *DstCoeff, const SCEV *SrcConst, const SCEV *DstConst,
2231 const Loop *CurSrcLoop, const Loop *CurDstLoop, unsigned Level,
2232 FullDependence &Result, Constraint &NewConstraint) const {
2233 if (!isDependenceTestEnabled(DependenceTestType::WeakZeroSIV))
2234 return false;
2235
2236 // For the WeakSIV test, it's possible the loop isn't common to
2237 // the Src and Dst loops. If it isn't, then there's no need to
2238 // record a direction.
2239 LLVM_DEBUG(dbgs() << "\tWeak-Zero (src) SIV test\n");
2240 LLVM_DEBUG(dbgs() << "\t DstCoeff = " << *DstCoeff << "\n");
2241 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n");
2242 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n");
2243 ++WeakZeroSIVapplications;
2244 assert(0 < Level && Level <= MaxLevels && "Level out of range");
2245 Level--;
2246 Result.Consistent = false;
2247 const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst);
2248 NewConstraint.setLine(SE->getZero(Delta->getType()), DstCoeff, Delta,
2249 CurSrcLoop, CurDstLoop);
2250 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n");
2251 if (isKnownPredicate(CmpInst::ICMP_EQ, SrcConst, DstConst)) {
2252 if (Level < CommonLevels) {
2253 Result.DV[Level].Direction &= Dependence::DVEntry::GE;
2254 Result.DV[Level].PeelFirst = true;
2255 ++WeakZeroSIVsuccesses;
2256 }
2257 return false; // dependences caused by first iteration
2258 }
2259 const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
2260 if (!ConstCoeff)
2261 return false;
2262 const SCEV *AbsCoeff = SE->isKnownNegative(ConstCoeff)
2263 ? SE->getNegativeSCEV(ConstCoeff)
2264 : ConstCoeff;
2265 const SCEV *NewDelta =
2266 SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta;
2267
2268 // check that Delta/SrcCoeff < iteration count
2269 // really check NewDelta < count*AbsCoeff
2270 if (const SCEV *UpperBound =
2271 collectUpperBound(CurSrcLoop, Delta->getType())) {
2272 LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound << "\n");
2273 const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound);
2274 if (isKnownPredicate(CmpInst::ICMP_SGT, NewDelta, Product)) {
2275 ++WeakZeroSIVindependence;
2276 ++WeakZeroSIVsuccesses;
2277 return true;
2278 }
2279 if (isKnownPredicate(CmpInst::ICMP_EQ, NewDelta, Product)) {
2280 // dependences caused by last iteration
2281 if (Level < CommonLevels) {
2282 Result.DV[Level].Direction &= Dependence::DVEntry::LE;
2283 Result.DV[Level].PeelLast = true;
2284 ++WeakZeroSIVsuccesses;
2285 }
2286 return false;
2287 }
2288 }
2289
2290 // check that Delta/SrcCoeff >= 0
2291 // really check that NewDelta >= 0
2292 if (SE->isKnownNegative(NewDelta)) {
2293 // No dependence, newDelta < 0
2294 ++WeakZeroSIVindependence;
2295 ++WeakZeroSIVsuccesses;
2296 return true;
2297 }
2298
2299 // if SrcCoeff doesn't divide Delta, then no dependence
2300 if (isa<SCEVConstant>(Delta) &&
2301 !isRemainderZero(cast<SCEVConstant>(Delta), ConstCoeff)) {
2302 ++WeakZeroSIVindependence;
2303 ++WeakZeroSIVsuccesses;
2304 return true;
2305 }
2306 return false;
2307}
2308
2309// weakZeroDstSIVtest -
2310// From the paper, Practical Dependence Testing, Section 4.2.2
2311//
2312// When we have a pair of subscripts of the form [c1 + a*i] and [c2],
2313// where i is an induction variable, c1 and c2 are loop invariant,
2314// and a is a constant, we can solve it exactly using the
2315// Weak-Zero SIV test.
2316//
2317// Given
2318//
2319// c1 + a*i = c2
2320//
2321// we get
2322//
2323// i = (c2 - c1)/a
2324//
2325// If i is not an integer, there's no dependence.
2326// If i < 0 or > UB, there's no dependence.
2327// If i = 0, the direction is <= and peeling the
2328// 1st iteration will break the dependence.
2329// If i = UB, the direction is >= and peeling the
2330// last iteration will break the dependence.
2331// Otherwise, the direction is *.
2332//
2333// Can prove independence. Failing that, we can sometimes refine
2334// the directions. Can sometimes show that first or last
2335// iteration carries all the dependences (so worth peeling).
2336//
2337// (see also weakZeroSrcSIVtest)
2338//
2339// Return true if dependence disproved.
2340bool DependenceInfo::weakZeroDstSIVtest(
2341 const SCEV *SrcCoeff, const SCEV *SrcConst, const SCEV *DstConst,
2342 const Loop *CurSrcLoop, const Loop *CurDstLoop, unsigned Level,
2343 FullDependence &Result, Constraint &NewConstraint) const {
2344 if (!isDependenceTestEnabled(DependenceTestType::WeakZeroSIV))
2345 return false;
2346
2347 // For the WeakSIV test, it's possible the loop isn't common to the
2348 // Src and Dst loops. If it isn't, then there's no need to record a direction.
2349 LLVM_DEBUG(dbgs() << "\tWeak-Zero (dst) SIV test\n");
2350 LLVM_DEBUG(dbgs() << "\t SrcCoeff = " << *SrcCoeff << "\n");
2351 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n");
2352 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n");
2353 ++WeakZeroSIVapplications;
2354 assert(0 < Level && Level <= SrcLevels && "Level out of range");
2355 Level--;
2356 Result.Consistent = false;
2357 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
2358 NewConstraint.setLine(SrcCoeff, SE->getZero(Delta->getType()), Delta,
2359 CurSrcLoop, CurDstLoop);
2360 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n");
2361 if (isKnownPredicate(CmpInst::ICMP_EQ, DstConst, SrcConst)) {
2362 if (Level < CommonLevels) {
2363 Result.DV[Level].Direction &= Dependence::DVEntry::LE;
2364 Result.DV[Level].PeelFirst = true;
2365 ++WeakZeroSIVsuccesses;
2366 }
2367 return false; // dependences caused by first iteration
2368 }
2369 const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
2370 if (!ConstCoeff)
2371 return false;
2372 const SCEV *AbsCoeff = SE->isKnownNegative(ConstCoeff)
2373 ? SE->getNegativeSCEV(ConstCoeff)
2374 : ConstCoeff;
2375 const SCEV *NewDelta =
2376 SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta;
2377
2378 // check that Delta/SrcCoeff < iteration count
2379 // really check NewDelta < count*AbsCoeff
2380 if (const SCEV *UpperBound =
2381 collectUpperBound(CurSrcLoop, Delta->getType())) {
2382 LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound << "\n");
2383 const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound);
2384 if (isKnownPredicate(CmpInst::ICMP_SGT, NewDelta, Product)) {
2385 ++WeakZeroSIVindependence;
2386 ++WeakZeroSIVsuccesses;
2387 return true;
2388 }
2389 if (isKnownPredicate(CmpInst::ICMP_EQ, NewDelta, Product)) {
2390 // dependences caused by last iteration
2391 if (Level < CommonLevels) {
2392 Result.DV[Level].Direction &= Dependence::DVEntry::GE;
2393 Result.DV[Level].PeelLast = true;
2394 ++WeakZeroSIVsuccesses;
2395 }
2396 return false;
2397 }
2398 }
2399
2400 // check that Delta/SrcCoeff >= 0
2401 // really check that NewDelta >= 0
2402 if (SE->isKnownNegative(NewDelta)) {
2403 // No dependence, newDelta < 0
2404 ++WeakZeroSIVindependence;
2405 ++WeakZeroSIVsuccesses;
2406 return true;
2407 }
2408
2409 // if SrcCoeff doesn't divide Delta, then no dependence
2410 if (isa<SCEVConstant>(Delta) &&
2411 !isRemainderZero(cast<SCEVConstant>(Delta), ConstCoeff)) {
2412 ++WeakZeroSIVindependence;
2413 ++WeakZeroSIVsuccesses;
2414 return true;
2415 }
2416 return false;
2417}
2418
2419// exactRDIVtest - Tests the RDIV subscript pair for dependence.
2420// Things of the form [c1 + a*i] and [c2 + b*j],
2421// where i and j are induction variable, c1 and c2 are loop invariant,
2422// and a and b are constants.
2423// Returns true if any possible dependence is disproved.
2424// Marks the result as inconsistent.
2425// Works in some cases that symbolicRDIVtest doesn't, and vice versa.
2426bool DependenceInfo::exactRDIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff,
2427 const SCEV *SrcConst, const SCEV *DstConst,
2428 const Loop *SrcLoop, const Loop *DstLoop,
2429 FullDependence &Result) const {
2430 if (!isDependenceTestEnabled(DependenceTestType::ExactRDIV))
2431 return false;
2432
2433 LLVM_DEBUG(dbgs() << "\tExact RDIV test\n");
2434 LLVM_DEBUG(dbgs() << "\t SrcCoeff = " << *SrcCoeff << " = AM\n");
2435 LLVM_DEBUG(dbgs() << "\t DstCoeff = " << *DstCoeff << " = BM\n");
2436 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n");
2437 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n");
2438 ++ExactRDIVapplications;
2439 Result.Consistent = false;
2440 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
2441 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n");
2442 const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
2443 const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
2444 const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
2445 if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
2446 return false;
2447
2448 // find gcd
2449 APInt G, X, Y;
2450 APInt AM = ConstSrcCoeff->getAPInt();
2451 APInt BM = ConstDstCoeff->getAPInt();
2452 APInt CM = ConstDelta->getAPInt();
2453 unsigned Bits = AM.getBitWidth();
2454 if (findGCD(Bits, AM, BM, CM, G, X, Y)) {
2455 // gcd doesn't divide Delta, no dependence
2456 ++ExactRDIVindependence;
2457 return true;
2458 }
2459
2460 LLVM_DEBUG(dbgs() << "\t X = " << X << ", Y = " << Y << "\n");
2461
2462 // since SCEV construction seems to normalize, LM = 0
2463 std::optional<APInt> SrcUM;
2464 // SrcUM is perhaps unavailable, let's check
2465 if (const SCEVConstant *UpperBound =
2466 collectConstantUpperBound(SrcLoop, Delta->getType())) {
2467 SrcUM = UpperBound->getAPInt();
2468 LLVM_DEBUG(dbgs() << "\t SrcUM = " << *SrcUM << "\n");
2469 }
2470
2471 std::optional<APInt> DstUM;
2472 // UM is perhaps unavailable, let's check
2473 if (const SCEVConstant *UpperBound =
2474 collectConstantUpperBound(DstLoop, Delta->getType())) {
2475 DstUM = UpperBound->getAPInt();
2476 LLVM_DEBUG(dbgs() << "\t DstUM = " << *DstUM << "\n");
2477 }
2478
2479 APInt TU(APInt::getSignedMaxValue(Bits));
2480 APInt TL(APInt::getSignedMinValue(Bits));
2481 APInt TC = CM.sdiv(G);
2482 APInt TX = X * TC;
2483 APInt TY = Y * TC;
2484 LLVM_DEBUG(dbgs() << "\t TC = " << TC << "\n");
2485 LLVM_DEBUG(dbgs() << "\t TX = " << TX << "\n");
2486 LLVM_DEBUG(dbgs() << "\t TY = " << TY << "\n");
2487
2488 APInt TB = BM.sdiv(G);
2489 APInt TA = AM.sdiv(G);
2490
2491 // At this point, we have the following equations:
2492 //
2493 // TA*i - TB*j = TC
2494 //
2495 // Also, we know that the all pairs of (i, j) can be expressed as:
2496 //
2497 // (TX + k*TB, TY + k*TA)
2498 //
2499 // where k is an arbitrary integer.
2500 auto [TL0, TU0] = inferDomainOfAffine(TB, TX, SrcUM);
2501 auto [TL1, TU1] = inferDomainOfAffine(TA, TY, DstUM);
2502
2503 LLVM_DEBUG(dbgs() << "\t TA = " << TA << "\n");
2504 LLVM_DEBUG(dbgs() << "\t TB = " << TB << "\n");
2505
2506 auto CreateVec = [](const std::optional<APInt> &V0,
2507 const std::optional<APInt> &V1) {
2509 if (V0)
2510 Vec.push_back(*V0);
2511 if (V1)
2512 Vec.push_back(*V1);
2513 return Vec;
2514 };
2515
2516 SmallVector<APInt, 2> TLVec = CreateVec(TL0, TL1);
2517 SmallVector<APInt, 2> TUVec = CreateVec(TU0, TU1);
2518 if (TLVec.empty() || TUVec.empty())
2519 return false;
2520
2521 TL = APIntOps::smax(TLVec.front(), TLVec.back());
2522 TU = APIntOps::smin(TUVec.front(), TUVec.back());
2523 LLVM_DEBUG(dbgs() << "\t TL = " << TL << "\n");
2524 LLVM_DEBUG(dbgs() << "\t TU = " << TU << "\n");
2525
2526 if (TL.sgt(TU))
2527 ++ExactRDIVindependence;
2528 return TL.sgt(TU);
2529}
2530
2531// symbolicRDIVtest -
2532// In Section 4.5 of the Practical Dependence Testing paper,the authors
2533// introduce a special case of Banerjee's Inequalities (also called the
2534// Extreme-Value Test) that can handle some of the SIV and RDIV cases,
2535// particularly cases with symbolics. Since it's only able to disprove
2536// dependence (not compute distances or directions), we'll use it as a
2537// fall back for the other tests.
2538//
2539// When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*j]
2540// where i and j are induction variables and c1 and c2 are loop invariants,
2541// we can use the symbolic tests to disprove some dependences, serving as a
2542// backup for the RDIV test. Note that i and j can be the same variable,
2543// letting this test serve as a backup for the various SIV tests.
2544//
2545// For a dependence to exist, c1 + a1*i must equal c2 + a2*j for some
2546// 0 <= i <= N1 and some 0 <= j <= N2, where N1 and N2 are the (normalized)
2547// loop bounds for the i and j loops, respectively. So, ...
2548//
2549// c1 + a1*i = c2 + a2*j
2550// a1*i - a2*j = c2 - c1
2551//
2552// To test for a dependence, we compute c2 - c1 and make sure it's in the
2553// range of the maximum and minimum possible values of a1*i - a2*j.
2554// Considering the signs of a1 and a2, we have 4 possible cases:
2555//
2556// 1) If a1 >= 0 and a2 >= 0, then
2557// a1*0 - a2*N2 <= c2 - c1 <= a1*N1 - a2*0
2558// -a2*N2 <= c2 - c1 <= a1*N1
2559//
2560// 2) If a1 >= 0 and a2 <= 0, then
2561// a1*0 - a2*0 <= c2 - c1 <= a1*N1 - a2*N2
2562// 0 <= c2 - c1 <= a1*N1 - a2*N2
2563//
2564// 3) If a1 <= 0 and a2 >= 0, then
2565// a1*N1 - a2*N2 <= c2 - c1 <= a1*0 - a2*0
2566// a1*N1 - a2*N2 <= c2 - c1 <= 0
2567//
2568// 4) If a1 <= 0 and a2 <= 0, then
2569// a1*N1 - a2*0 <= c2 - c1 <= a1*0 - a2*N2
2570// a1*N1 <= c2 - c1 <= -a2*N2
2571//
2572// return true if dependence disproved
2573bool DependenceInfo::symbolicRDIVtest(const SCEV *A1, const SCEV *A2,
2574 const SCEV *C1, const SCEV *C2,
2575 const Loop *Loop1,
2576 const Loop *Loop2) const {
2577 if (!isDependenceTestEnabled(DependenceTestType::SymbolicRDIV))
2578 return false;
2579
2580 ++SymbolicRDIVapplications;
2581 LLVM_DEBUG(dbgs() << "\ttry symbolic RDIV test\n");
2582 LLVM_DEBUG(dbgs() << "\t A1 = " << *A1);
2583 LLVM_DEBUG(dbgs() << ", type = " << *A1->getType() << "\n");
2584 LLVM_DEBUG(dbgs() << "\t A2 = " << *A2 << "\n");
2585 LLVM_DEBUG(dbgs() << "\t C1 = " << *C1 << "\n");
2586 LLVM_DEBUG(dbgs() << "\t C2 = " << *C2 << "\n");
2587 const SCEV *N1 = collectUpperBound(Loop1, A1->getType());
2588 const SCEV *N2 = collectUpperBound(Loop2, A1->getType());
2589 LLVM_DEBUG(if (N1) dbgs() << "\t N1 = " << *N1 << "\n");
2590 LLVM_DEBUG(if (N2) dbgs() << "\t N2 = " << *N2 << "\n");
2591 const SCEV *C2_C1 = SE->getMinusSCEV(C2, C1);
2592 const SCEV *C1_C2 = SE->getMinusSCEV(C1, C2);
2593 LLVM_DEBUG(dbgs() << "\t C2 - C1 = " << *C2_C1 << "\n");
2594 LLVM_DEBUG(dbgs() << "\t C1 - C2 = " << *C1_C2 << "\n");
2595 if (SE->isKnownNonNegative(A1)) {
2596 if (SE->isKnownNonNegative(A2)) {
2597 // A1 >= 0 && A2 >= 0
2598 if (N1) {
2599 // make sure that c2 - c1 <= a1*N1
2600 const SCEV *A1N1 = SE->getMulExpr(A1, N1);
2601 LLVM_DEBUG(dbgs() << "\t A1*N1 = " << *A1N1 << "\n");
2602 if (isKnownPredicate(CmpInst::ICMP_SGT, C2_C1, A1N1)) {
2603 ++SymbolicRDIVindependence;
2604 return true;
2605 }
2606 }
2607 if (N2) {
2608 // make sure that -a2*N2 <= c2 - c1, or a2*N2 >= c1 - c2
2609 const SCEV *A2N2 = SE->getMulExpr(A2, N2);
2610 LLVM_DEBUG(dbgs() << "\t A2*N2 = " << *A2N2 << "\n");
2611 if (isKnownPredicate(CmpInst::ICMP_SLT, A2N2, C1_C2)) {
2612 ++SymbolicRDIVindependence;
2613 return true;
2614 }
2615 }
2616 } else if (SE->isKnownNonPositive(A2)) {
2617 // a1 >= 0 && a2 <= 0
2618 if (N1 && N2) {
2619 // make sure that c2 - c1 <= a1*N1 - a2*N2
2620 const SCEV *A1N1 = SE->getMulExpr(A1, N1);
2621 const SCEV *A2N2 = SE->getMulExpr(A2, N2);
2622 const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2);
2623 LLVM_DEBUG(dbgs() << "\t A1*N1 - A2*N2 = " << *A1N1_A2N2 << "\n");
2624 if (isKnownPredicate(CmpInst::ICMP_SGT, C2_C1, A1N1_A2N2)) {
2625 ++SymbolicRDIVindependence;
2626 return true;
2627 }
2628 }
2629 // make sure that 0 <= c2 - c1
2630 if (SE->isKnownNegative(C2_C1)) {
2631 ++SymbolicRDIVindependence;
2632 return true;
2633 }
2634 }
2635 } else if (SE->isKnownNonPositive(A1)) {
2636 if (SE->isKnownNonNegative(A2)) {
2637 // a1 <= 0 && a2 >= 0
2638 if (N1 && N2) {
2639 // make sure that a1*N1 - a2*N2 <= c2 - c1
2640 const SCEV *A1N1 = SE->getMulExpr(A1, N1);
2641 const SCEV *A2N2 = SE->getMulExpr(A2, N2);
2642 const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2);
2643 LLVM_DEBUG(dbgs() << "\t A1*N1 - A2*N2 = " << *A1N1_A2N2 << "\n");
2644 if (isKnownPredicate(CmpInst::ICMP_SGT, A1N1_A2N2, C2_C1)) {
2645 ++SymbolicRDIVindependence;
2646 return true;
2647 }
2648 }
2649 // make sure that c2 - c1 <= 0
2650 if (SE->isKnownPositive(C2_C1)) {
2651 ++SymbolicRDIVindependence;
2652 return true;
2653 }
2654 } else if (SE->isKnownNonPositive(A2)) {
2655 // a1 <= 0 && a2 <= 0
2656 if (N1) {
2657 // make sure that a1*N1 <= c2 - c1
2658 const SCEV *A1N1 = SE->getMulExpr(A1, N1);
2659 LLVM_DEBUG(dbgs() << "\t A1*N1 = " << *A1N1 << "\n");
2660 if (isKnownPredicate(CmpInst::ICMP_SGT, A1N1, C2_C1)) {
2661 ++SymbolicRDIVindependence;
2662 return true;
2663 }
2664 }
2665 if (N2) {
2666 // make sure that c2 - c1 <= -a2*N2, or c1 - c2 >= a2*N2
2667 const SCEV *A2N2 = SE->getMulExpr(A2, N2);
2668 LLVM_DEBUG(dbgs() << "\t A2*N2 = " << *A2N2 << "\n");
2669 if (isKnownPredicate(CmpInst::ICMP_SLT, C1_C2, A2N2)) {
2670 ++SymbolicRDIVindependence;
2671 return true;
2672 }
2673 }
2674 }
2675 }
2676 return false;
2677}
2678
2679// testSIV -
2680// When we have a pair of subscripts of the form [c1 + a1*i] and [c2 - a2*i]
2681// where i is an induction variable, c1 and c2 are loop invariant, and a1 and
2682// a2 are constant, we attack it with an SIV test. While they can all be
2683// solved with the Exact SIV test, it's worthwhile to use simpler tests when
2684// they apply; they're cheaper and sometimes more precise.
2685//
2686// Return true if dependence disproved.
2687bool DependenceInfo::testSIV(const SCEV *Src, const SCEV *Dst, unsigned &Level,
2688 FullDependence &Result, Constraint &NewConstraint,
2689 const SCEV *&SplitIter) const {
2690 LLVM_DEBUG(dbgs() << " src = " << *Src << "\n");
2691 LLVM_DEBUG(dbgs() << " dst = " << *Dst << "\n");
2692 const SCEVAddRecExpr *SrcAddRec = dyn_cast<SCEVAddRecExpr>(Src);
2693 const SCEVAddRecExpr *DstAddRec = dyn_cast<SCEVAddRecExpr>(Dst);
2694 if (SrcAddRec && DstAddRec) {
2695 const SCEV *SrcConst = SrcAddRec->getStart();
2696 const SCEV *DstConst = DstAddRec->getStart();
2697 const SCEV *SrcCoeff = SrcAddRec->getStepRecurrence(*SE);
2698 const SCEV *DstCoeff = DstAddRec->getStepRecurrence(*SE);
2699 const Loop *CurSrcLoop = SrcAddRec->getLoop();
2700 const Loop *CurDstLoop = DstAddRec->getLoop();
2701 assert(haveSameSD(CurSrcLoop, CurDstLoop) &&
2702 "Loops in the SIV test should have the same iteration space and "
2703 "depth");
2704 Level = mapSrcLoop(CurSrcLoop);
2705 bool disproven;
2706 if (SrcCoeff == DstCoeff)
2707 disproven = strongSIVtest(SrcCoeff, SrcConst, DstConst, CurSrcLoop,
2708 CurDstLoop, Level, Result, NewConstraint);
2709 else if (SrcCoeff == SE->getNegativeSCEV(DstCoeff))
2710 disproven = weakCrossingSIVtest(SrcCoeff, SrcConst, DstConst, CurSrcLoop,
2711 CurDstLoop, Level, Result, NewConstraint,
2712 SplitIter);
2713 else
2714 disproven =
2715 exactSIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurSrcLoop,
2716 CurDstLoop, Level, Result, NewConstraint);
2717 return disproven || gcdMIVtest(Src, Dst, Result) ||
2718 symbolicRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurSrcLoop,
2719 CurDstLoop);
2720 }
2721 if (SrcAddRec) {
2722 const SCEV *SrcConst = SrcAddRec->getStart();
2723 const SCEV *SrcCoeff = SrcAddRec->getStepRecurrence(*SE);
2724 const SCEV *DstConst = Dst;
2725 const Loop *CurSrcLoop = SrcAddRec->getLoop();
2726 Level = mapSrcLoop(CurSrcLoop);
2727 return weakZeroDstSIVtest(SrcCoeff, SrcConst, DstConst, CurSrcLoop,
2728 CurSrcLoop, Level, Result, NewConstraint) ||
2729 gcdMIVtest(Src, Dst, Result);
2730 }
2731 if (DstAddRec) {
2732 const SCEV *DstConst = DstAddRec->getStart();
2733 const SCEV *DstCoeff = DstAddRec->getStepRecurrence(*SE);
2734 const SCEV *SrcConst = Src;
2735 const Loop *CurDstLoop = DstAddRec->getLoop();
2736 Level = mapDstLoop(CurDstLoop);
2737 return weakZeroSrcSIVtest(DstCoeff, SrcConst, DstConst, CurDstLoop,
2738 CurDstLoop, Level, Result, NewConstraint) ||
2739 gcdMIVtest(Src, Dst, Result);
2740 }
2741 llvm_unreachable("SIV test expected at least one AddRec");
2742 return false;
2743}
2744
2745// testRDIV -
2746// When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*j]
2747// where i and j are induction variables, c1 and c2 are loop invariant,
2748// and a1 and a2 are constant, we can solve it exactly with an easy adaptation
2749// of the Exact SIV test, the Restricted Double Index Variable (RDIV) test.
2750// It doesn't make sense to talk about distance or direction in this case,
2751// so there's no point in making special versions of the Strong SIV test or
2752// the Weak-crossing SIV test.
2753//
2754// With minor algebra, this test can also be used for things like
2755// [c1 + a1*i + a2*j][c2].
2756//
2757// Return true if dependence disproved.
2758bool DependenceInfo::testRDIV(const SCEV *Src, const SCEV *Dst,
2759 FullDependence &Result) const {
2760 // we have 3 possible situations here:
2761 // 1) [a*i + b] and [c*j + d]
2762 // 2) [a*i + c*j + b] and [d]
2763 // 3) [b] and [a*i + c*j + d]
2764 // We need to find what we've got and get organized
2765
2766 const SCEV *SrcConst, *DstConst;
2767 const SCEV *SrcCoeff, *DstCoeff;
2768 const Loop *SrcLoop, *DstLoop;
2769
2770 LLVM_DEBUG(dbgs() << " src = " << *Src << "\n");
2771 LLVM_DEBUG(dbgs() << " dst = " << *Dst << "\n");
2772 const SCEVAddRecExpr *SrcAddRec = dyn_cast<SCEVAddRecExpr>(Src);
2773 const SCEVAddRecExpr *DstAddRec = dyn_cast<SCEVAddRecExpr>(Dst);
2774 if (SrcAddRec && DstAddRec) {
2775 SrcConst = SrcAddRec->getStart();
2776 SrcCoeff = SrcAddRec->getStepRecurrence(*SE);
2777 SrcLoop = SrcAddRec->getLoop();
2778 DstConst = DstAddRec->getStart();
2779 DstCoeff = DstAddRec->getStepRecurrence(*SE);
2780 DstLoop = DstAddRec->getLoop();
2781 } else if (SrcAddRec) {
2782 if (const SCEVAddRecExpr *tmpAddRec =
2783 dyn_cast<SCEVAddRecExpr>(SrcAddRec->getStart())) {
2784 SrcConst = tmpAddRec->getStart();
2785 SrcCoeff = tmpAddRec->getStepRecurrence(*SE);
2786 SrcLoop = tmpAddRec->getLoop();
2787 DstConst = Dst;
2788 DstCoeff = SE->getNegativeSCEV(SrcAddRec->getStepRecurrence(*SE));
2789 DstLoop = SrcAddRec->getLoop();
2790 } else
2791 llvm_unreachable("RDIV reached by surprising SCEVs");
2792 } else if (DstAddRec) {
2793 if (const SCEVAddRecExpr *tmpAddRec =
2794 dyn_cast<SCEVAddRecExpr>(DstAddRec->getStart())) {
2795 DstConst = tmpAddRec->getStart();
2796 DstCoeff = tmpAddRec->getStepRecurrence(*SE);
2797 DstLoop = tmpAddRec->getLoop();
2798 SrcConst = Src;
2799 SrcCoeff = SE->getNegativeSCEV(DstAddRec->getStepRecurrence(*SE));
2800 SrcLoop = DstAddRec->getLoop();
2801 } else
2802 llvm_unreachable("RDIV reached by surprising SCEVs");
2803 } else
2804 llvm_unreachable("RDIV expected at least one AddRec");
2805 return exactRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, SrcLoop, DstLoop,
2806 Result) ||
2807 gcdMIVtest(Src, Dst, Result) ||
2808 symbolicRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, SrcLoop,
2809 DstLoop);
2810}
2811
2812// Tests the single-subscript MIV pair (Src and Dst) for dependence.
2813// Return true if dependence disproved.
2814// Can sometimes refine direction vectors.
2815bool DependenceInfo::testMIV(const SCEV *Src, const SCEV *Dst,
2816 const SmallBitVector &Loops,
2817 FullDependence &Result) const {
2818 LLVM_DEBUG(dbgs() << " src = " << *Src << "\n");
2819 LLVM_DEBUG(dbgs() << " dst = " << *Dst << "\n");
2820 Result.Consistent = false;
2821 return gcdMIVtest(Src, Dst, Result) ||
2822 banerjeeMIVtest(Src, Dst, Loops, Result);
2823}
2824
2825// Given a product, e.g., 10*X*Y, returns the first constant operand,
2826// in this case 10. If there is no constant part, returns std::nullopt.
2827static std::optional<APInt> getConstantPart(const SCEV *Expr) {
2828 if (const auto *Constant = dyn_cast<SCEVConstant>(Expr))
2829 return Constant->getAPInt();
2830 if (const auto *Product = dyn_cast<SCEVMulExpr>(Expr))
2831 if (const auto *Constant = dyn_cast<SCEVConstant>(Product->getOperand(0)))
2832 return Constant->getAPInt();
2833 return std::nullopt;
2834}
2835
2836bool DependenceInfo::accumulateCoefficientsGCD(const SCEV *Expr,
2837 const Loop *CurLoop,
2838 const SCEV *&CurLoopCoeff,
2839 APInt &RunningGCD) const {
2840 // If RunningGCD is already 1, exit early.
2841 // TODO: It might be better to continue the recursion to find CurLoopCoeff.
2842 if (RunningGCD == 1)
2843 return true;
2844
2845 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
2846 if (!AddRec) {
2847 assert(isLoopInvariant(Expr, CurLoop) &&
2848 "Expected loop invariant expression");
2849 return true;
2850 }
2851
2852 assert(AddRec->isAffine() && "Unexpected Expr");
2853 const SCEV *Start = AddRec->getStart();
2854 const SCEV *Step = AddRec->getStepRecurrence(*SE);
2855 if (AddRec->getLoop() == CurLoop) {
2856 CurLoopCoeff = Step;
2857 } else {
2858 std::optional<APInt> ConstCoeff = getConstantPart(Step);
2859
2860 // If the coefficient is the product of a constant and other stuff, we can
2861 // use the constant in the GCD computation.
2862 if (!ConstCoeff)
2863 return false;
2864
2865 // TODO: What happens if ConstCoeff is the "most negative" signed number
2866 // (e.g. -128 for 8 bit wide APInt)?
2867 RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff->abs());
2868 }
2869
2870 return accumulateCoefficientsGCD(Start, CurLoop, CurLoopCoeff, RunningGCD);
2871}
2872
2873//===----------------------------------------------------------------------===//
2874// gcdMIVtest -
2875// Tests an MIV subscript pair for dependence.
2876// Returns true if any possible dependence is disproved.
2877// Marks the result as inconsistent.
2878// Can sometimes disprove the equal direction for 1 or more loops,
2879// as discussed in Michael Wolfe's book,
2880// High Performance Compilers for Parallel Computing, page 235.
2881//
2882// We spend some effort (code!) to handle cases like
2883// [10*i + 5*N*j + 15*M + 6], where i and j are induction variables,
2884// but M and N are just loop-invariant variables.
2885// This should help us handle linearized subscripts;
2886// also makes this test a useful backup to the various SIV tests.
2887//
2888// It occurs to me that the presence of loop-invariant variables
2889// changes the nature of the test from "greatest common divisor"
2890// to "a common divisor".
2891bool DependenceInfo::gcdMIVtest(const SCEV *Src, const SCEV *Dst,
2892 FullDependence &Result) const {
2893 if (!isDependenceTestEnabled(DependenceTestType::GCDMIV))
2894 return false;
2895
2896 LLVM_DEBUG(dbgs() << "starting gcd\n");
2897 ++GCDapplications;
2898 unsigned BitWidth = SE->getTypeSizeInBits(Src->getType());
2899 APInt RunningGCD = APInt::getZero(BitWidth);
2900
2901 // Examine Src coefficients.
2902 // Compute running GCD and record source constant.
2903 // Because we're looking for the constant at the end of the chain,
2904 // we can't quit the loop just because the GCD == 1.
2905 const SCEV *Coefficients = Src;
2906 while (const SCEVAddRecExpr *AddRec =
2907 dyn_cast<SCEVAddRecExpr>(Coefficients)) {
2908 const SCEV *Coeff = AddRec->getStepRecurrence(*SE);
2909 // If the coefficient is the product of a constant and other stuff,
2910 // we can use the constant in the GCD computation.
2911 std::optional<APInt> ConstCoeff = getConstantPart(Coeff);
2912 if (!ConstCoeff)
2913 return false;
2914 RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff->abs());
2915 Coefficients = AddRec->getStart();
2916 }
2917 const SCEV *SrcConst = Coefficients;
2918
2919 // Examine Dst coefficients.
2920 // Compute running GCD and record destination constant.
2921 // Because we're looking for the constant at the end of the chain,
2922 // we can't quit the loop just because the GCD == 1.
2923 Coefficients = Dst;
2924 while (const SCEVAddRecExpr *AddRec =
2925 dyn_cast<SCEVAddRecExpr>(Coefficients)) {
2926 const SCEV *Coeff = AddRec->getStepRecurrence(*SE);
2927 // If the coefficient is the product of a constant and other stuff,
2928 // we can use the constant in the GCD computation.
2929 std::optional<APInt> ConstCoeff = getConstantPart(Coeff);
2930 if (!ConstCoeff)
2931 return false;
2932 RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff->abs());
2933 Coefficients = AddRec->getStart();
2934 }
2935 const SCEV *DstConst = Coefficients;
2936
2937 APInt ExtraGCD = APInt::getZero(BitWidth);
2938 const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
2939 LLVM_DEBUG(dbgs() << " Delta = " << *Delta << "\n");
2940 const SCEVConstant *Constant = dyn_cast<SCEVConstant>(Delta);
2941 if (const SCEVAddExpr *Sum = dyn_cast<SCEVAddExpr>(Delta)) {
2942 // If Delta is a sum of products, we may be able to make further progress.
2943 for (const SCEV *Operand : Sum->operands()) {
2944 if (isa<SCEVConstant>(Operand)) {
2945 assert(!Constant && "Surprised to find multiple constants");
2946 Constant = cast<SCEVConstant>(Operand);
2947 } else if (const SCEVMulExpr *Product = dyn_cast<SCEVMulExpr>(Operand)) {
2948 // Search for constant operand to participate in GCD;
2949 // If none found; return false.
2950 std::optional<APInt> ConstOp = getConstantPart(Product);
2951 if (!ConstOp)
2952 return false;
2953 ExtraGCD = APIntOps::GreatestCommonDivisor(ExtraGCD, ConstOp->abs());
2954 } else
2955 return false;
2956 }
2957 }
2958 if (!Constant)
2959 return false;
2960 APInt ConstDelta = cast<SCEVConstant>(Constant)->getAPInt();
2961 LLVM_DEBUG(dbgs() << " ConstDelta = " << ConstDelta << "\n");
2962 if (ConstDelta == 0)
2963 return false;
2964 RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ExtraGCD);
2965 LLVM_DEBUG(dbgs() << " RunningGCD = " << RunningGCD << "\n");
2966 APInt Remainder = ConstDelta.srem(RunningGCD);
2967 if (Remainder != 0) {
2968 ++GCDindependence;
2969 return true;
2970 }
2971
2972 // Try to disprove equal directions.
2973 // For example, given a subscript pair [3*i + 2*j] and [i' + 2*j' - 1],
2974 // the code above can't disprove the dependence because the GCD = 1.
2975 // So we consider what happen if i = i' and what happens if j = j'.
2976 // If i = i', we can simplify the subscript to [2*i + 2*j] and [2*j' - 1],
2977 // which is infeasible, so we can disallow the = direction for the i level.
2978 // Setting j = j' doesn't help matters, so we end up with a direction vector
2979 // of [<>, *]
2980 //
2981 // Given A[5*i + 10*j*M + 9*M*N] and A[15*i + 20*j*M - 21*N*M + 5],
2982 // we need to remember that the constant part is 5 and the RunningGCD should
2983 // be initialized to ExtraGCD = 30.
2984 LLVM_DEBUG(dbgs() << " ExtraGCD = " << ExtraGCD << '\n');
2985
2986 bool Improved = false;
2987 Coefficients = Src;
2988 while (const SCEVAddRecExpr *AddRec =
2989 dyn_cast<SCEVAddRecExpr>(Coefficients)) {
2990 Coefficients = AddRec->getStart();
2991 const Loop *CurLoop = AddRec->getLoop();
2992 RunningGCD = ExtraGCD;
2993 const SCEV *SrcCoeff = AddRec->getStepRecurrence(*SE);
2994 const SCEV *DstCoeff = SE->getMinusSCEV(SrcCoeff, SrcCoeff);
2995
2996 if (!accumulateCoefficientsGCD(Src, CurLoop, SrcCoeff, RunningGCD) ||
2997 !accumulateCoefficientsGCD(Dst, CurLoop, DstCoeff, RunningGCD))
2998 return false;
2999
3000 Delta = SE->getMinusSCEV(SrcCoeff, DstCoeff);
3001 // If the coefficient is the product of a constant and other stuff,
3002 // we can use the constant in the GCD computation.
3003 std::optional<APInt> ConstCoeff = getConstantPart(Delta);
3004 if (!ConstCoeff)
3005 // The difference of the two coefficients might not be a product
3006 // or constant, in which case we give up on this direction.
3007 continue;
3008 RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff->abs());
3009 LLVM_DEBUG(dbgs() << "\tRunningGCD = " << RunningGCD << "\n");
3010 if (RunningGCD != 0) {
3011 Remainder = ConstDelta.srem(RunningGCD);
3012 LLVM_DEBUG(dbgs() << "\tRemainder = " << Remainder << "\n");
3013 if (Remainder != 0) {
3014 unsigned Level = mapSrcLoop(CurLoop);
3015 Result.DV[Level - 1].Direction &= ~Dependence::DVEntry::EQ;
3016 Improved = true;
3017 }
3018 }
3019 }
3020 if (Improved)
3021 ++GCDsuccesses;
3022 LLVM_DEBUG(dbgs() << "all done\n");
3023 return false;
3024}
3025
3026//===----------------------------------------------------------------------===//
3027// banerjeeMIVtest -
3028// Use Banerjee's Inequalities to test an MIV subscript pair.
3029// (Wolfe, in the race-car book, calls this the Extreme Value Test.)
3030// Generally follows the discussion in Section 2.5.2 of
3031//
3032// Optimizing Supercompilers for Supercomputers
3033// Michael Wolfe
3034//
3035// The inequalities given on page 25 are simplified in that loops are
3036// normalized so that the lower bound is always 0 and the stride is always 1.
3037// For example, Wolfe gives
3038//
3039// LB^<_k = (A^-_k - B_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k
3040//
3041// where A_k is the coefficient of the kth index in the source subscript,
3042// B_k is the coefficient of the kth index in the destination subscript,
3043// U_k is the upper bound of the kth index, L_k is the lower bound of the Kth
3044// index, and N_k is the stride of the kth index. Since all loops are normalized
3045// by the SCEV package, N_k = 1 and L_k = 0, allowing us to simplify the
3046// equation to
3047//
3048// LB^<_k = (A^-_k - B_k)^- (U_k - 0 - 1) + (A_k - B_k)0 - B_k 1
3049// = (A^-_k - B_k)^- (U_k - 1) - B_k
3050//
3051// Similar simplifications are possible for the other equations.
3052//
3053// When we can't determine the number of iterations for a loop,
3054// we use NULL as an indicator for the worst case, infinity.
3055// When computing the upper bound, NULL denotes +inf;
3056// for the lower bound, NULL denotes -inf.
3057//
3058// Return true if dependence disproved.
3059bool DependenceInfo::banerjeeMIVtest(const SCEV *Src, const SCEV *Dst,
3060 const SmallBitVector &Loops,
3061 FullDependence &Result) const {
3062 if (!isDependenceTestEnabled(DependenceTestType::BanerjeeMIV))
3063 return false;
3064
3065 LLVM_DEBUG(dbgs() << "starting Banerjee\n");
3066 ++BanerjeeApplications;
3067 LLVM_DEBUG(dbgs() << " Src = " << *Src << '\n');
3068 const SCEV *A0;
3069 CoefficientInfo *A = collectCoeffInfo(Src, true, A0);
3070 LLVM_DEBUG(dbgs() << " Dst = " << *Dst << '\n');
3071 const SCEV *B0;
3072 CoefficientInfo *B = collectCoeffInfo(Dst, false, B0);
3073 BoundInfo *Bound = new BoundInfo[MaxLevels + 1];
3074 const SCEV *Delta = SE->getMinusSCEV(B0, A0);
3075 LLVM_DEBUG(dbgs() << "\tDelta = " << *Delta << '\n');
3076
3077 // Compute bounds for all the * directions.
3078 LLVM_DEBUG(dbgs() << "\tBounds[*]\n");
3079 for (unsigned K = 1; K <= MaxLevels; ++K) {
3080 Bound[K].Iterations = A[K].Iterations ? A[K].Iterations : B[K].Iterations;
3081 Bound[K].Direction = Dependence::DVEntry::ALL;
3082 Bound[K].DirSet = Dependence::DVEntry::NONE;
3083 findBoundsALL(A, B, Bound, K);
3084#ifndef NDEBUG
3085 LLVM_DEBUG(dbgs() << "\t " << K << '\t');
3086 if (Bound[K].Lower[Dependence::DVEntry::ALL])
3087 LLVM_DEBUG(dbgs() << *Bound[K].Lower[Dependence::DVEntry::ALL] << '\t');
3088 else
3089 LLVM_DEBUG(dbgs() << "-inf\t");
3090 if (Bound[K].Upper[Dependence::DVEntry::ALL])
3091 LLVM_DEBUG(dbgs() << *Bound[K].Upper[Dependence::DVEntry::ALL] << '\n');
3092 else
3093 LLVM_DEBUG(dbgs() << "+inf\n");
3094#endif
3095 }
3096
3097 // Test the *, *, *, ... case.
3098 bool Disproved = false;
3099 if (testBounds(Dependence::DVEntry::ALL, 0, Bound, Delta)) {
3100 // Explore the direction vector hierarchy.
3101 unsigned DepthExpanded = 0;
3102 unsigned NewDeps =
3103 exploreDirections(1, A, B, Bound, Loops, DepthExpanded, Delta);
3104 if (NewDeps > 0) {
3105 bool Improved = false;
3106 for (unsigned K = 1; K <= CommonLevels; ++K) {
3107 if (Loops[K]) {
3108 unsigned Old = Result.DV[K - 1].Direction;
3109 Result.DV[K - 1].Direction = Old & Bound[K].DirSet;
3110 Improved |= Old != Result.DV[K - 1].Direction;
3111 if (!Result.DV[K - 1].Direction) {
3112 Improved = false;
3113 Disproved = true;
3114 break;
3115 }
3116 }
3117 }
3118 if (Improved)
3119 ++BanerjeeSuccesses;
3120 } else {
3121 ++BanerjeeIndependence;
3122 Disproved = true;
3123 }
3124 } else {
3125 ++BanerjeeIndependence;
3126 Disproved = true;
3127 }
3128 delete[] Bound;
3129 delete[] A;
3130 delete[] B;
3131 return Disproved;
3132}
3133
3134// Hierarchically expands the direction vector
3135// search space, combining the directions of discovered dependences
3136// in the DirSet field of Bound. Returns the number of distinct
3137// dependences discovered. If the dependence is disproved,
3138// it will return 0.
3139unsigned DependenceInfo::exploreDirections(unsigned Level, CoefficientInfo *A,
3140 CoefficientInfo *B, BoundInfo *Bound,
3141 const SmallBitVector &Loops,
3142 unsigned &DepthExpanded,
3143 const SCEV *Delta) const {
3144 // This algorithm has worst case complexity of O(3^n), where 'n' is the number
3145 // of common loop levels. To avoid excessive compile-time, pessimize all the
3146 // results and immediately return when the number of common levels is beyond
3147 // the given threshold.
3148 if (CommonLevels > MIVMaxLevelThreshold) {
3149 LLVM_DEBUG(dbgs() << "Number of common levels exceeded the threshold. MIV "
3150 "direction exploration is terminated.\n");
3151 for (unsigned K = 1; K <= CommonLevels; ++K)
3152 if (Loops[K])
3153 Bound[K].DirSet = Dependence::DVEntry::ALL;
3154 return 1;
3155 }
3156
3157 if (Level > CommonLevels) {
3158 // record result
3159 LLVM_DEBUG(dbgs() << "\t[");
3160 for (unsigned K = 1; K <= CommonLevels; ++K) {
3161 if (Loops[K]) {
3162 Bound[K].DirSet |= Bound[K].Direction;
3163#ifndef NDEBUG
3164 switch (Bound[K].Direction) {
3166 LLVM_DEBUG(dbgs() << " <");
3167 break;
3169 LLVM_DEBUG(dbgs() << " =");
3170 break;
3172 LLVM_DEBUG(dbgs() << " >");
3173 break;
3175 LLVM_DEBUG(dbgs() << " *");
3176 break;
3177 default:
3178 llvm_unreachable("unexpected Bound[K].Direction");
3179 }
3180#endif
3181 }
3182 }
3183 LLVM_DEBUG(dbgs() << " ]\n");
3184 return 1;
3185 }
3186 if (Loops[Level]) {
3187 if (Level > DepthExpanded) {
3188 DepthExpanded = Level;
3189 // compute bounds for <, =, > at current level
3190 findBoundsLT(A, B, Bound, Level);
3191 findBoundsGT(A, B, Bound, Level);
3192 findBoundsEQ(A, B, Bound, Level);
3193#ifndef NDEBUG
3194 LLVM_DEBUG(dbgs() << "\tBound for level = " << Level << '\n');
3195 LLVM_DEBUG(dbgs() << "\t <\t");
3196 if (Bound[Level].Lower[Dependence::DVEntry::LT])
3197 LLVM_DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::LT]
3198 << '\t');
3199 else
3200 LLVM_DEBUG(dbgs() << "-inf\t");
3201 if (Bound[Level].Upper[Dependence::DVEntry::LT])
3202 LLVM_DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::LT]
3203 << '\n');
3204 else
3205 LLVM_DEBUG(dbgs() << "+inf\n");
3206 LLVM_DEBUG(dbgs() << "\t =\t");
3207 if (Bound[Level].Lower[Dependence::DVEntry::EQ])
3208 LLVM_DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::EQ]
3209 << '\t');
3210 else
3211 LLVM_DEBUG(dbgs() << "-inf\t");
3212 if (Bound[Level].Upper[Dependence::DVEntry::EQ])
3213 LLVM_DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::EQ]
3214 << '\n');
3215 else
3216 LLVM_DEBUG(dbgs() << "+inf\n");
3217 LLVM_DEBUG(dbgs() << "\t >\t");
3218 if (Bound[Level].Lower[Dependence::DVEntry::GT])
3219 LLVM_DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::GT]
3220 << '\t');
3221 else
3222 LLVM_DEBUG(dbgs() << "-inf\t");
3223 if (Bound[Level].Upper[Dependence::DVEntry::GT])
3224 LLVM_DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::GT]
3225 << '\n');
3226 else
3227 LLVM_DEBUG(dbgs() << "+inf\n");
3228#endif
3229 }
3230
3231 unsigned NewDeps = 0;
3232
3233 // test bounds for <, *, *, ...
3234 if (testBounds(Dependence::DVEntry::LT, Level, Bound, Delta))
3235 NewDeps += exploreDirections(Level + 1, A, B, Bound, Loops, DepthExpanded,
3236 Delta);
3237
3238 // Test bounds for =, *, *, ...
3239 if (testBounds(Dependence::DVEntry::EQ, Level, Bound, Delta))
3240 NewDeps += exploreDirections(Level + 1, A, B, Bound, Loops, DepthExpanded,
3241 Delta);
3242
3243 // test bounds for >, *, *, ...
3244 if (testBounds(Dependence::DVEntry::GT, Level, Bound, Delta))
3245 NewDeps += exploreDirections(Level + 1, A, B, Bound, Loops, DepthExpanded,
3246 Delta);
3247
3248 Bound[Level].Direction = Dependence::DVEntry::ALL;
3249 return NewDeps;
3250 } else
3251 return exploreDirections(Level + 1, A, B, Bound, Loops, DepthExpanded,
3252 Delta);
3253}
3254
3255// Returns true iff the current bounds are plausible.
3256bool DependenceInfo::testBounds(unsigned char DirKind, unsigned Level,
3257 BoundInfo *Bound, const SCEV *Delta) const {
3258 Bound[Level].Direction = DirKind;
3259 if (const SCEV *LowerBound = getLowerBound(Bound))
3260 if (isKnownPredicate(CmpInst::ICMP_SGT, LowerBound, Delta))
3261 return false;
3262 if (const SCEV *UpperBound = getUpperBound(Bound))
3263 if (isKnownPredicate(CmpInst::ICMP_SGT, Delta, UpperBound))
3264 return false;
3265 return true;
3266}
3267
3268// Computes the upper and lower bounds for level K
3269// using the * direction. Records them in Bound.
3270// Wolfe gives the equations
3271//
3272// LB^*_k = (A^-_k - B^+_k)(U_k - L_k) + (A_k - B_k)L_k
3273// UB^*_k = (A^+_k - B^-_k)(U_k - L_k) + (A_k - B_k)L_k
3274//
3275// Since we normalize loops, we can simplify these equations to
3276//
3277// LB^*_k = (A^-_k - B^+_k)U_k
3278// UB^*_k = (A^+_k - B^-_k)U_k
3279//
3280// We must be careful to handle the case where the upper bound is unknown.
3281// Note that the lower bound is always <= 0
3282// and the upper bound is always >= 0.
3283void DependenceInfo::findBoundsALL(CoefficientInfo *A, CoefficientInfo *B,
3284 BoundInfo *Bound, unsigned K) const {
3285 Bound[K].Lower[Dependence::DVEntry::ALL] =
3286 nullptr; // Default value = -infinity.
3287 Bound[K].Upper[Dependence::DVEntry::ALL] =
3288 nullptr; // Default value = +infinity.
3289 if (Bound[K].Iterations) {
3290 Bound[K].Lower[Dependence::DVEntry::ALL] = SE->getMulExpr(
3291 SE->getMinusSCEV(A[K].NegPart, B[K].PosPart), Bound[K].Iterations);
3292 Bound[K].Upper[Dependence::DVEntry::ALL] = SE->getMulExpr(
3293 SE->getMinusSCEV(A[K].PosPart, B[K].NegPart), Bound[K].Iterations);
3294 } else {
3295 // If the difference is 0, we won't need to know the number of iterations.
3296 if (isKnownPredicate(CmpInst::ICMP_EQ, A[K].NegPart, B[K].PosPart))
3297 Bound[K].Lower[Dependence::DVEntry::ALL] =
3298 SE->getZero(A[K].Coeff->getType());
3299 if (isKnownPredicate(CmpInst::ICMP_EQ, A[K].PosPart, B[K].NegPart))
3300 Bound[K].Upper[Dependence::DVEntry::ALL] =
3301 SE->getZero(A[K].Coeff->getType());
3302 }
3303}
3304
3305// Computes the upper and lower bounds for level K
3306// using the = direction. Records them in Bound.
3307// Wolfe gives the equations
3308//
3309// LB^=_k = (A_k - B_k)^- (U_k - L_k) + (A_k - B_k)L_k
3310// UB^=_k = (A_k - B_k)^+ (U_k - L_k) + (A_k - B_k)L_k
3311//
3312// Since we normalize loops, we can simplify these equations to
3313//
3314// LB^=_k = (A_k - B_k)^- U_k
3315// UB^=_k = (A_k - B_k)^+ U_k
3316//
3317// We must be careful to handle the case where the upper bound is unknown.
3318// Note that the lower bound is always <= 0
3319// and the upper bound is always >= 0.
3320void DependenceInfo::findBoundsEQ(CoefficientInfo *A, CoefficientInfo *B,
3321 BoundInfo *Bound, unsigned K) const {
3322 Bound[K].Lower[Dependence::DVEntry::EQ] =
3323 nullptr; // Default value = -infinity.
3324 Bound[K].Upper[Dependence::DVEntry::EQ] =
3325 nullptr; // Default value = +infinity.
3326 if (Bound[K].Iterations) {
3327 const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff);
3328 const SCEV *NegativePart = getNegativePart(Delta);
3329 Bound[K].Lower[Dependence::DVEntry::EQ] =
3330 SE->getMulExpr(NegativePart, Bound[K].Iterations);
3331 const SCEV *PositivePart = getPositivePart(Delta);
3332 Bound[K].Upper[Dependence::DVEntry::EQ] =
3333 SE->getMulExpr(PositivePart, Bound[K].Iterations);
3334 } else {
3335 // If the positive/negative part of the difference is 0,
3336 // we won't need to know the number of iterations.
3337 const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff);
3338 const SCEV *NegativePart = getNegativePart(Delta);
3339 if (NegativePart->isZero())
3340 Bound[K].Lower[Dependence::DVEntry::EQ] = NegativePart; // Zero
3341 const SCEV *PositivePart = getPositivePart(Delta);
3342 if (PositivePart->isZero())
3343 Bound[K].Upper[Dependence::DVEntry::EQ] = PositivePart; // Zero
3344 }
3345}
3346
3347// Computes the upper and lower bounds for level K
3348// using the < direction. Records them in Bound.
3349// Wolfe gives the equations
3350//
3351// LB^<_k = (A^-_k - B_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k
3352// UB^<_k = (A^+_k - B_k)^+ (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k
3353//
3354// Since we normalize loops, we can simplify these equations to
3355//
3356// LB^<_k = (A^-_k - B_k)^- (U_k - 1) - B_k
3357// UB^<_k = (A^+_k - B_k)^+ (U_k - 1) - B_k
3358//
3359// We must be careful to handle the case where the upper bound is unknown.
3360void DependenceInfo::findBoundsLT(CoefficientInfo *A, CoefficientInfo *B,
3361 BoundInfo *Bound, unsigned K) const {
3362 Bound[K].Lower[Dependence::DVEntry::LT] =
3363 nullptr; // Default value = -infinity.
3364 Bound[K].Upper[Dependence::DVEntry::LT] =
3365 nullptr; // Default value = +infinity.
3366 if (Bound[K].Iterations) {
3367 const SCEV *Iter_1 = SE->getMinusSCEV(
3368 Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType()));
3369 const SCEV *NegPart =
3370 getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff));
3371 Bound[K].Lower[Dependence::DVEntry::LT] =
3372 SE->getMinusSCEV(SE->getMulExpr(NegPart, Iter_1), B[K].Coeff);
3373 const SCEV *PosPart =
3374 getPositivePart(SE->getMinusSCEV(A[K].PosPart, B[K].Coeff));
3375 Bound[K].Upper[Dependence::DVEntry::LT] =
3376 SE->getMinusSCEV(SE->getMulExpr(PosPart, Iter_1), B[K].Coeff);
3377 } else {
3378 // If the positive/negative part of the difference is 0,
3379 // we won't need to know the number of iterations.
3380 const SCEV *NegPart =
3381 getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff));
3382 if (NegPart->isZero())
3383 Bound[K].Lower[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff);
3384 const SCEV *PosPart =
3385 getPositivePart(SE->getMinusSCEV(A[K].PosPart, B[K].Coeff));
3386 if (PosPart->isZero())
3387 Bound[K].Upper[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff);
3388 }
3389}
3390
3391// Computes the upper and lower bounds for level K
3392// using the > direction. Records them in Bound.
3393// Wolfe gives the equations
3394//
3395// LB^>_k = (A_k - B^+_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k + A_k N_k
3396// UB^>_k = (A_k - B^-_k)^+ (U_k - L_k - N_k) + (A_k - B_k)L_k + A_k N_k
3397//
3398// Since we normalize loops, we can simplify these equations to
3399//
3400// LB^>_k = (A_k - B^+_k)^- (U_k - 1) + A_k
3401// UB^>_k = (A_k - B^-_k)^+ (U_k - 1) + A_k
3402//
3403// We must be careful to handle the case where the upper bound is unknown.
3404void DependenceInfo::findBoundsGT(CoefficientInfo *A, CoefficientInfo *B,
3405 BoundInfo *Bound, unsigned K) const {
3406 Bound[K].Lower[Dependence::DVEntry::GT] =
3407 nullptr; // Default value = -infinity.
3408 Bound[K].Upper[Dependence::DVEntry::GT] =
3409 nullptr; // Default value = +infinity.
3410 if (Bound[K].Iterations) {
3411 const SCEV *Iter_1 = SE->getMinusSCEV(
3412 Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType()));
3413 const SCEV *NegPart =
3414 getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart));
3415 Bound[K].Lower[Dependence::DVEntry::GT] =
3416 SE->getAddExpr(SE->getMulExpr(NegPart, Iter_1), A[K].Coeff);
3417 const SCEV *PosPart =
3418 getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart));
3419 Bound[K].Upper[Dependence::DVEntry::GT] =
3420 SE->getAddExpr(SE->getMulExpr(PosPart, Iter_1), A[K].Coeff);
3421 } else {
3422 // If the positive/negative part of the difference is 0,
3423 // we won't need to know the number of iterations.
3424 const SCEV *NegPart =
3425 getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart));
3426 if (NegPart->isZero())
3427 Bound[K].Lower[Dependence::DVEntry::GT] = A[K].Coeff;
3428 const SCEV *PosPart =
3429 getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart));
3430 if (PosPart->isZero())
3431 Bound[K].Upper[Dependence::DVEntry::GT] = A[K].Coeff;
3432 }
3433}
3434
3435// X^+ = max(X, 0)
3436const SCEV *DependenceInfo::getPositivePart(const SCEV *X) const {
3437 return SE->getSMaxExpr(X, SE->getZero(X->getType()));
3438}
3439
3440// X^- = min(X, 0)
3441const SCEV *DependenceInfo::getNegativePart(const SCEV *X) const {
3442 return SE->getSMinExpr(X, SE->getZero(X->getType()));
3443}
3444
3445// Walks through the subscript,
3446// collecting each coefficient, the associated loop bounds,
3447// and recording its positive and negative parts for later use.
3448DependenceInfo::CoefficientInfo *
3449DependenceInfo::collectCoeffInfo(const SCEV *Subscript, bool SrcFlag,
3450 const SCEV *&Constant) const {
3451 const SCEV *Zero = SE->getZero(Subscript->getType());
3452 CoefficientInfo *CI = new CoefficientInfo[MaxLevels + 1];
3453 for (unsigned K = 1; K <= MaxLevels; ++K) {
3454 CI[K].Coeff = Zero;
3455 CI[K].PosPart = Zero;
3456 CI[K].NegPart = Zero;
3457 CI[K].Iterations = nullptr;
3458 }
3459 while (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Subscript)) {
3460 const Loop *L = AddRec->getLoop();
3461 unsigned K = SrcFlag ? mapSrcLoop(L) : mapDstLoop(L);
3462 CI[K].Coeff = AddRec->getStepRecurrence(*SE);
3463 CI[K].PosPart = getPositivePart(CI[K].Coeff);
3464 CI[K].NegPart = getNegativePart(CI[K].Coeff);
3465 CI[K].Iterations = collectUpperBound(L, Subscript->getType());
3466 Subscript = AddRec->getStart();
3467 }
3468 Constant = Subscript;
3469#ifndef NDEBUG
3470 LLVM_DEBUG(dbgs() << "\tCoefficient Info\n");
3471 for (unsigned K = 1; K <= MaxLevels; ++K) {
3472 LLVM_DEBUG(dbgs() << "\t " << K << "\t" << *CI[K].Coeff);
3473 LLVM_DEBUG(dbgs() << "\tPos Part = ");
3474 LLVM_DEBUG(dbgs() << *CI[K].PosPart);
3475 LLVM_DEBUG(dbgs() << "\tNeg Part = ");
3476 LLVM_DEBUG(dbgs() << *CI[K].NegPart);
3477 LLVM_DEBUG(dbgs() << "\tUpper Bound = ");
3478 if (CI[K].Iterations)
3479 LLVM_DEBUG(dbgs() << *CI[K].Iterations);
3480 else
3481 LLVM_DEBUG(dbgs() << "+inf");
3482 LLVM_DEBUG(dbgs() << '\n');
3483 }
3484 LLVM_DEBUG(dbgs() << "\t Constant = " << *Subscript << '\n');
3485#endif
3486 return CI;
3487}
3488
3489// Looks through all the bounds info and
3490// computes the lower bound given the current direction settings
3491// at each level. If the lower bound for any level is -inf,
3492// the result is -inf.
3493const SCEV *DependenceInfo::getLowerBound(BoundInfo *Bound) const {
3494 const SCEV *Sum = Bound[1].Lower[Bound[1].Direction];
3495 for (unsigned K = 2; Sum && K <= MaxLevels; ++K) {
3496 if (Bound[K].Lower[Bound[K].Direction])
3497 Sum = SE->getAddExpr(Sum, Bound[K].Lower[Bound[K].Direction]);
3498 else
3499 Sum = nullptr;
3500 }
3501 return Sum;
3502}
3503
3504// Looks through all the bounds info and
3505// computes the upper bound given the current direction settings
3506// at each level. If the upper bound at any level is +inf,
3507// the result is +inf.
3508const SCEV *DependenceInfo::getUpperBound(BoundInfo *Bound) const {
3509 const SCEV *Sum = Bound[1].Upper[Bound[1].Direction];
3510 for (unsigned K = 2; Sum && K <= MaxLevels; ++K) {
3511 if (Bound[K].Upper[Bound[K].Direction])
3512 Sum = SE->getAddExpr(Sum, Bound[K].Upper[Bound[K].Direction]);
3513 else
3514 Sum = nullptr;
3515 }
3516 return Sum;
3517}
3518
3519//===----------------------------------------------------------------------===//
3520// Constraint manipulation for Delta test.
3521
3522// Given a linear SCEV,
3523// return the coefficient (the step)
3524// corresponding to the specified loop.
3525// If there isn't one, return 0.
3526// For example, given a*i + b*j + c*k, finding the coefficient
3527// corresponding to the j loop would yield b.
3528const SCEV *DependenceInfo::findCoefficient(const SCEV *Expr,
3529 const Loop *TargetLoop) const {
3530 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
3531 if (!AddRec)
3532 return SE->getZero(Expr->getType());
3533 if (AddRec->getLoop() == TargetLoop)
3534 return AddRec->getStepRecurrence(*SE);
3535 return findCoefficient(AddRec->getStart(), TargetLoop);
3536}
3537
3538// Given a linear SCEV,
3539// return the SCEV given by zeroing out the coefficient
3540// corresponding to the specified loop.
3541// For example, given a*i + b*j + c*k, zeroing the coefficient
3542// corresponding to the j loop would yield a*i + c*k.
3543const SCEV *DependenceInfo::zeroCoefficient(const SCEV *Expr,
3544 const Loop *TargetLoop) const {
3545 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
3546 if (!AddRec)
3547 return Expr; // ignore
3548 if (AddRec->getLoop() == TargetLoop)
3549 return AddRec->getStart();
3550 return SE->getAddRecExpr(zeroCoefficient(AddRec->getStart(), TargetLoop),
3551 AddRec->getStepRecurrence(*SE), AddRec->getLoop(),
3552 AddRec->getNoWrapFlags());
3553}
3554
3555// Given a linear SCEV Expr,
3556// return the SCEV given by adding some Value to the
3557// coefficient corresponding to the specified TargetLoop.
3558// For example, given a*i + b*j + c*k, adding 1 to the coefficient
3559// corresponding to the j loop would yield a*i + (b+1)*j + c*k.
3560const SCEV *DependenceInfo::addToCoefficient(const SCEV *Expr,
3561 const Loop *TargetLoop,
3562 const SCEV *Value) const {
3563 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
3564 if (!AddRec) // create a new addRec
3565 return SE->getAddRecExpr(Expr, Value, TargetLoop,
3566 SCEV::FlagAnyWrap); // Worst case, with no info.
3567 if (AddRec->getLoop() == TargetLoop) {
3568 const SCEV *Sum = SE->getAddExpr(AddRec->getStepRecurrence(*SE), Value);
3569 if (Sum->isZero())
3570 return AddRec->getStart();
3571 return SE->getAddRecExpr(AddRec->getStart(), Sum, AddRec->getLoop(),
3572 AddRec->getNoWrapFlags());
3573 }
3574 if (SE->isLoopInvariant(AddRec, TargetLoop))
3575 return SE->getAddRecExpr(AddRec, Value, TargetLoop, SCEV::FlagAnyWrap);
3576 return SE->getAddRecExpr(
3577 addToCoefficient(AddRec->getStart(), TargetLoop, Value),
3578 AddRec->getStepRecurrence(*SE), AddRec->getLoop(),
3579 AddRec->getNoWrapFlags());
3580}
3581
3582// Review the constraints, looking for opportunities
3583// to simplify a subscript pair (Src and Dst).
3584// Return true if some simplification occurs.
3585// If the simplification isn't exact (that is, if it is conservative
3586// in terms of dependence), set consistent to false.
3587// Corresponds to Figure 5 from the paper
3588//
3589// Practical Dependence Testing
3590// Goff, Kennedy, Tseng
3591// PLDI 1991
3592bool DependenceInfo::propagate(const SCEV *&Src, const SCEV *&Dst,
3594 SmallVectorImpl<Constraint> &Constraints,
3595 bool &Consistent) {
3596 bool Result = false;
3597 for (unsigned LI : Loops.set_bits()) {
3598 LLVM_DEBUG(dbgs() << "\t Constraint[" << LI << "] is");
3599 LLVM_DEBUG(Constraints[LI].dump(dbgs()));
3600 if (Constraints[LI].isDistance())
3601 Result |= propagateDistance(Src, Dst, Constraints[LI], Consistent);
3602 else if (Constraints[LI].isLine())
3603 Result |= propagateLine(Src, Dst, Constraints[LI], Consistent);
3604 else if (Constraints[LI].isPoint())
3605 Result |= propagatePoint(Src, Dst, Constraints[LI]);
3606 }
3607 return Result;
3608}
3609
3610// Attempt to propagate a distance
3611// constraint into a subscript pair (Src and Dst).
3612// Return true if some simplification occurs.
3613// If the simplification isn't exact (that is, if it is conservative
3614// in terms of dependence), set consistent to false.
3615bool DependenceInfo::propagateDistance(const SCEV *&Src, const SCEV *&Dst,
3616 Constraint &CurConstraint,
3617 bool &Consistent) {
3618 const Loop *CurSrcLoop = CurConstraint.getAssociatedSrcLoop();
3619 const Loop *CurDstLoop = CurConstraint.getAssociatedDstLoop();
3620 LLVM_DEBUG(dbgs() << "\t\tSrc is " << *Src << "\n");
3621 const SCEV *A_K = findCoefficient(Src, CurSrcLoop);
3622 if (A_K->isZero())
3623 return false;
3624 const SCEV *DA_K = SE->getMulExpr(A_K, CurConstraint.getD());
3625 Src = SE->getMinusSCEV(Src, DA_K);
3626 Src = zeroCoefficient(Src, CurSrcLoop);
3627 LLVM_DEBUG(dbgs() << "\t\tnew Src is " << *Src << "\n");
3628 LLVM_DEBUG(dbgs() << "\t\tDst is " << *Dst << "\n");
3629 Dst = addToCoefficient(Dst, CurDstLoop, SE->getNegativeSCEV(A_K));
3630 LLVM_DEBUG(dbgs() << "\t\tnew Dst is " << *Dst << "\n");
3631 if (!findCoefficient(Dst, CurDstLoop)->isZero())
3632 Consistent = false;
3633 return true;
3634}
3635
3636// Attempt to propagate a line
3637// constraint into a subscript pair (Src and Dst).
3638// Return true if some simplification occurs.
3639// If the simplification isn't exact (that is, if it is conservative
3640// in terms of dependence), set consistent to false.
3641bool DependenceInfo::propagateLine(const SCEV *&Src, const SCEV *&Dst,
3642 Constraint &CurConstraint,
3643 bool &Consistent) {
3644 const Loop *CurSrcLoop = CurConstraint.getAssociatedSrcLoop();
3645 const Loop *CurDstLoop = CurConstraint.getAssociatedDstLoop();
3646 const SCEV *A = CurConstraint.getA();
3647 const SCEV *B = CurConstraint.getB();
3648 const SCEV *C = CurConstraint.getC();
3649 LLVM_DEBUG(dbgs() << "\t\tA = " << *A << ", B = " << *B << ", C = " << *C
3650 << "\n");
3651 LLVM_DEBUG(dbgs() << "\t\tSrc = " << *Src << "\n");
3652 LLVM_DEBUG(dbgs() << "\t\tDst = " << *Dst << "\n");
3653 if (A->isZero()) {
3654 const SCEVConstant *Bconst = dyn_cast<SCEVConstant>(B);
3655 const SCEVConstant *Cconst = dyn_cast<SCEVConstant>(C);
3656 if (!Bconst || !Cconst)
3657 return false;
3658 APInt Beta = Bconst->getAPInt();
3659 APInt Charlie = Cconst->getAPInt();
3660 APInt CdivB = Charlie.sdiv(Beta);
3661 assert(Charlie.srem(Beta) == 0 && "C should be evenly divisible by B");
3662 const SCEV *AP_K = findCoefficient(Dst, CurDstLoop);
3663 Src = SE->getMinusSCEV(Src, SE->getMulExpr(AP_K, SE->getConstant(CdivB)));
3664 Dst = zeroCoefficient(Dst, CurDstLoop);
3665 if (!findCoefficient(Src, CurSrcLoop)->isZero())
3666 Consistent = false;
3667 } else if (B->isZero()) {
3668 const SCEVConstant *Aconst = dyn_cast<SCEVConstant>(A);
3669 const SCEVConstant *Cconst = dyn_cast<SCEVConstant>(C);
3670 if (!Aconst || !Cconst)
3671 return false;
3672 APInt Alpha = Aconst->getAPInt();
3673 APInt Charlie = Cconst->getAPInt();
3674 APInt CdivA = Charlie.sdiv(Alpha);
3675 assert(Charlie.srem(Alpha) == 0 && "C should be evenly divisible by A");
3676 const SCEV *A_K = findCoefficient(Src, CurSrcLoop);
3677 Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, SE->getConstant(CdivA)));
3678 Src = zeroCoefficient(Src, CurSrcLoop);
3679 if (!findCoefficient(Dst, CurDstLoop)->isZero())
3680 Consistent = false;
3681 } else if (isKnownPredicate(CmpInst::ICMP_EQ, A, B)) {
3682 const SCEVConstant *Aconst = dyn_cast<SCEVConstant>(A);
3683 const SCEVConstant *Cconst = dyn_cast<SCEVConstant>(C);
3684 if (!Aconst || !Cconst)
3685 return false;
3686 APInt Alpha = Aconst->getAPInt();
3687 APInt Charlie = Cconst->getAPInt();
3688 APInt CdivA = Charlie.sdiv(Alpha);
3689 assert(Charlie.srem(Alpha) == 0 && "C should be evenly divisible by A");
3690 const SCEV *A_K = findCoefficient(Src, CurSrcLoop);
3691 Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, SE->getConstant(CdivA)));
3692 Src = zeroCoefficient(Src, CurSrcLoop);
3693 Dst = addToCoefficient(Dst, CurDstLoop, A_K);
3694 if (!findCoefficient(Dst, CurDstLoop)->isZero())
3695 Consistent = false;
3696 } else {
3697 // paper is incorrect here, or perhaps just misleading
3698 const SCEV *A_K = findCoefficient(Src, CurSrcLoop);
3699 Src = SE->getMulExpr(Src, A);
3700 Dst = SE->getMulExpr(Dst, A);
3701 Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, C));
3702 Src = zeroCoefficient(Src, CurSrcLoop);
3703 Dst = addToCoefficient(Dst, CurDstLoop, SE->getMulExpr(A_K, B));
3704 if (!findCoefficient(Dst, CurDstLoop)->isZero())
3705 Consistent = false;
3706 }
3707 LLVM_DEBUG(dbgs() << "\t\tnew Src = " << *Src << "\n");
3708 LLVM_DEBUG(dbgs() << "\t\tnew Dst = " << *Dst << "\n");
3709 return true;
3710}
3711
3712// Attempt to propagate a point
3713// constraint into a subscript pair (Src and Dst).
3714// Return true if some simplification occurs.
3715bool DependenceInfo::propagatePoint(const SCEV *&Src, const SCEV *&Dst,
3716 Constraint &CurConstraint) {
3717 const Loop *CurSrcLoop = CurConstraint.getAssociatedSrcLoop();
3718 const Loop *CurDstLoop = CurConstraint.getAssociatedDstLoop();
3719 const SCEV *A_K = findCoefficient(Src, CurSrcLoop);
3720 const SCEV *AP_K = findCoefficient(Dst, CurDstLoop);
3721 const SCEV *XA_K = SE->getMulExpr(A_K, CurConstraint.getX());
3722 const SCEV *YAP_K = SE->getMulExpr(AP_K, CurConstraint.getY());
3723 LLVM_DEBUG(dbgs() << "\t\tSrc is " << *Src << "\n");
3724 Src = SE->getAddExpr(Src, SE->getMinusSCEV(XA_K, YAP_K));
3725 Src = zeroCoefficient(Src, CurSrcLoop);
3726 LLVM_DEBUG(dbgs() << "\t\tnew Src is " << *Src << "\n");
3727 LLVM_DEBUG(dbgs() << "\t\tDst is " << *Dst << "\n");
3728 Dst = zeroCoefficient(Dst, CurDstLoop);
3729 LLVM_DEBUG(dbgs() << "\t\tnew Dst is " << *Dst << "\n");
3730 return true;
3731}
3732
3733// Update direction vector entry based on the current constraint.
3734void DependenceInfo::updateDirection(Dependence::DVEntry &Level,
3735 const Constraint &CurConstraint) const {
3736 LLVM_DEBUG(dbgs() << "\tUpdate direction, constraint =");
3737 LLVM_DEBUG(CurConstraint.dump(dbgs()));
3738 if (CurConstraint.isAny())
3739 ; // use defaults
3740 else if (CurConstraint.isDistance()) {
3741 // this one is consistent, the others aren't
3742 Level.Scalar = false;
3743 Level.Distance = CurConstraint.getD();
3744 unsigned NewDirection = Dependence::DVEntry::NONE;
3745 if (!SE->isKnownNonZero(Level.Distance)) // if may be zero
3746 NewDirection = Dependence::DVEntry::EQ;
3747 if (!SE->isKnownNonPositive(Level.Distance)) // if may be positive
3748 NewDirection |= Dependence::DVEntry::LT;
3749 if (!SE->isKnownNonNegative(Level.Distance)) // if may be negative
3750 NewDirection |= Dependence::DVEntry::GT;
3751 Level.Direction &= NewDirection;
3752 } else if (CurConstraint.isLine()) {
3753 Level.Scalar = false;
3754 Level.Distance = nullptr;
3755 // direction should be accurate
3756 } else if (CurConstraint.isPoint()) {
3757 Level.Scalar = false;
3758 Level.Distance = nullptr;
3759 unsigned NewDirection = Dependence::DVEntry::NONE;
3760 if (!isKnownPredicate(CmpInst::ICMP_NE, CurConstraint.getY(),
3761 CurConstraint.getX()))
3762 // if X may be = Y
3763 NewDirection |= Dependence::DVEntry::EQ;
3764 if (!isKnownPredicate(CmpInst::ICMP_SLE, CurConstraint.getY(),
3765 CurConstraint.getX()))
3766 // if Y may be > X
3767 NewDirection |= Dependence::DVEntry::LT;
3768 if (!isKnownPredicate(CmpInst::ICMP_SGE, CurConstraint.getY(),
3769 CurConstraint.getX()))
3770 // if Y may be < X
3771 NewDirection |= Dependence::DVEntry::GT;
3772 Level.Direction &= NewDirection;
3773 } else
3774 llvm_unreachable("constraint has unexpected kind");
3775}
3776
3777/// Check if we can delinearize the subscripts. If the SCEVs representing the
3778/// source and destination array references are recurrences on a nested loop,
3779/// this function flattens the nested recurrences into separate recurrences
3780/// for each loop level.
3781bool DependenceInfo::tryDelinearize(Instruction *Src, Instruction *Dst,
3783 assert(isLoadOrStore(Src) && "instruction is not load or store");
3784 assert(isLoadOrStore(Dst) && "instruction is not load or store");
3785 Value *SrcPtr = getLoadStorePointerOperand(Src);
3786 Value *DstPtr = getLoadStorePointerOperand(Dst);
3787 Loop *SrcLoop = LI->getLoopFor(Src->getParent());
3788 Loop *DstLoop = LI->getLoopFor(Dst->getParent());
3789 const SCEV *SrcAccessFn = SE->getSCEVAtScope(SrcPtr, SrcLoop);
3790 const SCEV *DstAccessFn = SE->getSCEVAtScope(DstPtr, DstLoop);
3791 const SCEVUnknown *SrcBase =
3792 dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccessFn));
3793 const SCEVUnknown *DstBase =
3794 dyn_cast<SCEVUnknown>(SE->getPointerBase(DstAccessFn));
3795
3796 if (!SrcBase || !DstBase || SrcBase != DstBase)
3797 return false;
3798
3799 SmallVector<const SCEV *, 4> SrcSubscripts, DstSubscripts;
3800
3801 if (!tryDelinearizeFixedSize(Src, Dst, SrcAccessFn, DstAccessFn,
3802 SrcSubscripts, DstSubscripts) &&
3803 !tryDelinearizeParametricSize(Src, Dst, SrcAccessFn, DstAccessFn,
3804 SrcSubscripts, DstSubscripts))
3805 return false;
3806
3807 assert(isLoopInvariant(SrcBase, SrcLoop) &&
3808 isLoopInvariant(DstBase, DstLoop) &&
3809 "Expected SrcBase and DstBase to be loop invariant");
3810
3811 int Size = SrcSubscripts.size();
3812 LLVM_DEBUG({
3813 dbgs() << "\nSrcSubscripts: ";
3814 for (int I = 0; I < Size; I++)
3815 dbgs() << *SrcSubscripts[I];
3816 dbgs() << "\nDstSubscripts: ";
3817 for (int I = 0; I < Size; I++)
3818 dbgs() << *DstSubscripts[I];
3819 });
3820
3821 // The delinearization transforms a single-subscript MIV dependence test into
3822 // a multi-subscript SIV dependence test that is easier to compute. So we
3823 // resize Pair to contain as many pairs of subscripts as the delinearization
3824 // has found, and then initialize the pairs following the delinearization.
3825 Pair.resize(Size);
3826 SCEVMonotonicityChecker MonChecker(SE);
3827 const Loop *OutermostLoop = SrcLoop ? SrcLoop->getOutermostLoop() : nullptr;
3828 for (int I = 0; I < Size; ++I) {
3829 Pair[I].Src = SrcSubscripts[I];
3830 Pair[I].Dst = DstSubscripts[I];
3831 unifySubscriptType(&Pair[I]);
3832
3834 if (MonChecker.checkMonotonicity(Pair[I].Src, OutermostLoop).isUnknown())
3835 return false;
3836 if (MonChecker.checkMonotonicity(Pair[I].Dst, OutermostLoop).isUnknown())
3837 return false;
3838 }
3839 }
3840
3841 return true;
3842}
3843
3844/// Try to delinearize \p SrcAccessFn and \p DstAccessFn if the underlying
3845/// arrays accessed are fixed-size arrays. Return true if delinearization was
3846/// successful.
3847bool DependenceInfo::tryDelinearizeFixedSize(
3848 Instruction *Src, Instruction *Dst, const SCEV *SrcAccessFn,
3849 const SCEV *DstAccessFn, SmallVectorImpl<const SCEV *> &SrcSubscripts,
3850 SmallVectorImpl<const SCEV *> &DstSubscripts) {
3851 LLVM_DEBUG({
3852 const SCEVUnknown *SrcBase =
3853 dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccessFn));
3854 const SCEVUnknown *DstBase =
3855 dyn_cast<SCEVUnknown>(SE->getPointerBase(DstAccessFn));
3856 assert(SrcBase && DstBase && SrcBase == DstBase &&
3857 "expected src and dst scev unknowns to be equal");
3858 });
3859
3860 SmallVector<int, 4> SrcSizes;
3861 SmallVector<int, 4> DstSizes;
3862 if (!tryDelinearizeFixedSizeImpl(SE, Src, SrcAccessFn, SrcSubscripts,
3863 SrcSizes) ||
3864 !tryDelinearizeFixedSizeImpl(SE, Dst, DstAccessFn, DstSubscripts,
3865 DstSizes))
3866 return false;
3867
3868 // Check that the two size arrays are non-empty and equal in length and
3869 // value.
3870 if (SrcSizes.size() != DstSizes.size() ||
3871 !std::equal(SrcSizes.begin(), SrcSizes.end(), DstSizes.begin())) {
3872 SrcSubscripts.clear();
3873 DstSubscripts.clear();
3874 return false;
3875 }
3876
3877 assert(SrcSubscripts.size() == DstSubscripts.size() &&
3878 "Expected equal number of entries in the list of SrcSubscripts and "
3879 "DstSubscripts.");
3880
3881 Value *SrcPtr = getLoadStorePointerOperand(Src);
3882 Value *DstPtr = getLoadStorePointerOperand(Dst);
3883
3884 // In general we cannot safely assume that the subscripts recovered from GEPs
3885 // are in the range of values defined for their corresponding array
3886 // dimensions. For example some C language usage/interpretation make it
3887 // impossible to verify this at compile-time. As such we can only delinearize
3888 // iff the subscripts are positive and are less than the range of the
3889 // dimension.
3891 auto AllIndicesInRange = [&](SmallVector<int, 4> &DimensionSizes,
3892 SmallVectorImpl<const SCEV *> &Subscripts,
3893 Value *Ptr) {
3894 size_t SSize = Subscripts.size();
3895 for (size_t I = 1; I < SSize; ++I) {
3896 const SCEV *S = Subscripts[I];
3897 if (!isKnownNonNegative(S, Ptr)) {
3898 LLVM_DEBUG({
3899 dbgs() << "Check failed: !isKnownNonNegative(S, Ptr)\n";
3900 dbgs() << " S: " << *S << "\n" << " Ptr: " << *Ptr << "\n";
3901 });
3902 return false;
3903 }
3904 if (auto *SType = dyn_cast<IntegerType>(S->getType())) {
3905 const SCEV *Range = SE->getConstant(
3906 ConstantInt::get(SType, DimensionSizes[I - 1], false));
3907 if (!isKnownLessThan(S, Range)) {
3908 LLVM_DEBUG({
3909 dbgs() << "Check failed: !isKnownLessThan(S, Range)\n";
3910 dbgs() << " S: " << *S << "\n"
3911 << " Range: " << *Range << "\n";
3912 });
3913 return false;
3914 }
3915 }
3916 }
3917 return true;
3918 };
3919
3920 if (!AllIndicesInRange(SrcSizes, SrcSubscripts, SrcPtr) ||
3921 !AllIndicesInRange(DstSizes, DstSubscripts, DstPtr)) {
3922 LLVM_DEBUG(dbgs() << "Check failed: AllIndicesInRange.\n");
3923 SrcSubscripts.clear();
3924 DstSubscripts.clear();
3925 return false;
3926 }
3927 }
3928 LLVM_DEBUG({
3929 dbgs() << "Delinearized subscripts of fixed-size array\n"
3930 << "SrcGEP:" << *SrcPtr << "\n"
3931 << "DstGEP:" << *DstPtr << "\n";
3932 });
3933 return true;
3934}
3935
3936bool DependenceInfo::tryDelinearizeParametricSize(
3937 Instruction *Src, Instruction *Dst, const SCEV *SrcAccessFn,
3938 const SCEV *DstAccessFn, SmallVectorImpl<const SCEV *> &SrcSubscripts,
3939 SmallVectorImpl<const SCEV *> &DstSubscripts) {
3940
3941 Value *SrcPtr = getLoadStorePointerOperand(Src);
3942 Value *DstPtr = getLoadStorePointerOperand(Dst);
3943 const SCEVUnknown *SrcBase =
3944 dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccessFn));
3945 const SCEVUnknown *DstBase =
3946 dyn_cast<SCEVUnknown>(SE->getPointerBase(DstAccessFn));
3947 assert(SrcBase && DstBase && SrcBase == DstBase &&
3948 "expected src and dst scev unknowns to be equal");
3949
3950 const SCEV *ElementSize = SE->getElementSize(Src);
3951 if (ElementSize != SE->getElementSize(Dst))
3952 return false;
3953
3954 const SCEV *SrcSCEV = SE->getMinusSCEV(SrcAccessFn, SrcBase);
3955 const SCEV *DstSCEV = SE->getMinusSCEV(DstAccessFn, DstBase);
3956
3957 const SCEVAddRecExpr *SrcAR = dyn_cast<SCEVAddRecExpr>(SrcSCEV);
3958 const SCEVAddRecExpr *DstAR = dyn_cast<SCEVAddRecExpr>(DstSCEV);
3959 if (!SrcAR || !DstAR || !SrcAR->isAffine() || !DstAR->isAffine())
3960 return false;
3961
3962 // First step: collect parametric terms in both array references.
3964 collectParametricTerms(*SE, SrcAR, Terms);
3965 collectParametricTerms(*SE, DstAR, Terms);
3966
3967 // Second step: find subscript sizes.
3969 findArrayDimensions(*SE, Terms, Sizes, ElementSize);
3970
3971 // Third step: compute the access functions for each subscript.
3972 computeAccessFunctions(*SE, SrcAR, SrcSubscripts, Sizes);
3973 computeAccessFunctions(*SE, DstAR, DstSubscripts, Sizes);
3974
3975 // Fail when there is only a subscript: that's a linearized access function.
3976 if (SrcSubscripts.size() < 2 || DstSubscripts.size() < 2 ||
3977 SrcSubscripts.size() != DstSubscripts.size())
3978 return false;
3979
3980 size_t Size = SrcSubscripts.size();
3981
3982 // Statically check that the array bounds are in-range. The first subscript we
3983 // don't have a size for and it cannot overflow into another subscript, so is
3984 // always safe. The others need to be 0 <= subscript[i] < bound, for both src
3985 // and dst.
3986 // FIXME: It may be better to record these sizes and add them as constraints
3987 // to the dependency checks.
3989 for (size_t I = 1; I < Size; ++I) {
3990 bool SNN = isKnownNonNegative(SrcSubscripts[I], SrcPtr);
3991 bool DNN = isKnownNonNegative(DstSubscripts[I], DstPtr);
3992 bool SLT = isKnownLessThan(SrcSubscripts[I], Sizes[I - 1]);
3993 bool DLT = isKnownLessThan(DstSubscripts[I], Sizes[I - 1]);
3994 if (SNN && DNN && SLT && DLT)
3995 continue;
3996
3997 LLVM_DEBUG({
3998 dbgs() << "Delinearization checks failed: can't prove the following\n";
3999 if (!SNN)
4000 dbgs() << " isKnownNonNegative(" << *SrcSubscripts[I] << ")\n";
4001 if (!DNN)
4002 dbgs() << " isKnownNonNegative(" << *DstSubscripts[I] << ")\n";
4003 if (!SLT)
4004 dbgs() << " isKnownLessThan(" << *SrcSubscripts[I] << ", "
4005 << *Sizes[I - 1] << ")\n";
4006 if (!DLT)
4007 dbgs() << " isKnownLessThan(" << *DstSubscripts[I] << ", "
4008 << *Sizes[I - 1] << ")\n";
4009 });
4010 return false;
4011 }
4012
4013 return true;
4014}
4015
4016//===----------------------------------------------------------------------===//
4017
4018#ifndef NDEBUG
4019// For debugging purposes, dump a small bit vector to dbgs().
4021 dbgs() << "{";
4022 for (unsigned VI : BV.set_bits()) {
4023 dbgs() << VI;
4024 if (BV.find_next(VI) >= 0)
4025 dbgs() << ' ';
4026 }
4027 dbgs() << "}\n";
4028}
4029#endif
4030
4032 FunctionAnalysisManager::Invalidator &Inv) {
4033 // Check if the analysis itself has been invalidated.
4034 auto PAC = PA.getChecker<DependenceAnalysis>();
4035 if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Function>>())
4036 return true;
4037
4038 // Check transitive dependencies.
4039 return Inv.invalidate<AAManager>(F, PA) ||
4040 Inv.invalidate<ScalarEvolutionAnalysis>(F, PA) ||
4041 Inv.invalidate<LoopAnalysis>(F, PA);
4042}
4043
4047
4048// depends -
4049// Returns NULL if there is no dependence.
4050// Otherwise, return a Dependence with as many details as possible.
4051// Corresponds to Section 3.1 in the paper
4052//
4053// Practical Dependence Testing
4054// Goff, Kennedy, Tseng
4055// PLDI 1991
4056//
4057// Care is required to keep the routine below, getSplitIteration(),
4058// up to date with respect to this routine.
4059std::unique_ptr<Dependence>
4061 bool UnderRuntimeAssumptions) {
4063 bool PossiblyLoopIndependent = true;
4064 if (Src == Dst)
4065 PossiblyLoopIndependent = false;
4066
4067 if (!(Src->mayReadOrWriteMemory() && Dst->mayReadOrWriteMemory()))
4068 // if both instructions don't reference memory, there's no dependence
4069 return nullptr;
4070
4071 if (!isLoadOrStore(Src) || !isLoadOrStore(Dst)) {
4072 // can only analyze simple loads and stores, i.e., no calls, invokes, etc.
4073 LLVM_DEBUG(dbgs() << "can only handle simple loads and stores\n");
4074 return std::make_unique<Dependence>(Src, Dst,
4075 SCEVUnionPredicate(Assume, *SE));
4076 }
4077
4078 const MemoryLocation &DstLoc = MemoryLocation::get(Dst);
4079 const MemoryLocation &SrcLoc = MemoryLocation::get(Src);
4080
4081 switch (underlyingObjectsAlias(AA, F->getDataLayout(), DstLoc, SrcLoc)) {
4084 // cannot analyse objects if we don't understand their aliasing.
4085 LLVM_DEBUG(dbgs() << "can't analyze may or partial alias\n");
4086 return std::make_unique<Dependence>(Src, Dst,
4087 SCEVUnionPredicate(Assume, *SE));
4089 // If the objects noalias, they are distinct, accesses are independent.
4090 LLVM_DEBUG(dbgs() << "no alias\n");
4091 return nullptr;
4093 break; // The underlying objects alias; test accesses for dependence.
4094 }
4095
4096 if (DstLoc.Size != SrcLoc.Size || !DstLoc.Size.isPrecise() ||
4097 !SrcLoc.Size.isPrecise()) {
4098 // The dependence test gets confused if the size of the memory accesses
4099 // differ.
4100 LLVM_DEBUG(dbgs() << "can't analyze must alias with different sizes\n");
4101 return std::make_unique<Dependence>(Src, Dst,
4102 SCEVUnionPredicate(Assume, *SE));
4103 }
4104
4105 Value *SrcPtr = getLoadStorePointerOperand(Src);
4106 Value *DstPtr = getLoadStorePointerOperand(Dst);
4107 const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
4108 const SCEV *DstSCEV = SE->getSCEV(DstPtr);
4109 LLVM_DEBUG(dbgs() << " SrcSCEV = " << *SrcSCEV << "\n");
4110 LLVM_DEBUG(dbgs() << " DstSCEV = " << *DstSCEV << "\n");
4111 const SCEV *SrcBase = SE->getPointerBase(SrcSCEV);
4112 const SCEV *DstBase = SE->getPointerBase(DstSCEV);
4113 if (SrcBase != DstBase) {
4114 // If two pointers have different bases, trying to analyze indexes won't
4115 // work; we can't compare them to each other. This can happen, for example,
4116 // if one is produced by an LCSSA PHI node.
4117 //
4118 // We check this upfront so we don't crash in cases where getMinusSCEV()
4119 // returns a SCEVCouldNotCompute.
4120 LLVM_DEBUG(dbgs() << "can't analyze SCEV with different pointer base\n");
4121 return std::make_unique<Dependence>(Src, Dst,
4122 SCEVUnionPredicate(Assume, *SE));
4123 }
4124
4125 // Even if the base pointers are the same, they may not be loop-invariant. It
4126 // could lead to incorrect results, as we're analyzing loop-carried
4127 // dependencies. Src and Dst can be in different loops, so we need to check
4128 // the base pointer is invariant in both loops.
4129 Loop *SrcLoop = LI->getLoopFor(Src->getParent());
4130 Loop *DstLoop = LI->getLoopFor(Dst->getParent());
4131 if (!isLoopInvariant(SrcBase, SrcLoop) ||
4132 !isLoopInvariant(DstBase, DstLoop)) {
4133 LLVM_DEBUG(dbgs() << "The base pointer is not loop invariant.\n");
4134 return std::make_unique<Dependence>(Src, Dst,
4135 SCEVUnionPredicate(Assume, *SE));
4136 }
4137
4138 uint64_t EltSize = SrcLoc.Size.toRaw();
4139 const SCEV *SrcEv = SE->getMinusSCEV(SrcSCEV, SrcBase);
4140 const SCEV *DstEv = SE->getMinusSCEV(DstSCEV, DstBase);
4141
4142 // Check that memory access offsets are multiples of element sizes.
4143 if (!SE->isKnownMultipleOf(SrcEv, EltSize, Assume) ||
4144 !SE->isKnownMultipleOf(DstEv, EltSize, Assume)) {
4145 LLVM_DEBUG(dbgs() << "can't analyze SCEV with different offsets\n");
4146 return std::make_unique<Dependence>(Src, Dst,
4147 SCEVUnionPredicate(Assume, *SE));
4148 }
4149
4150 if (!Assume.empty()) {
4151 if (!UnderRuntimeAssumptions)
4152 return std::make_unique<Dependence>(Src, Dst,
4153 SCEVUnionPredicate(Assume, *SE));
4154 // Add non-redundant assumptions.
4155 unsigned N = Assumptions.size();
4156 for (const SCEVPredicate *P : Assume) {
4157 bool Implied = false;
4158 for (unsigned I = 0; I != N && !Implied; I++)
4159 if (Assumptions[I]->implies(P, *SE))
4160 Implied = true;
4161 if (!Implied)
4162 Assumptions.push_back(P);
4163 }
4164 }
4165
4166 unsigned Pairs = 1;
4167 SmallVector<Subscript, 2> Pair(Pairs);
4168 Pair[0].Src = SrcEv;
4169 Pair[0].Dst = DstEv;
4170
4171 SCEVMonotonicityChecker MonChecker(SE);
4172 const Loop *OutermostLoop = SrcLoop ? SrcLoop->getOutermostLoop() : nullptr;
4174 if (MonChecker.checkMonotonicity(Pair[0].Src, OutermostLoop).isUnknown() ||
4175 MonChecker.checkMonotonicity(Pair[0].Dst, OutermostLoop).isUnknown())
4176 return std::make_unique<Dependence>(Src, Dst,
4177 SCEVUnionPredicate(Assume, *SE));
4178
4179 if (Delinearize) {
4180 if (tryDelinearize(Src, Dst, Pair)) {
4181 LLVM_DEBUG(dbgs() << " delinearized\n");
4182 Pairs = Pair.size();
4183 }
4184 }
4185
4186 // Establish loop nesting levels considering SameSD loops as common
4187 establishNestingLevels(Src, Dst);
4188
4189 LLVM_DEBUG(dbgs() << " common nesting levels = " << CommonLevels << "\n");
4190 LLVM_DEBUG(dbgs() << " maximum nesting levels = " << MaxLevels << "\n");
4191 LLVM_DEBUG(dbgs() << " SameSD nesting levels = " << SameSDLevels << "\n");
4192
4193 // Modify common levels to consider the SameSD levels in the tests
4194 CommonLevels += SameSDLevels;
4195 MaxLevels -= SameSDLevels;
4196 if (SameSDLevels > 0) {
4197 // Not all tests are handled yet over SameSD loops
4198 // Revoke if there are any tests other than ZIV, SIV or RDIV
4199 for (unsigned P = 0; P < Pairs; ++P) {
4201 Subscript::ClassificationKind TestClass =
4202 classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()),
4203 Pair[P].Dst, LI->getLoopFor(Dst->getParent()), Loops);
4204
4205 if (TestClass != Subscript::ZIV && TestClass != Subscript::SIV &&
4206 TestClass != Subscript::RDIV) {
4207 // Revert the levels to not consider the SameSD levels
4208 CommonLevels -= SameSDLevels;
4209 MaxLevels += SameSDLevels;
4210 SameSDLevels = 0;
4211 break;
4212 }
4213 }
4214 }
4215
4216 if (SameSDLevels > 0)
4217 SameSDLoopsCount++;
4218
4219 FullDependence Result(Src, Dst, SCEVUnionPredicate(Assume, *SE),
4220 PossiblyLoopIndependent, CommonLevels);
4221 ++TotalArrayPairs;
4222
4223 for (unsigned P = 0; P < Pairs; ++P) {
4224 assert(Pair[P].Src->getType()->isIntegerTy() && "Src must be an integer");
4225 assert(Pair[P].Dst->getType()->isIntegerTy() && "Dst must be an integer");
4226 Pair[P].Loops.resize(MaxLevels + 1);
4227 Pair[P].GroupLoops.resize(MaxLevels + 1);
4228 Pair[P].Group.resize(Pairs);
4229 removeMatchingExtensions(&Pair[P]);
4230 Pair[P].Classification =
4231 classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()), Pair[P].Dst,
4232 LI->getLoopFor(Dst->getParent()), Pair[P].Loops);
4233 Pair[P].GroupLoops = Pair[P].Loops;
4234 Pair[P].Group.set(P);
4235 LLVM_DEBUG(dbgs() << " subscript " << P << "\n");
4236 LLVM_DEBUG(dbgs() << "\tsrc = " << *Pair[P].Src << "\n");
4237 LLVM_DEBUG(dbgs() << "\tdst = " << *Pair[P].Dst << "\n");
4238 LLVM_DEBUG(dbgs() << "\tclass = " << Pair[P].Classification << "\n");
4239 LLVM_DEBUG(dbgs() << "\tloops = ");
4241 }
4242
4243 SmallBitVector Separable(Pairs);
4244 SmallBitVector Coupled(Pairs);
4245
4246 // Partition subscripts into separable and minimally-coupled groups
4247 // Algorithm in paper is algorithmically better;
4248 // this may be faster in practice. Check someday.
4249 //
4250 // Here's an example of how it works. Consider this code:
4251 //
4252 // for (i = ...) {
4253 // for (j = ...) {
4254 // for (k = ...) {
4255 // for (l = ...) {
4256 // for (m = ...) {
4257 // A[i][j][k][m] = ...;
4258 // ... = A[0][j][l][i + j];
4259 // }
4260 // }
4261 // }
4262 // }
4263 // }
4264 //
4265 // There are 4 subscripts here:
4266 // 0 [i] and [0]
4267 // 1 [j] and [j]
4268 // 2 [k] and [l]
4269 // 3 [m] and [i + j]
4270 //
4271 // We've already classified each subscript pair as ZIV, SIV, etc.,
4272 // and collected all the loops mentioned by pair P in Pair[P].Loops.
4273 // In addition, we've initialized Pair[P].GroupLoops to Pair[P].Loops
4274 // and set Pair[P].Group = {P}.
4275 //
4276 // Src Dst Classification Loops GroupLoops Group
4277 // 0 [i] [0] SIV {1} {1} {0}
4278 // 1 [j] [j] SIV {2} {2} {1}
4279 // 2 [k] [l] RDIV {3,4} {3,4} {2}
4280 // 3 [m] [i + j] MIV {1,2,5} {1,2,5} {3}
4281 //
4282 // For each subscript SI 0 .. 3, we consider each remaining subscript, SJ.
4283 // So, 0 is compared against 1, 2, and 3; 1 is compared against 2 and 3, etc.
4284 //
4285 // We begin by comparing 0 and 1. The intersection of the GroupLoops is empty.
4286 // Next, 0 and 2. Again, the intersection of their GroupLoops is empty.
4287 // Next 0 and 3. The intersection of their GroupLoop = {1}, not empty,
4288 // so Pair[3].Group = {0,3} and Done = false (that is, 0 will not be added
4289 // to either Separable or Coupled).
4290 //
4291 // Next, we consider 1 and 2. The intersection of the GroupLoops is empty.
4292 // Next, 1 and 3. The intersection of their GroupLoops = {2}, not empty,
4293 // so Pair[3].Group = {0, 1, 3} and Done = false.
4294 //
4295 // Next, we compare 2 against 3. The intersection of the GroupLoops is empty.
4296 // Since Done remains true, we add 2 to the set of Separable pairs.
4297 //
4298 // Finally, we consider 3. There's nothing to compare it with,
4299 // so Done remains true and we add it to the Coupled set.
4300 // Pair[3].Group = {0, 1, 3} and GroupLoops = {1, 2, 5}.
4301 //
4302 // In the end, we've got 1 separable subscript and 1 coupled group.
4303 for (unsigned SI = 0; SI < Pairs; ++SI) {
4304 if (Pair[SI].Classification == Subscript::NonLinear) {
4305 // ignore these, but collect loops for later
4306 ++NonlinearSubscriptPairs;
4307 collectCommonLoops(Pair[SI].Src, LI->getLoopFor(Src->getParent()),
4308 Pair[SI].Loops);
4309 collectCommonLoops(Pair[SI].Dst, LI->getLoopFor(Dst->getParent()),
4310 Pair[SI].Loops);
4311 Result.Consistent = false;
4312 } else if (Pair[SI].Classification == Subscript::ZIV) {
4313 // always separable
4314 Separable.set(SI);
4315 } else {
4316 // SIV, RDIV, or MIV, so check for coupled group
4317 bool Done = true;
4318 for (unsigned SJ = SI + 1; SJ < Pairs; ++SJ) {
4319 SmallBitVector Intersection = Pair[SI].GroupLoops;
4320 Intersection &= Pair[SJ].GroupLoops;
4321 if (Intersection.any()) {
4322 // accumulate set of all the loops in group
4323 Pair[SJ].GroupLoops |= Pair[SI].GroupLoops;
4324 // accumulate set of all subscripts in group
4325 Pair[SJ].Group |= Pair[SI].Group;
4326 Done = false;
4327 }
4328 }
4329 if (Done) {
4330 if (Pair[SI].Group.count() == 1) {
4331 Separable.set(SI);
4332 ++SeparableSubscriptPairs;
4333 } else {
4334 Coupled.set(SI);
4335 ++CoupledSubscriptPairs;
4336 }
4337 }
4338 }
4339 }
4340
4341 LLVM_DEBUG(dbgs() << " Separable = ");
4342 LLVM_DEBUG(dumpSmallBitVector(Separable));
4343 LLVM_DEBUG(dbgs() << " Coupled = ");
4345
4346 Constraint NewConstraint;
4347 NewConstraint.setAny(SE);
4348
4349 // test separable subscripts
4350 for (unsigned SI : Separable.set_bits()) {
4351 LLVM_DEBUG(dbgs() << "testing subscript " << SI);
4352 switch (Pair[SI].Classification) {
4353 case Subscript::ZIV:
4354 LLVM_DEBUG(dbgs() << ", ZIV\n");
4355 if (testZIV(Pair[SI].Src, Pair[SI].Dst, Result))
4356 return nullptr;
4357 break;
4358 case Subscript::SIV: {
4359 LLVM_DEBUG(dbgs() << ", SIV\n");
4360 unsigned Level;
4361 const SCEV *SplitIter = nullptr;
4362 if (testSIV(Pair[SI].Src, Pair[SI].Dst, Level, Result, NewConstraint,
4363 SplitIter))
4364 return nullptr;
4365 break;
4366 }
4367 case Subscript::RDIV:
4368 LLVM_DEBUG(dbgs() << ", RDIV\n");
4369 if (testRDIV(Pair[SI].Src, Pair[SI].Dst, Result))
4370 return nullptr;
4371 break;
4372 case Subscript::MIV:
4373 LLVM_DEBUG(dbgs() << ", MIV\n");
4374 if (testMIV(Pair[SI].Src, Pair[SI].Dst, Pair[SI].Loops, Result))
4375 return nullptr;
4376 break;
4377 default:
4378 llvm_unreachable("subscript has unexpected classification");
4379 }
4380 }
4381
4382 if (Coupled.count()) {
4383 // test coupled subscript groups
4384 LLVM_DEBUG(dbgs() << "starting on coupled subscripts\n");
4385 LLVM_DEBUG(dbgs() << "MaxLevels + 1 = " << MaxLevels + 1 << "\n");
4386 SmallVector<Constraint, 4> Constraints(MaxLevels + 1);
4387 for (unsigned II = 0; II <= MaxLevels; ++II)
4388 Constraints[II].setAny(SE);
4389 for (unsigned SI : Coupled.set_bits()) {
4390 LLVM_DEBUG(dbgs() << "testing subscript group " << SI << " { ");
4391 SmallBitVector Group(Pair[SI].Group);
4392 SmallBitVector Sivs(Pairs);
4393 SmallBitVector Mivs(Pairs);
4394 SmallBitVector ConstrainedLevels(MaxLevels + 1);
4395 SmallVector<Subscript *, 4> PairsInGroup;
4396 for (unsigned SJ : Group.set_bits()) {
4397 LLVM_DEBUG(dbgs() << SJ << " ");
4398 if (Pair[SJ].Classification == Subscript::SIV)
4399 Sivs.set(SJ);
4400 else
4401 Mivs.set(SJ);
4402 PairsInGroup.push_back(&Pair[SJ]);
4403 }
4404 unifySubscriptType(PairsInGroup);
4405 LLVM_DEBUG(dbgs() << "}\n");
4406 while (Sivs.any()) {
4407 bool Changed = false;
4408 for (unsigned SJ : Sivs.set_bits()) {
4409 LLVM_DEBUG(dbgs() << "testing subscript " << SJ << ", SIV\n");
4410 // SJ is an SIV subscript that's part of the current coupled group
4411 unsigned Level;
4412 const SCEV *SplitIter = nullptr;
4413 LLVM_DEBUG(dbgs() << "SIV\n");
4414 if (testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, Result, NewConstraint,
4415 SplitIter))
4416 return nullptr;
4417 ConstrainedLevels.set(Level);
4418 if (intersectConstraints(&Constraints[Level], &NewConstraint)) {
4419 if (Constraints[Level].isEmpty()) {
4420 ++DeltaIndependence;
4421 return nullptr;
4422 }
4423 Changed = true;
4424 }
4425 Sivs.reset(SJ);
4426 }
4427 if (Changed) {
4428 // propagate, possibly creating new SIVs and ZIVs
4429 LLVM_DEBUG(dbgs() << " propagating\n");
4430 LLVM_DEBUG(dbgs() << "\tMivs = ");
4432 for (unsigned SJ : Mivs.set_bits()) {
4433 // SJ is an MIV subscript that's part of the current coupled group
4434 LLVM_DEBUG(dbgs() << "\tSJ = " << SJ << "\n");
4435 if (propagate(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops,
4436 Constraints, Result.Consistent)) {
4437 LLVM_DEBUG(dbgs() << "\t Changed\n");
4438 ++DeltaPropagations;
4439 Pair[SJ].Classification = classifyPair(
4440 Pair[SJ].Src, LI->getLoopFor(Src->getParent()), Pair[SJ].Dst,
4441 LI->getLoopFor(Dst->getParent()), Pair[SJ].Loops);
4442 switch (Pair[SJ].Classification) {
4443 case Subscript::ZIV:
4444 LLVM_DEBUG(dbgs() << "ZIV\n");
4445 if (testZIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
4446 return nullptr;
4447 Mivs.reset(SJ);
4448 break;
4449 case Subscript::SIV:
4450 Sivs.set(SJ);
4451 Mivs.reset(SJ);
4452 break;
4453 case Subscript::RDIV:
4454 case Subscript::MIV:
4455 break;
4456 default:
4457 llvm_unreachable("bad subscript classification");
4458 }
4459 }
4460 }
4461 }
4462 }
4463
4464 // test & propagate remaining RDIVs
4465 for (unsigned SJ : Mivs.set_bits()) {
4466 if (Pair[SJ].Classification == Subscript::RDIV) {
4467 LLVM_DEBUG(dbgs() << "RDIV test\n");
4468 if (testRDIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
4469 return nullptr;
4470 // I don't yet understand how to propagate RDIV results
4471 Mivs.reset(SJ);
4472 }
4473 }
4474
4475 // test remaining MIVs
4476 // This code is temporary.
4477 // Better to somehow test all remaining subscripts simultaneously.
4478 for (unsigned SJ : Mivs.set_bits()) {
4479 if (Pair[SJ].Classification == Subscript::MIV) {
4480 LLVM_DEBUG(dbgs() << "MIV test\n");
4481 if (testMIV(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops, Result))
4482 return nullptr;
4483 } else
4484 llvm_unreachable("expected only MIV subscripts at this point");
4485 }
4486
4487 // update Result.DV from constraint vector
4488 LLVM_DEBUG(dbgs() << " updating\n");
4489 for (unsigned SJ : ConstrainedLevels.set_bits()) {
4490 if (SJ > CommonLevels)
4491 break;
4492 updateDirection(Result.DV[SJ - 1], Constraints[SJ]);
4493 if (Result.DV[SJ - 1].Direction == Dependence::DVEntry::NONE)
4494 return nullptr;
4495 }
4496 }
4497 }
4498
4499 // Make sure the Scalar flags are set correctly.
4500 SmallBitVector CompleteLoops(MaxLevels + 1);
4501 for (unsigned SI = 0; SI < Pairs; ++SI)
4502 CompleteLoops |= Pair[SI].Loops;
4503 for (unsigned II = 1; II <= CommonLevels; ++II)
4504 if (CompleteLoops[II])
4505 Result.DV[II - 1].Scalar = false;
4506
4507 // Set the distance to zero if the direction is EQ.
4508 // TODO: Ideally, the distance should be set to 0 immediately simultaneously
4509 // with the corresponding direction being set to EQ.
4510 for (unsigned II = 1; II <= Result.getLevels(); ++II) {
4511 if (Result.getDirection(II) == Dependence::DVEntry::EQ) {
4512 if (Result.DV[II - 1].Distance == nullptr)
4513 Result.DV[II - 1].Distance = SE->getZero(SrcSCEV->getType());
4514 else
4515 assert(Result.DV[II - 1].Distance->isZero() &&
4516 "Inconsistency between distance and direction");
4517 }
4518
4519#ifndef NDEBUG
4520 // Check that the converse (i.e., if the distance is zero, then the
4521 // direction is EQ) holds.
4522 const SCEV *Distance = Result.getDistance(II);
4523 if (Distance && Distance->isZero())
4524 assert(Result.getDirection(II) == Dependence::DVEntry::EQ &&
4525 "Distance is zero, but direction is not EQ");
4526#endif
4527 }
4528
4529 if (SameSDLevels > 0) {
4530 // Extracting SameSD levels from the common levels
4531 // Reverting CommonLevels and MaxLevels to their original values
4532 assert(CommonLevels >= SameSDLevels);
4533 CommonLevels -= SameSDLevels;
4534 MaxLevels += SameSDLevels;
4535 std::unique_ptr<FullDependence::DVEntry[]> DV, DVSameSD;
4536 DV = std::make_unique<FullDependence::DVEntry[]>(CommonLevels);
4537 DVSameSD = std::make_unique<FullDependence::DVEntry[]>(SameSDLevels);
4538 for (unsigned Level = 0; Level < CommonLevels; ++Level)
4539 DV[Level] = Result.DV[Level];
4540 for (unsigned Level = 0; Level < SameSDLevels; ++Level)
4541 DVSameSD[Level] = Result.DV[CommonLevels + Level];
4542 Result.DV = std::move(DV);
4543 Result.DVSameSD = std::move(DVSameSD);
4544 Result.Levels = CommonLevels;
4545 Result.SameSDLevels = SameSDLevels;
4546 // Result is not consistent if it considers SameSD levels
4547 Result.Consistent = false;
4548 }
4549
4550 if (PossiblyLoopIndependent) {
4551 // Make sure the LoopIndependent flag is set correctly.
4552 // All directions must include equal, otherwise no
4553 // loop-independent dependence is possible.
4554 for (unsigned II = 1; II <= CommonLevels; ++II) {
4555 if (!(Result.getDirection(II) & Dependence::DVEntry::EQ)) {
4556 Result.LoopIndependent = false;
4557 break;
4558 }
4559 }
4560 } else {
4561 // On the other hand, if all directions are equal and there's no
4562 // loop-independent dependence possible, then no dependence exists.
4563 bool AllEqual = true;
4564 for (unsigned II = 1; II <= CommonLevels; ++II) {
4565 if (Result.getDirection(II) != Dependence::DVEntry::EQ) {
4566 AllEqual = false;
4567 break;
4568 }
4569 }
4570 if (AllEqual)
4571 return nullptr;
4572 }
4573
4574 return std::make_unique<FullDependence>(std::move(Result));
4575}
4576
4577//===----------------------------------------------------------------------===//
4578// getSplitIteration -
4579// Rather than spend rarely-used space recording the splitting iteration
4580// during the Weak-Crossing SIV test, we re-compute it on demand.
4581// The re-computation is basically a repeat of the entire dependence test,
4582// though simplified since we know that the dependence exists.
4583// It's tedious, since we must go through all propagations, etc.
4584//
4585// Care is required to keep this code up to date with respect to the routine
4586// above, depends().
4587//
4588// Generally, the dependence analyzer will be used to build
4589// a dependence graph for a function (basically a map from instructions
4590// to dependences). Looking for cycles in the graph shows us loops
4591// that cannot be trivially vectorized/parallelized.
4592//
4593// We can try to improve the situation by examining all the dependences
4594// that make up the cycle, looking for ones we can break.
4595// Sometimes, peeling the first or last iteration of a loop will break
4596// dependences, and we've got flags for those possibilities.
4597// Sometimes, splitting a loop at some other iteration will do the trick,
4598// and we've got a flag for that case. Rather than waste the space to
4599// record the exact iteration (since we rarely know), we provide
4600// a method that calculates the iteration. It's a drag that it must work
4601// from scratch, but wonderful in that it's possible.
4602//
4603// Here's an example:
4604//
4605// for (i = 0; i < 10; i++)
4606// A[i] = ...
4607// ... = A[11 - i]
4608//
4609// There's a loop-carried flow dependence from the store to the load,
4610// found by the weak-crossing SIV test. The dependence will have a flag,
4611// indicating that the dependence can be broken by splitting the loop.
4612// Calling getSplitIteration will return 5.
4613// Splitting the loop breaks the dependence, like so:
4614//
4615// for (i = 0; i <= 5; i++)
4616// A[i] = ...
4617// ... = A[11 - i]
4618// for (i = 6; i < 10; i++)
4619// A[i] = ...
4620// ... = A[11 - i]
4621//
4622// breaks the dependence and allows us to vectorize/parallelize
4623// both loops.
4625 unsigned SplitLevel) {
4626 assert(Dep.isSplitable(SplitLevel) &&
4627 "Dep should be splitable at SplitLevel");
4628 Instruction *Src = Dep.getSrc();
4629 Instruction *Dst = Dep.getDst();
4630 assert(Src->mayReadFromMemory() || Src->mayWriteToMemory());
4631 assert(Dst->mayReadFromMemory() || Dst->mayWriteToMemory());
4632 assert(isLoadOrStore(Src));
4633 assert(isLoadOrStore(Dst));
4634 Value *SrcPtr = getLoadStorePointerOperand(Src);
4635 Value *DstPtr = getLoadStorePointerOperand(Dst);
4637 AA, F->getDataLayout(), MemoryLocation::get(Dst),
4639
4640 // establish loop nesting levels
4641 establishNestingLevels(Src, Dst);
4642
4643 FullDependence Result(Src, Dst, Dep.Assumptions, false, CommonLevels);
4644
4645 unsigned Pairs = 1;
4646 SmallVector<Subscript, 2> Pair(Pairs);
4647 const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
4648 const SCEV *DstSCEV = SE->getSCEV(DstPtr);
4649 Pair[0].Src = SE->removePointerBase(SrcSCEV);
4650 Pair[0].Dst = SE->removePointerBase(DstSCEV);
4651
4652 if (Delinearize) {
4653 if (tryDelinearize(Src, Dst, Pair)) {
4654 LLVM_DEBUG(dbgs() << " delinearized\n");
4655 Pairs = Pair.size();
4656 }
4657 }
4658
4659 for (unsigned P = 0; P < Pairs; ++P) {
4660 assert(Pair[P].Src->getType()->isIntegerTy() && "Src must be an integer");
4661 assert(Pair[P].Dst->getType()->isIntegerTy() && "Dst must be an integer");
4662 Pair[P].Loops.resize(MaxLevels + 1);
4663 Pair[P].GroupLoops.resize(MaxLevels + 1);
4664 Pair[P].Group.resize(Pairs);
4665 removeMatchingExtensions(&Pair[P]);
4666 Pair[P].Classification =
4667 classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()), Pair[P].Dst,
4668 LI->getLoopFor(Dst->getParent()), Pair[P].Loops);
4669 Pair[P].GroupLoops = Pair[P].Loops;
4670 Pair[P].Group.set(P);
4671 }
4672
4673 SmallBitVector Separable(Pairs);
4674 SmallBitVector Coupled(Pairs);
4675
4676 // partition subscripts into separable and minimally-coupled groups
4677 for (unsigned SI = 0; SI < Pairs; ++SI) {
4678 if (Pair[SI].Classification == Subscript::NonLinear) {
4679 // ignore these, but collect loops for later
4680 collectCommonLoops(Pair[SI].Src, LI->getLoopFor(Src->getParent()),
4681 Pair[SI].Loops);
4682 collectCommonLoops(Pair[SI].Dst, LI->getLoopFor(Dst->getParent()),
4683 Pair[SI].Loops);
4684 Result.Consistent = false;
4685 } else if (Pair[SI].Classification == Subscript::ZIV)
4686 Separable.set(SI);
4687 else {
4688 // SIV, RDIV, or MIV, so check for coupled group
4689 bool Done = true;
4690 for (unsigned SJ = SI + 1; SJ < Pairs; ++SJ) {
4691 SmallBitVector Intersection = Pair[SI].GroupLoops;
4692 Intersection &= Pair[SJ].GroupLoops;
4693 if (Intersection.any()) {
4694 // accumulate set of all the loops in group
4695 Pair[SJ].GroupLoops |= Pair[SI].GroupLoops;
4696 // accumulate set of all subscripts in group
4697 Pair[SJ].Group |= Pair[SI].Group;
4698 Done = false;
4699 }
4700 }
4701 if (Done) {
4702 if (Pair[SI].Group.count() == 1)
4703 Separable.set(SI);
4704 else
4705 Coupled.set(SI);
4706 }
4707 }
4708 }
4709
4710 Constraint NewConstraint;
4711 NewConstraint.setAny(SE);
4712
4713 // test separable subscripts
4714 for (unsigned SI : Separable.set_bits()) {
4715 switch (Pair[SI].Classification) {
4716 case Subscript::SIV: {
4717 unsigned Level;
4718 const SCEV *SplitIter = nullptr;
4719 (void)testSIV(Pair[SI].Src, Pair[SI].Dst, Level, Result, NewConstraint,
4720 SplitIter);
4721 if (Level == SplitLevel) {
4722 assert(SplitIter != nullptr);
4723 return SplitIter;
4724 }
4725 break;
4726 }
4727 case Subscript::ZIV:
4728 case Subscript::RDIV:
4729 case Subscript::MIV:
4730 break;
4731 default:
4732 llvm_unreachable("subscript has unexpected classification");
4733 }
4734 }
4735
4736 assert(!Coupled.empty() && "coupled expected non-empty");
4737
4738 // test coupled subscript groups
4739 SmallVector<Constraint, 4> Constraints(MaxLevels + 1);
4740 for (unsigned II = 0; II <= MaxLevels; ++II)
4741 Constraints[II].setAny(SE);
4742 for (unsigned SI : Coupled.set_bits()) {
4743 SmallBitVector Group(Pair[SI].Group);
4744 SmallBitVector Sivs(Pairs);
4745 SmallBitVector Mivs(Pairs);
4746 SmallBitVector ConstrainedLevels(MaxLevels + 1);
4747 for (unsigned SJ : Group.set_bits()) {
4748 if (Pair[SJ].Classification == Subscript::SIV)
4749 Sivs.set(SJ);
4750 else
4751 Mivs.set(SJ);
4752 }
4753 while (Sivs.any()) {
4754 bool Changed = false;
4755 for (unsigned SJ : Sivs.set_bits()) {
4756 // SJ is an SIV subscript that's part of the current coupled group
4757 unsigned Level;
4758 const SCEV *SplitIter = nullptr;
4759 (void)testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, Result, NewConstraint,
4760 SplitIter);
4761 if (Level == SplitLevel && SplitIter)
4762 return SplitIter;
4763 ConstrainedLevels.set(Level);
4764 if (intersectConstraints(&Constraints[Level], &NewConstraint))
4765 Changed = true;
4766 Sivs.reset(SJ);
4767 }
4768 if (!Changed)
4769 continue;
4770 // propagate, possibly creating new SIVs and ZIVs
4771 for (unsigned SJ : Mivs.set_bits()) {
4772 // SJ is an MIV subscript that's part of the current coupled group
4773 if (!propagate(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops, Constraints,
4774 Result.Consistent))
4775 continue;
4776 Pair[SJ].Classification = classifyPair(
4777 Pair[SJ].Src, LI->getLoopFor(Src->getParent()), Pair[SJ].Dst,
4778 LI->getLoopFor(Dst->getParent()), Pair[SJ].Loops);
4779 switch (Pair[SJ].Classification) {
4780 case Subscript::ZIV:
4781 Mivs.reset(SJ);
4782 break;
4783 case Subscript::SIV:
4784 Sivs.set(SJ);
4785 Mivs.reset(SJ);
4786 break;
4787 case Subscript::RDIV:
4788 case Subscript::MIV:
4789 break;
4790 default:
4791 llvm_unreachable("bad subscript classification");
4792 }
4793 }
4794 }
4795 }
4796 llvm_unreachable("somehow reached end of routine");
4797}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Expand Atomic instructions
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition Compiler.h:638
static cl::opt< DependenceTestType > EnableDependenceTest("da-enable-dependence-test", cl::init(DependenceTestType::All), cl::ReallyHidden, cl::desc("Run only specified dependence test routine and disable others. " "The purpose is mainly to exclude the influence of other " "dependence test routines in regression tests. If set to All, all " "dependence test routines are enabled."), cl::values(clEnumValN(DependenceTestType::All, "all", "Enable all dependence test routines."), clEnumValN(DependenceTestType::StrongSIV, "strong-siv", "Enable only Strong SIV test."), clEnumValN(DependenceTestType::WeakCrossingSIV, "weak-crossing-siv", "Enable only Weak-Crossing SIV test."), clEnumValN(DependenceTestType::ExactSIV, "exact-siv", "Enable only Exact SIV test."), clEnumValN(DependenceTestType::WeakZeroSIV, "weak-zero-siv", "Enable only Weak-Zero SIV test."), clEnumValN(DependenceTestType::ExactRDIV, "exact-rdiv", "Enable only Exact RDIV test."), clEnumValN(DependenceTestType::SymbolicRDIV, "symbolic-rdiv", "Enable only Symbolic RDIV test."), clEnumValN(DependenceTestType::GCDMIV, "gcd-miv", "Enable only GCD MIV test."), clEnumValN(DependenceTestType::BanerjeeMIV, "banerjee-miv", "Enable only Banerjee MIV test.")))
static bool isLoadOrStore(const Instruction *I)
static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA, ScalarEvolution &SE, LoopInfo &LI, bool NormalizeResults)
static bool isDependenceTestEnabled(DependenceTestType Test)
Returns true iff Test is enabled.
static bool findGCD(unsigned Bits, const APInt &AM, const APInt &BM, const APInt &Delta, APInt &G, APInt &X, APInt &Y)
static void dumpSmallBitVector(SmallBitVector &BV)
static APInt ceilingOfQuotient(const APInt &A, const APInt &B)
static APInt floorOfQuotient(const APInt &A, const APInt &B)
static const SCEV * minusSCEVNoSignedOverflow(const SCEV *A, const SCEV *B, ScalarEvolution &SE)
Returns A - B if it guaranteed not to signed wrap.
static AliasResult underlyingObjectsAlias(AAResults *AA, const DataLayout &DL, const MemoryLocation &LocA, const MemoryLocation &LocB)
static std::pair< std::optional< APInt >, std::optional< APInt > > inferDomainOfAffine(const APInt &A, const APInt &B, const std::optional< APInt > &UB)
Given an affine expression of the form A*k + B, where k is an arbitrary integer, infer the possible r...
static std::optional< APInt > getConstantPart(const SCEV *Expr)
static bool isRemainderZero(const SCEVConstant *Dividend, const SCEVConstant *Divisor)
static cl::opt< bool > Delinearize("da-delinearize", cl::init(true), cl::Hidden, cl::desc("Try to delinearize array references."))
static cl::opt< bool > EnableMonotonicityCheck("da-enable-monotonicity-check", cl::init(false), cl::Hidden, cl::desc("Check if the subscripts are monotonic. If it's not, dependence " "is reported as unknown."))
static cl::opt< bool > DumpMonotonicityReport("da-dump-monotonicity-report", cl::init(false), cl::Hidden, cl::desc("When printing analysis, dump the results of monotonicity checks."))
static cl::opt< unsigned > MIVMaxLevelThreshold("da-miv-max-level-threshold", cl::init(7), cl::Hidden, cl::desc("Maximum depth allowed for the recursive algorithm used to " "explore MIV direction vectors."))
static cl::opt< bool > DisableDelinearizationChecks("da-disable-delinearization-checks", cl::Hidden, cl::desc("Disable checks that try to statically verify validity of " "delinearized subscripts. Enabling this option may result in incorrect " "dependence vectors for languages that allow the subscript of one " "dimension to underflow or overflow into another dimension."))
Hexagon Hardware Loops
Module.h This file contains the declarations for the Module class.
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition Lint.cpp:539
Loop::LoopBounds::Direction Direction
Definition LoopInfo.cpp:231
#define F(x, y, z)
Definition MD5.cpp:55
#define I(x, y, z)
Definition MD5.cpp:58
#define G(x, y, z)
Definition MD5.cpp:56
#define T
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
#define P(N)
FunctionAnalysisManager FAM
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition PassSupport.h:42
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
void visit(MachineFunction &MF, MachineBasicBlock &Start, std::function< void(MachineBasicBlock *)> op)
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition Statistic.h:171
#define LLVM_DEBUG(...)
Definition Debug.h:114
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
static SymbolRef::Type getType(const Symbol *Sym)
Definition TapiFile.cpp:39
LocallyHashedType DenseMapInfo< LocallyHashedType >::Empty
A manager for alias analyses.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Class for arbitrary precision integers.
Definition APInt.h:78
static LLVM_ABI void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
Definition APInt.cpp:1890
APInt abs() const
Get the absolute value.
Definition APInt.h:1795
bool sgt(const APInt &RHS) const
Signed greater than comparison.
Definition APInt.h:1201
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition APInt.h:1488
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition APInt.h:209
LLVM_ABI APInt sdiv(const APInt &RHS) const
Signed division function for APInt.
Definition APInt.cpp:1644
bool sle(const APInt &RHS) const
Signed less or equal comparison.
Definition APInt.h:1166
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition APInt.h:219
LLVM_ABI APInt srem(const APInt &RHS) const
Function for signed remainder operation.
Definition APInt.cpp:1736
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition APInt.h:1130
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
Definition APInt.h:200
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
Definition APInt.h:1237
The possible results of an alias query.
@ MayAlias
The two locations may or may not alias.
@ NoAlias
The two locations do not alias at all.
@ PartialAlias
The two locations alias, but only due to a partial overlap.
@ MustAlias
The two locations precisely alias each other.
This templated class represents "all analyses that operate over <aparticular IR unit>" (e....
Definition Analysis.h:50
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
AnalysisUsage & addRequiredTransitive()
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:41
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
void enableCrossIterationMode()
Assume that values may come from different cycle iterations.
bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition InstrTypes.h:676
@ ICMP_SLT
signed less than
Definition InstrTypes.h:705
@ ICMP_SLE
signed less or equal
Definition InstrTypes.h:706
@ ICMP_SGT
signed greater than
Definition InstrTypes.h:703
@ ICMP_NE
not equal
Definition InstrTypes.h:698
@ ICMP_SGE
signed greater or equal
Definition InstrTypes.h:704
This is an important base class in LLVM.
Definition Constant.h:43
A parsed version of the target data layout string in and methods for querying it.
Definition DataLayout.h:63
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.
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.
LLVM_ABI const SCEV * getSplitIteration(const Dependence &Dep, unsigned Level)
getSplitIteration - Give a dependence that's splittable at some particular level, return the iteratio...
LLVM_ABI SCEVUnionPredicate getRuntimeAssumptions() const
getRuntimeAssumptions - Returns all the runtime assumptions under which the dependence test is valid.
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.
Dependence - This class represents a dependence between two memory memory references in a function.
Instruction * getDst() const
getDst - Returns the destination instruction for this dependence.
void dumpImp(raw_ostream &OS, bool IsSameSD=false) const
dumpImp - For debugging purposes.
Dependence(Dependence &&)=default
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 bool isPeelLast(unsigned Level, bool SameSD=false) const
isPeelLast - Returns true if peeling the last iteration from this regular or SameSD loop level will b...
virtual bool isConsistent() const
isConsistent - Returns true if this dependence is consistent (occurs every time the source and destin...
virtual unsigned getLevels() const
getLevels - Returns the number of common loops surrounding the source and destination of the dependen...
virtual unsigned getDirection(unsigned Level, bool SameSD=false) const
getDirection - Returns the direction associated with a particular common or SameSD level.
virtual bool isScalar(unsigned Level, bool SameSD=false) const
isScalar - Returns true if a particular regular or SameSD level is scalar; that is,...
bool isFlow() const
isFlow - Returns true if this is a flow (aka true) dependence.
virtual bool isPeelFirst(unsigned Level, bool SameSD=false) const
isPeelFirst - Returns true if peeling the first iteration from this regular or SameSD loop level will...
bool isInput() const
isInput - Returns true if this is an input dependence.
bool isAnti() const
isAnti - Returns true if this is an anti dependence.
virtual bool isSplitable(unsigned Level, bool SameSD=false) const
isSplitable - Returns true if splitting the loop will break the dependence.
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 dump(raw_ostream &OS) const
dump - For debugging purposes, dumps a dependence to OS.
virtual bool inSameSDLoops(unsigned Level) const
inSameSDLoops - Returns true if this level is an SameSD level, i.e., performed across two separate lo...
Class representing an expression and its matching format.
FullDependence - This class represents a dependence between two memory references in a function.
FullDependence(Instruction *Source, Instruction *Destination, const SCEVUnionPredicate &Assumes, bool PossiblyLoopIndependent, unsigned Levels)
unsigned getDirection(unsigned Level, bool SameSD=false) const override
getDirection - Returns the direction associated with a particular common or SameSD level.
bool isScalar(unsigned Level, bool SameSD=false) const override
isScalar - Returns true if a particular regular or SameSD level is scalar; that is,...
bool isDirectionNegative() const override
Check if the direction vector is negative.
const SCEV * getDistance(unsigned Level, bool SameSD=false) const override
getDistance - Returns the distance (or NULL) associated with a particular common or SameSD level.
DVEntry getDVEntry(unsigned Level, bool IsSameSD) const
getDVEntry - Returns the DV entry associated with a regular or a SameSD level.
bool isSplitable(unsigned Level, bool SameSD=false) const override
isSplitable - Returns true if splitting the loop will break the dependence.
bool isPeelLast(unsigned Level, bool SameSD=false) const override
isPeelLast - Returns true if peeling the last iteration from this regular or SameSD loop level will b...
bool isPeelFirst(unsigned Level, bool SameSD=false) const override
isPeelFirst - Returns true if peeling the first iteration from this regular or SameSD loop level will...
bool inSameSDLoops(unsigned Level) const override
inSameSDLoops - Returns true if this level is an SameSD level, i.e., performed across two separate lo...
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:314
FunctionPass(char &pid)
Definition Pass.h:316
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
An instruction for reading from memory.
bool isPrecise() const
uint64_t toRaw() const
Analysis pass that exposes the LoopInfo for a function.
Definition LoopInfo.h:569
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
const LoopT * getOutermostLoop() const
Get the outermost loop in which this loop is contained.
unsigned getLoopDepth() const
Return the nesting level of this loop.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Definition LoopInfo.h:596
This class represents a loop nest and can be used to query its properties.
Represents a single loop in the control flow graph.
Definition LoopInfo.h:40
Representation for a specific memory location.
static LLVM_ABI MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
static MemoryLocation getBeforeOrAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())
Return a location that may access any location before or after Ptr, while remaining within the underl...
AAMDNodes AATags
The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...
const Value * Ptr
The address of the start of the location.
A Module instance is used to store all the information related to an LLVM module.
Definition Module.h:67
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition Analysis.h:275
This node represents a polynomial recurrence on the trip count of the specified loop.
LLVM_ABI const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
const SCEV * getOperand() const
This class represents a constant integer value.
const APInt & getAPInt() const
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
const SCEV * getOperand(unsigned i) const
This class represents an assumption made using SCEV expressions which can be checked at run-time.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
void print(raw_ostream &OS, unsigned Depth) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool isAlwaysTrue() const override
Implementation of the SCEVPredicate interface.
This class represents an analyzed expression in the program.
LLVM_ABI ArrayRef< const SCEV * > operands() const
Return operands of this SCEV expression.
LLVM_ABI bool isOne() const
Return true if the expression is a constant one.
LLVM_ABI bool isZero() const
Return true if the expression is a constant zero.
LLVM_ABI Type * getType() const
Return the LLVM type of this SCEV expression.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
LLVM_ABI const SCEV * removePointerBase(const SCEV *S)
Compute an expression equivalent to S - getPointerBase(S).
LLVM_ABI const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
LLVM_ABI bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI=nullptr)
Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?
LLVM_ABI const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
This is a 'bitvector' (really, a variable-sized bit array), optimized for the case when the array is ...
SmallBitVector & set()
iterator_range< const_set_bits_iterator > set_bits() const
int find_next(unsigned Prev) const
Returns the index of the next set bit following the "Prev" bit.
bool any() const
Returns true if any bit is set.
bool empty() const
Tests whether there are no bits in this bitvector.
size_type count() const
Returns the number of bits which are set.
SmallBitVector & reset()
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void resize(size_type N)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition Type.h:45
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition Type.h:240
LLVM Value Representation.
Definition Value.h:75
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
Changed
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Abstract Attribute helper functions.
Definition Attributor.h:165
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition APInt.h:2248
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
Definition APInt.h:2253
LLVM_ABI APInt GreatestCommonDivisor(APInt A, APInt B)
Compute GCD of two unsigned APInt values.
Definition APInt.cpp:798
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition CallingConv.h:24
@ C
The default llvm calling convention, compatible with C.
Definition CallingConv.h:34
@ BasicBlock
Various leaf nodes.
Definition ISDOpcodes.h:81
@ TB
TB - TwoByte - Set if this instruction has a two byte opcode, which starts with a 0x0F byte before th...
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
FunctionAddr VTableAddr Value
Definition InstrProf.h:137
InstIterator< SymbolTableList< BasicBlock >, Function::iterator, BasicBlock::iterator, Instruction > inst_iterator
void collectParametricTerms(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Terms)
Collect parametric terms occurring in step expressions (first step of delinearization).
void findArrayDimensions(ScalarEvolution &SE, SmallVectorImpl< const SCEV * > &Terms, SmallVectorImpl< const SCEV * > &Sizes, const SCEV *ElementSize)
Compute the array dimensions Sizes from the set of Terms extracted from the memory access function of...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
@ Done
Definition Threading.h:60
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
inst_iterator inst_begin(Function *F)
void computeAccessFunctions(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< const SCEV * > &Sizes)
Return in Subscripts the access functions for each dimension in Sizes (third step of delinearization)...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:207
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
inst_iterator inst_end(Function *F)
bool tryDelinearizeFixedSizeImpl(ScalarEvolution *SE, Instruction *Inst, const SCEV *AccessFn, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< int > &Sizes)
Implementation of fixed size array delinearization.
constexpr unsigned BitWidth
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
LLVM_ABI bool isKnownNonNegative(const Value *V, const SimplifyQuery &SQ, unsigned Depth=0)
Returns true if the give value is known to be non-negative.
LLVM_ABI bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
LLVM_ABI FunctionPass * createDependenceAnalysisWrapperPass()
createDependenceAnalysisPass - This creates an instance of the DependenceAnalysis wrapper pass.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition BitVector.h:869
#define N
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition Analysis.h:29
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Dependence::DVEntry - Each level in the distance/direction vector has a direction (or perhaps a union...
This class defines a simple visitor class that may be used for various SCEV analysis purposes.