ScopInfo: Add support for delinearizing fortran arrays
gfortran (and fortran in general?) does not compute the address of an array
element directly from the array sizes (e.g., %s0, %s1), but takes first the
maximum of the sizes and 0 (e.g., max(0, %s0)) before multiplying the resulting
value with the per-dimension array subscript expressions. To successfully
delinearize index expressions as we see them in fortran, we first filter 'smax'
expressions out of the SCEV expression, use them to guess array size parameters
and only then continue with the existing delinearization.
llvm-svn: 253995
diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp
index c776ef7..778ebff 100644
--- a/polly/lib/Analysis/ScopDetection.cpp
+++ b/polly/lib/Analysis/ScopDetection.cpp
@@ -487,11 +487,103 @@
MapInsnToMemAcc InsnToMemAcc;
+/// @brief Remove smax of smax(0, size) expressions from a SCEV expression and
+/// register the '...' components.
+///
+/// Array access expressions as they are generated by gfortran contain smax(0,
+/// size) expressions that confuse the 'normal' delinearization algorithm.
+/// However, if we extract such expressions before the normal delinearization
+/// takes place they can actually help to identify array size expressions in
+/// fortran accesses. For the subsequently following delinearization the smax(0,
+/// size) component can be replaced by just 'size'. This is correct as we will
+/// always add and verify the assumption that for all subscript expressions
+/// 'exp' the inequality 0 <= exp < size holds. Hence, we will also verify
+/// that 0 <= size, which means smax(0, size) == size.
+struct SCEVRemoveMax : public SCEVVisitor<SCEVRemoveMax, const SCEV *> {
+public:
+ static const SCEV *remove(ScalarEvolution &SE, const SCEV *Expr,
+ std::vector<const SCEV *> *Terms = nullptr) {
+
+ SCEVRemoveMax D(SE, Terms);
+ return D.visit(Expr);
+ }
+
+ SCEVRemoveMax(ScalarEvolution &SE, std::vector<const SCEV *> *Terms)
+ : SE(SE), Terms(Terms) {}
+
+ const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) { return Expr; }
+
+ const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
+ return Expr;
+ }
+
+ const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
+ return SE.getSignExtendExpr(visit(Expr->getOperand()), Expr->getType());
+ }
+
+ const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) { return Expr; }
+
+ const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) {
+ if (Expr->getOperand(0)->isZero()) {
+ auto Res = visit(Expr->getOperand(1));
+ if (Terms)
+ (*Terms).push_back(Res);
+ return Res;
+ }
+
+ return Expr;
+ }
+
+ const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) { return visit(Expr); }
+
+ const SCEV *visitUnknown(const SCEVUnknown *Expr) { return Expr; }
+
+ const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {
+ return Expr;
+ }
+
+ const SCEV *visitConstant(const SCEVConstant *Expr) { return Expr; }
+
+ const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
+ SmallVector<const SCEV *, 5> NewOps;
+ for (const SCEV *Op : Expr->operands())
+ NewOps.push_back(visit(Op));
+
+ return SE.getAddRecExpr(NewOps, Expr->getLoop(), Expr->getNoWrapFlags());
+ }
+
+ const SCEV *visitAddExpr(const SCEVAddExpr *Expr) {
+ SmallVector<const SCEV *, 5> NewOps;
+ for (const SCEV *Op : Expr->operands())
+ NewOps.push_back(visit(Op));
+
+ return SE.getAddExpr(NewOps);
+ }
+
+ const SCEV *visitMulExpr(const SCEVMulExpr *Expr) {
+ SmallVector<const SCEV *, 5> NewOps;
+ for (const SCEV *Op : Expr->operands())
+ NewOps.push_back(visit(Op));
+
+ return SE.getMulExpr(NewOps);
+ }
+
+private:
+ ScalarEvolution &SE;
+ std::vector<const SCEV *> *Terms;
+};
+
SmallVector<const SCEV *, 4>
ScopDetection::getDelinearizationTerms(DetectionContext &Context,
const SCEVUnknown *BasePointer) const {
SmallVector<const SCEV *, 4> Terms;
for (const auto &Pair : Context.Accesses[BasePointer]) {
+ std::vector<const SCEV *> MaxTerms;
+ SCEVRemoveMax::remove(*SE, Pair.second, &MaxTerms);
+ if (MaxTerms.size() > 0) {
+ Terms.insert(Terms.begin(), MaxTerms.begin(), MaxTerms.end());
+ continue;
+ }
// In case the outermost expression is a plain add, we check if any of its
// terms has the form 4 * %inst * %param * %param ..., aka a term that
// contains a product between a parameter and an instruction that is
@@ -592,6 +684,7 @@
for (const auto &Pair : Context.Accesses[BasePointer]) {
const Instruction *Insn = Pair.first;
auto *AF = Pair.second;
+ AF = SCEVRemoveMax::remove(*SE, AF);
bool IsNonAffine = false;
TempMemoryAccesses.insert(std::make_pair(Insn, MemAcc(Insn, Shape)));
MemAcc *Acc = &TempMemoryAccesses.find(Insn)->second;