DependenceAnalysis.cpp source code [llvm_projects/llvm/lib/Analysis/DependenceAnalysis.cpp]

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

Browse the source code of llvm_projects/llvm/lib/Analysis/DependenceAnalysis.cpp