[ValueTracking] De-pessimize isImpliedCondition around unsigned compares

[sanjoy]

Summary

Currently isImpliedCondition will optimize "I +_nuw C < L ==> I < L"
only if C is positive. This is an unnecessary restriction -- the
implication holds even if C is negative.

[majnemer]

LGTM

llvm/trunk/lib/Analysis/ValueTracking.cpp

case CmpInst::ICMP_SLE: {
     }
     return false;
   }
 
   case CmpInst::ICMP_ULT:
   case CmpInst::ICMP_ULE: {
     ConstantInt *CI;
 
-    // LHS u<  LHS +_{nuw} C   if C > 0
-    // LHS u<= LHS +_{nuw} C   if C >= 0
+    // LHS u<  LHS +_{nuw} C   if C != 0
+    // LHS u<= LHS +_{nuw} C
     if (match(RHS, m_NUWAdd(m_Specific(LHS), m_ConstantInt(CI)))) {
       if (Pred == CmpInst::ICMP_ULT)
-        return CI->getValue().isStrictlyPositive();
-      return !CI->isNegative();
+        return !CI->isZero();
+      return true;
     }
     return false;
   }
   }
 }
 
 /// Return true if "icmp Pred BLHS BRHS" is true whenever "icmp Pred
 /// ALHS ARHS" is true.

llvm/trunk/test/Transforms/InstSimplify/implies.ll

 ; CHECK: ret i1 true
   %iplus1 = add nsw i32 %i, 1
   %var29 = icmp slt i32 %i, %length.i
   %var30 = icmp slt i32 %iplus1, %length.i
   %res = icmp uge i1 %var29, %var30
   ret i1 %res
 }
 
-; i +_{nuw} C_{>0} <u L ==> i <u L
+; i +_{nuw} C <u L ==> i <u L
 define i1 @test4(i32 %length.i, i32 %i) {
 ; CHECK-LABEL: @test4
 ; CHECK: ret i1 true
   %iplus1 = add nuw i32 %i, 1
   %var29 = icmp ult i32 %i, %length.i
   %var30 = icmp ult i32 %iplus1, %length.i
   %res = icmp ule i1 %var30, %var29
   ret i1 %res
; CHECK: ret i1 true
   %iplus1 = add nuw i32 %i, 1
   %len.plus.one = add nuw i32 %length.i, 1
   %var29 = icmp ult i32 %i, %len.plus.one
   %var30 = icmp ult i32 %iplus1, %length.i
   %res = icmp ule i1 %var30, %var29
   ret i1 %res
 }
 
+; i +_{nuw} C <s L ==> i < L, even if C is negative
+define i1 @test9(i32 %length.i, i32 %i) {
+; CHECK-LABEL: @test9(
+; CHECK: ret i1 true
+  %iplus1 = add nuw i32 %i, -100
+  %var29 = icmp ult i32 %i, %length.i
+  %var30 = icmp ult i32 %iplus1, %length.i
+  %res = icmp ule i1 %var30, %var29
+  ret i1 %res
+}
+
 ; X >=(s) Y == X ==> Y (i1 1 becomes -1 for reasoning)
 define i1 @test_sge(i32 %length.i, i32 %i) {
 ; CHECK-LABEL: @test_sge
 ; CHECK: ret i1 true
   %iplus1 = add nsw nuw i32 %i, 1
   %var29 = icmp ult i32 %i, %length.i
   %var30 = icmp ult i32 %iplus1, %length.i
   %res = icmp sge i1 %var30, %var29
   ret i1 %res
 }