From fd229caa0138d296090c101655c82ca7da58ddd6 Mon Sep 17 00:00:00 2001 From: Eli Friedman Date: Fri, 21 May 2021 16:58:36 -0700 Subject: [PATCH] [polly] Fix SCEVLoopAddRecRewriter to avoid invalid AddRecs. When we're remapping an AddRec, the AddRec constructed by a partial rewrite might not make sense. This triggers an assertion complaining it's not loop-invariant. Instead of constructing the partially rewritten AddRec, just skip straight to calling evaluateAtIteration. Testcase was automatically reduced using llvm-reduce, so it's a little messy, but hopefully makes sense. Differential Revision: https://reviews.llvm.org/D102959 --- .../llvm/Analysis/ScalarEvolutionExpressions.h | 12 +++-- llvm/lib/Analysis/ScalarEvolution.cpp | 15 ++++-- polly/test/Isl/CodeGen/OpenMP/scev-rewriting.ll | 56 ++++++++++++++++++++++ 3 files changed, 74 insertions(+), 9 deletions(-) create mode 100644 polly/test/Isl/CodeGen/OpenMP/scev-rewriting.ll diff --git a/llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h b/llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h index 37e675f..ad0c747 100644 --- a/llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h +++ b/llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h @@ -401,6 +401,11 @@ class Type; /// iteration number. const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const; + /// Return the value of this chain of recurrences at the specified iteration + /// number. Takes an explicit list of operands to represent an AddRec. + static const SCEV *evaluateAtIteration(ArrayRef Operands, + const SCEV *It, ScalarEvolution &SE); + /// Return the number of iterations of this loop that produce /// values in the specified constant range. Another way of /// looking at this is that it returns the first iteration number @@ -895,13 +900,10 @@ class Type; Operands.push_back(visit(Op)); const Loop *L = Expr->getLoop(); - const SCEV *Res = SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags()); - if (0 == Map.count(L)) - return Res; + return SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags()); - const SCEVAddRecExpr *Rec = cast(Res); - return Rec->evaluateAtIteration(Map[L], SE); + return SCEVAddRecExpr::evaluateAtIteration(Operands, Map[L], SE); } private: diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 84671f5..0d3d781 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -1025,16 +1025,23 @@ static const SCEV *BinomialCoefficient(const SCEV *It, unsigned K, /// where BC(It, k) stands for binomial coefficient. const SCEV *SCEVAddRecExpr::evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const { - const SCEV *Result = getStart(); - for (unsigned i = 1, e = getNumOperands(); i != e; ++i) { + return evaluateAtIteration(makeArrayRef(op_begin(), op_end()), It, SE); +} + +const SCEV * +SCEVAddRecExpr::evaluateAtIteration(ArrayRef Operands, + const SCEV *It, ScalarEvolution &SE) { + assert(Operands.size() > 0); + const SCEV *Result = Operands[0]; + for (unsigned i = 1, e = Operands.size(); i != e; ++i) { // The computation is correct in the face of overflow provided that the // multiplication is performed _after_ the evaluation of the binomial // coefficient. - const SCEV *Coeff = BinomialCoefficient(It, i, SE, getType()); + const SCEV *Coeff = BinomialCoefficient(It, i, SE, Result->getType()); if (isa(Coeff)) return Coeff; - Result = SE.getAddExpr(Result, SE.getMulExpr(getOperand(i), Coeff)); + Result = SE.getAddExpr(Result, SE.getMulExpr(Operands[i], Coeff)); } return Result; } diff --git a/polly/test/Isl/CodeGen/OpenMP/scev-rewriting.ll b/polly/test/Isl/CodeGen/OpenMP/scev-rewriting.ll new file mode 100644 index 0000000..13fffa3 --- /dev/null +++ b/polly/test/Isl/CodeGen/OpenMP/scev-rewriting.ll @@ -0,0 +1,56 @@ +; RUN: opt < %s -polly-vectorizer=polly -polly-parallel -polly-parallel-force -polly-process-unprofitable -polly-codegen -S | FileCheck %s +; CHECK: define internal void @DoStringSort_polly_subfn +target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128" +target triple = "aarch64-unknown-linux-gnueabi" + +define void @DoStringSort() { +bb: + br label %bb1 + +bb1: ; preds = %bb1, %bb + %i = phi i32 [ 0, %bb ], [ %i2, %bb1 ] + %i2 = add i32 %i, 1 + br i1 undef, label %bb1, label %bb3 + +bb3: ; preds = %bb1 + br i1 undef, label %bb6, label %bb4 + +bb4: ; preds = %bb3 + %i5 = bitcast i8* undef to i32* + br label %bb6 + +bb6: ; preds = %bb4, %bb3 + %i7 = phi i32* [ %i5, %bb4 ], [ undef, %bb3 ] + br i1 undef, label %bb21, label %bb8 + +bb8: ; preds = %bb20, %bb6 + %i9 = phi i32* [ %i7, %bb6 ], [ %i10, %bb20 ] + %i10 = getelementptr inbounds i32, i32* %i9, i32 %i2 + br i1 undef, label %bb11, label %bb20 + +bb11: ; preds = %bb8 + br label %bb12 + +bb12: ; preds = %bb11 + br label %bb13 + +bb13: ; preds = %bb12 + br label %bb14 + +bb14: ; preds = %bb14, %bb13 + %i15 = phi i32 [ %i17, %bb14 ], [ 1, %bb13 ] + %i16 = getelementptr inbounds i32, i32* %i9, i32 %i15 + store i32 undef, i32* %i16, align 4 + %i17 = add i32 %i15, 1 + %i18 = icmp eq i32 %i15, %i + br i1 %i18, label %bb19, label %bb14 + +bb19: ; preds = %bb14 + br label %bb20 + +bb20: ; preds = %bb19, %bb8 + br i1 undef, label %bb21, label %bb8 + +bb21: ; preds = %bb20, %bb6 + unreachable +} -- 2.7.4