diff --git a/llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h b/llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h
--- a/llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h
+++ b/llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h
@@ -401,6 +401,11 @@
     /// 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
@@ -895,13 +900,10 @@
         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:
diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -1025,16 +1025,23 @@
 /// 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;
 }
diff --git a/polly/test/Isl/CodeGen/OpenMP/scev-rewriting.ll b/polly/test/Isl/CodeGen/OpenMP/scev-rewriting.ll
new file mode 100644
--- /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
+}