Index: llvm/trunk/lib/Analysis/ScalarEvolution.cpp
===================================================================
--- llvm/trunk/lib/Analysis/ScalarEvolution.cpp
+++ llvm/trunk/lib/Analysis/ScalarEvolution.cpp
@@ -3774,6 +3774,24 @@
   }
 }
 
+/// Check whether value has nuw/nsw/exact set but SCEV does not.
+/// TODO: In reality it is better to check the poison recursevely
+/// but this is better than nothing.
+static bool SCEVLostPoisonFlags(const SCEV *S, const Value *V) {
+  if (auto *I = dyn_cast<Instruction>(V)) {
+    if (isa<OverflowingBinaryOperator>(I)) {
+      if (auto *NS = dyn_cast<SCEVNAryExpr>(S)) {
+        if (I->hasNoSignedWrap() && !NS->hasNoSignedWrap())
+          return true;
+        if (I->hasNoUnsignedWrap() && !NS->hasNoUnsignedWrap())
+          return true;
+      }
+    } else if (isa<PossiblyExactOperator>(I) && I->isExact())
+      return true;
+  }
+  return false;
+}
+
 /// Return an existing SCEV if it exists, otherwise analyze the expression and
 /// create a new one.
 const SCEV *ScalarEvolution::getSCEV(Value *V) {
@@ -3787,7 +3805,7 @@
     // ValueExprMap before insert S->{V, 0} into ExprValueMap.
     std::pair<ValueExprMapType::iterator, bool> Pair =
         ValueExprMap.insert({SCEVCallbackVH(V, this), S});
-    if (Pair.second) {
+    if (Pair.second && !SCEVLostPoisonFlags(S, V)) {
       ExprValueMap[S].insert({V, nullptr});
 
       // If S == Stripped + Offset, add Stripped -> {V, Offset} into
Index: llvm/trunk/test/Transforms/LoopStrengthReduce/post-inc-icmpzero.ll
===================================================================
--- llvm/trunk/test/Transforms/LoopStrengthReduce/post-inc-icmpzero.ll
+++ llvm/trunk/test/Transforms/LoopStrengthReduce/post-inc-icmpzero.ll
@@ -6,11 +6,12 @@
 
 ; CHECK:   [[r1:%[a-z0-9\.]+]] = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
 ; CHECK:   [[r2:%[a-z0-9\.]+]] = lshr exact i64 [[r1]], 1
+; CHECK:   [[r3:%[a-z0-9\.]+]] = bitcast i64 [[r2]] to i64
 ; CHECK: for.body.lr.ph:
-; CHECK:   [[r3:%[a-z0-9]+]] = shl i64 [[r2]], 1
+; CHECK:   [[r4:%[a-z0-9]+]] = shl i64 [[r3]], 1
 ; CHECK:   br label %for.body
 ; CHECK: for.body:
-; CHECK:   %lsr.iv2 = phi i64 [ %lsr.iv.next, %for.body ], [ [[r3]], %for.body.lr.ph ]
+; CHECK:   %lsr.iv2 = phi i64 [ %lsr.iv.next, %for.body ], [ [[r4]], %for.body.lr.ph ]
 ; CHECK:   %lsr.iv.next = add i64 %lsr.iv2, -2
 ; CHECK:   %lsr.iv.next3 = inttoptr i64 %lsr.iv.next to i16*
 ; CHECK:   %cmp27 = icmp eq i16* %lsr.iv.next3, null
Index: llvm/trunk/unittests/Analysis/ScalarEvolutionTest.cpp
===================================================================
--- llvm/trunk/unittests/Analysis/ScalarEvolutionTest.cpp
+++ llvm/trunk/unittests/Analysis/ScalarEvolutionTest.cpp
@@ -1288,5 +1288,107 @@
   EXPECT_FALSE(I->hasNoSignedWrap());
 }
 
+// Check that SCEV does not save the SCEV -> V
+// mapping of SCEV differ from V in NUW flag.
+TEST_F(ScalarEvolutionsTest, SCEVCacheNUW) {
+  /*
+   * Create the following code:
+   * func(i64 %a)
+   * entry:
+   *  %s1 = add i64 %a, -1
+   *  %s2 = add nuw i64 %a, -1
+   *  br label %exit
+   * exit:
+   *  ret %s
+   */
+
+  // Create a module.
+  Module M("SCEVCacheNUW", Context);
+
+  Type *T_int64 = Type::getInt64Ty(Context);
+
+  FunctionType *FTy =
+      FunctionType::get(Type::getVoidTy(Context), { T_int64 }, false);
+  Function *F = cast<Function>(M.getOrInsertFunction("func", FTy));
+  Argument *Arg = &*F->arg_begin();
+  ConstantInt *C = ConstantInt::get(Context, APInt(64, -1));
+
+  BasicBlock *Entry = BasicBlock::Create(Context, "entry", F);
+  BasicBlock *Exit = BasicBlock::Create(Context, "exit", F);
+
+  IRBuilder<> Builder(Entry);
+  auto *S1 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));
+  auto *S2 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));
+  S2->setHasNoUnsignedWrap(true);
+  Builder.CreateBr(Exit);
+
+  Builder.SetInsertPoint(Exit);
+  auto *R = cast<Instruction>(Builder.CreateRetVoid());
+
+  ScalarEvolution SE = buildSE(*F);
+  // Get S2 first to move it to cache.
+  const SCEV *SC2 = SE.getSCEV(S2);
+  EXPECT_TRUE(isa<SCEVAddExpr>(SC2));
+  // Now get S1.
+  const SCEV *SC1 = SE.getSCEV(S1);
+  EXPECT_TRUE(isa<SCEVAddExpr>(SC1));
+  // Expand for S1, it should use S1 not S2 in spite S2
+  // first in the cache.
+  SCEVExpander Exp(SE, M.getDataLayout(), "expander");
+  auto *I = cast<Instruction>(Exp.expandCodeFor(SC1, nullptr, R));
+  EXPECT_FALSE(I->hasNoUnsignedWrap());
+}
+
+// Check that SCEV does not save the SCEV -> V
+// mapping of SCEV differ from V in NSW flag.
+TEST_F(ScalarEvolutionsTest, SCEVCacheNSW) {
+  /*
+   * Create the following code:
+   * func(i64 %a)
+   * entry:
+   *  %s1 = add i64 %a, -1
+   *  %s2 = add nsw i64 %a, -1
+   *  br label %exit
+   * exit:
+   *  ret %s
+   */
+
+  // Create a module.
+  Module M("SCEVCacheNUW", Context);
+
+  Type *T_int64 = Type::getInt64Ty(Context);
+
+  FunctionType *FTy =
+      FunctionType::get(Type::getVoidTy(Context), { T_int64 }, false);
+  Function *F = cast<Function>(M.getOrInsertFunction("func", FTy));
+  Argument *Arg = &*F->arg_begin();
+  ConstantInt *C = ConstantInt::get(Context, APInt(64, -1));
+
+  BasicBlock *Entry = BasicBlock::Create(Context, "entry", F);
+  BasicBlock *Exit = BasicBlock::Create(Context, "exit", F);
+
+  IRBuilder<> Builder(Entry);
+  auto *S1 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));
+  auto *S2 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));
+  S2->setHasNoSignedWrap(true);
+  Builder.CreateBr(Exit);
+
+  Builder.SetInsertPoint(Exit);
+  auto *R = cast<Instruction>(Builder.CreateRetVoid());
+
+  ScalarEvolution SE = buildSE(*F);
+  // Get S2 first to move it to cache.
+  const SCEV *SC2 = SE.getSCEV(S2);
+  EXPECT_TRUE(isa<SCEVAddExpr>(SC2));
+  // Now get S1.
+  const SCEV *SC1 = SE.getSCEV(S1);
+  EXPECT_TRUE(isa<SCEVAddExpr>(SC1));
+  // Expand for S1, it should use S1 not S2 in spite S2
+  // first in the cache.
+  SCEVExpander Exp(SE, M.getDataLayout(), "expander");
+  auto *I = cast<Instruction>(Exp.expandCodeFor(SC1, nullptr, R));
+  EXPECT_FALSE(I->hasNoSignedWrap());
+}
+
 }  // end anonymous namespace
 }  // end namespace llvm