[InstCombine] Fold icmp x, ~x and icmp ~x, x by testing the sign

[tianz]

Summary

[InstCombine] Fold icmp x, ~x and icmp ~x, x by testing the sign

Fixes #57532.

Examples:
https://alive2.llvm.org/ce/z/XBj9Pf
https://alive2.llvm.org/ce/z/UNkucP

[tianz]

Baseline tests: https://reviews.llvm.org/D133330

[RKSimon]

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

8

please don't enumerate tests - chose a name that describes the pattern + any specific constant you're using

[RKSimon]

@tianz reverse-ping

[tianz]

Updated the tests according to review comment

[spatel]

The predicate check is too restrictive. We can handle unsigned preds too:
https://alive2.llvm.org/ce/z/s38fNL

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (match(Op0, m_Not(m_Value(A)))) {
         return new ICmpInst(I.getPredicate(), B, A);
 
       const APInt *C;
       if (match(Op1, m_APInt(C)))
         return new ICmpInst(I.getSwappedPredicate(), A,
                             ConstantInt::get(Op1->getType(), ~(*C)));
     }
 
+    // Try to fold icmp x, ~x and icmp ~x, x by testing the sign
+    if (((match(Op1, m_Not(m_Value(A))) && Op0 == A) ||
+         (match(Op0, m_Not(m_Value(A))) && Op1 == A)) &&
+        ICmpInst::isSigned(I.getPredicate())) {
+      CmpInst::Predicate NewPred =
+          (Op1 == A) ? I.getSwappedPredicate() : I.getPredicate();
+
+      if (I.getPredicate() == ICmpInst::ICMP_SLT ||
+          I.getPredicate() == ICmpInst::ICMP_SLE) {
+        NewPred = ICmpInst::getStrictPredicate(NewPred);
+      } else {
+        NewPred = ICmpInst::getNonStrictPredicate(NewPred);
+      }
+
+      return new ICmpInst(NewPred, A, Constant::getNullValue(A->getType()));
+    }
+
     Instruction *AddI = nullptr;
     if (match(&I, m_UAddWithOverflow(m_Value(A), m_Value(B),
                                      m_Instruction(AddI))) &&
         isa<IntegerType>(A->getType())) {
       Value *Result;
       Constant *Overflow;
       // m_UAddWithOverflow can match patterns that do not include  an explicit
       // "add" instruction, so check the opcode of the matched op.

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

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -passes=instcombine -S | FileCheck %s
+
+declare void @use16(i16)
+declare void @usev4(<4 x i4>)
+
+define <2 x i1> @icmp_not_sgt(<2 x i32> %_x) {
+; CHECK-LABEL: @icmp_not_sgt(
+; CHECK-NEXT:    [[X:%.*]] = sdiv <2 x i32> <i32 42, i32 42>, [[_X:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt <2 x i32> [[X]], <i32 -1, i32 -1>
+; CHECK-NEXT:    ret <2 x i1> [[CMP]]
+;
+  %x = sdiv <2 x i32> <i32 42, i32 42>, %_x ; thwart complexity-based canonicalization
+  %not = xor <2 x i32> %x, <i32 -1, i32 -1>
+  %cmp = icmp sgt <2 x i32> %x, %not
+  ret <2 x i1> %cmp
+}
+
+define i1 @icmp_not_sgt_swapped(i8 %x) {
+; CHECK-LABEL: @icmp_not_sgt_swapped(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[X:%.*]], 1
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %not = xor i8 %x, -1
+  %cmp = icmp sgt i8 %not, %x
+  ret i1 %cmp
+}
+
+define i1 @icmp__not_sge(i5 %_x) {
+; CHECK-LABEL: @icmp__not_sge(
+; CHECK-NEXT:    [[X:%.*]] = sdiv i5 10, [[_X:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i5 [[X]], -1
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %x = sdiv i5 42, %_x ; thwart complexity-based canonicalization
+  %not = xor i5 %x, -1
+  %cmp = icmp sge i5 %x, %not
+  ret i1 %cmp
+}
+
+define <3 x i1> @icmp_not_sge_swapped(<3 x i7> %x) {
+; CHECK-LABEL: @icmp_not_sge_swapped(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt <3 x i7> [[X:%.*]], <i7 1, i7 1, i7 1>
+; CHECK-NEXT:    ret <3 x i1> [[CMP]]
+;
+  %not = xor <3 x i7> %x, <i7 -1, i7 -1, i7 -1>
+  %cmp = icmp sge <3 x i7> %not, %x
+  ret <3 x i1> %cmp
+}
+
+define <4 x i1> @icmp_not_slt(<4 x i4> %_x) {
+; CHECK-LABEL: @icmp_not_slt(
+; CHECK-NEXT:    [[X:%.*]] = sdiv <4 x i4> <i4 -6, i4 -6, i4 -6, i4 -6>, [[_X:%.*]]
+; CHECK-NEXT:    [[NOT:%.*]] = xor <4 x i4> [[X]], <i4 -1, i4 -1, i4 -1, i4 -1>
+; CHECK-NEXT:    call void @usev4(<4 x i4> [[NOT]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt <4 x i4> [[X]], zeroinitializer
+; CHECK-NEXT:    ret <4 x i1> [[CMP]]
+;
+  %x = sdiv <4 x i4> <i4 42, i4 42, i4 42, i4 42>, %_x ; thwart complexity-based canonicalization
+  %not = xor <4 x i4> %x, <i4 -1, i4 -1, i4 -1, i4 -1>
+  call void @usev4(<4 x i4> %not) ; extra use of xor
+  %cmp = icmp slt <4 x i4> %x, %not
+  ret <4 x i1> %cmp
+}
+
+define i1 @icmp_not_slt_swapped(i16 %x) {
+; CHECK-LABEL: @icmp_not_slt_swapped(
+; CHECK-NEXT:    [[NOT:%.*]] = xor i16 [[X:%.*]], -1
+; CHECK-NEXT:    call void @use16(i16 [[NOT]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i16 [[X]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %not = xor i16 %x, -1
+  call void @use16(i16 %not) ; extra use of xor
+  %cmp = icmp slt i16 %not, %x
+  ret i1 %cmp
+}
+
+define i1 @icmp_not_sle(i8 %_x) {
+; CHECK-LABEL: @icmp_not_sle(
+; CHECK-NEXT:    [[X:%.*]] = sdiv i8 42, [[_X:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[X]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %x = sdiv i8 42, %_x ; thwart complexity-based canonicalization
+  %not = xor i8 %x, -1
+  %cmp = icmp sle i8 %x, %not
+  ret i1 %cmp
+}
+
+define <2 x i1> @icmp_not_sle_swapped(<2 x i8> %x) {
+; CHECK-LABEL: @icmp_not_sle_swapped(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt <2 x i8> [[X:%.*]], zeroinitializer
+; CHECK-NEXT:    ret <2 x i1> [[CMP]]
+;
+  %not = xor <2 x i8> %x, <i8 -1, i8 poison>
+  %cmp = icmp sle <2 x i8> %not, %x
+  ret <2 x i1> %cmp
+}
+
+define i1 @negative_test_unsigned_pred(i8 %x) {
+; CHECK-LABEL: @negative_test_unsigned_pred(
+; CHECK-NEXT:    [[NOT:%.*]] = xor i8 [[X:%.*]], -1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8 [[NOT]], [[X]]
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %not = xor i8 %x, -1
+  %cmp = icmp ugt i8 %not, %x
+  ret i1 %cmp
+}
+
+define i1 @negative_test_equality(i8 %x) {
+; CHECK-LABEL: @negative_test_equality(
+; CHECK-NEXT:    ret i1 false
+;
+  %not = xor i8 %x, -1
+  %cmp = icmp eq i8 %not, %x
+  ret i1 %cmp
+}