[ValueTracking] More unsigned binary op implied conditions

[caojoshua]

Summary

We add rules for sub, mul, udiv, urem, shl, and &&. We also add
strengthened rule for add to work for all Values, and not just
constants. We have to check for zeros for mul, div, and urem.

[nikic]

I predicted this is going to happen in https://reviews.llvm.org/D149510#4315073, and now it is happening. You are reimplementing InstSimplify comparison folding in isTruePredicate().

[caojoshua]

In D152646#4411887, @nikic wrote:

I predicted this is going to happen in https://reviews.llvm.org/D149510#4315073, and now it is happening. You are reimplementing InstSimplify comparison folding in isTruePredicate().

Oops. I thought this was a draft.

I can give an attempt at using SimplifyICmpInst as you mentioned, and see how much compile time is impacted.

[caojoshua]

In D152646#4411887, @nikic wrote:

I predicted this is going to happen in https://reviews.llvm.org/D149510#4315073, and now it is happening. You are reimplementing InstSimplify comparison folding in isTruePredicate().

I'm not aware of where in InstSimplify this is re-implementing. simplifyICmp() and simplifyICmpOfBools() both make calls out to isTruePredicate(). Passing in the test examples to places like InstCombine or ConstraintElimination does not simplify. I don't believe existing logic to simplify these cases exists right now.

I believe that isTruePredicate() is the correct place to put this logic right now. I agree with your concerns on writing a bunch of different rules, but I don't see another way if we want to optimize these cases (maybe pick out the ones that are more useful, like subtraction).

[nikic]

In D152646#4412382, @caojoshua wrote:

In D152646#4411887, @nikic wrote:

I predicted this is going to happen in https://reviews.llvm.org/D149510#4315073, and now it is happening. You are reimplementing InstSimplify comparison folding in isTruePredicate().

I'm not aware of where in InstSimplify this is re-implementing. simplifyICmp() and simplifyICmpOfBools() both make calls out to isTruePredicate(). Passing in the test examples to places like InstCombine or ConstraintElimination does not simplify. I don't believe existing logic to simplify these cases exists right now.

I don't follow. isTruePredicate() is a static function in ValueTracking, so how can InstSimplify call it?

You should be able to find the cases you're duplicating in simplifyICmpWithBinOpOnLHS().

llvm/lib/Analysis/ValueTracking.cpp

case CmpInst::ICMP_SLE: {
     if (match(RHS, m_NSWAdd(m_Specific(LHS), m_APInt(C))))
       return !C->isNegative();
     return false;
   }
 
   case CmpInst::ICMP_ULE: {
     const APInt *C;
 
-    // LHS u<= LHS +_{nuw} C   for any C
-    if (match(RHS, m_NUWAdd(m_Specific(LHS), m_APInt(C))))
+    // LHS u<= LHS +_{nuw} V for any V
+    if (match(RHS, m_NUWAdd(m_Specific(LHS), m_Value())))
       return true;
 
+    // RHS -_{nuw} V u<= RHS for any V
+    if (match(LHS, m_NUWSub(m_Specific(RHS), m_Value())))
+      return true;
+
+    // LHS u<= LHS *_{nuw} C if C is not zero
+    if (match(RHS, m_NUWMul(m_Specific(LHS), m_APInt(C))))
+      return !C->isZero();
+
+    // RHS u/ C u<= RHS if C is not Zero
+    if (match(LHS, m_UDiv(m_Specific(RHS), m_APInt(C))))
+      return !C->isZero();
+
+    // RHS u% C u<= RHS if C is not zero
+    if (match(LHS, m_URem(m_Specific(RHS), m_APInt(C))))
+      return !C->isZero();
+
     // RHS >> V u<= RHS for any V
     if (match(LHS, m_LShr(m_Specific(RHS), m_Value())))
       return true;
 
+    // LHS u<= LHS <<_{nuw} V for any V
+    if (match(RHS, m_NUWShl(m_Specific(LHS), m_Value())))
+      return true;
+
+    // RHS & V u<= RHS for any V
+    if (match(LHS, m_And(m_Specific(RHS), m_Value())))
+      return true;
+
     // Match A to (X +_{nuw} CA) and B to (X +_{nuw} CB)
     auto MatchNUWAddsToSameValue = [&](const Value *A, const Value *B,
                                        const Value *&X,
                                        const APInt *&CA, const APInt *&CB) {
       if (match(A, m_NUWAdd(m_Value(X), m_APInt(CA))) &&
           match(B, m_NUWAdd(m_Specific(X), m_APInt(CB))))
         return true;
 

llvm/test/Transforms/InstSimplify/implies.ll

;
   tail call void @llvm.assume(i1 %2)
   %3 = icmp eq i64 %x, %y
   ret i1 %3
 }
 
 ; i +_{nuw} V <u L ==> i <u L
 define i1 @add(i32 %length.i, i32 %i, i32 %v) {
 ; CHECK-LABEL: @add(
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw i32 [[I:%.*]], [[V:%.*]]
-; CHECK-NEXT:    [[COND1:%.*]] = icmp ult i32 [[I]], [[LENGTH_I:%.*]]
-; CHECK-NEXT:    [[COND2:%.*]] = icmp ult i32 [[ADD]], [[LENGTH_I]]
-; CHECK-NEXT:    [[RES:%.*]] = icmp ule i1 [[COND2]], [[COND1]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %add = add nuw i32 %i, %v
   %cond1 = icmp ult i32 %i, %length.i
   %cond2 = icmp ult i32 %add, %length.i
   %res = icmp ule i1 %cond2, %cond1
   ret i1 %res
 }
 
 ; i <u L ==> i -_{nuw} V <u L
 define i1 @sub(i32 %length.i, i32 %i, i32 %v) {
 ; CHECK-LABEL: @sub(
-; CHECK-NEXT:    [[SUB:%.*]] = sub nuw i32 [[I:%.*]], [[V:%.*]]
-; CHECK-NEXT:    [[COND1:%.*]] = icmp ult i32 [[I]], [[LENGTH_I:%.*]]
-; CHECK-NEXT:    [[COND2:%.*]] = icmp ult i32 [[SUB]], [[LENGTH_I]]
-; CHECK-NEXT:    [[RES:%.*]] = icmp ule i1 [[COND1]], [[COND2]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %sub = sub nuw i32 %i, %v
   %cond1 = icmp ult i32 %i, %length.i
   %cond2 = icmp ult i32 %sub, %length.i
   %res = icmp ule i1 %cond1, %cond2
   ret i1 %res
 }
 
 ; i *_{nuw} C <u L ==> i <u L for C != 0
 define i1 @mul(i32 %length.i, i32 %i) {
 ; CHECK-LABEL: @mul(
-; CHECK-NEXT:    [[MUL:%.*]] = mul nuw i32 [[I:%.*]], 2
-; CHECK-NEXT:    [[COND1:%.*]] = icmp ult i32 [[I]], [[LENGTH_I:%.*]]
-; CHECK-NEXT:    [[COND2:%.*]] = icmp ult i32 [[MUL]], [[LENGTH_I]]
-; CHECK-NEXT:    [[RES:%.*]] = icmp ule i1 [[COND2]], [[COND1]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %mul = mul nuw i32 %i, 2
   %cond1 = icmp ult i32 %i, %length.i
   %cond2 = icmp ult i32 %mul, %length.i
   %res = icmp ule i1 %cond2, %cond1
   ret i1 %res
 }
 
;
   %cond2 = icmp ult i32 %mul, %length.i
   %res = icmp ule i1 %cond2, %cond1
   ret i1 %res
 }
 
 ; i <u L ==> i / C <u L for C != 0
 define i1 @udiv(i32 %length.i, i32 %i) {
 ; CHECK-LABEL: @udiv(
-; CHECK-NEXT:    [[UDIV:%.*]] = udiv i32 [[I:%.*]], 3
-; CHECK-NEXT:    [[COND1:%.*]] = icmp ult i32 [[I]], [[LENGTH_I:%.*]]
-; CHECK-NEXT:    [[COND2:%.*]] = icmp ult i32 [[UDIV]], [[LENGTH_I]]
-; CHECK-NEXT:    [[RES:%.*]] = icmp ule i1 [[COND1]], [[COND2]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %udiv = udiv i32 %i, 3
   %cond1 = icmp ult i32 %i, %length.i
   %cond2 = icmp ult i32 %udiv, %length.i
   %res = icmp ule i1 %cond1, %cond2
   ret i1 %res
 }
 
 ; i <u L ==> i % C <u L for C != 0
 define i1 @urem(i32 %length.i, i32 %i) {
 ; CHECK-LABEL: @urem(
-; CHECK-NEXT:    [[UREM:%.*]] = urem i32 [[I:%.*]], 2
-; CHECK-NEXT:    [[COND1:%.*]] = icmp ult i32 [[I]], [[LENGTH_I:%.*]]
-; CHECK-NEXT:    [[COND2:%.*]] = icmp ult i32 [[UREM]], [[LENGTH_I]]
-; CHECK-NEXT:    [[RES:%.*]] = icmp ule i1 [[COND1]], [[COND2]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %urem = urem i32 %i, 2
   %cond1 = icmp ult i32 %i, %length.i
   %cond2 = icmp ult i32 %urem, %length.i
   %res = icmp ule i1 %cond1, %cond2
   ret i1 %res
 }
 
;
   %var30 = icmp ult i32 %shl, %length.i
   %res = icmp ule i1 %var29, %var30
   ret i1 %res
 }
 
 ; i <<_{nuw} V <u L ==> i <u L
 define i1 @shl(i32 %length.i, i32 %i, i32 %v) {
 ; CHECK-LABEL: @shl(
-; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i32 [[I:%.*]], [[V:%.*]]
-; CHECK-NEXT:    [[COND1:%.*]] = icmp ult i32 [[I]], [[LENGTH_I:%.*]]
-; CHECK-NEXT:    [[COND2:%.*]] = icmp ult i32 [[SHL]], [[LENGTH_I]]
-; CHECK-NEXT:    [[RES:%.*]] = icmp ule i1 [[COND2]], [[COND1]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %shl = shl nuw i32 %i, %v
   %cond1 = icmp ult i32 %i, %length.i
   %cond2 = icmp ult i32 %shl, %length.i
   %res = icmp ule i1 %cond2, %cond1
   ret i1 %res
 }
 
-; i <u L ==> i && C <u L
+; i <u L ==> i & C <u L
 define i1 @and(i32 %length.i, i32 %i, i32 %v) {
 ; CHECK-LABEL: @and(
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[I:%.*]], [[V:%.*]]
-; CHECK-NEXT:    [[COND1:%.*]] = icmp ult i32 [[I]], [[LENGTH_I:%.*]]
-; CHECK-NEXT:    [[COND2:%.*]] = icmp ult i32 [[AND]], [[LENGTH_I]]
-; CHECK-NEXT:    [[RES:%.*]] = icmp ule i1 [[COND1]], [[COND2]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %and = and i32 %i, %v
   %cond1 = icmp ult i32 %i, %length.i
   %cond2 = icmp ult i32 %and, %length.i
   %res = icmp ule i1 %cond1, %cond2
   ret i1 %res
 }
 
 declare void @llvm.assume(i1)