[polly] Fix SCEVLoopAddRecRewriter to avoid invalid AddRecs.

[efriedma]

Summary

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.

[Meinersbur]

This only changes code in ScalarEvolution, so is this a SCEV fix or was Polly using ScalarEvolution in a way that was not originally intended?

[efriedma]

SCEVLoopAddRecRewriter was originally added for use by polly, and has only ever been used by polly. So the "original intent" is just whatever polly needed, I think.

[Meinersbur]

The test is sufficient for me. Thank you for the fix.

llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h

void setNoWrapFlags(NoWrapFlags Flags) {
         Flags = ScalarEvolution::setFlags(Flags, FlagNW);
       SubclassData |= Flags;
     }
 
     /// Return the value of this chain of recurrences at the specified
     /// 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<const SCEV *> 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
     /// where the value is not in the condition, thus computing the
     /// exit count.  If the iteration count can't be computed, an
     /// instance of SCEVCouldNotCompute is returned.
     const SCEV *getNumIterationsInRange(const ConstantRange &Range,
                                         ScalarEvolution &SE) const;
public:
     }
 
     const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
       SmallVector<const SCEV *, 2> Operands;
       for (const SCEV *Op : Expr->operands())
         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<SCEVAddRecExpr>(Res);
-      return Rec->evaluateAtIteration(Map[L], SE);
+      return SCEVAddRecExpr::evaluateAtIteration(Operands, Map[L], SE);
     }
 
   private:
     LoopToScevMapT &Map;
   };
 
 } // end namespace llvm
 
 #endif // LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H

llvm/lib/Analysis/ScalarEvolution.cpp

 /// chain by the binomial coefficient corresponding to it.  In other words, we
 /// can evaluate {A,+,B,+,C,+,D} as:
 ///
 ///   A*BC(It, 0) + B*BC(It, 1) + C*BC(It, 2) + D*BC(It, 3)
 ///
 /// 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<const SCEV *> 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<SCEVCouldNotCompute>(Coeff))
       return Coeff;
 
-    Result = SE.getAddExpr(Result, SE.getMulExpr(getOperand(i), Coeff));
+    Result = SE.getAddExpr(Result, SE.getMulExpr(Operands[i], Coeff));
   }
   return Result;
 }
 
 //===----------------------------------------------------------------------===//
 //                    SCEV Expression folder implementations
 //===----------------------------------------------------------------------===//
 

polly/test/Isl/CodeGen/OpenMP/scev-rewriting.ll

+; 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
+}