[InstSimplify] Simplify bool icmp with not in LHS

[hasyimibhar]

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

[spatel]

llvm/lib/Analysis/InstructionSimplify.cpp

2707

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

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.

[hasyimibhar]

Handle general case with not in LHS

[hasyimibhar]

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

[hasyimibhar]

Rebase

[hasyimibhar]

Fix commit

[hasyimibhar]

Fix author email

[spatel]

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?

[hasyimibhar]

Don't change LHS and Pred

[hasyimibhar]

In D114666#3172182, @spatel wrote:

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]

In D114666#3172200, @hasyimibhar wrote:

In D114666#3172182, @spatel wrote:

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

[hasyimibhar]

Baseline tests added here: https://reviews.llvm.org/D115209

[spatel]

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

2708–2717

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.

2712–2713

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.

[hasyimibhar]

Fix simplification logic

[hasyimibhar]

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]

Run git-clang-format

[spatel]

llvm/lib/Analysis/InstructionSimplify.cpp

2707–2717

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.

2712

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]

llvm/lib/Analysis/InstructionSimplify.cpp

2729

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

--

[hasyimibhar]

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

[hasyimibhar]

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

• Test with xor operands swapped (using m_Xor would have missed this)
• Test with undef (based on alive: https://alive2.llvm.org/ce/z/mFCLsM)

[hasyimibhar]

Revert test rename

[spatel]

llvm/lib/Analysis/InstructionSimplify.cpp

2729

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

2. 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]

llvm/lib/Analysis/InstructionSimplify.cpp

2729

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]

LGTM - thanks for working through the feedback!

llvm/lib/Analysis/InstructionSimplify.cpp

2729

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.

llvm/lib/Analysis/InstructionSimplify.cpp

 /// Fold an icmp when its operands have i1 scalar type.
 static Value *simplifyICmpOfBools(CmpInst::Predicate Pred, Value *LHS,
                                   Value *RHS, const SimplifyQuery &Q) {
   Type *ITy = GetCompareTy(LHS); // The return type.
   Type *OpTy = LHS->getType();   // The operand type.
   if (!OpTy->isIntOrIntVectorTy(1))
     return nullptr;
 
   // A boolean compared to true/false can be simplified in 14 out of the 20
-  // (10 predicates * 2 constants) possible combinations. Cases not handled here
-  // require a 'not' of the LHS, so those must be transformed in InstCombine.
+  // (10 predicates * 2 constants) possible combinations.
+
+  // If LHS is of the form not(X), inverse the predicate.
+  // E.g not(X) == 0 -> X != 0
+  Value *X;
+  if (match(LHS, m_Xor(m_Value(X), m_One()))) {
+    Pred = CmpInst::getInversePredicate(Pred);
+    LHS = X;
+  }
+
   if (match(RHS, m_Zero())) {
     switch (Pred) {
     case CmpInst::ICMP_NE:  // X !=  0 -> X
     case CmpInst::ICMP_UGT: // X >u  0 -> X
     case CmpInst::ICMP_SLT: // X <s  0 -> X
       return LHS;
 
     case CmpInst::ICMP_ULT: // X <u  0 -> false
     case CmpInst::ICMP_SGT: // X >s  0 -> false
       return getFalse(ITy);
 
     case CmpInst::ICMP_UGE: // X >=u 0 -> true
     case CmpInst::ICMP_SLE: // X <=s 0 -> true
       return getTrue(ITy);
 
     default: break;
     }
   } else if (match(RHS, m_One())) {
     switch (Pred) {
     case CmpInst::ICMP_EQ:  // X ==   1 -> X

llvm/test/Transforms/InstSimplify/icmp.ll

 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %mul = shl i8 %x, 2
   %div = udiv i8 %mul, 3
   %cmp = icmp ule i8 %div, %x
   ret i1 %cmp
 }
 
+; Test simplification with not in LHS
+
+define i1 @not_cmp_eq(i1 %x) {
+; CHECK-LABEL: @not_cmp_eq(
+; CHECK-NEXT:    ret i1 %x
+;
+  %not = xor i1 %x, true
+  %cmp = icmp eq i1 %not, 0
+  ret i1 %cmp
+}
+
+define i1 @not_cmp_ule(i1 %x) {
+; CHECK-LABEL: @not_cmp_ule(
+; CHECK-NEXT:    ret i1 %x
+;
+  %not = xor i1 %x, true
+  %cmp = icmp ule i1 %not, 0
+  ret i1 %cmp
+}
+
+define i1 @not_cmp_sge(i1 %x) {
+; CHECK-LABEL: @not_cmp_sge(
+; CHECK-NEXT:    ret i1 %x
+;
+  %not = xor i1 %x, true
+  %cmp = icmp sge i1 %not, 0
+  ret i1 %cmp
+}
+
+define i1 @not_cmp_ne(i1 %x) {
+; CHECK-LABEL: @not_cmp_ne(
+; CHECK-NEXT:    ret i1 %x
+;
+  %not = xor i1 %x, true
+  %cmp = icmp ne i1 %not, true
+  ret i1 %cmp
+}
+
+define i1 @not_cmp_ult(i1 %x) {
+; CHECK-LABEL: @not_cmp_ult(
+; CHECK-NEXT:    ret i1 %x
+;
+  %not = xor i1 %x, true
+  %cmp = icmp ult i1 %not, 1
+  ret i1 %cmp
+}
+
+define i1 @not_cmp_sgt(i1 %x) {
+; CHECK-LABEL: @not_cmp_sgt(
+; CHECK-NEXT:    ret i1 %x
+;
+  %not = xor i1 %x, true
+  %cmp = icmp sgt i1 %not, -1
+  ret i1 %cmp
+}
+
+define i1 @not_cmp_sext(i1 %x) {
+; CHECK-LABEL: @not_cmp_sext(
+; CHECK-NEXT:    ret i1 %x
+;
+  %not = xor i1 %x, true
+  %t0 = sext i1 %not to i32
+  %cmp = icmp eq i32 %t0, 0
+  ret i1 %cmp
+}
+
 ; Don't crash matching recurrences/invertible ops.
 
 define void @PR50191(i32 %x) {
 ; CHECK-LABEL: @PR50191(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[P1:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[SUB1:%.*]], [[LOOP]] ]