summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/Analysis/ScalarEvolutionExpressions.h18
-rw-r--r--lib/Analysis/Delinearization.cpp14
-rw-r--r--lib/Analysis/DependenceAnalysis.cpp21
-rw-r--r--lib/Analysis/ScalarEvolution.cpp35
4 files changed, 49 insertions, 39 deletions
diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h
index b468fcd025..01b034f8a0 100644
--- a/include/llvm/Analysis/ScalarEvolutionExpressions.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h
@@ -362,14 +362,12 @@ namespace llvm {
SmallVectorImpl<const SCEV *> &Terms) const;
/// Return in Subscripts the access functions for each dimension in Sizes.
- const SCEV *
- computeAccessFunctions(ScalarEvolution &SE,
- SmallVectorImpl<const SCEV *> &Subscripts,
- SmallVectorImpl<const SCEV *> &Sizes) const;
+ void computeAccessFunctions(ScalarEvolution &SE,
+ SmallVectorImpl<const SCEV *> &Subscripts,
+ SmallVectorImpl<const SCEV *> &Sizes) const;
/// Split this SCEVAddRecExpr into two vectors of SCEVs representing the
- /// subscripts and sizes of an array access. Returns the remainder of the
- /// delinearization that is the offset start of the array.
+ /// subscripts and sizes of an array access.
///
/// The delinearization is a 3 step process: the first two steps compute the
/// sizes of each subscript and the third step computes the access functions
@@ -432,10 +430,10 @@ namespace llvm {
/// The subscript of the outermost dimension is the Quotient: [j+k].
///
/// Overall, we have: A[][n][m], and the access function: A[j+k][2i][5i].
- const SCEV *delinearize(ScalarEvolution &SE,
- SmallVectorImpl<const SCEV *> &Subscripts,
- SmallVectorImpl<const SCEV *> &Sizes,
- const SCEV *ElementSize) const;
+ void delinearize(ScalarEvolution &SE,
+ SmallVectorImpl<const SCEV *> &Subscripts,
+ SmallVectorImpl<const SCEV *> &Sizes,
+ const SCEV *ElementSize) const;
};
//===--------------------------------------------------------------------===//
diff --git a/lib/Analysis/Delinearization.cpp b/lib/Analysis/Delinearization.cpp
index 6c8702787d..9334cebe18 100644
--- a/lib/Analysis/Delinearization.cpp
+++ b/lib/Analysis/Delinearization.cpp
@@ -95,26 +95,34 @@ void Delinearization::print(raw_ostream &O, const Module *) const {
// Do not analyze memory accesses outside loops.
for (Loop *L = LI->getLoopFor(BB); L != nullptr; L = L->getParentLoop()) {
const SCEV *AccessFn = SE->getSCEVAtScope(getPointerOperand(*Inst), L);
+
+ const SCEVUnknown *BasePointer =
+ dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFn));
+ // Do not delinearize if we cannot find the base pointer.
+ if (!BasePointer)
+ break;
+ AccessFn = SE->getMinusSCEV(AccessFn, BasePointer);
const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(AccessFn);
// Do not try to delinearize memory accesses that are not AddRecs.
if (!AR)
break;
+
O << "\n";
O << "Inst:" << *Inst << "\n";
O << "In Loop with Header: " << L->getHeader()->getName() << "\n";
-
O << "AddRec: " << *AR << "\n";
SmallVector<const SCEV *, 3> Subscripts, Sizes;
- const SCEV *Res = AR->delinearize(*SE, Subscripts, Sizes, SE->getElementSize(Inst));
+ AR->delinearize(*SE, Subscripts, Sizes, SE->getElementSize(Inst));
if (Subscripts.size() == 0 || Sizes.size() == 0 ||
Subscripts.size() != Sizes.size()) {
O << "failed to delinearize\n";
continue;
}
- O << "Base offset: " << *Res << "\n";
+
+ O << "Base offset: " << *BasePointer << "\n";
O << "ArrayDecl[UnknownSize]";
int Size = Subscripts.size();
for (int i = 0; i < Size - 1; i++)
diff --git a/lib/Analysis/DependenceAnalysis.cpp b/lib/Analysis/DependenceAnalysis.cpp
index 33cb20685c..d0784f1e67 100644
--- a/lib/Analysis/DependenceAnalysis.cpp
+++ b/lib/Analysis/DependenceAnalysis.cpp
@@ -3184,6 +3184,17 @@ 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())
@@ -3200,20 +3211,14 @@ bool DependenceAnalysis::tryDelinearize(const SCEV *SrcSCEV,
// Third step: compute the access functions for each subscript.
SmallVector<const SCEV *, 4> SrcSubscripts, DstSubscripts;
- const SCEV *RemainderS = SrcAR->computeAccessFunctions(*SE, SrcSubscripts, Sizes);
- const SCEV *RemainderD = DstAR->computeAccessFunctions(*SE, DstSubscripts, Sizes);
+ 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;
- // When the difference in remainders is different than a constant it might be
- // that the base address of the arrays is not the same.
- const SCEV *DiffRemainders = SE->getMinusSCEV(RemainderS, RemainderD);
- if (!isa<SCEVConstant>(DiffRemainders))
- return false;
-
int size = SrcSubscripts.size();
DEBUG({
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 4e4eb21433..35a825ad05 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -7458,16 +7458,15 @@ void ScalarEvolution::findArrayDimensions(SmallVectorImpl<const SCEV *> &Terms,
/// Third step of delinearization: compute the access functions for the
/// Subscripts based on the dimensions in Sizes.
-const SCEV *SCEVAddRecExpr::computeAccessFunctions(
+void SCEVAddRecExpr::computeAccessFunctions(
ScalarEvolution &SE, SmallVectorImpl<const SCEV *> &Subscripts,
SmallVectorImpl<const SCEV *> &Sizes) const {
// Early exit in case this SCEV is not an affine multivariate function.
if (Sizes.empty() || !this->isAffine())
- return nullptr;
+ return;
- const SCEV *Zero = SE.getConstant(this->getType(), 0);
- const SCEV *Res = this, *Remainder = Zero;
+ const SCEV *Res = this;
int Last = Sizes.size() - 1;
for (int i = Last; i >= 0; i--) {
const SCEV *Q, *R;
@@ -7488,10 +7487,12 @@ const SCEV *SCEVAddRecExpr::computeAccessFunctions(
if (i == Last) {
// Bail out if the remainder is too complex.
- if (isa<SCEVAddRecExpr>(R))
- return nullptr;
+ if (isa<SCEVAddRecExpr>(R)) {
+ Subscripts.clear();
+ Sizes.clear();
+ return;
+ }
- Remainder = R;
continue;
}
@@ -7510,7 +7511,6 @@ const SCEV *SCEVAddRecExpr::computeAccessFunctions(
for (const SCEV *S : Subscripts)
dbgs() << *S << "\n";
});
- return Remainder;
}
/// Splits the SCEV into two vectors of SCEVs representing the subscripts and
@@ -7562,27 +7562,28 @@ const SCEV *SCEVAddRecExpr::computeAccessFunctions(
/// asking for the SCEV of the memory access with respect to all enclosing
/// loops, calling SCEV->delinearize on that and printing the results.
-const SCEV *SCEVAddRecExpr::delinearize(
- ScalarEvolution &SE, SmallVectorImpl<const SCEV *> &Subscripts,
- SmallVectorImpl<const SCEV *> &Sizes, const SCEV *ElementSize) const {
+void SCEVAddRecExpr::delinearize(ScalarEvolution &SE,
+ SmallVectorImpl<const SCEV *> &Subscripts,
+ SmallVectorImpl<const SCEV *> &Sizes,
+ const SCEV *ElementSize) const {
// First step: collect parametric terms.
SmallVector<const SCEV *, 4> Terms;
collectParametricTerms(SE, Terms);
if (Terms.empty())
- return nullptr;
+ return;
// Second step: find subscript sizes.
SE.findArrayDimensions(Terms, Sizes, ElementSize);
if (Sizes.empty())
- return nullptr;
+ return;
// Third step: compute the access functions for each subscript.
- const SCEV *Remainder = computeAccessFunctions(SE, Subscripts, Sizes);
+ computeAccessFunctions(SE, Subscripts, Sizes);
- if (!Remainder || Subscripts.empty())
- return nullptr;
+ if (Subscripts.empty())
+ return;
DEBUG({
dbgs() << "succeeded to delinearize " << *this << "\n";
@@ -7595,8 +7596,6 @@ const SCEV *SCEVAddRecExpr::delinearize(
dbgs() << "[" << *S << "]";
dbgs() << "\n";
});
-
- return Remainder;
}
//===----------------------------------------------------------------------===//
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-04 09:47:52 +0000