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

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