[InstSimplify] Simplify `icmp eq/ne/ugt/ult X, 0` -> true/false where `X` is known to be zero.

[goldstein.w.n]

Summary

This case was previously missing as the above icmp conditions only
checked if X was known non-zero.

Later on isKnownNonEqual also doesn't run (to save compile time) as
its assumed that simplifyICmpWithZero handles the icmp pred X, 0
cases sufficiently.

[nikic]

This doesn't make sense to me. If the value is known all zeroes, then the value should fold to zero, at which point the icmp becomes trivial (not necessarily in InstSimplify, but in InstCombine).

The basic pattern from your tests already folds to zero: https://llvm.godbolt.org/z/EWTd4P3aY The pattern with the zero comparison does not: https://llvm.godbolt.org/z/xnv4joe9G

At a guess, this is because we specially handle values used inside return instructions in https://github.com/llvm/llvm-project/blob/8e7c1b9a3d5f08046261ca0b7e5d319a4c4c9b25/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp#L3111 -- we should possibly stop doing that, because it gives a misleading picture of which folds work and which don't.

Ands that fold to constants based on known bits are intended to reliably fold as part of demanded bits simplification here: https://github.com/llvm/llvm-project/blob/8e7c1b9a3d5f08046261ca0b7e5d319a4c4c9b25/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp#L200

The problem is that the pattern you are testing is special-cased in ValueTracking only: https://github.com/llvm/llvm-project/blob/8e7c1b9a3d5f08046261ca0b7e5d319a4c4c9b25/llvm/lib/Analysis/ValueTracking.cpp#LL1088C75-L1088C75 Because demanded bits simplification reimplements the known bits calculation for performance reasons, this is lost in that case.

The right fix here would be to make sure that the special-case known bits calculation for and is shared between ValueTracking and SimplifyDemanded.

[goldstein.w.n]

In D142300#4071621, @nikic wrote:

This doesn't make sense to me. If the value is known all zeroes, then the value should fold to zero, at which point the icmp becomes trivial (not necessarily in InstSimplify, but in InstCombine).

The basic pattern from your tests already folds to zero: https://llvm.godbolt.org/z/EWTd4P3aY The pattern with the zero comparison does not: https://llvm.godbolt.org/z/xnv4joe9G

At a guess, this is because we specially handle values used inside return instructions in https://github.com/llvm/llvm-project/blob/8e7c1b9a3d5f08046261ca0b7e5d319a4c4c9b25/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp#L3111 -- we should possibly stop doing that, because it gives a misleading picture of which folds work and which don't.

Ands that fold to constants based on known bits are intended to reliably fold as part of demanded bits simplification here: https://github.com/llvm/llvm-project/blob/8e7c1b9a3d5f08046261ca0b7e5d319a4c4c9b25/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp#L200

The problem is that the pattern you are testing is special-cased in ValueTracking only: https://github.com/llvm/llvm-project/blob/8e7c1b9a3d5f08046261ca0b7e5d319a4c4c9b25/llvm/lib/Analysis/ValueTracking.cpp#LL1088C75-L1088C75 Because demanded bits simplification reimplements the known bits calculation for performance reasons, this is lost in that case.

The right fix here would be to make sure that the special-case known bits calculation for and is shared between ValueTracking and SimplifyDemanded.

I see. That makes sense and will do for v2 (was very confused why it works for cmp against non-zero, but not against zero). Any chance you can review D142271 first? I think the way to do this is to factor out a helper method and would be nice to get both patterns / not have inter-patch dependencies.

[goldstein.w.n]

In D142300#4071621, @nikic wrote:

This doesn't make sense to me. If the value is known all zeroes, then the value should fold to zero, at which point the icmp becomes trivial (not necessarily in InstSimplify, but in InstCombine).

The basic pattern from your tests already folds to zero: https://llvm.godbolt.org/z/EWTd4P3aY The pattern with the zero comparison does not: https://llvm.godbolt.org/z/xnv4joe9G

At a guess, this is because we specially handle values used inside return instructions in https://github.com/llvm/llvm-project/blob/8e7c1b9a3d5f08046261ca0b7e5d319a4c4c9b25/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp#L3111 -- we should possibly stop doing that, because it gives a misleading picture of which folds work and which don't.

Ands that fold to constants based on known bits are intended to reliably fold as part of demanded bits simplification here: https://github.com/llvm/llvm-project/blob/8e7c1b9a3d5f08046261ca0b7e5d319a4c4c9b25/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp#L200

The problem is that the pattern you are testing is special-cased in ValueTracking only: https://github.com/llvm/llvm-project/blob/8e7c1b9a3d5f08046261ca0b7e5d319a4c4c9b25/llvm/lib/Analysis/ValueTracking.cpp#LL1088C75-L1088C75 Because demanded bits simplification reimplements the known bits calculation for performance reasons, this is lost in that case.

The right fix here would be to make sure that the special-case known bits calculation for and is shared between ValueTracking and SimplifyDemanded.

Dropping this in favor of: https://reviews.llvm.org/D142429

llvm/lib/Analysis/InstructionSimplify.cpp

static Value *simplifyICmpWithZero(CmpInst::Predicate Pred, Value *LHS,
   switch (Pred) {
   default:
     llvm_unreachable("Unknown ICmp predicate!");
   case ICmpInst::ICMP_ULT:
     return getFalse(ITy);
   case ICmpInst::ICMP_UGE:
     return getTrue(ITy);
   case ICmpInst::ICMP_EQ:
-  case ICmpInst::ICMP_ULE:
+  case ICmpInst::ICMP_ULE: {
     if (isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT, Q.IIQ.UseInstrInfo))
       return getFalse(ITy);
-    break;
+    KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
+    if (LHSKnown.Zero.isAllOnes())
+      return getTrue(ITy);
+  } break;
   case ICmpInst::ICMP_NE:
-  case ICmpInst::ICMP_UGT:
+  case ICmpInst::ICMP_UGT: {
     if (isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT, Q.IIQ.UseInstrInfo))
       return getTrue(ITy);
-    break;
+    KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
+    if (LHSKnown.Zero.isAllOnes())
+      return getFalse(ITy);
+  } break;
   case ICmpInst::ICMP_SLT: {
     KnownBits LHSKnown = computeKnownBits(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
     if (LHSKnown.isNegative())
       return getTrue(ITy);
     if (LHSKnown.isNonNegative())
       return getFalse(ITy);
     break;
   }

llvm/test/Transforms/InstSimplify/icmp-constant.ll

 ;
   %c = icmp ult <2 x i8> %x, <i8 undef, i8 poison>
   ret <2 x i1> %c
 }
 
 
 define i1 @cmp_ne_0_is_false(i32 %x) {
 ; CHECK-LABEL: @cmp_ne_0_is_false(
-; CHECK-NEXT:    [[Y:%.*]] = add i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[Z:%.*]] = and i32 [[X]], [[Y]]
-; CHECK-NEXT:    [[B:%.*]] = and i32 [[Z]], 1
-; CHECK-NEXT:    [[E:%.*]] = icmp ne i32 [[B]], 0
-; CHECK-NEXT:    ret i1 [[E]]
+; CHECK-NEXT:    ret i1 false
 ;
   %y = add i32 %x, 1
   %z = and i32 %x, %y
   %b = and i32 %z, 1
   %e = icmp ne i32 %b, 0
   ret i1 %e
 }
 
 define i1 @cmp_eq_0_is_true(i32 %x) {
 ; CHECK-LABEL: @cmp_eq_0_is_true(
-; CHECK-NEXT:    [[Y:%.*]] = add i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[Z:%.*]] = and i32 [[X]], [[Y]]
-; CHECK-NEXT:    [[B:%.*]] = and i32 [[Z]], 1
-; CHECK-NEXT:    [[E:%.*]] = icmp eq i32 [[B]], 0
-; CHECK-NEXT:    ret i1 [[E]]
+; CHECK-NEXT:    ret i1 true
 ;
   %y = add i32 %x, 1
   %z = and i32 %x, %y
   %b = and i32 %z, 1
   %e = icmp eq i32 %b, 0
   ret i1 %e
 }
 
 define <2 x i1> @cmp_ule_0_is_true(<2 x i32> %x) {
 ; CHECK-LABEL: @cmp_ule_0_is_true(
-; CHECK-NEXT:    [[Y:%.*]] = add <2 x i32> [[X:%.*]], <i32 1, i32 1>
-; CHECK-NEXT:    [[Z:%.*]] = and <2 x i32> [[X]], [[Y]]
-; CHECK-NEXT:    [[B:%.*]] = and <2 x i32> [[Z]], <i32 1, i32 1>
-; CHECK-NEXT:    [[E:%.*]] = icmp ule <2 x i32> [[B]], zeroinitializer
-; CHECK-NEXT:    ret <2 x i1> [[E]]
+; CHECK-NEXT:    ret <2 x i1> <i1 true, i1 true>
 ;
   %y = add <2 x i32> %x, <i32 1, i32 1>
   %z = and <2 x i32> %x, %y
   %b = and <2 x i32> %z, <i32 1, i32 1>
   %e = icmp ule <2 x i32> %b, <i32 0, i32 0>
   ret <2 x i1> %e
 }
 
 define <2 x i1> @cmp_ugt_0_is_false(<2 x i32> %x) {
 ; CHECK-LABEL: @cmp_ugt_0_is_false(
-; CHECK-NEXT:    [[Y:%.*]] = add <2 x i32> [[X:%.*]], <i32 1, i32 1>
-; CHECK-NEXT:    [[Z:%.*]] = and <2 x i32> [[X]], [[Y]]
-; CHECK-NEXT:    [[B:%.*]] = and <2 x i32> [[Z]], <i32 1, i32 1>
-; CHECK-NEXT:    [[E:%.*]] = icmp ugt <2 x i32> [[B]], zeroinitializer
-; CHECK-NEXT:    ret <2 x i1> [[E]]
+; CHECK-NEXT:    ret <2 x i1> zeroinitializer
 ;
   %y = add <2 x i32> %x, <i32 1, i32 1>
   %z = and <2 x i32> %x, %y
   %b = and <2 x i32> %z, <i32 1, i32 1>
   %e = icmp ugt <2 x i32> %b, <i32 0, i32 0>
   ret <2 x i1> %e
 }