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
118 "Dependence Analysis", true, true)
123 "Dependence Analysis", true, true)
154 // Used to test the dependence analyzer.
192 // Dependence methods
194 // Returns true if this is an input dependence.
195 bool Dependence::isInput() const {
200 // Returns true if this is an output dependence.
201 bool Dependence::isOutput() const {
206 // Returns true if this is an flow (aka true) dependence.
207 bool Dependence::isFlow() const {
212 // Returns true if this is an anti dependence.
213 bool Dependence::isAnti() const {
222 bool Dependence::isScalar(unsigned level) const {
233 : Dependence(Source, Destination), Levels(CommonLevels),
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 {
700 // If we're looking at the possibility of a dependence between the store
1024 // 1) the values are equal, so there's a dependence
1025 // 2) the values are different, so there's no dependence
1026 // 3) the values might be equal, so we have to assume a dependence.
1028 // Return true if dependence disproved.
1051 // From the paper, Practical Dependence Testing, Section 4.2.1
1060 // If there's a dependence,
1064 // The dependence distance is
1068 // A dependence only exists if d is an integer and abs(d) <= U, where U is the
1069 // loop's upper bound. If a dependence exists, the dependence direction is
1076 // Return true if dependence disproved.
1109 // Distance greater than trip count - no dependence
1127 // Coeff doesn't divide Distance, no dependence
1135 Result.DV[Level].Direction &= Dependence::DVEntry::LT;
1137 Result.DV[Level].Direction &= Dependence::DVEntry::GT;
1139 Result.DV[Level].Direction &= Dependence::DVEntry::EQ;
1146 Result.DV[Level].Direction &= Dependence::DVEntry::EQ;
1171 unsigned NewDirection = Dependence::DVEntry::NONE;
1174 NewDirection = Dependence::DVEntry::LT;
1176 NewDirection |= Dependence::DVEntry::EQ;
1179 NewDirection |= Dependence::DVEntry::GT;
1189 // From the paper, Practical Dependence Testing, Section 4.2.2
1203 // If i < 0, there is no dependence.
1204 // If i > upperbound, there is no dependence.
1205 // If i = 0 (i.e., if c1 = c2), there's a dependence with distance = 0.
1206 // If i = upperbound, there's a dependence with distance = 0.
1207 // If i is integral, there's a dependence (all directions).
1208 // If the non-integer part = 1/2, there's a dependence (<> directions).
1209 // Otherwise, there's no dependence.
1215 // Return true if dependence disproved.
1236 Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::LT);
1237 Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::GT);
1270 // if Delta < 0, then no dependence.
1274 // No dependence, Delta < 0
1289 // Delta too big, no dependence
1296 Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::LT);
1297 Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::GT);
1317 // Coeff doesn't divide Delta, no dependence
1330 Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::EQ);
1346 // Returns true if dependence disproved; i.e., gcd does not divide Delta.
1371 return true; // gcd doesn't divide Delta, no dependence
1435 // Return true if dependence disproved.
1469 // gcd doesn't divide Delta, no dependence
1535 unsigned NewDirection = Dependence::DVEntry::NONE;
1551 NewDirection |= Dependence::DVEntry::LT;
1577 NewDirection |= Dependence::DVEntry::EQ;
1594 NewDirection |= Dependence::DVEntry::GT;
1600 if (Result.DV[Level].Direction == Dependence::DVEntry::NONE)
1602 return Result.DV[Level].Direction == Dependence::DVEntry::NONE;
1618 // From the paper, Practical Dependence Testing, Section 4.2.2
1633 // If i is not an integer, there's no dependence.
1634 // If i < 0 or > UB, there's no dependence.
1636 // 1st iteration will break the dependence.
1638 // last iteration will break the dependence.
1647 // Return true if dependence disproved.
1672 Result.DV[Level].Direction &= Dependence::DVEntry::LE;
1700 Result.DV[Level].Direction &= Dependence::DVEntry::GE;
1711 // No dependence, newDelta < 0
1717 // if SrcCoeff doesn't divide Delta, then no dependence
1729 // From the paper, Practical Dependence Testing, Section 4.2.2
1744 // If i is not an integer, there's no dependence.
1745 // If i < 0 or > UB, there's no dependence.
1747 // 1st iteration will break the dependence.
1749 // last iteration will break the dependence.
1758 // Return true if dependence disproved.
1782 Result.DV[Level].Direction &= Dependence::DVEntry::LE;
1810 Result.DV[Level].Direction &= Dependence::DVEntry::GE;
1821 // No dependence, newDelta < 0
1827 // if SrcCoeff doesn't divide Delta, then no dependence
1838 // exactRDIVtest - Tests the RDIV subscript pair for dependence.
1842 // Returns true if any possible dependence is disproved.
1873 // gcd doesn't divide Delta, no dependence
1948 // In Section 4.5 of the Practical Dependence Testing paper,the authors
1952 // dependence (not compute distances or directions), we'll use it as a
1961 // For a dependence to exist, c1 + a1*i must equal c2 + a2*j for some
1968 // To test for a dependence, we compute c2 - c1 and make sure it's in the
1988 // return true if dependence disproved
2105 // Return true if dependence disproved.
2176 // Return true if dependence disproved.
2241 // Tests the single-subscript MIV pair (Src and Dst) for dependence.
2242 // Return true if dependence disproved.
2270 // Tests an MIV subscript pair for dependence.
2271 // Returns true if any possible dependence is disproved.
2378 // the code above can't disprove the dependence because the GCD = 1.
2455 Result.DV[Level - 1].Direction &= unsigned(~Dependence::DVEntry::EQ);
2499 // Return true if dependence disproved.
2520 Bound[K].Direction = Dependence::DVEntry::ALL;
2521 Bound[K].DirSet = Dependence::DVEntry::NONE;
2525 if (Bound[K].Lower[Dependence::DVEntry::ALL])
2526 DEBUG(dbgs() << *Bound[K].Lower[Dependence::DVEntry::ALL] << '\t');
2529 if (Bound[K].Upper[Dependence::DVEntry::ALL])
2530 DEBUG(dbgs() << *Bound[K].Upper[Dependence::DVEntry::ALL] << '\n');
2538 if (testBounds(Dependence::DVEntry::ALL, 0, Bound, Delta)) {
2579 // dependences discovered. If the dependence is disproved,
2596 case Dependence::DVEntry::LT:
2599 case Dependence::DVEntry::EQ:
2602 case Dependence::DVEntry::GT:
2605 case Dependence::DVEntry::ALL:
2627 if (Bound[Level].Lower[Dependence::DVEntry::LT])
2628 DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::LT] << '\t');
2631 if (Bound[Level].Upper[Dependence::DVEntry::LT])
2632 DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::LT] << '\n');
2636 if (Bound[Level].Lower[Dependence::DVEntry::EQ])
2637 DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::EQ] << '\t');
2640 if (Bound[Level].Upper[Dependence::DVEntry::EQ])
2641 DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::EQ] << '\n');
2645 if (Bound[Level].Lower[Dependence::DVEntry::GT])
2646 DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::GT] << '\t');
2649 if (Bound[Level].Upper[Dependence::DVEntry::GT])
2650 DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::GT] << '\n');
2659 if (testBounds(Dependence::DVEntry::LT, Level, Bound, Delta))
2664 if (testBounds(Dependence::DVEntry::EQ, Level, Bound, Delta))
2669 if (testBounds(Dependence::DVEntry::GT, Level, Bound, Delta))
2673 Bound[Level].Direction = Dependence::DVEntry::ALL;
2716 Bound[K].Lower[Dependence::DVEntry::ALL] = nullptr; // Default value = -infinity.
2717 Bound[K].Upper[Dependence::DVEntry::ALL] = nullptr; // Default value = +infinity.
2719 Bound[K].Lower[Dependence::DVEntry::ALL] =
2722 Bound[K].Upper[Dependence::DVEntry::ALL] =
2729 Bound[K].Lower[Dependence::DVEntry::ALL] =
2732 Bound[K].Upper[Dependence::DVEntry::ALL] =
2757 Bound[K].Lower[Dependence::DVEntry::EQ] = nullptr; // Default value = -infinity.
2758 Bound[K].Upper[Dependence::DVEntry::EQ] = nullptr; // Default value = +infinity.
2762 Bound[K].Lower[Dependence::DVEntry::EQ] =
2765 Bound[K].Upper[Dependence::DVEntry::EQ] =
2774 Bound[K].Lower[Dependence::DVEntry::EQ] = NegativePart; // Zero
2777 Bound[K].Upper[Dependence::DVEntry::EQ] = PositivePart; // Zero
2799 Bound[K].Lower[Dependence::DVEntry::LT] = nullptr; // Default value = -infinity.
2800 Bound[K].Upper[Dependence::DVEntry::LT] = nullptr; // Default value = +infinity.
2806 Bound[K].Lower[Dependence::DVEntry::LT] =
2810 Bound[K].Upper[Dependence::DVEntry::LT] =
2819 Bound[K].Lower[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff);
2823 Bound[K].Upper[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff);
2845 Bound[K].Lower[Dependence::DVEntry::GT] = nullptr; // Default value = -infinity.
2846 Bound[K].Upper[Dependence::DVEntry::GT] = nullptr; // Default value = +infinity.
2852 Bound[K].Lower[Dependence::DVEntry::GT] =
2856 Bound[K].Upper[Dependence::DVEntry::GT] =
2864 Bound[K].Lower[Dependence::DVEntry::GT] = A[K].Coeff;
2867 Bound[K].Upper[Dependence::DVEntry::GT] = A[K].Coeff;
3037 // in terms of dependence), set consistent to false.
3040 // Practical Dependence Testing
3067 // in terms of dependence), set consistent to false.
3094 // in terms of dependence), set consistent to false.
3190 void DependenceAnalysis::updateDirection(Dependence::DVEntry &Level,
3201 unsigned NewDirection = Dependence::DVEntry::NONE;
3203 NewDirection = Dependence::DVEntry::EQ;
3205 NewDirection |= Dependence::DVEntry::LT;
3207 NewDirection |= Dependence::DVEntry::GT;
3218 unsigned NewDirection = Dependence::DVEntry::NONE;
3223 NewDirection |= Dependence::DVEntry::EQ;
3228 NewDirection |= Dependence::DVEntry::LT;
3233 NewDirection |= Dependence::DVEntry::GT;
3310 // The delinearization transforms a single-subscript MIV dependence test into
3311 // a multi-subscript SIV dependence test that is easier to compute. So we
3321 // delinearization has found, and add these constraints to the dependence
3347 // Returns NULL if there is no dependence.
3348 // Otherwise, return a Dependence with as many details as possible.
3351 // Practical Dependence Testing
3357 std::unique_ptr<Dependence>
3365 // if both instructions don't reference memory, there's no dependence
3371 return make_unique<Dependence>(Src, Dst);
3383 return make_unique<Dependence>(Src, Dst);
3389 break; // The underlying objects alias; test accesses for dependence.
3723 if (Result.DV[SJ - 1].Direction == Dependence::DVEntry::NONE)
3740 // loop-independent dependence is possible.
3742 if (!(Result.getDirection(II) & Dependence::DVEntry::EQ)) {
3750 // loop-independent dependence possible, then no dependence exists.
3753 if (Result.getDirection(II) != Dependence::DVEntry::EQ) {
3771 // The re-computation is basically a repeat of the entire dependence test,
3772 // though simplified since we know that the dependence exists.
3778 // Generally, the dependence analyzer will be used to build
3779 // a dependence graph for a function (basically a map from instructions
3799 // There's a loop-carried flow dependence from the store to the load,
3800 // found by the weak-crossing SIV test. The dependence will have a flag,
3801 // indicating that the dependence can be broken by splitting the loop.
3803 // Splitting the loop breaks the dependence, like so:
3812 // breaks the dependence and allows us to vectorize/parallelize
3814 const SCEV *DependenceAnalysis::getSplitIteration(const Dependence &Dep,
