[InstCombine] Simplify 'xor'/'add' to 'or' if no common bits are set.

[lebedev.ri]

Summary

In order to get the whole fold as specified in PR6773,
let's first handle the simple straight-forward things.
Let's start with the xor -> or simplification.

The one obvious thing missing here: the constant mask is not handled.
I have an idea how to handle it, but it will require some thinking,
and is not strictly required here, so i've left that for later.

This haveNoCommonBitsSet() change looks kinda monstrous, i could refactor
it e.g. into "out of these 2 pairs of two values, one of these 4 values is inverted value from another pair" matcher,
but i'm not sure if i should?

https://rise4fun.com/Alive/Pkmg

[lebedev.ri]

Show that add is also handled.

[spatel]

lib/Analysis/ValueTracking.cpp

200–201

It's probably better to put this check above the computeKnownBits calls because this check is cheap (don't waste time doing recursive work if we can match this case first)

200–203

I think that's logically correct, but it can be coded more simply. All we need to capture is the inverted mask (double-check that this results in the same test changes):

// Look for an inverted mask: (X & Y) op (~X & Z).
Value *X;
if (match(LHS, m_c_And(m_Not(m_Value(X)), m_Value())) &&
    match(RHS, m_c_And(m_Specific(X), m_Value())))
  return true;
if (match(RHS, m_c_And(m_Not(m_Value(X)), m_Value())) &&
    match(LHS, m_c_And(m_Specific(X), m_Value())))
  return true;

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2449–2452

It's fine to include this in the review, but please make this (and the affected tests) a separate commit. In case there's a problem and/or need to revert, that will make it easier to diagnose the bug.

[lebedev.ri]

Adjusted based on @spatel review.
Thank you for the review!

lib/Analysis/ValueTracking.cpp

200–201

Right. I was wondering about that, but decided to add it after the existing logic. Will move.

200–203

Thanks, that is more succinct indeed!
Not too good at _c_ommutative matchers yet :/

The original code had full test coverage, and this code does not cause
any changes in tests as compared to my variant, so i *think* it's good.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2449–2452

Yep, sure.
I kinda did not realize that the call visitAnd() would already show
this transform, thus it got into this differential.

[spatel]

LGTM.

Note that for the value tracking improvement, there are a couple of other passes (that I've never looked at) that use haveNoCommonBitsSet(). If it's possible to show a test improvement from this change for those passes, that would be nice.

Also note that SelectionDAG has a twin for llvm::haveNoCommonBitsSet(), so it would be good to add a 'TODO' there about the potential improvement and referencing the IR version of the code. If you have the C++ template skills to unify any of that code, that would be a great maintenance improvement.

[lebedev.ri]

In D45631#1068338, @spatel wrote:

LGTM.

Thank you for the review!

Note that for the value tracking improvement, there are a couple of other passes (that I've never looked at) that use haveNoCommonBitsSet(). If it's possible to show a test improvement from this change for those passes, that would be nice.

There seem to be two other users:

1. ConstantOffsetExtractor::CanTraceInto(), (llvm/test/CodeGen/AArch64/aarch64-gep-opt.ll, @test-struct_1) That use does not appear to be covered by any tests at all (at least with x86/aarch64 backends). Will add FIXME comment.
2. StraightLineStrengthReduce::allocateCandidatesAndFindBasisForMul(), (test/Transforms/StraightLineStrengthReduce/slsr-mul.ll, @or) It requires a value and a constant. So i'm also not sure i can show the effect there...

Also note that SelectionDAG has a twin for llvm::haveNoCommonBitsSet(), so it would be good to add a 'TODO' there about the potential improvement and referencing the IR version of the code.

Sure thing, will do.

If you have the C++ template skills to unify any of that code, that would be a great maintenance improvement.

Interesting, but will require tests, again, so i don't feel confident looking into it right now.

lib/Analysis/ValueTracking.cpp

assert(LHS->getType() == RHS->getType() &&
          "LHS and RHS should have the same type");
   assert(LHS->getType()->isIntOrIntVectorTy() &&
          "LHS and RHS should be integers");
   IntegerType *IT = cast<IntegerType>(LHS->getType()->getScalarType());
   KnownBits LHSKnown(IT->getBitWidth());
   KnownBits RHSKnown(IT->getBitWidth());
   computeKnownBits(LHS, LHSKnown, DL, 0, AC, CxtI, DT);
   computeKnownBits(RHS, RHSKnown, DL, 0, AC, CxtI, DT);
-  return (LHSKnown.Zero | RHSKnown.Zero).isAllOnesValue();
+  if ((LHSKnown.Zero | RHSKnown.Zero).isAllOnesValue())
+    return true;
+  // Try to see if both sides are masked by the same mask (inverted on one side)
+  // I.e.  binop (x & m), (y & ~m)
+  Value *A, *B, *C, *D;
+  if (match(LHS, m_And(m_Value(A), m_Value(B))) &&
+      match(RHS, m_And(m_Value(C), m_Value(D)))) {
+    if (match(A, m_Not(m_CombineOr(m_Specific(C), m_Specific(D)))) ||
+        match(B, m_Not(m_CombineOr(m_Specific(C), m_Specific(D)))) ||
+        match(C, m_Not(m_CombineOr(m_Specific(A), m_Specific(B)))) ||
+        match(D, m_Not(m_CombineOr(m_Specific(A), m_Specific(B)))))
+      return true;
+  }
+  return false;
 }
 
 bool llvm::isOnlyUsedInZeroEqualityComparison(const Instruction *CxtI) {
   for (const User *U : CxtI->users()) {
     if (const ICmpInst *IC = dyn_cast<ICmpInst>(U))
       if (IC->isEquality())
         if (Constant *C = dyn_cast<Constant>(IC->getOperand(1)))
           if (C->isNullValue())

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Instruction *InstCombiner::visitXor(BinaryOperator &I) {
   // See if we can simplify any instructions used by the instruction whose sole
   // purpose is to compute bits we don't care about.
   if (SimplifyDemandedInstructionBits(I))
     return &I;
 
   if (Value *V = SimplifyBSwap(I, Builder))
     return replaceInstUsesWith(I, V);
 
+  // A^B --> A|B iff A and B have no bits set in common.
+  if (haveNoCommonBitsSet(Op0, Op1, DL, &AC, &I, &DT))
+    return BinaryOperator::CreateOr(Op0, Op1);
+
   // Apply DeMorgan's Law for 'nand' / 'nor' logic with an inverted operand.
   Value *X, *Y;
 
   // We must eliminate the and/or (one-use) for these transforms to not increase
   // the instruction count.
   // ~(~X & Y) --> (X | ~Y)
   // ~(Y & ~X) --> (X | ~Y)
   if (match(&I, m_Not(m_OneUse(m_c_And(m_Not(m_Value(X)), m_Value(Y)))))) {

test/Transforms/InstCombine/logical-select.ll

;
   ret i1 %xor
 }
 
 ; Don't replace a cheap logic op with a potentially expensive select
 ; unless we can also eliminate one of the other original ops.
 
 define i1 @bools_multi_uses2(i1 %a, i1 %b, i1 %c) {
 ; CHECK-LABEL: @bools_multi_uses2(
-; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[C:%.*]], true
-; CHECK-NEXT:    [[AND1:%.*]] = and i1 [[NOT]], [[A:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i1 [[C]], [[B:%.*]]
-; CHECK-NEXT:    [[ADD:%.*]] = xor i1 [[AND1]], [[AND2]]
-; CHECK-NEXT:    ret i1 [[ADD]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[C:%.*]], i1 [[B:%.*]], i1 [[A:%.*]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %not = xor i1 %c, -1
   %and1 = and i1 %not, %a
   %and2 = and i1 %c, %b
   %or = or i1 %and1, %and2
   %add = add i1 %and1, %and2
   %and3 = and i1 %or, %add
   ret i1 %and3

test/Transforms/InstCombine/masked-merge.ll

;
   ret <3 x i32> %or
 }
 
 define i32 @xor(i32 %x, i32 %y, i32 %m) {
 ; CHECK-LABEL: @xor(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[AND]], [[AND1]]
+; CHECK-NEXT:    [[XOR:%.*]] = or i32 [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %and = and i32 %x, %m
   %neg = xor i32 %m, -1
   %and1 = and i32 %neg, %y
   %xor = xor i32 %and, %and1
   ret i32 %xor
 }
 
 define <2 x i32> @xor_splatvec(<2 x i32> %x, <2 x i32> %y, <2 x i32> %m) {
 ; CHECK-LABEL: @xor_splatvec(
 ; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor <2 x i32> [[M]], <i32 -1, i32 -1>
 ; CHECK-NEXT:    [[AND1:%.*]] = and <2 x i32> [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor <2 x i32> [[AND]], [[AND1]]
+; CHECK-NEXT:    [[XOR:%.*]] = or <2 x i32> [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret <2 x i32> [[XOR]]
 ;
   %and = and <2 x i32> %x, %m
   %neg = xor <2 x i32> %m, <i32 -1, i32 -1>
   %and1 = and <2 x i32> %neg, %y
   %xor = xor <2 x i32> %and, %and1
   ret <2 x i32> %xor
 }
 
 define <3 x i32> @xor_vec_undef(<3 x i32> %x, <3 x i32> %y, <3 x i32> %m) {
 ; CHECK-LABEL: @xor_vec_undef(
 ; CHECK-NEXT:    [[AND:%.*]] = and <3 x i32> [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor <3 x i32> [[M]], <i32 -1, i32 undef, i32 -1>
 ; CHECK-NEXT:    [[AND1:%.*]] = and <3 x i32> [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor <3 x i32> [[AND]], [[AND1]]
+; CHECK-NEXT:    [[XOR:%.*]] = or <3 x i32> [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret <3 x i32> [[XOR]]
 ;
   %and = and <3 x i32> %x, %m
   %neg = xor <3 x i32> %m, <i32 -1, i32 undef, i32 -1>
   %and1 = and <3 x i32> %neg, %y
   %xor = xor <3 x i32> %and, %and1
   ret <3 x i32> %xor
 }

 
 
 
 define i32 @xor_commutative0(i32 %x, i32 %y, i32 %m) {
 ; CHECK-LABEL: @xor_commutative0(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[M:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[AND]], [[AND1]]
+; CHECK-NEXT:    [[XOR:%.*]] = or i32 [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %and = and i32 %m, %x ; swapped order
   %neg = xor i32 %m, -1
   %and1 = and i32 %neg, %y
   %xor = xor i32 %and, %and1
   ret i32 %xor
 }
 
 define i32 @xor_commutative1(i32 %x, i32 %m) {
 ; CHECK-LABEL: @xor_commutative1(
 ; CHECK-NEXT:    [[Y:%.*]] = call i32 @gen32()
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[Y]], [[NEG]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[AND]], [[AND1]]
+; CHECK-NEXT:    [[XOR:%.*]] = or i32 [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %y = call i32 @gen32()
   %and = and i32 %x, %m
   %neg = xor i32 %m, -1
   %and1 = and i32 %y, %neg; swapped order
   %xor = xor i32 %and, %and1
   ret i32 %xor
 }
 
 define i32 @xor_commutative2(i32 %x, i32 %y, i32 %m) {
 ; CHECK-LABEL: @xor_commutative2(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[AND1]], [[AND]]
+; CHECK-NEXT:    [[XOR:%.*]] = or i32 [[AND1]], [[AND]]
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %and = and i32 %x, %m
   %neg = xor i32 %m, -1
   %and1 = and i32 %neg, %y
   %xor = xor i32 %and1, %and ; swapped order
   ret i32 %xor
 }
 
 
 define i32 @xor_commutative3(i32 %x, i32 %m) {
 ; CHECK-LABEL: @xor_commutative3(
 ; CHECK-NEXT:    [[Y:%.*]] = call i32 @gen32()
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[M:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[Y]], [[NEG]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[AND]], [[AND1]]
+; CHECK-NEXT:    [[XOR:%.*]] = or i32 [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %y = call i32 @gen32()
   %and = and i32 %m, %x ; swapped order
   %neg = xor i32 %m, -1
   %and1 = and i32 %y, %neg; swapped order
   %xor = xor i32 %and, %and1
   ret i32 %xor
 }
 
 define i32 @xor_commutative4(i32 %x, i32 %y, i32 %m) {
 ; CHECK-LABEL: @xor_commutative4(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[M:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[AND1]], [[AND]]
+; CHECK-NEXT:    [[XOR:%.*]] = or i32 [[AND1]], [[AND]]
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %and = and i32 %m, %x ; swapped order
   %neg = xor i32 %m, -1
   %and1 = and i32 %neg, %y
   %xor = xor i32 %and1, %and ; swapped order
   ret i32 %xor
 }
 
 define i32 @xor_commutative5(i32 %x, i32 %m) {
 ; CHECK-LABEL: @xor_commutative5(
 ; CHECK-NEXT:    [[Y:%.*]] = call i32 @gen32()
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[Y]], [[NEG]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[AND1]], [[AND]]
+; CHECK-NEXT:    [[XOR:%.*]] = or i32 [[AND1]], [[AND]]
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %y = call i32 @gen32()
   %and = and i32 %x, %m
   %neg = xor i32 %m, -1
   %and1 = and i32 %y, %neg; swapped order
   %xor = xor i32 %and1, %and ; swapped order
   ret i32 %xor
 }
 
 
 define i32 @xor_commutative6(i32 %x, i32 %m) {
 ; CHECK-LABEL: @xor_commutative6(
 ; CHECK-NEXT:    [[Y:%.*]] = call i32 @gen32()
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[M:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[Y]], [[NEG]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[AND1]], [[AND]]
+; CHECK-NEXT:    [[XOR:%.*]] = or i32 [[AND1]], [[AND]]
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %y = call i32 @gen32()
   %and = and i32 %m, %x ; swapped order
   %neg = xor i32 %m, -1
   %and1 = and i32 %y, %neg; swapped order
   %xor = xor i32 %and1, %and ; swapped order
   ret i32 %xor
;
   ret i32 %or
 }
 
 define i32 @n0_xor_oneuse(i32 %x, i32 %y, i32 %m) {
 ; CHECK-LABEL: @n0_xor_oneuse(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[AND]], [[AND1]]
+; CHECK-NEXT:    [[XOR:%.*]] = or i32 [[AND]], [[AND1]]
 ; CHECK-NEXT:    call void @use32(i32 [[AND]])
 ; CHECK-NEXT:    call void @use32(i32 [[NEG]])
 ; CHECK-NEXT:    call void @use32(i32 [[AND1]])
 ; CHECK-NEXT:    ret i32 [[XOR]]
 ;
   %and = and i32 %x, %m
   %neg = xor i32 %m, -1
   %and1 = and i32 %neg, %y