[SCEV] Support negative values in signed/unsigned predicate reasoning

[mkazantsev]

Summary

There is a piece of logic that uses the fact that signed and unsigned versions of the
same predicate are equivalent when both values are non-negative. It's also true when
both of them are negative.

[nikic]

LGTM

[reames]

It would be really good to implement this same logic in Utils/SimplifyIndVars.cpp where we canonicalize comparisons to unsigned for the known-non-negative case. @mkazantsev Can I ask you to implement that as a follow up please?

llvm/lib/Analysis/ScalarEvolution.cpp

if (!FoundLHS->getType()->isPointerTy() &&
         isImpliedCondOperands(Pred, LHS, RHS, getNotSCEV(FoundLHS),
                               getNotSCEV(FoundRHS), Context))
       return true;
 
     return false;
   }
 
   // Unsigned comparison is the same as signed comparison when both the operands
-  // are non-negative.
+  // are non-negative or negative.
   if (CmpInst::isUnsigned(FoundPred) &&
       CmpInst::getSignedPredicate(FoundPred) == Pred &&
-      isKnownNonNegative(FoundLHS) && isKnownNonNegative(FoundRHS))
+      ((isKnownNonNegative(FoundLHS) && isKnownNonNegative(FoundRHS)) ||
+       (isKnownNegative(FoundLHS) && isKnownNegative(FoundRHS))))
     return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS, Context);
 
   // Check if we can make progress by sharpening ranges.
   if (FoundPred == ICmpInst::ICMP_NE &&
       (isa<SCEVConstant>(FoundLHS) || isa<SCEVConstant>(FoundRHS))) {
 
     const SCEVConstant *C = nullptr;
     const SCEV *V = nullptr;

llvm/test/Transforms/IndVarSimplify/negative_ranges.ll

 
 exit:
   ret i32 1
 
 side_exit:
   ret i32 0
 }
 
-; FIXME: 2nd check is implied by the 1st one as both values are negative.
 define i32 @test_02(i32* %p, i32* %s) {
 ; CHECK-LABEL: @test_02(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[START:%.*]] = load i32, i32* [[P:%.*]], align 4, !range [[RNG0]]
 ; CHECK-NEXT:    [[END:%.*]] = load i32, i32* [[S:%.*]], align 4, !range [[RNG0]]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[C1:%.*]] = icmp ult i32 [[IV]], [[END]]
 ; CHECK-NEXT:    br i1 [[C1]], label [[GUARDED:%.*]], label [[SIDE_EXIT:%.*]]
 ; CHECK:       guarded:
-; CHECK-NEXT:    [[C2:%.*]] = icmp slt i32 [[IV]], [[END]]
-; CHECK-NEXT:    br i1 [[C2]], label [[BACKEDGE]], label [[SIDE_EXIT]]
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[SIDE_EXIT]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 1
 ; CHECK:       side_exit:
 ; CHECK-NEXT:    ret i32 0