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