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