Index: lib/Transforms/Scalar/LoopStrengthReduce.cpp
===================================================================
--- lib/Transforms/Scalar/LoopStrengthReduce.cpp
+++ lib/Transforms/Scalar/LoopStrengthReduce.cpp
@@ -325,7 +325,7 @@
 
   // Look at addrec operands.
   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S))
-    if (!AR->getStart()->isZero()) {
+    if (!AR->getStart()->isZero() && AR->isAffine()) {
       DoInitialMatch(AR->getStart(), L, Good, Bad, SE);
       DoInitialMatch(SE.getAddRecExpr(SE.getConstant(AR->getType(), 0),
                                       AR->getStepRecurrence(SE),
@@ -578,7 +578,8 @@
       // FlagNW is independent of the start value, step direction, and is
       // preserved with smaller magnitude steps.
       // FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
-      return SE.getAddRecExpr(Start, Step, AR->getLoop(), SCEV::FlagAnyWrap);
+      if (AR->isAffine())
+        return SE.getAddRecExpr(Start, Step, AR->getLoop(), SCEV::FlagAnyWrap);
     }
     return nullptr;
   }
@@ -3202,7 +3203,7 @@
       Ops.push_back(C ? SE.getMulExpr(C, Remainder) : Remainder);
       Remainder = nullptr;
     }
-    if (Remainder != AR->getStart()) {
+    if (Remainder != AR->getStart() && AR->isAffine()) {
       if (!Remainder)
         Remainder = SE.getConstant(AR->getType(), 0);
       return SE.getAddRecExpr(Remainder,
Index: test/Transforms/LoopStrengthReduce/ARM/addrec-is-loop-invariant.ll
===================================================================
--- /dev/null
+++ test/Transforms/LoopStrengthReduce/ARM/addrec-is-loop-invariant.ll
@@ -0,0 +1,35 @@
+; RUN: llc -mtriple=armv8-eabi -verify-machineinstrs %s -o /dev/null
+
+; This test checks that when the IR is not under LCSSA form,
+; Loop Strength Reduction will not create an Add Reccurence
+; Expression if not all its operands are loop invariants.
+
+define void @add_rec_expr() {
+entry:
+  br label %loop0
+
+loop0:
+  %c.0 = phi i32 [ 0, %entry ], [ %inc.0, %loop0 ]
+  %inc.0 = add nuw i32 %c.0, 1
+  br i1 undef, label %loop0, label %bb1
+
+bb1:
+  %mul.0 = mul i32 %c.0, %c.0
+  %gelptr.0 = getelementptr inbounds i16, i16* undef, i32 %mul.0
+  br label %loop1
+
+loop1:
+  %inc.1 = phi i32 [ %inc.2, %bb4 ], [ 0, %bb1 ]
+  %mul.1 = mul i32 %inc.1, %c.0
+  br label %bb3
+
+bb3:
+  %add.0 = add i32 undef, %mul.1
+  %gelptr.1 = getelementptr inbounds i16, i16* %gelptr.0, i32 %add.0
+  store i16 undef, i16* %gelptr.1, align 2
+  br label %bb4
+
+bb4:
+  %inc.2 = add nuw i32 %inc.1, 1
+  br label %loop1
+}