Index: llvm/trunk/lib/Analysis/ScalarEvolution.cpp
===================================================================
--- llvm/trunk/lib/Analysis/ScalarEvolution.cpp
+++ llvm/trunk/lib/Analysis/ScalarEvolution.cpp
@@ -1550,8 +1550,16 @@
                        getMulExpr(WideMaxBECount,
                                   getZeroExtendExpr(Step, WideTy)));
           if (SAdd == OperandExtendedAdd) {
-            // Cache knowledge of AR NSW, which is propagated to this AddRec.
-            const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNSW);
+            // If AR wraps around then
+            //
+            //    abs(Step) * MaxBECount > unsigned-max(AR->getType())
+            // => SAdd != OperandExtendedAdd
+            //
+            // Thus (AR is not NW => SAdd != OperandExtendedAdd) <=>
+            // (SAdd == OperandExtendedAdd => AR is NW)
+
+            const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNW);
+
             // Return the expression with the addrec on the outside.
             return getAddRecExpr(getSignExtendAddRecStart(AR, Ty, this),
                                  getZeroExtendExpr(Step, Ty),
Index: llvm/trunk/test/Analysis/ScalarEvolution/incorrect-nsw.ll
===================================================================
--- llvm/trunk/test/Analysis/ScalarEvolution/incorrect-nsw.ll
+++ llvm/trunk/test/Analysis/ScalarEvolution/incorrect-nsw.ll
@@ -0,0 +1,26 @@
+; RUN: opt -analyze -scalar-evolution -scalar-evolution < %s | FileCheck %s
+
+define void @bad.nsw() {
+; CHECK-LABEL: Classifying expressions for: @bad.nsw
+; CHECK-LABEL: Classifying expressions for: @bad.nsw
+ entry: 
+  br label %loop
+
+ loop:
+  %i = phi i8 [ -1, %entry ], [ %i.inc, %loop ]
+; CHECK:  %i = phi i8 [ -1, %entry ], [ %i.inc, %loop ]
+; CHECK-NEXT: -->  {-1,+,-128}<nw><%loop>
+; CHECK-NOT: -->  {-1,+,-128}<nsw><%loop>
+
+  %counter = phi i8 [ 0, %entry ], [ %counter.inc, %loop ]
+
+  %i.inc = add i8 %i, -128
+  %i.sext = sext i8 %i to i16
+
+  %counter.inc = add i8 %counter, 1
+  %continue = icmp eq i8 %counter, 1
+  br i1 %continue, label %exit, label %loop
+
+ exit:
+  ret void  
+}