// Both of these are conservative weaknesses;
// that is, not a source of correctness problems.
//
-// The implementation depends on the GEP instruction to
-// differentiate subscripts. Since Clang linearizes subscripts
-// for most arrays, we give up some precision (though the existing MIV tests
-// will help). We trust that the GEP instruction will eventually be extended.
-// In the meantime, we should explore Maslov's ideas about delinearization.
+// The implementation depends on the GEP instruction to differentiate
+// subscripts. Since Clang linearizes some array subscripts, the dependence
+// analysis is using SCEV->delinearize to recover the representation of multiple
+// subscripts, and thus avoid the more expensive and less precise MIV tests. The
+// delinearization is controlled by the flag -da-delinearize.
//
// We should pay some careful attention to the possibility of integer overflow
// in the implementation of the various tests. This could happen with Add,
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/ADT/Statistic.h"
-#include "llvm/Operator.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
-#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/Operator.h"
+#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/InstIterator.h"
STATISTIC(BanerjeeIndependence, "Banerjee independence");
STATISTIC(BanerjeeSuccesses, "Banerjee successes");
+static cl::opt<bool>
+Delinearize("da-delinearize", cl::init(false), cl::Hidden, cl::ZeroOrMore,
+ cl::desc("Try to delinearize array references."));
+
//===----------------------------------------------------------------------===//
// basics
APInt Xr = Xtop; // though they're just going to be overwritten
APInt::sdivrem(Xtop, Xbot, Xq, Xr);
APInt Yq = Ytop;
- APInt Yr = Ytop;;
+ APInt Yr = Ytop;
APInt::sdivrem(Ytop, Ybot, Yq, Yr);
if (Xr != 0 || Yr != 0) {
X->setEmpty();
else if (isInput())
OS << "input";
unsigned Levels = getLevels();
- if (Levels) {
- OS << " [";
- for (unsigned II = 1; II <= Levels; ++II) {
- if (isSplitable(II))
- Splitable = true;
- if (isPeelFirst(II))
- OS << 'p';
- const SCEV *Distance = getDistance(II);
- if (Distance)
- OS << *Distance;
- else if (isScalar(II))
- OS << "S";
+ OS << " [";
+ for (unsigned II = 1; II <= Levels; ++II) {
+ if (isSplitable(II))
+ Splitable = true;
+ if (isPeelFirst(II))
+ OS << 'p';
+ const SCEV *Distance = getDistance(II);
+ if (Distance)
+ OS << *Distance;
+ else if (isScalar(II))
+ OS << "S";
+ else {
+ unsigned Direction = getDirection(II);
+ if (Direction == DVEntry::ALL)
+ OS << "*";
else {
- unsigned Direction = getDirection(II);
- if (Direction == DVEntry::ALL)
- OS << "*";
- else {
- if (Direction & DVEntry::LT)
- OS << "<";
- if (Direction & DVEntry::EQ)
- OS << "=";
- if (Direction & DVEntry::GT)
- OS << ">";
- }
+ if (Direction & DVEntry::LT)
+ OS << "<";
+ if (Direction & DVEntry::EQ)
+ OS << "=";
+ if (Direction & DVEntry::GT)
+ OS << ">";
}
- if (isPeelLast(II))
- OS << 'p';
- if (II < Levels)
- OS << " ";
}
- if (isLoopIndependent())
- OS << "|<";
- OS << "]";
- if (Splitable)
- OS << " splitable";
+ if (isPeelLast(II))
+ OS << 'p';
+ if (II < Levels)
+ OS << " ";
}
+ if (isLoopIndependent())
+ OS << "|<";
+ OS << "]";
+ if (Splitable)
+ OS << " splitable";
}
OS << "!\n";
}
//
// Program 2.1, page 29.
// Computes the GCD of AM and BM.
-// Also finds a solution to the equation ax - by = gdc(a, b).
-// Returns true iff the gcd divides Delta.
+// Also finds a solution to the equation ax - by = gcd(a, b).
+// Returns true if dependence disproved; i.e., gcd does not divide Delta.
static
bool findGCD(unsigned Bits, APInt AM, APInt BM, APInt Delta,
APInt &G, APInt &X, APInt &Y) {
//
// It occurs to me that the presence of loop-invariant variables
// changes the nature of the test from "greatest common divisor"
-// to "a common divisor!"
+// to "a common divisor".
bool DependenceAnalysis::gcdMIVtest(const SCEV *Src,
const SCEV *Dst,
FullDependence &Result) const {
AddRec->getLoop(),
AddRec->getNoWrapFlags());
}
+ if (SE->isLoopInvariant(AddRec, TargetLoop))
+ return SE->getAddRecExpr(AddRec,
+ Value,
+ TargetLoop,
+ SCEV::FlagAnyWrap);
return SE->getAddRecExpr(addToCoefficient(AddRec->getStart(),
TargetLoop, Value),
AddRec->getStepRecurrence(*SE),
bool DependenceAnalysis::propagate(const SCEV *&Src,
const SCEV *&Dst,
SmallBitVector &Loops,
- SmallVector<Constraint, 4> &Constraints,
+ SmallVectorImpl<Constraint> &Constraints,
bool &Consistent) {
bool Result = false;
for (int LI = Loops.find_first(); LI >= 0; LI = Loops.find_next(LI)) {
llvm_unreachable("constraint has unexpected kind");
}
+/// Check if we can delinearize the subscripts. If the SCEVs representing the
+/// source and destination array references are recurrences on a nested loop,
+/// this function flattens the nested recurrences into seperate recurrences
+/// for each loop level.
+bool
+DependenceAnalysis::tryDelinearize(const SCEV *SrcSCEV, const SCEV *DstSCEV,
+ SmallVectorImpl<Subscript> &Pair) const {
+ const SCEVAddRecExpr *SrcAR = dyn_cast<SCEVAddRecExpr>(SrcSCEV);
+ const SCEVAddRecExpr *DstAR = dyn_cast<SCEVAddRecExpr>(DstSCEV);
+ if (!SrcAR || !DstAR || !SrcAR->isAffine() || !DstAR->isAffine())
+ return false;
+
+ SmallVector<const SCEV *, 4> SrcSubscripts, DstSubscripts, SrcSizes, DstSizes;
+ SrcAR->delinearize(*SE, SrcSubscripts, SrcSizes);
+ DstAR->delinearize(*SE, DstSubscripts, DstSizes);
+
+ int size = SrcSubscripts.size();
+ int dstSize = DstSubscripts.size();
+ if (size != dstSize || size < 2)
+ return false;
+
+#ifndef NDEBUG
+ DEBUG(errs() << "\nSrcSubscripts: ");
+ for (int i = 0; i < size; i++)
+ DEBUG(errs() << *SrcSubscripts[i]);
+ DEBUG(errs() << "\nDstSubscripts: ");
+ for (int i = 0; i < size; i++)
+ DEBUG(errs() << *DstSubscripts[i]);
+#endif
+
+ // The delinearization transforms a single-subscript MIV dependence test into
+ // a multi-subscript SIV dependence test that is easier to compute. So we
+ // resize Pair to contain as many pairs of subscripts as the delinearization
+ // has found, and then initialize the pairs following the delinearization.
+ Pair.resize(size);
+ for (int i = 0; i < size; ++i) {
+ Pair[i].Src = SrcSubscripts[i];
+ Pair[i].Dst = DstSubscripts[i];
+
+ // FIXME: we should record the bounds SrcSizes[i] and DstSizes[i] that the
+ // delinearization has found, and add these constraints to the dependence
+ // check to avoid memory accesses overflow from one dimension into another.
+ // This is related to the problem of determining the existence of data
+ // dependences in array accesses using a different number of subscripts: in
+ // C one can access an array A[100][100]; as A[0][9999], *A[9999], etc.
+ }
+
+ return true;
+}
//===----------------------------------------------------------------------===//
Pair[0].Dst = DstSCEV;
}
+ if (Delinearize && Pairs == 1 && CommonLevels > 1 &&
+ tryDelinearize(Pair[0].Src, Pair[0].Dst, Pair)) {
+ DEBUG(dbgs() << " delinerized GEP\n");
+ Pairs = Pair.size();
+ }
+
for (unsigned P = 0; P < Pairs; ++P) {
Pair[P].Loops.resize(MaxLevels + 1);
Pair[P].GroupLoops.resize(MaxLevels + 1);
}
}
- // make sure Scalar flags are set correctly
+ // Make sure the Scalar flags are set correctly.
SmallBitVector CompleteLoops(MaxLevels + 1);
for (unsigned SI = 0; SI < Pairs; ++SI)
CompleteLoops |= Pair[SI].Loops;
if (CompleteLoops[II])
Result.DV[II - 1].Scalar = false;
- // make sure loopIndepent flag is set correctly
if (PossiblyLoopIndependent) {
+ // Make sure the LoopIndependent flag is set correctly.
+ // All directions must include equal, otherwise no
+ // loop-independent dependence is possible.
for (unsigned II = 1; II <= CommonLevels; ++II) {
if (!(Result.getDirection(II) & Dependence::DVEntry::EQ)) {
Result.LoopIndependent = false;
}
}
}
+ else {
+ // On the other hand, if all directions are equal and there's no
+ // loop-independent dependence possible, then no dependence exists.
+ bool AllEqual = true;
+ for (unsigned II = 1; II <= CommonLevels; ++II) {
+ if (Result.getDirection(II) != Dependence::DVEntry::EQ) {
+ AllEqual = false;
+ break;
+ }
+ }
+ if (AllEqual)
+ return NULL;
+ }
FullDependence *Final = new FullDependence(Result);
Result.DV = NULL;
Pair[0].Dst = DstSCEV;
}
+ if (Delinearize && Pairs == 1 && CommonLevels > 1 &&
+ tryDelinearize(Pair[0].Src, Pair[0].Dst, Pair)) {
+ DEBUG(dbgs() << " delinerized GEP\n");
+ Pairs = Pair.size();
+ }
+
for (unsigned P = 0; P < Pairs; ++P) {
Pair[P].Loops.resize(MaxLevels + 1);
Pair[P].GroupLoops.resize(MaxLevels + 1);
projects / oota-llvm.git / blobdiff