[instCombine] Handle (X & C2) < C1 --> (X & C2) == 0

[craig.topper]

Summary

We already did (X & C2) > C1 --> (X & C2) != 0, if any bit set in (X & C2) will produce a result greater than C1. But there is an equivalent inverse condition with <= C1 (which will be canonicalized to < C1+1)

[spatel]

LGTM. The bit-logic looks right to me - but I miss Alive. :)
cc @nlopes

See inline for some nits.

lib/Transforms/InstCombine/InstCombineCompares.cpp

1720 ↗

(On Diff #115937)

Is this is a weird way of asking: !C2->isNullValue() ?

1722 ↗

(On Diff #115937)

The change to use getActiveBits() could be an NFC commit before this patch.

test/Transforms/InstCombine/icmp.ll

1141 ↗

(On Diff #115937)

Would be nice to have a test that uses constants at/near the limits. Something like:
define i1 @test67inverse(i8 %x) {

%and = and i8 %x, -128
%cmp = icmp ult i8 %and, 126
ret i1 %cmp

}

Could use vectors to add more testing diversity...assuming that works.

llvm/trunk/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (match(Or, m_Or(m_Value(LShr), m_Value(A))) &&
         Value *NewAnd = Builder.CreateAnd(A, NewOr, And->getName());
         Cmp.setOperand(0, NewAnd);
         return &Cmp;
       }
     }
   }
 
   // (X & C2) > C1 --> (X & C2) != 0, if any bit set in (X & C2) will produce a
-  // result greater than C1.
+ // result greater than C1. Also handle (X & C2) < C1 --> (X & C2) == 0.
+  if (!C2->isNullValue()) {
     unsigned NumTZ = C2->countTrailingZeros();
-  if (Cmp.getPredicate() == ICmpInst::ICMP_UGT && NumTZ < C2->getBitWidth() &&
+    if (Cmp.getPredicate() == ICmpInst::ICMP_UGT &&
         NumTZ >= C1->getActiveBits()) {
       Constant *Zero = Constant::getNullValue(And->getType());
       return new ICmpInst(ICmpInst::ICMP_NE, And, Zero);
     }
+    if (Cmp.getPredicate() == ICmpInst::ICMP_ULT &&
+        NumTZ >= C1->ceilLogBase2()) {
+      Constant *Zero = Constant::getNullValue(And->getType());
+      return new ICmpInst(ICmpInst::ICMP_EQ, And, Zero);
+    }
+  }
 
   return nullptr;
 }
 
 /// Fold icmp (and X, Y), C.
 Instruction *InstCombiner::foldICmpAndConstant(ICmpInst &Cmp,
                                                BinaryOperator *And,
                                                const APInt *C) {

llvm/trunk/test/Transforms/InstCombine/icmp.ll

;
   %and = and i32 %x, 127
   %cmp = icmp sgt i32 %and, 31
   ret i1 %cmp
 }
 
 define i1 @test67inverse(i32 %x) {
 ; CHECK-LABEL: @test67inverse(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 96
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[AND]], 32
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %and = and i32 %x, 127
   %cmp = icmp sle i32 %and, 31
   ret i1 %cmp
 }
 
 ; The test above relies on 3 different folds.
;
   %and = and <2 x i32> %x, <i32 127, i32 127>
   %cmp = icmp ugt <2 x i32> %and, <i32 31, i32 31>
   ret <2 x i1> %cmp
 }
 
 define <2 x i1> @test67vecinverse(<2 x i32> %x) {
 ; CHECK-LABEL: @test67vecinverse(
 ; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> [[X:%.*]], <i32 96, i32 96>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult <2 x i32> [[AND]], <i32 32, i32 32>
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <2 x i32> [[AND]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %and = and <2 x i32> %x, <i32 96, i32 96>
   %cmp = icmp sle <2 x i32> %and, <i32 31, i32 31>
   ret <2 x i1> %cmp
 }
 
 define i1 @test68(i32 %x) {