[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 ↗

(On Diff #142471)

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 ↗

(On Diff #142471)

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 ↗

(On Diff #142471)

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 ↗

(On Diff #142471)

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

200–203 ↗

(On Diff #142471)

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 ↗

(On Diff #142471)

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.

llvm/trunk/lib/Analysis/ValueTracking.cpp

 bool llvm::haveNoCommonBitsSet(const Value *LHS, const Value *RHS,
                                const DataLayout &DL,
                                AssumptionCache *AC, const Instruction *CxtI,
                                const DominatorTree *DT) {
   assert(LHS->getType() == RHS->getType() &&
          "LHS and RHS should have the same type");
   assert(LHS->getType()->isIntOrIntVectorTy() &&
          "LHS and RHS should be integers");
+  // 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;
   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();
 }
 

llvm/trunk/test/Transforms/InstCombine/masked-merge-add.ll

 ; Most basic positive tests
 ; ============================================================================ ;
 
 define i32 @p(i32 %x, i32 %y, i32 %m) {
 ; CHECK-LABEL: @p(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add i32 [[AND]], [[AND1]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %and = and i32 %x, %m
   %neg = xor i32 %m, -1
   %and1 = and i32 %neg, %y
   %ret = add i32 %and, %and1
   ret i32 %ret
 }
 
 define <2 x i32> @p_splatvec(<2 x i32> %x, <2 x i32> %y, <2 x i32> %m) {
 ; CHECK-LABEL: @p_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:    [[RET:%.*]] = add <2 x i32> [[AND]], [[AND1]]
+; CHECK-NEXT:    [[RET:%.*]] = or <2 x i32> [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret <2 x i32> [[RET]]
 ;
   %and = and <2 x i32> %x, %m
   %neg = xor <2 x i32> %m, <i32 -1, i32 -1>
   %and1 = and <2 x i32> %neg, %y
   %ret = add <2 x i32> %and, %and1
   ret <2 x i32> %ret
 }
 
 define <3 x i32> @p_vec_undef(<3 x i32> %x, <3 x i32> %y, <3 x i32> %m) {
 ; CHECK-LABEL: @p_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:    [[RET:%.*]] = add <3 x i32> [[AND]], [[AND1]]
+; CHECK-NEXT:    [[RET:%.*]] = or <3 x i32> [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret <3 x i32> [[RET]]
 ;
   %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
   %ret = add <3 x i32> %and, %and1
   ret <3 x i32> %ret
 }

 ; Used to make sure that the IR complexity sorting does not interfere.
 declare i32 @gen32()
 
 define i32 @p_commutative0(i32 %x, i32 %y, i32 %m) {
 ; CHECK-LABEL: @p_commutative0(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[M:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add i32 [[AND]], [[AND1]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %and = and i32 %m, %x ; swapped order
   %neg = xor i32 %m, -1
   %and1 = and i32 %neg, %y
   %ret = add i32 %and, %and1
   ret i32 %ret
 }
 
 define i32 @p_commutative1(i32 %x, i32 %m) {
 ; CHECK-LABEL: @p_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:    [[RET:%.*]] = add i32 [[AND]], [[AND1]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %y = call i32 @gen32()
   %and = and i32 %x, %m
   %neg = xor i32 %m, -1
   %and1 = and i32 %y, %neg; swapped order
   %ret = add i32 %and, %and1
   ret i32 %ret
 }
 
 define i32 @p_commutative2(i32 %x, i32 %y, i32 %m) {
 ; CHECK-LABEL: @p_commutative2(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add i32 [[AND1]], [[AND]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND1]], [[AND]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %and = and i32 %x, %m
   %neg = xor i32 %m, -1
   %and1 = and i32 %neg, %y
   %ret = add i32 %and1, %and ; swapped order
   ret i32 %ret
 }
 
 define i32 @p_commutative3(i32 %x, i32 %m) {
 ; CHECK-LABEL: @p_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:    [[RET:%.*]] = add i32 [[AND]], [[AND1]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND]], [[AND1]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %y = call i32 @gen32()
   %and = and i32 %m, %x ; swapped order
   %neg = xor i32 %m, -1
   %and1 = and i32 %y, %neg; swapped order
   %ret = add i32 %and, %and1
   ret i32 %ret
 }
 
 define i32 @p_commutative4(i32 %x, i32 %y, i32 %m) {
 ; CHECK-LABEL: @p_commutative4(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[M:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add i32 [[AND1]], [[AND]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND1]], [[AND]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %and = and i32 %m, %x ; swapped order
   %neg = xor i32 %m, -1
   %and1 = and i32 %neg, %y
   %ret = add i32 %and1, %and ; swapped order
   ret i32 %ret
 }
 
 define i32 @p_commutative5(i32 %x, i32 %m) {
 ; CHECK-LABEL: @p_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:    [[RET:%.*]] = add i32 [[AND1]], [[AND]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND1]], [[AND]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %y = call i32 @gen32()
   %and = and i32 %x, %m
   %neg = xor i32 %m, -1
   %and1 = and i32 %y, %neg; swapped order
   %ret = add i32 %and1, %and ; swapped order
   ret i32 %ret
 }
 
 define i32 @p_commutative6(i32 %x, i32 %m) {
 ; CHECK-LABEL: @p_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:    [[RET:%.*]] = add i32 [[AND1]], [[AND]]
+; CHECK-NEXT:    [[RET:%.*]] = or i32 [[AND1]], [[AND]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %y = call i32 @gen32()
   %and = and i32 %m, %x ; swapped order
   %neg = xor i32 %m, -1
   %and1 = and i32 %y, %neg; swapped order
   %ret = add i32 %and1, %and ; swapped order
   ret i32 %ret

 
 declare void @use32(i32)
 
 define i32 @n0_oneuse(i32 %x, i32 %y, i32 %m) {
 ; CHECK-LABEL: @n0_oneuse(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], [[M:%.*]]
 ; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[M]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NEG]], [[Y:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add i32 [[AND]], [[AND1]]
+; CHECK-NEXT:    [[RET:%.*]] = 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 [[RET]]
 ;
   %and = and i32 %x, %m
   %neg = xor i32 %m, -1
   %and1 = and i32 %neg, %y