# Changeset View

Changeset View

# Standalone View

Standalone View

# lib/Analysis/DependenceAnalysis.cpp

Show First 20 Lines • Show All 100 Lines • ▼ Show 20 Line(s) | |||||

101 | STATISTIC(DeltaIndependence, "Delta independence"); | 101 | STATISTIC(DeltaIndependence, "Delta independence"); | ||

102 | STATISTIC(DeltaPropagations, "Delta propagations"); | 102 | STATISTIC(DeltaPropagations, "Delta propagations"); | ||

103 | STATISTIC(GCDapplications, "GCD applications"); | 103 | STATISTIC(GCDapplications, "GCD applications"); | ||

104 | STATISTIC(GCDsuccesses, "GCD successes"); | 104 | STATISTIC(GCDsuccesses, "GCD successes"); | ||

105 | STATISTIC(GCDindependence, "GCD independence"); | 105 | STATISTIC(GCDindependence, "GCD independence"); | ||

106 | STATISTIC(BanerjeeApplications, "Banerjee applications"); | 106 | STATISTIC(BanerjeeApplications, "Banerjee applications"); | ||

107 | STATISTIC(BanerjeeIndependence, "Banerjee independence"); | 107 | STATISTIC(BanerjeeIndependence, "Banerjee independence"); | ||

108 | STATISTIC(BanerjeeSuccesses, "Banerjee successes"); | 108 | STATISTIC(BanerjeeSuccesses, "Banerjee successes"); | ||

109 | STATISTIC(SymbolicEQSuccesses, "Symbolic EQ successes"); | ||||

109 | 110 | | |||

110 | static cl::opt<bool> | 111 | static cl::opt<bool> | ||

111 | Delinearize("da-delinearize", cl::init(false), cl::Hidden, cl::ZeroOrMore, | 112 | Delinearize("da-delinearize", cl::init(false), cl::Hidden, cl::ZeroOrMore, | ||

112 | cl::desc("Try to delinearize array references.")); | 113 | cl::desc("Try to delinearize array references.")); | ||

113 | 114 | | |||

114 | //===----------------------------------------------------------------------===// | 115 | //===----------------------------------------------------------------------===// | ||

115 | // basics | 116 | // basics | ||

116 | 117 | | |||

▲ Show 20 Lines • Show All 3176 Lines • ▼ Show 20 Line(s) | 3293 | for (unsigned VI : BV.set_bits()) { | |||

3293 | dbgs() << VI; | 3294 | dbgs() << VI; | ||

3294 | if (BV.find_next(VI) >= 0) | 3295 | if (BV.find_next(VI) >= 0) | ||

3295 | dbgs() << ' '; | 3296 | dbgs() << ' '; | ||

3296 | } | 3297 | } | ||

3297 | dbgs() << "}\n"; | 3298 | dbgs() << "}\n"; | ||

3298 | } | 3299 | } | ||

3299 | #endif | 3300 | #endif | ||

3300 | 3301 | | |||

3302 | // Returns true if expression S is proven to be not loop invariant in loop | ||||

3303 | // L. This stronger than just checking !SE->isLoopInvariant(), as | ||||

3304 | // isLoopInvariant only returns true if the expression can be proven to be | ||||

3305 | // loop invariant, but there are loop invariant expression that isLoopInvariant | ||||

3306 | // might not be able to prove. | ||||

3307 | static bool IsNotLoopInvariant(const SCEV *S, const Loop *L, | ||||

3308 | ScalarEvolution *SE) { | ||||

3309 | switch (static_cast<SCEVTypes>(S->getSCEVType())) { | ||||

3310 | case scConstant: | ||||

3311 | return false; | ||||

3312 | case scTruncate: | ||||

3313 | case scZeroExtend: | ||||

3314 | case scSignExtend: | ||||

3315 | return IsNotLoopInvariant(cast<SCEVCastExpr>(S)->getOperand(), L, SE); | ||||

3316 | case scAddRecExpr: { | ||||

3317 | const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(S); | ||||

3318 | // If L is the addrec's loop and it has a non-zero step, it is not loop | ||||

3319 | // invariant. | ||||

3320 | if (AR->getLoop() == L) | ||||

3321 | return SE->isKnownNonZero(AR->getStepRecurrence(*SE)); | ||||

3322 | return false; | ||||

3323 | } | ||||

3324 | case scAddExpr: | ||||

3325 | // AddExpr are not loop invariant if any of the terms is not loop invariant. | ||||

3326 | return any_of(cast<SCEVNAryExpr>(S)->operands(), [L, SE](const SCEV *S) { | ||||

3327 | return IsNotLoopInvariant(S, L, SE); | ||||

3328 | }); | ||||

3329 | case scMulExpr: { | ||||

3330 | // MulExpr is are not loop invariant if any of the terms is not loop | ||||

3331 | // invariant and we do not multiply with 0. | ||||

3332 | bool AnyNotInvariant = false; | ||||

3333 | bool AllInvariantNonZero = true; | ||||

3334 | for (const SCEV *Op : cast<SCEVNAryExpr>(S)->operands()) { | ||||

3335 | bool NotInvariant = IsNotLoopInvariant(Op, L, SE); | ||||

3336 | AnyNotInvariant |= NotInvariant; | ||||

3337 | AllInvariantNonZero &= NotInvariant || SE->isKnownNonZero(Op); | ||||

3338 | } | ||||

3339 | | ||||

3340 | return AllInvariantNonZero && AnyNotInvariant; | ||||

3341 | } | ||||

3342 | default: | ||||

3343 | return false; | ||||

3344 | } | ||||

3345 | } | ||||

3346 | | ||||

3301 | // depends - | 3347 | // depends - | ||

3302 | // Returns NULL if there is no dependence. | 3348 | // Returns NULL if there is no dependence. | ||

3303 | // Otherwise, return a Dependence with as many details as possible. | 3349 | // Otherwise, return a Dependence with as many details as possible. | ||

3304 | // Corresponds to Section 3.1 in the paper | 3350 | // Corresponds to Section 3.1 in the paper | ||

3305 | // | 3351 | // | ||

3306 | // Practical Dependence Testing | 3352 | // Practical Dependence Testing | ||

3307 | // Goff, Kennedy, Tseng | 3353 | // Goff, Kennedy, Tseng | ||

3308 | // PLDI 1991 | 3354 | // PLDI 1991 | ||

▲ Show 20 Lines • Show All 338 Lines • ▼ Show 20 Line(s) | 3692 | if (SJ > CommonLevels) | |||

3647 | break; | 3693 | break; | ||

3648 | updateDirection(Result.DV[SJ - 1], Constraints[SJ]); | 3694 | updateDirection(Result.DV[SJ - 1], Constraints[SJ]); | ||

3649 | if (Result.DV[SJ - 1].Direction == Dependence::DVEntry::NONE) | 3695 | if (Result.DV[SJ - 1].Direction == Dependence::DVEntry::NONE) | ||

3650 | return nullptr; | 3696 | return nullptr; | ||

3651 | } | 3697 | } | ||

3652 | } | 3698 | } | ||

3653 | } | 3699 | } | ||

3654 | 3700 | | |||

3701 | // Try to conclude DVEntry::EQ, in case Src and Dst access the same memory | ||||

3702 | // location for loop dependent locations in the same loop. | ||||

3703 | Loop *SrcL = LI->getLoopFor(Src->getParent()); | ||||

3704 | Loop *DstL = LI->getLoopFor(Dst->getParent()); | ||||

3705 | if (SrcL == DstL && IsNotLoopInvariant(SrcSCEV, SrcL, SE) && | ||||

3706 | IsNotLoopInvariant(DstSCEV, DstL, SE)) { | ||||

3707 | const SCEV *DiffSCEV = SE->getMinusSCEV(SrcSCEV, DstSCEV); | ||||

tvvikram: Even I am facing a similar issue. What happens if the access is something like A[(i + j) * n] =… | |||||

Not Done ReplyRight, thanks for having a look! fhahn: Right, thanks for having a look! `isLoopInvariant` is not enough, looks like we need something… | |||||

3708 | if (DiffSCEV->isZero()) { | ||||

3709 | for (unsigned i = 0; i < Result.Levels; i++) | ||||

3710 | Result.DV[i].Direction = Dependence::DVEntry::EQ; | ||||

3711 | SymbolicEQSuccesses++; | ||||

3712 | } | ||||

3713 | } | ||||

3714 | | ||||

3655 | // Make sure the Scalar flags are set correctly. | 3715 | // Make sure the Scalar flags are set correctly. | ||

3656 | SmallBitVector CompleteLoops(MaxLevels + 1); | 3716 | SmallBitVector CompleteLoops(MaxLevels + 1); | ||

3657 | for (unsigned SI = 0; SI < Pairs; ++SI) | 3717 | for (unsigned SI = 0; SI < Pairs; ++SI) | ||

3658 | CompleteLoops |= Pair[SI].Loops; | 3718 | CompleteLoops |= Pair[SI].Loops; | ||

3659 | for (unsigned II = 1; II <= CommonLevels; ++II) | 3719 | for (unsigned II = 1; II <= CommonLevels; ++II) | ||

3660 | if (CompleteLoops[II]) | 3720 | if (CompleteLoops[II]) | ||

3661 | Result.DV[II - 1].Scalar = false; | 3721 | Result.DV[II - 1].Scalar = false; | ||

3662 | 3722 | | |||

▲ Show 20 Lines • Show All 255 Lines • Show Last 20 Lines |

Even I am facing a similar issue. What happens if the access is something like A[(i + j) * n] = A[(i + j) * n] + 10, where n can be 0. In this case, the dependence would be "*" and not "=" right? Maybe just checking if difference is zero wouldn't be enough but traversing the SCEV to see that it is simple/understandable would be necessary.