[SCEV] Fix wrong Equal predicate created in getAddRecForPhiWithCasts

[dorit]

Summary

This came up during D38948:

CreateAddRecFromPHIWithCastsImpl() adds an IncrementNUSW overflow predicate which allows the PSCEV rewriter to rewrite this scev expression:
(zext i8 {0, + , (trunc i32 step to i8)} to i32)
into
{0, +, (sext i8 (trunc i32 step to i8) to i32)}

But then it adds the wrong Equal predicate:
%step == (zext i8 (trunc i32 %step to i8) to i32).
instead of:
%step == (sext i8 (trunc i32 %step to i8) to i32)

This is fixed here.

[dorit]

ping

[sanjoy]

lgtm with stylistic nits.

lib/Analysis/ScalarEvolution.cpp

4631 ↗

(On Diff #124886)

How about reducing the capture list of this lambda so that we don't have both Signed and isSigned in scope?

Alternately, you could s/isSigned/CreateSignExtend/ (actually now that I think of it, I like this option better than the first option).

Finally, the LLVM convention is to start variable names with uppercase.

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::createAddRecFromPHIWithCastsImpl(const SCEVUnknown *SymbolicPHI) {
 
   // It is possible that the predicates P2 and/or P3 are computable at
   // compile time due to StartVal and/or Accum being constants.
   // If either one is, then we can check that now and escape if either P2
   // or P3 is false.
 
   // 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 CreateSignExtend) -> 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())
+        CreateSignExtend ? getSignExtendExpr(TruncatedExpr, Expr->getType())
                          : getZeroExtendExpr(TruncatedExpr, Expr->getType());
     return ExtendedExpr;
   };
 
   // Given:
   //  ExtendedExpr = (Ext ix (Trunc iy (Expr) to ix) to iy
-  //               = GetExtendedExpr(Expr)
+  //               = getExtendedExpr(Expr)
   // Determine whether the predicate P: Expr == ExtendedExpr
   // is known to be false at compile time
   auto PredIsKnownFalse = [&](const SCEV *Expr,
                               const SCEV *ExtendedExpr) -> bool {
     return Expr != ExtendedExpr &&
            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, /*CreateSignExtend=*/true);
   if (PredIsKnownFalse(Accum, AccumExtended)) {
     DEBUG(dbgs() << "P3 is compile-time false\n";);
     return None;
   }
 
   auto AppendPredicate = [&](const SCEV *Expr,
                              const SCEV *ExtendedExpr) -> void {
     if (Expr != ExtendedExpr &&

llvm/trunk/test/Transforms/LoopVectorize/pr30654-phiscev-sext-trunc.ll

 
 for.end:                                
   ret void
 }
 
 ; 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) {
 ;   int i;
 ;   unsigned char p = 0;
 ;   for (i = 0; i < n; i++) {
 ;      a[i] = p;
 ;      p = p + step;
 ;   }
 ; }
 ; 
 
 ; CHECK-LABEL: @doit2
 ; CHECK: vector.scevcheck
 ; CHECK: %mul = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 {{.*}}, i8 {{.*}})
 ; 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:
 ; CHECK: <4 x i32>
 
 ; Function Attrs: norecurse nounwind uwtable
 define void @doit2(i32 %n, i32 %step) local_unnamed_addr  {
 entry: