Index: llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp =================================================================== --- llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp +++ llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp @@ -2030,17 +2030,54 @@ return BinaryOperator::Create(BOpc, CmpP, CmpQ); } - // Are we using xors to bitwise check for a pair of (in)equalities? Convert to + // 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. - 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); + // ((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) + bool Match = true; + SmallVector, 2> CmpValues; + SmallVector WorkList(1, Or); + + while (!WorkList.empty()) { + llvm::Value * CurrentValue = WorkList.pop_back_val(); + auto *OrOperator = dyn_cast(CurrentValue); + if (!OrOperator || OrOperator->getOpcode() != BinaryOperator::Or) { + Match = false; + break; + } + + Value *OrLhs = OrOperator->getOperand(0), + *OrRhs = OrOperator->getOperand(1); + + Value *Lhs, *Rhs; + if (match(OrLhs, m_OneUse(m_Xor(m_Value(Lhs), m_Value(Rhs))))) { + CmpValues.emplace_back(Lhs, Rhs); + } else { + WorkList.push_back(OrLhs); + } + + if (match(OrRhs, m_OneUse(m_Xor(m_Value(Lhs), m_Value(Rhs))))) { + CmpValues.emplace_back(Lhs, Rhs); + } else { + WorkList.push_back(OrRhs); + } + } + + if (Match) { auto BOpc = Pred == CmpInst::ICMP_EQ ? Instruction::And : Instruction::Or; - return BinaryOperator::Create(BOpc, Cmp12, Cmp34); + llvm::Value *LhsCmp = Builder.CreateICmp(Pred, CmpValues.rbegin()->first, + CmpValues.rbegin()->second); + + for (auto It = CmpValues.rbegin() + 1; It != CmpValues.rend() - 1; ++It) { + Value *RhsCmp = Builder.CreateICmp(Pred, It->first, It->second); + LhsCmp = Builder.CreateBinOp(BOpc, LhsCmp, RhsCmp); + } + + Value *RhsCmp = Builder.CreateICmp(Pred, CmpValues.begin()->first, + CmpValues.begin()->second); + return BinaryOperator::Create(BOpc, LhsCmp, RhsCmp); } return nullptr; Index: llvm/test/Transforms/InstCombine/icmp-or.ll =================================================================== --- llvm/test/Transforms/InstCombine/icmp-or.ll +++ llvm/test/Transforms/InstCombine/icmp-or.ll @@ -363,3 +363,155 @@ %r = icmp sgt i8 %or, -1 ret i1 %r } + +define i1 @icmp_or_xor_2_1(i64 %x1, i64 %y1, i64 %x2, i64 %y2) { +; CHECK-LABEL: @icmp_or_xor_2_1( +; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i64 %y1, %x1 +; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i64 %y2, %x2 +; CHECK-NEXT: [[AND:%.*]] = and i1 [[TMP1]], [[TMP2]] +; CHECK-NEXT: ret i1 [[AND]] +; + %xor = xor i64 %y1, %x1 + %xor1 = xor i64 %y2, %x2 + %or = or i64 %xor1, %xor + %cmp = icmp eq i64 %or, 0 + ret i1 %cmp +} + +; negative test - wrong cmp constant + +define i1 @icmp_or_xor_2_2(i64 %x1, i64 %y1, i64 %x2, i64 %y2, i64 %x3, i64 %y3, i64 %x4, i64 %y4) { +; CHECK-LABEL: @icmp_or_xor_2_2( +; CHECK-NEXT: [[XOR1:%.*]] = xor i64 %y1, %x1 +; CHECK-NEXT: [[XOR2:%.*]] = xor i64 %y2, %x2 +; CHECK-NEXT: [[OR:%.*]] = or i64 [[XOR2]], [[XOR1]] +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i64 [[OR]], 1 +; CHECK-NEXT: ret i1 [[CMP]] +; + %xor = xor i64 %y1, %x1 + %xor1 = xor i64 %y2, %x2 + %or = or i64 %xor1, %xor + %cmp = icmp eq i64 %or, 1 + ret i1 %cmp +} + +; negative test - xor multiuse + +define i1 @icmp_or_xor_2_3(i64 %x1, i64 %y1, i64 %x2, i64 %y2) { +; CHECK-LABEL: @icmp_or_xor_2_3( +; CHECK-NEXT: [[XOR1:%.*]] = xor i64 %y1, %x1 +; CHECK-NEXT: [[XOR2:%.*]] = xor i64 %y2, %x2 +; CHECK-NEXT: [[OR1:%.*]] = or i64 [[XOR2]], [[XOR1]] +; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i64 [[OR1]], 0 +; CHECK-NEXT: [[CMP2:%.*]] = icmp eq i64 [[XOR2]], 0 +; CHECK-NEXT: [[OR2:%.*]] = or i1 [[CMP1]], [[CMP2]] +; CHECK-NEXT: ret i1 [[OR2]] +; + %xor = xor i64 %y1, %x1 + %xor1 = xor i64 %y2, %x2 + %or = or i64 %xor1, %xor + %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: [[TMP1:%.*]] = icmp eq i64 %y1, %x1 +; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i64 %y2, %x2 +; CHECK-NEXT: [[AND1:%.*]] = and i1 [[TMP1]], [[TMP2]] +; CHECK-NEXT: [[TMP3:%.*]] = icmp eq i64 %y3, %x3 +; CHECK-NEXT: [[AND2:%.*]] = and i1 [[AND1]], [[TMP3]] +; CHECK-NEXT: ret i1 [[AND2]] +; + %xor = xor i64 %y1, %x1 + %xor1 = xor i64 %y2, %x2 + %or = or i64 %xor1, %xor + %xor2 = xor i64 %y3, %x3 + %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_2(i64 %x1, i64 %y1, i64 %x2, i64 %y2, i64 %x3, i64 %y3) { +; CHECK-LABEL: @icmp_or_xor_3_2( +; CHECK-NEXT: [[XOR1:%.*]] = xor i64 %y1, %x1 +; CHECK-NEXT: [[XOR2:%.*]] = xor i64 %y2, %x2 +; CHECK-NEXT: [[AND:%.*]] = and i64 [[XOR2]], [[XOR1]] +; CHECK-NEXT: [[XOR3:%.*]] = xor i64 %y3, %x3 +; CHECK-NEXT: [[OR2:%.*]] = or i64 [[AND]], [[XOR3]] +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i64 [[OR2]], 0 +; CHECK-NEXT: ret i1 [[CMP]] +; + %xor = xor i64 %y1, %x1 + %xor1 = xor i64 %y2, %x2 + %and = and i64 %xor1, %xor + %xor2 = xor i64 %y3, %x3 + %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: [[TMP1:%.*]] = icmp eq i64 %y1, %x1 +; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i64 %y2, %x2 +; CHECK-NEXT: [[AND1:%.*]] = and i1 [[TMP1]], [[TMP2]] +; CHECK-NEXT: [[TMP3:%.*]] = icmp eq i64 %y3, %x3 +; CHECK-NEXT: [[AND2:%.*]] = and i1 [[AND1]], [[TMP3]] +; CHECK-NEXT: ret i1 [[AND2]] +; + %xor = xor i64 %y1, %x1 + %xor1 = xor i64 %y2, %x2 + %or = or i64 %xor1, %xor + %xor2 = xor i64 %y3, %x3 + %or1 = or i64 %xor2, %or + %cmp = icmp eq i64 %or1, 0 + ret i1 %cmp +} + +; negative test - and instead of or + +define i1 @icmp_or_xor_3_4(i64 %x1, i64 %y1, i64 %x2, i64 %y2, i64 %x3, i64 %y3) { +; CHECK-LABEL: @icmp_or_xor_3_4( +; CHECK-NEXT: [[XOR1:%.*]] = xor i64 %y1, %x1 +; CHECK-NEXT: [[XOR2:%.*]] = xor i64 %y2, %x2 +; CHECK-NEXT: [[AND:%.*]] = and i64 [[XOR2]], [[XOR1]] +; CHECK-NEXT: [[XOR3:%.*]] = xor i64 %y3, %x3 +; CHECK-NEXT: [[OR2:%.*]] = or i64 [[XOR3]], [[AND]] +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i64 [[OR2]], 0 +; CHECK-NEXT: ret i1 [[CMP]] +; + %xor = xor i64 %y1, %x1 + %xor1 = xor i64 %y2, %x2 + %and = and i64 %xor1, %xor + %xor2 = xor i64 %y3, %x3 + %or1 = or i64 %xor2, %and + %cmp = icmp eq i64 %or1, 0 + ret i1 %cmp +} + +define i1 @icmp_or_xor_4(i64 %x1, i64 %y1, i64 %x2, i64 %y2, i64 %x3, i64 %y3, i64 %x4, i64 %y4) { +; CHECK-LABEL: @icmp_or_xor_4( +; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i64 %y1, %x1 +; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i64 %y2, %x2 +; CHECK-NEXT: [[AND1:%.*]] = and i1 [[TMP1]], [[TMP2]] +; CHECK-NEXT: [[TMP3:%.*]] = icmp eq i64 %y3, %x3 +; CHECK-NEXT: [[AND2:%.*]] = and i1 [[AND1]], [[TMP3]] +; CHECK-NEXT: [[TMP4:%.*]] = icmp eq i64 %y4, %x4 +; CHECK-NEXT: [[AND3:%.*]] = and i1 [[AND2]], [[TMP4]] +; CHECK-NEXT: ret i1 [[AND3]] +; + %xor = xor i64 %y1, %x1 + %xor1 = xor i64 %y2, %x2 + %or = or i64 %xor1, %xor + %xor2 = xor i64 %y3, %x3 + %xor3 = xor i64 %y4, %x4 + %or1 = or i64 %xor3, %xor2 + %or2 = or i64 %or, %or1 + %cmp = icmp eq i64 %or2, 0 + ret i1 %cmp +}