LLVM 24.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// Since Clang linearizes some array subscripts, the dependence
22// analysis is using SCEV->delinearize to recover the representation of multiple
23// subscripts, and thus avoid the more expensive and less precise MIV tests. The
24// delinearization is controlled by the flag -da-delinearize.
25//
26// We should pay some careful attention to the possibility of integer overflow
27// in the implementation of the various tests. This could happen with Add,
28// Subtract, or Multiply, with both APInt's and SCEV's.
29//
30// Some non-linear subscript pairs can be handled by the GCD test
31// (and perhaps other tests).
32// Should explore how often these things occur.
33//
34// Finally, it seems like certain test cases expose weaknesses in the SCEV
35// simplification, especially in the handling of sign and zero extensions.
36// It could be useful to spend time exploring these.
37//
38// Please note that this is work in progress and the interface is subject to
39// change.
40//
41//===----------------------------------------------------------------------===//
42// //
43// In memory of Ken Kennedy, 1945 - 2007 //
44// //
45//===----------------------------------------------------------------------===//
46
48#include "AnalysisOptions.h"
49#include "llvm/ADT/Statistic.h"
58#include "llvm/IR/Module.h"
60#include "llvm/Support/Debug.h"
63
64using namespace llvm;
65
66#define DEBUG_TYPE "da"
67
68//===----------------------------------------------------------------------===//
69// statistics
70
71STATISTIC(TotalArrayPairs, "Array pairs tested");
72STATISTIC(NonlinearSubscriptPairs, "Nonlinear subscript pairs");
73STATISTIC(ZIVapplications, "ZIV applications");
74STATISTIC(ZIVindependence, "ZIV independence");
75STATISTIC(StrongSIVapplications, "Strong SIV applications");
76STATISTIC(StrongSIVsuccesses, "Strong SIV successes");
77STATISTIC(StrongSIVindependence, "Strong SIV independence");
78STATISTIC(WeakCrossingSIVapplications, "Weak-Crossing SIV applications");
79STATISTIC(WeakCrossingSIVsuccesses, "Weak-Crossing SIV successes");
80STATISTIC(WeakCrossingSIVindependence, "Weak-Crossing SIV independence");
81STATISTIC(ExactSIVapplications, "Exact SIV applications");
82STATISTIC(ExactSIVsuccesses, "Exact SIV successes");
83STATISTIC(ExactSIVindependence, "Exact SIV independence");
84STATISTIC(WeakZeroSIVapplications, "Weak-Zero SIV applications");
85STATISTIC(WeakZeroSIVsuccesses, "Weak-Zero SIV successes");
86STATISTIC(WeakZeroSIVindependence, "Weak-Zero SIV independence");
87STATISTIC(ExactRDIVapplications, "Exact RDIV applications");
88STATISTIC(ExactRDIVindependence, "Exact RDIV independence");
89STATISTIC(GCDapplications, "GCD applications");
90STATISTIC(GCDsuccesses, "GCD successes");
91STATISTIC(GCDindependence, "GCD independence");
92STATISTIC(BanerjeeApplications, "Banerjee applications");
93STATISTIC(BanerjeeIndependence, "Banerjee independence");
94STATISTIC(BanerjeeSuccesses, "Banerjee successes");
95STATISTIC(SameSDLoopsCount, "Loops with Same iteration Space and Depth");
96
97//===----------------------------------------------------------------------===//
98// basics
99
101 LoopInfo *LI)
102 : Opts(getAnalysisOptions(*F)), AA(AA), SE(SE), LI(LI), F(F) {}
103
106 auto &AA = FAM.getResult<AAManager>(F);
107 auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);
108 auto &LI = FAM.getResult<LoopAnalysis>(F);
109 return DependenceInfo(&F, &AA, &SE, &LI);
110}
111
112AnalysisKey DependenceAnalysis::Key;
113
115 "Dependence Analysis", true, true)
121
123
126
130
132 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
133 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
134 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
135 info.reset(new DependenceInfo(&F, &AA, &SE, &LI));
136 return false;
137}
138
140
142
149
150namespace {
151
152/// A wrapper class for std::optional<APInt> that provides arithmetic operators
153/// with overflow checking in a signed sense. This allows us to omit inserting
154/// an overflow check at every arithmetic operation, which simplifies the code
155/// if the operations are chained like `a + b + c + ...`.
156///
157/// If an calculation overflows, the result becomes "invalid" which is
158/// internally represented by std::nullopt. If any operand of an arithmetic
159/// operation is "invalid", the result will also be "invalid".
160struct OverflowSafeSignedAPInt {
161 OverflowSafeSignedAPInt() : Value(std::nullopt) {}
162 OverflowSafeSignedAPInt(const APInt &V) : Value(V) {}
163 OverflowSafeSignedAPInt(const std::optional<APInt> &V) : Value(V) {}
164
165 OverflowSafeSignedAPInt operator+(const OverflowSafeSignedAPInt &RHS) const {
166 if (!Value || !RHS.Value)
167 return OverflowSafeSignedAPInt();
168 bool Overflow;
169 APInt Result = Value->sadd_ov(*RHS.Value, Overflow);
170 if (Overflow)
171 return OverflowSafeSignedAPInt();
172 return OverflowSafeSignedAPInt(Result);
173 }
174
175 OverflowSafeSignedAPInt operator+(int RHS) const {
176 if (!Value)
177 return OverflowSafeSignedAPInt();
178 return *this + fromInt(RHS);
179 }
180
181 OverflowSafeSignedAPInt operator-(const OverflowSafeSignedAPInt &RHS) const {
182 if (!Value || !RHS.Value)
183 return OverflowSafeSignedAPInt();
184 bool Overflow;
185 APInt Result = Value->ssub_ov(*RHS.Value, Overflow);
186 if (Overflow)
187 return OverflowSafeSignedAPInt();
188 return OverflowSafeSignedAPInt(Result);
189 }
190
191 OverflowSafeSignedAPInt operator-(int RHS) const {
192 if (!Value)
193 return OverflowSafeSignedAPInt();
194 return *this - fromInt(RHS);
195 }
196
197 OverflowSafeSignedAPInt operator*(const OverflowSafeSignedAPInt &RHS) const {
198 if (!Value || !RHS.Value)
199 return OverflowSafeSignedAPInt();
200 bool Overflow;
201 APInt Result = Value->smul_ov(*RHS.Value, Overflow);
202 if (Overflow)
203 return OverflowSafeSignedAPInt();
204 return OverflowSafeSignedAPInt(Result);
205 }
206
207 OverflowSafeSignedAPInt operator-() const {
208 if (!Value)
209 return OverflowSafeSignedAPInt();
210 if (Value->isMinSignedValue())
211 return OverflowSafeSignedAPInt();
212 return OverflowSafeSignedAPInt(-*Value);
213 }
214
215 operator bool() const { return Value.has_value(); }
216
217 bool operator!() const { return !Value.has_value(); }
218
219 const APInt &operator*() const {
220 assert(Value && "Value is not available.");
221 return *Value;
222 }
223
224 const APInt *operator->() const {
225 assert(Value && "Value is not available.");
226 return &*Value;
227 }
228
229private:
230 /// Underlying value. std::nullopt means "unknown". An arithmetic operation on
231 /// "unknown" always produces "unknown".
232 std::optional<APInt> Value;
233
234 OverflowSafeSignedAPInt fromInt(uint64_t V) const {
235 assert(Value && "Value is not available.");
236 return OverflowSafeSignedAPInt(
237 APInt(Value->getBitWidth(), V, /*isSigned=*/true));
238 }
239};
240
241} // anonymous namespace
242
243// Used to test the dependence analyzer.
244// Looks through the function, noting instructions that may access memory.
245// Calls depends() on every possible pair and prints out the result.
246// Ignores all other instructions.
248 ScalarEvolution &SE, LoopInfo &LI,
249 bool NormalizeResults) {
250 auto *F = DA->getFunction();
251
252 for (inst_iterator SrcI = inst_begin(F), SrcE = inst_end(F); SrcI != SrcE;
253 ++SrcI) {
254 if (SrcI->mayReadOrWriteMemory()) {
255 for (inst_iterator DstI = SrcI, DstE = inst_end(F); DstI != DstE;
256 ++DstI) {
257 if (DstI->mayReadOrWriteMemory()) {
258 OS << "Src:" << *SrcI << " --> Dst:" << *DstI << "\n";
259 OS << " da analyze - ";
260 if (auto D = DA->depends(&*SrcI, &*DstI,
261 /*UnderRuntimeAssumptions=*/true)) {
262
263#ifndef NDEBUG
264 // Verify that the distance being zero is equivalent to the
265 // direction being EQ.
266 for (unsigned Level = 1; Level <= D->getLevels(); Level++) {
267 const SCEV *Distance = D->getDistance(Level);
268 bool IsDistanceZero = Distance && Distance->isZero();
269 bool IsDirectionEQ =
270 D->getDirection(Level) == Dependence::DVEntry::EQ;
271 assert(IsDistanceZero == IsDirectionEQ &&
272 "Inconsistent distance and direction.");
273 }
274#endif
275
276 // Normalize negative direction vectors if required by clients.
277 if (NormalizeResults && D->normalize(&SE))
278 OS << "normalized - ";
279 D->dump(OS);
280 } else
281 OS << "none!\n";
282 }
283 }
284 }
285 }
286}
287
289 const Module *) const {
291 OS, info.get(), getAnalysis<ScalarEvolutionWrapperPass>().getSE(),
292 getAnalysis<LoopInfoWrapperPass>().getLoopInfo(), false);
293}
294
297 OS << "Printing analysis 'Dependence Analysis' for function '" << F.getName()
298 << "':\n";
300 FAM.getResult<ScalarEvolutionAnalysis>(F),
301 FAM.getResult<LoopAnalysis>(F), NormalizeResults);
302 return PreservedAnalyses::all();
303}
304
305//===----------------------------------------------------------------------===//
306// Dependence methods
307
308// Returns true if this is an input dependence.
310 return Src->mayReadFromMemory() && Dst->mayReadFromMemory();
311}
312
313// Returns true if this is an output dependence.
315 return Src->mayWriteToMemory() && Dst->mayWriteToMemory();
316}
317
318// Returns true if this is an flow (aka true) dependence.
319bool Dependence::isFlow() const {
320 return Src->mayWriteToMemory() && Dst->mayReadFromMemory();
321}
322
323// Returns true if this is an anti dependence.
324bool Dependence::isAnti() const {
325 return Src->mayReadFromMemory() && Dst->mayWriteToMemory();
326}
327
328// Returns true if a particular level is scalar; that is,
329// if no subscript in the source or destination mention the induction
330// variable associated with the loop at this level.
331// Leave this out of line, so it will serve as a virtual method anchor
332bool Dependence::isScalar(unsigned level, bool IsSameSD) const { return false; }
333
334//===----------------------------------------------------------------------===//
335// FullDependence methods
336
338 const SCEVUnionPredicate &Assumes,
339 bool PossiblyLoopIndependent,
340 unsigned CommonLevels)
341 : Dependence(Source, Destination, Assumes), Levels(CommonLevels),
342 LoopIndependent(PossiblyLoopIndependent) {
343 SameSDLevels = 0;
344 if (CommonLevels)
345 DV = std::make_unique<DVEntry[]>(CommonLevels);
346}
347
348// FIXME: in some cases the meaning of a negative direction vector
349// may not be straightforward, e.g.,
350// for (int i = 0; i < 32; ++i) {
351// Src: A[i] = ...;
352// Dst: use(A[31 - i]);
353// }
354// The dependency is
355// flow { Src[i] -> Dst[31 - i] : when i >= 16 } and
356// anti { Dst[i] -> Src[31 - i] : when i < 16 },
357// -- hence a [<>].
358// As long as a dependence result contains '>' ('<>', '<=>', "*"), it
359// means that a reversed/normalized dependence needs to be considered
360// as well. Nevertheless, current isDirectionNegative() only returns
361// true with a '>' or '>=' dependency for ease of canonicalizing the
362// dependency vector, since the reverse of '<>', '<=>' and "*" is itself.
364 for (unsigned Level = 1; Level <= Levels; ++Level) {
365 unsigned char Direction = DV[Level - 1].Direction;
366 if (Direction == Dependence::DVEntry::EQ)
367 continue;
368 if (Direction == Dependence::DVEntry::GT ||
369 Direction == Dependence::DVEntry::GE)
370 return true;
371 return false;
372 }
373 return false;
374}
375
377 std::swap(Src, Dst);
378 for (unsigned Level = 1; Level <= Levels; ++Level) {
379 unsigned char Direction = DV[Level - 1].Direction;
380 // Reverse the direction vector, this means LT becomes GT
381 // and GT becomes LT.
382 unsigned char RevDirection = Direction & Dependence::DVEntry::EQ;
383 if (Direction & Dependence::DVEntry::LT)
384 RevDirection |= Dependence::DVEntry::GT;
385 if (Direction & Dependence::DVEntry::GT)
386 RevDirection |= Dependence::DVEntry::LT;
387 DV[Level - 1].Direction = RevDirection;
388 // Reverse the dependence distance as well.
389 if (DV[Level - 1].Distance != nullptr)
390 DV[Level - 1].Distance = SE.getNegativeSCEV(DV[Level - 1].Distance);
391 }
392}
393
395 if (!isDirectionNegative())
396 return false;
397
398 LLVM_DEBUG(dbgs() << "Before normalizing negative direction vectors:\n";
399 dump(dbgs()););
400 negate(*SE);
401 LLVM_DEBUG(dbgs() << "After normalizing negative direction vectors:\n";
402 dump(dbgs()););
403 return true;
404}
405
406// The rest are simple getters that hide the implementation.
407
408// getDirection - Returns the direction associated with a particular common or
409// SameSD level.
410unsigned FullDependence::getDirection(unsigned Level, bool IsSameSD) const {
411 return getDVEntry(Level, IsSameSD).Direction;
412}
413
414// Returns the distance (or NULL) associated with a particular common or
415// SameSD level.
416const SCEV *FullDependence::getDistance(unsigned Level, bool IsSameSD) const {
417 return getDVEntry(Level, IsSameSD).Distance;
418}
419
420// Returns true if a particular regular or SameSD level is scalar; that is,
421// if no subscript in the source or destination mention the induction variable
422// associated with the loop at this level.
423bool FullDependence::isScalar(unsigned Level, bool IsSameSD) const {
424 return getDVEntry(Level, IsSameSD).Scalar;
425}
426
427// inSameSDLoops - Returns true if this level is an SameSD level, i.e.,
428// performed across two separate loop nests that have the Same iteration space
429// and Depth.
430bool FullDependence::inSameSDLoops(unsigned Level) const {
431 assert(0 < Level && Level <= static_cast<unsigned>(Levels) + SameSDLevels &&
432 "Level out of range");
433 return Level > Levels;
434}
435
436//===----------------------------------------------------------------------===//
437// DependenceInfo methods
438
439// For debugging purposes. Dumps a dependence to OS.
441 if (isConfused())
442 OS << "confused";
443 else {
444 if (isFlow())
445 OS << "flow";
446 else if (isOutput())
447 OS << "output";
448 else if (isAnti())
449 OS << "anti";
450 else if (isInput())
451 OS << "input";
452 dumpImp(OS);
453 unsigned SameSDLevels = getSameSDLevels();
454 if (SameSDLevels > 0) {
455 OS << " / assuming " << SameSDLevels << " loop level(s) fused: ";
456 dumpImp(OS, true);
457 }
458 }
459 OS << "!\n";
460
462 if (!Assumptions.isAlwaysTrue()) {
463 OS << " Runtime Assumptions:\n";
464 Assumptions.print(OS, 2);
465 }
466}
467
468// For debugging purposes. Dumps a dependence to OS with or without considering
469// the SameSD levels.
470void Dependence::dumpImp(raw_ostream &OS, bool IsSameSD) const {
471 unsigned Levels = getLevels();
472 unsigned SameSDLevels = getSameSDLevels();
473 bool OnSameSD = false;
474 unsigned LevelNum = Levels;
475 if (IsSameSD)
476 LevelNum += SameSDLevels;
477 OS << " [";
478 for (unsigned II = 1; II <= LevelNum; ++II) {
479 if (!OnSameSD && inSameSDLoops(II))
480 OnSameSD = true;
481 const SCEV *Distance = getDistance(II, OnSameSD);
482 if (Distance)
483 OS << *Distance;
484 else if (isScalar(II, OnSameSD))
485 OS << "S";
486 else {
487 unsigned Direction = getDirection(II, OnSameSD);
488 if (Direction == DVEntry::ALL)
489 OS << "*";
490 else {
491 if (Direction & DVEntry::LT)
492 OS << "<";
493 if (Direction & DVEntry::EQ)
494 OS << "=";
495 if (Direction & DVEntry::GT)
496 OS << ">";
497 }
498 }
499 if (II < LevelNum)
500 OS << " ";
501 }
502 if (isLoopIndependent())
503 OS << "|<";
504 OS << "]";
505}
506
507/// Drop alias scopes that are only valid within a single loop iteration.
508static MDNode *
510 const SmallPtrSetImpl<const MDNode *> &LoopAliasScopes) {
511 if (!ScopeList || LoopAliasScopes.empty())
512 return ScopeList;
513
514 // For the sake of simplicity, drop the whole scope list if any scope is
515 // iteration-local.
516 if (any_of(ScopeList->operands(), [&](Metadata *Scope) {
517 return LoopAliasScopes.contains(cast<MDNode>(Scope));
518 }))
519 return nullptr;
520
521 return ScopeList;
522}
523
524// Location is spanned accross iteration
525// and single iteration alias scope are dropped
526static MemoryLocation
528 const SmallPtrSetImpl<const MDNode *> &LoopAliasScopes) {
530 Adj.AATags.Scope = adjustAliasScopeList(Adj.AATags.Scope, LoopAliasScopes);
531 Adj.AATags.NoAlias =
532 adjustAliasScopeList(Adj.AATags.NoAlias, LoopAliasScopes);
533 return Adj;
534}
535
536// Returns NoAlias/MayAliass/MustAlias for two memory locations based upon their
537// underlaying objects. If LocA and LocB are known to not alias (for any reason:
538// tbaa, non-overlapping regions etc), then it is known there is no dependency.
539// Otherwise the underlying objects are checked to see if they point to
540// different identifiable objects.
541static AliasResult
543 const MemoryLocation &LocA, const MemoryLocation &LocB,
544 const SmallPtrSetImpl<const MDNode *> &LoopAliasScopes) {
545
546 MemoryLocation LocAS = adjustLoc(LocA, LoopAliasScopes);
547 MemoryLocation LocBS = adjustLoc(LocB, LoopAliasScopes);
548
549 BatchAAResults BAA(*AA);
551
552 if (BAA.isNoAlias(LocAS, LocBS))
554
555 // Check the underlying objects are the same
556 const Value *AObj = getUnderlyingObject(LocA.Ptr);
557 const Value *BObj = getUnderlyingObject(LocB.Ptr);
558
559 // If the underlying objects are the same, they must alias
560 if (AObj == BObj)
562
563 // We may have hit the recursion limit for underlying objects, or have
564 // underlying objects where we don't know they will alias.
565 if (!isIdentifiedObject(AObj) || !isIdentifiedObject(BObj))
567
568 // Otherwise we know the objects are different and both identified objects so
569 // must not alias.
571}
572
573// Returns true if the load or store can be analyzed. Atomic and volatile
574// operations have properties which this analysis does not understand.
575static bool isLoadOrStore(const Instruction *I) {
576 if (const LoadInst *LI = dyn_cast<LoadInst>(I))
577 return LI->isUnordered();
578 else if (const StoreInst *SI = dyn_cast<StoreInst>(I))
579 return SI->isUnordered();
580 return false;
581}
582
583// Returns true if two loops have the Same iteration Space and Depth. To be
584// more specific, two loops have SameSD if they are in the same nesting
585// depth and have the same backedge count. SameSD stands for Same iteration
586// Space and Depth.
587bool DependenceInfo::haveSameSD(const Loop *SrcLoop,
588 const Loop *DstLoop) const {
589 if (SrcLoop == DstLoop)
590 return true;
591
592 if (SrcLoop->getLoopDepth() != DstLoop->getLoopDepth())
593 return false;
594
595 if (!SrcLoop || !SrcLoop->getLoopLatch() || !DstLoop ||
596 !DstLoop->getLoopLatch())
597 return false;
598
599 const SCEV *SrcUB = SE->getBackedgeTakenCount(SrcLoop);
600 const SCEV *DstUB = SE->getBackedgeTakenCount(DstLoop);
602 return false;
603
604 Type *WiderType = SE->getWiderType(SrcUB->getType(), DstUB->getType());
605 SrcUB = SE->getNoopOrZeroExtend(SrcUB, WiderType);
606 DstUB = SE->getNoopOrZeroExtend(DstUB, WiderType);
607
608 if (SrcUB == DstUB)
609 return true;
610
611 return false;
612}
613
614// Examines the loop nesting of the Src and Dst
615// instructions and establishes their shared loops. Sets the variables
616// CommonLevels, SrcLevels, and MaxLevels.
617// The source and destination instructions needn't be contained in the same
618// loop. The routine establishNestingLevels finds the level of most deeply
619// nested loop that contains them both, CommonLevels. An instruction that's
620// not contained in a loop is at level = 0. MaxLevels is equal to the level
621// of the source plus the level of the destination, minus CommonLevels.
622// This lets us allocate vectors MaxLevels in length, with room for every
623// distinct loop referenced in both the source and destination subscripts.
624// The variable SrcLevels is the nesting depth of the source instruction.
625// It's used to help calculate distinct loops referenced by the destination.
626// Here's the map from loops to levels:
627// 0 - unused
628// 1 - outermost common loop
629// ... - other common loops
630// CommonLevels - innermost common loop
631// ... - loops containing Src but not Dst
632// SrcLevels - innermost loop containing Src but not Dst
633// ... - loops containing Dst but not Src
634// MaxLevels - innermost loops containing Dst but not Src
635// Consider the follow code fragment:
636// for (a = ...) {
637// for (b = ...) {
638// for (c = ...) {
639// for (d = ...) {
640// A[] = ...;
641// }
642// }
643// for (e = ...) {
644// for (f = ...) {
645// for (g = ...) {
646// ... = A[];
647// }
648// }
649// }
650// }
651// }
652// If we're looking at the possibility of a dependence between the store
653// to A (the Src) and the load from A (the Dst), we'll note that they
654// have 2 loops in common, so CommonLevels will equal 2 and the direction
655// vector for Result will have 2 entries. SrcLevels = 4 and MaxLevels = 7.
656// A map from loop names to loop numbers would look like
657// a - 1
658// b - 2 = CommonLevels
659// c - 3
660// d - 4 = SrcLevels
661// e - 5
662// f - 6
663// g - 7 = MaxLevels
664// SameSDLevels counts the number of levels after common levels that are
665// not common but have the same iteration space and depth. Internally this
666// is checked using haveSameSD. Currently we only need to check for SameSD
667// levels up to one level after the common levels, and therefore SameSDLevels
668// will be either 0 or 1.
669// 1. Assume that in this code fragment, levels c and e have the same iteration
670// space and depth, but levels d and f does not. Then SameSDLevels is set to 1.
671// In that case the level numbers for the previous code look like
672// a - 1
673// b - 2
674// c,e - 3 = CommonLevels
675// d - 4 = SrcLevels
676// f - 5
677// g - 6 = MaxLevels
678void DependenceInfo::establishNestingLevels(const Instruction *Src,
679 const Instruction *Dst) {
680 const BasicBlock *SrcBlock = Src->getParent();
681 const BasicBlock *DstBlock = Dst->getParent();
682 unsigned SrcLevel = LI->getLoopDepth(SrcBlock);
683 unsigned DstLevel = LI->getLoopDepth(DstBlock);
684 const Loop *SrcLoop = LI->getLoopFor(SrcBlock);
685 const Loop *DstLoop = LI->getLoopFor(DstBlock);
686 SrcLevels = SrcLevel;
687 MaxLevels = SrcLevel + DstLevel;
688 SameSDLevels = 0;
689 while (SrcLevel > DstLevel) {
690 SrcLoop = SrcLoop->getParentLoop();
691 SrcLevel--;
692 }
693 while (DstLevel > SrcLevel) {
694 DstLoop = DstLoop->getParentLoop();
695 DstLevel--;
696 }
697
698 const Loop *SrcUncommonFrontier = nullptr, *DstUncommonFrontier = nullptr;
699 // Find the first uncommon level pair and check if the associated levels have
700 // the SameSD.
701 while (SrcLoop != DstLoop) {
702 SrcUncommonFrontier = SrcLoop;
703 DstUncommonFrontier = DstLoop;
704 SrcLoop = SrcLoop->getParentLoop();
705 DstLoop = DstLoop->getParentLoop();
706 SrcLevel--;
707 }
708 if (SrcUncommonFrontier && DstUncommonFrontier &&
709 haveSameSD(SrcUncommonFrontier, DstUncommonFrontier))
710 SameSDLevels = 1;
711 CommonLevels = SrcLevel;
712 MaxLevels -= CommonLevels;
713}
714
715// Given one of the loops containing the source, return
716// its level index in our numbering scheme.
717unsigned DependenceInfo::mapSrcLoop(const Loop *SrcLoop) const {
718 return SrcLoop->getLoopDepth();
719}
720
721// Given one of the loops containing the destination,
722// return its level index in our numbering scheme.
723unsigned DependenceInfo::mapDstLoop(const Loop *DstLoop) const {
724 unsigned D = DstLoop->getLoopDepth();
725 if (D > CommonLevels)
726 // This tries to make sure that we assign unique numbers to src and dst when
727 // the memory accesses reside in different loops that have the same depth.
728 return D - CommonLevels + SrcLevels;
729 else
730 return D;
731}
732
733// Returns true if Expression is loop invariant in LoopNest.
734bool DependenceInfo::isLoopInvariant(const SCEV *Expression,
735 const Loop *LoopNest) const {
736 // Unlike ScalarEvolution::isLoopInvariant() we consider an access outside of
737 // any loop as invariant, because we only consier expression evaluation at a
738 // specific position (where the array access takes place), and not across the
739 // entire function.
740 if (!LoopNest)
741 return true;
742
743 // If the expression is invariant in the outermost loop of the loop nest, it
744 // is invariant anywhere in the loop nest.
745 return SE->isLoopInvariant(Expression, LoopNest->getOutermostLoop());
746}
747
748// Finds the set of loops from the LoopNest that
749// have a level <= CommonLevels and are referred to by the SCEV Expression.
750void DependenceInfo::collectCommonLoops(const SCEV *Expression,
751 const Loop *LoopNest,
752 SmallBitVector &Loops) const {
753 while (LoopNest) {
754 unsigned Level = LoopNest->getLoopDepth();
755 if (Level <= CommonLevels && !SE->isLoopInvariant(Expression, LoopNest))
756 Loops.set(Level);
757 LoopNest = LoopNest->getParentLoop();
758 }
759}
760
761// Examine the scev and return true iff it's affine.
762// Collect any loops mentioned in the set of "Loops".
763bool DependenceInfo::checkSubscript(const SCEV *Expr, const Loop *LoopNest,
764 SmallBitVector &Loops, bool IsSrc) {
765 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
766 if (!AddRec)
767 return isLoopInvariant(Expr, LoopNest);
768
769 // The AddRec must depend on one of the containing loops. Otherwise,
770 // mapSrcLoop and mapDstLoop return indices outside the intended range. This
771 // can happen when a subscript in one loop references an IV from a sibling
772 // loop that could not be replaced with a concrete exit value by
773 // getSCEVAtScope.
774 const Loop *L = LoopNest;
775 while (L && AddRec->getLoop() != L)
776 L = L->getParentLoop();
777 if (!L)
778 return false;
779
780 if (!AddRec->hasNoSignedWrap())
781 return false;
782
783 const SCEV *Start = AddRec->getStart();
784 const SCEV *Step = AddRec->getStepRecurrence(*SE);
785 if (!isLoopInvariant(Step, LoopNest))
786 return false;
787 if (IsSrc)
788 Loops.set(mapSrcLoop(AddRec->getLoop()));
789 else
790 Loops.set(mapDstLoop(AddRec->getLoop()));
791 return checkSubscript(Start, LoopNest, Loops, IsSrc);
792}
793
794// Examine the scev and return true iff it's linear.
795// Collect any loops mentioned in the set of "Loops".
796bool DependenceInfo::checkSrcSubscript(const SCEV *Src, const Loop *LoopNest,
798 return checkSubscript(Src, LoopNest, Loops, true);
799}
800
801// Examine the scev and return true iff it's linear.
802// Collect any loops mentioned in the set of "Loops".
803bool DependenceInfo::checkDstSubscript(const SCEV *Dst, const Loop *LoopNest,
805 return checkSubscript(Dst, LoopNest, Loops, false);
806}
807
808// Examines the subscript pair (the Src and Dst SCEVs)
809// and classifies it as either ZIV, SIV, RDIV, MIV, or Nonlinear.
810// Collects the associated loops in a set.
811DependenceInfo::Subscript::ClassificationKind
812DependenceInfo::classifyPair(const SCEV *Src, const Loop *SrcLoopNest,
813 const SCEV *Dst, const Loop *DstLoopNest,
815 SmallBitVector SrcLoops(MaxLevels + 1);
816 SmallBitVector DstLoops(MaxLevels + 1);
817 if (!checkSrcSubscript(Src, SrcLoopNest, SrcLoops))
818 return Subscript::NonLinear;
819 if (!checkDstSubscript(Dst, DstLoopNest, DstLoops))
820 return Subscript::NonLinear;
821 Loops = SrcLoops;
822 Loops |= DstLoops;
823 unsigned N = Loops.count();
824 if (N == 0)
825 return Subscript::ZIV;
826 if (N == 1)
827 return Subscript::SIV;
828 if (N == 2 && SrcLoops.count() == 1 && DstLoops.count() == 1)
829 return Subscript::RDIV;
830 return Subscript::MIV;
831}
832
833// All subscripts are all the same type.
834// Loop bound may be smaller (e.g., a char).
835// Should zero extend loop bound, since it's always >= 0.
836// This routine collects upper bound and extends or truncates if needed.
837// Truncating is safe when subscripts are known not to wrap. Cases without
838// nowrap flags should have been rejected earlier.
839// Return null if no bound available.
840const SCEV *DependenceInfo::collectUpperBound(const Loop *L, Type *T) const {
841 if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
842 const SCEV *UB = SE->getBackedgeTakenCount(L);
843 return SE->getTruncateOrZeroExtend(UB, T);
844 }
845 return nullptr;
846}
847
848// Calls collectUpperBound(), then attempts to cast it to APInt.
849// If the cast fails, returns std::nullopt.
850std::optional<APInt>
851DependenceInfo::collectNonNegativeConstantUpperBound(const Loop *L,
852 Type *T) const {
853 if (const SCEV *UB = collectUpperBound(L, T))
854 if (auto *C = dyn_cast<SCEVConstant>(UB)) {
855 APInt Res = C->getAPInt();
856 if (Res.isNonNegative())
857 return Res;
858 }
859 return std::nullopt;
860}
861
862/// Returns \p A - \p B if it guaranteed not to signed wrap. Otherwise returns
863/// nullptr. \p A and \p B must have the same integer type.
864static const SCEV *minusSCEVNoSignedOverflow(const SCEV *A, const SCEV *B,
865 ScalarEvolution &SE) {
866 if (SE.willNotOverflow(Instruction::Sub, /*Signed=*/true, A, B))
867 return SE.getMinusSCEV(A, B);
868 return nullptr;
869}
870
871/// Returns true iff \p Test is enabled.
872static bool isDependenceTestEnabled(const AnalysisOptions &Opts,
874 if (Opts.da_enable_dependence_test == DependenceTestType::All)
875 return true;
876 // The Banerjee test is disabled by default because of correctness issues,
877 // but can be enabled with -da-enable-dependence-test=banerjee-miv or
878 // -da-enable-dependence-test=all.
879 if (Opts.da_enable_dependence_test == DependenceTestType::Default)
881 return Opts.da_enable_dependence_test == Test;
882}
883
884// testZIV -
885// When we have a pair of subscripts of the form [c1] and [c2],
886// where c1 and c2 are both loop invariant, we attack it using
887// the ZIV test. Basically, we test by comparing the two values,
888// but there are actually three possible results:
889// 1) the values are equal, so there's a dependence
890// 2) the values are different, so there's no dependence
891// 3) the values might be equal, so we have to assume a dependence.
892//
893// Return true if dependence disproved.
894bool DependenceInfo::testZIV(const SCEV *Src, const SCEV *Dst,
895 FullDependence &Result) const {
896 LLVM_DEBUG(dbgs() << " src = " << *Src << "\n");
897 LLVM_DEBUG(dbgs() << " dst = " << *Dst << "\n");
898 ++ZIVapplications;
899 if (SE->isKnownPredicate(CmpInst::ICMP_EQ, Src, Dst)) {
900 LLVM_DEBUG(dbgs() << " provably dependent\n");
901 return false; // provably dependent
902 }
903 if (SE->isKnownPredicate(CmpInst::ICMP_NE, Src, Dst)) {
904 LLVM_DEBUG(dbgs() << " provably independent\n");
905 ++ZIVindependence;
906 return true; // provably independent
907 }
908 LLVM_DEBUG(dbgs() << " possibly dependent\n");
909 return false; // possibly dependent
910}
911
912// strongSIVtest -
913// From the paper, Practical Dependence Testing, Section 4.2.1
914//
915// When we have a pair of subscripts of the form [c1 + a*i] and [c2 + a*i],
916// where i is an induction variable, c1 and c2 are loop invariant,
917// and a is a constant, we can solve it exactly using the Strong SIV test.
918//
919// Can prove independence. Failing that, can compute distance (and direction).
920// In the presence of symbolic terms, we can sometimes make progress.
921//
922// If there's a dependence,
923//
924// c1 + a*i = c2 + a*i'
925//
926// The dependence distance is
927//
928// d = i' - i = (c1 - c2)/a
929//
930// A dependence only exists if d is an integer and abs(d) <= U, where U is the
931// loop's upper bound. If a dependence exists, the dependence direction is
932// defined as
933//
934// { < if d > 0
935// direction = { = if d = 0
936// { > if d < 0
937//
938// Return true if dependence disproved.
939bool DependenceInfo::strongSIVtest(const SCEVAddRecExpr *Src,
940 const SCEVAddRecExpr *Dst, unsigned Level,
941 FullDependence &Result,
942 bool UnderRuntimeAssumptions) {
944 return false;
945
946 const SCEV *Coeff = Src->getStepRecurrence(*SE);
947 assert(Coeff == Dst->getStepRecurrence(*SE) &&
948 "Expecting same coefficient in Strong SIV test");
949 const SCEV *SrcConst = Src->getStart();
950 const SCEV *DstConst = Dst->getStart();
951 LLVM_DEBUG(dbgs() << "\tStrong SIV test\n");
952 LLVM_DEBUG(dbgs() << "\t Coeff = " << *Coeff);
953 LLVM_DEBUG(dbgs() << ", " << *Coeff->getType() << "\n");
954 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst);
955 LLVM_DEBUG(dbgs() << ", " << *SrcConst->getType() << "\n");
956 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst);
957 LLVM_DEBUG(dbgs() << ", " << *DstConst->getType() << "\n");
958 ++StrongSIVapplications;
959 assert(0 < Level && Level <= CommonLevels && "level out of range");
960 Level--;
961
962 const SCEV *Delta = minusSCEVNoSignedOverflow(SrcConst, DstConst, *SE);
963 if (!Delta)
964 return false;
965 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta);
966 LLVM_DEBUG(dbgs() << ", " << *Delta->getType() << "\n");
967
968 // Can we compute distance?
969 if (isa<SCEVConstant>(Delta) && isa<SCEVConstant>(Coeff)) {
970 APInt ConstDelta = cast<SCEVConstant>(Delta)->getAPInt();
971 APInt ConstCoeff = cast<SCEVConstant>(Coeff)->getAPInt();
972 APInt Distance = ConstDelta; // these need to be initialized
973 APInt Remainder = ConstDelta;
974 APInt::sdivrem(ConstDelta, ConstCoeff, Distance, Remainder);
975 LLVM_DEBUG(dbgs() << "\t Distance = " << Distance << "\n");
976 LLVM_DEBUG(dbgs() << "\t Remainder = " << Remainder << "\n");
977 // Make sure Coeff divides Delta exactly
978 if (Remainder != 0) {
979 // Coeff doesn't divide Distance, no dependence
980 ++StrongSIVindependence;
981 ++StrongSIVsuccesses;
982 return true;
983 }
984 Result.DV[Level].Distance = SE->getConstant(Distance);
985 if (Distance.sgt(0))
986 Result.DV[Level].Direction &= Dependence::DVEntry::LT;
987 else if (Distance.slt(0))
988 Result.DV[Level].Direction &= Dependence::DVEntry::GT;
989 else
990 Result.DV[Level].Direction &= Dependence::DVEntry::EQ;
991 ++StrongSIVsuccesses;
992 } else if (Delta->isZero()) {
993 // Check if coefficient could be zero. If so, 0/0 is undefined and we
994 // cannot conclude that only same-iteration dependencies exist.
995 // When coeff=0, all iterations access the same location.
996 if (SE->isKnownNonZero(Coeff)) {
998 dbgs() << "\t Coefficient proven non-zero by SCEV analysis\n");
999 } else {
1000 // Cannot prove at compile time, would need runtime assumption.
1001 if (UnderRuntimeAssumptions) {
1002 const SCEVPredicate *Pred = SE->getComparePredicate(
1003 ICmpInst::ICMP_NE, Coeff, SE->getZero(Coeff->getType()));
1004 Result.Assumptions = Result.Assumptions.getUnionWith(Pred, *SE);
1005 LLVM_DEBUG(dbgs() << "\t Added runtime assumption: " << *Coeff
1006 << " != 0\n");
1007 } else {
1008 // Cannot add runtime assumptions, this test cannot handle this case.
1009 // Let more complex tests try.
1010 LLVM_DEBUG(dbgs() << "\t Would need runtime assumption " << *Coeff
1011 << " != 0, but not allowed. Failing this test.\n");
1012 return false;
1013 }
1014 }
1015 // Since 0/X == 0 (where X is known non-zero or assumed non-zero).
1016 Result.DV[Level].Distance = Delta;
1017 Result.DV[Level].Direction &= Dependence::DVEntry::EQ;
1018 ++StrongSIVsuccesses;
1019 } else {
1020 if (Coeff->isOne()) {
1021 LLVM_DEBUG(dbgs() << "\t Distance = " << *Delta << "\n");
1022 Result.DV[Level].Distance = Delta; // since X/1 == X
1023 }
1024
1025 // maybe we can get a useful direction
1026 bool DeltaMaybeZero = !SE->isKnownNonZero(Delta);
1027 bool DeltaMaybePositive = !SE->isKnownNonPositive(Delta);
1028 bool DeltaMaybeNegative = !SE->isKnownNonNegative(Delta);
1029 bool CoeffMaybePositive = !SE->isKnownNonPositive(Coeff);
1030 bool CoeffMaybeNegative = !SE->isKnownNonNegative(Coeff);
1031 // The double negatives above are confusing.
1032 // It helps to read !SE->isKnownNonZero(Delta)
1033 // as "Delta might be Zero"
1034 unsigned NewDirection = Dependence::DVEntry::NONE;
1035 if ((DeltaMaybePositive && CoeffMaybePositive) ||
1036 (DeltaMaybeNegative && CoeffMaybeNegative))
1037 NewDirection = Dependence::DVEntry::LT;
1038 if (DeltaMaybeZero)
1039 NewDirection |= Dependence::DVEntry::EQ;
1040 if ((DeltaMaybeNegative && CoeffMaybePositive) ||
1041 (DeltaMaybePositive && CoeffMaybeNegative))
1042 NewDirection |= Dependence::DVEntry::GT;
1043 if (NewDirection < Result.DV[Level].Direction)
1044 ++StrongSIVsuccesses;
1045 Result.DV[Level].Direction &= NewDirection;
1046 }
1047 return false;
1048}
1049
1050// weakCrossingSIVtest -
1051// From the paper, Practical Dependence Testing, Section 4.2.2
1052//
1053// When we have a pair of subscripts of the form [c1 + a*i] and [c2 - a*i],
1054// where i is an induction variable, c1 and c2 are loop invariant,
1055// and a is a constant, we can solve it exactly using the
1056// Weak-Crossing SIV test.
1057//
1058// Given c1 + a*i = c2 - a*i', we can look for the intersection of
1059// the two lines, where i = i', yielding
1060//
1061// c1 + a*i = c2 - a*i
1062// 2a*i = c2 - c1
1063// i = (c2 - c1)/2a
1064//
1065// If i < 0, there is no dependence.
1066// If i > upperbound, there is no dependence.
1067// If i = 0 (i.e., if c1 = c2), there's a dependence with distance = 0.
1068// If i = upperbound, there's a dependence with distance = 0.
1069// If i is integral, there's a dependence (all directions).
1070// If the non-integer part = 1/2, there's a dependence (<> directions).
1071// Otherwise, there's no dependence.
1072//
1073// Can prove independence. Failing that,
1074// can sometimes refine the directions.
1075// Can determine iteration for splitting.
1076//
1077// Return true if dependence disproved.
1078bool DependenceInfo::weakCrossingSIVtest(const SCEVAddRecExpr *Src,
1079 const SCEVAddRecExpr *Dst,
1080 unsigned Level,
1081 FullDependence &Result) const {
1083 return false;
1084
1085 const SCEV *Coeff = Src->getStepRecurrence(*SE);
1086 const SCEV *SrcConst = Src->getStart();
1087 const SCEV *DstConst = Dst->getStart();
1088
1089 assert(Coeff == SE->getNegativeSCEV(Dst->getStepRecurrence(*SE)) &&
1090 "Unexpected input for weakCrossingSIVtest");
1091
1092 LLVM_DEBUG(dbgs() << "\tWeak-Crossing SIV test\n");
1093 LLVM_DEBUG(dbgs() << "\t Coeff = " << *Coeff << "\n");
1094 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n");
1095 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n");
1096 ++WeakCrossingSIVapplications;
1097 assert(0 < Level && Level <= CommonLevels && "Level out of range");
1098 Level--;
1099 const SCEV *Delta = minusSCEVNoSignedOverflow(DstConst, SrcConst, *SE);
1100 if (!Delta)
1101 return false;
1102
1103 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n");
1104 const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(Coeff);
1105 if (!ConstCoeff)
1106 return false;
1107
1108 const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
1109 if (!ConstDelta)
1110 return false;
1111
1112 ConstantRange SrcRange = SE->getSignedRange(Src);
1113 ConstantRange DstRange = SE->getSignedRange(Dst);
1114 LLVM_DEBUG(dbgs() << "\t SrcRange = " << SrcRange << "\n");
1115 LLVM_DEBUG(dbgs() << "\t DstRange = " << DstRange << "\n");
1116 if (SrcRange.intersectWith(DstRange).isSingleElement()) {
1117 // The ranges touch at exactly one value (i = i' = 0 or i = i' = BTC).
1118 Result.DV[Level].Direction &= ~Dependence::DVEntry::LT;
1119 Result.DV[Level].Direction &= ~Dependence::DVEntry::GT;
1120 ++WeakCrossingSIVsuccesses;
1121 if (!Result.DV[Level].Direction) {
1122 ++WeakCrossingSIVindependence;
1123 return true;
1124 }
1125 Result.DV[Level].Distance = SE->getZero(Delta->getType());
1126 return false;
1127 }
1128
1129 // check that Coeff divides Delta
1130 APInt APDelta = ConstDelta->getAPInt();
1131 APInt APCoeff = ConstCoeff->getAPInt();
1132 APInt Distance = APDelta; // these need to be initialzed
1133 APInt Remainder = APDelta;
1134 APInt::sdivrem(APDelta, APCoeff, Distance, Remainder);
1135 LLVM_DEBUG(dbgs() << "\t Remainder = " << Remainder << "\n");
1136 if (Remainder != 0) {
1137 // Coeff doesn't divide Delta, no dependence
1138 ++WeakCrossingSIVindependence;
1139 ++WeakCrossingSIVsuccesses;
1140 return true;
1141 }
1142 LLVM_DEBUG(dbgs() << "\t Distance = " << Distance << "\n");
1143
1144 // if 2*Coeff doesn't divide Delta, then the equal direction isn't possible
1145 if (Distance[0]) {
1146 // Equal direction isn't possible
1147 Result.DV[Level].Direction &= ~Dependence::DVEntry::EQ;
1148 ++WeakCrossingSIVsuccesses;
1149 }
1150 return false;
1151}
1152
1153// Kirch's algorithm, from
1154//
1155// Optimizing Supercompilers for Supercomputers
1156// Michael Wolfe
1157// MIT Press, 1989
1158//
1159// Program 2.1, page 29.
1160// Computes the GCD of AM and BM.
1161// Also finds a solution to the equation ax - by = gcd(a, b).
1162// Returns true if dependence disproved; i.e., gcd does not divide Delta.
1163//
1164// We don't use OverflowSafeSignedAPInt here because it's known that this
1165// algorithm doesn't overflow.
1166static std::optional<bool> findGCD(unsigned Bits, const APInt &AM,
1167 const APInt &BM, const APInt &Delta,
1168 APInt &G, APInt &X, APInt &Y) {
1169 LLVM_DEBUG(dbgs() << "\t AM = " << AM << "\n");
1170 LLVM_DEBUG(dbgs() << "\t BM = " << BM << "\n");
1171 LLVM_DEBUG(dbgs() << "\t Delta = " << Delta << "\n");
1172 APInt A0(Bits, 1, true), A1(Bits, 0, true);
1173 APInt B0(Bits, 0, true), B1(Bits, 1, true);
1174
1175 // APInt::abs will overflow. In that case, bail out early.
1176 if (AM.isMinSignedValue() || BM.isMinSignedValue())
1177 return std::nullopt;
1178
1179 APInt G0 = AM.abs();
1180 APInt G1 = BM.abs();
1181 APInt Q = G0; // these need to be initialized
1182 APInt R = G0;
1183 APInt::sdivrem(G0, G1, Q, R);
1184 while (R != 0) {
1185 // clang-format off
1186 APInt A2 = A0 - Q*A1; A0 = A1; A1 = A2;
1187 APInt B2 = B0 - Q*B1; B0 = B1; B1 = B2;
1188 G0 = G1; G1 = R;
1189 // clang-format on
1190 APInt::sdivrem(G0, G1, Q, R);
1191 }
1192 G = G1;
1193 LLVM_DEBUG(dbgs() << "\t GCD = " << G << "\n");
1194 X = AM.slt(0) ? -A1 : A1;
1195 Y = BM.slt(0) ? B1 : -B1;
1196
1197 // make sure gcd divides Delta
1198 R = Delta.srem(G);
1199 if (R != 0)
1200 return true; // gcd doesn't divide Delta, no dependence
1201 Q = Delta.sdiv(G);
1202 return false;
1203}
1204
1205static OverflowSafeSignedAPInt
1206floorOfQuotient(const OverflowSafeSignedAPInt &OA,
1207 const OverflowSafeSignedAPInt &OB) {
1208 if (!OA || !OB)
1209 return OverflowSafeSignedAPInt();
1210
1211 APInt A = *OA;
1212 APInt B = *OB;
1213 APInt Q = A; // these need to be initialized
1214 APInt R = A;
1215 APInt::sdivrem(A, B, Q, R);
1216 if (R == 0)
1217 return Q;
1218 if ((A.sgt(0) && B.sgt(0)) || (A.slt(0) && B.slt(0)))
1219 return Q;
1220 return OverflowSafeSignedAPInt(Q) - 1;
1221}
1222
1223static OverflowSafeSignedAPInt
1224ceilingOfQuotient(const OverflowSafeSignedAPInt &OA,
1225 const OverflowSafeSignedAPInt &OB) {
1226 if (!OA || !OB)
1227 return OverflowSafeSignedAPInt();
1228
1229 APInt A = *OA;
1230 APInt B = *OB;
1231 APInt Q = A; // these need to be initialized
1232 APInt R = A;
1233 APInt::sdivrem(A, B, Q, R);
1234 if (R == 0)
1235 return Q;
1236 if ((A.sgt(0) && B.sgt(0)) || (A.slt(0) && B.slt(0)))
1237 return OverflowSafeSignedAPInt(Q) + 1;
1238 return Q;
1239}
1240
1241/// Given an affine expression of the form A*k + B, where k is an arbitrary
1242/// integer, infer the possible range of k based on the known range of the
1243/// affine expression. If we know A*k + B is non-negative, i.e.,
1244///
1245/// A*k + B >=s 0
1246///
1247/// we can derive the following inequalities for k when A is positive:
1248///
1249/// k >=s -B / A
1250///
1251/// Since k is an integer, it means k is greater than or equal to the
1252/// ceil(-B / A).
1253///
1254/// If the upper bound of the affine expression \p UB is passed, the following
1255/// inequality can be derived as well:
1256///
1257/// A*k + B <=s UB
1258///
1259/// which leads to:
1260///
1261/// k <=s (UB - B) / A
1262///
1263/// Again, as k is an integer, it means k is less than or equal to the
1264/// floor((UB - B) / A).
1265///
1266/// The similar logic applies when A is negative, but the inequalities sign flip
1267/// while working with them.
1268///
1269/// Preconditions: \p A is non-zero, and we know A*k + B and \p UB are
1270/// non-negative.
1271static std::pair<OverflowSafeSignedAPInt, OverflowSafeSignedAPInt>
1272inferDomainOfAffine(OverflowSafeSignedAPInt A, OverflowSafeSignedAPInt B,
1273 OverflowSafeSignedAPInt UB) {
1274 assert(A && B && "A and B must be available");
1275 assert(*A != 0 && "A must be non-zero");
1276 assert((!UB || UB->isNonNegative()) && "UB must be non-negative");
1277 OverflowSafeSignedAPInt TL, TU;
1278 if (A->sgt(0)) {
1279 TL = ceilingOfQuotient(-B, A);
1280 LLVM_DEBUG(if (TL) dbgs() << "\t Possible TL = " << *TL << "\n");
1281
1282 // New bound check - modification to Banerjee's e3 check
1283 TU = floorOfQuotient(UB - B, A);
1284 LLVM_DEBUG(if (TU) dbgs() << "\t Possible TU = " << *TU << "\n");
1285 } else {
1286 TU = floorOfQuotient(-B, A);
1287 LLVM_DEBUG(if (TU) dbgs() << "\t Possible TU = " << *TU << "\n");
1288
1289 // New bound check - modification to Banerjee's e3 check
1290 TL = ceilingOfQuotient(UB - B, A);
1291 LLVM_DEBUG(if (TL) dbgs() << "\t Possible TL = " << *TL << "\n");
1292 }
1293 return std::make_pair(TL, TU);
1294}
1295
1296// exactSIVtest -
1297// When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*i],
1298// where i is an induction variable, c1 and c2 are loop invariant, and a1
1299// and a2 are constant, we can solve it exactly using an algorithm developed
1300// by Banerjee and Wolfe. See Algorithm 6.2.1 (case 2.5) in:
1301//
1302// Dependence Analysis for Supercomputing
1303// Utpal Banerjee
1304// Kluwer Academic Publishers, 1988
1305//
1306// It's slower than the specialized tests (strong SIV, weak-zero SIV, etc),
1307// so use them if possible. They're also a bit better with symbolics and,
1308// in the case of the strong SIV test, can compute Distances.
1309//
1310// Return true if dependence disproved.
1311//
1312// This is a modified version of the original Banerjee algorithm. The original
1313// only tested whether Dst depends on Src. This algorithm extends that and
1314// returns all the dependencies that exist between Dst and Src.
1315bool DependenceInfo::exactSIVtest(const SCEVAddRecExpr *Src,
1316 const SCEVAddRecExpr *Dst, unsigned Level,
1317 FullDependence &Result) const {
1319 return false;
1320
1321 LLVM_DEBUG(dbgs() << "\tExact SIV test\n");
1322 ++ExactSIVapplications;
1323 assert(0 < Level && Level <= CommonLevels && "Level out of range");
1324 Level--;
1325 bool Res = exactTestImpl(Src, Dst, Result, Level);
1326 if (Res) {
1327 ++ExactSIVsuccesses;
1328 ++ExactSIVindependence;
1329 }
1330 return Res;
1331}
1332
1333// Return true if the divisor evenly divides the dividend.
1334static bool isRemainderZero(const SCEVConstant *Dividend,
1335 const SCEVConstant *Divisor) {
1336 const APInt &ConstDividend = Dividend->getAPInt();
1337 const APInt &ConstDivisor = Divisor->getAPInt();
1338 return ConstDividend.srem(ConstDivisor) == 0;
1339}
1340
1341bool DependenceInfo::weakZeroSIVtestImpl(const SCEVAddRecExpr *AR,
1342 const SCEV *Const, unsigned Level,
1343 FullDependence &Result) const {
1344 const SCEV *ARCoeff = AR->getStepRecurrence(*SE);
1345 const SCEV *ARConst = AR->getStart();
1346
1347 if (Const == ARConst && SE->isKnownNonZero(ARCoeff)) {
1348 if (Level < CommonLevels) {
1349 Result.DV[Level].Direction &= Dependence::DVEntry::LE;
1350 ++WeakZeroSIVsuccesses;
1351 }
1352 return false; // dependences caused by first iteration
1353 }
1354
1355 const SCEV *Delta = minusSCEVNoSignedOverflow(Const, ARConst, *SE);
1356 if (!Delta)
1357 return false;
1358 const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(ARCoeff);
1359 if (!ConstCoeff)
1360 return false;
1361
1362 if (const SCEV *UpperBound =
1363 collectUpperBound(AR->getLoop(), Delta->getType())) {
1364 LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound << "\n");
1365 bool OverlapAtLast = [&] {
1366 if (!SE->isKnownNonZero(ConstCoeff))
1367 return false;
1368 const SCEV *Last = AR->evaluateAtIteration(UpperBound, *SE);
1369 return Last == Const;
1370 }();
1371 if (OverlapAtLast) {
1372 // dependences caused by last iteration
1373 if (Level < CommonLevels) {
1374 Result.DV[Level].Direction &= Dependence::DVEntry::GE;
1375 ++WeakZeroSIVsuccesses;
1376 }
1377 return false;
1378 }
1379 }
1380
1381 // if ARCoeff doesn't divide Delta, then no dependence
1382 if (isa<SCEVConstant>(Delta) &&
1383 !isRemainderZero(cast<SCEVConstant>(Delta), ConstCoeff)) {
1384 ++WeakZeroSIVindependence;
1385 ++WeakZeroSIVsuccesses;
1386 return true;
1387 }
1388 return false;
1389}
1390
1391// weakZeroSrcSIVtest -
1392// From the paper, Practical Dependence Testing, Section 4.2.2
1393//
1394// When we have a pair of subscripts of the form [c1] and [c2 + a*i],
1395// where i is an induction variable, c1 and c2 are loop invariant,
1396// and a is a constant, we can solve it exactly using the
1397// Weak-Zero SIV test.
1398//
1399// Given
1400//
1401// c1 = c2 + a*i
1402//
1403// we get
1404//
1405// (c1 - c2)/a = i
1406//
1407// If i is not an integer, there's no dependence.
1408// If i < 0 or > UB, there's no dependence.
1409// If i = 0, the direction is >=.
1410// If i = UB, the direction is <=.
1411// Otherwise, the direction is *.
1412//
1413// Can prove independence. Failing that, we can sometimes refine
1414// the directions. Can sometimes show that first or last
1415// iteration carries all the dependences (so worth peeling).
1416//
1417// (see also weakZeroDstSIVtest)
1418//
1419// Return true if dependence disproved.
1420bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *SrcConst,
1421 const SCEVAddRecExpr *Dst,
1422 unsigned Level,
1423 FullDependence &Result) const {
1425 return false;
1426
1427 // For the WeakSIV test, it's possible the loop isn't common to
1428 // the Src and Dst loops. If it isn't, then there's no need to
1429 // record a direction.
1430 [[maybe_unused]] const SCEV *DstCoeff = Dst->getStepRecurrence(*SE);
1431 [[maybe_unused]] const SCEV *DstConst = Dst->getStart();
1432 LLVM_DEBUG(dbgs() << "\tWeak-Zero (src) SIV test\n");
1433 LLVM_DEBUG(dbgs() << "\t DstCoeff = " << *DstCoeff << "\n");
1434 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n");
1435 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n");
1436 ++WeakZeroSIVapplications;
1437 assert(0 < Level && Level <= MaxLevels && "Level out of range");
1438 Level--;
1439
1440 // We have analyzed a dependence from Src to Dst, so \c Result may represent a
1441 // dependence in that direction. However, \c weakZeroSIVtestImpl will analyze
1442 // a dependence from \c Dst to \c SrcConst. To keep the consistency, we need
1443 // to negate the current result before passing it to \c weakZeroSIVtestImpl,
1444 // and negate it back after that.
1445 Result.negate(*SE);
1446 bool Res = weakZeroSIVtestImpl(Dst, SrcConst, Level, Result);
1447 Result.negate(*SE);
1448 return Res;
1449}
1450
1451// weakZeroDstSIVtest -
1452// From the paper, Practical Dependence Testing, Section 4.2.2
1453//
1454// When we have a pair of subscripts of the form [c1 + a*i] and [c2],
1455// where i is an induction variable, c1 and c2 are loop invariant,
1456// and a is a constant, we can solve it exactly using the
1457// Weak-Zero SIV test.
1458//
1459// Given
1460//
1461// c1 + a*i = c2
1462//
1463// we get
1464//
1465// i = (c2 - c1)/a
1466//
1467// If i is not an integer, there's no dependence.
1468// If i < 0 or > UB, there's no dependence.
1469// If i = 0, the direction is <=.
1470// If i = UB, the direction is >=.
1471// Otherwise, the direction is *.
1472//
1473// Can prove independence. Failing that, we can sometimes refine
1474// the directions. Can sometimes show that first or last
1475// iteration carries all the dependences (so worth peeling).
1476//
1477// (see also weakZeroSrcSIVtest)
1478//
1479// Return true if dependence disproved.
1480bool DependenceInfo::weakZeroDstSIVtest(const SCEVAddRecExpr *Src,
1481 const SCEV *DstConst, unsigned Level,
1482 FullDependence &Result) const {
1484 return false;
1485
1486 // For the WeakSIV test, it's possible the loop isn't common to the
1487 // Src and Dst loops. If it isn't, then there's no need to record a direction.
1488 [[maybe_unused]] const SCEV *SrcCoeff = Src->getStepRecurrence(*SE);
1489 [[maybe_unused]] const SCEV *SrcConst = Src->getStart();
1490 LLVM_DEBUG(dbgs() << "\tWeak-Zero (dst) SIV test\n");
1491 LLVM_DEBUG(dbgs() << "\t SrcCoeff = " << *SrcCoeff << "\n");
1492 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n");
1493 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n");
1494 ++WeakZeroSIVapplications;
1495 assert(0 < Level && Level <= SrcLevels && "Level out of range");
1496 Level--;
1497
1498 return weakZeroSIVtestImpl(Src, DstConst, Level, Result);
1499}
1500
1501// exactRDIVtest - Tests the RDIV subscript pair for dependence.
1502// Things of the form [c1 + a*i] and [c2 + b*j],
1503// where i and j are induction variable, c1 and c2 are loop invariant,
1504// and a and b are constants.
1505// Returns true if any possible dependence is disproved.
1506// Works in some cases that symbolicRDIVtest doesn't, and vice versa.
1507bool DependenceInfo::exactRDIVtest(const SCEVAddRecExpr *Src,
1508 const SCEVAddRecExpr *Dst,
1509 FullDependence &Result) const {
1511 return false;
1512
1513 LLVM_DEBUG(dbgs() << "\tExact RDIV test\n");
1514 ++ExactRDIVapplications;
1515 bool Res = exactTestImpl(Src, Dst, Result, std::nullopt);
1516 if (Res)
1517 ++ExactRDIVindependence;
1518 return Res;
1519}
1520
1521bool DependenceInfo::exactTestImpl(const SCEVAddRecExpr *Src,
1522 const SCEVAddRecExpr *Dst,
1523 FullDependence &Result,
1524 std::optional<unsigned> Level) const {
1525 const SCEV *SrcCoeff = Src->getStepRecurrence(*SE);
1526 const SCEV *SrcConst = Src->getStart();
1527 const SCEV *DstCoeff = Dst->getStepRecurrence(*SE);
1528 const SCEV *DstConst = Dst->getStart();
1529 LLVM_DEBUG(dbgs() << "\t SrcCoeff = " << *SrcCoeff << "\n");
1530 LLVM_DEBUG(dbgs() << "\t DstCoeff = " << *DstCoeff << "\n");
1531 LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n");
1532 LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n");
1533
1534 const SCEV *Delta = minusSCEVNoSignedOverflow(DstConst, SrcConst, *SE);
1535 if (!Delta)
1536 return false;
1537 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n");
1538 const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
1539 const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
1540 const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
1541 if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
1542 return false;
1543
1544 // find gcd
1545 APInt G, X, Y;
1546 APInt AM = ConstSrcCoeff->getAPInt();
1547 APInt BM = ConstDstCoeff->getAPInt();
1548 APInt CM = ConstDelta->getAPInt();
1549 unsigned Bits = AM.getBitWidth();
1550 std::optional<bool> GCDRes = findGCD(Bits, AM, BM, CM, G, X, Y);
1551
1552 // GCD calculation failed so we cannot proceed with this test.
1553 if (!GCDRes)
1554 return false;
1555 if (*GCDRes) {
1556 // gcd doesn't divide Delta, no dependence
1557 return true;
1558 }
1559
1560 LLVM_DEBUG(dbgs() << "\t X = " << X << ", Y = " << Y << "\n");
1561
1562 // since SCEV construction seems to normalize, LM = 0
1563 std::optional<APInt> SrcUM =
1564 collectNonNegativeConstantUpperBound(Src->getLoop(), Delta->getType());
1565 if (SrcUM)
1566 LLVM_DEBUG(dbgs() << "\t SrcUM = " << *SrcUM << "\n");
1567
1568 std::optional<APInt> DstUM =
1569 collectNonNegativeConstantUpperBound(Dst->getLoop(), Delta->getType());
1570 if (DstUM)
1571 LLVM_DEBUG(dbgs() << "\t DstUM = " << *DstUM << "\n");
1572
1573 OverflowSafeSignedAPInt TC = CM.sdiv(G);
1574 OverflowSafeSignedAPInt TX = OverflowSafeSignedAPInt(X) * TC;
1575 OverflowSafeSignedAPInt TY = OverflowSafeSignedAPInt(Y) * TC;
1576 if (!TC || !TX || !TY)
1577 return false;
1578 LLVM_DEBUG(dbgs() << "\t TC = " << *TC << "\n");
1579 LLVM_DEBUG(dbgs() << "\t TX = " << *TX << "\n");
1580 LLVM_DEBUG(dbgs() << "\t TY = " << *TY << "\n");
1581
1582 APInt TB = BM.sdiv(G);
1583 APInt TA = AM.sdiv(G);
1584
1585 // At this point, we have the following equations:
1586 //
1587 // TA*i - TB*j = TC
1588 //
1589 // Also, we know that the all pairs of (i, j) can be expressed as:
1590 //
1591 // (TX + k*TB, TY + k*TA)
1592 //
1593 // where k is an arbitrary integer.
1594 auto [TL0, TU0] = inferDomainOfAffine(TB, TX, SrcUM);
1595 auto [TL1, TU1] = inferDomainOfAffine(TA, TY, DstUM);
1596
1597 LLVM_DEBUG(dbgs() << "\t TA = " << TA << "\n");
1598 LLVM_DEBUG(dbgs() << "\t TB = " << TB << "\n");
1599
1600 auto GetMaxOrMin = [](const OverflowSafeSignedAPInt &V0,
1601 const OverflowSafeSignedAPInt &V1,
1602 bool IsMin) -> std::optional<APInt> {
1603 if (V0 && V1)
1604 return IsMin ? APIntOps::smin(*V0, *V1) : APIntOps::smax(*V0, *V1);
1605 if (V0)
1606 return *V0;
1607 if (V1)
1608 return *V1;
1609 return std::nullopt;
1610 };
1611
1612 std::optional<APInt> OptTL = GetMaxOrMin(TL0, TL1, false);
1613 std::optional<APInt> OptTU = GetMaxOrMin(TU0, TU1, true);
1614 if (!OptTL || !OptTU)
1615 return false;
1616
1617 APInt TL = std::move(*OptTL);
1618 APInt TU = std::move(*OptTU);
1619 LLVM_DEBUG(dbgs() << "\t TL = " << TL << "\n");
1620 LLVM_DEBUG(dbgs() << "\t TU = " << TU << "\n");
1621
1622 if (TL.sgt(TU))
1623 return true;
1624
1625 if (!Level)
1626 return false;
1627 assert(SrcUM == DstUM && "Expecting same upper bound for Src and Dst");
1628
1629 // explore directions
1630 unsigned NewDirection = Dependence::DVEntry::NONE;
1631 OverflowSafeSignedAPInt LowerDistance, UpperDistance;
1632 OverflowSafeSignedAPInt OTY(TY), OTX(TX), OTA(TA), OTB(TB), OTL(TL), OTU(TU);
1633 // NOTE: It's unclear whether these calculations can overflow. At the moment,
1634 // we conservatively assume they can.
1635 if (TA.sgt(TB)) {
1636 LowerDistance = (OTY - OTX) + (OTA - OTB) * OTL;
1637 UpperDistance = (OTY - OTX) + (OTA - OTB) * OTU;
1638 } else {
1639 LowerDistance = (OTY - OTX) + (OTA - OTB) * OTU;
1640 UpperDistance = (OTY - OTX) + (OTA - OTB) * OTL;
1641 }
1642
1643 if (!LowerDistance || !UpperDistance)
1644 return false;
1645
1646 LLVM_DEBUG(dbgs() << "\t LowerDistance = " << *LowerDistance << "\n");
1647 LLVM_DEBUG(dbgs() << "\t UpperDistance = " << *UpperDistance << "\n");
1648
1649 if (LowerDistance->sle(0) && UpperDistance->sge(0))
1650 NewDirection |= Dependence::DVEntry::EQ;
1651 if (LowerDistance->slt(0))
1652 NewDirection |= Dependence::DVEntry::GT;
1653 if (UpperDistance->sgt(0))
1654 NewDirection |= Dependence::DVEntry::LT;
1655
1656 // finished
1657 Result.DV[*Level].Direction &= NewDirection;
1658 LLVM_DEBUG(dbgs() << "\t Result = ");
1659 LLVM_DEBUG(Result.dump(dbgs()));
1660 return Result.DV[*Level].Direction == Dependence::DVEntry::NONE;
1661}
1662
1663// testSIV -
1664// When we have a pair of subscripts of the form [c1 + a1*i] and [c2 - a2*i]
1665// where i is an induction variable, c1 and c2 are loop invariant, and a1 and
1666// a2 are constant, we attack it with an SIV test. While they can all be
1667// solved with the Exact SIV test, it's worthwhile to use simpler tests when
1668// they apply; they're cheaper and sometimes more precise.
1669//
1670// Return true if dependence disproved.
1671bool DependenceInfo::testSIV(const SCEV *Src, const SCEV *Dst, unsigned &Level,
1672 FullDependence &Result,
1673 bool UnderRuntimeAssumptions) {
1674 LLVM_DEBUG(dbgs() << " src = " << *Src << "\n");
1675 LLVM_DEBUG(dbgs() << " dst = " << *Dst << "\n");
1676 const SCEVAddRecExpr *SrcAddRec = dyn_cast<SCEVAddRecExpr>(Src);
1677 const SCEVAddRecExpr *DstAddRec = dyn_cast<SCEVAddRecExpr>(Dst);
1678 if (SrcAddRec && DstAddRec) {
1679 const SCEV *SrcCoeff = SrcAddRec->getStepRecurrence(*SE);
1680 const SCEV *DstCoeff = DstAddRec->getStepRecurrence(*SE);
1681 const Loop *CurSrcLoop = SrcAddRec->getLoop();
1682 [[maybe_unused]] const Loop *CurDstLoop = DstAddRec->getLoop();
1683 assert(haveSameSD(CurSrcLoop, CurDstLoop) &&
1684 "Loops in the SIV test should have the same iteration space and "
1685 "depth");
1686 Level = mapSrcLoop(CurSrcLoop);
1687 bool disproven = false;
1688 if (SrcCoeff == DstCoeff)
1689 disproven = strongSIVtest(SrcAddRec, DstAddRec, Level, Result,
1690 UnderRuntimeAssumptions);
1691 else if (SrcCoeff == SE->getNegativeSCEV(DstCoeff))
1692 disproven = weakCrossingSIVtest(SrcAddRec, DstAddRec, Level, Result);
1693 return disproven || exactSIVtest(SrcAddRec, DstAddRec, Level, Result);
1694 }
1695 if (SrcAddRec) {
1696 const Loop *CurSrcLoop = SrcAddRec->getLoop();
1697 Level = mapSrcLoop(CurSrcLoop);
1698 return weakZeroDstSIVtest(SrcAddRec, Dst, Level, Result);
1699 }
1700 if (DstAddRec) {
1701 const Loop *CurDstLoop = DstAddRec->getLoop();
1702 Level = mapDstLoop(CurDstLoop);
1703 return weakZeroSrcSIVtest(Src, DstAddRec, Level, Result);
1704 }
1705 llvm_unreachable("SIV test expected at least one AddRec");
1706 return false;
1707}
1708
1709// testRDIV -
1710// When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*j]
1711// where i and j are induction variables, c1 and c2 are loop invariant,
1712// and a1 and a2 are constant, we can solve it exactly with an easy adaptation
1713// of the Exact SIV test, the Restricted Double Index Variable (RDIV) test.
1714// It doesn't make sense to talk about distance or direction in this case,
1715// so there's no point in making special versions of the Strong SIV test or
1716// the Weak-crossing SIV test.
1717//
1718// Return true if dependence disproved.
1719bool DependenceInfo::testRDIV(const SCEV *Src, const SCEV *Dst,
1720 FullDependence &Result) const {
1721 LLVM_DEBUG(dbgs() << " src = " << *Src << "\n");
1722 LLVM_DEBUG(dbgs() << " dst = " << *Dst << "\n");
1723 const SCEVAddRecExpr *SrcAddRec = dyn_cast<SCEVAddRecExpr>(Src);
1724 const SCEVAddRecExpr *DstAddRec = dyn_cast<SCEVAddRecExpr>(Dst);
1725 assert(SrcAddRec && DstAddRec && "Unexpected non-addrec input");
1726 return exactRDIVtest(SrcAddRec, DstAddRec, Result) ||
1727 gcdMIVtest(Src, Dst, Result);
1728}
1729
1730// Tests the single-subscript MIV pair (Src and Dst) for dependence.
1731// Return true if dependence disproved.
1732// Can sometimes refine direction vectors.
1733bool DependenceInfo::testMIV(const SCEV *Src, const SCEV *Dst,
1734 const SmallBitVector &Loops,
1735 FullDependence &Result) const {
1736 LLVM_DEBUG(dbgs() << " src = " << *Src << "\n");
1737 LLVM_DEBUG(dbgs() << " dst = " << *Dst << "\n");
1738 return gcdMIVtest(Src, Dst, Result) ||
1739 banerjeeMIVtest(Src, Dst, Loops, Result);
1740}
1741
1742/// Given a SCEVMulExpr, returns its first operand if its first operand is a
1743/// constant and the product doesn't overflow in a signed sense. Otherwise,
1744/// returns std::nullopt. For example, given (10 * X * Y)<nsw>, it returns 10.
1745/// Notably, if it doesn't have nsw, the multiplication may overflow, and if
1746/// so, it may not a multiple of 10.
1747static std::optional<APInt> getConstantCoefficient(const SCEV *Expr) {
1748 if (const auto *Constant = dyn_cast<SCEVConstant>(Expr))
1749 return Constant->getAPInt();
1750 if (const auto *Product = dyn_cast<SCEVMulExpr>(Expr))
1751 if (const auto *Constant = dyn_cast<SCEVConstant>(Product->getOperand(0)))
1752 if (Product->hasNoSignedWrap())
1753 return Constant->getAPInt();
1754 return std::nullopt;
1755}
1756
1757const SCEV *DependenceInfo::accumulateCoefficientsGCD(const SCEV *Expr,
1758 const Loop *CurLoop,
1759 const SCEV *&CurLoopCoeff,
1760 APInt &RunningGCD) const {
1761 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
1762 if (!AddRec) {
1763 assert(isLoopInvariant(Expr, CurLoop) &&
1764 "Expected loop invariant expression");
1765 return Expr;
1766 }
1767
1768 assert(AddRec->isAffine() && "Unexpected Expr");
1769 const SCEV *Start = AddRec->getStart();
1770 const SCEV *Step = AddRec->getStepRecurrence(*SE);
1771 if (AddRec->getLoop() == CurLoop) {
1772 CurLoopCoeff = Step;
1773 } else {
1774 std::optional<APInt> ConstCoeff = getConstantCoefficient(Step);
1775
1776 // If the coefficient is the product of a constant and other stuff, we can
1777 // use the constant in the GCD computation.
1778 if (!ConstCoeff)
1779 return nullptr;
1780
1781 // TODO: What happens if ConstCoeff is the "most negative" signed number
1782 // (e.g. -128 for 8 bit wide APInt)?
1783 RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff->abs());
1784 }
1785
1786 return accumulateCoefficientsGCD(Start, CurLoop, CurLoopCoeff, RunningGCD);
1787}
1788
1789//===----------------------------------------------------------------------===//
1790// gcdMIVtest -
1791// Tests an MIV subscript pair for dependence.
1792// Returns true if any possible dependence is disproved.
1793// Can sometimes disprove the equal direction for 1 or more loops,
1794// as discussed in Michael Wolfe's book,
1795// High Performance Compilers for Parallel Computing, page 235.
1796//
1797// We spend some effort (code!) to handle cases like
1798// [10*i + 5*N*j + 15*M + 6], where i and j are induction variables,
1799// but M and N are just loop-invariant variables.
1800// This should help us handle linearized subscripts;
1801// also makes this test a useful backup to the various SIV tests.
1802//
1803// It occurs to me that the presence of loop-invariant variables
1804// changes the nature of the test from "greatest common divisor"
1805// to "a common divisor".
1806bool DependenceInfo::gcdMIVtest(const SCEV *Src, const SCEV *Dst,
1807 FullDependence &Result) const {
1809 return false;
1810
1811 LLVM_DEBUG(dbgs() << "starting gcd\n");
1812 ++GCDapplications;
1813 unsigned BitWidth = SE->getTypeSizeInBits(Src->getType());
1814 APInt RunningGCD = APInt::getZero(BitWidth);
1815
1816 const SCEV *Dummy = nullptr;
1817 const SCEV *SrcConst =
1818 accumulateCoefficientsGCD(Src, nullptr, Dummy, RunningGCD);
1819 if (!SrcConst)
1820 return false;
1821 const SCEV *DstConst =
1822 accumulateCoefficientsGCD(Dst, nullptr, Dummy, RunningGCD);
1823 if (!DstConst)
1824 return false;
1825
1826 const SCEV *Delta = minusSCEVNoSignedOverflow(DstConst, SrcConst, *SE);
1827 if (!Delta)
1828 return false;
1829 LLVM_DEBUG(dbgs() << " Delta = " << *Delta << "\n");
1830 const SCEVConstant *Constant = dyn_cast<SCEVConstant>(Delta);
1831 if (!Constant)
1832 return false;
1833 APInt ConstDelta = Constant->getAPInt();
1834 LLVM_DEBUG(dbgs() << " ConstDelta = " << ConstDelta << "\n");
1835 if (ConstDelta == 0)
1836 return false;
1837 LLVM_DEBUG(dbgs() << " RunningGCD = " << RunningGCD << "\n");
1838 APInt Remainder = ConstDelta.srem(RunningGCD);
1839 if (Remainder != 0) {
1840 ++GCDindependence;
1841 return true;
1842 }
1843
1844 // Try to disprove equal directions.
1845 // For example, given a subscript pair [3*i + 2*j] and [i' + 2*j' - 1],
1846 // the code above can't disprove the dependence because the GCD = 1.
1847 // So we consider what happen if i = i' and what happens if j = j'.
1848 // If i = i', we can simplify the subscript to [2*i + 2*j] and [2*j' - 1],
1849 // which is infeasible, so we can disallow the = direction for the i level.
1850 // Setting j = j' doesn't help matters, so we end up with a direction vector
1851 // of [<>, *]
1852
1853 bool Improved = false;
1854 const SCEV *Coefficients = Src;
1855 while (const SCEVAddRecExpr *AddRec =
1856 dyn_cast<SCEVAddRecExpr>(Coefficients)) {
1857 Coefficients = AddRec->getStart();
1858 const Loop *CurLoop = AddRec->getLoop();
1859 RunningGCD = 0;
1860 const SCEV *SrcCoeff = AddRec->getStepRecurrence(*SE);
1861 const SCEV *DstCoeff = SE->getZero(SrcCoeff->getType());
1862
1863 if (!accumulateCoefficientsGCD(Src, CurLoop, SrcCoeff, RunningGCD) ||
1864 !accumulateCoefficientsGCD(Dst, CurLoop, DstCoeff, RunningGCD))
1865 return false;
1866
1867 Delta = minusSCEVNoSignedOverflow(DstCoeff, SrcCoeff, *SE);
1868 if (!Delta)
1869 continue;
1870 // If the coefficient is the product of a constant and other stuff,
1871 // we can use the constant in the GCD computation.
1872 std::optional<APInt> ConstCoeff = getConstantCoefficient(Delta);
1873 if (!ConstCoeff)
1874 // The difference of the two coefficients might not be a product
1875 // or constant, in which case we give up on this direction.
1876 continue;
1877 RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff->abs());
1878 LLVM_DEBUG(dbgs() << "\tRunningGCD = " << RunningGCD << "\n");
1879 if (RunningGCD != 0) {
1880 Remainder = ConstDelta.srem(RunningGCD);
1881 LLVM_DEBUG(dbgs() << "\tRemainder = " << Remainder << "\n");
1882 if (Remainder != 0) {
1883 unsigned Level = mapSrcLoop(CurLoop);
1884 Result.DV[Level - 1].Direction &= ~Dependence::DVEntry::EQ;
1885 Improved = true;
1886 }
1887 }
1888 }
1889 if (Improved)
1890 ++GCDsuccesses;
1891 LLVM_DEBUG(dbgs() << "all done\n");
1892 return false;
1893}
1894
1895//===----------------------------------------------------------------------===//
1896
1897namespace {
1898/// A closed signed interval containing the possible values of part of the
1899/// Banerjee subscript-difference expression.
1900/// A null Lower denotes -infinity, and a null Upper denotes +infinity. If
1901/// both finite endpoints are in reverse signed order (Lower >s Upper), the
1902/// interval is empty.
1903struct BanerjeeInterval {
1904 const SCEV *Lower;
1905 const SCEV *Upper;
1906
1907 BanerjeeInterval(const SCEV *Lower, const SCEV *Upper)
1908 : Lower(Lower), Upper(Upper) {}
1909
1910 bool isEmpty(ScalarEvolution &SE) const {
1911 return Lower && Upper &&
1913 }
1914};
1915} // namespace
1916
1917/// Add two intervals. A missing endpoint propagates the corresponding
1918/// infinity.
1919static BanerjeeInterval addIntervals(const BanerjeeInterval &A,
1920 const BanerjeeInterval &B,
1921 ScalarEvolution &SE) {
1922 const SCEV *Lower = nullptr;
1923 const SCEV *Upper = nullptr;
1924 if (A.Lower && B.Lower)
1925 Lower = SE.getAddExpr(A.Lower, B.Lower);
1926 if (A.Upper && B.Upper)
1927 Upper = SE.getAddExpr(A.Upper, B.Upper);
1928 return BanerjeeInterval(Lower, Upper);
1929}
1930
1931/// Intersect two intervals. Both inputs conservatively contain the feasible
1932/// values, so their intersection does too and may provide tighter one-sided
1933/// bounds.
1934static BanerjeeInterval intersectIntervals(const BanerjeeInterval &A,
1935 const BanerjeeInterval &B,
1936 ScalarEvolution &SE) {
1937 const SCEV *Lower = A.Lower;
1938 const SCEV *Upper = A.Upper;
1939 if (B.Lower)
1940 Lower = Lower ? SE.getSMaxExpr(Lower, B.Lower) : B.Lower;
1941 if (B.Upper)
1942 Upper = Upper ? SE.getSMinExpr(Upper, B.Upper) : B.Upper;
1943 return BanerjeeInterval(Lower, Upper);
1944}
1945
1946/// Return the singleton interval containing \p C.
1947static BanerjeeInterval constantInterval(const SCEV *C) {
1948 return BanerjeeInterval(C, C);
1949}
1950
1951/// Return the canonical empty interval [1, 0].
1952static BanerjeeInterval emptyInterval(Type *Ty, ScalarEvolution &SE) {
1953 return BanerjeeInterval(SE.getOne(Ty), SE.getZero(Ty));
1954}
1955
1956/// Compute the range of \p Coeff * X for \p Lower <=s X <=s \p Upper.
1957static BanerjeeInterval signedRangeInterval(const SCEV *Coeff,
1958 const SCEV *Lower,
1959 const SCEV *Upper,
1960 ScalarEvolution &SE) {
1961 // Coeff and the endpoints have already been extended to WideType. The
1962 // width proof in banerjeeMIVtest guarantees that these multiplications do
1963 // not wrap, so their SCEV values match mathematical signed integers.
1964 const SCEV *LowerValue = SE.getMulExpr(Coeff, Lower);
1965 const SCEV *UpperValue = SE.getMulExpr(Coeff, Upper);
1966 return BanerjeeInterval(SE.getSMinExpr(LowerValue, UpperValue),
1967 SE.getSMaxExpr(LowerValue, UpperValue));
1968}
1969
1970/// Compute the range of Coeff * X for 0 <= X <= Upper. A null Upper denotes
1971/// an unbounded nonnegative X.
1972static BanerjeeInterval variableInterval(const SCEV *Coeff, const SCEV *Upper,
1973 ScalarEvolution &SE) {
1974 const SCEV *Zero = SE.getZero(Coeff->getType());
1975 if (Coeff->isZero())
1976 return constantInterval(Zero);
1977 if (!Upper) {
1978 if (SE.isKnownNegative(Coeff))
1979 return BanerjeeInterval(nullptr, Zero);
1980 if (SE.isKnownNonNegative(Coeff))
1981 return BanerjeeInterval(Zero, nullptr);
1982 return BanerjeeInterval(nullptr, nullptr);
1983 }
1984 return signedRangeInterval(Coeff, Zero, Upper, SE);
1985}
1986
1987/// Compute any finite one-sided bound on
1988///
1989/// A * SrcIndex - B * DstIndex
1990///
1991/// for a strict direction when no upper bound is known for the nonnegative
1992/// normalized indices.
1993///
1994/// For SrcIndex < DstIndex, write DstIndex = SrcIndex + D, where D >= 1:
1995///
1996/// A * SrcIndex - B * DstIndex
1997/// = (A - B) * SrcIndex + (-B) * D.
1998///
1999/// If A - B >= 0 and B <= 0, both terms increase with their nonnegative
2000/// variables (SrcIndex and D), so the expression is bounded below by -B.
2001/// If A - B <= 0 and B >= 0, it is bounded above by -B.
2002///
2003/// For SrcIndex > DstIndex, write SrcIndex = DstIndex + D:
2004///
2005/// A * SrcIndex - B * DstIndex
2006/// = (A - B) * DstIndex + A * D.
2007///
2008/// If A - B >= 0 and A >= 0, the expression is bounded below by A.
2009/// If A - B <= 0 and A <= 0, it is bounded above by A.
2011 const SCEV *ACoeff, const SCEV *BCoeff, unsigned char Direction,
2012 ScalarEvolution &SE) {
2013 const SCEV *DeltaCoeff = SE.getMinusSCEV(ACoeff, BCoeff);
2014
2015 switch (Direction) {
2017 const SCEV *Boundary = SE.getNegativeSCEV(BCoeff);
2018 const SCEV *Lower = nullptr;
2019 const SCEV *Upper = nullptr;
2020 if (SE.isKnownNonNegative(DeltaCoeff) && SE.isKnownNonPositive(BCoeff))
2021 Lower = Boundary;
2022 if (SE.isKnownNonPositive(DeltaCoeff) && SE.isKnownNonNegative(BCoeff))
2023 Upper = Boundary;
2024 return BanerjeeInterval(Lower, Upper);
2025 }
2027 const SCEV *Lower = nullptr;
2028 const SCEV *Upper = nullptr;
2029 if (SE.isKnownNonNegative(ACoeff) && SE.isKnownNonNegative(DeltaCoeff))
2030 Lower = ACoeff;
2031 if (SE.isKnownNonPositive(ACoeff) && SE.isKnownNonPositive(DeltaCoeff))
2032 Upper = ACoeff;
2033 return BanerjeeInterval(Lower, Upper);
2034 }
2035 default:
2036 llvm_unreachable("unexpected direction");
2037 }
2038}
2039
2040/// Return the smallest closed interval containing Values.
2042 ScalarEvolution &SE) {
2043 assert(!Values.empty() && "expected at least one value");
2044 const SCEV *Lower = Values.front();
2045 const SCEV *Upper = Values.front();
2046 for (const SCEV *Value : Values.drop_front()) {
2049 }
2050 return BanerjeeInterval(Lower, Upper);
2051}
2052
2053/// Evaluate one loop level's contribution A * SrcIndex - B * DstIndex to the
2054/// complete source-minus-destination subscript difference.
2055static const SCEV *
2056evaluateSubscriptDifference(const SCEV *A, const SCEV *SrcIndex, const SCEV *B,
2057 const SCEV *DstIndex, ScalarEvolution &SE) {
2058 return SE.getMinusSCEV(SE.getMulExpr(A, SrcIndex),
2059 SE.getMulExpr(B, DstIndex));
2060}
2061
2062/// Return the widest type used by a subscript or by an exact backedge-taken
2063/// count of one of its recurrences.
2064static Type *getBanerjeeBaseType(const SCEV *Src, const SCEV *Dst,
2065 ScalarEvolution &SE) {
2066 Type *BaseType = SE.getWiderType(Src->getType(), Dst->getType());
2067 for (const SCEV *Subscript : {Src, Dst}) {
2068 while (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Subscript)) {
2069 const SCEV *MaxIterIndex = SE.getBackedgeTakenCount(AddRec->getLoop());
2070 if (!isa<SCEVCouldNotCompute>(MaxIterIndex))
2071 BaseType = SE.getWiderType(BaseType, MaxIterIndex->getType());
2072 Subscript = AddRec->getStart();
2073 }
2074 }
2075 return BaseType;
2076}
2077
2078/// banerjeeMIVtest -
2079/// Use Banerjee's Inequalities to test an MIV subscript pair.
2080/// (Wolfe calls this the Extreme Value Test; see Section 2.5.2 of
2081/// Optimizing Supercompilers for Supercomputers, Michael Wolfe.)
2082///
2083/// The original Wolfe formulae are algebraically simplified for normalized
2084/// loops (L_k=0, N_k=1); we now evaluate the subscript difference directly
2085/// at the vertices of the constraint polytope for each direction (e.g., (0,1),
2086/// (0,U), (U-1,U) for <). All operands are extended to a sufficiently wide
2087/// SCEV integer type before the arithmetic, so symbolic expressions remain
2088/// available to ScalarEvolution without wrapping intermediate results.
2089///
2090/// Loop bounds are backedge-taken counts (maximum normalized iteration
2091/// index). A single-iteration loop has bound 0, making < and > impossible.
2092/// Unknown interval endpoints are treated conservatively as infinities.
2093///
2094/// Return true if dependence disproved.
2095bool DependenceInfo::banerjeeMIVtest(const SCEV *Src, const SCEV *Dst,
2096 const SmallBitVector &Loops,
2097 FullDependence &Result) const {
2099 return false;
2100
2101 LLVM_DEBUG(dbgs() << "starting Banerjee\n");
2102 ++BanerjeeApplications;
2103
2104 Type *BaseType = getBanerjeeBaseType(Src, Dst, *SE);
2105 unsigned BaseBits = SE->getTypeSizeInBits(BaseType);
2106 // Let B be the maximum bit width among the source and destination
2107 // subscripts and the exact backedge-taken counts of the loops appearing
2108 // in their recurrences. Let L = MaxLevels. A coefficient C is a signed
2109 // B-bit value, so |C| <= 2^(B-1). A normalized iteration index I is a
2110 // nonnegative B-bit value, so I < 2^B. Therefore |C*I| < 2^(2B-1), and one
2111 // level's contribution |A*I-B*J| < 2^(2B). The accumulated
2112 // subscript-difference bound across L levels is less than
2113 // L*2^(2B) <= 2^(2B+L). One additional bit holds the sign, so 2B+L+1 bits
2114 // are sufficient for every intermediate Banerjee computation.
2115 unsigned WideBits = 2 * BaseBits + MaxLevels + 1;
2116 Type *WideType = IntegerType::get(F->getContext(), WideBits);
2117 const SCEV *Zero = SE->getZero(WideType);
2118
2119 CoefficientInfo EmptyCoeff{Zero, Zero, nullptr};
2120 SmallVector<CoefficientInfo, 4> CI(MaxLevels + 1, EmptyCoeff);
2121 assert(Loops.size() > MaxLevels && "loop bit vector is too small");
2122 assert(Result.Levels >= CommonLevels &&
2123 "direction vector is too small for common levels");
2124
2125 const SCEV *A0 = collectCoeffInfo(Src, true, WideType, CI);
2126 const SCEV *B0 = collectCoeffInfo(Dst, false, WideType, CI);
2127 const SCEV *Delta = SE->getMinusSCEV(B0, A0);
2128 LLVM_DEBUG(dbgs() << "\tDelta = " << *Delta << '\n');
2129
2130 SmallVector<BoundInfo, 4> Bound(MaxLevels + 1);
2131 for (unsigned K = 0; K <= MaxLevels; ++K) {
2132 Bound[K].Direction = Dependence::DVEntry::ALL;
2133 Bound[K].DirSet = Dependence::DVEntry::NONE;
2134 }
2135 for (unsigned K = 1; K <= MaxLevels; ++K) {
2136 findBoundsALL(CI, Bound, K);
2137 findBoundsLT(CI, Bound, K);
2138 findBoundsEQ(CI, Bound, K);
2139 findBoundsGT(CI, Bound, K);
2140 }
2141
2142 if (!testBounds(Dependence::DVEntry::ALL, 0, Bound, Delta)) {
2143 ++BanerjeeIndependence;
2144 return true;
2145 }
2146
2147 unsigned NewDeps = exploreDirections(1, Bound, Loops, Delta, Result);
2148 if (NewDeps == 0) {
2149 ++BanerjeeIndependence;
2150 return true;
2151 }
2152
2153 bool Improved = false;
2154 for (unsigned K = 1; K <= CommonLevels; ++K) {
2155 if (!Loops[K])
2156 continue;
2157 unsigned Old = Result.DV[K - 1].Direction;
2158 Result.DV[K - 1].Direction = Old & Bound[K].DirSet;
2159 Improved |= Old != Result.DV[K - 1].Direction;
2160 if (!Result.DV[K - 1].Direction) {
2161 ++BanerjeeIndependence;
2162 return true;
2163 }
2164 }
2165
2166 if (Improved)
2167 ++BanerjeeSuccesses;
2168 return false;
2169}
2170
2171/// Walks through the subscript and collects its coefficient at each loop
2172/// level. Each level has one maximum iteration index shared by the source and
2173/// destination coefficients. All collected values and the returned constant
2174/// term are extended to the widened analysis type before Banerjee arithmetic.
2175const SCEV *
2176DependenceInfo::collectCoeffInfo(const SCEV *Subscript, bool SrcFlag,
2177 Type *WideType,
2179 SmallBitVector SeenLevels(MaxLevels + 1);
2180 while (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Subscript)) {
2181 unsigned K =
2182 SrcFlag ? mapSrcLoop(AddRec->getLoop()) : mapDstLoop(AddRec->getLoop());
2183 assert(K > 0 && K <= MaxLevels && "invalid mapped loop level");
2184 assert(!SeenLevels[K] && "duplicate recurrence for loop level");
2185 SeenLevels.set(K);
2186
2187 const SCEV *Step = AddRec->getStepRecurrence(*SE);
2188 const SCEV *&Coeff = SrcFlag ? CI[K].SrcCoeff : CI[K].DstCoeff;
2189 Coeff = SE->getNoopOrSignExtend(Step, WideType);
2190
2191 const SCEV *MaxIterIndex = SE->getBackedgeTakenCount(AddRec->getLoop());
2192 if (!isa<SCEVCouldNotCompute>(MaxIterIndex)) {
2193 // A backedge-taken count is semantically an unsigned, nonnegative
2194 // iteration index. When its signed nonnegativity is also known, sign
2195 // extension preserves more symbolic relationships. Otherwise use zero
2196 // extension; this fallback does not assume that the value is negative.
2197 CI[K].MaxIterIndex =
2198 SE->isKnownNonNegative(MaxIterIndex)
2199 ? SE->getNoopOrSignExtend(MaxIterIndex, WideType)
2200 : SE->getNoopOrZeroExtend(MaxIterIndex, WideType);
2201 }
2202
2203 Subscript = AddRec->getStart();
2204 }
2205 return SE->getNoopOrSignExtend(Subscript, WideType);
2206}
2207
2208/// Looks through all the bounds info and computes the selected lower bound.
2209const SCEV *DependenceInfo::getLowerBound(ArrayRef<BoundInfo> Bound) const {
2210 const SCEV *Sum = Bound[1].Lower[Bound[1].Direction];
2211 for (unsigned K = 2; Sum && K <= MaxLevels; ++K) {
2212 if (!Bound[K].Lower[Bound[K].Direction])
2213 return nullptr;
2214 Sum = SE->getAddExpr(Sum, Bound[K].Lower[Bound[K].Direction]);
2215 }
2216 return Sum;
2217}
2218
2219/// Looks through all the bounds info and computes the selected upper bound.
2220const SCEV *DependenceInfo::getUpperBound(ArrayRef<BoundInfo> Bound) const {
2221 const SCEV *Sum = Bound[1].Upper[Bound[1].Direction];
2222 for (unsigned K = 2; Sum && K <= MaxLevels; ++K) {
2223 if (!Bound[K].Upper[Bound[K].Direction])
2224 return nullptr;
2225 Sum = SE->getAddExpr(Sum, Bound[K].Upper[Bound[K].Direction]);
2226 }
2227 return Sum;
2228}
2229
2230/// Returns false when the selected bounds are proven infeasible. Returns true
2231/// when they may be feasible or ScalarEvolution cannot decide.
2232bool DependenceInfo::testBounds(unsigned char DirKind, unsigned Level,
2234 const SCEV *Delta) const {
2235 Bound[Level].Direction = DirKind;
2236 for (unsigned K = 1; K <= MaxLevels; ++K) {
2237 unsigned char Direction = Bound[K].Direction;
2238 BanerjeeInterval Interval(Bound[K].Lower[Direction],
2239 Bound[K].Upper[Direction]);
2240 if (Interval.isEmpty(*SE))
2241 return false;
2242 }
2243 if (const SCEV *Lower = getLowerBound(Bound))
2244 if (SE->isKnownPredicate(CmpInst::ICMP_SGT, Lower, Delta))
2245 return false;
2246 if (const SCEV *Upper = getUpperBound(Bound))
2247 if (SE->isKnownPredicate(CmpInst::ICMP_SGT, Delta, Upper))
2248 return false;
2249 return true;
2250}
2251
2252/// Hierarchically expands the direction-vector search space.
2253unsigned DependenceInfo::exploreDirections(unsigned Level,
2255 const SmallBitVector &Loops,
2256 const SCEV *Delta,
2257 const FullDependence &Result) const {
2258 if (CommonLevels > Opts.da_miv_max_level_threshold) {
2259 LLVM_DEBUG(dbgs() << "Number of common levels exceeded the threshold. MIV "
2260 "direction exploration is terminated.\n");
2261 for (unsigned K = 1; K <= CommonLevels; ++K)
2262 if (Loops[K])
2263 Bound[K].DirSet = Dependence::DVEntry::ALL;
2264 return 1;
2265 }
2266
2267 if (Level > CommonLevels) {
2268 for (unsigned K = 1; K <= CommonLevels; ++K)
2269 if (Loops[K])
2270 Bound[K].DirSet |= Bound[K].Direction;
2271 return 1;
2272 }
2273
2274 if (!Loops[Level])
2275 return exploreDirections(Level + 1, Bound, Loops, Delta, Result);
2276
2277 unsigned NewDeps = 0;
2278 unsigned OldDirections = Result.DV[Level - 1].Direction;
2279 for (unsigned char Dir : {Dependence::DVEntry::LT, Dependence::DVEntry::EQ,
2281 if (!(OldDirections & Dir))
2282 continue;
2283 if (testBounds(Dir, Level, Bound, Delta))
2284 NewDeps += exploreDirections(Level + 1, Bound, Loops, Delta, Result);
2285 }
2286 Bound[Level].Direction = Dependence::DVEntry::ALL;
2287 return NewDeps;
2288}
2289
2290/// Computes the lower and upper bounds for level K using the * direction.
2291///
2292/// At this level the contribution to the subscript difference is
2293///
2294/// F_k(i, j) = A_k i - B_k j.
2295///
2296/// The * direction imposes no relation between i and j, so the feasible domain
2297/// is the rectangle [0, U_A] x [0, U_B]. The extrema of this affine expression
2298/// occur at its corners. Equivalently, when U_A = U_B = U, Wolfe's normalized
2299/// bounds are
2300///
2301/// LB^*_k = (A^-_k - B^+_k) U
2302/// UB^*_k = (A^+_k - B^-_k) U,
2303///
2304/// where X^+ = max(X, 0) and X^- = min(X, 0).
2305void DependenceInfo::findBoundsALL(ArrayRef<CoefficientInfo> CI,
2307 unsigned K) const {
2308 BanerjeeInterval SrcInterval =
2309 variableInterval(CI[K].SrcCoeff, CI[K].MaxIterIndex, *SE);
2310 BanerjeeInterval DstInterval = variableInterval(
2311 SE->getNegativeSCEV(CI[K].DstCoeff), CI[K].MaxIterIndex, *SE);
2312 BanerjeeInterval Interval = addIntervals(SrcInterval, DstInterval, *SE);
2313 Bound[K].Lower[Dependence::DVEntry::ALL] = Interval.Lower;
2314 Bound[K].Upper[Dependence::DVEntry::ALL] = Interval.Upper;
2315}
2316
2317/// Computes the lower and upper bounds for level K using the = direction.
2318///
2319/// Here i = j, so F_k(i, i) = (A_k - B_k)i over the common range
2320/// [0, min(U_A, U_B)]. The extrema therefore occur at the two endpoints.
2321/// When the common upper bound is U, Wolfe's normalized bounds are
2322///
2323/// LB^=_k = (A_k - B_k)^- U
2324/// UB^=_k = (A_k - B_k)^+ U.
2325void DependenceInfo::findBoundsEQ(ArrayRef<CoefficientInfo> CI,
2327 unsigned K) const {
2328 BanerjeeInterval Interval =
2329 variableInterval(SE->getMinusSCEV(CI[K].SrcCoeff, CI[K].DstCoeff),
2330 CI[K].MaxIterIndex, *SE);
2331 Bound[K].Lower[Dependence::DVEntry::EQ] = Interval.Lower;
2332 Bound[K].Upper[Dependence::DVEntry::EQ] = Interval.Upper;
2333}
2334
2335/// Computes the lower and upper bounds for level K using the < direction.
2336///
2337/// For a known common upper bound U, the feasible domain is
2338/// 0 <= i < j <= U. Its vertices are (0, 1), (0, U), and (U - 1, U), so
2339/// evaluating F_k at those points gives the exact extrema. Equivalently,
2340/// Wolfe's normalized bounds are
2341///
2342/// LB^<_k = (A^-_k - B_k)^- (U - 1) - B_k
2343/// UB^<_k = (A^+_k - B_k)^+ (U - 1) - B_k.
2344///
2345/// If U is zero the domain is empty. If no common upper bound is known, the
2346/// implementation computes any finite one-sided bound it can prove and leaves
2347/// the other side unbounded.
2348void DependenceInfo::findBoundsLT(ArrayRef<CoefficientInfo> CI,
2350 unsigned K) const {
2351 const SCEV *ACoeff = CI[K].SrcCoeff;
2352 const SCEV *BCoeff = CI[K].DstCoeff;
2353 const SCEV *MaxIterIndex = CI[K].MaxIterIndex;
2354
2356 ACoeff, BCoeff, Dependence::DVEntry::LT, *SE);
2357 if (MaxIterIndex && MaxIterIndex->isZero()) {
2358 Interval = emptyInterval(ACoeff->getType(), *SE);
2359 } else if (MaxIterIndex) {
2360 const SCEV *Zero = SE->getZero(ACoeff->getType());
2361 const SCEV *One = SE->getOne(ACoeff->getType());
2362 const SCEV *MaxMinusOne = SE->getMinusSCEV(MaxIterIndex, One);
2364 Values.push_back(
2365 evaluateSubscriptDifference(ACoeff, Zero, BCoeff, One, *SE));
2366 Values.push_back(
2367 evaluateSubscriptDifference(ACoeff, Zero, BCoeff, MaxIterIndex, *SE));
2368 Values.push_back(evaluateSubscriptDifference(ACoeff, MaxMinusOne, BCoeff,
2369 MaxIterIndex, *SE));
2370 Interval =
2372 }
2373 Bound[K].Lower[Dependence::DVEntry::LT] = Interval.Lower;
2374 Bound[K].Upper[Dependence::DVEntry::LT] = Interval.Upper;
2375}
2376
2377/// Computes the lower and upper bounds for level K using the > direction.
2378///
2379/// For a known common upper bound U, the feasible domain is
2380/// 0 <= j < i <= U. Its vertices are (1, 0), (U, 0), and (U, U - 1), so
2381/// evaluating F_k at those points gives the exact extrema. Equivalently,
2382/// Wolfe's normalized bounds are
2383///
2384/// LB^>_k = (A_k - B^+_k)^- (U - 1) + A_k
2385/// UB^>_k = (A_k - B^-_k)^+ (U - 1) + A_k.
2386///
2387/// If U is zero the domain is empty. If no common upper bound is known, the
2388/// implementation computes any finite one-sided bound it can prove and leaves
2389/// the other side unbounded.
2390void DependenceInfo::findBoundsGT(ArrayRef<CoefficientInfo> CI,
2392 unsigned K) const {
2393 const SCEV *ACoeff = CI[K].SrcCoeff;
2394 const SCEV *BCoeff = CI[K].DstCoeff;
2395 const SCEV *MaxIterIndex = CI[K].MaxIterIndex;
2396
2398 ACoeff, BCoeff, Dependence::DVEntry::GT, *SE);
2399 if (MaxIterIndex && MaxIterIndex->isZero()) {
2400 Interval = emptyInterval(ACoeff->getType(), *SE);
2401 } else if (MaxIterIndex) {
2402 const SCEV *Zero = SE->getZero(ACoeff->getType());
2403 const SCEV *One = SE->getOne(ACoeff->getType());
2404 const SCEV *MaxMinusOne = SE->getMinusSCEV(MaxIterIndex, One);
2406 Values.push_back(
2407 evaluateSubscriptDifference(ACoeff, One, BCoeff, Zero, *SE));
2408 Values.push_back(
2409 evaluateSubscriptDifference(ACoeff, MaxIterIndex, BCoeff, Zero, *SE));
2410 Values.push_back(evaluateSubscriptDifference(ACoeff, MaxIterIndex, BCoeff,
2411 MaxMinusOne, *SE));
2412 Interval =
2414 }
2415 Bound[K].Lower[Dependence::DVEntry::GT] = Interval.Lower;
2416 Bound[K].Upper[Dependence::DVEntry::GT] = Interval.Upper;
2417}
2418
2419/// Check if we can delinearize the subscripts. If the SCEVs representing the
2420/// source and destination array references are recurrences on a nested loop,
2421/// this function flattens the nested recurrences into separate recurrences
2422/// for each loop level.
2423bool DependenceInfo::tryDelinearize(Instruction *Src, Instruction *Dst,
2425 assert(isLoadOrStore(Src) && "instruction is not load or store");
2426 assert(isLoadOrStore(Dst) && "instruction is not load or store");
2427 Value *SrcPtr = getLoadStorePointerOperand(Src);
2428 Value *DstPtr = getLoadStorePointerOperand(Dst);
2429 Loop *SrcLoop = LI->getLoopFor(Src->getParent());
2430 Loop *DstLoop = LI->getLoopFor(Dst->getParent());
2431 const SCEV *SrcAccessFn = SE->getSCEVAtScope(SrcPtr, SrcLoop);
2432 const SCEV *DstAccessFn = SE->getSCEVAtScope(DstPtr, DstLoop);
2433 const SCEVUnknown *SrcBase =
2434 dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccessFn));
2435 const SCEVUnknown *DstBase =
2436 dyn_cast<SCEVUnknown>(SE->getPointerBase(DstAccessFn));
2437
2438 if (!SrcBase || !DstBase || SrcBase != DstBase)
2439 return false;
2440
2441 SmallVector<const SCEV *, 4> SrcSubscripts, DstSubscripts;
2442
2443 if (!tryDelinearizeFixedSize(Src, Dst, SrcAccessFn, DstAccessFn,
2444 SrcSubscripts, DstSubscripts) &&
2445 !tryDelinearizeParametricSize(Src, Dst, SrcAccessFn, DstAccessFn,
2446 SrcSubscripts, DstSubscripts))
2447 return false;
2448
2449 assert(isLoopInvariant(SrcBase, SrcLoop) &&
2450 isLoopInvariant(DstBase, DstLoop) &&
2451 "Expected SrcBase and DstBase to be loop invariant");
2452
2453 int Size = SrcSubscripts.size();
2454 LLVM_DEBUG({
2455 dbgs() << "\nSrcSubscripts: ";
2456 for (int I = 0; I < Size; I++)
2457 dbgs() << *SrcSubscripts[I];
2458 dbgs() << "\nDstSubscripts: ";
2459 for (int I = 0; I < Size; I++)
2460 dbgs() << *DstSubscripts[I];
2461 dbgs() << "\n";
2462 });
2463
2464 // The delinearization transforms a single-subscript MIV dependence test into
2465 // a multi-subscript SIV dependence test that is easier to compute. So we
2466 // resize Pair to contain as many pairs of subscripts as the delinearization
2467 // has found, and then initialize the pairs following the delinearization.
2468 Pair.resize(Size);
2469 for (int I = 0; I < Size; ++I) {
2470 Pair[I].Src = SrcSubscripts[I];
2471 Pair[I].Dst = DstSubscripts[I];
2472
2473 assert(Pair[I].Src->getType() == Pair[I].Dst->getType() &&
2474 "Unexpected different types for the subscripts");
2475 }
2476
2477 return true;
2478}
2479
2480/// Try to delinearize \p SrcAccessFn and \p DstAccessFn if the underlying
2481/// arrays accessed are fixed-size arrays. Return true if delinearization was
2482/// successful.
2483bool DependenceInfo::tryDelinearizeFixedSize(
2484 Instruction *Src, Instruction *Dst, const SCEV *SrcAccessFn,
2485 const SCEV *DstAccessFn, SmallVectorImpl<const SCEV *> &SrcSubscripts,
2486 SmallVectorImpl<const SCEV *> &DstSubscripts) {
2487 LLVM_DEBUG({
2488 const SCEVUnknown *SrcBase =
2489 dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccessFn));
2490 const SCEVUnknown *DstBase =
2491 dyn_cast<SCEVUnknown>(SE->getPointerBase(DstAccessFn));
2492 assert(SrcBase && DstBase && SrcBase == DstBase &&
2493 "expected src and dst scev unknowns to be equal");
2494 });
2495
2496 const SCEV *ElemSize = SE->getElementSize(Src);
2497 assert(ElemSize == SE->getElementSize(Dst) && "Different element sizes");
2498 SmallVector<const SCEV *, 4> SrcSizes, DstSizes;
2499 if (!delinearizeFixedSizeArray(*SE, SE->removePointerBase(SrcAccessFn),
2500 SrcSubscripts, SrcSizes, ElemSize) ||
2501 !delinearizeFixedSizeArray(*SE, SE->removePointerBase(DstAccessFn),
2502 DstSubscripts, DstSizes, ElemSize))
2503 return false;
2504
2505 // Check that the two size arrays are non-empty and equal in length and
2506 // value. SCEV expressions are uniqued, so we can compare pointers.
2507 if (SrcSizes.size() != DstSizes.size() ||
2508 !std::equal(SrcSizes.begin(), SrcSizes.end(), DstSizes.begin())) {
2509 SrcSubscripts.clear();
2510 DstSubscripts.clear();
2511 return false;
2512 }
2513
2514 assert(SrcSubscripts.size() == DstSubscripts.size() &&
2515 "Expected equal number of entries in the list of SrcSubscripts and "
2516 "DstSubscripts.");
2517
2518 // In general we cannot safely assume that the subscripts recovered from GEPs
2519 // are in the range of values defined for their corresponding array
2520 // dimensions. For example some C language usage/interpretation make it
2521 // impossible to verify this at compile-time. As such we can only delinearize
2522 // iff the subscripts are positive and are less than the range of the
2523 // dimension.
2524 if (Opts.da_delinearization_checks) {
2525 if (!validateDelinearizationResult(*SE, SrcSizes, SrcSubscripts) ||
2526 !validateDelinearizationResult(*SE, DstSizes, DstSubscripts)) {
2527 SrcSubscripts.clear();
2528 DstSubscripts.clear();
2529 return false;
2530 }
2531 }
2532 LLVM_DEBUG({
2533 dbgs() << "Delinearized subscripts of fixed-size array\n"
2534 << "SrcGEP:" << *getLoadStorePointerOperand(Src) << "\n"
2535 << "DstGEP:" << *getLoadStorePointerOperand(Dst) << "\n";
2536 });
2537 return true;
2538}
2539
2540bool DependenceInfo::tryDelinearizeParametricSize(
2541 Instruction *Src, Instruction *Dst, const SCEV *SrcAccessFn,
2542 const SCEV *DstAccessFn, SmallVectorImpl<const SCEV *> &SrcSubscripts,
2543 SmallVectorImpl<const SCEV *> &DstSubscripts) {
2544
2545 const SCEVUnknown *SrcBase =
2546 dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccessFn));
2547 const SCEVUnknown *DstBase =
2548 dyn_cast<SCEVUnknown>(SE->getPointerBase(DstAccessFn));
2549 assert(SrcBase && DstBase && SrcBase == DstBase &&
2550 "expected src and dst scev unknowns to be equal");
2551
2552 const SCEV *ElementSize = SE->getElementSize(Src);
2553 if (ElementSize != SE->getElementSize(Dst))
2554 return false;
2555
2556 const SCEV *SrcSCEV = SE->getMinusSCEV(SrcAccessFn, SrcBase);
2557 const SCEV *DstSCEV = SE->getMinusSCEV(DstAccessFn, DstBase);
2558
2559 const SCEVAddRecExpr *SrcAR = dyn_cast<SCEVAddRecExpr>(SrcSCEV);
2560 const SCEVAddRecExpr *DstAR = dyn_cast<SCEVAddRecExpr>(DstSCEV);
2561 if (!SrcAR || !DstAR || !SrcAR->isAffine() || !DstAR->isAffine())
2562 return false;
2563
2564 // First step: collect parametric terms in both array references.
2566 collectParametricTerms(*SE, SrcAR, Terms);
2567 collectParametricTerms(*SE, DstAR, Terms);
2568
2569 // Second step: find subscript sizes.
2571 findArrayDimensions(*SE, Terms, Sizes, ElementSize);
2572
2573 // Third step: compute the access functions for each subscript.
2574 computeAccessFunctions(*SE, SrcAR, SrcSubscripts, Sizes);
2575 computeAccessFunctions(*SE, DstAR, DstSubscripts, Sizes);
2576
2577 // Fail when there is only a subscript: that's a linearized access function.
2578 if (SrcSubscripts.size() < 2 || DstSubscripts.size() < 2 ||
2579 SrcSubscripts.size() != DstSubscripts.size())
2580 return false;
2581
2582 // Statically check that the array bounds are in-range. The first subscript we
2583 // don't have a size for and it cannot overflow into another subscript, so is
2584 // always safe. The others need to be 0 <= subscript[i] < bound, for both src
2585 // and dst.
2586 // FIXME: It may be better to record these sizes and add them as constraints
2587 // to the dependency checks.
2588 if (Opts.da_delinearization_checks)
2589 if (!validateDelinearizationResult(*SE, Sizes, SrcSubscripts) ||
2590 !validateDelinearizationResult(*SE, Sizes, DstSubscripts))
2591 return false;
2592
2593 return true;
2594}
2595
2596//===----------------------------------------------------------------------===//
2597
2598#ifndef NDEBUG
2599// For debugging purposes, dump a small bit vector to dbgs().
2601 dbgs() << "{";
2602 for (unsigned VI : BV.set_bits()) {
2603 dbgs() << VI;
2604 if (BV.find_next(VI) >= 0)
2605 dbgs() << ' ';
2606 }
2607 dbgs() << "}\n";
2608}
2609#endif
2610
2612 FunctionAnalysisManager::Invalidator &Inv) {
2613 // Check if the analysis itself has been invalidated.
2614 auto PAC = PA.getChecker<DependenceAnalysis>();
2615 if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Function>>())
2616 return true;
2617
2618 // Check transitive dependencies.
2619 return Inv.invalidate<AAManager>(F, PA) ||
2620 Inv.invalidate<ScalarEvolutionAnalysis>(F, PA) ||
2621 Inv.invalidate<LoopAnalysis>(F, PA);
2622}
2623
2624void DependenceInfo::updateLoopAliasScopes(const Loop *L) {
2625 if (!L || !AlreadyCheckedLoops.insert(L).second)
2626 return;
2627
2628 Function *DeclFn = F->getParent()
2629 ? F->getParent()->getFunction(Intrinsic::getName(
2630 Intrinsic::experimental_noalias_scope_decl))
2631 : nullptr;
2632 // No decls in this module. Parent loops cannot add any either.
2633 if (!DeclFn || DeclFn->use_empty())
2634 return;
2635
2636 for (BasicBlock *BB : L->blocks()) {
2637 // Subloop blocks belong to the inner loop. Scan them when that loop
2638 // is updated. The parent walk below picks up a decl between two loops.
2639 if (LI->getLoopFor(BB) != L)
2640 continue;
2641 for (const Instruction &I : *BB) {
2642 if (const auto *Decl = dyn_cast<NoAliasScopeDeclInst>(&I)) {
2643 for (Metadata *Op : Decl->getScopeList()->operands())
2644 LoopAliasScopes.insert(cast<MDNode>(Op));
2645 }
2646 }
2647 }
2648 updateLoopAliasScopes(L->getParentLoop());
2649}
2650
2651// depends -
2652// Returns NULL if there is no dependence.
2653// Otherwise, return a Dependence with as many details as possible.
2654// Corresponds to Section 3.1 in the paper
2655//
2656// Practical Dependence Testing
2657// Goff, Kennedy, Tseng
2658// PLDI 1991
2659//
2660std::unique_ptr<Dependence>
2662 bool UnderRuntimeAssumptions) {
2664 bool PossiblyLoopIndependent = true;
2665 if (Src == Dst)
2666 PossiblyLoopIndependent = false;
2667
2668 if (!(Src->mayReadOrWriteMemory() && Dst->mayReadOrWriteMemory()))
2669 // if both instructions don't reference memory, there's no dependence
2670 return nullptr;
2671
2672 if (!isLoadOrStore(Src) || !isLoadOrStore(Dst)) {
2673 // can only analyze simple loads and stores, i.e., no calls, invokes, etc.
2674 LLVM_DEBUG(dbgs() << "can only handle simple loads and stores\n");
2675 return std::make_unique<Dependence>(Src, Dst,
2676 SCEVUnionPredicate(Assume, *SE));
2677 }
2678
2679 const MemoryLocation &DstLoc = MemoryLocation::get(Dst);
2680 const MemoryLocation &SrcLoc = MemoryLocation::get(Src);
2681
2682 updateLoopAliasScopes(LI->getLoopFor(Src->getParent()));
2683 updateLoopAliasScopes(LI->getLoopFor(Dst->getParent()));
2684
2685 switch (underlyingObjectsAlias(AA, F->getDataLayout(), DstLoc, SrcLoc,
2686 LoopAliasScopes)) {
2689 // cannot analyse objects if we don't understand their aliasing.
2690 LLVM_DEBUG(dbgs() << "can't analyze may or partial alias\n");
2691 return std::make_unique<Dependence>(Src, Dst,
2692 SCEVUnionPredicate(Assume, *SE));
2694 // If the objects noalias, they are distinct, accesses are independent.
2695 LLVM_DEBUG(dbgs() << "no alias\n");
2696 return nullptr;
2698 break; // The underlying objects alias; test accesses for dependence.
2699 }
2700
2701 if (DstLoc.Size != SrcLoc.Size || !DstLoc.Size.isPrecise() ||
2702 !SrcLoc.Size.isPrecise()) {
2703 // The dependence test gets confused if the size of the memory accesses
2704 // differ.
2705 LLVM_DEBUG(dbgs() << "can't analyze must alias with different sizes\n");
2706 return std::make_unique<Dependence>(Src, Dst,
2707 SCEVUnionPredicate(Assume, *SE));
2708 }
2709
2710 Value *SrcPtr = getLoadStorePointerOperand(Src);
2711 Value *DstPtr = getLoadStorePointerOperand(Dst);
2712 const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
2713 const SCEV *DstSCEV = SE->getSCEV(DstPtr);
2714 LLVM_DEBUG(dbgs() << " SrcSCEV = " << *SrcSCEV << "\n");
2715 LLVM_DEBUG(dbgs() << " DstSCEV = " << *DstSCEV << "\n");
2716 const SCEV *SrcBase = SE->getPointerBase(SrcSCEV);
2717 const SCEV *DstBase = SE->getPointerBase(DstSCEV);
2718 if (SrcBase != DstBase) {
2719 // If two pointers have different bases, trying to analyze indexes won't
2720 // work; we can't compare them to each other. This can happen, for example,
2721 // if one is produced by an LCSSA PHI node.
2722 //
2723 // We check this upfront so we don't crash in cases where getMinusSCEV()
2724 // returns a SCEVCouldNotCompute.
2725 LLVM_DEBUG(dbgs() << "can't analyze SCEV with different pointer base\n");
2726 return std::make_unique<Dependence>(Src, Dst,
2727 SCEVUnionPredicate(Assume, *SE));
2728 }
2729
2730 // Even if the base pointers are the same, they may not be loop-invariant. It
2731 // could lead to incorrect results, as we're analyzing loop-carried
2732 // dependencies. Src and Dst can be in different loops, so we need to check
2733 // the base pointer is invariant in both loops.
2734 Loop *SrcLoop = LI->getLoopFor(Src->getParent());
2735 Loop *DstLoop = LI->getLoopFor(Dst->getParent());
2736 if (!isLoopInvariant(SrcBase, SrcLoop) ||
2737 !isLoopInvariant(DstBase, DstLoop)) {
2738 LLVM_DEBUG(dbgs() << "The base pointer is not loop invariant.\n");
2739 return std::make_unique<Dependence>(Src, Dst,
2740 SCEVUnionPredicate(Assume, *SE));
2741 }
2742
2743 uint64_t EltSize = SrcLoc.Size.toRaw();
2744 const SCEV *SrcEv = SE->getMinusSCEV(SrcSCEV, SrcBase);
2745 const SCEV *DstEv = SE->getMinusSCEV(DstSCEV, DstBase);
2746
2747 // Check that memory access offsets are multiples of element sizes.
2748 // Add to Assume if only runtime assumptions are allowed.
2749 if (!SE->isKnownMultipleOf(SrcEv, EltSize,
2750 UnderRuntimeAssumptions ? &Assume : nullptr) ||
2751 !SE->isKnownMultipleOf(DstEv, EltSize,
2752 UnderRuntimeAssumptions ? &Assume : nullptr)) {
2753 LLVM_DEBUG(dbgs() << "can't analyze SCEV with different offsets\n");
2754 return std::make_unique<Dependence>(Src, Dst,
2755 SCEVUnionPredicate(Assume, *SE));
2756 }
2757
2758 unsigned Pairs = 1;
2759 SmallVector<Subscript, 2> Pair(Pairs);
2760 Pair[0].Src = SrcEv;
2761 Pair[0].Dst = DstEv;
2762 if (Opts.da_delinearize) {
2763 if (tryDelinearize(Src, Dst, Pair)) {
2764 LLVM_DEBUG(dbgs() << " delinearized\n");
2765 Pairs = Pair.size();
2766 }
2767 }
2768
2769 // Establish loop nesting levels considering SameSD loops as common
2770 establishNestingLevels(Src, Dst);
2771
2772 LLVM_DEBUG(dbgs() << " common nesting levels = " << CommonLevels << "\n");
2773 LLVM_DEBUG(dbgs() << " maximum nesting levels = " << MaxLevels << "\n");
2774 LLVM_DEBUG(dbgs() << " SameSD nesting levels = " << SameSDLevels << "\n");
2775
2776 // Modify common levels to consider the SameSD levels in the tests
2777 CommonLevels += SameSDLevels;
2778 MaxLevels -= SameSDLevels;
2779 if (SameSDLevels > 0) {
2780 // Not all tests are handled yet over SameSD loops
2781 // Revoke if there are any tests other than ZIV, SIV or RDIV
2782 for (unsigned P = 0; P < Pairs; ++P) {
2784 Subscript::ClassificationKind TestClass =
2785 classifyPair(Pair[P].Src, SrcLoop, Pair[P].Dst, DstLoop, Loops);
2786
2787 if (TestClass != Subscript::ZIV && TestClass != Subscript::SIV &&
2788 TestClass != Subscript::RDIV) {
2789 // Revert the levels to not consider the SameSD levels
2790 CommonLevels -= SameSDLevels;
2791 MaxLevels += SameSDLevels;
2792 SameSDLevels = 0;
2793 break;
2794 }
2795 }
2796 }
2797
2798 if (SameSDLevels > 0)
2799 SameSDLoopsCount++;
2800
2801 FullDependence Result(Src, Dst, SCEVUnionPredicate(Assume, *SE),
2802 PossiblyLoopIndependent, CommonLevels);
2803 ++TotalArrayPairs;
2804
2805 for (unsigned P = 0; P < Pairs; ++P) {
2806 assert(Pair[P].Src->getType()->isIntegerTy() && "Src must be an integer");
2807 assert(Pair[P].Dst->getType()->isIntegerTy() && "Dst must be an integer");
2808 Pair[P].Loops.resize(MaxLevels + 1);
2809 Pair[P].Classification =
2810 classifyPair(Pair[P].Src, SrcLoop, Pair[P].Dst, DstLoop, Pair[P].Loops);
2811 LLVM_DEBUG(dbgs() << " subscript " << P << "\n");
2812 LLVM_DEBUG(dbgs() << "\tsrc = " << *Pair[P].Src << "\n");
2813 LLVM_DEBUG(dbgs() << "\tdst = " << *Pair[P].Dst << "\n");
2814 LLVM_DEBUG(dbgs() << "\tclass = " << Pair[P].Classification << "\n");
2815 LLVM_DEBUG(dbgs() << "\tloops = ");
2817 }
2818
2819 // Test each subscript individually
2820 for (unsigned SI = 0; SI < Pairs; ++SI) {
2821 LLVM_DEBUG(dbgs() << "testing subscript " << SI);
2822
2823 // Attempt signed range test first.
2824 ConstantRange SrcRange = SE->getSignedRange(Pair[SI].Src);
2825 ConstantRange DstRange = SE->getSignedRange(Pair[SI].Dst);
2826 if (SrcRange.intersectWith(DstRange).isEmptySet())
2827 return nullptr;
2828
2829 switch (Pair[SI].Classification) {
2830 case Subscript::NonLinear:
2831 // ignore these, but collect loops for later
2832 ++NonlinearSubscriptPairs;
2833 collectCommonLoops(Pair[SI].Src, SrcLoop, Pair[SI].Loops);
2834 collectCommonLoops(Pair[SI].Dst, DstLoop, Pair[SI].Loops);
2835 break;
2836 case Subscript::ZIV:
2837 LLVM_DEBUG(dbgs() << ", ZIV\n");
2838 if (testZIV(Pair[SI].Src, Pair[SI].Dst, Result))
2839 return nullptr;
2840 break;
2841 case Subscript::SIV: {
2842 LLVM_DEBUG(dbgs() << ", SIV\n");
2843 unsigned Level;
2844 if (testSIV(Pair[SI].Src, Pair[SI].Dst, Level, Result,
2845 UnderRuntimeAssumptions))
2846 return nullptr;
2847 break;
2848 }
2849 case Subscript::RDIV:
2850 LLVM_DEBUG(dbgs() << ", RDIV\n");
2851 if (testRDIV(Pair[SI].Src, Pair[SI].Dst, Result))
2852 return nullptr;
2853 break;
2854 case Subscript::MIV:
2855 LLVM_DEBUG(dbgs() << ", MIV\n");
2856 if (testMIV(Pair[SI].Src, Pair[SI].Dst, Pair[SI].Loops, Result))
2857 return nullptr;
2858 break;
2859 }
2860 }
2861
2862 // Make sure the Scalar flags are set correctly.
2863 SmallBitVector CompleteLoops(MaxLevels + 1);
2864 for (unsigned SI = 0; SI < Pairs; ++SI)
2865 CompleteLoops |= Pair[SI].Loops;
2866 for (unsigned II = 1; II <= CommonLevels; ++II)
2867 if (CompleteLoops[II])
2868 Result.DV[II - 1].Scalar = false;
2869
2870 // Set the distance to zero if the direction is EQ.
2871 // TODO: Ideally, the distance should be set to 0 immediately simultaneously
2872 // with the corresponding direction being set to EQ.
2873 for (unsigned II = 1; II <= Result.getLevels(); ++II) {
2874 if (Result.getDirection(II) == Dependence::DVEntry::EQ) {
2875 if (Result.DV[II - 1].Distance == nullptr)
2876 Result.DV[II - 1].Distance = SE->getZero(SrcSCEV->getType());
2877 else
2878 assert(Result.DV[II - 1].Distance->isZero() &&
2879 "Inconsistency between distance and direction");
2880 }
2881
2882#ifndef NDEBUG
2883 // Check that the converse (i.e., if the distance is zero, then the
2884 // direction is EQ) holds.
2885 const SCEV *Distance = Result.getDistance(II);
2886 if (Distance && Distance->isZero())
2887 assert(Result.getDirection(II) == Dependence::DVEntry::EQ &&
2888 "Distance is zero, but direction is not EQ");
2889#endif
2890 }
2891
2892 if (SameSDLevels > 0) {
2893 // Extracting SameSD levels from the common levels
2894 // Reverting CommonLevels and MaxLevels to their original values
2895 assert(CommonLevels >= SameSDLevels);
2896 CommonLevels -= SameSDLevels;
2897 MaxLevels += SameSDLevels;
2898 std::unique_ptr<FullDependence::DVEntry[]> DV, DVSameSD;
2899 DV = std::make_unique<FullDependence::DVEntry[]>(CommonLevels);
2900 DVSameSD = std::make_unique<FullDependence::DVEntry[]>(SameSDLevels);
2901 for (unsigned Level = 0; Level < CommonLevels; ++Level)
2902 DV[Level] = Result.DV[Level];
2903 for (unsigned Level = 0; Level < SameSDLevels; ++Level)
2904 DVSameSD[Level] = Result.DV[CommonLevels + Level];
2905 Result.DV = std::move(DV);
2906 Result.DVSameSD = std::move(DVSameSD);
2907 Result.Levels = CommonLevels;
2908 Result.SameSDLevels = SameSDLevels;
2909 }
2910
2911 if (PossiblyLoopIndependent) {
2912 // Make sure the LoopIndependent flag is set correctly.
2913 // All directions must include equal, otherwise no
2914 // loop-independent dependence is possible.
2915 for (unsigned II = 1; II <= CommonLevels; ++II) {
2916 if (!(Result.getDirection(II) & Dependence::DVEntry::EQ)) {
2917 Result.LoopIndependent = false;
2918 break;
2919 }
2920 }
2921 } else {
2922 // On the other hand, if all directions are equal and there's no
2923 // loop-independent dependence possible, then no dependence exists.
2924 // However, if there are runtime assumptions, we must return the result.
2925 bool AllEqual = true;
2926 for (unsigned II = 1; II <= CommonLevels; ++II) {
2927 if (Result.getDirection(II) != Dependence::DVEntry::EQ) {
2928 AllEqual = false;
2929 break;
2930 }
2931 }
2932 if (AllEqual && Result.Assumptions.getPredicates().empty())
2933 return nullptr;
2934 }
2935
2936 return std::make_unique<FullDependence>(std::move(Result));
2937}
SDValue Pred
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
uint64_t uint64_t
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
bpf unwind BPF Unwind Lower
#define X(NUM, ENUM, NAME)
Definition ELF.h:665
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
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")
static bool isLoadOrStore(const Instruction *I)
static std::optional< bool > findGCD(unsigned Bits, const APInt &AM, const APInt &BM, const APInt &Delta, APInt &G, APInt &X, APInt &Y)
static OverflowSafeSignedAPInt floorOfQuotient(const OverflowSafeSignedAPInt &OA, const OverflowSafeSignedAPInt &OB)
static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA, ScalarEvolution &SE, LoopInfo &LI, bool NormalizeResults)
static OverflowSafeSignedAPInt ceilingOfQuotient(const OverflowSafeSignedAPInt &OA, const OverflowSafeSignedAPInt &OB)
static void dumpSmallBitVector(SmallBitVector &BV)
static BanerjeeInterval emptyInterval(Type *Ty, ScalarEvolution &SE)
Return the canonical empty interval [1, 0].
static std::pair< OverflowSafeSignedAPInt, OverflowSafeSignedAPInt > inferDomainOfAffine(OverflowSafeSignedAPInt A, OverflowSafeSignedAPInt B, OverflowSafeSignedAPInt UB)
Given an affine expression of the form A*k + B, where k is an arbitrary integer, infer the possible r...
static MDNode * adjustAliasScopeList(MDNode *ScopeList, const SmallPtrSetImpl< const MDNode * > &LoopAliasScopes)
Drop alias scopes that are only valid within a single loop iteration.
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, const SmallPtrSetImpl< const MDNode * > &LoopAliasScopes)
static BanerjeeInterval constantInterval(const SCEV *C)
Return the singleton interval containing C.
static Type * getBanerjeeBaseType(const SCEV *Src, const SCEV *Dst, ScalarEvolution &SE)
Return the widest type used by a subscript or by an exact backedge-taken count of one of its recurren...
static BanerjeeInterval variableInterval(const SCEV *Coeff, const SCEV *Upper, ScalarEvolution &SE)
Compute the range of Coeff * X for 0 <= X <= Upper.
static std::optional< APInt > getConstantCoefficient(const SCEV *Expr)
Given a SCEVMulExpr, returns its first operand if its first operand is a constant and the product doe...
static BanerjeeInterval strictDirectionIntervalWithUnknownUpperBound(const SCEV *ACoeff, const SCEV *BCoeff, unsigned char Direction, ScalarEvolution &SE)
Compute any finite one-sided bound on.
static const SCEV * evaluateSubscriptDifference(const SCEV *A, const SCEV *SrcIndex, const SCEV *B, const SCEV *DstIndex, ScalarEvolution &SE)
Evaluate one loop level's contribution A * SrcIndex - B * DstIndex to the complete source-minus-desti...
static bool isRemainderZero(const SCEVConstant *Dividend, const SCEVConstant *Divisor)
static BanerjeeInterval signedRangeInterval(const SCEV *Coeff, const SCEV *Lower, const SCEV *Upper, ScalarEvolution &SE)
Compute the range of Coeff * X for Lower <=s X <=s Upper.
static BanerjeeInterval intervalFromValues(ArrayRef< const SCEV * > Values, ScalarEvolution &SE)
Return the smallest closed interval containing Values.
static bool isDependenceTestEnabled(const AnalysisOptions &Opts, DependenceTestType Test)
Returns true iff Test is enabled.
static BanerjeeInterval addIntervals(const BanerjeeInterval &A, const BanerjeeInterval &B, ScalarEvolution &SE)
Add two intervals.
static BanerjeeInterval intersectIntervals(const BanerjeeInterval &A, const BanerjeeInterval &B, ScalarEvolution &SE)
Intersect two intervals.
static MemoryLocation adjustLoc(MemoryLocation Loc, const SmallPtrSetImpl< const MDNode * > &LoopAliasScopes)
Hexagon Hardware Loops
Module.h This file contains the declarations for the Module class.
Loop::LoopBounds::Direction Direction
Definition LoopInfo.cpp:249
#define F(x, y, z)
Definition MD5.cpp:54
#define I(x, y, z)
Definition MD5.cpp:57
#define G(x, y, z)
Definition MD5.cpp:55
std::pair< uint64_t, uint64_t > Interval
#define T
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
BaseType
A given derived pointer can have multiple base pointers through phi/selects.
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:119
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
Value * RHS
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
bool isMinSignedValue() const
Determine if this is the smallest signed value.
Definition APInt.h:419
static LLVM_ABI void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
Definition APInt.cpp:1928
APInt abs() const
Get the absolute value.
Definition APInt.h:1815
bool sgt(const APInt &RHS) const
Signed greater than comparison.
Definition APInt.h:1205
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition APInt.h:1508
LLVM_ABI APInt sdiv(const APInt &RHS) const
Signed division function for APInt.
Definition APInt.cpp:1673
LLVM_ABI APInt srem(const APInt &RHS) const
Function for signed remainder operation.
Definition APInt.cpp:1774
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
Definition APInt.h:330
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition APInt.h:1134
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
Definition APInt.h:196
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()
Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:40
LLVM Basic Block Representation.
Definition BasicBlock.h:62
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)
@ ICMP_SGT
signed greater than
Definition InstrTypes.h:767
@ ICMP_NE
not equal
Definition InstrTypes.h:762
This class represents a range of values.
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
bool isSingleElement() const
Return true if this set contains exactly one member.
LLVM_ABI ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
This is an important base class in LLVM.
Definition Constant.h:44
A parsed version of the target data layout string in and methods for querying it.
Definition DataLayout.h:64
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 DependenceInfo(Function *F, AAResults *AA, ScalarEvolution *SE, LoopInfo *LI)
LLVM_ABI std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool UnderRuntimeAssumptions=false)
depends - Tests for a dependence between the Src and Dst instructions.
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 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.
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 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.
void negate(ScalarEvolution &SE) override
Negate the dependence by swapping the source and destination, and reversing the direction and distanc...
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 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:312
FunctionPass(char &pid)
Definition Pass.h:314
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition Type.cpp:333
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:598
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:623
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
Metadata node.
Definition Metadata.h:1081
ArrayRef< MDOperand > operands() const
Definition Metadata.h:1435
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.
Root of the metadata hierarchy.
Definition Metadata.h:64
A Module instance is used to store all the information related to an LLVM module.
Definition Module.h:68
Represent a mutable reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:294
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:276
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.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
SCEVUse getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
This class represents a constant integer value.
const APInt & getAPInt() const
This class represents a composition of other SCEV predicates, and is the class that most clients will...
This class represents an analyzed expression in the program.
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.
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 bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
LLVM_ABI Type * getWiderType(Type *Ty1, Type *Ty2) const
LLVM_ABI bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
LLVM_ABI bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
LLVM_ABI const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
LLVM_ABI const SCEV * getSMinExpr(SCEVUse LHS, SCEVUse RHS)
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
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(SCEVUse LHS, SCEVUse RHS, SCEVFlags Flags=SCEV::FlagNone, unsigned Depth=0)
Return LHS-RHS.
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
LLVM_ABI SCEVUse getAddExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlagsPair Flags={}, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
LLVM_ABI SCEVUse getMulExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlagsPair Flags={}, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
LLVM_ABI bool isKnownPredicate(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI const SCEV * getSMaxExpr(SCEVUse LHS, SCEVUse RHS)
LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEVFlags Flags=SCEV::FlagNone)
Return the SCEV object corresponding to -V.
This is a 'bitvector' (really, a variable-sized bit array), optimized for the case when the array is ...
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.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void resize(size_type N)
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:46
LLVM Value Representation.
Definition Value.h:75
LLVM_ABI Value(Type *Ty, unsigned scid)
Definition Value.cpp:49
bool use_empty() const
Definition Value.h:348
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Abstract Attribute helper functions.
Definition Attributor.h:166
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition APInt.h:2274
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
Definition APInt.h:2279
LLVM_ABI APInt GreatestCommonDivisor(APInt A, APInt B, bool IsSigned=false)
Compute GCD of two APInt values.
Definition APInt.cpp:826
constexpr bool operator!(E Val)
@ BasicBlock
Various leaf nodes.
Definition ISDOpcodes.h:83
LLVM_ABI StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
@ TB
TB - TwoByte - Set if this instruction has a two byte opcode, which starts with a 0x0F byte before th...
This is an optimization pass for GlobalISel generic memory operations.
InstIterator< SymbolTableList< BasicBlock >, Function::iterator, BasicBlock::iterator, Instruction > inst_iterator
LLVM_ABI void collectParametricTerms(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Terms)
Collect parametric terms occurring in step expressions (first step of delinearization).
LLVM_ABI 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...
RelativeUniformCounterPtr Values
Definition InstrProf.h:91
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
APInt operator*(APInt a, uint64_t RHS)
Definition APInt.h:2261
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)
LLVM_ABI bool validateDelinearizationResult(ScalarEvolution &SE, ArrayRef< const SCEV * > Sizes, ArrayRef< const SCEV * > Subscripts)
Check that each subscript in Subscripts is within the corresponding size in Sizes.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
Definition InstrProf.h:143
const AnalysisOptions & getAnalysisOptions(const LLVMContext &C)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1762
LLVM_ABI 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 bool delinearizeFixedSizeArray(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< const SCEV * > &Sizes, const SCEV *ElementSize)
Split this SCEVAddRecExpr into two vectors of SCEVs representing the subscripts and sizes of an acces...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth, bool MustPreserveProvenance=false)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
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)
DWARFExpression::Operation Op
constexpr unsigned BitWidth
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
APInt operator-(APInt)
Definition APInt.h:2214
APInt operator+(APInt a, const APInt &b)
Definition APInt.h:2219
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
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.
Implement std::hash so that hash_code can be used in STL containers.
Definition BitVector.h:879
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition BitVector.h:881
#define N
MDNode * Scope
The tag for alias scope specification (used with noalias).
Definition Metadata.h:797
MDNode * NoAlias
The tag specifying the noalias scope.
Definition Metadata.h:800
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...