[NFC][X86][AArch64] Add 'A - (A & B)' pattern tests (PR44448)

The fold 'A - (A & (B - 1))' -> 'A & (0 - B)'
added in 8dab0a4a7d691f2704f1079538e0ef29548db159
is too specific. It should just be 'A - (A & B)' -> 'A & (~B)'

Name: X - (X & Y)  ->  X & (~Y)
%o = and i32 %X, %Y
%r = sub i32 %X, %o
  =>
%n = xor i32 %Y, -1
%r = and i32 %X, %n

https://rise4fun.com/Alive/kOUl

See
  https://bugs.llvm.org/show_bug.cgi?id=44448
  https://reviews.llvm.org/D71499

2 files changed, 297 insertions, 0 deletions

diff --git a/llvm/test/CodeGen/AArch64/sub-of-bias.ll b/llvm/test/CodeGen/AArch64/sub-of-bias.ll
new file mode 100644
index 00000000000..8a80ff8d7b6
--- /dev/null
+++ b/llvm/test/CodeGen/AArch64/sub-of-bias.ll
@@ -0,0 +1,107 @@
+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple=aarch64-unknown-linux-gnu < %s | FileCheck %s
+
+; Fold
+;   ptr - (ptr & mask)
+; To
+;   ptr & (~mask)
+;
+; This needs to be a backend-level fold because only by now pointers
+; are just registers; in middle-end IR this can only be done via @llvm.ptrmask()
+; intrinsic which is not sufficiently widely-spread yet.
+;
+; https://bugs.llvm.org/show_bug.cgi?id=44448
+
+; The basic positive tests
+
+define i32 @t0_32(i32 %ptr, i32 %mask) nounwind {
+; CHECK-LABEL: t0_32:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    and w8, w0, w1
+; CHECK-NEXT:    sub w0, w0, w8
+; CHECK-NEXT:    ret
+  %bias = and i32 %ptr, %mask
+  %r = sub i32 %ptr, %bias
+  ret i32 %r
+}
+define i64 @t1_64(i64 %ptr, i64 %mask) nounwind {
+; CHECK-LABEL: t1_64:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    and x8, x0, x1
+; CHECK-NEXT:    sub x0, x0, x8
+; CHECK-NEXT:    ret
+  %bias = and i64 %ptr, %mask
+  %r = sub i64 %ptr, %bias
+  ret i64 %r
+}
+
+define i32 @t2_commutative(i32 %ptr, i32 %mask) nounwind {
+; CHECK-LABEL: t2_commutative:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    and w8, w1, w0
+; CHECK-NEXT:    sub w0, w0, w8
+; CHECK-NEXT:    ret
+  %bias = and i32 %mask, %ptr ; swapped
+  %r = sub i32 %ptr, %bias
+  ret i32 %r
+}
+
+; Extra use tests
+
+define i32 @n3_extrause1(i32 %ptr, i32 %mask, i32* %bias_storage) nounwind {
+; CHECK-LABEL: n3_extrause1:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    and w8, w0, w1
+; CHECK-NEXT:    sub w0, w0, w8
+; CHECK-NEXT:    str w8, [x2]
+; CHECK-NEXT:    ret
+  %bias = and i32 %ptr, %mask ; has extra uses, can't fold
+  store i32 %bias, i32* %bias_storage
+  %r = sub i32 %ptr, %bias
+  ret i32 %r
+}
+
+; Negative tests
+
+define i32 @n4_different_ptrs(i32 %ptr0, i32 %ptr1, i32 %mask) nounwind {
+; CHECK-LABEL: n4_different_ptrs:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    and w8, w1, w2
+; CHECK-NEXT:    sub w0, w0, w8
+; CHECK-NEXT:    ret
+  %bias = and i32 %ptr1, %mask ; not %ptr0
+  %r = sub i32 %ptr0, %bias ; not %ptr1
+  ret i32 %r
+}
+define i32 @n5_different_ptrs_commutative(i32 %ptr0, i32 %ptr1, i32 %mask) nounwind {
+; CHECK-LABEL: n5_different_ptrs_commutative:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    and w8, w2, w1
+; CHECK-NEXT:    sub w0, w0, w8
+; CHECK-NEXT:    ret
+  %bias = and i32 %mask, %ptr1 ; swapped, not %ptr0
+  %r = sub i32 %ptr0, %bias ; not %ptr1
+  ret i32 %r
+}
+
+define i32 @n6_not_lowbit_mask(i32 %ptr, i32 %mask) nounwind {
+; CHECK-LABEL: n6_not_lowbit_mask:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    and w8, w0, w1
+; CHECK-NEXT:    sub w0, w0, w8
+; CHECK-NEXT:    ret
+  %bias = and i32 %ptr, %mask
+  %r = sub i32 %ptr, %bias
+  ret i32 %r
+}
+
+define i32 @n7_sub_is_not_commutative(i32 %ptr, i32 %mask) nounwind {
+; CHECK-LABEL: n7_sub_is_not_commutative:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    and w8, w0, w1
+; CHECK-NEXT:    sub w0, w8, w0
+; CHECK-NEXT:    ret
+  %bias = and i32 %ptr, %mask
+  %r = sub i32 %bias, %ptr ; wrong order
+  ret i32 %r
+}
diff --git a/llvm/test/CodeGen/X86/sub-of-bias.ll b/llvm/test/CodeGen/X86/sub-of-bias.ll
new file mode 100644
index 00000000000..a51b909bf93
--- /dev/null
+++ b/llvm/test/CodeGen/X86/sub-of-bias.ll
@@ -0,0 +1,190 @@
+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple=i686-unknown-linux-gnu             < %s | FileCheck %s   --check-prefixes=CHECK,NOBMI,X86,NOBMI-X86
+; RUN: llc -mtriple=i686-unknown-linux-gnu -mattr=+bmi < %s | FileCheck %s   --check-prefixes=CHECK,BMI,X86,BMI-X86
+; RUN: llc -mtriple=x86_64-unknown-linux-gnu             < %s | FileCheck %s --check-prefixes=CHECK,NOBMI,X64,NOBMI-X64
+; RUN: llc -mtriple=x86_64-unknown-linux-gnu -mattr=+bmi < %s | FileCheck %s --check-prefixes=CHECK,BMI,X64,BMI-X64
+
+; Fold
+;   ptr - (ptr & mask)
+; To
+;   ptr & (~mask)
+;
+; This needs to be a backend-level fold because only by now pointers
+; are just registers; in middle-end IR this can only be done via @llvm.ptrmask()
+; intrinsic which is not sufficiently widely-spread yet.
+;
+; https://bugs.llvm.org/show_bug.cgi?id=44448
+
+; The basic positive tests
+
+define i32 @t0_32(i32 %ptr, i32 %mask) nounwind {
+; X86-LABEL: t0_32:
+; X86:       # %bb.0:
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    andl %eax, %ecx
+; X86-NEXT:    subl %ecx, %eax
+; X86-NEXT:    retl
+;
+; X64-LABEL: t0_32:
+; X64:       # %bb.0:
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    andl %edi, %esi
+; X64-NEXT:    subl %esi, %eax
+; X64-NEXT:    retq
+  %bias = and i32 %ptr, %mask
+  %r = sub i32 %ptr, %bias
+  ret i32 %r
+}
+define i64 @t1_64(i64 %ptr, i64 %mask) nounwind {
+; X86-LABEL: t1_64:
+; X86:       # %bb.0:
+; X86-NEXT:    pushl %esi
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    andl %edx, %ecx
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %esi
+; X86-NEXT:    andl %eax, %esi
+; X86-NEXT:    subl %esi, %eax
+; X86-NEXT:    sbbl %ecx, %edx
+; X86-NEXT:    popl %esi
+; X86-NEXT:    retl
+;
+; X64-LABEL: t1_64:
+; X64:       # %bb.0:
+; X64-NEXT:    movq %rdi, %rax
+; X64-NEXT:    andq %rdi, %rsi
+; X64-NEXT:    subq %rsi, %rax
+; X64-NEXT:    retq
+  %bias = and i64 %ptr, %mask
+  %r = sub i64 %ptr, %bias
+  ret i64 %r
+}
+
+define i32 @t2_commutative(i32 %ptr, i32 %mask) nounwind {
+; X86-LABEL: t2_commutative:
+; X86:       # %bb.0:
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    andl %eax, %ecx
+; X86-NEXT:    subl %ecx, %eax
+; X86-NEXT:    retl
+;
+; X64-LABEL: t2_commutative:
+; X64:       # %bb.0:
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    andl %edi, %esi
+; X64-NEXT:    subl %esi, %eax
+; X64-NEXT:    retq
+  %bias = and i32 %mask, %ptr ; swapped
+  %r = sub i32 %ptr, %bias
+  ret i32 %r
+}
+
+; Extra use tests
+
+define i32 @n3_extrause1(i32 %ptr, i32 %mask, i32* %bias_storage) nounwind {
+; X86-LABEL: n3_extrause1:
+; X86:       # %bb.0:
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
+; X86-NEXT:    andl %eax, %edx
+; X86-NEXT:    movl %edx, (%ecx)
+; X86-NEXT:    subl %edx, %eax
+; X86-NEXT:    retl
+;
+; X64-LABEL: n3_extrause1:
+; X64:       # %bb.0:
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    andl %edi, %esi
+; X64-NEXT:    movl %esi, (%rdx)
+; X64-NEXT:    subl %esi, %eax
+; X64-NEXT:    retq
+  %bias = and i32 %ptr, %mask ; has extra uses, can't fold
+  store i32 %bias, i32* %bias_storage
+  %r = sub i32 %ptr, %bias
+  ret i32 %r
+}
+
+; Negative tests
+
+define i32 @n4_different_ptrs(i32 %ptr0, i32 %ptr1, i32 %mask) nounwind {
+; X86-LABEL: n4_different_ptrs:
+; X86:       # %bb.0:
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    andl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    subl %ecx, %eax
+; X86-NEXT:    retl
+;
+; X64-LABEL: n4_different_ptrs:
+; X64:       # %bb.0:
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    andl %edx, %esi
+; X64-NEXT:    subl %esi, %eax
+; X64-NEXT:    retq
+  %bias = and i32 %ptr1, %mask ; not %ptr0
+  %r = sub i32 %ptr0, %bias ; not %ptr1
+  ret i32 %r
+}
+define i32 @n5_different_ptrs_commutative(i32 %ptr0, i32 %ptr1, i32 %mask) nounwind {
+; X86-LABEL: n5_different_ptrs_commutative:
+; X86:       # %bb.0:
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    andl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    subl %ecx, %eax
+; X86-NEXT:    retl
+;
+; X64-LABEL: n5_different_ptrs_commutative:
+; X64:       # %bb.0:
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    andl %edx, %esi
+; X64-NEXT:    subl %esi, %eax
+; X64-NEXT:    retq
+  %bias = and i32 %mask, %ptr1 ; swapped, not %ptr0
+  %r = sub i32 %ptr0, %bias ; not %ptr1
+  ret i32 %r
+}
+
+define i32 @n6_not_lowbit_mask(i32 %ptr, i32 %mask) nounwind {
+; X86-LABEL: n6_not_lowbit_mask:
+; X86:       # %bb.0:
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    andl %eax, %ecx
+; X86-NEXT:    subl %ecx, %eax
+; X86-NEXT:    retl
+;
+; X64-LABEL: n6_not_lowbit_mask:
+; X64:       # %bb.0:
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    andl %edi, %esi
+; X64-NEXT:    subl %esi, %eax
+; X64-NEXT:    retq
+  %bias = and i32 %ptr, %mask
+  %r = sub i32 %ptr, %bias
+  ret i32 %r
+}
+
+define i32 @n7_sub_is_not_commutative(i32 %ptr, i32 %mask) nounwind {
+; X86-LABEL: n7_sub_is_not_commutative:
+; X86:       # %bb.0:
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    andl %ecx, %eax
+; X86-NEXT:    subl %ecx, %eax
+; X86-NEXT:    retl
+;
+; X64-LABEL: n7_sub_is_not_commutative:
+; X64:       # %bb.0:
+; X64-NEXT:    movl %esi, %eax
+; X64-NEXT:    andl %edi, %eax
+; X64-NEXT:    subl %edi, %eax
+; X64-NEXT:    retq
+  %bias = and i32 %ptr, %mask
+  %r = sub i32 %bias, %ptr ; wrong order
+  ret i32 %r
+}