lib/Analysis/DependenceAnalysis.cpp

13 //            Practical Dependence Testing
136                       "Dependence Analysis", true, true)
140 INITIALIZE_PASS_END(DependenceAnalysisWrapperPass, "da", "Dependence Analysis",
212   OS << "'Dependence Analysis' for function '" << F.getName() << "':\n";
218 // Dependence methods
221 bool Dependence::isInput() const {
227 bool Dependence::isOutput() const {
233 bool Dependence::isFlow() const {
239 bool Dependence::isAnti() const {
248 bool Dependence::isScalar(unsigned level) const {
259     : Dependence(Source, Destination), Levels(CommonLevels),
433 //            Practical Dependence Testing
591 void Dependence::dump(raw_ostream &OS) const {
1117 // From the paper, Practical Dependence Testing, Section 4.2.1
1198       Result.DV[Level].Direction &= Dependence::DVEntry::LT;
1200       Result.DV[Level].Direction &= Dependence::DVEntry::GT;
1202       Result.DV[Level].Direction &= Dependence::DVEntry::EQ;
1209     Result.DV[Level].Direction &= Dependence::DVEntry::EQ;
1234     unsigned NewDirection = Dependence::DVEntry::NONE;
1237       NewDirection = Dependence::DVEntry::LT;
1239       NewDirection |= Dependence::DVEntry::EQ;
1242       NewDirection |= Dependence::DVEntry::GT;
1252 // From the paper, Practical Dependence Testing, Section 4.2.2
1295     Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::LT);
1296     Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::GT);
1355       Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::LT);
1356       Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::GT);
1389     Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::EQ);
1586   unsigned NewDirection = Dependence::DVEntry::NONE;
1602     NewDirection |= Dependence::DVEntry::LT;
1628     NewDirection |= Dependence::DVEntry::EQ;
1645     NewDirection |= Dependence::DVEntry::GT;
1651   if (Result.DV[Level].Direction == Dependence::DVEntry::NONE)
1653   return Result.DV[Level].Direction == Dependence::DVEntry::NONE;
1669 // From the paper, Practical Dependence Testing, Section 4.2.2
1722       Result.DV[Level].Direction &= Dependence::DVEntry::GE;
1750         Result.DV[Level].Direction &= Dependence::DVEntry::LE;
1779 // From the paper, Practical Dependence Testing, Section 4.2.2
1831       Result.DV[Level].Direction &= Dependence::DVEntry::LE;
1859         Result.DV[Level].Direction &= Dependence::DVEntry::GE;
1994 // In Section 4.5 of the Practical Dependence Testing paper,the authors
2484         Result.DV[Level - 1].Direction &= unsigned(~Dependence::DVEntry::EQ);
2548     Bound[K].Direction = Dependence::DVEntry::ALL;
2549     Bound[K].DirSet = Dependence::DVEntry::NONE;
2553     if (Bound[K].Lower[Dependence::DVEntry::ALL])
2554       LLVM_DEBUG(dbgs() << *Bound[K].Lower[Dependence::DVEntry::ALL] << '\t');
2557     if (Bound[K].Upper[Dependence::DVEntry::ALL])
2558       LLVM_DEBUG(dbgs() << *Bound[K].Upper[Dependence::DVEntry::ALL] << '\n');
2566   if (testBounds(Dependence::DVEntry::ALL, 0, Bound, Delta)) {
2622         case Dependence::DVEntry::LT:
2625         case Dependence::DVEntry::EQ:
2628         case Dependence::DVEntry::GT:
2631         case Dependence::DVEntry::ALL:
2653       if (Bound[Level].Lower[Dependence::DVEntry::LT])
2654         LLVM_DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::LT]
2658       if (Bound[Level].Upper[Dependence::DVEntry::LT])
2659         LLVM_DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::LT]
2664       if (Bound[Level].Lower[Dependence::DVEntry::EQ])
2665         LLVM_DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::EQ]
2669       if (Bound[Level].Upper[Dependence::DVEntry::EQ])
2670         LLVM_DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::EQ]
2675       if (Bound[Level].Lower[Dependence::DVEntry::GT])
2676         LLVM_DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::GT]
2680       if (Bound[Level].Upper[Dependence::DVEntry::GT])
2681         LLVM_DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::GT]
2691     if (testBounds(Dependence::DVEntry::LT, Level, Bound, Delta))
2696     if (testBounds(Dependence::DVEntry::EQ, Level, Bound, Delta))
2701     if (testBounds(Dependence::DVEntry::GT, Level, Bound, Delta))
2705     Bound[Level].Direction = Dependence::DVEntry::ALL;
2744   Bound[K].Lower[Dependence::DVEntry::ALL] = nullptr; // Default value = -infinity.
2745   Bound[K].Upper[Dependence::DVEntry::ALL] = nullptr; // Default value = +infinity.
2747     Bound[K].Lower[Dependence::DVEntry::ALL] =
2750     Bound[K].Upper[Dependence::DVEntry::ALL] =
2757       Bound[K].Lower[Dependence::DVEntry::ALL] =
2760       Bound[K].Upper[Dependence::DVEntry::ALL] =
2783   Bound[K].Lower[Dependence::DVEntry::EQ] = nullptr; // Default value = -infinity.
2784   Bound[K].Upper[Dependence::DVEntry::EQ] = nullptr; // Default value = +infinity.
2788     Bound[K].Lower[Dependence::DVEntry::EQ] =
2791     Bound[K].Upper[Dependence::DVEntry::EQ] =
2800       Bound[K].Lower[Dependence::DVEntry::EQ] = NegativePart; // Zero
2803       Bound[K].Upper[Dependence::DVEntry::EQ] = PositivePart; // Zero
2823   Bound[K].Lower[Dependence::DVEntry::LT] = nullptr; // Default value = -infinity.
2824   Bound[K].Upper[Dependence::DVEntry::LT] = nullptr; // Default value = +infinity.
2830     Bound[K].Lower[Dependence::DVEntry::LT] =
2834     Bound[K].Upper[Dependence::DVEntry::LT] =
2843       Bound[K].Lower[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff);
2847       Bound[K].Upper[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff);
2867   Bound[K].Lower[Dependence::DVEntry::GT] = nullptr; // Default value = -infinity.
2868   Bound[K].Upper[Dependence::DVEntry::GT] = nullptr; // Default value = +infinity.
2874     Bound[K].Lower[Dependence::DVEntry::GT] =
2878     Bound[K].Upper[Dependence::DVEntry::GT] =
2886       Bound[K].Lower[Dependence::DVEntry::GT] = A[K].Coeff;
2889       Bound[K].Upper[Dependence::DVEntry::GT] = A[K].Coeff;
3061 //            Practical Dependence Testing
3208 void DependenceInfo::updateDirection(Dependence::DVEntry &Level,
3218     unsigned NewDirection = Dependence::DVEntry::NONE;
3220       NewDirection = Dependence::DVEntry::EQ;
3222       NewDirection |= Dependence::DVEntry::LT;
3224       NewDirection |= Dependence::DVEntry::GT;
3235     unsigned NewDirection = Dependence::DVEntry::NONE;
3240       NewDirection |= Dependence::DVEntry::EQ;
3245       NewDirection |= Dependence::DVEntry::LT;
3250       NewDirection |= Dependence::DVEntry::GT;
3392 // Otherwise, return a Dependence with as many details as possible.
3395 //            Practical Dependence Testing
3401 std::unique_ptr<Dependence>
3414     return std::make_unique<Dependence>(Src, Dst);
3429     return std::make_unique<Dependence>(Src, Dst);
3737         if (Result.DV[SJ - 1].Direction == Dependence::DVEntry::NONE)
3756       if (!(Result.getDirection(II) & Dependence::DVEntry::EQ)) {
3767       if (Result.getDirection(II) != Dependence::DVEntry::EQ) {
3826 const SCEV *DependenceInfo::getSplitIteration(const Dependence &Dep,