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