[InstCombine] Use `analyzeKnownBitsFromAndXorOr` in `SimplifyDemandedUseBits` for and/xor/or

[goldstein.w.n]

Summary

There are extra patterns that have for these three logic operations
that aren't covered in SimplifyDemandedUseBits. To avoid duplicating
the code, just use analyzeKnownBitsFromAndXorOr in
SimplifyDemandedUseBits to get full coverage.

[nikic]

This is going to unnecessarily recompute known bits we already have. Please go with the helpers instead. Doing a recursive computeKnownBits() call for an operand we didn't check yet is fine, but we shouldn't recompute the known bits we already have.

[goldstein.w.n]

Use helper instead of computeknownbits

[goldstein.w.n]

In D142429#4076067, @nikic wrote:

This is going to unnecessarily recompute known bits we already have. Please go with the helpers instead. Doing a recursive computeKnownBits() call for an operand we didn't check yet is fine, but we shouldn't recompute the known bits we already have.

Done in V2. Made the AndXorOr helper public in previous patch (D142427) so now just goes through analyzeKnownBitsFromAndXorOr.

[goldstein.w.n]

Rebase

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

198–199

You can use cast<Operator>(I) here and drop the if. Every Instruction is an Operator.

[goldstein.w.n]

Rebase + switch case

[nikic]

LGTM

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

case Instruction::And: {
     // If either the LHS or the RHS are Zero, the result is zero.
     if (SimplifyDemandedBits(I, 1, DemandedMask, RHSKnown, Depth + 1) ||
         SimplifyDemandedBits(I, 0, DemandedMask & ~RHSKnown.Zero, LHSKnown,
                              Depth + 1))
       return I;
     assert(!RHSKnown.hasConflict() && "Bits known to be one AND zero?");
     assert(!LHSKnown.hasConflict() && "Bits known to be one AND zero?");
 
-    Known = LHSKnown & RHSKnown;
+    Known = analyzeKnownBitsFromAndXorOr(cast<Operator>(I), LHSKnown, RHSKnown,
+                                         Depth, DL, &AC, CxtI, &DT);
 
     // If the client is only demanding bits that we know, return the known
     // constant.
     if (DemandedMask.isSubsetOf(Known.Zero | Known.One))
       return Constant::getIntegerValue(VTy, Known.One);
 
     // If all of the demanded bits are known 1 on one side, return the other.
     // These bits cannot contribute to the result of the 'and'.
case Instruction::Or: {
     // If either the LHS or the RHS are One, the result is One.
     if (SimplifyDemandedBits(I, 1, DemandedMask, RHSKnown, Depth + 1) ||
         SimplifyDemandedBits(I, 0, DemandedMask & ~RHSKnown.One, LHSKnown,
                              Depth + 1))
       return I;
     assert(!RHSKnown.hasConflict() && "Bits known to be one AND zero?");
     assert(!LHSKnown.hasConflict() && "Bits known to be one AND zero?");
 
-    Known = LHSKnown | RHSKnown;
+    Known = analyzeKnownBitsFromAndXorOr(cast<Operator>(I), LHSKnown, RHSKnown,
+                                         Depth, DL, &AC, CxtI, &DT);
 
     // If the client is only demanding bits that we know, return the known
     // constant.
     if (DemandedMask.isSubsetOf(Known.Zero | Known.One))
       return Constant::getIntegerValue(VTy, Known.One);
 
     // If all of the demanded bits are known zero on one side, return the other.
     // These bits cannot contribute to the result of the 'or'.
if (DemandedMask == 1 &&
       Builder.SetInsertPoint(I);
       auto *Xor = Builder.CreateXor(LHS, RHS);
       return Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, Xor);
     }
 
     assert(!RHSKnown.hasConflict() && "Bits known to be one AND zero?");
     assert(!LHSKnown.hasConflict() && "Bits known to be one AND zero?");
 
-    Known = LHSKnown ^ RHSKnown;
+    Known = analyzeKnownBitsFromAndXorOr(cast<Operator>(I), LHSKnown, RHSKnown,
+                                         Depth, DL, &AC, CxtI, &DT);
 
     // If the client is only demanding bits that we know, return the known
     // constant.
     if (DemandedMask.isSubsetOf(Known.Zero | Known.One))
       return Constant::getIntegerValue(VTy, Known.One);
 
     // If all of the demanded bits are known zero on one side, return the other.
     // These bits cannot contribute to the result of the 'xor'.

llvm/test/Analysis/ValueTracking/knownbits-and-or-xor-lowbit.ll

;
   %w = or <2 x i8> %x, %y
   %r = icmp eq <2 x i8> %w, <i8 90, i8 90>
   ret <2 x i1> %r
 }
 
 ;; These tests are just to check if it can simplify using demanded bits path.
 define <2 x i32> @add_and_eval_vec(<2 x i32> %x, <2 x i32> %C) {
 ; CHECK-LABEL: @add_and_eval_vec(
-; CHECK-NEXT:    [[Y:%.*]] = add <2 x i32> [[X:%.*]], <i32 1, i32 1>
-; CHECK-NEXT:    [[Z:%.*]] = and <2 x i32> [[Y]], [[X]]
-; CHECK-NEXT:    [[B:%.*]] = shl <2 x i32> [[Z]], <i32 31, i32 31>
-; CHECK-NEXT:    ret <2 x i32> [[B]]
+; CHECK-NEXT:    ret <2 x i32> zeroinitializer
 ;
   %y = add <2 x i32> %x, <i32 1, i32 1>
   %z = and <2 x i32> %x, %y
   ;; shl so we don't commute the and
   %b = shl <2 x i32> %z, <i32 31, i32 31>
   ret <2 x i32> %b
 }
 
 
 define <2 x i32> @add_xor_eval_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @add_xor_eval_vec(
-; CHECK-NEXT:    [[Y:%.*]] = add <2 x i32> [[X:%.*]], <i32 1, i32 1>
-; CHECK-NEXT:    [[Z:%.*]] = xor <2 x i32> [[Y]], [[X]]
-; CHECK-NEXT:    [[B:%.*]] = and <2 x i32> [[Z]], <i32 1, i32 1>
-; CHECK-NEXT:    ret <2 x i32> [[B]]
+; CHECK-NEXT:    ret <2 x i32> <i32 1, i32 1>
 ;
   %y = add <2 x i32> %x, <i32 1, i32 1>
   %z = xor <2 x i32> %y, %x
   %b = and <2 x i32> %z, <i32 1, i32 1>
   ret <2 x i32> %b
 }
 
 define <2 x i32> @add_or_eval_vec(<2 x i32> %x, <2 x i32> %C) {
 ; CHECK-LABEL: @add_or_eval_vec(
-; CHECK-NEXT:    [[Y:%.*]] = add <2 x i32> [[X:%.*]], <i32 1, i32 1>
-; CHECK-NEXT:    [[Z:%.*]] = or <2 x i32> [[Y]], [[X]]
-; CHECK-NEXT:    [[B:%.*]] = and <2 x i32> [[Z]], <i32 1, i32 1>
-; CHECK-NEXT:    ret <2 x i32> [[B]]
+; CHECK-NEXT:    ret <2 x i32> <i32 1, i32 1>
 ;
   %y = add <2 x i32> %x, <i32 1, i32 1>
   %z = or <2 x i32> %y, %x
   %b = and <2 x i32> %z, <i32 1, i32 1>
   ret <2 x i32> %b
 }

llvm/test/Analysis/ValueTracking/knownbits-bmi-pattern.ll

;
   %x2 = sub <2 x i32> %x1, <i32 1, i32 1>
   %x3 = xor <2 x i32> %x2, %x1
   %z = icmp ne <2 x i32> %x3, <i32 8, i32 8>
   ret <2 x i1> %z
 }
 
 define i1 @blsmsk_ge_is_false(i32 %x) {
 ; CHECK-LABEL: @blsmsk_ge_is_false(
-; CHECK-NEXT:    [[X1:%.*]] = or i32 [[X:%.*]], 10
-; CHECK-NEXT:    [[X2:%.*]] = add nsw i32 [[X1]], -1
-; CHECK-NEXT:    [[X3:%.*]] = xor i32 [[X1]], [[X2]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp ugt i32 [[X3]], 7
-; CHECK-NEXT:    ret i1 [[Z]]
+; CHECK-NEXT:    ret i1 false
 ;
   %x1 = or i32 %x, 10
   %x2 = sub i32 %x1, 1
   %x3 = xor i32 %x1, %x2
   %z = icmp uge i32 %x3, 8
   ret i1 %z
 }
 
 define <2 x i1> @blsmsk_gt_is_false_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @blsmsk_gt_is_false_vec(
-; CHECK-NEXT:    [[X1:%.*]] = or <2 x i32> [[X:%.*]], <i32 10, i32 10>
-; CHECK-NEXT:    [[X2:%.*]] = add nsw <2 x i32> [[X1]], <i32 -1, i32 -1>
-; CHECK-NEXT:    [[X3:%.*]] = xor <2 x i32> [[X2]], [[X1]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp ugt <2 x i32> [[X3]], <i32 8, i32 8>
-; CHECK-NEXT:    ret <2 x i1> [[Z]]
+; CHECK-NEXT:    ret <2 x i1> zeroinitializer
 ;
   %x1 = or <2 x i32> %x, <i32 10, i32 10>
   %x2 = sub <2 x i32> %x1, <i32 1, i32 1>
   %x3 = xor <2 x i32> %x2, %x1
   %z = icmp ugt <2 x i32> %x3, <i32 8, i32 8>
   ret <2 x i1> %z
 }
 
;
   %x2 = sub i32 %x1, 1
   %x3 = xor i32 %x2, %x1
   %z = add i32 %x3, 32
   ret i32 %z
 }
 
 define <2 x i32> @blsmsk_add_eval_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @blsmsk_add_eval_vec(
-; CHECK-NEXT:    [[X1:%.*]] = or <2 x i32> [[X:%.*]], <i32 9, i32 9>
-; CHECK-NEXT:    [[X2:%.*]] = add nsw <2 x i32> [[X1]], <i32 -1, i32 -1>
-; CHECK-NEXT:    [[X3:%.*]] = xor <2 x i32> [[X2]], [[X1]]
-; CHECK-NEXT:    [[Z:%.*]] = or <2 x i32> [[X3]], <i32 32, i32 32>
-; CHECK-NEXT:    ret <2 x i32> [[Z]]
+; CHECK-NEXT:    ret <2 x i32> <i32 33, i32 33>
 ;
   %x1 = or <2 x i32> %x, <i32 9, i32 9>
   %x2 = add <2 x i32> %x1, <i32 -1, i32 -1>
   %x3 = xor <2 x i32> %x2, %x1
   %z = add <2 x i32> %x3, <i32 32, i32 32>
   ret <2 x i32> %z
 }
 
 define i32 @blsmsk_sub_eval(i32 %x) {
 ; CHECK-LABEL: @blsmsk_sub_eval(
-; CHECK-NEXT:    [[X1:%.*]] = or i32 [[X:%.*]], 9
-; CHECK-NEXT:    [[X2:%.*]] = add i32 [[X1]], 31
-; CHECK-NEXT:    [[X3:%.*]] = xor i32 [[X1]], [[X2]]
-; CHECK-NEXT:    [[Z:%.*]] = or i32 [[X3]], -32
-; CHECK-NEXT:    ret i32 [[Z]]
+; CHECK-NEXT:    ret i32 -31
 ;
   %x1 = or i32 %x, 9
   %x2 = sub i32 %x1, 1
   %x3 = xor i32 %x1, %x2
   %z = sub i32 %x3, 32
   ret i32 %z
 }
 
 define i32 @blsmsk_or_eval(i32 %x) {
 ; CHECK-LABEL: @blsmsk_or_eval(
 ; CHECK-NEXT:    ret i32 33
 ;
   %x1 = or i32 %x, 129
   %x2 = sub i32 %x1, 1
   %x3 = xor i32 %x2, %x1
   %z = or i32 %x3, 32
   ret i32 %z
 }
 
 define <2 x i32> @blsmsk_or_eval_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @blsmsk_or_eval_vec(
-; CHECK-NEXT:    [[X1:%.*]] = or <2 x i32> [[X:%.*]], <i32 9, i32 9>
-; CHECK-NEXT:    [[X2:%.*]] = add nsw <2 x i32> [[X1]], <i32 -1, i32 -1>
-; CHECK-NEXT:    [[X3:%.*]] = xor <2 x i32> [[X2]], [[X1]]
-; CHECK-NEXT:    [[Z:%.*]] = or <2 x i32> [[X3]], <i32 32, i32 32>
-; CHECK-NEXT:    ret <2 x i32> [[Z]]
+; CHECK-NEXT:    ret <2 x i32> <i32 33, i32 33>
 ;
   %x1 = or <2 x i32> %x, <i32 9, i32 9>
   %x2 = add <2 x i32> %x1, <i32 -1, i32 -1>
   %x3 = xor <2 x i32> %x2, %x1
   %z = or <2 x i32> %x3, <i32 32, i32 32>
   ret <2 x i32> %z
 }
 
;
   ret i1 %z
 }
 
 define i1 @blsmsk_gt_is_false_assume(i32 %x) {
 ; CHECK-LABEL: @blsmsk_gt_is_false_assume(
 ; CHECK-NEXT:    [[LB:%.*]] = and i32 [[X:%.*]], 2
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[LB]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    [[X2:%.*]] = add nsw i32 [[X]], -1
-; CHECK-NEXT:    [[X3:%.*]] = xor i32 [[X2]], [[X]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp ugt i32 [[X3]], 8
-; CHECK-NEXT:    ret i1 [[Z]]
+; CHECK-NEXT:    ret i1 false
 ;
   %lb = and i32 %x, 2
   %cmp = icmp ne i32 %lb, 0
   call void @llvm.assume(i1 %cmp)
   %x2 = sub i32 %x, 1
   %x3 = xor i32 %x2, %x
   %z = icmp ugt i32 %x3, 8
   ret i1 %z
;
   ret <2 x i32> %z
 }
 
 define i32 @blsmsk_sub_eval_assume(i32 %x) {
 ; CHECK-LABEL: @blsmsk_sub_eval_assume(
 ; CHECK-NEXT:    [[LB:%.*]] = and i32 [[X:%.*]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[LB]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    [[X2:%.*]] = add i32 [[X]], 31
-; CHECK-NEXT:    [[X3:%.*]] = xor i32 [[X2]], [[X]]
-; CHECK-NEXT:    [[Z:%.*]] = or i32 [[X3]], -32
-; CHECK-NEXT:    ret i32 [[Z]]
+; CHECK-NEXT:    ret i32 -31
 ;
   %lb = and i32 %x, 1
   %cmp = icmp ne i32 %lb, 0
   call void @llvm.assume(i1 %cmp)
   %x2 = sub i32 %x, 1
   %x3 = xor i32 %x, %x2
   %z = sub i32 %x3, 32
   ret i32 %z
;
   %x2 = sub <2 x i32> <i32 0, i32 0>, %x1
   %x3 = and <2 x i32> %x1, %x2
   %z = icmp uge <2 x i32> %x3, <i32 8, i32 8>
   ret <2 x i1> %z
 }
 
 define i1 @blsi_gt_is_false(i32 %x) {
 ; CHECK-LABEL: @blsi_gt_is_false(
-; CHECK-NEXT:    [[X1:%.*]] = or i32 [[X:%.*]], 10
-; CHECK-NEXT:    [[X2:%.*]] = sub nsw i32 0, [[X1]]
-; CHECK-NEXT:    [[X3:%.*]] = and i32 [[X1]], [[X2]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp ugt i32 [[X3]], 8
-; CHECK-NEXT:    ret i1 [[Z]]
+; CHECK-NEXT:    ret i1 false
 ;
   %x1 = or i32 %x, 10
   %x2 = sub i32 0, %x1
   %x3 = and i32 %x2, %x1
   %z = icmp ugt i32 %x3, 8
   ret i1 %z
 }
 
;
   %x2 = sub i32 0, %x1
   %x3 = and i32 %x2, %x1
   %z = sub i32 %x3, 32
   ret i32 %z
 }
 
 define <2 x i32> @blsi_sub_eval_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @blsi_sub_eval_vec(
-; CHECK-NEXT:    [[X1:%.*]] = or <2 x i32> [[X:%.*]], <i32 33, i32 33>
-; CHECK-NEXT:    [[X2:%.*]] = sub nsw <2 x i32> zeroinitializer, [[X1]]
-; CHECK-NEXT:    [[X3:%.*]] = and <2 x i32> [[X1]], [[X2]]
-; CHECK-NEXT:    [[Z:%.*]] = or <2 x i32> [[X3]], <i32 -32, i32 -32>
-; CHECK-NEXT:    ret <2 x i32> [[Z]]
+; CHECK-NEXT:    ret <2 x i32> <i32 -31, i32 -31>
 ;
   %x1 = or <2 x i32> %x, <i32 33, i32 33>
   %x2 = sub <2 x i32> <i32 0, i32 0>, %x1
   %x3 = and <2 x i32> %x1, %x2
   %z = sub <2 x i32> %x3, <i32 32, i32 32>
   ret <2 x i32> %z
 }
 
 define i32 @blsi_or_eval(i32 %x) {
 ; CHECK-LABEL: @blsi_or_eval(
 ; CHECK-NEXT:    ret i32 33
 ;
   %x1 = or i32 %x, 129
   %x2 = sub i32 0, %x1
   %x3 = and i32 %x2, %x1
   %z = or i32 %x3, 32
   ret i32 %z
 }
 
 define <2 x i32> @blsi_xor_eval_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @blsi_xor_eval_vec(
-; CHECK-NEXT:    [[X1:%.*]] = or <2 x i32> [[X:%.*]], <i32 33, i32 33>
-; CHECK-NEXT:    [[X2:%.*]] = sub nsw <2 x i32> zeroinitializer, [[X1]]
-; CHECK-NEXT:    [[X3:%.*]] = and <2 x i32> [[X1]], [[X2]]
-; CHECK-NEXT:    [[Z1:%.*]] = or <2 x i32> [[X3]], <i32 32, i32 32>
-; CHECK-NEXT:    ret <2 x i32> [[Z1]]
+; CHECK-NEXT:    ret <2 x i32> <i32 33, i32 33>
 ;
   %x1 = or <2 x i32> %x, <i32 33, i32 33>
   %x2 = sub <2 x i32> <i32 0, i32 0>, %x1
   %x3 = and <2 x i32> %x2, %x1
   %z = xor <2 x i32> %x3, <i32 32, i32 32>
   ret <2 x i32> %z
 }
 
;
   ret i1 %z
 }
 
 define i1 @blsi_ge_is_false_assume(i32 %x) {
 ; CHECK-LABEL: @blsi_ge_is_false_assume(
 ; CHECK-NEXT:    [[LB:%.*]] = and i32 [[X:%.*]], 4
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[LB]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    [[X2:%.*]] = sub nsw i32 0, [[X]]
-; CHECK-NEXT:    [[X3:%.*]] = and i32 [[X2]], [[X]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp ugt i32 [[X3]], 7
-; CHECK-NEXT:    ret i1 [[Z]]
+; CHECK-NEXT:    ret i1 false
 ;
   %lb = and i32 %x, 4
   %cmp = icmp ne i32 %lb, 0
   call void @llvm.assume(i1 %cmp)
   %x2 = sub i32 0, %x
   %x3 = and i32 %x2, %x
   %z = icmp uge i32 %x3, 8
   ret i1 %z

llvm/test/Transforms/InstCombine/ctpop-pow2.ll

;
   %sub = sub <2 x i64> <i64 0 ,i64 0>, %x
   %and = and <2 x i64> %sub, %x
   %cnt = call <2 x i64> @llvm.ctpop.v2i64(<2 x i64> %and)
   ret <2 x i64> %cnt
 }
 
 define <2 x i32> @ctpop_x_and_negx_vec_nz(<2 x i32> %x) {
 ; CHECK-LABEL: @ctpop_x_and_negx_vec_nz(
-; CHECK-NEXT:    [[X1:%.*]] = or <2 x i32> [[X:%.*]], <i32 1, i32 1>
-; CHECK-NEXT:    [[SUB:%.*]] = sub nsw <2 x i32> zeroinitializer, [[X1]]
-; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> [[X1]], [[SUB]]
-; CHECK-NEXT:    ret <2 x i32> [[AND]]
+; CHECK-NEXT:    ret <2 x i32> <i32 1, i32 1>
 ;
   %x1 = or <2 x i32> %x, <i32 1 ,i32 1>
   %sub = sub <2 x i32> <i32 0 ,i32 0>, %x1
   %and = and <2 x i32> %sub, %x1
   %cnt = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %and)
   ret <2 x i32> %cnt
 }