lib/Analysis/DependenceAnalysis.cpp

190   return Src->mayReadFromMemory() && Dst->mayReadFromMemory();
196   return Src->mayWriteToMemory() && Dst->mayWriteToMemory();
202   return Src->mayWriteToMemory() && Dst->mayReadFromMemory();
208   return Src->mayReadFromMemory() && Dst->mayWriteToMemory();
660 // Examines the loop nesting of the Src and Dst
677 //          ... - loops containing Src but not Dst
678 //    SrcLevels - innermost loop containing Src but not Dst
679 //          ... - loops containing Dst but not Src
680 //    MaxLevels - innermost loops containing Dst but not Src
699 // to A (the Src) and the load from A (the Dst), we'll note that they
710 void DependenceAnalysis::establishNestingLevels(const Instruction *Src,
712   const BasicBlock *SrcBlock = Src->getParent();
786   const SCEV *Src = Pair->Src;
788   if ((isa<SCEVZeroExtendExpr>(Src) && isa<SCEVZeroExtendExpr>(Dst)) ||
789       (isa<SCEVSignExtendExpr>(Src) && isa<SCEVSignExtendExpr>(Dst))) {
790     const SCEVCastExpr *SrcCast = cast<SCEVCastExpr>(Src);
793       Pair->Src = SrcCast->getOperand();
802 bool DependenceAnalysis::checkSrcSubscript(const SCEV *Src,
805   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Src);
807     return isLoopInvariant(Src, LoopNest);
835 // Examines the subscript pair (the Src and Dst SCEVs)
839 DependenceAnalysis::classifyPair(const SCEV *Src, const Loop *SrcLoopNest,
844   if (!checkSrcSubscript(Src, SrcLoopNest, SrcLoops))
955 bool DependenceAnalysis::testZIV(const SCEV *Src,
958   DEBUG(dbgs() << "    src = " << *Src << "\n");
961   if (isKnownPredicate(CmpInst::ICMP_EQ, Src, Dst)) {
965   if (isKnownPredicate(CmpInst::ICMP_NE, Src, Dst)) {
1584   // the Src and Dst loops. If it isn't, then there's no need to
1695   // Src and Dst loops. If it isn't, then there's no need to record a direction.
2034 bool DependenceAnalysis::testSIV(const SCEV *Src,
2040   DEBUG(dbgs() << "    src = " << *Src << "\n");
2042   const SCEVAddRecExpr *SrcAddRec = dyn_cast<SCEVAddRecExpr>(Src);
2064       gcdMIVtest(Src, Dst, Result) ||
2075       gcdMIVtest(Src, Dst, Result);
2080     const SCEV *SrcConst = Src;
2085       gcdMIVtest(Src, Dst, Result);
2105 bool DependenceAnalysis::testRDIV(const SCEV *Src,
2118   DEBUG(dbgs() << "    src = " << *Src << "\n");
2120   const SCEVAddRecExpr *SrcAddRec = dyn_cast<SCEVAddRecExpr>(Src);
2149       SrcConst = Src;
2162     gcdMIVtest(Src, Dst, Result) ||
2169 // Tests the single-subscript MIV pair (Src and Dst) for dependence.
2172 bool DependenceAnalysis::testMIV(const SCEV *Src,
2176   DEBUG(dbgs() << "    src = " << *Src << "\n");
2179   return gcdMIVtest(Src, Dst, Result) ||
2180     banerjeeMIVtest(Src, Dst, Loops, Result);
2214 bool DependenceAnalysis::gcdMIVtest(const SCEV *Src,
2219   unsigned BitWidth = SE->getTypeSizeInBits(Src->getType());
2222   // Examine Src coefficients.
2226   const SCEV *Coefficients = Src;
2319   Coefficients = Src;
2327     const SCEV *Inner = Src;
2428 bool DependenceAnalysis::banerjeeMIVtest(const SCEV *Src,
2434   DEBUG(dbgs() << "    Src = " << *Src << '\n');
2436   CoefficientInfo *A = collectCoeffInfo(Src, true, A0);
2963 // to simplify a subscript pair (Src and Dst).
2972 bool DependenceAnalysis::propagate(const SCEV *&Src,
2982       Result |= propagateDistance(Src, Dst, Constraints[LI], Consistent);
2984       Result |= propagateLine(Src, Dst, Constraints[LI], Consistent);
2986       Result |= propagatePoint(Src, Dst, Constraints[LI]);
2993 // constraint into a subscript pair (Src and Dst).
2997 bool DependenceAnalysis::propagateDistance(const SCEV *&Src,
3002   DEBUG(dbgs() << "\t\tSrc is " << *Src << "\n");
3003   const SCEV *A_K = findCoefficient(Src, CurLoop);
3007   Src = SE->getMinusSCEV(Src, DA_K);
3008   Src = zeroCoefficient(Src, CurLoop);
3009   DEBUG(dbgs() << "\t\tnew Src is " << *Src << "\n");
3020 // constraint into a subscript pair (Src and Dst).
3024 bool DependenceAnalysis::propagateLine(const SCEV *&Src,
3033   DEBUG(dbgs() << "\t\tSrc = " << *Src << "\n");
3044     //    Src = SE->getAddExpr(Src, SE->getMulExpr(AP_K, SE->getConstant(CdivB)));
3045     Src = SE->getMinusSCEV(Src, SE->getMulExpr(AP_K, SE->getConstant(CdivB)));
3047     if (!findCoefficient(Src, CurLoop)->isZero())
3058     const SCEV *A_K = findCoefficient(Src, CurLoop);
3059     Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, SE->getConstant(CdivA)));
3060     Src = zeroCoefficient(Src, CurLoop);
3072     const SCEV *A_K = findCoefficient(Src, CurLoop);
3073     Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, SE->getConstant(CdivA)));
3074     Src = zeroCoefficient(Src, CurLoop);
3081     const SCEV *A_K = findCoefficient(Src, CurLoop);
3082     Src = SE->getMulExpr(Src, A);
3084     Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, C));
3085     Src = zeroCoefficient(Src, CurLoop);
3090   DEBUG(dbgs() << "\t\tnew Src = " << *Src << "\n");
3097 // constraint into a subscript pair (Src and Dst).
3099 bool DependenceAnalysis::propagatePoint(const SCEV *&Src,
3103   const SCEV *A_K = findCoefficient(Src, CurLoop);
3107   DEBUG(dbgs() << "\t\tSrc is " << *Src << "\n");
3108   Src = SE->getAddExpr(Src, SE->getMinusSCEV(XA_K, YAP_K));
3109   Src = zeroCoefficient(Src, CurLoop);
3110   DEBUG(dbgs() << "\t\tnew Src is " << *Src << "\n");
3197 Dependence *DependenceAnalysis::depends(Instruction *Src,
3200   if (Src == Dst)
3203   if ((!Src->mayReadFromMemory() && !Src->mayWriteToMemory()) ||
3208   if (!isLoadOrStore(Src) || !isLoadOrStore(Dst)) {
3211     return new Dependence(Src, Dst);
3214   Value *SrcPtr = getPointerOperand(Src);
3222     return new Dependence(Src, Dst);
3232   establishNestingLevels(Src, Dst);
3236   FullDependence Result(Src, Dst, PossiblyLoopIndependent, CommonLevels);
3251       isLoopInvariant(SrcPtrSCEV, LI->getLoopFor(Src->getParent())) &&
3264       Pair[P].Src = SE->getSCEV(*SrcIdx);
3274     Pair[0].Src = SrcSCEV;
3284       classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()),
3290     DEBUG(dbgs() << "\tsrc = " << *Pair[P].Src << "\n");
3330   //      Src Dst    Classification Loops  GroupLoops Group
3361       collectCommonLoops(Pair[SI].Src,
3362                          LI->getLoopFor(Src->getParent()),
3414       if (testZIV(Pair[SI].Src, Pair[SI].Dst, Result))
3421       if (testSIV(Pair[SI].Src, Pair[SI].Dst, Level,
3428       if (testRDIV(Pair[SI].Src, Pair[SI].Dst, Result))
3433       if (testMIV(Pair[SI].Src, Pair[SI].Dst, Pair[SI].Loops, Result))
3470           if (testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level,
3491             if (propagate(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops,
3496                 classifyPair(Pair[SJ].Src, LI->getLoopFor(Src->getParent()),
3502                 if (testZIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
3525           if (testRDIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
3538           if (testMIV(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops, Result))
3648   Instruction *Src = Dep->getSrc();
3650   assert(Src->mayReadFromMemory() || Src->mayWriteToMemory());
3652   assert(isLoadOrStore(Src));
3654   Value *SrcPtr = getPointerOperand(Src);
3660   establishNestingLevels(Src, Dst);
3662   FullDependence Result(Src, Dst, false, CommonLevels);
3673       isLoopInvariant(SrcPtrSCEV, LI->getLoopFor(Src->getParent())) &&
3685       Pair[P].Src = SE->getSCEV(*SrcIdx);
3692     Pair[0].Src = SrcSCEV;
3702       classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()),
3716       collectCommonLoops(Pair[SI].Src,
3717                          LI->getLoopFor(Src->getParent()),
3758       (void) testSIV(Pair[SI].Src, Pair[SI].Dst, Level,
3797           (void) testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level,
3810             if (propagate(Pair[SJ].Src, Pair[SJ].Dst,
3813                 classifyPair(Pair[SJ].Src, LI->getLoopFor(Src->getParent()),