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
47#include "llvm/Analysis/DependenceAnalysis.h"
48#include "AnalysisOptions.h"
49#include "llvm/ADT/Statistic.h"
50#include "llvm/Analysis/AliasAnalysis.h"
51#include "llvm/Analysis/Delinearization.h"
52#include "llvm/Analysis/LoopInfo.h"
53#include "llvm/Analysis/ScalarEvolution.h"
54#include "llvm/Analysis/ScalarEvolutionExpressions.h"
55#include "llvm/Analysis/ValueTracking.h"
56#include "llvm/IR/InstIterator.h"
57#include "llvm/IR/IntrinsicInst.h"
58#include "llvm/IR/Module.h"
59#include "llvm/InitializePasses.h"
60#include "llvm/Support/Debug.h"
61#include "llvm/Support/ErrorHandling.h"
62#include "llvm/Support/raw_ostream.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
100DependenceInfo::DependenceInfo(Function *F, AAResults *AA, ScalarEvolution *SE,
101 LoopInfo *LI)
102 : Opts(getAnalysisOptions(F: *F)), AA(AA), SE(SE), LI(LI), F(F) {}
103
104DependenceAnalysis::Result
105DependenceAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
106 auto &AA = FAM.getResult<AAManager>(IR&: F);
107 auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(IR&: F);
108 auto &LI = FAM.getResult<LoopAnalysis>(IR&: F);
109 return DependenceInfo(&F, &AA, &SE, &LI);
110}
111
112AnalysisKey DependenceAnalysis::Key;
113
114INITIALIZE_PASS_BEGIN(DependenceAnalysisWrapperPass, "da",
115 "Dependence Analysis", true, true)
116INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
117INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
118INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
119INITIALIZE_PASS_END(DependenceAnalysisWrapperPass, "da", "Dependence Analysis",
120 true, true)
121
122char DependenceAnalysisWrapperPass::ID = 0;
123
124DependenceAnalysisWrapperPass::DependenceAnalysisWrapperPass()
125 : FunctionPass(ID) {}
126
127FunctionPass *llvm::createDependenceAnalysisWrapperPass() {
128 return new DependenceAnalysisWrapperPass();
129}
130
131bool DependenceAnalysisWrapperPass::runOnFunction(Function &F) {
132 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
133 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
134 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
135 info.reset(p: new DependenceInfo(&F, &AA, &SE, &LI));
136 return false;
137}
138
139DependenceInfo &DependenceAnalysisWrapperPass::getDI() const { return *info; }
140
141void DependenceAnalysisWrapperPass::releaseMemory() { info.reset(); }
142
143void DependenceAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
144 AU.setPreservesAll();
145 AU.addRequiredTransitive<AAResultsWrapperPass>();
146 AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
147 AU.addRequiredTransitive<LoopInfoWrapperPass>();
148}
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: *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(V: 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: *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(V: 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: *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.
247static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA,
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(Src: &*SrcI, Dst: &*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: &SE))
278 OS << "normalized - ";
279 D->dump(OS);
280 } else
281 OS << "none!\n";
282 }
283 }
284 }
285 }
286}
287
288void DependenceAnalysisWrapperPass::print(raw_ostream &OS,
289 const Module *) const {
290 dumpExampleDependence(
291 OS, DA: info.get(), SE&: getAnalysis<ScalarEvolutionWrapperPass>().getSE(),
292 LI&: getAnalysis<LoopInfoWrapperPass>().getLoopInfo(), NormalizeResults: false);
293}
294
295PreservedAnalyses
296DependenceAnalysisPrinterPass::run(Function &F, FunctionAnalysisManager &FAM) {
297 OS << "Printing analysis 'Dependence Analysis' for function '" << F.getName()
298 << "':\n";
299 dumpExampleDependence(OS, DA: &FAM.getResult<DependenceAnalysis>(IR&: F),
300 SE&: FAM.getResult<ScalarEvolutionAnalysis>(IR&: F),
301 LI&: FAM.getResult<LoopAnalysis>(IR&: F), NormalizeResults);
302 return PreservedAnalyses::all();
303}
304
305//===----------------------------------------------------------------------===//
306// Dependence methods
307
308// Returns true if this is an input dependence.
309bool Dependence::isInput() const {
310 return Src->mayReadFromMemory() && Dst->mayReadFromMemory();
311}
312
313// Returns true if this is an output dependence.
314bool Dependence::isOutput() const {
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
337FullDependence::FullDependence(Instruction *Source, Instruction *Destination,
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[]>(num: 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.
363bool FullDependence::isDirectionNegative() const {
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
376void FullDependence::negate(ScalarEvolution &SE) {
377 std::swap(a&: Src, b&: 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(V: DV[Level - 1].Distance);
391 }
392}
393
394bool FullDependence::normalize(ScalarEvolution *SE) {
395 if (!isDirectionNegative())
396 return false;
397
398 LLVM_DEBUG(dbgs() << "Before normalizing negative direction vectors:\n";
399 dump(dbgs()););
400 negate(SE&: *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.
440void Dependence::dump(raw_ostream &OS) const {
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, IsSameSD: true);
457 }
458 }
459 OS << "!\n";
460
461 SCEVUnionPredicate Assumptions = getRuntimeAssumptions();
462 if (!Assumptions.isAlwaysTrue()) {
463 OS << " Runtime Assumptions:\n";
464 Assumptions.print(OS, Depth: 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(Level: II))
480 OnSameSD = true;
481 const SCEV *Distance = getDistance(Level: II, SameSD: OnSameSD);
482 if (Distance)
483 OS << *Distance;
484 else if (isScalar(level: II, IsSameSD: OnSameSD))
485 OS << "S";
486 else {
487 unsigned Direction = getDirection(Level: II, SameSD: 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 *
509adjustAliasScopeList(MDNode *ScopeList,
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(Range: ScopeList->operands(), P: [&](Metadata *Scope) {
517 return LoopAliasScopes.contains(Ptr: cast<MDNode>(Val: 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
527adjustLoc(MemoryLocation Loc,
528 const SmallPtrSetImpl<const MDNode *> &LoopAliasScopes) {
529 MemoryLocation Adj = MemoryLocation::getBeforeOrAfter(Ptr: Loc.Ptr, AATags: Loc.AATags);
530 Adj.AATags.Scope = adjustAliasScopeList(ScopeList: Adj.AATags.Scope, LoopAliasScopes);
531 Adj.AATags.NoAlias =
532 adjustAliasScopeList(ScopeList: 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
542underlyingObjectsAlias(AAResults *AA, const DataLayout &DL,
543 const MemoryLocation &LocA, const MemoryLocation &LocB,
544 const SmallPtrSetImpl<const MDNode *> &LoopAliasScopes) {
545
546 MemoryLocation LocAS = adjustLoc(Loc: LocA, LoopAliasScopes);
547 MemoryLocation LocBS = adjustLoc(Loc: LocB, LoopAliasScopes);
548
549 BatchAAResults BAA(*AA);
550 BAA.enableCrossIterationMode();
551
552 if (BAA.isNoAlias(LocA: LocAS, LocB: LocBS))
553 return AliasResult::NoAlias;
554
555 // Check the underlying objects are the same
556 const Value *AObj = getUnderlyingObject(V: LocA.Ptr);
557 const Value *BObj = getUnderlyingObject(V: LocB.Ptr);
558
559 // If the underlying objects are the same, they must alias
560 if (AObj == BObj)
561 return AliasResult::MustAlias;
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(V: AObj) || !isIdentifiedObject(V: BObj))
566 return AliasResult::MayAlias;
567
568 // Otherwise we know the objects are different and both identified objects so
569 // must not alias.
570 return AliasResult::NoAlias;
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>(Val: I))
577 return LI->isUnordered();
578 else if (const StoreInst *SI = dyn_cast<StoreInst>(Val: 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(L: SrcLoop);
600 const SCEV *DstUB = SE->getBackedgeTakenCount(L: DstLoop);
601 if (isa<SCEVCouldNotCompute>(Val: SrcUB) || isa<SCEVCouldNotCompute>(Val: DstUB))
602 return false;
603
604 Type *WiderType = SE->getWiderType(Ty1: SrcUB->getType(), Ty2: DstUB->getType());
605 SrcUB = SE->getNoopOrZeroExtend(V: SrcUB, Ty: WiderType);
606 DstUB = SE->getNoopOrZeroExtend(V: DstUB, Ty: 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(BB: SrcBlock);
683 unsigned DstLevel = LI->getLoopDepth(BB: DstBlock);
684 const Loop *SrcLoop = LI->getLoopFor(BB: SrcBlock);
685 const Loop *DstLoop = LI->getLoopFor(BB: 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(SrcLoop: SrcUncommonFrontier, DstLoop: 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(S: Expression, L: 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(S: Expression, L: 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>(Val: Expr);
766 if (!AddRec)
767 return isLoopInvariant(Expression: 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&: *SE);
785 if (!isLoopInvariant(Expression: Step, LoopNest))
786 return false;
787 if (IsSrc)
788 Loops.set(mapSrcLoop(SrcLoop: AddRec->getLoop()));
789 else
790 Loops.set(mapDstLoop(DstLoop: AddRec->getLoop()));
791 return checkSubscript(Expr: 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,
797 SmallBitVector &Loops) {
798 return checkSubscript(Expr: Src, LoopNest, Loops, IsSrc: 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,
804 SmallBitVector &Loops) {
805 return checkSubscript(Expr: Dst, LoopNest, Loops, IsSrc: 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,
814 SmallBitVector &Loops) {
815 SmallBitVector SrcLoops(MaxLevels + 1);
816 SmallBitVector DstLoops(MaxLevels + 1);
817 if (!checkSrcSubscript(Src, LoopNest: SrcLoopNest, Loops&: SrcLoops))
818 return Subscript::NonLinear;
819 if (!checkDstSubscript(Dst, LoopNest: DstLoopNest, Loops&: 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(V: UB, Ty: 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>(Val: 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(BinOp: Instruction::Sub, /*Signed=*/true, LHS: A, RHS: B))
867 return SE.getMinusSCEV(LHS: A, RHS: B);
868 return nullptr;
869}
870
871/// Returns true iff \p Test is enabled.
872static bool isDependenceTestEnabled(const AnalysisOptions &Opts,
873 DependenceTestType Test) {
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)
880 return Test != DependenceTestType::BanerjeeMIV;
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(Pred: CmpInst::ICMP_EQ, LHS: Src, RHS: Dst)) {
900 LLVM_DEBUG(dbgs() << " provably dependent\n");
901 return false; // provably dependent
902 }
903 if (SE->isKnownPredicate(Pred: CmpInst::ICMP_NE, LHS: Src, RHS: 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) {
943 if (!isDependenceTestEnabled(Opts, Test: DependenceTestType::StrongSIV))
944 return false;
945
946 const SCEV *Coeff = Src->getStepRecurrence(SE&: *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(A: SrcConst, B: DstConst, SE&: *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>(Val: Delta) && isa<SCEVConstant>(Val: Coeff)) {
970 APInt ConstDelta = cast<SCEVConstant>(Val: Delta)->getAPInt();
971 APInt ConstCoeff = cast<SCEVConstant>(Val: Coeff)->getAPInt();
972 APInt Distance = ConstDelta; // these need to be initialized
973 APInt Remainder = ConstDelta;
974 APInt::sdivrem(LHS: ConstDelta, RHS: ConstCoeff, Quotient&: 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(Val: Distance);
985 if (Distance.sgt(RHS: 0))
986 Result.DV[Level].Direction &= Dependence::DVEntry::LT;
987 else if (Distance.slt(RHS: 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(S: Coeff)) {
997 LLVM_DEBUG(
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 Pred: ICmpInst::ICMP_NE, LHS: Coeff, RHS: SE->getZero(Ty: Coeff->getType()));
1004 Result.Assumptions = Result.Assumptions.getUnionWith(N: Pred, SE&: *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(S: Delta);
1027 bool DeltaMaybePositive = !SE->isKnownNonPositive(S: Delta);
1028 bool DeltaMaybeNegative = !SE->isKnownNonNegative(S: Delta);
1029 bool CoeffMaybePositive = !SE->isKnownNonPositive(S: Coeff);
1030 bool CoeffMaybeNegative = !SE->isKnownNonNegative(S: 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 {
1082 if (!isDependenceTestEnabled(Opts, Test: DependenceTestType::WeakCrossingSIV))
1083 return false;
1084
1085 const SCEV *Coeff = Src->getStepRecurrence(SE&: *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(A: DstConst, B: SrcConst, SE&: *SE);
1100 if (!Delta)
1101 return false;
1102
1103 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n");
1104 const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(Val: Coeff);
1105 if (!ConstCoeff)
1106 return false;
1107
1108 const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Val: Delta);
1109 if (!ConstDelta)
1110 return false;
1111
1112 ConstantRange SrcRange = SE->getSignedRange(S: Src);
1113 ConstantRange DstRange = SE->getSignedRange(S: Dst);
1114 LLVM_DEBUG(dbgs() << "\t SrcRange = " << SrcRange << "\n");
1115 LLVM_DEBUG(dbgs() << "\t DstRange = " << DstRange << "\n");
1116 if (SrcRange.intersectWith(CR: 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(Ty: 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(LHS: APDelta, RHS: APCoeff, Quotient&: 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(LHS: G0, RHS: G1, Quotient&: Q, Remainder&: 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(LHS: G0, RHS: G1, Quotient&: Q, Remainder&: R);
1191 }
1192 G = G1;
1193 LLVM_DEBUG(dbgs() << "\t GCD = " << G << "\n");
1194 X = AM.slt(RHS: 0) ? -A1 : A1;
1195 Y = BM.slt(RHS: 0) ? B1 : -B1;
1196
1197 // make sure gcd divides Delta
1198 R = Delta.srem(RHS: G);
1199 if (R != 0)
1200 return true; // gcd doesn't divide Delta, no dependence
1201 Q = Delta.sdiv(RHS: 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(LHS: A, RHS: B, Quotient&: Q, Remainder&: R);
1216 if (R == 0)
1217 return Q;
1218 if ((A.sgt(RHS: 0) && B.sgt(RHS: 0)) || (A.slt(RHS: 0) && B.slt(RHS: 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(LHS: A, RHS: B, Quotient&: Q, Remainder&: R);
1234 if (R == 0)
1235 return Q;
1236 if ((A.sgt(RHS: 0) && B.sgt(RHS: 0)) || (A.slt(RHS: 0) && B.slt(RHS: 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(RHS: 0)) {
1279 TL = ceilingOfQuotient(OA: -B, OB: 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(OA: UB - B, OB: A);
1284 LLVM_DEBUG(if (TU) dbgs() << "\t Possible TU = " << *TU << "\n");
1285 } else {
1286 TU = floorOfQuotient(OA: -B, OB: 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(OA: UB - B, OB: A);
1291 LLVM_DEBUG(if (TL) dbgs() << "\t Possible TL = " << *TL << "\n");
1292 }
1293 return std::make_pair(x&: TL, y&: 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 {
1318 if (!isDependenceTestEnabled(Opts, Test: DependenceTestType::ExactSIV))
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(RHS: 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&: *SE);
1345 const SCEV *ARConst = AR->getStart();
1346
1347 if (Const == ARConst && SE->isKnownNonZero(S: 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(A: Const, B: ARConst, SE&: *SE);
1356 if (!Delta)
1357 return false;
1358 const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(Val: ARCoeff);
1359 if (!ConstCoeff)
1360 return false;
1361
1362 if (const SCEV *UpperBound =
1363 collectUpperBound(L: AR->getLoop(), T: Delta->getType())) {
1364 LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound << "\n");
1365 bool OverlapAtLast = [&] {
1366 if (!SE->isKnownNonZero(S: ConstCoeff))
1367 return false;
1368 const SCEV *Last = AR->evaluateAtIteration(It: UpperBound, SE&: *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>(Val: Delta) &&
1383 !isRemainderZero(Dividend: cast<SCEVConstant>(Val: Delta), Divisor: 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 {
1424 if (!isDependenceTestEnabled(Opts, Test: DependenceTestType::WeakZeroSIV))
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&: *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&: *SE);
1446 bool Res = weakZeroSIVtestImpl(AR: Dst, Const: SrcConst, Level, Result);
1447 Result.negate(SE&: *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 {
1483 if (!isDependenceTestEnabled(Opts, Test: DependenceTestType::WeakZeroSIV))
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&: *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(AR: Src, Const: 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 {
1510 if (!isDependenceTestEnabled(Opts, Test: DependenceTestType::ExactRDIV))
1511 return false;
1512
1513 LLVM_DEBUG(dbgs() << "\tExact RDIV test\n");
1514 ++ExactRDIVapplications;
1515 bool Res = exactTestImpl(Src, Dst, Result, Level: 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&: *SE);
1526 const SCEV *SrcConst = Src->getStart();
1527 const SCEV *DstCoeff = Dst->getStepRecurrence(SE&: *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(A: DstConst, B: SrcConst, SE&: *SE);
1535 if (!Delta)
1536 return false;
1537 LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n");
1538 const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Val: Delta);
1539 const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(Val: SrcCoeff);
1540 const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(Val: 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, Delta: 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(L: Src->getLoop(), T: Delta->getType());
1565 if (SrcUM)
1566 LLVM_DEBUG(dbgs() << "\t SrcUM = " << *SrcUM << "\n");
1567
1568 std::optional<APInt> DstUM =
1569 collectNonNegativeConstantUpperBound(L: Dst->getLoop(), T: Delta->getType());
1570 if (DstUM)
1571 LLVM_DEBUG(dbgs() << "\t DstUM = " << *DstUM << "\n");
1572
1573 OverflowSafeSignedAPInt TC = CM.sdiv(RHS: 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(RHS: G);
1583 APInt TA = AM.sdiv(RHS: 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(A: TB, B: TX, UB: SrcUM);
1595 auto [TL1, TU1] = inferDomainOfAffine(A: TA, B: TY, UB: 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(A: *V0, B: *V1) : APIntOps::smax(A: *V0, B: *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(RHS: 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(RHS: 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(RHS: 0) && UpperDistance->sge(RHS: 0))
1650 NewDirection |= Dependence::DVEntry::EQ;
1651 if (LowerDistance->slt(RHS: 0))
1652 NewDirection |= Dependence::DVEntry::GT;
1653 if (UpperDistance->sgt(RHS: 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>(Val: Src);
1677 const SCEVAddRecExpr *DstAddRec = dyn_cast<SCEVAddRecExpr>(Val: Dst);
1678 if (SrcAddRec && DstAddRec) {
1679 const SCEV *SrcCoeff = SrcAddRec->getStepRecurrence(SE&: *SE);
1680 const SCEV *DstCoeff = DstAddRec->getStepRecurrence(SE&: *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(SrcLoop: CurSrcLoop);
1687 bool disproven = false;
1688 if (SrcCoeff == DstCoeff)
1689 disproven = strongSIVtest(Src: SrcAddRec, Dst: DstAddRec, Level, Result,
1690 UnderRuntimeAssumptions);
1691 else if (SrcCoeff == SE->getNegativeSCEV(V: DstCoeff))
1692 disproven = weakCrossingSIVtest(Src: SrcAddRec, Dst: DstAddRec, Level, Result);
1693 return disproven || exactSIVtest(Src: SrcAddRec, Dst: DstAddRec, Level, Result);
1694 }
1695 if (SrcAddRec) {
1696 const Loop *CurSrcLoop = SrcAddRec->getLoop();
1697 Level = mapSrcLoop(SrcLoop: CurSrcLoop);
1698 return weakZeroDstSIVtest(Src: SrcAddRec, DstConst: Dst, Level, Result);
1699 }
1700 if (DstAddRec) {
1701 const Loop *CurDstLoop = DstAddRec->getLoop();
1702 Level = mapDstLoop(DstLoop: CurDstLoop);
1703 return weakZeroSrcSIVtest(SrcConst: Src, Dst: 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>(Val: Src);
1724 const SCEVAddRecExpr *DstAddRec = dyn_cast<SCEVAddRecExpr>(Val: Dst);
1725 assert(SrcAddRec && DstAddRec && "Unexpected non-addrec input");
1726 return exactRDIVtest(Src: SrcAddRec, Dst: 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>(Val: Expr))
1749 return Constant->getAPInt();
1750 if (const auto *Product = dyn_cast<SCEVMulExpr>(Val: Expr))
1751 if (const auto *Constant = dyn_cast<SCEVConstant>(Val: Product->getOperand(i: 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>(Val: 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&: *SE);
1771 if (AddRec->getLoop() == CurLoop) {
1772 CurLoopCoeff = Step;
1773 } else {
1774 std::optional<APInt> ConstCoeff = getConstantCoefficient(Expr: 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(A: RunningGCD, B: ConstCoeff->abs());
1784 }
1785
1786 return accumulateCoefficientsGCD(Expr: 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 {
1808 if (!isDependenceTestEnabled(Opts, Test: DependenceTestType::GCDMIV))
1809 return false;
1810
1811 LLVM_DEBUG(dbgs() << "starting gcd\n");
1812 ++GCDapplications;
1813 unsigned BitWidth = SE->getTypeSizeInBits(Ty: Src->getType());
1814 APInt RunningGCD = APInt::getZero(numBits: BitWidth);
1815
1816 const SCEV *Dummy = nullptr;
1817 const SCEV *SrcConst =
1818 accumulateCoefficientsGCD(Expr: Src, CurLoop: nullptr, CurLoopCoeff&: Dummy, RunningGCD);
1819 if (!SrcConst)
1820 return false;
1821 const SCEV *DstConst =
1822 accumulateCoefficientsGCD(Expr: Dst, CurLoop: nullptr, CurLoopCoeff&: Dummy, RunningGCD);
1823 if (!DstConst)
1824 return false;
1825
1826 const SCEV *Delta = minusSCEVNoSignedOverflow(A: DstConst, B: SrcConst, SE&: *SE);
1827 if (!Delta)
1828 return false;
1829 LLVM_DEBUG(dbgs() << " Delta = " << *Delta << "\n");
1830 const SCEVConstant *Constant = dyn_cast<SCEVConstant>(Val: 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(RHS: 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>(Val: Coefficients)) {
1857 Coefficients = AddRec->getStart();
1858 const Loop *CurLoop = AddRec->getLoop();
1859 RunningGCD = 0;
1860 const SCEV *SrcCoeff = AddRec->getStepRecurrence(SE&: *SE);
1861 const SCEV *DstCoeff = SE->getZero(Ty: SrcCoeff->getType());
1862
1863 if (!accumulateCoefficientsGCD(Expr: Src, CurLoop, CurLoopCoeff&: SrcCoeff, RunningGCD) ||
1864 !accumulateCoefficientsGCD(Expr: Dst, CurLoop, CurLoopCoeff&: DstCoeff, RunningGCD))
1865 return false;
1866
1867 Delta = minusSCEVNoSignedOverflow(A: DstCoeff, B: SrcCoeff, SE&: *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(Expr: 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(A: RunningGCD, B: ConstCoeff->abs());
1878 LLVM_DEBUG(dbgs() << "\tRunningGCD = " << RunningGCD << "\n");
1879 if (RunningGCD != 0) {
1880 Remainder = ConstDelta.srem(RHS: RunningGCD);
1881 LLVM_DEBUG(dbgs() << "\tRemainder = " << Remainder << "\n");
1882 if (Remainder != 0) {
1883 unsigned Level = mapSrcLoop(SrcLoop: 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 &&
1912 SE.isKnownPredicate(Pred: CmpInst::ICMP_SGT, LHS: Lower, RHS: 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(LHS: A.Lower, RHS: B.Lower);
1926 if (A.Upper && B.Upper)
1927 Upper = SE.getAddExpr(LHS: A.Upper, RHS: 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(LHS: Lower, RHS: B.Lower) : B.Lower;
1941 if (B.Upper)
1942 Upper = Upper ? SE.getSMinExpr(LHS: Upper, RHS: 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(LHS: Coeff, RHS: Lower);
1965 const SCEV *UpperValue = SE.getMulExpr(LHS: Coeff, RHS: Upper);
1966 return BanerjeeInterval(SE.getSMinExpr(LHS: LowerValue, RHS: UpperValue),
1967 SE.getSMaxExpr(LHS: LowerValue, RHS: 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(Ty: Coeff->getType());
1975 if (Coeff->isZero())
1976 return constantInterval(C: Zero);
1977 if (!Upper) {
1978 if (SE.isKnownNegative(S: Coeff))
1979 return BanerjeeInterval(nullptr, Zero);
1980 if (SE.isKnownNonNegative(S: Coeff))
1981 return BanerjeeInterval(Zero, nullptr);
1982 return BanerjeeInterval(nullptr, nullptr);
1983 }
1984 return signedRangeInterval(Coeff, Lower: 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.
2010static BanerjeeInterval strictDirectionIntervalWithUnknownUpperBound(
2011 const SCEV *ACoeff, const SCEV *BCoeff, unsigned char Direction,
2012 ScalarEvolution &SE) {
2013 const SCEV *DeltaCoeff = SE.getMinusSCEV(LHS: ACoeff, RHS: BCoeff);
2014
2015 switch (Direction) {
2016 case Dependence::DVEntry::LT: {
2017 const SCEV *Boundary = SE.getNegativeSCEV(V: BCoeff);
2018 const SCEV *Lower = nullptr;
2019 const SCEV *Upper = nullptr;
2020 if (SE.isKnownNonNegative(S: DeltaCoeff) && SE.isKnownNonPositive(S: BCoeff))
2021 Lower = Boundary;
2022 if (SE.isKnownNonPositive(S: DeltaCoeff) && SE.isKnownNonNegative(S: BCoeff))
2023 Upper = Boundary;
2024 return BanerjeeInterval(Lower, Upper);
2025 }
2026 case Dependence::DVEntry::GT: {
2027 const SCEV *Lower = nullptr;
2028 const SCEV *Upper = nullptr;
2029 if (SE.isKnownNonNegative(S: ACoeff) && SE.isKnownNonNegative(S: DeltaCoeff))
2030 Lower = ACoeff;
2031 if (SE.isKnownNonPositive(S: ACoeff) && SE.isKnownNonPositive(S: 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.
2041static BanerjeeInterval intervalFromValues(ArrayRef<const SCEV *> 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()) {
2047 Lower = SE.getSMinExpr(LHS: Lower, RHS: Value);
2048 Upper = SE.getSMaxExpr(LHS: Upper, RHS: Value);
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(LHS: SE.getMulExpr(LHS: A, RHS: SrcIndex),
2059 RHS: SE.getMulExpr(LHS: B, RHS: 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(Ty1: Src->getType(), Ty2: Dst->getType());
2067 for (const SCEV *Subscript : {Src, Dst}) {
2068 while (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Val: Subscript)) {
2069 const SCEV *MaxIterIndex = SE.getBackedgeTakenCount(L: AddRec->getLoop());
2070 if (!isa<SCEVCouldNotCompute>(Val: MaxIterIndex))
2071 BaseType = SE.getWiderType(Ty1: BaseType, Ty2: 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 {
2098 if (!isDependenceTestEnabled(Opts, Test: DependenceTestType::BanerjeeMIV))
2099 return false;
2100
2101 LLVM_DEBUG(dbgs() << "starting Banerjee\n");
2102 ++BanerjeeApplications;
2103
2104 Type *BaseType = getBanerjeeBaseType(Src, Dst, SE&: *SE);
2105 unsigned BaseBits = SE->getTypeSizeInBits(Ty: 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(C&: F->getContext(), NumBits: WideBits);
2117 const SCEV *Zero = SE->getZero(Ty: WideType);
2118
2119 CoefficientInfo EmptyCoeff{.SrcCoeff: Zero, .DstCoeff: Zero, .MaxIterIndex: 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(Subscript: Src, SrcFlag: true, WideType, CI);
2126 const SCEV *B0 = collectCoeffInfo(Subscript: Dst, SrcFlag: false, WideType, CI);
2127 const SCEV *Delta = SE->getMinusSCEV(LHS: B0, RHS: 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(DirKind: Dependence::DVEntry::ALL, Level: 0, Bound, Delta)) {
2143 ++BanerjeeIndependence;
2144 return true;
2145 }
2146
2147 unsigned NewDeps = exploreDirections(Level: 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,
2178 MutableArrayRef<CoefficientInfo> CI) const {
2179 SmallBitVector SeenLevels(MaxLevels + 1);
2180 while (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Val: Subscript)) {
2181 unsigned K =
2182 SrcFlag ? mapSrcLoop(SrcLoop: AddRec->getLoop()) : mapDstLoop(DstLoop: 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&: *SE);
2188 const SCEV *&Coeff = SrcFlag ? CI[K].SrcCoeff : CI[K].DstCoeff;
2189 Coeff = SE->getNoopOrSignExtend(V: Step, Ty: WideType);
2190
2191 const SCEV *MaxIterIndex = SE->getBackedgeTakenCount(L: AddRec->getLoop());
2192 if (!isa<SCEVCouldNotCompute>(Val: 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(S: MaxIterIndex)
2199 ? SE->getNoopOrSignExtend(V: MaxIterIndex, Ty: WideType)
2200 : SE->getNoopOrZeroExtend(V: MaxIterIndex, Ty: WideType);
2201 }
2202
2203 Subscript = AddRec->getStart();
2204 }
2205 return SE->getNoopOrSignExtend(V: Subscript, Ty: 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(LHS: Sum, RHS: 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(LHS: Sum, RHS: 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,
2233 MutableArrayRef<BoundInfo> Bound,
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&: *SE))
2241 return false;
2242 }
2243 if (const SCEV *Lower = getLowerBound(Bound))
2244 if (SE->isKnownPredicate(Pred: CmpInst::ICMP_SGT, LHS: Lower, RHS: Delta))
2245 return false;
2246 if (const SCEV *Upper = getUpperBound(Bound))
2247 if (SE->isKnownPredicate(Pred: CmpInst::ICMP_SGT, LHS: Delta, RHS: Upper))
2248 return false;
2249 return true;
2250}
2251
2252/// Hierarchically expands the direction-vector search space.
2253unsigned DependenceInfo::exploreDirections(unsigned Level,
2254 MutableArrayRef<BoundInfo> Bound,
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: 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,
2280 Dependence::DVEntry::GT}) {
2281 if (!(OldDirections & Dir))
2282 continue;
2283 if (testBounds(DirKind: Dir, Level, Bound, Delta))
2284 NewDeps += exploreDirections(Level: 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,
2306 MutableArrayRef<BoundInfo> Bound,
2307 unsigned K) const {
2308 BanerjeeInterval SrcInterval =
2309 variableInterval(Coeff: CI[K].SrcCoeff, Upper: CI[K].MaxIterIndex, SE&: *SE);
2310 BanerjeeInterval DstInterval = variableInterval(
2311 Coeff: SE->getNegativeSCEV(V: CI[K].DstCoeff), Upper: CI[K].MaxIterIndex, SE&: *SE);
2312 BanerjeeInterval Interval = addIntervals(A: SrcInterval, B: DstInterval, SE&: *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,
2326 MutableArrayRef<BoundInfo> Bound,
2327 unsigned K) const {
2328 BanerjeeInterval Interval =
2329 variableInterval(Coeff: SE->getMinusSCEV(LHS: CI[K].SrcCoeff, RHS: CI[K].DstCoeff),
2330 Upper: CI[K].MaxIterIndex, SE&: *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,
2349 MutableArrayRef<BoundInfo> Bound,
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
2355 BanerjeeInterval Interval = strictDirectionIntervalWithUnknownUpperBound(
2356 ACoeff, BCoeff, Direction: Dependence::DVEntry::LT, SE&: *SE);
2357 if (MaxIterIndex && MaxIterIndex->isZero()) {
2358 Interval = emptyInterval(Ty: ACoeff->getType(), SE&: *SE);
2359 } else if (MaxIterIndex) {
2360 const SCEV *Zero = SE->getZero(Ty: ACoeff->getType());
2361 const SCEV *One = SE->getOne(Ty: ACoeff->getType());
2362 const SCEV *MaxMinusOne = SE->getMinusSCEV(LHS: MaxIterIndex, RHS: One);
2363 SmallVector<const SCEV *, 3> Values;
2364 Values.push_back(
2365 Elt: evaluateSubscriptDifference(A: ACoeff, SrcIndex: Zero, B: BCoeff, DstIndex: One, SE&: *SE));
2366 Values.push_back(
2367 Elt: evaluateSubscriptDifference(A: ACoeff, SrcIndex: Zero, B: BCoeff, DstIndex: MaxIterIndex, SE&: *SE));
2368 Values.push_back(Elt: evaluateSubscriptDifference(A: ACoeff, SrcIndex: MaxMinusOne, B: BCoeff,
2369 DstIndex: MaxIterIndex, SE&: *SE));
2370 Interval =
2371 intersectIntervals(A: Interval, B: intervalFromValues(Values, SE&: *SE), SE&: *SE);
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,
2391 MutableArrayRef<BoundInfo> Bound,
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
2397 BanerjeeInterval Interval = strictDirectionIntervalWithUnknownUpperBound(
2398 ACoeff, BCoeff, Direction: Dependence::DVEntry::GT, SE&: *SE);
2399 if (MaxIterIndex && MaxIterIndex->isZero()) {
2400 Interval = emptyInterval(Ty: ACoeff->getType(), SE&: *SE);
2401 } else if (MaxIterIndex) {
2402 const SCEV *Zero = SE->getZero(Ty: ACoeff->getType());
2403 const SCEV *One = SE->getOne(Ty: ACoeff->getType());
2404 const SCEV *MaxMinusOne = SE->getMinusSCEV(LHS: MaxIterIndex, RHS: One);
2405 SmallVector<const SCEV *, 3> Values;
2406 Values.push_back(
2407 Elt: evaluateSubscriptDifference(A: ACoeff, SrcIndex: One, B: BCoeff, DstIndex: Zero, SE&: *SE));
2408 Values.push_back(
2409 Elt: evaluateSubscriptDifference(A: ACoeff, SrcIndex: MaxIterIndex, B: BCoeff, DstIndex: Zero, SE&: *SE));
2410 Values.push_back(Elt: evaluateSubscriptDifference(A: ACoeff, SrcIndex: MaxIterIndex, B: BCoeff,
2411 DstIndex: MaxMinusOne, SE&: *SE));
2412 Interval =
2413 intersectIntervals(A: Interval, B: intervalFromValues(Values, SE&: *SE), SE&: *SE);
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,
2424 SmallVectorImpl<Subscript> &Pair) {
2425 assert(isLoadOrStore(Src) && "instruction is not load or store");
2426 assert(isLoadOrStore(Dst) && "instruction is not load or store");
2427 Value *SrcPtr = getLoadStorePointerOperand(V: Src);
2428 Value *DstPtr = getLoadStorePointerOperand(V: Dst);
2429 Loop *SrcLoop = LI->getLoopFor(BB: Src->getParent());
2430 Loop *DstLoop = LI->getLoopFor(BB: Dst->getParent());
2431 const SCEV *SrcAccessFn = SE->getSCEVAtScope(V: SrcPtr, L: SrcLoop);
2432 const SCEV *DstAccessFn = SE->getSCEVAtScope(V: DstPtr, L: DstLoop);
2433 const SCEVUnknown *SrcBase =
2434 dyn_cast<SCEVUnknown>(Val: SE->getPointerBase(V: SrcAccessFn));
2435 const SCEVUnknown *DstBase =
2436 dyn_cast<SCEVUnknown>(Val: SE->getPointerBase(V: 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(N: 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(Inst: Src);
2497 assert(ElemSize == SE->getElementSize(Dst) && "Different element sizes");
2498 SmallVector<const SCEV *, 4> SrcSizes, DstSizes;
2499 if (!delinearizeFixedSizeArray(SE&: *SE, Expr: SE->removePointerBase(S: SrcAccessFn),
2500 Subscripts&: SrcSubscripts, Sizes&: SrcSizes, ElementSize: ElemSize) ||
2501 !delinearizeFixedSizeArray(SE&: *SE, Expr: SE->removePointerBase(S: DstAccessFn),
2502 Subscripts&: DstSubscripts, Sizes&: DstSizes, ElementSize: 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(first1: SrcSizes.begin(), last1: SrcSizes.end(), first2: 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&: *SE, Sizes: SrcSizes, Subscripts: SrcSubscripts) ||
2526 !validateDelinearizationResult(SE&: *SE, Sizes: DstSizes, Subscripts: 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>(Val: SE->getPointerBase(V: SrcAccessFn));
2547 const SCEVUnknown *DstBase =
2548 dyn_cast<SCEVUnknown>(Val: SE->getPointerBase(V: DstAccessFn));
2549 assert(SrcBase && DstBase && SrcBase == DstBase &&
2550 "expected src and dst scev unknowns to be equal");
2551
2552 const SCEV *ElementSize = SE->getElementSize(Inst: Src);
2553 if (ElementSize != SE->getElementSize(Inst: Dst))
2554 return false;
2555
2556 const SCEV *SrcSCEV = SE->getMinusSCEV(LHS: SrcAccessFn, RHS: SrcBase);
2557 const SCEV *DstSCEV = SE->getMinusSCEV(LHS: DstAccessFn, RHS: DstBase);
2558
2559 const SCEVAddRecExpr *SrcAR = dyn_cast<SCEVAddRecExpr>(Val: SrcSCEV);
2560 const SCEVAddRecExpr *DstAR = dyn_cast<SCEVAddRecExpr>(Val: DstSCEV);
2561 if (!SrcAR || !DstAR || !SrcAR->isAffine() || !DstAR->isAffine())
2562 return false;
2563
2564 // First step: collect parametric terms in both array references.
2565 SmallVector<const SCEV *, 4> Terms;
2566 collectParametricTerms(SE&: *SE, Expr: SrcAR, Terms);
2567 collectParametricTerms(SE&: *SE, Expr: DstAR, Terms);
2568
2569 // Second step: find subscript sizes.
2570 SmallVector<const SCEV *, 4> Sizes;
2571 findArrayDimensions(SE&: *SE, Terms, Sizes, ElementSize);
2572
2573 // Third step: compute the access functions for each subscript.
2574 computeAccessFunctions(SE&: *SE, Expr: SrcAR, Subscripts&: SrcSubscripts, Sizes);
2575 computeAccessFunctions(SE&: *SE, Expr: DstAR, Subscripts&: 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&: *SE, Sizes, Subscripts: SrcSubscripts) ||
2590 !validateDelinearizationResult(SE&: *SE, Sizes, Subscripts: 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().
2600static void dumpSmallBitVector(SmallBitVector &BV) {
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
2611bool DependenceInfo::invalidate(Function &F, const PreservedAnalyses &PA,
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>(IR&: F, PA) ||
2620 Inv.invalidate<ScalarEvolutionAnalysis>(IR&: F, PA) ||
2621 Inv.invalidate<LoopAnalysis>(IR&: F, PA);
2622}
2623
2624void DependenceInfo::updateLoopAliasScopes(const Loop *L) {
2625 if (!L || !AlreadyCheckedLoops.insert(Ptr: L).second)
2626 return;
2627
2628 Function *DeclFn = F->getParent()
2629 ? F->getParent()->getFunction(Name: Intrinsic::getName(
2630 id: 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>(Val: &I)) {
2643 for (Metadata *Op : Decl->getScopeList()->operands())
2644 LoopAliasScopes.insert(Ptr: cast<MDNode>(Val: Op));
2645 }
2646 }
2647 }
2648 updateLoopAliasScopes(L: 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>
2661DependenceInfo::depends(Instruction *Src, Instruction *Dst,
2662 bool UnderRuntimeAssumptions) {
2663 SmallVector<const SCEVPredicate *, 4> Assume;
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(I: Src) || !isLoadOrStore(I: 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>(args&: Src, args&: Dst,
2676 args: SCEVUnionPredicate(Assume, *SE));
2677 }
2678
2679 const MemoryLocation &DstLoc = MemoryLocation::get(Inst: Dst);
2680 const MemoryLocation &SrcLoc = MemoryLocation::get(Inst: Src);
2681
2682 updateLoopAliasScopes(L: LI->getLoopFor(BB: Src->getParent()));
2683 updateLoopAliasScopes(L: LI->getLoopFor(BB: Dst->getParent()));
2684
2685 switch (underlyingObjectsAlias(AA, DL: F->getDataLayout(), LocA: DstLoc, LocB: SrcLoc,
2686 LoopAliasScopes)) {
2687 case AliasResult::MayAlias:
2688 case AliasResult::PartialAlias:
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>(args&: Src, args&: Dst,
2692 args: SCEVUnionPredicate(Assume, *SE));
2693 case AliasResult::NoAlias:
2694 // If the objects noalias, they are distinct, accesses are independent.
2695 LLVM_DEBUG(dbgs() << "no alias\n");
2696 return nullptr;
2697 case AliasResult::MustAlias:
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>(args&: Src, args&: Dst,
2707 args: SCEVUnionPredicate(Assume, *SE));
2708 }
2709
2710 Value *SrcPtr = getLoadStorePointerOperand(V: Src);
2711 Value *DstPtr = getLoadStorePointerOperand(V: Dst);
2712 const SCEV *SrcSCEV = SE->getSCEV(V: SrcPtr);
2713 const SCEV *DstSCEV = SE->getSCEV(V: DstPtr);
2714 LLVM_DEBUG(dbgs() << " SrcSCEV = " << *SrcSCEV << "\n");
2715 LLVM_DEBUG(dbgs() << " DstSCEV = " << *DstSCEV << "\n");
2716 const SCEV *SrcBase = SE->getPointerBase(V: SrcSCEV);
2717 const SCEV *DstBase = SE->getPointerBase(V: 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>(args&: Src, args&: Dst,
2727 args: 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(BB: Src->getParent());
2735 Loop *DstLoop = LI->getLoopFor(BB: Dst->getParent());
2736 if (!isLoopInvariant(Expression: SrcBase, LoopNest: SrcLoop) ||
2737 !isLoopInvariant(Expression: DstBase, LoopNest: DstLoop)) {
2738 LLVM_DEBUG(dbgs() << "The base pointer is not loop invariant.\n");
2739 return std::make_unique<Dependence>(args&: Src, args&: Dst,
2740 args: SCEVUnionPredicate(Assume, *SE));
2741 }
2742
2743 uint64_t EltSize = SrcLoc.Size.toRaw();
2744 const SCEV *SrcEv = SE->getMinusSCEV(LHS: SrcSCEV, RHS: SrcBase);
2745 const SCEV *DstEv = SE->getMinusSCEV(LHS: DstSCEV, RHS: 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(S: SrcEv, M: EltSize,
2750 Predicates: UnderRuntimeAssumptions ? &Assume : nullptr) ||
2751 !SE->isKnownMultipleOf(S: DstEv, M: EltSize,
2752 Predicates: UnderRuntimeAssumptions ? &Assume : nullptr)) {
2753 LLVM_DEBUG(dbgs() << "can't analyze SCEV with different offsets\n");
2754 return std::make_unique<Dependence>(args&: Src, args&: Dst,
2755 args: 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) {
2783 SmallBitVector Loops;
2784 Subscript::ClassificationKind TestClass =
2785 classifyPair(Src: Pair[P].Src, SrcLoopNest: SrcLoop, Dst: Pair[P].Dst, DstLoopNest: 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(N: MaxLevels + 1);
2809 Pair[P].Classification =
2810 classifyPair(Src: Pair[P].Src, SrcLoopNest: SrcLoop, Dst: Pair[P].Dst, DstLoopNest: DstLoop, Loops&: 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 = ");
2816 LLVM_DEBUG(dumpSmallBitVector(Pair[P].Loops));
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(S: Pair[SI].Src);
2825 ConstantRange DstRange = SE->getSignedRange(S: Pair[SI].Dst);
2826 if (SrcRange.intersectWith(CR: 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(Expression: Pair[SI].Src, LoopNest: SrcLoop, Loops&: Pair[SI].Loops);
2834 collectCommonLoops(Expression: Pair[SI].Dst, LoopNest: DstLoop, Loops&: Pair[SI].Loops);
2835 break;
2836 case Subscript::ZIV:
2837 LLVM_DEBUG(dbgs() << ", ZIV\n");
2838 if (testZIV(Src: Pair[SI].Src, Dst: 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(Src: Pair[SI].Src, Dst: 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(Src: Pair[SI].Src, Dst: Pair[SI].Dst, Result))
2852 return nullptr;
2853 break;
2854 case Subscript::MIV:
2855 LLVM_DEBUG(dbgs() << ", MIV\n");
2856 if (testMIV(Src: Pair[SI].Src, Dst: Pair[SI].Dst, Loops: 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(Level: II) == Dependence::DVEntry::EQ) {
2875 if (Result.DV[II - 1].Distance == nullptr)
2876 Result.DV[II - 1].Distance = SE->getZero(Ty: 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[]>(num: CommonLevels);
2900 DVSameSD = std::make_unique<FullDependence::DVEntry[]>(num: 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(Level: 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(Level: 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>(args: std::move(Result));
2937}
2938