Page MenuHomePhabricator
Differential D46201 Diff 149977 lib/Analysis/DependenceAnalysis.cpp

Changeset View

Standalone View

View Options

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);
tvvikramUnsubmitted
Not Done
ReplyInline Actions

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.

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

Right, 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