// //
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "da"
-
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/InstIterator.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"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
+#define DEBUG_TYPE "da"
+
//===----------------------------------------------------------------------===//
// statistics
DstI != DstE; ++DstI) {
if (isa<StoreInst>(*DstI) || isa<LoadInst>(*DstI)) {
OS << "da analyze - ";
- if (Dependence *D = DA->depends(&*SrcI, &*DstI, true)) {
+ if (auto D = DA->depends(&*SrcI, &*DstI, true)) {
D->dump(OS);
for (unsigned Level = 1; Level <= D->getLevels(); Level++) {
if (D->isSplitable(Level)) {
OS << "da analyze - split level = " << Level;
- OS << ", iteration = " << *DA->getSplitIteration(D, Level);
+ OS << ", iteration = " << *DA->getSplitIteration(*D, Level);
OS << "!\n";
}
}
- delete D;
}
else
OS << "none!\n";
Levels(CommonLevels),
LoopIndependent(PossiblyLoopIndependent) {
Consistent = true;
- DV = CommonLevels ? new DVEntry[CommonLevels] : NULL;
+ DV = CommonLevels ? new DVEntry[CommonLevels] : nullptr;
}
// The rest are simple getters that hide the implementation.
if (StoreInst *SI = dyn_cast<StoreInst>(I))
return SI->getPointerOperand();
llvm_unreachable("Value is not load or store instruction");
- return 0;
+ return nullptr;
}
const SCEV *UB = SE->getBackedgeTakenCount(L);
return SE->getNoopOrZeroExtend(UB, T);
}
- return NULL;
+ return nullptr;
}
) const {
if (const SCEV *UB = collectUpperBound(L, T))
return dyn_cast<SCEVConstant>(UB);
- return NULL;
+ return nullptr;
}
if (const SCEVConstant *Constant = dyn_cast<SCEVConstant>(Product->getOperand(Op)))
return Constant;
}
- return NULL;
+ return nullptr;
}
CoefficientInfo *B,
BoundInfo *Bound,
unsigned K) const {
- Bound[K].Lower[Dependence::DVEntry::ALL] = NULL; // Default value = -infinity.
- Bound[K].Upper[Dependence::DVEntry::ALL] = NULL; // Default value = +infinity.
+ Bound[K].Lower[Dependence::DVEntry::ALL] = nullptr; // Default value = -infinity.
+ Bound[K].Upper[Dependence::DVEntry::ALL] = nullptr; // Default value = +infinity.
if (Bound[K].Iterations) {
Bound[K].Lower[Dependence::DVEntry::ALL] =
SE->getMulExpr(SE->getMinusSCEV(A[K].NegPart, B[K].PosPart),
CoefficientInfo *B,
BoundInfo *Bound,
unsigned K) const {
- Bound[K].Lower[Dependence::DVEntry::EQ] = NULL; // Default value = -infinity.
- Bound[K].Upper[Dependence::DVEntry::EQ] = NULL; // Default value = +infinity.
+ Bound[K].Lower[Dependence::DVEntry::EQ] = nullptr; // Default value = -infinity.
+ Bound[K].Upper[Dependence::DVEntry::EQ] = nullptr; // Default value = +infinity.
if (Bound[K].Iterations) {
const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff);
const SCEV *NegativePart = getNegativePart(Delta);
CoefficientInfo *B,
BoundInfo *Bound,
unsigned K) const {
- Bound[K].Lower[Dependence::DVEntry::LT] = NULL; // Default value = -infinity.
- Bound[K].Upper[Dependence::DVEntry::LT] = NULL; // Default value = +infinity.
+ Bound[K].Lower[Dependence::DVEntry::LT] = nullptr; // Default value = -infinity.
+ Bound[K].Upper[Dependence::DVEntry::LT] = nullptr; // Default value = +infinity.
if (Bound[K].Iterations) {
const SCEV *Iter_1 =
SE->getMinusSCEV(Bound[K].Iterations,
CoefficientInfo *B,
BoundInfo *Bound,
unsigned K) const {
- Bound[K].Lower[Dependence::DVEntry::GT] = NULL; // Default value = -infinity.
- Bound[K].Upper[Dependence::DVEntry::GT] = NULL; // Default value = +infinity.
+ Bound[K].Lower[Dependence::DVEntry::GT] = nullptr; // Default value = -infinity.
+ Bound[K].Upper[Dependence::DVEntry::GT] = nullptr; // Default value = +infinity.
if (Bound[K].Iterations) {
const SCEV *Iter_1 =
SE->getMinusSCEV(Bound[K].Iterations,
CI[K].Coeff = Zero;
CI[K].PosPart = Zero;
CI[K].NegPart = Zero;
- CI[K].Iterations = NULL;
+ CI[K].Iterations = nullptr;
}
while (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Subscript)) {
const Loop *L = AddRec->getLoop();
if (Bound[K].Lower[Bound[K].Direction])
Sum = SE->getAddExpr(Sum, Bound[K].Lower[Bound[K].Direction]);
else
- Sum = NULL;
+ Sum = nullptr;
}
return Sum;
}
if (Bound[K].Upper[Bound[K].Direction])
Sum = SE->getAddExpr(Sum, Bound[K].Upper[Bound[K].Direction]);
else
- Sum = NULL;
+ Sum = nullptr;
}
return Sum;
}
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),
- AddRec->getLoop(),
- AddRec->getNoWrapFlags());
+ return SE->getAddRecExpr(AddRec, Value, TargetLoop, SCEV::FlagAnyWrap);
+ return SE->getAddRecExpr(
+ addToCoefficient(AddRec->getStart(), TargetLoop, Value),
+ AddRec->getStepRecurrence(*SE), AddRec->getLoop(),
+ AddRec->getNoWrapFlags());
}
}
else if (CurConstraint.isLine()) {
Level.Scalar = false;
- Level.Distance = NULL;
+ Level.Distance = nullptr;
// direction should be accurate
}
else if (CurConstraint.isPoint()) {
Level.Scalar = false;
- Level.Distance = NULL;
+ Level.Distance = nullptr;
unsigned NewDirection = Dependence::DVEntry::NONE;
if (!isKnownPredicate(CmpInst::ICMP_NE,
CurConstraint.getY(),
/// source and destination array references are recurrences on a nested loop,
/// this function flattens the nested recurrences into separate recurrences
/// for each loop level.
-bool
-DependenceAnalysis::tryDelinearize(const SCEV *SrcSCEV, const SCEV *DstSCEV,
- SmallVectorImpl<Subscript> &Pair) const {
+bool DependenceAnalysis::tryDelinearize(const SCEV *SrcSCEV,
+ const SCEV *DstSCEV,
+ SmallVectorImpl<Subscript> &Pair,
+ const SCEV *ElementSize) const {
+ const SCEVUnknown *SrcBase =
+ dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcSCEV));
+ const SCEVUnknown *DstBase =
+ dyn_cast<SCEVUnknown>(SE->getPointerBase(DstSCEV));
+
+ if (!SrcBase || !DstBase || SrcBase != DstBase)
+ return false;
+
+ SrcSCEV = SE->getMinusSCEV(SrcSCEV, SrcBase);
+ DstSCEV = SE->getMinusSCEV(DstSCEV, DstBase);
+
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);
+ // First step: collect parametric terms in both array references.
+ SmallVector<const SCEV *, 4> Terms;
+ SrcAR->collectParametricTerms(*SE, Terms);
+ DstAR->collectParametricTerms(*SE, Terms);
- int size = SrcSubscripts.size();
- // Fail when there is only a subscript: that's a linearized access function.
- if (size < 2)
- return false;
+ // Second step: find subscript sizes.
+ SmallVector<const SCEV *, 4> Sizes;
+ SE->findArrayDimensions(Terms, Sizes, ElementSize);
- int dstSize = DstSubscripts.size();
- // Fail when the number of subscripts in Src and Dst differ.
- if (size != dstSize)
+ // Third step: compute the access functions for each subscript.
+ SmallVector<const SCEV *, 4> SrcSubscripts, DstSubscripts;
+ SrcAR->computeAccessFunctions(*SE, SrcSubscripts, Sizes);
+ DstAR->computeAccessFunctions(*SE, DstSubscripts, Sizes);
+
+ // Fail when there is only a subscript: that's a linearized access function.
+ if (SrcSubscripts.size() < 2 || DstSubscripts.size() < 2 ||
+ SrcSubscripts.size() != DstSubscripts.size())
return false;
- // Fail when the size of any of the subscripts in Src and Dst differs: the
- // dependence analysis assumes that elements in the same array have same size.
- // SCEV delinearization does not have a context based on which it would decide
- // globally the size of subscripts that would best fit all the array accesses.
- for (int i = 0; i < size; ++i)
- if (SrcSizes[i] != DstSizes[i])
- return false;
+ int size = SrcSubscripts.size();
-#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
+ DEBUG({
+ dbgs() << "\nSrcSubscripts: ";
+ for (int i = 0; i < size; i++)
+ dbgs() << *SrcSubscripts[i];
+ dbgs() << "\nDstSubscripts: ";
+ for (int i = 0; i < size; i++)
+ dbgs() << *DstSubscripts[i];
+ });
// The delinearization transforms a single-subscript MIV dependence test into
// a multi-subscript SIV dependence test that is easier to compute. So we
//
// Care is required to keep the routine below, getSplitIteration(),
// up to date with respect to this routine.
-Dependence *DependenceAnalysis::depends(Instruction *Src,
- Instruction *Dst,
- bool PossiblyLoopIndependent) {
+std::unique_ptr<Dependence>
+DependenceAnalysis::depends(Instruction *Src, Instruction *Dst,
+ bool PossiblyLoopIndependent) {
if (Src == Dst)
PossiblyLoopIndependent = false;
if ((!Src->mayReadFromMemory() && !Src->mayWriteToMemory()) ||
(!Dst->mayReadFromMemory() && !Dst->mayWriteToMemory()))
// if both instructions don't reference memory, there's no dependence
- return NULL;
+ return nullptr;
if (!isLoadOrStore(Src) || !isLoadOrStore(Dst)) {
// can only analyze simple loads and stores, i.e., no calls, invokes, etc.
DEBUG(dbgs() << "can only handle simple loads and stores\n");
- return new Dependence(Src, Dst);
+ return make_unique<Dependence>(Src, Dst);
}
Value *SrcPtr = getPointerOperand(Src);
case AliasAnalysis::PartialAlias:
// cannot analyse objects if we don't understand their aliasing.
DEBUG(dbgs() << "can't analyze may or partial alias\n");
- return new Dependence(Src, Dst);
+ return make_unique<Dependence>(Src, Dst);
case AliasAnalysis::NoAlias:
// If the objects noalias, they are distinct, accesses are independent.
DEBUG(dbgs() << "no alias\n");
- return NULL;
+ return nullptr;
case AliasAnalysis::MustAlias:
break; // The underlying objects alias; test accesses for dependence.
}
}
if (Delinearize && Pairs == 1 && CommonLevels > 1 &&
- tryDelinearize(Pair[0].Src, Pair[0].Dst, Pair)) {
+ tryDelinearize(Pair[0].Src, Pair[0].Dst, Pair, SE->getElementSize(Src))) {
DEBUG(dbgs() << " delinerized GEP\n");
Pairs = Pair.size();
}
case Subscript::ZIV:
DEBUG(dbgs() << ", ZIV\n");
if (testZIV(Pair[SI].Src, Pair[SI].Dst, Result))
- return NULL;
+ return nullptr;
break;
case Subscript::SIV: {
DEBUG(dbgs() << ", SIV\n");
unsigned Level;
- const SCEV *SplitIter = NULL;
+ const SCEV *SplitIter = nullptr;
if (testSIV(Pair[SI].Src, Pair[SI].Dst, Level,
Result, NewConstraint, SplitIter))
- return NULL;
+ return nullptr;
break;
}
case Subscript::RDIV:
DEBUG(dbgs() << ", RDIV\n");
if (testRDIV(Pair[SI].Src, Pair[SI].Dst, Result))
- return NULL;
+ return nullptr;
break;
case Subscript::MIV:
DEBUG(dbgs() << ", MIV\n");
if (testMIV(Pair[SI].Src, Pair[SI].Dst, Pair[SI].Loops, Result))
- return NULL;
+ return nullptr;
break;
default:
llvm_unreachable("subscript has unexpected classification");
DEBUG(dbgs() << "testing subscript " << SJ << ", SIV\n");
// SJ is an SIV subscript that's part of the current coupled group
unsigned Level;
- const SCEV *SplitIter = NULL;
+ const SCEV *SplitIter = nullptr;
DEBUG(dbgs() << "SIV\n");
if (testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level,
Result, NewConstraint, SplitIter))
- return NULL;
+ return nullptr;
ConstrainedLevels.set(Level);
if (intersectConstraints(&Constraints[Level], &NewConstraint)) {
if (Constraints[Level].isEmpty()) {
++DeltaIndependence;
- return NULL;
+ return nullptr;
}
Changed = true;
}
case Subscript::ZIV:
DEBUG(dbgs() << "ZIV\n");
if (testZIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
- return NULL;
+ return nullptr;
Mivs.reset(SJ);
break;
case Subscript::SIV:
if (Pair[SJ].Classification == Subscript::RDIV) {
DEBUG(dbgs() << "RDIV test\n");
if (testRDIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
- return NULL;
+ return nullptr;
// I don't yet understand how to propagate RDIV results
Mivs.reset(SJ);
}
if (Pair[SJ].Classification == Subscript::MIV) {
DEBUG(dbgs() << "MIV test\n");
if (testMIV(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops, Result))
- return NULL;
+ return nullptr;
}
else
llvm_unreachable("expected only MIV subscripts at this point");
SJ >= 0; SJ = ConstrainedLevels.find_next(SJ)) {
updateDirection(Result.DV[SJ - 1], Constraints[SJ]);
if (Result.DV[SJ - 1].Direction == Dependence::DVEntry::NONE)
- return NULL;
+ return nullptr;
}
}
}
}
}
if (AllEqual)
- return NULL;
+ return nullptr;
}
- FullDependence *Final = new FullDependence(Result);
- Result.DV = NULL;
- return Final;
+ auto Final = make_unique<FullDependence>(Result);
+ Result.DV = nullptr;
+ return std::move(Final);
}
//
// breaks the dependence and allows us to vectorize/parallelize
// both loops.
-const SCEV *DependenceAnalysis::getSplitIteration(const Dependence *Dep,
+const SCEV *DependenceAnalysis::getSplitIteration(const Dependence &Dep,
unsigned SplitLevel) {
- assert(Dep && "expected a pointer to a Dependence");
- assert(Dep->isSplitable(SplitLevel) &&
+ assert(Dep.isSplitable(SplitLevel) &&
"Dep should be splitable at SplitLevel");
- Instruction *Src = Dep->getSrc();
- Instruction *Dst = Dep->getDst();
+ Instruction *Src = Dep.getSrc();
+ Instruction *Dst = Dep.getDst();
assert(Src->mayReadFromMemory() || Src->mayWriteToMemory());
assert(Dst->mayReadFromMemory() || Dst->mayWriteToMemory());
assert(isLoadOrStore(Src));
}
if (Delinearize && Pairs == 1 && CommonLevels > 1 &&
- tryDelinearize(Pair[0].Src, Pair[0].Dst, Pair)) {
+ tryDelinearize(Pair[0].Src, Pair[0].Dst, Pair, SE->getElementSize(Src))) {
DEBUG(dbgs() << " delinerized GEP\n");
Pairs = Pair.size();
}
switch (Pair[SI].Classification) {
case Subscript::SIV: {
unsigned Level;
- const SCEV *SplitIter = NULL;
+ const SCEV *SplitIter = nullptr;
(void) testSIV(Pair[SI].Src, Pair[SI].Dst, Level,
Result, NewConstraint, SplitIter);
if (Level == SplitLevel) {
- assert(SplitIter != NULL);
+ assert(SplitIter != nullptr);
return SplitIter;
}
break;
for (int SJ = Sivs.find_first(); SJ >= 0; SJ = Sivs.find_next(SJ)) {
// SJ is an SIV subscript that's part of the current coupled group
unsigned Level;
- const SCEV *SplitIter = NULL;
+ const SCEV *SplitIter = nullptr;
(void) testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level,
Result, NewConstraint, SplitIter);
if (Level == SplitLevel && SplitIter)
}
}
llvm_unreachable("somehow reached end of routine");
- return NULL;
+ return nullptr;
}
projects / oota-llvm.git / blobdiff