[InstCombine] combine intersection for inequality icmps

[inclyc]

Summary

define i1 @src(i32 %A) {
  %mask1 = and i32 %A, 15 ; 0x0f
  %tst1 = icmp eq i32 %mask1, 3 ; 0x03
  %mask2 = and i32 %A, 255 ; 0xff
  %tst2 = icmp eq i32 %mask2, 243; 0xf3
  %res = or i1 %tst1, %tst2
  ret i1 %res
}

->

define i1 @tgt(i32 %A) {
  %1 = and i32 %A, 15
  %res = icmp eq i32 %1, 3
  ret i1 %res
}

Proof: https://alive2.llvm.org/ce/z/4AyvcE

Assume that (B & D) & (C ^ E) == 0, and (B & D) == D || (B & D) == B,
transforms:

(icmp ne (A & B), C) & (icmp ne (A & D), E)
-> (icmp ne (A & (B&D)), (C&E))

Fixes: https://github.com/llvm/llvm-project/issues/59680

[inclyc]

Assume that (B & D) & (C ^ E) == 0, and (B & D) == D || (B & D) == B,
transforms:

(icmp ne (A & B), C) & (icmp ne (A & D), E)
-> (icmp ne (A & (B&D)), (C&E))

Previous version I forgot the condition (B & D) == D || (B & D) == B.

[inclyc]

Handle (icmp ne (A & B), B) & (icmp eq (A & D), D), B & D having a single bit set

[bcl5980]

We should write proof with variables(not constant like 3, 15 in current alive2 link) also.

[inclyc]

We should write proof with variables(not constant like 3, 15 in current alive2 link) also.

Ahh, seems these conditions are still incorrent https://alive2.llvm.org/ce/z/tqUgLh :(

Thanks @bcl5980

[inclyc]

Proof: https://alive2.llvm.org/ce/z/4AyvcE

[inclyc]

ping :)

[spatel]

I'm not familiar with all of the potential folds in foldLogOpOfMaskedICmps(), so if anyone else has comments, please jump in.

I'd prefer that we add more negative tests such as mismatched icmp predicates, operands, and bitwise logic ops (even if there are shared predicates with existing transform to bail out on those patterns).

Also, please pre-commit baseline tests to main or at least locally and rebase this patch on top of that, so we can see exact diffs for tests that do change.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

717–718

Add a string message to each assert like "Expected impossible compares to be simplified".

But I'm skeptical that we can actually do that. Ie, how do we guarantee that the operands of this logic instruction were already visited before we got here? If we can't guarantee that, just bail out instead.

724

Why does this use B and D rather than ConstB and ConstD?
In fact, why do we create this at all - can we use ConstT in the next line?

[bcl5980]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

628–630

Can we merge the code into here? It looks the logic is almost the same.

717–718

I think the assert should be OK. simplifyICmpInst will optimize the icmp to constant at very early time before the assert triggered.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

717–718

No - this is a mistake I've made a few times in the past. :)

In simple examples (one basic block), you are correct - we will visit the icmp operands before the bitwise logic instruction.

But it is possible that we are visiting this bitwise logic instruction before visiting the icmp instructions. In that case, we can see unsimplified instructions.

Usually, it takes a long time before the bug is discovered in the wild, and/or we fuzz our way to a test that creates just the right sequence to trigger the problem.

I advise that we just 'return nullptr' here.

[bcl5980]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

717–718

Thanks for the explaination. Then maybe we should add bail out for if (Mask & BMask_Mixed) also.

[inclyc]

Address comments

• merge NotMixed & Mixed
• add precommite revision
• use ConstT instead of "create and"
• bailout assertions

Todo:

• understandable comments
• robust tests (How can I test icmps that are expected failing?)

[bcl5980]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

628

Is Mask & (BMask_Mixed | BMask_NotMixed) better?

682

I think this code can be shared by both BMask_Mixed and BMask_NotMixed also.

686

Is this condition the same to line 660 ? Can we add some code like:

if (((*ConstB & *ConstD) & (ConstC ^ ConstE)).getBoolValue())
  return isMixed ? ConstantInt::get(LHS->getType(), !IsAnd) : nullptr

689

This also can be shared by select like:

Value *ICmpLHS = Builder.CreateBinOp(isMixed ? Instruction::Or : Instruction::And);
Value * ICmpRHS = ConstantInt::get(A->getType(), isMixed ? (ConstC | ConstE) : (ConstC & ConstE));

Or you can check isMixed at first:

Instruction::BinaryOps ICmpLHSOpcode;
APInt ICmpRHSAP;
Value* ICmpAndConflictBailout;
if (isMixed) {
  ICmpLHSOpcode = Instruction::Or;
  ICmpRHSAP = ConstC | ConstE;
  ICmpAndConflictBailout = ConstantInt::get(LHS->getType(), !IsAnd);
} else {
  ICmpLHSOpcode = Instruction::And;
  ICmpRHSAP = ConstC & ConstE;
  ICmpAndConflictBailout = ConstantInt::get(LHS->getType(), !IsAnd);
}

[inclyc]

Looks like the test LLVM.Transforms/InstCombine::sign-test-and-or.ll is failed due to recent changes on this patch. I'd like to inspect it first. :)

[spatel]

In D140666#4065425, @inclyc wrote:

Looks like the test LLVM.Transforms/InstCombine::sign-test-and-or.ll is failed due to recent changes on this patch. I'd like to inspect it first. :)

Those diffs are miscompiles if I'm seeing it correctly, so something is not right with this patch.

[inclyc]

In D140666#4069648, @spatel wrote:

In D140666#4065425, @inclyc wrote:

Looks like the test LLVM.Transforms/InstCombine::sign-test-and-or.ll is failed due to recent changes on this patch. I'd like to inspect it first. :)

Those diffs are miscompiles if I'm seeing it correctly, so something is not right with this patch.

Thanks! Changes are planned after the Spring Festival these days. I'm sorry for the delay.

[inclyc]

@bcl5980

Can we merge the code into here? It looks the logic is almost the same.

Looking at it so far, I think we have some misconceptions about merging. Some icmps may be both Mixed and NotMixed? Suggested code changes are assuming icmps are "Mixed" or not, instead, we may encounter Mask = BMask_Mixed | BMask_NotMixed I think that's the fact.

[inclyc]

unmerge instcombine

[inclyc]

• use "ConstT" instead of creating new instruction

[inclyc]

1

[inclyc]

add test masked_and_expected_false

[bcl5980]

In D140666#4076679, @inclyc wrote:

@bcl5980

Can we merge the code into here? It looks the logic is almost the same.

Looking at it so far, I think we have some misconceptions about merging. Some icmps may be both Mixed and NotMixed? Suggested code changes are assuming icmps are "Mixed" or not, instead, we may encounter Mask = BMask_Mixed | BMask_NotMixed I think that's the fact.

I don't think BMask_Mixed and BMask_NotMixed will happen at the same time.

[inclyc]

I don't think BMask_Mixed and BMask_NotMixed will happen at the same time.

LLVM.Transforms/InstCombine::sign-test-and-or.ll has given us an example.

define i1 @test9(i32 %a) {
; CHECK-LABEL: @test9(
; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], -1073741824
; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 1073741824
; CHECK-NEXT:    ret i1 [[TMP2]]
;
  %1 = and i32 %a, 1073741824
  %2 = icmp ne i32 %1, 0
  %3 = icmp sgt i32 %a, -1
  %or.cond = and i1 %2, %3
  ret i1 %or.cond
}

I'm not sure about this, but the debugger showed me Mask = BMask_Mixed | BMask_NotMixed. Can you reproduce this on your machine?

[bcl5980]

In D140666#4088741, @inclyc wrote:

I don't think BMask_Mixed and BMask_NotMixed will happen at the same time.

LLVM.Transforms/InstCombine::sign-test-and-or.ll has given us an example.

define i1 @test9(i32 %a) {
; CHECK-LABEL: @test9(
; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], -1073741824
; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 1073741824
; CHECK-NEXT:    ret i1 [[TMP2]]
;
  %1 = and i32 %a, 1073741824
  %2 = icmp ne i32 %1, 0
  %3 = icmp sgt i32 %a, -1
  %or.cond = and i1 %2, %3
  ret i1 %or.cond
}

I'm not sure about this, but the debugger showed me Mask = BMask_Mixed | BMask_NotMixed. Can you reproduce this on your machine?

Yeah, I can reproduce the case. What I mean is not it will not happen for any case. B, D is pow2, C, E is 0 can trigger that. But this case I don't think it can match the condition in your code:

const APInt ConstT = *ConstB & *ConstD;
if (ConstT != *ConstB && ConstT != *ConstD)

So for this transform you add, it is not a problem I think. If you really concern for that. My suggestion is like this code:

if (Mask & (BMask_Mixed | BMask_NotMixed)) {
  const APInt *OldConstC, *OldConstE;
  if (!match(C, m_APInt(OldConstC)) || !match(E, m_APInt(OldConstE)))
    return nullptr;

  auto FoldBMixed = [&](ICmpInst::Predicate CC, bool IsNot) -> Value * {
    CC = IsNot ? CmpInst::getInversePredicate(CC) : CC;
    const APInt ConstC = PredL != CC ? *ConstB ^ *OldConstC : *OldConstC;
    const APInt ConstE = PredR != CC ? *ConstD ^ *OldConstE : *OldConstE;

    if (((*ConstB & *ConstD) & (ConstC ^ ConstE)).getBoolValue())
      return IsNot ? nullptr : ConstantInt::get(LHS->getType(), !IsAnd);

    if (IsNot && !ConstB->isSubsetOf(*ConstD) && !ConstD->isSubsetOf(*ConstB))
      return nullptr;

    APInt BD, CE;
    if (IsNot) {
      BD = *ConstB & *ConstD;
      CE = ConstC & ConstE;
    } else {
      BD = *ConstB | *ConstD;
      CE = ConstC | ConstE;
    }
    Value *NewAnd = Builder.CreateAnd(A, BD);
    Value *CEVal = ConstantInt::get(A->getType(), CE);
    return Builder.CreateICmp(NewCC, CEVal, NewAnd);
  };

  if (Mask & BMask_Mixed)
    return FoldBMixed(NewCC, false);
  if (Mask & BMask_NotMixed) // can be else also
    return FoldBMixed(NewCC, true);
}

Your code is also correct I think, I just hope we can reuse code as much as possible.
But it depends on you, the code I paste here is also not perfect. It use the flag IsNot too many times that makes the code ugly and a little more cpu overhead.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

717–718

After read the code again I find in the function getMaskedICmpType: the mask BMask_Mixed and BMask_NotMixed already means B&C == C , D&E == E.
So I think early bail out is redundant.

[inclyc]

Address comments form @bcl5980

• Merge Mixed & NotMixed codes
• return Builder.CreateICmp(NewCC, CEVal, NewAnd); -> return Builder.CreateICmp(CC, CEVal, NewAnd);
• Bail out extra assertions

[bcl5980]

LGTM. But please wait for @spatel or @nikic to review current code.

[inclyc]

• vector tests

[inclyc]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

717–718

After read the code again I find in the function getMaskedICmpType: the mask BMask_Mixed and BMask_NotMixed already means B&C == C , D&E == E.
So I think early bail out is redundant.

This looks correct, and we've removed the relevant checks in the code. @spatel WDYT?

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

692

Is there a negative test for this condition? Add a "negative test" comment if it is already here. Otherwise, can we add it?

[inclyc]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

692

Yes. See @masked_icmps_bmask_notmixed_not_subset_notoptimized in D142090. "not subset" refers to this condition

[spatel]

I can't say that I completely understand all of the code paths through foldLogOpOfMaskedICmps(), but we have tests, and it seems to work, so LGTM.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (Mask & AMask_NotAllOnes) {
     // the same as either B or D).
     APInt NewMask = *ConstB | *ConstD;
     if (NewMask == *ConstB)
       return LHS;
     else if (NewMask == *ConstD)
       return RHS;
   }
 
+  if (Mask & BMask_Mixed || Mask & BMask_NotMixed) {
+    // (icmp eq (A & B), C) &/| (icmp eq (A & D), E)
+
+    // (icmp eq (A & B), C) & (icmp eq (A & D), E)
+    // -> (icmp eq (A & (B|D)), (C|E))
+
+    // (icmp eq (A & B), C) | (icmp eq (A & D), E)
+    // -> (icmp eq (A & (B & D)), (C & E))
+
+    if (Mask & BMask_NotMixed)
+      NewCC = CmpInst::getInversePredicate(NewCC);
+    const APInt *OldConstC, *OldConstE;
+    if (!match(C, m_APInt(OldConstC)) || !match(E, m_APInt(OldConstE)))
+      return nullptr;
+
+    const APInt ConstC = PredL != NewCC ? *ConstB ^ *OldConstC : *OldConstC;
+    const APInt ConstE = PredR != NewCC ? *ConstD ^ *OldConstE : *OldConstE;
+
     if (Mask & BMask_Mixed) {
       // (icmp eq (A & B), C) & (icmp eq (A & D), E)
       // We already know that B & C == C && D & E == E.
       // If we can prove that (B & D) & (C ^ E) == 0, that is, the bits of
       // C and E, which are shared by both the mask B and the mask D, don't
       // contradict, then we can transform to
       // -> (icmp eq (A & (B|D)), (C|E))
       // Currently, we only handle the case of B, C, D, and E being constant.
       // We can't simply use C and E because we might actually handle
       //   (icmp ne (A & B), B) & (icmp eq (A & D), D)
       // with B and D, having a single bit set.
-    const APInt *OldConstC, *OldConstE;
-    if (!match(C, m_APInt(OldConstC)) || !match(E, m_APInt(OldConstE)))
-      return nullptr;
-
-    const APInt ConstC = PredL != NewCC ? *ConstB ^ *OldConstC : *OldConstC;
-    const APInt ConstE = PredR != NewCC ? *ConstD ^ *OldConstE : *OldConstE;
 
       // If there is a conflict, we should actually return a false for the
       // whole construct.
       if (((*ConstB & *ConstD) & (ConstC ^ ConstE)).getBoolValue())
         return ConstantInt::get(LHS->getType(), !IsAnd);
-
       Value *NewOr1 = Builder.CreateOr(B, D);
       Value *NewAnd = Builder.CreateAnd(A, NewOr1);
       Constant *NewOr2 = ConstantInt::get(A->getType(), ConstC | ConstE);
       return Builder.CreateICmp(NewCC, NewAnd, NewOr2);
     }
+    // Mask & BMask_NotMixed
+
+    // Check the intersection (B & D) for inequality.
+    // Assume that (B & D) == B || (B & D) == D, i.e B/D is a subset of D/B
+    // and (B & D) & (C ^ E) == 0, bits of C and E, which are shared by both the
+    // B and the D, don't contradict.
+    // Note that we can assume (~B & C) == 0 && (~D & E) == 0, previous
+    // operation should delete these icmps if it hadn't been met.
+
+    // (icmp ne (A & B), C) & (icmp ne (A & D), E)
+    // -> (icmp ne (A & (B & D)), (C & E))
+    const APInt ConstT = *ConstB & *ConstD;
+    if (ConstT != *ConstB && ConstT != *ConstD)
+      return nullptr;
+
+    if ((~*ConstB & ConstC) != 0 || (~*ConstD & ConstE) != 0)
+      return nullptr;
 
+    // If there is a conflict, we still have to check both sides.
+    if (((*ConstB & *ConstD) & (ConstC ^ ConstE)).getBoolValue())
+      return nullptr;
+
+    Value *NewAnd1 = Builder.CreateAnd(A, ConstT);
+    Value *NewAnd2 = ConstantInt::get(A->getType(), ConstC & ConstE);
+    return Builder.CreateICmp(NewCC, NewAnd1, NewAnd2);
+  }
   return nullptr;
 }
 
 /// Try to fold a signed range checked with lower bound 0 to an unsigned icmp.
 /// Example: (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
 /// If \p Inverted is true then the check is for the inverted range, e.g.
 /// (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n
 Value *InstCombinerImpl::simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1,
                                             bool Inverted) {
   // Check the lower range comparison, e.g. x >= 0
   // InstCombine already ensured that if there is a constant it's on the RHS.
   ConstantInt *RangeStart = dyn_cast<ConstantInt>(Cmp0->getOperand(1));
   if (!RangeStart)
     return nullptr;
 
   ICmpInst::Predicate Pred0 = (Inverted ? Cmp0->getInversePredicate() :
                                Cmp0->getPredicate());
 
   // Accept x > -1 or x >= 0 (after potentially inverting the predicate).
   if (!((Pred0 == ICmpInst::ICMP_SGT && RangeStart->isMinusOne()) ||
         (Pred0 == ICmpInst::ICMP_SGE && RangeStart->isZero())))
     return nullptr;
 
   ICmpInst::Predicate Pred1 = (Inverted ? Cmp1->getInversePredicate() :
                                Cmp1->getPredicate());
 
   Value *Input = Cmp0->getOperand(0);
   Value *RangeEnd;
   if (Cmp1->getOperand(0) == Input) {
     // For the upper range compare we have: icmp x, n
     RangeEnd = Cmp1->getOperand(1);
   } else if (Cmp1->getOperand(1) == Input) {
     // For the upper range compare we have: icmp n, x
     RangeEnd = Cmp1->getOperand(0);
     Pred1 = ICmpInst::getSwappedPredicate(Pred1);
   } else {
     return nullptr;
   }
 
   // Check the upper range comparison, e.g. x < n

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

;
   %tst2 = icmp eq i32 %mask2, 0
   %res = select i1 %tst1, i1 true, i1 %tst2
   ret i1 %res
 }
 
 
 define i1 @masked_or_eq(i32 %A) {
 ; CHECK-LABEL: @masked_or_eq(
-; CHECK-NEXT:    [[MASK1:%.*]] = and i32 [[A:%.*]], 15
-; CHECK-NEXT:    [[TST1:%.*]] = icmp eq i32 [[MASK1]], 3
-; CHECK-NEXT:    [[MASK2:%.*]] = and i32 [[A]], 255
-; CHECK-NEXT:    [[TST2:%.*]] = icmp eq i32 [[MASK2]], 243
-; CHECK-NEXT:    [[RES:%.*]] = or i1 [[TST1]], [[TST2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], 15
+; CHECK-NEXT:    [[RES:%.*]] = icmp eq i32 [[TMP1]], 3
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %mask1 = and i32 %A, 15 ; 0x0f
   %tst1 = icmp eq i32 %mask1, 3 ; 0x03
   %mask2 = and i32 %A, 255 ; 0xff
   %tst2 = icmp eq i32 %mask2, 243; 0xf3
   %res = or i1 %tst1, %tst2
   ret i1 %res
;
   %mask2 = and i32 %A, 255 ; 0xff
   %tst2 = icmp eq i32 %mask2, 242; 0xf2
   %res = or i1 %tst1, %tst2
   ret i1 %res
 }
 
 define i1 @masked_and_ne(i32 %A) {
 ; CHECK-LABEL: @masked_and_ne(
-; CHECK-NEXT:    [[MASK1:%.*]] = and i32 [[A:%.*]], 15
-; CHECK-NEXT:    [[TST1:%.*]] = icmp ne i32 [[MASK1]], 3
-; CHECK-NEXT:    [[MASK2:%.*]] = and i32 [[A]], 255
-; CHECK-NEXT:    [[TST2:%.*]] = icmp ne i32 [[MASK2]], 243
-; CHECK-NEXT:    [[RES:%.*]] = and i1 [[TST1]], [[TST2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], 15
+; CHECK-NEXT:    [[RES:%.*]] = icmp ne i32 [[TMP1]], 3
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %mask1 = and i32 %A, 15 ; 0x0f
   %tst1 = icmp ne i32 %mask1, 3 ; 0x03
   %mask2 = and i32 %A, 255 ; 0xff
   %tst2 = icmp ne i32 %mask2, 243 ; 0xf3
   %res = and i1 %tst1, %tst2
   ret i1 %res