Changeset View
Changeset View
Standalone View
Standalone View
lib/Analysis/DependenceAnalysis.cpp
Show First 20 Lines • Show All 100 Lines • ▼ Show 20 Lines | |||||
STATISTIC(DeltaIndependence, "Delta independence"); | STATISTIC(DeltaIndependence, "Delta independence"); | ||||
STATISTIC(DeltaPropagations, "Delta propagations"); | STATISTIC(DeltaPropagations, "Delta propagations"); | ||||
STATISTIC(GCDapplications, "GCD applications"); | STATISTIC(GCDapplications, "GCD applications"); | ||||
STATISTIC(GCDsuccesses, "GCD successes"); | STATISTIC(GCDsuccesses, "GCD successes"); | ||||
STATISTIC(GCDindependence, "GCD independence"); | STATISTIC(GCDindependence, "GCD independence"); | ||||
STATISTIC(BanerjeeApplications, "Banerjee applications"); | STATISTIC(BanerjeeApplications, "Banerjee applications"); | ||||
STATISTIC(BanerjeeIndependence, "Banerjee independence"); | STATISTIC(BanerjeeIndependence, "Banerjee independence"); | ||||
STATISTIC(BanerjeeSuccesses, "Banerjee successes"); | STATISTIC(BanerjeeSuccesses, "Banerjee successes"); | ||||
STATISTIC(SymbolicEQSuccesses, "Symbolic EQ successes"); | |||||
static cl::opt<bool> | static cl::opt<bool> | ||||
Delinearize("da-delinearize", cl::init(false), cl::Hidden, cl::ZeroOrMore, | Delinearize("da-delinearize", cl::init(false), cl::Hidden, cl::ZeroOrMore, | ||||
cl::desc("Try to delinearize array references.")); | cl::desc("Try to delinearize array references.")); | ||||
//===----------------------------------------------------------------------===// | //===----------------------------------------------------------------------===// | ||||
// basics | // basics | ||||
▲ Show 20 Lines • Show All 3,176 Lines • ▼ Show 20 Lines | for (unsigned VI : BV.set_bits()) { | ||||
dbgs() << VI; | dbgs() << VI; | ||||
if (BV.find_next(VI) >= 0) | if (BV.find_next(VI) >= 0) | ||||
dbgs() << ' '; | dbgs() << ' '; | ||||
} | } | ||||
dbgs() << "}\n"; | dbgs() << "}\n"; | ||||
} | } | ||||
#endif | #endif | ||||
// Returns true if expression S is proven to be not loop invariant in loop | |||||
// L. This stronger than just checking !SE->isLoopInvariant(), as | |||||
// isLoopInvariant only returns true if the expression can be proven to be | |||||
// loop invariant, but there are loop invariant expression that isLoopInvariant | |||||
// might not be able to prove. | |||||
static bool IsNotLoopInvariant(const SCEV *S, const Loop *L, | |||||
ScalarEvolution *SE) { | |||||
switch (static_cast<SCEVTypes>(S->getSCEVType())) { | |||||
case scConstant: | |||||
return false; | |||||
case scTruncate: | |||||
case scZeroExtend: | |||||
case scSignExtend: | |||||
return IsNotLoopInvariant(cast<SCEVCastExpr>(S)->getOperand(), L, SE); | |||||
case scAddRecExpr: { | |||||
const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(S); | |||||
// If L is the addrec's loop and it has a non-zero step, it is not loop | |||||
// invariant. | |||||
if (AR->getLoop() == L) | |||||
return SE->isKnownNonZero(AR->getStepRecurrence(*SE)); | |||||
return false; | |||||
} | |||||
case scAddExpr: | |||||
// AddExpr are not loop invariant if any of the terms is not loop invariant. | |||||
return any_of(cast<SCEVNAryExpr>(S)->operands(), [L, SE](const SCEV *S) { | |||||
return IsNotLoopInvariant(S, L, SE); | |||||
}); | |||||
case scMulExpr: { | |||||
// MulExpr is are not loop invariant if any of the terms is not loop | |||||
// invariant and we do not multiply with 0. | |||||
bool AnyNotInvariant = false; | |||||
bool AllInvariantNonZero = true; | |||||
for (const SCEV *Op : cast<SCEVNAryExpr>(S)->operands()) { | |||||
bool NotInvariant = IsNotLoopInvariant(Op, L, SE); | |||||
AnyNotInvariant |= NotInvariant; | |||||
AllInvariantNonZero &= NotInvariant || SE->isKnownNonZero(Op); | |||||
} | |||||
return AllInvariantNonZero && AnyNotInvariant; | |||||
} | |||||
default: | |||||
return false; | |||||
} | |||||
} | |||||
// depends - | // depends - | ||||
// Returns NULL if there is no dependence. | // Returns NULL if there is no dependence. | ||||
// Otherwise, return a Dependence with as many details as possible. | // Otherwise, return a Dependence with as many details as possible. | ||||
// Corresponds to Section 3.1 in the paper | // Corresponds to Section 3.1 in the paper | ||||
// | // | ||||
// Practical Dependence Testing | // Practical Dependence Testing | ||||
// Goff, Kennedy, Tseng | // Goff, Kennedy, Tseng | ||||
// PLDI 1991 | // PLDI 1991 | ||||
▲ Show 20 Lines • Show All 338 Lines • ▼ Show 20 Lines | for (unsigned SI : Coupled.set_bits()) { | ||||
break; | break; | ||||
updateDirection(Result.DV[SJ - 1], Constraints[SJ]); | updateDirection(Result.DV[SJ - 1], Constraints[SJ]); | ||||
if (Result.DV[SJ - 1].Direction == Dependence::DVEntry::NONE) | if (Result.DV[SJ - 1].Direction == Dependence::DVEntry::NONE) | ||||
return nullptr; | return nullptr; | ||||
} | } | ||||
} | } | ||||
} | } | ||||
// Try to conclude DVEntry::EQ, in case Src and Dst access the same memory | |||||
// location for loop dependent locations in the same loop. | |||||
Loop *SrcL = LI->getLoopFor(Src->getParent()); | |||||
Loop *DstL = LI->getLoopFor(Dst->getParent()); | |||||
if (SrcL == DstL && IsNotLoopInvariant(SrcSCEV, SrcL, SE) && | |||||
IsNotLoopInvariant(DstSCEV, DstL, SE)) { | |||||
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 ReplyInline ActionsRight, 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… | |||||
if (DiffSCEV->isZero()) { | |||||
for (unsigned i = 0; i < Result.Levels; i++) | |||||
Result.DV[i].Direction = Dependence::DVEntry::EQ; | |||||
SymbolicEQSuccesses++; | |||||
} | |||||
} | |||||
// Make sure the Scalar flags are set correctly. | // Make sure the Scalar flags are set correctly. | ||||
SmallBitVector CompleteLoops(MaxLevels + 1); | SmallBitVector CompleteLoops(MaxLevels + 1); | ||||
for (unsigned SI = 0; SI < Pairs; ++SI) | for (unsigned SI = 0; SI < Pairs; ++SI) | ||||
CompleteLoops |= Pair[SI].Loops; | CompleteLoops |= Pair[SI].Loops; | ||||
for (unsigned II = 1; II <= CommonLevels; ++II) | for (unsigned II = 1; II <= CommonLevels; ++II) | ||||
if (CompleteLoops[II]) | if (CompleteLoops[II]) | ||||
Result.DV[II - 1].Scalar = false; | Result.DV[II - 1].Scalar = false; | ||||
▲ 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.