[ValueTracking] Add logic for tracking lowbit of (and/xor/or X, (add/sub X, Odd))

[goldstein.w.n]

Summary

Any case of logicop + add/sub(Odd) we can prove the low bit is either
zero/non-zero.

Alive2 Links:

xor:
    sub x, C: https://alive2.llvm.org/ce/z/aaABdS
    sub C, x: https://alive2.llvm.org/ce/z/2W-ZJ7
    add C, x: https://alive2.llvm.org/ce/z/pzDkte
or:
    sub x, C: https://alive2.llvm.org/ce/z/xd-bcP
    sub C, x: https://alive2.llvm.org/ce/z/p8hXJF
    add C, x: https://alive2.llvm.org/ce/z/osmkB6
and:
    sub x, C: https://alive2.llvm.org/ce/z/D_NNxR
    sub C, x: https://alive2.llvm.org/ce/z/N_5C62
    add C, x: https://alive2.llvm.org/ce/z/4cy7a4

[goldstein.w.n]

Make and/xor/or helper public

[goldstein.w.n]

Rebase and use blsi/blsmsk api

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase + apply changes from D142271

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[nikic]

Can you please split this into an NFC patch that splits off analyzeKnownBitsFromAndXorOr() without changing logic, and then one that implements the new folds? (D142429 could be based on either one.)

[goldstein.w.n]

Rebase after splitting

[goldstein.w.n]

In D142427#4089086, @nikic wrote:

Can you please split this into an NFC patch that splits off analyzeKnownBitsFromAndXorOr() without changing logic, and then one that implements the new folds? (D142429 could be based on either one.)

Done see D142849

[goldstein.w.n]

ping.

[goldstein.w.n]

ping.

[goldstein.w.n]

ping @nikic

[goldstein.w.n]

Rebase

[goldstein.w.n]

ping.

[nikic]

It looks like the tests have coverage for the newly added or/xor with add cases -- but this patch also adds sub cases that don't have any corresponding test change? Either the sub cases should be dropped, or they should be tested.

[goldstein.w.n]

Rebase

[goldstein.w.n]

In D142427#4138229, @nikic wrote:

It looks like the tests have coverage for the newly added or/xor with add cases -- but this patch also adds sub cases that don't have any corresponding test change? Either the sub cases should be dropped, or they should be tested.

Added new tests to cover all new cases. Removed some of the less useful existing tests.

[nikic]

LGTM

[goldstein.w.n]

Rebase

llvm/lib/Analysis/ValueTracking.cpp

if (HasKnownOne &&
       KnownOut = XBits.blsmsk();
     }
     break;
   default:
     llvm_unreachable("Invalid Op used in 'analyzeKnownBitsFromAndXorOr'");
   }
 
   // and(x, add (x, -1)) is a common idiom that always clears the low bit;
+  // xor/or(x, add (x, -1)) is an idiom that will always set the low bit.
   // here we handle the more general case of adding any odd number by
-  // matching the form and(x, add(x, y)) where y is odd.
+  // matching the form and/xor/or(x, add(x, y)) where y is odd.
   // TODO: This could be generalized to clearing any bit set in y where the
   // following bit is known to be unset in y.
-  if (IsAnd && !KnownOut.Zero[0] && !KnownOut.One[0] &&
-      match(I, m_c_BinOp(m_Value(X), m_c_Add(m_Deferred(X), m_Value(Y))))) {
+  if (!KnownOut.Zero[0] && !KnownOut.One[0] &&
+      (match(I, m_c_BinOp(m_Value(X), m_c_Add(m_Deferred(X), m_Value(Y)))) ||
+       match(I, m_c_BinOp(m_Value(X), m_Sub(m_Deferred(X), m_Value(Y)))) ||
+       match(I, m_c_BinOp(m_Value(X), m_Sub(m_Value(Y), m_Deferred(X)))))) {
     KnownBits KnownY(BitWidth);
     computeKnownBits(Y, DemandedElts, KnownY, Depth + 1, Q);
-    if (KnownY.countMinTrailingOnes() > 0)
+    if (KnownY.countMinTrailingOnes() > 0) {
+      if (IsAnd)
         KnownOut.Zero.setBit(0);
+      else
+        KnownOut.One.setBit(0);
+    }
   }
   return KnownOut;
 }
 
 // Public so this can be used in `SimplifyDemandedUseBits`.
 KnownBits llvm::analyzeKnownBitsFromAndXorOr(
     const Operator *I, const KnownBits &KnownLHS, const KnownBits &KnownRHS,
     unsigned Depth, const DataLayout &DL, AssumptionCache *AC,

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 define <2 x i1> @sub_XY_and_bit0_is_zero(<2 x i8> %x, <2 x i8> %C) nounwind {
 ; CHECK-LABEL: @sub_XY_and_bit0_is_zero(
-; CHECK-NEXT:    [[C1:%.*]] = or <2 x i8> [[C:%.*]], <i8 9, i8 9>
-; CHECK-NEXT:    [[Y:%.*]] = sub <2 x i8> [[X:%.*]], [[C1]]
-; CHECK-NEXT:    [[W:%.*]] = and <2 x i8> [[Y]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq <2 x i8> [[W]], <i8 -1, i8 -1>
-; CHECK-NEXT:    ret <2 x i1> [[R]]
+; CHECK-NEXT:    ret <2 x i1> zeroinitializer
 ;
   %C1 = or <2 x i8> %C, <i8 9, i8 9>
   %y = sub <2 x i8> %x, %C1
   %w = and <2 x i8> %x, %y
   %r = icmp eq <2 x i8> %w, <i8 -1, i8 -1>
   ret <2 x i1> %r
 }
 
 define i1 @sub_XY_xor_bit0_is_one(i8 %x, i8 %C) nounwind {
 ; CHECK-LABEL: @sub_XY_xor_bit0_is_one(
-; CHECK-NEXT:    [[C1:%.*]] = or i8 [[C:%.*]], 1
-; CHECK-NEXT:    [[Y:%.*]] = sub i8 [[X:%.*]], [[C1]]
-; CHECK-NEXT:    [[W:%.*]] = xor i8 [[Y]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[W]], 10
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %C1 = or i8 %C, 1
   %y = sub i8 %x, %C1
   %w = xor i8 %x, %y
   %r = icmp eq i8 %w, 10
   ret i1 %r
 }
 
 define i1 @sub_XY_or_bit0_is_one(i8 %x, i8 %C) nounwind {
 ; CHECK-LABEL: @sub_XY_or_bit0_is_one(
-; CHECK-NEXT:    [[C1:%.*]] = or i8 [[C:%.*]], 1
-; CHECK-NEXT:    [[Y:%.*]] = sub i8 [[X:%.*]], [[C1]]
-; CHECK-NEXT:    [[W:%.*]] = or i8 [[Y]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[W]], 10
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %C1 = or i8 %C, 1
   %y = sub i8 %x, %C1
   %w = or i8 %x, %y
   %r = icmp eq i8 %w, 10
   ret i1 %r
 }
 
 define i1 @sub_YX_and_bit0_is_zero(i8 %x, i8 %C) nounwind {
 ; CHECK-LABEL: @sub_YX_and_bit0_is_zero(
-; CHECK-NEXT:    [[C1:%.*]] = or i8 [[C:%.*]], 1
-; CHECK-NEXT:    [[Y:%.*]] = sub i8 [[C1]], [[X:%.*]]
-; CHECK-NEXT:    [[W:%.*]] = and i8 [[Y]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[W]], -1
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %C1 = or i8 %C, 1
   %y = sub i8 %C1, %x
   %w = and i8 %x, %y
   %r = icmp eq i8 %w, -1
   ret i1 %r
 }
 
 define <2 x i1> @sub_YX_xor_bit0_is_one(<2 x i8> %x, <2 x i8> %C) nounwind {
 ; CHECK-LABEL: @sub_YX_xor_bit0_is_one(
-; CHECK-NEXT:    [[C1:%.*]] = or <2 x i8> [[C:%.*]], <i8 1, i8 1>
-; CHECK-NEXT:    [[Y:%.*]] = sub <2 x i8> [[C1]], [[X:%.*]]
-; CHECK-NEXT:    [[W:%.*]] = xor <2 x i8> [[Y]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq <2 x i8> [[W]], <i8 12, i8 12>
-; CHECK-NEXT:    ret <2 x i1> [[R]]
+; CHECK-NEXT:    ret <2 x i1> zeroinitializer
 ;
   %C1 = or <2 x i8> %C, <i8 1, i8 1>
   %y = sub <2 x i8> %C1, %x
   %w = xor <2 x i8> %x, %y
   %r = icmp eq <2 x i8> %w, <i8 12, i8 12>
   ret <2 x i1> %r
 }
 
 define i1 @sub_YX_or_bit0_is_one(i8 %x, i8 %C) nounwind {
 ; CHECK-LABEL: @sub_YX_or_bit0_is_one(
-; CHECK-NEXT:    [[C1:%.*]] = or i8 [[C:%.*]], 1
-; CHECK-NEXT:    [[Y:%.*]] = sub i8 [[C1]], [[X:%.*]]
-; CHECK-NEXT:    [[W:%.*]] = or i8 [[Y]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[W]], 32
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %C1 = or i8 %C, 1
   %y = sub i8 %C1, %x
   %w = or i8 %x, %y
   %r = icmp eq i8 %w, 32
   ret i1 %r
 }
 
 define i1 @add_YX_xor_bit0_is_one(i8 %x, i8 %C) nounwind {
 ; CHECK-LABEL: @add_YX_xor_bit0_is_one(
-; CHECK-NEXT:    [[C1:%.*]] = or i8 [[C:%.*]], 1
-; CHECK-NEXT:    [[Y:%.*]] = add i8 [[C1]], [[X:%.*]]
-; CHECK-NEXT:    [[W:%.*]] = xor i8 [[Y]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[W]], 32
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %C1 = or i8 %C, 1
   %y = add i8 %C1, %x
   %w = xor i8 %x, %y
   %r = icmp eq i8 %w, 32
   ret i1 %r
 }
 
 define <2 x i1> @add_XY_or_bit0_is_one(<2 x i8> %x, <2 x i8> %C) nounwind {
 ; CHECK-LABEL: @add_XY_or_bit0_is_one(
-; CHECK-NEXT:    [[C1:%.*]] = or <2 x i8> [[C:%.*]], <i8 1, i8 1>
-; CHECK-NEXT:    [[Y:%.*]] = add <2 x i8> [[C1]], [[X:%.*]]
-; CHECK-NEXT:    [[W:%.*]] = or <2 x i8> [[Y]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq <2 x i8> [[W]], <i8 90, i8 90>
-; CHECK-NEXT:    ret <2 x i1> [[R]]
+; CHECK-NEXT:    ret <2 x i1> zeroinitializer
 ;
   %C1 = or <2 x i8> %C, <i8 1, i8 1>
   %y = add <2 x i8> %C1, %x
   %w = or <2 x i8> %x, %y
   %r = icmp eq <2 x i8> %w, <i8 90, i8 90>
   ret <2 x i1> %r
 }