This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] combine intersection for inequality icmps
ClosedPublic

Authored by inclyc on Dec 25 2022, 10:50 PM.

Details

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

Diff Detail

Event Timeline

inclyc created this revision.Dec 25 2022, 10:50 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 25 2022, 10:50 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
inclyc requested review of this revision.Dec 25 2022, 10:50 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 25 2022, 10:50 PM
inclyc edited the summary of this revision. (Show Details)Dec 25 2022, 10:51 PM
inclyc added a reviewer: nikic.
inclyc updated this revision to Diff 485339.Dec 26 2022, 8:01 PM

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 edited the summary of this revision. (Show Details)Dec 26 2022, 8:05 PM
inclyc updated this revision to Diff 485341.Dec 26 2022, 8:41 PM
inclyc edited the summary of this revision. (Show Details)

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

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

inclyc planned changes to this revision.Jan 3 2023, 1:37 AM

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 edited the summary of this revision. (Show Details)Jan 3 2023, 7:41 PM

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
697–698

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.

704

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 added inline comments.Jan 17 2023, 11:45 PM
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
627–628

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

697–698

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

spatel added inline comments.Jan 18 2023, 5:08 AM
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
697–698

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 added inline comments.Jan 18 2023, 6:05 PM
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
697–698

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

inclyc updated this revision to Diff 490411.Jan 19 2023, 1:28 AM

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 added inline comments.Jan 19 2023, 4:46 AM
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
627–628

Is Mask & (BMask_Mixed | BMask_NotMixed) better?

643–644

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
663–670

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);
}
679

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

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 requested changes to this revision.Jan 20 2023, 10:33 AM

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.

This revision now requires changes to proceed.Jan 20 2023, 10:33 AM
inclyc planned changes to this revision.Jan 22 2023, 8:22 AM

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 added a comment.EditedJan 24 2023, 5:13 AM

@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 updated this revision to Diff 491739.Jan 24 2023, 6:03 AM

unmerge instcombine

inclyc planned changes to this revision.Jan 24 2023, 8:20 PM
inclyc updated this revision to Diff 492032.Jan 25 2023, 2:00 AM
  • use "ConstT" instead of creating new instruction
inclyc updated this revision to Diff 492043.Jan 25 2023, 2:29 AM

add test masked_and_expected_false

@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.

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?

inclyc marked 5 inline comments as done.Jan 29 2023, 5:01 AM

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
697–698

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 updated this revision to Diff 493501.Jan 31 2023, 12:01 AM

Address comments form @bcl5980

  • Merge Mixed & NotMixed codes
  • return Builder.CreateICmp(NewCC, CEVal, NewAnd); -> return Builder.CreateICmp(CC, CEVal, NewAnd);
  • Bail out extra assertions
inclyc marked 6 inline comments as done.Jan 31 2023, 12:05 AM
bcl5980 accepted this revision.Jan 31 2023, 7:15 PM

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

inclyc updated this revision to Diff 494135.Feb 1 2023, 6:12 PM
  • vector tests
inclyc added inline comments.Feb 5 2023, 5:38 PM
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
697–698

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 added inline comments.Feb 8 2023, 10:28 AM
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
671

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

inclyc added inline comments.Feb 8 2023, 11:47 PM
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
671

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

spatel accepted this revision.Feb 9 2023, 12:34 PM

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.

This revision is now accepted and ready to land.Feb 9 2023, 12:34 PM
This revision was landed with ongoing or failed builds.Feb 9 2023, 8:50 PM
This revision was automatically updated to reflect the committed changes.