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! isLoopInvariant is not enough, looks like we need something like "may be loop invariant" :) I'll update the patch. 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.