[InstCombine] Fold A + (B & ~A) to A | B

[nikic]

Summary

This adds two folds:

• A + (B & ~A) --> A | B (https://alive2.llvm.org/ce/z/N5fWZ9)
• A + ((A & B) ^ B) --> A | B (https://alive2.llvm.org/ce/z/so3jNz)

The reason why the second fold is necessary is that we consider this to be the canonical form if B is a constant. (I did check whether we can change that, but it looks like a number of folds depend on the current canonicalization, so I ended up adding both patterns here.)

[spatel]

Do you see any advantage or disadvantage of treating these as part of haveNoCommonBitsSet()?
https://alive2.llvm.org/ce/z/FNtH4K
We should manage to get the logic reductions already if the 'add' was replaced by 'or'.

[nikic]

Implement as part of haveNoCommonBitsSet() instead.

The second pattern (canonical form for constants) doesn't get fully folded in this case, so this will require an additional or fold. But that seems like something we'd want to do anyway.

[spatel]

In D124763#3485962, @nikic wrote:

Implement as part of haveNoCommonBitsSet() instead.

The second pattern (canonical form for constants) doesn't get fully folded in this case, so this will require an additional or fold. But that seems like something we'd want to do anyway.

Thanks - LGTM.

llvm/lib/Analysis/ValueTracking.cpp

// Look for an inverted mask: (X & ~M) op (Y & M).
     Value *M;
     if (match(LHS, m_c_And(m_Not(m_Value(M)), m_Value())) &&
         match(RHS, m_c_And(m_Specific(M), m_Value())))
       return true;
     if (match(RHS, m_c_And(m_Not(m_Value(M)), m_Value())) &&
         match(LHS, m_c_And(m_Specific(M), m_Value())))
       return true;
   }
+
+  // X op (Y & ~X)
+  if (match(RHS, m_c_And(m_Not(m_Specific(LHS)), m_Value())) ||
+      match(LHS, m_c_And(m_Not(m_Specific(RHS)), m_Value())))
+    return true;
+
+  // X op ((X & Y) ^ Y) -- this is the canonical form of the previous pattern
+  // for constant Y.
+  Value *Y;
+  if (match(RHS,
+            m_c_Xor(m_c_And(m_Specific(LHS), m_Value(Y)), m_Deferred(Y))) ||
+      match(LHS, m_c_Xor(m_c_And(m_Specific(RHS), m_Value(Y)), m_Deferred(Y))))
+    return true;
+
   // Look for: (A & B) op ~(A | B)
   {
     Value *A, *B;
     if (match(LHS, m_And(m_Value(A), m_Value(B))) &&
         match(RHS, m_Not(m_c_Or(m_Specific(A), m_Specific(B)))))
       return true;
     if (match(RHS, m_And(m_Value(A), m_Value(B))) &&
         match(LHS, m_Not(m_c_Or(m_Specific(A), m_Specific(B)))))

llvm/test/Transforms/InstCombine/add.ll

;
   %i1 = or i8 %i0, 15 ; no common bits
   call void @use(i8 %i1) ; extra use
   %r = add i8 %i1, 42
   ret i8 %r
 }
 
 define i8 @add_and_xor(i8 %x, i8 %y) {
 ; CHECK-LABEL: @add_and_xor(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X:%.*]], -1
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[XOR]], [[Y:%.*]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[AND]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %xor = xor i8 %x, -1
   %and = and i8 %xor, %y
   %add = add i8 %and, %x
   ret i8 %add
 }
 
;
   %and = and i8 %xor, %y
   %add = add i8 %and, %x
   ret i8 %add
 }
 
 define i8 @add_and_xor_commuted1(i8 %x, i8 %_y) {
 ; CHECK-LABEL: @add_and_xor_commuted1(
 ; CHECK-NEXT:    [[Y:%.*]] = udiv i8 42, [[_Y:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X:%.*]], -1
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[Y]], [[XOR]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[AND]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[Y]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %y = udiv i8 42, %_y ; thwart complexity-based canonicalization
   %xor = xor i8 %x, -1
   %and = and i8 %y, %xor
   %add = add i8 %and, %x
   ret i8 %add
 }
 
 define i8 @add_and_xor_commuted2(i8 %_x, i8 %y) {
 ; CHECK-LABEL: @add_and_xor_commuted2(
 ; CHECK-NEXT:    [[X:%.*]] = udiv i8 42, [[_X:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X]], -1
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[XOR]], [[Y:%.*]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[X]], [[AND]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[X]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %x = udiv i8 42, %_x ; thwart complexity-based canonicalization
   %xor = xor i8 %x, -1
   %and = and i8 %xor, %y
   %add = add i8 %x, %and
   ret i8 %add
 }
 
 define i8 @add_and_xor_commuted3(i8 %_x, i8 %_y) {
 ; CHECK-LABEL: @add_and_xor_commuted3(
 ; CHECK-NEXT:    [[X:%.*]] = udiv i8 42, [[_X:%.*]]
 ; CHECK-NEXT:    [[Y:%.*]] = udiv i8 42, [[_Y:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X]], -1
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[Y]], [[XOR]]
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i8 [[X]], [[AND]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[X]], [[Y]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %x = udiv i8 42, %_x ; thwart complexity-based canonicalization
   %y = udiv i8 42, %_y ; thwart complexity-based canonicalization
   %xor = xor i8 %x, -1
   %and = and i8 %y, %xor
   %add = add i8 %x, %and
   ret i8 %add
 }
 
 define i8 @add_and_xor_extra_use(i8 %x, i8 %y) {
 ; CHECK-LABEL: @add_and_xor_extra_use(
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X:%.*]], -1
 ; CHECK-NEXT:    call void @use(i8 [[XOR]])
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[XOR]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[AND]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[Y]], [[X]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %xor = xor i8 %x, -1
   call void @use(i8 %xor)
   %and = and i8 %xor, %y
   call void @use(i8 %and)
   %add = add i8 %and, %x
   ret i8 %add
 }
 
 define i8 @add_xor_and_const(i8 %x) {
 ; CHECK-LABEL: @add_xor_and_const(
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X:%.*]], 42
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[AND]], 42
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[XOR]], [[X]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %and = and i8 %x, 42
   %xor = xor i8 %and, 42
   %add = add i8 %xor, %x
   ret i8 %add
 }
 
;
   ret i8 %add
 }
 
 define i8 @add_xor_and_var(i8 %x, i8 %y) {
 ; CHECK-LABEL: @add_xor_and_var(
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[AND]], [[Y]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[XOR]], [[X]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %and = and i8 %x, %y
   call void @use(i8 %and)
   %xor = xor i8 %and, %y
   %add = add i8 %xor, %x
   ret i8 %add
 }
;
   ret i8 %add
 }
 
 define i8 @add_xor_and_var_commuted1(i8 %x, i8 %y) {
 ; CHECK-LABEL: @add_xor_and_var_commuted1(
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[AND]], [[Y]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[XOR]], [[X]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %and = and i8 %y, %x
   call void @use(i8 %and)
   %xor = xor i8 %and, %y
   %add = add i8 %xor, %x
   ret i8 %add
 }
 
 define i8 @add_xor_and_var_commuted2(i8 %x, i8 %_y) {
 ; CHECK-LABEL: @add_xor_and_var_commuted2(
 ; CHECK-NEXT:    [[Y:%.*]] = udiv i8 42, [[_Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[Y]], [[X:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[Y]], [[AND]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[XOR]], [[X]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %y = udiv i8 42, %_y ; thwart complexity-based canonicalization
   %and = and i8 %x, %y
   call void @use(i8 %and)
   %xor = xor i8 %y, %and
   %add = add i8 %xor, %x
   ret i8 %add
 }
 
 define i8 @add_xor_and_var_commuted3(i8 %x, i8 %_y) {
 ; CHECK-LABEL: @add_xor_and_var_commuted3(
 ; CHECK-NEXT:    [[Y:%.*]] = udiv i8 42, [[_Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[Y]], [[X:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[Y]], [[AND]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[XOR]], [[X]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %y = udiv i8 42, %_y ; thwart complexity-based canonicalization
   %and = and i8 %y, %x
   call void @use(i8 %and)
   %xor = xor i8 %y, %and
   %add = add i8 %xor, %x
   ret i8 %add
 }
 
 define i8 @add_xor_and_var_commuted4(i8 %_x, i8 %y) {
 ; CHECK-LABEL: @add_xor_and_var_commuted4(
 ; CHECK-NEXT:    [[X:%.*]] = udiv i8 42, [[_X:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[AND]], [[Y]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[X]], [[XOR]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[X]], [[XOR]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %x = udiv i8 42, %_x ; thwart complexity-based canonicalization
   %and = and i8 %x, %y
   call void @use(i8 %and)
   %xor = xor i8 %and, %y
   %add = add i8 %x, %xor
   ret i8 %add
 }
 
 define i8 @add_xor_and_var_commuted5(i8 %_x, i8 %y) {
 ; CHECK-LABEL: @add_xor_and_var_commuted5(
 ; CHECK-NEXT:    [[X:%.*]] = udiv i8 42, [[_X:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[AND]], [[Y]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[X]], [[XOR]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[X]], [[XOR]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %x = udiv i8 42, %_x ; thwart complexity-based canonicalization
   %and = and i8 %y, %x
   call void @use(i8 %and)
   %xor = xor i8 %and, %y
   %add = add i8 %x, %xor
   ret i8 %add
 }
 
 define i8 @add_xor_and_var_commuted6(i8 %_x, i8 %_y) {
 ; CHECK-LABEL: @add_xor_and_var_commuted6(
 ; CHECK-NEXT:    [[X:%.*]] = udiv i8 42, [[_X:%.*]]
 ; CHECK-NEXT:    [[Y:%.*]] = udiv i8 42, [[_Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X]], [[Y]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[Y]], [[AND]]
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i8 [[X]], [[XOR]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[X]], [[XOR]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %x = udiv i8 42, %_x ; thwart complexity-based canonicalization
   %y = udiv i8 42, %_y ; thwart complexity-based canonicalization
   %and = and i8 %x, %y
   call void @use(i8 %and)
   %xor = xor i8 %y, %and
   %add = add i8 %x, %xor
   ret i8 %add
 }
 
 define i8 @add_xor_and_var_commuted7(i8 %_x, i8 %_y) {
 ; CHECK-LABEL: @add_xor_and_var_commuted7(
 ; CHECK-NEXT:    [[X:%.*]] = udiv i8 42, [[_X:%.*]]
 ; CHECK-NEXT:    [[Y:%.*]] = udiv i8 42, [[_Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[Y]], [[X]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[Y]], [[AND]]
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i8 [[X]], [[XOR]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[X]], [[XOR]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %x = udiv i8 42, %_x ; thwart complexity-based canonicalization
   %y = udiv i8 42, %_y ; thwart complexity-based canonicalization
   %and = and i8 %y, %x
   call void @use(i8 %and)
   %xor = xor i8 %y, %and
   %add = add i8 %x, %xor
   ret i8 %add
 }
 
 define i8 @add_xor_and_var_extra_use(i8 %x, i8 %y) {
 ; CHECK-LABEL: @add_xor_and_var_extra_use(
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[AND]], [[Y]]
 ; CHECK-NEXT:    call void @use(i8 [[XOR]])
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[XOR]], [[X]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %and = and i8 %x, %y
   call void @use(i8 %and)
   %xor = xor i8 %and, %y
   call void @use(i8 %xor)
   %add = add i8 %xor, %x
   ret i8 %add
 }