Index: lib/Analysis/ScalarEvolution.cpp
===================================================================
--- lib/Analysis/ScalarEvolution.cpp
+++ lib/Analysis/ScalarEvolution.cpp
@@ -4624,12 +4624,12 @@
 
   // Construct the extended SCEV: (Ext ix (Trunc iy (Expr) to ix) to iy)
   // for each of StartVal and Accum
-  auto GetExtendedExpr = [&](const SCEV *Expr) -> const SCEV * {
+  auto GetExtendedExpr = [&](const SCEV *Expr, bool isSigned) -> const SCEV * {
     assert(isLoopInvariant(Expr, L) && "Expr is expected to be invariant");
     const SCEV *TruncatedExpr = getTruncateExpr(Expr, TruncTy);
     const SCEV *ExtendedExpr =
-        Signed ? getSignExtendExpr(TruncatedExpr, Expr->getType())
-               : getZeroExtendExpr(TruncatedExpr, Expr->getType());
+        isSigned ? getSignExtendExpr(TruncatedExpr, Expr->getType())
+                 : getZeroExtendExpr(TruncatedExpr, Expr->getType());
     return ExtendedExpr;
   };
 
@@ -4644,13 +4644,15 @@
            isKnownPredicate(ICmpInst::ICMP_NE, Expr, ExtendedExpr);
   };
 
-  const SCEV *StartExtended = GetExtendedExpr(StartVal);
+  const SCEV *StartExtended = GetExtendedExpr(StartVal, Signed);
   if (PredIsKnownFalse(StartVal, StartExtended)) {
     DEBUG(dbgs() << "P2 is compile-time false\n";);
     return None;
   }
 
-  const SCEV *AccumExtended = GetExtendedExpr(Accum);
+  // The Step is always Signed (because the overflow checks are either
+  // NSSW or NUSW)
+  const SCEV *AccumExtended = GetExtendedExpr(Accum, /*isSigned=*/true);
   if (PredIsKnownFalse(Accum, AccumExtended)) {
     DEBUG(dbgs() << "P3 is compile-time false\n";);
     return None;
Index: test/Transforms/LoopVectorize/pr30654-phiscev-sext-trunc.ll
===================================================================
--- test/Transforms/LoopVectorize/pr30654-phiscev-sext-trunc.ll
+++ test/Transforms/LoopVectorize/pr30654-phiscev-sext-trunc.ll
@@ -74,7 +74,7 @@
 ; Same as above, but for checking the SCEV "zext(trunc(%p.09)) + %step".
 ; Here we expect the following two predicates to be added for runtime checking:
 ; 1) {0,+,(trunc i32 %step to i8)}<%for.body> Added Flags: <nusw>
-; 2) Equal predicate: %step == (zext i8 (trunc i32 %step to i8) to i32)
+; 2) Equal predicate: %step == (sext i8 (trunc i32 %step to i8) to i32)
 ;
 ; int a[N];
 ; void doit2(int n, int step) {
@@ -93,7 +93,8 @@
 ; CHECK-NOT: %mul = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 {{.*}}, i8 {{.*}})
 ; CHECK: %[[TEST:[0-9]+]] = or i1 {{.*}}, %mul.overflow
 ; CHECK: %[[NTEST:[0-9]+]] = or i1 false, %[[TEST]]
-; CHECK: %ident.check = icmp ne i32 {{.*}}, %{{.*}}
+; CHECK: %[[EXT:[0-9]+]] = sext i8 {{.*}} to i32
+; CHECK: %ident.check = icmp ne i32 {{.*}}, %[[EXT]]
 ; CHECK: %{{.*}} = or i1 %[[NTEST]], %ident.check
 ; CHECK-NOT: %mul = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 {{.*}}, i8 {{.*}})
 ; CHECK: vector.body: