Lines Matching refs:Dependence
14 // Practical Dependence Testing
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.
28 // subscripts. Since Clang linearizes some array subscripts, the dependence
116 "Dependence Analysis", true, true)
121 "Dependence Analysis", true, true)
152 // Used to test the dependence analyzer.
166 if (Dependence *D = DA->depends(&*SrcI, &*DstI, true)) {
191 // Dependence methods
193 // Returns true if this is an input dependence.
194 bool Dependence::isInput() const {
199 // Returns true if this is an output dependence.
200 bool Dependence::isOutput() const {
205 // Returns true if this is an flow (aka true) dependence.
206 bool Dependence::isFlow() const {
211 // Returns true if this is an anti dependence.
212 bool Dependence::isAnti() const {
221 bool Dependence::isScalar(unsigned level) const {
233 Dependence(Source, Destination),
266 // will break this dependence.
274 // will break this dependence.
281 // Returns true if splitting this loop will break the dependence.
416 // Practical Dependence Testing
574 // For debugging purposes. Dumps a dependence to OS.
575 void Dependence::dump(raw_ostream &OS) const {
703 // If we're looking at the possibility of a dependence between the store
955 // 1) the values are equal, so there's a dependence
956 // 2) the values are different, so there's no dependence
957 // 3) the values might be equal, so we have to assume a dependence.
959 // Return true if dependence disproved.
982 // From the paper, Practical Dependence Testing, Section 4.2.1
991 // If there's a dependence,
995 // The dependence distance is
999 // A dependence only exists if d is an integer and abs(d) <= U, where U is the
1000 // loop's upper bound. If a dependence exists, the dependence direction is
1007 // Return true if dependence disproved.
1040 // Distance greater than trip count - no dependence
1058 // Coeff doesn't divide Distance, no dependence
1066 Result.DV[Level].Direction &= Dependence::DVEntry::LT;
1068 Result.DV[Level].Direction &= Dependence::DVEntry::GT;
1070 Result.DV[Level].Direction &= Dependence::DVEntry::EQ;
1077 Result.DV[Level].Direction &= Dependence::DVEntry::EQ;
1102 unsigned NewDirection = Dependence::DVEntry::NONE;
1105 NewDirection = Dependence::DVEntry::LT;
1107 NewDirection |= Dependence::DVEntry::EQ;
1110 NewDirection |= Dependence::DVEntry::GT;
1120 // From the paper, Practical Dependence Testing, Section 4.2.2
1134 // If i < 0, there is no dependence.
1135 // If i > upperbound, there is no dependence.
1136 // If i = 0 (i.e., if c1 = c2), there's a dependence with distance = 0.
1137 // If i = upperbound, there's a dependence with distance = 0.
1138 // If i is integral, there's a dependence (all directions).
1139 // If the non-integer part = 1/2, there's a dependence (<> directions).
1140 // Otherwise, there's no dependence.
1146 // Return true if dependence disproved.
1167 Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::LT);
1168 Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::GT);
1203 // if Delta < 0, then no dependence.
1207 // No dependence, Delta < 0
1222 // Delta too big, no dependence
1229 Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::LT);
1230 Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::GT);
1250 // Coeff doesn't divide Delta, no dependence
1263 Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::EQ);
1279 // Returns true if dependence disproved; i.e., gcd does not divide Delta.
1304 return true; // gcd doesn't divide Delta, no dependence
1368 // Return true if dependence disproved.
1402 // gcd doesn't divide Delta, no dependence
1468 unsigned NewDirection = Dependence::DVEntry::NONE;
1484 NewDirection |= Dependence::DVEntry::LT;
1510 NewDirection |= Dependence::DVEntry::EQ;
1527 NewDirection |= Dependence::DVEntry::GT;
1533 if (Result.DV[Level].Direction == Dependence::DVEntry::NONE)
1535 return Result.DV[Level].Direction == Dependence::DVEntry::NONE;
1551 // From the paper, Practical Dependence Testing, Section 4.2.2
1566 // If i is not an integer, there's no dependence.
1567 // If i < 0 or > UB, there's no dependence.
1569 // 1st iteration will break the dependence.
1571 // last iteration will break the dependence.
1580 // Return true if dependence disproved.
1605 Result.DV[Level].Direction &= Dependence::DVEntry::LE;
1633 Result.DV[Level].Direction &= Dependence::DVEntry::GE;
1644 // No dependence, newDelta < 0
1650 // if SrcCoeff doesn't divide Delta, then no dependence
1662 // From the paper, Practical Dependence Testing, Section 4.2.2
1677 // If i is not an integer, there's no dependence.
1678 // If i < 0 or > UB, there's no dependence.
1680 // 1st iteration will break the dependence.
1682 // last iteration will break the dependence.
1691 // Return true if dependence disproved.
1715 Result.DV[Level].Direction &= Dependence::DVEntry::LE;
1743 Result.DV[Level].Direction &= Dependence::DVEntry::GE;
1754 // No dependence, newDelta < 0
1760 // if SrcCoeff doesn't divide Delta, then no dependence
1771 // exactRDIVtest - Tests the RDIV subscript pair for dependence.
1775 // Returns true if any possible dependence is disproved.
1806 // gcd doesn't divide Delta, no dependence
1881 // In Section 4.5 of the Practical Dependence Testing paper,the authors
1885 // dependence (not compute distances or directions), we'll use it as a
1894 // For a dependence to exist, c1 + a1*i must equal c2 + a2*j for some
1901 // To test for a dependence, we compute c2 - c1 and make sure it's in the
1921 // return true if dependence disproved
2038 // Return true if dependence disproved.
2109 // Return true if dependence disproved.
2174 // Tests the single-subscript MIV pair (Src and Dst) for dependence.
2175 // Return true if dependence disproved.
2203 // Tests an MIV subscript pair for dependence.
2204 // Returns true if any possible dependence is disproved.
2311 // the code above can't disprove the dependence because the GCD = 1.
2388 Result.DV[Level - 1].Direction &= unsigned(~Dependence::DVEntry::EQ);
2432 // Return true if dependence disproved.
2453 Bound[K].Direction = Dependence::DVEntry::ALL;
2454 Bound[K].DirSet = Dependence::DVEntry::NONE;
2458 if (Bound[K].Lower[Dependence::DVEntry::ALL])
2459 DEBUG(dbgs() << *Bound[K].Lower[Dependence::DVEntry::ALL] << '\t');
2462 if (Bound[K].Upper[Dependence::DVEntry::ALL])
2463 DEBUG(dbgs() << *Bound[K].Upper[Dependence::DVEntry::ALL] << '\n');
2471 if (testBounds(Dependence::DVEntry::ALL, 0, Bound, Delta)) {
2512 // dependences discovered. If the dependence is disproved,
2529 case Dependence::DVEntry::LT:
2532 case Dependence::DVEntry::EQ:
2535 case Dependence::DVEntry::GT:
2538 case Dependence::DVEntry::ALL:
2560 if (Bound[Level].Lower[Dependence::DVEntry::LT])
2561 DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::LT] << '\t');
2564 if (Bound[Level].Upper[Dependence::DVEntry::LT])
2565 DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::LT] << '\n');
2569 if (Bound[Level].Lower[Dependence::DVEntry::EQ])
2570 DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::EQ] << '\t');
2573 if (Bound[Level].Upper[Dependence::DVEntry::EQ])
2574 DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::EQ] << '\n');
2578 if (Bound[Level].Lower[Dependence::DVEntry::GT])
2579 DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::GT] << '\t');
2582 if (Bound[Level].Upper[Dependence::DVEntry::GT])
2583 DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::GT] << '\n');
2592 if (testBounds(Dependence::DVEntry::LT, Level, Bound, Delta))
2597 if (testBounds(Dependence::DVEntry::EQ, Level, Bound, Delta))
2602 if (testBounds(Dependence::DVEntry::GT, Level, Bound, Delta))
2606 Bound[Level].Direction = Dependence::DVEntry::ALL;
2649 Bound[K].Lower[Dependence::DVEntry::ALL] = nullptr; // Default value = -infinity.
2650 Bound[K].Upper[Dependence::DVEntry::ALL] = nullptr; // Default value = +infinity.
2652 Bound[K].Lower[Dependence::DVEntry::ALL] =
2655 Bound[K].Upper[Dependence::DVEntry::ALL] =
2662 Bound[K].Lower[Dependence::DVEntry::ALL] =
2665 Bound[K].Upper[Dependence::DVEntry::ALL] =
2690 Bound[K].Lower[Dependence::DVEntry::EQ] = nullptr; // Default value = -infinity.
2691 Bound[K].Upper[Dependence::DVEntry::EQ] = nullptr; // Default value = +infinity.
2695 Bound[K].Lower[Dependence::DVEntry::EQ] =
2698 Bound[K].Upper[Dependence::DVEntry::EQ] =
2707 Bound[K].Lower[Dependence::DVEntry::EQ] = NegativePart; // Zero
2710 Bound[K].Upper[Dependence::DVEntry::EQ] = PositivePart; // Zero
2732 Bound[K].Lower[Dependence::DVEntry::LT] = nullptr; // Default value = -infinity.
2733 Bound[K].Upper[Dependence::DVEntry::LT] = nullptr; // Default value = +infinity.
2740 Bound[K].Lower[Dependence::DVEntry::LT] =
2744 Bound[K].Upper[Dependence::DVEntry::LT] =
2753 Bound[K].Lower[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff);
2757 Bound[K].Upper[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff);
2779 Bound[K].Lower[Dependence::DVEntry::GT] = nullptr; // Default value = -infinity.
2780 Bound[K].Upper[Dependence::DVEntry::GT] = nullptr; // Default value = +infinity.
2787 Bound[K].Lower[Dependence::DVEntry::GT] =
2791 Bound[K].Upper[Dependence::DVEntry::GT] =
2799 Bound[K].Lower[Dependence::DVEntry::GT] = A[K].Coeff;
2802 Bound[K].Upper[Dependence::DVEntry::GT] = A[K].Coeff;
2976 // in terms of dependence), set consistent to false.
2979 // Practical Dependence Testing
3006 // in terms of dependence), set consistent to false.
3033 // in terms of dependence), set consistent to false.
3129 void DependenceAnalysis::updateDirection(Dependence::DVEntry &Level,
3140 unsigned NewDirection = Dependence::DVEntry::NONE;
3142 NewDirection = Dependence::DVEntry::EQ;
3144 NewDirection |= Dependence::DVEntry::LT;
3146 NewDirection |= Dependence::DVEntry::GT;
3157 unsigned NewDirection = Dependence::DVEntry::NONE;
3162 NewDirection |= Dependence::DVEntry::EQ;
3167 NewDirection |= Dependence::DVEntry::LT;
3172 NewDirection |= Dependence::DVEntry::GT;
3233 // The delinearization transforms a single-subscript MIV dependence test into
3234 // a multi-subscript SIV dependence test that is easier to compute. So we
3243 // delinearization has found, and add these constraints to the dependence
3270 // Returns NULL if there is no dependence.
3271 // Otherwise, return a Dependence with as many details as possible.
3274 // Practical Dependence Testing
3280 Dependence *DependenceAnalysis::depends(Instruction *Src,
3288 // if both instructions don't reference memory, there's no dependence
3294 return new Dependence(Src, Dst);
3305 return new Dependence(Src, Dst);
3311 break; // The underlying objects alias; test accesses for dependence.
3639 if (Result.DV[SJ - 1].Direction == Dependence::DVEntry::NONE)
3656 // loop-independent dependence is possible.
3658 if (!(Result.getDirection(II) & Dependence::DVEntry::EQ)) {
3666 // loop-independent dependence possible, then no dependence exists.
3669 if (Result.getDirection(II) != Dependence::DVEntry::EQ) {
3689 // The re-computation is basically a repeat of the entire dependence test,
3690 // though simplified since we know that the dependence exists.
3696 // Generally, the dependence analyzer will be used to build
3697 // a dependence graph for a function (basically a map from instructions
3717 // There's a loop-carried flow dependence from the store to the load,
3718 // found by the weak-crossing SIV test. The dependence will have a flag,
3719 // indicating that the dependence can be broken by splitting the loop.
3721 // Splitting the loop breaks the dependence, like so:
3730 // breaks the dependence and allows us to vectorize/parallelize
3732 const SCEV *DependenceAnalysis::getSplitIteration(const Dependence *Dep,
3734 assert(Dep && "expected a pointer to a Dependence");
