[InstCombine] Generalise ((x1 ^ y1) | (x2 ^ y2)) == 0 transform

[kitaisreal]

Summary

Generalise ((x1 ^ y1) | (x2 ^ y2)) == 0 transform to more than two pairs of variables https://github.com/llvm/llvm-project/issues/57831.
Depends D154384.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2110

Shouldn't we also be able to chase OrOp1 (if it doesn't match Xor).

Figure it should be something along the lines of:

if(match(Op0, Xor) && match(Op1, Xor)) {
 // Base Case
}
else if(match(Op0, Xor)) {
 // Chase Op1
}
else if(match(Op1, Xor)) {
 // Chase Op1
}
else {
 break;
}

2110

Err third condition should be "Chase Op0"

[kitaisreal]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2110

Agree. Updated.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2093

AFAICT this condition never comes into play. You check the loop condition before reseting OrOperator every time. I'd say either make this a while(1) or make this BO && B0->getOpcode() == Instruction::Or

2116

There could we a case where we have:

(or (or (xor A, B), (xor C, D)), (or (xor E, F), (xor G, H))).
Not sure if it worth handling this case, but maybe switch this to a worklist algo so you can arbitrarily add Or ops.

[goldstein.w.n]

llvm/test/Transforms/InstCombine/icmp-or.ll

415

Can you 1) split the tests to a seperate patch (so we can see the diff this patch generates).

2. Can you add a few negative tests (maybe where cmp is not against 0, one of the xors has multiuse, where its or->or (invalid), etc...).

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2088

Maybe add as a todo, but this also works for sub (or implement in a follow up patch!)

[kitaisreal]

Moved test in separate patch https://reviews.llvm.org/D154384.

[kitaisreal]

Make implementation more general. Updated tests.

[kitaisreal]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2088

I can implement this in follow up patch.

2116

Updated implementation to support such case.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2088

Thanks :)
Can you add TODO for it in the meantime.

2102

Prefer not name these Or* as you expect to match them for Xor. Can you just make these Lhs/Rhs.

2111

The match(Op, Xor) { emplace(XorOps) } else { WorkList.Add(Op) } could be a lambda for LHS/RHS.

2118

At first I thought this should be !CmpValues.empty() so you can match something like:

(or (or (xor A, B), (xor C, D)), (and E, F)) but realize we will visit the inner or and handle it there. Can you add a comment here (or above where you set Match to false) that such a case will inherently be handled so its okay to fail on any non-or/xor.

llvm/test/Transforms/InstCombine/icmp-or.ll

415

This is still outstanding.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2091

Unnecessary llvm:: prefix here and elsewhere.

2095

Why does this one need to be handled separately?

2102

These are the Lhs/Rhs of an Or though. Lhs/Rhs of the Xor are matched below.

Not sure why this isn't doing match(CurrentValue, m_Or(m_Value(OrLhs), m_Value(OrRhs)) though.

[kitaisreal]

Updated implementation

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2088

Added TODO.

2091

Updated.

2095

To properly support lifetime of allocated operators we must allocate them using Builder, and Builder methods return Value *.
But this function expects to return BinaryOperator * instead of Value *, so last one handled separately.

2102

Updated implementation to use match.

2111

Updated.

2118

It seems that more easier approach is to clear CmpValues if we fail to match.

llvm/test/Transforms/InstCombine/icmp-or.ll

415

I moved tests into separate patch https://reviews.llvm.org/D154384. Should we merge it first so we can see the difference after this patch is applied ?

[kitaisreal]

Updated tests.

[goldstein.w.n]

General note, can you actually mark "done" the comments you have addressed rather than just replying to them?

[goldstein.w.n]

llvm/test/Transforms/InstCombine/icmp-or.ll

415

Do the following.

Rebase this patch ontop of the test change (so instead of this patch adding a bunch of tests, we should see diffs generated).

Then use the "Edit Related Revisions" option on phabricator and set this commit as the child of the test commit.

[kitaisreal]

Added changes on top of the tests.

[goldstein.w.n]

LGTM.

[goldstein.w.n]

llvm/test/Transforms/InstCombine/icmp-or.ll

488–489

Can you postfix all the negative tests with '_fail'?

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2095

You can do something like return replaceInstUsesWith(Or, LhsCmp) to convert the Value into Instruction for the return value.

2111

As this is now a pretty complex fold, I'd suggest moving it into a separate function. That would allow you to use early return nullptr here.

[kitaisreal]

Updated implementation.

[nikic]

LG

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1980

nit: Omit braces for single-line if.

[kitaisreal]

I do not have commit access. Can you please land this one for me Maksim Kita <[e-mail]> ?

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1980

I plan to continue this optimization for 'sub' in my next patch, so I will fix nitpick in next patch.

[goldstein.w.n]

In D154306#4500843, @kitaisreal wrote:

I do not have commit access. Can you please land this one for me Maksim Kita <[e-mail]> ?

Will do later today.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (C.isZero() ^ (Pred == CmpInst::ICMP_NE)) {
       return BinaryOperator::CreateNot(And);
     }
     return BinaryOperator::CreateAnd(TruncY, X);
   }
 
   return nullptr;
 }
 
+/// Fold icmp eq/ne (or (xor (X1, X2), xor(X3, X4))), 0.
+static Value *foldICmpOrXorChain(ICmpInst &Cmp, BinaryOperator *Or,
+                                 InstCombiner::BuilderTy &Builder) {
+  // Are we using xors to bitwise check for a pair or pairs of (in)equalities?
+  // Convert to a shorter form that has more potential to be folded even
+  // further.
+  // ((X1 ^ X2) || (X3 ^ X4)) == 0 --> (X1 == X2) && (X3 == X4)
+  // ((X1 ^ X2) || (X3 ^ X4)) != 0 --> (X1 != X2) || (X3 != X4)
+  // ((X1 ^ X2) || (X3 ^ X4) || (X5 ^ X6)) == 0 -->
+  // (X1 == X2) && (X3 == X4) && (X5 == X6)
+  // ((X1 ^ X2) || (X3 ^ X4) || (X5 ^ X6)) != 0 -->
+  // (X1 != X2) || (X3 != X4) || (X5 != X6)
+  // TODO: Implement for sub
+  SmallVector<std::pair<Value *, Value *>, 2> CmpValues;
+  SmallVector<Value *, 16> WorkList(1, Or);
+
+  while (!WorkList.empty()) {
+    auto MatchOrOperatorArgument = [&](Value *OrOperatorArgument) {
+      Value *Lhs, *Rhs;
+
+      if (match(OrOperatorArgument,
+                m_OneUse(m_Xor(m_Value(Lhs), m_Value(Rhs))))) {
+        CmpValues.emplace_back(Lhs, Rhs);
+      } else {
+        WorkList.push_back(OrOperatorArgument);
+      }
+    };
+
+    Value *CurrentValue = WorkList.pop_back_val();
+    Value *OrOperatorLhs, *OrOperatorRhs;
+
+    if (!match(CurrentValue,
+               m_Or(m_Value(OrOperatorLhs), m_Value(OrOperatorRhs)))) {
+      return nullptr;
+    }
+
+    MatchOrOperatorArgument(OrOperatorRhs);
+    MatchOrOperatorArgument(OrOperatorLhs);
+  }
+
+  ICmpInst::Predicate Pred = Cmp.getPredicate();
+  auto BOpc = Pred == CmpInst::ICMP_EQ ? Instruction::And : Instruction::Or;
+  Value *LhsCmp = Builder.CreateICmp(Pred, CmpValues.rbegin()->first,
+                                     CmpValues.rbegin()->second);
+
+  for (auto It = CmpValues.rbegin() + 1; It != CmpValues.rend(); ++It) {
+    Value *RhsCmp = Builder.CreateICmp(Pred, It->first, It->second);
+    LhsCmp = Builder.CreateBinOp(BOpc, LhsCmp, RhsCmp);
+  }
+
+  return LhsCmp;
+}
+
 /// Fold icmp (or X, Y), C.
 Instruction *InstCombinerImpl::foldICmpOrConstant(ICmpInst &Cmp,
                                                   BinaryOperator *Or,
                                                   const APInt &C) {
   ICmpInst::Predicate Pred = Cmp.getPredicate();
   if (C.isOne()) {
     // icmp slt signum(V) 1 --> icmp slt V, 1
     Value *V = nullptr;
if (match(Or, m_Or(m_PtrToInt(m_Value(P)), m_PtrToInt(m_Value(Q))))) {
     Value *CmpP =
         Builder.CreateICmp(Pred, P, ConstantInt::getNullValue(P->getType()));
     Value *CmpQ =
         Builder.CreateICmp(Pred, Q, ConstantInt::getNullValue(Q->getType()));
     auto BOpc = Pred == CmpInst::ICMP_EQ ? Instruction::And : Instruction::Or;
     return BinaryOperator::Create(BOpc, CmpP, CmpQ);
   }
 
-  // Are we using xors to bitwise check for a pair of (in)equalities? Convert to
-  // a shorter form that has more potential to be folded even further.
-  Value *X1, *X2, *X3, *X4;
-  if (match(OrOp0, m_OneUse(m_Xor(m_Value(X1), m_Value(X2)))) &&
-      match(OrOp1, m_OneUse(m_Xor(m_Value(X3), m_Value(X4))))) {
-    // ((X1 ^ X2) || (X3 ^ X4)) == 0 --> (X1 == X2) && (X3 == X4)
-    // ((X1 ^ X2) || (X3 ^ X4)) != 0 --> (X1 != X2) || (X3 != X4)
-    Value *Cmp12 = Builder.CreateICmp(Pred, X1, X2);
-    Value *Cmp34 = Builder.CreateICmp(Pred, X3, X4);
-    auto BOpc = Pred == CmpInst::ICMP_EQ ? Instruction::And : Instruction::Or;
-    return BinaryOperator::Create(BOpc, Cmp12, Cmp34);
-  }
+  if (Value *V = foldICmpOrXorChain(Cmp, Or, Builder))
+    return replaceInstUsesWith(Cmp, V);
 
   return nullptr;
 }
 
 /// Fold icmp (mul X, Y), C.
 Instruction *InstCombinerImpl::foldICmpMulConstant(ICmpInst &Cmp,
                                                    BinaryOperator *Mul,
                                                    const APInt &C) {
   ICmpInst::Predicate Pred = Cmp.getPredicate();
   Type *MulTy = Mul->getType();
   Value *X = Mul->getOperand(0);
 
   // If there's no overflow:
   // X * X == 0 --> X == 0
   // X * X != 0 --> X != 0
   if (Cmp.isEquality() && C.isZero() && X == Mul->getOperand(1) &&
       (Mul->hasNoUnsignedWrap() || Mul->hasNoSignedWrap()))
     return new ICmpInst(Pred, X, ConstantInt::getNullValue(MulTy));
 
   const APInt *MulC;
   if (!match(Mul->getOperand(1), m_APInt(MulC)))
     return nullptr;
 
   // If this is a test of the sign bit and the multiply is sign-preserving with
   // a constant operand, use the multiply LHS operand instead:
   // (X * +MulC) < 0 --> X < 0
   // (X * -MulC) < 0 --> X > 0
   if (isSignTest(Pred, C) && Mul->hasNoSignedWrap()) {
     if (MulC->isNegative())
       Pred = ICmpInst::getSwappedPredicate(Pred);
     return new ICmpInst(Pred, X, ConstantInt::getNullValue(MulTy));
   }
 
   if (MulC->isZero())
     return nullptr;
 
   // If the multiply does not wrap or the constant is odd, try to divide the
   // compare constant by the multiplication factor.
   if (Cmp.isEquality()) {

llvm/test/Transforms/InstCombine/icmp-or.ll

;
   %dec = add i8 %x, -2
   %or = or i8 %dec, %x
   %r = icmp sgt i8 %or, -1
   ret i1 %r
 }
 
 define i1 @icmp_or_xor_2_eq(i64 %x1, i64 %y1, i64 %x2, i64 %y2) {
 ; CHECK-LABEL: @icmp_or_xor_2_eq(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i64 [[X1:%.*]], [[Y1:%.*]]
-; CHECK-NEXT:    [[XOR1:%.*]] = xor i64 [[X2:%.*]], [[Y2:%.*]]
-; CHECK-NEXT:    [[OR:%.*]] = or i64 [[XOR]], [[XOR1]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[OR]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[X1:%.*]], [[Y1:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[X2:%.*]], [[Y2:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %xor = xor i64 %x1, %y1
   %xor1 = xor i64 %x2, %y2
   %or = or i64 %xor, %xor1
   %cmp = icmp eq i64 %or, 0
   ret i1 %cmp
 }
 
 define i1 @icmp_or_xor_2_ne(i64 %x1, i64 %y1, i64 %x2, i64 %y2) {
 ; CHECK-LABEL: @icmp_or_xor_2_ne(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i64 [[X1:%.*]], [[Y1:%.*]]
-; CHECK-NEXT:    [[XOR1:%.*]] = xor i64 [[X2:%.*]], [[Y2:%.*]]
-; CHECK-NEXT:    [[OR:%.*]] = or i64 [[XOR]], [[XOR1]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[OR]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i64 [[X1:%.*]], [[Y1:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i64 [[X2:%.*]], [[Y2:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = or i1 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %xor = xor i64 %x1, %y1
   %xor1 = xor i64 %x2, %y2
   %or = or i64 %xor, %xor1
   %cmp = icmp ne i64 %or, 0
   ret i1 %cmp
 }
;
   %or = or i64 %xor, %xor1
   %cmp = icmp eq i64 %or, 1
   ret i1 %cmp
 }
 
 ; negative test - wrong cmp constant
 
 define i1 @icmp_or_xor_2_ne_fail(i64 %x1, i64 %y1, i64 %x2, i64 %y2) {
 ; CHECK-LABEL: @icmp_or_xor_2_ne_fail(
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i64 [[X1:%.*]], [[Y1:%.*]]
 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i64 [[X2:%.*]], [[Y2:%.*]]
 ; CHECK-NEXT:    [[OR:%.*]] = or i64 [[XOR]], [[XOR1]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[OR]], 1
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %xor = xor i64 %x1, %y1
   %xor1 = xor i64 %x2, %y2
;
   %cmp = icmp eq i64 %or, 0
   %cmp_1 = icmp eq i64 %xor1, 0
   %or1 = or i1 %cmp, %cmp_1
   ret i1 %or1
 }
 
 define i1 @icmp_or_xor_3_1(i64 %x1, i64 %y1, i64 %x2, i64 %y2, i64 %x3, i64 %y3) {
 ; CHECK-LABEL: @icmp_or_xor_3_1(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i64 [[X1:%.*]], [[Y1:%.*]]
-; CHECK-NEXT:    [[XOR1:%.*]] = xor i64 [[X2:%.*]], [[Y2:%.*]]
-; CHECK-NEXT:    [[OR:%.*]] = or i64 [[XOR]], [[XOR1]]
-; CHECK-NEXT:    [[XOR2:%.*]] = xor i64 [[X3:%.*]], [[Y3:%.*]]
-; CHECK-NEXT:    [[OR1:%.*]] = or i64 [[OR]], [[XOR2]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[OR1]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[X1:%.*]], [[Y1:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[X2:%.*]], [[Y2:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = and i1 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i64 [[X3:%.*]], [[Y3:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[TMP3]], [[TMP4]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %xor = xor i64 %x1, %y1
   %xor1 = xor i64 %x2, %y2
   %or = or i64 %xor, %xor1
   %xor2 = xor i64 %x3, %y3
   %or1 = or i64 %or, %xor2
   %cmp = icmp eq i64 %or1, 0
   ret i1 %cmp
 }
 
 ; negative test - and instead of or
 
 define i1 @icmp_or_xor_3_fail(i64 %x1, i64 %y1, i64 %x2, i64 %y2, i64 %x3, i64 %y3) {
 ; CHECK-LABEL: @icmp_or_xor_3_fail(
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i64 [[X1:%.*]], [[Y1:%.*]]
 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i64 [[X2:%.*]], [[Y2:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i64 [[XOR]], [[XOR1]]
 ; CHECK-NEXT:    [[XOR2:%.*]] = xor i64 [[X3:%.*]], [[Y3:%.*]]
 ; CHECK-NEXT:    [[OR1:%.*]] = or i64 [[AND]], [[XOR2]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[OR1]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %xor = xor i64 %x1, %y1
   %xor1 = xor i64 %x2, %y2
   %and = and i64 %xor, %xor1
   %xor2 = xor i64 %x3, %y3
   %or1 = or i64 %and, %xor2
   %cmp = icmp eq i64 %or1, 0
   ret i1 %cmp
 }
 
 define i1 @icmp_or_xor_3_3(i64 %x1, i64 %y1, i64 %x2, i64 %y2, i64 %x3, i64 %y3) {
 ; CHECK-LABEL: @icmp_or_xor_3_3(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i64 [[X1:%.*]], [[Y1:%.*]]
-; CHECK-NEXT:    [[XOR1:%.*]] = xor i64 [[X2:%.*]], [[Y2:%.*]]
-; CHECK-NEXT:    [[OR:%.*]] = or i64 [[XOR]], [[XOR1]]
-; CHECK-NEXT:    [[XOR2:%.*]] = xor i64 [[X3:%.*]], [[Y3:%.*]]
-; CHECK-NEXT:    [[OR1:%.*]] = or i64 [[XOR2]], [[OR]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[OR1]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[X1:%.*]], [[Y1:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[X2:%.*]], [[Y2:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = and i1 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i64 [[X3:%.*]], [[Y3:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[TMP3]], [[TMP4]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %xor = xor i64 %x1, %y1
   %xor1 = xor i64 %x2, %y2
   %or = or i64 %xor, %xor1
   %xor2 = xor i64 %x3, %y3
   %or1 = or i64 %xor2, %or
   %cmp = icmp eq i64 %or1, 0
;
   %xor2 = xor i64 %x3, %y3
   %or1 = or i64 %xor2, %and
   %cmp = icmp eq i64 %or1, 0
   ret i1 %cmp
 }
 
 define i1 @icmp_or_xor_4_1(i64 %x1, i64 %y1, i64 %x2, i64 %y2, i64 %x3, i64 %y3, i64 %x4, i64 %y4) {
 ; CHECK-LABEL: @icmp_or_xor_4_1(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i64 [[X1:%.*]], [[Y1:%.*]]
-; CHECK-NEXT:    [[XOR1:%.*]] = xor i64 [[X2:%.*]], [[Y2:%.*]]
-; CHECK-NEXT:    [[OR:%.*]] = or i64 [[XOR]], [[XOR1]]
-; CHECK-NEXT:    [[XOR2:%.*]] = xor i64 [[X3:%.*]], [[Y3:%.*]]
-; CHECK-NEXT:    [[XOR3:%.*]] = xor i64 [[X4:%.*]], [[Y4:%.*]]
-; CHECK-NEXT:    [[OR1:%.*]] = or i64 [[XOR2]], [[XOR3]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i64 [[OR]], [[OR1]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[OR2]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[X3:%.*]], [[Y3:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[X4:%.*]], [[Y4:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = and i1 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i64 [[X1:%.*]], [[Y1:%.*]]
+; CHECK-NEXT:    [[TMP5:%.*]] = and i1 [[TMP3]], [[TMP4]]
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp eq i64 [[X2:%.*]], [[Y2:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[TMP5]], [[TMP6]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %xor = xor i64 %x1, %y1
   %xor1 = xor i64 %x2, %y2
   %or = or i64 %xor, %xor1
   %xor2 = xor i64 %x3, %y3
   %xor3 = xor i64 %x4, %y4
   %or1 = or i64 %xor2, %xor3
   %or2 = or i64 %or, %or1
   %cmp = icmp eq i64 %or2, 0
   ret i1 %cmp
 }
 
 define i1 @icmp_or_xor_4_2(i64 %x1, i64 %y1, i64 %x2, i64 %y2, i64 %x3, i64 %y3, i64 %x4, i64 %y4) {
 ; CHECK-LABEL: @icmp_or_xor_4_2(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i64 [[X1:%.*]], [[Y1:%.*]]
-; CHECK-NEXT:    [[XOR1:%.*]] = xor i64 [[X2:%.*]], [[Y2:%.*]]
-; CHECK-NEXT:    [[OR:%.*]] = or i64 [[XOR]], [[XOR1]]
-; CHECK-NEXT:    [[XOR2:%.*]] = xor i64 [[X3:%.*]], [[Y3:%.*]]
-; CHECK-NEXT:    [[XOR3:%.*]] = xor i64 [[X4:%.*]], [[Y4:%.*]]
-; CHECK-NEXT:    [[OR1:%.*]] = or i64 [[XOR2]], [[XOR3]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i64 [[OR1]], [[OR]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[OR2]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[X1:%.*]], [[Y1:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[X2:%.*]], [[Y2:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = and i1 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i64 [[X3:%.*]], [[Y3:%.*]]
+; CHECK-NEXT:    [[TMP5:%.*]] = and i1 [[TMP3]], [[TMP4]]
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp eq i64 [[X4:%.*]], [[Y4:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[TMP5]], [[TMP6]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %xor = xor i64 %x1, %y1
   %xor1 = xor i64 %x2, %y2
   %or = or i64 %xor, %xor1
   %xor2 = xor i64 %x3, %y3
   %xor3 = xor i64 %x4, %y4
   %or1 = or i64 %xor2, %xor3
   %or2 = or i64 %or1, %or
   %cmp = icmp eq i64 %or2, 0
   ret i1 %cmp
 }