Page MenuHomePhabricator

[InstSimplify] Simplify bool icmp with not in LHS
ClosedPublic

Authored by hasyimibhar on Nov 27 2021, 8:25 AM.

Details

Summary

Refer to https://bugs.llvm.org/show_bug.cgi?id=52546. Simplifies the following cases:

  • not(X) == 0 -> X != 0 -> X
  • not(X) <=u 0 -> X >u 0 -> X
  • not(X) >=s 0 -> X <s 0 -> X
  • not(X) != 1 -> X == 1 -> X
  • not(X) <=u 1 -> X >=u 1 -> X
  • not(X) >s 1 -> X <=s -1 -> X

Diff Detail

Event Timeline

hasyimibhar created this revision.Nov 27 2021, 8:25 AM
hasyimibhar requested review of this revision.Nov 27 2021, 8:25 AM
Herald added a project: Restricted Project. · View Herald TranscriptNov 27 2021, 8:25 AM
hasyimibhar retitled this revision from Simplify icmp for bool value to [InstSimplify] Fold bool(X) ^ 1 == 0 to X.Nov 27 2021, 8:51 AM
hasyimibhar edited the summary of this revision. (Show Details)
spatel added inline comments.Nov 28 2021, 7:46 AM
llvm/lib/Analysis/InstructionSimplify.cpp
2705–2706

The comment and code structure suggest that we are missing related patterns.

Can we generalize this to look through a 'not' of LHS and invert/swap the predicate?

For example, we should be able to reduce these patterns too:

define i1 @not_cmp_ne(i1 %x) {
  %not = xor i1 %x, true
  %cmp = icmp ne i1 %not, true
  ret i1 %cmp
}

define i1 @not_cmp_ult(i1 %x) {
  %not = xor i1 %x, true
  %cmp = icmp ult i1 %not, 1
  ret i1 %cmp
}
llvm/test/Transforms/InstSimplify/icmp.ll
194 ↗(On Diff #390163)

We want tests with the sext instruction because this code handles looking through that cast (and possible others?), but the minimal pattern does not include casts. So we need to add tests for code with no sext ops.

Handle general case with not in LHS

@spatel Updated to handle general pattern. Let me know if this is what you mean, as I'm pretty new to LLVM.

hasyimibhar retitled this revision from [InstSimplify] Fold bool(X) ^ 1 == 0 to X to [InstSimplify] Simplify bool icmp with not in LHS.Dec 4 2021, 11:37 PM
hasyimibhar edited the summary of this revision. (Show Details)

Fix author email

spatel added a comment.Dec 5 2021, 8:28 AM

I don't think the logic is correct. You should start by creating a complete set of baseline tests based on the existing tests in:
https://github.com/llvm/llvm-project/blob/main/llvm/test/Transforms/InstSimplify/icmp-bool-constant.ll

We can then pre-commit those tests ahead of this patch to make sure we get correct results in all cases with this patch.

You may also want to check how these patterns are handled by "opt -instcombine" (assuming they are handled correctly there).

Finally, I'm worried about changing the values of LHS or Pred directly in this code because those values are used in other transforms later within simplifyICmpOfBools. We could be silently breaking those transforms if the test coverage for those is not good?

Don't change LHS and Pred

I don't think the logic is correct. You should start by creating a complete set of baseline tests based on the existing tests in:
https://github.com/llvm/llvm-project/blob/main/llvm/test/Transforms/InstSimplify/icmp-bool-constant.ll

We can then pre-commit those tests ahead of this patch to make sure we get correct results in all cases with this patch.

You may also want to check how these patterns are handled by "opt -instcombine" (assuming they are handled correctly there).

I don't quite understand. Do you mean I should create a separate revision that contains only passing test cases to show how this case is currently being handled by both instsimplify and instcombine?

spatel added a comment.Dec 5 2021, 9:28 AM

I don't think the logic is correct. You should start by creating a complete set of baseline tests based on the existing tests in:
https://github.com/llvm/llvm-project/blob/main/llvm/test/Transforms/InstSimplify/icmp-bool-constant.ll

We can then pre-commit those tests ahead of this patch to make sure we get correct results in all cases with this patch.

You may also want to check how these patterns are handled by "opt -instcombine" (assuming they are handled correctly there).

I don't quite understand. Do you mean I should create a separate revision that contains only passing test cases to show how this case is currently being handled by both instsimplify and instcombine?

Yes, you can create a patch that just adds all of the tests with baseline CHECK results (without this patch) to the file "icmp-bool-constant.ll".
You can either commit that locally and show diffs on this patch, push it to main, or post it to Phabricator if you don't have commit access yet.

To check if your logic is correct, compare results against "opt -instcombine" and/or use Alive2:
https://alive2.llvm.org/ce/z/VzNJsr

spatel added a comment.Dec 8 2021, 6:07 AM

I pushed the baseline tests with:
64d4bd02dc3f

So this patch can be rebased/updated to show diffs on those (and we can confirm that the transform is correct by comparing against the instcombine results).

llvm/lib/Analysis/InstructionSimplify.cpp
2706–2716

The code comment should not be deleted. It is referring to patterns like this:
https://alive2.llvm.org/ce/z/3rhGa5
In that case, we can't do anything in instsimplify because we do not create new values here. But instcombine has the ability to create a new instruction.

2710–2711

Please make a helper function or lambda to give these values smaller scope. It is not accurate to name these "*Not" in the case that we are not matching a 'not' instruction, so a different (more generic) name would be better.

Fix simplification logic

I fixed the logic so that only 6 cases should be affected. I double checked with this: https://alive2.llvm.org/ce/z/uZiDpt

hasyimibhar edited the summary of this revision. (Show Details)Dec 9 2021, 5:02 AM
hasyimibhar edited the summary of this revision. (Show Details)

Run git-clang-format

spatel added inline comments.Dec 9 2021, 6:13 AM
llvm/lib/Analysis/InstructionSimplify.cpp
2705–2716

Given the new version of the patch, we should update this comment. :)
Something like this might explain better:

// A boolean compared to true/false can be reduced in 14 out of the 20
// (10 predicates * 2 constants) possible combinations directly. The other
// 6 cases require a 'not' of the LHS.
2710

Is there a reason to use m_Xor() rather than m_Not()?
Is the transform safe with vector types that might have undef elements?
For example:

define <2 x i1> @ult_t_not(<2 x i1> %a) {
  %not = xor <2 x i1> %a, <i1 undef, i1 true>
  %r = icmp ult <2 x i1> %not, <i1 true, i1 true>
  ret <2 x i1> %r
}
hasyimibhar added inline comments.Dec 9 2021, 6:35 AM
llvm/lib/Analysis/InstructionSimplify.cpp
2728

@spatel I missed adding a break; here (and below), and I noticed that this is the reason why check-polly is failing. Do you know what kind of tests I could add to icmp-not-bool-contant.ll to catch this mistake? If it weren't for the failing check-polly test, I would have missed this.

--
/Users/hasyimibahrudin/workspace/llvm/llvm-project/polly/test/Support/dumpmodule.ll:78:15: error: AFTEREARLY: expected string not found in input
; AFTEREARLY: polly.split_new_and_old:
              ^
/Users/hasyimibahrudin/workspace/llvm/llvm-project/build/tools/polly/test/Support/Output/dumpmodule.ll.tmp-npm-after-early.ll:4:30: note: scanning from here
define internal void @callee(i32 %n, double* noalias nonnull %A, i32 %i) #0 {
                             ^
/Users/hasyimibahrudin/workspace/llvm/llvm-project/build/tools/polly/test/Support/Output/dumpmodule.ll.tmp-npm-after-early.ll:9:18: note: possible intended match here
body: ; preds = %entry.split, %body
                 ^

Input file: /Users/hasyimibahrudin/workspace/llvm/llvm-project/build/tools/polly/test/Support/Output/dumpmodule.ll.tmp-npm-after-early.ll
Check file: /Users/hasyimibahrudin/workspace/llvm/llvm-project/polly/test/Support/dumpmodule.ll

-dump-input=help explains the following input dump.

Input was:
<<<<<<
            1: ; ModuleID = '<stdin>'
            2: source_filename = "<stdin>"
            3:
            4: define internal void @callee(i32 %n, double* noalias nonnull %A, i32 %i) #0 {
check:78'0                                  X~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ error: no match found
            5: entry.split:
check:78'0     ~~~~~~~~~~~~~
            6:  %j.cmp1 = icmp sgt i32 %n, 0
check:78'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
            7:  br i1 %j.cmp1, label %body, label %return
check:78'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
            8:
check:78'0     ~
            9: body: ; preds = %entry.split, %body
check:78'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
check:78'1                      ?                   possible intended match
           10:  %j2 = phi i32 [ %j.inc, %body ], [ 0, %entry.split ]
check:78'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           11:  %idx = add i32 %j2, %i
check:78'0     ~~~~~~~~~~~~~~~~~~~~~~~~
           12:  %0 = sext i32 %idx to i64
check:78'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~
           13:  %arrayidx = getelementptr inbounds double, double* %A, i64 %0
check:78'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           14:  store double 4.200000e+01, double* %arrayidx, align 8
check:78'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
            .
            .
            .
>>>>>>
--
--
/Users/hasyimibahrudin/workspace/llvm/llvm-project/polly/test/Support/pipelineposition.ll:87:18: error: INLINED2-NEXT: expected string not found in input
; INLINED2-NEXT: [n] -> { Stmt_polly_loop_header_i_us_us[i0, i1] -> [i0, 1, i1] };
                 ^
<stdin>:59:13: note: scanning from here
 Schedule :=
            ^
<stdin>:60:2: note: possible intended match here
 [n] -> { Stmt_body_i_us[i0, i1] -> [i0, i1] };
 ^

Input file: <stdin>
Check file: /Users/hasyimibahrudin/workspace/llvm/llvm-project/polly/test/Support/pipelineposition.ll

-dump-input=help explains the following input dump.

Input was:
<<<<<<
           .
           .
           .
          54:  n/a
          55:  Statements {
          56:  Stmt_body_i_us
          57:  Domain :=
          58:  [n] -> { Stmt_body_i_us[i0, i1] : 0 <= i0 < n and 0 <= i1 < n };
          59:  Schedule :=
next:87'0                 X error: no match found
          60:  [n] -> { Stmt_body_i_us[i0, i1] -> [i0, i1] };
next:87'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
next:87'1      ?                                               possible intended match
          61:  MustWriteAccess := [Reduction Type: NONE] [Scalar: 0]
next:87'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
          62:  [n] -> { Stmt_body_i_us[i0, i1] -> MemRef_A[i0 + i1] };
next:87'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
          63:  }
next:87'0     ~~~
>>>>>>

--
  • Fix missing break
  • Use m_Not instead of m_Xor
  • Add more test cases

I added 2 extra test cases for each of the 6 cases:

Revert test rename

spatel added inline comments.Dec 9 2021, 7:38 AM
llvm/lib/Analysis/InstructionSimplify.cpp
2728

I don't know how that mistake could be missed.

  1. If I compile the earlier draft of the patch locally, I see compiler warnings:
/llvm-project/llvm/lib/Analysis/InstructionSimplify.cpp:2730:5: warning: unannotated fall-through between switch labels [-Wimplicit-fallthrough]
    case CmpInst::ICMP_ULT: // X <u  0 -> false
  1. If I run the regression tests, there were test failures:
% ninja check-llvm-transforms
...
Failed Tests (3):
  LLVM :: Transforms/InstSimplify/icmp-bool-constant.ll
  LLVM :: Transforms/InstSimplify/select-inseltpoison.ll
  LLVM :: Transforms/InstSimplify/select.ll

If the tests without a 'not' instruction did not exist already, then we should have added them as part of this patch or the preliminary patch that added tests. But since they already exist, I don't think it is worth duplicating them.

hasyimibhar added inline comments.Dec 9 2021, 8:07 AM
llvm/lib/Analysis/InstructionSimplify.cpp
2728

You are right. If I remove the break, I can see lots of tests failing with check-llvm-transforms (I didn't know about this test). I probably missed this because I was looking at the failing tests on harbormaster, not locally. So I could have missed the other failing tests and only noticed the most recent failed tests, which was check-polly.

spatel accepted this revision.Dec 9 2021, 8:36 AM

LGTM - thanks for working through the feedback!

llvm/lib/Analysis/InstructionSimplify.cpp
2728

It's not clear to me what tests the pre-commit / Phabricator hooks are running currently...

But you should always run the regression tests locally to save a lot of suffering:
https://llvm.org/docs/GettingStarted.html#for-developers-to-commit-changes-from-git

Note that "$ ninja check-llvm-transforms" is a subset of the more general "$ ninja check" command" - best to run the entire set of tests, or you'll probably break a lot of bots (and get a lot of fail mails) if any of those tests break locally.

This revision is now accepted and ready to land.Dec 9 2021, 8:36 AM
This revision was automatically updated to reflect the committed changes.