[InstCombine] improve fold for icmp_eq_and to icmp_ult

[Chenbing.Zheng]

Summary

In D95959, the improve analysis for "C >> X" broken the fold
((%x & C) == 0) --> %x u< (-C) iff (-C) is power of two.

It simplifies C, but fails to satisfy the fold condition.
This patch try to restore C before the fold.

[spatel]

This seems like it should be a known bits transform instead. Any value with high zeros should allow the transform, not just a 'lshr'.
For example, we might have a udiv of a constant:
https://alive2.llvm.org/ce/z/A5ZTf2

[Chenbing.Zheng]

address comment

[Chenbing.Zheng]

update tests

[spatel]

llvm/test/Transforms/InstCombine/lshr-and-negC-icmpeq-zero.ll

215

This is almost the same as @scalar_i32_lshr_and_negC_eq_X_is_constant1.

We would have better coverage if this is changed to use udiv instead of lshr. Also, change predicate to 'ne' so we are testing that code path too.

We should also have a negative test where the high bits are all clear except for the last necessary bit - that way, we will know that the known-bits calculation is correct.

[Chenbing.Zheng]

address comments

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1782

Make this comment more exact:

// Set high zeros of C2 to allow matching negated power-of-2.

1788–1789

I think this should be updated to use isNegatedPowerOf2 - if that's correct, you could even commit that change as a NFC patch before this one.

[Chenbing.Zheng]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1788–1789

I agree with you, https://reviews.llvm.org/D129103

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (Cmp.isEquality() && C1.isZero()) {
     // Restrict this fold to single-use 'and' (PR10267).
     // Replace (and X, (1 << size(X)-1) != 0) with X s< 0
     if (C2->isSignMask()) {
       Constant *Zero = Constant::getNullValue(X->getType());
       auto NewPred = isICMP_NE ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_SGE;
       return new ICmpInst(NewPred, X, Zero);
     }
 
+    APInt NewC2 = *C2;
+    KnownBits Know = computeKnownBits(And->getOperand(0), 0, And);
+    // Set high zeros of C2 to allow matching negated power-of-2.
+    NewC2 = *C2 + APInt::getHighBitsSet(C2->getBitWidth(),
+                                        Know.countMinLeadingZeros());
+
     // Restrict this fold only for single-use 'and' (PR10267).
     // ((%x & C) == 0) --> %x u< (-C)  iff (-C) is power of two.
-    if (C2->isNegatedPowerOf2()) {
-      Constant *NegBOC =
-          ConstantExpr::getNeg(cast<Constant>(And->getOperand(1)));
+    if (NewC2.isNegatedPowerOf2()) {
+      Constant *NegBOC = ConstantInt::get(And->getType(), -NewC2);
       auto NewPred = isICMP_NE ? ICmpInst::ICMP_UGE : ICmpInst::ICMP_ULT;
       return new ICmpInst(NewPred, X, NegBOC);
     }
   }
 
   // If the LHS is an 'and' of a truncate and we can widen the and/compare to
   // the input width without changing the value produced, eliminate the cast:
   //

llvm/test/Transforms/InstCombine/lshr-and-negC-icmpeq-zero.ll

;
   %and = and i32 %lshr, 4294967288  ; ~7
   store i32 %and, i32* %p  ; extra use of and
   %add = add i32 %lshr, %z  ; extra use of lshr
   store i32 %add, i32* %q
   %r = icmp eq i32 %and, 0
   ret i1 %r
 }
 
-; Negative tests
-
-; TODO: This could be reduced to lshr+icmp ult.
-
 define i1 @scalar_i32_lshr_and_negC_eq_X_is_constant1(i32 %y) {
 ; CHECK-LABEL: @scalar_i32_lshr_and_negC_eq_X_is_constant1(
 ; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 12345, [[Y:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[LSHR]], 16376
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[AND]], 0
+; CHECK-NEXT:    [[R:%.*]] = icmp ult i32 [[LSHR]], 8
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %lshr = lshr i32 12345, %y
   %and = and i32 %lshr, 4294967288  ; ~7
   %r = icmp eq i32 %and, 0
   ret i1 %r
 }
 
-; TODO: This could be reduced to lshr+icmp ult.
-
 define i1 @scalar_i32_lshr_and_negC_eq_X_is_constant2(i32 %y) {
 ; CHECK-LABEL: @scalar_i32_lshr_and_negC_eq_X_is_constant2(
-; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 268435456, [[Y:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[LSHR]], 536870904
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[AND]], 0
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i32 [[Y:%.*]], 25
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %lshr = lshr i32 268435456, %y
   %and = and i32 %lshr, 4294967288  ; ~7
   %r = icmp eq i32 %and, 0
   ret i1 %r
 }
+define i1 @scalar_i32_udiv_and_negC_eq_X_is_constant3(i32 %y) {
+; CHECK-LABEL: @scalar_i32_udiv_and_negC_eq_X_is_constant3(
+; CHECK-NEXT:    [[R:%.*]] = icmp ult i32 [[Y:%.*]], 1544
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %lshr = udiv  i32 12345, %y
+  %and = and i32 %lshr, 16376    ; 0x3ff8
+  %r = icmp ne i32 %and, 0
+  ret i1 %r
+}
+
+; Negative test
 
+define i1 @scalar_i32_lshr_and_negC_eq_X_is_constant_negtive(i32 %y) {
+; CHECK-LABEL: @scalar_i32_lshr_and_negC_eq_X_is_constant_negtive(
+; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 16384, [[Y:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[LSHR]], 16376
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[AND]], 0
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %lshr = lshr i32 16384, %y    ; 0x4000
+  %and = and i32 %lshr, 16376   ; 0x3ff8
+  %r = icmp eq i32 %and, 0
+  ret i1 %r
+}
 ; Check 'slt' predicate
 
 define i1 @scalar_i32_lshr_and_negC_slt(i32 %x, i32 %y) {
 ; CHECK-LABEL: @scalar_i32_lshr_and_negC_slt(
 ; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[R:%.*]] = icmp slt i32 [[LSHR]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;